Term Project, CIS 510/410, Internet Multimedia (W03)

Simulation Project

Internet Multimedia
CIS 510/410
Winter 2003

Part I (Due Mar 13th, In Class)

For this part of your project, you develop and evaluate a TCP-friendly rate-based congestion control protocol using the network simulator. The protocol uses Additive Increase, Multiplicative Decrease (AIMD) algorithm for adjusting transmission rate. You can simulate the protocol entirely in tcl.

1) Protocol Description

Sender functionality:

The sender sends data packet and receives per-packet Acknowledgment (ACK) from the receiver. The sender includes a monotonically increasing sequence number in each data packet, and the receiver copies sequence number of each data packet in its ACK packet. Thus the ACK packets are used to measure sample round-trip-time (RTT) where an RTT sample is the difference between departure time of a packet and arrival time of its ACK. The RTT samples are used to estimate timeout value for loss detection as we describe later.

The sender regulates its transmission rate by adjusting the inter-packet-gap (IPG). The sender sends one packet per IPG, and uses the following strategy to adjust IPG:

If a loss event is detected, then the transmission rate is multiplicatively decreased,

IPG = Beta * IPG, Beta > 1
If no loss event occurs, then the transmission rate is linearly increased once per smoothed RTT (SRTT),

IPG(i+1) = (IPG(i)*SRTT)/[Alpha*IPG(i)+SRTT], Alpha > 1.
* Alpha and Beta are input parameters. Alpha controls slope of linear increase, and Beta is the backoff factor for exponential decrease.

SRTT is an exponentially weighted moving average of RTT samples that is calculated as follows:

SRTT(i+1) = (1 - a) SRTT(i) + a * RTT, a = 0.75

We use SRTT because RTT samples could exhibit rapid variations. All losses that occur during one RTT are considered part of a single loss event. Thus the rate should be decreased at most once per RTT. To group losses during one RTT and react to them just once, you can use the following mechanism: when a loss is detected, the sender can record the sequence number of the last transmitted packet, and ignore any lost packet with a smaller sequence number. For example, assuming when the sender detects that sequence number 11 is lost, it has already sent sequence number 23. This means that there are already 12 packets (23 - 11) in flight. The sender will react to the loss of sequence number 11 by doubling the IPG, but it does not react to loss of any other packets with sequence number less or equal to 23.

The sender uses two parallel mechanisms to detect losses: 1) timer-based loss detection, and 2) ack-based loss detection.

The timer-based loss detection mechanism considers a transmitted packet as lost if the packet is not acknowledged after a timeout period from its departure time. Thus, the sender should keep track of departure time of each transmitted packet. Timeout period should be set to 4*SRTT.
The ack-based loss detection mechanism simply uses incoming ACKs to detect a lost packets. When ACK for sequence number N arrives, any outstanding packets with sequence number less than (N-3) is considered lost.

When an ACK arrives, the sender: 1) measures an RTT sample, removes the record for the acknowledged packet, 2) updates SRTT , and 3) performs ack-based loss detection. Before sending a packet, the sender 1) performs timer-based loss detection (using the current timeout value), 2) sends a packet and create a record (including packet sequence number and departure time), and 3) schedule transmission of the next time for an IPG later. The receiver simply acknowledges data packets.

Sample tcl codes

cc.tcl, sample code for sender and receiver
timers.tcl, some basic timer utilities
test-cc.tcl, a test program

2) Protocol Evaluation

You need to perform several evaluation on your CC protocol. For all the evaluations use simple topology shown here. For tcp-friendly simulation, we use the exact same topology but half of the flows are TCP flows, as shown here. For all the simulation use the following default parameters except when other parameters are requested. Alhpa = 1
Beta = 2
bottleneck delay = 20 ms, bottleneck RTT = 40ms
Sidelink delay = 3ms, Sidelink bandwidth = 10Mbps
Duration of simulation = 60 sec

A. Intra-protocol Fairness

To examine fairness among co-existing CC flows, you need to run 6 separate simulations with n = 2, 5, 10, 20 and 50 co-existing CC flows. The following results should be presented:

A.1) Average bandwidth for each flow in each simulation. Plot a graph where X axis is number of flows in a simulation (i.e. 2,5,10, 20,50) and Y axis is the average bandwidth of a flow in that simulation. So you have 2 point with x=2, 5 points with x=5, etc. This graph shows how average per-flow bandwidth changes with number of co-existing flows. More details on how to setup the simulation is provided below
A.2) Variations of per-RTT average bandwidth for each flow. Plot variations of per-RTT average bandwidth for first and last CC flow in each simulation (i.e. flow 1, 2 for n=2, flow 1,5 for n = 5, etc) where X axis is time, Y axis is per-RTT average bandwidth of each flow. Some suggestions on how to measure per-RTT average bandwidth is described below.

B. TCP-friendliness

To examine fairness with co-existing TCP traffic, you need to repeat the simulations for intra-protocol fairness but replace half of the flows with TCP flows. You need to run 6 separate simulations with n = 2 (1tcp+1CC), 5(3tcp+2CC), 10(5tcp+5CC), 20(10tcp+10CC) and 50(25tcp+25CC) flows and present the following results:

B.1) Average bandwidth for each flow in each simulation. Plot a graph where X axis is number of flows in a simulation (i.e. 2,5,10, 20,50) and Y axis is the average bandwidth of a flow in that simulation. So you have 2 point with x=2, 5 points with x=5, etc. Note that average bandwidth of TCP and CC flows should be presented with different "dot types" in your graph. This graph shows how average per-flow bandwidth for both TCP and CC flows change with total number of co-existing flows. More details on how to setup the simulation is provided below
B.2) Variations of per-RTT average bandwidth for each flow. Plot variations of per-RTT average bandwidth for first CC and first TCP flows in each simulation where X axis is time, Y axis is per-RTT average bandwidth of each flow. Some suggestions on how to measure per-RTT average bandwidth is described below.

C. Effect of RTT

Repeat simulation B.1 and B.2, but double the RTT for half of TCP flows and half of CC flows. To increase RTT for a given flow, you should increase the delay on one of the sidelinks from 0.003 (3ms) to 0.02 (20 ms). This roughly doubles the overall RTT (i.e. (3+20+3)*2 --> (20+20+3)*2).

C.1) Average bandwidth for each flow in each simulation. Similar to B1.
C.2) Variations of per-RTT average bandwidth for each flow. Similar to B.2

D. Effect of Alpha and Beta

Run a simulation with 4, 8, 12, 20, 40 flows where 25% of flows are TCP and 75% of flows are CC. Divide CC flows into 3 groups with different (Alpha, Beta) values as follows, group1 (Alpha=1, Beta=2), group2 (Alpha=0.583, Beta=1.33), group3(Alpha = 0.865, Beta = 3). For example, for a simulation with 8 flows, use 2 TCP and 6 CC flows (2 group1, 2 group2, and 2 group3), etc. Note that all these pairs of Alpha and Beta values should lead to a TCP-friendly behavior. Present the following results

D.1) Average bandwidth for each flow in each simulation. Similar to B1.
D.2) Variations of per-RTT average bandwidth for each flow. Similar to B.2

E. Responsiveness

Repeat simulation D but add a cbr source that starts at time t=30 and stops at time t=40, and present the following results

E.1) Average bandwidth for each flow in each simulation. Similar to B1.
E.2) Variations of per-RTT average bandwidth for each flow. Similar to B.2

Misc.

Topology

Use simple topology shown here. For tcp-friendly simulation, we use the exact same topology but half of the flows are TCP flows, as shown here. Use the following parameters in your simulation:
All links are duplex with DropTail queue. Packet size for all flows should be 100 bytes. For side links on both sides use the following information:
s_bw = 10 Mbps, s_delay = 0.003 (3 ms)
.

For the bottleneck link, use the following parameters: b_delay = 0.020 (20 ms). Since number of flows vary among simulations, to ensure that each flow has sufficient amount of resources (bw and buffer) across all simulations, you need to proportionally adjust bandwidth and buffer size of the bottleneck link (between n0-n1) as follows (blink denotes bottleneck link):
blink_bw = bw-per-flow * no-of-flow, blink_buf(pkt) = [blink_bw * (blink_delay*2) * 4]/PktSize. Which specifies required buf size for the bottleneck link in terms of packets. Assume bw-per-flow: 0.08 Mbps. bw can be easily specified when you create a link as follows:
$ns duplex-link $n(0) $n(1) $b_bw $b_delay $b_type

To specify buffer size on a link, you can use the following command:
$ns queue-limit $n(0) $n(1) $blink_buf $ns queue-limit $n(1) $n(0) $blink_buf

As for packet size, use 100 byte per data packet and 40 bytes per ack packets. You can easily change packet size for a CC agent or TCP flow as follows:
set PKTSIZE 100
set snder [new Agent/Message/CC 1]
set rcver [new Agent/Message/Acker 1]
$snder set packetSize_ $PKTSIZE
$acker set packetSize_ 40

To measure per-RTT average BW of a TCP flow, you can use the same approach that we used in your first exercise, i.e. measure average bandwidth every 112 ms (20+20+3*4). For your CC flows, you can use a timer and periodically print no of packets that are sent by each CC flow into a file

Sample code

You can use this piece of tcl code to generate topology with Nmax nodes. All the above suggestions/parameters were already included in the sample code but you need to read it, understand it and verify it. NOTE: This code is intended to get you started but it has not been tested. Make sure to check it to ensure it does what it is supposed to do.

What to Submit

You should submit hard copy of requested graphs in class and email your tcl code (i.e. cc.tcl and test-cc.tcl) as attachments to your email before class on Tue 2/25.

Second part of your project will be online by 2/25th,

Last Update: 2/21/2003, reza@cs.uoregon.edu