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

Revision 4657, 14.0 KB (checked in by soohyunc, 4 years ago)

-- added a timer for calculating TFWC's retransmission timeout

(To-do)
need to add some sort of send method when this timer goes off

  • 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
47/*
48 * retransmission timer
49 */
50void TfwcRtxTimer::timeout() {
51        s_ -> expire(TFWC_TIMER_RTX);
52}
53
54/*
55 * TFWC sender definition
56 */
57TfwcSndr::TfwcSndr() :
58        seqno_(0),
59        cwnd_(1),
60        aoa_(0),
61        t_now_(0),
62        t_ts_(0),
63        t_ts_echo_(0),
64        now_(0),
65        so_recv_(0),
66        ndtp_(0),
67        nakp_(0),
68        ntep_(0),
69        nsve_(0),
70        epoch_(1),
71        jacked_(0),
72        begins_(0),
73        ends_(0),
74        num_elm_(1),
75        num_vec_(1)
76{
77        // allocate tsvec_ in memory
78        tsvec_ = (double *)malloc(sizeof(double) * TSZ);
79        clear_tsv(TSZ);
80
81        // allocate seqvec in memory
82        seqvec_ = (u_int32_t *)malloc(sizeof(u_int32_t) * SSZ);
83        clear_sqv(SSZ);
84        num_seqvec_ = 0;
85
86        // allocate refvec in memory
87        refvec_ = (u_int32_t *)malloc(sizeof(u_int32_t) * RSZ);
88        clear_refv(RSZ);
89        num_refvec_ = 0;
90
91        // for simulating TCP's 3 dupack rule
92        // (allowing packet re-ordering issue)
93        for (int i = 0; i < DUPACKS; i++)
94                mvec_[i] = 0;
95
96        minrto_ = 0.0;
97        maxrto_ = 100000.0;
98        srtt_ = -1.0;
99        rto_ = 3.0;             // RFC 1122
100        rttvar_ = 0.0;
101        df_ = 0.95;
102        sqrtrtt_ = 1.0;
103        t0_ = 6.0;
104        alpha_ = 0.125;
105        beta_ = 0.25;
106        g_ = 0.01;
107        k_ = 4;
108        ts_ = 0.0;
109        ts_echo_ = 0.0;
110
111        is_tfwc_on_ = false;
112        is_first_loss_seen_ = false;
113        first_lost_pkt_ = -1;
114        num_missing_ = 0;
115
116        avg_interval_ = 0.0;
117        I_tot0_ = 0.0;
118        I_tot1_ = 0.0;
119        tot_weight_ = 0.0;
120}
121
122void TfwcSndr::tfwc_sndr_send(int seqno, double now, double offset) {
123
124        // parse seqno and mark timestamp for this data packet
125        seqno_  = seqno;
126        now_    = now;
127        ts_off_ = offset;
128
129        // timestamp vector for loss history update
130        tsvec_[seqno_%TSZ] = now_;
131
132        //fprintf(stderr, "\t>> now_: %f tsvec_[%d]: %f\n",
133        //      now_, seqno_%TSZ, tsvec_[seqno_%TSZ]);
134
135        // sequence number must be greater than zero
136        //assert (seqno_ > 0);
137        // number of total data packet sent
138        //ndtp_++;
139}
140
141/*
142 * main TFWC reception path
143 */
144void TfwcSndr::tfwc_sndr_recv(u_int16_t type, u_int16_t begin, u_int16_t end,
145                u_int16_t *chunk, double so_rtime)
146{
147        // number of ack received
148        //nakp_++;
149
150        // get start/end seqno that this XR chunk reports
151        begins_ = begin;        // lowest packet seqno
152        ends_ = end;            // highest packet seqno plus one
153
154        // so_timestamp (timestamp for packet reception)
155        so_recv_ = so_rtime;
156
157        // get the number of AckVec chunks
158        //   use seqno space to work out the num chunks
159        //   (add one to num unless exactly divisible by BITLEN
160        //   - so it is large enough to accomodate all the bits
161        num_elm_ = ends_ - begins_;
162        num_vec_ = num_elm_/BITLEN + (num_elm_%BITLEN > 0);
163
164        // retrieve ackvec
165        if (type == XR_BT_1) {
166                // just acked seqno
167                // i.e.,) head seqno(= highest seqno) of this ackvec
168                jacked_ = ends_ - 1;
169
170                // declared AckVec
171                ackv_ = (u_int16_t *) malloc (sizeof(u_int16_t) * num_vec_);
172                // clear the existing AckVec
173                clear_ackv(num_vec_);
174                // clone AckVec from Vic
175                clone_ackv(chunk, num_vec_);
176
177                //fprintf(stderr,
178                //"    [%s +%d] begins: %d ends: %d jacked: %d\n",
179                //              __FILE__, __LINE__, begins_, ends_, jacked_);
180
181                // generate seqno vector
182                gen_seqvec(ackv_, num_vec_);
183
184                // generate margin vector
185                marginvec(jacked_);
186                print_mvec();
187
188                // generate reference vector
189                // (it represents seqvec when there are no losses)
190                //      @begin: aoa_+1 (lowest seqno)
191                //      @end: mvec_[DUPACKS-1] - 1
192                gen_refvec(mvec_[DUPACKS-1]-1, aoa_+1);
193
194                // TFWC is not turned on (i.e., no packet loss yet)
195                if(!is_tfwc_on_) {
196                        if(detect_loss()) {
197                                is_tfwc_on_ = true;
198                                dupack_action();
199                                ts_ = tsvec_[first_lost_pkt_%TSZ];
200                        } else {
201                                // TCP-like AIMD control
202                                cwnd_ += 1;
203                        }
204                }
205                // TFWC is turned on, so control that way
206                else {
207                        control();
208                }
209                fprintf(stderr, "\tnow: %f\tcwnd: %d\n", so_recv_, cwnd_);
210
211                // set ackofack (real number)
212                aoa_ = ackofack();
213
214                // update RTT with the sampled RTT
215                tao_ = so_recv_ - tsvec_[jacked_%TSZ];
216                update_rtt(tao_);
217                fprintf(stderr, "\t<< now_: %f tsvec_[%d]: %f rtt: %f srtt: %f\n",
218                        so_recv_, jacked_%TSZ, tsvec_[jacked_%TSZ], tao_, srtt_);
219
220                // initialize variables for the next pkt reception
221                free(ackv_);
222                init_var();
223        }
224        // retrieve ts echo
225        else if (type == XR_BT_3) {
226                ntep_++;                // number of ts echo packet received
227
228                ts_echo_ = chunk[num_vec_ - 1];
229                fprintf(stderr,
230                "    [%s +%d] ts echo:  %f\n", __FILE__,__LINE__, ts_echo_);
231
232                tao_ = now() - ts_echo_;
233
234                // update RTT
235                //update_rtt(tao_);
236        }
237}
238
239/*
240 * generate seqno vector
241 * (interpret the received AckVec to real sequence numbers)
242 * @ackvec: received AckVec
243 */
244void TfwcSndr::gen_seqvec (u_int16_t *v, int n) {
245        // clear seqvec before starts
246        clear_sqv(num_seqvec_);
247
248        int i, j, k = 0;
249        int x = num_elm_%BITLEN;
250
251        // start of seqvec (lowest seqno)
252        int start = begins_;
253
254        for (i = 0; i < n-1; i++) {
255                for (j = BITLEN; j > 0; j--) {
256                        if( CHECK_BIT_AT(v[i], j) )
257                                seqvec_[k++%SSZ] = start;
258                        else num_missing_++;
259                        start++;
260                }
261        }
262
263        int a = (x == 0) ? BITLEN : x;
264        for (i = a; i > 0; i--) {
265                if( CHECK_BIT_AT(v[n-1], i) )
266                        seqvec_[k++%SSZ] = start;
267                else num_missing_++;
268                start++;
269        }
270
271        // therefore, the number of seqvec elements is:
272        num_seqvec_ = num_elm_ - num_missing_;
273        // printing retrieved sequence numbers from received AckVec
274        print_seqvec(num_seqvec_);
275}
276
277/*
278 * generate reference vector
279 * (it represents the seqno vector when no losses)
280 * @end:    end seqno   (highest)
281 * @begin:  begin seqno (lowest)
282 */
283void TfwcSndr::gen_refvec(int end, int begin) {
284        // clear previous reference vector
285        clear_refv(num_refvec_);
286        // number of reference element - when no loss
287        num_refvec_ = end - begin + 1;
288
289        // generate refvec elements
290        fprintf(stderr, "\tcomparing numbers: (");
291        for (int i = 0; i < num_refvec_; i++) {
292                refvec_[i] = begin + i;
293                fprintf(stderr, " %d", refvec_[i]);
294        } fprintf(stderr, " )\n");
295}
296
297/*
298 * detect packet loss in the received vector
299 * @ret: true when there is a loss
300 */
301bool TfwcSndr::detect_loss() {
302        bool ret;       // 'true' when there is a loss
303        bool is_there = false;
304        int count = 0; // packet loss counter
305
306        // compare refvec and seqvec
307        for (int i = 0; i < num_refvec_; i++) {
308                for (int j = num_seqvec_-1; j >= 0; j--) {
309                        if (refvec_[i] == seqvec_[j]) {
310                                is_there = true;
311                                // we found it, so reset count
312                                count = 0; break;
313                        } else {
314                                is_there = false;
315                                count++;
316                        }
317                } // packet loss should be captured by now
318
319                // record the very first lost packet seqno
320                if(!is_there) {
321                        if(!is_first_loss_seen_)
322                                first_lost_pkt_ = refvec_[i];
323                }
324        }
325        return ret = (count > 0) ? true : false;
326}
327
328/*
329 * update RTT using the sampled RTT value
330 */
331void TfwcSndr::update_rtt(double rtt_sample) {
332
333        // calculate smoothed RTT
334        if (srtt_ < 0) {
335                // the first RTT observation
336                srtt_ = rtt_sample;
337                rttvar_ = rtt_sample/2.0;
338                sqrtrtt_ = sqrt(rtt_sample);
339        } else {
340                srtt_ = df_ * srtt_ + (1 - df_) * rtt_sample;
341                rttvar_ = rttvar_ + beta_ * (fabs(srtt_ - rtt_sample) - rttvar_);
342                sqrtrtt_ = df_ * sqrtrtt_ + (1 - df_) * sqrt(rtt_sample);
343        }
344
345        // update the current RTO
346        if (k_ * rttvar_ > g_)
347                rto_ = srtt_ + k_ * rttvar_;
348        else
349                rto_ = srtt_ + g_;
350
351        // 'rto' could be rounded by 'maxrto'
352        if (rto_ > maxrto_)
353                rto_ = maxrto_;
354}
355
356/*
357 * core part for congestion window control
358 */
359void TfwcSndr::control() {
360        loss_history();
361        avg_loss_interval();
362
363        // loss event rate (p)
364        p_ = 1.0 / avg_interval_;
365
366        // simplified TCP throughput equation
367        double tmp1 = 12.0 * sqrt(p_ * 3.0/8.0);
368        double tmp2 = p_ * (1.0 + 32.0 * pow(p_, 2.0));
369        double term1 = sqrt(p_ * 2.0/3.0);
370        double term2 = tmp1 * tmp2;
371        f_p_ = term1 + term2;
372
373        // TFWC congestion window
374        t_win_ = 1 / f_p_;
375
376        cwnd_ = (int) (t_win_ + .5);
377
378        // cwnd should always be greater than 1
379        if (cwnd_ < 1)
380                cwnd_ = 1;
381}
382
383/*
384 * generate weighting factors
385 */
386void TfwcSndr::gen_weight() {
387#ifdef SHORT_HISTORY
388        // this is just weighted moving average (WMA)
389        for(int i = 0; i <= HSZ; i++){
390                if(i < HSZ/2)
391                        weight_[i] = 1.0;
392                else
393                        weight_[i] = 1.0 - (i-(HSZ/2 - 1.0)) / (HSZ/2 + 1.0);
394        }
395#else
396        // this is exponentially weighted moving average (EWMA)
397        for (int i=0; i <= HSZ; i++) {
398                if (i < HSZ/4)
399                        weight_[i] = 1.0;
400                else
401                        weight_[i] = 2.0 / (i - 1.0);
402        }
403#endif
404}
405
406/*
407 * compute packet loss history
408 */
409void TfwcSndr::pseudo_history() {
410        pseudo_interval_ = 1 / p_;
411
412        /* bzero for all history information */
413        for(int i = 0; i <= HSZ+1; i++)
414                history_[i] = 0;
415
416        /* (let) most recent history information be 0 */
417        history_[0] = 0;
418
419        /* (let) the pseudo interval be the first history information */
420        history_[1] = (int) pseudo_interval_;
421}
422
423/*
424 * dupack action
425 *   o  halve cwnd_
426 *   o  marking pseudo loss history and loss rate
427 */
428void TfwcSndr::dupack_action() {
429        // this is the very first packet loss
430        is_first_loss_seen_ = true;
431
432        // we now have just one meaningful history information
433        hsz_ = 1;
434
435        // halve the current cwnd_
436        cwnd_ = cwnd_ / 2;
437
438        // congestion window never goes below 1
439        if (cwnd_ < 1)
440                cwnd_ = 1;
441
442        // temp cwnd to compute the pseudo values
443        tmp_cwnd_ = cwnd_;
444
445        // creating simulated loss history and loss rate
446        pseudo_p();
447        pseudo_history();
448
449        // generate weight factors
450        gen_weight();
451}
452
453/*
454 * compute simulated loss rate
455 */
456void TfwcSndr::pseudo_p() {
457        for (pseudo_p_ = 0.00001; pseudo_p_ < 1.0; pseudo_p_ += 0.00001) {
458                f_p_ = sqrt((2.0/3.0) * pseudo_p_) + 12.0 * pseudo_p_ *
459                        (1.0 + 32.0 * pow(pseudo_p_, 2.0)) * sqrt((3.0/8.0) * pseudo_p_);
460
461                t_win_ = 1 / f_p_;
462
463                if(t_win_ < tmp_cwnd_)
464                        break;
465        }
466        p_ = pseudo_p_;
467}
468
469/*
470 * compute simulated loss history
471 */
472void TfwcSndr::loss_history() {
473        bool is_loss = false;           // is there a loss found in seqvec?
474        bool is_new_event = false;      // is this a new loss event?
475
476        // compare reference with seqvec
477        for (int i = 0; i < num_refvec_; i++) {
478                // is there a loss found?
479                for (int j = 0; j < num_seqvec_; j++) {
480                        if (refvec_[i] == seqvec_[j]) {
481                                is_loss = false;
482                                break;
483                        } else 
484                                is_loss = true;
485                }
486
487                // is this a new loss event?
488                if (is_loss) {
489                        if (tsvec_[refvec_[i]%TSZ] - ts_ > srtt_)
490                        is_new_event = true;
491                        else
492                        is_new_event = false;
493                }
494
495                // compute loss history (compare refvec and seqvec)
496                // o  everytime it sees a loss
497                //    it will compare the timestamp with smoothed RTT
498                //
499                // o  if the time difference is greater than RTT,
500                //    then this loss starts a new loss event
501                // o  if the time difference is less than RTT,
502                //    then we do nothing
503                //
504                // o  if there is no loss,
505                //    simply increment the loss interval by one
506                if (is_loss && is_new_event) {
507                        // this is a new loss event!
508
509                        // increase current history size
510                        hsz_ = (hsz_ < HSZ) ? ++hsz_ : HSZ;
511
512                        // shift history information
513                        for (int k = HSZ; k > 0; k--)
514                                history_[k] = history_[k-1];
515
516                        // record lost packet's timestamp
517                        ts_ = tsvec_[refvec_[i]%TSZ];
518
519                        // let the most recent history information be one
520                        history_[0] = 1;
521                }
522                else {
523                        // this is not a new loss event
524                        // increase the current history information
525                        history_[0]++;
526                }
527        }
528}
529
530/*
531 * average loss interval
532 */
533void TfwcSndr::avg_loss_interval() {
534
535        I_tot0_ = 0;
536        I_tot1_ = 0;
537        tot_weight_ = 0;
538        int i = 0, j = 0;
539
540        // make a decision whether to include the most recent loss interval
541        //fprintf(stderr, "\n\tHIST_0 [");
542        for (i = 0; i < hsz_; i++) {
543                I_tot0_ += weight_[i] * history_[i];
544                tot_weight_ += weight_[i];
545        //      print_history_item(i);
546        }
547        //fprintf(stderr, "]\n");
548        //fprintf(stderr, "\tHIST_1 [");
549        for (i = 1, j = 0; i < hsz_ + 1; i++, j++) {
550                I_tot1_ += weight_[i-1] * history_[i];
551        //      print_history_item(i, j);
552        }
553        //fprintf(stderr, "]\n");
554
555        // compare I_tot0_ and I_tot1_ and use larger value
556        if (I_tot0_ < I_tot1_)
557                I_tot_ = I_tot1_;
558        else
559                I_tot_ = I_tot0_;
560
561        // this is average loss interval
562        avg_interval_ = I_tot_ / tot_weight_;
563        fprintf(stderr, "\tnow: %f\tALI: %f\n\n", now(), avg_interval_);
564}
565
566/*
567 * print history item
568 */
569void TfwcSndr::print_history_item (int i) {
570        fprintf(stderr, "%d", history_[i]);
571        if (i < hsz_ - 1) fprintf(stderr, ", ");
572}
573
574void TfwcSndr::print_history_item (int i, int j) {
575        fprintf(stderr, "%d", history_[i]);
576        if (j < hsz_ - 1) fprintf(stderr, ", ");
577}
578
579/*
580 * retransmission timer-out
581 */
582void TfwcSndr::expire(int option) {
583        if (option == TFWC_TIMER_RTX)
584                reset_rtx_timer(1);
585        else
586                reset_rtx_timer(0);
587}
588
589/*
590 * reset Rtx Timer
591 */
592void TfwcSndr::reset_rtx_timer (int backoff) {
593        if(backoff)
594                backoff_timer();
595
596        set_rtx_timer();
597}
598
599/*
600 * backoff Rtx Timer
601 */
602void TfwcSndr::backoff_timer() {
603        if (srtt_ < 0) srtt_ = 1.0;
604        rto_ = 2.0 * srtt_;
605
606        if (rto_ > maxrto_)
607                rto_ = maxrto_;
608}
609
610/*
611 * set Rtx Timer
612 */
613void TfwcSndr::set_rtx_timer() {
614        // resched() is basically msched(miliseconds)
615        rtx_timer_ -> resched(rto_ * 1000.);
616}
Note: See TracBrowser for help on using the browser.