Tree Formation and Packet Forwarding
Last updated
Last updated
In this article we will touch upon the basic ideas and mechanisms behind multicast. We will get a general sense of how a multicast tree is formed and how traffic flows through the tree. Don’t get too hung up on the details here, as we will go much deeper into how this all works in later articles. The important thing to take from this article is the general ideas behind how multicast works overall.
Unicast traffic is forwarded based on destination IP. Multicast traffic is forwarded based on a different model. Multicast involves a single source sending traffic to multiple hosts. Multicast distribution trees are used in order to forward and replicate traffic sent from a source to all receivers interested in receiving the traffic.
A source distribution tree is a model in which the source (sender) is the root of the tree. The receivers are leaves on the tree, and the brances of the tree connect the receivers to the source.
The routers run a multicast routing protocol (which is outside of the scope of this article for now) in order to learn where receivers are located. Traffic is forwarded from the source towards the receivers.
In this example, the source is 10.1.1.1. The source is sending to the multicast group 239.1.1.1. Source trees are notated as (S, G) in which S is the source address, and G is the multicast group IP address. This tree would be notated as (10.1.1.1, 239.1.1.1).
If you are having trouble visualizing the tree, picture the tree upside down. The server at the top, is the root, or base of the tree, and the tree expands out as you make your way down the diagram and the receivers are spread out.
A source tree is also called a shortest path tree (SPT). This is because the traffic from the source to the receivers follows the shortest path through the network. The path is actually the shortest path from the perspective of the reverse direction of the traffic. The path is built using the receiver’s shortest path towards the source. (The default router connected to the receivers uses its IGP shortest path towards 10.1.1.1 to choose which link it will receive the multicast traffic on). This will make more sense later when we look at RPF checks.
PIM-DM uses a source tree. We will see PIM-DM in action in a later article.
Whereas a source tree is rooted at the source, a shared tree is rooted at a device called the Rendezvous Point (RP). Traffic from any source must flow directly to the RP. The RP then distributes the traffic to the receivers.
Shared trees are notated as (*, G) because any source can send to the group. It doesn’t matter which source is sending, because all traffic goes to the RP first anyways. This is called ASM (any source multicast).
We now have two sources, 10.1.1.1 and 10.1.2.1. However, both multicast flows count as a single tree, (*, G) because the multicast group is the same. The diagram above shows (*, 239.1.1.1). The traffic from both senders goes immediately to the RP. The RP then directs multicast traffic towards the receivers. The RP knows which interfaces face the receivers due to the multicast routing protocol, which we will look at later.
Notice that traffic is not flowing in the shortest path. It would be more optimal if the traffic from 10.1.1.1 flowed like this to the receiver on the far right:
However, this would break the rule which states that the traffic must first go through the RP. This is why a source tree is called a “shortest path tree” in comparison to a shared tree.
A multicast router must deliver traffic towards the receivers and sometimes may have to replicate a packet received on one interface out multiple interfaces. How do routers ensure that a “multicast storm” does not occur?
The answer is that the routers use a reverse path forwarding check to ensure that received multicast traffic arrived on the correct interface.
Reverse path forwarding invovles ensuring that received traffic arrived on the interface that would be used to send traffic towards the source. The unicast topology itself is loop-free (typically built using IGPs that ensure loopfreeness), so the "reverse" of this can also be considered loop-free. The source IP of a received packet is used as the destination IP in a RIB lookup. If the packet was received on the interface that would be used to send unicast traffic towards the source, the packet is accepted. If the packet received on a different interface, the packet is dropped. This will make more sense with an example.
Let’s examine the following source tree:
R5 has a shortest path to 10.1.1.1 via Gi1. The RIB has 10.1.1.1 via Gi1. If R5 receives multicast traffic from the source 10.1.1.1 on Gi1, it passes the RPF check.
What happens if R4 incorrectly replicates the traffic from 10.1.1.1 directly to R5? R2 will reject the packet because it arrived on Gi2, not Gi1. Gi1 is the interface used to deliver unicast traffic to the source, so multicast traffic from the source must arrive on this interface.
In multicast terms, Gi1 on R5 is called the upstream interface for (10.1.1.1, 239.1.1.1). The upstream interface is the interface which the router should receive the multicast traffic on. Gi3 on R5 is the downstream interface for (10.1.1.1, 239.1.1.1). A downstream interface faces the receivers. A router can have multiple downstream interfaces, but only one upstream interface. A packet received on the upstream interface is forwarded out the downstream interface(s). If there are multiple downstream interfaces, the packet is replicated. The list of downstream interfaces is called the OIL (Outgoing Interface List). The OIL is just the set of downstream interfaces for a given (S, G) or (*, G).
Here is the same source tree as before, with the upstream interface of each router labeled as U, and the downstream interfaces labeled as D.
For a source tree, the upstream interface always points towards the source. For a shared tree, the upstream interface always points towards the RP. This is an extremely important concept!
A router connected directly to a source is called a First Hop Router (FHR). It is the first hop of the multicast traffic. A router connected directly to receivers is called a Last Hop Router (LHR). (It is the last router hop the multicast traffic takes). Here is the diagram above with these router functions labeled.
An LHR is responsible for keeping track of whether or not receivers exist on the LAN. Receivers signal interest in a multicast group to their LHR, and a LHR periodically checks that receivers still exist for the multicast group. The protocol used to control this process is called IGMP (Internet Group Membership Protocol), which we will explore in the next article.
Make sure you fully understand these concepts before moving on. These concepts build the foundation of multicast, and are needed in order to understand how PIM (the multicast routing protocol) works.
I would suggest re-reading this article and doing some outside study. You can also move on to IGMP and PIM, and then come back to these concepts afterwards. It will probably make even more sense once you have a basic understanding of how PIM works. I imagine these concepts will be totally foreign to you if you are new to multicast. If so, don’t fret and simply give it a little time for the concepts to sink in.
