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

Revision 4640, 13.1 KB (checked in by soohyunc, 4 years ago)

shut off printing HISTORY items

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