Section 2.1. Vector Protocol Basics
2.1. Vector Protocol BasicsA vector is defined as a quantity that has both magnitude and direction. An IP route is a vector, in which the direction is some egress interface or a next-hop address. How the route's magnitude is defined varies from one protocol to another. It might be a distance measured in router hops (RIP), autonomous system hops (BGP), or a sum of interface characteristics (IGRP and EIGRP). The magnitude might also be a sum of dimensionless interface metrics (OSPF and IS-IS). But stating that a route is a vector is not really useful in differentiating vector protocols from link state protocols. A route derived by either is a vector. My friend Paul Goyette points out that in virology, a vector is a means of propagation of some pathogen. In fact, the Latin root of the word, vectus, means "bearer" or "carrier." For example, a mosquito is a vector that carries malaria from one organism to the next: Mosquito A picks up the malaria virus from organism X and deposits it in organism Y. Mosquito B picks up the virus from organism Y and deposits it in organism Z. This definition gets us closer to understanding a vector protocol: Update message A picks up route data from router X and deposits it in router Y. Update message B picks up route data from router Y and deposits it in router Z (Figure 2.1). Figure 2.1. Update A and Update B are vectorscarriers of information from one router to another. Getting back to mosquitoes, the virus that mosquito B takes away from organism Y is not the same virus that mosquito A deposited in organism Y. The deposited virus multiplies and possibly even mutates within the organism before some copy of it is picked up by mosquito B. Similarly, the route data update message B picks up from router Y is not the same route data that update message A deposited in router Y, even though the route data pertains to the same destination. An algorithm modifies the deposited route data in router Y in such a way that the data reflects that router's position in the network relative to the route's destination. We have now defined, at a very high level, both the procedure used by vector protocols to communicate destination addresses and their associated information between routers, and the algorithm that uses the information to calculate shortest paths to the destination addresses. Moving with all due prudence away from malarial mosquitoes, let's add more focus to the definitions. Information for a particular destination prefix originates in some router. The router learns the information in one of three ways:
A vector protocol transmits the destination prefix to its directly connected neighbors. Each neighbor, when it receives the route information, modifies the information in such a way that the route information indicates the distance from that router to the originating router. For example, RIP increases the router hop count by one. The modified route is then added into the router's routing table. Only then is the route sent to that router's own directly connected neighbors, to be modified again by those neighbors. 2.1.1. Vector Protocol ConvergenceFigure 2.2 shows how route information is vectored from the originating routers.[1] At time t0, the only entries in the four routers' routing tables are their directly connected networks, indicated by a hop count of 0. No other information has yet been communicated by the routing protocol.
Figure 2.2. Routing information converges in a hop-by-hop manner in a network using a distance vector protocol. At time t1, the first updates have been received and processed by the routing protocol, and the results have been entered into the routing tables. Each new time increment represents a new update period, until at time t3 all four routing tables have all the information needed to reach all subnets in the network. At this time the routes to all subnets in the network are said to be converged. Processing of the update messages involves two steps. First, the advertised hop count is incremented by one. If router B tells router A that a destination prefix is two hops away from itself, router A increments the hop count to three to indicate its own distance to the destination. In the second step, the routing protocol compares the received routes and their newly incremented hop counts with the existing routing table entries. If there is no entry for the particular destination address, an entry is made. The entry includes the destination prefix, the distance (hop count), and the address of the neighboring router that sent the advertisement. If the route table already contains an entry for the processed route, the hop counts are compared. If the newly incremented hop count of the received route is equal to or greater than the hop count of the existing entry, no change is made. But if the hop count of the received route is less than the hop count of the existing entry, the entry is replaced by the new route. In this way, the shortest route to each destination is maintained in the routing table. For example, at time t1, router B advertises prefixes 10.1.2.0 and 10.1.3.0 to router A, both with a hop count of 0 because the prefixes are directly connected to B. Router A increments the hop counts of both prefixes to 1, and then looks at the entries in its routing table. There is already an entry for 10.1.2.0, and the hop count of the entry is 0. That is less than the route received from B, which now has a hop count of 1, so the received route is dropped. However, there is no entry for 10.1.3.0, so that route is entered into the table along with the hop count and router B's interface address. The basic vector algorithm described here is more officially called the Bellman-Ford or Ford-Fulkerson algorithm. 2.1.2. Common Characteristics of Vector ProtocolsThree important characteristics of all vector protocols can be observed from the preceding example:
Each of these characteristics bears examining, because each can be a disadvantage of vector protocols. Each router along a route plays a part in the route calculation. Look at router D's entry for subnet 10.1.1.0 in Figure 2.2. The entry indicates that the subnet is three hops away, via router C (10.1.4.1). This entry is the result of A advertising the prefix with a hop count of 0 at time t0, B advertising the prefix with a hop count of 1 at time t1, and C advertising the prefix with a hop count of 2 at time t2. As a result, the calculation of the route to 10.1.1.0 from router D is a distributed calculationseveral routers play a role in deriving the route. If any router makes a mistake in its calculation, all subsequent routers inherit the mistake. A router cannot update its neighbors about a route until it has performed its own route calculation. Router C could not tell D about prefix 10.1.1.0 until it had first incremented the hop count advertised by B, compared the result with its own routing table, and made the appropriate entry for the shortest route. That shortest route entry is then what is advertised to D. This is significant because the processing at each router takes some finite amount of time. If the processing time at each router is t, then the time for a route to be processed across three routers is 3t, and across six routers 6t. If the route includes many router hops, the convergence timethe time for the last router on the path to correctly enter the route into its routing tablecan be unacceptably long. If a destination is not directly connected, all a router knows about the destination is what a directly connected neighbor tells it. All of us have had the experience of having to ask someone for directions. With vector routing protocols, the neighboring router is the guy giving the directions: "You go this-a-way for eight hops. You can't miss it." (I always cringe when someone says I can't miss it, because it invariably means I will.) You have no other information; you must trust that the neighbor giving the directions, whether to an IP subnet or to an antique store in the country, is giving you accurate information. The neighbor might be mistaken, or might even give you intentionally incorrect information. Two of these characteristicsthat all routers along a route participate in the calculation and that a given router only knows what its upstream neighbor tells itcombine to exacerbate the potential for inaccuracy. As a child, you might have played the game variously known as Gossip or Rumor. The game works best with 10 or more participants. Everyone lines up, and the person at one end of the line whispers some statement into the ear of the next person in line. That person whispers what was heard into the next person's ear, and so on, until the last person in line gets whispered to. That person then says out loud what he or she was told, and the first person says out loud what the original statement was. The end statement is almost always different from the beginning statement, often in very funny ways. "My uncle has three mean hogs" might arrive at the end of the line as "Jeff's uncle is a green tree frog." Slight changes at several hops compound, causing extreme corruption of the original message. Vector protocols are susceptible to the same sorts of incremental corruption of information, although the end result is seldom funny. 2.1.3. Routing LoopsDistance vector protocols are susceptible to routing loops because of the way routing information convergeseach router knows only its directly connected links and what its neighbors tell it. It cannot "see" the entire network topology. This section looks at several tactics used by vector protocols for avoiding routing loops and the limitations of those tactics. 2.1.3.1. Split HorizonBecause vector protocols process updates hop by hop, the updates for a particular destination should always flow downstreamthat is, away from the destination. Updates should not flow upstream toward a destination; partly because it just does not make sense for a route update to go backward along a route, and more important, because doing so can cause incorrect route calculations. Suppose router D in Figure 2.3 advertises subnet 10.1.1.0 toward router C. Router C then thinks it has an alternative route to 10.1.1.0, via router D. Under stable conditions, this is harmless. But suppose the real route to 10.1.1.0 becomes invalid. In that case, router C installs an entry in its routing table to 10.1.1.0 with a distance of four hops and pointing toward router D. A packet with a destination on the 10.1.1.0 subnet is then mistakenly forwarded to router D, which of course forwards the packets right back to router C. A single-hop routing loop has formed, and the packet will continue bouncing back and forth between the two routers until its TTL expires. Presumably there would not be just one packet going to the same destination, but a flow of packets. And when each packet in the flow expires in the loop, the packet is retransmitted. You can easily see that such a loop, aside from gobbling up packets, can cause a possibly serious depletion of link and router resources. Many types of packets in modern networks can have quite high TTL values, making the impact of a routing loop that much worse. Figure 2.3. A potential one-hop routing loop can develop if updates flow upstream. Single-hop loops in the simple, linear network of Figure 2.3 are easily prevented with update rules such as split horizon, which dictates that an update for a destination must not be sent to the neighbor from which the destination was learned. That is, updates must never be sent upstream, only downstream. But what about the network in Figure 2.4? Links have been rearranged so that routers B, C, and D and their links form a physical loop. Physical loops in a network are good because they almost always add redundancy. But loops can also be a challenge for vector protocols. When router A advertises subnet 10.1.1.0, its only neighbor is B, and so the update is clearly sent downstream. B advertises the subnet to its neighbors C and D, which are also downstream. But things become murky at routers C and D. As the figure shows, C and D send updates to each other over their shared link. Are the updates being sent downstream from subnet 10.1.1.0 or upstream toward the subnet? Figure 2.4. Physical loops in a network introduce the possibility of routing loops in distance vector protocols. Perhaps a sufficient, if not satisfactory, answer is that the updates between C and D are being sent "parallel" to subnet 10.1.1.0. The reality is that in most cases the split horizon rule will take care of any ambiguities in this network. Both C and D will have already made an entry into their routing tables indicating 10.1.1.0 as two hops away via router B. When C receives D's update, and D receives C's update, each router will increment the hop count to 3, see that it is a longer distance than the existing route to 10.1.1.0, and drop the update. In Figure 2.5, the link between router B and router C is broken. This is where the redundancy of physical loops pays off. Router C knows from the link's Layer 2 protocol that the link has failed and that therefore the route to 10.1.1.0 via next-hop router B is no longer useable. C can then select the next-best route to 10.1.1.0, via router D. Figure 2.5. Router C can learn an alternate route to 10.1.1.0 when the link between B and C fails. How router C learns of the next-best route depends on the specific vector protocol. RIP and IGRP send periodic unsolicited updates to their neighbors, so C will learn that D has an alternate route at the expiration of D's next update period. If the routers in Figure 2.5 are running BGP, each router stores alternate routes in a table. So C will find the next-best route to 10.1.1.0 via D in its BGP table. If the network is running EIGRP C either has the alternate route in a topology table or will actively query D for a route to 10.1.1.0.[2]
2.1.3.2. Counting to InfinityIn Figure 2.6, the link between router A and router B has failed. This presents a more interesting case than the failure in Figure 2.5 because it introduces the possibility of some vector protocols becoming confused about the network topology. As with the previous case, router B invalidates the route to 10.1.1.0 as soon as it learns from the Layer 2 protocol that the link to A has failed. All modern IP vector protocols update their neighbors as soon as such a change is detected (called a triggered or flash update). So, B sends updates to C and D telling them that the route it previously advertised to 10.1.1.0 is no longer valid. Most of the time, these triggered updates cause a reasonably fast network reconvergence. But given the right circumstances, things can go wrong. Figure 2.6. Router B notifies C and D that 10.1.1.0 is unreachable when the link between A and B fails. Imagine a very small time period in which two things happen (Figure 2.7):
Figure 2.7. When a link is broken in a vector protocol network, routing complications can result because of the timing of updates. Router C has already processed the update from B and knows that 10.1.1.0 is no longer reachable through that neighbor. But then it receives the update from D, claiming it can reach 10.1.1.0 2 hops away. C assumes this information is accurate (remember, a vector protocol only knows what its neighbors tell it), and makes an entry in its routing table indicating that the previously unreachable 10.1.1.0 is now reachable via D, three hops away. The new route at C triggers an update to B, which now thinks 10.1.1.0 is reachable from C, four hops away. B updates D, which records the subnet reachable via B, five hops away. D then sends this information to C. When C receives this new update, the route is compared with the existing route table entry. The existing entry says that 10.1.1.0 is three hops away, whereas the new route shows the same subnet six hops away. However, both the existing route and the new route came from router D. Therefore, C must assume that the new entry describes the same route, and that the distance has increased for some unknown reason. So, C replaces the existing route with the new one. Another consequence of "I only know what my neighbors tell me." C then updates B, which increments its route to seven hops and updates D, which increments its route to eight hops and updates C, and so on. Because this circular pattern of updates could go on, theoretically, until the hop count reaches to infinity, the problem is called counting to infinity. The ill effects of counting to infinity can be limited by defining a finite value at which a route is considered unreachable. RIP, for example, defines an unreachable route as being 16 hops. In our example, the first router to increment the route to 16 hops marks the route as unreachable and then updates its downstream neighbor that the route is unreachable. Such a procedure eventually stops the counting to infinity loop, but it does not prevent the loop. Any packet with a destination address belonging to subnet 10.1.1.0 that arrives at any one of the three routers in Figure 2.7 is routed in a loop until the routers conclude that the route is unreachable. 2.1.3.3. Holddown TimersA solution for preventing the counting to infinity problem is a holddown timer. If a router learns a route from a neighbor and then hears from that same neighbor that the route has become unreachable, a holddown timer is set for the route. Until the timer expires, the router will not accept any new information about that destination unless either
In our example, C would have set a holddown timer on the route to 10.1.1.0, and would not have accepted the update with a higher hop count from D. By the time the timer expired, D would know that 10.1.1.0 is unreachable. The problem with holddown timers is that they come with a price. The holddown period is 180 seconds for RIP, and 280 seconds for IGRP. As a result, holddown timers can drastically increase network convergence time. Suppose the same link failure happened in the network shown in Figure 2.8. Here, router D actually does have an alternate route to 10.1.1.0. Because the alternate route through D has a higher hop count that the broken route through B, however, C will not accept D's route for at least three minutes. 10.1.1.0 is unreachable to any hosts or additional network segments connected through C for the duration of the holddown period. Figure 2.8. Router C will not accept Router D's alternate route to 10.1.1.0 until the holdown timer has expired. 2.1.3.4. EIGRP TacticsEIGRP uses an alternative convergence algorithm known as the diffusing update algorithm (DUAL) that is specifically designed to perform distributed routing calculations while maintaining freedom from loops at every instant. EIGRP does not send periodic updates, which was the core cause of the loop in the previous example. Instead, it maintains a topology table in which routes from neighbors, within certain distance limits, are kept. The best of these feasible routes is selected and added to the routing table. If the router learns that a route has become invalid, it looks in the topology table for an alternate route. Keeping a set of alternative routes at the ready means that EIGRP can often reconverge faster than protocols that must wait for an update. A route advertised by a neighbor is only considered feasible and added to the topology table if the distance from the neighbor to the destination is shorter than the router's own shortest distance to the destination. This selection rule, called the feasibility condition, is key to loop avoidance: If my neighbor's advertised distance to a destination is less than my own shortest distance to the destination, the neighbor's route cannot possibly loop through me. The feasibility condition is applied in Figure 2.9. Router A has chosen the route through B, at a cost of 20 (B's advertised distance of 15 plus the link cost of 5) as its shortest path to destination X. Router A has also selected the route through router C as a feasible route and placed it into the EIGRP topology table, because C's advertised distance of 18 is lower than A's distance of 20. Figure 2.9. With EIGRP, router A selects route B as its shortest path to destination X, and router C as a feasible route to be used as an alternative if the route through B becomes invalid. The absence of an alternative route in the topology table does not necessarily mean that no alternative route exists. Router D in Figure 2.9 also has a valid route to destination X. But because D's distance to X is 25, which is higher than A's distance to X, the route is not considered feasible and is not added to the topology table. But what happens if the route through B fails, and either the alternate route through C also fails or does not exist? If A looks into its topology table and finds no feasible successor to the failed route through B, it sends a query to each of its downstream neighbors asking them for a route to X. The neighbor then looks into its own topology table for a feasible successor. If it finds one, it sends a reply to the querying router with the route information. If it does not find a feasible successor, it in turn queries its own downstream neighbors. If it has no downstream neighbors, it sends a reply saying so. So when a router queries its neighbors for a route to a destination, either it will receive one or more replies with alternative routes or, if there are no alternative routes, the queries will reach the edges of the EIGRP domain where there are no more neighbors to query and replies will come back empty. A querying router waits until it has received a reply from every queried neighbor before choosing a new route or declaring that the destination is unreachable. DUAL makes EIGRP a decided improvement over RIP and IGRP, but it has two possible drawbacks. The first is that EIGRP is a proprietary protocol, so an EIGRP domain is an all-Cisco domain. Whether this is an issue varies from one network operator to another, depending on their preferences. The second drawback is that although EIGRP works well in small to medium networks, it can begin to exhibit scalability problems as a network grows very large. Queries can take a long time to return, causing slow convergence. And in extreme cases, a query might take so long to return that the querying router will decide that the query is lost, and declare the neighbor to whom the query was sent stuck in active (SIA). When that happens, the router clears its adjacency to the neighbor and drops all routes learned from the neighbor, resulting in sometimes serious network stability problems. There are two solutions to an EIGRP network prone to SIAs. The first is to increase the time that a router waits for replies to queries. This works as long as queries are just slow and not actually being lost, but it increases convergence time. The second solution is to break up the network into areas. However, EIGRP has no facility for easily doing this. Instead, multiple EIGRP processes must be used, and careful design and operational procedures are needed to control traffic in such a network.
2.1.3.5. BGP TacticsBGP has a very simple loop-avoidance mechanism. Its basic measure of distance is the autonomous system hop. But rather than measure this distance in autonomous system (AS) hop counts, it associates with each destination prefix a route attribute called AS_PATH. This attribute is a list, sequenced or unsequenced, of the AS numbers of all autonomous systems that a route passes through. To find a shortest path to a given destination, the router selects the route to the destination with the least AS numbers in the AS_PATH.[3] AS numbers are globally unique, so no two numbers for different autonomous systems should be the same. As a router receives a route update from a BGP neighbor, it examines the AS_PATH of each route the update contains. If the router sees its own AS number in a route's AS_PATH, it knows that the route has already passed through its AS once. The route therefore represents a loop, and is dropped.
But BGP is designed for advertising routes between autonomous systems, not for advertising routes within a single AS. In other words, BGP is an external gateway protocol, not an internal gateway protocol (IGP). BGP can run internally within an AS, but this is only to communicate routes from one external-facing router at the edge of the AS to another external-facing router at another edge of the AS. It is not used for discovering routes between two destinations within the same AS.
|
EAN: 2147483647
Pages: 111