CSE461 Homework 2

Assigned: 1/12/06
  1. Part 1: 1/22/06 @ 11.59pm.
  2. Parts 2 and 3: 1/20/06 @ 11.59pm.

There are three parts to this assignment. The first is a moderately difficult programming assignment. The second is a straightforward programming assignment. The third is a small set of questions drawn from the book. I recommend you start early.

1. Stop and Wait


You will implement a reliable datagram protocol using the stop-and-wait (also known as alternating bit) protocol.

A message is considered sent once it has been delivered and acknowledged. An unacknowledged message is resent after a timeout. After a finite number of resends, an error is reported.


Implement the stop-and-wait protocol using Unix's UDP Sockets Interface. Your protocol should run as a library that is linked into a client program and a server program. It should extend the sockets API with three new routines:
     reliable_sendto(int s, const 
			void *msg, size_t len, int flags,
         		const struct sockaddr *to, socklen_t tolen);

     reliable_recvfrom(int s, void *buf, 
				size_t len, 
				int flags, struct sockaddr *from,
         			socklen_t *fromlen);

     void reliable_config(int retries, int timeoutms);
These first two routines are modeled on the existing sendto and recvfrom APIs. See the man pages for more information.

reliable_sendto should return the number of characters sent, or -1 if an error occurred. In addition to the standard UNIX errors that can occur on a sendto, you should set errno to ETIMEDOUT in the event that the sender receives no acknowledgment after attempting to send multiple times. See intro(2) for more information on system call error numbers.

The third routine allows you to parameterize the number of retransmissions that should occur when appropriate acknowledgements are not forthcoming in a window of timeoutms milliseconds. By default, your protocol should retransmit 4 times with a timeout of 10 milliseconds. A timeout of 0 ms disables retransmissions and causes reliable_send to never report an unacknowledged datagram. A retries of 0 also disables retransmissions, but delays at least timeoutms before returning. Datagrams are never reported as lost. k

You should put your protocol implementation in a file called reliable.c and link it in with a client and server program. Your main client program should be called "swclient.s" and your server program should be called "swserver.c." Each is to be executed from the command line on different computers:

notattu2: ./swclient host portnum maxdgramsize nretries timeoutms
attu2: ./swserver portnum  

You may find it helpful to run both on the same computer (in different windows) during development.
The client reads data from stdin and sends it to the server. The client's non-optional arguments indicate the target address (host, portnum), the maximum allowable size of reliable datagram, the number of retries for each packet, and the timeout in milliseconds that should be used to clock a retransmission.

The server displays the data it receives on the UNIX stdout channel. The server's portnum is an optional specifier indicating on which port the server should receive messages. Without this optional specifier, the server should be willing to accept any port from the OS (bind to sin_port = 0). This simplifes the sharing of the port space. See here for information on using bind.


First, measure the underlying reliability of the network by disabling retransmissions and measuring loss (the difference between the number of packets sent on the client and the number received on the server) as a function of the timeout. Use timeouts ranging from 0ms to .5 seconds, and datagram sizes of 512 bytes and 8k. Show your measurements on a LOSS graph of packet loss as a function of timeout with one line for each datagram size.

Second, measure throughput as a function of timeout for 5 different datagram sizes: 10 bytes, 512 bytes, 2k, 8k, and 64k. To measure throughput, you should copy a large file from the client to the server to ensure that your timing covers many round trips. Consider timeouts ranging from small to medium to large (10, 50, 500 ms). Show your measurements in two graphs: Include a THROUGHPUT graph with one line for each of the different datagram sizes where the x-axis is your timeout, and the y-axis is your measured throughput. Include a RETRANSMISSION graph, where the y-axis is the total number of retransmissions that the client performed.

Include a thoughtful discussion and analysis of the results of no more than one page. Don't forget to make clear the description of the experimental setup (eg, machine names, types, speeds, network speed, etc.).


What to turn in?

Turn in a tar file called "reliable.tar" that contains a directory called Reliable. This directory contains your source code and Makefile, a file called results.pdf that contains your evaluation, and a file called README that contains any information we might need in evaluating your solution. For example, bugs and limitations should be included in the README.

2. Statistical Multiplexing. How lucky can you get?

In class, I presented an analysis of the likelihood of running out of bandwidth for a statistically multiplexed channel. As I mentioned, my analysis was a little broken because I assumed that the number of ways in which "exactly k of n" transmitters could occur simultaneously was the same as "at least k of n." This is wrong, since there are fewer ways in which exactly k of n can occur relative to at least k of n.

Write a program that properly computes the probability of running out of bandwidth given that there are more ways in which "at least k of n" nodes can be transmitting than there are "exactly k of n." You should use the same parameters that I used in lecture. Your program should produce a table of 2 columns. The first column is the number of nodes on the network, and the second column is the probability that the network is overcommitted.

What to turn in?

Turn in a tar file called "lucky.tar" that contains a directory called Lucky. This directory contains the source code for your program and a file called "lucky.typescript" that shows it running. You may write the program in any language you like. As well, the directory should contain a README that includes any bugs or limitations.

3. By the book.

Please do these questions from the book:

What to turn in?

Turn in a tar file called "SolutionsHW2.tar" that contains a directory called SolutionsHW2. This directory contains an ascii file called "solutions.txt" that contains the solutions to the five questions.

Grading Criteria

Each section will be graded independently on an integral scale of 0 to 4, with the first part having a weight of 3 and the second and third parts having weights of 1. As with all assignments in this class, the evaluation will be based on the extent to which the solution demonstrates an understanding of each problem's key concepts: