idnits 2.17.1 draft-ietf-ippm-reordering-07.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.5 on line 1613. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1624. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1631. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1637. ** The document seems to lack an RFC 3978 Section 5.1 IPR Disclosure Acknowledgement -- however, there's a paragraph with a matching beginning. Boilerplate error? ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** The document seems to lack an RFC 3978 Section 5.4 Reference to BCP 78 -- however, there's a paragraph with a matching beginning. Boilerplate error? ** 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 1403 has weird spacing: '...tic int ring[...' == Line 1404 has weird spacing: '...tic int r = 0...' == Line 1405 has weird spacing: '... int l = ...' == Line 1406 has weird spacing: '... int j;...' == Line 1407 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 section? '1' on line 1154 looks like a reference -- Missing reference section? '2' on line 1317 looks like a reference -- Missing reference section? '3' on line 160 looks like a reference -- Missing reference section? '4' on line 167 looks like a reference -- Missing reference section? '5' on line 168 looks like a reference -- Missing reference section? '6' on line 168 looks like a reference -- Missing reference section? '7' on line 168 looks like a reference -- Missing reference section? '8' on line 168 looks like a reference -- Missing reference section? '9' on line 1167 looks like a reference -- Missing reference section? '10' on line 168 looks like a reference -- Missing reference section? 'L' on line 1041 looks like a reference -- Missing reference section? '11' on line 572 looks like a reference -- Missing reference section? '12' on line 888 looks like a reference -- Missing reference section? 'MAXN' on line 1403 looks like a reference Summary: 6 errors (**), 0 flaws (~~), 6 warnings (==), 21 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 disclosed, and any of which he or she becomes aware will 18 be disclosed, in accordance with RFC 3668. 20 Internet-Drafts are working documents of the Internet Engineering 21 Task Force (IETF), its areas, and its working groups. Note that 22 other groups may also distribute working documents as Internet- 23 Drafts. 25 Internet-Drafts are draft documents valid for a maximum of six 26 months and may be updated, replaced, or obsoleted by other documents 27 at any time. It is inappropriate to use Internet-Drafts as 28 reference material or to cite them other than as "work in progress." 30 The list of current Internet-Drafts can be accessed at 31 http://www.ietf.org/ietf/1id-abstracts.txt 33 The list of Internet-Draft Shadow Directories can be accessed at 34 http://www.ietf.org/shadow.html. 36 Copyright Notice 38 Copyright (C) The Internet Society (2004). 40 Abstract 42 This memo defines metrics to evaluate if a network has maintained 43 packet order on a packet-by-packet basis. It provides motivations 44 for the new metrics and discusses the measurement issues. The memo 45 first defines a reordered singleton, and then uses it as the basis 46 for sample metrics to quantify the extent of reordering in several 47 useful dimensions for network characterization or receiver design. 48 Additional metrics quantify the frequency of reordering and the 49 distance between separate occurrences. We then define a metric with 50 purely receiver analysis orientation. Several examples of evaluation 51 using the various sample metrics are included. An Appendix gives 52 extended definitions for evaluating order with packet fragmentation. 54 Contents 56 Status of this Memo................................................1 57 Copyright Notice...................................................1 58 Abstract...........................................................1 59 1. Conventions used in this document...............................3 60 2. Introduction....................................................3 61 2.1 Motivation.....................................................4 62 2.2 Goals and Objectives...........................................5 63 3. A Reordered Packet Singleton Metric.............................5 64 3.1 Metric Name:...................................................6 65 3.2 Metric Parameters:.............................................6 66 3.3 Definition:....................................................6 67 3.4 Sequence Discontinuity Definition..............................7 68 3.5 Evaluation in Time or Byte Order...............................8 69 3.6 Discussion.....................................................8 70 4. Sample Metrics..................................................8 71 4.1 Reordered Packet Ratio.........................................9 72 4.1.1 Metric Name:.................................................9 73 4.1.2 Metric Parameters:...........................................9 74 4.1.3 Definition:..................................................9 75 4.1.4 Discussion...................................................9 76 4.2 Reordering Extent..............................................9 77 4.2.1 Metric Name:................................................10 78 4.2.2 Parameter Notation:.........................................10 79 4.2.3 Definition:.................................................10 80 4.2.4 Discussion:.................................................10 81 4.3 Reordering Late Time Offset...................................11 82 4.3.1 Metric Name:................................................11 83 4.3.2 Metric Parameters:..........................................11 84 4.3.3 Definition:.................................................11 85 4.3.4 Discussion..................................................12 86 4.4 Reordering Byte Offset........................................12 87 4.4.1 Metric Name:................................................12 88 4.4.2 Metric Parameters:..........................................12 89 4.4.3 Definition:.................................................12 90 4.4.4 Discussion..................................................13 91 4.5 Gaps between multiple Reordering Discontinuities..............13 92 4.5.1 Metric Name:................................................13 93 4.5.2 Parameters:.................................................13 94 4.5.3 Definition of Reordering Discontinuity:.....................13 95 4.5.4 Definition of Reordering Gap:...............................13 96 4.5.5 Discussion..................................................14 97 4.6 Reordering-free Runs..........................................14 98 4.6.1 Metric Name:................................................14 99 4.6.2 Parameters:.................................................14 100 4.6.3 Definition:.................................................15 101 4.6.4 Discussion:.................................................15 102 5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric..16 103 5.1 Metric Name:..................................................16 104 5.2 Parameter Notation:...........................................16 105 5.3 Definitions...................................................16 106 5.4 Discussion:...................................................17 107 6. Measurement and Implementation Issues..........................18 108 7. Examples of Arrival Order Evaluation...........................20 109 7.1 Example with a single packet reordered........................20 110 7.2 Example with two packets reordered............................22 111 7.3 Example with three packets reordered..........................23 112 7.4 Example with Multiple Packet Reordering Discontinuities.......24 113 8. Security Considerations........................................24 114 8.1 Denial of Service Attacks.....................................24 115 8.2 User data confidentiality.....................................25 116 8.3 Interference with the metric..................................25 117 9. IANA Considerations............................................25 118 10. Normative References..........................................25 119 11. Informative References........................................25 120 12. Acknowledgments...............................................26 121 13. Appendix A Example Implementations in C (Informative).........27 122 14. Appendix B Fragment Order Evaluation (Informative)............29 123 14.1 Metric Name:.................................................29 124 14.2 Additional Metric Parameters:................................29 125 14.3 Definition:..................................................30 126 14.4 Discussion: Notes on Sample Metrics when evaluating Fragments31 127 15. Author's Addresses............................................31 128 Full Copyright Statement..........................................32 129 Intellectual Property.............................................32 130 Acknowledgement...................................................33 132 1. Conventions used in this document 134 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 135 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 136 document are to be interpreted as described in RFC 2119 [1]. 137 Although RFC 2119 was written with protocols in mind, the key words 138 are used in this document for similar reasons. They are used to 139 ensure the results of measurements from two different 140 implementations are comparable, and to note instances when an 141 implementation could perturb the network. 143 2. Introduction 145 Ordered delivery is a property of successful packet transfer 146 attempts, where the packet sequence ascends for each arriving packet 147 and there are no backward steps. 149 An explicit sequence number, such as an incrementing message number 150 or the packet sending time carried in each packet, establishes the 151 Source Sequence. 153 The detection of reordering at the Destination is based on packet 154 arrival order in comparison with a non-reversing reference value. 156 This metric is consistent with RFC 2330 [2], and classifies arriving 157 packets with sequence numbers smaller than their predecessors as 158 out-of-order, or reordered. For example, if sequentially numbered 159 packets arrive 1,2,4,5,3, then packet 3 is reordered. This is 160 equivalent to Paxon's reordering definition in [3], where "late" 161 packets were declared reordered. The alternative is to emphasize 162 "premature" packets instead (4 and 5 in the example), but only the 163 arrival of packet 3 distinguishes this circumstance from packet 164 loss. Focusing attention on late packets allows us to maintain 165 orthogonality with the packet loss metric. The metric's construction 166 is very similar to the sequence space validation for received 167 segments in RFC793 [4]. Earlier work to define ordered delivery 168 includes [5], [6], [7], [8], [9] and [10]. 170 2.1 Motivation 172 A reordering metric is relevant for most applications, especially 173 when assessing network support for Real-Time media streams. The 174 extent of reordering may be sufficient to cause a received packet to 175 be discarded by functions above the IP layer. 177 Packet order is not expected to change during transfer, but several 178 specific path characteristics can cause order to change. 180 Examples are: 181 * When two paths, one with slightly longer transfer time, support a 182 single packet stream or flow, then packets traversing the longer 183 path may arrive out-of-order. Multiple paths may be used to 184 achieve load balancing, or may arise from route instability. 185 * To increase capacity, a network device designed with multiple 186 processors serving a single port may reorder as a byproduct. 187 * A layer 2 retransmission protocol that compensates for an error- 188 prone link may cause packet reordering. 189 * If for any reason, the packets in a buffer are not serviced in the 190 order of their arrival, their order will change. 191 * If packets in a flow are assigned to multiple buffers (following 192 evaluation of traffic characteristics, for example), and the 193 buffers have different occupations and/or service rates, then 194 order will likely change. 196 When one or more of the above path characteristics are present 197 continuously, then reordering may be present on a steady-state 198 basis. The steady-state reordering condition typically causes an 199 appreciable fraction of packets to be reordered. This form of 200 reordering is most easily detected by minimizing the spacing between 201 test packets. Transient reordering may occur in response to network 202 instability; temporary routing loops can cause periods of extreme 203 reordering. This condition is characterized by long in-order streams 204 with occasional instances of reordering, sometimes with extreme 205 correlation. However, we do not expect packet delivery in a 206 completely random order, where for example, the last packet or the 207 first packet in a sample is equally likely to arrive at the 208 destination first. Thus we expect at least a minimal degree of order 209 in the packet arrivals, as exhibited in real networks. 211 The ability to restore order at the destination will likely have 212 finite limits. Practical hosts have receiver buffers with finite 213 size in terms of packets, bytes, or time (such as de-jitter 214 buffers). Once the initial determination of reordering is made, it 215 is useful to quantify the extent of reordering, or lateness, in all 216 meaningful dimensions. 218 2.2 Goals and Objectives 220 The definitions below intend to satisfy the goals of: 222 1. Determining whether or not packet reordering has occurred. 223 2. Quantifying the degree of reordering (achieving this second 224 goal requires assumptions of upper layer functions and 225 capabilities to restore order, and therefore several 226 solutions). 228 Reordering Metrics MUST: 230 + have one or more relevant applications, such as receiver design 231 or network characterization. 232 + be computable "on the fly" 233 + work with Poisson and Periodic test streams 234 + work even if the stream has duplicate or lost packets 236 It is desirable for Reordering Metrics to have one or more of the 237 following attributes: 239 + have concatenating results for segments measured separately 240 + have simplicity for easy consumption and understanding 241 + have relevance to TCP performance 242 + have relevance to Real-time application performance 244 The current set of metrics meet all the requirements above, and 245 provides all but the concatenation attribute (except in the case 246 where segments exhibit no reordering, and one may estimate that the 247 segment concatenation would also exhibit this desirable outcome). 248 However, satisfying these goals limits the set of metrics to those 249 that provide some clear insight into network characterization or 250 receiver design, and they are not likely to be exhaustive in their 251 coverage of the applications with respect to packet reordering 252 effects. Likewise, additional measurements may be possible. 254 3. A Reordered Packet Singleton Metric 256 The IPPM framework RFC 2330 [2] describes the notions of singletons, 257 samples, and statistics. For easy reference: 259 By a 'singleton' metric, we refer to metrics that are, 260 in a sense, atomic. For example, a single instance of "bulk 261 throughput capacity" from one host to another might be defined 262 as a singleton metric, even though the instance involves 263 measuring the timing of a number of Internet packets. 265 The evaluation of packet order requires several supporting concepts. 266 The first is a sequence number applied to packets at the source to 267 uniquely identify the order of packet transmission. The sequence 268 number may be established by a simple message number, a byte stream 269 number, or it may be the actual time when each packet departs from 270 the Source. 272 The second supporting concept is a stored value which is the "next 273 expected" packet number. Under normal conditions, the value of Next 274 Expected (NextExp) is the sequence number of the previous packet 275 plus 1 (for message numbering). 277 Each packet within a packet stream can be evaluated with this order 278 singleton metric. 280 3.1 Metric Name: 282 Type-P-Reordered 284 3.2 Metric Parameters: 286 + Src, the IP address of a host 288 + Dst, the IP address of a host 290 + SrcTime, the time of packet emission from the Source (or wire 291 time) 293 + s, the packet sequence number applied at the Source, in units of 294 messages. 296 + SrcByte, the packet sequence number applied at the Source, in 297 units of payload bytes. 299 + NextExp, the Next Expected Sequence number at the Destination, in 300 units of messages, time, or bytes. 302 + PayloadSize, the number of bytes contained in the information 303 field and referred to when the SrcByte sequence is based on byte 304 transfer. 306 3.3 Definition: 308 If a packet is found to be reordered by comparison with the Next 309 Expected value, its Type-P-Reordered = TRUE; otherwise Type-P- 310 Reordered = FALSE, as defined below: 312 The value of Type-P-Reordered is defined as TRUE if s < NextExp (the 313 packet is reordered). In this case, NextExp value does not change. 315 The value of Type-P-Reordered is defined as FALSE if s >= NextExp 316 (the packet is in-order). In this case, NextExp is set to s+1. 318 Since the Next Expected value cannot decrease, it provides a non- 319 reversing order criterion to identify reordered packets. 321 This definition can also be specified in pseudo-code. 323 On successful arrival of a packet with sequence number s: 324 if s >= NextExp then /* s is in-order */ 325 NextExp = s + 1; 326 Type-P-Reordered = False; 327 else /* when s < NextExp */ 328 Type-P-Reordered = True 330 3.4 Sequence Discontinuity Definition 332 Packets with s > NextExp are a special case of in-order delivery. 333 This condition indicates a sequence discontinuity, either because of 334 packet loss or reordering. Reordered packets must arrive for the 335 sequence discontinuity to be defined as a reordering discontinuity 336 (see section 4). 338 We define two different states for in-order packets. 340 When s = NextExp, the original sequence has been maintained, and 341 there is no discontinuity present. 343 When s > NextExp, some packets in the original sequence have not yet 344 arrived, and there is a sequence discontinuity associated with 345 packet s. The size of the discontinuity is s - NextExp, equal to 346 the number of packets presently missing, either reordered or lost. 348 In pseudo-code: 350 On successful arrival of a packet with sequence number s: 351 if s >= NextExp, then /* s is in-order */ 352 if s > NextExp then 353 SequenceDiscontinuty = True; 354 SeqDiscontinutySize = s - NextExp; 355 else 356 SequenceDiscontinuty = False; 357 NextExp = s + 1; 358 Type-P-Reordered = False; 360 else /* when s < NextExp */ 361 Type-P-Reordered = True; 362 SequenceDiscontinuty = False; 364 Discontinuities are easiest to detect with message numbering or 365 payload byte numbering where payload size is constant (and 366 retransmissions are distinguished), and may be possible with 367 Periodic Streams and Source Time numbering. 369 3.5 Evaluation in Time or Byte Order 371 For the alternate sequence dimensions, in-order packets have byte 372 stream numbers or Source times greater than or equal to the value of 373 NextExp. Each new in-order packet will increase the NextExp to 374 SrcTime plus 1 clock tick when using Source times, or to SrcByte 375 plus the payload size plus 1 for byte numbering. In the pseudo-code 376 of section 3.3, SrcByte (or SrcTime) replaces the sequence number s, 377 and we have: 379 if SrcByte >= NextExp then /* packet is in-order */ 380 NextExp = SrcByte + PayloadSize + 1; 381 Type-P-Reordered = False; 383 When using Source time, PayloadSize=0 (or a fixed time increment, if 384 using a reliable periodic packet source). 386 3.6 Discussion 388 Any arriving packet bearing a sequence number from the sequence that 389 establishes the Next Expected value can be evaluated to determine 390 whether it is in-order or reordered, based on a previous packet's 391 arrival. In the case where Next Expected is Undefined (because the 392 arriving packet is the first successful transfer), the packet is 393 designated in-order. 395 This metric assumes re-assembly of packet fragments before 396 evaluation. In principle, it is possible to use the Type-P-Reordered 397 metric to evaluate reordering among packet fragments, but each 398 fragment must contain source sequence information. 399 See the Appendix on fragment order evaluation for more detail. 401 If duplicate packets (multiple non-corrupt copies) arrive at the 402 destination, they MUST be noted and only the first to arrive is 403 considered for further analysis (copies would be declared reordered 404 according to the definition above). This requirement has the same 405 storage implications as earlier IPPM metrics, and follows the 406 precedent of RFC 2679. We provide a suggestion to minimize storage 407 size needed in the section on Measurement and Implementation Issues. 409 4. Sample Metrics 411 In this section, we define metrics applicable to a sample of packets 412 from a single Source sequence number system. When reordering occurs, 413 it is highly desirable to assert the degree to which a packet is 414 out-of-order, or reordered with respect other packets. This section 415 defines several metrics that quantify the extent of reordering in 416 various units of measure. Each metric highlights a relevant use. 418 The metrics in the sub-sections below have a network 419 characterization orientation, but also have relevance to receiver 420 design where reordering compensation is of interest. We begin with a 421 simple ratio metric indicating the reordered portion of the sample. 423 4.1 Reordered Packet Ratio 425 4.1.1 Metric Name: 427 Type-P-Reordered-Ratio-Stream 429 4.1.2 Metric Parameters: 431 The parameter set includes Type-P-Reordered singleton parameters, 432 the parameters unique to Poisson or Periodic Streams (as in RFC 2330 433 and RFC3432), plus the following: 435 + T0, a start time 437 + Tf, an end time 439 + dT, a waiting time for each packet to arrive 441 4.1.3 Definition: 443 For the packets arriving successfully between T0 and Tf+dT, the 444 ratio of reordered packets in the sample is 446 (Total of Reordered packets) / (Total packets received) 448 This fraction may be expressed as a percentage (multiply by 100%). 449 Note that in the case of duplicate packets, only the first copy is 450 used. 452 4.1.4 Discussion 454 When the Type-P-Reordered-Ratio-Stream is zero, no further 455 reordering metrics need be examined for that sample. Therefore, the 456 value of this metric is its simple ability to summarize the results 457 for a reordering-free sample. 459 4.2 Reordering Extent 461 This section defines the extent to which packets are reordered, and 462 associates a specific sequence discontinuity with each reordered 463 packet. 465 4.2.1 Metric Name: 467 Type-P-packet-Reordering-Extent-Stream 469 4.2.2 Parameter Notation: 471 Given a stream of packets sent from a source to a destination, let K 472 be the total number of packets in that stream. 474 Assign each packet a sequence number, a consecutive integer from 1 475 to K in the order of packet transmission (at the source). 477 Let L be the total number of packets received out of the K packets 478 sent. Recall that identical copies (duplicates) have been removed, 479 so L<=K. 481 Let s[1], s[2], ..., s[L], represent the original sequence numbers 482 associated with the packets in order of arrival. 484 Consider a reordered packet (as identified in section 3) with 485 arrival index i and source sequence number s[i]. There exists a set 486 of indexes j (1<=j s[i]. 488 4.2.3 Definition: 490 The reordering extent, e, of packet s[i] is defined to be 491 i-j for the smallest value of j when s[j] > s[i]. 493 Informally, the reordering extent is the maximum distance, in 494 packets, from a reordered packet to the earliest packet received 495 that has a larger sequence number. If a packet is in-order, its 496 reordering extent is undefined. The first packet to arrive is in- 497 order by definition, and has undefined reordering extent. 499 Comment on the definition of extent: For some arrival orders, the 500 assignment of a simple position/distance as the reordering extent 501 tends to overestimate the receiver storage needed to restore order. 502 A more accurate and complex procedure to calculate packet storage 503 would be to subtract any earlier reordered packets that the receiver 504 could pass on to the upper layers. With the bias understood, this 505 definition is deemed sufficient, especially for those who demand "on 506 the fly" calculations. 508 4.2.4 Discussion: 510 The packet with index j (s[j], identified in the Definition above) 511 is the reordering discontinuity associated with packet with index i 512 (s[i]). This definition is formalized below. 514 Note that the K packets in the stream could be some subset of a 515 larger stream, but L is still the total number of packets received 516 out of the K packets sent in that subset. 518 A receiver must possess storage to restore order to packets that are 519 reordered. For cases with single reordered packets, the extent e 520 gives the number of packets that must be held in the receiver's 521 buffer while waiting for the reordered packet to complete the 522 sequence. For more complex scenarios, the extent may be an 523 overestimate of required storage (see the Examples section). 525 Knowledge of the reordering extent e is particularly useful for 526 determining the portion of reordered packets that can or cannot be 527 restored to order in a typical receiver buffer based on their 528 arrival order alone (and without the aid of retransmission). 530 A sample's reordering extents may be expressed as a histogram, to 531 easily summarize the frequency of various extents. 533 4.3 Reordering Late Time Offset 535 Reordered packets can be assigned offset values indicating their 536 lateness in terms of buffer time that a receiver must possess to 537 accommodate them. Offset metrics are calculated only on reordered 538 packets, as identified by the reordered packet singleton metric in 539 Section 3. 541 4.3.1 Metric Name: 543 Type-P-packet-Late-Time-Stream 545 4.3.2 Metric Parameters: 547 In addition to the parameters defined for Type-P-Reordered, we 548 specify: 550 + DstTime, the time that each packet in the stream arrives at the 551 destination 553 4.3.3 Definition: 555 Lateness in time is calculated using destination times. When 556 received packet i is reordered, and has a reordering extent e, then: 558 LateTime(i) = DstTime(i)-DstTime(i-e) 560 Alternatively, using similar notation to that of section 4.2, an 561 equivalent definition is: 562 LateTime(i) = DstTime(i)-DstTime(j), for min{j|1<=js[i], or SrcTime[j]>SrcTime[i]. 565 4.3.4 Discussion 567 The offset metrics can help predict whether reordered packets will 568 be useful in a general receiver buffer system with finite limits. 569 The limit may be the time of storage prior to a cyclic play-out 570 instant (as with de-jitter buffers). 572 Note that the One-way IPDV [11] gives the delay variation for a 573 packet w.r.t. the preceding packet in the source sequence. Lateness 574 and IPDV give an indication of whether a buffer at the destination 575 has sufficient storage to accommodate the network's behavior and 576 restore order. When an earlier packet in the Source sequence is 577 lost, IPDV will necessarily be undefined for adjacent packets, and 578 Late Time may provide the only way to evaluate the usefulness of a 579 packet. 581 In the case of de-jitter buffers, there are circumstances where the 582 receiver employs loss concealment at the intended play-out time of a 583 late packet. However, if this packet arrives out of order, the Late 584 Time determines whether the packet is still useful. IPDV no longer 585 applies, because the receiver establishes a new play-out schedule 586 with additional buffer delay to accommodate similar events in the 587 future (this requires very minimal processing). 589 4.4 Reordering Byte Offset 591 Reordered packets can be assigned offset values indicating the 592 storage in bytes that a receiver must possess to accommodate them. 593 The various offset metrics are calculated only on reordered packets, 594 as identified by the reordered packet singleton metric in Section 3. 596 4.4.1 Metric Name: 598 Type-P-packet-Byte-Offset-Stream 600 4.4.2 Metric Parameters: 602 We use the same parameters defined earlier. 604 4.4.3 Definition: 606 Byte stream offset is the sum of the payload sizes of intervening 607 in-order packets between the reordered packet and the discontinuity 608 (including the packet at the discontinuity). 610 For reordered packet i with a reordering extent e: 611 ByteOffset(i) = Sum[in-order packets back to reordering discon.] 612 = Sum[PayloadSize(packet at i-1 if in-order), 613 PayloadSize(packet at i-2 if in-order), ... 614 PayloadSize(packet at i-e if in-order)] 616 4.4.4 Discussion 618 The byte offset metric can help predict whether reordered packets 619 will be useful in a general receiver buffer system with finite 620 limits. The limit is expressed as the number of bytes the buffer 621 can store. 623 When packets in the stream have variable sizes, it may be most 624 useful to characterize offset in terms of the payload size(s) of 625 stored packets, using the Type-P-packet-Byte-Offset-Stream metric 626 and byte stream numbering. 628 4.5 Gaps between multiple Reordering Discontinuities 630 4.5.1 Metric Name: 632 Type-P-packet-Reordering-Gap-Stream 634 4.5.2 Parameters: 636 No new parameters. 638 4.5.3 Definition of Reordering Discontinuity: 640 All reordered packets are associated with a packet at a reordering 641 discontinuity, defined as the in-order packet s[j] that arrived at 642 the minimum value of j (1<=j s[i]. 644 Note that s[j] will have been found to cause a sequence 645 discontinuity, where s > NextExp when evaluated with the reordered 646 singleton metric as described in section 3.4. 648 Recall that i - e = min(j). Subsequent reordered packets may be 649 associated with the same s[j], or with a different discontinuity. 650 This definition is used in the definition of the Reordering Gap, 651 below. 653 4.5.4 Definition of Reordering Gap: 655 A reordering gap is the distance between successive reordering 656 discontinuities. Type-P-packet-Reordering-Gap-Stream assigns a value 657 to (all) packets in a stream. 659 If: 661 The packet s[j'] is found to be a reordering discontinuity, based 662 on the arrival of reordered packet s[i'] with extent e', and 664 an earlier reordering discontinuity s[j], based on the arrival of 665 reordered packet s[i] with extent e was already detected, and 666 i' > i, and 668 there are no reordering discontinuities between j and j', 670 then the Reordering Gap for packet s[j'] is the difference between 671 the arrival positions the reordering discontinuities, as shown 672 below: 674 Gap(j') = (j') - (j) 676 Otherwise: 678 The Type-P-packet-Reordering-Gap-Stream for the packet is 0. 680 Gaps may also be expressed in time: 682 GapTime(j') = DstTime(j') - DstTime(j) 684 4.5.5 Discussion 686 When separate reordering discontinuities can be distinguished, then 687 a count may also be reported (along with the discontinuity 688 description, such as the number of reordered packets associated with 689 that discontinuity and their extents and offsets). The Gaps between 690 a sample's reordering discontinuities may be expressed as a 691 histogram, to easily summarize the frequency of various gaps. 692 Reporting the mode, average, range, etc. may also summarize the 693 distributions. 695 The Gap metric may help to correlate the frequency of reordering 696 discontinuities with their cause. Gap lengths are also informative 697 to receiver designers, revealing the period of reordering 698 discontinuities. The combination of reordering gaps and extent 699 reveals whether receivers will be required to handle cases of 700 overlapping reordered packets. 702 4.6 Reordering-free Runs 704 This section defines a metric based on a count of consecutive 705 packets between reordered packets. 707 4.6.1 Metric Name: 709 Type-P-packet-Reordering-Free-Run-Stream 711 4.6.2 Parameters: 713 r, the run counter 714 n, the number of runs 715 a, the accumulator of in-order packets 716 p, the number of packets 717 q, the squared sum of the run counters 719 4.6.3 Definition: 721 As packets in a sample arrive at the Destination, the count of 722 packets to the next reordered packet is a Reordering-Free run. Note 723 that the minimum run-length is one according to this definition. A 724 pseudo code example follows: 726 r = 0; /* r is the run counter */ 727 n = 0; /* n is the number of runs */ 728 a = 0; /* a is the accumulator of in order packets */ 729 p = 0; /* p is the number of packets */ 730 q = 0; /* q is the squared sum of the run counters */ 732 while(packets arrive with sequence number s) 733 { 734 p++; 735 if (s >= NextExp) /* s is in-order */ 736 then r++; 737 a++; 738 else /* s is reordered */ 739 q+= r*r; 740 r = 1; 741 n++; 742 } 744 Each in-order arrival increments the run counter and the accumulator 745 of in order packets, each reordered packet resets the run counter 746 after adding it to the accumulator. 748 Each arrival of a reordered packet yields a new count in the Run 749 vector. Long runs accompany periods where order was maintained, 750 while short runs indicate frequent, or multi-packet reordering. 752 The percent of packets in-order is 100*a/p 754 The average Reordering-Free run length is a/n 756 The q counter gives an indication of variation of the Reordering- 757 Free runs from the average by comparing q/a to a/n ((q/a)/(a/n)) 759 4.6.4 Discussion: 761 Type-P-packet-Reordering-Free-Run-Stream parameters give a brief 762 summary of the stream's reordering characteristics including the 763 average reordering-free run length, and the variation of run 764 lengths, therefore a key application of this metric is network 765 evaluation. 767 For example for 36 packets with 3 runs of 11 in-order packets we 768 have: 770 p = 36 771 n = 3 772 a = 33 773 q = 3 * (11*11) = 363 774 ave reordering-free run = 11 775 q/a = 11 776 (q/a)/ave = 1.0 778 For 36 packets with 3 runs, 2 of length 1 and one of length 31 779 p = 36 780 n = 3 781 a = 33 782 q = 1 + 1 + 961 = 963 783 ave reordering-free run = 11 784 q/a = 29.18 785 (q/a)/ave = 2.65 787 5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric 789 5.1 Metric Name: 791 Type-P-packet-n-Reordering-Stream 793 5.2 Parameter Notation: 795 Let n be a positive integer (a parameter). Let k be a positive 796 integer equal to the number of packets sent (sample size). Let l be 797 a non-negative integer representing the number of packets that were 798 received out of the k packets sent. (Note that there is no 799 relationship between k and l: on one hand, losses can make l less 800 than k; on the other hand, duplicates can make l greater than k.) 801 Assign each sent packet a sequence number, 1 to k, in order of 802 packet emission. 804 Let s[1], s[2], ..., s[l] be the original sequence numbers of the 805 received packets, in the order of arrival. 807 5.3 Definitions 809 Definition 1: Received packet number i (n < i <= l), with source 810 sequence number s[i], is n-reordered if and only if for all j such 811 that i-n <= j < i, s[j] > s[i]. 813 Claim: If by this definition, a packet's reordering is n and 0 < n' 814 < n, then the packet is also reordered to the n' extent. 816 Note: This definition is illustrated by C code in Appendix A. It 817 determines the n-reordering for a value of n=3 (when actually 818 writing applications that would report the metric, one would 819 probably report it for several values of n, such as 1, 2, 3, 4 -- 820 and maybe a few more consecutive values). 822 This definition does not assign an n to all reordered packets as 823 defined by the singleton metric, in particular when blocks of 824 successive packets are reordered. (In the arrival sequence 825 s={1,2,3,7,8,9,4,5,6}, packets 4, 5, and 6 are reordered, but only 826 packet 4 is n-reordered, with n=3.) 828 Definition 2: The degree of n-reordering of the sample is m/l, where 829 m is the number of n-reordered packets in the sample. 831 Definition 3: The degree of "monotonic reordering" of the sample is 832 its degree of 1-reordering. 834 Definition 4: A sample is said to have no reordering if its degree 835 of n-reordering is 0. 837 5.4 Discussion: 839 The degree of n-reordering may be expressed as a percentage, in 840 which case the number from Definition 2 is multiplied by 100%. 842 Knowledge of n-reordering is particularly useful for determining the 843 portion of reordered packets that can or cannot be restored to order 844 in a typical TCP receiver buffer based on their arrival order alone 845 (and without the aid of retransmission). 847 Important special cases are n=1 and n=3: 849 - For n=1, absence of 1-reordering means the sequence numbers that 850 the receiver sees are monotonically increasing with respect to the 851 previous arriving packet. 853 - For n=3, a NewReno TCP sender would retransmit 1 packet in 854 response to an instance of 3-reordering and therefore consider this 855 packet lost for the purposes of congestion control (the sender will 856 half its congestion window). Detecting instances of 3-reordering is 857 useful for determining the portion of reordered packets that are in 858 fact as good as lost. 860 A sample's n-reordering may be expressed as a histogram, to 861 summarize the frequency for each value of n. 863 We note that the definition of n-reordering cannot predict the exact 864 number of packets unnecessarily retransmitted by a TCP sender under 865 some circumstances, such as cases with closely-spaced reordered 866 singletons. The definition is less complicated than a TCP 867 implementation where both time and position influence the sender's 868 behavior. 870 A packet's n-reordering is sometimes equal to its reordering extent, 871 e. n-reordering is different in the following ways: 873 1. n is a count of early packets with consecutive arrival positions 874 at the receiver. 876 2. Reordered packets may not be n-reordered, but will have an 877 extent, e (see the examples). 879 6. Measurement and Implementation Issues 881 The results of tests will be dependent on the time interval between 882 measurement packets (both at the Source, and during transport where 883 spacing may change). Clearly, packets launched infrequently (e.g., 884 1 per 10 seconds) are unlikely to be reordered. 886 Test stream designers may prefer to use a periodic sending interval 887 so that a known temporal bias is maintained, also bringing 888 simplified results analysis (as described in RFC 3432 [12]). In this 889 case, the periodic sending interval should be chosen to reproduce 890 the closest Source packet spacing expected (down to the link speed 891 serialization time limit). Use of the closest possible spacing 892 should reveal the greatest extent of steady-state reordering on the 893 path. Of course, packet spacing is likely to vary as the stream 894 traverses the test path. 896 Packet lengths might also be varied to attempt to detect instances 897 of parallel processing (they may cause steady state reordering). For 898 example, a line-speed burst of the longest (MTU-length) packets 899 followed by a burst of the shortest possible packets may be an 900 effective detecting pattern. Other size patterns are possible. 902 The non-reversing order criterion and all metrics described above 903 remain valid and useful when a stream of packets experiences packet 904 loss, or both loss and reordering. In other words, losses alone do 905 not cause subsequent packets to be declared reordered. 907 Assuming that the necessary sequence information (sequence number 908 and/or source time stamp) is included in the packet payload 909 (possibly in application headers such as RTP), packet sequence may 910 be evaluated in a passive measurement arrangement. Also, it is 911 possible to evaluate sequence at a single point along a path, since 912 the usual need for synchronized Src and Dst Clocks may be relaxed to 913 some extent. 915 When the Src sequence is based on byte stream, or payload numbering, 916 care must be taken to avoid declaring retransmitted packets 917 reordered. The additional reference of Src Time is one way to avoid 918 this ambiguity. 920 Since this metric definition may use sequence numbers with finite 921 range, it is possible that the sequence numbers could reach end-of- 922 range and roll over to zero during a measurement. By definition, 923 the Next Expected value cannot decrease, and all packets received 924 after a roll-over would be declared reordered. Sequence number 925 roll-over can be avoided by using combinations of counter size and 926 test duration where roll-over is impossible (and sequence is reset 927 to zero at the start). Also, message-based numbering results in 928 slower sequence consumption. There may still be cases where 929 methodological mitigation of this problem is desirable (e.g., long- 930 term testing). The elements of mitigation are: 932 1. There must be a test to detect if a roll-over has occurred. It 933 would be nearly impossible for the sequence numbers of successive 934 packets to jump by more than half the total range, so these large 935 discontinuities are designated as roll-over. 937 2. All sequence numbers used in computations are represented in a 938 sufficiently large precision. The numbers have a correction applied 939 (equivalent to adding a significant digit) whenever roll-over is 940 detected. 942 3. Reordered packets coincident with sequence numbers reaching end- 943 of-range must also be detected for proper application of correction 944 factor. 946 Ideally, the test instrument would have the ability to use all 947 earlier packets at any point in the test stream. In practice, there 948 will be limited ability to determine reordering extent, due to the 949 storage requirements for previous packets. Saving only packets that 950 indicate discontinuities (and their arrival positions) will reduce 951 storage volume. 953 Another solution is to use a sliding history window of packets, 954 where the window size would be determined by an upper bound on the 955 useful reordering extent. This bound could be several packets or 956 several seconds-worth of packets, depending on the intended 957 analysis. When discarding all stream information beyond the window, 958 the reordering extent or degree of n-reordering may need to be 959 expressed as greater than the window length if the reordering 960 discontinuity information has been discarded, and Gap calculations 961 would not be possible. 963 The requirement to ignore duplicate packets also mandates storage. 964 Here, tracking the sequence numbers of missing packets may minimize 965 storage size. Missing packets may eventually be declared lost, or 966 reordered if they arrive. The missing packet list and the largest 967 sequence number received thus far (NextExp - 1) are sufficient 968 information to determine if a packet is a duplicate (assuming a 969 manageable storage size for packets that are missing due to loss). 971 Some in-order packet arrivals may not be useful to TCP receivers, 972 due to the receiver window. Sequence Discontinuities and their size 973 are defined in section 3.4, and this information may be useful to 974 determine whether a packet is useful or not. 976 When in-order packet s arrives and represents a Sequence 977 Discontinuity, 978 If 979 SeqDiscontinutySize >= (number of packets needed to exceed TCP 980 Receive window) 981 then s will not be acknowledged until the TCP window fills and 982 slides over. If s is sufficiently beyond the window and the path is 983 congested such that intermediate packets never arrive, s will be 984 discarded and the TCP connection may drop. 986 Last, we note that determining reordering extents and gaps is tricky 987 when there are overlapped or nested events. Test instrument 988 complexity and reordering complexity are directly correlated. 990 7. Examples of Arrival Order Evaluation 992 This section provides some examples to illustrate how the non- 993 reversing order criterion works, how n-reordering works in 994 comparison, and the value of viewing reordering in all the 995 dimensions of time, bytes, and position. 997 Throughout this section, we will refer to packets by their source 998 sequence number, except where noted. So "Packet 4" refers to the 999 packet with source sequence number 4, and the reader should refer to 1000 the tables in each example to determine packet 4's arrival index 1001 number, if needed. 1003 7.1 Example with a single packet reordered 1005 Table 1 gives a simple case of reordering, where one packet is 1006 reordered, Packet 4. Packets are listed according to their arrival, 1007 and message numbering is used. 1009 Table 1 Example with Packet 4 Reordered, 1010 Sending order(SrcNum@Src): 1,2,3,4,5,6,7,8,9,10 1011 s Src Dst Dst Byte Late 1012 @Dst NextExp Time Time Delay IPDV Order Offset Time 1013 1 1 0 68 68 1 1014 2 2 20 88 68 0 2 1015 3 3 40 108 68 0 3 1016 5 4 80 148 68 -82 4 1017 6 6 100 168 68 0 5 1018 7 7 120 188 68 0 6 1019 8 8 140 208 68 0 7 1020 4 9 60 210 150 82 8 400 62 1021 9 9 160 228 68 0 9 1022 10 10 180 248 68 0 10 1024 Each column gives the following information: 1026 s Packet sequence number at the Source. 1027 NextExp The value of NextExp when the packet arrived(before 1028 update). 1029 SrcTime Packet time stamp at the Source, ms. 1030 DstTime Packet time stamp at the Destination, ms. 1031 Delay 1-way delay of the packet, ms. 1032 IPDV IP Packet Delay Variation, ms 1033 IPDV = Delay(SrcNum)-Delay(SrcNum-1) 1034 DstOrder Order in which the packet arrived at the Destination. 1035 Byte Offset The Byte Offset of a reordered packet, in bytes. 1036 LateTime The lateness of a reordered packet, in ms. 1038 We can see that when Packet 4 arrives, NextExp=9, and it is declared 1039 reordered. We compute the extent of reordering as follows: 1041 Using the notation , the received 1042 packets are represented as: 1044 \/ 1045 s = 1, 2, 3, 5, 6, 7, 8, 4, 9, 10 1046 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 1047 /\ 1048 when j=7, 8 > 4, so the reordering extent is 1 or more. 1049 when j=6, 7 > 4, so the reordering extent is 2 or more. 1050 when j=5, 6 > 4, so the reordering extent is 3 or more. 1051 when j=4, 5 > 4, so the reordering extent is 4 or more. 1052 when j=3, but 3 < 4, and 4 is the maximum extent, e=4 (assuming 1053 there are no earlier sequence discontinuities, as in this example). 1055 Further, we can compute the Late Time (210-148=62ms using DstTime) 1056 compared to Packet 5's arrival. If the receiver has a de-jitter 1057 buffer that holds more than 4 packets, or at least 62 ms storage, 1058 Packet 4 may be useful. Note that 1-way delay and IPDV also indicate 1059 unusual behavior for Packet 4. Also, if Packet 4 had arrived at 1060 least 62ms earlier, it would have been in-order in this example. 1062 If all packets contained 100 byte payloads, then Byte Offset is 1063 equal to 400 bytes. 1065 Following the definitions of section 5.1, Packet 4 is defined to be 1066 4-reordered. 1068 7.2 Example with two packets reordered 1070 Table 2 Example with Packets 5 and 6 Reordered, 1071 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10 1072 s Src Dst Dst Byte Late 1073 @Dst NextExp Time Time Delay IPDV Order Offset Time 1074 1 1 0 68 68 1 1075 2 2 20 88 68 0 2 1076 3 3 40 108 68 0 3 1077 4 4 60 128 68 0 4 1078 7 5 120 188 68 -22 5 1079 5 8 80 189 109 41 6 100 1 1080 6 8 100 190 90 -19 7 100 2 1081 8 8 140 208 68 0 8 1082 9 9 160 228 68 0 9 1083 10 10 180 248 68 0 10 1085 Table 2 shows a case where Packets 5 and 6 arrive just behind Packet 1086 7, so both 5 and 6 are reordered. The Late times (189-188=1, 190- 1087 188=2) are small. 1089 Using the notation , the received 1090 packets are represented as: 1092 \/ \/ 1093 s = 1, 2, 3, 4, 7, 5, 6, 8, 9, 10 1094 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 1095 /\ /\ 1097 Considering Packet 5 first: 1098 when j=5, 7 > 5, so the reordering extent is 1 or more. 1099 when j=4, but 4 < 5, so 1 is its maximum extent, and e=1. 1101 Considering Packet 6 next: 1102 when j=6, 5 < 6, the extent is not yet defined. 1103 when j=5, 7 > 6, so the reordering extent is i-j=2 or more. 1104 when j=4, 4 < 6, and we find 2 is its maximum extent, and e=2. 1106 We can also associate each of these reordered packets with a 1107 reordering discontinuity. We find the minimum j=5 (for both packets) 1108 according to Section 4.2.3. So Packet 6 is associated with the same 1109 reordering discontinuity as Packet 5, at Packet 7. 1111 This is a case where reordering extent e would over-estimate the 1112 packet storage required to restore order. Only one packet storage is 1113 required (to hold Packet 7), but e=2 for Packet 6. 1115 Following the definitions of section 5, Packet 5 is defined to be 1- 1116 reordered, but Packet 6 is not qualified n-reordered. 1118 A hypothetical sender/receiver pair may retransmit Packet 5 1119 unnecessarily, since it is 1-reordered (in agreement with the 1120 singleton metric). Though Packet 6 may not be unnecessarily 1121 retransmitted, the receiver cannot advance Packet 7 to the higher 1122 layers until after Packet 6 arrives. Therefore, the singleton metric 1123 correctly determined that Packet 6 is reordered. 1125 7.3 Example with three packets reordered 1127 Table 3 Example with Packets 4, 5, and 6 reordered 1128 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11 1129 s Src Dst Dst Byte Late 1130 @Dst NextExp Time Time Delay IPDV Order Offset Time 1131 1 1 0 68 68 1 1132 2 2 20 88 68 0 2 1133 3 3 40 108 68 0 3 1134 7 4 120 188 68 -88 4 1135 8 8 140 208 68 0 5 1136 9 9 160 228 68 0 6 1137 10 10 180 248 68 0 7 1138 4 11 60 250 190 122 8 400 62 1139 5 11 80 252 172 -18 9 400 64 1140 6 11 100 256 156 -16 10 400 68 1141 11 11 200 268 68 0 11 1143 The case in Table 3 is where three packets in sequence have long 1144 transit times (Packets with s = 4,5,and 6). Delay, Late time, and 1145 Byte Offset capture this very well, and indicate variation in 1146 reordering extent, while IPDV indicates that the spacing between 1147 packets 4,5,and 6 has changed. 1149 The histogram of Reordering extents (e) would be: 1151 Bin 1 2 3 4 5 6 7 1152 Frequency 0 0 0 1 1 1 0 1154 Using the notation , the received 1155 packets are represented as: 1157 s = 1, 2, 3, 7, 8, 9,10, 4, 5, 6, 11 1158 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11 1160 We first calculate the n-reordering. Considering Packet 4 first: 1161 when n=1, 7<=j<8, and 10> 4, so the packet is 1-reordered. 1162 when n=2, 6<=j<8, and 9 > 4, so the packet is 2-reordered. 1163 when n=3, 5<=j<8, and 8 > 4, so the packet is 3-reordered. 1164 when n=4, 4<=j<8, and 7 > 4, so the packet is 4-reordered. 1165 when n=5, 3<=j<8, but 3 < 4, and 4 is the maximum n-reordering. 1167 Considering packet 5[9] next: 1169 when n=1, 8<=j<9, but 4 < 5, so the packet at i=9 is not qualified 1170 as n-reordered. We find the same to for Packet 6. 1172 We now consider whether reordered Packets 5 and 6 are associated 1173 with the same reordering discontinuity as Packet 4. Using the test 1174 of Section 4.2.3, we find that the minimum j=4 for all three 1175 packets. They are all associated with the reordering discontinuity 1176 at Packet 7. 1178 This example shows again that the n-reordering definition identifies 1179 a single Packet (4) with a sufficient degree of reordering to result 1180 in one unnecessary packet retransmission by the New Reno TCP sender. 1181 Also, the reordered arrival of Packets 5 and 6 will allow the 1182 receiver process to pass Packets 7 through 10 up the protocol stack 1183 (the singleton metric indicates 5 and 6 are reordered, and they are 1184 all associated with a single reordering discontinuity). 1186 7.4 Example with Multiple Packet Reordering Discontinuities 1188 Table 4 Example with Multiple Packet Reordering Discontinuities 1189 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 1191 Discontinuity Discontinuity 1192 |---------Gap---------| 1193 s = 1, 2, 3, 6, 7, 4, 5, 8, 9, 10, 12, 13, 11, 14, 15, 16 1194 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 1196 r = 1, 2, 3, 4, 5, 1, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, ... 1197 n = 1 2 3 1198 end r counts = 5 1 6 1200 Packet 4 has extent e=2, Packet 5 has extent e=3, and Packet 11 has 1201 e=2. There are two different reordering discontinuities, one at 1202 Packet 6 (where j=4) and one at Packet 12 (where j'=11). 1204 According to the definition of Reordering Gap 1205 Gap(j') = (j') - (j) 1206 Gap(11) = (11) - (4) = 7 1208 We also have three reordering-free runs of lengths 5, 1, and 6. 1210 The differences between these two multiple-event metrics are evident 1211 here. Gaps are the distance between sequence discontinuities that 1212 are subsequently defined as reordering discontinuities, while 1213 reordering-free runs capture the distance between reordered packets. 1215 8. Security Considerations 1217 8.1 Denial of Service Attacks 1218 This metric requires a stream of packets sent from one host (source) 1219 to another host (destination) through intervening networks. This 1220 method could be abused for denial of service attacks directed at 1221 destination and/or the intervening network(s). 1223 Administrators of source, destination, and the intervening 1224 network(s) should establish bilateral or multi-lateral agreements 1225 regarding the timing, size, and frequency of collection of sample 1226 metrics. Use of this method in excess of the terms agreed between 1227 the participants may be cause for immediate rejection or discard of 1228 packets or other escalation procedures defined between the affected 1229 parties. 1231 8.2 User data confidentiality 1233 Active use of this method generates packets for a sample, rather 1234 than taking samples based on user data, and does not threaten user 1235 data confidentiality. Passive measurement must restrict attention to 1236 the headers of interest. Since user payloads may be temporarily 1237 stored for length analysis, suitable precautions MUST be taken to 1238 keep this information safe and confidential. 1240 8.3 Interference with the metric 1242 It may be possible to identify that a certain packet or stream of 1243 packets is part of a sample. With that knowledge at the destination 1244 and/or the intervening networks, it is possible to change the 1245 processing of the packets (e.g. increasing or decreasing delay) that 1246 may distort the measured performance. It may also be possible to 1247 generate additional packets that appear to be part of the sample 1248 metric. These additional packets are likely to perturb the results 1249 of the sample measurement. 1251 To discourage the kind of interference mentioned above, packet 1252 interference checks, such as cryptographic hash, may be used. 1254 9. IANA Considerations 1256 Since this metric does not define a protocol or well-known values, 1257 there are no IANA considerations in this memo. 1259 10. Normative References 1261 1 Bradner, S., "Key words for use in RFCs to Indicate Requirement 1262 Levels", RFC 2119, March 1997. 1264 2 Paxson, V., Almes, G., Mahdavi, J., and Mathis, M., "Framework 1265 for IP Performance Metrics", RFC 2330, May 1998. 1267 11. Informative References 1268 3 V.Paxson, "Measurements and Analysis of End-to-End Internet 1269 Dynamics," Ph.D. dissertation, U.C. Berkeley, 1997, 1270 ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz. 1272 4 Postel, J., "Transmission Control Protocol", STD 7, RFC 793, 1273 September 1981. 1274 Obtain via: http://www.rfc-editor.org/rfc/rfc793.txt 1276 5 L.Ciavattone and A.Morton, "Out-of-Sequence Packet Parameter 1277 Definition (for Y.1540)", Contribution number T1A1.3/2000-047, 1278 October 30, 2000. ftp://ftp.t1.org/pub/t1a1/2000-A13/0a130470.doc 1280 6 J.C.R.Bennett, C.Partridge, and N.Shectman, "Packet Reordering is 1281 Not Pathological Network Behavior," IEEE/ACM Transactions on 1282 Networking, vol.7, no.6, pp.789-798, December 1999. 1284 7 D.Loguinov and H.Radha, "Measurement Study of Low-bitrate 1285 Internet Video Streaming", Proceedings of the ACM SIGCOMM 1286 Internet Measurement Workshop 2001 November 1-2, 2001, San 1287 Francisco, USA. 1289 8 J.Bellardo and S.Savage, "Measuring Packet Reordering," 1290 Proceedings of the ACM SIGCOMM Internet Measurement Workshop 1291 2002, November 6-8, Marseille, France. 1293 9 S.Jaiswal et al., "Measurement and Classification of Out-of- 1294 Sequence Packets in a Tier-1 IP Backbone," Proceedings of the ACM 1295 SIGCOMM Internet Measurement Workshop 2002, November 6-8, 1296 Marseille, France. 1298 10 L.Ciavattone, A.Morton, and G.Ramachandran, "Standardized Active 1299 Measurements on a Tier 1 IP Backbone," IEEE Communications Mag., 1300 pp 90-97, June 2003. 1302 11 Demichelis, C., and Chimento, P., "IP Packet Delay Variation 1303 Metric for IP Performance Metrics (IPPM)", RFC 3393, November 1304 2002. 1306 12 Raisanen, V., Grotefeld, G., and Morton, A., "Network performance 1307 measurement with periodic streams", RFC 3432, November 2002. 1309 12. Acknowledgments 1311 The authors would like to acknowledge many helpful discussions with 1312 Matt Zekauskas, Jon Bennett (who authored the sections on 1313 Reordering-Free Runs), and Matt Mathis. We thank David Newman and 1314 Henk Uijterwall for their reviews and suggestions, and Michal 1315 Przybylski for sharing implementation experiences with us on the 1316 ippm-list. We gratefully acknowledge the foundation laid by the 1317 authors of the IP performance Framework [2]. 1319 13. Appendix A Example Implementations in C (Informative) 1321 Two example c-code implementations of reordering definitions follow: 1323 Example 1 n-reordering ============================================ 1325 #include 1327 #define MAXN 100 1329 #define min(a, b) ((a) < (b)? (a): (b)) 1330 #define loop(x) ((x) >= 0? x: x + MAXN) 1332 /* 1333 * Read new sequence number and return it. Return a sentinel value 1334 * of EOF (at least once) when there are no more sequence numbers. 1335 * In this example, the sequence numbers come from stdin; 1336 * in an actual test, they would come from the network. 1337 * 1338 */ 1339 int 1340 read_sequence_number() 1341 { 1342 int res, rc; 1343 rc = scanf("%d\n", &res); 1344 if (rc == 1) return res; 1345 else return EOF; 1346 } 1348 int 1349 main() 1350 { 1351 int m[MAXN]; /* We have m[j-1] == number of 1352 * j-reordered packets. */ 1353 int ring[MAXN]; /* Last sequence numbers seen. */ 1354 int r = 0; /* Ring pointer for next write. */ 1355 int l = 0; /* Number of sequence numbers read. */ 1356 int s; /* Last sequence number read. */ 1357 int j; 1359 for (j = 0; j < MAXN; j++) m[j] = 0; 1360 for (;(s = read_sequence_number())!= EOF;l++,r=(r+1)%MAXN) { 1361 for (j=0; j 1376 #define MAXN 100 1377 #define min(a, b) ((a) < (b)? (a): (b)) 1378 #define loop(x) ((x) >= 0? x: x + MAXN) 1380 /* Global counters */ 1381 int receive_packets=0; /* number of recieved */ 1382 int reorder_packets=0; /* number of reordered packets */ 1384 /* function to test if current packet has been reordered 1385 * returns 0 = not reordered 1386 * 1 = reordered 1387 */ 1388 int testorder1(int seqnum) // Al 1389 { 1390 static int NextExp = 1; 1391 int iReturn = 0; 1393 if (seqnum >= NextExp) { 1394 NextExp = seqnum+1; 1395 } else { 1396 iReturn = 1; 1397 } 1398 return iReturn; 1399 } 1401 int testorder2(int seqnum) // Stanislav 1402 { 1403 static int ring[MAXN]; /* Last sequence numbers seen. */ 1404 static int r = 0; /* Ring pointer for next write */ 1405 int l = 0; /* Number of sequence numbers read. */ 1406 int j; 1407 int iReturn = 0; 1409 l++; 1410 r = (r+1) % MAXN; 1411 for (j=0; j= NextExp, 1487 * AND the fragment offset FragOffset >= NextExpFrag 1489 However, it more efficient to define reordered conditions exactly, 1490 and designate Type-P-Reordered as False otherwise. 1492 The value of Type-P-Reordered is defined as True (the packet is 1493 reordered) under the conditions below. In these cases, the NextExp 1494 value does not change. 1496 Case 1: if s < NextExp 1498 Case 2: if s < FragSeq# 1500 Case 3: if s>= NextExp AND s = FragSeq# AND FragOffset < NextExpFrag 1502 This definition can also be illustrated in pseudo-code. A draft 1503 version of the code follows, and some simplification may be 1504 possible. A challenging aspect surrounds the housekeeping for the 1505 new parameters. 1507 NextExp=0; 1508 NextExpFrag=0; 1509 FragSeq#=0; 1511 while(packets arrive with s, MoreFrag, FragOffset) 1512 { 1513 if (s>=NextExp AND MoreFrag==0 AND s>=FragSeq#){ 1514 /* a normal packet or last frag of an in-order packet arrived 1515 */ 1516 NextExp = s+1; 1517 FragSeq# = 0; 1518 NextExpFrag = 0; 1519 Reordering = False; 1520 } 1521 if (s>=NextExp AND MoreFrag==1 AND s>FragSeq#>=0){ 1522 /* a fragment of a new packet arrived, possibly with a 1523 higher sequence number than the current fragmented packet */ 1524 FragSeq# = s; 1525 NextExpFrag = FragOffset+1; 1526 Reordering = False; 1527 } 1528 if (s>=NextExp AND MoreFrag==1 AND s==FragSeq#){ 1529 /* a fragment of the "current packet s" arrived */ 1530 if (FragOffset >= NextExpFrag){ 1531 NextExpFrag = FragOffset+1; 1532 Reordering = False; 1533 } 1534 else{ 1535 Reordering = True; /* fragment reordered */ 1536 } 1537 } 1538 if (s>=NextExp AND MoreFrag==1 AND s < FragSeq#){ 1539 /* case where a late fragment arrived, 1540 for illustration only, redundant with else below*/ 1541 Reordering = True; 1542 } 1543 else { /* when s < NextExp, or MoreFrag==0 AND s < FragSeq# */ 1544 Reordering = True; 1545 } 1546 } 1548 A working version of the code would include a check to ensure that 1549 all fragments of a packet arrive before using the Reordered status 1550 further, such as in sample metrics. 1552 14.4 Discussion: Notes on Sample Metrics when evaluating Fragments 1554 All fragments with the same Source Sequence Number are assigned the 1555 same Source Time. 1557 Evaluation with byte stream numbering may be simplified if the 1558 fragment offset is simply added to the SourceByte of the first 1559 packet (with fragment offset = 0), keeping the 8 octet units of the 1560 offset in mind. 1562 15. Author's Addresses 1564 Al Morton 1565 AT&T Labs 1566 Room D3 - 3C06 1567 200 Laurel Ave. South 1568 Middletown, NJ 07748 USA 1569 Phone +1 732 420 1571 1570 EMail: 1572 Len Ciavattone 1573 AT&T Labs 1574 Room C4 - 2B29 1575 200 Laurel Ave. South 1576 Middletown, NJ 07748 USA 1577 Phone +1 732 420 1239 1578 EMail: 1580 Gomathi Ramachandran 1581 AT&T Labs 1582 Room C4 - 3D22 1583 200 Laurel Ave. South 1584 Middletown, NJ 07748 USA 1585 Phone +1 732 420 2353 1586 EMail: 1588 Stanislav Shalunov 1589 Internet2 1590 200 Business Park Drive, Suite 307 1591 Armonk, NY 10504 1592 Phone: + 1 914 765 1182 1593 EMail: 1595 Jerry Perser 1596 Consultant 1597 Calabasas, CA 91302 USA 1598 Phone: + 1 1599 EMail: 1601 Full Copyright Statement 1603 Copyright (C) The Internet Society (2004). This document is subject 1604 to the rights, licenses and restrictions contained in BCP 78 and 1605 except as set forth therein, the authors retain all their rights. 1607 This document and the information contained herein are provided on 1608 an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE 1609 REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE 1610 INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR 1611 IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 1612 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1613 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1615 Intellectual Property 1617 The IETF takes no position regarding the validity or scope of any 1618 Intellectual Property Rights or other rights that might be claimed 1619 to pertain to the implementation or use of the technology described 1620 in this document or the extent to which any license under such 1621 rights might or might not be available; nor does it represent that 1622 it has made any independent effort to identify any such rights. 1623 Information on the procedures with respect to rights in RFC 1624 documents can be found in BCP 78 and BCP 79. 1626 Copies of IPR disclosures made to the IETF Secretariat and any 1627 assurances of licenses to be made available, or the result of an 1628 attempt made to obtain a general license or permission for the use 1629 of such proprietary rights by implementers or users of this 1630 specification can be obtained from the IETF on-line IPR repository 1631 at http://www.ietf.org/ipr. 1633 The IETF invites any interested party to bring to its attention any 1634 copyrights, patents or patent applications, or other proprietary 1635 rights that may cover technology that may be required to implement 1636 this standard. Please address the information to the IETF at ietf- 1637 ipr@ietf.org. 1639 Acknowledgement 1641 Funding for the RFC Editor function is currently provided by the 1642 Internet Society.