El algoritmo de los nodos superiores es un algoritmo para administrar un calendario de reserva de recursos. El algoritmo se publicó por primera vez en 2003, [1] y se mejoró en 2009. [2] Se utiliza cuando un recurso se comparte entre muchos usuarios (por ejemplo, ancho de banda en un enlace de telecomunicaciones o capacidad de disco en un gran centro de datos ).
El algoritmo permite a los usuarios:
- comprobar si hay una cantidad de recurso disponible durante un período de tiempo específico,
- reservar una cantidad de recursos para un período de tiempo específico,
- eliminar una reserva anterior,
- mover el calendario hacia adelante (el calendario cubre una duración definida y debe adelantarse a medida que pasa el tiempo).
Principio
El calendario se almacena como un árbol binario donde las hojas representan períodos de tiempo elementales. Otros nodos representan el período de tiempo cubierto por todos sus descendientes.
El período de tiempo cubierto por una reserva está representado por un conjunto de "nodos superiores". Este conjunto es el conjunto mínimo de nodos que cubre exactamente el período de tiempo de reserva.
Un nodo del árbol binario es un "nodo superior" para una reserva dada si
- todos sus descendientes están dentro del período de tiempo de reserva, y
- es el nodo raíz, o al menos un descendiente del nodo padre está fuera del período de tiempo de reserva.
El siguiente valor se almacena en cada nodo:
q (nodo) = max (q (hijo izquierdo), q (hijo derecho)) + cantidad total de recurso reservado para todas las reservas que tienen este nodo como "nodo superior"
(para la optimización del código , las dos partes de esta suma generalmente se almacenan por separado).
Actuación
La ventaja de este algoritmo es que el tiempo para registrar una nueva reserva de recursos depende solo del tamaño del calendario (no depende del número total de reservas).
Sea n el número de períodos elementales del calendario.
El número máximo de "nodos superiores" para una reserva determinada es 2.log n.
- para verificar si una cantidad de recurso está disponible durante un período de tiempo específico: O (log n )
- para reservar una cantidad de recurso durante un período de tiempo específico: O (log n )
- para borrar una reserva previa: O (log n )
- para hacer avanzar el calendario: O (log n + M.log n)
donde M es el número de reservas que están activas durante los períodos de calendario agregados.
( M = 0 si no se permiten reservas después del final del calendario).
Referencias
- ^ Patente estadounidense relacionada (el algoritmo es de dominio público desde 2008)
- ^ Algoritmo mejorado de los nodos superiores
enlaces externos
- (en francés) código fuente C