Protocoles de réseau local DCN

La présente RFC est une description du protocole utilisé dans les réseaux locaux DCN pour maintenir la connexité, l’acheminement, et les informations de conservation de l’heure. Ces procédures peuvent intéresser les concepteurs et les mises en œuvre d’autres réseaux.

1 Introduction

Le présent document décrit l’architecture et les protocoles de réseau local du réseau informatique distribué (DCN, Distributed Computer Network), famille de réseaux locaux fondés sur la technologie de l’Internet et une mise en œuvre du logiciel fondé sur PDP11 appelé le Fuzzball. Les réseaux locaux DCN sont en fonctionnement depuis environ trois ans et comportent des clones aux USA, au Royaume-uni, en Norvège et en Allemagne. Ils comportent normalement un certain nombre de Fuzzballs PDP11 ou LSI-11, dont un est choisi comme passerelle, et comportent souvent aussi d’autres hôtes compatibles Internet.

Les protocoles DCN de réseau local sont destinés à fournir des fonctions de connexité, d’acheminement et de conservation de l’heure pour un ensemble d’ordinateurs individuels et hôtes de service connectés de façon aléatoire. La philosophie de conception qui guide la mise en œuvre de Fuzzball est d’incorporer la fonctionnalité complète dans chaque hôte, qui peut servir tout à la fois de commutateur de paquets, de passerelle et d’hôte de service. Lorsqu’un ensemble de Fuzzballs sont connectés ensemble en utilisant une collection fortuite d’interfaces en série, en parallèle ou de bus en concurrence, ils s’organisent eux-mêmes en un réseau avec l’acheminement fondé sur le délai minimum.

L’objet du présent document est de décrire les protocoles de réseau local utilisés par le DCN pour maintenir les fonctions de connexité, d’acheminement et de conservation de l’heure. Le document est une révision extensive et un développement du paragraphe 4.2 de [1] et il est divisé en deux parties, dont la première est une description informelle de l’architecture, avec des remarques explicatives. La seconde partie consiste en une spécification semi formelle des entités et protocoles utilisés pour déterminer la connexité, établir l’acheminement et maintenir la synchronisation d’horloges et elle est conçue pour aider à la mise en œuvre des systèmes en cohorte. Le codage de niveau liaison est décrit en appendice.

2 Description littérale

L’architecture DCN est conçue pour les réseaux locaux comportant jusqu’à 256 hôtes et passerelles utilisant le protocole Internet (IP) et ses protocoles clients. Elle procure des fonctions d’acheminement adaptatif et de synchronisation d’horloge dans une topologie arbitraire comportant des liaisons point à point et des systèmes de bus multipoints. Elle est destinée à être utilisée pour connecter des ordinateurs individuels les uns aux autres et avec des machines de service, des passerelles et autres hôtes de la communauté de l’Internet. Cependant, elle n’est pas destinée à être utilisée par les grands réseaux complexes et ne prend pas en charge les algorithmes sophistiqués d’acheminement et de contrôle, par exemple, de l’ARPANET.

Une brève description de la structure de traitement et d’adressage utilisée dans le DCN peut être utile pour la compréhension de la suite de l’exposé. Un hôte DCN physique est un processeur compatible PDP11 qui prend en charge un certain nombre de processus coopératifs séquentiels, dont chacun reçoit un identifiant unique de 8 bits appelé son identifiant d’accès (port ID). Chaque hôte DCN physique contient un ou plusieurs processus internet, dont chacun prend en charge un hôte virtuel auquel est donné un identifiant unique de 8 bits appelé son identifiant d’hôte (host ID.

Chaque hôte virtuel peut prendre en charge plusieurs protocoles internet, plusieurs connexions et, de plus, une horloge virtuelle. Chaque hôte physique contient une horloge physique qui peut fonctionner à un débit arbitraire, ainsi qu’une horloge logique à 32 bits qui fonctionne à 1000 Hz et est supposée être remise à zéro tous les jours à 0000 heure TU. Tous les hôtes physiques ne mettent pas en œuvre la précision complète de 32 bits ; cependant, dans de tels cas, la résolution de l’horloge logique peut être un peu inférieure.

Il y a une correspondance biunivoque entre les adresses Internet et les identifiants d’hôtes. L’identifiant d’hôte est formé à partir d’un octet spécifié de l’adresse Internet auquel est ajouté un décalage spécifié. Le numéro et le décalage d’octet sont choisis au moment de la configuration et doivent être les mêmes pour tous les hôtes DCN qui se partagent le réseau local. Pour les réseaux de classe B et de classe C, le quatrième octet est normalement utilisé de cette façon pour l’acheminement au sein du réseau local. Dans le cas des réseaux de classe B , le troisième octet est considéré comme faisant partie du numéro de réseau par les hôtes DCN ; donc, cet octet peut être utilisé pour l’acheminement entre les réseaux DCN locaux. Pour les réseaux de classe A, le troisième octet (champ d’hôte logique ARPANET) est normalement utilisé pour l’acheminement lorsque c’est nécessaire.

Chaque hôte physique DCN est identifié par un identifiant d’hôte pour les besoins de la détection de boucles dans les mises à jour d’acheminement, qui établissent les chemins de délai minimum entre les hôtes virtuels. Par convention, l’identifiant d’hôte physique est alloué comme identifiant d’hôte de l’un des ses hôtes virtuels. Un lien avec un réseau voisin est associé à un hôte virtuel particulier, appelé une passerelle, auquel est alloué un identifiant d’hôte unique.

Les liaisons connectant ensemble les divers hôtes physiques et les réseaux étrangers peuvent être distribuées de façon arbitraire, tant que le réseau reste pleinement connecté. Si la pleine connexité est perdue, due à une défaillance de liaison ou d’hôte, les hôtes virtuels dans chacun des segments subsistants peuvent continuer à fonctionner avec chacun des autres et, une fois la connexité restaurée, avec tous les autres.

L’acheminement des datagrammes est entièrement déterminé par l’adresse Internet – il n’y a pas d’en-tête local comme dans l’ARPANET. Chaque hôte physique contient deux tableaux, le tableau des hôtes, qui est utilisé pour déterminer la liaison sortante vers chaque autre hôte de réseau local, et le tableau des réseaux, qui est utilisé pour déterminer l’hôte de sortie (passerelle) vers chaque autre réseau. Le tableau des hôtes contient les estimations des délais d’aller-retour et de décalage d’horloge logique pour tous les hôtes virtuels dans le réseau et est indexé par identifiant d’hôte. Pour les besoins du calcul de ces estimations, le délai et le décalage de chaque hôte virtuel par rapport à l’hôte physique dans lequel il réside est supposé de zéro. La seule exception est celle d’un hôte virtuel spécial associé à un receveur de code horaire radio NBS, où le décalage est calculé par rapport à l’heure diffusée.

Le tableau des réseaux contient une entrée pour chaque réseau voisin qui peut être connecté au réseau local et, en plus, pour certains autres réseaux qui ne sont pas voisins. Chaque entrée contient le numéro de réseau, ainsi que l’identifiant d’hôte de la passerelle de réseau local vers ce réseau. La fonction d’acheminement regarde simplement le numéro de réseau dans le tableau des réseaux, trouve l’identifiant d’hôte de la passerelle et restitue l’identifiant de l’accès au processus de sortie de réseau à partir du tableau des hôtes. D’autres informations sont incluses dans le tableau des hôtes et le tableau des réseaux comme décrit ci-dessous.

Les estimations de délai et de décalage sont mises à jour par les messages HELLO échangés sur les liaisons qui connectent les hôtes physiques voisins. Les messages HELLO sont échangés fréquemment, mais pas au point de dégrader matériellement le débit de la liaison pour les messages de données ordinaires. Un message HELLO contient une copie des informations de délai et de décalage provenant du tableau des hôtes de l’envoyeur, ainsi que les informations pour calculer le délai d’aller-retour et le décalage d’horloge logique du receveur par rapport à l’envoyeur.

L’algorithme d’acheminement est similaire à celui (anciennement) utilisé dans l’ARPANET et autres lieux en ce que l’estimation du délai d’aller-retour (biaisé) calculé avec un voisin est ajoutée à chaque estimation de délai donnée dans son message HELLO et comparée aux estimations de délai correspondantes dans le tableau des hôtes. Si un délai calculé de cette façon est inférieur au délai figurant déjà dans le tableau des hôtes, l’acheminement avec l’hôte virtuel correspondant est changé en conséquence. Le fonctionnement détaillé de cet algorithme, qui inclut des dispositions pour la logique montante et descendante d’hôte et la suppression de boucle, est résumé dans un paragraphe ultérieur.

Les réseaux locaux DCN sont autoconfigurants pour tous les hôtes et les réseaux voisins ; c’est-à-dire que les algorithmes d’acheminement vont trouver les chemins à délai minimum entre tous les hôtes et passerelles vers les réseaux voisins. De plus, les informations de conservation de l’heure peuvent être échangées en utilisant des messages HELLO particuliers entre les réseaux locaux DCN voisins. Pour un acheminement au-delà des réseaux voisins, des entrées supplémentaires peuvent être configurées dans les tableaux de réseaux en tant que de besoin. De plus, une entrée particulière peut être configurée dans les tableaux de réseaux pour spécifier l’identifiant d’hôte de la passerelle avec tous les réseaux non explicitement inclus dans le tableau.

Pour l’acheminement via ARPANET et les réseaux qu’on peut atteindre à travers lui, un hôte de réseau local choisi est équipé d’une interface IMP et configuré avec un processeur de passerelle GGP/EGP. Ce processeur assure la maintenance du tableau des réseaux dans l’hôte local, incluant les conducteurs ARPANET, de façon dynamique au titre des interactions de protocole GGP/EGP avec les autres passerelles ARPANET. Les interactions de protocole GGP/EGP sont éventuellement aussi bien des passerelles non ARPANET.

La structure d’hôte virtuel portable utilisée dans le DCN invite à une interprétation assez large de l’adressage. Afin de minimiser la confusion par la suite, le terme "identifiant d’hôte" sera uniquement appliqué aux hôtes virtuels, tandis que "numéro d’hôte" sera appliqué aux hôtes physiques, appelés de façon générique hôtes DCN.

2.1 Tableaux des hôtes et des réseaux

Il y a dans chaque hôte DCN deux tableaux qui contrôlent l’acheminement des datagrammes du protocole Internet (IP) : le tableau des réseaux et le tableau des hôtes. Le tableau des réseaux sert à déterminer l’identifiant d’hôte de la passerelle (du routeur) sur la route d’un réseau étranger, tandis que le tableau des hôtes sert à déterminer la liaison, par rapport à l’hôte DCN, sur la route d’un hôte virtuel. Le tableau des hôtes est entretenu de façon dynamique à l’aide de mises à jour générées par des messages HELLO périodiques. Le tableau des réseaux est fixé au moment de la configuration pour tous les hôtes DCN excepté ceux qui prennent en charge un processus de passerelle GGP/EGP. Dans ce cas, le tableau des réseaux est mis à jour au titre du fonctionnement de la passerelle. De plus, les entrées dans l’un et l’autre tableau peuvent être changées par des commandes de l’opérateur.

Le format du tableau des réseau est indiqué à la Figure 1.

Figure 1. Entrée du tableau des réseaux

Le champ "Net Name" définit un nom court (RAD50) pour le réseau, alors que le champ "Net" définit la classe A/B/C du numéro de réseau. Le champ "Gateway ID" contient l’identifiant d’hôte de la première passerelle vers le réseau et le champ "Hops" contient le nombre de bonds jusqu’à lui. Les champs restants ne sont utilisés que par le processus de passerelle GGP/EGP et comporte le champ "Index", qui contient un indice dans la matrice d’acheminement, et le champ "Gateway Leader", qui contient l’amorce (à octet permuté) de réseau local pour la passerelle sur un réseau voisin.

Le tableau des réseaux contient un nombre indéfini d’entrées et se termine par une entrée particulière dont les champs "Net" sont mis à zéro. Si le champ "Hops" de cette entrée est inférieur à 255, le champ "Gateway ID" de cette entrée est utilisé pour tous les réseaux qui ne sont pas dans le tableau. Si le champ "Hops" est de 255, tous les réseaux qui ne sont pas explicitement mentionnés dans le tableau apparaissent comme injoignables.

Le format du tableau des hôtes est donné à la Figure 2.

Figure 2 : Entrée du tableau des hôtes

L’ordre de la position de chaque entrée du tableau des hôtes correspond à celui de son identifiant d’hôte. Le champ "Name" contient un nom (RAD50) abrégé pour une référence facile. Le champ "Port ID" contient l’identifiant d’accès du processus de sortie du réseau sur le plus court chemin vers son hôte virtuel et le champ "Delay" contient le délai d’aller-retour mesuré pour l’atteindre. Le champ "Offset" contient la différence entre l’horloge logique de cet hôte et l’horloge logique de l’hôte local. Le champ "Local Leader" contient des informations utilisées pour construire l’amorce locale du paquet sortant, pour les réseaux qui l’exigent. Le champ "Update Timestamp" contient la valeur de l’horloge logique au moment où l’entrée a été mise à jour pour la dernière fois, et le champ "TTL" la durée (en secondes) restante jusqu’à ce que l’hôte virtuel soit déclaré mort.

Tous les champs excepté le champ "Name" sont remplis au titre du processus de mise à jour de l’acheminement, qui est initié à l’arrivé d’un message HELLO provenant d’un hôte DCN voisin. Ce message prend la forme d’un datagramme IP qui porte le numéro de protocole réservé de 63 et d’un champ de données tel qu’indiqué à la Figure 3.

Figure 3 : Format de message HELLO

Il y a deux formats de message HELLO, selon la longueur du message. Un des formats, envoyé par un hôte DCN à un autre hôte sur le même réseau local, inclut à la fois la zone fixée et la zone d’hôte indiquées ci-dessus. Le second format, envoyé dans tous les autres cas, ne comporte que la zone fixée.

Noter que tous les champs de mots indiqués sont à octets permutés par rapport à la représentation PDP11 ordinaire. Le champ "Checksum" contient une somme de contrôle qui couvre les champs indiqués. Les champs "Date" et "Time" sont remplis avec la date et l’heure d’origine locales. Le champ "Timestamp" est utilisé dans le calcul du délai d’aller-retour (voir ci-dessous). Le champ "Offset" contient le décalage du bloc des adresses Internet utilisé par le réseau local. Les champs "Delay Host n" et "Offset Host n" représentent une copie des entrées correspondantes du tableau des hôtes comme elles existaient au moment de leur origine. Le champ "Hosts (n)" contient le nombre des entrées dans ce tableau.

2.2 Calculs de délai d’aller-retour

Périodiquement, chaque hôte DCN physique envoie un message HELLO à son voisin sur chacune des liaisons de communication qui leurs sont communes. Pour chacune de ces liaisons, l’envoyeur conserve un ensemble des variables d’état, qui inclut une copie du champ source-adresse du dernier message HELLO reçu.

Lors de la construction d’un message HELLO, l’envoyeur règle le champ d’adresse de destination à cette variable d’état et le champ d’adresse de source à sa propre adresse. Il remplie alors les champs "Date" et "Time" d’après son horloge logique et le champ "Timestamp" d’après une autre variable d’état. Il copie finalement les valeurs "Delay" et "Offset" d’après son tableau des hôtes dans le message.

Un hôte qui reçoit un message HELLO l’élimine si le format est mauvais ou si la vérification de la somme de contrôle échoue. Si elle est valide, il initialise une variable d’état de liaison pour montrer que la liaison est active. Chaque fois qu’un message HELLO est transmis dans cet état, la variable est décrémentée. Si elle descend jusqu’à zéro, la liaison est déclarée morte.

L’hôte vérifie ensuite si le champ d’adresse de source correspond à la variable d’état qui contient la dernière adresse mémorisée. S’il ne correspond pas, c’est que la liaison a été commutée sur un nouvel hôte, de sorte que les variables d’état sont évacuées et que la liaison est mise de force dans un état de récupération. L’hôte vérifie alors si le champ d’adresse de destination correspond à sa propre adresse. Si c’est le cas, c’est que le message s’est mis en boucle (ce qui n’est légal que dans le cas d’un réseau de diffusion) et les informations de délai d’aller-retour sont corrigées. Les zones d’hôte et de réseau sont ignorées dans ce cas. Sinon, les zones hôte et réseau du message sont traitées pour mettre à jour les tableaux hôte et réseau.

Les calculs de délai d’aller-retour sont effectués de la façon suivante. Les processus d’entrée/sortie de la liaison alloués à chaque liaison entretiennent une variable d’état interne qui est mise à jour lorsque chaque message HELLO est reçu et transmis. Lorsqu’un message HELLO est reçu, cette variable prend la valeur du champ "Time" moins l’heure du jour en cours. Puis le prochain message HELLO est transmis, et la valeur allouée au champ "Timestamp" est calculée comme les 16 bits de plus faible poids de cette variable plus l’heure du jour en cours. La valeur de cette variable est forcée à zéro si la liaison est défaillante ou si l’horloge logique du système a été remise à zéro depuis la réception du dernier message HELLO.

Si un message HELLO est reçu avec un champ "Timestamp" de zéro, aucun traitement autre que le remplissage de la variable d’état interne n’est effectué. Autrement, le délai d’aller-retour est calculé comme les 16 bits de plus faible poids de l’heure du jour en cours moins la valeur de ce champ. Afin de s’assurer de la plus grande précision, le calcul n’est effectué que si la longueur (en octets) du dernier message HELLO transmis correspond à la longueur du message HELLO reçu.

La technique ci-dessus rend le calcul indépendant des décalages et intervalles d’horloge entre les messages HELLO chez l’un ou l’autre hôte, protège contre les erreurs qui pourraient survenir du fait de la perte de messages HELLO et fonctionne même lorsqu’un hôte voisin transmet simplement en retour le message HELLO à son origine sans le modifier. Ce dernier comportement, typique des IMP et passerelles ARPANET, ainsi que des réseaux de diffusion, s’appuie sur le mécanisme de détection de boucle de façon à ce que des calculs corrects puissent être effectués et, de plus, que des mises à jour d’hôtes parasites puissent être évitées.

2.3 Mises à jour d’hôtes

Lorsque arrive un message HELLO qui aboutit à un calcul de délai d’aller-retour valide, on effectue un processus de mise à jour d’hôte. Cela consiste à ajouter tour à tour le délai d’aller-retour à chaque entrée "Delay Host n" dans le message HELLO et à comparer chacun de ces délais calculés au champ "Host Delay" de l’entrée correspondante du tableau des hôtes. Chaque entrée est alors mise à jour conformément aux règles suivantes :

1. Si la liaison assure la connexion avec un autre hôte DCN sur le même réseau et si l’identifiant d’accès (PID, port ID) du processus de sortie de la liaison correspond au champ "Port ID" de l’entrée, mettre alors l’entrée à jour.

2. Si la liaison assure la connexion avec un autre hôte DCN sur le même réseau, et si le PID du processus de sortie de la liaison ne correspond pas au champ "Port ID" et si le délai calculé est inférieur au champ "Host Delay" d’au moins un seuil de commutation spécifié (actuellement de 100 millisecondes), mettre alors l’entrée à jour.

3. Si la liaison assure la connexion avec un réseau étranger et s’il lui est alloué un identifiant d’hôte correspondant à l’entrée, mettre alors l’entrée à jour. Dans ce cas uniquement, utiliser pour délai calculé le délai d’aller-retour.

4. Si aucune des conditions ci-dessus n’est satisfaite, ou si l’hôte virtuel a été déclaré mort et si le champ "TTL" contient une valeur différente de zéro, aucune mise à jour n’est alors effectuée.

Le processus de mise à jour consiste à remplacer le champ "Delay" par le délai calculé, le champ "Port ID" par le PID du processus de sortie de la liaison, le champ "Update Timestamp" par l’heure courante et le champ "TTL" par une valeur spécifiée (actuellement de 120) en secondes. Si le délai calculé excède un intervalle spécifié maximum (actuellement de 30 secondes), l’hôte virtuel est déclaré mort en réglant le champ "Delay" correspondant au maximum et les champs restants comme auparavant. Pour les besoins du calcul du délai, des valeurs inférieures à un minimum spécifié (actuellement de 100 millisecondes) sont arrondies à ce minimum.

Le champ "Offset" est aussi remplacé durant le processus de mise à jour. Lorsque le message HELLO arrive, la valeur de l’horloge logique actuelle est soustraite du champ "Time" et la différence est ajoutée à la moitié du délai d’aller-retour. La somme résultante, qui représente le décalage de l’horloge locale avec l’horloge de l’envoyeur, est ajoutée au champ "Offset" correspondant du message HELLO et la somme remplace le champ "Offset" du tableau des hôtes. Et donc, le champ "Offset" dans le tableau des hôtes pour un hôte virtuel particulier n’est remplacé que si cet hôte est actif et sur le chemin de moindre délai vers l’hôte DCN.

L’objet du seuil de commutation en (2) ci-dessus et la spécification du délai minimum dans le processus de mise à jour est d’éviter des commutations inutiles entre les liaisons et les boucles transitoires qui peuvent survenir du fait des variations normales des délais de propagation. L’objet de la vérification du champ "TTL" en (4) ci-dessus est de s’assurer de la cohérence en purgeant tous les chemins vers un hôte virtuel lorsque cet hôte virtuel est défaillant.

En plus des mises à jour effectuées lorsqu’un message HELLO arrive, chaque hôte virtuel dans un hôte DCN effectue aussi une mise à jour périodique de sa propre entrée de tableau des hôtes. La procédure est identique à celle indiquée ci-dessus, excepté que le délai et le décalage calculés sont pris pour zéro. Au moins un des hôtes virtuels dans un hôte DCN doit avoir le même identifiant d’hôte que le numéro d’hôte alloué à l’hôte DCN lui-même et tous doivent avoir le même numéro de réseau alloué. En dehors de cela, il n’y a pas de restriction sur le nombre ou les adresses des processus internet résidents dans un même hôte DCN.

Il serait appréciable que les hôtes virtuels soient véritablement portables et puissent migrer sur le réseau, si une telle exigence devait se faire jour. Les protocoles de mise à jour d’hôte décrits ici assurent que les procédures d’acheminement convergent toujours vers les chemins de délai minimum via des liaisons opérationnelles et des hôtes DCN. Dans le cas de réseaux de diffusion tels que les Ethernets, les procédures sont légèrement modifiées comme décrit ci-dessous. Dans ce cas, les messages HELLO sont utilisés pour déterminer l’acheminement à partir des divers hôtes Ethernet vers des destinations en dehors du câble, ainsi que pour fournir la synchronisation.

2.4 Temporisations

Le champ "TTL" dans chaque entrée de tableau des hôtes est décrémenté une fois par seconde en fonctionnement normal. Et donc, si à la suite d’une mise à jour d’hôte, une autre mise à jour n’est pas reçue dans un intervalle correspondant à la valeur initialisée dans ce champ, il revient à zéro, point auquel l’hôte virtuel est déclaré mort et l’entrée du tableau des hôtes est réglée comme décrit ci-dessus. L’intervalle de 120 secondes utilisé actuellement fournit au moins quatre messages HELLO à générer par chaque voisin sur chaque liaison durant cet intervalle, car le délai maximum entre les messages HELLO est de 30 secondes sur la liaison la plus lente (1200 bit/s). Et donc, si un message HELLO est perdu, le nombre maximum de liaisons entre tout hôte virtuel et un autre est de quatre.

Le champ "TTL" est initialisé à 120 secondes lorsque survient une mise à jour et lorsque l’hôte virtuel est déclaré mort. Durant l’intervalle, ce champ revient à zéro immédiatement après avoir été déclaré mort, les mises à jour sont ignorées. Cela donne un intervalle décent pour que les mauvaises nouvelles se propagent tout autour du réseau et pour que les tableaux des hôtes dans tous les hôtes DCN reflètent le fait. Et donc, la formation de boucles d’acheminement est empêchée.

Les procédures de transmission de datagrammes IP invitent à décrémenter le champ "time-to-live" de l’en-tête IP une fois par seconde ou à chaque point où il est retransmis, quel que soit ce qui intervient en premier. La valeur utilisée actuellement à cette fin est 30, de sorte qu’un datagramme IP ne puisse pas vivre sur le réseau plus longtemps que ce nombre de secondes. C’est donc le délai maximum permis sur tout chemin entre deux hôtes virtuels. Si ce délai maximum est dépassé en calculant le délai d’aller-retour pour une entrée de tableau des hôtes, l’hôte virtuel correspondant sera déclaré mort.

L’intervalle entre les messages HELLO sur une liaison quelconque dépend du débit de données pris en charge par la liaison. En règle générale, cet intervalle est réglé à 16 fois la durée d’aller-retour espérée pour le paquet le plus long à envoyer sur cette liaison. Pour une transmission asynchrone à 1200 bit/s et des longueurs de paquet de 256 octets, cela correspond à un intervalle maximum de message HELLO d’environ 30 secondes.

Bien que le calcul du délai d’aller-retour, dont dépend le processus d’acheminement, soit relativement insensible au trafic et à l’encombrement du réseau, des variations stochastiques des valeurs calculées surviennent ordinairement du fait du codage (bourrage de bits ou de caractères) et des perturbations du support. Afin de supprimer les boucles et les changements de chemin non nécessaires, un seuil de commutation minimum est incorporé dans le mécanisme d’acheminement (voir ci-dessus). L’intervalle utilisé pour ce seuil, ainsi que pour le délai minimum sur tout chemin, est de 100 millisecondes.

3 Spécification formelle

Les paragraphes qui suivent forment un cadre formel qui décrit le protocole DCN HELLO. Ce protocole fonctionne entre les hôtes DCN voisins qui partagent une liaison point à point commune et fournit des fonctions de détermination automatique de la connexité, d’acheminement et de conservation de l’heure.

Les descriptions qui suivent sont organisées comme suit : d’abord, un résumé des structures des données décrit les variables globales et les formats de paquet. Puis sont décrits trois processus qui mettent en œuvre le protocole : les processus CLOCK, HELLO et HOST. La description de ces processus est organisée en paragraphes qui décrivent (1) les variables locales utilisées par ce processus, (2) les paramètres et constantes et (3) les événements qui initient ensemble le traitement avec les procédures qu’ils évoquent. Dans le cas des variables, on fait une distinction entre les variables d’état, qui conservent leur contenu entre les appels de procédure, et les temporaires, qui ont une durée de vie limitée au fonctionnement du processus. Excepté comme noté ci-dessous, le contenu initial des variables d’état est sans importance.

3.1 Structures des données

3.1.1 Variables globales

ADDRESS
C’est une variable temporaire en chaîne binaire de 32 bits utilisée pour contenir une adresse Internet.

CLOCK-HID
C’est une variable d’état en entiers de huit bits utilisée pour contenir l’identifiant d’hôte de l’hôte de réseau local à utiliser comme horloge maîtresse. Elle est initialisée à la valeur appropriée selon la configuration du réseau.

DATE
C’est une variable d’état en chaîne binaire de 16 bits utilisée pour contenir la date en format RT-11. Les bits 0-4 contiennent l’année, avec zéro correspondant à 1972, les bits 5-9 contiennent le jour du mois et les bits 10-14 contiennent le mois, commençant par le premier janvier.

DATE-VALID
C’est une variable d’état d’un bit utilisée pour indiquer si la date et l’heure locale sont synchronisées avec l’horloge maîtresse. Une valeur de un indique que l’horloge locale n’est pas synchronisée avec l’horloge maîtresse. Cette variable est initialisée à un lorsque l’heure locale passe minuit. Elle est réglée à zéro chaque fois qu’une mise à jour valide de la date et de l’heure est reçue de l’horloge maîtresse.

DELAY
C’est une variable temporaire d’entiers de 16 bits qui représente le délai d’aller-retour en millisecondes jusqu’à un hôte.

HID
C’est une variable temporaire d’entiers de huit bits qui contient l’identifiant d’hôte de certains hôtes sur le réseau local. Il y a une correspondance biunivoque entre les adresses Internet des hôtes locaux et leurs HID. La transposition entre eux est choisie comme base du numéro d’octet de l’adresse Internet. Pour les hôtes DCN, c’est le quatrième octet, alors que pour les hôtes directement connectés à un IMP ARPANET de classe A ou une passerelle, c’est le troisième octet (champ d’hôte logique). Le contenu de cet octet est à ajouter à ADDRESS-OFFSET pour former le HID associé à l’adresse.

HOLD
C’est une variable d’état de huit bits en compteur qui indique si les horodatages sont valides ou non. Lorsque HOLD est différent de zéro, les horodatages devraient être considérés comme invalides. Lorsqu’il est réglé à une valeur quelconque différente de zéro, le compteur décrémente jusqu’à zéro avec un battement de 1 Hz. Sa valeur initiale est zéro.

HOST-TABLE
C’est un tableau des entrées NHOSTS indexées par identifiant d’hôte (HID). Il y a une entrée pour chaque hôte dans le réseau local. Chaque entrée a le format suivant :

HOST-TABLE.DELAY
C’est un champ de 16 bits qui contient le délai calculé d’aller-retour en millisecondes pour l’hôte du HID.

HOST-TABLE.OFFSET
C’est un champ de 16 bits qui contient le décalage calculé signé en millisecondes qui doit être ajouté à l’horloge apparente locale pour être d’accord avec l’horloge apparente de l’hôte du HID.

HOST-TABLE.PID
C’est un champ de huit bits qui contient le PID du processus de sortie de réseau choisi par l’algorithme d’acheminement pour transmettre les paquets à l’hôte du HID.

HOST-TABLE.TTL
C’est un champ de huit bits utilisé comme indicateur de durée de vie. Il est décrémenté par le processus HOST une fois par seconde et initialisé à une valeur choisie lorsqu’un message HELLO est reçu. Le tableau est initialisé avec le champ HOST-TABLE.DELAY réglé à MAXDELAY pour toutes les entrées. Le contenu des autres champs est sans importance.

LOCAL-ADDRESS
C’est une variable d’état de chaîne binaire à 32 bits utilisée pour contenir l'adresse Internet de l'hôte local.

NET-TABLE
C’est un tableau des entrées NNETS avec le format suivant :

NET-TABLE.HID
C’est un champ de huit bits qui contient l’identifiant d’hôte du pseudo processus de transmission des paquets au tableau NET-TABLE.NET.

NET-TABLE.NET
C’est un champ de 24 bits qui contient un numéro de réseau Internet de classe A (huit bits), de classe B (16 bits) ou de classe C (24 bits). Noter que la largeur de champ réelle pour les numéros de réseau de classe B est de 24 bits afin de fournir une capacité de sous-réseau, dans laquelle les huit bits de plus fort poids des 16 bits de l’adresse d’hôte sont interprétés comme le numéro de sous-réseau.

Le tableau est construit au moment de la configuration et doit inclure une entrée pour chaque réseau qui est un voisin potentiel. Un réseau voisin est défini comme un réseau qui contient un hôte qui peut être directement connecté à un hôte sur le réseau local. L’entrée pour un tel réseau est initiée par NET-TABLE.NET réglé au numéro de réseau voisin et NET-TABLE.HID réglé à un identifiant d’hôte virtuel arbitraire non alloué à un autre hôte virtuel de réseau local.

Les entrées restantes dans NET-TABLE sont initiées au moment de l’amorçage initial avec les champs NET-TABLE.NET réglés à zéro et les champs NET-TABLE.HID réglés à un identifiant d’hôte choisi par la configuration pour être utilisé à la transmission des paquets à tous les réseaux autres que les réseaux voisins. Dans le cas où un module de passerelle est inclus dans la configuration d’hôte locale, les protocoles GGP et/ou EGP seront utilisés pour l’entretien de ces entrées ; alors que, dans le cas où il n’est pas inclus de module de passerelle, une seule de ces entrées est nécessaire.

OFFSET
C’est une variable temporaire d’entier signé de 16 bits qui représente le décalage en millisecondes à ajouter à l’heure de l’horloge apparente pour donner l’heure de l’horloge apparente de l’hôte voisin.

3.1.2 Paramètres

ADDRESS-OFFSET
C’est un entier qui représente la valeur du champ adresse Internet correspondant au premier hôte dans HOST-TABLE.

NHOSTS
C’est un entier qui définit le nombre des entrées dans HOST-TABLE.

NNETS
C’est un entier qui définit le nombre des entrées dans MET-TABLE.

3.1.3 Champs de paquet HELLO

PKT.ADDRESS-OFFSET
Ce champ de huit bits est copié de ADDRESS-OFFSET par l’envoyeur.

PKT.DATESTAMP
Les bits 0-14 de ce champ de 16 bits sont copiés de DATE par l’envoyeur, alors que le bit 15 est copié de DATE-VALID.

PKT.DATE-VALID
Ce champ d’un bit est le bit 15 de PKT.DATESTAMP.

PKT.DESTINATION
Ce champ de 32 bits fait partie de l’en-tête IP. Il est copié de HLO.NEIGHBOR-ADDRESS par l’envoyeur.

PKT.HOST-TABLE
C’est un tableau des entrées de PKT.NHOSTS, dont chaque entrée comporte deux champs. Les entrées sont indexées par identifiant d’hôte et ont le format suivant :

PKT.HOST-TABLE.DELAY
Ce champ de 16 bits est copié du champ HOST-TABLE.DELAY correspondant par l’envoyeur.

PKT.HOST-TABLE.OFFSET
Ce champ de 16 bits est copié du champ HOST-TABLE.OFFSET correspondant par l’envoyeur.

PKT.LENGTH
Ce champ de 16 bits fait partie de l’en-tête IP. Il est établi par l’envoyeur avec le nombre d’octets dans le paquet.

PKT.NHOSTS
Ce champ de huit bits est copié de NHOST par l’envoyeur.

PKT.SOURCE
Ce champ de 16 bits fait partie de l’en-tête IP. Il est copié de LOCAL-ADDRESS par l’envoyeur.

PKT.TIMESTAMP
Ce champ de 32 bits contient l’heure apparente à laquelle le paquet a été transmis en millisecondes après minuit TU.

PKT.TSP
Ce champ de 16 bits contient une variable utilisée dans les calculs de délai d’aller-retour.

3.2 Processus CLOCK (CLK)

Le système de conservation de l’heure entretient trois horloges : (1) l’horloge physique, qui est déterminée par un oscillateur/compteur matériel ; (2) l’horloge apparente, qui entretient l’heure utilisée par les processus clients et (3) l’horloge réelle, qui représente l’heure fournie par une référence externe. Les horloges apparente et réelle sont entretenues comme des quantités de 48 bits avec 32 bits de signification disponibles pour les processus client. Ces horloges tournent à 1000 Hz et sont remises à zéro à minuit TU.

Le processus CLOCK consiste en un ensemble de variables d’état ainsi qu’en un ensemble de procédures qui sont invoquées à la suite des interruptions matérielles et des demandes des clients. On suppose qu’un temporisateur d’intervalle est séparé logiquement du mécanisme d’horloge locale, bien que les deux puissent être déduits de la même source horaire.

3.2.1 Variables locales

CLK.CLOCK
C’est une variable d’état à point fixe de 48 bits utilisée pour représenter l’heure apparente. Le point décimal (la virgule) est à la droite du bit 16 (numérotés à partir de la droite au bit 0). Le bit 16 s’incrémente à un rythme équivalent à 1000 Hz indépendant de l’horloge matérielle. (Dans le cas de matériel à horloge programmable, la valeur de CLK.CLOCK doit être corrigée comme décrit ci-dessous.)

CLK.COUNT
C’est un registre matériel qui s’incrémente à un rythme R. Il peut être représenté par une simple horloge linéaire, qui provoque des interruptions au rythme de la fréquence de ligne, ou par une horloge programmable, qui contient un registre de 16 bits qui est programmé pour compter à un rythme de 1000 Hz et cause une interruption en cas de débordement. Le registre est considéré comme une variable à point fixe avec le point décimal (la virgule) à la droite du bit 0.

CLK.DELTA
C’est une variable d’état de 48 bits signés à point fixe utilisé pour représenter l’incrément à ajouter à CLK.CLOCK pour donner l’heure réelle. Le point décimal (la virgule) est à la droite du 16.

3.2.3 Paramètres

ADJUST-FRACTION
C’est un entier qui définit le coefficient d’ajustement utilisé pour calculer une fraction servant de multiplicateur de CLK.DELTA pour corriger CLK.CLOCK une fois par intervalle d’ajustement d’horloge. Une valeur de sept est suggérée.

ADJUST-INTERVAL
C’est un entier qui définit l’intervalle d’ajustement d’horloge en millisecondes. Une valeur de 500 (une demie seconde) est suggérée pour l’horloge linéaire et 4000 (quatre secondes) pour l’horloge à 1000 Hz.

CLOCK-TICK
C’est un entier à virgule fixe qui définit l’incrément en millisecondes à ajouter à CLK.CLOCK par suite d’un tic d’horloge. La virgule est à la droite du 16. Dans le cas d’une interruption d’une horloge linéaire, la valeur de CLOCK-TICK devrait être de 16,66666 (60 Hz) ou 20,00000 (50 Hz). Dans le cas de débordement d’une horloge programmable à 1000 Hz, la valeur devrait être 65536,00000.

HOLD-INTERVAL
C’est un entier qui définit le nombre de secondes que HOLD va décompter après la remise à zéro de CLK.CLOCK. L’intervalle qui en résulte doit être au moins aussi long que le HELLO-INTERVAL maximum utilisé par tout processus HELLO.

3.2.3 Événements et procédures

Événement INCREMENT-CLOCK
Cet événement est évoqué comme résultat d’une interruption de tic, dans le cas d’une horloge linéaire, ou d’un débordement de compteur, dans le cas d’une horloge à 1000 Hz. Il cause l’incrémentation de l’horloge logique de la valeur de CLOCK-TICK.

Événement ADJUST-CLOCK
Cet événement est évoqué toutes les ADJUST-INTERVAL millisecondes pour sauter de l’heure de l’horloge apparente à l’heure de l’horloge réelle telle que réglée par la procédure SET-CLOCK. Ceci est fait en soustrayant une fraction du facteur de correction CLK.DELTA de la valeur de CLK.DELTA et en ajoutant la même fraction à CLK.CLOCK. Cela continue jusqu’à ce que l’invocation suivante de SET-CLOCK ou de CLK.DELTA ait été réduite à zéro.

Les valeurs suggérées pour ADJUST-INTERVAL et ADJUST-FRACTION représentent un taux de remplacement maximum de moins de ± 2 ms par seconde, dans le cas d’une horloge à 1000 Hz. L’action vise à lisser les corrections d’horloge brutales reçues des systèmes voisins pour obtenir une référence locale de grande qualité, tout en s’assurant que l’heure de l’horloge apparente est toujours augmentée de façon monotone.

Événement DECREMENT-HOLD
Cet événement est évoqué une fois par seconde pour décrémenter la valeur de HOLD.

Procédure READ-CLOCK
Cette procédure est appelée par un processus client. Elle retourne l’heure apparente calculée comme la partie entière de la somme CLK.CLOCK plus CLK.COUNT. Noter que la précision de la valeur retournée est limitée à ± 1 milliseconde, de sorte que les processus client doivent s’attendre à ce que l’heure apparente "revienne en arrière" à l’occasion du fait de corrections de dérive. Lorsque cela arrive, le retour en arrière ne sera jamais supérieur à une milliseconde et ne surviendra jamais plus de deux fois par seconde.

Procédure SET-CLOCK
Cette procédure est appelée par un processus client. Elle établit un facteur de correction de l’heure en millisecondes. L’argument représente une quantité signée à virgule fixe de 32 bits avec la virgule à la droite du bit 0, qui est à ajouter à CLK.CLOCK de sorte que READ-CLOCK retourne ensuite l’heure réelle.

3.3 Processus HELLO

Le processus HELLO conserve la synchronisation horaire avec un processus HELLO voisin en utilisant le protocole HELLO. Il participe aussi à l’algorithme d’acheminement. Il y a un processus HELLO et un ensemble de variables d’état locales pour chaque liaison qui connecte l’hôte à un de ses voisins.

3.3.1 Variables locales

HLO.BROADCAST
C’est une variable d’état en commutateur à un bit. Mise à zéro pour une liaison point à point, elle est à un pour une liaison de diffusion (par exemple Ethernet).

HLO.KEEP-ALIVE
C’est une variable d’état en compteur de huit bits utilisée pour indiquer si la liaison est active. Elle est initialisée avec une valeur de zéro.

HLO.LENGTH
C’est une variable d’état d’entier de 16 bits utilisée pour noter la longueur en octets du dernier message HELLO envoyé.

HLO.NEIGHBOR-ADDRESS
C’est une variable d’état d’entier de 32 bits utilisée pour contenir l’adresse Internet de l’hôte voisin.

HLO.PID
C’est une variable d’état d’entier de huit bits utilisée pour identifier le processus de sortie de réseau associé à ce processus HELLO. Elle est initialisée par le noyau à la création du processus et reste inchangée ensuite.

HLO.POLL
C’est une variable d’état en commutateur de un bit. Réglée à un, le processus HELLO envoie spontanément des messages HELLO. Mise à zéro, le processus HELLO répond aux messages HELLO, mais ne les envoie pas spontanément.

HLO.TIMESTAMP
C’est une variable temporaire d’entier de 32 bits utilisée pour noter l’heure d’arrivée d’un message HELLO.

HLO.TSP
C’est une variable d’état d’entier de 16 bits signée utilisée dans les calculs de délai d’aller-retour.

3.3.2 Paramètres

HELLO-INTERVAL
C’est un entier qui définit l’intervalle en secondes entre les messages HELLO. Il va d’environ huit à un maximum de 30 secondes, selon la vitesse de la ligne.

HOLD-DOWN-INTERVAL
C’est un entier qui définit l’intervalle en secondes pendant lequel un hôte sera considéré comme actif suite à la réception d’un message HELLO indiquant que l’hôte est actif. Une valeur de 120 est suggérée.

KEEP-ALIVE-INTERVAL
C’est un entier qui définit l’intervalle, en unités de HELLO-INTERVAL, pendant lequel un processus HELLO va considérer la liaison comme active. Une valeur de quatre est suggérée.

MAXDELAY
C’est un entier qui définit le délai d’aller-retour maximum en secondes sur une chemin vers tout hôte joignable. Une valeur de 30 est suggérée.

MINDELAY
C’est un entier qui définit le seuil minimum de commutation en millisecondes en dessous duquel les routes ne seront pas changées. Une valeur de 100 est suggérée.

3.3.3 Événements et procédures

Événement INPUT-PACKET
Lorsqu’un paquet arrive, le processus d’entrée de réseau établit d’abord HLO.TIMESTAMP à la valeur retournée par la procédure READ-CLOCK, puis vérifie que le paquet a une amorce locale, un format d’en-tête IP et une somme de contrôle valides. Si le champ protocole dans l’en-tête IP indique un message HELLO, le paquet est passé au processus HELLO. Si on trouve une erreur, le paquet est abandonné.

Le processus HELLO vérifie d’abord que le paquet a un format d’en-tête IP et une somme de contrôle valides. Si on trouve une erreur, le paquet est abandonné. Autrement, il est traité comme suit :

1. Si PKT.SOURCE est égal à LOCAL-ADDRESS, la ligne vers l’hôte voisin est en boucle. Si c’est une liaison de diffusion (HLO.BROADCAST est mis à un), on ignore cette subtilité ; sinon, c’est considéré comme une erreur et tout traitement ultérieur est abandonné. Noter que, dans des configurations particulières qui impliquent d’autres systèmes (par exemple, les IMP ARPANET et les passerelles) il peut être utile d’utiliser un HELLO en boucle pour surveiller la connexité. La mise en œuvre DCN fournit cette caractéristique, mais elle n’est pas décrite ici.

2. Régler KEEP-ALIVE-INTERVAL à HLO.KEEP-ALIVE. Cela indique le nombre maximum d’intervalles de HELLO que le champ HLO.TSP considère comme valide.

3. Régler PKT.TIMESTAMP - HLO.TIMESTAMP à HLO.TSP. Cela fait partie du calcul de délai d’aller-retour. La valeur de HLO.TSP sera mise à jour et retournée au voisin dans le prochain message HELLO transmis. Ensuite, calculer le délai d’aller-retour brut et le décalage :

HLO.TIMESTAMP - PKT.TSP à DELAY et HLO.TSP + DELAY/2 à OFFSET.

Note : Dans le cas de liaison de diffusion (HLO.BROADCAST mis à un) régler DELAY à zéro.

4. N’effectuer cette étape que dans les cas de liaison non diffusion (HLO.BROADCAST mis à zéro). Si PKT.SOURCE n’est pas égal à HLO.NEIGHBOR-ADDRESS, un nouveau voisin est alors apparu sur cette liaison. Régler PKT.SOURCE à HLO.NEIGHBOR ADDRESS, MAXDELAY à DELAY et procéder à l’étape suivante. Cela forcera la ligne à être déclarée morte et résultera en un maintien de cycle. Autrement, si PKT.TSP est à zéro ou si HOLD est différent de zéro, le calcul de DELAY est alors invalide et le traitement ultérieur est abandonné. Noter qu’un maintien de cycle est forcé dans tous les cas si un nouveau voisin est reconnu.

5. Si le traitement atteint ce point, les variables DELAY et OFFSET peuvent être supposées valides ainsi que les données restantes dans le paquet. D’abord, si DELAY < MINDELAY, régler MINDELAY à DELAY. Cela évite les commutations de chemin inutiles quand la différence des délais n’est pas significative et a pour effet que sur les liaisons à faible délai l’algorithme d’acheminement dégénère en bond minimum plutôt qu’en délai minimum. Puis régler HLO.PID à PID. Il y a deux cas :

Cas 1 : PKT.NHOSTS est à zéro.
Cela sera le cas lorsque l’hôte voisin vient d’arriver ou est sur un réseau ou sous-réseau différent. Régler NEIGHBOR-ADDRESS à ADDRESS et invoquer la procédure ROUTE, qui va retourner l’identifiant d’hôte. Puis invoquer la procédure UPDATE. En cas d’erreur, ne rien faire mais retourner.

Cas 2 : PKT.NHOSTS est différent de zéro.
C’est le cas lorsque l’hôte voisin est sur le même réseau ou sous-réseau. D’abord, sauvegarder les valeurs de DELAY et OFFSET dans les variables temporaires F et G. Puis, pour chaque valeur de HID de zéro à NHOSTS-1 considérer l’entrée PKT.HOSTS-TABLE correspondante et faire ce qui suit : Régler F + PKT.HOST-TABLE.DELAY à DELAY et G + PKT.HOST-TABLE.OFFSET à OFFSET et invoquer la procédure UPDATE. Cela termine le traitement.

Procédure ROUTE
Cette procédure retourne l’identifiant d’hôte dans le HID de l’hôte représenté par la variable ADDRESS globale

1. D’abord, déterminer si l’hôte représenté par ADDRESS est sur le même réseau local que LOCAL-ADDRESS. Pour les besoins de cette comparaison les bits 0 à 7 et 16 à 31 sont comparés pour les réseaux de classe A et les bits 8 à 31 sont comparés pour les réseaux de classe B et classe C. Cela fournit une capacité d’indiquer les sous-réseaux lorsque les bits 0 à 7 et 16 à 23 (classe A) ou 8 à 15 (classe B) sont utilisés comme numéro de sous-réseau.

Cas 1 : L’hôte est sur le même réseau ou sous-réseau.
Extraire le champ d’adresse de ADDRESS, soustraire ADDRESS-OFFSET et mémoriser le résultat dans HID. Si 0 ≤ HID < NHOSTS, la procédure se termine normalement ; autrement elle se termine en condition d’erreur.

Cas 2 : L’hôte n’est pas sur le même réseau ou sous-réseau.
Chercher le NET-TABLE pour une correspondance des champs de réseau de LOCAL-ADDRESS et NET-TABLE.NET. Si elle existe, régler NET-TABLE.HID à HID et retourner normalement. Si le champ NET-TABLE.NET est à zéro, ce qui indique la dernière entrée dans le tableau, régler HET-TABLE.HID à HID et retourner normalement. Noter que, dans le cas d’hôtes comportant des modules de passerelle GGP/EGP, si aucune correspondance n’est trouvée, la procédure se termine en condition d’erreur.

Procédure UPDATE
Cette procédure met à jour l’entrée de HOST-TABLE indiquée par le HID en utilisant trois variables globales : DELAY, OFFSET et PID. Son objet est de mettre à jour l’entrée de HOST-TABLE correspondant au HID de l’identifiant d’hôte. Dans ce qui suit, toutes les références sont à cette entrée.

1. Si PID n’est pas égal à HOST-TABLE.PID, le chemin pour le HID d’hôte n’est pas via le processus de sortie de réseau associé à ce processus HELLO. Dans ce cas, si DELAY + MINDELAY > HOST-TABLE.DELAY, le chemin est plus long qu’un figurant déjà dans HOST-TABLE, aussi la procédure ne fait rien.

2. Cette étape n’est atteinte que si la route vers l’HID de l’hôte est via le processus de sortie de réseau associé à ce processus HELLO ou si la chemin nouvellement rapporté vers cet hôte est plus court d’au moins MINDELAY. Il y a deux cas :

Cas 1 : HOST-TABLE.DELAY < MAXDELAY.
Le chemin existant pour le HID de l’hôte est actif et c’est une liaison point à point (HLO.BROADCAST est réglé à zéro). Si DELAY < MAXDELAY, le chemin nouvellement rapporté est aussi actif. Procéder à l’étape suivante. Autrement, initier un cycle de maintien en réglant MAXDELAY à HOST-TABLE.DELAY et HOLD-DOWN-INTERVAL à HOST-TABLE.TTL et retourner.

Cas 2 : HOST-TABLE.DELAY ≤ MAXDELAY.
Le chemin existant pour le HID de l’hôte est mort. Si DELAY < MAXDELAY et HOST-TABLE.TTL est à zéro, la période de maintien a expiré et le chemin nouvellement rapporté a juste été activé. Procéder à l’étape suivante. Autrement retourner simplement.

3. Dans cette étape, l’entrée HOST-DELAY est mise à jour. Régler DELAY à HOST-TABLE.DELAY, HOLD-DOWN-INTERVAL à HOST-TABLE.TTL et HLO.PID à HOST-TABLE.PID.

4. Pour une conservation précise de l’heure, le décalage ne peut être considéré comme valide que si la longueur du dernier paquet HELLO transmis est égale à la longueur du dernier reçu. Et donc, si HLO.LENGTH égal PKT.LENGTH, régler OFFSET à HOST-TABLE.OFFSET ; autrement, laisser ce champ seul. Finalement, si HID est égal à CLOCK-HID et si le bit 15 (le bit DATE-VALID) de DATE est zéro, régler PKT.DATESTAMP à DATE et invoquer la procédure SET-CLOCK du processus CLOCK avec l’argument HLO.TIMESTAMP.

Événement OUTPUT-PACKET
Cet événement est invoqué toutes les HELLO-INTERVAL secondes. Il détermine si un message HELLO est à transmettre, le transmet et met à jour les variables d’état.

1. Si HLO.KEEP-ALIVE est différent de zéro, décrémenter sa valeur.

2. Si HLO.POLL est à zéro et si HLO.KEEP-ALIVE est à zéro, ne pas envoyer de message HELLO. Si l’un des deux est différent de zéro, initialiser les champs de paquet comme suit : LOCAL-ADDRESS à PKT.SOURCE, HLO.NEIGHBOR-ADDRESS à PKT.DESTINATION et DATE à PKT.DATESTAMP.

Note : PKT.DESTINATION est réglé à zéro si c’est une liaison de diffusion (HLO.BROADCAST mis à un). Noter aussi que le bit 15 de DATE est le bit DATE-VALID. Si ce bit est à un, le receveur ne mettra pas à jour son horloge maîtresse à partir des informations du paquet transmis. Cela n’est significatif que si l’hôte envoyeur est sur le chemin de moindre délai vers l’horloge maîtresse.

Régler PKT.TIMESTAMP à la valeur retournée de la procédure READ-CLOCK. Si HLO.KEEP-ALIVE est zéro ou si HOLD est différent de zéro, régler PKT.TSP à zéro ; autrement, régler PKT.TIMESTAMP + HLO.TSP à PKT.TSP.

3. Déterminer si le voisin est sur le même réseau ou sous-réseau. Si le voisin est sur un réseau différent, régler PKT.NHOSTS à zéro et passer à l’étape suivante. Autrement, régler NHOSTS à PKT.NHOSTS et pour chaque valeur de HID de zéro à PKT.HOSTS-1 copier les champs HOST-TABLE.DELAY et HOST-TABLE.OFFSET de l’entrée HOST-TABLE correspondante dans l’ordre dans le paquet. Pour chaque entrée copiée vérifier si le champ HOST-TABLE.PID correspond au HLO.PID du processus HELLO. S’il en est ainsi, une boucle de routage est possible. Dans ce cas, utiliser à la place MAXDELAY pour le champ de délai dans le paquet.

4. Finalement, régler HLO.LENGTH au nombre d’octets dans le paquet et envoyer le paquet.

3.4 Processus HOST (HOS)

Ce processus entretient les tableaux d’acheminement. Il est activé une fois par seconde pour examiner HOST-TABLE et décrémenter le champ HOST-TABLE.TTL pour chaque entrée. Il effectue aussi des fonctions de maintenance.

3.4.1 Variables locales

HOS.PID
C’est un entier de huit bits utilisé pour identifier le processus HOST. Il est initialisé par le noyau lorsque le processus est créé et reste ensuite inchangé.

HOS.HID
C’est une variable temporaire de huit bits.

3.4.2 Événements et procédures

Événement SCAN
Cet événement est invoqué une fois par seconde pour examiner le HOST-TABLE et effectuer les fonctions de maintenance.

1. Pour chaque valeur d’une variable temporaire F de zéro à NHOSTS-1, effectuer ce qui suit : régler LOCAL-ADDRESS à ADDRESS et invoquer la procédure ROUTE, qui va retourner le HID de l’hôte. Si F est égal à HID, régler DELAY et OFFSET tous deux à zéro, HOS.PID à PID et invoquer la procédure UPDATE. Cela fera que tous les paquets reçus avec l’adresse locale seront acheminés sur ce processus.

Si HOST-TABLE.TTL est à zéro, sauter cette étape. Autrement, décrémenter HOST-TABLE.TTL de un. Si le résultat est différent de zéro, sauter le reste de cette étape. Autrement, si HOST-TABLE.DELAY < MAXDELAY, régler HOLDOFF-INTERVAL à HOST-TABLE.TTL et MAXDELAY à HOST-TABLE.DELAY. L’effet de cette étape est de déclarer un maintien de cycle lorsqu’un hôte meurt.

4 Références

1. D.L. Mills, "Final Report on Internet Research, ARPA Packet SwitchingProgram." Rapport technique TSLAB 82-7, COMSAT Laboratories, décembre 1982.

Appendice A. Formats de paquet de niveau liaison

A.1 Liaisons en série utilisant des interfaces à interruption de programme

Ci-après figure une description du format de trame utilisé sur les liaisons en série asynchrones et synchrones avec des interfaces à interruption de programme telles que DEC DLV11 et DPV11. Ce format procure un codage transparent pour tous les messages, y compris les messages HELLO, mais ne fournit pas les fonctions de détection d’erreur ou de retransmission. Il est conçu pour être facilement mis en œuvre et compatible autant que possible avec les protocoles standard de l’industrie.

Le protocole est à bits en série, avec la même interprétation de l’ordre de transmission que pour les appareils d’interface asynchrones et synchrones standard; c’est-à-dire, le bit de plus faible poids de chaque octet est transmis en premier. La portion de données de la trame consiste en un datagramme Internet codé conformément à la convention de transparence de "bourrage de caractères" :

1. La trame commence par la séquence DLE-STX de deux octets, dans le cas de liaisons asynchrones, ou la séquence SYN-SYN-DLE-STX de quatre octets, dans le cas de liaisons synchrones. La portion de données est transmise ensuite, codée comme décrit ci-dessous, suivie par la séquence DLE-ETX de deux octets. Aucune somme de contrôle n’est transmise ni attendue. S’il est nécessaire pour une raison quelconque de transmettre un remplissage de temps autre que dans la portion des données, on utilise le DEL (tout en uns).

2. Au sein de la portion des données de la trame, la mémoire tampon d’émission est examinée à la recherche d’un DLE. Chaque DLE trouvé cause l’émission de la séquence DLE-DLE. S’il est nécessaire pour une raison quelconque que l’émetteur insère un remplissage de temps au sein de la portion des données, on utilise la séquence DLE-DEL.

3. Lorsque dans l’examen du flux des données au sein de la portion des données de la trame on trouve la séquence DLE-DLE, on insère un seul DLE dans la mémoire tampon de réception. Si on trouve la séquence DLE-ETX, la mémoire tampon est soumise au traitement. La séquence DLE-DEL est éliminée. Toute autre séquence de deux octets commençant par DLE et se terminant par autre chose que DLE, ETX ou DEL est considérée comme une erreur de protocole (voir la note ci-dessous).

Note : Dans le cas de liaisons synchrones qui utilisent des interfaces à interruption de programme telles que DPV11, par exemple, on suggère un protocole légèrement modifié lorsque les deux extrémités de la liaison sont d’accord. Ces interfaces fournissent normalement un registre des paramètres qui peut être chargé avec un code utilisé à la fois pour détecter le schéma de synchronisation du récepteur et pour le remplissage de temps lorsque le registre de mémoire tampon d’émission ne peut pas être servi à temps pour le prochain caractère.

Le registre des paramètres doit être chargé avec le code SYN pour que ce protocole fonctionne correctement. Cependant, s’il était nécessaire de transmettre le remplissage de temps, un seul SYN sera transmis, plutôt que la séquence DLE-DEL spécifiée. Les perturbations dues à ces événements peuvent être minimisées par l’utilisation des règles suivantes :

1. Si l’émetteur perçoit une condition de remplissage de temps (habituellement par un bit de commande alloué à cette fin) entre les trames ou immédiatement à la suite de la transmission d’un DLE, la condition est ignorée.

2. Si l’émetteur perçoit une condition de remplissage de temps à d’autres moments, il envoie la séquence DLE-CAN.

3. Si le receveur trouve un SYN entre les trames ou immédiatement après le DLE, le SYN est éliminé sans que cela affecte le décodage de la séquence.

4. Si le receveur trouve la séquence DLE-CAN dans la portion de données, il élimine la séquence et l’octet immédiatement précédant.

Ces règles fonctionneront dans les cas où un seul SYN a été inséré par l’émetteur et même lorsque un SYN a été inséré dans la séquence DLE-CAN. Si une condition de dépassement (données perdues) est perçue chez le receveur, l’action appropriée est de retourner à l’état de synchronisation initial. Ce devrait aussi être l’action si tout code autre que STX se trouve à la suite du DLE initial, ou si tout code autre que DLE, ETX, DEL ou CAN se trouve à la suite d’un DLE dans la portion des données.

A.2 Liaisons en série utilisant des appareils DDCMP

Ci-après figure une description du format de trame utilisé sur les liaisons DDCMP DEC avec des interfaces DMA telles que le DMV11 et DMR11 DEC. Ces interfaces mettent en œuvre le protocole DDCMP DEC, qui comporte des fonctions de détection d’erreur et de retransmission. Le format de trame DDCMP est le suivant :

Par rapport à ce diagramme, chaque octet est transmis en commençant par l’octet le plus à gauche, les bits de chaque octet transmis avec le bit de moindre poids en premier. Le contenu de tous les champs excepté le champ "Data" est géré par l’interface. Le datagramme Internet est placé dans ce champ comme il est, sans bourrage de caractère ou de bit (les dimensions de ce champ sont indiquées par l’interface dans le champ "Count".

A.3 Liaisons en série utilisant des appareils HDLC

Ci-après figure une description du format de trame utilisé sur les liaisons HDLC avec des interfaces à interruption de programme tels que le DPV11 DEC.

Par rapport à ce diagramme, chaque octet est transmis en commençant par l’octet le plus à gauche, les bits de chaque octet transmis avec le bit de moindre poids en premier. Le code xxxxxxxx représente la portion des données et cccccccc représente la somme de contrôle. Les bits entre les champs "Flag" sont codés avec une convention de bourrage des bits dans laquelle un bit zéro est bourré à la suite d’une chaîne de cinq bits à un. Les champs "Addr" et "Ctrl" ne sont pas utilisés et la somme de contrôle est ignorée. Le datagramme Internet est placé dans le champ "Data", qui doit être un multiple de huit bits en longueur.

A.4 Liaisons ARPANET 1822 utilisant des interfaces d’hôte local ou distant

Ci-après figure une description du format de trame utilisé avec les interfaces ARPANET 1822 locales ou distantes. Ces interfaces peuvent être utilisées pour connecter un hôte DCN à un IMP ARPANET, passerelle ou extenseur d’accès ou pour connecter deux hôtes DCN. Lorsqu’il est utilisé pour connecter un hôte DCN à un IMP ARPANET, passerelle ou extenseur d’accès, une amorce 1822 à 96 bits est ajoutée en tête du datagramme Internet. Le codage de cette amorce est décrit dans le rapport BBN 1822. Lorsqu’il est utilisé pour connecter deux hôtes DCN, aucune amorce n’est utilisée et la trame contient seulement le datagramme Internet.

A.5 Liaisons ARPANET 1822 utilisant des interfaces HDH

Ci-après figure une description du format de trame utilisé avec les interfaces HDH ARPANET 1822. Ces interfaces peuvent être utilisées pour connecter un hôte DCN à un IMP ARPANET ou un passerelle ou pour connecter deux hôtes DCN. Dans l’un et l’autre cas, le format de trame est décrit dans l’Appendice J du rapport BBN 1822.

A.6 Liaisons LAPB X.25 utilisant des interfaces RSRE

Ci-après figure une description du format de trame utilisé sur les liaisons LAPB X.25 avec les interfaces Royal Signals et Radar Establishment. Ces interfaces mettent en œuvre le protocole d’accès de liaison X.25 en mode équilibré (LAPB, Link Access Protocol Balanced), aussi connu sous le nom de protocole de niveau trame, utilisant un format de trame similaire à celui décrit en A.3 ci-dessus. Les datagrammes Internet sont placés dans la portion des données des trames I et codés avec la procédure de bourrage de bits décrite en A.3. Il n’y a pas de format de niveau paquet utilisé avec ces interfaces.

A.7 Liaisons Ethernet

Ci-après figure une description du format de trame utilisé sur les liaisons Ethernet.

Selon ce diagramme, chaque champ est transmis en commençant par le champ le plus à gauche, avec les bits de chaque champ transmis avec le bit de plus faible poids en premier. Les champs "Dest Addr" et "Srce Addr" contiennent les adresses Ethernet à 48 bits, alors que le champ "Type" contient la valeur allouée pour les datagrammes IP (0800 hex) ou pour les datagrammes ARP (0806 hex). Le datagramme Internet est placé dans le champ "Data" et il est suivi par la somme de contrôle de 32 bits. Le protocole de résolution d’adresse (ARP, Address Resolution Protocol) est utilisé pour établir la transposition entre l’adresse Ethernet et les adresses Internet.