idnits 2.17.1 draft-ietf-ippm-reporting-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** The document seems to lack a License Notice according IETF Trust Provisions of 28 Dec 2009, Section 6.b.i or Provisions of 12 Sep 2009 Section 6.b -- however, there's a paragraph with a matching beginning. Boilerplate error? (You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Feb 2009 rather than one of the newer Notices. See https://trustee.ietf.org/license-info/.) 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 and authors Copyright Line does not match the current year -- The document seems to contain a disclaimer for pre-RFC5378 work, and may have content which was first submitted before 10 November 2008. The disclaimer is necessary when there are original authors that you have been unable to contact, or if some do not wish to grant the BCP78 rights to the IETF Trust. If you are able to get all authors (current and original) to grant those rights, you can and should remove the disclaimer; otherwise, the disclaimer is needed and you can ignore this comment. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (March 9, 2009) is 5527 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 1420 -- Looks like a reference, but probably isn't: '1000' on line 1391 == Outdated reference: A later version (-08) exists of draft-ietf-ippm-duplicate-07 ** Obsolete normative reference: RFC 2679 (Obsoleted by RFC 7679) ** Obsolete normative reference: RFC 2680 (Obsoleted by RFC 7680) Summary: 4 errors (**), 0 flaws (~~), 2 warnings (==), 5 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: September 10, 2009 University of Delaware 6 March 9, 2009 8 Reporting IP Performance Metrics to Users 9 draft-ietf-ippm-reporting-03.txt 11 Status of this Memo 13 This Internet-Draft is submitted to IETF in full conformance with the 14 provisions of BCP 78 and BCP 79. This document may contain material 15 from IETF Documents or IETF Contributions published or made publicly 16 available before November 10, 2008. The person(s) controlling the 17 copyright in some of this material may not have granted the IETF 18 Trust the right to allow modifications of such material outside the 19 IETF Standards Process. Without obtaining an adequate license from 20 the person(s) controlling the copyright in such materials, this 21 document may not be modified outside the IETF Standards Process, and 22 derivative works of it may not be created outside the IETF Standards 23 Process, except to format it for publication as an RFC or to 24 translate it into languages other than English. 26 Internet-Drafts are working documents of the Internet Engineering 27 Task Force (IETF), its areas, and its working groups. Note that 28 other groups may also distribute working documents as Internet- 29 Drafts. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 The list of current Internet-Drafts can be accessed at 37 http://www.ietf.org/ietf/1id-abstracts.txt. 39 The list of Internet-Draft Shadow Directories can be accessed at 40 http://www.ietf.org/shadow.html. 42 This Internet-Draft will expire on September 10, 2009. 44 Copyright Notice 46 Copyright (c) 2009 IETF Trust and the persons identified as the 47 document authors. All rights reserved. 49 This document is subject to BCP 78 and the IETF Trust's Legal 50 Provisions Relating to IETF Documents in effect on the date of 51 publication of this document (http://trustee.ietf.org/license-info). 52 Please review these documents carefully, as they describe your rights 53 and restrictions with respect to this document. 55 Abstract 57 The aim of this document is to define a small set of metrics that are 58 robust, easy to understand, orthogonal, relevant, and easy to 59 compute. The IPPM WG has defined a large number of richly 60 parameterized metrics because network measurement has many purposes. 61 Often, the ultimate purpose is to report a concise set of metrics 62 describing a network's state to an end user. It is for this purpose 63 that the present set of metrics is defined. 65 Table of Contents 67 1. Requirements Notation . . . . . . . . . . . . . . . . . . . . 4 68 2. Goals and Motivation . . . . . . . . . . . . . . . . . . . . . 5 69 3. Applicability for Long-Term Measurements . . . . . . . . . . . 7 70 4. Reportable Metrics Set . . . . . . . . . . . . . . . . . . . . 8 71 4.1. Median Delay . . . . . . . . . . . . . . . . . . . . . . . 8 72 4.2. Loss Ratio . . . . . . . . . . . . . . . . . . . . . . . . 8 73 4.3. Delay Spread . . . . . . . . . . . . . . . . . . . . . . . 8 74 4.4. Duplication . . . . . . . . . . . . . . . . . . . . . . . 9 75 4.5. Reordering . . . . . . . . . . . . . . . . . . . . . . . . 9 76 5. Sample Source . . . . . . . . . . . . . . . . . . . . . . . . 10 77 5.1. One-Way Active Measurement . . . . . . . . . . . . . . . . 10 78 5.2. Round-Trip Active Measurement . . . . . . . . . . . . . . 11 79 5.3. Passive Measurement . . . . . . . . . . . . . . . . . . . 11 80 6. Security Considerations . . . . . . . . . . . . . . . . . . . 12 81 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 13 82 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 83 9. Internationalization Considerations . . . . . . . . . . . . . 15 84 10. Normative References . . . . . . . . . . . . . . . . . . . . . 16 85 Appendix A. Sample Source Code for Computing the Metrics . . . . 17 86 Appendix B. Example Report . . . . . . . . . . . . . . . . . . . 41 87 Appendix C. TODO . . . . . . . . . . . . . . . . . . . . . . . . 42 88 Appendix D. Revision History . . . . . . . . . . . . . . . . . . 43 89 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 44 91 1. Requirements Notation 93 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 94 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 95 document are to be interpreted as described in [RFC2119]. 97 2. Goals and Motivation 99 The IPPM working group has defined many richly parameterized 100 performance metrics with a number of variants (one-way delay, one-way 101 loss, delay variation, reordering, etc.) and a protocol for obtaining 102 the measurement data needed to compute these metrics (OWAMP). It 103 would be beneficial to define a standard way to report a set of 104 performance metrics to end users. Parameterization might be 105 acceptable in such a set, but there must still be defaults for 106 everything. It is especially important to get these defaults right. 107 Such a set would enable different tools to produce results that can 108 be compared against each other. 110 Existing tools already report statistics about the network. This is 111 done for varying reasons: network testing tools, such as the ping 112 program available in UNIX-derived operating systems as well as in 113 Microsoft Windows, report statistics with no knowledge of why the 114 user is running the program; networked games might report statistics 115 of the network connection to the server so users can better 116 understand why they get the results they get (e.g., if something is 117 slow, is this because of the network or the CPU?), so they can 118 compare their statistics to those of others ("you're not lagged any 119 more than I am") or perhaps so that users can decide whether they 120 need to upgrade the connection to their home; IP telephony hardware 121 and software might report the statistics for similar reasons. While 122 existing tools report statistics, the particular set of metrics they 123 choose is ad hoc; some metrics are not statistically robust, some are 124 not relevant, and some are not easy to understand; more important 125 than specific shortcomings, however, is the incompatibility: even if 126 the sets of metrics were perfect, they would still be all different, 127 and, therefore, metrics reported by different tools would not be 128 comparable. 130 The set of metrics of this document is meant for human consumption. 131 It must therefore be small. A screen full of numbers is likely to be 132 too confusing. Restricting output to a single number would likewise 133 not be descriptive enough. (Would you pick loss? delay? throughput? 134 something else?) In this document we aim for a "handful" of numbers. 136 Each of the metrics must be statistically robust. Intuitively, this 137 means that having a small number of bad data points and a small 138 amount of noise must not dramatically change the metric. 140 Each metric in the set must have, qualitatively, an immediate 141 intuitive meaning that has to be obvious for an advanced end user 142 without consulting documentation (that is, it has to be clear what 143 rough meaning, intuitively, the larger values of a given metric 144 have). 146 To be small, the set has to be orthogonal: each of the metrics has to 147 express a property not covered by other metrics (otherwise, there's 148 redundancy). 150 The metrics in the set must be relevant. Partly, being easy to 151 understand will help achieve this, but additional constraint may be 152 placed by relevancy. 154 Finally, while this set will most frequently be computed for small 155 data sets, where efficiency is not a serious consideration, it must 156 be possible to compute for large data sets, too. In particular, it 157 must be possible to compute the metrics in a single pass over the 158 data using a limited amount of memory (i.e., it must be possible to 159 take a source of measurement data with a high data rate and compute 160 the metrics on the fly, discarding each data point after it is 161 processed). 163 3. Applicability for Long-Term Measurements 165 The metrics in this document are most applicable to short-term 166 network measurements (seconds or at most minutes) and are targeted 167 for real-time display of such measurements. 169 One consideration that would have to be addressed to make these 170 metrics suitable for longer-term measurements (hours and days) is 171 that of network availability: during such long periods of time the 172 network may be completely down for some time and it does not seem to 173 make sense to average out the reports in such a way that the network 174 being down for 1% of the time becomes 1% packet loss. 176 4. Reportable Metrics Set 178 The following metrics comprise the set: 180 1. median delay; 182 2. loss ratio; 184 3. delay spread; 186 4. duplication; 188 5. reordering. 190 Each of the above is represented by a single numeric quantity, 191 computed as described below. 193 4.1. Median Delay 195 The reported median delay is the median of all delays in the sample. 196 When a packet is lost, its delay is to be considered +infinity for 197 the purposes of this computation; therefore, if more than half of all 198 packets are lost, the delay is +infinity. 200 For more information, refer to section 5.2 (Type-P-One-way-Delay- 201 Median) of RFC 2679 [RFC2679] (A One-way Delay Metric for IPPM), and 202 supporting text. 204 4.2. Loss Ratio 206 Loss Ratio is the fraction, expressed as a percentile, of packets 207 that did not arrive intact within a given number of seconds (the 208 timeout value) after being sent. Since this set of metrics often has 209 to be reported to a waiting human user, the default timeout value 210 should be small. By default, 2 seconds MUST be the timeout value. 211 Use of a different timeout value MUST be reported. 213 For more information, refer to Section 4.1 (Type-P-One-way-Packet- 214 Loss-Average) of RFC 2680 [RFC2680] (A One-way Packet Loss Metric for 215 IPPM). The Loss Ratio is 100*Type-P-One-way-Packet-Loss-Average. 217 4.3. Delay Spread 219 Delay spread is the interquartile spread of observed delays. This is 220 a metric to represent what is commonly referred to as "jitter". 221 Delay spread is reported as the difference of the 75th and 25th 222 percentiles of delay. When both percentiles are +infinity, the value 223 of delay spread is undefined. Therefore, if less than 25% of packets 224 are lost, it is defined and finite; if between 75% and 25% of packets 225 are lost, it is +infinity; finally, if more than 75% of packets are 226 lost, it is undefined. 228 For more information, refer to section 5.1 (Type-P-One-way-Delay- 229 Percentile) of RFC 2679 [RFC2679] (A One-way Delay Metric for IPPM), 230 and supporting text. The Delay Spread is the 75th Type-P-One-way- 231 Delay-Percentile minus the 25th Type-P-One-way-Delay-Percentile. 233 4.4. Duplication 235 Duplication is the fraction of transmitted packets for which more 236 than a single copy of the packet was received within the timeout 237 period (ideally using the same timeout as in the definition of loss), 238 expressed in percentage points. 240 Note: while most received packets can be ones previously seen, 241 duplication can never exceed 100%. 243 For more information, see section 5.2 (Type-P-one-way-replicated- 244 packet-rate) of RFC TBD-duplicate [I-D.ietf-ippm-duplicate] (A One- 245 Way Packet Duplication Metric). Duplication is 100*Type-P-one-way- 246 replicated-packet-rate. 248 4.5. Reordering 250 Reordering is the fraction of sent packets for which the sequence 251 number of the packet received immediately before the first copy of 252 the given packet is not the decrement of the sequence number of the 253 given packet. For the purposes of determining the sequence number of 254 the preceding packet in this definition, assuming sequence numbers 255 starting with 1, an extra packet at the start of the stream of 256 received packets, with a sequence number of 0, is considered to be 257 present (this extra packet, of course, is not counted for the 258 purposes of computing the fraction). 260 FIXME: References. 262 5. Sample Source 264 Section 4 describes the metrics to compute on a sample of 265 measurements. The source of the sample in not discussed there, and, 266 indeed, the metrics discussed (delay, loss, etc.) are simply 267 estimators that could be applied to any sample whatsoever. For the 268 names of the estimators to be applicable, of course, the measurements 269 need to come from a packet delivery network. 271 The data in the samples for the set of metrics discussed in this 272 document can come from the following sources: one-way active 273 measurement, round-trip measurement, and passive measurement. There 274 infrequently is a choice between active and passive measurement, as, 275 typically, only one is available; consequently, no preference is 276 given to one over the other. In cases where clocks can be expected 277 to be synchronized, in general, one-way measurements are preferred 278 over round-trip measurements (as one-way measurements are more 279 informative). When one-way measurements cannot be obtained, or when 280 clocks cannot be expected to be synchronized, round-trip measurement 281 MAY be used. 283 5.1. One-Way Active Measurement 285 The default duration of the measurement interval is 10 seconds. 287 The default sending schedule is a Poisson stream. 289 The default sending rate is 10 packets/second on average. The 290 default sending schedule is a Poisson stream. When randomized 291 schedules, such as a Poisson stream, are used, the rate MUST be set 292 with the distribution parameter(s). With a randomized schedule, the 293 default sample size is 100 packets and the measurement window 294 duration can vary to some extent depending on the values of the 295 (pseudo-)random deviates. 297 The default packet size is the minimum necessary for the measurement. 299 Values other than the default ones MAY be used; if they are used, 300 their use, and specific values used, MUST be reported. 302 A one-way active measurement is characterized by the source IP 303 address, the destination IP address, the time when measurement was 304 taken, and the type of packets (e.g., UDP with given port numbers and 305 a given DSCP) used in the measurement. For the time, the end of the 306 measurement interval MUST be reported. 308 5.2. Round-Trip Active Measurement 310 The same default parameters and characterization apply to round-trip 311 measurement as to one-way measurement (Section 5.1). 313 5.3. Passive Measurement 315 Passive measurement use whatever data it is natural to use. For 316 example, an IP telephony application or a networked game would use 317 the data that it sends. An analysis of performance of a link might 318 use all the packets that traversed the link in the measurement 319 interval. An analysis of performance of an Internet service 320 provider's network might use all the packets that traversed the 321 network in the measurement interval. An analysis of performance of a 322 specific service from the point of view of a given site might use an 323 appropriate filter to select only the relevant packets. In any case, 324 the source needs to be reported. 326 The same default duration applies to passive measurement as to one- 327 way active measurement (Section 5.1). 329 When the passive measurement data is reported in real time, or based 330 on user demand, a sliding window SHOULD be used as a measurement 331 period, so that recent data become more quickly reflected. For 332 historical reporting purposes, a fixed interval may be preferable. 334 6. Security Considerations 336 The reporting per se, not being a protocol, does not raise security 337 considerations. 339 An aspect of reporting relevant to security is how the reported 340 metrics are used and how they are collected. If it is important that 341 the metrics satisfy certain conditions (e.g., that the ISP whose 342 network is being measured be unable to make the metrics appear better 343 than they are), the collection mechanism MUST ensure that this is, 344 indeed, so. The exact mechanisms to do so are outside of scope of 345 this document and belong with discussion of particular measurement 346 data collection protocols. 348 7. Acknowledgments 350 We gratefully acknowledge discussion with, encouragement from, and 351 contributions of Lawrence D. Dunn, Reza Fardid, Ruediger Geib, 352 Matt Mathis, Al Morton, Carsten Schmoll, Henk Uijterwaal, and 353 Matthew J. Zekauskas. 355 8. IANA Considerations 357 This document requires no action from the IANA. 359 9. Internationalization Considerations 361 The reported metrics, while they might occasionally be parsed by 362 machine, are primarily meant for human consumption. As such, they 363 MAY be reported in the language preferred by the user, using an 364 encoding suitable for the purpose, such as UTF-8. 366 10. Normative References 368 [I-D.ietf-ippm-duplicate] 369 Uijterwaal, H., "A One-Way Packet Duplication Metric", 370 draft-ietf-ippm-duplicate-07 (work in progress), 371 January 2009. 373 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 374 Requirement Levels", BCP 14, RFC 2119, March 1997. 376 [RFC2679] Almes, G., Kalidindi, S., and M. Zekauskas, "A One-way 377 Delay Metric for IPPM", RFC 2679, September 1999. 379 [RFC2680] Almes, G., Kalidindi, S., and M. Zekauskas, "A One-way 380 Packet Loss Metric for IPPM", RFC 2680, September 1999. 382 Appendix A. Sample Source Code for Computing the Metrics 384 This appendix only serves for illustrative purposes. 386 /* 387 * reporting.c -- performance metrics reporting as in Internet Draft 388 * draft-ietf-ippm-reporting. 389 * 390 * Written by Stanislav Shalunov, http://www.internet2.edu/~shalunov/ 391 * Bernhard Lutzmann, belu@users.sf.net 392 * Federico Montesino Pouzols, fedemp@altern.org 393 * 394 * This file is also available, under a different (BSD-style) 395 * license, as part of thrulay. 396 */ 398 /** 399 * @file reporting.c 400 * 401 * @short metrics computation and reporting. 402 **/ 404 #include 405 #include 406 #include 407 #include 408 #include 409 #include 411 #define min(a, b) ((a) < (b) ? (a) : (b)) 412 #define max(a, b) ((a) > (b) ? (a) : (b)) 414 /* 415 * Reordering. 416 */ 417 #define loop(x) ((x) >= 0 ? (x) : (x) + (int)reordering_max) 419 /* 420 * Duplication. 421 */ 422 static uint64_t *bitfield = NULL; /* Bit field used to check for 423 duplicated packets. */ 425 /* 426 * Reordering. 427 */ 428 static uint64_t reordering_max; /* We have m[j-1] == number of */ 429 static uint64_t *reordering_m; /* We have m[j-1] == number of 430 j-reordered packets. */ 431 static uint64_t *reordering_ring; /* Last sequence numbers seen */ 432 static int r = 0; /* Ring pointer for next write. */ 433 static int l = 0; /* Counter of sequence numbers. */ 435 /* 436 * Quantiles 437 * 438 * Reference: 439 * 440 * [1] Manku, Rajagopalan, Lindsay: "Approximate Medians and other 441 * Quantiles in One Pass and with Limited Memory", 442 * http://www-db.stanford.edu/~manku/papers/98sigmod-quantiles.pdf 443 */ 445 #define QUANTILE_EPS 0.005 447 static uint16_t quantile_max_seq; /* Maximum number of sequences */ 448 static int *quantile_k; /* number of elements in buffer */ 450 static double **quantile_input; /* This is the buffer where the 451 sequence of incoming packets is 452 saved. If we received enough 453 packets, we will write this 454 buffer to a quantile buffer. */ 455 static int *quantile_input_cnt; /* number of elements in input 456 * buffer */ 457 static int *quantile_empty_buffers; /* number of empty buffers */ 459 static int *quantile_b; /* number of buffers */ 461 static double **quantile_buf; 463 static int *quantile_alternate; /* this is used to determine 464 the offset in COLLAPSE (if 465 weight is even) */ 467 static uint64_t *quantile_inf_cnt; /* this counter is for the 468 additional -inf, +inf 469 elements we added to NEW 470 buffer to fill it up. */ 472 typedef struct quantile { 473 struct quantile *next; /* pointer to next quantile 474 * buffer */ 475 int weight; /* 0 if buffer is empty, > 0 if buffer is 476 * full */ 478 int level; 479 double *buffer; 480 int pos; /* current position in buffer; used in 481 quantile_collapse() */ 482 } quantile_t; 484 static quantile_t **quantile_buffer_head; 486 int 487 reordering_init(uint64_t max) 488 { 489 reordering_max = max; 490 reordering_m = calloc(reordering_max, sizeof(uint64_t)); 491 reordering_ring = calloc(reordering_max, sizeof(uint64_t)); 492 if (reordering_m == NULL) { 493 return -1; 494 } else { 495 return 0; 496 } 497 } 499 int 500 reordering_checkin(uint64_t packet_sqn) 501 { 502 int j; 504 for (j = 0; j < min(l, (int)reordering_max) && 506 packet_sqn < reordering_ring[loop(r-j-1)]; j++) { 507 reordering_m[j]++; 508 } 509 reordering_ring[r] = packet_sqn; 510 l++; 511 r = (r + 1) % reordering_max; 512 return 0; 513 } 515 double 516 reordering_output(uint64_t j) 517 { 518 if (j >= reordering_max) 519 return -1; 520 else 521 return (double)reordering_m[j] / (l - j - 1); 522 } 524 void 525 reordering_exit(void) 526 { 527 free(reordering_ring); 528 free(reordering_m); 529 } 531 int 532 duplication_init(uint64_t npackets) 533 { 534 uint64_t bitfield_len = 0; /* Number of sectors in bitfield */ 536 /* Allocate memory for bit field */ 537 bitfield_len = ((npackets % 64)? 538 (npackets / 64 + 1) : npackets / 64); 539 bitfield = calloc(bitfield_len, sizeof(uint64_t)); 540 if (bitfield == NULL) { 541 return -1; 542 } else { 543 return 0; 544 } 545 } 547 int 548 duplication_check(uint64_t packet_sqn) 549 { 550 uint64_t bitfield_sec; /* Which sector in bitfield */ 551 uint64_t bitfield_bit; /* Which bit in sector */ 553 /* Calculate sector */ 554 bitfield_sec = packet_sqn >> 6; 556 /* Calculate bit in sector */ 557 bitfield_bit = (uint64_t)1 << (packet_sqn & 63); 559 if (bitfield[bitfield_sec] & bitfield_bit) { 560 /* Duplicated packet */ 561 return 1; 562 } else { 563 /* Unique packet */ 564 bitfield[bitfield_sec] |= bitfield_bit; 565 return 0; 566 } 567 } 569 void 570 duplication_exit(void) 571 { 572 free(bitfield); 573 } 574 /* Calculate binomial coefficient C(n, k). */ 575 int64_t 576 binomial (int n, int k) 577 { 578 int64_t bc = 0; 579 int i, m; 581 /* C(n, k) = C(n, n-k) */ 582 k = min(k, n-k); 584 if (k >= 0) { 585 bc = 1; 586 m = max(k, n-k); 588 for (i = 1; i <= k; i++) { 589 bc = (bc * (m + i)) / i; 590 } 591 } 593 return bc; 594 } 596 int 597 quantile_compare(const void *d1, const void *d2) 598 { 599 if (*(double *)d1 < *(double *)d2) { 600 return -1; 601 } else if (*(double *)d1 == *(double *)d2) { 602 return 0; 603 } else { 604 assert(*(double *)d1 > *(double *)d2); 605 return 1; 606 } 607 } 609 void 610 quantile_sort (double *list, int length) 611 { 612 qsort(list, length, sizeof(double), quantile_compare); 613 } 615 /** 616 * Implementation of NEW operation from section 3.1 of paper [1]. 617 * 618 * Takes as input an empty buffer. Simply populates the quantile 619 * buffer with the next k elements from the input sequence, labels 620 * the buffer as full, and assigns it a weight of 1. 621 * 622 * If there are not enough elements to fill up the buffer, we 623 * alternately add -inf, +inf elements until buffer is full (-inf 624 * == 0, +inf == DBL_MAX). 625 * 626 * NOTE: We sort the elements in the input buffer before we copy 627 * them to the quantile buffer. 628 * 629 * @param seq Sequence index. 630 * 631 * @return 632 * @retval 0 on success. 633 * @retval -2 need an empty buffer. 634 * @retval -3 bad input sequence length. 635 **/ 636 int 637 quantile_new(uint16_t seq, quantile_t *q, double *input, int k, 638 int level) 639 { 640 int i; 642 /* Check that buffer is really empty. */ 643 if (q->weight != 0) { 644 return -2; 645 } 647 /* Sanity check for length of input sequence. */ 648 if (k > quantile_k[seq]) { 649 return -3; 650 } 652 /* If there are not enough elements in the input buffer, fill 653 * it up with -inf, +inf elements. */ 654 for (i = k; i < quantile_k[seq]; i++) { 655 if (i % 2) { 656 input[i] = DBL_MAX; 657 } else { 658 input[i] = 0; 659 } 661 /* Increment counter that indicates how many additional 662 * elements we added to fill the buffer. */ 663 quantile_inf_cnt[seq]++; 664 } 666 quantile_sort(input, quantile_k[seq]); 668 memcpy(q->buffer, input, sizeof(double) * quantile_k[seq]); 669 /* Mark buffer as full and set level. */ 670 q->weight = 1; 671 q->level = level; 673 /* Update number of empty quantile buffers. */ 674 quantile_empty_buffers[seq]--; 676 return 0; 677 } 679 /* Implementation of COLLAPSE operation from section 3.2 of paper 680 * [1]. 681 * 682 * This is called from quantile_algorithm() if there are no empty 683 * buffers. We COLLAPSE all the full buffers, where level has 684 * value `level'. Output is written to the first buffer in linked 685 * list with level set to `level'. The level of the output buffer 686 * is increased by 1. All other buffers we used in the COLLAPSE 687 * are marked empty. */ 688 int 689 quantile_collapse(uint16_t seq, int level) 690 { 691 quantile_t *qp = NULL, *qp_out = NULL; 692 int num_buffers = 0; /* number of buffers with level 693 * `level' */ 694 int weight = 0; /* weight of the output buffer */ 695 int offset; 696 int i, j; 697 double min_dbl; 698 long next_pos; 699 long merge_pos = 0; 701 /* Check that there are at least two full buffers with given 702 * level. Also calculate weight of output buffer. */ 703 for (qp = quantile_buffer_head[seq]; qp != NULL; qp = qp->next) { 704 if ((qp->weight != 0) && (qp->level == level)) { 705 num_buffers++; 706 weight += qp->weight; 707 qp->pos = 0; 708 } else { 709 /* We mark the buffers that are not used in this 710 * COLLAPSE. */ 711 qp->pos = -1; 712 } 713 } 714 if (num_buffers < 2) { 715 return -4; 717 } 719 /* NOTE: The elements in full buffers are sorted. So we don't 720 * have to do that again. 721 */ 722 /* Search for first full buffer with matching level. This is 723 * the buffer where we save the output. */ 724 for (qp_out = quantile_buffer_head[seq]; qp_out != NULL; 725 qp_out = qp_out->next) { 726 if (qp_out->pos != -1) { 727 break; 728 } 729 } 731 /* Calculate offset */ 732 if (weight % 2) { 733 /* odd */ 734 offset = (weight + 1) / 2; 735 } else { 736 /* even - we alternate between two choices in each 737 * COLLAPSE */ 738 if (quantile_alternate[seq] % 2) { 739 offset = weight / 2; 740 } else { 741 offset = (weight + 2)/ 2; 742 } 743 quantile_alternate[seq] = (quantile_alternate[seq] + 1) % 2; 744 } 746 /* Initialize next position of element to save. Because first 747 * position is at 0, we have to decrement offset by 1. */ 748 next_pos = offset - 1; 750 for (i = 0; i < quantile_k[seq]; ) { 752 /* Search for current minimal element in all buffers. 753 * Because buffers are all sorted, we just have to check 754 * the element at current position. */ 755 min_dbl = DBL_MAX; 756 for (qp = quantile_buffer_head[seq]; qp != NULL; 757 qp = qp->next) { 758 /* Skip wrong buffers. */ 759 if (qp->pos == -1) { 760 continue; 761 } 763 /* Check that we are not at the end of buffer. */ 764 if (qp->pos >= quantile_k[seq]) { 765 continue; 766 } 768 /* Update minimum element. */ 769 min_dbl = min(min_dbl, qp->buffer[qp->pos]); 770 } 772 /* Now process this minimal element in all buffers. */ 773 for (qp = quantile_buffer_head[seq]; qp != NULL; 774 qp = qp->next) { 775 /* Skip wrong buffers. */ 776 if (qp->pos == -1) { 777 continue; 778 } 780 /* Now process minimal element in this buffer. */ 781 for (; (qp->buffer[qp->pos] == min_dbl) && 782 (qp->pos < quantile_k[seq]); 783 qp->pos++) { 785 /* We run this loop `qp->weight' times. 786 * We check there if we are in a position 787 * so we have to save this element in our 788 * output buffer. */ 789 for (j = 0; j < qp->weight; j++) { 791 if (next_pos == merge_pos) { 792 quantile_buf[seq][i] = min_dbl; 793 i++; 795 if (i == quantile_k[seq]) { 796 /* We have written 797 * all elements to 798 * output buffer, so 799 * exit global loop. */ 800 goto out; 801 } 803 /* Update next position. */ 804 next_pos += weight; 805 } 807 merge_pos++; 808 } /* for(j = 0; j < qp->weight; j++) */ 809 } /* for (; (qp->buffer[qp->pos] == min_dbl) && 810 (qp->pos < quantile_k[seq]); qp->pos++) */ 811 } /* for (qp = quantile_buffer_head[seq]; qp!=NULL; 812 qp = qp->next) */ 814 } /* for (i = 0; i < quantile_k[seq]; ) */ 816 out: 817 memcpy(qp_out->buffer, quantile_buf[seq], 818 sizeof(double) * quantile_k[seq]); 820 /* Update weight of output buffer. */ 821 qp_out->weight = weight; 822 qp_out->level = level+1; 824 /* Update list of empty buffers. */ 825 for (qp = quantile_buffer_head[seq]; qp != NULL; qp = qp->next) { 826 if ((qp->pos != -1) && (qp != qp_out)) { 827 qp->weight = 0; 828 qp->level = 0; 829 } 830 } 831 quantile_empty_buffers[seq] += num_buffers - 1; 832 return 0; 833 } 835 /** 836 * Implementation of COLLAPSE policies from section 3.4 of paper 837 * [1]. 838 * 839 * There are three different algorithms noted in the paper. We use 840 * the "New Algorithm". 841 * 842 * @param seq Sequence index. 843 * 844 * @return 845 * @retval 0 on success. 846 * @retval -1 quantiles not initialized. 847 * @retval -2 need an empty buffer for new operation. 848 * @retval -3 bad input sequence length in new operation. 849 * @retval -4 not enough buffers for collapse operation. 850 **/ 851 int 852 quantile_algorithm (uint16_t seq, double *input, int k) 853 { 854 int rc; 855 quantile_t *qp = NULL, *qp2 = NULL; 856 int min_level = -1; 858 /* This should always be true. */ 859 if (quantile_buffer_head[seq] != NULL) { 860 min_level = quantile_buffer_head[seq]->level; 861 } else { 862 return -1; 863 } 865 /* Get minimum level of all currently full buffers. */ 866 for (qp = quantile_buffer_head[seq]; qp != NULL; qp = qp->next) { 867 if (qp->weight != 0) { 868 /* Full buffer. */ 869 min_level = min(min_level, qp->level); 870 } 871 } 873 if (quantile_empty_buffers[seq] == 0) { 874 /* There are no empty buffers. Invoke COLLAPSE on the set 875 * of buffers with minimum level. */ 877 rc = quantile_collapse(seq, min_level); 878 if (rc < 0) 879 return rc; 880 } else if (quantile_empty_buffers[seq] == 1) { 881 /* We have exactly one empty buffer. Invoke NEW and assign 882 * it level `min_level'. */ 884 /* Search the empty buffer. */ 885 for (qp = quantile_buffer_head[seq]; qp != NULL; 886 qp = qp->next) { 887 if (qp->weight == 0) { 888 /* Found empty buffer. */ 889 break; 890 } 891 } 893 rc = quantile_new(seq, qp, input, k, min_level); 894 if (rc < 0) 895 return rc; 896 } else { 897 /* There are at least two empty buffers. Invoke NEW on each 898 * and assign level `0' to each. */ 900 /* Search for two empty buffers. */ 901 for (qp = quantile_buffer_head[seq]; qp != NULL; 902 qp = qp->next) { 903 if (qp->weight == 0) { 904 /* Found first empty buffer. */ 905 break; 906 } 907 } 908 for (qp2 = qp->next; qp2 != NULL; qp2 = qp2->next) { 909 if (qp2->weight == 0) { 910 /* Found second empty buffer. */ 911 break; 912 } 913 } 915 if (k <= quantile_k[seq]) { 916 /* This could happen if we call this after we 917 * received all packets but don't have enough to 918 * fill up two buffers. */ 920 rc = quantile_new(seq, qp, input, k, 0); 921 if (rc < 0) 922 return rc; 923 } else { 924 /* We have enough input data for two buffers. */ 925 rc = quantile_new(seq, qp, input, quantile_k[seq], 0); 926 if (rc < 0) 927 return rc; 928 rc = quantile_new(seq, qp2, input + quantile_k[seq], 929 k - quantile_k[seq], 0); 930 if (rc < 0) 931 return rc; 932 } 933 } 934 return 0; 935 } 937 int 938 quantile_init_seq(uint16_t seq) 939 { 940 quantile_t *qp = NULL; 941 int i; 943 if ( seq >= quantile_max_seq) 944 return -5; 946 /* Allocate memory for quantile buffers. Buffers are linked 947 * lists with a pointer to next buffer. We need `quantile_b' 948 * buffers, where each buffer has space for `quantile_k' 949 * elements. */ 950 for (i = 0; i < quantile_b[seq]; i++) { 951 if (i == 0) { 952 /* Initialize first buffer. */ 953 qp = malloc(sizeof(quantile_t)); 954 if (qp == NULL) { 955 return -1; 956 } 957 quantile_buffer_head[seq] = qp; 959 } else { 960 qp->next = malloc(sizeof(quantile_t)); 961 if (qp->next == NULL) { 962 return -1; 963 } 964 qp = qp->next; 965 } 967 /* `qp' points to buffer that should be initialized. */ 968 qp->next = NULL; 969 qp->weight = 0; /* empty buffers have weight of 0 */ 970 qp->level = 0; 971 qp->buffer = malloc(sizeof(double) * quantile_k[seq]); 972 if (qp->buffer == NULL) { 973 return -1; 974 } 975 } 976 /* Update number of empty quantile buffers. */ 977 quantile_empty_buffers[seq] = quantile_b[seq]; 979 return 0; 980 } 982 int 983 quantile_init (uint16_t max_seq, double eps, uint64_t N) 984 { 985 int b, b_tmp = 0; 986 int k, k_tmp = 0; 987 int h, h_max = 0; 988 int seq, rc; 990 quantile_max_seq = max_seq; 991 /* Allocate array for the requested number of sequences. */ 992 quantile_k = calloc(max_seq, sizeof(int)); 993 quantile_input = calloc(max_seq, sizeof(double*)); 994 quantile_input_cnt = calloc(max_seq, sizeof(int)); 995 quantile_empty_buffers = calloc(max_seq, sizeof(int)); 996 quantile_b = calloc(max_seq, sizeof(int)); 997 quantile_buf = calloc(max_seq, sizeof(double*)); 998 quantile_alternate = calloc(max_seq, sizeof(int)); 999 quantile_inf_cnt = calloc(max_seq, sizeof(uint64_t)); 1000 quantile_buffer_head = calloc(max_seq, sizeof(quantile_t*)); 1002 /* "In practice, optimal values for b and k can be computed by 1003 * trying out different values of b in the range 1 and 30." */ 1004 for (b = 2; b <= 30; b++) { 1005 /* For each b, compute the largest integral h that 1006 * satisfies: 1008 * (h-2) * C(b+h-2, h-1) - C(b+h-3, h-3) + 1009 * C(b+h-3, h-2) <= 2 * eps * N 1010 */ 1011 for (h = 0; ; h++) { 1012 if (((h-2) * binomial(b+h-2, h-1) - 1013 binomial(b+h-3, h-3) + 1014 binomial(b+h-3, h-2)) > 1015 (2 * eps * N)) { 1016 /* This h does not satisfy the inequality from 1017 * above. */ 1018 break; 1019 } 1020 h_max = h; 1021 } 1023 /* Now compute the smallest integral k that satisfies: 1024 * k * C(b+h-2, h-1) => N. */ 1025 k = ceil(N / (double)binomial(b+h_max-2, h_max-1)); 1027 /* Identify that b that minimizes b*k. */ 1028 if ((b_tmp == 0) && (k_tmp == 0)) { 1029 /* Initialize values */ 1030 b_tmp = b; 1031 k_tmp = k; 1032 } 1034 if ((b * k) < (b_tmp * k_tmp)) { 1035 /* Found b and k for which the product is smaller than 1036 * for the ones before. Because we want to minimize 1037 * b*k (required memory), we save them. */ 1038 b_tmp = b; 1039 k_tmp = k; 1040 } 1041 } 1043 /* Set global quantile values. For now, all sequences share 1044 the same k and b values.*/ 1045 for (seq = 0; seq < max_seq; seq++ ) { 1046 quantile_b[seq] = b_tmp; 1047 quantile_k[seq] = k_tmp; 1048 } 1050 /* Allocate memory for input buffer. We allocate enough space 1051 * to save up to `2 * quantile_k' elements. This space is 1052 * needed in the COLLAPSE policy if there are more than two 1053 * empty buffers. Because then we have to invoke NEW on two 1054 * buffers and thus need an input buffer with `2 * quantile_k' 1055 * elements. */ 1057 for (seq = 0; seq < quantile_max_seq; seq++) { 1058 quantile_input[seq] = malloc(sizeof(double) * 2 * 1059 quantile_k[seq]); 1060 if (quantile_input[seq] == NULL) { 1061 return -1; 1062 } 1063 quantile_input_cnt[seq] = 0; 1064 } 1066 /* Allocate memory for output buffer. This buffer is used in 1067 * COLLAPSE to store temporary output buffer before it gets 1068 * copied to one of the buffers used in COLLAPSE. */ 1069 for (seq = 0; seq < quantile_max_seq; seq++ ) { 1070 quantile_buf[seq] = malloc(sizeof(double) * quantile_k[seq]); 1071 if (quantile_buf[seq] == NULL) { 1072 return -1; 1073 } 1074 } 1076 for (seq = 0; seq < max_seq; seq++) { 1077 rc = quantile_init_seq(seq); 1078 if (rc < 0) 1079 return rc; 1080 } 1082 return 0; 1083 } 1085 int 1086 quantile_value_checkin(uint16_t seq, double value) 1087 { 1088 int rc = 0; 1090 if ( seq >= quantile_max_seq) 1091 return -5; 1093 quantile_input[seq][quantile_input_cnt[seq]++] = value; 1095 /* If we have at least two empty buffers, 1096 * we need input for two buffers, to twice 1097 * the value of `quantile_k'. */ 1098 if (quantile_empty_buffers[seq] >= 2) { 1099 if (quantile_input_cnt[seq] == 1100 (2 * quantile_k[seq])) { 1101 rc = quantile_algorithm(seq, quantile_input[seq], 1102 quantile_input_cnt[seq]); 1103 /* Reset counter. */ 1104 quantile_input_cnt[seq] = 0; 1106 } 1107 } else { 1108 /* There are 0 or 1 empty buffers */ 1109 if (quantile_input_cnt[seq] == quantile_k[seq]) { 1110 rc = quantile_algorithm(seq, quantile_input[seq], 1111 quantile_input_cnt[seq]); 1112 /* Reset counter. */ 1113 quantile_input_cnt[seq] = 0; 1114 } 1115 } 1116 return rc; 1117 } 1119 int 1120 quantile_finish(uint16_t seq) 1121 { 1122 int rc = 0; 1124 if ( seq >= quantile_max_seq) 1125 return -5; 1127 if (quantile_input_cnt[seq] > 0) { 1128 rc = quantile_algorithm(seq, quantile_input[seq], 1129 quantile_input_cnt[seq]); 1130 } 1131 return rc; 1132 } 1134 void 1135 quantile_reset(uint16_t seq) 1136 { 1137 quantile_input_cnt[seq] = 0; 1138 quantile_empty_buffers[seq] = quantile_b[seq]; 1139 memset(quantile_buf[seq],0,sizeof(double) * quantile_k[seq]); 1140 memset(quantile_input[seq],0,sizeof(double) * quantile_k[seq]); 1141 } 1143 /** 1144 * Deinitialize one quantile sequence. 1145 **/ 1146 void 1147 quantile_exit_seq(uint16_t seq) 1148 { 1149 quantile_t *qp = NULL, *next; 1151 if (seq >= quantile_max_seq) 1152 return; 1154 qp = quantile_buffer_head[seq]; 1155 while (qp != NULL) { 1156 /* Save pointer to next buffer. */ 1157 next = qp->next; 1159 /* Free buffer and list entry. */ 1160 free(qp->buffer); 1161 free(qp); 1163 /* Set current buffer to next one. */ 1164 qp = next; 1165 } 1167 quantile_buffer_head[seq] = NULL; 1168 quantile_input_cnt[seq] = 0; 1169 quantile_empty_buffers[seq] = quantile_b[seq]; 1170 } 1172 void 1173 quantile_exit(void) 1174 { 1175 int seq; 1177 /* Free per sequence structures */ 1178 for (seq = 0; seq < quantile_max_seq; seq++) { 1179 quantile_exit_seq(seq); 1181 /* Free output buffer. */ 1182 free(quantile_buf[seq]); 1184 /* Free input buffer. */ 1185 free(quantile_input[seq]); 1186 } 1188 free(quantile_buffer_head); 1189 free(quantile_inf_cnt); 1190 free(quantile_alternate); 1191 free(quantile_buf); 1192 free(quantile_b); 1193 free(quantile_empty_buffers); 1194 free(quantile_input_cnt); 1195 free(quantile_input); 1196 free(quantile_k); 1197 } 1199 int 1200 quantile_output (uint16_t seq, uint64_t npackets, double phi, 1201 double *result) 1203 { 1204 quantile_t *qp = NULL; 1205 int num_buffers = 0; 1206 int weight = 0; 1207 int j; 1208 long next_pos = 0; 1209 long merge_pos = 0; 1210 double min_dbl; 1211 double beta; 1212 double phi2; /* this is phi' */ 1214 if ( seq >= quantile_max_seq) 1215 return -5; 1217 /* Check that there are at least two full buffers with given 1218 * level. */ 1219 for (qp = quantile_buffer_head[seq]; qp != NULL; qp = qp->next) { 1220 if (qp->weight != 0) { 1221 num_buffers++; 1222 weight += qp->weight; 1223 qp->pos = 0; 1224 } else { 1225 qp->pos = -1; 1226 } 1227 } 1228 if (num_buffers < 2) { 1229 /* XXX: In section 3.3 "OUTPUT operation" of paper [1] is 1230 * says that OUTPUT takes c => 2 full input buffers. But 1231 * what if we just have one full input buffer? 1232 * 1233 * For example this happens if you run a UDP test with a 1234 * block size of 100k and a test duration of 3 seconds: $ 1235 * ./thrulay -u 100k -t 3 localhost 1236 */ 1238 if (num_buffers != 1) { 1239 return -1; 1240 } 1241 } 1243 /* Calculate beta and phi' */ 1244 beta = 1 + quantile_inf_cnt[seq] / (double)npackets; 1245 assert(beta >= 1.0); 1247 assert(phi >= 0.0 && phi <= 1.0); 1248 phi2 = (2 * phi + beta - 1) / (2 * beta); 1250 next_pos = ceil(phi2 * quantile_k[seq] * weight); 1251 /* XXX: If the client just sends a few packets, it is possible 1252 * that next_pos is too large. If this is the case, decrease 1253 * it. */ 1254 if (next_pos >= (num_buffers * quantile_k[seq])) { 1255 next_pos --; 1256 } 1258 while (1) { 1260 /* Search for current minimal element in all buffers. 1261 * Because buffers are all sorted, we just have to check 1262 * the element at current position. */ 1263 min_dbl = DBL_MAX; 1264 for (qp = quantile_buffer_head[seq]; qp != NULL; 1265 qp = qp->next) { 1266 /* Skip wrong buffers. */ 1267 if (qp->pos == -1) { 1268 continue; 1269 } 1271 /* Check that we are not at the end of buffer. */ 1272 if (qp->pos >= quantile_k[seq]) { 1273 continue; 1274 } 1276 /* Update minimum element. */ 1277 min_dbl = min(min_dbl, qp->buffer[qp->pos]); 1278 } 1280 /* Now process this minimal element in all buffers. */ 1281 for (qp = quantile_buffer_head[seq]; qp != NULL; 1282 qp = qp->next) { 1283 /* Skip wrong buffers. */ 1284 if (qp->pos == -1) { 1285 continue; 1286 } 1288 /* Now process minimal element in this buffer. */ 1289 for (; (qp->buffer[qp->pos] == min_dbl) && 1290 (qp->pos < quantile_k[seq]); 1291 qp->pos++) { 1293 /* Increment merge position `qp->weight' 1294 * times. If we pass the position we seek, 1295 * return current minimal element. */ 1296 for (j = 0; j < qp->weight; j++) { 1297 if (next_pos == merge_pos) { 1298 *result = min_dbl; 1299 return 0; 1300 } 1301 merge_pos++; 1302 } 1303 } 1304 } 1305 } 1307 /* NOTREACHED */ 1308 } 1310 #ifdef THRULAY_REPORTING_SAMPLE_LOOP 1312 #include 1313 #include 1315 #ifndef NAN 1316 #define _ISOC99_SOURCE 1317 #include 1318 #endif 1320 #define ERR_FATAL 0 1321 #define ERR_WARNING 1 1323 void __attribute__((noreturn)) 1324 quantile_alg_error(int rc) 1325 { 1326 switch (rc) { 1327 case -1: 1328 fprintf(stderr, "Error: quantiles not initialized."); 1329 break; 1330 case -2: 1331 fprintf(stderr, "Error: NEW needs an empty buffer."); 1332 break; 1333 case -3: 1334 fprintf(stderr, "Error: Bad input sequence length."); 1335 break; 1336 case -4: 1337 fprintf(stderr, "Error: Not enough buffers for COLLAPSE."); 1338 break; 1339 default: 1340 fprintf(stderr, "Error: Unknown quantile_algorithm error."); 1341 } 1342 exit(1); 1343 } 1345 /** 1346 * Will read a sample data file (first and only parameter) whose 1347 * lines give two values per line (per received packet): measured 1348 * packet delay and packet sequence number (in "%lf %lu" 1349 * format). As an exception, the first line specifies the number 1350 * of packets actually sent. Example: 1351 * ---- 1352 10 1353 0.101 0 1354 0.109 1 1355 0.12 1 1356 0.10 3 1357 0.14 4 1358 0.15 5 1359 0.13 2 1360 0.09 6 1361 0.1 8 1362 0.091 7 1363 * ---- 1364 * 1365 * To compile this sample reporting main(): 1366 * 1367 * gcc -std=c99 -DTHRULAY_REPORTING_SAMPLE_LOOP reporting.c -lm 1368 * 1369 **/ 1370 int 1371 main(int argc, char *argv[]) 1372 { 1373 FILE *sf; 1374 /* 'Measured data' */ 1375 const int max_packets = 65535; 1376 /* 'Received' packets*/ 1377 int npackets = 0; 1378 uint64_t packet_sqn[max_packets]; /* Fill in with sample data */ 1379 double packet_delay[max_packets]; /* Fill in with sample data */ 1380 uint64_t packets_sent = 0; /* Fill in with sample data */ 1381 /* reordering */ 1382 const uint64_t reordering_max = 100; 1383 char buffer_reord[reordering_max * 80]; 1384 size_t r = 0; 1385 uint64_t j = 0; 1386 /* Stats */ 1387 uint64_t unique_packets = 0, packets_dup = 0; 1388 double quantile_25, quantile_50, quantile_75; 1389 double delay, jitter; 1390 double packet_loss; 1391 char report_buffer[1000]; 1392 /* Auxiliary variables */ 1393 int i, rc, rc2, rc3; 1394 memset(packet_sqn,0,sizeof(uint64_t)*max_packets); 1395 memset(packet_delay,0,sizeof(double)*max_packets); 1397 /* Inititalize duplication */ 1398 rc = duplication_init(max_packets); 1399 if (-1 == rc) { 1400 perror("calloc"); 1401 exit(1); 1402 } 1404 /* Initialize quantiles */ 1405 rc = quantile_init(1, QUANTILE_EPS, max_packets); 1406 if (-1 == rc) { 1407 perror("malloc"); 1408 exit(1); 1409 } 1411 /* Initialize reordering */ 1412 rc = reordering_init(reordering_max); 1413 if (-1 == rc) { 1414 perror("calloc"); 1415 exit(1); 1416 } 1418 /* Open sample file */ 1419 if (2 == argc) { 1420 sf = fopen(argv[1],"r"); 1421 } else { 1422 fprintf(stderr, "no input file\n"); 1423 exit(1); 1424 } 1426 /* Process sample input file. */ 1428 /* The sender somehow tells the receiver how many packets were 1429 actually sent. */ 1430 fscanf(sf,"%lu",&packets_sent); 1432 for (i = 0; i < max_packets && !feof(sf); i++) { 1434 fscanf(sf,"%lf %lu",&packet_delay[i],&packet_sqn[i]); 1435 npackets++; 1437 /* 1438 * Duplication 1439 */ 1440 if (duplication_check(packet_sqn[i])) { 1441 /* Duplicated packet */ 1442 packets_dup++; 1443 continue; 1444 } else { 1445 /* Unique packet */ 1446 unique_packets++; 1447 } 1449 /* 1450 * Delay quantiles. 1451 */ 1452 rc = quantile_value_checkin(0, packet_delay[i]); 1453 if (rc < 0) 1454 quantile_alg_error(rc); 1456 /* 1457 * Reordering 1458 */ 1459 reordering_checkin(packet_sqn[i]); 1460 } 1462 /* 1463 * Perform last algorithm operation with a possibly not full 1464 * input buffer. 1465 */ 1466 rc = quantile_finish(0); 1467 if (rc < 0) 1468 quantile_alg_error(rc); 1470 rc = quantile_output(0, unique_packets, 0.25, &quantile_25); 1471 rc2 = quantile_output(0, unique_packets, 0.50, &quantile_50); 1472 rc3 = quantile_output(0, unique_packets, 0.75, &quantile_75); 1473 if (-1 == rc || -1 == rc2 || -1 == rc3) { 1474 fprintf(stderr,"An error occurred while computing delay " 1475 "quantiles. %d %d %d\n",rc, rc2, rc3); 1476 exit(1); 1477 } 1479 /* Delay and jitter computation */ 1480 packet_loss = packets_sent > unique_packets? 1481 (100.0*(packets_sent - unique_packets))/packets_sent: 0; 1482 delay = (packet_loss > 50.0)? INFINITY : quantile_50; 1483 if (packet_loss < 25.0 ) { 1484 jitter = quantile_75 - quantile_25; 1485 } else if (packet_loss > 75.0) { 1486 jitter = NAN; 1487 } else { 1488 jitter = INFINITY; 1489 } 1490 /* Format final report */ 1491 snprintf(report_buffer, sizeof(report_buffer), 1492 "Delay: %3.3fms\n" 1493 "Loss: %3.3f%%\n" 1494 "Jitter: %3.3fms\n" 1495 "Duplication: %3.3f%%\n" 1496 "Reordering: %3.3f%%\n", 1497 1000.0 * delay, 1498 packet_loss, 1499 1000.0 * jitter, 1500 100 * (double)packets_dup/npackets, 1501 100.0 * reordering_output(0)); 1503 printf("%s", report_buffer); 1505 /* Deallocate resources for statistics. */ 1506 reordering_exit(); 1507 quantile_exit(); 1508 duplication_exit(); 1510 fclose(sf); 1512 exit(0); 1513 } 1515 #endif /* THRULAY_REPORTING_SAMPLE_LOOP */ 1517 Appendix B. Example Report 1519 This appendix only serves for illustrative purposes. 1521 This report is produced by running the sample program in Appendix A 1522 on the sample input embedded in a comment in its source code: 1524 Delay: 109.000ms 1525 Loss: 10.000% 1526 Jitter: 40.000ms 1527 Duplication: 18.182% 1528 Reordering: 25.000% 1530 Appendix C. TODO 1532 FIXME: This section needs to be removed before publication. 1534 o Add references 1536 Appendix D. Revision History 1538 FIXME: This section needs to be removed before publication. 1540 version -03: 1541 Add most references; some small wording changes for clarity. 1543 version -02: 1544 Update terminology. 1546 Log leading up to -01: 1547 $Log: draft-ietf-ippm-reporting.xml,v $ 1548 Revision 1.8 2006/10/23 21:45:54 shalunov 1549 draft-ietf-ippm-reporting-01.txt 1551 Revision 1.7 2006/10/23 21:45:13 shalunov 1552 Add sample source code and output. 1554 Revision 1.6 2006/06/02 21:21:57 shalunov 1555 draft-ietf-ippm-reporting-00: Include a ``Scope'' section. 1556 Change tags from draft-shalunov-ippm-reporting. 1558 Revision 1.5 2006/05/02 20:25:44 shalunov 1559 Version 03: Various refinements and clarifications based on feedback 1560 from Reza Fardid, Ruediger Geib, and Al Morton. 1562 Revision 1.4 2006/04/25 22:38:58 shalunov 1563 Version 02: Address comments from Carsten Schmoll, sent in message 1564 70524A4436C03E43A293958B505008B61B9CFB@EXCHSRV.fokus.fraunhofer.de. 1565 My response, with clarifications and diffs, is in message 1566 8664kxwazk.fsf@abel.internet2.edu. 1568 Revision 1.3 2006/04/11 22:09:47 shalunov 1569 Version 01: Wording changes based on discussion with Matt Zekauskas 1570 (reordering, loss). Rewrite abstract a bit. Add TODO list. 1572 Revision 1.2 2006/04/04 21:39:20 shalunov 1573 Convert to xml2rfc 1.30 and RFC 3978 IPR statement. 1575 Revision 1.1.1.1 2006/04/02 17:07:36 shalunov 1576 Initial import into CVS. 1578 Authors' Addresses 1580 Stanislav Shalunov 1582 Email: shalunov@shlang.com 1583 URI: http://shlang.com/ 1585 Martin Swany 1586 University of Delaware 1587 Department of Computer and Information Sciences 1588 Newark, DE 19716 1589 US 1591 Email: swany@cis.udel.edu 1592 URI: http://www.cis.udel.edu/~swany/