idnits 2.17.1 draft-ietf-ippm-reporting-05.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 (July 13, 2010) is 5029 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 1435 -- Looks like a reference, but probably isn't: '1000' on line 1405 ** Obsolete normative reference: RFC 2679 (Obsoleted by RFC 7679) ** Obsolete normative reference: RFC 2680 (Obsoleted by RFC 7680) Summary: 2 errors (**), 0 flaws (~~), 1 warning (==), 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: January 14, 2011 University of Delaware 6 July 13, 2010 8 Reporting IP Performance Metrics to Users 9 draft-ietf-ippm-reporting-05.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 January 14, 2011. 40 Copyright Notice 42 Copyright (c) 2010 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. Normative References . . . . . . . . . . . . . . . . . . . . . 16 87 Appendix A. Sample Source Code for Computing the Metrics . . . . 17 88 Appendix B. Example Report . . . . . . . . . . . . . . . . . . . 41 89 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 42 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. Introduction 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 packets sent but not lost for which 236 more 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 5560 [RFC5560] (A One-Way Packet Duplication 245 Metric). Duplication is Type-P-one-way-replicated-packet-rate 246 expressed as a percentage. 248 4.5. Reordering 250 Reordering is the fraction of unique packets received for which the 251 sequence number of any given packet is less than the highest sequence 252 number largest sequence number of any packet previously received. 253 For the purposes of determining the sequence number of the preceding 254 packets in this definition, assume sequence numbers starting with 1, 255 and an extra packet at the start of the stream of received packets, 256 with a sequence number of 0, is considered to be present (this extra 257 packet, of course, is not counted for the purposes of computing the 258 fraction). 260 For more information, refer to section 4.1.3 (Type-P-Reordered-Ratio- 261 Stream) of RFC 4737 [RFC4737] (Packet Reordering Metrics), and 262 supporting text. The precise definition of a reordered packet is in 263 section 3.3. 265 {Comment: As the non-normative sample code in Appendix A below shows, 266 this is also related to the amount of 1-reordering (Section 5.3 RFC 267 4737 [RFC4737]). It is not, however, the degree of 1-reordering in 268 5.3; because 1-reordering divides by the number of all packets 269 received, instead of the number of non-duplicate packets received.} 271 5. Sample Source 273 Section 4 describes the metrics to compute on a sample of 274 measurements. The source of the sample in not discussed there, and, 275 indeed, the metrics discussed (delay, loss, etc.) are simply 276 estimators that could be applied to any sample whatsoever. For the 277 names of the estimators to be applicable, of course, the measurements 278 need to come from a packet delivery network. 280 The data in the samples for the set of metrics discussed in this 281 document can come from the following sources: one-way active 282 measurement, round-trip measurement, and passive measurement. There 283 infrequently is a choice between active and passive measurement, as, 284 typically, only one is available; consequently, no preference is 285 given to one over the other. In cases where clocks can be expected 286 to be synchronized, in general, one-way measurements are preferred 287 over round-trip measurements (as one-way measurements are more 288 informative). When one-way measurements cannot be obtained, or when 289 clocks cannot be expected to be synchronized, round-trip measurement 290 MAY be used. 292 5.1. One-Way Active Measurement 294 The default duration of the measurement interval is 10 seconds. 296 The default sending schedule is a Poisson stream. 298 The default sending rate is 10 packets/second on average. The 299 default sending schedule is a Poisson stream. When randomized 300 schedules, such as a Poisson stream, are used, the rate MUST be set 301 with the distribution parameter(s). With a randomized schedule, the 302 default sample size is 100 packets and the measurement window 303 duration can vary to some extent depending on the values of the 304 (pseudo-)random deviates. 306 The default packet size is the minimum necessary for the measurement. 308 Values other than the default ones MAY be used; if they are used, 309 their use, and specific values used, MUST be reported. 311 A one-way active measurement is characterized by the source IP 312 address, the destination IP address, the time when measurement was 313 taken, and the type of packets (e.g., UDP with given port numbers and 314 a given DSCP) used in the measurement. For the time, the end of the 315 measurement interval MUST be reported. 317 5.2. Round-Trip Active Measurement 319 The same default parameters and characterization apply to round-trip 320 measurement as to one-way measurement (Section 5.1). 322 5.3. Passive Measurement 324 Passive measurement use whatever data it is natural to use. For 325 example, an IP telephony application or a networked game would use 326 the data that it sends. An analysis of performance of a link might 327 use all the packets that traversed the link in the measurement 328 interval. An analysis of performance of an Internet service 329 provider's network might use all the packets that traversed the 330 network in the measurement interval. An analysis of performance of a 331 specific service from the point of view of a given site might use an 332 appropriate filter to select only the relevant packets. In any case, 333 the source needs to be reported. 335 The same default duration applies to passive measurement as to one- 336 way active measurement (Section 5.1). 338 When the passive measurement data is reported in real time, or based 339 on user demand, a sliding window SHOULD be used as a measurement 340 period, so that recent data become more quickly reflected. For 341 historical reporting purposes, a fixed interval may be preferable. 343 6. Security Considerations 345 The reporting per se, not being a protocol, does not raise security 346 considerations. 348 An aspect of reporting relevant to security is how the reported 349 metrics are used and how they are collected. If it is important that 350 the metrics satisfy certain conditions (e.g., that the ISP whose 351 network is being measured be unable to make the metrics appear better 352 than they are), the collection mechanism MUST ensure that this is, 353 indeed, so. The exact mechanisms to do so are outside of scope of 354 this document and belong with discussion of particular measurement 355 data collection protocols. 357 7. Acknowledgments 359 We gratefully acknowledge discussion with, encouragement from, and 360 contributions of Lawrence D. Dunn, Reza Fardid, Ruediger Geib, 361 Matt Mathis, Al Morton, Carsten Schmoll, Henk Uijterwaal, and 362 Matthew J. Zekauskas. 364 8. IANA Considerations 366 This document requires no action from the IANA. 368 9. Internationalization Considerations 370 The reported metrics, while they might occasionally be parsed by 371 machine, are primarily meant for human consumption. As such, they 372 MAY be reported in the language preferred by the user, using an 373 encoding suitable for the purpose, such as UTF-8. 375 10. Normative References 377 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 378 Requirement Levels", BCP 14, RFC 2119, March 1997. 380 [RFC2679] Almes, G., Kalidindi, S., and M. Zekauskas, "A One-way 381 Delay Metric for IPPM", RFC 2679, September 1999. 383 [RFC2680] Almes, G., Kalidindi, S., and M. Zekauskas, "A One-way 384 Packet Loss Metric for IPPM", RFC 2680, September 1999. 386 [RFC4737] Morton, A., Ciavattone, L., Ramachandran, G., Shalunov, 387 S., and J. Perser, "Packet Reordering Metrics", RFC 4737, 388 November 2006. 390 [RFC5560] Uijterwaal, H., "A One-Way Packet Duplication Metric", 391 RFC 5560, May 2009. 393 Appendix A. Sample Source Code for Computing the Metrics 395 This appendix only serves for illustrative purposes. 397 /* 398 * reporting.c -- performance metrics reporting as in Internet Draft 399 * draft-ietf-ippm-reporting. 400 * 401 * Written by Stanislav Shalunov, http://www.internet2.edu/~shalunov/ 402 * Bernhard Lutzmann, belu@users.sf.net 403 * Federico Montesino Pouzols, fedemp@altern.org 404 * 405 * This file is also available, under a different (BSD-style) 406 * license, as part of thrulay. 407 */ 409 /** 410 * @file reporting.c 411 * 412 * @short metrics computation and reporting. 413 **/ 415 #include 416 #include 417 #include 418 #include 419 #include 420 #include 422 #define min(a, b) ((a) < (b) ? (a) : (b)) 423 #define max(a, b) ((a) > (b) ? (a) : (b)) 425 /* 426 * Reordering. 427 */ 428 #define loop(x) ((x) >= 0 ? (x) : (x) + (int)reordering_max) 430 /* 431 * Duplication. 432 */ 433 static uint64_t *bitfield = NULL; /* Bit field used to check for 434 duplicated packets. */ 436 /* 437 * Reordering. 438 */ 439 static uint64_t reordering_max; /* We have m[j-1] == number of */ 440 static uint64_t *reordering_m; /* We have m[j-1] == number of 441 j-reordered packets. */ 442 static uint64_t *reordering_ring; /* Last sequence numbers seen */ 443 static int r = 0; /* Ring pointer for next write. */ 444 static int l = 0; /* Counter of sequence numbers. */ 446 /* 447 * Quantiles 448 * 449 * Reference: 450 * 451 * [1] Manku, Rajagopalan, Lindsay: "Approximate Medians and other 452 * Quantiles in One Pass and with Limited Memory", 453 * http://www-db.stanford.edu/~manku/papers/98sigmod-quantiles.pdf 454 */ 456 #define QUANTILE_EPS 0.005 458 static uint16_t quantile_max_seq; /* Maximum number of sequences */ 459 static int *quantile_k; /* number of elements in buffer */ 461 static double **quantile_input; /* This is the buffer where the 462 sequence of incoming packets is 463 saved. If we received enough 464 packets, we will write this 465 buffer to a quantile buffer. */ 466 static int *quantile_input_cnt; /* number of elements in input 467 * buffer */ 468 static int *quantile_empty_buffers; /* number of empty buffers */ 470 static int *quantile_b; /* number of buffers */ 472 static double **quantile_buf; 474 static int *quantile_alternate; /* this is used to determine 475 the offset in COLLAPSE (if 476 weight is even) */ 478 static uint64_t *quantile_inf_cnt; /* this counter is for the 479 additional -inf, +inf 480 elements we added to NEW 481 buffer to fill it up. */ 483 typedef struct quantile { 484 struct quantile *next; /* pointer to next quantile 485 * buffer */ 486 int weight; /* 0 if buffer is empty, > 0 if buffer is 487 * full */ 489 int level; 490 double *buffer; 491 int pos; /* current position in buffer; used in 492 quantile_collapse() */ 493 } quantile_t; 495 static quantile_t **quantile_buffer_head; 497 int 498 reordering_init(uint64_t max) 499 { 500 reordering_max = max; 501 reordering_m = calloc(reordering_max, sizeof(uint64_t)); 502 reordering_ring = calloc(reordering_max, sizeof(uint64_t)); 503 if (reordering_m == NULL) { 504 return -1; 505 } else { 506 return 0; 507 } 508 } 510 int 511 reordering_checkin(uint64_t packet_sqn) 512 { 513 int j; 515 for (j = 0; j < min(l, (int)reordering_max) && 517 packet_sqn < reordering_ring[loop(r-j-1)]; j++) { 518 reordering_m[j]++; 519 } 520 reordering_ring[r] = packet_sqn; 521 l++; 522 r = (r + 1) % reordering_max; 523 return 0; 524 } 526 double 527 reordering_output(uint64_t j) 528 { 529 if (j >= reordering_max) 530 return -1; 531 else 532 return (double)reordering_m[j] / l); 533 } 535 void 536 reordering_exit(void) 537 { 538 free(reordering_ring); 539 free(reordering_m); 540 } 542 int 543 duplication_init(uint64_t npackets) 544 { 545 uint64_t bitfield_len = 0; /* Number of sectors in bitfield */ 547 /* Allocate memory for bit field */ 548 bitfield_len = ((npackets % 64)? 549 (npackets / 64 + 1) : npackets / 64); 550 bitfield = calloc(bitfield_len, sizeof(uint64_t)); 551 if (bitfield == NULL) { 552 return -1; 553 } else { 554 return 0; 555 } 556 } 558 int 559 duplication_check(uint64_t packet_sqn) 560 { 561 uint64_t bitfield_sec; /* Which sector in bitfield */ 562 uint64_t bitfield_bit; /* Which bit in sector */ 564 /* Calculate sector */ 565 bitfield_sec = packet_sqn >> 6; 567 /* Calculate bit in sector */ 568 bitfield_bit = (uint64_t)1 << (packet_sqn & 63); 570 if (bitfield[bitfield_sec] & bitfield_bit) { 571 /* Duplicated packet */ 572 return 1; 573 } else { 574 /* Unique packet */ 575 bitfield[bitfield_sec] |= bitfield_bit; 576 return 0; 577 } 578 } 580 void 581 duplication_exit(void) 582 { 583 free(bitfield); 584 } 585 /* Calculate binomial coefficient C(n, k). */ 586 int64_t 587 binomial (int n, int k) 588 { 589 int64_t bc = 0; 590 int i, m; 592 /* C(n, k) = C(n, n-k) */ 593 k = min(k, n-k); 595 if (k >= 0) { 596 bc = 1; 597 m = max(k, n-k); 599 for (i = 1; i <= k; i++) { 600 bc = (bc * (m + i)) / i; 601 } 602 } 604 return bc; 605 } 607 int 608 quantile_compare(const void *d1, const void *d2) 609 { 610 if (*(double *)d1 < *(double *)d2) { 611 return -1; 612 } else if (*(double *)d1 == *(double *)d2) { 613 return 0; 614 } else { 615 assert(*(double *)d1 > *(double *)d2); 616 return 1; 617 } 618 } 620 void 621 quantile_sort (double *list, int length) 622 { 623 qsort(list, length, sizeof(double), quantile_compare); 624 } 626 /** 627 * Implementation of NEW operation from section 3.1 of paper [1]. 628 * 629 * Takes as input an empty buffer. Simply populates the quantile 630 * buffer with the next k elements from the input sequence, labels 631 * the buffer as full, and assigns it a weight of 1. 632 * 633 * If there are not enough elements to fill up the buffer, we 634 * alternately add -inf, +inf elements until buffer is full (-inf 635 * == 0, +inf == DBL_MAX). 636 * 637 * NOTE: We sort the elements in the input buffer before we copy 638 * them to the quantile buffer. 639 * 640 * @param seq Sequence index. 641 * 642 * @return 643 * @retval 0 on success. 644 * @retval -2 need an empty buffer. 645 * @retval -3 bad input sequence length. 646 **/ 647 int 648 quantile_new(uint16_t seq, quantile_t *q, double *input, int k, 649 int level) 650 { 651 int i; 653 /* Check that buffer is really empty. */ 654 if (q->weight != 0) { 655 return -2; 656 } 658 /* Sanity check for length of input sequence. */ 659 if (k > quantile_k[seq]) { 660 return -3; 661 } 663 /* If there are not enough elements in the input buffer, fill 664 * it up with -inf, +inf elements. */ 665 for (i = k; i < quantile_k[seq]; i++) { 666 if (i % 2) { 667 input[i] = DBL_MAX; 668 } else { 669 input[i] = 0; 670 } 672 /* Increment counter that indicates how many additional 673 * elements we added to fill the buffer. */ 674 quantile_inf_cnt[seq]++; 675 } 677 quantile_sort(input, quantile_k[seq]); 679 memcpy(q->buffer, input, sizeof(double) * quantile_k[seq]); 680 /* Mark buffer as full and set level. */ 681 q->weight = 1; 682 q->level = level; 684 /* Update number of empty quantile buffers. */ 685 quantile_empty_buffers[seq]--; 687 return 0; 688 } 690 /* Implementation of COLLAPSE operation from section 3.2 of paper 691 * [1]. 692 * 693 * This is called from quantile_algorithm() if there are no empty 694 * buffers. We COLLAPSE all the full buffers, where level has 695 * value `level'. Output is written to the first buffer in linked 696 * list with level set to `level'. The level of the output buffer 697 * is increased by 1. All other buffers we used in the COLLAPSE 698 * are marked empty. */ 699 int 700 quantile_collapse(uint16_t seq, int level) 701 { 702 quantile_t *qp = NULL, *qp_out = NULL; 703 int num_buffers = 0; /* number of buffers with level 704 * `level' */ 705 int weight = 0; /* weight of the output buffer */ 706 int offset; 707 int i, j; 708 double min_dbl; 709 long next_pos; 710 long merge_pos = 0; 712 /* Check that there are at least two full buffers with given 713 * level. Also calculate weight of output buffer. */ 714 for (qp = quantile_buffer_head[seq]; qp != NULL; qp = qp->next) { 715 if ((qp->weight != 0) && (qp->level == level)) { 716 num_buffers++; 717 weight += qp->weight; 718 qp->pos = 0; 719 } else { 720 /* We mark the buffers that are not used in this 721 * COLLAPSE. */ 722 qp->pos = -1; 723 } 724 } 725 if (num_buffers < 2) { 726 return -4; 728 } 730 /* NOTE: The elements in full buffers are sorted. So we don't 731 * have to do that again. 732 */ 733 /* Search for first full buffer with matching level. This is 734 * the buffer where we save the output. */ 735 for (qp_out = quantile_buffer_head[seq]; qp_out != NULL; 736 qp_out = qp_out->next) { 737 if (qp_out->pos != -1) { 738 break; 739 } 740 } 742 /* Calculate offset */ 743 if (weight % 2) { 744 /* odd */ 745 offset = (weight + 1) / 2; 746 } else { 747 /* even - we alternate between two choices in each 748 * COLLAPSE */ 749 if (quantile_alternate[seq] % 2) { 750 offset = weight / 2; 751 } else { 752 offset = (weight + 2)/ 2; 753 } 754 quantile_alternate[seq] = (quantile_alternate[seq] + 1) % 2; 755 } 757 /* Initialize next position of element to save. Because first 758 * position is at 0, we have to decrement offset by 1. */ 759 next_pos = offset - 1; 761 for (i = 0; i < quantile_k[seq]; ) { 763 /* Search for current minimal element in all buffers. 764 * Because buffers are all sorted, we just have to check 765 * the element at current position. */ 766 min_dbl = DBL_MAX; 767 for (qp = quantile_buffer_head[seq]; qp != NULL; 768 qp = qp->next) { 769 /* Skip wrong buffers. */ 770 if (qp->pos == -1) { 771 continue; 772 } 774 /* Check that we are not at the end of buffer. */ 775 if (qp->pos >= quantile_k[seq]) { 776 continue; 777 } 779 /* Update minimum element. */ 780 min_dbl = min(min_dbl, qp->buffer[qp->pos]); 781 } 783 /* Now process this minimal element in all buffers. */ 784 for (qp = quantile_buffer_head[seq]; qp != NULL; 785 qp = qp->next) { 786 /* Skip wrong buffers. */ 787 if (qp->pos == -1) { 788 continue; 789 } 791 /* Now process minimal element in this buffer. */ 792 for (; (qp->buffer[qp->pos] == min_dbl) && 793 (qp->pos < quantile_k[seq]); 794 qp->pos++) { 796 /* We run this loop `qp->weight' times. 797 * We check there if we are in a position 798 * so we have to save this element in our 799 * output buffer. */ 800 for (j = 0; j < qp->weight; j++) { 802 if (next_pos == merge_pos) { 803 quantile_buf[seq][i] = min_dbl; 804 i++; 806 if (i == quantile_k[seq]) { 807 /* We have written 808 * all elements to 809 * output buffer, so 810 * exit global loop. */ 811 goto out; 812 } 814 /* Update next position. */ 815 next_pos += weight; 816 } 818 merge_pos++; 819 } /* for(j = 0; j < qp->weight; j++) */ 820 } /* for (; (qp->buffer[qp->pos] == min_dbl) && 821 (qp->pos < quantile_k[seq]); qp->pos++) */ 822 } /* for (qp = quantile_buffer_head[seq]; qp!=NULL; 823 qp = qp->next) */ 825 } /* for (i = 0; i < quantile_k[seq]; ) */ 827 out: 828 memcpy(qp_out->buffer, quantile_buf[seq], 829 sizeof(double) * quantile_k[seq]); 831 /* Update weight of output buffer. */ 832 qp_out->weight = weight; 833 qp_out->level = level+1; 835 /* Update list of empty buffers. */ 836 for (qp = quantile_buffer_head[seq]; qp != NULL; qp = qp->next) { 837 if ((qp->pos != -1) && (qp != qp_out)) { 838 qp->weight = 0; 839 qp->level = 0; 840 } 841 } 842 quantile_empty_buffers[seq] += num_buffers - 1; 843 return 0; 844 } 846 /** 847 * Implementation of COLLAPSE policies from section 3.4 of paper 848 * [1]. 849 * 850 * There are three different algorithms noted in the paper. We use 851 * the "New Algorithm". 852 * 853 * @param seq Sequence index. 854 * 855 * @return 856 * @retval 0 on success. 857 * @retval -1 quantiles not initialized. 858 * @retval -2 need an empty buffer for new operation. 859 * @retval -3 bad input sequence length in new operation. 860 * @retval -4 not enough buffers for collapse operation. 861 **/ 862 int 863 quantile_algorithm (uint16_t seq, double *input, int k) 864 { 865 int rc; 866 quantile_t *qp = NULL, *qp2 = NULL; 867 int min_level = -1; 869 /* This should always be true. */ 870 if (quantile_buffer_head[seq] != NULL) { 871 min_level = quantile_buffer_head[seq]->level; 872 } else { 873 return -1; 874 } 876 /* Get minimum level of all currently full buffers. */ 877 for (qp = quantile_buffer_head[seq]; qp != NULL; qp = qp->next) { 878 if (qp->weight != 0) { 879 /* Full buffer. */ 880 min_level = min(min_level, qp->level); 881 } 882 } 884 if (quantile_empty_buffers[seq] == 0) { 885 /* There are no empty buffers. Invoke COLLAPSE on the set 886 * of buffers with minimum level. */ 888 rc = quantile_collapse(seq, min_level); 889 if (rc < 0) 890 return rc; 891 } else if (quantile_empty_buffers[seq] == 1) { 892 /* We have exactly one empty buffer. Invoke NEW and assign 893 * it level `min_level'. */ 895 /* Search the empty buffer. */ 896 for (qp = quantile_buffer_head[seq]; qp != NULL; 897 qp = qp->next) { 898 if (qp->weight == 0) { 899 /* Found empty buffer. */ 900 break; 901 } 902 } 904 rc = quantile_new(seq, qp, input, k, min_level); 905 if (rc < 0) 906 return rc; 907 } else { 908 /* There are at least two empty buffers. Invoke NEW on each 909 * and assign level `0' to each. */ 911 /* Search for two empty buffers. */ 912 for (qp = quantile_buffer_head[seq]; qp != NULL; 913 qp = qp->next) { 914 if (qp->weight == 0) { 915 /* Found first empty buffer. */ 916 break; 917 } 918 } 919 for (qp2 = qp->next; qp2 != NULL; qp2 = qp2->next) { 920 if (qp2->weight == 0) { 921 /* Found second empty buffer. */ 922 break; 923 } 924 } 926 if (k <= quantile_k[seq]) { 927 /* This could happen if we call this after we 928 * received all packets but don't have enough to 929 * fill up two buffers. */ 931 rc = quantile_new(seq, qp, input, k, 0); 932 if (rc < 0) 933 return rc; 934 } else { 935 /* We have enough input data for two buffers. */ 936 rc = quantile_new(seq, qp, input, quantile_k[seq], 0); 937 if (rc < 0) 938 return rc; 939 rc = quantile_new(seq, qp2, input + quantile_k[seq], 940 k - quantile_k[seq], 0); 941 if (rc < 0) 942 return rc; 943 } 944 } 945 return 0; 946 } 948 int 949 quantile_init_seq(uint16_t seq) 950 { 951 quantile_t *qp = NULL; 952 int i; 954 if ( seq >= quantile_max_seq) 955 return -5; 957 /* Allocate memory for quantile buffers. Buffers are linked 958 * lists with a pointer to next buffer. We need `quantile_b' 959 * buffers, where each buffer has space for `quantile_k' 960 * elements. */ 961 for (i = 0; i < quantile_b[seq]; i++) { 962 if (i == 0) { 963 /* Initialize first buffer. */ 964 qp = malloc(sizeof(quantile_t)); 965 if (qp == NULL) { 966 return -1; 967 } 968 quantile_buffer_head[seq] = qp; 970 } else { 971 qp->next = malloc(sizeof(quantile_t)); 972 if (qp->next == NULL) { 973 return -1; 974 } 975 qp = qp->next; 976 } 978 /* `qp' points to buffer that should be initialized. */ 979 qp->next = NULL; 980 qp->weight = 0; /* empty buffers have weight of 0 */ 981 qp->level = 0; 982 qp->buffer = malloc(sizeof(double) * quantile_k[seq]); 983 if (qp->buffer == NULL) { 984 return -1; 985 } 986 } 987 /* Update number of empty quantile buffers. */ 988 quantile_empty_buffers[seq] = quantile_b[seq]; 990 return 0; 991 } 993 int 994 quantile_init (uint16_t max_seq, double eps, uint64_t N) 995 { 996 int b, b_tmp = 0; 997 int k, k_tmp = 0; 998 int h, h_max = 0; 999 int seq, rc; 1001 quantile_max_seq = max_seq; 1002 /* Allocate array for the requested number of sequences. */ 1003 quantile_k = calloc(max_seq, sizeof(int)); 1004 quantile_input = calloc(max_seq, sizeof(double*)); 1005 quantile_input_cnt = calloc(max_seq, sizeof(int)); 1006 quantile_empty_buffers = calloc(max_seq, sizeof(int)); 1007 quantile_b = calloc(max_seq, sizeof(int)); 1008 quantile_buf = calloc(max_seq, sizeof(double*)); 1009 quantile_alternate = calloc(max_seq, sizeof(int)); 1010 quantile_inf_cnt = calloc(max_seq, sizeof(uint64_t)); 1011 quantile_buffer_head = calloc(max_seq, sizeof(quantile_t*)); 1013 /* "In practice, optimal values for b and k can be computed by 1014 * trying out different values of b in the range 1 and 30." */ 1015 for (b = 2; b <= 30; b++) { 1016 /* For each b, compute the largest integral h that 1017 * satisfies: 1019 * (h-2) * C(b+h-2, h-1) - C(b+h-3, h-3) + 1020 * C(b+h-3, h-2) <= 2 * eps * N 1021 */ 1022 for (h = 0; ; h++) { 1023 if (((h-2) * binomial(b+h-2, h-1) - 1024 binomial(b+h-3, h-3) + 1025 binomial(b+h-3, h-2)) > 1026 (2 * eps * N)) { 1027 /* This h does not satisfy the inequality from 1028 * above. */ 1029 break; 1030 } 1031 h_max = h; 1032 } 1034 /* Now compute the smallest integral k that satisfies: 1035 * k * C(b+h-2, h-1) => N. */ 1036 k = ceil(N / (double)binomial(b+h_max-2, h_max-1)); 1038 /* Identify that b that minimizes b*k. */ 1039 if ((b_tmp == 0) && (k_tmp == 0)) { 1040 /* Initialize values */ 1041 b_tmp = b; 1042 k_tmp = k; 1043 } 1045 if ((b * k) < (b_tmp * k_tmp)) { 1046 /* Found b and k for which the product is smaller than 1047 * for the ones before. Because we want to minimize 1048 * b*k (required memory), we save them. */ 1049 b_tmp = b; 1050 k_tmp = k; 1051 } 1052 } 1054 /* Set global quantile values. For now, all sequences share 1055 the same k and b values.*/ 1056 for (seq = 0; seq < max_seq; seq++ ) { 1057 quantile_b[seq] = b_tmp; 1058 quantile_k[seq] = k_tmp; 1059 } 1061 /* Allocate memory for input buffer. We allocate enough space 1062 * to save up to `2 * quantile_k' elements. This space is 1063 * needed in the COLLAPSE policy if there are more than two 1064 * empty buffers. Because then we have to invoke NEW on two 1065 * buffers and thus need an input buffer with `2 * quantile_k' 1066 * elements. */ 1068 for (seq = 0; seq < quantile_max_seq; seq++) { 1069 quantile_input[seq] = malloc(sizeof(double) * 2 * 1070 quantile_k[seq]); 1071 if (quantile_input[seq] == NULL) { 1072 return -1; 1073 } 1074 quantile_input_cnt[seq] = 0; 1075 } 1077 /* Allocate memory for output buffer. This buffer is used in 1078 * COLLAPSE to store temporary output buffer before it gets 1079 * copied to one of the buffers used in COLLAPSE. */ 1080 for (seq = 0; seq < quantile_max_seq; seq++ ) { 1081 quantile_buf[seq] = malloc(sizeof(double) * quantile_k[seq]); 1082 if (quantile_buf[seq] == NULL) { 1083 return -1; 1084 } 1085 } 1087 for (seq = 0; seq < max_seq; seq++) { 1088 rc = quantile_init_seq(seq); 1089 if (rc < 0) 1090 return rc; 1091 } 1093 return 0; 1094 } 1096 int 1097 quantile_value_checkin(uint16_t seq, double value) 1098 { 1099 int rc = 0; 1101 if ( seq >= quantile_max_seq) 1102 return -5; 1104 quantile_input[seq][quantile_input_cnt[seq]++] = value; 1106 /* If we have at least two empty buffers, 1107 * we need input for two buffers, to twice 1108 * the value of `quantile_k'. */ 1109 if (quantile_empty_buffers[seq] >= 2) { 1110 if (quantile_input_cnt[seq] == 1111 (2 * quantile_k[seq])) { 1112 rc = quantile_algorithm(seq, quantile_input[seq], 1113 quantile_input_cnt[seq]); 1114 /* Reset counter. */ 1115 quantile_input_cnt[seq] = 0; 1117 } 1118 } else { 1119 /* There are 0 or 1 empty buffers */ 1120 if (quantile_input_cnt[seq] == quantile_k[seq]) { 1121 rc = quantile_algorithm(seq, quantile_input[seq], 1122 quantile_input_cnt[seq]); 1123 /* Reset counter. */ 1124 quantile_input_cnt[seq] = 0; 1125 } 1126 } 1127 return rc; 1128 } 1130 int 1131 quantile_finish(uint16_t seq) 1132 { 1133 int rc = 0; 1135 if ( seq >= quantile_max_seq) 1136 return -5; 1138 if (quantile_input_cnt[seq] > 0) { 1139 rc = quantile_algorithm(seq, quantile_input[seq], 1140 quantile_input_cnt[seq]); 1141 } 1142 return rc; 1143 } 1145 void 1146 quantile_reset(uint16_t seq) 1147 { 1148 quantile_input_cnt[seq] = 0; 1149 quantile_empty_buffers[seq] = quantile_b[seq]; 1150 memset(quantile_buf[seq],0,sizeof(double) * quantile_k[seq]); 1151 memset(quantile_input[seq],0,sizeof(double) * quantile_k[seq]); 1152 } 1154 /** 1155 * Deinitialize one quantile sequence. 1156 **/ 1157 void 1158 quantile_exit_seq(uint16_t seq) 1159 { 1160 quantile_t *qp = NULL, *next; 1162 if (seq >= quantile_max_seq) 1163 return; 1165 qp = quantile_buffer_head[seq]; 1166 while (qp != NULL) { 1167 /* Save pointer to next buffer. */ 1168 next = qp->next; 1170 /* Free buffer and list entry. */ 1171 free(qp->buffer); 1172 free(qp); 1174 /* Set current buffer to next one. */ 1175 qp = next; 1176 } 1178 quantile_buffer_head[seq] = NULL; 1179 quantile_input_cnt[seq] = 0; 1180 quantile_empty_buffers[seq] = quantile_b[seq]; 1181 } 1183 void 1184 quantile_exit(void) 1185 { 1186 int seq; 1188 /* Free per sequence structures */ 1189 for (seq = 0; seq < quantile_max_seq; seq++) { 1190 quantile_exit_seq(seq); 1192 /* Free output buffer. */ 1193 free(quantile_buf[seq]); 1195 /* Free input buffer. */ 1196 free(quantile_input[seq]); 1197 } 1199 free(quantile_buffer_head); 1200 free(quantile_inf_cnt); 1201 free(quantile_alternate); 1202 free(quantile_buf); 1203 free(quantile_b); 1204 free(quantile_empty_buffers); 1205 free(quantile_input_cnt); 1206 free(quantile_input); 1207 free(quantile_k); 1208 } 1210 int 1211 quantile_output (uint16_t seq, uint64_t npackets, double phi, 1212 double *result) 1214 { 1215 quantile_t *qp = NULL; 1216 int num_buffers = 0; 1217 int weight = 0; 1218 int j; 1219 long next_pos = 0; 1220 long merge_pos = 0; 1221 double min_dbl; 1222 double beta; 1223 double phi2; /* this is phi' */ 1225 if ( seq >= quantile_max_seq) 1226 return -5; 1228 /* Check that there are at least two full buffers with given 1229 * level. */ 1230 for (qp = quantile_buffer_head[seq]; qp != NULL; qp = qp->next) { 1231 if (qp->weight != 0) { 1232 num_buffers++; 1233 weight += qp->weight; 1234 qp->pos = 0; 1235 } else { 1236 qp->pos = -1; 1237 } 1238 } 1239 if (num_buffers < 2) { 1240 /* XXX: In section 3.3 "OUTPUT operation" of paper [1] is 1241 * says that OUTPUT takes c => 2 full input buffers. But 1242 * what if we just have one full input buffer? 1243 * 1244 * For example this happens if you run a UDP test with a 1245 * block size of 100k and a test duration of 3 seconds: $ 1246 * ./thrulay -u 100k -t 3 localhost 1247 */ 1249 if (num_buffers != 1) { 1250 return -1; 1251 } 1252 } 1254 /* Calculate beta and phi' */ 1255 beta = 1 + quantile_inf_cnt[seq] / (double)npackets; 1256 assert(beta >= 1.0); 1258 assert(phi >= 0.0 && phi <= 1.0); 1259 phi2 = (2 * phi + beta - 1) / (2 * beta); 1261 next_pos = ceil(phi2 * quantile_k[seq] * weight); 1262 /* XXX: If the client just sends a few packets, it is possible 1263 * that next_pos is too large. If this is the case, decrease 1264 * it. */ 1265 if (next_pos >= (num_buffers * quantile_k[seq])) { 1266 next_pos --; 1267 } 1269 while (1) { 1271 /* Search for current minimal element in all buffers. 1272 * Because buffers are all sorted, we just have to check 1273 * the element at current position. */ 1274 min_dbl = DBL_MAX; 1275 for (qp = quantile_buffer_head[seq]; qp != NULL; 1276 qp = qp->next) { 1277 /* Skip wrong buffers. */ 1278 if (qp->pos == -1) { 1279 continue; 1280 } 1282 /* Check that we are not at the end of buffer. */ 1283 if (qp->pos >= quantile_k[seq]) { 1284 continue; 1285 } 1287 /* Update minimum element. */ 1288 min_dbl = min(min_dbl, qp->buffer[qp->pos]); 1289 } 1291 /* Now process this minimal element in all buffers. */ 1292 for (qp = quantile_buffer_head[seq]; qp != NULL; 1293 qp = qp->next) { 1294 /* Skip wrong buffers. */ 1295 if (qp->pos == -1) { 1296 continue; 1297 } 1299 /* Now process minimal element in this buffer. */ 1300 for (; (qp->buffer[qp->pos] == min_dbl) && 1301 (qp->pos < quantile_k[seq]); 1302 qp->pos++) { 1304 /* Increment merge position `qp->weight' 1305 * times. If we pass the position we seek, 1306 * return current minimal element. */ 1307 for (j = 0; j < qp->weight; j++) { 1308 if (next_pos == merge_pos) { 1309 *result = min_dbl; 1310 return 0; 1311 } 1312 merge_pos++; 1313 } 1314 } 1315 } 1316 } 1318 /* NOTREACHED */ 1319 } 1321 #ifdef THRULAY_REPORTING_SAMPLE_LOOP 1323 #include 1324 #include 1326 #ifndef NAN 1327 #define _ISOC99_SOURCE 1328 #include 1329 #endif 1331 #define ERR_FATAL 0 1332 #define ERR_WARNING 1 1334 void __attribute__((noreturn)) 1335 quantile_alg_error(int rc) 1336 { 1337 switch (rc) { 1338 case -1: 1339 fprintf(stderr, "Error: quantiles not initialized."); 1340 break; 1341 case -2: 1342 fprintf(stderr, "Error: NEW needs an empty buffer."); 1343 break; 1344 case -3: 1345 fprintf(stderr, "Error: Bad input sequence length."); 1346 break; 1347 case -4: 1348 fprintf(stderr, "Error: Not enough buffers for COLLAPSE."); 1349 break; 1350 default: 1351 fprintf(stderr, "Error: Unknown quantile_algorithm error."); 1352 } 1353 exit(1); 1354 } 1356 /** 1357 * Will read a sample data file (first and only parameter) whose 1358 * lines give two values per line (per received packet): measured 1359 * packet delay and packet sequence number (in "%lf %lu" 1360 * format). As an exception, the first line specifies the number 1361 * of packets actually sent. 1362 * NOTE: The code as written assume there is no newline on the last 1363 * line. FIXME. 1364 * Example: 1365 * ---- 1366 10 1367 0.101 1 1368 0.109 2 1369 0.12 2 1370 0.10 4 1371 0.14 5 1372 0.15 6 1373 0.13 3 1374 0.09 7 1375 0.1 9 1376 0.091 8 1377 * ---- 1378 * 1379 * To compile this sample reporting main(): 1380 * 1381 * gcc -std=c99 -DTHRULAY_REPORTING_SAMPLE_LOOP reporting.c -lm 1382 * 1383 **/ 1384 int 1385 main(int argc, char *argv[]) 1386 { 1387 FILE *sf; 1388 /* 'Measured data' */ 1389 const int max_packets = 65535; 1390 /* 'Received' packets*/ 1391 int npackets = 0; 1392 uint64_t packet_sqn[max_packets]; /* Fill in with sample data */ 1393 double packet_delay[max_packets]; /* Fill in with sample data */ 1394 uint64_t packets_sent = 0; /* Fill in with sample data */ 1395 /* reordering */ 1396 const uint64_t reordering_max = 100; 1397 char buffer_reord[reordering_max * 80]; 1398 size_t r = 0; 1399 uint64_t j = 0; 1400 /* Stats */ 1401 uint64_t unique_packets = 0, packets_dup = 0; 1402 double quantile_25, quantile_50, quantile_75; 1403 double delay, jitter; 1404 double packet_loss; 1405 char report_buffer[1000]; 1406 /* Auxiliary variables */ 1407 int i, rc, rc2, rc3; 1409 memset(packet_sqn,0,sizeof(uint64_t)*max_packets); 1410 memset(packet_delay,0,sizeof(double)*max_packets); 1412 /* Inititalize duplication */ 1413 rc = duplication_init(max_packets); 1414 if (-1 == rc) { 1415 perror("calloc"); 1416 exit(1); 1417 } 1419 /* Initialize quantiles */ 1420 rc = quantile_init(1, QUANTILE_EPS, max_packets); 1421 if (-1 == rc) { 1422 perror("malloc"); 1423 exit(1); 1424 } 1426 /* Initialize reordering */ 1427 rc = reordering_init(reordering_max); 1428 if (-1 == rc) { 1429 perror("calloc"); 1430 exit(1); 1431 } 1433 /* Open sample file */ 1434 if (2 == argc) { 1435 sf = fopen(argv[1],"r"); 1436 } else { 1437 fprintf(stderr, "no input file\n"); 1438 exit(1); 1439 } 1441 /* Process sample input file. */ 1443 /* The sender somehow tells the receiver how many packets were 1444 actually sent. */ 1445 fscanf(sf,"%lu",&packets_sent); 1447 for (i = 0; i < max_packets && !feof(sf); i++) { 1449 fscanf(sf,"%lf %lu",&packet_delay[i],&packet_sqn[i]); 1450 /* Take care of common issue of ending the file with a 1451 newline; feof would not have been set but there is 1452 no more data. Assume delay of 0.0 means we're done. 1453 */ 1454 if (packet_delay[i] == 0.0) break; 1455 npackets++; 1457 /* 1458 * Duplication 1459 */ 1460 if (duplication_check(packet_sqn[i])) { 1461 /* Duplicated packet */ 1462 packets_dup++; 1463 continue; 1464 } else { 1465 /* Unique packet */ 1466 unique_packets++; 1467 } 1469 /* 1470 * Delay quantiles. 1471 */ 1472 rc = quantile_value_checkin(0, packet_delay[i]); 1473 if (rc < 0) 1474 quantile_alg_error(rc); 1476 /* 1477 * Reordering 1478 */ 1479 reordering_checkin(packet_sqn[i]); 1480 } 1482 /* 1483 * Perform last algorithm operation with a possibly not full 1484 * input buffer. 1485 */ 1486 rc = quantile_finish(0); 1487 if (rc < 0) 1488 quantile_alg_error(rc); 1490 rc = quantile_output(0, unique_packets, 0.25, &quantile_25); 1491 rc2 = quantile_output(0, unique_packets, 0.50, &quantile_50); 1492 rc3 = quantile_output(0, unique_packets, 0.75, &quantile_75); 1493 if (-1 == rc || -1 == rc2 || -1 == rc3) { 1494 fprintf(stderr,"An error occurred while computing delay " 1495 "quantiles. %d %d %d\n",rc, rc2, rc3); 1496 exit(1); 1497 } 1499 /* Delay and jitter computation */ 1500 packet_loss = packets_sent > unique_packets? 1501 (100.0*(packets_sent - unique_packets))/packets_sent: 0; 1503 delay = (packet_loss > 50.0)? INFINITY : quantile_50; 1504 if (packet_loss < 25.0 ) { 1505 jitter = quantile_75 - quantile_25; 1506 } else if (packet_loss > 75.0) { 1507 jitter = NAN; 1508 } else { 1509 jitter = INFINITY; 1510 } 1512 /* Format final report */ 1513 snprintf(report_buffer, sizeof(report_buffer), 1514 "Delay: %3.3fms\n" 1515 "Loss: %3.3f%%\n" 1516 "Jitter: %3.3fms\n" 1517 "Duplication: %3.3f%%\n" 1518 "Reordering: %3.3f%%\n", 1519 1000.0 * delay, 1520 packet_loss, 1521 1000.0 * jitter, 1522 100 * (double)packets_dup/npackets, 1523 100.0 * reordering_output(0)); 1525 printf("%s", report_buffer); 1527 /* Deallocate resources for statistics. */ 1528 reordering_exit(); 1529 quantile_exit(); 1530 duplication_exit(); 1532 fclose(sf); 1534 exit(0); 1535 } 1537 #endif /* THRULAY_REPORTING_SAMPLE_LOOP */ 1539 Appendix B. Example Report 1541 This appendix only serves for illustrative purposes. 1543 This report is produced by running the sample program in Appendix A 1544 on the sample input embedded in a comment in its source code: 1546 Delay: 109.000ms 1547 Loss: 10.000% 1548 Jitter: 40.000ms 1549 Duplication: 10.000% 1550 Reordering: 22.222% 1552 Authors' Addresses 1554 Stanislav Shalunov 1556 Email: shalunov@shlang.com 1557 URI: http://shlang.com/ 1559 Martin Swany 1560 University of Delaware 1561 Department of Computer and Information Sciences 1562 Newark, DE 19716 1563 US 1565 Email: swany@cis.udel.edu 1566 URI: http://www.cis.udel.edu/~swany/