4.2 L'ALGORiTHME
L'idée de ce nouvel algorithme consiste
à ajouter deux champs dynamiques dans la table de routage de chaque
site, l'un pour le nombre de jetons libre et l'autre pour le nombre de jetons
présent qui sont propres pour chaque site.
À chaque fois qu'il y a une modification au
niveau de ces deux variables, le site doit modifier sa table de routage dans
les deux champs, et par conséquent les autres sites doivent aussi
modifier leurs tables de routage et faire des changements au niveau du site en
question et plus exactement au niveau des deux variables et cela grâce
aux messages de contrôle utilisés pour le routage.
Lorsqu'un site demandeur désire entrer en SC,
il doit d'abord consulter sa table de routage, et essayer de trouver les sites
qui possèdent des jetons libres, ensuite le site le plus proche selon le
champ Distance sera choisi pour adresser la requête. Dans le cas
où tous les sites sont en SC, le plus proche site possèdant un
jeton sera choisi.
Si un site reçoit une requête et ne
possède pas de jetons libre ni de jeton présent, il doit envoyer
un message au demandeur lui indiquant qu'il ne posséde rien, et il doit
réessayer de chercher un autre site adéquat. Cette méthode
permet donc de minimiser le nombre de messages échangés pour
chaque entrée en SC.
4.2.1 Hypothèses
Pour assurer le bon fonctionnement de notre algorithme,
on suppose que :
- Le nombre N des noeuds et le K des racines (qui
détiennent les jetons) sont connus. - Chaque noeud connaît ses
voisins immédiats.
- Les canaux de communication sont fiables, et il n'y a
pas de perte de messages. - Les sites du système ne tombent pas en
panne.
- Le réseau n'est pas
partitionné.
4.2.2 Description de l'algorithme
Nous allons décrire les changements
effectués au niveau des variables locales, les messages utilisés,
et enfin les procédures de l'algorithme.
4.2.2.1 Les variables locales
Chaque noeud i dans le système maintient
les variables locales suivantes :
- Demandeuri : une variable booléenne
initialisée à Faux, indiquant si i a demandé une
ressource critique ou non.
- Jetoni : une variable booléenne
indiquant si i possède un jeton ou non, elle
est
initialisée à Faux au niveau des sites simple et à
Vrai au niveau des sites racines.
- Suivanti : une variable indiquant
l'identité d'un site auquel on va retransmettre notre jeton une fois
servi.
- AODVi(B,C) : la table de routage du site en
question, avec l'utilisation et la modification de deux champs seulement
:
B : le nombre de jetons libre.
C : le nombre de jetons présent.
4.2.2.2 Les messages utilisés
Dans cet algorithme, on utilise trois types de
messages:
- Requête (Jeton, i) : envoyé par le site
i vers le site qui détient un jeton lors de la demande de la
Section critique.
- Accord (Jeton) : envoyé par le site qui
détient le jeton à un site demandeur pour lui permettre
d'utiliser la ressource critique demandée.
- Rejet (Jeton) : envoyé par un ancien
détenteur du jeton à un site demandeur pour lui informer qu'il ne
détient plus le jeton.
| 
