Internet Engineering Task Force					Van Jacobson
Differentiated Services Working Group 	                                LBNL
Internet Draft 				Kathleen Nichols
Internet Draft							Cisco Systems
Expires February, May, 1999						Kedarnath Poduri
					                        Bay Networks
								August,
							        November, 1998

			An Expedited Forwarding PHB
		     <draft-ietf-diffserv-phb-ef-00.txt>
		    <draft-ietf-diffserv-phb-ef-01.txt>

Status of this Memo

This document is a submission to the IETF Differentiated Services
(DiffServ) Working Group.  Comments are solicited and should be
addressed to the working group mailing list or to the editor.

This document is an Internet-Draft.  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 draft documents are valid for a maximum of six months
and may be updated, replaced, or obsolete 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."

To learn view the current status entire list of any Internet-Draft, current Internet-Drafts, please check the
"1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), ftp.nordu.net (Northern Europe),
ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific Rim),
ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast).

Distribution of this memo is unlimited.

Abstract

The definition of PHBs (per-hop forwarding behaviors) is a critical part
of the work of the Diffserv Working Group.  This document describes a
PHB called Expedited Forwarding.  We show the generality of this PHB by
noting that it can be produced by more than one mechanism and give an
example of its use to produce at least one service, a Virtual Leased
Line.  A recommended codepoint for this PHB is given.

A pdf version of this document is available at
ftp://ftp.ee.lbl.gov/papers/ef_phb.pdf

1. Introduction

Network nodes that implement the differentiated services enhancements to
IP use a codepoint in the IP header to select a per-hop behavior (PHB)
as the specific forwarding treatment for that packet [HEADER, ARCH].
This draft describes a particular PHB called expedited forwarding (EF).
The EF PHB can be used to build a low loss, low latency, low jitter,
assured bandwidth, end-to-end service through DS domains.  Such a
service appears to the endpoints like a point-to-point connection or a
"virtual leased line".  This service has also been described as Premium
service [2BIT].

Loss, latency and jitter are all due to the queues traffic experiences
while transiting the network.  Therefore providing low loss, latency and
jitter for some traffic aggregate means ensuring that the aggregate sees
no (or very small) queues.  Queues arise when (short term) (short-term) traffic
arrival rate exceeds departure rate at some node.  Thus a service that
ensures no queues for some aggregate is equivalent to bounding rates
such that, at every transit node, the aggregate's max arrival rate is
less than that aggregate's min departure rate.

Creating such a service has two parts:

1) configuring Configuring nodes so that the aggregate has a well-defined minimum
   departure rate.  (`Well-defined' means independent of the dynamic state
   of the node.  In particular, independent of the intensity of other
   traffic at the node.)

2) conditioning Conditioning the aggregate (via policing and shaping) so that it's
   arrival rate at any node is always less than that node's configured
   minimum departure rate.  The EF PHB provides the first part of the
   service.  The network boundary traffic conditioners described in [ARCH]
   provide the second part.

The EF PHB is not a mandatory part of the Differentiated Services
architecture.  I.e., a node is not required to implement the EF PHB in
order to be considered DS-compliant.  However, when a DS-compliant node
claims to implement the EF PHB, the implementation must conform to the
specification given in this document.

The next sections describe the EF PHB in detail and give examples of how
it might be implemented.  The keywords "MUST", "MUST NOT", "REQUIRED",
"SHOULD", "SHOULD NOT", and "MAY" that appear in this document are to be
interpreted as described in [Bradner97].

2. Description of EF per-hop behavior

2.1 Description

The EF PHB is defined as a forwarding treatment for a particular
diffserv aggregate where the departure rate of the aggregate's packets
from any diffserv node must equal or exceed a configurable rate.  The EF
traffic should receive this rate independent of the intensity of any
other traffic attempting to transit the node.  It should average at
least the configured rate when measured over any time interval equal to
or longer than a packet time at the configured rate.  (Behavior at time
scales shorter than a packet time at the configured rate is deliberately
not specified.) The configured minimum rate must be settable by a
network administrator (using whatever mechanism the node supports for
non-volatile configuration).

If the EF PHB is implemented by a mechanism that allows unlimited
preemption of other traffic (e.g., a priority queue), the implementation
must include some means to limit the damage EF traffic could inflict on
other traffic (e.g., a token bucket rate limiter).  This maximum EF rate
must be settable by a network administrator (using whatever mechanism
the node supports for non-volatile configuration).  The minimum and
maximum rates can be the same and configured by a single parameter.

The Appendix describes how this PHB can be used to construct end-to-end
services.

2.2 Example Mechanisms to Implement the EF PHB

Several types of queue scheduling mechanisms may be employed to deliver
the forwarding behavior described in section 2.1 and thus implement the
EF PHB.  A simple priority queue will give the appropriate behavior as
long as there is no higher priority queue the that could preempt the EF for
more than a packet time at the configured rate.  (This could be
accomplished by having a rate policer such as a token bucket associated
with each priority queue to bound how much the queue can starve other
traffic.)

It's also possible to use a single queue in a group of queues serviced
by a weighted round robin scheduler where the share of the output
bandwidth assigned to the EF queue is equal to the configured rate.
This could be implemented, for example, using one PHB of a Class
Selector Compliant set of PHBs [HEADER].

Another possible implementation is a CBQ [CBQ] scheduler that gives the
EF queue priority up to the configured rate.

All of these mechanisms give the basic properties required for the EF
PHB though different choices result in differences in auxiliary behavior
such as jitter seen by individual microflows.  See Appendix A.3 for
simulations that quantify some of these differences.

2.3 Recommended codepoint for this PHB

Codepoint 101100 101110 is recommended for the EF PHB.

2.4 Mutability

Packets marked for EF PHB may be remarked at a DS domain boundary to
other codepoints that satisfy the EF PHB only.  Packets marked for EF
PHBs SHOULD NOT be demoted or promoted to another PHB by a DS domain.

2.5 Tunneling

When EF packets are tunneled, the tunneling packets must be marked as
EF.

2.6 Interaction with other PHBs

Other PHBs and PHB groups may be deployed in the same DS node or domain
with the EF PHB as long as the requirement of section 2.1 is met.

3. Security Considerations

To protect itself against denial of service attacks, the edge of a DS
domain MUST strictly police all EF marked packets to a rate negotiated
with the adjacent upstream domain.  (This rate must be <= the EF PHB
configured rate.) Packets in excess of the negotiated rate MUST be
dropped.  If two adjacent domains have not negotiated an EF rate, the
downstream domain MUST use 0 as the rate (i.e., drop all EF marked
packets).

Since the end-to-end premium service constructed from the EF PHB
requires that the upstream domain police and shape EF marked traffic to
meet the rate negotiated with the downstream domain, the downstream
domain's policer should never have to drop packets.  Thus these drops
should be noted (e.g., via SNMP traps) as possible security violations
or serious misconfiguration.  Similarly, since the aggregate EF traffic
rate is constrained at every interior node, the EF queue should never
overflow so if it does the drops should be noted as possible attacks or
serious misconfiguration.

4. References

[Bradner97] S. Bradner, "Key words for use in RFCs to Indicate Requirement
Levels", Internet RFC 2119, March 1997.

[HEADER] K. Nichols, S. Blake, F. Baker, and D. Black, "Definition of the
Differentiated  Services Field (DS Field) in the IPv4 and IPv6 Headers",
<draft-ietf-diffserv-header-02.txt>, August 1998.

[ARCH] D. Black, S. Blake, M. Carlson, E. Davies, Z. Wang, and W. Weiss,
"An Architecture  for Differentiated Services", Internet Draft <draft-ietf-diffserv-arch-01.txt>,
<draft-ietf-diffserv-arch-04.txt>, August 1998.

[2BIT] K. Nichols, V. Jacobson, and L. Zhang, "A Two-bit Differentiated
Services Architecture for the Internet", Internet Draft
<draft-nichols-diff-svc-arch-00.txt>, November 1997, ftp://ftp.ee.lbl.gov/papers/dsarch.pdf.
ftp://ftp.ee.lbl.gov/papers/dsarch.pdf

[CBQ] S. Floyd and V. Jacobson, "Link-sharing and Resource Management
Models for Packet Networks", IEEE/ACM Transactions on Networking,
Vol. 3 no. 4, pp. 365-386, August 1995.

[IW] K. Poduri and K. Nichols, "Simulation Studies of Increased Initial
TCP Window Size", <draft-ietf-tcpimpl-poduri-02.txt>,
	    August, August 1998.

[LCN] K. Nichols, "Improving Network Simulation with Feedback", to
	    appear in proceedings Proceedings
of LCN '98, October, 1998 1998.

5. Authors' Addresses

Van Jacobson
Lawrence Berkeley National Laboratory
M/S 50B-2239
One Cyclotron Road
Berkeley,
Cisco Systems, Inc
170 W. Tasman Drive
San Jose, CA 94720
van@ee.lbl.gov 95134-1706
van@cisco.com

Kathleen Nichols
Bay Networks, Inc.
4401 Great America Parkway
Santa Clara,
Cisco Systems, Inc
170 W. Tasman Drive
San Jose, CA 95052-8185
knichols@baynetworks.com
+1 408-495-3252 95134-1706
kmn@cisco.com

Kedarnath Poduri
Bay Networks, Inc.
Bay Networks, Inc.
4401 Great America Parkway
Santa Clara, CA 95052-8185
kpoduri@baynetworks.com

Appendix.

Appendix A: Example use of and experiences with the EF PHB

A.1 Virtual Leased Line Service

A VLL Service, also known as Premium service [2BIT], is quantified by a
peak bandwidth.

A.2 Experiences with its use in ESNET

A prototype of the VLL service has been deployed on DOE's ESNet
backbone.  This uses weighted-round-robin queuing features of cisco 7xxx Cisco 75xx
series routers to implement the EF PHB.  The early tests have been very
successful (details are available in ftp://ftp.ee.lbl.gov/talks/vj-doeqos.pdf
and ftp://ftp.ee.lbl.gov/talks/vj-i2qos-may98.pdf) and work is in progress to make the service available on a
routine production basis. basis (see ftp://ftp.ee.lbl.gov/talks/vj-doeqos.pdf
and ftp://ftp.ee.lbl.gov/talks/vj-i2qos-may98.pdf for details).

A.3 Simulation Results

A.3.1 Jitter variation

In section 2.2, we pointed out that a number of mechanisms may might be used
to implement the EF PHB.  The simplest is a priority queue (PQ) where
the arrival rate of the queue is strictly less than its departure service rate.
As jitter comes from the queuing delay along the path, a feature of this
implementation is that EF-marked microflows will see very little jitter
at their subscribed rate if all DS nodes along the path use this
implementation since packets spend little time in queues. This low-jitter behavior is  The EF PHB
does not have an explicit jitter requirement, but it is clear from the
definition that the expected jitter in packets that use a requirement
of service based
on the EF PHB, PHB will be less than for best-effort style packet delivery.
A PQ implementation for the EF PHB should give the smallest jitter, but
we want used simulation to explore how other implementations, in this
case WRR, particularly
weighted round-robin (WRR), compare in jitter. We've compared  PQ and WRR because these seemed to be
the best and worst cases, respectively, for jitter. jitter and we wanted to
supply some rough guidelines for implementers choosing to use WRR.

Our basic simulation model is implemented in ns-2 as described in [IW] and
[LCN].  We've made some further modifications to ns-2, using the CBQ
modules included with ns-2 as a basis to implement priority queuing and
WRR.

We experimented with a six-hop  Our topology has six hops with decreasing bandwidth in the
direction of a single 1.5 Mbps bottleneck link. For our EF-marked packets,
we set up sources to  Sources produce
EF-marked packets at a constant an average bit rate equal to their subscribed
packet rate.  Packets are produced with a variation of +/-10% of from the
interpacket spacing at the subscribed packet rate.  The individual
source rates were picked to add up to 30% of the bottleneck link or 450
Kbps.  A mixture of other kinds of traffic, FTPs and HTTPs, is used to
fill the link. We report jitter as the added delay normalized by the time to send a  EF packet at the subscribed peak rate. The pdf version of this document
contains graphs of percentile vs jitter and sources produce either all 160 byte packets or
all 1500 byte packets.  Though we include text tables that
report focus on the 95th percentile from each statistics of the scenarios. We used different
packet sizes for the EF-marked packets in our simulations, but always used
the same packet flows with
one size for of packet, all EF-marked packets in any particular
simulation. We report percentile of packets seeing less than a particular
normalized packet size in jitter.

We will consider the implementation experiments used a mixture of short
packet EF sources and long packet EF sources so the EF PHB with a priority queue
(PQ) as queues had a kind mix
of baseline or "ideal" case. To summarize the results we've
seen for PQ jitter, jitter is most strongly dependent on both packet size. For
1500 byte packets, all lengths.

We used as the jitter is less than 0.5 packet times. For 160 byte
packets, 95% definition the absolute value of packet jitter is less than 3.5 packet the difference
between the arrival times with most of two adjacent packets
having less than one packet's worth minus their departure
times, |(aj-ai) - (dj-di)|.  For the target flow of jitter. each experiment, we
record the median, 90th and 95th percentile values of jitter (in
milliseconds) in a table.  The PQ results will be shown
with pdf version of this document contains
graphs of the WRR results below.

Next we jitter percentiles.

We explored the jitter behavior for WRR implementations of the EF PHB.
What we
We wanted to explore was see how different the jitter behavior is from that of PQ implementations. Major features that can affect jitter are packet
size, number of queues for
and to examine the effects of different choices of WRR scheduler, queue weight and
number of queues on jitter.  To this end, we define the amount by which
service-to-arrival rate ratio as the
guaranteed minimum service WRR rate of the an EF queue exceeds (or the
queue's minimum share of the output link) times the output link
bandwidth divided by the peak arrival rate to the EF queue. We have not yet systematically explored effects of
hop count, EF allocations of more or less than 30% of EF-marked packets at a
queue.  If the link bandwidth,
or more complex topologies. However, this information WRR weight is simply chosen to guide
those who are interested in a low jitter implementation exactly balance arrival and is
departure rates, results will not required
for implementing be stable.  Thus the minimum ratio of
service rate to arrival rate used here is 1.03 which, in our
simulations, means that the EF PHB with WRR. queue gets a weight of 31% of the output
links.  In our WRR simulations, we kept the link full with other traffic
as described above, splitting the non-EF-marked traffic among the non-EF
queues. If the WRR weight is chosen to exactly balance arrival and
departure rates, our results will not be stable except for the simplest
cases, so we always overallocate by a minimum of 1% of the output link
bandwidth or, in this case, 3%

Our first set of experiments uses the peak arrival rate minimal service-to-arrival ratio
of EF-marked
packets. We recommend at least this overallocation to implementors. In
figure 1 1.06 and table 1, we show results from varying vary the number of individual microflows composing the EF
aggregate of 450 Kbps. In this case
all EF packets are 1500 bytes and the EF queue gets a weight of 31% of the
output links. The leftmost curve shows the results for from 2 to 36.  We compare these WRR implementations to a PQ
implementation with 24 flows.
Note that the maximum jitter  First, we examine a microflow at a
subscribed rate of 3.2 packets occurs only for 36 flows, 56 Kbps sending 1500 byte packets, then one at the
same rate but sending 160 byte packets.  Table 1 shows the 50th, 90th
and 95th percentile of all scenarios is less than 1 packet of jitter. jitter in milliseconds.  Figure 2 and table 1 shows plots the results when 1500
byte flows and figure 2 the 160 byte flows.  Note that a packet-time for
a 1500 byte packet size of 160 bytes at 56 Kbps is used.

Table 1: Variation in 214 ms, for a 160 byte packet 23 ms.
Thus the jitter with  number of for the large packets rarely exceeds half a subscribed
rate packet-time, though most jitters for the small packets are at least
one subscribed rate packet-time.  Keep in mind that the EF flows

--------------------------------------------------------------
Num aggregate is
composed of mixtures of small and large packets in both cases, so the
short packets can still queue behind long packets in the EF flows	   	Jitter 		     Jitter
		   (95th percentile     (95th percentile
		   1500 Byte Packets)	160 Byte Packets)
-------------------------------------------------------------- queue.
Also, the service-to-arrival ratio used here is the minimum possible to
implement the EF PHB.  PQ (24)			0.07			0.5

2			0.6			6.6

4			0.4			3.9

8			0.3			1.8

24			0.6			2.1

-------------------------------------------------------------- gives a very low jitter.

(see pdf form of document for all tables)

Next we look at the effects of overallocating increasing the link share, that is
giving a minimum service rate service-to-arrival ratio
to see if it reduces jitter.  This means that exceeds EF packets are expected to
remain enqueued for less time, though the peak arrival rate by various
amounts. (Of course, with WRR, that amount of bandwidth is still available
for all other
packets.) We fixed queues remains the same.  In this set of experiments, the
number of flows composing the aggregate was fixed at eight and the total
number of queues at five (four non-EF queues). In figure 3 we report results  Table 2 shows the
results, first for a 1500 byte EF packets flow, then for a 160 byte flow.  Figures
3 plots the 1500 byte results and in figure 4 we show the 160 byte packets. results.  Table
2 gives the 95th percentile values of jitter for the same. Overallocation by up to 100%  Performance
gains leveled off at service-to-arrival ratios of 1.5.  Note that the
higher service-to-arrival ratios still does do not give the same performance
as PQ, but note that most now 90% of packets experience small jitter. In fact, overallocation does not appear to have much
improvement associated with it.

Table 2: Variation in Jitter with Overallocation of BW to EF queues.

--------------------------------------------------------------
% less than a subscribed
packet-time of Over-	   	Jitter 		     Jitter
  Allocation	    (95th percentile     (95th percentile
		   1500 Byte Packets)	160 Byte Packets)
--------------------------------------------------------------

PQ			0.05			0.5

3			0.3			2.2

30			0.2			1.4

50			0.15			1.2

70			0.15			1.2

100			0.15			1.2

--------------------------------------------------------------- jitter, even for the small packets.  We know believe that increasing
implementers should use service-to-arrival ratios of at least 1.5 and
further study may be desired to determine the efficacy of higher ratios.

Increasing the number of queues at the output interfaces can lead to
more variability in the service time for EF packets. packets so we carried out an
experiment varying the number of queues at each output port.  We set fixed
the number of flows in the aggregate to eight and used a 31% weight for the 30% EF allocation
and varied the number of queues at each output interface. 1.03
service-to-arrival ratio.  Results are shown in figure 5 and table 3. Note that most packets experience little jitter.
Figure 5 includes PQ with 8 flows is included as a baseline.

Table 3: Variation in Jitter with Number of Queues at Output Interface

---------------------------------------
Num of Queues	   	Jitter
  	           (95th percentile
		   1500 Byte Packets)
---------------------------------------

PQ			0.05

2			0.2

4			0.3

6			0.3

8			0.35

---------------------------------------

We intend to perform further studies and vary other parameters, but at
present it

It appears that most packet jitter for WRR is low, but low and can be reduced by
overallocating a
proper choice of the EF queue's WRR share of the output link with
respect to its subscribed rate packet jitter can be reduced if desired. rate.  As noted, WRR is probably a "worst
case" while PQ is the best case.  Other possibilities include WFQ or CBQ
with a fixed rate limit for the EF queue, but giving it priority over
other queues.  We expect the latter to have performance nearly identical
with PQ, though future simulations can verify this.  We have not yet
systematically explored effects of hop count, EF allocations of more or
less than 30% of the link bandwidth, or more complex topologies.  Note
that this information is simply to guide implementers.

A.3.2 VLL service

We used simulation to see how well a VLL service built from the EF PHB
behaved, that is, does it look like a "leased line" at the subscribed
rate.  In the simulations of the last section, none of the EF packets
were dropped in the network and the target rate was always achieved for
those CBR sources.  However, we wanted to see if VLL really looks like a
"wire" to a TCP using it.  So we simulated long-lived FTPs using a VLL
service.  Table 4 gives the percentage of each link allocated to EF
traffic (bandwidths are lower on the links with fewer EF microflows),
the subscribed VLL rate, the average rate for the same type of
sender-receiver pair connected by a full duplex dedicated link at the
subscribed rate and the average of the VLL flows for each simulation
(all sender-receiver pairs had the same value).  Losses only occur when
the input shaping buffer overflows but not in the network.  The target
rate is not achieved due to the well-known TCP behavior.