root/vic/branches/cc/cc/tfrc_sndr.cpp @ 4854

Revision 4854, 14.8 KB (checked in by soohyunc, 4 years ago)

printing send rate

  • Property svn:keywords set to Id Revision
Line 
1/*
2 * Copyright (c) 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 <stdio.h>
35#include <stdlib.h>
36#include <math.h>
37#include <sys/types.h>
38#include "assert.h"
39#include "rtp.h"
40#include "inet.h"
41#include "pktbuf-rtp.h"
42#include "vic_tcl.h"
43#include "module.h"
44#include "transmitter.h"
45#include "tfrc_sndr.h"
46#include "formula.h"
47
48// TfrcSndr instance
49TfrcSndr TfrcSndr::instance_;
50
51// initial TFRC send rate (bytes/sec)
52#define INIT_RATE MAX_RTP
53
54/*
55 * TFRC Sender Constructor
56 */
57TfrcSndr::TfrcSndr() :
58        seqno_(0),
59        x_rate_(INIT_RATE),
60        aoa_(0),
61        now_(0),
62        so_recv_(0),
63        ndtp_(0),
64        nakp_(0),
65        ntep_(0),
66        nsve_(0),
67        jacked_(0),
68        begins_(0),
69        ends_(0),
70        num_elm_(1),
71        num_vec_(1)
72{
73        // allocate tsvec_ in memory
74        tsvec_ = (double *) malloc(sizeof(double) * TSZ);
75        clear_tsv(TSZ);
76        // allocate seqvec in memory
77        seqvec_ = (u_int32_t *) malloc(sizeof(u_int32_t) * SSZ);
78        clear_sqv(SSZ);
79        num_seqvec_ = 0;
80        // allocate refvec in memory
81        refvec_ = (u_int32_t *) malloc(sizeof(u_int32_t) * RSZ);
82        clear_refv(RSZ);
83        num_refvec_ = 0;
84
85        // initialize variables
86        minrto_ = 0.0;
87        maxrto_ = 100000.0;
88        srtt_ = -1.0;
89        rto_ = 3.0;     // RFC 1122
90        rttvar_ = 0.0;
91        df_ = 0.95;
92        sqrtrtt_ = 1.0;
93        t0_ = 6.0;
94        alpha_ = 0.125;
95        beta_ = 0.25;
96        g_ = 0.01;
97        k_ = 4;
98        ts_ = 0.0;
99
100        is_tfrc_on_ = false;
101        is_first_loss_seen_ = false;
102        first_lost_pkt_ = -1;
103        num_missing_ = 0;
104
105        avg_interval_ = 0.0;
106        I_tot0_ = 0.0;
107        I_tot1_ = 0.0;
108        tot_weight_ = 0.0;
109
110        tcp_tick_ = 0.01;
111        srtt_init_ = 12;
112        rttvar_exp_ = 2;
113        t_srtt_ = int(srtt_init_/tcp_tick_) << T_SRTT_BITS;
114        t_rttvar_ = int(rttvar_init_/tcp_tick_) << T_RTTVAR_BITS;
115
116        // record packet size in bytes
117        record_ = (u_int16_t *)malloc(sizeof(u_int16_t) * PSR);
118        clear_record(PSR);
119        // EWMA packet size
120        asize_ = 0;
121        pcnt_ = 0;
122        psize_ = 1000;
123        lambda1_ = .75;
124        lambda2_ = .15;
125}
126
127/*
128 * TFRC send
129 */
130void TfrcSndr::send(pktbuf* pb, double now) {
131        // the very first data packet
132        if(seqno_ == 0)
133        ts_off_ = tx_ts_offset();
134
135        // parse seqno and mark timestamp for this data packet
136        rtphdr* rh = (rtphdr *) pb->data;
137        seqno_  = ntohs(rh->rh_seqno);
138        now_    = now;
139
140        // alrithmetic average packet size (per frame)
141        asize_ += pb->len;
142        pcnt_++;
143
144        // tag finished (end of frame)
145        if (!(pb->tag)) {
146                asize_ /= pcnt_;
147                // EWMA'd packet size
148                if (pcnt_ > SMALL_FRAME)
149                psize_ = lambda1_ * asize_ + (1 - lambda1_) * psize_;
150                else
151                psize_ = lambda2_ * asize_ + (1 - lambda2_) * psize_;
152
153                asize_ = 0; pcnt_ = 0;
154        }
155        // number of *estimated* bytes for this packet
156        record_[seqno_%PSR] = psize_;
157        //print_psize(now_, psize_, pb->len);
158
159        // timestamp vector for loss history update
160        tsvec_[seqno_%TSZ]  = now_-SKEW;
161        //print_packet_tsvec();
162
163        // sequence number must be greater than zero
164        assert (seqno_ > 0);
165        // number of total data packet sent
166        ndtp_++;
167}
168
169/*
170 * main TFRC reception path
171 */
172void TfrcSndr::recv(u_int16_t type, u_int16_t begin, u_int16_t end,
173        u_int16_t *chunk, double so_rtime, bool ack_clock, pktbuf* pb)
174{
175  UNUSED(ack_clock);
176  UNUSED(pb);
177
178  switch(type) {
179  // XR block type 1
180  case XR_BT_1:
181  {
182        // number of ack received
183        nakp_++;
184        // so_timestamp
185        so_recv_ = so_rtime;
186        // revert to the previous history?
187        bool revert = false;
188
189        // get start/end seqno that this XR chunk reports
190        begins_ = begin;        // lowest packet seqno
191        ends_ = end;            // highest packet seqno plus one
192
193        // just acked seqno
194        // i.e.,) head seqno(= highest seqno) of this ackvec
195        jacked_ = ends_ - 1;
196
197        // get the number of AckVec chunks
198        //   use seqno space to work out the num chunks
199        //   (add one to num unless exactly divisible by BITLEN
200        //   - so it is large enough to accomodate all the bits)
201        num_elm_ = get_numelm(begins_, jacked_);
202        num_vec_ = get_numvec(num_elm_);
203
204        // declared AckVec
205        ackv_ = (u_int16_t *) malloc (sizeof(u_int16_t) * num_vec_);
206        // clear the existing AckVec
207        clear_ackv(num_vec_);
208        // clone AckVec from Vic
209        clone_ackv(chunk, num_vec_);
210        //print_vec("ackvec", ackv_, num_vec_);
211
212        // generate seqno vector
213        gen_seqvec(ackv_, num_vec_);
214
215        // generate margin vector
216        marginvec(jacked_);
217        print_mvec();
218
219        // generate reference vector
220        // (it represents seqvec when no losses)
221        // @begin: aoa_+1 (lowest seqno)
222        // @end: jacked_
223        gen_refvec(mvec_[DUPACKS-1]-1, aoa_+1);
224
225        // TFRC congestioin control
226        update_xrate();
227
228        // set ackofack (real number)
229        aoa_ = ackofack();
230
231        // sampled RTT
232        tao_ = so_recv_ - tsvec_[jacked_%TSZ];
233        // update RTT with the sampled RTT
234        update_rtt(tao_);
235
236        // reset variables for the next pkt reception
237        reset_var(revert);
238  }
239  break;
240
241  // XR block type 3
242  case XR_BT_3:
243  {}
244  break;
245  }
246}
247
248/*
249 * generate seqno vector
250 * (interpret the received AckVec to real sequence numbers)
251 * @ackvec: receivec AckVec
252 */
253void TfrcSndr::gen_seqvec(u_int16_t *v, int n) {
254        // clear seqvec before starts
255        clear_sqv(num_seqvec_);
256       
257        int i, j, k = 0;
258        int x = num_elm_%BITLEN;
259
260        // start of seqvec (lowest seqno)
261        int start = begins_;
262
263        for (i = 0; i < n-1; i++) {
264                for (j = BITLEN; j > 0; j--) {
265                        if( CHECK_BIT_AT(v[i], j) )
266                                seqvec_[k++%SSZ] = start;
267                        else num_missing_++;
268                        start++;
269                }
270        }
271
272        int a = (x == 0) ? BITLEN : x;
273        for (i = a; i > 0; i--) {
274                if( CHECK_BIT_AT(v[n-1], i) )
275                        seqvec_[k++%SSZ] = start;
276                else num_missing_++;
277                start++;
278        }
279
280        // therefore, the number of seqvec elements is:
281        num_seqvec_ = num_elm_ - num_missing_;
282        // printing retrieved sequence numbers from received AckVec
283        print_vec("sequence numbers", seqvec_, num_seqvec_);
284}
285
286/*
287 * generate reference vector
288 * (it represents seqno vector when no losses)
289 * @end:        end seqno (highest)
290 * @begin:      begin seqno (lowest)
291 */
292void TfrcSndr::gen_refvec(int end, int begin) {
293        // clear previous reference vector
294        clear_refv(num_refvec_);
295        // number of reference element - when no loss
296        num_refvec_ = end - begin + 1;
297
298        // generate refvec elements
299        fprintf(stderr, "\tcomparing numbers: (");
300        for (int i = 0; i < num_refvec_; i++) {
301                refvec_[i] = begin + i;
302                fprintf(stderr, " %d", refvec_[i]);
303        } fprintf(stderr, " )\n");
304}
305
306void TfrcSndr::reset_var(bool reverted) {
307        // init vars------------*
308        num_missing_ = 0;
309        //----------------------*
310
311        if(!reverted) {
312        }
313
314        // finally, free ackvec
315        free(ackv_);
316}
317
318/*
319 * detect the very first packet loss
320 * @ret: true if there is a loss
321 */
322bool TfrcSndr::detect_loss() {
323        bool ret;       // true if there is a loss
324        bool is_there = false;
325        int count = 0;  // packet loss counter
326
327        // compare refvec and seqvec
328        for (int i = 0; i < num_refvec_; i++) {
329          for (int j = num_seqvec_-1; j >= 0; j--) {
330            if(refvec_[i] == seqvec_[j]) {
331                  is_there = true;
332                  // we found it, so reset and break
333                  count = 0; break;
334                } else {
335                  is_there = false;
336                  count++;
337                }
338          } // packet loss should be captured by now
339
340          // record the very first lost packet seqno
341          if(!is_there) {
342            if(!is_first_loss_seen_)
343                first_lost_pkt_ = refvec_[i];
344          }
345        }
346        return ret = (count > 0) ? true : false;
347}
348
349/*
350 *
351 */
352void TfrcSndr::dupack_action(int seqno) {
353        // this is the very first packet loss
354        is_first_loss_seen_ = true;
355
356        // we now have just one meaningful history information
357        hsz_ = 1;
358
359        // cut rate in half
360        x_rate_ /= 2.0;
361
362        // creating simulated loss history and loss rate
363        p_ = pseudo_p(x_rate_);
364        pseudo_history(p_);
365
366        // generate weight factors
367        gen_weight();
368
369        // finally, record the very first lost packet's timestamp
370        ts_ = tsvec_[seqno%TSZ];
371        //then, turn on TFRC algo
372        is_tfrc_on_ = true;
373}
374
375/*
376 * TCP-like slow start
377 */
378void TfrcSndr::slow_start() {
379        double m = 2.0;
380        x_rate_ = m * x_rate_;
381}
382
383/*
384 * TCP-like Additive Increase
385 * (until the very first packet loss)
386 */
387void TfrcSndr::tcp_like_increase() {
388        // if loss, do TCP's dupack-like action
389        if(detect_loss())
390                dupack_action(first_lost_pkt_);
391        // if no loss, do TCP-like AI
392        else
393                slow_start();
394}
395
396/*
397 * generate weighting factors
398 */
399void TfrcSndr::gen_weight() {
400#ifdef SHORT_HISTORY
401        // this is just weighted moving average (WMA)
402        for(int i = 0; i <= HSZ; i++){
403          if(i < HSZ/2)
404                weight_[i] = 1.0;
405          else
406                weight_[i] = 1.0 - (i-(HSZ/2 - 1.0)) / (HSZ/2 + 1.0);
407        }
408#else
409        // this is exponentially weighted moving average (EWMA)
410        for (int i=0; i <= HSZ; i++) {
411          if (i < HSZ/4)
412                weight_[i] = 1.0;
413          else
414                weight_[i] = 2.0 / (i - 1.0);
415        }
416#endif
417}
418
419/*
420 * compute simulated loss rate
421 */
422double TfrcSndr::pseudo_p(double rate) {
423        double pseudo;
424        double f, x;
425        for (pseudo = 0.00001; pseudo < 1.0; pseudo += 0.00001) {
426          f = sqrt((2.0/3.0) * pseudo) + 12.0 * pseudo *
427            (1.0 + 32.0 * pow(pseudo, 2.0)) * sqrt((3.0/8.0) * pseudo);
428
429          x = 1./(srtt_ * f);
430
431          if (x < rate)
432                break;
433        }
434        return (pseudo);
435}
436
437/*
438 * compute simulated loss history
439 */
440void TfrcSndr::pseudo_history(double p) {
441        double pseudo_interval = 1.0 / p;
442
443        // bzero for all history information
444        for (int i = 0; i <= HSZ+1; i++)
445                history_[i] = 0;
446        // let most recent history information be 0
447        history_[0] = 0;
448        // put the pseudo interval in the first history bucket
449        history_[1] = pseudo_interval;
450}
451
452/*
453 * update sending rate
454 */
455void TfrcSndr::update_xrate() {
456        // TFRC is not in action yet (i.e., no packet loss yet)
457        if(!is_tfrc_on_)
458          tcp_like_increase();
459        // TFRC is turned on, so compute send rate
460        else
461          calc_xrate();
462
463        print_xrate();
464}
465
466/*
467 * calculate send rate
468 */
469void TfrcSndr::calc_xrate() {
470        loss_history();
471        avg_loss_interval();
472
473        // loss event rate (p)
474        p_ = 1.0 / avg_interval_;
475
476        // sending rate (bytes/sec)
477        x_rate_ = p_to_b(p_, srtt_, t0_, psize_, 1);
478}
479
480/*
481 * update RTT using sampled RTT value
482 */
483void TfrcSndr::update_rtt(double rtt_sample) {
484        // calculate t0_
485        t_rtt_ = int(rtt_sample/tcp_tick_ + .5);
486        if(t_rtt_ == 0) t_rtt_ = 1;
487
488        if(t_srtt_ != 0) {
489                register short rtt_delta;
490                rtt_delta = t_rtt_ - (t_srtt_ >> T_SRTT_BITS);
491
492                if ((t_srtt_ += rtt_delta) <= 0)
493                t_srtt_ = 1;
494
495                if (rtt_delta < 0)
496                rtt_delta = -rtt_delta;
497
498                rtt_delta -= (t_rttvar_ >> T_RTTVAR_BITS);
499                if((t_rttvar_ += rtt_delta) <= 0)
500                t_rttvar_ = 1;
501        }
502        else {
503                t_srtt_ = t_rtt_ << T_SRTT_BITS;
504                t_rttvar_ = t_rtt_ << (T_RTTVAR_BITS-1);
505        }
506
507        // finally, t0_ = (smoothed RTT) + 4 * (rtt variance)
508        t0_ = (((t_rttvar_ << (rttvar_exp_ + (T_SRTT_BITS - T_RTTVAR_BITS)))
509                + t_srtt_)  >> T_SRTT_BITS ) * tcp_tick_;
510
511        if (t0_ < minrto_)
512                t0_ = minrto_;
513
514        // calculate smoothed RTT
515        if (srtt_ < 0) {
516                // the first RTT observation
517                srtt_ = rtt_sample;
518                rttvar_ = rtt_sample/2.0;
519                sqrtrtt_ = sqrt(rtt_sample);
520        } else {
521                srtt_ = df_ * srtt_ + (1 - df_) * rtt_sample;
522                rttvar_ = rttvar_ + beta_ * (fabs(srtt_ - rtt_sample) - rttvar_);
523                sqrtrtt_ = df_ * sqrtrtt_ + (1 - df_) * sqrt(rtt_sample);
524        }
525
526        // 'rto' could be rounded by 'maxrto'
527        if (rto_ > maxrto_)
528                rto_ = maxrto_;
529
530        print_rtt_info();
531}
532
533/*
534 * compute loss history
535 */
536void TfrcSndr::loss_history() {
537        bool is_loss = false;       // is there a loss found in seqvec?
538        bool is_new_event = false;  // is this a new loss event?
539
540        // compare reference with seqvec
541        for (int i = 0; i < num_refvec_; i++) {
542          // is there a loss found?? and, is this a new loss event??
543          if (!find_seqno(seqvec_, num_seqvec_, refvec_[i])) {
544                is_loss = true;
545                if (tsvec_[refvec_[i]%TSZ] - ts_ > srtt_)
546                  is_new_event = true;
547                else
548                  is_new_event = false;
549          }
550
551          // compute loss history (compare refvec and seqvec)
552          // o  everytime it sees a loss
553          //    it will compare the timestamp with smoothed RTT
554          //
555          // o  if the time difference is greater than RTT,
556          //    then this loss starts a new loss event
557          // o  if the time difference is less than RTT,
558          //    then we do nothing
559          //
560          // o  if there is no loss,
561          //    simply increment the loss interval by one
562          if (is_loss && is_new_event) {
563                // this is a new loss event!
564
565                // store previous ALI before changing history
566                //record_history(refvec_[i], avg_interval_, ts_);
567
568                // increase current history size
569                hsz_ = (hsz_ < HSZ) ? ++hsz_ : HSZ;
570
571                // shift history information
572                for (int k = HSZ; k > 0; k--)
573                        history_[k] = history_[k-1];
574
575                // record lost packet's timestamp
576                ts_ = tsvec_[refvec_[i]%TSZ];
577
578                // let the most recent history information be one
579                history_[0] = 1;
580          }
581          else {
582                // this is not a new loss event
583                // increase the current history information
584                history_[0]++;
585          }
586        } // end for(;;) statement
587}
588
589/*
590 * average loss interval
591 */
592void TfrcSndr::avg_loss_interval() {
593
594        I_tot0_ = 0;
595        I_tot1_ = 0;
596        tot_weight_ = 0;
597        int i = 0, j = 0;
598
599        // make a decision whether to include the most recent loss interval
600        //fprintf(stderr, "\n\tHIST_0 [");
601        for (i = 0; i < hsz_; i++) {
602                I_tot0_ += weight_[i] * history_[i];
603                tot_weight_ += weight_[i];
604        //  print_history_item(i);
605        }
606        //fprintf(stderr, "]\n");
607        //fprintf(stderr, "\tHIST_1 [");
608        for (i = 1, j = 0; i < hsz_ + 1; i++, j++) {
609                I_tot1_ += weight_[i-1] * history_[i];
610        //  print_history_item(i, j);
611        }
612        //fprintf(stderr, "]\n");
613
614        // compare I_tot0_ and I_tot1_ and use larger value
615        if (I_tot0_ < I_tot1_)
616                I_tot_ = I_tot1_;
617        else
618                I_tot_ = I_tot0_;
619
620        // this is average loss interval
621        avg_interval_ = I_tot_ / tot_weight_;
622        print_ALI();
623}
624
625/*
626 * find seqno in the array
627 */
628bool TfrcSndr::find_seqno (u_int16_t *v, int n, int target) {
629        for (int i = 0; i < n; i++) {
630          if (v[i] == target)
631                return true;
632        }
633        return false;
634}
635bool TfrcSndr::find_seqno(u_int32_t *v, int n, u_int32_t target) {
636        for (int i = 0; i < n; i++) {
637          if(v[i] == target)
638                return true;
639        }
640        return false;
641}
642
643/*
644 * print history item
645 */
646void TfrcSndr::print_history_item (int i) {
647        fprintf(stderr, "%d", history_[i]);
648        if (i < hsz_ - 1) fprintf(stderr, ", ");
649}
650
651void TfrcSndr::print_history_item (int i, int j) {
652        fprintf(stderr, "%d", history_[i]);
653        if (j < hsz_ - 1) fprintf(stderr, ", ");
654}
Note: See TracBrowser for help on using the browser.