CSAIL Event Calendar: Previous Series

Scheduling in "switched" networks

Speaker: Devavrat Shah , MIT, LIDS
Date: October 2 2007
Time: 4:15PM to 5:15PM
Location: 32--155
Host: Ronitt Rubinfeld, MIT

We consider networks in which simultaneous utilization of resources is constrained. Such networks can be used to model switch in an Internet router, wireless network, bandwidth sharing in the Internet or concurrency control in databases. The scheduling algorithm, that determines which resources are utilized at any point in time, affects the network performance in a crucial manner.

In this talk, we will present an optimal scheduling algorithm for such "switched" networks. We will describe how this algorithm "pops out" as a "formal limit" of a sequence of sub-optimal popular algorithms. We will also explain relation between algorithmic performance and the shape of effective network state space. Time permitting, we will discuss complexity of the optimal algorithm.

This talk is based on a joint work with Damon Wischik, University College of London.

See other events that are part of Theory Colloquium Fall 2007

See other events happening in October 2007