DIMACS TR: 99-19
Deadlock-Free Routing in Irregular Networks Using Prefix Routing
Algorithm
Authors: Jie Wu and Li Sheng
ABSTRACT
In this paper, we propose a deadlock-free routing
in irregular networks using prefix routing.
Prefix routing is a special type of routing
with a compact routing table associated with each node
(processor). Basically, each outgoing channel of a node
is assigned a special label and an outgoing channel is selected if
its label is a prefix of the label of the destination node. Node and
channel labeling in an irregular network is done through constructing
a spanning tree. The routing process follows a two-phase process of
going up and then down along the spanning tree, with a possible cross
channel (shortcut) between two branches of the tree between two
phases. We show that the proposed routing scheme is deadlock- and
livelock- free.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-19.ps.gz
DIMACS Home Page