Title: Crossbar Scheduling Algorithms for Input-Queued Switches

Long Gong
Ph.D. student
School of Computer Science
Georgia Institute of Technology

Date: Tuesday, Nov 12, 2019
Time: 11 a.m. - 1 p.m. (Eastern Time)
Location: KACB 2108

Committee:
---------------
Dr. Jun (Jim) Xu (Advisor, School of Computer Science, Georgia Institute of Technology)
Dr. Mostafa H. Ammar (School of Computer Science, Georgia Institute of Technology)

Dr. Ellen W. Zegura (School of Computer Science, Georgia Institute of Technology)

Dr. Siva Theja Maguluri (School of Industrial and Systems Engineering, Georgia Institute of Technology)

Dr. Bill Lin (Department of Computer Science and Engineering, University of California, San Diego)

Abstract:
------------
Switches and routers today primarily employ an input-queued (IQ) crossbar architecture to interconnect the input ports with the output ports.  In an IQ switch, a crossbar schedule, or a matching between the input ports and the output ports needs to be computed for each switching cycle, or time slot. It is a challenging research problem to design crossbar scheduling algorithms that can produce high-quality matchings -- those resulting in high switch throughput and low queueing delays -- yet have a very low computational complexity when the switch has a large number of ports.  Indeed, there appears to be a fundamental tradeoff between the computational complexity of the matching (scheduling) algorithm and the quality of the computed matchings.

This thesis proposal consists of two aspects. The first aspect is to investigate next-generation bipartite matching algorithms for crossbar scheduling, that are low in computational complexities (preferably O(1) and definitely no more than O(log N) per port), yet have excellent throughput and delay performances. The second aspect is to rigorously analyze the throughput and the delay performance guarantees of the proposed algorithms using existing or yet-to-be-developed mathematical techniques. Building on our recent breakthroughs along the line of research on designing next-generation bipartite matching algorithms for crossbar scheduling and the knowledge we have acquired through their discoveries. First, we propose a batch scheduling algorithm that appears to have all the desired properties of next-generation crossbar scheduling algorithms mentioned above. Second, we propose to investigate the throughput and the delay performance guarantees of this algorithm.