Title :
Line graph based fast rerouting and reconfiguration for handling transient and permanent node failures
Author :
Joshi, Prashant D. ; Hamdioui, Said
Abstract :
Design of a class of optimally fault tolerant networks is described using modified line graphs. Appropriate node naming allows the shortest paths to be determined in log time. Self-healing in the presence of transient node failures can also be done in log time, and the rerouting takes place without loops or backtracking. The stretch of the network is maintained at the theoretically minimum value possible of one. The diameters of these networks are best in this class. In addition, the work describes how to reconfigure node connections to make the network optimally fault tolerant once more, in the presence of permanent faults. The changes so required are quantified and shown to be minimal. We demonstrate a class of optimally fault tolerant networks which provide minimal rerouting and reconfiguring overhead while maintaining optimal routing distances in the presence of faults.
Keywords :
fault tolerant computing; graph theory; telecommunication network routing; log time; modified line graphs; node connections; node naming; optimal routing distances; optimally fault tolerant networks; permanent node failures; reconfiguring overhead; rerouting; self-healing; transient node failures; Conferences; Decision support systems; Manganese; Routing; Switches; Connectivity; Diameter of graph; Fault Tolerance; Line Graphs; Node naming;
Conference_Titel :
High Performance Switching and Routing (HPSR), 2014 IEEE 15th International Conference on
Conference_Location :
Vancouver, BC
DOI :
10.1109/HPSR.2014.6900898