draft-ietf-bmwg-hash-stuffing-05.txt   draft-ietf-bmwg-hash-stuffing-06.txt 
Network Working Group D. Newman Network Working Group D. Newman
Internet-Draft Network Test Internet-Draft Network Test
Expires: August 13, 2006 T. Player Intended status: Informational T. Player
Spirent Communications Expires: April 1, 2007 Spirent Communications
February 9, 2006 September 28, 2006
Hash and Stuffing: Overlooked Factors in Network Device Benchmarking Hash and Stuffing: Overlooked Factors in Network Device Benchmarking
draft-ietf-bmwg-hash-stuffing-05.txt draft-ietf-bmwg-hash-stuffing-06.txt
Status of this Memo Status of this Memo
By submitting this Internet-Draft, each author represents that any By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware 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 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. aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
skipping to change at page 1, line 35 skipping to change at page 1, line 35
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This Internet-Draft will expire on August 13, 2006. This Internet-Draft will expire on April 1, 2007.
Copyright Notice Copyright Notice
Copyright (C) The Internet Society (2006). Copyright (C) The Internet Society (2006).
Abstract Abstract
Test engineers take pains to declare all factors that affect a given Test engineers take pains to declare all factors that affect a given
measurement, including intended load, packet length, test duration, measurement, including intended load, packet length, test duration,
and traffic orientation. However, current benchmarking practice and traffic orientation. However, current benchmarking practice
skipping to change at page 2, line 12 skipping to change at page 3, line 7
addresses or other test traffic contents, even though these fields addresses or other test traffic contents, even though these fields
can affect test results. Second, "stuff" bits and bytes inserted in can affect test results. Second, "stuff" bits and bytes inserted in
test traffic by some link-layer technologies add significant and test traffic by some link-layer technologies add significant and
variable overhead, which in turn affects test results. This document variable overhead, which in turn affects test results. This document
describes the effects of these factors; recommends guidelines for describes the effects of these factors; recommends guidelines for
test traffic contents; and offers formulas for determining the test traffic contents; and offers formulas for determining the
probability of bit- and byte-stuffing in test traffic. probability of bit- and byte-stuffing in test traffic.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Requirements . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Requirements . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. General considerations . . . . . . . . . . . . . . . . . . . . 5 3. General considerations . . . . . . . . . . . . . . . . . . . . 6
3.1. Repeatability . . . . . . . . . . . . . . . . . . . . . . 5 3.1. Repeatability . . . . . . . . . . . . . . . . . . . . . . 6
3.2. Randomness . . . . . . . . . . . . . . . . . . . . . . . . 5 3.2. Randomness . . . . . . . . . . . . . . . . . . . . . . . . 6
4. Packet Content Variations . . . . . . . . . . . . . . . . . . 6 4. Packet Content Variations . . . . . . . . . . . . . . . . . . 7
4.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 6 4.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 7
4.2. Ethernet MAC Addresses . . . . . . . . . . . . . . . . . . 7 4.2. Ethernet MAC Addresses . . . . . . . . . . . . . . . . . . 8
4.2.1. Randomized Sets of MAC Addresses . . . . . . . . . . . 8 4.2.1. Randomized Sets of MAC Addresses . . . . . . . . . . . 9
4.3. MPLS Addressing . . . . . . . . . . . . . . . . . . . . . 10 4.3. MPLS Addressing . . . . . . . . . . . . . . . . . . . . . 11
4.4. Network-layer Addressing . . . . . . . . . . . . . . . . . 10 4.4. Network-layer Addressing . . . . . . . . . . . . . . . . . 11
4.5. Transport-layer Addressing . . . . . . . . . . . . . . . . 11 4.5. Transport-layer Addressing . . . . . . . . . . . . . . . . 12
4.6. Application-layer Patterns . . . . . . . . . . . . . . . . 11 4.6. Application-layer Patterns . . . . . . . . . . . . . . . . 12
5. Control Character Stuffing . . . . . . . . . . . . . . . . . . 12 5. Control Character Stuffing . . . . . . . . . . . . . . . . . . 13
5.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 12 5.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 13
5.2. PPP Bit Stuffing . . . . . . . . . . . . . . . . . . . . . 12 5.2. PPP Bit Stuffing . . . . . . . . . . . . . . . . . . . . . 13
5.2.1. Calculating Bit-Stuffing Probability . . . . . . . . . 15 5.2.1. Calculating Bit-Stuffing Probability . . . . . . . . . 16
5.2.2. Bit Stuffing for Finite Strings . . . . . . . . . . . 16 5.2.2. Bit Stuffing for Finite Strings . . . . . . . . . . . 17
5.2.3. Applied Bit Stuffing . . . . . . . . . . . . . . . . . 17 5.2.3. Applied Bit Stuffing . . . . . . . . . . . . . . . . . 18
5.3. POS Byte Stuffing . . . . . . . . . . . . . . . . . . . . 17 5.3. POS Byte Stuffing . . . . . . . . . . . . . . . . . . . . 18
5.3.1. Nullifying ACCM . . . . . . . . . . . . . . . . . . . 18 5.3.1. Nullifying ACCM . . . . . . . . . . . . . . . . . . . 19
5.3.2. Other Stuffed Characters . . . . . . . . . . . . . . . 18 5.3.2. Other Stuffed Characters . . . . . . . . . . . . . . . 19
5.3.3. Applied Byte Stuffing . . . . . . . . . . . . . . . . 18 5.3.3. Applied Byte Stuffing . . . . . . . . . . . . . . . . 19
6. Security Considerations . . . . . . . . . . . . . . . . . . . 20 6. Security Considerations . . . . . . . . . . . . . . . . . . . 21
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22
8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 22 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 23
8.1. Normative References . . . . . . . . . . . . . . . . . . . 22 8.1. Normative References . . . . . . . . . . . . . . . . . . . 23
8.2. Informative References . . . . . . . . . . . . . . . . . . 22 8.2. Informative References . . . . . . . . . . . . . . . . . . 23
Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 23 Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 24
Appendix B. Proof of Formula for Finite Bit Stuffing . . . . . . 24 Appendix B. Proof of Formula for Finite Bit Stuffing . . . . . . 25
Appendix C. Explicit Calculation of Bit Stuffing Overhead . . . . 25 Appendix C. Explicit Calculation of Bit Stuffing Overhead for
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 27 IPv4 . . . . . . . . . . . . . . . . . . . . . . . . 26
Intellectual Property and Copyright Statements . . . . . . . . . . 28 Appendix D. Explicit Calculation of Bit Stuffing Overhead for
IPv6 . . . . . . . . . . . . . . . . . . . . . . . . 28
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 30
Intellectual Property and Copyright Statements . . . . . . . . . . 31
1. Introduction 1. Introduction
Experience in benchmarking networking devices suggests that the Experience in benchmarking networking devices suggests that the
contents of test traffic can have a profound impact on test results. contents of test traffic can have a profound impact on test results.
For example, some devices may forward randomly addressed traffic For example, some devices may forward randomly addressed traffic
without loss, but drop significant numbers of packets when offered without loss, but drop significant numbers of packets when offered
packets containing nonrandom addresses. packets containing nonrandom addresses.
Methodologies such as [RFC2544] and [RFC2889] do not require any Methodologies such as [RFC2544] and [RFC2889] do not require any
declaration of packet contents. These methodologies do require the declaration of packet contents. These methodologies do require the
declaration of test parameters such as traffic distribution and declaration of test parameters such as traffic distribution and
traffic orientation, and yet packet contents can have at least as traffic orientation, and yet packet contents can have at least as
great an impact on test results as the other factors. Variations in great an impact on test results as the other factors. Variations in
packet contents also can lead to non-repeatability of test results: packet contents also can lead to non-repeatability of test results:
Two individuals may follow methodology procedures to the letter, and Two individuals may follow methodology procedures to the letter, and
still obtain very different results. still obtain very different results.
A related issue is the insertion of stuff bits or bytes by link-layer 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 technologies using PPP with HDLC-like framing. This stuffing is done
to ensure sequences in test traffic will not be confused with flag or to ensure sequences in test traffic will not be confused with control
control characters. characters.
Stuffing adds significant and variable overhead. Currently there is Stuffing adds significant and variable overhead. Currently there is
no standard method for determining the probability that stuffing will no standard method for determining the probability that stuffing will
occur for a given pattern, and thus no way to determine what impact occur for a given pattern, and thus no way to determine what impact
stuffing will have on test results. stuffing will have on test results.
This document covers two areas. First, we discuss strategies for This document covers two areas. First, we discuss strategies for
dealing with randomness and nonrandomness in test traffic. Second, dealing with randomness and nonrandomness in test traffic. Second,
we present formulas to determine the probability of bit- and byte- we present formulas to determine the probability of bit- and byte-
stuffing on PPP and POS circuits. In both areas, we provide stuffing on PPP and POS circuits. In both areas, we provide
recommendations for obtaining more repeatability in test results. recommendations for obtaining better repeatability in test results.
2. Requirements 2. Requirements
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119]. document are to be interpreted as described in [RFC2119].
3. General considerations 3. General considerations
3.1. Repeatability 3.1. Repeatability
Repeatability is a desirable trait in benchmarking, but it can be an Repeatability is a desirable trait in benchmarking, but it can be an
elusive goal. It is a common but mistaken belief that test results elusive goal. It is a common but mistaken belief that test results
can always be reproduced provided the device under test and test can always be reproduced provided the device under test and test
instrument are configured identically for each test iteration. In instrument are configured identically for each test iteration. In
fact, even identical configurations may introduce some variations in fact, even identical configurations may introduce some variations in
test traffic, such as changes in timestamps, TCP sequence numbers, or test traffic, such as changes in timestamps, TCP sequence numbers, or
other naturally occurring phenomena. other common phenomena.
While this variability does not necessarily invalidate test results, While this variability does not necessarily invalidate test results,
it is important to recognize such variation exists. Exact bit-for- it is important to recognize the existing variation. Exact bit-for-
bit reproduction of test traffic in all cases is a hard problem. A bit reproduction of test traffic is a hard problem. A simpler
simpler approach is to acknowledge that some variation exists, approach is to acknowledge that some variation exists, characterize
characterize that variation, and describe it when analyzing test that variation, and describe it when analyzing test results.
results.
3.2. Randomness 3.2. Randomness
This document recommends the use of pseudorandom patterns in test This document recommends the use of pseudorandom patterns in test
traffic under controlled lab conditions. The rand() functions traffic under controlled lab conditions. The rand() functions
available in many programming languages produce output that is available in many programming languages produce output that is
pseudorandom rather than truly random. Pseudorandom patterns are pseudorandom rather than truly random. Pseudorandom patterns are
sufficient for the recommendations given in this document, provided sufficient for the recommendations given in this document, provided
they produce output that is uniformly distributed across the pattern they produce output that is uniformly distributed across the pattern
space. space.
skipping to change at page 7, line 33 skipping to change at page 8, line 33
00:00:PP:00:00:RR 00:00:PP:00:00:RR
where PP is the source interface number of the test instrument and 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 is a pseudorandom number. In this case, there should be an equal
probability of the least significant 3 bits of the MAC address having probability of the least significant 3 bits of the MAC address having
any value from 000 to 111 inclusive. Thus, the outcome of XOR any value from 000 to 111 inclusive. Thus, the outcome of XOR
operations should be equally distributed from 0 to 7, and operations should be equally distributed from 0 to 7, and
distribution across NPs should also be equal (at least for this distribution across NPs should also be equal (at least for this
particular 3-bit hashing algorithm). Absent other impediments, the particular 3-bit hashing algorithm). Absent other impediments, the
device should be able to utilize 100 percent of available bandwidth. device should be able to utilize 100 percent of available capacity.
This simple example presumes knowledge on the tester's part of the This simple example presumes knowledge on the tester's part of the
hashing algorithm used by the device under test. Knowledge of such hashing algorithm used by the device under test. Knowledge of such
algorithms is not always possible beforehand, and in any event algorithms is not always possible beforehand, and in any event
violates the "black box" spirit of many documents produced by the violates the "black box" spirit of many documents produced by the
IETF BMWG. IETF BMWG.
Therefore, this memo adds a new consideration for benchmarking Therefore, this memo adds a new consideration for benchmarking
methodologies, to select traffic patterns that overcome the effects methodologies, to select traffic patterns that overcome the effects
of non-randomness regardless of the hashing algorithms in use. The of non-randomness regardless of the hashing algorithms in use. The
balance of this section offers recommendations for test traffic balance of this section offers recommendations for test traffic
patterns to avoid these effects, starting at the link layer and patterns to avoid these effects, starting at the link layer and
working up to the application layer. working up to the application layer.
4.2. Ethernet MAC Addresses 4.2. Ethernet MAC Addresses
Test traffic SHOULD use pseudorandom patterns in Ethernet addresses. Test traffic SHOULD use pseudorandom patterns in Ethernet addresses.
The following source and destination Ethernet address pattern is The following source and destination Ethernet address pattern is
RECOMMENDED for use when benchmarking Ethernet devices: RECOMMENDED for use when benchmarking Ethernet devices:
(RR & 0xFE):PP:PP:RR:RR:RR (RR & 0xFC):PP:PP:RR:RR:RR
where (RR & 0xFE) is a pseudorandom number bitwise ANDed with 0xFE, where (RR & 0xFC) is a pseudorandom number bitwise ANDed with 0xFC,
PP:PP is the 1-indexed interface number of the test instrument and PP:PP is the 1-indexed interface number of the test instrument and
RR:RR:RR is a pseudorandom number. RR:RR:RR is a pseudorandom number.
The bitwise ANDing of the high-order byte in the MAC address with The bitwise ANDing of the high-order byte in the MAC address with
0xFE guarantees a non multicast address. 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 Test traffic SHOULD use PP:PP to identify the source interface number
of the test instrument. Such identification can be useful in of the test instrument. Such identification can be useful in
troubleshooting. Allocating 2 bytes of the MAC address for interface troubleshooting. Allocating 2 bytes of the MAC address for interface
identification allows for tests of up to 65,536 interfaces. A 2-byte identification allows for tests of up to 65,536 interfaces. A 2-byte
space allows for tests much larger than those currently used in space allows for tests much larger than those currently used in
device benchmarking; however, tests involving more than 256 device benchmarking; however, tests involving more than 256
interfaces (fully utilizing a 1-byte space) are fairly common. interfaces (fully utilizing a 1-byte space) are fairly common.
Note that the "PP:PP" designation refers to the source interface of Note that the "PP:PP" designation refers to the source interface of
skipping to change at page 8, line 43 skipping to change at page 9, line 44
all-0s Ethernet address. Some devices will drop frames with all-0s all-0s Ethernet address. Some devices will drop frames with all-0s
Ethernet addresses. Ethernet addresses.
It is RECOMMENDED to use pseudorandom patterns in the least It is RECOMMENDED to use pseudorandom patterns in the least
significant 3 bytes of the MAC address. Using pseudorandom values significant 3 bytes of the MAC address. Using pseudorandom values
for the low-order 3 bytes means choosing one of 16.7 million unique for the low-order 3 bytes means choosing one of 16.7 million unique
addresses. While this address space is vastly larger than is addresses. While this address space is vastly larger than is
currently required in lab benchmarking, it does assure more realistic currently required in lab benchmarking, it does assure more realistic
test traffic. test traffic.
Note also that since only 31 of 48 bits in the MAC address have Note also that since only 30 of 48 bits in the MAC address have
pseudorandom values, there is no possibility of randomly generating a pseudorandom values, there is no possibility of randomly generating a
broadcast or multicast value by accident. broadcast or multicast value by accident.
4.2.1. Randomized Sets of MAC Addresses 4.2.1. Randomized Sets of MAC Addresses
It is common benchmarking practice for a test instrument to emulate It is common benchmarking practice for a test instrument to emulate
multiple hosts, even on a single interface. This is desirable in multiple hosts, even on a single interface. This is desirable in
assessing DUT/SUT scalability. assessing DUT/SUT scalability.
However, test instruments may emulate multiple MAC addresses by However, test instruments may emulate multiple MAC addresses by
skipping to change at page 10, line 6 skipping to change at page 11, line 8
produces only one or two out of eight possible outcomes. produces only one or two out of eight possible outcomes.
Every MAC address SHOULD be pseudorandom, not just the starting one. Every MAC address SHOULD be pseudorandom, not just the starting one.
When generating traffic with multiple addresses, it is RECOMMENDED When generating traffic with multiple addresses, it is RECOMMENDED
that all addresses use pseudorandom values. There are multiple ways that all addresses use pseudorandom values. There are multiple ways
to use sets of pseudorandom numbers. One strategy would be for the to use sets of pseudorandom numbers. One strategy would be for the
test instrument to iterate over an array of pseudorandom values test instrument to iterate over an array of pseudorandom values
rather than incrementing/decrementing from a starting address. The rather than incrementing/decrementing from a starting address. The
actual method is an implementation detail; in the end, any method actual method is an implementation detail; in the end, any method
that uses multiple addresses and avoids the undesired effects of that uses multiple addresses with pseudorandom patterns will be
address processing in the DUT/SUT will be sufficient sufficient
4.3. MPLS Addressing 4.3. MPLS Addressing
Similiar to L2 switches, MPLS routers make forwarding decisions based Similiar to L2 switches, MPLS routers make forwarding decisions based
on a 20 bit MPLS label. Unless specific labels are required, it is 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 RECOMMENDED that uniformly random values between 0 and 1,048,575 be
used for all labels assigned by test equipment. used for all labels assigned by test equipment.
4.4. Network-layer Addressing 4.4. Network-layer Addressing
skipping to change at page 10, line 46 skipping to change at page 11, line 48
source and destination IP addresses. source and destination IP addresses.
Just as in the case of MAC addresses, nonrandom IP addresses can have Just as in the case of MAC addresses, nonrandom IP addresses can have
an adverse effect on the outcome of ECMP link assignment decisions. an adverse effect on the outcome of ECMP link assignment decisions.
When benchmarking devices that implement ECMP or any other form of When benchmarking devices that implement ECMP or any other form of
Layer 3 aggregation, it is RECOMMENDED to use a randomly distributed Layer 3 aggregation, it is RECOMMENDED to use a randomly distributed
range of IP addresses. In particular, testers SHOULD NOT use range of IP addresses. In particular, testers SHOULD NOT use
addresses that produce the undesired effects of address processing. addresses that produce the undesired effects of address processing.
If, for example, a DUT can be observed to exhibit high packet loss 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 when offered IPv4 network addresses that take the form x.x.1.x/24,
relatively low packet loss when the source and destination network and relatively low packet loss when the source and destination
addresses take the form of x.x.R.x/24 (where R is some random value network addresses take the form of x.x.R.x/24 (where R is some random
between 0 and 9), test engineers SHOULD use the random pattern. value between 0 and 9), test engineers SHOULD use the random pattern.
4.5. Transport-layer Addressing 4.5. Transport-layer Addressing
Some devices with transport- or application-layer awareness use TCP Some devices with transport- or application-layer awareness use TCP
or UDP port numbers in making forwarding decisions. Examples of such or UDP port numbers in making forwarding decisions. Examples of such
devices include load balancers and application-layer firewalls. devices include load balancers and application-layer firewalls.
Test instruments have the capability of generating packets with Test instruments have the capability of generating packets with
random TCP and UDP source and destination port numbers. Known random TCP and UDP source and destination port numbers. Known
destination port numbers are often required for testing application- destination port numbers are often required for testing application-
layer devices. However, unless known port numbers are specifically layer devices. However, unless known port numbers are specifically
required for a test, it is RECOMMENDED to use randomly distributed required for a test, it is RECOMMENDED to use pseudorandom and
values for both source and destination port numbers. uniformly distributed values for both source and destination port
numbers.
In addition, it may be desirable to pick pseudorandom values from a In addition, it may be desirable to pick pseudorandom values from a
selected pool of numbers. Many services identify themselves through selected pool of numbers. Many services identify themselves through
use of reserved destination port numbers between 1 and 1023 use of reserved destination port numbers between 1 and 1023
inclusive. Unless specific port numbers are required, it is inclusive. Unless specific port numbers are required, it is
RECOMMENDED to pick randomly distributed destination port numbers RECOMMENDED to pick randomly distributed destination port numbers
between these lower and upper boundaries. between these lower and upper boundaries.
Similarly, clients typically choose source port numbers in the space Similarly, clients typically choose source port numbers in the space
between 1024 and 65535 inclusive. Unless specific port numbers are between 1024 and 65535 inclusive. Unless specific port numbers are
skipping to change at page 16, line 41 skipping to change at page 17, line 41
For a uniformly random finite bit string of length L, we can 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 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 strings of length L. This count can then be used to calculate the
expected number of stuffs for the string. expected number of stuffs for the string.
Let f(L) represent the number of bit-stuffs in the set of all 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 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) there are no strings of length 5. For L >= 5, f(L) = 2^(L-5) + (L-5)
* 2^(L-6) + f(L-5). * 2^(L-6) + f(L-5).
A proof of this formula can be found in Appendix A. A proof of this formula can be found in Appendix B.
Now, the expected number of stuffing events, E[stuffs], can be found 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 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. 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 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 bit-stuff 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 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 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). L_n, where 5 <= n <= L, caused a stuff is f(L) / (L * 2^L).
skipping to change at page 18, line 47 skipping to change at page 19, line 47
% overhead = E[byte-stuffs] / framesize (in bytes) % overhead = E[byte-stuffs] / framesize (in bytes)
When testing a DUT/SUT that implements PPP in HDLC-like framing and 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 L2TP (or any other technology that uses nonzero ACCM values), it is
RECOMMENDED that testers reduce the maximum intended load by 13.3 RECOMMENDED that testers reduce the maximum intended load by 13.3
percent to avoid introducing congestion. percent to avoid introducing congestion.
When testing a DUT/SUT that implements PPP in HDLC-like framing and 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 an ACCM value of 0x00, it is RECOMMENDED that testers reduce the
maximum offered load by 0.8 percent to avoid introducing congestion. maximum intended load by 0.8 percent to avoid introducing congestion.
Note that the percentages given above are approximations. For Note that the percentages given above are approximations. For
greatest precision, the actual intended load SHOULD be explictly greatest precision, the actual intended load SHOULD be explictly
calculated from the test traffic calculated from the test traffic
Note also that the DUT/SUT may be able to forward intended loads Note also that the DUT/SUT may be able to forward intended loads
higher than the calculated theoretical maximum rate without packet higher than the calculated theoretical maximum rate without packet
loss. Such results are the result of queuing on the part of the DUT/ 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- SUT. While a device's throughput may be above this level, delay-
related measurements may be affected. Accordingly, it is RECOMMENDED related measurements may be affected. Accordingly, it is RECOMMENDED
to reduce offered levels by the amount of byte-stuffing overhead when to reduce offered levels by the amount of byte-stuffing overhead when
testing devices using byte-synchronous links. This recommendation testing devices using byte-synchronous links. This recommendation
applies for all measurements, including throughput. applies for all measurements, including throughput.
6. Security Considerations 6. Security Considerations
This document recommends the use of pseudorandom patterns in test This document recommends the use of pseudorandom patterns in test
traffic. The rand() functions of many programming languages produce traffic. This usage requires a uniform distribution, but does not
output that is pseudorandom rather than truly random. As far as the have strict predictability requirements. Although it is not
authors are aware, pseudorandom patterns are sufficient for sufficient for security applications, the rand() function of many
generating test traffic in lab conditions. 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 [RFC2615], section 6, discusses a denial-of-service attack involving
the intentional transmission of characters that require stuffing. the intentional transmission of characters that require stuffing.
This attack could consume up to 100 percent of available bandwidth. This attack could consume up to 100 percent of available bandwidth.
However, the test networks described in BMWG documents generally However, the test networks described in BMWG documents generally
SHOULD NOT be reachable by anyone other than the tester(s). SHOULD NOT be reachable by anyone other than the tester(s).
7. IANA Considerations 7. IANA Considerations
This document has no actions for IANA. This document has no actions for IANA.
skipping to change at page 23, line 9 skipping to change at page 24, line 9
[Go97] Goralski, W., "SONET: A Guide to Synchronous Optical [Go97] Goralski, W., "SONET: A Guide to Synchronous Optical
Networks", 1997. Networks", 1997.
[Kn97] Knuth, D., "The Art of Computer Programming, Volume 2, Third [Kn97] Knuth, D., "The Art of Computer Programming, Volume 2, Third
Edition", 1997. Edition", 1997.
Appendix A. Acknowledgements Appendix A. Acknowledgements
The authors gratefully acknowledge reviews and contributions by Len The authors gratefully acknowledge reviews and contributions by Len
Ciavattone, Robert Craig, John Dawson, Neil Carter, Glenn Chagnot, Ciavattone, Robert Craig, John Dawson, Neil Carter, Glenn Chagnot,
Kevin Dubray, Rafael Francis, Paul Hoffman, David Joyner, Al Morton, Kevin Dubray, Diego Dugatkin, Rafael Francis, Paul Hoffman, David
Joe Perches, Scott Poretsky, and Kris Rousey. Joyner, Al Morton, Joe Perches, Jerry Perser, Scott Poretsky, and
Kris Rousey.
Appendix B. Proof of Formula for Finite Bit Stuffing Appendix B. Proof of Formula for Finite Bit Stuffing
We would like to construct a function, f(L), that allows us to 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 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. 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. 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- Clearly, when 0 <= L <= 4, f(L) = 0, as there can be no possible bit-
stuff if there are < 5 bits. stuff if there are < 5 bits.
skipping to change at page 25, line 5 skipping to change at page 26, line 5
sequence of bits to generate two stuffing events, there must be at 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), 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 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. above squence is irrelevant when looking for bit-stuffs.
Additionally, we've already determined that the number of strings 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) + 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 (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) = 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. 2^(L-5) + (L-5) * 2^(L-6) + f(L-5) for all L >= 5.
Appendix C. Explicit Calculation of Bit Stuffing Overhead Appendix C. Explicit Calculation of Bit Stuffing Overhead for IPv4
Consider a scenario where a tester is transmitting test frames across Consider a scenario where a tester is transmitting IPv4 test packets
a bit synchronous link. The test traffic has the following across a bit synchronous link. The test traffic has the following
parameters (values are in decimal): parameters (values are in decimal):
+----------------------+-----------------------------+ +----------------------+-----------------------------+
| Field | Value | | Field | Value |
+----------------------+-----------------------------+ +----------------------+-----------------------------+
| IP Version | 4 | | IP Version | 4 |
| | | | | |
| IP Header Length | 5 | | IP Header Length | 5 |
| | | | | |
| TOS | 0 | | TOS | 0 |
skipping to change at page 27, line 5 skipping to change at page 28, line 5
However, since we cannot have a fractional stuff, we round down to However, since we cannot have a fractional stuff, we round down to
130. Thus, we expect 130 stuffs per packet. 130. Thus, we expect 130 stuffs per packet.
Finally, we can calculate bit-stuffing overhead by dividing the Finally, we can calculate bit-stuffing overhead by dividing the
expected number of stuff bits by the total number of bits in the IP expected number of stuff bits by the total number of bits in the IP
datagram. So, this example traffic would generate 1.58% overhead. datagram. So, this example traffic would generate 1.58% overhead.
If our payload had consisted exclusively of zero bits, our 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% would have been 0.012%. An all ones payload would produce 19.47%
overhead. overhead.
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
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.
Authors' Addresses Authors' Addresses
David Newman David Newman
Network Test Network Test
Email: dnewman@networktest.com Email: dnewman@networktest.com
Timmons C. Player Timmons C. Player
Spirent Communications Spirent Communications
Email: timmons.player@spirentcom.com Email: timmons.player@spirentcom.com
Intellectual Property Statement 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 The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights 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 might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79. found in BCP 78 and BCP 79.
skipping to change at page 28, line 29 skipping to change at page 31, line 45
such proprietary rights by implementers or users of this such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr. http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at this standard. Please address the information to the IETF at
ietf-ipr@ietf.org. ietf-ipr@ietf.org.
Disclaimer of Validity
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 (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 Acknowledgment
Funding for the RFC Editor function is currently provided by the Funding for the RFC Editor function is provided by the IETF
Internet Society. Administrative Support Activity (IASA).
 End of changes. 26 change blocks. 
88 lines changed or deleted 182 lines changed or added

This html diff was produced by rfcdiff 1.33. The latest version is available from http://tools.ietf.org/tools/rfcdiff/