On 9/27/10 7:44 PM, Juha Heinanen wrote:
Daniel-Constantin Mierla writes:
maybe there are other options, but here is what I did for dispatcher weighted load balancing:
- each destination set has associated an array of 100 integers
- when destination set is loaded, this array is filled with indexes of
destination addresses in the set as many times as associated weight value
- when this array is filled, the content is randomized
daniel,
this is the same algorithm that i was looking at to implement only that i was thinking to use an array that was long enough to hold the sum of the weights.
At runtime, a position of the last used index in array is keep, incremented and looped again over the array. During the load the 100-indexes array is traversed 2 times, once to fill and second to radomize, but then selection is very fast at runtime, which is more important for a load balancer, since loading is done very rarely and in MI/RPC process, in parallel with normal operation using old data.
in case of lcr, things are more complicated, because in the set of matching gateways for a destination, gws are ordered first based on prefix length, then based on priority and finally based on randomized weight. so there should be several of those arrays. also, the arrays would need to be created and organized every time load_gws() is called, i.e., once per call. this would result in lots of code lines and performance hit at load_gws() call.
the script that i wrote can be used to figure out the desired weights without any implementation complexity. just a single rand() call for each matching gw and a single qsort() call for the set is all that is needed. so, for now, i'll include the script in the tools dir and reference it in lcr README.
you can create as well an utils or tools directory inside lcr module folder, that will suggest direct relation with the module.
Cheers, Daniel