Attaining Loop-Free Routing with Coordinated Updates Carrying Minimum Link-State Information

The Acyclic Source-Tree Routing Algorithm (ASTRAL) is introduced to provide loop-free multipath routing in computer networks. With ASTRAL, routers share link-state information only about those links used in their paths to destinations rather than complete topology data, and without requiring periodic messaging. ASTRAL attains loop freedom by making routers coordinate with their immediate neighbors so that they change their next hops to destinations only after routers verify that the data in their topology databases are consistent with the topology data stored at their neighbors. ASTRAL is proven to guarantee loop-free routes at every instant and to converge to shortest paths within a finite time. ASTRAL is shown to be at least as efficient as the ideal link-state algorithm, more efficient than existing link-state routing protocols like OSPF and IS-IS, and more efficient than DUAL, which is the basis of EIGRP.