Universal stability in multi-hop radio networks (Q2194858)

This paper is concerned with analyzing the stability of routing protocols in multi-hop wireless networks, in the context of adversarial queueing. A routing protocol needs a transmission policy, a scheduling policy and hearing control. The authors analyze two types of hearing control, viz., reactive and proactive. Based on their analyses, they develop a family of scheduling policies that are universally stable. The principal contributions of this paper are as follows: \begin{enumerate} \item The introduction of a formal framework for analyzing routing protocols with respect to a transmission policy, a scheduling policy and hearing control. The framework is robust and can be generalized to other settings as well. \item A connection is established between wired models and multi-hop radio network models. In particular, they show that any scheduling policy which is unstable in the former under adversarial models is also unstable in the latter. \item Showing that some scheduling policies which are stable in wired networks are unstable in multi-hop radio networks. \end{enumerate} The field of radio networks has been studied extensively in the literature. The first author has made several contributions to this topic in previous papers. In the current paper, the issue of stability in routing algorithms and in particular universal stability are considered. The paper has a nice expository style and all the basic concepts, such as stability against an adversary and universal stability, are defined appropriately, which makes for a pleasant reading. The paper is also somewhat comprehensive in that the authors analyze the scheduling problem from several perspectives. On the hearing control front, they consider both proactive and reactive control. They study the effects of scheduling policies on both wired and wireless models. One of the interesting contributions is that a scheduling policy which is stable in wired networks may be unstable in multi-hop radio networks. It is clear that the paper makes important contributions to the field of radio networks.