00001 /* -*- Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */ 00002 /* 00003 * Copyright (c) @ Regents of the University of California. 00004 * All rights reserved. 00005 * 00006 * Redistribution and use in source and binary forms, with or without 00007 * modification, are permitted provided that the following conditions 00008 * are met: 00009 * 1. Redistributions of source code must retain the above copyright 00010 * notice, this list of conditions and the following disclaimer. 00011 * 2. Redistributions in binary form must reproduce the above copyright 00012 * notice, this list of conditions and the following disclaimer in the 00013 * documentation and/or other materials provided with the distribution. 00014 * 3. All advertising materials mentioning features or use of this software 00015 * must display the following acknowledgement: 00016 * This product includes software developed by the MASH Research 00017 * Group at the University of California Berkeley. 00018 * 4. Neither the name of the University nor of the Research Group may be 00019 * used to endorse or promote products derived from this software without 00020 * specific prior written permission. 00021 * 00022 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 00023 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 00024 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 00025 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 00026 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 00027 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 00028 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 00029 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 00030 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 00031 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 00032 * SUCH DAMAGE. 00033 * 00034 */ 00035 00036 /* 00037 * TCP-Linux module for NS2 00038 * 00039 * May 2006 00040 * 00041 * Author: Xiaoliang (David) Wei (DavidWei@acm.org) 00042 * 00043 * NetLab, the California Institute of Technology 00044 * http://netlab.caltech.edu 00045 * 00046 * Module: scoreboard1.h 00047 * This is the header file for Scoreboard1 in TCP-Linux. 00048 * We define the states of a packet in here (SKB_FLAG_*). 00049 * 00050 */ 00051 00052 #ifndef ns_scoreboard1_h 00053 #define ns_scoreboard1_h 00054 00055 // Definition of the scoreboard class: 00056 #include "tcp.h" 00057 00058 #define SKB_FLAG_INFLIGHT 0 /* in flight, new packets */ 00059 #define SKB_FLAG_SACKED 1 /* Acked by SACK block */ 00060 #define SKB_FLAG_LOST 2 /* lost by FACK signal */ 00061 #define SKB_FLAG_RETRANSMITTED 4 /* in flight, but is retransmitted packets */ 00062 00063 class ScoreBoardNode1 { 00064 public: 00065 ScoreBoardNode1(int start, int end, char flag): 00066 flag_(flag), 00067 seq_(start), 00068 nxt_(end), 00069 next_in_queue_(NULL) 00070 {} 00071 inline char GetFlag() { return flag_; } 00072 00073 inline int GetStart() { return seq_; } 00074 inline int GetEnd() { return (flag_==SKB_FLAG_RETRANSMITTED)?seq_:nxt_; } 00075 inline int GetLength() {return (flag_==SKB_FLAG_RETRANSMITTED)?1:(nxt_+1-seq_); } 00076 inline int GetRtx() { return retran_;} 00077 inline int GetSndNxt() { return nxt_; } 00078 inline void SetFlag(char flag) { if (flag_==SKB_FLAG_RETRANSMITTED) nxt_=seq_; flag_ = flag;} 00079 inline void SetBegin(int seq) { seq_=seq; } 00080 inline void Append(ScoreBoardNode1* next) {next_in_queue_ = next;} 00081 inline bool Inside(int seq) { return (flag_==SKB_FLAG_RETRANSMITTED)?(seq==seq_):((seq>=seq_) && (seq<=nxt_)); } 00082 // inline int Compare(int seq) { if (flag_==SKB_FLAG_RETRANSMITTED) return (seq-seq_); else if (seq<seq_) return -1; else if (seq>nxt_) return 1; else return 0;} 00083 inline int ShouldClean(int ackseq) 00084 // return: 0: this block should not be touched; -1: the whole block should be deleted; 00085 // >0: the first # of packets should be deleted 00086 { 00087 if (ackseq<seq_) 00088 return 0; 00089 else if ((flag_==SKB_FLAG_RETRANSMITTED)||(ackseq>=nxt_)) return -1; 00090 else return ackseq+1-seq_; 00091 } 00092 00093 inline ScoreBoardNode1* GetNext() { return next_in_queue_; } 00094 00095 inline bool Mergable() { return ((next_in_queue_) && (next_in_queue_->flag_!=SKB_FLAG_RETRANSMITTED) && (next_in_queue_->flag_ == flag_)); } 00096 //to check if the next packet can be merged to this packet 00097 00098 void Merge() 00099 { 00100 //merge with the next packet: WARNING: call this function ONLY WHEN you check the validity by Mergable. 00101 ScoreBoardNode1* next = next_in_queue_; 00102 nxt_ = next->nxt_; 00103 next_in_queue_ = next->next_in_queue_; 00104 delete next; 00105 } 00106 00107 00108 inline bool Splittable(int seq) { return (flag_!=SKB_FLAG_RETRANSMITTED) && (seq>seq_) && (seq<=nxt_);} 00109 //to check if a node can be split from seq. 00110 00111 ScoreBoardNode1* Split(int seq) 00112 { 00113 // split the current node by the seq; the new node starts is [seq, end of the block]; return the new node 00114 // WARNING: Make sure it is Splittable before this functionis called. 00115 ScoreBoardNode1* next = new ScoreBoardNode1(seq, nxt_, flag_); 00116 next->next_in_queue_ = next_in_queue_; 00117 next_in_queue_ = next; 00118 nxt_ = seq-1; 00119 return next; 00120 } 00121 00122 void MarkRetran(int snd_nxt, int retrans_id) 00123 // Mark the first packet of this block as a retransmission packet 00124 // WARNING: Make sure it is a lost block before calling this function 00125 { 00126 if (nxt_ > seq_ ) Split(seq_+1); 00127 flag_ = SKB_FLAG_RETRANSMITTED; 00128 nxt_ = snd_nxt; 00129 retran_ = retrans_id; 00130 } 00131 00132 private: 00133 char flag_; 00134 int seq_; /* Packet number */ 00135 int nxt_; 00136 /* This member has two different meanings: 00137 1. If the flag_ is not SKB_FLAG_RETRANSMITTED, this means the right edge (included) of the block: [seq_, nxt_] 00138 2. If the flag_ is SKB_FLAG_RETRANSMITTED, this means the snd_nxt_ at the time of retransmission (retransmitted packet is one packet per node) 00139 */ 00140 int retran_; /* Packet retransmitted or not. If retran_ == 0: not retransmitted, if retran_>0, it's the rtx_id_ when it is retransmitted. */ 00141 /* the combination of (retran_, snd_nxt_) can detect the loss of retransmitted packet in an accurate way */ 00142 // double when; //We don't have head timeout yet 00143 ScoreBoardNode1* next_in_queue_; 00144 }; 00145 00146 00147 class ScoreBoard1 { 00148 public: 00149 ScoreBoard1(): head_(NULL), last_rtx_seq_(-1) {ClearScoreBoard();} 00150 virtual ~ScoreBoard1(){ClearScoreBoard ();} 00151 virtual int IsEmpty () {return (head_ == NULL);} 00152 virtual void ClearScoreBoard (); 00153 virtual int GetNextRetran (); 00154 virtual void Dump(); 00155 // virtual void MarkRetran (int retran_seqno); 00156 virtual void MarkRetran (int retran_seqno, int snd_nxt); 00157 virtual int UpdateScoreBoard (int last_ack_, hdr_tcp*, int dupack_threshold=3); 00158 virtual void MarkLoss(int snd_una, int snd_nxt); 00159 //the return value: flags 00160 inline int FackOut() { return fack_out_; } 00161 inline int SackOut() { return sack_out_; } 00162 inline int packets_in_flight(int snd_una, int snd_nxt){return snd_nxt - snd_una - fack_out_ - sack_out_;} 00163 inline int fack() {return fack_;} 00164 // inline bool sure_timestamp(int seq) { return seq>last_rtx_seq_;} 00165 void test(); 00166 00167 protected: 00168 bool CleanRtxQueue(int last_ack, unsigned char* flag); 00169 00170 ScoreBoardNode1* head_; 00171 ScoreBoardNode1* nxt_to_retrx_; 00172 //the next packet to be retransmitted. if nxt_to_retrx_==NULL: no packet can be retransmitted. 00173 00174 00175 int acked_rtx_id_, rtx_id_; //the current id of retransmitted packet 00176 int fack_; // the furthest sacked seq# 00177 int fack_out_; //# of packets that are in the scoreboard, which are deemed to be lost 00178 int sack_out_; //# of packets that are in the scoreboard, which are sacked. 00179 int last_rtx_seq_; // the seqno that we cleaned scoreboard last time. 00180 00181 }; 00182 00183 #endif