idnits 2.17.1 draft-ietf-ippm-reporting-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 16. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 1552. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1563. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1570. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1576. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Introduction section. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (July 14, 2008) is 5764 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: '1' on line 1371 -- Looks like a reference, but probably isn't: '1000' on line 1342 Summary: 2 errors (**), 0 flaws (~~), 1 warning (==), 10 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group S. Shalunov 3 Internet-Draft 4 Intended status: Standards Track M. Swany 5 Expires: January 15, 2009 University of Delaware 6 July 14, 2008 8 Reporting IP Performance Metrics to Users 9 draft-ietf-ippm-reporting-02.txt 11 Status of this Memo 13 By submitting this Internet-Draft, each author represents that any 14 applicable patent or other IPR claims of which he or she is aware 15 have been or will be disclosed, and any of which he or she becomes 16 aware will be disclosed, in accordance with Section 6 of BCP 79. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet- 21 Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six months 24 and may be updated, replaced, or obsoleted by other documents at any 25 time. It is inappropriate to use Internet-Drafts as reference 26 material or to cite them other than as "work in progress." 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/ietf/1id-abstracts.txt. 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 This Internet-Draft will expire on January 15, 2009. 36 Abstract 38 The aim of this document is to define a small set of metrics that are 39 robust, easy to understand, orthogonal, relevant, and easy to 40 compute. The IPPM WG has defined a large number of richly 41 parameterized metrics because network measurement has many purposes. 42 Often, the ultimate purpose is to report a concise set of metrics 43 describing a network's state to an end user. It is for this purpose 44 that the present set of metrics is defined. 46 Table of Contents 48 1. Requirements Notation . . . . . . . . . . . . . . . . . . . . 3 49 2. Goals and Motivation . . . . . . . . . . . . . . . . . . . . . 4 50 3. Applicability for Long-Term Measurements . . . . . . . . . . . 6 51 4. Reportable Metrics Set . . . . . . . . . . . . . . . . . . . . 7 52 4.1. Median Delay . . . . . . . . . . . . . . . . . . . . . . . 7 53 4.2. Loss Ratio . . . . . . . . . . . . . . . . . . . . . . . . 7 54 4.3. Delay Spread . . . . . . . . . . . . . . . . . . . . . . . 7 55 4.4. Duplication . . . . . . . . . . . . . . . . . . . . . . . 7 56 4.5. Reordering . . . . . . . . . . . . . . . . . . . . . . . . 8 57 5. Sample Source . . . . . . . . . . . . . . . . . . . . . . . . 9 58 5.1. One-Way Active Measurement . . . . . . . . . . . . . . . . 9 59 5.2. Round-Trip Active Measurement . . . . . . . . . . . . . . 10 60 5.3. Passive Measurement . . . . . . . . . . . . . . . . . . . 10 61 6. Security Considerations . . . . . . . . . . . . . . . . . . . 11 62 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 12 63 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13 64 9. Internationalization Considerations . . . . . . . . . . . . . 14 65 10. Normative References . . . . . . . . . . . . . . . . . . . . . 15 66 Appendix A. Sample Source Code for Computing the Metrics . . . . 16 67 Appendix B. Example Report . . . . . . . . . . . . . . . . . . . 40 68 Appendix C. TODO . . . . . . . . . . . . . . . . . . . . . . . . 41 69 Appendix D. Revision History . . . . . . . . . . . . . . . . . . 42 70 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 43 71 Intellectual Property and Copyright Statements . . . . . . . . . . 44 73 1. Requirements Notation 75 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 76 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 77 document are to be interpreted as described in [RFC2119]. 79 2. Goals and Motivation 81 The IPPM working group has defined many richly parameterized 82 performance metrics with a number of variants (one-way delay, one-way 83 loss, delay variation, reordering, etc.) and a protocol for obtaining 84 the measurement data needed to compute these metrics (OWAMP). It 85 would be beneficial to define a standard way to report a set of 86 performance metrics to end users. Parameterization might be 87 acceptable in such a set, but there must still be defaults for 88 everything. It is especially important to get these defaults right. 89 Such a set would enable different tools to produce results that can 90 be compared against each other. 92 Existing tools already report statistic about the network. This is 93 done for varying reasons: network testing tools, such as the ping 94 program available in UNIX-derived operating systems as well as in 95 Microsoft Windows, report statistics with no knowledge of why the 96 user is running the program; networked games might report statistics 97 of the network connection to the server so users can better 98 understand why they get the results they get (e.g., if something is 99 slow, is this because of the network or the CPU?), so they can 100 compare their statistics to those of others ("you're not lagged any 101 more than I am") or perhaps so that users can decide whether they 102 need to upgrade the connection to their home; IP telephony hardware 103 and software might report the statistics for similar reasons. While 104 existing tools report statistics all right, the particular set of 105 metrics they choose is ad hoc; some metrics are not statistically 106 robust, some are not relevant, and some are not easy to understand; 107 more important than specific shortcomings, however, is the 108 incompatibility: even if the sets of metrics were perfect, they would 109 still be all different, and, therefore, metrics reported by different 110 tools would not be comparable. 112 The set of metrics of this document is meant for human consumption. 113 It must therefore be small. Anything greater than half-dozen numbers 114 is certainly too confusing. 116 Each of the metrics must be statistically robust. Intuitively, this 117 means that having a small number of bad data points and a small 118 amount of noise must not dramatically change the metric. 120 Each metric in the set must have, qualitatively, an immediate 121 intuitive meaning that has to be obvious for an advanced end user 122 without consulting documentation (that is, it has to be clear what 123 rough meaning, intuitively, the larger values of a given metric 124 have). 126 To be small, the set has to be orthogonal: each of the metrics has to 127 express a property not covered by other metrics (otherwise, there's 128 redundancy). 130 The metrics in the set must be relevant. Partly, being easy to 131 understand will help achieve this, but additional constraint may be 132 placed by relevancy. 134 Finally, while this set will most frequently be computed for small 135 data sets, where efficiency is not a serious consideration, it must 136 be possible to compute for large data sets, too. In particular, it 137 must be possible to compute the metrics in a single pass over the 138 data using a limited amount of memory (i.e., it must be possible to 139 take a source of measurement data with a high data rate and compute 140 the metrics on the fly, discarding each data point after it is 141 processed). 143 3. Applicability for Long-Term Measurements 145 The metrics in this document are most applicable to short-term 146 network measurements (seconds or at most minutes) and are targeted 147 for real-time display of such measurements. 149 One consideration that would have to be addressed to make these 150 metrics suitable for longer-term measurements (hours and days) is 151 that of network availability: during such long periods of time the 152 network may be completely down for some time and it does not seem to 153 make sense to average out the reports in such a way that the network 154 being down for 1% of the time becomes 1% packet loss. 156 4. Reportable Metrics Set 158 The following metrics comprise the set: 160 1. median delay; 162 2. loss ratio; 164 3. delay spread; 166 4. duplication; 168 5. reordering. 170 Each of the above is represented by a single numeric quantity, 171 computed as described below. 173 4.1. Median Delay 175 The reported median delay is the median of all delays in the sample. 176 When a packet is lost, its delay is to be considered +infinity for 177 the purposes of this computation; therefore, if more than half of all 178 packets are lost, the delay is +infinity. 180 4.2. Loss Ratio 182 Loss Ratio is the fraction, expressed as a percentile, of packets 183 that did not arrive intact within a given number of seconds (the 184 timeout value) after being sent. Since this set of metrics often has 185 to be reported to a waiting human user, the default timeout value 186 should be small. By default, 2 seconds MUST be the timeout value. 187 Use of a different timeout value MUST be reported. 189 4.3. Delay Spread 191 Delay spread is the interquartile spread of observed delays. This is 192 a metric to represent what is commonly referred to as "jitter". 193 Delay spread is reported as the difference of the 75th and 25th 194 percentiles of delay. When both percentiles are +infinity, the value 195 of delay spread is undefined. Therefore, if less than 25% of packets 196 are lost, it is defined and finite; if between 75% and 25% of packets 197 are lost, it is +infinity; finally, if more than 75% of packets are 198 lost, it is undefined. 200 4.4. Duplication 202 Duplication is the fraction of transmitted packets for which more 203 than a single copy of the packet was received within the timeout 204 period (ideally using the same timeout as in the definition of loss), 205 expressed in percentage points. 207 Note: while most received packets can be ones previously seen, 208 duplication can never exceed 100%. 210 4.5. Reordering 212 Reordering is the fraction of sent packets for which the sequence 213 number of the packet received immediately before the first copy of 214 the given packet is not the decrement of the sequence number of the 215 given packet. For the purposes of determining the sequence number of 216 the preceding packet in this definition, assuming sequence numbers 217 starting with 1, an extra packet at the start of the stream of 218 received packets, with a sequence number of 0, is considered to be 219 present (this extra packet, of course, is not counted for the 220 purposes of computing the fraction). 222 FIXME: References. 224 5. Sample Source 226 Section 4 describes the metrics to compute on a sample of 227 measurements. The source of the sample in not discussed there, and, 228 indeed, the metrics discussed (delay, loss, etc.) are simply 229 estimators that could be applied to any sample whatsoever. For the 230 names of the estimators to be applicable, of course, the measurements 231 need to come from a packet delivery network. 233 The data in the samples for the set of metrics discussed in this 234 document can come from the following sources: one-way active 235 measurement, round-trip measurement, and passive measurement. There 236 infrequently is a choice between active and passive measurement, as, 237 typically, only one is available; consequently, no preference is 238 given to one over the other. In cases where clocks can be expected 239 to be synchronized, in general, one-way measurements are preferred 240 over round-trip measurements (as one-way measurements are more 241 informative). When one-way measurements cannot be obtained, or when 242 clocks cannot be expected to be synchronized, round-trip measurement 243 MAY be used. 245 5.1. One-Way Active Measurement 247 The default duration of the measurement interval is 10 seconds. 249 The default sending schedule is a Poisson stream. 251 The default sending rate is 10 packets/second on average. The 252 default sending schedule is a Poisson stream. When randomized 253 schedules, such as a Poisson stream, are used, the rate MUST be set 254 with the distribution parameter(s). With a randomized schedule, the 255 default sample size is 100 packets and the measurement window 256 duration can vary to some extent depending on the values of the 257 (pseudo-)random deviates. 259 The default packet size is the minimum necessary for the measurement. 261 Values other than the default ones MAY be used; if they are used, 262 their use, and specific values used, MUST be reported. 264 A one-way active measurement is characterized by the source IP 265 address, the destination IP address, the time when measurement was 266 taken, and the type of packets (e.g., UDP with given port numbers and 267 a given DSCP) used in the measurement. For the time, the end of the 268 measurement interval MUST be reported. 270 5.2. Round-Trip Active Measurement 272 The same default parameters and characterization apply to round-trip 273 measurement as to one-way measurement (Section 5.1). 275 5.3. Passive Measurement 277 Passive measurement use whatever data it is natural to use. For 278 example, an IP telephony application or a networked game would use 279 the data that it sends. An analysis of performance of a link might 280 use all the packets that traversed the link in the measurement 281 interval. An analysis of performance of an Internet service 282 provider's network might use all the packets that traversed the 283 network in the measurement interval. An analysis of performance of a 284 specific service from the point of view of a given site might use an 285 appropriate filter to select only the relevant packets. In any case, 286 the source needs to be reported. 288 The same default duration applies to passive measurement as to one- 289 way active measurement (Section 5.1). 291 When the passive measurement data is reported in real time, or based 292 on user demand, a sliding window SHOULD be used as a measurement 293 period, so that recent data become more quickly reflected. For 294 historical reporting purposes, a fixed interval may be preferable. 296 6. Security Considerations 298 The reporting per se, not being a protocol, does not raise security 299 considerations. 301 An aspect of reporting relevant to security is how the reported 302 metrics are used and how they are collected. If it is important that 303 the metrics satisfy certain conditions (e.g., that the ISP whose 304 network is being measured be unable to make the metrics appear better 305 than they are), the collection mechanism MUST ensure that this is, 306 indeed, so. The exact mechanisms to do so are outside of scope of 307 this document and belong with discussion of particular measurement 308 data collection protocols. 310 7. Acknowledgments 312 We gratefully acknowledge discussion with, encouragement from, and 313 contributions of Lawrence D. Dunn, Reza Fardid, Ruediger Geib, 314 Matt Mathis, Al Morton, Carsten Schmoll, Henk Uijterwaal, and 315 Matthew J. Zekauskas. 317 8. IANA Considerations 319 This document requires no action from the IANA. 321 9. Internationalization Considerations 323 The reported metrics, while they might occasionally be parsed by 324 machine, are primarily meant for human consumption. As such, they 325 MAY be reported in the language preferred by the user, using an 326 encoding suitable for the purpose, such as UTF-8. 328 10. Normative References 330 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 331 Requirement Levels", BCP 14, RFC 2119, March 1997. 333 Appendix A. Sample Source Code for Computing the Metrics 335 This appendix only serves for illustrative purposes. 337 /* 338 * reporting.c -- performance metrics reporting as in Internet Draft 339 * draft-ietf-ippm-reporting. 340 * 341 * Written by Stanislav Shalunov, http://www.internet2.edu/~shalunov/ 342 * Bernhard Lutzmann, belu@users.sf.net 343 * Federico Montesino Pouzols, fedemp@altern.org 344 * 345 * This file is also available, under a different (BSD-style) 346 * license, as part of thrulay. 347 */ 349 /** 350 * @file reporting.c 351 * 352 * @short metrics computation and reporting. 353 **/ 355 #include 356 #include 357 #include 358 #include 359 #include 360 #include 362 #define min(a, b) ((a) < (b) ? (a) : (b)) 363 #define max(a, b) ((a) > (b) ? (a) : (b)) 365 /* 366 * Reordering. 367 */ 368 #define loop(x) ((x) >= 0 ? (x) : (x) + (int)reordering_max) 370 /* 371 * Duplication. 372 */ 373 static uint64_t *bitfield = NULL; /* Bit field used to check for 374 duplicated packets. */ 376 /* 377 * Reordering. 378 */ 379 static uint64_t reordering_max; /* We have m[j-1] == number of */ 380 static uint64_t *reordering_m; /* We have m[j-1] == number of 381 j-reordered packets. */ 382 static uint64_t *reordering_ring; /* Last sequence numbers seen */ 383 static int r = 0; /* Ring pointer for next write. */ 384 static int l = 0; /* Counter of sequence numbers. */ 386 /* 387 * Quantiles 388 * 389 * Reference: 390 * 391 * [1] Manku, Rajagopalan, Lindsay: "Approximate Medians and other 392 * Quantiles in One Pass and with Limited Memory", 393 * http://www-db.stanford.edu/~manku/papers/98sigmod-quantiles.pdf 394 */ 396 #define QUANTILE_EPS 0.005 398 static uint16_t quantile_max_seq; /* Maximum number of sequences */ 399 static int *quantile_k; /* number of elements in buffer */ 401 static double **quantile_input; /* This is the buffer where the 402 sequence of incoming packets is 403 saved. If we received enough 404 packets, we will write this 405 buffer to a quantile buffer. */ 406 static int *quantile_input_cnt; /* number of elements in input 407 * buffer */ 408 static int *quantile_empty_buffers; /* number of empty buffers */ 410 static int *quantile_b; /* number of buffers */ 412 static double **quantile_buf; 414 static int *quantile_alternate; /* this is used to determine 415 the offset in COLLAPSE (if 416 weight is even) */ 418 static uint64_t *quantile_inf_cnt; /* this counter is for the 419 additional -inf, +inf 420 elements we added to NEW 421 buffer to fill it up. */ 423 typedef struct quantile { 424 struct quantile *next; /* pointer to next quantile 425 * buffer */ 426 int weight; /* 0 if buffer is empty, > 0 if buffer is 427 * full */ 429 int level; 430 double *buffer; 431 int pos; /* current position in buffer; used in 432 quantile_collapse() */ 433 } quantile_t; 435 static quantile_t **quantile_buffer_head; 437 int 438 reordering_init(uint64_t max) 439 { 440 reordering_max = max; 441 reordering_m = calloc(reordering_max, sizeof(uint64_t)); 442 reordering_ring = calloc(reordering_max, sizeof(uint64_t)); 443 if (reordering_m == NULL) { 444 return -1; 445 } else { 446 return 0; 447 } 448 } 450 int 451 reordering_checkin(uint64_t packet_sqn) 452 { 453 int j; 455 for (j = 0; j < min(l, (int)reordering_max) && 457 packet_sqn < reordering_ring[loop(r-j-1)]; j++) { 458 reordering_m[j]++; 459 } 460 reordering_ring[r] = packet_sqn; 461 l++; 462 r = (r + 1) % reordering_max; 463 return 0; 464 } 466 double 467 reordering_output(uint64_t j) 468 { 469 if (j >= reordering_max) 470 return -1; 471 else 472 return (double)reordering_m[j] / (l - j - 1); 473 } 475 void 476 reordering_exit(void) 477 { 478 free(reordering_ring); 479 free(reordering_m); 480 } 482 int 483 duplication_init(uint64_t npackets) 484 { 485 uint64_t bitfield_len = 0; /* Number of sectors in bitfield */ 487 /* Allocate memory for bit field */ 488 bitfield_len = ((npackets % 64)? 489 (npackets / 64 + 1) : npackets / 64); 490 bitfield = calloc(bitfield_len, sizeof(uint64_t)); 491 if (bitfield == NULL) { 492 return -1; 493 } else { 494 return 0; 495 } 496 } 498 int 499 duplication_check(uint64_t packet_sqn) 500 { 501 uint64_t bitfield_sec; /* Which sector in bitfield */ 502 uint64_t bitfield_bit; /* Which bit in sector */ 504 /* Calculate sector */ 505 bitfield_sec = packet_sqn >> 6; 507 /* Calculate bit in sector */ 508 bitfield_bit = (uint64_t)1 << (packet_sqn & 63); 510 if (bitfield[bitfield_sec] & bitfield_bit) { 511 /* Duplicated packet */ 512 return 1; 513 } else { 514 /* Unique packet */ 515 bitfield[bitfield_sec] |= bitfield_bit; 516 return 0; 517 } 518 } 520 void 521 duplication_exit(void) 522 { 523 free(bitfield); 524 } 525 /* Calculate binomial coefficient C(n, k). */ 526 int64_t 527 binomial (int n, int k) 528 { 529 int64_t bc = 0; 530 int i, m; 532 /* C(n, k) = C(n, n-k) */ 533 k = min(k, n-k); 535 if (k >= 0) { 536 bc = 1; 537 m = max(k, n-k); 539 for (i = 1; i <= k; i++) { 540 bc = (bc * (m + i)) / i; 541 } 542 } 544 return bc; 545 } 547 int 548 quantile_compare(const void *d1, const void *d2) 549 { 550 if (*(double *)d1 < *(double *)d2) { 551 return -1; 552 } else if (*(double *)d1 == *(double *)d2) { 553 return 0; 554 } else { 555 assert(*(double *)d1 > *(double *)d2); 556 return 1; 557 } 558 } 560 void 561 quantile_sort (double *list, int length) 562 { 563 qsort(list, length, sizeof(double), quantile_compare); 564 } 566 /** 567 * Implementation of NEW operation from section 3.1 of paper [1]. 568 * 569 * Takes as input an empty buffer. Simply populates the quantile 570 * buffer with the next k elements from the input sequence, labels 571 * the buffer as full, and assigns it a weight of 1. 572 * 573 * If there are not enough elements to fill up the buffer, we 574 * alternately add -inf, +inf elements until buffer is full (-inf 575 * == 0, +inf == DBL_MAX). 576 * 577 * NOTE: We sort the elements in the input buffer before we copy 578 * them to the quantile buffer. 579 * 580 * @param seq Sequence index. 581 * 582 * @return 583 * @retval 0 on success. 584 * @retval -2 need an empty buffer. 585 * @retval -3 bad input sequence length. 586 **/ 587 int 588 quantile_new(uint16_t seq, quantile_t *q, double *input, int k, 589 int level) 590 { 591 int i; 593 /* Check that buffer is really empty. */ 594 if (q->weight != 0) { 595 return -2; 596 } 598 /* Sanity check for length of input sequence. */ 599 if (k > quantile_k[seq]) { 600 return -3; 601 } 603 /* If there are not enough elements in the input buffer, fill 604 * it up with -inf, +inf elements. */ 605 for (i = k; i < quantile_k[seq]; i++) { 606 if (i % 2) { 607 input[i] = DBL_MAX; 608 } else { 609 input[i] = 0; 610 } 612 /* Increment counter that indicates how many additional 613 * elements we added to fill the buffer. */ 614 quantile_inf_cnt[seq]++; 615 } 617 quantile_sort(input, quantile_k[seq]); 619 memcpy(q->buffer, input, sizeof(double) * quantile_k[seq]); 620 /* Mark buffer as full and set level. */ 621 q->weight = 1; 622 q->level = level; 624 /* Update number of empty quantile buffers. */ 625 quantile_empty_buffers[seq]--; 627 return 0; 628 } 630 /* Implementation of COLLAPSE operation from section 3.2 of paper 631 * [1]. 632 * 633 * This is called from quantile_algorithm() if there are no empty 634 * buffers. We COLLAPSE all the full buffers, where level has 635 * value `level'. Output is written to the first buffer in linked 636 * list with level set to `level'. The level of the output buffer 637 * is increased by 1. All other buffers we used in the COLLAPSE 638 * are marked empty. */ 639 int 640 quantile_collapse(uint16_t seq, int level) 641 { 642 quantile_t *qp = NULL, *qp_out = NULL; 643 int num_buffers = 0; /* number of buffers with level 644 * `level' */ 645 int weight = 0; /* weight of the output buffer */ 646 int offset; 647 int i, j; 648 double min_dbl; 649 long next_pos; 650 long merge_pos = 0; 652 /* Check that there are at least two full buffers with given 653 * level. Also calculate weight of output buffer. */ 654 for (qp = quantile_buffer_head[seq]; qp != NULL; qp = qp->next) { 655 if ((qp->weight != 0) && (qp->level == level)) { 656 num_buffers++; 657 weight += qp->weight; 658 qp->pos = 0; 659 } else { 660 /* We mark the buffers that are not used in this 661 * COLLAPSE. */ 662 qp->pos = -1; 663 } 664 } 665 if (num_buffers < 2) { 666 return -4; 668 } 670 /* NOTE: The elements in full buffers are sorted. So we don't 671 * have to do that again. 672 */ 673 /* Search for first full buffer with matching level. This is 674 * the buffer where we save the output. */ 675 for (qp_out = quantile_buffer_head[seq]; qp_out != NULL; 676 qp_out = qp_out->next) { 677 if (qp_out->pos != -1) { 678 break; 679 } 680 } 682 /* Calculate offset */ 683 if (weight % 2) { 684 /* odd */ 685 offset = (weight + 1) / 2; 686 } else { 687 /* even - we alternate between two choices in each 688 * COLLAPSE */ 689 if (quantile_alternate[seq] % 2) { 690 offset = weight / 2; 691 } else { 692 offset = (weight + 2)/ 2; 693 } 694 quantile_alternate[seq] = (quantile_alternate[seq] + 1) % 2; 695 } 697 /* Initialize next position of element to save. Because first 698 * position is at 0, we have to decrement offset by 1. */ 699 next_pos = offset - 1; 701 for (i = 0; i < quantile_k[seq]; ) { 703 /* Search for current minimal element in all buffers. 704 * Because buffers are all sorted, we just have to check 705 * the element at current position. */ 706 min_dbl = DBL_MAX; 707 for (qp = quantile_buffer_head[seq]; qp != NULL; 708 qp = qp->next) { 709 /* Skip wrong buffers. */ 710 if (qp->pos == -1) { 711 continue; 712 } 714 /* Check that we are not at the end of buffer. */ 715 if (qp->pos >= quantile_k[seq]) { 716 continue; 717 } 719 /* Update minimum element. */ 720 min_dbl = min(min_dbl, qp->buffer[qp->pos]); 721 } 723 /* Now process this minimal element in all buffers. */ 724 for (qp = quantile_buffer_head[seq]; qp != NULL; 725 qp = qp->next) { 726 /* Skip wrong buffers. */ 727 if (qp->pos == -1) { 728 continue; 729 } 731 /* Now process minimal element in this buffer. */ 732 for (; (qp->buffer[qp->pos] == min_dbl) && 733 (qp->pos < quantile_k[seq]); 734 qp->pos++) { 736 /* We run this loop `qp->weight' times. 737 * We check there if we are in a position 738 * so we have to save this element in our 739 * output buffer. */ 740 for (j = 0; j < qp->weight; j++) { 742 if (next_pos == merge_pos) { 743 quantile_buf[seq][i] = min_dbl; 744 i++; 746 if (i == quantile_k[seq]) { 747 /* We have written 748 * all elements to 749 * output buffer, so 750 * exit global loop. */ 751 goto out; 752 } 754 /* Update next position. */ 755 next_pos += weight; 756 } 758 merge_pos++; 759 } /* for(j = 0; j < qp->weight; j++) */ 760 } /* for (; (qp->buffer[qp->pos] == min_dbl) && 761 (qp->pos < quantile_k[seq]); qp->pos++) */ 762 } /* for (qp = quantile_buffer_head[seq]; qp!=NULL; 763 qp = qp->next) */ 765 } /* for (i = 0; i < quantile_k[seq]; ) */ 767 out: 768 memcpy(qp_out->buffer, quantile_buf[seq], 769 sizeof(double) * quantile_k[seq]); 771 /* Update weight of output buffer. */ 772 qp_out->weight = weight; 773 qp_out->level = level+1; 775 /* Update list of empty buffers. */ 776 for (qp = quantile_buffer_head[seq]; qp != NULL; qp = qp->next) { 777 if ((qp->pos != -1) && (qp != qp_out)) { 778 qp->weight = 0; 779 qp->level = 0; 780 } 781 } 782 quantile_empty_buffers[seq] += num_buffers - 1; 783 return 0; 784 } 786 /** 787 * Implementation of COLLAPSE policies from section 3.4 of paper 788 * [1]. 789 * 790 * There are three different algorithms noted in the paper. We use 791 * the "New Algorithm". 792 * 793 * @param seq Sequence index. 794 * 795 * @return 796 * @retval 0 on success. 797 * @retval -1 quantiles not initialized. 798 * @retval -2 need an empty buffer for new operation. 799 * @retval -3 bad input sequence length in new operation. 800 * @retval -4 not enough buffers for collapse operation. 801 **/ 802 int 803 quantile_algorithm (uint16_t seq, double *input, int k) 804 { 805 int rc; 806 quantile_t *qp = NULL, *qp2 = NULL; 807 int min_level = -1; 809 /* This should always be true. */ 810 if (quantile_buffer_head[seq] != NULL) { 811 min_level = quantile_buffer_head[seq]->level; 812 } else { 813 return -1; 814 } 816 /* Get minimum level of all currently full buffers. */ 817 for (qp = quantile_buffer_head[seq]; qp != NULL; qp = qp->next) { 818 if (qp->weight != 0) { 819 /* Full buffer. */ 820 min_level = min(min_level, qp->level); 821 } 822 } 824 if (quantile_empty_buffers[seq] == 0) { 825 /* There are no empty buffers. Invoke COLLAPSE on the set 826 * of buffers with minimum level. */ 828 rc = quantile_collapse(seq, min_level); 829 if (rc < 0) 830 return rc; 831 } else if (quantile_empty_buffers[seq] == 1) { 832 /* We have exactly one empty buffer. Invoke NEW and assign 833 * it level `min_level'. */ 835 /* Search the empty buffer. */ 836 for (qp = quantile_buffer_head[seq]; qp != NULL; 837 qp = qp->next) { 838 if (qp->weight == 0) { 839 /* Found empty buffer. */ 840 break; 841 } 842 } 844 rc = quantile_new(seq, qp, input, k, min_level); 845 if (rc < 0) 846 return rc; 847 } else { 848 /* There are at least two empty buffers. Invoke NEW on each 849 * and assign level `0' to each. */ 851 /* Search for two empty buffers. */ 852 for (qp = quantile_buffer_head[seq]; qp != NULL; 853 qp = qp->next) { 854 if (qp->weight == 0) { 855 /* Found first empty buffer. */ 856 break; 857 } 858 } 859 for (qp2 = qp->next; qp2 != NULL; qp2 = qp2->next) { 860 if (qp2->weight == 0) { 861 /* Found second empty buffer. */ 862 break; 863 } 864 } 866 if (k <= quantile_k[seq]) { 867 /* This could happen if we call this after we 868 * received all packets but don't have enough to 869 * fill up two buffers. */ 871 rc = quantile_new(seq, qp, input, k, 0); 872 if (rc < 0) 873 return rc; 874 } else { 875 /* We have enough input data for two buffers. */ 876 rc = quantile_new(seq, qp, input, quantile_k[seq], 0); 877 if (rc < 0) 878 return rc; 879 rc = quantile_new(seq, qp2, input + quantile_k[seq], 880 k - quantile_k[seq], 0); 881 if (rc < 0) 882 return rc; 883 } 884 } 885 return 0; 886 } 888 int 889 quantile_init_seq(uint16_t seq) 890 { 891 quantile_t *qp = NULL; 892 int i; 894 if ( seq >= quantile_max_seq) 895 return -5; 897 /* Allocate memory for quantile buffers. Buffers are linked 898 * lists with a pointer to next buffer. We need `quantile_b' 899 * buffers, where each buffer has space for `quantile_k' 900 * elements. */ 901 for (i = 0; i < quantile_b[seq]; i++) { 902 if (i == 0) { 903 /* Initialize first buffer. */ 904 qp = malloc(sizeof(quantile_t)); 905 if (qp == NULL) { 906 return -1; 907 } 908 quantile_buffer_head[seq] = qp; 910 } else { 911 qp->next = malloc(sizeof(quantile_t)); 912 if (qp->next == NULL) { 913 return -1; 914 } 915 qp = qp->next; 916 } 918 /* `qp' points to buffer that should be initialized. */ 919 qp->next = NULL; 920 qp->weight = 0; /* empty buffers have weight of 0 */ 921 qp->level = 0; 922 qp->buffer = malloc(sizeof(double) * quantile_k[seq]); 923 if (qp->buffer == NULL) { 924 return -1; 925 } 926 } 927 /* Update number of empty quantile buffers. */ 928 quantile_empty_buffers[seq] = quantile_b[seq]; 930 return 0; 931 } 933 int 934 quantile_init (uint16_t max_seq, double eps, uint64_t N) 935 { 936 int b, b_tmp = 0; 937 int k, k_tmp = 0; 938 int h, h_max = 0; 939 int seq, rc; 941 quantile_max_seq = max_seq; 942 /* Allocate array for the requested number of sequences. */ 943 quantile_k = calloc(max_seq, sizeof(int)); 944 quantile_input = calloc(max_seq, sizeof(double*)); 945 quantile_input_cnt = calloc(max_seq, sizeof(int)); 946 quantile_empty_buffers = calloc(max_seq, sizeof(int)); 947 quantile_b = calloc(max_seq, sizeof(int)); 948 quantile_buf = calloc(max_seq, sizeof(double*)); 949 quantile_alternate = calloc(max_seq, sizeof(int)); 950 quantile_inf_cnt = calloc(max_seq, sizeof(uint64_t)); 951 quantile_buffer_head = calloc(max_seq, sizeof(quantile_t*)); 953 /* "In practice, optimal values for b and k can be computed by 954 * trying out different values of b in the range 1 and 30." */ 955 for (b = 2; b <= 30; b++) { 956 /* For each b, compute the largest integral h that 957 * satisfies: 959 * (h-2) * C(b+h-2, h-1) - C(b+h-3, h-3) + 960 * C(b+h-3, h-2) <= 2 * eps * N 961 */ 962 for (h = 0; ; h++) { 963 if (((h-2) * binomial(b+h-2, h-1) - 964 binomial(b+h-3, h-3) + 965 binomial(b+h-3, h-2)) > 966 (2 * eps * N)) { 967 /* This h does not satisfy the inequality from 968 * above. */ 969 break; 970 } 971 h_max = h; 972 } 974 /* Now compute the smallest integral k that satisfies: 975 * k * C(b+h-2, h-1) => N. */ 976 k = ceil(N / (double)binomial(b+h_max-2, h_max-1)); 978 /* Identify that b that minimizes b*k. */ 979 if ((b_tmp == 0) && (k_tmp == 0)) { 980 /* Initialize values */ 981 b_tmp = b; 982 k_tmp = k; 983 } 985 if ((b * k) < (b_tmp * k_tmp)) { 986 /* Found b and k for which the product is smaller than 987 * for the ones before. Because we want to minimize 988 * b*k (required memory), we save them. */ 989 b_tmp = b; 990 k_tmp = k; 991 } 992 } 994 /* Set global quantile values. For now, all sequences share 995 the same k and b values.*/ 996 for (seq = 0; seq < max_seq; seq++ ) { 997 quantile_b[seq] = b_tmp; 998 quantile_k[seq] = k_tmp; 999 } 1001 /* Allocate memory for input buffer. We allocate enough space 1002 * to save up to `2 * quantile_k' elements. This space is 1003 * needed in the COLLAPSE policy if there are more than two 1004 * empty buffers. Because then we have to invoke NEW on two 1005 * buffers and thus need an input buffer with `2 * quantile_k' 1006 * elements. */ 1008 for (seq = 0; seq < quantile_max_seq; seq++) { 1009 quantile_input[seq] = malloc(sizeof(double) * 2 * 1010 quantile_k[seq]); 1011 if (quantile_input[seq] == NULL) { 1012 return -1; 1013 } 1014 quantile_input_cnt[seq] = 0; 1015 } 1017 /* Allocate memory for output buffer. This buffer is used in 1018 * COLLAPSE to store temporary output buffer before it gets 1019 * copied to one of the buffers used in COLLAPSE. */ 1020 for (seq = 0; seq < quantile_max_seq; seq++ ) { 1021 quantile_buf[seq] = malloc(sizeof(double) * quantile_k[seq]); 1022 if (quantile_buf[seq] == NULL) { 1023 return -1; 1024 } 1025 } 1027 for (seq = 0; seq < max_seq; seq++) { 1028 rc = quantile_init_seq(seq); 1029 if (rc < 0) 1030 return rc; 1031 } 1033 return 0; 1034 } 1036 int 1037 quantile_value_checkin(uint16_t seq, double value) 1038 { 1039 int rc = 0; 1041 if ( seq >= quantile_max_seq) 1042 return -5; 1044 quantile_input[seq][quantile_input_cnt[seq]++] = value; 1046 /* If we have at least two empty buffers, 1047 * we need input for two buffers, to twice 1048 * the value of `quantile_k'. */ 1049 if (quantile_empty_buffers[seq] >= 2) { 1050 if (quantile_input_cnt[seq] == 1051 (2 * quantile_k[seq])) { 1052 rc = quantile_algorithm(seq, quantile_input[seq], 1053 quantile_input_cnt[seq]); 1054 /* Reset counter. */ 1055 quantile_input_cnt[seq] = 0; 1057 } 1058 } else { 1059 /* There are 0 or 1 empty buffers */ 1060 if (quantile_input_cnt[seq] == quantile_k[seq]) { 1061 rc = quantile_algorithm(seq, quantile_input[seq], 1062 quantile_input_cnt[seq]); 1063 /* Reset counter. */ 1064 quantile_input_cnt[seq] = 0; 1065 } 1066 } 1067 return rc; 1068 } 1070 int 1071 quantile_finish(uint16_t seq) 1072 { 1073 int rc = 0; 1075 if ( seq >= quantile_max_seq) 1076 return -5; 1078 if (quantile_input_cnt[seq] > 0) { 1079 rc = quantile_algorithm(seq, quantile_input[seq], 1080 quantile_input_cnt[seq]); 1081 } 1082 return rc; 1083 } 1085 void 1086 quantile_reset(uint16_t seq) 1087 { 1088 quantile_input_cnt[seq] = 0; 1089 quantile_empty_buffers[seq] = quantile_b[seq]; 1090 memset(quantile_buf[seq],0,sizeof(double) * quantile_k[seq]); 1091 memset(quantile_input[seq],0,sizeof(double) * quantile_k[seq]); 1092 } 1094 /** 1095 * Deinitialize one quantile sequence. 1096 **/ 1097 void 1098 quantile_exit_seq(uint16_t seq) 1099 { 1100 quantile_t *qp = NULL, *next; 1102 if (seq >= quantile_max_seq) 1103 return; 1105 qp = quantile_buffer_head[seq]; 1106 while (qp != NULL) { 1107 /* Save pointer to next buffer. */ 1108 next = qp->next; 1110 /* Free buffer and list entry. */ 1111 free(qp->buffer); 1112 free(qp); 1114 /* Set current buffer to next one. */ 1115 qp = next; 1116 } 1118 quantile_buffer_head[seq] = NULL; 1119 quantile_input_cnt[seq] = 0; 1120 quantile_empty_buffers[seq] = quantile_b[seq]; 1121 } 1123 void 1124 quantile_exit(void) 1125 { 1126 int seq; 1128 /* Free per sequence structures */ 1129 for (seq = 0; seq < quantile_max_seq; seq++) { 1130 quantile_exit_seq(seq); 1132 /* Free output buffer. */ 1133 free(quantile_buf[seq]); 1135 /* Free input buffer. */ 1136 free(quantile_input[seq]); 1137 } 1139 free(quantile_buffer_head); 1140 free(quantile_inf_cnt); 1141 free(quantile_alternate); 1142 free(quantile_buf); 1143 free(quantile_b); 1144 free(quantile_empty_buffers); 1145 free(quantile_input_cnt); 1146 free(quantile_input); 1147 free(quantile_k); 1148 } 1150 int 1151 quantile_output (uint16_t seq, uint64_t npackets, double phi, 1152 double *result) 1154 { 1155 quantile_t *qp = NULL; 1156 int num_buffers = 0; 1157 int weight = 0; 1158 int j; 1159 long next_pos = 0; 1160 long merge_pos = 0; 1161 double min_dbl; 1162 double beta; 1163 double phi2; /* this is phi' */ 1165 if ( seq >= quantile_max_seq) 1166 return -5; 1168 /* Check that there are at least two full buffers with given 1169 * level. */ 1170 for (qp = quantile_buffer_head[seq]; qp != NULL; qp = qp->next) { 1171 if (qp->weight != 0) { 1172 num_buffers++; 1173 weight += qp->weight; 1174 qp->pos = 0; 1175 } else { 1176 qp->pos = -1; 1177 } 1178 } 1179 if (num_buffers < 2) { 1180 /* XXX: In section 3.3 "OUTPUT operation" of paper [1] is 1181 * says that OUTPUT takes c => 2 full input buffers. But 1182 * what if we just have one full input buffer? 1183 * 1184 * For example this happens if you run a UDP test with a 1185 * block size of 100k and a test duration of 3 seconds: $ 1186 * ./thrulay -u 100k -t 3 localhost 1187 */ 1189 if (num_buffers != 1) { 1190 return -1; 1191 } 1192 } 1194 /* Calculate beta and phi' */ 1195 beta = 1 + quantile_inf_cnt[seq] / (double)npackets; 1196 assert(beta >= 1.0); 1198 assert(phi >= 0.0 && phi <= 1.0); 1199 phi2 = (2 * phi + beta - 1) / (2 * beta); 1201 next_pos = ceil(phi2 * quantile_k[seq] * weight); 1202 /* XXX: If the client just sends a few packets, it is possible 1203 * that next_pos is too large. If this is the case, decrease 1204 * it. */ 1205 if (next_pos >= (num_buffers * quantile_k[seq])) { 1206 next_pos --; 1207 } 1209 while (1) { 1211 /* Search for current minimal element in all buffers. 1212 * Because buffers are all sorted, we just have to check 1213 * the element at current position. */ 1214 min_dbl = DBL_MAX; 1215 for (qp = quantile_buffer_head[seq]; qp != NULL; 1216 qp = qp->next) { 1217 /* Skip wrong buffers. */ 1218 if (qp->pos == -1) { 1219 continue; 1220 } 1222 /* Check that we are not at the end of buffer. */ 1223 if (qp->pos >= quantile_k[seq]) { 1224 continue; 1225 } 1227 /* Update minimum element. */ 1228 min_dbl = min(min_dbl, qp->buffer[qp->pos]); 1229 } 1231 /* Now process this minimal element in all buffers. */ 1232 for (qp = quantile_buffer_head[seq]; qp != NULL; 1233 qp = qp->next) { 1234 /* Skip wrong buffers. */ 1235 if (qp->pos == -1) { 1236 continue; 1237 } 1239 /* Now process minimal element in this buffer. */ 1240 for (; (qp->buffer[qp->pos] == min_dbl) && 1241 (qp->pos < quantile_k[seq]); 1242 qp->pos++) { 1244 /* Increment merge position `qp->weight' 1245 * times. If we pass the position we seek, 1246 * return current minimal element. */ 1247 for (j = 0; j < qp->weight; j++) { 1248 if (next_pos == merge_pos) { 1249 *result = min_dbl; 1250 return 0; 1251 } 1252 merge_pos++; 1253 } 1254 } 1255 } 1256 } 1258 /* NOTREACHED */ 1259 } 1261 #ifdef THRULAY_REPORTING_SAMPLE_LOOP 1263 #include 1264 #include 1266 #ifndef NAN 1267 #define _ISOC99_SOURCE 1268 #include 1269 #endif 1271 #define ERR_FATAL 0 1272 #define ERR_WARNING 1 1274 void __attribute__((noreturn)) 1275 quantile_alg_error(int rc) 1276 { 1277 switch (rc) { 1278 case -1: 1279 fprintf(stderr, "Error: quantiles not initialized."); 1280 break; 1281 case -2: 1282 fprintf(stderr, "Error: NEW needs an empty buffer."); 1283 break; 1284 case -3: 1285 fprintf(stderr, "Error: Bad input sequence length."); 1286 break; 1287 case -4: 1288 fprintf(stderr, "Error: Not enough buffers for COLLAPSE."); 1289 break; 1290 default: 1291 fprintf(stderr, "Error: Unknown quantile_algorithm error."); 1292 } 1293 exit(1); 1294 } 1296 /** 1297 * Will read a sample data file (first and only parameter) whose 1298 * lines give two values per line (per received packet): measured 1299 * packet delay and packet sequence number (in "%lf %lu" 1300 * format). As an exception, the first line specifies the number 1301 * of packets actually sent. Example: 1302 * ---- 1303 10 1304 0.101 0 1305 0.109 1 1306 0.12 1 1307 0.10 3 1308 0.14 4 1309 0.15 5 1310 0.13 2 1311 0.09 6 1312 0.1 8 1313 0.091 7 1314 * ---- 1315 * 1316 * To compile this sample reporting main(): 1317 * 1318 * gcc -std=c99 -DTHRULAY_REPORTING_SAMPLE_LOOP reporting.c -lm 1319 * 1320 **/ 1321 int 1322 main(int argc, char *argv[]) 1323 { 1324 FILE *sf; 1325 /* 'Measured data' */ 1326 const int max_packets = 65535; 1327 /* 'Received' packets*/ 1328 int npackets = 0; 1329 uint64_t packet_sqn[max_packets]; /* Fill in with sample data */ 1330 double packet_delay[max_packets]; /* Fill in with sample data */ 1331 uint64_t packets_sent = 0; /* Fill in with sample data */ 1332 /* reordering */ 1333 const uint64_t reordering_max = 100; 1334 char buffer_reord[reordering_max * 80]; 1335 size_t r = 0; 1336 uint64_t j = 0; 1337 /* Stats */ 1338 uint64_t unique_packets = 0, packets_dup = 0; 1339 double quantile_25, quantile_50, quantile_75; 1340 double delay, jitter; 1341 double packet_loss; 1342 char report_buffer[1000]; 1343 /* Auxiliary variables */ 1344 int i, rc, rc2, rc3; 1345 memset(packet_sqn,0,sizeof(uint64_t)*max_packets); 1346 memset(packet_delay,0,sizeof(double)*max_packets); 1348 /* Inititalize duplication */ 1349 rc = duplication_init(max_packets); 1350 if (-1 == rc) { 1351 perror("calloc"); 1352 exit(1); 1353 } 1355 /* Initialize quantiles */ 1356 rc = quantile_init(1, QUANTILE_EPS, max_packets); 1357 if (-1 == rc) { 1358 perror("malloc"); 1359 exit(1); 1360 } 1362 /* Initialize reordering */ 1363 rc = reordering_init(reordering_max); 1364 if (-1 == rc) { 1365 perror("calloc"); 1366 exit(1); 1367 } 1369 /* Open sample file */ 1370 if (2 == argc) { 1371 sf = fopen(argv[1],"r"); 1372 } else { 1373 fprintf(stderr, "no input file\n"); 1374 exit(1); 1375 } 1377 /* Process sample input file. */ 1379 /* The sender somehow tells the receiver how many packets were 1380 actually sent. */ 1381 fscanf(sf,"%lu",&packets_sent); 1383 for (i = 0; i < max_packets && !feof(sf); i++) { 1385 fscanf(sf,"%lf %lu",&packet_delay[i],&packet_sqn[i]); 1386 npackets++; 1388 /* 1389 * Duplication 1390 */ 1391 if (duplication_check(packet_sqn[i])) { 1392 /* Duplicated packet */ 1393 packets_dup++; 1394 continue; 1395 } else { 1396 /* Unique packet */ 1397 unique_packets++; 1398 } 1400 /* 1401 * Delay quantiles. 1402 */ 1403 rc = quantile_value_checkin(0, packet_delay[i]); 1404 if (rc < 0) 1405 quantile_alg_error(rc); 1407 /* 1408 * Reordering 1409 */ 1410 reordering_checkin(packet_sqn[i]); 1411 } 1413 /* 1414 * Perform last algorithm operation with a possibly not full 1415 * input buffer. 1416 */ 1417 rc = quantile_finish(0); 1418 if (rc < 0) 1419 quantile_alg_error(rc); 1421 rc = quantile_output(0, unique_packets, 0.25, &quantile_25); 1422 rc2 = quantile_output(0, unique_packets, 0.50, &quantile_50); 1423 rc3 = quantile_output(0, unique_packets, 0.75, &quantile_75); 1424 if (-1 == rc || -1 == rc2 || -1 == rc3) { 1425 fprintf(stderr,"An error occurred while computing delay " 1426 "quantiles. %d %d %d\n",rc, rc2, rc3); 1427 exit(1); 1428 } 1430 /* Delay and jitter computation */ 1431 packet_loss = packets_sent > unique_packets? 1432 (100.0*(packets_sent - unique_packets))/packets_sent: 0; 1433 delay = (packet_loss > 50.0)? INFINITY : quantile_50; 1434 if (packet_loss < 25.0 ) { 1435 jitter = quantile_75 - quantile_25; 1436 } else if (packet_loss > 75.0) { 1437 jitter = NAN; 1438 } else { 1439 jitter = INFINITY; 1440 } 1441 /* Format final report */ 1442 snprintf(report_buffer, sizeof(report_buffer), 1443 "Delay: %3.3fms\n" 1444 "Loss: %3.3f%%\n" 1445 "Jitter: %3.3fms\n" 1446 "Duplication: %3.3f%%\n" 1447 "Reordering: %3.3f%%\n", 1448 1000.0 * delay, 1449 packet_loss, 1450 1000.0 * jitter, 1451 100 * (double)packets_dup/npackets, 1452 100.0 * reordering_output(0)); 1454 printf("%s", report_buffer); 1456 /* Deallocate resources for statistics. */ 1457 reordering_exit(); 1458 quantile_exit(); 1459 duplication_exit(); 1461 fclose(sf); 1463 exit(0); 1464 } 1466 #endif /* THRULAY_REPORTING_SAMPLE_LOOP */ 1468 Appendix B. Example Report 1470 This appendix only serves for illustrative purposes. 1472 This report is produced by running the sample program in Appendix A 1473 on the sample input embedded in a comment in its source code: 1475 Delay: 109.000ms 1476 Loss: 10.000% 1477 Jitter: 40.000ms 1478 Duplication: 18.182% 1479 Reordering: 25.000% 1481 Appendix C. TODO 1483 FIXME: This section needs to be removed before publication. 1485 o Add references 1487 Appendix D. Revision History 1489 FIXME: This section needs to be removed before publication. 1491 $Log: draft-ietf-ippm-reporting.xml,v $ 1492 Revision 1.8 2006/10/23 21:45:54 shalunov 1493 draft-ietf-ippm-reporting-01.txt 1495 Revision 1.7 2006/10/23 21:45:13 shalunov 1496 Add sample source code and output. 1498 Revision 1.6 2006/06/02 21:21:57 shalunov 1499 draft-ietf-ippm-reporting-00: Include a ``Scope'' section. 1500 Change tags from draft-shalunov-ippm-reporting. 1502 Revision 1.5 2006/05/02 20:25:44 shalunov 1503 Version 03: Various refinements and clarifications based on feedback 1504 from Reza Fardid, Ruediger Geib, and Al Morton. 1506 Revision 1.4 2006/04/25 22:38:58 shalunov 1507 Version 02: Address comments from Carsten Schmoll, sent in message 1508 70524A4436C03E43A293958B505008B61B9CFB@EXCHSRV.fokus.fraunhofer.de. 1509 My response, with clarifications and diffs, is in message 1510 8664kxwazk.fsf@abel.internet2.edu. 1512 Revision 1.3 2006/04/11 22:09:47 shalunov 1513 Version 01: Wording changes based on discussion with Matt Zekauskas 1514 (reordering, loss). Rewrite abstract a bit. Add TODO list. 1516 Revision 1.2 2006/04/04 21:39:20 shalunov 1517 Convert to xml2rfc 1.30 and RFC 3978 IPR statement. 1519 Revision 1.1.1.1 2006/04/02 17:07:36 shalunov 1520 Initial import into CVS. 1522 Authors' Addresses 1524 Stanislav Shalunov 1526 Email: shalunov@shlang.com 1527 URI: http://shlang.com/ 1529 Martin Swany 1530 University of Delaware 1531 Department of Computer and Information Sciences 1532 Newark, DE 19716 1533 US 1535 Email: swany@cis.udel.edu 1536 URI: http://www.cis.udel.edu/~swany/ 1538 Full Copyright Statement 1540 Copyright (C) The IETF Trust (2008). 1542 This document is subject to the rights, licenses and restrictions 1543 contained in BCP 78, and except as set forth therein, the authors 1544 retain all their rights. 1546 This document and the information contained herein are provided on an 1547 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1548 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 1549 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 1550 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 1551 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1552 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1554 Intellectual Property 1556 The IETF takes no position regarding the validity or scope of any 1557 Intellectual Property Rights or other rights that might be claimed to 1558 pertain to the implementation or use of the technology described in 1559 this document or the extent to which any license under such rights 1560 might or might not be available; nor does it represent that it has 1561 made any independent effort to identify any such rights. Information 1562 on the procedures with respect to rights in RFC documents can be 1563 found in BCP 78 and BCP 79. 1565 Copies of IPR disclosures made to the IETF Secretariat and any 1566 assurances of licenses to be made available, or the result of an 1567 attempt made to obtain a general license or permission for the use of 1568 such proprietary rights by implementers or users of this 1569 specification can be obtained from the IETF on-line IPR repository at 1570 http://www.ietf.org/ipr. 1572 The IETF invites any interested party to bring to its attention any 1573 copyrights, patents or patent applications, or other proprietary 1574 rights that may cover technology that may be required to implement 1575 this standard. Please address the information to the IETF at 1576 ietf-ipr@ietf.org.