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