idnits 2.17.1 draft-ietf-bmwg-hash-stuffing-03.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 781. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 753. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 760. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 766. ** 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 (June 21, 2005) is 6877 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 718, but no explicit reference was found in the text == Unused Reference: 'Go97' is defined on line 721, but no explicit reference was found in the text == Unused Reference: 'Kn97' is defined on line 724, 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: December 23, 2005 T. Player 5 Spirent Communications 6 June 21, 2005 8 Hash and Stuffing: Overlooked Factors in Network Device Benchmarking 9 draft-ietf-bmwg-hash-stuffing-03.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 December 23, 2005. 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 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 20 85 A. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 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 The following source and destination Ethernet address pattern is 251 RECOMMENDED for use when benchmarking Ethernet devices: 253 (RR & 0xFE):PP:PP:RR:RR:RR 254 where (RR & 0xFE) is a pseudorandom number bitwise ANDed with 0xFE, 255 PP:PP is the interface number of the test instrument and RR:RR:RR is 256 a pseudorandom number. 258 The bitwise ANDing of the high-order byte in the MAC address with 259 0xFE guarantees a non multicast address. 261 It is RECOMMENDED to use PP:PP to identify the source interface 262 number of the test instrument. Such identification can be useful in 263 troubleshooting. Allocating 2 bytes of the MAC address for interface 264 identification allows for tests of up to 65,536 interfaces. A 2-byte 265 space allows for tests much larger than those currently used in 266 device benchmarking; however, tests involving more than 256 267 interfaces (fully utilizing a 1-byte space) are fairly common. 269 It is RECOMMENDED to use pseudorandom patterns in the least 270 significant 3 bytes of the MAC address. Using pseudorandom values 271 for the low-order 3 bytes means choosing one of 16.7 million unique 272 addresses. While this address space is vastly larger than is 273 currently required in lab benchmarking, it does assure more realistic 274 test traffic. 276 Note also that since only 31 of 48 bits in the MAC address have 277 pseudorandom values, there is no possibility of randomly generating a 278 broadcast or multicast value by accident. 280 4.2.1 Randomized Sets of MAC Addresses 282 It is common benchmarking practice for a test instrument to emulate 283 multiple hosts, even on a single interface. This is desirable in 284 assessing DUT/SUT scalability. 286 However, test instruments may emulate multiple MAC addresses by 287 incrementing and/or decrementing addresses from a fixed starting 288 point. This leads to situations as described above in "Address 289 Pattern Variations" where hashing algorithms produce nonoptimal 290 outcomes. 292 The outcome can be nonoptimal even if the set of addresses begins 293 with a pseudorandom number. For example, the following source/ 294 destination pairs will not be equally distributed by the 3-bit 295 hashing algorithm discussed above: 297 Source Destination 298 00:00:01:FC:B3:45 00:00:19:38:8C:80 299 00:00:01:FC:B3:46 00:00:19:38:8C:81 300 00:00:01:FC:B3:47 00:00:19:38:8C:82 301 00:00:01:FC:B3:48 00:00:19:38:8C:83 302 00:00:01:FC:B3:49 00:00:19:38:8C:84 303 00:00:01:FC:B3:4A 00:00:19:38:8C:85 304 00:00:01:FC:B3:4B 00:00:19:38:8C:86 305 00:00:01:FC:B3:4C 00:00:19:38:8C:87 307 Again working with our 3-bit XOR hashing algorithm, we get the 308 following outcomes: 310 101 ^ 000 = 101 311 110 ^ 001 = 111 312 111 ^ 010 = 101 313 000 ^ 011 = 011 314 001 ^ 100 = 101 315 010 ^ 101 = 111 316 011 ^ 110 = 101 317 100 ^ 111 = 011 319 Note that only three of eight possible outcomes are achieved when 320 incrementing addresses. This is actually the best case. 321 Incrementing from other combinations of pseudorandom address pairs 322 produces only one or two out of eight possible outcomes. 324 Every MAC address SHOULD be pseudorandom, not just the starting one. 326 When generating traffic with multiple addresses, it is RECOMMENDED 327 that all addresses use pseudorandom values. There are multiple ways 328 to use sets of pseudorandom numbers. One strategy would be for the 329 test instrument to iterate over an array of pseudorandom values 330 rather than incrementing/decrementing from a starting address. The 331 actual method is an implementation detail; in the end, any method 332 that uses multiple addresses and avoids hash table collisions will be 333 sufficient. 335 4.3 MPLS Addressing 337 Similiar to L2 switches, MPLS routers make forwarding decisions based 338 on a 20 bit MPLS label. Unless specific labels are required, it is 339 RECOMMENDED that uniformly random values between 0 and 1,048,575 be 340 used for all labels assigned by test equipment. 342 4.4 Network-layer Addressing 344 Routers make forwarding decisions based on destination network 345 address. Since there is no hashing of source and destination 346 addresses, the requirement for pseudorandom patterns at the network 347 layer is far less critical than in the Ethernet MAC address case. 349 However, there are cases where randomly distributed IPv4 and/or IPv6 350 addresses are desirable. For example, the equal cost multipath 351 (ECMP) feature performs load-sharing across multiple links. Routers 352 implementing ECMP may perform a hash of source and destination IP 353 addresses in assigning flows. 355 Since multiple ECMP routes by definition have the same metric, 356 routers use some other "tiebreaker" mechanism to assign traffic to 357 each link. As far as the authors are aware, there is no standard 358 algorithm for ECMP link assignment. Some implementations perform a 359 hash of all bits of the source and destination IP addresses for this 360 purpose. 362 Just as in the case of MAC addresses, nonrandom IP addresses can have 363 an adverse effect on the outcome of ECMP link assignment decisions. 365 When benchmarking devices that implement ECMP or any other form of 366 Layer 3 aggregation, it is RECOMMENDED to use a randomly distributed 367 range of IP addresses. 369 4.5 Transport-layer Addressing 371 Some devices with transport- or application-layer awareness use TCP 372 or UDP port numbers in making forwarding decisions. Examples of such 373 devices include load balancers and application-layer firewalls. 375 Test instruments have the capability of generating packets with 376 random TCP and UDP source and destination port numbers. Known 377 destination port numbers are often required for testing application- 378 layer devices. However, unless known port numbers are specifically 379 required for a test, it is RECOMMENDED to use randomly distributed 380 values for both source and destination port numbers. 382 In addition, it may be desirable to pick pseudorandom values from a 383 selected pool of numbers. Many services identify themselves through 384 use of reserved destination port numbers between 1 and 1023 385 inclusive. Unless specific port numbers are required, it is 386 RECOMMENDED to pick randomly distributed destination port numbers 387 between these lower and upper boundaries. 389 Similarly, clients typically choose source port numbers in the space 390 between 1024 and 65535 inclusive. Unless specific port numbers are 391 required, it is RECOMMENDED to pick randomly distributed source port 392 numbers between these lower and upper boundaries. 394 5. Control Character Stuffing 396 5.1 Problem Statement 398 Link-layer technologies that use HDLC-like framing may insert an 399 extra bit or byte before each instance of a control character in 400 traffic. These insertions prevent confusion with control characters, 401 but they may also introduce significant overhead. 403 The overhead of these escape sequences is problematic for two 404 reasons. First, the amount of overhead is non-deterministic. The 405 best testers can do is to characterize the probability that an escape 406 sequence will occur for a given pattern. This greatly complicates 407 the requirement of declaring exactly how much traffic is offered to a 408 DUT/SUT. 410 Second, in the absence of characterization and compensation for this 411 overhead, the tester may unwittingly congest the DUT/SUT. For 412 example, if a tester intends to offer traffic to a DUT at 95 percent 413 of line rate, but the link-layer protocol introduces an additional 1 414 percent of overhead to escape control characters, then the aggregate 415 offered load will be 96 percent of line rate. If the DUT's actual 416 channel capacity is only 95 percent, congestion will occur and the 417 DUT will drop traffic even though the tester did not intend this 418 outcome. 420 As described in [RFC1661] and [RFC1662], PPP and HDLC-like framing 421 introduce two kinds of escape sequences: bit and byte stuffing. Bit 422 stuffing refers to the insertion of an escape bit on bit-synchronous 423 links. Byte stuffing refers to the insertion of an escape byte on 424 byte-synchronous links. We discuss each in turn. 426 5.2 PPP Bit Stuffing 428 [RFC1662], section 5.2 specifies that any sequence of five contiguous 429 "1" bits within a frame must be escaped by inserting a "0" bit prior 430 to the sequence. This escaping is necessary to avoid confusion with 431 the HDLC control character 0x7D, which contains six "1" bits. 433 Consider the following PPP frame containing a TCP/IP packet. Not 434 shown is the 1-byte flag sequence (0x7D), at least one of which must 435 occur between frames. 437 The contents of the various frame fields can be described one of two 438 ways: 440 1. Field contents never change over the test duration. An example 441 would be the IP version number. 443 2. Field contents change over the test duration. Some of these 444 changes are known prior to the test duration. An example would 445 be the use of incrementing IP addresses. Some of these changes 446 are unknown. An example would be a dynamically calculated field 447 such as the TCP checksum. 449 In the diagram below, 30 out of 48 total bytes are subject to change 450 over the test duration. The fields containing the changeable bytes 451 are given in ((double parentheses)). 453 0 1 2 3 454 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 455 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 456 | Address | Control | Protocol | 457 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 458 |Version| IHL |Type of Service| Total Length | 459 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 460 | Identification |Flags| Fragment Offset | 461 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 462 | Time to Live | Protocol | ((Header Checksum)) | 463 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 464 | ((Source Address)) | 465 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 466 | ((Destination Address)) | 467 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 468 | ((Source Port)) | ((Destination Port)) | 469 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 470 | ((Sequence Number)) | 471 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 472 | ((Acknowledgment Number)) | 473 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 474 | Data | |U|A|P|R|S|F| | 475 | Offset| Reserved |R|C|S|S|Y|I| ((Window)) | 476 | | |G|K|H|T|N|N| | 477 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 478 | ((Checksum)) | Urgent Pointer | 479 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 480 | ((FCS (4 bytes) )) | 481 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 483 None of the other fields are known to contain sequences subject to 484 bit-stuffing, at least not in their entirety. 486 Given the information at hand, and assuming static contents for the 487 rest of the fields, the challenge is to determine the probability 488 that bit-stuffing will occur. 490 5.2.1 Calculating Bit-Stuffing Probability 492 In order to calculate bit-stuffing probabilities, we assume that for 493 any string of length L, the probability of the Lth + 1 bit equalling 494 1 is 0.5 and the probability of the Lth + 1 bit equalling 0 is 0.5. 495 Additionally, the value of the Lth + 1 bit is independant of any 496 previous bits. 498 We can calculate the probability of bit stuffing for both infinite 499 and finite strings of random bits. We begin with the infinite-string 500 case, which is required to prove the finite-string case. For an 501 infinitely long string of random bits, we will need to insert a stuff 502 bit if and only if state 5 is reached in the following state table. 504 |--------------------<----------------------| 505 | |1 506 _______ __|__ _____ _____ _____ __|__ 507 | | 1 | | 1 | | 1 | | 1 | | 1 | | 508 | start |--->| 1 |--->| 2 |--->| 3 |--->| 4 |--->| 5 | 509 |_______| |_____| |_____| |_____| |_____| |_____| 510 | | | | | | | 511 | |0 |0 |0 |0 |0 |0 512 |-<-|----<----|----<-----|----<-----|----<-----|----<-----| 514 Initially, we begin in the "start" state. A 1 bit moves us into the 515 next highest state, and a 0 bit returns us to the start state. From 516 state 5, a 1 bit takes us back to the 1 state and a 0 bit returns us 517 to "start." From this state table we can build the following 518 transition matrix: 520 | start 1 2 3 4 5 521 ______|_________________________________________________ 522 start | 0.5 | 0.5 | 0.5 | 0.5 | 0.5 | 0.5 523 1 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0 | 0.5 524 2 | 0.0 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0 525 3 | 0.0 | 0.0 | 0.5 | 0.0 | 0.0 | 0.0 526 4 | 0.0 | 0.0 | 0.0 | 0.5 | 0.0 | 0.0 527 5 | 0.0 | 0.0 | 0.0 | 0.0 | 0.5 | 0.0 529 With this transition matrix we can build the following system of 530 equations. If P(x) represents the probability of reaching state x, 531 then: 533 P(start) = 0.5 * P(start) + 0.5 * P(1) + 0.5 * P(2) + 0.5 * P(3) + 534 0.5 * P(4) + 0.5 * P(5) 536 P(1) = 0.5 * P(start) + 0.5 * P(5) 537 P(2) = 0.5 * P(1) 538 P(3) = 0.5 * P(2) 539 P(4) = 0.5 * P(3) 540 P(5) = 0.5 * P(4) 542 P(start) + P(1) + P(2) + P(3) + P(4) + P(5) = 1 544 Solving this system of equations yields: 546 P(start) = 0.5 547 P(1) = 8/31 548 P(2) = 4/31 549 P(3) = 2/31 550 P(4) = 1/31 551 P(5) = 1/62 553 Thus, for an infinitely long string of random bits, the probability 554 of 5 sequential 1 bits is 1/62. Put another way, we expect to add 555 one stuff bit for every 62 bits of random uniform data. 557 5.2.2 Bit Stuffing for Finite Strings 559 The above result indicates that for any string of uniformly 560 distributed random bits, we expect a stuffing event to occur every 62 561 bits. So, given a string of some finite length L, where L >= 5, the 562 expected number of stuffs is simply L * 1/62. 564 5.2.3 Applied Bit Stuffing 566 The amount of overhead attributable to bit stuffing may be calculated 567 explicitly as long as the total number of random bits per frame, 568 L_rand-bits, and the probability of stuffing, P(stuff), is known. 570 % overhead = ( P(stuff) * L_rand-bits ) / framesize (in bits) 572 Note that if the entire frame contains random bits, then the 573 percentage overhead is simply the probability of stuffing expressed 574 as a percentage. 576 Given that the overhead added by bit-stuffing is at most 1 in 62, or 577 approximately 1.6 percent, it is RECOMMENDED that testers reduce the 578 maximum offered load by 1.6 percent to avoid introducing congestion 579 when testing devices using bit-synchronous interfaces (such as T1/E1, 580 DS-3, and the like). 582 The percentage given above is an approximation. For greatest 583 precision, the actual offered load SHOULD be calculated using the 584 percentage overhead formula above and then expressed in frames per 585 second, rounded down to the nearest integer. 587 Note that the DUT/SUT may be able to forward offered loads higher 588 than the calculated theoretical maximum rate without packet loss. 589 Such results are the result of queuing on the part of the DUT/SUT. 590 While a device's throughput may be above this level, delay-related 591 measurements may be affected. Accordingly, it is RECOMMENDED to 592 reduce offered levels by the amount of bit-stuffing overhead when 593 testing devices using bit-synchronous links. This recommendation 594 applies for all measurements, including throughput. 596 5.3 POS Byte Stuffing 598 [RFC1662] requires that "Each Flag Sequence, Control Escape octet, 599 and any octet which is flagged in the sending Async-Control- 600 Character-Map (ACCM), is replaced by a two octet sequence consisting 601 of the Control Escape octet followed by the original octet exclusive- 602 or'd with hexadecimal 0x20." The practical effect of this is to 603 insert a stuff byte for instances of up to 34 characters: 0x7E, 0x7D, 604 or any of 32 ACCM values. 606 A common implementation of PPP in HDLC-like framing is in PPP over 607 Sonet/SDH (POS), as defined in [RFC2615]. 609 As with the bit-stuffing case, the requirement in characterizing POS 610 test traffic is to determine the probability that byte-stuffing will 611 occur for a given sequence. This is much simpler to do than with 612 bit-synchronous links, since there is no possibility of overlap 613 across byte boundaries. 615 5.3.1 Nullifying ACCM 617 Testers can greatly reduce the probability of byte-stuffing by 618 configuring link partners to negotiate an ACCM value of 0x00. It is 619 RECOMMENDED that testers configure the test instrument(s) and DUT/SUT 620 to negotiate an ACCM value of 0x00 unless specific ACCM values are 621 required. 623 One instance where nonzero ACCM values are used is in the layer 2 624 tunneling protocol (L2TP), as defined in [RFC2661], section 4.4.6. 625 When the default ACCM values are used, the probability of stuffing 626 for any given random byte is 34 in 256, or approximately 13.3 627 percent. 629 5.3.2 Other Stuffed Characters 631 If an ACCM value of 0x00 is negotiated, the only characters subject 632 to stuffing are the flag and control escape characters. Thus, we can 633 say that without ACCM the probability of stuffing for any given 634 random byte is 2 in 256, or approximately 0.8 percent. 636 5.3.3 Applied Byte Stuffing 638 The amount of overhead attributable to bit or byte stuffing may be 639 calculated explicitly as long as the total number of random bytes per 640 frame, L_rand-bytes, and the probability of stuffing, P(stuff), is 641 known. 643 % overhead = ( P(stuff) * L_rand-bytes ) / framesize (in bytes) 645 Note that if the entire frame contains random bytes, then the 646 percentage overhead is simply the probability of stuffing expressed 647 as a percentage. 649 When testing a DUT/SUT that implements PPP in HDLC-like framing and 650 L2TP (or any other technology that uses nonzero ACCM values), it is 651 RECOMMENDED that testers reduce the maximum offered load by 13.3 652 percent to avoid introducing congestion. 654 When testing a DUT/SUT that implements PPP in HDLC-like framing and 655 an ACCM value of 0x00, it is RECOMMENDED that testers reduce the 656 maximum offered load by 0.8 percent to avoid introducing congestion. 658 Note that the percentages given above are approximations. For 659 greatest precision, the actual offered load SHOULD be calculated 660 using the percentage overhead formula above and then expressed in 661 frames per second (rounded down to the nearest integer). 663 Note also that the DUT/SUT may be able to forward offered loads 664 higher than the calculated theoretical maximum rate without packet 665 loss. Such results are the result of queuing on the part of the DUT/ 666 SUT. While a device's throughput may be above this level, delay- 667 related measurements may be affected. Accordingly, it is RECOMMENDED 668 to reduce offered levels by the amount of byte-stuffing overhead when 669 testing devices using byte-synchronous links. This recommendation 670 applies for all measurements, including throughput. 672 6. Security Considerations 674 This document recommends the use of pseudorandom patterns in test 675 traffic. The rand() functions of many programming languages produce 676 output that is pseudorandom rather than truly random. As far as the 677 authors are aware, pseudorandom patterns are sufficient for 678 generating test traffic in lab conditions. 680 [RFC2615], section 6, discusses a denial-of-service attack involving 681 the intentional transmission of characters that require stuffing. 682 This attack could consume up to 100 percent of available bandwidth. 683 However, the test networks described in BMWG documents generally 684 SHOULD NOT be reachable by anyone other than the tester(s). 686 7. IANA Considerations 688 This document has no actions for IANA. 690 8. References 692 8.1 Normative References 694 [RFC1661] Simpson, W., "The Point-to-Point Protocol (PPP)", STD 51, 695 RFC 1661, July 1994. 697 [RFC1662] Simpson, W., "PPP in HDLC-like Framing", STD 51, RFC 1662, 698 July 1994. 700 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 701 Requirement Levels", BCP 14, RFC 2119, March 1997. 703 [RFC2544] Bradner, S. and J. McQuaid, "Benchmarking Methodology for 704 Network Interconnect Devices", RFC 2544, March 1999. 706 [RFC2615] Malis, A. and W. Simpson, "PPP over SONET/SDH", RFC 2615, 707 June 1999. 709 [RFC2661] Townsley, W., Valencia, A., Rubens, A., Pall, G., Zorn, 710 G., and B. Palter, "Layer Two Tunneling Protocol "L2TP"", 711 RFC 2661, August 1999. 713 [RFC2889] Mandeville, R. and J. Perser, "Benchmarking Methodology 714 for LAN Switching Devices", RFC 2889, August 2000. 716 8.2 Informative References 718 [Ca63] Campbell, D. and J. Stanley, "Experimental and Quasi- 719 Experimental Designs for Research", 1963. 721 [Go97] Goralski, W., "SONET: A Guide to Synchronous Optical 722 Networks", 1997. 724 [Kn97] Knuth, D., "The Art of Computer Programming, Volume 2, Third 725 Edition", 1997. 727 Authors' Addresses 729 David Newman 730 Network Test 732 Email: dnewman@networktest.com 733 Timmons C. Player 734 Spirent Communications 736 Email: timmons.player@spirentcom.com 738 Appendix A. Acknowledgements 740 The authors gratefully acknowledge reviews and contributions by Neil 741 Carter, Glenn Chagnot, Rafael Francis, Paul Hoffman, David Joyner, 742 Joe Perches, and Scott Poretsky. 744 Intellectual Property Statement 746 The IETF takes no position regarding the validity or scope of any 747 Intellectual Property Rights or other rights that might be claimed to 748 pertain to the implementation or use of the technology described in 749 this document or the extent to which any license under such rights 750 might or might not be available; nor does it represent that it has 751 made any independent effort to identify any such rights. Information 752 on the procedures with respect to rights in RFC documents can be 753 found in BCP 78 and BCP 79. 755 Copies of IPR disclosures made to the IETF Secretariat and any 756 assurances of licenses to be made available, or the result of an 757 attempt made to obtain a general license or permission for the use of 758 such proprietary rights by implementers or users of this 759 specification can be obtained from the IETF on-line IPR repository at 760 http://www.ietf.org/ipr. 762 The IETF invites any interested party to bring to its attention any 763 copyrights, patents or patent applications, or other proprietary 764 rights that may cover technology that may be required to implement 765 this standard. Please address the information to the IETF at 766 ietf-ipr@ietf.org. 768 The IETF has been notified of intellectual property rights claimed in 769 regard to some or all of the specification contained in this 770 document. For more information consult the online list of claimed 771 rights. 773 Disclaimer of Validity 775 This document and the information contained herein are provided on an 776 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 777 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 778 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 779 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 780 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 781 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 783 Copyright Statement 785 Copyright (C) The Internet Society (2005). This document is subject 786 to the rights, licenses and restrictions contained in BCP 78, and 787 except as set forth therein, the authors retain all their rights. 789 Acknowledgment 791 Funding for the RFC Editor function is currently provided by the 792 Internet Society.