Packet Scheduling Over Multiple Communication Channels

Speaker:	Professor Laxmi Narayan Bhuyan
		Department of Computer Science and Engineering
		University of California, Riverside

Title:		"Packet Scheduling Over Multiple Communication Channels"

Date:		Thursday, 14 September 2006

Time:		11:am - 12 noon

Venue:		Room 2404 (via lift nos. 17/18)
		HKUST

ABSTRACT:

Scheduling packets across multiple transmission entities (e.g. link
aggregation) or processing elements (e.g. network processors) is a
challenging problem. This problem is crucial to many applications (that
utilize parallel communication or processing paths) like multi-path
wireless channels, multi-path routing, data processing by network
processors, and trans-coding multimedia flow traffic content over the
Internet, to name a few. The aim of our research is to design packet
scheduling algorithms for multilink systems that reduce packet reordering,
and ensure fair sharing of flows and result in optimal utilization of the
links.

In this talk, we first propose a Dynamic Batch Co-Scheduling (DBCS) scheme
to schedule packets in a heterogeneous multilink system assuming that the
workload is perfectly divisible. The processed loads from the processors
are ordered perfectly. We analyze the throughput and derive expressions
for the batch size, scheduling time and maximum number of schedulable
processors. To effectively schedule variable length packets, we propose a
Packetized Dynamic Batch Co-Scheduling (P-DBCS) scheme by applying a
combination of deficit round robin (DRR) and surplus round robin (SRR)
schemes. We extend the algorithm to handle multiple flows based on a fair
scheduling of flows depending on their reservations. Extensive sensitivity
results are provided through analysis and simulation to show that the
proposed algorithms satisfy both the load balancing and in-order
requirements in packet processing.


**********************
Biography:

Laxmi Narayan Bhuyan is a professor of Computer Science and Engineering at
the University of California, Riverside since January 2001. Prior to that
he was a professor of Computer Science at Texas A&M University (1989-2000)
and Program Director of the Computer System Architecture Program at the
National Science Foundation (1998-2000). He has also worked as a
consultant to Intel and HP Labs. Dr. Bhuyan received his Ph.D. degree in
Computer Engineering from Wayne State University in 1982. His current
research interests are in the areas of network computing, multiprocessor
architectures, router and web server architectures, parallel and
distributed processing, and performance evaluation. He has published more
than 150 papers in these areas in IEEE Transactions on Computers (TC),
IEEE Transactions on Parallel and Distributed Systems (TPDS), Journal of
Parallel and Distributed Computing (JPDC), and many refereed conference
proceedings.

Dr. Bhuyan currently serves as the Editor-in-Chief of the IEEE
Transactions on Parallel and Distributed Systems (TPDS). He is a past
Editor of the IEEE TC, JPDC, and Parallel Computing Journal. His
professional activities are too numerous to describe. To mention a few, he
was the founding Program Committee Chairman of the HPCA in 1995, Program
Chair of the IPDPS in 1996, General Chair of ADCOM-2001, and General Chair
of HPCA-9 (2003). He was elected Chair of the IEEE Computer Society
Technical Committee on Computer Architecture (TCCA) between 1995-1998.

Dr. Bhuyan is a Fellow of the IEEE, a Fellow of the ACM, a Fellow of the
AAAS (American Association for the Advancement of Science), and a Fellow
of the WIF (World Innovation Foundation). He has also been named as an ISI
Highly Cited Researcher in Computer Science. He has received other awards
such as Halliburton Professorship at Texas A&M University, and Senior
Fellow of the Texas Engineering Experiment Station. He was also awarded
the IEEE CS Outstanding Contribution Award in 1997.