开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Windows编程 > 通讯编程 > 查看源码
scoreboard1.cc
资源名称：ns-allinone-2.33.tar.gz　[点击查看]
上传用户：rrhhcc
上传日期：2015-12-11
资源大小：54129k
文件大小：15k
源码类别：

通讯编程

开发平台：

Visual C++

scoreboard1.cc：源码内容
  1. /* -*- Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
  2. /*
  3.  * Copyright (c) 1996 The Regents of the University of California.
  4.  * All rights reserved.
  5.  * 
  6.  * Redistribution and use in source and binary forms, with or without
  7.  * modification, are permitted provided that the following conditions
  8.  * are met:
  9.  * 1. Redistributions of source code must retain the above copyright
  10.  *    notice, this list of conditions and the following disclaimer.
  11.  * 2. Redistributions in binary form must reproduce the above copyright
  12.  *    notice, this list of conditions and the following disclaimer in the
  13.  *    documentation and/or other materials provided with the distribution.
  14.  * 3. All advertising materials mentioning features or use of this software
  15.  *    must display the following acknowledgement:
  16.  *  This product includes software developed by the Network Research
  17.  *  Group at Lawrence Berkeley National Laboratory.
  18.  * 4. Neither the name of the University nor of the Laboratory may be used
  19.  *    to endorse or promote products derived from this software without
  20.  *    specific prior written permission.
  21.  * 
  22.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32.  * SUCH DAMAGE.
  33.  */
  35. /* 
  36.  * TCP-Linux module for NS2 
  37.  *
  38.  * May 2006
  39.  *
  40.  * Author: Xiaoliang (David) Wei  (DavidWei@acm.org)
  41.  *
  42.  * NetLab, the California Institute of Technology 
  43.  * http://netlab.caltech.edu
  44.  *
  45.  * Module: scoreboard1.cc
  46.  *      This is the Scoreboard implementation for TCP-Linux in NS-2.
  47.  *      We loosely follow the Linux implementation (clearn_rtx_queue and sacktag_write_queue in tcp_input.c) in Scoreboard Update.
  48.  *
  49.  */
  51. #include <stdlib.h>
  52. #include <stdio.h>
  54. #include "scoreboard1.h"
  55. #include "tcp.h"
  56. #include "linux/ns-linux-util.h"
  58. #define ASSERT(x) if (!(x)) {printf ("Assert SB failedn"); exit(1);}
  59. #define ASSERT1(x) if (!(x)) {printf ("Assert1 SB (length)n"); exit(1);}
  60. #define ASSERT2(x,y...) if (!(x)) {printf(y); exit(1); }
  62. bool ScoreBoard1::CleanRtxQueue(int last_ack, unsigned char* flag) 
  63. {
  64. int cmp;
  65. bool changed_acked_rtx = false;
  66. //clean the acked packets
  67. while ((head_) && ((cmp=head_->ShouldClean(last_ack))!=0)) {
  68. int pkt_num = (cmp<0) ? head_->GetLength(): cmp;
  69. switch (head_->GetFlag()) {
  70. case SKB_FLAG_SACKED: 
  71. sack_out_ -= pkt_num;
  72. ASSERT2((sack_out_>=0), "SACK_OUT %d get negative when advancing edge, last_ack %dn", sack_out_, last_ack);
  73. break;
  74. case SKB_FLAG_LOST:
  75. fack_out_ -= pkt_num;
  76. ASSERT2((fack_out_>=0), "fack_out %d get negative when advancing edge, last_ack %dn", fack_out_, last_ack);
  77. break;
  78. }
  79. //printf("%d: %d %dn", last_ack, cmp, head_->GetFlag());
  81. if (cmp<0) {
  82. ScoreBoardNode1* tmp=head_;
  83. head_=head_->GetNext();
  84. if (tmp->GetFlag()==SKB_FLAG_RETRANSMITTED) {
  85. if (tmp->GetRtx()>acked_rtx_id_) {
  86. changed_acked_rtx = true;
  87. acked_rtx_id_ = tmp->GetRtx();
  88. }
  89. (*flag) |= FLAG_UNSURE_TSTAMP;
  90. }
  91. if (tmp == nxt_to_retrx_) nxt_to_retrx_ = head_;
  92. delete tmp;
  93. } else {
  94. head_->SetBegin(last_ack+1);
  95. break;
  96. }
  97. }
  98. return changed_acked_rtx;
  99. }
  100. // last_ack = TCP last ack
  101. int ScoreBoard1::UpdateScoreBoard (int last_ack, hdr_tcp* tcph, int dupack_threshold)
  102. {
  103. // This one pass process is not completely accurate:
  104. //
  105. // There is some case such that the acked_rtx_id_ is increased in the later part of the process,
  106. // and this change may mark some earlier packet in the queue to be lost 
  107. // One example:
  108. // 1 (retran=1) 2-5 (sacked) 6(retran=5) 
  109. // if this sack block has 6 in its sack, 1 won't be marked lost in the round.
  110. // However, 1 will be marked as lost when the next SACK arrives
  111. //
  112. // Also, if there is some new packet loss happens after the right most seq of this SACK, this
  113. // pass will not find the loss since it stops at the right most seq of this SACK.
  114. // However, the lost packets will be marked when there is new SACK come back. 
  115. //printf("clean rtxn");
  116. unsigned char flag = 0;
  117. bool thorough = CleanRtxQueue(last_ack, &flag);
  119. if (head_==NULL) {
  120. ClearScoreBoard();
  121. thorough=false;
  122. // if there is no outstanding lost packets, we might not need to do the rest
  123. }
  125. if ((!thorough) && (tcph->sa_length()==0)) return (flag);
  127. // SACK pre-processing
  128. // we filter D-SACK and sort the SACKs below
  129. int sa_length = 0;
  130. int left[NSA+1];
  131. int right[NSA+1];
  132. for (int i=0; i < tcph->sa_length(); i++) {
  133. int sack_left = tcph->sa_left(i);
  134. int sack_right = tcph->sa_right(i);
  135. if (sack_left >= last_ack) { //here we filter the D-SACK
  136. int j = sa_length;
  137. sa_length++;
  138. while ((j>0) && (left[j-1] > sack_left)) { 
  139. left[j] = left[j-1]; 
  140. right[j] = right[j-1]; 
  141. j--;
  142. }
  143. //insert to the right place to keep increasing order
  144. left[j] = sack_left;
  145. right[j] = sack_right;
  146. }
  147. }
  148. if ((!thorough)&&(sa_length == 0)) return (flag); //same reason as the first return 0
  150. if ((sa_length > 0) && (fack_ < (right[sa_length-1]-1))) {
  151. // advance fack_. right[sa_length-1]-1 is the right most of all the sacks in the packet. 
  152. fack_ = right[sa_length-1]-1;
  153. thorough = true;
  154. }
  156. //  If there is no scoreboard, create one.
  157. if (head_==NULL) {
  158. head_ = new ScoreBoardNode1(last_ack+1, fack_,0);
  159. //initially, create a block from snd_una to facked, 
  160. //  with flag==0 meaning that packets are in flight
  161. };
  163. // From now, we process the score board
  164. nxt_to_retrx_ = NULL;
  167. // printf("start traversen");
  168. int lost_seq_threshold = fack_ - (dupack_threshold+1);
  169. ScoreBoardNode1* now = head_; // the block we are processing
  170. ScoreBoardNode1* prev = NULL;
  171. int sack_index = 0; //the sack that is currently focused 
  172. while ((now != NULL) && ((sack_index<sa_length)||thorough)) {
  173. if (now->GetFlag()!=SKB_FLAG_SACKED) {
  174. while ((sack_index<sa_length) && (right[sack_index]<=now->GetStart()) )
  175. sack_index++;
  176. //find the sack that match "now"
  177. if (sack_index<sa_length) {
  178. //printf("Sack block: [%d %d], now block: %d[%d %d]n", left[sack_index], right[sack_index], now->GetFlag(), now->GetStart(), now->GetEnd());
  179. if (left[sack_index]<=now->GetEnd()) {
  180. // We share some intersection between this SACK and this "now"
  181. if (left[sack_index]>now->GetStart()) {
  182. //printf("split to make some sackesn");
  183. // the first part of "now" is not SACKED
  184. now->Split(left[sack_index]);
  185. } else {
  186. if (right[sack_index]<=now->GetEnd()) {
  187. //partially sacked
  188. //printf("going to splitn");
  189. now->Split(right[sack_index]);
  190. //printf("done splitn");
  191. };
  192. int pktnum = now->GetLength();
  193. switch (now->GetFlag()) {
  194. case SKB_FLAG_LOST:
  195. fack_out_ -= pktnum;
  196. break;
  197. case SKB_FLAG_RETRANSMITTED:
  198. acked_rtx_id_ = now->GetRtx();
  199. flag |= FLAG_UNSURE_TSTAMP;
  200. thorough = true;
  201. break;
  202. }
  203. sack_out_ += pktnum;
  204. flag |= FLAG_DATA_SACKED;
  205. now->SetFlag(SKB_FLAG_SACKED);
  206. }
  207. };
  208. }
  209. if ((sack_index>=sa_length)|| (left[sack_index]>now->GetEnd())) {
  210. //printf("now block: %d[%d %d]n", now->GetFlag(),now->GetStart(), now->GetEnd());
  212. switch (now->GetFlag()) {
  213. case SKB_FLAG_RETRANSMITTED:
  214. // check if it is lost again
  215. if (((now->GetSndNxt() <= fack_)
  216. ||((now->GetRtx() + dupack_threshold+1) < acked_rtx_id_))) {
  217. now->SetFlag(SKB_FLAG_LOST);
  218. fack_out_++;
  219. flag |= FLAG_DATA_LOST;
  220. if (!nxt_to_retrx_) nxt_to_retrx_ = now;
  221. } 
  222. break;
  223. case SKB_FLAG_INFLIGHT:
  224. //check if it is lost
  225. if (now->GetStart() <= lost_seq_threshold) {
  226. //some packets might be lost
  227. if (lost_seq_threshold<now->GetEnd()) {
  228. //partial loss
  229. now->Split(lost_seq_threshold+1);
  230. }
  231. now->SetFlag(SKB_FLAG_LOST);
  232. fack_out_ += now->GetLength();
  233. flag |= FLAG_DATA_LOST;
  234. if (!nxt_to_retrx_) nxt_to_retrx_ = now;
  235. }
  236. break;
  237. case SKB_FLAG_LOST:
  238. if (!nxt_to_retrx_) nxt_to_retrx_ = now;
  239. break;
  240. }
  241. }
  242. }
  243. //printf("now block: %d[%d %d]n", now->GetFlag(),now->GetStart(), now->GetEnd());
  245. if ((prev) && (prev->Mergable())) {
  246. //Try to merge with previous node
  247. //printf("Merging %d [%d,%d] + %d [%d, %d]n", prev->GetFlag(), prev->GetStart(), prev->GetEnd(), now->GetFlag(), now->GetStart(), now->GetEnd());
  248. prev->Merge();
  249. } else {
  250. prev = now;
  251. }
  253. if ((prev->GetNext()==NULL) && (prev->GetEnd()<fack_)) {
  254. //printf("appending %d %dn",prev->GetEnd()+1, fack_);
  255. prev->Append(new ScoreBoardNode1(prev->GetEnd()+1, fack_,0));
  256. //extend the scoreboard
  257. }
  258. now = prev -> GetNext();
  259. };
  261. return (flag);
  263. }
  265. void ScoreBoard1::MarkLoss(int snd_una, int snd_nxt) {
  266. nxt_to_retrx_ = NULL;
  267. ScoreBoardNode1* now = head_;
  268. ScoreBoardNode1* prev = NULL;
  269. bool last_lost = false;
  270. while (now) {
  271. if (!(now->GetFlag() & (SKB_FLAG_SACKED))) {
  272. if (! (now->GetFlag() & SKB_FLAG_LOST)) 
  273. fack_out_ += now->GetEnd() - now->GetStart() + 1;
  274. now->SetFlag(SKB_FLAG_LOST);
  275. if (last_lost) {
  276. prev->Merge();
  277. now=prev;
  278. } else {
  279. if (nxt_to_retrx_==NULL) nxt_to_retrx_ = now;
  280. }
  281. last_lost = true;
  282. } else {
  283. last_lost = false;
  284. }
  285. prev = now;
  286. now = now->GetNext();
  287. if ((now==NULL) && ((prev->GetEnd()+1) < snd_nxt)) {
  288. //all the packets that we sent have lost
  289. now = new ScoreBoardNode1(prev->GetEnd()+1, snd_nxt-1, SKB_FLAG_INFLIGHT);
  290. prev->Append(now);
  291. }
  292. }
  293. if ((prev==NULL) && (snd_una<snd_nxt)) {
  294. //the score board is empty
  295. head_ = new ScoreBoardNode1(snd_una, snd_nxt-1, SKB_FLAG_LOST);
  296. nxt_to_retrx_ = head_;
  297. fack_out_ += snd_nxt - snd_una;
  298. }
  299. rtx_id_ = 0;
  300. acked_rtx_id_ = -1;
  301. }
  303. void ScoreBoard1::ClearScoreBoard()
  304. {
  305. rtx_id_ = 0;
  306. acked_rtx_id_ = -1;
  307.         fack_out_ = 0;
  308.         sack_out_ = 0;
  309. fack_ = 0;
  310. nxt_to_retrx_ = NULL;
  311. while (head_) {
  312. ScoreBoardNode1* temp = head_;
  313. head_ = head_->GetNext();
  314. delete temp;
  315. }
  316. }
  318. /*
  319.  * GetNextRetran() returns "-1" if there is no packet that is
  320.  *   not acked and not sacked and not retransmitted.
  321.  */
  322. int ScoreBoard1::GetNextRetran()
  323. {
  324. while ((nxt_to_retrx_) && (nxt_to_retrx_->GetFlag() != SKB_FLAG_LOST))
  325. nxt_to_retrx_ = nxt_to_retrx_->GetNext();
  326. if (nxt_to_retrx_) {
  327. return nxt_to_retrx_->GetStart();
  328. } else
  329. return -1;
  330. }
  332. void ScoreBoard1::MarkRetran (int retran_seqno, int snd_nxt)
  333. {
  334. ASSERT2(((nxt_to_retrx_) && (nxt_to_retrx_->Inside(retran_seqno))), "Trying to mark a retransmission outside the recommended one: %p %d, snd_nxt: %dn", nxt_to_retrx_, retran_seqno, snd_nxt);
  335. fack_out_ --;
  336. ASSERT2((fack_out_>=0), "fack_out gets negative in Mark Retran, %d, snd_nxt: %d, rtx_seq:%dn", fack_out_, snd_nxt, retran_seqno);
  337. nxt_to_retrx_->MarkRetran(snd_nxt, rtx_id_);
  338. rtx_id_++;
  339. last_rtx_seq_=retran_seqno;
  340. }
  343. void ScoreBoard1::Dump()
  344. {
  345.        if (head_ == NULL ) { printf("SB: No entryn"); return; };
  347.        printf("SB len:%d fack:%d sack_out:%d fack_out:%d acked_rtx_id:%d next_rtx_id:%dn", 
  348. fack_-head_->GetStart(), 
  349. fack_, 
  350. sack_out_,
  351. fack_out_,
  352. acked_rtx_id_,
  353. rtx_id_
  354. );
  356. ScoreBoardNode1* now=head_;
  357. while (now) {
  358. if (now->GetFlag()==SKB_FLAG_RETRANSMITTED) 
  359. printf("seq:%d (%d snd_nxt:%d rtxid:%d)n", now->GetStart(), now->GetFlag(), now->GetSndNxt(), now->GetRtx());
  360. else
  361. printf("seq:[%d,%d] (%d)n", now->GetStart(), now->GetEnd(), now->GetFlag());
  362. now=now->GetNext();
  363.        }
  364.        printf("n");
  365. }
  367. void ScoreBoard1::test() 
  368. {
  369. ClearScoreBoard();
  370. hdr_tcp test;
  371. test.sa_length_ =  1;
  372. test.sack_area_[0][0]= 4;
  373. test.sack_area_[0][1]= 5;
  375. printf(" 1 x x 4  n");
  376. UpdateScoreBoard(1, &test); Dump();
  377.         test.sack_area_[0][0]= 7;
  378.         test.sack_area_[0][1]= 8;
  380. printf(" 1 x x 4 x x 7 n");
  381. UpdateScoreBoard(1, &test); Dump();
  383. printf(" 1 R x 4 x x 7n");
  384. MarkRetran(GetNextRetran(),8); Dump();
  386. test.sack_area_[0][0]= 9;
  387. test.sack_area_[0][1]= 10;
  388. printf(" 1 x x 4 x x 7 x 9 n");
  389. UpdateScoreBoard(1, &test); Dump();
  391. test.sack_area_[0][0]= 7;
  392.         test.sack_area_[0][1]= 9;
  393.         printf(" 1 x x 4 x x 7 8 9n");
  394.         UpdateScoreBoard(1, &test); Dump();
  396. printf(" 1 R x 4 x x 7 8 9n");
  397.         MarkRetran(GetNextRetran(),60); Dump();
  399. printf(" 1 R R 4 x x 7 8 9n");
  400.         MarkRetran(GetNextRetran(),60); Dump();
  402. test.sack_area_[0][0]= 3;
  403.         test.sack_area_[0][1]= 4;
  404.         printf(" 1 R 3 4 x x 7 8 9n");
  405.         UpdateScoreBoard(1, &test); Dump();
  407. test.sack_area_[0][0]= 15;
  408.         test.sack_area_[0][1]= 19;
  409.         printf(" 1 R 3 4 x x 7 8 9 x x x x x 15 - 19n");
  410.         UpdateScoreBoard(1, &test); Dump();
  412. printf(" 1 R R 4 R x 7 8 9 x x x x x 15 - 19n");
  413.         MarkRetran(GetNextRetran(),60); Dump();
  415. printf(" 1 R 3 4 R R 7 8 9 x x x x x 15 - 19n");
  416.         MarkRetran(GetNextRetran(),60); Dump();
  418. printf(" 1 R R 4 R R 7 8 9 R x x x x 15 - 19n");
  419.         MarkRetran(GetNextRetran(),60); Dump();
  421.         printf(" 1 R 3 4 R R 7 8 9 R R x x x 15 16n");
  422.         MarkRetran(GetNextRetran(),60); Dump();
  424.         printf(" 1 R 3 4 R R 7 8 9 R R R x x 15 16n");
  425.         MarkRetran(GetNextRetran(),60); Dump();
  427.         printf(" 1 R 3 4 R R 7 8 9 R R R R x 15 16n");
  428.         MarkRetran(GetNextRetran(),60); Dump();
  430. printf(" 1 R 3 4 R R 7 8 9 R R R R R 15 16n");
  431.         MarkRetran(GetNextRetran(),60); Dump();
  433.         test.sack_area_[0][0]= 5;
  434.         test.sack_area_[0][1]= 11;
  435.         printf(" 1 R 3 4 5 6 7 8 9 10 R R R R 15 16n");
  436.         UpdateScoreBoard(1, &test); Dump();
  438. test.sack_area_[0][0]= 25;
  439.         test.sack_area_[0][1]= 40;
  440.         printf(" 1 R 3 4 5 6 7 8 9 10 11 12 13 R 15 16 25-40n");
  441.         UpdateScoreBoard(1, &test); Dump();
  443. printf(" 1 R 3 4 5 6 7 8 9 10 11 12 13 R 15 16 Rn");
  444.         MarkRetran(GetNextRetran(),90); Dump();
  445. printf(" 1 R 3 4 5 6 7 8 9 10 11 12 13 R 15 16 R Rn");
  446.         MarkRetran(GetNextRetran(),20); Dump();
  447. printf(" 1 R 3 4 5 6 7 8 9 10 11 12 13 R 15 16 R R Rn");
  448.         MarkRetran(GetNextRetran(),20); Dump();
  449. printf(" 1 R 3 4 5 6 7 8 9 10 11 12 13 R 15 16 R R R Rn");
  450.         MarkRetran(GetNextRetran(),20); Dump();
  451. printf(" 1 R 3 4 5 6 7 8 9 10 11 12 13 R 15 16 R R R R Rn");
  452.         MarkRetran(GetNextRetran(),20); Dump();
  453. printf(" 1 R 3 4 5 6 7 8 9 10 11 12 13 R 15 16 R R R R R Rn");
  454.         MarkRetran(GetNextRetran(),20); Dump();
  456.         test.sack_area_[0][0]= 11;
  457.         test.sack_area_[0][1]= 16;
  458.         printf(" 1 R 3 4 5 6 7 8 9 10 11 12 13 14 15 16 25-40n");
  459.         UpdateScoreBoard(1, &test); Dump();
  461. test.sack_area_[0][0]= 11;
  462.         test.sack_area_[0][1]= 16;
  463.         printf(" 1 x 3 4 5 6 7 8 9 10 11 12 13 14 15 16 25-40n");
  464.         UpdateScoreBoard(1, &test); Dump();
  467. printf(" 1 R 3 4 5 6 7 8 9 10 11 12 13 R 15 16n");
  468. MarkRetran(GetNextRetran(),20); Dump();
  470. UpdateScoreBoard(3, &test); Dump();
  471. }