Digital Library

Abstract: The tutorial surveys three issues in the design of interconnection networks, switching techniques, mechanisms for deadlock handling, and routing algorithms. These three issues are closely related to each other. Switching techniques have a major impact on performance. Several switching techniques are described, including some recent hybrid techniques, and highlighting the relationship between switching technique and network technology.

Routing alogirthms determine the path followed by messages from source to destination. Adaptive routing algorithms have the potential to increase link utilization and throughput by avoiding congested regions in the network. However, adaptive routing algorithms are prone to deadlock. The tutorial presents several techniques for deadlock handling, and their application to the design of adaptive routing algorithms. The talk describes techniques for deadlock avoidance and recovery, mainly focusing on proposals that allow cyclic dependencies between network resources. Progressive deadlock recovery is emerging as an alternative to deadlock avoidance. In order to make it viable, it is necessary to reduce the frequency of deadlock and to implement an efficient deadlock detection mechanism. Deadlocks are characterized during the talk, presenting mechanisms to reduce the frequency of deadlock, and describing efficent me chanisms for distributed deadlock detection.

Several methodologies for the design of addaptive routing algorithms are described, as well as their application to multicomputer networks and networks of workstations with irregular topologies. Networks of workstations may require long links to connect different nodes and switches. The effect of wire length on performance, and the relationship with flow contorl mechanisms is analyzed. Finally, some evaluation results show the impact of different design parameters on performance.

Speaker's Biography: Jose Duato is a Professor in the Departement of Systems Engineering, Computers and Automation of the Technical University of Valencia. His research interests are the interconnection networks for multicomputers, multiprocessors and networks of workstations. Professor Duato developed the first theory of deadlock-free adaptive routing, and is a co-author of the book "inteconnection Networks: An Engineering Approach". Dr. Duato is serving as an editor of IEEE Transactions on Parallel and Distributed Systems, and served on the Program Committees of several major conferences.

• Click on this Start PDF link
• Use the "Next Page" button to advance the slides as the talk progresses.
• Photographs from the presentation.