idnits 2.17.1 

draft-ietf-ippm-reordering-09.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 1807.

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

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

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

  ** 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 1596 has weird spacing: '...tic int  ring[...'

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

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

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

  == Line 1600 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 1299

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

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

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

  == Missing Reference: 'MAXN' is mentioned on line 1596, 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)

  -- Obsolete informational reference (is this intentional?): RFC 1323
     (Obsoleted by RFC 7323)

  -- Obsolete informational reference (is this intentional?): RFC 2581
     (Obsoleted by RFC 5681)

  -- Obsolete informational reference (is this intentional?): RFC 2960
     (Obsoleted by RFC 4960)


     Summary: 9 errors (**), 0 flaws (~~), 8 warnings (==), 14 comments (--).

     Run idnits with the --verbose option for more detailed information about
     the items above.

--------------------------------------------------------------------------------


2	Network Working Group                                          A.Morton
3	Internet Draft                                             L.Ciavattone
4	Document: <draft-ietf-ippm-reordering-09.txt>            G.Ramachandran
5	Category: Standards Track                                     AT&T Labs
6	                                                             S.Shalunov
7	                                                              Internet2
8	                                                               J.Perser
9	                                                             Consultant

11	                     Packet Reordering Metric for IPPM

13	Status of this Memo

15	   This document is an Internet-Draft and is subject to all provisions
16	   of section 3 of RFC 3667. By submitting this Internet-Draft, each
17	   author represents that any applicable patent or other IPR claims of
18	   which he or she is aware have been disclosed, and any of which he or
19	   she becomes aware will be disclosed, in accordance with RFC 3668.

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

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

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

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

37	Copyright Notice

39	   Copyright (C) The Internet Society (2005).

41	Abstract

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

57	Contents

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

135	1. Conventions used in this document

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

146	   In this memo, the characters "<=" should be read as "less than or
147	   equal to" and ">=" as "greater than or equal to".

149	2. Introduction

151	   Ordered arrival is a property found in packets that transit their
152	   path, where the packet sequence number increases with each new
153	   arrival and there are no backward steps. The Internet Protocol
154	   [RFC791] has no mechanisms to assure either packet delivery or
155	   sequencing, and higher layer protocols (above IP) should be prepared
156	   to deal with both loss and reordering. This memo defines reordering
157	   metrics.

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

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

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

180	2.1 Motivation

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

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

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

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

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

230	2.2 Goals and Objectives

232	   The definitions below intend to satisfy the goals of:

234	     1. Determining whether or not packet reordering has occurred.
235	     2. Quantifying the degree of reordering. (We define a number of
236	        metrics to meet this goal, because receiving procedures differ
237	        by protocol or application. Since the affects of packet
238	        reordering vary with these procedures, a metric that quantifies
239	        a key aspect of one receiver's behavior could be irrelevant to
240	        a different receiver.)

242	   Reordering Metrics MUST:

244	   +  have one or more applications, such as receiver design or network
245	      characterization, and a compelling relevance in the working
246	      group's view.
247	   +  be computable "on the fly"
248	   +  work even if the stream has duplicate or lost packets

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

253	   +  ability to concatenate results for segments measured separately
254	      to estimate the reordering of an entire path
255	   +  simplicity for easy consumption and understanding
256	   +  relevance to TCP design
257	   +  relevance to Real-time application performance
258	   The current set of metrics meet all the requirements above and
259	   provides all but the concatenation attribute (except in the case
260	   where segments exhibit no reordering, and one may estimate that the
261	   segment concatenation would also exhibit this desirable outcome).
262	   However, satisfying these goals restricts the set of metrics to
263	   those that provide some clear insight into network characterization
264	   or receiver design. They are not likely to be exhaustive in their
265	   coverage of reordering effects on applications, and additional
266	   measurements may be possible.

268	2.3 Required Context for All Reordering Metrics

270	   A critical aspect of all reordering metrics is their inseparable
271	   bond with the measurement conditions. Packet reordering is not well
272	   defined unless the full measurement context is reported. Therefore,
273	   all reordering metric definitions include the following parameters:

275	   1. The "Packet of Type-P" [RFC2330] identifiers for the packet
276	   stream, including the transport addresses for source and
277	   destination, and any other information which may result in different
278	   packet treatments.

280	   2. The stream parameter set for the sending discipline, such as the
281	   parameters unique to Periodic Streams (as in RFC 3432 [RFC3432]),
282	   TCP-like Streams (as in RFC 3148 [RFC3148]), or Poisson Streams (as
283	   in RFC 2330 [RFC2330]. The stream parameters include the packet
284	   size, either specified as a fixed value or as a pattern of sizes (as
285	   applicable).

287	   Whenever a metric is reported, it MUST include a description of
288	   these parameters to provide a context for the results.

290	3. A Reordered Packet Singleton Metric

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

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

301	   The evaluation of packet order requires several supporting concepts.
302	   The first is an algorithm (function) that produces a series of
303	   monotonically increasing identifiers applied to packets at the
304	   source to uniquely establish the order of packet transmission.  The
305	   unique sequence identifier may simply be an incrementing integer
306	   message number, as used below.

308	   The second supporting concept is a stored value which is the "next
309	   expected" packet number. Under normal conditions, the value of Next
310	   Expected (NextExp) is the sequence number of the previous packet
311	   plus 1 for message numbering (in general, the receiver reproduces
312	   the sender's algorithm and the sequence of identifiers so that the
313	   "next expected" can be determined).

315	   Each packet within a packet stream can be evaluated with this order
316	   singleton metric.

318	3.1 Metric Name:

320	   Type-P-Reordered

322	3.2 Metric Parameters:

324	   +  Src, the IP address of a host

326	   +  Dst, the IP address of a host

328	   +  SrcTime, the time of packet emission from the Source (or wire
329	      time)

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

334	   +  NextExp, the Next Expected Sequence number at the Destination, in
335	      units of messages.

337	   And optionally:

339	   +  PayloadSize, the number of bytes contained in the information
340	      field and referred to when the SrcByte sequence is based on bytes
341	      transfered.

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

346	3.3 Definition:

348	   If a packet s, (sent at time, SrcTime) is found to be reordered by
349	   comparison with the Next Expected value, its Type-P-Reordered =
350	   TRUE; otherwise Type-P-Reordered = FALSE, as defined below:

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

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

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

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

364	   On successful arrival of a packet with sequence number s:
365	        if s >= NextExp then /* s is in-order */
366	                NextExp = s + 1;
367	                Type-P-Reordered = False;
368	        else     /* when s < NextExp */
369	                Type-P-Reordered = True

371	3.4 Sequence Discontinuity Definition

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

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

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

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

389	   In pseudo-code:

391	   On successful arrival of a packet with sequence number s:
392	        if s >= NextExp, then /* s is in-order */
393	                if s > NextExp then
394	                          SequenceDiscontinuty = True;
395	                          SeqDiscontinutySize = s - NextExp;
396	                else
397	                          SequenceDiscontinuty = False;
398	                NextExp = s + 1;
399	                Type-P-Reordered = False;

401	        else /* when s < NextExp */
402	                Type-P-Reordered = True;
403	                SequenceDiscontinuty = False;

405	   Whether there are any Sequence Discontinuities and their size is
406	   determined by the conditions causing loss and/or reordering along
407	   the measurement path. Note that a packet could be reordered at one
408	   point, and subsequently lost elsewhere on the path, but this cannot
409	   be known from observations at the Destination.

411	3.5 Evaluation of Reordering in Dimensions of Time or Bytes
412	   It is possible to use alternate dimensions of time or payload bytes
413	   to test for reordering in the definition of section 3.3, as long as
414	   the SrcTimes and SrcBytes are unique and reliable. Sequence
415	   Discontinuities are easily defined and detected with message
416	   numbering, however, this is not so simple in the dimensions of time
417	   or bytes. This is a detractor for the alternate dimensions because
418	   the Sequence Discontinuity definition plays a key role in the sample
419	   metrics that follow.

421	   It is possible to detect Sequence Discontinuities with payload byte
422	   numbering, but only when the complete pattern of payload sizes is
423	   stored at the Destination, or when payload size is constant and then
424	   the byte numbering adds needless complexity over message numbering.

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

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

433	3.6 Discussion

435	   Any arriving packet bearing a sequence number from the sequence that
436	   establishes the Next Expected value can be evaluated to determine
437	   whether it is in-order or reordered, based on a previous packet's
438	   arrival. In the case where Next Expected is Undefined (because the
439	   arriving packet is the first successful transfer), the packet is
440	   designated in-order (Type-P-Reordered=FALSE).

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

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

456	4. Sample Metrics

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

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

470	4.1 Reordered Packet Ratio

472	4.1.1 Metric Name:

474	   Type-P-Reordered-Ratio-Stream

476	4.1.2 Metric Parameters:

478	   The parameter set includes Type-P-Reordered singleton parameters,
479	   the parameters unique to Poisson Streams (as in RFC 2330 [RFC2330],
480	   Periodic Streams (as in RFC 3432 [RFC3432]), or TCP-like Streams (as
481	   in RFC 3148 [RFC3148]), packet size or size patterns, and the
482	   following:

484	   + T0, a start time

486	   + Tf, an end time

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

490	   + K,  the total number of packets in the stream sent from Source to
491	     Destination

493	   + L,  the total number of packets received (arriving between T0 and
494	     Tf+dT) out of the K packets sent. Recall that identical copies
495	     (duplicates) have been removed, so L <= K.

497	4.1.3 Definition:

499	   Given a stream of packets sent from a Source to a Destination, the
500	   ratio of reordered packets in the sample is

502	   (Count of packets with Type-P-Reordered=TRUE) / ( L )

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

508	4.1.4 Discussion

510	   When the Type-P-Reordered-Ratio-Stream is zero, no further
511	   reordering metrics need be examined for that sample. Therefore, the
512	   value of this metric is its simple ability to summarize the results
513	   for a reordering-free sample.

515	4.2 Reordering Extent

517	   This section defines the extent to which packets are reordered, and
518	   associates a specific Sequence Discontinuity with each reordered
519	   packet. This section inherits the Parameters defined above.

521	4.2.1 Metric Name:

523	   Type-P-packet-Reordering-Extent-Stream

525	4.2.2 Notation and Metric Parameters:

527	   Recall that K is the number of packets in the stream at the Source
528	   and L is the number of packets received at the Destination.

530	   Each packet has been assigned a sequence number, s, a consecutive
531	   integer from 1 to K in the order of packet transmission (at the
532	   source).

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

537	   s[i] can be thought of as a vector, where the index i is the arrival
538	   position of the packet with sequence number s.  In theory, any
539	   Source sequence number could appear in any arrival position, but
540	   this is unlikely in reality.

542	   Consider a reordered packet (Type-P-Reordered=TRUE) with arrival
543	   index i and source sequence number s[i]. There exists a set of
544	   indexes j (1 <= j < i) such that s[j] > s[i].

546	   The new parameters are:

548	   + i,     the index for arrival position, where i-1 represents an
549	     arrival earlier than i.

551	   + j,     a set of one or more arrival indexes,  where 1 <= j < i.

553	   + s[i],  the original sequence numbers, s, in order of arrival.

555	   + e,     the Reordering Extent, defined below.

557	4.2.3 Definition:

559	   The reordering extent, e, of packet s[i] is defined to be i-j for
560	   the smallest value of j where s[j] > s[i].

562	   Informally, the reordering extent is the maximum distance, in
563	   packets, from a reordered packet to the earliest packet received
564	   that has a larger sequence number.  If a packet is in-order, its
565	   reordering extent is undefined. The first packet to arrive is in-
566	   order by definition, and has undefined reordering extent.

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

577	4.2.4 Discussion:

579	   The packet with index j (s[j], identified in the Definition above)
580	   is the reordering discontinuity associated with packet s at index i
581	   (s[i]). This definition is formalized below.

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

587	   If a receiver intends to restore order, then its buffer capacity
588	   determines its ability to handle packets that are reordered. For
589	   cases with single reordered packets, the extent e gives the number
590	   of packets that must be held in the receiver's buffer while waiting
591	   for the reordered packet to complete the sequence. For more complex
592	   scenarios, the extent may be an overestimate of required storage
593	   (see the Examples section).

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

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

603	4.3 Reordering Late Time Offset

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

611	4.3.1 Metric Name:

613	   Type-P-packet-Late-Time-Stream

615	4.3.2 Metric Parameters:

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

620	   +  DstTime, the time that each packet in the stream arrives at the
621	     destination, and may be associated with index i, or packet s[i]

623	   +  LateTime(s[i]), the offset of packet s[i] in time, defined below

625	4.3.3 Definition:

627	   Lateness in time is calculated using destination times. When
628	   received packet s[i] is reordered, and has a reordering extent e,
629	   then:

631	   LateTime(s[i]) = DstTime(i)-DstTime(i-e)

633	   Alternatively, using similar notation to that of section 4.2, an
634	   equivalent definition is:

636	   LateTime(s[i]) = DstTime(i)-DstTime(j), for min{j|1<=j<i} that
637	   satisfies s[j]>s[i].

639	4.3.4 Discussion

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

646	   Note that the One-way IPDV [RFC3393] gives the delay variation for a
647	   packet w.r.t. the preceding packet in the source sequence. Lateness
648	   and IPDV give an indication of whether a buffer at the destination
649	   has sufficient storage to accommodate the network's behavior and
650	   restore order. When an earlier packet in the Source sequence is
651	   lost, IPDV will necessarily be undefined for adjacent packets, and
652	   LateTime may provide the only way to evaluate the usefulness of a
653	   packet.

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

663	   The combination of loss and reordering influences the LateTime
664	   metric. If presented with the arrival sequence 1, 10, 5 (where
665	   packets 2, 3, 4, and 6 through 9 are lost), LateTime would not
666	   indicate exactly how "late" packet 5 is from its intended arrival
667	   position. IPDV [RFC3393] would not capture this either, because of
668	   the lack of adjacent packet pairs.  Assuming a Periodic Stream
669	   [RFC3432], an expected arrival time could be defined for all
670	   packets, but this is essentially a single-point delay variation
671	   metric (as defined in ITU-T Recommendations [I.356] and [Y.1540]),
672	   and not a reordering metric.

674	4.4 Reordering Byte Offset

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

681	4.4.1 Metric Name:

683	   Type-P-packet-Byte-Offset-Stream

685	4.4.2 Metric Parameters:

687	   We use the same parameters defined earlier, including the optional
688	   parameters of SrcByte and PayloadSize, and define:

690	   +  ByteOffset(s[i]), the offset of packet s[i] in bytes

692	4.4.3 Definition:

694	   The Byte stream offset for reordered packet s[i] is the sum of the
695	   payload sizes of packets qualified by the following criteria:

697	   * Arrival prior to the reordered packet, s[i], and

699	   * The send sequence number, s, is greater than s[i].

701	   Packets that meet both these criteria are normally buffered until
702	   the sequence beneath them is complete. Note that these criteria
703	   apply to both in-order and reordered packets.

705	   For reordered packet s[i] with a reordering extent e:
706	   ByteOffset(s[i]) = Sum[qualified packets]
707	                    = Sum[PayloadSize(packet at i-1 if qualified),
708	                        PayloadSize(packet at i-2 if qualified), ...
709	                        PayloadSize(packet at i-e always qualified)]

711	   Using our earlier notation:
712	   ByteOffset(s[i]) =
713	               Sum[payloads of s[j] where s[j]>s[i] and i > j >= i-e]

715	4.4.4 Discussion
716	   We note that estimates of buffer size due to reordering depend on
717	   greatly on the test stream, in terms of the spacing between test
718	   packets and their size, especially when packet size is variable. In
719	   these and other circumstances, it may be most useful to characterize
720	   offset in terms of the payload size(s) of stored packets, using the
721	   Type-P-packet-Byte-Offset-Stream metric.

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

728	4.5 Gaps between multiple Reordering Discontinuities

730	4.5.1 Metric Name:

732	   Type-P-packet-Reordering-Gap-Stream

734	4.5.2 Parameters:

736	   We use the same parameters defined earlier, but add the convention
737	   that index i' is greater than i, likewise j' > j, and define:

739	   +  Gap(s[j']), the Reordering Gap of packet s[j'] in units of
740	      integer messages

742	   +  GapTime(s[j']), the Reordering Gap of packet s[j'] in units of
743	      time

745	4.5.3 Definition of Reordering Discontinuity:

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

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

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

759	4.5.4 Definition of Reordering Gap:

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

765	   If:

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

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

773	      i' > i, and

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

777	   then the Reordering Gap for packet s[j'] is the difference between
778	   the arrival positions the reordering discontinuities, as shown
779	   below:

781	   Gap(s[j'])    =   (j')  -  (j)

783	   Otherwise:

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

787	   Gaps may also be expressed in time:

789	   GapTime(s[j']) = DstTime(j') - DstTime(j)

791	4.5.5 Discussion

793	   When separate reordering discontinuities can be distinguished, then
794	   a count may also be reported (along with the discontinuity
795	   description, such as the number of reordered packets associated with
796	   that discontinuity and their extents and offsets). The Gaps between
797	   a sample's reordering discontinuities may be expressed as a
798	   histogram, to easily summarize the frequency of various gaps.
799	   Reporting the mode, average, range, etc. may also summarize the
800	   distributions.

802	   The Gap metric may help to correlate the frequency of reordering
803	   discontinuities with their cause. Gap lengths are also informative
804	   to receiver designers, revealing the period of reordering
805	   discontinuities. The combination of reordering gaps and extent
806	   reveals whether receivers will be required to handle cases of
807	   overlapping reordered packets.

809	4.6 Reordering-free Runs

811	   This section defines a metric based on a count of consecutive in-
812	   order packets between reordered packets.

814	4.6.1 Metric Name:

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

818	4.6.2 Parameters:

820	   We use the same parameters defined earlier, and define the
821	   following:

823	   + r, the run counter

825	   + x, the number of runs, also the number of reordered packets

827	   + a, the accumulator of in-order packets

829	   + p, the number of packets (when the stream is complete, p=(x+a)=L)

831	   + q, the sum of the squares of the runs counted

833	4.6.3 Definition:

835	   As packets in a sample arrive at the Destination, the count of in-
836	   order packets between reordered packets is a Reordering-Free run.
837	   Note that the minimum run-length is zero according to this
838	   definition. A pseudo code example follows:

840	   r = 0; /* r is the run counter */
841	   x = 0; /* x is the number of runs */
842	   a = 0; /* a is the accumulator of in order packets */
843	   p = 0; /* p is the number of packets */
844	   q = 0; /* q is the sum of the squares of the runs counted */

846	   while(packets arrive with sequence number s)
847	   {
848	        p++;
849	        if (s >= NextExp) /* s is in-order */
850	                then r++;
851	                a++;
852	        else    /* s is reordered */
853	                q+= r*r;
854	                r = 0;
855	                x++;
856	   }

858	   Each in-order arrival increments the run counter and the accumulator
859	   of in order packets, each reordered packet resets the run counter
860	   after adding it to the sum of the squared lengths.

862	   Each arrival of a reordered packet yields a new run count.  Long
863	   runs accompany periods where order was maintained, while short runs
864	   indicate frequent, or multi-packet reordering.

866	   The percent of packets in-order is 100*a/p

868	   The average Reordering-Free run length is a/x
869	   The q counter gives an indication of variation of the Reordering-
870	   Free runs from the average by comparing q/a to a/x  ((q/a)/(a/x))

872	4.6.4 Discussion and Illustration:

874	   Type-P-packet-Reordering-Free-Run-Stream parameters give a brief
875	   summary of the stream's reordering characteristics including the
876	   average reordering-free run length, and the variation of run
877	   lengths, therefore a key application of this metric is network
878	   evaluation.

880	   For 36 packets with 3 runs of 11 in-order packets we have:
881	      p = 36
882	      x = 3
883	      a = 33
884	      q = 3 * (11*11) = 363
885	      ave reordering-free run = 11
886	      q/a = 11
887	      (q/a)/(a/x) = 1.0

889	   For 36 packets with 3 runs, 2 runs of length 1 and one of length 31
890	      p = 36
891	      x = 3
892	      a = 33
893	      q = 1 + 1 + 961 = 963
894	      ave reordering-free run = 11
895	      q/a = 29.18
896	      (q/a)/(a/x) = 2.65

898	   The variability in run length is prominent in the difference between
899	   the q values (sum of the squared run lengths) and comparing average
900	   run length to the (q/a)/(a/x) ratios (equals 1 when all runs are the
901	   same length).

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

905	   This section describes a metric that conveys information associated
906	   with the affect of reordering on TCP.  However, in order to infer
907	   anything about TCP performance, the test stream MUST bear a close
908	   resemblance to the TCP sender of interest. RFC 3148 [RFC3148] lists
909	   the specific aspects of congestion control algorithms that must be
910	   specified. Further, RFC 3148 recommends that Bulk Transfer Capacity
911	   metrics SHOULD have instruments to distinguish three cases of packet
912	   reordering (in section 3.3). The sample metrics defined above
913	   satisfy the requirements to classify packets that are slightly or
914	   grossly out-of-order. The metric in this section adds the capability
915	   to estimate whether reordering might cause the DUP-ACK threshold to
916	   be exceeded causing the Fast Retransmit algorithm to be invoked.
917	   Additional TCP Kernel Instruments are summarized in [Mat03].

919	5.1 Metric Name:

921	   Type-P-packet-n-Reordering-Stream

923	5.2 Parameter Notation:

925	   Let n be a positive integer (a parameter).  Let k be a positive
926	   integer equal to the number of packets sent (sample size).  Let l be
927	   a non-negative integer representing the number of packets that were
928	   received out of the k packets sent.  (Note that there is no
929	   relationship between k and l: on one hand, losses can make l less
930	   than k; on the other hand, duplicates can make l greater than k.)
931	   Assign each sent packet a sequence number, 1 to k, in order of
932	   packet emission.

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

937	5.3 Definitions

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

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

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

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

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

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

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

967	5.4 Discussion:

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

972	   The n-reordering metric is helpful for matching the duplicate ACK
973	   threshold setting to a given path.  For example, if a path exhibits
974	   no more than 5-reordering, a DUP-ACK threshold of 6 may avoid
975	   unnecessary retransmissions.

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

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

983	   - For n=3, a NewReno TCP sender would retransmit 1 packet in
984	   response to an instance of 3-reordering and therefore consider this
985	   packet lost for the purposes of congestion control (the sender will
986	   half its congestion window, see [RFC2581]). 3 is default threshold
987	   for SCTP [RFC2960], and the future Datagram Congestion Control
988	   Protocol (DCCP).

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

993	   We note that the definition of n-reordering cannot predict the exact
994	   number of packets unnecessarily retransmitted by a TCP sender under
995	   some circumstances, such as cases with closely-spaced reordered
996	   singletons. Both time and position influence the sender's behavior.

998	   A packet's n-reordering designation is sometimes equal to its
999	   reordering extent, e. n-reordering is different in the following
1000	   ways:

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

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

1008	6. Measurement and Implementation Issues

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

1015	   In order to gauge the reordering for an application according to the
1016	   metrics defined in this memo, it is RECOMMENDED to use the same
1017	   sending pattern as the application of interest. In any case, the
1018	   exact method of packet generation MUST be reported with the
1019	   measurement results, including all stream parameters.

1021	   +  To make inferences about applications that use TCP, it is
1022	      REQUIRED to use TCP-like Streams as in [RFC3148]

1024	   +  For real-time applications, it is RECOMMENDED to use Periodic
1025	      Streams as in [RFC3432]

1027	   It is acceptable to report the metrics of Sections 3 and 4 with
1028	   other IPPM metrics using Poisson Streams [RFC2330]. Poisson streams
1029	   represent an "unbiased sample" of network performance for packet
1030	   loss and delay metrics. However, it would be incorrect to make
1031	   inferences about the application categories above using reordering
1032	   metrics measured with Poisson streams.

1034	   Test stream designers may prefer to use a periodic sending interval
1035	   so that a known temporal bias is maintained, also bringing
1036	   simplified results analysis (as described in [RFC3432]). In this
1037	   case, it is RECOMMENDED that the periodic sending interval should be
1038	   chosen to reproduce the closest Source packet spacing expected.
1039	   Testers must recognize that streams sent at the link speed
1040	   serialization limit MUST have limited duration and MUST consider
1041	   packet loss as an indication that the stream has caused congestion,
1042	   and suspend further testing.

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

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

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

1059	   Assuming that the necessary sequence information (message number) is
1060	   included in the packet payload (possibly in application headers such
1061	   as RTP), reordering metrics may be evaluated in a passive
1062	   measurement arrangement.  Also, it is possible to evaluate order at
1063	   any point along a Source-Destination path, recognizing that
1064	   intermediate measurements may differ from those made at the
1065	   Destination (where reordering's affect on applications can be
1066	   inferred).

1068	   It is possible to apply these metrics to evaluate reordering in a
1069	   TCP sender's stream. In this case, the Source sequence numbers would
1070	   be based on byte stream, or segment numbering. Since the stream may
1071	   include retransmissions due to loss or reordering, care must be
1072	   taken to avoid declaring retransmitted packets reordered. The
1073	   additional sequence reference of s or SrcTime helps to avoid this
1074	   ambiguity, or the optional TCP timestamp field [RFC1323].

1076	   Since this metric definition may use sequence numbers with finite
1077	   range, it is possible that the sequence numbers could reach end-of-
1078	   range and roll over to zero during a measurement.  By definition,
1079	   the Next Expected value cannot decrease, and all packets received
1080	   after a roll-over would be declared reordered.  Sequence number
1081	   roll-over can be avoided by using combinations of counter size and
1082	   test duration where roll-over is impossible (and sequence is reset
1083	   to zero at the start). Also, message-based numbering results in
1084	   slower sequence consumption.  There may still be cases where
1085	   methodological mitigation of this problem is desirable (e.g., long-
1086	   term testing).  The elements of mitigation are:

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

1093	   2. All sequence numbers used in computations are represented in a
1094	   sufficiently large precision.  The numbers have a correction applied
1095	   (equivalent to adding a significant digit) whenever roll-over is
1096	   detected.

1098	   3. Reordered packets coincident with sequence numbers reaching end-
1099	   of-range must also be detected for proper application of correction
1100	   factor.

1102	   Ideally, the test instrument would have the ability to use all
1103	   earlier packets at any point in the test stream. In practice, there
1104	   will be limited ability to determine reordering extent, due to the
1105	   storage requirements for previous packets. Saving only packets that
1106	   indicate discontinuities (and their arrival positions) will reduce
1107	   storage volume.

1109	   Another solution is to use a sliding history window of packets,
1110	   where the window size would be determined by an upper bound on the
1111	   useful reordering extent. This bound could be several packets or
1112	   several seconds-worth of packets, depending on the intended
1113	   analysis. When discarding all stream information beyond the window,
1114	   the reordering extent or degree of n-reordering may need to be
1115	   expressed as greater than the window length if the reordering
1116	   discontinuity information has been discarded, and Gap calculations
1117	   would not be possible.

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

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

1131	7. Examples of Arrival Order Evaluation

1133	   This section provides some examples to illustrate how the non-
1134	   reversing order criterion works, how n-reordering works in
1135	   comparison, and the value of quantifying reordering in all the
1136	   dimensions of time, bytes, and position.

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

1144	7.1 Example with a single packet reordered

1146	   Table 1 gives a simple case of reordering, where one packet is
1147	   reordered, Packet 4. Packets are listed according to their arrival,
1148	   and message numbering is used. All packets contain 100 bytes,
1149	   beginning with s=1 and (s x 100)-99 for s=2,3,4,...

1151	   Table 1 Example with Packet 4 Reordered,
1152	   Sending order(SrcNum@Src): 1,2,3,4,5,6,7,8,9,10
1153	   s            Src     Dst                     Dst     Byte    Late
1154	   @Dst NextExp Time    Time    Delay   IPDV    Order   Offset  Time
1155	    1     1       0      68      68              1
1156	    2     2      20      88      68       0      2
1157	    3     3      40     108      68       0      3
1158	    5     4      80     148      68     -82      4
1159	    6     6     100     168      68       0      5
1160	    7     7     120     188      68       0      6
1161	    8     8     140     208      68       0      7
1162	    4     9      60     210     150      82      8      400     62
1163	    9     9     160     228      68       0      9
1164	   10    10     180     248      68       0     10

1166	   Each column gives the following information:

1168	   s        Packet sequence number at the Source.
1169	   NextExp  The value of NextExp when the packet arrived(before
1170	   update).
1171	   SrcTime  Packet time stamp at the Source, ms.
1172	   DstTime  Packet time stamp at the Destination, ms.
1173	   Delay    1-way delay of the packet, ms.
1174	   IPDV     IP Packet Delay Variation, ms
1175	            IPDV = Delay(SrcNum)-Delay(SrcNum-1)
1176	   DstOrder Order in which the packet arrived at the Destination.
1177	   Byte Offset  The Byte Offset of a reordered packet, in bytes.
1178	   LateTime The lateness of a reordered packet, in ms.

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

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

1186	                            \/
1187	   s = 1, 2, 3, 5, 6, 7, 8, 4, 9, 10
1188	   i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
1189	                            /\

1191	   Applying the definition of Type-P-packet-Reordering-Extent-Stream:
1192	   when j=7, 8 > 4, so the reordering extent is 1 or more.
1193	   when j=6, 7 > 4, so the reordering extent is 2 or more.
1194	   when j=5, 6 > 4, so the reordering extent is 3 or more.
1195	   when j=4, 5 > 4, so the reordering extent is 4 or more.
1196	   when j=3, but 3 < 4, and 4 is the maximum extent, e=4 (assuming
1197	   there are no earlier sequence discontinuities, as in this example).

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

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

1209	   Following the definitions of section 5.1, Packet 4 is designated 4-
1210	   reordered.

1212	7.2 Example with two packets reordered

1214	   Table 2 Example with Packets 5 and 6 Reordered,
1215	   Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10
1216	   s            Src     Dst                     Dst     Byte    Late
1217	   @Dst NextExp Time    Time    Delay   IPDV    Order   Offset  Time
1218	    1     1       0      68      68              1
1219	    2     2      20      88      68       0      2
1220	    3     3      40     108      68       0      3
1221	    4     4      60     128      68       0      4
1222	    7     5     120     188      68     -22      5
1223	    5     8      80     189     109      41      6      100     1
1224	    6     8     100     190      90     -19      7      100     2
1225	    8     8     140     208      68       0      8
1226	    9     9     160     228      68       0      9
1227	   10    10     180     248      68       0     10

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

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

1236	                      \/ \/
1237	   s = 1, 2, 3, 4, 7, 5, 6, 8, 9, 10
1238	   i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
1239	                      /\ /\

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

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

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

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

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

1263	   A hypothetical sender/receiver pair may retransmit Packet 5
1264	   unnecessarily, since it is 1-reordered (in agreement with the
1265	   singleton metric). Though Packet 6 may not be unnecessarily
1266	   retransmitted, the receiver cannot advance Packet 7 to the higher
1267	   layers until after Packet 6 arrives. Therefore, the singleton metric
1268	   correctly determined that Packet 6 is reordered.

1270	7.3 Example with three packets reordered

1272	   Table 3 Example with Packets 4, 5, and 6 reordered
1273	   Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11
1274	   s            Src     Dst                     Dst     Byte    Late
1275	   @Dst NextExp Time    Time    Delay   IPDV    Order   Offset  Time
1276	    1    1        0      68      68              1
1277	    2    2       20      88      68       0      2
1278	    3    3       40     108      68       0      3
1279	    7    4      120     188      68     -88      4
1280	    8    8      140     208      68       0      5
1281	    9    9      160     228      68       0      6
1282	   10   10      180     248      68       0      7
1283	    4   11       60     250     190     122      8      400     62
1284	    5   11       80     252     172     -18      9      400     64
1285	    6   11      100     256     156     -16     10      400     68
1286	   11   11      200     268      68       0     11

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

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

1296	   Bin         1  2  3  4  5  6  7
1297	   Frequency   0  0  0  1  1  1  0

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

1302	   s = 1, 2, 3, 7, 8, 9,10, 4, 5, 6, 11
1303	   i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11

1305	   We first calculate the n-reordering. Considering Packet 4 first:
1306	   when n=1, 7<=j<8, and 10> 4, so the packet is 1-reordered.
1307	   when n=2, 6<=j<8, and 9 > 4, so the packet is 2-reordered.
1308	   when n=3, 5<=j<8, and 8 > 4, so the packet is 3-reordered.
1309	   when n=4, 4<=j<8, and 7 > 4, so the packet is 4-reordered.
1310	   when n=5, 3<=j<8, but 3 < 4, and 4 is the maximum n-reordering.

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

1316	   We now consider whether reordered Packets 5 and 6 are associated
1317	   with the same reordering discontinuity as Packet 4.  Using the test
1318	   of Section 4.2.3, we find that the minimum j=4 for all three
1319	   packets. They are all associated with the reordering discontinuity
1320	   at Packet 7.

1322	   This example shows again that the n-reordering definition identifies
1323	   a single Packet (4) with a sufficient degree of n-reordering that
1324	   might cause one unnecessary packet retransmission by the New Reno
1325	   TCP sender (with DUP-ACK threshold=3 or 4). Also, the reordered
1326	   arrival of Packets 5 and 6 will allow the receiver process to pass
1327	   Packets 7 through 10 up the protocol stack (the singleton Type-P-
1328	   Reordered = TRUE for Packets 5 and 6, and they are all associated
1329	   with a single reordering discontinuity).

1331	7.4 Example with Multiple Packet Reordering Discontinuities

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

1336	          Discontinuity         Discontinuity
1337	                |---------Gap---------|
1338	   s = 1, 2, 3, 6, 7, 4, 5, 8, 9, 10, 12, 13, 11, 14, 15, 16
1339	   i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

1341	   r = 1, 2, 3, 4, 5, 0, 0, 1, 2,  3,  4,  5,  0,  1,  2,  3, ...
1342	   number of runs,n = 1  2                     3
1343	   end r counts =     5  0                     5
1344	   (these values are computed after the packet arrives)

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

1350	   According to the definition of Reordering Gap
1351	   Gap(s[j']) = (j') - (j)
1352	   Gap(Packet 12) = (11) - (4) = 7

1354	   We also have three reordering-free runs of lengths 5, 0, and 5.

1356	   The differences between these two multiple-event metrics are evident
1357	   here.  Gaps are the distance between sequence discontinuities that
1358	   are subsequently defined as reordering discontinuities, while
1359	   reordering-free runs capture the distance between reordered packets.

1361	8. Security Considerations

1363	8.1 Denial of Service Attacks

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

1370	   Administrators of source, destination, and the intervening
1371	   network(s) should establish bilateral or multi-lateral agreements
1372	   regarding the timing, size, and frequency of collection of sample
1373	   metrics.  Use of this method in excess of the terms agreed between
1374	   the participants may be cause for immediate rejection or discard of
1375	   packets or other escalation procedures defined between the affected
1376	   parties.

1378	8.2 User data confidentiality

1380	   Active use of this method generates packets for a sample, rather
1381	   than taking samples based on user data, and does not threaten user
1382	   data confidentiality. Passive measurement must restrict attention to
1383	   the headers of interest. Since user payloads may be temporarily
1384	   stored for length analysis, suitable precautions MUST be taken to
1385	   keep this information safe and confidential. In most cases, a
1386	   hashing function will produce a value suitable for payload
1387	   comparisons.

1389	8.3 Interference with the metric

1391	   It may be possible to identify that a certain packet or stream of
1392	   packets is part of a sample. With that knowledge at the destination
1393	   and/or the intervening networks, it is possible to change the
1394	   processing of the packets (e.g. increasing or decreasing delay) that
1395	   may distort the measured performance.  It may also be possible to
1396	   generate additional packets that appear to be part of the sample
1397	   metric. These additional packets are likely to perturb the results
1398	   of the sample measurement.

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

1403	9. IANA Considerations

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

1408	10. Normative References

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

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

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

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

1428	   [RFC3432]  Raisanen, V., Grotefeld, G., and Morton, A., "Network
1429	              performance measurement with periodic streams", RFC 3432,
1430	              November 2002.

1432	11. Informative References

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

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

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

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

1452	   [I.356]    ITU-T Recommendation I.356, "B-ISDN ATM layer cell
1453	              transfer performance", March 2000.

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

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

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

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

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

1478	   [RFC1323]  Jacobson, V., Braden, R., and Borman, D., "TCP Extensions
1479	              for High Performance", RFC 1323, May 1992.

1481	   [RFC2581]  Allman, M., Paxson, V., and Stevens, W., "TCP Congestion
1482	              Control", RFC 2581, April 1999.

1484	   [RFC2960]  Stewart, R., et al., "Stream Control Transmission
1485	              Protocol", RFC 2960, October 2000.

1487	   [RFC3393]  Demichelis, C., and Chimento, P., "IP Packet Delay
1488	              Variation Metric for IP Performance Metrics (IPPM)", RFC
1489	              3393, November 2002.
1490	   [Y.1540]   ITU-T Recommendation Y.1540, "Internet protocol data
1491	              communication service - IP packet transfer and
1492	              availability performance parameters", December 2002.

1494	12. Acknowledgments

1496	   The authors would like to acknowledge many helpful discussions with
1497	   Matt Zekauskas, Jon Bennett (who authored the sections on
1498	   Reordering-Free Runs), and Matt Mathis. We thank David Newman, Henk
1499	   Uijterwall, Mark Allman, Vern Paxson, and Phil Chimento for their
1500	   reviews and suggestions, and Michal Przybylski for sharing
1501	   implementation experiences with us on the ippm-list. We gratefully
1502	   acknowledge the foundation laid by the authors of the IP performance
1503	   Framework [RFC2330].

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

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

1509	   Example 1  n-reordering ============================================

1511	   #include <stdio.h>

1513	   #define MAXN   100

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

1518	   /*
1519	    * Read new sequence number and return it. Return a sentinel value
1520	    * of EOF (at least once) when there are no more sequence numbers.
1521	    * In this example, the sequence numbers come from stdin;
1522	    * in an actual test, they would come from the network.

1524	    *
1525	   */
1526	   int
1527	   read_sequence_number()
1528	   {
1529	           int     res, rc;
1530	           rc = scanf("%d\n", &res);
1531	           if (rc == 1) return res;
1532	           else return EOF;
1533	   }

1535	   int
1536	   main()
1537	   {
1538	           int     m[MAXN];       /* We have m[j-1] == number of
1539	                                            * j-reordered packets. */
1540	           int     ring[MAXN];    /* Last sequence numbers seen. */
1541	           int     r = 0;          /* Ring pointer for next write. */
1542	           int     l = 0;        /* Number of sequence numbers read. */
1543	           int     s;              /* Last sequence number read. */
1544	           int     j;

1546	           for (j = 0; j < MAXN; j++) m[j] = 0;
1547	           for (;(s = read_sequence_number())!= EOF;l++,r=(r+1)%MAXN) {
1548	             for (j=0; j<min(l, MAXN)&&s<ring[loop(r-j-1)];j++) m[j]++;
1549	             ring[r] = s;
1550	           }
1551	           for (j = 0; j < MAXN && m[j]; j++)
1552	             printf("%d-reordering = %f%%\n", j+1, 100.0*m[j]/(l-j-1));
1553	           if (j == 0) printf("no reordering\n");
1554	           else if (j < MAXN) printf("no %d-reordering\n", j+1);
1555	           else printf("only up to %d-reordering is handled\n", MAXN);
1556	           exit(0);
1557	   }

1559	   /* Example 2   singleton and n-reordering comparison =======
1560	      Author:  Jerry Perser 7-2002 (mod by acm 12-2004)
1561	      Compile: $ gcc -o jpboth file.c
1562	      Usage:   $ jpboth 1 2 3 7 8 4 5 6 (pkt sequence given on cmdline)
1563	      Note to cut/pasters: line 59 may need repair
1564	   */

1566	      #include <stdio.h>

1568	      #define MAXN   100
1569	      #define min(a, b) ((a) < (b)? (a): (b))
1570	      #define loop(x) ((x) >= 0? x: x + MAXN)

1572	      /* Global counters */
1573	      int receive_packets=0;       /* number of received */
1574	      int reorder_packets_Al=0;    /* num reordered pkts (singleton) */
1575	      int reorder_packets_Stas=0; /* num reordered pkts(n-reordering)*/

1577	      /* function to test if current packet has been reordered
1578	       * returns 0 = not reordered
1579	       *         1 = reordered
1580	       */
1581	      int testorder1(int seqnum)   // Al
1582	      {
1583	           static int NextExp = 1;
1584	           int iReturn = 0;

1586	           if (seqnum >= NextExp) {
1587	                   NextExp = seqnum+1;
1588	           } else {
1589	                   iReturn = 1;
1590	           }
1591	           return iReturn;
1592	      }

1594	      int testorder2(int seqnum)   // Stanislav
1595	      {
1596	           static int  ring[MAXN];    /* Last sequence numbers seen. */
1597	           static int  r = 0;         /* Ring pointer for next write */
1598	           int   l = 0;          /* Number of sequence numbers read. */
1599	           int   j;
1600	           int  iReturn = 0;

1602	           l++;
1603	           r = (r+1) % MAXN;
1604	           for (j=0; j<min(l, MAXN) && seqnum<ring[loop(r-j-1)]; j++)
1605	                       iReturn = 1;
1606	           ring[r] = seqnum;
1607	           return iReturn;
1608	      }
1609	      int main(int argc, char *argv[])
1610	      {
1611	           int i, packet;
1612	           for (i=1; i< argc; i++) {
1613	                receive_packets++;
1614	                packet = atoi(argv[i]);
1615	                reorder_packets_Al += testorder1(packet); // singleton
1616	                reorder_packets_Stas += testorder2(packet); //n-reord.
1617	           }
1618	           printf("Received packets = %d, Singleton Reordered = %d, n-
1619	   reordered = %d\n",  receive_packets, reorder_packets_Al,
1620	   reorder_packets_Stas );
1621	           exit(0);
1622	      }

1624	   Reference
1625	   ISO/IEC 9899:1999 (E), as amended by ISO/IEC 9899:1999/Cor.1:2001
1626	   (E). Also published as:

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

1632	14. Appendix B Fragment Order Evaluation (Informative)

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

1639	14.1 Metric Name:

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

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

1649	14.2 Additional Metric Parameters:

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

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

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

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

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

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

1673	14.3 Definition:

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

1678	   * the sequence number s >= NextExp,

1680	   * AND the fragment offset FragOffset >= NextExpFrag

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

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

1689	   Case 1: if s < NextExp

1691	   Case 2: if s < FragSeq#

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

1695	   This definition can also be illustrated in pseudo-code. A draft
1696	   version of the code follows, and some simplification may be
1697	   possible. A challenging aspect surrounds the housekeeping for the
1698	   new parameters.

1700	   NextExp=0;
1701	   NextExpFrag=0;
1702	   FragSeq#=0;

1704	   while(packets arrive with s, MoreFrag, FragOffset)
1705	   {
1706	   if (s>=NextExp AND MoreFrag==0 AND s>=FragSeq#){
1707	        /* a normal packet or last frag of an in-order packet arrived
1708	   */
1709	        NextExp = s+1;
1710	        FragSeq# = 0;
1711	        NextExpFrag = 0;
1712	        Reordering = False;
1713	        }
1714	   if (s>=NextExp AND MoreFrag==1 AND s>FragSeq#>=0){
1715	        /* a fragment of a new packet arrived, possibly with a
1716	        higher sequence number than the current fragmented packet */
1717	        FragSeq# = s;
1718	        NextExpFrag = FragOffset+1;
1719	        Reordering = False;
1720	        }
1721	   if (s>=NextExp AND MoreFrag==1 AND s==FragSeq#){
1722	        /* a fragment of the "current packet s" arrived */
1723	        if (FragOffset >= NextExpFrag){
1724	                NextExpFrag = FragOffset+1;
1725	                Reordering = False;
1726	                }

1728	        else{
1729	                Reordering = True; /* fragment reordered  */
1730	                }
1731	        }
1732	   if (s>=NextExp AND MoreFrag==1 AND s < FragSeq#){
1733	        /* case where a late fragment arrived,
1734	           for illustration only, redundant with else below */
1735	        Reordering = True;
1736	        }
1737	   else { /* when s < NextExp, or MoreFrag==0 AND s < FragSeq# */
1738	        Reordering = True;
1739	        }
1740	   }

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

1746	14.4 Discussion: Notes on Sample Metrics when evaluating Fragments

1748	   All fragments with the same Source Sequence Number are assigned the
1749	   same Source Time.

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

1756	15. Author's Addresses

1758	   Al Morton
1759	   AT&T Labs
1760	   Room D3 - 3C06
1761	   200 Laurel Ave. South
1762	   Middletown, NJ 07748 USA
1763	   Phone  +1 732 420 1571
1764	   EMail: <acmorton@att.com>

1766	   Len Ciavattone
1767	   AT&T Labs
1768	   Room C2 - 3D02
1769	   200 Laurel Ave. South
1770	   Middletown, NJ 07748 USA
1771	   Phone  +1 732 420 1239
1772	   EMail: <lencia@att.com>

1774	   Gomathi Ramachandran
1775	   AT&T Labs
1776	   Room C4 - 3D22
1777	   200 Laurel Ave. South
1778	   Middletown, NJ 07748 USA
1779	   Phone  +1 732 420 2353
1780	   EMail: <gomathi@att.com>

1782	   Stanislav Shalunov
1783	   Internet2
1784	   200 Business Park Drive, Suite 307
1785	   Armonk, NY 10504
1786	   Phone: + 1 914 765 1182
1787	   EMail: <shalunov@internet2.edu>

1789	   Jerry Perser
1790	   Consultant
1791	   Calabasas, CA 91302  USA
1792	   Phone: + 1
1793	   EMail: <jerry@perser.org>

1795	Full Copyright Statement

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

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

1809	Intellectual Property

1811	   The IETF takes no position regarding the validity or scope of any
1812	   Intellectual Property Rights or other rights that might be claimed
1813	   to pertain to the implementation or use of the technology described
1814	   in this document or the extent to which any license under such
1815	   rights might or might not be available; nor does it represent that
1816	   it has made any independent effort to identify any such rights.
1817	   Information on the procedures with respect to rights in RFC
1818	   documents can be found in BCP 78 and BCP 79.

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

1827	   The IETF invites any interested party to bring to its attention any
1828	   copyrights, patents or patent applications, or other proprietary
1829	   rights that may cover technology that may be required to implement
1830	   this standard.  Please address the information to the IETF at ietf-
1831	   ipr@ietf.org.

1833	Acknowledgement

1835	   Funding for the RFC Editor function is currently provided by the
1836	   Internet Society.