Paper Info
Title
Improving the Up*/Down* Routing Scheme for Networks of Workstations
Abstract
Networks of workstations (NOWs) are being considered as a cost-effective alternative to parallel computers. Many NOWs are arranged as a switch-based network with irregular topology, which makes routing and deadlock avoidance quite complicated. Current proposals use the up*/down* routing algorithm to remove cyclic dependencies between channels and avoid deadlock. Recently, a simple and effective methodology to compute up*/down* routing tables has been proposed by us. The resulting up*/down* routing scheme makes use of a different link direction assignment to compute routing tables. Assignment of link direction is based on generating an underlying acyclic connected graph from the network graph. In this paper, we propose and evaluate new heuristic rules to compute the underlying graph. Moreover, we propose a traffic balancing algorithm to obtain more efficient up*/down* routing tables when source routing is used. Evaluation results show that the routing algorithm based on the new methodology increases throughput by a factor of up to 2.8 in large networks, also reducing latency significantly.
Year
DOI
Venue
2000
10.1007/3-540-44520-X_123
Euro-Par
Keywords
Field
DocType
different link direction assignment,network graph,new heuristic rule,deadlock avoidance,underlying graph,link direction,effective methodology,source routing,routing algorithm,routing scheme,large network,connected graph,parallel computer,cost effectiveness
Multipath routing,Link-state routing protocol,Dynamic Source Routing,Policy-based routing,Static routing,Computer science,Computer network,Destination-Sequenced Distance Vector routing,Routing table,Zone Routing Protocol,Distributed computing
Conference
Volume
ISSN
ISBN
1900
0302-9743
3-540-67956-1
Citations 
PageRank 
References 
36
2.76
6
Authors
2
Name
Order
Citations
PageRank
José Carlos Sancho138229.97
Antonio Robles248130.40