- Algorithme des nœuds chapeaux
-
L’algorithme des nœuds chapeaux est un algorithme de gestion d'un calendrier de ressources[1]. Il a été inventé en 1994.
Il est utilisé pour partager une ressource entre un grand nombre d'utilisateurs (par exemple pour réserver de la bande passante dans un réseau télécom, ou de l'espace disque dans un centre de calcul).
Sommaire
Présentation
L'algorithme permet d'effectuer quatre opérations :
- déterminer si une quantité de ressource est disponible sur une période donnée du calendrier,
- réserver une quantité de ressource pour une période donnée,
- supprimer une réservation,
- décaler le calendrier (le calendrier couvrant une période de temps finie, il doit être régulièrement décalé au fur et à mesure que le temps passe).
L'intérêt de l'algorithme est que le temps d'exécution des 3 premières opérations dépend uniquement de la taille du calendrier (il est indépendant du nombre de réservations déjà effectuées).
Principe
La quantité de ressource à réserver est représentée par un nombre (par exemple un nombre de Ko/s sur un lien de réseau).
Le calendrier est mémorisé sous forme d'un arbre binaire dans lequel une feuille représente une période élémentaire, et un nœud interne représente la période constituée par tous ses descendants.
Exemple d'un calendrier d'une durée de 7 heures (avec des périodes élémentaires d'une heure) Pour une réservation donnée, on définit l'ensemble de ses "nœuds-chapeaux" qui est l'ensemble minimal de nœuds représentant la durée de la réservation.
Plus précisément, un nœud est un "nœud-chapeau" pour une réservation si et seulement si :
- toutes ses feuilles descendantes sont contenues dans la durée de la réservation,
et
- c'est le nœud racine, ou bien au moins une feuille descendante du nœud père est en dehors de la réservation.
Nœuds-chapeaux pour une réservation allant de 1h00 à 5h59 A chaque nœud est mémorisée la quantité de ressource réservée suivante :
q(nœud) = max (q(fils gauche), q(fils droit)) + somme des quantités réservées pour les réservations ayant le nœud comme nœud-chapeau(dans la pratique, pour des raisons d'optimisation, on mémorisera séparément les deux termes de cette somme).
L'enregistrement d'une réservation revient donc à ne mémoriser la quantité réservée que dans ses nœuds-chapeaux.
Performances
Soit "n" le nombre de périodes élémentaires du calendrier. On peut remarquer que le nombre de nœuds-chapeaux pour une réservation quelconque est inférieur ou égal à 2.log n, et que la détermination de ces nœuds-chapeaux se fait en O(log n).
- Détermination de la quantité de ressource disponible sur une période donnée : O(log n)
- Enregistrement d'une réservation : O(log n)
- Suppression d'une réservation : O(log n)
- Décalage du calendrier : O(log n + M.log n)
où M est le nombre de réservations actives pendant la période ajoutée en fin du calendrier.
M est nul si on s'interdit d'enregistrer des réservations au-delà de la durée du calendrier. Si M est important, on planifie en général le décalage du calendrier pendant les périodes creuses d'activité (souvent pendant la nuit).
Procédures
On utilise la notation suivante :
q(nœud) = qf(nœud) + qn(nœud) qf(nœud) = max (q(fils gauche), q(fils droit)) qn(nœud) = somme des quantités réservées pour les réservations ayant le nœud comme nœud-chapeau t0(nœud) = début de la période représentée par le nœud t1(nœud) = fin de la période représentée par le nœud t0(resa) = début de la période de réservation t1(resa) = fin de la période de réservation
Calcul des nœuds-chapeaux pour une période donnée
Le nœud-chapeau le plus à gauche (nommé TG) est trouvé en parcourant l'arbre depuis la racine, jusqu'à trouver un nœud tel que t0(nœud)=t0(resa), et t1(nœud)⇐t1(resa)
Le nœud-chapeau le plus à droite (nommé TD) est trouvé d'une manière similaire.
Les nœuds-chapeaux intermédiaires sont déduits en remontant l'arbre à partir de ces deux nœuds-chapeaux TG et TD, jusqu'à leur nœud parent commun :
- pendant la remontée depuis TG : si un nœud est tel que t1(nœud) != t1(dernier nœud-chapeau parcouru), alors le fils droit de ce nœud est un nœud-chapeau,
- pendant la remontée depuis TD : si un nœud est tel que t0(nœud) != t0(dernier nœud-chapeau parcouru), alors le fils gauche de ce nœud est un nœud-chapeau.
Détermination de la quantité de ressource disponible sur une période
La quantité de ressource disponible se déduit de la quantité maximale réservée sur la période.
Pour un nœud donné, la quantité maximale réservée sur la période correspondante est égale à
qMax(nœud) = q(nœud) + somme des qn() des nœuds parents jusqu'à la racine de l'arbre
La quantité maximale réservée sur une période donnée est la valeur maximale des qMax() des nœuds-chapeaux.
Réservation d'une quantité de ressource pour une période donnée
L'enregistrement d'une réservation s'effectue en ajoutant la quantité réservée au qn() de tous les nœuds-chapeaux. Le qf() des nœuds parents doit être mis à jour en conséquence.
Suppression d'une réservation
La suppression d'une réservation s'effectue en retranchant la quantité précédemment réservée au qn() de tous les nœuds-chapeaux. Le qf() des nœuds parents doit être mis à jour en conséquence.
Décalage du calendrier
Le décalage se fait en retirant des nœuds à gauche de l'arbre et en en ajoutant à droite.
Pour chaque sous-arbre supprimé à gauche de l'arbre, le qf() de ses nœuds parents doit être recalculé.
Il faut également supprimer et réenregistrer chaque réservation active pendant la période ajoutée au calendrier (s'il y en a). Cette étape peut éventuellement être optimisée en regroupant la suppression/réenregistrement pour ne modifier que les nœuds-parents impactés par le décalage du calendrier.
Liens externes
Notes et références
- Dossier de l'Office Européen des Brevets relatif à cet algorithme (L'algorithme n'est plus protégé depuis avril 2007)
Wikimedia Foundation. 2010.
