DOC PREVIEW
CMU CS 15744 - Core-St at eless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations i

This preview shows page 1-2-3-4 out of 13 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Core-St at eless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks* Ion Stoica Scott Shenker CMlJ Xerox PARC istoicaQcs.cmu.edu [email protected] Hui Zhang CMlJ [email protected] Abstract Router mechanisms designed to achieve fair bandwidth al- locations, like Fair Queueing, have many desirable proper- ties for congestion control in the Internet. However, such mechanisms usually need to maintain state, manage buffers, and/or perform packet scheduling on a per flow basis, and this complexity may prevent them from being cost-effectively implemented and widely deployed. In this paper, we pro- pose an architecture that significantly reduces this imple- mentation complexity yet st,ill achieves approximately fair bandwidth allocations. We apply this approach to an is- land of routers - that is, a contiguous region of the net- work and we distinguish between edge routers and core routers. Edge routers maintain per flow state; they estimate the incoming rate of each flow and insert a label into each packet header based on this estimate. Core routers main- tain no per flow state; they use FIFO packet scheduling aug- mented by a probabilistic dropping algorithm that uses the packet labels and an estimate of the aggregate traffic at the router. We call the scheme Core-Stateless Fair Queueing. We present simulations and analysis on the performance of this approach, and discuss an alternate approach. 1 Introduction A central tenet of the Internet architecture is that conges- tion control is achieved mainly through end-host algorithms. However, starting with Nagle [16], many researchers ob- served that such end-to-end congestion control solutions are greatly improved when routers have mechanisms that allo- cate bandwidth in a fair manner, Fair bandwidth allocation protects well-behaved flows from ill-behaved ones, and al- lows a diverse set of end-to-end congestion control policies Lo co-exist in the network [7]. As we discuss in Section 4, * I’hls research was sponsored by DARPA under contract numbers N66001-96-C-8528, E30602-97-Z-0287, and DABT63-94-C-0073, and by a NSF Carerr Award under grant number NCR-9624979. Addi- tlonal support was provided by Intel Corp., MCI, and Sun Microsys- terns. Views and conclusions contained in this document are those of the authors and should no be interpreted as representing the official poliries, either expressed or implied, of DARPA, NSF, Intel, MCI, Sun, or the U.S. government Q ,998 ACM l-58113~003.l/98/0008.. $5.00 sorne maintain that fair bandwidth allocation’ plays a uer- essary, not just beneficial, role in congestion control [7, 191. Until now, fair allocations were typically achieved by us- ing per-flow queueing mechanisms - such as Fair Queueing [7, 181 and its many variants [2, 10, 20]- or per-flow dropping mechanisms such as Flow Random Early Drop (FRED) [14]. These mechanisms are more complex to implement than t,ra- ditional FIFO queueing with drop-tail, which is the most widely implemented and deployed mechanism in routers to- day. In particular, fair allocation mechanisms inherently require the routers to maintain state and perform opera- tions on a per flow basis. For each packet that arrives at the router, the routers needs t,o clnssi~$ the packet into a flow, update per flow state variables, and perform certain opera- tions based on the per flow state. The operations can be as simple as deciding whether to drop or queue the packet (e.g., FRED), or as complex as manipulation of priority queues (e.g., Fair Queueing). While a number of techniques have been proposed to reduce the complexity of the per packet> operations [I, 20, 211, and commercial implementations are available in some intermediate class routers, it is still MI- clear whether these algorithms can be cost-effectively implr- mented in high-speed backbone routers because all these al- gorithms still require packet classification and per flow state management. In this paper we start with the assumption that (1) fair allocation mechanisms play an important, perhaps even nec- essary, role in congestion control, and (2) the complexity of existing fair allocation mechanisms is a substantial hin- drance to their adoption. Both of these points are debat- able; developments in router technology may make such al- gorithms rather inexpensive to implement, and there may be solutions to congestion control that do not require fair allocation (we discuss this point more fully in Sectiou 4). By using these two assumptions as our starting points we are not claiming that they are true, but rather are only looking at the implications if indeed they 2uere true. If one starts with these assumptions then overcoming the complex- ity problem in achieving fair allocation becomes a vitally important problem. To this end, we propose and examine an architecture and a set of algorithms that allocate bandwidth in an approxi- mately fair manner while allowing the routers on high-speed links to use FIFO queueing and maintain no per-flow state. ‘We use the max.mm defimtmn of fairness [la] which, whole not the only possible candidate for fairness, LS certamly a reasonable one and, moreover, can be implemented with only local mformatlon 118In this approach, we identify an island of routers’ and dis- tinguish between the edge and the core of the island. Edge routers compute per-flow rate estimates and label the pack- ets passing through them by inserting these estimates into each packet header. Core routers use FIFO queueing and keep no per-flow state. They employ a probabilistic drop- ping algorithm that uses the information in the packet la- bels along with the router’s own measurement of the aggre- gate traffic.


View Full Document

CMU CS 15744 - Core-St at eless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations i

Documents in this Course
Lecture

Lecture

25 pages

Lecture

Lecture

10 pages

Lecture

Lecture

10 pages

Lecture

Lecture

45 pages

Lecture

Lecture

48 pages

Lecture

Lecture

19 pages

Lecture

Lecture

97 pages

Lecture

Lecture

39 pages

Lecture

Lecture

49 pages

Lecture

Lecture

33 pages

Lecture

Lecture

21 pages

Lecture

Lecture

52 pages

Problem

Problem

9 pages

Lecture

Lecture

6 pages

03-BGP

03-BGP

13 pages

Lecture

Lecture

42 pages

lecture

lecture

54 pages

lecture

lecture

21 pages

Lecture

Lecture

18 pages

Lecture

Lecture

18 pages

Lecture

Lecture

58 pages

lecture

lecture

17 pages

lecture

lecture

46 pages

Lecture

Lecture

72 pages

Lecture

Lecture

44 pages

Lecture

Lecture

13 pages

Lecture

Lecture

22 pages

Lecture

Lecture

48 pages

lecture

lecture

73 pages

17-DNS

17-DNS

52 pages

Lecture

Lecture

10 pages

lecture

lecture

53 pages

lecture

lecture

51 pages

Wireless

Wireless

27 pages

lecture

lecture

14 pages

lecture

lecture

18 pages

Lecture

Lecture

16 pages

Lecture

Lecture

14 pages

lecture

lecture

16 pages

Lecture

Lecture

16 pages

Lecture

Lecture

37 pages

Lecture

Lecture

44 pages

Lecture

Lecture

11 pages

Lecture

Lecture

61 pages

Multicast

Multicast

61 pages

Lecture

Lecture

19 pages

Lecture

Lecture

8 pages

Lecture

Lecture

81 pages

Lecture

Lecture

9 pages

Lecture

Lecture

6 pages

Lecture

Lecture

63 pages

Lecture

Lecture

13 pages

Lecture

Lecture

63 pages

Lecture

Lecture

50 pages

lecture

lecture

35 pages

Lecture

Lecture

47 pages

Lecture

Lecture

29 pages

Lecture

Lecture

92 pages

Load more
Download Core-St at eless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations i
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Core-St at eless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations i and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Core-St at eless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations i 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?