Efficient control of non-cooperative traffic using sending rate estimate-based queue management schemes

In this dissertation, we develop router-based queue management schemes with the ability to support quality of service (QoS) objectives in terms of bandwidth guarantees for traffic flows in the Internet. We develop simple packet dropping schemes that are inexpensively implementable at high speeds and that can achieve max-min fair bandwidth allocations to all the users. In short, we develop schemes that can approximate fair queueing using a single FIFO queue and a light-weight queue management algorithm.; First, we review the state-of-the-art congestion control algorithms and argue that router-based schemes are an inescapable necessity. Router-based congestion control call be performed either by scheduling algorithms or by queue management algorithms. Scheduling algorithms employ complex per-flow queueing, and can guarantee strict QoS requirements of users. They are often considered too complex for high speed implementation and do not scale. Queue management algorithms, on the other hand, employ a FIFO queue to be shared by all flows and a simple packet dropping mechanism. This simple design makes them amenable to high speed implementations. Queue management schemes are often criticized for their lack of QoS support and their inability to protect well-behaved sources from ill-behaved sources.; Second, we argue that in order to provide QoS using queue management schemes, we should make packet dropping decision a compound function of the sending rate of each flow and the instantaneous queue length, instead of just the average queue length. To pursue this idea further, we devise a novel, highly efficient algorithm that can estimate the relative sending rate of flows with a high degree of accuracy. We use this algorithm to design a family of queue management schemes called sending rate estimate based queue management (SREQM) schemes. We present different versions of SREQM optimized for memory and processing with techniques employing sampling and Bloom filters to further reduce the amount of state variables and memory required to make dropping decisions. We complement the designs with detailed simulations and analyses to show that SREQM is robust and can guarantee fairness in a wide variety of operating conditions. We also study the interaction between sources and queue management schemes using game theory, and show that SREQM can achieve Nash equilibrium, which indicates a stable operating condition.; Finally, we present techniques to estimate buffer requirements with the constraint of maximizing the link utilization, and show that SREQM requires lower buffer space than other queue management schemes such as RED. We argue that high link utilization and low buffer requirements are due to the desynchronization of flows by SREQM.