DC - Chapter - 6 : Group Communication

6.1 Unicasting versus Multicasting

In the IPC data is sent from a source process, the sender, to one destination process, the receiver. This form of IPC can be called unicasting, where the information or message is sent to a single receiver, as opposed to multicasting, where the information is sent to multiple receivers. Unicasting provides one-to-one IPC whereas multicasting supports one-to-many IPC as shown in figure 6.1

 

Fig 6.1 Unicast IPC v/s Multicast IPC

The majority of network services and network applications use unicast for IPC, whereas multicasting is useful for applications such as online conferences, interactive distance learning, and can be used for applications such as online auction.

In an application or network service which makes use of multicasting, a set of processes form a group, called a multicast group.  Each process in a group can send and receive message to/from other participating process in the group.

In an application such as online conferencing, a group of processes interoperate using multicasting to exchange audio, video, and/or text data.

6.2 An Archetypal Multicast API

An application program interface that supports multicasting must provide the following primitive operations:

— Join – This operation allows a process to join a specific multicast group.  A process that has joined a multicast group can receive all multicast messages addressed to the group. A process may be a member of one or more multicast groups at any one time.

— Send – This operation allows a process to send a message to all processes currently participating in a multicast group.

— Receive –This operation allows a member process to receive messages sent to a multicast group.

— Leave –This operation allows a process to leave a multicast group and stop receiving any multicast addressed to the group.

6.3 Connectionless versus Connection-Oriented Multicast

A basic multicast mechanism is connectionless. The reason is obvious if you consider the one-to-many nature of multicasting. In a group of n processes, if a connection is to be established between a sender and every other process in the group, a total of n-1 connections will be needed. Moreover, each of the n processes may potentially be a sender, so that each process must maintain a connection with every other process, resulting in a total of n * (n - 1) or roughly n² connections. If n is large, the sheer number of such connections will become prohibitively expensive.

Moreover, connectionless IPC is appropriate for a common type of multicast applications like audio or video data transmission among processes in real time. When audio or video data is transmitted, the reduction in latency provided by connection less communication outweighs the advantages offered by connection-oriented communication. For example when data for animation is sent it is more acceptable for a receiver to experience a distortion in the image of an occasional frame than a frequent, perceptible delay between consecutive frames.

6.4 Reliable Multicast v/s Unreliable Multicast

When a multicast message is sent by a process, the run-time support of the multicast mechanism is responsible for delivering the message to each process currently in the multicast group.

Due to factors such as failures of network links, network hosts, routing delays or any other software and hardware problems, the time between when a multicast message is sent and when it is received may vary among the recipient processes.

In some cases the correct message is received by all processes and in other cases, some of the participants may not receive the message at all.

Sometimes the messages may be received by other processes in the group in a corrupted form.  Such a system is said to provide unreliable multicast.

On the other hand a multicast system which guarantees that each message is eventually delivered to each process in the group in uncorrupted form is said to provide reliable multicast. In such a system, each message sent by a process can be assumed to be delivered in a non corrupted form to all processes in the group eventually.

Some applications, such as video conferencing or database applications can tolerate an occasional miss or misordering of messages for which such anomalies are unacceptable. 

Therefore, when employing a multicasting mechanism for an application, it is important that you choose one with the characteristics appropriate for your application. Otherwise, measures will need to be provided in the logic of the application in order to handle the anomalies that may occur in message delivery.

 6.5 Classifications of reliable multicast

The definition of reliable multicast places no restriction on the order in which the messages are delivered to each individual process: Each process may receive the messages in any permutation of the order in which those messages were sent. For applications where the order of message delivery is significant, it is helpful to further classify reliable multicast systems as described below.

Unordered Multicast

An unordered reliable multicast system provides no guarantee on the delivery order of the messages.

Example: Processes P₁, P₂, and P₃ have formed a multicast group.  Further suppose that three messages, m₁, m₂, m₃ have been sent to the group. Then an unordered reliable multicast system may deliver the messages to each of the three processes in any of the 3! = 6 permutations (m1-m2-m3, m1-m3-m2, m2-m1-m3, m2-m3-m1, m3-m1-m2, m3-m2-m1).  

FIFO multicast

A system which guarantees that the delivery of the messages adhere to the following condition is said to provide FIFO (first-in-first-out) or send-order multicast:

If process P sent messages m_i and m_j, in that order, then each process in the multicast group will be delivered the messages m_i and m_j, in the same order.

Suppose P₁ sends messages m₁, m₂, and m₃ in order, then each process in the group is guaranteed to have those messages delivered in that same order: m₁, m₂, then m₃.

Note that FIFO multicast places no restriction on the delivery order among messages sent by different processes.

To illustrate the point, let us use a simplified example of a multicast group of two processes: P₁ and P₂. Suppose P₁ sends messages m₁₁ then m₁₂, while P₂ sends messages m₂₁ then m₂₂.  Then a FIFO multicast system can deliver the messages to each of the two processes in any of the following orders:

m₁₁-m₁₂-m₂₁-m₂₂,  m₁₁-m₂₁-m₁₂-m₂₂,  m₁₁-m₂₁-m₂₂-m₁₂,

m₂₁-m₁₁-m₁₂-m_22,  m₂₁-m₁₁-m₂₂-m₁₂,  m₂₁-m₂₂-m₁₁-m₁₂.

Causal Order Multicast

A multicast system is said to provide causal multicast if its message delivery satisfies the following criterion:

If message m_i causes (results in) the occurrence of message m_j, then m_i will be delivered to each process before m_j.  Messages m_i and m_j are said to have a causal or happen-before relationship, denoted m_i -> m_j.  The happen-before relationship is transitory: if m_i -> m_j and m_j -> m_k, then m_i -> m_j -> m_k.   In this case, a causal-order multicast system guarantees that these three messages will be delivered to each process in the order of m_i, m_j, then m_k.

For example suppose three processes P₁, P₂, and P₃ are in a multicast group.  P₁ sends a message m₁, to which P₂ replies with a multicast message m₂. Since m₂ is triggered by m₁, the two messages share a causal relationship of m₁-> m_2.  Suppose the receiving of m₂ in turn triggers a multicast message m₃ sent by P₃, that is, m₂-> m_3.  The three messages share the causal relationship of m₁-> m₂-> m₃.  A causal-order multicast message system ensures that these three messages will be delivered to each of the three processes in the order of m₁- m_2- m₃.

As a variation of the above example, suppose P₁ multicasts message m₁, to which P₂ replies with a multicast message m₂, and independently P₃ replies to m₁ with a multicast message m₃.  The three messages now share these causal relationships: m₁ -> m₂ and m₁ -> m₃.  A causal-order multicast system can delivery these message in either of the following orders:

   m₁- m₂- m₃

   m₁- m₃- m₂

In such a system, it is not possible for the messages to be delivered to any of the processes in any other permutation of the three messages, such as m₂- m₁- m₃ or m₃- m₁- m₂, the first of these violates the causal relationship m₁ -> m₂, while the second permutation violates the causal relationship m₁ -> m₃.

Atomic order multicast

In an atomic-order multicast system, all messages are guaranteed to be delivered to each participant in the exact same order.  Note that the delivery order does not have to be FIFO or causal, but must be identical for each process. 

Example:

P₁ sends m₁, P₂ sends m₂, and P₃ sends m₃.

An atomic system will guarantee that the messages will be delivered to each process in only one of the six orders:

  m₁- m₂- m₃,   m₁- m₃- m₂,     m₂- m₁ - m₃,

  m₂- m₃- m₁,   m₃- m₁- m₂,     m₃- m₂- m₁.

Consider an example for this:    

P₁ sends m₁ then m₂.

P₂ replies to m₁ by sending m₃.

P₃ replies to m₃ by sending m₄.

Although atomic multicast imposes no ordering on these messages, the sequence of the events dictates that P₁ must be delivered m₁ before sending m₂.  Likewise, P₂ must receive m₁ then m₃, while P₃ must receive m₃ before m₄.  Hence any atomic delivery order must preserve the order m_1- m_3- m₄. The remaining message m₂ can however be interleaved with these messages in any manner. Thus an atomic multicast will result in the messages being delivered to each of the processes in one of the following orders:  m_1- m_2- m_3- m_4, m_1- m_3- m_2- m₄ or m_1- m_3- m_4- m_2.  For example, each process may be delivered the messages in this order m_1- m_3- m_2- m_4.

6.6 The Java Basic Multicast API

At the transport layer, the basic multicast supported by Java is an extension of UDP (the User Datagram Protocol), which, as you recall, is connectionless and unreliable.  For the basic multicast, Java provides a set of classes which are closely related to the datagram socket API classes.

There are four major classes in the API, the first three of which we have already seen in the context of datagram sockets.

1. InetAddress:  In the datagram socket API, this class represents the IP address of the sender or receiver. In multicasting, this class can be used to identify a multicast group.
2. DatagramPacket: As with datagram sockets, an object of this class represents an actual datagram; in multicast, a Datagram Packet object represents  a packet of data sent to all participants or received by each participant in a multicast group.
3. DatagramSocket: In the datagram socket API, this class represents a socket through which a process may send or receive data.
4. MulticastSocket: A MulticastSocket is a DatagramSocket, with additional capabilities for joining and leaving a multicast group.  An object of the multicast datagram socket class can be used for sending and receiving IP multicast packets.

 6.7 IP Multicast Addresses

Instead of a single process, a multicast datagram is meant to be received by all the processes that are currently members of a specific multicast group.  Hence each multicast datagram needs to be addressed to a multicast group instead of an individual process.

The Java multicast API uses the Internet Protocol (IP) multicast addresses for identifying multicast groups. 

In IPv4 a multicast group is specified by

           i.      a class D IP address combined with

            ii.   a standard UDP port number.

Class D IP addresses are those with the prefix bit string of 1110, and hence these addresses are in the range of 224.0.0.0 to 239.255.255.255, inclusive.  Excluding the four prefix bits, there are 32-4=28 remaining bits, resulting in an address space of 2²⁸; that is, approximate 268 million class D addresses are available, although the address 224.0.0.0 is reserved and should not be used by any application.

An application which uses the Java multicast API must specify at least one multicast address for the application.  To select a multicast address for an application, there are the following options:

1. Obtain a permanently assigned static multicast address from IANA: Permanent addresses are limited to global, well-known Internet applications, and their allocations are highly restricted.

2.   Choose an arbitrary address, assuming that the combination of the random address and port number will not likely be in use.

3.   Obtain a transient multicast address at runtime; such an address can be received by an application through the Session Announcement Protocol.   

6.8 Operations in a Multicast group

Joining a Multicast Group

To join a multicast group at IP address m and UDP port p, a MulticastSocket object must be instantiated with p, then the object’s joinGroup method can be invoked specifying the address m:

//Join a Multicast group at IP address 239.1.2.3 and port 3456

InetAddress group = InetAddress.getByName("239.1.2.3");

MulticastSocket s = new MulticastSocket(3456);

s.joinGroup(group);    

Sending to a multicast group

A multicast message can be sent using syntax similar with the datagram socket API.

String msg = "This is a multicast message.";          

InetAddress group = InetAddress.getByName("239.1.2.3");

MulticastSocket s = new MulticastSocket(3456);

s.joinGroup(group);   

DatagramPacket hi = new DatagramPacket(msg.getBytes( ), msg.length( ),group,

  3456);

s.send(hi);

Receiving messages in a multicast group

A process that has joined a multicast group may receive messages sent to the group using syntax similar to receiving data using a datagram socket API.

 byte[ ] buf = new byte[1000];

 InetAddress group = InetAddress.getByName("239.1.2.3");           

 MulticastSocket s = new MulticastSocket(3456);             

 s.joinGroup(group);               

 DatagramPacket recv = new DatagramPacket(buf, buf.length);            

 s.receive(recv);

Leaving a multicast group

A process may leave a multicast group by invoking the leaveGroup method of a MulticastSocket object, specifying the multicast address of the group. 

s.leaveGroup(group);

6.9 Time-to-live

The runtime support for a multicast API often employs a technique known as message propagation, whereby a packet is propagated from a host to a neighboring host in an algorithm which, when executed properly, will eventually deliver the message to all the participants. 

Under some anomalous circumstances, however, it is possible that the algorithm which controls the propagation does not terminate properly, resulting in a packet circulating in the network indefinitely which causes unnecessary overhead on the systems and the network.

To avoid this occurrence, it is recommended that a “time to live” parameter be set with each multicast datagram. The time-to-live (ttl) parameter, when set, limits the count of network links or hops that the packet will be forwarded on the network.

Setting the “time-to-live”

String msg = "Hello everyone!";

InetAddress group = InetAddress.getByName("224.0.0.1"); 

MulticastSocket s = new MulticastSocket(3456); 

s.setTimeToLive(1);  // set time-to-live to 1 hop

DatagramPacket hi = new DatagramPacket(msg.getBytes( ), msg.length( ),group,

  3456);                              

s.send(hi);

The value specified for the ttl must be in the range 0<=ttl<=255; an IllegalArgument Exception will be thrown otherwise.

The recommended ttl settings are:

—  0 if the multicast is restricted to processes on the same host

—  1 if the multicast is restricted to processes on the same subnet

—  32 if the multicast is restricted to processes on the same site

—  64 if the multicast is restricted to is processes on the same region

—  128 is if the multicast is restricted to processes on the same continent

—  255 is the multicast is unrestricted

6.10 Reliable Multicast API

The Java basic Multicast API provides unreliable multicast which does not guarantee the delivery of messages to any of the receiver participants.

If you run your processes on one host or on hosts on one subnet, you are not likely to observe any loss of messages or scrambling in the delivery order of the messages. These anomalies are more likely when the participating hosts are remotely connected, due to network failures or routing delays.

There are applications for which unreliable multicasting is unacceptable. For such applications, there are a number of available packages that provide reliable multicast API, some of which are as follows:

The Java Reliable Multicast Service (JRM Service) provides the capabilities for a receiver to repair multicast data that are lost or damaged, as well as security measures to protect data privacy.

The Totem system, developed by the University of California, provides reliable totally ordered delivery of messages to processes within process groups on a single local-area network, or over multiple local-area networks interconnected by gateways.

TASC’s Reliable Multicast Framework (RMF) provides reliable and send ordered (FIFO) multicast.