RFC 4737
Packet Reordering Metrics
RFC 4737: Packet Reordering Metrics 🎀
okay bestie, this is part 1 of 9 so we're just getting started 🦋 Here's the title block facts you need up front:
- Number: RFC 4737
- Title: Packet Reordering Metrics
- Category: Standards Track
- Date: November 2006
- Authors: A. Morton, L. Ciavattone, G. Ramachandran (all AT&T Labs), S. Shalunov (Internet2), and J. Perser (Veriwave)
- Obsoletes/Updates: the title block doesn't list anything this one obsoletes or updates 💅
It's from the Network Working Group, so you know it's the real deal 💜
Status of This Memo ✨
okay so this doc is a standards track protocol spec for the Internet community 🌸 It's asking folks for discussion and suggestions for improvements. If you want the current standardization state and status of this protocol, go check the "Internet Official Protocol Standards" (STD 1) doc 📚 Distribution of this memo is unlimited, so share away 🫶
Copyright Notice 🔥
Copyright (C) The IETF Trust (2006).
Abstract 🦋
this memo defines metrics for figuring out whether a network kept packets in order, packet by packet 👀 It explains why these new metrics are needed and talks through the measurement issues, including the context information that all the metrics need 🧚
It starts by defining a reordered singleton, then uses that as the base for sample metrics that measure how much reordering happens in a few useful dimensions. Those are handy for characterizing networks or designing receivers 💖 More metrics cover how often reordering happens and how far apart the separate occurrences are ✨ Then there's a metric aimed at how reordering affects TCP 👑 The memo also includes several examples of evaluating with the sample metrics, and an appendix covers extended definitions for checking order when packets get fragmented 🍓
Table of Contents 💜
1. Introduction ....................................................4
1.1. Motivation .................................................4
1.2. Goals and Objectives .......................................5
1.3. Required Context for All Reordering Metrics ................6
2. Conventions Used in this Document ...............................7
3. A Reordered Packet Singleton Metric .............................7
3.1. Metric Name ................................................8
3.2. Metric Parameters ..........................................8
3.3. Definition .................................................8
3.4. Sequence Discontinuity Definition ..........................9
3.5. Evaluation of Reordering in Dimensions of Time or Bytes ...10
3.6. Discussion ................................................10
4. Sample Metrics .................................................11
4.1. Reordered Packet Ratio ....................................11
4.1.1. Metric Name ........................................11
4.1.2. Metric Parameters ..................................11
4.1.3. Definition .........................................12
4.1.4. Discussion .........................................12
4.2. Reordering Extent .........................................12
4.2.1. Metric Name ........................................12
4.2.2. Notation and Metric Parameters .....................12
4.2.3. Definition .........................................13
4.2.4. Discussion .........................................13
4.3. Reordering Late Time Offset ...............................14
4.3.1. Metric Name ........................................14
4.3.2. Metric Parameters ..................................14
4.3.3. Definition .........................................15
4.3.4. Discussion .........................................15
4.4. Reordering Byte Offset ....................................16
4.4.1. Metric Name ........................................16
4.4.2. Metric Parameters ..................................16
4.4.3. Definition .........................................16
4.4.4. Discussion .........................................17
4.5. Gaps between Multiple Reordering Discontinuities ..........17
4.5.1. Metric Names .......................................17
4.5.2. Parameters .........................................17
4.5.3. Definition of Reordering Discontinuity .............17
4.5.4. Definition of Reordering Gap .......................18
4.5.5. Discussion .........................................18
4.6. Reordering-Free Runs ......................................19
4.6.1. Metric Names .......................................19
4.6.2. Parameters .........................................19
4.6.3. Definition .........................................19
4.6.4. Discussion and Illustration ........................20
5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric ..21
5.1. Metric Name ...............................................21
5.2. Parameter Notation ........................................21
5.3. Definitions ...............................................22
5.4. Discussion ................................................22
6. Measurement and Implementation Issues ..........................23
6.1. Passive Measurement Considerations ........................26
7. Examples of Arrival Order Evaluation ...........................26
7.1. Example with a Single Packet Reordered ....................26
7.2. Example with Two Packets Reordered ........................28
7.3. Example with Three Packets Reordered ......................30
7.4. Example with Multiple Packet Reordering Discontinuities ...31
8. Security Considerations ........................................32
8.1. Denial-of-Service Attacks .................................32
8.2. User Data Confidentiality .................................32
8.3. Interference with the Metric ..............................32
9. IANA Considerations ............................................33
10. Normative References ..........................................35
11. Informative References ........................................36
12. Acknowledgements ..............................................37
Appendix A. Example Implementations in C (Informative) ............38
Appendix B. Fragment Order Evaluation (Informative) ...............41
B.1. Metric Name ...............................................41
B.2. Additional Metric Parameters ..............................41
B.3. Definition ................................................42
B.4. Discussion: Notes on Sample Metrics When Evaluating
Fragments .................................................43
Appendix C. Disclaimer and License ................................431. Introduction ✨
okay so ordered arrival is a thing packets have on their trip through the network 🦋 When packets arrive in order, the sequence number goes up with each new arrival and there are no backward steps 💅 The Internet Protocol [RFC791] [RFC2460] has no mechanisms to ensure packets get delivered or stay in sequence, so higher-layer protocols (above IP) need to be ready to deal with both loss and reordering 🫶 This memo is all about defining reordering metrics 🔥
each packet carries a unique sequence identifier, like an incrementing consecutive integer message number, and that's what establishes the source sequence 🌈
the destination detects reordering by comparing packet arrival order against a non-reversing reference value [Cia03] 🧚
this metric lines up with [RFC2330] and classifies arriving packets whose sequence numbers are smaller than their predecessors' as out-of-order or reordered 👀 For example, if sequentially numbered packets arrive 1,2,4,5,3, then packet 3 is reordered 💖 This is equivalent to Paxon's reordering definition in [Pax98], where "late" packets were declared reordered ✨ The alternative is to focus on "premature" packets instead (4 and 5 in the example), but only the arrival of packet 3 tells that situation apart from packet loss 🙈 Focusing on late packets lets us keep orthogonality with the packet loss metric 💜 The metric's construction is very similar to the sequence space validation for received segments in [RFC793] 🍓 Earlier work to define ordered delivery includes [Cia00], [Ben99], [Lou01], [Bel02], [Jai02], and [Cia03] 🌸
1.1. Motivation 💅
a reordering metric is relevant for most applications, especially when assessing network support for Real-Time media streams 🎀 The extent of reordering may be enough to cause a received packet to be discarded by functions above the IP layer 😭
packet order may change during transfer, and several specific path characteristics can make reordering more likely 🦋 Examples are:
- When two (or more) paths with slightly differing transfer times support a single packet stream or flow, packets traversing the longer path(s) may arrive out-of-order. Multiple paths may be used to achieve load balancing or may arise from route instability 🛤️
- To increase capacity, a network device designed with multiple processors serving a single port (or parallel links) may reorder as a byproduct 🧠
- A layer-2 retransmission protocol that compensates for an error-prone link may cause packet reordering 🔁
- If for any reason the packets in a buffer are not serviced in the order of their arrival, their order will change 🪣
- If packets in a flow are assigned to multiple buffers (following evaluation of traffic characteristics, for example), and the buffers have different occupation levels and/or service rates, then order will likely change 📦
when one or more of the above path characteristics are present continuously, reordering may be present on a steady-state basis 🌊 The steady-state reordering condition typically causes an appreciable fraction of packets to be reordered 😳 This form of reordering is most easily detected by minimizing the spacing between test packets 🔍 Transient reordering may occur in response to network instability; temporary routing loops can cause periods of extreme reordering 🌀 This condition is characterized by long, in-order streams with occasional instances of reordering, sometimes with extreme correlation 💫 However, we do not expect packet delivery in a completely random order, where, for example, the last packet or the first packet in a sample is equally likely to arrive first at the destination 🙅♀️ Thus, we expect at least a minimal degree of order in the packet arrivals, as exhibited in real networks 🫶
the ability to restore order at the destination will likely have finite limits 🥲 Practical hosts have receiver buffers with finite size in terms of packets, bytes, or time (such as de-jitter buffers) 🎧 Once the initial determination of reordering is made, it is useful to quantify the extent of reordering, or lateness, in all meaningful dimensions 👑
1.2. Goals and Objectives ✨
okay so the definitions below are trying to hit two big goals 💅
- Figuring out whether packet reordering actually happened at all 👀
- Quantifying how much reordering there was. (We define a bunch of metrics for this, because receivers handle things differently depending on the protocol or app. The effects of reordering change with how the receiver behaves, so a metric that captures one receiver's key behavior might be totally irrelevant to a different receiver. If you report all the metrics defined below, you get a wide-ranging view of the reordering conditions 🦋)
Reordering Metrics MUST:
- have one or more applications, like receiver design or network characterization, plus a compelling relevance in the eyes of the community that's interested in them 🔥
- be computable "on the fly" ⏱️
- work even if the stream has duplicate or lost packets 🫶
it's desirable for Reordering Metrics to have one or more of these vibes too:
- the ability to concatenate results for segments measured separately, so you can estimate the reordering of an entire path 🧩
- simplicity, so they're easy to consume and understand 🎀
- relevance to TCP design 🌸
- relevance to real-time application performance 💜
the current set of metrics checks every requirement above and gives you everything except the concatenation attribute 😭 (the one exception is when measurements of path segments show no reordering, in which case you can estimate that the complete path made of those segments also shows no reordering ✨). BUT, and this is a big but, meeting these goals means the set is limited to metrics that give some clear insight into network characterization or receiver design. They're not likely to cover every reordering effect on applications, and more measurements might be possible 🧚
1.3. Required Context for All Reordering Metrics 🍓
ngl this part is so important. Reordering metrics are inseparably bonded to the measurement conditions 💖 Packet reordering isn't well defined unless you report the full measurement context, so every reordering metric definition includes these parameters:
- The "Packet of Type-P" [RFC2330] identifiers for the packet stream, including the transport addresses for source and destination, plus any other info that might lead to different packet treatments.
- The stream parameter set for the sending discipline, like the parameters unique to periodic streams (as in [RFC3432]), TCP-like streams (as in [RFC3148]), or Poisson streams (as in [RFC2330]). The stream parameters include the packet size, given either as a fixed value or as a pattern of sizes (whichever applies) 📏
Whenever a metric is reported, it MUST include a description of these parameters so the results have some context 🫶
2. Conventions Used in this Document 🎀
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. Yes, RFC 2119 was written with protocols in mind, but the key words get used here for similar reasons 🧠 They make sure results from two different implementations are comparable, and they flag moments when an implementation could perturb the network 🌈
In this memo, the characters <= should be read as "less than or equal to", and >= as "greater than or equal to" 💅
3. A Reordered Packet Singleton Metric 🦋
The IPPM framework [RFC2330] describes the notions of singletons, samples, and statistics. For easy reference:
By a 'singleton' metric, we refer to metrics that are, in a sense, atomic. For example, a single instance of "bulk throughput capacity" from one host to another might be defined as a singleton metric, even though the instance involves measuring the timing of a number of Internet packets.
Evaluating packet order takes a few supporting concepts 🧩 The first is an algorithm (function) that produces a series of strictly monotonically increasing identifiers, applied to packets at the source so the order of transmission is uniquely established. (A function, g(x), is strictly monotonically increasing if for any x>y, g(x)>g(y).) The unique sequence identifier can just be an incrementing consecutive integer message number, or a sequence number like the ones used below. The possibility of sequence number rollover gets discussed in Section 6 ⏳
The second concept is a stored value called the "next expected" packet number. Under normal conditions, Next Expected (NextExp) is the sequence number of the previous packet plus 1 for message numbering. (In general, the receiver reproduces the sender's algorithm and the sequence of identifiers so that the "next expected" value can be worked out ✨)
Each packet within a packet stream can be evaluated with this order singleton metric 💜
3.1. Metric Name 🌸
Type-P-Reordered
3.2. Metric Parameters 🧚
- Src, the IP address of a host.
- Dst, the IP address of a host.
- SrcTime, the time of packet emission from the source (or wire time).
- s, the unique packet sequence number applied at the source, in units of messages.
- NextExp, the next expected sequence number at the destination, in units of messages. The stored value in NextExp is determined from a previously arriving packet.
And optionally:
- PayloadSize, the number of bytes contained in the information field, referred to when the SrcByte sequence is based on bytes transferred.
- SrcByte, the packet sequence number applied at the source, in units of payload bytes.
3.3. Definition 🔥
If a packet s (sent at time, SrcTime) is found to be reordered by comparison with the NextExp value, its Type-P-Reordered = TRUE. Otherwise, Type-P-Reordered = FALSE, as defined below:
The value of Type-P-Reordered is defined as TRUE if s < NextExp (the packet is reordered). In this case, the NextExp value does not change.
The value of Type-P-Reordered is defined as FALSE if s >= NextExp (the packet is in-order). In this case, NextExp is set to s+1 for comparison with the next packet to arrive.
Since the NextExp value can't decrease, it gives you a non-reversing order criterion for spotting reordered packets 👑
This definition can also be written as pseudo-code 💻
On successful arrival of a packet with sequence number s:
if s >= NextExp then /* s is in-order */
NextExp = s + 1;
Type-P-Reordered = False;
else /* when s < NextExp */
Type-P-Reordered = True3.4. Sequence Discontinuity Definition 🌈
Packets with s > NextExp are a special case of in-order delivery. This condition indicates a sequence discontinuity, because of either packet loss or reordering. Reordered packets must arrive for the sequence discontinuity to be defined as a reordering discontinuity (see Section 4) 🫠
We define two different states for in-order packets 🎀
When s = NextExp, the original sequence has been maintained, and there's no discontinuity present ✨
When s > NextExp, some packets in the original sequence haven't arrived yet, and there's a sequence discontinuity associated with packet s. The size of the discontinuity is s - NextExp, which equals the number of packets presently missing, either reordered or lost 🍓
In pseudo-code:
On successful arrival of a packet with sequence number s:
if s >= NextExp, then /* s is in-order */
if s > NextExp then
SequenceDiscontinuty = True;
SeqDiscontinutySize = s - NextExp;
else
SequenceDiscontinuty = False;
NextExp = s + 1;
Type-P-Reordered = False;
else /* when s < NextExp */
Type-P-Reordered = True;
SequenceDiscontinuty = False;Whether any sequence discontinuities happen (and how big they are) depends on the conditions causing loss and/or reordering along the measurement path 🛤️ Note that a packet could be reordered at one point and then lost somewhere else on the path, but you can't know that from observations at the destination 👀
3.5. Evaluation of Reordering in Dimensions of Time or Bytes ⏰
You can use alternate dimensions of time or payload bytes to test for reordering in the definition of Section 3.3, as long as the SrcTimes and SrcBytes are unique and reliable 💖 Sequence discontinuities are easy to define and detect with message numbering, but it's not so simple in the dimensions of time or bytes. That's a detractor for the alternate dimensions, because the sequence discontinuity definition plays a key role in the sample metrics that follow 🙈
It's possible to detect sequence discontinuities with payload byte numbering, but only when the test device knows exactly what value to assign as NextExp in response to any packet arrival. That works when the complete pattern of payload sizes is stored at the destination, or if the size pattern can be generated using a pseudo-random number generator and a shared seed. If payload size is constant, byte numbering adds needless complexity over message numbering 🙄
It may be possible to detect sequence discontinuities with periodic streams and source time numbering, but there are practical pitfalls with sending exactly on-schedule and with clock reliability ⚠️
The dimensions of time and bytes still matter as an important basis for characterizing the extent of reordering, as described in Sections 4.3 and 4.4 🦋
3.6. Discussion 💬
Any arriving packet bearing a sequence number from the sequence that establishes the NextExp value can be evaluated to determine whether it's in-order or reordered, based on a previous packet's arrival. In the case where NextExp is Undefined (because the arriving packet is the first successful transfer), the packet is designated in-order (Type-P-Reordered=FALSE) 🧁
This metric assumes reassembly of packet fragments before evaluation. In principle, you can use the Type-P-Reordered metric to evaluate reordering among packet fragments, but each fragment must contain source sequence information. See Appendix B, "Fragment Order Evaluation", for more detail 🧩
If duplicate packets (multiple non-corrupt copies) arrive at the destination, they MUST be noted, and only the first to arrive is considered for further analysis (copies would be declared reordered according to the definition above). This requirement has the same storage implications as earlier IPPM metrics and follows the precedent of [RFC2679]. We provide a suggestion to minimize the storage size needed in Section 6 on Measurement and Implementation Issues 🌟
4. Sample Metrics ✨
okay so this section is all about metrics for a sample of packets that all come from one source sequence number system 🧚 when reordering happens, you really want to know how out-of-order each packet is compared to the others 👀 so these metrics measure the amount of reordering in different units. each one highlights a different use case, and they're giving main character energy 💅
the metrics below are mostly about describing what the network is doing, but they're also useful for receiver design, especially if you're trying to compensate for reordering 🫶 we'll start with the simplest one: a ratio that tells you what portion of the sample got reordered 🍓
4.1. Reordered Packet Ratio
4.1.1. Metric Name
Type-P-Reordered-Ratio-Stream
4.1.2. Metric Parameters
the parameter set includes the Type-P-Reordered singleton parameters 💖 plus the parameters that are unique to Poisson streams (see [RFC2330]), periodic streams (see [RFC3432]), or TCP-like streams (see [RFC3148]). it also includes packet size or size patterns, and these:
T0, a start timeTf, an end timedT, a waiting time for each packet to arrive, in secondsK, the total number of packets in the stream sent from source to destinationL, the total number of packets received (arriving betweenT0andTf+dT) out of theKpackets sent. recall that identical copies (duplicates) have been removed, soL <= K✨R, the ratio of reordered packets to received packets, defined below
note that dT is basically the threshold for declaring a packet as lost 🙈 the IPPM Packet Loss Metric [RFC2680] doesn't recommend a value for it. instead it says that "good engineering, including an understanding of packet lifetimes, will be needed in practice."
4.1.3. Definition
given a stream of packets sent from a source to a destination, the ratio of reordered packets in the sample is:
R = (Count of packets with Type-P-Reordered=TRUE) / ( L )you can express this fraction as a percentage if you multiply by 100 💅 and in the case of duplicate packets, only the first copy gets used 🌸
4.1.4. Discussion
when Type-P-Reordered-Ratio-Stream is zero, you don't need to look at any other reordering metrics for that sample 🦋 so its whole purpose is to summarize a sample that has no reordering at all, which is iconic ✨
4.2. Reordering Extent
this section defines how far packets get reordered, and it links a specific sequence discontinuity to each reordered packet 💜 it inherits the parameters we already defined above.
4.2.1. Metric Name
Type-P-Packet-Reordering-Extent-Stream
4.2.2. Notation and Metric Parameters
remember that K is the number of packets in the stream at the source, and L is the number of packets received at the destination 🎀
each packet gets a sequence number, s, which is a consecutive integer from 1 to K in the order the packets were transmitted (at the source) 🌈
let s[1], s[2], ..., s[L] represent the original sequence numbers of the packets, in the order they arrived 💖
you can think of s[i] as a vector, where the index i is the arrival position of the packet with sequence number s 🧚 in theory, any source sequence number could show up in any arrival position, but that's unlikely in reality 🙈
now, think about a reordered packet (Type-P-Reordered=TRUE) with arrival index i and source sequence number s[i]. there is a set of indexes j (with 1 <= j < i) such that s[j] > s[i] 👀
the new parameters are:
i, the index for arrival position, wherei-1means an arrival earlier thanij, a set of one or more arrival indexes, where1 <= j < is[i], the original sequence numbers,s, in order of arrivale, the Reordering Extent, in units of packets, defined below
4.2.3. Definition
the reordering extent, e, of packet s[i] is defined as i-j for the smallest value of j where s[j] > s[i] ✨
informally, the reordering extent is the maximum distance (in packets) from a reordered packet back to the earliest packet that arrived with a larger sequence number 💅 if a packet is in-order, its reordering extent is undefined 🌸 and the very first packet to arrive is in-order by definition, so it also has an undefined reordering extent.
comment on the definition of extent: for some arrival orders, a simple position or distance as the reordering extent tends to overestimate the receiver storage needed to restore order 😭 a more accurate (but more complex) way to calculate packet storage would be to subtract any earlier reordered packets that the receiver could pass up to the upper layers (see the Byte Offset metric). once you understand that bias, this definition is considered good enough, especially for people who need "on the fly" calculations 🔥
4.2.4. Discussion
the packet with index j (s[j], which we identified in the Definition above) is the reordering discontinuity associated with packet s at index i (s[i]) 💖 this is formalized below.
the K packets in the stream could be a subset of a bigger stream, but L is still the total number of packets received out of the K packets sent in that subset 🎀
if a receiver wants to restore order, its buffer capacity decides how well it can handle reordered packets 🫶 for single reordered packets, the extent e tells you how many packets have to sit in the receiver's buffer while it waits for the reordered packet to complete the sequence 👑 for more complicated scenarios, the extent might overestimate the storage you need (see Section 4.4 on Reordering Byte Offset and the examples in Section 7). also, if the receiver clears its buffer for any reason, the extent metric won't reflect that, since it assumes the receiver would try exhaustively to restore order 🙈
even though reordering extent is mainly about the offset in arrival position, it can also help you figure out what portion of reordered packets can or can't be put back in order in a typical receiver buffer, based only on their arrival order (without any retransmission) 🦋
a sample's reordering extents can be shown as a histogram, which is an easy way to summarize how often each extent shows up 📊✨
4.3. Reordering Late Time Offset
reordered packets can get offset values that show how late they are, in terms of the buffer time a receiver needs to hold them 💜 offset metrics are only calculated for reordered packets, which are identified by the reordered packet singleton metric in Section 3.
4.3.1. Metric Name
Type-P-Packet-Late-Time-Stream
4.3.2. Metric Parameters
on top of the parameters defined for Type-P-Reordered-Ratio-Stream, we also specify:
DstTime, the time that each packet in the stream arrives at the destination, which may be associated with indexi, or with packets[i]LateTime(s[i]), the offset of packets[i]in units of seconds, defined below
4.3.3. Definition
lateness in time is calculated using destination times 🌸 when received packet s[i] is reordered and has a reordering extent e, then:
LateTime(s[i]) = DstTime(i)-DstTime(i-e)alternatively, using similar notation to Section 4.2, an equivalent definition is:
LateTime(s[i]) = DstTime(i)-DstTime(j), for min{j|1<=j<i} that satisfies s[j]>s[i].4.3.4. Discussion
offset metrics can help predict whether reordered packets will be useful in a general receiver buffer system that has finite limits 🎀 that limit might be the amount of time you can store packets before a cyclic play-out instant (like with de-jitter buffers) ✨
note that the one-way IP Packet Delay Variation (IPDV) [RFC3393] gives the delay variation for a packet compared to the packet right before it in the source sequence 👀 lateness and IPDV both tell you whether a buffer at the destination has enough storage to handle the network's behavior and put everything back in order 💅 when an earlier packet in the source sequence is lost, IPDV will always be undefined for adjacent packets, so LateTime might be the only way to tell whether a packet is still useful 😭
with de-jitter buffers, the receiver sometimes uses loss concealment at the intended play-out time of a late packet 🧚 but if that packet shows up out of order, the Late Time tells you whether it's still useful 🦋 IPDV doesn't apply anymore, because the receiver sets up a new play-out schedule with extra buffer delay to handle similar events in the future (this takes very minimal processing) 🌈
the combination of loss and reordering affects the LateTime metric 🙈 if you get the arrival sequence 1, 10, 5 (where packets 2, 3, 4, and 6 through 9 are lost), LateTime wouldn't tell you exactly how "late" packet 5 is from its intended arrival position 😭 IPDV [RFC3393] wouldn't capture it either, because there aren't any adjacent packet pairs. assuming a periodic stream [RFC3432], you could define an expected arrival time for all packets, but that's basically a single-point delay variation metric (as defined in the ITU-T Recommendations [I.356] and [Y.1540]), not a reordering metric 💖
a sample's LateTime results can be shown as a histogram, which summarizes how often each buffer time is needed to accommodate reordered packets and lets you tune buffers on that basis 📊 a cumulative distribution function (CDF) of buffer time vs. percent of reordered packets accommodated can be really informative too 💜
4.4. Reordering Byte Offset
reordered packets can also get offset values that show how many bytes of storage a receiver must have to accommodate them 🦋 again, offset metrics are only calculated on reordered packets, as identified by the reordered packet singleton metric in Section 3.
4.4.1. Metric Name
Type-P-Packet-Byte-Offset-Stream
4.4.2. Metric Parameters
we use the same parameters defined earlier, including the optional parameters SrcByte and PayloadSize, and we define:
ByteOffset(s[i]), the offset of packets[i]in bytes
4.4.3. Definition
the byte stream offset for reordered packet s[i] is the sum of the payload sizes of the packets that meet these criteria 🌸
- the arrival is before the reordered packet,
s[i], and - the send sequence number,
s, is greater thans[i].
packets that meet both of these criteria are normally buffered until the sequence beneath them is complete 🫶 note that these criteria apply to both in-order and reordered packets ✨
for reordered packet s[i] with a reordering extent e:
ByteOffset(s[i]) = Sum[qualified packets]
= Sum[PayloadSize(packet at i-1 if qualified),
PayloadSize(packet at i-2 if qualified), ...
PayloadSize(packet at i-e always qualified)]using our earlier notation:
ByteOffset(s[i]) =
Sum[payloads of s[j] where s[j]>s[i] and i > j >= i-e]4.4.4. Discussion 💖
okay bestie, buffer size estimates from reordering depend SO much on the test stream 😭 like how far apart the test packets are and how big they are, especially when the sizes keep changing 🌸 in these situations (and others), it's giving most useful to describe the offset by the payload size(s) of the stored packets, using the Type-P-packet-Byte-Offset-Stream metric 🎀
the byte offset metric can help predict whether reordered packets will be useful in a general receiver buffer system with finite limits ✨ the limit is expressed as the number of bytes the buffer can store 🧚
a sample's ByteOffset results can be shown as a histogram to summarize how often different buffer lengths are needed to accommodate reordered packets, so you can tune buffers based on that 📊 a CDF with buffer size vs. percent of reordered packets accommodated may be informative too 💅
4.5. Gaps between Multiple Reordering Discontinuities 🦋
4.5.1. Metric Names
Type-P-Packet-Reordering-Gap-Stream
Type-P-Packet-Reordering-GapTime-Stream4.5.2. Parameters
we use the same parameters defined earlier, but add the convention that index i' is greater than i, likewise j' > j, and define:
Gap(s[j']), the Reordering Gap of packets[j']in units of integer messages
and the OPTIONAL parameter:
GapTime(s[j']), the Reordering Gap of packets[j']in units of seconds 🌈
4.5.3. Definition of Reordering Discontinuity
all reordered packets are associated with a packet at a reordering discontinuity, defined as the in-order packet s[j] that arrived at the minimum value of j (1<=j<i) for which s[j]> s[i] 🔥
note that s[j] will have been found to cause a sequence discontinuity, where s > NextExp when evaluated with the reordered singleton metric as described in Section 3.4 🙈
recall that i - e = min(j) 💜 subsequent reordered packets may be associated with the same s[j], or with a different discontinuity. this fact is used in the definition of the Reordering Gap, below ✨
4.5.4. Definition of Reordering Gap
a reordering gap is the distance between successive reordering discontinuities 🍓 the Type-P-Packet-Reordering-Gap-Stream metric assigns a value for Gap(s[j']) to (all) packets in a stream (and a value for GapTime(s[j']), when reported) 🎀
if:
- the packet
s[j']is found to be a reordering discontinuity, based on the arrival of reordered packets[i']with extente', and - an earlier reordering discontinuity
s[j], based on the arrival of reordered packets[i]with extentewas already detected, and i' > i, and- there are no reordering discontinuities between
jandj',
then the Reordering Gap for packet s[j'] is the difference between the arrival positions the reordering discontinuities, as shown below:
Gap(s[j']) = (j') - (j)Gaps MAY also be expressed in time:
GapTime(s[j']) = DstTime(j') - DstTime(j)otherwise, Gap(s[j']) (and GapTime(s[j']) ) for packet s[j'] is 0 🫶
4.5.5. Discussion
when separate reordering discontinuities can be distinguished, a count may also be reported 🧁 (along with the discontinuity description, such as the number of reordered packets associated with that discontinuity and their extents and offsets). the Gaps between a sample's reordering discontinuities may be expressed as a histogram to easily summarize the frequency of various gaps. reporting the mode, average, range, etc., may also summarize the distributions 📈
the Gap metric may help to correlate the frequency of reordering discontinuities with their cause 🔍 gap lengths are also informative to receiver designers, revealing the period of reordering discontinuities 🌸 the combination of reordering gaps and extent reveals whether receivers will be required to handle cases of overlapping reordered packets 👑
4.6. Reordering-Free Runs 🌷
this section defines a metric based on a count of consecutive in-order packets between reordered packets 🦋
4.6.1. Metric Names
Type-P-Packet-Reordering-Free-Run-x-numruns-Stream
Type-P-Packet-Reordering-Free-Run-q-squruns-Stream
Type-P-Packet-Reordering-Free-Run-p-numpkts-Stream
Type-P-Packet-Reordering-Free-Run-a-accpkts-Stream4.6.2. Parameters
we use the same parameters defined earlier and define the following 💅
r, the run counterx, the number of runs, also the number of reordered packetsa, the accumulator of in-order packetsp, the number of packets (when the stream is complete,p=(x+a)=L)q, the sum of the squares of the runs counted
4.6.3. Definition
as packets in a sample arrive at the destination, the count of in-order packets between reordered packets is a Reordering-Free run 🏃♀️ note that the minimum run-length is zero according to this definition. a pseudo-code example follows:
r = 0; /* r is the run counter */
x = 0; /* x is the number of runs */
a = 0; /* a is the accumulator of in-order packets */
p = 0; /* p is the number of packets */
q = 0; /* q is the sum of the squares of the runs counted */
while(packets arrive with sequence number s)
{
p++;
if (s >= NextExp) /* s is in-order */
then r++;
a++;
else /* s is reordered */
q+= r*r;
r = 0;
x++;
}each in-order arrival increments the run counter and the accumulator of in-order packets 🎀 each reordered packet resets the run counter after adding it to the sum of the squared lengths ✨
each arrival of a reordered packet yields a new run count. long runs accompany periods where order was maintained, while short runs indicate frequent or multi-packet reordering 🌊
the percent of packets in-order is 100*a/p 🍰
the average Reordering-Free run length is a/x 💖
the q counter gives an indication of variation of the Reordering-Free runs from the average by comparing q/a to a/x ((q/a)/(a/x)) 🔥
4.6.4. Discussion and Illustration
Type-P-packet-Reordering-Free-Run-Stream parameters give a brief summary of the stream's reordering characteristics including the average reordering-free run length, and the variation of run lengths 🧠 therefore, a key application of this metric is network evaluation 🌈
for 36 packets with 3 runs of 11 in-order packets, we have:
p = 36
x = 3
a = 33
q = 3 * (11*11) = 363
ave. reordering-free run = 11
q/a = 11
(q/a)/(a/x) = 1.0for 36 packets with 3 runs, 2 runs of length 1, and one of length 31, we have:
p = 36
x = 3
a = 33
q = 1 + 1 + 961 = 963
ave. reordering-free run = 11
q/a = 29.18
(q/a)/(a/x) = 2.65the variability in run length is prominent in the difference between the q values (sum of the squared run lengths) and in comparing average run length to the (q/a)/(a/x) ratios (equals 1 when all runs are the same length) 👑😭
5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric 💅
this section describes a metric that conveys information associated with the effect of reordering on TCP 🦋 however, in order to infer anything about TCP performance, the test stream MUST bear a close resemblance to the TCP sender of interest. [RFC3148] lists the specific aspects of congestion control algorithms that must be specified. further, RFC 3148 recommends that Bulk Transfer Capacity metrics SHOULD have instruments to distinguish three cases of packet reordering (in Section 3.3) ✨ the sample metrics defined above satisfy the requirements to classify packets that are slightly or grossly out-of-order 🧚 the metric in this section adds the capability to estimate whether reordering might cause the DUP-ACK threshold to be exceeded causing the Fast Retransmit algorithm to be invoked. additional TCP Kernel Instruments are summarized in [Mat03] 🔍
5.1. Metric Name
Type-P-Packet-n-Reordering-Stream5.2. Parameter Notation
let n be a positive integer (a parameter). let k be a positive integer equal to the number of packets sent (sample size). let l be a non-negative integer representing the number of packets that were received out of the k packets sent. (note that there is no relationship between k and l: on one hand, losses can make l less than k; on the other hand, duplicates can make l greater than k.) assign each sent packet a sequence number, 1 to k, in order of packet emission 🌸
let s[1], s[2], ..., s[l] be the original sequence numbers of the received packets, in the order of arrival 💖
5.3. Definitions
Definition 1: received packet number i (n < i <= l), with source sequence number s[i], is n-reordered if and only if for all j such that i-n <= j < i, s[j] > s[i] 🎀
Claim: if, by this definition, a packet is n-reordered and 0 < n' < n, then the packet is also n'-reordered 🧠
Note: this definition is illustrated by C code in Appendix A. the code determines and reports the n-reordering for n from 1 to a specified parameter (MAXN in the code, set to 100). the value of n conjectured to be relevant for TCP is the TCP duplicate ACK threshold (set to the value of 3 by paragraph 2 of Section 3.2 of [RFC 2581]) 🍓
this definition does not assign an n to all reordered packets as defined by the singleton metric, in particular when blocks of successive packets are reordered. (in the arrival sequence s={1,2,3,7,8,9,4,5,6}, packets 4, 5, and 6 are reordered, but only packet 4 is n-reordered, with n=3.) 🙈
Definition 2: the degree of n-reordering of a sample is m/l, where m is the number of n-reordered packets in the sample 📊
Definition 3: the degree of monotonic reordering of a sample is its degree of 1-reordering 🌈
Definition 4: a sample is said to have no reordering if its degree of monotonic reordering is 0 ✨
Note: as follows from the claim above, if monotonic reordering of a sample is 0, then the n-reordering of the sample is 0 for all n 💜
5.4. Discussion 🎀
okay so the degree of n-reordering can be written as a percentage, and you just multiply the Definition 2 number by 100 💅
the n-reordering metric is seriously helpful for matching your duplicate ACK threshold to a specific path ✨ like, if a path shows no more than 5-reordering, a DUP-ACK threshold of 6 may avoid unnecessary retransmissions. main character energy for the threshold 🦋
two special cases are lowkey the most important, n=1 and n=3 👑
- for
n=1, no 1-reordering means the sequence numbers the receiver sees are monotonically increasing compared to the previous arriving packet 🌸 - for
n=3, a NewReno TCP sender would retransmit 1 packet after an instance of 3-reordering and therefore treat that packet as lost for congestion control purposes (the sender halves its congestion window, see [RFC2581]) 😭 three is the default threshold for Stream Control Transport Protocol (SCTP) [RFC2960], and for the Datagram Congestion Control Protocol (DCCP) [RFC4340] when it's used with Congestion Control ID 2: TCP-like Congestion Control [RFC4341] 🧚
a sample's n-reordering can be shown as a histogram to summarize how frequent each value of n is 🍓
ngl, the definition of n-reordering can't predict the exact number of packets a TCP sender will unnecessarily retransmit in some situations, like closely-spaced reordered singletons 💀 both time and position influence how the sender behaves. iykyk 🙈
a packet's n-reordering designation is sometimes the same as its reordering extent, e. but they're different in these ways:
- n is a count of early packets with consecutive arrival positions at the receiver.
- Reordered packets (
Type-P-Reordered=TRUE) may not be n-reordered, but they will have an extent, e (see the examples) ✨
6. Measurement and Implementation Issues 🌈
the results of tests depend on the time interval between measurement packets (both at the source, and during transport, where spacing may change) 🦋 clearly, packets launched infrequently (e.g., 1 per 10 seconds) are unlikely to get reordered, so it's giving "no drama" 💤
if you want to gauge reordering for an application using the metrics in this memo, it is RECOMMENDED to use the same sending pattern as that application 🫶 in any case, the exact method of packet generation MUST be reported with the measurement results, including all stream parameters. no skipping that part, bestie 📋
- to make inferences about applications that use TCP, it is REQUIRED to use TCP-like Streams as in [RFC3148] 💖
- for real-time applications, it is RECOMMENDED to use periodic streams as in [RFC3432] 🎀
it's acceptable to report the metrics of Sections 3 and 4 alongside other IPPM metrics using Poisson streams [RFC2330]. Poisson streams represent an "unbiased sample" of network performance for packet loss and delay metrics ✨ however, it would be incorrect to make inferences about the application categories above using reordering metrics measured with Poisson streams. not me making that mistake 🙅♀️
test stream designers may prefer a periodic sending interval so they keep a known temporal bias and get simplified results analysis (as described in [RFC3432]) 🍓 in this case, it is RECOMMENDED that the periodic sending interval be chosen to reproduce the closest source packet spacing expected 🌸 testers have to recognize that streams sent at the link speed serialization limit MUST have limited duration, and they MUST consider packet loss an indication that the stream has caused congestion, then suspend further testing 🚨 this is a big deal, babe.
when you want to compare independent measurements of reordering, it is RECOMMENDED to use the same test stream parameters in each measurement system 💜
packet lengths might also be varied to try to detect instances of parallel processing (they may cause steady state reordering) 🧚 for example, a line-speed burst of the longest (MTU-length) packets followed by a burst of the shortest possible packets may be an effective detecting pattern. other size patterns are possible too 🌈
the non-reversing order criterion and all the metrics described above stay valid and useful when a stream of packets experiences packet loss, or both loss and reordering 🦋 in other words, losses alone do not cause subsequent packets to be declared reordered. so relax, the loss isn't making things look out of order 😌
since this metric definition may use sequence numbers with a finite range, the sequence numbers could reach end-of-range and roll over to zero during a measurement 😭 by definition, the NextExp value cannot decrease, and all packets received after a rollover would be declared reordered. yikes 💀 sequence number rollover can be avoided by using combinations of counter size and test duration where rollover is impossible (and the sequence is reset to zero at the start) ✨ also, message-based numbering results in slower sequence consumption. there may still be cases where methodological mitigation of this problem is desirable (e.g., long-term testing) 🫶 the elements of mitigation are:
- there must be a test to detect if a rollover has occurred. it would be nearly impossible for the sequence numbers of successive packets to jump by more than half the total range, so these large discontinuities are designated as rollover 🔥
- all sequence numbers used in computations are represented in a sufficiently large precision. the numbers get a correction applied (equivalent to adding a significant digit) whenever rollover is detected 🧮
- reordered packets coincident with sequence numbers reaching end-of-range must also be detected for proper application of the correction factor 👑
ideally, the test instrument would be able to use all earlier packets at any point in the test stream 🌸 in practice, though, there will be limited ability to determine the extent of reordering, because of the storage requirements for previous packets. saving only packets that indicate discontinuities (and their arrival positions) will reduce storage volume 💅
another solution is a sliding history window of packets, where the window size is determined by an upper bound on the useful reordering extent 🦋 this bound could be several packets or several seconds' worth of packets, depending on the intended analysis. when all stream information beyond the window gets discarded, the reordering extent or degree of n-reordering may need to be expressed as greater than the window length if the reordering discontinuity information has been thrown away, and Gap calculations would not be possible 😩
the requirement to ignore duplicate packets also means storage 🗂️ tracking the sequence numbers of missing packets can minimize storage size. missing packets may eventually be declared lost, or be reordered if they arrive 🌈 the missing packet list and the largest sequence number received so far (NextExp - 1) are sufficient information to determine if a packet is a duplicate (assuming a manageable storage size for packets that are missing due to loss) 🧚
it's important to note that practical IP networks also have limited ability to "store" packets, even when routing loops appear temporarily 🌀 so the maximum storage for reordering metrics (and their complexity) would only approach the number of packets in the sample, K, when the sending time for K packets is small compared to the network's largest possible transfer time ⏳ another possible limit on storage is the maximum length of the sequence number field, assuming most test streams don't exhaust this length in practice 💖
last, determining reordering extents and gaps is tricky when there are overlapped or nested events 😵💫 test instrument complexity and reordering complexity are directly correlated. period 💅
6.1. Passive Measurement Considerations 🔍
as with other IPPM metrics, the definitions were built primarily for Active measurements 🎀
assuming the necessary sequence information (message number) is included in the packet payload (possibly in application headers such as RTP), reordering metrics can be evaluated in a passive measurement arrangement ✨ it's also possible to evaluate order at any point along a source-destination path, recognizing that intermediate measurements may differ from those made at the destination (where the reordering effect on applications can be inferred) 🦋
it's possible to apply these metrics to evaluate reordering in a TCP sender's stream 🌸 in this case, the source sequence numbers would be based on byte stream or segment numbering. since the stream may include retransmissions due to loss or reordering, care must be taken to avoid declaring retransmitted packets reordered 😬 the additional sequence reference of s or SrcTime helps avoid this ambiguity in active measurement, or the optional TCP timestamp field [RFC1323] does it in passive measurement 🫶
7. Examples of Arrival Order Evaluation 🧁
this section gives some examples to show how the non-reversing order criterion works, how n-reordering works in comparison, and why it's worth quantifying reordering in all the dimensions of time, bytes, and position 🌈 it's giving data nerd and I'm here for it 🤓
throughout this section, we'll refer to packets by their source sequence number, except where noted. so "Packet 4" means the packet with source sequence number 4 💜 and the reader should check the tables in each example to find packet 4's arrival index number, if needed 📊
7.1. Example with a Single Packet Reordered ✨
okay so Table 1 is the simplest reordering case ever 💖 only ONE packet gets reordered, and that's Packet 4 🧚 packets are listed by when they arrive, and we use message numbers. every packet has PayloadSize=100 bytes, with SrcByte=(s x 100)-99 for s=1,2,3,4,...
Table 1: Example with Packet 4 Reordered,
Sending order( s @Src): 1,2,3,4,5,6,7,8,9,10
s Src Dst Dst Byte Late
@Dst NextExp Time Time Delay IPDV Order Offset Time
-----------------------------------------------------------------
1 1 0 68 68 1
2 2 20 88 68 0 2
3 3 40 108 68 0 3
5 4 80 148 68 -82 4
6 6 100 168 68 0 5
7 7 120 188 68 0 6
8 8 140 208 68 0 7
4 9 60 210 150 82 8 400 62
9 9 160 228 68 0 9
10 10 180 248 68 0 10here's what each column is giving us:
s: the packet's sequence number at the source.NextExp: the value of NextExp when the packet arrived, before it got updated.SrcTime: the packet's time stamp at the source, in ms.DstTime: the packet's time stamp at the destination, in ms.Delay: the 1-way delay of the packet, in ms.IPDV: IP Packet Delay Variation, in ms. It'sIPDV = Delay(SrcNum)-Delay(SrcNum-1).DstOrder: the order the packet showed up in at the destination.Byte Offset: how far off a reordered packet is, in bytes.LateTime: how late a reordered packet is, in ms.
so when Packet 4 shows up, NextExp=9, and it gets declared reordered 👀 now we work out the extent of the reordering. we write the received packets as <s[1], ..., s[i], ..., s[L]>, like this:
\/
s = 1, 2, 3, 5, 6, 7, 8, 4, 9, 10
i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
/\then we apply the definition of Type-P-Packet-Reordering-Extent-Stream:
when j=7, 8 > 4, so the reordering extent is 1 or more.
when j=6, 7 > 4, so the reordering extent is 2 or more.
when j=5, 6 > 4, so the reordering extent is 3 or more.
when j=4, 5 > 4, so the reordering extent is 4 or more.
when j=3, but 3 < 4, and 4 is the maximum extent, e=4 (assuming
there are no earlier sequence discontinuities, as in this example).so the extent comes out to e=4 💅
we can also work out the Late Time, which is 210-148=62ms using DstTime, compared to Packet 5's arrival. if the receiver has a de-jitter buffer that holds more than 4 packets, or at least 62 ms of storage, then Packet 4 may still be useful 🫶 also, 1-way delay and IPDV are both acting weird for Packet 4. and if Packet 4 had shown up at least 62ms earlier, it would've been in-order in this example. main character energy but make it late 💀
if every packet had a 100 byte payload, then the Byte Offset works out to 400 bytes.
following the definitions in Section 5.1, Packet 4 gets designated 4-reordered 🦋
7.2. Example with Two Packets Reordered 🌸
Table 2 is a case where Packets 5 and 6 both arrive late 😭
Table 2 Example with Packets 5 and 6 Reordered,
Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10
s Src Dst Dst Byte Late
@Dst NextExp Time Time Delay IPDV Order Offset Time
-----------------------------------------------------------------
1 1 0 68 68 1
2 2 20 88 68 0 2
3 3 40 108 68 0 3
4 4 60 128 68 0 4
7 5 120 188 68 -22 5
5 8 80 189 109 41 6 100 1
6 8 100 190 90 -19 7 100 2
8 8 140 208 68 0 8
9 9 160 228 68 0 9
10 10 180 248 68 0 10so Packets 5 and 6 arrive right behind Packet 7, which means both 5 and 6 count as reordered 🎀 their Late times are small too (189-188=1, 190-188=2).
we write the received packets as <s[1], ..., s[i], ..., s[l]>:
\/ \/
s = 1, 2, 3, 4, 7, 5, 6, 8, 9, 10
i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
/\ /\starting with Packet 5:
when j=5, 7 > 5, so the reordering extent is 1 or more.
when j=4, we have 4 < 5, so 1 is its maximum extent, and e=1.then Packet 6:
when j=6, 5 < 6, the extent is not yet defined.
when j=5, 7 > 6, so the reordering extent is i-j=2 or more.
when j=4, 4 < 6, and we find 2 is its maximum extent, and e=2.we can also link each reordered packet to a reordering discontinuity. we find the minimum j=5 for both packets, following Section 4.2.3. so Packet 6 is tied to the same discontinuity as Packet 5, which is the Reordering Discontinuity at Packet 7 🔥
this is a case where the reordering extent e would over-estimate the packet storage needed to restore order. only one packet's worth of storage is needed (to hold Packet 7), but e=2 for Packet 6 🙈
following the definitions in Section 5, Packet 5 is designated 1-reordered, but Packet 6 is not designated n-reordered 🫶
a hypothetical sender and receiver pair might retransmit Packet 5 for no reason, since it's 1-reordered (which matches the singleton metric). Packet 6 probably won't get retransmitted unnecessarily, but the receiver can't move Packet 7 up to the higher layers until Packet 6 arrives. so the singleton metric correctly figured out that Packet 6 is reordered ✨
7.3. Example with Three Packets Reordered 🧚
Table 3 is where three packets in a row have long transit times (Packets with s = 4, 5, and 6) 😭
Table 3 Example with Packets 4, 5, and 6 reordered
Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11
s Src Dst Dst Byte Late
@Dst NextExp Time Time Delay IPDV Order Offset Time
-----------------------------------------------------------------
1 1 0 68 68 1
2 2 20 88 68 0 2
3 3 40 108 68 0 3
7 4 120 188 68 -88 4
8 8 140 208 68 0 5
9 9 160 228 68 0 6
10 10 180 248 68 0 7
4 11 60 250 190 122 8 400 62
5 11 80 252 172 -18 9 400 64
6 11 100 256 156 -16 10 400 68
11 11 200 268 68 0 11Delay, Late time, and Byte Offset capture this really well and show the variation in reordering extent 📈 while IPDV shows that the spacing between Packets 4, 5, and 6 has changed.
the histogram of reordering extents (e) looks like this:
Bin 1 2 3 4 5 6 7
Frequency 0 0 0 1 1 1 0we write the received packets as <s[1], ..., s[i], ..., s[l]>:
s = 1, 2, 3, 7, 8, 9,10, 4, 5, 6, 11
i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11we start by calculating the n-reordering, beginning with Packet 4:
when n=1, 7<=j<8, and 10> 4, so the packet is 1-reordered.
when n=2, 6<=j<8, and 9 > 4, so the packet is 2-reordered.
when n=3, 5<=j<8, and 8 > 4, so the packet is 3-reordered.
when n=4, 4<=j<8, and 7 > 4, so the packet is 4-reordered.
when n=5, 3<=j<8, but 3 < 4, and 4 is the maximum n-reordering.then Packet 5[9]:
when n=1, 8<=j<9, but 4 < 5, so the packet at i=9 is not designated
as n-reordered. We find the same result for Packet 6.next we check whether reordered Packets 5 and 6 belong to the same reordering discontinuity as Packet 4. using the test in Section 4.2.3, the minimum j=4 for all three packets. so they're all tied to the reordering discontinuity at Packet 7 🎀
this example shows again that the n-reordering definition picks out a single packet (Packet 4) with enough n-reordering to possibly cause one unnecessary retransmission by the New Reno TCP sender (with DUP-ACK threshold=3 or 4). also, the reordered arrival of Packets 5 and 6 lets the receiver pass Packets 7 through 10 up the protocol stack (the singleton Type-P-Reordered = TRUE for Packets 5 and 6, and they're all tied to one reordering discontinuity) 💖
7.4. Example with Multiple Packet Reordering Discontinuities 👑
Table 4 has multiple reordering discontinuities going on at once 🌈
Table 4 Example with Multiple Packet Reordering Discontinuities
Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
Discontinuity Discontinuity
|---------Gap---------|
s = 1, 2, 3, 6, 7, 4, 5, 8, 9, 10, 12, 13, 11, 14, 15, 16
i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
r = 1, 2, 3, 4, 5, 0, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, ...
number of runs,n = 1 2 3
end r counts = 5 0 5
(These values are computed after the packet arrives.)Packet 4 has extent e=2, Packet 5 has extent e=3, and Packet 11 has e=2. there are two different reordering discontinuities, one at Packet 6 (where j=4) and one at Packet 12 (where j'=11) 👀
following the definition of Reordering Gap:
Gap(s[j']) = (j') - (j)
Gap(Packet 12) = (11) - (4) = 7we also have three reordering-free runs, with lengths 5, 0, and 5.
the differences between these two multiple-event metrics are obvious here 💅 Gaps are the distance between sequence discontinuities that later get defined as reordering discontinuities, while reordering-free runs capture the distance between reordered packets. iykyk 🧠
8. Security Considerations 🔐
8.1. Denial-of-Service Attacks 💀
this metric needs a stream of packets sent from one host (the source) to another host (the destination) through the networks in between. this method could be abused for denial-of-service attacks aimed at the destination and/or the intervening network(s). yikes, not cute 😭
The administrators of the source, destination, and intervening network(s) should set up bilateral or multilateral agreements about the timing, size, and frequency of collecting sample metrics. using this method beyond what the participants agreed to may get packets rejected or discarded right away, or lead to other escalation procedures the affected parties have defined.
8.2. User Data Confidentiality 🔒
active use of this method generates packets for a sample, rather than taking samples from user data, so it doesn't threaten user data confidentiality 🫶 passive measurement has to restrict its attention to the headers of interest. since user payloads may be stored temporarily for length analysis, suitable precautions MUST be taken to keep this information safe and confidential 🚨 in most cases, a hashing function will give a value that's good enough for payload comparisons.
8.3. Interference with the Metric 🎀
okay so it might be possible to spot that a certain packet or stream of packets is part of a sample 👀 and if the destination or the networks in between know that, they could change how they handle those packets (like adding or removing delay) 😬 which can totally distort the measured performance. It may also be possible to generate extra packets that look like part of the sample metric. Those extra packets are likely to mess with the sample results. ngl that's a whole vibe-killer 💀 The likely consequences of packet injection are that the extra packets would get declared duplicates, or that the original packets would be seen as duplicates (if they arrive after the matching injected packets), which leads to invalid measurements on the injected packets 🙈
The requirements for data collection resistance to interference by malicious parties, and the mechanisms to get that resistance, are covered in other IPPM memos 🦋 A set of requirements for a data collection protocol can be found in [RFC3763], and a protocol specification for the One-Way Active Measurement Protocol (OWAMP) is in [RFC4656]. The security considerations sections of the two OWAMP documents are extensive and should be consulted for additional details 📚 go read them, bestie!
9. IANA Considerations 🌈
Metrics defined in this memo have been registered in the IANA IPPM METRICS REGISTRY, as described in the initial version of the registry [RFC4148] ✨
IANA has registered the following metrics in the IANA-IPPM-METRICS-REGISTRY-MIB 💖
ietfReorderedSingleton OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Reordered"
REFERENCE
"Reference RFC 4737, Section 3"
::= { ianaIppmMetrics 34 }
ietfReorderedPacketRatio OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Reordered-Ratio-Stream"
REFERENCE
"Reference RFC 4737, Section 4.1"
::= { ianaIppmMetrics 35 }
ietfReorderingExtent OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Packet-Reordering-Extent-Stream"
REFERENCE
"Reference RFC 4737, Section 4.2"
::= { ianaIppmMetrics 36 }
ietfReorderingLateTimeOffset OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Packet-Late-Time-Stream"
REFERENCE
"Reference RFC 4737, Section 4.3"
::= { ianaIppmMetrics 37 }
ietfReorderingByteOffset OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Packet-Byte-Offset-Stream"
REFERENCE
"Reference RFC 4737, Section 4.4"
::= { ianaIppmMetrics 38 }
ietfReorderingGap OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Packet-Reordering-Gap-Stream"
REFERENCE
"Reference RFC 4737, Section 4.5"
::= { ianaIppmMetrics 39 }
ietfReorderingGapTime OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Packet-Reordering-GapTime-Stream"
REFERENCE
"Reference RFC 4737, Section 4.5"
::= { ianaIppmMetrics 40 }
ietfReorderingFreeRunx OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Packet-Reordering-Free-Run-x-numruns-Stream"
REFERENCE
"Reference RFC 4737, Section 4.6"
::= { ianaIppmMetrics 41 }
ietfReorderingFreeRunq OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Packet-Reordering-Free-Run-q-squruns-Stream"
REFERENCE
"Reference RFC 4737, Section 4.6"
::= { ianaIppmMetrics 42 }
ietfReorderingFreeRunp OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Packet-Reordering-Free-Run-p-numpkts-Stream"
REFERENCE
"Reference RFC 4737, Section 4.6"
::= { ianaIppmMetrics 43 }
ietfReorderingFreeRuna OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Packet-Reordering-Free-Run-a-accpkts-Stream"
REFERENCE
"Reference RFC 4737, Section 4.6"
::= { ianaIppmMetrics 44 }
ietfnReordering OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Packet-n-Reordering-Stream"
REFERENCE
"Reference RFC 4737, Section 5"
::= { ianaIppmMetrics 45 }10. Normative References 💜
[RFC791]Postel, J., "Internet Protocol", STD 5, RFC 791, September 1981.[RFC2119]Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.[RFC2330]Paxson, V., Almes, G., Mahdavi, J., and M. Mathis, "Framework for IP Performance Metrics", RFC 2330, May 1998.[RFC2460]Deering, S. and R. Hinden, "Internet Protocol, Version 6 (IPv6) Specification", RFC 2460, December 1998.[RFC3148]Mathis, M. and M. Allman, "A Framework for Defining Empirical Bulk Transfer Capacity Metrics", RFC 3148, July 2001.[RFC3432]Raisanen, V., Grotefeld, G., and A. Morton, "Network performance measurement with periodic streams", RFC 3432, November 2002.[RFC3763]Shalunov, S. and B. Teitelbaum, "One-way Active Measurement Protocol (OWAMP) Requirements", RFC 3763, April 2004.[RFC4148]Stephan, E., "IP Performance Metrics (IPPM) Metrics Registry", BCP 108, RFC 4148, August 2005.[RFC4656]Shalunov, S., Teitelbaum, B., Karp, A., Boote, J., and M. Zeckauskas, "A One-way Active Measurement Protocol (OWAMP)", RFC 4656, September 2006.
11. Informative References ✨
[Bel02]J. Bellardo and S. Savage, "Measuring Packet Reordering," Proceedings of the ACM SIGCOMM Internet Measurement Workshop 2002, November 6-8, Marseille, France.[Ben99]J.C.R. Bennett, C. Partridge, and N. Shectman, "Packet Reordering is Not Pathological Network Behavior," IEEE/ACM Transactions on Networking, vol. 7, no. 6, pp. 789-798, December 1999.[Cia00]L. Ciavattone and A. Morton, "Out-of-Sequence Packet Parameter Definition (for Y.1540)", Contribution number T1A1.3/2000-047, October 30, 2000,http://home.comcast.net/~acmacm/IDcheck/0A130470.doc.[Cia03]L. Ciavattone, A. Morton, and G. Ramachandran, "Standardized Active Measurements on a Tier 1 IP Backbone," IEEE Communications Mag., pp. 90-97, June 2003.[I.356]ITU-T Recommendation I.356, "B-ISDN ATM layer cell transfer performance", March 2000.[Jai02]S. Jaiswal et al., "Measurement and Classification of Out-of-Sequence Packets in a Tier-1 IP Backbone," Proceedings of the ACM SIGCOMM Internet Measurement Workshop 2002, November 6-8, Marseille, France.[Lou01]D. Loguinov and H. Radha, "Measurement Study of Low-bitrate Internet Video Streaming", Proceedings of the ACM SIGCOMM Internet Measurement Workshop 2001 November 1-2, 2001, San Francisco, USA.[Mat03]M. Mathis, J. Heffner, and R. Reddy, "Web100: Extended TCP Instrumentation for Research, Education and Diagnosis", ACM Computer Communications Review, Vol 33, Num 3, July 2003,http://www.web100.org/docs/mathis03web100.pdf.[Pax98]V. Paxson, "Measurements and Analysis of End-to-End Internet Dynamics," Ph.D. dissertation, U.C. Berkeley, 1997,ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz.[RFC793]Postel, J., "Transmission Control Protocol", STD 7, RFC 793, September 1981.[RFC1323]Jacobson, V., Braden, R., and D. Borman, "TCP Extensions for High Performance", RFC 1323, May 1992.[RFC2581]Allman, M., Paxson, V., and W. Stevens, "TCP Congestion Control", RFC 2581, April 1999.[RFC2679]Almes, G., Kalidindi, S., and M. Zekauskas, "A One-way Delay Metric for IPPM", RFC 2679, September 1999.[RFC2680]Almes, G., Kalidindi, S., and M. Zekauskas, "A One-way Packet Loss Metric for IPPM", RFC 2680, September 1999.[RFC2960]Stewart, R., Xie, Q., Morneault, K., Sharp, C., Schwarzbauer, H., Taylor, T., Rytina, I., Kalla, M., Zhang, L., and V. Paxson, "Stream Control Transmission Protocol", RFC 2960, October 2000.[RFC3393]Demichelis, C. and P. Chimento, "IP Packet Delay Variation Metric for IP Performance Metrics (IPPM)", RFC 3393, November 2002.[RFC4340]Kohler, E., Handley, M., and S. Floyd, "Datagram Congestion Control Protocol (DCCP)", RFC 4340, March 2006.[RFC4341]Floyd, S. and E. Kohler, "Profile for Datagram Congestion Control Protocol (DCCP) Congestion Control ID 2: TCP-like Congestion Control", RFC 4341, March 2006.[TBABAJ02]T. Banka, A. Bare, A. P. Jayasumana, "Metrics for Degree of Reordering in Packet Sequences", Proc. 27th IEEE Conference on Local Computer Networks, Tampa, FL, Nov. 2002.[Y.1540]ITU-T Recommendation Y.1540, "Internet protocol data communication service - IP packet transfer and availability performance parameters", December 2002.
12. Acknowledgements 🫶
The authors would like to acknowledge many helpful discussions with Matt Zekauskas, Jon Bennett (who authored the sections on Reordering-Free Runs), and Matt Mathis. We thank David Newman, Henk Uijterwaal, Mark Allman, Vern Paxson, and Phil Chimento for their reviews and suggestions, and Michal Przybylski for sharing implementation experiences with us on the ippm-list. Anura Jayasumana and Nischal Piratla brought in recent work-in-progress [TBABAJ02]. We gratefully acknowledge the foundation laid by the authors of the IP performance framework [RFC2330] 💅✨
Appendix A. Example Implementations in C (Informative) 💻✨
okay bestie, two example C implementations of the reordering definitions are next, and they're giving pure main character energy 💅
#include <stdio.h>
#define MAXN 100
#define min(a, b) ((a) < (b)? (a): (b))
#define loop(x) ((x) >= 0? x: x + MAXN)
/*
* Read new sequence number and return it. Return a sentinel value
* of EOF (at least once) when there are no more sequence numbers.
* In this example, the sequence numbers come from stdin;
* in an actual test, they would come from the network.
*
*/
int
read_sequence_number()
{
int res, rc;
rc = scanf("%d\n", &res);
if (rc == 1) return res;
else return EOF;
}
int
main()
{
int m[MAXN]; /* We have m[j-1] == number of
* j-reordered packets. */
int ring[MAXN]; /* Last sequence numbers seen. */
int r = 0; /* Ring pointer for next write. */
int l = 0; /* Number of sequence numbers read. */
int s; /* Last sequence number read. */
int j;
for (j = 0; j < MAXN; j++) m[j] = 0;
for (;(s = read_sequence_number())!= EOF;l++,r=(r+1)%MAXN) {
for (j=0; j<min(l, MAXN)&&s<ring[loop(r-j-1)];j++) m[j]++;
ring[r] = s;
}
for (j = 0; j < MAXN && m[j]; j++)
printf("%d-reordering = %f%%\n", j+1, 100.0*m[j]/(l-j-1));
if (j == 0) printf("no reordering\n");
else if (j < MAXN) printf("no %d-reordering\n", j+1);
else printf("only up to %d-reordering is handled\n", MAXN);
exit(0);
}Example 2 is the singleton and n-reordering comparison, and it comes with a little author credit and notes 🫶
/* Example 2 singleton and n-reordering comparison =======
Author: Jerry Perser 7-2002 (mod by acm 12-2004)
Compile: $ gcc -o jpboth file.c
Usage: $ jpboth 1 2 3 7 8 4 5 6 (pkt sequence given on cmdline)
Note to cut/pasters: line 59 may need repair
*/
#include <stdio.h>
#define MAXN 100
#define min(a, b) ((a) < (b)? (a): (b))
#define loop(x) ((x) >= 0? x: x + MAXN)
/* Global counters */
int receive_packets=0; /* number of received */
int reorder_packets_Al=0; /* num reordered pkts (singleton) */
int reorder_packets_Stas=0; /* num reordered pkts(n-reordering)*/
/* function to test if current packet has been reordered
* returns 0 = not reordered
* 1 = reordered
*/
int testorder1(int seqnum) // Al
{
static int NextExp = 1;
int iReturn = 0;
if (seqnum >= NextExp) {
NextExp = seqnum+1;
} else {
iReturn = 1;
}
return iReturn;
}
int testorder2(int seqnum) // Stanislav
{
static int ring[MAXN]; /* Last sequence numbers seen. */
static int r = 0; /* Ring pointer for next write */
int l = 0; /* Number of sequence numbers read. */
int j;
int iReturn = 0;
l++;
r = (r+1) % MAXN;
for (j=0; j<min(l, MAXN) && seqnum<ring[loop(r-j-1)]; j++)
iReturn = 1;
ring[r] = seqnum;
return iReturn;
}
int main(int argc, char *argv[])
{
int i, packet;
for (i=1; i< argc; i++) {
receive_packets++;
packet = atoi(argv[i]);
reorder_packets_Al += testorder1(packet); // singleton
reorder_packets_Stas += testorder2(packet); //n-reord.
}
printf("Received packets = %d, Singleton Reordered = %d, n-
reordered = %d\n", receive_packets, reorder_packets_Al,
reorder_packets_Stas );
exit(0);
}Reference 📚
ISO/IEC 9899:1999 (E), as amended by ISO/IEC 9899:1999/Cor.1:2001 (E). Also published as:
The C Standard: Incorporating Technical Corrigendum 1, British Standards Institute, ISBN: 0-470-84573-2, Hardcover, 558 pages, September 2003.
Appendix B. Fragment Order Evaluation (Informative) 🧩
okay so Section 3 said fragment reassembly is assumed to happen before we judge order, but similar procedures could work before reassembly too 🦋 this appendix gives the definitions and procedures for spotting reordering in a packet stream that includes fragmentation, and it's kind of iconic ngl ✨
B.1. Metric Name
The Metric keeps the same name, Type-P-Reordered, but it needs some extra parameters 🎀
Also, this appendix assumes the device that splits a packet into fragments sends them in ascending fragment offset order. Early Linux sent fragments in reverse order, so it's worth checking for that possibility 👀
B.2. Additional Metric Parameters
MoreFrag, the state of the More Fragments Flag in the IP header.FragOffset, the offset from the beginning of a fragmented packet, in 8 octet units (also from the IP header).FragSeq#, the sequence number from the IP header of a fragmented packet currently under evaluation for reordering. When set to zero, fragment evaluation is not in progress.NextExpFrag, the next expected fragment offset at the destination, in 8 octet units. Set to zero when fragment evaluation is not in progress.
The packet sequence number, s, is assumed to be the same as the IP header sequence number. Also, the value of NextExp does not change with the in-order arrival of fragments. NextExp only gets updated when a last fragment or a complete packet arrives 💖
Packets with missing fragments MUST be declared lost, and the Reordering status of any fragments that do arrive MUST be excluded from sample metrics. This one is important bestie, don't skip it 🚨
B.3. Definition
The value of Type-P-Reordered is typically false (the packet is in-order) when:
- the sequence number
s >= NextExp, AND - the fragment offset
FragOffset >= NextExpFrag
However, it's more efficient to define the reordered conditions exactly and set Type-P-Reordered to False otherwise 🌸
The value of Type-P-Reordered is defined as True (the packet is reordered) under the conditions below. In these cases, the NextExp value does not change 🙈
Case 1: if s < NextExp
Case 2: if s < FragSeq#
Case 3: if s >= NextExp AND s = FragSeq# AND FragOffset < NextExpFrag
The definition can also be shown in pseudo-code. Here's a version, and some simplification may be possible. Housekeeping for the new parameters will be challenging 🥲
NextExp=0;
NextExpFrag=0;
FragSeq#=0;
while(packets arrive with s, MoreFrag, FragOffset)
{
if (s>=NextExp AND MoreFrag==0 AND s>=FragSeq#){
/* a normal packet or last frag of an in-order packet arrived */
NextExp = s+1;
FragSeq# = 0;
NextExpFrag = 0;
Reordering = False;
}
if (s>=NextExp AND MoreFrag==1 AND s>FragSeq#>=0){
/* a fragment of a new packet arrived, possibly with a
higher sequence number than the current fragmented packet */
FragSeq# = s;
NextExpFrag = FragOffset+1;
Reordering = False;
}
if (s>=NextExp AND MoreFrag==1 AND s==FragSeq#){
/* a fragment of the "current packet s" arrived */
if (FragOffset >= NextExpFrag){
NextExpFrag = FragOffset+1;
Reordering = False;
}
else{
Reordering = True; /* fragment reordered */
}
}
if (s>=NextExp AND MoreFrag==1 AND s < FragSeq#){
/* case where a late fragment arrived,
for illustration only, redundant with else below */
Reordering = True;
}
else { /* when s < NextExp, or MoreFrag==0 AND s < FragSeq# */
Reordering = True;
}
}A working version of the code would also include a check to make sure all fragments of a packet arrive before the Reordered status gets used further, such as in sample metrics 🔍
B.4. Discussion: Notes on Sample Metrics When Evaluating Fragments
All fragments with the same source sequence number are assigned the same source time 🕰️
Evaluation with byte stream numbering may be simplified if the fragment offset is simply added to the SourceByte of the first packet (the one with fragment offset = 0), keeping the 8 octet units of the offset in mind 🍓
Appendix C. Disclaimer and License 📜
Regarding this entire document or any portion of it (including the pseudo-code and C code), the authors make no guarantees and are not responsible for any damage resulting from its use. The authors grant irrevocable permission to anyone to use, modify, and distribute it in any way that does not diminish the rights of anyone else to use, modify, and distribute it, provided that redistributed derivative works do not contain misleading author or version information. Derivative works need not be licensed under similar terms 🫶
Authors' Addresses 🧚
Here's where you can find the authors, all six of them, and yes the phone numbers are real and they're all in the original 💜
Al Morton
AT&T Labs
Room D3 - 3C06
200 Laurel Ave. South
Middletown, NJ 07748 USA
Phone +1 732 420 1571
EMail: acmorton@att.com
Len Ciavattone
AT&T Labs
Room A2 - 4G06
200 Laurel Ave. South
Middletown, NJ 07748 USA
Phone +1 732 420 1239
EMail: lencia@att.com
Gomathi Ramachandran
AT&T Labs
Room C4 - 3D22
200 Laurel Ave. South
Middletown, NJ 07748 USA
Phone +1 732 420 2353
EMail: gomathi@att.com
Stanislav Shalunov
Internet2
1000 Oakbrook DR STE 300
Ann Arbor, MI 48104
Phone: +1 734 995 7060
EMail: shalunov@internet2.edu
Jerry Perser
Veriwave
8770 SW Nimbus Ave.
Suite B
Beaverton, OR 97008 USA
Phone: +1 818 338 4112
EMail: jperser@veriwave.comFull Copyright Statement ©️
Copyright (C) The IETF Trust (2006).
This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights.
This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST, AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property 🔒
The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document, or the extent to which any license under such rights might or might not be available. It also doesn't represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification, can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org 📬
okay bestie, this is the final little note at the end 🫶 Funding for the RFC Editor function is currently being covered by the Internet Society 💖 so the people keeping the whole RFC series running get their support from them right now ✨ that's literally it, periodt 💅
📦 where this page comes from
- ietf: rfc4737 2006-11
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms