Top-nodes algorithm
The top-nodes algorithm is an algorithm for managing a resource reservation calendar. The algorithm has been first published in 2003, and has been improved in 2009. It is used when a resource is shared among many users.
The algorithm allows users to:
- check if an amount of resource is available during a specific period of time,
- reserve an amount of resource for a specific period of time,
- delete a previous reservation,
- move the calendar forward.
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.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
- 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.
q = max, q)
+ total amount of reserved resource for all reservations having this node as a "top-node"
Performance
The advantage of this algorithm is that the time to register a new resource reservation depends only on the calendar size.Let be the number of elementary periods in the calendar.
The maximal number of "top-nodes" for a given reservation is 2.log n.
- to check if an amount of resource is available during a specific period of time : O
- to reserve an amount of resource for a specific period of time : O
- to delete a previous reservation : O
- to move the calendar forward : O