Faults in irregular networks have previously been handled through a global or local network reconfiguration, which leaves the net-work unavailable or disconnected until the reconfiguration is finished. We present FRoots, which leaves the network available and connected by using redundant paths. Only packets residing in the network at the fault time might become unroutable, and FRoots can be designed to offer an alternative path for such packets. To accommodate sequential, multi-ple faults, reconfiguration of the obsolete paths is done without a severe downgrade of network throughput. PRoots is based on a load balanc-ing version of Up~*/Down~* routing, and uses a modest number of virtual channels to achieve redundancy properties. However, FRoota utilizes all channels in the fault-free case, thus experiencing no performance loss compared to its predecessor routing algorithm.
展开▼