http://debianws.lexgopc.com/wiki143/index.php?action=history&feed=atom&title=Top-nodes_algorithmTop-nodes algorithm - Revision history2026-05-04T17:10:33ZRevision history for this page on the wikiMediaWiki 1.43.1http://debianws.lexgopc.com/wiki143/index.php?title=Top-nodes_algorithm&diff=6205775&oldid=previmported>Bruce1ee: fixed lint errors – obsolete HTML tags2022-10-05T13:34:00Z<p>fixed <a href="/wiki143/index.php?title=Special:LintErrors" title="Special:LintErrors">lint errors</a> – obsolete HTML tags</p>
<p><b>New page</b></p><div>The '''top-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]]).<br />
<br />
The algorithm allows users to:<br />
* check if an amount of [[resource]] is available during a specific period of time,<br />
* reserve an amount of resource for a specific period of time,<br />
* delete a previous reservation,<br />
* move the calendar forward (the calendar covers a defined duration, and it must be moved forward as time goes by).<br />
<br />
==Principle==<br />
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.<br />
[[File:AlgoRayroleArbre.svg|center|Example of a seven-hour calendar (with elementary periods of one hour)]]<br />
{{center|''Example of a seven-hour calendar (with elementary periods of one hour)''}}<br />
<br />
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.<br />
<br />
A node of the [[binary tree]] is a "top-node" for a given reservation if<br />
* all its descendants are inside the reservation period of time, and<br />
* it is the root node, or at least one descendant of the parent node is outside of the reservation period of time.<br />
[[File:AlgoRayroleResa.svg|center|Top-nodes for a reservation from 1:00 to 5:59]]<br />
{{center|''Top-nodes for a reservation from 1:00 to 5:59''}}<br />
<br />
The following value is stored in each node:<br />
q(node) = max(q(left child), q(right child))<br />
+ total amount of reserved resource for all reservations having this node as a "top-node"<br />
(for [[code optimization]], the two parts of this sum are usually stored separately.)<br />
<br />
==Performance==<br />
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).<br />
<br />
Let {{var|n}} be the number of elementary periods in the calendar.<br />
<br />
The maximal number of "top-nodes" for a given reservation is 2.log n.<br />
* to check if an amount of resource is available during a specific period of time : ''O''(log ''n'')<br />
* to reserve an amount of resource for a specific period of time : ''O''(log ''n'')<br />
* to delete a previous reservation : ''O''(log ''n'')<br />
* to move the calendar forward : ''O''(log ''n'' + M.log n)<br />
where {{var|M}} is the number of reservations that are active during the added calendar periods.<br />
<br />
({{var|M}} = 0 if reservations are not allowed after the end of the calendar.)<br />
<br />
==References==<br />
{{Reflist}}<br />
<br />
==External links==<br />
* {{in lang|fr}} [http://www.developpez.net/forums/showthread.php?p=3078887 C source code]<br />
<br />
[[Category:Scheduling algorithms]]</div>imported>Bruce1ee