Load Balancing with Memory

A standard load balancing model considers placing n balls into n bins by choosing d possible locations for each ball independently and uniformly at random and sequentially placing each in the least loaded of its chosen bins. It is well known that allowing just a small amount of choice (d = 2) greatly improves performance over random placement (d = 1). In this paper, we show that similar performance gains occur by introducing memory. We focus on the situation where each time a ball is placed, the least loaded of that ball's choices after placement is remembered and used as one of the possible choices for the next ball. For example, we show that when each ball gets just one random choice, but can also choose the best of the last ball's choices, the maximum number of balls in a bin is log log n/2 log /spl phi/ + O(1) with high probability, where /spl phi/ = (1 + /spl radic/5)/2 is the golden ratio. The asymptotic performance is therefore better with one random choice and one choice from memory than with two fresh random choices for each ball; the performance with memory asymptotically matches the asymmetric policy, using two choices introduced by Vocking (1999). More generally, we find that a small amount of memory, like a small amount of choice, can dramatically improve the load balancing performance. We also investigate continuous time variations corresponding to queueing systems, where we find similar results.

Authors

• Michael Mitzenmacher
• Balaji Prabhakar
• Devavrat Shah

Keywords

• Load management
• Performance gain
• Gold
• Switches
• Load modeling
• Grounding
• Routing
• Telephony
• Scheduling algorithm
• Algorithm design and analysis
• Load Balancing
• High Probability
• Random Placement
• Queueing System
• Random Choice
• Golden Ratio
• Large Differences
• Differential Equations
• Markov Chain
• Fixed Point
• Set Of Equations
• Time System
• Original System
• Service Rate
• Memory System
• Discrete System
• Local Memory
• Arrival Rate
• Real Size
• Use Of Memory
• Weak Policy
• Discrete Case
• Discrete Bins
• PROCESS Version