RFC 4814
Hash and Stuffing: Overlooked Factors in Network Device Benchmarking
Hash and Stuffing: Overlooked Factors in Network Device Benchmarking 🦋
Title block tea ☕: this is RFC 4814, filed under the Network Working Group in March 2007. It's an Informational doc, so it's sharing knowledge rather than setting a standard. The authors are D. Newman (Network Test) and T. Player (Spirent Communications). The title block doesn't list anything it obsoletes or updates.
Status of This Memo ✨
This memo gives info to the Internet community. It is not an Internet standard of any kind, and anyone can share it freely with no limits. 🌸
Copyright Notice 💜
The IETF Trust holds the copyright, and the notice says Copyright (C) The IETF Trust (2007). 🎀
Abstract 🔥
Okay so test engineers are SO thorough. They declare everything that could change a measurement: the intended load, packet length, how long the test runs, and which way the traffic goes. But bestie, current benchmarking practice misses two factors that seriously change results. 😭
First, the existing methods don't require anyone to report the addresses or other contents of test traffic, even though those fields can change the outcome. Second, "stuff" bits and bytes that some link-layer technologies slip into test traffic add a big, variable amount of overhead, and that messes with results too. 💀
This doc explains how these factors work, suggests guidelines for what goes inside test traffic, and gives formulas for figuring out how likely bit- and byte-stuffing is in test traffic. ✨
Table of Contents 🧚
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Requirements . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. General Considerations . . . . . . . . . . . . . . . . . . . . 4
3.1. Repeatability . . . . . . . . . . . . . . . . . . . . . . 4
3.2. Randomness . . . . . . . . . . . . . . . . . . . . . . . . 4
4. Packet Content Variations . . . . . . . . . . . . . . . . . . 5
4.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 5
4.2. IEEE 802 MAC Addresses . . . . . . . . . . . . . . . . . . 7
4.2.1. Randomized Sets of MAC Addresses . . . . . . . . . . . 8
4.3. MPLS Addressing . . . . . . . . . . . . . . . . . . . . . 9
4.4. Network-layer Addressing . . . . . . . . . . . . . . . . . 9
4.5. Transport-Layer Addressing . . . . . . . . . . . . . . . . 10
4.6. Application-Layer Patterns . . . . . . . . . . . . . . . . 10
5. Control Character Stuffing . . . . . . . . . . . . . . . . . . 11
5.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 11
5.2. PPP Bit-Stuffing . . . . . . . . . . . . . . . . . . . . . 12
5.2.1. Calculating Bit-Stuffing Probability . . . . . . . . . 14
5.2.2. Bit-Stuffing for Finite Strings . . . . . . . . . . . 15
5.2.3. Applied Bit-Stuffing . . . . . . . . . . . . . . . . . 16
5.3. POS Byte-Stuffing . . . . . . . . . . . . . . . . . . . . 16
5.3.1. Nullifying ACCM . . . . . . . . . . . . . . . . . . . 17
5.3.2. Other Stuffed Characters . . . . . . . . . . . . . . . 17
5.3.3. Applied Byte-Stuffing . . . . . . . . . . . . . . . . 17
6. Security Considerations . . . . . . . . . . . . . . . . . . . 18
7. Normative References . . . . . . . . . . . . . . . . . . . . . 19
Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 20
Appendix B. Proof of Formula for Finite Bit-Stuffing . . . . . . 20
Appendix C. Explicit Calculation of Bit-Stuffing Overhead for
IPv4 . . . . . . . . . . . . . . . . . . . . . . . . 21
Appendix D. Explicit Calculation of Bit-Stuffing Overhead for
IPv6 . . . . . . . . . . . . . . . . . . . . . . . . 23
Appendix E. Terminology . . . . . . . . . . . . . . . . . . . . . 241. Introduction 🌈
Okay so experience with benchmarking networking devices shows that what's inside test traffic can totally change the results. 😭 For example, some devices may forward randomly addressed traffic with zero loss, but then drop a bunch of packets when they're handed packets with nonrandom addresses. Wild, right? 💅
Methodologies like [RFC2544] and [RFC2889] don't require any declaration of packet contents. They do make you declare test parameters like traffic distribution and traffic orientation, but packet contents can matter at least as much as those. 🙈 Changing the contents can also make results non-repeatable: two people can follow the methodology to the letter and still get very different numbers. Not fair, bestie. 😤
There's also a related issue: link-layer technologies that use PPP with High-Level Data Link Control (HDLC)-like framing insert stuff bits or bytes. They do this so that sequences in test traffic can't get mistaken for control characters. 🧚
That stuffing adds significant and variable overhead. Right now there's no standard way to figure out how likely stuffing is for a given pattern, so there's no way to know how much it will change the results. Iconic behavior from the standards world, honestly. 💀
This document covers two areas. First, it talks about how to handle randomness and nonrandomness in test traffic. Second, it gives formulas for the probability of bit- and byte-stuffing on Point-to-Point Protocol (PPP) and Packet over SONET (POS) circuits. In both areas, it gives recommendations for better repeatability in test results. 🦋
Benchmarking activities described in this memo are limited to technology characterization using controlled stimuli in a laboratory environment, using dedicated address space. Lab-only, periodt. 🔬
The benchmarking network topology will be an independent test setup. It MUST NOT be connected to devices that might forward the test traffic into a production network, or misroute traffic to the test management network. This is a hard no, bestie. 🚫
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 read as described in [RFC2119]. 🎀
3. General Considerations 🌸
3.1. Repeatability 🔁
Repeatability is a super desirable trait in benchmarking, but it's kinda elusive. People often assume test results can always be recreated as long as the device under test and the test instrument are configured the same way every iteration. Mistaken belief, babe. 🙈 Even identical configs can add some variation to test traffic, like changes in timestamps, TCP sequence numbers, or other common stuff.
This variability doesn't automatically invalidate results, but you have to notice it. Exact bit-for-bit repeatability of test traffic is a genuinely hard problem. A simpler move is to admit some variation exists, characterize it, and describe it when you analyze the results. ✨
Randomness is another repeatability thing. Benchmarking experience with some IEEE 802.11 devices suggests that nonrandom media access control (MAC) and IP addresses must be used across multiple trials. That seems to contradict some recommendations in this document, but honestly, either nonrandom or pseudorandom patterns may be more desirable depending on the test setup. Sometimes it's even good to mix the two, like generating a pseudorandom traffic pattern for one trial and then reusing that same pattern across all the trials. Main character energy in the test design 👑. The keywords in this document are RECOMMENDs and not MUSTs when it comes to pseudorandom test traffic patterns. 💅
Also, this section is only about repeatability, which is about how much test results vary from trial to trial on the same test bed. Reproducibility is a separate concern: it's about how precise results are when they come from different test beds. Clearly, reproducing across multiple test beds needs repeatability on a single test bed first. Build the foundation, bestie. 🧱
3.2. Randomness 🎲
This document recommends pseudorandom patterns in test traffic under controlled lab conditions. The rand() functions in many programming languages give output that's pseudorandom rather than truly random. Pseudorandom patterns are good enough for the recommendations here, as long as they produce output that's uniformly distributed across the pattern space. Iykyk. 🦋
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. Math with a glow-up. ✨
4. Packet Content Variations 💅
4.1. Problem Statement 🌸
okay bestie, test traffic contents can seriously change your numbers 📉. throughput, jitter, latency, and loss all depend on it. like, many network devices feed addresses into a hashing algorithm to decide which path a packet takes 🛤️
picture an Ethernet switch with eight network processors (NPs) in its switching fabric 🧚
ingress
||
\/
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ___ ___ ___ ___ ___ ___ ___ ___ |
|| | | | | | | | | | | | | | | | |
||NP0| |NP1| |NP2| |NP3| |NP4| |NP5| |NP6| |NP7| |
||___| |___| |___| |___| |___| |___| |___| |___| |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
||
\/
egressso to assign incoming traffic to the various NPs, let's say a hashing algorithm does 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. no cap 💀)
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, though, the actual outcome of the hash (and thus any test results) will be very different depending on the degree of randomness in test traffic 😭
now suppose the traffic is nonrandom, so every interface of the test instrument uses this pattern in its source MAC addresses:
00:00:PP:00:00:01where 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. so the outcome of the XOR operation will always be 0, given the same three least significant bits:
001 ^ 001 = 000the switch will assign ALL the 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:RRwhere PP is the source interface number of the test instrument and RR is a pseudorandom number. here there should be an equal probability of the least significant 3 bits of the MAC address having any value from 000 to 111 inclusive. so 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 🙌
ngl this simple example presumes the tester knows the hashing algorithm used by the device under test. knowing those algorithms isn't always possible beforehand, and in any event it violates the "black box" spirit of many documents produced by the IETF Benchmarking Working Group (BMWG) 🙈
so this memo adds a new consideration for benchmarking methodologies: select traffic patterns that overcome the effects of nonrandomness, regardless of the hashing algorithms in use 💖 the rest 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. IEEE 802 MAC Addresses 🦋
test traffic SHOULD use pseudorandom patterns in IEEE 802 MAC addresses. the following source and destination MAC address pattern is RECOMMENDED:
(RR & 0xFC):PP:PP:RR:RR:RRwhere (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 low-order two bits of that byte to 0, guaranteeing a non-multicast address and a non locally administered address ✨ note that the resulting addresses may violate IEEE 802 standards by using organizationally unique identifiers (OUIs) not assigned to the test port manufacturer. however, since these addresses will be used only on isolated test networks, there should be no possibility of mistaken identity 🫶
test traffic SHOULD use PP:PP to identify the source interface number of the test instrument. this identification can be super 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 device under test/system under test (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 zero-indexed. this avoids the low but nonzero probability of an all-zeros MAC address. some devices will drop frames with all-zeros MAC 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 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:87again 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 = 011note 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 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 💅
experience with benchmarking of IEEE 802.11 devices suggests suboptimal test outcomes may result if different pseudorandom MAC and IP addresses are used from trial to trial. in such cases (not just for 802.11 but for any device using IEEE 802 MAC and IP addresses), testers MAY generate a pseudorandom set of MAC and IP addresses once, or MAY generate a nonrandom set of MAC and IP addresses once. in either case, the same MAC and IP addresses MUST be used in all trials 🔒
4.3. MPLS Addressing 🧚♀️
similar to L2 switches, multiprotocol label switching (MPLS) devices make forwarding decisions based on a 20-bit MPLS label. unless specific labels are required, it is RECOMMENDED that uniformly random values between 16 and 1,048,575 be used for all labels assigned by test equipment. as per [RFC3032], this avoids using reserved MPLS labels in the range of 0-15 inclusive 🌸
4.4. Network-layer Addressing 🌈
when routers make forwarding decisions based solely on the destination network address, there may be no potential for hashing collision of source and destination addresses, like in the Ethernet switching case we talked about earlier. however, the potential still exists for hashing collisions 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 "tie-breaker" 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 like with 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 🎀
4.5. Transport-Layer Addressing 🦋
okay so some devices can actually peek at TCP or UDP port numbers and use them to decide where a packet goes 👀 load balancers and application-layer firewalls are the big examples, and they're lowkey obsessed with ports.
Test instruments can generate packets with random TCP and UDP source and destination port numbers 🎲 but app-layer devices often need known destination ports to test properly, so it's a bit of a balancing act. Unless a test specifically needs certain ports, it is RECOMMENDED to use pseudorandom and uniformly distributed values for both source and destination port numbers 💅
It may also be a vibe to pick pseudorandom values from a chosen pool of numbers 🌸 Lots of services announce themselves on reserved destination ports between 1 and 49151 inclusive. So unless specific ports are needed, it is RECOMMENDED to pick randomly distributed destination port numbers between those lower and upper bounds 🎀
Clients usually grab their source ports from the range between 1024 and 65535 inclusive 🌈 Again, unless specific port numbers are required, it is RECOMMENDED to pick randomly distributed source port numbers between those bounds ✨
4.6. Application-Layer Patterns 🧚
Most measurements need application-layer headers and a payload stuffed into the test traffic 📦 And this is where things get extra, because app-layer contents give stuffing even more places to happen, and they can come out nonrandom when they go through app-layer-aware hashing algorithms 😭
There are sooo many application-layer protocols out there, so we're not going to recommend any specific test traffic patterns 🙈 Still, test engineers SHOULD be aware that application-layer traffic contents MAY produce nonrandom outcomes with some hashing algorithms 💀 The same problems that show up at lower layers also show up at the application layer, and as section 5 explains, stuffing can happen with any part of a test packet, app-layer contents included 🫶
For example, some traffic generators slip fields into payloads so they can tell test traffic apart 🍓 Those fields might hold a transmission timestamp, a sequence number, a test equipment interface identifier and/or "stream" number, and a cyclic redundancy check (CRC) over the test payload or test packet. Every single one of those fields is a potential stuffing candidate 🔥
5. Control Character Stuffing 👑
5.1. Problem Statement 💜
Link-layer technologies that use High-Level Data Link Control (HDLC)-like framing may insert an extra bit or byte in front of each control character in the traffic 🫧 Those "stuffing" insertions keep control characters from getting confused with real data, but they can also add a lot of overhead 😩 Stuffing depends on the data, so picking different payload patterns means the frames on the media come out at different lengths, even when the original frames were all the same size 🤯
The overhead from these escape sequences is a problem for two reasons 💁♀️ First, working out exactly how much overhead there is can be non-trivial, or even impossible, for certain kinds of test traffic. In those cases, the best testers can do is characterize the probability that an escape sequence will happen for a given pattern. That makes it way harder to declare exactly how much traffic is offered to a DUT/SUT 🥺
Second, if nobody characterizes and compensates for this overhead, the tester can accidentally congest the DUT/SUT without meaning to 😱 Say a tester wants to offer traffic to a DUT at 95 percent of line rate, but the link-layer protocol adds another 1 percent of overhead to escape control characters. Then the aggregate offered load is actually 96 percent of line rate. If the DUT's real channel capacity is only 95 percent, congestion happens and the DUT drops traffic even though the tester never meant for that to happen 💀
As described in [RFC1661] and [RFC1662], PPP and HDLC-like framing bring in two kinds of escape sequences: bit- and byte-stuffing 🌷 Bit-stuffing is the insertion of an escape bit on bit-synchronous links. Byte-stuffing is the insertion of an escape byte on byte-synchronous links. We'll go through each one in turn 🎀
5.2. PPP Bit-Stuffing 🩷
[RFC1662], section 5.2, says that any sequence of five contiguous "1" bits within a frame must be escaped by inserting a "0" bit before the sequence 🧠 This escaping is needed so it doesn't get mixed up with the HDLC control character 0x7E, which has six "1" bits in a row 🙃
Here's a PPP frame carrying a TCP/IP packet 📦 It doesn't show the 1-byte flag sequence (0x7E), and at least one of those must occur between frames.
The contents of the various frame fields can be described in one of three ways:
- Field contents never change over the test duration. An example would be the IP version number.
- Field contents change over the test duration. Some of these changes are known before the test starts. An example would be incrementing IP addresses. Some of these changes are unknown. An example would be a dynamically calculated field such as the TCP checksum.
- Field contents may not be known. An example would be proprietary payload fields in test packets.
In the diagram below, 30 out of the 48 total bytes in the packet headers can change over the test duration 📊 On top of that, the payload field could change in both content and size 🌈 The fields with changeable bytes are marked with ((double parentheses)) 🧚
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 that get bit-stuffed, at least not in their entirety 🤔 This example has no payload, but as section 4.6 noted, test traffic payloads often give stuffing extra chances to happen, and they MUST be taken into account when calculating stuff probability 🚨 Assuming static contents for the rest of the fields, the challenge is working out the probability that bit-stuffing occurs ✨
5.2.1. Calculating Bit-Stuffing Probability 🔮
To calculate bit-stuffing probabilities, we assume that for any string of length L, where b_n is the "n"th bit of the string and 1 <= n <= L, the probability of b_n being "1" is 0.5, and the probability of b_n being "0" is also 0.5. On top of that, the value of b_n is independent of every other bit 🎲
We can calculate bit-stuffing probability for both infinite and finite strings of random bits 💫 We'll start with the infinite-string case. For an infinitely long string of uniformly random bits, we need to insert a stuff bit if and only if state 5 is reached in the state table below 🫶
|--------------------<----------------------|
| |1
_______ __|__ _____ _____ _____ __|__
| | 1 | | 1 | | 1 | | 1 | | 1 | |
| start |--->| 1 |--->| 2 |--->| 3 |--->| 4 |--->| 5 |
|_______| |_____| |_____| |_____| |_____| |_____|
| | | | | | |
| |0 |0 |0 |0 |0 |0
|-<-|----<----|----<-----|----<-----|----<-----|----<-----|We start in the "start" state. A "1" bit moves us to the next highest state, and a "0" bit sends us back to start. From state 5, a "1" bit takes us back to the 1 state and a "0" bit returns us to "start" 🔄
From this state diagram 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.0With this matrix we can set up a system of equations. If P(x) is the probability of reaching state x, then 🧮
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) = 1Solving this system gives us 🎉
P(start) = 0.5
P(1) = 8/31
P(2) = 4/31
P(3) = 2/31
P(4) = 1/31
P(5) = 1/62So for an infinitely long string of uniformly random bits, the probability that any individual bit causes a transition to state 5, and therefore causes a stuff, is 1/62 🦋✨
5.2.2. Bit-Stuffing for Finite Strings 🧮✨
Okay so, if you grab a uniformly random finite bit string of length L, you can actually count every single bit-stuff across ALL possible strings of length L 🤯. Then you use that count to work out the expected number of stuffs for the string. It's giving math bestie 💅
Let f(L) be the number of bit-stuffs in the set of all possible strings of length L. Clearly, for 0 <= L <= 4, f(L) = 0 because there are no strings of length 5 🙈. For L >= 5, the formula is:
f(L) = 2^(L-5) + (L-5) * 2^(L-6) + f(L-5)A proof of this formula lives in Appendix B 🎀.
Now, the expected number of stuffing events, E[stuffs], is the total number of stuffs across all possible strings divided by the total number of strings. So for any L:
E[stuffs] = f(L) / 2^LSimilarly, the probability that any particular bit causes a bit-stuff is the total number of stuffs across all strings of length L divided by the total number of bits across all strings of length L. So 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 overhead from bit-stuffing can 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] can be approximated by multiplying the length of the string by 1/62 🌸.
% overhead = E[bit-stuffs] / framesize (in bits)Given that the overhead from bit-stuffing is about 1 in 62, or 1.6 percent, it is RECOMMENDED that testers reduce the maximum intended load by 1.6 percent so they don't cause congestion when testing devices using bit-synchronous interfaces (like T1/E1, DS-3, and the like) 🍓.
The percentage above is an approximation. For the 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. This happens because of queuing on the part of the DUT/SUT. The device's throughput may be above this level, but delay-related measurements may get affected 😭. So 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 is that a stuff byte gets inserted 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 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 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. So 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 overhead from byte-stuffing can 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.
The percentages above are approximations. For the greatest precision, the actual intended load SHOULD be explicitly calculated from the test traffic.
Note also that the DUT/SUT may be able to forward intended loads higher than the calculated theoretical maximum rate without packet loss. This happens because of queuing on the part of the DUT/SUT. The device's throughput may be above this level, but delay-related measurements may get affected. So 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.
6. Security Considerations 🚨
This document recommends the use of pseudorandom patterns in test traffic. This usage requires a uniform distribution, but it 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) 🔐.
7. 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.
[RFC3032] Rosen, E., Tappan, D., Fedorkow, G., Rekhter, Y.,
Farinacci, D., Li, T., and A. Conta, "MPLS Label Stack
Encoding", RFC 3032, January 2001.Appendix A. Acknowledgements 🫶
The authors gratefully acknowledge reviews and contributions by Tom Alexander, 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, Dan Romascanu, and Kris Rousey 🌈.
Appendix B. Proof of Formula for Finite Bit-Stuffing 🧠🧚
We would like to construct a function, f(L), that allows us to explicitly 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 fewer than 5 bits.
Suppose L >= 5. Then there is 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 positions 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 causes 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 that have fixed values in the string S, and a total of L-6 bits that 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 "1" 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 has to 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 sequence 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🌸 That's the whole proof, bestie! 🌸
Appendix C. Explicit Calculation of Bit-Stuffing Overhead for IPv4 ✨
Okay so, picture this 🎀 a tester is blasting IPv4 test packets across a bit synchronous link, and she wants to know exactly how much stuffing she's getting. Here are the vibes (values in decimal, periodt 💅):
+-----------------------+---------------------------+
| Field | Value |
+-----------------------+---------------------------+
| IP Version | 4 |
| IP Header Length | 5 |
| Type of service (TOS) | 0 |
| Datagram Length | 1028 |
| ID | 0 |
| Flags/Fragments | 0 |
| Time to live (TTL) | 64 |
| Protocol | 17 |
| Source IP | 192.18.13.1-192.18.13.254 |
| Destination IP | 192.18.1.10 |
| Source UDP Port | pseudorandom port |
| Destination UDP Port | pseudorandom port |
| UDP Length | 1008 |
| Payload | 1000 pseudorandom bytes |
+-----------------------+---------------------------+So the goal is to figure out E[packet stuffs] 🧮🦋, which is the expected number of stuffs per packet. Let's go 🫶
First up, there are 254 different IP headers to think about 😭, and the source IP's changing 4th octet is gonna cause the occasional bit-stuffing moment, so we have to count those. Also, the 3rd octet of the source IP and the first octet of the destination IP are both gonna mess with the stuffing, so they're in the mix too 💜
An exhaustive search shows that cycling through all 254 headers gives 51 bit-stuffs for the destination IP address. So that's an expectation of 51/254 stuffs per packet from the changing source IP address 🌸
For the IP CRC, the value goes down as the source IP goes up. A little calculation shows the CRC values for these headers land somewhere in the range 0xE790 to 0xE88F ✨
Also, both the protocol and the source IP address have to be considered, since they hand over some extra leading and trailing "1" bits 🙈
An exhaustive search shows that cycling through all 254 headers gives 102 bit-stuffs for the CRC. That's an expectation of 102/254 stuffs per packet due to the CRC 💅
Now the UDP part, which is where it gets spicy 🌶️. Since the destination IP address is even and the UDP length is less than 32768, the random source and destination ports give us 32 bits of sequential random data, and we don't have to worry about the boundary bits 🎀. We also assume the payload is pseudorandom, so the UDP CRC is pseudorandom too 🌈 The even UDP length field again means we only consider the bits actually inside the CRC and data fields 🫶
So, using the formula for the expected number of stuffs in a finite string from section 5.2.2, we get E[UDP stuffs] = f(32)/2^32 + f(8000+16)/2^(8000+16). Now, f(32)/2^32 is totally doable and comes out to about 0.465 🧠. But f(8016)/2^8016 is way too large to calculate easily 💀, so we approximate it using the probability value from section 5.2.1. That gives us E[UDP] ~ 0.465 + 8016/62 ~ 129.755 🔥
Putting it all together: E[packet stuffs] = 51/254 + 102/254 + 129.755 = 130.357 ✨. But we can't have a fractional stuff, so we round down to 130. Thus, we expect 130 stuffs per packet 👑
Last step: we get the 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 generates 1.58% overhead 🍓. If the payload were all zero bits, the overhead would be 0.012%. An all-ones payload? 19.47% overhead 😭💖
Appendix D. Explicit Calculation of Bit-Stuffing Overhead for IPv6 🧚
Same energy, new protocol 🦋. Here's a tester sending IPv6 test packets across a bit-synchronous link. The values are in decimal, except the 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 | 2001:DB8:0:1::1-2001:DB8:0:1::FF |
| Destination IP | 2001:DB8:0:2::10 |
| Source UDP Port | pseudorandom port |
| Destination UDP Port | pseudorandom port |
| UDP Length | 1008 |
| Payload | 1000 pseudorandom bytes |
+----------------------+----------------------------------+Our goal is still E[packet stuffs] 🌸, the expected number of stuffs per packet.
First, there are 255 different IP headers to consider 🎀, and the changing 4th quad in the source IP addresses will cause occasional bit-stuffing events, so we count those too 💜. Also, since the first quad of the destination address has a leading zero bit, we don't have to consider those adjacent bits when counting bit-stuffs in the source IP address 🙈
An exhaustive search shows that cycling through all 255 headers produces 20 bit-stuffs for the source IP address. That's an expectation of 20/255 stuffs per packet due to the changing source IP address ✨
We also have to deal with the pseudorandomly generated flow label 🌈. But since the Traffic Class field is 0 and the Payload Length field is less than 32768 (so its leading bit is 0), we can treat the flow label as 20 bits of random data 🫶. That makes the expectation of a stuff in the flow label f(20)/2^20 ~ .272 💅
Just like the flow label case, the fourth quad of the destination IP address is even and the UDP length field is less than 32768. So the random source and destination ports give us 32 bits of sequential random data, and we don't have to consider the boundary bits 🦋. We also assume the payload is pseudorandom, so the UDP CRC is too 🌸. The even UDP length field again means we only consider the bits inside the CRC and data fields. So, using the formula for the expected number of stuffs in a finite string from section 5.2.2, E[UDP stuffs] = f(32)/2^32 + f(8000+16)/2^(8000+16). f(32)/2^32 is about 0.465 🧠. For f(8016)/2^8016, which is too large to calculate easily 💀, we approximate using the probability value from section 5.2.1. So E[UDP stuffs] ~ 0.465 + 8016/62 ~ 129.755 🔥
Now we can explicitly calculate E[packet stuffs] = 20/255 + 0.272 + 129.755 = 130.105 ✨. Since we can't have a fractional stuff, we round down to 130. So we expect 130 stuffs per packet 👑
Finally, the bit-stuffing overhead is the expected number of stuff bits divided by the total number of bits in the IP datagram. So this traffic generates 1.55% overhead 🍓. With an all-zero payload, the overhead would be 0.010%. An all-ones payload gives 19.09% overhead 😭💖
Appendix E. Terminology 📚
Hashing
Also known as a hash function. In this document, it's an algorithm that transforms data for use in path selection by a networking device. For example, an Ethernet switch with multiple processing elements might use the source and destination MAC addresses of an incoming frame as input to a hash function. The hash function produces numeric output that tells the switch which processing element to use when forwarding the frame 🔀
Randomness
In this document, it means having an equal probability of any possible outcome for a given pattern space. For example, if an experiment has N randomly distributed outcomes, then any individual outcome has a 1 in N chance of happening 🎲
Repeatability
The precision of test results obtained on a single test bed, but from trial to trial. See also "reproducibility" 🔁
Reproducibility
The precision of test results between different setups, possibly at different locations. See also "repeatability" 🌍
Stuffing
The insertion of a bit or byte within a frame to avoid confusion with control characters. For example, RFC 1662 requires the insertion of a "0" bit before any sequence of five contiguous "1" bits within a frame, so it doesn't get mixed up with the HDLC control character 0x7E 💅
Authors' Addresses
David Newman Network Test
EMail: dnewman@networktest.com
Timmons C. Player Spirent Communications
EMail: timmons.player@spirent.com
Full Copyright Statement
Copyright (C) The IETF Trust (2007).
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, THE IETF TRUST 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.
Acknowledgement
Funding for the RFC Editor function is currently provided by the Internet Society.
📦 where this page comes from
- ietf: rfc4814 2007-03
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms