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

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

Ashwin Pananjady and Orhan Ocal

Last Modification Date: Wednesday, February 10, 2016