# Top-nodes algorithm

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Top-nodes_algorithm
> Markdown URL: https://mediated.wiki/source/Top-nodes_algorithm.md
> Source: https://en.wikipedia.org/wiki/Top-nodes_algorithm
> Source revision: 1114235515
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

The '''top-nodes algorithm''' is an [algorithm](/source/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](/source/Bandwidth_(signal_processing)) in a [telecommunication](/source/telecommunication) link, or [disk capacity](/source/disk_capacity) in a large [data center](/source/data_center)).

The algorithm allows users to:
* check if an amount of [resource](/source/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](/source/binary_tree) where leaves represent elementary time periods. Other nodes represent the period of time covered by all their descendants.
center|Example of a seven-hour calendar (with elementary periods of one hour)
{{center|''Example of a seven-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](/source/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.
center|Top-nodes for a reservation from 1:00 to 5:59
{{center|''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](/source/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.)

==References==
{{Reflist}}

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

Category:Scheduling algorithms

---
Adapted from the Wikipedia article [Top-nodes algorithm](https://en.wikipedia.org/wiki/Top-nodes_algorithm) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Top-nodes_algorithm?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.