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