Multicast algorithms are used to establish paths through the network. These paths allow multicast traffic to effectively reach all group members.
Each algorithm should address the following set of requirements:
- The algorithm must route data only to group members.
- The algorithm must optimize the path from source to destinations.
- The algorithm must maintain loop-free routes.
- The algorithm must provide scalable signaling functions used to create and
maintain group membership. - The algorithm must not concentrate traffic on a subset of links.
Several algorithms have been developed for use in multicast routing protocols.
These algorithms have varying levels of success addressing these design
requirements. We review two algorithms in the following sections.
In this article
Reverse Path Forwarding Algorithm
The reverse path forwarding (RPF) algorithm uses a multicast delivery tree to forward datagrams from the source to each member in the multicast group. As shown in the next image, packets are replicated only at necessary branches in the delivery tree.
To track the membership of individual groups, trees are calculated and updated dynamically.
The algorithm maintains a reverse path table used to reach each source. This table maps every known source network to the preferred interface used to reach the source. When forwarding data, if the datagram arrives through the interface used to transmit datagrams back to the source, the datagram is forwarded through every appropriate downstream interface. Otherwise, the datagram arrived through a sub-optimal path and is discarded. Using this process, duplicate packets caused by network loops are filtered.
The use of RPF provides two benefits:
- RPF guarantees the fastest delivery for multicast data. In this configuration, traffic follows the shortest path from the source to each destination.
- A different tree is computed for each source node. Packet delivery is
distributed over multiple network links. This results in a more efficient use of network resources.
Center-based tree algorithm
The center-based tree (CBT) algorithm describes another method to determine optimum paths between members of a multicast group.
The algorithm describes the following steps:
- A center point in the network is chosen. This fixed point represents the center of the multicast group.
- Each recipient sends a join request directed towards the center point. This is accomplished using an IGMP membership report for that group.
- The request is processed by all intermediate devices located between the
multicast recipient and the center point. If the router receiving the request is already a member of the tree, it marks one more interface as belonging to the group. If this is the first join request, the router forwards the request one step further toward the source.
This procedure builds a delivery tree for each multicast group. The tree is
identical for all sources. Each router maintains a single tree for the entire group.
This contrasts with the process used in the RPF algorithm. The RPF algorithm builds a tree for each sender in a multicast group.
Because there is no requirement for the source to be a member of the group, multicast packets from a source are forwarded toward the center point until they reach a router belonging to the tree. At this stage, the packets are forwarded using the multicast processing of the center-based tree.
The disadvantage to the center-based tree algorithm is that it might build a
suboptimal path for some sources and receivers.
Multicast Routing Protocols
A number of multicast routing protocols have been developed using these algorithms:
- Distance Vector Multicast Routing Protocol (DVMRP)
- Multicast OSPF (MOSPF)
- Protocol Independent Multicast (PIM)
Our goal is to develop each of these algorithms in separate articles.
