 1/draftietfbmwghashstuffing04.txt 20060211 01:12:17.000000000 +0100
+++ 2/draftietfbmwghashstuffing05.txt 20060211 01:12:17.000000000 +0100
@@ 1,19 +1,19 @@
Network Working Group D. Newman
InternetDraft Network Test
Expires: April 11, 2006 T. Player
+Expires: August 13, 2006 T. Player
Spirent Communications
 October 8, 2005
+ February 9, 2006
Hash and Stuffing: Overlooked Factors in Network Device Benchmarking
 draftietfbmwghashstuffing04.txt
+ draftietfbmwghashstuffing05.txt
Status of this Memo
By submitting this InternetDraft, 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.
InternetDrafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
@@ 24,73 +24,76 @@
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use InternetDrafts as reference
material or to cite them other than as "work in progress."
The list of current InternetDrafts can be accessed at
http://www.ietf.org/ietf/1idabstracts.txt.
The list of InternetDraft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
 This InternetDraft will expire on April 11, 2006.
+ This InternetDraft will expire on August 13, 2006.
Copyright Notice
 Copyright (C) The Internet Society (2005).
+ Copyright (C) The Internet Society (2006).
Abstract
Test engineers take pains to declare all factors that affect a given
 measurement, including offered load, packet length, test duration,
+ 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 linklayer 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 bytestuffing in test traffic.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Requirements . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. General considerations . . . . . . . . . . . . . . . . . . . . 5
3.1. Repeatability . . . . . . . . . . . . . . . . . . . . . . 5
3.2. Randomness . . . . . . . . . . . . . . . . . . . . . . . . 5
 4. Address Pattern Variations . . . . . . . . . . . . . . . . . . 6
+ 4. Packet Content Variations . . . . . . . . . . . . . . . . . . 6
4.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 6
4.2. Ethernet MAC Addresses . . . . . . . . . . . . . . . . . . 7
4.2.1. Randomized Sets of MAC Addresses . . . . . . . . . . . 8
4.3. MPLS Addressing . . . . . . . . . . . . . . . . . . . . . 10
4.4. Networklayer Addressing . . . . . . . . . . . . . . . . . 10
 4.5. Transportlayer Addressing . . . . . . . . . . . . . . . . 10
+ 4.5. Transportlayer Addressing . . . . . . . . . . . . . . . . 11
+ 4.6. Applicationlayer Patterns . . . . . . . . . . . . . . . . 11
5. Control Character Stuffing . . . . . . . . . . . . . . . . . . 12
5.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 12
5.2. PPP Bit Stuffing . . . . . . . . . . . . . . . . . . . . . 12
 5.2.1. Calculating BitStuffing Probability . . . . . . . . . 14
 5.2.2. Bit Stuffing for Finite Strings . . . . . . . . . . . 15
 5.2.3. Applied Bit Stuffing . . . . . . . . . . . . . . . . . 15
 5.3. POS Byte Stuffing . . . . . . . . . . . . . . . . . . . . 16
 5.3.1. Nullifying ACCM . . . . . . . . . . . . . . . . . . . 16
 5.3.2. Other Stuffed Characters . . . . . . . . . . . . . . . 17
 5.3.3. Applied Byte Stuffing . . . . . . . . . . . . . . . . 17
 6. Security Considerations . . . . . . . . . . . . . . . . . . . 18
 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19
 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20
 8.1. Normative References . . . . . . . . . . . . . . . . . . . 20
 8.2. Informative References . . . . . . . . . . . . . . . . . . 20
 Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 21
 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22
 Intellectual Property and Copyright Statements . . . . . . . . . . 23
+ 5.2.1. Calculating BitStuffing Probability . . . . . . . . . 15
+ 5.2.2. Bit Stuffing for Finite Strings . . . . . . . . . . . 16
+ 5.2.3. Applied Bit Stuffing . . . . . . . . . . . . . . . . . 17
+ 5.3. POS Byte Stuffing . . . . . . . . . . . . . . . . . . . . 17
+ 5.3.1. Nullifying ACCM . . . . . . . . . . . . . . . . . . . 18
+ 5.3.2. Other Stuffed Characters . . . . . . . . . . . . . . . 18
+ 5.3.3. Applied Byte Stuffing . . . . . . . . . . . . . . . . 18
+ 6. Security Considerations . . . . . . . . . . . . . . . . . . . 20
+ 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21
+ 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 22
+ 8.1. Normative References . . . . . . . . . . . . . . . . . . . 22
+ 8.2. Informative References . . . . . . . . . . . . . . . . . . 22
+ Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 23
+ Appendix B. Proof of Formula for Finite Bit Stuffing . . . . . . 24
+ Appendix C. Explicit Calculation of Bit Stuffing Overhead . . . . 25
+ Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 27
+ Intellectual Property and Copyright Statements . . . . . . . . . . 28
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
@@ 150,31 +153,30 @@
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.
4. Address Pattern Variations
+4. Packet Content Variations
4.1. Problem Statement
 The addresses and port numbers used in a test can have a significant
 impact on metrics such as throughput, jitter, latency, and loss.
 This is because many network devices feed such addresses into hashing
 algorithms to determine which path upon which to forward a given
 packet.
+ 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 example of an Ethernet switch with eight network
+ 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 
___ ___ ___ ___ ___ ___ ___ ___ 
@@ 233,24 +235,26 @@
distribution across NPs should also be equal (at least for this
particular 3bit hashing algorithm). Absent other impediments, the
device should be able to utilize 100 percent of available bandwidth.
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.
 The balance of this section offers recommendations for test traffic
 patterns, starting at the link layer and working up to the transport
 layer. These patterns should overcome the effects of nonrandomness
 regardless of the hashing algorithms in use.
+ Therefore, this memo adds a new consideration for benchmarking
+ methodologies, to select traffic patterns that overcome the effects
+ of nonrandomness 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
RECOMMENDED for use when benchmarking Ethernet devices:
(RR & 0xFE):PP:PP:RR:RR:RR
where (RR & 0xFE) is a pseudorandom number bitwise ANDed with 0xFE,
@@ 261,20 +265,28 @@
0xFE guarantees a non multicast 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 2byte
space allows for tests much larger than those currently used in
device benchmarking; however, tests involving more than 256
interfaces (fully utilizing a 1byte 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 1indexed and SHOULD NOT
be 0indexed. This avoids the low but nonzero probability of an
all0s Ethernet address. Some devices will drop frames with all0s
Ethernet addresses.
It is RECOMMENDED to use pseudorandom patterns in the least
significant 3 bytes of the MAC address. Using pseudorandom values
for the loworder 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
@@ 329,56 +341,64 @@
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 and avoids hash table collisions will be
 sufficient.
+ that uses multiple addresses and avoids the undesired effects of
+ address processing in the DUT/SUT 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. Networklayer Addressing
 Routers make forwarding decisions based on destination network
 address. Since there is no hashing of source and destination
 addresses, the requirement for pseudorandom patterns at the network
 layer is far less critical than in the Ethernet MAC address case.
+ 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.
 However, there are cases where randomly distributed IPv4 and/or IPv6
 addresses are desirable. For example, the equal cost multipath
 (ECMP) feature performs loadsharing across multiple links. Routers
 implementing ECMP may perform a hash of source and destination IP
 addresses in assigning flows.
+ 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.
+ 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.
+ 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 IP 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. Transportlayer Addressing
Some devices with transport or applicationlayer awareness use TCP
or UDP port numbers in making forwarding decisions. Examples of such
devices include load balancers and applicationlayer 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
@@ 391,35 +411,57 @@
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. Applicationlayer Patterns
+
+ Many measurements require the insertion of applicationlayer
+ header(s) and payload into test traffic. Applicationlayer packet
+ contents offer additional opportunities for stuffing to occur, and
+ may also present nonrandom outcomes when fed through application
+ layeraware hashing algorithms. Given the vast number of
+ applicationlayer protocols in use, we make no recommendation for
+ specific test traffic patterns to be used; however, test engineers
+ SHOULD be aware that applicationlayer traffic contents MAY produce
+ nonrandom outcomes with some hashing algorithms. The same issues
+ that apply with lowerlayer 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
+ applicationlayer 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.
+
5. Control Character Stuffing
5.1. Problem Statement
Linklayer technologies that use HDLClike 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, the amount of overhead is nondeterministic. 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.
+ reasons. First, explictly calculating the amount of overhead can be
+ nontrivial 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 linklayer 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.
@@ 428,41 +470,46 @@
introduce two kinds of escape sequences: bit and byte stuffing. Bit
stuffing refers to the insertion of an escape bit on bitsynchronous
links. Byte stuffing refers to the insertion of an escape byte on
bytesynchronous 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 0x7D, which contains six "1" bits.
+ the HDLC control character 0x7E, which contains six "1" bits.
Consider the following PPP frame containing a TCP/IP packet. Not
 shown is the 1byte flag sequence (0x7D), at least one of which must
+ shown is the 1byte flag sequence (0x7E), at least one of which must
occur between frames.
 The contents of the various frame fields can be described one of two
 ways:
+ The contents of the various frame fields can be described one of
+ three ways:
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.
 In the diagram below, 30 out of 48 total bytes are subject to change
 over the test duration. The fields containing the changeable bytes
 are given in ((double parentheses)).
+ 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)).
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 
+++++++++++++++++++++++++++++++++
@@ 477,68 +524,79 @@
 ((Sequence Number)) 
+++++++++++++++++++++++++++++++++
 ((Acknowledgment Number)) 
+++++++++++++++++++++++++++++++++
 Data  UAPRSF 
 Offset Reserved RCSSYI ((Window)) 
  GKHTNN 
+++++++++++++++++++++++++++++++++
 ((Checksum))  Urgent Pointer 
+++++++++++++++++++++++++++++++++
+  
+ / ((payload)) /
+  
+ +++++++++++++++++++++++++++++++++
 ((FCS (4 bytes) )) 
+++++++++++++++++++++++++++++++++
None of the other fields are known to contain sequences subject to
 bitstuffing, at least not in their entirety.
+ bitstuffing, 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 bitstuffing will occur.
5.2.1. Calculating BitStuffing Probability
In order to calculate bitstuffing probabilities, we assume that for
 any string of length L, the probability of the Lth + 1 bit equalling
 1 is 0.5 and the probability of the Lth + 1 bit equalling 0 is 0.5.
 Additionally, the value of the Lth + 1 bit is independant of any
 previous bits.
+ 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
+ We can calculate the probability of bitstuffing for both infinite
and finite strings of random bits. We begin with the infinitestring
 case, which is required to prove the finitestring case. For an
 infinitely long string of random bits, we will need to insert a stuff
 bit if and only if state 5 is reached in the following state table.
+ 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:
+ 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:
  start 1 2 3 4 5
 _______________________________________________________
 start  0.5  0.5  0.5  0.5  0.5  0.5
 1  0.5  0.0  0.0  0.0  0.0  0.5
 2  0.0  0.5  0.0  0.0  0.0  0.0
 3  0.0  0.0  0.5  0.0  0.0  0.0
 4  0.0  0.0  0.0  0.5  0.0  0.0
 5  0.0  0.0  0.0  0.0  0.5  0.0
+ \ 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:
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)
@@ 550,55 +608,69 @@
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 random bits, the probability
 of 5 sequential 1 bits is 1/62. Put another way, we expect to add
 one stuff bit for every 62 bits of random uniform data.
+ 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
 The above result indicates that for any string of uniformly
 distributed random bits, we expect a stuffing event to occur every 62
 bits. So, given a string of some finite length L, where L >= 5, the
 expected number of stuffs is simply L * 1/62.
+ For a uniformly random finite bit string of length L, we can
+ explicitly count the number of bitstuffs 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.
5.2.3. Applied Bit Stuffing
+ Let f(L) represent the number of bitstuffs 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^(L5) + (L5)
+ * 2^(L6) + f(L5).
 The amount of overhead attributable to bit stuffing may be calculated
 explicitly as long as the total number of random bits per frame,
 L_randbits, and the probability of stuffing, P(stuff), is known.
+ A proof of this formula can be found in Appendix A.
 % overhead = ( P(stuff) * L_randbits ) / framesize (in bits)
+ 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.
 Note that if the entire frame contains random bits, then the
 percentage overhead is simply the probability of stuffing expressed
 as a percentage.
+ Similiarly, the probability that any particular bit is the cause of a
+ bitstuff can be calculated by dividing the total number of stuffs in
+ 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).
 Given that the overhead added by bitstuffing is at most 1 in 62, or
 approximately 1.6 percent, it is RECOMMENDED that testers reduce the
 maximum offered load by 1.6 percent to avoid introducing congestion
 when testing devices using bitsynchronous interfaces (such as T1/E1,
+5.2.3. Applied Bit Stuffing
+
+ The amount of overhead attributable to bitstuffing may be calculated
+ explicitly as long as the expected number of stuff bits per frame,
+ E[bitstuffs] is known. For long uniformly random bitstrings,
+ E[bitstuffs] may be approximated by multiplying the length of the
+ string by 1/62.
+
+ % overhead = E[bitstuffs] / framesize (in bits)
+
+ Given that the overhead added by bitstuffing 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 bitsynchronous interfaces (such as T1/E1,
DS3, and the like).
The percentage given above is an approximation. For greatest
 precision, the actual offered load SHOULD be calculated using the
 percentage overhead formula above and then expressed in frames per
 second, rounded down to the nearest integer.
+ precision, the actual intended load SHOULD be explicitly calculated
+ from the test traffic.
 Note that the DUT/SUT may be able to forward offered loads higher
+ 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, delayrelated
measurements may be affected. Accordingly, it is RECOMMENDED to
reduce offered levels by the amount of bitstuffing overhead when
testing devices using bitsynchronous links. This recommendation
applies for all measurements, including throughput.
5.3. POS Byte Stuffing
@@ 635,46 +707,42 @@
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 bit or byte stuffing may be
 calculated explicitly as long as the total number of random bytes per
 frame, L_randbytes, and the probability of stuffing, P(stuff), is
 known.

 % overhead = ( P(stuff) * L_randbytes ) / framesize (in bytes)
+ The amount of overhead attributable to byte stuffing may be
+ calculated explicitly as long as the expected number of stuff bytes
+ per frame, E[bytestuffs], is known. For long uniformly random byte
+ strings, E[bytestuffs] may be approximated by multiplying the length
+ of the string by the probability that any single byte is a stuff
+ byte.
 Note that if the entire frame contains random bytes, then the
 percentage overhead is simply the probability of stuffing expressed
 as a percentage.
+ % overhead = E[bytestuffs] / framesize (in bytes)
When testing a DUT/SUT that implements PPP in HDLClike framing and
L2TP (or any other technology that uses nonzero ACCM values), it is
 RECOMMENDED that testers reduce the maximum offered load by 13.3
+ 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 HDLClike framing and
an ACCM value of 0x00, it is RECOMMENDED that testers reduce the
maximum offered load by 0.8 percent to avoid introducing congestion.
Note that the percentages given above are approximations. For
 greatest precision, the actual offered load SHOULD be calculated
 using the percentage overhead formula above and then expressed in
 frames per second (rounded down to the nearest integer).

 Note also that the DUT/SUT may be able to forward offered loads
+ greatest precision, the actual intended load SHOULD be explictly
+ 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. 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 bytestuffing overhead when
testing devices using bytesynchronous links. This recommendation
applies for all measurements, including throughput.
6. Security Considerations
@@ 726,23 +794,157 @@
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.
Appendix A. Acknowledgements
 The authors gratefully acknowledge reviews and contributions by Neil
 Carter, Glenn Chagnot, Rafael Francis, Paul Hoffman, David Joyner,
 Joe Perches, and Scott Poretsky.
+ The authors gratefully acknowledge reviews and contributions by Len
+ Ciavattone, Robert Craig, John Dawson, Neil Carter, Glenn Chagnot,
+ Kevin Dubray, Rafael Francis, Paul Hoffman, David Joyner, Al Morton,
+ Joe Perches, Scott Poretsky, 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
+ explictly count the total number of bitstuffs 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 bitstuff. Let us suppose that the first 5 bits, b_1,...,b_5,
+ cause a stuffing event. Then, there are (L5) bits that could have
+ any value, i.e. the bits in position b_6 to b_L. So, there must be
+ 2^(L5) 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 <= L4. In order to guarantee that b_n starts
+ a stuff sequence, b_(n1) 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 L6 bits which do not have
+ fixed values. Hence, for each value of n, there are 2^(L6) possible
+ strings with at least one bitstuff for a total of (L5) * 2^(L6)
+
+ So, given a string of length L, where L >= 5, we know that there are
+ 2^(L5) + (L5) * 2^(L6) strings which will be transmitted with at
+ least one stuffed bit. However, if L >= 10, then there could be more
+ than one bitstuff 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 <= L9. 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 bitstuffs.
+ Additionally, we've already determined that the number of strings
+ with at least one stuff in a bit string of length L is 2^(L5) +
+ (L5) * 2^(L6). Thus, the total number of stuffing events in the
+ set of all bit strings of length L can be represented as f(L) =
+ 2^(L5) + (L5) * 2^(L6) + f(L5) for all L >= 5.
+
+Appendix C. Explicit Calculation of Bit Stuffing Overhead
+
+ Consider a scenario where a tester is transmitting test frames 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.1192.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 bitstuffing 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.
+
+ 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 bitstuffing 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.
Authors' Addresses
David Newman
Network Test
Email: dnewman@networktest.com
Timmons C. Player
Spirent Communications
@@ 778,18 +980,18 @@
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.
Copyright Statement
 Copyright (C) The Internet Society (2005). This document is subject
+ 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.
Acknowledgment
Funding for the RFC Editor function is currently provided by the
Internet Society.