Scheduling for Communication and Processing Networks
Seminar Room 1, Newton Institute
AbstractThe 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.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.