METHOD FOR LOOP-FREE MULTIPATH ROUTING USING PREDECESSOR INFORMATION

A method is described for routing network traffic based on distance information to provide multiple paths that need not have equal costs. The routing algorithm MPATH of the present method provide loop-free routing at every instant, without the need of internodal synchronization which spans more than a single hop. Paths are computed using shortest distances and predecessor information in the routing computation. The use of multiple-successors allows for load-balancing within the network. The algorithm is both distributed and scalable to large networks due to its use of only one-hop synchronization. A number of procedures are described by way of example, including path computation, main table updating, neighbor table updating, and a multipath (MPATH) algorithm.