Buffer and queue protection in high -speed network routers

2006 2006

Other formats: Order a copy

Abstract (summary)

A key threat to network applications in enterprise networks is buffer and queue exhaustion from high rate non-adaptive flows, that we call belligerent flows. There is normally more than enough bandwidth for well-behaving applications. Belligerent flows use as much bandwidth as they can grab, and they do not respond correctly to network congestion signals. If not limited, belligerent flows increase queueing delay and cause packet drops by filling network switch buffers. Once switch runs out of queue space, incoming packets are dropped, causing denial of service to other well-behaving flows. A fast response buffer and queue protection mechanism that is implementable in high speed switch hardware is needed.

First, we describe a queue buffer management scheme, Dynamic Buffer Limiting (DBL), that is designed to protect the switch queue buffers from belligerent flows. Our results demonstrate that DBL detects and limits belligerent flows quickly while providing reasonable treatment to well-behaving flows and protecting low-rate, drop- and latency-sensitive fragile flows, without relying on trust in the network.

Second, we show that the algorithm is implementable in high speed switch hardware at a cost competitive with alternative solutions. In this thesis, we focus on high-speed enterprise Ethernet switches.

Finally, we discuss extensions to the basic algorithm to provide rate control (rate-DBL) and active queue selection (AQS). We demonstrate that Rate-DBL provides self-regulation of high priority and low-rate traffic, such as voice-over-IP traffic, preventing misuse of scheduling priority by a misbehaving flow. We show AQS segregates belligerent flows from well-behaving flows, providing higher goodput and lower delay to well-behaving flows.

We implemented DBL in a commercial high-speed Ethernet switch, in the widely deployed Cisco Catalyst 4000/4500 switch. In this hardware implementation, DBL handles 102 Million packets per second.

Indexing (details)

Computer science
0984: Computer science
Identifier / keyword
Applied sciences; Buffer; High-speed network; Queue; Routers
Buffer and queue protection in high -speed network routers
Ertemalp, Fusun
Number of pages
Publication year
Degree date
School code
DAI-B 66/11, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
9780542431234, 0542431238
Garcia-Molina, Hector
Stanford University
University location
United States -- California
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.