Chapter 5 - Distance Vector Multicast Routing Protocol

Chapter 5: Distance Vector Multicast Routing Protocol

	Overview

	We have seen in the previous two chapters how hosts indicate their desire to join or leave a multicast group using the Internet Group Management Protocol (IGMP) and how switches and routers exchange multicast information using the Cisco Group Management Protocol (CGMP). In this chapter, we begin our investigation of multicast routing protocols, which are designed to efficiently (hopefully!) determine a path from multicast sources to multicast receivers. Before we jump into our first multicast routing protocol, we must first illuminate the general differences between unicast and multicast routing protocols.

Unicast Versus Multicast Routing

	An IP unicast routing protocol (RIP, IGRP, EIGRP, OSPF, and BGP) is used to determine a path from a sender (source) to a single receiver (destination). Each router along the path from the source to the destination must contain a routing table that indicates which interface to use to forward the packet in order to reach the final destination. This route can either be learned by a dynamic IP routing protocol, a static route, or a default route. As the packet is routed through the network, routers inspect the destination IP address to determine the next hop to the final destination and the source address is not used in making the routing decision.

	Of fundamental importance to this discussion is the fact that the destination IP address is a Class A, B, or C unicast address. In Figure 5-1, we have a simple network with a source (172.16.1.1) that is sending to a destination (172.16.5.1). It is a simple matter for each router to determine the path to the destination. Assume that only default and directly connected routes are being used in routers A, B, and C. When the packet from the source arrives at router A, the destination address in the IP packet is examined and checked against the routing table. Router A has four routes, three are directly attached, and one is a default route that says send every packet that is not destined for one of my three directly attached networks out the serial link. Routers B and C have similar routing tables. As the packet travels through the network, each router checks the destination IP address, consults the routing table, and forwards the packet out the proper interface.

	Figure 5-1: Routing of a unicast IP packet from source to destination

Reverse Path Forwarding

	The situation becomes very interesting if the destination address is a multicast or Class D IP address. This is the first general difference between unicast and multicast there may be multiple receivers with the same address, possibly on different networks, as shown in Figure 5-2. Each host that wants to receive multicast traffic for group 225.65.10.154 will use IGMP to inform the local router using a Join message. When the multicast packet reaches router A, the router determines that the packet is multicast because the address is Class D. The IGMP table is consulted and router A sees that at least one host on a directly attached network (172.16.2.0) has joined the group so the packet is forwarded onto that network. If downstream hosts are to receive the multicast traffic, then router A must forward the traffic on the serial interface and so must router B. If there are no downstream receivers, then it does not make sense for router A to forward the traffic to B because this is a waste of valuable bandwidth.

	Figure 5-2: Routing of a multicast packet from source to receivers

	Therefore, a multicast router needs a mechanism to determine on which interfaces to forward multicast traffic. One method is to simply forward the multicast traffic out all interfaces except for the interface on which the traffic was received. What could possibly go wrong? The network in Figure 5-3 illustrates a problem that can occur if multicast traffic is simply forwarded out all interfaces except for the one on which the traffic was received:

	Figure 5-3: Formation of a multicast routing loop

	1.		The sender sends a multicast packet to router A.

	2.		Router A forwards the traffic to routers B and C.

	3.		Routers B and C forward the traffic to router D and to the attached receivers.

	4.		Router D forwards the traffic to the receiver and then back to routers B and C.

	The multicast traffic then circulates in the network until the TTL field in the IP packet goes to zero. Oops! This is probably not a good idea. A technique that is employed with multicast routing protocols to prevent this situation from occurring is called Reverse Path Forwarding (RPF). RPF requires that a unicast routing table exist in each multicast router. When a router receives a multicast packet, the router checks to see if the packet was received on the interface that is on the shortest path back to the source. In other words, the interface that is on the shortest path back to the source is the interface the router would use if forwarding a unicast packet to the source. This is the other major general difference between unicast and multicast routing protocols.

	A multicast routing protocol examines both the source and destination IP addresses when a forwarding decision is being made. The destination address, along with the IGMP table, is used to determine if any hosts require the traffic on a particular interface. The RPF technique is used to see if the multicast packet was received on the interface that would be used to send a unicast packet to the source. If the multicast packet was received on the interface that would be used to forward a packet to the source, then the multicast packet is forwarded out the appropriate interfaces. If the multicast packet was not received on the interface that would be used to send a packet to the source, then the multicast packet is discarded. Figure 5-4 shows the flow of multicast packets when RPF is employed.

	Figure 5-4: Using Reverse Path Forwarding (RPF) to eliminate multicast routing loops

	The router interface that is the RPF back to the source is indicated for each router. Router D has two equal paths back to the multicast source, one through router B and one through router C. We will assume that the interface back to router B is chosen as the RPF interface. Soon we will see how a particular interface is chosen as the RPF interface.

	With RPF, the sequence of events in Figure 5-4 is as follows:

	1.		The multicast source sends a packet to router A.

	2.		Router A determines that the multicast packet was received on the RPF interface; thus, router A forwards the packet out all interfaces except for the one on which the packet was received.

	3.		Routers B and C receive the multicast packet on their RPF interfaces, so the packet is forwarded out all interfaces except for the one on which the packet was received.

	4.		Router D receives the multicast packet on two interfaces but only accepts the packet from the RPF interface. Router D then forwards the packet out the interface to router C and the interface to the attached receiver. However, router C rejects the multicast packet from router D because it did not arrive on the RPF interface.

DVMRP and RIP

The RPF technique to prevent multicast routing loops depends on the available IP routing information contained in the router. As stated earlier, the router can use static routes, default routes, or dynamic routing information to build the routing table. A dynamic routing protocol is almost always preferred and DVMRP is no exception. DVMRP utilizes its own dynamic routing protocol for route exchange and routing table construction. The routing protocol used by DVMRP is based on the Routing Information Protocol (RIP), so we will review RIP to gain an understanding of the mechanisms involved and the problems that can occur with a distance vector routing protocol.

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)

 

DVMRP Operation

	The basic operation of DVMRP consists of four processes. The first process is neighbor discovery, which is used to find other DVMRP-capable and enabled routers attached to a common network. The second process is that of route exchange. Although the DVMRP route exchange process is similar to RIP, there are important differences that will be demonstrated. The purpose of a multicast routing protocol is the efficient delivery of multicast datagrams to destinations that want to receive them. Therefore, DVMRP must interoperate with IGMP to determine if multicast packets need to be forwarded onto a network (receivers are present) or if the packets need to be prevented from reaching a network (no receivers present). DVMRP can dynamically add or delete networks from the list of networks that desire to receive multicast traffic from a particular group. The final two basic DVRMP processes are used to achieve this dynamic nature. Networks are added to the for warding list using Graft messages, while networks are removed from the forwarding list using Prune messages.

	DVMRP messages are sent using the IP packet format (see Figure 5-12) with no options  and with the protocol field set to 2, identifying the packet type as an IGMP message. The type field is set to 19 (0x13) to identify the IGMP packet as a DVMRP message and the code field is used to differentiate between the various DVMRP packets, as shown in Table 5-6.

	Figure 5-12: Encapsulation of a DVMRP packet in an IP datagram

	Table 5-6: DVMRP Packet Type Identifiers

	Packet Type

Code

	Probe

1

	Route Report

2

	Ask-Neighbors2

5

	Neighbors2

6

	Prune

7

	Graft

8

	Graft Ack

9

	DVMRP Neighbor Discovery

	When DVMRP is initially enabled on a router, the DVMRP process determines if the router has any DVMRP neighboring routers. The purpose of neighbor discovery is to locate other DVMRP routers that are directly connected in order to determine the capabilities of neighbor routers and to enable a keep-alive function.

	Neighbor probes are sent on all DVMRP-enabled interfaces every 10 seconds. If a previously discovered neighbor does not respond with its own keep-alive (neighbor probe) message within 35 seconds, then the neighbor is declared down. Routers that have tagged a neighbor as down are required to follow the actions listed in the following steps.

	1.		Any routes that have been learned from the dead neighbor are placed in the hold-down state.

	2.		If traffic was being forwarded to this router (it was a down-stream router), then this dependency should be removed.

	3.		If the dead neighbor was the designated forwarder on a multi-access network, then a new designated forwarder needs to be elected.

	4.		If the dead neighbor was an upstream router, then forwarding entries must be flushed.

	5.		If Grafts from this neighbor need to be acknowledged, then they can be canceled.

	6.		If the neighbor is the last downstream router on the interface and no other receivers are on the network, then the interface should be pruned.

	Neighbors are discovered using IGMP packets with the format shown in Figure 5-13. The type code of 0x13 indicates that this a DVMRP message. Neighbor discovery packets are identified by setting the code field to 1. The checksum field in all DVMRP packets is the standard 16-bit ones compliment of the ones compliment sum of the packet.

	Figure 5-13: DVMRP neighbor discovery packet format

	The Generation ID field is used to determine if a neighbor router has been rebooted. When a router discovers that the generation ID field has changed, the router can assume that the neighbor has been restarted. When this occurs, the router that detected the change in neighbor generation ID flushes any prune information that it has from the neighbor and then sends a unicast copy of the routing table to the neighbor. The network in Figure 5-14 illustrates the neighbor discovery process.

	Figure 5-14: Network used to illustrate the DVMRP neighbor discovery process

	When DVMRP is enabled on the ethernet interface on router A, a DVMRP probe packet is sent out from that interface. Router A has not discovered any DVMRP neighbors at this point, so the neighbor list in the probe packet is empty (see Figure 5-15).

	Figure 5-15: DVMRP neighbor discovery packet format, initial contents

	The neighbor probe interval is 10 seconds. Router A will continue to send neighbor probe packets with an empty neighbor list until DVMRP is enabled on the ethernet interface of router B. Assume DVMRP is enabled on router B, which receives a neighbor probe from router A before it sends its initial probe. Router B will place the IP address of router A into the neighbor list of the probe packet and then transmit the probe having the format of Figure 5-16.

	Figure 5-16: Neighbor probe packet sent by router B.

	When router A receives the probe from router B and detects its IP address, then router A has established a two-way adjacency with router B. When router A sends the next probe, the packet will now contain the IP address of router B, which will form a two-way adjacency with router A. Once the two-way adjacency has been formed, the routers can exchange their routing information.

	The neighbor discovery process also determines if any DVMRP enabled routers are directly attached to any of the router s interfaces. If no neighbors are discovered, then the network is a leaf network, meaning that no other DVMRP routers are on the network that will forward the multicast traffic. On leaf networks, the router only needs to consult the IGMP tables to determine if any receivers for a particular multicast group are on the network. For non-leaf networks, networks on which there is a DVMRP neighbor, other techniques are required to determine if multicast traffic needs to be forwarded (see Figure 5-17).

	Figure 5-17: DVMRP leaf and non-leaf networks

	DVMRP Route Exchange

	DVMRP initially advertises directly connected networks. As other networks are learned through the route advertisement process and routes are added to the local DVMRP routing table, more routes may be advertised.

	Unlike RIP route advertisements, DVMRP routes are sent in an abbreviated format, as shown in Figure 5-18. Route advertisements consist of three components: the netmask, the network, and the metric. The netmask is assumed to be of the form 255.x.x.x because the standard subnet masks for class A, B, and C addresses begins with 255. Because the first octet of every subnet mask is assumed to be 255, then the first octet does not need to be included in the route report. This is why the length of the netmask fields in Figure 5-18 is shown as only three bytes. For example, if the netmask in the route report has a value of 255.255.128, then the full netmask has the value 255.255.255.128.

	Figure 5-18: DVMRP Route Report packet format

	Another method used to reduce the size of the route report is to list one netmask for all networks having the same netmask, instead of listing a netmask for every network. If we are advertising networks 172.16.1.0/24 and 172.16.2.0/24, for example, then we could list the two networks, 172.16.1.0 and 172.16.2.0, and one netmask, 255.255.0 (remember the assumed 255 at the beginning of the netmask). For routing, we only need to know the network address that corresponds to the non-zero values of the netmask. To reduce the packet size further, only the portion of the network that corresponds to a non-zero value of the netmask needs to be reported. With a netmask of 255.255.255.0, we only need to report 172.16.1 and 172.16.2 for the networks mentioned previously. The metric parameter must be listed for each advertised network and the metric values will be explained shortly.

	Looking back at Figure 5-18, it is not clear how to differentiate when one set of netmask-network-metric groups ends and another group begins. The delineation between groups is accomplished by setting the most significant bit of the last metric value for the last network in the group, which is equivalent to adding 128 to the metric.

	Let s look at an example. Assume a DVMRP router has the following routes in the local routing table.

	Network

	Netmask

	Metric

	156.26.1.0

	255.255.255.0

	1

	144.223.0.0

	255.255.0.0

	2

	12.0.0.0

	255.0.0.0

	3

	191.56.3.0

	255.255.255.0

	4

	130.10.10.0

	255.255.0.0

	5

	188.44.0.0

	255.255.0.0

	6

	The first step in determining the DVMRP route report format is to group the networks to be advertised according to their netmask.

	Network

	Netmask

	Metric

	Network Reported

	12.0.0.0

	255.0.0.0

	3 + 128 = 131

	12

	144.223.0.0

	255.255.0.0

	2

	144.223

	130.10.10.0

	255.255.0.0

	5

	130.10

	188.44.0.0

	255.255.0.0

	6 + 128 = 134

	188.44

	156.26.1.0

	255.255.255.0

	1

	156.26.1

	191.56.3.0

	255.255.255.0

	4 + 128 = 132

	191.56.3

	Notice that 128 (the most significant bit set) has been added to the last metric of the last network in each group. With the route information listed above, the route report packet can be built and is shown in Figure 5-19.

	Figure 5-19: Example DVMRP Route Report packet

	One special case is that of the default route. The default route is represented by the mask-network pair 00 00 00/00 . The mask indicates a standard Class C address and normal processing indicates that the mask is 255.0.0.0. This case needs to be interpreted correctly, so the mask for the default route is 0.0.0.0 and not 255.0.0.0.

	The processing of DVMRP route reports is much more complex than RIP route processing. The rules that follow dictate how a DVMRP router will treat the routes received in a route report:

	1.		If the route is received from a neighbor, then accept it. If the route report is received from a router for which a two-way adjacency was not established (not a neighbor), then reject the route report.

	2.		If the metric of a route in the report plus the metric of the receiving router is greater than or equal to infinity (32), then set the metric to infinity (32).

	3.		If the metric of a route in the report is greater than or equal to infinity, then no change to the metric will be made (we will see why).

	4.		If a route is not in the routing table (a new route) and the metric plus the metric of the receiving router is less than infinity (32), then the route is added to the routing table.

	5.		If a route is in the routing table, then another set of rules comes into effect.

	a.		If the metric is between but not equal to 32 (infinity) and 64 (2 x 32), then the sending router is informing the receiving router that it is dependent on the receiving router for multicast traffic from any source on that network. Another way of stating this is that the receiving router is on the shortest path back to any source on that network. Figure 5-20 illustrates this situation.

	Figure 5-20: DVMRP poison-reverse used to indicate route dependency

			In Figure 5-20, we assume that routers A and B have completed the neighbor discovery process and that they have formed a two-way adjacency. As part of its route report, router B says that it can reach network 172.16.2.0/24 with a metric of one (directly attached). In some cases, metrics can be assigned to an interface, but typically the metric is set to one, indicating that the network is one hop away. Router A installs this route in its routing table because this is a new route.

			Router A also determines that traffic from any multicast source on network 172.16.2.0/24 has to pass through router B to get to router A. In this situation, router A will poison-reverse the route by adding infinity (32) to the metric and reporting the route back to router B. Router A has a metric of 2 for network 172.16.2.0/24  and the poison-reverse value is 34 (2 + 32). When router B receives this metric (34), then it knows that router A depends on it for multicast traffic from network 172.16.2.0/24. This information is important when pruning occurs.

			The function of poison-reverse can easily be seen in the network of Figure 5-21. Router A advertises to routers B and C that it can reach the source in one hop. Routers B and C add one to the metric and advertise the metric as two. Router D then adds one to the metric and advertises the distance as three. Router E receives two advertisements for the source with metrics of two and three, chooses the smallest metric as the RPF interface, and poison-reverses the route. So when router E transmits its routing table to C, the metric is 35, indicating that router E is dependent on router C for traffic from the source.

	Figure 5-21: DVMRP poison-reverse example

	b.		If the metric plus the metric of the receiving router is greater than the metric of the route already in the routing table, then check the address of the sending router. If the address of the sending router is different than the address of the sending router for the route in the table, ignore the route. If the address of the sending router is the same as the address of the sending router for the route in the table, then replace the metric in the table for that route.

	c.		If the metric plus the metric of the receiving router is less than the metric of the route in the table, then replace the route in the table. If the address of the sending router is different than the address of the sending router in the table, then poison-reverse the route.

	d.		If the metric plus the metric of the receiving router is equal to the metric in the routing table and the address of the sender matches the address of the sender in the routing table, then refresh the route. If the address of the sender is not the same as the address of the sender in the routing table and the new sender s IP address is lower, use this neighbor as the upstream router.

	e.		If the metric of the received route is greater than or equal to 2 x 32 (64), then ignore the route.

	Figure 5-22 illustrates rule 5b:

	Figure 5-22: Illustration of rule 5b

	1.		Router B sends a route report to router C advertising network 172.16.1.0/24.

	2.		This is a new route for router C, so the route is installed in the routing table and the poison-reverse route is sent back to router B.

	3.		Router A sends a route report containing the network 172.16.1.0/24 with the same metric being advertised by router B.

	4.		Router C now selects router A as the upstream router for multicast traffic from network 172.16.1.0/24 because router A has a lower IP address than router B and sends a poison-reverse to router A for this network. An updated poison-reverse is also sent to router B (without the addition of infinity) to inform router B that router C is no longer dependent on router B for multicast traffic from network 172.16.1.0/24.

	In the case of a multi-access network such as ethernet, only one router needs to forward multicast traffic onto the network. For the network in Figure 5-23, each router is a designated forwarder for a particular multicast source. The designated forwarder for each multicast source is the router that has the smallest metric back to the source. If two or more routers attached to a multi-access network have the same metric back to the source, then the router with the lowest IP address is elected designated forwarder.

	Figure 5-23: DVMRP-designated router example

	For network 172.16.1.0 in Figure 5-23, there are three multicast sources for which a designated forwarder needs to be elected. For source 1, the choices are router A or router B. Both have an identical metric back to source 1, so the IP address of the routers is used to break the tie. In this case, router A becomes the designated forwarder because it has a lower IP address. For source 2, router B is the designated forwarder because it is the only router attached to network 172.16.1.0/24 that has a path back to source 2. The same argument applies for router C and source 3. In this scenario, we have three designated forwarders on the multi-access network, one for each source.

	Source-Based Multicast Trees

	The routing table that is constructed using DVMRP route exchange produces multicast delivery trees that are source-based. The term source-based simply means that forwarding paths are based on the shortest path back to the source (remember RPF?). Therefore, for every multicast source, there is a corresponding multicast tree that connects the sender to all receivers through the RPF interface. For example, the network in Figures 5-24a and 5-24b contains two multicast sources. It is not important which multicast address the sources are sending packets to, only the location of the sources when constructing the delivery tree.

	Figure 5-24a: Source-based multicast delivery tree for source 1

	Figure 5-24b: Source-based multicast delivery tree for source 2

	DVMRP Pruning and Grafting

	Membership in a multicast group is dynamic and receivers can join or leave a multicast group using IGMP. Forwarding multicast traffic onto networks that have no receivers or downstream routers is an inefficient use of network resources, so DVMRP uses prunes and grafts to dynamically alter the structure of the source-based trees. To illustrate the situations when pruning and grafting comes into effect, we will examine some simple network scenarios where these mechanisms come into play. In Figure 5-25, we have a network with one multicast source and one multicast receiver.

	Figure 5-25: DVMRP network used to illustrate pruning and grafting

	Router A and B have no leaf networks, a network with only multicast receivers and no forwarding routers. The receiver on router C has signaled, using IGMP, that it desires to receive traffic from the multicast group (which has as its source the host attached to router A).

	How do routers A and B know to forward traffic to router C so the host may receive it? Initially, DVMRP assumes that all networks have receivers and so it floods the multicast traffic received on the RPF interface on all networks. Routers A and B know that they are upstream routers in relation to router C due to the fact that router C has used poison-reverse for the network containing the source.

	Assume now that the receiver no longer wishes to receive multicast traffic from the source. The host then sends an IGMP Leave message for the group, and router C queries the network and discovers that no hosts want to receive multicast traffic. At this point, there is no reason for any of the routers to forward multicast traffic from the source because there are no longer any receivers. Router C sends a Prune message to router B, and because no other networks require the forwarding of multicast traffic by router B, router B sends a Prune message to router A. Router A now has no downstream routers requiring multicast traffic, so router A prunes its serial interface.

	Prunes are also necessary when hosts need to receive multicast traffic on an attached network. The network of Figure 5-26 contains a multi-access ethernet segment. From our earlier discussion, we know that either router C or D will become the designated forwarded for the ethernet network, based on the metric back to the source, or in the case of a tie, the IP address. Whichever router is not elected as designated forwarder must prune its serial interface from the source tree, so only one router will forward the multicast traffic to the receiver.

	Figure 5-26: Pruning interfaces on a multi-access network

	The actions that a router must take when a Prune message is received are as follows:

	1.		If the Prune is received from a router that the receiving router has not formed a two-way adjacency with, then discard the message.

	2.		Examine the Prune message and determine if the message is the proper format.

	3.		If the Prune message does not apply to source information active on the router, then discard the message.

	4.		If the neighbor that sent the prune is not a dependent neighbor for the network to be pruned, then discard the message.

	5.		If there is an active Prune from this neighbor for the indicated source network and group, then reset the timer to the value received in the Prune message.

	6.		If there is not an active Prune from this neighbor for the indicated source network and group, then set a time-out using the value in the Prune message.

	7.		If all dependent downstream routers on this network have been sent Prunes, then determine if any group members are on the network. If there are no group members, then send a Prune message to the upstream router.

	The actions a router must take when sending a prune are as follows:

	1.		If the upstream router cannot receive Prunes, then do not send a Prune. This can be determined from the neighbor s DVMRP version and capabilities.

	2.		If any Graft messages need to be acknowledged, cancel them.

	The Prune packet format is shown in Figure 5-27.

	Figure 5-27: DVMRP Prune packet format

	The Prune lifetime is the amount of time the Prune is in effect. DVMRP is a broadcast and Prune protocol, so when the Prune expires, the multicast traffic will again be forwarded until another Prune is received.

	Grafting is the opposite of pruning. When a pruned network needs to again receive multicast traffic from a particular source for a multicast group, then the network needs to be added, or grafted, back onto the multicast source based tree. Graft messages are sent upstream until they reach the source tree for the particular multicast source and are acknowledged at each hop. Graft messages are sent under the following conditions:

	1.		If a host joins a multicast group (using IGMP) on a network that has been pruned for that group.

	2.		A DVMRP router is enabled on a pruned network and is dependent on the upstream router.

	3.		A router on a pruned network restarts (signaled by the generation ID).

	4.		If a Graft acknowledgment is not received for a previous Graft message.

	The format of the Graft and Graft acknowledgment packets are shown in Figures 5-28 and 5-29. The values of the various DVMRP timers are listed in Table 5-7.

	Figure 5-28: DVMRP Graft packet format

	Figure 5-29: DVMRP Graft acknowledgment packet format

	Table 5-7: DVMRP Timers and Values

	Timer

Value in Seconds

	Probe Interval

10

	Neighbor Timeout Interval

35

	Minimum Flash Update Interval

5

	Router Report Interval

60

	Route Expiration Time

140

	Route Hold-Down

120

	Prune Lifetime

Variable (less than two hours)

	Prune Retransmission Time

3 with exponential back-off

	Graft Retransmission Time

5 with exponential back-off

	Tracing and Troubleshooting

	DVMRP contains a mechanism for determining the characteristics of a particular router. The first part of this mechanism is to send a unicast request to a DVMRP router requesting this information. The packet is called an Ask-Neighbors2 and it has the format shown in Figure 5-30. The response to an Ask-Neighbors2 packet is the Neighbors2 response packet, whose format is shown in Figure 5-31.

	Figure 5-30: DVMRP Ask-Neighbors2 packet

	Figure 5-31: DVMRP Neighbors2 packet format

	The capabilities field lists the characteristics of the router, and the possible values are listed in Table 5-8 and the flags values in Table 5-9. The Neighbors2 packet contains a section for each interface on the router from which the information was requested. For each router interface, the Neighbors2 packet contains the metric of the interface, the interface flags, the number of neighbors on the network connected to the interface, and the neighbors addresses.

	Table 5-8: DVMRP Router Capabilities

	Bit

Flag

Description

	0

Leaf

This is a leaf router

	1

Prune

Router understands pruning

	2

GenID

Router sends generation IDs

	3

Mtrace

Router handles Mtrace requests

	4

SNMP

Router supports the DVMRP MIB

	Table 5-9: DVMRP Interface Flags

	Bit

Flag

Description

	0

Tunnel

Neighbor reached via a tunnel

	1

Source Route

Tunnel uses IP source routing

	2

Reserved

No longer used

	3

Reserved

No longer used

	4

Down

Operational status down

	5

Disabled

Administrative status down

	6

Querier

Querier for the interface

	7

Leaf

No downstream neighbors on this interface

	DVMRP Tunnels and the Internet Multicast Backbone

	Tunnels are used to transport one protocol within another. For example, in Figure 5-32, we have a network that is running IP and IPX applications, but only IP is enabled between routers A and B. For the IPX traffic from router A to get to the client attached to router B, the IPX datagram is sent through an IP tunnel connecting the two routers.

	Figure 5-32: Tunneling IPX in IP

	Assume that the Netware server in Figure 5-32 is sending an IPX packet to the Netware client. The data from the server is encapsulated in an IPX packet at layer 3 and sent to the ethernet module at layer 2. The ethernet module then encapsulates the IPX packet in an ethernet frame with destination and source ethernet addresses. The IPX packet is treated as data inside the ethernet frame. When router A receives the frame, the data is removed and router A determines that this is an IPX packet destined for the IPX network attached to router B. Because IP is the only protocol enabled between the routers, a tunnel needs to be configured to carry the IPX packet in an IP packet. Assuming the tunnel has been configured, router A encapsulates the IPX packet in an IP packet. Notice that we are encapsulating one layer 3 protocol, IPX, in another layer 3 protocol, IP. This is typically the characteristic of tunneling. When the IP packet reaches the other end of the tunnel, router B removes the IPX packet from the IP packet and forwards the IPX packet onto the network on which the Netware client is attached.

	The Internet Multicast Backbone (MBONE) is a logical multicast network overlaid onto the physical unicast Internet (see Figure 5-33).

	Figure 5-33: The Internet and the MBONE

	Multicast traffic that travels between DVMRP sections of the Internet needs to be sent over an IP tunnel that encapsulates the multicast packet into a unicast packet (see Figure 5-34).

	Figure 5-34: A DVMRP tunnel

	The two DVMRP routers and the tunnel form the logical or virtual multicast network that is a subset of the physical Internet. Tunnels are needed because not all routers on the Internet support multicast routing. Even if they did, the maximum hop count for DVMRP is 32, which is not sufficient to span the entire Internet. DVMRP tunnels are IP in IP tunnels, as shown in Figure 5-35.

	Figure 5-35: Multicast traffic encapsulated in an IP in IP tunnel

	Cisco routers do not implement DVMRP but can interact with DVMRP, as we shall see in later chapters. CGMP can act as a proxy for a non-Cisco DVMRP router using the interface command

	ip cgmp proxy

	Consider the network in Figure 5-36. Here we have a non-Cisco DVMRP router connected to a Cisco switch that has CGMP enabled, and with CGMP enabled on the interface connected to the switch. With CGMP proxy enabled on the router, the router listens to the DVMRP messages and determines the groups for which DVMRP will be forwarding traffic. The proxy router then informs the switch using CGMP about any DVMRP hosts attached to the switch that wish to receive the traffic.

	Figure 5-36: Cisco router acting as a proxy for the DVMRP router and host.

	DVMRP Router Commands

	Cisco does not support a full DVMRP implementation but does support a number of commands that affect DVRMP information that is being injected into the network. The DVMRP commands available are listed below with an explanation of their use. These commands are used when integrating PIM and DVMRP networks and are covered in more detail in Chapter 8, PIM-DVMRP Networks.

	ip dvmrp unicast routing

Type: interface

	This command allows Cisco routers to exchange DVMRP routing information. Routes received in a DVMRP report message are cached by the router in a DVMRP routing table. If PIM is running, then these routes will be preferred over routes in the unicast table.

	ip dvmrp route-hog notification <route-count>

default--route-count = 10,000

Type: global

	The route-hog notification command is used to send notification by way of a syslog message when the number of DVMRP routes has exceeded the route-count limit. There may be a misconfigured router on the MBONE, which is advertising a large number of routes.

	ip dvmrp route-limit <route-count>

default--route-count = 7000

Type: global

	The route-limit command limits the number of DVMRP routes advertised on a DVMRP-enabled interface. The interface could be a DVMRP tunnel, an interface with a DVMRP neighbor, or an interface configured with ip dvmrp unicast-routing. This command prevents injecting more routes than the route-count parameter into the MBONE.

	ip dvmrp distance <administrative-distance>

Type: interface

	This command sets the administrative distance for DVMRP routes to the value specified.

	ip dvmrp metric <metric> [list <access-list>]

{[<protocol> <process-id>] | dvmrp]}

Type: interface

	If PIM is configured on an interface and there are DVMRP neighbors, the router send DVMRP report messages. This command is used to set the metrics for unicast routes that are reported to the DVMRP neighbor. If an access-list is used, either standard or extended, then only those destinations permitted by the access-list will have the specified metric applied to the routes. The <protocol> <process-id> pair is used to limit the application of the metric to routes learned by the specified protocol. The DVMRP parameter is used to apply the metric only to routes from the DVMRP routing table. The command can be used multiple times on an interface.

	ip dvmrp accept-filter <access-list> [neighbor-list <nbr-acl>] [<distance>]

Type: interface

	This is used to filter incoming DVMRP reports. If the destination matches the <access-list> from neighbors in the <nbr-ac1>, then the routes are stored in the DVMRP routing table with <distance>.

	ip dvmrp default-information originate | only

Type: interface

	The default network 0.0.0.0 will be advertised to DVMRP neighbors on the interface with a default metric of 1. It only has effect if the neighbor is an mrouted 3.4 system. If the keyword only is used, then no other DVMRP routes will be reported. The keyword originate allows more specific routes to be advertised.

	ip dvmrp metric-offset [in | out] <increment>

default: in

increment default: in 1 out 0

Type: interface

	The value of increment is added to either incoming or outgoing DVMRP route reports.

	ip dvmrp reject-non-pruners

Type: interface

	If a DVMRP neighbor does not support pruning and grafting, then a neighbor relationship will not be established.

	ip dvmrp summary-address <address> <mask> metric <value>

Type: interface

	This configures a summary address to be advertised out of the interface.

	ip dvmrp auto-summary

Type: interface

	This enables DVMRP auto-summarization.

	ip dvmrp output-report-delay <delay-time> [<burst>]

default: delay = 100 milliseconds burst = 2

Type: interface

	This configures the interpacket delay between DVMRP reports in milliseconds. A set number of packets given by the burst parameter will be transmitted with a delay given by the delay-time parameter.

	tunnel mode dvmrp

Type: interface (tunnel)

	This is used on a tunnel interface connecting a Cisco router to an mrouted machine. Usually it is used to connect to the MBONE.

	References

	RFC 1058, Routing Information Protocol, C. Hedrick, Rutgers University, 1988

	RFC 2453, RIP Version 2, G. Malkin, Bay Networks, 1998

	RFC 1075, Distance Vector Multicast Routing Protocol, D. Waitzman, C. Partridge, S. Deering, 1988

	IETF Internet Draft, Distance Vector Multicast Routing Protocol, T. Pusateri, 1998, draft-ietf-idmr-dvmrp-v3-07.txt