Capacity, queues and complexity in stochastic networks


Stochastic (processing) networks have served as canonical model to design and analyze algorithms for communication
networks such as the telephone network and the Internet.Most such algorithms are for resolving contention of some
form between various entities contending to utilize constrained resources. Desired performance includes (i) efficient utilization of resources or high in capacity, (ii) low average latency or equivalently small average queue-sizes, and (iii) implement-abilityor low computational complexity with minimal data structure.

In this talk, I will discuss the interplay between these three performance metrics by means of an example. The focus will be on the maximum weight policy, originally introduced by Tassiulas and Ephremides (1992), and its variants.

The talk will survey results based on joint works (in chronological order) with (a) Damon Wischik, UCL; (b) Jinwoo Shin, MIT; and (c) David Tse, UC Berkeley and John Tsitsiklis, MIT.