Abstract
We study stability of routing in multi-hop wireless networks in the framework of adversarial queueing. A routing algorithm consists of three components: a transmission policy to decide on immediate transmissions, a scheduling policy to select a packet to transmit, and a hearing control to coordinate transmissions with scheduling. We consider two kinds of hearing control: proactive and reactive. We compare these policies and show relationships between the wired-network adversarial model and the multi-hop radio network model. In particular, we introduce a family of scheduling policies that are universally stable when using reactive hearing control, and obtain some stability results by using regular transmission oracles. We also prove that networks in which there is at least one node with an out-degree greater than 1 are unstable when using reactive hearing control, but all directed acyclic networks are universally stable, regardless of their out-degree, if using proactive hearing control.
Original language | English (US) |
---|---|
Pages (from-to) | 48-64 |
Number of pages | 17 |
Journal | Journal of Computer and System Sciences |
Volume | 114 |
DOIs | |
State | Published - Dec 2020 |
Keywords
- Adversarial queuing
- Hearing control
- Packet routing
- Queuing discipline
- Radio network
- Transmission policy
- Universal stability
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics