A TCP pacing implementation for NS2

(Part of the NS-2 enhancement project)

Apr 2006

This is a patch that provides various options of TCP pacing in NS-2. The patch is for NS-2.28. You may need some modification if you want to install it for higher version.

Patch for NS-2.28:

The patch can be downloaded from here. It is for NS-2.28. To install the patch, you need to take the following steps, assuming you have successfully installed and run NS-2.28 in your computer:

Copy the patch to ns-allinone-2.28/ns-2.28
In the directory of ns-allinone-2.28/ns-2.28 , run: make clean
In the directory of ns-allinone-2.28/ns-2.28 , run: patch -p1 < ns-pacing.patch
(Optional) delete the patch file by rm ns-pacing.patch
recompile the ns2 by make and make install

The patch changes the following files:

tcp/tcp.h: to add more control variables and state variables
tcp/tcp.cc: to add the major part of pacing implementation and hooks to the TCP
tcp/tcp-fack.h: to add hooks to TCP-Fack
tcp/tcp-fack.cc: to add hooks to TCP-Fack
tcp/tcp-reno.cc: to add hooks to TCP-Reno
tcp/tcp-sack1.cc: to add hooks to TCP-Sack1
tcl/lib/ns-default.tcl: to add default values to control variables

Usage:

1. Normal Usage:

The major control variable is pace_packet_.

This variable controls if the pacing is activated or not, and in which mode the pacing is activated. The following table shows the valid values for pace_packet_.

Value	Functions	Color in figure
0	(default) no pacing	Red
1	traditional pacing. This option allows TCP to pace the packet in a rate of cwnd/RTT (packet/sec).	Green
2	aggressive pacing. This option predicts the maximum value of congestion window at the end of this RTT (pCwnd). And pace the packet in a rate of pCwnd/ RTT (packet/sec)	Blue

The following figure shows the difference of these three options. The X-axle is time; Y-axle is the sequence numbers of packets sent by a TCP flow. Each point in the figure corresponds to one packet sending event. We can see that the traditional pacing will slow down itself gradually.
The scripts to generate this figure can be found at the example directory.

Sending sequence of different pacing options

2. Advanced Usage (which means even more risky!)

random_pace_: Random Pacing.
This pacing algorithm sends packets at a random momoent, uniformly distributed over the interval of [-0.4cwnd/RTT, +0.4*cwnd/RTT] around the time that a packet is paced to send in regular pacing.

Value	Functions
0	turn off random pacing (default)
1	turn on random pacing

pure_rate_control_: Pure Rate Control.
This option allows the TCP to send packets in pure rate control, without the constraint of cwnd. The rate that each packet is sent out is cwnd/RTT.

Value	Functions
0	turn off pure rate control (default)
1	turn on pure rate control

ack_counting_: Ack Couting RTT Boundary Estimator
NS-TCP uses per-ack actions to grow congestion window:
cwnd=cwnd+1/cwnd equation in congestion avoidance state;
cwnd=cwnd+1 equation in slow start state.
With pacing, this function will be slow down since the return of ack is slower, hence the packet sending rate is also slow down, leading to a positive loop in slowing down the rate.
Ack Couting RTT Boundary Estimator counts the number of acked packets, and compares it to the cwnd. Hence it can detect when a RTT is finish. And it changes the per-ack action into per RTT action:
cwnd=cwnd+1 equation in congestion avoidance state;
cwnd=cwnd*2 equation in slow start state.

Value	Functions
0	turn off Ack Counting RTT Boundary Estimator (default)
1	turn on Ack Counting RTT Boundary Estimator

pace_loss_filter_: Loss Filter for Pacing
Due to the evenly spread out packet sending event, pacing TCP can sample the loss signal much better, and hence see more packet loss in comparison to non-paced flows. This option allows pacing TCP to filter some loss event in some way.

Value	Functions
0	turn off Loss Filter for Pacing (default)
Positive number	turn on Loss Filter for Pacing. This filter is a time filter. TCP pacing regards any observed loss in pace_loss_filter_ RTTs as a single loss event.
Negative number	turn on Loss Filter for Pacing. This filter is a cwnd reduction filter. For each observed packet loss, the window reduction of pacing TCP will be 1/(-pace_loss_filter) of the window reduction of non-paced TCP.

inflation_ratio_: Congestion Window Inflation for Pacing.
Pacing TCP is constrained by both pacing rate and window. When pacing allows a packet to send, the window might not allow any packets to send, and hence waste the pacing token. This happens more often in loss recovery. Congestion Window Inflation allows pacing to inflate the congestion window temporarily when pacing rate allows the packets to be sent.

Value	Functions
0	turn off Congestion Window Inflation (default)
Positive number	turn on Congestion Window Inflation: the cwnd can be inflated to at most 1/inflation_ratio_ of the original cwnd.

Known Problems:

WARNING: This is a piece of work is highly preliminary. Users shall use it at their own risk, and verify its results carefully before drawing any conclusions from the results.
There are a list of known problems:

The pacing algorithm does not work with overhead_ option. If you want to use overhead_ with pacing, use the random_pace_ option, too.
As shown in the figure, aggressive pacing does not estimate the cwnd in the future very accurately, hence still results in some degree of burstiness.
Any functions in the Advanced Usage parts are highly experimental and are subject to frequent changes.

Acknowledgment:

This work is inspired and greatly helped by Prof. Pei Cao at Stanford and by Prof. Steven Low at Caltech. Many thanks to them!