Algorithme des nœuds chapeaux
# Algorithme des nœuds chapeaux

L’algorithme des nœuds chapeaux est un algorithme de gestion d'un calendrier de ressources. Il a été inventé en 2003, et amélioré en 2009.

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

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

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.

À chaque nœud est mémorisée la quantité de ressource réservée suivante :

(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 :

### 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 à

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.

