Standards & Protocols
First Generation Multicast Routing
By Mike Rodbell
DVMRP was the source of all of the initial multicast backbone, or MBone routing. As
the technology has evolved, it has found its role usurped in many places, but it still remains at the core of all MBone routing.
Continuing in our review of IP multicast technologies, this month let’s take a look at one of the more widely used multicast routing protocols, the distance-vector multicast routing protocol (DVMRP). In reality, the DVMRP is a bit more than just a routing protocol. To provide the necessary support, the protocol consists of two major portions: an information protocol
and a strategy for the actual forwarding of the multicast transmissions. As a routing information protocol, DVMRP is derived from the widely accepted routing information protocol (RIP), with modifications to support distribution of replicated, multicast traffic. There have been two major algorithms used for the delivery mechanisms. The original DVMRP used the truncated reverse-path broadcasting (TRPB) algorithm. More recently, something called the reverse-path multicast (RPM) algorithm was introduced.
DVMRP was the source of all of the initial MBone routing. As the technology has evolved, it has found its role usurped in many places, but it still remains at the core of all MBone routing. It falls into the class of routing algorithms referred to as “dense mode” multicast routing algorithms; however, it has appendages that allow it to operate over WAN architectures. The term “dense mode” means that routes are defined in such a manner that multicast participation is tightly grouped in a
particular area of the network.
The similarities of DVMRP and RIP are mostly found in the way that the two protocols identify routes. Both are based on distance vector mechanisms where each router accumulates and forwards metric distances to destination locations. Probably the main distinction between the two protocols is that while RIP is used to measure and identify routes to destination addresses, DVMRP is primarily concerned with identification of the routes to the source of multicast transmissions. The
identification of this information provides the routers with the ability to determine the forward looking paths that should be used to forward multicast traffic.
While the information protocol is key to the name of the protocol, the traffic forwarding mechanisms are integral to DVMRP-based networks. As multicast traffic is received by routers in the network, it is forwarded through one of two general algorithms, depending on the particular version of the protocol being implemented. The early versions of
DVMRP specified in RFC 1075 employed the TRPB algorithm with more recent versions using the RPM approach.
TRPB: first-generation DVMRP
TRPB techniques were developed to address some of the deficiencies of the crude early approaches to broadcast routing. Early Internet broadcast algorithms employed the reverse path broadcast (RPB) algorithm. With RPB, as each broadcast datagram is received by a router, the router forwards the packet along all interfaces that have a metric to the information
source greater than the incoming interface. While this algorithm (in general) is effective at avoiding routing loops (and the subsequent broadcast storms), it has the unfortunate characteristic of flooding the network with traffic over interfaces — over which there may be no particularly good reason to transmit the information. Additionally, the traffic is routed over a distance limited only by the time-to-live (TTL) field in the original datagram. There were a few tricks incorporated into the RPB
algorithm, although in its basic form, there were network architectures in which packet transmissions could still be duplicated.
TRPB extends the mechanisms offered by RPB by forwarding multicast packets onto only those subnetworks containing hosts that are advertising group memberships through the Internet group management protocol (IGMP). By itself, TRPB eliminates the traffic only on the leaf subnetworks. Routing subnetworks still carry a considerable amount of broadcast traffic, some percentage of which
is either unnecessary or duplicate.
Much of this duplicate and unnecessary traffic can be further limited through additional truncations to the routing tree. Using the routing information provided by the DVMRP information distribution, information can be routed in accordance with the known routes to multicast destinations.
Reverse path multicasting
RPM provides further enhancements to the multicast routing algorithm specified by TRPB. RPM techniques extend the TRPB forwarding mechanisms
to incorporate “pruning” mechanisms, which are used to further constrain the routing tree to include only those routes that lead to group members. With RPM, delivery trees are created that are limited to only those subnetworks containing group members and to the routers and subnetworks that represent the shortest path to those subnetworks containing the group members.
This pruning process is a unique feature of RPM networks. Take, for example, the network shown in
Figure 1
. In this network, there are legitimate routes to multicast group members, and there are routes that serve no useful purpose in the routing of traffic to the members in the diagram. Tracing the packets through the network, the source node first transmits the datagrams to router
R1
. There are two general states in the network. Without knowledge of the complete network multicast routing topology,
R1
will forward the multicast datagram to routers
R2, R4, R3,
and
R7
. As
the messages traverse the network, the participating routers must then make decisions about whether they should continue to forward the datagrams or prune themselves from the routing tree. The routers issue pruning messages as the messages flood through the network. For example, when
R7
exchanges messages with
R3, R3
determines that
R7
is not the shortest path to the route through the network, terminating the path. The resulting interaction between
R3
and
R7
causes
R7
to prune itself from the network. Similarly,
R2
determines that it has no routes to the indicated group (no members along its routing path) by virtue of messages from the leaf router
R6. R2
then informs
R1
of its lack of multicast routes, thereby pruning itself from the network.
Yes, there is an information exchange protocol at the center of DVMRP. As mentioned earlier, the fundamentals of the protocol are very similar to RIP. There are a few differences, though. Routes are
calculated to source nodes rather than destinations. What DVMRP identifies as a destination is actually the combination of the multicast group and the traffic source. The information exchange portion of DVMRP runs on top of the IGMP packet formats where RIP uses the user datagram protocol (UDP). The protocol formats used by DVMRP have some significant advantages over those employed by RIP. Where RIP packet formats are somewhat rigid in format, DVMRP employs a format that permits the grouping of one or more
commands into a single atomic message. As these messages are exchanged between routers, the multicast network topology can be easily modified.
The protocol data format consists of a fixed-length IGMP header used to identify the type of message, followed by a series of command fields. There are four types of messages that can be sent with DVMRP:
•
Response messages
provide routing information to a collection of destinations (multicast groups).
•
Request messages
are used to
request information relating to destinations.
•
Nonmembership reports
(NMR)
are used to poison routes through the advertising router.
•
NMR cancelations
cancel previous nonmembership announcements.
Following this message is a collection of routing information that can be used by the routers to coordinate the various multicast routing trees in accordance with the RPM algorithm. The information transported in each of these messages can include collections of the following
fields:
•
Null
is a placeholder to provide padding along the 32-bit boundaries of the address family indicator (AFI), which identifies the types of addresses being used in the message. For version-4 IP networks, the default family is 2, indicating the use of the standard 32-bit addressing scheme.
•
Subnetwork mask
supports the use of classless addressing when signaling routes back to the multicast destination (traffic source).
•
Metric
is used to indicate the
metric distance to the route destination.
•
Flags
are used for additional control of network routes. Defined flags include an indication that the destination is unreachable and that a split-horizon route is being transferred within the message.
•
Infinity
allows the flexible definition of infinity for the routes being carried by the message. This is different than RIP, which defaults to infinity being equal to 16. While this provides the advantage of supporting larger networks,
care must be taken with large values for infinity. When routing loops are not detected, slow convergence effects can take extremely long periods of time to resolve themselves.
•
Destination address
identifies the destination address(es), being referenced in the route advertisement.
•
Requested destination address
provides a list of addresses that the requester is seeking.
•
NMR
indicates multicast groups not supported by the advertising router. This command includes
the multicast group address(es) along with the hold-down times to be applied to the routing information.
•
NMR cancel
cancels a previous NMR.
As in the case of RIP, DVMRP routers advertise their routing information on a regular basis. As topology changes are detected, the routers issue triggered updates with a small amount of debounce time to permit aggregation of reports and limit the effects of oscillations in the network topology.
Tunneling
As multicast routing represents
a feature improvement in IP-based networks, not all routers can be expected to incorporate a full set of multicast routing protocols. To support the implementation of multicast networks that may be interconnected through nonmulticastable routers, tunneling approaches have been developed. In the tunneling approach, routers can be statically associated with one another, acting as if they are participating over a direct link. Configuration information related to the tunnel includes the definition of the local
end-point, the remote end-point, the tunnel metric, and its associated threshold. Traffic between the routers is forwarded through an algorithm referred to as “weak encapsulation.” In weak encapsulation, source-based routing is used to forward both control traffic, as well as multicast traffic. Control information is sent over the tunnel route as unicast datagrams are directed to the far end-point of the tunnel.
Some shortcomings
Given the significant technical challenges of
distributing efficient multicast information, DVMRP is not without its shortcomings. The flooding required by the routers to manage the routes can aggregate into large amounts of traffic required for information exchanges and for the transmission of packets through the network prior to pruning of the multicast tree. DVMRP is also not very tolerant of route instability. As a member of the distance vector routing family, timers need to be tuned to re-learn routes. Oscillations strongly interfere with that
behavior. However, it’s still important to note that, in the presence of these challenges, DVMRP remains the protocol of choice in the MBone.
DVMRP is the first widely deployed multicast routing protocol in use today. It has been in use for over a decade, providing useful services, and has also served as a foundation for research into multicast routing. Many of its shortcomings are being overcome through advances in multicast routing protocols including link state protocols (OSPF), as well as through the
more recent research into sparse-mode multicast routing protocols for WAN.
Mike Rodbell is director of embedded software development for CIENA Communications Inc. He has developed voice and data communication systems for a wide range of commercial and military systems. He holds a BSCS from Trinity College of Hartford, CT, and an MSEE from Loyola College of Baltimore, MD. He can be reached at mrodbell@ciena.com or http:// www.ciena.com.
Puzzled by a network processing design issue?
