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:
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
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.)
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 be the number of elementary periods in the calendar.
The maximal number of "top-nodes" for a given reservation is 2.log n.
where is the number of reservations that are active during the added calendar periods.
(= 0 if reservations are not allowed after the end of the calendar.)