Multicast Routing Algorithms

In this article I’ll expose each multicast routing algorithm that I studied: Flooding, Spanning-Tree, RPB and RPM.

Flooding

Flooding is the most basic multicast routing algorithm. The way it works is as follows:

  1. the router receives a multicast packet on interface Int1
  2. if the packet is “seen” for the first time, then the router duplicates it on all other interfaces. Otherwise, it discards it.

The fact of “seeing” the packet or not is trackable by a table entry in the router memory.

Flooding does not involve any routing tables. The more links we have the more router memory it consumes. Besides, its loop detection mechanism is weak.

Spanning-Tree

And I am not referring to the spanning tree protocol. This algorithm was popular among Internet users. Is is based on flooding but instead of doing it all over the place, it is done on each spanning tree.

Spanning trees are built on links between routers. A Spanning tree is an active and loop-free path between each two routers.

The problem with this algorithm is that some links will be heavily used while others are not at all.

Reverse Path Broadcast (RPB)

another multicast routing algorithm is the Reverse Path Broadcast. Built on the Spanning-Tree algorithm, the Reverse Path Broadcast algorithm is also called Reverse Path Forwarding RPF. It introduces the following concepts:

  • Source: “Where you must go; where the path of the One ends.“, The Oracle said in the Matrix. This is the source of the multicast traffic
  • (source, group) pair: a pair that identifies multicast traffic in the Reverse Path Broadcast algorithm
  • Parent link: a link that is on the shortest path from a multicast router to the Source.
  • Child link: any non-parent link
  • Leaf subnetwork: a subnet that is attached to a multicast router.

The purpose of the RPB is to build, for each (source, group) pair, a spanning-tree that is rooted in the source of the multicast group. For example, if we have two sources of multicast traffic, then two spanning trees will be built.

Similarly, if we have more than one source in the same multicast group, a spanning-tree will be built for each source. And each spanning-tree is rooted in the source.of the multicast group.

The operation of RPB is simple: any multicast packet received on a parent link is duplicated on all child links.

We said that RPB duplicates the multicast packet on all the child links. However, RPB can determine whether to send multicast packets on specific interfaces or not. The reason is because sometimes a neighbor router receives the multicast packet on a link and then finds that it’s a child link. So it simply discards it. Therefore, the local router should not have sent the packet on the first place.

So how can a router learn which links are parent links and which are child links? The answer is that RPB builds on information it gathers from the routing protocol used in the network; if a link state protocol is being deployed, then the router has a topological database and both the link state tree rooted on router X and the multicast tree sourced at router X are the same. If it’s a distance vector protocol, the neighboring router can inform the local router that the common link is a child link for it, and it will discard the packet anyway.

multicast-routing-algorithms-1
Figure: a Reverse Path Broadcast example © Stanford University

Let’s run an example. The figure above shows bold and normal links. The bold links represent the shortest path tree from host S to all other routers. RPB will use this tree.

  • the source S sends a multicast packet to the multicast group. Router A is directly attached to the source of the multicast traffic. It is connected to both B and C. Router A sends a multicast packet to each of B and C,
  • B receives a multicast packet on link 1. This is a parent link. It duplicates the packet on all other links 3, 4, 5 and the leaf links
  • C receives the packet on link 2, which is a parent link. It also receives a multicast packet on link 3. This is a child link for C. So C discards the packet
  • Router D receives the packet on link 4. This is a parent link. It also duplicates the packet on link 8
  • Router E receives the multicast packet on links 5, 6, 8 and 9. Link 5 is a parent link. The other links are child links. So router E accepts the packet on link 5 and discards the rest
  • Router E duplicates the multicast packet on child links 6, 8 and 9
  • Router F receives the multicast packet on links 7 and 9. It accepts the packet only on link 7 because it is the parent link.

To optimize this example, let’s assume that B learned that link 3 is a child link for C. So when B receives a mutlicast packet, it will send it out of all links except links 1 and 3.

Reverse Path Multicast (RPM)

The Reverse Path Multicast is a multicast routing algorithm that is based on the Reverse Path Broadcast, with the introduction of the pruning concept.

Routers are connected to sub-networks. The sub-networks may contain hosts that request to participate in the multicast process (through IGMP). In this case, we call these leaf sub-networks with group members. Otherwise, they are leaf sub-networks with no group members.

multicast-routing-algorithms-2
Figure: Reverse Path Multicast algorithm example © Stanford University

Initially, all routers receive one copy of the multicast packet. Then, each router that is connected to leaf sub-networks with no group members sends a prune message one hop back towards the source. The upstream router receives the prune message on its child links, writes the prune information in memory and forwards the prune message one hop back to the source too.

The Source receives the prune messages, and a source-based forwarding multicast tree is built of only “live branches”.

Pruning is dynamic in time. So routers send prune messages regularly and the forwarding multicast tree is refreshed.

We see that Reverse Path Multicast requires routers to maintain state information in memory. The state information is updated with each wave of pruning messages, which does not scale well with large number of multicast groups and sources.

Sources I used to collect my notes on multicast routing algorithm:

Leave a Comment