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

Revision 4763, 12.0 KB (checked in by soohyunc, 4 years ago)

Subsequent to the Revision 4762... (to prevent from segfault)

had to consider all re-ordering cases (e.g., packet reordering, ack reordering,
depricated ack reception)

i.e., if the above cases occurred before we see the first packet loss, then we
do not have any history to go back. therefore, we increase cwnd to clock a
packet out.

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