[e2e] [help] TCP rate control on Linux?

Paolo Castagna castagna at cefriel.it
Fri Apr 27 05:04:49 PDT 2001


Hi, 
I'm an Italian student and I'm doing a Master Thesis on TCP rate 
control. 

TCP rate control is a new technique for transparently augmenting 
end-to-end TCP performance by controlling the sending rate of a TCP 
source. The sending rate of a TCP source is determined by its window 
size, the round trip time and the rate of acknowledgments. 
TCP rate control affects these aspects by modifying the ack number 
and receiver window fields in acknowledgments and by modulating the 
acknowledgment rate. From a performance viewpoint a key benefit of 
TCP rate control is to avoid adverse performance effects due to 
packet losses such as reduced goodput and unfairness or large spread 
in per-user goodputs. Further, TCP rate control positively affects 
performance even if the bottleneck is non-local and the end-host 
TCP implementations are non-conforming. [see article below] 

I would like to know your opinions about that, and if there is 
already something similar in the Linux world. I've already see 
the kernel sources but I didn't find something like that. Yes, 
I know CBQ, traffic shaping (classic), netfilter. 

I'll appreciate suggestion about how to implement such ideas, 
TCP rate control, I mean, on Linux, specifically in the 
kernel 2.4.x 

There are two algorithms in the TCP rate control technique, as 
describe in the paper below, may be usefull for you to have the 
algorithms: 

--------------------------------------------------------------------- 

Algorithm 1 - Rate Allocation Algorithm 

The goal of this algorithm is to allocate max-min fair rates to 
competing TCP flows. Initially, equal rate allocations are given to 
all competing flows. Then sending rates of flows are estimated by 
maintaining an exponential average over a rate sampling interval. 
When a flow does not to utilize its allocation, it is labeled as 
bottlenecked. Excess allocation is stripped off from all such 
bottlenecked flows and allocated to non-bottlenecked or hungry flows. 
This step is repeated until there is no residual bandwidth to 
allocate or all flows are bottlenecked. This algorithm is invoked 
every time a new flow begins, a flow terminates or when the rate 
sampling interval expires. The resulting rate allocations are 
stored into a table. 

--------------------------------------------------------------------- 

1. For each flow i, let Ri be the measured rate 
   and Ai be the allocated rate. 

2. If N is the total number of flows and B is the bottleneck 
   capacity, the initial allocation for each flow i is 

     Ai = B / N                                      (2) 

3. If Ri < (p * Ai) for some satisfaction percentage p 
   (a statically chosen parameter), then mark flow i as 
   bottlenecked, else mark it as hungry. 

4. Let U be the aggregate residual bandwidth i.e the 
   bandwidth which remains unutilized by the bottlenecked 
   flows. 

5. Distribute this residual bandwidth evenly over all the 
   hungry flows. If H is the total number of hungry flows, 
   the new allocation for a hungry flow j is given by 

     Aj = Aj + (U / H)                               (3) 

6. For each bottlenecked flow k the new allocation is 
   given by 

     Ak = (Ak + Rk) / 2                              (4) 

   So for bottlenecked flows, the allocation approaches 
   the measured rate over successive iterations of the 
   algorithm. 

--------------------------------------------------------------------- 

About this algorithm, I've a problem... how can I measure the rate 
Ri for each TCP flow? I've found NeTraMet on this URL: 
http://www.auckland.ac.nz/net/Accounting/ntm.Release.note.html 
... and I've also read the discussion about that on linux-kernel 
mailing list. Where is the best place to make a such thing? 
I've thought in /net/core/dev.c in function dev_queue_xmit. 
And, again, how can I associate the rate Ri to each TCP flow? 

--------------------------------------------------------------------- 

Algorithm 2 - Rate Enforcement Algorithm 

This algorithm enforces the rate allocation by converting the rate 
to a window value. Additionally, it spaces out the acknowledgments 
of a flow, so that they are evenly distributed over its RTT. 

--------------------------------------------------------------------- 

1. For each flow i let 

     wi = the calculated window size in units of packets. 
     Di = the inter-ack spacing in seconds. 
     RTTi = the round trip time (RTT) of flow i, ideally 
     not including queuing delays, in seconds. 
     MSSi = the maximum segment size of flow i, in bytes. 
     Ai = the rate allocation in bytes/s. 

2. Observe that for each flow i, we have: 

     wi * MSSi = Ai * RTTi                           (5) 

   So the window value can be calculated as, 
   
     wi = (Ai * RTTi) / MSSi                         (6) 

3. The inter-ack spacing time (RTTi/wi) can also be 
   obtained from equation (5): 

     Di = RTTi / wi = MSSi / Ai                      (7) 

4. For each flow i, acks (if available) are clocked out 
   at intervals of Di with the receiver window field set 
   to Wi. 

5. The receiver window field of the ack of flow i is set as: 

     Wi = min(wi * MSSi , actual receiver window)    (8) 

6. The ack number field in the header is determined based 
   upon two variables (max and min sequence number) used to 
   denote the ack queue. In the common case, the ack number 
   would be chosen to progress by one MSSi. 
   
--------------------------------------------------------------------- 

About this algorithm, where is, for you, the best place 
where to do a such thing? In general I'd like to do only minor 
changes possible in the kernel sources, and I would like to 
implement a module for TCP rate control. 
I've also found an usefull paper by Glenn Herrin, I've try the 
example with the kernel v2.4.3 but I've some problem with it: 
when I export a symbol from the kernel, using EXPORT_SYMBOL and I 
try to use it from a module I have the error: "undefined symbol in 
mymodule" even if it's listed in /boot/System.map 

--------------------------------------------------------------------- 

Papers: 

o Shrikrishna Karandikar, Shivkumar Kalyanaraman, 
  Prasad Bagal, Bob Packer, 
  "TCP Rate Control", 
  Computer Communication Review, a publication of ACM SIGCOMM, 
  volume 30, number 1, January 2000. ISSN # 0146-4833. 
  URL:
http://www.acm.org/sigcomm/ccr/archive/2000/jan00/ccr-200001-kara.html 

o Glenn Herrin, 
  Linux IP Networking, 
  A Guide to the Implementation and 
  Modification of the Linux Protocol Stack 
  TR 00-04, May 31, 2000 
  URL: http://kernelnewbies.org/documents/ipnetworking/ 

o Others interesting papers: 
  URL:
http://www.ecse.rpi.edu/Homepages/shivkuma/research/papers-rpi.html#tcp 

--------------------------------------------------------------------- 

Commercial products based on idea of TCP Rate Control: 

o Packeteer - http://www.packeteer.com/ (*) [nasdaq: PKTR] 
o Allot - http://www.allot.com/ 

(*) I know about patents. 

--------------------------------------------------------------------- 

I beg your pardon for the lenght of this message, and also for my 
bad english :/ I hope this is the right place for a such discussion, 
if not, please, excuse me, and if you know send me some references. 

Greetings, 
Paolo Castagna. 

--------------------------------------------------------------------- 

PS: 
Keywords:  TCP, TCP Rate Control, Congestion Control, Ack Bucket. 
Not pertinet: ECN, SACK, Tocken Bucket, Queueing Disciplines, CBQ, 
WFF, Filters, RED, ... 




More information about the end2end-interest mailing list