idnits 2.17.1 draft-ietf-ippm-reordering-02.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 452 has weird spacing: '...oadSize where...' == Line 935 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 720 looks like a reference -- Missing reference section? '2' on line 298 looks like a reference -- Missing reference section? '3' on line 838 looks like a reference -- Missing reference section? '4' on line 741 looks like a reference -- Missing reference section? '5' on line 689 looks like a reference -- Missing reference section? '6' on line 684 looks like a reference -- Missing reference section? '7' on line 690 looks like a reference -- Missing reference section? '9' on line 740 looks like a reference -- Missing reference section? '10' on line 741 looks like a reference -- Missing reference section? '8' on line 741 looks like a reference Summary: 5 errors (**), 0 flaws (~~), 2 warnings (==), 13 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 Spirent 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 a simple metric to determine if a network has 34 maintained packet order. It provides motivations for the new metric, 35 suggests a metric definition, and discusses the issues associated 36 with measurement. The memo includes sample metrics to quantify the 37 extent of reordering in several useful dimensions. Some examples of 38 evaluation using the various sample metrics are included. 40 1. Conventions used in this document 42 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 43 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 44 document are to be interpreted as described in RFC 2119 [2]. 45 Although RFC 2119 was written with protocols in mind, the key words 46 are used in this document for similar reasons. They are used to 47 ensure the results of measurements from two different 48 implementations are comparable, and to note instances when an 49 implementation could perturb the network. 51 2. Introduction 53 Ordered delivery is a property of successful packet transfer 54 attempts, where the packet sequence ascends for each arriving packet 55 and there are no backward steps. 57 An explicit sequence number, such as an incrementing message number 58 or the packet sending time carried in each packet, establishes the 59 Source Sequence. 61 The presence of reordering at the Destination is based on arrival 62 order. 64 This metric is consistent with RFC 2330 [3], and classifies arriving 65 packets with sequence numbers smaller than their predecessors as 66 out-of-order, or reordered. For example, if arriving packets are 67 numbered 1,2,4,5,3, then packet 3 is reordered. This is equivalent 68 to Paxon's reordering definition in [4], where "late" packets were 69 declared reordered. The alternative is to emphasize "premature" 70 packets instead (4 and 5 in the example), but only the arrival of 71 packet 3 distinguishes this circumstance from packet loss. Focusing 72 attention on late packets allows us to maintain orthogonality with 73 the packet loss metric. The metric's construction is very similar to 74 the sequence space validation for received segments in RFC793 [5]. 75 Earlier work to define ordered delivery includes [6], [7], [8 and 76 more ???. 78 2.1 Motivation 80 A reordering metric is relevant for most applications, especially 81 when assessing network support for Real-Time media streams. The 82 extent of reordering may be sufficient to cause a received packet to 83 be discarded by functions above the IP layer. 85 Packet order is not expected to change during transfer, but several 86 specific path characteristics can cause their order to change. 88 Examples are: 89 * When two paths, one with slightly longer transfer time, support a 90 single packet stream or flow, then packets traversing the longer 91 path may arrive out-of-order. Multiple paths may be used to 92 achieve load balancing, or may arise from route instability. 93 * To increase capacity, a network device designed with multiple 94 processors serving a single port may reorder as a byproduct. 95 * A layer 2 retransmission protocol that compensates for an error- 96 prone link may cause packet reordering. 97 * If for any reason, the packets in a buffer are not serviced in the 98 order of their arrival, their order will change. 99 * If packets in a flow are assigned to multiple buffers (following 100 evaluation of traffic characteristics, for example), and the 101 buffers have different occupations and/or service rates, then 102 order will likely change. 104 The ability to restore order at the destination will likely have 105 finite limits. Practical hosts have receiver buffers with finite 106 size in terms of packets, bytes, or time (such as de-jitter 107 buffers). Once the initial determination of reordering is made, it 108 is useful to quantify the extent of reordering, or lateness, in all 109 meaningful dimensions. 111 2.2 Goals and Objectives 113 The definitions below intend to satisfy the goals of: 114 1. Determining whether or not packet order is maintained. 115 2. Quantifying the extent (achieving this second goal requires 116 assumptions of upper layer functions and capabilities to 117 restore order, and therefore several solutions). 119 Reordering Metrics MUST: 121 + be relevant to one or more known applications 122 + be computable "on the fly" 123 + work with Poisson and Periodic test streams 124 + work even if the stream has duplicate or lost packets 126 Reordering Metrics SHOULD: 128 + have concatenating results for segments measured separately 129 + have simplicity for easy consumption and understanding 130 + have relevance to TCP performance 131 + have relevance to Real-time application performance 133 3. An Ordered Arrival Singleton Metric 135 The IPPM framework RFC 2330 [3] gives the definitions of singletons, 136 samples, and statistics. 138 The evaluation of packet order requires several supporting concepts. 139 The first is a sequence number applied to packets at the source to 140 uniquely identify the order of packet transmission. The sequence 141 number may be established by a simple message number, a byte stream 142 number, or it may be the actual time when each packet departs from 143 the Src. 145 The second supporting concept is a stored value which is the "next 146 expected" packet number. Under normal conditions, the value of Next 147 Expected (NextExp) is the sequence number of the previous packet 148 (plus 1 for message numbering). In byte stream numbering, NextExp 149 is a value 1 byte greater than the last in-order packet sequence 150 number + payload. If Src time is used as the sequence number, 151 NextExp is the Src time from the last in-order packet + 1 clock 152 tick. 154 Each packet within a packet stream can be evaluated for its order 155 singleton metric. 157 3.1 Metric Name: 159 Type-P-Non-Reversing-Order 161 3.2 Metric Parameters: 163 + Src, the IP address of a host 165 + Dst, the IP address of a host 167 + SrcTime, the time of packet emission from the Src (or wire time) 169 + s, the packet sequence number applied at the Src, in units of 170 messages. 172 + SrcByte, the packet sequence number applied at the Src, in units 173 of payload bytes. 175 + NextExp, the Next Expected Sequence number at the Dst, in units 176 of messages, time, or bytes. 178 + PayloadSize, the number of bytes contained in the information 179 field and referred to when the SrcByte sequence is based on byte 180 transfer. 182 3.3 Definition: 184 In-order packets have sequence numbers (or Src times) greater than 185 or equal to the value of Next Expected. Each new in-order packet 186 will increase the Next Expected (typically by 1 for message 187 numbering, or the payload size plus 1 for byte numbering). The Next 188 Expected value cannot decrease, thereby specifying non-reversing 189 order as the basis to identify reordered packets. 191 A reordered packet outcome occurs when a single IP packet at the Dst 192 Measurement Point results in the following: 193 The packet has a Src sequence number lower than the Next Expected 194 (NextExp), and therefore the packet is reordered. The Next Expected 195 value does not change on the arrival of this packet. 197 This definition can also be specified in pseudo-code. 198 On successful arrival of a packet with sequence number s: 199 if s >= NextExp, /* s is in-order */ 200 then 201 NextExp = s + PayloadSize + 1; 202 else /* when s < NextExp */ 203 designate packet s as reordered; 205 The sequence number s may be replaced by SrcTime or SrcByte. When 206 using s (message-based sequence numbering) or Src time, 207 PayloadSize=0. 209 3.4 Discussion 211 Any arriving packet bearing a sequence number from the sequence that 212 establishes the Next Expected value can be evaluated to determine if 213 it is in-order, or reordered, based on a previous packet's arrival. 214 In the case where Next Expected is Undefined (because the arriving 215 packet is the first successful transfer), the packet is designated 216 in-order. 218 If duplicate packets (multiple non-corrupt copies) arrive at the 219 destination, they MUST be noted and only the first to arrive is 220 considered for further analysis (additional copies would be declared 221 reordered according to the definition above). This requirement has 222 the same storage requirements as earlier IPPM metrics, and follows 223 the precedent of RFC 2679. 225 Packets with s > NextExp are a special case of in-order delivery. 226 This condition indicates a sequence discontinuity, either because of 227 packet loss or reordering. Reordered packets must arrive for the 228 sequence discontinuity to be part of a reordering event (defined in 229 the next section). Discontinuities are easiest to detect with 230 message numbering or payload byte numbering where payload size is 231 constant, and may be possible with Periodic Streams and Src Time 232 numbering. 234 4. Sample Metrics 236 In this section, we define metrics applicable to a sample of packets 237 from a single Src sequence number system. We begin with a simple 238 ratio metric indicating the reordered portion of the sample. When 239 this ratio is zero, no further reordering metrics are needed for 240 that sample. 242 When reordering occurs, it is highly desirable to assert the degree 243 to which a packet is out-of-order, or reordered with respect to a 244 sample of packets. This section defines several metrics that 245 quantify the extent of reordering in various units of measure. Each 246 "extent" metric highlights a relevant application. 248 4.1 Reordered Packet Ratio 250 4.1.1 Metric Name: 252 Type-P-Reordered-Ratio-Poisson/Periodic-Stream 254 4.1.2 Metric Parameters: 256 The parameter set includes Type-P-Non-Reversing-Order singleton 257 parameters, the parameters unique to Poisson or Periodic Streams, 258 plus the following: 260 + T0, a start time 262 + Tf, an end time 264 + dT, a waiting time for each packet to arrive 266 4.1.3 Definition: 268 For the packets arriving successfully between T0 and Tf+dT, the 269 ratio of reordered packets in the sample is 271 (Total of Reordered packets) / (Total packets received) 273 This fraction may be expressed as a percentage (multiply by 100%). 274 Note that in the case of duplicate packets, only the first copy is 275 used. 277 4.2 Reordering Events and their Extent 278 Note: This section is expected to evolve further as we integrate the 279 various metrics of reordering extent (n-reordering and other 280 distance metrics used in earlier drafts). The co-authors are not yet 281 satisfied with all aspects of this section, and comments are 282 welcome. 284 4.2.1 Metric Name: 286 Type-P-packet-n-Reordering-Event-Poisson/Periodic-Stream 288 4.2.2 Parameter Notation: 290 Let n be a positive integer (a parameter). Let k be a positive 291 integer (sample size, the number of packets sent). Let l be a non- 292 negative integer representing the number of packets that were 293 received out of the k packets sent. (Note that there is no 294 relationship between k and l: on one hand, losses can make l less 295 than k; on the other hand, duplicates can make l greater than k.) 296 Assign each sent packet a sequence number, 1 to k. 298 Let s[1], s[2], ..., s[l] be the original sequence numbers of the 299 received packets, in the order of arrival. 301 4.2.3 Definition 1: 303 Received packet number i (n < i <= l), with Src sequence number s 304 (s[i]), is reordered to the extent n if and only if for all j such 305 that i-n <= j < i we have s[j] > s[i]. 307 Claim: If by this definition, the extent of a packet's reordering is 308 n and 0 < n' < n, then the packet is also reordered to the n' 309 extent. 311 Note: This definition is illustrated by C code in Appendix A. It 312 determines the presence of n-reordering events for a particular 313 value of n (when actually writing applications that would report the 314 metric, one would probably report it for several values of n, such 315 as 1, 2, 3, 4 -- and maybe a few more consecutive values). 316 Also, this definition does not assign an extent to all reordered 317 packets as defined by the singleton metric, in particular when 318 blocks of successive packets are reordered. (In the arrival sequence 319 s={1,2,3,7,8,9,4,5,6}, packets 4, 5, and 6 are reordered, but only 4 320 is assigned a reordering extent according to Definition 1.) All 321 reordered packets are assigned a reordering extent by associating 322 them with a specific reordering event, as defined below. 324 4.2.4 Definition 2: 325 Note: The intent of this section is to assign a reordering extent to 326 all reordered packets, not just the ones identified by Definition 1. 327 This definition is new in this version and needs more study. 329 A packet s[i] that satisfies Definition 1 constitutes an n- 330 Reordering Event with the following characteristics: 332 1. The maximum value of n that satisfies Definition 1 is the extent 333 of the reordering event. (Extent n is assigned to all packets 334 associated with this event in part 3 below.) 336 2. The in-order packet arrival defined as beginning the event 337 (having indicated a sequence discontinuity) is s[j] for j that 338 satisfies the following: 340 min{j|1<=j s[i] 342 Typically i-n=j. This aspect of a reordering event is used later in 343 the definition of the gap between successive events. 345 3. The arrival of any subsequent reordered packets with sequence 346 number s meeting the following condition: 348 s[j] > s[*] > s[i], or 349 (s at beginning of event) > s > (lowest s in the reordering event) 351 are associated with the reordering event first identified by s[i], 352 the sequence discontinuity that starts the event at s[j], and are 353 assigned the same reordering extent, n. 354 >>> 355 Comment on Part 3.: For some arrival orders, the assignment of the 356 same extent to all packets in a reordering event will tend to 357 underestimate their true extent. However, a pure position/distance 358 metric (as appeared in earlier versions of this draft) would tend to 359 overestimate the receiver storage needed. We need to weigh the value 360 of adding more complexity in this definition against the accuracy it 361 would provide. 362 A more accurate and complex procedure would be to count any 363 additional in-order packets that arrive after a reordering event is 364 identified, and add them to the extent of the first reordered packet 365 (up to some counter limit of interest) for packets in the interval 366 s[i] < s[*] < s[j]. 367 Those who desire "on-the-fly" calculation must assess whether such a 368 procedure is feasible. 370 Discussion: 372 A receiver must perform some amount of "work" to restore order to 373 all packets that are part of an n-reordering event. The extent n 374 gives the number of packets that must be held in the receiver's 375 buffer while waiting for the reordered packets in the sequence. As 376 reordered packets arrive, the amount of work stays the same if they 377 are all part of the same reordering event. If new reordering events 378 occur, the work in terms of buffer size can increase. See Examples 379 section (specific example to be provided). 381 Knowledge of the reordering extent n is particularly useful for 382 determining the portion of reordered packets that can or cannot be 383 restored to order in a typical TCP receiver buffer based on their 384 arrival order alone (and without the aid of retransmission). 386 Important special cases are n=1 and n=3: 388 - For n=1, absence of 1-reordering events means the sequence numbers 389 that the receiver sees are monotonically increasing with respect to 390 the previous arriving packet. 392 - For n=3, a NewReno TCP sender would retransmit 1 packet in 393 response to a 3-reordering event and therefore consider this a loss 394 event for the purposes of congestion control (the sender will half 395 its congestion window). Detecting 3-reordering events is useful for 396 determining the portion of reordered packets that are in fact as 397 good as lost. 399 We note that the definition of n-reordering events cannot predict 400 the exact number of packets unnecessarily retransmitted by a TCP 401 sender under some circumstances, such as closely-spaced reordering 402 events. The definition is less complicated than a TCP implementation 403 where both time and position influence the sender's behavior. 405 A sample's reordering extents may be expressed as a histogram, to 406 easily summarize the frequency of various extents. 408 4.3 Reordering Offset 409 Any packet whose sequence number causes the Next Expected value to 410 increment by more than the usual increment indicates a discontinuity 411 in the sequence. From this point on, any reordered packets can be 412 assigned Offset values indicating the storage in bytes and lateness 413 in terms of buffer time that a receiver must possess to accommodate 414 them. The various Offset metrics are calculated only on reordered 415 packets, as identified by the ordered arrival singleton in section 416 3. 418 4.3.1 Metric Name: Type-P-packet-Late-Time-Poisson/Periodic-Stream 420 Metric Parameters: In addition to the parameters defined for Type-P- 421 Non-Reversing-Order, we specify: 423 + DstTime, the time that each packet in the stream arrives at Dst 425 Definition: Lateness in time is calculated using Dst times. When 426 packet i is reordered, and part of a reordering event with n extent 427 (assuming j=i-n): 429 LateTime(i) = DstTime(i)-DstTime(i-n) 431 Alternatively, using similar notation to that of section 4.2, an 432 equivalent definition is: 433 LateTime(i) = DstTime[i]-DstTime[j], for min{j|1<=js[i], or SrcTime[j]>SrcTime[i]. 436 4.3.2 Metric Name: Type-P-packet-Byte-Offset-Poisson/Periodic-Stream 438 Metric Parameters: We use the same parameters defined above. 440 Definition: Byte stream offset is the sum of the payload sizes of 441 all intervening packets between the reordered packet and the 442 discontinuity (including the packet at the discontinuity). 444 For reordered packet i 445 ByteOffset(i) = Sum[in-order packets to start of the reordering 446 event] 447 = Sum[PayloadSize(packet at i-1), 448 PayloadSize(packet at i-2), ... 449 PayloadSize(packet at i-n)] 451 Alternatively, if all payload sizes are equal: 452 ByteOffset(i) = n * PayloadSize where n is the reordering extent. 453 >>>>Comment: Previous comments on the accuracy of extent n apply 454 here as well. 456 4.3.3 Discussion 458 The Offset metrics can predict whether reordered packets will be 459 useful in a general receiver buffer system with finite limits. The 460 limit may be the number of bytes or packets the buffer can store, or 461 the time of storage prior to a cyclic play-out instant (as with de- 462 jitter buffers). 464 Note that the One-way IPDV [9] gives the delay variation for a 465 packet w.r.t. the preceding packet in the source sequence. Lateness 466 and IPDV give an indication of whether a buffer at Dst has 467 sufficient storage to accommodate the network's behavior and restore 468 order. When an earlier packet in the Src sequence is lost, IPDV will 469 necessarily be undefined for adjacent packets, and Late Time may 470 provide the only way to evaluate the usefulness of a packet. 472 In the case of de-jitter buffers, there are circumstances where the 473 receiver employs loss concealment at the intended play-out time of a 474 late packet. However, if this packet arrives out of order, the Late 475 Time determines whether the packet is still useful. IPDV no longer 476 applies, because the receiver establishes a new play-out schedule 477 with additional buffer delay to accommodate similar events in the 478 future - this requires very minimal processing. 480 When packets in the stream have variable sizes, it may be most 481 useful to characterize Offset in terms of the payload size(s) of 482 stored packets (using byte stream numbering). 484 4.4 Gaps between multiple Reordering Events 486 4.4.1 Metric Name: 488 Type-P-packet-Reordering-Event-Gap-Poisson/Periodic-Stream 490 4.4.2 Parameters: 492 No new parameters. 494 4.4.3 Definition: 496 A reordering event with extent n is detected according to section 497 4.2 with the arrival of packet s[i]. The next reordering event with 498 extent n' is detected at packet i', and there are no reordering 499 events between i and i'. 501 The Reordering Event Gap is the difference between the arrival 502 positions the packets, as shown below (assuming j=i-n): 504 Gap(i) = (i'-n') - (i-n) 506 Gaps may also be expressed in time: 508 GapTime(i) = DstTime(i'-n') - DstTime(i-n) 509 The Gaps between a sample's reordering events may be expressed as a 510 histogram, to easily summarize the frequency of various extents. 512 4.4.4 Discussion 514 When separate reordering events can be distinguished, then an event 515 count may also be reported (along with the event description, such 516 as the number of reordered packets and their extents or offsets). 517 The distribution of various metrics may also be reported and 518 summarized by the mode, average, range, histogram, etc. 520 The Gap metric may help to correlate the frequency of reordering 521 events with their cause. 523 5. Measurement Issues 525 The results of tests will be dependent on the time interval between 526 measurement packets (both at the Src, and during transport where 527 spacing may change). Clearly, packets launched infrequently (e.g., 528 1 per 10 seconds) are unlikely to be reordered. 530 Test streams may prefer to use a periodic sending interval so that a 531 known temporal bias is maintained, also bringing simplified results 532 analysis (as described in RFC 3432 [10]). In this case, the periodic 533 sending interval should be chosen to reproduce the closest Src 534 packet spacing expected. 535 <<<, the received 626 packets are represented as: 628 \/ 629 s = 1, 2, 3, 5, 6, 7, 8, 4, 9, 10 630 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 631 /\ 632 when n=1, 7<=J<8, and 8 > 4, so the reordering extent is 1 or more. 633 when n=2, 6<=J<8, and 7 > 4, so the reordering extent is 2 or more. 634 when n=3, 5<=J<8, and 6 > 4, so the reordering extent is 3 or more. 635 when n=4, 4<=J<8, and 5 > 4, so the reordering extent is 4 or more. 636 when n=5, 3<=J<8, but 3 < 4, and 4 is the maximum extent. 638 Further, we can compute the Late Time (210-148=62ms using DstTime) 639 compared to packet 5's arrival. If Dst has a de-jitter buffer that 640 holds more than 4 packets, or at least 62 ms storage, packet 4 may 641 be useful. Note that 1-way delay and IPDV also indicate unusual 642 behavior for packet 4. 644 If all packets contained 100 byte payloads, then Byte Offset is 645 equal to 400 bytes. 647 Table 2 Example with Packets 5 and 6 Reordered, 648 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10 649 s Src Dst Dst Byte Late 650 @Dst NextExp Time Time Delay IPDV Order Offset Time 651 1 1 0 68 68 1 652 2 2 20 88 68 0 2 653 3 3 40 108 68 0 3 654 4 4 60 128 68 0 4 655 7 5 120 188 68 -22 5 656 5 8 80 189 109 41 6 100 1 657 6 8 100 190 90 -19 7 100 2 658 8 8 140 208 68 0 8 659 9 9 160 228 68 0 9 660 10 10 180 248 68 0 10 661 Table 2 shows a case where packets 5 and 6 arrive just behind packet 662 7, so both 5 and 6 are reordered. The Late times (189-188=1, 190- 663 188=2) are small. 665 Using the notation , the received 666 packets are represented as: 668 \/ \/ 669 s = 1, 2, 3, 4, 7, 5, 6, 8, 9, 10 670 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 671 /\ /\ 673 Considering packet 5[6] first: 674 when n=1, 5<=J<6, and 7 > 5, so the reordering extent is 1 or more. 675 when n=2, 4<=J<6, but 4 < 5, and 1 is the maximum extent. 677 Considering packet 6[7] next: 678 when n=1, 6<=J<7, and 5 < 6, so the packet at i=7 does not have its 679 own reordering extent, and must be part of the same reordering event 680 as packet 5[6]. Using the test of Section 4.2.4, Definition 2, we 681 find that the condition is met for packet 6[7]: 683 s[i] < s < s[i-n] 684 5[6] < 6[7] < 7[5] 686 A hypothetical sender/receiver pair may retransmit packet 5[8] 687 unnecessarily, since it is reordered with extent n=1(in agreement 688 with the singleton metric). However, the receiver cannot advance 689 packet 7[5] to the higher layers until after packet 6[7] arrives. 690 Therefore, the singleton metric correctly determined that 6[7] is 691 reordered, and both packets are part of a 1-reordering event. 693 Table 3 Example with Packets 4, 5, and 6 reordered 694 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11 695 s Src Dst Dst Byte Late 696 @Dst NextExp Time Time Delay IPDV Order Offset Time 697 1 1 0 68 68 1 698 2 2 20 88 68 0 2 699 3 3 40 108 68 0 3 700 7 4 120 188 68 -68 4 701 8 8 140 208 68 0 5 702 9 9 160 228 68 0 6 703 10 10 180 248 68 0 7 704 4 11 60 250 190 122 8 400 62 705 5 11 80 252 172 -18 9 400 64 706 6 11 100 256 156 -16 10 400 68 707 11 11 200 268 68 0 11 709 The case in Table 3 is where three packets in sequence have long 710 transit times (packets with s = 4,5,and 6). Delay, Late time, and 711 Byte Offset capture this very well, and indicate variation in 712 reordering extent, while IPDV indicates that the spacing between 713 packets 4,5,and 6 has changed. 715 The histogram of Reordering extents (n) would be: 717 Bin 1 2 3 4 5 6 7 718 Frequency 0 0 0 3 0 0 0 720 Using the notation , the received 721 packets are represented as: 723 s = 1, 2, 3, 7, 8, 9,10, 4, 5, 6, 11 724 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11 726 Considering packet 4[8] first: 727 when n=1, 7<=J<8, and 10> 4, so the reordering extent is 1 or more. 728 when n=2, 6<=J<8, and 9 > 4, so the reordering extent is 2 or more. 729 when n=3, 5<=J<8, and 8 > 4, so the reordering extent is 3 or more. 730 when n=4, 4<=J<8, and 7 > 4, so the reordering extent is 4 or more. 731 when n=5, 3<=J<8, but 3 < 4, and 4 is the maximum extent. 733 Considering packet 5[9] next: 734 when n=1, 8<=J<9, but 4 < 5, so the packet at i=9 does not have its 735 own reordering extent, and must be part of the same reordering event 736 as packet 4[8]. Using the test of Section 4.2.4, Definition 2, we 737 find that the condition is met for both packets 5[9] and 6[10]: 739 s[i] < s < s[i-n] 740 4[8] < 5[9] < 7[4] 741 4[8] < 6[10]< 7[4] 743 This example shows again that the n-reordering event definition 744 identifies a single event (s=4) with a sufficient degree of 745 reordering to result in one unnecessary packet retransmission by the 746 New Reno TCP sender. Also, the reordered arrival of packets s=5 and 747 s=6 will allow the receiver process to pass packets 7 through 10 up 748 the protocol stack (the singleton metric indicates 5 and 6 are 749 reordered, and they are all part of one reordering event). 751 7. Security Considerations 753 7.1 Denial of Service Attacks 755 This metric requires a stream of packets sent from one host (Src) to 756 another host (Dst) through intervening networks. This method could 757 be abused for denial of service attacks directed at Dst and/or the 758 intervening network(s). 760 Administrators of Src, Dst, and the intervening network(s) should 761 establish bilateral or multi-lateral agreements regarding the 762 timing, size, and frequency of collection of sample metrics. Use of 763 this method in excess of the terms agreed between the participants 764 may be cause for immediate rejection or discard of packets or other 765 escalation procedures defined between the affected parties. 767 7.2 User data confidentiality 769 Active use of this method generates packets for a sample, rather 770 than taking samples based on user data, and does not threaten user 771 data confidentiality. Passive measurement must restrict attention to 772 the headers of interest. Since user payloads may be temporarily 773 stored for length analysis, suitable precautions MUST be taken to 774 keep this information safe and confidential. 776 7.3 Interference with the metric 778 It may be possible to identify that a certain packet or stream of 779 packets is part of a sample. With that knowledge at Dst and/or the 780 intervening networks, it is possible to change the processing of the 781 packets (e.g. increasing or decreasing delay) that may distort the 782 measured performance. It may also be possible to generate 783 additional packets that appear to be part of the sample metric. 784 These additional packets are likely to perturb the results of the 785 sample measurement. 787 To discourage the kind of interference mentioned above, packet 788 interference checks, such as cryptographic hash, may be used. 790 8. IANA Considerations 792 Since this metric does not define a protocol or well-known values, 793 there are no IANA considerations in this memo. 795 9. References 797 1 Bradner, S., "The Internet Standards Process -- Revision 3", BCP 798 9, RFC 2026, October 1996. 800 2 Bradner, S., "Key words for use in RFCs to Indicate Requirement 801 Levels", RFC 2119, March 1997. 803 3 Paxson, V., Almes, G., Mahdavi, J., and Mathis, M., "Framework 804 for IP Performance Metrics", RFC 2330, May 1998. 806 4 V.Paxson, "Measurements and Analysis of End-to-End Internet 807 Dynamics," Ph.D. dissertation, U.C. Berkeley, 1997, 808 ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz. 810 5 Postel, J., "Transmission Control Protocol", STD 7, RFC 793, 811 September 1981. 812 Obtain via: http://www.rfc-editor.org/rfc/rfc793.txt 814 6 L.Ciavattone and A.Morton, "Out-of-Sequence Packet Parameter 815 Definition (for Y.1540)", Contribution number T1A1.3/2000-047, 816 October 30, 2000. ftp://ftp.t1.org/pub/t1a1/2000-A13/0a130470.doc 818 7 J.C.R.Bennett, C.Partridge, and N.Shectman, "Packet Reordering is 819 Not Pathological Network Behavior," IEEE/ACM Transactions on 820 Neteworking, vol.7, no.6, pp.789-798, December 1999. 822 8 D.Loguinov and H.Radha, "Measurement Study of Low-bitrate 823 Internet Video Streaming"' Proceedings of the ACM SIGCOMM 824 Internet Measurement Workshop 2001 November 1-2, 2001, San 825 Francisco, USA. 827 9 Demichelis, C., and Chimento, P., "IP Packet Delay Variation 828 Metric for IP Performance Metrics (IPPM)", RFC 3393, November 829 2002. 831 10 Raisanen, V., Grotefeld, G., and Morton, A., "Network performance 832 measurement with periodic streams", RFC 3432, November 2002. 834 11. Acknowledgments 836 The authors would like to acknowledge many helpful discussions with 837 Matt Mathis and Jon Bennett. We gratefully acknowledge the 838 foundation laid by the authors of the IP performance Framework [3]. 840 12. Appendix A (informative) 842 Two example c-code implementations of reordering definitions follow: 844 Example 1 n-reordering ============================================ 846 #include 848 #define MAX_N 100 850 #define min(a, b) ((a) < (b)? (a): (b)) 851 #define loop(x) ((x) >= 0? x: x + MAX_N) 853 /* 854 * Read new sequence number and return it. Return a sentinel value 855 of EOF 856 * (at least once) when there are no more sequence numbers. In this 857 example, 858 * the sequence numbers come from stdin; in an actual test, they 859 would come 860 * from the network. 861 */ 862 int 863 read_sequence_number() 864 { 865 int res, rc; 866 rc = scanf("%d\n", &res); 867 if (rc == 1) return res; 868 else return EOF; 869 } 871 int 872 main() 873 { 874 int m[MAX_N]; /* We have m[j-1] == number 875 of 876 * j-reordered packets. */ 877 int ring[MAX_N]; /* Last sequence numbers 878 seen. */ 879 int r = 0; /* Ring pointer for next 880 write. */ 881 int l = 0; /* Number of sequence 882 numbers read. */ 883 int s; /* Last sequence number 884 read. */ 885 int j; 887 for (j = 0; j < MAX_N; j++) m[j] = 0; 888 for (; (s = read_sequence_number()) != EOF; l++, r = (r+1) % 889 MAX_N) { 890 for (j=0; j 907 #define MAX_N 100 908 #define min(a, b) ((a) < (b)? (a): (b)) 909 #define loop(x) ((x) >= 0? x: x + MAX_N) 911 /* Global counters */ 912 int receive_packets=0; /* number of recieved */ 913 int reorder_packets=0; /* number of reordered packets */ 914 /* function to test if current packet has been reordered 915 * returns 0 = not reordered 916 * 1 = reordered 917 */ 918 int testorder1(int seqnum) // Al 919 { 920 static int NextExp = 1; 921 int iReturn = 0; 923 if (seqnum >= NextExp) { 924 NextExp = seqnum+1; 925 } else { 926 iReturn = 1; 927 } 928 return iReturn; 929 } 931 int testorder2(int seqnum) // Stanislav 932 { 933 static int ring[MAX_N]; /* Last sequence numbers 934 seen. */ 935 static int r = 0; /* Ring pointer for next write. 936 */ 937 int l = 0; /* Number of sequence 938 numbers read. */ 939 int j; 940 int iReturn = 0; 942 l++; 943 r = (r+1) % MAX_N; 944 for (j=0; j 972 Len Ciavattone 973 AT&T Labs 974 Room C4 - 2B29 975 200 Laurel Ave. South 976 Middletown, NJ 07748 USA 977 Phone +1 732 420 1239 978 980 Gomathi Ramachandran 981 AT&T Labs 982 Room C4 - 3D22 983 200 Laurel Ave. South 984 Middletown, NJ 07748 USA 985 Phone +1 732 420 2353 986 988 Stanislav Shalunov 989 Internet2 990 200 Business Park Drive, Suite 307 991 Armonk, NY 10504 992 Phone: + 1 914 765 1182 993 EMail: 995 Jerry Perser 996 Spirent Communications 997 26750 Agoura Road 998 Calabasas, CA 91302 USA 999 Phone: + 1 818 676 2300 1000 EMail: 1002 Full Copyright Statement 1004 "Copyright (C) The Internet Society (date). All Rights Reserved. 1005 This document and translations of it may be copied and furnished to 1006 others, and derivative works that comment on or otherwise explain it 1007 or assist in its implmentation may be prepared, copied, published 1008 and distributed, in whole or in part, without restriction of any 1009 kind, provided that the above copyright notice and this paragraph 1010 are included on all such copies and derivative works. However, this 1011 document itself may not be modified in any way, such as by removing 1012 the copyright notice or references to the Internet Society or other 1013 Internet organizations, except as needed for the purpose of 1014 developing Internet standards in which case the procedures for 1015 copyrights defined in the Internet Standards process must be 1016 followed, or as required to translate it into languages other than 1017 English. 1019 The limited permissions granted above are perpetual and will not be 1020 revoked by the Internet Society or its successors or assigns. 1022 This document and the information contained herein is provided on an 1023 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 1024 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 1025 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 1026 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 1027 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.