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

Revision 4762, 11.9 KB (checked in by soohyunc, 4 years ago)

if packet re-ordering occurred before the first packet loss, then we do not have
any history to revert - i.e., we didn't yet go into ALI routines.

  • 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 RECORD 10000
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
177private:
178        // update RTT
179        void update_rtt(double tao);
180
181        // TCP-like Additive Increase
182        // (until the very first packet loss)
183        void tcp_like_increase();
184
185        // detect packet loss
186        // (to capture the very first lost packet loss)
187        bool detect_loss();
188
189        // TFWC congestion window
190        void cwnd_in_bytes();
191        void cwnd_in_packets(bool revert);
192
193        // calcuate average loss interval
194        void avg_loss_interval();
195        void print_history_item (int);
196        void print_history_item (int, int);
197        bool revert_interval(int reseq);
198        void record_history(int seqno, double interval, double ts);
199
200        // calculate loss history
201        void loss_history();
202
203        // estimate loss history and loss probability
204        double pseudo_p(int cwnd);
205        void pseudo_history(double p);
206
207        // generate weight factors
208        void gen_weight();
209
210        // dupack action
211        void dupack_action(int seqno);
212
213        // new RTO
214        void new_rto(double rtt);
215
216        // determine out-of-ordered ack delivery
217        bool out_of_ack (u_int16_t, u_int32_t*, int);
218
219        // keep packet conservation rule
220        void packet_clocking (pktbuf* pb, bool flag);
221
222        // AckVec clone from Vic
223        inline void clone_ackv(u_int16_t *c, int n) {
224                for (int i = 0; i < n; i++)
225                ackv_[i] = ntohs(c[i]);
226        }
227
228        // copy AckVec to store
229        inline void copy_ackv(int n) {
230                for(int i = 0; i < n; i++)
231                pvec_[i] = ackv_[i];
232        }
233
234        // clear timestamp vector
235        inline void clear_tsv (int n) {
236                for (int i = 0; i < n; i++)
237                tsvec_[i] = 0;
238        }
239
240        // clear seqvec
241        inline void clear_sqv (int n) {
242                for (int i = 0; i < n; i++)
243                seqvec_[i] = 0;
244        }
245
246        // clear ackvec
247        inline void clear_ackv (int n) {
248                for (int i = 0; i < n; i++)
249                ackv_[i] = 0;
250        }
251
252        // clear previous ackvec
253        inline void clear_pvec (int n) {
254                for (int i = 0; i < n; i++)
255                pvec_[i] = 0;
256        }
257
258        // clear refvec
259        inline void clear_refv (int n) {
260                for (int i = 0; i < n; i++)
261                refvec_[i] = 0;
262        }
263
264        // clear record for packet size in bytes
265        inline void clear_record (int n) {
266                for (int i = 0; i < n; i++)
267                record_[i] = 0;
268        }
269
270        // clear seqno that triggered a new loss event
271        inline void clear_prev_interval (int n) {
272                for (int i = 0; i < n; i++)
273                prev_interval_[i] = 0;
274        }
275
276        // clear seqno that triggered a new loss event
277        inline void clear_new_hist_seqno (int n) {
278                for (int i = 0; i < n; i++)
279                new_hist_seqno_[i] = 0;
280                new_hist_seqno_size_ = 0;
281        }
282
283        // number of ackvec chunks
284        inline int get_numvec(int n) {
285        return (n/BITLEN + (n%BITLEN > 0));     
286        }
287
288        // number of ackvec elements
289        inline int get_numelm (int begin, int end) {
290        return (end - begin + 1);
291        }
292
293        // replace jack'ed
294        inline void replace (u_int16_t highest) {
295                jacked_ = highest;
296        }
297
298        // store jack'ed
299        inline void store (u_int16_t highest) {
300                __jacked_ = highest;
301        }
302
303        // find seqno
304        bool find_seqno(u_int16_t *v, int n, int target);
305        bool find_seqno(u_int32_t *v, int n, u_int32_t target);
306
307        // print cwnd for debugging
308        inline void print_cwnd() {
309        fprintf(stderr, "\tnow: %f\tcwnd: %d\n", so_recv_, cwnd_);
310        }
311
312        // print received XR chunk info
313        inline void print_xr_info(const char* str, const int i) {
314        fprintf(stderr,
315        "    [%s +%d] begins: %d ends: %d jacked: %d\n",
316        str, i, begins_, ends_, jacked_);
317        }
318
319        // print RTT related info for debugging
320        inline void print_rtt_info() {
321        fprintf(stderr,
322        "\t>> now_: %f tsvec_[%d]: %f rtt: %f srtt: %f\n",
323        so_recv_, jacked_%TSZ, tsvec_[jacked_%TSZ], tao_, srtt_);
324        }
325        inline void print_rtt_info(const char* str) {
326        fprintf(stderr,
327        "\t%s now_: %f tsvec_[%d]: %f rtt: %f srtt: %f\n",
328        str, so_recv_, jacked_%TSZ, tsvec_[jacked_%TSZ], tao_, srtt_);
329        }
330
331        // print ALI for debugging
332        inline void print_ALI() {
333        fprintf(stderr, "\tnow: %f\tALI: %f\n\n", so_recv_, avg_interval_);
334        }
335
336        // print packet's timestamp record
337        inline void print_packet_tsvec() {
338        fprintf(stderr, "\t>> now: %f tsvec_[%d]: %f\n",
339        now_, seqno_%TSZ, tsvec_[seqno_%TSZ]);
340        }
341
342        // print mvec
343        inline void print_mvec() {
344        fprintf(stderr, "\tmargin numbers: ( %d %d %d )\n",
345        mvec_[0], mvec_[1], mvec_[2]);
346        }
347        // print vec
348        inline void print_vec(const char* str, u_int32_t *vec, int c) {
349        fprintf(stderr, "\t%s: (", str);
350                for (int i = 0; i < c; i++)
351                fprintf(stderr, " %d", vec[i]);
352        fprintf(stderr, " )\n");
353        }
354        inline void print_vec(const char* str, u_int16_t *vec, int c) {
355        fprintf(stderr, "\t%s: (", str);
356                for (int i = 0; i < c; i++)
357                fprintf(stderr, " %d", vec[i]);
358        fprintf(stderr, " )\n");
359        }
360
361        int ndtp_;              // number of data packet sent
362        int nakp_;              // number of ackvec packet received
363        int ntep_;              // number of ts echo packet received
364        int nsve_;              // number of seqvec element
365
366        double ts_off_;         // timestamp offset for gettimeofday
367
368        u_int32_t *seqvec_;             // generated seqno vec
369        int     num_seqvec_;            // number of seqvec elements
370        u_int32_t *refvec_;             // reference seqno vec
371        int num_refvec_;                // number of refvec elements
372        double *tsvec_;                 // timestamp vector
373        u_int16_t jacked_;              // just acked seqno (head of ackvec)
374        bool is_first_loss_seen_;
375        bool is_tfwc_on_;
376        int num_missing_;       // number of missing seqno
377        double f_p_;    // f(p) = sqrt(2/3)*p + 12*p*(1+32*p^2)*sqrt(3/8)*p
378        double p_;              // packet loss probability
379        double t_win_;      // temporal cwin size to get p_ value
380        double avg_interval_;   // average loss interval
381        int history_[HSZ+1];    // loss interval history
382        int prev_history_[HSZ];// previous loss interval history
383        double weight_[HSZ+1];  // weight for calculating avg loss interval
384        double I_tot_;          // total sum
385        double I_tot0_;         // from 0 to n-1
386        double I_tot1_;         // form 1 to n
387        double tot_weight_;     // total weight
388        int hsz_;               // current history size
389        bool to_driven_;        // is TFWC being driven by timer-out?
390
391        // RTT related variables
392        double srtt_;   // smoothed RTT
393        double rttvar_; // RTT variation
394        double rto_;    // retransmission timeout
395        double minrto_; // min RTO allowed
396        double maxrto_; // max RTO
397        double df_;             // decay factor
398        double sqrtrtt_;        // the mean of the sqrt of RTT
399
400        // first lost packet (used only at the very first packet loss)
401        int first_lost_pkt_;
402
403        // XR chunk begin/end
404        u_int16_t begins_;      // start seqno that this XR chunk reports
405        u_int16_t ends_;        // end seqno + 1 that this XR chunk reports
406        int     num_elm_;               // number of ackvec elements
407        int num_vec_;           // numver of ackvec chunks
408
409        // TCP's RTO calculation
410        double alpha_;  // smoothing factor for RTT/RTO calculation
411        double beta_;   // smoothing factor for RTT/RTO calculation
412        double g_;              // timer granularity
413        int k_;                 // k value
414        int t_rtt_;             // RTT
415        int t_rttvar_;  // RTT variance
416        int t_srtt_;    // smoothed RTT
417        int srtt_init_; // initial val for t_srtt_
418        int rttvar_init_;       // initial val for t_rttvar_
419        int rttvar_exp_;        // exponent of multiple for t0_
420        double t0_;             // t0 value at TCP throughput equation
421        double tcp_tick_;
422
423        // packet reordering
424        bool reorder_;
425        // highest/lowest packet sequence numbers (prev ackvec)
426        u_int16_t __jacked_;    // previous highest packet sequence number
427        double *prev_interval_; // previous avgerage intervals
428        u_int16_t *new_hist_seqno_;     // seqno that introduced a new loss event
429        int new_hist_seqno_size_;
430
431        // record of packet size in bytes
432        u_int16_t *record_;
433};
434
435#endif
Note: See TracBrowser for help on using the browser.