- About CS
- Future Students
- Current Students
- News & Events
- Active Learning: Nina Balcan Shores Up Foundations of Her Field
- Algorithm for Success: Zvi Galil Brings the Fire to Georgia Tech
- An Agile Architecture: Hyesoon Kim Looks to Combine CPUs & GPUs
- Box Seats in Atlanta: Fortnow Poised to Take School of CS to the Show
- Quantum Resistance: Chris Peikert & the Power of Lattices
- The People’s Network: Computing Students Work for More Transparent Internet
HomeARC Colloquium: Devavrat Shah, MIT
ARC Colloquium: Devavrat Shah, MIT
Add to Calendar
- May 31, 2012 3:00 pm
- Klaus 1116W
We consider a switched (queueing) network in which there are constraints on which queues may be served simultaneously; such net-works have been used to effectively model input-queued switches and wireless networks. The scheduling policy for such a network specifies which queues to serve at any point in time, based on the current state or past history of the system. As the main result, we provide a new class of online scheduling policies that achieve optimal average queue-size scaling for a class of switched networks including input-queued switches. In particular, it establishes the validity of a long-standing conjecture about optimal queue-size scaling for input-queued switches.
This is based on joint work with Neil Walton (Univ of Amsterdam) and Yuan Zhong (MIT).
Devavrat Shah is currently a Jamieson associate professor with the department of electrical engineering and computer science, MIT. He is a member of the Laboratory for Information and Decision Systems (LIDS) and Operations Research Center (ORC). His research focus is on theory of large complex networks which includes network algorithms and statistical inference. He has received 2008 ACM Sigmetrics Rising Star Award and 2010 Erlang Prize from the Applied Probability Society of INFORMS. He currently serves as an associate editor of Operations Research.