Scheduling algorithms for high performance packet switches

2007 2007

Other formats: Order a copy

Abstract (summary)

Switches and routers play important roles in providing high performance network service to end users. With the ever increasing demand for higher bandwidth and better service, it has become a more and more challenging task to design efficient scheduling algorithms for high performance switches. Based on the locations to buffer blocked packets, packet switches can be divided into several different categories: output queued (OQ) switches, input queued (IQ) switches, combined input-output queued (CIOQ) switches, and buffered crossbar switches.

In this dissertation, we design a series of efficient scheduling algorithms for different types of packet switches, analyze their performances, and discuss implementation issues. Firstly, for IQ switches, we propose a general method to convert traditional three step iterative matching algorithms to two step algorithms, which have implementation advantages and maintain identical performances. We theoretically prove the average convergence iteration number for iterative matching algorithms, and show by simulation that it is more accurate than the classical result. On the other hand, to efficiently buffer multicast packets in IQ switches, we present a novel queue structure by separately storing the address information and data information of a packet. In conjunction with the new multicast queue structure, we design a first-in-first-out based multicast scheduling algorithm called FIFO Multicast Scheduling (FIFOMS), which achieves low latency and high throughput for multicast traffic. Secondly, in order to apply two step algorithms to CIOQ switches, we propose a pipeline scheme called Second of Line (SOL) matching. It makes two scheduling decisions in every time slot without extra scheduling time or arbitration hardware. Any two step iterative matching algorithm can be efficiently pipelined with the proposed scheme, and furthermore achieves 100% throughput for any admissible traffic. Thirdly, for buffered crossbar switches, we propose the Localized Asynchronous Packet Scheduling (LAPS) algorithm that schedules variable length packets without segmentation-and-reassembly. It has the nice property to guarantee 100% throughput for any admissible traffic, as well as many implementation advantages. Finally, we consider how to fairly allocate bandwidth in packet switches to facilitate performance guarantees. We formulate the problem based on the max-min fairness principle, and present solution algorithms for unicast traffic and multicast traffic, respectively. The proposed algorithms are universally applicable to any type of switches and scheduling algorithms.

Indexing (details)

Computer science
0984: Computer science
Identifier / keyword
Applied sciences; Multicast scheduling; Packet switches; Scheduling
Scheduling algorithms for high performance packet switches
Pan, Deng
Number of pages
Publication year
Degree date
School code
DAI-B 69/10, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
State University of New York at Stony Brook
University location
United States -- New York
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.