Network Working Group D. Newman Internet-Draft Network Test Intended status: Informational T. Player Expires: April 1, 2007 Spirent Communications September 28, 2006 Hash and Stuffing: Overlooked Factors in Network Device Benchmarking draft-ietf-bmwg-hash-stuffing-06.txt Status of this Memo 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. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on April 1, 2007. Copyright Notice Copyright (C) The Internet Society (2006). Newman & Player Expires April 1, 2007 [Page 1] Internet-Draft Hash and Stuffing September 2006 Abstract Test engineers take pains to declare all factors that affect a given measurement, including intended load, packet length, test duration, and traffic orientation. However, current benchmarking practice overlooks two factors that have a profound impact on test results. First, existing methodologies do not require the reporting of addresses or other test traffic contents, even though these fields can affect test results. Second, "stuff" bits and bytes inserted in test traffic by some link-layer technologies add significant and variable overhead, which in turn affects test results. This document describes the effects of these factors; recommends guidelines for test traffic contents; and offers formulas for determining the probability of bit- and byte-stuffing in test traffic. Newman & Player Expires April 1, 2007 [Page 2] Internet-Draft Hash and Stuffing September 2006 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Requirements . . . . . . . . . . . . . . . . . . . . . . . . . 5 3. General considerations . . . . . . . . . . . . . . . . . . . . 6 3.1. Repeatability . . . . . . . . . . . . . . . . . . . . . . 6 3.2. Randomness . . . . . . . . . . . . . . . . . . . . . . . . 6 4. Packet Content Variations . . . . . . . . . . . . . . . . . . 7 4.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 7 4.2. Ethernet MAC Addresses . . . . . . . . . . . . . . . . . . 8 4.2.1. Randomized Sets of MAC Addresses . . . . . . . . . . . 9 4.3. MPLS Addressing . . . . . . . . . . . . . . . . . . . . . 11 4.4. Network-layer Addressing . . . . . . . . . . . . . . . . . 11 4.5. Transport-layer Addressing . . . . . . . . . . . . . . . . 12 4.6. Application-layer Patterns . . . . . . . . . . . . . . . . 12 5. Control Character Stuffing . . . . . . . . . . . . . . . . . . 13 5.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 13 5.2. PPP Bit Stuffing . . . . . . . . . . . . . . . . . . . . . 13 5.2.1. Calculating Bit-Stuffing Probability . . . . . . . . . 16 5.2.2. Bit Stuffing for Finite Strings . . . . . . . . . . . 17 5.2.3. Applied Bit Stuffing . . . . . . . . . . . . . . . . . 18 5.3. POS Byte Stuffing . . . . . . . . . . . . . . . . . . . . 18 5.3.1. Nullifying ACCM . . . . . . . . . . . . . . . . . . . 19 5.3.2. Other Stuffed Characters . . . . . . . . . . . . . . . 19 5.3.3. Applied Byte Stuffing . . . . . . . . . . . . . . . . 19 6. Security Considerations . . . . . . . . . . . . . . . . . . . 21 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 23 8.1. Normative References . . . . . . . . . . . . . . . . . . . 23 8.2. Informative References . . . . . . . . . . . . . . . . . . 23 Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 24 Appendix B. Proof of Formula for Finite Bit Stuffing . . . . . . 25 Appendix C. Explicit Calculation of Bit Stuffing Overhead for IPv4 . . . . . . . . . . . . . . . . . . . . . . . . 26 Appendix D. Explicit Calculation of Bit Stuffing Overhead for IPv6 . . . . . . . . . . . . . . . . . . . . . . . . 28 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 30 Intellectual Property and Copyright Statements . . . . . . . . . . 31 Newman & Player Expires April 1, 2007 [Page 3] Internet-Draft Hash and Stuffing September 2006 1. Introduction Experience in benchmarking networking devices suggests that the contents of test traffic can have a profound impact on test results. For example, some devices may forward randomly addressed traffic without loss, but drop significant numbers of packets when offered packets containing nonrandom addresses. Methodologies such as [RFC2544] and [RFC2889] do not require any declaration of packet contents. These methodologies do require the declaration of test parameters such as traffic distribution and traffic orientation, and yet packet contents can have at least as great an impact on test results as the other factors. Variations in packet contents also can lead to non-repeatability of test results: Two individuals may follow methodology procedures to the letter, and still obtain very different results. A related issue is the insertion of stuff bits or bytes by link-layer technologies using PPP with HDLC-like framing. This stuffing is done to ensure sequences in test traffic will not be confused with control characters. Stuffing adds significant and variable overhead. Currently there is no standard method for determining the probability that stuffing will occur for a given pattern, and thus no way to determine what impact stuffing will have on test results. This document covers two areas. First, we discuss strategies for dealing with randomness and nonrandomness in test traffic. Second, we present formulas to determine the probability of bit- and byte- stuffing on PPP and POS circuits. In both areas, we provide recommendations for obtaining better repeatability in test results. Newman & Player Expires April 1, 2007 [Page 4] Internet-Draft Hash and Stuffing September 2006 2. Requirements The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. Newman & Player Expires April 1, 2007 [Page 5] Internet-Draft Hash and Stuffing September 2006 3. General considerations 3.1. Repeatability Repeatability is a desirable trait in benchmarking, but it can be an elusive goal. It is a common but mistaken belief that test results can always be reproduced provided the device under test and test instrument are configured identically for each test iteration. In fact, even identical configurations may introduce some variations in test traffic, such as changes in timestamps, TCP sequence numbers, or other common phenomena. While this variability does not necessarily invalidate test results, it is important to recognize the existing variation. Exact bit-for- bit reproduction of test traffic is a hard problem. A simpler approach is to acknowledge that some variation exists, characterize that variation, and describe it when analyzing test results. 3.2. Randomness This document recommends the use of pseudorandom patterns in test traffic under controlled lab conditions. The rand() functions available in many programming languages produce output that is pseudorandom rather than truly random. Pseudorandom patterns are sufficient for the recommendations given in this document, provided they produce output that is uniformly distributed across the pattern space. Specifically, for any random bit pattern of length L, the probability of generating that specific pattern SHOULD equal 1 over 2 to the Lth power. Newman & Player Expires April 1, 2007 [Page 6] Internet-Draft Hash and Stuffing September 2006 4. Packet Content Variations 4.1. Problem Statement The contents of test traffic can have a significant impact on metrics such as throughput, jitter, latency, and loss. For example, many network devices feed addresses into a hashing algorithm to determine which path upon which to forward a given packet. Consider the simple case of an Ethernet switch with eight network processors (NPs) in its switching fabric: ingress || \/ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ___ ___ ___ ___ ___ ___ ___ ___ | || | | | | | | | | | | | | | | | | ||NP0| |NP1| |NP2| |NP3| |NP4| |NP5| |NP6| |NP7| | ||___| |___| |___| |___| |___| |___| |___| |___| | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ || \/ egress To assign incoming traffic to the various NPs, suppose a hashing algorithm performs an exclusive-or (XOR) operation on the least significant 3 bits of the source and destination MAC addresses in each frame. (This is an actual example the authors have observed in multiple devices from multiple manufacturers.) In theory, a random distribution of source and destination MAC addresses should result in traffic being uniformly distributed across all eight NPs. (Instances of the term "random" in this document refer to a random uniform distribution across a given address space. Section 3.2 describes random uniform distributions in more detail.) In practice, the actual outcome of the hash (and thus any test results) will be very different depending on the degree of randomness in test traffic. Suppose the traffic is nonrandom so that every interface of the test instrument uses this pattern in its source MAC addresses: 00:00:PP:00:00:01 Newman & Player Expires April 1, 2007 [Page 7] Internet-Draft Hash and Stuffing September 2006 where PP is the source interface number of the test instrument. In this case, the least significant 3 bits of every source and destination MAC address are 001, regardless of interface number. Thus, the outcome of the XOR operation will always be 0, given the same three least significant bits: 001 ^ 001 = 000 Thus, the switch will assign all traffic to NP0, leaving the other seven NPs idle. Given a heavy enough load, NP0 and the switch will become congested, even though seven other NPs are available. At most, this device will be able to utilize approximately 12.5 percent of its total capacity, with the remaining 87.5 percent of capacity unused. Now consider the same example with randomly distributed addresses. In this case, the test instrument offers traffic using MAC addresses with this pattern: 00:00:PP:00:00:RR where PP is the source interface number of the test instrument and RR is a pseudorandom number. In this case, there should be an equal probability of the least significant 3 bits of the MAC address having any value from 000 to 111 inclusive. Thus, the outcome of XOR operations should be equally distributed from 0 to 7, and distribution across NPs should also be equal (at least for this particular 3-bit hashing algorithm). Absent other impediments, the device should be able to utilize 100 percent of available capacity. This simple example presumes knowledge on the tester's part of the hashing algorithm used by the device under test. Knowledge of such algorithms is not always possible beforehand, and in any event violates the "black box" spirit of many documents produced by the IETF BMWG. Therefore, this memo adds a new consideration for benchmarking methodologies, to select traffic patterns that overcome the effects of non-randomness regardless of the hashing algorithms in use. The balance of this section offers recommendations for test traffic patterns to avoid these effects, starting at the link layer and working up to the application layer. 4.2. Ethernet MAC Addresses Test traffic SHOULD use pseudorandom patterns in Ethernet addresses. The following source and destination Ethernet address pattern is Newman & Player Expires April 1, 2007 [Page 8] Internet-Draft Hash and Stuffing September 2006 RECOMMENDED for use when benchmarking Ethernet devices: (RR & 0xFC):PP:PP:RR:RR:RR where (RR & 0xFC) is a pseudorandom number bitwise ANDed with 0xFC, PP:PP is the 1-indexed interface number of the test instrument and RR:RR:RR is a pseudorandom number. The bitwise ANDing of the high-order byte in the MAC address with 0xFC sets the high-order two bits of that byte to 0, guaranteeing a non multicast address and a non locally administered address. Test traffic SHOULD use PP:PP to identify the source interface number of the test instrument. Such identification can be useful in troubleshooting. Allocating 2 bytes of the MAC address for interface identification allows for tests of up to 65,536 interfaces. A 2-byte space allows for tests much larger than those currently used in device benchmarking; however, tests involving more than 256 interfaces (fully utilizing a 1-byte space) are fairly common. Note that the "PP:PP" designation refers to the source interface of the test instrument, not the DUT/SUT. There are situations where the DUT/SUT interface number may change during the test; one example would be a test of wireless LAN roaming. By referring to the (presumably static) source interface number of the test instrument, test engineers can keep track of test traffic regardless of any possible DUT/SUT changes. Further, source interface numbers SHOULD be 1-indexed and SHOULD NOT be 0-indexed. This avoids the low but nonzero probability of an all-0s Ethernet address. Some devices will drop frames with all-0s Ethernet addresses. It is RECOMMENDED to use pseudorandom patterns in the least significant 3 bytes of the MAC address. Using pseudorandom values for the low-order 3 bytes means choosing one of 16.7 million unique addresses. While this address space is vastly larger than is currently required in lab benchmarking, it does assure more realistic test traffic. Note also that since only 30 of 48 bits in the MAC address have pseudorandom values, there is no possibility of randomly generating a broadcast or multicast value by accident. 4.2.1. Randomized Sets of MAC Addresses It is common benchmarking practice for a test instrument to emulate multiple hosts, even on a single interface. This is desirable in Newman & Player Expires April 1, 2007 [Page 9] Internet-Draft Hash and Stuffing September 2006 assessing DUT/SUT scalability. However, test instruments may emulate multiple MAC addresses by incrementing and/or decrementing addresses from a fixed starting point. This leads to situations as described above in "Address Pattern Variations" where hashing algorithms produce nonoptimal outcomes. The outcome can be nonoptimal even if the set of addresses begins with a pseudorandom number. For example, the following source/ destination pairs will not be equally distributed by the 3-bit hashing algorithm discussed above: Source Destination 00:00:01:FC:B3:45 00:00:19:38:8C:80 00:00:01:FC:B3:46 00:00:19:38:8C:81 00:00:01:FC:B3:47 00:00:19:38:8C:82 00:00:01:FC:B3:48 00:00:19:38:8C:83 00:00:01:FC:B3:49 00:00:19:38:8C:84 00:00:01:FC:B3:4A 00:00:19:38:8C:85 00:00:01:FC:B3:4B 00:00:19:38:8C:86 00:00:01:FC:B3:4C 00:00:19:38:8C:87 Again working with our 3-bit XOR hashing algorithm, we get the following outcomes: 101 ^ 000 = 101 110 ^ 001 = 111 111 ^ 010 = 101 000 ^ 011 = 011 001 ^ 100 = 101 010 ^ 101 = 111 011 ^ 110 = 101 100 ^ 111 = 011 Note that only three of eight possible outcomes are achieved when incrementing addresses. This is actually the best case. Incrementing from other combinations of pseudorandom address pairs produces only one or two out of eight possible outcomes. Every MAC address SHOULD be pseudorandom, not just the starting one. When generating traffic with multiple addresses, it is RECOMMENDED that all addresses use pseudorandom values. There are multiple ways Newman & Player Expires April 1, 2007 [Page 10] Internet-Draft Hash and Stuffing September 2006 to use sets of pseudorandom numbers. One strategy would be for the test instrument to iterate over an array of pseudorandom values rather than incrementing/decrementing from a starting address. The actual method is an implementation detail; in the end, any method that uses multiple addresses with pseudorandom patterns will be sufficient 4.3. MPLS Addressing Similiar to L2 switches, MPLS routers make forwarding decisions based on a 20 bit MPLS label. Unless specific labels are required, it is RECOMMENDED that uniformly random values between 0 and 1,048,575 be used for all labels assigned by test equipment. 4.4. Network-layer Addressing When routers make forwarding decisions based solely on destination network address, there may be no potential for hashing collision of source and destination addresses, as in the case of Ethernet switching discussed earlier. However, the potential still exists for hashing collisions to exist at the network layer, and testers SHOULD take this potential into consideration when crafting the network- layer contents of test traffic. For example, the equal cost multipath (ECMP) feature performs load- sharing across multiple links. Routers implementing ECMP may perform a hash of source and destination IP addresses in assigning flows. Since multiple ECMP routes by definition have the same metric, routers use some other "tiebreaker" mechanism to assign traffic to each link. As far as the authors are aware, there is no standard algorithm for ECMP link assignment. Some implementations perform a hash of all bits of the source and destination IP addresses for this purpose. Others may perform a hash on one or more bytes in the source and destination IP addresses. Just as in the case of MAC addresses, nonrandom IP addresses can have an adverse effect on the outcome of ECMP link assignment decisions. When benchmarking devices that implement ECMP or any other form of Layer 3 aggregation, it is RECOMMENDED to use a randomly distributed range of IP addresses. In particular, testers SHOULD NOT use addresses that produce the undesired effects of address processing. If, for example, a DUT can be observed to exhibit high packet loss when offered IPv4 network addresses that take the form x.x.1.x/24, and relatively low packet loss when the source and destination network addresses take the form of x.x.R.x/24 (where R is some random value between 0 and 9), test engineers SHOULD use the random pattern. Newman & Player Expires April 1, 2007 [Page 11] Internet-Draft Hash and Stuffing September 2006 4.5. Transport-layer Addressing Some devices with transport- or application-layer awareness use TCP or UDP port numbers in making forwarding decisions. Examples of such devices include load balancers and application-layer firewalls. Test instruments have the capability of generating packets with random TCP and UDP source and destination port numbers. Known destination port numbers are often required for testing application- layer devices. However, unless known port numbers are specifically required for a test, it is RECOMMENDED to use pseudorandom and uniformly distributed values for both source and destination port numbers. In addition, it may be desirable to pick pseudorandom values from a selected pool of numbers. Many services identify themselves through use of reserved destination port numbers between 1 and 1023 inclusive. Unless specific port numbers are required, it is RECOMMENDED to pick randomly distributed destination port numbers between these lower and upper boundaries. Similarly, clients typically choose source port numbers in the space between 1024 and 65535 inclusive. Unless specific port numbers are required, it is RECOMMENDED to pick randomly distributed source port numbers between these lower and upper boundaries. 4.6. Application-layer Patterns Many measurements require the insertion of application-layer header(s) and payload into test traffic. Application-layer packet contents offer additional opportunities for stuffing to occur, and may also present nonrandom outcomes when fed through application layer-aware hashing algorithms. Given the vast number of application-layer protocols in use, we make no recommendation for specific test traffic patterns to be used; however, test engineers SHOULD be aware that application-layer traffic contents MAY produce nonrandom outcomes with some hashing algorithms. The same issues that apply with lower-layer traffic patterns also apply at the application layer. As discussed in section 5, the potential for stuffing exists with any part of a test packet, including application-layer contents. For example, some traffic generators insert fields into packet payloads to distinguish test traffic. These fields may contain a transmission timestamp; sequence number; test equipment interface identifier and/or "stream" number; and a CRC over the contents of the test payload or test packet. All these fields are potential candidates for stuffing. Newman & Player Expires April 1, 2007 [Page 12] Internet-Draft Hash and Stuffing September 2006 5. Control Character Stuffing 5.1. Problem Statement Link-layer technologies that use HDLC-like framing may insert an extra bit or byte before each instance of a control character in traffic. These insertions prevent confusion with control characters, but they may also introduce significant overhead. The overhead of these escape sequences is problematic for two reasons. First, explictly calculating the amount of overhead can be non-trivial or even impossible for certain types of test traffic. In such cases, the best testers can do is to characterize the probability that an escape sequence will occur for a given pattern. This greatly complicates the requirement of declaring exactly how much traffic is offered to a DUT/SUT. Second, in the absence of characterization and compensation for this overhead, the tester may unwittingly congest the DUT/SUT. For example, if a tester intends to offer traffic to a DUT at 95 percent of line rate, but the link-layer protocol introduces an additional 1 percent of overhead to escape control characters, then the aggregate offered load will be 96 percent of line rate. If the DUT's actual channel capacity is only 95 percent, congestion will occur and the DUT will drop traffic even though the tester did not intend this outcome. As described in [RFC1661] and [RFC1662], PPP and HDLC-like framing introduce two kinds of escape sequences: bit and byte stuffing. Bit stuffing refers to the insertion of an escape bit on bit-synchronous links. Byte stuffing refers to the insertion of an escape byte on byte-synchronous links. We discuss each in turn. 5.2. PPP Bit Stuffing [RFC1662], section 5.2 specifies that any sequence of five contiguous "1" bits within a frame must be escaped by inserting a "0" bit prior to the sequence. This escaping is necessary to avoid confusion with the HDLC control character 0x7E, which contains six "1" bits. Consider the following PPP frame containing a TCP/IP packet. Not shown is the 1-byte flag sequence (0x7E), at least one of which must occur between frames. The contents of the various frame fields can be described one of three ways: Newman & Player Expires April 1, 2007 [Page 13] Internet-Draft Hash and Stuffing September 2006 1. Field contents never change over the test duration. An example would be the IP version number. 2. Field contents change over the test duration. Some of these changes are known prior to the test duration. An example would be the use of incrementing IP addresses. Some of these changes are unknown. An example would be a dynamically calculated field such as the TCP checksum. 3. Field contents may not be known. An example would be proprietary payload fields in test packets. In the diagram below, 30 out of 48 total bytes in the packet headers are subject to change over the test duration. Additionally, the payload field could be subject to change both content and size. The fields containing the changeable bytes are given in ((double parentheses)). Newman & Player Expires April 1, 2007 [Page 14] Internet-Draft Hash and Stuffing September 2006 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Address | Control | Protocol | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Version| IHL |Type of Service| Total Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Identification |Flags| Fragment Offset | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Time to Live | Protocol | ((Header Checksum)) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ((Source Address)) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ((Destination Address)) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ((Source Port)) | ((Destination Port)) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ((Sequence Number)) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ((Acknowledgment Number)) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Data | |U|A|P|R|S|F| | | Offset| Reserved |R|C|S|S|Y|I| ((Window)) | | | |G|K|H|T|N|N| | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ((Checksum)) | Urgent Pointer | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | / ((payload)) / | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ((FCS (4 bytes) )) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ None of the other fields are known to contain sequences subject to bit-stuffing, at least not in their entirety. Note that there is no payload in this simple example; as noted in section 4.6, the payload contents of test traffic often will present additional opportunities for stuffing to occur, and MUST be taken into account when calculating stuff probability. Given the information at hand, and assuming static contents for the rest of the fields, the challenge is to determine the probability that bit-stuffing will occur. Newman & Player Expires April 1, 2007 [Page 15] Internet-Draft Hash and Stuffing September 2006 5.2.1. Calculating Bit-Stuffing Probability In order to calculate bit-stuffing probabilities, we assume that for any string of length L, where b_n represents the "n"th bit of the string and 1 <= n <= L, the probability of b_n equalling "1" is 0.5 and the probability of b_n equalling "0" is 0.5. Additionally, the value of b_n is independent of any other bits. We can calculate the probability of bit-stuffing for both infinite and finite strings of random bits. We begin with the infinite-string case. For an infinitely long string of uniformly random bits, we will need to insert a stuff bit if and only if state 5 is reached in the following state table. |--------------------<----------------------| | |1 _______ __|__ _____ _____ _____ __|__ | | 1 | | 1 | | 1 | | 1 | | 1 | | | start |--->| 1 |--->| 2 |--->| 3 |--->| 4 |--->| 5 | |_______| |_____| |_____| |_____| |_____| |_____| | | | | | | | | |0 |0 |0 |0 |0 |0 |-<-|----<----|----<-----|----<-----|----<-----|----<-----| Initially, we begin in the "start" state. A "1" bit moves us into the next highest state, and a "0" bit returns us to the start state. From state 5, a "1" bit takes us back to the 1 state and a "0" bit returns us to "start." From this state table we can build the following transition matrix: \ To | \ | \ | From \ | start 1 2 3 4 5 ______\|_________________________________________________ start | 0.5 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0 1 | 0.5 | 0.0 | 0.5 | 0.0 | 0.0 | 0.0 2 | 0.5 | 0.0 | 0.0 | 0.5 | 0.0 | 0.0 3 | 0.5 | 0.0 | 0.0 | 0.0 | 0.5 | 0.0 4 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0 | 0.5 5 | 0.5 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0 With this transition matrix we can build the following system of equations. If P(x) represents the probability of reaching state x, then: Newman & Player Expires April 1, 2007 [Page 16] Internet-Draft Hash and Stuffing September 2006 P(start) = 0.5 * P(start) + 0.5 * P(1) + 0.5 * P(2) + 0.5 * P(3) + 0.5 * P(4) + 0.5 * P(5) P(1) = 0.5 * P(start) + 0.5 * P(5) P(2) = 0.5 * P(1) P(3) = 0.5 * P(2) P(4) = 0.5 * P(3) P(5) = 0.5 * P(4) P(start) + P(1) + P(2) + P(3) + P(4) + P(5) = 1 Solving this system of equations yields: P(start) = 0.5 P(1) = 8/31 P(2) = 4/31 P(3) = 2/31 P(4) = 1/31 P(5) = 1/62 Thus, for an infinitely long string of uniformly random bits, the probability of any individual bit causing a transition to state 5, and thus causing a stuff, is 1/62. 5.2.2. Bit Stuffing for Finite Strings For a uniformly random finite bit string of length L, we can explicitly count the number of bit-stuffs in the set of all possible strings of length L. This count can then be used to calculate the expected number of stuffs for the string. Let f(L) represent the number of bit-stuffs in the set of all possible strings of length L. Clearly, for 0 <= L <= 4, f(L) = 0 as there are no strings of length 5. For L >= 5, f(L) = 2^(L-5) + (L-5) * 2^(L-6) + f(L-5). A proof of this formula can be found in Appendix B. Now, the expected number of stuffing events, E[stuffs], can be found by dividing the total number of stuffs in all possible strings by the total number of strings. Thus for any L, E[stuffs] = f(L) / 2^L. Similiarly, the probability that any particular bit is the cause of a bit-stuff can be calculated by dividing the total number of stuffs in Newman & Player Expires April 1, 2007 [Page 17] Internet-Draft Hash and Stuffing September 2006 the set of all strings of length L by the total number of bits in the set of all strings of length L. Hence for any L, the probability that L_n, where 5 <= n <= L, caused a stuff is f(L) / (L * 2^L). 5.2.3. Applied Bit Stuffing The amount of overhead attributable to bit-stuffing may be calculated explicitly as long as the expected number of stuff bits per frame, E[bit-stuffs] is known. For long uniformly random bit-strings, E[bit-stuffs] may be approximated by multiplying the length of the string by 1/62. % overhead = E[bit-stuffs] / framesize (in bits) Given that the overhead added by bit-stuffing is approximately 1 in 62, or 1.6 percent, it is RECOMMENDED that testers reduce the maximum intended load by 1.6 percent to avoid introducing congestion when testing devices using bit-synchronous interfaces (such as T1/E1, DS-3, and the like). The percentage given above is an approximation. For greatest precision, the actual intended load SHOULD be explicitly calculated from the test traffic. Note that the DUT/SUT may be able to forward intended loads higher than the calculated theoretical maximum rate without packet loss. Such results are the result of queuing on the part of the DUT/SUT. While a device's throughput may be above this level, delay-related measurements may be affected. Accordingly, it is RECOMMENDED to reduce offered levels by the amount of bit-stuffing overhead when testing devices using bit-synchronous links. This recommendation applies for all measurements, including throughput. 5.3. POS Byte Stuffing [RFC1662] requires that "Each Flag Sequence, Control Escape octet, and any octet which is flagged in the sending Async-Control- Character-Map (ACCM), is replaced by a two octet sequence consisting of the Control Escape octet followed by the original octet exclusive- or'd with hexadecimal 0x20." The practical effect of this is to insert a stuff byte for instances of up to 34 characters: 0x7E, 0x7D, or any of 32 ACCM values. A common implementation of PPP in HDLC-like framing is in PPP over Sonet/SDH (POS), as defined in [RFC2615]. As with the bit-stuffing case, the requirement in characterizing POS test traffic is to determine the probability that byte-stuffing will Newman & Player Expires April 1, 2007 [Page 18] Internet-Draft Hash and Stuffing September 2006 occur for a given sequence. This is much simpler to do than with bit-synchronous links, since there is no possibility of overlap across byte boundaries. 5.3.1. Nullifying ACCM Testers can greatly reduce the probability of byte-stuffing by configuring link partners to negotiate an ACCM value of 0x00. It is RECOMMENDED that testers configure the test instrument(s) and DUT/SUT to negotiate an ACCM value of 0x00 unless specific ACCM values are required. One instance where nonzero ACCM values are used is in the layer 2 tunneling protocol (L2TP), as defined in [RFC2661], section 4.4.6. When the default ACCM values are used, the probability of stuffing for any given random byte is 34 in 256, or approximately 13.3 percent. 5.3.2. Other Stuffed Characters If an ACCM value of 0x00 is negotiated, the only characters subject to stuffing are the flag and control escape characters. Thus, we can say that without ACCM the probability of stuffing for any given random byte is 2 in 256, or approximately 0.8 percent. 5.3.3. Applied Byte Stuffing The amount of overhead attributable to byte stuffing may be calculated explicitly as long as the expected number of stuff bytes per frame, E[byte-stuffs], is known. For long uniformly random byte- strings, E[byte-stuffs] may be approximated by multiplying the length of the string by the probability that any single byte is a stuff byte. % overhead = E[byte-stuffs] / framesize (in bytes) When testing a DUT/SUT that implements PPP in HDLC-like framing and L2TP (or any other technology that uses nonzero ACCM values), it is RECOMMENDED that testers reduce the maximum intended load by 13.3 percent to avoid introducing congestion. When testing a DUT/SUT that implements PPP in HDLC-like framing and an ACCM value of 0x00, it is RECOMMENDED that testers reduce the maximum intended load by 0.8 percent to avoid introducing congestion. Note that the percentages given above are approximations. For greatest precision, the actual intended load SHOULD be explictly calculated from the test traffic Newman & Player Expires April 1, 2007 [Page 19] Internet-Draft Hash and Stuffing September 2006 Note also that the DUT/SUT may be able to forward intended loads higher than the calculated theoretical maximum rate without packet loss. Such results are the result of queuing on the part of the DUT/ SUT. While a device's throughput may be above this level, delay- related measurements may be affected. Accordingly, it is RECOMMENDED to reduce offered levels by the amount of byte-stuffing overhead when testing devices using byte-synchronous links. This recommendation applies for all measurements, including throughput. Newman & Player Expires April 1, 2007 [Page 20] Internet-Draft Hash and Stuffing September 2006 6. Security Considerations This document recommends the use of pseudorandom patterns in test traffic. This usage requires a uniform distribution, but does not have strict predictability requirements. Although it is not sufficient for security applications, the rand() function of many programming languages may provide a uniform distribution that is usable for testing purposes in lab conditions. Implementations of rand() may vary and provide different properties so test designers SHOULD understand the distribution created by the underlying function and how seeding the initial state affects its behavior. [RFC2615], section 6, discusses a denial-of-service attack involving the intentional transmission of characters that require stuffing. This attack could consume up to 100 percent of available bandwidth. However, the test networks described in BMWG documents generally SHOULD NOT be reachable by anyone other than the tester(s). Newman & Player Expires April 1, 2007 [Page 21] Internet-Draft Hash and Stuffing September 2006 7. IANA Considerations This document has no actions for IANA. Newman & Player Expires April 1, 2007 [Page 22] Internet-Draft Hash and Stuffing September 2006 8. References 8.1. Normative References [RFC1661] Simpson, W., "The Point-to-Point Protocol (PPP)", STD 51, RFC 1661, July 1994. [RFC1662] Simpson, W., "PPP in HDLC-like Framing", STD 51, RFC 1662, July 1994. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC2544] Bradner, S. and J. McQuaid, "Benchmarking Methodology for Network Interconnect Devices", RFC 2544, March 1999. [RFC2615] Malis, A. and W. Simpson, "PPP over SONET/SDH", RFC 2615, June 1999. [RFC2661] Townsley, W., Valencia, A., Rubens, A., Pall, G., Zorn, G., and B. Palter, "Layer Two Tunneling Protocol "L2TP"", RFC 2661, August 1999. [RFC2889] Mandeville, R. and J. Perser, "Benchmarking Methodology for LAN Switching Devices", RFC 2889, August 2000. 8.2. Informative References [Ca63] Campbell, D. and J. Stanley, "Experimental and Quasi- Experimental Designs for Research", 1963. [Go97] Goralski, W., "SONET: A Guide to Synchronous Optical Networks", 1997. [Kn97] Knuth, D., "The Art of Computer Programming, Volume 2, Third Edition", 1997. Newman & Player Expires April 1, 2007 [Page 23] Internet-Draft Hash and Stuffing September 2006 Appendix A. Acknowledgements The authors gratefully acknowledge reviews and contributions by Len Ciavattone, Robert Craig, John Dawson, Neil Carter, Glenn Chagnot, Kevin Dubray, Diego Dugatkin, Rafael Francis, Paul Hoffman, David Joyner, Al Morton, Joe Perches, Jerry Perser, Scott Poretsky, and Kris Rousey. Newman & Player Expires April 1, 2007 [Page 24] Internet-Draft Hash and Stuffing September 2006 Appendix B. Proof of Formula for Finite Bit Stuffing We would like to construct a function, f(L), that allows us to explictly count the total number of bit-stuffs in the set of all strings of length L. Let S represent a bit string of length L. Additionally, let b_n be the nth bit of string S where 1 <= n <= L. Clearly, when 0 <= L <= 4, f(L) = 0, as there can be no possible bit- stuff if there are < 5 bits. Suppose L >= 5, then there are some number of strings that will cause stuffing events. Let us count them. We begin by counting the number of strings that will cause at least one bit-stuff. Let us suppose that the first 5 bits, b_1,...,b_5, cause a stuffing event. Then, there are (L-5) bits that could have any value, i.e. the bits in position b_6 to b_L. So, there must be 2^(L-5) strings where the first 5 bits cause a stuff. Now suppose that some other sequence of bits cause a stuff, b_n to b_(n+4) for some 1 < n <= L-4. In order to guarantee that b_n starts a stuff sequence, b_(n-1) must be 0, otherwise a stuff could occur at b_(n+3). Thus, there are a total of 6 bits which must have fixed values in the string, S, and a total of L-6 bits which do not have fixed values. Hence, for each value of n, there are 2^(L-6) possible strings with at least one bit-stuff for a total of (L-5) * 2^(L-6) So, given a string of length L, where L >= 5, we know that there are 2^(L-5) + (L-5) * 2^(L-6) strings which will be transmitted with at least one stuffed bit. However, if L >= 10, then there could be more than one bit-stuff within the string S. Let Z represent a sequence of 5 sequential ones bits. Consider the bit string ..., b_n, b_(n+1), b_(n+2), Z, b_(n+8), b_(n+9), ... where 1 <= n <= L-9. For the above sequence of bits to generate two stuffing events, there must be at least one run of five sequential one's bits in ..., b_n, b_(n+1), b_(n+2), b_(n+8), b_(n+9), ... Note that the position of Z in the above squence is irrelevant when looking for bit-stuffs. Additionally, we've already determined that the number of strings with at least one stuff in a bit string of length L is 2^(L-5) + (L-5) * 2^(L-6). Thus, the total number of stuffing events in the set of all bit strings of length L can be represented as f(L) = 2^(L-5) + (L-5) * 2^(L-6) + f(L-5) for all L >= 5. Newman & Player Expires April 1, 2007 [Page 25] Internet-Draft Hash and Stuffing September 2006 Appendix C. Explicit Calculation of Bit Stuffing Overhead for IPv4 Consider a scenario where a tester is transmitting IPv4 test packets across a bit synchronous link. The test traffic has the following parameters (values are in decimal): +----------------------+-----------------------------+ | Field | Value | +----------------------+-----------------------------+ | IP Version | 4 | | | | | IP Header Length | 5 | | | | | TOS | 0 | | | | | Datagram Length | 1028 | | | | | ID | 0 | | | | | Flags/Fragments | 0 | | | | | TTL | 64 | | | | | Protocol | 17 | | | | | Source IP | 192.168.13.1-192.168.13.254 | | | | | Destination IP | 192.168.1.10 | | | | | Source UDP Port | pseudorandom port | | | | | Destination UDP Port | pseudorandom port | | | | | UDP Length | 1008 | | | | | Payload | 1000 pseudorandom bytes | +----------------------+-----------------------------+ We want to calculate the expected number of stuffs per packet, or E[packet stuffs]. First, we observe that we have 254 different IP headers to consider, and secondly, that the changing 4th octet in the IP source addresses will produce occasional bit-stuffing events, so we must enumerate these occurances. Additionally, we must take into account that the 3rd octet of the source IP and the first octet of the destination IP will affect stuffing occurences. Newman & Player Expires April 1, 2007 [Page 26] Internet-Draft Hash and Stuffing September 2006 An exhaustive search shows that cycling through all 254 headers produces 51 bit stuffs for the destination IP address. This gives us an expectation of 51/254 stuffs per packet due to the changing source IP address. For the IP CRC, we observe that the value will decrement as the source IP is incremented. A little calculation shows that the CRC values for these headers will fall in the range of 0xE790 to 0xE88F. Additionally, both the protocol and source IP address must be considered, as they provide a source of extra leading and trailing ones bits. An exhaustive search shows that cycling through all 254 headers will produce 102 bit stuffs for the CRC. This gives us an expectation of 102/254 stuffs per packet due to the CRC. Since our destination IP address is even and the UDP length is less than 32768, the random source and destination ports provide 32 bits of sequential random data without forcing us to consider the boundry bits. Additionally, we will assume that since our payload is pseudorandom, our UDP CRC will be too. The even UDP length field again allows us to only consider the bits explicitly contained within the CRC and data fields. So, using the forumla for the expected number of stuffs in a finite string from section 5.2.2, we determine that E[UDP stuffs] = f(32)/2^32 + f(8000+16)/2^(8000+16). Now, f(32)/2^32 is calculatable without too much difficulty and is approximately 0.465. However, f(8016)/2^8016 is a little large to calculate easily, so we will approximate this value by using the probability value obtained in section 5.2.1. Thus, E[UDP] ~ 0.465 + 8016/62 ~ 129.755. Hence, E[packet stuffs] = 51/254 + 102/254 + 129.755 = 130.357. However, since we cannot have a fractional stuff, we round down to 130. Thus, we expect 130 stuffs per packet. Finally, we can calculate bit-stuffing overhead by dividing the expected number of stuff bits by the total number of bits in the IP datagram. So, this example traffic would generate 1.58% overhead. If our payload had consisted exclusively of zero bits, our overhead would have been 0.012%. An all ones payload would produce 19.47% overhead. Newman & Player Expires April 1, 2007 [Page 27] Internet-Draft Hash and Stuffing September 2006 Appendix D. Explicit Calculation of Bit Stuffing Overhead for IPv6 Consider a scenario where a tester is transmitting IPv6 test packets across a bit synchronous link. The test traffic has the following parameters (values are in decimal except for IPv6 addresses, which are in hexadecimal): +----------------------+------------------------------+ | Field | Value | +----------------------+------------------------------+ | IP Version | 6 | | | | | Traffic Class | 0 | | | | | Flow Label | pseudorandom label | | | | | Payload Length | 1008 | | | | | Next Header | 17 | | | | | Hop Limit | 64 | | | | | Source IP | DEAD:0:0:1::1-DEAD:0:0:1::FF | | | | | Destination IP | DEAD:0:0:2::10 | | | | | Source UDP Port | pseudorandom port | | | | | Destination UDP Port | pseudorandom port | | | | | UDP Length | 1008 | | | | | Payload | 1000 pseudorandom bytes | +----------------------+------------------------------+ We want to calculate the expected number of stuffs per packet, or E[packet stuffs]. First, we observe that we have 255 different IP headers to consider, and secondly, that the changing 4th quad in the IP source addresses will produce occasional bit-stuffing events, so we must enumerate these occurances. Additionally, we must take into account that the first quad of the destination IP address will affect stuffing occurences, since binary represenation of the address provides leading 1's bits. An exhaustive search shows that cycling through all 255 headers produces 36 bit stuffs for the destination IP address. This gives us Newman & Player Expires April 1, 2007 [Page 28] Internet-Draft Hash and Stuffing September 2006 an expectation of 36/255 stuffs per packet due to the changing source IP address. We also have to consider our pseudorandomlly generated flow label. However, since our Traffic Class field is 0 and our Payload Length field is less than 32768 (and thus the leading bit of the Payload Length field is 0), we may consider the flow label as 20 bits of random data. Thus the expectation of a stuff in the flow label is f(20)/2^20 ~ .272. Similiar to the flow label case above, the fourth quad of our destination IP address is even and the UDP length field is less than 32768, so the random source and destination ports provide 32 bits of sequential random data without forcing us to consider the boundry bits. Additionally, we will assume that since our payload is pseudorandom, our UDP CRC will be too. The even UDP length field again allows us to only consider the bits explicitly contained within the CRC and data fields. So, using the forumla for the expected number of stuffs in a finite string from section 5.2.2, we determine that E[UDP stuffs] = f(32)/2^32 + f(8000+16)/2^(8000+16). Now, f(32)/2^32 is calculatable without too much difficulty and is approximately 0.465. However, f(8016)/2^8016 is a little large to calculate easily, so we will approximate this value by using the probability value obtained in section 5.2.1. Thus, E[UDP stuffs] ~ 0.465 + 8016/62 ~ 129.755. Now we may explicty calculate that E[packet stuffs] = 36/255 + 0.272 + 129.755 = 130.168. However, since we cannot have a fractional stuff, we round down to 130. Thus, we expect 130 stuffs per packet. Finally, we can calculate bit-stuffing overhead by dividing the expected number of stuff bits by the total number of bits in the IP datagram. So, this example traffic would generate 1.55% overhead. If our payload had consisted exclusively of zero bits, our overhead would have been 0.010%. An all ones payload would produce 19.09% overhead. Newman & Player Expires April 1, 2007 [Page 29] Internet-Draft Hash and Stuffing September 2006 Authors' Addresses David Newman Network Test Email: dnewman@networktest.com Timmons C. Player Spirent Communications Email: timmons.player@spirentcom.com Newman & Player Expires April 1, 2007 [Page 30] Internet-Draft Hash and Stuffing September 2006 Full Copyright Statement Copyright (C) The Internet Society (2006). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Intellectual Property The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Acknowledgment Funding for the RFC Editor function is provided by the IETF Administrative Support Activity (IASA). Newman & Player Expires April 1, 2007 [Page 31]