draft-ietf-diffserv-ef-supplemental-01.txt   rfc3247.txt 
Network Working Group Anna Charny, Editor Network Working Group A. Charny
Internet Draft Fred Baker Request for Comments: 3247 Cisco Systems, Inc.
Expiration Date: December 2001 Bruce Davie Category: Informational J.C.R. Bennett
Cisco Systems, Inc. Motorola
Jon Bennet K. Benson
Riverdelta Networks Tellabs
J.Y. Le Boudec
Kent Benson Jean-Yves Le Boudec EPFL
Tellabs EPFL A. Chiu
Celion Networks
Angela Chiu William Courtney W. Courtney
AT&T Labs TRW TRW
S. Davari
Shahram Davari Victor Firoiu PMC-Sierra
PMC-Sierra Nortel Networks V. Firoiu
Nortel Networks
Charles Kalmanek K.K. Ramakrishnam C. Kalmanek
AT&T Research TeraOptic Networks AT&T Research
K.K. Ramakrishnan
Dimitrios Stiliadis TeraOptic Networks
Lucent Technologies March 2002
June 2001
Supplemental Information for the New Definition of the EF PHB
draft-ietf-diffserv-ef-supplemental-01.txt Supplemental Information for the New Definition
of the EF PHB (Expedited Forwarding Per-Hop Behavior)
Status of this Memo Status of this Memo
This document is an Internet-Draft and is in full conformance with This memo provides information for the Internet community. It does
all provisions of Section 10 of RFC2026. not specify an Internet standard of any kind. Distribution of this
memo is unlimited.
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
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 document is a product of the Diffserv working group of the
Internet Engineering Task Force. Please address comments to the
group's mailing list at diffserv@ietf.org, with a copy to the
authors.
Copyright Notice Copyright Notice
Copyright (C) The Internet Society (2001). All Rights Reserved. Copyright (C) The Internet Society (2001). All Rights Reserved.
Abstract Abstract
This document was written during the process of clarification of This document was written during the process of clarification of
RFC2598 [10] that led to the publication of revised specification of RFC2598 "An Expedited Forwarding PHB" that led to the publication of
EF [6]. Its primary motivation is providing additional explanation to revised specification of EF "An Expedited Forwarding PHB". Its
the revised EF definition and its properties. The document also primary motivation is providing additional explanation to the revised
provides additional implementation examples and gives some guidance EF definition and its properties. The document also provides
for computation of the numerical parameters of the new definition for additional implementation examples and gives some guidance for
computation of the numerical parameters of the new definition for
several well known schedulers and router architectures. several well known schedulers and router architectures.
Contents Table of Contents
1 Introduction ........................................... 3 1 Introduction ........................................... 2
2 Definition of EF PHB ................................... 3 2 Definition of EF PHB ................................... 3
2.1 The formal definition .................................. 3 2.1 The formal definition .................................. 3
2.2 Relation to Packet Scale Rate Guarantee ................ 6 2.2 Relation to Packet Scale Rate Guarantee ................ 6
2.3 The need for dual characterization of EF PHB ........... 8 2.3 The need for dual characterization of EF PHB ........... 7
3 Per Packet delay ....................................... 10 3 Per Packet delay ....................................... 9
3.1 Single hop delay bound ................................. 10 3.1 Single hop delay bound ................................. 9
3.2 Multi-hop worst case delay ............................. 10 3.2 Multi-hop worst case delay ............................. 10
4 Packet loss ............................................ 11 4 Packet loss ............................................ 10
5 Implementation considerations .......................... 12 5 Implementation considerations .......................... 11
5.1 The output buffered model with EF FIFO at the output. .. 13 5.1 The output buffered model with EF FIFO at the output. .. 12
5.1.1 Strict Non-preemptive Priority Queue ................... 13 5.1.1 Strict Non-preemptive Priority Queue ................... 12
5.1.2 WF2Q ................................................... 13 5.1.2 WF2Q ................................................... 13
5.1.3 Deficit Round Robin (DRR) .............................. 13 5.1.3 Deficit Round Robin (DRR) .............................. 13
5.1.4 Start-Time Fair Queuing and Self-Clocked Fair Queuing .. 14 5.1.4 Start-Time Fair Queuing and Self-Clocked Fair Queuing .. 13
5.2 Router with Internal Delay and EF FIFO at the output ... 14 5.2 Router with Internal Delay and EF FIFO at the output ... 13
6 Security Considerations ................................ 14 6 Security Considerations ................................ 14
7 References ............................................. 15 7 References ............................................. 14
Appendix A. Difficulties with the RFC 2598 EF PHB Definition .. 16
Appendix B. Alternative Characterization of Packet Scale Rate
Guarantee ......................................... 20
Acknowledgements .............................................. 22
Authors' Addresses ............................................ 22
Full Copyright Statement ...................................... 24
1. Introduction 1. Introduction
The Expedited Forwarding (EF) Per-Hop Behavior (PHB) was designed to The Expedited Forwarding (EF) Per-Hop Behavior (PHB) was designed to
be used to build a low-loss, low-latency, low-jitter, assured be used to build a low-loss, low-latency, low-jitter, assured
bandwidth service. The potential benefits of this service, and bandwidth service. The potential benefits of this service, and
therefore the EF PHB, are enormous. Because of the great value of therefore the EF PHB, are enormous. Because of the great value of
this PHB, it is critical that the forwarding behavior required of and this PHB, it is critical that the forwarding behavior required of and
delivered by an EF-compliant node be specific, quantifiable, and delivered by an EF-compliant node be specific, quantifiable, and
unambiguous. unambiguous.
Unfortunately, the definition of EF PHB in the original RFC2598 [10] Unfortunately, the definition of EF PHB in the original RFC2598 [10]
was not sufficiently precise (see Appendix and [4]). A more precise was not sufficiently precise (see Appendix A and [4]). A more
definition is given in [6]. This document is intended to aid in the precise definition is given in [6]. This document is intended to aid
understanding of the properties of the new definition and provide in the understanding of the properties of the new definition and
supplemental information not included in the text of [6] for sake of provide supplemental information not included in the text of [6] for
brevity. sake of brevity.
The document is outlined as follows. In section 2, we briefly restate This document is outlined as follows. In section 2, we briefly
the definition for EF PHB of [6]. We then provide some additional restate the definition for EF PHB of [6]. We then provide some
discussion of this definition and describe some of its properties. additional discussion of this definition and describe some of its
We discuss the issues associated with per-packet delay and loss in properties. We discuss the issues associated with per-packet delay
sections 3 and 4. In section 5 we discuss the impact of known and loss in sections 3 and 4. In section 5 we discuss the impact of
scheduling architectures on the critical parameters of the new known scheduling architectures on the critical parameters of the new
definition. We also discuss the impact of deviation of real devices definition. We also discuss the impact of deviation of real devices
from the ideal output-buffered model on the magnitude of the critical from the ideal output-buffered model on the magnitude of the critical
parameters in the definition. parameters in the definition.
2. Definition of EF PHB 2. Definition of EF PHB
2.1. The formal definition 2.1. The formal definition
An intuitive explanation of the new EF definition is described in An intuitive explanation of the new EF definition is described in
[6]. Here we restate the formal definition from [6] verbatim. [6]. Here we restate the formal definition from [6] verbatim.
A node that supports EF on an interface I at some configured rate R A node that supports EF on an interface I at some configured rate R
MUST satisfy the following equations: MUST satisfy the following equations:
d_j <= f_j + E_a for all j (eq_1) d_j <= f_j + E_a for all j>0 (eq_1)
where f_j is defined iteratively by where f_j is defined iteratively by
f_0 = 0, d_0 = 0 f_0 = 0, d_0 = 0
f_j = max(a_j, min(d_j-1, f_j-1)) + l_j/R, for all j > 0 (eq_2) f_j = max(a_j, min(d_j-1, f_j-1)) + l_j/R, for all j > 0 (eq_2)
In this definition: In this definition:
- d_j is the time that the last bit of the j-th EF packet to - d_j is the time that the last bit of the j-th EF packet to
depart actually leaves the node from the interface I. depart actually leaves the node from the interface I.
- f_j is the target departure time for the j-th EF packet to - f_j is the target departure time for the j-th EF packet to
depart from I, the "ideal" time at or before which the last bit of depart from I, the "ideal" time at or before which the last bit
that packet should leave the node. of that packet should leave the node.
- a_j is the time that the last bit of the j-th EF packet destined - a_j is the time that the last bit of the j-th EF packet
to the output I actually arrives at the node. destined to the output I actually arrives at the node.
- l_j is the size (bits) of the j-th EF packet to depart from I. - l_j is the size (bits) of the j-th EF packet to depart from I.
l_j is measured on the IP datagram (IP header plus payload) and l_j is measured on the IP datagram (IP header plus payload) and
does not include any lower layer (e.g. MAC layer) overhead. does not include any lower layer (e.g. MAC layer) overhead.
- R is the EF configured rate at output I (in bits/second). - R is the EF configured rate at output I (in bits/second).
- E_a is the error term for the treatment of the EF aggregate. - E_a is the error term for the treatment of the EF aggregate.
Note that E_a represents the worst case deviation between actual Note that E_a represents the worst case deviation between
departure time of an EF packet and ideal departure time of the actual departure time of an EF packet and ideal departure time
same packet, i.e. E_a provides an upper bound on (d_j - f_j) for of the same packet, i.e. E_a provides an upper bound on (d_j -
all j. f_j) for all j.
- d_0 and f_0 do not refer to a real packet departure but are used - d_0 and f_0 do not refer to a real packet departure but are
purely for the purposes of the recursion. The time origin should used purely for the purposes of the recursion. The time origin
be chosen such that no EF packets are in the system at time 0. should be chosen such that no EF packets are in the system at
time 0.
- for the definitions of a_j and d_j, the "last bit" of the packet - for the definitions of a_j and d_j, the "last bit" of the
includes the layer 2 trailer if present, because a packet cannot packet includes the layer 2 trailer if present, because a
generally be considered available for forwarding until such a packet cannot generally be considered available for forwarding
trailer has been received. until such a trailer has been received.
An EF-compliant node MUST be able to be characterized by the range of An EF-compliant node MUST be able to be characterized by the range of
possible R values that it can support on each of its interfaces while possible R values that it can support on each of its interfaces while
conforming to these equations, and the value of E_a that can be met conforming to these equations, and the value of E_a that can be met
on each interface. R may be line rate or less. E_a MAY be specified on each interface. R may be line rate or less. E_a MAY be specified
as a worst-case value for all possible R values or MAY be expressed as a worst-case value for all possible R values or MAY be expressed
as a function of R. as a function of R.
Note also that, since a node may have multiple inputs and complex Note also that, since a node may have multiple inputs and complex
internal scheduling, the jth EF packet to arrive at the node destined internal scheduling, the j-th EF packet to arrive at the node
for a certain interface may not be the jth EF packet to depart from destined for a certain interface may not be the j-th EF packet to
that interface. It is in this sense that eq_1 and eq_2 are unaware of depart from that interface. It is in this sense that eq_1 and eq_2
packet identity. are unaware of packet identity.
In addition, a node that supports EF on an interface I at some In addition, a node that supports EF on an interface I at some
configured rate R MUST satisfy the following equations: configured rate R MUST satisfy the following equations:
D_j <= F_j + E_p for all j (eq_3) D_j <= F_j + E_p for all j>0 (eq_3)
where F_j is defined iteratively by where F_j is defined iteratively by
F_0 = 0, D_0 = 0 F_0 = 0, D_0 = 0
F_j = max(A_j, min(D_j-1, F_j-1)) + L_j/R, for all j > 0 (eq_4) F_j = max(A_j, min(D_j-1, F_j-1)) + L_j/R, for all j > 0 (eq_4)
In this definition: In this definition:
- D_j is actual the departure time of the individual EF packet - D_j is the actual departure time of the individual EF packet
that arrived at the node destined for interface I at time A_j, that arrived at the node destined for interface I at time A_j,
i.e., given a packet which was the j-th EF packet destined for I i.e., given a packet which was the j-th EF packet destined for
to arrive at the node via any input, D_j is the time at which the I to arrive at the node via any input, D_j is the time at which
last bit of that individual packet actually leaves the node from the last bit of that individual packet actually leaves the node
the interface I. from the interface I.
- F_j is the target departure time for the individual EF packet - F_j is the target departure time for the individual EF packet
that arrived at the node destined for interface I at time A_j. that arrived at the node destined for interface I at time A_j.
- A_j is the time that the last bit of the j-th EF packet destined - A_j is the time that the last bit of the j-th EF packet
to the output I to arrive actually arrives at the node. destined to the output I to arrive actually arrives at the
node.
- L_j is the size (bits) of the j-th EF packet to arrive at the - L_j is the size (bits) of the j-th EF packet to arrive at the
node that is destined to output I. L_j is measured on the IP node that is destined to output I. L_j is measured on the IP
datagram (IP header plus payload) and does not include any lower datagram (IP header plus payload) and does not include any
layer (e.g. MAC layer) overhead. lower layer (e.g. MAC layer) overhead.
- R is the EF configured rate at output I (in bits/second). - R is the EF configured rate at output I (in bits/second).
- E_p is the error term for the treatment of individual EF - E_p is the error term for the treatment of individual EF
packets. Note that E_p represents the worst case deviation between packets. Note that E_p represents the worst case deviation
actual departure time of an EF packet and ideal departure time of between the actual departure time of an EF packet and the ideal
the same packet, i.e. E_p provides an upper bound on (D_j - F_j) departure time of the same packet, i.e. E_p provides an upper
for all j. bound on (D_j - F_j) for all j.
- D_0 and F_0 do not refer to a real packet departure but are used - D_0 and F_0 do not refer to a real packet departure but are
purely for the purposes of the recursion. The time origin should used purely for the purposes of the recursion. The time origin
be chosen such that no EF packets are in the system at time 0. should be chosen such that no EF packets are in the system at
time 0.
- for the definitions of A_j and D_j, the "last bit" of the packet - for the definitions of A_j and D_j, the "last bit" of the
includes the layer 2 trailer if present, because a packet cannot packet includes the layer 2 trailer if present, because a
generally be considered available for forwarding until such a packet cannot generally be considered available for forwarding
trailer has been received. until such a trailer has been received.
It is the fact that D_j and F_j refer to departure times for the jth It is the fact that D_j and F_j refer to departure times for the j-th
packet to arrive that makes eq_3 and eq_4 aware of packet identity. packet to arrive that makes eq_3 and eq_4 aware of packet identity.
This is the critical distinction between the last two equations and This is the critical distinction between the last two equations and
the first two. the first two.
An EF-compliant node SHOULD be able to be characterized by the range An EF-compliant node SHOULD be able to be characterized by the range
of possible R values that it can support on each of its interfaces of possible R values that it can support on each of its interfaces
while conforming to these equations, and the value of E_p that can be while conforming to these equations, and the value of E_p that can be
met on each interface. E_p MAY be specified as a worst-case value for met on each interface. E_p MAY be specified as a worst-case value
all possible R values or MAY be expressed as a function of R. An E_p for all possible R values or MAY be expressed as a function of R. An
value of "undefined" MAY be specified. E_p value of "undefined" MAY be specified.
Finally, there is an additional requirement in [6] that an EF Finally, there is an additional recommendation in [6] that an EF
compliant node cannot reorder packets within a microflow. compliant node SHOULD NOT reorder packets within a micorflow.
The definitions described in this section are referred to as The definitions described in this section are referred to as
aggregate and packet-identity-aware packet scale rate guarantee aggregate and packet-identity-aware packet scale rate guarantee
[4],[2]. An alternative mathematical characterisation of packet scale [4],[2]. An alternative mathematical characterization of packet
rate guarantee is given in Appendix B. scale rate guarantee is given in Appendix B.
2.2. Relation to Packet Scale Rate Guarantee 2.2. Relation to Packet Scale Rate Guarantee
Consider the case of an ideal output-buffered device with an EF FIFO Consider the case of an ideal output-buffered device with an EF FIFO
at the output. For such a device, the i-th packet to arrive to the at the output. For such a device, the i-th packet to arrive to the
device is also the i-th packet to depart from the device. Therefore, device is also the i-th packet to depart from the device. Therefore,
in this ideal model the aggregate behavior and packet-identity-aware in this ideal model the aggregate behavior and packet-identity-aware
characteristics are identical, and E_a = E_p. In this section we characteristics are identical, and E_a = E_p. In this section we
therefore omit the subscript and refer to the latency term simply as therefore omit the subscript and refer to the latency term simply as
E. E.
It could be shown that for such an ideal device the definition of It could be shown that for such an ideal device the definition of
section 2 is stronger than the well-known rate-latency curve [2] in section 2.1 is stronger than the well-known rate-latency curve [2] in
the sense that if a scheduler satisfies the EF definition it also the sense that if a scheduler satisfies the EF definition it also
satisfies the rate-latency curve. As a result, all the properties satisfies the rate-latency curve. As a result, all the properties
known for the rate-latency curve also apply to the modified EF known for the rate-latency curve also apply to the modified EF
definition. However, we argue below that the definition of section definition. However, we argue below that the definition of section
2.1 is more suitable to reflect the intent of EF PHB than the rate- 2.1 is more suitable to reflect the intent of EF PHB than the rate-
latency curve. latency curve.
It is shown in [2] that the rate-latency curve is equivalent to the It is shown in [2] that the rate-latency curve is equivalent to the
following definition: following definition:
Definition of Rate Latency Curve (RLC): Definition of Rate Latency Curve (RLC):
D(j) <= F'(j) + E (eq_5) D(j) <= F'(j) + E (eq_5)
where where
F'(0)=0, F'(j)=max(a(j), F'(j-1))+ L(j)/R for all j>0 (eq_6)
F'(0)=0, F'(j)=max(a(j), F'(j-1))+ L(j)/R for all j>0 (eq_6)
It can be easily verified that the EF definition of section 2.1 is It can be easily verified that the EF definition of section 2.1 is
stronger than RLC by noticing that for all j, F'(j) >= F(j). stronger than RLC by noticing that for all j, F'(j) >= F(j).
It is easy to see that F'(j) in the definition RLC corresponds to the It is easy to see that F'(j) in the definition of RLC corresponds to
time the j-th departure should have occurred should the EF aggregate the time the j-th departure should have occurred should the EF
be constantly served exactly at its configured rate R. Following the aggregate be constantly served exactly at its configured rate R.
common convention, we refer to F'(j) as the "fluid finish time" of Following the common convention, we refer to F'(j) as the "fluid
the j-th packet to depart. finish time" of the j-th packet to depart.
The intuitive meaning of the rate-latency curve of RLC is that any The intuitive meaning of the rate-latency curve of RLC is that any
packet is served at most time E later than this packet would finish packet is served at most time E later than this packet would finish
service in the fluid model. service in the fluid model.
For RLC (and hence for the stronger EF definition) it holds that in For RLC (and hence for the stronger EF definition) it holds that in
any interval (0,t) the EF aggregate gets close to the desired service any interval (0,t) the EF aggregate gets close to the desired service
rate R (as long as there is enough traffic to sustain this rate). The rate R (as long as there is enough traffic to sustain this rate).
discrepancy between the ideal and the actual service in this interval The discrepancy between the ideal and the actual service in this
depends on the latency term E, which in turn depends on the interval depends on the latency term E, which in turn depends on the
scheduling implementation. The smaller E, the smaller the difference scheduling implementation. The smaller E, the smaller the difference
between the configured rate and the actual rate achieved by the between the configured rate and the actual rate achieved by the
scheduler. scheduler.
While RLC guarantees the desired rate to the EF aggregate in all While RLC guarantees the desired rate to the EF aggregate in all
intervals (0,t) to within a specified error, it may nevertheless intervals (0,t) to within a specified error, it may nevertheless
result in large gaps in service. For example, suppose that (a large result in large gaps in service. For example, suppose that (a large
number) N of identical EF packets of length L arrived from different number) N of identical EF packets of length L arrived from different
interfaces to the EF queue in the absence of any non-EF traffic. interfaces to the EF queue in the absence of any non-EF traffic.
Then any work-conserving scheduler will serve all N packets at link Then any work-conserving scheduler will serve all N packets at link
speed. When the last packet is sent at time NL/C, where C is the speed. When the last packet is sent at time NL/C, where C is the
capacity of output link, F(N) will be equal to NL/R. That is, the capacity of output link, F'(N) will be equal to NL/R. That is, the
scheduler is running ahead of ideal, since NL/C < NL/R for R < C. scheduler is running ahead of ideal, since NL/C < NL/R for R < C.
Suppose now that at time NL/C a large number of non-EF packets Suppose now that at time NL/C a large number of non-EF packets
arrive, followed by a single EF packet. Then the scheduler can arrive, followed by a single EF packet. Then the scheduler can
legitimately delay starting to send the EF packet until time legitimately delay starting to send the EF packet until time
F(N+1)=(N+1)L/R + E - L/C. This means that the EF aggregate will F'(N+1)=(N+1)L/R + E - L/C. This means that the EF aggregate will
have no service at all in the interval (NL/C, (N+1)L/R + E - L/C). have no service at all in the interval (NL/C, (N+1)L/R + E - L/C).
This interval can be quite large if R is substantially smaller than This interval can be quite large if R is substantially smaller than
C. In essence, the EF aggregate can be "punished" by a gap in C. In essence, the EF aggregate can be "punished" by a gap in
service for receiving faster service than its configured rate at the service for receiving faster service than its configured rate at the
beginning. beginning.
The new EF definition alleviates this problem by introducing the term The new EF definition alleviates this problem by introducing the term
min(D(j-1), F(j-1)) in the recursion. Essentially, this means that min(D(j-1), F(j-1)) in the recursion. Essentially, this means that
the fluid finishing time is "reset" if that packet is sent before its the fluid finishing time is "reset" if that packet is sent before its
"ideal" departure time. As a consequence of that, for the case where "ideal" departure time. As a consequence of that, for the case where
the EF aggregate is served in the FIFO order, suppose a packet the EF aggregate is served in the FIFO order, suppose a packet
arrives at time t to a server satisfying the EF definition. The arrives at time t to a server satisfying the EF definition. The
packet will be transmitted no later than time t + Q(t)/R + E, where packet will be transmitted no later than time t + Q(t)/R + E, where
Q(t) is the EF queue size at time t (including the packet under Q(t) is the EF queue size at time t (including the packet under
discussion)[4]. discussion)[4].
2.3. The need for dual characterization of EF PHB 2.3. The need for dual characterization of EF PHB
In a more general case, where either the output scheduler does not In a more general case, where either the output scheduler does not
serve the EF packets in a FIFO order, or the variable internal delay serve the EF packets in a FIFO order, or the variable internal delay
in the device reorders packets while delivering them to the output in the device reorders packets while delivering them to the output
(or both), the i-th packet destined to a given output interface to (or both), the i-th packet destined to a given output interface to
arrive to the device may no longer be the i-th packet to depart from arrive to the device may no longer be the i-th packet to depart from
that interface. In that case the packet-identity-aware and the that interface. In that case the packet-identity-aware and the
aggregate definitions are no longer identical. aggregate definitions are no longer identical.
The aggregate behavior definition can be viewed as a truly aggregate The aggregate behavior definition can be viewed as a truly aggregate
characteristic of the service provided to EF packets. For an analogy characteristic of the service provided to EF packets. For an
consider a dark reservoir to which all arriving packets are placed. analogy, consider a dark reservoir to which all arriving packets are
A scheduler is allowed to pick a packet from the reservoir in a placed. A scheduler is allowed to pick a packet from the reservoir
random order, without any knowledge of the order of packet arrivals. in a random order, without any knowledge of the order of packet
The aggregate part of the definition measures the accuracy of the arrivals. The aggregate part of the definition measures the accuracy
output rate provided to the EF aggregate as a whole. The smaller E_a, of the output rate provided to the EF aggregate as a whole. The
the more accurate is the assurance that the reservoir is drained at smaller E_a, the more accurate is the assurance that the reservoir is
least at the configured rate. drained at least at the configured rate.
Note that in this reservoir analogy packets of EF aggregate may be Note that in this reservoir analogy packets of EF aggregate may be
arbitrarily reordered. However, the definition of EF PHB given in [6] arbitrarily reordered. However, the definition of EF PHB given in
explicitly requires that no packet reordering occur within a [6] explicitly requires that no packet reordering occur within a
microflow. This requirement restricts the scheduling implementations, microflow. This requirement restricts the scheduling
or, in the reservoir analogy, the order of pulling packets out of the implementations, or, in the reservoir analogy, the order of pulling
reservoir to make sure that packets within a microflow are not packets out of the reservoir to make sure that packets within a
reordered, but it still allows reordering at the aggregate level. microflow are not reordered, but it still allows reordering at the
aggregate level.
Note that reordering within the aggregate, as long as there is no Note that reordering within the aggregate, as long as there is no
flow-level reordering, does not necessarily reflect a "bad" service. flow-level reordering, does not necessarily reflect a "bad" service.
Consider for example a scheduler that arbitrates among 10 different Consider for example a scheduler that arbitrates among 10 different
EF "flows" with diverse rates. A scheduler that is aware of the rate EF "flows" with diverse rates. A scheduler that is aware of the rate
requirements may choose to send a packet of the faster flow before a requirements may choose to send a packet of the faster flow before a
packet of the slower flow to maintain lower jitter at the flow level. packet of the slower flow to maintain lower jitter at the flow level.
In particular, an ideal "flow"-aware WFQ scheduler will cause In particular, an ideal "flow"-aware WFQ scheduler will cause
reordering within the aggregate, while maintaining packet ordering reordering within the aggregate, while maintaining packet ordering
and small jitter at the flow level. and small jitter at the flow level.
It is intuitively clear that for such a scheduler, as well as for a It is intuitively clear that for such a scheduler, as well as for a
simpler FIFO scheduler, the "accuracy" of the service rate is crucial simpler FIFO scheduler, the "accuracy" of the service rate is crucial
for minimizing "flow"-level jitter. The packet-identity-aware for minimizing "flow"-level jitter. The packet-identity-aware
definition quantifies this accuracy of the service rate. definition quantifies this accuracy of the service rate.
However, the small value of E_a does not give any assurances about However, the small value of E_a does not give any assurances about
the absolute value of per-packet delay. In fact, if the input rate the absolute value of per-packet delay. In fact, if the input rate
exceeds the configured rate, the aggregate behavior definition may exceeds the configured rate, the aggregate behavior definition may
result in arbitrarily large delay of a subset of packets. This is result in arbitrarily large delay of a subset of packets. This is
the primary motivation for the packet-identity-aware definition. the primary motivation for the packet-identity-aware definition.
The primary goal of the packet-aware characterization of the EF The primary goal of the packet-aware characterization of the EF
implementation is that, unlike the aggregate behavior implementation is that, unlike the aggregate behavior
characterization, it provides a way to find a per-packet delay bound characterization, it provides a way to find a per-packet delay bound
as a function of input traffic parameters. as a function of input traffic parameters.
While the aggregate behavior definition characterizes the accuracy of While the aggregate behavior definition characterizes the accuracy of
the service rate of the entire EF aggregate, the packet-identity- the service rate of the entire EF aggregate, the packet-identity-
aware part of the definition characterizes the deviation of the aware part of the definition characterizes the deviation of the
device from an ideal server that serves the EF aggregate in FIFO device from an ideal server that serves the EF aggregate in FIFO
order at least at the configured rate. order at least at the configured rate.
The value of E_p in the packet-identity-aware definition is therefore The value of E_p in the packet-identity-aware definition is therefore
affected by two factors: the accuracy of the aggregate rate service affected by two factors: the accuracy of the aggregate rate service
and the degree of packet reordering within the EF aggregate (under and the degree of packet reordering within the EF aggregate (under
the constraint that packets within the same microflow are not the constraint that packets within the same microflow are not
reordered). Therefore, a sub-aggregate aware device that provides an reordered). Therefore, a sub-aggregate aware device that provides an
ideal service rate to the aggregate, and also provides an ideal rate ideal service rate to the aggregate, and also provides an ideal rate
service for each of the sub-aggregates, may nevertheless have a very service for each of the sub-aggregates, may nevertheless have a very
large value of E_p (in this case E_p must be at least equal to the large value of E_p (in this case E_p must be at least equal to the
ratio of the maximum packet size divided by the smallest rate of any ratio of the maximum packet size divided by the smallest rate of any
sub aggregate). As a result, a large value of E_p does not sub aggregate). As a result, a large value of E_p does not
necessarily mean that the service provided to EF aggregate is bad - necessarily mean that the service provided to EF aggregate is bad -
rather it may be an indication that the service is good, but non- rather it may be an indication that the service is good, but non-
FIFO. On the other hand, a large value of E_p may also mean that the FIFO. On the other hand, a large value of E_p may also mean that the
aggregate service is very inaccurate (bursty), and hence in this case aggregate service is very inaccurate (bursty), and hence in this case
the large value of E_p reflects a poor quality of implementation. the large value of E_p reflects a poor quality of implementation.
skipping to change at page 10, line 8 skipping to change at page 9, line 29
guidance on the quality of the EF implementation. However, a small guidance on the quality of the EF implementation. However, a small
value of E_p does indicate a high quality FIFO implementation. value of E_p does indicate a high quality FIFO implementation.
Since E_p and E_a relate to different aspects of the EF Since E_p and E_a relate to different aspects of the EF
implementation, they should be considered together to determine the implementation, they should be considered together to determine the
quality of the implementation. quality of the implementation.
3. Per Packet delay 3. Per Packet delay
The primary motivation for the packet-identity-aware definition is The primary motivation for the packet-identity-aware definition is
that it allows allows quantification of the per-packet delay bound. that it allows quantification of the per-packet delay bound. This
This section discusses the issues with computing per-packet delay section discusses the issues with computing per-packet delay.
3.1. Single hop delay bound 3.1. Single hop delay bound
If the total traffic arriving to an output port I from all inputs is If the total traffic arriving to an output port I from all inputs is
constrained by a leaky bucket with parameters (R, B), where R is the constrained by a leaky bucket with parameters (R, B), where R is the
configured rate at I, and B is the bucket depth (burst), then the configured rate at I, and B is the bucket depth (burst), then the
delay of any packet departing from I is bounded by D_p, given by delay of any packet departing from I is bounded by D_p, given by
D_p = B/R + E_p (eq_7) D_p = B/R + E_p (eq_7)
(see appendix B). (see appendix B).
Because the delay bound depends on the configured rate R and the Because the delay bound depends on the configured rate R and the
input burstiness B, it is desirable for both of these parameters to input burstiness B, it is desirable for both of these parameters to
be visible to a user of the device. A PDB desiring a particular be visible to a user of the device. A PDB desiring a particular
delay bound may need to limit the range of configured rates and delay bound may need to limit the range of configured rates and
allowed burstiness that it can support in order to deliver such allowed burstiness that it can support in order to deliver such
bound. Equation (eq_7) provides a means for determining an acceptable bound. Equation (eq_7) provides a means for determining an
operating region for the device with a given E_p. It may also be acceptable operating region for the device with a given E_p. It may
useful to limit the total offered load to a given output to some rate also be useful to limit the total offered load to a given output to
R_1 < R (e.g. to obtain end-to-end delay bounds [5]). It is important some rate R_1 < R (e.g. to obtain end-to-end delay bounds [5]). It
to realize that, while R_1 may also be a configurable parameter of is important to realize that, while R_1 may also be a configurable
the device, the delay bound in (eq_7) does not depend on it. It may parameter of the device, the delay bound in (eq_7) does not depend on
be possible to get better bounds explicitly using the bound on the it. It may be possible to get better bounds explicitly using the
input rate, but the bound (eq_7) does not take advantage of this bound on the input rate, but the bound (eq_7) does not take advantage
information. of this information.
3.2. Multi-hop worst case delay 3.2. Multi-hop worst case delay
Although the PHB defines inherently local behavior, in this section Although the PHB defines inherently local behavior, in this section
we briefly discuss the issue of per-packet delay as the packet we briefly discuss the issue of per-packet delay as the packet
traverses several hops implementing EF PHB. Given a delay bound traverses several hops implementing EF PHB. Given a delay bound
(eq_7) at a single hop, it is tempting to conclude that per-packet (eq_7) at a single hop, it is tempting to conclude that per-packet
bound across h hops is simply h times the bound (eq_7). However, bound across h hops is simply h times the bound (eq_7). However,
this is not necessarily the case, unless B represents the worst case this is not necessarily the case, unless B represents the worst case
input burstiness across all nodes in the network. input burstiness across all nodes in the network.
Unfortunately, obtaining such a worst case value of B is not trivial. Unfortunately, obtaining such a worst case value of B is not trivial.
If EF PHB is implemented using aggregate class-based scheduling where If EF PHB is implemented using aggregate class-based scheduling where
all EF packets share a single FIFO, the effect of jitter accumulation all EF packets share a single FIFO, the effect of jitter accumulation
may result in an increase in burstiness from hop to hop. In may result in an increase in burstiness from hop to hop. In
particular, it can be shown that unless severe restrictions on EF particular, it can be shown that unless severe restrictions on EF
utilization are imposed, even if all EF flows are ideally shaped at utilization are imposed, even if all EF flows are ideally shaped at
the ingress, then for any value of delay D it is possible to the ingress, then for any value of delay D it is possible to
construct a network where EF utilization on any link is bounded not construct a network where EF utilization on any link is bounded not
to exceed a given factor, no flow traverses more than a specified to exceed a given factor, no flow traverses more than a specified
number of hops, but there exists a packet that experiences a delay number of hops, but there exists a packet that experiences a delay
more than D [5]. This result implies that the ability to limit the more than D [5]. This result implies that the ability to limit the
worst case burstiness and the resulting end-to-end delay across worst case burstiness and the resulting end-to-end delay across
several hops may require not only limiting EF utilization on all several hops may require not only limiting EF utilization on all
links, but also constraining the global network topology. Such links, but also constraining the global network topology. Such
topology constraints would need to be specified in the definition of topology constraints would need to be specified in the definition of
any PDB built on top of EF PHB, if such PDB requires a strict worst any PDB built on top of EF PHB, if such PDB requires a strict worst
case delay bound. case delay bound.
4. Packet loss 4. Packet loss
Any device with finite buffering may need to drop packets if the Any device with finite buffering may need to drop packets if the
input burstiness becomes sufficiently high. To meet the low loss input burstiness becomes sufficiently high. To meet the low loss
objective of EF, a node may be characterized by the operating region objective of EF, a node may be characterized by the operating region
in which loss of EF due to congestion will not occur. This may be in which loss of EF due to congestion will not occur. This may be
specified as a token bucket of rate r <= R and burst size B that can specified as a token bucket of rate r <= R and burst size B that can
be offered from all inputs to a given output interface without loss. be offered from all inputs to a given output interface without loss.
However, as discussed in the previous section, the phenomenon of However, as discussed in the previous section, the phenomenon of
jitter accumulation makes it generally difficult to guarantee that jitter accumulation makes it generally difficult to guarantee that
the input burstiness never exceeds the specified operating region for the input burstiness never exceeds the specified operating region for
nodes internal to the DiffServ domain. A no-loss guarantee across nodes internal to the DiffServ domain. A no-loss guarantee across
multiple hops may require specification of constraints on network multiple hops may require specification of constraints on network
topology which are outside the scope of inherently local definition topology which are outside the scope of inherently local definition
of a PHB. Thus, it must be possible to establish whether a device of a PHB. Thus, it must be possible to establish whether a device
conforms to the EF definition even when some packets are lost. conforms to the EF definition even when some packets are lost.
This can be done by performing an "off-line" test of conformance to This can be done by performing an "off-line" test of conformance to
equations (eq_1)- (eq_4). After observing a sequence of packets equations (eq_1)- (eq_4). After observing a sequence of packets
entering and leaving the node, the packets which did not leave are entering and leaving the node, the packets which did not leave are
assumed lost and are notionally removed from the input stream. The assumed lost and are notionally removed from the input stream. The
remaining packets now constitute the arrival stream and the packets remaining packets now constitute the arrival stream and the packets
which left the node constitute the departure stream. Conformance to which left the node constitute the departure stream. Conformance to
the equations can thus be verified by considering only those packets the equations can thus be verified by considering only those packets
that successfully passed through the node.. that successfully passed through the node.
Note that specification of which packets are lost in the case when Note that specification of which packets are lost in the case when
loss does occur is beyond the scope of the definition of EF PHB. loss does occur is beyond the scope of the definition of EF PHB.
However, those packets that were not lost must conform to the However, those packets that were not lost must conform to the
equations definition of EF PHB in section 2.1. equations definition of EF PHB in section 2.1.
5. Implementation considerations 5. Implementation considerations
A packet passing through a router will experience delay for a number A packet passing through a router will experience delay for a number
of reasons. Two familiar components of this delay are the time the of reasons. Two familiar components of this delay are the time the
skipping to change at page 12, line 23 skipping to change at page 11, line 40
There may be other components of a packet's delay through a router, There may be other components of a packet's delay through a router,
however. A router might have to do some amount of header processing however. A router might have to do some amount of header processing
before the packet can be given to the correct output scheduler, for before the packet can be given to the correct output scheduler, for
example. In another case a router may have a FIFO buffer (called a example. In another case a router may have a FIFO buffer (called a
transmission queue in [7]) where the packet sits after being selected transmission queue in [7]) where the packet sits after being selected
by the output scheduler but before it is transmitted. In cases such by the output scheduler but before it is transmitted. In cases such
as these, the extra delay a packet may experience can be accounted as these, the extra delay a packet may experience can be accounted
for by absorbing it into the latency terms E_a and E_p. for by absorbing it into the latency terms E_a and E_p.
Implementing EF on a router with a multi-stage switch fabric requires Implementing EF on a router with a multi-stage switch fabric requires
special attention. A packet may experience additional delays due to special attention. A packet may experience additional delays due to
the fact that it must compete with other traffic for forwarding the fact that it must compete with other traffic for forwarding
resources at multiple contention points in the switch core. The delay resources at multiple contention points in the switch core. The
an EF packet may experience before it even reaches the output-link delay an EF packet may experience before it even reaches the output-
scheduler should be included in the latency term. Input-buffered and link scheduler should be included in the latency term. Input-
input/output-buffered routers based on crossbar design may also buffered and input/output-buffered routers based on crossbar design
require modification of their latency terms. The factors such as the may also require modification of their latency terms. The factors
speedup factor and the choice of crossbar arbitration algorithms may such as the speedup factor and the choice of crossbar arbitration
affect the latency terms substantially. algorithms may affect the latency terms substantially.
Delay in the switch core comes from two sources, both of which must Delay in the switch core comes from two sources, both of which must
be considered. The first part of this delay is the fixed delay a be considered. The first part of this delay is the fixed delay a
packet experiences regardless of the other traffic. This component packet experiences regardless of the other traffic. This component
of the delay includes the time it takes for things such as packet of the delay includes the time it takes for things such as packet
segmentation and reassembly in cell based cores, enqueueing and segmentation and reassembly in cell based cores, enqueueing and
dequeueing at each stage, and transmission between stages. The dequeuing at each stage, and transmission between stages. The second
second part of the switch core delay is variable and depends on the part of the switch core delay is variable and depends on the type and
type and amount of other traffic traversing the core. This delay amount of other traffic traversing the core. This delay comes about
comes about if the stages in the core mix traffic flowing between if the stages in the core mix traffic flowing between different
different input/output port pairs. Thus, EF packets must compete input/output port pairs. Thus, EF packets must compete against other
against other traffic for forwarding resources in the core. Some of traffic for forwarding resources in the core. Some of this
this competing traffic may even be EF traffic from other aggregates. competing traffic may even be traffic from other, non-EF aggregates.
This introduces extra delay, that can also be absorbed by the latency This introduces extra delay, that can also be absorbed by the latency
term in the definition. term in the definition.
To capture these considerations, in this section we will consider two To capture these considerations, in this section we will consider two
simplified implementation examples. The first is an ideal output simplified implementation examples. The first is an ideal output
buffered node where packets entering the device from an input buffered node where packets entering the device from an input
interface are immediately delivered to the output scheduler. In this interface are immediately delivered to the output scheduler. In this
model the properties of the output scheduler fully define the values model the properties of the output scheduler fully define the values
of the parameters E_a and E_p. We will consider the case where the of the parameters E_a and E_p. We will consider the case where the
output scheduler implements aggregate class-based queueing, so that output scheduler implements aggregate class-based queuing, so that
all EF packets share a single queue. We will discuss the values of all EF packets share a single queue. We will discuss the values of
E_a and E_p for a variety of class-based schedulers widely considered E_a and E_p for a variety of class-based schedulers widely
considered.
The second example will consider a router modeled as a black box with The second example will consider a router modeled as a black box with
a known bound on the variable delay a packet can experience from the a known bound on the variable delay a packet can experience from the
time it arrives to an input to the time it is delivered to its time it arrives to an input to the time it is delivered to its
destination output. The output scheduler in isolation is assumed to destination output. The output scheduler in isolation is assumed to
be an aggregate scheduler where all EF packets share a single FIFO be an aggregate scheduler where all EF packets share a single FIFO
queue, with a known value of E_a(S)=E_p(S)=E(S). This model provides queue, with a known value of E_a(S)=E_p(S)=E(S). This model provides
a reasonable abstraction to a large class of router implementations. a reasonable abstraction to a large class of router implementations.
5.1. The output buffered model with EF FIFO at the output. 5.1. The output buffered model with EF FIFO at the output.
As has been mentioned earlier, in this model E_a = E_p, so we shall As has been mentioned earlier, in this model E_a = E_p, so we shall
omit the subscript and refer to both terms as latency E. The omit the subscript and refer to both terms as latency E. The
remainder of this subsection discusses E for a number of scheduling remainder of this subsection discusses E for a number of scheduling
implementations. implementations.
5.1.1. Strict Non-preemptive Priority Queue 5.1.1. Strict Non-preemptive Priority Queue
A Strict Priority scheduler in which all EF packets share a single A Strict Priority scheduler in which all EF packets share a single
FIFO queue which is served at strict non-preemptive priority over FIFO queue which is served at strict non-preemptive priority over
other queues satisfies the EF definition with the latency term E = other queues satisfies the EF definition with the latency term E =
MTU/C where MTU is the maximum packet size and C is the speed of the MTU/C where MTU is the maximum packet size and C is the speed of the
output link. output link.
5.1.2. WF2Q 5.1.2. WF2Q
Another scheduler that satisfies the EF definition with a small Another scheduler that satisfies the EF definition with a small
latency term is WF2Q described in [1]. A class-based WF2Q scheduler, latency term is WF2Q described in [1]. A class-based WF2Q scheduler,
in which all EF traffic shares a single queue with the weight in which all EF traffic shares a single queue with the weight
corresponding to the configured rate of the EF aggregate satisfies corresponding to the configured rate of the EF aggregate satisfies
the EF definition with the latency term E = MTU/C+MTU/R. the EF definition with the latency term E = MTU/C+MTU/R.
5.1.3. Deficit Round Robin (DRR) 5.1.3. Deficit Round Robin (DRR)
For DRR [12], E can be shown to grow linearly with For DRR [12], E can be shown to grow linearly with
N*(r_max/r_min)*MTU, where r_min and r_max denote the smallest and N*(r_max/r_min)*MTU, where r_min and r_max denote the smallest and
the largest rate among the rate assignments of all queues in the the largest rate among the rate assignments of all queues in the
scheduler, and N is the number of queues in the scheduler scheduler, and N is the number of queues in the scheduler.
5.1.4. Start-Time Fair Queuing and Self-Clocked Fair Queuing 5.1.4. Start-Time Fair Queuing and Self-Clocked Fair Queuing
For Start-Time Fair Queuing and (SFQ) [9] and Self-Clocked Fair For Start-Time Fair Queuing (SFQ) [9] and Self-Clocked Fair Queuing
Queueing (SCFQ) [8] E can be shown to grow linearly with the number (SCFQ) [8] E can be shown to grow linearly with the number of queues
of queues in the scheduler. in the scheduler.
5.2. Router with Internal Delay and EF FIFO at the output 5.2. Router with Internal Delay and EF FIFO at the output
In this section we consider a router which is modeled as follows. A In this section we consider a router which is modeled as follows. A
packet entering the router may experience a variable delay D_v with a packet entering the router may experience a variable delay D_v with a
known upper bound D. That is, 0<=D_v<=D. At the output all EF known upper bound D. That is, 0<=D_v<=D. At the output all EF
packets share a single class queue. Class queues are scheduled by a packets share a single class queue. Class queues are scheduled by a
scheduler with a known value E_p(S)=E(S) (where E(S) corresponds to scheduler with a known value E_p(S)=E(S) (where E(S) corresponds to
the model where this scheduler is implemented in an ideal output the model where this scheduler is implemented in an ideal output
buffered device). buffered device).
The computation of E_p is more complicated in this case. For such The computation of E_p is more complicated in this case. For such
device, it can be shown that E_p = E(S)+2D+2B/R (see Appendix C). device, it can be shown that E_p = E(S)+2D+2B/R (see [13]).
Recall from the discussion of section 3 that bounding input Recall from the discussion of section 3 that bounding input
burstiness B may not be easy in a general topology. In the absence of burstiness B may not be easy in a general topology. In the absence
the knowledge of a bound on B one can bound E_p as E_p = E(S) + of the knowledge of a bound on B one can bound E_p as E_p = E(S) +
D*C_inp/R (see appendix B). D*C_inp/R (see [13]).
Note also that the bounds in this section are derived using only the Note also that the bounds in this section are derived using only the
bound on the variable portion of the interval delay and the error bound on the variable portion of the interval delay and the error
bound of the output scheduler. If more details about the bound of the output scheduler. If more details about the
architecture of a device are available, it may be possible to compute architecture of a device are available, it may be possible to compute
better bounds. better bounds.
6. Security Considerations 6. Security Considerations
This informational draft provides additional information to aid in This informational document provides additional information to aid in
understanding of the EF PHB described in [6]. It adds no new understanding of the EF PHB described in [6]. It adds no new
functions to it. As a result, it adds no security issues to those functions to it. As a result, it adds no security issues to those
described in that specification. described in that specification.
7. References 7. References
[1] J.C.R. Bennett and H. Zhang, ``WF2Q: Worst-case Fair Weighted [1] J.C.R. Bennett and H. Zhang, "WF2Q: Worst-case Fair Weighted
Fair Queuing'', INFOCOM'96, Mar, 1996 Fair Queuing", INFOCOM'96, March 1996.
[2] J.-Y. Le Boudec, P. Thiran, "Network Calculus", Springer Verlag [2] J.-Y. Le Boudec, P. Thiran, "Network Calculus", Springer Verlag
Lecture Notes in Computer Science volume 2050, June 2001 (available Lecture Notes in Computer Science volume 2050, June 2001
online at http://icawww.epfl.ch) (available online at http://lcawww.epfl.ch).
[3] S. Bradner, "Key Words for Use in RFCs to Indicate Requirement [3] Bradner, S., "Key Words for Use in RFCs to Indicate Requirement
Levels", BCP 14, RFC 2119, March 1997. Levels", BCP 14, RFC 2119, March 1997.
[4] J. Bennett, K. Benson, A. Charny, W. Courney, J.Y. Le Boudec, [4] J.C.R. Bennett, K. Benson, A. Charny, W. Courtney, J.Y. Le
"Delay Jitter Bounds and Packet Scale Rate Guarantee for Expedited Boudec, "Delay Jitter Bounds and Packet Scale Rate Guarantee
Forwarding", Proc. Infocom 2001, April 2001. for Expedited Forwarding", Proc. Infocom 2001, April 2001.
[5] A. Charny, J.-Y. Le Boudec "Delay Bounds in a Network with [5] A. Charny, J.-Y. Le Boudec "Delay Bounds in a Network with
Aggregate Scheduling". Proc. of QoFIS'2000, September 25-26, 2000, Aggregate Scheduling". Proc. of QoFIS'2000, September 25-26,
Berlin, Germany. 2000, Berlin, Germany.
[6] B. Davie, ed. et al, "An Expedited Forwarding PHB", draft-ietf- [6] Davie, B., Charny, A., Baker, F., Bennett, J.C.R., Benson, K.,
diffserv-rfc2598bis-01.txt, work in progress, April 2001. Boudec, J., Chiu, A., Courtney, W., Davari, S., Firoiu, V.,
Kalmanek, C., Ramakrishnan, K.K. and D. Stiliadis, "An
Expedited Forwarding PHB (Per-Hop Behavior)", RFC 3246, March
2002.
[7] T. Ferrari and P. F. Chimento, "A Measurement- Based Analysis of [7] T. Ferrari and P. F. Chimento, "A Measurement-Based Analysis of
Expedited Forwarding PHB Mechanisms," Eighth International Workshop Expedited Forwarding PHB Mechanisms," Eighth International
on Quality of Service, Pittsburgh, PA, June 2000, Workshop on Quality of Service, Pittsburgh, PA, June 2000.
[8] S.J. Golestani. "A Self-clocked Fair Queuing Scheme for Broad- [8] S.J. Golestani. "A Self-clocked Fair Queuing Scheme for Broad-
band Applications". In Proceedings of IEEE INFOCOM'94, pages 636-646, band Applications". In Proceedings of IEEE INFOCOM'94, pages
Toronto, CA, April 1994. 636-646, Toronto, CA, April 1994.
[9] P. Goyal, H.M. Vin, and H. Chen. "Start-time Fair Queuing: A [9] P. Goyal, H.M. Vin, and H. Chen. "Start-time Fair Queuing: A
Scheduling Algorithm for Integrated Services". In Proceedings of the Scheduling Algorithm for Integrated Services". In Proceedings
ACM-SIGCOMM 96, pages 157-168, Palo Alto, CA, August 1996. of the ACM-SIGCOMM 96, pages 157-168, Palo Alto, CA, August
1996.
[10] V. Jacobson, K. Nichols, K. Poduri, "An Expedited Forwarding [10] Jacobson, V., Nichols, K. and K. Poduri, "An Expedited
PHB", RFC 2598, June 1999 Forwarding PHB", RFC 2598, June 1999.
[11] V. Jacobson, K. Nichols, K. Poduri, "The 'Virtual Wire' Behavior [11] Jacobson, V., Nichols, K. and K. Poduri, "The 'Virtual Wire'
Aggregate," (draft-ietf-diffserv-ba-vw-00.txt), March 2000. Behavior Aggregate", Work in Progress.
[12] M. Shreedhar and G. Varghese. "Efficient Fair Queueing Using [12] M. Shreedhar and G. Varghese. "Efficient Fair Queuing Using
Deficit Round Robin". In Proceedings of SIGCOMM'95, pages 231-243, Deficit Round Robin". In Proceedings of SIGCOMM'95, pages
Boston, MA, September 1995. 231-243, Boston, MA, September 1995.
[13] Le Boudec, J.-Y., Charny, A. "Packet Scale Rate Guarantee for
non-FIFO Nodes", Infocom 2002, New York, June 2002.
Appendix A. Difficulties with the RFC 2598 EF PHB Definition Appendix A. Difficulties with the RFC 2598 EF PHB Definition
The definition of the EF PHB as given in [10] states: The definition of the EF PHB as given in [10] states:
"The EF PHB is defined as a forwarding treatment for a particular "The EF PHB is defined as a forwarding treatment for a particular
diffserv aggregate where the departure rate of the aggregate's diffserv aggregate where the departure rate of the aggregate's
packets from any diffserv node must equal or exceed a configurable packets from any diffserv node must equal or exceed a configurable
rate. The EF traffic SHOULD receive this rate independent of the rate. The EF traffic SHOULD receive this rate independent of the
intensity of any other traffic attempting to transit the node. It intensity of any other traffic attempting to transit the node. It
[the EF PHB departure rate] SHOULD average at least the configured [the EF PHB departure rate] SHOULD average at least the configured
rate when measured over any time interval equal to or longer than the rate when measured over any time interval equal to or longer than the
time it takes to send an output link MTU sized packet at the time it takes to send an output link MTU sized packet at the
configured rate." configured rate."
A literal interpretation of the definition would consider the A literal interpretation of the definition would consider the
behaviors given in the next two subsections as non-compliant. The behaviors given in the next two subsections as non-compliant. The
definition also unnecessarily constrains the maximum configurable definition also unnecessarily constrains the maximum configurable
rate of an EF aggregate. rate of an EF aggregate.
A.1 Perfectly-Clocked Forwarding A.1 Perfectly-Clocked Forwarding
Consider the following stream forwarded from a router with EF- Consider the following stream forwarded from a router with EF-
configured rate R=C/2, where C is the output line rate. In the configured rate R=C/2, where C is the output line rate. In the
illustration, E is an MTU-sized EF packet while x is a non-EF packet illustration, E is an MTU-sized EF packet while x is a non-EF packet
or unused capacity, also of size MTU. or unused capacity, also of size MTU.
E x E x E x E x E x E x... E x E x E x E x E x E x...
|-----| |-----|
The interval between the vertical bars is 3*MTU/C, which is greater The interval between the vertical bars is 3*MTU/C, which is greater
than MTU/(C/2), and so is subject to the EF PHB definition. During than MTU/(C/2), and so is subject to the EF PHB definition. During
this interval, 3*MTU/2 bits of the EF aggregate should be forwarded, this interval, 3*MTU/2 bits of the EF aggregate should be forwarded,
but only MTU bits are forwarded. Therefore, while this forwarding but only MTU bits are forwarded. Therefore, while this forwarding
pattern should be considered compliant under any reasonable pattern should be considered compliant under any reasonable
interpretation of the EF PHB, it actually does not formally comply interpretation of the EF PHB, it actually does not formally comply
with the definition of RFC 2598. with the definition of RFC 2598.
Note that this forwarding pattern can occur in any work-conserving Note that this forwarding pattern can occur in any work-conserving
scheduler in an ideal output-buffered architecture where EF packets scheduler in an ideal output-buffered architecture where EF packets
arrive in a perfectly clocked manner according to the above pattern arrive in a perfectly clocked manner according to the above pattern
and are forwarded according to exactly the same pattern in the and are forwarded according to exactly the same pattern in the
absence of any non-EF traffic. absence of any non-EF traffic.
Trivial as this example may be, it reveals the lack of mathematical Trivial as this example may be, it reveals the lack of mathematical
precision in the formal definition. The fact that no work-conserving precision in the formal definition. The fact that no work-conserving
scheduler can formally comply with the definition is unfortunate, and scheduler can formally comply with the definition is unfortunate, and
appears to warrant some changes to the definition that would correct appears to warrant some changes to the definition that would correct
this problem. this problem.
The underlying reason for the problem described here is quite simple The underlying reason for the problem described here is quite simple
- one can only expect that the EF aggregate is served at configured - one can only expect that the EF aggregate is served at configured
rate in some interval where there is enough backlog of EF packets to rate in some interval where there is enough backlog of EF packets to
sustain that rate. In the example above the packets come in exactly sustain that rate. In the example above the packets come in exactly
at the rate at which they are served, and so there is no persistent at the rate at which they are served, and so there is no persistent
backlog. Certainly, if the input rate is even smaller than the backlog. Certainly, if the input rate is even smaller than the
configured rate of the EF aggregate, there will be no backlog as configured rate of the EF aggregate, there will be no backlog as
well, and a similar formal difficulty will occur. well, and a similar formal difficulty will occur.
A seemingly simple solution to this difficulty might be to require A seemingly simple solution to this difficulty might be to require
that the EF aggregate is served at its configured rate only when the that the EF aggregate is served at its configured rate only when the
queue is backlogged. However, as we show in the remainder of this queue is backlogged. However, as we show in the remainder of this
section, this solution does not suffice. section, this solution does not suffice.
A.2 Router Internal Delay A.2 Router Internal Delay
We now argue that the example considered in the previous section is We now argue that the example considered in the previous section is
not as trivial as it may seem at first glance. not as trivial as it may seem at first glance.
Consider a router with EF configured rate R = C/2 as in the previous Consider a router with EF configured rate R = C/2 as in the previous
example, but with an internal delay of 3T (where T = MTU/C) between example, but with an internal delay of 3T (where T = MTU/C) between
the time that a packet arrives at the router and the time that it is the time that a packet arrives at the router and the time that it is
first eligible for forwarding at the output link. Such things as first eligible for forwarding at the output link. Such things as
header processing, route look-up, and delay in switching through a header processing, route look-up, and delay in switching through a
multi-layer fabric could cause this delay. Now suppose that EF multi-layer fabric could cause this delay. Now suppose that EF
traffic arrives regularly at a rate of (2/3)R = C/3. The router will traffic arrives regularly at a rate of (2/3)R = C/3. The router will
perform as shown below. perform as shown below.
EF Packet Number 1 2 3 4 5 6 ... EF Packet Number 1 2 3 4 5 6 ...
Arrival (at router) 0 3T 6T 9T 12T 15T ... Arrival (at router) 0 3T 6T 9T 12T 15T ...
Arrival (at scheduler) 3T 6T 9T 12T 15T 18T ... Arrival (at scheduler) 3T 6T 9T 12T 15T 18T ...
Departure 4T 7T 10T 13T 16T 19T ... Departure 4T 7T 10T 13T 16T 19T ...
Again, the output does not satisfy the RFC 2598 definition of EF PHB. Again, the output does not satisfy the RFC 2598 definition of EF PHB.
As in the previous example, the underlying reason for this problem is As in the previous example, the underlying reason for this problem is
that the scheduler cannot forward EF traffic faster than it arrives. that the scheduler cannot forward EF traffic faster than it arrives.
However, it can be easily seen that the existence of internal delay However, it can be easily seen that the existence of internal delay
causes one packet to be inside the router at all times. An external causes one packet to be inside the router at all times. An external
observer will rightfully conclude that the number of EF packets that observer will rightfully conclude that the number of EF packets that
arrived to the router is always at least one greater than the number arrived to the router is always at least one greater than the number
of EF packets that left the router, and therefore the EF aggregate is of EF packets that left the router, and therefore the EF aggregate is
constantly backlogged. However, while the EF aggregate is constantly backlogged. However, while the EF aggregate is
continuously backlogged, the observed output rate is nevertheless continuously backlogged, the observed output rate is nevertheless
strictly less that the configured rate. strictly less that the configured rate.
This example indicates that the simple addition of the condition that This example indicates that the simple addition of the condition that
EF aggregate must receive its configured rate only when the EF EF aggregate must receive its configured rate only when the EF
aggregate is backlogged does not suffice in this case. aggregate is backlogged does not suffice in this case.
Yet, the problem described here is of fundamental importance in Yet, the problem described here is of fundamental importance in
practice. Most routers have a certain amount of internal delay. A practice. Most routers have a certain amount of internal delay. A
vendor declaring EF compliance is not expected to simultaneously vendor declaring EF compliance is not expected to simultaneously
declare the details of the internals of the router. Therefore, the declare the details of the internals of the router. Therefore, the
existence of internal delay may cause a perfectly reasonable EF existence of internal delay may cause a perfectly reasonable EF
implementation to display seemingly non-conformant behavior, which is implementation to display seemingly non-conformant behavior, which is
clearly undesirable. clearly undesirable.
A.3 Maximum Configurable Rate and Provisioning Efficiency A.3 Maximum Configurable Rate and Provisioning Efficiency
It is well understood that with any non-preemptive scheduler, the It is well understood that with any non-preemptive scheduler, the
compliant configurable rate for an EF aggregate cannot exceed C/2 RFC-2598-compliant configurable rate for an EF aggregate cannot
[11]. This is because an MTU-sized EF packet may arrive to an empty exceed C/2 [11]. This is because an MTU-sized EF packet may arrive
queue at time t just as an MTU-sized non-EF packet begins service. to an empty queue at time t just as an MTU-sized non-EF packet begins
The maximum number of EF bits that could be forwarded during the service. The maximum number of EF bits that could be forwarded
interval [t, t + 2*MTU/C] is MTU. But if configured rate R > C/2, during the interval [t, t + 2*MTU/C] is MTU. But if configured rate
then this interval would be of length greater than MTU/R, and more R > C/2, then this interval would be of length greater than MTU/R,
than MTU EF bits would have to be served during this interval for the and more than MTU EF bits would have to be served during this
router to be compliant. Thus, R must be no greater than C/2. interval for the router to be compliant. Thus, R must be no greater
than C/2.
It can be shown that for schedulers other than PQ, such as various It can be shown that for schedulers other than PQ, such as various
implementations of WFQ, the maximum compliant configured rate may be implementations of WFQ, the maximum compliant configured rate may be
much smaller than 50%. For example, for SCFQ [8] the maximum much smaller than 50%. For example, for SCFQ [8] the maximum
configured rate cannot exceed C/N, where N is the number of queues in configured rate cannot exceed C/N, where N is the number of queues in
the scheduler. For WRR, mentioned as compliant in section 2.2 of RFC the scheduler. For WRR, mentioned as compliant in section 2.2 of RFC
2598, this limitation is even more severe. This is because in these 2598, this limitation is even more severe. This is because in these
schedulers a packet arriving to an empty EF queue may be forced to schedulers a packet arriving to an empty EF queue may be forced to
wait until one packet from each other queue (in the case of SCFQ) or wait until one packet from each other queue (in the case of SCFQ) or
until several packets from each other queue (in the case of WRR) are until several packets from each other queue (in the case of WRR) are
served before it will finally be forwarded. served before it will finally be forwarded.
While it is frequently assumed that the configured rate of EF traffic While it is frequently assumed that the configured rate of EF traffic
will be substantially smaller than the link bandwidth, the will be substantially smaller than the link bandwidth, the
requirement that this rate should never exceed 50% of the link requirement that this rate should never exceed 50% of the link
bandwidth appears unnecessarily limiting. For example, in a fully bandwidth appears unnecessarily limiting. For example, in a fully
connected mesh network, where any flow traverses a single link on its connected mesh network, where any flow traverses a single link on its
way from source to its destination there seems no compelling reason way from source to its destination there seems no compelling reason
to limit the amount of EF traffic to 50% (or an even smaller to limit the amount of EF traffic to 50% (or an even smaller
percentage for some schedulers) of the link bandwidth. percentage for some schedulers) of the link bandwidth.
Another, perhaps even more striking example is the fact that even a Another, perhaps even more striking example is the fact that even a
TDM circuit with dedicated slots cannot be configured to forward EF TDM circuit with dedicated slots cannot be configured to forward EF
packets at more than 50% of the link speed without violating RFC 2598 packets at more than 50% of the link speed without violating RFC 2598
(unless the entire link is configured for EF). If the configured rate (unless the entire link is configured for EF). If the configured
of EF traffic is greater than 50% (but less than the link speed), rate of EF traffic is greater than 50% (but less than the link
there will always exist an interval longer than MTU/R in which less speed), there will always exist an interval longer than MTU/R in
than the configured rate is achieved. For example, suppose the which less than the configured rate is achieved. For example,
configured rate of the EF aggregate is 2C/3. Then the forwarding suppose the configured rate of the EF aggregate is 2C/3. Then the
pattern of the TDM circuit might be forwarding pattern of the TDM circuit might be
E E x E E x E E x ... E E x E E x E E x ...
|---| |---|
where only one packet is served in the marked interval of length 2T = where only one packet is served in the marked interval of length 2T =
2MTU/C. But at least 4/3 MTU would have to be served during this 2MTU/C. But at least 4/3 MTU would have to be served during this
interval by a router in compliance with the definition in RFC 2598. interval by a router in compliance with the definition in RFC 2598.
The fact that even a TDM line cannot be booked over 50% by EF traffic The fact that even a TDM line cannot be booked over 50% by EF traffic
indicates that the restriction is artificial and unnecessary. indicates that the restriction is artificial and unnecessary.
A.4 The Non-trivial Nature of the Difficulties A.4 The Non-trivial Nature of the Difficulties
One possibility to correct the problems discussed in the previous One possibility to correct the problems discussed in the previous
sections might be to attempt to clarify the definition of the sections might be to attempt to clarify the definition of the
intervals to which the definition applied or by averaging over intervals to which the definition applied or by averaging over
multiple intervals. However, an attempt to do so meets with multiple intervals. However, an attempt to do so meets with
considerable analytical and implementation difficulties. For example, considerable analytical and implementation difficulties. For
attempting to align interval start times with some epochs of the example, attempting to align interval start times with some epochs of
forwarded stream appears to require a certain degree of global clock the forwarded stream appears to require a certain degree of global
synchronization and is fraught with the risk of misinterpretation and clock synchronization and is fraught with the risk of
mistake in practice. misinterpretation and mistake in practice.
Another approach might be to allow averaging of the rates over some Another approach might be to allow averaging of the rates over some
larger time scale. However, it is unclear exactly what finite time larger time scale. However, it is unclear exactly what finite time
scale would suffice in all reasonable cases. Furthermore, this scale would suffice in all reasonable cases. Furthermore, this
approach would compromise the notion of very short-term time scale approach would compromise the notion of very short-term time scale
guarantees that are the essence of EF PHB. guarantees that are the essence of EF PHB.
We also explored a combination of two simple fixes. The first is the We also explored a combination of two simple fixes. The first is the
addition of the condition that the only intervals subject to the addition of the condition that the only intervals subject to the
definition are those that fall inside a period during which the EF definition are those that fall inside a period during which the EF
aggregate is continuously backlogged in the router (i.e., when an EF aggregate is continuously backlogged in the router (i.e., when an EF
packet is in the router). The second is the addition of an error packet is in the router). The second is the addition of an error
(latency) term that could serve as a figure-of-merit in the (latency) term that could serve as a figure-of-merit in the
advertising of EF services. advertising of EF services.
With the addition of these two changes the candidate definition With the addition of these two changes the candidate definition
becomes as follows: becomes as follows:
In any interval of time (t1, t2) in which EF traffic is continuously In any interval of time (t1, t2) in which EF traffic is continuously
backlogged, at least R(t2 - t1 - E) bits of EF traffic must be backlogged, at least R(t2 - t1 - E) bits of EF traffic must be
served, where R is the configured rate for the EF aggregate and E is served, where R is the configured rate for the EF aggregate and E is
an implementation-specific latency term. an implementation-specific latency term.
The "continuously backlogged" condition eliminates the insufficient- The "continuously backlogged" condition eliminates the insufficient-
packets-to-forward difficulty while the addition of the latency term packets-to-forward difficulty while the addition of the latency term
of size MTU/C resolves the perfectly-clocked forwarding example of size MTU/C resolves the perfectly-clocked forwarding example
(section 1.2.1), and also removes the limitation on EF configured (section A.1), and also removes the limitation on EF configured rate.
rate.
However, neither fix (nor the two of them together) resolves the However, neither fix (nor the two of them together) resolves the
example of section 1.2.2. To see this, recall that in the example of example of section A.2. To see this, recall that in the example of
section 1.2.2 the EF aggregate is continuously backlogged, but the section A.2 the EF aggregate is continuously backlogged, but the
service rate of the EF aggregate is consistently smaller than the service rate of the EF aggregate is consistently smaller than the
configured rate, and therefore no finite latency term will suffice to configured rate, and therefore no finite latency term will suffice to
bring the example into conformance. bring the example into conformance.
Appendix B. Alternative Characterization of Packet Scale Rate Guarantee Appendix B. Alternative Characterization of Packet Scale Rate Guarantee
The proofs of several bounds in this document can be found in The proofs of several bounds in this document can be found in [13].
http://ica1www.epfl.ch/PS_files/proofsEFJuli2001.pdf. These proofs These proofs use an algebraic characterization of the aggregate
use an algebraic characterization of the aggregate definition given definition given by (eq_1), (eq_2), and packet identity aware
by (eq_1), (eq-2), and packet identity aware definition given by (eq definition given by (eq_3), (eq_4). Since this characterization is
3), (eq 4). Since this characterization is of interest on its own, of interest on its own, we present it in this section.
we present it in this section.
Theorem B1. Characterization of the aggregate definition without Theorem B1. Characterization of the aggregate definition without
f_n. f_n.
Consider a system where packets are numbered 1, 2, ... in order of Consider a system where packets are numbered 1, 2, ... in order of
arrival. As in the aggregate definition, call a_n the n-th arrival arrival. As in the aggregate definition, call a_n the n-th arrival
time, d_n - the n-th departure time, and l_n the size of the n-th time, d_n - the n-th departure time, and l_n the size of the n-th
packet to depart. Define by convention d_0=0. The aggregate packet to depart. Define by convention d_0=0. The aggregate
definition with rate R and latency E_a is equivalent to saying that definition with rate R and latency E_a is equivalent to saying that
for all n and all 0<=j<= n-1: for all n and all 0<=j<= n-1:
d_n <= E_a + d_j + (l_(j+1) + ... + l_n)/R (eq_b1) d_n <= E_a + d_j + (l_(j+1) + ... + l_n)/R (eq_b1)
or or
there exists some j+1 <= k <= n such that there exists some j+1 <= k <= n such that
d_n <= E_a + a_k + (l_k + ... + l_n)/R (eq_b2) d_n <= E_a + a_k + (l_k + ... + l_n)/R (eq_b2)
Theorem B2. Characterization of packet-identity-aware definition Theorem B2. Characterization of packet-identity-aware definition
without F_n. without F_n.
Consider a system where packets are numbered 1, 2, ... in order of Consider a system where packets are numbered 1, 2, ... in order of
arrival. As in the packet-identity-aware definition, call A_n, D_n arrival. As in the packet-identity-aware definition, call A_n, D_n
the arrival and departure times for the n-th packet, and L_n the size the arrival and departure times for the n-th packet, and L_n the size
of this packet. Define by convention D_0=0. The packet identity aware of this packet. Define by convention D_0=0. The packet identity
definition with rate R and latency E_p is equivalent to saying that aware definition with rate R and latency E_p is equivalent to saying
for all n and all 0<=j<= n-1: that for all n and all 0<=j<= n-1:
D_n <= E_p + D_j + (L_{j+1} + ... + L_n)/R (eq_b3) D_n <= E_p + D_j + (L_{j+1} + ... + L_n)/R (eq_b3)
or or
there exists some j+1 <= k <= n such that there exists some j+1 <= k <= n such that
D_n <= E_p + A_k + (L_k + ... + L_n)/R (eq_b4) D_n <= E_p + A_k + (L_k + ... + L_n)/R (eq_b4)
For the proofs of both Theorems, see For the proofs of both Theorems, see [13].
http://ica1www.epfl.ch/PS_files/proofsEFJuli2001.pdf
Authors' addresses Acknowledgements
This document could not have been written without Fred Baker, Bruce
Davie and Dimitrios Stiliadis. Their time, support and insightful
comments were invaluable.
Authors' Addresses
Anna Charny Anna Charny
Cisco Systems Cisco Systems
300 Apollo Drive 300 Apollo Drive
Chelmsford, MA 01824 Chelmsford, MA 01824
E-mail: acharny@cisco.com EMail: acharny@cisco.com
Fred Baker
Cisco Systems
170 West Tasman Dr.
San Jose, CA 95134
E-mail: fred@cisco.com
Jon Bennett Jon Bennett
RiverDelta Networks Motorola
3 Highwood Drive East 3 Highwood Drive East
Tewksbury, MA 01876 Tewksbury, MA 01876
E-mail: jcrb@riverdelta.com EMail: jcrb@motorola.com
Kent Benson Kent Benson
Tellabs Research Center Tellabs Research Center
3740 Edison Lake Parkway #101 3740 Edison Lake Parkway #101
Mishawaka, IN 46545 Mishawaka, IN 46545
E-mail: Kent.Benson@tellabs.com EMail: Kent.Benson@tellabs.com
Jean-Yves Le Boudec Jean-Yves Le Boudec
ICA-EPFL, INN ICA-EPFL, INN
Ecublens, CH-1015 Ecublens, CH-1015
Lausanne-EPFL, Switzerland Lausanne-EPFL, Switzerland
E-mail: leboudec@epfl.ch EMail: jean-yves.leboudec@epfl.ch
Angela Chiu Angela Chiu
AT&T Labs Celion Networks
100 Schulz Dr. Rm 4-204 1 Sheila Drive, Suite 2
Red Bank, NJ 07701 Tinton Falls, NJ 07724
E-mail: alchiu@att.com
EMail: angela.chiu@celion.com
Bill Courtney Bill Courtney
TRW TRW
Bldg. 201/3702 Bldg. 201/3702
One Space Park One Space Park
Redondo Beach, CA 90278 Redondo Beach, CA 90278
E-mail: bill.courtney@trw.com EMail: bill.courtney@trw.com
Shahram Davari Shahram Davari
PMC-Sierra Inc PMC-Sierra Inc
411 Legget Drive 411 Legget Drive
Ottawa, ON K2K 3C9, Canada Ottawa, ON K2K 3C9, Canada
E-mail: shahram_davari@pmc-sierra.com EMail: shahram_davari@pmc-sierra.com
Bruce Davie
Cisco Systems, Inc.
300 Apollo Drive
Chelmsford, MA, 01824
E-mail: bsd@cisco.com
Victor Firoiu Victor Firoiu
Nortel Networks Nortel Networks
600 Tech Park 600 Tech Park
Billerica, MA 01821 Billerica, MA 01821
E-mail: vfirou@nortelnetworks.com EMail: vfiroiu@nortelnetworks.com
Charles Kalmanek Charles Kalmanek
AT&T Labs-Research AT&T Labs-Research
180 Park Avenue, Room A113, 180 Park Avenue, Room A113,
Florham Park NJ Florham Park NJ
E-mail: crk@research.att.com. EMail: crk@research.att.com
K.K. Ramakrishnan K.K. Ramakrishnan
TeraOptic Networks, Inc. TeraOptic Networks, Inc.
686 W. Maude Ave 686 W. Maude Ave
Sunnyvale, CA 94086 Sunnyvale, CA 94086
E-mail: kk@teraoptic.com EMail: kk@teraoptic.com
Dimitrios Stiliadis
Lucent Technologies
1380 Rodick Road
Markham, Ontario, L3R-4G5, Canada
E-mail: stiliadi@bell-labs.com
Full Copyright Full Copyright Statement
Copyright (C) The Internet Society 2001. All Rights Reserved. Copyright (C) The Internet Society (2001). All Rights Reserved.
This document and translations of it may be copied and furnished to This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose ofdeveloping Internet organizations, except as needed for the purpose of
Internet standards in which case the procedures for copyrights developing Internet standards in which case the procedures for
defined in the Internet Standards process must be followed, or as copyrights defined in the Internet Standards process must be
required to translate it into languages other than English. followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns. revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement
Funding for the RFC Editor function is currently provided by the
Internet Society.
 End of changes. 145 change blocks. 
393 lines changed or deleted 375 lines changed or added

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