Subject: BSD 4.4 TCP header prediction code error - Secondary Effect

From: Ali Irfan-FIA225 <[email-masked]>
Date: Tue, 18 Jan 2000 14:33:07 -0600

In [Brakmo95], the authors identified the error in the Header Prediction
Code due to which TCP fails to deflate the window after fast recovery
causing an inappropriate amount of data to be sent into the network after
recovery. This error has also been noted in [TCPImplErr] section 2.8,
"Failure of window deflation after loss recovery".  There is a secondary
effect of the error in the header prediction code leading to inconsistent
fast-retransmit behavior, which is outlined here.

In BSD4.4 TCP, during fast-recovery/fast-retransmit behavior, if cwnd
exceeds ssthresh and a new ack arrives, the header-prediction part of the
code gets exercised. This leads to failure to "deflate" the window causing
large amount of data to be sent, as documented previously. Another
consequence is that the dupack count (t_dupacks) does not get reset. The
dupack count is above re-transmission threshold (usually 3). Subsequently,
the code does not go into fast recovery/fast retransmit when three dupacks
arrive. The dupack count gets reset after the arrival of a new ack following
a timeout retransmission.

A snippet of a trace from a simulation showing this behavior is included.
The simulation is for bulk transfer. Source always sends 512 byte segments
and the advertised window is for 8 (4096 bytes).  The configuration for the
forward path is Src(B) ->10 ms latency -> router (6 buffers) -> 8 kbps link
-> dest(A). Return path for acks: Dest(A) -> 10 ms latency -> Src(B). The
configuration is for low speed wireless/cellular links. 

(cwnd and ssthresh are expressed in #segments)

No. Time(s)   Src Dest  Seq No. Ack No. cwnd  ssthresh Comments
1    21.399    A  B       .     18433   6.879     4
2    21.399    B  A     20993     .       .       .
3    21.911    A  B       .     18945   7.025     4
4    21.911    B  A     21505     .       .       .
5    21.911    B  A     22017     .       .       .    pkt dropped
6    22.423    A  B       .     19457   7.167     4
7    22.423    B  A     22529     .       .       .
8    22.935    A  B       .     19969   7.306     4
9    22.935    B  A     23041     .       .       .
10   23.447    A  B       .     20481   7.443     4
11   23.447    B  A     23553     .       .       .
12   23.959    A  B       .     20993   7.578     4
13   23.959    B  A     24065     .       .       .
14   24.471    A  B       .     21505   7.710     4
15   24.471    B  A     24577     .       .       .
16   24.983    A  B       .     22017   7.839     4
17   24.983    B  A     25089     .       .       .
18   25.495    A  B       .     22017   7.839     4
19   26.007    A  B       .     22017   7.839     4
20   26.519    A  B       .     22017     6       3
21   26.519    B  A     22017     .       .       .
22   27.031    A  B       .     22017     7       3
23   27.543    A  B       .     22017     8       3
24   27.543    B  A     25601     .       .       .
25   28.055    A  B       .     22017     9       3
26   28.567    A  B       .     25601     9       3
27   28.567    B  A     26113     .       .       .
28   28.567    B  A     26625     .       .       .
29   28.567    B  A     27137     .       .       .    primary symptom
30   28.567    B  A     27649     .       .       .  (excessive xmission)
31   28.567    B  A     28161     .       .       .
32   28.567    B  A     28673     .       .       .    pkt dropped
33   28.567    B  A     29185     .       .       .    pkt dropped
34   29.079    A  B       .     26113     9       3
35   29.079    B  A     29697     .       .       .
36   29.591    A  B       .     26625     9       3
37   29.591    B  A     30209     .       .       .
38   30.103    A  B       .     27137     9       3
39   30.103    B  A     30721     .       .       .
40   30.615    A  B       .     27649     9       3
41   30.615    B  A     31233     .       .       .
42   31.127    A  B       .     28161     9       3
43   31.127    B  A     31745     .       .       .
44   31.639    A  B       .     28673     9       3
45   31.639    B  A     32257     .       .       .
46   32.151    A  B       .     28673     10      3
47   32.663    A  B       .     28673     11      3
48   33.175    A  B       .     28673     12      3    secondary symptom
49   33.687    A  B       .     28673     13      3  (no fast retransmit)
50   34.199    A  B       .     28673     14      3
51   34.711    A  B       .     28673     15      3
52   36.679    B  A     28673     .       1       4
53   37.211    A  B       .     29185     2       4
54   37.211    B  A     29185     .       .       .
55   37.211    B  A     29697     .       .       .
56   37.743    A  B       .     32769     3       4

References

[Brakmo95] L.S. Brakmo and L.L. Peterson, "Performance Problems in BDS4.4
TCP," Computer Communication Review , Vol 25, No. 5, October 1995, pg.
69-86. http://www.cs.arizona.edu/xkernel/people/brakmo.html
[TCPImplErr] RFC2525, Known TCP Implementation Problems, March 1999.

Irfan Ali
Motorola, Network Solutions Sector
1501 Shure Drive
Arlington Heights, IL 60004
Phone: (847)632-3281
email: [email-masked]

---

From: Luigi Rizzo <[email-masked]>
Date: Wed, 19 Jan 2000 10:10:15 +0100 (CET)

> configuration is for low speed wireless/cellular links. 

can't help noticing one thing, which people do all the times when
modeling slow-speed links.

In your system the packet transmission time is 512/560ms (not sure
if you count headers in your 512 bytes), for a total queueing delay
(one way) of over 3 seconds, so what is the meaning of putting 10ms
latency in the path!

> 1    21.399    A  B       .     18433   6.879     4
...
> 12   23.959    A  B       .     20993   7.578     4

	cheers
	luigi
-----------------------------------+-------------------------------------
  Luigi RIZZO, [email-masked]  . Dip. di Ing. dell'Informazione
  http://www.iet.unipi.it/~luigi/  . Universita` di Pisa
  TEL/FAX: +39-050-568.533/522     . via Diotisalvi 2, 56126 PISA (Italy)
  Mobile   +39-347-0373137
-----------------------------------+-------------------------------------