Packet scheduling in networks with fixed-size buffers

Mahmoud Elhaddad (Pitt/CS)

PhD Proposal Defense

Friday, November 30th, 2007
2:30pm - SENSQ 6106 - Eli Lilly

Abstract

In packet networks where buffers have small fixed capacity, the packet loss  rate (proportion  of packets  that are  dropped) is  the primary metric  for the evaluation  of work-conserving  scheduling algorithms.
In  this research,  we look  at some  fundamental  scheduling problems related to  minimizing the loss rate and  its variants.  Surprisingly, to date  this area of  research has remained largely  unexplored, with only few known results.

The first  part of the  thesis deals with  the analysis and  design of online  scheduling  algorithms  for  networks  of  output-queued  (OQ) routers---a router architecture where arriving packets are immediately switched to the outputs  for buffering and transmission.  In practice, however, most  routers employ  combined input-output queuing  (CIOQ) to reduce the required internal router speed.  This entails the use of an arbitration policy to decide which  packets are switched to the router outputs  at  every   time  step.   The  second  part   of  the  thesis investigates arbitration policies with the objective of minimizing the input  buffer  capacity  required   for  the  exact  emulation  of  OQ scheduling algorithms in CIOQ routers.

In the proposed thesis my goal is to show that: (1) a family of simple scheduling algorithms that treat sessions fairly at every network link provides  (nearly) optimal  guarantees  for multiple  loss metrics  of practical  interest,  and  (2) such  algorithms  can  be  realized  in practical routers  with small increases  in internal speed and  in the required buffer capacity.

Dissertation CO-AdviserS

Prof. Taieb Znati, Department of Computer Science
Prof. Rami Melhem, Department of Computer Science

Committee Members

Prof. Kirk Pruhs, Department of Computer Science
Prof. Devavrat Shah, MIT