Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Weighted Load Balancing Algorithm

IP.com Disclosure Number: IPCOM000033400D
Original Publication Date: 2004-Dec-09
Included in the Prior Art Database: 2004-Dec-09
Document File: 2 page(s) / 86K

Publishing Venue

IBM

Abstract

This publication is about a weighted load balancing algorithm that allocates a request to each server at least once. It also has an upper limit to the execution time of a cycle, which is the time needed for all servers to be picked at least once. With this algorithm, each server will be allocated a number of requests that is proportional to its weight throughout a cycle. Additionally, the algorithm scales well as the number of servers increases, regardless of the differences between the weights allocated to the servers.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 59% of the total text.

Page 1 of 2

Weighted Load Balancing Algorithm

The following table represents the data structures used during one cycle and each step of the algorithm applied to a configuration where there are 3 servers and they have weights 6, 3, and 3 respectively.

                                        selectServerFrom generatedIndex selectedServer arrayLength 0 1 2 3 4 5 6 7 8 9 10 11 step 1 2 1 12 1 1 1 1 1 1 2 2 2 3 3 3 step 2 8 2 11 1 3 1 1 1 1 2 2 2 3 3 3 step 3 4 1 10 1 1 1 1 1 3 2 3 2 3 step 4 1 1 9 1 1 1 3 1 3 2 3 2 step 5 6 3 8 1 1 2 1 1 3 2 3 2 step 6 3 2 7 1 1 2 3 1 3 2 3 step 7 2 1 6 1 1 2 3 1 3 step 8 1 1 5 1 3 2 3 1 step 9 3 2 4 1 3 2 3 step 10 2 3 3 1 3 3 step 11 2 1 2 1 3 0 step 12 1 1 1 1 0 0

selectServerFrom. This array is shown on the right hand side of the table. It keeps track of the server list from which the load balancer can select a server to send a request to at each step of the cycle. This list reflects those servers that did not have their share of load yet compared to the weights they were given initially and the requests that were sent to them during the cycle being executed. Initially, this array contains as many times 's' as the weight of server s. For example, server 1 appears 6 times because it has weight 6, and the servers 2 and 3 appear 3 times because each has weight 3. This means that the load balancer can select server 1 6 times and servers 2 and 3 3 times each because no request was sent to them yet. arrayLength. This variable keeps track of the relevant part of the array selectServerFro...