Networks of workstations are poised to become low-cost alternatives to massively parallel processors. Such networked systems rely on high-performance router switches that efficiently utilize available network bandwidth. Irregularities in the distributed system owing to arbitrary interconnection topology, disparate link length, variable traffic demands (real-time, bursty, best-effort), etc., can significantly complicate high-performance routing. This project develops and implements efficient deadlock-free adaptive routing techniques applicable to irregular networks. Research activities being carried out under this grant include (a) developing classification schemes for irregular topologies useful for characterizing message blocking/deadlock phenomena and evaluating performance, (b) developing efficient deadlock-free routing algorithms applicable to irregular NOW-type networks, and (3) developing router switch architectures that maximize routing adaptivity, minimize latency, and utilize bandwidth efficiently over long and variable-length network links.
