Guaranteeing Stability and Delay in Dynamic Networks based on Infinite Games

We study stability and delay in dynamic networks under adversarial conditions. Adversarial conditions are mandatory in establishing deterministic performance guarantees in networks. Under this framework, we concentrate on the general stability region for a network, i.e. without specifying the routing algorithm. This is in contrast to related work for adversarial network conditions, where usually the backpressure routing algorithm is considered. Our work consists of four novel contributions: (1) We present a novel analysis model which is based on the theory of infinite two-player games; (2) Using this approach, we can characterize the stability region of networks under adversarial conditions for arbitrary routing schemes; (3) We determine conditions under which a delay bound for packet forwarding under adversarial conditions exists; (4) We provide a backtracking algorithm which determines in a model-checking fashion network stability. The backtracking algorithm is furthermore shown to reduce the computational effort significantly for practical scenarios.QC 20150123