Chat servers

Figure 1 shows a sketch of the system you will build. There are two kinds of processes: servers (represented by orange squares) and clients (represented by yellow circles). Each client is connected to one of the servers, and each server is connected to all the other servers. The clients and servers can all run on different machines, or (e.g., for testing) they can all run on the same machine.

The system will provide different chat rooms (i.e., groups in multicast communication). Client can join one of the chat rooms and then post messages, which should be delivered to all the other clients that are currently in the same chat room. If there was only a single server, this would be easy: the server would simply send each message it receives to all the clients who are currently in the relevant room. However, since there can be multiple servers, this simple approach does not work. Instead, the servers will internally use multicast to deliver the messages.

To make this a little more concrete, consider the following example. In the figure, client is connected to server S3. Suppose D joins chat room #3, which already contains A and B, and posts a message there (say, “Hello”). S3 then multicasts D’s message to multicast group #3, so it will be delivered to the other servers. (All servers are members of all multicast groups.) Every server then forwards D’s message to all of its local clients that are currently in chat room #3. In this case, S3 will echo it back to D, and S1 will send it to A and B. S2 does not currently have any clients that are in chat room #3, so it ignores the message.

The servers should support three different ordering modes that we studied in class:

• Unordered multicast: Each server delivers the messages to its clients in whatever order the server happens to receive them;
• FIFO multicast: The messages from a given client C sent to the same chat room should be delivered to all the clients in the chat room in the order they were sent by C; and
• Totally ordered multicast: The messages in a given chat room should be delivered to all the clients in that room in the same order.

Your implementation should be fully distributed; in other words, there should not be any central ‘sequencing nodes’. All communication, both between clients and servers and among the servers, should be via unicast UDP using datagram sockets. You may assume that there is no message loss, and that the messages between a server and its local clients are not reordered; however, messages between servers are typically out-of-order.

Specification

The client

Your first task is to implement a simple chat client. The user should be able to invoke the client from the command line with the IP address and port (i.e., the bind address) of a particular server as a parameter (written in the form IP:port). Note that each client is connected to exactly one server. The user should then be able to type lines of text (commands or chat messages), and, whenever the user has entered a new line, the chat client should send the line to the server in a single UDP packet (without any trailing or or ). The client should also listen for UDP packets from the server; whenever it receives such a packet, it should print its contents to the terminal. You may also want to add a -v option to the client program for your own debugging purposes (what to print for the client’s debug output is entirely up to you).

Commands

When the server receives a line of text from the user, it should check whether it begins with a forward slash (/). If not, the server should consider the line to be a chat message; otherwise, it should treat it as a command. The following commands should be supported, and all of them should be case sensitive.

• /join 〈roomID〉: Used to join a particular chat room (Example: /join 7). The roomID should be an integer in the set {1,2,...,N} where N is the total number of chat rooms. Your implementation should support at least N = 10 chat rooms (i.e., with room IDs 1,2,3,...,10). If the command succeeds, the server should respond with a line that starts with +OK (Example: +OK You are now in chat room #7). If the user tries to join more than one chat room at a time, or if the specified chat room does not exist (e.g., the specified room is outside your supported range of room IDs), the server should respond with a line that starts with -ERR (Example: -ERR You are already in room #9).
• /part: Used to leave the current chat room. If successful, the server sends a response that starts with +OK (Example: +OK You have left chat room #7). If the user is not currently in a chat room, the server sends a response that starts with -ERR.
• /nick 〈nickname〉: Used to set the user’s nickname (Example: /nick Linh). The server should respond with a line that starts with +OK. If the user does not explicitly set a nickname, the server should use its IP and port (Example: 127.0.0.1:5005). If the /nick command is used more than once, the server should use the latest nickname. The /nick command can be issued at any time (including even before the user joins a chatroom), and it should persist across chatrooms. You may assume that 〈nickname〉 can be any non-empty sequence of ASCII alphanumeric characters. It is case sensitive, and, for ease of implementation, does not need to be unique (i.e., it is okay to have two users with the same nickname). Since nickname is not unique, you should use the IP and port to distinguish between different clients.
• /quit: When the user enters this special command, the chat client should send the command to the server and then terminate. The server should remove the chat client from its list of active clients, as well as inform other servers so that they can clean up any internal data structures (e.g., the holdback queue for that client in FIFO ordering) after delivering all the existing messages from that client. The /quit command can be sent by the user at any time.

If the user sends a text message without having joined a chat room, the server should respond with a line that starts with -ERR. To make your implementation easier, each client cannot be in more than one chat room at a time. You may assume that each text message sent by the user is at most 1000 bytes. If the user terminates the client using CTRL+C, the client should behave in the same way as if it has received a /quit command. If the user enters an invalid command, i.e., the text begins with “/” but does not fall into the above commands, the server should respond with a line that starts with -ERR.

Below is an example session of the chat client (the lines in bold are typed by the user; the server’s bind address is 127.0.0.1:5000):

The server

Often, multicast systems support dynamic membership: nodes can join and leave the system at runtime. However, to simplify the assignment a bit, we will implement only static membership: each server will have access to a configuration file that contains the addresses of all the servers in the system.

Each server will have two — potentially different — addresses. The first is the forwarding address: this is the IP and port number that other servers should use as the destination address when they want to send a message to this server. The second is the bind address: this is the IP and port number on which the server listens for UDP messages from clients and from other servers; it is the address that the server should bind to (and that its clients should connect to). Usually, the two addresses are the same. However, for debugging, it is useful to have the ability to make them different; for more details, see Section 3.2.

Your server program should require two command-line arguments. The first is the name of a configuration file that contains the forwarding address and the bind address of all the server instances, and the second is the index of the current server instance in this list. The file should contain one line for each server instance. The configuration file follows one of the two formats, depending on whether the proxy is used or not (the proxy will be described later in Section 3.2):

• If the proxy is used: Each line should contain two IPs and port numbers, separated by a comma (Example: 127.0.0.1:8001,127.0.0.1:5001); the first address is the forwarding address and the second is the bind address.
• If the proxy is not used: Each line of the configuration file should contain only one IP address and port number (Example: 127.0.0.1:5000); this address serves as both the forwarding address and the bind address for that server.

The index of the first server should be 1. For instance, suppose the file foo.txt contains the following lines (notice that the proxy is used in this example because each line contains two addresses):

• 127.0.0.1:8000,127.0.0.1:5000
• 127.0.0.1:8001,127.0.0.1:5001
• 127.0.0.1:8002,127.0.0.1:5002

and the server is invoked like this: chatserver foo.txt 2, then the server would listen for (all) messages on its bind address, i.e., on 127.0.0.1:5001. When it has a message for the third server, it would send the message to (i.e., set the destination of the message to be) the third server’s forwarding address, which is 127.0.0.1:8002; when it has a message for the first server, it sends the message to the first server’s forwarding address, which is 127.0.0.1:8000. In addition, the user would invoke a client of the server using the server’s bind address — e.g., a client of the second server can be invoked like this: chatclient 127.0.0.1:5001.

The server should also accept two options (-v and -o) on the command line:

• When the -v option is present, the server should print a line to stdout when something important happens. (This is meant for debugging, so it is up to you to decide what qualifies as important.) Each such line should start with a prefix of the form hh:mm:ss.uuuuuu Snn, where hh:mm:ss.uuuuuu is the current UTC time in hours, minutes, seconds, and microseconds, and nn is the server index from the command line. For instance, the server might print 03:48:22.004328 S02 Client 17 posts "Hi" to chat room #3. To obtain the current wall-clock time, you can use functions such as gettimeofday() or clock_gettime() and convert the obtained values to the correct format as shown above.
• The -o option is used to select an ordering mode: choices are -o unordered (the default), -o fifo, and -o total. You may assume that all servers will always use the same ordering mode. Please note that all ordering semantics must be implemented entirely in the server; this is possible because messages between a client and its server will never be lost or arrive out-of-order. (The client merely sends messages from the user to the server and displays messages the server delivers to the user.)

When no arguments are given on the command line at all, the server should print your name and SEAS login and then terminate. If the server is terminated using CTRL+C, it should close its socket and exit. When a client posts a message to a chat room, the server should prepend “” to the message, where xxx is the client’s nickname (or the client’s IP:port if the client has not set a nickname), just like in the example transcript above.

You may assume that all the servers will be running at the same time (before invoking the clients) and that they do not fail. Your implementation must support at least 10 servers, with up to 250 clients in total.

Extra credit

Causal ordering (+6%)

For this extra-credit task, you should add a fourth ordering mode: causal ordering. As with the existing three modes, your implementation must be fully distributed — for instance, you may not use a central coordinator. Your server should support an -o causal option to enable this mode. Since this is the extra credit, you will need to write test cases on your own; however, at the very least, your solution should pass the FIFO test, which you can use our provided tester for checking.

Lossy links (+4%)

For this extra-credit task, you should add a way to handle message losses on the server-server links. Lost messages should be retransmitted, but you may assume that the network remains connected, and that a message will eventually be delivered if it is retransmitted sufficiently often. The proxy.cc tool already supports a command-line option -l that causes the proxy to drop a certain fraction of the messages it forwards; this should be useful for testing. The server should continue to support the three ordering semantics (unordered, fifo, total).