Wiki page for hw2 set up: It's here.

Javadoc for hw2 classes: It's there here.

Updated software release: 1/14, 7:29PM

There was a problem with the original release: the Lobby.class I distributed was compiled with port 8764 embedded into it. If you then changed the lobby port, as you needed to, the clients would try to contact the lobby at its new port, while it was listening (hearing nothing) at 8764. That has been addressed by taking the lobby's port out of the code entirely, and supplying it instead on the command line when invoking the lobby. (If you're using my scripts, they hide all command line arguments, so there is no change in their use.) As a side-effect of this, I decided to remove one of the shell scripts in the tool set entirely; again, this is one you shouldn't have ever noticed, but it means one fewer files in the main directory. Additionally, this new release was an opportunity to updatethe scripts to enhance their reporting of situations in which they are being invoked incorrectly.

Some changes to the instructions have been required. They are highlighted in yellow below (or will be, in a few minutes).

Finally there is a potential problem in using the scripts to control remote executions: they assume you can ssh to a remote host without having to type a password. Rumor has it this is the default situation on CSE systems, which seems somewhat plausible. Normally, however, you have to set up ssh keys. Here's a terse page on what to do, and here's a longer, more completely explained one. (To determine whether or not you need ssh keys, in your control shell issue the command ssh remotehost ls, where remotehost is an actual remote host name (e.g., attu3). If the result seems to be the output of ls, you don't need to do anything. If it fails, then you do, if you want to use the scripts.

To get the new release, delete your existing version (saving any files you might have edited), and refetch using the links below. To be sure you have this release, check for this line at the top of file makefile in the root directory:

# $Id: makefile,v 1.3 2009/01/15 03:22:32 zahorjan Exp $

Overview

There are two parts to this assignment. Part A is a programming project. Part B is also a programming project, except without the programming: it's a set of questions you'd have to answer to implement extensions to the Part A functionality, without the inevitable pain of actually implementing them.

This assignment is intended to give experience with a few things:

• multicast and totally ordered multicast
• socket programming
• protocol layering
• packet encapsulation
• flow control (or, rather, what happens when you don't have it)
• control vs. data planes

The actual number of lines required by a working final solution (Part A) is small; my implementation contains fewer than 150 lines beyond what is in the skeleton code. Two things about that, though:

1. Putting back lines that have been deleted from working code is a lot harder than writing those lines in the first place. (It's less work than writing the entire application, but it's still hard.)
2. This code, in particular, might be a little hard to digest. I'll try to ease that with some explanations, and pictures, here.

Rather than try to write everything about this assignment on one page, I'm going to break it up in a number of pages. The remainder of what is on this page is about the Part A implementation. There will be links for Part B and extended information about Part A.

Part A Overview

The basic goal is easy to understand, a multicast-based chat program. In fact, the chat application is complete, and provided in the skeleton code. What we're building is the multicast network layer that it relies on.

Like most everything so far in this assignment, there are actually two multicast network layers. One provides simply multicast: a single send() call made by the chat application results in data being delivered to many destinations. (The destinations make up the "multicast group.") Multicast is fully implemented in the skeleton code. I'll refer to it as the code does, using "MCast."

The second protocol is totally ordered multicast. We want chat lines that are read off the network to appear in the same order for everyone in the multicast group, and we get this by relying on a network protocol that guarantees to provide that consistent order. We (and the code) refer to this as TOMCast. Looking down at TOMCast from the chat application code, when a receive() is performed, the packet that is returned is guaranteed to be the one that should come next - the same one all other clients get on their corresponding receive. In contrast, with MCast there is no guarantee that two distinct members of the multicast group will receive the same sequence of packets in successive calls to receive().

It's important to understand the division of responsibility in the implementation. From top to bottom, it's this:

• The chat application takes "user input" (it actually generates it out of thin air, but logically it's what the user types) and sends it to everyone in the multicast group. It also reads data that was sent to it from anyone in the multicast group, and prints it.
• TOMCast is responsible for imposing an order on packets received off the network (i.e., sent by multicast group members) so that all members receive them in the same order (assuming no packet losses occur). It also provides a send() interface, with semantics that are identical to MCast.
• MCast is responsible for taking a single send() from the chat application code and causing delivery of data to all members of the multicast group. It also provides a receive() interface, but doesn't say anything about the order of packets returned by calling that interface.
• Below MCast is some other network layer, one that knows how to deliver a packet to single, remote client. MCast makes multiple calls to this interface to achieve multicast. We'll be using UDP, an actual internet protocol, for this layer. (UDP, of course, is built on other layers of protocols, but we don't need to talk about those for a while.) At this level, UDP provides send(packet) and receive(packet), where a packet is basically an array of bytes (where I mean to include the notion that the array has some fixed maximum capacity).

As mentioned earlier, MCast is totally built, as is the chat application (not to mention UDP). What's missing are key parts of TOMCast. Part of Part A is about completing that, that is, enforcing an order for the packets returned from receive() calls that is consistent across all members of the multicast group. The other part has to do with some practical details that arise when trying to build multicast (of any sort).

Specifically, What Do I Have To Do For Part A?

Two things:

• Complete the implementation of TOMCast.
• Implement the lobby.

Much of TOMCast is written - the parts that are heavily intertwined with the rest of the code (e.g., the implementation of MCAST), or that you need but might lead to concurrency bugs if you're not familiar with multi-threaded programming. Only a tiny amount of the lobby is in the skeleton code. It is a stand alone application, though, isn't multithreaded, and is simple, except that it uses sockets and packets.

I don't think there's a compelling reason to promote doing either part first. My advice is to do the TOMCast implementation. It is largely just regular old Java programming - you don't need to know much about sockets and packets to be able to do it. There is some multithreading, but I've tried to keep you as far from that as I could. Doing this part first will undoubtedly require some reading of other pieces of code. That could be of use in implementing the lobby. (I'm pretty sure you're going to want to have read some code to build the lobby, even though strictly speaking that isn't necessary.)

Working on TOMCast requires that you have a working lobby. One is provided in the skeletal distribution, as files Lobby.class-originalDist and Lobby$State.class-originalDist.

More details on each piece follow.

An Abstract View of Some Practical Details

In this section we think about implementing MCast/TOMCast, but at a level of detail above writing actual lines of code.

An issue not addressed by the RTOM algorithm in the lectures notes is, how do we know who is in the multicast group? It seems intuitively clear that this is a prerequisite to building MCast. (Unfortunately, in some absolute sense, it isn't. See Note 1.)

As an implementation issue, knowing who is part of the multicast group can be handled a number of ways. In something as unrealistic as an assignment, the group members can simply be hard coded into the code: a list of IP address/port pairs is embedded there. That, obviously, isn't a very good solution, except for the property of requiring little implementation effort.

The next simplest thing is for there to be some "well-known server" that is used to register interest in the multicast group. By "well known," I mean the location of this one server is hard coded. A client that wants to join the group contacts the server. It gets back a list of all clients currently in the group. It can then start multicasting to those clients.

There are other approaches beyond this, but they are more complicated, and typically rely on some lower level networking layer providing at least limited broadcast (broadcast over a limited area, for instance, within one building). You may have heard them referred to as rendezvous services (or protocols).

In this assignment, I've taken the well-known server approach. To avoid possible confusion about the way overloaded term "server," I'm calling the well-known service a "lobby" (terminology I've borrowed from the gaming world). The location of the lobby isn't actually hard coded into the chat application. Instead, it is provided as a command line argument. This very slight distinction allows you to choose where to run the lobby without recompiling the code.

We use the lobby for two things. First, each chat client registers with the lobby (provides its address to the lobby) when it starts running. The lobby therefore knows who is currently in the multicast group. When a client registers, it is provided with the list of participants. This is the basic function of the lobby.

The second thing we use the lobby for has a motivation that isn't really about multicast. It's this. We're working towards implementing TOMCast, so that all clients display the same list of messages. Presumably, we're going to do some testing of our implementations. To be useful, after each test we have to determine whether the output of all the clients match or not. It would be nice if we could do that simply by comparing output for equality (because the diff program will do that for us).

The problem is that, unless we do something special, the output won't be the same, even for correct TOMCast implementations. The reason is that we can't start all the clients at exactly the same time. Between the time the first comes up and they all come up, any messages sent will be received by only some of them (because only some are members of the MCast group).

The lobby provides a handy way to synchronize the clients, to avoid that problem (by which I mean to make it so rare that we might never experience it). We do that simply by failing to provide the MCast group list until all clients have registered. That way, none of them will start trying to send anything until all are there.

How do we know what "all" means? When we launch the lobby, we tell it the number of clients that will eventually join. (This is another form of "well known"-ness: data that has to provided "out of band" from the communication we're building so that we can build the communication we're building.)

Here's a picture of the protocol (sequence of packet exchanges) the clients make with the lobby:

Here T0 < T1 < T2 < T3. At T0-T2, each client sends a HELLO packet to the lobby, which is expecting a total of 3 clients. The lobby defers answering until it has heard all three client-to-server HELLOs. When it does (time T3) it sends a HELLO back to each client, and includes with it the multicast group information. Each client then begins sending MCast messages directly to the other clients. (The lobby is no longer involved, and can terminate execution at this point.)

In reality, we can't arrange that all clients get the server-to-client HELLO at exactly the same time. But, it's close enough that, overwhelmingly, they should end up showing the same set of messages in their output.

The MCast Protocol

The full MCast protocol is this:

1. The lobby is started, and told to expect N clients in the multicast group.
2. When a client application starts, it calls MCastSocket.join(). That results in an MCastPacket of type CLIENT_SERVER_HELLO being sent to the lobby. The client then blocks until a reply is heard.
3. The lobby extracts the sender's address (IP address and port) from each such packet it receives. That is guaranteed to be unique to that client, and serves as the "name" of that client as far as the MCast protocol goes.
4. When the lobby hears from N clients, it then sends a SERVER_CLIENT_HELLO packet to each. The payload of that packet contains a string representation of the multicast group members, as a list of space separated InetSocketAddress.toString()'s. For example:

   "attu2/128.208.1.138:7329 attu2/128.208.1.139:2493 "
   

5. Having sent the N SERVER_CLIENT_HELLO's, the lobby can now terminate, as it has no further role.
6. The clients now multicast data to each other, using packets of type CLIENT_MCAST, and with payloads containing the chat msg typed by the user (logically).
7. When a client application wants to leave the group, it invokes MCastSocket.leave(), which causes a CLIENT_CLIENT_GOODBYE packet to be multicast.
8. When an MCastSocket has heard a CLIENT_CLIENT_GOODBYE from everyone in the group, it creates and injects a SOCKET_CLOSED packet into the packet buffer (more on that in a second), and the receive thread terminates (more on that in a second).

The MCast/TOMCast Implementation

I'm going to start with a description of the overall code architecture. I'm pretty sure you'll want to read this, read what follows, and then read this again.

Here's a picture:

Here's what it means:

• There are three protocols.
  UDP (blue): Implemented by the Java API with two classes, one representing the data sent or received (a packet) and one representing the communication endpoint (the socket).
  • MCast (yellow): Implemented in the skeletal code, also as two classes.
  • TOMCast (red): Implemented in the skeletal code, also as two classes.
• TOMCast subclasses MCast: a TOMCast packet is an MCast packet; a TOMCast socket is an MCast socket.
• MCast cannot subclass the Java classes, because they don't allow subclassing. So, an MCast packet contains a DatagramPacket; an MCastSocket contains a DatagramSocket.
• A packet, for all protocols, has two parts: a header, containing fixed length control information, and a payload, containing a variable amount of data stuffed in by the client application. (The client of DatagramPacket is MCastpacket, of MCastPacket is TOMCastPacket or the chat application, and of TOMCastPacket the chat application.)
• The three protocols share a byte[] array. They have different ideas of how to interpret what is in it, though.
  • The DatagramPacket views the entire byte[] as payload. The UDP header is contained in the DatagramPacket object.
  • The MCastPacket thinks the first word (4 bytes) of the byte[] is its header, and the rest is payload. The MCastPacket header is a 'type': the kind of packet being exchanged. For instance, we've already seen CLIENT_SERVER_HELLO and SERVER_CLIENT_HELLO types, in the image above about use of the lobby.
  • The TOMCastPacket thinks the byte[] has the MCastPacket header, followed by the TOMCastPacket header, followed by the payload. The TOMCastPacket header is also one word, to be used to contain a clock value.
• The method names in the figure indicate what functionality each class supports (either by implementing it itself or by inheriting it). Basically, to send, you construct a packet, set its address, set it's header information, set its payload, and then hand it as an argument to a socket of the corresponding type by invoking send(). You get packets off the network by invoking receive() on a socket. The type of packet you get depends on the type of socket you use.
• The MCastSocket and TOMCastSocket join() method implements the lobby communication discussed above. The leave() operation causes a packet with MCast header type CLIENT_CLIENT_GOODBYE to be multicast to all clients in the group. That informs them they shouldn't expect to receive any more packets from the departing client.

The TOMCast Protocol

TOMCast is layered on top of MCast. The packet exchange protocol is identical to the MCast protocol (described above). One distinction is that each packet carries a TOMCast header, as well as the MCast header. The TOMCast header contains a clock value.

Implementing TOMCast means changing the code so that TOMCast.receive() returns packets in a consistent order across all clients. The code that is needed operates on only a single client, i.e., there is no new network related (sending or receiving of packets) code required.

Threading Architecture: How Receive Works

It works like this (assuming we're using TOMCast -- if we're using MCast, just chop off the TOMCast part of this picture, and have the chat application thread call receive() on the MCast socket):

Execution starts in the chat application. It creates either a TOMCastSocket or an MCastSocket. Each socket creates a thread (a happy face, in the image) that sits in a loop trying to obtain a new packet from the layer below. When it gets one, it puts it in a queue, then tries to get another one. It does this until the layer below indicates no more packets will ever arrive.

The chat application itself also creates a receive thread. It sits in a loop reading packets from the socket it created, extracting the payloads from them, and printing them - these are the chat messages sent by clients.

The original thread (the one that started execution at the first line of ChatClient.main()) is still running. It's in a loop sending packets. That execution path isn't shown in the figure, but because send() is non-blocking, on a send the client thread moves down all the layers (through a cascading series of sends to the next lower level), and then returns back up to the chat app.

One perhaps surprising thing has to do with how a chat line produced by a client makes its way to being printed by that same client. The answer is pretty simple: the client sends it to itself, via the network. That is, a client always sends every message to literally everyone in the multicast group, including itself. It's own receive thread will eventually get the packet, and print its contents.

When some thread in a layer above calls receive(), a packet from the queue is delivered. (Note that this description does not address what needs to be done to implement ordering in TOMCast - it's about the thread architecture, not the details of buffering.) If none is available, the calling thread blocks until one is put in the queue.

There is one slightly tricky detail here. Suppose the application thread has called TOMCast's receive() and has blocked waiting for the next packet to arrive. Now suppose the TOMCast receive thread finds out that there will be no more packets. (It knows this because it has received CLIENT_CLIENT_GOODBYE packets from all group members.) It can't just terminate execution. If it did, the client thread would be blocked forever, waiting for a packet that won't arrive.

Getting the client thread unblocked requires putting a packet in the queue. There aren't any real ones (i.e., ones that came off the network), so we make one up. It carries an MCastPacket type (header) value of SOCKET_CLOSED. That unblocks the calling thread, which notices that it has this special packet type, and concludes that the socket is closed (no more packets will be available).

Code to do that already exists in the skeleton.

A Note on Implementing the Lobby

If you look at the lobby figure way (way) above, you might notice that what it is doing is MCast: it reads some packets, then MCast's a single packet to all group members (even though it itself is not a group member). So, you might be tempted to implement the lobby using an MCastSocket.

Don't do that. It can't be made to work in any way that isn't unnatural. The problem is that the MCastSocket won't be join()'ed, so won't know who the MCast group members are until it receives the packet you're trying to send (which you can't send because you haven't received it yet). You could try to unicast that packet to yourself, to join(), then do a multicast send, but (a) the MCastSocket has now caused you more, rather than less, work (in terms of coding), and (b) whether this works or not depends heavily on the implementation details of MCastSocket, not just its advertised semantics.

Use a (raw) DatagramSocket. It's okay, and sensible, to use an MCastPacket, though, to provide a convenient way to view the packets you're sending and receiving as having an MCast header and payload. (To mix MCastPacket's with DataGramSocket, you have to use the getDGPacket() interface of MCastPacket to extract the DatagramPacket, which is what DatagramSocket requires.)

Obtaining the Skeletal Source

First of all, this is a Java program, so you're going to need Java development tools. Presumably, you already have those. (They're on all department machines, of course.)

• Download hw2.tar.gz or hw2.jar.
• Expand the file you just fetched. If your browser hasn't already let you do that, use tar (tar xzf hw2.tar.gz) or jar (jar xf hw2.jar). A new subdirectory, hw2, will be created.
• You now have the source. To create javadoc for the source:
  • On a system with *nix (Linxu, Mac, or Windows with cygwin) and gnu make, type make jdoc in a shell, while in the hw2 directory. Subdirectory javadoc will be produced. Open index.html from that subdirectory in a browser.
  • On a Windows system without cygwin: Well, my first advice is to get cygwin. It is admittedly a bit of a pain, as what you get with the default install isn't enough - it won't have java tools, it won't have make, etc. You have to go through the big list of offered packages and keep adding things. You can do this by trial and error (to discover what else you don't have that you need).

    In the likely case you don't want to do that, my next suggestion is to work on attu. You can do that from anywhere. The entire assignment was designed so that even basic (non-windowed) connectivity to attu would be just fine.

    If you really want to work on a Windows box using Windows tools, I can't be of much help. Someone in the class probably knows, though. Presumably the Java tools you've been using will get you a long way: past creating the javadoc and compiling the code. I'm not sure that will be enough, though, as hinted next.

Build, Execution, and Test Environments

To build, compile chatapp/ChatClient.java and mcast/Lobby.java. Easy enough.

To run, you need to start up at least one client and the lobby. You probably want more clients than one, though. All can run on a single machine (e.g., your home machine or attu), or they can be spread around (e.g., across attu1 through attu4, plus maybe a lab machine you're sitting at). The code is networked, after all, so it really shouldn't care where it runs.

The one gotcha (of the kind that makes the code appear not to run) applies to home machines (and not department machines). Typical home connectivity precludes a machine from outside your home's network sending packets to your home machine, unless (at least) your home machine has sent packets to that remote machine first. This means the networking infrastructure you'd be using precludes mixing your home and remote machines for running this assignment. (This is a complicated issue. Roughly, if your home machine has a static IP, you should be able to mix, and if not, you can't. If you don't know whether or not it does, it doesn't.)

Finally, you need to test, that is, to see whether or not you got the right results (total ordering). To help with that, the chat application writes a file of all its chat output. That lets you do comparisons after the chat session terminates.

While it is possible to do without them, I highly recommend the execution control and test tools I built for use with this assignment. They automate all of the above. They require a bash shell, though, not to mention perl and a shared file system (so, either execution of all clients and lobby on a single machine, or execution on machines that share files via a file server, like the attu's, not to mention all lab machines).

There is a separate page about these tools.

Note: You can definitely execute on multiple machines, and send actual packets across actual networks. The machine known as attu actually isn't a machine at all; it's a DNS trick. Instead, there are four machines, attu1, attu2, attu3, and attu4, that you can connect to by using those names. (When you connect using the name attu, one of the four is chosen for you at random. This is a simple attempt to load balance use of the four machines - we tell you all to use attu, then we sprinkle you about when you do.)

make test

It's possible to run the skeletal code "without modification." I think it's worth doing that, as a test of your install and build environments, and your understanding of how to run the program.

1. First, edit mcast/Lobby.java and change the constant LOBBY_PORT from 6874 to some number of your choosing in the range 1024 to 65535. The lobby's port no longer exists in the code. It is instead an invocation argument to chatapp.ChatClient and mcast.Lobby. If you're using the execution control scripts, you never had to type any command line arguments, and you still don't. But, the port number being used still needs to be changed. You'll find the value being used in file go.sh - shell variable LOBBY_PORT, very near the top. The reason: only one socket with a given port number can exist on a machine at any one time. If two of you run on one of the attu's, and neither has changed the default LOBBY_PORT number, the second one will fail when the lobby tries to create its socket.

   You can change this port number once, now, and forget about it. The rest of the code will work with whatever number you've chosen. (But note that port number conflicts are still theoretically possible -- a particular run may fail because, by chance, the port number you chose happens to be in use by some random other application running on the same machine at that moment.)

2. Now do a build. If you're using the tools I built, or emulating them, your class files will end up in hw2/classes. (If not, it's not a big deal, but you will have to adjust these instructions accordingly.)

3. To run, you need a lobby. There is one, distributed as the files hw2/classes/mcast/Lobby.class-originalDist and Lobby$State.class-originalDist. (De-compiling those is definitely in the academic misconduct sphere.) Copy them to Lobby.class and Lobby$State.class, in the same directory.

4. You're now good to go. The chat client application uses MCast sockets and packets, which are fully implemented, so you should be able to execute. (To do so, start a lobby, then start one or more clients. See the javadoc and or comments in the code for arguments to give when starting.)

5. Adding 10 characters to the chat application causes it to use TOMCast instead of MCast: just change 'MCastPacket' and 'MCastSocket' to 'TOMCastPacket' and 'TOMCastSocket' in the five places they occur. Rebuild, and you're ready to run (except that you might have just wiped out the functional lobby by rebuilding, so you might have to copy the working distribution files again).

Although the distributed TOMCastSocket code doesn't implement total ordering, it does implement all the other mechanism (shown in the threading figure above, and discussed in the text) required. This means that TOMCastSocket is essentially doing nothing but passing though packets from MCastSocket, in the same order it received them. The program should run the same as before, albeit a little slower. (The speed distinction is too small to be noticeable to humans. However, it can affect the likelihood that buffer overflow, resulting in packet loss, occurs.)

Understanding Results

Two things on this.

First of all, MCastPacket will not ensure consistent ordering across clients. But, you may observe that it is consistent, even in hundreds of consecutive experiments. Then, it might fail once or twice. Or, it might fail a lot. It depends on the number of clients, how long they sleep between sends, the set of machines everything is running on, and how those machines are connected.

The other side of the coin is that even a correct TOMCastSocket implementation is going to fail to provide consistent results across clients from time to time, and maybe most of the time. The reason is that we don't have any guarantee of reliable delivery. If packets are lost, clients get different results.

You can increase the likelihood of losses in TOMCast, and of inconsistent results in MCast, by: (a) increasing the number of packets sent in the run (an argument to the client invocation), or (b) reducing the time between sends (also an argument to the client invocation), or (c) reducing the size of the receive buffers (defined constants in the socket code), or a combination of all. You can make losses less likely, and improve the fraction of time MCast provides consistent results, by moving those parameters in the opposite direction.

Notes

1. We can achieve multicast by relying on broadcast. In broadcast, a single packet send causes delivery to every machine (currently connected). Each machine can then examine the data. Each machine knows wether it is part of the multicast group or not, so those that want the packet accept it, and the others simply discard it. In some situations, broadcast is easier to implement than multicast, because broadcast doesn't have to enforce not sending to someone who isn't interested. Broadcast is what the radio is. The KUOW radio signal is constantly present at every radio. Each radio can tune to it, or not. KUOW doesn't know who is listening. A similar situation can hold in some cases in computer networks.