Scheduling for Communication and Processing Networks
1 hour 2 mins 48 secs,
220.08 MB,
Windows Media Video
44100 Hz,
478.46 kbits/sec
Share this media item:
Embed this media item:
Embed this media item:
About this item
Description: |
Walrand, J (UC, Berkeley)
Friday 15 January 2010, 11:00-12:00 |
---|
Created: | 2010-01-19 13:49 | ||
---|---|---|---|
Collection: | Stochastic Processes in Communication Sciences | ||
Publisher: | Isaac Newton Institute | ||
Copyright: | Walrand, J | ||
Language: | eng (English) | ||
Distribution: | World (downloadable) | ||
Credits: |
|
||
Explicit content: | No | ||
Aspect Ratio: | 4:3 | ||
Screencast: | No | ||
Bumper: | /sms-ingest/static/new-4x3-bumper.dv | ||
Trailer: | /sms-ingest/static/new-4x3-trailer.dv |
Abstract: | 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. |
---|
Available Formats
Format | Quality | Bitrate | Size | |||
---|---|---|---|---|---|---|
MPEG-4 Video | 480x360 | 1.84 Mbits/sec | 867.24 MB | View | Download | |
WebM | 480x360 | 755.89 kbits/sec | 343.25 MB | View | Download | |
Flash Video | 480x360 | 806.3 kbits/sec | 370.87 MB | View | Download | |
iPod Video | 480x360 | 505.19 kbits/sec | 232.37 MB | View | Download | |
QuickTime | 384x288 | 848.34 kbits/sec | 390.21 MB | View | Download | |
MP3 | 44100 Hz | 125.0 kbits/sec | 57.28 MB | Listen | Download | |
Windows Media Video * | 478.46 kbits/sec | 220.08 MB | View | Download | ||
Auto | (Allows browser to choose a format it supports) |