*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
