RFC 5236
Improved Packet Reordering Metrics
RFC 5236: Improved Packet Reordering Metrics 🦋
Okay bestie, the title block first! 💖 This is an RFC from the Network Working Group, and it's numbered RFC 5236. It was written by A. Jayasumana (Colorado State University), N. Piratla (Deutsche Telekom Labs), T. Banka (Colorado State University), A. Bare, and R. Whitner (Agilent Technologies, Inc.). It's dated June 2008 and its category is Informational 🌸 The header doesn't list anything it obsoletes or updates, so it stands on its own. ✨
The whole doc is about making packet reordering easier to measure, so let's get into it. 💅
Table of Contents
1. Introduction and Motivation .....................................3
2. Attributes of Packet Reordering Metrics .........................4
3. Reorder Density and Reorder Buffer-Occupancy Density ............7
3.1. Receive Index (RI) .........................................8
3.2. Out-of-Order Packet ........................................9
3.3. Displacement (D) ...........................................9
3.4. Displacement Threshold (DT) ................................9
3.5. Displacement Frequency (FD) ...............................10
3.6. Reorder Density (RD) ......................................10
3.7. Expected Packet (E) .......................................10
3.8. Buffer Occupancy (B) ......................................10
3.9. Buffer-Occupancy Threshold (BT) ...........................11
3.10. Buffer-Occupancy Frequency (FB) ..........................11
3.11. Reorder Buffer-Occupancy Density (RBD) ...................11
4. Representation of Packet Reordering and Reorder Density ........11
5. Selection of DT ................................................12
6. Detection of Lost and Duplicate Packets ........................13
7. Algorithms to Evaluate RD and RBD ..............................14
7.1. Algorithm for RD ..........................................14
7.2. Algorithm for RBD .........................................16
8. Examples .......................................................17
9. Characteristics Derivable from RD and RBD ......................21
10. Comparison with Other Metrics .................................22
11. Security Considerations .......................................22
12. References ....................................................22
12.1. Normative References .....................................22
12.2. Informative References ...................................22
13. Contributors ..................................................24Status of This Memo
This memo provides information for the Internet community. 🧚 It does not specify an Internet standard of any kind. Distribution of this memo is unlimited. 🌈
IESG Note
Okay, this part is important, so read it twice! 🙈 The content of this RFC was once considered by the IETF, so it may look a lot like a current IETF work in progress or a published IETF work. The IETF standard for reordering metrics is RFC 4737. The metrics in this document were not adopted for inclusion in RFC 4737. This RFC is not a candidate for any level of Internet Standard. 🚫
The IETF disclaims any knowledge of the fitness of this RFC for any purpose. It specifically notes that the decision to publish was not based on IETF review for things like security, congestion control, or inappropriate interaction with deployed protocols. The RFC Editor chose to publish this document at its discretion. Readers should exercise caution when evaluating its value for implementation and deployment. See RFC 3932 for more information. 💀
Abstract
The main character of this doc is two improved metrics for packet reordering! ✨ They are Reorder Density (RD) and Reorder Buffer-occupancy Density (RBD) 👑
A threshold is used to clearly define when a packet is considered lost. 🦋 It keeps computational complexity at O(N), and it keeps the memory needed for evaluation independent of N, where N is the length of the packet sequence. 🫶 RD is the comprehensive one that captures the characteristics of reordering. RBD looks at the sequences from the point of view of recovery from reordering. 🌸
These metrics are simple to compute, yet they still give a full picture of packet reordering. 🍓 The measures are robust and orthogonal to packet loss and duplication. It's giving clean and independent! 💅
1. Introduction and Motivation 🌷
Packet reordering is a phenomenon that happens in Internet Protocol (IP) networks. 🌊 Major causes include, but are not limited to, packet striping at layers 2 and 3 [Ben99] [Jai03], priority scheduling (for example, Diffserv), and route fluttering [Pax97] [Boh03]. Reordering leads to degradation of the performance of many applications [Ben99] [Bla02] [Lao02]. 😭 Increased link speeds [Bar04], increased parallelism within routers and switches, Quality-of-Service (QoS) support, and load balancing among links all point to increased packet reordering in future networks. 🚀
Effective metrics for reordering are required to measure and quantify reordering. ✨ A good metric, or a set of metrics, that captures the nature of reordering can be expected to give insight into the reordering phenomenon in networks. 🔥 It may be possible to use such metrics to predict the effects of reordering on applications that are sensitive to it, and perhaps even to compensate for reordering. 🧁 A metric for reordered packets may also help evaluate network protocols and implementations with respect to their impact on packet reordering. 🎀
The percentage of out-of-order packets is often used as a metric for characterizing reordering. 🙃 However, this metric is vague and lacking in detail. Further, there is no uniform definition for the degree of reordering of an arrived packet [Ban02] [Pi05a]. For example, consider the two packet sequences (1, 3, 4, 2, 5) and (1, 4, 3, 2, 5). It is possible to interpret the reordering of packets in these sequences differently. For example:
- (i) Packets 2, 3, and 4 are out of order in both cases.
- (ii) Only packet 2 is out of order in the first sequence, while packets 2 and 3 are out of order in the second.
- (iii) Packets 3 and 4 are out of order in both the sequences.
- (iv) Packets 2, 3, and 4 are out of order in the first sequence, while packets 4 and 2 are out of order in the second sequence.
Ngl, this is why the percentage metric is so messy! 😵💫 In essence, the percentage of out-of-order packets as a metric of reordering is subject to interpretation. It can't capture the reordering unambiguously and therefore can't capture it accurately either. 💔
Other metrics try to fix this ambiguity by defining only the late packets, or only the early packets, as reordered. 🕰️ However, measuring reordering based only on late packets, or only on early packets, is not always effective. Consider the sequence (1, 20, 2, 3, ..., 19, 21, 22, ...). The only anomaly is that packet 20 is delivered immediately after packet 1. 🤏 A metric based only on lateness will show a high degree of reordering, even though in this example it's just one packet arriving ahead of the others. Similarly, a metric based only on earliness doesn't accurately capture reordering caused by a late-arriving packet. 🙅♀️
A complete reorder metric must account for both earliness and lateness, and it must be able to tell the two apart. 🧠 Not capturing both is what stops a metric from being useful for estimating end-to-end reordering based on reordering in constituent subnets. 🔗
The sensitivity to packet reordering can vary a lot from one application to another. 🎭 Take the packet sequence (1, 3, 4, 2, 5) again. If there are buffers available to store packets 3 and 4 while waiting for packet 2, an application can recover from the reordering. 🛟 However, with certain real-time applications, the out-of-order arrival of packet 2 may make it useless. 🥀 One can argue that a good packet reordering measurement scheme should capture application-specific effects. But a counter argument is that packet reordering should be measured strictly with respect to the order of delivery, independent of the application. ⚖️
Many different packet reordering metrics have been suggested. 📚 For example, the standards-track document RFC 4737 [RFC4737] defines 11 metrics for packet reordering, including lateness-based percentage metrics, reordering extent metrics, and N-reordering. 🧮
Section 2 of this document discusses the desirable attributes of any packet reordering metric. 📝 Section 3 introduces two additional packet reorder metrics: Reorder Density (RD) and Reorder Buffer-occupancy Density (RBD), which the authors claim are superior to the others [Pi07]. 👑 In particular, RD possesses all the desirable attributes, while other metrics fall significantly short in several of them. 💅 RBD is unique in that it measures reordering in terms of the system resources needed for recovery from packet reordering. 🧺 Both RD and RBD have a computational complexity of O(N), where N is the length of the packet sequence, so they can be used for real-time online monitoring. ⏱️ 🌈
Part 1 of 6 is done, bestie! 🎀
2. Attributes of Packet Reordering Metrics ✨
okay so the very first and most important thing a packet reordering metric has to do is capture how much reordering is happening in a sequence of packets 💅 A number that changes when packets get shuffled doesn't automatically make it a good metric, bestie. In [Ben99], the authors wrote down the features a reordering metric should have. These are the foremost requirements from above:
- simplicity
- low sensitivity to packet loss
- ability to combine reorder measures from two networks
- minimal value for in-order data
- independence of data size
We'll explain these in detail below, along with some extra features 🎀 The ability to combine reorder measures from two networks got added to broaden applicability, and data size independence gets discussed under evaluation complexity. Data size independence could also refer to the final measure, like percentage reordering or some normalized representation, so keep that in mind 🦋
a) Simplicity
An ideal metric is simple to understand and evaluate, and yet still informative, meaning it gives you a complete picture of reordering 🌸 Percentage of packets reordered is the simplest singleton metric. But its definition is ambiguous (we talked about that earlier), and it doesn't tell you the extent of reordering, so it's less informative. On the flip side, tracking the displacement of every single packet without compressing the data holds all the info about reordering, but it's not simple to evaluate or use 😭
A simpler metric might be the better pick in some cases even if it doesn't capture reordering completely. Other cases might need a more complex but complete metric 🧚
Here's the balancing act: lateness-based metrics only count the late packets as reordered, and earliness-based metrics only count the early packets. But a metric based purely on earliness or purely on lateness only captures part of what's going on. A metric that captures both early and late arrivals gives you the complete picture of reordering in a sequence 👑
b) Low Sensitivity to Packet Loss and Duplication
A reorder metric should only treat an out-of-order packet as reordered 🔥 If a packet gets lost in transit, that should not make the packets following it, which arrive in order, get classified as out of order. Take the sequence (1, 3, 4, 5, 6). If packet 2 was lost, the sequence should not be considered to contain any out-of-order packets 🙈
Duplicates are the same deal. If multiple copies of a packet get delivered, that must not make a packet count as out of order, as long as one copy arrives in the proper position. For example, the sequence (1, 2, 3, 2, 4, 5) has no reordering at all 💖
If you want to track losses and duplicates, use metrics that are built for that, like percentage of lost packets and percentage of duplicate packets 🍓
c) Low Evaluation Complexity
Memory and time complexity matter a LOT for implementation and real-time measurements 💜 Spatial (memory) complexity is about how many buffers the whole measurement process needs. Time (computation) complexity is about how many computation steps it takes to work out how much reordering is in a sequence ✨
On-the-fly evaluation of the metric for large streams of packets needs computational complexity of O(N), where N is the number of received packets used for the reordering measure. That's the magic bit, because it means the metric can be updated in constant-time as each packet arrives 🦋
Without a threshold that defines losses, or a limit on how many sequence numbers to buffer for duplicate detection, the worst-case complexity of loss and duplication detection will grow with N 💀 How fast it grows depends on things like the value of N and how the duplicate detection scheme is implemented.
d) Robustness
Reorder measurements should be robust against different network phenomena and peculiarities, in the measurement or in the sequences themselves 🛡️ That includes things like a very late arrival of a duplicate packet, or even a rogue packet caused by an error or by sequence number wraparound 😱 The impact of an event tied to one packet or a small number of packets should be proportional in the reorder measure, not a huge overreaction 🌈
Check this out. In the arrival sequence (1, 5430, 2, 3, 4, 5, ...), packet 5430 looks super early. It could be due to a sequence rollover in test streams, or it could be for some unknown reason 🤷♀️
e) Broad Applicability
The IP performance metrics framework [RFC2330] says: "The metrics must aid users and providers in understanding the performance they experience or provide". Iconic energy, honestly 👑
A reorder metric should be useful for a bunch of different purposes, not just be a value (or set of values) that wiggles as packets get reordered in a stream 💅 An application or a transport protocol implementation can use the reordering info to allocate resources for recovering from reordering. A metric might also be useful for TCP flow control, for allocating buffer resources for recovery from reordering, and/or for network diagnosis 🔥
Being able to combine the reorder metrics of the constituent subnets to measure end-to-end reordering would be an extremely useful property ✨ Without it, no amount of individual network measurements would help predict end-to-end reordering, unless you measured reordering for the exact pair of endpoints you care about 😭
Providing different types of info based on monitoring or diagnostic needs also broadens the metric's applicability 🌸 Examples of useful reordering info include the percentage of reordered packets that caused fast retransmissions in TCP, or the percentage of utilization of the reorder recovery buffer 🧚
3. Reorder Density and Reorder Buffer-Occupancy Density 🎀
In this memo, we define two discrete density functions: Reorder Density (RD) and Reorder Buffer-occupancy Density (RBD). Together they capture the nature of reordering in a packet stream 💖 You can use them on their own or together to characterize reordering. There are also algorithms for evaluating these metrics in real time on an incoming packet stream 🦋
RD is the distribution of displacements of packets from their original positions, normalized by the number of packets 🌈 An early packet has a negative displacement, and a late packet has a positive displacement. A threshold on displacement keeps the computation within bounds. The threshold you pick depends on what you're measuring and your constraints, like whether duplicate packets get counted when evaluating these displacements (more on that in Section 5) 🍓
RD has been shown to capture the nature and properties of reordering comprehensively in [Pi05a], [Pi05b], [Pi05c], and [Pi07] 👑 The RD observed at the output port of a subnet, when the input is an in-order packet stream, can be seen as a "reorder response" of a network. It's kind of like the "system response" or "impulse response" from traditional system theory 🧠 Under stationary conditions, RD is the probability density of the packet displacement for a subnet 💅 RD measured on individual subnets can be combined using the convolution operation to predict the end-to-end reorder characteristics of a network formed by a cascade of subnets, under a fairly broad set of conditions [Pi05b] ✨ RD also shows real promise as a tool for analytical modeling of reordering, as shown with a load-balancing scenario in [Pi06] 🔥 And using a threshold to define when a packet counts as lost makes the metric robust, efficient, and adaptable for different networks and stream characteristics 🫶
RBD is the normalized histogram of the occupancy of a hypothetical buffer that would allow recovery from out-of-order delivery of packets 🌸 If an arriving packet is early, it gets added to that hypothetical buffer until it can be released in order [Ban02]. The occupancy of this buffer after each arrival is the measure of reordering 💜 A threshold is used to declare a packet lost, which keeps the computation complexity within bounds. You can pick that threshold based on application requirements, like in real-time apps where a late arrival makes a packet useless ⏰ In [Ban02], this metric was called RD, and buffer occupancy was known as displacement 🙈
RD and RBD are simple, yet useful, metrics for measuring and evaluating reordering ✨ They're robust against lots of peculiarities like the ones we talked about before, and they have a computational complexity of O(N), where N is the received sequence size 🦋 RD is orthogonal to loss and duplication, whereas RBD is orthogonal to duplication only 💅
A detailed comparison of these and other proposed reordering metrics is in [Pi07] 🎀
The terms below are used to formally define RD, RBD, and the measurement algorithms. The wraparound of sequence numbers isn't addressed explicitly in this document, but with modulo-N arithmetic, all the claims made here still hold in the presence of wraparound 🧚
3.1. Receive Index (RI)
Consider a sequence of packets (1, 2, ..., N) transmitted over a network 🌈 A receive index RI (1, 2, ...) is a value assigned to a packet as it arrives at its destination, based on the order of arrival 💖 A receive index is not assigned to duplicate packets, and the receive index value skips the value corresponding to a lost packet. (Detecting loss and duplication for this purpose is covered in Section 6.) If there's no reordering, the sequence number of the packet and its receive index are the same for each packet 🍓
RI is used to compute the earliness and lateness of an arriving packet ✨ Here are two examples of received sequences with receive index values, for a sequence of 5 packets (1, 2, 3, 4, 5) arriving out of order:
Example 1:
Arrived sequence: 2 1 4 5 3
receive index: 1 2 3 4 5
Example 2:
Arrived sequence: 1 4 3 5 3
receive index: 1 3 4 5 -In Example 1, there's no loss or duplication 🦋 In Example 2, the packet with sequence number 2 is lost, so 2 doesn't get assigned an RI 💀 Packet 3 is duplicated, so the second copy doesn't get an RI either 🙈
3.2. Out-of-Order Packet
When a packet's sequence number isn't equal to the RI assigned to it, that packet is considered to be an out-of-order packet 🔥 Duplicates that don't have an RI defined get ignored 💅
3.3. Displacement (D) ✨
okay so the displacement of a packet is the difference between its RI and its sequence number. For packet i, that's RI[i] - i 💅 A negative displacement means the packet arrived early, and a positive one means it arrived late. Example 3 shows an arrived sequence with the displacement of each packet 🎀
Example 3:
Arrived sequence: 1 4 3 5 3 8 7 6
receive index: 1 3 4 5 - 6 7 8
Displacement: 0 -1 1 0 - -2 0 23.4. Displacement Threshold (DT) 🌸
the displacement threshold is a cutoff on displacement that lets the metric decide when a packet counts as lost or duplicate 🫶 deciding "lost" is tricky, bestie, because you can never be 100% sure. a packet could show up after some super long delay 😭 so in practice, a packet gets labeled lost if it hasn't shown up within an administratively defined displacement threshold, DT.
duplicates work the same way. in theory you'd have to track every packet that has arrived (or is missing) forever 💀 but practically, the missing packets inside a window of sequence numbers are enough. so DT is the practical tool for calling a packet lost or duplicated. it makes the metric more robust ✨, keeps the computational complexity for long sequences within O(N), and keeps storage requirements independent of N.
if DT is too small, reordered packets might get wrongly labeled as lost 🙈 a big DT, on the other hand, means more memory to track sequence numbers and more time to evaluate the metric. it's also possible to use two different thresholds for the two cases. Section 5 has more on picking DT.
3.5. Displacement Frequency (FD) 🦋
Displacement Frequency FD[k] is the number of arrived packets with a displacement of k, where k goes from -DT to DT 🍓
3.6. Reorder Density (RD) 🔥
RD is the distribution of the Displacement Frequencies FD[k], normalized with respect to N'. N' is the length of the received sequence, skipping lost and duplicate packets. Here, N' = sum(FD[k]) for k in [-DT, DT] ✨
3.7. Expected Packet (E) 👑
a packet with sequence number E is expected if E is the biggest number where every packet with a lower sequence number has either already arrived or been determined to be lost 🧚
3.8. Buffer Occupancy (B) 🌈
okay this one is so good 😭 an arrived packet with a sequence number higher than an expected packet is treated as being stored in a hypothetical buffer, long enough to recover from the reordering ✨ at any arrival moment, the buffer occupancy equals the number of out-of-order packets in the buffer, including the packet that just arrived. each packet gets one buffer location, though it's possible to stretch the concept so it counts bytes instead.
for example, take the sequence (1, 2, 4, 5, 3) with expected order (1, 2, 3, 4, 5). when packet 4 shows up, the occupancy is 1, because 4 came early 💅 when packet 5 arrives, the occupancy becomes 2. then packet 3 arrives, the reordering gets recovered, and the occupancy drops right back to zero 🎀
3.9. Buffer-Occupancy Threshold (BT) 🦋
the buffer-occupancy threshold is a cap on the maximum size of that hypothetical buffer used for recovering from reordering. just like DT for RD, BT is what decides loss and duplication when computing the Reorder Buffer-occupancy Density (RBD) (see Section 3.11). BT adds robustness and limits how much work RBD has to do 💖
3.10. Buffer-Occupancy Frequency (FB) 🍓
every time a packet arrives, the buffer occupancy could be any value k from 0 up to BT 🫶 the buffer occupancy frequency FB[k] counts the arrival instances after which the occupancy is exactly k.
3.11. Reorder Buffer-Occupancy Density (RBD) 💜
Reorder buffer-occupancy density is the buffer occupancy frequencies divided by the total number of non-duplicate packets. so RBD[k] = FB[k]/N', where N' is the length of the received sequence, skipping the excessively delayed (deemed lost) and duplicate packets 🔥 N' also works out to sum(FB[k]) for all k in [0, BT].
4. Representation of Packet Reordering and Reorder Density 🧚
okay picture a sequence of packets (1, 2, ..., N) 🌸 the RI given to packet m is "the sequence number m plus an offset dm," which looks like this:
RI = m + dm; D = dma reorder event of packet m is written as r(m, dm). when dm isn't zero, a reorder event has happened 👑 a packet is late if dm > 0 and early if dm < 0. so all the reordering in a packet sequence is fully captured by the union of reorder events, R, which is called the reorder set 💅
R = {r(m,dm)| dm not equal to 0 for all m}if a sequence has no reordering at all, then R is the null set ✨
Examples 4 and 5 show the reorder set in action 🎀
Example 4. No losses or duplicates
Arrived Sequence 1 2 3 5 4 6
receive index (RI) 1 2 3 4 5 6
Displacement (D) 0 0 0 -1 1 0
R = {(4,1), (5,-1)}Example 5. Packet 4 is lost and 2 is duplicated
Arrived Sequence 1 2 5 3 6 2
receive index (RI) 1 2 3 5 6 -
Displacement (D) 0 0 -2 2 0 -
R = {(3, 2), (5, -2)}RD is the discrete density of how frequent packets are with respect to their displacements, meaning how far they've moved late or early from their original spot 🦋 let S[k] be the set of reorder events in R with displacement equal to k:
S[k]= {r(m, dm)| dm = k}let |S[k]| be the size (cardinality) of S[k]. then RD[k] is |S[k]| normalized by the total number of received packets (N'). N' doesn't count duplicate or lost packets 💖
RD[k] = |S[k]| / N' for k not equal to zeroRD[0] covers the packets where RI is the same as the sequence number:
RD[0] = 1 - sum(|S[k]| / N')like we said before, FD[k] is the thing that keeps track of |S[k]| 🌈
5. Selection of DT 🔥
okay so putting a threshold on lost and duplicate packets might sound like it adds error to the reorder metrics, but in practice it usually doesn't 💅 applications, protocols, and the network itself all run under finite resource limits, and past certain points, picking a bigger value just stops mattering 😭 if an application's behavior lets you define a DT, then using it in the reorder metric doesn't invalidate or limit the metric. increasing DT won't give you any extra benefit ✨ for TCP, the maximum transmit and receive window sizes naturally cap how useful DT can be 🎀 and sequence number wraparound can be a helpful upper bound for DT in some cases.
if there are no operational constraints like those, or if you just want the complete picture of reordering, DT can be as large as you need 👑 if DT equals the length of the packet sequence (the worst case), you get the complete picture of reordering 🧚 any metric that doesn't use a threshold to declare a packet lost is implicitly making one of two assumptions: a) a missing packet isn't considered lost until the end of the sequence, or b) the packet is considered lost until it shows up. the first one matches setting DT to the sequence length, and the second one leads to lots of complexity and robustness problems 💀
6. Detection of Lost and Duplicate Packets 💖
in RD, a packet counts as lost if it's late beyond DT 🫶 a non-duplicate arriving packet doesn't have a copy in the buffer, and its sequence number isn't less than (earlier than) E. in RBD, a packet counts as lost once the buffer fills up to its threshold BT. a packet counts as a duplicate when its sequence number is less than the expected packet, or when its sequence number is already in the buffer 🌸
here's the tricky bit 😭 since RI skips over the sequence number of a lost packet, you have to figure out how to assign RI to the packets that show up after it but before we know it's lost. this only comes up when reorder metrics are calculated in real time for an incoming sequence, not with offline computations. there are two ways to handle it:
- a) Go-back Method: RD is computed as packets arrive. when a packet is deemed lost, the RI values get corrected and the displacements get recomputed. the Go-back Method only kicks in when a packet is lost, and recomputing RD involves at most DT packets ✨
- b) Stay-back Method: RD evaluation lags behind the arriving packets, so the correct RI and E values can be assigned to each packet as it arrives 🎀 RI is assigned to a packet only once, and the value given is guaranteed to be correct. in the worst case, the computation lags the arriving packet by DT. the lag from the Stay-back Method only happens when a packet is missing 🦋
another thing to think about is how robust the metric is against the weird stuff that can happen in a sequence, as discussed in Section 2 🙈 take the arrival sequence (1, 5430, 2, 3, 4, 5, ...). with RD, DT keeps things proportional, because it limits the damage a rogue packet can do to the results ✨ in this example, when the displacement is bigger than DT, the rogue packet 5430 gets discarded. so the impact of the rogue packet is capped at DT packets, which puts a limit on how much error it can cause 💅 also, a threshold different from DT can serve the same purpose. for example, a pre-set threshold that limits how long a packet can sit in the buffer can make RBD robust against rogue packets 👑
7. Algorithms to Evaluate RD and RBD 💜
the algorithms for computing RD and RBD are below 🌈 they work for online computation of an incoming packet stream and always give you an up-to-date metric for the packets read so far ✨ to keep things simple, the sequence numbers are assumed to start at 1 and go up in steps of 1. only the Stay-back Method of loss detection is covered here, so the RD values lag by a maximum of DT 🎀 the algorithm for the Go-back Method is in [Bar04]. Perl scripts for these algorithms are posted in [Per04] 🫶
7.1. Algorithm for RD 💖
okay bestie, this is the RD algorithm, and it's giving full detective energy 🕵️♀️✨ you keep a sliding window of incoming sequence numbers, and you use a little buffer to hold the early arrivals until their turn comes up. Here are the variables first 🎀
Variables used:
-------------------------------------------------------------------
RI: receive index.
S: Arrival under consideration for lateness/earliness computation.
D: Lateness or earliness of the packet being processed: dm for m.
FD[-DT..DT]: Frequency of lateness and earliness.
window[1..DT+1]: List of incoming sequence numbers; FIFO buffer.
buffer[1..DT]: Array to hold sequence numbers of early arrivals.
window[] and buffer[] are empty at the beginning.
===================================================================And here's the algorithm itself, which I'm keeping exactly as written so nothing gets lost in translation 🫶
Step 1. Initialize:
Store first unique DT+1 sequence numbers in arriving order into
window; RI = 1;
Step 2. Repeat (until window is empty):
If (window or buffer contains sequence number RI)
{
Move sequence number out of window to S # window is FIFO
D = RI - S; # compute displacement
If (absolute(D) <= DT) # Apply threshold
{
FD[D]++; # Update frequency
If (buffer contains sequence number RI)
Delete RI from buffer;
If (D < 0) # Early Arrival
add S to empty slot in buffer;
RI++; # Update RI value
}
Else # Displacement beyond threshold.
{
Discard S;
# Note, an early arrival in window is moved to buffer if
# its displacement is less or equal to DT. Therefore, the
# contents in buffer will have only possible RIs. Thus,
# clearing an RI as it is consumed prevents memory leaks
# in buffer
}
# Get next incoming non-duplicate sequence number, if any.
newS = get_next_arrival(); # subroutine called*
if (newS != null)
{
add newS to window;
}
if (window is empty) go to step 3;
}
Else # RI not found. Get next RI value.
{
# Next RI is the minimum among window and buffer contents.
m = minimum (minimum (window), minimum (buffer));
If (RI < m)
RI = m;
Else
RI++;
}
Step 3. Normalize FD to get RD;
# Get a new sequence number from packet stream, if any
subroutine get_next_arrival()
{
do # get non-duplicate next arrival
{
newS = new sequence from arriving stream;
if (newS == null) # End of packet stream
return null;
} while (newS < RI or newS in buffer or newS in window);
return newS;
}The "Apply threshold" check is the bit to watch: anything whose displacement is beyond DT gets discarded, no exceptions 👀
7.2. Algorithm for RBD 🦋
okay now the RBD one, and honestly it's just as iconic 💅 this one tracks the next expected sequence number, how full the buffer is, and how often each occupancy level shows up. Variables first 🌸
Variables used:
---------------------------------------------------------------------
# E : Next expected sequence number.
# S : Sequence number of the packet just arrived.
# B : Current buffer occupancy.
# BT: Buffer Occupancy threshold.
# FB[i]: Frequency of buffer occupancy i (0 <= i <= BT).
# in_buffer(N) : True if the packet with sequence number N is
already stored in the buffer.
=====================================================================Now the steps, copied exactly so the logic stays perfect 🧚
1. Initialize E = 1, B = 0 and FB[i] = 0 for all values of i.
2. Do the following for each arrived packet.
If (in_buffer(S) || S < E) /*Do nothing*/;
/* Case a: S is a duplicate or excessively delayed packet.
Discard the packet.*/
Else
{
If (S == E)
/* Case b: Expected packet has arrived.*/
{
E = E + 1;
While (in_buffer(E))
{
B = B - 1; /* Free buffer occupied by E.*/
E = E + 1; /* Expect next packet.*/
}
FB[B] = FB[B] + 1; /*Update frequency for buffer
occupancy B.*/
} /* End of If (S == E)*/
ElseIf (S > E)
/* Case c: Arrived packet has a sequence number higher
than expected.*/
{
If (B < BT)
/* Store the arrived packet in a buffer.*/
B = B + 1;
Else
/* Expected packet is delayed beyond the BT.
Treat it as lost.*/
{
Repeat
{
E = E + 1;
}
Until (in_buffer(E) || E == S);
While (in_buffer(E) || E == S)
{
if (E != S) B = B - 1;
E = E + 1;
}
}
FB[B] = FB[B] + 1; /*Update frequency for buffer
occupancy B.*/
} /* End of ElseIf (S > E)*/
}
3. Normalize FB[i] to obtain RBD[i], for all values of i using
FB[i]
RBD[i] = ----------------------------------
Sum(FB[j] for 0 <= j <= BT)🫶 that's the whole RBD algorithm, and the last step is where all those counts become the final RBD values 💜
8. Examples 🎀
a. Scenario with no packet loss 🦋
okay so bestie, let's run the sequence (1, 4, 2, 5, 3, 6, 7, 8) with DT = BT = 4. 💖 Tables 1 and 2 show every computational step of the RD algorithm on this sequence, and it's so satisfying to watch the numbers fall into place 😭
------------------------------------------------------
Table 1: Late/Early-packet Frequency computation steps
------------------------------------------------------
S 1 4 2 5 3 6 7 8
RI 1 2 3 4 5 6 7 8
D 0 -2 1 -1 2 0 0 0
FD[D] 1 1 1 1 1 2 3 4
------------------------------------------------------
(S, RI,D and FD[D] as described in Section 7.1)
------------------------------------------------------The last row (FD[D]) is the current frequency of occurrence of the displacement D, so it's giving running tally 📊 For example, column 3 shows FD[1] = 1, and column 4 shows FD[-1] = 1. The final RD values are in Table 2 ✨
-------------------------------------------------
Table 2: Reorder Density (RD)
-------------------------------------------------
D -2 -1 0 1 2
FD[D] 1 1 4 1 1
RD[D] 0.125 0.125 0.5 0.125 0.125
-------------------------------------------------
(D,FD[D] and RD[D] as described in Section 7.1)
-------------------------------------------------Tables 3 and 4 do the same thing for RBD on this example, so you can compare the two side by side 🌸
------------------------------------------------------------
Table 3: Buffer occupancy frequencies (FB) computation steps
------------------------------------------------------------
S 1 4 2 5 3 6 7 8
E 1 2 2 3 3 6 7 8
B 0 1 1 2 0 0 0 0
FB[B] 1 1 2 1 2 3 4 5
------------------------------------------------------------
(E,S,B and FB[B] as described in Section 7.2)
------------------------------------------------------------
------------------------------------------------------------
Table 4: Reorder Buffer-occupancy Density
------------------------------------------------------------
B 0 1 2
FB[B] 5 2 1
RBD[B] 0.625 0.25 0.125
------------------------------------------------------------
(B,FB[B] and RBD[B] as discussed in Section 7.2)
------------------------------------------------------------Here are the graphs of the densities, bestie 🧚
^ ^
| |
| _
^ 0.5 _ ^ 0.625 | |
| | | | | |
| | | |
RD[D] | | RBD[B] | | - o.25
_ _ | | _ _ 0.125 | || | - 0.125
| || || || || | | || || |
--+--+--+--+--+--+--> ---+--+--+--
-2 -1 0 1 2 0 1 2
D --> B -->b. Scenario with packet loss 🫶
this one is the plot twist 😭 Consider a sequence of 6 packets (1, 2, 4, 5, 6, 7) with DT = BT = 3. Table 5 shows the RD computation steps on this sequence to get FD[D].
------------------------------------------------------
Table 5: Late/Early-packet Frequency computation steps
------------------------------------------------------
S 1 2 4 5 6 7
RI 1 2 4 5 6 7
D 0 0 0 0 0 0
FD[D] 1 2 3 4 5 6
------------------------------------------------------
(S,RI,D and FD[D] as described in Section 7.1)
------------------------------------------------------Table 6 shows the FB[B] for this same arrival sequence 💅
-------------------------------------------------
Table 6: Buffer occupancy computation steps
-------------------------------------------------
S 1 2 4 5 6 7
E 1 2 3 3 3 7
B 0 0 1 2 3 0
FB[B] 1 2 1 1 1 3
-------------------------------------------------
(E,S,B and FB[B] as described in Section 7.2)
-------------------------------------------------And here are the graphs of RD and RBD for the above sequence 🌈
^ ^
| |
1.0 _ |
^ | | ^ |
| | | | 0.5 _
| | | |
RD[D] | | RBD[B] | | _ _ _ 0.167
| | | || || || |
--+--+--+--> --+--+--+--+-->
-1 0 1 0 1 2 3
D --> B -->c. Scenario with duplicate packets 👑
last example, and it's a good one 🙈 Consider a sequence of 6 packets (1, 3, 2, 3, 4, 5) with DT = 2. Table 7 shows the RD computation steps on this sequence to get FD[D].
------------------------------------------------------
Table 7: Late/Early-packet Frequency computation steps
------------------------------------------------------
S 1 3 2 3 4 5
RI 1 2 3 - 4 5
D 0 -1 1 - 0 0
FD[D] 1 1 1 - 2 3
------------------------------------------------------
(S, RI,D and FD[D] as described in Section 7.1)
------------------------------------------------------Table 8 shows the FB[B] for this arrival sequence 🦋
------------------------------------------------------
Table 8: Buffer Occupancy Frequency computation steps
------------------------------------------------------
S 1 3 2 3 4 5
E 1 2 2 - 4 5
B 0 1 0 - 0 0
FB[B] 1 1 2 - 3 4
------------------------------------------------------
(E,S,B and FB[B] as described in Section 7.2)
------------------------------------------------------Graphs of RD and RBD for this sequence are below 🍓
^ ^
| |
^ | ^ 0.8 _
| 0.6 _ | | |
| | | |
RD[D] | | RBD[B] | |
0.2 _ | | _ 0.2 | | _ 0.2
| || || | | || |
--+--+--+--+--+--+--> ---+--+--+--
-2 -1 0 1 2 0 1 2
D --> B -->9. Characteristics Derivable from RD and RBD ✨
ngl, RD and RBD can give you more info depending on what you're building 💜 Say a node needs to allocate resources so it can recover from reordering. Then the mean and variance of buffer occupancy can be derived from RBD. For example, the mean occupancy looks like this:
Mean occupancy of recovery buffer = sum(i*RBD[i] for 0 <= i <= BT)RBD can be tweaked to count buffer occupancy in bytes instead of packets, which is useful when actual buffer space is what really matters 🧚 Another option is to use time to update the buffer occupancy, rather than updating it at every arrival instant.
From RD you can pull out the percentage of late (or early) packets, the mean displacement of packets, and the mean displacement of late (or early) packets [Ye06]. For instance, the fraction of packets that arrive after three or more of their successors (in transmission order) is given by Sum [RD[i] for 3<=i<=DT]. RD also lets you extract things like the entropy of the reordered sequence, which is basically a measure of disorder in the sequence [Ye06]. And since RD is a probability mass function, it's a handy tool for theoretical modeling and analysis of reordering, e.g., see [Pi06] 🌸
10. Comparison with Other Metrics 🔥
RD and RBD get compared to the other metrics of [RFC4737] in [Pi07] 💅
11. Security Considerations 💀
The security considerations listed in [RFC4737], [RFC3763], and [RFC4656] are extensive and directly applicable to the usage of these metrics, so they should be consulted for additional details. ⚠️ Seriously, go read them, bestie, they are not optional vibes 😭
12. References 📚
12.1. Normative References 🌟
[RFC2330] Paxson, V., Almes, G., Mahdavi, J., and M. Mathis, "Framework for IP Performance Metrics", RFC 2330, May 1998.
[Pi07] N. M. Piratla and A. P. Jayasumana, "Metrics for Packet Reordering - A Comparative Analysis," International Journal of Communication Systems (IJCS), Vol. 21/1, 2008, pp: 99-113.
12.2. Informative References ✨
okay bestie, this is the reading list 📚💅 these are the background papers and docs the authors leaned on. none of them are required to implement anything, they're just the receipts 🧾🫶
[Ben99] J. C. R. Bennett, C. Partridge and N. Shectman, "Packet Reordering is Not Pathological Network Behavior," IEEE/ACM Trans. on Networking , Dec. 1999, pp.789-798.
[Jai03] S. Jaiswal, G. Iannaccone, C. Diot, J. Kurose and D. Towsley, "Measurement and Classification of Out-of-sequence Packets in Tier-1 IP Backbone," Proc. IEEE INFOCOM, Mar. 2003, pp. 1199-1209.
[Pax97] 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.
[Boh03] S. Bohacek, J. Hespanha, J. Lee, C. Lim and K.Obraczka, "TCP-PR: TCP for Persistent Packet Reordering," Proc. of the IEEE 23rdICDCS, May 2003, pp.222-231.
[Bla02] E. Blanton and M. Allman, "On Making TCP More Robust to Packet Reordering," ACM Computer Comm. Review, 32(1), Jan. 2002, pp.20-30.
[Lao02] M. Laor and L. Gendel, "The Effect of Packet Reordering in a Backbone Link on Application Throughput," IEEE Network, Sep./Oct. 2002, pp.28-36.
[Bar04] A. A. Bare, "Measurement and Analysis of Packet Reordering Using Reorder Density," Masters Thesis, Department of Computer Science, Colorado State University, Fort Collins, Colorado, Fall 2004.
[Ban02] T. Banka, A. 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, pp. 332-342.
[Pi05a] N. M. Piratla, "A Theoretical Foundation, Metrics and Modeling of Packet Reordering and Methodology of Delay Modeling using Inter-packet Gaps," Ph.D. Dissertation, Department of Electrical and Computer Engineering, Colorado State University, Fort Collins, CO, Fall 2005.
[Pi05b] N. M. Piratla, A. P. Jayasumana and A. A. Bare, "RD: A Formal, Comprehensive Metric for Packet Reordering," Proc. 5th International IFIP-TC6 Networking Conference (Networking 2005), Waterloo, Canada, May 2-6, 2005, LNCS 3462, pp: 78-89.
[Pi06] N. M. Piratla and A. P. Jayasumana, "Reordering of Packets due to Multipath Forwarding - An Analysis," Proc. IEE Intl. Conf. Communications ICC 2006, Istanbul, Turkey, Jun. 2006, pp:829-834.
[Per04] Perl Scripts for RLED and RBD, http://www.cnrl.colostate.edu/packet_reorder.html, Last modified on Jul. 18, 2004.
[Ye06] B. Ye, A. P. Jayasumana and N. Piratla, "On Monitoring of End-to-End Packet Reordering over the Internet," Proc. Int. Conf. on Networking and Services (ICNS'06), Santa Clara, CA, July 2006.
[RFC4737] Morton, A., Ciavattone, L., Ramachandran, G., Shalunov, S., and J. Perser, "Packet Reordering Metrics", RFC 4737, November 2006.
[RFC3763] Shalunov, S. and B. Teitelbaum, "One-way Active Measurement Protocol (OWAMP) Requirements", RFC 3763, April 2004.
[RFC4656] Shalunov, S., Teitelbaum, B., Karp, A., Boote, J., and M. Zekauskas, "A One-way Active Measurement Protocol (OWAMP)", RFC 4656, September 2006.
[Pi05c] N. M. Piratla, A. P. Jayasumana and T. Banka, "On Reorder Density and its Application to Characterization of Packet Reordering," Proc. 30th IEEE Local Computer Networks Conference (LCN 2005), Sydney, Australia, Nov. 2005, pp:156-165.
13. Contributors 🎀
big thank you to our contributor, Jerry McCollom 🫶 here's where to find him:
Jerry McCollom
Hewlett Packard, 3404 East Harmony Road
Fort Collins, CO 80528, USA
EMail: jerry_mccollom@hp.comAuthors' Addresses 💜
and here are the authors, the brains behind the whole thing 🧠✨
Anura P. Jayasumana
Computer Networking Research Laboratory
Department of Electrical and Computer Engineering
1373 Colorado State University,
Fort Collins, CO 80523, USA
EMail: Anura.Jayasumana@colostate.edu
Nischal M. Piratla
Deutsche Telekom Laboratories
Ernst-Reuter-Platz 7
D-10587 Berlin, Germany
EMail: Nischal.Piratla@telekom.de
Tarun Banka
Computer Networking Research Laboratory
Department of Electrical and Computer Engineering
1373 Colorado State University
Fort Collins, CO 80523, USA
EMail: Tarun.Banka@colostate.edu
Abhijit A. Bare
Agilent Technologies, Inc.
900 South Taft Ave.
Loveland, CO 80537, USA
EMail: abhijit_bare@agilent.com
Rick Whitner
Agilent Technologies, Inc.
900 South Taft Ave.
Loveland, CO 80537, USA
EMail: rick_whitner@agilent.comFull Copyright Statement ⭐
this part is legal stuff, so I'm keeping it word-for-word so nothing gets lost 🙈
Copyright (C) The IETF Trust (2008).
This document is subject to the rights, licenses and restrictions
contained in BCP 78 and at http://www.rfc-editor.org/copyright.html,
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 🦋
same deal here, the IPR stuff stays exactly as written 💅
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; nor does it 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.📦 where this page comes from
- ietf: rfc5236 2008-06
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms