0. Introduction

L’utilisation du temps physique est-elle inévitable dans tout protocole destiné à garantir des communications fiables dans les réseaux à pertes (« best effort ») ? Quels sont les liens entre TCP/IP et les algorithmes distribués au cœur des réseaux contemporains ?

La première question fait encore l’objet de débats entre spécialistes. La seconde question est très rarement posée, malgré son importance historico-scientifique. 

1. Protocoles de transport pour réseaux de type « best effort »

 On considère des réseaux à commutation de paquets^[1], non fiables (« best effort »), à délais variables. Les paquets circulent dans un ordre quelconque, et plusieurs copies d’un même paquet peuvent exister. Soit R un tel réseau. 

Soit une source S et un destinataire D, processus séquentiels exécutés sur des équipements connectés à R, et une liaison virtuelle LV (niveau transport, OSI/ISO 4) sur laquelle S envoie une suite ordonnée (?) de messages vers D. Par communications fiables, on entend livraison chez D de ?. 

Les protocoles de transport tels que TCP ^[2] sont la véritable innovation de rupture qui a permis l’avènement d’Internet.^[3] Selon les présentations traditionnelles, un protocole de transport a pour but d’assurer les propriétés suivantes :

- livraison chez D d’une suite de messages strictement identique à ? (ordonnée, sans pertes, sans répétitions),

- en optimisant l’utilisation des ressources disponibles chez S, R et D, sans les saturer.

D’un point de vue algorithmique, le but poursuivi est plus ambitieux. Soit un message M reçu et acquitté par D. On veut assurer la propriété d’accord Ψ suivante :

Proposition Φ(S) : S sait que D a reçu M. Proposition Φ(D) : D sait que S sait que D a reçu M. 

Il y a accord entre S et D lorsque Φ(S) et Φ(D) sont toutes deux vraies. 

 Le protocole TCP ainsi que ses variantes—y compris les plus récentes^[4]—garantit Ψ, grâce au contrôle d’erreur et de flux « de bout-en-bout » exercé par le mécanisme de fenêtre glissante, basé sur des acks ou des nacks, et sur des réveils mesurant le temps, dont les valeurs sont déduites de la variable RTT. RTT est une fonction de Δ_S, Δ_R et Δ_D. Δ_S et Δ_D sont les délais d’activation et d’exécution de S et D sur leurs équipements respectifs. Δ_R est le délai de traversée de R.^[5]

 Un message est segmenté en PDU de longueur maximale connue (nécessaire pour le contrôle de flux), transmis par R sous la forme de paquet (IPv4 ou IPv6). S émet vers D des PDU numérotés (entiers j consécutifs—modulo une base ignorée ici) et D renvoie vers S des ack(j) ou des nack(j). S, D et R sont sujets à fautes transitoires ou permanentes (arrêts pour S et D, pertes de ack/nack ou de PDU—un PDU détecté erroné est ignoré). On suppose que S et D sont honnêtes (pas d’usurpation d’identité, pas de falsification des PDU, etc.). Les ressources allouées à LV (temps de calcul, mémoire, entrées-sorties, etc.) sont partagées avec d’autres processus présents dans les équipements et dans R. 

 À tout instant, on a (indice temps ignoré) :

- w : taille de la fenêtre en cours sur LV, connue à l’identique par S et D ; w est ajustable dynamiquement en fonction des charges et délais observés^[6].

 - j(S) : tous les PDU de numéros allant jusqu’à j(S) ont été acquittés par D (selon S) / le bord inférieur de la fenêtre chez S est j* = j(S)+1

==> Outre son numéro j ∈ [j(S)+1, j(S)+1+w], tout PDU est accompagné par j*.

 - j(D) : tous les PDU de numéros allant jusqu’à j(D) ont été acquittés par D (selon D) / le bord inférieur de la fenêtre chez D est j(D)+1

==> D accepte les PDU numérotés de j(D)+1 à j(D)+1+w. 

Les ack/nack non perdus sont reçus par S passé un certain délai. Donc, j(S) ≤ j(D). En pire cas, S s’interdit d’émettre un total de j(D)-j(S) PDU alors que D est prêt à les recevoir (perte d’efficacité). 

 Cette description simplifiée couvre les variantes connues des protocoles ARQ^[7], celles qui reposent sur des ack et des retransmissions de tous les PDU dont les numéros appartiennent à la fenêtre courante, ainsi que celles qui utilisent des nack (retransmission du PDU de numéro j(S)+1 ou des PDU qui ont été acquittés négativement par D). Un nombre maximum de retransmissions (PDU, ack, nack) est fixé. Quand ce seuil est atteint, LV est fermée. 

Tant que LV n’est pas fermée, D doit renvoyer en un délai maximum connu (une fonction de RTT) un ack pour les PDU reçus, ou un nack en cas de PDU manquant, éventuellement répété. Après réception d’un ack/nack, S doit envoyer un ou plusieurs PDU (éventuellement, un PDU vide) en un délai maximum connu (une fonction de RTT).

Retour sur la propriété d’accord Ψ (PDU M numéroté m, reçu et acquitté par D) :

La proposition Φ(S) est vraie quand S reçoit ack(v), v ≥ m, ou nack(v), v ≥ m+1.

La proposition Φ(D) est vraie quand D reçoit un PDU porteur d’un numéro j* ≥ m.

2. Temps physique et protocoles de transport

On examine l’assertion A suivante :

L’utilisation du temps physique est inévitable dans tout protocole destiné à garantir Ψ.

Certains spécialistes (excellents connaisseurs de l’histoire des protocoles) tentent de démontrer que A est incorrecte via un contre-exemple bâti avec le protocole ABP^[8], qui repose sur l’inondation (flooding) des ressources. Un seul message (bit b = 0 par exemple) est en transit entre S et D. S "inonde" R et D, en émettant sans arrêt des copies du message en transit, jusqu’à réception d’un ack(b). Le message suivant est alors émis par S, estampillé avec bit b =1. Et ainsi de suite. ABP n’utilise pas de réveil. 

Discussion sous l’angle "ingénierie des protocoles" 

- ABP est un protocole de niveau OSI/ISO 2 (data link). S et D communiquent directement via un lien physique (pas de réseau R). Un inconvénient majeur de ABP est de n’autoriser qu’un seul message en transit sur un lien.

En outre, les seuls processus considérés sont S et D. Les équipements connectés aux réseaux actuels et les réseaux eux-mêmes sont multiplexés. Le partage équitable des ressources est un impératif. L’appropriation exclusive (source de gaspillage) de ressources partagées est bannie. Elle est évitée en introduisant chez S une attente entre deux envois de copies consécutifs. Mais comment attendre sans réveil ? 

 - Bounded Retransmision Protocol. Il a pour but de transformer ABP en protocole de transport « efficace », en lui ajoutant le mécanisme de fenêtre glissante. Ce protocole fonctionnerait sans réveil. Après un envoi, S « donne la main » au système d’exploitation local (ordonnanceur et gestionnaire des processus), qui « rend la main » à S après avoir exécuté un ou plusieurs processus. S met alors fin à son silence (en émettant un ou plusieurs PDU). Et ainsi de suite. Idem pour D. 

Cette « solution » repose de facto sur au moins un réveil. Ce sont les systèmes d’exploitation qui contiennent horloges et réveils ! Tout mécanisme d'attente fondé sur des exécutions (des occupations de ressources en général) se ramène à une "horloge du pauvre", le temps étant compté ou « consommé » de façon très approximative. En Informatique, on utilise les transitions d'état pour "faire avancer" les processus—les propriétés de vivacité (liveness) et de terminaison. Toute transition d'état est "bonne à prendre". Il se trouve que les incréments d'horloges sont les transitions d'état les plus précises et exactes imaginées jusqu'à présent. De plus, une horloge (qui permet de construire des réveils) a l'avantage de libérer les ressources utiles, gaspillées par des attentes actives inutiles. 

- Connaissance partagée de RTT. S et D doivent partager la même connaissance de RTT à l’ouverture de LV. Il peut s’agir d’une valeur standard, ou bien négociée. Les durées maximales Δ_S et Δ_D dépendent chacune d’un ensemble de paramètres propres à leur équipement (processus exécutables séquentiels ou parallèles—à flots multiples, algorithmes d’ordonnancement, durées pires cas d’activation et d’exécution des processus, échéances ou/et priorités respectives de ces derniers, etc.). Pour connaître Δ_S et Δ_D, il faut mener une analyse « d’ordonnançabilité » (schedulability analysis) propre à chaque équipement. Ces analyses sont de complexité non négligeable. De plus, les durées pires cas d’exécution d’un processus peuvent dépendre de valeurs de variables d'entrée, de suspension(s) en cours d’exécution (attente sur sémaphore pour entrée en section critique), d’interruptions sur événements externes. On se contente donc en général de prendre pour Δ_S et Δ_D un majorant des durées pire cas d’activation et d’exécution des processus. Δ_R dépend des charges réseau dues au trafic acheminé sur toutes les liaisons virtuelles. 

Outre leur relatives imprécisions et variabilité dans le temps, ces durées peuvent être incompatibles avec des qualités-de-service imposées ou promises par les fournisseurs d’accès à R. Des réveils qui déclenchent des interruptions garantissent que tout équipement pourra « tenir » un RTT donné (standard ou négocié). Ce qui n’est pas le cas en l’absence de réveils. 

- Risques d’échec et d’attente infinie. Sans utilisation de réveils, une ouverture de LV peut échouer (délais observés trop grands). Sans réveil, comment S ou D peuvent-ils savoir s'ils doivent continuer à attendre ou abandonner ? Ne pouvant savoir si un silence est « anormalement long » (pas de PDU ou de ack/nack), ils doivent compter sur un gestionnaire de processus qui fera, pour leur compte et grâce à des réveils, la différence entre "tout va bien, attendre" et "une surcharge ou une défaillance est survenue, ne plus attendre"—fermeture de la LV dans ce dernier cas. 

L’assertion A peut donc être réécrite comme suit :

Tout protocole destiné à garantir Ψ est nécessairement fondé sur la connaissance partagée d’une borne supérieure finie des délais de niveau transport.

Une preuve montrant que l’assertion A est correcte, ainsi que les conditions que doit satisfaire RTT, sont données dans ^[9]. 

Discussion sous l’angle "algorithmes distribués"

Le problème d’accord à deux processus (propriété Ψ) est un cas particulier des problèmes posés et étudiés par la communauté "Algorithmes Distribués" à partir de la fin des années 1970. Les réseaux tels que R appartiennent à la catégorie des systèmes asynchrones : les délais sont finis non bornés, ou bien ils sont finis et bornés, mais les valeurs des bornes sont inconnues (pas de RTT). Il existe de nombreux résultats d’impossibilité. Voici deux exemples pertinents.

 - Communications fiables FIFO

Garantir Ψ revient à prouver qu’elles sont possibles sur des réseaux tels que R. Il a été démontré que ce problème n’a pas de solution en asynchrone.^[10] Concernant ABP en particulier :

“Three kinds of faults are of interest when discussing reliable FIFO channels in asynchronous systems: loss, reordering, and duplication of packets. There is a solution, the Alternating Bit protocol, for the case of both loss and duplication faults. By way of contrast, no solution is possible for the case of both reordering and duplication faults.” ^[11]

- Consensus Distribué

Au lieu de deux processus (S et D), on généralise à n processus, n > 2.  Par exemple, on considère h sources supposées émettre la suite ordonnée ? et k destinations, h > 1, k > 1 (cas des systèmes à haute disponibilité). La propriété d’accord Ψ implique la possibilité de décider collectivement si oui ou non un nouveau message M peut être ajouté au préfixe de ? en cours chez chacun des processus (placé dans les préfixes au rang donné par m).

Un résultat d'impossibilité très connu en Informatique fut établi en 1985 : en présence d'une seule faute, si l'on ne connait pas la valeur d’une borne supérieure finie des délais, Consensus Distribué est impossible^[12]. Consensus Distribué est la propriété d’accord Ψ. Ce résultat a ensuite été étendu à toutes les fautes possibles (processus et réseau). Voir ^[13] pour un exemple.

 Par contre, il est possible de prouver la propriété d’accord Ψ dans les systèmes asynchrones temporisés (timed asynchrony)^[14], qui sont des systèmes asynchrones « augmentés » de la connaissance des valeurs de bornes finies des délais (tel que RTT dans le cas d’Internet).

 Conclusion : l'assertion A est correcte

3. Et maintenant ?

Grâce aux progrès technologiques (câbles optiques sous-marins à plusieurs centaines de térabits/s, processeurs multicœur à plusieurs dizaines de térabits/s, etc.), les capacités de traitement et de mémorisation au sein des architectures réseaux IP/MPLS (virtualisées et segmentées), au-dessus des réseaux (cloud computing) et en bordure des réseaux (mobile edge computing) deviennent quasiment illimitées. Des avancées basées sur des innovations algorithmiques « gourmandes » en puissance de calcul sont désormais disponibles (codes elliptiques et certificats d’authentification, génération dynamique de mots de passe infalsifiables à usage unique, apprentissage algorithmique non supervisé, etc.). Des solutions bien connues (pseudonymization, concurrency control, blockchains, etc.) sont des extensions d’algorithmes distribués, destinées à garantir différentes variantes de la propriété d’accord Ψ, impliquant plusieurs (h+k) intervenants (h et k éventuellement inconnus) :

- en coopération explicite (fabrication et enregistrement de pseudonymes sans violation de l’anonymat, structures de données multicopiées dans les SDN (software defined networks) et celles utilisées par les moteurs de recherche, etc.),

- en concurrence absolue (achats-ventes/enchères, transactions financières, etc.). 

Dans le vaste domaine du Numérique, la transition TCP/IP ==> algorithmes distribués amorcée dès la fin des années 1970 fut l’une des plus importantes. La comprendre permet de suivre l’évolution des connaissances jusqu’à nos jours. 

 Avec Internet, les humains ont commencé leur « migration » vers un univers cyberphysique, en cours de construction. Ainsi se voyait réalisée la « symbiose » prévue dès 1960 par Joseph Licklider, un extraordinaire visionnaire^[15]. Grâce aux outils digitaux (assistants à commande vocale, PC/smartphones, bracelets connectés, etc.) et services accessibles via le Web, les humains se sont dotés de nouvelles possibilités offertes par le cyberespace. Ce faisant, ils s’exposent à de nouveaux dangers, notamment cyber-espionnage, vol de données à caractère personnel, et « morts » numériques par usurpation d’identité ou rançongiciels. Dans un avenir peu éloigné, « immergés » dans des véhicules terrestres ou aériens communicants à pilotage partiellement ou entièrement automatisé, ils s’exposeront en outre à des cyberattaques potentiellement létales (morts physiques par collisions).

Les réseaux formés spontanément par de tels véhicules sont un exemple particulièrement intéressant de systèmes de processus communicants mobiles. Certaines technologies au cœur de l’Internet du futur seront employées (par exemple, antennes embarquées compactes MIMO 5G de courte portée). D’autres innovations sont attendues comme, par exemple, short-lived privacy-preserving naming, proof-of-presence, self-aware computing. Il est nécessaire de démontrer que ces réseaux sont dotés de quatre propriétés fondamentales : safety, privacy, efficiency, cybersecurity. Cette condition est incontournable dans toute société motorisée soucieuse d’éthique et de respect de la vie humaine. La question clé est alors : comment concevoir pour pouvoir prouver ?

 (NDLR : ceci fera l’objet d’un futur article).

Glossaire

ABP                Alternating Bit Protocol

ack                  acknowledgement

ARQ               Automatic Repeat request

FIFO               First In First Out

IETF               Internet Engineering Task Force

IP                    Internet Protocol

MIMO            Multiple-Input Multiple-Output

MPLS             MultiProtocol Label Switching

nack                negative ack

OSI/ISO         Open Systems Interconnection/International Standards Organisation

PDU               Protocol Data Unit

RfC                 Request for Comments

RTT                Round Trip Time

TCP                Transmission Control Protocol

^[1] Les concepts de réseau non fiable (« best effort ») et de « message block » (devenu paquet/datagramme) furent inventés par Paul Baran (Rand Corporation) en 1960 et 1961.