MIT 6.02 DRAFT Lecture NotesFall 2010 (Last update: November 11, 2010)Comments, questions or bug reports?Please contact [email protected] 19Network Routing - IIRouting Around FailuresThis lecture describes the mechanisms used by distributed routing protocols to handle linkand node failures, packet losses (which may cause advertisements to be lost), changes inlink costs, and (as in the previous lecture) new nodes and links being added to the network.We will use the term churn to refer to any changes in the network topology. Our goal is tofind the best paths in the face of churn. Of particular interest will be the ability to routearound failures, finding the minimum-cost working paths between any two nodes fromamong the set of available paths.We start by discussing what it means for a routing protocol to be correct, and define ourcorrectness goal in the face of churn. The first step to solving the problem is to discoverfailures. In routing protocols, each node is responsible for discovering which of its linksand corresponding nodes are still working; most routing protocols use a simple HELLOprotocol for this task. Then, to handle failures, each node runs the advertisement and integra-tion steps periodically. The idea is for each node to repeatedly propagate what it knowsabout the network topology to its neighbors so that any changes are propagated to all thenodes in the network. These periodic messages are the key mechanism used by routingprotocols to cope with changes in the network. Of course, the routing protocol has to berobust to packet losses that cause various messages to be lost; for example, one can’t usethe absence of a single message to assume that a link or node has failed, for packet lossesare usually far more common than actual failures.We will see that the distributed computation done in the distance-vector protocol in-teracts adversely with the periodic advertisements and causes the routing protocol to notproduce correct routing tables in the face of certain kinds of failures. We will present andanalyze a few different solutions that overcome these adverse interactions, which extendour distance-vector protocol. We also discuss some circumstances under which link-stateprotocols don’t work correctly. We conclude this chapter by comparing link-state and dis-tance vector protocols.12CHAPTER 19. NETWORK ROUTING - IIROUTING AROUND FAILURES� 19.1 Correctness and ConvergenceIn an ideal, correctly working routing protocol, two properties hold:1. For any node, if the node has a route to a given destination, then there will be ausable path in the network topology from the node to the destination that traversesthe link named in the route. We call this property route validity.2. In addition, each node will have a route to each destination for which there is ausable path in the network topology, and any packet forwarded along the sequenceof these routes will reach the destination (note that a route is the outgoing link ateach switch; the sequence of routes corresponds to a path). We call this property pathvisibility because it is a statement of how visible the usable paths are to the switchesin the network.If these two properties hold in a network, then the network’s routing protocol is said tohave converged. It is impossible to guarantee that these properties hold at all times becauseit takes a non-zero amount of time for any change to propagate through the network to allnodes, and for all the nodes to come to some consensus on the state of the network. Hence,we will settle for a less ambitious—though still challenging—goal, eventual convergence.We define eventual convergence as follows: Given an arbitrary initial state of the networkand the routing tables at time t =0, suppose some sequence of failure and recovery eventsand other changes to the topology occur over some duration of time, τ. After t = τ , sup-pose that no changes occur to the network topology, also that no route advertisements orHELLO messages are lost. Then, if the routing protocol ensures that route validity and pathvisibility hold in the network after some finite amount of time following t = τ, then the protocol issaid to “eventually converge”.In practice, it is quite possible, and indeed likely, that there will be no time τ afterwhich there are no changes or packet losses, but even in these cases, eventual convergenceis a valuable property of a routing protocol because it shows that the protocol is workingtoward ensuring that the routing tables are all correct. The time taken for the protocol toconverge after a sequence of changes have occurred (or from some initial state) is calledthe convergence time. Thus, even though churn in real networks is possible at any time,eventual convergence is still a valuable goal.During the time it takes for the protocol to converge, a number of things could gowrong: routing loops and reduced path visibility are two significant problems.� 19.1.1 Routing LoopsSuppose the nodes in a network each want a route to some destination D. If the routesthey have for D take them on a path with a sequence of nodes that form a cycle, then thenetwork has a routing loop. That is, if the path resulting from the routes at each successivenode forms a sequence of two or more nodes n1,n2,...,nkin which ni= njfor some i �= j,then we have a routing loop. Obviously, packets sent along this path to D will be stuckin the network forever, unless other mechanisms are put in place to “flush” such packetsfrom the network (see Section 19.2).SECTION 19.2. ALLEVIATING ROUTING LOOPS: HOP LIMITS ON PACKETS 3� 19.1.2 Reduced Path Visibil ityThis problem usually arises when a failed link or node recovers after a failure and a pre-viously unreachable part of the network now becomes reachable via that link or node.Because it takes time for the protocol to converge, it takes time for this information topropagate through the network and for all the nodes to correctly compute paths to nodeson the “other side” of the network. During that time, the routing tables have not yet con-verged, so as far as data packets are concerned, the previously unreachable part of thenetwork still remains that way.� 19.2 Alleviating Routing Loops: Hop L i mi ts on PacketsIf a packet is sent along a sequence of routers that are part of a routing loop, the packetwill remain in the network until the routing loop is eliminated. The typical time scales overwhich routing protocols converge could be