Top-nodes algorithm: Difference between revisions

Content deleted Content added
Added wikilinks
m fixed lint errors – obsolete HTML tags
 
(One intermediate revision by one other user not shown)
Line 1:
The '''top-nodes algorithm''' is an [[algorithm]] for managing a resource reservation calendar. The algorithm has been first published in 2003,<ref>[https://archive.istoday/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:
Line 9:
==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|center|Example of a seven-hour calendar (with elementary periods of one hour)]]</center>
<{{center>|''Example of a seven-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.
Line 17:
* 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>[[File:AlgoRayroleResa.svg|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: