DEADLOCK-FREE ADAPTIVE ROUTING IN MULTICOMPUTER NETWORKS USING VIRTUAL CHANNELS

The use of adaptive routing in a multicomputer inter-connection networ k improves network performance by making use of all available paths an d provides fault tolerance by allowing messages to be routed around fa iled channels and nodes. This paper describes two deadlock-free adapti ve routing algorithms. Both algorithms allocate virtual channels using a count of the number of dimension reversals a packet has performed t o eliminate cycles in resource dependency graphs. The static algorithm eliminates cycles in the network channel dependency graph. The dynami c algorithm improves virtual channel utilization by permitting depende ncy cycles and instead eliminating cycles in the packet wait-for graph . We prove that these algorithms are deadlock-free and give experiment al measurements of their performance. For nonuniform traffic patterns, these algorithms improve network throughput by a factor of three comp ared to deterministic routing. The dynamic algorithm gives better perf ormance at moderate traffic rates but requires source throttling to re main stable at high traffic rates. Both algorithms allow the network t o gracefully degrade in the presence of faulty channels.