Scheduling for Communication and Processing Networks
1 hour 2 mins 34 secs,
57.28 MB,
MP3
44100 Hz,
125.0 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) | |||||