Congestion Control in Computer Networks

Srinivasan Keshav

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-91-649
September 1991

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/CSD-91-649.pdf

This thesis examines the problem of congestion control in reservationless packet switched wide area data networks. We define congestion as the loss of utility to a network user due to high traffic loads and congestion control mechanisms as those that maximize a user's utility at high traffic loads. In this thesis, we study mechanisms that act at two time scales: multiple round trip times and less than one round trip time. At these time scales, congestion control involves the scheduling discipline at the output trunks of switches and routers, and the flow control protocol at the transport layer of the hosts.

We initially consider the problem of protecting well-behaved users from congestion caused by ill-behaved users by allocating all users a fair share of the network bandwidth. This motivates the design and analysis of the Fair Queueing resource scheduling discipline. We then study the efficient implementation of the discipline by doing an average case performance evaluation of several data structures for packet buffering.

Since a Fair Queueing server maintains logically separate pre-conversion queues and approximates a bitwise-round robin server, it partially decouples the service received by incoming traffic streams. This allows us to deterministically model a single conversation in a network of Fair Queueing servers. Analysis of the model shows that a source can estimate the service rate of the slowest server in the path to its destination (the bottleneck) by sending a pair of back-to-back packets (a packet-pair probe), and measuring the inter-acknowledgement spacing. The probe values can be used to control a user's data sending rate. We formalize this notion by modeling a conversation as a linear system in a simple control-theoretic approach. This is used to synthesize a robust and provably stable flow control protocol. The network state, that is, the service rate of the bottleneck, can be estimated from the series of probe values using an estimator based on elementary fuzzy logic.

Our analysis and performance claims are examined by simulation experiments on a set of eight test scenarios. We show that under a wide variety of test conditions, both of our schemes provide users with good performance. Thus, these mechanisms should prove useful in future high-speed networks.

Advisor: Domenico Ferrari


BibTeX citation:

@phdthesis{Keshav:CSD-91-649,
    Author = {Keshav, Srinivasan},
    Title = {Congestion Control in Computer Networks},
    School = {EECS Department, University of California, Berkeley},
    Year = {1991},
    Month = {Sep},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/6386.html},
    Number = {UCB/CSD-91-649},
    Abstract = {This thesis examines the problem of congestion control in reservationless packet switched wide area data networks. We define congestion as the loss of utility to a network user due to high traffic loads and congestion control mechanisms as those that maximize a user's utility at high traffic loads. In this thesis, we study mechanisms that act at two time scales: multiple round trip times and less than one round trip time. At these time scales, congestion control involves the scheduling discipline at the output trunks of switches and routers, and the flow control protocol at the transport layer of the hosts. <p>We initially consider the problem of protecting well-behaved users from congestion caused by ill-behaved users by allocating all users a fair share of the network bandwidth. This motivates the design and analysis of the Fair Queueing resource scheduling discipline. We then study the efficient implementation of the discipline by doing an average case performance evaluation of several data structures for packet buffering. <p>Since a Fair Queueing server maintains logically separate pre-conversion queues and approximates a bitwise-round robin server, it partially decouples the service received by incoming traffic streams. This allows us to deterministically model a single conversation in a network of Fair Queueing servers. Analysis of the model shows that a source can estimate the service rate of the slowest server in the path to its destination (the bottleneck) by sending a pair of back-to-back packets (a packet-pair probe), and measuring the inter-acknowledgement spacing. The probe values can be used to control a user's data sending rate. We formalize this notion by modeling a conversation as a linear system in a simple control-theoretic approach. This is used to synthesize a robust and provably stable flow control protocol. The network state, that is, the service rate of the bottleneck, can be estimated from the series of probe values using an estimator based on elementary fuzzy logic. <p>Our analysis and performance claims are examined by simulation experiments on a set of eight test scenarios. We show that under a wide variety of test conditions, both of our schemes provide users with good performance. Thus, these mechanisms should prove useful in future high-speed networks.}
}

EndNote citation:

%0 Thesis
%A Keshav, Srinivasan
%T Congestion Control in Computer Networks
%I EECS Department, University of California, Berkeley
%D 1991
%@ UCB/CSD-91-649
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/6386.html
%F Keshav:CSD-91-649