root/vic/branches/cc/cc/tfwc_sndr.h @ 4783

Revision 4783, 12.3 KB (checked in by soohyunc, 4 years ago)

calculated packet size using EWMA scheme

  • 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#ifndef vic_tfwc_sndr_h
35#define vic_tfwc_sndr_h
36
37#include "bitmap.h"     // bitmap operations
38#include "cc_timer.h"
39
40#define DUPACKS 3   // simulating TCP's 3 dupacks
41#define TSZ     1000    // tsvec_ size
42#define SSZ 1000        // seqvec_ size
43#define RSZ 1000        // refvec_ size
44#define PSR 10000       // packet size record
45
46#define SHORT_HISTORY           // history size = 8
47#ifdef  SHORT_HISTORY
48#define HSZ 8   // history size for avg loss history
49#else
50#define HSZ 16  // history size for avg loss history
51#endif
52
53#define T_RTTVAR_BITS   2
54#define T_SRTT_BITS             3
55
56#define BITLEN  16
57
58// timer related
59#define TFWC_TIMER_RTX          0
60#define TFWC_TIMER_RESET        1
61
62class TfwcSndr;
63class Transmitter;
64
65// re-transmission timer
66class TfwcRtxTimer : public CcTimerHandler {
67public:
68        TfwcRtxTimer(TfwcSndr *s) : CcTimerHandler() { s_ = s;}
69        virtual void timeout();
70
71protected:
72        TfwcSndr *s_;
73};
74
75// TFWC sender class
76class TfwcSndr {
77public:
78        // constructor
79        TfwcSndr();
80        virtual ~TfwcSndr() {};
81
82        // virtual functions
83        virtual void cc_tfwc_output(bool recv_by_ch=0) = 0;
84        virtual void cc_tfwc_output(pktbuf*) = 0;
85        virtual void cc_tfwc_trigger(pktbuf* pb=0) = 0;
86        virtual double tx_ts_offset() = 0;
87        virtual int tx_buf_size() = 0;
88
89        // parse seqno and timestamp
90        void tfwc_sndr_send(pktbuf*, double);
91
92        // main reception path (XR packet)
93        void tfwc_sndr_recv(u_int16_t type, u_int16_t begin, u_int16_t end,
94        u_int16_t *chunk, double so_rtime, bool recv_by_ch, pktbuf* pb);
95
96        // return ackofack
97        inline u_int16_t tfwc_sndr_get_aoa() { return aoa_; }
98
99        // return just acked seqno
100        inline u_int16_t tfwc_sndr_jacked() { return jacked_; }
101
102        // return tfwc controlled cwnd value
103        inline u_int32_t tfwc_magic() { return cwnd_; };
104
105        // set timestamp in double type (TfwcSndr)
106        inline double tfwc_sndr_now() {
107                timeval tv;
108                ::gettimeofday(&tv, NULL);
109                return ((double) tv.tv_sec + 1e-6 * (double) tv.tv_usec);
110        }
111
112        // return the current time
113        inline double now() { return (tfwc_sndr_now()-ts_off_); }
114
115        // variables
116        u_int16_t seqno_;       // packet sequence number
117        u_int32_t cwnd_;        // congestion window
118
119        // Rtx timer
120        void expire(int option);
121
122protected:
123        // generate sequence numbers
124        void gen_seqvec(u_int16_t *v, int n);
125
126        // generate reference seqno
127        void gen_refvec(int end, int begin);
128
129        // reset variables
130        void reset_var(bool reverted);
131
132        // get the first position in ackvec where 1 is marked
133        inline u_int16_t get_head_pos(u_int16_t ackvec) {
134                int l;
135                for (l = 0; l < BITLEN; l++) {
136                if(GET_HEAD_VEC(ackvec, l)) break;
137                }
138                return (BITLEN - l);
139        }
140        // get the last position in ackvec where 1 is marked
141        inline u_int16_t get_tail_pos(u_int16_t ackvec) {
142                int l;
143                for (l = 0; l < BITLEN; l++) {
144                if(GET_TAIL_VEC(ackvec, l)) break;
145                }
146                return (l + 1);
147        }
148        // generate margin vector
149        inline void marginvec(u_int16_t hseq) {
150        for (int i = 0; i < DUPACKS; i++)
151                // round up if it is less than zero
152                mvec_[i] = ((hseq - i) < 0) ? 0 : (hseq - i);
153        }
154        // ackofack
155        inline u_int16_t ackofack () {
156        return ((mvec_[DUPACKS - 1] - 1) <= 0) ?
157                0 : (u_int16_t) (mvec_[DUPACKS - 1] - 1);
158        }
159
160        // retransmission timer
161        TfwcRtxTimer rtx_timer_;
162        void set_rtx_timer();
163        void reset_rtx_timer(int backoff);
164        void backoff_timer();
165
166        int mvec_[DUPACKS]; // margin vec (simulatinmg TCP 3 dupacks)
167        u_int16_t *ackv_;       // received AckVec (from TfwcRcvr)
168        u_int16_t *pvec_;       // previous (stored) AckVec
169        u_int16_t aoa_;         // ack of ack
170        double ts_;                     // time stamp (double type)
171        double ts_echo_;        // time stamp echo (double type)
172        double now_;            // real-time now
173        double so_recv_;        // SO_TIMESTAMP (XR packet reception)
174        double tao_;            // sampled RTT
175        double prev_ts_;
176
177        // packet size
178        int psize_;
179        double lambda_;
180
181private:
182        // update RTT
183        void update_rtt(double tao);
184
185        // TCP-like Additive Increase
186        // (until the very first packet loss)
187        void tcp_like_increase();
188
189        // detect packet loss
190        // (to capture the very first lost packet loss)
191        bool detect_loss();
192
193        // TFWC congestion window in packets
194        void window_in_packets(bool revert);
195        void cwnd_in_packets(bool revert);
196        // TFWC congestion window in bytes
197        void window_in_bytes(bool revert);
198        void cwnd_in_bytes(bool revert);
199
200        // calcuate average loss interval
201        void avg_loss_interval();
202        void print_history_item (int);
203        void print_history_item (int, int);
204        bool revert_interval(int reseq);
205        void record_history(int seqno, double interval, double ts);
206
207        // calculate loss history
208        void loss_history();
209
210        // estimate loss history and loss probability
211        double pseudo_p(int cwnd);
212        void pseudo_history(double p);
213
214        // generate weight factors
215        void gen_weight();
216
217        // dupack action
218        void dupack_action(int seqno);
219
220        // new RTO
221        void new_rto(double rtt);
222
223        // determine out-of-ordered ack delivery
224        bool out_of_ack (u_int16_t, u_int32_t*, int);
225
226        // keep packet conservation rule
227        void packet_clocking (pktbuf* pb, bool flag);
228
229        // AckVec clone from Vic
230        inline void clone_ackv(u_int16_t *c, int n) {
231                for (int i = 0; i < n; i++)
232                ackv_[i] = ntohs(c[i]);
233        }
234
235        // copy AckVec to store
236        inline void copy_ackv(int n) {
237                for(int i = 0; i < n; i++)
238                pvec_[i] = ackv_[i];
239        }
240
241        // clear timestamp vector
242        inline void clear_tsv (int n) {
243                for (int i = 0; i < n; i++)
244                tsvec_[i] = 0;
245        }
246
247        // clear seqvec
248        inline void clear_sqv (int n) {
249                for (int i = 0; i < n; i++)
250                seqvec_[i] = 0;
251        }
252
253        // clear ackvec
254        inline void clear_ackv (int n) {
255                for (int i = 0; i < n; i++)
256                ackv_[i] = 0;
257        }
258
259        // clear previous ackvec
260        inline void clear_pvec (int n) {
261                for (int i = 0; i < n; i++)
262                pvec_[i] = 0;
263        }
264
265        // clear refvec
266        inline void clear_refv (int n) {
267                for (int i = 0; i < n; i++)
268                refvec_[i] = 0;
269        }
270
271        // clear record for packet size in bytes
272        inline void clear_record (int n) {
273                for (int i = 0; i < n; i++)
274                record_[i] = 0;
275        }
276
277        // clear seqno that triggered a new loss event
278        inline void clear_prev_interval (int n) {
279                for (int i = 0; i < n; i++)
280                prev_interval_[i] = 0;
281        }
282
283        // clear seqno that triggered a new loss event
284        inline void clear_new_hist_seqno (int n) {
285                for (int i = 0; i < n; i++)
286                new_hist_seqno_[i] = 0;
287                new_hist_seqno_size_ = 0;
288        }
289
290        // number of ackvec chunks
291        inline int get_numvec(int n) {
292        return (n/BITLEN + (n%BITLEN > 0));     
293        }
294
295        // number of ackvec elements
296        inline int get_numelm (int begin, int end) {
297        return (end - begin + 1);
298        }
299
300        // replace jack'ed
301        inline void replace (u_int16_t highest) {
302                jacked_ = highest;
303        }
304
305        // store jack'ed
306        inline void store (u_int16_t highest) {
307                __jacked_ = highest;
308        }
309
310        // find seqno
311        bool find_seqno(u_int16_t *v, int n, int target);
312        bool find_seqno(u_int32_t *v, int n, u_int32_t target);
313
314        // print cwnd for debugging
315        inline void print_cwnd() {
316        fprintf(stderr, "\tnow: %f\tcwnd: %d\n", so_recv_, cwnd_);
317        }
318
319        // print received XR chunk info
320        inline void print_xr_info(const char* str, const int i) {
321        fprintf(stderr,
322        "    [%s +%d] begins: %d ends: %d jacked: %d\n",
323        str, i, begins_, ends_, jacked_);
324        }
325
326        // print RTT related info for debugging
327        inline void print_rtt_info() {
328        fprintf(stderr,
329        "\t>> now_: %f tsvec_[%d]: %f rtt: %f srtt: %f\n",
330        so_recv_, jacked_%TSZ, tsvec_[jacked_%TSZ], tao_, srtt_);
331        }
332        inline void print_rtt_info(const char* str) {
333        fprintf(stderr,
334        "\t%s now_: %f tsvec_[%d]: %f rtt: %f srtt: %f\n",
335        str, so_recv_, jacked_%TSZ, tsvec_[jacked_%TSZ], tao_, srtt_);
336        }
337
338        // print ALI for debugging
339        inline void print_ALI() {
340        fprintf(stderr, "\tnow: %f\tALI: %f\n\n", so_recv_, avg_interval_);
341        }
342
343        // print packet's timestamp record
344        inline void print_packet_tsvec() {
345        fprintf(stderr, "\t>> now: %f tsvec_[%d]: %f\n",
346        now_, seqno_%TSZ, tsvec_[seqno_%TSZ]);
347        }
348
349        // print mvec
350        inline void print_mvec() {
351        fprintf(stderr, "\tmargin numbers: ( %d %d %d )\n",
352        mvec_[0], mvec_[1], mvec_[2]);
353        }
354        // print vec
355        inline void print_vec(const char* str, u_int32_t *vec, int c) {
356        fprintf(stderr, "\t%s: (", str);
357                for (int i = 0; i < c; i++)
358                fprintf(stderr, " %d", vec[i]);
359        fprintf(stderr, " )\n");
360        }
361        inline void print_vec(const char* str, u_int16_t *vec, int c) {
362        fprintf(stderr, "\t%s: (", str);
363                for (int i = 0; i < c; i++)
364                fprintf(stderr, " %d", vec[i]);
365        fprintf(stderr, " )\n");
366        }
367
368        // print packet size
369        inline void print_psize(double now, int size) {
370        fprintf(stderr, "\tnow: %f psize: %d\n", now, size);
371        }
372
373        int ndtp_;              // number of data packet sent
374        int nakp_;              // number of ackvec packet received
375        int ntep_;              // number of ts echo packet received
376        int nsve_;              // number of seqvec element
377
378        double ts_off_;         // timestamp offset for gettimeofday
379
380        u_int32_t *seqvec_;             // generated seqno vec
381        int     num_seqvec_;            // number of seqvec elements
382        u_int32_t *refvec_;             // reference seqno vec
383        int num_refvec_;                // number of refvec elements
384        double *tsvec_;                 // timestamp vector
385        u_int16_t jacked_;              // just acked seqno (head of ackvec)
386        bool is_first_loss_seen_;
387        bool is_tfwc_on_;
388        int num_missing_;       // number of missing seqno
389        double f_p_;    // f(p) = sqrt(2/3)*p + 12*p*(1+32*p^2)*sqrt(3/8)*p
390        double p_;              // packet loss probability
391        double t_win_;      // temporal cwin size to get p_ value
392        double avg_interval_;   // average loss interval
393        int history_[HSZ+1];    // loss interval history
394        int prev_history_[HSZ];// previous loss interval history
395        double weight_[HSZ+1];  // weight for calculating avg loss interval
396        double I_tot_;          // total sum
397        double I_tot0_;         // from 0 to n-1
398        double I_tot1_;         // form 1 to n
399        double tot_weight_;     // total weight
400        int hsz_;               // current history size
401        bool to_driven_;        // is TFWC being driven by timer-out?
402
403        // RTT related variables
404        double srtt_;   // smoothed RTT
405        double rttvar_; // RTT variation
406        double rto_;    // retransmission timeout
407        double minrto_; // min RTO allowed
408        double maxrto_; // max RTO
409        double df_;             // decay factor
410        double sqrtrtt_;        // the mean of the sqrt of RTT
411
412        // first lost packet (used only at the very first packet loss)
413        int first_lost_pkt_;
414
415        // XR chunk begin/end
416        u_int16_t begins_;      // start seqno that this XR chunk reports
417        u_int16_t ends_;        // end seqno + 1 that this XR chunk reports
418        int     num_elm_;               // number of ackvec elements
419        int num_vec_;           // numver of ackvec chunks
420
421        // TCP's RTO calculation
422        double alpha_;  // smoothing factor for RTT/RTO calculation
423        double beta_;   // smoothing factor for RTT/RTO calculation
424        double g_;              // timer granularity
425        int k_;                 // k value
426        int t_rtt_;             // RTT
427        int t_rttvar_;  // RTT variance
428        int t_srtt_;    // smoothed RTT
429        int srtt_init_; // initial val for t_srtt_
430        int rttvar_init_;       // initial val for t_rttvar_
431        int rttvar_exp_;        // exponent of multiple for t0_
432        double t0_;             // t0 value at TCP throughput equation
433        double tcp_tick_;
434
435        // packet reordering
436        bool reorder_;
437        // highest/lowest packet sequence numbers (prev ackvec)
438        u_int16_t __jacked_;    // previous highest packet sequence number
439        double *prev_interval_; // previous avgerage intervals
440        u_int16_t *new_hist_seqno_;     // seqno that introduced a new loss event
441        int new_hist_seqno_size_;
442
443        // record of packet size in bytes
444        u_int16_t *record_;
445};
446
447#endif
Note: See TracBrowser for help on using the browser.