CS 414/415 Programming Project 3

Unreliable datagram networking


Overview

Preemption, which you implemented in the previous project, provides a basis for more sophisticated features to be added to minithreads. Your goal in this project is to add unreliable networking on top of the preemptive threads package: it should be possible for one copy of the minithreads package to send a message to another minithreads instance running on a different computer, and even for different threads in the same package to exchange messages.

We have provided you with a simple "raw" interface to the network, which behaves like IP: it allows a thread running in a minithreads package on machine A to send a packet to the minithreads package running on machine B. When the packet arrives, it raises a network interrupt. This interface is not very convenient for application programming, since it does not allow the sender to control which thread at machine B will receive the message!

The goal of this project is to add a "minimsg" layer on top of the raw interface, which implements "miniports". Each instance of the minithreads system maintains a collection of local miniports. Miniports serve as destination and source identifiers, uniquely identifying the connection (and the set of threads) to which the packet needs to be delivered. Senders name not only the destination machine, say B, but also the port number, say X, to which their packet should be delivered. When the packet arrives at B, it is queued at the appropriate miniport, waiting to be received.

This assignment closely follows the IP/UDP analogy. The raw interface we provide is equivalent to IP. The miniport and packet send and receive operations you write are equivalent to UDP. To make the project tractable, we omit a few details, such as UDP checksums and fragmentation of long datagrams (for that you'll have to wait until the next assignment!).

The Details

The interface you need to implement is in minimsg.h. We have provided you with skeletal routines to start off with. Note that you will need to closely interface with the network.h interface in order to start up the pseudo-network device and the IP-layer, to send messages and to receive them. Below, we first describe what we provide you with in terms of a network device and how you need to interact with it, (as with real networking cards, there are some elaborate constraints on when the card can be initialized), then what you need to implement in the minimsgs interface, and finally describe the miniport usage conventions you need to implement to facilitate uniform applications.

To start up the networking pseudo-device, you need to call network_initialize(). This function should be called after minithread_clock_init(), but before interrupts are enabled and thread scheduling starts because the network interrupt initialization shares code with the clock interrupt mechanism. Network_initialize takes a "network handler" as an argument. Analogous to the clock_handler from the previous assignment, you will get an interrupt every time a packet arrives. This interrupt will be taken on the stack of the currently executing thread, thereby interrupting it. Once minithreads figures out that the cause of the interrupt was a network packet, it will invoke the "network handler" you provide. At that point, you can do anything you like to process the packet, but note that you are executing in interrupt mode and should try to finish as soon as possible and resume execution.

You can send packets to other hosts using the network_send_packet() call in network.h. The remote host that the packet is destined for is identified by the network_address_t type. Packets are passed by two arguments, a char* buffer, and a length field. The maximum length of a packet that your network pseudo-device supports is given by the MAX_NETWORK_PKT_SIZE constant in network.h. The network_send_packet() function takes two (buffer, length) pairs: one for the header, and one for the data; the buffers get concatenated before they're sent, and it's the receiver's job to strip the header off the packet when it arrives.

Extra Information: The parameter to your network_handler should be cast into a pointer to a network_interrupt_arg_t. The information about the packet received is stored into the fields of network_interrupt_arg_t: addr is the network_address_t of the sender, buffer is an array containing the message (the header followed by the data) and size is the size of the message (header size plus data size). You have to unpack the header and the data and for this you have to remember the size of the header.

Minimsgs

Your minimsg layer needs to send and receive packets on a best-effort basis. This means that, on the sender's side, you need to assemble a header that identifies to whom the packet is directed, and on the receiver's side, you need to examine the header, figure out the destination, enqueue the packet in the right place and wake up any threads that may be sleeping, waiting for a packet to arrive.

minimsg_send() is only required to assemble a header for the message that will be sufficient on the receiving end to identify the recipient. Since the recipient will probably want to respond to this packet, you will need to include fields that together with the information received in the handler's parameter identifies the sender. You do not need to implement UDP-fragmentation, a time-to-live field, or a checksum for this assignment.

Receiving messages requires decoding the packet header to determine which miniport it has been sent to, then checking if a thread is blocked waiting to receive a message from that miniport. If so, that thread can be woken up, otherwise, the message must be queued at the miniport until a receive is performed. If multiple threads are waiting to receive a packet, only one should be woken up, and incoming packets should be routed to the waiting threads in round-robin fashion. That is, if threads A, B and C are waiting to receive on port X, A should get packet 1, B packet 2, C packet 3. There should be just one copy of each packet, and no thread should receive less than one packet.

Though best-effort delivery is fine for this project, your code should not introduce "more unreliable" operation! For instance, if a thread on machine A sends a stream of messages to a single port on machine B, which arrive in the order M1, M2, ..., then that's the order they need to be returned by receive operations on that port, with no additional duplication or packet loss.

Miniports

Miniports are used to identify communication endpoints. They come in two forms: local and remote, with their own corresponding functions, miniport_local_create() and miniport_remote_create(). Remote ports are data structures that host A uses to identify ports on host B. Local ports identify other ports on host A itself. A remote port has a network_address_t to specify the remote machine, and a miniport identifier to distinguish miniports on that machine. A local port has some additional fields to allow messages to be queued on it, and threads to block waiting for messages. A remote port on machine A corresponds to some local port on machine B, and serves as the destination for a minimsg_send(). Sending from machine A also requires a local port at machine A to be specified. When the message arrives at machine B, a remote port will be created and returned as part of the receive, corresponding to the local port at machine A the message was sent from: this allows the receiver to reply. To destroy a port, local or remote, the miniport_destroy() function should be used. It is legal to specify a local port as the destination of a send operation.

A large part of your task will involve managing the local port space. To simplify this assignment, we decided not to require you to implement a nameserver. Recall from the lectures that nameservers or portmappers are intended to avoid building such dependencies into programs. Therefore, in order to identify applications residing on remote hosts, programs will have to reference hard-coded port numbers. This isn't too unrealistic - today, many popular services, such as remote login, mail, time, etc. do not use a nameserver but instead reside at well-known TCP or UDP ports. Other programs then use these magic numbers to connect to these services on remote machines without going through a nameserver.

Each new local miniport should get a unique number. To make it easy to test your code, please follow these two conventions:

  1. Use port numbers 0, 1, 2, for successively-created local miniports. Do not reuse port numbers, even if the original port using a number is destroyed, unless you reach the end of your port-space (which should be about 65535 ports).
  2. Ignore intervening calls to create remote ports. This includes remote ports automatically created by a receive operation. The sequence of port creation operations "local, remote, local, remote, local, local" should number the local ports 0, 1, 2, 3.
The reason for these rules is to make it as easy as possible for a machine A to predict what port numbers another machine B will be using for its ports: in order to send to a miniport at B, A has to know its number. To implement these conventions, we suggest you start numbering local ports at 0, and remote ports at 32768.

Extra Information: Function minimsg_receive has to create a miniport for every message received and the application is responsible for destroying this miniport when is no longer needed. If the message is received from a local port, the same local port cannot be returned since it will be destroyed and also a copy of the local port will complicate the internal bookkeeping since now multiple local miniports can have the same port number. For this reason you should create a special type of miniport that is just a surrogate for a local port (just a "pointer" to the real port) that can be safely destroyed by the application without affecting the local miniport. You should handle this special "pointer" local ports internally.

Tablet systems

Starting with this project, you will run your system code both on PC desktops and on the Tablet PCs. Every group has received a Tablet. These tablets have been imaged with Windows XP Tablet and Visual Studio .NET 2003, along with Ethereal, a network packet analyzer. This may be very valuable to you in your debugging. Code that runs under Windows XP should compile and run correctly under the Tablets.

How to Get Started

How to Test Your Code

It's crucial that systems code be correct and robust. You must test your code with reasonable and unreasonable test cases, and ensure that it behaves correctly.

To facilitate testing of minimessages, we provided you with some test programs. It's a good idea to start with these, and develop your own tests as you need them. The tests appear in network[1-6].c, and they are example uses of the minimsg interface. Besides network tests, there are other programs used to test the alarm and preemption implementation.

Do not forget to check for memory leaks. Your threads package should not run out of memory when large numbers of ports are created and destroyed.

Audio Streaming

Now that we have local and remote message ports on our minithreads system, we have opened up a wealth of application possibilities. Rohan, one of the TA's, has written a simple streaming audio app that we will provide you. You can use it to test the efficiency of your implementation. We will run a race at the end to see which group has the best performance, with the winner receiving CS414/415 glory.

For the Adventurous

Note: These suggestions for an extra challenge will be examined but not graded. They will have no impact on the class grades. They are here to provide some direction to those who finish their assignments early and are looking for a way to impress friends and family.

Build a nameserver that sits on a given miniport and implements the following protocol:

Where <name> is the name of the registered service, and <portnum> is the number of its port. It uses NACK to signify that there is no such service. It also listens on a local port to receive registration requests from local threads:

Final Word

Here is where we will put the frequently asked questions about Project 3.

If you need help with any part of the assignment, we are here to help.


cs414@cs.cornell.edu