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