Abstract

Link failures are a common cause of service disruption in computer networks. When a link of a network fails, all communications which were using the failed link are temporarily interrupted. Techniques have been engineered to alleviate the consequences of hardware failure in a network by rerouting traffic from the failed link to other links. When performed by low communication layers, rerouting is fast but expensive as additional hardware is needed. On the other hand, it is possible to reroute traffic at higher layers using software mechanisms, but such solutions prove to be slow. Moreover, most rerouting schemes are not optimized for multicasting applications such as teleconferencing where one sender can send data to several receivers.

The Internet is a datagram packet switching network where data is carried in IP packets. Recently, Multiprotocol Label Switching (MPLS) has been devised to carry IP packets over virtual circuits, thus combining the advantages of datagram packet switching and virtual circuit switching. In this thesis, we devise a solution to protect multicast communications in MPLS networks from a link failure. We present a graph algorithm which selects a backup path in a multicast routing tree that carries multicast traffic. The backup path aims at minimizing the number of receivers of the multicast routing tree that are dropped from the communication if a single link of the tree fails. We present MPLS multicast Fast Reroute, a new mechanism for MPLS networks which reroutes traffic over a backup path when a link of the multicast routing tree fails. We provide an implementation of MPLS multicast Fast Reroute on PC routers running the Linux operating system. We experimentally show that MPLS multicast Fast Reroute can repair multicast routing trees in less than 50 ms, making link failures unnoticeable to all end users.