idnits 2.17.1 draft-ietf-ippm-reordering-05.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. 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 1174 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 918 looks like a reference -- Missing reference section? '2' on line 620 looks like a reference -- Missing reference section? '3' on line 1076 looks like a reference -- Missing reference section? '4' on line 73 looks like a reference -- Missing reference section? '5' on line 80 looks like a reference -- Missing reference section? '6' on line 81 looks like a reference -- Missing reference section? '7' on line 81 looks like a reference -- Missing reference section? '8' on line 81 looks like a reference -- Missing reference section? '9' on line 931 looks like a reference -- Missing reference section? '10' on line 81 looks like a reference -- Missing reference section? 'L' on line 814 looks like a reference -- Missing reference section? '12' on line 440 looks like a reference -- Missing reference section? '13' on line 701 looks like a reference Summary: 5 errors (**), 0 flaws (~~), 1 warning (==), 16 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group A.Morton 2 Internet Draft L.Ciavattone 3 Document: G.Ramachandran 4 Category: Standards Track AT&T Labs 5 S.Shalunov 6 Internet2 7 J.Perser 8 Consultant 10 Packet Reordering Metric for IPPM 12 Status of this Memo 14 This document is an Internet-Draft and is in full conformance with 15 all provisions of Section 10 of RFC2026 [1]. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note that 19 other groups may also distribute working documents as Internet- 20 Drafts. Internet-Drafts are draft documents valid for a maximum of 21 six months and may be updated, replaced, or made obsolete by other 22 documents at any time. It is inappropriate to use Internet-Drafts as 23 reference material or to cite them other than as "work in progress." 25 The list of current Internet-Drafts can be accessed at 26 http://www.ietf.org/ietf/1id-abstracts.txt 28 The list of Internet-Draft Shadow Directories can be accessed at 29 http://www.ietf.org/shadow.html. 31 Abstract 33 This memo defines metrics to evaluate if a network has maintained 34 packet order on a packet-by-packet basis. It provides motivations 35 for the new metrics and discusses the measurement issues. The memo 36 first defines a reordered singleton, and then uses it as the basis 37 for sample metrics to quantify the extent of reordering in several 38 useful dimensions. Additional metrics quantify the frequency of 39 reordering and the distance between separate occurrences. We then 40 define metrics with a receiver analysis orientation. Several 41 examples of evaluation using the various sample metrics are 42 included. An Appendix gives extended definitions for evaluating 43 order with packet fragmentation. 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 52 ensure the results of measurements from two different 53 implementations are comparable, and to note instances when an 54 implementation could perturb the network. 56 2. Introduction 58 Ordered delivery is a property of successful packet transfer 59 attempts, where the packet sequence ascends for each arriving packet 60 and there are no backward steps. 62 An explicit sequence number, such as an incrementing message number 63 or the packet sending time carried in each packet, establishes the 64 Source Sequence. 66 The detection of reordering at the Destination is based on packet 67 arrival order in comparison with a non-reversing reference value. 69 This metric is consistent with RFC 2330 [3], and classifies arriving 70 packets with sequence numbers smaller than their predecessors as 71 out-of-order, or reordered. For example, if sequentially numbered 72 packets arrive 1,2,4,5,3, then packet 3 is reordered. This is 73 equivalent to Paxon's reordering definition in [4], where "late" 74 packets were declared reordered. The alternative is to emphasize 75 "premature" packets instead (4 and 5 in the example), but only the 76 arrival of packet 3 distinguishes this circumstance from packet 77 loss. Focusing attention on late packets allows us to maintain 78 orthogonality with the packet loss metric. The metric's construction 79 is very similar to the sequence space validation for received 80 segments in RFC793 [5]. Earlier work to define ordered delivery 81 includes [6], [7], [8], [9], [10] and [11. 83 2.1 Motivation 85 A reordering metric is relevant for most applications, especially 86 when assessing network support for Real-Time media streams. The 87 extent of reordering may be sufficient to cause a received packet to 88 be discarded by functions above the IP layer. 90 Packet order is not expected to change during transfer, but several 91 specific path characteristics can cause order to change. 93 Examples are: 94 * When two paths, one with slightly longer transfer time, support a 95 single packet stream or flow, then packets traversing the longer 96 path may arrive out-of-order. Multiple paths may be used to 97 achieve load balancing, or may arise from route instability. 98 * To increase capacity, a network device designed with multiple 99 processors serving a single port may reorder as a byproduct. 100 * A layer 2 retransmission protocol that compensates for an error- 101 prone link may cause packet reordering. 103 * If for any reason, the packets in a buffer are not serviced in the 104 order of their arrival, their order will change. 105 * If packets in a flow are assigned to multiple buffers (following 106 evaluation of traffic characteristics, for example), and the 107 buffers have different occupations and/or service rates, then 108 order will likely change. 110 When one or more of the above path characteristics are present 111 continuously, then reordering may be present on a steady-state 112 basis. Measurements most easily detect this form of reordering when 113 the spacing between packets is minimized. Transient reordering may 114 occur in response to network instability; temporary routing loops 115 can cause periods of extreme reordering. 117 The ability to restore order at the destination will likely have 118 finite limits. Practical hosts have receiver buffers with finite 119 size in terms of packets, bytes, or time (such as de-jitter 120 buffers). Once the initial determination of reordering is made, it 121 is useful to quantify the extent of reordering, or lateness, in all 122 meaningful dimensions. 124 2.2 Goals and Objectives 126 The definitions below intend to satisfy the goals of: 127 1. Determining whether or not packet order is maintained. 128 2. Quantifying the extent (achieving this second goal requires 129 assumptions of upper layer functions and capabilities to 130 restore order, and therefore several solutions). 132 Reordering Metrics MUST: 134 + be relevant to one or more known applications 135 + be computable "on the fly" 136 + work with Poisson and Periodic test streams 137 + work even if the stream has duplicate or lost packets 139 Reordering Metrics SHOULD: 141 + have concatenating results for segments measured separately 142 + have simplicity for easy consumption and understanding 143 + have relevance to TCP performance 144 + have relevance to Real-time application performance 146 3. A Reordered Packet Singleton Metric 148 The IPPM framework RFC 2330 [3] describes the notions of singletons, 149 samples, and statistics. For easy reference: 151 By a 'singleton' metric, we refer to metrics that are, 152 in a sense, atomic. For example, a single instance of "bulk 153 throughput capacity" from one host to another might be defined 154 as a singleton metric, even though the instance involves 155 measuring the timing of a number of Internet packets. 157 The evaluation of packet order requires several supporting concepts. 158 The first is a sequence number applied to packets at the source to 159 uniquely identify the order of packet transmission. The sequence 160 number may be established by a simple message number, a byte stream 161 number, or it may be the actual time when each packet departs from 162 the Source. 164 The second supporting concept is a stored value which is the "next 165 expected" packet number. Under normal conditions, the value of Next 166 Expected (NextExp) is the sequence number of the previous packet 167 (plus 1 for message numbering). 169 Each packet within a packet stream can be evaluated with this order 170 singleton metric. 172 3.1 Metric Name: 174 Type-P-Reordered 176 3.2 Metric Parameters: 178 + Src, the IP address of a host 180 + Dst, the IP address of a host 182 + SrcTime, the time of packet emission from the Source (or wire 183 time) 185 + s, the packet sequence number applied at the Source, in units of 186 messages. 188 + SrcByte, the packet sequence number applied at the Source, in 189 units of payload bytes. 191 + NextExp, the Next Expected Sequence number at the Destination, in 192 units of messages, time, or bytes. 194 + PayloadSize, the number of bytes contained in the information 195 field and referred to when the SrcByte sequence is based on byte 196 transfer. 198 3.3 Definition: 200 The value of Type-P-Reordered is defined as false if s >= NextExp 201 (the packet is in-order). In this case, NextExp is set to s+1. 203 The value of Type-P-Reordered is defined as true if s < NextExp (the 204 packet is reordered). In this case, NextExp value does not change. 206 Since the Next Expected value cannot decrease, it provides a non- 207 reversing order criterion to identify reordered packets. 209 This definition can also be specified in pseudo-code. 211 On successful arrival of a packet with sequence number s: 212 if s >= NextExp, /* s is in-order */ 213 then 214 NextExp = s + 1; 215 Type-P-Reordered = False; 216 else /* when s < NextExp */ 217 Type-P-Reordered = True 219 We note that when s = NextExp, the original sequence has been 220 maintained, and there is no discontinuity present. 222 3.4 Evaluation in Time or Byte Order 224 For the alternate sequence dimensions, in-order packets have byte 225 stream numbers or Source times greater than or equal to the value of 226 NextExp. Each new in-order packet will increase the NextExp SrcTime 227 plus 1 clock tick when using Source times, or to SrcByte plus the 228 payload size plus 1 for byte numbering. In the pseudo-code above, 229 SrcByte (or SrcTime) replaces the sequence number s, and we have: 231 if SrcByte >= NextExp, /* packet is in-order */ 232 then 233 NextExp = SrcByte + PayloadSize + 1; 235 When using Source time, PayloadSize=0 (or a fixed time increment, if 236 using a reliable periodic packet source). 238 3.5 Discussion 240 Any arriving packet bearing a sequence number from the sequence that 241 establishes the Next Expected value can be evaluated to determine 242 whether it is in-order or reordered, based on a previous packet's 243 arrival. In the case where Next Expected is Undefined (because the 244 arriving packet is the first successful transfer), the packet is 245 designated in-order. 247 This metric assumes re-assembly of packet fragments before 248 evaluation. In principle, it is possible to use the Type-P-Reordered 249 metric to evaluate reordering among packet fragments, but each 250 fragment must contain source sequence information. 251 See the Appendix on fragment order evaluation for more detail. 253 If duplicate packets (multiple non-corrupt copies) arrive at the 254 destination, they MUST be noted and only the first to arrive is 255 considered for further analysis (copies would be declared reordered 256 according to the definition above). This requirement has the same 257 storage implications as earlier IPPM metrics, and follows the 258 precedent of RFC 2679. 260 Packets with s > NextExp are a special case of in-order delivery. 261 This condition indicates a sequence discontinuity, either because of 262 packet loss or reordering. Reordered packets must arrive for the 263 sequence discontinuity to be defined as a reordering discontinuity 264 (see next section). Discontinuities are easiest to detect with 265 message numbering or payload byte numbering where payload size is 266 constant (and retransmissions are distinguished), and may be 267 possible with Periodic Streams and Source Time numbering. 269 4. Sample Metrics 271 In this section, we define metrics applicable to a sample of packets 272 from a single Source sequence number system. We begin with a simple 273 ratio metric indicating the reordered portion of the sample. When 274 this ratio is zero, no further reordering metrics are needed for 275 that sample. 277 When reordering occurs, it is highly desirable to assert the degree 278 to which a packet is out-of-order, or reordered with respect other 279 packets. This section defines several metrics that quantify the 280 extent of reordering in various units of measure. Each "extent" 281 metric highlights a relevant use. 283 The metrics in the sub-sections below have a network 284 characterization orientation, but also have relevance to receiver 285 design. 287 4.1 Reordered Packet Ratio 289 4.1.1 Metric Name: 291 Type-P-Reordered-Ratio-Stream 293 4.1.2 Metric Parameters: 295 The parameter set includes Type-P-Reordered singleton parameters, 296 the parameters unique to Poisson or Periodic Streams (as in RFC 2330 297 and RFC3432), plus the following: 299 + T0, a start time 301 + Tf, an end time 303 + dT, a waiting time for each packet to arrive 305 4.1.3 Definition: 307 For the packets arriving successfully between T0 and Tf+dT, the 308 ratio of reordered packets in the sample is 310 (Total of Reordered packets) / (Total packets received) 312 This fraction may be expressed as a percentage (multiply by 100%). 313 Note that in the case of duplicate packets, only the first copy is 314 used. 316 4.2 Reordering Extent 318 This section defines the extent to which packets are reordered, and 319 associates a specific sequence discontinuity with each reordered 320 packet. 322 4.2.1 Metric Name: 324 Type-P-packet-Reordering-Extent-Stream 326 4.2.2 Parameter Notation: 328 Given a stream of packets sent from a source to a destination, let K 329 be the total number of packets in that stream. 331 Assign each packet a sequence number, a consecutive integer from 1 332 to K in the order of packet emission. 334 Let L be the total number of packets received out of the K packets 335 sent. Recall that identical copies (duplicates) have been removed, 336 so L<=K. 338 Let s[1], s[2], ..., s[L], represent the original sequence numbers 339 associated with the packets in order of arrival. 341 Consider a reordered packet (as identified in section 3) with 342 arrival index i and source sequence number s[i]. There exists a set 343 of indexes j (1<=j s[i]. 345 4.2.3 Definition: 347 The reordering extent, e, of packet s[i] is defined to be 348 i-j for the smallest value of j. 350 Informally, the reordering extent is the maximum distance, in 351 packets, from a reordered packet to the earliest packet received 352 that has a larger sequence number. If a packet is in-order, its 353 reordering extent is undefined. The first packet to arrive is in- 354 order by definition, and has undefined reordering extent. 356 >>>>>>> Comment on this definition of extent: For some arrival 357 orders, the assignment of a simple position/distance as the 358 reordering extent tends to overestimate the receiver storage needed 359 to restore order. We need to weigh the value of adding more 360 complexity in this definition against the accuracy it would provide. 361 A more accurate and complex procedure to calculate packet storage 362 would be to subtract any earlier reordered packets that the receiver 363 could pass on to the upper layers. 364 Those who desire "on-the-fly" calculation must assess whether such a 365 procedure is feasible. 367 4.2.4 Discussion: 369 The packet with index j (s[j], identified in the Definition above) 370 is the reordering discontinuity associated with packet with index i 371 (s[i]). This definition is formalized below. 373 Note that the K packets in the stream could be some subset of a 374 larger stream, but L is still the total number of packets received 375 out of the K packets sent in that subset. 377 A receiver must possess storage to restore order to packets that are 378 reordered. For cases with single reordered packets, the extent e 379 gives the number of packets that must be held in the receiver's 380 buffer while waiting for the reordered packet to complete the 381 sequence. For more complex scenarios, the extent may be an 382 overestimate of required storage. See Examples section (specific 383 example to be provided). 385 Knowledge of the reordering extent e is particularly useful for 386 determining the portion of reordered packets that can or cannot be 387 restored to order in a typical receiver buffer based on their 388 arrival order alone (and without the aid of retransmission). 390 A sample's reordering extents may be expressed as a histogram, to 391 easily summarize the frequency of various extents. 393 4.3 Reordering Offset 395 Any reordered packets can be assigned offset values indicating the 396 storage in bytes and lateness in terms of buffer time that a 397 receiver must possess to accommodate them. The various offset 398 metrics are calculated only on reordered packets, as identified by 399 the ordered arrival singleton in section 3. 401 4.3.1 Metric Name: Type-P-packet-Late-Time-Stream 403 Metric Parameters: In addition to the parameters defined for Type-P- 404 Reordered, we specify: 406 + DstTime, the time that each packet in the stream arrives at Dst 408 Definition: Lateness in time is calculated using Dst times. When 409 received packet i is reordered, and has a reordering extent e, then: 411 LateTime(i) = DstTime(i)-DstTime(i-e) 413 Alternatively, using similar notation to that of section 4.2, an 414 equivalent definition is: 415 LateTime(i) = DstTime(i)-DstTime(j), for min{j|1<=js[i], or SrcTime[j]>SrcTime[i]. 418 4.3.2 Metric Name: Type-P-packet-Byte-Offset-Stream 420 Metric Parameters: We use the same parameters defined above. 422 Definition: Byte stream offset is the sum of the payload sizes of 423 intervening in-order packets between the reordered packet and the 424 discontinuity (including the packet at the discontinuity). 426 For reordered packet i with a reordering extent e: 427 ByteOffset(i) = Sum[in-order packets back to reordering discon.] 428 = Sum[PayloadSize(packet at i-1 if in-order), 429 PayloadSize(packet at i-2 if in-order), ... 430 PayloadSize(packet at i-e if in-order)] 432 4.3.3 Discussion 434 The offset metrics can help predict whether reordered packets will 435 be useful in a general receiver buffer system with finite limits. 436 The limit may be the number of bytes or packets the buffer can 437 store, or the time of storage prior to a cyclic play-out instant (as 438 with de-jitter buffers). 440 Note that the One-way IPDV [12] gives the delay variation for a 441 packet w.r.t. the preceding packet in the source sequence. Lateness 442 and IPDV give an indication of whether a buffer at Dst has 443 sufficient storage to accommodate the network's behavior and restore 444 order. When an earlier packet in the Src sequence is lost, IPDV will 445 necessarily be undefined for adjacent packets, and Late Time may 446 provide the only way to evaluate the usefulness of a packet. 448 In the case of de-jitter buffers, there are circumstances where the 449 receiver employs loss concealment at the intended play-out time of a 450 late packet. However, if this packet arrives out of order, the Late 451 Time determines whether the packet is still useful. IPDV no longer 452 applies, because the receiver establishes a new play-out schedule 453 with additional buffer delay to accommodate similar events in the 454 future - this requires very minimal processing. 456 When packets in the stream have variable sizes, it may be most 457 useful to characterize Offset in terms of the payload size(s) of 458 stored packets (using byte stream numbering). 460 4.4 Gaps between multiple Reordering Discontinuities 462 4.4.1 Metric Name: 464 Type-P-packet-Reordering-Gap-Stream 466 4.4.2 Parameters: 468 No new parameters. 470 4.4.3 Definition of Reordering Discontinuity: 472 All reordered packets are associated with a packet at a reordering 473 discontinuity, defined as the in-order packet arrival s[j] at the 474 minimum value of j (1<=j s[i]. 476 Recall that i - e = min(j). Subsequent reordered packets may be 477 associated with the same s[j], or with a different discontinuity. 478 This definition is used in the definition of the Reordering Gap, 479 below. 481 4.4.4 Definition of Reordering Gap: 483 A reordering gap is the distance between successive reordering 484 discontinuities. Type-P-packet-Reordering-Gap-Stream assigns a value 485 to (all) packets in a stream. 487 If: 489 The packet s[j'] is found to be a reordering discontinuity, based 490 on the arrival of reordered packet s[i'] with extent e', and 492 an earlier reordering discontinuity s[j], based on the arrival of 493 reordered packet s[i] with extent e was already detected, and 495 i' > i, and 497 there are no reordering discontinuities between j and j', 499 then the Reordering Gap for packet s[j'] is the difference between 500 the arrival positions the reordering discontinuities, as shown 501 below: 503 Gap(j') = (j') - (j) 505 Otherwise: 507 The Type-P-packet-Reordering-Gap-Stream for the packet is 0. 509 Gaps may also be expressed in time: 511 GapTime(j') = DstTime(j') - DstTime(j) 513 4.4.5 Discussion 515 When separate reordering discontinuities can be distinguished, then 516 a count may also be reported (along with the discontinuity 517 description, such as the number of reordered packets associated with 518 that discontinuity and their extents and offsets). The Gaps between 519 a sample's reordering discontinuities may be expressed as a 520 histogram, to easily summarize the frequency of various gaps. 521 Reporting the mode, average, range, etc. may also summarize the 522 distributions. 524 The Gap metric may help to correlate the frequency of reordering 525 discontinuities with their cause. 527 4.5 Reordering-free Runs 529 This section defines a metric based on a count of consecutive 530 packets between reordered packets. 532 4.5.1 Metric Name: 534 Type-P-packet-Reordering-Free-Run-Stream 536 4.5.2 Parameters: 538 No new parameters. 540 4.5.3 Definition: 542 As packets in a sample arrive at the Destination, the count of 543 packets to the next reordered packet is a Reordering-Free run. Note 544 that the minimum run-length is one according to this definition. A 545 pseudo code example follows: 547 r = 0; /* r is the run counter */ 548 n = 0; /* n is the number of runs */ 549 a = 0; /* a is the accumulator of in order packets */ 550 p = 0; /* p is the number of packets */ 551 q = 0; /* q is the squared sum of the run counters */ 553 while(packets arrive with sequence number s) 554 { 555 P++; 556 if (s >= NextExp) /* s is in-order */ 557 then r++; 558 a++; 559 else /* s is reordered */ 560 q+= r*r; 561 r = 1; 562 n++; 563 } 565 Each arrival of a reordered packet yields a new count in the Run 566 vector. Long runs accompany periods where order was maintained, 567 while short runs indicate frequent, or multi-packet reordering. 569 4.5.4 Discussion: 571 Each in-order arrival increments the run counter and the accumulator 572 of in order packets, each reordered packet resets the run counter 573 after adding it to the accumulator. 575 The percent of packets in order is 100*a/p 577 The average in order run length is a/n 579 The q counter gives an indication of variation of the in order runs 580 from the average by comparing q/a to a/n ((q/a)/(a/n)) 582 For example for 36 packets with 3 runs of 11 in-order packets we 583 have: 584 p = 36 585 n = 3 586 a = 33 587 q = 3 * (11*11) = 363 588 ave io = 11 589 q/a = 11 590 (q/a)/ave = 1.0 592 For 36 packets with 3 runs, 2 of length 1 and one of length 31 593 p = 36 594 n = 3 595 a = 33 596 q = 1 + 1 + 961 = 963 597 ave io = 11 598 q/a = 29.18 599 (q/a)/ave = 2.65 601 5. Metric Related to Receiver Assessment 603 5.1 A TCP-Relevant Metric 605 5.1.1 Metric Name: 607 Type-P-packet-n-Reordering-Stream 609 5.1.2 Parameter Notation: 611 Let n be a positive integer (a parameter). Let k be a positive 612 integer equal to the number of packets sent (sample size). Let l be 613 a non-negative integer representing the number of packets that were 614 received out of the k packets sent. (Note that there is no 615 relationship between k and l: on one hand, losses can make l less 616 than k; on the other hand, duplicates can make l greater than k.) 617 Assign each sent packet a sequence number, 1 to k, in order of 618 packet emission. 620 Let s[1], s[2], ..., s[l] be the original sequence numbers of the 621 received packets, in the order of arrival. 623 5.1.3 Definitions 625 Definition 1: Received packet number i (n < i <= l), with source 626 sequence number s[i], is n-reordered if and only if for all j such 627 that i-n <= j < i, s[j] > s[i]. 629 Claim: If by this definition, a packet's reordering is n and 0 < n' 630 < n, then the packet is also reordered to the n' extent. 632 Note: This definition is illustrated by C code in Appendix A. It 633 determines the n-reordering for a value of n=3 (when actually 634 writing applications that would report the metric, one would 635 probably report it for several values of n, such as 1, 2, 3, 4 -- 636 and maybe a few more consecutive values). 637 This definition does not assign an n to all reordered packets as 638 defined by the singleton metric, in particular when blocks of 639 successive packets are reordered. (In the arrival sequence 640 s={1,2,3,7,8,9,4,5,6}, packets 4, 5, and 6 are reordered, but only 4 641 is n-reordered, with n=3.) 643 Definition 2: The degree of n-reordering of the sample is m/l. 645 Definition 3: The degree of "monotonic reordering" of the sample is 646 its degree of 1-reordering. 648 Definition 4: A sample is said to have no reordering if its degree 649 of n-reordering is 0. 651 5.1.4 Discussion: 653 The degree of n-reordering may be expressed as a percentage, in 654 which case the number from definition 2 is multiplied by 100. 656 Knowledge of n-reordering is particularly useful for determining the 657 portion of reordered packets that can or cannot be restored to order 658 in a typical TCP receiver buffer based on their arrival order alone 659 (and without the aid of retransmission). 661 Important special cases are n=1 and n=3: 663 - For n=1, absence of 1-reordering means the sequence numbers that 664 the receiver sees are monotonically increasing with respect to the 665 previous arriving packet. 667 - For n=3, a NewReno TCP sender would retransmit 1 packet in 668 response to an instance of 3-reordering and therefore consider this 669 packet lost for the purposes of congestion control (the sender will 670 half its congestion window). Detecting instances of 3-reordering is 671 useful for determining the portion of reordered packets that are in 672 fact as good as lost. 674 A sample's n-reordering may be expressed as a histogram, to 675 summarize the frequency for each value of n. 677 We note that the definition of n-reordering cannot predict the exact 678 number of packets unnecessarily retransmitted by a TCP sender under 679 some circumstances, such as cases with closely-spaced reordered 680 singletons. The definition is less complicated than a TCP 681 implementation where both time and position influence the sender's 682 behavior. 684 A packet's n-reordering is sometimes equal to its reordering extent, 685 e. n-reordering is different in the following ways: 687 1. n is a count of *adjacent* early packets. 689 2. Some reordered packets may not be n-reordered, but will have e 690 (see the examples). 692 6. Measurement Issues 694 The results of tests will be dependent on the time interval between 695 measurement packets (both at the Src, and during transport where 696 spacing may change). Clearly, packets launched infrequently (e.g., 697 1 per 10 seconds) are unlikely to be reordered. 699 Test streams may prefer to use a periodic sending interval so that a 700 known temporal bias is maintained, also bringing simplified results 701 analysis (as described in RFC 3432 [13]). In this case, the periodic 702 sending interval should be chosen to reproduce the closest Src 703 packet spacing expected. Of course, packet spacing is likely to vary 704 as the stream traverses the test path. 705 <<<, the received 815 packets are represented as: 817 \/ 818 s = 1, 2, 3, 5, 6, 7, 8, 4, 9, 10 819 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 820 /\ 821 when j=7, 8 > 4, so the reordering extent is 1 or more. 822 when j=6, 7 > 4, so the reordering extent is 2 or more. 823 when j=5, 6 > 4, so the reordering extent is 3 or more. 824 when j=4, 5 > 4, so the reordering extent is 4 or more. 825 when j=3, but 3 < 4, and 4 is the maximum extent, e=4 (assuming 826 there are no earlier sequence discontinuities, as in this example). 828 Further, we can compute the Late Time (210-148=62ms using DstTime) 829 compared to Packet 5's arrival. If the receiver has a de-jitter 830 buffer that holds more than 4 packets, or at least 62 ms storage, 831 Packet 4 may be useful. Note that 1-way delay and IPDV also indicate 832 unusual behavior for Packet 4. 834 If all packets contained 100 byte payloads, then Byte Offset is 835 equal to 400 bytes. 837 Following the definitions of section 5.1, Packet 4 is defined to be 838 4-reordered. 840 Table 2 Example with Packets 5 and 6 Reordered, 841 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10 842 s Src Dst Dst Byte Late 843 @Dst NextExp Time Time Delay IPDV Order Offset Time 844 1 1 0 68 68 1 845 2 2 20 88 68 0 2 846 3 3 40 108 68 0 3 847 4 4 60 128 68 0 4 848 7 5 120 188 68 -22 5 849 5 8 80 189 109 41 6 100 1 850 6 8 100 190 90 -19 7 100 2 851 8 8 140 208 68 0 8 852 9 9 160 228 68 0 9 853 10 10 180 248 68 0 10 855 Table 2 shows a case where Packets 5 and 6 arrive just behind Packet 856 7, so both 5 and 6 are reordered. The Late times (189-188=1, 190- 857 188=2) are small. 859 Using the notation , the received 860 packets are represented as: 862 \/ \/ 863 s = 1, 2, 3, 4, 7, 5, 6, 8, 9, 10 864 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 865 /\ /\ 867 Considering Packet 5 first: 869 when j=5, 7 > 5, so the reordering extent is 1 or more. 870 when j=4, but 4 < 5, so 1 is its maximum extent, and e=1. 872 Considering Packet 6 next: 873 when j=6, 5 < 6, the extent is not yet defined. 874 when j=5, 7 > 6, so the reordering extent is i-j=2 or more. 875 when j=4, 4 < 6, and we find 2 is its maximum extent, and e=2. 877 We can also associate each of these reordered packets with a 878 reordering discontinuity. We find the minimum j=5 (for both packets) 879 according to Section 4.2.4. So Packet 6 is associated with the same 880 reordering discontinuity as Packet 5, at Packet 7. 882 Following the definitions of section 5.1, Packet 5 is defined to be 883 1-reordered, but Packet 6 is not qualified n-reordered. 885 A hypothetical sender/receiver pair may retransmit Packet 5 886 unnecessarily, since it is 1-reordered (in agreement with the 887 singleton metric). Though Packet 6 may not be unnecessarily 888 retransmitted, the receiver cannot advance Packet 7 to the higher 889 layers until after Packet 6 arrives. Therefore, the singleton metric 890 correctly determined that Packet 6 is reordered. 892 Table 3 Example with Packets 4, 5, and 6 reordered 893 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11 894 s Src Dst Dst Byte Late 895 @Dst NextExp Time Time Delay IPDV Order Offset Time 896 1 1 0 68 68 1 897 2 2 20 88 68 0 2 898 3 3 40 108 68 0 3 899 7 4 120 188 68 -88 4 900 8 8 140 208 68 0 5 901 9 9 160 228 68 0 6 902 10 10 180 248 68 0 7 903 4 11 60 250 190 122 8 400 62 904 5 11 80 252 172 -18 9 400 64 905 6 11 100 256 156 -16 10 400 68 906 11 11 200 268 68 0 11 908 The case in Table 3 is where three packets in sequence have long 909 transit times (Packets with s = 4,5,and 6). Delay, Late time, and 910 Byte Offset capture this very well, and indicate variation in 911 reordering extent, while IPDV indicates that the spacing between 912 packets 4,5,and 6 has changed. 914 The histogram of Reordering extents (e) would be: 916 Bin 1 2 3 4 5 6 7 917 Frequency 0 0 0 1 1 1 0 918 Using the notation , the received 919 packets are represented as: 921 s = 1, 2, 3, 7, 8, 9,10, 4, 5, 6, 11 922 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11 924 We first calculate the n-reordering. Considering Packet 4 first: 925 when n=1, 7<=j<8, and 10> 4, so the packet is 1-reordered. 926 when n=2, 6<=j<8, and 9 > 4, so the packet is 2-reordered. 927 when n=3, 5<=j<8, and 8 > 4, so the packet is 3-reordered. 928 when n=4, 4<=j<8, and 7 > 4, so the packet is 4-reordered. 929 when n=5, 3<=j<8, but 3 < 4, and 4 is the maximum n-reordering. 931 Considering packet 5[9] next: 932 when n=1, 8<=j<9, but 4 < 5, so the packet at i=9 is not qualified 933 as n-reordered. We find the same to for Packet 6. 935 We now consider whether reordered Packets 5 and 6 are associated 936 with the same reordering discontinuity as Packet 4. Using the test 937 of Section 4.2.4, Definition 2, we find that the minimum j=4 for all 938 three packets. They are all associated with the reordering 939 discontinuity at Packet 7. 941 This example shows again that the n-reordering definition identifies 942 a single Packet (4) with a sufficient degree of reordering to result 943 in one unnecessary packet retransmission by the New Reno TCP sender. 944 Also, the reordered arrival of Packets 5 and 6 will allow the 945 receiver process to pass Packets 7 through 10 up the protocol stack 946 (the singleton metric indicates 5 and 6 are reordered, and they are 947 all associated with a single reordering discontinuity). 949 Table 4 Example with Packets Multiple Reordering Discontinuities 950 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 952 Discontinuity Discontinuity 953 |---------Gap---------| 954 s = 1, 2, 3, 6, 7, 4, 5, 8, 9, 10, 12, 13, 11, 14, 15, 16 955 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 957 r = 1, 2, 3, 4, 5, 1, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, ... 958 n = 1 2 3 959 end r counts = 5 1 6 961 Packet 4 has extent e=2, Packet 5 has extent e=3, and Packet 11 has 962 e=2. There are two different reordering discontinuities, one at 963 Packet 6 (where j=4) and one at Packet 12 (where j'=11). 965 According to the definition of Reordering Gap 966 Gap(j') = (j') - (j) 967 Gap(11) = (11) - (4) = 7 968 We also have three reordering-free runs of lengths 5, 1, and 6. 970 The differences between these two multiple-event metrics are evident 971 here. Gaps are the distance between sequence discontinuities that 972 are subsequently defined as reordering discontinuities, while 973 reordering-free runs are capture the distance between reordered 974 packets. 976 8. Security Considerations 978 8.1 Denial of Service Attacks 980 This metric requires a stream of packets sent from one host (Src) to 981 another host (Dst) through intervening networks. This method could 982 be abused for denial of service attacks directed at Dst and/or the 983 intervening network(s). 985 Administrators of Src, Dst, and the intervening network(s) should 986 establish bilateral or multi-lateral agreements regarding the 987 timing, size, and frequency of collection of sample metrics. Use of 988 this method in excess of the terms agreed between the participants 989 may be cause for immediate rejection or discard of packets or other 990 escalation procedures defined between the affected parties. 992 8.2 User data confidentiality 994 Active use of this method generates packets for a sample, rather 995 than taking samples based on user data, and does not threaten user 996 data confidentiality. Passive measurement must restrict attention to 997 the headers of interest. Since user payloads may be temporarily 998 stored for length analysis, suitable precautions MUST be taken to 999 keep this information safe and confidential. 1001 8.3 Interference with the metric 1003 It may be possible to identify that a certain packet or stream of 1004 packets is part of a sample. With that knowledge at Dst and/or the 1005 intervening networks, it is possible to change the processing of the 1006 packets (e.g. increasing or decreasing delay) that may distort the 1007 measured performance. It may also be possible to generate 1008 additional packets that appear to be part of the sample metric. 1009 These additional packets are likely to perturb the results of the 1010 sample measurement. 1012 To discourage the kind of interference mentioned above, packet 1013 interference checks, such as cryptographic hash, may be used. 1015 9. IANA Considerations 1017 Since this metric does not define a protocol or well-known values, 1018 there are no IANA considerations in this memo. 1020 10. References 1022 1 Bradner, S., "The Internet Standards Process -- Revision 3", BCP 1023 9, RFC 2026, October 1996. 1025 2 Bradner, S., "Key words for use in RFCs to Indicate Requirement 1026 Levels", RFC 2119, March 1997. 1028 3 Paxson, V., Almes, G., Mahdavi, J., and Mathis, M., "Framework 1029 for IP Performance Metrics", RFC 2330, May 1998. 1031 4 V.Paxson, "Measurements and Analysis of End-to-End Internet 1032 Dynamics," Ph.D. dissertation, U.C. Berkeley, 1997, 1033 ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz. 1035 5 Postel, J., "Transmission Control Protocol", STD 7, RFC 793, 1036 September 1981. 1037 Obtain via: http://www.rfc-editor.org/rfc/rfc793.txt 1039 6 L.Ciavattone and A.Morton, "Out-of-Sequence Packet Parameter 1040 Definition (for Y.1540)", Contribution number T1A1.3/2000-047, 1041 October 30, 2000. ftp://ftp.t1.org/pub/t1a1/2000-A13/0a130470.doc 1043 7 J.C.R.Bennett, C.Partridge, and N.Shectman, "Packet Reordering is 1044 Not Pathological Network Behavior," IEEE/ACM Transactions on 1045 Networking, vol.7, no.6, pp.789-798, December 1999. 1047 8 D.Loguinov and H.Radha, "Measurement Study of Low-bitrate 1048 Internet Video Streaming", Proceedings of the ACM SIGCOMM 1049 Internet Measurement Workshop 2001 November 1-2, 2001, San 1050 Francisco, USA. 1052 9 J.Bellardo and S.Savage, "Measuring Packet Reordering," 1053 Proceedings of the ACM SIGCOMM Internet Measurement Workshop 1054 2002, November 6-8, Marseille, France. 1056 10 S.Jaiswal et al., "Measurement and Classification of Out-of- 1057 Sequence Packets in a Tier-1 IP Backbone," Proceedings of the ACM 1058 SIGCOMM Internet Measurement Workshop 2002, November 6-8, 1059 Marseille, France. 1061 11 L.Ciavattone, A.Morton, and G.Ramachandran, "Standardized Active 1062 Measurements on a Tier 1 IP Backbone," IEEE Communications Mag., 1063 pp 90-97, June 2003. 1064 12 Demichelis, C., and Chimento, P., "IP Packet Delay Variation 1065 Metric for IP Performance Metrics (IPPM)", RFC 3393, November 1066 2002. 1068 13 Raisanen, V., Grotefeld, G., and Morton, A., "Network performance 1069 measurement with periodic streams", RFC 3432, November 2002. 1071 12. Acknowledgments 1073 The authors would like to acknowledge many helpful discussions with 1074 Matt Mathis, Jon Bennett, and Matt Zekauskas. We gratefully 1075 acknowledge the foundation laid by the authors of the IP performance 1076 Framework [3]. 1078 13. Appendix A (informative) 1080 Two example c-code implementations of reordering definitions follow: 1082 Example 1 n-reordering ============================================ 1084 #include 1086 #define MAX_N 100 1088 #define min(a, b) ((a) < (b)? (a): (b)) 1089 #define loop(x) ((x) >= 0? x: x + MAX_N) 1091 /* 1092 * Read new sequence number and return it. Return a sentinel value 1093 of EOF 1094 * (at least once) when there are no more sequence numbers. In this 1095 example, 1096 * the sequence numbers come from stdin; in an actual test, they 1097 would come 1098 * from the network. 1099 */ 1100 int 1101 read_sequence_number() 1102 { 1103 int res, rc; 1104 rc = scanf("%d\n", &res); 1105 if (rc == 1) return res; 1106 else return EOF; 1107 } 1109 int 1110 main() 1111 { 1112 int m[MAX_N]; /* We have m[j-1] == number 1113 of 1114 * j-reordered packets. */ 1115 int ring[MAX_N]; /* Last sequence numbers 1116 seen. */ 1117 int r = 0; /* Ring pointer for next 1118 write. */ 1119 int l = 0; /* Number of sequence 1120 numbers read. */ 1121 int s; /* Last sequence number 1122 read. */ 1123 int j; 1125 for (j = 0; j < MAX_N; j++) m[j] = 0; 1126 for (; (s = read_sequence_number()) != EOF; l++, r = (r+1) % 1127 MAX_N) { 1128 for (j=0; j 1145 #define MAX_N 100 1146 #define min(a, b) ((a) < (b)? (a): (b)) 1147 #define loop(x) ((x) >= 0? x: x + MAX_N) 1149 /* Global counters */ 1150 int receive_packets=0; /* number of recieved */ 1151 int reorder_packets=0; /* number of reordered packets */ 1153 /* function to test if current packet has been reordered 1154 * returns 0 = not reordered 1155 * 1 = reordered 1156 */ 1157 int testorder1(int seqnum) // Al 1158 { 1159 static int NextExp = 1; 1160 int iReturn = 0; 1162 if (seqnum >= NextExp) { 1163 NextExp = seqnum+1; 1164 } else { 1165 iReturn = 1; 1166 } 1167 return iReturn; 1168 } 1170 int testorder2(int seqnum) // Stanislav 1171 { 1172 static int ring[MAX_N]; /* Last sequence numbers 1173 seen. */ 1174 static int r = 0; /* Ring pointer for next write. 1175 */ 1176 int l = 0; /* Number of sequence 1177 numbers read. */ 1178 int j; 1179 int iReturn = 0; 1181 l++; 1182 r = (r+1) % MAX_N; 1183 for (j=0; j= NextExp, 1248 * AND the fragment offset FragOffset >= NextExpFrag 1250 However, it more efficient to define reordered conditions exactly, 1251 and designate Type-P-Reordered as False otherwise. 1253 The value of Type-P-Reordered is defined as True (the packet is 1254 reordered) under the conditions below. In these cases, the NextExp 1255 value does not change. 1257 Case 1: if s < NextExp 1259 Case 2: if s < FragSeq# 1261 Case 3: if s>= NextExp AND s = FragSeq# AND FragOffset < NextExpFrag 1263 This definition can also be illustrated in pseudo-code. A draft 1264 version of the code follows, and some simplification may be 1265 possible. A challenging aspect surrounds the housekeeping for the 1266 new parameters. 1268 NextExp=0; 1269 NextExpFrag=0; 1270 FragSeq#=0; 1272 while(packets arrive with s, MoreFrag, FragOffset) 1273 { 1274 if (s>=NextExp AND MoreFrag==0 AND s>=FragSeq#){ 1275 /* a normal packet or last frag of an in-order packet arrived 1276 */ 1277 NextExp = s+1; 1278 FragSeq# = 0; 1279 NextExpFrag = 0; 1280 Reordering = False; 1281 } 1282 if (s>=NextExp AND MoreFrag==1 AND s>FragSeq#>=0){ 1283 /* a fragment of a new packet arrived, possibly with a 1284 higher sequence number than the current fragmented packet */ 1285 FragSeq# = s; 1286 NextExpFrag = FragOffset+1; 1287 Reordering = False; 1288 } 1289 if (s>=NextExp AND MoreFrag==1 AND s==FragSeq#){ 1290 /* a fragment of the "current packet s" arrived */ 1291 if (FragOffset >= NextExpFrag){ 1292 NextExpFrag = FragOffset+1; 1293 Reordering = False; 1294 } 1295 else{ 1296 Reordering = True; /* fragment reordered */ 1297 } 1298 } 1299 if (s>=NextExp AND MoreFrag==1 AND s < FragSeq#){ 1300 /* case where a late fragment arrived */ 1301 Reordering = True; 1302 } 1303 else { /* when s < NextExp, or MoreFrag==0 AND s < FragSeq# */ 1304 Reordering = True; 1305 } 1306 } 1308 A working version of the code would include a check to ensure that 1309 all fragments of a packet arrive before using the Reordered status 1310 further, such as in sample metrics. 1312 13.3 Notes on Sample Metrics 1314 All fragments with the same Source Sequence Number are assigned the 1315 same Source Time. 1317 Evaluation with byte stream numbering may be simplified if the 1318 fragment offset is simply added to the SourceByte of the first 1319 packet (with fragment offset = 0), keeping the 8 octet units of the 1320 offset in mind. 1322 14. Author's Addresses 1324 Al Morton 1325 AT&T Labs 1326 Room D3 - 3C06 1327 200 Laurel Ave. South 1328 Middletown, NJ 07748 USA 1329 Phone +1 732 420 1571 1330 EMail: 1332 Len Ciavattone 1333 AT&T Labs 1334 Room C4 - 2B29 1335 200 Laurel Ave. South 1336 Middletown, NJ 07748 USA 1337 Phone +1 732 420 1239 1338 EMail: 1340 Gomathi Ramachandran 1341 AT&T Labs 1342 Room C4 - 3D22 1343 200 Laurel Ave. South 1344 Middletown, NJ 07748 USA 1345 Phone +1 732 420 2353 1346 EMail: 1348 Stanislav Shalunov 1349 Internet2 1350 200 Business Park Drive, Suite 307 1351 Armonk, NY 10504 1352 Phone: + 1 914 765 1182 1353 EMail: 1355 Jerry Perser 1356 Consultant 1357 Calabasas, CA 91302 USA 1358 Phone: + 1 1359 EMail: 1361 Full Copyright Statement 1363 "Copyright (C) The Internet Society (date). All Rights Reserved. 1364 This document and translations of it may be copied and furnished to 1365 others, and derivative works that comment on or otherwise explain it 1366 or assist in its implmentation may be prepared, copied, published 1367 and distributed, in whole or in part, without restriction of any 1368 kind, provided that the above copyright notice and this paragraph 1369 are included on all such copies and derivative works. However, this 1370 document itself may not be modified in any way, such as by removing 1371 the copyright notice or references to the Internet Society or other 1372 Internet organizations, except as needed for the purpose of 1373 developing Internet standards in which case the procedures for 1374 copyrights defined in the Internet Standards process must be 1375 followed, or as required to translate it into languages other than 1376 English. 1378 The limited permissions granted above are perpetual and will not be 1379 revoked by the Internet Society or its successors or assigns. 1381 This document and the information contained herein is provided on an 1382 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 1383 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 1384 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 1385 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 1386 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.