Routing and forwarding in multicast are quite different from unicast. First, since there are typically multiple recipients of a single original packet, the packet’s delivery path has many branches, making the entire path a distribution tree. Secondly, unlike unicast routing, the source address information has an important role in forwarding multicast packets. Additionally, behavior of receiving nodes directly affects routing information via the host-to-router protocol such as MLD.
This section provides a brief overview of the general background of multicast routing, and gives an introduction to Protocol Independent Multicast (PIM), today’s most popular multicast routing protocol. While most of the discussions are not specific to IPv6, these will help understand later sections of this topic, especially for those who are not familiar with this field.
Reverse Path Forwarding
The Reverse Path Forwarding (RPF) algorithm is a fundamental notion of multicast routing. It verifies whether a multicast packet is received on the interface to which the router would forward a unicast packet to the source of the multicast packet. The RPF algorithm prevents forwarding loops by checking the source of the multicast packet and the incoming interface (IIF), permitting a router to accept a multicast packet only if the packet comes from the appropriate interface. The router then forwards this multicast packet onto some or all of the other interfaces. Multicast routing protocol and local multicast group membership determine the list of outgoing interfaces onto which the router fans out the multicast packet.
Figure 2-6 illustrates the basic concept of RPF. In Figure 2-6(a), a multicast packet of source S and group G (denoted as <S, G>) arrives on the correct IIF, and the router forwards the packet to the other interfaces assuming these interfaces are part of the correct outgoing interface list for group G. In Figure 2-6(b), a multicast packet arrives on the wrong IIF so the router discards the packet due to RPF failure.
FIGURE 2-6
Note that group G does not have any effect on performing the RPF check. It is only meaningful when the forwarding router determines the outgoing interfaces.
Multicast Routing Models
There are several models to realize multicast routing. This topic will concentrate on two major models, which the target implementation of this topic supports: the flood and prune model and the explicit-join model. Multicast routing protocols based on these models are often called a dense mode protocol and a sparse mode protocol, respectively.
The following description is not specific to IPv6 multicast routing, but we assume the MLD protocol as the group membership protocol to be specific.
Flood and Prune Model
In the flood and prune model, multicast routers first "flood" multicast packets in the entire network. That is, the routers forward multicast packets to all interfaces except the incoming one based on RPF.
When the packet is delivered to a router that attaches to a leaf network, the router makes a decision based on whether any receivers have informed the router of their existence via the MLD protocol.
If no receivers exist, the "prune" procedure starts. The router at the leaf network sends a prune message (the details may differ among protocols) to the upstream router based on RPF. If a router receives a prune message and no other routers or hosts request the multicast reception, it stops forwarding multicast packets for the group to the arrival interface of the prune message. Additionally, when the router stops forwarding for all possible outgoing interfaces, it then sends the prune message to its upstream router.
By repeating the procedure, the packet distribution converges to the ideal form: packets are delivered to all receivers, and to the receivers only. The resulting forwarding paths form a distribution tree for the pair of source and group addresses.
Figure 2-7 illustrates the flooding process. The arrows represent the flooding paths. There are four hosts in this routing domain: a multicast source S and three receivers, H1 to H3.
Initially, multicast packets from host S are flooded throughout the entire domain including network N2 even though there are no membership nodes on N2.
Then the prune stage starts as shown in Figure 2-8. During the pruning stage, router R3 sends a prune message upstream because R3 has no downstream routers and there are no group members on N2. Since R3 is the only downstream router of R2, R2 also sends a prune message upstream. R1 will stop forwarding the multicast packets to R2 once it receives the prune message from R2. R1 will not propagate a prune message upstream because R1 has one other downstream router, R4, with active group memberships.
The shaded region of the network in Figure 2-8 will be excluded from the multicast forwarding tree once the pruning process completes.
Explicit-Join Model
Flood and prune is a simple mechanism, and works nicely in some environments. In particular, it is advantageous that no special configuration is needed other than enabling the corresponding multicast routing protocol. But it also has disadvantages. First, flood and prune is not suitable for larger scale networks due to its flooding. Secondly, with this model a certain number of packets must be sent on every single link (except the ones excluded by RPF). Depending on the volume of the packets and the link bandwidth, even the short period of unnecessary packets may be undesirable.
FIGURE 2-54
FIGURE 2-8
The explicit-join model explores a totally different way to solve these problems. In this model, when a router receives a Multicast Listener Report from a leaf network, it sends a join message (the details of which depend on the multicast routing protocol) for the group address toward the root node of multicast delivery tree, based on RPF. The root node can be an originating node of packets for the multicast address or a special router, often called a core, located between the originating node and the leaf nodes. For simplicity, the case with a core is mainly explained here, but the essential point is generally the same. Each router on the way to the core forwards the join message to the core, remembering the interest about the group downstream. When the join message arrives at the core, a packet distribution path for the specified multicast group is established.
Figure 2-9 shows the process of establishing a distribution path in the explicit-join model. In this example, two hosts, H1 and H2, are joining a multicast group. When the adjacent routers to H1 and H2, R4 and R5, receive Report messages from these hosts, the routers send join messages toward the core router.
Note that it is not trivial how these routers know the direction to the core router. This is one difficult issue of the explicit-join model with a core router, which will be revisited at the end of this section.
Continuing with the example, assume host S begins multicast packet transmissions to the group (Figure 2-10). The first hop multicast router (R1) will forward these packets to the core router. The core is a special router, so each routing protocol provides a way to determine its address. How the packets are forwarded from the first-hop router to the core also depends on the routing protocol. Once the core receives the packet, it can simply distribute the packet along with the path already established (if any).
FIGURE 2-9
In fact, in Figure 2-10 the core does not forward the packets toward router R5 since no receiver exists in the leaf network attached to R5. This way the packets are only sent on the links where the packets are necessary, and the problems in the flood and prune model are solved or at least mitigated.
Note that the packet distribution path through the core from host S to host H2 or H3 is not the optimal path, which is the path via the link connecting R1 and R3. One of the problems associated with the explicit-join model using a core router is that the core may not be on every optimal path between the source and other group members.
In addition, the dependence on a core router may be problematic in that the core router can be a single point of failure. While particular routing protocols may offer remedies such as [PIMSM-BSR], [RFC3446] and [RFC4610], these proposals have their own issues, such as convergence delay or higher router load. Further details of these issues and solutions are beyond the scope of this topic; for simplicity a single core will generally be assumed in the following discussion.
Another difficult issue in the explicit-join model is how each router knows the address of the core router. The examples shown in Figures 2-9 and 2-10 implicitly assumed each router somehow knew the address, but routing protocols using the explicit-join model actually need to provide methods for this purpose: the address information can be manually configured into each participating router, may be available through a dynamic discovery process [PIMSM-BSR], or can even be embedded in the corresponding multicast address [RFC3446]. Further discussion on core discovery is beyond the scope of this topic. In the rest of this topic, the address of a core router is generally assumed to be given in some way.
FIGURE 2-10
Protocol Independent Multicast
Protocol Independent Multicast, PIM, is a major multicast routing protocol for IPv4, and is the only protocol for IPv6 available in the real world. PIM basically requires that all routers in a routing domain support the protocol, and, unlike DVMRP (Distance Vector Multicast Routing Protocol [RFC1075D, PIM does not require tunneling for bypassing routers that do not support the protocol.
PIM version 2, the current version of PIM, supports multiple network protocols: the packet format and the specification support both IPv4 and IPv6 (and even other or future network protocols).
PIM is called "Protocol Independent" because it is independent from protocols to perform RPF for multicast forwarding and for PIM message exchanges. Within PIM, only multicast group information is exchanged among routers. Typically, routing information given by the unicast routing protocol used in the multicast routing domain is simply used to perform RPF.
Figure 2-11 shows how an IPv6 multicast group address is encoded in PIM messages. Address Family specifies the PIM address family of the Multicast Address field of this encoded address. A value of 2 is assigned to IPv6 by IANA.
Encoding Type specifies the type of encoding used within the specified address family. The value of 0 is reserved and represents the native encoding used by the address family.
B called the Bidirectional PIM bit. The definition and usage of this bit is beyond the scope of this topic.
Reserved must be set to zero by the sender and ignored by the receiver.
Z called the Admin Scope Zone bit. The definition and usage of this bit is beyond the scope of this topic.
Mask length 8-bits in length, and specifies the number of contiguous bits starting from the leftmost bit position. When applied to the Group Multicast Address, it gives the corresponding range of multicast groups.
Group Multicast Address holds the multicast group address. This field is 16 bytes in size when carrying an IPv6 multicast address.
There are two types of PIM protocol: the PIM Sparse Mode (PIM-SM) protocol [RFC4601], and the PIM Dense Mode (PIM-DM) protocol [RFC3973]. The following description provides some key concepts of each PIM protocol, which are essential to understanding the relevant code description in the later sections of this topic. The complexity of the protocols, however, warrants a separate topic (such as [Wil00]) to discuss the protocols in full detail.
FIGURE 2-11
