Line graph based fast rerouting and reconfiguration for handling transient and permanent node failures

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.