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