Load balancing and switch scheduling

Xiangheng Liu, Andrea Goldsmith

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations

Abstract

Packet switching remains one of the bottlenecks in building fast Internet routers. Load balancing and switch scheduling are two important algorithms in the effort to maximize the throughput and minimize the latency of these packet switches. A load balancing algorithm regulates the traffic to conform to the service rates while a switch scheduling algorithm allocates the service rates adaptive to the arrival patterns. Many existing load balancing and switch scheduling algorithms are very similar. We show that load balancing and switch scheduling systems are dual systems based on the linear queue dynamics approximation. This allows us to cast a load balancing problem as a scheduling problem, and vice versa. We further show an example of designing a new algorithm for load balancing using an existing scheduling algorithm based on the duality. The duality perspective also allows us to solve unknown problems. We find the entropy rate of the randomized bandwidth allocation system with linear queue dynamics based on the knowledge of the entropy rate of the randomized load balancing system. For the general case, we find both an upper and a lower bound on the entropy rate. The joint use of dual load balancing and switch scheduling algorithms leads to performance gains as we show using mean field analysis.

Original languageEnglish (US)
Article numberGC09-2
Pages (from-to)1010-1014
Number of pages5
JournalIEEE International Conference on Communications
Volume2
StatePublished - 2005
Externally publishedYes
Event2005 IEEE International Conference on Communications, ICC 2005 - Seoul, Korea, Republic of
Duration: May 16 2005May 20 2005

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Keywords

  • Communication Switching
  • Duality
  • Entropy Rate
  • Load Balancing
  • Switch Scheduling

Fingerprint Dive into the research topics of 'Load balancing and switch scheduling'. Together they form a unique fingerprint.

Cite this