Survey of Different Multicast Routing Protocols

M. Capan

Croatian Academic and Research Network - CARNet,
Research and Developemnet Laboratory
J. Marohnica bb, Zagreb, Croatia
tel. + 385 1 6165 616, fax. + 385 1 6165 615

(CARNet na MIPRO'98)

Abstract - Today's networks are designed to reliably transmit traffic such as data from point to point i.e. unicasting, or from point to multipoint i.e. broadcasting. Multimedia places further demands on the network. First of all, multimedia traffic, such as audio or video, cannot tolerate delays in delivery like those tolerable by plain data transfer applications. Multimedia requires that data packets arrive on time and in the proper order at the client side. Real-time protocols and quality of service guarantees addresses this issue. Furthermore, multimedia requires transmitting large amount of traffic over the network and thus uses far more of the network’s bandwidth than in case of those basic network operations. Multicasting offers far more efficient way of transmitting such traffic over the Internet than unicasting or broadcasting ever would. The subject of this paper addresses the issue of efficient routing of such multicast traffic.

I. INTRODUCTION

The majority of IP traffic on today’s networks is unicast, i.e. a separate IP packet is sent from a source to a destination participating in a connection. Networks also support broadcasting. When a packet is broadcast, the same packet is sent to all clients on the network. In case when the same packet needs to be sent only to some of the clients on the network, both of these methods unnecessary waste network bandwidth. Unicast is wasting bandwidth by sending multiple copies of the same packet through the same portion of the network from the source to the destination. Broadcast is wasting bandwidth by sending the data to the whole network no matter if there is a client that wants to receive it. Because each client must process the broadcast IP packet no matter the broadcast is of its interest or not, broadcast slows the performance of client machines needlessly.

Multicasting in some way takes the advantages of both these approaches and tries to avoid their disadvantages. General idea behind multicast is to send single copy of an IP packet to all of those of clients that requested it, and not to send multiple copies of a packet over the same portion of the network, nor to send packets to clients who don’t want it. Basic idea in multicasting IP packets is to construct a tree structure data delivery path through the network. This tree is rooted at the source of the multicast traffic and its leaves are subnetworks containing receivers of that traffic. The multicast source sends a single copy of an IP packet through the branches of the tree. The intermediate routers are responsible for multiplication of received IP packets and for forwarding them down the correct branches to other routers and to receivers’ subnetworks. Furthermore, routers have to prune off branches where client decided not to receive multicast traffic any more and graft branches back to the tree when a client in a new subnetwork wishes to join the receiver group.

This way multicasting allows that deployment of multimedia applications on the network doesn’t cause immediate network congestion by forcing network to do packet replication only when necessary.

II. MULTICAST FUNDAMENTALS

For each IP packet relay method there is corresponding fundamental type of IP address: unicast, broadcast, and multicast. The key difference between a multicast IP packet and a unicast IP packet is the presence of a “group address” in the Destination Address field of the IP header of multicast IP packet. Instead of Class A, B, or C of IP addresses, multicasting employs Class D destination addresses which are all those IP addresses that begin with following binary sequence 1110, which in Internet standard dotted decimal notation are IP addresses ranging from 224.0.0.0 to 239.255.255.255.

A multicast address is designed to enable a delivery of IP multicast packets to a set of clients that have been configured as members of a multicast group in various scattered subnetworks. Individual clients are free to join or leave multicast group at any time. A client may be a member of more than one multicast group at any given time and does not have to belong to a group to send message to members of a group.

Multicast enabled router employs a group membership protocol, such as Internet Group Management Protocol (IGMP) [2], to learn about the presence of group members on their directly attached subnetworks. When a client wishes to join a multicast group, it transmits a group membership protocol message to its router for the group or groups that it wishes to join, and sets its IP process and network interface card to receive IP packets addressed to the multicast group.

IGMP provides the final step in a multicast packet delivery service since it is only concerned with the managing multicast traffic between the local router and group members on its directly attached subnetworks. In order to enable multicast service on an internetwork multicast routers between themselves use a multicast routing protocol. A multicast routing protocol is responsible for the construction of multicast packet delivery trees and for performing efficient multicast packet forwarding. There is a number of different forwarding algorithms employed by the multicast routing protocols, such as:

• flooding,
• spanning trees,
• Reverse Path Broadcasting (TPB),
• Truncated Reverse Path Broadcasting (TRPB),
• Reverse Path Multicasting (RPM) and
• Core-Based Trees.

Most prevalent multicast routing protocols in Internet today, which implement some of the previously mentioned forwarding algorithms, are:

• Distance Vector Multicast Routing Protocol (DVMRP),
• Multicast Open Shortest Path First (MOSPF) and
• Protocol-Independent Multicast (PIM).

III. MULTICAST FORWARDING ALGORITHMS

Flooding

This selfexplaining technique uses plain flooding a lgorithm for forwarding incoming multicast IP packets to all routers on an internetwork. The flooding procedure begins when a router receives a packet that is addressed to a multicast group. The router checks if this is the first time that it has seen this particular packet or whether it had seen the packet before. If it is the first reception of the packet, the packet is forwarded on all interfaces except the one on which it arrived. If the router has seen the packet before, it is simply discarded. A flooding algorithm is very simple to implement since a router does not have to maintain a routing table. It only needs to keep track of the recently seen packets, but apparently flooding algorithm can’t scale widely over the Internet since it generates a large number of duplicate packets and uses all available paths across the internetwork as show in Fig. 1.

Spanning tree

A more effective solution than flooding would be to appropriately select a subset of the Internet topology that forms a spanning tree and use it for forwarding of multicast packets. The spanning tree defines a tree-structured subnetwork of the Internet where only one active path connects any two routers. Once the spanning tree has been built, a multicast router simply forwards each multicast packet to all interfaces that are part of the spanning tree except the one on which the packet arrived from. When compared to simple forwarding, spanning tree algorithm insures loopless multicast packet path to all routers in the internetwork, but drawbacks of this algorithm are traffic concentration on relatively small number of available links and failing to provide most efficient path between the source subnetwork and group members.

Reverse Path Broadcasting

It is obvious that building one spanning tree across the Internet as forwarding path for all multicast traffic independent of its source and receivers is not the way to efficiently and evenly utilize the network. A more efficient approach would be to build a group-specific spanning tree for each potential source of the multicast traffic. Since there are many potential sources, a different spanning tree is constructed for each active (source-destination group) pair and therefore traffic load is evenly shared across the network. The algorithm used for constructing these source-rooted trees is referred to as Reverse Path Broadcasting (RPB). For each source-group pair, if a packet arrives on a link that the local router considers being the shortest path back to the source of the packet, then the router forwards the packet on all interfaces except the incoming interface. Otherwise, the packet is discarded. The interface over which the router expects to receive multicast packets from a particular source is referred to as the “parent” link. The outbound links over which the router forwards the multicast packet are called the “child” links. This basic RPB algorithm could be even more enhanced to prevent unnecessary packet duplication if the router making forwarding decision could determine whether a neighbouring router on a potential child link considers the local router to be on the shortest path back to the source. If so, packet is forwarded to the neighbour, otherwise is not and packet duplication is prevented. The information needed to make this decision can be derived from a link-state routing protocol since each local router maintains a routing domain topology database, which is regularly updated. By these update-messages downstream router can inform upstream router if it considers it to be on shortest path back to the source. Considering simple case of network topology as illustrated in Fig. 2, building the spanning tree using RPB algorithm would create the same spanning tree as show by that figure.

The key benefit of reverse path broadcasting is that it is reasonably efficient and easy to implement. It does not require the router’s knowledge about the entire spanning tree nor it does not require a special mechanism to stop the forwarding process, as flooding does. In addition, it guarantees efficient delivery since multicast packets always follow the “shortest” path from the source station to the destination group. Finally, the packets are distributed over multiple links, resulting in better network utilization since a different tree is computed for each (source, group) pair.

One of the major limitations of the RPB algorithm is that it does not take into account multicast group membership when building the distribution tree for a (source, group) pair. As a result, multicast packets may be unnecessarily forwarded to subnetworks that have no members in the destination group.

Truncated Reverse Path Broadcasting (TRPB)

Truncated Reverse Path Broadcasting (TRPB) was developed to overcome previously mentioned limitation of Reverse Path Broadcasting. With the help of IGMP, multicast routers determine the group memberships on each leaf subnetwork and then avoid forwarding multicast packet with specific multicast destination group address onto a leaf subnetwork if it does not have at least one member of the destination group present. The spanning delivery tree is “truncated” by the router if a leaf subnetwork does not have group members.

TRPB overcomes some limitations of RPB, but it solves only part of the problem. It eliminates unnecessary IP multicast traffic towards leaf subnetworks, but it still forwards multicast traffic onto any intermediate routers on the branches of the distribution tree toward leaf subnetwork with no group members.

Reverse Path Multicasting (RPM)

Reverse Path Multicasting (RPM) is an enhancement of Reverse Path Broadcasting and Truncated Reverse Path Broadcasting because RPM creates a delivery tree that only spans to:

• subnetworks with group members
• routers and subnetworks along the shortest path to subnetworks with group members

RPM allows the source-rooted spanning tree to be pruned so multicast packets are only forwarded along branches leading to members of the destination group (Fig. 3). When a multicast router receives a packet for a (source, group) pair, the first packet is forwarded following the TRPB algorithm to all routers in the internetwork. The TRPB algorithm guarantees that each router on a leaf subnetwork receives the first multicast packet. If there is a group member on one of its subnetworks, a router forwards the packet based on its IGMP information. If none of the subnetworks connected to the router have group members, the router may transmit prune message to the upstream router informing it that it should not forward packets for the particular (source, group) pair downstream anymore.

Prune messages are sent only one hop back toward the source. An upstream router receiving a prune message is required to record the prune information in memory. If the upstream router has no local recipient or receives prune messages on each of the child interfaces that it used to forward the first packet, the upstream router does not need to receive additional packets for the (source, group) pair. This means that the upstream router can generate a prune message of its own, one hop back toward the source. This succession of prune messages creates a multicast forwarding tree that contains only alive branches i.e., branches that lead to active group members. Since both, the group membership and network topology, are dynamically changing, the pruned state of the multicast forwarding tree is regularly refreshed.

Periodically, the prune information is removed from the memory of all routers and the next packet for the (source, group) pair is forwarded to all leaf routers. This results in a new burst of prune messages, allowing the multicast-forwarding tree to adapt to the ever-changing multicast delivery requirements of the internetwork.

Despite the improvements offered by the RPM algorithm, there are still several limitation considering scaling issues. In developing an Internet-wide delivery service the first RPM limitation is that multicast packets must be periodically forwarded to every router in the internetwork and the second is that each router in the tree is required to maintain state information for all groups and each source. The significance of these limitations is amplified as the number of sources and groups in the multicast internetwork expands.

Core-Based Trees (CBT)

The latest algorithm [5], contrary to previously mentioned which built a source-rooted, shortest-path tree for each source-group pair, constructs a single delivery tree that is shared by all members of a group. The CBT algorithm is quite similar to the spanning tree algorithm except it allows a different core-based tree for each group. Multicast traffic for each group is sent and received over the same delivery tree, regardless of the source. A core-based tree may involve a single router or set of routers, which acts as the core of a multicast delivery tree.

A CBT (Fig. 4) shared distribution tree has a core router that is used to construct the tree. Routers join the tree by sending a Join message to the core. When the core receives a Join request, it returns an acknowledgment over the reverse path, thus forming a branch of the tree. Each station that wishes to receive multicast traffic addressed to a multicast group is required to send a join message toward the nearest core branch of the core tree for the particular multicast group. In that way join messages don’t need to travel all the way to the core before being acknowledged. If a Join message hits a router on the tree before it reaches the core, that on-tree router terminates the join and acknowledges it. After that, the router that sent the Join is then connected to the shared tree.

Similar to other multicast forwarding algorithms, CBT does not require that the source of a multicast packet be a member of the destination group. Packets sourced by a non-group member are simply unicasted toward the core until they reach the first router that is a member of the group’s delivery tree. When the unicast packet reaches a member of the delivery tree, the packet is multicast to all outgoing interfaces that are part of the tree except the incoming link. This guarantees that the multicast packet is forwarded to all routers in the delivery tree.

In terms of scalability, CBT offers several advantages over the Reverse Path Multicasting (RPM) algorithm. CBT makes efficient use of router resources since it only requires a router to maintain state information for each group, not for each (source, group) pair. Also, CBT conserves network bandwidth since it does not require periodical multicast packet forwarding to all multicast routers in the internetwork.

Despite these benefits, there are still several limitations to the CBT approach. CBT aggregates traffic onto a smaller subset of links than would be used for source-based trees. The resulting concentration of traffic around the core is a potential problem for this approach to multicast routing. In addition, a single shared delivery tree may create suboptimal routes resulting in increased delay—a critical issue for some multimedia. Some versions of CBT support the use more than one core thus achieving load balancing.

IV. MULTICAST ROUTING PROTOCOLS

Distance Vector Multicast Routing Protocol (DVMRP)

DVMRP is a distance-vector routing protocol designed to support forwarding of multicast packets through an internetwork. DVMRP is widely used in the Internet Multicast Backbone (MBone) [11], multicast enabled set is of subnetworks and routers that support the delivery of IP multicast traffic to over 30 countries all over the world.

DVMRP constructs source-rooted multicast delivery trees using variants of the Reverse Path Broadcasting (RPB) algorithm. DVMRP was first defined in RFC-1075 [1]. The original specification was derived from the Routing Information Protocol (RIP) and employed the Truncated Reverse Path Broadcasting (TRPB) algorithm. The major difference between RIP and DVMRP is that RIP is concerned with calculating the next hop to a destination, while DVMRP is concerned with computing the previous hop back to a source. The latest version of software multicast routing - mrouted 3.9, has extended DVMRP to employ the Reverse Path Multicasting (RPM) algorithm. This means that the latest implementations of DVMRP are quite different from the original RFC specification in many ways.

The ports of a DVMRP router may be either a physical interface to a directly attached subnetwork or a virtual interface to another multicast island. These virtual interfaces are used for tunneling multicast traffic across parts of an internetwork that don’t support multicast. Tunneling refers to the process of encapsulation of multicast IP packets in unicast IP packets, which then can be routed by conventional routers. The encapsulation is added on entry into a tunnel and stripped off on exit from the tunnel.

All interfaces are configured with a metric that specifies the cost for the given port and a Time-To-Live (TTL) threshold that limits the scope of a multicast transmission. In addition, each tunnel interface must be explicitly configured with two additional parameters - the IP address of the local router’s interface and the IP address of the remote router’s interface.

TABLE 1. TTL Scope control values

A multicast router will only forward multicast packets across an interface if the TTL field in the IP header is greater than the TTL threshold assigned to the interface. Table 1 lists the conventional TTL values used to restrict the scope of an IP multicast.

Operation and Future Development

DVMRP implements the Reverse Path Multicasting (RPM) algorithm. According to RPM, the first packet for any source-group pair is forwarded across the entire internetwork, providing the packet’s TTL and router interface thresholds permit it. The initial multicast packet is delivered to all leaf routers, which transmit prune messages back toward the source if there are no group members on their directly attached leaf subnetworks. The prune messages result in the removal of branches from the tree that do not lead to group members, thus creating a source-specific shortest path tree with all leaves having group members. Periodically, this initial procedure is repeated to allow the pruned branches grow back if needed. Furthermore, DVMRP implements mechanisms to quickly “graft” back a previously pruned branch of a group’s delivery tree. If a router that previously sent a prune message for a (source, group) pair discovers new group members on a leaf network, it sends a graft message to the group’s previous-hop router. When an upstream router receives a graft message, it cancels out the previously received prune message. Graft messages may cascade back toward the source allowing previously pruned branches to be restored as part of the multicast delivery tree.

When there is more than one DVMRP router on a subnetwork, the Dominant Router has to be elected among them to be responsible for the periodic transmission of IGMP Host Membership Query messages. Upon initialization, a DVMRP router considers itself to be the Dominant Router for the subnetwork until it receives a Host Membership Query message from a neighbor router with a lower IP address. In such case the router with lower IP address is always elected as the new Dominant Router.

Since the DVMRP was developed to route only multicast and not unicast traffic, a router may be required to run multiple routing processes - one for the delivery of unicast traffic and another for the delivery of multicast traffic. The DVMRP process periodically exchanges routing table update messages with multicast-capable neighbors.

DVMRP relies on the receipt of “poison reverse” updates for leaf router detection. This technique requires that a downstream neighbor advertise “infinity” for a source subnetwork to the previous hop router on its shortest-path back to that source subnetwork. If an upstream router does not receive a “poison reverse” update for the source subnetwork on a downstream interface, the upstream router assumes that the downstream subnetwork is a leaf and removes the downstream port from its list of forwarding ports.

The rapid growth of the MBone is beginning to place increasing demands on its routers. The current version of the DVMRP treats the MBone as a single, “flat” routing domain where each router is required to maintain detailed routing information to every subnetwork on the MBone. As the number of subnetworks continues to increase, the size of the routing tables and of the periodic update messages will continue to grow.

To overcome these potential threats, a hierarchical version of the DVMRP is under development. In hierarchical routing, the MBone is divided into a number of individual routing domains. Each routing domain executes its own instance of a multicast routing protocol and another protocol is used for routing between the individual domains. Hierarchical routing reduces the demand for router resources because each router only needs to know the explicit details about routing packets to destinations within its own domain, but knows nothing about the detailed topological structure of any of the other domains. The protocol running between the individual domains maintains information about the interconnection of the domains, but not about the internal topology of each domain.

In addition to reducing the amount of routing information, there are several other benefits gained from the development of a hierarchical version of the DVMRP:

• Different multicast routing protocols may be deployed in each region of the MBone. This permits the testing and deployment of new protocols on a domain-by-domain basis.
• The effects of individual link or router failures are limited to only those routers operating within a single domain. Likewise, the effect of any change to the topological interconnection of regions is limited to only inter-domain routers. These enhancements are especially important when deploying a distance-vector routing protocol that can result in relatively long convergence times.
• The count-to-infinity problem associated with distance-vector routing protocol places limitations on the maximum diameter of the MBone topology. Hierarchical routing limits that diameter constraint to a single domain, not to the entire MBone.

Hierarchical DVMRP [6] allows the creation of non-intersecting regions, each identified by unique Region-Id, where a region can implement any multicast routing protocols such as DVMRP, MOSPF or PIM as so called “Level 1” protocol. Each region is required to have at least one “boundary router” that is responsible for providing inter-regional connectivity. The boundary routers execute a “Level 2” protocol to forward traffic between regions. When a multicast packet originates within a region, it is forwarded according to the “Level 1” protocol to all subnetworks containing group members. In addition, the packet is forwarded to each of the boundary routers for that source region. The “Level 2” routers tag the packet with the Region-Id and place it in an encapsulation header for delivery to other regions. When the packet arrives at a remote region, the encapsulation header is removed before delivery to group members by the “Level 1” routers.

Multicast Open Shortest Path First (MOSPF)

The Multicast extensions to OSPF (MOSPF) are defined in RFC-1584 [4].Version 2 of the Open Shortest Path First (OSPF) routing protocol is defined in RFC-1583 [3]. It is an Interior Gateway Protocol (IGP) specifically designed to distribute unicast topology information among routers belonging to a single Autonomous System. OSPF is based on link-state algorithms that permit rapid route calculation with a minimum of routing protocol traffic. In addition to efficient route calculation, OSPF is an open standard that supports hierarchical routing, load balancing, and the import of external routing information.

MOSPF routers maintain a current image of the network topology through the unicast OSPF link-state information exchange. MOSPF enhances the OSPF protocol by providing the ability to route multicast IP traffic. The enhancements that have been added are backward compatible so that routers running MOSPF will interoperate with non-multicast OSPF routers when forwarding unicast IP data traffic.

MOSPF, unlike DVMRP, does not provide support for tunnels.

The OSPF link state database provides a complete description of the Autonomous System's topology. By adding a new type of link state advertisement (LSA), the group-membership LSA, the location of all multicast group members is precisely located in the database. The path of a multicast packet can then be calculated by building a shortest-path tree rooted at the packet’s source. All branches not containing multicast members are pruned from the tree. The shortest path tree for each source-group pair is built “on demand” using Dijkstra’s algorithm when a router receives the first multicast packet for a particular source-group pair. The results of the shortest path calculation are then cached for use by subsequent packets having the same source and destination.

Properties of the basic MOSPF routing algorithm can be summarized as:

• For a given multicast packet, all routers within an OSPF area calculate the same source-rooted shortest path delivery tree. Tiebreakers have been defined to guarantee that if several equal-cost paths exist, all routers agree on a single path through the area. MOSPF does not support the concept of equal-cost multipath routing like unicast OSPF does.
• Synchronized link state databases containing Group-Membership LSAs allow an MOSPF router to effectively perform the Reverse Path Multicasting (RPM) computation “in memory”. Unlike DVMRP, this means that the first multicast packet of a group transmission does not have to be forwarded to all routers in the area.
• The “on demand” construction of the shortest-path delivery tree has the benefit of spreading calculations over time, resulting in a lesser impact for participating routers.

Each MOSPF router makes its forwarding decision based on the contents of its forwarding cache. The forwarding cache is built from the source-rooted shortest-path tree for each (source, group) pair and the router’s local group database. After the router discovers its position in the shortest path tree, a forwarding cache entry is created containing the (source, group) pair, the upstream node, and the downstream interfaces. At this point, the Dijkstra shortest path tree processing is discarded, releasing all resources associated with the creation of the tree. From this point on, the forwarding cache entry is used to forward all subsequent multicast packet for the (source, group) pair.

The information in the forwarding cache is not aged or periodically refreshed. It is maintained as long as there are system resources (i.e. memory) available or until the next topology change. In general, the contents of the forwarding cache will change when:

• The topology of the OSPF internetwork changes, forcing all of the packets shortest-path trees to be recalculated.
• There is a change in the Group-Membership LSAs indicating that the distribution of individual group members has changed.

Benefits and Shortcomings of MOSPF

MOSPF routers can be combined with non-multicast OSPF routers. This permits the gradual deployment of MOSPF and allows experimentation with multicast routing on a limited scale. When MOSPF and non-multicast OSPF routers are mixed within an Autonomous System, all routers will interoperate in the forwarding of unicast packets.

The MOSPF router is required to eliminate all non-multicast OSPF routers when it builds its source-rooted shortest-path delivery tree. An MOSPF router can easily determine the multicast capability of any other router based on the setting of the multicast bit (MC-bit) in the Options field of each router’s link state advertisements. The omission of non-multicast routers can create a number of potential problems when forwarding multicast traffic:

• Multicast packets may be forwarded along suboptimal routes since the shortest path between two points may require traversal of a non-multicast OSPF router
• Even though there is unicast connectivity to a destination, there may not be multicast connectivity. For example, the network may partition with respect to multicast connectivity since the only path between two points requires traversal of a non-multicast OSPF router.
• The forwarding of multicast and unicast packets between two points may follow entirely different paths through the internetwork. This might make some routing problems a bit more difficult to debug.

Protocol-Independent Multicast (PIM)

The Protocol-Independent Multicast (PIM) routing protocol is the youngest of all multicast routing protocols and still under development by the Inter-Domain Multicast Routing (IDMR) working group of the IETF. PIM receives its name because it is not dependent on the mechanisms provided by any particular unicast routing protocol. However, any implementation supporting PIM requires the presence of a unicast routing protocol for providing routing table information and to adapt to topology changes.

PIM makes a clear distinction between a multicast routing protocol that is designed for dense environments and one that is designed for sparse environments. Dense-mode refers to a protocol that is designed to operate in an environment where group members are relatively densely packed and bandwidth is plentiful. Sparse-mode refers to a protocol that is optimized for environments where group members are distributed across many regions of the Internet and bandwidth is not necessarily widely available. It is important to note that sparse-mode does not imply that the group has few members, just that they are widely dispersed across the Internet.

The argument for making this distinction and therefore two different protocols is that when group members and senders are sparsely distributed across a wide area, both DVMRP and MOSPF as dense-mode protocols do not provide the most efficient multicast delivery service. DVMRP periodically sends multicast packets over many links that do not lead to group members, while MOSPF can send group membership information over links that do not lead to senders or receivers.

PIM Dense Mode (PIM-DM)

While the PIM architecture was driven by the need to provide scalable sparse-mode delivery trees, it also defines a new dense-mode protocol instead of relying on existing dense-mode protocols such as DVMRP and MOSPF. It is envisioned that PIM-DM [7] will be deployed in resource-rich environments, such as a campus LAN where group membership is relatively dense and bandwidth is likely to be readily available. PIM Dense Mode (PIM-DM) is similar to DVMRP in that it employs the Reverse Path Multicasting (RPM) algorithm. However, there are several important differences between PIM-DM and DVMRP or MOSPF:

• PIM-DM relies on the presence of an existing unicast routing protocol to adapt to topology changes, but it is independent of the mechanisms of the specific unicast routing protocol. In contrast, DVMRP contains an integrated routing protocol that makes use of its own RIP-like exchanges to compute the required unicast routing information. MOSPF uses the information contained in the OSPF link-state database, but MOSPF is specific to only the OSPF unicast routing protocol.
• Unlike DVMRP, which calculates a set of child interfaces for each (source, group) pair, PIM-DM simply forwards multicast traffic on all downstream interfaces until explicit prune messages are received. PIM-DM is willing to accept packet duplication to eliminate routing protocol dependencies and to avoid the overhead involved in building the parent/child database.

For those cases where group members suddenly appear on a pruned branch of the distribution tree, PIM-DM, like DVMRP, employs graft messages to add the previously pruned branch to the delivery tree. Finally, PIM-DM control message processing and data packet forwarding are integrated with PIM-Sparse Mode operation so that a single router can run different modes for different groups.

PIM Sparse Mode (PIM-SM)

PIM Sparse Mode (PIM-SM) [8] is being developed to provide a multicast routing protocol that provides efficient communication between members of sparsely distributed groups that are most common in wide-area internetworks. Its designers believe that a situation in which several hosts wish to participate in a multicast conference do not justify flooding the entire internetwork with periodic multicast traffic. They fear that existing multicast routing protocols will experience scaling problems if several thousand small conferences are in progress, creating large amounts of aggregate traffic that would potentially saturate most wide-area Internet connections. To eliminate these potential scaling issues, PIM-SM is designed to limit multicast traffic so that only those routers interested in receiving traffic for a particular group “see” it. PIM-SM differs from existing dense-mode multicast algorithms in two essential ways:

• Routers with directly attached or downstream members are required to join a sparse-mode distribution tree by transmitting explicit join messages. If a router does not become part of the predefined distribution tree, it will not receive multicast traffic addressed to the group. In contrast, dense-mode multicast routing protocols assume downstream group membership and continue to forward multicast traffic on downstream links until explicit prune messages are received. The default forwarding action of the other dense-mode multicast routing protocols is to forward traffic, while the default action of a sparse-mode multicast routing protocol is to block traffic unless it is explicitly requested.
• PIM-SM is similar to the Core-Based Tree (CBT) approach in that it employs the concept of a rendezvous point (RP). Equivalently to core router in case of CBT, RP are points where receivers “meet” sources. The initiator of each multicast group selects a primary RP and a small ordered set of alternative RPs, known as the RP-list. For each multicast group, there is only a single active RP. Each receiver wishing to join a multicast group contacts its directly attached router, which in turn joins the multicast distribution tree by sending an explicit join message to the group’s primary RP. A source uses the RP to announce its presence and to find a path to members that have joined the group. This model requires sparse-mode routers to maintain some state (i.e., the RP-list) prior to the arrival of data packets. In contrast, dense-mode multicast routing protocols are data driven, since they do not define any state for a multicast group until the first data packet arrives.

When there is more than one PIM router connected to a multi-access LAN, the router with the highest IP address is selected to function as the Designated Router (DR) for the LAN. The DR is responsible for the transmission of IGMP Host Query messages, for sending Join/Prune messages toward the RP, and for maintaining the status of the active RP for local senders to multicast groups.

To facilitate the differentiation between DM and SM groups, a part of the Class D multicast address space is reserved to be used by SM groups. When the DR receives an IGMP Report message for a new group, the DR determines if the group is RP-based by examining the group address. If the address indicates a SM group, the DR performs a lookup in the associated group’s RP-list to determine the primary RP for the group. After performing the lookup, the DR creates a multicast forwarding cache for the (*, group) pair and transmits a unicast PIM-Join message to the primary RP. The (*, group) notation indicates an (any source, group) pair. The intermediate routers forward the unicast PIM-Join message and create a forwarding cache entry for the (*, group) pair. Intermediate routers create the forwarding cache entry so that they will know how to forward traffic addressed to the (*, group) pair downstream to the DR originating the PIM-Join message.

When a host first transmits a multicast packet to a group, its DR must forward the packet to the primary RP for subsequent distribution across the group’s delivery tree. The DR encapsulates the multicast packet in a PIM-SM-Register packet and unicasts it to the primary RP for the group. The PIM-SM-Register packet informs the RP of a new source, which causes the active RP to transmit PIM-Join messages back to the source station’s DR. The routers lying between the source’s DR and the RP maintain state from received PIM-Join messages so that they will know how to forward subsequent unencapsulated multicast packets from the source subnetwork to the RP.

The source’s DR ceases to encapsulate data packets in PIM-SM-Registers when it receives Join/Prune messages from the RP. From this point on, the DR forwards data traffic in its native multicast format to the RP. When the RP receives multicast packets from the source station, it resends the packet on the RP-shared tree to all downstream group members.

The RP-shared tree provides connectivity for group members but does not optimize the delivery path through the internetwork. PIM-SM allows receivers to either continue to receive multicast traffic over the RP-shared tree or over a source-rooted shortest-path tree that a receiver subsequently creates thus reducing the transmission delay between itself and a particular source.

A PIM router with local receivers has the option of switching to the source’s shortest-path tree as soon as it starts receiving data packets from the source station. The local receiver’s DR does this by sending a Join message toward the active source. At the same time, protocol mechanisms guarantee that a Prune message for the same source is transmitted to the active RP. Alternatively, the DR may be configured to continue using the RP-based tree and never switch over to the source’s shortest-path tree.

It is important to note that PIM is an Internet draft. It means it is still early in its development cycle and there are several important issues that require further research, engineering, and experimentation:

• PIM-SM still requires routers to maintain a significant amount of state information to describe sources and groups.
• Some multicast routers will be required to have both PIM interfaces and non-PIM interfaces. The interaction and sharing of multicast routing information between PIM and other multicast routing protocols is still in the early stages of definition.
• The future deployment of PIM-SM will probably require more coordination between Internet service providers to support an Internet-wide delivery service.
• Finally, PIM-SM is considerably more complex than DVMRP or the MOSPF extensions.

V. CONCLUSION

This paper describes concepts and mechanisms behind several multicast routing protocols and discusses some of their characteristic, advantages and disadvantages. Short summary of surveyed protocols is given in Table 2.

Since the selection of routing protocols is an important step in deployment of multicast service in a network, this paper is intended to be only the first step in the implementation of multicasting in the Croatian Academic and Research Network. The future considerations will include profiles of expected application usage, scalability, vendor support, performance overhead, dependence on other network protocols, flexibility, interoperability and router overhead.

TABLE 2. Multicast Routing Protocols Overview

REFERENCES

Requests for Comment (RFCs)

[1] RFC 1075 "Distance Vector Multicast Routing Protocol", D. Waitzman, C. Partridge, and S. Deering, November 1988.

[2] RFC 1112 "Host Extensions for IP Multicasting", Steve Deering, August 1989.

[3] RFC 1583 "OSPF Version 2", John Moy, March 1994.

[4] RFC 1584 "Multicast Extensions to OSPF", John Moy, March 1994.

Internet Drafts

[5] "Core Based Trees (CBT) Multicast Routing Architecture", <draft-ietf-idmr-cbt-arch-04.txt>, A. J. Ballardie, June 20, 1995.

[6] "Hierarchical Distance Vector Multicast Routing for the MBONE", Ajit Thyagarajan and Steve Deering, July 1995.

[7] "Protocol-Independent Multicast (PIM), Dense-Mode Protocol Specification", <draft-ietf-idmr-PIM-DM-spec-01.txt>, D. Estrin, D. Farinacci, V. Jacobson, C. Liu, L. Wei, P. Sharma, and A. Helmy, January 17, 1996.

[8] "Protocol-Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification", <draft-ietf-idmr-PIM-SM-spec-02.txt>, S. Deering, D. Estrin, D. Farinacci, V. Jacobson, C. Liu, L. Wei, P. Sharma, and A Helmy, September 7, 1995.

Internet Sites

[9] "Introduction to IP Multicast Routing", An IP Multicast Initiative White Paper, http://www.ipmulticast.com/community/whitepapers/introrouting.html

[10] "How IP Multicast Works", An IP Multicast Initiative White Paper, http://www.ipmulticast.com/community/whitepapers/howipmcworks.html

[11] The MBone Information Web, http://www.mbone.com/