idnits 2.17.1 draft-jayasumana-reorder-density-08.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 23. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 1085. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1096. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1103. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1109. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 1 longer page, the longest (page 1) being 59 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 3 instances of too long lines in the document, the longest one being 1 character in excess of 72. ** There are 4 instances of lines with control characters in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust Copyright Line does not match the current year == Line 182 has weird spacing: '... and yet i...' == Line 183 has weird spacing: '...tage of packe...' == Line 196 has weird spacing: '...packets as re...' == Line 226 has weird spacing: '...lved in compu...' == Line 241 has weird spacing: '...quences such ...' == (14 more instances...) -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (July 10, 2007) is 6127 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'RFC2330' is mentioned on line 252, but not defined == Missing Reference: '-DT' is mentioned on line 428, but not defined == Missing Reference: 'DT' is mentioned on line 428, but not defined -- Looks like a reference, but probably isn't: '0' on line 528 == Missing Reference: 'BT' is mentioned on line 474, but not defined == Missing Reference: 'B' is mentioned on line 922, but not defined == Missing Reference: 'D' is mentioned on line 922, but not defined -- Looks like a reference, but probably isn't: '1' on line 786 == Missing Reference: '-1' is mentioned on line 787, but not defined == Missing Reference: 'RFC4737' is mentioned on line 955, but not defined == Unused Reference: 'Pi05c' is defined on line 1039, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'Ben99' -- Possible downref: Non-RFC (?) normative reference: ref. 'Jai03' -- Possible downref: Non-RFC (?) normative reference: ref. 'Pax97' -- Possible downref: Non-RFC (?) normative reference: ref. 'Boh03' -- Possible downref: Non-RFC (?) normative reference: ref. 'Bla02' -- Possible downref: Non-RFC (?) normative reference: ref. 'Lao02' -- Possible downref: Non-RFC (?) normative reference: ref. 'Bar04' -- Possible downref: Non-RFC (?) normative reference: ref. 'Ban02' -- Possible downref: Non-RFC (?) normative reference: ref. 'Pi05a' -- Possible downref: Non-RFC (?) normative reference: ref. 'Pi05b' -- Possible downref: Non-RFC (?) normative reference: ref. 'Pi07' -- Possible downref: Non-RFC (?) normative reference: ref. 'Pi06' -- Possible downref: Non-RFC (?) normative reference: ref. 'Per04' -- Possible downref: Non-RFC (?) normative reference: ref. 'Ye06' -- Possible downref: Non-RFC (?) normative reference: ref. 'Pi05c' Summary: 4 errors (**), 0 flaws (~~), 18 warnings (==), 25 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Draft Anura P. Jayasumana 2 Expiration Date: January 10, 2008 Colorado State University 3 Nischal M. Piratla 4 Deutsche Telekom Labs 5 Tarun Banka 6 Colorado State University 7 Abhijit A. Bare 8 Rick Whitner 9 Jerry McCollom 10 Agilent Technologies 11 July 10, 2007 13 Reorder Density and Reorder Buffer-occupancy Density - Metrics for 14 Packet Reordering Measurements 16 draft-jayasumana-reorder-density-08.txt 18 Status of this Memo 20 By submitting this Internet-Draft, each author represents that any 21 applicable patent or other IPR claims of which he or she is aware 22 have been or will be disclosed, and any of which he or she becomes 23 aware will be disclosed, in accordance with Section 6 of BCP 79. 25 Internet-Drafts are working documents of the Internet Engineering 26 Task Force (IETF), its areas, and its working groups. Note that 27 other groups may also distribute working documents as Internet- 28 Drafts. 30 Internet-Drafts are draft documents valid for a maximum of six months 31 and may be updated, replaced, or obsoleted by other documents at any 32 time. It is inappropriate to use Internet-Drafts as reference 33 material or to cite them other than as "work in progress." 35 The list of current Internet-Drafts can be accessed at 36 http://www.ietf.org/1id-abstracts.html 38 The list of Internet-Draft Shadow Directories can be accessed at 39 http://www.ietf.org/shadow.html 41 This Internet-Draft will expire on January 10, 2008. 43 Copyright Notice 45 Copyright (C) The IETF Trust (2007). 47 Abstract 49 This document presents two metrics for packet reordering, namely, 50 Reorder Density (RD) and Reorder Buffer-occupancy Density (RBD). A 51 threshold is used to clearly define when a packet is considered lost, 52 to bound computational complexity at O(N), and to keep the memory. 54 requirement for evaluation independent of N, where N is the length of 55 the packet sequence. RD is a comprehensive metric that captures the 56 characteristics of reordering, while RBD evaluates the sequences from 57 the point of view of recovery from reordering. These metrics are 58 simple to compute yet comprehensive in their characterization of 59 packet reordering. The measures are robust and orthogonal to packet 60 loss and duplication. 62 Table of Contents 64 1. Introduction and Motivation . . . . . . . . . . . . . . . . . 3 65 2. Attributes of Packet Reordering Metrics. . . . . . . . . . . . 4 66 3. Reorder Density and Reorder Buffer-occupancy Density . . . . . 6 67 3.1 Receive_index (RI) . . . . . . . . . . . . . . . . . . . . 8 68 3.2 Out-of-order Packet . . . . . . . . . . . . . . . . . . . . 8 69 3.3 Displacement (D) . . . . . . . . . . . . . . . . . . . . . 8 70 3.4 Displacement Threshold (DT) . . . . . . . . . . . . . . . . 9 71 3.5 Displacement Frequency (FD) . . . . . . . . . . . . . . . . 9 72 3.6 Reorder Density (RD) . . . . . . . . . . . . . . . . . . . 9 73 3.7 Expected Packet (E) . . . . . . . . . . . . . . . . . . . . 9 74 3.8 Buffer Occupancy (B) . . . . . . . . . . . . . . . . . . . 9 75 3.9 Buffer Occupancy Threshold (BT) . . . . . . . . . . . . . . 10 76 3.10 Buffer Occupancy Frequency (FB) . . . . . . . . . . . . . . 10 77 3.11 Reorder Buffer-Occupancy Density (RBD) . . . . . . . . . . 10 78 4. Representation of Packet Reordering and Reorder Density . . . 10 79 5. Selection of DT . . . . . . . . . . . . . . . . . . . . . . . 11 80 6. Detection of Lost and Duplicate Packets . . . . . . . . . . . 12 81 7. Algorithms to Compute RD and RBD . . . . . . . . . . . . . . . 13 82 7.1 RD Algorithm . . . . . . . . . . . . . . . . . . . . . . . 13 83 7.2 RBD Algorithm . . . . . . . . . . . . . . . . . . . . . . . 15 84 8. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 85 9. Characteristics Derivable from RD and RBD. . . . . . . . . . . 19 86 10. Comparison with Other Metrics . . . . . . . . . . . . . . . . 20 87 11. Security Considerations . . . . . . . . . . . . . . . . . . . 20 88 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 89 13. Normative References . . . . . . . . . . . . . . . . . . . . . 20 90 14. Author's Address . . . . . . . . . . . . . . . . . . . . . . . 22 91 Full Copyright Statement . . . . . . . . . . . . . . . . . . . . . 23 92 Intellectual Property . . . . . . . . . . . . . . . . . . . . . . 23 94 1. Introduction and Motivation 96 Packet reordering is a phenomena that occurs in Internet Protocol 97 (IP) networks. Major causes of packet reordering include, but are 98 not limited to, packet striping at layers 2 and 3 [Ben99,Jai03], 99 priority scheduling (e.g., Diffserv), and route fluttering 100 [Pax97,Boh03]. Reordering leads to degradation of the performance of 101 many applications [Ben99,Bla02,Lao02]. Increased link speeds[Bar04], 102 increased parallelism within routers and switches, QoS support, and 103 load balancing among links all point to increased packet reordering 104 in future networks. 106 Effective metrics for reordering are required to measure and quantify 107 reordering. A good metric or a set of metrics capturing the nature of 108 reordering can be expected to provide insight into the reordering 109 phenomenon in networks. It may be possible to use such metrics to 110 predict the effects of reordering on applications that are sensitive 111 to packet reorder, and perhaps even to compensate for reordering. A 112 metric for reordered packets, may also help evaluate network 113 protocols and implementations with respect to their impact on packet 114 reordering. 116 The percentage of out-of-order packets is often used as a metric for 117 characterizing reordering. However, this metric is vague and lacks 118 in detail. Further, there is no uniform definition for the degree of 119 reordering of an arrived packet [Ban02,Pi05a]. For example, consider 120 the two packet sequences (1, 3, 4, 2, 5) and (1, 4, 3, 2, 5). It is 121 possible to interpret the reordering of packets in these sequences 122 differently. For example, 124 (i) Packets 2, 3 and 4 are out-of-order in both cases. 125 (ii) Only packet 2 is out-of-order in the first sequence, while 126 packets 2 and 3 are out-of-order in the second. 127 (iii)Packets 3 and 4 are out-of-order in both the sequences. 128 (iv) Packets 2, 3 and 4 are out-of-order in the first sequence, 129 while packets 4 and 2 are out-of-order in the second sequence. 131 In essence, the percentage of out-of-order packets as a metric of 132 reordering is subject to interpretation and cannot capture the 133 reordering unambiguously and hence, accurately. 135 Other metrics attempt to overcome this ambiguity by defining only the 136 late packets or only the early packets as being reordered. However, 137 measuring reordering based only on late or only on early packets is 138 not always effective. Consider, for example the sequence (1, 20, 2, 139 3,..,19, 21, 22, ...); the only anomaly is that packet 20 is 140 delivered immediately after packet 1. A metric based only on 141 lateness will indicate a high degree of reordering, even though in 142 this example it is a single packet arriving ahead of others. 143 Similarly, a metric based only on earliness does not accurately 144 capture reordering caused by a late arriving packet. A complete 145 reorder metric must account for both earliness and lateness, and must 146 be able to differentiate between the two. The inability to capture 147 both the earliness and the lateness precludes a metric from being 148 useful for estimating end-to-end reordering based on reordering in 149 constituent subnets. 151 The sensitivity to packet reordering can vary significantly from one 152 application to the other. Consider again the packet sequence (1, 3, 153 4, 2, 5). If buffers are available to store packets 3 and 4 while 154 waiting for packet 2, an application can recover from reordering. 155 However, with certain real-time applications, the arrival of packet 2 156 out of order may render it useless. While one can argue that a good 157 packet reordering measurement scheme should capture 158 application-specific effects, a counter argument can also be made 159 that packet reordering should be measured strictly with respect to 160 the order of delivery independent of the application. 162 2. Attributes of Packet Reordering Metrics 164 The first and foremost requirement of a packet reorder metric is its 165 ability to capture the amount and extent of reordering in a sequence 166 of packets. The fact that a measure varies with reordering of packets 167 in a stream does not make it a good metric. In [Ben99], authors have 168 provided desirable features of a reordering metric. This list encloses 169 the foremost requirement stated above, simplicity, low sensitivity to 170 packet loss, ability to combine reorder measures from two networks, 171 minimal value for in-order data, and independence to data size. These 172 features are explained below in detail, along with additional desired 173 features. Note, the ability to combine reorder measures from two 174 networks is added to broader applicability and data size independence 175 is discussed under evaluation complexity. However, data size 176 independence could also refer to the final measure, as in percentage 177 reordering oR even a normalized representation. 179 a) Simplicity 181 An ideal metric is one that is simple to understand and evaluate, 182 and yet informative, i.e., able to provide a complete picture of 183 reordering. Percentage of packets reordered is the simplest 184 singleton metric; But the ambiguity in its definition as discussed 185 earlier, and its failure to carry the extent of reordering make it 186 less informative. On the other hand, keeping track of the 187 displacements of each and every packet without compressing the 188 data will contain all the information about reordering, but it is 189 not simple to evaluate or use. 191 A simpler metric may be preferred in some cases even though it 192 does not capture reordering completely, while other cases may 193 demand more complex, yet complete metric. 195 In striving to strike a balance, the lateness based metrics 196 consider only the late packets as reordered, and earliness based 197 metrics only the early packets as reordered. A metric based only 198 on earliness or only on lateness however captures only a part of 199 information associated with reordering. A metric capturing both 200 early and late arrivals in contrast provides a complete picture of 201 reordering in a sequence. 203 b) Low Sensitivity to Packet Loss and Duplication 205 A reorder metric should treat only an out-of-order packet as 206 reordered, i.e., if a packet is lost during transit then this 207 should not result in its following packets, which arrive in order, 208 to be classified as out of order. Consider the sequence (1, 3, 4, 209 5, 6). If packet 2 has been lost, the sequence should not be 210 considered to contain any out-of-order packets. Similarly, if 211 multiple copies of a packet (duplicates) are delivered, this must 212 not result in a packet being classified as out of order, as long 213 as one copy arrives in the proper position. For example, sequence 214 (1, 2, 3, 2, 4, 5) has no reordering. The lost and duplicate 215 packet counts may be tracked using metrics specifically to measure 216 those, e.g., percentage of lost packets, and percentage of 217 duplicate packets. 219 c) Low evaluation complexity 221 Memory and time complexities associated with evaluating a metric 222 play a vital role in implementation and real-time measurements. 223 Spatial/memory complexity corresponds to the amount of buffers 224 required for the overall measurement process, whereas 225 time/computation complexity refers to the number of computation 226 steps involved in computing the amount of reordering in 227 a sequence. On-the-fly evaluation of the metric for large streams 228 of packets requires the computational complexity to be O(N), where 229 N denotes the number of received packets, used for reordering 230 measure. This allows the metric to be updated in constant-time as 231 each packet arrives. In the absence of a threshold defining losses 232 or the number of sequence numbers to buffer for detection of 233 duplicates, the worst-case complexity of loss and duplication 234 detection will increase with N. The rate of increase will depend 235 among other things on the value of N and the implementation of 236 duplicate detection scheme. 238 d) Robustness 240 Reorder measurement should be robust against different network 241 phenomena and peculiarities in measurement or sequences such as a 242 very late arrival of a duplicate packet, or even a rogue packet 243 due to an error or sequence number wrap-around. The impact due to 244 an event associated with a single or a small number of packets 245 should have a sense of proportionality on the reorder measure. 246 Consider for example, the arrival sequence: (1, 5430, 2, 3, 4, 247 5,..) where packet 5430 appears to be very early; it may be either 248 due to sequence rollover in test streams or some unknown reason. 250 e) Broad applicability 252 A framework for IP performance metrics [RFC2330] states: "The 253 metrics must aid users and providers in understanding the 254 performance they experience or provide." 256 Rather than being a mere value or a set of values that changes 257 with the reordering of packets in a stream, a reorder metric 258 should be useful for a variety of purposes. An application or a 259 transport protocol implementation, for example, may be able to use 260 the reordering information to allocate resources to recover from 261 reordering. A metric may be useful for TCP flow control, buffer 262 resource allocation for recovery from reordering and /or network 263 diagnosis. 265 The ability to combine the reorder metrics of constituent subnets 266 to provide the end to end reordering would be an extremely useful 267 property. In the absence of this property, no amount of individual 268 network measurements short of measuring the reordering for the 269 pair of endpoints of interest would be useful in predicting the 270 end-to-end reordering. 272 The ability to provide different types of information based on 273 monitoring or diagnostic needs also broadens the applicability of 274 a metric. Examples of applicable information for reordering may 275 include parameters such as the percentage of reordered packets that 276 resulted in fast retransmissions in TCP, or the percentage of 277 utilization of reorder recovery buffer. 279 3. Reorder Density and Reorder Buffer-occupancy Density 281 In this memo, we define two discrete density functions, Reorder 282 Density (RD) and Reorder Buffer-occupancy Density (RBD), that capture 283 the nature of reordering in a packet stream. These two metrics can 284 be used individually or collectively to characterize the reordering 285 in a packet stream. Also presented are algorithms for real-time 286 evaluation of these metrics for an incoming packet stream. 288 RD is defined as the distribution of displacements of packets from 289 their original positions, normalized with respect to the number of 290 packets. An early packet corresponds to a negative displacement and 291 a late packet to a positive displacement. A threshold on displacement 292 is used to keep the computation within bounds. Choice of such a 293 threshold is important to the needs of measurement and is further 294 discussed in Section 5. In other terms, if user Duplicate packets 295 are accounted for when evaluating these displacements. 297 The ability of RD to capture the nature and properties of reordering 298 in a comprehensive manner has been demonstrated in [Pi05a, Pi05b, 299 Pi05c,Pi07]. The RD observed at the output port of a subnet when the 300 input is an in-order packet stream, can be viewed as a "reorder 301 response" of a network, a concept somewhat similar to the "system 302 response" or "impulse response" used in traditional system theory. 303 For a subnet under stationary conditions, RD is the probability 304 density of the packet displacement. RD measured on individual 305 subnets can be combined, using the convolution operation, to 306 predict the end-to-end reorder characteristics of the network formed 307 by the cascade of subnets under a fairly broad set of conditions 308 [Pi05b]. RD also shows significant promise as a tool for analytical 309 modeling of reordering, as demonstrated with a load-balancing 310 scenario in [Pi06]. Use of a threshold to define the condition under 311 which a packet is considered lost, makes the metric robust, efficient 312 and adaptable for different network and stream characteristics. 314 RBD is the normalized histogram of the occupancy of a hypothetical 315 buffer that would allow the recovery from out-of-order delivery of 316 packets. If an arriving packet is early, it is added to a 317 hypothetical buffer until it can be released in order [Ban02]. The 318 occupancy of this buffer after each arrival is used as the measure of 319 reordering. A threshold, used to declare a packet as lost, keeps the 320 complexity of computation within bounds. The threshold may be 321 selected based on application requirements in situations where the 322 late arrival of a packet makes it useless, e.g., a real-time 323 applications. In [Ban02], this metric was called RD and buffer 324 occupancy was known as displacement. 326 RD and RBD are simple, yet useful, metrics that for measurement and 327 evaluation of reordering. These metrics are robust against many 328 peculiarities, such as those discussed previously, and have a 329 computational complexity of O(N), where N is the received sequence 330 size. RD is orthogonal to loss and duplication, whereas RBD is 331 orthogonal to duplication. 333 A detailed comparison of these and other proposed metrics for 334 reordering is presented in [Pi07]. 336 The following terms are used to formally define RD, RBD, and the 337 measurement algorithms. Wraparound of sequence numbers is not 338 explicitly addressed in this document, but with the use of modulo-N 339 arithmetic, all claims made here remain valid in the presence of 340 wraparound. 342 3.1 Receive_index (RI) 344 Consider a sequence of packets (1, 2, ..., N) transmitted over a 345 network. A receive_index RI (1, 2, ...), is a value assigned 346 to a packet as it arrives at its destination according to the order 347 of arrival. A receive_index is not assigned to duplicate packets, 348 and the receive_index value skips the value corresponding to a lost 349 packet. (The detection of loss and duplication for this purpose is 350 described in section 6.) In the absence of reordering, the sequence 351 number of the packet and the receive_index are the same for each 352 packet. 354 RI is used to compute earliness and lateness of an arriving packet. 355 Below are two examples of received sequences with receive_index 356 values for a sequence of 5 packets (1, 2, 3, 4, 5) arriving out of 357 order: 359 Example 1: 360 Arrived sequence: 2 1 4 5 3 361 Receive_index: 1 2 3 4 5 363 Example 2: 364 Arrived sequence: 1 4 3 5 3 365 Receive_index: 1 3 4 5 - 367 In Example 1, there is no loss or duplication. In Example 2, the 368 packet with sequence number 2 is lost, thus 2 is not assigned as an 369 RI; packet 3 is duplicated, thus the second copy is not assigned an 370 RI. 372 3.2 Out-of-Order Packet 374 When the sequence number of a packet is not equal to the RI assigned 375 to it, it is considered an out-of-order packet. Duplicates for which 376 an RI is not defined are ignored. 378 3.3 Displacement (D) 380 Displacement (D) of a packet is defined as the difference between RI 381 and the sequence number of the packet, i.e., the displacement of 382 packet i is RI[i] - i. Thus, a negative displacement indicates the 383 earliness of a packet and a positive displacement to the lateness. 384 In example 3 below, an arrived sequence with displacements of each 385 packet is illustrated. 387 Example 3: 388 Arrived sequence: 1 4 3 5 3 8 7 6 389 Receive_index: 1 3 4 5 - 6 7 8 390 Displacement: 0 -1 1 0 - -2 0 2 392 3.4 Displacement Threshold (DT) 394 The displacement threshold is a threshold on the displacement of 395 packets that allows the metric to classify a packet as lost or 396 duplicate. Determining when to classify a packet as lost is 397 difficult because there is no point in time at which a packet can 398 definitely be classified as lost; the packet may still arrive after 399 some arbitrarily long delay. However, from a practical point of 400 view, a packet may be classified as lost if it has not arrived within 401 a certain administratively defined displacement threshold, DT. 402 Similarly, to identify a duplicate packet, it is theoretically 403 necessary to keep track of all the arrived (or missing) packets. 404 Again, however, from a practical point of view, missing packets 405 within a certain window of sequence numbers suffice. Thus, DT is 406 used as a practical means for declaring a packet as lost or 407 duplicated. DT makes the metric more robust, keeps the 408 computational complexity for long sequences within O(N), and keeps 409 storage requirements independent of N. 411 If DT is selected too small, reordered packets might be classified as 412 lost. A large DT will increase both the size of memory required to 413 keep track of sequence numbers and the length of computation time 414 required to evaluate the metric. Indeed, it is possible to use two 415 different thresholds for the two cases. The selection of DT is 416 further discussed in section 5. 418 3.5 Displacement Frequency (FD) 420 Displacement Frequency FD[k] is the number of arrived packets having 421 a displacement of k, where k takes values from -DT to DT. 423 3.6 Reorder Density (RD) 425 RD is defined as the distribution of the Displacement Frequencies 426 FD[k], normalized with respect to N', where N'is the length of the 427 received sequence, ignoring lost and duplicate packets. N' is equal 428 to the sum(FD[k]) for k in [-DT, DT]. 430 3.7 Expected Packet (E) 432 A packet with sequence number E is expected if E is the largest 433 number such that all the packets with sequence numbers less than E 434 have already arrived or have been determined to be lost. 436 3.8 Buffer Occupancy (B) 438 An arrived packet with a sequence number greater than that of an 439 expected packet is considered to be stored in a hypothetical buffer 440 sufficiently long to permit recovery from reordering. At any packet 441 arrival instant, the buffer occupancy is equal to the number of 442 out-of-order packets in the buffer, including the newly arrived 443 packet. One buffer location is assumed for each packet, although it 444 is possible to extend the concept to the case where the number of 445 bytes is used for buffer occupancy. For example, consider the 446 sequence of packets (1, 2, 4, 5, 3) with expected order (1, 2, 3, 4, 447 5). When packet 4 arrives the buffer occupancy is 1 because packet 4 448 arrived early. Similarly, the buffer occupancy becomes 2 when packet 449 5 arrives. When packet 3 arrives, recovery from reordering occurs 450 and the buffer occupancy reduces to zero. 452 3.9 Buffer Occupancy Threshold (BT) 454 Buffer occupancy threshold is a threshold on the maximum size of the 455 hypothetical buffer that is used for recovery from reordering. As 456 with the case of DT for RD, BT is used for loss and duplication 457 classification for Reorder Buffer-occupancy Density (RBD) computation 458 (see section 3.11). BT provides robustness, and limits the 459 computation complexity of RBD. 461 3.10 Buffer Occupancy Frequency (FB) 463 At the arrival of each packet the buffer occupancy may take any value 464 k ranging from 0 to BT. The buffer occupancy frequency FB[k] is the 465 number of arrival instances after which the occupancy takes the value 466 of k. 468 3.11 Reorder Buffer-Occupancy Density (RBD) 470 Reorder buffer-occupancy density is the buffer occupancy frequencies 471 normalized by the total number of non-duplicate packets, i.e., 472 RBD[k] = FB[k]/N' where N' is the length of the received sequence, 473 ignoring excessively delayed (deemed lost) and duplicate packets. N' 474 is also the sum(FB[k]) for all k such that k belongs to [0, BT]. 476 4. Representation of Packet Reordering and Reorder Density 478 Consider a sequence of packets (1, 2, ..., N). Let the RI assigned 479 to packet m be "the sequence number m plus an offset dm," i.e., 481 RI = m + dm 482 D = dm 484 A reorder event of packet m is represented by r(m, dm). 485 When dm is not equal to zero, a reorder event is said to have 486 occurred. A packet is late if dm > 0 and early if dm < 0. 487 Thus, packet reordering of a sequence of packets is completely 488 represented by the union of reorder events, R, referred to as the 489 reorder set: 490 R = {r(m,dm)| dm not equal to 0 for all m} 492 If there is no reordering in a packet sequence then R is the null 493 set. 495 Examples 4 and 5 illustrate the reorder set: 497 Example 4. No losses or duplicates 499 Arrived Sequence 1 2 3 5 4 6 500 Receive_index (RI) 1 2 3 4 5 6 501 Displacement (D) 0 0 0 -1 1 0 502 R = {(4,1), (5,-1)} 504 Example 5. Packet 4 is lost and 2 is duplicated 506 Arrived Sequence 1 2 5 3 6 2 507 Receive_index (RI) 1 2 3 5 6 - 508 Displacement (D) 0 0 -2 2 0 - 509 R = {(3, 2), (5, -2)} 511 RD is defined as the discrete density of the frequency of packets 512 with respect to their displacements, i.e., the lateness and earliness 513 from the original position. Let S[k] denote the set of reorder 514 events in R with displacement equal to k, i.e., 516 S[k]= {r(m, dm)| dm = k} 518 Let |S[k]| be the cardinality of set S[k]. Thus, RD[k] is defined as 519 |S[k]| normalized with respect to the total number of received 520 packets (N'). Note that N' does not include duplicates or lost 521 packets. 523 RD[k] = |S[k]| / N' for k not equal to zero. 525 RD[0] corresponds to the packets for which RI is the same as the 526 sequence number: 528 RD[0] = 1 - sum(|S[k]| / N') 530 As defined previously, FD[k] is the measure that keeps track of 531 |S[k]|. 533 5. Selection of DT 535 Although assigning a threshold for determining lost and duplicate 536 packets might appear to introduce error into the reorder metrics, in 537 practice this need not be the case. Applications, protocols, and the 538 network itself operate within finite resource constraints which 539 introduce practical limits beyond which the choice of certain values 540 become irrelevant. If the operational nature of an application 541 is such that a DT can be defined, then using DT in the computation of 542 reorder metrics will not invalidate nor limit the effectiveness of the 543 metrics, i.e., increasing DT does not provide any benefit. In the 544 case of TCP, the maximum transmit and receive window sizes impose a 545 natural limit on the useful value of DT. Sequence number wraparound 546 may provide a useful upper bound for DT in some instances. 548 If there are no operational constraints imposed by factors as 549 described above, or if one is purely interested in a more complete 550 picture of reordering, then DT can be made as large as required. If 551 DT is equal to the length of the packet sequence (worst case 552 scenario), a complete picture of reordering is seen. Any metric that 553 does not rely on a threshold to declare a packet as lost, implicitly 554 makes one of two assumptions: a) A missing packet is not considered 555 lost until the end of the sequence, or b) the packet is considered 556 lost until it arrives. Former corresponds to the case where DT is 557 set to the length of the sequence. Latter leads to many problems 558 related to complexity and robustness. 560 6. Detection of Lost and Duplicate Packets 562 In RD, a packet is considered lost if it is late beyond DT. 563 Non-duplicate arriving packets do not have a copy in the buffer and 564 do not have a sequence number less (earlier) than E. In RBD, a 565 packet is considered lost if the buffer is filled to its threshold 566 BT. A packet is considered a duplicate when the sequence number is 567 less than the expected packet, or if the sequence number is already 568 in the buffer. 570 Since RI skips the sequence number of a lost packet, the question 571 arises as to how to assign an RI to subsequent packets that arrive 572 before it is known that the packet is lost. This problem arises only 573 when reorder metrics are calculated in real-time for an incoming 574 sequence, and not with offline computations. This concern can be 575 handled in one of two ways: 577 a) Go-back Method: RD is computed as packets arrive. When a packet 578 is deemed lost, RI values are corrected and displacements recomputed. 579 The Go-back Method is only invoked when a packet is lost, and 580 re-computing involves at most DT packets. 582 b) Stay-back Method: RD evaluation lags the arriving packets so that 583 the correct RI and E values can be assigned to each packet as it 584 arrives. Here, RI is assigned to a packet only once, and the value 585 assigned is guaranteed to be correct. In the worst case, the 586 computation lags arriving packet by DT. The lag associated with the 587 Stay-back Method is incurred only when a packet is missing. 589 Another issue related to a metric and its implementation is the 590 robustness against peculiarities that may occur in a sequence as 591 discussed in Section 2. Consider for example, the arrival sequence: 592 (1, 5430, 2, 3, 4, 5,...). With RD, a sense of proportionality is 593 maintained easily using the concept of threshold (DT) and to limit 594 the effect of a rogue packet to this threshold. With RD, for 595 example, as its displacement is greater than threshold, it is 596 discarded. This way the impact due to the rogue packet, 5430, is 597 limited at most to DT packets, thus imposing a limit on the amount of 598 error it can cause in results. Note also that a threshold different 599 from DT can be used for this purpose. By limiting the time a packet 600 to remain in the buffer according to a prespecified threshold, RBD 601 can be made robust against rogue packets as well. 603 7. Algorithms to evaluate RD and RBD 605 The algorithms to compute RD and RBD are given below. These 606 algorithms are applicable for on-line computation of an incoming 607 packet stream, and provide an up-to-date metric for the packet stream 608 so far. For simplicity, the sequence numbers are considered to start 609 from 1 and continue in increments of 1. Only the Stay-back Method of 610 loss detection is presented here, hence the RD values lag by a 611 maximum of DT. Algorithm for go-back method is given in [Bar04]. Perl 612 scripts for these algorithms are posted in [Per04]. 614 7.1 Algorithm for RD 616 Variables used: 617 ------------------------------------------------------------------- 618 RI: receive_index. 619 S: Arrival under consideration for lateness/earliness computation. 620 D: Lateness or earliness of the packet being processed: dm for m. 621 FD[ -DT..DT]: Frequency of lateness and earliness. 622 window[1..DT+1]: List of incoming sequence numbers; FIFO buffer. 623 buffer[1..DT]: Array to hold sequence numbers of early arrivals. 624 window[] and buffer[] are empty at the beginning. 625 =================================================================== 627 Step 1. Initialize: 629 Store first unique DT+1 sequence numbers in arriving order into 630 window; 631 RI = 1; 633 Step 2. Repeat (until window is empty): 635 If (window or buffer contains sequence number RI) 636 { 637 Move sequence number out of window to S # window is FIFO 638 D = RI - S; # compute displacement 639 If (absolute(D) <= DT) # Apply threshold 640 { 641 FD[D]++; # Update frequency 643 If (buffer contains sequence number RI) 644 Delete RI from buffer; 646 If (D < 0) # Early Arrival 647 add S to empty slot in buffer; 648 RI++; # Update RI value 649 } 651 Else # Displacement beyond threshold. 652 { 653 Discard S; 654 # Note, an early arrival in window is moved to buffer if 655 # its displacement is less or equal to DT. Therefore, the 656 # contents in buffer will have only possible RIs. Thus, 657 # clearing an RI as it is consumed prevents memory leaks 658 # in buffer 659 } 660 # Get next incoming non-duplicate sequence number, if any. 661 newS = get_next_arrival(); # subroutine called* 662 if (newS != null) 663 { 664 add newS to window; 665 } 666 if (window is empty) go to step 3; 667 } 668 Else # RI not found. Get next RI value. 669 { 670 # Next RI is the minimum among window and buffer contents. 671 m = minimum (minimum (window), minimum (buffer)); 672 If (RI < m) 673 RI = m; 674 Else 675 RI++; 676 } 678 Step 3. Normalize FD to get RD; 680 # Get a new sequence number from packet stream, if any 681 subroutine get_next_arrival() 682 { 683 do # get non-duplicate next arrival 684 { 685 newS = new sequence from arriving stream; 686 if (newS == null) # End of packet stream 687 return null; 688 } while (newS < RI or newS in buffer or newS in window); 690 return newS; 691 } 693 7.2 RBD Algorithm 695 Variables used: 696 --------------------------------------------------------------------- 697 # E : Next expected sequence number. 698 # S : Sequence number of the packet just arrived. 699 # B : Current buffer occupancy. 700 # BT: Buffer Occupancy threshold. 701 # FB[i]: Frequency of buffer occupancy i (0 <= i <= BT). 702 # in_buffer(N) : True if the packet with sequence number N is 703 already stored in the buffer. 704 ===================================================================== 706 1. Initialize E = 1, B = 0 and FB[i] = 0 for all values of i. 708 2. Do the following for each arrived packet. 710 If (in_buffer(S) || S < E) /*Do nothing*/; 711 /* Case a: S is a duplicate or excessively delayed packet. 712 Discard the packet.*/ 713 Else 714 { 716 If (S == E) 717 /* Case b: Expected packet has arrived.*/ 718 { 719 E = E + 1; 720 While (in_buffer(E)) 721 { 722 B = B - 1; /* Free buffer occupied by E.*/ 723 E = E + 1; /* Expect next packet.*/ 724 } 725 FB[B] = FB[B] + 1; /*Update frequency for buffer 726 occupancy B.*/ 727 } /* End of ElseIf (S == E)*/ 729 ElseIf (S > E) 730 /* Case c: Arrived packet has a sequence number higher 731 than expected.*/ 732 { 733 If (B < BT) 734 /* Store the arrived packet in a buffer.*/ 735 B = B + 1; 736 Else 737 /* Expected packet is delayed beyond the BT. 738 Treat it as lost.*/ 739 { 740 Repeat 741 { 742 E = E + 1; 743 } 744 Until (in_buffer(E) || E == S); 746 While (in_buffer(E) || E == S) 747 { 748 if (E != S) B = B - 1; 749 E = E + 1; 750 } 751 } 752 FB[B] = FB[B] + 1; /*Update frequency for buffer 753 occupancy B.*/ 754 } /* End of ElseIf (S > E)*/ 756 } 758 3. Normalize FB[i] to obtain RBD[i], for all values of i using 760 FB[i] 761 RBD[i] = ---------------------------------- 762 Sum(FB[j] for 0 <= j <= BT) 764 8. Examples 766 a. Scenario with no packet loss 768 Consider the sequence of packets (1, 4, 2, 5, 3, 6, 7, 8) with 769 DT = BT = 4. 771 Tables 1 and 2 show the computational steps when the RD algorithm is 772 applied to the above sequence. 774 ------------------------------------------------------ 775 Table 1: Late/Early-packet Frequency computation steps 776 ------------------------------------------------------ 777 S 1 4 2 5 3 6 7 8 778 RI 1 2 3 4 5 6 7 8 779 D 0 -2 1 -1 2 0 0 0 780 FD[D] 1 1 1 1 1 2 3 4 781 ------------------------------------------------------ 782 (S, RI,D and FD[D] as described in section 7.1) 783 ------------------------------------------------------ 785 The last row (FD[D]) represents the current frequency of occurrence 786 of the displacement D, e.g., column 3 indicates FD[1] = 1 while 787 column 4 indicates FD[-1] = 1. The final set of values for RD are 788 shown in Table 2. 790 ------------------------------------------------- 791 Table 2: Reorder Density (RD) 792 ------------------------------------------------- 793 D -2 -1 0 1 2 794 FD[D] 1 1 4 1 1 795 RD[D] 0.125 0.125 0.5 0.125 0.125 796 ------------------------------------------------- 797 (D,FD[D] and RD[D] as described in section 7.1) 798 ------------------------------------------------- 800 Tables 3 and 4 illustrate the computational steps for RBD for the 801 same example. 803 ------------------------------------------------------------ 804 Table 3: Buffer occupancy frequencies (FB) computation steps 805 ------------------------------------------------------------ 806 S 1 4 2 5 3 6 7 8 807 E 1 2 2 3 3 6 7 8 808 B 0 1 1 2 0 0 0 0 809 FB[B] 1 1 2 1 2 3 4 5 810 ------------------------------------------------------------ 811 (E,S,B and FB[B] as described in section 7.2) 812 ------------------------------------------------------------ 814 ------------------------------------------------------------------ 815 Table 4: Reorder Buffer-occupancy Density 816 ------------------------------------------------------------------ 817 B 0 1 2 818 FB[B] 5 2 1 819 RBD[B] 0.625 0.25 0.125 820 ----------------------------------------------------------------- 821 (B,FB[B] and RBD[B] as discussed in section 7.2) 822 ------------------------------------------------------------------ 824 Graphical representations of the densities are as follows: 826 ^ ^ 827 | | 828 | _ 829 ^ 0.5 _ ^ 0.625 | | 830 | | | | | | 831 | | | | 832 RD[D] | | RBD[B] | | - o.25 833 _ _ | | _ _ 0.125 | || | - 0.125 834 | || || || || | | || || | 835 --+--+--+--+--+--+--> ---+--+--+-- 836 -2 -1 0 1 2 0 1 2 837 D --> B --> 839 b. Scenario with packet loss 841 Consider a sequence of 6 packets (1, 2, 4, 5, 6, 7) with DT = BT = 3. 842 Table 5 shows the computational steps when the RD algorithm is 843 applied to the above sequence to obtain FD[D]. 845 ------------------------------------------------------ 846 Table 5: Late/Early-packet Frequency computation steps 847 ------------------------------------------------------ 848 S 1 2 4 5 6 7 849 RI 1 2 4 5 6 7 850 D 0 0 0 0 0 0 851 FD[D] 1 2 3 4 5 6 852 ------------------------------------------------------ 853 (S,RI,D and FD[D] as described in section 7.1) 854 ------------------------------------------------------ 856 Table 6 illustrates the FB[B] for the above arrival sequence. 858 ------------------------------------------------- 859 Table 6: Buffer occupancy computation steps 860 ------------------------------------------------- 861 S 1 2 4 5 6 7 862 E 1 2 3 3 3 7 863 B 0 0 1 2 3 0 864 FB[B] 1 2 1 1 1 3 865 ------------------------------------------------- 866 (E,S,B and FB[B] as described in section 7.2) 867 ------------------------------------------------- 869 Graphical representations of RD and RBD for the above sequence are as 870 follows. 872 ^ ^ 873 | | 874 1.0 _ | 875 ^ | | ^ | 876 | | | | 0.5 _ 877 | | | | 878 RD[D] | | RBD[B] | | _ _ _ 0.167 879 | | | || || || | 880 --+--+--+--> --+--+--+--+--> 881 -1 0 1 0 1 2 3 882 D --> B --> 884 c. Scenario with duplicate packets 886 Consider a sequence of 6 packets (1, 3, 2, 3, 4, 5) with DT = 2. 887 Tables 7 shows the computational steps when the RD algorithm is 888 applied to the above sequence to obtain FD[D]. 890 ------------------------------------------------------ 891 Table 7: Late/Early-packet Frequency computation steps 892 ------------------------------------------------------ 893 S 1 3 2 3 4 5 894 RI 1 2 3 - 4 5 895 D 0 -1 1 - 0 0 896 FD[D] 1 1 1 - 2 3 897 ------------------------------------------------------ 898 (S, RI,D and FD[D] as described in section 7.1) 899 ------------------------------------------------------ 901 Table 8 illustrates the FB[B] for the above arrival sequence. 903 ------------------------------------------------------ 904 Table 8: Buffer Occupancy Frequency computation steps 905 ------------------------------------------------------ 906 S 1 3 2 3 4 5 907 E 1 2 2 - 4 5 908 B 0 1 0 - 0 0 909 FB[B] 1 1 2 - 3 4 910 ------------------------------------------------------ 911 (E,S,B and FB[B] as described in section 7.2) 912 ------------------------------------------------------ 914 Graphical representations of RD and RBD for the above sequence 915 are as follows: 917 ^ ^ 918 | | 919 ^ | ^ 0.8 _ 920 | 0.6 _ | | | 921 | | | | 922 RD[D] | | RBD[B] | | 923 0.2 _ | | _ 0.2 | | _ 0.2 924 | || || | | || | 925 --+--+--+--+--+--+--> ---+--+--+-- 926 -2 -1 0 1 2 0 1 2 927 D --> B --> 929 9. Characteristics Derivable from RD and RBD 931 Additional information may be extracted from RD and RBD depending on 932 the specific applications. For example, in case resource allocation 933 at a node to recover from reordering, the mean and variance of buffer 934 occupancy can be derived from RBD. For example, 936 Mean occupancy of recovery buffer = sum(i*RBD[i] for 0 <= i <= BT) 937 The basic definition of RBD may be modified to count the buffer 938 occupancy in bytes as opposed to packets when the actual buffer space 939 is more important. Another alternative is to use time to update the 940 buffer occupancy compared to updating it at every arrival instant. 942 The parameters that can be extracted from RD include the percentage 943 of late (or early) packets, mean displacement of packets and mean 944 displacement of late (or early) packets[Ye06]. For example, the 945 fraction of packets that arrive after three or more of their 946 successors according to the order of transmission is given by 947 Sum [RD[i] for 3<=i<=DT] RD also allows for extraction of parameters 948 such as entropy of the reordered sequence, a measure of disorder in 949 the sequence [Ye06]. Due to the probability mass function nature of 950 RD, it is also a convenient measure for theoretical modeling and 951 analysis of reordering, e.g., see [Pi06]. 953 10. Comparison with Other Metrics 955 RD and RBD are compared to other metrics of [RFC4737] in [Pi07]. 957 11. Security Considerations 959 This security considerations listed in RFC 4737, RFC 3763, RFC 4656 960 are extensive and directly applicable to the usage of these metrics, 961 thus should be consulted for additional details. 963 12. IANA Considerations 965 This document requires nothing from the IANA. 967 13. References 969 [Ben99] J. C. R. Bennett, C. Partridge and N. Shectman, "Packet 970 Reordering is Not Pathological Network Behavior," IEEE/ACM 971 Trans. on Networking , Dec. 1999, pp.789-798. 973 [Jai03] S. Jaiswal, G. Iannaccone, C. Diot, J. Kurose and D. 974 Towsley, "Measurement and Classification of Out-of-sequence 975 Packets in Tier-1 IP Backbone," Proc. IEEE INFOCOM, Mar. 976 2003, pp. 1199-1209. 978 [Pax97] V.Paxson, "Measurements and Analysis of End-to-End Internet 979 Dynamics," Ph.D. Dissertation, U.C. Berkeley, 1997, 980 ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz. 982 [Boh03] S. Bohacek, J. Hespanha, J. Lee, C. Lim and K.Obraczka, 983 "TCP-PR: TCP for Persistent Packet Reordering," Proc. of 984 the IEEE 23rdICDCS, May 2003, pp.222-231. 986 [Bla02] E. Blanton and M. Allman, "On Making TCP More Robust to 987 Packet Reordering," ACM Computer Comm. Review, 32(1), Jan. 988 2002, pp.20-30. 990 [Lao02] M. Laor and L. Gendel, "The Effect of Packet Reordering 991 in a Backbone Link on Application Throughput," IEEE 992 Network, Sep./Oct. 2002, pp.28-36. 994 [Bar04] A. A. Bare, "Measurement and Analysis of Packet Reordering 995 Using Reorder Density," Masters Thesis, Department of 996 Computer Science, Colorado State University, Fort Collins, 997 Colorado, Fall 2004. 999 [Ban02] T. Banka, A. A. Bare, A. P. Jayasumana, "Metrics for Degree 1000 of Reordering in Packet Sequences", Proc. 27th IEEE 1001 Conference on Local Computer Networks, Tampa, FL, Nov. 2002, 1002 pp. 332-342. 1004 [Pi05a] N. M. Piratla, "A Theoretical Foundation, Metrics and 1005 Modeling of Packet Reordering and Methodology of Delay 1006 Modeling using Inter-packet Gaps," Ph.D. Dissertation, 1007 Department of Electrical and Computer Engineering, Colorado 1008 State University, Fort Collins, CO, Fall 2005. 1010 [RFC2330]V. Paxson, G. Almes, J. Madhavi and M. Mathis, "Framework 1011 for IP Performance Metrics," RFC 2330. 1013 [Pi05b] N. M. Piratla, A. P. Jayasumana and A. A. Bare, "RD: A 1014 Formal, Comprehensive Metric for Packet Reordering," Proc. 1015 5th International IFIP-TC6 Networking Conference (Networking 1016 2005), Waterloo, Canada, May 2-6, 2005, LNCS 3462, 1017 pp: 78-89. 1019 [Pi07] N. M. Piratla and A. P. Jayasumana, "Metrics for Packet 1020 Reordering - A Comparative Analysis," International Journal 1021 of Communication Systems, 2007, dx.doi.org/10.1002/dac.884. 1023 [Pi06] N. M. Piratla and A. P. Jayasumana, "Reordering of Packets 1024 due to Multipath Forwarding - An Analysis," Proc. IEE Intl. 1025 Conf. Communications ICC 2006, Istanbul, Turkey, Jun. 2006. 1027 [Per04] Perl Scripts for RLED and RBD, 1028 http://www.cnrl.colostate.edu/Reorder_Density.html, 1029 Last modified on Jul. 18, 2004. 1031 [Ye06] B. Ye, A. P. Jayasumana and N. Piratla, "On Monitoring of 1032 End-to-End Packet Reordering over the Internet," Proc. Int. 1033 Conf. on Networking and Services (ICNS'06), Santa Clara, CA, 1034 July 2006. 1036 [RFC4737]A. Morton, L. Ciavattone, G. Ramachandran, S.Shalunov and 1037 J.Perser, "Packet Reordering Metrics." 1039 [Pi05c] N. M. Piratla, A. P. Jayasumana and T. Banka, "On Reorder 1040 Density and its Application to Characterization of Packet 1041 Reordering," Proc. 30th IEEE Local Computer Networks 1042 Conference (LCN 2005), Sydney, Australia, Nov. 2005. 1044 14. Authors' Addresses 1046 Anura P. Jayasumana 1047 Computer Networking Research Laboratory, 1048 Department of Electrical and Computer Engineering, 1049 1373 Colorado State University, 1050 Fort Collins, CO 80523, USA 1052 Nischal M. Piratla 1053 Deutsche Telekom Laboratories 1054 Ernst-Reuter-Platz 7, 1055 D-10587 Berlin, Germany 1057 Tarun Banka 1058 Computer Networking Research Laboratory, 1059 Department of Electrical and Computer Engineering, 1060 1373 Colorado State University, 1061 Fort Collins, CO 80523, USA 1063 Abhijit A. Bare 1064 Rick Whitner 1065 Jerry McCollom 1066 Agilent Technologies, 900 South Taft Ave., 1067 Loveland, CO 80537, USA 1069 Expiration Date: January 10, 2008 1071 Full Copyright Statement 1073 Copyright (C) The IETF Trust (2007). 1075 This document is subject to the rights, licenses and restrictions 1076 contained in BCP 78, and except as set forth therein, the authors 1077 retain all their rights. 1079 This document and the information contained herein are provided on an 1080 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1081 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 1082 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 1083 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 1084 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1085 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1087 Intellectual Property 1089 The IETF takes no position regarding the validity or scope of any 1090 Intellectual Property Rights or other rights that might be claimed 1091 to pertain to the implementation or use of the technology described 1092 in this document or the extent to which any license under such 1093 rights might or might not be available; nor does it represent that 1094 it has made any independent effort to identify any such rights. 1095 Information on the procedures with respect to rights in RFC 1096 documents can be found in BCP 78 and BCP 79. 1098 Copies of IPR disclosures made to the IETF Secretariat and any 1099 assurances of licenses to be made available, or the result of an 1100 attempt made to obtain a general license or permission for the use 1101 of such proprietary rights by implementers or users of this 1102 specification can be obtained from the IETF on-line IPR repository 1103 at http://www.ietf.org/ipr. 1105 The IETF invites any interested party to bring to its attention any 1106 copyrights, patents or patent applications, or other proprietary 1107 rights that may cover technology that may be required to implement 1108 this standard. Please address the information to the IETF at ietf- 1109 ipr@ietf.org.