Networking‎ > ‎

Multicasting

Multicasting

1. Introduction to Multicasting 

        Multicast (point-to-multipoint) is a communication pattern in which a source host sends a message to a group of destination hosts, to decrease of the network load.

       Usage:

              a. Stock ticker applications : transmit packets to stations. The packets sent to these stations share a group of links on their paths to their destinations.

              Since multicasting requires the transmission of only a single packet by the source and replicates this packet only if it is necessary (at forks of the multicast delivery tree), multicast transmission can conserve the so much needed network bandwidth.

              b. Resource discovery : Applications (BOOTP, OSPF) in which a host needs to find out whether a certain type of service is available or not.

              c. Datacasting applications : Instead of using a set of point-to-point connections between the participating nodes, multicasting can be used for distribution of the multimedia data to the receivers. In real world stations may join or leave an audio-cast or a video-cast at any time. 

       Making multicast delivery efficient in a packet switching network requires a whole set of new protocols and mechanisms at the network layer.

              a. Multicast addresses must be available that can designate a multicast group as the destination of a datagram.

              In IP multicasting, whenever a multicast message is sent out, a multicast group ID (set of “Class D” IP addresses) specifies the destination group.

              b. There must be mechanisms that allow a host to join and leave a multicast group.

              To solve the problem of Internet-wide routing of multicast messages, hosts needs to join a group using IGMP by informing the multicast router on their subnetwork. Leaving a group is done through IGMP too.

              Whenever a multicast router receive a multicast packet it checks the group ID of the message and forwards the packet only if there is a member of that group in networks connected to it. IGMP provides the information required in the last stage of forwarding a multicast message to its destinations.

              c. There is a need for multicast routing protocols that set up paths, called distribution tree, from the sender to the members of a multicast group. The issues related to setting up multicast distribution trees are referred to as multicast routing. 

        Routers perform two main processes in IP multicast: multicast routing and multicast forwarding.

               a. Multicast routing sets up the distribution tree for a multicast group by setting the content of multicast routing tables. In multicast, a routing table may list multiple next hop addresses for a routing table entry.

               b. As in unicast, forwarding refers to the processing of an incoming datagram, the routing table lookup, and the transmission on an outgoing interface. When a multicast packet arrives at a router, the router performs a lookup in the multicast routing table for a matching entry. The router forwards one copy of the packet to each next hop address in the matching routing table entry.

       However, for delivering a multicast packet from the source to the destination nodes on other networks, multicast routers need to exchange the information they have gathered from the group membership of the hosts directly connected to them. There are many different algorithms such as "flooding", "spanning tree", "reverse path broadcasting", and "reverse path multicasting" for exchanging the routing information among the routers. Some of these algorithms have been used in dynamic multicast routing protocols such as Distance Vector Multicast Routing Protocol (DVMRP), Multicast extension to Open Shortest Path First (MOSPF), and Protocol Independent Multicast(PIM).

       Based on the routing information obtained through one of the protocols, whenever a multicast packet is sent out to a multicast group, multicast routers will decide whether to forward that packet to their network(s) or not.

       Finally the leaf router will see if there is any member of that particular group on its physically attached networks based of the IGMP information and decides whether to forward the packet or not.

2. IP Multicast 

A central notion of IP multicast is the IP multicast [PROJECT:Class D] destination address. Each multicast address specifies a multicast group. A host joins a multicast group by starting to listen to packets sent to the IP address associated with the multicast group. There is no separate mechanism for creating an IP multicast group.

IP multicast groups are open and dynamic, in the sense that every host can join and leave any multicast group. There is no access control for joining a multicast group. The size of a multicast group is not limited. A host can join multiple multicast groups at a time, and on each host there may be multiple applications that receive packets sent to an IP multicast address.

A multicast packet is an IP datagram that has an IP multicast address as destination address. A multicast packet is delivered to all hosts that are members the multicast group designated by the IP multicast address. A host can transmit multicast packets to any multicast group. A host does not need to be a member of a multicast group to transmit multicast packets to that group. Also, multiple hosts can send to a multicast group at the same time.

A notable difference between multicast and unicast on the Internet is that only UDP is available as transport protocol for multicast applications. There is no multicast version of TCP.

For applications that require a reliable data transfer, for example, one-to-many file transfer applications, the mechanisms that ensure a reliable data transfer, such as sequence numbers, timers and retransmissions, must be provided by the application layer.



Protocol Layers for Unicast and Multicast

3. IP Multicast Addressing

A Class D IP address is assigned to a group of nodes defining a multicast group. The most significant four bits of Class D addresses are set to "1110". The 28-bit number following these four bits is called "multicast group ID".

Reserved Blocks of Multicast Addresses:                                              

224.0.0.0 to 224.0.0.255 - Routing Protocols, Topology Discovery, TTL is 1

239.0.0.0 to 239.255.255.255 - site-local "administratively scoped" applications

224.0.0.1 - all hosts and routers on this subnet

224.0.0.2 – all routers on this subset

Prefix 233.0.0.0/8 – Owners of Autonomous system, IP 1st byte 233, 2nd & 3rd byte 16nit AS no, 4th byte designate 256 reserved multicast address.



Format of Class D IP address

A multicast datagram (packet) is delivered to the group members with the same best-effort reliability as a unicast IP packet. Loss of packet and out of order delivery is possible.

Like unicast IP packets, there should be a MAC-layer address to which the IP multicast address maps. The IANA has reserved a set of the IEEE-802 MAC-layer addresses for multicast packets, ranging from 01:00:5E:00:00:00 to 01:00:5E:7F:FF:FF (hex). An IP multicast address can be mapped to an IEEE-802 address by placing the least-significant 23 bits of the IP multicast address into the least-significant 23 bits of the MAC-layer multicast address. Mapping of a IP multicast address to a IEEE-802 MAC-layer address is illustrated in below.

It should be noted that because of the mapping procedure there will be 32 different multicast addresses mapped to the same IEEE-802 address.



Mapping of Class D IP address into Ethernet multicast address

4. IGMP : Receivers joining the Multicast Group

Hosts willing to receive multicast messages (packets) need to inform their immediately-neighboring routers that they are interested in receiving multicast messages sent to certain multicast groups, through IGMP protocol. The router (elected querier incase of multiple routers in LAN) checks periodically if group members are still alive, using IGMP.

The leaf router forwards the multicast packets if at-least one group member exist in subnet else discards the packet.

a. Joining a Group


Host Sends IGMP Report to join the group

b. Maintaining a  Group


Router sends periodic Queries to 224.0.0.1

One member per group per subnet reports

Other members suppress reports

c. Leaving a Group (IGMPv1)


Hosts quietly leaves group

Router sends 3 General Queries  (60 secs apart)

No IGMP Report for the group is received

Group times out (Worst case delay ~=3 minutes)

d. Leaving a Group (IGMPv2)


Hosts sends Leave message to 224.0.0.2

Router sends Group specific query to 224.1.1.1

No IGMP Report is received within ~3 secs

Group 224.1.1.1 times out

e. IGMPv3 : Enables hosts to listen only to a specified subnet of the hosts sending to the group


f. IGMP message format




5. Protocol Independent Multicast

PIM is a multicast routing protocol, concerned with setting up distribution trees that provide a path from the multicast sources to multicast group members.

PIMv2 protocol messages are encapsulated in IP datagrams with protocol number 103. PIM messages can be sent as unicast or multicast packets. When sent as multicast packets, PIM uses the multicast IP address 224.0.0.13, which is reserved as the ALL-PIM-Routers group.



PIMv2 Message Format





                        PIMv2 Message Types

All messages have a four byte long header, which is followed by type-specific fields. The first field of the header is the version field, which is set to 2 in PIMv2. The Type field specifies one of the message types. Message types Hello, Join/Prune, Bootstrap, Assert, and Graft are sent as multicast packets to address 224.0.0.13 with the TTL field in the IP header set to 1. Note that the same message type is used for Join and Prune messages. All other message types are sent as unicast messages. The third byte of the header is unused. The last two bytes of the header are a checksum. We refer to10 for a description of the type-specific fields of PIM messages.

6. PIM Sparse Mode (PIM-SM)

PIM-SM initially builds a core-based tree routing protocol for a multicast group, which is shared by all sources. When the traffic from a source exceeds a threshold, PIM constructs a source-based tree for that source.

We next discuss how the core-based tree is constructed, how a source transmits data, and how PIM-SM switches to a source-based tree. In PIM-SM, a core router is called rendezvous point (RP) and a core-based tree is called rendezvous-point tree (RPT). The RPT in PIM-SM is unidirectional, that is, multicast packets are forwarded only downstream in the RPT and sources send multicast packet to the RP. The RPs can either be statically configured or it can be dynamically determined via an advertisement mechanism, which is part of PIM-SM. Also, a network can have a different RP for each multicast group. To keep the discussion of PIM-SM concise, we assume that there is only one statically configured RP in the network.

In PIM a router can have both an (S, G) and an (*, G) entry for the same multicast group. In this case, when a packet arrives with source address S for group G the router first tries to find a match in the routing table for an entry (S, G). If no match is found, the router looks for an (*, G) entry. If no matching entry is found, the router tries to forward the packet to the RP for that group. If no RP is known, the datagram is discarded. When a match is found, the router performs an RP check, that is, it verifies that the datagram was received on the incoming interface that is listed in the routing table entry, and then forwards the data to the outgoing interface list.


            PIM-SM : H2 Joins                                                       PIM-SM : H3 Joins

When a host joins a multicast group, the DR for that host sends a Join message on the reverse path to the RP. The DR for host H2, router R3, sends a Join(*, G) message to R2, its RPF neighbor for the RP. Assuming that R2 does not have a multicast entry for (*, G), when R2 receives the Join message, it sets up a (*, G) routing table entry, and sends a Join(*, G) message to R5. When the RP receives the Join message, it adds the outgoing interface that connects to R2 to the routing table entry for (*, G). As with Prune messages, Join messages are sent periodically, about once per minute. The routing entries created with a Join message have a limited lifetime, and a router deletes an entry if no new Join message has been received for some time.

When host H3 joins the multicast group G, router R4 sends a Join(*, G) message to R2. Since R2 already has an entry for (*, G), the R2 does not forward the Join message to the RP, and simply adds interface I3 to the outgoing interface list for the (*, G) routing table entry.



                                                Data transmission in PIM-SM

PIM Register Message

Next we explore data delivery in an RPT. When a source wants to transmit data to a multicast group, the DR for the source sends a Register message to the RP of the group, and encapsulates the multicast packet in the Register message. The RP that receives a Register message extracts the multicast packets, and sends the multicast packet downstream in the RPT. If the RPT does not have any downstream nodes, the RP discards the multicast packet.

PIM Join Message

When the Register message with the first datagram message arrives at the RP, the RP sends a Join(S,G) message to the source. The Join message travels from the RP on the reverse shortest path and sets up a (S, G) routing table entries on all routers between the source and the RP.

PIM Register-Stop Message

When the Join message reaches the DR of the source, the DR sends multicast packets from the source to the RP. Once the RP receives the multicast packets from the reverse path, it sends a Register-stop message to the DR to stop the transmission of encapsulated datagrams. For a certain time, between the reception of the Join message and the Register-stop message, the DR of the source receives two copies of each multicast packet from the source, one encapsulated in a Register message and one native multicast packet.

Refer to Figure, host S1 sends a multicast packet to its DR, R1. R1 encapsulated the datagram in a Register message, and sends the message as a unicast message to the RP. The RP extracts the multicast packet from the register message, and forwards the message in the RPT. In the figure, we assume that only host H1 has joined the multicast group G, and the RPT consists of the path R5‡ R2‡ R3. Then, the RP sends a Join(S1,G) to the DR of the source. When R1 receives the Join message it sets up an (S1, G) routing table entry, and begins forwarding native multicast packets, that is, regular IP datagrams with the destination address set to G, to the RP. R1 continues sending multicast packets encapsulated in Register messages to the RP. As soon, as the first native multicast packet reaches the R5, R5 sends a Register-stop message to R1. This stops the transmission of Register messages with encapsulated multicast packets.

Comments