CSE 123B: Communications Software

Assignments

Assignment 1: A Web Server

The goal of this project is to build a functional HTTP/1.0 server.  This assignment will teach you the basics of distributed programming, client/server structures, and issues in building high performance servers.  While the course lectures will focus on the concepts that enable network communication, it is also important to understand the structure of systems that make use of the global Internet.

This project should be done in teams of two.

Part 1: Build the Server (Due: April 15, 5 pm)

At a high level, a web server listens for connections on a socket (bound to a specific port on a host machine).  Clients connect to this socket and use a simple text-based protocol to retrieve files from the server.  For example, you might try the following command from a UNIX machine:

% telnet www.cs.ucsd.edu 80
GET index.html HTTP/1.0\n
\n

(type two carriage returns after the "GET" command).  This will return to you (on the command line) the html representing the "front page" of the UCSD computer science web page.

One of the key things to keep in mind in building your web server is that the server is translating relative filenames (such as index.html ) to absolute filenames in a local filesystem.  For example, you might decide to keep all the files for your server in ~student/cse222/server/files/ , which we call the root.  When your server gets a request for index.html , it will prepend the root to the specified file and determine if the file exists, and if the proper permissions are set on the file (typically the file has to be world readable).  If the file does not exist, a file not found error is returned.  If a file is present but the proper permissions are not set, a permission denied error is returned.  Otherwise, an HTTP OK message is returned along with the contents of a file.  How would your server support ".htaccess" files on a per-directory basis to limit the domains that are allowed access to a given directory?

You should also note that web servers typically translate "GET /" to "GET /index.html".  That is, index.html is assumed to be the filename if no explicit filename is present.  That is why the two URL's " http://www.cs.ucsd.edu " and " http://www.cs.ucsd.edu/index.html " return equivalent results.

When you type a URL into a web browser, it will retrieve the contents of the file.  If the file is of type text/html , it will parse the html for embedded links (such as images) and then make separate connections to the web server to retrieve the embedded files.  If a web page contains 4 images, a total of five separate connections will be made to the web server to retrieve the html and the four image files.  Note that the previous discussion assumes the HTTP/1.0 protocol which is what you will be supporting in this first assignment.

Next, add simple HTTP/1.1 support to your web server, consisting of persistent connections and pipelining of client requests to your web browser. You will also need to add some heuristic to your web server to determine when it will close a "persistent" connection. That is, after the results of a single request are returned (e.g., index.html), the server should by default leave the connection open for some period of time, allowing the client to reuse that connection to make subsequent requests. This timeout needs to be configured in the server and ideally should be dynamic based on the number of other active connections the server is currently supporting. That is, if the server is idle, it can afford to leave the connection open for a relatively long period of time. If the server is busy, it may not be able to afford to have an idle connection sitting around (consuming kernel/thread resources) for very long.

For this assignment, you will need to support enough of the HTTP protocol to allow an existing web browser (netscape or IE) to connect to your web server and retrieve the contents of the UCSD CS front page from your server.  (Of course, this will require that you copy the appropriate files to your server's document directory.)

At a high level, your web server will be structured something like the following:

Forever loop:
Listen for connections
    Accept new connection from incoming client
    Parse HTTP/1.0 request
    Ensure well-formed request (return error otherwise)
    Determine if target file exists and if permissions are set properly (return error otherwise)
    Transmit contents of file to connect (by performing reads on the file and writes on the socket)
    Close the connection

You will have three main choices in how you structure your web server in the context of the above simple structure:

  • A multi-threaded approach will spawn a new thread for each incoming connection.  That is, once the server accepts a connection, it will spawn a thread to parse the request, transmit the file, etc.
  • A multi-process approach (really only an option if you choose to do your development in C/C++) maintains a worker pool of active processes to hand requests off to from the main server.  This approach is largely appropriate because of its portability (relative to assuming the presence of a given threads package across multiple hardware/software platform).  It does face increased context-switch overhead relative to a multi-threaded approach.
  • An event-driven architecture will keep a list of active connections and loop over them, performing a little bit of work on behalf of each connection.  For example, there might be a loop that first checks to see if any new connections are pending to the server (performing appropriate bookkeeping if so), and then it will loop overall all existing client connections and send a "block" of file data to each (e.g., 4096 bytes, or 8192 bytes, matching the granularity of disk block size).  This event-driven architecture has the primary advantage of avoiding any synchronization issues associated with a multi-threaded model (though synchronization effects should be limited in your simple web server) and avoids the performance overhead of context switching among a number of threads.

You may choose from C or C++ to build your web server but you must do it in a Unix-like environment.  You will want to become familiar with the interactions of the following system calls to build your system: socket(), select(), listen(), accept(), connect() .  We outline a number of resources below with additional information on these system calls.  A good book is also available on this topic.

Assignment 1 Submission guidelines

You must include a makefile with your submission. When we run make along with your makefile the webserver should be created as a single file called server.

Make the server document directory ( the directory which the webserver uses to serve files ) a command line option. The command line option must be specified as -document_root. Thus, we should be able to run your webserver as
$ ./server -document_root "/home/chubble/assignment1_files"
Note that there is no slash at the end of assignment1_files.

Make the port the server listens on, a command line option. The option must be specified as -port . Thus, we should be able to run your server as
$ ./server -document_root "/home/chubble/assignment1_files" -port 8080

To submit your assignment, submit a tarball of your assignment using the turnin command :
% turnin -c cs123b -p project1 project1.tar

Please include the following files in your tar ball.

  1. A short writeup. This should consist of the following:
    1. The names of all people involved along with their email addresses and SIDs.
    2. What all functionality is implemented in your webserver.
    3. What are the problems(if any) with your webserver.
    Writeups should preferably be typeset
  2. All the files for your source code only. Please do not include any executables.
  3. The makefile.

Assignment 2

A pdf version of this assignment description can be found here

Introduction

The goal of this assignment is to learn some of the commonly used techniques for achieving fault tolerance in distributed systems. One of the fundamental problems in this space is ensuring that services remain available in the face of failure.

The service you will be building attempts to collect the results of a poll from a set of clients. Periodically, each client will transmit its decision on a vote to the service. Each vote will be uniquely identified by a sequence number and will simply consist of clients voting yes or no on that sequence number. The vote will be initiated by the server requesting a vote from each client on a particular sequence number (e.g., ballot or initiative). The service will consist of exactly two replicas, each receiving a separate copy of the vote over a TCP connection. Each replica goes through the same logic to transmit a summary of the vote back to all clients, e.g., 55\% of the clients voted yes. The primary also transmits a copy of the vote to the backup. While the backup does not transmit vote results to the clients, note that it has the exact same information as the primary and hence could transmit the vote results at any time.

Client

It is fine for a given client to receive multiple copies of the results for a given vote. The vote results should have a globally unique identifier such that clients can easily detect the reception of a duplicate result. Each client should log the results of each vote to a local file. There should be no duplicate or missing entries from the file. The format of the log file should be as follows:
< Vote ID >    < Yes Count >   < No Count > \n
That is each line should contain the vote sequence number, followed by the number of Yes votes, followed by the number of No votes followed by a newline. Each field on the same line should be delimated with spaces. Finally, you can assume that clients are dependable, meaning they will never crash and the link between clients and servers will never go down.

Servers

In all cases, there will be two replicas of the server, a primary and a backup. Each will spawn a separate thread to exchange heartbeat messages with the other. These heartbeats might be exchanged once a second as a form of keep alive: when receiving a keep alive each instance of the server can assume that the other is still up and functioning correctly. If one machine does not receive a heartbeat for a specified minimum of intervals, e.g, 5 intervals, then it assumes that the other has failed.

If the primary detects the failure of the backup, its responsibility is to restart the backup. For simplicity, you may assume that the primary and backup are running on the same machine, but listening on different ports. In general of course, the primary and backup may be running on different machines across a cluster or even across the wide area Internet. Thus, restarting the backup will consist of appropriate calls to fork()/exec() and having the backup execute the appropriate join protocol. The primary must also inform the clients of the identity (e.g., IP address/port) of the new backup once the backup has restarted and executed a join protocol. Once the backup is restarted, clients may transmit their subsequent votes to the new backup.

If the backup detects the failure of the primary, it elevates itself to the status of primary and takes over the job of disseminating vote results to clients. For instance, if clients are still waiting for the results of a given vote after the failure of the primary, the newly elevated primary will transmit these results to all clients.

In general, servers are heavy weight pieces of software that cannot be restarted immediately. Hence, we will assume that a newly started backup takes a fairly long amount of time to restart (30 seconds, though you may use shorter values for testing). While a new backup is starting, the primary will inform the clients that it is the only person that should be collecting votes. Once the backup has successfully executed the join protocol, the primary will inform clients of the identity of the new backup and all votes will once again go to the primary and backup.

You may assume that the primary and the backup never fail simultaneously. Further, we assume that none of the participants, the clients or the servers, are malicious. However, you cannot make the assumption that the link between the primary and backup is always dependable. A valid scenario would be for a communication loss to happen between the primary and backup, and both the primary and backup would assume that the other has failed and try to become the new primary.

The same piece of code should be used to implement both the primary and the backup. There should simply be a switch to determine whether a particular server is acting in "primary"- or "backup"-mode at any particular point in time.

Protocol

To summarize, here are the communication protocols that you need to design and implement as part of this assignment:

  1. The process of transmitting a vote fom a cient to both the primary and the backup from individual clients.
  2. Transmitting vote summaries from the primary to all clients.
  3. The keep alive messages between the primary and the backup.
  4. The join protocol for a new replica joining an existing primary as a backup.
  5. Communication of backup/primary identity from the primary to the clients in the face of failure.

Milestones

For this assignment, the design of the protocol governing the interaction of the various components will be critical. Thus, we will proceed with this assignment in two parts as outlined below:

Part 1, due April 25, 2005 at 5 pm. You will submit a detailed description of the protocol that you will use for communication among the various entities. You may encode your protocol any way that you like, but consider using XML and/or XMLRPC for the communication as a learning exercise to gain some exposure to this technology. You should also have completed clients that transmit a vote to both a primary and a backup, wait for a response, write the response to disk, and then move on to the next vote. You do not need to have any failure detection, joins, redirection to particular primaries/replicas implemented. However, the protocol for all such communication needs to be fully documented. Include any relevant pictures to describe this communication process.

Part 2, due May 6, 2005 at 5 pm. You will complete the fully functional replicated service including all of the protocols mentioned above. You should also submit updated documentation reflecting your final protocol, including why you settled on the design that you did, how to run your system, etc.

Assignment 3: Distributed Peer-to-Peer File Sharing

Introduction

For this assignment you will be implementing a distributed file-sharing protocol. To aid you in this feat, you will be using a research effort called Mace: a tool used for designing, implementing and testing distributed protocols. Mace is a very powerful tool and many of its features are beyond the scope of this project, however you will need some baseline understanding of Mace in order to complete the assignment and are encouraged to read the documentation included in the release.

The Files

A detailed description of the protocol you will be implementing can be found here. The release of Mace that will be used for this class which also contains some skeleton code for the protocol can be found at http://macedon.ucsd.edu/release/mace under the login and password given in class. All necessary documentation including basic tutorials and examples can be found in mace/docs/.

Getting Started

You are strongly encouraged to attend sections and office hours in order to get a basic understanding of Mace. The service you are implementing is called Cal_A_Lum and a skeleton .mac file can be found in mace/services/Cal_A_Lum. The application you will eventually be running with your P2P service can be found in mace/application/CalALum_gui. This application contains a GUI front end and is quite bulky, so you are encouraged to write your own simple applications for testing your protocol.

To get yourself started first go to mace/docs and type in "make". These will generate all of the pdf files that you will need for reference. Next enter the root directory /mace and type in make. This should create the mace compiler as well as compile try to compile any services you have in mace/services. However, for this project you will only be writing to the Cal_A_Lum service.

Now look at the file /mace/services/Cal_A_Lum/Cal_A_Lum.mac. This file contains a skeleton for the protocol that you will be writing. All of the states, transitions and messages have been defined for you, however you will need to determine what the contents of these should be. You will also need to define auto_types to maintain information about other nodes in the network as well as any other serializable data structures you wish to have. The auto_type supernode_peer has been defined for you as well as a data structure for maintaining a set of peers, but these are obviously not all the auto types your protocol will require.

Due Dates

Part 1, Due Mon, May 23 at 5pm: Definition of autotypes and messages. For the first milestone you will turn in a .mac file at the very least gives the full definitions for auto types and messages that are required by your protocol.

Part 2, Due Fri, June 3 at 5pm: Everything. A working version of your protocol which should work seamlessly with the application provided is due including a write up which gives you and your partners names, email addresses and SID, and any details regarding your protocol implementation we should know about.

Turn-in Instructions (please read!!)

You must include a writeup with your project submission. Please put the writeup in the root directory : /mace and include the following items in your writeup :

  1. Names, email addresses and SIDs of all members of the group
  2. A description of what (if any) features you have failed to implement for the project
  3. Any assumptions you have made about the protocol that have you do not believe have been made clear in the writeup.
  4. Any other information you believe we will find useful in grading your project.
  5. Please answer the following questions :
    1. What did you think of mace in terms of usability and utility.
    2. How many hours did you spend on project1? project2? project3?
    3. If you could re-implement project 3 in any language of your choice, which would it be?
    4. Any extra comments regarding project 3 are welcome.

When turning in your submission, make sure to first make clean from the base mace directory. Next, tar your entire mace project (recursively including directories), then gzip your submission. Email your tarball to : calvin.hubble@gmail.com with the subject line CSE 123B Project 3 submission.