Internet Engineering Task Force Anura P. Jayasumana INTERNET-DRAFT Nischal M. Piratla draft-jayasumana-reorder-density-03.txt Abhijit A. Bare Tarun Banka Colorado State University Rick Whitner Jerry McCollom Agilent Technologies July 2004 Expires: January 2005 Reorder Density and Reorder Buffer-occupancy Density - Metrics for Packet Reordering Measurements Status of this memo By submitting this Internet-Draft, we certify that any applicable patent or other IPR claims of which we are aware have been disclosed, and any of which we become aware will be disclosed, in accordance with RFC 3668. This document may not be modified, and derivative works of it may not be created, except to publish it as an RFC and to translate it into languages other than English. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or made obsolete by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/1id-abstracts.html. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Copyright Notice Copyright (C), 2004, The Internet Society. All Rights Reserved. Abstract Out of order arrival of packets is a common occurrence on Internet, and it will be more widespread as the link speeds increase. Percentage packet reordering is vague and unclear. A good reorder metric will capture the occurrence and characteristics of reordering Anura Jayasumana [Page 1] Internet Draft July 2004 comprehensively, and have broader utility than merely distinguishing among different reordered sequences. Two metrics for packet reordering are presented, namely, Reorder Density (RD) and Reorder Buffer-occupancy Density (RBD). A threshold is used to clearly define when a packet is considered lost, to upper bound computational complexity at O(N), and to keep the memory requirement for evaluation independent of N, where N is the length of the packet sequence. RD is a comprehensive metric that captures the characteristics of reordering, while RBD evaluates the sequences from the point of view of recovery from reordering. These metrics are simple to compute yet comprehensive in their characterization of packet reordering. The measures are robust, and orthogonal to packet loss and duplication. Table of Contents 1. Introduction and Motivation . . . . . . . . . . . . . . . . . 3 2. Definitions of the terms used . . . . . . . . . . . . . . . . 5 2.1 Receive_index (RI) . . . . . . . . . . . . . . . . . . . . 5 2.2 Out-of-order Packet . . . . . . . . . . . . . . . . . . . . 6 2.3 Early-packet and Late-packet . . . . . . . . . . . . . . . 6 2.4 Displacement (D) . . . . . . . . . . . . . . . . . . . . . 6 2.5 Displacement Threshold (DT) . . . . . . . . . . . . . . . . 7 2.6 Lateness/Earliness Frequency (FLE) . . . . . . . . . . . . 7 2.7 Reorder Density (RD) . . . . . . . . . . . . . . . . . . . 7 2.8 Expected Packet (E) . . . . . . . . . . . . . . . . . . . . 7 2.9 Buffer Occupancy (B) . . . . . . . . . . . . . . . . . . . 8 2.10 Buffer Occupancy Threshold (BT) . . . . . . . . . . . . . . 8 2.11 Buffer Occupancy Frequency (FB) . . . . . . . . . . . . . . 8 2.12 Reorder Buffer-occupancy Density (RBD) . . . . . . . . . . 8 3. Representation of packet reordering and Reorder Density . . . 8 4. Selection of DT . . . . . . . . . . . . . . . . . . . . . . . 9 5. Detection of Lost and Duplicate Packets . . . . . . . . . . . 10 6. Algorithms to compute RD and RBD . . . . . . . . . . . . . . . 10 5.1 RD Algorithm . . . . . . . . . . . . . . . . . . . . . . . 11 5.2 RBD Algorithm . . . . . . . . . . . . . . . . . . . . . . . 12 7. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 8. Comparison with Other Metrics . . . . . . . . . . . . . . . . 18 9. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 10. Security Considerations . . . . . . . . . . . . . . . . . . . 20 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 12. Normative References . . . . . . . . . . . . . . . . . . . . . 20 13. Author's Address . . . . . . . . . . . . . . . . . . . . . . . 21 14. Revision History . . . . . . . . . . . . . . . . . . . . . . . 22 Full Copyright Statement . . . . . . . . . . . . . . . . . . . . . 22 Intellectual Property . . . . . . . . . . . . . . . . . . . . . . 22 Appendix A . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Appendix B . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Anura Jayasumana [Page 2] Internet Draft July 2004 1. Introduction and Motivation The increase in link speeds, increased parallelism within routers and switches, QoS support and load balancing among links, all point to future networks with increased packet reordering. Major causes for reordering of packets include but are not limited to packet stripping at layers 2 and 3 [1,2], priority scheduling (ex.diffserv), and route fluttering [3,4,5]. Reordering leads to degradation of the performance of many applications [1,6,7]. For example, perceived quality of voice degrades if a VoIP application receives packets out-of-order. Once the reordering in arriving packet streams is measured and/or quantified, it may be possible to predict the effects of reordering on applications that are sensitive to reordering, and perhaps even 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 lacks in detail. There is no uniform definition of the degree of reordering of an arrived packet [8,9]. For example, consider two packet sequences (1, 3, 4, 2, 5) and (1, 4, 3, 2, 5). It is possible to interpret the reordering of packets differently in this case, 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. In essence, the percentage of out-of-order packets is subject to interpretation and it cannot capture the reordering unambiguously and, hence, accurately. Other metrics attempt to overcome this ambiguity by defining only the late packets or only the early packets to be reordered. However, measuring reordering based on only late packets or early packets is not always effective. Consider a metric that measures packet reordering based on lateness only. For example, consider a sequence of packets with the only anomaly being packet 20 delivered after packet 1: (1, 20, 2, 3,..,19, 21, 22, ...). A metric based only on lateness will indicate a high degree of reordering, whereas it is caused by one packet arriving ahead of others. Similarly, a metric based only on earliness does not capture reordering caused by a late packet accurately. Thus, a complete reorder metric should account for both earliness and lateness and be able to differentiate them. Anura Jayasumana [Page 3] Internet Draft July 2004 With the two packet sequences (1, 3, 4, 2, 5) and (1, 4, 3, 2, 5), for example if buffers are available to store the packets 3 and 4 while waiting for the packet 2, it is possible to recover from the reordering. However, there may be cases where the application requirement is such that arrival of packet 2 after this delay renders it useless. While one can argue that a good packet reordering measurement scheme should capture such effects, a counter argument can also be made that packet reordering should be measured strictly with respect to the order of delivery and should be application independent. The desirable attributes of a packet reorder metric include: 1) Simplicity: The measure should be simple, yet contain sufficient information to be useful. 2) Orthogonality: Metric, to the extent possible, should be independent of or orthogonal to other phenomena that affect the packet streams, e.g., packet loss and duplication. 3) Usefulness: Rather than being a mere representation of the amount of reordering in a packet stream, reorder metric should be useful to the application and/or resource management schemes. For example, it may allow one to determine the size of buffer that is required to recover from reordering. 4) Differentiability: Metric should provide insight into the nature of reordering, and perhaps even into possible causes. 5) Evaluation complexity: The metric should be computable in real-time. In evaluating reordering in an arbitrarily long sequence, one should be able to keep a running measurement, without having to wait till all the packets have arrived. The memory requirement, i.e. the amount of state information, should not grow with the length of the sequence (N), and the computation time should be O(N). 6) Robustness: The metric should be self-correcting against events such as bursty losses, and sequence number wraparound. It should also have a sense of proportionality, i.e. the measure should not change significantly due to a peculiar behavior of a very small number of packets. For example, consider a TCP sequence number rollover scenario with packet 2000 from the previous cycle appearing in initial part of the current cycle which starts from sequence number 1,2,.. This will cause a large change in a late-packet reorder metric. 7) Broader Applicability: A good metric should have applicability beyond just characterizing the nature of reordering in a given sequence of packets. For example, a good metric may allow one to combine the reorder characteristics of individual networks to predict the reorder behavior of the network formed by concatenation of these networks. Anura Jayasumana [Page 4] Internet Draft July 2004 In this memo, we define two density functions, Reorder Density (RD) and Reorder Buffer-occupancy Density (RBD), that capture the nature of reordering in a packet stream. These two metrics may be used individually or collectively to characterize the reordering in a packet stream. Reorder density is the normalized distribution of the displacement of a packet from its original position. Lost and duplicate packets are accounted for in evaluating the displacement. The nature of reordering introduced by a network with stationary statistical characteristics can be captured using this metric in the form of a reorder response [9,10]. For reordering introduced by such a system, or for a statistically significant sequence of packets, RD is the probability density of the packet displacement. RBD is the normalized histogram of the occupancy of a hypothetical buffer that would allow the recovery from out-of-order delivery of packets. If an arriving packet is early, it is added to a hypothetical buffer until it can be released in order. The occupancy of this buffer after each arrival is used as the measure of reordering. However, the arrival of a packet may be regarded useless different constraints, such as due to the application, e.g., the packet may be too late for a real-time application. To accommodate such constraints, we define a threshold on the hypothetical buffer size, as explained in section 2.10. In [8], this metric is called RD and buffer occupancy is known as displacement. RD and RBD are simple, orthogonal to loss and duplication, useful to improve/evaluate the application performance, robust against peculiarities and have a computation complexity of O(N), where the received sequence size is N. Also, RD of a cascade of a network formed by two subnets is the convolution of RDs of individual subnets. 2. Definitions of terms used Some important terms are defined, which will help us describe the Reorder Density, the Reorder Buffer-occupancy Density and the measurement algorithm. We do not explicitly address wraparound of sequence numbers in this document, but with the use of modulo-N arithmetic, all the claims here remain valid, in the presence of wraparound. 2.1 Receive_index (RI): Without loss of generality, consider a sequence of packets (1, 2,..N) transmitted over a network. A receive_index RI, (1, 2,..) is assigned to each packet as it arrives at the destination. A receive_index is not assigned to a duplicate, and the receive_index skips the number corresponding to a lost packet. The detection of loss and duplication Anura Jayasumana [Page 5] Internet Draft July 2004 for this purpose is described later (section 5). RI is used to compute earliness and lateness of an arriving packet. Below 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 is no loss or duplication. In example 2, the packet with sequence number 2 is lost, and thus 2 is not assigned as a RI; packet 3 is duplicated, thus the second copy is not assigned an RI. 2.2 Out-of-order Packet: When the sequence number of a packet is not equal to the RI assigned to it, it is considered as an out-of-order packet. Duplicates, for which RI is not defined, are ignored. 2.3 Early-packet and Late-packet: An arriving packet i is early if its sequence number is greater than its RI and it is late if its sequence number is less than its RI. Let the receive_index of packet 'i' be RI[i]. If i > RI[i] the packet is early, and i < RI[i] the packet is late. 2.4 Displacement (D): Displacement of a packet is defined as the difference between RI and the sequence number of the packet, i.e., the displacement of packet i is RI[i] - i. Thus, a negative displacement refers to the earliness of a packet and a positive displacement to the lateness. In example 3 below, an arrived sequence with displacements of each packet are illustrated. 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 2 Anura Jayasumana [Page 6] Internet Draft July 2004 2.5 Displacement Threshold (DT): This parameter is a threshold on the displacement of a packet that allows the metric to classify a packet as lost or duplicate. It is arguable as to when a packet can be classified as lost. One could wait till the end of sequence and if a packet does not arrive, it may be labeled as lost. But, the packet may still arrive after a long delay. Thus, there is no point in time that a packet can theoretically be classified as lost. From a practical point of view however, a packet may be classified as lost if it hasnĖt arrived within a certain displacement threshold, DT. If DT is selected too small, reordered packets may be classified as lost. A large DT will increase the size of memory to keep track of sequence numbers as well as computation time to evaluate the metric. Similarly, to identify whether a packet is a duplicate, theoretically it is necessary to keep track of all the arrived (or missing) packets so far. But from a practical point of view, missing packets within a certain window of sequence numbers suffice. We use DT for declaring a packet as lost, or as a duplicate. It is indeed possible to use two different thresholds for the two cases. The selection of DT is further discussed in section 4. DT makes the metric more robust and keeps the computation complexity for long sequences within O(N), and storage requirement independent of N. 2.6 Lateness/Earliness Frequency (FLE) Lateness/Earliness frequency FLE[k] is the number of arrived packets having a displacement of k. Due to the use of DT, k takes the value from -DT to DT. 2.7 Reorder Density (RD) RD is defined as the distribution of all Lateness/Earliness frequencies FLE[k] normalized with respect to total number of non-duplicate packets received (N'), where N' is the length of the received sequence ignoring lost and duplicate packets. N' is also the sum(FLE[k]) for all k such that k belongs to [-DT, DT]. 2.8 Expected Packet(E): A packet with sequence number 'E' is expected, if E is the largest number such that all the packets with sequence number less than E have already arrived or have been detected to be lost. Anura Jayasumana [Page 7] Internet Draft July 2004 2.9 Buffer Occupancy (B): An arrived packet with a sequence number greater than that of expected packet is considered to be stored in a hypothetical buffer long enough to recover from reordering. At any packet arrival, the buffer occupancy is equal to the number of such out-of-order packets in the buffer including the arrived packet (assuming one buffer for each packet). For example, for the sequence of packets (1, 2, 4, 5, 3), the expected order is (1, 2, 3, 4, 5) and buffer occupancy value, when the packet with the sequence number 4 arrives is 1 because it arrived early. Similarly, the buffer occupancy becomes 2, when the packet with the sequence number 5 arrives. When the packet with sequence number 3 arrives, we recover from reordering and the buffer occupancy changes to zero. 2.10 Buffer Occupancy Threshold (BT) Buffer occupancy threshold BT, is a parameter that places a threshold on the maximum size of the hypothetical buffer that is used for recovery from reordering. As in the case of DT, it is used for loss and duplication classification for RBD computation. It also provides robustness in addition to limiting the computation complexity of RBD. 2.11 Buffer Occupancy Frequency (FB) At the arrival of each packet the buffer occupancy may take any value 'k' ranging from 0 to BT. The buffer occupancy frequency FB[k] is the number of times the occupancy takes the value of 'k'. 2.12 Reorder Buffer-occupancy Density (RBD) Buffer occupancy frequencies are normalized against the total number of non-duplicate packets received to compute Reorder Buffer-occupancy density, i.e. RBD[k] = FB[k]/N' where N' is the length of the received sequence ignoring lost and duplicate packets. N' is also the sum(FB[k]) for all k such that k belongs to [0, BT]. 3. Representation of packet reordering and Reorder Density Without loss of generality, consider a sequence of packets (1, 2,...N) transmitted over a network. An index, (1, 2,...), denoted by receive_index, is assigned to each packet as it arrives at the destination. A receive_index is not assigned to lost and duplicate packets. In the absence of reordering the sequence number of the packet and the receive_index are same for each packet. Let the receive_index assigned to packet m be (m + dm ). This event is represented by r(m, dm). When dm is not equal to zero, we say that a reorder event has occurred. A packet is late if this offset dm > 0, and early if dm < 0. Thus, packet reordering of a sequence of packets is completely represented by the union of reorder events, R, referred to as the reorder set: Anura Jayasumana [Page 8] Internet Draft July 2004 R = {r(m,dm)| dm not equal to 0 for all m} If there is no reordering in a packet sequence then R is the null set. Examples 4 and 5 illustrate the reorder set: Example 4. No losses or duplicates Arrived Sequence 1 2 3 5 4 6 Receive_index 1 2 3 4 5 6 Displacement 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 1 2 3 5 6 - Displacement 0 0 -2 2 0 - R = {(3, 2), (5, -2)} RD is defined as the discrete density of the frequency of packets with respect to their displacements, i.e., the lateness and earliness from the original position. Let S[k] denote the set of reorder events in R with displacement equal to k , i.e., S[k]= {r(m, dm)| dm = k} Let |S[k]| be the cardinality of set S[k] . Thus, RD[k] is defined as |S[k]| normalized with respect to the total number of received packets (N'). Note that N' does not include duplicates or lost packets. RD[k] = |S[k]|/ N' for k not equal to zero. RD [0] corresponds to the packets for which receive_index is the same as the sequence number. Thus RD[0] = 1 - sum(|S[k]| / N ') Thus, defined FLE[k] is the measure that keeps track of |S[k]|. 4. Selection of DT While the selection of the value of DT, for the purpose of defining lost and duplicate packets and to keep computation/storage complexity within bounds, appears to introduce an error, this need not be the case in practice. Application, transport layer protocol or the network characteristics often define a value, above which DT does not have an impact on the measurement. In case of a VoIP application, for example, with a bit-rate of 128kbps and packet size of 200 bytes, DT value can be determined as follows. Assume that the application can Anura Jayasumana [Page 9] Internet Draft July 2004 wait maximum 50 ms for an expected packet, and that the packets arrive at constant rate. That means within 50 ms, the application can receive (128*1000*0.05)/(200*8) i.e. 4 packets. Since the packet arriving after this duration is as good as lost, the DT value could be kept at 4. If application is such that a DT can be defined then the use of DT does not cause any limitation, i.e., increasing DT does not provide any benefit. In case of TCP, the transmit and receive windows impose a natural limit on the useful value of DT. If there is no limitation defined on DT imposed by factors just described, or if one is purely interested in a more complete picture of reordering, then DT can be made as large as required. In the worst case, DT is equal to the length of the packet sequence, we get a complete picture of reordering. This will not be a problem, if the length of the packet sequence is known before the computation, or if DT is allowed to grow without a limit. 5. Detection of Lost and Duplicate Packets As RD and RBD use thresholds, all the previous packet arrivals need not be buffered to compare with current/future arrivals. In both RD and RBD, the sequence number of the arrival is compared to the early arrivals. However, the size of buffer is limited by the thresholds DT and BT respectively. A non-duplicate packet does not have a copy in this buffer. At the same time, it cannot be earlier than those in buffer either. Thus, we can compare the sequence number against the expected sequence number and the buffer to identify a duplicate. Since a packet is not considered lost until it is late beyond DT, the question arises as to how a RI can be assigned to packets with later packet numbers. This can be handled in one of two ways: a) Go-back Method: RD and RBD are computed as the packets arrive, and when a packet is deemed lost, go back and correct receive_index values and expected sequence numbers respectively, and recompute displacements and buffer-occupancies. b) Stay-back Method: RD and RBD evaluation lags the arriving packets so that it can assign the correct receive_index and expected packet to each packet as it arrives. This way, RI and expected are assigned to packet once and they are correct values. In the worst case, the computations are delayed by DT and BT packets respectively. Stay-back method needs to stay back only when a packet is missing. 6. Algorithms to compute RD and RBD Below, we present the algorithms to compute RD and RBD. Only Stay-back method is presented here, i.e., RD and RBD values lag by DT and BT respectively, to detect lost packets. Both Stay-back and Go-back methods are described elsewhere [9]. Perl scripts for these algorithms are posted in [11]. Anura Jayasumana [Page 10] Internet Draft July 2004 To keep the explanation simple, we assume without loss of generality, that the sequence numbers start from 1 and continue with increments of 1. 6.1 RD Algorithm Variables used: RI: receive_index. S: Arrival under consideration for lateness/earliness computation. D: Lateness or earliness of the packet being processed. FLE[ -DT..DT]: Frequency of lateness and earliness. window[1..DT+1]: List of incoming sequence numbers. buffer[1..DT]: Array to hold sequence numbers of early arrivals. window[] and buffer[] are empty at the beginning. Step 1. Initialize: Store first unique DT+1 sequence numbers in arriving order into window; RI = 1; Step 2. Repeat: If (window or buffer contains sequence number RI) { Copy first sequence number in window to S; Delete first sequence number from window; D = RI - S; # compute displacement If (absolute(D) <= DT) # Apply threshold { FLE[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; } Anura Jayasumana [Page 11] Internet Draft July 2004 # 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 FLE 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; } 6.2 RBD Algorithm Variables used: BT: Buffer Occupancy Threshold. E: Currently expected sequence number. S: Arrival under consideration. B: Number of sequence numbers present in buffer. newS: Next arriving sequence number. window[1..BT+1]: List of incoming sequence numbers. buffer[1..BT]: Array to hold sequence numbers of early arrivals. TW[1..BT+1]: List of sequence numbers within threshold that are searched to detect losses. EW[1..BT+1]: List to retain expected sequence numbers of late arrivals in threshold. FB[0..BT]: Frequency of buffer-occupancy. Anura Jayasumana [Page 12] Internet Draft July 2004 Step 1. Initialize. Store first unique BT+1 sequence numbers in arriving order into window; Copy all elements in window to TW; Step 2. Repeat. # Next expected sequence number, newE, is the smallest element # in TW. Thus, lost packets are neglected. newE = smallest sequence number in TW; Delete newE from TW; # Update TW Add newE to EW; # Update EW # Following is regular RBD processing. S = first sequence number in window; Delete first sequence number from window; E = first sequence number in EW; If (S == E) # Next expected packet arrived { Delete E from EW; # Sequence number is not expected anymore k = first sequence number in EW; # k is a temporary variable. While (buffer contains sequence number k) { Delete k from both EW and buffer; k = first sequence number in EW; } } Else # S is an early arrival. Add it to the buffer. Add S to buffer; B = number of occupied slots in buffer; FB[B]++; # Increment frequency of current buffer occupancy # Get next incoming non-duplicate sequence number, if any. newS = get_next_arrival(); # subroutine called* if (newS != null) # subroutine called* { Add newS to window; Add newS to TW; } if (window is empty) go to step 3; Step 3. Normalize FB to get RBD; Anura Jayasumana [Page 13] Internet Draft July 2004 * 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 <= newE or newS in TW); return newS; } 7. Examples We consider a few different sequences to exemplify the above algorithm. a. Case with no packet loss: Consider a sequence of 5 packets (1, 4, 2, 5, 3, 6, 7, 8) with DT = BT = 4. Tables 1 and 2 show the computation steps when RD algorithm is applied to the above sequence. ------------------------------------------------------ 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 FLE[D] 1 1 1 1 1 2 3 4 ------------------------------------------------------ (S, RI,D,FLE[D] as described in section 6) ------------------------------------------------------ The last row (FLE[D]) represents the current frequency of occurrence of the displacement D, e.g., column 3 indicates FLE[1] = 1 while column 4 indicates FLE[-1] = 1.The final set of values for RD are shown in table 2. ------------------------------------------------- Table 2: Reorder Density (RD) ------------------------------------------------- D -2 -1 0 1 2 FLE[D] 1 1 4 1 1 RD[D] 0.125 0.125 0.5 0.125 0.125 ------------------------------------------------- (D,FLE[D],RD[D] as described in section 6) ------------------------------------------------- Anura Jayasumana [Page 14] Internet Draft July 2004 Tables 3 and 4 illustrate the computation steps for RBD for the same example -------------------------------------------------------- Table 3: Buffer Occupancy Frequency 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,FB[B] as described in section 6) -------------------------------------------------------- ------------------------------------------------- Table 4: Reorder Buffer-occupancy Density (RBD) ------------------------------------------------- B 0 1 2 FB[B] 5 2 1 RBD[B] 0.625 0.25 0.125 ------------------------------------------------- (B,FB[B],RBD[B] as described in section 6) ------------------------------------------------- Graphical representations of the densities are as follows: ^ ^ | | | _ ^ 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. Case with packet loss: Consider a sequence of 6 packets (1, 2, 4, 5, 6, 7) with DT = BT = 3. Table 5 shows the computation steps, when the RD algorithm is applied to the above sequence. Anura Jayasumana [Page 15] Internet Draft July 2004 ------------------------------------------------------ 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 FLE[D] 1 2 3 4 5 6 ------------------------------------------------------ (S, RI,D,FLE[D] as described in section 6) ------------------------------------------------------ Table 6 illustrates the RBD for the above arrival sequence. ------------------------------------------------- Table 6: Buffer Occupancy Frequency computation steps ------------------------------------------------- S 1 2 4 5 6 7 E 1 2 4 5 6 7 B 0 0 0 0 0 0 FB[D] 1 2 3 4 5 6 ------------------------------------------------- (E,S,B,FB[B] as described in section 6) ------------------------------------------------- Graphical representations of above RD and ED are as follows. ^ ^ | | 1.0 _ 1.0 _ ^ | | ^ | | | | | | | | | | | | RD[D] | | RBD[B] | | | | | | --+--+--+--> --+--+--> -1 0 1 0 1 D --> B --> c. Case of duplicate packets: Consider a sequence of 6 packets (1, 3, 2, 3 , 4, 5) with DT = 2. Tables 7 and 8 show the computation steps when the RD algorithm is applied to the above sequence. Anura Jayasumana [Page 16] Internet Draft July 2004 ------------------------------------------------------ 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 FLE[D] 1 1 1 - 2 3 ------------------------------------------------------ (S, RI,D,FLE[D] as described in section 6) ------------------------------------------------------ -------------------------------------------- Table 8: Reorder Density (RD) -------------------------------------------- D -1 0 1 FLE[D] 1 3 1 RD[D] 0.2 0.6 0.2 -------------------------------------------- (D,FLE[D],RD[D] as described in section 6) -------------------------------------------- Table 9 and 10 illustrates the RBD for the above arrival sequence. ------------------------------------------------------ Table 9: 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,FB[B] as described in section 6) ------------------------------------------------------ ------------------------------------------------- Table 10: Reorder Buffer-occupancy Density (RBD) ------------------------------------------------- B 0 1 FB[B] 4 1 RD[B] 0.8 0.2 ------------------------------------------------- (B,FB[B],RBD[B] as described in section 6) ------------------------------------------------- Anura Jayasumana [Page 17] Internet Draft July 2004 Graphical Representation of RD, ED and LD is as follows: ^ ^ | | ^ | ^ 0.8 _ | 0.6 _ | | | | | | | RD[D] | | RBD[B] | | 0.2 _ | | _ 0.2 | | _ 0.2 | || || | | || | --+--+--+--+--+--+--> ---+--+--+-- -2 -1 0 1 2 0 1 2 D --> B --> 8. Comparison with Other Metrics Percentage of out-of-order packets is commonly used as a packet reordering metric. As shown in section 1, this metric has many disadvantages. Reordering offset [12] is a metric to measure reordering. In this metric a packet is not considered reordered until it arrives. It uses the definition of late arrival as in [3]. However, a duplicate packet is considered as a reordered packet. Unlike RD and RBD, this metric is not orthogonal to duplication of packets. Appendix B uses a few example sequences to compare Reordering offset, RD and RBD. N-reordering [12] is a metric where an expected packet is 1-reordered, 2-reordered and so on till it arrives. If a packet arrives after 40 positions from its expected position then it is 40-reordered. Two examples are listed in Appendix A to show the difference between RD and RBD, and N-reordering. These examples show that N-reordering is much more susceptible to delayed packets as it cannot treat them as lost when their useful life is over, whereas with RD this is taken care of using threshold. One may argue that since N-reordering does not use a threshold, there is no possibility of characterizing a reordered packet (late by more than DT) as lost. This comes however at a heavy cost, especially with respect to long sequences, which are likely to be the cases in many measurement scenarios, both in terms of computation complexity and memory. If such complexity is acceptable, DT can be set to N in the calculation of RD and RBD to overcome this concern, while preserving its all other advantages over N-reordering. Another option is to include a threshold for loss detection in computing N-reordering as well. Anura Jayasumana [Page 18] Internet Draft July 2004 However, RD is a more comprehensive measure that captures both earliness and lateness. It can be shown that information contained in N-reordering in this case is a subset of that contained in RD. From RD measure, we can derive measures similar to N-reordering and Reordering offset that are orthogonal to loss and duplication. For example, consider a RD measure given as RD[-1]= 0.3, RD[0] = 0.5, RD[1] = 0.1, RD[2] = 0.1. The measure similar to N-reordering will have reorder measure as: 10% 2-reordering and 20% 1-reordering. reorder offset will have 10% packets by offset two and 10% by offset one. 9. Summary Two metrics for packet reordering, Reorder Density (RD) and Reorder Buffer-occupancy Density (RBD) were presented, and some of their salient features are listed below: RD captures the reorder characteristics of a packet stream in a comprehensive manner. When used with a packet sequence of sufficient length, it approaches the probability density of displacement of packets in a stream. Thus parameters such as the mean and variance of lateness of late packets, and fraction of packets arriving earlier by more than m packets, can easily be obtained. It does not assume that only two possibilities exists for a packet: ex. in lateness based metrics, a packet is either in order, or is late, but can never be early. As it considers both earliness and lateness simultaneously, it contains information that would be captured by an earliness based metric as well as a lateness based metric. RBD evaluates reordering from the perspective of recovery from reordering. Thus it provides information such as the size of buffers required for an application to recover from reordering. Both RD and RBD use thresholds to clearly define when a packet is considered lost. They also use these thresholds to overcome having to maintain a long list (of all received packets or all missing packets) to identify duplicates. As a result they can accommodate anomalies such as burst losses and multiple duplicates in a robust manner. The threshold values can be selected to achieve the required degree of accuracy. The time complexity of evaluating RD and RBD for a stream of packets is O(N), while the amount of memory needed is proportional to the threshold (DT or BT). Both RD and RBD are orthogonal to loss and duplication. In comparison, N-reordering and reordering offset are not. Information provided by RD may be used to change the number of duplicate ACKs a TCP implementation could wait before opting for fast retransmits [13]. RBD is useful for evaluating the impact of reordering on the performance of an application relying on a buffer for recovery, and conversely to estimate the storage requirements or other parameters to achieve required quality of service. Anura Jayasumana [Page 19] Internet Draft July 2004 RD, a density function of displacement of packets, can help significantly in modeling theoretical analysis of reordering. In fact, for a network with stationary statistical characteristics, and a given interpacket gap distribution of a input packet stream, the reordering of the network may be characterized using a Reorder Response, the RD observed at the output. In [10], we prove that the reorder response of two concatenated subnets is equal to the convolution of the reorder responses of the two subnets. Algorithms for generating sequences of packets for a given RD, and RBD are described in [14]. Such algorithms are useful for simulation of networks to understand the interaction of reordering produced by complex networks of subnets. 10. Security Considerations This document does not define any protocol. The metric definition per se is believed to have no security implications. 11. IANA Considerations This document requires nothing from the IANA. 12. References [1] J. C. R. Bennett, C. Partridge and N. Shectman, "Packet Reordering is Not Pathological Network Behavior," Trans. on Networking IEEE/ACM, Dec. 1999, pp.789-798. [2] 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. [3] 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. [4] S. Bohacek, J. Hespanha, J. Lee, C. Lim and K.Obraczka, "TCP-PR: TCP for Persistent Packet Reordering," In Proc. of the IEEE 23rd ICDCS, May 2003, pp.222-231. [5] G. Iannaccone, S. Jaiswal and C. Diot, "Packet Reordering Inside the Sprint Backbone," Tech.Report, TR01-ATL-062917, Sprint ATL, Jun. 2001. [6] E. Blanton and M. Allman, "On Making TCP More Robust to Packet Reordering," ACM Computer Comm. Review, 32(1), Jan. 2002, pp.20- 30. Anura Jayasumana [Page 20] Internet Draft July 2004 [7] 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. [8] 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. [9] N. M. Piratla, "Metrics, measurements and techniques to characterize Internet," Ph.D. Dissertation, Department of Electrical and Computer Engineering, Colorado State University, Fort Collins, CO. (in progress) [10] N. M. Piratla, A. P. Jayasumana and A. A. Bare, " RD: A Formal, Comprehensive Metric for Packet Reordering," (under review for publication). [11] Perl Scripts for RLED and RBD, http://www.cnrl.colostate.edu/Reorder_Density.html, Last modified on Jul. 18, 2004. [12] A. Morton, L. Ciavattone, G. Ramachandran, S.Shalunov and J.Perser, "Packet Reordering Metric for IPPM", Internet Draft, , August 2004. [13] M. Zhang, B. Karp, S. Floyd and L. Peterson, "RR-TCP: A Reordering-Robust TCP with DSACK," Proc. The Eleventh IEEE International Conference on Networking Protocols (ICNP 2003), Atlanta, GA, Nov. 2003, pp. 95-106. [14] 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. 13. Authors' Addresses Anura P. Jayasumana Nischal M. Piratla Abhijit A. Bare Tarun Banka Computer Networking Research Laboratory, Department of Electrical and Computer Engineering, 1373 Colorado State University, Fort Collins, CO 80523. Rick Whitner Jerry McCollom Agilent Technologies, 4380 Ziegler Rd., Fort Collins, CO, USA Expiration Date: January 2005 Anura Jayasumana [Page 21] Internet Draft July 2004 14. Revision History This is a third version of this draft. The following changes have been made when compared to the previous drafts: 1) ED (Early Density) and LD (Late Density) in the previous draft have been replaced by a new Reorder Density function, that captures the information in ED, LD, and more, in a single, comprehensive metric. Reorder Density function is orthogonal to losses and duplicates, and capture both lateness and earliness. The new reorder density function addresses all the concerns expressed at the IETF meeting, Fall 2003. 2) The Reorder Density function defined in the previous draft is renamed Reorder Buffer-occupancy Density (RBD), reflecting its properties more accurately. It has also been modified to address the comments from ippm, including orthogonality to packet loss. 3) As suggested by the RFC reviewers, the formal definitions for RBD and RD are included. Full Copyright Statement Copyright (C) The Internet Society (2004). 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 CONTRIBUTORS, THE ORGANIZATIONS THEY REPRESENT OR ARE SPONSORED BY (IF ANY), THE INTERNET SOCIETY 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 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; neither does it represent that it has made any effort to identify any such rights. Information on the IETF's procedures with respect to rights in standards-track and standards-related documentation can be found in BCP-11. 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 repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent Anura Jayasumana [Page 22] Internet Draft July 2004 applications, or other proprietary rights, which may cover technology that may be required to practice this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Appendix A Example 1:For the sequence <1,2,3,4,5,2,1> RD output: --------------------- Reorder Density --------------------- D 0 FLE[D] 5 RD[D] 1.00 --------------------- RBD output: ----------------------------------- Reorder Buffer-occupancy Density ----------------------------------- B 0 FB[B] 5 RBD[B] 1.00 ----------------------------------- N-reordering output: 1-reordering = 33.333333% 2-reordering = 40.000000% 3-reordering = 50.000000% 4-reordering = 33.333333% 5-reordering = 50.000000% no 6-reordering 1-reordering = 2 2-reordering = 2 3-reordering = 2 4-reordering = 1 5-reordering = 1 no 6-reordering In this example, the N-reordering algorithm shows that there is 5-reordering. If you look at the sequence there are two duplicate packets namely, sequence numbers 2 & 1. In RD and RBD, these packets are discarded. As obvious, the sequence has no reordering. Anura Jayasumana [Page 23] Internet Draft July 2004 Example 2: For Sequence: <1,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26, 27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,2> RD output with DT = 5: ------------------ Reorder Density ------------------ D 0 FLE[D] 40 RD[D] 1.00 ------------------ RBD output with BT = 5: ----------------------------------- Reorder Buffer-occupancy Density ----------------------------------- B 0 FB[B] 40 RBD[B] 1.00 ----------------------------------- Since packet 2 is assumed to be lost, there are no late packets, which leads to no reordering. N-reordering output: 1-reordering = 2.500000% 2-reordering = 2.564103% 3-reordering = 2.631579% 4-reordering = 2.702703% 5-reordering = 2.777778% 6-reordering = 2.857143% 7-reordering = 2.941176% 8-reordering = 3.030303% 9-reordering = 3.125000% 10-reordering = 3.225806% 11-reordering = 3.333333% 12-reordering = 3.448276% 13-reordering = 3.571429% 14-reordering = 3.703704% 15-reordering = 3.846154% 16-reordering = 4.000000% 17-reordering = 4.166667% 18-reordering = 4.347826% 19-reordering = 4.545455% 20-reordering = 4.761905% 21-reordering = 5.000000% 22-reordering = 5.263158% Anura Jayasumana [Page 24] Internet Draft July 2004 23-reordering = 5.555556% 24-reordering = 5.882353% 25-reordering = 6.250000% 26-reordering = 6.666667% 27-reordering = 7.142857% 28-reordering = 7.692308% 29-reordering = 8.333333% 30-reordering = 9.090909% 31-reordering = 10.000000% 32-reordering = 11.111111% 33-reordering = 12.500000% 34-reordering = 14.285714% 35-reordering = 16.666667% 36-reordering = 20.000000% 37-reordering = 25.000000% 38-reordering = 33.333333% 39-reordering = 50.000000% no 40-reordering This example clearly shows that N-reordering is much more susceptible to delayed packets as it cannot treat them as lost when their useful life is over, whereas RD and RBD are most robust metrics. Appendix B From "...Table 1 Example with Packet 4 Reordered, Sending order(SrcNum@Src): 1,2,3,4,5,6,7,8,9,10 SrcNum Src Dst Dst Posit. 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 4 62 9 9 160 228 68 0 9 10 10 180 248 68 0 10 Each column gives the following information: Anura Jayasumana [Page 25] Internet Draft July 2004 SrcNum Packet sequence number at the Source. NextExp The value of NextExp when the packet arrived(before update). SrcTime Packet time stamp at the Source, ms. DstTime Packet time stamp at the Destination, ms. Delay 1-way delay of the packet, ms. IPDV IP Packet Delay Variation, ms IPDV = Delay(SrcNum)-Delay(SrcNum-1)..." Reorder Buffer Density (BT =5) for the above example: SrcNum @Dst NextExp Buffer occupancy Frequency 1 1 0 FB[0] = 1 2 2 0 FB[0]++ 3 3 0 FB[0]++ 5 4 1 FB[1] = 1 6 4 2 FB[2] = 1 7 4 3 FB[3] = 1 8 4 4 FB[4] = 1 4 4 0 FB[0]++ 9 9 0 FB[0]++ 10 10 0 FB[0]++ Normalized FB[i] for all i: FB[0] = 0.6, FB[1] = 0.1, FB[2] = 0.1, FB[3] = 0.1, FB[4] = 0.1 In this case, if we can set DT = 3 to get something equivalent to IPDV must be less than 80 time units, then the table will look like this: SrcNum @Dst Expected Buffer occupancy Frequency 1 1 0 FB[0] = 1 2 2 0 FB[0]++ 3 3 0 FB[0]++ 5 4 1 FB[0]++ 6 4 2 FB[0]++ 7 4 3 FB[0]++ 8 4 0 FB[0]++ {after the current packet's arrival, packet '4' is rendered useless!} 4 9 0 - {discarded pkt.} 9 9 0 FB[0]++ 10 10 0 FB[0]++ Normalized FB[i] for all i: FB[0] = 9/9 = 1. Anura Jayasumana [Page 26]