Top-nodes algorithm: Difference between revisions
mNo edit summary |
Added wikilinks |
||
| Line 1: | Line 1: | ||
{{Underlinked|date=December 2012}} |
|||
The '''top-nodes algorithm''' is an [[algorithm]] for managing a resource reservation calendar. The algorithm has been first published in 2003,<ref>[https://archive.is/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 '''top-nodes algorithm''' is an [[algorithm]] for managing a resource reservation calendar. The algorithm has been first published in 2003,<ref>[https://archive.is/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: |
The algorithm allows users to: |
||
* check if an amount of resource is available during a specific period of time, |
* check if an amount of [[resource]] is available during a specific period of time, |
||
* reserve an amount of resource for a specific period of time, |
* reserve an amount of resource for a specific period of time, |
||
* delete a previous reservation, |
* delete a previous reservation, |
||
| Line 16: | Line 14: | ||
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. |
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 |
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 |
* 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. |
* it is the root node, or at least one descendant of the parent node is outside of the reservation period of time. |
||
| Line 25: | Line 23: | ||
q(node) = max(q(left child), q(right child)) |
q(node) = max(q(left child), q(right child)) |
||
+ total amount of reserved resource for all reservations having this node as a "top-node" |
+ 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.) |
(for [[code optimization]], the two parts of this sum are usually stored separately.) |
||
==Performance== |
==Performance== |
||
Revision as of 21:08, 15 November 2020
The top-nodes algorithm is an algorithm for managing a resource reservation calendar. The algorithm has been first published in 2003,[1] and has been improved in 2009.[2] It is used when a resource is shared among many users (for example bandwidth in a telecommunication link, or disk capacity in a large data center).
The algorithm allows users to:
- check if an amount of resource is available during a specific period of time,
- reserve an amount of resource for a specific period of time,
- delete a previous reservation,
- 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 leaves represent elementary time periods. Other nodes represent the period of time covered by all their descendants.
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.
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.)
References
- ^ Related US patent (the algorithm is in the public domain since 2008)
- ^ Improved top-nodes algorithm
External links
- (in French) C source code