idnits 2.17.1 draft-ietf-bmwg-hash-stuffing-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 16. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 1140. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1151. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1158. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1164. 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 : ---------------------------------------------------------------------------- == There are 2 instances of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust 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 (December 31, 2006) is 6324 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) == Missing Reference: 'UDP' is mentioned on line 978, but not defined ** Downref: Normative reference to an Informational RFC: RFC 2544 ** Downref: Normative reference to an Informational RFC: RFC 2889 Summary: 3 errors (**), 0 flaws (~~), 4 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: July 4, 2007 T. Player 5 Spirent Communications 6 December 31, 2006 8 Hash and Stuffing: Overlooked Factors in Network Device Benchmarking 9 draft-ietf-bmwg-hash-stuffing-08.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 July 4, 2007. 36 Copyright Notice 38 Copyright (C) The IETF Trust (2006). 40 Abstract 42 Test engineers take pains to declare all factors that affect a given 43 measurement, including intended 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 . . . . . . . . . . . . . . . . . . . . . . . . . 4 58 2. Requirements . . . . . . . . . . . . . . . . . . . . . . . . . 5 59 3. General considerations . . . . . . . . . . . . . . . . . . . . 6 60 3.1. Repeatability . . . . . . . . . . . . . . . . . . . . . . 6 61 3.2. Randomness . . . . . . . . . . . . . . . . . . . . . . . . 6 62 4. Packet Content Variations . . . . . . . . . . . . . . . . . . 8 63 4.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 8 64 4.2. IEEE 802 MAC Addresses . . . . . . . . . . . . . . . . . . 9 65 4.2.1. Randomized Sets of MAC Addresses . . . . . . . . . . . 11 66 4.3. MPLS Addressing . . . . . . . . . . . . . . . . . . . . . 12 67 4.4. Network-layer Addressing . . . . . . . . . . . . . . . . . 12 68 4.5. Transport-layer Addressing . . . . . . . . . . . . . . . . 13 69 4.6. Application-layer Patterns . . . . . . . . . . . . . . . . 13 70 5. Control Character Stuffing . . . . . . . . . . . . . . . . . . 15 71 5.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 15 72 5.2. PPP Bit Stuffing . . . . . . . . . . . . . . . . . . . . . 15 73 5.2.1. Calculating Bit-Stuffing Probability . . . . . . . . . 18 74 5.2.2. Bit Stuffing for Finite Strings . . . . . . . . . . . 20 75 5.2.3. Applied Bit Stuffing . . . . . . . . . . . . . . . . . 20 76 5.3. POS Byte Stuffing . . . . . . . . . . . . . . . . . . . . 21 77 5.3.1. Nullifying ACCM . . . . . . . . . . . . . . . . . . . 21 78 5.3.2. Other Stuffed Characters . . . . . . . . . . . . . . . 21 79 5.3.3. Applied Byte Stuffing . . . . . . . . . . . . . . . . 22 80 6. Security Considerations . . . . . . . . . . . . . . . . . . . 23 81 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24 82 8. Normative References . . . . . . . . . . . . . . . . . . . . . 25 83 Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 26 84 Appendix B. Proof of Formula for Finite Bit Stuffing . . . . . . 27 85 Appendix C. Explicit Calculation of Bit Stuffing Overhead for 86 IPv4 . . . . . . . . . . . . . . . . . . . . . . . . 28 87 Appendix D. Explicit Calculation of Bit Stuffing Overhead for 88 IPv6 . . . . . . . . . . . . . . . . . . . . . . . . 30 89 Appendix E. Terminology . . . . . . . . . . . . . . . . . . . . . 32 90 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 33 91 Intellectual Property and Copyright Statements . . . . . . . . . . 34 93 1. Introduction 95 Experience in benchmarking networking devices suggests that the 96 contents of test traffic can have a profound impact on test results. 97 For example, some devices may forward randomly addressed traffic 98 without loss, but drop significant numbers of packets when offered 99 packets containing nonrandom addresses. 101 Methodologies such as [RFC2544] and [RFC2889] do not require any 102 declaration of packet contents. These methodologies do require the 103 declaration of test parameters such as traffic distribution and 104 traffic orientation, and yet packet contents can have at least as 105 great an impact on test results as the other factors. Variations in 106 packet contents also can lead to non-repeatability of test results: 107 Two individuals may follow methodology procedures to the letter, and 108 still obtain very different results. 110 A related issue is the insertion of stuff bits or bytes by link-layer 111 technologies using PPP with HDLC-like framing. This stuffing is done 112 to ensure sequences in test traffic will not be confused with control 113 characters. 115 Stuffing adds significant and variable overhead. Currently there is 116 no standard method for determining the probability that stuffing will 117 occur for a given pattern, and thus no way to determine what impact 118 stuffing will have on test results. 120 This document covers two areas. First, we discuss strategies for 121 dealing with randomness and nonrandomness in test traffic. Second, 122 we present formulas to determine the probability of bit- and byte- 123 stuffing on point-to-point protocol (PPP) and packet over Sonet (POS) 124 circuits. In both areas, we provide recommendations for obtaining 125 better repeatability in test results. 127 Benchmarking activities as described in this memo are limited to 128 technology characterization using controlled stimuli in a laboratory 129 environment, using dedicated address space. 131 The benchmarking network topology will be an independent test setup 132 and MUST NOT be connected to devices that may forward the test 133 traffic into a production network, or misroute traffic to the test 134 management network. 136 2. Requirements 138 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 139 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 140 document are to be interpreted as described in [RFC2119]. 142 3. General considerations 144 3.1. Repeatability 146 Repeatability is a desirable trait in benchmarking, but it can be an 147 elusive goal. It is a common but mistaken belief that test results 148 can always be recreated provided the device under test and test 149 instrument are configured identically for each test iteration. In 150 fact, even identical configurations may introduce some variations in 151 test traffic, such as changes in timestamps, TCP sequence numbers, or 152 other common phenomena. 154 While this variability does not necessarily invalidate test results, 155 it is important to recognize the existing variation. Exact bit-for- 156 bit repeatability of test traffic is a hard problem. A simpler 157 approach is to acknowledge that some variation exists, characterize 158 that variation, and describe it when analyzing test results. 160 Another issue related to repeatability is the avoidance of randomness 161 in test traffic. For example, benchmarking experience with some IEEE 162 802.11 devices suggests that nonrandom media access control (MAC) and 163 IP addresses must be used across multiple trials. Although this 164 would seem to contradict some recommendations made in this document, 165 in fact either nonrandom or pseudorandom patterns may be more 166 desirable depending on the test setup. There are also situations 167 where it may be desirable to use combinations of the two, for example 168 by generating pseudorandom traffic patterns for one test trial and 169 then re-using the same pattern across all trials. The keywords in 170 this document are RECOMMENDs and not MUSTs with regard to the use of 171 pseudorandom test traffic patterns. 173 Note also that this discussion covers only repeatability, which is 174 concerned with variability of test results from trial to trial on the 175 same test bed. A separate concern is reproducibility, which refers 176 to the precision of test results obtained from different test beds. 177 Clearly, reproducibility across multiple test beds requires 178 repeatability on a single test bed. 180 3.2. Randomness 182 This document recommends the use of pseudorandom patterns in test 183 traffic under controlled lab conditions. The rand() functions 184 available in many programming languages produce output that is 185 pseudorandom rather than truly random. Pseudorandom patterns are 186 sufficient for the recommendations given in this document, provided 187 they produce output that is uniformly distributed across the pattern 188 space. 190 Specifically, for any random bit pattern of length L, the probability 191 of generating that specific pattern SHOULD equal 1 over 2 to the Lth 192 power. 194 4. Packet Content Variations 196 4.1. Problem Statement 198 The contents of test traffic can have a significant impact on metrics 199 such as throughput, jitter, latency, and loss. For example, many 200 network devices feed addresses into a hashing algorithm to determine 201 which path upon which to forward a given packet. 203 Consider the simple case of an Ethernet switch with eight network 204 processors (NPs) in its switching fabric: 206 ingress 207 || 208 \/ 209 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 210 | ___ ___ ___ ___ ___ ___ ___ ___ | 211 || | | | | | | | | | | | | | | | | 212 ||NP0| |NP1| |NP2| |NP3| |NP4| |NP5| |NP6| |NP7| | 213 ||___| |___| |___| |___| |___| |___| |___| |___| | 214 | | 215 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 216 || 217 \/ 218 egress 220 To assign incoming traffic to the various NPs, suppose a hashing 221 algorithm performs an exclusive-or (XOR) operation on the least 222 significant 3 bits of the source and destination MAC addresses in 223 each frame. (This is an actual example the authors have observed in 224 multiple devices from multiple manufacturers.) 226 In theory, a random distribution of source and destination MAC 227 addresses should result in traffic being uniformly distributed across 228 all eight NPs. (Instances of the term "random" in this document 229 refer to a random uniform distribution across a given address space. 230 Section 3.2 describes random uniform distributions in more detail.) 231 In practice, the actual outcome of the hash (and thus any test 232 results) will be very different depending on the degree of randomness 233 in test traffic. 235 Suppose the traffic is nonrandom so that every interface of the test 236 instrument uses this pattern in its source MAC addresses: 238 00:00:PP:00:00:01 239 where PP is the source interface number of the test instrument. 241 In this case, the least significant 3 bits of every source and 242 destination MAC address are 001, regardless of interface number. 243 Thus, the outcome of the XOR operation will always be 0, given the 244 same three least significant bits: 246 001 ^ 001 = 000 248 Thus, the switch will assign all traffic to NP0, leaving the other 249 seven NPs idle. Given a heavy enough load, NP0 and the switch will 250 become congested, even though seven other NPs are available. At 251 most, this device will be able to utilize approximately 12.5 percent 252 of its total capacity, with the remaining 87.5 percent of capacity 253 unused. 255 Now consider the same example with randomly distributed addresses. 256 In this case, the test instrument offers traffic using MAC addresses 257 with this pattern: 259 00:00:PP:00:00:RR 261 where PP is the source interface number of the test instrument and RR 262 is a pseudorandom number. In this case, there should be an equal 263 probability of the least significant 3 bits of the MAC address having 264 any value from 000 to 111 inclusive. Thus, the outcome of XOR 265 operations should be equally distributed from 0 to 7, and 266 distribution across NPs should also be equal (at least for this 267 particular 3-bit hashing algorithm). Absent other impediments, the 268 device should be able to utilize 100 percent of available capacity. 270 This simple example presumes knowledge on the tester's part of the 271 hashing algorithm used by the device under test. Knowledge of such 272 algorithms is not always possible beforehand, and in any event 273 violates the "black box" spirit of many documents produced by the 274 IETF Benchmarking Working Group (BMWG). 276 Therefore, this memo adds a new consideration for benchmarking 277 methodologies, to select traffic patterns that overcome the effects 278 of non-randomness regardless of the hashing algorithms in use. The 279 balance of this section offers recommendations for test traffic 280 patterns to avoid these effects, starting at the link layer and 281 working up to the application layer. 283 4.2. IEEE 802 MAC Addresses 285 Test traffic SHOULD use pseudorandom patterns in IEEE 802 MAC 286 addresses. The following source and destination MAC address pattern 287 is RECOMMENDED: 289 (RR & 0xFC):PP:PP:RR:RR:RR 291 where (RR & 0xFC) is a pseudorandom number bitwise ANDed with 0xFC, 292 PP:PP is the 1-indexed interface number of the test instrument and 293 RR:RR:RR is a pseudorandom number. 295 The bitwise ANDing of the high-order byte in the MAC address with 296 0xFC sets the low-order two bits of that byte to 0, guaranteeing a 297 non multicast address and a non locally administered address. Note 298 that the resulting addresses may violate IEEE 802 standards by using 299 organizationally unique identifiers (OUIs) not assigned to the test 300 port manufacturer. However, since these addresses will be used only 301 on isolated test networks there should be no possibility of mistaken 302 identity. 304 Test traffic SHOULD use PP:PP to identify the source interface number 305 of the test instrument. Such identification can be useful in 306 troubleshooting. Allocating 2 bytes of the MAC address for interface 307 identification allows for tests of up to 65,536 interfaces. A 2-byte 308 space allows for tests much larger than those currently used in 309 device benchmarking; however, tests involving more than 256 310 interfaces (fully utilizing a 1-byte space) are fairly common. 312 Note that the "PP:PP" designation refers to the source interface of 313 the test instrument, not the device under test/system under test 314 (DUT/SUT). There are situations where the DUT/SUT interface number 315 may change during the test; one example would be a test of wireless 316 LAN roaming. By referring to the (presumably static) source 317 interface number of the test instrument, test engineers can keep 318 track of test traffic regardless of any possible DUT/SUT changes. 320 Further, source interface numbers SHOULD be 1-indexed and SHOULD NOT 321 be 0-indexed. This avoids the low but nonzero probability of an 322 all-0s MAC address. Some devices will drop frames with all-0s MAC 323 addresses. 325 It is RECOMMENDED to use pseudorandom patterns in the least 326 significant 3 bytes of the MAC address. Using pseudorandom values 327 for the low-order 3 bytes means choosing one of 16.7 million unique 328 addresses. While this address space is vastly larger than is 329 currently required in lab benchmarking, it does assure more realistic 330 test traffic. 332 Note also that since only 30 of 48 bits in the MAC address have 333 pseudorandom values, there is no possibility of randomly generating a 334 broadcast or multicast value by accident. 336 4.2.1. Randomized Sets of MAC Addresses 338 It is common benchmarking practice for a test instrument to emulate 339 multiple hosts, even on a single interface. This is desirable in 340 assessing DUT/SUT scalability. 342 However, test instruments may emulate multiple MAC addresses by 343 incrementing and/or decrementing addresses from a fixed starting 344 point. This leads to situations as described above in "Address 345 Pattern Variations" where hashing algorithms produce nonoptimal 346 outcomes. 348 The outcome can be nonoptimal even if the set of addresses begins 349 with a pseudorandom number. For example, the following source/ 350 destination pairs will not be equally distributed by the 3-bit 351 hashing algorithm discussed above: 353 Source Destination 354 00:00:01:FC:B3:45 00:00:19:38:8C:80 355 00:00:01:FC:B3:46 00:00:19:38:8C:81 356 00:00:01:FC:B3:47 00:00:19:38:8C:82 357 00:00:01:FC:B3:48 00:00:19:38:8C:83 358 00:00:01:FC:B3:49 00:00:19:38:8C:84 359 00:00:01:FC:B3:4A 00:00:19:38:8C:85 360 00:00:01:FC:B3:4B 00:00:19:38:8C:86 361 00:00:01:FC:B3:4C 00:00:19:38:8C:87 363 Again working with our 3-bit XOR hashing algorithm, we get the 364 following outcomes: 366 101 ^ 000 = 101 367 110 ^ 001 = 111 368 111 ^ 010 = 101 369 000 ^ 011 = 011 370 001 ^ 100 = 101 371 010 ^ 101 = 111 372 011 ^ 110 = 101 373 100 ^ 111 = 011 375 Note that only three of eight possible outcomes are achieved when 376 incrementing addresses. This is actually the best case. 377 Incrementing from other combinations of pseudorandom address pairs 378 produces only one or two out of eight possible outcomes. 380 Every MAC address SHOULD be pseudorandom, not just the starting one. 382 When generating traffic with multiple addresses, it is RECOMMENDED 383 that all addresses use pseudorandom values. There are multiple ways 384 to use sets of pseudorandom numbers. One strategy would be for the 385 test instrument to iterate over an array of pseudorandom values 386 rather than incrementing/decrementing from a starting address. The 387 actual method is an implementation detail; in the end, any method 388 that uses multiple addresses with pseudorandom patterns will be 389 sufficient. 391 Experience with benchmarking of IEEE 802.11 devices suggests 392 suboptimal test outcomes may result if different pseudorandom MAC and 393 IP addresses are used from trial to trial. In such cases (not just 394 for 802.11 but for any device using IEEE 802 MAC and IP addresses), 395 testers MAY generate a pseudorandom set of MAC and IP addresses once, 396 or MAY generate a nonrandom set of MAC and IP addresses once. In 397 either case, the same MAC and IP addresses MUST be used in all 398 trials. 400 4.3. MPLS Addressing 402 Similar to L2 switches, multiprotocol label switching (MPLS) devices 403 make forwarding decisions based on a 20 bit MPLS label. Unless 404 specific labels are required, it is RECOMMENDED that uniformly random 405 values between 16 and 1,048,575 be used for all labels assigned by 406 test equipment. As per [RFC3032], this avoids using reserved MPLS 407 labels in the range of 0-15 inclusive. 409 4.4. Network-layer Addressing 411 When routers make forwarding decisions based solely on destination 412 network address, there may be no potential for hashing collision of 413 source and destination addresses, as in the case of Ethernet 414 switching discussed earlier. However, the potential still exists for 415 hashing collisions to exist at the network layer, and testers SHOULD 416 take this potential into consideration when crafting the network- 417 layer contents of test traffic. 419 For example, the equal cost multipath (ECMP) feature performs load- 420 sharing across multiple links. Routers implementing ECMP may perform 421 a hash of source and destination IP addresses in assigning flows. 423 Since multiple ECMP routes by definition have the same metric, 424 routers use some other "tiebreaker" mechanism to assign traffic to 425 each link. As far as the authors are aware, there is no standard 426 algorithm for ECMP link assignment. Some implementations perform a 427 hash of all bits of the source and destination IP addresses for this 428 purpose. Others may perform a hash on one or more bytes in the 429 source and destination IP addresses. 431 Just as in the case of MAC addresses, nonrandom IP addresses can have 432 an adverse effect on the outcome of ECMP link assignment decisions. 434 When benchmarking devices that implement ECMP or any other form of 435 Layer 3 aggregation, it is RECOMMENDED to use a randomly distributed 436 range of IP addresses. In particular, testers SHOULD NOT use 437 addresses that produce the undesired effects of address processing. 438 If, for example, a DUT can be observed to exhibit high packet loss 439 when offered IPv4 network addresses that take the form x.x.1.x/24, 440 and relatively low packet loss when the source and destination 441 network addresses take the form of x.x.R.x/24 (where R is some random 442 value between 0 and 9), test engineers SHOULD use the random pattern. 444 4.5. Transport-layer Addressing 446 Some devices with transport- or application-layer awareness use TCP 447 or UDP port numbers in making forwarding decisions. Examples of such 448 devices include load balancers and application-layer firewalls. 450 Test instruments have the capability of generating packets with 451 random TCP and UDP source and destination port numbers. Known 452 destination port numbers are often required for testing application- 453 layer devices. However, unless known port numbers are specifically 454 required for a test, it is RECOMMENDED to use pseudorandom and 455 uniformly distributed values for both source and destination port 456 numbers. 458 In addition, it may be desirable to pick pseudorandom values from a 459 selected pool of numbers. Many services identify themselves through 460 use of reserved destination port numbers between 1 and 49151 461 inclusive. Unless specific port numbers are required, it is 462 RECOMMENDED to pick randomly distributed destination port numbers 463 between these lower and upper boundaries. 465 Similarly, clients typically choose source port numbers in the space 466 between 1024 and 65535 inclusive. Unless specific port numbers are 467 required, it is RECOMMENDED to pick randomly distributed source port 468 numbers between these lower and upper boundaries. 470 4.6. Application-layer Patterns 472 Many measurements require the insertion of application-layer 473 header(s) and payload into test traffic. Application-layer packet 474 contents offer additional opportunities for stuffing to occur, and 475 may also present nonrandom outcomes when fed through application 476 layer-aware hashing algorithms. Given the vast number of 477 application-layer protocols in use, we make no recommendation for 478 specific test traffic patterns to be used; however, test engineers 479 SHOULD be aware that application-layer traffic contents MAY produce 480 nonrandom outcomes with some hashing algorithms. The same issues 481 that apply with lower-layer traffic patterns also apply at the 482 application layer. As discussed in section 5, the potential for 483 stuffing exists with any part of a test packet, including 484 application-layer contents. For example, some traffic generators 485 insert fields into packet payloads to distinguish test traffic. 486 These fields may contain a transmission timestamp; sequence number; 487 test equipment interface identifier and/or "stream" number; and a CRC 488 over the contents of the test payload or test packet. All these 489 fields are potential candidates for stuffing. 491 5. Control Character Stuffing 493 5.1. Problem Statement 495 Link-layer technologies that use high-level data link control (HDLC)- 496 like framing may insert an extra bit or byte before each instance of 497 a control character in traffic. These "stuffing" insertions prevent 498 confusion with control characters, but they may also introduce 499 significant overhead. Stuffing is data-dependent; thus selection of 500 different payload patterns will result in frames transmitted on the 501 media that vary in length, even though the original frames may all be 502 of the same length. 504 The overhead of these escape sequences is problematic for two 505 reasons. First, explicitly calculating the amount of overhead can be 506 non-trivial or even impossible for certain types of test traffic. In 507 such cases, the best testers can do is to characterize the 508 probability that an escape sequence will occur for a given pattern. 509 This greatly complicates the requirement of declaring exactly how 510 much traffic is offered to a DUT/SUT. 512 Second, in the absence of characterization and compensation for this 513 overhead, the tester may unwittingly congest the DUT/SUT. For 514 example, if a tester intends to offer traffic to a DUT at 95 percent 515 of line rate, but the link-layer protocol introduces an additional 1 516 percent of overhead to escape control characters, then the aggregate 517 offered load will be 96 percent of line rate. If the DUT's actual 518 channel capacity is only 95 percent, congestion will occur and the 519 DUT will drop traffic even though the tester did not intend this 520 outcome. 522 As described in [RFC1661] and [RFC1662], PPP and HDLC-like framing 523 introduce two kinds of escape sequences: bit and byte stuffing. Bit 524 stuffing refers to the insertion of an escape bit on bit-synchronous 525 links. Byte stuffing refers to the insertion of an escape byte on 526 byte-synchronous links. We discuss each in turn. 528 5.2. PPP Bit Stuffing 530 [RFC1662], section 5.2 specifies that any sequence of five contiguous 531 "1" bits within a frame must be escaped by inserting a "0" bit prior 532 to the sequence. This escaping is necessary to avoid confusion with 533 the HDLC control character 0x7E, which contains six "1" bits. 535 Consider the following PPP frame containing a TCP/IP packet. Not 536 shown is the 1-byte flag sequence (0x7E), at least one of which must 537 occur between frames. 539 The contents of the various frame fields can be described one of 540 three ways: 542 1. Field contents never change over the test duration. An example 543 would be the IP version number. 545 2. Field contents change over the test duration. Some of these 546 changes are known prior to the test duration. An example would 547 be the use of incrementing IP addresses. Some of these changes 548 are unknown. An example would be a dynamically calculated field 549 such as the TCP checksum. 551 3. Field contents may not be known. An example would be proprietary 552 payload fields in test packets. 554 In the diagram below, 30 out of 48 total bytes in the packet headers 555 are subject to change over the test duration. Additionally, the 556 payload field could be subject to change both content and size. The 557 fields containing the changeable bytes are given in ((double 558 parentheses)). 560 0 1 2 3 561 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 562 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 563 | Address | Control | Protocol | 564 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 565 |Version| IHL |Type of Service| Total Length | 566 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 567 | Identification |Flags| Fragment Offset | 568 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 569 | Time to Live | Protocol | ((Header Checksum)) | 570 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 571 | ((Source Address)) | 572 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 573 | ((Destination Address)) | 574 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 575 | ((Source Port)) | ((Destination Port)) | 576 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 577 | ((Sequence Number)) | 578 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 579 | ((Acknowledgment Number)) | 580 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 581 | Data | |U|A|P|R|S|F| | 582 | Offset| Reserved |R|C|S|S|Y|I| ((Window)) | 583 | | |G|K|H|T|N|N| | 584 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 585 | ((Checksum)) | Urgent Pointer | 586 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 587 | | 588 / ((payload)) / 589 | | 590 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 591 | ((FCS (4 bytes) )) | 592 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 594 None of the other fields are known to contain sequences subject to 595 bit-stuffing, at least not in their entirety. Note that there is no 596 payload in this simple example; as noted in section 4.6, the payload 597 contents of test traffic often will present additional opportunities 598 for stuffing to occur, and MUST be taken into account when 599 calculating stuff probability. 601 Given the information at hand, and assuming static contents for the 602 rest of the fields, the challenge is to determine the probability 603 that bit-stuffing will occur. 605 5.2.1. Calculating Bit-Stuffing Probability 607 In order to calculate bit-stuffing probabilities, we assume that for 608 any string of length L, where b_n represents the "n"th bit of the 609 string and 1 <= n <= L, the probability of b_n equalling "1" is 0.5 610 and the probability of b_n equalling "0" is 0.5. Additionally, the 611 value of b_n is independent of any other bits. 613 We can calculate the probability of bit-stuffing for both infinite 614 and finite strings of random bits. We begin with the infinite-string 615 case. For an infinitely long string of uniformly random bits, we 616 will need to insert a stuff bit if and only if state 5 is reached in 617 the following state table. 619 |--------------------<----------------------| 620 | |1 621 _______ __|__ _____ _____ _____ __|__ 622 | | 1 | | 1 | | 1 | | 1 | | 1 | | 623 | start |--->| 1 |--->| 2 |--->| 3 |--->| 4 |--->| 5 | 624 |_______| |_____| |_____| |_____| |_____| |_____| 625 | | | | | | | 626 | |0 |0 |0 |0 |0 |0 627 |-<-|----<----|----<-----|----<-----|----<-----|----<-----| 629 Initially, we begin in the "start" state. A "1" bit moves us into 630 the next highest state, and a "0" bit returns us to the start state. 631 From state 5, a "1" bit takes us back to the 1 state and a "0" bit 632 returns us to "start." 633 From this state diagram we can build the following transition matrix: 635 \ To | 636 \ | 637 \ | 638 From \ | start 1 2 3 4 5 639 ______\|_________________________________________________ 640 start | 0.5 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0 641 1 | 0.5 | 0.0 | 0.5 | 0.0 | 0.0 | 0.0 642 2 | 0.5 | 0.0 | 0.0 | 0.5 | 0.0 | 0.0 643 3 | 0.5 | 0.0 | 0.0 | 0.0 | 0.5 | 0.0 644 4 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0 | 0.5 645 5 | 0.5 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0 647 With this transition matrix we can build the following system of 648 equations. If P(x) represents the probability of reaching state x, 649 then: 651 P(start) = 0.5 * P(start) + 0.5 * P(1) + 0.5 * P(2) + 0.5 * P(3) + 652 0.5 * P(4) + 0.5 * P(5) 654 P(1) = 0.5 * P(start) + 0.5 * P(5) 655 P(2) = 0.5 * P(1) 656 P(3) = 0.5 * P(2) 657 P(4) = 0.5 * P(3) 658 P(5) = 0.5 * P(4) 660 P(start) + P(1) + P(2) + P(3) + P(4) + P(5) = 1 662 Solving this system of equations yields: 664 P(start) = 0.5 665 P(1) = 8/31 666 P(2) = 4/31 667 P(3) = 2/31 668 P(4) = 1/31 669 P(5) = 1/62 671 Thus, for an infinitely long string of uniformly random bits, the 672 probability of any individual bit causing a transition to state 5, 673 and thus causing a stuff, is 1/62. 675 5.2.2. Bit Stuffing for Finite Strings 677 For a uniformly random finite bit string of length L, we can 678 explicitly count the number of bit-stuffs in the set of all possible 679 strings of length L. This count can then be used to calculate the 680 expected number of stuffs for the string. 682 Let f(L) represent the number of bit-stuffs in the set of all 683 possible strings of length L. Clearly, for 0 <= L <= 4, f(L) = 0 as 684 there are no strings of length 5. For L >= 5, f(L) = 2^(L-5) + (L-5) 685 * 2^(L-6) + f(L-5). 687 A proof of this formula can be found in Appendix B. 689 Now, the expected number of stuffing events, E[stuffs], can be found 690 by dividing the total number of stuffs in all possible strings by the 691 total number of strings. Thus for any L, E[stuffs] = f(L) / 2^L. 693 Similarly, the probability that any particular bit is the cause of a 694 bit-stuff can be calculated by dividing the total number of stuffs in 695 the set of all strings of length L by the total number of bits in the 696 set of all strings of length L. Hence for any L, the probability that 697 L_n, where 5 <= n <= L, caused a stuff is f(L) / (L * 2^L). 699 5.2.3. Applied Bit Stuffing 701 The amount of overhead attributable to bit-stuffing may be calculated 702 explicitly as long as the expected number of stuff bits per frame, 703 E[bit-stuffs] is known. For long uniformly random bit-strings, 704 E[bit-stuffs] may be approximated by multiplying the length of the 705 string by 1/62. 707 % overhead = E[bit-stuffs] / framesize (in bits) 709 Given that the overhead added by bit-stuffing is approximately 1 in 710 62, or 1.6 percent, it is RECOMMENDED that testers reduce the maximum 711 intended load by 1.6 percent to avoid introducing congestion when 712 testing devices using bit-synchronous interfaces (such as T1/E1, 713 DS-3, and the like). 715 The percentage given above is an approximation. For greatest 716 precision, the actual intended load SHOULD be explicitly calculated 717 from the test traffic. 719 Note that the DUT/SUT may be able to forward intended loads higher 720 than the calculated theoretical maximum rate without packet loss. 721 Such results are the result of queuing on the part of the DUT/SUT. 722 While a device's throughput may be above this level, delay-related 723 measurements may be affected. Accordingly, it is RECOMMENDED to 724 reduce offered levels by the amount of bit-stuffing overhead when 725 testing devices using bit-synchronous links. This recommendation 726 applies for all measurements, including throughput. 728 5.3. POS Byte Stuffing 730 [RFC1662] requires that "Each Flag Sequence, Control Escape octet, 731 and any octet which is flagged in the sending Async-Control- 732 Character-Map (ACCM), is replaced by a two octet sequence consisting 733 of the Control Escape octet followed by the original octet exclusive- 734 or'd with hexadecimal 0x20." The practical effect of this is to 735 insert a stuff byte for instances of up to 34 characters: 0x7E, 0x7D, 736 or any of 32 ACCM values. 738 A common implementation of PPP in HDLC-like framing is in PPP over 739 Sonet/SDH (POS), as defined in [RFC2615]. 741 As with the bit-stuffing case, the requirement in characterizing POS 742 test traffic is to determine the probability that byte-stuffing will 743 occur for a given sequence. This is much simpler to do than with 744 bit-synchronous links, since there is no possibility of overlap 745 across byte boundaries. 747 5.3.1. Nullifying ACCM 749 Testers can greatly reduce the probability of byte-stuffing by 750 configuring link partners to negotiate an ACCM value of 0x00. It is 751 RECOMMENDED that testers configure the test instrument(s) and DUT/SUT 752 to negotiate an ACCM value of 0x00 unless specific ACCM values are 753 required. 755 One instance where nonzero ACCM values are used is in the layer 2 756 tunneling protocol (L2TP), as defined in [RFC2661], section 4.4.6. 757 When the default ACCM values are used, the probability of stuffing 758 for any given random byte is 34 in 256, or approximately 13.3 759 percent. 761 5.3.2. Other Stuffed Characters 763 If an ACCM value of 0x00 is negotiated, the only characters subject 764 to stuffing are the flag and control escape characters. Thus, we can 765 say that without ACCM the probability of stuffing for any given 766 random byte is 2 in 256, or approximately 0.8 percent. 768 5.3.3. Applied Byte Stuffing 770 The amount of overhead attributable to byte stuffing may be 771 calculated explicitly as long as the expected number of stuff bytes 772 per frame, E[byte-stuffs], is known. For long uniformly random byte- 773 strings, E[byte-stuffs] may be approximated by multiplying the length 774 of the string by the probability that any single byte is a stuff 775 byte. 777 % overhead = E[byte-stuffs] / framesize (in bytes) 779 When testing a DUT/SUT that implements PPP in HDLC-like framing and 780 L2TP (or any other technology that uses nonzero ACCM values), it is 781 RECOMMENDED that testers reduce the maximum intended load by 13.3 782 percent to avoid introducing congestion. 784 When testing a DUT/SUT that implements PPP in HDLC-like framing and 785 an ACCM value of 0x00, it is RECOMMENDED that testers reduce the 786 maximum intended load by 0.8 percent to avoid introducing congestion. 788 Note that the percentages given above are approximations. For 789 greatest precision, the actual intended load SHOULD be explicitly 790 calculated from the test traffic 792 Note also that the DUT/SUT may be able to forward intended loads 793 higher than the calculated theoretical maximum rate without packet 794 loss. Such results are the result of queuing on the part of the DUT/ 795 SUT. While a device's throughput may be above this level, delay- 796 related measurements may be affected. Accordingly, it is RECOMMENDED 797 to reduce offered levels by the amount of byte-stuffing overhead when 798 testing devices using byte-synchronous links. This recommendation 799 applies for all measurements, including throughput. 801 6. Security Considerations 803 This document recommends the use of pseudorandom patterns in test 804 traffic. This usage requires a uniform distribution, but does not 805 have strict predictability requirements. Although it is not 806 sufficient for security applications, the rand() function of many 807 programming languages may provide a uniform distribution that is 808 usable for testing purposes in lab conditions. Implementations of 809 rand() may vary and provide different properties so test designers 810 SHOULD understand the distribution created by the underlying function 811 and how seeding the initial state affects its behavior. 813 [RFC2615], section 6, discusses a denial-of-service attack involving 814 the intentional transmission of characters that require stuffing. 815 This attack could consume up to 100 percent of available bandwidth. 816 However, the test networks described in BMWG documents generally 817 SHOULD NOT be reachable by anyone other than the tester(s). 819 7. IANA Considerations 821 This document has no actions for IANA. 823 8. Normative References 825 [RFC1661] Simpson, W., "The Point-to-Point Protocol (PPP)", STD 51, 826 RFC 1661, July 1994. 828 [RFC1662] Simpson, W., "PPP in HDLC-like Framing", STD 51, RFC 1662, 829 July 1994. 831 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 832 Requirement Levels", BCP 14, RFC 2119, March 1997. 834 [RFC2544] Bradner, S. and J. McQuaid, "Benchmarking Methodology for 835 Network Interconnect Devices", RFC 2544, March 1999. 837 [RFC2615] Malis, A. and W. Simpson, "PPP over SONET/SDH", RFC 2615, 838 June 1999. 840 [RFC2661] Townsley, W., Valencia, A., Rubens, A., Pall, G., Zorn, 841 G., and B. Palter, "Layer Two Tunneling Protocol "L2TP"", 842 RFC 2661, August 1999. 844 [RFC2889] Mandeville, R. and J. Perser, "Benchmarking Methodology 845 for LAN Switching Devices", RFC 2889, August 2000. 847 [RFC3032] Rosen, E., Tappan, D., Fedorkow, G., Rekhter, Y., 848 Farinacci, D., Li, T., and A. Conta, "MPLS Label Stack 849 Encoding", RFC 3032, January 2001. 851 Appendix A. Acknowledgements 853 The authors gratefully acknowledge reviews and contributions by Tom 854 Alexander, Len Ciavattone, Robert Craig, John Dawson, Neil Carter, 855 Glenn Chagnot, Kevin Dubray, Diego Dugatkin, Rafael Francis, Paul 856 Hoffman, David Joyner, Al Morton, Joe Perches, Jerry Perser, Scott 857 Poretsky, Dan Romascanu, and Kris Rousey. 859 Appendix B. Proof of Formula for Finite Bit Stuffing 861 We would like to construct a function, f(L), that allows us to 862 explicitly count the total number of bit-stuffs in the set of all 863 strings of length L. Let S represent a bit string of length L. 864 Additionally, let b_n be the nth bit of string S where 1 <= n <= L. 866 Clearly, when 0 <= L <= 4, f(L) = 0, as there can be no possible bit- 867 stuff if there are < 5 bits. 869 Suppose L >= 5, then there are some number of strings that will cause 870 stuffing events. Let us count them. 872 We begin by counting the number of strings that will cause at least 873 one bit-stuff. Let us suppose that the first 5 bits, b_1,...,b_5, 874 cause a stuffing event. Then, there are (L-5) bits that could have 875 any value, i.e. the bits in position b_6 to b_L. So, there must be 876 2^(L-5) strings where the first 5 bits cause a stuff. 878 Now suppose that some other sequence of bits cause a stuff, b_n to 879 b_(n+4) for some 1 < n <= L-4. In order to guarantee that b_n starts 880 a stuff sequence, b_(n-1) must be 0, otherwise a stuff could occur at 881 b_(n+3). Thus, there are a total of 6 bits which must have fixed 882 values in the string, S, and a total of L-6 bits which do not have 883 fixed values. Hence, for each value of n, there are 2^(L-6) possible 884 strings with at least one bit-stuff for a total of (L-5) * 2^(L-6) 886 So, given a string of length L, where L >= 5, we know that there are 887 2^(L-5) + (L-5) * 2^(L-6) strings which will be transmitted with at 888 least one stuffed bit. However, if L >= 10, then there could be more 889 than one bit-stuff within the string S. Let Z represent a sequence of 890 5 sequential ones bits. Consider the bit string ..., b_n, b_(n+1), 891 b_(n+2), Z, b_(n+8), b_(n+9), ... where 1 <= n <= L-9. For the above 892 sequence of bits to generate two stuffing events, there must be at 893 least one run of five sequential one's bits in ..., b_n, b_(n+1), 894 b_(n+2), b_(n+8), b_(n+9), ... Note that the position of Z in the 895 above sequence is irrelevant when looking for bit-stuffs. 896 Additionally, we've already determined that the number of strings 897 with at least one stuff in a bit string of length L is 2^(L-5) + 898 (L-5) * 2^(L-6). Thus, the total number of stuffing events in the 899 set of all bit strings of length L can be represented as f(L) = 900 2^(L-5) + (L-5) * 2^(L-6) + f(L-5) for all L >= 5. 902 Appendix C. Explicit Calculation of Bit Stuffing Overhead for IPv4 904 Consider a scenario where a tester is transmitting IPv4 test packets 905 across a bit synchronous link. The test traffic has the following 906 parameters (values are in decimal): 908 +-----------------------+---------------------------+ 909 | Field | Value | 910 +-----------------------+---------------------------+ 911 | IP Version | 4 | 912 | | | 913 | IP Header Length | 5 | 914 | | | 915 | Type of service (TOS) | 0 | 916 | | | 917 | Datagram Length | 1028 | 918 | | | 919 | ID | 0 | 920 | | | 921 | Flags/Fragments | 0 | 922 | | | 923 | Time to live (TTL) | 64 | 924 | | | 925 | Protocol | 17 | 926 | | | 927 | Source IP | 192.18.13.1-192.18.13.254 | 928 | | | 929 | Destination IP | 192.18.1.10 | 930 | | | 931 | Source UDP Port | pseudorandom port | 932 | | | 933 | Destination UDP Port | pseudorandom port | 934 | | | 935 | UDP Length | 1008 | 936 | | | 937 | Payload | 1000 pseudorandom bytes | 938 +-----------------------+---------------------------+ 940 We want to calculate the expected number of stuffs per packet, or 941 E[packet stuffs]. 943 First, we observe that we have 254 different IP headers to consider, 944 and secondly, that the changing 4th octet in the IP source addresses 945 will produce occasional bit-stuffing events, so we must enumerate 946 these occurrences. Additionally, we must take into account that the 947 3rd octet of the source IP and the first octet of the destination IP 948 will affect stuffing occurrences. 950 An exhaustive search shows that cycling through all 254 headers 951 produces 51 bit stuffs for the destination IP address. This gives us 952 an expectation of 51/254 stuffs per packet due to the changing source 953 IP address. 955 For the IP CRC, we observe that the value will decrement as the 956 source IP is incremented. A little calculation shows that the CRC 957 values for these headers will fall in the range of 0xE790 to 0xE88F. 958 Additionally, both the protocol and source IP address must be 959 considered, as they provide a source of extra leading and trailing 960 ones bits. 962 An exhaustive search shows that cycling through all 254 headers will 963 produce 102 bit stuffs for the CRC. This gives us an expectation of 964 102/254 stuffs per packet due to the CRC. 966 Since our destination IP address is even and the UDP length is less 967 than 32768, the random source and destination ports provide 32 bits 968 of sequential random data without forcing us to consider the boundary 969 bits. Additionally, we will assume that since our payload is 970 pseudorandom, our UDP CRC will be too. The even UDP length field 971 again allows us to only consider the bits explicitly contained within 972 the CRC and data fields. So, using the formula for the expected 973 number of stuffs in a finite string from section 5.2.2, we determine 974 that E[UDP stuffs] = f(32)/2^32 + f(8000+16)/2^(8000+16). Now, 975 f(32)/2^32 is calculable without too much difficulty and is 976 approximately 0.465. However, f(8016)/2^8016 is a little large to 977 calculate easily, so we will approximate this value by using the 978 probability value obtained in section 5.2.1. Thus, E[UDP] ~ 0.465 + 979 8016/62 ~ 129.755. 981 Hence, E[packet stuffs] = 51/254 + 102/254 + 129.755 = 130.357. 982 However, since we cannot have a fractional stuff, we round down to 983 130. Thus, we expect 130 stuffs per packet. 985 Finally, we can calculate bit-stuffing overhead by dividing the 986 expected number of stuff bits by the total number of bits in the IP 987 datagram. So, this example traffic would generate 1.58% overhead. 988 If our payload had consisted exclusively of zero bits, our overhead 989 would have been 0.012%. An all ones payload would produce 19.47% 990 overhead. 992 Appendix D. Explicit Calculation of Bit Stuffing Overhead for IPv6 994 Consider a scenario where a tester is transmitting IPv6 test packets 995 across a bit synchronous link. The test traffic has the following 996 parameters (values are in decimal except for IPv6 addresses, which 997 are in hexadecimal): 999 +----------------------+----------------------------------+ 1000 | Field | Value | 1001 +----------------------+----------------------------------+ 1002 | IP Version | 6 | 1003 | | | 1004 | Traffic Class | 0 | 1005 | | | 1006 | Flow Label | pseudorandom label | 1007 | | | 1008 | Payload Length | 1008 | 1009 | | | 1010 | Next Header | 17 | 1011 | | | 1012 | Hop Limit | 64 | 1013 | | | 1014 | Source IP | 2001:DB8:0:1::1-2001:DB8:0:1::FF | 1015 | | | 1016 | Destination IP | 2001:DB8:0:2::10 | 1017 | | | 1018 | Source UDP Port | pseudorandom port | 1019 | | | 1020 | Destination UDP Port | pseudorandom port | 1021 | | | 1022 | UDP Length | 1008 | 1023 | | | 1024 | Payload | 1000 pseudorandom bytes | 1025 +----------------------+----------------------------------+ 1027 We want to calculate the expected number of stuffs per packet, or 1028 E[packet stuffs]. 1030 First, we observe that we have 255 different IP headers to consider, 1031 and secondly, that the changing 4th quad in the IP source addresses 1032 will produce occasional bit-stuffing events, so we must enumerate 1033 these occurrences. Additionally, we also note that since the first 1034 quad of the destination address has a leading zero bit, we do no have 1035 to consider these adjacent bits when calculating the number of bit 1036 stuffs in the source IP address. 1038 An exhaustive search shows that cycling through all 255 headers 1039 produces 20 bit stuffs for the source IP address. This gives us an 1040 expectation of 20/255 stuffs per packet due to the changing source IP 1041 address. 1043 We also have to consider our pseudorandomly generated flow label. 1044 However, since our Traffic Class field is 0 and our Payload Length 1045 field is less than 32768 (and thus the leading bit of the Payload 1046 Length field is 0), we may consider the flow label as 20 bits of 1047 random data. Thus the expectation of a stuff in the flow label is 1048 f(20)/2^20 ~ .272. 1050 Similar to the flow label case above, the fourth quad of our 1051 destination IP address is even and the UDP length field is less than 1052 32768, so the random source and destination ports provide 32 bits of 1053 sequential random data without forcing us to consider the boundary 1054 bits. Additionally, we will assume that since our payload is 1055 pseudorandom, our UDP CRC will be too. The even UDP length field 1056 again allows us to only consider the bits explicitly contained within 1057 the CRC and data fields. So, using the formula for the expected 1058 number of stuffs in a finite string from section 5.2.2, we determine 1059 that E[UDP stuffs] = f(32)/2^32 + f(8000+16)/2^(8000+16). Now, 1060 f(32)/2^32 is calculable without too much difficulty and is 1061 approximately 0.465. However, f(8016)/2^8016 is a little large to 1062 calculate easily, so we will approximate this value by using the 1063 probability value obtained in section 5.2.1. Thus, E[UDP stuffs] ~ 1064 0.465 + 8016/62 ~ 129.755. 1066 Now we may explicitly calculate that E[packet stuffs] = 20/255 + 1067 0.272 + 129.755 = 130.105. However, since we cannot have a 1068 fractional stuff, we round down to 130. Thus, we expect 130 stuffs 1069 per packet. 1071 Finally, we can calculate bit-stuffing overhead by dividing the 1072 expected number of stuff bits by the total number of bits in the IP 1073 datagram. So, this example traffic would generate 1.55% overhead. 1074 If our payload had consisted exclusively of zero bits, our overhead 1075 would have been 0.010%. An all ones payload would produce 19.09% 1076 overhead. 1078 Appendix E. Terminology 1080 Hashing 1082 Also known as a hash function. In the context of this document, an 1083 algorithm for transforming data for use in path selection by a 1084 networking device. For example, an Ethernet switch with multiple 1085 processing elements might use the source and destination MAC 1086 addresses of an incoming frame as input for a hash function. The 1087 hash function produces numeric output that tells the switch which 1088 processing element to use in forwarding the frame. 1090 Randomness 1092 In the context of this document, the quality of having an equal 1093 probability of any possible outcome for a given pattern space. For 1094 example, if an experiment has N randomly distributed outcomes, then 1095 any individual outcome has a 1 in N probability of occurrence. 1097 Repeatability 1099 The precision of test results obtained on a single test bed, but from 1100 trial to trial. See also "reproducibility." 1102 Reproducibility 1104 The precision of test results between different setups, possibly at 1105 different locations. See also "repeatability." 1107 Stuffing 1109 The insertion of a bit or byte within a frame to avoid confusion with 1110 control characters. For example, RFC 1662 requires the insertion of 1111 a 0 bit prior to any sequence of five contiguous 1 bits within a 1112 frame to avoid confusion with the HDLC control character 0x7E. 1114 Authors' Addresses 1116 David Newman 1117 Network Test 1119 Email: dnewman@networktest.com 1121 Timmons C. Player 1122 Spirent Communications 1124 Email: timmons.player@spirent.com 1126 Full Copyright Statement 1128 Copyright (C) The IETF Trust (2006). 1130 This document is subject to the rights, licenses and restrictions 1131 contained in BCP 78, and except as set forth therein, the authors 1132 retain all their rights. 1134 This document and the information contained herein are provided on an 1135 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1136 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 1137 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 1138 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 1139 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1140 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1142 Intellectual Property 1144 The IETF takes no position regarding the validity or scope of any 1145 Intellectual Property Rights or other rights that might be claimed to 1146 pertain to the implementation or use of the technology described in 1147 this document or the extent to which any license under such rights 1148 might or might not be available; nor does it represent that it has 1149 made any independent effort to identify any such rights. Information 1150 on the procedures with respect to rights in RFC documents can be 1151 found in BCP 78 and BCP 79. 1153 Copies of IPR disclosures made to the IETF Secretariat and any 1154 assurances of licenses to be made available, or the result of an 1155 attempt made to obtain a general license or permission for the use of 1156 such proprietary rights by implementers or users of this 1157 specification can be obtained from the IETF on-line IPR repository at 1158 http://www.ietf.org/ipr. 1160 The IETF invites any interested party to bring to its attention any 1161 copyrights, patents or patent applications, or other proprietary 1162 rights that may cover technology that may be required to implement 1163 this standard. Please address the information to the IETF at 1164 ietf-ipr@ietf.org. 1166 Acknowledgment 1168 Funding for the RFC Editor function is provided by the IETF 1169 Administrative Support Activity (IASA).