8 - Load Balancing

Question 1

Where might load balancing apply?

Answer 1

Master-worker parallel computation
Traffic management
Collision avoidance

Question 2

Challenges of load balancing

Answer 2

Procedure complexity
Outdated info
Fault Tolerance
Scalability
Heterogeneous hardware - different speeds/capacity

Question 3

Static load balancing

Answer 3

Doesn’t consider state
All set in advance

Question 4

Static: Attributes

Answer 4

Do not change
Tasks needed to be regular

Question 5

Round robin algorithm

Answer 5

Assign next ball to next bin then start again

Question 6

Weighted round robin

Answer 6

A larger bin is given more balls/jobs

Question 7

Round Robin General problem

Answer 7

State not being considered means that jobs with different durations/temporarily slow servers affect it.

Question 8

Simple Randomised

Answer 8

For each ball, choose a random bin. No state info

Question 9

Simple randomised: Examples

Answer 9

Client side load balancing - randomly choose ip
Hash tables - hash value can be used

Question 10

Hash function with n buckets

Answer 10

Simple using modulo eg h(ID) = ID mod n

30 for 6 buckets = 0
11 = 5

Question 11

Random vs Hash

Answer 11

Random cannot find same item again
Hashing; item can be found knowing ID and hash function

Question 12

Dynamic Load Balancer

Answer 12

Based on current state.
Can move tasks where necessary
Allows greater modularity

Question 13

Least loaded Bin

Answer 13

Server side balancer forwards request to backends.

Question 14

Least time allocation

Answer 14

Allocation to bin that will serve at earliest time. Considers speed and queues

Question 15

Multiple Dispatcher Problem

Answer 15

They will send their request to the same server (herd behaviour) and has opposite effect on performance.

Question 16

Goren et al Multi dispatch solution

Answer 16

Round based algorithm. Allocate to bins based on probabilities in current round.

Need to know server queues, processing rates and job arrival rates

Question 17

Dynamic Randomised

Answer 17

Choose multiple random bins, allocate the ball to the bin of lowest load

Question 18

Power of two choices improvements

In terms of m balls and n bins

Answer 18

Case m = n: Exp improvement
Case m > n: Max load above avg is independent of num balls m

Question 19

When does multiple-choice lose some power?

Answer 19

In parallel settings

Question 20

Parallel Scenario

Answer 20

Balls arrive in batches of n
Allocated using GREEDY[d] but bin loads only updated between batches.
Decisions may be based on outdated load info

Question 21

g-bounded process

Answer 21

Allocated using two choices, but if load difference is g or less then process makes mistake.

Question 22

Gap between average load in parallel, 1 + β process and g-bounded scenario

Answer 22

Independent of m (number of balls)

Question 23

1 + β process

(balls into bins)

Answer 23

Some balls allocated using 2 choices, the rest using 1.

2 bins queries, and with probability 1 - β, ball is allocated to random bin. 1+ β choice for each ball

Question 24

Probability that none of m = n balls fall into particular bin

Answer 24

1/e

Question 25

Expected number of empty bins

Answer 25

n/e

This is greatly simplified process

Question 26

Collision

Answer 26

Any two or more balls falling into one bin

Question 27

Bernoulli Process (probability that ball falls into bin and doesn’t)

Answer 27

Ball falls into bin: 1/n
Ball does not fall into bin: 1 - 1/n

Question 28

Probability of at least k balls

Answer 28

(e/k)^k

Question 29

Maximum load in any bin

Answer 29

At most (3ln(n))/ln(ln(n))

High probability is 1 - o(n)

Question 30

Distributed hash table

Answer 30

Set of nodes that store items

Question 31

Chord

Answer 31

Nodes organsied in logical ring with N nodes

Question 32

Scalable key location run time

Answer 32

O(log(N))

Every shortcut cuts distance at least in half.

Question 33

Chord: Adding a Node x

Answer 33

Let y successor of x.
Move items at y that belong to x to x
Update finger tables

Question 34

Chord: Removing a node

Answer 34

(Move items to successor)
Let y be successor of x
Move items of x to y
Update finger tables

Question 35

Chord: Advantages

Answer 35

Scalable
Small routing tables
Fully decentralised

Question 36

Is a chord well load-balanced?

Answer 36

No - different arc lengths.

Eg node 28 is assigned everything from 22 to 28. 21 only items hashed to 21

Question 37

Load balancing a Chord

Answer 37

Map every node to r cycle points
r arcs per node = distribution is more even