Back to search

NJIT

On scheduling input queued cell switches

Abstract

dc:description.abstract

Output-queued switching, though is able to offer high throughput, guaranteed delay and fairness, lacks scalability owing to the speed up problem. Input-queued switching, on the other hand, is scalable, and is thus becoming an attractive alternative. This dissertation presents three approaches toward resolving the major problem encountered in input-queued switching that has prohibited the provision of quality of service guarantees. First, we proposed a maximum size matching based algorithm, referred to as min-max fair input queueing (MFIQ), which minimizes the additional delay caused by back pressure, and at the same time provides fair service among competing sessions. Like any maximum size matching algorithm, MFIQ performs well for uniform traffic, in which the destinations of the incoming cells are uniformly distributed over all the outputs, but is not stable for non-uniform traffic. Subse-quently, we proposed two maximum weight matching based algorithms, longest normalized queue first (LNQF) and earliest due date first matching (EDDFM), which are stable for both uniform and non-uniform traffic. LNQF provides fairer service than longest queue first (LQF) and better traffic shaping than oldest cell first (OCF), and EDDEM has lower probability of delay overdue than LQF, LNQF, and OCF. Our third approach, referred to as store-sort-and-forward (SSF), is a frame based scheduling algorithm. SSF is proved to be able to achieve strict sense 100% throughput, and provide bounded delay and delay jitter for input-queued switches if the traffic conforms to the (r, T) model.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy in Electrical Engineering - (Ph.D.)
Discipline thesis:degree_discipline
Electrical and Computer Engineering

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Li, Shizhao
Contributors dc:contributor
  • Nirwan Ansari
  • John D. Carpinelli
  • Xiaoqiang Chen

Subjects

dc:subject × 3

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.njit.edu/dissertations/986

Chain of custody

source
Harvested from
NJIT
Base URL
digitalcommons.njit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Li, Shizhao. On scheduling input queued cell switches. https://digitalcommons.njit.edu/dissertations/986