Top-nodes algorithm

[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".

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

Example of a seven-hour calendar (with elementary periods of one hour)
Example of a seven-hour calendar (with elementary periods of one hour)
Top-nodes for a reservation from 1:00 to 5:59
Top-nodes for a reservation from 1:00 to 5:59