[Bitobi-arch] [archi] Efficacité du rézal par l'architecture

[Olivier Lourdais]

Principe : que chaque noeud est un comportement "améliorant" (civique) 
pour l'état du réseau (diminution de la latence globale, répartition 
correcte de la latence, ...)

Les algos entrant en jeu n'ont imho pas vocation à être normalisés 
(plusieurs algos peuvent coexister, et leur non-utilisation n'empêche 
pas le réseau de fonctionner) (on peut toutefois donner des exemples 
d'algo à titre indicatif), et ça n'entre de toutes façons pas dans le 
cadre de cette ml.
Toutefois, pour permettre à un noeud de se connecter à tel noeud plutôt 
qu'à tel autre, il faut lui fournir des informations sur l'état du 
réseau, et bien sûr il faut évaluer l'état du réseau.

Le premier extrait de mail (un peu dépoussiéré) :
-----
bon, je propose que chaque noeud connaisse en permanence l'état 
(approximatif) du réseau, modélisé par un graphe
à chaque noeud pourrait être associé ces infos :
- infos d'authentification (clé gpg + autres infos ?)
- nombre de connexions max à d'autes noeuds
- nombre de requêtes/sec pour les n dernières minutes (+ éventuellement 
le nombres d'utilisateurs différents, reconnus par leur cookies (voire 
la liste des users)) (+ éventuellement le nombre max de req/sec (et 
d'utilsateurs ?) acceptées (limite "souple" vu que c'est difficile à 
bloquer sans faire chier le peuple))
et pour chaque arc :
- sa latence [question pour les experts en résal : y'a t'il un moyen 
d'avoir une estimation fiable (en tenant compte de la synchronisation 
d'heure entre tous les noeuds) de la latence entre les noeuds A et B ? 
on peut avoir facilement (latence(A, B) + latence(B, A)), mais est il 
possile de connaître latence(A, B) ET latence(B, A) par un moyen 
qualconque ? et sinon est-il acceptable d'approximer (latence(A, B) ~= 
latence(B, A) ~= ((latence(A, B) + latence(B, A)) / 2)) dans le cas 
général ? (grosso modo, j'entends par latence "temps de la propagation 
d'un message", ou toute valeure proportionnelle au temps de la 
propagation d'un message) ]

pour maintenir tout çà, il faut penser à diffuser des messages "de 
service" :
- ajout d'une connexion (A: le noeud B vient de se connecter à moi)
- suppression d'une connexion (A: je viens de perdre le contac avec le 
noeud B)
- mise à jour de la latence (plus éventuellement des messages pour 
estimer la latence, mais je pense qui çà se ferait plutôt à un plus bas 
niveau)
- mise à jour des infos associées à un noeud

quand un noeud veut rejoindre le réseau (je zappe des étapes qui ont 
déjà été énumérées) :
1. il demande à un noeud (noeud fixe, de référence ?) l'état du réseau 
(le graphe)
2. il applique sur ce graphe un algo basé sur Warshall-Floyd* pour 
déterminer le diamètre du réseau (le nombre max d'arcs entre deux 
noeuds, mais ici plutôt la latence max entre deux noeuds)
3. il se connecte aux deux noeuds qu'il a établi être les extrémités du 
diamètre du réseau
remarques :
- un comportement de ce type a imho tendance à améliorer l'état du 
réseau (vu que çà ajoute un lien potentiellement plus rapide entre les 
deux noeuds les plus éloignés du réseau)
- l'algo peut prendre d'autres éléments en compte (info sur les noeuds) 
pour choisir les noeuds
- l'algo est donné à titre indicatif, pas normatif (çà fait pas partie 
du protocole et çà n'est pas gênant que tous les noeuds n'utilisent pas 
le même algo)
- le noeud peut se choisir plus de 2 voisins
- on peut aussi envisager qu'un noeud déjà relié au réseau lance 
régulièrement un algo de ce genre pour voir s'il est possible 
d'améliorer le réseau
- quand est noeud se déconnecte, ses anciens voisins vont éventuellement 
établir de nouvelles liaisons (selon leur nb de liaison min) pour 
améliorer le réseau et leur place dans le réseau

* un tel algo prend en entrée un graphe G qui contient les connexions 
entre les noeuds (voisins) et leur latence, et rend un graphe G' qui 
contient les connexions virtuelles entre chaque noeud (pas forcément 
physiquement voisin) et leur latence (calculée en cumulant les latences 
des connexions physiques utilisées) : si G contient les noeuds A, B et 
C, avec des connexions physiques A->B (latence=25) et B->C (latence=17), 
alors le graphe G' contiendra les connexions de G + la connexion A->C 
(latence=42) (s'il y a deux chemins dans G pour aller de A à C, on 
choisit celui qui a la latence la plus faible)
-----

un autre :
-----

> à la louche, je
> dirais : demandons-nous d'abord si il est nécessaire d'avoir une
> connaissance plus complexe du bitobi que 'tel noeud est up, tel noeud
> est down'. Si oui, alors faut trouver un bon algo, et là je vous laisse
> oeuvrer ;)


Si on veut assurer le meilleur fonctionnement possible (minimiser le 
temps de propagation d'un message, ne pas concentrer la charge sur 
quelques noeuds, ...), il faut fournir à tout noeud qui veut se 
connecter les informations nécessaires, et donc connaître en permanence 
l'état approximatif (mais néanmoins détaillé) du réseau (ce qui peut 
aussi amener des noeuds à modifier leurs connexions)
Et je pense qu'on peut y inclure un max d'infos dès le début (tant que 
çà coûte pas trop cher), étant donné que les algos qui utiliseront ces 
donnés seront non normatifs et à la discretion des implémentations (de 
noeud et de mouling agent).
-----

puis :
-----

> Ouais.. Du coup effectivement, une connaissance de l'état du réseau plus
> précise que up, down risque d'être nécessaire.. va falloir une
> représentation ad-hoc du réseau, alors..


sur chaque noeud çà peut se modéliser par un graphe valué, qui peut se 
sérialiser facilement en xml (ensemble de sommets + enemble d'arcs) pour 
le transmettre à un noeud qui vient de se connecter
pour les messages de services qui feront évolué le graphe de chaque 
noeud, on peut avoir des messages du genre :
- A: je viens de me connecter à B
- A: je vais me déconnecter
- A: je viens de perdre ma connexion avec B sans qu'il annonce sa 
déconnexion (chaque noeud regarde si B a encore une connexion active 
avec un autre noeud, si çà n'est pas le cas, B est considéré comme down)
- A: je viens d'évaluer ma connexion avec B, la latence est actuellement 
de x ms
- A: voici mes stats de charge : x req/sec depuis les coincoins 
traditionnels, avec n utilisateurs authentifiés distincts ces 10 
dernières minutes, ...
- A: voici les quotas que j'aimerais bien respecter vis à vis de la 
charge : x req/sec max, ...
-----


Pour évaluer la latence de A vers B, vous pensez qu'il suffit d'un 
échange du style :
A->B : <test-latence heure-envoi="01/02/2003-42:42:42.123"/>
B->A : <réponse-test-latence 
heure-envoi="01/02/2003-42:42:42.123" heure-réception="01/02/2003-42:42:45.456"/>
?
En gros, est-ce que la synchro entre chaque noeud suffit à avoir des 
mesures fiables avec ce protocole ?