In this project we will implement the Token-based Mutual Exclusion (TME) protocol using a broadcast structure.  The aim of the protocol is to maintain the distributed mutual exclusion among processes (sites) that need to cooperate. To implement the protocol we need to use two communication structures: muticasting which is one-to-many and point-to-point sending and receiving messages. To multicast messages we will use MulticastSocket class, which is provided by Java, for point-to-point commincation we will use plain Datagram Sockets that we have already used in project 2. In this document we use the terms broadcast and multicast interchangeably so they have the same meaning which is sending a message to all members in a group. The term group means the communicating and cooperating sites in this project.
 

How to Send and Receive Multicast Messages

Multicast messages can be sent and received by using plain Datagram sockets and packets. But this introduces a lot of overhead to the network since every message has to be sent to all members of the group individually.

Fortunately, Java provides the MulticastSocket class to deal with multicast messages within a group. This class uses the IP Multicast mechanism that is supported by the underlying IP network. IP Multicast mechanism in turn relies on the Multicast group that is simply an IP address that falls into the IP class D address (224.0.0.0 - 239.255.255.255). Hence to multicast a message, a given host simply sends its message to the predetermined class D address of the group. To receive a multicast message, a host should listen on a port which is bound to the same predetermined class D address.

At the application level, we will not deal with the network level details of the Multicast mechanism since Java provides necessary APIs for hiding all lower network levels details.

The procedure to receive and send  multicast messages:

• Determine the multicast group address (from the range given above) and a port number for the multicast socket to be bound.

• Create a multicast socket by giving the port from previous step to listen on (MulticastSocket() )
• Announce interest in the multicast group by joining the group. (joinGroup() )
• Receive messages by creating a datagram packet (DatagramPacket() ) and calling receive() method.
• Leave the multicast group (leaveGroup() )
• Close the socket.

• Create a multicast socket by giving the predetermined port number. (MulticastSocket() )
• Create a datagram packet by specifying the predetermined group address and port number.(DatagramPacket() )
• Send messages using send().
• Close the socket.

For details on MulticastSocket class see http://java.sun.com/products//jdk/1.1/docs/api/java.net.MulticastSocket.html
 

Network Environment We Will Use

Since we will use Multicast class of Java and it relies on the underlying network, our network environment must support IP multicast. But because our department network does not support IP multicast in general, we need to limit our environment into a single local network, which immediately connects all the hosts we use. We have such a network environment in CISE lab 114. The machines that we can use are:

sun114-11 through sun114-16
sun114-21 through sun114-26
sun114-31 through sun114-36
sun114-41 through sun114-46

Note for FEEDS students: These machines are available remotely using ssh.

However any other machines, which are connected immediately (i.e. there is no routers between them) can be used.

Note on Time-to-Live value

Time-to-Live (TTL) is a parameter that could be specified for an IP datagram. It specifies how many times a given datagram should be forwarded on to the network by the routers in the network It is also known as the hop count. This value is important in the case of multicasts to limit the datagrams multicast to be forwarded a certain part of the network.

Because we will use a single network to test our application a TTL value of 1 should be sufficient.

Note on Port Numbers in a point-to-point communication

Except multicast port numbers and well-known server port numbers, no communication application can assume a fixed port number. For example, if an e-mail client application has such an assumption, you cannot run more than one instance of that application on a single host which is a highly undesirable situation. Therefore, in general for clients and for systems like this project that need peer-to-peer communication, port numbers should be assigned by the operating system. This is the only way to get a port number that is available at that time. Java provides methods to allocate a port number from the operating system.
 

Implementing Token-based Mutual Exclusion (TME) protocol using a broadcast structure

The protocol is given in pp. 137-138 in the textbook.

Since we will be using MulticastSocket class to send the messages and this class relies on the UDP datagrams (which in turn relies on unreliable IP) we should expect that the messages could be lost, duplicated or delivered out of order. But as indicated above, due to the local area network environment we use, it is highly unlikely to observe that any message is lost, duplicated or delivered out of order. Therefore we assume that we will deploy our application to a large internetwork (i.e. the Internet) and develop and test it in our network environment by simulating the large internetwork conditions. To keep it simple, we will not consider the lost and duplicated messages. However we will simulate the network delays so that some messages will arrive to their destination out of order and consequently some sites at a specific instance of time receive some messages while others do not.. Details of this simulation is given below.

Since the messages will be sent (via multicast) to the each member of the group, every group member will also receive its own messages. The application should be designed to ignore these messages.

In this implementation, there will exactly be 5 sites (group members) named from 0 to 4. Every site will multicast a predetermined number of messages that will be passed as a parameter to the program. Every site will consist of two threads, one for multicasting and the other for receiving the messages multicast.

There are three steps that every site will follow:

1- Initialization of the system

Immeadiately after started, the sender threads will sleep some fixed amount of time to make sure that other sites are also up and running. This time interval is a parameter to the program and will be specified in the config file.

After that, sender threads will annouce their existence to the other members by multicasting a message, which consists of site id, host name and the port number. Since the sites will also communicate point-to-point to send the token, they will need this information. Sites will register this information (i.e.a simple table).

On the other hand, the receiver threads will listen to these inialization messages from all the other sites. The sender thread will wait until the receiver thread indicates that all these messages have been received and the system is up.

We assume that initially site 0 has the token.

2- Simulating the Critical Sections

This step is what actually runs the TME protocol.

When a site is up, the sender thread will do some local processing (simulated by sleeping some random amount of time). Then the thread will need to execute in the
critical section (will also be simulated by sleeping some random amount of time). If the site has no idle token, the thread needs to annouce (multicast a message) that it wants to enter to the critical section, hence the token. Then it will block and wait for the token to arrive. Meanwhile, receving thread continues to run and receive the messages from the other sites. The sender thread will go through this process the number of times, which is given as a program parameter (see config file).

3- Leaving the system

After executing in the ciritical section the number of times mentioned above, sender thread will annouce that it is done running and want to leave the system. After multicasting this message, the sender thread will terminate gracefully.

On the other hand, the receiver thread should wait to receive the terminate (i.e. leaving the system) messages from all the other sites. Once received, it should also terminate gracefully.
 

How to Simulate Network Delays

The easiest way to simulate network delays is to send multicast messages to some group members first and then send to others after some time has been passed. This can easily be realized by two logical groups within the main physical group of 5 sites as below:

Multicasting messages:

define two logical groups group1 and group2 (e.g.,  239.1.2.3 and 239.1.2.4)

if (my Id < 3)
        multicast the message to group1
        sleep some random time upto the value given as a parameter in ms
        multicast the message to group2
else
        multicast the message to group2
        sleep some random time upto the value given as a parameter in ms
        multicast the message to group1

Receiving Messages:

define two logical groups group1 and group2 (must be the same groups as above)

if (my Id < 3)
        Join to group1
else
        Join to group2

Receive messages

With the pseudocode above, every site will receive all the messages sent to the 5-site group, regardless of which logical group they have joined. Also each site will multicast the messages to every other member by multicasting them to each logical group in different order. Note that the same port number can be used for both logical groups.
 

Program Specification

Two programs (hence two main() methods) are sufficient for this system.

First one is to start sites (group members). There should be 5 sites named 0,1,2,3, and 4. This program will read the configuration file config and start the sites on remote machines as we did in previous projects using rsh. After starting all the sites it will terminate.

Second one is the main program that will implement the TME. This program will create two threads, one for multicasting messages and the other to receive them. This program will accept necessary parameters.
 

A Sample configuration file config

# The below order of info must be preserved
# Initial Wait Time in ms - Sender threads should wait this amount of time initially
4000
# Multicast Wait Time in ms - Wait time between multicasts to two logical groups (random time upto this amount)
3000
# Group address 1
239.1.2.3
# Group address 2
239.1.2.4
# Multicast Port
6666
# Number of Critical Sections
5
# Host Names of the Sites
sun114-11
sun114-22
sun114-33
sun114-44
sun114-12

Important Note: The config file is input to the system. Therefore the values in this file are NOT fixed. You must NOT assume fixed values and must NOT hard-code them into your program source. Also the comment lines are only for humans and not for programs, you must not assume their existence. Programs must check and skip if any exists.

However the format (order of the values) of the file is fixed. You do not need to check the format and correctness of the file, you can assume that we will use a correct config file. You will be provided with a sample config file later by e-mail. But again, the values will just be examples, you must test your system by several
different (in content) config files you provide by yourselves. Any config file you use must be a plain text file, to make sure please use a Unix text editor to create one.
 

Output

Below is one possible, sample output of the system. This output is produced by site (process) 0 and the number of ciritical sections executed in this run is 5.

EVENT  is the event that occurred and displayed.
LOCAL SV is the Sequence Vector maintained by this site locally.
TOKEN VECTOR  is the vector carried by the token. If nothing is displayed that means the site does NOT have the token at that time.
TOKEN QUEUE is the Queue that is carried by the token. If nothing is displayed that means the Queue is empty.

Local SV and Token Vector values are displayed from left to right in the order of site0 through site4.
Token Queue is a FIFO queue and the top entry is the leftmost entry displayed.

Possible EVENT values are:

IR:X  Initialization Received - site id, host name and port number are received from site X
IS:M  Initialization Sent (Multicast) - site id, host name, and port number are multicast (announced) by this site

RR:X  token Request Received from site X
RS:M  token Request Sent (Multicast) by this site
TR:X  Token Received from site X
TS:X  Token Sent to site X form this site
CS:S  Critical Section executed and token has been updated by this site, token will be Sent because token queue is NOT empty.
CS:I  Critical Section executed and token has been updated by this site, token is Idle because token queue IS empty.

LR:X  Leave Received - A message received from site X indicating it is done and will Leave the system.
LS:M  Leave Sent - A message Multicast by this site indicating this site is done and will leave.
 

SITE ID: 0
# of CRITICAL SECTIONS : 5

Event   Local  SV     Token Vector   Token Queue
======  =========     ============   ===========
 IR:2   0 0 0 0 0      0 0 0 0 0
 IR:3   0 0 0 0 0      0 0 0 0 0
 IR:0   0 0 0 0 0      0 0 0 0 0
 IS:M   0 0 0 0 0      0 0 0 0 0
 IR:1   0 0 0 0 0      0 0 0 0 0
 IR:4   0 0 0 0 0      0 0 0 0 0
 RR:1   0 1 0 0 0      0 0 0 0 0
 TS:1   0 1 0 0 0
 RR:2   0 1 1 0 0
 RR:4   1 1 1 0 1
 RR:3   1 1 1 1 1
 RR:1   1 2 1 1 1
 RS:M   1 2 1 1 1
 TR:1   1 2 1 1 1      0 1 0 0 0      2 4
 CS:S   1 2 1 1 1      1 1 0 0 0      4 1 3
 TS:2   1 2 1 1 1
 RS:M   2 2 1 1 1
 RR:2   2 2 2 1 1
 RR:1   2 3 2 1 1
 RR:4   2 3 2 1 2
 TR:3   2 3 2 1 2      1 2 1 1 1
 CS:S   2 3 2 1 2      2 2 1 1 1      2 4
 TS:1   2 3 2 1 2
 RR:3   3 3 2 2 2
 RR:2   3 3 3 2 2
 RS:M   3 3 3 2 2
 TR:4   3 3 3 2 2      2 3 2 1 2      3
 CS:S   3 3 3 2 2      3 3 2 1 2      2
 TS:3   3 3 3 2 2
 RR:1   3 4 3 2 2
 RR:4   3 4 3 2 3
 RS:M   4 4 3 2 3
 RR:1   4 5 3 2 3
 RR:2   4 5 4 2 3
 RR:3   4 5 4 3 3
 TR:4   4 5 4 3 3      3 4 3 2 3      3
 CS:S   4 5 4 3 3      4 4 3 2 3      1 2
 TS:3   4 5 4 3 3
 RR:4   5 5 4 3 4
 LR:1   5 5 4 3 4
 RR:2   5 5 5 3 4
 RS:M   5 5 5 3 4
 TR:2   5 5 5 3 4      4 5 4 3 3      4
 CS:S   5 5 5 3 4      5 5 4 3 3      2
 TS:4   5 5 5 3 4
 LS:M   5 5 5 3 4
 RR:3   5 5 5 4 4
 LR:0   5 5 5 4 4
 RR:4   5 5 5 4 5
 LR:2   5 5 5 4 5
 LR:4   5 5 5 4 5
 RR:3   5 5 5 5 5
 LR:3   5 5 5 5 5
 

Notes

• Please remember that the general project requirements page is valid for all projects.
• There should be 5 members of the multicast group identified as 0,1,2,3,4
• The command to start the system must be java Start
• The name of the configuration file must be config and this file should not be submitted.
• Output files must be named as log0,log1, .. log4..
• Failure to follow the requirements (including the file and program names and submission procedures) will result in points loss.

• Develop your application step by step:

• Remember that access to every piece of data shared by different threads must be mutually exclusive (i.e. synchronized).
• Use different group addresses and port numbers in different tests to make sure you are not receiving others' messages coincidentally.
• You may limit the number of ciritical sections to 9 for easy message handling.
• If you see the system is hung due to lost initiliaze messages caused by machines responding slowly, change the initial wait time in the config file to a slightly larger value and/or change the machines in your config file to get rid of the heavily loaded machines.
• To see how network delays effect the system, change the multicast wait time in the config file to different values in different runs.

Please refer to the project general requirements page for submission procedure and use proj4 for the -p argument of turnin if you are a local student and FEEDSproj4 if you are a FEEDS student.