32/2011 : Brief announcement: full reversal routing as a linear dynamical system

RR Number

32/2011

Conference

SPAA 2011

Author(s)

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

Abstract

Although substantial analysis has been done on the Full Reversal (FR) routing algorithm since its introduction by Gafni and Bertsekas in 1981, a complete understanding of its functioning---especially its time complexity---has been missing until now. In this paper, we derive the first exact formula for the time complexity of FR: given any (acyclic) graph the formula provides the exact time complexity of any node in terms of some simple properties of the graph. Our major technical insight is to describe executions of FR as a dynamical system, and to observe that this system is linear in the min-plus algebra. As a consequence of the insight provided by the new formula, we are able to prove that FR is time-efficient when executed on tree networks. This result exposes an unstable aspect of the time complexity of FR that has not previously been reported. Finally, our results for FR are instrumental in providing an exact formula for the time complexity of a generalization of FR, as we show in a companion paper that the generalization can be reduced to FR.

Bibtex

@inproceedings{CFWW11:SPAA,
 author = {Charron-Bost, Bernadette and Fuegger, Matthias and Welch, Jennifer L. and Widder, Josef},
 title = {Brief announcement: full reversal routing as a linear dynamical system},
 booktitle = {Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures},
 series = {SPAA '11},
 year = {2011},
 isbn = {978-1-4503-0743-7},
 location = {San Jose, California, USA},
 pages = {129--130},
 numpages = {2},
 url = {http://doi.acm.org/10.1145/1989493.1989510},
 doi = {http://doi.acm.org/10.1145/1989493.1989510},
 acmid = {1989510},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {linear dynamical systems, link reversal, min-plus algebra, routing, time complexity},
} 

Download