Multicast

So far, we have concentrated on point-to-point communication or unicast, where a single source is sending data to a single receiver. Many applications however require that data be sent simultaneously to several receivers. The best example of such a requirement is teleconferencing between a group of three or more people. When one of the members of the group is speaking, his/her voice must be delivered to all other group members: this is called point-to-multipoint communication, or multicast.

Figure 1.8: Multicast achieved through unicast. Member $A$ sends the same data three times to members $B$, $C$ and $D$.

A simple solution to implement multicasting is to send the same data in turn to all other members of the conference. In other words, point-to-multipoint communication can be achieved through multiple point-to-point communications. However, such a solution is expensive in terms of bandwidth utilization: the same information must be sent $n-1$ times if the teleconference gathers $n$ people, thus wasting bandwidth. In Figure 1.8, $A$ sends the same data three times, wasting two thirds of the bandwidth on the leftmost link. A more efficient support of multicast in a network sets up a multicast routing tree, where the switches are the nodes of the tree and the links are the edges of the tree. Each switch that is a bifurcation of the tree duplicates packets to each outgoing link. By forwarding data on this tree structure and duplicating data at intermediate nodes of the tree, the same information flows on each link of the tree only once, hereby saving bandwidth. Multicast routing trees can be either Shortest Path Trees or Core Based Trees. We review each of these structures in the next subsection.

Multicast routing tree structure

In a shortest path tree structure, each possible source of a multicast group is the root of a separate tree. The edges of the tree are network links, nodes are routers, and leaves are members of the multicast group. If the group contains $n$ possible sources, then $n$ trees must be built. A shortest path tree is obtained by computing the shortest path (in terms of some link cost -- usually the cost is one for each link) between the source and each other group member. Figure 1.9 shows examples of shortest path trees rooted at two different nodes in a multicast group of four nodes (Figure 1.9(a)). The two shortest path trees do not use the same set of links, but all paths from node $A$ to other nodes (Figure 1.9(b)) and from node $B$ to other nodes (Figure 1.9(c)) use a minimum number of links.

Figure 1.9: Shortest path trees. This figure only shows the shortest path trees rooted at $A$ and $B$.

In center-based or core based tree multicast, all participants are leaves of the same, unique shared tree. All the traffic generated by the multicast group flows through a special node on this tree, called center or core, as shown in Figure 1.10. Contrary to shortest path trees, the path between two group members is not guaranteed to be the shortest. For instance, in Figure 1.10, data sent by node $A$ uses five links before reaching $C$ when the shortest path between $A$ and $C$ is only three links long. It can be shown that a particular core based tree, called Steiner Tree [30] is optimal in terms of bandwidth utilization. However, it can also be proven that computing Steiner trees is NP-hard [42]. A more thorough comparison between shortest path trees and core based trees can be found in [68].

Figure 1.10: Center-based multicast routing tree. The multicast group shares a single tree.

In Section 1.1, we discussed link failures with unicast traffic and explained that traffic has to be rerouted to a different path to avoid a failed link. With datagram packet switching, rerouting is performed automatically online after a link fails while traffic engineering techniques allow to pre-plan backup paths in circuit switching and VC-switching. A multicast group member is dropped from a multicast group when this member cannot reach or be reached by the core or source of the tree anymore. In order to protect a multicast routing tree from any single link failure, it is possible to pre-plan a different backup path between each group member and the source or the core of a multicast routing tree. For instance, in Figure 1.11(a), a core-based tree centered in $C$ with three group members $A$, $B$ and $D$ is fully protected by three pre-planned backup paths. If any single link in the tree fails, the connectivity between $C$ and any dropped group member is restored by rerouting traffic over the backup path between $C$ and the dropped group member. However, pre-planning involves additional computations, circuit advertising, and possibly resource reservation on the backup path to make sure that the rerouted traffic will not overload the backup path. Backup path pre-planning is therefore costly in terms of computations and bandwidth reservation. Thus, it is desirable to limit the number of pre-planned backup paths in a network. In Figure 1.11(b), we show how only two backup paths are required to protect the multicast routing tree from any single link failure. If link $(CA)$ fails, traffic between $A$ and $C$ is rerouted over the leftmost backup path. If link $(CB)$ fails, then multicast traffic can still reach node $C$ via $B$ and the rightmost backup path. The same backup path is also used when link $(CD)$ fails, hereby keeping node $D$ reachable from any other member of the tree. Therefore, a single backup path can be used to protect the multicast routing tree from different link failures.

Figure 1.11: Pre-planning backup paths in a multicast routing tree. It is possible to protect the multicast routing tree with three group members from any single link failure with only two pre-planned backup paths.

Multicast with IP

Multicast with IP has been studied since 1988 [21] and a certain range of IP addresses (all addresses beginning with the four bits 1110, or, in dotted-decimal notation, 224.0.0.0 to 239.255.255.255) has been allocated for multicast communications. An IP multicast address is an identifier for a multicast group. IP multicast is defined for UDP only, an unreliable datagram oriented transport protocol.

Since a multicast routing tree can span over the whole Internet, establishing a multicast routing tree and then routing multicast packets is the main issue encountered by IP multicast. Another issue is that few routers are multicast-enabled in the Internet. IP multicast is achieved with two protocols.

First, a signaling protocol like IGMP [20] [29] runs between end hosts and routers and is responsible for managing host group membership. Multicast groups are open and dynamic. To join a multicast group, a host needs to know the IP address of the group and send an IGMP message to its next-hop router; on the other hand, a host can leave a group at any time by sending the appropriate IGMP message.

Second, multicast routing protocols run between routers to create and manage multicast routing trees. Many multicast routing protocols have been designed in the last decade. The Distance Vector Multicast Routing Protocol (DVMRP [67]) builds source-rooted trees using a Distance Vector protocol, where each router is able to determine the outgoing link of a packet based on local information only. MOSPF [48] extends a unicast routing protocol, OSPF. MOSPF also builds source-rooted trees, but because OSPF is a link-state routing protocol, each OSPF router knows the full topology of the network. Thus, MOSPF can build shortest path trees using the well-known Dijkstra shortest path algorithm [24]. One protocol uses core based trees: Core Based Tree or CBT [9]. Finally, PIM [27] can build both types of trees. In multicast groups that contain many receivers (PIM Dense Mode), PIM builds shortest path trees. Conversely, with smaller groups (PIM Sparse Mode), PIM builds core based trees.

Last but not least, IP routers are able to duplicate packets. Routers with three or more links involved in a multicast routing tree must duplicate packets before they can forward them simultaneously on several links.

Although IP multicasting is well defined and standardized, it is not widely deployed in the Internet [26] mainly because of current multicast routing protocols scalability issues. We now present how VC-switching technologies, ATM and MPLS, support multicasting.

Multicast with ATM

Three different approaches have been proposed to add multicast support to ATM. The first one, the usage of point-to-multipoint virtual circuits to carry multicast traffic [2], requires cell duplication by switches and a specific signaling protocol to advertise the point-to-multipoint virtual circuits. In [32], the authors make a survey of the different techniques available to duplicate cells with specific hardware. However, the current standard ATM signaling protocol does not support point-to-multipoint virtual circuits implemented in hardware [7]. Moreover, we have seen that ATM switches perform Segmentation and Reassembly to fit IP packets into ATM cells. With AAL5 [36], the main adaptation layer currently deployed in ATM networks, cells arriving at a destination switch are identified solely by a virtual circuit number. ATM switches that receive multicast cells have no means of knowing the origin of a cell. Therefore, ATM switches cannot reassemble IP packets contained in cells from different sources that have been interleaved by the ATM network [18].

The other two ATM multicast approaches emulate point-to-multipoint virtual circuits with point-to-point virtual circuits [25]. In the multicast virtual circuit mesh model, every member of a multicast group establishes a point-to-point virtual circuit to every other member of the group. This approach is not scalable with the number of multicast group members. Indeed, when a node wants to join or leave a group, every group member must create or terminate a virtual circuit to the new member. Third, in the Multicast Server model (MCS), a centralized server is responsible for handling multicast traffic. For instance, in LANE [65], all multicast traffic on an ATM network is sent to a Broadcast and Unknown Server (BUS) which establishes a point-to-point virtual circuit with all other members of the group. While MCS does not have the scalability issue of mesh virtual circuits, the BUS is a single point of failure and can become a bottleneck in the network.

The Multicast Address Resolution Server (MARS) architecture [5] implements both mesh virtual circuits and MCS. With MARS, members of a multicast group must contact a MARS server to join or leave a group. Then, the MARS server can either act as an ARP server and let a joining host establish a point-to-point virtual circuit to all other group members, or act as the center of a core based tree and create a unicast path to every member of the group in order to replace one point-to-multipoint virtual circuit by several point-to-point virtual circuits. In summary, current implementations of multicast with ATM only emulate multicasting with unicast virtual circuits and therefore do not have efficient multicast support.

Multicast with MPLS

Although MPLS natively supports multicasting in its design, MPLS multicast has not been given a lot of attention and is still at the proposal stage [56] [71]. As a side note, Alcatel stated to have an implementation running as early as 1999 [17]. This prototype of multicast over MPLS uses a proprietary signaling protocol or proprietary extensions to an existing signaling protocol.

Multicast and unicast traffic require different types of processing from routers. For instance, IP identifies multicast packets by looking at the multicast address range. In MPLS, unicast and multicast packets have already been assigned a different type code in the link-layer header [61]. Therefore, MPLS routers know whether a packets is from a unicast or a multicast flow.

MPLS multicast is fundamentally different from ATM multicast. First, MPLS routers do not need to perform Segmentation and Reassembly, thus the aforementioned frame interleaving issue does not exist in MPLS multicast networks. Second, MPLS routers are mainly IP routers enhanced to support MPLS. The packet duplication mechanism that is implemented in IP routers to support IP multicast can be used to duplicate MPLS packets. MPLS routers at the bifurcation of a multicast routing tree duplicate packets and send copies of the same packet on different outgoing links. Each copy of an incoming MPLS multicast packet is assigned a different label before it is forwarded on an outgoing link. Furthermore, when a packet is duplicated, one copy can be forwarded using MPLS (the label of the incoming packet is swapped and the packet is sent to another MPLS router) and another copy can be sent using IP (the label is incoming is popped and the packet is forwarded to an IP router). Therefore, a multicast MPLS router can be at the same time a LSR and a LER for the same multicast virtual circuit.

Each member of a multicast group can build a shortest path tree multicast LSP to reach all other members. Alternatively, all members of a group can be leaves of a common core based tree whose center can be any node of the network. A signaling protocol performs multicast LSP establishment and termination, online or offline. MPLS can rely on an IP multicast routing protocol to build the tree online, and then create a multicast LSP that matches the IP multicast routing tree. The other alternative is to have MPLS multicast LSPs built offline by a dedicated server. This solution may be preferable in situations where substantial offline computing is necessary. The dedicated server computes a multicast routing tree and uses signaling protocol messages to advertise the multicast LSP. This particular form of routing where a LSP is fully defined and advertised by a particular node is called Explicit Routing. Explicit Routing is a traffic engineering technique which is a novelty of MPLS over ATM. However, the main issue with MPLS multicast is that no signaling protocol currently supports MPLS multicast virtual circuits (multicast LSPs).