Buffer and queue protection in high-speed network routers

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.