LIBRA: a distributed routing algorithm for large internets

The loop-identification-and-blocking routing algorithm (LIBRA) is introduced for the distributed maintenance of routing information in large internets. According to LIBRA, each node maintains a routing table; each entry in this table contains the length of and next node in the chosen path to each destination, and a path label. Update messages contain a list of updates; each such update specifies the destination node, the length of the selected path, and its path label. A path label consists of a list of node identifiers used to identify and block a loop before it is used for routing. LIBRA is shown to converge in a finite time after an arbitrary sequence of link-cost or topological changes and to be loop-free at every instant, with no need for internodal coordination spanning more than one hop, or the specification or computation of complete paths from source to destination. LIBRA´s performance is shown to be better than the performance of other routing algorithms previously proposed or currently used in network and internet routing protocols