Dynamic routing in multiparented networks

Richard Gibbens
Frank Kelly
Stephen Turner

IEEE/ACM Transactions on Networking, volume 1(1993) pages 261-270.


In this paper, we investigate some of the consequences for dynamic routing schemes of dual-and multiparented networks, in which a call can enter (or leave) the network at two or more points. In particular, we compare bounds on the performance of optimal dynamic routing strategies which respectively ignore and utilize the multiparented structure, and show that simple schemes, easily implemented and analyzed, are able to achieve most of the additional advantages allowed to dynamic routing schemes by multiparenting. Further, we illustrate the robust behaviour of these schemes under traffic mismatches as well as multiple link or node failure events.

Frank Kelly's papers