Add Book to My BookshelfPurchase This Book Online

Chapter 5 - Distance Vector Multicast Routing Protocol

Cisco Multicast Routing & Switching
William R. Parkhurst
  Copyright © 1999 The McGraw-Hill Companies

Routing Information Protocol (RIP)
RIP Version 1 is specified in RFC 1058 and belongs to the class of routing protocols called Interior Gateway Protocols (IGP). An IGP is used for routing within a single autonomous system. An autonomous system (AS) is one in which the routing policies are under a common authority and utilize a common routing scheme. An Exterior Gateway Protocol (EGP) is used to route between autonomous systems (see Figure 5-5).
Figure 5-5: Interior and Exterior Gateway Routing Protocols
RIP is a distance-vector routing protocol, which only uses a hop count when making a routing decision. A hop count is the number of routers that a packet has to traverse in order to reach its destination. If two unequal speed or bandwidth routes to the same destination exist but with the same hop count, then RIP considers both routes to be the same distance (see Figure 5-6), which is an obvious limitation of the protocol.
Figure 5-6: All equal-hop paths are considered equal by RIP.
RIP follows a simple algorithm for constructing a routing table. When a router is initially booted, the only networks it is aware of are those that are directly connected. A RIP routing table contains the destination network, the hop count or metric to the destination network, and the interface a packet should be sent through to reach the destination network. Routers A and B in Figure 5-7 would have initial routing tables as shown in Tables 5-1 and 5-2.
Table 5-1: Initial Routing Table for Router A
Destination Network
Hop Count
Interface
1
1
1
2
1
2
6
1
3
Table 5-2: Initial Routing Table for Router B
Destination Network
Hop Count
Interface
2
1
1
3
1
2
Routers C through F would have similar routing tables. Every 30 seconds RIP broadcasts the entire routing table on every RIP-configured interface using the format in Figure 5-8. One RIP message can contain up to 25 networks. If a routing table contains more than 25 entries, multiple RIP messages will have to be transmitted.
The command field in the RIP message can be used to request all or part of a routing table (command = 1), or signify a response to a request (command =2). Other values are specified in RFC 1058, but they are now considered obsolete. Usually a router sets the command field to one and then broadcasts the entire routing table.
When a router receives a RIP message, a simple algorithm is used to determine if the route(s) should be added to the routing table:
  1. If a route in the update is not in the routing table, then add the route to the table and increase the metric by one.
  2. If the route in the update is in the routing table, add it to the local table only if the metric is less than the metric for the current route and the update was received on a different interface. If the update was received on the same interface as the one in the routing table, then accept the route and the metric.
When router B transmits the first RIP message, router A only installs the route to network 3 with a hop count of 2, but does not install the route to network 2 because the route already exists with a metric equal to router B’s metric. The routing table for router A contains four routes, as shown in Table 5-3.
Table 5-3: Initial Routing Table for Router A
Destination Network
Hop Count
Interface
1
1
1
2
1
2
6
1
3
3
2
2
Router A now knows that if it has a packet destined for network 3 it can send it to router B through interface 2. After a period of time, all the routers in the network of Table 5-3 will contain entries in their routing tables for every network. The complete routing table for router A is contained in Table 5-4.
Table 5-4: Final Routing Table for Router A
Destination Network
Hop Count
Interface
1
1
1
2
1
2
3
2
2
4
3
2
5
4
2
6
1
3
7
2
3
8
3
3
Notice in Figure 5-7 that router A can reach network 5 through interface 3 with a hop count of four or through interface 2 with a hop count of four. Which route will router A place in the routing table? The answer depends on whether it receives the RIP message from router E first or from router B. Both routers B and E will advertise a route to network 5 with a hop count of three. According to the RIP algorithm, router A will install the route from the first RIP message received and ignore the route from the second.
Figure 5-7: Sample RIP network
In Figure 5-8, the metric is shown to have a range of values between one and 16. A hop count of 16 signifies that the corresponding network is unreachable. Such a value is considered to be infinity by RIP, which is another limitation of the protocol. Networks that are more than 15 hops away cannot be reached. Many corporate networks have hundreds of routers and their size makes RIP unusable as a routing protocol.
Figure 5-8: RIP Message format
RIP is also a slowly converging protocol. Convergence is a measure of how long it takes to propagate a route through the network when there is a change. Assuming we boot all the routers in Figure 5-7 simultaneously, it will take 60 seconds (if all routers immediately send their initial RIP message) for the route to network 5 to reach router A. If router D loses the connection to network 5, it will advertise a hop count of 16 (infinity) to network 5. Router A will not know that the network is unreachable for 60 seconds (a very long time) and will continue to send packets to network 5 until it learns the network is unreachable. Actually, all the routers do not send their initial routing tables at the same time. The 30-second timer for RIP updates is offset by a random amount to prevent the routers from transmitting simultaneously.
Two additional timers are also associated with RIP updates, the timeout timer and the garbage-collection timer. When a new route is installed in the routing table, the timeout timer is initialized to zero and begins to count. Every time a RIP message containing the route is received, the timeout timer is reset to zero. If a RIP message containing the route is not received for 180 seconds, the metric for the route is set to 16 and a garbage-collection timer for the route is started. If 120 seconds pass without receiving the route in a RIP message, the route is removed from the routing table. If a message is received containing the route before the garbage-collection timer reaches 120, the timer is cleared and the route is installed in the routing table.
Count to Infinity Problem
In Figure 5-9, router A has lost connectivity to network 1. Router A adjusts the metric in the routing table for network 1 to 16. Assume router B transmits its routing table before router A.
The message from router B contains a route to network 1 with a hop count of two. This is better than the route currently in router A’s routing table, so the route is installed. Router A now advertises that it can reach network 1 with a hop count of three. Because router B receives this information on the same interface as the route currently in the table, it installs the route with a hop count of four. Router B now advertises to router A a hop count of four for network 1 and router A installs it with a hop count of five and so on ad infinitum (or at least to 16).
Figure 5-9: Rip Count to Infinity Problem.
While the routers are counting to 16, we have a routing loop. Packets that A has to send to network 1 are sent to router B and router B sends them to router A and so on. The routing loop will be broken when the routers finally count to 16, but with 30-second updates this could take some time. Meanwhile, the network is being flooded with packets essentially making the network unusable.
Split Horizon  Split horizon is a technique used to solve the counting to infinity problem. With split horizon, a router does not advertise a route over the interface from which it learned the route. This prevents router B from advertising the route to network 1 back to router A. Within 30 seconds, router A would advertise a hop count of 16 to network 1, alerting the network that the network is unreachable.
Split Horizon with Poison-Reverse  This technique allows a router to send updates about routes over the interface that they were learned from, but the hop count is set to 16. For our example, router B would advertise a route to network 1 with a hop count of 16, preventing routing A from placing it in the routing table. DVMRP uses a modified version of poison-reverse for determining downstream dependencies.
Hold Down  Hold down causes a router to ignore routing updates about a route for a period of time after the route has been declared unreachable. For our example, router A determines that network 1 is unreachable. With hold down, router A will ignore advertisements about network 1 from routers B and E during the hold down period, which will allow router A to transmit its routing table, informing the network that network 1 is unreachable.
Triggered Updates  Although split horizon solves the routing loop problem between two routers, a situation could occur when three or more routers form a routing loop. Split horizon cannot prevent this from happening. Triggered updates require a router to immediately transmit the routing table when a change occurs, which speeds up the convergence of the network but has the potential for creating broadcast storms. Another situation could arise where a router receives a triggered update and then a regular update from another router reinstalling the route. In short, this is not a technique that solves all the convergence problems of RIP, although the ones mentioned do add a measure of stability to a RIP network.
RIP and VLSM
Simply stated, don’t use VLSM with RIP. You can do it, but it won’t work and it can cause a lot of head scratching if you don’t realize what is happening.
If you look back at the RIP message format in Figure 5-8, you will notice that a very important piece of information is missing, the subnet mask! When RIP is constructing the routing message for an interface, RIP only includes those networks that have the same subnet mask as the interface on which the message is to be transmitted. In Figure 5-10, we have a router with four interfaces. Two of the interfaces use a /20 subnet mask and two of the interfaces use a /24 subnet mask.
Figure 5-10: RIP and VLSM
Downstream routers on interfaces 1 and 2 would never learn about networks 1.0 and 2.0, and routers downstream of interfaces 3 and 4 would never learn about networks 16 and 32. If all the subnet masks are equal, then there is not a problem. Without transmitting the sub net mask, RIP cannot take advantage of the properties of VLSM, yet another limitation.
RIP Version 2
RFC 1723, 1994, contains extensions to RIP version 1. Most notable is the RIP message format (see Figure 5-11). The shaded entries are the additions that have been made in version 2. The route tag can be used to indicate routes that have been learned from other RIP routers or from another IGP, such as OSPF, or from an EGP, such as BGP. The subnet mask is probably the most important addition allowing designers to use VLSM with RIP V2.
Figure 5-11: RIP Version 2 Message format
Unfortunately, RIP V2 still suffers from the other limitations of RIP V1 as summarized in Table 5-5.
Table 5-5: RIP Limitations
Slow Convergence
Routing to Infinity
Can’t handle VLSM (V1)
Unable to detect routing loops
Only metric is hop count
Small network diameter (15 hops)
If multiple routes to a destination exist, will only use one (no load balancing)

 


 
Books24x7.com, Inc © 2000 –  Feedback