Résumé

  • Dans le modèle de Keshav, deux paquets consécutifs étaient le plus fortement espacés par le serveur à allocation de débit constituant le goulot ; l’écart entre acquittements donnait une estimation bruitée du débit alloué à une conversation.
  • L’estimation alimentait un contrôleur borné par un point de consigne de file, un lissage exponentiel ajusté par logique floue, une preuve de stabilité conditionnelle et une procédure volontaire de recalage.
  • La paire ne certifiait pas la bande passante de l’Internet. La méthode supposait un ordonnanceur de type équitable, excluait le FCFS ordinaire et ne promettait ni absence de pertes, ni livraison applicative, ni qualité de service.

Provoquer juste assez de file pour pouvoir mesurer

Lorsque plusieurs paquets d’un même flux attendent déjà, leur cadence de service peut réapparaître dans les acquittements. Une file vide ne fournit aucun rythme. Le problème de Keshav était donc moins de voir à travers le routeur que de produire un événement dont le routeur ne pourrait s’empêcher de modifier.

Dans sa rétrospective de 2019, il situe l’intuition en décembre 1989, dans un café de Berkeley. Deux paquets partiraient dos à dos. Le premier occuperait un tour de service, le second attendrait immédiatement derrière lui. Sur un chemin de plusieurs nœuds, le service par conversation le plus lent imposerait l’écart le plus grand ; les acquittements pourraient ramener cette trace à la source sans champ explicite annoncé par les routeurs.

Ce récit a une portée précise. Le texte de 2019 se présente comme une note éditoriale non évaluée par les pairs : il documente la mémoire de l’auteur, pas un essai indépendant. Il consigne aussi une attribution essentielle. Samar Singh et Ashok Agrawala étaient arrivés séparément à une idée comparable presque au même moment, avant de réunir leurs travaux avec Keshav. L’article de contrôle de SIGCOMM est signé par Keshav, mais la paire de paquets ne doit pas devenir le mythe d’un inventeur solitaire.

L’observabilité venait de l’ordonnanceur

Le mécanisme supposait des Rate Allocating Servers, proches de Fair Queueing et de Virtual Clock. Dans ces files de sortie, chaque conversation active reçoit un tour suffisamment régulier pour que l’intervalle entre deux de ses propres services ait une signification. Le temps inclut les tours accordés aux autres conversations ; le plus long de ces temps le long du chemin est le temps de service du goulot.

La paire supprime l’intervalle choisi par la source. Le réseau doit alors inscrire le sien. Un serveur plus rapide situé après le goulot ne referme pas cet écart dans le modèle. Le nombre deux n’était donc pas magique : la discipline de file rendait l’état accessible à une petite expérience.

Le texte refuse explicitement d’étendre le résultat à un réseau premier arrivé, premier servi. Dans une file FCFS, une rafale d’un autre flux peut changer brutalement le service apparent. Sans contrat d’allocation par conversation, le même écart ne porte plus la même information. Une sonde ne peut mesurer que la structure que le système expose réellement.

L’écart de retour restait un reçu bruité

La source n’observait jamais directement la file. Les deux acquittements pouvaient subir des attentes différentes sur le chemin retour et se rapprocher ou s’éloigner. Même sur l’aller, un nœud placé après le goulot pouvait ajouter une différence. Mesurer au récepteur réduirait une partie du bruit retour, sans effacer les perturbations aval.

Keshav modélisait donc la mesure comme une observation bruitée et le débit alloué comme une valeur changeante. Une conversation qui devient active ou inactive modifie la part des autres. La dernière mesure était à la fois imparfaite et déjà ancienne lorsqu’elle entrait dans la prochaine décision.

Un filtre de Kalman offrait une solution formelle, mais il exigeait les variances du bruit du système et de l’observation. Ces paramètres devaient eux-mêmes provenir d’une simulation ou de mesures. La solution pratique fut un lissage exponentiel piloté par logique floue : beaucoup de mémoire lorsque le système semblait stable, davantage de poids au présent lorsqu’il changeait. La logique floue ne remplaçait pas les faits ; elle déclarait la règle de vieillissement des faits.

La stabilité appartenait aux hypothèses qui la prouvaient

Le contrôleur associait le débit estimé au nombre de paquets non acquittés, au RTT et à une estimation de la file du goulot. Il visait un point de fonctionnement, et non la simple reproduction de la dernière mesure.

Le choix B/2 servait l’exposition. Une file trop vide peut laisser inutilisé un tour offert ; une file trop pleine accroît délai et pertes. Sous une hypothèse de bruit symétrique, la moitié mettait la cible entre les deux risques. Le papier autorisait un autre choix : ce n’était pas une constante universelle.

Un premier contrôleur plaçait ses pôles sur le cercle unité et n’était pas asymptotiquement stable. Un paramètre de placement les amenait à l’intérieur, dans le modèle linéaire. Une variante continue pouvait agir à chaque retour de sonde plutôt qu’une fois par RTT. La preuve était substantielle, mais elle ne quittait pas son périmètre : approximation fluide, état RAS observable, dynamique linéaire et hypothèses de bruit.

S’arrêter pour retrouver un zéro vérifiable

Une file estimée à partir d’estimations antérieures peut dériver. Tous les nombres du contrôleur peuvent rester cohérents entre eux alors qu’ils se sont détachés de la file réelle.

La remise à zéro proposée avait un coût visible. La source envoyait une paire spéciale, puis cessait d’émettre jusqu’à son acquittement. Sans paquet ultérieur, sa file au goulot pouvait se vider ; l’estimation était alors ramenée à zéro. Le prix était environ un aller-retour de capacité inutilisée.

Ce silence n’était pas une panne. Il créait la condition qui rendait de nouveau l’état vérifiable. Plutôt que masquer l’incertitude par un lissage supplémentaire, le système payait une calibration.

Le contrôle de débit ne garantissait pas non plus l’absence de perte. Le papier lui associait un contrôle par fenêtre comme plafond conservateur, avec des hypothèses de tampons par conversation. Le débit choisissait une zone de fonctionnement ; la fenêtre bordait le risque. Aucun des deux mécanismes ne pouvait emprunter la promesse de l’autre.

Ce que deux paquets ne pouvaient certifier

L’article de 1991 résumait qualitativement des simulations, renvoyait les détails à d’autres travaux et présentait les mesures sur réseau réel comme une étape future. Il reconnaissait les limites de la linéarité, des bruits gaussiens et blancs, de l’interaction avec la fenêtre et d’un modèle centré sur une seule conversation.

Les méthodes ultérieures de dispersion ont souvent servi à discuter capacité ou bande passante disponible. Il serait erroné de projeter ces significations en arrière. La paire de Keshav estimait le débit de service attribué à une conversation sous un ordonnanceur RAS. Elle ne prouvait ni vitesse physique du lien, ni capacité libre, ni débit de bout en bout, ni livraison applicative.

La biographie de Cambridge retrace aujourd’hui son parcours de Berkeley à Bell Labs, Cornell, Waterloo et Cambridge ; son site précise que Keshav est son prénom, bien que placé syntaxiquement en dernier. L’héritage utile de ce travail tient à son contrat de preuve : conserver avec l’intervalle le flux, l’ordonnanceur, la direction, le moment et l’incertitude. Sans eux, un nombre très précis perd son droit à commander.

Sources