Puzzle 3: Multiple Access

Goal

To understand the problems that arise when sharing a resource in a distributed environment by designing and implementing an efficient multiple access protocol.

Outline

The computer world has many shared resources, such as printers, servers, and file systems. In networking it is very common for many computers share a transmission medium. Although sharing a medium is often the best choice for practical and economical reasons, in many cases we simply have no other choice. Ethernet is an example of shared medium - it has one wire that is shared by many computers. Another example is wireless communication - where the shared medium is a radio-frequency band.

But sharing a medium has some problems, especially when two or more computers want to use the medium at the same time. In this situation, colliding messages from both computers are lost. Chapter 7 of the textbook presents many solutions for this problem. For example, your Ethernet card runs a protocol to handle packet collision on the attached wire. Cellular phones use different protocol to handle collision of data packets.

In this puzzle you have to implement a protocol that efficiently shares a resource. It is up to you to choose a protocol: you can pick an existing protocol or you can invent one yourself.

As in the last assignment you should do the whole assignment using the Entrapid simulator.

The shared resource (server)

In this puzzle the shared resource is not a medium but a server. Even though it may seem different we face the same problems as in sharing a medium.

The server in this example is a math server, that, given a number, returns its square. An important feature of the server is that it can only handle one request at a time. If it gets another request while handling one then both fail (a collision). The server   takes  one second (plus or minus a few milliseconds) to handle each request. Upon failure the server sends both colliding clients a nack message.

As in the last assignment you will find the source for the server with a Makefile in /home/cs519/entrapid/ma_server/. You should copy the files in that directory to a directory in your home path and build the server there. See notes in the last assignment for compilation instructions.

The server takes no argument. It will wait for connections on port 2000.

The clients

Your client take one argument , its hostname (if the client is running on machine m3 the argument will be m3).

When your client wants to use the shared resource it should do the following

• Read a request from stdin. The input is  a number (not necessarily 0 padded). You should use scanf to read the input. The client will get EOF (end-of-file) on end of input. If the request is 'EOF' it should terminate
• Open a connection to the server.
• Send the request (10-digit ASCII string, 0 padded) - e.g. the number 123 must be sent as the ASCII  string "0000000123". Use the sprintf function to format the request.
• Read the reply (also 10-digit, 0 padded ASCII string). Use the atol function (converts from ascii to long)  to convert the reply string to an integer (see the source of the provided server for an example). If the request failed (because another client tried to use the server) your reply will be "-000000001". If the reply is too large to fit in ten digits, it will be truncated.
• Print out the answer. The client should write correct replies onto stdout in the same order as the requests. Each reply should be followed by newline. By correct replies we mean that you should not write nack messages (-1).

  For example if your requests are:

  5
  12
  -2

  Then your output should be

  25
  144
  4

  Important: If you want to write out something else write it to stderr (see man pages for fprintf for how-to). Do not write anything but the replies to stdout.

• Close the connection.

Keep in mind that not all requests may be available when the client is started.

To make sure the reply is from the server the test server will do something slightly different (like to the 4th power). So do not generate your reply in the client!

You will find a very simple client at /home/cs519/entrapid/ma_client/. This simple client serves two purposes. You should use the makefile you find in the ma_client directory to make your client. Also you can use it to test if the server is running correctly. It is different from your client in the way that it does not read its input from stdin but only sends one request (the number 12) to the server and while it gets a reply it simply writes it out.

The protocol

The hardest part of this assignment, and also the most important, is to pick the right multiple access protocol. You have complete freedom in your selection as long as you follow the constraints below. Do not pick the first protocol that pops up in your mind. Spend some time to figure out what is important and what might go wrong and how you can test your protocol. Try to avoid very complicated protocols, remember that you have to implement it as well.

Read and study chapter 7 in the textbook carefully before writing a single line of code. If your protocol does not work it will be considered a major bug and you will get 0 grade for the assignment.

Make the following assumptions when you select the protocol.

• the clients will all be started at the same time (before any of them gets its first request)
• a client may run on any node in the network except the one the server is running on
• all clients are identical (same source code)
• the client takes one argument (the hostname)
• at most one client will run on each machine
• the clients will not crash (you have to make sure of that in your implementation)
• not all requests are available to a client when it is started
• the server will be running when the clients are started
• the communication is reliable (no message loss)
• the clients can only communicate through the network using socket programming (i.e. they are of course not allowed to communicate through the file system on babbage or by using semaphores, etc.)

Even with these assumptions, there are many 'correct' solutions. Your goal is to find the most efficient solution, that is, the one that wastes the least amount of time on the wire. As you do the puzzle, think about how you may need to change the solution if one or more of the constraints above were to be removed. This will help you appreciate the designers of Ethernet a little more :-)

The network topology

The network has 6 nodes; all connected to the same wire (you do not have to worry about packet collision on the wire). The server will run on m0 on port 2000. The 3 clients will run on any 3 of the 5 remaining nodes

.

You have to initialize the simulator, using simrun, similarily as in last assignment. The network initialization file is:

/home/cs519/entrapid/topology/puzzle3.init

Unlike last time you do not need to set up any routing information for this topology. The reason is that all the nodes are neighbors in this topology and you do not need to set up routes to neighbors.

Hints

• While you are getting started, it may be good to slow down the server even more. Instead of 1 second, you can make it take 10 seconds to do the calculation. Simply change the alarm line in the ma_server.cpp.
• A word to the wise: UDP

Documentation

Additional documentation for the simulator is at http://www.ensim.com/documentation/. There you will find more detailed information on how to use the simulator and man pages for all supported system-calls. To get access to the online documentation you have to register (of course it is free) at http://www.ensim.com/cornell/cs519/register.html.

Grading

Your ma_client.cpp should compile with the provided Makefile without any warnings. We will run 3 instances of your client on three of the nodes of the network described above. We will feed each client on some number of requests and check the replies. The total number of requests will be 20 (so the minimum running time is 20 seconds), but you will not know in advance which client is getting how many requests.

Your grade will be based on the number of requests served in 21 seconds. If you manage to serve all 20 requests in 21 seconds you will get full grade (5). If you will not be able to serve any request you will get 0. This time the grading is not binary--if you are somewhere in between 0 and 20 requests served in 21 seconds your grade is linearly depending on how many requests you got through (rounded).

We will only run each test once, so if you use random numbers in your solution make then sure that the variation in the efficiency of your protocol is minimal.

What to submit

Please first read the overall submission instructions. In addition, please follow these instructions:

Similar to what you did last time you should mail the source file (ma_client.cpp) to snorri@cs.cornell.edu as plain ASCII text (no attachments please).

Before you send me your code, please mail it first to yourself. Extract the code and compile it. This way you will find out if your mailer is wrapping lines, replacing characters, etc. Or use the mailx program to send mail (see the man page for mailx)

The subject line must be: CS519: Homework 3

Put a one line comment at the top of your code with your name and Cornell ID (6 digits) with the prefixes "Student:"  and "CornellID:".
Example:

/* Student: John Doe CornellID: 123456 */

Known problems

In this section you will find known problems using the simulator and porting programs to it. We will add to this list whenever we find new problems. Please check this list if you have problems.

• On Solaris accept will return -1 with errno EINTR if a signal (such as Alarm) occurs while in a blocking accept. But the virtual machines do not implement Solaris OS, but FreeBSD. In FreeBSD accept does not return even if a signal occurs. In the simulator accept returns on signals. Its return value is 0. This we will fix but not in the version you are using for this assignment. If you set an alarm with SIGALARM, test for this return code.
• In FreeBSD you can only get signals if you are in a system call or a context switch occurs. The simulator does not see context switches so signals can only occur while you are in a system call.
• Do not use C++ stream library (iostream.h). To be able to distiguish between close inside the simulator and close outside the simulator we redefine close. iostream.h undefines our definition so all "close" supposed to be inside the simulator are performed outside the simulator and will therefore fail.
• Do not use C++ comments (// ...). Use instead standard C comments (/* ... */). This is because many of you used mail programs that did line wrapping to submit last assignment. This caused lot of problems compiling you program. Also do not use long strings for the same reason.
• You main function must take two parameters: "int main( int argc, char **argv ) { ... }". This is because it is renamed (to app_main) and wrapped by the simulator library.
• Asynchronous read on stdin failes. A student reported this problem. Since there is no obvious workaround then I will promise that all the clients will have gotten all requests within circa 10 seconds from when the clients were started. See also: stdin_problem.html

Changes to the puzzle (10/20/98)

Because of the problem Entrapid has mixing real file descriptor (like stdin) and virtual ones many students have been complaining that they need to redo the whole assignment. Therefore we decided to change the assignment a little.

Instead reading from stdin the client can read from a special request server called ma_request (both executables and source is found at ~cs519/entrapid/ma_request). The ma_request takes 3 arguments, the name of the clients.

% ma_request m2 m3 m5

It establishes a TCP connection to each of these clients (on port 10001). The ma_request reads from stdin (this is not a problem since I do not need to read on a virtual socket at the same time). The request is of the form "machine-index<space>number" where the machine is either 1, 2, or 3. The machine numbers have nothing to do with the machine names, it is an index to the machine names you passed to the ma_request program. A little example is maybe clearer:

% ma_request m2 m3 m5
2 873                    This sends 0000000873 to the second machine (which is m3 not m2)
1 38                     This sends 0000000038 to the first machine (which is m2)

Upon request the ma_request sends a 10 byte string (0 padded) to the client. Note that the 10 byte string is not 0 terminated. You should use the read function to read it (not fscanf). The ma_request closes all connections when it gets EOF (Ctrl-D on keyboard). You can run ma_request on any of the virtual machines (for example m0).

If you want to use stdin to read the input, then that is fine. But if you uses the ma_request method then please add the following line after the student id line in your program (this should be line 2):

/* Uses the request server */

The assignment is due on Thursday (10/22/98). If you already submitted you can resubmit if you want.

Sorry for the inconvenience.