PIP - Pick In Proportion

PIP - Pick in Proportion.

You need to deal out a stream of items one at a time in proportions.

You could use a round robin list. A,B,C,A,B,A,B,C,A,B,A,B,C

This idea uses a bank of numerical controlled oscillators.

You have an array of buckets, and these accumulate fill in the required proportions.

You have a bucket for each destination. The fullest bucket gets the Item and the bucket is emptied.

 OnItemRecieved{
   Add requiredProportionToBuckets()
   // Pick distination
   bucket = FindBucketWithMostFill()
   // Look for bucket with most fill, Thats the destination, and empty it.
   DeliverItemToDestination( bucket )
   EmptyFullestBucket( bucket )
 }

When you empty the bucket, do you add the sum of the buckets or the sum or the proportions.

Why are you picking in proportion?

Is it so that destinations get an exact equal share or just try to share the load when overloaded.

If time is added, then each timer tick, different proportions could be added to the bucket. How would this affect the result?

The Account Analogy

Get an income, when funds available buy the required item.

• There is a steady flow of income.
• Add this in proportion to each account.
• When the Account has enough to buy the item, buy it.

Another way.

What about BULK Buys where the cost on multiple items is less.

It might be we want a set of proportions, but it would be best to buy in bulk, or use in bulk.

It might cost more to use an item one at a time, so it may be best to hold back the purchase.

With Added Rate control

Add a leaky bucket on the output. If running, what do you do?

Empty the bucket if picked, but by more or less than the sum of proportions.

• If less is subtracted, it will get picked sooner again.
• If more is subtracted, it will get picked later again.

If Leaky Bucket running subtract Add an amount for Time

Names

• PIP Personal Improvement Plan
• PIP Pick In Proportion
• The PerfectPubRound

When you pick a bucket do you need to empty the whole bucket

You could measure the rate of OnItem Requests.

Could you have a bucket that backed off traffic, like the fairground penny fall profit.

Could you have a bucket that leaked.

If the bucket fill leaked, it would get picked more often. The leak could be negative.

OnItemReceived() - add proportions each item. OnLeak() - add proportions on timer tick, so they get picked.

When an Item is picked, subtract the sum of proportions from the bucket.

Should each bucket also have a time component? Should the bucket record when it was last emptied? If picked too often should it buffer and back off.

Links

http://www.dougrice.plus.com/Erlangs/loadShareTry.htm

http://www.dougrice.plus.com/Erlangs/loadShare.htm

http://www.dougrice.plus.com/Erlangs/loadShareMidi.htm

numerical controlled oscillators

This idea uses a bank of numerical controlled oscillators.

A numerical controlled oscillator uses a constant tick to increment a counter by a constant. When the counter overflows, toggle output.

 Fout = increment / 2^n * Fin

You have a counter or accumulator which you had a constant each tick.

numerical controlled oscillators with multiple clocks

What about two Fin, but one accumulator and two increments?

 Fout = ( increment1 * Fin1 + increment2* Fin2 ) / 2^n

Counters and clocks

You could have a counter that is clocked by two clocks.

 Fin1 provides Fin1 ticks per second 
 Fin2 provides Fin2 ticks per second 

 so ( Fin1+Fin2 ) counts per second

Fout = ( Fin1+Fin2 ) /2^n

Modified load share

I want to limit the rate a destination is picked.

For each bucket have another leaky bucket that leaks.

You can test if this is empty when adding the proportions.

If empty add proportion

If !empty // there are options

  option1: step over bucket. This will mean proportions are not maintained.
  option2: add less than the proportion to the bucket. This will mean proportions are not maintained.

  option3: add to bucket, but when picking the fullest bucket subtract a constant to stop it being picked. 
  option4: add to bucket, but when picking the fullest bucket skip it being picked. Deferred Payment. 
  option5: add to sister bucket and add sister bucket to main bucket when leak empties.

If the input event rate is greater that ( wanted destination rate * proportion ), then there is congestion.

I tried option4 and it has problems.

http://www.dougrice.plus.com/Erlangs/loadShareTryUpdate.htm - update of origiinal with more buckets and proportions

http://www.dougrice.plus.com/Erlangs/loadShareTryLeak.htm - option 4 - has issues.

When a bucket is picked, I subtracts the Sum of the Fills. Some fills go negative, which is okay, but these get big.

Maybe limiting the fill to being positive, and start the fills with the Sum of proportions?