draft-ietf-bmwg-hash-stuffing-00.txt   draft-ietf-bmwg-hash-stuffing-01.txt 
Network Working Group D. Newman Network Working Group D. Newman
Internet-Draft Network Test Internet-Draft Network Test
Expires: January 8, 2005 T. Player Expires: April 21, 2005 T. Player
Spirent Communications Spirent Communications
July 10, 2004 October 21, 2004
Hash and Stuffing: Overlooked Factors in Network Device Benchmarking Hash and Stuffing: Overlooked Factors in Network Device Benchmarking
draft-ietf-bmwg-hash-stuffing-00.txt draft-ietf-bmwg-hash-stuffing-01.txt
Status of this Memo Status of this Memo
By submitting this Internet-Draft, I certify that any applicable This document is an Internet-Draft and is subject to all provisions
patent or other IPR claims of which I am aware have been disclosed, of section 3 of RFC 3667. By submitting this Internet-Draft, each
and any of which I become aware will be disclosed, in accordance with 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 become aware will be disclosed, in accordance with
RFC 3668. RFC 3668.
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
other groups may also distribute working documents as other groups may also distribute working documents as
Internet-Drafts. Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
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 January 8, 2005. This Internet-Draft will expire on April 21, 2005.
Copyright Notice Copyright Notice
Copyright (C) The Internet Society (2004). All Rights Reserved. Copyright (C) The Internet Society (2004).
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 offered load, packet length, test duration, measurement, including offered 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
skipping to change at page 2, line 20 skipping to change at page 2, line 22
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Requirements . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Requirements . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. General considerations . . . . . . . . . . . . . . . . . . . . 5 3. General considerations . . . . . . . . . . . . . . . . . . . . 5
3.1 Repeatability . . . . . . . . . . . . . . . . . . . . . . 5 3.1 Repeatability . . . . . . . . . . . . . . . . . . . . . . 5
3.2 Randomness . . . . . . . . . . . . . . . . . . . . . . . . 5 3.2 Randomness . . . . . . . . . . . . . . . . . . . . . . . . 5
4. Address Pattern Variations . . . . . . . . . . . . . . . . . . 6 4. Address Pattern Variations . . . . . . . . . . . . . . . . . . 6
4.1 Problem Statement . . . . . . . . . . . . . . . . . . . . 6 4.1 Problem Statement . . . . . . . . . . . . . . . . . . . . 6
4.2 Ethernet MAC Addresses . . . . . . . . . . . . . . . . . . 7 4.2 Ethernet MAC Addresses . . . . . . . . . . . . . . . . . . 7
4.2.1 Randomized Sets of MAC Addresses . . . . . . . . . . . 8 4.2.1 Randomized Sets of MAC Addresses . . . . . . . . . . . 8
4.3 Network-layer Addressing . . . . . . . . . . . . . . . . . 9 4.3 MPLS Addressing . . . . . . . . . . . . . . . . . . . . . 10
4.4 Transport-layer Addressing . . . . . . . . . . . . . . . . 10 4.4 Network-layer Addressing . . . . . . . . . . . . . . . . . 10
5. Control Character Stuffing . . . . . . . . . . . . . . . . . . 11 4.5 Transport-layer Addressing . . . . . . . . . . . . . . . . 10
5.1 Problem Statement . . . . . . . . . . . . . . . . . . . . 11 5. Control Character Stuffing . . . . . . . . . . . . . . . . . . 12
5.2 PPP Bit Stuffing . . . . . . . . . . . . . . . . . . . . . 11 5.1 Problem Statement . . . . . . . . . . . . . . . . . . . . 12
5.2.1 Calculating Bit-Stuffing Probability . . . . . . . . . 13 5.2 PPP Bit Stuffing . . . . . . . . . . . . . . . . . . . . . 12
5.2.2 Bit Stuffing for Finite Strings . . . . . . . . . . . 14 5.2.1 Calculating Bit-Stuffing Probability . . . . . . . . . 14
5.2.3 Applied Bit Stuffing . . . . . . . . . . . . . . . . . 14 5.2.2 Bit Stuffing for Finite Strings . . . . . . . . . . . 15
5.3 POS Byte Stuffing . . . . . . . . . . . . . . . . . . . . 15 5.2.3 Applied Bit Stuffing . . . . . . . . . . . . . . . . . 15
5.3.1 Nullifying ACCM . . . . . . . . . . . . . . . . . . . 15 5.3 POS Byte Stuffing . . . . . . . . . . . . . . . . . . . . 16
5.3.2 Other Stuffed Characters . . . . . . . . . . . . . . . 15 5.3.1 Nullifying ACCM . . . . . . . . . . . . . . . . . . . 16
5.3.3 Applied Byte Stuffing . . . . . . . . . . . . . . . . 15 5.3.2 Other Stuffed Characters . . . . . . . . . . . . . . . 17
6. Security Considerations . . . . . . . . . . . . . . . . . . . 17 5.3.3 Applied Byte Stuffing . . . . . . . . . . . . . . . . 17
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 6. Security Considerations . . . . . . . . . . . . . . . . . . . 18
8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19
8.1 Normative References . . . . . . . . . . . . . . . . . . . . 19 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20
8.2 Informative References . . . . . . . . . . . . . . . . . . . 19 8.1 Normative References . . . . . . . . . . . . . . . . . . . . 20
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 19 8.2 Informative References . . . . . . . . . . . . . . . . . . . 20
A. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 20 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 20
Intellectual Property and Copyright Statements . . . . . . . . 21 A. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 22
Intellectual Property and Copyright Statements . . . . . . . . 23
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
skipping to change at page 5, line 27 skipping to change at page 5, line 27
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 it is important to recognize such variation exists. Exact
bit-for-bit reproduction of test traffic in all cases is a hard bit-for-bit reproduction of test traffic in all cases is a hard
problem. A simpler approach is to acknowledge that some variation problem. A simpler approach is to acknowledge that some variation
exists, characterize that variation, and describe it when analyzing exists, characterize that variation, and describe it when analyzing
test results. test 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 of traffic under controlled lab conditions. The rand() functions
many programming languages produce output that is pseudorandom rather available in many programming languages produce output that is
than truly random. Pseudorandom patterns are sufficient for the pseudorandom rather than truly random. Pseudorandom patterns are
recommendations given in this document, provided they produce an even sufficient for the recommendations given in this document, provided
distribution of outcomes from the hashing algorithm of the device or they produce output that is uniformly distributed across the pattern
system under test. space.
Specifically, for any random bit pattern of length L, the probability
of generating that specific pattern SHOULD equal 1 over 2 to the Lth
power.
4. Address Pattern Variations 4. Address Pattern Variations
4.1 Problem Statement 4.1 Problem Statement
The addresses and port numbers used in a test can have a significant The addresses and port numbers used in a test can have a significant
impact on metrics such as throughput, jitter, latency, and loss. impact on metrics such as throughput, jitter, latency, and loss.
This is because many network devices feed such addresses into hashing This is because many network devices feed such addresses into hashing
algorithms to determine which path upon which to forward a given algorithms to determine which path upon which to forward a given
packet. packet.
skipping to change at page 6, line 39 skipping to change at page 6, line 39
\/ \/
egress egress
To assign incoming traffic to the various NPs, suppose a hashing To assign incoming traffic to the various NPs, suppose a hashing
algorithm performs an exclusive-or (XOR) operation on the least algorithm performs an exclusive-or (XOR) operation on the least
significant 3 bits of the source and destination MAC addresses in significant 3 bits of the source and destination MAC addresses in
each frame. (This is an actual example the authors have observed in each frame. (This is an actual example the authors have observed in
multiple devices from multiple manufacturers.) multiple devices from multiple manufacturers.)
In theory, a random distribution of source and destination MAC In theory, a random distribution of source and destination MAC
addresses should result in traffic being evenly distributed across addresses should result in traffic being uniformly distributed across
all eight NPs. In practice, the actual outcome of the hash (and thus all eight NPs. (Instances of the term "random" in this document
any test results) will be very different depending on the amount of refer to a random uniform distribution across a given address space.
randomness in test traffic. Section 3.2 describes random uniform distributions in more detail.)
In practice, the actual outcome of the hash (and thus any test
results) will be very different depending on the degree of randomness
in test traffic.
Suppose the traffic is nonrandom so that every interface of the test Suppose the traffic is nonrandom so that every interface of the test
instrument uses this pattern in its source MAC addresses: instrument uses this pattern in its source MAC addresses:
00:00:PP:00:00:01 00:00:PP:00:00:01
where PP is the source interface number of the test instrument. where PP is the source interface number of the test instrument.
In this case, the least significant 3 bits of every source and In this case, the least significant 3 bits of every source and
destination MAC address are 001, regardless of interface number. destination MAC address are 001, regardless of interface number.
Thus, the outcome of the XOR operation will always be 0, given the Thus, the outcome of the XOR operation will always be 0, given the
same three least significant bits: same three least significant bits:
001 ^ 001 = 000 001 ^ 001 = 000
Thus, the switch will assign all traffic to NP0, leaving the other Thus, the switch will assign all traffic to NP0, leaving the other
skipping to change at page 7, line 27 skipping to change at page 7, line 30
Now consider the same example with randomly distributed addresses. Now consider the same example with randomly distributed addresses.
In this case, the test instrument offers traffic using MAC addresses In this case, the test instrument offers traffic using MAC addresses
with this pattern: with this pattern:
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 evenly distributed from 0 to 7, and distribution operations should be equally distributed from 0 to 7, and
across NPs should also be even (at least for this particular 3-bit distribution across NPs should also be equal (at least for this
hashing algorithm). Absent other impediments, the device should be particular 3-bit hashing algorithm). Absent other impediments, the
able to utilize 100 percent of available bandwidth. device should be able to utilize 100 percent of available bandwidth.
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.
The balance of this section offers recommendations for test traffic The balance of this section offers recommendations for test traffic
patterns, starting at the link layer and working up to the transport patterns, starting at the link layer and working up to the transport
layer. These patterns should overcome the effects of nonrandomness layer. These patterns should overcome the effects of nonrandomness
regardless of the hashing algorithms in use. regardless of the hashing algorithms in use.
4.2 Ethernet MAC Addresses 4.2 Ethernet MAC 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:
00:PP:PP:RR:RR:RR (RR & 0xFE):PP:PP:RR:RR:RR
where (RR & 0xFE) is a pseudorandom number bitwise ANDed with 0xFE,
where PP:PP is the interface number of the test instrument and PP:PP is the interface number of the test instrument and RR:RR:RR is
RR:RR:RR is a pseudorandom number. a pseudorandom number.
It is NOT RECOMMENDED that testers randomize the high-order byte in The bitwise ANDing of the high-order byte in the MAC address with
the MAC address. If the high-order byte were randomized, there is a 0xFE guarantees a non multicast address.
low but nonzero probability of generating a frame with a MAC address
beginning 01:00:5E. That pattern is reserved for multicast use.
It is RECOMMENDED to use PP:PP to identify the source interface It is RECOMMENDED to use PP:PP to identify the source interface
number of the test instrument. Such identification can be useful in number 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.
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 greater currently required in lab benchmarking, it does assure more realistic
randomness in test traffic. test traffic.
Note also that since only 3 out of 6 bytes in the MAC address have Note also that since only 31 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 nonrandom Pattern Variations" where hashing algorithms produce nonoptimal
outcomes. outcomes.
The outcome can be nonrandom even if the set of addresses begins with The outcome can be nonoptimal even if the set of addresses begins
a pseudorandom number. For example, the following source/destination with a pseudorandom number. For example, the following
pairs will not be evenly distributed by the 3-bit hashing algorithm source/destination pairs will not be equally distributed by the 3-bit
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
00:00:01:FC:B3:47 00:00:19:38:8C:82 00:00:01:FC:B3:47 00:00:19:38:8C:82
00:00:01:FC:B3:48 00:00:19:38:8C:83 00:00:01:FC:B3:48 00:00:19:38:8C:83
00:00:01:FC:B3:49 00:00:19:38:8C:84 00:00:01:FC:B3:49 00:00:19:38:8C:84
00:00:01:FC:B3:50 00:00:19:38:8C:85 00:00:01:FC:B3:50 00:00:19:38:8C:85
00:00:01:FC:B3:51 00:00:19:38:8C:86 00:00:01:FC:B3:51 00:00:19:38:8C:86
00:00:01:FC:B3:52 00:00:19:38:8C:87 00:00:01:FC:B3:52 00:00:19:38:8C:87
skipping to change at page 9, line 32 skipping to change at page 9, line 44
incrementing addresses. This is actually the best case. incrementing addresses. This is actually the best case.
Incrementing from other combinations of pseudorandom address pairs Incrementing from other combinations of pseudorandom address pairs
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. rather than incrementing/decrementing from a starting address. The
Another method would be to increment/decrement using steps that are actual method is an implementation detail; in the end, any method
relatively prime to the hash table. The actual method is an that uses multiple addresses and avoids hash table collisions will be
implementation detail; in the end, any method that uses multiple sufficient.
addresses and avoids hash table collisions will be sufficient.
4.3 Network-layer Addressing 4.3 MPLS Addressing
Similiar to L2 switches, MPLS routers make forwarding decisions based
on a 20 bit MPLS label. Unless specific labels are required, it is
RECOMMENDED that uniformly random values between 0 and 1,048,575 be
used for all labels assigned by test equipment.
4.4 Network-layer Addressing
Routers make forwarding decisions based on destination network Routers make forwarding decisions based on destination network
address. Since there is no hashing of source and destination address. Since there is no hashing of source and destination
addresses, the requirement for pseudorandom patterns at the network addresses, the requirement for pseudorandom patterns at the network
layer is far less critical than in the Ethernet MAC address case. layer is far less critical than in the Ethernet MAC address case.
However, there are cases where randomly distributed IPv4 addresses However, there are cases where randomly distributed IPv4 addresses
are desirable. For example, the equal cost multipath (ECMP) feature are desirable. For example, the equal cost multipath (ECMP) feature
performs load-sharing across multiple links. Routers implementing performs load-sharing across multiple links. Routers implementing
ECMP may perform a hash of source and destination IP addresses in ECMP may perform a hash of source and destination IP addresses in
skipping to change at page 10, line 16 skipping to change at page 10, line 35
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 "tiebreaker" 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. purpose.
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, it is RECOMMENDED to When benchmarking devices that implement ECMP or any other form of
use IP addresses that will produce an even distribution across paths. Layer 3 aggregation, it is RECOMMENDED to use a randomly distributed
range of IP addresses.
4.4 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 destination port numbers are often required for testing
application-layer devices. However, unless known port numbers are application-layer devices. However, unless known port numbers are
specifically required for a test, it is RECOMMENDED to use specifically required for a test, it is RECOMMENDED to use randomly
pseudorandom values for both source and destination port numbers. 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 destination port numbers at random between these RECOMMENDED to pick randomly distributed destination port numbers
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 source port numbers at random required, it is RECOMMENDED to pick randomly distributed source port
between these lower and upper boundaries. numbers between these lower and upper boundaries.
5. Control Character Stuffing 5. Control Character Stuffing
5.1 Problem Statement 5.1 Problem Statement
Link-layer technologies that use HDLC-like framing may insert an Link-layer technologies that use HDLC-like framing may insert an
extra bit or byte before each instance of a control character in extra bit or byte before each instance of a control character in
traffic. These insertions prevent confusion with control characters, traffic. These insertions prevent confusion with control characters,
but they may also introduce significant overhead. but they may also introduce significant overhead.
skipping to change at page 12, line 48 skipping to change at page 13, line 48
| | |G|K|H|T|N|N| | | | |G|K|H|T|N|N| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ((Checksum)) | Urgent Pointer | | ((Checksum)) | Urgent Pointer |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ((FCS (4 bytes) )) | | ((FCS (4 bytes) )) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
None of the other fields are known to contain sequences subject to None of the other fields are known to contain sequences subject to
bit-stuffing, at least not in their entirety. bit-stuffing, at least not in their entirety.
However, some fields may contain one or more "1" bits adjacent to
fields that change. For example, if the low-order octet of the IP
destination address has a value of 1 this could place a "1" bit
adjacent to the source port, which is a variable.
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
any string of length L, the probability of the Lth + 1 bit equalling
1 is 0.5 and the probability of the Lth + 1 bit equalling 0 is 0.5.
Additionally, the value of the Lth + 1 bit is independant of any
previous bits.
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, which is required to prove the finite-string case. For an case, which is required to prove the finite-string case. For an
infinitely long string of random bits, we will need to insert a stuff infinitely long string of random bits, we will need to insert a stuff
bit if and only if state 5 is reached in the following state table. bit if and only if state 5 is reached in the following state table.
|--------------------<----------------------| |--------------------<----------------------|
| |1 | |1
_______ ___|__ ______ ______ ______ ___|__ _______ __|__ _____ _____ _____ __|__
| | 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 the Initially, we begin in the "start" state. A 1 bit moves us into the
next highest state, and a 0 bit returns us to the start state. From next highest state, and a 0 bit returns us to the start state. From
state 5, a 1 bit takes us back to the 1 state and a 0 bit returns us state 5, a 1 bit takes us back to the 1 state and a 0 bit returns us
to "start." From this state table we can build the following to "start." From this state table we can build the following
transition matrix: transition matrix:
| start 1 2 3 4 5 | 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.5 | 0.5 | 0.5 | 0.5
1 | 0.5 | 0.0 | 0.5 | 0.0 | 0.0 | 0.0 1 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0 | 0.5
2 | 0.5 | 0.0 | 0.0 | 0.5 | 0.0 | 0.0 2 | 0.0 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0
3 | 0.5 | 0.0 | 0.0 | 0.0 | 0.5 | 0.0 3 | 0.0 | 0.0 | 0.5 | 0.0 | 0.0 | 0.0
4 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0 | 0.5 4 | 0.0 | 0.0 | 0.0 | 0.5 | 0.0 | 0.0
5 | 0.5 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0 5 | 0.0 | 0.0 | 0.0 | 0.0 | 0.5 | 0.0
With this transition matrix we can build the following system of With this transition matrix we can build the following system of
equations. If P(x) represents the probability of reaching state x, equations. If P(x) represents the probability of reaching state x,
then: then:
P(start) = 0.5 * P(start) + 0.5 * P(1) + 0.5 * P(2) + 0.5 * P(3) + P(start) = 0.5 * P(start) + 0.5 * P(1) + 0.5 * P(2) + 0.5 * P(3) +
0.5 * P(4) + 0.5 * P(5) 0.5 * P(4) + 0.5 * P(5)
P(1) = 0.5 * P(start) + 0.5 * P(5) P(1) = 0.5 * P(start) + 0.5 * P(5)
P(2) = 0.5 * P(1) P(2) = 0.5 * P(1)
P(3) = 0.5 * P(2) P(3) = 0.5 * P(2)
skipping to change at page 14, line 29 skipping to change at page 15, line 24
Solving this system of equations yields: Solving this system of equations yields:
P(start) = 0.5 P(start) = 0.5
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 random bits, the probability Thus, for an infinitely long string of random bits, the probability
of 5 sequential 1 bits is 1 in 62. of 5 sequential 1 bits is 1/62. Put another way, we expect to add
one stuff bit for every 62 bits of random uniform data.
5.2.2 Bit Stuffing for Finite Strings 5.2.2 Bit Stuffing for Finite Strings
TBD The above result indicates that for any string of uniformly
distributed random bits, we expect a stuffing event to occur every 62
bits. So, given a string of some finite length L, where L >= 5, the
expected number of stuffs is simply L * 1/62.
5.2.3 Applied Bit Stuffing 5.2.3 Applied Bit Stuffing
Given that the overhead added by bit-stuffing is 1 in 62, or The amount of overhead attributable to bit stuffing may be calculated
explicitly as long as the total number of random bits per frame,
L_rand-bits, and the probability of stuffing, P(stuff), is known.
% overhead = ( P(stuff) * L_rand-bits ) / framesize (in bits)
Note that if the entire frame contains random bits, then the
percentage overhead is simply the probability of stuffing expressed
as a percentage.
Given that the overhead added by bit-stuffing is at most 1 in 62, or
approximately 1.6 percent, it is RECOMMENDED that testers reduce the approximately 1.6 percent, it is RECOMMENDED that testers reduce the
maximum offered load by 1.6 percent to avoid introducing congestion maximum offered load by 1.6 percent to avoid introducing congestion
when testing devices using bit-synchronous interfaces (such as T1/E1, when 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 offered load should be calculated using frames precision, the actual offered load should be calculated using the
per second rather than percentage of line rate as the unit of percentage overhead formula above and then expressed in frames per
measurement. second, rounded down to the nearest integer.
Note that the DUT/SUT may be able to forward offered loads higher Note that the DUT/SUT may be able to forward offered loads higher
than 98.4 percent without packet loss. Such results are the result than the calculated theoretical maximum without packet loss. Such
of queuing on the part of the DUT/SUT. While a device's throughput results are the result of queuing on the part of the DUT/SUT. While
may be above this level, delay-related measurements such as latency a device's throughput may be above this level, delay-related
or jitter may be affected. Accordingly, it is RECOMMENDED to reduce measurements such as latency or jitter may be affected. Accordingly,
offered levels by the amount of bit-stuffing overhead when testing it is RECOMMENDED to reduce offered levels by the amount of
devices using bit-synchronous links. This recommendation applies for bit-stuffing overhead when testing devices using bit-synchronous
all measurements, including throughput. links. This recommendation 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 and any octet which is flagged in the sending
Async-Control-Character-Map (ACCM), is replaced by a two octet Async-Control-Character-Map (ACCM), is replaced by a two octet
sequence consisting of the Control Escape octet followed by the sequence consisting of the Control Escape octet followed by the
original octet exclusive-or'd with hexadecimal 0x20." The practical original octet exclusive-or'd with hexadecimal 0x20." The practical
effect of this is to insert a stuff byte for instances of up to 34 effect of this is to insert a stuff byte for instances of up to 34
characters: 0x7E, 0x7D, or any of 32 ACCM values. characters: 0x7E, 0x7D, or any of 32 ACCM values.
skipping to change at page 15, line 38 skipping to change at page 17, line 4
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 ACCM values are defined, the probability of stuffing for any
given byte is 34 in 256, or approximately 13.3 percent. When the default ACCM values are used, the probability of stuffing
for any given random byte is 34 in 256, or approximately 13.3
percent.
5.3.2 Other Stuffed Characters 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 byte say that without ACCM the probability of stuffing for any given
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 bit or byte stuffing may be
calculated explicitly as long as the total number of random bytes per
frame, L_rand-bytes, and the probability of stuffing, P(stuff), is
known.
% overhead = ( P(stuff) * L_rand-bytes ) / framesize (in bytes)
Note that if the entire frame contains random bytes, then the
percentage overhead is simply the probability of stuffing expressed
as a percentage.
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 offered load by 13.3 RECOMMENDED that testers reduce the maximum offered 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 offered 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 offered load should be calculated greatest precision, the actual offered load should be calculated from
using frames per second rather than percentage of line rate as the the % overhead formula above and expressed in frames per second
unit of measurement. rather than percentage of line rate as the unit of measurement.
Note also that the DUT/SUT may be able to forward offered loads Note also that the DUT/SUT may be able to forward offered loads
higher than the percentages given above without packet loss. Such higher than the calculated theoretical maximum without packet loss.
results are the result of queuing on the part of the DUT/SUT. While Such results are the result of queuing on the part of the DUT/SUT.
a device's throughput may be above this level, delay-related While a device's throughput may be above this level, delay-related
measurements such as latency or jitter may be affected. Accordingly, measurements such as latency or jitter may be affected. Accordingly,
it is RECOMMENDED to reduce offered levels by the amount of it is RECOMMENDED to reduce offered levels by the amount of
byte-stuffing overhead when testing devices using byte-synchronous byte-stuffing overhead when testing devices using byte-synchronous
links. This recommendation applies for all measurements, including links. This recommendation applies for all measurements, including
throughput. 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. Testers should be aware that the rand() functions of many traffic. Testers should be aware that the rand() functions of many
programming languages produce output that is pseudorandom rather than programming languages produce output that is pseudorandom rather than
truly random. As far as the authors are aware, pseudorandom patterns truly random. As far as the authors are aware, pseudorandom patterns
are sufficient for generating test traffic in lab conditions. are sufficient for generating test traffic in lab conditions.
However, when testing devices that require truly random input (such
as devices using cryptographic functions), it is strongly RECOMMENDED
to use rand() functions that return truly random values.
[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 attackers or anyone else other than the SHOULD NOT be reachable by anyone other than the tester(s).
tester(s).
7. IANA Considerations 7. IANA Considerations
This document has no actions for IANA. This document has no actions for IANA.
8. References 8. References
8.1 Normative References 8.1 Normative References
[RFC1661] Simpson, W., "The Point-to-Point Protocol (PPP)", STD 51, [RFC1661] Simpson, W., "The Point-to-Point Protocol (PPP)", STD 51,
skipping to change at page 19, line 39 skipping to change at page 20, line 39
for LAN Switching Devices", RFC 2889, August 2000. for LAN Switching Devices", RFC 2889, August 2000.
8.2 Informative References 8.2 Informative References
[Ca63] Campbell, D. and J. Stanley, "Experimental and [Ca63] Campbell, D. and J. Stanley, "Experimental and
Quasi-Experimental Designs for Research", 1963. Quasi-Experimental Designs for Research", 1963.
[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
Edition", 1997.
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
Appendix A. Acknowledgements Appendix A. Acknowledgements
The authors gratefully acknowledge the contributions of Glenn The authors gratefully acknowledge reviews and contributions by Glenn
Chagnot, Rafael Francis, and David Joyner. Chagnot, Rafael Francis, Paul Hoffman, David Joyner, Joe Perches, and
Scott Poretsky.
Intellectual Property Statement Intellectual Property Statement
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
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/