Section 15.2. Intradomain Multicast Protocols

15.2. Intradomain Multicast Protocols

Intra domain routing protocols carry out the multicast function within domains. The implementation of multicast routing faces the following particular challenges:

• Dynamic change in the group membership

• Minimizing network load and avoiding routing loops

• Finding concentration points of traffic

In practice, several protocols play major roles in establishing multicast connections. The Distance Vector Multicast Routing Protocol (DVMRP) and the Internet Group Management Protocol (IGMP) are the two original protocols forming the early version of the multicast backbone (MBone). Other protocols, such as Multicast Open Shortest Path First (MOSPF), core -based trees (CBT), and protocol-independent multicast (PIM) enhance MBone performance.

15.2.1. Distance Vector Multicast Routing Protocol (DVMRP)

The Distance Vector Multicast Routing Protocol (DVMRP) is one of the oldest multicast protocols. It is based on a concept of exchanging routing table information among directly connected neighboring routers. The MBone topology can enable multiple tunnels to run over a common physical link. Each participating router maintains information about all the destinations within the system. DVMRP creates multicast trees, using the dense-mode algorithm. A multicast router typically implements several other independent routing protocols besides DVMRP for multicast routing, such as RIP or OSPF for unicast routing.

This protocol is not designed for WANs with a large number of nodes, since it can support only a limited number of hops for a packet. This is clearly considered a drawback of this protocol, as it causes packet discarding if a packet does not reach its destination within the maximum number of hops set. Another constraint in this protocol is the periodic expansion of a multicast tree, leading to periodic broadcasting of multicast data. This constraint in turn causes the issue of periodic broadcast of routing tables, which consumes a large available bandwidth. DVMRP supports only the source-based multicast tree. Thus, this protocol is appropriate for multicasting data among a limited number of distributed receivers located close to the source.

15.2.2. Internet Group Management Protocol (IGMP)

The Internet Group Management Protocol (IGMP) is used for TCP/IP between a receiver and its immediate multicast-enabled routers reporting multicast group information. This protocol has several versions and is required on all machines that receive IP multicast. As the name suggests, IGMP is a group-oriented management protocol that provides a dynamic service to registered individual hosts in a multicast group on a particular network.

When it sends an IGMP message to its local multicast router, a network host it in fact identifies the group membership. Routers are usually sensitive to these types of messages and periodically send out queries to discover which subnet groups are active. When a host wants to join a group, the group's multicast address receives an IGMP message stating the group membership. The local multicast router receives this message and constructs all routes by propagating the group membership information to other multicast routers throughout the network.

The IGMP packet format has several versions; Figure 15.4 shows version 3. The first 8 bits indicate the message type : which may be one of membership query , membership report v ₁ , membership report v ₂ , leave group , and membership report v ₃ . Hosts send IGMP membership reports corresponding to a particular multicast group, expressing an interest in joining that group.

Figure 15.4. IGPM packet format

IGMP is compatible with TCP/IP, so the TCP/IP stack running on a host forwards the IGMP membership report when an application opens a multicast socket. A router periodically transmits an IGMP membership query to verify that at least one host on the subnet is still interested in receiving traffic directed to that group. In this case, if no response to three consecutive IGMP membership queries is received, the router times out the group and stops forwarding traffic directed toward that group. (Note that v _i refers to the version of the protocol the membership report belongs to.)

IGMP version 3 supports include and exclude modes. In include mode, a receiver announces the membership to a host group and provides a list of source addresses from which it wants to receive traffic. With exclude mode , a receiver expresses the membership to a multicast group and provides a list of source addresses from which it does not want to receive traffic. With the leave group message, hosts can report to the local multicast router that they intend to leave the group. If any remaining hosts are interested in receiving the traffic, the router transmits a group-specific query. In this case, if the router receives no response, the router times out the group and stops forwarding the traffic.

The next 8 bits, max response time , are used to indicate the time before sending a response report (default, 10 seconds). The Resv field is set to 0 and is reserved for future development. The next field is S flag, to suppress router-side processing. QRV indicates the querier's robustness variable. QQIC is the querier's query interval code. N shows the number of sources, and Source Address [ i ] provides a vector of N individual IP addresses.

15.2.3. Multicast OSPF (MOSPF) Protocol

The Multicast Open Shortest Path First (MOSPF) protocol, an extension to the unicast model of OSPF discussed in Chapter 7, constructs a link-state database with an advertisement mechanism. Let's explore what new features a link-state router requires to become capable of multicast functions.

Link-State Multicast

As explained in Chapter 7, link-state routing occurs when a node in a network has to obtain the state of its connected links and then send an update to all the other routers once the state changes. On receipt of the routing information, each router reconfigures the entire topology of the network. The link-state routing algorithm uses Dijkstra's algorithm to compute the least-cost path.

The multicast feature can be added to a router using the link-state routing algorithm by placing the spanning tree root at the router. The router uses the tree to identify the best next node. To include the capability of multicast support, the link-state router needs the set of groups that have members on a particular link added to the state for that link. Therefore, each LAN attached to the network must have its host periodically announce all groups it belongs to. This way, a router simply detects such announcements from LANs and updates its routing table.

Details of MOSPF

With OSPF, a router uses the flooding technique to send a packet to all routers within the same hierarchical area and to all other network routers. This simply allows all MOSPF routers in an area to have the same view of group membership. Once a link-state table is created, the router computes the shortest path to each multicast member by using Dijkstra's algorithm. This protocol for a domain with n LANs is summarized as follows .

Begin MOSPF Protocol

1. Define: N _i = LAN i in the domain, i ˆˆ{1, 2, ..., n }

   G _j (i) = Multicast group j constructed with connections to N _i

   R _i = Router attached to N _i

2. Multicast groups: R _i maintains all N _j group memberships.

3. Update: Use the link-state multicast whereby each router R _i floods all its multicast group numbers , G _j (i) , to all its directly attached routers.

4. Using the shortest-path tree algorithm, each router constructs a least-cost tree for all destination groups.

5. When it arrives at a router, a multicast packet finds the right tree, makes the necessary number of copies of the packet, and routes the copies.

MOSPF adds a link-state field, mainly membership information about the group of LANs needing to receive the multicast packet. MOSPF also uses Dijkstra's algorithm and calculates a shortest-path multicast tree. MOSPF does not flood multicast traffic everywhere to create state. Dijkstra's algorithm must be rerun when group membership changes. MOSPF does not support sparse-mode tree (shared-tree) algorithm. Each OSPF router builds the unicast routing topology, and each MOSPF router can build the shortest-path tree for each source and group. Group-membership reports are broadcast throughout the OSPF area. MOSPF is a dense-mode protocol, and the membership information is broadcast to all MOSPF routers. Note that frequent broadcasting of membership information degrades network performance.

Example.	In Figure 15.5, each of the five LANs in a certain domain has an associated router. Show an example of MOSPF for multicasting from router R 1 to seven servers located in LANs 1, 2, and 3. Figure 15.5. Use of MOSPF to multicast from router R 1 to seven servers located in two different multicast groups spread over three LANs
Solution.	Multicast groups 1 and 2 are formed . For group 1, the best tree is implemented using copying root R 4 . For group 2, the best tree is implemented using copying root R 7 .

15.2.4. Protocol-Independent Multicast (PIM)

Protocol-independent multicast (PIM) is an excellent multicast protocol for networks, regardless of size and membership density. PIM is "independent" because it implements multicasting independently of any routing protocol entering into the multicast routing information database. PIM can operate in both dense mode and sparse mode . Dense-mode is a flood-and-prune protocol and is best suited for networks densely populated by receivers and with enough bandwidth. This version of PIM is comparable to DVMRP.

Sparse-mode PIM typically offers better stability because of the way it establishes trees. This version assumes that systems can be located far away from one another and that group members are " sparsely " distributed across the system. This protocol for a domain with n LANs is summarized as follows.

Begin PIM Algorithm

1. Define: N _i = LAN i in the domain i ˆˆ{1, 2, ..., n }

   G _j (i) = Multicast group j constructed with connections to N _i

   R _i = The router attached to N _i

2. Multicast groups: R _i maintains all N _j group memberships.

3. Rendezvous router: Using the sparse-mode tree algorithm, each group G _j (i) chooses a rendezvous router.

4. Update: Each Router R _i updates its rendezvous router whenever there is a change in the group.

5. When it arrives at a rendezvous router, a multicast packet finds the right tree and routes the packet.

Sparse-mode PIM first creates a shared tree, followed by one or more source-specific trees if there is enough traffic demand. Routers join and leave the multicast group join and prune by protocol messages. These messages are sent to a rendezvous router allocated to each multicast group. The rendezvous point is chosen by all the routers in a group and is treated as a meeting place for sources and receivers. Receivers join the shared tree, and sources register with that rendezvous router. Note that the shortest-path algorithm made by the unicast routing is used in this protocol for the construction of trees.

Each source registers with its rendezvous router and sends a single copy of multicast data through it to all registered receivers. Group members register to receive data through the rendezvous router. This registration process triggers the shortest-path tree between the source and the rendezvous router. Each source transmits multicast data packets encapsulated in unicast packets to the rendezvous router. If receivers have joined the group in the rendezvous router, the encapsulation is stripped off the packet, and it is sent on the shared tree. This kind of multicast forwarding state between the source and the rendezvous router enables the rendezvous router to receive the multicast traffic from the source and to avoid the overhead of encapsulation.

Example.	In Figure 15.6, the five LANs in a certain domain each have an associated router. Show an example of sparse-mode PIM for multicasting from router R 1 to four servers located in a multicast group spread over LANs 2 and 3. Figure 15.6. Sparse-mode PIM for multicasting from router R 1 to four servers in a multicast group spread over LANs 2 and 3
Solution.	Multicasting is formed with R 3 the associated rendezvous router for this group. Thus, the group uses a reverse unicast path as shown to update the rendezvous router of any joins and leaves . For this group, the multicast tree is implemented using copying root R 7 .

15.2.5. Core-Based Trees (CBT) Protocol

In sparse mode, forwarding traffic to the rendezvous router and then to receivers causes delay and longer paths. This issue can be partially solved in the core-based tree (CBT) protocol, which uses bidirectional trees. Sparse-mode PIM is comparable to CBT but with two differences. First, CBT uses bidirectional shared trees, whereas sparse-mode PIM uses unidirectional shared trees. Clearly, bidirectional shared trees are more efficient when packets move from a source to the root of the multicast tree; as a result, packets can be sent up and down in the tree. Second, CBT uses only a shared tree and does not use shortest-path trees.

CBT is comparable to DVMRP in WANs and uses the basic sparse-mode paradigm to create a single shared tree used by all sources. As with the shared-trees algorithm, the tree must be rooted at a core point. All sources send their data to the core point, and all receivers send explicit join messages to the core. In contrast, DVMRP is costly, since it broadcasts packets, causing each participating router to become overwhelmed and thereby requiring keeping track of every source-group pair. CBT's bidirectional routing takes into account the current group membership when it is being established.

When broadcasting occurs, it results in traffic concentration on a single link, since CBT has a single delivery tree for each group. Although it is designed for intradomain multicast routing, this protocol is appropriate for interdomain applications as well. However, it can suffer from latency issues, as in most cases, the traffic must flow through the core router. This type of router is a bottleneck if its location is not carefully selected, especially when transmitters and receivers are far apart.

15.2.6. Multicast Backbone (MBone)

The first milestone in the creation of a practical multicast platform was the development of the multicast backbone (MBone), which carried its first worldwide event when several sites received audio simultaneously . The multicast routing function was implemented using unicast-encapsulated multicast packets. The connectivity among certain receivers was provided using point-to-point IP-encapsulated tunnels . Figure 15.7 shows an example of tunneling among routers in the early version of MBone. Each tunnel connects two end points via one logical link and crosses several routers. In this scenario, once a packet is received, it can be sent to other tunnel end points or broadcast to local members. The routing in earlier version of MBone was based on DVMRP and IGMP.

Figure 15.7. Tunneling in the multicast backbone