Accession Number:

ADA277422

Title:

Principles of Ultradependability in Chaotic Routing

Descriptive Note:

Final rept. 1 Oct 1990-30 Sep 1993

Corporate Author:

WASHINGTON UNIV SEATTLE DEPT OF COMPUTER SCIENCE AND ENGINEERING

Personal Author(s):

Report Date:

1993-09-30

Pagination or Media Count:

10.0

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 iPSC2, 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 ones 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 packets 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.

Subject Categories:

  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE