Hispanopedia WikiEl algoritmo top-nodes es un algoritmo para gestionar 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 recursos disponible durante un período de tiempo específico,
- reservar una cantidad de recursos durante un período de tiempo específico,
- eliminar una reserva anterior,
- Avanzar el calendario (el calendario abarca una duración definida y debe avanzarse a medida que pasa el tiempo).
Principio
El calendario se almacena como un árbol binario donde las hojas representan períodos de tiempo elementales. Los demás nodos representan el período de tiempo que abarcan todos sus descendientes.
El período de tiempo que abarca una reserva está representado por un conjunto de "nodos principales". Este conjunto es el conjunto mínimo de nodos que cubren exactamente el período de tiempo de la reserva.
Un nodo del árbol binario es un "nodo superior" para una reserva dada si
- todos sus descendientes se encuentran dentro del período de tiempo de la reserva, y
- Es el nodo raíz, o al menos un descendiente del nodo padre, quien se encuentra fuera del período de reserva.
En cada nodo se almacena el siguiente valor:
q(nodo) = max(q(hijo izquierdo), q(hijo derecho)) + Cantidad total de recursos reservados para todas las reservas que tienen este nodo como "nodo superior"
(Para optimizar el código , las dos partes de esta suma suelen almacenarse por separado).
Actuación
La ventaja de este algoritmo es que el tiempo para registrar una nueva reserva de recursos depende únicamente del tamaño del calendario (no depende del número total de reservas).
Sea n el número de períodos elementales en el calendario.
El número máximo de "nodos superiores" para una reserva dada es 2.log n.
- Para comprobar si una cantidad de recursos está disponible durante un período de tiempo específico : O (log n )
- Reservar una cantidad de recursos durante un período de tiempo específico : O (log n )
- Para eliminar una reserva anterior : O (log n )
- para 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 del calendario añadidos.
( M = 0 si no se permiten reservas después del final del calendario.)
Referencias
Enlaces externos
- Código fuente en C (en francés)
- Algoritmos de planificación
