root/vic/branches/cc/cc/tfwc_sndr.cpp @ 4762

Revision 4762, 21.7 KB (checked in by soohyunc, 4 years ago)

if packet re-ordering occurred before the first packet loss, then we do not have
any history to revert - i.e., we didn't yet go into ALI routines.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Rev URL
Line 
1/*
2 * Copyright (c) 2008-2010 University College London
3 * All rights reserved.
4 *
5 * AUTHOR: Soo-Hyun Choi <s.choi@cs.ucl.ac.uk>
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 *    notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 *    notice, this list of conditions and the following disclaimer in the
14 *    documentation and/or other materials provided with the distribution.
15 * 3. Neither the name of the University nor of the Laboratory may be used
16 *    to endorse or promote products derived from this software without
17 *    specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * SUCH DAMAGE.
30 *
31 * $Id$
32 */
33
34#include "assert.h"
35#include "config.h"
36#include "timer.h"
37#include "math.h"
38#include "rtp.h"
39#include "inet.h"
40#include "pktbuf-rtp.h"
41#include "vic_tcl.h"
42#include "module.h"
43#include "transmitter.h"
44#include "tfwc_sndr.h"
45
46// timestamp skew from Vic to Network Device
47// (approximately 10 usec)
48#define SKEW 0.000010
49
50/*
51 * retransmission timer
52 */
53void TfwcRtxTimer::timeout() {
54        debug_msg("\t*------ TIMEOUT! ------*\n");
55        s_ -> expire(TFWC_TIMER_RTX);
56}
57
58/*
59 * TFWC sender definition
60 */
61TfwcSndr::TfwcSndr() :
62        seqno_(0),
63        cwnd_(1),
64        rtx_timer_(this),
65        aoa_(0),
66        now_(0),
67        so_recv_(0),
68        ndtp_(0),
69        nakp_(0),
70        ntep_(0),
71        nsve_(0),
72        jacked_(0),
73        begins_(0),
74        ends_(0),
75        num_elm_(1),
76        num_vec_(1)
77{
78        // allocate tsvec_ in memory
79        tsvec_ = (double *)malloc(sizeof(double) * TSZ);
80        clear_tsv(TSZ);
81
82        // allocate seqvec in memory
83        seqvec_ = (u_int32_t *)malloc(sizeof(u_int32_t) * SSZ);
84        clear_sqv(SSZ);
85        num_seqvec_ = 0;
86
87        // allocate refvec in memory
88        refvec_ = (u_int32_t *)malloc(sizeof(u_int32_t) * RSZ);
89        clear_refv(RSZ);
90        num_refvec_ = 0;
91
92        // for simulating TCP's 3 dupack rule
93        // (allowing packet re-ordering issue)
94        for (int i = 0; i < DUPACKS; i++)
95                mvec_[i] = 0;
96
97        minrto_ = 0.0;
98        maxrto_ = 100000.0;
99        srtt_ = -1.0;
100        rto_ = 3.0;             // RFC 1122
101        rttvar_ = 0.0;
102        df_ = 0.95;
103        sqrtrtt_ = 1.0;
104        t0_ = 6.0;
105        alpha_ = 0.125;
106        beta_ = 0.25;
107        g_ = 0.01;
108        k_ = 4;
109        ts_ = 0.0;
110        ts_echo_ = 0.0;
111
112        is_tfwc_on_ = false;
113        is_first_loss_seen_ = false;
114        first_lost_pkt_ = -1;
115        num_missing_ = 0;
116
117        avg_interval_ = 0.0;
118        I_tot0_ = 0.0;
119        I_tot1_ = 0.0;
120        tot_weight_ = 0.0;
121
122        to_driven_ = false;
123        tcp_tick_ = 0.01;
124        srtt_init_ = 12;
125        rttvar_exp_ = 2;
126        t_srtt_ = int(srtt_init_/tcp_tick_) << T_SRTT_BITS;
127        t_rttvar_ = int(rttvar_init_/tcp_tick_) << T_RTTVAR_BITS;
128
129        // allocate previously received ackvec in memory
130        pvec_ = (u_int16_t *)malloc(sizeof(u_int16_t) * num_vec_);
131        clear_pvec(num_vec_);
132        __jacked_ = 0;
133        // previous average loss intervals
134        prev_interval_ = (double *)malloc(sizeof(double) * RSZ);
135        clear_prev_interval(RSZ);
136        new_hist_seqno_ = (u_int16_t *)malloc(sizeof(u_int16_t) * RSZ);
137        clear_new_hist_seqno(RSZ);
138        new_hist_seqno_size_ = 0;
139
140        // packet reordering
141        reorder_ = false;
142
143        // record of packet size in bytes
144        record_ = (u_int16_t *)malloc(sizeof(u_int16_t) * RECORD);
145        clear_record(RECORD);
146}
147
148void TfwcSndr::tfwc_sndr_send(pktbuf* pb, double now) {
149        // the very first data packet
150        if(seqno_ == 0)
151        ts_off_ = tx_ts_offset();
152
153        // number of bytes for this packet
154        record_[seqno_%RECORD] = pb->len;
155        // parse seqno and mark timestamp for this data packet
156        rtphdr* rh = (rtphdr *) pb->data;
157        seqno_  = ntohs(rh->rh_seqno);
158        now_    = now;
159
160        // timestamp vector for loss history update
161        tsvec_[seqno_%TSZ] = now_-SKEW;
162        //print_packet_tsvec();
163
164        // sequence number must be greater than zero
165        assert (seqno_ > 0);
166        // number of total data packet sent
167        ndtp_++;
168       
169        // set retransmission timer
170        set_rtx_timer();
171}
172
173/*
174 * main TFWC reception path
175 */
176void TfwcSndr::tfwc_sndr_recv(u_int16_t type, u_int16_t begin, u_int16_t end,
177                u_int16_t *chunk, double so_rtime, bool recv_by_ch, pktbuf* pb)
178{
179  switch (type) {
180  // retrieve ackvec
181  case XR_BT_1:
182  {
183        // number of ack received
184        nakp_++;
185        // so_timestamp (timestamp for packet reception)
186        so_recv_ = so_rtime;
187        // packet reordering?
188        reorder_ = false;
189        // reordered ack delivery?
190        bool outofack = false;
191        UNUSED(outofack);
192        // revert to the previous history?
193        bool revert = false;
194
195        // get start/end seqno that this XR chunk reports
196        begins_ = begin;        // lowest packet seqno
197        ends_ = end;            // highest packet seqno plus one
198
199        // just acked seqno
200        // i.e.,) head seqno(= highest seqno) of this ackvec
201        jacked_ = ends_ - 1;
202
203        //print_xr_info(__FILE__,__LINE__);
204
205        // get the number of AckVec chunks
206        //   use seqno space to work out the num chunks
207        //   (add one to num unless exactly divisible by BITLEN
208        //   - so it is large enough to accomodate all the bits
209        num_elm_ = get_numelm(begins_, jacked_);
210        num_vec_ = get_numvec(num_elm_);
211
212        // declared AckVec
213        ackv_ = (u_int16_t *) malloc (sizeof(u_int16_t) * num_vec_);
214        // clear the existing AckVec
215        clear_ackv(num_vec_);
216        // clone AckVec from Vic
217        clone_ackv(chunk, num_vec_);
218        //print_vec("ackvec", ackv_, num_vec_);
219
220        //---------------------------------------------------------*
221        // detect packet reordering and reordered ack delivery
222        int shift = abs(__jacked_ - jacked_);
223        if (jacked_ < __jacked_) {
224                //
225                // this ack is deprecated message (e.g., too old).
226                //
227                if(jacked_ < aoa_) {
228                  debug_msg("warning: this ack(%d) is older than AoA(%d)!\n", jacked_,aoa_);
229                  // trigger a packet out to keep Jacob's packet conservation rule
230                  //packet_clocking(pb, recv_by_ch);
231                 
232                  // this ack is already too old,
233                  // so revert to the eariler history
234                  revert = revert_interval(jacked_);
235                  // then, update cwnd
236                  cwnd_in_packets(revert);
237                  print_cwnd();
238                  // finally, reset variables
239                  reset_var(revert);
240                  return;
241                }
242                //
243                // this ack is delivered out-of-order
244                //
245                else if(out_of_ack(jacked_, seqvec_, num_seqvec_)) {
246                  debug_msg("warning: this ack(%d) itself is out-of-order!\n",jacked_);
247                  // if the disorder is beyond 3 dupack rule,
248                  // revert to the earlier history
249                  if(shift >= DUPACKS)
250                  revert = revert_interval(jacked_);
251                  // then, update cwnd
252                  cwnd_in_packets(revert);
253                  print_cwnd();
254                  // finally, reset variables
255                  reset_var(revert);
256                  return;
257                }
258                //
259                // packet is out-of-order, so adjust ackvec re-construction
260                //
261                else {
262                  debug_msg("warning: packet reordering occurred!\n");
263                  // replace just ack'ed seqno
264                  replace(__jacked_);
265                  // re-calculate numelm and numvec
266                  num_elm_ = get_numelm(begins_, jacked_);
267                  num_vec_ = get_numvec(num_elm_);
268                  reorder_ = true;
269                }
270        }
271        else {
272                free(pvec_);
273        }
274        //---------------------------------------------------------*
275
276        // if packet reordering occurred, insert re-ordered seqno
277        // into the received ackvec using previously received ackvec
278        if(reorder_) {
279                for (int i = 0; i < num_vec_; i++) {
280                ackv_[i] = (ackv_[i] << shift) | pvec_[i];
281                }
282        }
283        // this will ensure constructing ackv correctly,
284        // when there is packet re-ordering.
285        // (e.g., if packet reordering, then ack will be ordered that way.)
286        else {
287                for (int i = 0; i < num_vec_; i++) {
288                ackv_[i] = (pvec_[i] << shift) | ackv_[i];
289                }
290        }
291
292        // generate seqno vector
293        //print_vec("ackvec", ackv_, num_vec_);
294        gen_seqvec(ackv_, num_vec_);
295
296        // generate margin vector
297        marginvec(jacked_);
298        print_mvec();
299
300        // generate reference vector
301        // (it represents seqvec when there are no losses)
302        //      @begin: aoa_+1 (lowest seqno)
303        //      @end: mvec_[DUPACKS-1] - 1
304        gen_refvec(mvec_[DUPACKS-1]-1, aoa_+1);
305
306        // we have detected packet re-ordering!!!
307        // so, we've updated/corrected received ackvec
308        // by inserting "jacked" to the previous ackvec.
309        // finally, we only need to clock packets out.
310        // (i.e., do NOT update cwnd and RTT)
311        if(reorder_ && is_tfwc_on_) {
312                // revert to the earlier history if the disorder is beyond 3 dupack rule
313                if (shift >= DUPACKS)
314                revert = revert_interval(jacked_);
315                // then, update cwnd
316                cwnd_in_packets(revert);
317                print_cwnd();
318                // finally, reset variables
319                reset_var(revert);
320                return;
321        }
322
323        // TFWC is not turned on (i.e., no packet loss yet)
324        if(!is_tfwc_on_)
325                tcp_like_increase();
326        // TFWC is turned on, so compute congestion window
327        else
328                cwnd_in_packets(revert);
329
330        print_cwnd();
331
332        // set ackofack (real number)
333        aoa_ = ackofack();
334
335        // sampled RTT
336        tao_ = so_recv_ - tsvec_[jacked_%TSZ];
337        // update RTT with the sampled RTT
338        update_rtt(tao_);
339
340        // is TFWC being driven by timeout mechanism?
341        if(to_driven_ && is_tfwc_on_)
342                new_rto(tao_);
343       
344        // reset variables for the next pkt reception
345        reset_var(revert);
346  }
347  break;
348
349  // retrieve ts echo
350  case XR_BT_3:
351  {
352        ntep_++;                // number of ts echo packet received
353        ts_echo_ = chunk[num_vec_ - 1];
354        //fprintf(stderr, "    [%s +%d] ts echo:        %f\n",
355        //      __FILE__,__LINE__, ts_echo_);
356
357        tao_ = now() - ts_echo_;
358  }
359  break;
360
361  default:
362  break;
363  } // end switch (type)
364
365  return;
366}
367
368/*
369 * detect out-of-ordered ack delivery
370 * -- if just ack'ed seqno (jack) is already in sequence vector,
371 *    then, this ack should've been arrived earlier.
372 *    (i.e., this ack is out-of-ordered)
373 */
374bool TfwcSndr::out_of_ack(u_int16_t target, u_int32_t *sqv, int n) {
375        for (int i = 0; i < n; i++) {
376                if (sqv[i] == target)
377                return true;
378        }
379        return false;
380}
381
382void TfwcSndr::reset_var(bool reverted) {
383        // init vars------------*
384        num_missing_ = 0;
385        //----------------------*
386
387        if(!reverted) {
388        // store jack'ed
389        store(jacked_);
390        // declare pvec to store ackv
391        pvec_ = (u_int16_t *)malloc(sizeof(u_int16_t) * num_vec_);
392        clear_pvec(num_vec_);
393        // store ackv
394        copy_ackv(num_vec_);
395        //print_vec("stored ackvec", pvec_, num_vec_);
396        }
397
398        // finally, free ackvec
399        free(ackv_);
400}
401
402/*
403 * generate seqno vector
404 * (interpret the received AckVec to real sequence numbers)
405 * @ackvec: received AckVec
406 */
407void TfwcSndr::gen_seqvec (u_int16_t *v, int n) {
408        // clear seqvec before starts
409        clear_sqv(num_seqvec_);
410
411        int i, j, k = 0;
412        int x = num_elm_%BITLEN;
413
414        // start of seqvec (lowest seqno)
415        int start = begins_;
416
417        for (i = 0; i < n-1; i++) {
418                for (j = BITLEN; j > 0; j--) {
419                        if( CHECK_BIT_AT(v[i], j) )
420                                seqvec_[k++%SSZ] = start;
421                        else num_missing_++;
422                        start++;
423                }
424        }
425
426        int a = (x == 0) ? BITLEN : x;
427        for (i = a; i > 0; i--) {
428                if( CHECK_BIT_AT(v[n-1], i) )
429                        seqvec_[k++%SSZ] = start;
430                else num_missing_++;
431                start++;
432        }
433
434        // therefore, the number of seqvec elements is:
435        num_seqvec_ = num_elm_ - num_missing_;
436        // printing retrieved sequence numbers from received AckVec
437        print_vec("sequence numbers", seqvec_, num_seqvec_);
438}
439
440/*
441 * generate reference vector
442 * (it represents the seqno vector when no losses)
443 * @end:    end seqno   (highest)
444 * @begin:  begin seqno (lowest)
445 */
446void TfwcSndr::gen_refvec(int end, int begin) {
447        // clear previous reference vector
448        clear_refv(num_refvec_);
449        // number of reference element - when no loss
450        num_refvec_ = end - begin + 1;
451
452        // generate refvec elements
453        fprintf(stderr, "\tcomparing numbers: (");
454        for (int i = 0; i < num_refvec_; i++) {
455                refvec_[i] = begin + i;
456                fprintf(stderr, " %d", refvec_[i]);
457        } fprintf(stderr, " )\n");
458}
459
460/*
461 * detect packet loss in the received vector
462 * @ret: true when there is a loss
463 */
464bool TfwcSndr::detect_loss() {
465        bool ret;       // 'true' when there is a loss
466        bool is_there = false;
467        int count = 0; // packet loss counter
468
469        // compare refvec and seqvec
470        for (int i = 0; i < num_refvec_; i++) {
471                for (int j = num_seqvec_-1; j >= 0; j--) {
472                        if (refvec_[i] == seqvec_[j]) {
473                                is_there = true;
474                                // we found it, so reset count
475                                count = 0; break;
476                        } else {
477                                is_there = false;
478                                count++;
479                        }
480                } // packet loss should be captured by now
481
482                // record the very first lost packet seqno
483                if(!is_there) {
484                        if(!is_first_loss_seen_)
485                        first_lost_pkt_ = refvec_[i];
486                }
487        }
488        return ret = (count > 0) ? true : false;
489}
490
491/*
492 * update RTT using the sampled RTT value
493 */
494void TfwcSndr::update_rtt(double rtt_sample) {
495        // calculate t0_
496        t_rtt_ = int(rtt_sample/tcp_tick_ + .5);
497        if(t_rtt_ == 0) t_rtt_ = 1;
498
499        if(t_srtt_ != 0) {
500                register short rtt_delta;
501                rtt_delta = t_rtt_ - (t_srtt_ >> T_SRTT_BITS);
502
503                if ((t_srtt_ += rtt_delta) <= 0)
504                        t_srtt_ = 1;
505
506                if (rtt_delta < 0)
507                        rtt_delta = -rtt_delta;
508
509                rtt_delta -= (t_rttvar_ >> T_RTTVAR_BITS);
510                if((t_rttvar_ += rtt_delta) <= 0)
511                        t_rttvar_ = 1;
512        }
513        else {
514                t_srtt_ = t_rtt_ << T_SRTT_BITS;
515                t_rttvar_ = t_rtt_ << (T_RTTVAR_BITS-1);
516        }
517
518        // finally, t0_ = (smoothed RTT) + 4 * (rtt variance)
519        t0_ = (((t_rttvar_ << (rttvar_exp_ + (T_SRTT_BITS - T_RTTVAR_BITS)))
520                        + t_srtt_)  >> T_SRTT_BITS ) * tcp_tick_;
521       
522        if (t0_ < minrto_)
523                t0_ = minrto_;
524
525        // calculate smoothed RTT
526        if (srtt_ < 0) {
527                // the first RTT observation
528                srtt_ = rtt_sample;
529                rttvar_ = rtt_sample/2.0;
530                sqrtrtt_ = sqrt(rtt_sample);
531        } else {
532                srtt_ = df_ * srtt_ + (1 - df_) * rtt_sample;
533                rttvar_ = rttvar_ + beta_ * (fabs(srtt_ - rtt_sample) - rttvar_);
534                sqrtrtt_ = df_ * sqrtrtt_ + (1 - df_) * sqrt(rtt_sample);
535        }
536
537        // update the current RTO
538        if(!to_driven_) {
539                if (k_ * rttvar_ > g_)
540                rto_ = srtt_ + k_ * rttvar_;
541                else
542                rto_ = srtt_ + g_;
543        }
544
545        // 'rto' could be rounded by 'maxrto'
546        if (rto_ > maxrto_)
547                rto_ = maxrto_;
548
549        print_rtt_info();
550}
551
552/*
553 * core part for congestion window control
554 * (cwnd is in packets)
555 */
556void TfwcSndr::cwnd_in_packets(bool revert) {
557        if(!revert) {
558        loss_history();
559        avg_loss_interval();
560        }
561
562        // loss event rate (p)
563        p_ = 1.0 / avg_interval_;
564
565        // simplified TCP throughput equation
566        double tmp1 = 12.0 * sqrt(p_ * 3.0/8.0);
567        double tmp2 = p_ * (1.0 + 32.0 * pow(p_, 2.0));
568        double term1 = sqrt(p_ * 2.0/3.0);
569        double term2 = tmp1 * tmp2;
570        f_p_ = term1 + term2;
571
572        // TFWC congestion window
573        t_win_ = 1. / f_p_;
574        cwnd_ = (int) (t_win_ + .5);
575
576        // timeout driven when cwnd is less than 2
577        if (t_win_ < 2.)
578                to_driven_ = true;
579        else
580                to_driven_ = false;
581
582        // cwnd should always be greater than 1
583        if (cwnd_ < 1)
584                cwnd_ = 1;
585}
586
587/*
588 * core part for congestion window control
589 * (cwnd is in bytes)
590 */
591void cwnd_in_bytes() {
592}
593
594/*
595 * generate weighting factors
596 */
597void TfwcSndr::gen_weight() {
598#ifdef SHORT_HISTORY
599        // this is just weighted moving average (WMA)
600        for(int i = 0; i <= HSZ; i++){
601                if(i < HSZ/2)
602                        weight_[i] = 1.0;
603                else
604                        weight_[i] = 1.0 - (i-(HSZ/2 - 1.0)) / (HSZ/2 + 1.0);
605        }
606#else
607        // this is exponentially weighted moving average (EWMA)
608        for (int i=0; i <= HSZ; i++) {
609                if (i < HSZ/4)
610                        weight_[i] = 1.0;
611                else
612                        weight_[i] = 2.0 / (i - 1.0);
613        }
614#endif
615}
616
617/*
618 * compute packet loss history
619 */
620void TfwcSndr::pseudo_history(double p) {
621        double pseudo = 1 / p;
622
623        /* bzero for all history information */
624        for(int i = 0; i <= HSZ+1; i++)
625                history_[i] = 0;
626
627        /* (let) most recent history information be 0 */
628        history_[0] = 0;
629
630        /* (let) the pseudo interval be the first history information */
631        history_[1] = pseudo;
632}
633/*
634 * TCP-like Additive Increase
635 * (until the very first packet loss)
636 */
637void TfwcSndr::tcp_like_increase() {
638        // if loss, do dupack action
639        if(detect_loss())
640                dupack_action(first_lost_pkt_);
641        // if no loss, do TCP-like AI
642        else
643                cwnd_++;
644}
645
646/*
647 * dupack action
648 *   o  halve cwnd_
649 *   o  marking pseudo loss history and loss rate
650 */
651void TfwcSndr::dupack_action(int seqno) {
652        // this is the very first packet loss
653        is_first_loss_seen_ = true;
654
655        // we now have just one meaningful history information
656        hsz_ = 1;
657
658        // halve the current cwnd_
659        cwnd_ = cwnd_ / 2;
660
661        // congestion window never goes below 1
662        if (cwnd_ < 1)
663                cwnd_ = 1;
664
665        // creating simulated loss history and loss rate
666        p_ = pseudo_p(cwnd_);
667        pseudo_history(p_);
668
669        // generate weight factors
670        gen_weight();
671
672        // finally, record the very first lost packet's timestamp
673        ts_ = tsvec_[seqno%TSZ];
674        // then, turn on TFWC algo
675        is_tfwc_on_ = true;
676}
677
678/*
679 * compute simulated loss rate
680 */
681double TfwcSndr::pseudo_p(int cwnd) {
682        double pseudo;
683        for (pseudo = 0.00001; pseudo < 1.0; pseudo += 0.00001) {
684        f_p_ = sqrt((2.0/3.0) * pseudo) + 12.0 * pseudo *
685        (1.0 + 32.0 * pow(pseudo, 2.0)) * sqrt((3.0/8.0) * pseudo);
686
687        t_win_ = 1 / f_p_;
688
689        if(t_win_ < cwnd)
690                break;
691        }
692
693        return (pseudo);
694}
695
696/*
697 * compute simulated loss history
698 */
699void TfwcSndr::loss_history() {
700        bool is_loss = false;           // is there a loss found in seqvec?
701        bool is_new_event = false;      // is this a new loss event?
702
703        // compare reference with seqvec
704        for (int i = 0; i < num_refvec_; i++) {
705                // is there a loss found?? and, is this a new loss event??
706                if (!find_seqno(seqvec_, num_seqvec_, refvec_[i])) {
707                        is_loss = true;
708                        if (tsvec_[refvec_[i]%TSZ] - ts_ > srtt_)
709                        is_new_event = true;
710                        else
711                        is_new_event = false;
712                }
713
714                // compute loss history (compare refvec and seqvec)
715                // o  everytime it sees a loss
716                //    it will compare the timestamp with smoothed RTT
717                //
718                // o  if the time difference is greater than RTT,
719                //    then this loss starts a new loss event
720                // o  if the time difference is less than RTT,
721                //    then we do nothing
722                //
723                // o  if there is no loss,
724                //    simply increment the loss interval by one
725                if (is_loss && is_new_event) {
726                        // this is a new loss event!
727
728                        // store previous ALI before changing history
729                        record_history(refvec_[i], avg_interval_, ts_);
730
731                        // increase current history size
732                        hsz_ = (hsz_ < HSZ) ? ++hsz_ : HSZ;
733
734                        // shift history information
735                        for (int k = HSZ; k > 0; k--)
736                                history_[k] = history_[k-1];
737
738                        // record lost packet's timestamp
739                        ts_ = tsvec_[refvec_[i]%TSZ];
740
741                        // let the most recent history information be one
742                        history_[0] = 1;
743                }
744                else {
745                        // this is not a new loss event
746                        // increase the current history information
747                        history_[0]++;
748                }
749        }
750}
751
752/*
753 * average loss interval
754 */
755void TfwcSndr::avg_loss_interval() {
756
757        I_tot0_ = 0;
758        I_tot1_ = 0;
759        tot_weight_ = 0;
760        int i = 0, j = 0;
761
762        // make a decision whether to include the most recent loss interval
763        //fprintf(stderr, "\n\tHIST_0 [");
764        for (i = 0; i < hsz_; i++) {
765                I_tot0_ += weight_[i] * history_[i];
766                tot_weight_ += weight_[i];
767        //      print_history_item(i);
768        }
769        //fprintf(stderr, "]\n");
770        //fprintf(stderr, "\tHIST_1 [");
771        for (i = 1, j = 0; i < hsz_ + 1; i++, j++) {
772                I_tot1_ += weight_[i-1] * history_[i];
773        //      print_history_item(i, j);
774        }
775        //fprintf(stderr, "]\n");
776
777        // compare I_tot0_ and I_tot1_ and use larger value
778        if (I_tot0_ < I_tot1_)
779                I_tot_ = I_tot1_;
780        else
781                I_tot_ = I_tot0_;
782
783        // this is average loss interval
784        avg_interval_ = I_tot_ / tot_weight_;
785        print_ALI();
786}
787
788/*
789 * store loss interval and timestamp
790 */
791void TfwcSndr::record_history(int seqno, double interval, double ts) {
792        // store seqno
793        new_hist_seqno_[new_hist_seqno_size_++] = seqno;
794        // store average loss interval
795        prev_interval_[seqno%RSZ] = interval;
796        // store timestamp
797        prev_ts_ = ts;
798        // copy history
799        for(int i = 0; i < hsz_; i++)
800        prev_history_[i] = history_[i];
801}
802
803/*
804 * revert average loss interval on packet re-ordering
805 */
806bool TfwcSndr::revert_interval(int reseq) {
807        // we didn't see the first lost packet yet.
808        if(!is_first_loss_seen_) {
809                dupack_action(reseq);
810                return (false);
811        }
812
813        // check if this re-ordered seqno actually triggered a new loss event
814        // if yes, revert to the previous state
815        if(find_seqno(new_hist_seqno_, new_hist_seqno_size_, reseq)) {
816                // reverting to the previous ALI
817                avg_interval_ = prev_interval_[reseq%RSZ];
818                // reverting to the previous timestamp
819                ts_ = prev_ts_;
820                // reverting to the previous history
821                for (int i = 0; i < hsz_; i++)
822                history_[i] = prev_history_[i];
823
824                print_ALI();
825
826                // finally, clear up the state variables
827                clear_prev_interval(RSZ);
828                clear_new_hist_seqno(new_hist_seqno_size_);
829                return (true);
830        }
831        return (false);
832}
833
834/*
835 * find seqno in the array
836 */
837bool TfwcSndr::find_seqno (u_int16_t *v, int n, int target) {
838        for (int i = 0; i < n; i++) {
839                if (v[i] == target)
840                return true;
841        }
842        return false;
843}
844bool TfwcSndr::find_seqno(u_int32_t *v, int n, u_int32_t target) {
845        for (int i = 0; i < n; i++) {
846                if(v[i] == target)
847                return true;
848        }
849        return false;
850}
851
852/*
853 * print history item
854 */
855void TfwcSndr::print_history_item (int i) {
856        fprintf(stderr, "%d", history_[i]);
857        if (i < hsz_ - 1) fprintf(stderr, ", ");
858}
859
860void TfwcSndr::print_history_item (int i, int j) {
861        fprintf(stderr, "%d", history_[i]);
862        if (j < hsz_ - 1) fprintf(stderr, ", ");
863}
864
865/*
866 * retransmission timer-out
867 */
868void TfwcSndr::expire(int option) {
869        if (option == TFWC_TIMER_RTX) {
870                if(!to_driven_)
871                reset_rtx_timer(1);
872                else
873                reset_rtx_timer(0);
874
875                // artificially inflate the latest ack
876                if(!to_driven_)
877                        jacked_++;
878
879                // trigger packet sending
880                cc_tfwc_output();
881        }
882}
883
884/*
885 * reset Rtx Timer
886 */
887void TfwcSndr::reset_rtx_timer (int backoff) {
888        if(backoff)
889                backoff_timer();
890
891        set_rtx_timer();
892}
893
894/*
895 * backoff Rtx Timer
896 */
897void TfwcSndr::backoff_timer() {
898        if (srtt_ < 0) srtt_ = 1.0;
899        rto_ = 2.0 * srtt_;
900
901        if (rto_ > maxrto_)
902                rto_ = maxrto_;
903}
904
905/*
906 * set Rtx Timer
907 */
908void TfwcSndr::set_rtx_timer() {
909        // resched() is basically msched(miliseconds)
910        rtx_timer_.resched(rto_ * 1000.);
911}
912
913/*
914 * new RTO calculation
915 */
916void TfwcSndr::new_rto(double rtt) {
917        double tmp1 = 3. * sqrt(p_ * 3./8.);
918        double tmp2 = t0_ * p_ * (1. + 32. * pow(p_, 2.));
919
920        if(tmp1 > 1.)
921                tmp1 = 1.;
922
923        double term1 = rtt * sqrt(p_ * 2./3.);
924        double term2 = tmp1 * tmp2;
925
926        rto_ = (term1 + term2) * sqrt(rtt)/sqrtrtt_;
927}
928
929/*
930 * clokcing packet out on re-ordering detection
931 */
932void TfwcSndr::packet_clocking (pktbuf* pb, bool flag) {
933        if (flag)
934                cc_tfwc_trigger();
935        else
936                cc_tfwc_trigger(pb);
937}
Note: See TracBrowser for help on using the browser.