Providing a Low-Delay IP Service Within a Best-Effort Internet
ABE (Alternative Best-Effort) is a novel service for IP networks. It provides a low bounded queueing delay service in the Internet. The service is best-effort, and requires no additional charging or usage control. Its goal is to help applications with stringent real time constraints, such as interactive audio. With ABE, it is not required to police how much traffic uses the low delay capability, the service being designed to operate equally well in all traffic scenarios.
Applications choose 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.
Green and blue were chosen because they are primary colours of equal value, with neither having priority over the other. Green is picked for low-delay because it is the go signal on a traffic light.
Using green helps those adaptive applications whose utility depends not only on throughput, but also on the end-to-end delays of individual packets. Typically, green flows have real-time deadlines (e.g. interactive audio). For example, one application that would likely benefit from ABE would be IP Telephony .
Blue traffic seeks to minimise overall transfer time, but does not care so much about individual packet delays. As such FTP, and HTML type traffic would choose blue, as well as pretty much anything which requires file data transfer.
Not necessarily. Depending on network conditions, the application receive satisfactory performance out of being blue.
Yes. Indeed, it is considered normal behaviour for a flow to colour mix in a manner that increases its utility.
This refers to the current best-effort IP network, where there is no distinction between packets that value low-delay over higher throughput.
No, they have a different service. 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.
ABE addresses a different m
arket to existing differentiated or integrated services. The combination of lower delay with reduced throughput for green makes it different from existing differentiated service proposals such as expedited forwarding (EF) and assured forwarding (EF).ABE does not offer any guarantee, or even indication of guarantee, on throughput. It is a new service in its own right and not a substitute for reservation or priority services.
Unlike these services, 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, as long as they are satisfied with the throughput they receive.
The incentive to choose one or other is based on the nature of one's traffic and on traffic conditions. Neither traffic type can be said to be better, so flat rate pricing may be maintained, and there is no need for reservations or profiles.
The ABE service is designed to work with either losses or ECN as feedback.
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 ECN will be used. ABE would be even more attractive with ECN. The implementation, ABE/DSD, described on this page uses loss-based feedback.
Green Does Not Hurt Blue means that if a 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.
We give here just a brief overview of what it means to adhere to this property and referred the interested to Section 3.4 of the latest paper on ABE.
Imagine all sources are blue. If some sources then decide to tag some packets green, the quality of service received by those packets which remained blue should be at least as good as if they didn't. The delay should not to be any larger for the blue packets, and any blue packet which would not have been dropped (or marked with ECN) if the packets were all blue must not be dropped when there are green packets around.
However, the sources are assumed to be adaptive, and thus the packets sent by sources will not be the same when some packets are coloured green. Thus, we consider Green Does Not Hurt Blue as being a requirement in two parts. The first is Local Transparency To Blue, which is defined as follows:
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:
- the delay is not larger in the real, ABE scenario than in the flat best-effort scenario
- if the blue packet is not dropped (or marked with a congestion notification) in the flat best-effort scenario, then it is not dropped in the real, ABE scenario.
Ignoring the effects due to the rate adaptation of the sources, this ensures packets marked green in a node do not hurt blue packets. This requirement is necessary 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. see here), 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 were blue, and there is the risk that, in some cases, it might hurt blue packets.
It is necessary to compensate for the delay decrease obtained by green traffic which leads us to the second requirement to ensure Green Does Not Hurt Blue, Throughput Transparency to Blue:
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.
A network with only green sources behaves like a flat best-effort network with smaller buffers.
A network where all sources are blue behaves as a flat best-effort network.
It stands for "Alternative", though it should be referred to simply as ABE. Originally, it stood for "Asymmetric". We changed the name to "Alternative" on a recommendation so as to avoid confusion with asymmetric links (links with different properties in different directions). We inadvertently caused even more confusion by doing this. Oops. Hence the desire to refer to the service simply as ABE which encompasses both the original and current expansions of the acronym.
ABE was designed with adaptive multimedia flows, that rate adapt within the constraints of TCP Friendliness, in mind, and is designed as such. However, the Local Transparency property of ABE protects blue traffic at least as well as it does in a flat best-effort network. This means that unresponsive flows will damage blue only, in the worst case, as much as they do now, ensuring non-responsive flows can be supported to the same extent they can be today. Like today's Internet, ABE does not enforce TCP Friendliness, and we envisage implementations that combine ABE and enforcement.
ABE can be employed on some links in the network where it is needed, and is not needed on all links.
Local Transparency facilitates gradual deployment of ABE. Imagine, for example, the scenario as in the picture above. The network has added ABE, but there are some sources (the ones in the lower part of the diagram) which would benefit from being green in that they want low delay, but their applications do not exploit ABE. The default traffic colour is blue. Since Local Transparency ensures no increase in delay for blue packets, these applications will not suffer as a result of the deployment of ABE.
It must:
For requirement 1, the value of the low bounded delay is decided by the operator. Requirements 2 and 3 are to ensure blue do not suffer with the introduction of the ABE service. The 4th requirement is to make ABE as attractive to green as possible within the constraints of protecting blue.
ABE is not restricted to any specific implementation. Many implementations of ABE are possible and we encourage others, such as universities and research centres, to define others (for example implementations based on per-flow queueing are certainly do-able) We focus here on ABE/DSD, which is described below.
The first implementation of ABE was ABE/EDF, which appeared in the proceedings of Globecom 99 and IwQoS 99 It is based on favouring green by preferential scheduling using a modified version of EDF, combined with favouring blue packets for packet acceptance and has been implemented in Linux by Werner Almesberger.
DSD stands for Duplicate Scheduling with Deadlines. It gets this name because it uses a new scheduling concept called duplicates, which approximates the operation of flat best-effort using a virtual queue which is fed with duplicates of all incoming packets.
ABE/DSD's goal is to offer green packets the best service possible while still fulfilling the requirements of an ABE router implementation. This lends itself naturally to an optimisation problem. We would like to minimise the number of green losses subject to the constraints:
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.
In summary, this is what happens a packet upon arrival at the output port of a router:
This is how packets are scheduled to be served:
Sure. Please have a look at the page on an example.
It has been implemented and simulated extensively under the simulator, ns-2. An implementation in dummynet has been created, and is currently being tested on a test bed at Sprint ATL. Finally, an implementation in Linux is in the pipeline.
The code for ns-2 and dummynet will be made available shortly and placed on this web site. Anyone who wishes to obtain the code in the meantime, should write to me.
There might be. It is possible to determine when a green packet arrives if it should be dropped then, rather than wait for its deadline to expire. We describe how to do this in the Internet Draft.
The implementation as described ensures Local Transparency to Blue. To ensure that Throughput Transparency holds too, ABE/DSD uses additionally a control loop, the details of which are described in the technical report.
Order is preserved between classes. This means that blue packets cannot overtake blue packets that arrive beforehand and that green packets cannot overtake green packets that came before them.
Green packets can overtake blue packets that were already in the queue. If this was not allowed then offering a lower bounded delay to green would entail dropping far too many green.
No. One can use an active queue management scheme such as RED on the virtual queue, and using those results in assigning drops and delays for blue packets.
You can have a look at a slide-show, the latest technical report, and/or an Internet Draft.
Please contact Paul Hurley at paul.hurley@epfl.ch.
Amongst those working on the ABE are Catherine Boutremans, Christophe Diot, Paul Hurley, Gianluca Iannaconne, Mourad Kara, Jean-Yves Le Boudec, and Patrick Thiran.
The following universitites and research lab are involved:
Of course, we welcome other contributions to ABE!