Name
Abstract | ||
|---|---|---|
This paper describes a new class of deadlock-free routing algorithms for irregular networks based on ordered links. In this case, the links are ordered by partitioning them into a set of layers, each layer containing a spanning tree (when possible). Deadlock free routes can then be derived by using links with non-decreasing order. The deadlock-freedom property is proved. Two different implementations of the routing algorithm are studied. The resultant performance of these algorithms is then compared to other known algorithms: the shortest-path algorithm (which may result in deadlocks) and the up */down* algorithm. Various performance metrics are considered, including path-length, network capacity, fault tolerance and time of computation. We argue that network capacity is the most important metric to optimize. It is shown that the proposed algorithms are promising since they usually achieve higher network capacity than up */down*, while they perform only slightly worse than up */down* in other metrics. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1109/LCN.2002.1181765 | LCN |
Keywords | Field | DocType |
network topology,spanning tree,channel capacity,fault tolerant,protocols,shortest path algorithm,graph theory | Multipath routing,Link-state routing protocol,Path vector protocol,Static routing,Computer science,Hierarchical routing,Routing domain,Computer network,Routing table,Distributed computing,Routing protocol | Conference |
ISSN | ISBN | Citations |
0742-1303 | 0-7695-1591-6 | 1 |
PageRank | References | Authors |
0.35 | 6 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dah Ming Chiu | 1 | 3618 | 694.24 |
| Miriam Kadansky | 2 | 27 | 2.41 |
| Radia J. Perlman | 3 | 459 | 170.30 |
| John Reynders | 4 | 2 | 1.60 |
| Guy Steele | 5 | 22 | 3.04 |
| Murat Yuksel | 6 | 445 | 61.52 |