FROOTS - Fault Handling in Up{sup}*/Down{sup}* Routed Networks with Multiple Roots

摘要

Faults in irregular networks have previously been handled through a global or local network reconfiguration, which leaves the network 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, multiple faults, reconfiguration of the obsolete paths is done without a severe downgrade of network throughput. FRoots is based on a load balancing version of Up{sup}*/Down{sup}* routing, and uses a modest number of virtual channels to achieve redundancy properties. However, FRoots utilizes all channels in the fault-free case, thus experiencing no performance loss compared to its predecessor routing algorithm.