leaky bucket load share using the equitable pub round algorithm.

Here is a load share using leaky buckets. This is similar to the equitable pub round algorithm, where the person who drinks the most picks up the round most often.

You and some mates walk into the pub, however, some only drink halves, some drink pints, and each person is supposed to pick up their round fairly.

One person buys the round, and each person is credited the cost of their drink. The person with the most credit buys the next round, and the total cost is subtracted from their credit. Hopefully the person who is costing the most buys the round most often.

A load share splits a stream of events into several streams with different proportions.

You have a stream of events that you wish to split into streams using different proportions or parts. Have a bucket for each stream.

For each event fill the buckets at the wanted parts (proportions). To pick the stream to send the event down, pick the fullest bucket and take out a dollop equal to the sum of the parts. ( The fill may go neagtive ) This should work for ever if using integers. Rounding errors may be a problem if using floats.

Input a list of parts (proportions).
After this number of events change the proportions to these.
new parts (proportions). NOTE buckets are not emptied.
recalculate | Mashup to demo this to generate Midi sequences

Simulation showing bucket fills after each event, but before dollop taken out


Here is the function called once per event:
function doAnEvent(){
  var totalWants   = 0
  var totalBuckets = 0
  var maxBucket    = 0   
  var maxBucketCnt = 0

  // each output stream has it's own bucket.
  // for each event put a dollop of water equal to the (parts ) portions wanted into each stream's bucket
  for ( var cnt=0; cnt < wantA.length ; cnt++ ){
    bucketsA[cnt] -= -wantA[cnt]*1

    // work out the totals
    totalWants   += wantA[cnt]*1
    totalBuckets += bucketsA[cnt]*1

    //is this bucket the fullest.
    // look for the max, or last equal one.
    if ( bucketsA[cnt] >= maxBucket ) {
      maxBucketCnt = cnt  
      maxBucket = bucketsA[cnt] 
    }
  }

  // For the stream picked, take out a dollop from it's bucket equal to the sum of the parts.
  //bucketsA[maxBucketCnt] -= totalWants*1


  // instead, if you subtract the sum of the fill of the buckets, it removes rounding errors if any.
  bucketsA[maxBucketCnt] -= totalBuckets*1  
}

A load share using the error technique.

You have a set of want percentages between 0 to 100% expressed as integers between 0 and 100. You maintain a count of the number of events offered to each destination. You maintain a totalCounts which is the sum of the counts.

Assume the traffic has been distributed to the wanted proportions, so the counts reflect this.

Start by putting the want percentages into each count. e..g if you want 25%,50%,25% to three destinations, put 25,50,25 into each count, and work out totalCounts and totalWants.

Now for each event do:

2) Work out the actual percentages by dividing each count by the totalCounts.

3) You now have the proportions. How close are these to the want proportions, so work out a normalised error.

4) To work out the normalised errors, for each count divide it by the corresponding want proportions. ( look out for divide by zero errors when the want proportion equals zero. Assume error = 0 )

5) The one with the biggest normalised error is the one to choose next.

6) Use this destination and increment it's count, and increment totalCounts.

7) When ( totalCounts > 2* totalWants ) subtract the wants from the corresponding counts. After this totalCounts will equal totalWants again.

This maintains the event distribution to the wanted integer percentages. The want percentages could be want parts instead, so you could have want parts of 1,1,1 for 1/3,1/3,1/3 distribution of the traffic.