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

Revision 4763, 21.9 KB (checked in by soohyunc, 4 years ago)

Subsequent to the Revision 4762... (to prevent from segfault)

had to consider all re-ordering cases (e.g., packet reordering, ack reordering,
depricated ack reception)

i.e., if the above cases occurred before we see the first packet loss, then we
do not have any history to go back. therefore, we increase cwnd to clock a
packet out.

  • 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                  window_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(!is_tfwc_on_)
248                  // if the disorder is beyond 3 dupack rule,
249                  // revert to the earlier history
250                  if(shift >= DUPACKS)
251                  revert = revert_interval(jacked_);
252                  // then, update cwnd
253                  window_in_packets(revert);
254                  print_cwnd();
255                  // finally, reset variables
256                  reset_var(revert);
257                  return;
258                }
259                //
260                // packet is out-of-order, so adjust ackvec re-construction
261                //
262                else {
263                  debug_msg("warning: packet reordering occurred!\n");
264                  // replace just ack'ed seqno
265                  replace(__jacked_);
266                  // re-calculate numelm and numvec
267                  num_elm_ = get_numelm(begins_, jacked_);
268                  num_vec_ = get_numvec(num_elm_);
269                  reorder_ = true;
270                }
271        }
272        else {
273                free(pvec_);
274        }
275        //---------------------------------------------------------*
276
277        // if packet reordering occurred, insert re-ordered seqno
278        // into the received ackvec using previously received ackvec
279        if(reorder_) {
280                for (int i = 0; i < num_vec_; i++) {
281                ackv_[i] = (ackv_[i] << shift) | pvec_[i];
282                }
283        }
284        // this will ensure constructing ackv correctly,
285        // when there is packet re-ordering.
286        // (e.g., if packet reordering, then ack will be ordered that way.)
287        else {
288                for (int i = 0; i < num_vec_; i++) {
289                ackv_[i] = (pvec_[i] << shift) | ackv_[i];
290                }
291        }
292
293        // generate seqno vector
294        //print_vec("ackvec", ackv_, num_vec_);
295        gen_seqvec(ackv_, num_vec_);
296
297        // generate margin vector
298        marginvec(jacked_);
299        print_mvec();
300
301        // generate reference vector
302        // (it represents seqvec when there are no losses)
303        //      @begin: aoa_+1 (lowest seqno)
304        //      @end: mvec_[DUPACKS-1] - 1
305        gen_refvec(mvec_[DUPACKS-1]-1, aoa_+1);
306
307        // we have detected packet re-ordering!!!
308        // so, we've updated/corrected received ackvec
309        // by inserting "jacked" to the previous ackvec.
310        // finally, we only need to clock packets out.
311        // (i.e., do NOT update cwnd and RTT)
312        if(reorder_) {
313                // revert to the earlier history if the disorder is beyond 3 dupack rule
314                if (shift >= DUPACKS)
315                revert = revert_interval(jacked_);
316                // then, update cwnd
317                window_in_packets(revert);
318                print_cwnd();
319                // finally, reset variables
320                reset_var(revert);
321                return;
322        }
323
324        // TFWC congestion window in packets
325        window_in_packets(revert);
326        print_cwnd();
327
328        // set ackofack (real number)
329        aoa_ = ackofack();
330
331        // sampled RTT
332        tao_ = so_recv_ - tsvec_[jacked_%TSZ];
333        // update RTT with the sampled RTT
334        update_rtt(tao_);
335
336        // is TFWC being driven by timeout mechanism?
337        if(to_driven_ && is_tfwc_on_)
338                new_rto(tao_);
339       
340        // reset variables for the next pkt reception
341        reset_var(revert);
342  }
343  break;
344
345  // retrieve ts echo
346  case XR_BT_3:
347  {
348        ntep_++;                // number of ts echo packet received
349        ts_echo_ = chunk[num_vec_ - 1];
350        //fprintf(stderr, "    [%s +%d] ts echo:        %f\n",
351        //      __FILE__,__LINE__, ts_echo_);
352
353        tao_ = now() - ts_echo_;
354  }
355  break;
356
357  default:
358  break;
359  } // end switch (type)
360
361  return;
362}
363
364/*
365 * TFWC congestion window in packets
366 */
367void TfwcSndr::window_in_packets(bool revert) {
368        // TFWC is not turned on (i.e., no packet loss yet)
369        if(!is_tfwc_on_)
370                tcp_like_increase();
371        // TFWC is turned on, so compute congestion window
372        else
373                cwnd_in_packets(revert);
374}
375
376/*
377 * detect out-of-ordered ack delivery
378 * -- if just ack'ed seqno (jack) is already in sequence vector,
379 *    then, this ack should've been arrived earlier.
380 *    (i.e., this ack is out-of-ordered)
381 */
382bool TfwcSndr::out_of_ack(u_int16_t target, u_int32_t *sqv, int n) {
383        for (int i = 0; i < n; i++) {
384                if (sqv[i] == target)
385                return true;
386        }
387        return false;
388}
389
390void TfwcSndr::reset_var(bool reverted) {
391        // init vars------------*
392        num_missing_ = 0;
393        //----------------------*
394
395        if(!reverted) {
396        // store jack'ed
397        store(jacked_);
398        // declare pvec to store ackv
399        pvec_ = (u_int16_t *)malloc(sizeof(u_int16_t) * num_vec_);
400        clear_pvec(num_vec_);
401        // store ackv
402        copy_ackv(num_vec_);
403        //print_vec("stored ackvec", pvec_, num_vec_);
404        }
405
406        // finally, free ackvec
407        free(ackv_);
408}
409
410/*
411 * generate seqno vector
412 * (interpret the received AckVec to real sequence numbers)
413 * @ackvec: received AckVec
414 */
415void TfwcSndr::gen_seqvec (u_int16_t *v, int n) {
416        // clear seqvec before starts
417        clear_sqv(num_seqvec_);
418
419        int i, j, k = 0;
420        int x = num_elm_%BITLEN;
421
422        // start of seqvec (lowest seqno)
423        int start = begins_;
424
425        for (i = 0; i < n-1; i++) {
426                for (j = BITLEN; j > 0; j--) {
427                        if( CHECK_BIT_AT(v[i], j) )
428                                seqvec_[k++%SSZ] = start;
429                        else num_missing_++;
430                        start++;
431                }
432        }
433
434        int a = (x == 0) ? BITLEN : x;
435        for (i = a; i > 0; i--) {
436                if( CHECK_BIT_AT(v[n-1], i) )
437                        seqvec_[k++%SSZ] = start;
438                else num_missing_++;
439                start++;
440        }
441
442        // therefore, the number of seqvec elements is:
443        num_seqvec_ = num_elm_ - num_missing_;
444        // printing retrieved sequence numbers from received AckVec
445        print_vec("sequence numbers", seqvec_, num_seqvec_);
446}
447
448/*
449 * generate reference vector
450 * (it represents the seqno vector when no losses)
451 * @end:    end seqno   (highest)
452 * @begin:  begin seqno (lowest)
453 */
454void TfwcSndr::gen_refvec(int end, int begin) {
455        // clear previous reference vector
456        clear_refv(num_refvec_);
457        // number of reference element - when no loss
458        num_refvec_ = end - begin + 1;
459
460        // generate refvec elements
461        fprintf(stderr, "\tcomparing numbers: (");
462        for (int i = 0; i < num_refvec_; i++) {
463                refvec_[i] = begin + i;
464                fprintf(stderr, " %d", refvec_[i]);
465        } fprintf(stderr, " )\n");
466}
467
468/*
469 * detect packet loss in the received vector
470 * @ret: true when there is a loss
471 */
472bool TfwcSndr::detect_loss() {
473        bool ret;       // 'true' when there is a loss
474        bool is_there = false;
475        int count = 0; // packet loss counter
476
477        // compare refvec and seqvec
478        for (int i = 0; i < num_refvec_; i++) {
479                for (int j = num_seqvec_-1; j >= 0; j--) {
480                        if (refvec_[i] == seqvec_[j]) {
481                                is_there = true;
482                                // we found it, so reset count
483                                count = 0; break;
484                        } else {
485                                is_there = false;
486                                count++;
487                        }
488                } // packet loss should be captured by now
489
490                // record the very first lost packet seqno
491                if(!is_there) {
492                        if(!is_first_loss_seen_)
493                        first_lost_pkt_ = refvec_[i];
494                }
495        }
496        return ret = (count > 0) ? true : false;
497}
498
499/*
500 * update RTT using the sampled RTT value
501 */
502void TfwcSndr::update_rtt(double rtt_sample) {
503        // calculate t0_
504        t_rtt_ = int(rtt_sample/tcp_tick_ + .5);
505        if(t_rtt_ == 0) t_rtt_ = 1;
506
507        if(t_srtt_ != 0) {
508                register short rtt_delta;
509                rtt_delta = t_rtt_ - (t_srtt_ >> T_SRTT_BITS);
510
511                if ((t_srtt_ += rtt_delta) <= 0)
512                        t_srtt_ = 1;
513
514                if (rtt_delta < 0)
515                        rtt_delta = -rtt_delta;
516
517                rtt_delta -= (t_rttvar_ >> T_RTTVAR_BITS);
518                if((t_rttvar_ += rtt_delta) <= 0)
519                        t_rttvar_ = 1;
520        }
521        else {
522                t_srtt_ = t_rtt_ << T_SRTT_BITS;
523                t_rttvar_ = t_rtt_ << (T_RTTVAR_BITS-1);
524        }
525
526        // finally, t0_ = (smoothed RTT) + 4 * (rtt variance)
527        t0_ = (((t_rttvar_ << (rttvar_exp_ + (T_SRTT_BITS - T_RTTVAR_BITS)))
528                        + t_srtt_)  >> T_SRTT_BITS ) * tcp_tick_;
529       
530        if (t0_ < minrto_)
531                t0_ = minrto_;
532
533        // calculate smoothed RTT
534        if (srtt_ < 0) {
535                // the first RTT observation
536                srtt_ = rtt_sample;
537                rttvar_ = rtt_sample/2.0;
538                sqrtrtt_ = sqrt(rtt_sample);
539        } else {
540                srtt_ = df_ * srtt_ + (1 - df_) * rtt_sample;
541                rttvar_ = rttvar_ + beta_ * (fabs(srtt_ - rtt_sample) - rttvar_);
542                sqrtrtt_ = df_ * sqrtrtt_ + (1 - df_) * sqrt(rtt_sample);
543        }
544
545        // update the current RTO
546        if(!to_driven_) {
547                if (k_ * rttvar_ > g_)
548                rto_ = srtt_ + k_ * rttvar_;
549                else
550                rto_ = srtt_ + g_;
551        }
552
553        // 'rto' could be rounded by 'maxrto'
554        if (rto_ > maxrto_)
555                rto_ = maxrto_;
556
557        print_rtt_info();
558}
559
560/*
561 * core part for congestion window control
562 * (cwnd is in packets)
563 */
564void TfwcSndr::cwnd_in_packets(bool revert) {
565        if(!revert) {
566        loss_history();
567        avg_loss_interval();
568        }
569
570        // loss event rate (p)
571        p_ = 1.0 / avg_interval_;
572
573        // simplified TCP throughput equation
574        double tmp1 = 12.0 * sqrt(p_ * 3.0/8.0);
575        double tmp2 = p_ * (1.0 + 32.0 * pow(p_, 2.0));
576        double term1 = sqrt(p_ * 2.0/3.0);
577        double term2 = tmp1 * tmp2;
578        f_p_ = term1 + term2;
579
580        // TFWC congestion window
581        t_win_ = 1. / f_p_;
582        cwnd_ = (int) (t_win_ + .5);
583
584        // timeout driven when cwnd is less than 2
585        if (t_win_ < 2.)
586                to_driven_ = true;
587        else
588                to_driven_ = false;
589
590        // cwnd should always be greater than 1
591        if (cwnd_ < 1)
592                cwnd_ = 1;
593}
594
595/*
596 * core part for congestion window control
597 * (cwnd is in bytes)
598 */
599void cwnd_in_bytes() {
600}
601
602/*
603 * generate weighting factors
604 */
605void TfwcSndr::gen_weight() {
606#ifdef SHORT_HISTORY
607        // this is just weighted moving average (WMA)
608        for(int i = 0; i <= HSZ; i++){
609                if(i < HSZ/2)
610                        weight_[i] = 1.0;
611                else
612                        weight_[i] = 1.0 - (i-(HSZ/2 - 1.0)) / (HSZ/2 + 1.0);
613        }
614#else
615        // this is exponentially weighted moving average (EWMA)
616        for (int i=0; i <= HSZ; i++) {
617                if (i < HSZ/4)
618                        weight_[i] = 1.0;
619                else
620                        weight_[i] = 2.0 / (i - 1.0);
621        }
622#endif
623}
624
625/*
626 * compute packet loss history
627 */
628void TfwcSndr::pseudo_history(double p) {
629        double pseudo = 1 / p;
630
631        /* bzero for all history information */
632        for(int i = 0; i <= HSZ+1; i++)
633                history_[i] = 0;
634
635        /* (let) most recent history information be 0 */
636        history_[0] = 0;
637
638        /* (let) the pseudo interval be the first history information */
639        history_[1] = pseudo;
640}
641/*
642 * TCP-like Additive Increase
643 * (until the very first packet loss)
644 */
645void TfwcSndr::tcp_like_increase() {
646        // if loss, do dupack action
647        if(detect_loss())
648                dupack_action(first_lost_pkt_);
649        // if no loss, do TCP-like AI
650        else
651                cwnd_++;
652}
653
654/*
655 * dupack action
656 *   o  halve cwnd_
657 *   o  marking pseudo loss history and loss rate
658 */
659void TfwcSndr::dupack_action(int seqno) {
660        // this is the very first packet loss
661        is_first_loss_seen_ = true;
662
663        // we now have just one meaningful history information
664        hsz_ = 1;
665
666        // halve the current cwnd_
667        cwnd_ = cwnd_ / 2;
668
669        // congestion window never goes below 1
670        if (cwnd_ < 1)
671                cwnd_ = 1;
672
673        // creating simulated loss history and loss rate
674        p_ = pseudo_p(cwnd_);
675        pseudo_history(p_);
676
677        // generate weight factors
678        gen_weight();
679
680        // finally, record the very first lost packet's timestamp
681        ts_ = tsvec_[seqno%TSZ];
682        // then, turn on TFWC algo
683        is_tfwc_on_ = true;
684}
685
686/*
687 * compute simulated loss rate
688 */
689double TfwcSndr::pseudo_p(int cwnd) {
690        double pseudo;
691        for (pseudo = 0.00001; pseudo < 1.0; pseudo += 0.00001) {
692        f_p_ = sqrt((2.0/3.0) * pseudo) + 12.0 * pseudo *
693        (1.0 + 32.0 * pow(pseudo, 2.0)) * sqrt((3.0/8.0) * pseudo);
694
695        t_win_ = 1 / f_p_;
696
697        if(t_win_ < cwnd)
698                break;
699        }
700
701        return (pseudo);
702}
703
704/*
705 * compute simulated loss history
706 */
707void TfwcSndr::loss_history() {
708        bool is_loss = false;           // is there a loss found in seqvec?
709        bool is_new_event = false;      // is this a new loss event?
710
711        // compare reference with seqvec
712        for (int i = 0; i < num_refvec_; i++) {
713                // is there a loss found?? and, is this a new loss event??
714                if (!find_seqno(seqvec_, num_seqvec_, refvec_[i])) {
715                        is_loss = true;
716                        if (tsvec_[refvec_[i]%TSZ] - ts_ > srtt_)
717                        is_new_event = true;
718                        else
719                        is_new_event = false;
720                }
721
722                // compute loss history (compare refvec and seqvec)
723                // o  everytime it sees a loss
724                //    it will compare the timestamp with smoothed RTT
725                //
726                // o  if the time difference is greater than RTT,
727                //    then this loss starts a new loss event
728                // o  if the time difference is less than RTT,
729                //    then we do nothing
730                //
731                // o  if there is no loss,
732                //    simply increment the loss interval by one
733                if (is_loss && is_new_event) {
734                        // this is a new loss event!
735
736                        // store previous ALI before changing history
737                        record_history(refvec_[i], avg_interval_, ts_);
738
739                        // increase current history size
740                        hsz_ = (hsz_ < HSZ) ? ++hsz_ : HSZ;
741
742                        // shift history information
743                        for (int k = HSZ; k > 0; k--)
744                                history_[k] = history_[k-1];
745
746                        // record lost packet's timestamp
747                        ts_ = tsvec_[refvec_[i]%TSZ];
748
749                        // let the most recent history information be one
750                        history_[0] = 1;
751                }
752                else {
753                        // this is not a new loss event
754                        // increase the current history information
755                        history_[0]++;
756                }
757        }
758}
759
760/*
761 * average loss interval
762 */
763void TfwcSndr::avg_loss_interval() {
764
765        I_tot0_ = 0;
766        I_tot1_ = 0;
767        tot_weight_ = 0;
768        int i = 0, j = 0;
769
770        // make a decision whether to include the most recent loss interval
771        //fprintf(stderr, "\n\tHIST_0 [");
772        for (i = 0; i < hsz_; i++) {
773                I_tot0_ += weight_[i] * history_[i];
774                tot_weight_ += weight_[i];
775        //      print_history_item(i);
776        }
777        //fprintf(stderr, "]\n");
778        //fprintf(stderr, "\tHIST_1 [");
779        for (i = 1, j = 0; i < hsz_ + 1; i++, j++) {
780                I_tot1_ += weight_[i-1] * history_[i];
781        //      print_history_item(i, j);
782        }
783        //fprintf(stderr, "]\n");
784
785        // compare I_tot0_ and I_tot1_ and use larger value
786        if (I_tot0_ < I_tot1_)
787                I_tot_ = I_tot1_;
788        else
789                I_tot_ = I_tot0_;
790
791        // this is average loss interval
792        avg_interval_ = I_tot_ / tot_weight_;
793        print_ALI();
794}
795
796/*
797 * store loss interval and timestamp
798 */
799void TfwcSndr::record_history(int seqno, double interval, double ts) {
800        // store seqno
801        new_hist_seqno_[new_hist_seqno_size_++] = seqno;
802        // store average loss interval
803        prev_interval_[seqno%RSZ] = interval;
804        // store timestamp
805        prev_ts_ = ts;
806        // copy history
807        for(int i = 0; i < hsz_; i++)
808        prev_history_[i] = history_[i];
809}
810
811/*
812 * revert average loss interval on packet re-ordering
813 */
814bool TfwcSndr::revert_interval(int reseq) {
815        // we didn't see the first lost packet yet.
816        if(!is_first_loss_seen_) {
817                dupack_action(reseq);
818                return (false);
819        }
820
821        // check if this re-ordered seqno actually triggered a new loss event
822        // if yes, revert to the previous state
823        if(find_seqno(new_hist_seqno_, new_hist_seqno_size_, reseq)) {
824                // reverting to the previous ALI
825                avg_interval_ = prev_interval_[reseq%RSZ];
826                // reverting to the previous timestamp
827                ts_ = prev_ts_;
828                // reverting to the previous history
829                for (int i = 0; i < hsz_; i++)
830                history_[i] = prev_history_[i];
831
832                print_ALI();
833
834                // finally, clear up the state variables
835                clear_prev_interval(RSZ);
836                clear_new_hist_seqno(new_hist_seqno_size_);
837                return (true);
838        }
839        return (false);
840}
841
842/*
843 * find seqno in the array
844 */
845bool TfwcSndr::find_seqno (u_int16_t *v, int n, int target) {
846        for (int i = 0; i < n; i++) {
847                if (v[i] == target)
848                return true;
849        }
850        return false;
851}
852bool TfwcSndr::find_seqno(u_int32_t *v, int n, u_int32_t target) {
853        for (int i = 0; i < n; i++) {
854                if(v[i] == target)
855                return true;
856        }
857        return false;
858}
859
860/*
861 * print history item
862 */
863void TfwcSndr::print_history_item (int i) {
864        fprintf(stderr, "%d", history_[i]);
865        if (i < hsz_ - 1) fprintf(stderr, ", ");
866}
867
868void TfwcSndr::print_history_item (int i, int j) {
869        fprintf(stderr, "%d", history_[i]);
870        if (j < hsz_ - 1) fprintf(stderr, ", ");
871}
872
873/*
874 * retransmission timer-out
875 */
876void TfwcSndr::expire(int option) {
877        if (option == TFWC_TIMER_RTX) {
878                if(!to_driven_)
879                reset_rtx_timer(1);
880                else
881                reset_rtx_timer(0);
882
883                // artificially inflate the latest ack
884                if(!to_driven_)
885                        jacked_++;
886
887                // trigger packet sending
888                cc_tfwc_output();
889        }
890}
891
892/*
893 * reset Rtx Timer
894 */
895void TfwcSndr::reset_rtx_timer (int backoff) {
896        if(backoff)
897                backoff_timer();
898
899        set_rtx_timer();
900}
901
902/*
903 * backoff Rtx Timer
904 */
905void TfwcSndr::backoff_timer() {
906        if (srtt_ < 0) srtt_ = 1.0;
907        rto_ = 2.0 * srtt_;
908
909        if (rto_ > maxrto_)
910                rto_ = maxrto_;
911}
912
913/*
914 * set Rtx Timer
915 */
916void TfwcSndr::set_rtx_timer() {
917        // resched() is basically msched(miliseconds)
918        rtx_timer_.resched(rto_ * 1000.);
919}
920
921/*
922 * new RTO calculation
923 */
924void TfwcSndr::new_rto(double rtt) {
925        double tmp1 = 3. * sqrt(p_ * 3./8.);
926        double tmp2 = t0_ * p_ * (1. + 32. * pow(p_, 2.));
927
928        if(tmp1 > 1.)
929                tmp1 = 1.;
930
931        double term1 = rtt * sqrt(p_ * 2./3.);
932        double term2 = tmp1 * tmp2;
933
934        rto_ = (term1 + term2) * sqrt(rtt)/sqrtrtt_;
935}
936
937/*
938 * clokcing packet out on re-ordering detection
939 */
940void TfwcSndr::packet_clocking (pktbuf* pb, bool flag) {
941        if (flag)
942                cc_tfwc_trigger();
943        else
944                cc_tfwc_trigger(pb);
945}
Note: See TracBrowser for help on using the browser.