DYNAMIC SCHEDULING IN CONSTRAINED PROCESSING STRUCTURES: `Geometry' of Packet Scheduling in Communication Switches
Thursday, Sep. 26, 2002
2:00-3:30 p.m.
Hughes Room
We consider a processing system having several queues, which can be set to one of several service modes at any point in time. When the system is in a given mode, each queue receives service at some fixed mode-specific rate. Modes typically reflect resource contention constraints and operational entanglements among the various queues. We discuss some new general families of algorithms for dynamically choosing service modes for observed queue backlogs, so as to maximize the throughput of the system.

A special case of the above processing structure is that of input queued packet switches, which has attracted considerable interest lately. We discuss some applications of the general results to packet scheduling, which provide an interesting `geometric perspective' on maximal throughput algorithms for packet switches.

UC Berkeley Networking
Ashwin Pananjady and Orhan Ocal
Last Modification Date: Wednesday, February 10, 2016