12:45 PM, Thursday, March 09, 2000
Room 104, Gates Computer Science Building

CHOKe: A simple router mechanism for Quality of Service

Balaji Prabhakar
Stanford University

About the talk:

The essential issue of providing differentiated QoS to individual users is the fair allocation of network resources among the users. The network can accomplish this by employing packet scheduling mechanisms like Weighted Fair Queueing (WFQ) at the switching nodes. It has been shown that these schemes effectively erect ``bandwidth firewalls'' between the flows of different users, thus guaranteeing that the QoS of one flow is not at the mercy of other flows. But schemes like WFQ suffer from ``the curse of dimensionality'': They require switches/routers to maintain flow state information for distinguishing the packets of individual flows. This renders them too complex to be used in large high speed networks.

In this talk I will present a simple randomized scheme for providing QoS to each of N flows that share the outgoing link of a congested router. The buffer at the outgoing link is a simple FIFO (hence the algorithm maintains no state), shared by packets belonging to all the flows. We devise a simple packet dropping scheme, called CHOKe, which drops more packets from flows that submit more packets/sec than is allowed by their fair share. We present some natural models for analyzing the scheme and discuss its implementation.

About the speaker:

Balaji Prabhakar is an assistant professor in the departments of Electrical Engineering and Computer Science at Stanford University.