idnits 2.17.1 draft-ietf-ippm-reordering-13.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 18. -- Found old boilerplate from RFC 3978, Section 5.5 on line 2038. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 2049. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 2056. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 2062. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. == There is 1 instance of lines with non-ascii characters in the document. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 1814 has weird spacing: '...tic int ring[...' == Line 1815 has weird spacing: '...tic int r = 0...' == Line 1816 has weird spacing: '... int l = ...' == Line 1817 has weird spacing: '... int j;...' == Line 1818 has weird spacing: '... int iRetu...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- Couldn't find a document date in the document -- date freshness check skipped. -- 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) == Missing Reference: 'RFC2640' is mentioned on line 159, but not defined -- Looks like a reference, but probably isn't: '1' on line 1365 -- Looks like a reference, but probably isn't: '2' on line 983 == Missing Reference: 'L' is mentioned on line 1249, but not defined -- Looks like a reference, but probably isn't: '9' on line 1378 == Missing Reference: 'MAXN' is mentioned on line 1814, but not defined == Unused Reference: 'RFC2460' is defined on line 1600, but no explicit reference was found in the text ** Downref: Normative reference to an Informational RFC: RFC 2330 ** Obsolete normative reference: RFC 2460 (Obsoleted by RFC 8200) ** Downref: Normative reference to an Informational RFC: RFC 3148 ** Downref: Normative reference to an Informational RFC: RFC 3763 ** Obsolete normative reference: RFC 4148 (Obsoleted by RFC 6248) -- Possible downref: Non-RFC (?) normative reference: ref. 'RFCyyyy' -- Obsolete informational reference (is this intentional?): RFC 793 (Obsoleted by RFC 9293) -- Obsolete informational reference (is this intentional?): RFC 1323 (Obsoleted by RFC 7323) -- Obsolete informational reference (is this intentional?): RFC 2581 (Obsoleted by RFC 5681) -- Obsolete informational reference (is this intentional?): RFC 2679 (Obsoleted by RFC 7679) -- Obsolete informational reference (is this intentional?): RFC 2680 (Obsoleted by RFC 7680) -- Obsolete informational reference (is this intentional?): RFC 2960 (Obsoleted by RFC 4960) Summary: 9 errors (**), 0 flaws (~~), 11 warnings (==), 18 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group A.Morton 3 Internet Draft L.Ciavattone 4 Document: G.Ramachandran 5 Category: Standards Track AT&T Labs 6 S.Shalunov 7 Internet2 8 J.Perser 9 Veriwave 11 Packet Reordering Metric for IPPM 13 Status of this Memo 15 By submitting this Internet-Draft, each author represents that any 16 applicable patent or other IPR claims of which he or she is aware 17 have been or will be disclosed, and any of which he or she becomes 18 aware will be disclosed, in accordance with Section 6 of BCP 79. 20 This document is an Internet-Draft and is subject to all provisions 21 of section 3 of BCP 78. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF), its areas, and its working groups. Note that 25 other groups may also distribute working documents as Internet- 26 Drafts. 28 Internet-Drafts are draft documents valid for a maximum of six 29 months and may be updated, replaced, or obsoleted by other documents 30 at any time. It is inappropriate to use Internet-Drafts as 31 reference material or to cite them other than as "work in progress." 33 The list of current Internet-Drafts can be accessed at 34 http://www.ietf.org/ietf/1id-abstracts.txt 36 The list of Internet-Draft Shadow Directories can be accessed at 37 http://www.ietf.org/shadow.html. 39 Copyright Notice 41 Copyright (C) The Internet Society (2006). 43 Abstract 45 This memo defines metrics to evaluate if a network has maintained 46 packet order on a packet-by-packet basis. It provides motivations 47 for the new metrics and discusses the measurement issues, including 48 the context information required for all metrics. The memo first 49 defines a reordered singleton, and then uses it as the basis for 50 sample metrics to quantify the extent of reordering in several 51 useful dimensions for network characterization or receiver design. 52 Additional metrics quantify the frequency of reordering and the 53 distance between separate occurrences. We then define a metric 54 oriented toward assessing reordering effects on TCP. Several 55 examples of evaluation using the various sample metrics are 56 included. An Appendix gives extended definitions for evaluating 57 order with packet fragmentation. 59 Contents 61 Status of this Memo................................................1 62 Copyright Notice...................................................1 63 Abstract...........................................................1 64 1. Conventions Used in this Document...............................3 65 2. Introduction....................................................4 66 2.1 Motivation.....................................................4 67 2.2 Goals and Objectives...........................................5 68 2.3 Required Context for All Reordering Metrics....................6 69 3. A Reordered Packet Singleton Metric.............................6 70 3.1 Metric Name....................................................7 71 3.2 Metric Parameters..............................................7 72 3.3 Definition.....................................................8 73 3.4 Sequence Discontinuity Definition..............................8 74 3.5 Evaluation of Reordering in Dimensions of Time or Bytes........9 75 3.6 Discussion.....................................................9 76 4. Sample Metrics.................................................10 77 4.1 Reordered Packet Ratio........................................10 78 4.1.1 Metric Name.................................................10 79 4.1.2 Metric Parameters...........................................10 80 4.1.3 Definition..................................................11 81 4.1.4 Discussion..................................................11 82 4.2 Reordering Extent.............................................11 83 4.2.1 Metric Name.................................................11 84 4.2.2 Notation and Metric Parameters..............................11 85 4.2.3 Definition..................................................12 86 4.2.4 Discussion..................................................12 87 4.3 Reordering Late Time Offset...................................13 88 4.3.1 Metric Name.................................................13 89 4.3.2 Metric Parameters...........................................13 90 4.3.3 Definition..................................................14 91 4.3.4 Discussion..................................................14 92 4.4 Reordering Byte Offset........................................15 93 4.4.1 Metric Name.................................................15 94 4.4.2 Metric Parameters...........................................15 95 4.4.3 Definition..................................................15 96 4.4.4 Discussion..................................................15 97 4.5 Gaps between multiple Reordering Discontinuities..............16 98 4.5.1 Metric Names................................................16 99 4.5.2 Parameters..................................................16 100 4.5.3 Definition of Reordering Discontinuity......................16 101 4.5.4 Definition of Reordering Gap................................16 102 4.5.5 Discussion..................................................17 103 4.6 Reordering-free Runs..........................................17 104 4.6.1 Metric Names................................................18 105 4.6.2 Parameters..................................................18 106 4.6.3 Definition..................................................18 107 4.6.4 Discussion and Illustration.................................19 108 5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric..19 109 5.1 Metric Name...................................................20 110 5.2 Parameter Notation............................................20 111 5.3 Definitions...................................................20 112 5.4 Discussion....................................................21 113 6. Measurement and Implementation Issues..........................21 114 6.1 Passive Measurement Considerations............................24 115 7. Examples of Arrival Order Evaluation...........................25 116 7.1 Example with a Single Packet Reordered........................25 117 7.2 Example with Two Packets Reordered............................26 118 7.3 Example with Three Packets Reordered..........................28 119 7.4 Example with Multiple Packet Reordering Discontinuities.......29 120 8. Security Considerations........................................29 121 8.1 Denial of Service Attacks.....................................29 122 8.2 User Data Confidentiality.....................................30 123 8.3 Interference with the Metric..................................30 124 9. IANA Considerations............................................30 125 10. Normative References..........................................32 126 11. Informative References........................................33 127 12. Acknowledgments...............................................35 128 13. Appendix A Example Implementations in C (Informative).........35 129 14. Appendix B Fragment Order Evaluation (Informative)............38 130 14.1 Metric Name..................................................38 131 14.2 Additional Metric Parameters.................................38 132 14.3 Definition...................................................38 133 14.4 Discussion: Notes on Sample Metrics when Evaluating Fragments40 134 15. Disclaimer and License........................................40 135 16. Author's Addresses............................................40 136 Full Copyright Statement..........................................41 137 Intellectual Property.............................................41 138 Acknowledgement...................................................42 140 1. Conventions Used in this Document 142 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 143 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 144 document are to be interpreted as described in [RFC2119]. Although 145 RFC 2119 was written with protocols in mind, the key words are used 146 in this document for similar reasons. They are used to ensure the 147 results of measurements from two different implementations are 148 comparable, and to note instances when an implementation could 149 perturb the network. 151 In this memo, the characters "<=" should be read as "less than or 152 equal to" and ">=" as "greater than or equal to". 154 2. Introduction 156 Ordered arrival is a property found in packets that transit their 157 path, where the packet sequence number increases with each new 158 arrival and there are no backward steps. The Internet Protocol 159 [RFC791] [RFC2640] has no mechanisms to assure either packet 160 delivery or sequencing, and higher layer protocols (above IP) should 161 be prepared to deal with both loss and reordering. This memo defines 162 reordering metrics. 164 A unique sequence identifier carried in each packet, such as an 165 incrementing consecutive integer message number, establishes the 166 Source Sequence. 168 The detection of reordering at the Destination is based on packet 169 arrival order in comparison with a non-reversing reference value 170 [Cia03]. 172 This metric is consistent with [RFC2330], and classifies arriving 173 packets with sequence numbers smaller than their predecessors as 174 out-of-order, or reordered. For example, if sequentially numbered 175 packets arrive 1,2,4,5,3, then packet 3 is reordered. This is 176 equivalent to Paxon's reordering definition in [Pax98], where "late" 177 packets were declared reordered. The alternative is to emphasize 178 "premature" packets instead (4 and 5 in the example), but only the 179 arrival of packet 3 distinguishes this circumstance from packet 180 loss. Focusing attention on late packets allows us to maintain 181 orthogonality with the packet loss metric. The metric's construction 182 is very similar to the sequence space validation for received 183 segments in [RFC793]. Earlier work to define ordered delivery 184 includes [Cia00], [Ben99], [Lou01], [Bel02], [Jai02] and [Cia03]. 186 2.1 Motivation 188 A reordering metric is relevant for most applications, especially 189 when assessing network support for Real-Time media streams. The 190 extent of reordering may be sufficient to cause a received packet to 191 be discarded by functions above the IP layer. 193 Packet order may change during transfer, and several specific path 194 characteristics can make reordering more likely. 196 Examples are: 197 * When two (or more) paths with slightly differing transfer times 198 support a single packet stream or flow, then packets traversing 199 the longer path(s) may arrive out-of-order. Multiple paths may be 200 used to achieve load balancing, or may arise from route 201 instability. 203 * To increase capacity, a network device designed with multiple 204 processors serving a single port (or parallel links) may reorder 205 as a byproduct. 206 * A layer 2 retransmission protocol that compensates for an error- 207 prone link may cause packet reordering. 208 * If for any reason, the packets in a buffer are not serviced in the 209 order of their arrival, their order will change. 210 * If packets in a flow are assigned to multiple buffers (following 211 evaluation of traffic characteristics, for example), and the 212 buffers have different occupations and/or service rates, then 213 order will likely change. 215 When one or more of the above path characteristics are present 216 continuously, then reordering may be present on a steady-state 217 basis. The steady-state reordering condition typically causes an 218 appreciable fraction of packets to be reordered. This form of 219 reordering is most easily detected by minimizing the spacing between 220 test packets. Transient reordering may occur in response to network 221 instability; temporary routing loops can cause periods of extreme 222 reordering. This condition is characterized by long in-order streams 223 with occasional instances of reordering, sometimes with extreme 224 correlation. However, we do not expect packet delivery in a 225 completely random order, where for example, the last packet or the 226 first packet in a sample is equally likely to arrive first at the 227 destination. Thus we expect at least a minimal degree of order in 228 the packet arrivals, as exhibited in real networks. 230 The ability to restore order at the destination will likely have 231 finite limits. Practical hosts have receiver buffers with finite 232 size in terms of packets, bytes, or time (such as de-jitter 233 buffers). Once the initial determination of reordering is made, it 234 is useful to quantify the extent of reordering, or lateness, in all 235 meaningful dimensions. 237 2.2 Goals and Objectives 239 The definitions below intend to satisfy the goals of: 241 1. Determining whether or not packet reordering has occurred. 242 2. Quantifying the degree of reordering. (We define a number of 243 metrics to meet this goal, because receiving procedures differ 244 by protocol or application. Since the effects of packet 245 reordering vary with these procedures, a metric that quantifies 246 a key aspect of one receiver's behavior could be irrelevant to 247 a different receiver. If all the metrics defined below are 248 reported, they give a wide-ranging view of reordering 249 conditions.) 251 Reordering Metrics MUST: 253 + have one or more applications, such as receiver design or network 254 characterization, and a compelling relevance in the view of the 255 interested community. 256 + be computable "on the fly" 257 + work even if the stream has duplicate or lost packets 259 It is desirable for Reordering Metrics to have one or more of the 260 following attributes: 262 + ability to concatenate results for segments measured separately 263 to estimate the reordering of an entire path 264 + simplicity for easy consumption and understanding 265 + relevance to TCP design 266 + relevance to Real-time application performance 268 The current set of metrics meets all the requirements above and 269 provides all but the concatenation attribute (except in the case 270 where measurements of path segments exhibit no reordering, and one 271 may estimate that the complete path composed of these segments would 272 also exhibit no reordering). However, satisfying these goals 273 restricts the set of metrics to those that provide some clear 274 insight into network characterization or receiver design. They are 275 not likely to be exhaustive in their coverage of reordering effects 276 on applications, and additional measurements may be possible. 278 2.3 Required Context for All Reordering Metrics 280 A critical aspect of all reordering metrics is their inseparable 281 bond with the measurement conditions. Packet reordering is not well 282 defined unless the full measurement context is reported. Therefore, 283 all reordering metric definitions include the following parameters: 285 1. The "Packet of Type-P" [RFC2330] identifiers for the packet 286 stream, including the transport addresses for source and 287 destination, and any other information which may result in different 288 packet treatments. 290 2. The stream parameter set for the sending discipline, such as the 291 parameters unique to Periodic Streams (as in [RFC3432]), TCP-like 292 Streams (as in [RFC3148]), or Poisson Streams (as in [RFC2330]). The 293 stream parameters include the packet size, either specified as a 294 fixed value or as a pattern of sizes (as applicable). 296 Whenever a metric is reported, it MUST include a description of 297 these parameters to provide a context for the results. 299 3. A Reordered Packet Singleton Metric 301 The IPPM framework [RFC2330] describes the notions of singletons, 302 samples, and statistics. For easy reference: 304 By a 'singleton' metric, we refer to metrics that are, 305 in a sense, atomic. For example, a single instance of "bulk 306 throughput capacity" from one host to another might be defined 307 as a singleton metric, even though the instance involves 308 measuring the timing of a number of Internet packets. 310 The evaluation of packet order requires several supporting concepts. 311 The first is an algorithm (function) that produces a series of 312 strictly monotonically increasing identifiers applied to packets at 313 the source to uniquely establish the order of packet transmission 314 (where a function, g(x), is strictly monotonically increasing if for 315 any x>y, g(x)>g(y) ). The unique sequence identifier may simply be 316 an incrementing consecutive integer message number, or sequence 317 number as used below. The prospect of sequence number roll-over is 318 discussed in Section 6. 320 The second supporting concept is a stored value which is the "next 321 expected" packet number. Under normal conditions, the value of Next 322 Expected (NextExp) is the sequence number of the previous packet 323 plus 1 for message numbering (in general, the receiver reproduces 324 the sender's algorithm and the sequence of identifiers so that the 325 "next expected" can be determined). 327 Each packet within a packet stream can be evaluated with this order 328 singleton metric. 330 3.1 Metric Name 332 Type-P-Reordered 334 3.2 Metric Parameters 336 + Src, the IP address of a host 338 + Dst, the IP address of a host 340 + SrcTime, the time of packet emission from the Source (or wire 341 time) 343 + s, the unique packet sequence number applied at the Source, in 344 units of messages. 346 + NextExp, the Next Expected Sequence number at the Destination, in 347 units of messages. The stored value in NextExp is determined from 348 a previously arriving packet. 350 And optionally: 352 + PayloadSize, the number of bytes contained in the information 353 field and referred to when the SrcByte sequence is based on bytes 354 transfered. 356 + SrcByte, the packet sequence number applied at the Source, in 357 units of payload bytes. 359 3.3 Definition 361 If a packet s, (sent at time, SrcTime) is found to be reordered by 362 comparison with the Next Expected value, its Type-P-Reordered = 363 TRUE; otherwise Type-P-Reordered = FALSE, as defined below: 365 The value of Type-P-Reordered is defined as TRUE if s < NextExp (the 366 packet is reordered). In this case, the NextExp value does not 367 change. 369 The value of Type-P-Reordered is defined as FALSE if s >= NextExp 370 (the packet is in-order). In this case, NextExp is set to s+1 for 371 comparison with the next packet to arrive. 373 Since the Next Expected value cannot decrease, it provides a non- 374 reversing order criterion to identify reordered packets. 376 This definition can also be specified in pseudo-code. 378 On successful arrival of a packet with sequence number s: 379 if s >= NextExp then /* s is in-order */ 380 NextExp = s + 1; 381 Type-P-Reordered = False; 382 else /* when s < NextExp */ 383 Type-P-Reordered = True 385 3.4 Sequence Discontinuity Definition 387 Packets with s > NextExp are a special case of in-order delivery. 388 This condition indicates a sequence discontinuity, either because of 389 packet loss or reordering. Reordered packets must arrive for the 390 sequence discontinuity to be defined as a reordering discontinuity 391 (see section 4). 393 We define two different states for in-order packets. 395 When s = NextExp, the original sequence has been maintained, and 396 there is no discontinuity present. 398 When s > NextExp, some packets in the original sequence have not yet 399 arrived, and there is a sequence discontinuity associated with 400 packet s. The size of the discontinuity is s - NextExp, equal to 401 the number of packets presently missing, either reordered or lost. 403 In pseudo-code: 405 On successful arrival of a packet with sequence number s: 406 if s >= NextExp, then /* s is in-order */ 407 if s > NextExp then 408 SequenceDiscontinuty = True; 409 SeqDiscontinutySize = s - NextExp; 410 else 411 SequenceDiscontinuty = False; 412 NextExp = s + 1; 413 Type-P-Reordered = False; 415 else /* when s < NextExp */ 416 Type-P-Reordered = True; 417 SequenceDiscontinuty = False; 419 Whether any Sequence Discontinuities occur (and their size) is 420 determined by the conditions causing loss and/or reordering along 421 the measurement path. Note that a packet could be reordered at one 422 point, and subsequently lost elsewhere on the path, but this cannot 423 be known from observations at the Destination. 425 3.5 Evaluation of Reordering in Dimensions of Time or Bytes 427 It is possible to use alternate dimensions of time or payload bytes 428 to test for reordering in the definition of section 3.3, as long as 429 the SrcTimes and SrcBytes are unique and reliable. Sequence 430 Discontinuities are easily defined and detected with message 431 numbering, however, this is not so simple in the dimensions of time 432 or bytes. This is a detractor for the alternate dimensions because 433 the Sequence Discontinuity definition plays a key role in the sample 434 metrics that follow. 436 It is possible to detect Sequence Discontinuities with payload byte 437 numbering, but only when the test device knows exactly what value to 438 assign as NextExp in response to any packet arrival. This is 439 possible when the complete pattern of payload sizes is stored at the 440 Destination, or if the size pattern can be generated using a pseudo- 441 random number generator and a shared seed. If payload size is 442 constant, byte numbering adds needless complexity over message 443 numbering. 445 It may be possible to detect Sequence Discontinuities with Periodic 446 Streams and Source Time numbering, but there are practical pitfalls 447 with sending exactly on-schedule and with clock reliability. 449 The dimensions of time and bytes remain an important basis for 450 characterizing the extent of reordering, as described in sections 451 4.3 and 4.4. 453 3.6 Discussion 455 Any arriving packet bearing a sequence number from the sequence that 456 establishes the Next Expected value can be evaluated to determine 457 whether it is in-order or reordered, based on a previous packet's 458 arrival. In the case where Next Expected is Undefined (because the 459 arriving packet is the first successful transfer), the packet is 460 designated in-order (Type-P-Reordered=FALSE). 462 This metric assumes re-assembly of packet fragments before 463 evaluation. In principle, it is possible to use the Type-P-Reordered 464 metric to evaluate reordering among packet fragments, but each 465 fragment must contain source sequence information. 466 See the Appendix on fragment order evaluation for more detail. 468 If duplicate packets (multiple non-corrupt copies) arrive at the 469 destination, they MUST be noted and only the first to arrive is 470 considered for further analysis (copies would be declared reordered 471 according to the definition above). This requirement has the same 472 storage implications as earlier IPPM metrics, and follows the 473 precedent of [RFC2679]. We provide a suggestion to minimize storage 474 size needed in Section 6 on Measurement and Implementation Issues. 476 4. Sample Metrics 478 In this section, we define metrics applicable to a sample of packets 479 from a single Source sequence number system. When reordering occurs, 480 it is highly desirable to assert the degree to which a packet is 481 out-of-order, or reordered with respect other packets. This section 482 defines several metrics that quantify the extent of reordering in 483 various units of measure. Each metric highlights a relevant use. 485 The metrics in the sub-sections below have a network 486 characterization orientation, but also have relevance to receiver 487 design where reordering compensation is of interest. We begin with a 488 simple ratio metric indicating the reordered portion of the sample. 490 4.1 Reordered Packet Ratio 492 4.1.1 Metric Name 494 Type-P-Reordered-Ratio-Stream 496 4.1.2 Metric Parameters 498 The parameter set includes Type-P-Reordered singleton parameters, 499 the parameters unique to Poisson Streams (as in [RFC2330], Periodic 500 Streams (as in [RFC3432]), or TCP-like Streams (as in [RFC3148]), 501 packet size or size patterns, and the following: 503 + T0, a start time 505 + Tf, an end time 507 + dT, a waiting time for each packet to arrive, in seconds 508 + K, the total number of packets in the stream sent from Source to 509 Destination 511 + L, the total number of packets received (arriving between T0 and 512 Tf+dT) out of the K packets sent. Recall that identical copies 513 (duplicates) have been removed, so L <= K. 515 + R, the ratio of reordered packets to received packets, defined 516 below 518 Note that parameter dT is effectively the threshold for declaring a 519 packet as lost. The IPPM Packet Loss Metric [RFC2680] declines to 520 recommend a value for this threshold, saying instead that "good 521 engineering, including an understanding of packet lifetimes, will be 522 needed in practice." 524 4.1.3 Definition 526 Given a stream of packets sent from a Source to a Destination, the 527 ratio of reordered packets in the sample is 529 R = (Count of packets with Type-P-Reordered=TRUE) / ( L ) 531 This fraction may be expressed as a percentage (multiply by 100). 532 Note that in the case of duplicate packets, only the first copy is 533 used. 535 4.1.4 Discussion 537 When the Type-P-Reordered-Ratio-Stream is zero, no further 538 reordering metrics need be examined for that sample. Therefore, the 539 value of this metric is its simple ability to summarize the results 540 for a reordering-free sample. 542 4.2 Reordering Extent 544 This section defines the extent to which packets are reordered, and 545 associates a specific Sequence Discontinuity with each reordered 546 packet. This section inherits the Parameters defined above. 548 4.2.1 Metric Name 550 Type-P-Packet-Reordering-Extent-Stream 552 4.2.2 Notation and Metric Parameters 554 Recall that K is the number of packets in the stream at the Source 555 and L is the number of packets received at the Destination. 557 Each packet has been assigned a sequence number, s, a consecutive 558 integer from 1 to K in the order of packet transmission (at the 559 source). 561 Let s[1], s[2], ..., s[L], represent the original sequence numbers 562 associated with the packets in order of arrival. 564 s[i] can be thought of as a vector, where the index i is the arrival 565 position of the packet with sequence number s. In theory, any 566 Source sequence number could appear in any arrival position, but 567 this is unlikely in reality. 569 Consider a reordered packet (Type-P-Reordered=TRUE) with arrival 570 index i and source sequence number s[i]. There exists a set of 571 indexes j (1 <= j < i) such that s[j] > s[i]. 573 The new parameters are: 575 + i, the index for arrival position, where i-1 represents an 576 arrival earlier than i. 578 + j, a set of one or more arrival indexes, where 1 <= j < i. 580 + s[i], the original sequence numbers, s, in order of arrival. 582 + e, the Reordering Extent, in units of packets, defined below. 584 4.2.3 Definition 586 The reordering extent, e, of packet s[i] is defined to be i-j for 587 the smallest value of j where s[j] > s[i]. 589 Informally, the reordering extent is the maximum distance, in 590 packets, from a reordered packet to the earliest packet received 591 that has a larger sequence number. If a packet is in-order, its 592 reordering extent is undefined. The first packet to arrive is in- 593 order by definition, and has undefined reordering extent. 595 Comment on the definition of extent: For some arrival orders, the 596 assignment of a simple position/distance as the reordering extent 597 tends to overestimate the receiver storage needed to restore order. 598 A more accurate and complex procedure to calculate packet storage 599 would be to subtract any earlier reordered packets that the receiver 600 could pass on to the upper layers (see the Byte Offset metric). With 601 the bias understood, this definition is deemed sufficient, 602 especially for those who demand "on the fly" calculations. 604 4.2.4 Discussion 605 The packet with index j (s[j], identified in the Definition above) 606 is the reordering discontinuity associated with packet s at index i 607 (s[i]). This definition is formalized below. 609 Note that the K packets in the stream could be some subset of a 610 larger stream, but L is still the total number of packets received 611 out of the K packets sent in that subset. 613 If a receiver intends to restore order, then its buffer capacity 614 determines its ability to handle packets that are reordered. For 615 cases with single reordered packets, the extent e gives the number 616 of packets that must be held in the receiver's buffer while waiting 617 for the reordered packet to complete the sequence. For more complex 618 scenarios, the extent may be an overestimate of required storage 619 (see section 4.4 on Reordering Byte Offset and the Examples 620 section). Also, if the receiver purges its buffer for any reason, 621 the extent metric would not reflect this behavior, assuming instead 622 that the receiver would exhaustively attempt to restore order. 624 Although reordering extent primarily quantifies the offset in terms 625 of arrival position, it may also be useful for determining the 626 portion of reordered packets that can or cannot be restored to order 627 in a typical receiver buffer based on their arrival order alone (and 628 without the aid of retransmission). 630 A sample's reordering extents may be expressed as a histogram, to 631 easily summarize the frequency of various extents. 633 4.3 Reordering Late Time Offset 635 Reordered packets can be assigned offset values indicating their 636 lateness in terms of buffer time that a receiver must possess to 637 accommodate them. Offset metrics are calculated only on reordered 638 packets, as identified by the reordered packet singleton metric in 639 Section 3. 641 4.3.1 Metric Name 643 Type-P-Packet-Late-Time-Stream 645 4.3.2 Metric Parameters 647 In addition to the parameters defined for Type-P-Reordered-Ratio- 648 Stream, we specify: 650 + DstTime, the time that each packet in the stream arrives at the 651 destination, and may be associated with index i, or packet s[i] 653 + LateTime(s[i]), the offset of packet s[i] in units of seconds, 654 defined below 656 4.3.3 Definition 658 Lateness in time is calculated using destination times. When 659 received packet s[i] is reordered, and has a reordering extent e, 660 then: 662 LateTime(s[i]) = DstTime(i)-DstTime(i-e) 664 Alternatively, using similar notation to that of section 4.2, an 665 equivalent definition is: 667 LateTime(s[i]) = DstTime(i)-DstTime(j), for min{j|1<=js[i]. 670 4.3.4 Discussion 672 The offset metrics can help predict whether reordered packets will 673 be useful in a general receiver buffer system with finite limits. 674 The limit may be the time of storage prior to a cyclic play-out 675 instant (as with de-jitter buffers). 677 Note that the One-way IPDV [RFC3393] gives the delay variation for a 678 packet w.r.t. the preceding packet in the source sequence. Lateness 679 and IPDV give an indication of whether a buffer at the destination 680 has sufficient storage to accommodate the network's behavior and 681 restore order. When an earlier packet in the Source sequence is 682 lost, IPDV will necessarily be undefined for adjacent packets, and 683 LateTime may provide the only way to evaluate the usefulness of a 684 packet. 686 In the case of de-jitter buffers, there are circumstances where the 687 receiver employs loss concealment at the intended play-out time of a 688 late packet. However, if this packet arrives out of order, the Late 689 Time determines whether the packet is still useful. IPDV no longer 690 applies, because the receiver establishes a new play-out schedule 691 with additional buffer delay to accommodate similar events in the 692 future (this requires very minimal processing). 694 The combination of loss and reordering influences the LateTime 695 metric. If presented with the arrival sequence 1, 10, 5 (where 696 packets 2, 3, 4, and 6 through 9 are lost), LateTime would not 697 indicate exactly how "late" packet 5 is from its intended arrival 698 position. IPDV [RFC3393] would not capture this either, because of 699 the lack of adjacent packet pairs. Assuming a Periodic Stream 700 [RFC3432], an expected arrival time could be defined for all 701 packets, but this is essentially a single-point delay variation 702 metric (as defined in ITU-T Recommendations [I.356] and [Y.1540]), 703 and not a reordering metric. 705 A sample's LateTime results may be expressed as a histogram, to 706 summarize the frequency of buffer times needed to accommodate 707 reordered packets and permit buffer tuning on that basis. A CDF with 708 buffer time vs. percent of reordered packets accommodated may be 709 informative. 711 4.4 Reordering Byte Offset 713 Reordered packets can be assigned offset values indicating the 714 storage in bytes that a receiver must possess to accommodate them. 715 Offset metrics are calculated only on reordered packets, as 716 identified by the reordered packet singleton metric in Section 3. 718 4.4.1 Metric Name 720 Type-P-Packet-Byte-Offset-Stream 722 4.4.2 Metric Parameters 724 We use the same parameters defined earlier, including the optional 725 parameters of SrcByte and PayloadSize, and define: 727 + ByteOffset(s[i]), the offset of packet s[i] in bytes 729 4.4.3 Definition 731 The Byte stream offset for reordered packet s[i] is the sum of the 732 payload sizes of packets qualified by the following criteria: 734 * Arrival prior to the reordered packet, s[i], and 736 * The send sequence number, s, is greater than s[i]. 738 Packets that meet both these criteria are normally buffered until 739 the sequence beneath them is complete. Note that these criteria 740 apply to both in-order and reordered packets. 742 For reordered packet s[i] with a reordering extent e: 743 ByteOffset(s[i]) = Sum[qualified packets] 744 = Sum[PayloadSize(packet at i-1 if qualified), 745 PayloadSize(packet at i-2 if qualified), ... 746 PayloadSize(packet at i-e always qualified)] 748 Using our earlier notation: 749 ByteOffset(s[i]) = 750 Sum[payloads of s[j] where s[j]>s[i] and i > j >= i-e] 752 4.4.4 Discussion 754 We note that estimates of buffer size due to reordering depend 755 greatly on the test stream, in terms of the spacing between test 756 packets and their size, especially when packet size is variable. In 757 these and other circumstances, it may be most useful to characterize 758 offset in terms of the payload size(s) of stored packets, using the 759 Type-P-packet-Byte-Offset-Stream metric. 761 The byte offset metric can help predict whether reordered packets 762 will be useful in a general receiver buffer system with finite 763 limits. The limit is expressed as the number of bytes the buffer 764 can store. 766 A sample's ByteOffset results may be expressed as a histogram, to 767 summarize the frequency of buffer lengths needed to accommodate 768 reordered packets and permit buffer tuning on that basis. A CDF with 769 buffer size vs. percent of reordered packets accommodated may be 770 informative. 772 4.5 Gaps between multiple Reordering Discontinuities 774 4.5.1 Metric Names 776 Type-P-Packet-Reordering-Gap-Stream 777 Type-P-Packet-Reordering-GapTime-Stream 779 4.5.2 Parameters 781 We use the same parameters defined earlier, but add the convention 782 that index i' is greater than i, likewise j' > j, and define: 784 + Gap(s[j']), the Reordering Gap of packet s[j'] in units of 785 integer messages 787 and the OPTIONAL parameter: 789 + GapTime(s[j']), the Reordering Gap of packet s[j'] in units of 790 seconds 792 4.5.3 Definition of Reordering Discontinuity 794 All reordered packets are associated with a packet at a reordering 795 discontinuity, defined as the in-order packet s[j] that arrived at 796 the minimum value of j (1<=j s[i]. 798 Note that s[j] will have been found to cause a sequence 799 discontinuity, where s > NextExp when evaluated with the reordered 800 singleton metric as described in section 3.4. 802 Recall that i - e = min(j). Subsequent reordered packets may be 803 associated with the same s[j], or with a different discontinuity. 804 This fact is used in the definition of the Reordering Gap, below. 806 4.5.4 Definition of Reordering Gap 807 A reordering gap is the distance between successive reordering 808 discontinuities. The Type-P-Packet-Reordering-Gap-Stream metric 809 assigns a value for Gap(s[j']) to (all) packets in a stream (and a 810 value for GapTime(s[j']), when reported). 812 If: 814 The packet s[j'] is found to be a reordering discontinuity, based 815 on the arrival of reordered packet s[i'] with extent e', and 817 an earlier reordering discontinuity s[j], based on the arrival of 818 reordered packet s[i] with extent e was already detected, and 820 i' > i, and 822 there are no reordering discontinuities between j and j', 824 then the Reordering Gap for packet s[j'] is the difference between 825 the arrival positions the reordering discontinuities, as shown 826 below: 828 Gap(s[j']) = (j') - (j) 830 Gaps MAY also be expressed in time: 832 GapTime(s[j']) = DstTime(j') - DstTime(j) 834 Otherwise: 836 Gap(s[j�]) (and GapTime(s[j']) ) for packet s[j�] is 0. 838 4.5.5 Discussion 840 When separate reordering discontinuities can be distinguished, then 841 a count may also be reported (along with the discontinuity 842 description, such as the number of reordered packets associated with 843 that discontinuity and their extents and offsets). The Gaps between 844 a sample's reordering discontinuities may be expressed as a 845 histogram, to easily summarize the frequency of various gaps. 846 Reporting the mode, average, range, etc. may also summarize the 847 distributions. 849 The Gap metric may help to correlate the frequency of reordering 850 discontinuities with their cause. Gap lengths are also informative 851 to receiver designers, revealing the period of reordering 852 discontinuities. The combination of reordering gaps and extent 853 reveals whether receivers will be required to handle cases of 854 overlapping reordered packets. 856 4.6 Reordering-free Runs 857 This section defines a metric based on a count of consecutive in- 858 order packets between reordered packets. 860 4.6.1 Metric Names 862 Type-P-Packet-Reordering-Free-Run-x-numruns-Stream 863 Type-P-Packet-Reordering-Free-Run-q-squruns-Stream 864 Type-P-Packet-Reordering-Free-Run-p-numpkts-Stream 865 Type-P-Packet-Reordering-Free-Run-a-accpkts-Stream 867 4.6.2 Parameters 869 We use the same parameters defined earlier, and define the 870 following: 872 + r, the run counter 874 + x, the number of runs, also the number of reordered packets 876 + a, the accumulator of in-order packets 878 + p, the number of packets (when the stream is complete, p=(x+a)=L) 880 + q, the sum of the squares of the runs counted 882 4.6.3 Definition 884 As packets in a sample arrive at the Destination, the count of in- 885 order packets between reordered packets is a Reordering-Free run. 886 Note that the minimum run-length is zero according to this 887 definition. A pseudo code example follows: 889 r = 0; /* r is the run counter */ 890 x = 0; /* x is the number of runs */ 891 a = 0; /* a is the accumulator of in-order packets */ 892 p = 0; /* p is the number of packets */ 893 q = 0; /* q is the sum of the squares of the runs counted */ 895 while(packets arrive with sequence number s) 896 { 897 p++; 898 if (s >= NextExp) /* s is in-order */ 899 then r++; 900 a++; 901 else /* s is reordered */ 902 q+= r*r; 903 r = 0; 904 x++; 905 } 906 Each in-order arrival increments the run counter and the accumulator 907 of in-order packets, each reordered packet resets the run counter 908 after adding it to the sum of the squared lengths. 910 Each arrival of a reordered packet yields a new run count. Long 911 runs accompany periods where order was maintained, while short runs 912 indicate frequent, or multi-packet reordering. 914 The percent of packets in-order is 100*a/p 916 The average Reordering-Free run length is a/x 918 The q counter gives an indication of variation of the Reordering- 919 Free runs from the average by comparing q/a to a/x ((q/a)/(a/x)) 921 4.6.4 Discussion and Illustration 923 Type-P-packet-Reordering-Free-Run-Stream parameters give a brief 924 summary of the stream's reordering characteristics including the 925 average reordering-free run length, and the variation of run 926 lengths, therefore a key application of this metric is network 927 evaluation. 929 For 36 packets with 3 runs of 11 in-order packets we have: 930 p = 36 931 x = 3 932 a = 33 933 q = 3 * (11*11) = 363 934 ave reordering-free run = 11 935 q/a = 11 936 (q/a)/(a/x) = 1.0 938 For 36 packets with 3 runs, 2 runs of length 1 and one of length 31 939 p = 36 940 x = 3 941 a = 33 942 q = 1 + 1 + 961 = 963 943 ave reordering-free run = 11 944 q/a = 29.18 945 (q/a)/(a/x) = 2.65 947 The variability in run length is prominent in the difference between 948 the q values (sum of the squared run lengths) and comparing average 949 run length to the (q/a)/(a/x) ratios (equals 1 when all runs are the 950 same length). 952 5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric 954 This section describes a metric that conveys information associated 955 with the effect of reordering on TCP. However, in order to infer 956 anything about TCP performance, the test stream MUST bear a close 957 resemblance to the TCP sender of interest. [RFC3148] lists the 958 specific aspects of congestion control algorithms that must be 959 specified. Further, RFC 3148 recommends that Bulk Transfer Capacity 960 metrics SHOULD have instruments to distinguish three cases of packet 961 reordering (in section 3.3). The sample metrics defined above 962 satisfy the requirements to classify packets that are slightly or 963 grossly out-of-order. The metric in this section adds the capability 964 to estimate whether reordering might cause the DUP-ACK threshold to 965 be exceeded causing the Fast Retransmit algorithm to be invoked. 966 Additional TCP Kernel Instruments are summarized in [Mat03]. 968 5.1 Metric Name 970 Type-P-Packet-n-Reordering-Stream 972 5.2 Parameter Notation 974 Let n be a positive integer (a parameter). Let k be a positive 975 integer equal to the number of packets sent (sample size). Let l be 976 a non-negative integer representing the number of packets that were 977 received out of the k packets sent. (Note that there is no 978 relationship between k and l: on one hand, losses can make l less 979 than k; on the other hand, duplicates can make l greater than k.) 980 Assign each sent packet a sequence number, 1 to k, in order of 981 packet emission. 983 Let s[1], s[2], ..., s[l] be the original sequence numbers of the 984 received packets, in the order of arrival. 986 5.3 Definitions 988 Definition 1: Received packet number i (n < i <= l), with source 989 sequence number s[i], is n-reordered if and only if for all j such 990 that i-n <= j < i, s[j] > s[i]. 992 Claim: If by this definition, a packet's reordering is n and 0 < n' 993 < n, then the packet is also reordered to the n' extent. 995 Note: This definition is illustrated by C code in Appendix A. It 996 determines the n-reordering for a value of n=3 (when actually 997 writing applications that would report the metric, one would 998 probably report it for several values of n, such as 1, 2, 3, 4 -- 999 and maybe a few more consecutive values). 1001 This definition does not assign an n to all reordered packets as 1002 defined by the singleton metric, in particular when blocks of 1003 successive packets are reordered. (In the arrival sequence 1004 s={1,2,3,7,8,9,4,5,6}, packets 4, 5, and 6 are reordered, but only 1005 packet 4 is n-reordered, with n=3.) 1007 Definition 2: The degree of n-reordering of the sample is m/l, where 1008 m is the number of n-reordered packets in the sample. 1010 Definition 3: The degree of "monotonic reordering" of the sample is 1011 its degree of 1-reordering. 1013 Definition 4: A sample is said to have no reordering if its degree 1014 of n-reordering is 0. 1016 5.4 Discussion 1018 The degree of n-reordering may be expressed as a percentage, in 1019 which case the number from Definition 2 is multiplied by 100. 1021 The n-reordering metric is helpful for matching the duplicate ACK 1022 threshold setting to a given path. For example, if a path exhibits 1023 no more than 5-reordering, a DUP-ACK threshold of 6 may avoid 1024 unnecessary retransmissions. 1026 Important special cases are n=1 and n=3: 1028 - For n=1, absence of 1-reordering means the sequence numbers that 1029 the receiver sees are monotonically increasing with respect to the 1030 previous arriving packet. 1032 - For n=3, a NewReno TCP sender would retransmit 1 packet in 1033 response to an instance of 3-reordering and therefore consider this 1034 packet lost for the purposes of congestion control (the sender will 1035 halve its congestion window, see [RFC2581]). Three is default 1036 threshold for Stream Control Transport Protocol (SCTP) [RFC2960], 1037 and the Datagram Congestion Control Protocol (DCCP) [RFC4340] when 1038 used with Congestion Control ID 2: TCP-like Congestion Control 1039 [RFC4341]. 1041 A sample's n-reordering may be expressed as a histogram, to 1042 summarize the frequency for each value of n. 1044 We note that the definition of n-reordering cannot predict the exact 1045 number of packets unnecessarily retransmitted by a TCP sender under 1046 some circumstances, such as cases with closely-spaced reordered 1047 singletons. Both time and position influence the sender's behavior. 1049 A packet's n-reordering designation is sometimes equal to its 1050 reordering extent, e. n-reordering is different in the following 1051 ways: 1053 1. n is a count of early packets with consecutive arrival positions 1054 at the receiver. 1056 2. Reordered packets (Type-P-Reordered=TRUE) may not be n-reordered, 1057 but will have an extent, e (see the examples). 1059 6. Measurement and Implementation Issues 1060 The results of tests will be dependent on the time interval between 1061 measurement packets (both at the Source, and during transport where 1062 spacing may change). Clearly, packets launched infrequently (e.g., 1063 1 per 10 seconds) are unlikely to be reordered. 1065 In order to gauge the reordering for an application according to the 1066 metrics defined in this memo, it is RECOMMENDED to use the same 1067 sending pattern as the application of interest. In any case, the 1068 exact method of packet generation MUST be reported with the 1069 measurement results, including all stream parameters. 1071 + To make inferences about applications that use TCP, it is 1072 REQUIRED to use TCP-like Streams as in [RFC3148] 1074 + For real-time applications, it is RECOMMENDED to use Periodic 1075 Streams as in [RFC3432] 1077 It is acceptable to report the metrics of Sections 3 and 4 with 1078 other IPPM metrics using Poisson Streams [RFC2330]. Poisson streams 1079 represent an "unbiased sample" of network performance for packet 1080 loss and delay metrics. However, it would be incorrect to make 1081 inferences about the application categories above using reordering 1082 metrics measured with Poisson streams. 1084 Test stream designers may prefer to use a periodic sending interval 1085 so that a known temporal bias is maintained, also bringing 1086 simplified results analysis (as described in [RFC3432]). In this 1087 case, it is RECOMMENDED that the periodic sending interval should be 1088 chosen to reproduce the closest Source packet spacing expected. 1089 Testers must recognize that streams sent at the link speed 1090 serialization limit MUST have limited duration and MUST consider 1091 packet loss as an indication that the stream has caused congestion, 1092 and suspend further testing. 1094 When intending to compare independent measurements of reordering, it 1095 is RECOMMENDED to use the same test stream parameters in each 1096 measurement system. 1098 Packet lengths might also be varied to attempt to detect instances 1099 of parallel processing (they may cause steady state reordering). For 1100 example, a line-speed burst of the longest (MTU-length) packets 1101 followed by a burst of the shortest possible packets may be an 1102 effective detecting pattern. Other size patterns are possible. 1104 The non-reversing order criterion and all metrics described above 1105 remain valid and useful when a stream of packets experiences packet 1106 loss, or both loss and reordering. In other words, losses alone do 1107 not cause subsequent packets to be declared reordered. 1109 Since this metric definition may use sequence numbers with finite 1110 range, it is possible that the sequence numbers could reach end-of- 1111 range and roll over to zero during a measurement. By definition, 1112 the Next Expected value cannot decrease, and all packets received 1113 after a roll-over would be declared reordered. Sequence number 1114 roll-over can be avoided by using combinations of counter size and 1115 test duration where roll-over is impossible (and sequence is reset 1116 to zero at the start). Also, message-based numbering results in 1117 slower sequence consumption. There may still be cases where 1118 methodological mitigation of this problem is desirable (e.g., long- 1119 term testing). The elements of mitigation are: 1121 1. There must be a test to detect if a roll-over has occurred. It 1122 would be nearly impossible for the sequence numbers of successive 1123 packets to jump by more than half the total range, so these large 1124 discontinuities are designated as roll-over. 1126 2. All sequence numbers used in computations are represented in a 1127 sufficiently large precision. The numbers have a correction applied 1128 (equivalent to adding a significant digit) whenever roll-over is 1129 detected. 1131 3. Reordered packets coincident with sequence numbers reaching end- 1132 of-range must also be detected for proper application of correction 1133 factor. 1135 Ideally, the test instrument would have the ability to use all 1136 earlier packets at any point in the test stream. In practice there 1137 will be limited ability to determine reordering extent, due to the 1138 storage requirements for previous packets. Saving only packets that 1139 indicate discontinuities (and their arrival positions) will reduce 1140 storage volume. 1142 Another solution is to use a sliding history window of packets, 1143 where the window size would be determined by an upper bound on the 1144 useful reordering extent. This bound could be several packets or 1145 several seconds worth of packets, depending on the intended 1146 analysis. When discarding all stream information beyond the window, 1147 the reordering extent or degree of n-reordering may need to be 1148 expressed as greater than the window length if the reordering 1149 discontinuity information has been discarded, and Gap calculations 1150 would not be possible. 1152 The requirement to ignore duplicate packets also mandates storage. 1153 Here, tracking the sequence numbers of missing packets may minimize 1154 storage size. Missing packets may eventually be declared lost, or 1155 reordered if they arrive. The missing packet list and the largest 1156 sequence number received thus far (NextExp - 1) are sufficient 1157 information to determine if a packet is a duplicate (assuming a 1158 manageable storage size for packets that are missing due to loss). 1160 It is important to note that practical IP networks also have limited 1161 ability to "store" packets, even when routing loops appear 1162 temporarily. Therefore, the maximum storage for reordering metrics 1163 (and their complexity) would only approach the number packets in the 1164 sample, K, when the sending time for K packets is small with respect 1165 to the network's largest possible transfer time. Another possible 1166 limitation on storage is the maximum length of the sequence number 1167 field, assuming that most test streams do not exhaust this length in 1168 practice. 1170 Last, we note that determining reordering extents and gaps is tricky 1171 when there are overlapped or nested events. Test instrument 1172 complexity and reordering complexity are directly correlated. 1174 6.1 Passive Measurement Considerations 1176 As with other IPPM metrics, the definitions have been constructed 1177 primarily for Active measurements. 1179 Assuming that the necessary sequence information (message number) is 1180 included in the packet payload (possibly in application headers such 1181 as RTP), reordering metrics may be evaluated in a passive 1182 measurement arrangement. Also, it is possible to evaluate order at 1183 any point along a Source-Destination path, recognizing that 1184 intermediate measurements may differ from those made at the 1185 Destination (where the reordering effect on applications can be 1186 inferred). 1188 It is possible to apply these metrics to evaluate reordering in a 1189 TCP sender's stream. In this case, the Source sequence numbers would 1190 be based on byte stream, or segment numbering. Since the stream may 1191 include retransmissions due to loss or reordering, care must be 1192 taken to avoid declaring retransmitted packets reordered. The 1193 additional sequence reference of s or SrcTime helps to avoid this 1194 ambiguity in active measurement, or the optional TCP timestamp field 1195 [RFC1323] in passive measurement. 1197 7. Examples of Arrival Order Evaluation 1199 This section provides some examples to illustrate how the non- 1200 reversing order criterion works, how n-reordering works in 1201 comparison, and the value of quantifying reordering in all the 1202 dimensions of time, bytes, and position. 1204 Throughout this section, we will refer to packets by their source 1205 sequence number, except where noted. So "Packet 4" refers to the 1206 packet with source sequence number 4, and the reader should refer to 1207 the tables in each example to determine packet 4's arrival index 1208 number, if needed. 1210 7.1 Example with a Single Packet Reordered 1212 Table 1 gives a simple case of reordering, where one packet is 1213 reordered, Packet 4. Packets are listed according to their arrival, 1214 and message numbering is used. All packets contain PayloadSize=100 1215 bytes, with SrcByte=(s x 100)-99 for s=1,2,3,4,... 1217 Table 1 Example with Packet 4 Reordered, 1218 Sending order(SrcNum@Src): 1,2,3,4,5,6,7,8,9,10 1219 s Src Dst Dst Byte Late 1220 @Dst NextExp Time Time Delay IPDV Order Offset Time 1221 1 1 0 68 68 1 1222 2 2 20 88 68 0 2 1223 3 3 40 108 68 0 3 1224 5 4 80 148 68 -82 4 1225 6 6 100 168 68 0 5 1226 7 7 120 188 68 0 6 1227 8 8 140 208 68 0 7 1228 4 9 60 210 150 82 8 400 62 1229 9 9 160 228 68 0 9 1230 10 10 180 248 68 0 10 1232 Each column gives the following information: 1234 s Packet sequence number at the Source. 1235 NextExp The value of NextExp when the packet arrived(before 1236 update). 1237 SrcTime Packet time stamp at the Source, ms. 1238 DstTime Packet time stamp at the Destination, ms. 1239 Delay 1-way delay of the packet, ms. 1240 IPDV IP Packet Delay Variation, ms 1241 IPDV = Delay(SrcNum)-Delay(SrcNum-1) 1242 DstOrder Order in which the packet arrived at the Destination. 1243 Byte Offset The Byte Offset of a reordered packet, in bytes. 1244 LateTime The lateness of a reordered packet, in ms. 1246 We can see that when Packet 4 arrives, NextExp=9, and it is declared 1247 reordered. We compute the extent of reordering as follows: 1249 Using the notation , the received 1250 packets are represented as: 1252 \/ 1253 s = 1, 2, 3, 5, 6, 7, 8, 4, 9, 10 1254 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 1255 /\ 1257 Applying the definition of Type-P-packet-Reordering-Extent-Stream: 1258 when j=7, 8 > 4, so the reordering extent is 1 or more. 1259 when j=6, 7 > 4, so the reordering extent is 2 or more. 1260 when j=5, 6 > 4, so the reordering extent is 3 or more. 1261 when j=4, 5 > 4, so the reordering extent is 4 or more. 1262 when j=3, but 3 < 4, and 4 is the maximum extent, e=4 (assuming 1263 there are no earlier sequence discontinuities, as in this example). 1265 Further, we can compute the Late Time (210-148=62ms using DstTime) 1266 compared to Packet 5's arrival. If the receiver has a de-jitter 1267 buffer that holds more than 4 packets, or at least 62 ms storage, 1268 Packet 4 may be useful. Note that 1-way delay and IPDV indicate 1269 unusual behavior for Packet 4. Also, if Packet 4 had arrived at 1270 least 62ms earlier, it would have been in-order in this example. 1272 If all packets contained 100 byte payloads, then Byte Offset is 1273 equal to 400 bytes. 1275 Following the definitions of section 5.1, Packet 4 is designated 4- 1276 reordered. 1278 7.2 Example with Two Packets Reordered 1280 Table 2 Example with Packets 5 and 6 Reordered, 1281 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10 1282 s Src Dst Dst Byte Late 1283 @Dst NextExp Time Time Delay IPDV Order Offset Time 1284 1 1 0 68 68 1 1285 2 2 20 88 68 0 2 1286 3 3 40 108 68 0 3 1287 4 4 60 128 68 0 4 1288 7 5 120 188 68 -22 5 1289 5 8 80 189 109 41 6 100 1 1290 6 8 100 190 90 -19 7 100 2 1291 8 8 140 208 68 0 8 1292 9 9 160 228 68 0 9 1293 10 10 180 248 68 0 10 1295 Table 2 shows a case where Packets 5 and 6 arrive just behind Packet 1296 7, so both 5 and 6 are reordered. The Late times (189-188=1, 190- 1297 188=2) are small. 1299 Using the notation , the received 1300 packets are represented as: 1302 \/ \/ 1303 s = 1, 2, 3, 4, 7, 5, 6, 8, 9, 10 1304 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 1305 /\ /\ 1307 Considering Packet 5 first: 1308 when j=5, 7 > 5, so the reordering extent is 1 or more. 1309 when j=4, we have 4 < 5, so 1 is its maximum extent, and e=1. 1311 Considering Packet 6 next: 1312 when j=6, 5 < 6, the extent is not yet defined. 1313 when j=5, 7 > 6, so the reordering extent is i-j=2 or more. 1314 when j=4, 4 < 6, and we find 2 is its maximum extent, and e=2. 1316 We can also associate each of these reordered packets with a 1317 reordering discontinuity. We find the minimum j=5 (for both packets) 1318 according to Section 4.2.3. So Packet 6 is associated with the same 1319 reordering discontinuity as Packet 5, the Reordering Discontinuity 1320 at Packet 7. 1322 This is a case where reordering extent e would over-estimate the 1323 packet storage required to restore order. Only one packet storage is 1324 required (to hold Packet 7), but e=2 for Packet 6. 1326 Following the definitions of section 5, Packet 5 is designated 1- 1327 reordered, but Packet 6 is not designated n-reordered. 1329 A hypothetical sender/receiver pair may retransmit Packet 5 1330 unnecessarily, since it is 1-reordered (in agreement with the 1331 singleton metric). Though Packet 6 may not be unnecessarily 1332 retransmitted, the receiver cannot advance Packet 7 to the higher 1333 layers until after Packet 6 arrives. Therefore, the singleton metric 1334 correctly determined that Packet 6 is reordered. 1336 7.3 Example with Three Packets Reordered 1338 Table 3 Example with Packets 4, 5, and 6 reordered 1339 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11 1340 s Src Dst Dst Byte Late 1341 @Dst NextExp Time Time Delay IPDV Order Offset Time 1342 1 1 0 68 68 1 1343 2 2 20 88 68 0 2 1344 3 3 40 108 68 0 3 1345 7 4 120 188 68 -88 4 1346 8 8 140 208 68 0 5 1347 9 9 160 228 68 0 6 1348 10 10 180 248 68 0 7 1349 4 11 60 250 190 122 8 400 62 1350 5 11 80 252 172 -18 9 400 64 1351 6 11 100 256 156 -16 10 400 68 1352 11 11 200 268 68 0 11 1354 The case in Table 3 is where three packets in sequence have long 1355 transit times (Packets with s = 4,5,and 6). Delay, Late time, and 1356 Byte Offset capture this very well, and indicate variation in 1357 reordering extent, while IPDV indicates that the spacing between 1358 packets 4,5,and 6 has changed. 1360 The histogram of Reordering extents (e) would be: 1362 Bin 1 2 3 4 5 6 7 1363 Frequency 0 0 0 1 1 1 0 1365 Using the notation , the received 1366 packets are represented as: 1368 s = 1, 2, 3, 7, 8, 9,10, 4, 5, 6, 11 1369 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11 1371 We first calculate the n-reordering. Considering Packet 4 first: 1372 when n=1, 7<=j<8, and 10> 4, so the packet is 1-reordered. 1373 when n=2, 6<=j<8, and 9 > 4, so the packet is 2-reordered. 1374 when n=3, 5<=j<8, and 8 > 4, so the packet is 3-reordered. 1375 when n=4, 4<=j<8, and 7 > 4, so the packet is 4-reordered. 1376 when n=5, 3<=j<8, but 3 < 4, and 4 is the maximum n-reordering. 1378 Considering packet 5[9] next: 1379 when n=1, 8<=j<9, but 4 < 5, so the packet at i=9 is not designated 1380 as n-reordered. We find the same to for Packet 6. 1382 We now consider whether reordered Packets 5 and 6 are associated 1383 with the same reordering discontinuity as Packet 4. Using the test 1384 of Section 4.2.3, we find that the minimum j=4 for all three 1385 packets. They are all associated with the reordering discontinuity 1386 at Packet 7. 1388 This example shows again that the n-reordering definition identifies 1389 a single Packet (4) with a sufficient degree of n-reordering that 1390 might cause one unnecessary packet retransmission by the New Reno 1391 TCP sender (with DUP-ACK threshold=3 or 4). Also, the reordered 1392 arrival of Packets 5 and 6 will allow the receiver process to pass 1393 Packets 7 through 10 up the protocol stack (the singleton Type-P- 1394 Reordered = TRUE for Packets 5 and 6, and they are all associated 1395 with a single reordering discontinuity). 1397 7.4 Example with Multiple Packet Reordering Discontinuities 1399 Table 4 Example with Multiple Packet Reordering Discontinuities 1400 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 1402 Discontinuity Discontinuity 1403 |---------Gap---------| 1404 s = 1, 2, 3, 6, 7, 4, 5, 8, 9, 10, 12, 13, 11, 14, 15, 16 1405 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 1407 r = 1, 2, 3, 4, 5, 0, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, ... 1408 number of runs,n = 1 2 3 1409 end r counts = 5 0 5 1410 (these values are computed after the packet arrives) 1412 Packet 4 has extent e=2, Packet 5 has extent e=3, and Packet 11 has 1413 e=2. There are two different reordering discontinuities, one at 1414 Packet 6 (where j=4) and one at Packet 12 (where j'=11). 1416 According to the definition of Reordering Gap 1417 Gap(s[j']) = (j') - (j) 1418 Gap(Packet 12) = (11) - (4) = 7 1420 We also have three reordering-free runs of lengths 5, 0, and 5. 1422 The differences between these two multiple-event metrics are evident 1423 here. Gaps are the distance between sequence discontinuities that 1424 are subsequently defined as reordering discontinuities, while 1425 reordering-free runs capture the distance between reordered packets. 1427 8. Security Considerations 1429 8.1 Denial of Service Attacks 1431 This metric requires a stream of packets sent from one host (source) 1432 to another host (destination) through intervening networks. This 1433 method could be abused for denial of service attacks directed at 1434 destination and/or the intervening network(s). 1436 Administrators of source, destination, and the intervening 1437 network(s) should establish bilateral or multi-lateral agreements 1438 regarding the timing, size, and frequency of collection of sample 1439 metrics. Use of this method in excess of the terms agreed between 1440 the participants may be cause for immediate rejection or discard of 1441 packets or other escalation procedures defined between the affected 1442 parties. 1444 8.2 User Data Confidentiality 1446 Active use of this method generates packets for a sample, rather 1447 than taking samples based on user data, and does not threaten user 1448 data confidentiality. Passive measurement must restrict attention to 1449 the headers of interest. Since user payloads may be temporarily 1450 stored for length analysis, suitable precautions MUST be taken to 1451 keep this information safe and confidential. In most cases, a 1452 hashing function will produce a value suitable for payload 1453 comparisons. 1455 8.3 Interference with the Metric 1457 It may be possible to identify that a certain packet or stream of 1458 packets is part of a sample. With that knowledge at the destination 1459 and/or the intervening networks, it is possible to change the 1460 processing of the packets (e.g. increasing or decreasing delay) that 1461 may distort the measured performance. It may also be possible to 1462 generate additional packets that appear to be part of the sample 1463 metric. These additional packets are likely to perturb the results 1464 of the sample measurement. The likely consequences of packet 1465 injection are that the additional packets would be declared 1466 duplicates, or that the original packets would be seen as duplicates 1467 (if they arrive after the corresponding injected packets) causing 1468 invalid measurements on the injected packets. 1470 The requirements for data collection resistance to interference by 1471 malicious parties and mechanisms to achieve such resistance are 1472 available in other IPPM memos. A set of requirements for a data 1473 collection protocol can be found in [RFC3763], and a protocol 1474 specification for the One-Way Active Measurement Protocol (OWAMP) is 1475 in [RFCyyyy]. The security considerations sections of the two OWAMP 1476 documents are extensive and should be consulted for additional 1477 details. 1479 9. IANA Considerations 1481 Metrics defined in this memo are designed to be registered in the 1482 IANA IPPM METRICS REGISTRY as described in initial version of the 1483 registry [RFC4148]. 1485 IANA is asked to register the following metrics in the IANA-IPPM- 1486 METRICS-REGISTRY-MIB (where RFC xxxx is replaced with the number of 1487 this memo): 1489 ietfReorderedSingleton OBJECT-IDENTITY 1490 STATUS current 1491 DESCRIPTION 1492 "Type-P-Reordered" 1493 REFERENCE 1494 "Reference RFC xxxx, section 3" 1495 ::= { ianaIppmMetrics nn } -- IANA assigns nn 1497 ietfReorderedPacketRatio OBJECT-IDENTITY 1498 STATUS current 1499 DESCRIPTION 1500 "Type-P-Reordered-Ratio-Stream" 1501 REFERENCE 1502 "Reference RFC xxxx, section 4.1" 1503 ::= { ianaIppmMetrics nn } -- IANA assigns nn 1505 ietfReorderingExtent OBJECT-IDENTITY 1506 STATUS current 1507 DESCRIPTION 1508 "Type-P-Packet-Reordering-Extent-Stream" 1509 REFERENCE 1510 "Reference RFC xxxx, section 4.2" 1511 ::= { ianaIppmMetrics nn } -- IANA assigns nn 1513 ietfReorderingLateTimeOffset OBJECT-IDENTITY 1514 STATUS current 1515 DESCRIPTION 1516 "Type-P-Packet-Late-Time-Stream" 1517 REFERENCE 1518 "Reference RFC xxxx, section 4.3" 1519 ::= { ianaIppmMetrics nn } -- IANA assigns nn 1521 ietfReorderingByteOffset OBJECT-IDENTITY 1522 STATUS current 1523 DESCRIPTION 1524 "Type-P-Packet-Byte-Offset-Stream" 1525 REFERENCE 1526 "Reference RFC xxxx, section 4.4" 1527 ::= { ianaIppmMetrics nn } -- IANA assigns nn 1529 ietfReorderingGap OBJECT-IDENTITY 1530 STATUS current 1531 DESCRIPTION 1532 "Type-P-Packet-Reordering-Gap-Stream" 1533 REFERENCE 1534 "Reference RFC xxxx, section 4.5" 1535 ::= { ianaIppmMetrics nn } -- IANA assigns nn 1537 ietfReorderingGapTime OBJECT-IDENTITY 1538 STATUS current 1539 DESCRIPTION 1540 "Type-P-Packet-Reordering-GapTime-Stream" 1541 REFERENCE 1542 "Reference RFC xxxx, section 4.5" 1543 ::= { ianaIppmMetrics nn } -- IANA assigns nn 1545 ietfReorderingFreeRunx OBJECT-IDENTITY 1546 STATUS current 1547 DESCRIPTION 1548 "Type-P-Packet-Reordering-Free-Run-x-numruns-Stream" 1549 REFERENCE 1550 "Reference RFC xxxx, section 4.6" 1551 ::= { ianaIppmMetrics nn } -- IANA assigns nn 1553 ietfReorderingFreeRunq OBJECT-IDENTITY 1554 STATUS current 1555 DESCRIPTION 1556 "Type-P-Packet-Reordering-Free-Run-q-squruns-Stream" 1557 REFERENCE 1558 "Reference RFC xxxx, section 4.6" 1559 ::= { ianaIppmMetrics nn } -- IANA assigns nn 1561 ietfReorderingFreeRunp OBJECT-IDENTITY 1562 STATUS current 1563 DESCRIPTION 1564 "Type-P-Packet-Reordering-Free-Run-p-numpkts-Stream" 1565 REFERENCE 1566 "Reference RFC xxxx, section 4.6" 1567 ::= { ianaIppmMetrics nn } -- IANA assigns nn 1569 ietfReorderingFreeRuna OBJECT-IDENTITY 1570 STATUS current 1571 DESCRIPTION 1572 "Type-P-Packet-Reordering-Free-Run-a-accpkts-Stream" 1573 REFERENCE 1574 "Reference RFC xxxx, section 4.6" 1575 ::= { ianaIppmMetrics nn } -- IANA assigns nn 1577 ietfnReordering OBJECT-IDENTITY 1578 STATUS current 1579 DESCRIPTION 1580 "Type-P-Packet-n-Reordering-Stream" 1581 REFERENCE 1582 "Reference RFC xxxx, section 5" 1583 ::= { ianaIppmMetrics nn } -- IANA assigns nn 1585 10. Normative References 1587 [RFC791] Postel, J., "Internet Protocol", STD 5, RFC 791, 1588 September 1981. 1589 Obtain via: http://www.rfc-editor.org/rfc/rfc791.txt 1591 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1592 Requirement Levels", RFC 2119, March 1997. 1593 Obtain via: http://www.rfc-editor.org/rfc/rfc2119.txt 1595 [RFC2330] Paxson, V., Almes, G., Mahdavi, J., and Mathis, M., 1596 "Framework for IP Performance Metrics", RFC 2330, May 1597 1998. 1598 Obtain via: http://www.rfc-editor.org/rfc/rfc2330.txt 1600 [RFC2460] Deering, S. and Hinden, R., "Internet Protocol Version 6 1601 (IPv6) Specification", RFC 2460, December 1998. 1602 Obtain via: http://www.rfc-editor.org/rfc/rfc2460.txt 1604 [RFC3148] Mathis, M. and Allman, M., "A Framework for Defining 1605 Empirical Bulk Transfer Capacity Metrics", RFC 3148, July 1606 2001. 1607 Obtain via: http://www.rfc-editor.org/rfc/rfc3148.txt 1609 [RFC3432] Raisanen, V., Grotefeld, G., and Morton, A., "Network 1610 performance measurement with periodic streams", RFC 3432, 1611 November 2002. 1612 Obtain via: http://www.rfc-editor.org/rfc/rfc3432.txt 1614 [RFC3763] Shalunov, S. and Teitelbaum, B., "One-way Active 1615 Measurement Protocol (OWAMP) Requirements", RFC 3763, 1616 April 2004. 1617 Obtain via: http://www.rfc-editor.org/rfc/rfc3763.txt 1619 [RFC4148] Stephan, E., "IP Performance Metrics (IPPM) Metrics 1620 Registry", RFC 4148, BCP 108, August 2005. 1621 Obtain via: http://www.rfc-editor.org/rfc/rfc4148.txt 1623 [RFCyyyy] Shalunov, S., Teitelbaum, B., Karp, A., Boote, J., and 1624 Zeckauskas, M., "One-way Active Measurement Protocol 1625 (OWAMP) Requirements", RFC yyyy, 2006. 1626 Obtain via: http://www.rfc-editor.org/rfc/rfcyyyy.txt 1628 11. Informative References 1630 [Bel02] J.Bellardo and S.Savage, "Measuring Packet Reordering," 1631 Proceedings of the ACM SIGCOMM Internet Measurement 1632 Workshop 2002, November 6-8, Marseille, France. 1634 [Ben99] J.C.R.Bennett, C.Partridge, and N.Shectman, "Packet 1635 Reordering is Not Pathological Network Behavior," 1636 IEEE/ACM Transactions on Networking, vol.7, no.6, pp.789- 1637 798, December 1999. 1639 [Cia00] L.Ciavattone and A.Morton, "Out-of-Sequence Packet 1640 Parameter Definition (for Y.1540)", Contribution number 1641 T1A1.3/2000-047, October 30, 2000. 1642 ftp://ftp.t1.org/pub/t1a1/2000-A13/0a130470.doc 1644 [Cia03] L.Ciavattone, A.Morton, and G.Ramachandran, "Standardized 1645 Active Measurements on a Tier 1 IP Backbone," IEEE 1646 Communications Mag., pp 90-97, June 2003. 1648 [I.356] ITU-T Recommendation I.356, "B-ISDN ATM layer cell 1649 transfer performance", March 2000. 1651 [Jai02] S.Jaiswal et al., "Measurement and Classification of Out- 1652 of-Sequence Packets in a Tier-1 IP Backbone," Proceedings 1653 of the ACM SIGCOMM Internet Measurement Workshop 2002, 1654 November 6-8, Marseille, France. 1656 [Lou01] D.Loguinov and H.Radha, "Measurement Study of Low-bitrate 1657 Internet Video Streaming", Proceedings of the ACM SIGCOMM 1658 Internet Measurement Workshop 2001 November 1-2, 2001, 1659 San Francisco, USA. 1661 [Mat03] M. Mathis, J Heffner and R Reddy, "Web100: Extended TCP 1662 Instrumentation for Research, Education and Diagnosis", 1663 ACM Computer Communications Review, Vol 33, Num 3, July 1664 2003. http://www.web100.org/docs/mathis03web100.pdf 1666 [Pax98] V.Paxson, "Measurements and Analysis of End-to-End 1667 Internet Dynamics," Ph.D. dissertation, U.C. Berkeley, 1668 1997, ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz. 1670 [RFC793] Postel, J., "Transmission Control Protocol", STD 7, RFC 1671 793, September 1981. 1672 Obtain via: http://www.rfc-editor.org/rfc/rfc793.txt 1674 [RFC1323] Jacobson, V., Braden, R., and Borman, D., "TCP Extensions 1675 for High Performance", RFC 1323, May 1992. 1677 [RFC2581] Allman, M., Paxson, V., and Stevens, W., "TCP Congestion 1678 Control", RFC 2581, April 1999. 1680 [RFC2679] Almes, G., Kalidindi, S., and Zekauskas, M., "A One-way 1681 Delay Metric for IPPM", RFC 2679, September 1999. 1682 Obtain via: http://www.rfc-editor.org/rfc/rfc2679.txt 1684 [RFC2680] Almes, G., Kalidindi, S., and Zekauskas, M., "A One-way 1685 Packet Loss Metric for IPPM", RFC 2680, September 1999. 1686 Obtain via: http://www.rfc-editor.org/rfc/rfc2680.txt 1688 [RFC2960] Stewart, R., et al., "Stream Control Transmission 1689 Protocol", RFC 2960, October 2000. 1691 [RFC3393] Demichelis, C., and Chimento, P., "IP Packet Delay 1692 Variation Metric for IP Performance Metrics (IPPM)", RFC 1693 3393, November 2002. 1695 [RFC4340] Kohler, E., Handley, M. and Floyd, S., "Datagram 1696 Congestion Control Protocol (DCCP)", RFC 4340, March 1697 2006. 1699 [RFC4341] Floyd, S. and Kohler, E., "Profile for Datagram 1700 Congestion Control Protocol (DCCP) Congestion Control ID 1701 2: TCP-like Congestion Control", RFC 4341, March 2006. 1703 [TBABAJ02] T. Banka, A. A. Bare, A. P. Jayasumana, "Metrics for 1704 Degree of Reordering in Packet Sequences", Proc. 27th 1705 IEEE Conference on Local Computer Networks, Tampa, FL, 1706 Nov. 2002. 1708 [Y.1540] ITU-T Recommendation Y.1540, "Internet protocol data 1709 communication service - IP packet transfer and 1710 availability performance parameters", December 2002. 1712 12. Acknowledgments 1714 The authors would like to acknowledge many helpful discussions with 1715 Matt Zekauskas, Jon Bennett (who authored the sections on 1716 Reordering-Free Runs), and Matt Mathis. We thank David Newman, Henk 1717 Uijterwaal, Mark Allman, Vern Paxson, and Phil Chimento for their 1718 reviews and suggestions, and Michal Przybylski for sharing 1719 implementation experiences with us on the ippm-list. Anura 1720 Jayasumana and Nischal Piratla brought in recent work-in-progress 1721 [TBABAJ02]. We gratefully acknowledge the foundation laid by the 1722 authors of the IP performance Framework [RFC2330]. 1724 13. Appendix A Example Implementations in C (Informative) 1726 Two example c-code implementations of reordering definitions follow: 1728 Example 1 n-reordering ============================================ 1730 #include 1732 #define MAXN 100 1734 #define min(a, b) ((a) < (b)? (a): (b)) 1735 #define loop(x) ((x) >= 0? x: x + MAXN) 1737 /* 1738 * Read new sequence number and return it. Return a sentinel value 1739 * of EOF (at least once) when there are no more sequence numbers. 1740 * In this example, the sequence numbers come from stdin; 1741 * in an actual test, they would come from the network. 1742 * 1743 */ 1744 int 1745 read_sequence_number() 1746 { 1747 int res, rc; 1748 rc = scanf("%d\n", &res); 1749 if (rc == 1) return res; 1750 else return EOF; 1751 } 1753 int 1754 main() 1755 { 1756 int m[MAXN]; /* We have m[j-1] == number of 1757 * j-reordered packets. */ 1758 int ring[MAXN]; /* Last sequence numbers seen. */ 1759 int r = 0; /* Ring pointer for next write. */ 1760 int l = 0; /* Number of sequence numbers read. */ 1761 int s; /* Last sequence number read. */ 1762 int j; 1764 for (j = 0; j < MAXN; j++) m[j] = 0; 1765 for (;(s = read_sequence_number())!= EOF;l++,r=(r+1)%MAXN) { 1766 for (j=0; j 1786 #define MAXN 100 1787 #define min(a, b) ((a) < (b)? (a): (b)) 1788 #define loop(x) ((x) >= 0? x: x + MAXN) 1790 /* Global counters */ 1791 int receive_packets=0; /* number of received */ 1792 int reorder_packets_Al=0; /* num reordered pkts (singleton) */ 1793 int reorder_packets_Stas=0; /* num reordered pkts(n-reordering)*/ 1795 /* function to test if current packet has been reordered 1796 * returns 0 = not reordered 1797 * 1 = reordered 1798 */ 1799 int testorder1(int seqnum) // Al 1800 { 1801 static int NextExp = 1; 1802 int iReturn = 0; 1804 if (seqnum >= NextExp) { 1805 NextExp = seqnum+1; 1806 } else { 1807 iReturn = 1; 1808 } 1809 return iReturn; 1810 } 1812 int testorder2(int seqnum) // Stanislav 1813 { 1814 static int ring[MAXN]; /* Last sequence numbers seen. */ 1815 static int r = 0; /* Ring pointer for next write */ 1816 int l = 0; /* Number of sequence numbers read. */ 1817 int j; 1818 int iReturn = 0; 1820 l++; 1821 r = (r+1) % MAXN; 1822 for (j=0; j= NextExp, 1897 * AND the fragment offset FragOffset >= NextExpFrag 1899 However, it more efficient to define reordered conditions exactly, 1900 and designate Type-P-Reordered as False otherwise. 1902 The value of Type-P-Reordered is defined as True (the packet is 1903 reordered) under the conditions below. In these cases, the NextExp 1904 value does not change. 1906 Case 1: if s < NextExp 1908 Case 2: if s < FragSeq# 1910 Case 3: if s>= NextExp AND s = FragSeq# AND FragOffset < NextExpFrag 1912 This definition can also be illustrated in pseudo-code. A version of 1913 the code follows, and some simplification may be possible. A 1914 challenging aspect surrounds the housekeeping for the new 1915 parameters. 1917 NextExp=0; 1918 NextExpFrag=0; 1919 FragSeq#=0; 1921 while(packets arrive with s, MoreFrag, FragOffset) 1922 { 1923 if (s>=NextExp AND MoreFrag==0 AND s>=FragSeq#){ 1924 /* a normal packet or last frag of an in-order packet arrived 1925 */ 1926 NextExp = s+1; 1927 FragSeq# = 0; 1928 NextExpFrag = 0; 1929 Reordering = False; 1930 } 1931 if (s>=NextExp AND MoreFrag==1 AND s>FragSeq#>=0){ 1932 /* a fragment of a new packet arrived, possibly with a 1933 higher sequence number than the current fragmented packet */ 1934 FragSeq# = s; 1935 NextExpFrag = FragOffset+1; 1936 Reordering = False; 1937 } 1938 if (s>=NextExp AND MoreFrag==1 AND s==FragSeq#){ 1939 /* a fragment of the "current packet s" arrived */ 1940 if (FragOffset >= NextExpFrag){ 1941 NextExpFrag = FragOffset+1; 1942 Reordering = False; 1943 } 1945 else{ 1946 Reordering = True; /* fragment reordered */ 1947 } 1948 } 1949 if (s>=NextExp AND MoreFrag==1 AND s < FragSeq#){ 1950 /* case where a late fragment arrived, 1951 for illustration only, redundant with else below */ 1952 Reordering = True; 1953 } 1954 else { /* when s < NextExp, or MoreFrag==0 AND s < FragSeq# */ 1955 Reordering = True; 1956 } 1957 } 1959 A working version of the code would include a check to ensure that 1960 all fragments of a packet arrive before using the Reordered status 1961 further, such as in sample metrics. 1963 14.4 Discussion: Notes on Sample Metrics when Evaluating Fragments 1965 All fragments with the same Source Sequence Number are assigned the 1966 same Source Time. 1968 Evaluation with byte stream numbering may be simplified if the 1969 fragment offset is simply added to the SourceByte of the first 1970 packet (with fragment offset = 0), keeping the 8 octet units of the 1971 offset in mind. 1973 15. Disclaimer and License 1975 Regarding this entire document or any portion of it (including the 1976 pseudo-code and C code), the authors make no guarantees and are not 1977 responsible for any damage resulting from its use. The authors 1978 grant irrevocable permission to anyone to use, modify, and 1979 distribute it in any way that does not diminish the rights of anyone 1980 else to use, modify, and distribute it, provided that redistributed 1981 derivative works do not contain misleading author or version 1982 information. Derivative works need not be licensed under similar 1983 terms. 1985 16. Author's Addresses 1987 Al Morton 1988 AT&T Labs 1989 Room D3 - 3C06 1990 200 Laurel Ave. South 1991 Middletown, NJ 07748 USA 1992 Phone +1 732 420 1571 1993 EMail: 1995 Len Ciavattone 1996 AT&T Labs 1997 Room A2 - 4G06 1998 200 Laurel Ave. South 1999 Middletown, NJ 07748 USA 2000 Phone +1 732 420 1239 2001 EMail: 2003 Gomathi Ramachandran 2004 AT&T Labs 2005 Room C4 - 3D22 2006 200 Laurel Ave. South 2007 Middletown, NJ 07748 USA 2008 Phone +1 732 420 2353 2009 EMail: 2011 Stanislav Shalunov 2012 Internet2 2013 1000 Oakbrook DR STE 300 2014 Ann Arbor, MI 48104 2015 +1 734 995 7060 2016 EMail: 2018 Jerry Perser 2019 Veriwave 2020 USA 2021 Phone: 2022 EMail: 2024 Full Copyright Statement 2026 Copyright (C) The Internet Society (2006). 2028 This document is subject to the rights, licenses and restrictions 2029 contained in BCP 78, and except as set forth therein, the authors 2030 retain all their rights. 2032 This document and the information contained herein are provided on 2033 an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE 2034 REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE 2035 INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR 2036 IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 2037 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 2038 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 2040 Intellectual Property 2042 The IETF takes no position regarding the validity or scope of any 2043 Intellectual Property Rights or other rights that might be claimed 2044 to pertain to the implementation or use of the technology described 2045 in this document or the extent to which any license under such 2046 rights might or might not be available; nor does it represent that 2047 it has made any independent effort to identify any such rights. 2048 Information on the procedures with respect to rights in RFC 2049 documents can be found in BCP 78 and BCP 79. 2051 Copies of IPR disclosures made to the IETF Secretariat and any 2052 assurances of licenses to be made available, or the result of an 2053 attempt made to obtain a general license or permission for the use 2054 of such proprietary rights by implementers or users of this 2055 specification can be obtained from the IETF on-line IPR repository 2056 at http://www.ietf.org/ipr. 2058 The IETF invites any interested party to bring to its attention any 2059 copyrights, patents or patent applications, or other proprietary 2060 rights that may cover technology that may be required to implement 2061 this standard. Please address the information to the IETF at ietf- 2062 ipr@ietf.org. 2064 Acknowledgement 2066 Funding for the RFC Editor function is currently provided by the 2067 Internet Society.