[ns] Scoreboard and TCP/Sack1 fixes

[Ethan Blanton <eblanton@cs.ohiou.edu>]

Hi,
Attached to this file is a diff containing fixes for the scoreboard and
TCP/Sack1 code.  All validation tests pass excepting tcpVariants.tcl
onedrop_fack and twodrops_fack.  I expect this is because FACK contains a bug 
similar to the SACK bug outlined below, but I do not have time to chase it 
down.

Note that I am aware that my previous patches did *not* validate due to the
below-mentioned TCP/Sack1 bug, and I have fixed this.

These diffs are against ns-2-snapshot-20000707, but these files do not
appear to have changed in some days so it should patch against older
snapshots or even releases, as well.

Outline of changes:

An entry was created in the scoreboard for every packet processed during
loss recovery (and subsequently deleted) regardless of whether it contained
SACK information or not; while not precisely incorrect behavior, this makes
algorithms that depend on knowing the actual state of SACK information in
the scoreboard difficult to implement.  This entry creation has been removed
by checking tcph->sa_length() before creating an entry.

The scoreboard did not properly advance the left edge of the SACK window
*unless* the processed packet contained a SACK block - therefore normal
cumulative acks acknowledging data in the SACK blocks were not taking effect
until a SACK block was encountered.  This check now occurs for every
processed packet, whether it contains SACK blocks or not.

TCP/Sack1 sometimes erroneously passed last_ack_ instead of highest_ack_
into scb_.UpdateScoreboard().  Fixed.

Later,
Ethan
diff -ruN ns-2/scoreboard.cc ns-2-orig/scoreboard.cc
--- ns-2/scoreboard.cc	Fri Jul  7 10:45:09 2000
+++ ns-2-orig/scoreboard.cc	Fri Jul  7 14:51:09 2000
@@ -64,7 +64,7 @@
 	int retran_decr = 0;
 
 	//  If there is no scoreboard, create one.
-	if (length_ == 0 && tcph->sa_length()) {
+	if (length_ == 0) {
 		i = last_ack+1;
 		SBNI.seq_no_ = i;
 		SBNI.ack_flag_ = 0;
@@ -78,29 +78,7 @@
 			exit(1);
 		}
 	}	
-	
-	//  Advance the left edge of the block.
-	if (length_ && SBN[first_].seq_no_ <= last_ack) {
-		for (i=SBN[first_].seq_no_; i<=last_ack; i++) {
-			//  Advance the ACK
-			if (SBNI.seq_no_ <= last_ack) {
-				ASSERT(first_ == i%SBSIZE);
-				first_ = (first_+1)%SBSIZE; 
-				length_--;
-				ASSERT1(length_ >= 0);
-				SBNI.ack_flag_ = 1;
-				SBNI.sack_flag_ = 1;
-				if (SBNI.retran_) {
-					SBNI.retran_ = 0;
-					SBNI.snd_nxt_ = 0;
-					retran_decr++;
-				}
-				if (length_==0) 
-					break;
-			}
-		}
-	}
-	
+
 	for (sack_index=0; sack_index < tcph->sa_length(); sack_index++) {
 		sack_left = tcph->sa_left(sack_index);
 		sack_right = tcph->sa_right(sack_index);
@@ -118,6 +96,28 @@
 				if (length_ >= SBSIZE) {
 					printf ("Error, scoreboard too large (increase SBSIZE for more space)\n");
 					exit(1);
+				}
+			}
+		}
+
+		//  Advance the left edge of the block.
+		if (SBN[first_].seq_no_ <= last_ack) {
+			for (i=SBN[(first_)%SBSIZE].seq_no_; i<=last_ack; i++) {
+				//  Advance the ACK
+				if (SBNI.seq_no_ <= last_ack) {
+					ASSERT(first_ == i%SBSIZE);
+					first_ = (first_+1)%SBSIZE; 
+					length_--;
+					ASSERT1(length_ >= 0);
+					SBNI.ack_flag_ = 1;
+					SBNI.sack_flag_ = 1;
+					if (SBNI.retran_) {
+						SBNI.retran_ = 0;
+						SBNI.snd_nxt_ = 0;
+						retran_decr++;
+					}
+					if (length_==0) 
+					  break;
 				}
 			}
 		}
diff -ruN ns-2/tcp-sack1.cc ns-2-orig/tcp-sack1.cc
--- ns-2/tcp-sack1.cc	Fri Jul  7 10:39:01 2000
+++ ns-2-orig/tcp-sack1.cc	Fri Jul  7 14:50:59 2000
@@ -119,7 +119,7 @@
 					tcph->seqno(), last_ack_);
 				abort();
 			}
-			scb_.UpdateScoreBoard (highest_ack_, tcph);
+			scb_.UpdateScoreBoard (last_ack_, tcph);
 			/*
 		 	 * Check for a duplicate ACK
 			 */
@@ -168,7 +168,7 @@
 			newtimer(pkt);
 		} else if (timeout_ == FALSE) {
 			/* got another dup ack */
-			scb_.UpdateScoreBoard (highest_ack_, tcph);
+			scb_.UpdateScoreBoard (last_ack_, tcph);
 			if (dupacks_ > 0)
 				dupacks_++;
 		}