Source-based multicast protocols can be further divided into broadcast-and-prune protocols versus those protocols that broadcast their group membership information (these latter broadcasts are sometimes called domainwide reports). In a broadcast-and-prune protocol, the source-based tree is initially built to encompass all network segments, regardless of group membership. The first multicast datagram will be sent along this initial tree. A router at a leaf of this tree may receive the datagram and realize that it has no group members on its attached segments. If so, the router indicates that it does not need to receive these datagrams anymore, by sending Prune messages to its upstream neighbor. This neighbor may in turn send a Prune to its upstream neighbor, and so on, until the tree has been rolled back to reach only group members.

Figure 14.1 shows an example from our sample multicast network. A multicast datagram with source S1 and destination G1 is initially forwarded to two segments without group members: 128.4.1/24 and 128.4.2/24. This causes R8 and R9 to send Prunes to R7, R7 to R4, and so on, until the tree on the lower left of Figure 9.3 is attained.

Figure 14.1. Operation of a broadcast-and-prune protocol.

Prune information is eventually deleted, to make the routing robust in the face of unexpected failures (implementation bugs and so on). This deletion causes the pruning process to periodically begin anew. If a new group member appears on a segment not currently on the tree, Graft messages are forwarded toward the source to extend the tree to the new group member. Graft messages need to be reliable, and so they are retransmitted until acknowledged. In Figure 14.1, if a host on 128.4.1/24 were to join G1, grafts would be sent from R8 to R7, R7 to R4, and so on, until the branch R1-R2-R4-R7-R8 is grafted onto the tree.

MOSPF, on the other hand, is an example of a protocol that broadcasts its group membership information throughout the routing domain. This allows MOSPF to restrict the initial tree to group members only, avoiding the broadcast-and-prune procedure entirely.

One other useful concept when discussing these protocols is data-driven versus control-driven actions. Data-driven actions occur in a router during the process of forwarding a multicast datagram. Examples include MOSPF routers building multicast cache entries, DVMRP routers sending Prunes, and PIM routers sending Assert messages. Control-driven actions occur because of the reception of routing protocol or IGMP messages, or external events, such as link failures. Examples of control-driven actions include the sending of Grafts in DVMRP, the broadcast of group information in MOSPF, and the creation of a branch of the shared tree in CBT.

The original design of the Distance Vector Multicast Routing Protocol (DVMRP) was documented in [255]. By the time that DVMRP was first implemented, by the UNIX mrouted program, the protocol had changed considerably. The mrouted code served as the DVMRP specification for several years, until the code was reverse engineered and an up-to-date DVMRP written specification was produced [202]. Even today, mrouted changes more quickly than the DVMRP specification can keep up. Almost all of the MBONE consists of multicast routers running DVMRP.

DVMRP is a broadcast-and-prune protocol that employs Distance Vector technology to advertise multicast sources. DVMRP uses IGMP’s encapsulation. All DVMRP packets are encoded as IGMP Type 0x13, with the second byte of the IGMP header indicating the DVMRP packet type. There are separate DVMRP packet types for neighbor discovery (DVMRP Probes), distribution of multicast source information (DVMRP Route Reports), tree maintenance (DVMRP Prunes, Grafts, and Graft Acks), and for monitoring DVMRP routers (DVMRP Ask Neighbors 2 and Neighbors 2).

Each DVMRP router periodically broadcasts to its neighbors a list of sources and the distance from these sources to the router. In this way, a DVMRP router can calculate the previous hop on each multicast source’s path, just as RIP calculates the next hop to the destinations it advertises: The previous hop on a source’s tree is the DVMRP router that is advertising the shortest distance from the source. This calculation has all the convergence problems normally associated with a Distance Vector protocol (see Section 13.1), although DVMRP attempts to improve convergence by employing the techniques of split horizon with poison reverse and hold down.

In order to start the prune process, each router in a broadcast-and-prune protocol needs to know whether it is the leaf of a particular source’s broadcast tree. In DVMRP, this is accomplished via reception of Route Reports. For example, in Figure 14.1, router R7 knows that it is not a leaf for source S1, because both routers R8 and R9 indicate that they are downstream by setting the cost of S1 to infinity in Route Reports sent back to R7 (in DVMRP, R8 and R9 are said to be subordinate to R7). R7 then knows that it cannot send prunes upstream until prunes have first been received from both R8 and R9.

Route Reports are also used to get rid of equal-cost paths to group members. At the top of Figure 9.3, routers R10 and R11 would both be sending DVMRP Route Reports onto segment 192.7.1/24, advertising source S2 with the same cost. On receiving each other’s Route Reports, the two routers would agree that the router having the smaller IP address (assumed to be R10 in this case) is responsible for forwarding multicasts from S2 onto the segment.

The Multicast Extensions to OSPF (MOSPF) [171] is a source-based multicast routing protocol. MOSPF, described in detail in Chapter 10, allows introduction of a multicast routing capability to an OSPF routing domain. MOSPF has seen considerable deployment in private internets, and limited deployment at the edges of the MBONE. MOSPF routers can interoperate with regular, nonmulticast OSPF routers, and MOSPF capability can be introduced piecemeal into an OSPF routing domain.

MOSPF introduces no new OSPF packet formats but does add a new LSA, the group-membership-LSA, and flags MOSPF-capable routers by setting an appropriate bit in their router-LSAs. Group membership is broadcast throughout the entire MOSPF routing domain by flooding group-membership-LSAs.

Creation of MOSPF multicast routing entries is data driven. The first time a MOSPF router sees a datagram with a given source and destination group, the router performs a Dijkstra SPF calculation rooted at the datagram source. Non-MOSPF routers are avoided by this calculation, and since the location of group members is known in advance, the resulting tree extends only to active group members. In MOSPF, tiebreakers are introduced to the Dijkstra calculation so that all MOSPF routers produce exactly the same tree.

When the state of the network changes—for example, a link goes inoperational, group membership changes, and so on—updated LSAs are flooded, describing the new network state. When a MOSPF router receives one of these updated LSAs, the router deletes all multicast routing table entries that might possibly change, knowing that they will be recreated by the next matching data packet.

Since MOSPF routers have a global view of the routing domain, supplied by the link-state database, the routers can perform a special forwarding optimization. By examining a multicast datagram’s TTL, a MOSPF router can tell when a multicast datagram has no chance of reaching the nearest group member. In these cases, rather than waste network bandwidth by forwarding the datagram, a MOSPF router simply discards the datagram instead. This is advantageous when hosts are performing expanding ring searches (Section 10.1.1).

In order to deploy MOSPF in the MBONE, the interactions between MOSPF and DVMRP have been defined (Section 10.6). MOSPF has a hierarchical multicast capability, used between areas and when multicasting datagrams to members outside of the AS. When so doing, MOSPF has incomplete group membership information and so requires certain routers at the area borders/AS boundary to receive all multicast datagrams, regardless of destination. Unfortunately this means that some datagrams get forwarded into areas of the routing domain that have no group members, wasting network bandwidth in the process.

Protocol Independent Multicast, Dense Mode (PIM Dense) [60] can be thought of as DVMRP without the routing updates. PIM Dense is a source-based, broadcast-and-prune protocol that uses unicast routing to build reverse-path forwarding trees. The “dense” refers to the PIM designers’ belief that PIM Dense mechanisms are more appropriate when group members are densely populated throughout the routing domain. When group members are few and scattered, PIM Sparse (Section 14.5) is thought to be a better protocol.

Both PIMs run directly over IP, using IP protocol 103. In PIM Dense, there are message types to detect neighboring PIM routers (PIM Hellos) and to perform maintenance of source-based trees (PIM Join/Prunes, Grafts, and Graft Acks).

PIM Dense must supply mechanisms for two functions that are implemented by DVMRP Route Reports: leaf detection and removal of equal-cost paths. For leaf detection, a PIM router can tell whether any other PIM routers are on a network segment by whether it is receiving PIM Hellos. The PIM router then assumes that all neighbors are downstream for any given source; if a neighbor is not downstream for a given source, it will simply send a PIM Prune message.

Removal of equal-cost paths is data driven. Again using the example at the top of Figure 9.3, if this network is running PIM Dense, the first datagram sent from S2 to Gl will be multicast twice onto segment 192.7.1/24, once by R10 and once by R11. On receiving these data packets from segment 192.7.1/24, which is different than the correct incoming interface for source S2, R10 and R11 both multicast PIM Assert messages onto 192.7.1/24. Asserts contain metrics; on receiving each other’s Assert, the two routers will agree that only the router advertising the smaller metric will continue forwarding multicasts from S2 onto the segment.

Cisco has implemented both PIMs (Sparse and Dense), together with a gateway function to DVMRP, allowing deployment of PIM in some places at the edge of the MBONE.

Protocol Independent Multicast, Sparse Mode (PIM Sparse) [70] is one of two shared-tree multicast routing protocols developed by the IETF’s IDMR Working Group. PIM’s unique feature is that the forwarding of multicasts matching a particular source and destination group can be shifted off the group’s shared tree onto a source-based tree, presumably when the traffic levels warrant the more efficient paths produced by a source-based scheme (Section 9.3.1). PIM Sparse shares packet formats with PIM Dense, running directly over IP, using IP protocol 103. PIM Sparse contains message types to detect neighboring PIM routers (PIM Hellos), maintain the shared tree (PIM Join/Prunes and Asserts), switch from shared trees to source-based trees (PIM Register and Register-Stop messages), and select Rendezvous Points, or RPs (PIM Bootstrap and Candidate-RP-Advertisement messages).

PIM Sparse elects a Designated Router for each network segment. When one of the network segment’s hosts joins a group G1, the Designated Router sends Join messages toward G1’s RP to add a new branch to the shared tree. The state of the shared tree is periodically confirmed by resending Joins toward the RP.

Branches of the shared tree are torn down when hosts leave a group. In this case, Prune messages are forwarded toward the RP. Branches are also torn down when unicast routing indicates that the best path toward the RP has changed. A new branch will then be grafted at the next Join refresh.

Core Based Trees (CBT) [16] is the other shared-tree multicast routing protocol developed by the IETF’s IDMR Working Group. CBT, which has not yet been deployed in the Internet, runs directly over IP, using IP protocol 7. Separate message types are used to elect a Designated Router on LANs (CBT Hellos) and to perform maintenance of the shared tree (CBT JOIN_REQUEST, JOIN_ACK, QUIT_NOTIFICATION, ECHO_REQUEST, ECHO_REPLY, and FLUSH_TREE messages).

When a host joins a multicast group, the host’s Designated Router forwards JOIN_REQUESTs to the group’s core, adding a branch to the group’s shared tree. Construction of the branch is confirmed by forwarding JOIN_ACKs in the reverse direction.

The state of the shared tree is periodically verified by sending ECHO_REQUESTs and ECHO_REPLYs between neighboring CBT routers on the shared tree. If a CBT router’s upstream neighbor (the CBT router one hop nearer the core) is determined to be inoperational, the downstream branches of the tree are removed, using the FLUSH_TREE messages, and then these branches are reconstructed from the leaves, using the JOIN_REQUEST mechanism. When the host leaves a group, the host’s branch is removed by sending QUIT_NOTIFICATIONs toward the core.

The interaction among multicast routing protocols is not nearly as well developed as that among unicast routing protocols. Multicast routing interactions are more difficult than unicast interactions. Multicast protocols must agree on a single, strict tree for each multicast datagram, and not all multicast protocols even agree on the number of trees that should be constructed—the source-based protocols construct a tree for each source and destination group combination, whereas the shared-tree protocols construct a single tree for each group.

However, progress has been made in connecting specific multicast protocols (Section 10.6), and routers have been developed that attach MOSPF and PIM domains to the MBONE’s DVMRP. Proposals have also started coming out of the IDMR Working Group for the way that interactions among various multicast routing protocols should be structured [15], [244], [245].