We’ve come almost to the end of our little series on fast reroute; in this episode we’ll look at maximally redundant trees (MRTs) — this episode is going to be a little “graphy,” so get your seatbelts on.
The general idea behind IP fast reroute is to precalculate a set of alternate paths that can reach a specific destination without using the shortest path. MRTs take this one step farther by building two entire topologies that touch every node in the network (note – not every edge, just every node). If the shortest path fails, traffic can be moved onto one of these two overlay topologies to be forwarded along a “less than best path” towards the destination.
An interesting aside here: MRTs can also be used to build completely noncongruent (or discontiguous) topologies on any physical topology which has at least two paths between every two attached nodes (called a two connected topology). Further investigation down this path might, actually, produce some interesting traffic engineering results that reach beyond the fast reroute use case.
Let’s look at the two connected topology in the embedded graphic, and sort out how this works.
Let’s begin at B, and choose one link to remove from our local database; say the link between B and C. Once we’ve removed this link, B can calculate a path back to the neighbor reachable through the removed link (essentially finding a path back to itself, but breaking the path by removing a single link to prevent a cycle or loop in the topology). We can say this path is directed at B from C’s vantage point, so the path runs counter clockwise around the ring, in the direction [C,F,E,D,A,B].
From this point, we can examine any rings attached to this first ring; in this case, we have the ring containing G. Since we are trying to build a topology directed towards B, we would choose the link between G and D to include. We can call this the red topology. To build the second tree, we can simply reverse the direction when calculating from B; start by removing the [B,A] link, and calculate from B to C. Finally, include the [G,F] path to bring the second ring into the topology. We can call this second topology the blue topology. After we reach this point, we have the topology show below, including the red and blue overlay topologies.
MRT doesn’t build these two trees in precisely the same way – instead, a Depth First Search (DFS) is performed across the topology, and each node (router) assigned a number. Each router then computes a low point and a high point, and then builds a tree based on the low and high points in the tree. Finally “ears,” which are the outlying rings attached to the main topology, are added. The result, however, is the same as what’s described here. See this paper for an explanation of DFS numbering, low points, and high points; see this presentation for another explanation; see the MRT draft for a fuller explanation of MRTs.
What is interesting about this calculation is that it doesn’t interact with the SPF algorithm used by either OSPF or IS-IS. Because of the differences in the way the two ways of computing a tree work, they will produce trees that only overlap sometimes (on the back of napkin, I’d expect either of the two MRT topologies to overlap with the normal shortest path computed by Dijkstra about 50% of the time).
This means that by building a shortest path tree in the normal way, and then overlaying it with a pair of maximally redundant trees built using this process, you actually create three different topologies. These topologies will, of course, share some edges (links) and nodes (routers), but at least one of the three topologies will be able to reach any destination in the network in the case of a single link or router failure. If a link fails, then, the local router can place any traffic it would normally send across the failed link on an MRT topology that hasn’t been impacted by the failure.
The one point to remember here is that once a packet has entered either of the two overlay topologies, it cannot leave that topology until it reaches its final destination. If it does leave the overlay topology before all the routers in the network have been notified of the failure, SPF has been run, and a new shortest path tree computed, there is a chance of a loop.
While it’s possible to use just about any tunneling mechanism to build the two overlay topologies calculated by MRT, the MRT drafts describe using MPLS to do so.
Next time, we’ll think a little about the relationship between fast reroute and centralized control planes.