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