14.6 Adaptive and Fault-Tolerant Routing There are up to g node-disjoint and edge-disjoint shortest paths between any node pairs in a g-cube Thus, one can route messages around congested or failed nodes/inks A useful notion for designing adaptive wormhole routing algorithms is that of virtual communication networks Each of the two subnetworks in Fig. 14 11 is acyclic Hence, any routing scheme that begins by using links in subnet 0, at some point Subnetwork o Subnetwork 1 switches the path to subnet 1 and from then on remains in Fig. 14.11 Partitioning a 3-cube into subnet 1 is deadlock-free subnetworks for deadlock-free routing Fa2010 Parallel Processing, Low-Diameter Architectures Slide 18Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 18 14.6 Adaptive and Fault-Tolerant Routing There are up to q node-disjoint and edge-disjoint shortest paths between any node pairs in a q-cube Thus, one can route messages around congested or failed nodes/links A useful notion for designing adaptive wormhole routing algorithms is that of virtual communication networks Each of the two subnetworks in Fig. 14.11 is acyclic Hence, any routing scheme that begins by using links in subnet 0, at some point switches the path to subnet 1, and from then on remains in subnet 1, is deadlock-free 0 2 1 3 4 6 5 7 0 2 1 3 4 6 5 7 Subnetwork 0 Subnetwork 1 Fig. 14.11 Partitioning a 3-cube into subnetworks for deadlock-free routing