Client/Server assignment

Data communication I, Department of Computer Systems, Uppsala University

Introduction

The goal of this assignment is to familiarize you with the UDP/IP protocol, application protocol design and socket programming under UNIX. You will hopefully also pick up some basic Client/Server concepts as well as a basic understanding of name servers.

You will implement a simple protocol for a Client/Server application (a simple distributed database, see below). The application protocol you will work with is faulty, and since your clients must work with existing servers, you do not have the option of changing the protocol. Instead, you must write your client so that it compensates for the faults of the protocol, without violating or extending it.

Reading

You should have read Tanenbaum "Computer Networks", chapter 6, especially pages 486-487 and Section 6.4, before you start to solve this assignment.

Additionally we have put together a small introduction to socket programming and UDP that you will probably find useful. If you need more information, consult Stevens "Unix Network Programming" and the manual pages for the individual functions.

We have tried to include as much information as possible in this document, but unfortunately this means that finding specific information can be hard. This assignment is available on the web (via links from the course home page) which means that you can use 'Find' in Netscape to search for keywords in the text. Also, the web-version includes links to other references.

The rules

Before you start

The assignment consists of three parts:

  1. An implementation of a (reliable) client
  2. Analysis of the protocol
  3. An implementation of a server (optional on some instances of the course)

The three parts should be handed in as three separate assignments. I.e. not stapled together. The correcting of different parts may be handled by different persons, and having the parts separate will simplify this. All parts have the same deadline.

Suggestions

The analysis is probably the most important part of this assignment. If you get that part right, getting the more programming oriented parts right should be straightforward.

You should probably start by reading through the Client part a few times so that you understand how it is supposed to work. After that, start looking at the analysis. Try to do as much of the analysis as you can before actually starting work on the Client and Server. As you find new problems while working on the Client and later the Server, revise your analysis.

The Client and Server has a lot of code in common, at least if you do them right, so you should probably not start implementing the Server until the Client is almost finished.

Finish your work by going over the analysis a final time, checking both that your Client and Server handle all problems you have found in your analysis, and that your analysis include all the problems you actually handle in your programs.

The application

The application you are going to work with in this assignment is a simple distributed database. The protocol and database engine only support three operations: Insert (put), Remove (del) and Query (get).

Servers handle tables of the database. Each table consists of zero or more pairs of <key,data>.

A simple database might look like this:

telephone
joe 4711
bill 11147
email
joe joe@foo.bar
bill bill@cookie.duh

Tables

These two table can reside on the same server, or they may reside on two different servers. But how do we find the right server? We could require that the names of tables include the full network address, but since we already have a database system, we could instead use it to simplify things. We define one table called 'nameserver' and place it on a server on a known network address.

The nameserver table consists of a key/data pair <table_name, network_address>. This means that we can query the nameserver table for a table name, and the returned value should be the network address of the server that this table resides on.

E.g to find the telephone number of 'joe' we would first query the 'nameserver' table for the key 'telephone', i.e the network address of the server that the 'telephone' table resides on. Then we would contact this server and query the 'telephone' table for the key 'joe'.

This way we only have to know the network address of the nameserver, and from this we can figure out all other addresses needed. This is basically the way that the Internet Domain Name System (DNS) works, only it translates between domain names (e.g. Zeke.Update.UU.SE) and IP-addresses (e.g. 130.238.11.14).

The system

The system you will build is potentially quite big. When you start testing your servers, the complete system will be a single database consisting of 20-40 servers running in parallel. You should be very careful when updating the nameserver, since you otherwise might change data that others are relying on. Specifically, you should never delete an entry from the nameserver unless you have verified that the server corresponding to that entry is down.

The protocol

The network protocol defines how the client and server communicates, and what the semantics of different requests are. The protocol we use is built on top of UDP, and thus automatically gets all the benefits and drawbacks of UDP. We use UDP because it is extremely simple compared to TCP (which will do a lot behind our backs), and also have less overhead. If you are familiar with UDP, both using and understanding TCP will be simpler. You can read more about UDP and TCP in the course literature.

Within UDP-packets we frame our application level protocol. We use a single message format for all types of requests, and we use fixed length text strings and single byte values to simplify message handling.

Request Response
GET(table, key) Return EXISTS and set Data field in response if <key,data> pair exists in table.

Return NONEXISTENT if <key,data> pair does not exists in table.

Return ERROR and set Data to an appropriate error message in all other cases.
PUT(table, key, data) Return EXISTS if some <key,data'> pair exists in table.

Return NONEXISTENT and insert <key,data> into the table if no pair <key,data'> exists in table.

Return ERROR and set Data to an appropriate error message in all other cases.
DEL(table, key) Return EXISTS and remove <key,data'> pair from database, if a pair <key,data'> exists in table.

Return NONEXISTENT if no <key,data'> pair exists in table.

Return ERROR and set Data to an appropriate error message in all other cases.

A request contains the following fields:

Name Function
Cookie A "magic cookie" (a null-terminated string). It is used for testing purposes to tell the server to simulate specific behaviors, and also to identify the protocol. It will be explained in more detail below.
Table Name of the table, a null-terminated string.
Request Type of request.
Values: GET, PUT or DEL
Reply The reply from the server. Must be set to NONE in requests.
Values: NONE, EXISTS, NONEXISTENT or ERROR
Key The key part of the pair, a null-terminated string.
Data The data part of the pair, a null-terminated string. Must be set to empty string unless used by the request.

If the server returns ERROR, it may use the Data field for additional feedback.

In the response, the Table, Request and Key fields should always be copies of the corresponding fields of the request. The Data field should also be a copy unless it is modified by the operation.

The prefix of the Cookie of the response should be set to the value of COOKIE, e.g. strncmp(Cookie, COOKIE, strlen(COOKIE)) should yield the result 0.

Example:

If we issue GET(telephone, joe), the message actually sent by the client should be
{COOKIE, "telephone", GET, NONE, "joe", ""}
and given the tables above, the response could be either
{COOKIE, "telephone", GET, EXISTS, "joe", "4711"}
if everything went well, or
{COOKIE, "telephone", GET, ERROR, "joe", "Unable to fulfill request, error #12"}
if the server had problems handling the request.

Notes for clever programmers

  1. The server may use strncpy() to copy string fields. (Sorry... :-)
  2. The client and server may chose to send only as much data as is needed, i.e. it may truncate the packet to the minimum size needed to fit the data.
  3. We will use a C-structure directly as our message. This can cause problems because different systems may not share the same memory layout for structs. You should be aware of this if you try to implement a client or server on a different architecture/compiler than the one used by the example servers.


Assignment part 1 - A reliable database client.

The objective of this part of the assignment is to try to implement a reliable database client using this protocol. As mentioned in the introduction, the application protocol is faulty. A naive implementation will be highly unreliable since no provisions have been made in the protocol to ensure reliability, and the underlying transport protocol, UDP, is unreliable.

It is fairly easy to see how one might end up with a protocol as the one we are working with here. In fact, if we had a perfect communications channel it would be a very good protocol, at least in terms of overhead. Unfortunately, we live in the real world where packets occasionally get lost, scrambled, duplicated and/or delayed.

Your client should, from the users point of view, behave as if the communications channel was perfect, even when it isn't. That is, even in the face of lost packets, the client should always report correctly to the user what really happened at the server and follow the semantics of the protocol. If this goal is at all attainable is up to you to find out. Any case which you think is impossible or impractical to handle must be carefully described in the analysis, with examples of how it occurs and reasoning why it is impossible or impractical to handle. In the case of "impractical", this is a subjective measure, which means that you have to actually convince the person correcting your assignment. You can safely assume that this person is not easily convinced.

In short, your client should handle the unreliable network, so that the user can act as if the network was reliable.

Message format

The file message.h in the assignment subdirectory of the course directory contains the message-type and also defines all constants used in the messages as well as some other constants used in the protocol. We do not want you to modify this file, and we require that you use the supplied file.

The name server

Your client should lookup network addresses to servers handling specific tables via the special 'nameserver' table. This table will always (hopefully) be found on the port NSPORT on the machine NAMESERVER. NSPORT and NAMESERVER are defined in the file 'nameserver.h' in the assignment directory. If you include this file, the symbols will be defined. The keys of the nameserver table will be the tables you can lookup. The data associated with each key will be a string consisting of machine name, followed by a colon, followed by the port number. Your client must correctly parse this answer. E.g to lookup the address of the 'telephone' table you would send a GET("nameserver","telephone") message to NAMESERVER on port NSPORT. The answer could be "dkns.docs.uu.se:11147", which would mean that the server handling the 'telephone' table is located on port 11147 on the machine "dkns.docs.uu.se".

The client program

The operations your client should support are as below. These should be given as command line arguments to the client program.

Operation Description
GET <table> <key> Get <key,data> pair from table <table>.
DEL <table> <key> Delete <key,data> pair from table <table>.
PUT <table> <key> <data> Insert the <key,data> pair into table <table>.

Basic operations

Operation Description
COPY <table1> <key1> <table2> <key2> Copy <key1,data> in table <table1> to <key2,data> in table <table2>.
MOVE <table1> <key1> <table2> <key2> Move <key1,data> in table <table1> to <key2,data> in table <table2>. Do not delete the original until you have successfully inserted the data in its new table.

Synthetic operations

The synthetic MOVE and COPY operations should behave as the PUT operation when it comes to return-values. I.e. they return EXISTS on failure and NONEXISTENT on success. This, of course, means that you may have to transform return-values for intermediate operations. You should also make sure that they are atomic from the user's point of view. I.e. they should either succeed or leave all tables unmodified.

For each operations you should print EXISTS/NONEXISTENT/ERROR as appropriate on a line by itself. Any following lines are assumed to be the data returned. A newline should follow whatever data is printed. I.e for PUT, DEL etc only an empty line should be printed, unless an error occurred.

If errors are detected internally in your client you should print CLIENT_ERROR on a line by itself, followed by the actual error message. If the error occurred during your conversation with the name server, you should print NAMESERVER_ERROR on a line by itself, followed by an error message.

Examples:

# ./dbclient GET "telephone" "joe"
EXISTS
4711
#
# ./dbclient DEL "telephone" "joe"
EXISTS

#
# ./dbclient GET "telephone" "bjorn"
NONEXISTENT

#
# ./dbclient GET "feleton" "joe"
NAMESERVER_ERROR
Non-existent table 'feleton'.
#
# ./dbclient GET "joe"
CLIENT_ERROR
Too few arguments.
Correct syntax is: ./dbclient GET <table> <key>
#

You may print additional diagnostics to standard error (STDERR) when you are running in debug-mode (see below), but on standard out (STDOUT) nothing but what has been outlined above should be printed. This is to simplify automatic testing.

Errors

Between the time you send a request until you receive the answer, a number of things may happen:

Unfortunately, the network will not inform us when any of these errors occur, we have to discover for ourselves what happened.

We define TIMEOUT to be an upper limit on the time we will wait for a response to a single request before we consider it lost. We define RETRIES to be the maximum number of times we will try to send a request to a given server before we consider it or the link to it to be down.

The only case in which you may report a complete failure is if you have sent RETRIES request to the same sender and waited up TIMEOUT seconds per request.

If the server is down, it will take RETRIES*TIMEOUT seconds to determine this. If you e.g. receive RETRIES irrelevant answers (i.e. duplicates, garbled packages etc), you may not consider this to be a total failure. You may, however, reset the timer after handling an irrelevant packet.

This will give you the necessary parameters to determine if the server is down, and when to consider a packet lost. The remaining problems you will have to figure out how to handle yourselves.

In all cases except for a complete failure as defined above, the error should be considered temporary and your client should recover gracefully.

Testing and Cookies

Since you initially do not have a server of your own, and thus cannot create new tables, you will have to use the table reserved for testing, "dbtest". Quite obviously, unexpected things will happen if the whole course use the same key, especially if you all do it at the same time. For this reason, we recommend that you prefix all keys with your user name. E.g. if your user name is 'd99foo' and you want to create a key 'bar', you should call it 'd99foo.bar'.

For testing purposes, your client program should also handle two additional flags. You should stop looking for flags on the command line when your find your first non-flag argument.

Debug

-d Enable your debugging information. If this flag is used, you may write debug output on STDERR. Otherwise, you should not print anything beyond what has been explicitly specified in this assignment. If enabled, you may write debug output on STDERR.

You should include enough debug-messages to allow a user to roughly follow the flow of code, but the specifics are up to you.

Example

The 'sed' command used below will prepend the string 'STDOUT: ' to all output on STDOUT:

# ./dbclient -d GET "telephone" "joe" | sed -e 's/^/STDOUT: /'
Debug: Sending request 0 to nameserver.
Debug: Got response from nameserver.
Debug: Message OK.
Debug: Sending request 1 to telephone.
Debug: Got response from telephone.
Debug: Message OK.
Debug: Printing result.
STDOUT: EXISTS
STDOUT: 4711
#

Cookie

-c <N> <string> Append the specified string to the cookie-field of the Nth request. This is used to tell the server that it should handle a request in a specific manner, e.g. predictable errors. You can specify multiple cookies.
Request numbering

The requests are numbered from 0 and up. Our test scripts will assume that your client always start by looking up tables in the nameserver. In the case of COPY and MOVE, which involves two nameserver lookups, we will assume that you do both before doing anything else. We will also assume that you always do two lookups, even if both are to the same table.

Notice that each packet sent count as a request, i.e. you should increment your counter for each outgoing packet. This means that if you timeout and resend a packet, the counter should be incremented.

Cookie values

Cookie Explanation
-RANDOM Generate a random error.
-REQLOSE Simulate a lost request.
-RSPLOSE Simulate a lost response.
-DELAY Simulate a delayed response.
-DUP Simulate a duplicated response.
-GARBLE Simulate a garbled response.

Supported cookies

Internally, this string should be appended to the value of COOKIE. E.g., when preparing a request, you should first copy the value COOKIE to it, and if a -c flag is specified for this request, append the provided string to the cookie.

Example

(Notice that we do not prepend 'STDOUT: ' to the normal output this time.)

# ./dbclient -d -c 1 "-REQLOSE" -c 2 "-REQLOSE" GET "telephone" "joe"
Debug: Sending request 0 to nameserver.
Debug: Got response from nameserver.
Debug: Message OK.
Debug: Adding "-REQLOSE" to Cookie field.
Debug: Sending request 1 to telephone.
Debug: Timeout
Debug: Resending request.
Debug: Adding "-REQLOSE" to Cookie field.
Debug: Sending request 2 to telephone.
Debug: Timeout
Debug: Resending request.
Debug: Sending request 3 to telephone.
Debug: Got response from telephone.
Debug: Message OK.
Debug: Printing result.
EXISTS
4711
#

Test scripts

You should test your client using the test scripts provided in the "client-test" subdirectory of the course directory. You should not copy these, since they may be changed during the course. You can create symbolic links from the test programs to your current directory with the command 'ln -s /path/to/coursedir/client-test/test* .'. All client test programs accept one parameter which should be the path to the client you want to test.

Example of test script usage
# ./test1 ./dbclient
Your client passed test1.
# 

Limitations

Documentation

We require you to document your code properly. This means that each function should be prepended with a description of what it is supposed to do, what the expected parameters are and what the expected result is. If the operation implemented is non-trivial, an outline of how the function works (algorithm etc) should also be included. In your code, you should use descriptive names for variables and functions, and where necessary, you should include additional information about what is going on.

You should also produce external documentation describing the overall structure and implementation of your client. This documentation should serve as a map of your code, helping both understanding of the implementation and finding specific parts.

Presentation of results

Your finished client should consist of the following:

A few suggestions


Assignment part 2 - The analysis

This is perhaps the most important part of the assignment, and while your analysis may be helped by the practical experience you get by implementing the protocol, the analysis will be crucial to getting your implementations correct.

Problems

You should give a list of problems you have found in the protocol. For each problem you should explain:

A new protocol

Using your findings above, you should design a new protocol on top of UDP that does not have the problems you have discovered in the existing. You should give enough details to make it possible to implement your protocol, if you use mechanisms described in the course literature, you only need to give a reference and explain how you use them. Your description should be clear and concise.

Questions

Finally you should answer some questions:

  1. The name server in the current system is a very useful component, but also a potential problem. What are the problems? Suggest solutions.
  2. You have been working with UDP in this assignment.
  3. In the Errors section we enumerate a few possible error scenarios. Describe how these different errors will manifest themselves at the client, and what problems they may cause. Explain how you detected and handled them in your client.

Presentation of results

Your finished analysis should consist of the following:

The number of pages recommended are only approximations to give you an idea of the size of the analysis.


Assignment part 3 - The server

The server is the component in the system that handles data. By now you should be familiar with the underlying protocol, so we will not repeat the description. You will also have more freedom to design the server and make necessary assumptions. You should, however, document your assumptions. The general requirements on the server are the same as on the client, e.g. you have to produce good, working, well documented code, and you may not violate the protocol in any way.

You may implement the database engine on your own, or you may use ndbm or any other database package. A simplified interface to ndbm, called mydb is available in the course directory.

Startup

At startup your server should accept the debug-flag ("-d") just like the client. All other arguments should be names of tables that this server instance will handle.

Example:

# ./server d99foo.test d99foo.other d99foo.junk

This will start a server that will attempt to create three tables.

During startup the server should:

Having done this, the server enters into an infinite loop where it will answer all well-formed queries sent to it. It should respond with ERROR to all queries to other tables than the ones it handles (i.e. the tables actually entered into the nameserver). It should return meaningful error messages in whenever it returns ERROR to a query.

Your server should handle cookies, that is you should make sure that every request has a proper cookie set. Your server also needs to recognize all the debug-cookies listed, and your debugging output should include information that a debug-cookie has been received and what function it should activate. While you do not have to actually implement the debugging-functions activated by the debugging cookies, we strongly recommend that you at least implement the simple debugging functions (e.g. losing requests/replies).

Output from the server should be kept to a minimum unless the debug-flag is specified. That is, you should report fatal errors, such as failing to enter a table into the nameserver or errors from the operating system, but for example not when a request to a non-existing table is made. Debugging output should include a trace of all requests made, and information about how they were handled.

Example

# ./server -d test
Sun Nov  9 22:35:39 1997: sockaddr setup for port 26642 address 127.0.0.1
Sun Nov  9 22:35:39 1997: Inserted 'test' into nameserver.
Sun Nov  9 22:35:46 1997: Received 127.0.0.1: {"PROT1", "test", 1, 0, "d99foo.test", ""}
Sun Nov  9 22:35:46 1997: GET d99foo.test' from table 'test'
Sun Nov  9 22:35:46 1997: Sending  127.0.0.1: {"PROT1", "test", 1, 1, "d99foo.test", "Hello, world"}
#

Testing

Just as with the client, there are some test scripts for the server. These are located in the "server-test" subdirectory. These take two arguments, the path to your client and the path to your server.

Example:

# ./test1 ./dbclient ./dbserver
Your server and client passed test1.
#

Presentation of results

Your finished server should consist of the following: