idnits 2.17.1 

draft-ietf-ippm-reordering-08.txt:

  Checking boilerplate required by RFC 5378 and the IETF Trust (see
  https://trustee.ietf.org/license-info):
  ----------------------------------------------------------------------------

  ** It looks like you're using RFC 3978 boilerplate.  You should update this
     to the boilerplate described in the IETF Trust License Policy document
     (see https://trustee.ietf.org/license-info), which is required now.

  -- Found old boilerplate from RFC 3978, Section 5.5 on line 1653.

  -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1663.

  -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1670.

  -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1676.

  ** The document seems to lack an RFC 3978 Section 5.1 IPR Disclosure
     Acknowledgement. 

  ** This document has an original RFC 3978 Section 5.4 Copyright Line,
     instead of the newer IETF Trust Copyright according to RFC 4748.

  ** The document seems to lack an RFC 3978 Section 5.4 Reference to BCP 78
     -- however, there's a paragraph with a matching beginning. Boilerplate
     error?

  ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead
     of the newer disclaimer which includes the IETF Trust according to RFC
     4748.

  ** The document uses RFC 3667 boilerplate or RFC 3978-like boilerplate
     instead of verbatim RFC 3978 boilerplate.  After 6 May 2005, submission
     of drafts without verbatim RFC 3978 boilerplate is not accepted.

     The following non-3978 patterns matched text found in the document. 
     That text should be removed or replaced:

        This document is an Internet-Draft and is subject to all provisions of
        Section 3 of RFC 3667.


  Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt:
  ----------------------------------------------------------------------------

  ** Missing expiration date.  The document expiration date should appear on
     the first and last page.


  Checking nits according to https://www.ietf.org/id-info/checklist :
  ----------------------------------------------------------------------------

     No issues found here.

  Miscellaneous warnings:
  ----------------------------------------------------------------------------

  == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not
     match the current year

  == Line 1444 has weird spacing: '...tic int  ring[...'

  == Line 1445 has weird spacing: '...tic int  r = 0...'

  == Line 1446 has weird spacing: '...    int   l = ...'

  == Line 1447 has weird spacing: '...    int   j;...'

  == Line 1448 has weird spacing: '...    int  iRetu...'

  -- The document seems to lack a disclaimer for pre-RFC5378 work, but may
     have content which was first submitted before 10 November 2008.  If you
     have contacted all the original authors and they are all willing to grant
     the BCP78 rights to the IETF Trust, then this is fine, and you can ignore
     this comment.  If not, you may need to add the pre-RFC5378 disclaimer. 
     (See the Legal Provisions document at
     https://trustee.ietf.org/license-info for more information.)

  -- Couldn't find a document date in the document -- date freshness check
     skipped.

  -- Found something which looks like a code comment -- if you have code
     sections in the document, please surround them with '<CODE BEGINS>' and
     '<CODE ENDS>' lines.


  Checking references for intended status: Proposed Standard
  ----------------------------------------------------------------------------

     (See RFCs 3967 and 4897 for information about using normative references
     to lower-maturity documents in RFCs)

  -- Looks like a reference, but probably isn't: '1' on line 1174

  -- Looks like a reference, but probably isn't: '2' on line 821

  == Missing Reference: 'L' is mentioned on line 1058, but not defined

  -- Looks like a reference, but probably isn't: '9' on line 1187

  == Missing Reference: 'MAXN' is mentioned on line 1444, but not defined

  ** Downref: Normative reference to an Informational RFC: RFC 2330

  ** Downref: Normative reference to an Informational RFC: RFC 3148

  -- Obsolete informational reference (is this intentional?): RFC  793
     (Obsoleted by RFC 9293)


     Summary: 9 errors (**), 0 flaws (~~), 8 warnings (==), 11 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: <draft-ietf-ippm-reordering-08.txt>            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 subject to all provisions
15	   of section 3 of RFC 3667. By submitting this Internet-Draft, each
16	   author represents that any applicable patent or other IPR claims of
17	   which he or she is aware have been disclosed, and any of which he or
18	   she becomes aware will be disclosed, in accordance with RFC 3668.

20	   Internet-Drafts are working documents of the Internet Engineering
21	   Task Force (IETF), its areas, and its working groups.  Note that
22	   other groups may also distribute working documents as Internet-
23	   Drafts.

25	   Internet-Drafts are draft documents valid for a maximum of six
26	   months and may be updated, replaced, or obsoleted by other documents
27	   at any time.  It is inappropriate to use Internet-Drafts as
28	   reference material or to cite them other than as "work in progress."

30	   The list of current Internet-Drafts can be accessed at
31	   http://www.ietf.org/ietf/1id-abstracts.txt

33	   The list of Internet-Draft Shadow Directories can be accessed at
34	   http://www.ietf.org/shadow.html.

36	Copyright Notice

38	   Copyright (C) The Internet Society (2004).

40	Abstract

42	   This memo defines metrics to evaluate if a network has maintained
43	   packet order on a packet-by-packet basis. It provides motivations
44	   for the new metrics and discusses the measurement issues. The memo
45	   first defines a reordered singleton, and then uses it as the basis
46	   for sample metrics to quantify the extent of reordering in several
47	   useful dimensions for network characterization or receiver design.
48	   Additional metrics quantify the frequency of reordering and the
49	   distance between separate occurrences. We then define a metric with
50	   purely receiver analysis orientation. Several examples of evaluation
51	   using the various sample metrics are included. An Appendix gives
52	   extended definitions for evaluating order with packet fragmentation.

54	Contents

56	   Status of this Memo................................................1
57	   Copyright Notice...................................................1
58	   Abstract...........................................................1
59	   1. Conventions used in this document...............................3
60	   2. Introduction....................................................3
61	   2.1 Motivation.....................................................4
62	   2.2 Goals and Objectives...........................................5
63	   3. A Reordered Packet Singleton Metric.............................6
64	   3.1 Metric Name:...................................................6
65	   3.2 Metric Parameters:.............................................6
66	   3.3 Definition:....................................................7
67	   3.4 Sequence Discontinuity Definition..............................7
68	   3.5 Evaluation of Reordering in Dimensions of Time or Bytes........8
69	   3.6 Discussion.....................................................8
70	   4. Sample Metrics..................................................9
71	   4.1 Reordered Packet Ratio.........................................9
72	   4.1.1 Metric Name:.................................................9
73	   4.1.2 Metric Parameters:...........................................9
74	   4.1.3 Definition:..................................................9
75	   4.1.4 Discussion...................................................9
76	   4.2 Reordering Extent.............................................10
77	   4.2.1 Metric Name:................................................10
78	   4.2.2 Parameter Notation:.........................................10
79	   4.2.3 Definition:.................................................10
80	   4.2.4 Discussion:.................................................11
81	   4.3 Reordering Late Time Offset...................................11
82	   4.3.1 Metric Name:................................................11
83	   4.3.2 Metric Parameters:..........................................11
84	   4.3.3 Definition:.................................................11
85	   4.3.4 Discussion..................................................12
86	   4.4 Reordering Byte Offset........................................12
87	   4.4.1 Metric Name:................................................12
88	   4.4.2 Metric Parameters:..........................................12
89	   4.4.3 Definition:.................................................12
90	   4.4.4 Discussion..................................................13
91	   4.5 Gaps between multiple Reordering Discontinuities..............13
92	   4.5.1 Metric Name:................................................13
93	   4.5.2 Parameters:.................................................13
94	   4.5.3 Definition of Reordering Discontinuity:.....................13
95	   4.5.4 Definition of Reordering Gap:...............................14
96	   4.5.5 Discussion..................................................14
97	   4.6 Reordering-free Runs..........................................14
98	   4.6.1 Metric Name:................................................15
99	   4.6.2 Parameters:.................................................15
100	   4.6.3 Definition:.................................................15
101	   4.6.4 Discussion:.................................................16
102	   5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric..16
103	   5.1 Metric Name:..................................................16
104	   5.2 Parameter Notation:...........................................17
105	   5.3 Definitions...................................................17
106	   5.4 Discussion:...................................................17
107	   6. Measurement and Implementation Issues..........................18
108	   7. Examples of Arrival Order Evaluation...........................20
109	   7.1 Example with a single packet reordered........................21
110	   7.2 Example with two packets reordered............................22
111	   7.3 Example with three packets reordered..........................23
112	   7.4 Example with Multiple Packet Reordering Discontinuities.......25
113	   8. Security Considerations........................................25
114	   8.1 Denial of Service Attacks.....................................25
115	   8.2 User data confidentiality.....................................25
116	   8.3 Interference with the metric..................................26
117	   9. IANA Considerations............................................26
118	   10. Normative References..........................................26
119	   11. Informative References........................................26
120	   12. Acknowledgments...............................................27
121	   13. Appendix A Example Implementations in C (Informative).........28
122	   14. Appendix B Fragment Order Evaluation (Informative)............30
123	   14.1 Metric Name:.................................................30
124	   14.2 Additional Metric Parameters:................................30
125	   14.3 Definition:..................................................31
126	   14.4 Discussion: Notes on Sample Metrics when evaluating Fragments32
127	   15. Author's Addresses............................................32
128	   Full Copyright Statement..........................................33
129	   Intellectual Property.............................................33
130	   Acknowledgement...................................................34

132	1. Conventions used in this document

134	   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
135	   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
136	   document are to be interpreted as described in RFC 2119 [RFC2119].
137	   Although RFC 2119 was written with protocols in mind, the key words
138	   are used in this document for similar reasons.  They are used to
139	   ensure the results of measurements from two different
140	   implementations are comparable, and to note instances when an
141	   implementation could perturb the network.

143	2. Introduction

145	   Ordered arrival is a property found in packets that successfully
146	   transit their path, where the packet sequence number increases with
147	   each new arrival and there are no backward steps. Internet Protocol
148	   [RFC791] has no mechanisms to assure either packet delivery or
149	   sequencing, and other protocols should be prepared to deal with both
150	   loss and reordering. This memo defines reordering metrics.

152	   A unique sequence number, such as an incrementing message number
153	   carried in each packet, establishes the Source Sequence.

155	   The detection of reordering at the Destination is based on packet
156	   arrival order in comparison with a non-reversing reference value.

158	   This metric is consistent with RFC 2330 [RFC2330], and classifies
159	   arriving packets with sequence numbers smaller than their
160	   predecessors as out-of-order, or reordered. For example, if
161	   sequentially numbered packets arrive 1,2,4,5,3, then packet 3 is
162	   reordered. This is equivalent to Paxon's reordering definition in
163	   [Pax98], where "late" packets were declared reordered. The
164	   alternative is to emphasize "premature" packets instead (4 and 5 in
165	   the example), but only the arrival of packet 3 distinguishes this
166	   circumstance from packet loss. Focusing attention on late packets
167	   allows us to maintain orthogonality with the packet loss metric. The
168	   metric's construction is very similar to the sequence space
169	   validation for received segments in RFC 793 [RFC793]. Earlier work
170	   to define ordered delivery includes [Cia00], [Ben99], [Lou01],
171	   [Bel02], [Jai02] and [Cia03].

173	2.1 Motivation

175	   A reordering metric is relevant for most applications, especially
176	   when assessing network support for Real-Time media streams. The
177	   extent of reordering may be sufficient to cause a received packet to
178	   be discarded by functions above the IP layer.

180	   Packet order may change during transfer, and several specific path
181	   characteristics can make reordering more likely.

183	   Examples are:
184	   * When two paths, one with slightly longer transfer time, support a
185	     single packet stream or flow, then packets traversing the longer
186	     path may arrive out-of-order. Multiple paths may be used to
187	     achieve load balancing, or may arise from route instability.
188	   * To increase capacity, a network device designed with multiple
189	     processors serving a single port may reorder as a byproduct.
190	   * A layer 2 retransmission protocol that compensates for an error-
191	     prone link may cause packet reordering.
192	   * If for any reason, the packets in a buffer are not serviced in the
193	     order of their arrival, their order will change.
194	   * If packets in a flow are assigned to multiple buffers (following
195	     evaluation of traffic characteristics, for example), and the
196	     buffers have different occupations and/or service rates, then
197	     order will likely change.

199	   When one or more of the above path characteristics are present
200	   continuously, then reordering may be present on a steady-state
201	   basis. The steady-state reordering condition typically causes an
202	   appreciable fraction of packets to be reordered. This form of
203	   reordering is most easily detected by minimizing the spacing between
204	   test packets.  Transient reordering may occur in response to network
205	   instability; temporary routing loops can cause periods of extreme
206	   reordering. This condition is characterized by long in-order streams
207	   with occasional instances of reordering, sometimes with extreme
208	   correlation. However, we do not expect packet delivery in a
209	   completely random order, where for example, the last packet or the
210	   first packet in a sample is equally likely to arrive first at the
211	   destination. Thus we expect at least a minimal degree of order in
212	   the packet arrivals, as exhibited in real networks.

214	   The ability to restore order at the destination will likely have
215	   finite limits.  Practical hosts have receiver buffers with finite
216	   size in terms of packets, bytes, or time (such as de-jitter
217	   buffers). Once the initial determination of reordering is made, it
218	   is useful to quantify the extent of reordering, or lateness, in all
219	   meaningful dimensions.

221	2.2 Goals and Objectives

223	   The definitions below intend to satisfy the goals of:

225	     1. Determining whether or not packet reordering has occurred.
226	     2. Quantifying the degree of reordering (achieving this second
227	        goal requires assumptions of upper layer functions and
228	        capabilities to restore order, and therefore several
229	        solutions).

231	   Reordering Metrics MUST:

233	   +  have one or more applications, such as receiver design or network
234	     characterization, and a compelling relevance in the working
235	     group's view.
236	   +  be computable "on the fly"
237	   +  work even if the stream has duplicate or lost packets

239	   It is desirable for Reordering Metrics to have one or more of the
240	   following attributes:

242	   +  concatenating results for segments measured separately
243	   +  simplicity for easy consumption and understanding
244	   +  relevance to TCP performance
245	   +  relevance to Real-time application performance

247	   The current set of metrics meet all the requirements above, and
248	   provides all but the concatenation attribute (except in the case
249	   where segments exhibit no reordering, and one may estimate that the
250	   segment concatenation would also exhibit this desirable outcome).
251	   However, satisfying these goals limits the set of metrics to those
252	   that provide some clear insight into network characterization or
253	   receiver design, and they are not likely to be exhaustive in their
254	   coverage of the applications with respect to packet reordering
255	   effects. Likewise, additional measurements may be possible.

257	3. A Reordered Packet Singleton Metric

259	   The IPPM framework RFC 2330 [RFC2330] describes the notions of
260	   singletons, samples, and statistics. For easy reference:

262	        By a 'singleton' metric, we refer to metrics that are,
263	        in a sense, atomic.  For example, a single instance of "bulk
264	        throughput capacity" from one host to another might be defined
265	        as a singleton metric, even though the instance involves
266	        measuring the timing of a number of Internet packets.

268	   The evaluation of packet order requires several supporting concepts.
269	   The first is a sequence number applied to packets at the source to
270	   uniquely identify the order of packet transmission.  The unique
271	   sequence number may be a simple message number.

273	   The second supporting concept is a stored value which is the "next
274	   expected" packet number. Under normal conditions, the value of Next
275	   Expected (NextExp) is the sequence number of the previous packet
276	   plus 1 (for message numbering).

278	   Each packet within a packet stream can be evaluated with this order
279	   singleton metric.

281	3.1 Metric Name:

283	   Type-P-Reordered

285	3.2 Metric Parameters:

287	   +  Src, the IP address of a host

289	   +  Dst, the IP address of a host

291	   +  SrcTime, the time of packet emission from the Source (or wire
292	      time)

294	   +  s, the unique packet sequence number applied at the Source, in
295	      units of messages.

297	   +  SrcByte, the packet sequence number applied at the Source, in
298	      units of payload bytes.

300	   +  NextExp, the Next Expected Sequence number at the Destination, in
301	      units of messages, time, or bytes.

303	   +  PayloadSize, the number of bytes contained in the information
304	      field and referred to when the SrcByte sequence is based on byte
305	      transfer.

307	3.3 Definition:

309	   If a packet is found to be reordered by comparison with the Next
310	   Expected value, its Type-P-Reordered = TRUE; otherwise Type-P-
311	   Reordered = FALSE, as defined below:

313	   The value of Type-P-Reordered is defined as TRUE if s < NextExp (the
314	   packet is reordered). In this case, NextExp value does not change.

316	   The value of Type-P-Reordered is defined as FALSE if s >= NextExp
317	   (the packet is in-order). In this case, NextExp is set to s+1.

319	   Since the Next Expected value cannot decrease, it provides a non-
320	   reversing order criterion to identify reordered packets.

322	   This definition can also be specified in pseudo-code.

324	   On successful arrival of a packet with sequence number s:
325	        if s >= NextExp then /* s is in-order */
326	                NextExp = s + 1;
327	                Type-P-Reordered = False;
328	        else     /* when s < NextExp */
329	                Type-P-Reordered = True

331	3.4 Sequence Discontinuity Definition

333	   Packets with s > NextExp are a special case of in-order delivery.
334	   This condition indicates a sequence discontinuity, either because of
335	   packet loss or reordering. Reordered packets must arrive for the
336	   sequence discontinuity to be defined as a reordering discontinuity
337	   (see section 4).

339	   We define two different states for in-order packets.

341	   When s = NextExp, the original sequence has been maintained, and
342	   there is no discontinuity present.

344	   When s > NextExp, some packets in the original sequence have not yet
345	   arrived, and there is a sequence discontinuity associated with
346	   packet s.  The size of the discontinuity is s - NextExp, equal to
347	   the number of packets presently missing, either reordered or lost.

349	   In pseudo-code:

351	   On successful arrival of a packet with sequence number s:
352	        if s >= NextExp, then /* s is in-order */
353	                if s > NextExp then
354	                          SequenceDiscontinuty = True;
355	                          SeqDiscontinutySize = s - NextExp;
356	                else
357	                          SequenceDiscontinuty = False;
358	                NextExp = s + 1;
359	                Type-P-Reordered = False;

361	        else /* when s < NextExp */
362	                Type-P-Reordered = True;
363	                SequenceDiscontinuty = False;

365	3.5 Evaluation of Reordering in Dimensions of Time or Bytes

367	   It is possible to use alternate dimensions of time or payload bytes
368	   to test for reordering in the definition of section 3.3, as long as
369	   the SrcTimes and SrcBytes are unique and reliable. Sequence
370	   Discontinuities are easily defined and detected with message
371	   numbering, however, this is not so in the dimensions of time or
372	   bytes. This is a detractor for the alternate dimensions because the
373	   Sequence Discontinuity definition plays a key role in the sample
374	   metrics that follow.

376	   It is possible to detect Sequence Discontinuities with payload byte
377	   numbering, but only when payload size is constant, and then the byte
378	   numbering adds needless complexity over message numbering.

380	   It may be possible to detect Sequence Discontinuities with Periodic
381	   Streams and Source Time numbering, but there are practical pitfalls
382	   with sending exactly on-schedule and with clock reliability.

384	   The dimensions of time and bytes remain an important basis for
385	   characterizing the extent of reordering, as described later.

387	3.6 Discussion

389	   Any arriving packet bearing a sequence number from the sequence that
390	   establishes the Next Expected value can be evaluated to determine
391	   whether it is in-order or reordered, based on a previous packet's
392	   arrival. In the case where Next Expected is Undefined (because the
393	   arriving packet is the first successful transfer), the packet is
394	   designated in-order.

396	   This metric assumes re-assembly of packet fragments before
397	   evaluation. In principle, it is possible to use the Type-P-Reordered
398	   metric to evaluate reordering among packet fragments, but each
399	   fragment must contain source sequence information.
400	   See the Appendix on fragment order evaluation for more detail.

402	   If duplicate packets (multiple non-corrupt copies) arrive at the
403	   destination, they MUST be noted and only the first to arrive is
404	   considered for further analysis (copies would be declared reordered
405	   according to the definition above). This requirement has the same
406	   storage implications as earlier IPPM metrics, and follows the
407	   precedent of RFC 2679. We provide a suggestion to minimize storage
408	   size needed in the section on Measurement and Implementation Issues.

410	4. Sample Metrics

412	   In this section, we define metrics applicable to a sample of packets
413	   from a single Source sequence number system. When reordering occurs,
414	   it is highly desirable to assert the degree to which a packet is
415	   out-of-order, or reordered with respect other packets. This section
416	   defines several metrics that quantify the extent of reordering in
417	   various units of measure. Each metric highlights a relevant use.

419	   The metrics in the sub-sections below have a network
420	   characterization orientation, but also have relevance to receiver
421	   design where reordering compensation is of interest. We begin with a
422	   simple ratio metric indicating the reordered portion of the sample.

424	4.1 Reordered Packet Ratio

426	4.1.1 Metric Name:

428	   Type-P-Reordered-Ratio-Stream

430	4.1.2 Metric Parameters:

432	   The parameter set includes Type-P-Reordered singleton parameters,
433	   the parameters unique to Poisson Streams (as in RFC 2330 [RFC2330],
434	   Periodic Streams (as in RFC 3432 [RFC3432]), or TCP-like Streams (as
435	   in RFC 3148 [RFC3148]), plus the following:

437	   + T0, a start time

439	   + Tf, an end time

441	   + dT, a waiting time for each packet to arrive

443	4.1.3 Definition:

445	   For the packets arriving successfully between T0 and Tf+dT, the
446	   ratio of reordered packets in the sample is

448	   (Total of Reordered packets) / (Total packets received)

450	   This fraction may be expressed as a percentage (multiply by 100%).
451	   Note that in the case of duplicate packets, only the first copy is
452	   used.

454	4.1.4 Discussion
455	   When the Type-P-Reordered-Ratio-Stream is zero, no further
456	   reordering metrics need be examined for that sample. Therefore, the
457	   value of this metric is its simple ability to summarize the results
458	   for a reordering-free sample.

460	4.2 Reordering Extent

462	   This section defines the extent to which packets are reordered, and
463	   associates a specific sequence discontinuity with each reordered
464	   packet. This section inherits the Parameters defined above.

466	4.2.1 Metric Name:

468	   Type-P-packet-Reordering-Extent-Stream

470	4.2.2 Parameter Notation:

472	   Given a stream of packets sent from a source to a destination, let K
473	   be the total number of packets in that stream.

475	   Assign each packet a sequence number, a consecutive integer from 1
476	   to K in the order of packet transmission (at the source).

478	   Let L be the total number of packets received out of the K packets
479	   sent. Recall that identical copies (duplicates) have been removed,
480	   so L<=K.

482	   Let s[1], s[2], ..., s[L], represent the original sequence numbers
483	   associated with the packets in order of arrival.

485	   Consider a reordered packet (as identified in section 3) with
486	   arrival index i and source sequence number s[i]. There exists a set
487	   of indexes j (1<=j<i) such that s[j] > s[i].

489	4.2.3 Definition:

491	   The reordering extent, e, of packet s[i] is defined to be
492	   i-j for the smallest value of j when s[j] > s[i].

494	   Informally, the reordering extent is the maximum distance, in
495	   packets, from a reordered packet to the earliest packet received
496	   that has a larger sequence number.  If a packet is in-order, its
497	   reordering extent is undefined. The first packet to arrive is in-
498	   order by definition, and has undefined reordering extent.

500	   Comment on the definition of extent:  For some arrival orders, the
501	   assignment of a simple position/distance as the reordering extent
502	   tends to overestimate the receiver storage needed to restore order.
503	   A more accurate and complex procedure to calculate packet storage
504	   would be to subtract any earlier reordered packets that the receiver
505	   could pass on to the upper layers. With the bias understood, this
506	   definition is deemed sufficient, especially for those who demand "on
507	   the fly" calculations.

509	4.2.4 Discussion:

511	   The packet with index j (s[j], identified in the Definition above)
512	   is the reordering discontinuity associated with packet with index i
513	   (s[i]). This definition is formalized below.

515	   Note that the K packets in the stream could be some subset of a
516	   larger stream, but L is still the total number of packets received
517	   out of the K packets sent in that subset.

519	   A receiver must possess storage to restore order to packets that are
520	   reordered. For cases with single reordered packets, the extent e
521	   gives the number of packets that must be held in the receiver's
522	   buffer while waiting for the reordered packet to complete the
523	   sequence. For more complex scenarios, the extent may be an
524	   overestimate of required storage (see the Examples section).

526	   Knowledge of the reordering extent e is particularly useful for
527	   determining the portion of reordered packets that can or cannot be
528	   restored to order in a typical receiver buffer based on their
529	   arrival order alone (and without the aid of retransmission).

531	   A sample's reordering extents may be expressed as a histogram, to
532	   easily summarize the frequency of various extents.

534	4.3 Reordering Late Time Offset

536	   Reordered packets can be assigned offset values indicating their
537	   lateness in terms of buffer time that a receiver must possess to
538	   accommodate them. Offset metrics are calculated only on reordered
539	   packets, as identified by the reordered packet singleton metric in
540	   Section 3.

542	4.3.1 Metric Name:

544	   Type-P-packet-Late-Time-Stream

546	4.3.2 Metric Parameters:

548	   In addition to the parameters defined for Type-P-Reordered-Ratio-
549	   Stream, we specify:

551	   +  DstTime, the time that each packet in the stream arrives at the
552	     destination

554	4.3.3 Definition:

556	   Lateness in time is calculated using destination times. When
557	   received packet i is reordered, and has a reordering extent e, then:

559	   LateTime(i) = DstTime(i)-DstTime(i-e)

561	   Alternatively, using similar notation to that of section 4.2, an
562	   equivalent definition is:
563	   LateTime(i) = DstTime(i)-DstTime(j), for min{j|1<=j<i} that
564	   satisfies s[j]>s[i].

566	4.3.4 Discussion

568	   The offset metrics can help predict whether reordered packets will
569	   be useful in a general receiver buffer system with finite limits.
570	   The limit may be the time of storage prior to a cyclic play-out
571	   instant (as with de-jitter buffers).

573	   Note that the One-way IPDV [RFC3393] gives the delay variation for a
574	   packet w.r.t. the preceding packet in the source sequence. Lateness
575	   and IPDV give an indication of whether a buffer at the destination
576	   has sufficient storage to accommodate the network's behavior and
577	   restore order. When an earlier packet in the Source sequence is
578	   lost, IPDV will necessarily be undefined for adjacent packets, and
579	   Late Time may provide the only way to evaluate the usefulness of a
580	   packet.

582	   In the case of de-jitter buffers, there are circumstances where the
583	   receiver employs loss concealment at the intended play-out time of a
584	   late packet. However, if this packet arrives out of order, the Late
585	   Time determines whether the packet is still useful. IPDV no longer
586	   applies, because the receiver establishes a new play-out schedule
587	   with additional buffer delay to accommodate similar events in the
588	   future (this requires very minimal processing).

590	4.4 Reordering Byte Offset

592	   Reordered packets can be assigned offset values indicating the
593	   storage in bytes that a receiver must possess to accommodate them.
594	   The various offset metrics are calculated only on reordered packets,
595	   as identified by the reordered packet singleton metric in Section 3.

597	4.4.1 Metric Name:

599	   Type-P-packet-Byte-Offset-Stream

601	4.4.2 Metric Parameters:

603	   We use the same parameters defined earlier.

605	4.4.3 Definition:

607	   Byte stream offset is the sum of the payload sizes of intervening
608	   in-order packets between the reordered packet and the discontinuity
609	   (including the packet at the discontinuity).

611	   For reordered packet i with a reordering extent e:
612	   ByteOffset(i) = Sum[in-order packets back to reordering discon.]
613	                 = Sum[PayloadSize(packet at i-1 if in-order),
614	                        PayloadSize(packet at i-2 if in-order), ...
615	                        PayloadSize(packet at i-e if in-order)]

617	4.4.4 Discussion

619	   We note that estimates of buffer size due to reordering depend on
620	   greatly on the test stream, in terms of the spacing between test
621	   packets and their size, especially when packet size is variable.

623	   The byte offset metric can help predict whether reordered packets
624	   will be useful in a general receiver buffer system with finite
625	   limits.  The limit is expressed as the number of bytes the buffer
626	   can store.

628	   When packets in the stream have variable sizes, it may be most
629	   useful to characterize offset in terms of the payload size(s) of
630	   stored packets, using the Type-P-packet-Byte-Offset-Stream metric.

632	4.5 Gaps between multiple Reordering Discontinuities

634	4.5.1 Metric Name:

636	   Type-P-packet-Reordering-Gap-Stream

638	4.5.2 Parameters:

640	   We use the same parameters defined earlier.

642	4.5.3 Definition of Reordering Discontinuity:

644	   All reordered packets are associated with a packet at a reordering
645	   discontinuity, defined as the in-order packet s[j] that arrived at
646	   the minimum value of j (1<=j<i) for which s[j]> s[i].

648	   Note that s[j] will have been found to cause a sequence
649	   discontinuity, where s > NextExp when evaluated with the reordered
650	   singleton metric as described in section 3.4.

652	   Recall that i - e = min(j). Subsequent reordered packets may be
653	   associated with the same s[j], or with a different discontinuity.
654	   This definition is used in the definition of the Reordering Gap,
655	   below.

657	4.5.4 Definition of Reordering Gap:

659	   A reordering gap is the distance between successive reordering
660	   discontinuities. Type-P-packet-Reordering-Gap-Stream assigns a value
661	   to (all) packets in a stream.

663	   If:

665	      The packet s[j'] is found to be a reordering discontinuity, based
666	      on the arrival of reordered packet s[i'] with extent e', and

668	      an earlier reordering discontinuity s[j], based on the arrival of
669	      reordered packet s[i] with extent e was already detected, and

671	      i' > i, and

673	      there are no reordering discontinuities between j and j',

675	   then the Reordering Gap for packet s[j'] is the difference between
676	   the arrival positions the reordering discontinuities, as shown
677	   below:

679	   Gap(j')    =   (j')  -  (j)

681	   Otherwise:

683	   The Type-P-packet-Reordering-Gap-Stream for the packet is 0.

685	   Gaps may also be expressed in time:

687	   GapTime(j') = DstTime(j') - DstTime(j)

689	4.5.5 Discussion

691	   When separate reordering discontinuities can be distinguished, then
692	   a count may also be reported (along with the discontinuity
693	   description, such as the number of reordered packets associated with
694	   that discontinuity and their extents and offsets). The Gaps between
695	   a sample's reordering discontinuities may be expressed as a
696	   histogram, to easily summarize the frequency of various gaps.
697	   Reporting the mode, average, range, etc. may also summarize the
698	   distributions.

700	   The Gap metric may help to correlate the frequency of reordering
701	   discontinuities with their cause. Gap lengths are also informative
702	   to receiver designers, revealing the period of reordering
703	   discontinuities. The combination of reordering gaps and extent
704	   reveals whether receivers will be required to handle cases of
705	   overlapping reordered packets.

707	4.6 Reordering-free Runs
708	   This section defines a metric based on a count of consecutive
709	   packets between reordered packets.

711	4.6.1 Metric Name:

713	   Type-P-packet-Reordering-Free-Run-Stream

715	4.6.2 Parameters:

717	   We use the same parameters defined earlier, plus the following:
718	   r, the run counter
719	   n, the number of runs
720	   a, the accumulator of in-order packets
721	   p, the number of packets
722	   q, the squared sum of the run counters

724	4.6.3 Definition:

726	   As packets in a sample arrive at the Destination, the count of
727	   packets to the next reordered packet is a Reordering-Free run. Note
728	   that the minimum run-length is one according to this definition. A
729	   pseudo code example follows:

731	   r = 0; /* r is the run counter */
732	   n = 0; /* n is the number of runs */
733	   a = 0; /* a is the accumulator of in order packets */
734	   p = 0; /* p is the number of packets */
735	   q = 0; /* q is the squared sum of the run counters */

737	   while(packets arrive with sequence number s)
738	   {
739	        p++;
740	        if (s >= NextExp) /* s is in-order */
741	                then r++;
742	                a++;
743	        else    /* s is reordered */
744	                q+= r*r;
745	                r = 1;
746	                n++;
747	   }

749	   Each in-order arrival increments the run counter and the accumulator
750	   of in order packets, each reordered packet resets the run counter
751	   after adding it to the accumulator.

753	   Each arrival of a reordered packet yields a new count in the Run
754	   vector.  Long runs accompany periods where order was maintained,
755	   while short runs indicate frequent, or multi-packet reordering.

757	   The percent of packets in-order is 100*a/p
758	   The average Reordering-Free run length is a/n

760	   The q counter gives an indication of variation of the Reordering-
761	   Free runs from the average by comparing q/a to a/n  ((q/a)/(a/n))

763	4.6.4 Discussion:

765	   Type-P-packet-Reordering-Free-Run-Stream parameters give a brief
766	   summary of the stream's reordering characteristics including the
767	   average reordering-free run length, and the variation of run
768	   lengths, therefore a key application of this metric is network
769	   evaluation.

771	   For example for 36 packets with 3 runs of 11 in-order packets we
772	   have:
773	      p = 36
774	      n = 3
775	      a = 33
776	      q = 3 * (11*11) = 363
777	      ave reordering-free run = 11
778	      q/a = 11
779	      (q/a)/ave = 1.0

781	   For 36 packets with 3 runs, 2 of length 1 and one of length 31
782	      p = 36
783	      n = 3
784	      a = 33
785	      q = 1 + 1 + 961 = 963
786	      ave reordering-free run = 11
787	      q/a = 29.18
788	      (q/a)/ave = 2.65

790	5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric

792	   This section describes a metric that conveys information associated
793	   with the affect of reordering on TCP.  However, in order to infer
794	   anything about TCP performance, the test stream MUST bear a close
795	   resemblance to the TCP sender of interest. RFC 3148 [RFC3148] lists
796	   the specific aspects of congestion control algorithms that must be
797	   specified. Further, RFC 3148 recommends that Bulk Transfer Capacity
798	   metrics SHOULD have instruments to distinguish three cases of packet
799	   reordering (in section 3.3). The sample metrics defined above
800	   satisfy the requirements to classify packets that are slightly or
801	   grossly out-of-order. The metric in this section adds the capability
802	   to distinguish the case where the Fast Retransmit algorithm is
803	   invoked due to reordering. Additional TCP Kernel Instruments are
804	   summarized in [Mat03].

806	5.1 Metric Name:

808	   Type-P-packet-n-Reordering-Stream

810	5.2 Parameter Notation:

812	   Let n be a positive integer (a parameter).  Let k be a positive
813	   integer equal to the number of packets sent (sample size).  Let l be
814	   a non-negative integer representing the number of packets that were
815	   received out of the k packets sent.  (Note that there is no
816	   relationship between k and l: on one hand, losses can make l less
817	   than k; on the other hand, duplicates can make l greater than k.)
818	   Assign each sent packet a sequence number, 1 to k, in order of
819	   packet emission.

821	   Let s[1], s[2], ..., s[l] be the original sequence numbers of the
822	   received packets, in the order of arrival.

824	5.3 Definitions

826	   Definition 1: Received packet number i (n < i <= l), with source
827	   sequence number s[i], is n-reordered if and only if for all j such
828	   that i-n <= j < i, s[j] > s[i].

830	   Claim: If by this definition, a packet's reordering is n and 0 < n'
831	   < n, then the packet is also reordered to the n' extent.

833	   Note: This definition is illustrated by C code in Appendix A.  It
834	   determines the n-reordering for a value of n=3 (when actually
835	   writing applications that would report the metric, one would
836	   probably report it for several values of n, such as 1, 2, 3, 4 --
837	   and maybe a few more consecutive values).

839	   This definition does not assign an n to all reordered packets as
840	   defined by the singleton metric, in particular when blocks of
841	   successive packets are reordered. (In the arrival sequence
842	   s={1,2,3,7,8,9,4,5,6}, packets 4, 5, and 6 are reordered, but only
843	   packet 4 is n-reordered, with n=3.)

845	   Definition 2: The degree of n-reordering of the sample is m/l, where
846	   m is the number of n-reordered packets in the sample.

848	   Definition 3: The degree of "monotonic reordering" of the sample is
849	   its degree of 1-reordering.

851	   Definition 4: A sample is said to have no reordering if its degree
852	   of n-reordering is 0.

854	5.4 Discussion:

856	   The degree of n-reordering may be expressed as a percentage, in
857	   which case the number from Definition 2 is multiplied by 100%.

859	   Knowledge of n-reordering is particularly useful for determining the
860	   portion of reordered packets that can or cannot be restored to order
861	   in a typical TCP receiver buffer based on their arrival order alone
862	   (and without the aid of retransmission).

864	   Important special cases are n=1 and n=3:

866	   - For n=1, absence of 1-reordering means the sequence numbers that
867	   the receiver sees are monotonically increasing with respect to the
868	   previous arriving packet.

870	   - For n=3, a NewReno TCP sender would retransmit 1 packet in
871	   response to an instance of 3-reordering and therefore consider this
872	   packet lost for the purposes of congestion control (the sender will
873	   half its congestion window). Detecting instances of 3-reordering is
874	   useful for determining the portion of reordered packets that are in
875	   fact as good as lost.

877	   A sample's n-reordering may be expressed as a histogram, to
878	   summarize the frequency for each value of n.

880	   We note that the definition of n-reordering cannot predict the exact
881	   number of packets unnecessarily retransmitted by a TCP sender under
882	   some circumstances, such as cases with closely-spaced reordered
883	   singletons. The definition is less complicated than a TCP
884	   implementation where both time and position influence the sender's
885	   behavior.

887	   A packet's n-reordering designation is sometimes equal to its
888	   reordering extent, e. n-reordering is different in the following
889	   ways:

891	   1. n is a count of early packets with consecutive arrival positions
892	   at the receiver.

894	   2. Reordered packets (Type-P-Reordered=TRUE) may not be n-reordered,
895	   but will have an extent, e (see the examples).

897	6. Measurement and Implementation Issues

899	   The results of tests will be dependent on the time interval between
900	   measurement packets (both at the Source, and during transport where
901	   spacing may change).  Clearly, packets launched infrequently (e.g.,
902	   1 per 10 seconds) are unlikely to be reordered.

904	   Test stream designers may prefer to use a periodic sending interval
905	   so that a known temporal bias is maintained, also bringing
906	   simplified results analysis (as described in [RFC3432]). In this
907	   case, it is RECOMMENDED that the periodic sending interval should be
908	   chosen to reproduce the closest Source packet spacing expected (down
909	   to the link speed serialization time limit). Use of the closest
910	   possible spacing should reveal the greatest extent of steady-state
911	   reordering on the path. Of course, packet spacing is likely to vary
912	   as the stream traverses the test path. In any case, the exact method
913	   of packet generation MUST be reported with measurement results,
914	   including all stream parameters.

916	   When intending to compare or concatenate independent measurements of
917	   reordering, it is RECOMMENDED to use the same test stream parameters
918	   in each measurement system.

920	   Packet lengths might also be varied to attempt to detect instances
921	   of parallel processing (they may cause steady state reordering). For
922	   example, a line-speed burst of the longest (MTU-length) packets
923	   followed by a burst of the shortest possible packets may be an
924	   effective detecting pattern.  Other size patterns are possible.

926	   The non-reversing order criterion and all metrics described above
927	   remain valid and useful when a stream of packets experiences packet
928	   loss, or both loss and reordering. In other words, losses alone do
929	   not cause subsequent packets to be declared reordered.

931	   Assuming that the necessary sequence information (sequence number
932	   and/or source time stamp) is included in the packet payload
933	   (possibly in application headers such as RTP), packet sequence may
934	   be evaluated in a passive measurement arrangement.  Also, it is
935	   possible to evaluate order at a single point along a path, since the
936	   usual need for synchronized Src and Dst Clocks may be relaxed to
937	   some extent.

939	   It is possible to apply these metrics to evaluate reordering in a
940	   TCP sender's stream. In this case, the Source sequence numbers would
941	   be based on byte stream, or segment numbering. Since the stream may
942	   include retransmissions due to loss or reordering, care must be
943	   taken to avoid declaring retransmitted packets reordered. The
944	   additional sequence reference of either s or SrcTime help to avoid
945	   this ambiguity.

947	   Since this metric definition may use sequence numbers with finite
948	   range, it is possible that the sequence numbers could reach end-of-
949	   range and roll over to zero during a measurement.  By definition,
950	   the Next Expected value cannot decrease, and all packets received
951	   after a roll-over would be declared reordered.  Sequence number
952	   roll-over can be avoided by using combinations of counter size and
953	   test duration where roll-over is impossible (and sequence is reset
954	   to zero at the start). Also, message-based numbering results in
955	   slower sequence consumption.  There may still be cases where
956	   methodological mitigation of this problem is desirable (e.g., long-
957	   term testing).  The elements of mitigation are:

959	   1. There must be a test to detect if a roll-over has occurred.  It
960	   would be nearly impossible for the sequence numbers of successive
961	   packets to jump by more than half the total range, so these large
962	   discontinuities are designated as roll-over.

964	   2. All sequence numbers used in computations are represented in a
965	   sufficiently large precision.  The numbers have a correction applied
966	   (equivalent to adding a significant digit) whenever roll-over is
967	   detected.

969	   3. Reordered packets coincident with sequence numbers reaching end-
970	   of-range must also be detected for proper application of correction
971	   factor.

973	   Ideally, the test instrument would have the ability to use all
974	   earlier packets at any point in the test stream. In practice, there
975	   will be limited ability to determine reordering extent, due to the
976	   storage requirements for previous packets. Saving only packets that
977	   indicate discontinuities (and their arrival positions) will reduce
978	   storage volume.

980	   Another solution is to use a sliding history window of packets,
981	   where the window size would be determined by an upper bound on the
982	   useful reordering extent. This bound could be several packets or
983	   several seconds-worth of packets, depending on the intended
984	   analysis. When discarding all stream information beyond the window,
985	   the reordering extent or degree of n-reordering may need to be
986	   expressed as greater than the window length if the reordering
987	   discontinuity information has been discarded, and Gap calculations
988	   would not be possible.

990	   The requirement to ignore duplicate packets also mandates storage.
991	   Here, tracking the sequence numbers of missing packets may minimize
992	   storage size. Missing packets may eventually be declared lost, or
993	   reordered if they arrive. The missing packet list and the largest
994	   sequence number received thus far (NextExp - 1) are sufficient
995	   information to determine if a packet is a duplicate (assuming a
996	   manageable storage size for packets that are missing due to loss).

998	   Some in-order packet arrivals may not be useful to TCP receivers,
999	   due to the receiver window. Sequence Discontinuities and their size
1000	   are defined in section 3.4, and this information may be useful to
1001	   determine whether a packet is useful or not.

1003	   Last, we note that determining reordering extents and gaps is tricky
1004	   when there are overlapped or nested events. Test instrument
1005	   complexity and reordering complexity are directly correlated.

1007	7. Examples of Arrival Order Evaluation

1009	   This section provides some examples to illustrate how the non-
1010	   reversing order criterion works, how n-reordering works in
1011	   comparison, and the value of viewing reordering in all the
1012	   dimensions of time, bytes, and position.

1014	   Throughout this section, we will refer to packets by their source
1015	   sequence number, except where noted.  So "Packet 4" refers to the
1016	   packet with source sequence number 4, and the reader should refer to
1017	   the tables in each example to determine packet 4's arrival index
1018	   number, if needed.

1020	7.1 Example with a single packet reordered

1022	   Table 1 gives a simple case of reordering, where one packet is
1023	   reordered, Packet 4. Packets are listed according to their arrival,
1024	   and message numbering is used.

1026	   Table 1 Example with Packet 4 Reordered,
1027	   Sending order(SrcNum@Src): 1,2,3,4,5,6,7,8,9,10
1028	   s            Src     Dst                     Dst     Byte    Late
1029	   @Dst NextExp Time    Time    Delay   IPDV    Order   Offset  Time
1030	    1     1       0      68      68              1
1031	    2     2      20      88      68       0      2
1032	    3     3      40     108      68       0      3
1033	    5     4      80     148      68     -82      4
1034	    6     6     100     168      68       0      5
1035	    7     7     120     188      68       0      6
1036	    8     8     140     208      68       0      7
1037	    4     9      60     210     150      82      8      400     62
1038	    9     9     160     228      68       0      9
1039	   10    10     180     248      68       0     10

1041	   Each column gives the following information:

1043	   s        Packet sequence number at the Source.
1044	   NextExp  The value of NextExp when the packet arrived(before
1045	   update).
1046	   SrcTime  Packet time stamp at the Source, ms.
1047	   DstTime  Packet time stamp at the Destination, ms.
1048	   Delay    1-way delay of the packet, ms.
1049	   IPDV     IP Packet Delay Variation, ms
1050	            IPDV = Delay(SrcNum)-Delay(SrcNum-1)
1051	   DstOrder Order in which the packet arrived at the Destination.
1052	   Byte Offset  The Byte Offset of a reordered packet, in bytes.
1053	   LateTime The lateness of a reordered packet, in ms.

1055	   We can see that when Packet 4 arrives, NextExp=9, and it is declared
1056	   reordered. We compute the extent of reordering as follows:

1058	   Using the notation <s[1], ..., s[i], ..., s[L]>, the received
1059	   packets are represented as:

1061	                            \/
1062	   s = 1, 2, 3, 5, 6, 7, 8, 4, 9, 10
1063	   i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
1064	                            /\

1066	   Applying the definition of Type-P-packet-Reordering-Extent-Stream:
1067	   when j=7, 8 > 4, so the reordering extent is 1 or more.
1068	   when j=6, 7 > 4, so the reordering extent is 2 or more.
1069	   when j=5, 6 > 4, so the reordering extent is 3 or more.
1070	   when j=4, 5 > 4, so the reordering extent is 4 or more.
1071	   when j=3, but 3 < 4, and 4 is the maximum extent, e=4 (assuming
1072	   there are no earlier sequence discontinuities, as in this example).

1074	   Further, we can compute the Late Time (210-148=62ms using DstTime)
1075	   compared to Packet 5's arrival.  If the receiver has a de-jitter
1076	   buffer that holds more than 4 packets, or at least 62 ms storage,
1077	   Packet 4 may be useful. Note that 1-way delay and IPDV indicate
1078	   unusual behavior for Packet 4. Also, if Packet 4 had arrived at
1079	   least 62ms earlier, it would have been in-order in this example.

1081	   If all packets contained 100 byte payloads, then Byte Offset is
1082	   equal to 400 bytes.

1084	   Following the definitions of section 5.1, Packet 4 is designated 4-
1085	   reordered.

1087	7.2 Example with two packets reordered

1089	   Table 2 Example with Packets 5 and 6 Reordered,
1090	   Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10
1091	   s            Src     Dst                     Dst     Byte    Late
1092	   @Dst NextExp Time    Time    Delay   IPDV    Order   Offset  Time
1093	    1     1       0      68      68              1
1094	    2     2      20      88      68       0      2
1095	    3     3      40     108      68       0      3
1096	    4     4      60     128      68       0      4
1097	    7     5     120     188      68     -22      5
1098	    5     8      80     189     109      41      6      100     1
1099	    6     8     100     190      90     -19      7      100     2
1100	    8     8     140     208      68       0      8
1101	    9     9     160     228      68       0      9
1102	   10    10     180     248      68       0     10

1104	   Table 2 shows a case where Packets 5 and 6 arrive just behind Packet
1105	   7, so both 5 and 6 are reordered. The Late times (189-188=1, 190-
1106	   188=2) are small.

1108	   Using the notation <s[1], ..., s[i], ..., s[l]>, the received
1109	   packets are represented as:

1111	                      \/ \/
1112	   s = 1, 2, 3, 4, 7, 5, 6, 8, 9, 10
1113	   i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
1114	                      /\ /\

1116	   Considering Packet 5 first:
1117	   when j=5, 7 > 5, so the reordering extent is 1 or more.
1118	   when j=4, we have 4 < 5, so 1 is its maximum extent, and e=1.

1120	   Considering Packet 6 next:
1121	   when j=6, 5 < 6, the extent is not yet defined.
1122	   when j=5, 7 > 6, so the reordering extent is i-j=2 or more.
1123	   when j=4, 4 < 6, and we find 2 is its maximum extent, and e=2.

1125	   We can also associate each of these reordered packets with a
1126	   reordering discontinuity. We find the minimum j=5 (for both packets)
1127	   according to Section 4.2.3. So Packet 6 is associated with the same
1128	   reordering discontinuity as Packet 5, the Reordering Discontinuity
1129	   at Packet 7.

1131	   This is a case where reordering extent e would over-estimate the
1132	   packet storage required to restore order. Only one packet storage is
1133	   required (to hold Packet 7), but e=2 for Packet 6.

1135	   Following the definitions of section 5, Packet 5 is designated 1-
1136	   reordered, but Packet 6 is not designated n-reordered.

1138	   A hypothetical sender/receiver pair may retransmit Packet 5
1139	   unnecessarily, since it is 1-reordered (in agreement with the
1140	   singleton metric). Though Packet 6 may not be unnecessarily
1141	   retransmitted, the receiver cannot advance Packet 7 to the higher
1142	   layers until after Packet 6 arrives. Therefore, the singleton metric
1143	   correctly determined that Packet 6 is reordered.

1145	7.3 Example with three packets reordered

1147	   Table 3 Example with Packets 4, 5, and 6 reordered
1148	   Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11
1149	   s            Src     Dst                     Dst     Byte    Late
1150	   @Dst NextExp Time    Time    Delay   IPDV    Order   Offset  Time
1151	    1    1        0      68      68              1
1152	    2    2       20      88      68       0      2
1153	    3    3       40     108      68       0      3
1154	    7    4      120     188      68     -88      4
1155	    8    8      140     208      68       0      5
1156	    9    9      160     228      68       0      6
1157	   10   10      180     248      68       0      7
1158	    4   11       60     250     190     122      8      400     62
1159	    5   11       80     252     172     -18      9      400     64
1160	    6   11      100     256     156     -16     10      400     68
1161	   11   11      200     268      68       0     11

1163	   The case in Table 3 is where three packets in sequence have long
1164	   transit times (Packets with s = 4,5,and 6). Delay, Late time, and
1165	   Byte Offset capture this very well, and indicate variation in
1166	   reordering extent, while IPDV indicates that the spacing between
1167	   packets 4,5,and 6 has changed.

1169	   The histogram of Reordering extents (e) would be:

1171	   Bin         1  2  3  4  5  6  7
1172	   Frequency   0  0  0  1  1  1  0

1174	   Using the notation <s[1], ..., s[i], ..., s[l]>, the received
1175	   packets are represented as:

1177	   s = 1, 2, 3, 7, 8, 9,10, 4, 5, 6, 11
1178	   i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11

1180	   We first calculate the n-reordering. Considering Packet 4 first:
1181	   when n=1, 7<=j<8, and 10> 4, so the packet is 1-reordered.
1182	   when n=2, 6<=j<8, and 9 > 4, so the packet is 2-reordered.
1183	   when n=3, 5<=j<8, and 8 > 4, so the packet is 3-reordered.
1184	   when n=4, 4<=j<8, and 7 > 4, so the packet is 4-reordered.
1185	   when n=5, 3<=j<8, but 3 < 4, and 4 is the maximum n-reordering.

1187	   Considering packet 5[9] next:
1188	   when n=1, 8<=j<9, but 4 < 5, so the packet at i=9 is not designated
1189	   as n-reordered. We find the same to for Packet 6.

1191	   We now consider whether reordered Packets 5 and 6 are associated
1192	   with the same reordering discontinuity as Packet 4.  Using the test
1193	   of Section 4.2.3, we find that the minimum j=4 for all three
1194	   packets. They are all associated with the reordering discontinuity
1195	   at Packet 7.

1197	   This example shows again that the n-reordering definition identifies
1198	   a single Packet (4) with a sufficient degree of reordering to result
1199	   in one unnecessary packet retransmission by the New Reno TCP sender.
1200	   Also, the reordered arrival of Packets 5 and 6 will allow the
1201	   receiver process to pass Packets 7 through 10 up the protocol stack
1202	   (the singleton Type-P-Reordered = TRUE for Packets 5 and 6, and they
1203	   are all associated with a single reordering discontinuity).

1205	7.4 Example with Multiple Packet Reordering Discontinuities

1207	   Table 4 Example with Multiple Packet Reordering Discontinuities
1208	   Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16

1210	          Discontinuity         Discontinuity
1211	                |---------Gap---------|
1212	   s = 1, 2, 3, 6, 7, 4, 5, 8, 9, 10, 12, 13, 11, 14, 15, 16
1213	   i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

1215	   r = 1, 2, 3, 4, 5, 1, 1, 2, 3,  4,  5,  6,  1,  2,  3,  4, ...
1216	   number of runs,n = 1  2                     3
1217	   end r counts =     5  1                     6

1219	   Packet 4 has extent e=2, Packet 5 has extent e=3, and Packet 11 has
1220	   e=2. There are two different reordering discontinuities, one at
1221	   Packet 6 (where j=4) and one at Packet 12 (where j'=11).

1223	   According to the definition of Reordering Gap
1224	   Gap(j') = (j') - (j)
1225	   Gap(11) = (11) - (4) = 7

1227	   We also have three reordering-free runs of lengths 5, 1, and 6.

1229	   The differences between these two multiple-event metrics are evident
1230	   here.  Gaps are the distance between sequence discontinuities that
1231	   are subsequently defined as reordering discontinuities, while
1232	   reordering-free runs capture the distance between reordered packets.

1234	8. Security Considerations

1236	8.1 Denial of Service Attacks

1238	   This metric requires a stream of packets sent from one host (source)
1239	   to another host (destination) through intervening networks.  This
1240	   method could be abused for denial of service attacks directed at
1241	   destination and/or the intervening network(s).

1243	   Administrators of source, destination, and the intervening
1244	   network(s) should establish bilateral or multi-lateral agreements
1245	   regarding the timing, size, and frequency of collection of sample
1246	   metrics.  Use of this method in excess of the terms agreed between
1247	   the participants may be cause for immediate rejection or discard of
1248	   packets or other escalation procedures defined between the affected
1249	   parties.

1251	8.2 User data confidentiality

1253	   Active use of this method generates packets for a sample, rather
1254	   than taking samples based on user data, and does not threaten user
1255	   data confidentiality. Passive measurement must restrict attention to
1256	   the headers of interest. Since user payloads may be temporarily
1257	   stored for length analysis, suitable precautions MUST be taken to
1258	   keep this information safe and confidential.

1260	8.3 Interference with the metric

1262	   It may be possible to identify that a certain packet or stream of
1263	   packets is part of a sample. With that knowledge at the destination
1264	   and/or the intervening networks, it is possible to change the
1265	   processing of the packets (e.g. increasing or decreasing delay) that
1266	   may distort the measured performance.  It may also be possible to
1267	   generate additional packets that appear to be part of the sample
1268	   metric. These additional packets are likely to perturb the results
1269	   of the sample measurement.

1271	   To discourage the kind of interference mentioned above, packet
1272	   interference checks, such as cryptographic hash, may be used.

1274	9. IANA Considerations

1276	   Since this metric does not define a protocol or well-known values,
1277	   there are no IANA considerations in this memo.

1279	10. Normative References

1281	   [RFC791]   Postel, J., "Internet Protocol", STD 5, RFC 791,
1282	              September 1981.
1283	              Obtain via: http://www.rfc-editor.org/rfc/rfc791.txt

1285	   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
1286	              Requirement Levels", RFC 2119, March 1997.
1287	              Obtain via: http://www.rfc-editor.org/rfc/rfc2119.txt

1289	   [RFC2330]  Paxson, V., Almes, G., Mahdavi, J., and Mathis, M.,
1290	              "Framework for IP Performance Metrics", RFC 2330, May
1291	              1998.
1292	              Obtain via: http://www.rfc-editor.org/rfc/rfc2330.txt

1294	   [RFC3148]  Mathis, M. and Allman, M., "A Framework for Defining
1295	              Empirical Bulk Transfer Capacity Metrics", RFC 3148, July
1296	              2001.
1297	              Obtain via: http://www.rfc-editor.org/rfc/rfc3148.txt

1299	   [RFC3432]  Raisanen, V., Grotefeld, G., and Morton, A., "Network
1300	              performance measurement with periodic streams", RFC 3432,
1301	              November 2002.

1303	11. Informative References

1305	   [Bel02]    J.Bellardo and S.Savage, "Measuring Packet Reordering,"
1306	              Proceedings of the ACM SIGCOMM Internet Measurement
1307	              Workshop 2002, November 6-8, Marseille, France.

1309	   [Ben99]    J.C.R.Bennett, C.Partridge, and N.Shectman, "Packet
1310	              Reordering is Not Pathological Network Behavior,"
1311	              IEEE/ACM Transactions on Networking, vol.7, no.6, pp.789-
1312	              798, December 1999.

1314	   [Cia00]    L.Ciavattone and A.Morton, "Out-of-Sequence Packet
1315	              Parameter Definition (for Y.1540)", Contribution number
1316	              T1A1.3/2000-047, October 30, 2000.
1317	              ftp://ftp.t1.org/pub/t1a1/2000-A13/0a130470.doc

1319	   [Cia03]    L.Ciavattone, A.Morton, and G.Ramachandran, "Standardized
1320	              Active Measurements on a Tier 1 IP Backbone," IEEE
1321	              Communications Mag., pp 90-97, June 2003.

1323	   [Jai02]    S.Jaiswal et al., "Measurement and Classification of Out-
1324	              of-Sequence Packets in a Tier-1 IP Backbone," Proceedings
1325	              of the ACM SIGCOMM Internet Measurement Workshop 2002,
1326	              November 6-8, Marseille, France.

1328	   [Lou01]    D.Loguinov and H.Radha, "Measurement Study of Low-bitrate
1329	              Internet Video Streaming", Proceedings of the ACM SIGCOMM
1330	              Internet Measurement Workshop 2001 November 1-2, 2001,
1331	              San Francisco, USA.

1333	   [Mat03]    M. Mathis, J Heffner and R Reddy, "Web100: Extended TCP
1334	              Instrumentation for Research, Education and Diagnosis",
1335	              ACM Computer Communications Review, Vol 33, Num 3, July
1336	              2003. http://www.web100.org/docs/mathis03web100.pdf

1338	   [Pax98]    V.Paxson, "Measurements and Analysis of End-to-End
1339	              Internet Dynamics," Ph.D. dissertation, U.C. Berkeley,
1340	              1997, ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz.

1342	   [RFC793]   Postel, J., "Transmission Control Protocol", STD 7, RFC
1343	              793, September 1981.
1344	              Obtain via: http://www.rfc-editor.org/rfc/rfc793.txt

1346	   [RFC3393]  Demichelis, C., and Chimento, P., "IP Packet Delay
1347	              Variation Metric for IP Performance Metrics (IPPM)", RFC
1348	              3393, November 2002.

1350	12. Acknowledgments

1352	   The authors would like to acknowledge many helpful discussions with
1353	   Matt Zekauskas, Jon Bennett (who authored the sections on
1354	   Reordering-Free Runs), and Matt Mathis. We thank David Newman, Henk
1355	   Uijterwall, and Mark Allman for their reviews and suggestions, and
1356	   Michal Przybylski for sharing implementation experiences with us on
1357	   the ippm-list. We gratefully acknowledge the foundation laid by the
1358	   authors of the IP performance Framework [RFC2330].

1360	13. Appendix A Example Implementations in C (Informative)

1362	   Two example c-code implementations of reordering definitions follow:

1364	   Example 1  n-reordering ============================================

1366	   #include <stdio.h>

1368	   #define MAXN   100

1370	   #define min(a, b) ((a) < (b)? (a): (b))
1371	   #define loop(x) ((x) >= 0? x: x + MAXN)

1373	   /*
1374	    * Read new sequence number and return it. Return a sentinel value
1375	    * of EOF (at least once) when there are no more sequence numbers.
1376	    * In this example, the sequence numbers come from stdin;
1377	    * in an actual test, they would come from the network.
1378	    *
1379	   */
1380	   int
1381	   read_sequence_number()
1382	   {
1383	           int     res, rc;
1384	           rc = scanf("%d\n", &res);
1385	           if (rc == 1) return res;
1386	           else return EOF;
1387	   }

1389	   int
1390	   main()
1391	   {
1392	           int     m[MAXN];       /* We have m[j-1] == number of
1393	                                            * j-reordered packets. */
1394	           int     ring[MAXN];    /* Last sequence numbers seen. */
1395	           int     r = 0;          /* Ring pointer for next write. */
1396	           int     l = 0;        /* Number of sequence numbers read. */
1397	           int     s;              /* Last sequence number read. */
1398	           int     j;

1400	           for (j = 0; j < MAXN; j++) m[j] = 0;
1401	           for (;(s = read_sequence_number())!= EOF;l++,r=(r+1)%MAXN) {
1402	             for (j=0; j<min(l, MAXN)&&s<ring[loop(r-j-1)];j++) m[j]++;
1403	             ring[r] = s;
1404	           }
1405	           for (j = 0; j < MAXN && m[j]; j++)
1406	             printf("%d-reordering = %f%%\n", j+1, 100.0*m[j]/(l-j-1));
1407	           if (j == 0) printf("no reordering\n");
1408	           else if (j < MAXN) printf("no %d-reordering\n", j+1);
1409	           else printf("only up to %d-reordering is handled\n", MAXN);
1410	           exit(0);
1411	   }

1413	   Example 2   singleton and n-reordering comparison =================

1415	   #include <stdio.h>

1417	   #define MAXN   100
1418	   #define min(a, b) ((a) < (b)? (a): (b))
1419	   #define loop(x) ((x) >= 0? x: x + MAXN)

1421	   /* Global counters */
1422	   int receive_packets=0;       /* number of recieved */
1423	   int reorder_packets=0;       /* number of reordered packets */

1425	   /* function to test if current packet has been reordered
1426	    * returns 0 = not reordered
1427	    *         1 = reordered
1428	    */
1429	   int testorder1(int seqnum)   // Al
1430	   {
1431	        static int NextExp = 1;
1432	        int iReturn = 0;

1434	        if (seqnum >= NextExp) {
1435	                NextExp = seqnum+1;
1436	        } else {
1437	                iReturn = 1;
1438	        }
1439	        return iReturn;
1440	   }

1442	   int testorder2(int seqnum)   // Stanislav
1443	   {
1444	           static int  ring[MAXN];    /* Last sequence numbers seen. */
1445	           static int  r = 0;         /* Ring pointer for next write */
1446	           int   l = 0;          /* Number of sequence numbers read. */
1447	           int   j;
1448	           int  iReturn = 0;

1450	           l++;
1451	           r = (r+1) % MAXN;
1452	           for (j=0; j<min(l, MAXN) && seqnum<ring[loop(r-j-1)]; j++)
1453	                    iReturn = 1;
1454	           ring[r] = seqnum;
1455	      return iReturn;
1456	   }
1457	   int main(int argc, char *argv[])
1458	   {
1459	           int i, packet;
1460	        for (i=1; i< argc; i++) {
1461	                receive_packets++;
1462	                packet = atoi(argv[i]);
1463	                reorder_packets += testorder2(packet);
1464	        }
1465	        printf("Received packets = %d, Reordered packets = %d\n",
1466	   receive_packets, reorder_packets);
1467	        exit(0);
1468	   }

1470	   Reference

1472	   ISO/IEC 9899:1999 (E), as amended by ISO/IEC 9899:1999/Cor.1:2001
1473	   (E). Also published as:

1475	   The C Standard: Incorporating Technical Corrigendum 1, British
1476	   Standards Institute, ISBN: 0-470-84573-2, Hardcover, 558 pages,
1477	   September 2003.

1479	14. Appendix B Fragment Order Evaluation (Informative)

1481	   Section 3 stated that fragment re-assembly is assumed prior to order
1482	   evaluation, but that similar procedures could be applied prior to
1483	   re-assembly.  This appendix gives definitions and procedures to
1484	   identify reordering in a packet stream that includes fragmentation.

1486	14.1 Metric Name:

1488	   The Metric retains the same name, Type-P-Reordered, but additional
1489	   parameters are required.

1491	   This Appendix assumes that the device that divides a packet into
1492	   fragments send them according to ascending fragment offset. Early
1493	   Linux OS sent fragments in reverse order, so this possibility is
1494	   worth checking.

1496	14.2 Additional Metric Parameters:

1498	   +  MoreFrag, the state of the More Fragments Flag in the IP header

1500	   +  FragOffset, the offset from the beginning of a fragmented packet,
1501	      in 8 octet units (also from the IP header).

1503	   +  FragSeq#, the sequence number from the IP header of a fragmented
1504	      packet currently under evaluation for reordering. When set to
1505	      zero, fragment evaluation is not in progress.

1507	   +  NextExpFrag, the Next Expected Fragment Offset at the
1508	      Destination, in 8 octet units. Set to zero when fragment
1509	      evaluation is not in progress.

1511	   The packet sequence number, s, is assumed to be the same as the IP
1512	   header sequence number. Also, the value of NextExp does not change
1513	   with the in-order arrival of fragments. NextExp is only updated when
1514	   a last fragment or a complete packet arrives.

1516	   Note that packets with missing fragments MUST be declared lost, and
1517	   the Reordering status of any fragments that do arrive MUST be
1518	   excluded from sample metrics.

1520	14.3 Definition:

1522	   The value of Type-P-Reordered is typically false (the packet is in-
1523	   order) when

1525	   * the sequence number s >= NextExp,

1527	   * AND the fragment offset FragOffset >= NextExpFrag

1529	   However, it more efficient to define reordered conditions exactly,
1530	   and designate Type-P-Reordered as False otherwise.

1532	   The value of Type-P-Reordered is defined as True (the packet is
1533	   reordered) under the conditions below. In these cases, the NextExp
1534	   value does not change.

1536	   Case 1: if s < NextExp

1538	   Case 2: if s < FragSeq#

1540	   Case 3: if s>= NextExp AND s = FragSeq# AND FragOffset < NextExpFrag

1542	   This definition can also be illustrated in pseudo-code. A draft
1543	   version of the code follows, and some simplification may be
1544	   possible. A challenging aspect surrounds the housekeeping for the
1545	   new parameters.

1547	   NextExp=0;
1548	   NextExpFrag=0;
1549	   FragSeq#=0;

1551	   while(packets arrive with s, MoreFrag, FragOffset)
1552	   {
1553	   if (s>=NextExp AND MoreFrag==0 AND s>=FragSeq#){
1554	        /* a normal packet or last frag of an in-order packet arrived
1555	   */
1556	        NextExp = s+1;
1557	        FragSeq# = 0;
1558	        NextExpFrag = 0;
1559	        Reordering = False;
1560	        }
1561	   if (s>=NextExp AND MoreFrag==1 AND s>FragSeq#>=0){
1562	        /* a fragment of a new packet arrived, possibly with a
1563	        higher sequence number than the current fragmented packet */
1564	        FragSeq# = s;
1565	        NextExpFrag = FragOffset+1;
1566	        Reordering = False;
1567	        }
1568	   if (s>=NextExp AND MoreFrag==1 AND s==FragSeq#){
1569	        /* a fragment of the "current packet s" arrived */
1570	        if (FragOffset >= NextExpFrag){
1571	                NextExpFrag = FragOffset+1;
1572	                Reordering = False;
1573	                }
1574	        else{
1575	                Reordering = True; /* fragment reordered  */
1576	                }
1577	        }
1578	   if (s>=NextExp AND MoreFrag==1 AND s < FragSeq#){
1579	        /* case where a late fragment arrived,
1580	           for illustration only, redundant with else below*/
1581	        Reordering = True;
1582	        }
1583	   else { /* when s < NextExp, or MoreFrag==0 AND s < FragSeq# */
1584	        Reordering = True;
1585	        }
1586	   }

1588	   A working version of the code would include a check to ensure that
1589	   all fragments of a packet arrive before using the Reordered status
1590	   further, such as in sample metrics.

1592	14.4 Discussion: Notes on Sample Metrics when evaluating Fragments

1594	   All fragments with the same Source Sequence Number are assigned the
1595	   same Source Time.

1597	   Evaluation with byte stream numbering may be simplified if the
1598	   fragment offset is simply added to the SourceByte of the first
1599	   packet (with fragment offset = 0), keeping the 8 octet units of the
1600	   offset in mind.

1602	15. Author's Addresses

1604	   Al Morton
1605	   AT&T Labs
1606	   Room D3 - 3C06
1607	   200 Laurel Ave. South
1608	   Middletown, NJ 07748 USA
1609	   Phone  +1 732 420 1571
1610	   EMail: <acmorton@att.com>

1612	   Len Ciavattone
1613	   AT&T Labs
1614	   Room C4 - 2B29
1615	   200 Laurel Ave. South
1616	   Middletown, NJ 07748 USA
1617	   Phone  +1 732 420 1239
1618	   EMail: <lencia@att.com>

1620	   Gomathi Ramachandran
1621	   AT&T Labs
1622	   Room C4 - 3D22
1623	   200 Laurel Ave. South
1624	   Middletown, NJ 07748 USA
1625	   Phone  +1 732 420 2353
1626	   EMail: <gomathi@att.com>

1628	   Stanislav Shalunov
1629	   Internet2
1630	   200 Business Park Drive, Suite 307
1631	   Armonk, NY 10504
1632	   Phone: + 1 914 765 1182
1633	   EMail: <shalunov@internet2.edu>

1635	   Jerry Perser
1636	   Consultant
1637	   Calabasas, CA 91302  USA
1638	   Phone: + 1
1639	   EMail: <jerry@perser.org>

1641	Full Copyright Statement

1643	   Copyright (C) The Internet Society (2004).  This document is subject
1644	   to the rights, licenses and restrictions contained in BCP 78 and
1645	   except as set forth therein, the authors retain all their rights.

1647	   This document and the information contained herein are provided on
1648	   an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE
1649	   REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE
1650	   INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR
1651	   IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
1652	   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
1653	   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

1655	Intellectual Property
1656	   The IETF takes no position regarding the validity or scope of any
1657	   Intellectual Property Rights or other rights that might be claimed
1658	   to pertain to the implementation or use of the technology described
1659	   in this document or the extent to which any license under such
1660	   rights might or might not be available; nor does it represent that
1661	   it has made any independent effort to identify any such rights.
1662	   Information on the procedures with respect to rights in RFC
1663	   documents can be found in BCP 78 and BCP 79.

1665	   Copies of IPR disclosures made to the IETF Secretariat and any
1666	   assurances of licenses to be made available, or the result of an
1667	   attempt made to obtain a general license or permission for the use
1668	   of such proprietary rights by implementers or users of this
1669	   specification can be obtained from the IETF on-line IPR repository
1670	   at http://www.ietf.org/ipr.

1672	   The IETF invites any interested party to bring to its attention any
1673	   copyrights, patents or patent applications, or other proprietary
1674	   rights that may cover technology that may be required to implement
1675	   this standard.  Please address the information to the IETF at ietf-
1676	   ipr@ietf.org.

1678	Acknowledgement

1680	   Funding for the RFC Editor function is currently provided by the
1681	   Internet Society.