1. Spreading Computations for Loop-Free Multipath Routing in Computer Networks
- Author
-
Garcia-Luna-Aceves, J.J., Moghaddassian, Morteza, and Hsieh, Charles
- Subjects
loop-free routing ,multipath routing ,diffusing computations ,destination sequence numbers ,distributed computations. - Abstract
Loop-free routing approaches based on distance information combine a Local Ordering Condition (LOC) with a distributed reordering computation (DRC). The LOC allows routers to determine whether they can independently change next hops to destinations without creating a routing loop, and the DRC permits routers re-establish their ordering relative to a destination when the LOC is not satisfied. A new type of DRC called Spreading Computations is shown to be inherently more efficient than DRCs used in existing loop-free routing protocols. A new routing algorithm based on spreading computations is presented and compared with OSPF, DSDV, and RIPv2 using the ns-3 simulator. The results show that using spreading computations results in faster convergence speeds after link or router recoveries or failures.
- Published
- 2024