Load Balancer

Brokers in a distributed publish/subscribe system located at different geographical areas may suffer from uneven load distribution due to different population densities, interests, and usage patterns of end-users. A broker in a hotspot area where there is high message traffic resulting from a large number of publishers and subscribers may get overloaded from excessive processing or bandwidth requirements. In both cases, queues accumulate with increasingly more messages waiting to be processed, resulting in increasingly higher processing and delivery delays. Worse yet, a broker may crash when it runs out of memory from queueing too many messages. A load balancing solution can help in this scenario by dynamically offloading clients to less loaded brokers, as illustrated by the picture below:

• With and without load balancing:
  

The load balancing solution consists of the detector, mediator, load estimation tools, and offload algorithms (shown below) that determine which subscribers to offload. The detector detects and initiates a trigger when an overload or load imbalance occurs. The trigger from the detector tells the mediator to establish a load balancing session between the two entities, namely offloading broker (broker with the higher load doing the offloading) and the load-accepting broker (broker accepting load from the offloading broker). Depending on which performance metric is to be balanced, one of the offload algorithms is invoked on the offloading broker to determine the set of subscribers to delegate to the load-accepting broker based on estimating how much load is reduced and increased at each broker using the load estimation algorithms. Finally, the mediator is invoked to coordinate the migration of subscribers and ends the load balancing session between the two brokers.

• Load balancer modules:
  

The load balancing algorithm meets the following 5 strong properties:

1. Dynamic – load balancing can be invoked anytime when overload or uneven load distribution is detected
2. Adaptive – a distinct offload algorithm designed to load balance on each type of resource
3. Heterogeneous – account for brokers with different resource capacities and subscriptions subscribing to different publication sets
4. Distributed – scalability of load balancing algorithm and the pub/sub infrastructure
5. Transparent – publishers and subscribers are not aware about load balancing

Experimental results show that the PADRES load balancing solution is well-controlled and effective at reducing high processing delays resulting from overload conditions while at the same time imposes minimal overhead.

• Client perceived delivery delay:
  

• Scalability on the number of edge brokers:
  

More details on the load balancing algorithm can be found in the paper published at the ACM Middleware 2006 conference at Melbourne, Australia.