Top-nodes algorithm: Difference between revisions

Revision as of 20:31, 8 January 2020

Revision as of 17:55, 28 June 2020

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 lots ofmany users (for example [[Bandwidth (signal processing)|bandwidth]] in a [[telecommunication]] link, or [[disk capacity]] in a large [[data center]]).

The algorithm allows users to:

Line 11:

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

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

<center>''Example of a 7seven-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.