idnits 2.17.1 draft-ietf-bmwg-hash-stuffing-00.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 3667, Section 5.1 on line 16. -- Found old boilerplate from RFC 3978, Section 5.5 on line 745. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 717. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 724. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 730. ** Found boilerplate matching RFC 3978, Section 5.4, paragraph 1 (on line 751), which is fine, but *also* found old RFC 2026, Section 10.4C, paragraph 1 text on line 38. ** The document seems to lack an RFC 3978 Section 5.1 IPR Disclosure Acknowledgement -- however, there's a paragraph with a matching beginning. Boilerplate error? ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. ** The document uses RFC 3667 boilerplate or RFC 3978-like boilerplate instead of verbatim RFC 3978 boilerplate. After 6 May 2005, submission of drafts without verbatim RFC 3978 boilerplate is not accepted. The following non-3978 patterns matched text found in the document. That text should be removed or replaced: By submitting this Internet-Draft, I certify that any applicable patent or other IPR claims of which I am aware have been disclosed, or will be disclosed, and any of which I become aware will be disclosed, in accordance with RFC 3668. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 18 longer pages, the longest (page 19) being 73 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 22 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 647 has weird spacing: '...sion of chara...' == The document seems to use 'NOT RECOMMENDED' as an RFC 2119 keyword, but does not include the phrase in its RFC 2119 key words list. -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (July 10, 2004) is 7230 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: 'Ca63' is defined on line 685, but no explicit reference was found in the text == Unused Reference: 'Go97' is defined on line 688, 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: 8 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: January 8, 2005 T. Player 5 Spirent Communications 6 July 10, 2004 8 Hash and Stuffing: Overlooked Factors in Network Device Benchmarking 9 draft-ietf-bmwg-hash-stuffing-00.txt 11 Status of this Memo 13 By submitting this Internet-Draft, I certify that any applicable 14 patent or other IPR claims of which I am aware have been disclosed, 15 and any of which I become aware will be disclosed, in accordance with 16 RFC 3668. 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 21 Internet-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 January 8, 2005. 36 Copyright Notice 38 Copyright (C) The Internet Society (2004). All Rights Reserved. 40 Abstract 42 Test engineers take pains to declare all factors that affect a given 43 measurement, including offered load, packet length, test duration, 44 and traffic orientation. However, current benchmarking practice 45 overlooks two factors that have a profound impact on test results. 46 First, existing methodologies do not require the reporting of 47 addresses or other test traffic contents, even though these fields 48 can affect test results. Second, "stuff" bits and bytes inserted in 49 test traffic by some link-layer technologies add significant and 50 variable overhead, which in turn affects test results. This document 51 describes the effects of these factors; recommends guidelines for 52 test traffic contents; and offers formulas for determining the 53 probability of bit- and byte-stuffing in test traffic. 55 Table of Contents 57 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 58 2. Requirements . . . . . . . . . . . . . . . . . . . . . . . . . 4 59 3. General considerations . . . . . . . . . . . . . . . . . . . . 5 60 3.1 Repeatability . . . . . . . . . . . . . . . . . . . . . . 5 61 3.2 Randomness . . . . . . . . . . . . . . . . . . . . . . . . 5 62 4. Address Pattern Variations . . . . . . . . . . . . . . . . . . 6 63 4.1 Problem Statement . . . . . . . . . . . . . . . . . . . . 6 64 4.2 Ethernet MAC Addresses . . . . . . . . . . . . . . . . . . 7 65 4.2.1 Randomized Sets of MAC Addresses . . . . . . . . . . . 8 66 4.3 Network-layer Addressing . . . . . . . . . . . . . . . . . 9 67 4.4 Transport-layer Addressing . . . . . . . . . . . . . . . . 10 68 5. Control Character Stuffing . . . . . . . . . . . . . . . . . . 11 69 5.1 Problem Statement . . . . . . . . . . . . . . . . . . . . 11 70 5.2 PPP Bit Stuffing . . . . . . . . . . . . . . . . . . . . . 11 71 5.2.1 Calculating Bit-Stuffing Probability . . . . . . . . . 13 72 5.2.2 Bit Stuffing for Finite Strings . . . . . . . . . . . 14 73 5.2.3 Applied Bit Stuffing . . . . . . . . . . . . . . . . . 14 74 5.3 POS Byte Stuffing . . . . . . . . . . . . . . . . . . . . 15 75 5.3.1 Nullifying ACCM . . . . . . . . . . . . . . . . . . . 15 76 5.3.2 Other Stuffed Characters . . . . . . . . . . . . . . . 15 77 5.3.3 Applied Byte Stuffing . . . . . . . . . . . . . . . . 15 78 6. Security Considerations . . . . . . . . . . . . . . . . . . . 17 79 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 80 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19 81 8.1 Normative References . . . . . . . . . . . . . . . . . . . . 19 82 8.2 Informative References . . . . . . . . . . . . . . . . . . . 19 83 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 19 84 A. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 20 85 Intellectual Property and Copyright Statements . . . . . . . . 21 87 1. Introduction 89 Experience in benchmarking networking devices suggests that the 90 contents of test traffic can have a profound impact on test results. 91 For example, some devices may forward randomly addressed traffic 92 without loss, but drop significant numbers of packets when offered 93 packets containing nonrandom addresses. 95 Methodologies such as [RFC2544] and [RFC2889] do not require any 96 declaration of packet contents. These methodologies do require the 97 declaration of test parameters such as traffic distribution and 98 traffic orientation, and yet packet contents can have at least as 99 great an impact on test results as the other factors. Variations in 100 packet contents also can lead to non-repeatability of test results: 101 Two individuals may follow methodology procedures to the letter, and 102 still obtain very different results. 104 A related issue is the insertion of stuff bits or bytes by link-layer 105 technologies using PPP with HDLC-like framing. This stuffing is done 106 to ensure sequences in test traffic will not be confused with flag or 107 control characters. 109 Stuffing adds significant and variable overhead. Currently there is 110 no standard method for determining the probability that stuffing will 111 occur for a given pattern, and thus no way to determine what impact 112 stuffing will have on test results. 114 This document covers two areas. First, we discuss strategies for 115 dealing with randomness and nonrandomness in test traffic. Second, 116 we present formulas to determine the probability of bit- and 117 byte-stuffing on PPP and POS circuits. In both areas, we provide 118 recommendations for obtaining more repeatability in test results. 120 2. Requirements 122 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 123 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 124 document are to be interpreted as described in [RFC2119]. 126 3. General considerations 128 3.1 Repeatability 130 Repeatability is a desirable trait in benchmarking, but it can be an 131 elusive goal. It is a common but mistaken belief that test results 132 can always be reproduced provided the device under test and test 133 instrument are configured are configured identically for each test 134 iteration. In fact, even identical configurations may introduce some 135 variations in test traffic, such as changes in timestamps, TCP 136 sequence numbers, or other naturally occurring phenomena. 138 While this variability does not necessarily invalidate test results, 139 it is important to recognize such variation exists. Exact 140 bit-for-bit reproduction of test traffic in all cases is a hard 141 problem. A simpler approach is to acknowledge that some variation 142 exists, characterize that variation, and describe it when analyzing 143 test results. 145 3.2 Randomness 147 This document recommends the use of pseudorandom patterns in test 148 traffic under controlled lab conditions. The rand() functions of 149 many programming languages produce output that is pseudorandom rather 150 than truly random. Pseudorandom patterns are sufficient for the 151 recommendations given in this document, provided they produce an even 152 distribution of outcomes from the hashing algorithm of the device or 153 system under test. 155 4. Address Pattern Variations 157 4.1 Problem Statement 159 The addresses and port numbers used in a test can have a significant 160 impact on metrics such as throughput, jitter, latency, and loss. 161 This is because many network devices feed such addresses into hashing 162 algorithms to determine which path upon which to forward a given 163 packet. 165 Consider the simple example of an Ethernet switch with eight network 166 processors (NPs) in its switching fabric: 168 ingress 169 || 170 \/ 171 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 172 | ___ ___ ___ ___ ___ ___ ___ ___ | 173 || | | | | | | | | | | | | | | | | 174 ||NP0| |NP1| |NP2| |NP3| |NP4| |NP5| |NP6| |NP7| | 175 ||___| |___| |___| |___| |___| |___| |___| |___| | 176 | | 177 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 178 || 179 \/ 180 egress 182 To assign incoming traffic to the various NPs, suppose a hashing 183 algorithm performs an exclusive-or (XOR) operation on the least 184 significant 3 bits of the source and destination MAC addresses in 185 each frame. (This is an actual example the authors have observed in 186 multiple devices from multiple manufacturers.) 188 In theory, a random distribution of source and destination MAC 189 addresses should result in traffic being evenly distributed across 190 all eight NPs. In practice, the actual outcome of the hash (and thus 191 any test results) will be very different depending on the amount of 192 randomness in test traffic. 194 Suppose the traffic is nonrandom so that every interface of the test 195 instrument uses this pattern in its source MAC addresses: 197 00:00:PP:00:00:01 199 where PP is the source interface number of the test instrument. 201 In this case, the least significant 3 bits of every source and 202 destination MAC address are 001, regardless of interface number. 203 Thus, the outcome of the XOR operation will always be 0, given the 204 same three least significant bits: 206 001 ^ 001 = 000 208 Thus, the switch will assign all traffic to NP0, leaving the other 209 seven NPs idle. Given a heavy enough load, NP0 and the switch will 210 become congested, even though seven other NPs are available. At 211 most, this device will be able to utilize approximately 12.5 percent 212 of its total capacity, with the remaining 87.5 percent of capacity 213 unused. 215 Now consider the same example with randomly distributed addresses. 216 In this case, the test instrument offers traffic using MAC addresses 217 with this pattern: 219 00:00:PP:00:00:RR 221 where PP is the source interface number of the test instrument and RR 222 is a pseudorandom number. In this case, there should be an equal 223 probability of the least significant 3 bits of the MAC address having 224 any value from 000 to 111 inclusive. Thus, the outcome of XOR 225 operations should be evenly distributed from 0 to 7, and distribution 226 across NPs should also be even (at least for this particular 3-bit 227 hashing algorithm). Absent other impediments, the device should be 228 able to utilize 100 percent of available bandwidth. 230 This simple example presumes knowledge on the tester's part of the 231 hashing algorithm used by the device under test. Knowledge of such 232 algorithms is not always possible beforehand, and in any event 233 violates the "black box" spirit of many documents produced by the 234 IETF BMWG. 236 The balance of this section offers recommendations for test traffic 237 patterns, starting at the link layer and working up to the transport 238 layer. These patterns should overcome the effects of nonrandomness 239 regardless of the hashing algorithms in use. 241 4.2 Ethernet MAC Addresses 243 The following source and destination Ethernet address pattern is 244 RECOMMENDED for use when benchmarking Ethernet devices: 246 00:PP:PP:RR:RR:RR 248 where PP:PP is the interface number of the test instrument and 249 RR:RR:RR is a pseudorandom number. 251 It is NOT RECOMMENDED that testers randomize the high-order byte in 252 the MAC address. If the high-order byte were randomized, there is a 253 low but nonzero probability of generating a frame with a MAC address 254 beginning 01:00:5E. That pattern is reserved for multicast use. 256 It is RECOMMENDED to use PP:PP to identify the source interface 257 number of the test instrument. Such identification can be useful in 258 troubleshooting. Allocating 2 bytes of the MAC address for interface 259 identification allows for tests of up to 65,536 interfaces. A 2-byte 260 space allows for tests much larger than those currently used in 261 device benchmarking; however, tests involving more than 256 262 interfaces (fully utilizing a 1-byte space) are fairly common. 264 It is RECOMMENDED to use pseudorandom patterns in the least 265 significant 3 bytes of the MAC address. Using pseudorandom values 266 for the low-order 3 bytes means choosing one of 16.7 million unique 267 addresses. While this address space is vastly larger than is 268 currently required in lab benchmarking, it does assure greater 269 randomness in test traffic. 271 Note also that since only 3 out of 6 bytes in the MAC address have 272 pseudorandom values, there is no possibility of randomly generating a 273 broadcast or multicast value by accident. 275 4.2.1 Randomized Sets of MAC Addresses 277 It is common benchmarking practice for a test instrument to emulate 278 multiple hosts, even on a single interface. This is desirable in 279 assessing DUT/SUT scalability. 281 However, test instruments may emulate multiple MAC addresses by 282 incrementing and/or decrementing addresses from a fixed starting 283 point. This leads to situations as described above in "Address 284 Pattern Variations" where hashing algorithms produce nonrandom 285 outcomes. 287 The outcome can be nonrandom even if the set of addresses begins with 288 a pseudorandom number. For example, the following source/destination 289 pairs will not be evenly distributed by the 3-bit hashing algorithm 290 discussed above: 292 Source Destination 293 00:00:01:FC:B3:45 00:00:19:38:8C:80 294 00:00:01:FC:B3:46 00:00:19:38:8C:81 295 00:00:01:FC:B3:47 00:00:19:38:8C:82 296 00:00:01:FC:B3:48 00:00:19:38:8C:83 297 00:00:01:FC:B3:49 00:00:19:38:8C:84 298 00:00:01:FC:B3:50 00:00:19:38:8C:85 299 00:00:01:FC:B3:51 00:00:19:38:8C:86 300 00:00:01:FC:B3:52 00:00:19:38:8C:87 301 ... 303 Again working with our 3-bit XOR hashing algorithm, we get the 304 following outcomes: 306 101 ^ 000 = 101 307 110 ^ 001 = 111 308 111 ^ 010 = 101 309 000 ^ 011 = 011 310 001 ^ 100 = 101 311 010 ^ 101 = 111 312 011 ^ 110 = 101 313 100 ^ 111 = 011 315 Note that only three of eight possible outcomes are achieved when 316 incrementing addresses. This is actually the best case. 317 Incrementing from other combinations of pseudorandom address pairs 318 produces only one or two out of eight possible outcomes. 320 Every MAC address should be pseudorandom, not just the starting one. 322 When generating traffic with multiple addresses, it is RECOMMENDED 323 that all addresses use pseudorandom values. There are multiple ways 324 to use sets of pseudorandom numbers. One strategy would be for the 325 test instrument to iterate over an array of pseudorandom values 326 rather than incrementing/decrementing from a starting address. 327 Another method would be to increment/decrement using steps that are 328 relatively prime to the hash table. The actual method is an 329 implementation detail; in the end, any method that uses multiple 330 addresses and avoids hash table collisions will be sufficient. 332 4.3 Network-layer Addressing 334 Routers make forwarding decisions based on destination network 335 address. Since there is no hashing of source and destination 336 addresses, the requirement for pseudorandom patterns at the network 337 layer is far less critical than in the Ethernet MAC address case. 339 However, there are cases where randomly distributed IPv4 addresses 340 are desirable. For example, the equal cost multipath (ECMP) feature 341 performs load-sharing across multiple links. Routers implementing 342 ECMP may perform a hash of source and destination IP addresses in 343 assigning flows. 345 Since multiple ECMP routes by definition have the same metric, 346 routers use some other "tiebreaker" mechanism to assign traffic to 347 each link. As far as the authors are aware, there is no standard 348 algorithm for ECMP link assignment. Some implementations perform a 349 hash of all bits of the source and destination IP addresses for this 350 purpose. 352 Just as in the case of MAC addresses, nonrandom IP addresses can have 353 an adverse effect on the outcome of ECMP link assignment decisions. 355 When benchmarking devices that implement ECMP, it is RECOMMENDED to 356 use IP addresses that will produce an even distribution across paths. 358 4.4 Transport-layer Addressing 360 Some devices with transport- or application-layer awareness use TCP 361 or UDP port numbers in making forwarding decisions. Examples of such 362 devices include load balancers and application-layer firewalls. 364 Test instruments have the capability of generating packets with 365 random TCP and UDP source and destination port numbers. Known 366 destination port numbers are often required for testing 367 application-layer devices. However, unless known port numbers are 368 specifically required for a test, it is RECOMMENDED to use 369 pseudorandom values for both source and destination port numbers. 371 In addition, it may be desirable to pick pseudorandom values from a 372 selected pool of numbers. Many services identify themselves through 373 use of reserved destination port numbers between 1 and 1023 374 inclusive. Unless specific port numbers are required, it is 375 RECOMMENDED to pick destination port numbers at random between these 376 lower and upper boundaries. 378 Similarly, clients typically choose source port numbers in the space 379 between 1024 and 65535 inclusive. Unless specific port numbers are 380 required, it is RECOMMENDED to pick source port numbers at random 381 between these lower and upper boundaries. 383 5. Control Character Stuffing 385 5.1 Problem Statement 387 Link-layer technologies that use HDLC-like framing may insert an 388 extra bit or byte before each instance of a control character in 389 traffic. These insertions prevent confusion with control characters, 390 but they may also introduce significant overhead. 392 The overhead of these escape sequences is problematic for two 393 reasons. First, the amount of overhead is non-deterministic. The 394 best testers can do is to characterize the probability that an escape 395 sequence will occur for a given pattern. This greatly complicates 396 the requirement of declaring exactly how much traffic is offered to a 397 DUT/SUT. 399 Second, in the absence of characterization and compensation for this 400 overhead, the tester may unwittingly congest the DUT/SUT. For 401 example, if a tester intends to offer traffic to a DUT at 95 percent 402 of line rate, but the link-layer protocol introduces an additional 1 403 percent of overhead to escape control characters, then the aggregate 404 offered load will be 96 percent of line rate. If the DUT's actual 405 channel capacity is only 95 percent, congestion will occur and the 406 DUT will drop traffic even though the tester did not intend this 407 outcome. 409 As described in [RFC1661] and [RFC1662], PPP and HDLC-like framing 410 introduce two kinds of escape sequences: bit and byte stuffing. Bit 411 stuffing refers to the insertion of an escape bit on bit-synchronous 412 links. Byte stuffing refers to the insertion of an escape byte on 413 byte-synchronous links. We discuss each in turn. 415 5.2 PPP Bit Stuffing 417 [RFC1662], section 5.2 specifies that any sequence of five contiguous 418 "1" bits within a frame must be escaped by inserting a "0" bit prior 419 to the sequence. This escaping is necessary to avoid confusion with 420 the HDLC control character 0x7D, which contains six "1" bits. 422 Consider the following PPP frame containing a TCP/IP packet. Not 423 shown is the 1-byte flag sequence (0x7D), at least one of which must 424 occur between frames. 426 The contents of the various frame fields can be described one of two 427 ways: 429 1. Field contents never change over the test duration. An example 430 would be the IP version number. 432 2. Field contents change over the test duration. Some of these 433 changes are known prior to the test duration. An example would 434 be the use of incrementing IP addresses. Some of these changes 435 are unknown. An example would be a dynamically calculated field 436 such as the TCP checksum. 438 In the diagram below, 30 out of 48 total bytes are subject to change 439 over the test duration. The fields containing the changeable bytes 440 are given in ((double parentheses)). 442 0 1 2 3 443 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 444 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 445 | Address | Control | Protocol | 446 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 447 |Version| IHL |Type of Service| Total Length | 448 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 449 | Identification |Flags| Fragment Offset | 450 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 451 | Time to Live | Protocol | ((Header Checksum)) | 452 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 453 | ((Source Address)) | 454 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 455 | ((Destination Address)) | 456 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 457 | ((Source Port)) | ((Destination Port)) | 458 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 459 | ((Sequence Number)) | 460 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 461 | ((Acknowledgment Number)) | 462 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 463 | Data | |U|A|P|R|S|F| | 464 | Offset| Reserved |R|C|S|S|Y|I| ((Window)) | 465 | | |G|K|H|T|N|N| | 466 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 467 | ((Checksum)) | Urgent Pointer | 468 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 469 | ((FCS (4 bytes) )) | 470 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 472 None of the other fields are known to contain sequences subject to 473 bit-stuffing, at least not in their entirety. 475 However, some fields may contain one or more "1" bits adjacent to 476 fields that change. For example, if the low-order octet of the IP 477 destination address has a value of 1 this could place a "1" bit 478 adjacent to the source port, which is a variable. 480 Given the information at hand, and assuming static contents for the 481 rest of the fields, the challenge is to determine the probability 482 that bit-stuffing will occur. 484 5.2.1 Calculating Bit-Stuffing Probability 486 We can calculate the probability of bit stuffing for both infinite 487 and finite strings of random bits. We begin with the infinite-string 488 case, which is required to prove the finite-string case. For an 489 infinitely long string of random bits, we will need to insert a stuff 490 bit if and only if state 5 is reached in the following state table. 492 |--------------------<----------------------| 493 | |1 494 _______ ___|__ ______ ______ ______ ___|__ 495 | | 1 | | 1 | | 1 | | 1 | | 1 | | 496 | start |--->| 1 |--->| 2 |--->| 3 |--->| 4 |--->| 5 | 497 |_______| |_____| |_____| |_____| |_____| |_____| 498 | | | | | | | 499 | |0 |0 |0 |0 |0 |0 500 |-<-|----<----|----<-----|----<-----|----<-----|----<-----| 502 Initially, we begin in the "start" state. A 1 bit moves us into the 503 next highest state, and a 0 bit returns us to the start state. From 504 state 5, a 1 bit takes us back to the 1 state and a 0 bit returns us 505 to "start." From this state table we can build the following 506 transition matrix: 508 | start 1 2 3 4 5 509 ______|_________________________________________________ 510 start | 0.5 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0 511 1 | 0.5 | 0.0 | 0.5 | 0.0 | 0.0 | 0.0 512 2 | 0.5 | 0.0 | 0.0 | 0.5 | 0.0 | 0.0 513 3 | 0.5 | 0.0 | 0.0 | 0.0 | 0.5 | 0.0 514 4 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0 | 0.5 515 5 | 0.5 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0 517 With this transition matrix we can build the following system of 518 equations. If P(x) represents the probability of reaching state x, 519 then: 521 P(start) = 0.5 * P(start) + 0.5 * P(1) + 0.5 * P(2) + 0.5 * P(3) + 522 0.5 * P(4) + 0.5 * P(5) 524 P(1) = 0.5 * P(start) + 0.5 * P(5) 525 P(2) = 0.5 * P(1) 526 P(3) = 0.5 * P(2) 527 P(4) = 0.5 * P(3) 528 P(5) = 0.5 * P(4) 530 P(start) + P(1) + P(2) + P(3) + P(4) + P(5) = 1 532 Solving this system of equations yields: 534 P(start) = 0.5 535 P(1) = 8/31 536 P(2) = 4/31 537 P(3) = 2/31 538 P(4) = 1/31 539 P(5) = 1/62 541 Thus, for an infinitely long string of random bits, the probability 542 of 5 sequential 1 bits is 1 in 62. 544 5.2.2 Bit Stuffing for Finite Strings 546 TBD 548 5.2.3 Applied Bit Stuffing 550 Given that the overhead added by bit-stuffing is 1 in 62, or 551 approximately 1.6 percent, it is RECOMMENDED that testers reduce the 552 maximum offered load by 1.6 percent to avoid introducing congestion 553 when testing devices using bit-synchronous interfaces (such as T1/E1, 554 DS-3, and the like). 556 The percentage given above is an approximation. For greatest 557 precision, the actual offered load should be calculated using frames 558 per second rather than percentage of line rate as the unit of 559 measurement. 561 Note that the DUT/SUT may be able to forward offered loads higher 562 than 98.4 percent without packet loss. Such results are the result 563 of queuing on the part of the DUT/SUT. While a device's throughput 564 may be above this level, delay-related measurements such as latency 565 or jitter may be affected. Accordingly, it is RECOMMENDED to reduce 566 offered levels by the amount of bit-stuffing overhead when testing 567 devices using bit-synchronous links. This recommendation applies for 568 all measurements, including throughput. 570 5.3 POS Byte Stuffing 572 [RFC1662] requires that "Each Flag Sequence, Control Escape octet, 573 and any octet which is flagged in the sending 574 Async-Control-Character-Map (ACCM), is replaced by a two octet 575 sequence consisting of the Control Escape octet followed by the 576 original octet exclusive-or'd with hexadecimal 0x20." The practical 577 effect of this is to insert a stuff byte for instances of up to 34 578 characters: 0x7E, 0x7D, or any of 32 ACCM values. 580 A common implementation of PPP in HDLC-like framing is in PPP over 581 Sonet/SDH (POS), as defined in [RFC2615]. 583 As with the bit-stuffing case, the requirement in characterizing POS 584 test traffic is to determine the probability that byte-stuffing will 585 occur for a given sequence. This is much simpler to do than with 586 bit-synchronous links, since there is no possibility of overlap 587 across byte boundaries. 589 5.3.1 Nullifying ACCM 591 Testers can greatly reduce the probability of byte-stuffing by 592 configuring link partners to negotiate an ACCM value of 0x00. It is 593 RECOMMENDED that testers configure the test instrument(s) and DUT/SUT 594 to negotiate an ACCM value of 0x00 unless specific ACCM values are 595 required. 597 One instance where nonzero ACCM values are used is in the layer 2 598 tunneling protocol (L2TP), as defined in [RFC2661], section 4.4.6. 599 When ACCM values are defined, the probability of stuffing for any 600 given byte is 34 in 256, or approximately 13.3 percent. 602 5.3.2 Other Stuffed Characters 604 If an ACCM value of 0x00 is negotiated, the only characters subject 605 to stuffing are the flag and control escape characters. Thus, we can 606 say that without ACCM the probability of stuffing for any given byte 607 is 2 in 256, or approximately 0.8 percent. 609 5.3.3 Applied Byte Stuffing 611 When testing a DUT/SUT that implements PPP in HDLC-like framing and 612 L2TP (or any other technology that uses nonzero ACCM values), it is 613 RECOMMENDED that testers reduce the maximum offered load by 13.3 614 percent to avoid introducing congestion. 616 When testing a DUT/SUT that implements PPP in HDLC-like framing and 617 an ACCM value of 0x00, it is RECOMMENDED that testers reduce the 618 maximum offered load by 0.8 percent to avoid introducing congestion. 620 Note that the percentages given above are approximations. For 621 greatest precision, the actual offered load should be calculated 622 using frames per second rather than percentage of line rate as the 623 unit of measurement. 625 Note also that the DUT/SUT may be able to forward offered loads 626 higher than the percentages given above without packet loss. Such 627 results are the result of queuing on the part of the DUT/SUT. While 628 a device's throughput may be above this level, delay-related 629 measurements such as latency or jitter may be affected. Accordingly, 630 it is RECOMMENDED to reduce offered levels by the amount of 631 byte-stuffing overhead when testing devices using byte-synchronous 632 links. This recommendation applies for all measurements, including 633 throughput. 635 6. Security Considerations 637 This document recommends the use of pseudorandom patterns in test 638 traffic. Testers should be aware that the rand() functions of many 639 programming languages produce output that is pseudorandom rather than 640 truly random. As far as the authors are aware, pseudorandom patterns 641 are sufficient for generating test traffic in lab conditions. 642 However, when testing devices that require truly random input (such 643 as devices using cryptographic functions), it is strongly RECOMMENDED 644 to use rand() functions that return truly random values. 646 [RFC2615], section 6, discusses a denial-of-service attack involving 647 the intentional transmission of characters that require stuffing. 648 This attack could consume up to 100 percent of available bandwidth. 649 However, the test networks described in BMWG documents generally 650 SHOULD NOT be reachable by attackers or anyone else other than the 651 tester(s). 653 7. IANA Considerations 655 This document has no actions for IANA. 657 8. References 659 8.1 Normative References 661 [RFC1661] Simpson, W., "The Point-to-Point Protocol (PPP)", STD 51, 662 RFC 1661, July 1994. 664 [RFC1662] Simpson, W., "PPP in HDLC-like Framing", STD 51, RFC 1662, 665 July 1994. 667 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 668 Requirement Levels", BCP 14, RFC 2119, March 1997. 670 [RFC2544] Bradner, S. and J. McQuaid, "Benchmarking Methodology for 671 Network Interconnect Devices", RFC 2544, March 1999. 673 [RFC2615] Malis, A. and W. Simpson, "PPP over SONET/SDH", RFC 2615, 674 June 1999. 676 [RFC2661] Townsley, W., Valencia, A., Rubens, A., Pall, G., Zorn, G. 677 and B. Palter, "Layer Two Tunneling Protocol "L2TP"", RFC 678 2661, August 1999. 680 [RFC2889] Mandeville, R. and J. Perser, "Benchmarking Methodology 681 for LAN Switching Devices", RFC 2889, August 2000. 683 8.2 Informative References 685 [Ca63] Campbell, D. and J. Stanley, "Experimental and 686 Quasi-Experimental Designs for Research", 1963. 688 [Go97] Goralski, W., "SONET: A Guide to Synchronous Optical 689 Networks", 1997. 691 Authors' Addresses 693 David Newman 694 Network Test 696 EMail: dnewman@networktest.com 698 Timmons C. Player 699 Spirent Communications 701 EMail: timmons.player@spirentcom.com 703 Appendix A. Acknowledgements 705 The authors gratefully acknowledge the contributions of Glenn 706 Chagnot, Rafael Francis, and David Joyner. 708 Intellectual Property Statement 710 The IETF takes no position regarding the validity or scope of any 711 Intellectual Property Rights or other rights that might be claimed to 712 pertain to the implementation or use of the technology described in 713 this document or the extent to which any license under such rights 714 might or might not be available; nor does it represent that it has 715 made any independent effort to identify any such rights. Information 716 on the procedures with respect to rights in RFC documents can be 717 found in BCP 78 and BCP 79. 719 Copies of IPR disclosures made to the IETF Secretariat and any 720 assurances of licenses to be made available, or the result of an 721 attempt made to obtain a general license or permission for the use of 722 such proprietary rights by implementers or users of this 723 specification can be obtained from the IETF on-line IPR repository at 724 http://www.ietf.org/ipr. 726 The IETF invites any interested party to bring to its attention any 727 copyrights, patents or patent applications, or other proprietary 728 rights that may cover technology that may be required to implement 729 this standard. Please address the information to the IETF at 730 ietf-ipr@ietf.org. 732 The IETF has been notified of intellectual property rights claimed in 733 regard to some or all of the specification contained in this 734 document. For more information consult the online list of claimed 735 rights. 737 Disclaimer of Validity 739 This document and the information contained herein are provided on an 740 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 741 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 742 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 743 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 744 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 745 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 747 Copyright Statement 749 Copyright (C) The Internet Society (2004). This document is subject 750 to the rights, licenses and restrictions contained in BCP 78, and 751 except as set forth therein, the authors retain all their rights. 753 Acknowledgment 755 Funding for the RFC Editor function is currently provided by the 756 Internet Society.