idnits 2.17.1 draft-ietf-ippm-reordering-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by 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. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document is more than 15 pages and seems to lack a Table of Contents. == The page length should not exceed 58 lines per page, but there was 25 longer pages, the longest (page 10) being 77 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 25 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 1196 has weird spacing: '...tic int r = ...' -- 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 930 looks like a reference -- Missing reference section? '2' on line 617 looks like a reference -- Missing reference section? '3' on line 1092 looks like a reference -- Missing reference section? '4' on line 76 looks like a reference -- Missing reference section? '5' on line 83 looks like a reference -- Missing reference section? '6' on line 84 looks like a reference -- Missing reference section? '7' on line 84 looks like a reference -- Missing reference section? '8' on line 84 looks like a reference -- Missing reference section? '9' on line 943 looks like a reference -- Missing reference section? '10' on line 84 looks like a reference -- Missing reference section? 'L' on line 820 looks like a reference -- Missing reference section? '11' on line 460 looks like a reference -- Missing reference section? '12' on line 703 looks like a reference Summary: 5 errors (**), 0 flaws (~~), 3 warnings (==), 16 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 Spirent 11 Packet Reordering Metric for IPPM 13 Status of this Memo 15 This document is an Internet-Draft and is in full conformance with 16 all provisions of Section 10 of RFC2026 [1]. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet- 21 Drafts. Internet-Drafts are draft documents valid for a maximum of 22 six months and may be updated, replaced, or made obsolete by other 23 documents at any time. It is inappropriate to use Internet-Drafts as 24 reference material or to cite them other than as "work in progress." 26 The list of current Internet-Drafts can be accessed at 27 http://www.ietf.org/ietf/1id-abstracts.txt 29 The list of Internet-Draft Shadow Directories can be accessed at 30 http://www.ietf.org/shadow.html. 32 Abstract 34 This memo defines metrics to evaluate if a network has maintained 35 packet order on a packet-by-packet basis. It provides motivations 36 for the new metrics and discusses the measurement issues. The memo 37 first defines a reordered singleton, and then uses it as the basis 38 for sample metrics to quantify the extent of reordering in several 39 useful dimensions. Additional metrics quantify the frequency of 40 reordering and the distance between separate occurrences. We then 41 define metrics with a receiver analysis orientation. Several 42 examples of evaluation using the various sample metrics are 43 included. 45 1. Conventions used in this document 47 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 48 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 49 document are to be interpreted as described in RFC 2119 [2]. 50 Although RFC 2119 was written with protocols in mind, the key words 51 are used in this document for similar reasons. They are used to 53 Packet Reordering Metric for IPPM October 2003 55 ensure the results of measurements from two different 56 implementations are comparable, and to note instances when an 57 implementation could perturb the network. 59 2. Introduction 61 Ordered delivery is a property of successful packet transfer 62 attempts, where the packet sequence ascends for each arriving packet 63 and there are no backward steps. 65 An explicit sequence number, such as an incrementing message number 66 or the packet sending time carried in each packet, establishes the 67 Source Sequence. 69 The detection of reordering at the Destination is based on packet 70 arrival order in comparison with a non-reversing reference value. 72 This metric is consistent with RFC 2330 [3], and classifies arriving 73 packets with sequence numbers smaller than their predecessors as 74 out-of-order, or reordered. For example, if sequentially numbered 75 packets arrive 1,2,4,5,3, then packet 3 is reordered. This is 76 equivalent to Paxon's reordering definition in [4], where "late" 77 packets were declared reordered. The alternative is to emphasize 78 "premature" packets instead (4 and 5 in the example), but only the 79 arrival of packet 3 distinguishes this circumstance from packet 80 loss. Focusing attention on late packets allows us to maintain 81 orthogonality with the packet loss metric. The metric's construction 82 is very similar to the sequence space validation for received 83 segments in RFC793 [5]. Earlier work to define ordered delivery 84 includes [6], [7], [8], [9], [10] and more ???. 86 2.1 Motivation 88 A reordering metric is relevant for most applications, especially 89 when assessing network support for Real-Time media streams. The 90 extent of reordering may be sufficient to cause a received packet to 91 be discarded by functions above the IP layer. 93 Packet order is not expected to change during transfer, but several 94 specific path characteristics can cause order to change. 96 Examples are: 97 * When two paths, one with slightly longer transfer time, support a 98 single packet stream or flow, then packets traversing the longer 99 path may arrive out-of-order. Multiple paths may be used to 100 achieve load balancing, or may arise from route instability. 101 * To increase capacity, a network device designed with multiple 102 processors serving a single port may reorder as a byproduct. 103 * A layer 2 retransmission protocol that compensates for an error- 104 prone link may cause packet reordering. 106 Packet Reordering Metric for IPPM October 2003 108 * If for any reason, the packets in a buffer are not serviced in the 109 order of their arrival, their order will change. 110 * If packets in a flow are assigned to multiple buffers (following 111 evaluation of traffic characteristics, for example), and the 112 buffers have different occupations and/or service rates, then 113 order will likely change. 115 When one or more of the above path characteristics are present 116 continuously, then reordering may be present on a steady-state 117 basis. Measurements most easily detect this form of reordering when 118 the spacing between packets is minimized. Transient reordering may 119 occur in response to network instability; temporary routing loops 120 can cause periods of extreme reordering. 122 The ability to restore order at the destination will likely have 123 finite limits. Practical hosts have receiver buffers with finite 124 size in terms of packets, bytes, or time (such as de-jitter 125 buffers). Once the initial determination of reordering is made, it 126 is useful to quantify the extent of reordering, or lateness, in all 127 meaningful dimensions. 129 2.2 Goals and Objectives 131 The definitions below intend to satisfy the goals of: 132 1. Determining whether or not packet order is maintained. 133 2. Quantifying the extent (achieving this second goal requires 134 assumptions of upper layer functions and capabilities to 135 restore order, and therefore several solutions). 137 Reordering Metrics MUST: 139 + be relevant to one or more known applications 140 + be computable "on the fly" 141 + work with Poisson and Periodic test streams 142 + work even if the stream has duplicate or lost packets 144 Reordering Metrics SHOULD: 146 + have concatenating results for segments measured separately 147 + have simplicity for easy consumption and understanding 148 + have relevance to TCP performance 149 + have relevance to Real-time application performance 151 3. A Reordered Packet Singleton Metric 153 The IPPM framework RFC 2330 [3] describes the notions of singletons, 154 samples, and statistics. For easy reference: 156 By a 'singleton' metric, we refer to metrics that are, 157 in a sense, atomic. For example, a single instance of "bulk 158 throughput capacity" from one host to another might be defined 160 Packet Reordering Metric for IPPM October 2003 162 as a singleton metric, even though the instance involves 163 measuring the timing of a number of Internet packets. 165 The evaluation of packet order requires several supporting concepts. 166 The first is a sequence number applied to packets at the source to 167 uniquely identify the order of packet transmission. The sequence 168 number may be established by a simple message number, a byte stream 169 number, or it may be the actual time when each packet departs from 170 the Source. 172 The second supporting concept is a stored value which is the "next 173 expected" packet number. Under normal conditions, the value of Next 174 Expected (NextExp) is the sequence number of the previous packet 175 (plus 1 for message numbering). 177 Each packet within a packet stream can be evaluated with this order 178 singleton metric. 180 3.1 Metric Name: 182 Type-P-Reordered 184 3.2 Metric Parameters: 186 + Src, the IP address of a host 188 + Dst, the IP address of a host 190 + SrcTime, the time of packet emission from the Source (or wire 191 time) 193 + s, the packet sequence number applied at the Source, in units of 194 messages. 196 + SrcByte, the packet sequence number applied at the Source, in 197 units of payload bytes. 199 + NextExp, the Next Expected Sequence number at the Destination, in 200 units of messages, time, or bytes. 202 + PayloadSize, the number of bytes contained in the information 203 field and referred to when the SrcByte sequence is based on byte 204 transfer. 206 3.3 Definition: 208 The value of Type-P-Reordered is defined as false if s >= NextExp 209 (the packet is in-order). In this case, NextExp is set to s+1. 211 The value of Type-P-Reordered is defined as true if s < NextExp (the 212 packet is reordered). In this case, NextExp value does not change. 214 Packet Reordering Metric for IPPM October 2003 216 Since the Next Expected value cannot decrease, it provides a non- 217 reversing order criterion to identify reordered packets. 219 This definition can also be specified in pseudo-code. 221 On successful arrival of a packet with sequence number s: 222 if s >= NextExp, /* s is in-order */ 223 then 224 NextExp = s + 1; 225 Type-P-Reordered = False; 226 else /* when s < NextExp */ 227 Type-P-Reordered = True 229 We note that when s = NextExp, the original sequence has been 230 maintained, and there is no discontinuity present. 232 3.4 Evaluation in Time or Byte Order 234 For the alternate sequence dimensions, in-order packets have byte 235 stream numbers or Source times greater than or equal to the value of 236 NextExp. Each new in-order packet will increase the NextExp SrcTime 237 plus 1 clock tick when using Source times, or to SrcByte plus the 238 payload size plus 1 for byte numbering. In the pseudo-code above, 239 SrcByte (or SrcTime) replaces the sequence number s, and we have: 241 if SrcByte >= NextExp, /* packet is in-order */ 242 then 243 NextExp = SrcByte + PayloadSize + 1; 245 When using Source time, PayloadSize=0 (or a fixed time increment, if 246 using a reliable periodic packet source). 248 3.5 Discussion 250 Any arriving packet bearing a sequence number from the sequence that 251 establishes the Next Expected value can be evaluated to determine 252 whether it is in-order or reordered, based on a previous packet's 253 arrival. In the case where Next Expected is Undefined (because the 254 arriving packet is the first successful transfer), the packet is 255 designated in-order. 257 This metric assumes re-assembly of packet fragments before 258 evaluation. In principle, it is possible to use the Type-P-Reordered 259 metric to evaluate reordering among packet fragments, but each 260 fragment must contain source sequence information. 261 <<<<<<<< Note: Additional considerations will be needed here. 263 If duplicate packets (multiple non-corrupt copies) arrive at the 264 destination, they MUST be noted and only the first to arrive is 265 considered for further analysis (copies would be declared reordered 266 according to the definition above). This requirement has the same 268 Packet Reordering Metric for IPPM October 2003 270 storage implications as earlier IPPM metrics, and follows the 271 precedent of RFC 2679. 273 Packets with s > NextExp are a special case of in-order delivery. 274 This condition indicates a sequence discontinuity, either because of 275 packet loss or reordering. Reordered packets must arrive for the 276 sequence discontinuity to be defined as a reordering discontinuity 277 (see next section). Discontinuities are easiest to detect with 278 message numbering or payload byte numbering where payload size is 279 constant (and retransmissions are distinguished), and may be 280 possible with Periodic Streams and Source Time numbering. 282 4. Sample Metrics 284 In this section, we define metrics applicable to a sample of packets 285 from a single Source sequence number system. We begin with a simple 286 ratio metric indicating the reordered portion of the sample. When 287 this ratio is zero, no further reordering metrics are needed for 288 that sample. 290 When reordering occurs, it is highly desirable to assert the degree 291 to which a packet is out-of-order, or reordered with respect other 292 packets. This section defines several metrics that quantify the 293 extent of reordering in various units of measure. Each "extent" 294 metric highlights a relevant use. 296 The metrics in the sub-sections below have a network 297 characterization orientation, but also have relevance to receiver 298 design. 300 4.1 Reordered Packet Ratio 302 4.1.1 Metric Name: 304 Type-P-Reordered-Ratio-Stream 306 4.1.2 Metric Parameters: 308 The parameter set includes Type-P-Reordered singleton parameters, 309 the parameters unique to Poisson or Periodic Streams (as in RFC 2330 310 and RFC3432), plus the following: 312 + T0, a start time 314 + Tf, an end time 316 + dT, a waiting time for each packet to arrive 318 4.1.3 Definition: 320 Packet Reordering Metric for IPPM October 2003 322 For the packets arriving successfully between T0 and Tf+dT, the 323 ratio of reordered packets in the sample is 325 (Total of Reordered packets) / (Total packets received) 327 This fraction may be expressed as a percentage (multiply by 100%). 328 Note that in the case of duplicate packets, only the first copy is 329 used. 331 4.2 Reordering Extent 333 This section defines the extent to which packets are reordered, and 334 associates a specific sequence discontinuity with each reordered 335 packet. 337 4.2.1 Metric Name: 339 Type-P-packet-Reordering-Extent-Stream 341 4.2.2 Parameter Notation: 343 Given a stream of packets sent from a source to a destination, let K 344 be the total number of packets in that stream. 346 Assign each packet a sequence number, a consecutive integer from 1 347 to K in the order of packet emission. 349 Let L be the total number of packets received out of the K packets 350 sent. Recall that identical copies (duplicates) have been removed, 351 so L<=K. 353 Let s[1], s[2], ..., s[L], represent the original sequence numbers 354 associated with the packets in order of arrival. 356 Consider a reordered packet (as identified in section 3) with 357 arrival index i and source sequence number s[i]. There exists a set 358 of indexes j (1<=j s[i]. 360 4.2.3 Definition: 362 The reordering extent, e, of packet s[i] is defined to be 363 i-j for the smallest value of j. 365 Informally, the reordering extent is the maximum distance, in 366 packets, from a reordered packet to the earliest packet received 367 that has a larger sequence number. If a packet is in-order, it's 368 reordering extent is undefined. The first packet to arrive is in- 369 order by definition, and has undefined reordering extent. 371 >>>>>>> Comment on this definition of extent: For some arrival 372 orders, the assignment of a simple position/distance as the 373 reordering extent tends to overestimate the receiver storage needed 375 Packet Reordering Metric for IPPM October 2003 377 to restore order. We need to weigh the value of adding more 378 complexity in this definition against the accuracy it would provide. 379 A more accurate and complex procedure to calculate packet storage 380 would be to subtract any earlier reordered packets that the receiver 381 could pass on to the upper layers. 382 Those who desire "on-the-fly" calculation must assess whether such a 383 procedure is feasible. 385 4.2.4 Discussion: 387 The packet with index j (s[j], identified in the Definition above) 388 is the reordering discontinuity associated with packet with index i 389 (s[i]). This definition is formalized below. 391 Note that the K packets in the stream could be some subset of a 392 larger stream, but L is still the total number of packets received 393 out of the K packets sent in that subset. 395 A receiver must possess storage to restore order to packets that are 396 reordered. For cases with single reordered packets, the extent e 397 gives the number of packets that must be held in the receiver's 398 buffer while waiting for the reordered packet to complete the 399 sequence. For more complex scenarios, the extent may be an 400 overestimate of required storage. See Examples section (specific 401 example to be provided). 403 Knowledge of the reordering extent e is particularly useful for 404 determining the portion of reordered packets that can or cannot be 405 restored to order in a typical receiver buffer based on their 406 arrival order alone (and without the aid of retransmission). 408 A sample's reordering extents may be expressed as a histogram, to 409 easily summarize the frequency of various extents. 411 4.3 Reordering Offset 413 Any reordered packets can be assigned offset values indicating the 414 storage in bytes and lateness in terms of buffer time that a 415 receiver must possess to accommodate them. The various offset 416 metrics are calculated only on reordered packets, as identified by 417 the ordered arrival singleton in section 3. 419 4.3.1 Metric Name: Type-P-packet-Late-Time-Stream 421 Metric Parameters: In addition to the parameters defined for Type-P- 422 Reordered, we specify: 424 + DstTime, the time that each packet in the stream arrives at Dst 426 Definition: Lateness in time is calculated using Dst times. When 427 received packet i is reordered, and has a reordering extent e, then: 429 Packet Reordering Metric for IPPM October 2003 431 LateTime(i) = DstTime(i)-DstTime(i-e) 433 Alternatively, using similar notation to that of section 4.2, an 434 equivalent definition is: 435 LateTime(i) = DstTime(i)-DstTime(j), for min{j|1<=js[i], or SrcTime[j]>SrcTime[i]. 438 4.3.2 Metric Name: Type-P-packet-Byte-Offset-Stream 440 Metric Parameters: We use the same parameters defined above. 442 Definition: Byte stream offset is the sum of the payload sizes of 443 intervening in-order packets between the reordered packet and the 444 discontinuity (including the packet at the discontinuity). 446 For reordered packet i with a reordering extent e: 447 ByteOffset(i) = Sum[in-order packets back to reordering discon.] 448 = Sum[PayloadSize(packet at i-1 if in-order), 449 PayloadSize(packet at i-2 if in-order), ... 450 PayloadSize(packet at i-e if in-order)] 452 4.3.3 Discussion 454 The offset metrics can help predict whether reordered packets will 455 be useful in a general receiver buffer system with finite limits. 456 The limit may be the number of bytes or packets the buffer can 457 store, or the time of storage prior to a cyclic play-out instant (as 458 with de-jitter buffers). 460 Note that the One-way IPDV [11] gives the delay variation for a 461 packet w.r.t. the preceding packet in the source sequence. Lateness 462 and IPDV give an indication of whether a buffer at Dst has 463 sufficient storage to accommodate the network's behavior and restore 464 order. When an earlier packet in the Src sequence is lost, IPDV will 465 necessarily be undefined for adjacent packets, and Late Time may 466 provide the only way to evaluate the usefulness of a packet. 468 In the case of de-jitter buffers, there are circumstances where the 469 receiver employs loss concealment at the intended play-out time of a 470 late packet. However, if this packet arrives out of order, the Late 471 Time determines whether the packet is still useful. IPDV no longer 472 applies, because the receiver establishes a new play-out schedule 473 with additional buffer delay to accommodate similar events in the 474 future - this requires very minimal processing. 476 When packets in the stream have variable sizes, it may be most 477 useful to characterize Offset in terms of the payload size(s) of 478 stored packets (using byte stream numbering). 480 Packet Reordering Metric for IPPM October 2003 482 4.4 Gaps between multiple Reordering Discontinuities 484 4.4.1 Metric Name: 486 Type-P-packet-Reordering-Gap-Stream 488 4.4.2 Parameters: 490 No new parameters. 492 4.4.3 Definition of Reordering Discontinuity: 494 All reordered packets are associated with a packet at a reordering 495 discontinuity, defined as the in-order packet arrival s[j] at the 496 minimum value of j (1<=j s[i]. 498 Recall that i - e = min(j). Subsequent reordered packets may be 499 associated with the same s[j], or with a different discontinuity. 500 This definition is used in the definition of the Reordering Gap, 501 below. 503 4.4.4 Definition of Reordering Gap: 505 A reordering gap is the distance between successive reordering 506 discontinuities. Type-P-packet-Reordering-Gap-Stream assigns a value 507 to (all) packets in a stream. 509 If: 511 The packet s[j'] is found to be a reordering discontinuity, based 512 on the arrival of reordered packet s[i'] with extent e', and 514 an earlier reordering discontinuity s[j], based on the arrival of 515 reordered packet s[i] with extent e was already detected, and 517 i' > i, and 519 there are no reordering discontinuities between j and j', 521 then the Reordering Gap for packet s[j'] is the difference between 522 the arrival positions the reordering discontinuities, as shown 523 below: 525 Gap(j') = (j') - (j) 527 Otherwise: 529 The Type-P-packet-Reordering-Gap-Stream for the packet is 0. 531 Gaps may also be expressed in time: 533 Packet Reordering Metric for IPPM October 2003 535 GapTime(j') = DstTime(j') - DstTime(j) 537 4.4.5 Discussion 539 When separate reordering discontinuities can be distinguished, then 540 a count may also be reported (along with the discontinuity 541 description, such as the number of reordered packets associated with 542 that discontinuity and their extents and offsets). The Gaps between 543 a sample's reordering discontinuities may be expressed as a 544 histogram, to easily summarize the frequency of various gaps. 545 Reporting the mode, average, range, etc. may also summarize the 546 distributions. 548 The Gap metric may help to correlate the frequency of reordering 549 discontinuities with their cause. 551 4.5 Reordering-free Runs 553 This section defines a metric based on a count of consecutive 554 packets between reordered packets. 556 4.5.1 Metric Name: 558 Type-P-packet-Reordering-Free-Run-Stream 560 4.5.2 Parameters: 562 No new parameters. 564 4.5.3 Definition: 566 As packets in a sample arrive at the Destination, the count of 567 packets to the next reordered packet is a Reordering-Free run. Note 568 that the minimum run-length is one according to this definition. A 569 pseudo code example follows: 571 r = 0; /* r is the run counter */ 572 n = 0; /* n is the number of runs */ 573 a = 0; /* a is the accumulator of in order packets */ 574 p = 0; /* p is the number of packets */ 575 q = 0; /* q is the squared sum of the run counters */ 577 while(packets arrive with sequence number s) 578 { 579 P++; 580 if (s >= NextExp) /* s is in-order */ 581 then r++; 582 a++; 583 else /* s is reordered */ 584 q+= r*r; 585 r = 1; 587 Packet Reordering Metric for IPPM October 2003 589 n++; 590 } 592 4.5.4 Discussion: 594 Each arrival of a reordered packet yields a new count in the Run 595 vector. Long runs accompany periods where order was maintained, 596 while short runs indicate frequent, or multi-packet reordering. 598 5. Metric Related to Receiver Assessment 600 5.1 A TCP-Relevant Metric 602 5.1.1 Metric Name: 604 Type-P-packet-n-Reordering-Stream 606 5.1.2 Parameter Notation: 608 Let n be a positive integer (a parameter). Let k be a positive 609 integer equal to the number of packets sent (sample size). Let l be 610 a non-negative integer representing the number of packets that were 611 received out of the k packets sent. (Note that there is no 612 relationship between k and l: on one hand, losses can make l less 613 than k; on the other hand, duplicates can make l greater than k.) 614 Assign each sent packet a sequence number, 1 to k, in order of 615 packet emission. 617 Let s[1], s[2], ..., s[l] be the original sequence numbers of the 618 received packets, in the order of arrival. 620 5.1.3 Definitions 622 Definition 1: Received packet number i (n < i <= l), with source 623 sequence number s[i], is n-reordered if and only if for all j such 624 that i-n <= j < i, s[j] > s[i]. 626 Claim: If by this definition, a packet's reordering is n and 0 < n' 627 < n, then the packet is also reordered to the n' extent. 629 Note: This definition is illustrated by C code in Appendix A. It 630 determines the n-reordering for a value of n=3 (when actually 631 writing applications that would report the metric, one would 632 probably report it for several values of n, such as 1, 2, 3, 4 -- 633 and maybe a few more consecutive values). 634 This definition does not assign an n to all reordered packets as 635 defined by the singleton metric, in particular when blocks of 636 successive packets are reordered. (In the arrival sequence 637 s={1,2,3,7,8,9,4,5,6}, packets 4, 5, and 6 are reordered, but only 4 638 is n-reordered, with n=3.) 640 Definition 2: The degree of n-reordering of the sample is m/l. 642 Packet Reordering Metric for IPPM October 2003 644 Definition 3: The degree of "monotonic reordering" of the sample is 645 its degree of 1-reordering. 647 Definition 4: A sample is said to have no reordering if its degree 648 of n-reordering is 0. 650 5.1.4 Discussion: 652 The degree of n-reordering may be expressed as a percentage, in 653 which case the number from definition 2 is multiplied by 100. 655 Knowledge of n-reordering is particularly useful for determining the 656 portion of reordered packets that can or cannot be restored to order 657 in a typical TCP receiver buffer based on their arrival order alone 658 (and without the aid of retransmission). 660 Important special cases are n=1 and n=3: 662 - For n=1, absence of 1-reordering means the sequence numbers that 663 the receiver sees are monotonically increasing with respect to the 664 previous arriving packet. 666 - For n=3, a NewReno TCP sender would retransmit 1 packet in 667 response to an instance of 3-reordering and therefore consider this 668 packet lost for the purposes of congestion control (the sender will 669 half its congestion window). Detecting instances of 3-reordering is 670 useful for determining the portion of reordered packets that are in 671 fact as good as lost. 673 A sample's n-reordering may be expressed as a histogram, to 674 summarize the frequency for each value of n. 676 We note that the definition of n-reordering cannot predict the exact 677 number of packets unnecessarily retransmitted by a TCP sender under 678 some circumstances, such as cases with closely-spaced reordered 679 singletons. The definition is less complicated than a TCP 680 implementation where both time and position influence the sender's 681 behavior. 683 A packet's n-reordering is sometimes equal to it's reordering 684 extent, e. n-reordering is different in the following ways: 686 1. n is a count of *adjacent* early packets. 688 2. Some reordered packets may not be n-reordered, but will have e 689 (see the examples). 691 6. Measurement Issues 693 The results of tests will be dependent on the time interval between 694 measurement packets (both at the Src, and during transport where 696 Packet Reordering Metric for IPPM October 2003 698 spacing may change). Clearly, packets launched infrequently (e.g., 699 1 per 10 seconds) are unlikely to be reordered. 701 Test streams may prefer to use a periodic sending interval so that a 702 known temporal bias is maintained, also bringing simplified results 703 analysis (as described in RFC 3432 [12]). In this case, the periodic 704 sending interval should be chosen to reproduce the closest Src 705 packet spacing expected. Of course, packet spacing is likely to vary 706 as the stream traverses the test path. 707 <<<, the received 821 packets are represented as: 823 \/ 824 s = 1, 2, 3, 5, 6, 7, 8, 4, 9, 10 825 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 826 /\ 827 when j=7, 8 > 4, so the reordering extent is 1 or more. 828 when j=6, 7 > 4, so the reordering extent is 2 or more. 829 when j=5, 6 > 4, so the reordering extent is 3 or more. 830 when j=4, 5 > 4, so the reordering extent is 4 or more. 831 when j=3, but 3 < 4, and 4 is the maximum extent, e=4 (assuming 832 there are no earlier sequence discontinuities, as in this example). 834 Further, we can compute the Late Time (210-148=62ms using DstTime) 835 compared to Packet 5's arrival. If the receiver has a de-jitter 836 buffer that holds more than 4 packets, or at least 62 ms storage, 837 Packet 4 may be useful. Note that 1-way delay and IPDV also indicate 838 unusual behavior for Packet 4. 840 If all packets contained 100 byte payloads, then Byte Offset is 841 equal to 400 bytes. 843 Following the definitions of section 5.1, Packet 4 is defined to be 844 4-reordered. 846 Table 2 Example with Packets 5 and 6 Reordered, 847 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10 848 s Src Dst Dst Byte Late 849 @Dst NextExp Time Time Delay IPDV Order Offset Time 850 1 1 0 68 68 1 851 2 2 20 88 68 0 2 852 3 3 40 108 68 0 3 853 4 4 60 128 68 0 4 854 7 5 120 188 68 -22 5 855 5 8 80 189 109 41 6 100 1 857 Packet Reordering Metric for IPPM October 2003 859 6 8 100 190 90 -19 7 100 2 860 8 8 140 208 68 0 8 861 9 9 160 228 68 0 9 862 10 10 180 248 68 0 10 864 Table 2 shows a case where Packets 5 and 6 arrive just behind Packet 865 7, so both 5 and 6 are reordered. The Late times (189-188=1, 190- 866 188=2) are small. 868 Using the notation , the received 869 packets are represented as: 871 \/ \/ 872 s = 1, 2, 3, 4, 7, 5, 6, 8, 9, 10 873 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 874 /\ /\ 876 Considering Packet 5 first: 877 when j=5, 7 > 5, so the reordering extent is 1 or more. 878 when j=4, but 4 < 5, so 1 is its maximum extent, and e=1. 880 Considering Packet 6 next: 881 when j=6, 5 < 6, the extent is not yet defined. 882 when j=5, 7 > 6, so the reordering extent is i-j=2 or more. 883 when j=4, 4 < 6, and we find 2 is its maximum extent, and e=2. 885 We can also associate each of these reordered packets with a 886 reordering discontinuity. We find the minimum j=5 (for both packets) 887 according to Section 4.2.4. So Packet 6 is associated with the same 888 reordering discontinuity as Packet 5, at Packet 7. 890 Following the definitions of section 5.1, Packet 5 is defined to be 891 1-reordered, but Packet 6 is not qualified n-reordered. 893 A hypothetical sender/receiver pair may retransmit Packet 5 894 unnecessarily, since it is 1-reordered (in agreement with the 895 singleton metric). Though Packet 6 may not be unnecessarily 896 retransmitted, the receiver cannot advance Packet 7 to the higher 897 layers until after Packet 6 arrives. Therefore, the singleton metric 898 correctly determined that Packet 6 is reordered. 900 Table 3 Example with Packets 4, 5, and 6 reordered 901 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11 902 s Src Dst Dst Byte Late 903 @Dst NextExp Time Time Delay IPDV Order Offset Time 904 1 1 0 68 68 1 905 2 2 20 88 68 0 2 906 3 3 40 108 68 0 3 907 7 4 120 188 68 -88 4 908 8 8 140 208 68 0 5 910 Packet Reordering Metric for IPPM October 2003 912 9 9 160 228 68 0 6 913 10 10 180 248 68 0 7 914 4 11 60 250 190 122 8 400 62 915 5 11 80 252 172 -18 9 400 64 916 6 11 100 256 156 -16 10 400 68 917 11 11 200 268 68 0 11 919 The case in Table 3 is where three packets in sequence have long 920 transit times (Packets with s = 4,5,and 6). Delay, Late time, and 921 Byte Offset capture this very well, and indicate variation in 922 reordering extent, while IPDV indicates that the spacing between 923 packets 4,5,and 6 has changed. 925 The histogram of Reordering extents (e) would be: 927 Bin 1 2 3 4 5 6 7 928 Frequency 0 0 0 1 1 1 0 930 Using the notation , the received 931 packets are represented as: 933 s = 1, 2, 3, 7, 8, 9,10, 4, 5, 6, 11 934 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11 936 We first calculate the n-reordering. Considering Packet 4 first: 937 when n=1, 7<=j<8, and 10> 4, so the packet is 1-reordered. 938 when n=2, 6<=j<8, and 9 > 4, so the packet is 2-reordered. 939 when n=3, 5<=j<8, and 8 > 4, so the packet is 3-reordered. 940 when n=4, 4<=j<8, and 7 > 4, so the packet is 4-reordered. 941 when n=5, 3<=j<8, but 3 < 4, and 4 is the maximum n-reordering. 943 Considering packet 5[9] next: 944 when n=1, 8<=j<9, but 4 < 5, so the packet at i=9 is not qualified 945 as n-reordered. We find the same to for Packet 6. 947 We now consider whether reordered Packets 5 and 6 are associated 948 with the same reordering discontinuity as Packet 4. Using the test 949 of Section 4.2.4, Definition 2, we find that the minimum j=4 for all 950 three packets. They are all associated with the reordering 951 discontinuity at Packet 7. 953 This example shows again that the n-reordering definition identifies 954 a single Packet (4) with a sufficient degree of reordering to result 955 in one unnecessary packet retransmission by the New Reno TCP sender. 956 Also, the reordered arrival of Packets 5 and 6 will allow the 957 receiver process to pass Packets 7 through 10 up the protocol stack 958 (the singleton metric indicates 5 and 6 are reordered, and they are 959 all associated with a single reordering discontinuity). 961 Table 4 Example with Packets Multiple Reordering Discontinuities 962 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 964 Packet Reordering Metric for IPPM October 2003 966 Discontinuity Discontinuity 967 |---------Gap---------| 968 s = 1, 2, 3, 6, 7, 4, 5, 8, 9, 10, 12, 13, 11, 14, 15, 16 969 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 971 r = 1, 2, 3, 4, 5, 1, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, ... 972 n = 1 2 3 973 end r counts = 5 1 6 975 Packet 4 has extent e=2, Packet 5 has extent e=3, and Packet 11 has 976 e=2. There are two different reordering discontinuities, one at 977 Packet 6 (where j=4) and one at Packet 12 (where j'=11). 979 According to the definition of Reordering Gap 980 Gap(j') = (j') - (j) 981 Gap(11) = (11) - (4) = 7 983 We also have three reordering-free runs of lengths 5, 1, and 6. 985 The differences between these two multiple-event metrics are evident 986 here. Gaps are the distance between sequence discontinuities that 987 are subsequently defined as reordering discontinuities, while 988 reordering-free runs are capture the distance between reordered 989 packets. 991 8. Security Considerations 993 8.1 Denial of Service Attacks 995 This metric requires a stream of packets sent from one host (Src) to 996 another host (Dst) through intervening networks. This method could 997 be abused for denial of service attacks directed at Dst and/or the 998 intervening network(s). 1000 Administrators of Src, Dst, and the intervening network(s) should 1001 establish bilateral or multi-lateral agreements regarding the 1002 timing, size, and frequency of collection of sample metrics. Use of 1003 this method in excess of the terms agreed between the participants 1004 may be cause for immediate rejection or discard of packets or other 1005 escalation procedures defined between the affected parties. 1007 8.2 User data confidentiality 1009 Active use of this method generates packets for a sample, rather 1010 than taking samples based on user data, and does not threaten user 1011 data confidentiality. Passive measurement must restrict attention to 1012 the headers of interest. Since user payloads may be temporarily 1013 stored for length analysis, suitable precautions MUST be taken to 1014 keep this information safe and confidential. 1016 Packet Reordering Metric for IPPM October 2003 1018 8.3 Interference with the metric 1020 It may be possible to identify that a certain packet or stream of 1021 packets is part of a sample. With that knowledge at Dst and/or the 1022 intervening networks, it is possible to change the processing of the 1023 packets (e.g. increasing or decreasing delay) that may distort the 1024 measured performance. It may also be possible to generate 1025 additional packets that appear to be part of the sample metric. 1026 These additional packets are likely to perturb the results of the 1027 sample measurement. 1029 To discourage the kind of interference mentioned above, packet 1030 interference checks, such as cryptographic hash, may be used. 1032 9. IANA Considerations 1034 Since this metric does not define a protocol or well-known values, 1035 there are no IANA considerations in this memo. 1037 10. References 1039 1 Bradner, S., "The Internet Standards Process -- Revision 3", BCP 1040 9, RFC 2026, October 1996. 1042 2 Bradner, S., "Key words for use in RFCs to Indicate Requirement 1043 Levels", RFC 2119, March 1997. 1045 3 Paxson, V., Almes, G., Mahdavi, J., and Mathis, M., "Framework 1046 for IP Performance Metrics", RFC 2330, May 1998. 1048 4 V.Paxson, "Measurements and Analysis of End-to-End Internet 1049 Dynamics," Ph.D. dissertation, U.C. Berkeley, 1997, 1050 ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz. 1052 5 Postel, J., "Transmission Control Protocol", STD 7, RFC 793, 1053 September 1981. 1054 Obtain via: http://www.rfc-editor.org/rfc/rfc793.txt 1056 6 L.Ciavattone and A.Morton, "Out-of-Sequence Packet Parameter 1057 Definition (for Y.1540)", Contribution number T1A1.3/2000-047, 1058 October 30, 2000. ftp://ftp.t1.org/pub/t1a1/2000-A13/0a130470.doc 1060 7 J.C.R.Bennett, C.Partridge, and N.Shectman, "Packet Reordering is 1061 Not Pathological Network Behavior," IEEE/ACM Transactions on 1062 Neteworking, vol.7, no.6, pp.789-798, December 1999. 1064 8 D.Loguinov and H.Radha, "Measurement Study of Low-bitrate 1065 Internet Video Streaming", Proceedings of the ACM SIGCOMM 1066 Internet Measurement Workshop 2001 November 1-2, 2001, San 1067 Francisco, USA. 1069 Packet Reordering Metric for IPPM October 2003 1071 9 J.Bellardo and S.Savage, "Measuring Packet Reordering," 1072 Proceedings of the ACM SIGCOMM Internet Measurement Workshop 1073 2002, November 6-8, Marseille, France. 1075 10 S.Jaiswal et al., "Measurement and Classification of Out-of- 1076 Sequence Packets in a Tier-1 IP Backbone," Proceedings of the ACM 1077 SIGCOMM Internet Measurement Workshop 2002, November 6-8, 1078 Marseille, France. 1080 11 Demichelis, C., and Chimento, P., "IP Packet Delay Variation 1081 Metric for IP Performance Metrics (IPPM)", RFC 3393, November 1082 2002. 1084 12 Raisanen, V., Grotefeld, G., and Morton, A., "Network performance 1085 measurement with periodic streams", RFC 3432, November 2002. 1087 12. Acknowledgments 1089 The authors would like to acknowledge many helpful discussions with 1090 Matt Mathis, Jon Bennett, and Matt Zekauskas. We gratefully 1091 acknowledge the foundation laid by the authors of the IP performance 1092 Framework [3]. 1094 13. Appendix A (informative) 1096 Two example c-code implementations of reordering definitions follow: 1098 Example 1 n-reordering ============================================ 1100 #include 1102 #define MAX_N 100 1104 #define min(a, b) ((a) < (b)? (a): (b)) 1105 #define loop(x) ((x) >= 0? x: x + MAX_N) 1107 /* 1108 * Read new sequence number and return it. Return a sentinel value 1109 of EOF 1110 * (at least once) when there are no more sequence numbers. In this 1111 example, 1112 * the sequence numbers come from stdin; in an actual test, they 1113 would come 1114 * from the network. 1115 */ 1116 int 1117 read_sequence_number() 1118 { 1119 int res, rc; 1120 rc = scanf("%d\n", &res); 1121 if (rc == 1) return res; 1123 Packet Reordering Metric for IPPM October 2003 1125 else return EOF; 1126 } 1128 int 1129 main() 1130 { 1131 int m[MAX_N]; /* We have m[j-1] == number 1132 of 1133 * j-reordered packets. */ 1134 int ring[MAX_N]; /* Last sequence numbers 1135 seen. */ 1136 int r = 0; /* Ring pointer for next 1137 write. */ 1138 int l = 0; /* Number of sequence 1139 numbers read. */ 1140 int s; /* Last sequence number 1141 read. */ 1142 int j; 1144 for (j = 0; j < MAX_N; j++) m[j] = 0; 1145 for (; (s = read_sequence_number()) != EOF; l++, r = (r+1) % 1146 MAX_N) { 1147 for (j=0; j 1164 #define MAX_N 100 1165 #define min(a, b) ((a) < (b)? (a): (b)) 1166 #define loop(x) ((x) >= 0? x: x + MAX_N) 1168 /* Global counters */ 1169 int receive_packets=0; /* number of recieved */ 1170 int reorder_packets=0; /* number of reordered packets */ 1172 /* function to test if current packet has been reordered 1173 * returns 0 = not reordered 1174 * 1 = reordered 1176 Packet Reordering Metric for IPPM October 2003 1178 */ 1179 int testorder1(int seqnum) // Al 1180 { 1181 static int NextExp = 1; 1182 int iReturn = 0; 1184 if (seqnum >= NextExp) { 1185 NextExp = seqnum+1; 1186 } else { 1187 iReturn = 1; 1188 } 1189 return iReturn; 1190 } 1192 int testorder2(int seqnum) // Stanislav 1193 { 1194 static int ring[MAX_N]; /* Last sequence numbers 1195 seen. */ 1196 static int r = 0; /* Ring pointer for next write. 1197 */ 1198 int l = 0; /* Number of sequence 1199 numbers read. */ 1200 int j; 1201 int iReturn = 0; 1203 l++; 1204 r = (r+1) % MAX_N; 1205 for (j=0; j 1237 Len Ciavattone 1238 AT&T Labs 1239 Room C4 - 2B29 1240 200 Laurel Ave. South 1241 Middletown, NJ 07748 USA 1242 Phone +1 732 420 1239 1243 1245 Gomathi Ramachandran 1246 AT&T Labs 1247 Room C4 - 3D22 1248 200 Laurel Ave. South 1249 Middletown, NJ 07748 USA 1250 Phone +1 732 420 2353 1251 1253 Stanislav Shalunov 1254 Internet2 1255 200 Business Park Drive, Suite 307 1256 Armonk, NY 10504 1257 Phone: + 1 914 765 1182 1258 EMail: 1260 Jerry Perser 1261 Spirent Communications 1262 26750 Agoura Road 1263 Calabasas, CA 91302 USA 1264 Phone: + 1 818 676 2300 1265 EMail: 1267 Full Copyright Statement 1269 "Copyright (C) The Internet Society (date). All Rights Reserved. 1270 This document and translations of it may be copied and furnished to 1271 others, and derivative works that comment on or otherwise explain it 1272 or assist in its implmentation may be prepared, copied, published 1273 and distributed, in whole or in part, without restriction of any 1274 kind, provided that the above copyright notice and this paragraph 1275 are included on all such copies and derivative works. However, this 1276 document itself may not be modified in any way, such as by removing 1277 the copyright notice or references to the Internet Society or other 1278 Internet organizations, except as needed for the purpose of 1279 developing Internet standards in which case the procedures for 1280 copyrights defined in the Internet Standards process must be 1281 followed, or as required to translate it into languages other than 1282 English. 1284 Packet Reordering Metric for IPPM October 2003 1286 The limited permissions granted above are perpetual and will not be 1287 revoked by the Internet Society or its successors or assigns. 1289 This document and the information contained herein is provided on an 1290 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 1291 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 1292 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 1293 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 1294 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.