Principles of Ultradependability in Chaotic Routing
Abstract
Generally, routers used in state-of-the-art parallel computers are a form of oblivious router known as demonstration order routers. Examples include the iPSC/2, nCUBE, DELTA, Paragon, Dash, J-Machine, etc. In networks based on these routers all packets between source S and destination D take a single path, oblivious to network congestion and faults. This can lead to poor performance under high loads when congestion can be significant, and to system failure in large or unmaintainable systems where faults are likely. For these two reasons - performance and dependability - adaptive routing techniques have long been advocated. Adaptive routers can be divided into two broad classes, minimal adaptive, in which packets always take a shortest path to their destinations, and nonminimal adaptive, in which packet routes are not restricted to shortest paths. Though there have been many proposals for both types, it is generally true that nonminimal adaptive routers are superior minimal adaptive routers 10, 13. This is consistent with one's intuition follows: Although minimal adaptive router can bypass congestion by sending packets along alternate paths, they discover the congestion too late. That is, when there are no alternate forward paths to choose from, the packet's forward progress is stalled, and is now contributing to the congestion. This affect motivates nonminimal adaptive routing in which a packet can back up or deroute, and go around congestion when there are no forward paths.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 30, 1993
- Accession Number
- ADA277422
Entities
People
- Lawrence H Snyder
Organizations
- University of Washington