Fast dynamic reconfiguration in irregular networks

Exploitation of the wiring flexibility in Networks of Workstations demands configuration methods that can handle dynamic changes in irregular topologies. During reconfiguration of a network based on virtual cut-through or wormhole switching, however deadlocks in the transition phase between the old and the new routing function must be avoided. The avoidance of such deadlocks will in general make the performance of the network suffer during reconfiguration. Keeping reconfiguration time as short as possible, and leaving as much as possible of the network untouched is therefore of importance. We propose a method for dynamic reconfiguration of networks using up*/down* routing that aims at reducing the consequences of reconfiguration. This is done by identifying a restricted parr of the network, the skyline, as the only part where a full reconfiguration is necessary. This means that most of the network does not need to take part in the reconfiguration at all (other than adding entries for new nodes, and removing entries for removed nodes). Experiments show that for the most frequent configuration changes the skyline will be empty in 85-95% of the cases, leaving the whole of the network operational through the entire reconfiguration. For the most dramatic changes in topology-the addition of a link connecting two previously disjoint networks-an average of 90% of the links can start using the new routing function immediately for some topologies. Our approach is in principle orthogonal to other approaches, thus existing methods for dynamic reconfiguration can be applied in the reconfiguration of the skyline