Event Details

Congestion Price Estimation Using Probabilistic Packet Marking

Presenter: Jonathan Shapiro - Department of Computer Science, University of Massachusetts Amherst
Supervisor: Dr. R. Nigel Horspool, Chair, Department of Computer Science

Date: Mon, February 10, 2003
Time: 13:30:00 - 14:30:00
Place: CIT Building, room # 110

ABSTRACT

ABSTRACT:

The goal of congestion control protocols is to match the load offered by network users to the available capacity and to fairly allocate the capacity of bottleneck links. A class of recent analytical approaches to this problem--collectively known as optimization-based congestion control--adopt an economic framework in which network users are modelled as utility-maximizing agents and congestion feedback from the network as prices. By correctly setting these congestion prices, the network can drive its users toward a globally optimal bandwidth allocation. Congestion control protocols are seen in this framework as distributed algorithms for performing such an optimization, where each link adaptively sets its price and sessions make independent decisions knowing only the sum of link prices over their respective paths.

In this talk,I will focus on the problem of communicating the sum of link prices from the interior of the network to the edge. The Internet Protocol (IP) standard imposes a severe constraint on the design of practical protocols, namely, that only a single bit of the packet header--the explicit congestion notification (ECN) bit--is available for communicating congestion information to end-systems. This constraint can be addressed using 'probabilistic packet marking' algorithms to encode the sum of congestion prices over a path in the probability that the ECN bit is set at the path's end. In the main part of the talk, I will compare two such algorithms, one from the literature called 'random exponential marking' and a novel one I have developed called 'random additive marking'.

Time permitting, I will also briefly review other work I have done in the area of optimization-based congestion control.

Note: Mr. Shapiro is a candidate for a faculty position in the Department of Computer Science