Introduction to IP Multicast RoutingBy Chuck Semeria and Tom MauferAbstractThe first part of this paper describes the benefits of multicasting, the Multicast Backbone (MBONE), Class D addressing, and the operation of the Internet Group Management Protocol (IGMP). The second section explores a number of different algorithms that may potentially be employed by multicast routing protocols:
The third part contains the main body of the paper.
It describes how the previous algorithms are implemented
in multicast routing protocols available today.
IntroductionThere are three fundamental types of IPv4 addresses: unicast, broadcast, and multicast. A unicast address is designed to transmit a packet to a single destination. A broadcast address is used to send a datagram to an entire subnetwork. A multicast address is designed to enable the delivery of datagrams to a set of hosts that have been configured as members of a multicast group in various scattered subnetworks.Multicasting is not connection oriented. A multicast datagram is delivered to destination group members with the same "best-effort" reliability as a standard unicast IP datagram. This means that a multicast datagram is not guaranteed to reach all members of the group, or arrive in the same order relative to the transmission of other packets. The only 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. Instead of a Class A, B, or C IP address, multicasting employs a Class D destination address format (224.0.0.0- 239.255.255.255).
Multicast Groups
Group Membership Protocol
Figure 1: Multicast IP Delivery Service
Multicast Routing Protocol
Multicast Support for Emerging Internet ApplicationsToday, the majority of Internet applications rely on point-to-point transmission. The utilization of point-to-multipoint transmission has traditionally been limited to local area network applications. Over the past few years the Internet has seen a rise in the number of new applications that rely on multicast transmission. Multicast IP conserves bandwidth by forcing the network to do packet replication only when necessary, and offers an attractive alternative to unicast transmission for the delivery of network ticker tapes, live stock quotes, multiparty video-conferencing, and shared whiteboard applications (among others). It is important to note that the applications for IP Multicast are not solely limited to the Internet. Multicast IP can also play an important role in large distributed commercial networks.
Reducing Network Load
Resource Discovery
Support for Datacasting Applications
The Internet's Multicast Backbone (MBONE)The Internet Multicast Backbone (MBONE) is an interconnected set of subnetworks and routers that support the delivery of IP multicast traffic. The goal of the MBONE is to construct a semipermanent IP multicast testbed to enable the deployment of multicast applications without waiting for the ubiquitous deployment of multicast-capable routers in the Internet.The MBONE has grown from 40 subnets in four different countries in 1992 to more than 2800 subnets in over 25 countries by April 1996. With new multicast applications and multicast-based services appearing, it appears likely that the use of multicast technology in the Internet will continue to grow at an ever-increasing rate. The MBONE is a virtual network that is layered on top of sections of the physical Internet. It is composed of islands of multicast routing capability connected to other islands by virtual point-to-point links called "tunnels." The tunnels allow multicast traffic to pass through the non-multicast-capable parts of the Internet. IP multicast packets are encapsulated as IP-over-IP (i.e., the protocol number is set to 4), so they look like normal unicast packets to intervening routers. The encapsulation is added on entry to a tunnel and stripped off on exit from a tunnel. This set of multicast routers, their directly connected subnetworks, and the interconnecting tunnels define the
Figure 2: Internet Multicast Backbone (MBONE) Since the MBONE and the Internet have different topologies, multicast routers execute a separate routing protocol to decide how to forward multicast packets. The majority of the MBONE routers currently use the Distance Vector Multicast Routing Protocol (DVMRP), although some portions of the MBONE execute either Multicast OSPF (MOSPF) or the Protocol-Independent Multicast (PIM) routing protocols. The operation of each of these protocols is discussed later in this paper. The MBONE carries audio and video multicasts of IETF meetings, NASA space shuttle missions, U.S. House and Senate sessions, and live satellite weather photos. The Session Directory (SD) tool provides users with a listing of the active multicast sessions on the MBONE and allows them to define or join a conference.
Multicast AddressingA multicast address is assigned to a set of receivers defining a multicast group. Senders use the multicast address as the destination IP address of a packet that is to be transmitted to all group members.
Class D Addresses
Figure 3: Class D Multicast Address Format The Internet Assigned Numbers Authority (IANA) maintains a list of registered IP multicast groups. The base address 224.0.0.0 is reserved and cannot be assigned to any group. The block of multicast addresses ranging from 224.0.0.1 to 224.0.0.255 is reserved for the use of routing protocols and other low-level topology discovery or maintenance protocols. Multicast routers should not forward a multicast datagram with a destination address in this range, regardless of its TTL. The remaining groups ranging from 224.0.1.0 to 239.255.255.255 are assigned to various multicast applications or remain unassigned. From this range, 239.0.0.0 to 239.255.255.255 are to be reserved for site-local "administratively scoped" applications, not Internet-wide applications. Some of the well-known groups include: "all systems on this subnet" (224.0.0.1), "all routers on this subnet"(224.0.0.2), "all DVMRP routers" (224.0.0.4), "all OSPF routers" (224.0.0.5), "IETF-1-Audio" (224.0.1.11), "IETF-1- Video" (224.0.1.12), "AUDIONEWS" (224.0.1.7), and "MUSIC- SERVICE" (224.0.1.16).
Mapping a Class D Address to an Ethernet Address For example, the mapping between a Class D IP address and an Ethernet multicast address is obtained by placing the low-order 23 bits of the Class D address into the low-order 23 bits of IANA's reserved address block. Figure 4 illustrates how the multicast group address 224.10.8.5 (E0-0A-08-05) is mapped into an Ethernet (IEEE-802) multicast address.
Figure 4: Mapping Between Class D and IEEE-802 Multicast Addresses The mapping in Figure 4 places the low-order 23 bits of the IP multicast group ID into the low order 23 bits of the Ethernet address. You should note that the mapping may place up to 32 different IP groups into the same Ethernet address because the upper five bits of the IP multicast group ID are ignored. For example, the multicast addresses 224.138.8.5 (E0-8A-08-05) and 225.10.8.5 (E1-0A-08-05) would also be mapped to the same Ethernet address (01-00-5E-0A-08-05) used in this example.
Transmission and Delivery of Multicast Datagrams Things become much more complicated when the sender is attached to one subnetwork and receivers reside on different subnetworks. In this case, the routers are required to implement a multicast routing protocol that permits the construction of multicast delivery trees and supports multicast data packet forwarding. In addition, each router needs to implement a group membership protocol that allows it to learn about the existence of group members on its directly attached subnetworks.
Internet Group Management Protocol (IGMP)The Internet Group Management Protocol (IGMP) runs between hosts and their immediately neighboring multicast routers. The mechanisms of the protocol allow a host to inform its local router that it wishes to receive transmissions addressed to a specific multicast group. Also, routers periodically query the LAN to determine if known group members are still active. If there is more than one router on the LAN performing IP multicasting, one of the routers is elected "querier" and assumes the responsibility of querying the LAN for group members.Based on the group membership information learned from the IGMP, a router is able to determine which (if any) multicast traffic needs to be forwarded to each of its "leaf" subnetworks. Multicast routers use this information, in conjunction with a multicast routing protocol, to support IP multicasting across the Internet.
IGMP Version 1
Figure 5: Internet Group Management Protocol-Query Message
When a host receives a Query message, it responds with
a Host Membership Report for each host group to which
it belongs. In order to avoid a flurry of Reports,
each host starts a randomly chosen Report delay timer
for each of its group memberships. If, during the delay
period, another Report is heard for the same group,
the local host resets its timer to a new random value.
It should be noted that multicast routers do not need
to be directly addressed since their interfaces are
configured to receive all multicast IP traffic. Also,
a router does not need to maintain a detailed list
of which hosts belong to each multicast group; the
router only needs to know that at least one group member
is present on a network interface. If the router does not receive a Report for a particular group after a number of Queries, the router assumes that group members are no longer present on the interface and the group is removed from the list of group memberships for the directly attached subnetwork. When a host first joins a group, it immediately transmits a Report for the group rather than waiting for a router Query. This guarantees that the host will receive traffic addressed to the group if it is the first member of that group on the subnetwork.
IGMP Version 2 IGMP Version 2 defines a procedure for the election of the multicast querier for each LAN. In IGMP Version 2, the router with the lowest IP address on the LAN is elected the multicast querier. In IGMP Version 1, the querier election was determined by the multicast routing protocol. This could lead to potential problems because each multicast routing protocol used different methods for determining the multicast querier. IGMP Version 2 defines a new type of Query message-the Group-Specific Query message. Group-Specific Query messages allow a router to transmit a Query to a specific multicast group rather than all groups residing on a directly attached subnetwork. Finally, IGMP Version 2 defines a Leave Group message to lower IGMP's "leave latency." When the last host to respond to a Query with a Report wishes to leave that specific group, the host transmits a Leave Group message to the all-routers group (224.0.0.2) with the group field set to the group to be left. In response to a Leave Group message, the router begins the transmission of Group-Specific Query messages on the interface that received the Leave Group message. If there are no Reports in response to the Group-Specific Query messages, the group is removed from the list of group memberships for the directly attached subnetwork.
IGMP Version 3 IGMP Version 3 will help conserve bandwidth by allowing a host to select the specific sources from which it wants to receive traffic. Also, multicast routing protocols will be able to make use of this information to conserve bandwidth when constructing the branches of their multicast delivery trees. Finally, support for Leave Group messages first introduced in IGMP Version 2 has been enhanced to support Group-Source Leave messages. This feature allows a host to leave an entire group or to specify the specific IP address(es) of the (source, group) pair(s) that it wishes to leave.
Multicast Forwarding AlgorithmsIGMP provides the final step in a multicast packet delivery service since it is only concerned with the forwarding of multicast traffic from the local router to group members on directly attached subnetworks. IGMP is not concerned with the delivery of multicast packets between neighboring routers or across an internetwork. To provide an Internet-wide delivery service, it is necessary to define multicast routing protocols. A multicast routing protocol is responsible for the construction of multicast packet delivery trees and performing multicast packet forwarding. This section explores a number of different algorithms that may potentially be employed by multicast routing protocols:
Later sections will describe how these algorithms are
implemented in the most prevalent multicast routing
protocols in the Internet today.
Flooding A flooding algorithm is very simple to implement since a router does not have to maintain a routing table and only needs to keep track of the most recently seen packets. However, flooding does not scale for Internet-wide applications since it generates a large number of duplicate packets and uses all available paths across the internetwork instead of just a limited number. Also, the flooding algorithm makes inefficient use of router memory resources since each router is required to maintain a distinct table entry for each recently seen packet.
Spanning Tree
Figure 6: Spanning Tree 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 originally arrived. Forwarding along the branches of a spanning tree guarantees that the multicast packet will not loop and that it will eventually reach all routers in the internetwork. A spanning tree solution is powerful and is relatively easy to implement since there is a great deal of experience with spanning tree protocols in the Internet community. However, a spanning tree solution can centralize traffic on a small number of links, and may not provide the most efficient path between the source subnetwork and group members.
Reverse Path Broadcasting (RPB)
Operation
Figure 7: Reverse Path Broadcasting-Forwarding Algorithm This basic algorithm can be enhanced to reduce unnecessary packet duplication if the router making the forwarding decision can determine whether a neighboring router on a potential child link considers the local router to be on its shortest path back to the source [i.e., on the remote router's parent link for the (source, group) pair]. If this is the case, the packet is forwarded to the neighbor. Otherwise, the datagram is not forwarded on the potential child link because the neighboring router will be required to discard the packet since it arrives on a non-parent link for the (source, group) pair. The information needed to make this "downstream" decision is relatively easy to derive from a link-state routing protocol since each router maintains a topological database for the entire routing domain. If a distance-vector routing protocol is employed, a neighbor can either advertise its previous hop for the (source, group) pair as part of its routing update messages or "poison reverse" the route. Either of these techniques allows an upstream router to determine if a downstream neighboring router considers it to be on the downstream router's shortest path back to the source.
Figure 8: Example of Reverse Path Broadcasting Figure 8 shows an example of the basic operation of the enhanced RPB algorithm. Note that the source station (S) is attached to a leaf subnetwork directly connected to Router A. For this example, we will look at the RPB algorithm from Router B's perspective. Router B receives the multicast packet from Router A on link 1. Since Router B considers link 1 to be the parent link for the (source, group) pair, it forwards the packet on link 4, link 5, and the local leaf subnetworks if they have group members. Router B does not forward the packet on link 3 because it knows from routing protocol exchanges that Router C considers link 2 as its parent link for the (source, group) pair. If Router B were to forward the packet on link 3 it would be discarded by Router C since it would arrive on a non-parent link for the (source, group) pair.
Benefits and Limitations 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, datagrams may be unnecessarily forwarded to subnetworks that have no members in the destination group.
Truncated Reverse Path Broadcasting (TRPB)
Figure 9: Truncated Reverse Path Broadcasting (TRPB) Figure 9 illustrates the operation of the TRPB algorithm. In this example the router receives a multicast packet on its parent link for the (Source, G1) pair. The router forwards the datagram on !1 since the interface has at least one member of G1. The router does not forward the datagram to !3 since this interface has no members in the destination group. The datagram is forwarded on !4 if and only if a downstream router considers the interface as part of its parent link for the (Source, G1) pair. TRPB removes some limitations of RPB, but it solves only part of the problem. It eliminates unnecessary traffic on leaf subnetworks but it does not consider group memberships when building the branches of the distribution tree.
Reverse Path Multicasting (RPM) RPM allows the source-rooted spanning tree to be pruned so that datagrams are only forwarded along branches that lead to members of the destination group.
Operation
Figure 10: Reverse Path Multicasting (RPM) An upstream router receiving a prune message is required to record the prune information in memory. If the upstream router has no local recipient and 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 "live" 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 must be refreshed at regular intervals. 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.
Limitations
Core-Based Trees (CBT)
Operation
Figure 11: Multi-Core CBT Multicast Delivery Tree Each station that wishes to receive traffic that has been addressed to a multicast group is required to send a "join" message toward the "core tree" of the particular multicast group. A potential group member only needs to know the address of one of the group's core routers in order to transmit a unicast join request. The join request is processed by all intermediate routers that identify the interface on which the join was received as belonging to the group's delivery tree. The intermediate routers continue to forward the join message toward the core and marking local interfaces until the request reaches a core router. 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 unicast 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 on the delivery tree.
Benefits
Limitations
Distance Vector Multicast Routing Protocol (DVMRP)The Distance Vector Multicast Routing Protocol (DVMRP) is a distance-vector routing protocol designed to support the forwarding of multicast datagrams through an internetwork. DVMRP constructs source-rooted multicast delivery trees using variants of the Reverse Path Broadcasting (RPB) algorithm. Some version of DVMRP is currently deployed in the majority of MBONE routers.DVMRP was first defined in RFC-1075. 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. It is important to note that the latest mrouted version 3.8 and vendor implementations have 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 regards.
Physical and Tunnel Interfaces
Table 1 TTL Scope Control Values A multicast router will only forward a multicast datagram 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 that are used to restrict the scope of an IP multicast. For example, a multicast datagram with a TTL of less than 32 is restricted to the same site and should not be forwarded across an interface to other sites in the same region.
Basic Operation DVMRP implements a mechanism 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 sourc,e allowing previously pruned branches to be restored as part of the multicast delivery tree.
DVMRP Router Functions
Figure 12: DVMRP Designated Router In order to avoid duplicate multicast datagrams when there is more than one DVMRP router on a subnetwork, one router is elected the Dominant Router for the particular source subnetwork (see Figure 12). In Figure 13, Router C is downstream and may potentially receive datagrams from the source subnetwork from Router A or Router B. If Router A's metric to the source subnetwork is less than Router B's metric, Router A is dominant to Router B for this source. This means that Router A forwards traffic from the source subnetwork and Router B discards traffic from the source subnetwork. However, if Router A's metric is equal to Router B's metric, the router with the lowest IP address on its downstream interface (child link) becomes the Dominant Router.
Figure 13: DVMRP Dominant Router
DVMRP Routing Table 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. A sample routing table for a DVMRP router is shown in Figure 14. Unlike the typical table created by a unicast routing protocol such as RIP, the DVMRP routing table contains Source Subnets and From-Gateways instead of Destinations and Next-Hop Gateways. The routing table represents the shortest path source-rooted spanning tree to every participating subnetwork in the internetwork-the Reverse Path Broadcasting (RPB) tree. The DVMRP routing table does not consider group membership or received prune messages.
Figure 14: DVMRP Routing Table The key elements in DVMRP routing table include the following items: Source Subnet - A subnetwork containing a host sourcing multicast datagrams. Subnet Mask - The subnet mask assigned to the Source Subnet. Note that the DVMRP provides the subnet mask for each source subnetwork. From-Gateway - The previous hop router leading back to the Source Subnet. TTL - The time-to-live is used for table management and indicates the number of seconds before an entry is removed from the routing table.
DVMRP Forwarding Table
Figure 15: DVMRP Forwarding Table The forwarding table for a typical DVMRP router is shown in Figure 15. The elements in this display include the following items: Source Subnet - The subnetwork containing a host sourcing multicast datagrams addressed to the specified groups. Multicast Group - The Class D IP address to which multicast datagrams are addressed. Note that a given Source Subnet may contain sources for many different Multicast Groups. InPort - The parent port for the (source, group) pair. A "Pr" in this column indicates that a prune message has been sent to the upstream router. OutPorts - The child ports over which multicast datagrams for the (source, group) pair are forwarded. A lower-case "p" in this column indicates that the router has received a prune message from a downstream router.
Hierarchical DVMRP
Benefits of Hierarchical Multicast Routing
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:
Hierarchical Architecture
Figure 16: Hierarchical DVMRP The L2 routers exchange routing information in the form of Region-Ids instead of the individual subnetwork addresses contained within each region. With DVMRP as the L2 protocol, inter-regional multicast delivery tree is constructed based on the (region_ID, group) pair rather than the standard (source, group) pair. When a multicast packet originates within a region, it is forwarded according to the L1 protocol to all subnetworks containing group members. In addition, the datagram is forwarded to each of the boundary routers (L2) configured for the source region. The L2 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 L1 routers.
Multicast Extensions to OSPF (MOSPF)Version 2 of the Open Shortest Path First (OSPF) routing protocol is defined in RFC-1583. 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.The Multicast extensions to OSPF (MOSPF) are defined in RFC-1584. MOSPF routers maintain a current image of the network topology through the unicast OSPF link-state routing protocol. MOSPF enhances the OSPF protocol by providing the ability to route multicast IP traffic. The multicast extensions to OSPF are built on top of OSPF Version 2 so that a multicast routing capability can be easily introduced into an OSPF Version 2 routing domain. 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.
Intra-Area Routing with MOSPF
Local Group Database On any given subnetwork, the transmission of IGMP Host Membership Queries is performed solely by the Designated Router (DR). Also, the responsibility of listening to IGMP Host Membership Reports is performed only by the Designated Router (DR) and the Backup Designated Router (BDR). This means that in a mixed environment containing both MOSPF and OSPF routers, an MOSPF router must be elected the DR for the subnetwork if IGMP Queries are to be generated. This can be achieved by simply assigning all non-MOSPF routers a RouterPriority of 0 to prevent them from becoming the DR or BDR, thus allowing an MOSPF router to become the DR for the subnetwork. The DR is responsible for communicating group membership information to all other routers in the OSPF area by flooding Group-Membership LSAs. The DR originates a separate Group-Membership LSA for each multicast group having one or more entries in the DR's local group database. Similar to Router-LSAs and Network-LSAs, Group Membership-LSAs are flooded throughout a single area only. This ensures that all remotely originated multicast datagrams are forwarded to the specified subnetwork for distribution to local group members.
Datagram's Shortest Path Tree When the initial datagram arrives, the source subnetwork is located in the MOSPF link state database. The MOSPF link state database is simply the standard OSPF link state database with the addition of Group-Membership LSAs. Based on the Router-LSAs and Network-LSAs in the MOSPF link state database, a source-rooted shortest-path tree is constructed using Dijkstra's algorithm. After the tree is built, Group-Membership LSAs are used to prune those branches that do not lead to subnetworks containing individual group members. The result of the Dijkstra calculation is a pruned shortest-path tree rooted at the datagram's source.
Figure 17: Shortest Path Tree for (S, G) To forward a multicast datagram to downstream members of the group, each router must determine its position in the datagram's shortest path delivery tree. Assume that Figure 17 illustrates the shortest path tree for a particular (source, group) pair. Router E's upstream node is Router B and there are two downstream interfaces: one connecting to Subnetwork 6 and another connecting to Subnetwork 7.
Note the following properties of the basic MOSPF routing
algorithm:
Forwarding Cache
Figure 18: MOSPF Forwarding Cache Figure 18 displays the forwarding cache for an example MOSPF router. The elements in the display include the following items: Destination - The destination group address to which matching datagrams are forwarded. Source - The datagram's source subnetwork. Each Destination/Source pair identifies a separate forwarding cache entry. Upstream - The interface from which a matching datagram must be received. Downstream - The interfaces over which a matching datagram should be forwarded to reach Destination group members. TTL - The minimum number of hops a datagram will travel to reach the multicast group members. This allows the router to discard datagrams that do not have a chance of reaching a destination group member.
The information in the forwarding cache is not aged
or periodically refreshed. It is maintained as long
as there are system resources available (i.e., memory)
or until the next topology change. In general, the
contents of the forwarding cache will change when:
Mixing MOSPF and OSPF Routers
It is important to note that an 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:
Inter-Area Routing with MOSPF
Inter-Area Multicast Forwarders Inter-area multicast forwarders summarize their attached areas' group membership information to the backbone by originating new Group-Membership LSAs into the backbone area (Figure 19). It is important to note that the summarization of group membership in MOSPF is asymmetric. This means that group membership information from non-backbone areas is flooded into the backbone. However, the backbone does not readvertise either backbone group membership information or group membership information learned from other non-backbone areas into any non-backbone areas.
Figure 19: Inter-Area Routing Architecture To permit the forwarding of multicast traffic between areas, MOSPF introduces the concept of a "wild-card multicast receiver." A wild-card multicast receiver is a router that receives all multicast traffic generated in an area, regardless of the multicast group membership. In non-backbone areas, all inter-area multicast forwarders operate as wild-card multicast receivers. This guarantees that all multicast traffic originating in a non-backbone area is delivered to its inter-area multicast forwarder, and then if necessary into the backbone area. Since the backbone has group membership knowledge for all areas, the datagram can then be forwarded to group members residing in the backbone and other, non-backbone areas. The backbone area does not require wild-card multicast receivers because the routers in the backbone area have complete knowledge of group membership information for the entire OSPF system.
Inter-Area Datagram Shortest-Path Tree There are two cases that need to be considered when constructing an inter-area shortest-path delivery tree. The first involves the condition when the source subnetwork is located in the same area as the router performing the calculation. The second situation occurs when the source subnetwork is located in a different area than the router performing the calculation. If the source of a multicast datagram resides in the same area as the router performing the calculation, the pruning process must be careful to ensure that branches leading to other areas are not removed from the tree (Figure 20). Only those branches having no group members nor wild-card multicast receivers are pruned. Branches containing wild-card multicast receivers must be retained, since the local routers do not know if there are group members residing in other areas.
Figure 20: Datagram Shortest-Path Tree-Source in Same Area If the source of a multicast datagram resides in a different area than the router performing the calculation, the details describing the local topology surrounding the source station are not known. However, this information can be estimated using information provided by Summary-Links LSAs for the source subnetwork. In this case, the base of the tree begins with branches directly connecting the source subnetwork to each of the local area's inter-area multicast forwarders (Figure 21). The inter-area multicast forwarders must be included in the tree, since any multicast datagrams originating outside the local area will enter the area via an inter-area multicast forwarder.
Figure 21: Datagram Shortest-Path Tree-Source in a Remote Area Since each inter-area multicast forwarder is also an ABR, it must maintain a separate link-state database for each attached area. This means that each inter-area multicast forwarder is required to calculate a separate forwarding tree for each of its attached areas. After the individual trees are calculated, they are merged into a single forwarding cache entry for the (source, group) pair and then the individual trees are discarded.
Inter-Autonomous System Multicasting with MOSPF To facilitate inter-AS multicast routing, selected Autonomous System Boundary Routers (ASBRs) are configured as "inter-AS multicast forwarders." MOSPF makes the assumption that each inter-AS multicast forwarder executes an inter-AS multicast routing protocol (such as DVMRP), which forwards multicast datagrams in a reverse path forwarding (RPF) manner. Each inter-AS multicast forwarder functions as a wild-card multicast receiver in each of its attached areas. This guarantees that each inter-AS multicast forwarder remains on all pruned shortest-path trees and receives all multicast datagrams, regardless of the multicast group membership. Three cases need to be considered when describing the construction of an inter-AS shortest-path delivery tree. The first occurs when the source subnetwork is located in the same area as the router performing the calculation. For the second case, the source subnetwork resides in a different area than the router performing the calculation. The final case occurs when the source subnetwork is located in a different AS (or in another routing domain within the same AS) than the router performing the calculation. The first two cases are similar to the inter-area examples described in the previous section. The only enhancement is that inter-AS multicast forwarders must also be included on the pruned shortest path delivery tree. Branches containing inter-AS multicast forwarders must be retained since the local routers do not know if there are group members residing in other Autonomous Systems. When a multicast datagram arrives at an inter-AS multicast forwarder, it is the responsibility of the ASBR to determine whether the datagram should be forwarded outside of the local Autonomous System. Figure 22 illustrates a sample inter-AS shortest path delivery tree when the source subnetwork resides in the same area as the router performing the calculation.
Figure 22: Inter-AS Datagram Shortest-Path Tree-Source in Same Area If the source of a multicast datagram resides in a different Autonomous System than the router performing the calculation, the details describing the local topology surrounding the source station are not known. However, this information can be estimated using the multicast-capable AS-External Links describing the source subnetwork. In this case, the base of the tree begins with branches directly connecting the source subnetwork to each of the local area's inter-AS multicast forwarders. Figure 23 shows a sample inter-AS shortest-path delivery tree when the inter-AS multicast forwarder resides in the same area as the router performing the calculation. If the inter-AS multicast forwarder is located in a different area than the router performing the calculation, the topology surrounding the source is approximated by combining the Summary-ASBR Link with the multicast-capable AS-External Link.
Figure 23: Inter-AS Datagram Shortest-Path Tree-Source in Different AS As a final point, it is important to note that AS External Links are not imported into Stub areas. If the source is located outside of the stub area, the topology surrounding the source is estimated by the Default Summary Links originated by the stub area's intra-area multicast forwarder rather than the AS-External Links.
Protocol-Independent Multicast (PIM)The Protocol-Independent Multicast (PIM) routing protocol is currently under development by the Inter-Domain Multicast Routing (IDMR) working group of the IETF. The objective of the IDMR working group is to develop a standard multicast routing protocol that can provide scalable inter-domain multicast routing across the Internet.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 to provide 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 designers of PIM argue that DVMRP and MOSPF were developed for environments where group members are densely distributed. They emphasize that when group members and senders are sparsely distributed across a wide area, DVMRP and MOSPF 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)
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:
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-SM differs from existing dense-mode multicast algorithms
in two essential ways:
Figure 24: Rendezvous Points
Directly Attached Host Joins a Group
Figure 25: Host Joins a Multicast Group To facilitate the differentiation between DM and SM groups, a part of the Class D multicast address space is being reserved for use 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. The draft specification describes a procedure for the selection of the primary RP and the use of alternate RPs if the primary RP becomes unreachable. 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.
Directly Attached Source Sends to a Group
Figure 26: Source Sends to a Multicast Group The source's DR ceases to encapsulate data packets in PIM-SM- Registers when it receives Join/Prune messages from the RP. At this point, data traffic is forwarded by the DR in its native multicast format to the RP. When the RP receives multicast packets from the source station, it resends the datagrams on the RP-shared tree to all downstream group members.
RP-Shared Tree or Shortest Path Tree (SPT)
Figure 27: RP-Shared Tree (RP Tree) and Shortest-Path Tree (SPT) 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 changeover may be triggered if the data rate from the source station exceeds a predefined threshold. 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.
Unresolved Issues
ReferencesRequests for Comment (RFCs)1075 "Distance Vector Multicast Routing Protocol," D. Waitzman, C. Partridge, and S. Deering, November 1988.1112 "Host Extensions for IP Multicasting," Steve Deering, August 1989. 1583 "OSPF Version 2," John Moy, March 1994. 1584 "Multicast Extensions to OSPF," John Moy, March 1994. 1585 "MOSPF: Analysis and Experience," John Moy, March 1994. 1800 "Internet Official Protocol Standards," Jon Postel, Editor, July 1995. 1812 "Requirements for IP Version 4 Routers," Fred Baker, Editor, June 1995.
Internet Drafts"Core Based Trees (CBT) Multicast: Architectural Overview," <draft-ietf-idmr-cbt-arch- 02.txt>, A. J. Ballardie, June 20, 1995."Core Based Trees (CBT) Multicast: Protocol Specification," <draft -ietf-idmr-cbt-spec-03.txt>, A. J. Ballardie, November 21, 1995. "Hierarchical Distance Vector Multicast Routing for the MBONE," Ajit Thyagarajan and Steve Deering, July 1995. "Internet Group Management Protocol, Version 2," <draft-ietf- idmr-igmp-v2-01.txt>, William Fenner, Expires April 1996. "Internet Group Management Protocol, Version 3," <draft-cain- igmp-00.txt>, Brad Cain, Ajit Thyagarajan, and Steve Deering, Expires March 8, 1996 "Protocol-Independent Multicast (PIM), Dense-Mode Protocol Specification," <draft-ietf- idmr-PIM-DM-spec-01.ps>, D. Estrin, D. Farinacci, V. Jacobson, C. Liu, L. Wei, P. Sharma, and A. Helmy, January 17, 1996. "Protocol-Independent Multicast (PIM): Motivation and Architecture," <draft-ietf-idmr-pim- arch-01.ps>, S. Deering, D. Estrin, D. Farinacci, V. Jacobson, C. Liu, and L. Wei, January 11, 1995. "Protocol-Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification," <draft-ietf-idmr-PIM-SM-spec-02.ps>, S. Deering, D. Estrin, D. Farinacci, V. Jacobson, C. Liu, L. Wei, P. Sharma, and A Helmy, September 7, 1995.
TextbooksComer, Douglas E. Internetworking with TCP/IP: Volume 1-Principles, Protocols, and Architecture, Second Edition. Englewood Cliffs, NJ: Prentice Hall, 1991.Huitema, Christian. Routing in the Internet. Englewood Cliffs, NJ: Prentice Hall, 1995. Stevens, W. Richard. TCP/IP Illustrated: Volume 1 The Protocols. Reading, MA: Addison Wesley, 1994. Wright, Gary, and W. Richard Stevens. TCP/IP Illustrated: Volume 2-The Implementation. Reading, MA: Addison Wesley, 1995
Other Ballardie, Anthony J. "A New Approach to Multicast Communication in a Datagram Internetwork," Ph.D. Thesis, University of London, May 1995.
Click here to download a part one of this Paper (62KB) in Adobe Acrobat format.
|