idnits 2.17.1 draft-ietf-ippm-reordering-11.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 1843. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1854. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1861. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1867. ** 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. 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 1630 has weird spacing: '...tic int ring[...' == Line 1631 has weird spacing: '...tic int r = 0...' == Line 1632 has weird spacing: '... int l = ...' == Line 1633 has weird spacing: '... int j;...' == Line 1634 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) -- Looks like a reference, but probably isn't: '1' on line 1328 -- Looks like a reference, but probably isn't: '2' on line 956 == Missing Reference: 'L' is mentioned on line 1212, but not defined -- Looks like a reference, but probably isn't: '9' on line 1341 == Missing Reference: 'MAXN' is mentioned on line 1630, but not defined ** Downref: Normative reference to an Informational RFC: RFC 2330 ** Downref: Normative reference to an Informational RFC: RFC 3148 -- 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 2960 (Obsoleted by RFC 4960) Summary: 6 errors (**), 0 flaws (~~), 8 warnings (==), 15 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 Consultant 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 (2005). 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 affects 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:....................................................7 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:.................................................10 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:.................................................13 91 4.3.4 Discussion..................................................13 92 4.4 Reordering Byte Offset........................................14 93 4.4.1 Metric Name:................................................14 94 4.4.2 Metric Parameters:..........................................14 95 4.4.3 Definition:.................................................14 96 4.4.4 Discussion..................................................15 97 4.5 Gaps between multiple Reordering Discontinuities..............15 98 4.5.1 Metric Name:................................................15 99 4.5.2 Parameters:.................................................15 100 4.5.3 Definition of Reordering Discontinuity:.....................16 101 4.5.4 Definition of Reordering Gap:...............................16 102 4.5.5 Discussion..................................................16 103 4.6 Reordering-free Runs..........................................17 104 4.6.1 Metric Name:................................................17 105 4.6.2 Parameters:.................................................17 106 4.6.3 Definition:.................................................17 107 4.6.4 Discussion and Illustration:................................18 108 5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric..19 109 5.1 Metric Name:..................................................19 110 5.2 Parameter Notation:...........................................19 111 5.3 Definitions...................................................19 112 5.4 Discussion:...................................................20 113 6. Measurement and Implementation Issues..........................21 114 7. Examples of Arrival Order Evaluation...........................24 115 7.1 Example with a single packet reordered........................24 116 7.2 Example with two packets reordered............................25 117 7.3 Example with three packets reordered..........................27 118 7.4 Example with Multiple Packet Reordering Discontinuities.......28 119 8. Security Considerations........................................28 120 8.1 Denial of Service Attacks.....................................28 121 8.2 User data confidentiality.....................................29 122 8.3 Interference with the metric..................................29 123 9. IANA Considerations............................................29 124 10. Normative References..........................................29 125 11. Informative References........................................30 126 12. Acknowledgments...............................................31 127 13. Appendix A Example Implementations in C (Informative).........31 128 14. Appendix B Fragment Order Evaluation (Informative)............34 129 14.1 Metric Name:.................................................34 130 14.2 Additional Metric Parameters:................................34 131 14.3 Definition:..................................................35 132 14.4 Discussion: Notes on Sample Metrics when evaluating Fragments36 133 15. Author's Addresses............................................36 134 Full Copyright Statement..........................................37 135 Intellectual Property.............................................37 136 Acknowledgement...................................................38 138 1. Conventions used in this document 140 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 141 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 142 document are to be interpreted as described in RFC 2119 [RFC2119]. 143 Although RFC 2119 was written with protocols in mind, the key words 144 are used in this document for similar reasons. They are used to 145 ensure the results of measurements from two different 146 implementations are comparable, and to note instances when an 147 implementation could perturb the network. 149 In this memo, the characters "<=" should be read as "less than or 150 equal to" and ">=" as "greater than or equal to". 152 2. Introduction 154 Ordered arrival is a property found in packets that transit their 155 path, where the packet sequence number increases with each new 156 arrival and there are no backward steps. The Internet Protocol 157 [RFC791] has no mechanisms to assure either packet delivery or 158 sequencing, and higher layer protocols (above IP) should be prepared 159 to deal with both loss and reordering. This memo defines reordering 160 metrics. 162 A unique sequence number, such as an incrementing message number 163 carried in each packet, establishes the Source Sequence. 165 The detection of reordering at the Destination is based on packet 166 arrival order in comparison with a non-reversing reference value. 168 This metric is consistent with RFC 2330 [RFC2330], and classifies 169 arriving packets with sequence numbers smaller than their 170 predecessors as out-of-order, or reordered. For example, if 171 sequentially numbered packets arrive 1,2,4,5,3, then packet 3 is 172 reordered. This is equivalent to Paxon's reordering definition in 173 [Pax98], where "late" packets were declared reordered. The 174 alternative is to emphasize "premature" packets instead (4 and 5 in 175 the example), but only the arrival of packet 3 distinguishes this 176 circumstance from packet loss. Focusing attention on late packets 177 allows us to maintain orthogonality with the packet loss metric. The 178 metric's construction is very similar to the sequence space 179 validation for received segments in RFC 793 [RFC793]. Earlier work 180 to define ordered delivery includes [Cia00], [Ben99], [Lou01], 181 [Bel02], [Jai02] and [Cia03]. 183 2.1 Motivation 185 A reordering metric is relevant for most applications, especially 186 when assessing network support for Real-Time media streams. The 187 extent of reordering may be sufficient to cause a received packet to 188 be discarded by functions above the IP layer. 190 Packet order may change during transfer, and several specific path 191 characteristics can make reordering more likely. 193 Examples are: 194 * When two (or more) paths with slightly differing transfer times 195 support a single packet stream or flow, then packets traversing 196 the longer path(s) may arrive out-of-order. Multiple paths may be 197 used to achieve load balancing, or may arise from route 198 instability. 199 * To increase capacity, a network device designed with multiple 200 processors serving a single port (or parallel links) may reorder 201 as a byproduct. 202 * A layer 2 retransmission protocol that compensates for an error- 203 prone link may cause packet reordering. 205 * If for any reason, the packets in a buffer are not serviced in the 206 order of their arrival, their order will change. 207 * If packets in a flow are assigned to multiple buffers (following 208 evaluation of traffic characteristics, for example), and the 209 buffers have different occupations and/or service rates, then 210 order will likely change. 212 When one or more of the above path characteristics are present 213 continuously, then reordering may be present on a steady-state 214 basis. The steady-state reordering condition typically causes an 215 appreciable fraction of packets to be reordered. This form of 216 reordering is most easily detected by minimizing the spacing between 217 test packets. Transient reordering may occur in response to network 218 instability; temporary routing loops can cause periods of extreme 219 reordering. This condition is characterized by long in-order streams 220 with occasional instances of reordering, sometimes with extreme 221 correlation. However, we do not expect packet delivery in a 222 completely random order, where for example, the last packet or the 223 first packet in a sample is equally likely to arrive first at the 224 destination. Thus we expect at least a minimal degree of order in 225 the packet arrivals, as exhibited in real networks. 227 The ability to restore order at the destination will likely have 228 finite limits. Practical hosts have receiver buffers with finite 229 size in terms of packets, bytes, or time (such as de-jitter 230 buffers). Once the initial determination of reordering is made, it 231 is useful to quantify the extent of reordering, or lateness, in all 232 meaningful dimensions. 234 2.2 Goals and Objectives 236 The definitions below intend to satisfy the goals of: 238 1. Determining whether or not packet reordering has occurred. 239 2. Quantifying the degree of reordering. (We define a number of 240 metrics to meet this goal, because receiving procedures differ 241 by protocol or application. Since the affects of packet 242 reordering vary with these procedures, a metric that quantifies 243 a key aspect of one receiver's behavior could be irrelevant to 244 a different receiver. If all the metrics defined below are 245 reported, they give a wide-ranging view of reordering 246 conditions.) 248 Reordering Metrics MUST: 250 + have one or more applications, such as receiver design or network 251 characterization, and a compelling relevance in the working 252 group's view. 253 + be computable "on the fly" 254 + work even if the stream has duplicate or lost packets 255 It is desirable for Reordering Metrics to have one or more of the 256 following attributes: 258 + ability to concatenate results for segments measured separately 259 to estimate the reordering of an entire path 260 + simplicity for easy consumption and understanding 261 + relevance to TCP design 262 + relevance to Real-time application performance 264 The current set of metrics meet all the requirements above and 265 provides all but the concatenation attribute (except in the case 266 where segments exhibit no reordering, and one may estimate that the 267 segment concatenation would also exhibit this desirable outcome). 268 However, satisfying these goals restricts the set of metrics to 269 those that provide some clear insight into network characterization 270 or receiver design. They are not likely to be exhaustive in their 271 coverage of reordering effects on applications, and additional 272 measurements may be possible. 274 2.3 Required Context for All Reordering Metrics 276 A critical aspect of all reordering metrics is their inseparable 277 bond with the measurement conditions. Packet reordering is not well 278 defined unless the full measurement context is reported. Therefore, 279 all reordering metric definitions include the following parameters: 281 1. The "Packet of Type-P" [RFC2330] identifiers for the packet 282 stream, including the transport addresses for source and 283 destination, and any other information which may result in different 284 packet treatments. 286 2. The stream parameter set for the sending discipline, such as the 287 parameters unique to Periodic Streams (as in RFC 3432 [RFC3432]), 288 TCP-like Streams (as in RFC 3148 [RFC3148]), or Poisson Streams (as 289 in RFC 2330 [RFC2330]. The stream parameters include the packet 290 size, either specified as a fixed value or as a pattern of sizes (as 291 applicable). 293 Whenever a metric is reported, it MUST include a description of 294 these parameters to provide a context for the results. 296 3. A Reordered Packet Singleton Metric 298 The IPPM framework RFC 2330 [RFC2330] describes the notions of 299 singletons, samples, and statistics. For easy reference: 301 By a 'singleton' metric, we refer to metrics that are, 302 in a sense, atomic. For example, a single instance of "bulk 303 throughput capacity" from one host to another might be defined 304 as a singleton metric, even though the instance involves 305 measuring the timing of a number of Internet packets. 307 The evaluation of packet order requires several supporting concepts. 308 The first is an algorithm (function) that produces a series of 309 monotonically increasing identifiers applied to packets at the 310 source to uniquely establish the order of packet transmission. The 311 unique sequence identifier may simply be an incrementing integer 312 message number, as used below. 314 The second supporting concept is a stored value which is the "next 315 expected" packet number. Under normal conditions, the value of Next 316 Expected (NextExp) is the sequence number of the previous packet 317 plus 1 for message numbering (in general, the receiver reproduces 318 the sender's algorithm and the sequence of identifiers so that the 319 "next expected" can be determined). 321 Each packet within a packet stream can be evaluated with this order 322 singleton metric. 324 3.1 Metric Name: 326 Type-P-Reordered 328 3.2 Metric Parameters: 330 + Src, the IP address of a host 332 + Dst, the IP address of a host 334 + SrcTime, the time of packet emission from the Source (or wire 335 time) 337 + s, the unique packet sequence number applied at the Source, in 338 units of messages. 340 + NextExp, the Next Expected Sequence number at the Destination, in 341 units of messages. The stored value in NextExp is determined from 342 a previously arriving packet. 344 And optionally: 346 + PayloadSize, the number of bytes contained in the information 347 field and referred to when the SrcByte sequence is based on bytes 348 transfered. 350 + SrcByte, the packet sequence number applied at the Source, in 351 units of payload bytes. 353 3.3 Definition: 355 If a packet s, (sent at time, SrcTime) is found to be reordered by 356 comparison with the Next Expected value, its Type-P-Reordered = 357 TRUE; otherwise Type-P-Reordered = FALSE, as defined below: 359 The value of Type-P-Reordered is defined as TRUE if s < NextExp (the 360 packet is reordered). In this case, the NextExp value does not 361 change. 363 The value of Type-P-Reordered is defined as FALSE if s >= NextExp 364 (the packet is in-order). In this case, NextExp is set to s+1 for 365 comparison with the next packet to arrive. 367 Since the Next Expected value cannot decrease, it provides a non- 368 reversing order criterion to identify reordered packets. 370 This definition can also be specified in pseudo-code. 372 On successful arrival of a packet with sequence number s: 373 if s >= NextExp then /* s is in-order */ 374 NextExp = s + 1; 375 Type-P-Reordered = False; 376 else /* when s < NextExp */ 377 Type-P-Reordered = True 379 3.4 Sequence Discontinuity Definition 381 Packets with s > NextExp are a special case of in-order delivery. 382 This condition indicates a sequence discontinuity, either because of 383 packet loss or reordering. Reordered packets must arrive for the 384 sequence discontinuity to be defined as a reordering discontinuity 385 (see section 4). 387 We define two different states for in-order packets. 389 When s = NextExp, the original sequence has been maintained, and 390 there is no discontinuity present. 392 When s > NextExp, some packets in the original sequence have not yet 393 arrived, and there is a sequence discontinuity associated with 394 packet s. The size of the discontinuity is s - NextExp, equal to 395 the number of packets presently missing, either reordered or lost. 397 In pseudo-code: 399 On successful arrival of a packet with sequence number s: 400 if s >= NextExp, then /* s is in-order */ 401 if s > NextExp then 402 SequenceDiscontinuty = True; 403 SeqDiscontinutySize = s - NextExp; 404 else 405 SequenceDiscontinuty = False; 406 NextExp = s + 1; 407 Type-P-Reordered = False; 409 else /* when s < NextExp */ 410 Type-P-Reordered = True; 411 SequenceDiscontinuty = False; 413 Whether there are any Sequence Discontinuities and their size is 414 determined by the conditions causing loss and/or reordering along 415 the measurement path. Note that a packet could be reordered at one 416 point, and subsequently lost elsewhere on the path, but this cannot 417 be known from observations at the Destination. 419 3.5 Evaluation of Reordering in Dimensions of Time or Bytes 421 It is possible to use alternate dimensions of time or payload bytes 422 to test for reordering in the definition of section 3.3, as long as 423 the SrcTimes and SrcBytes are unique and reliable. Sequence 424 Discontinuities are easily defined and detected with message 425 numbering, however, this is not so simple in the dimensions of time 426 or bytes. This is a detractor for the alternate dimensions because 427 the Sequence Discontinuity definition plays a key role in the sample 428 metrics that follow. 430 It is possible to detect Sequence Discontinuities with payload byte 431 numbering, but only when the complete pattern of payload sizes is 432 stored at the Destination, or when payload size is constant and then 433 the byte numbering adds needless complexity over message numbering. 435 It may be possible to detect Sequence Discontinuities with Periodic 436 Streams and Source Time numbering, but there are practical pitfalls 437 with sending exactly on-schedule and with clock reliability. 439 The dimensions of time and bytes remain an important basis for 440 characterizing the extent of reordering, as described later. 442 3.6 Discussion 444 Any arriving packet bearing a sequence number from the sequence that 445 establishes the Next Expected value can be evaluated to determine 446 whether it is in-order or reordered, based on a previous packet's 447 arrival. In the case where Next Expected is Undefined (because the 448 arriving packet is the first successful transfer), the packet is 449 designated in-order (Type-P-Reordered=FALSE). 451 This metric assumes re-assembly of packet fragments before 452 evaluation. In principle, it is possible to use the Type-P-Reordered 453 metric to evaluate reordering among packet fragments, but each 454 fragment must contain source sequence information. 455 See the Appendix on fragment order evaluation for more detail. 457 If duplicate packets (multiple non-corrupt copies) arrive at the 458 destination, they MUST be noted and only the first to arrive is 459 considered for further analysis (copies would be declared reordered 460 according to the definition above). This requirement has the same 461 storage implications as earlier IPPM metrics, and follows the 462 precedent of RFC 2679. We provide a suggestion to minimize storage 463 size needed in the section on Measurement and Implementation Issues. 465 4. Sample Metrics 467 In this section, we define metrics applicable to a sample of packets 468 from a single Source sequence number system. When reordering occurs, 469 it is highly desirable to assert the degree to which a packet is 470 out-of-order, or reordered with respect other packets. This section 471 defines several metrics that quantify the extent of reordering in 472 various units of measure. Each metric highlights a relevant use. 474 The metrics in the sub-sections below have a network 475 characterization orientation, but also have relevance to receiver 476 design where reordering compensation is of interest. We begin with a 477 simple ratio metric indicating the reordered portion of the sample. 479 4.1 Reordered Packet Ratio 481 4.1.1 Metric Name: 483 Type-P-Reordered-Ratio-Stream 485 4.1.2 Metric Parameters: 487 The parameter set includes Type-P-Reordered singleton parameters, 488 the parameters unique to Poisson Streams (as in RFC 2330 [RFC2330], 489 Periodic Streams (as in RFC 3432 [RFC3432]), or TCP-like Streams (as 490 in RFC 3148 [RFC3148]), packet size or size patterns, and the 491 following: 493 + T0, a start time 495 + Tf, an end time 497 + dT, a waiting time for each packet to arrive 499 + K, the total number of packets in the stream sent from Source to 500 Destination 502 + L, the total number of packets received (arriving between T0 and 503 Tf+dT) out of the K packets sent. Recall that identical copies 504 (duplicates) have been removed, so L <= K. 506 4.1.3 Definition: 508 Given a stream of packets sent from a Source to a Destination, the 509 ratio of reordered packets in the sample is 510 (Count of packets with Type-P-Reordered=TRUE) / ( L ) 512 This fraction may be expressed as a percentage (multiply by 100). 513 Note that in the case of duplicate packets, only the first copy is 514 used. 516 4.1.4 Discussion 518 When the Type-P-Reordered-Ratio-Stream is zero, no further 519 reordering metrics need be examined for that sample. Therefore, the 520 value of this metric is its simple ability to summarize the results 521 for a reordering-free sample. 523 4.2 Reordering Extent 525 This section defines the extent to which packets are reordered, and 526 associates a specific Sequence Discontinuity with each reordered 527 packet. This section inherits the Parameters defined above. 529 4.2.1 Metric Name: 531 Type-P-packet-Reordering-Extent-Stream 533 4.2.2 Notation and Metric Parameters: 535 Recall that K is the number of packets in the stream at the Source 536 and L is the number of packets received at the Destination. 538 Each packet has been assigned a sequence number, s, a consecutive 539 integer from 1 to K in the order of packet transmission (at the 540 source). 542 Let s[1], s[2], ..., s[L], represent the original sequence numbers 543 associated with the packets in order of arrival. 545 s[i] can be thought of as a vector, where the index i is the arrival 546 position of the packet with sequence number s. In theory, any 547 Source sequence number could appear in any arrival position, but 548 this is unlikely in reality. 550 Consider a reordered packet (Type-P-Reordered=TRUE) with arrival 551 index i and source sequence number s[i]. There exists a set of 552 indexes j (1 <= j < i) such that s[j] > s[i]. 554 The new parameters are: 556 + i, the index for arrival position, where i-1 represents an 557 arrival earlier than i. 559 + j, a set of one or more arrival indexes, where 1 <= j < i. 561 + s[i], the original sequence numbers, s, in order of arrival. 563 + e, the Reordering Extent, defined below. 565 4.2.3 Definition: 567 The reordering extent, e, of packet s[i] is defined to be i-j for 568 the smallest value of j where s[j] > s[i]. 570 Informally, the reordering extent is the maximum distance, in 571 packets, from a reordered packet to the earliest packet received 572 that has a larger sequence number. If a packet is in-order, its 573 reordering extent is undefined. The first packet to arrive is in- 574 order by definition, and has undefined reordering extent. 576 Comment on the definition of extent: For some arrival orders, the 577 assignment of a simple position/distance as the reordering extent 578 tends to overestimate the receiver storage needed to restore order. 579 A more accurate and complex procedure to calculate packet storage 580 would be to subtract any earlier reordered packets that the receiver 581 could pass on to the upper layers (see the Byte Offset metric). With 582 the bias understood, this definition is deemed sufficient, 583 especially for those who demand "on the fly" calculations. 585 4.2.4 Discussion: 587 The packet with index j (s[j], identified in the Definition above) 588 is the reordering discontinuity associated with packet s at index i 589 (s[i]). This definition is formalized below. 591 Note that the K packets in the stream could be some subset of a 592 larger stream, but L is still the total number of packets received 593 out of the K packets sent in that subset. 595 If a receiver intends to restore order, then its buffer capacity 596 determines its ability to handle packets that are reordered. For 597 cases with single reordered packets, the extent e gives the number 598 of packets that must be held in the receiver's buffer while waiting 599 for the reordered packet to complete the sequence. For more complex 600 scenarios, the extent may be an overestimate of required storage 601 (see section 4.4 on Reordering Byte Offset and the Examples 602 section). 604 Although reordering extent primarily quantifies the offset in terms 605 of arrival position, it may also be useful for determining the 606 portion of reordered packets that can or cannot be restored to order 607 in a typical receiver buffer based on their arrival order alone (and 608 without the aid of retransmission). 610 A sample's reordering extents may be expressed as a histogram, to 611 easily summarize the frequency of various extents. 613 4.3 Reordering Late Time Offset 615 Reordered packets can be assigned offset values indicating their 616 lateness in terms of buffer time that a receiver must possess to 617 accommodate them. Offset metrics are calculated only on reordered 618 packets, as identified by the reordered packet singleton metric in 619 Section 3. 621 4.3.1 Metric Name: 623 Type-P-packet-Late-Time-Stream 625 4.3.2 Metric Parameters: 627 In addition to the parameters defined for Type-P-Reordered-Ratio- 628 Stream, we specify: 630 + DstTime, the time that each packet in the stream arrives at the 631 destination, and may be associated with index i, or packet s[i] 633 + LateTime(s[i]), the offset of packet s[i] in time, defined below 635 4.3.3 Definition: 637 Lateness in time is calculated using destination times. When 638 received packet s[i] is reordered, and has a reordering extent e, 639 then: 641 LateTime(s[i]) = DstTime(i)-DstTime(i-e) 643 Alternatively, using similar notation to that of section 4.2, an 644 equivalent definition is: 646 LateTime(s[i]) = DstTime(i)-DstTime(j), for min{j|1<=js[i]. 649 4.3.4 Discussion 651 The offset metrics can help predict whether reordered packets will 652 be useful in a general receiver buffer system with finite limits. 653 The limit may be the time of storage prior to a cyclic play-out 654 instant (as with de-jitter buffers). 656 Note that the One-way IPDV [RFC3393] gives the delay variation for a 657 packet w.r.t. the preceding packet in the source sequence. Lateness 658 and IPDV give an indication of whether a buffer at the destination 659 has sufficient storage to accommodate the network's behavior and 660 restore order. When an earlier packet in the Source sequence is 661 lost, IPDV will necessarily be undefined for adjacent packets, and 662 LateTime may provide the only way to evaluate the usefulness of a 663 packet. 665 In the case of de-jitter buffers, there are circumstances where the 666 receiver employs loss concealment at the intended play-out time of a 667 late packet. However, if this packet arrives out of order, the Late 668 Time determines whether the packet is still useful. IPDV no longer 669 applies, because the receiver establishes a new play-out schedule 670 with additional buffer delay to accommodate similar events in the 671 future (this requires very minimal processing). 673 The combination of loss and reordering influences the LateTime 674 metric. If presented with the arrival sequence 1, 10, 5 (where 675 packets 2, 3, 4, and 6 through 9 are lost), LateTime would not 676 indicate exactly how "late" packet 5 is from its intended arrival 677 position. IPDV [RFC3393] would not capture this either, because of 678 the lack of adjacent packet pairs. Assuming a Periodic Stream 679 [RFC3432], an expected arrival time could be defined for all 680 packets, but this is essentially a single-point delay variation 681 metric (as defined in ITU-T Recommendations [I.356] and [Y.1540]), 682 and not a reordering metric. 684 A sample's LateTime results may be expressed as a histogram, to 685 summarize the frequency of buffer times needed to accommodate 686 reordered packets and permit buffer tuning on that basis. A CDF with 687 buffer time vs. percent of reordered packets accommodated may be 688 informative. 690 4.4 Reordering Byte Offset 692 Reordered packets can be assigned offset values indicating the 693 storage in bytes that a receiver must possess to accommodate them. 694 Offset metrics are calculated only on reordered packets, as 695 identified by the reordered packet singleton metric in Section 3. 697 4.4.1 Metric Name: 699 Type-P-packet-Byte-Offset-Stream 701 4.4.2 Metric Parameters: 703 We use the same parameters defined earlier, including the optional 704 parameters of SrcByte and PayloadSize, and define: 706 + ByteOffset(s[i]), the offset of packet s[i] in bytes 708 4.4.3 Definition: 710 The Byte stream offset for reordered packet s[i] is the sum of the 711 payload sizes of packets qualified by the following criteria: 713 * Arrival prior to the reordered packet, s[i], and 714 * The send sequence number, s, is greater than s[i]. 716 Packets that meet both these criteria are normally buffered until 717 the sequence beneath them is complete. Note that these criteria 718 apply to both in-order and reordered packets. 720 For reordered packet s[i] with a reordering extent e: 721 ByteOffset(s[i]) = Sum[qualified packets] 722 = Sum[PayloadSize(packet at i-1 if qualified), 723 PayloadSize(packet at i-2 if qualified), ... 724 PayloadSize(packet at i-e always qualified)] 726 Using our earlier notation: 727 ByteOffset(s[i]) = 728 Sum[payloads of s[j] where s[j]>s[i] and i > j >= i-e] 730 4.4.4 Discussion 732 We note that estimates of buffer size due to reordering depend on 733 greatly on the test stream, in terms of the spacing between test 734 packets and their size, especially when packet size is variable. In 735 these and other circumstances, it may be most useful to characterize 736 offset in terms of the payload size(s) of stored packets, using the 737 Type-P-packet-Byte-Offset-Stream metric. 739 The byte offset metric can help predict whether reordered packets 740 will be useful in a general receiver buffer system with finite 741 limits. The limit is expressed as the number of bytes the buffer 742 can store. 744 A sample's ByteOffset results may be expressed as a histogram, to 745 summarize the frequency of buffer lengths needed to accommodate 746 reordered packets and permit buffer tuning on that basis. A CDF with 747 buffer size vs. percent of reordered packets accommodated may be 748 informative. 750 4.5 Gaps between multiple Reordering Discontinuities 752 4.5.1 Metric Name: 754 Type-P-packet-Reordering-Gap-Stream 756 4.5.2 Parameters: 758 We use the same parameters defined earlier, but add the convention 759 that index i' is greater than i, likewise j' > j, and define: 761 + Gap(s[j']), the Reordering Gap of packet s[j'] in units of 762 integer messages 764 + GapTime(s[j']), the Reordering Gap of packet s[j'] in units of 765 time 767 4.5.3 Definition of Reordering Discontinuity: 769 All reordered packets are associated with a packet at a reordering 770 discontinuity, defined as the in-order packet s[j] that arrived at 771 the minimum value of j (1<=j s[i]. 773 Note that s[j] will have been found to cause a sequence 774 discontinuity, where s > NextExp when evaluated with the reordered 775 singleton metric as described in section 3.4. 777 Recall that i - e = min(j). Subsequent reordered packets may be 778 associated with the same s[j], or with a different discontinuity. 779 This fact is used in the definition of the Reordering Gap, below. 781 4.5.4 Definition of Reordering Gap: 783 A reordering gap is the distance between successive reordering 784 discontinuities. Type-P-packet-Reordering-Gap-Stream assigns a value 785 to (all) packets in a stream. 787 If: 789 The packet s[j'] is found to be a reordering discontinuity, based 790 on the arrival of reordered packet s[i'] with extent e', and 792 an earlier reordering discontinuity s[j], based on the arrival of 793 reordered packet s[i] with extent e was already detected, and 795 i' > i, and 797 there are no reordering discontinuities between j and j', 799 then the Reordering Gap for packet s[j'] is the difference between 800 the arrival positions the reordering discontinuities, as shown 801 below: 803 Gap(s[j']) = (j') - (j) 805 Otherwise: 807 The Type-P-packet-Reordering-Gap-Stream for the packet is 0. 809 Gaps may also be expressed in time: 811 GapTime(s[j']) = DstTime(j') - DstTime(j) 813 4.5.5 Discussion 814 When separate reordering discontinuities can be distinguished, then 815 a count may also be reported (along with the discontinuity 816 description, such as the number of reordered packets associated with 817 that discontinuity and their extents and offsets). The Gaps between 818 a sample's reordering discontinuities may be expressed as a 819 histogram, to easily summarize the frequency of various gaps. 820 Reporting the mode, average, range, etc. may also summarize the 821 distributions. 823 The Gap metric may help to correlate the frequency of reordering 824 discontinuities with their cause. Gap lengths are also informative 825 to receiver designers, revealing the period of reordering 826 discontinuities. The combination of reordering gaps and extent 827 reveals whether receivers will be required to handle cases of 828 overlapping reordered packets. 830 4.6 Reordering-free Runs 832 This section defines a metric based on a count of consecutive in- 833 order packets between reordered packets. 835 4.6.1 Metric Name: 837 Type-P-packet-Reordering-Free-Run-Stream 839 4.6.2 Parameters: 841 We use the same parameters defined earlier, and define the 842 following: 844 + r, the run counter 846 + x, the number of runs, also the number of reordered packets 848 + a, the accumulator of in-order packets 850 + p, the number of packets (when the stream is complete, p=(x+a)=L) 852 + q, the sum of the squares of the runs counted 854 4.6.3 Definition: 856 As packets in a sample arrive at the Destination, the count of in- 857 order packets between reordered packets is a Reordering-Free run. 858 Note that the minimum run-length is zero according to this 859 definition. A pseudo code example follows: 861 r = 0; /* r is the run counter */ 862 x = 0; /* x is the number of runs */ 863 a = 0; /* a is the accumulator of in order packets */ 864 p = 0; /* p is the number of packets */ 865 q = 0; /* q is the sum of the squares of the runs counted */ 867 while(packets arrive with sequence number s) 868 { 869 p++; 870 if (s >= NextExp) /* s is in-order */ 871 then r++; 872 a++; 873 else /* s is reordered */ 874 q+= r*r; 875 r = 0; 876 x++; 877 } 879 Each in-order arrival increments the run counter and the accumulator 880 of in order packets, each reordered packet resets the run counter 881 after adding it to the sum of the squared lengths. 883 Each arrival of a reordered packet yields a new run count. Long 884 runs accompany periods where order was maintained, while short runs 885 indicate frequent, or multi-packet reordering. 887 The percent of packets in-order is 100*a/p 889 The average Reordering-Free run length is a/x 891 The q counter gives an indication of variation of the Reordering- 892 Free runs from the average by comparing q/a to a/x ((q/a)/(a/x)) 894 4.6.4 Discussion and Illustration: 896 Type-P-packet-Reordering-Free-Run-Stream parameters give a brief 897 summary of the stream's reordering characteristics including the 898 average reordering-free run length, and the variation of run 899 lengths, therefore a key application of this metric is network 900 evaluation. 902 For 36 packets with 3 runs of 11 in-order packets we have: 903 p = 36 904 x = 3 905 a = 33 906 q = 3 * (11*11) = 363 907 ave reordering-free run = 11 908 q/a = 11 909 (q/a)/(a/x) = 1.0 911 For 36 packets with 3 runs, 2 runs of length 1 and one of length 31 912 p = 36 913 x = 3 914 a = 33 915 q = 1 + 1 + 961 = 963 916 ave reordering-free run = 11 917 q/a = 29.18 918 (q/a)/(a/x) = 2.65 920 The variability in run length is prominent in the difference between 921 the q values (sum of the squared run lengths) and comparing average 922 run length to the (q/a)/(a/x) ratios (equals 1 when all runs are the 923 same length). 925 5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric 927 This section describes a metric that conveys information associated 928 with the affect of reordering on TCP. However, in order to infer 929 anything about TCP performance, the test stream MUST bear a close 930 resemblance to the TCP sender of interest. RFC 3148 [RFC3148] lists 931 the specific aspects of congestion control algorithms that must be 932 specified. Further, RFC 3148 recommends that Bulk Transfer Capacity 933 metrics SHOULD have instruments to distinguish three cases of packet 934 reordering (in section 3.3). The sample metrics defined above 935 satisfy the requirements to classify packets that are slightly or 936 grossly out-of-order. The metric in this section adds the capability 937 to estimate whether reordering might cause the DUP-ACK threshold to 938 be exceeded causing the Fast Retransmit algorithm to be invoked. 939 Additional TCP Kernel Instruments are summarized in [Mat03]. 941 5.1 Metric Name: 943 Type-P-packet-n-Reordering-Stream 945 5.2 Parameter Notation: 947 Let n be a positive integer (a parameter). Let k be a positive 948 integer equal to the number of packets sent (sample size). Let l be 949 a non-negative integer representing the number of packets that were 950 received out of the k packets sent. (Note that there is no 951 relationship between k and l: on one hand, losses can make l less 952 than k; on the other hand, duplicates can make l greater than k.) 953 Assign each sent packet a sequence number, 1 to k, in order of 954 packet emission. 956 Let s[1], s[2], ..., s[l] be the original sequence numbers of the 957 received packets, in the order of arrival. 959 5.3 Definitions 961 Definition 1: Received packet number i (n < i <= l), with source 962 sequence number s[i], is n-reordered if and only if for all j such 963 that i-n <= j < i, s[j] > s[i]. 965 Claim: If by this definition, a packet's reordering is n and 0 < n' 966 < n, then the packet is also reordered to the n' extent. 968 Note: This definition is illustrated by C code in Appendix A. It 969 determines the n-reordering for a value of n=3 (when actually 970 writing applications that would report the metric, one would 971 probably report it for several values of n, such as 1, 2, 3, 4 -- 972 and maybe a few more consecutive values). 974 This definition does not assign an n to all reordered packets as 975 defined by the singleton metric, in particular when blocks of 976 successive packets are reordered. (In the arrival sequence 977 s={1,2,3,7,8,9,4,5,6}, packets 4, 5, and 6 are reordered, but only 978 packet 4 is n-reordered, with n=3.) 980 Definition 2: The degree of n-reordering of the sample is m/l, where 981 m is the number of n-reordered packets in the sample. 983 Definition 3: The degree of "monotonic reordering" of the sample is 984 its degree of 1-reordering. 986 Definition 4: A sample is said to have no reordering if its degree 987 of n-reordering is 0. 989 5.4 Discussion: 991 The degree of n-reordering may be expressed as a percentage, in 992 which case the number from Definition 2 is multiplied by 100. 994 The n-reordering metric is helpful for matching the duplicate ACK 995 threshold setting to a given path. For example, if a path exhibits 996 no more than 5-reordering, a DUP-ACK threshold of 6 may avoid 997 unnecessary retransmissions. 999 Important special cases are n=1 and n=3: 1001 - For n=1, absence of 1-reordering means the sequence numbers that 1002 the receiver sees are monotonically increasing with respect to the 1003 previous arriving packet. 1005 - For n=3, a NewReno TCP sender would retransmit 1 packet in 1006 response to an instance of 3-reordering and therefore consider this 1007 packet lost for the purposes of congestion control (the sender will 1008 half its congestion window, see [RFC2581]). 3 is default threshold 1009 for SCTP [RFC2960], and the future Datagram Congestion Control 1010 Protocol (DCCP). 1012 A sample's n-reordering may be expressed as a histogram, to 1013 summarize the frequency for each value of n. 1015 We note that the definition of n-reordering cannot predict the exact 1016 number of packets unnecessarily retransmitted by a TCP sender under 1017 some circumstances, such as cases with closely-spaced reordered 1018 singletons. Both time and position influence the sender's behavior. 1020 A packet's n-reordering designation is sometimes equal to its 1021 reordering extent, e. n-reordering is different in the following 1022 ways: 1024 1. n is a count of early packets with consecutive arrival positions 1025 at the receiver. 1027 2. Reordered packets (Type-P-Reordered=TRUE) may not be n-reordered, 1028 but will have an extent, e (see the examples). 1030 6. Measurement and Implementation Issues 1032 The results of tests will be dependent on the time interval between 1033 measurement packets (both at the Source, and during transport where 1034 spacing may change). Clearly, packets launched infrequently (e.g., 1035 1 per 10 seconds) are unlikely to be reordered. 1037 In order to gauge the reordering for an application according to the 1038 metrics defined in this memo, it is RECOMMENDED to use the same 1039 sending pattern as the application of interest. In any case, the 1040 exact method of packet generation MUST be reported with the 1041 measurement results, including all stream parameters. 1043 + To make inferences about applications that use TCP, it is 1044 REQUIRED to use TCP-like Streams as in [RFC3148] 1046 + For real-time applications, it is RECOMMENDED to use Periodic 1047 Streams as in [RFC3432] 1049 It is acceptable to report the metrics of Sections 3 and 4 with 1050 other IPPM metrics using Poisson Streams [RFC2330]. Poisson streams 1051 represent an "unbiased sample" of network performance for packet 1052 loss and delay metrics. However, it would be incorrect to make 1053 inferences about the application categories above using reordering 1054 metrics measured with Poisson streams. 1056 Test stream designers may prefer to use a periodic sending interval 1057 so that a known temporal bias is maintained, also bringing 1058 simplified results analysis (as described in [RFC3432]). In this 1059 case, it is RECOMMENDED that the periodic sending interval should be 1060 chosen to reproduce the closest Source packet spacing expected. 1061 Testers must recognize that streams sent at the link speed 1062 serialization limit MUST have limited duration and MUST consider 1063 packet loss as an indication that the stream has caused congestion, 1064 and suspend further testing. 1066 When intending to compare independent measurements of reordering, it 1067 is RECOMMENDED to use the same test stream parameters in each 1068 measurement system. 1070 Packet lengths might also be varied to attempt to detect instances 1071 of parallel processing (they may cause steady state reordering). For 1072 example, a line-speed burst of the longest (MTU-length) packets 1073 followed by a burst of the shortest possible packets may be an 1074 effective detecting pattern. Other size patterns are possible. 1076 The non-reversing order criterion and all metrics described above 1077 remain valid and useful when a stream of packets experiences packet 1078 loss, or both loss and reordering. In other words, losses alone do 1079 not cause subsequent packets to be declared reordered. 1081 Assuming that the necessary sequence information (message number) is 1082 included in the packet payload (possibly in application headers such 1083 as RTP), reordering metrics may be evaluated in a passive 1084 measurement arrangement. Also, it is possible to evaluate order at 1085 any point along a Source-Destination path, recognizing that 1086 intermediate measurements may differ from those made at the 1087 Destination (where the reordering affect on applications can be 1088 inferred). 1090 It is possible to apply these metrics to evaluate reordering in a 1091 TCP sender's stream. In this case, the Source sequence numbers would 1092 be based on byte stream, or segment numbering. Since the stream may 1093 include retransmissions due to loss or reordering, care must be 1094 taken to avoid declaring retransmitted packets reordered. The 1095 additional sequence reference of s or SrcTime helps to avoid this 1096 ambiguity, or the optional TCP timestamp field [RFC1323]. 1098 Since this metric definition may use sequence numbers with finite 1099 range, it is possible that the sequence numbers could reach end-of- 1100 range and roll over to zero during a measurement. By definition, 1101 the Next Expected value cannot decrease, and all packets received 1102 after a roll-over would be declared reordered. Sequence number 1103 roll-over can be avoided by using combinations of counter size and 1104 test duration where roll-over is impossible (and sequence is reset 1105 to zero at the start). Also, message-based numbering results in 1106 slower sequence consumption. There may still be cases where 1107 methodological mitigation of this problem is desirable (e.g., long- 1108 term testing). The elements of mitigation are: 1110 1. There must be a test to detect if a roll-over has occurred. It 1111 would be nearly impossible for the sequence numbers of successive 1112 packets to jump by more than half the total range, so these large 1113 discontinuities are designated as roll-over. 1115 2. All sequence numbers used in computations are represented in a 1116 sufficiently large precision. The numbers have a correction applied 1117 (equivalent to adding a significant digit) whenever roll-over is 1118 detected. 1120 3. Reordered packets coincident with sequence numbers reaching end- 1121 of-range must also be detected for proper application of correction 1122 factor. 1124 Ideally, the test instrument would have the ability to use all 1125 earlier packets at any point in the test stream. In practice there 1126 will be limited ability to determine reordering extent, due to the 1127 storage requirements for previous packets. Saving only packets that 1128 indicate discontinuities (and their arrival positions) will reduce 1129 storage volume. 1131 Another solution is to use a sliding history window of packets, 1132 where the window size would be determined by an upper bound on the 1133 useful reordering extent. This bound could be several packets or 1134 several seconds-worth of packets, depending on the intended 1135 analysis. When discarding all stream information beyond the window, 1136 the reordering extent or degree of n-reordering may need to be 1137 expressed as greater than the window length if the reordering 1138 discontinuity information has been discarded, and Gap calculations 1139 would not be possible. 1141 The requirement to ignore duplicate packets also mandates storage. 1142 Here, tracking the sequence numbers of missing packets may minimize 1143 storage size. Missing packets may eventually be declared lost, or 1144 reordered if they arrive. The missing packet list and the largest 1145 sequence number received thus far (NextExp - 1) are sufficient 1146 information to determine if a packet is a duplicate (assuming a 1147 manageable storage size for packets that are missing due to loss). 1149 It is important to note that practical IP networks also have limited 1150 ability to "store" packets, even when routing loops appear 1151 temporarily. Therefore, the storage for reordering metrics (and 1152 their complexity) would only approach the number packets in the 1153 sample, K, when the sending time for K packets is small with respect 1154 to the network's largest possible transfer time. 1156 Last, we note that determining reordering extents and gaps is tricky 1157 when there are overlapped or nested events. Test instrument 1158 complexity and reordering complexity are directly correlated. 1160 7. Examples of Arrival Order Evaluation 1162 This section provides some examples to illustrate how the non- 1163 reversing order criterion works, how n-reordering works in 1164 comparison, and the value of quantifying reordering in all the 1165 dimensions of time, bytes, and position. 1167 Throughout this section, we will refer to packets by their source 1168 sequence number, except where noted. So "Packet 4" refers to the 1169 packet with source sequence number 4, and the reader should refer to 1170 the tables in each example to determine packet 4's arrival index 1171 number, if needed. 1173 7.1 Example with a single packet reordered 1175 Table 1 gives a simple case of reordering, where one packet is 1176 reordered, Packet 4. Packets are listed according to their arrival, 1177 and message numbering is used. All packets contain PayloadSize=100 1178 bytes, with SrcByte=(s x 100)-99 for s=1,2,3,4,... 1180 Table 1 Example with Packet 4 Reordered, 1181 Sending order(SrcNum@Src): 1,2,3,4,5,6,7,8,9,10 1182 s Src Dst Dst Byte Late 1183 @Dst NextExp Time Time Delay IPDV Order Offset Time 1184 1 1 0 68 68 1 1185 2 2 20 88 68 0 2 1186 3 3 40 108 68 0 3 1187 5 4 80 148 68 -82 4 1188 6 6 100 168 68 0 5 1189 7 7 120 188 68 0 6 1190 8 8 140 208 68 0 7 1191 4 9 60 210 150 82 8 400 62 1192 9 9 160 228 68 0 9 1193 10 10 180 248 68 0 10 1195 Each column gives the following information: 1197 s Packet sequence number at the Source. 1198 NextExp The value of NextExp when the packet arrived(before 1199 update). 1200 SrcTime Packet time stamp at the Source, ms. 1201 DstTime Packet time stamp at the Destination, ms. 1202 Delay 1-way delay of the packet, ms. 1203 IPDV IP Packet Delay Variation, ms 1204 IPDV = Delay(SrcNum)-Delay(SrcNum-1) 1205 DstOrder Order in which the packet arrived at the Destination. 1206 Byte Offset The Byte Offset of a reordered packet, in bytes. 1207 LateTime The lateness of a reordered packet, in ms. 1209 We can see that when Packet 4 arrives, NextExp=9, and it is declared 1210 reordered. We compute the extent of reordering as follows: 1212 Using the notation , the received 1213 packets are represented as: 1215 \/ 1216 s = 1, 2, 3, 5, 6, 7, 8, 4, 9, 10 1217 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 1218 /\ 1220 Applying the definition of Type-P-packet-Reordering-Extent-Stream: 1221 when j=7, 8 > 4, so the reordering extent is 1 or more. 1222 when j=6, 7 > 4, so the reordering extent is 2 or more. 1223 when j=5, 6 > 4, so the reordering extent is 3 or more. 1224 when j=4, 5 > 4, so the reordering extent is 4 or more. 1225 when j=3, but 3 < 4, and 4 is the maximum extent, e=4 (assuming 1226 there are no earlier sequence discontinuities, as in this example). 1228 Further, we can compute the Late Time (210-148=62ms using DstTime) 1229 compared to Packet 5's arrival. If the receiver has a de-jitter 1230 buffer that holds more than 4 packets, or at least 62 ms storage, 1231 Packet 4 may be useful. Note that 1-way delay and IPDV indicate 1232 unusual behavior for Packet 4. Also, if Packet 4 had arrived at 1233 least 62ms earlier, it would have been in-order in this example. 1235 If all packets contained 100 byte payloads, then Byte Offset is 1236 equal to 400 bytes. 1238 Following the definitions of section 5.1, Packet 4 is designated 4- 1239 reordered. 1241 7.2 Example with two packets reordered 1243 Table 2 Example with Packets 5 and 6 Reordered, 1244 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10 1245 s Src Dst Dst Byte Late 1246 @Dst NextExp Time Time Delay IPDV Order Offset Time 1247 1 1 0 68 68 1 1248 2 2 20 88 68 0 2 1249 3 3 40 108 68 0 3 1250 4 4 60 128 68 0 4 1251 7 5 120 188 68 -22 5 1252 5 8 80 189 109 41 6 100 1 1253 6 8 100 190 90 -19 7 100 2 1254 8 8 140 208 68 0 8 1255 9 9 160 228 68 0 9 1256 10 10 180 248 68 0 10 1258 Table 2 shows a case where Packets 5 and 6 arrive just behind Packet 1259 7, so both 5 and 6 are reordered. The Late times (189-188=1, 190- 1260 188=2) are small. 1262 Using the notation , the received 1263 packets are represented as: 1265 \/ \/ 1266 s = 1, 2, 3, 4, 7, 5, 6, 8, 9, 10 1267 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 1268 /\ /\ 1270 Considering Packet 5 first: 1271 when j=5, 7 > 5, so the reordering extent is 1 or more. 1272 when j=4, we have 4 < 5, so 1 is its maximum extent, and e=1. 1274 Considering Packet 6 next: 1275 when j=6, 5 < 6, the extent is not yet defined. 1276 when j=5, 7 > 6, so the reordering extent is i-j=2 or more. 1277 when j=4, 4 < 6, and we find 2 is its maximum extent, and e=2. 1279 We can also associate each of these reordered packets with a 1280 reordering discontinuity. We find the minimum j=5 (for both packets) 1281 according to Section 4.2.3. So Packet 6 is associated with the same 1282 reordering discontinuity as Packet 5, the Reordering Discontinuity 1283 at Packet 7. 1285 This is a case where reordering extent e would over-estimate the 1286 packet storage required to restore order. Only one packet storage is 1287 required (to hold Packet 7), but e=2 for Packet 6. 1289 Following the definitions of section 5, Packet 5 is designated 1- 1290 reordered, but Packet 6 is not designated n-reordered. 1292 A hypothetical sender/receiver pair may retransmit Packet 5 1293 unnecessarily, since it is 1-reordered (in agreement with the 1294 singleton metric). Though Packet 6 may not be unnecessarily 1295 retransmitted, the receiver cannot advance Packet 7 to the higher 1296 layers until after Packet 6 arrives. Therefore, the singleton metric 1297 correctly determined that Packet 6 is reordered. 1299 7.3 Example with three packets reordered 1301 Table 3 Example with Packets 4, 5, and 6 reordered 1302 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11 1303 s Src Dst Dst Byte Late 1304 @Dst NextExp Time Time Delay IPDV Order Offset Time 1305 1 1 0 68 68 1 1306 2 2 20 88 68 0 2 1307 3 3 40 108 68 0 3 1308 7 4 120 188 68 -88 4 1309 8 8 140 208 68 0 5 1310 9 9 160 228 68 0 6 1311 10 10 180 248 68 0 7 1312 4 11 60 250 190 122 8 400 62 1313 5 11 80 252 172 -18 9 400 64 1314 6 11 100 256 156 -16 10 400 68 1315 11 11 200 268 68 0 11 1317 The case in Table 3 is where three packets in sequence have long 1318 transit times (Packets with s = 4,5,and 6). Delay, Late time, and 1319 Byte Offset capture this very well, and indicate variation in 1320 reordering extent, while IPDV indicates that the spacing between 1321 packets 4,5,and 6 has changed. 1323 The histogram of Reordering extents (e) would be: 1325 Bin 1 2 3 4 5 6 7 1326 Frequency 0 0 0 1 1 1 0 1328 Using the notation , the received 1329 packets are represented as: 1331 s = 1, 2, 3, 7, 8, 9,10, 4, 5, 6, 11 1332 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11 1334 We first calculate the n-reordering. Considering Packet 4 first: 1335 when n=1, 7<=j<8, and 10> 4, so the packet is 1-reordered. 1336 when n=2, 6<=j<8, and 9 > 4, so the packet is 2-reordered. 1337 when n=3, 5<=j<8, and 8 > 4, so the packet is 3-reordered. 1338 when n=4, 4<=j<8, and 7 > 4, so the packet is 4-reordered. 1339 when n=5, 3<=j<8, but 3 < 4, and 4 is the maximum n-reordering. 1341 Considering packet 5[9] next: 1342 when n=1, 8<=j<9, but 4 < 5, so the packet at i=9 is not designated 1343 as n-reordered. We find the same to for Packet 6. 1345 We now consider whether reordered Packets 5 and 6 are associated 1346 with the same reordering discontinuity as Packet 4. Using the test 1347 of Section 4.2.3, we find that the minimum j=4 for all three 1348 packets. They are all associated with the reordering discontinuity 1349 at Packet 7. 1351 This example shows again that the n-reordering definition identifies 1352 a single Packet (4) with a sufficient degree of n-reordering that 1353 might cause one unnecessary packet retransmission by the New Reno 1354 TCP sender (with DUP-ACK threshold=3 or 4). Also, the reordered 1355 arrival of Packets 5 and 6 will allow the receiver process to pass 1356 Packets 7 through 10 up the protocol stack (the singleton Type-P- 1357 Reordered = TRUE for Packets 5 and 6, and they are all associated 1358 with a single reordering discontinuity). 1360 7.4 Example with Multiple Packet Reordering Discontinuities 1362 Table 4 Example with Multiple Packet Reordering Discontinuities 1363 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 1365 Discontinuity Discontinuity 1366 |---------Gap---------| 1367 s = 1, 2, 3, 6, 7, 4, 5, 8, 9, 10, 12, 13, 11, 14, 15, 16 1368 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 1370 r = 1, 2, 3, 4, 5, 0, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, ... 1371 number of runs,n = 1 2 3 1372 end r counts = 5 0 5 1373 (these values are computed after the packet arrives) 1375 Packet 4 has extent e=2, Packet 5 has extent e=3, and Packet 11 has 1376 e=2. There are two different reordering discontinuities, one at 1377 Packet 6 (where j=4) and one at Packet 12 (where j'=11). 1379 According to the definition of Reordering Gap 1380 Gap(s[j']) = (j') - (j) 1381 Gap(Packet 12) = (11) - (4) = 7 1383 We also have three reordering-free runs of lengths 5, 0, and 5. 1385 The differences between these two multiple-event metrics are evident 1386 here. Gaps are the distance between sequence discontinuities that 1387 are subsequently defined as reordering discontinuities, while 1388 reordering-free runs capture the distance between reordered packets. 1390 8. Security Considerations 1392 8.1 Denial of Service Attacks 1394 This metric requires a stream of packets sent from one host (source) 1395 to another host (destination) through intervening networks. This 1396 method could be abused for denial of service attacks directed at 1397 destination and/or the intervening network(s). 1399 Administrators of source, destination, and the intervening 1400 network(s) should establish bilateral or multi-lateral agreements 1401 regarding the timing, size, and frequency of collection of sample 1402 metrics. Use of this method in excess of the terms agreed between 1403 the participants may be cause for immediate rejection or discard of 1404 packets or other escalation procedures defined between the affected 1405 parties. 1407 8.2 User data confidentiality 1409 Active use of this method generates packets for a sample, rather 1410 than taking samples based on user data, and does not threaten user 1411 data confidentiality. Passive measurement must restrict attention to 1412 the headers of interest. Since user payloads may be temporarily 1413 stored for length analysis, suitable precautions MUST be taken to 1414 keep this information safe and confidential. In most cases, a 1415 hashing function will produce a value suitable for payload 1416 comparisons. 1418 8.3 Interference with the metric 1420 It may be possible to identify that a certain packet or stream of 1421 packets is part of a sample. With that knowledge at the destination 1422 and/or the intervening networks, it is possible to change the 1423 processing of the packets (e.g. increasing or decreasing delay) that 1424 may distort the measured performance. It may also be possible to 1425 generate additional packets that appear to be part of the sample 1426 metric. These additional packets are likely to perturb the results 1427 of the sample measurement. 1429 To discourage the kind of interference mentioned above, packet 1430 interference checks, such as cryptographic hash, may be used. 1432 9. IANA Considerations 1434 Since this metric does not define a protocol or well-known values, 1435 there are no IANA considerations in this memo. 1437 10. Normative References 1439 [RFC791] Postel, J., "Internet Protocol", STD 5, RFC 791, 1440 September 1981. 1441 Obtain via: http://www.rfc-editor.org/rfc/rfc791.txt 1443 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1444 Requirement Levels", RFC 2119, March 1997. 1445 Obtain via: http://www.rfc-editor.org/rfc/rfc2119.txt 1447 [RFC2330] Paxson, V., Almes, G., Mahdavi, J., and Mathis, M., 1448 "Framework for IP Performance Metrics", RFC 2330, May 1449 1998. 1450 Obtain via: http://www.rfc-editor.org/rfc/rfc2330.txt 1452 [RFC3148] Mathis, M. and Allman, M., "A Framework for Defining 1453 Empirical Bulk Transfer Capacity Metrics", RFC 3148, July 1454 2001. 1455 Obtain via: http://www.rfc-editor.org/rfc/rfc3148.txt 1457 [RFC3432] Raisanen, V., Grotefeld, G., and Morton, A., "Network 1458 performance measurement with periodic streams", RFC 3432, 1459 November 2002. 1461 11. Informative References 1463 [Bel02] J.Bellardo and S.Savage, "Measuring Packet Reordering," 1464 Proceedings of the ACM SIGCOMM Internet Measurement 1465 Workshop 2002, November 6-8, Marseille, France. 1467 [Ben99] J.C.R.Bennett, C.Partridge, and N.Shectman, "Packet 1468 Reordering is Not Pathological Network Behavior," 1469 IEEE/ACM Transactions on Networking, vol.7, no.6, pp.789- 1470 798, December 1999. 1472 [Cia00] L.Ciavattone and A.Morton, "Out-of-Sequence Packet 1473 Parameter Definition (for Y.1540)", Contribution number 1474 T1A1.3/2000-047, October 30, 2000. 1475 ftp://ftp.t1.org/pub/t1a1/2000-A13/0a130470.doc 1477 [Cia03] L.Ciavattone, A.Morton, and G.Ramachandran, "Standardized 1478 Active Measurements on a Tier 1 IP Backbone," IEEE 1479 Communications Mag., pp 90-97, June 2003. 1481 [I.356] ITU-T Recommendation I.356, "B-ISDN ATM layer cell 1482 transfer performance", March 2000. 1484 [Jai02] S.Jaiswal et al., "Measurement and Classification of Out- 1485 of-Sequence Packets in a Tier-1 IP Backbone," Proceedings 1486 of the ACM SIGCOMM Internet Measurement Workshop 2002, 1487 November 6-8, Marseille, France. 1489 [Lou01] D.Loguinov and H.Radha, "Measurement Study of Low-bitrate 1490 Internet Video Streaming", Proceedings of the ACM SIGCOMM 1491 Internet Measurement Workshop 2001 November 1-2, 2001, 1492 San Francisco, USA. 1494 [Mat03] M. Mathis, J Heffner and R Reddy, "Web100: Extended TCP 1495 Instrumentation for Research, Education and Diagnosis", 1496 ACM Computer Communications Review, Vol 33, Num 3, July 1497 2003. http://www.web100.org/docs/mathis03web100.pdf 1499 [Pax98] V.Paxson, "Measurements and Analysis of End-to-End 1500 Internet Dynamics," Ph.D. dissertation, U.C. Berkeley, 1501 1997, ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz. 1503 [RFC793] Postel, J., "Transmission Control Protocol", STD 7, RFC 1504 793, September 1981. 1505 Obtain via: http://www.rfc-editor.org/rfc/rfc793.txt 1507 [RFC1323] Jacobson, V., Braden, R., and Borman, D., "TCP Extensions 1508 for High Performance", RFC 1323, May 1992. 1510 [RFC2581] Allman, M., Paxson, V., and Stevens, W., "TCP Congestion 1511 Control", RFC 2581, April 1999. 1513 [RFC2960] Stewart, R., et al., "Stream Control Transmission 1514 Protocol", RFC 2960, October 2000. 1516 [RFC3393] Demichelis, C., and Chimento, P., "IP Packet Delay 1517 Variation Metric for IP Performance Metrics (IPPM)", RFC 1518 3393, November 2002. 1520 [TBABAJ02] T. Banka, A. A. Bare, A. P. Jayasumana, "Metrics for 1521 Degree of Reordering in Packet Sequences", Proc. 27th 1522 IEEE Conference on Local Computer Networks, Tampa, FL, 1523 Nov. 2002. 1525 [Y.1540] ITU-T Recommendation Y.1540, "Internet protocol data 1526 communication service - IP packet transfer and 1527 availability performance parameters", December 2002. 1529 12. Acknowledgments 1531 The authors would like to acknowledge many helpful discussions with 1532 Matt Zekauskas, Jon Bennett (who authored the sections on 1533 Reordering-Free Runs), and Matt Mathis. We thank David Newman, Henk 1534 Uijterwaal, Mark Allman, Vern Paxson, and Phil Chimento for their 1535 reviews and suggestions, and Michal Przybylski for sharing 1536 implementation experiences with us on the ippm-list. Anura 1537 Jayasumana and Nischal Piratla brought in recent work-in-progress 1538 [TBABAJ02]. We gratefully acknowledge the foundation laid by the 1539 authors of the IP performance Framework [RFC2330]. 1541 13. Appendix A Example Implementations in C (Informative) 1543 Two example c-code implementations of reordering definitions follow: 1545 Example 1 n-reordering ============================================ 1547 #include 1549 #define MAXN 100 1551 #define min(a, b) ((a) < (b)? (a): (b)) 1552 #define loop(x) ((x) >= 0? x: x + MAXN) 1554 /* 1555 * Read new sequence number and return it. Return a sentinel value 1556 * of EOF (at least once) when there are no more sequence numbers. 1557 * In this example, the sequence numbers come from stdin; 1558 * in an actual test, they would come from the network. 1559 * 1560 */ 1561 int 1562 read_sequence_number() 1563 { 1564 int res, rc; 1565 rc = scanf("%d\n", &res); 1566 if (rc == 1) return res; 1567 else return EOF; 1568 } 1570 int 1571 main() 1572 { 1573 int m[MAXN]; /* We have m[j-1] == number of 1574 * j-reordered packets. */ 1575 int ring[MAXN]; /* Last sequence numbers seen. */ 1576 int r = 0; /* Ring pointer for next write. */ 1577 int l = 0; /* Number of sequence numbers read. */ 1578 int s; /* Last sequence number read. */ 1579 int j; 1581 for (j = 0; j < MAXN; j++) m[j] = 0; 1582 for (;(s = read_sequence_number())!= EOF;l++,r=(r+1)%MAXN) { 1583 for (j=0; j 1602 #define MAXN 100 1603 #define min(a, b) ((a) < (b)? (a): (b)) 1604 #define loop(x) ((x) >= 0? x: x + MAXN) 1606 /* Global counters */ 1607 int receive_packets=0; /* number of received */ 1608 int reorder_packets_Al=0; /* num reordered pkts (singleton) */ 1609 int reorder_packets_Stas=0; /* num reordered pkts(n-reordering)*/ 1611 /* function to test if current packet has been reordered 1612 * returns 0 = not reordered 1613 * 1 = reordered 1614 */ 1615 int testorder1(int seqnum) // Al 1616 { 1617 static int NextExp = 1; 1618 int iReturn = 0; 1620 if (seqnum >= NextExp) { 1621 NextExp = seqnum+1; 1622 } else { 1623 iReturn = 1; 1624 } 1625 return iReturn; 1626 } 1628 int testorder2(int seqnum) // Stanislav 1629 { 1630 static int ring[MAXN]; /* Last sequence numbers seen. */ 1631 static int r = 0; /* Ring pointer for next write */ 1632 int l = 0; /* Number of sequence numbers read. */ 1633 int j; 1634 int iReturn = 0; 1636 l++; 1637 r = (r+1) % MAXN; 1638 for (j=0; j= NextExp, 1715 * AND the fragment offset FragOffset >= NextExpFrag 1717 However, it more efficient to define reordered conditions exactly, 1718 and designate Type-P-Reordered as False otherwise. 1720 The value of Type-P-Reordered is defined as True (the packet is 1721 reordered) under the conditions below. In these cases, the NextExp 1722 value does not change. 1724 Case 1: if s < NextExp 1726 Case 2: if s < FragSeq# 1728 Case 3: if s>= NextExp AND s = FragSeq# AND FragOffset < NextExpFrag 1730 This definition can also be illustrated in pseudo-code. A version of 1731 the code follows, and some simplification may be possible. A 1732 challenging aspect surrounds the housekeeping for the new 1733 parameters. 1735 NextExp=0; 1736 NextExpFrag=0; 1737 FragSeq#=0; 1739 while(packets arrive with s, MoreFrag, FragOffset) 1740 { 1741 if (s>=NextExp AND MoreFrag==0 AND s>=FragSeq#){ 1742 /* a normal packet or last frag of an in-order packet arrived 1743 */ 1744 NextExp = s+1; 1745 FragSeq# = 0; 1746 NextExpFrag = 0; 1747 Reordering = False; 1748 } 1749 if (s>=NextExp AND MoreFrag==1 AND s>FragSeq#>=0){ 1750 /* a fragment of a new packet arrived, possibly with a 1751 higher sequence number than the current fragmented packet */ 1752 FragSeq# = s; 1753 NextExpFrag = FragOffset+1; 1754 Reordering = False; 1755 } 1756 if (s>=NextExp AND MoreFrag==1 AND s==FragSeq#){ 1757 /* a fragment of the "current packet s" arrived */ 1758 if (FragOffset >= NextExpFrag){ 1759 NextExpFrag = FragOffset+1; 1760 Reordering = False; 1761 } 1762 else{ 1763 Reordering = True; /* fragment reordered */ 1764 } 1765 } 1766 if (s>=NextExp AND MoreFrag==1 AND s < FragSeq#){ 1767 /* case where a late fragment arrived, 1768 for illustration only, redundant with else below */ 1769 Reordering = True; 1770 } 1771 else { /* when s < NextExp, or MoreFrag==0 AND s < FragSeq# */ 1772 Reordering = True; 1773 } 1774 } 1776 A working version of the code would include a check to ensure that 1777 all fragments of a packet arrive before using the Reordered status 1778 further, such as in sample metrics. 1780 14.4 Discussion: Notes on Sample Metrics when evaluating Fragments 1782 All fragments with the same Source Sequence Number are assigned the 1783 same Source Time. 1785 Evaluation with byte stream numbering may be simplified if the 1786 fragment offset is simply added to the SourceByte of the first 1787 packet (with fragment offset = 0), keeping the 8 octet units of the 1788 offset in mind. 1790 15. Author's Addresses 1792 Al Morton 1793 AT&T Labs 1794 Room D3 - 3C06 1795 200 Laurel Ave. South 1796 Middletown, NJ 07748 USA 1797 Phone +1 732 420 1571 1798 EMail: 1800 Len Ciavattone 1801 AT&T Labs 1802 Room A2 - 4G06 1803 200 Laurel Ave. South 1804 Middletown, NJ 07748 USA 1805 Phone +1 732 420 1239 1806 EMail: 1808 Gomathi Ramachandran 1809 AT&T Labs 1810 Room C4 - 3D22 1811 200 Laurel Ave. South 1812 Middletown, NJ 07748 USA 1813 Phone +1 732 420 2353 1814 EMail: 1816 Stanislav Shalunov 1817 Internet2 1818 1000 Oakbrook DR STE 300 1819 Ann Arbor, MI 48104 1820 +1 734 995 7060 1821 EMail: 1823 Jerry Perser 1824 Consultant 1825 Calabasas, CA 91302 USA 1826 Phone: + 1 1827 EMail: 1829 Full Copyright Statement 1831 Copyright (C) The Internet Society (2005). 1833 This document is subject to the rights, licenses and restrictions 1834 contained in BCP 78, and except as set forth therein, the authors 1835 retain all their rights. 1837 This document and the information contained herein are provided on 1838 an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE 1839 REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE 1840 INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR 1841 IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 1842 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1843 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1845 Intellectual Property 1847 The IETF takes no position regarding the validity or scope of any 1848 Intellectual Property Rights or other rights that might be claimed 1849 to pertain to the implementation or use of the technology described 1850 in this document or the extent to which any license under such 1851 rights might or might not be available; nor does it represent that 1852 it has made any independent effort to identify any such rights. 1853 Information on the procedures with respect to rights in RFC 1854 documents can be found in BCP 78 and BCP 79. 1856 Copies of IPR disclosures made to the IETF Secretariat and any 1857 assurances of licenses to be made available, or the result of an 1858 attempt made to obtain a general license or permission for the use 1859 of such proprietary rights by implementers or users of this 1860 specification can be obtained from the IETF on-line IPR repository 1861 at http://www.ietf.org/ipr. 1863 The IETF invites any interested party to bring to its attention any 1864 copyrights, patents or patent applications, or other proprietary 1865 rights that may cover technology that may be required to implement 1866 this standard. Please address the information to the IETF at ietf- 1867 ipr@ietf.org. 1869 Acknowledgement 1871 Funding for the RFC Editor function is currently provided by the 1872 Internet Society.