Browse Prior Art Database

Well-balanced, efficient, weighted round-robin algorithm

IP.com Disclosure Number: IPCOM000132177D
Original Publication Date: 2005-Dec-05
Included in the Prior Art Database: 2005-Dec-05
Document File: 2 page(s) / 54K

Publishing Venue

IBM

Abstract

A time- and memory-efficient round-robin algorithm is described which generates a sequence of two symbols with parameterized weightings. The generated sequence is of minimal length and avoids long runs of either symbol. The algorithm may be generalized to many symbols and associated weightings.

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

Page 1 of 2

Well-balanced, efficient, weighted round-robin algorithm

Disclosed is a weighted round-robin algorithm, generating a sequence of two symbols with parameterized weightings. The algorithm efficiently generates a shortest possible sequence giving the required weightings. Any chosen subsequence will contain the symbols in approximately the chosen weightings.

  It is often necessary to distribute work between two or more systems, according to some weighting assigned to them. For example, if one system is twice as powerful as another, there can be a requirement to distribute twice as much work to the more powerful of the two. Similarly, it may be necessary to select a handful of requests from a running high-throughput system, perhaps for audit. In these, and many other situations, a sequence of symbols (for example, one symbol representing the more powerful system, another symbol representing the lesser system) is required to be generated within which each symbol appears with a given frequency.

  The algorithm described herein generates a sequence of two symbols ('A' and 'B') with given (integer) weightings. The algorithm has the following desirable properties:

The sequence generated is the shortest possible given the weightings: the length is the sum of the weights, divided by their greatest common divisor (gcd). The algorithm can therefore be run in advance of performance-intensive processing, generating a finite sequence which can be later (and repeatedly) quickly traversed.

The sequence is well-balanced; meaning that any subsequence will approximate the weightings. This means that the generated sequence may be partially used without scarificing the weighting requirement. The sequence avoids long runs of either symbol where possible.

The algorithm generates each symbol in constant time, meaning it may be efficiently used during processing rather than ahead of processing.

The algorithm operates within constant memory (unless its output is written into a buffer, in which case memory usage has the output sequence length as its complexity.

The algorithm can be implem...