Top-nodes algorithm: Difference between revisions

Revision as of 23:11, 20 May 2009

Latest revision as of 13:34, 5 October 2022

(25 intermediate revisions by 24 users not shown)

Line 1:

The '''Rayrole'stop-nodes algorithm''' is an [[algorithm]] for managing a resource reservation calendar. The algorithm has been first published in 2003,<ref>[https://archive.today/20120215024923/http://www.wikipatents.com/apps/20040204978.html Related US patent] (the algorithm is in the public ___domain since 2008)</ref> and has been improved in 2009.<ref>[https://www.researchgate.net/publication/311582722_Method_of_Managing_Resources_in_a_Telecommunication_Network_or_a_Computing_System Improved top-nodes algorithm]</ref> It is used when a resource is shared among many users (for example [[Bandwidth (signal processing)|bandwidth]] in a [[telecommunication]] link, or [[disk capacity]] in a large [[data center]]).

The algorithm allows users to:

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).

* 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 algorithm allows

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

* to check if an amount of resource is available during a specific period of time,

<center>[[ImageFile:AlgoRayroleArbre.jpgsvg|center|Example of a 7seven-hour calendar (with elementary periods of one hour)]]</center>

* to reserve an amount of resource for a specific period of time,

<{{center>|''Example of a 7seven-hour calendar (with elementary periods of one hour)''</center>}}

* 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.

<center>[[Image:AlgoRayroleArbre.jpg|Example of a 7-hour calendar (with elementary periods of one hour)]]</center>

<center>''Example of a 7-hour calendar (with elementary periods of one hour)''</center>

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

and

* it is the root node, or at least one descendant of the parent node is outside of the reservation period of time.

<center>[[ImageFile:AlgoRayroleResa.jpgsvg|center|Top-nodes for a reservation from 1:00 to 5:59]]</center>

<{{center>|''Top-nodes for a reservation from 1:00 to 5:59''</center>}}

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 "{{var|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 {{var|M}} is the number of reservations that are active during the added calendar periods.

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

==External links==

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

==References==

{{Reflist}}

<references/>

==External links==

* {{in lang|fr}} [http://www.developpez.net/forums/showthread.php?p=3078887 C source code]

[[Category:Scheduling algorithms]]

[[Category:Calendar algorithms]]

[[fr:Algorithme des noeuds chapeaux]]