Back to search

Georgia Institute of Technology

Crossbar scheduling algorithms for input-queued switches

Abstract

dc:description.abstract

Many of today's switches and routers adopt an input-queued crossbar architecture to interconnect the input ports with the output ports. Such a switch needs to compute a crossbar schedule, or a matching, between the input ports and the output ports during each switching cycle, or time slot. A key research challenge in designing large (in number of input/output ports N) input-queued crossbar switches is to develop crossbar scheduling algorithms that can compute high-quality matchings -- i.e., those that result in high switch throughput (ideally 100%) and low queueing delays for packets -- yet have a very low time complexity to support high link speeds. Indeed, there appears to be a fundamental tradeoff between the time complexity of the crossbar scheduling algorithm and the quality of the computed matchings (crossbar schedules). This dissertation research consists of two aspects. The first aspect is to investigate crossbar scheduling algorithms that are low in time complexities (preferably O(1) and definitely no more than O(logN) per port), yet have excellent throughput (ideally equal or close to 100%) and delay performances. The second aspect is to analyze the throughput and the delay performance guarantees of some of the proposed algorithms using Lyapunov stability analysis techniques. Along the first aspect, we have proposed four algorithms. The first algorithm, called SERENADE (SERENA, the Distributed Edition), is a parallel iterative algorithm that can provably, with a time complexity of only O(logN) per port, exactly emulate SERENA, a centralized algorithm with O(N) time complexity, which can attain 100% throughput and acceptable delay performance. The second algorithm, called Queue-Proportional Sampling (QPS), is an "add-on" approach that generates superior starter matchings than all other known strategies, yet incurs only O(1) additional time complexity at each input/output port. We use QPS to augment two existing crossbar scheduling algorithms, namely SERENA and iSLIP. The augmented algorithms, which we call QPS-SERENA and QPS-iSLIP, outperform the original algorithms by a wide margin, under various load conditions and traffic patterns. Building upon QPS, we propose the third algorithm, which we call QPS-r, a parallel iterative crossbar scheduling algorithm with O(1) time complexity per port. We have shown that QPS-3 (r=3 iterations) has comparable empirical throughput and delay performances as maximal matching algorithms that have much higher time complexities. The last algorithm, call Small-Batch QPS (SB-QPS), is a batch (crossbar) scheduling algorithm that builds upon and significantly improves the throughput performance of QPS-r, yet has a time complexity of O(1) per port (per time slot). Along the second aspect, we have proved, using Lyapunov stability analysis, that QPS-SERENA can achieve 100% throughput and that using matchings generated by QPS-r (even when r=1) as crossbar schedules results in at least 50% switch throughput and order-optimal (i.e., independent of the switch size N) average delay bounds for various traffic arrival processes.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Computer Science
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2020

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gong, Long
Advisor dc:contributor.advisor
  • Xu, Jun
Committee members dc:contributor.committeemember
  • Ammar, Mostafa H.
  • Zegura, Ellen W.
  • Maguluri, Siva Theja
  • Lin, Bill

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/63632

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Gong, Long. Crossbar scheduling algorithms for input-queued switches. Doctoral thesis, Georgia Institute of Technology, 2020. http://hdl.handle.net/1853/63632