A TCP pacing implementation for NS2

(Part of the NS-2 enhancement project)

David X. Wei

Netlab @ Caltech

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:

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

The patch changes the following files:

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:

  1. The pacing algorithm does not work with overhead_ option.  If you want to use overhead_ with pacing, use the random_pace_ option, too.
  2. 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.
  3. 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!