CSS 432 - Program 2: Sliding Window

CSS 432
Program 2: Sliding Window
Instructor: Joe McCarthy
Due date: See the Syllabus

1. Purpose

In this assignment you will implement the stop-and-wait and sliding window algorithms and evaluate their performance in transferring 20,000 packets over 100Mbps and 1Gbps networks.

2. UDP

UDP (User Datagram Protocol) is a connectionless, unreliable transport layer (OSI layer 4) protocol which does not prevent loss or or re-ordering of messages. Since it is not our primary intent to explore the UDP protocol in this assignment, it is recommended that use the UdpSocket class which you can find in ~css432/hw2. Also, you may want to use the Timer class in the same directory for your implementation and performance evaluation.

UdpSocket Class

Methods	Descriptions
`UdpSocket( int port )`	A default constructor that opens a UDP datagram socket with a given `port`. Use the last five digits of your student ID as the port number.
`~UdpSocket()`	A default destructor that closes the UDP datagram socket it has maintained.
`bool setDestAddress( char ipName[] )`	Set the destination IP address corresponding to a given server `ipName` (e.g., "uw1-320-16"). This method must be called before sending the first UDP message to the server.
`int pollRecvFrom()`	Check if this socket has data to read. The method returns the number of bytes to read or 0 if no messages have arrived. In general, a program is blocked to receive data (e.g., using `recvFrom()`) if there are no data to receive. Call this method if you need to prevent your program from being blocked when receiving data.
`int recvFrom( char msg[], int length )`	Receive data into `msg[]` of size `length`. This method can be used both to receive a message from a client as well as an acknowledgment from a server. As an example, if you wish to receive a single `char` variable, say `c`, your call should be `recvFrom( &c, sizeof( c ) )`.
`int sendTo( char msg[], int length )`	Send `msg[]` of size `length` size from a client to a server (whose address must have been previously set by `setDestAddress()`). As an example, if you wish to send a single `char` variable, say `c`, your call should be `sendTo( &c, sizeof( c ) )`.
`ackTo( char msg[], int length )`	Send an acknowledgment from a server to a client. Prior to calling this method, a server must receive at least one message from a client, (i.e, have called `recvFrom()` at least one time).

Timer Class

Methods	Descriptions
`Timer()`	A default constructor that zero-initializes its internal `tv_sec` and `tv_usec` variables.
`start()`	calls `gettimeofday()` to get the current date information and saves it in `tv_sec` and `tv_usec`.
`long lap()`	calls `gettimeofday()` to get the current date information and returns the time elapsed since its `start()` method was last called.
`long lap( long oldTv_sec, long oldTv_usec )`	calls `gettimeofday()` to get the current date information and returns the time elapsed since the time specified by `oldTv_sec` and `oldTv_usec`.
`long getSec()`	Retrieve the internal `tv_sec` variable value, which was set by the last `start()` method call.
`long getUsec()`	Retrieve the internal `tv_usec` variable value, which was set by the last `start()` method call.

3. HW2 Test Program

Copy ~css432/hw2/hw2.cpp to your directory. This program instantiates sock, (i.e., a UdpSocket object), allocates a 1460-byte message[], and evaluates the performance of UDP point-to-point communication using three different test cases:

Case 1: Unreliable test simply sends 20,000 UDP packets from a client to a server. The actual implementation can be found in:
- void clientUnreliable( UdpSocket &sock, const int max, int message[] ): sends message[] to a given server using the sock object max (=20,000) times .
- void serverUnreliable( UdpSocket &sock, const int max, int message[] ): receives message[] from a client using the sock object max (=20,000) times. However it does not send back any acknowledgment to the client.
This test may hang the server due to some UDP packets being sent by the client but never received by the server.
Case 2: Stop-and-wait test implements the stop-and-wait algorithm, i.e., a client writes a message sequence number in message[0], sends message[] and waits until it receives an integer acknowledgment of that sequence number from a server, while the server receives message[], copies the sequence number from message[0] to an acknowledgment message, and returns it to the client. You are to implement this algorithm in the following two functions:
- int clientStopWait( UdpSocket &sock, const int max, int message[] ): sends message[] and receives an acknowledgment from the server max (=20,000) times using the sock object. If the client cannot receive an acknowledgment immediately, it should start a Timer. If a timeout occurs (i.e., no response after 1500 usec), the client must resend the same message. The function must count the number of messages retransmitted and return it to the main function as its return value.
- void serverReliable( UdpSocket &sock, const int max, int message[] ): repeats receiving message[] and sending an acknowledgment at a server side max (=20,000) times using the sock object.
This test may not reach the peak performance supported by the underlying network. This is because the client must wait for an acknowledgment every time it sends out a new message.
Case 3: Sliding window implements the sliding window algorithm, using the first element in the message[] for s storing sequence numbers and acknowledgement numbers.
- A client keeps writing a message sequence number in message[0] and sending message[] as long as the number of in-transit messages is less than a given windowSize
- The server receives message[], saves the message's sequence number (stored in message[0]) in a local buffer array and returns a cumulative acknowledgement, i.e., the minimum sequence number of messages it has not yet received (the SeqNumToAck as described in the textbook).
You are to implement this algorithm in the following two functions:
- int clientSlidingWindow( UdpSocket &sock, const int max, int message[], int windowSize ): sends message[] and receiving an acknowledgment from a server max (=20,000) times using the sock object. As described above, the client can continuously send a new message[] and incrementing the sequence number as long as the number of in-transit messages (i.e., # of unacknowledged messages) is less than windowSize. That number should be decremented every time the client receives an acknowledgment. If the number of unacknowledged messages reaches windowSize, the client should start a Timer. If a timeout occurs (i.e., no response after 1500 usec), it must resend the message with the minimum sequence number among those which have not yet been acknowledged. The function must count the number of messages (not bytes) retransmitted and return it to the main function as its return value.
- void serverEarlyRetrans( UdpSocket &sock, const int max, int message[], int windowSize ) receives message[] and sends an acknowledgment to the client max (=20,000) times using the sock object. Every time the server receives a new message[], it must save the message's sequence number in its array and return a cumulative acknowledgment (as described above).
[NOTE: the windowSize in this assignment refers to the number of messages, not the number of bytes].
This test may get close to the peak performance supported by the underlying network. This is because the client can send in a pipelined fashion as many messages as the server can receive.

4. Statement of Work

Copy the following files from ~css432/hw2 to your directory:

hw2.cpp
UdpSocket.h
UdpSocket.cpp
Timer.h
Timer.cpp
udp.plt

Complete implementations of the following four functions that have been outlined above in a separate file, udp.cpp:

int clientStopWait( UdpSocket &sock, const int max, int message[] )
void serverReliable( UdpSocket &sock, const int max, int message[] )
int clientSlidingWindow( UdpSocket &sock, const int max, int message[], int windowSize )
void serverEarlyRetrans( UdpSocket &sock, const int max, int message[], int windowSize )

Some functions might not use all arguments passed to them. Change the definition of PORT in hw2.cpp to the last five digits of your student ID, and thereafter compile them with g++ as follows:

 
$ g++ UdpSocket.cpp Timer.cpp udp.cpp hw2.cpp -o hw2

If a compilation succcessfully completes, you will get an executable named hw2. Run this executable on both a client and a server machine. The program will display the following messages to the standard error:

Client side example:
   $ ./hw2 uw1-320-10 > data

Server side example:
   $ ./hw2
   Choose a testcase
      1: unreliable test
      2: stop-and-wait test
      3: sliding window
   -->

Type 1, 2, or 3 to evaluate the performance of one of the three different test cases respectively. The main function in hw2.cpp will redirect the output showing the performance results in the data file. Use cerr to print out any debugging information or message sequence numbers. Don't use cout, otherwise your debugging and message sequence information will be mixed up with performance results in the data file. If you wish to store cerr information in a separate file, e.g., data1 or data2 (one for the client, one for the server), you should type:

Client side example:
   $ ./hw2 uw1-320-10 2> data1

Server side example:
   $ ./hw2 2> data2

For test case #1, all you have to do is simply repeat running the program several times and observe if it hangs due to the drop-off of some UDP messages, and the discrepancy between the iteration number and the sequence number of the message received by the server.

For test case #2, run your program over 100Mbps and 1Gbps networks respectively and obtains an elapsed time for each network. When running on the 100Mbps network, substitute 100mbps.dat for data in the example shown above; when running on the 1Gbps network, substitute 1gbps.dat for data in the example shown above.

For test case #3, conduct performance evaluations over 100Mbps and 1Gbps networks respectively for window sizes 1 thru 30. Store their performance results in 100mbps_sw.dat and 1gbps_sw.dat.

To view those results with gnuplot, you need to edit the udp.plt file. Replace XXXX and YYYY with the elapsed times for your 100Mbps and 1Gbps network performance tests for test case #2.

   plot "100mbps_sw.dat" title "100mbps sliding window" with linespoints, 
   "1gbps_sw.dat" title "1gbps sliding window" with linespoints, 
   XXXX title "100mbs stopNwait" with line, YYYY title "1gbps stopNwait" with line

To view all results using gnuplot, type:

   $ gnuplot udp.plt
   $ ps2pdf udp.ps
   $ evince udp.pdf

5. What to Turn in

The homework is due at the beginning of class on the due date via Catalyst.

Criteria	Points (pct)
Documentation, including explanations and illustrations in details, of a stop-and-wait implementation a sliding window implementation	3 pts (15%)
Source code that adheres good modularization, coding style, and an appropriate amount of comments. The source code is graded in terms of `clientStopAndWait()`'s message send and ack receive `clientStopAndWait()`'s timeout and message re-transmit `serverReliable()`'s message receive and ack send `clientSlidingWindow()`'s message transfer and ack receive `clientSlidingWindow()`'s timeout and duplicated message re-transmit `serverEarlyRetrans()`'s cumulative acknowledgment, appropriate comments	7 pts (35%)
Execution output showing your client code running test cases 2 and 3. You can use the `script` program suggested for the first programming assignment to create the output file, `hw2.output`.	1 pts (5%)
Performance evaluation that includes the plot of values (udp.pdf). The correctness is evaluated in terms of stop-and-wait performance over 100Mbps stop-and-wait performance over 1Gbps sliding window performance over 100Mbps sliding window performance over 1Gbps	4 pts (20%)
Discussion of the difference between 100Mbps and 1Gbps performance results in both algorithms, including differences in the number of messages retransmitted between stop-and-wait and sliding window algorithms. stop-and-wait algorithm sliding window algorithm	5 pts (25%)
Total	20 pts (100%)

6. FAQ

This FAQ page may answer your questions. Click here

7. Acknowledgment

This assignment is closely modeled on an assignment earlier specified by Professor Fukuda.