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

Revision 4633, 12.9 KB (checked in by soohyunc, 4 years ago)

printing HISTORY method had an item off by one, especially HIST1.

  • 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 - 1, tsvec_[seqno_%TSZ-1]);
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_[ends_%TSZ];
196                update_rtt(tao_);
197
198                // initialize variables for the next pkt reception
199                free(ackv_);
200                init_loss_var();
201        }
202        // retrieve ts echo
203        else if (type == XR_BT_3) {
204                ntep_++;                // number of ts echo packet received
205
206                ts_echo_ = chunk[num_vec_ - 1];
207                fprintf(stderr,
208                "    [%s +%d] ts echo:  %f\n", __FILE__,__LINE__, ts_echo_);
209
210                tao_ = now() - ts_echo_;
211
212                // update RTT
213                //update_rtt(tao_);
214        }
215}
216
217/*
218 * generate seqno vector
219 * (interpret the received AckVec to real sequence numbers)
220 * @ackvec: received AckVec
221 */
222void TfwcSndr::gen_seqvec (u_int16_t *v, int n) {
223        // clear seqvec before starts
224        clear_sqv(num_seqvec_);
225
226        int i, j, k = 0;
227        int x = num_elm_%BITLEN;
228
229        // start of seqvec (lowest seqno)
230        int start = begins_;
231
232        for (i = 0; i < n-1; i++) {
233                for (j = BITLEN; j > 0; j--) {
234                        if( CHECK_BIT_AT(v[i], j) )
235                                seqvec_[k++%SSZ] = start;
236                        else num_loss_++;
237                        start++;
238                }
239        }
240
241        int a = (x == 0) ? BITLEN : x;
242        for (i = a; i > 0; i--) {
243                if( CHECK_BIT_AT(v[n-1], i) )
244                        seqvec_[k++%SSZ] = start;
245                else num_loss_++;
246                start++;
247        }
248
249        // therefore, the number of seqvec elements is:
250        num_seqvec_ = num_elm_ - num_loss_;
251        // printing retrieved sequence numbers from received AckVec
252        print_seqvec(num_seqvec_);
253}
254
255/*
256 * detect packet loss in the received vector
257 * @ret: true when there is a loss
258 */
259bool TfwcSndr::detect_loss(int end, int begin) {
260        bool ret;       // 'true' when there is a loss
261        bool is_there = false;
262        int count = 0; // packet loss counter
263
264        // number of tempvec element when no loss
265        int num = end - begin + 1;
266        u_int32_t tempvec[num];
267
268        // generate tempvec elements
269        fprintf(stderr, "\tcomparing numbers: (");
270        for (int i = 0; i < num; i++) {
271                tempvec[i] = begin + i;
272                fprintf(stderr, " %d", tempvec[i]);
273        } fprintf(stderr, " )\n");
274
275        // compare tempvec and seqvec
276        for (int i = 0; i < num; i++) {
277                for (int j = num_seqvec_-1; j >= 0; j--) {
278                        if (tempvec[i] == seqvec_[j]) {
279                                is_there = true;
280                                // we found it, so reset count
281                                count = 0; break;
282                        } else {
283                                is_there = false;
284                                count++;
285                        }
286                } // packet loss should be captured by now
287
288                // record the very first lost packet seqno
289                if(!is_there) {
290                        if(!is_first_loss_seen_)
291                                first_lost_pkt_ = tempvec[i];
292                }
293        }
294       
295        // store tempvec elements for updating loss history
296        first_elm_ = tempvec[0];
297        last_elm_ = first_elm_ + num;
298
299        return ret = (count > 0) ? true : false;
300}
301
302/*
303 * update RTT using the sampled RTT value
304 */
305void TfwcSndr::update_rtt(double rtt_sample) {
306
307        // calculate smoothed RTT
308        if (srtt_ < 0) {
309                // the first RTT observation
310                srtt_ = rtt_sample;
311                rttvar_ = rtt_sample/2.0;
312                sqrtrtt_ = sqrt(rtt_sample);
313        } else {
314                srtt_ = df_ * srtt_ + (1 - df_) * rtt_sample;
315                rttvar_ = rttvar_ + beta_ * (fabs(srtt_ - rtt_sample) - rttvar_);
316                sqrtrtt_ = df_ * sqrtrtt_ + (1 - df_) * sqrt(rtt_sample);
317        }
318
319        // update the current RTO
320        if (k_ * rttvar_ > g_)
321                rto_ = srtt_ + k_ * rttvar_;
322        else
323                rto_ = srtt_ + g_;
324
325        // 'rto' could be rounded by 'maxrto'
326        if (rto_ > maxrto_)
327                rto_ = maxrto_;
328}
329
330/*
331 * core part for congestion window control
332 */
333void TfwcSndr::control() {
334        loss_history();
335        avg_loss_interval();
336
337        // loss event rate (p)
338        p_ = 1.0 / avg_interval_;
339
340        // simplified TCP throughput equation
341        double tmp1 = 12.0 * sqrt(p_ * 3.0/8.0);
342        double tmp2 = p_ * (1.0 + 32.0 * pow(p_, 2.0));
343        double term1 = sqrt(p_ * 2.0/3.0);
344        double term2 = tmp1 * tmp2;
345        f_p_ = term1 + term2;
346
347        // TFWC congestion window
348        t_win_ = 1 / f_p_;
349
350        cwnd_ = (int) (t_win_ + .5);
351
352        // cwnd should always be greater than 1
353        if (cwnd_ < 1)
354                cwnd_ = 1;
355}
356
357/*
358 * generate weighting factors
359 */
360void TfwcSndr::gen_weight() {
361#ifdef SHORT_HISTORY
362        // this is just weighted moving average (WMA)
363        for(int i = 0; i <= HSZ; i++){
364                if(i < HSZ/2)
365                        weight_[i] = 1.0;
366                else
367                        weight_[i] = 1.0 - (i-(HSZ/2 - 1.0)) / (HSZ/2 + 1.0);
368        }
369#else
370        // this is exponentially weighted moving average (EWMA)
371        for (int i=0; i <= HSZ; i++) {
372                if (i < HSZ/4)
373                        weight_[i] = 1.0;
374                else
375                        weight_[i] = 2.0 / (i - 1.0);
376        }
377#endif
378}
379
380/*
381 * compute packet loss history
382 */
383void TfwcSndr::pseudo_history() {
384        pseudo_interval_ = 1 / p_;
385
386        /* bzero for all history information */
387        for(int i = 0; i <= HSZ+1; i++)
388                history_[i] = 0;
389
390        /* (let) most recent history information be 0 */
391        history_[0] = 0;
392
393        /* (let) the pseudo interval be the first history information */
394        history_[1] = (int) pseudo_interval_;
395}
396
397/*
398 * dupack action
399 *   o  halve cwnd_
400 *   o  marking pseudo loss history and loss rate
401 */
402void TfwcSndr::dupack_action() {
403        // this is the very first packet loss
404        is_first_loss_seen_ = true;
405
406        // we now have just one meaningful history information
407        hsz_ = 1;
408
409        // halve the current cwnd_
410        cwnd_ = cwnd_ / 2;
411
412        // congestion window never goes below 1
413        if (cwnd_ < 1)
414                cwnd_ = 1;
415
416        // temp cwnd to compute the pseudo values
417        tmp_cwnd_ = cwnd_;
418
419        // creating simulated loss history and loss rate
420        pseudo_p();
421        pseudo_history();
422
423        // generate weight factors
424        gen_weight();
425}
426
427/*
428 * compute simulated loss rate
429 */
430void TfwcSndr::pseudo_p() {
431        for (pseudo_p_ = 0.00001; pseudo_p_ < 1.0; pseudo_p_ += 0.00001) {
432                f_p_ = sqrt((2.0/3.0) * pseudo_p_) + 12.0 * pseudo_p_ *
433                        (1.0 + 32.0 * pow(pseudo_p_, 2.0)) * sqrt((3.0/8.0) * pseudo_p_);
434
435                t_win_ = 1 / f_p_;
436
437                if(t_win_ < tmp_cwnd_)
438                        break;
439        }
440        p_ = pseudo_p_;
441}
442
443/*
444 * compute simulated loss history
445 */
446void TfwcSndr::loss_history() {
447        bool is_loss;           // is there a loss found in seqvec?
448        bool is_new_event;      // is this a new loss event?
449        int numvec = last_elm_ - first_elm_ + 1;
450        u_int32_t tempvec[numvec];
451
452        for (int i = 0; i < numvec; i++)
453                tempvec[i] = first_elm_ + i;
454
455        // compare tempvec[] with seqvec
456        for (int i = 0; i < numvec; i++) {
457                // is there a loss found?
458                for (int j = 0; j < numvec; j++) {
459                        if (tempvec[i] == seqvec_[j]) {
460                                is_loss = false;
461                                break;
462                        } else 
463                                is_loss = true;
464                }
465
466                // is this a new loss event?
467                if (tsvec_[tempvec[i]%TSZ] - ts_ > srtt_)
468                        is_new_event = true;
469                else
470                        is_new_event = false;
471
472                // compute loss history (compare tempvec and seqvec)
473                // o  everytime it sees a loss
474                //    it will compare the timestamp with smoothed RTT
475                //
476                // o  if the time difference is greater than RTT,
477                //    then this loss starts a new loss event
478                // o  if the time difference is less than RTT,
479                //    then we do nothing
480                //
481                // o  if there is no loss,
482                //    simply increment the loss interval by one
483                if (is_loss && is_new_event) {
484                        // this is a new loss event!
485
486                        // increase current history size
487                        hsz_ = (hsz_ < HSZ) ? ++hsz_ : HSZ;
488
489                        // shift history information
490                        for (int k = HSZ; k > 0; k--)
491                                history_[k] = history_[k-1];
492
493                        // record lost packet's timestamp
494                        ts_ = tsvec_[tempvec[i]%TSZ];
495
496                        // let the most recent history information be one
497                        history_[0] = 1;
498                }
499                else {
500                        // this is not a new loss event
501                        // increase the current history information
502                        history_[0]++;
503                }
504        }
505}
506
507/*
508 * average loss interval
509 */
510void TfwcSndr::avg_loss_interval() {
511
512        I_tot0_ = 0;
513        I_tot1_ = 0;
514        tot_weight_ = 0;
515        int i = 0, j = 0;
516
517        // make a decision whether to include the most recent loss interval
518        fprintf(stderr, "\n\tHIST_0 [");
519        for (i = 0; i < hsz_; i++) {
520                I_tot0_ += weight_[i] * history_[i];
521                tot_weight_ += weight_[i];
522                print_history_item(i);
523        }
524        fprintf(stderr, "]\n");
525        fprintf(stderr, "\tHIST_1 [");
526        for (i = 1, j = 0; i < hsz_ + 1; i++, j++) {
527                I_tot1_ += weight_[i-1] * history_[i];
528                //tot_weight_ += weight_[i];
529                print_history_item(i, j);
530        }
531        fprintf(stderr, "]\n");
532
533        // compare I_tot0_ and I_tot1_ and use larger value
534        if (I_tot0_ < I_tot1_)
535                I_tot_ = I_tot1_;
536        else
537                I_tot_ = I_tot0_;
538
539        // this is average loss interval
540        avg_interval_ = I_tot_ / tot_weight_;
541        fprintf(stderr, "\tnow: %f\tALI: %f\n\n", now(), avg_interval_);
542}
543
544/*
545 * print history item
546 */
547void TfwcSndr::print_history_item (int i) {
548        fprintf(stderr, "%d", history_[i]);
549        if (i < hsz_ - 1) fprintf(stderr, ", ");
550}
551
552void TfwcSndr::print_history_item (int i, int j) {
553        fprintf(stderr, "%d", history_[i]);
554        if (j < hsz_ - 1) fprintf(stderr, ", ");
555}
Note: See TracBrowser for help on using the browser.