[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[ns] patch: tcp.cc slow-start bug ?



Hi,

I investigated the slow start if the "normal" tcp (in tcp.cc) a bit.
I have a slow link (16 kbps), max window is 20, and my tcp window size is 200.

I inserted some debug output in send_much(), in the inner loop, the first column is the time, win is the send window size, h ack the highest received ack, t_seqno_ the seqno of the packet which is currently being sent.

1 sendmuch win: 1 h ack: -1 t_seqno_: 0
1.03956 sendmuch win: 2 h ack: 0 t_seqno_: 1
1.03956 sendmuch win: 2 h ack: 0 t_seqno_: 2
1.06956 sendmuch win: 3 h ack: 1 t_seqno_: 3
1.06956 sendmuch win: 3 h ack: 1 t_seqno_: 4
1.07956 sendmuch win: 4 h ack: 2 t_seqno_: 5
1.07956 sendmuch win: 4 h ack: 2 t_seqno_: 6
1.09956 sendmuch win: 5 h ack: 3 t_seqno_: 7
1.09956 sendmuch win: 5 h ack: 3 t_seqno_: 8
1.10956 sendmuch win: 6 h ack: 4 t_seqno_: 9
1.10956 sendmuch win: 6 h ack: 4 t_seqno_: 10
1.12956 sendmuch win: 7 h ack: 5 t_seqno_: 11
1.12956 sendmuch win: 7 h ack: 5 t_seqno_: 12
1.13956 sendmuch win: 8 h ack: 6 t_seqno_: 13
1.13956 sendmuch win: 8 h ack: 6 t_seqno_: 14
1.15956 sendmuch win: 9 h ack: 7 t_seqno_: 15
1.15956 sendmuch win: 9 h ack: 7 t_seqno_: 16
1.16956 sendmuch win: 10 h ack: 8 t_seqno_: 17
1.16956 sendmuch win: 10 h ack: 8 t_seqno_: 18
1.18956 sendmuch win: 11 h ack: 9 t_seqno_: 19
1.18956 sendmuch win: 11 h ack: 9 t_seqno_: 20
1.19956 sendmuch win: 12 h ack: 10 t_seqno_: 21
1.19956 sendmuch win: 12 h ack: 10 t_seqno_: 22
1.21956 sendmuch win: 13 h ack: 11 t_seqno_: 23
1.21956 sendmuch win: 13 h ack: 11 t_seqno_: 24
1.22956 sendmuch win: 14 h ack: 12 t_seqno_: 25
1.22956 sendmuch win: 14 h ack: 12 t_seqno_: 26
1.24956 sendmuch win: 15 h ack: 13 t_seqno_: 27
1.24956 sendmuch win: 15 h ack: 13 t_seqno_: 28
1.25956 sendmuch win: 16 h ack: 14 t_seqno_: 29
1.25956 sendmuch win: 16 h ack: 14 t_seqno_: 30
1.27956 sendmuch win: 17 h ack: 15 t_seqno_: 31
1.27956 sendmuch win: 17 h ack: 15 t_seqno_: 32
1.28956 sendmuch win: 18 h ack: 16 t_seqno_: 33
1.28956 sendmuch win: 18 h ack: 16 t_seqno_: 34
1.30956 sendmuch win: 19 h ack: 17 t_seqno_: 35
1.30956 sendmuch win: 19 h ack: 17 t_seqno_: 36
1.31956 sendmuch win: 20 h ack: 18 t_seqno_: 37
1.31956 sendmuch win: 20 h ack: 18 t_seqno_: 38
1.33956 sendmuch win: 20 h ack: 19 t_seqno_: 39
1.34956 sendmuch win: 20 h ack: 20 t_seqno_: 40
1.36956 sendmuch win: 20 h ack: 21 t_seqno_: 41
1.37956 sendmuch win: 20 h ack: 22 t_seqno_: 42
1.39956 sendmuch win: 20 h ack: 23 t_seqno_: 43
1.40956 sendmuch win: 20 h ack: 24 t_seqno_: 44
1.42956 sendmuch win: 20 h ack: 25 t_seqno_: 45

So, the sender starts with 1 packet, receives the ack, increases cwnd, sends two packets.
Ok.
Now it receives the ack for packet #1. Again it increases cwnd, now 3, and sends 2 packets.
Then it receives ack #2 and increases cwnd to 4, nice :-)
But, it doesn't send 4 packets, it still sends only 2 packets. This is not exactly exponential behaviour ;-)
It sends only (h_ack+win) - t_seqno_ == 2 packets.
So it goes on until it reaches the max window size of 20 packets. Then it gets even worse.
It still sends only the difference of h_ack+win - t_seqno_ (e.g. 20+21-40 == 1) packets.
I interpret this behaviour this way, that this calculation 
(this is the loop which controls the number of packets)
 while (t_seqno_ <= highest_ack_ + win && t_seqno_ < curseq_)

assumes that the difference t_seqno_ - h_ack is the number of packets which have been sent but not yet acked.
And it assumes that these not yet acked packets sit in the receive buffer of the receiver and not in the send queue of the sender.
So if we have reached the max window size, the sender receives single acks.
After every single ack it sends a new packet. This is exactly the silly window syndrom (fast sender, slow receiver).
But we have a super fast receiver !
The receiver does actually nothing with the received packets, so the receive buffer (which in fact doesn't exist) is always empty. So we can always send the full cwnd packets.
As it is now, I never get any congestion, the speed is only triggered by the speed of the incoming acks.

An original qoute from linux kernel 2.4.12:

/* There is something which you must keep in mind when you analyze the
358  * behavior of the tp->ato delayed ack timeout interval.  When a
359  * connection starts up, we want to ack as quickly as possible.  The
360  * problem is that "good" TCP's do slow start at the beginning of data
361  * transmission.  The means that until we send the first few ACK's the
362  * sender will sit on his end and only queue most of his data, because
363  * he can only send snd_cwnd unacked packets at any given time.  For
364  * each ACK we send, he increments snd_cwnd and transmits more of his
365  * queue.  -DaveM
366  */

This says, that if the sender receives an ack, it increases its cwnd (as it is now), and then *sends* cwnd packets.
So here is the patch:

tcp.cc

void TcpAgent::send_much(int force, int reason, int maxburst)
{
   send_idle_helper();
   int win = window();
   int npackets = 0;
   if (!force && delsnd_timer_.status() == TIMER_PENDING)
      return;
   /* Save time when first packet was sent, for newreno  --Allman */
   if (t_seqno_ == 0)
      firstsent_ = Scheduler::instance().clock();
   if (burstsnd_timer_.status() == TIMER_PENDING)
      return;
+   int i=0;
+   while (i< win && t_seqno_ < curseq_)
-   while (t_seqno_ <= highest_ack_ + win && t_seqno_ < curseq_)
   {
+      i++;
      if (overhead_ == 0 || force)

This produces behaviour like linux 2.4.

Bye
Alex


--
Free Dmitry Sklyarov ! 
http://www.freesklyarov.org