University of Cambridge > > Isaac Newton Institute Seminar Series > Scheduling for Communication and Processing Networks

Scheduling for Communication and Processing Networks

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Mustapha Amrani.

Stochastic Processes in Communication Sciences

The talk reviews the history and recent results on the scheduling of tasks that require access to a set of resources. The first step was the discovery that maximum weighted matching achieves the maximum throughput for a class of such scheduling problems that includes wireless networks and packet switches. However, this algorithm is too complex to be directly applicable. The second step was understanding when a simpler algorithm, longest queue first, also achieves maximum throughput. The third step was inventing a distributed algorithm where tasks select an independent random back off delay before asking for the resources; this delay has a mean value that decreases exponentially with the backlog. Using stochastic approximation theory, one shows that this algorithm achieves the maximum throughput. The fourth step is a modification of maximum weight matching to achieve the maximum utility in a processing network where tasks not only share resources but also require access to parts. The talk explains the intuition behind the results and the main ideas of the proofs.

This talk is part of the Isaac Newton Institute Seminar Series series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2023, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity