Алгоритм верхних узлов

Алгоритм верхних узлов — это алгоритм управления календарем резервирования ресурсов. Алгоритм был впервые опубликован в 2003 году. и был улучшен в 2009 году. Он используется, когда ресурс используется многими пользователями (например, пропускная способность канала телекоммуникационного или емкость диска в большом центре обработки данных ).

Алгоритм позволяет пользователям:

• проверить, доступен ли объем ресурса в течение определенного периода времени,
• зарезервировать количество ресурса на определенный период времени,
• удалить предыдущее бронирование,
• переместить календарь вперед (календарь охватывает определенный период времени, и с течением времени его необходимо перемещать вперед).

Принцип

Календарь хранится в виде двоичного дерева , листья которого представляют элементарные периоды времени. Другие узлы представляют период времени, охватываемый всеми их потомками.

Example of a seven-hour calendar (with elementary periods of one hour)

Пример семичасового календаря (с элементарными периодами в один час)

Период времени, охватываемый резервированием, представлен набором «верхних узлов». Этот набор представляет собой минимальный набор узлов, который точно покрывает период резервирования.

Узел бинарного дерева является «верхним узлом» для данного резервирования, если

• все его потомки находятся внутри периода резервирования, и
• это корневой узел, или по крайней мере один потомок родительского узла находится за пределами периода резервирования.

Top-nodes for a reservation from 1:00 to 5:59

Топ-ноды для брони с 1:00 до 5:59

В каждом узле хранится следующее значение:

q(node) = max(q(left child), q(right child))
          + total amount of reserved resource for all reservations having this node as a "top-node"

(для оптимизации кода две части этой суммы обычно хранятся отдельно.)

Производительность

Преимущество этого алгоритма в том, что время регистрации нового резервирования ресурса зависит только от размера календаря (оно не зависит от общего количества резервирований).

Пусть n — количество элементарных периодов в календаре.

Максимальное количество «верхних узлов» для данного резервирования равно 2.log n.

• чтобы проверить, доступен ли объем ресурса в течение определенного периода времени: O (log n )
• зарезервировать количество ресурсов на определенный период времени: O (log n )
• чтобы удалить предыдущее бронирование: O (log n )
• чтобы переместить календарь вперед: O (log n + M.log n)

где M — количество резервирований, активных в течение добавленных календарных периодов.

( M = 0, если бронирование не разрешено после окончания календаря.)

Внешние ссылки

• (на французском языке) Исходный код C