Rayrole's algorithm

Rayrole's algorithm

Rayrole's algorithm is an algorithm for managing a resource reservation calendar [ [http://www.wikipatents.com/apps/20040204978.html Related US patent] ] .

It is used when a resource is shared among lots of users (for example bandwidth in a telecommunication link, or disk capacity in a large data center).

The algorithm allows
* to check if an amount of resource is available during a specific period of time,
* to reserve an amount of resource for a specific period of time,
* to delete a previous reservation,
* to move the calendar forward (the calendar covers a defined duration, and it must be moved forward as time goes by).

=Principle=The calendar is stored as a binary tree where leafs represent elementary time periods. Other nodes represent the period of time covered by all their descendants.


"Example of a 7-hour calendar (with elementary periods of one hour)"

The period of time covered by a reservation is represented by a set of "top-nodes". This set is the minimal set of nodes that exactly cover the reservation period of time.

A node of the binary tree is a "top-node" for a given reservation if
* all its descendants are inside the reservation period of time,and
* it is the root node, or at least one descendant of the parent node is outside of the reservation period of time.


"Top-nodes for a reservation from 1:00 to 5:59"

The following value is stored in each node: q(node) = max(q(left child), q(right child)) + total amount of reserved resource for all reservations having this node as a "top-node"(for code optimization, the two parts of this sum are usually stored separately.)

=Performance=The advantage of this algorithm is that the time to register a new resource reservation depends only on the calendar size (it does not depend on the total number of reservations).

Let "n" be the number of elementary periods in the calendar.

The maximal number of "top-nodes" for a given reservation is 2.log n.
* to check if an amount of resource is available during a specific period of time : O(log n)
* to reserve an amount of resource for a specific period of time : O(log n)
* to delete a previous reservation : O(log n)
* to move the calendar forward : O(log n + M.log n)where M is the number of reservations that are active during the added calendar periods.

(M = 0 if reservations are not allowed after the end of the calendar.)

External links

* [http://www.developpez.net/forums/showthread.php?p=3078887 C source code]

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”