7/2011 : Full Reversal Routing as a Linear Dynamical System

RR Number

7/2011

Comment

A shorter version appeared at SIROCCO 2011.

Author(s)

Bernadette Charron-Bost, Matthias Fuegger, Jennifer L. Welch, Josef Widder

Abstract

Link reversal is a versatile algorithm design paradigm, originally proposed by Gafni and Bertsekas in 1981 for routing, and subsequently applied to mutual exclusion, resource allocation, and various problems in wireless ad-hoc networks. Although these algorithms are well-known, until now there have been only preliminary results on time complexity, even for the simplest link reversal scheme for routing, called Full Reversal (FR). In this paper we tackle this open question for arbitrary communication graphs. Our central technical insight is to describe the behavior of FR as a dynamical system, and to observe that this system is linear in the min-plus algebra. From this characterization, we derive the first exact formula for the time complexity: Given any node in any (acyclic) graph, we present an exact formula for the time complexity of that node, in terms of some simple properties of the graph. These results for FR are instrumental in analyzing a broader class of link reversal routing algorithms, as we show in a companion paper that such algorithms can be reduced to FR. In the current paper, we further demonstrate the utility of our formulas by using them to show the previously unknown fact that FR is time-efficient when executed on trees.

Bibtex

@techreport{CFWW11:fr-tech,
  author =       "Bernadette Charron-Bost and Matthias Fuegger and Jennifer L. Welch and Josef Widder",
  title =        "Full Reversal Routing as a Linear Dynamical System",
  institution =  "Technische Universit{\"a}t Wien, Institut f{\"u}r Technische Informatik",
  address =      "Treitlstr. 1-3/182-2, 1040 Vienna, Austria",
  type =         "Research Report",
  year =         "2011",
  number =       "7/2011"
}

Download

Get techreport.pdf - Adobe PDF-format, (124.96 KB; posted at April 22 2011)