CSS 432 - Program 2: Sliding Window

CSS 432
Program 2: Sliding Window
Professor: Munehiro Fukuda
Due date: See the Syllabus

1. Purpose

This assignment implements the sliding window algorithm and evaluates its performance improvement over 1Gbps network. You are to observe the performance improvement of 20,000 packet transfers as increasing the size of a sliding window.

2. UDP

UDP is a connectionless, unreliable datagram transfer protocol. To implement the sliding window algorithm, we use UDP that brings up some typical network problems we have to address: loss and disorder of packets transferred between a client and a server. While you can send a variable size of data with UDP as far as it is less than 8Kbytes, we sends a packet whose size is fitted to the Ethernet MTU, (i.e., 1500bytes.) Excluding the fragment header, the actual data size we can use for UDP is 1460bytes. This way avoids further fragmentation at the data link layer and thus we can accurately implement the sliding window algorithm using UDP. Since it is not our major concern to explore UDP, use the UdpSocket class which you can find in ~css432/hw2. Also, you can use 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. 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 if there are no data to receive. Call this method if you need to prevent your program from being blocked when receiving data.
int sendTo( char msg[], int length )	Send msg[] of the length size from a client to a server whose address must be set by setDestAddress( ) a priori. If you send a single char variable, say c, your call should be sendTo( &c, int sizeof(c) ).
int recvFrom( char msg[], int length )	Receive data into msg[] of the length size. This method can be both used to receive a message from a client as well as an acknowledgment from a server. If you receive a single char variable, say c, your call should be recvFrom( &c, int 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, call 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 that sets the current date information in tv_sec and tv_usec.
long lap( )	calls gettimeofday to get the current date information and computes the lap from the time when the last start( ) method has been called.
long lap( long oldTv_sec, long oldTv_usec )	calls gettimeofday to get the current information and computes the lap from the time specified in oldTv_sec and oldTv_usec
long getSec( )	Retrieve its internal tv_sec variable content that has been set by the last start method.
log getUsec( )	Retrieve its internal tv_usec variable content that has been set by the last start method.

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[], 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[] ); repeats max (=20,000) times of sending message[] to a given server using the sock object.
- void serverUnreliable( UdpSocket &sock, const int max, int message[] ); repeats max (=20,000) times of receiving message[] from a client using the sock object. However it does not return any acknowledgment to the client.
This test may hang the server due to the drop-off of some UDP packets on their way to the server.
Case 2: Stop-and-wait test follows the stop-and-wait algorithm in that a client writes a message sequence number in message[0], sends message[] and waits until it receives an integer acknowledgment from a server, while the server receives message[], copies the sequence number from message[0] to an acknowledgment, 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[] ); repeats sending message[] and receiving an acknowledgment at a client side max (=20,000) times using the sock object. If the client cannot receive an acknowledgment immediately, it should start a timer. If a timeout (= 1500usec) has happened, 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 of underlying network. This is because the client must wait for an acknowledgment every time it sends out a new message.
Case 3: Sliding window follows the sliding window algorithm in that a client keeps writing a message sequence number in message[0] and sending message[] as far as the number of in-transit messages is less than a given window size, while the server receives message[], memorizes this message's sequence number in its array and returns as its acknowledgment the minimum sequence number of messages it has not yet received, (called a cumulative acknowledgment). NOTE! the window size in our assignments means the number of messages but not the number of bytes. You are to implement this algorithm in the following two functions:
- int clientSlidingWindow( UdpSocket &sock, const int max, int message[], int windowSize ); repeats sending message[] and receiving an acknowledgment at a client side max (=20,000) times using the sock object. As described above, the client can continuously send a new message[] as incrementing its sequence number as far 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 # of unacknowledged messages reaches windowSize, the client should start a timer. If a timeout (= 1500usec) has happened, it must send the message with the minimum sequence number among those which have not yet been acknowledged. The function must count the number of messages retransmitted and return it to the main function as its return value.
- void serverEarlyRetrans( UdpSocket &sock, const int max, int message[], int windowSize ); repeats receiving message[] and sending an acknowledgment at a server side max (=20,000) times using the sock object. Every time the server receives a new message[], it must memorizes this message's sequence number in its array and returns a cumulative acknowledgment
This test may get close to the peak performance of 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

Code in udp.cpp the following four functions that have been outlined above:

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, in which case you don't have to use all of these arguments as a matter of course. Change the hw2.cpp's PORT definition 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 completes in success, you will get the hw2 executable file. Run this program both on a client and a server side. 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, and 3 for evaluating the performance of the three different test cases respectively. The main function in hw2.cpp will store 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 hope to store cerr information in the data file, you should type:

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

Server side example:
   $ ./hw2 2> data2

For the test case #1, all you have to do is simply repeat running the program several times and observe if it may hang up due to the drop-off of some UDP messages.

For the test case #2, run your program over 1Gbps network and obtains an elapsed time for each network. To view those results with gnuplot, you need to edit the udp.plt file. Replace TTTTT with a elapsed time for 1Gbps network stop-and-wait performance test.

   plot "1gbps_sw.dat" title "1gbps sliding window" with linespoints, 
   TTTTT title "1gbps stopNwait" with line

For the test case #3, conduct performance evaluation over 1Gbps networks respectively for the window size = 1 to 30. Store their performance results in 1gbps.dat. To view all results using gnuplot, type:

   $ gnuplot upd.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. You have to turn in the following materials to CollectIt. No email submission is accepted.

Criteria	Percentage
Documentation of (1) a stop-and-wait and (2) a sliding window implementation, including explanations and illustrations in details	3pts(15%)
Source code that adheres good modularization, coding style, and an appropriate amount of comments. The source code is graded in terms of (1) clientStopAndWait( )'s message send and ack receive, (2) clientStopAndWait( )'s timeout and message re-transfer, (3) serverReliable( )'s message receive and ack send, (4) clientSlidingWindow( )'s message transfer and ack receive, (5) clientSlidingWindow( )'s timeout and duplicated message re-transfer, (6) serverEarlyRetrans( )'s cumulative acknowledgment, and (7) comments. Write as many comments as possible, otherwise the professor/the grader cannot keep track of these complicated algorithms.	7pts(35%)
Execution output such as a snapshot of your display/windows. Type `import -window root X.jpeg; lpr -Puw1-320-p1 X.jpeg` on a uw1-320 linux machine. Or, submit partial contents of standard output redirected to a file. You don't have to print out all data. Just one page evidence is enough.	1pts(5%)
Performance results in graph that prints out the tcp.ps file. The correctness is evaluated in terms of (1) stop-and-wait performance over 1Gbps and (1) sliding window performance over 1Gbps.	4pts(20%)
Discussions should be given for (1) your theoretical window size, (2) your empirical window size, and (2) any notable difference in the number of messages retransmitted between stop-and-wait and sliding window algorithms.	5pts(25%)
Total	20pts(100%)

6. FAQ

This FAQ page may answer your quetions. Click here