Simple routing strategies for adversarial systems

摘要: In this paper we consider the problem of delivering dynamically changing input streams in networks where both topology and can change an unpredictable way. particular, present two simple distributed balancing algorithms (one for packet injections one flow injections) show that case a single receiver these will always ensure number packets or system is bounded at any time step, even injection process completely saturates capacities available edges if network changes We also maximum be essentially best possible by providing lower bound holds online algorithm, whether not. Interestingly, our do not behave well adversarial setting. other extreme static pattern converge to point which they achieve average routing close achieved strategy. This demonstrates there are efficient very different scenarios.