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