TY - GEN
T1 - Optimal packet-oblivious stable routing in multi-hop wireless networks
AU - Cholvi, Vicent
AU - Garncarek, Paweł
AU - Jurdziński, Tomasz
AU - Kowalski, Dariusz R.
N1 - Funding Information:
V. Cholvi—This work was partially supported by the Ministerio de Ciencia, Innovación y Universidades grant PRX18/000163.
Publisher Copyright:
© Springer Nature Switzerland AG 2020.
PY - 2020
Y1 - 2020
N2 - Stability is an important issue in order to characterize the performance of a network, and it has become a major topic of study in the last decade. Roughly speaking, a communication network system is said to be stable if the number of packets waiting to be delivered (backlog) is finitely bounded at any one time. In this paper, we introduce a new family of combinatorial structures, which we call universally strong selectors, that are used to provide a set of transmission schedules. Making use of these structures, combined with some known queuing policies, we propose a packet-oblivious routing algorithm which is working without using any global topological information, and guarantees stability for certain injection rates. We show that this protocol is asymptotically optimal regarding the injection rate for which stability is guaranteed. Furthermore, we also introduce a packet-oblivious routing algorithm that guarantees stability for higher traffic. This algorithm is optimal regarding the injection rate for which stability is guaranteed. However, it needs to use some global information of the system topology.
AB - Stability is an important issue in order to characterize the performance of a network, and it has become a major topic of study in the last decade. Roughly speaking, a communication network system is said to be stable if the number of packets waiting to be delivered (backlog) is finitely bounded at any one time. In this paper, we introduce a new family of combinatorial structures, which we call universally strong selectors, that are used to provide a set of transmission schedules. Making use of these structures, combined with some known queuing policies, we propose a packet-oblivious routing algorithm which is working without using any global topological information, and guarantees stability for certain injection rates. We show that this protocol is asymptotically optimal regarding the injection rate for which stability is guaranteed. Furthermore, we also introduce a packet-oblivious routing algorithm that guarantees stability for higher traffic. This algorithm is optimal regarding the injection rate for which stability is guaranteed. However, it needs to use some global information of the system topology.
KW - Adversarial queuing
KW - Interference
KW - Packet latency
KW - Routing
KW - Stability
KW - Wireless network
UR - http://www.scopus.com/inward/record.url?scp=85089425076&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089425076&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-54921-3_10
DO - 10.1007/978-3-030-54921-3_10
M3 - Conference contribution
AN - SCOPUS:85089425076
SN - 9783030549206
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 165
EP - 182
BT - Structural Information and Communication Complexity - 27th International Colloquium, SIROCCO 2020, Proceedings
A2 - Richa, Andrea Werneck
A2 - Scheideler, Christian
PB - Springer
T2 - 27th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2020
Y2 - 29 June 2020 through 1 July 2020
ER -