[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[BUG] tcp-full.cc: ReassemblyQueue is broken
Hi,
After running some simple simulations using the FullTCP agent in
NS 2.b4 (simple dumbbell topology, 10Mb/s link, 20ms delay, RED
node at the link ingress), I ended up with a highly suspicious
trace file entry for one of the flows -- namely, the ACK number
appears to go _backwards_ (trace snippet at end).
The transmitter appears to perceives these ACKs as out-of-order
ACKs and discards them. Since it thus continues introducing new
data to the network rather than retransmitting the missing
segment, the receiver never ACKs the new data, so the transmitter
eventually starts hitting RTO and backing off (the simulation
lasted for 210s).
After some examination of tcp-full.{cc,h} in both 2.1b4 and
2.1b6, I believe the cause to be the ReassemblyQueue class, which
appears quite broken; if anyone has a better explanation of why
the ACK number went backwards, I'd be delighted to hear it.
Firstly, in
int ReassemblyQueue::add(int start, int end, int tiflags),
which adds a received packet to the ReassemblyQueue, storing the
packet chain as a doubly-linked list, the list insertion code is
incorrect in the case that the item is inserted into the middle
of the list (code at end).
Secondly,
int ReassemblyQueue::gensack(int *sacks, int maxsblock)
which I understand should calculate the contiguous blocks of data
on the ReassemblyQueue, and then the most recent N (maxsblocks)
and place them into "sacks" so that they can be SACKed, in fact
miscalculates the time for a contiguous block, and then (usually)
returns the first N contiguous blocks (which would presumably be
the _least_ recent N blocks). Again, code is appended to this
email.
Thirdly, and this is perhaps more of a query than a bug, I note
that the array to which "int* sacks" always points is declared in
tcp.h as
#define NSA 3
int sack_area_[NSA+1][2]; /* sack blocks: start, end of block */
but max_sack_blocks_ which is passed as maxsblocks in the call to
gensack() above is available through the OTcl interpreter, and
can presumably be changed (although it _is_ initialised to 3).
This doesn't strike me as a very good idea...
Finally, is there any way to request that NS dumps to a
trace-file all the seeds used for any random number streams?
Being unable to repeat the experiment that led to these results
is very annoying.
I have placed my patched version of tcp-full.cc (from NS 2.1b6)
at http://www.cl.cam.ac.uk/~rmm1002/code/tcp-full.cc for anyone
who is interested.
--
Richard Mortier --------------------
----------------- ------ Computer Laboratory,
[email protected] ----- University of Cambridge, UK
[email protected] ---- http://www.cl.cam.ac.uk/~rmm1002/
[ trace snippet -- lines marked with *** are where the ACK jumps
back ]
+ 12.0977 1 0 ack 40 ------- 8 1.7 0.7 1 22310 103449 0x18 40 0
- 12.0977 1 0 ack 40 ------- 8 1.7 0.7 1 22310 103449 0x18 40 0
r 12.1173 1 0 ack 40 ------- 8 1.7 0.7 1 22309 102913 0x18 40 0
+ 12.1173 0 1 tcp 576 ------- 8 0.7 1.7 103449 22372 1 0x10 40 0
r 12.1177 1 0 ack 40 ------- 8 1.7 0.7 1 22310 103449 0x18 40 0
+ 12.1177 0 1 tcp 576 ------- 8 0.7 1.7 103985 22373 1 0x10 40 0
- 12.1182 0 1 tcp 576 ------- 8 0.7 1.7 103449 22372 1 0x10 40 0
- 12.1187 0 1 tcp 576 ------- 8 0.7 1.7 103985 22373 1 0x10 40 0
r 12.1387 0 1 tcp 576 ------- 8 0.7 1.7 103449 22372 1 0x10 40 0
+ 12.1387 1 0 ack 40 ------- 8 1.7 0.7 1 22436 103985 0x18 40 0 ***
- 12.1387 1 0 ack 40 ------- 8 1.7 0.7 1 22436 103985 0x18 40 0 ***
r 12.1391 0 1 tcp 576 ------- 8 0.7 1.7 103985 22373 1 0x10 40 0
+ 12.1391 1 0 ack 40 ------- 8 1.7 0.7 1 22439 101841 0x18 40 0 ***
- 12.1391 1 0 ack 40 ------- 8 1.7 0.7 1 22439 101841 0x18 40 0 ***
r 12.1587 1 0 ack 40 ------- 8 1.7 0.7 1 22436 103985 0x18 40 0 ***
+ 12.1587 0 1 tcp 576 ------- 8 0.7 1.7 104521 22497 1 0x10 40 0
+ 12.1587 0 1 tcp 576 ------- 8 0.7 1.7 105057 22498 1 0x10 40 0
r 12.1592 1 0 ack 40 ------- 8 1.7 0.7 1 22439 101841 0x18 40 0 ***
- 12.1592 0 1 tcp 576 ------- 8 0.7 1.7 104521 22497 1 0x10 40 0
- 12.1596 0 1 tcp 576 ------- 8 0.7 1.7 105057 22498 1 0x10 40 0
r 12.1796 0 1 tcp 576 ------- 8 0.7 1.7 104521 22497 1 0x10 40 0
+ 12.1796 1 0 ack 40 ------- 8 1.7 0.7 1 22562 101841 0x18 40 0
- 12.1796 1 0 ack 40 ------- 8 1.7 0.7 1 22562 101841 0x18 40 0
r 12.1801 0 1 tcp 576 ------- 8 0.7 1.7 105057 22498 1 0x10 40 0
+ 12.1801 1 0 ack 40 ------- 8 1.7 0.7 1 22565 101841 0x18 40 0
- 12.1801 1 0 ack 40 ------- 8 1.7 0.7 1 22565 101841 0x18 40 0
r 12.1997 1 0 ack 40 ------- 8 1.7 0.7 1 22562 101841 0x18 40 0
r 12.2001 1 0 ack 40 ------- 8 1.7 0.7 1 22565 101841 0x18 40 0
+ 18.1587 0 1 tcp 576 ---A--- 8 0.7 1.7 103985 41826 1 0x10 40 0
- 18.1592 0 1 tcp 576 ---A--- 8 0.7 1.7 103985 41826 1 0x10 40 0
r 18.1797 0 1 tcp 576 ---A--- 8 0.7 1.7 103985 41826 1 0x10 40 0
+ 18.1797 1 0 ack 40 ------- 8 1.7 0.7 1 41888 101841 0x18 40 0
- 18.1797 1 0 ack 40 ------- 8 1.7 0.7 1 41888 101841 0x18 40 0
r 18.1997 1 0 ack 40 ------- 8 1.7 0.7 1 41888 101841 0x18 40 0
+ 30.1587 0 1 tcp 576 ---A--- 8 0.7 1.7 103985 79828 1 0x10 40 0
- 30.165 0 1 tcp 576 ---A--- 8 0.7 1.7 103985 79828 1 0x10 40 0
r 30.1855 0 1 tcp 576 ---A--- 8 0.7 1.7 103985 79828 1 0x10 40 0
+ 30.1855 1 0 ack 40 ------- 8 1.7 0.7 1 79923 101841 0x18 40 0
- 30.1855 1 0 ack 40 ------- 8 1.7 0.7 1 79923 101841 0x18 40 0
r 30.2055 1 0 ack 40 ------- 8 1.7 0.7 1 79923 101841 0x18 40 0
+ 54.1587 0 1 tcp 576 ---A--- 8 0.7 1.7 103985 156545 1 0x10 40 0
- 54.1645 0 1 tcp 576 ---A--- 8 0.7 1.7 103985 156545 1 0x10 40 0
r 54.185 0 1 tcp 576 ---A--- 8 0.7 1.7 103985 156545 1 0x10 40 0
+ 54.185 1 0 ack 40 ------- 8 1.7 0.7 1 156635 101841 0x18 40 0
- 54.185 1 0 ack 40 ------- 8 1.7 0.7 1 156635 101841 0x18 40 0
r 54.205 1 0 ack 40 ------- 8 1.7 0.7 1 156635 101841 0x18 40 0
+ 102.159 0 1 tcp 576 ---A--- 8 0.7 1.7 103985 308839 1 0x10 40 0
- 102.159 0 1 tcp 576 ---A--- 8 0.7 1.7 103985 308839 1 0x10 40 0
r 102.18 0 1 tcp 576 ---A--- 8 0.7 1.7 103985 308839 1 0x10 40 0
+ 102.18 1 0 ack 40 ------- 8 1.7 0.7 1 308905 101841 0x18 40 0
- 102.18 1 0 ack 40 ------- 8 1.7 0.7 1 308905 101841 0x18 40 0
r 102.2 1 0 ack 40 ------- 8 1.7 0.7 1 308905 101841 0x18 40 0
+ 198.159 0 1 tcp 576 ---A--- 8 0.7 1.7 103985 614821 1 0x10 40 0
- 198.159 0 1 tcp 576 ---A--- 8 0.7 1.7 103985 614821 1 0x10 40 0
r 198.179 0 1 tcp 576 ---A--- 8 0.7 1.7 103985 614821 1 0x10 40 0
+ 198.179 1 0 ack 40 ------- 8 1.7 0.7 1 614891 101841 0x18 40 0
- 198.179 1 0 ack 40 ------- 8 1.7 0.7 1 614891 101841 0x18 40 0
r 198.199 1 0 ack 40 ------- 8 1.7 0.7 1 614891 101841 0x18 40 0
[ end trace snippet ]
[ list insertion code ]
if (p == NULL) {
// insert at head
n->next_ = head_;
n->prev_ = NULL;
head_->prev_ = n;
head_ = n;
} else {
// insert in the middle or end
n->next_ = p->next_;
p->next_ = n;
n->prev_ = p;
// XXX RMM if (p == tail_)
// XXX RMM tail_ = n;
if (p == tail_)
{
tail_ = n;
}
else
{
n->next_->prev_ = n;
}
}
[ end list insertion code ]
[ gensack() code ]
int
ReassemblyQueue::gensack(int *sacks, int maxsblock)
{
seginfo *p, *q;
if (head_ == NULL)
return (0); // nothing there
//
// look for the SACK block containing the
// most recently received segment. Update the timestamps
// to match the most recent of the contig block
//
// XXX RMM Previously this shuffled maxima of adjacent times down one,
// and then set final time to max(first, second, final) time... Now
// leaves max. time in final segment.
p = head_;
while (p != NULL) {
q = p;
while (p->next_ &&
(p->next_->startseq_ == p->endseq_)) {
// XXX RMM p->time_ = MAX(p->time_, p->next_->time_);
p->next_->time_ = MAX(p->time_, p->next_->time_);
p = p->next_;
}
p->time_ = MAX(q->time_, p->time_);
p = p->next_;
}
//
// look for maxsblock most recent blocks
//
// XXX RMM Previously this returned the first n blocks in list (which
// are probably the n _least_ recent blocks). Now returns n most recent.
// RMM start
// Start at tail & work back; common case: most recent n are
// at end of list... Put first n (counting from tail_) on
// return list,
int *sacks_base_p = sacks;
register int i;
double sacks_times[maxsblock];
p = q = tail_;
for(i=0; i<maxsblock; i++)
{
while(p->prev_ &&
(p->prev_->endseq_ == p->startseq_))
{
p = p->prev_;
}
*sacks++ = p->startseq_;
*sacks++ = q->endseq_;
// stash the time corresp. to the SACK block entered
// in list
sacks_times[i] = q->time_;
if(p->prev_)
{
q = p = p->prev_;
}
else
{
break;
}
}
// if we have more blocks to consider, then p->prev_ exists;
// one should really be storing sacks[] in time order, so as
// to make replacing least recent with more recent easy, but I
// will cop out for now, and simply examine the entire list
// for each element remaining -- maxsblocks defaults to 3 (and
// had better not be bigger than 4 from its declaration -- NSA
// == 3) so this isn't too great a penalty... (he hopes)
// replacement policy is: go through sacks[] and replace
// 2-tuple with values from current list element (enumerated
// only once) iff (last PDU) time for SACK block corresp. to
// 2-tuple is >= (more recent than) time for block in list...
while(p->prev_)
{
// set up prev. SACK block for consideration...
p = q = p->prev_;
while(p->prev_ &&
p->prev_->endseq_ == p->startseq_)
{
p = p->prev_;
}
// now have previous SACK block in [p, q]...
int *ip, *tip=NULL;
double *dp, *tdp=NULL;
for(ip=sacks_base_p, dp=sacks_times;
ip<sacks;
ip+=2, dp++)
{
if(q->time_ >= *dp)
{
if(!tip && !tdp)
{
// first candidate => accept
tip = ip;
tdp = dp;
}
else
{
// not first candidate => must
// be older than prior candidate
if(*dp < *tdp)
{
tip = ip;
tdp = dp;
}
}
}
}
if(tdp && tip)
{
*tdp = q->time_;
tip[0] = p->startseq_;
tip[1] = q->endseq_;
}
}
// RMM end
#if 0
// double max;
// register int i;
// seginfo *maxp, *maxq;
//
// for (i = 0; i < maxsblock; ++i) {
// p = head_;
// max = 0.0;
// maxp = maxq = NULL;
//
// // find the max, q->ptr to left of max, p->ptr to right
// while (p != NULL) {
// q = p;
// while (p->next_ &&
// (p->next_->startseq_ == p->endseq_)) {
// p = p->next_;
// }
// if ((p->time_ > 0.0) && p->time_ > max) {
// maxp = p;
// maxq = q;
// }
// p = p->next_;
// }
//
// // if we found a max, scrawl it away
// if (maxp != NULL) {
// *sacks++ = maxq->startseq_;
// *sacks++ = maxp->endseq_;
// // invert timestamp on max's
// while (maxq != maxp) {
// maxq->time_ = -maxq->time_;
// maxq = maxq->next_;
// }
// maxp->time_ = -maxp->time_;
// } else
// break;
// }
//
// // now clean up all negatives
// p = head_;
// while (p != NULL) {
// if (p->time_ < 0.0)
// p->time_ = -p->time_;
// p = p->next_;
// }
#endif
return (i);
}
[ end gensack() code ]