Network Working Group D. Pullin Internet Draft California Institute of Technology Expiration Date: August 2002 A. Corlett B. Mandeville CQOS, Inc. S. Critchley Worldcom, Inc. Packet Reordering: The Minimal Longest Ascending Subsequence Metric Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026 [1]. 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/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract This draft describes a metric, based on the minimal longest ascending subsequence (MLAS), which can be used to measure the level of reorderedness of a given single sequence of packets transmitted by one host and received by a second. This metric enables reordering between similar packet flows to be compared across differing network topologies. The draft goes on to provide a set of recommended parameters which can be used when attempting to consistently compare reordering, and highlights potential issues which should be taken into account during measurement. 1. Introduction Traditionally, the effect of network conditions upon applications transmitting packets from one host to another has been measured according to the parameters generally accepted to have the most effect on the performance of the applications sending and receiving those packets. The following are usually measured - loss, delay (both one-way and two-way), and jitter. However, certain IP-based applications, such as voice, video, and encapsulated Layer 2 services, also rely to some extent on packets sent being received in the same order in which they were transmitted. These applications are affected to different extents by the level of reordering experienced. Reordering can be said to have occurred if packets are received in anything other than exactly the same order in which they are transmitted. However, should reordering occur, there is currently no standard metric in place with which to define the degree to which a sequence of packets received is out of order in relation to the sequence in which it was transmitted [2]. This document sets out to define such a metric, and provide a set of recommendations in order to assist in measurement. 2. An MLAS-based Packet Reordering Metric. 2.1 Metric considerations When transmitting, receiving, and sampling a sequence of packets in order to determine the level of reorderedness of that sequence, it is necessary to take into account the following: - Transmission and receipt devices. The sampled sequence of packets is always transmitted from one device, known as the source, and received at another device, known as the destination. In that way, a level of reordering can be given for packets passing in one direction across a network. - Sampling device. The device performing calculations on the packet sequence in order to derive a level of reorderedness may or may not be the same device as the destination device. - Length of Sequence The transmission device is capable of transmitting a defined number of packets in a sample sequence. The sampling device is aware of the number of packets defined in the sample sequence. Whether the transmission device labels each packet in a sample sequence with the length of that sequence is optional. - Transmission Interval The transmission device is capable of transmitting sample packets with a given interval between transmission. This interval is generally stated as the number of packets sent per second for any given sequence. The device sampling the given sequence of packets for reorderedness is aware of the interval between transmission of packets by the source. Whether the transmission device labels each packet transmitted in the sample sequence with the transmission interval of packets in that sequence is optional. - Overall Transmission Envelope It is assumed that 100% of packets in the sample sequence sent by the transmission device are received, and that they are received within a given time following transmission of the initial packet in the sequence, stated in seconds. Packets received after the end of this transmission envelope are discounted.Whether the transmission device labels each packet in the sequence with the overall envelope of the sequence is optional. - Packet Size The tranmission device is capable of transmitting sample packets in a given sequence with a standard packet size. This packet size is generally stated as a number of bytes. The sampling device is capable of aware of the packet size of each packet in the sample flow. Whether the transmission device labels each packet transmitted in the sample sequence with the given standard packet size for that sequence is optional. All packets in a given sequence should be of the same size. - Sequence Numbers All packets transmitted in a sample flow or sequence are given a transmission sequence number by the source device, and are given a receipt sequence number by the destination device. - Sequence awareness The device sampling the sequence of packets for reorderedness is capable of reading both the transmission and receipt sequence numbers, and of performing the calculation necessary to derive the degree of reorderedness of the sequence. It can therefore be stated that a sample packet sequence has the following stated properties: - Sequence Length, in number of packets. - Transmission Interval, in packets per second. - Overall Transmission Envelope, in seconds. - Packet Size, in bytes, for each packet. - Unique Sequence Numbers, both transmission and receipt, for each packet. 2.2 Definition of the MLAS-based Packet Ordering Metric. Suppose that we a set of integers {X} with elements x(i),i=1,....,N. These integers may represent the send order of a sequence of packets. For the purposes of this discussion the elements x(i) may be any integer, negative, zero or positive. Any number of repeated elements are allowed. In practice these integers may represent the send order of a sequence of packets, and so will be positive integers. An example with N=10 is {X} : {3,2,4,6,5,9,7,1,10,8} An ascending subsequence of X, denoted by {S} of length m, is defined as any subsequence of {X} which has the properties that (i) it contains m elements, (ii) the elements appear in {S} in the same order as they appear in{X} (iii) the elements of {S} are in ascending order. In the above example, there are countably many ascending subsequences of the given sequence. For example, ascending subsequences of length m=3 of the sequence of {X} given above include {S_1} : {2,4,6 } {S_2} : {4,7,10} {S_3} : {5,9,10} These are not exhaustive. 2.1.1 The Minimal Longest Ascending Subsequence (MLAS) For a given {X}, there exists some m=m_{max} such that no ascending subsequence is of length greater than m=m_{max}. For our example m_{max}=5 and {S_1} : {2,4,5,9,10} {S_2} : {2,4,5,7,10} {S_3} : {2,4,5,7,8} are all ascending subsequences of length m=5. We call these the longest ascending subsequences of {X}. The three shown above are not the complete set of ascending subsequences of length m=5 of our original sequence. We can rank ascending subsequences of the same length by comparing their terminal elements, and then, if necessary, the subsequent elements, working backwards. Thus for the three subsequences of length m=5 we give the ranking {S_3}< {S_2} <{S_1} because 8<10 and 7<9. The member belonging to the set of the longest ascending subsequences that has lowest rank is referred to as the Minimal Longest Ascending Subsequence (MLAS) of the sequence {X}. For any given {X} the MLAS is unique. For {X} given above, the MLAS is {S_3}. It is proposed that, for a given sequence of length N the elements of which are the packet send order, the packets that are `in order' be defined to be the MLAS for the sequence. Those packets not belonging to the MLAS are considered to be out of order. With this definition there are exactly m_{max} packets that are in order and N- m_{max} packets that are out of order. 2.1.2 The MLAS algorithm There exist well known algorithms for determining the MLAS of any given sequence. The one used presently was obtained from the website http://www.tiac.net/users/cri/mlas.html which also contains a description of the algorithm, and relevant pseudocode. The following brief description of the MLAS algorithm is derived from the above web site. [3] Suppose that we already have the MLAS for a sequence with elements x(i), i =1,...,K-1. This is always known for the first element of the sequence, for which m_{max}=1, and the MLAS consists simply of x(1) We use this, together with x(K), to obtain the MLAS for the extended sequence with elements x(i), i =1,...,K. Let t_m be the index of the terminal element of the minimal ascending of length m in the sequence x(i), i =1,...,K-1. Then the terminal element of this ascending subsequence is x(t_m). These terminal elements are ordered, so that x(t_1) x(t_{m_{max}}), then increment m_{max} by 1 and add a new ascending subsequence with t_{max}=K, else set t_{j+1}=K. Perform this procedure for K=1,...,N. In order to keep track of the MLAS, backpointers are used. Let b_l be the index of the predecessor of x(l). Each x(i) either has no predecessor (if it is a minimal ascending subsequence of length 1), in which case set b_i = -1, or it has just one predecessor. Backpointers are assigned when the algorithm passes through K=i. The output of the algorithm is m_{max} and the arrays t_m, m=1,....,m_{max} and b_q, q=1,....,N$. The reconstruction of the MLAS can be done after the basic algorithm has executed by first starting from x(t_{m_{max}}), and then following the predecessors backwards. It should be emphasized that this step is not necessary if only m_{max} is required. In addition, each minimal ascending subsequence with $m=1,..,m_{max}$ can also be found if required by the same procedure, starting from x(t_{m}). 2.1.3 Calculation of the reordering metric. The MLAS algorithm provides an approach to both the definition and solution of the packet ordering problem. For a given sequence it provides the length m_{max} of the minimal longest ascending subsequence in CPU cost order N*log(N), and with memory requirements order (N). The number of `packet moves' required to re-order the sequence is then simply N-m_{max}. This suggests that an ordering metric be defined as Q = m_{max}/N If the elements of a sequence {X} are in ascending order (all packets received in the order sent), then m_max = N and so Q = 1. If the elements of {X} are in perfect descending order (packets received in reverse order), then m_{max} = 1, and so Q = 1/N. Hence Q is bounded above by unity and below by 1/N. An alternative dedinition could be Q = log(m_{max}/N} -1 In this case perfect ascending order corresponds to Q = 0 and perfect descending order gives Q = log(1/N) -1. 3. Sampling Techniques In order to provide a consistent metric value when comparing differing levels of reordering across multiple networks, it is necessary to take certain considerations into account. These are provided below: 3.1 Sampling Parameters and Recommendations In this section, this draft provides recommendations for the following parameters: - Sequence Length. - Transmission Interval. - Packet Size. - Unique Sequence Numbers. - Overall Transmission Envelope. - Packet Protocol 3.1.1 Sequence Length It should be noted that it is possible to derive a degree of reordering in a sample sequence of any number of packets, as long as that number is greater than 0. However, the meaningfulness of the degree of reordering derived increases with the length of the sequence upon which the calculation is made. With this in mind, this draft recommends sampling as much as possible using longer packet sequences, and chooses to select a sequence length of 50 packets. Whether incremental sampling is performed, based on continual flow transmission, is optional and does not affect sequence length. However, when stating a degree of reordering it is considered to be necessary to state the sequence length of the sample sequence(s). 3.1.2 Transmission Interval Take a sequence of packets, X, transmitted by source A, in the following order: {X_A} : {1,2,3,4,5,6,7,8,9,10} The interval between transmission of each packet in {X_A} is 125 ms. After passing across a network, P, this sequence is received by destination B in the following order: {X_B} : {3,4,5,1,7,8,2,6,9,10} According to the metric defined in this draft, the sequence {X_A} has experienced a certain level of reordering, R. At the same time, another sequence of packets, Y, is transmitted by source A, in the same order: {Y_A} : {1,2,3,4,5,6,7,8,9,10} The interval between transmission of each packet in {Y_A} is 2 seconds. After passing across network P, this sequence is received by destination B in the following order: {Y_B} : {1,2,3,4,5,6,7,8,9,10} In this case, the sequence {Y_A} has experienced no reordering. Therefore, unless a transmission interval is stated it is impossible to assign a network-causal effect to reodering in given sequences of packets, and it is anticipated that this makes comparison of reordering across varying network topologies meaningless. Therefore, this draft recommends implementation of a limited set of example sequences, each of which contains a specific, stated, transmission interval in seconds. Each of this limited set of example sequences is designed to emulate the packet behaviour of a common IP application. Adherence to the recommended transmission intervals when sampling is not compulsory. However, when stating a degree of reordering it is considered necessary to state the transmission interval of the packets in the sampled sequence(s). 3.1.3 Packet Size Due to interface queuing, and other network parameters beyond the influence of the transmission devices, sequences of different packet size can experience reordering of differing magnitudes, even if all other factors are the same. With this in mind, this draft recommends implementation of a limited set of example sequences, each of which contains a specific, stated, packet size in bytes. Each of this limited set of example sequences is designed to emulate the packet behaviour of a common IP application. Adherence to the recommended packet sizes is not compulsory. However, when stating a degree of reordering of a given sequence it is considered necessary to state the packet size of the packets in the sample sequence. 3.1.4 Unique Sequence Numbers This draft recommends that unique sequence numbers are used for each packet in a sample sequence, in order that overall simplicity is maintained and that it is impossible that packets belonging to one sequence are transmitted with the same sequence as packets belonging to another sequence during two overlapping overall transmission intervals. 3.1.5 Overall Transmission Envelope In order for consistency to be achieved, this draft recommends that the value of the overall transmission envelope be not more than two seconds greater than the time taken to transmit the entire sequence according to its stated transmission interval value and its sequence length value. Adherence to the recommended overall transmission envelope is not compulsory. However, when stating a degree of reordering of a given sequence it is considered necessary to state the overall transmission envelope value, in seconds. 3.1.6 Packet Protocol This draft makes no recommendations on the protocol type used for the packets in a sample sequence as this is not perceived to have any effect on the reordering of any given packet sequence. However, this draft does recommend that, when sampling packet reordering, protocol of the sample packets used is stated in order to provide clarity and ease of comparison. 3.2 Recommended sample set. With the details and recommendations provided in section 3.1 above, this draft sets out the following flows which those carrying out sampling may or may not wish to apply in their sampling technique, and state when providing sampling results. Set Sequence Transmission Packet Overall Length Interval Size Transmission (packets) (pps) (Bytes) Envelope (s) 1 50 50 200 3.000 2 50 50 40 3.000 3 50 7 1500 8.143 4. 50 11 1500 6.545 5. 50 86 1500 3.724 6. 50 6 1500 10.333 7. 50 30 1500 3.667 8. 50 83 1500 2.602 These sample figures are intended to approximate to the following streams: 1 = G.711 VoIP 2 = G.729 VoIP 3 = appx 80Kbps streamed audio 4 = appx 128Kbps streamed video 5 = appx 1Mbps streamed video 6 = appx 9KBps TCP transfer 7 = appx 45KBps TCP transfer 8 = appx 125KBps TCP transfer 4. References [1] Bradner, S., "The Internet Standards Process -- Revision 3", RFC 2026, Internet Engineering Task Force, October 1996. [2] "On the packet ordering problem", D. Pullin, A. Corlett and R. Mandeville, CQOS Internal Document, April 2001. [3] Harter, R., "The minimal longest ascending subsequence algorithm", http://www.tiac.net/users/cri/mlas.html, and other references. 5. Authors' Addresses Sam Critchley Worldcom EMEA Network Service Joan Muyskenweg 22 1096 CJ Amsterdam The Netherlands Phone: +31 20 711 6082 Email: Sam.Critchley@wcom.com Dale Pullin Mailstop 105-50 California Institute of Technology 1200 East California Blvd. Pasadena CA 91125 Andrew Corlett CQOS Inc., 7 Technology Dr. Irvine, CA 92618 R. Mandeville CQOS Inc., 7 Technology Dr. Irvine, CA 92618 Expiration date: August, 2002