Guaranteeing Stability and Delay in Dynamic Networks based on Infinite Games
2014 (English)In: 2014 on IEEE 11th International Conference Mobile Ad Hoc and Sensor Systems (MASS), IEEE conference proceedings, 2014, 461-469 p.Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
IEEE conference proceedings, 2014. 461-469 p.
Research subject SRA - ICT
IdentifiersURN: urn:nbn:se:kth:diva-158224DOI: 10.1109/MASS.2014.41ScopusID: 2-s2.0-84925379721ISBN: 978-1-4799-6035-4OAI: oai:DiVA.org:kth-158224DiVA: diva2:775646
The IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS 2014),Philadelphia, Pennsylvania, October 27-30, 2014
FunderICT - The Next Generation
QC 201501232015-01-042015-01-042015-02-10Bibliographically approved