tfrc-sink.cc
上传用户:rrhhcc
上传日期:2015-12-11
资源大小:54129k
文件大小:30k
源码类别:

通讯编程

开发平台:

Visual C++

  1. /*
  2.  * Copyright (c) 1999  International Computer Science Institute
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice, this list of conditions and the following disclaimer in the
  12.  *    documentation and/or other materials provided with the distribution.
  13.  * 3. All advertising materials mentioning features or use of this software
  14.  *    must display the following acknowledgement:
  15.  * This product includes software developed by ACIRI, the AT&T 
  16.  *      Center for Internet Research at ICSI (the International Computer
  17.  *      Science Institute).
  18.  * 4. Neither the name of ACIRI nor of ICSI may be used
  19.  *    to endorse or promote products derived from this software without
  20.  *    specific prior written permission.
  21.  *
  22.  * THIS SOFTWARE IS PROVIDED BY ICSI AND CONTRIBUTORS ``AS IS'' AND
  23.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25.  * ARE DISCLAIMED.  IN NO EVENT SHALL ICSI OR CONTRIBUTORS BE LIABLE
  26.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32.  * SUCH DAMAGE.
  33.  */
  34. #include <stdio.h>
  35. #include <stdlib.h>
  36. #include <sys/types.h>
  37. #include <math.h>
  38.  
  39. #include "tfrc-sink.h"
  40. #include "formula-with-inverse.h"
  41. #include "flags.h"
  42. static class TfrcSinkClass : public TclClass {
  43. public:
  44.    TfrcSinkClass() : TclClass("Agent/TFRCSink") {}
  45.    TclObject* create(int, const char*const*) {
  46.       return (new TfrcSinkAgent());
  47.    }
  48. } class_tfrcSink; 
  49. TfrcSinkAgent::TfrcSinkAgent() : Agent(PT_TFRC_ACK), nack_timer_(this)
  50. {
  51. bind("packetSize_", &size_);
  52. bind("InitHistorySize_", &hsz);
  53. bind("NumFeedback_", &NumFeedback_);
  54. bind ("AdjustHistoryAfterSS_", &adjust_history_after_ss);
  55. bind ("printLoss_", &printLoss_);
  56. bind ("algo_", &algo); // algo for loss estimation
  57. bind ("PreciseLoss_", &PreciseLoss_);
  58. bind ("numPkts_", &numPkts_);
  59. bind("minDiscountRatio_", &minDiscountRatio_);
  60. // for WALI ONLY
  61. bind ("NumSamples_", &numsamples);
  62. bind ("discount_", &discount);
  63. bind ("smooth_", &smooth_);
  64. bind ("ShortIntervals_", &ShortIntervals_);
  65. bind ("ShortRtts_", &ShortRtts_);
  66. // EWMA use only
  67. bind ("history_", &history); // EWMA history
  68. // for RBPH use only
  69. bind("minlc_", &minlc); 
  70. bind("bytes_", &bytes_);
  71. rtt_ =  0; 
  72. tzero_ = 0;
  73. last_timestamp_ = 0;
  74. last_arrival_ = 0;
  75. last_report_sent=0;
  76. total_received_ = 0;
  77. total_losses_ = 0;
  78. total_dropped_ = 0;
  79. maxseq = -1;
  80. maxseqList = -1;
  81. rcvd_since_last_report  = 0;
  82. losses_since_last_report = 0;
  83. loss_seen_yet = 0;
  84. lastloss = 0;
  85. lastloss_round_id = -1 ;
  86. numPktsSoFar_ = 0;
  87. rtvec_ = NULL;
  88. tsvec_ = NULL;
  89. lossvec_ = NULL;
  90. // used by WALI and EWMA
  91. last_sample = 0;
  92. // used only for WALI 
  93. false_sample = 0;
  94. sample = NULL ; 
  95. weights = NULL ;
  96. mult = NULL ;
  97.         losses = NULL ;
  98. count_losses = NULL ;
  99.         num_rtts = NULL ;
  100. sample_count = 1 ;
  101. mult_factor_ = 1.0;
  102. init_WALI_flag = 0;
  103. // used only for EWMA
  104. avg_loss_int = -1 ;
  105. loss_int = 0 ;
  106. // used only bu RBPH
  107. sendrate = 0 ; // current send rate
  108. }
  109. /*
  110.  * This is a new loss event if it is at least an RTT after the beginning
  111.  *   of the last one.
  112.  * If PreciseLoss_ is set, the new_loss also checks that there is a
  113.  *     new round_id.
  114.  * The sender updates the round_id when it receives a new report from
  115.  *   the receiver, and when it reduces its rate after no feedback.
  116.  * Sometimes the rtt estimates can be less than the actual RTT, and
  117.  *   the round_id will catch this.  This can be useful if the actual
  118.  *   RTT increases dramatically.
  119.  */
  120. int TfrcSinkAgent::new_loss(int i, double tstamp)
  121. {
  122. double time_since_last_loss_interval = tsvec_[i%hsz]-lastloss;
  123. if ((time_since_last_loss_interval > rtt_)
  124.      && (PreciseLoss_ == 0 || (round_id > lastloss_round_id))) {
  125. lastloss = tstamp;
  126. lastloss_round_id = round_id ;
  127.                 if (time_since_last_loss_interval < ShortRtts_ * rtt_ &&
  128. algo == WALI) {
  129.                         count_losses[0] = 1;
  130.                 }
  131.                 if (rtt_ > 0 && algo == WALI) {
  132.                         num_rtts[0] = (int) ceil(time_since_last_loss_interval / rtt_);
  133.                         if (num_rtts[0] < 1) num_rtts[0] = 1;
  134.                 }
  135. return TRUE;
  136. } else return FALSE;
  137. }
  138. double TfrcSinkAgent::estimate_tstamp(int before, int after, int i)
  139. {
  140. double delta = (tsvec_[after%hsz]-tsvec_[before%hsz])/(after-before) ; 
  141. double tstamp = tsvec_[before%hsz]+(i-before)*delta ;
  142. return tstamp;
  143. }
  144. /*
  145.  * Receive new data packet.  If appropriate, generate a new report.
  146.  */
  147. void TfrcSinkAgent::recv(Packet *pkt, Handler *)
  148. {
  149. hdr_tfrc *tfrch = hdr_tfrc::access(pkt); 
  150. hdr_flags* hf = hdr_flags::access(pkt);
  151. double now = Scheduler::instance().clock();
  152. double p = -1;
  153. int ecnEvent = 0;
  154. int congestionEvent = 0;
  155. int UrgentFlag = 0; // send loss report immediately
  156. int newdata = 0; // a new data packet received
  157. if (algo == WALI && !init_WALI_flag) {
  158. init_WALI () ;
  159. }
  160. rcvd_since_last_report ++;
  161. total_received_ ++;
  162. // bytes_ was added by Tom Phelan, for reporting bytes received.
  163. bytes_ += hdr_cmn::access(pkt)->size();
  164. if (maxseq < 0) {
  165. // This is the first data packet.
  166. newdata = 1;
  167. maxseq = tfrch->seqno - 1 ;
  168. maxseqList = tfrch->seqno;
  169. rtvec_=(double *)malloc(sizeof(double)*hsz);
  170. tsvec_=(double *)malloc(sizeof(double)*hsz);
  171. lossvec_=(char *)malloc(sizeof(double)*hsz);
  172. if (rtvec_ && lossvec_) {
  173. int i;
  174. for (i = 0; i < hsz ; i ++) {
  175. lossvec_[i] = UNKNOWN;
  176. rtvec_[i] = -1; 
  177. tsvec_[i] = -1; 
  178. }
  179. }
  180. else {
  181. printf ("error allocating memory for packet buffersn");
  182. abort (); 
  183. }
  184. }
  185. /* for the time being, we will ignore out of order and duplicate 
  186.    packets etc. */
  187. int seqno = tfrch->seqno ;
  188. fsize_ = tfrch->fsize;
  189. int oldmaxseq = maxseq;
  190. // if this is the highest packet yet, or an unknown packet
  191. //   between maxseqList and maxseq  
  192. if ((seqno > maxseq) || 
  193.   (seqno > maxseqList && lossvec_[seqno%hsz] == UNKNOWN )) {
  194. if (seqno > maxseqList + 1)
  195. ++ numPktsSoFar_;
  196. UrgentFlag = tfrch->UrgentFlag;
  197. round_id = tfrch->round_id ;
  198. rtt_=tfrch->rtt;
  199. tzero_=tfrch->tzero;
  200. psize_=tfrch->psize;
  201. sendrate = tfrch->rate;
  202. last_arrival_=now;
  203. last_timestamp_=tfrch->timestamp;
  204. rtvec_[seqno%hsz]=now;
  205. tsvec_[seqno%hsz]=last_timestamp_;
  206. if (hf->ect() == 1 && hf->ce() == 1) {
  207. // ECN action
  208. lossvec_[seqno%hsz] = ECN_RCVD;
  209. ++ total_losses_;
  210. losses_since_last_report++;
  211. if (new_loss(seqno, tsvec_[seqno%hsz])) {
  212. ecnEvent = 1;
  213. lossvec_[seqno%hsz] = ECNLOST;
  214. if (algo == WALI) {
  215.                         ++ losses[0];
  216. }
  217. } else lossvec_[seqno%hsz] = RCVD;
  218. }
  219. if (seqno > maxseq) {
  220. int i = maxseq + 1;
  221. while (i < seqno) {
  222. // Added 3/1/05 in case we have wrapped around
  223. //   in packet sequence space.
  224. lossvec_[i%hsz] = UNKNOWN;
  225. ++ i;
  226. ++ total_losses_;
  227. ++ total_dropped_;
  228. }
  229. }
  230. if (seqno > maxseqList && 
  231.   (ecnEvent || numPktsSoFar_ >= numPkts_ ||
  232.      tsvec_[seqno%hsz] - tsvec_[maxseqList%hsz] > rtt_)) {
  233. // numPktsSoFar_ >= numPkts_:
  234. // Number of pkts since we last entered this procedure
  235. //   at least equal numPkts_, the number of non-sequential 
  236. //   packets that must be seen before inferring loss.
  237. // maxseqList: max seq number checked for dropped packets
  238. // Decide which losses begin new loss events.
  239. int i = maxseqList ;
  240. while(i < seqno) {
  241. if (lossvec_[i%hsz] == UNKNOWN) {
  242. rtvec_[i%hsz]=now;
  243. tsvec_[i%hsz]=estimate_tstamp(oldmaxseq, seqno, i);
  244. if (new_loss(i, tsvec_[i%hsz])) {
  245. congestionEvent = 1;
  246. lossvec_[i%hsz] = LOST;
  247. } else {
  248. // This lost packet is marked "NOT_RCVD"
  249. // as it does not begin a loss event.
  250. lossvec_[i%hsz] = NOT_RCVD; 
  251. }
  252. if (algo == WALI) {
  253.      ++ losses[0];
  254. }
  255. losses_since_last_report++;
  256. }
  257. i++;
  258. }
  259. maxseqList = seqno;
  260. numPktsSoFar_ = 0;
  261. } else if (seqno == maxseqList + 1) {
  262. maxseqList = seqno;
  263. numPktsSoFar_ = 0;
  264. if (seqno > maxseq) {
  265. maxseq = tfrch->seqno ;
  266. // if we are in slow start (i.e. (loss_seen_yet ==0)), 
  267. // and if we saw a loss, report it immediately
  268. if ((algo == WALI) && (loss_seen_yet ==0) && 
  269.   (tfrch->seqno - oldmaxseq > 1 || ecnEvent )) {
  270. UrgentFlag = 1 ; 
  271. loss_seen_yet = 1;
  272. if (adjust_history_after_ss) {
  273. p = adjust_history(tfrch->timestamp);
  274. }
  275. }
  276. if ((rtt_ > SMALLFLOAT) && 
  277. (now - last_report_sent >= rtt_/NumFeedback_)) {
  278. UrgentFlag = 1 ;
  279. }
  280. }
  281. if (UrgentFlag || ecnEvent || congestionEvent) {
  282. nextpkt(p);
  283. }
  284. Packet::free(pkt);
  285. }
  286. double TfrcSinkAgent::est_loss () 
  287. {
  288. double p = 0 ;
  289. switch (algo) {
  290. case WALI:
  291. p = est_loss_WALI () ;
  292. break;
  293. case EWMA:
  294. p = est_loss_EWMA () ;
  295. break;
  296. case RBPH:
  297. p = est_loss_RBPH () ;
  298. break;
  299. case EBPH:
  300. p = est_loss_EBPH () ;
  301. break;
  302. default:
  303. printf ("invalid algo specifiedn");
  304. abort();
  305. break ; 
  306. }
  307. return p;
  308. }
  309. /*
  310.  * compute estimated throughput in packets per RTT for report.
  311.  */
  312. double TfrcSinkAgent::est_thput () 
  313. {
  314. double time_for_rcv_rate;
  315. double now = Scheduler::instance().clock();
  316. double thput = 1 ;
  317. if ((rtt_ > 0) && ((now - last_report_sent) >= rtt_)) {
  318. // more than an RTT since the last report
  319. time_for_rcv_rate = (now - last_report_sent);
  320. if (rcvd_since_last_report > 0) {
  321. thput = rcvd_since_last_report/time_for_rcv_rate;
  322. }
  323. }
  324. else {
  325. // count number of packets received in the last RTT
  326. if (rtt_ > 0){
  327. double last = rtvec_[maxseq%hsz]; 
  328. int rcvd = 0;
  329. int i = maxseq;
  330. while (i > 0) {
  331. if (lossvec_[i%hsz] == RCVD) {
  332. if ((rtvec_[i%hsz] + rtt_) > last) 
  333. rcvd++; 
  334. else
  335. break ;
  336. }
  337. i--; 
  338. }
  339. if (rcvd > 0)
  340. thput = rcvd/rtt_; 
  341. }
  342. }
  343. return thput ;
  344. }
  345. /*
  346.  * Schedule sending this report, and set timer for the next one.
  347.  */
  348. void TfrcSinkAgent::nextpkt(double p) {
  349. sendpkt(p);
  350. /* schedule next report rtt/NumFeedback_ later */
  351. /* note from Sally: why is this 1.5 instead of 1.0? */
  352. if (rtt_ > 0.0 && NumFeedback_ > 0) 
  353. nack_timer_.resched(1.5*rtt_/NumFeedback_);
  354. }
  355. /*
  356.  * Create report message, and send it.
  357.  */
  358. void TfrcSinkAgent::sendpkt(double p)
  359. {
  360. double now = Scheduler::instance().clock();
  361. /*don't send an ACK unless we've received new data*/
  362. /*if we're sending slower than one packet per RTT, don't need*/
  363. /*multiple responses per data packet.*/
  364.         /*
  365.  * Do we want to send a report even if we have not received
  366.  * any new data?
  367.          */ 
  368. if (last_arrival_ >= last_report_sent) {
  369. Packet* pkt = allocpkt();
  370. if (pkt == NULL) {
  371. printf ("error allocating packetn");
  372. abort(); 
  373. }
  374. hdr_tfrc_ack *tfrc_ackh = hdr_tfrc_ack::access(pkt);
  375. tfrc_ackh->seqno=maxseq;
  376. tfrc_ackh->timestamp_echo=last_timestamp_;
  377. tfrc_ackh->timestamp_offset=now-last_arrival_;
  378. tfrc_ackh->timestamp=now;
  379. tfrc_ackh->NumFeedback_ = NumFeedback_;
  380. if (p < 0) 
  381. tfrc_ackh->flost = est_loss (); 
  382. else
  383. tfrc_ackh->flost = p;
  384. tfrc_ackh->rate_since_last_report = est_thput ();
  385. tfrc_ackh->losses = losses_since_last_report;
  386. if (total_received_ <= 0) 
  387. tfrc_ackh->true_loss = 0.0;
  388. else 
  389. tfrc_ackh->true_loss = 1.0 * 
  390.     total_losses_/(total_received_+total_dropped_);
  391. last_report_sent = now; 
  392. rcvd_since_last_report = 0;
  393. losses_since_last_report = 0;
  394. send(pkt, 0);
  395. }
  396. }
  397. int TfrcSinkAgent::command(int argc, const char*const* argv) 
  398. {
  399. if (argc == 3) {
  400. if (strcmp(argv[1], "weights") == 0) {
  401. /* 
  402.  * weights is a string of numbers, seperated by + signs
  403.  * the firs number is the total number of weights.
  404.  * the rest of them are the actual weights
  405.  * this overrides the defaults
  406.  */
  407. char *w ;
  408. w = (char *)calloc(strlen(argv[2])+1, sizeof(char)) ;
  409. if (w == NULL) {
  410. printf ("error allocating wn");
  411. abort();
  412. }
  413. strcpy(w, (char *)argv[2]);
  414. numsamples = atoi(strtok(w,"+"));
  415. sample = (int *)malloc((numsamples+1)*sizeof(int));
  416. losses = (int *)malloc((numsamples+1)*sizeof(int));
  417.                         count_losses = (int *)malloc((numsamples+1)*sizeof(int));
  418.                         num_rtts = (int *)malloc((numsamples+1)*sizeof(int));
  419. weights = (double *)malloc((numsamples+1)*sizeof(double));
  420. mult = (double *)malloc((numsamples+1)*sizeof(double));
  421. fflush(stdout);
  422. if (sample && weights) {
  423. int count = 0 ;
  424. while (count < numsamples) {
  425. sample[count] = 0;
  426. losses[count] = 1;
  427. count_losses[count] = 0;
  428.                                         num_rtts[count] = 0;
  429. mult[count] = 1;
  430. char *w;
  431. w = strtok(NULL, "+");
  432. if (w == NULL)
  433. break ; 
  434. else {
  435. weights[count++] = atof(w);
  436. }
  437. }
  438. if (count < numsamples) {
  439. printf ("error in weights string %sn", argv[2]);
  440. abort();
  441. }
  442. sample[count] = 0;
  443. losses[count] = 1;
  444. count_losses[count] = 0;
  445. num_rtts[count] = 0;
  446. weights[count] = 0;
  447. mult[count] = 1;
  448. free(w);
  449. return (TCL_OK);
  450. }
  451. else {
  452. printf ("error allocating memory for smaple and weights:2n");
  453. abort();
  454. }
  455. }
  456. }
  457. return (Agent::command(argc, argv));
  458. }
  459. void TfrcNackTimer::expire(Event *) {
  460. a_->nextpkt(-1);
  461. }
  462. void TfrcSinkAgent::print_loss(int sample, double ave_interval)
  463. {
  464. double now = Scheduler::instance().clock();
  465. double drops = 1/ave_interval;
  466. // This is ugly to include this twice, but the first one is
  467. //   for backward compatibility with earlier scripts. 
  468. printf ("time: %7.5f loss_rate: %7.5f n", now, drops);
  469. printf ("time: %7.5f sample 0: %5d loss_rate: %7.5f n", 
  470. now, sample, drops);
  471. //printf ("time: %7.5f send_rate: %7.5fn", now, sendrate);
  472. //printf ("time: %7.5f maxseq: %dn", now, maxseq);
  473. }
  474. void TfrcSinkAgent::print_loss_all(int *sample) 
  475. {
  476. double now = Scheduler::instance().clock();
  477. printf ("%f: sample 0: %5d 1: %5d 2: %5d 3: %5d 4: %5dn", 
  478. now, sample[0], sample[1], sample[2], sample[3], sample[4]); 
  479. }
  480. void TfrcSinkAgent::print_losses_all(int *losses) 
  481. {
  482. double now = Scheduler::instance().clock();
  483. printf ("%f: losses 0: %5d 1: %5d 2: %5d 3: %5d 4: %5dn", 
  484. now, losses[0], losses[1], losses[2], losses[3], losses[4]); 
  485. }
  486. void TfrcSinkAgent::print_count_losses_all(int *count_losses) 
  487. {
  488. double now = Scheduler::instance().clock();
  489. printf ("%f: count? 0: %5d 1: %5d 2: %5d 3: %5d 4: %5dn", 
  490. now, count_losses[0], count_losses[1], count_losses[2], count_losses[3], count_losses[4]); 
  491. }
  492. void TfrcSinkAgent::print_num_rtts_all(int *count_losses) 
  493. {
  494. double now = Scheduler::instance().clock();
  495. printf ("%f: rtts 0: %5d 1: %5d 2: %5d 3: %5d 4: %5dn", 
  496.      now, num_rtts[0], num_rtts[1], num_rtts[2], num_rtts[3], num_rtts[4]); 
  497. }
  498. ////////////////////////////////////////
  499. // algo specific code /////////////////
  500. ///////////////////////////////////////
  501. ////
  502. /// WALI Code
  503. ////
  504. double TfrcSinkAgent::est_loss_WALI () 
  505. {
  506. int i;
  507. double ave_interval1, ave_interval2; 
  508. int ds ; 
  509. if (!init_WALI_flag) {
  510. init_WALI () ;
  511. }
  512. // sample[i] counts the number of packets in the i-th loss interval
  513. // sample[0] contains the most recent sample.
  514.         // losses[i] contains the number of losses in the i-th loss interval
  515.         // count_losses[i] is 1 if the i-th loss interval is short.
  516.         // num_rtts[i] contains the number of rtts in the i-th loss interval
  517. for (i = last_sample; i <= maxseq ; i ++) {
  518. sample[0]++;
  519. if (lossvec_[i%hsz] == LOST || lossvec_[i%hsz] == ECNLOST) {
  520.         //  new loss event
  521. sample_count ++;
  522. shift_array (sample, numsamples+1, 0); 
  523. shift_array (losses, numsamples+1, 1); 
  524. shift_array (count_losses, numsamples+1, 1); 
  525. shift_array (num_rtts, numsamples+1, 0); 
  526. multiply_array(mult, numsamples+1, mult_factor_);
  527. shift_array (mult, numsamples+1, 1.0); 
  528. mult_factor_ = 1.0;
  529. }
  530. }
  531. last_sample = maxseq+1 ; 
  532. double now = Scheduler::instance().clock();
  533.         //if (ShortIntervals_ > 0 && printLoss_ > 0) {
  534.         //    printf ("now: %5.2f lastloss: %5.2f ShortRtts_: %d rtt_: %5.2fn",
  535.         //         now, lastloss, ShortRtts_, rtt_);
  536.         //}
  537.         if (ShortIntervals_ > 0 && 
  538.             now - lastloss > ShortRtts_ * rtt_) {
  539.               // Check if the current loss interval is short.
  540.               count_losses[0] = 0;
  541.         }
  542.         if (ShortIntervals_ > 0 && rtt_ > 0) {
  543.               // Count number of rtts in current loss interval.
  544.               num_rtts[0] = (int) ceil((now - lastloss) / rtt_);
  545.               if (num_rtts[0] < 1) num_rtts[0] = 1;
  546.         }
  547. if (sample_count>numsamples+1)
  548. // The array of loss intervals is full.
  549. ds=numsamples+1;
  550.      else
  551. ds=sample_count;
  552. if (sample_count == 1 && false_sample == 0) 
  553. // no losses yet
  554. return 0; 
  555. /* do we need to discount weights? */
  556. if (sample_count > 1 && discount && sample[0] > 0) {
  557.                 double ave = weighted_average1(1, ds, 1.0, mult, weights, sample, ShortIntervals_, losses, count_losses, num_rtts);
  558. int factor = 2;
  559. double ratio = (factor*ave)/sample[0];
  560. if ( ratio < 1.0) {
  561. // the most recent loss interval is very large
  562. mult_factor_ = ratio;
  563. double min_ratio = minDiscountRatio_;
  564. if (mult_factor_ < min_ratio) 
  565. mult_factor_ = min_ratio;
  566. }
  567. }
  568. // Calculations including the most recent loss interval.
  569.         ave_interval1 = weighted_average1(0, ds, mult_factor_, mult, weights, sample, ShortIntervals_, losses, count_losses, num_rtts);
  570.         // Calculations not including the most recent loss interval.
  571.         ave_interval2 = weighted_average1(1, ds, mult_factor_, mult, weights, sample, ShortIntervals_, losses, count_losses, num_rtts);
  572. // The most recent loss interval does not end in a loss
  573. // event.  Include the most recent interval in the 
  574. // calculations only if this increases the estimated loss
  575. // interval. 
  576.         // If ShortIntervals is less than 10, do not count the most
  577.         //   recent interval if it is a short interval.
  578.         //   Values of ShortIntervals greater than 10 are only for
  579.         //   validation purposes, and for backwards compatibility.
  580.         //
  581. if (ave_interval2 > ave_interval1 ||
  582.              (ShortIntervals_ > 1 && ShortIntervals_ < 10 
  583.                      && count_losses[0] == 1))
  584.                 // The second condition is to check if the first interval
  585.                 //  is a short interval.  If so, we must use ave_interval2.
  586. ave_interval1 = ave_interval2;
  587. if (ave_interval1 > 0) { 
  588. if (printLoss_ > 0) {
  589. print_loss(sample[0], ave_interval1);
  590. print_loss_all(sample);
  591. if (ShortIntervals_ > 0) {
  592. print_losses_all(losses);
  593. print_count_losses_all(count_losses);
  594.                                 print_num_rtts_all(num_rtts);
  595. }
  596. }
  597. return 1/ave_interval1; 
  598. } else return 999;     
  599. }
  600. // Calculate the weighted average.
  601. double TfrcSinkAgent::weighted_average(int start, int end, double factor, double *m, double *w, int *sample)
  602. {
  603. int i; 
  604. double wsum = 0;
  605. double answer = 0;
  606. if (smooth_ == 1 && start == 0) {
  607. if (end == numsamples+1) {
  608. // the array is full, but we don't want to uses
  609. //  the last loss interval in the array
  610. end = end-1;
  611. // effectively shift the weight arrays 
  612. for (i = start ; i < end; i++) 
  613. if (i==0)
  614. wsum += m[i]*w[i+1];
  615. else 
  616. wsum += factor*m[i]*w[i+1];
  617. for (i = start ; i < end; i++)  
  618. if (i==0)
  619.   answer += m[i]*w[i+1]*sample[i]/wsum;
  620. else 
  621. answer += factor*m[i]*w[i+1]*sample[i]/wsum;
  622.         return answer;
  623. } else {
  624. for (i = start ; i < end; i++) 
  625. if (i==0)
  626. wsum += m[i]*w[i];
  627. else 
  628. wsum += factor*m[i]*w[i];
  629. for (i = start ; i < end; i++)  
  630. if (i==0)
  631.   answer += m[i]*w[i]*sample[i]/wsum;
  632. else 
  633. answer += factor*m[i]*w[i]*sample[i]/wsum;
  634.         return answer;
  635. }
  636. }
  637. int TfrcSinkAgent::get_sample(int oldSample, int numLosses) 
  638. {
  639. int newSample;
  640. if (numLosses == 0) {
  641. newSample = oldSample;
  642. } else {
  643. newSample = oldSample / numLosses;
  644. }
  645. return newSample;
  646. }
  647. int TfrcSinkAgent::get_sample_rtts(int oldSample, int numLosses, int rtts) 
  648. {
  649. int newSample;
  650. if (numLosses == 0) {
  651. newSample = oldSample;
  652.                 //printf ("sample: %d numLosses: %dn", oldSample, numLosses);
  653. } else {
  654.                 double fraction;
  655.                 if (ShortRtts_ != 0)
  656.                      fraction = (ShortRtts_ + 1.0 - rtts) / ShortRtts_;
  657.                 else fraction = 1.0;
  658. int numLoss = (int) (floor(fraction * numLosses ));
  659.                 if (numLoss != 0)
  660.   newSample = oldSample / numLoss;
  661.                 else newSample = oldSample;
  662.                 //printf ("sample: %d rtts: %d numLosses: %d newSample: %d fraction: %5.2f numLoss %dn",
  663.                 //  oldSample, rtts, numLosses, newSample, fraction, numLoss);
  664. }
  665. return newSample;
  666. }
  667. // Calculate the weighted average, factor*m[i]*w[i]*sample[i]/wsum.
  668. // "factor" is "mult_factor_", for weighting the most recent interval
  669. //    when it is very large
  670. // "m[i]" is "mult[]", for old values of "mult_factor_".
  671. //
  672. // When ShortIntervals_%10 is 1, the length of a loss interval is
  673. //   "sample[i]/losses[i]" for short intervals, not just "sample[i]".
  674. //   This is equivalent to a loss event rate of "losses[i]/sample[i]",
  675. //   instead of "1/sample[i]".
  676. //
  677. // When ShortIntervals_%10 is 2, it is like ShortIntervals_ of 1,
  678. //   except that the number of losses per loss interval is at
  679. //   most 1460/byte-size-of-small-packets.
  680. //
  681. // When ShortIntervals_%10 is 3, short intervals are up to three RTTs,
  682. //   and the number of losses counted is a function of the interval size.
  683. //
  684. double TfrcSinkAgent::weighted_average1(int start, int end, double factor, double *m, double *w, int *sample, int ShortIntervals, int *losses, int *count_losses, int *num_rtts)
  685. {
  686.         int i;
  687.         int ThisSample;
  688.         double wsum = 0;
  689.         double answer = 0;
  690.         if (smooth_ == 1 && start == 0) {
  691.                 if (end == numsamples+1) {
  692.                         // the array is full, but we don't want to use
  693.                         //  the last loss interval in the array
  694.                         end = end-1;
  695.                 }
  696.                 // effectively shift the weight arrays
  697.                 for (i = start ; i < end; i++)
  698.                         if (i==0)
  699.                                 wsum += m[i]*w[i+1];
  700.                         else
  701.                                 wsum += factor*m[i]*w[i+1];
  702.                 for (i = start ; i < end; i++) {
  703.                         ThisSample = sample[i];
  704.                         if (ShortIntervals%10 == 1 && count_losses[i] == 1) {
  705.        ThisSample = get_sample(sample[i], losses[i]);
  706.                         }
  707.                         if (ShortIntervals%10 == 2 && count_losses[i] == 1) {
  708.        int adjusted_losses = int(fsize_/size_);
  709.        if (losses[i] < adjusted_losses) {
  710. adjusted_losses = losses[i];
  711.        }
  712.        ThisSample = get_sample(sample[i], adjusted_losses);
  713.                         }
  714.                         if (ShortIntervals%10 == 3 && count_losses[i] == 1) {
  715.        ThisSample = get_sample_rtts(sample[i], losses[i], num_rtts[i]);
  716.                         }
  717.                         if (i==0)
  718.                                 answer += m[i]*w[i+1]*ThisSample/wsum;
  719.                                 //answer += m[i]*w[i+1]*sample[i]/wsum;
  720.                         else
  721.                                 answer += factor*m[i]*w[i+1]*ThisSample/wsum;
  722.                                 //answer += factor*m[i]*w[i+1]*sample[i]/wsum;
  723. }
  724.                 return answer;
  725.         } else {
  726.                 for (i = start ; i < end; i++)
  727.                         if (i==0)
  728.                                 wsum += m[i]*w[i];
  729.                         else
  730.                                 wsum += factor*m[i]*w[i];
  731.                 for (i = start ; i < end; i++) {
  732.                        ThisSample = sample[i];
  733.                        if (ShortIntervals%10 == 1 && count_losses[i] == 1) {
  734.        ThisSample = get_sample(sample[i], losses[i]);
  735.                        }
  736.                        if (ShortIntervals%10 == 2 && count_losses[i] == 1) {
  737.        ThisSample = get_sample(sample[i], 7);
  738.        // Replace 7 by 1460/packet size.
  739.                                // NOT FINISHED.
  740.                        }
  741.                         if (ShortIntervals%10 == 3 && count_losses[i] == 1) {
  742.        ThisSample = get_sample_rtts(sample[i], losses[i], (int) num_rtts[i]);
  743.                         }
  744.                        if (i==0)
  745.                                 answer += m[i]*w[i]*ThisSample/wsum;
  746.                                 //answer += m[i]*w[i]*sample[i]/wsum;
  747.                         else
  748.                                 answer += factor*m[i]*w[i]*ThisSample/wsum;
  749.                                 //answer += factor*m[i]*w[i]*sample[i]/wsum;
  750. }
  751.                 return answer;
  752.         }
  753. }
  754. // Shift array a[] up, starting with a[sz-2] -> a[sz-1].
  755. void TfrcSinkAgent::shift_array(int *a, int sz, int defval) 
  756. {
  757. int i ;
  758. for (i = sz-2 ; i >= 0 ; i--) {
  759. a[i+1] = a[i] ;
  760. }
  761. a[0] = defval;
  762. }
  763. void TfrcSinkAgent::shift_array(double *a, int sz, double defval) {
  764. int i ;
  765. for (i = sz-2 ; i >= 0 ; i--) {
  766. a[i+1] = a[i] ;
  767. }
  768. a[0] = defval;
  769. }
  770. // Multiply array by value, starting with array index 1.
  771. // Array index 0 of the unshifted array contains the most recent interval.
  772. void TfrcSinkAgent::multiply_array(double *a, int sz, double multiplier) {
  773. int i ;
  774. for (i = 1; i <= sz-1; i++) {
  775. double old = a[i];
  776. a[i] = old * multiplier ;
  777. }
  778. }
  779. /*
  780.  * We just received our first loss, and need to adjust our history.
  781.  */
  782. double TfrcSinkAgent::adjust_history (double ts)
  783. {
  784. int i;
  785. double p;
  786. for (i = maxseq; i >= 0 ; i --) {
  787. if (lossvec_[i%hsz] == LOST || lossvec_[i%hsz] == ECNLOST ) {
  788. lossvec_[i%hsz] = NOT_RCVD; 
  789. }
  790. }
  791. lastloss = ts; 
  792. lastloss_round_id = round_id ;
  793. p=b_to_p(est_thput()*psize_, rtt_, tzero_, fsize_, 1);
  794. false_sample = (int)(1.0/p);
  795. sample[1] = false_sample;
  796. sample[0] = 0;
  797. losses[1] = 0;
  798. losses[0] = 1;
  799. count_losses[1] = 0;
  800. count_losses[0] = 0;
  801.         num_rtts[0]=0;
  802.         num_rtts[1]=0;
  803. sample_count++; 
  804. if (printLoss_) {
  805. print_loss_all (sample);
  806. if (ShortIntervals_ > 0) {
  807. print_losses_all(losses);
  808. print_count_losses_all(count_losses);
  809. print_num_rtts_all(num_rtts);
  810. }
  811. }
  812. false_sample = -1 ; 
  813. return p;
  814. }
  815. /*
  816.  * Initialize data structures for weights.
  817.  */
  818. void TfrcSinkAgent::init_WALI () {
  819. int i;
  820. if (numsamples < 0)
  821. numsamples = DEFAULT_NUMSAMPLES ;
  822. if (smooth_ == 1) {
  823. numsamples = numsamples + 1;
  824. }
  825. sample = (int *)malloc((numsamples+1)*sizeof(int));
  826.         losses = (int *)malloc((numsamples+1)*sizeof(int));
  827.         count_losses = (int *)malloc((numsamples+1)*sizeof(int));
  828.         num_rtts = (int *)malloc((numsamples+1)*sizeof(int));
  829. weights = (double *)malloc((numsamples+1)*sizeof(double));
  830. mult = (double *)malloc((numsamples+1)*sizeof(double));
  831. for (i = 0 ; i < numsamples+1 ; i ++) {
  832. sample[i] = 0 ; 
  833. }
  834. if (smooth_ == 1) {
  835. int mid = int(numsamples/2);
  836. for (i = 0; i < mid; i ++) {
  837. weights[i] = 1.0;
  838. }
  839. for (i = mid; i <= numsamples; i ++){
  840. weights[i] = 1.0 - (i-mid)/(mid + 1.0);
  841. }
  842. } else {
  843. int mid = int(numsamples/2);
  844. for (i = 0; i < mid; i ++) {
  845. weights[i] = 1.0;
  846. }
  847. for (i = mid; i <= numsamples; i ++){
  848. weights[i] = 1.0 - (i+1-mid)/(mid + 1.0);
  849. }
  850. }
  851. for (i = 0; i < numsamples+1; i ++) {
  852. mult[i] = 1.0 ; 
  853. }
  854. init_WALI_flag = 1;  /* initialization done */
  855. }
  856. ///////////////////////////
  857. // EWMA //////////////////
  858. //////////////////////////
  859. double TfrcSinkAgent::est_loss_EWMA () {
  860. double p1, p2 ;
  861. for (int i = last_sample; i <= maxseq ; i ++) {
  862. loss_int++; 
  863. if (lossvec_[i%hsz] == LOST || lossvec_[i%hsz] == ECNLOST ) {
  864. if (avg_loss_int < 0) {
  865. avg_loss_int = loss_int ; 
  866. } else {
  867. avg_loss_int = history*avg_loss_int + (1-history)*loss_int ;
  868. }
  869. loss_int = 0 ;
  870. }
  871. }
  872. last_sample = maxseq+1 ; 
  873. if (avg_loss_int < 0) { 
  874. p1 = 0;
  875. } else {
  876. p1 = 1.0/avg_loss_int ; 
  877. }
  878. if (loss_int == 0 
  879.     || avg_loss_int < 0){ //XXX this last check was added by a
  880.   //person who knows nothing of this
  881.   //code just to stop FP div by zero.
  882.   //Values were history=.75,
  883.   //avg_loss_int=-1, loss_int=3.  If
  884.   //you know what should be here,
  885.   //please cleanup and remove this
  886.   //comment.
  887. p2 = p1 ; 
  888. } else {
  889. p2 = 1.0/(history*avg_loss_int + (1-history)*loss_int) ;
  890. }
  891. if (p2 < p1) {
  892. p1 = p2 ; 
  893. }
  894. if (printLoss_ > 0) {
  895. if (p1 > 0) 
  896. print_loss(loss_int, 1.0/p1);
  897. else
  898. print_loss(loss_int, 0.00001);
  899. print_loss_all(sample);
  900. }
  901. return p1 ;
  902. }
  903. ///////////////////////////
  904. // RBPH //////////////////
  905. //////////////////////////
  906. double TfrcSinkAgent::est_loss_RBPH () {
  907. double numpkts = hsz ;
  908. double p ; 
  909. // how many pkts we should go back?
  910. if (sendrate > 0 && rtt_ > 0) {
  911. double x = b_to_p(sendrate, rtt_, tzero_, psize_, 1);
  912. if (x > 0) 
  913. numpkts = minlc/x ; 
  914. else
  915. numpkts = hsz ;
  916. }
  917. // that number must be below maxseq and hsz 
  918. if (numpkts > maxseq)
  919. numpkts = maxseq ;
  920. if (numpkts > hsz)
  921. numpkts = hsz ;
  922. int lc = 0;
  923. int pc = 0;
  924. int i = maxseq ;
  925. // first see if how many lc's we find in numpkts 
  926. while (pc < numpkts) {
  927. pc ++ ;
  928. if (lossvec_[i%hsz] == LOST || lossvec_[i%hsz] == ECNLOST )
  929. lc ++ ; 
  930. i -- ;
  931. }
  932. // if not enough lsos events, keep going back ...
  933. if (lc < minlc) {
  934. // but only as far as the history allows ...
  935. numpkts = maxseq ;
  936. if (numpkts > hsz)
  937. numpkts = hsz ;
  938. while ((lc < minlc) && (pc < numpkts)) {
  939. pc ++ ;
  940. if (lossvec_[i%hsz] == LOST || lossvec_[i%hsz] == ECNLOST )
  941. lc ++ ;
  942. i -- ;
  943. }
  944. }
  945. if (pc == 0) 
  946. p = 0; 
  947. else
  948. p = (double)lc/(double)pc ; 
  949. if (printLoss_ > 0) {
  950. if (p > 0) 
  951. print_loss(0, 1.0/p);
  952. else
  953. print_loss(0, 0.00001);
  954. print_loss_all(sample);
  955. }
  956. return p ;
  957. }
  958. ///////////////////////////
  959. // EBPH //////////////////
  960. //////////////////////////
  961. double TfrcSinkAgent::est_loss_EBPH () {
  962. double numpkts = hsz ;
  963. double p ; 
  964. int lc = 0;
  965. int pc = 0;
  966. int i = maxseq ;
  967. numpkts = maxseq ;
  968. if (numpkts > hsz)
  969. numpkts = hsz ;
  970. while ((lc < minlc) && (pc < numpkts)) {
  971. pc ++ ;
  972. if (lossvec_[i%hsz] == LOST || lossvec_[i%hsz] == ECNLOST)
  973. lc ++ ;
  974. i -- ;
  975. }
  976. if (pc == 0) 
  977. p = 0; 
  978. else
  979. p = (double)lc/(double)pc ; 
  980. if (printLoss_ > 0) {
  981. if (p > 0) 
  982. print_loss(0, 1.0/p);
  983. else
  984. print_loss(0, 0.00001);
  985. print_loss_all(sample);
  986. }
  987. return p ;
  988. }