Universal stability in multi-hop radio networks

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...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2020-12, Vol.114, p.48-64
Main Authors: Chlebus, Bogdan S., Cholvi, Vicent, Kowalski, Dariusz R.
Format: Article
Language:English
Subjects:
Adversarial queuing
Hearing control
Packet routing
Queuing discipline
Radio network
Transmission policy
Universal stability
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2020.05.009