Round Robin Can't See the Giant

In The Least Loaded Server Is a Rumor I argued that round robin, not random, is the baseline a load balancer has to beat, and that with load numbers a few service times old, plain round robin often wins. I ended with a caveat I hadn't tested: every job there had the same average size with a mild, exponential spread. Real jobs aren't like that. Most requests are quick and a few are enormous, and round robin can't see which is which.

So I measured it. The caveat turns out to be most of the story: with heavy-tailed jobs, round robin's advantage nearly disappears, and load information that is hundreds of service times old is still worth reading.

The setup

Same as before: 100 identical servers, each with its own first-come-first-served queue, jobs arriving at random, mean job size one service time, and the score is the mean time a job spends in the system. The board that dispatchers read shows each server's job count and is refreshed every T service times. One dispatcher, no tally of its own sends.

What changes is the spread of job sizes. I measure it with the squared coefficient of variation (SCV): the variance divided by the mean squared. Exponential sizes, as in the first post, have SCV 1. To get more spread I used a mix of two exponentials. At SCV 30, about 1 job in 61 is a giant averaging 30 service times and the rest average half a service time; the giants carry half of all the work. SCV 4 and 10 are milder versions of the same mix. I ran 12 seeds of 2 million jobs for every point.

Why not a Pareto distribution, the textbook heavy tail? I tried that too, and it's a trap for simulation. With a tail exponent of 2.2, random dispatch should average 55 service times at 90% load according to the exact formula for a single queue (Pollaczek–Khinchine), and two million jobs per run gave 38. The mean is driven by giants so rare that a finite run mostly doesn't meet them. The two-exponential mix has the same kind of variance without that problem: random dispatch at SCV 30 came out at 139.9 against the formula's 140.5, and at SCV 10, 51.1 against 50.5. The Pareto runs told the same story qualitatively; I'm just not quoting their numbers.

Round robin loses its edge

Mean time in system, in service times, at 90% load. Standard errors are under 2% everywhere.

With exponential jobs, round robin halves random's time. At SCV 30 it saves 5%.

The reason is in the shape of the queueing formula. Waiting time at a busy queue is roughly proportional to the variability of the arrivals plus the variability of the job sizes. Round robin removes almost all of the first: each server gets exactly every hundredth job, so its arrivals are nearly regular. With exponential jobs, arrival variability was half the total, so removing it halves the wait. With SCV 30, it was 1 part in 31. Round robin fixes the wrong half of the problem.

Best of two attacks the other half. It doesn't know job sizes either, only counts, but a server stuck behind a giant builds up a queue of small jobs, and a queue length is visible. At SCV 30 it is almost 9 times better than round robin. Least loaded with a live board does even better: 1.5, against 1.18 for an oracle that knows exactly how much work every server has left.

Old information stays useful

That's with a live board. The first post's real point was what happens when the board is old, so I swept the refresh interval from 1 to 500 service times.

Here's when each policy becomes worse than round robin:

T is the time between board refreshes, in service times. The ranges are the two grid points where the curve crosses round robin.

Going from exponential jobs to SCV 30 stretches the staleness budget by more than an order of magnitude. At 90% load, a best-of-two dispatcher reading a board refreshed every 10 service times averages 18.5 at SCV 30, seven times better than round robin. With exponential jobs, the same setup roughly ties it (5.1 vs 5.2).

My reading of why: the information that matters most is which servers are stuck behind a giant, and that fact changes on the time scale of a giant, not of an average job. A count that is 50 service times old still points at the server that's been grinding through one 30-unit job with a queue behind it. With exponential jobs nothing lasts that long, so an old count is mostly noise. I haven't tested this explanation beyond noticing that the curves move the right way.

Least loaded still herds: every job between refreshes chases the same few servers that looked empty. But the cost of that herd barely depends on job sizes. With a board 10 service times old at 90% load it averaged 22 to 25 at every spread I tried, while round robin grew from 5 to 132. So the herd is a fixed tax, and once job sizes are spread out enough (somewhere between SCV 4 and 10 at that staleness) it's cheaper than round robin's blindness.

What changes from the first post

• "With old information, just use round robin" holds only when job sizes are fairly uniform. With heavy-tailed jobs, even quite old queue counts beat it by a wide margin.
• Best of two is still the safe choice. It degraded gently at every spread and every staleness I tried, and it's the one that tolerates the oldest information.
• Round robin is still the right baseline to compare against. It's just a much weaker baseline when jobs vary a lot, so beating it proves less.
• If you simulate heavy tails, don't trust a Pareto mean from a finite run. Check it against the closed form first; mine was 30% low at two million jobs.

Limits: one dispatcher, identical servers, first-come-first-served queues, sizes independent of everything else. Real servers often share a processor among jobs instead of queueing them, and that changes how much a giant blocks everyone behind it. I'd expect it to shrink the gap. (Measured since: Sharing Servers Don't Mind the Giant. It does, by a lot.)