Internet DRAFT - draft-hurley-alternative-best-effort
draft-hurley-alternative-best-effort
INTERNET DRAFT Paul Hurley*
Expires: May 2001 Gianluca Iannaccone+
Mourad Kara^
Diffserv Working Group Jean-Yves Le Boudec*
Patrick Thiran+
Christophe Diot+
*Swiss Federal Institute of Technology, Lausanne
+Sprint Advanced Technology Labs, Burlingame, CA
^University of Leeds, UK
November 2000
The ABE Service
(http://www.abeservice.org)
draft-hurley-alternative-best-effort-01.txt
Status of this Memo
This document is an Internet-Draft and is in full conformance
with all provisions of Section 10 of RFC2026.
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.
A revised version of this draft document will be submitted to the
RFC editor as a Proposed Standard for the Internet Community.
Discussion and suggestions for improvement are requested. This
document will expire before May 24th 2001.
Distribution of this draft is unlimited.
Abstract
ABE (Alternative Best-Effort) is a novel service for IP networks. It
offers applications the choice between receiving a lower end-to-end
delay and receiving more overall throughput. Every best effort
packet is tagged as either green or blue. Green packets receive a
low, bounded queueing delay. To ensure blue packets do not suffer as
a result, green flows receive less throughput during bouts of
congestion.
The unique combination of lower delay with reduced throughput for
Hurley, et al. Expires: May 2001 [page 1]
INTERNET-DRAFT draft-hurley-alternative-best-effort-01.txt November 2000
green makes it different from existing differentiated service
proposals such as expedited forwarding [5] and assured forwarding
[6]. The incentive to choose one or other is based on the nature of
one's traffic and on traffic conditions. Typically, green flows have
real-time deadlines (e.g. interactive audio), while blue traffic
(e.g. bulk data transfer) seeks to minimise overall transfer time.
There is benefit for all traffic in that green traffic achieves
a low delay and blue traffic will receive at least as much throughput
as it would in a flat best-effort network and usually more. Neither
traffic type can be said to be better, thus flat rate pricing may be
maintained, and there is no need for reservations or profiles.
In this document we define the ABE service, discuss its usefulness,
and describe the requirements of router algorithms for ABE support.
We outline one particular router implementation, its implementation
in dummynet, and present initial experimental results of it on a
testbed. Note that ABE is not restricted to any specific
implementation and other implementations such as those based on
per-flow queueing are certainly do-able. As such, we invite
universities and research centres to define other implementations.
1. Introduction
Alternative Best-Effort (ABE) is a new IP service, whose goals are (1)
to provide a low queueing delay service and (2) to operate in best
effort mode, requiring no usage control. The first requirement is for
applications with stringent real time constraints, such as interactive
audio. The second requirement is to maintain the simplicity of the
original Internet. With ABE, it is not required to police how much
traffic uses the low delay capability. The service is designed to
operate equally well in all traffic scenarios.
ABE is designed primarily for rate-adaptive multimedia applications,
applications that adapt to network state. The rate is reduced when
negative feedback is received, and increased with positive
feedback. In today's Internet, feedback is based on packet drop. In
future, binary feedback based on Explicit Congestion Notification
(ECN) [7] will be used. Note that ABE would be even more attractive
with ECN. This document describes the ABE service both from the ECN
and loss-based feedback points of view. The implementation described
uses loss-based feedback.
As is required in the Internet, rate adaptation should be performed
such that the application is TCP-friendly [1], namely, it does not
receive more throughput than a TCP flow would. It has been
established that it is possible to implement adaptive multimedia
applications, which perform across a wide range of network conditions
[8, 9]. In this context, the key idea of ABE is to provide low-delay
at the expense of maybe less throughput. This is fundamental to
ensure ABE requires no usage control.
ABE operates as follows. Best effort IP packets are partitioned into
either low delay packets, called green packets, and other best effort
Hurley, et al. Expires: May 2001 [page 2]
INTERNET-DRAFT draft-hurley-alternative-best-effort-01.txt November 2000
packets, called blue packets. The choice of the terms blue and
green, two primary colours of equal warmth, is to indicate that none
of the two has priority over the other, while green, the colour of
the traffic light signal for go, indicates low queueing delay.
Green packets are given the guarantee of a low bounded delay in
every router. In exchange, if, as now, packet loss is used as the
source of feedback, these packets receive more losses during bouts of
congestion than blue packets. If ECN is used, then green packets are
more likely to be marked with the congestion bit than blue packets.
ABE addresses a different market to existing differentiated or
integrated services. Unlike these services, ABE does not offer any
guarantee, or even indication of guarantee, on throughput. A highly
loaded network offering ABE will give little throughput to all best
effort flows, no matter whether green or blue. However, ABE enables a
moderately loaded network to offer low delay to some applications
(typically, adaptive multimedia applications), as long as such
applications are satisfied with the throughput they receive.
Traditional byte transfer oriented applications would probably find
it more beneficial to use only blue packets.
2. ABE Service Requirements
ABE is an Internet service characterized by the following set of
requirements:
1. ABE packets are tagged as either green or blue.
2. Green packets receive a low, bounded delay at every hop, the
value of the per-hop delay bound configured by the operator.
3. Applications are expected to control their rate in a
TCP-friendly manner. Blue and green packets are considered to
belong to the same flow, not two distinct flows.
4. (Green does not hurt blue) If some source decides to tag some
of its packets green rather than blue, then the quality of the
service received by sources that tag all their packets blue
remains the same or becomes better.
5. All ABE packets belong to one single best effort class. If the
total load is high, then every source may receive little
throughput. However, entirely green sources may experience less
throughput than entirely blue sources sharing the same network
resources.
Requirement 5, the single class, ensures no policing of colour
tagging is required. In a network with a large number of blue
sources, a green source receives little throughput. Conversely, in a
network with many green sources, a blue source also receives little
throughput. This is not because the green sources are green, but
because there are many of them. If they were blue, the blue source
would probably get less throughput. However, it does get more than
if it were green. Lastly, a network where all sources are blue
Hurley, et al. Expires: May 2001 [page 3]
INTERNET-DRAFT draft-hurley-alternative-best-effort-01.txt November 2000
behaves as a flat best effort network. Conversely, a network with
only green sources behaves like a flat best effort network with
smaller buffers.
Requirement 4, that green do not hurt blue, is important. We now
outline what it entails. A more in depth discussion can be found in
Section 3.4 of [10]. Consider two scenarios, one in which all
sources are blue and the other in which some sources decide to tag
some packets green. The quality of service received by those packets
which remained blue in the second scenario should be as good as in
the first one. This requires the delay not to be any larger for the
blue packets, and that any blue packet which is not dropped (or
marked with congestion notification) in the first scenario would not
be either in the second one. As a consequence, the throughput of an
entirely blue flow would be at least as good in the second scenario,
since we assume that flows are TCP friendly.
A problem with this simple, intuitive definition is that sources are
assumed to be adaptive (TCP-friendly), thus in the second scenario,
the packets sent by the sources will not be the same as in the first
one. Furthermore, the behaviour of sources is dependent on their rate
adaptation algorithm, which, while being TCP-friendly, may have a
large number of different incarnations. As a first step in
circumventing this difficulty, we consider the concept of Local
Transparency to Blue:
Consider the scenario, flat best-effort, in which the node would
forget the colour and thus treat all ABE packets as one single best
effort class. An ABE node satisfies local transparency to blue if,
for each packet that is blue in the original (ABE) scenario:
o the delay is not larger in the real, ABE scenario than in the
flat best-effort scenario
o if the blue packet is not dropped (or marked with a congestion
notification) in the flat best-effort scenario, then it is not
either in the real, ABE scenario.
It means that if some packets are marked green in a node it does not
hurt blue packets, assuming one can ignore the effects due to rate
adaptation in the sources. It is a necessary requirement to ensure
green does not hurt blue. However, it may not be sufficient, since
the rate adaptation algorithm at the source might produce a higher
rate when the end-to-end delay is smaller.
Interpreting TCP-friendliness by the loss-throughput formula (e.g.
[13]), one can see that it is quite possible that, by becoming
green, a source would be allowed a higher data rate, due to the
reduction in round trip time. Such a source would generate more
packets than if it was blue, and there is the risk that, in some
cases, it might hurt blue packets.
The dependency of rate on round trip time in the loss-throughput is
Hurley, et al. Expires: May 2001 [page 4]
INTERNET-DRAFT draft-hurley-alternative-best-effort-01.txt November 2000
not necessarily a desirable feature of a rate adaption algorithm, and
fixes have been suggested that would remove the dependency of rate on
loss ratio [14]. If such fixes became widespread, then local
transparency to blue would indeed ensure that, from a throughput
viewpoint, green does not hurt blue. However, since the current
definition of TCP-friendliness does imply a dependency of rate on
round trip time, it is necessary to compensate for the delay decrease
obtained by green traffic which leads us to the "Throughput
Transparency to Blue" requirement for an ABE node: Assume that
sources employ a rate adaptation algorithm which conforms to a
loss-throughput formula. To provide blue with throughput
transparency, the ABE node must ensure that an entirely green flow
gets a lesser or equal throughput than if it were blue.
In summary, supporting the green does not hurt blue requirement can
be analysed as follows. A necessary condition is local transparency
to blue. Given the bias against long RTTs in the TCP-friendly rate
adaptation rules accepted today, ABE nodes have to additionally
satisfy throughput transparency to blue, which, due to reasons we
outlined, can only be achieved approximately. The implementation
presented in this draft satisfies exactly local transparency to
green and approximately satisfies throughput transparency to blue.
3. General Router Requirements
There may be many different implementations of ABE. We describe one
such implementation in Section 6. The generic router requirements
for any implementation are as follows:
1. Provide low, bounded delay to green packets.
2. Provide local transparency to blue.
3. Provide throughput transparency to blue.
4. Minimise green packet dropping or marking, subject to the above
requirements.
The first three requirements follow from our discussion in the
Section 2. The last requirement is because an implementation
should try to minimise green packet loss or marking, in order to
make the service attractive.
Enforcement of TCP-friendliness within a router is not specified.
Methods for enforcement are discussed in [2, 3] amongst others. We
expect in the future to see some implementations that would combine
the support of ABE with the enforcement of TCP-friendliness.
4. Source Aspects
A source is required to be TCP-friendly. Within this constraint, it
is perfectly permissible and considered normal practice for a source
to attempt to maximise its utility by employing a colour mixing
Hurley, et al. Expires: May 2001 [page 5]
INTERNET-DRAFT draft-hurley-alternative-best-effort-01.txt November 2000
strategy, where they would send some green packets and some blue.
Apart from possibly policing TCP- friendliness, the network
supporting ABE does not need to analyse individual flows. Source
strategies would typically be performed at the application level as
expected by Application Layer Framing (ALF) [11].
To illustrate the ABE service, we discuss now a very simple scenario.
Assume we have multimedia source, that is rate-adaptive, and has a
required minimum rate R0 in order to function properly, for a given
loss pattern in the network. If ECN is not used, the source
forward-correct packet losses, as long as the minimum rate is
achieved (see [8] for such an application example). The application
must choose between green or blue. The choice it makes depends on its
utility function u(R; D), for a given throughput R and end-to-end
network delay D.
In many situations today throughput is the major impediment. However,
once a minimum rate R0 is achieved which provides enough
intelligibility, delay becomes the major impediment. Thus, we assume
that the source utility function is such that it is 0 when R < R0 and
is a decreasing function of D when R <= R0. For such a source, the
optimal strategy is to be green when the load is such that the
minimum throughput can be received, blue when load means the minimum
throughput cannot be received as green, and to cease to operate when
the load is too high to do anything useful.
ABE opens up a new region of operation for the best-effort network.
In low load scenarios, a source may decide to obtain less throughput
for the benefit of low delay. In a flat best effort network, a
network without the ABE service, there is no such option; by
refraining from sending at a higher rate, there is in general no
impact on the queueing delay, because of external sources.
This example is of course oversimplified. In general we expect more
complex utility functions to be used, for example as specified in
[12]. Note that the detection of which region the source is currently
operating in has to be made automatically by the source itself.
Following immediately from the definition of the service, a blue
source has at least as high a throughput as a green one. Unlike the
multimedia source above, a source using TCP is more interested in its
throughput and would probably find it more beneficial to tag all its
packets blue.
5. Router Implementation
In this Section we present a router implementation model to support
the ABE service when using loss-based feedback. This implementation
assumes that the router has only output port queueing and is based on
a new scheduling concept, Duplicate Scheduling with Deadlines (DSD).
Before delving into the details of the scheme's description, let us
first explain its motivation. One of the first schemes to implement
Hurley, et al. Expires: May 2001 [page 6]
INTERNET-DRAFT draft-hurley-alternative-best-effort-01.txt November 2000
ABE that comes to mind is probably a FCFS scheduling discipline
with a threshold drop policy to filter green packets. In that scheme,
blue packets would be accepted until the buffer is full, whilst green
packets will only be accepted if it can be served with no greater
delay than some maximum d.
Whilst the scheme might operate "reasonably" well some of the time,
most of the time there would be little or no incentive in being
green. One wants to design a scheme that provides the best service
possible to green while still ensuring green does not hurt blue. The
gain blue packets would enjoy under ABE should be kept to a minimum
such that there is still an incentive to use green packets whenever
appropriate.
Let us temporarily consider only local transparency and solve the
additional problem of throughput transparency in Section 5.1. Then
in effect, we wish to minimise the number of green losses subject to
the following constraints:
o Green packets receive a no larger queueing delay than d.
o Local transparency to blue holds.
o The scheduling is work conserving.
o No reordering: Blue (respectively green) packets are served
in the order of arrival.
DSD is a solution to this problem. It is based on a new scheduling
concept called duplicates, which solves this problem by approximating
the operation (behaviour) of a flat best-effort service. A virtual
queue, with buffer space Buff, is fed with duplicates of all incoming
packets which are served by a FCFS discipline with rate c, as they
would be in a flat best-effort. Examples of how DSD works are given
in the Appendix. The times at which the duplicates are served is used
to assign blue packets deadlines at which they would have
(approximately) been served in a flat best-effort service. Actual
blue and green packets are fed into two separate queues, as follows.
Blue packet enqueuing and scheduling:
A blue packet is enqueued in the blue queue if its duplicate can be
admitted in the virtual queue. If the virtual queue length has
reached Buff, the duplicate and the original blue packet are dropped.
Otherwise, the duplicate is enqueued in the virtual queue, and the
original packet is tagged with a deadline, which is the time at which
the duplicate will be served in the virtual queue, and is the time at
which it would have (approximately) been served in a flat
best-effort service. A blue packet is always served at the latest
its deadline permits subject to work conservation.
Green packet enqueuing and scheduling:
Hurley, et al. Expires: May 2001 [page 7]
INTERNET-DRAFT draft-hurley-alternative-best-effort-01.txt November 2000
The simplest (we will discuss possible refinements later in this
section), green packets are enqueued in the green queue as soon as
they arrive. A duplicate of the same size is enqueued in the virtual
queue if there is enough space to accommodate it.
As green packets may not stay in the queue for more than d seconds,
they are tagged with a deadline which is their arrival time augmented
by d. If at a given time, the blue packet at the head of the queue
does not exceed its deadline by letting the first green packet go
first, the latter packet is served provided it waited for less than d
seconds. Green packets that have to wait for more than d seconds are
dropped from the green queue.
Upon the arrival of a packet at the output port, the algorithm is
summarised below:
Packet enqueueing Algorithm: (without early green packet drop)
add to virtual flat best-effort queue
if blue:
if dropped in virtual flat queue
drop
else
vd = queueing delay received in virtual queue
maxServiceTime = now + vd
tag maxServiceTime to packet
add to blue queue
else if green:
maxServiceTime = now + d
tag maxServiceTime to packet
add to green queue
Packet Serving Algorithm (without control loop):
remove all green packets whose maxServiceTime cannot be met
if no green packet to serve:
serve blue packet if any
else if no blue packet to serve:
serve green packet
else:
pg = transmission delay for head of green queue
mstb = maxServiceTime of head of blue queue
if now <= mstb - pg
serve green packet
else
serve blue packet
We have favoured clarity in description over efficiency. In
particular, the simple enqueuing mechanism of green packets
described above, with possible later dropping if they have been in
the queue for more than d seconds, may easily bring the total buffer
Hurley, et al. Expires: May 2001 [page 8]
INTERNET-DRAFT draft-hurley-alternative-best-effort-01.txt November 2000
occupancy (i.e. the sum of the green and blue queues lengths) above
Buff. To keep the total buffer occupancy of the green and blue
packets below Buff, green packets that would stay more than d seconds
in the queue must be discarded before being enqueued, rather than
after having waited d seconds in the queue. The following admission
test is applied: a green packet arriving at time t is discarded if
the sum of the length of the green queue at time t (including this
packet), and of the length of the first part of the blue queue that
contains packets tagged with a deadline shorter or equal to t + d +
pgnew, where pgnew is the transmission delay for the incoming green
packet, is more than c * (d + pgnew). It is accepted otherwise. The
fact that a green packet is served whenever the blue packet at the
head of the queue can wait before reaching its own deadline makes
this admission test both necessary and sufficient: it shown in [16]
that all accepted green packets are served within d seconds from
their arrival time if and only if they have passed this admission
test at the time of their arrrival.
Upon the arrival of a packet at the output port, the above algorithm
with the test for early drop of green packets, becomes:
Packet enqueueing Algorithm (with early green packet drop):
add to virtual flat best-effort queue
if blue:
if dropped in virtual flat queue
drop
else
vd = queueing delay received in virtual queue
maxServiceTime = now + vd
tag maxServiceTime to packet
add to blue queue
else if green:
maxServiceTime = now + d
pgnew = transmission delay for this packet
if (length(green queue) + length(blue queue with
packets with deadlines <= now + d + pgnew) > C*(d+pgnew) )
drop
else
tag maxServiceTime to packet
add to green queue
Packet Serving Algorithm (without control loop):
if no green packet to serve:
serve blue packet if any
else if no blue packet to serve:
serve green packet
else:
pg = transmission delay for head of green queue
mstb = maxServiceTime of head of blue queue
Hurley, et al. Expires: May 2001 [page 9]
INTERNET-DRAFT draft-hurley-alternative-best-effort-01.txt November 2000
if now <= mstb - pg
serve green packet
else
serve blue packet
It is not mandated that the virtual queue employ drop-tail queueing
although in the current implementation that is the case. An Active
Queue Management scheme such as RED [4] can be supported for blue
traffic by applying it to the virtual queue, and using those results
in assigning losses and deadlines.
Let us now look at its compliance with the ABE router requirements:
o Low bounded (per hop) delay for the green packets is enforced by
dropping a green packet that cannot be served in the deadline d.
o Local transparency to blue is ensured through dropping blues
only when they would be in the flat best-effort, and in not
letting accepted blues wait longer in the queue than they would
in flat best-effort.
o The DSD algorithm described so far does not ensure throughput
transparency to blue, which depends on the TCP feedback. This is
done by the control loop described in the next section.
o Minimising green packet dropping is achieved optimally by the
packet enqueueing and serving algorithms.
5.1 Control loop for DSD
The duplicate scheme, as it stands, provides the optimal performance
to green while constrained to support local transparency to blue.
In order to ensure throughput transparency as well, we used a control
loop, the details of which are contained in [10].
When TCP feedback comes into play, the throughput of blue and green
can be affected by violating throughput transparency and not
providing blue with enough throughput
To cater for this scenario, we add a control loop which adjusts to
the rate-adaptive nature of TCP. Since TCP-friendly sources are
sensitive to delay, we correct for any advantage green packets might
receive by increasing their delay. DSD, as described above, in
addition to providing minimum green losses for local transparency,
also minimises the delay green packets receive. This is because in
the event of either a green or a blue being able to wait and still
meet their deadlines, i.e. if both packets can wait, we always serve
the green packet first. This is not a requirement of ABE, and we can
still maintain local transparency, and not systematically favour the
green in this scenario. Note that by increasing the delay for green,
we are reducing their throughput, thus restoring throughput
transparency.
Hurley, et al. Expires: May 2001 [page 10]
INTERNET-DRAFT draft-hurley-alternative-best-effort-01.txt November 2000
We generalise the packet serving algorithm by introducing a green
bias g in the range [0,1], which determines the extent to which we
favour green over blue when both the first blue and green packets
have not yet reached their deadlines. More precisely, when both the
blue and green packets can wait, g is the probability that we serve
the green packet first. The value g=1 corresponds to the algorithm of
the previous subsection, where the green packet is always served if
both the blue and green packets can wait. Conversely the value g=0
corresponds to the systematic serving of the blue packet first. In
the example in Appendix A, the packets served would have thus been,
successively, B1, B2, G1, B3, B4, B5, B7, G3, G4, B8 and B9.
We use g as a control parameter to balance the throughputs of green
and blue. These are estimated from the loss-throughput formula
according of [13], the details of which are provided in [10]. This
algorithm is only one possible scheme, and its performance can be
improved, for example, by taking into account the deadlines of all
the packets in the queues, and not just those at the head. Such
extensions are the subject of further investigation.
6. Experimental results
This section represents on-going work and surveys some preliminary
experiments to evaluate the performance of ABE. We implemented the
ABE service as described in Section 5 in the Dummynet tool [15].
The experimental environment (see Figure 1) represents a gateway
where many networks are merged into one outgoing link. All hosts are
high end PCs running Linux. Each host has 2 network cards that we
used with a dedicated application to insert additional propagation
delay to the links from the routers to the hosts.
The two routers R1 and R2 are Cisco 7500 routers running IOS 12.0.
Dummynet acts as a bridge between the two routers and it is used to
emulate the bottleneck link and to implement the ABE service. The
links between the routers and the hosts are 10Mbps Ethernet links,
while between the routers and Dummynet we have a 100Mbps Fast
Ethernet link. We used this settings to make sure that all losses
occur inside the Dummynet bridge.
____ ____
host 1 ---| | _____________________ | |--- host 5
host 2 ---| R1 |---| ABE/dummynet bridge |---| R2 |--- host 6
host 3 ---| | |_____________________| | |--- host 7
host 4 ---|____| |____|--- host 8
Figure 1. Testbed configuration
In all the following experiments the bottleneck has a capacity of 1
Mbit/s, a 50 ms propagation delay and a buffer size of 75 Kbytes.
The links between hosts 1 to 4 to the router R1 have a propagation
Hurley, et al. Expires: May 2001 [page 11]
INTERNET-DRAFT draft-hurley-alternative-best-effort-01.txt November 2000
delay of 20ms, 40ms, 60ms and 80ms respectively.
The traffic generated by the hosts consists of persistent TCP SACK
connections ("coloured" as blue) and UDP connections ("coloured" as
green) sending at a constant bit rate.
All the results come from 10 minutes experiments where the first and
last minutes are discarded in order to take into account only steady
state behaviour.
Firstly, we compare the loss rate experienced by green traffic in the
presence of a variable amount of blue traffic and with different
settings for the ABE router to evaluate the impact of the ABE
settings (i.e. green maximum delay d) and of concurrent blue
traffic.
In Table 1 we show the average loss rate for green traffic made of 4
UDP connections sending at an aggregate rate of 100Kbps with a
background blue traffic made of 4 to 16 TCP sources. Table 2 shows
instead the aggregate throughput of blue traffic.
______________________________________________________________________
Table 1. Average loss rate (with 90% confidence interval)
experienced by green traffic.
----------------------------------------------------------------------
blue | ABE with green maximum delay Flat BE
srcs | 10ms 20ms 50ms
----------------------------------------------------------------------
4 | 16.58 (12.07) | 2.58 (0.71) | 2.07 (0.25) | 0.90 (0.34)
8 | 18.90 (1.59) | 2.63 (0.44) | 2.52 (0.62) | 2.37 (0.40)
16 | 21.26 (6.44) | 6.35 (0.59) | 6.21 (0.41) | 5.55 (0.41)
----------------------------------------------------------------------
______________________________________________________________________
Table 2. Aggregate throughtput of blue traffic (Kbps).
----------------------------------------------------------------------
blue | ABE with green maximum delay Flat BE
srcs | 10ms 20ms 50ms
----------------------------------------------------------------------
4 | 897.11 (1.87) | 891.77 (0.44) | 891.40 (0.51) | 889.75 (0.65)
8 | 905.06 (3.91) | 893.44 (0.51) | 893.41 (0.16) | 897.78 (0.57)
16 | 909.55 (4.74) | 897.55 (0.61) | 897.78 (0.57) | 896.62 (0.85)
----------------------------------------------------------------------
As expected, the loss rate for green traffic is much higher in ABE
than in the flat best effort scenario which is the cost to pay for a
lower queuing delay. Indeed, in the flat best effort scenario the
average queuing delay for UDP traffic is around 400ms, while with ABE
setting d to 10ms it is around 6ms.
Regarding blue traffic, experiments show that there is benefit in
being blue in terms of throughput. It comes directly from the fact
that green flows suffer higher loss rates, allowing blue packets to
Hurley, et al. Expires: May 2001 [page 12]
INTERNET-DRAFT draft-hurley-alternative-best-effort-01.txt November 2000
take advantage of the reduced buffer occupancy to reduce their round
trip time and therefore their throughput.
We are instigating further investigation to fully understand results
showed in the tables above. For instance, we need to study the high
variance of loss rate for green traffic in presence of few competing
blue sources, that may come from an inappropriate testbed
configuration or from a synchronisation phenomenon of TCP flows.
Moreover, from these preliminary results there seems to exist a
threshold for the maximum green delay beyond which there is a very
high increase in the green loss rate. This threshold phenomenon may
be pathological with the kind of scenarios we investigated or may be
a characteristic of the ABE implementation.
We have run additional experiments changing the traffic mix, making
the green traffic as the dominant part of the traffic over the
bottleneck. We do not believe that such scenarios can occur in a real
network, but they can be useful to evaluate robustness of the ABE
implementation and to identify pathological scenarios that may
heavily affect router performance.
The next two tables show the green loss rate and blue throughput when
the traffic is made of 16 blue/TCP connections and a variable number
of green/UDP sources with an aggregate sending rate from 100Kbps to
500Kbps, i.e. from 10% to 50% of the bottleneck bandwidth.
___________________________________________________________________
Table 3. Average loss rate (with 90% confidence interval)
experienced by green traffic.
-------------------------------------------------------------------
green | green maximum delay Flat BE
rate | 10ms 20ms 50ms
-------------------------------------------------------------------
100Kbps | 21.26 (6.44) | 6.35 (0.59) | 6.21 (0.41) | 5.55 (0.41)
200Kbps | 32.07 (12.52) | 8.95 (0.95) | 8.66 (1.01) | 7.56 (0.58)
500Kbps | 55.62 (7.19) | 31.50 (7.03)| 20.01(3.30) | 17.99 (2.30)
-------------------------------------------------------------------
___________________________________________________________________
Table 4. Aggregate throughtput of blue traffic (Kbps).
-------------------------------------------------------------------
green | green maximum delay Flat BE
rate | 10ms 20ms 50ms
-------------------------------------------------------------------
100Kbps| 909.55 (4.74)| 897.55 (0.61)| 897.78 (0.57)| 896.62 (0.85)
200Kbps| 825.33 (3.30)| 800.76 (2.20)| 799.90 (2.59)| 797.58 (2.10)
500Kbps| 631.14(44.06)| 597.82(16.15)| 555.23 (8.20)| 548.71 (7.81)
-------------------------------------------------------------------
7. Codepoint Requirements
An implementation of ABE using AF codepoints is not practical for the
Hurley, et al. Expires: May 2001 [page 13]
INTERNET-DRAFT draft-hurley-alternative-best-effort-01.txt November 2000
following reasons. Firstly, if we map blue and green within the same
AF class, we would give green a high precedence level in order for it
to receive a low delay. However this would contradict the requirement
that blue sources receive at least as much as it would if green.
Secondly, if we map blue and green to different AF classes, we would
need to coordinate packet dropping across the two classes, which
appears to contradict RFC2597.
An allocation of codepoints to support ABE is thus needed. There are
two possibilities for codepoint provision.
The first considers blue packets as normal best-effort packets, which
use the predefined DSCP value 0. ABE packet classification can be
achieved by introducing a new PHB for green. The DSCP value for
green specification should satisfy the following:
o It should be in one of the experimental/local use pools defined
in RFC2474: xxxx11 binary and xxxx01 binary.
o It should be smaller than 0x38 (otherwise, privileges are required
to set them at the source using the IP_TOS socket option)
Routers without an ABE implementation will simply treat blue and green
packets in the same way.
The second possibility is for ABE to have a traffic class of its own
with 2 codepoints. We leave for future discussion as to which of the
two possibilities would be preferable.
8. Conclusions
We described ABE, a new service which enables best-effort traffic to
experience a low delay, at the expense of possibly more throughput.
ABE is targeted at supporting rate-adaptive multimedia applications,
with no concept of reservation or signalling and while retaining the
spirit of a flat rate network. The service choice of green or blue is
self-policing since the user/application will be coaxed into choosing
one or the other or indeed a mixture of both, based on its traffic
profile objectives. ABE allows a collection of rate-adaptive
multimedia applications to drive the network into a region of
moderately high load and low delay. It also allows such an application
to trade reduced throughput for low delay, thus in some cases
increasing its utility.
It should be stressed that ABE is a new service in its own right and
not a substitute for reservation or priority services. In contrast,
with ABE, both delay sensitive (green) and throughput sensitive (blue)
traffic share the same resources, and high load in any of the two
pools affects the other.
9. References
[1] TCP friendly web site.
http://www.psc.edu=networking=tcp_friendly.html
Hurley, et al. Expires: May 2001 [page 14]
INTERNET-DRAFT draft-hurley-alternative-best-effort-01.txt November 2000
[2] Floyd, S., and Fall, K. Promoting the Use of End-to-End
Congestion Control in the Internet.
[3] B. Suter, T.V. Lakshman, D. Stiliadis, A. Choudhury. Design
Considerations for Supporting TCP with Per-flow Queueing.
Proceedings of IEEE INFOCOM 98.
[4] Floyd, S., and Jacobson, V. Random Early Detection gateways for
Congestion Avoidance. IEEE/ACM Transactions on Networking, V.1
N.4, August 1993, p.397-413.
[5] V. Jacobson, K. Nichols and K. Poduri. An Expedited Forwarding
PHB. RFC2598.
[6] J. Heinanen, F. Baker, W. Weiss, J. Wroclawski. Assured
Forwarding PHB Group. RFC2597.
[7] Floyd, S. TCP and Explicit Congestion Notification. ACM Computer
Communication Review. V. 24 N. 5, October 1994, p. 10-23.
[8] J. Bolot, S. Fosse-Parisis, D. Towsley. Adaptive FEC-Based Error
Control for Interactive Audio in the Internet.
Proceedings of IEEE Infocom 99.
[9] C. Diot, C. Huitema, T. Turletti. Multimedia Application should
be Adaptive. HPCS, Aug. 1995.
[10] P. Hurley, M. Kara, J-Y Le Boudec, P. Thiran. ABE: Providing A
Low-Delay Service Within Best-Effort (Under Submission).
Technical Report DSC/2000/034.
http://www.abeservice.org/papers/abe034.pdf
[11] D. Clark, D. L. Tennenhouse. Architectural considerations for a
new generation of protocols. Computer Communications Review,
vol. 20, Sept. 1990.
[12] L. Breslau and S. Shenker. Best-Effort versus Reservations: A
Simple Comparative Analysis. SIGCOMM 1998.
[13] J.Padhye, V.Firoiu, D.Towsley and J.Kurose. Modeling TCP
Throughput: A Simple Model and its Empirical Validation.
Proceedings of SIGCOMM'98.
[14] T.R. Henderson, E. Sahouria, S. McCanne, and R.H. Katz.
Improving Fairness of TCP Congestion Avoidance.
Proceedings of IEEE Globecom `98, Sydney, Australia, Nov. 1998.
[15] Luigi Rizzo. Dummynet: a simple approach to the evaluation of
network protocols. ACM Computer Communication Review, Jan 1997
[16] P. Thiran. Packet Admission Control for ABE with duplicates.
http://www.abeservice.org/papers/green_early_discard.ps
Hurley, et al. Expires: May 2001 [page 15]
INTERNET-DRAFT draft-hurley-alternative-best-effort-01.txt November 2000
10. Appendix A: A first example of DSD (with late green packet drop)
For this example, all packets are the same size and "packet" time is
used. The maximal buffer size is Buff=7 packets. The maximum green
queue wait is d=3 packets. B and G denote blue and green packets
respectively.
We use two snapshots to illustrate DSD. The first is at time t=0.
Deadline: 6 4 3 2 0
----------------------------------
| | B5 | B4 | B3 | B2 | B1 |---
---------------------------------- |
|
| -> serve at rate c
Deadline: 3 2 |
---------------------------------- |
| | | | | G2 | G1 |---
----------------------------------
Virtual Queue:
----------------------------------
B5 | G2 | B4 | B3 | B2 | G1 | B1 | -> serve at rate c
----------------------------------
B1 is served at time t=0 in order to meet its deadline, then G1, B2,
B3, B4. G2 has to be dropped from the green queue because it has to
wait for more than d=3, whereas B6 had to be dropped because the
virtual queue length was Buff when it arrived.
At time t=5, we reach the following situation:
Deadline: 10 9 7 6
----------------------------------
| | | B9 | B8 | B7 | B5 |---
---------------------------------- |
|
| -> serve at rate c
Deadline: 8 7 |
---------------------------------- |
| | | | | G4 | G3 |---
----------------------------------
Virtual Queue:
----------------------------------
G4 | B9 | B8 | G3 | B7 | B5 | G2 | -> serve at rate c
----------------------------------
As no blue packet has reached its deadline yet, G3 can be served,
followed by B5, B7, G4, B8, and B9
11. Appendix B: A second example of DSD (with early green packet drop)
Hurley, et al. Expires: May 2001 [page 16]
INTERNET-DRAFT draft-hurley-alternative-best-effort-01.txt November 2000
The scenario for this example is the same as the one in Appendix A,
except that now green packets are enqueued only if they pass the
admission test described in the router implementation, which amounts
here to accepting a green packet at time t if the number of green
packets in the queue at time t, augmented by the number of blue
packets in the queue with deadline in [t, t+4] is no more than 4.
The first snapshot at time t=0 then becomes
Deadline: 6 4 3 2 0
----------------------------------
| | B5 | B4 | B3 | B2 | B1 |---
---------------------------------- |
|
| -> serve at rate c
Deadline: 2 |
---------------------------------- |
| | | | | | G1 |---
----------------------------------
Virtual Queue:
----------------------------------
B5 | G2 | B4 | B3 | B2 | G1 | B1 | -> serve at rate c
----------------------------------
The only difference from the first snapshot in Appendix A is that G2
is no longer enqueued. Indeed, when it arrived, the green queue
contained already packet G1, and the blue queue contained packets B1,
B2 and B3. The total queue length at time was 5 packets (including
G2), and so G2 fails the test.
12. Authors' Address
Paul Hurley (contact author)
Jean-Yves Le Boudec
EPFL - DSC - ICA
IN Ecublens
CH-1015 Lausanne
Switzerland
Email: paul.hurley,Jean-Yves.Leboudec@epfl.ch
Gianluca Iannaccone
Christophe Diot
Patrick Thiran
Sprint ATL
1, Adrian Court
Burlingame, CA 94010
USA
Email: cdiot, pthiran, gianluca@sprintlabs.com
Mourad Kara
School of Computing
Hurley, et al. Expires: May 2001 [page 17]
INTERNET-DRAFT draft-hurley-alternative-best-effort-01.txt November 2000
University of Leeds
United Kingdom.
Email: mourad@scs.leeds.ac.uk
