2004 International Conference on Dependable Systems and Networks (DSN'04)
Delivering Packets During The Routing Convergence Latency Interval Through Highly Connected Detours
Florence, Italy
June 28-July 01
ISBN: 0-7695-2052-9
Routing protocols present a convergence latency for all routers to update their tables after a fault occurs and the network topology changes. During this time interval, which in the Internet has been shown to be of up to minutes, packets may be lost before reaching their destinations. In order to allow nodes to continue communicating during the convergence latency interval, we propose the use of alternative routes called detours. In this work we introduce new criteria for selecting detours based on network connectivity. Detours are chosen without the knowledge of which node or link is faulty. Highly connected components present a larger number of distinct paths, thus increasing the probability that the detour will work correctly. Experimental results were obtained with simulation on random Internet-like graphs generated with the Waxman method. Results show that the fault coverage obtained through the usage of the best detour is up to 90%. When the three best detours are considered, the fault coverage is up to 98%.
Index Terms:
Routing, Fault-Tolerance, Graph Theory, Connectivity, Cut Trees
Citation:
Elias Proc?pio Duarte Jr., Rog?rio Santini, Jaime Cohen, "Delivering Packets During The Routing Convergence Latency Interval Through Highly Connected Detours," dsn, pp.495, 2004 International Conference on Dependable Systems and Networks (DSN'04), 2004