Abstract:

Iterative scheduling algorithms for input-queued switches are efficient due to the use of massive parallel processing. Single-iteration scheduling algorithms can further minimize the scheduling overhead. Based on the principle of highest rank first (HRF), a new approach of designing single-iteration scheduling algorithms will be discussed in this talk. In particular, three algorithms will be covered, HRF-basic, HRF-refined and HRF-RC. In HRF-basic, VOQs at an input port are ranked according to their queue sizes. The rank of a VOQ, coded using log(N+1) bits where N is the switch size, is sent to the corresponding output as a request. If there are more than one requests/grants, the arbitration at an output/input is based on highest rank first. We show that HRF-basic outperforms the longest queue first (LQF) algorithm. To further enhance the performance of HRF-basic under heavy load, HRF-basic is combined with an implicit global round robin scheduler to form the HRF-refined algorithm. To cut down the request message size to single bit, the HRF with Request Coding (HRF-RC) algorithm is designed. Notably, existing single-bit-request algorithms convey two VOQ states to an output, “empty” or “nonempty”. In HRF-RC, a single-bit-request is used to indicate the increase or decrease of the VOQ rank. With a joint consideration of past single-bit-requests received, we show that HRF-RC achieves a comparable performance as HRF-refined.

Bio:

Lawrence Yeung received his B.Eng. and Ph.D. degrees in Information Engineering from The Chinese University of Hong Kong in 1992 and 1995, respectively. He joined the Department of Electrical and Electronic Engineering, The University of Hong Kong in July 2000, where he is currently a Professor. Lawrence’s research interests include wireless data networks, next-generation Internet, packet switch/router design, and all-optical networks.

Host:

Dr. Alex Liu