draft-ietf-bmwg-hash-stuffing-08.txt   rfc4814.txt 
Network Working Group D. Newman Network Working Group D. Newman
Internet-Draft Network Test Request for Comments: 4814 Network Test
Expires: July 4, 2007 T. Player Category: Informational T. Player
Spirent Communications Spirent Communications
December 31, 2006
Hash and Stuffing: Overlooked Factors in Network Device Benchmarking Hash and Stuffing: Overlooked Factors in Network Device Benchmarking
draft-ietf-bmwg-hash-stuffing-08.txt
Status of this Memo
By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months Status of This Memo
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on July 4, 2007. This memo provides information for the Internet community. It does
not specify an Internet standard of any kind. Distribution of this
memo is unlimited.
Copyright Notice Copyright Notice
Copyright (C) The IETF Trust (2006). Copyright (C) The IETF Trust (2007).
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
overlooks two factors that have a profound impact on test results. overlooks two factors that have a profound impact on test results.
First, existing methodologies do not require the reporting of First, existing methodologies do not require the reporting of
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 . . . . . . . . . . . . . . . . . . . . . . . . . 4 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Requirements . . . . . . . . . . . . . . . . . . . . . . . . . 5 2. Requirements . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. General considerations . . . . . . . . . . . . . . . . . . . . 6 3. General Considerations . . . . . . . . . . . . . . . . . . . . 4
3.1. Repeatability . . . . . . . . . . . . . . . . . . . . . . 6 3.1. Repeatability . . . . . . . . . . . . . . . . . . . . . . 4
3.2. Randomness . . . . . . . . . . . . . . . . . . . . . . . . 6 3.2. Randomness . . . . . . . . . . . . . . . . . . . . . . . . 4
4. Packet Content Variations . . . . . . . . . . . . . . . . . . 8 4. Packet Content Variations . . . . . . . . . . . . . . . . . . 5
4.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 8 4.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 5
4.2. IEEE 802 MAC Addresses . . . . . . . . . . . . . . . . . . 9 4.2. IEEE 802 MAC Addresses . . . . . . . . . . . . . . . . . . 7
4.2.1. Randomized Sets of MAC Addresses . . . . . . . . . . . 11 4.2.1. Randomized Sets of MAC Addresses . . . . . . . . . . . 8
4.3. MPLS Addressing . . . . . . . . . . . . . . . . . . . . . 12 4.3. MPLS Addressing . . . . . . . . . . . . . . . . . . . . . 9
4.4. Network-layer Addressing . . . . . . . . . . . . . . . . . 12 4.4. Network-layer Addressing . . . . . . . . . . . . . . . . . 9
4.5. Transport-layer Addressing . . . . . . . . . . . . . . . . 13 4.5. Transport-Layer Addressing . . . . . . . . . . . . . . . . 10
4.6. Application-layer Patterns . . . . . . . . . . . . . . . . 13 4.6. Application-Layer Patterns . . . . . . . . . . . . . . . . 10
5. Control Character Stuffing . . . . . . . . . . . . . . . . . . 15 5. Control Character Stuffing . . . . . . . . . . . . . . . . . . 11
5.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 15 5.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 11
5.2. PPP Bit Stuffing . . . . . . . . . . . . . . . . . . . . . 15 5.2. PPP Bit-Stuffing . . . . . . . . . . . . . . . . . . . . . 12
5.2.1. Calculating Bit-Stuffing Probability . . . . . . . . . 18 5.2.1. Calculating Bit-Stuffing Probability . . . . . . . . . 14
5.2.2. Bit Stuffing for Finite Strings . . . . . . . . . . . 20 5.2.2. Bit-Stuffing for Finite Strings . . . . . . . . . . . 15
5.2.3. Applied Bit Stuffing . . . . . . . . . . . . . . . . . 20 5.2.3. Applied Bit-Stuffing . . . . . . . . . . . . . . . . . 16
5.3. POS Byte Stuffing . . . . . . . . . . . . . . . . . . . . 21 5.3. POS Byte-Stuffing . . . . . . . . . . . . . . . . . . . . 16
5.3.1. Nullifying ACCM . . . . . . . . . . . . . . . . . . . 21 5.3.1. Nullifying ACCM . . . . . . . . . . . . . . . . . . . 17
5.3.2. Other Stuffed Characters . . . . . . . . . . . . . . . 21 5.3.2. Other Stuffed Characters . . . . . . . . . . . . . . . 17
5.3.3. Applied Byte Stuffing . . . . . . . . . . . . . . . . 22 5.3.3. Applied Byte-Stuffing . . . . . . . . . . . . . . . . 17
6. Security Considerations . . . . . . . . . . . . . . . . . . . 23 6. Security Considerations . . . . . . . . . . . . . . . . . . . 18
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24 7. Normative References . . . . . . . . . . . . . . . . . . . . . 19
8. Normative References . . . . . . . . . . . . . . . . . . . . . 25 Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 20
Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 26 Appendix B. Proof of Formula for Finite Bit-Stuffing . . . . . . 20
Appendix B. Proof of Formula for Finite Bit Stuffing . . . . . . 27 Appendix C. Explicit Calculation of Bit-Stuffing Overhead for
Appendix C. Explicit Calculation of Bit Stuffing Overhead for IPv4 . . . . . . . . . . . . . . . . . . . . . . . . 21
IPv4 . . . . . . . . . . . . . . . . . . . . . . . . 28 Appendix D. Explicit Calculation of Bit-Stuffing Overhead for
Appendix D. Explicit Calculation of Bit Stuffing Overhead for IPv6 . . . . . . . . . . . . . . . . . . . . . . . . 23
IPv6 . . . . . . . . . . . . . . . . . . . . . . . . 30 Appendix E. Terminology . . . . . . . . . . . . . . . . . . . . . 24
Appendix E. Terminology . . . . . . . . . . . . . . . . . . . . . 32
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 33
Intellectual Property and Copyright Statements . . . . . . . . . . 34
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 High-Level Data Link Control (HDLC)-like
to ensure sequences in test traffic will not be confused with control framing. This stuffing is done to ensure sequences in test traffic
characters. will not be confused with control 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 point-to-point protocol (PPP) and packet over Sonet (POS) stuffing on Point-to-Point Protocol (PPP) and Packet over SONET (POS)
circuits. In both areas, we provide recommendations for obtaining circuits. In both areas, we provide recommendations for obtaining
better repeatability in test results. better repeatability in test results.
Benchmarking activities as described in this memo are limited to Benchmarking activities as described in this memo are limited to
technology characterization using controlled stimuli in a laboratory technology characterization using controlled stimuli in a laboratory
environment, using dedicated address space. environment, using dedicated address space.
The benchmarking network topology will be an independent test setup The benchmarking network topology will be an independent test setup
and MUST NOT be connected to devices that may forward the test and MUST NOT be connected to devices that may forward the test
traffic into a production network, or misroute traffic to the test traffic into a production network, or misroute traffic to the test
management network. management network.
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 recreated provided the device under test and test can always be recreated 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 common phenomena. other common phenomena.
skipping to change at page 8, line 12 skipping to change at page 5, line 16
of generating that specific pattern SHOULD equal 1 over 2 to the Lth of generating that specific pattern SHOULD equal 1 over 2 to the Lth
power. power.
4. Packet Content Variations 4. Packet Content Variations
4.1. Problem Statement 4.1. Problem Statement
The contents of test traffic can have a significant impact on metrics The contents of test traffic can have a significant impact on metrics
such as throughput, jitter, latency, and loss. For example, many such as throughput, jitter, latency, and loss. For example, many
network devices feed addresses into a hashing algorithm to determine network devices feed addresses into a hashing algorithm to determine
which path upon which to forward a given packet. upon which path to forward a given packet.
Consider the simple case of an Ethernet switch with eight network Consider the simple case of an Ethernet switch with eight network
processors (NPs) in its switching fabric: processors (NPs) in its switching fabric:
ingress ingress
|| ||
\/ \/
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ___ ___ ___ ___ ___ ___ ___ ___ | | ___ ___ ___ ___ ___ ___ ___ ___ |
|| | | | | | | | | | | | | | | | | || | | | | | | | | | | | | | | | |
skipping to change at page 9, line 42 skipping to change at page 6, line 48
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 capacity. 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 Benchmarking Working Group (BMWG). IETF Benchmarking Working Group (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
of non-randomness regardless of the hashing algorithms in use. The nonrandomness, 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. IEEE 802 MAC Addresses 4.2. IEEE 802 MAC Addresses
Test traffic SHOULD use pseudorandom patterns in IEEE 802 MAC Test traffic SHOULD use pseudorandom patterns in IEEE 802 MAC
addresses. The following source and destination MAC address pattern addresses. The following source and destination MAC address pattern
is RECOMMENDED: is RECOMMENDED:
(RR & 0xFC):PP:PP:RR:RR:RR (RR & 0xFC):PP:PP:RR:RR:RR
where (RR & 0xFC) is a pseudorandom number bitwise ANDed with 0xFC, 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
0xFC sets the low-order two bits of that byte to 0, guaranteeing a 0xFC sets the low-order two bits of that byte to 0, guaranteeing a
non multicast address and a non locally administered address. Note non-multicast address and a non locally administered address. Note
that the resulting addresses may violate IEEE 802 standards by using that the resulting addresses may violate IEEE 802 standards by using
organizationally unique identifiers (OUIs) not assigned to the test organizationally unique identifiers (OUIs) not assigned to the test
port manufacturer. However, since these addresses will be used only port manufacturer. However, since these addresses will be used only
on isolated test networks there should be no possibility of mistaken on isolated test networks there should be no possibility of mistaken
identity. identity.
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
skipping to change at page 10, line 38 skipping to change at page 7, line 43
Note that the "PP:PP" designation refers to the source interface of Note that the "PP:PP" designation refers to the source interface of
the test instrument, not the device under test/system under test the test instrument, not the device under test/system under test
(DUT/SUT). There are situations where the DUT/SUT interface number (DUT/SUT). There are situations where the DUT/SUT interface number
may change during the test; one example would be a test of wireless may change during the test; one example would be a test of wireless
LAN roaming. By referring to the (presumably static) source LAN roaming. By referring to the (presumably static) source
interface number of the test instrument, test engineers can keep interface number of the test instrument, test engineers can keep
track of test traffic regardless of any possible DUT/SUT changes. track of test traffic regardless of any possible DUT/SUT changes.
Further, source interface numbers SHOULD be 1-indexed and SHOULD NOT Further, source interface numbers SHOULD be 1-indexed and SHOULD NOT
be 0-indexed. This avoids the low but nonzero probability of an be zero-indexed. This avoids the low but nonzero probability of an
all-0s MAC address. Some devices will drop frames with all-0s MAC all-zeros MAC address. Some devices will drop frames with all-zeros
addresses. MAC 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 30 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
incrementing and/or decrementing addresses from a fixed starting incrementing and/or decrementing addresses from a fixed starting
point. This leads to situations as described above in "Address point. This leads to situations, as described above in "Address
Pattern Variations" where hashing algorithms produce nonoptimal Pattern Variations", where hashing algorithms produce nonoptimal
outcomes. outcomes.
The outcome can be nonoptimal even if the set of addresses begins The outcome can be nonoptimal even if the set of addresses begins
with a pseudorandom number. For example, the following source/ with a pseudorandom number. For example, the following source/
destination pairs will not be equally distributed by the 3-bit destination pairs will not be equally distributed by the 3-bit
hashing algorithm discussed above: hashing algorithm discussed above:
Source Destination Source Destination
00:00:01:FC:B3:45 00:00:19:38:8C:80 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:46 00:00:19:38:8C:81
skipping to change at page 12, line 28 skipping to change at page 9, line 28
IP addresses are used from trial to trial. In such cases (not just 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), 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, 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 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 either case, the same MAC and IP addresses MUST be used in all
trials. trials.
4.3. MPLS Addressing 4.3. MPLS Addressing
Similar to L2 switches, multiprotocol label switching (MPLS) devices Similar to L2 switches, multiprotocol label switching (MPLS) devices
make forwarding decisions based on a 20 bit MPLS label. Unless make forwarding decisions based on a 20-bit MPLS label. Unless
specific labels are required, it is RECOMMENDED that uniformly random specific labels are required, it is RECOMMENDED that uniformly random
values between 16 and 1,048,575 be used for all labels assigned by values between 16 and 1,048,575 be used for all labels assigned by
test equipment. As per [RFC3032], this avoids using reserved MPLS test equipment. As per [RFC3032], this avoids using reserved MPLS
labels in the range of 0-15 inclusive. labels in the range of 0-15 inclusive.
4.4. Network-layer Addressing 4.4. Network-layer Addressing
When routers make forwarding decisions based solely on destination When routers make forwarding decisions based solely on the
network address, there may be no potential for hashing collision of destination network address, there may be no potential for hashing
source and destination addresses, as in the case of Ethernet collision of source and destination addresses, as in the case of
switching discussed earlier. However, the potential still exists for Ethernet switching discussed earlier. However, the potential still
hashing collisions to exist at the network layer, and testers SHOULD exists for hashing collisions at the network layer, and testers
take this potential into consideration when crafting the network- SHOULD take this potential into consideration when crafting the
layer contents of test traffic. network-layer contents of test traffic.
For example, the equal cost multipath (ECMP) feature performs load- For example, the equal cost multipath (ECMP) feature performs load-
sharing across multiple links. Routers implementing ECMP may perform sharing across multiple links. Routers implementing ECMP may perform
a hash of source and destination IP addresses in assigning flows. a hash of source and destination IP addresses in assigning flows.
Since multiple ECMP routes by definition have the same metric, Since multiple ECMP routes by definition have the same metric,
routers use some other "tiebreaker" mechanism to assign traffic to routers use some other "tie-breaker" mechanism to assign traffic to
each link. As far as the authors are aware, there is no standard each link. As far as the authors are aware, there is no standard
algorithm for ECMP link assignment. Some implementations perform a algorithm for ECMP link assignment. Some implementations perform a
hash of all bits of the source and destination IP addresses for this 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 purpose. Others may perform a hash on one or more bytes in the
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 IPv4 network addresses that take the form x.x.1.x/24, when offered IPv4 network addresses that take the form x.x.1.x/24,
and relatively low packet loss when the source and destination 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 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. 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 pseudorandom and required for a test, it is RECOMMENDED to use pseudorandom and
skipping to change at page 13, line 46 skipping to change at page 10, line 46
use of reserved destination port numbers between 1 and 49151 use of reserved destination port numbers between 1 and 49151
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
required, it is RECOMMENDED to pick randomly distributed source port required, it is RECOMMENDED to pick randomly distributed source port
numbers between these lower and upper boundaries. numbers between these lower and upper boundaries.
4.6. Application-layer Patterns 4.6. Application-Layer Patterns
Many measurements require the insertion of application-layer Many measurements require the insertion of application-layer
header(s) and payload into test traffic. Application-layer packet header(s) and payload into test traffic. Application-layer packet
contents offer additional opportunities for stuffing to occur, and contents offer additional opportunities for stuffing to occur, and
may also present nonrandom outcomes when fed through application may also present nonrandom outcomes when fed through application-
layer-aware hashing algorithms. Given the vast number of layer-aware hashing algorithms. Given the vast number of
application-layer protocols in use, we make no recommendation for application-layer protocols in use, we make no recommendation for
specific test traffic patterns to be used; however, test engineers specific test traffic patterns to be used; however, test engineers
SHOULD be aware that application-layer traffic contents MAY produce SHOULD be aware that application-layer traffic contents MAY produce
nonrandom outcomes with some hashing algorithms. The same issues nonrandom outcomes with some hashing algorithms. The same issues
that apply with lower-layer traffic patterns also apply at the that apply with lower-layer traffic patterns also apply at the
application layer. As discussed in section 5, the potential for application layer. As discussed in section 5, the potential for
stuffing exists with any part of a test packet, including stuffing exists with any part of a test packet, including
application-layer contents. For example, some traffic generators application-layer contents. For example, some traffic generators
insert fields into packet payloads to distinguish test traffic. insert fields into packet payloads to distinguish test traffic.
These fields may contain a transmission timestamp; sequence number; These fields may contain a transmission timestamp; sequence number;
test equipment interface identifier and/or "stream" number; and a CRC test equipment interface identifier and/or "stream" number; and a
over the contents of the test payload or test packet. All these cyclic redundancy check (CRC) over the contents of the test payload
fields are potential candidates for stuffing. or test packet. All these fields are potential candidates for
stuffing.
5. Control Character Stuffing 5. Control Character Stuffing
5.1. Problem Statement 5.1. Problem Statement
Link-layer technologies that use high-level data link control (HDLC)- Link-layer technologies that use High-Level Data Link Control (HDLC)-
like framing may insert an extra bit or byte before each instance of like framing may insert an extra bit or byte before each instance of
a control character in traffic. These "stuffing" insertions prevent a control character in traffic. These "stuffing" insertions prevent
confusion with control characters, but they may also introduce confusion with control characters, but they may also introduce
significant overhead. Stuffing is data-dependent; thus selection of significant overhead. Stuffing is data-dependent; thus, selection of
different payload patterns will result in frames transmitted on the different payload patterns will result in frames transmitted on the
media that vary in length, even though the original frames may all be media that vary in length, even though the original frames may all be
of the same length. of the same length.
The overhead of these escape sequences is problematic for two The overhead of these escape sequences is problematic for two
reasons. First, explicitly calculating the amount of overhead can be reasons. First, explicitly calculating the amount of overhead can be
non-trivial or even impossible for certain types of test traffic. In non-trivial or even impossible for certain types of test traffic. In
such cases, the best testers can do is to characterize the such cases, the best testers can do is to characterize the
probability that an escape sequence will occur for a given pattern. probability that an escape sequence will occur for a given pattern.
This greatly complicates the requirement of declaring exactly how This greatly complicates the requirement of declaring exactly how
skipping to change at page 15, line 37 skipping to change at page 12, line 6
overhead, the tester may unwittingly congest the DUT/SUT. For overhead, the tester may unwittingly congest the DUT/SUT. For
example, if a tester intends to offer traffic to a DUT at 95 percent example, if a tester intends to offer traffic to a DUT at 95 percent
of line rate, but the link-layer protocol introduces an additional 1 of line rate, but the link-layer protocol introduces an additional 1
percent of overhead to escape control characters, then the aggregate percent of overhead to escape control characters, then the aggregate
offered load will be 96 percent of line rate. If the DUT's actual 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 channel capacity is only 95 percent, congestion will occur and the
DUT will drop traffic even though the tester did not intend this DUT will drop traffic even though the tester did not intend this
outcome. outcome.
As described in [RFC1661] and [RFC1662], PPP and HDLC-like framing As described in [RFC1661] and [RFC1662], PPP and HDLC-like framing
introduce two kinds of escape sequences: bit and byte stuffing. Bit introduce two kinds of escape sequences: bit- and byte-stuffing.
stuffing refers to the insertion of an escape bit on bit-synchronous Bit-stuffing refers to the insertion of an escape bit on bit-
links. Byte stuffing refers to the insertion of an escape byte on synchronous links. Byte-stuffing refers to the insertion of an
byte-synchronous links. We discuss each in turn. escape byte on byte-synchronous links. We discuss each in turn.
5.2. PPP Bit Stuffing 5.2. PPP Bit-Stuffing
[RFC1662], section 5.2 specifies that any sequence of five contiguous [RFC1662], section 5.2, specifies that any sequence of five
"1" bits within a frame must be escaped by inserting a "0" bit prior contiguous "1" bits within a frame must be escaped by inserting a "0"
to the sequence. This escaping is necessary to avoid confusion with bit prior to the sequence. This escaping is necessary to avoid
the HDLC control character 0x7E, which contains six "1" bits. confusion with the HDLC control character 0x7E, which contains six
"1" bits.
Consider the following PPP frame containing a TCP/IP packet. Not Consider the following PPP frame containing a TCP/IP packet. Not
shown is the 1-byte flag sequence (0x7E), at least one of which must shown is the 1-byte flag sequence (0x7E), at least one of which must
occur between frames. occur between frames.
The contents of the various frame fields can be described one of The contents of the various frame fields can be described one of
three ways: three ways:
1. Field contents never change over the test duration. An example 1. Field contents never change over the test duration. An example
would be the IP version number. would be the IP version number.
skipping to change at page 18, line 14 skipping to change at page 14, line 13
calculating stuff probability. calculating stuff probability.
Given the information at hand, and assuming static contents for the Given the information at hand, and assuming static contents for the
rest of the fields, the challenge is to determine the probability rest of the fields, the challenge is to determine the probability
that bit-stuffing will occur. that bit-stuffing will occur.
5.2.1. Calculating Bit-Stuffing Probability 5.2.1. Calculating Bit-Stuffing Probability
In order to calculate bit-stuffing probabilities, we assume that for In order to calculate bit-stuffing probabilities, we assume that for
any string of length L, where b_n represents the "n"th bit of the 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 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 and the probability of b_n equalling "0" is 0.5. Additionally, the
value of b_n is independent of any other bits. 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 bit-stuffing for both infinite
and finite strings of random bits. We begin with the infinite-string and finite strings of random bits. We begin with the infinite-string
case. For an infinitely long string of uniformly random bits, we 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 will need to insert a stuff bit if and only if state 5 is reached in
the following state table. the following state table.
|--------------------<----------------------| |--------------------<----------------------|
skipping to change at page 18, line 37 skipping to change at page 14, line 36
| | 1 | | 1 | | 1 | | 1 | | 1 | | | | 1 | | 1 | | 1 | | 1 | | 1 | |
| start |--->| 1 |--->| 2 |--->| 3 |--->| 4 |--->| 5 | | start |--->| 1 |--->| 2 |--->| 3 |--->| 4 |--->| 5 |
|_______| |_____| |_____| |_____| |_____| |_____| |_______| |_____| |_____| |_____| |_____| |_____|
| | | | | | | | | | | | | |
| |0 |0 |0 |0 |0 |0 | |0 |0 |0 |0 |0 |0
|-<-|----<----|----<-----|----<-----|----<-----|----<-----| |-<-|----<----|----<-----|----<-----|----<-----|----<-----|
Initially, we begin in the "start" state. A "1" bit moves us into 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. 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 From state 5, a "1" bit takes us back to the 1 state and a "0" bit
returns us to "start." returns us to "start".
From this state diagram we can build the following transition matrix: From this state diagram we can build the following transition matrix:
\ To | \ To |
\ | \ |
\ | \ |
From \ | start 1 2 3 4 5 From \ | start 1 2 3 4 5
______\|_________________________________________________ ______\|_________________________________________________
start | 0.5 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0 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 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 2 | 0.5 | 0.0 | 0.0 | 0.5 | 0.0 | 0.0
skipping to change at page 20, line 5 skipping to change at page 15, line 32
P(1) = 8/31 P(1) = 8/31
P(2) = 4/31 P(2) = 4/31
P(3) = 2/31 P(3) = 2/31
P(4) = 1/31 P(4) = 1/31
P(5) = 1/62 P(5) = 1/62
Thus, for an infinitely long string of uniformly random bits, the Thus, for an infinitely long string of uniformly random bits, the
probability of any individual bit causing a transition to state 5, probability of any individual bit causing a transition to state 5,
and thus causing a stuff, is 1/62. and thus causing a stuff, is 1/62.
5.2.2. Bit Stuffing for Finite Strings 5.2.2. Bit-Stuffing for Finite Strings
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 B. 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.
Similarly, the probability that any particular bit is the cause of a Similarly, 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
L_n, where 5 <= n <= L, caused a stuff is f(L) / (L * 2^L). that L_n, where 5 <= n <= L, caused a stuff is f(L) / (L * 2^L).
5.2.3. Applied Bit Stuffing 5.2.3. Applied Bit-Stuffing
The amount of overhead attributable to bit-stuffing may be calculated The amount of overhead attributable to bit-stuffing may be calculated
explicitly as long as the expected number of stuff bits per frame, 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] is known. For long uniformly random bit-strings,
E[bit-stuffs] may be approximated by multiplying the length of the E[bit-stuffs] may be approximated by multiplying the length of the
string by 1/62. string by 1/62.
% overhead = E[bit-stuffs] / framesize (in bits) % overhead = E[bit-stuffs] / framesize (in bits)
Given that the overhead added by bit-stuffing is approximately 1 in Given that the overhead added by bit-stuffing is approximately 1 in
skipping to change at page 20, line 51 skipping to change at page 16, line 33
intended load by 1.6 percent to avoid introducing congestion when intended load by 1.6 percent to avoid introducing congestion when
testing devices using bit-synchronous interfaces (such as T1/E1, testing devices using bit-synchronous interfaces (such as T1/E1,
DS-3, and the like). DS-3, and the like).
The percentage given above is an approximation. For greatest The percentage given above is an approximation. For greatest
precision, the actual intended load SHOULD be explicitly calculated precision, the actual intended load SHOULD be explicitly calculated
from the test traffic. from the test traffic.
Note that the DUT/SUT may be able to forward intended loads higher Note that the DUT/SUT may be able to forward intended loads higher
than the calculated theoretical maximum rate without packet loss. than the calculated theoretical maximum rate without packet loss.
Such results are the result of queuing on the part of the DUT/SUT. This results from queuing on the part of the DUT/SUT. While a
While a device's throughput may be above this level, delay-related device's throughput may be above this level, delay-related
measurements may be affected. Accordingly, it is RECOMMENDED to measurements may be affected. Accordingly, it is RECOMMENDED to
reduce offered levels by the amount of bit-stuffing overhead when reduce offered levels by the amount of bit-stuffing overhead when
testing devices using bit-synchronous links. This recommendation testing devices using bit-synchronous links. This recommendation
applies for all measurements, including throughput. applies for all measurements, including throughput.
5.3. POS Byte Stuffing 5.3. POS Byte-Stuffing
[RFC1662] requires that "Each Flag Sequence, Control Escape octet, [RFC1662] requires that "Each Flag Sequence, Control Escape octet,
and any octet which is flagged in the sending Async-Control- and any octet which is flagged in the sending Async-Control-
Character-Map (ACCM), is replaced by a two octet sequence consisting Character-Map (ACCM), is replaced by a two octet sequence consisting
of the Control Escape octet followed by the original octet exclusive- of the Control Escape octet followed by the original octet exclusive-
or'd with hexadecimal 0x20." The practical effect of this is to or'd with hexadecimal 0x20". The practical effect of this is to
insert a stuff byte for instances of up to 34 characters: 0x7E, 0x7D, insert a stuff byte for instances of up to 34 characters: 0x7E, 0x7D,
or any of 32 ACCM values. or any of 32 ACCM values.
A common implementation of PPP in HDLC-like framing is in PPP over A common implementation of PPP in HDLC-like framing is in PPP over
Sonet/SDH (POS), as defined in [RFC2615]. SONET/SDH (POS), as defined in [RFC2615].
As with the bit-stuffing case, the requirement in characterizing POS As with the bit-stuffing case, the requirement in characterizing POS
test traffic is to determine the probability that byte-stuffing will test traffic is to determine the probability that byte-stuffing will
occur for a given sequence. This is much simpler to do than with occur for a given sequence. This is much simpler to do than with
bit-synchronous links, since there is no possibility of overlap bit-synchronous links, since there is no possibility of overlap
across byte boundaries. across byte boundaries.
5.3.1. Nullifying ACCM 5.3.1. Nullifying ACCM
Testers can greatly reduce the probability of byte-stuffing by Testers can greatly reduce the probability of byte-stuffing by
configuring link partners to negotiate an ACCM value of 0x00. It is configuring link partners to negotiate an ACCM value of 0x00. It is
RECOMMENDED that testers configure the test instrument(s) and DUT/SUT RECOMMENDED that testers configure the test instrument(s) and DUT/SUT
to negotiate an ACCM value of 0x00 unless specific ACCM values are to negotiate an ACCM value of 0x00 unless specific ACCM values are
required. required.
One instance where nonzero ACCM values are used is in the layer 2 One instance where nonzero ACCM values are used is in the Layer 2
tunneling protocol (L2TP), as defined in [RFC2661], section 4.4.6. Tunneling Protocol (L2TP), as defined in [RFC2661], section 4.4.6.
When the default ACCM values are used, the probability of stuffing When the default ACCM values are used, the probability of stuffing
for any given random byte is 34 in 256, or approximately 13.3 for any given random byte is 34 in 256, or approximately 13.3
percent. percent.
5.3.2. Other Stuffed Characters 5.3.2. Other Stuffed Characters
If an ACCM value of 0x00 is negotiated, the only characters subject If an ACCM value of 0x00 is negotiated, the only characters subject
to stuffing are the flag and control escape characters. Thus, we can to stuffing are the flag and control escape characters. Thus, we can
say that without ACCM the probability of stuffing for any given say that without ACCM the probability of stuffing for any given
random byte is 2 in 256, or approximately 0.8 percent. random byte is 2 in 256, or approximately 0.8 percent.
5.3.3. Applied Byte Stuffing 5.3.3. Applied Byte-Stuffing
The amount of overhead attributable to byte stuffing may be The amount of overhead attributable to byte-stuffing may be
calculated explicitly as long as the expected number of stuff bytes calculated explicitly as long as the expected number of stuff bytes
per frame, E[byte-stuffs], is known. For long uniformly random byte- per frame, E[byte-stuffs], is known. For long uniformly random byte-
strings, E[byte-stuffs] may be approximated by multiplying the length strings, E[byte-stuffs] may be approximated by multiplying the length
of the string by the probability that any single byte is a stuff of the string by the probability that any single byte is a stuff
byte. byte.
% 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
skipping to change at page 22, line 31 skipping to change at page 18, line 11
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 intended 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 explicitly greatest precision, the actual intended load SHOULD be explicitly
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. This results from queuing on the part of the DUT/SUT. While a
SUT. While a device's throughput may be above this level, delay- device's throughput may be above this level, delay-related
related measurements may be affected. Accordingly, it is RECOMMENDED measurements may be affected. Accordingly, it is RECOMMENDED to
to reduce offered levels by the amount of byte-stuffing overhead when 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. This usage requires a uniform distribution, but does not traffic. This usage requires a uniform distribution, but does not
have strict predictability requirements. Although it is not have strict predictability requirements. Although it is not
sufficient for security applications, the rand() function of many sufficient for security applications, the rand() function of many
programming languages may provide a uniform distribution that is programming languages may provide a uniform distribution that is
skipping to change at page 24, line 5 skipping to change at page 19, line 5
rand() may vary and provide different properties so test designers rand() may vary and provide different properties so test designers
SHOULD understand the distribution created by the underlying function SHOULD understand the distribution created by the underlying function
and how seeding the initial state affects its behavior. 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. Normative References
This document has no actions for IANA.
8. Normative References
[RFC1661] Simpson, W., "The Point-to-Point Protocol (PPP)", STD 51, [RFC1661] Simpson, W., "The Point-to-Point Protocol (PPP)", STD 51,
RFC 1661, July 1994. RFC 1661, July 1994.
[RFC1662] Simpson, W., "PPP in HDLC-like Framing", STD 51, RFC 1662, [RFC1662] Simpson, W., "PPP in HDLC-like Framing", STD 51, RFC 1662,
July 1994. July 1994.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119, March 1997.
skipping to change at page 27, line 5 skipping to change at page 20, line 13
Encoding", RFC 3032, January 2001. Encoding", RFC 3032, January 2001.
Appendix A. Acknowledgements Appendix A. Acknowledgements
The authors gratefully acknowledge reviews and contributions by Tom The authors gratefully acknowledge reviews and contributions by Tom
Alexander, Len Ciavattone, Robert Craig, John Dawson, Neil Carter, Alexander, Len Ciavattone, Robert Craig, John Dawson, Neil Carter,
Glenn Chagnot, Kevin Dubray, Diego Dugatkin, Rafael Francis, Paul Glenn Chagnot, Kevin Dubray, Diego Dugatkin, Rafael Francis, Paul
Hoffman, David Joyner, Al Morton, Joe Perches, Jerry Perser, Scott Hoffman, David Joyner, Al Morton, Joe Perches, Jerry Perser, Scott
Poretsky, Dan Romascanu, and Kris Rousey. Poretsky, Dan Romascanu, 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
explicitly count the total number of bit-stuffs in the set of all 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. 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.
Suppose L >= 5, then there are some number of strings that will cause Suppose L >= 5, then there is some number of strings that will cause
stuffing events. Let us count them. stuffing events. Let us count them.
We begin by counting the number of strings that will cause at least 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, 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 cause a stuffing event. Then, there are (L-5) bits that could have
any value, i.e. the bits in position b_6 to b_L. So, there must be any value, i.e., the bits in position b_6 to b_L. So, there must be
2^(L-5) strings where the first 5 bits cause a stuff. 2^(L-5) strings where the first 5 bits cause a stuff.
Now suppose that some other sequence of bits cause a stuff, b_n to 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 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 a stuff sequence, b_(n-1) must be 0, otherwise a stuff could occur at
b_(n+3). Thus, there are a total of 6 bits which must have fixed b_(n+3). Thus, there are a total of 6 bits which must have fixed
values in the string, S, and a total of L-6 bits which do not have values in the string, S, and a total of L-6 bits which do not have
fixed values. Hence, for each value of n, there are 2^(L-6) possible 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) 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 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 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 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 than one bit-stuff within the string S. Let Z represent a sequence
5 sequential ones bits. Consider the bit string ..., b_n, b_(n+1), 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 b_(n+2), Z, b_(n+8), b_(n+9), ... where 1 <= n <= L-9. For the above
sequence of bits to generate two stuffing events, there must be at 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 sequence is irrelevant when looking for bit-stuffs. above sequence 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 for IPv4 Appendix C. Explicit Calculation of Bit-Stuffing Overhead for IPv4
Consider a scenario where a tester is transmitting IPv4 test packets Consider a scenario where a tester is transmitting IPv4 test packets
across 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 |
| | |
| Type of service (TOS) | 0 | | Type of service (TOS) | 0 |
| | |
| Datagram Length | 1028 | | Datagram Length | 1028 |
| | |
| ID | 0 | | ID | 0 |
| | |
| Flags/Fragments | 0 | | Flags/Fragments | 0 |
| | |
| Time to live (TTL) | 64 | | Time to live (TTL) | 64 |
| | |
| Protocol | 17 | | Protocol | 17 |
| | |
| Source IP | 192.18.13.1-192.18.13.254 | | Source IP | 192.18.13.1-192.18.13.254 |
| | |
| Destination IP | 192.18.1.10 | | Destination IP | 192.18.1.10 |
| | |
| Source UDP Port | pseudorandom port | | Source UDP Port | pseudorandom port |
| | |
| Destination UDP Port | pseudorandom port | | Destination UDP Port | pseudorandom port |
| | |
| UDP Length | 1008 | | UDP Length | 1008 |
| | |
| Payload | 1000 pseudorandom bytes | | Payload | 1000 pseudorandom bytes |
+-----------------------+---------------------------+ +-----------------------+---------------------------+
We want to calculate the expected number of stuffs per packet, or We want to calculate the expected number of stuffs per packet, or
E[packet stuffs]. E[packet stuffs].
First, we observe that we have 254 different IP headers to consider, First, we observe that we have 254 different IP headers to consider,
and secondly, that the changing 4th octet in the IP source addresses and secondly, that the changing 4th octet in the IP source addresses
will produce occasional bit-stuffing events, so we must enumerate will produce occasional bit-stuffing events, so we must enumerate
these occurrences. Additionally, we must take into account that the these occurrences. Additionally, we must take into account that the
3rd octet of the source IP and the first octet of the destination IP 3rd octet of the source IP and the first octet of the destination IP
will affect stuffing occurrences. will affect stuffing occurrences.
An exhaustive search shows that cycling through all 254 headers An exhaustive search shows that cycling through all 254 headers
produces 51 bit stuffs for the destination IP address. This gives us 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 an expectation of 51/254 stuffs per packet due to the changing source
IP address. IP address.
For the IP CRC, we observe that the value will decrement as the For the IP CRC, we observe that the value will decrement as the
source IP is incremented. A little calculation shows that the CRC source IP is incremented. A little calculation shows that the CRC
values for these headers will fall in the range of 0xE790 to 0xE88F. values for these headers will fall in the range of 0xE790 to 0xE88F.
Additionally, both the protocol and source IP address must be Additionally, both the protocol and source IP address must be
considered, as they provide a source of extra leading and trailing considered, as they provide a source of extra leading and trailing
ones bits. "1" bits.
An exhaustive search shows that cycling through all 254 headers will An exhaustive search shows that cycling through all 254 headers will
produce 102 bit stuffs for the CRC. This gives us an expectation of produce 102 bit-stuffs for the CRC. This gives us an expectation of
102/254 stuffs per packet due to the CRC. 102/254 stuffs per packet due to the CRC.
Since our destination IP address is even and the UDP length is less Since our destination IP address is even and the UDP length is less
than 32768, the random source and destination ports provide 32 bits than 32768, the random source and destination ports provide 32 bits
of sequential random data without forcing us to consider the boundary of sequential random data without forcing us to consider the boundary
bits. Additionally, we will assume that since our payload is bits. Additionally, we will assume that since our payload is
pseudorandom, our UDP CRC will be too. The even UDP length field pseudorandom, our UDP CRC will be too. The even UDP length field
again allows us to only consider the bits explicitly contained within again allows us to only consider the bits explicitly contained within
the CRC and data fields. So, using the formula for the expected 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 determine number of stuffs in a finite string from section 5.2.2, we determine
skipping to change at page 29, line 44 skipping to change at page 22, line 36
8016/62 ~ 129.755. 8016/62 ~ 129.755.
Hence, E[packet stuffs] = 51/254 + 102/254 + 129.755 = 130.357. Hence, E[packet stuffs] = 51/254 + 102/254 + 129.755 = 130.357.
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 Appendix D. Explicit Calculation of Bit-Stuffing Overhead for IPv6
Consider a scenario where a tester is transmitting IPv6 test packets Consider a scenario where a tester is transmitting IPv6 test packets
across 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 except for IPv6 addresses, which parameters (values are in decimal except for IPv6 addresses, which
are in hexadecimal): are in hexadecimal):
+----------------------+----------------------------------+ +----------------------+----------------------------------+
| Field | Value | | Field | Value |
+----------------------+----------------------------------+ +----------------------+----------------------------------+
| IP Version | 6 | | IP Version | 6 |
| | |
| Traffic Class | 0 | | Traffic Class | 0 |
| | |
| Flow Label | pseudorandom label | | Flow Label | pseudorandom label |
| | |
| Payload Length | 1008 | | Payload Length | 1008 |
| | |
| Next Header | 17 | | Next Header | 17 |
| | |
| Hop Limit | 64 | | Hop Limit | 64 |
| | |
| Source IP | 2001:DB8:0:1::1-2001:DB8:0:1::FF | | Source IP | 2001:DB8:0:1::1-2001:DB8:0:1::FF |
| | |
| Destination IP | 2001:DB8:0:2::10 | | Destination IP | 2001:DB8:0:2::10 |
| | |
| Source UDP Port | pseudorandom port | | Source UDP Port | pseudorandom port |
| | |
| Destination UDP Port | pseudorandom port | | Destination UDP Port | pseudorandom port |
| | |
| UDP Length | 1008 | | UDP Length | 1008 |
| | |
| Payload | 1000 pseudorandom bytes | | Payload | 1000 pseudorandom bytes |
+----------------------+----------------------------------+ +----------------------+----------------------------------+
We want to calculate the expected number of stuffs per packet, or We want to calculate the expected number of stuffs per packet, or
E[packet stuffs]. E[packet stuffs].
First, we observe that we have 255 different IP headers to consider, First, we observe that we have 255 different IP headers to consider,
and secondly, that the changing 4th quad in the IP source addresses and secondly, that the changing 4th quad in the IP source addresses
will produce occasional bit-stuffing events, so we must enumerate will produce occasional bit-stuffing events, so we must enumerate
these occurrences. Additionally, we also note that since the first these occurrences. Additionally, we also note that since the first
quad of the destination address has a leading zero bit, we do no have quad of the destination address has a leading zero bit, we do no have
to consider these adjacent bits when calculating the number of bit to consider these adjacent bits when calculating the number of bit-
stuffs in the source IP address. stuffs in the source IP address.
An exhaustive search shows that cycling through all 255 headers An exhaustive search shows that cycling through all 255 headers
produces 20 bit stuffs for the source IP address. This gives us an produces 20 bit-stuffs for the source IP address. This gives us an
expectation of 20/255 stuffs per packet due to the changing source IP expectation of 20/255 stuffs per packet due to the changing source IP
address. address.
We also have to consider our pseudorandomly generated flow label. We also have to consider our pseudorandomly generated flow label.
However, since our Traffic Class field is 0 and our Payload Length 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 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 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 random data. Thus the expectation of a stuff in the flow label is
f(20)/2^20 ~ .272. f(20)/2^20 ~ .272.
skipping to change at page 31, line 39 skipping to change at page 24, line 30
Now we may explicitly calculate that E[packet stuffs] = 20/255 + Now we may explicitly calculate that E[packet stuffs] = 20/255 +
0.272 + 129.755 = 130.105. However, since we cannot have a 0.272 + 129.755 = 130.105. However, since we cannot have a
fractional stuff, we round down to 130. Thus, we expect 130 stuffs fractional stuff, we round down to 130. Thus, we expect 130 stuffs
per packet. 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.55% overhead. datagram. So, this example traffic would generate 1.55% 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.010%. An all ones payload would produce 19.09% would have been 0.010%. An all-ones payload would produce 19.09%
overhead. overhead.
Appendix E. Terminology Appendix E. Terminology
Hashing Hashing
Also known as a hash function. In the context of this document, an Also known as a hash function. In the context of this document, an
algorithm for transforming data for use in path selection by a algorithm for transforming data for use in path selection by a
networking device. For example, an Ethernet switch with multiple networking device. For example, an Ethernet switch with multiple
processing elements might use the source and destination MAC processing elements might use the source and destination MAC
skipping to change at page 32, line 27 skipping to change at page 25, line 8
Randomness Randomness
In the context of this document, the quality of having an equal In the context of this document, the quality of having an equal
probability of any possible outcome for a given pattern space. For probability of any possible outcome for a given pattern space. For
example, if an experiment has N randomly distributed outcomes, then example, if an experiment has N randomly distributed outcomes, then
any individual outcome has a 1 in N probability of occurrence. any individual outcome has a 1 in N probability of occurrence.
Repeatability Repeatability
The precision of test results obtained on a single test bed, but from The precision of test results obtained on a single test bed, but from
trial to trial. See also "reproducibility." trial to trial. See also "reproducibility".
Reproducibility Reproducibility
The precision of test results between different setups, possibly at The precision of test results between different setups, possibly at
different locations. See also "repeatability." different locations. See also "repeatability".
Stuffing Stuffing
The insertion of a bit or byte within a frame to avoid confusion with The insertion of a bit or byte within a frame to avoid confusion with
control characters. For example, RFC 1662 requires the insertion of control characters. For example, RFC 1662 requires the insertion of
a 0 bit prior to any sequence of five contiguous 1 bits within a a "0" bit prior to any sequence of five contiguous "1" bits within a
frame to avoid confusion with the HDLC control character 0x7E. frame to avoid confusion with the HDLC control character 0x7E.
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@spirent.com EMail: timmons.player@spirent.com
Full Copyright Statement Full Copyright Statement
Copyright (C) The IETF Trust (2006). Copyright (C) The IETF Trust (2007).
This document is subject to the rights, licenses and restrictions This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors contained in BCP 78, and except as set forth therein, the authors
retain all their rights. retain all their rights.
This document and the information contained herein are provided on an This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
skipping to change at page 34, line 45 skipping to change at page 26, 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.
Acknowledgment Acknowledgement
Funding for the RFC Editor function is provided by the IETF Funding for the RFC Editor function is currently provided by the
Administrative Support Activity (IASA). Internet Society.
 End of changes. 90 change blocks. 
176 lines changed or deleted 127 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/