Paper Info
Title
Fast, minimal and oblivious routing algorithms on the mesh with bounded queues
Abstract
This paper studies fast, deterministic, permutation routing algorithms with bounded queues on the n × n mesh. Our main result is an &Ogr;(n)-step, strongly-dimensional (and thus also source-oblivious and minimal) permutation routing algorithm. This algorithm works under a relaxed model in which nodes can freely send data to their neighbors.In a more prevalent model, the standard model, data may be sent only when accompanied by a packet. Under this model we present the following two algorithms: An &Ogr;(n log n)- step strongly-dimensional algorithm and an &Ogr;(n)-step oblivious and weakly-dimensional (and thus also minimal) algorithm.As said, all these algorithms store only &Ogr;(l) packets in a node. Moreover, they use only &Ogr;(log n) state bits in a node and transfer only &Ogr;(log n) data bits on an edge in a step.All our routing algorithms are based on the following new technique of open-loop flow control. An algorithm is composed of two stages: setup and transportation.The setup stage computes certain values and stores them in the network. In particular, it computes a rational number &agr;(e) for certain critical edges e.The transportation stage moves the packets to their destinations. It uses the computed values to slow the packets so that the traffic on each critical edge e is bounded by &agr;(e); that is, at most [&agr;(e).l] packets traverse e during any l consecutive steps.This bound on the burstiness of the traffic enables the algorithm to avoid hot spots and maintain bounded queues. The algorithm achieves this by an open-loop control: that is, during this stage no information is transferred in a direction opposite to that of the packets.An additional novelty of our algorithms is the application of a dynamic routing problem to solve a static one. The dynamic problem in question seems easy, as its network is just a linear array. We show, however, that this problem is unsolvable by the techniques of Adversarial Queuing Theory.
Year
DOI
Venue
2001
10.1145/378580.378584
Journal of Interconnection Networks
Keywords
Field
DocType
oblivious routing algorithm,n mesh,packets traverse e,step strongly-dimensional algorithm,algorithm work,n log n,log n,routing algorithm,permutation routing algorithm,dynamic routing problem,bounded queue,standard model,hot spot,flow control,dynamic routing,queuing theory,rational number
Link-state routing protocol,Dynamic Source Routing,Static routing,Computer science,Parallel computing,Destination-Sequenced Distance Vector routing,DSRFLOW,Algorithm,Routing table,Time complexity,Dynamic problem,Distributed computing
Conference
Volume
Issue
ISBN
2
4
1-58113-409-6
Citations 
PageRank 
References 
1
0.36
10
Authors
2
Name
Order
Citations
PageRank
Ami Litman124049.78
Shiri Moran-Schein291.90