Changeset 4753

Timestamp:

03/31/10 20:40:15 (3 years ago)

Author:

soohyunc

Message:

(this commit re-writes the packet re-ordering policy done by Revision 4730)

when packet re-ordering occurred (or ack re-ordering) and it is beyond 3
DUPACKS, then we need to revert to the previous state (reverting to the earlier
average loss interval and re-mark the timestamp).

in short, in Revision 4730, we trigger a packet out when this happens.
with this commit, instead of clocking a packet out, we revert ALI and timestamp
to the previous stage if:

-- this re-ordered seqno is beyond 3 DUPACKS
-- and that seqno actually changed ALI earlier

Location:

vic/branches/cc/cc

Files:

• tfwc_sndr.cpp (modified) (12 diffs)
• tfwc_sndr.h (modified) (10 diffs)

vic/branches/cc/cc/tfwc_sndr.cpp

@@ -64 +64 @@
         rtx_timer_(this),
         aoa_(0),
-        t_now_(0),
-        t_ts_(0),
-        t_ts_echo_(0),
         now_(0),
         so_recv_(0),
@@ -134 +131 @@
         clear_pvec(num_vec_);
         __jacked_ = 0;
+        // previous average loss intervals
+        prev_interval_ = (double *)malloc(sizeof(double) * RSZ);
+        clear_prev_interval(RSZ);
+        new_hist_seqno_ = (u_int16_t *)malloc(sizeof(u_int16_t) * RSZ);
+        clear_new_hist_seqno(RSZ);
+        new_hist_seqno_size_ = 0;
 
         // packet reordering
@@ -187 +190 @@
         bool outofack = false; 
         UNUSED(outofack);
+        // revert to the previous history?
+        bool revert = false;
 
         // get start/end seqno that this XR chunk reports
@@ -234 +239 @@
                   // trigger packets out to keep Jacob's packet conservation rule
                   if(shift >= DUPACKS)
-                  packet_clocking(pb, recv_by_ch);
+                  revert = revert_interval(jacked_);
+                  cwnd_in_packets(revert);
+                  print_cwnd();
                   return;
                 }
@@ -293 +300 @@
                 // triggering only if the disorder is beyond 3 dupack rule,
                 if (shift >= DUPACKS)
-                packet_clocking(pb, recv_by_ch);
+                revert = revert_interval(jacked_);
+                cwnd_in_packets(revert);
+                print_cwnd();
                 reset_var();
                 return;
@@ -301 +310 @@
         if(!is_tfwc_on_) {
                 if(detect_loss())
-                dupack_action(); 
+                dupack_action(first_lost_pkt_); 
                 else
                 cwnd_++; // TCP-like AIMD
@@ -307 +316 @@
         // TFWC is turned on, so compute congestion window
         else {
-                cwnd_in_packets();
+                cwnd_in_packets(revert);
         }
         print_cwnd();
@@ -533 +542 @@
  * (cwnd is in packets)
  */
-void TfwcSndr::cwnd_in_packets() {
+void TfwcSndr::cwnd_in_packets(bool revert) {
+        if(!revert) {
         loss_history();
         avg_loss_interval();
+        }
 
         // loss event rate (p)
@@ -614 +625 @@
  *   o  marking pseudo loss history and loss rate
  */
-void TfwcSndr::dupack_action() {
+void TfwcSndr::dupack_action(int seqno) {
         // this is the very first packet loss
         is_first_loss_seen_ = true;
@@ -636 +647 @@
 
         // finally, record the very first lost packet's timestamp
-        ts_ = tsvec_[first_lost_pkt_%TSZ];
+        ts_ = tsvec_[seqno%TSZ];
         // then, turn on TFWC algo
         is_tfwc_on_ = true;
@@ -699 +710 @@
                         // this is a new loss event!
 
+                        // store previous ALI before changing history
+                        record_history(refvec_[i], avg_interval_, ts_);
+
                         // increase current history size
                         hsz_ = (hsz_ < HSZ) ? ++hsz_ : HSZ;
@@ -757 +771 @@
 
 /*
+ * store loss interval and timestamp
+ */
+void TfwcSndr::record_history(int seqno, double interval, double ts) {
+        // store seqno
+        new_hist_seqno_[new_hist_seqno_size_++] = seqno;
+        // store average loss interval
+        prev_interval_[seqno%RSZ] = interval;
+        // store timestamp
+        prev_ts_ = ts;
+        // copy history
+        for(int i = 0; i < hsz_; i++)
+        prev_history_[i] = history_[i];
+}
+
+/*
+ * revert average loss interval on packet re-ordering
+ */
+bool TfwcSndr::revert_interval(int reseq) {
+        // we didn't see the first lost packet yet.
+        if(!is_first_loss_seen_) {
+                dupack_action(reseq);
+                return (false);
+        }
+
+        // check if this re-ordered seqno actually triggered a new loss event
+        // if yes, revert to the previous state
+        if(find_seqno(new_hist_seqno_, new_hist_seqno_size_, reseq)) {
+                // reverting to the previous ALI
+                avg_interval_ = prev_interval_[reseq%RSZ];
+                // reverting to the previous timestamp
+                ts_ = prev_ts_;
+                // reverting to the previous history
+                for (int i = 0; i < hsz_; i++)
+                history_[i] = prev_history_[i];
+
+                print_ALI();
+
+                // finally, clear up the state variables
+                clear_prev_interval(RSZ);
+                clear_new_hist_seqno(new_hist_seqno_size_);
+                return (true);
+        }
+        return (false);
+}
+
+/*
+ * find seqno in the array
+ */
+bool TfwcSndr::find_seqno (u_int16_t *v, int n, int target) {
+        for (int i = 0; i < n; i++) {
+                if (v[i] == target)
+                return true;
+        }
+        return false;
+}
+
+/*
  * print history item
  */

vic/branches/cc/cc/tfwc_sndr.h

@@ -187 +187 @@
         u_int16_t *pvec_;       // previous (stored) AckVec
         u_int16_t aoa_;         // ack of ack
-        u_int32_t t_now_;       // the time when the data packet sent
-        u_int32_t t_ts_;                // time stamp (u_int32_t type)
-        u_int32_t t_ts_echo_;   // echo time stamp from the receiver
         double ts_;                     // time stamp (double type)
         double ts_echo_;        // time stamp echo (double type)
@@ -195 +192 @@
         double so_recv_;        // SO_TIMESTAMP (XR packet reception)
         double tao_;            // sampled RTT
+        double prev_ts_;
 
 private:
@@ -206 +204 @@
         // TFWC congestion window
         void cwnd_in_bytes();
-        void cwnd_in_packets();
+        void cwnd_in_packets(bool revert);
 
         // calcuate average loss interval
@@ -212 +210 @@
         void print_history_item (int);
         void print_history_item (int, int);
+        bool revert_interval(int reseq);
+        void record_history(int seqno, double interval, double ts);
 
         // calculate loss history
@@ -224 +224 @@
 
         // dupack action
-        void dupack_action();
+        void dupack_action(int seqno);
 
         // new RTO
@@ -283 +283 @@
         }
 
+        // clear seqno that triggered a new loss event
+        inline void clear_prev_interval (int n) {
+                for (int i = 0; i < n; i++)
+                prev_interval_[i] = 0;
+        }
+
+        // clear seqno that triggered a new loss event
+        inline void clear_new_hist_seqno (int n) {
+                for (int i = 0; i < n; i++)
+                new_hist_seqno_[i] = 0;
+                new_hist_seqno_size_ = 0;
+        }
+
         // number of ackvec chunks
         inline int get_numvec(int n) {
@@ -302 +315 @@
                 __jacked_ = highest;
         }
+
+        // find seqno
+        bool find_seqno(u_int16_t *v, int n, int target);
 
         // print cwnd for debugging
@@ -344 +360 @@
 
         double ts_off_;         // timestamp offset for gettimeofday
-        u_int32_t ref_t_time_;  // reference time (uint32 format)
 
         u_int32_t *seqvec_;             // generated seqno vec
@@ -360 +375 @@
         double avg_interval_;   // average loss interval
         int history_[HSZ+1];    // loss interval history
+        int prev_history_[HSZ];// previous loss interval history
         double weight_[HSZ+1];  // weight for calculating avg loss interval
         double I_tot_;          // total sum
@@ -404 +420 @@
         // highest/lowest packet sequence numbers (prev ackvec)
         u_int16_t __jacked_;    // previous highest packet sequence number
+        double *prev_interval_; // previous avgerage intervals
+        u_int16_t *new_hist_seqno_;     // seqno that introduced a new loss event
+        int new_hist_seqno_size_;
 
         // record of packet size in bytes