AIMD High Speed TCP

AIMD:Additive Increase Multiplicative Decrease
増加は足し算・減少は掛け算

TCPは輻輳回避フェーズにおいて2つのパラメータを用いる．
AIMD( a, b )
a：増加パラメータ
b：減少パラメータ

aは1ACKごとにcwndの値をa増やす．
bはパケットロス時にcwndの値にbかける．

Reno(NewReno)ではa=1，b=0.5となっている．
High Speed TCPにおいては，cwnd(t-1)に依存してaとbは決定される．

      | Congestion      | Packet Loss
      |     Avoidance   |
------+-----------------+-----------------
      | cwnd(t)         | cwnd(t)
      | =cwnd(t-1)+a(w) | =cwnd(t-1)*b(w)
------+-----------------+-----------------
Reno  | a=1             | b=0.5
------+-----------------+-----------------
HSTCP | cwnd(t-1)  a(w) | b(w)
      | ---------  ---- | ----
      |       38     1  | 0.50
      |      118     2  | 0.44
      |      221     3  | 0.41
      |      347     4  | 0.38
      |      495     5  | 0.37
      |      663     6  | 0.35
      |      851     7  | 0.34
      |     1058     8  | 0.33
      |     1284     9  | 0.32
      |     1529    10  | 0.31
      |     1793    11  | 0.30
      |     2076    12  | 0.29
      |     2378    13  | 0.28
      |     2699    14  | 0.28
      |     3039    15  | 0.27
      |     3399    16  | 0.27
      |     3778    17  | 0.26
      |     4177    18  | 0.26
      |     4596    19  | 0.25
      |     5036    20  | 0.25
      |     5497    21  | 0.24
      |     5979    22  | 0.24
      |     6483    23  | 0.23
      |     7009    24  | 0.23
      |     7558    25  | 0.22
      |     8130    26  | 0.22
      |     8726    27  | 0.22
      |     9346    28  | 0.21
      |     9991    29  | 0.21
      |    10661    30  | 0.21
      |    11358    31  | 0.20
      |    12082    32  | 0.20
      |    12834    33  | 0.20
      |    13614    34  | 0.19
      |    14424    35  | 0.19
      |    15265    36  | 0.19
      |    16137    37  | 0.19
      |    17042    38  | 0.18
      |    17981    39  | 0.18
      |    18955    40  | 0.18
      |    19965    41  | 0.17
      |    21013    42  | 0.17
      |    22101    43  | 0.17
      |    23230    44  | 0.17
      |    24402    45  | 0.16
      |    25618    46  | 0.16
      |    26881    47  | 0.16
      |    28193    48  | 0.16
      |    29557    49  | 0.15
      |    30975    50  | 0.15
      |    32450    51  | 0.15
      |    33986    52  | 0.15
      |    35586    53  | 0.14
      |    37253    54  | 0.14
      |    38992    55  | 0.14
      |    40808    56  | 0.14
      |    42707    57  | 0.13
      |    44694    58  | 0.13
      |    46776    59  | 0.13
      |    48961    60  | 0.13
      |    51258    61  | 0.13
      |    53677    62  | 0.12
      |    56230    63  | 0.12
      |    58932    64  | 0.12
      |    61799    65  | 0.12
      |    64851    66  | 0.11
      |    68113    67  | 0.11
      |    71617    68  | 0.11
      |    75401    69  | 0.10
      |    79517    70  | 0.10
      |    84035    71  | 0.10
      |    89053    72  | 0.10
      |    94717    73  | 0.09

This table was computed with the following Perl program:
RFCに載っているものにちょっとだけ変更を加えた．
てかRFCに載ってるやつ，printfのところのダブルクォート足りてないような・・・？
あと，\nで改行しておいた．
log83000とか，log38ってどこから出てきたんだ．
あと1.2乗と12.8かけてるところも．

********************************************************************************

#!/usr/bin/perl

$top = 100000; #MAX value of cwnd
$num = 38;  #Initial value of cwnd

if ($num == 38) {
  print "     w  a(w)  b(w)\n";
  print "  ----  ----  ----\n";
  print "    38     1  0.50\n";
  $oldb = 0.50;
  $olda = 1;
}

while ($num < $top) {
  $bw = (0.1 -0.5)*(log($num)-log(38))/(log(83000)-log(38))+0.5;
  $aw = ($num**2*2.0*$bw) / ((2.0-$bw)*$num**1.2*12.8);
  if ($aw > $olda + 1) {
     printf "%6d %5d  %3.2f0\n", $num, $aw, $bw;
     $olda = $aw;
  }
  $num ++;
}

********************************************************************************

参考文献
http://tiki.is.os-omicron.org/tiki.cgi?c=v&p=AIMD
http://icfamon.dl.ac.uk/papers/DataTAG-WP2/reports/task1/20021001-Yee.pdf
http://www.ietf.org/rfc/rfc3649.txt