idnits 2.17.1 draft-ietf-bmwg-hash-stuffing-04.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 16. -- Found old boilerplate from RFC 3978, Section 5.5 on line 784. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 761. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 768. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 774. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year -- 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 (October 8, 2005) is 6774 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: 'Ca63' is defined on line 725, but no explicit reference was found in the text == Unused Reference: 'Go97' is defined on line 728, but no explicit reference was found in the text == Unused Reference: 'Kn97' is defined on line 731, but no explicit reference was found in the text ** Downref: Normative reference to an Informational RFC: RFC 2544 ** Downref: Normative reference to an Informational RFC: RFC 2889 Summary: 5 errors (**), 0 flaws (~~), 5 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group D. Newman 3 Internet-Draft Network Test 4 Expires: April 11, 2006 T. Player 5 Spirent Communications 6 October 8, 2005 8 Hash and Stuffing: Overlooked Factors in Network Device Benchmarking 9 draft-ietf-bmwg-hash-stuffing-04.txt 11 Status of this Memo 13 By submitting this Internet-Draft, each author represents that any 14 applicable patent or other IPR claims of which he or she is aware 15 have been or will be disclosed, and any of which he or she becomes 16 aware will be disclosed, in accordance with Section 6 of BCP 79. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet- 21 Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six months 24 and may be updated, replaced, or obsoleted by other documents at any 25 time. It is inappropriate to use Internet-Drafts as reference 26 material or to cite them other than as "work in progress." 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/ietf/1id-abstracts.txt. 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 This Internet-Draft will expire on April 11, 2006. 36 Copyright Notice 38 Copyright (C) The Internet Society (2005). 40 Abstract 42 Test engineers take pains to declare all factors that affect a given 43 measurement, including offered load, packet length, test duration, 44 and traffic orientation. However, current benchmarking practice 45 overlooks two factors that have a profound impact on test results. 46 First, existing methodologies do not require the reporting of 47 addresses or other test traffic contents, even though these fields 48 can affect test results. Second, "stuff" bits and bytes inserted in 49 test traffic by some link-layer technologies add significant and 50 variable overhead, which in turn affects test results. This document 51 describes the effects of these factors; recommends guidelines for 52 test traffic contents; and offers formulas for determining the 53 probability of bit- and byte-stuffing in test traffic. 55 Table of Contents 57 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 58 2. Requirements . . . . . . . . . . . . . . . . . . . . . . . . . 4 59 3. General considerations . . . . . . . . . . . . . . . . . . . . 5 60 3.1. Repeatability . . . . . . . . . . . . . . . . . . . . . . 5 61 3.2. Randomness . . . . . . . . . . . . . . . . . . . . . . . . 5 62 4. Address Pattern Variations . . . . . . . . . . . . . . . . . . 6 63 4.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 6 64 4.2. Ethernet MAC Addresses . . . . . . . . . . . . . . . . . . 7 65 4.2.1. Randomized Sets of MAC Addresses . . . . . . . . . . . 8 66 4.3. MPLS Addressing . . . . . . . . . . . . . . . . . . . . . 10 67 4.4. Network-layer Addressing . . . . . . . . . . . . . . . . . 10 68 4.5. Transport-layer Addressing . . . . . . . . . . . . . . . . 10 69 5. Control Character Stuffing . . . . . . . . . . . . . . . . . . 12 70 5.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 12 71 5.2. PPP Bit Stuffing . . . . . . . . . . . . . . . . . . . . . 12 72 5.2.1. Calculating Bit-Stuffing Probability . . . . . . . . . 14 73 5.2.2. Bit Stuffing for Finite Strings . . . . . . . . . . . 15 74 5.2.3. Applied Bit Stuffing . . . . . . . . . . . . . . . . . 15 75 5.3. POS Byte Stuffing . . . . . . . . . . . . . . . . . . . . 16 76 5.3.1. Nullifying ACCM . . . . . . . . . . . . . . . . . . . 16 77 5.3.2. Other Stuffed Characters . . . . . . . . . . . . . . . 17 78 5.3.3. Applied Byte Stuffing . . . . . . . . . . . . . . . . 17 79 6. Security Considerations . . . . . . . . . . . . . . . . . . . 18 80 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19 81 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20 82 8.1. Normative References . . . . . . . . . . . . . . . . . . . 20 83 8.2. Informative References . . . . . . . . . . . . . . . . . . 20 84 Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 21 85 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22 86 Intellectual Property and Copyright Statements . . . . . . . . . . 23 88 1. Introduction 90 Experience in benchmarking networking devices suggests that the 91 contents of test traffic can have a profound impact on test results. 92 For example, some devices may forward randomly addressed traffic 93 without loss, but drop significant numbers of packets when offered 94 packets containing nonrandom addresses. 96 Methodologies such as [RFC2544] and [RFC2889] do not require any 97 declaration of packet contents. These methodologies do require the 98 declaration of test parameters such as traffic distribution and 99 traffic orientation, and yet packet contents can have at least as 100 great an impact on test results as the other factors. Variations in 101 packet contents also can lead to non-repeatability of test results: 102 Two individuals may follow methodology procedures to the letter, and 103 still obtain very different results. 105 A related issue is the insertion of stuff bits or bytes by link-layer 106 technologies using PPP with HDLC-like framing. This stuffing is done 107 to ensure sequences in test traffic will not be confused with flag or 108 control characters. 110 Stuffing adds significant and variable overhead. Currently there is 111 no standard method for determining the probability that stuffing will 112 occur for a given pattern, and thus no way to determine what impact 113 stuffing will have on test results. 115 This document covers two areas. First, we discuss strategies for 116 dealing with randomness and nonrandomness in test traffic. Second, 117 we present formulas to determine the probability of bit- and byte- 118 stuffing on PPP and POS circuits. In both areas, we provide 119 recommendations for obtaining more repeatability in test results. 121 2. Requirements 123 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 124 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 125 document are to be interpreted as described in [RFC2119]. 127 3. General considerations 129 3.1. Repeatability 131 Repeatability is a desirable trait in benchmarking, but it can be an 132 elusive goal. It is a common but mistaken belief that test results 133 can always be reproduced provided the device under test and test 134 instrument are configured identically for each test iteration. In 135 fact, even identical configurations may introduce some variations in 136 test traffic, such as changes in timestamps, TCP sequence numbers, or 137 other naturally occurring phenomena. 139 While this variability does not necessarily invalidate test results, 140 it is important to recognize such variation exists. Exact bit-for- 141 bit reproduction of test traffic in all cases is a hard problem. A 142 simpler approach is to acknowledge that some variation exists, 143 characterize that variation, and describe it when analyzing test 144 results. 146 3.2. Randomness 148 This document recommends the use of pseudorandom patterns in test 149 traffic under controlled lab conditions. The rand() functions 150 available in many programming languages produce output that is 151 pseudorandom rather than truly random. Pseudorandom patterns are 152 sufficient for the recommendations given in this document, provided 153 they produce output that is uniformly distributed across the pattern 154 space. 156 Specifically, for any random bit pattern of length L, the probability 157 of generating that specific pattern SHOULD equal 1 over 2 to the Lth 158 power. 160 4. Address Pattern Variations 162 4.1. Problem Statement 164 The addresses and port numbers used in a test can have a significant 165 impact on metrics such as throughput, jitter, latency, and loss. 166 This is because many network devices feed such addresses into hashing 167 algorithms to determine which path upon which to forward a given 168 packet. 170 Consider the simple example of an Ethernet switch with eight network 171 processors (NPs) in its switching fabric: 173 ingress 174 || 175 \/ 176 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 177 | ___ ___ ___ ___ ___ ___ ___ ___ | 178 || | | | | | | | | | | | | | | | | 179 ||NP0| |NP1| |NP2| |NP3| |NP4| |NP5| |NP6| |NP7| | 180 ||___| |___| |___| |___| |___| |___| |___| |___| | 181 | | 182 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 183 || 184 \/ 185 egress 187 To assign incoming traffic to the various NPs, suppose a hashing 188 algorithm performs an exclusive-or (XOR) operation on the least 189 significant 3 bits of the source and destination MAC addresses in 190 each frame. (This is an actual example the authors have observed in 191 multiple devices from multiple manufacturers.) 193 In theory, a random distribution of source and destination MAC 194 addresses should result in traffic being uniformly distributed across 195 all eight NPs. (Instances of the term "random" in this document 196 refer to a random uniform distribution across a given address space. 197 Section 3.2 describes random uniform distributions in more detail.) 198 In practice, the actual outcome of the hash (and thus any test 199 results) will be very different depending on the degree of randomness 200 in test traffic. 202 Suppose the traffic is nonrandom so that every interface of the test 203 instrument uses this pattern in its source MAC addresses: 205 00:00:PP:00:00:01 206 where PP is the source interface number of the test instrument. 208 In this case, the least significant 3 bits of every source and 209 destination MAC address are 001, regardless of interface number. 210 Thus, the outcome of the XOR operation will always be 0, given the 211 same three least significant bits: 213 001 ^ 001 = 000 215 Thus, the switch will assign all traffic to NP0, leaving the other 216 seven NPs idle. Given a heavy enough load, NP0 and the switch will 217 become congested, even though seven other NPs are available. At 218 most, this device will be able to utilize approximately 12.5 percent 219 of its total capacity, with the remaining 87.5 percent of capacity 220 unused. 222 Now consider the same example with randomly distributed addresses. 223 In this case, the test instrument offers traffic using MAC addresses 224 with this pattern: 226 00:00:PP:00:00:RR 228 where PP is the source interface number of the test instrument and RR 229 is a pseudorandom number. In this case, there should be an equal 230 probability of the least significant 3 bits of the MAC address having 231 any value from 000 to 111 inclusive. Thus, the outcome of XOR 232 operations should be equally distributed from 0 to 7, and 233 distribution across NPs should also be equal (at least for this 234 particular 3-bit hashing algorithm). Absent other impediments, the 235 device should be able to utilize 100 percent of available bandwidth. 237 This simple example presumes knowledge on the tester's part of the 238 hashing algorithm used by the device under test. Knowledge of such 239 algorithms is not always possible beforehand, and in any event 240 violates the "black box" spirit of many documents produced by the 241 IETF BMWG. 243 The balance of this section offers recommendations for test traffic 244 patterns, starting at the link layer and working up to the transport 245 layer. These patterns should overcome the effects of nonrandomness 246 regardless of the hashing algorithms in use. 248 4.2. Ethernet MAC Addresses 250 Test traffic SHOULD use pseudorandom patterns in Ethernet addresses. 251 The following source and destination Ethernet address pattern is 252 RECOMMENDED for use when benchmarking Ethernet devices: 254 (RR & 0xFE):PP:PP:RR:RR:RR 256 where (RR & 0xFE) is a pseudorandom number bitwise ANDed with 0xFE, 257 PP:PP is the 1-indexed interface number of the test instrument and 258 RR:RR:RR is a pseudorandom number. 260 The bitwise ANDing of the high-order byte in the MAC address with 261 0xFE guarantees a non multicast address. 263 Test traffic SHOULD use PP:PP to identify the source interface number 264 of the test instrument. Such identification can be useful in 265 troubleshooting. Allocating 2 bytes of the MAC address for interface 266 identification allows for tests of up to 65,536 interfaces. A 2-byte 267 space allows for tests much larger than those currently used in 268 device benchmarking; however, tests involving more than 256 269 interfaces (fully utilizing a 1-byte space) are fairly common. 271 Further, source interface numbers SHOULD be 1-indexed and SHOULD NOT 272 be 0-indexed. This avoids the low but nonzero probability of an 273 all-0s Ethernet address. Some devices will drop frames with all-0s 274 Ethernet addresses. 276 It is RECOMMENDED to use pseudorandom patterns in the least 277 significant 3 bytes of the MAC address. Using pseudorandom values 278 for the low-order 3 bytes means choosing one of 16.7 million unique 279 addresses. While this address space is vastly larger than is 280 currently required in lab benchmarking, it does assure more realistic 281 test traffic. 283 Note also that since only 31 of 48 bits in the MAC address have 284 pseudorandom values, there is no possibility of randomly generating a 285 broadcast or multicast value by accident. 287 4.2.1. Randomized Sets of MAC Addresses 289 It is common benchmarking practice for a test instrument to emulate 290 multiple hosts, even on a single interface. This is desirable in 291 assessing DUT/SUT scalability. 293 However, test instruments may emulate multiple MAC addresses by 294 incrementing and/or decrementing addresses from a fixed starting 295 point. This leads to situations as described above in "Address 296 Pattern Variations" where hashing algorithms produce nonoptimal 297 outcomes. 299 The outcome can be nonoptimal even if the set of addresses begins 300 with a pseudorandom number. For example, the following source/ 301 destination pairs will not be equally distributed by the 3-bit 302 hashing algorithm discussed above: 304 Source Destination 305 00:00:01:FC:B3:45 00:00:19:38:8C:80 306 00:00:01:FC:B3:46 00:00:19:38:8C:81 307 00:00:01:FC:B3:47 00:00:19:38:8C:82 308 00:00:01:FC:B3:48 00:00:19:38:8C:83 309 00:00:01:FC:B3:49 00:00:19:38:8C:84 310 00:00:01:FC:B3:4A 00:00:19:38:8C:85 311 00:00:01:FC:B3:4B 00:00:19:38:8C:86 312 00:00:01:FC:B3:4C 00:00:19:38:8C:87 314 Again working with our 3-bit XOR hashing algorithm, we get the 315 following outcomes: 317 101 ^ 000 = 101 318 110 ^ 001 = 111 319 111 ^ 010 = 101 320 000 ^ 011 = 011 321 001 ^ 100 = 101 322 010 ^ 101 = 111 323 011 ^ 110 = 101 324 100 ^ 111 = 011 326 Note that only three of eight possible outcomes are achieved when 327 incrementing addresses. This is actually the best case. 328 Incrementing from other combinations of pseudorandom address pairs 329 produces only one or two out of eight possible outcomes. 331 Every MAC address SHOULD be pseudorandom, not just the starting one. 333 When generating traffic with multiple addresses, it is RECOMMENDED 334 that all addresses use pseudorandom values. There are multiple ways 335 to use sets of pseudorandom numbers. One strategy would be for the 336 test instrument to iterate over an array of pseudorandom values 337 rather than incrementing/decrementing from a starting address. The 338 actual method is an implementation detail; in the end, any method 339 that uses multiple addresses and avoids hash table collisions will be 340 sufficient. 342 4.3. MPLS Addressing 344 Similiar to L2 switches, MPLS routers make forwarding decisions based 345 on a 20 bit MPLS label. Unless specific labels are required, it is 346 RECOMMENDED that uniformly random values between 0 and 1,048,575 be 347 used for all labels assigned by test equipment. 349 4.4. Network-layer Addressing 351 Routers make forwarding decisions based on destination network 352 address. Since there is no hashing of source and destination 353 addresses, the requirement for pseudorandom patterns at the network 354 layer is far less critical than in the Ethernet MAC address case. 356 However, there are cases where randomly distributed IPv4 and/or IPv6 357 addresses are desirable. For example, the equal cost multipath 358 (ECMP) feature performs load-sharing across multiple links. Routers 359 implementing ECMP may perform a hash of source and destination IP 360 addresses in assigning flows. 362 Since multiple ECMP routes by definition have the same metric, 363 routers use some other "tiebreaker" mechanism to assign traffic to 364 each link. As far as the authors are aware, there is no standard 365 algorithm for ECMP link assignment. Some implementations perform a 366 hash of all bits of the source and destination IP addresses for this 367 purpose. 369 Just as in the case of MAC addresses, nonrandom IP addresses can have 370 an adverse effect on the outcome of ECMP link assignment decisions. 372 When benchmarking devices that implement ECMP or any other form of 373 Layer 3 aggregation, it is RECOMMENDED to use a randomly distributed 374 range of IP addresses. 376 4.5. Transport-layer Addressing 378 Some devices with transport- or application-layer awareness use TCP 379 or UDP port numbers in making forwarding decisions. Examples of such 380 devices include load balancers and application-layer firewalls. 382 Test instruments have the capability of generating packets with 383 random TCP and UDP source and destination port numbers. Known 384 destination port numbers are often required for testing application- 385 layer devices. However, unless known port numbers are specifically 386 required for a test, it is RECOMMENDED to use randomly distributed 387 values for both source and destination port numbers. 389 In addition, it may be desirable to pick pseudorandom values from a 390 selected pool of numbers. Many services identify themselves through 391 use of reserved destination port numbers between 1 and 1023 392 inclusive. Unless specific port numbers are required, it is 393 RECOMMENDED to pick randomly distributed destination port numbers 394 between these lower and upper boundaries. 396 Similarly, clients typically choose source port numbers in the space 397 between 1024 and 65535 inclusive. Unless specific port numbers are 398 required, it is RECOMMENDED to pick randomly distributed source port 399 numbers between these lower and upper boundaries. 401 5. Control Character Stuffing 403 5.1. Problem Statement 405 Link-layer technologies that use HDLC-like framing may insert an 406 extra bit or byte before each instance of a control character in 407 traffic. These insertions prevent confusion with control characters, 408 but they may also introduce significant overhead. 410 The overhead of these escape sequences is problematic for two 411 reasons. First, the amount of overhead is non-deterministic. The 412 best testers can do is to characterize the probability that an escape 413 sequence will occur for a given pattern. This greatly complicates 414 the requirement of declaring exactly how much traffic is offered to a 415 DUT/SUT. 417 Second, in the absence of characterization and compensation for this 418 overhead, the tester may unwittingly congest the DUT/SUT. For 419 example, if a tester intends to offer traffic to a DUT at 95 percent 420 of line rate, but the link-layer protocol introduces an additional 1 421 percent of overhead to escape control characters, then the aggregate 422 offered load will be 96 percent of line rate. If the DUT's actual 423 channel capacity is only 95 percent, congestion will occur and the 424 DUT will drop traffic even though the tester did not intend this 425 outcome. 427 As described in [RFC1661] and [RFC1662], PPP and HDLC-like framing 428 introduce two kinds of escape sequences: bit and byte stuffing. Bit 429 stuffing refers to the insertion of an escape bit on bit-synchronous 430 links. Byte stuffing refers to the insertion of an escape byte on 431 byte-synchronous links. We discuss each in turn. 433 5.2. PPP Bit Stuffing 435 [RFC1662], section 5.2 specifies that any sequence of five contiguous 436 "1" bits within a frame must be escaped by inserting a "0" bit prior 437 to the sequence. This escaping is necessary to avoid confusion with 438 the HDLC control character 0x7D, which contains six "1" bits. 440 Consider the following PPP frame containing a TCP/IP packet. Not 441 shown is the 1-byte flag sequence (0x7D), at least one of which must 442 occur between frames. 444 The contents of the various frame fields can be described one of two 445 ways: 447 1. Field contents never change over the test duration. An example 448 would be the IP version number. 450 2. Field contents change over the test duration. Some of these 451 changes are known prior to the test duration. An example would 452 be the use of incrementing IP addresses. Some of these changes 453 are unknown. An example would be a dynamically calculated field 454 such as the TCP checksum. 456 In the diagram below, 30 out of 48 total bytes are subject to change 457 over the test duration. The fields containing the changeable bytes 458 are given in ((double parentheses)). 460 0 1 2 3 461 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 462 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 463 | Address | Control | Protocol | 464 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 465 |Version| IHL |Type of Service| Total Length | 466 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 467 | Identification |Flags| Fragment Offset | 468 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 469 | Time to Live | Protocol | ((Header Checksum)) | 470 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 471 | ((Source Address)) | 472 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 473 | ((Destination Address)) | 474 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 475 | ((Source Port)) | ((Destination Port)) | 476 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 477 | ((Sequence Number)) | 478 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 479 | ((Acknowledgment Number)) | 480 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 481 | Data | |U|A|P|R|S|F| | 482 | Offset| Reserved |R|C|S|S|Y|I| ((Window)) | 483 | | |G|K|H|T|N|N| | 484 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 485 | ((Checksum)) | Urgent Pointer | 486 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 487 | ((FCS (4 bytes) )) | 488 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 490 None of the other fields are known to contain sequences subject to 491 bit-stuffing, at least not in their entirety. 493 Given the information at hand, and assuming static contents for the 494 rest of the fields, the challenge is to determine the probability 495 that bit-stuffing will occur. 497 5.2.1. Calculating Bit-Stuffing Probability 499 In order to calculate bit-stuffing probabilities, we assume that for 500 any string of length L, the probability of the Lth + 1 bit equalling 501 1 is 0.5 and the probability of the Lth + 1 bit equalling 0 is 0.5. 502 Additionally, the value of the Lth + 1 bit is independant of any 503 previous bits. 505 We can calculate the probability of bit stuffing for both infinite 506 and finite strings of random bits. We begin with the infinite-string 507 case, which is required to prove the finite-string case. For an 508 infinitely long string of random bits, we will need to insert a stuff 509 bit if and only if state 5 is reached in the following state table. 511 |--------------------<----------------------| 512 | |1 513 _______ __|__ _____ _____ _____ __|__ 514 | | 1 | | 1 | | 1 | | 1 | | 1 | | 515 | start |--->| 1 |--->| 2 |--->| 3 |--->| 4 |--->| 5 | 516 |_______| |_____| |_____| |_____| |_____| |_____| 517 | | | | | | | 518 | |0 |0 |0 |0 |0 |0 519 |-<-|----<----|----<-----|----<-----|----<-----|----<-----| 521 Initially, we begin in the "start" state. A 1 bit moves us into the 522 next highest state, and a 0 bit returns us to the start state. From 523 state 5, a 1 bit takes us back to the 1 state and a 0 bit returns us 524 to "start." From this state table we can build the following 525 transition matrix: 527 | start 1 2 3 4 5 528 ______|_________________________________________________ 529 start | 0.5 | 0.5 | 0.5 | 0.5 | 0.5 | 0.5 530 1 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0 | 0.5 531 2 | 0.0 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0 532 3 | 0.0 | 0.0 | 0.5 | 0.0 | 0.0 | 0.0 533 4 | 0.0 | 0.0 | 0.0 | 0.5 | 0.0 | 0.0 534 5 | 0.0 | 0.0 | 0.0 | 0.0 | 0.5 | 0.0 536 With this transition matrix we can build the following system of 537 equations. If P(x) represents the probability of reaching state x, 538 then: 540 P(start) = 0.5 * P(start) + 0.5 * P(1) + 0.5 * P(2) + 0.5 * P(3) + 541 0.5 * P(4) + 0.5 * P(5) 543 P(1) = 0.5 * P(start) + 0.5 * P(5) 544 P(2) = 0.5 * P(1) 545 P(3) = 0.5 * P(2) 546 P(4) = 0.5 * P(3) 547 P(5) = 0.5 * P(4) 549 P(start) + P(1) + P(2) + P(3) + P(4) + P(5) = 1 551 Solving this system of equations yields: 553 P(start) = 0.5 554 P(1) = 8/31 555 P(2) = 4/31 556 P(3) = 2/31 557 P(4) = 1/31 558 P(5) = 1/62 560 Thus, for an infinitely long string of random bits, the probability 561 of 5 sequential 1 bits is 1/62. Put another way, we expect to add 562 one stuff bit for every 62 bits of random uniform data. 564 5.2.2. Bit Stuffing for Finite Strings 566 The above result indicates that for any string of uniformly 567 distributed random bits, we expect a stuffing event to occur every 62 568 bits. So, given a string of some finite length L, where L >= 5, the 569 expected number of stuffs is simply L * 1/62. 571 5.2.3. Applied Bit Stuffing 573 The amount of overhead attributable to bit stuffing may be calculated 574 explicitly as long as the total number of random bits per frame, 575 L_rand-bits, and the probability of stuffing, P(stuff), is known. 577 % overhead = ( P(stuff) * L_rand-bits ) / framesize (in bits) 579 Note that if the entire frame contains random bits, then the 580 percentage overhead is simply the probability of stuffing expressed 581 as a percentage. 583 Given that the overhead added by bit-stuffing is at most 1 in 62, or 584 approximately 1.6 percent, it is RECOMMENDED that testers reduce the 585 maximum offered load by 1.6 percent to avoid introducing congestion 586 when testing devices using bit-synchronous interfaces (such as T1/E1, 587 DS-3, and the like). 589 The percentage given above is an approximation. For greatest 590 precision, the actual offered load SHOULD be calculated using the 591 percentage overhead formula above and then expressed in frames per 592 second, rounded down to the nearest integer. 594 Note that the DUT/SUT may be able to forward offered loads higher 595 than the calculated theoretical maximum rate without packet loss. 596 Such results are the result of queuing on the part of the DUT/SUT. 597 While a device's throughput may be above this level, delay-related 598 measurements may be affected. Accordingly, it is RECOMMENDED to 599 reduce offered levels by the amount of bit-stuffing overhead when 600 testing devices using bit-synchronous links. This recommendation 601 applies for all measurements, including throughput. 603 5.3. POS Byte Stuffing 605 [RFC1662] requires that "Each Flag Sequence, Control Escape octet, 606 and any octet which is flagged in the sending Async-Control- 607 Character-Map (ACCM), is replaced by a two octet sequence consisting 608 of the Control Escape octet followed by the original octet exclusive- 609 or'd with hexadecimal 0x20." The practical effect of this is to 610 insert a stuff byte for instances of up to 34 characters: 0x7E, 0x7D, 611 or any of 32 ACCM values. 613 A common implementation of PPP in HDLC-like framing is in PPP over 614 Sonet/SDH (POS), as defined in [RFC2615]. 616 As with the bit-stuffing case, the requirement in characterizing POS 617 test traffic is to determine the probability that byte-stuffing will 618 occur for a given sequence. This is much simpler to do than with 619 bit-synchronous links, since there is no possibility of overlap 620 across byte boundaries. 622 5.3.1. Nullifying ACCM 624 Testers can greatly reduce the probability of byte-stuffing by 625 configuring link partners to negotiate an ACCM value of 0x00. It is 626 RECOMMENDED that testers configure the test instrument(s) and DUT/SUT 627 to negotiate an ACCM value of 0x00 unless specific ACCM values are 628 required. 630 One instance where nonzero ACCM values are used is in the layer 2 631 tunneling protocol (L2TP), as defined in [RFC2661], section 4.4.6. 632 When the default ACCM values are used, the probability of stuffing 633 for any given random byte is 34 in 256, or approximately 13.3 634 percent. 636 5.3.2. Other Stuffed Characters 638 If an ACCM value of 0x00 is negotiated, the only characters subject 639 to stuffing are the flag and control escape characters. Thus, we can 640 say that without ACCM the probability of stuffing for any given 641 random byte is 2 in 256, or approximately 0.8 percent. 643 5.3.3. Applied Byte Stuffing 645 The amount of overhead attributable to bit or byte stuffing may be 646 calculated explicitly as long as the total number of random bytes per 647 frame, L_rand-bytes, and the probability of stuffing, P(stuff), is 648 known. 650 % overhead = ( P(stuff) * L_rand-bytes ) / framesize (in bytes) 652 Note that if the entire frame contains random bytes, then the 653 percentage overhead is simply the probability of stuffing expressed 654 as a percentage. 656 When testing a DUT/SUT that implements PPP in HDLC-like framing and 657 L2TP (or any other technology that uses nonzero ACCM values), it is 658 RECOMMENDED that testers reduce the maximum offered load by 13.3 659 percent to avoid introducing congestion. 661 When testing a DUT/SUT that implements PPP in HDLC-like framing and 662 an ACCM value of 0x00, it is RECOMMENDED that testers reduce the 663 maximum offered load by 0.8 percent to avoid introducing congestion. 665 Note that the percentages given above are approximations. For 666 greatest precision, the actual offered load SHOULD be calculated 667 using the percentage overhead formula above and then expressed in 668 frames per second (rounded down to the nearest integer). 670 Note also that the DUT/SUT may be able to forward offered loads 671 higher than the calculated theoretical maximum rate without packet 672 loss. Such results are the result of queuing on the part of the DUT/ 673 SUT. While a device's throughput may be above this level, delay- 674 related measurements may be affected. Accordingly, it is RECOMMENDED 675 to reduce offered levels by the amount of byte-stuffing overhead when 676 testing devices using byte-synchronous links. This recommendation 677 applies for all measurements, including throughput. 679 6. Security Considerations 681 This document recommends the use of pseudorandom patterns in test 682 traffic. The rand() functions of many programming languages produce 683 output that is pseudorandom rather than truly random. As far as the 684 authors are aware, pseudorandom patterns are sufficient for 685 generating test traffic in lab conditions. 687 [RFC2615], section 6, discusses a denial-of-service attack involving 688 the intentional transmission of characters that require stuffing. 689 This attack could consume up to 100 percent of available bandwidth. 690 However, the test networks described in BMWG documents generally 691 SHOULD NOT be reachable by anyone other than the tester(s). 693 7. IANA Considerations 695 This document has no actions for IANA. 697 8. References 699 8.1. Normative References 701 [RFC1661] Simpson, W., "The Point-to-Point Protocol (PPP)", STD 51, 702 RFC 1661, July 1994. 704 [RFC1662] Simpson, W., "PPP in HDLC-like Framing", STD 51, RFC 1662, 705 July 1994. 707 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 708 Requirement Levels", BCP 14, RFC 2119, March 1997. 710 [RFC2544] Bradner, S. and J. McQuaid, "Benchmarking Methodology for 711 Network Interconnect Devices", RFC 2544, March 1999. 713 [RFC2615] Malis, A. and W. Simpson, "PPP over SONET/SDH", RFC 2615, 714 June 1999. 716 [RFC2661] Townsley, W., Valencia, A., Rubens, A., Pall, G., Zorn, 717 G., and B. Palter, "Layer Two Tunneling Protocol "L2TP"", 718 RFC 2661, August 1999. 720 [RFC2889] Mandeville, R. and J. Perser, "Benchmarking Methodology 721 for LAN Switching Devices", RFC 2889, August 2000. 723 8.2. Informative References 725 [Ca63] Campbell, D. and J. Stanley, "Experimental and Quasi- 726 Experimental Designs for Research", 1963. 728 [Go97] Goralski, W., "SONET: A Guide to Synchronous Optical 729 Networks", 1997. 731 [Kn97] Knuth, D., "The Art of Computer Programming, Volume 2, Third 732 Edition", 1997. 734 Appendix A. Acknowledgements 736 The authors gratefully acknowledge reviews and contributions by Neil 737 Carter, Glenn Chagnot, Rafael Francis, Paul Hoffman, David Joyner, 738 Joe Perches, and Scott Poretsky. 740 Authors' Addresses 742 David Newman 743 Network Test 745 Email: dnewman@networktest.com 747 Timmons C. Player 748 Spirent Communications 750 Email: timmons.player@spirentcom.com 752 Intellectual Property Statement 754 The IETF takes no position regarding the validity or scope of any 755 Intellectual Property Rights or other rights that might be claimed to 756 pertain to the implementation or use of the technology described in 757 this document or the extent to which any license under such rights 758 might or might not be available; nor does it represent that it has 759 made any independent effort to identify any such rights. Information 760 on the procedures with respect to rights in RFC documents can be 761 found in BCP 78 and BCP 79. 763 Copies of IPR disclosures made to the IETF Secretariat and any 764 assurances of licenses to be made available, or the result of an 765 attempt made to obtain a general license or permission for the use of 766 such proprietary rights by implementers or users of this 767 specification can be obtained from the IETF on-line IPR repository at 768 http://www.ietf.org/ipr. 770 The IETF invites any interested party to bring to its attention any 771 copyrights, patents or patent applications, or other proprietary 772 rights that may cover technology that may be required to implement 773 this standard. Please address the information to the IETF at 774 ietf-ipr@ietf.org. 776 Disclaimer of Validity 778 This document and the information contained herein are provided on an 779 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 780 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 781 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 782 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 783 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 784 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 786 Copyright Statement 788 Copyright (C) The Internet Society (2005). This document is subject 789 to the rights, licenses and restrictions contained in BCP 78, and 790 except as set forth therein, the authors retain all their rights. 792 Acknowledgment 794 Funding for the RFC Editor function is currently provided by the 795 Internet Society.