CSS 432
Program 3: Additive Increase/Multiplicable Decrease
Spring Quarter 2004
Professor: Munehiro Fukuda
Assigned on 4/29/04 and due on 5/13/04

1. Purpose

2. Congestion Control Algorithms

1. Original RTT Estimation:
   Refer to the textbook pages 397-398. The origianl RTT estimation uses the following formula:

      EstimatedRTT = a * EstimatedRTT + ( 1 - a ) * SampleRTT
      Timeout = 2 * EstimatedRTT
   

   Your implementation is to initaialize EstimatedRTT with 1000usec and to set a to 0.85. Follow the RTT sampling algorithm shown in below:
   • Get the time when a message is created, (by calling gettimeofday( ))
   • Store this timestamp in the message, (specifically, tv_sec in message[1] and tv_usec in message[2]) and send it to a server.
   • Assume that the server returns the same timestamp in its acknowledgment, (specifically, tv_sec in ack[1] and tv_usec ack[2]).
   • Get the lap time between this acknowledgment's timestamp and the current time, (specifically, call Timer.lap( ack[1], ack[2] )).
   • Use this lap time as SampleRTT in the above formula.

2. Karn/Partridge Algorithm:
   Refer to the textbook pages 398-399. The Karn/Partridge algorithm does not sample the RTT for retransmitted messages. Therefore, whenever your implementation retransmits a previous message, it should not record the current timestamp in this retransmitted message. To distinguish it from other transmitted messages, you should modify the RTT sampling algorithm specified above:
   • Do not get the current time. Instead, store a meaningless time value in the retransmitted message, (specifically, -1 in message[1] and message[2]).
   • Do not sample or estimate RTT whenever you hav received an acknowledgment with a meaningless timestamp.

3. Slow Start:
   First of all, like HW2, the window size means the number of messages but not bytes. Similary, congestionThreshold defined below is referred as of the number of messages. Read the textbook through pages 471-473. The slow start algorithmn increments the window size by 2 whenever it receives a new acknowledgment as far as it is below the congestion threshold. To use this algorithm, define the valuable congestionThreshold as follows:

        int congestionThreshold = maxWindowSize;
   
        where windowSize is given by the main function indicating the maximum
        window size.
   

   This means that the very first packet transfers follow slow start until the current window size reaches congestionThreshold that has been initially set to the maximum window size. This increase the current window size rapidly until the first network congestion is detected.

4. AIMD:
   Refer to the textbook page 468-471. Once the current window size reaches congestionThreshold, it must be incremented by 1 but not 2 whenever the AIDM algorithm receives a new acknowledgment. This additive increment is repeated unless a congestion is detected.

   In general, A congestion is detected if packets began to be dropped off. In our implementation, we assume that a congestion has occurred if the number of unacknowledged messages has reached the current window size and the client hasn't received any new acknowledgment within TIMEOUT that has been recently estimated with our RTT estimation.

   Upon detecting a congestion, the AIMD algorithm sets congestionThreshold to half of the current window size, and then resets the window size to 1. In this way, it restarts slow start until another congestion takes place.

5. Sliding window:
   We uses the sliding window algorithm implemented in HW2, where a cilent keeps writing a message sequence number in message[0] and sending message[] as far as the number of in-transit messages is less than the ucrrent window size, while the server recieves message[], memorizes this message's sequence number in its array and returns a cumulative acknowledgment.

3. HW3 Test Program

1. Case 1: Unreliable test is the same as hw2.cpp.
2. Case 2: Stop-and-wait test is the same as hw2.cpp except it counts the average number of packets retransmitted, when repeating a 20,000-message transfer 10 times.
3. Case 3: Sliding window is exactly the same as hw2 and repeats evaluating an elapsed time for 20,000-message transmission as increasing the window size from 0 to 30.
4. Case 4: Sliding window + congestion is a new test case that uses hw2's clientSlidingWindow( ) function but focuses on the average elapsed time for the window size = 30 and counts the average number of packets retransmitted, when repeating a 20,000-message transfer 10 times.
5. Case 5: Slow start AIMD test + congestion follows the all congestion control algorithms explained above. The test measures the average elasped time and counts the average number of packets retransmitted, when repeating a 20,000-message transfer 10 times. This test case asks a user if he/she wants to activate or inactivate the RTT estimation algorithm. If it is inactivated, the test assumes that timeout is statically set to 1000usec.

4. udp.o Object File

This new version of serverEarlyRetrans( ) function is used in the test case 4 and 5 of the main function. It sends the client an acknowledgment formatted below:

   int acknowledgment[3];
   acknowledgment[0] = message[0];  // the original message sequence
   acknowledgment[1] = message[1];  // the original message's tv_sec timestamp
   acknowledgment[2] = message[2];  // the original message's tv_usec timestamp

5. Statement of Work

1. hw3.cpp
2. UdpSocket.h
3. UdpSocket.cpp
4. Timer.h
5. Timer.cpp
6. udp.o

   $ g++ UdpSocket.cpp Timer.cpp udp.o aimd.cpp hw3.cpp -o hw3

Client side example:
   $ ./hw3 uw1-320-10 > data
   Choose a testcase
      1: unreliable test
      2: stop-and-wait test
      3: sliding windows
      4: sliding windows + congestion
      5: slow-start-aimd test + congeestion
   --> 5
   use RTT estimation? (y or n): y

Server side example:
   $ ./hw3 

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

Server side example:
   $ ./hw3 2> data2