Greedy Failure-Carrying Packets

One approach to obtain scalable routing table sizes at the cost of a possible deviation from shortest paths is the creation of a limited number of spanning trees along which packets are forwarded greedily. An often overlooked drawback of this approach, however, is the potentially severe overhead for reorganizing tree structures and updating routing tables in the presence of node or link failures. Our rerouting strategy Greedy Failure-Carrying Packets (GFCP) encodes failure information in the data packet headers and uses this information in combination with unadapted routing tables to forward packets to their destination around failed links or nodes. This reduces the need to adapt the routing tables instantly and thereby reduces control overhead. The simulative evaluation of GFCP and a detailed comparison with an alternative rerouting strategy on an Internet-like topology show that GFCP performs well with regard to delivery ratio while excelling in the selection of short alternative paths, thereby reducing the load on the network. In contrast to alternative rerouting strategies, GFCP further reduces the network load by early discarding undeliverable packets.