×

A game-theoretic approach to routing under adversarial conditions. (English) Zbl 1198.90078

Calude, Christian S. (ed.) et al., Theoretical computer science. 6th IFIP WG 2.2 international conference, TCS 2010, held as a Part of the World Computer Congress (WCC 2010), Brisbane, Australia, September 20–23, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15239-9/hbk; 978-3-642-15240-5/ebook). IFIP Advances in Information and Communication Technology 323, 355-370 (2010).
Summary: We present a game-theoretic framework for modeling and solving routing problems in dynamically changing networks. The model covers the aspects of reactivity and non-termination, and it is motivated by quality-of-service provisioning in cognitive radio networks where data transmissions are interfered by primary systems. More precisely, we propose an infinite two-player game where a routing agent has to deliver network packets to their destinations while an adversary produces demands by generating packets and blocking connections. We obtain results on the status of basic problems, by showing principal limitations to solvability of routing requirements and singling out cases with algorithmic solutions.
For the entire collection see [Zbl 1200.68003].

MSC:

90B18 Communication networks in operations research
91A80 Applications of game theory
91A05 2-person games
68M10 Network design and communication in computer systems
PDFBibTeX XMLCite
Full Text: DOI