Diffusion des datagrammes Internet
en présence de sous-réseaux

Statut de ce mémoire
On propose des règles simples pour la diffusion des datagrammes Internet sur les réseaux locaux qui acceptent la diffusion, pour l’adressage des diffusions, et pour la façon dont elle devrait être traitée par les routeurs.

La présente RFC suggère une proposition de protocole pour la communauté ARPA-Internet, et appelle à des discussions et des suggestions pour son amélioration. La distribution du présent mémoire n’est soumise à aucune restriction.

Remerciement
La proposition qui figure ici est le résultat de discussions avec plusieurs autres personnes, en particulier J. Noël Chiappa et Christopher A. Kent, qui m’ont tous deux signalé d’importantes références.

1. Introduction

L’utilisation des diffusions, en particulier sur les réseaux de zone locale à grande vitesse, est une bonne base pour de nombreuses applications. Comme la diffusion n’est pas traitée dans la spécification IP de base [12], il n’y a pas d’accord sur la façon de procéder, et donc les concepteurs de protocoles n’en ont pas fait usage. (La question a été abordée précédemment, par exemple dans [6], mais n’a pas encore fait l’objet d’une norme.)

Nous ne considérons ici que le cas de diffusions de datagrammes non fiables, non en séquence, éventuellement dupliqués (pour un exposé sur la diffusion TCP, voir [10].) Même si elles ne sont pas fiables et sont de longueur limitée, les diffusions de datagrammes sont assez utiles [1].

On suppose que la couche de liaison des données du réseau local accepte la diffusion efficace. La plupart des réseaux de zone locale courants acceptent la diffusion ; par exemple, Ethernet [7, 5], ChaosNet [9], les réseaux en anneau à jetons [2], etc.

Nous ne supposons cependant pas que la livraison des diffusions est fiable. (On peut considérer que la fourniture d’un protocole de diffusion fiable relève de la couche d’au-dessus d’IP.) Il est assez coûteux de garantir la livraison des diffusions ; au lieu de cela, ce que nous supposons est qu’un hôte va recevoir la plupart des diffusions envoyées. C’est important pour éviter une utilisation excessive de la diffusion ; comme chaque hôte sur le réseau consacre au moins quelques efforts pour chaque diffusion, cela fait un coût certain.

Lorsqu’un datagramme est en diffusion, il cause un coût pour chaque hôte qui le traite. Donc, la diffusion ne devrait pas être utilisée de façon inconsidérée, mais plutôt lorsqu’elle est la meilleure solution à un problème.

2. Terminologie

Parce que la diffusion dépend de la couche spécifique de liaison des données utilisée sur un réseau local, nous devons en discuter par référence à la fois aux réseaux physiques et aux réseaux logiques.

Les termes utilisés en référence aux réseaux physiques sont, du point de vue de l’hôte qui envoie ou transmet une diffusion :

Réseau matériel local : liaison physique à laquelle l’hôte est rattaché.

Réseau matériel distant : réseau physique qui est séparé de l’hôte par au moins un routeur.

Collection de réseaux matériels : ensemble de réseaux matériels connectés (transitivement) par des routeurs.

Le monde IP comporte plusieurs sortes de réseaux logiques. Pour éviter les ambiguïtés, nous utilisons les termes suivants :

Internet : la collection DARPA Internet de réseaux IP.

Réseau IP : un réseau ou une collection de plusieurs réseaux matériels qui a un numéro de réseau IP spécifique.

Sous-réseau : membre singulier de la collection des réseaux matériels qui composent un réseau IP. Les adresses d’hôte sur un sous-réseau donné partagent un numéro de réseau IP avec les hôtes sur tous les autres sous-réseaux de ce réseau IP, mais la partie adresse locale est divisée en champs numéro de sous-réseau et numéro d’hôte pour indiquer sur quel sous-réseau se trouve un hôte. On ne postule pas une division particulière de la partie adresse locale ; cela peut varier d’un réseau à l’autre.

L’introduction d’un niveau sous-réseau dans la hiérarchie d’adressage est une variante par rapport à la spécification IP [12], mais vu la prolifération de l’utilisation de sous-réseaux adressables, il est évident qu’un schéma de difffusion devrait prendre en charge l’existence des sous-réseaux. Pour plus d’informations sur les sous-réseaux, voir [8].

Dans le présent document, le terme "adresse d’hôte" se réfère au champ d’adresse de l’hôte sur le sous-réseau d’un réseau IP divisé en sous-réseaux, ou autrement au champ partie hôte.

Un réseau IP peut consister en un seul réseau matériel ou en une collection de sous-réseaux ; du point de vue d’un hôte sur un autre réseau IP,cela ne devrait pas avoir d’importance.

3. Pourquoi la diffusion ?

Les diffusions sont utiles lorsque un hôte a besoin de trouver des informations sans savoir exactement quels autres hôtes peuvent les fournir, ou lorsqu’un hôte veut fournir à temps des informations à un grand ensemble d’hôtes.

Lorsqu’un hôte a besoin d’informations qu’un ou plusieurs de ses voisins pourraient avoir, il pourrait avoir une liste des voisins à qui demander, ou il pourrait interroger tous ses voisins possibles jusqu’à ce que l’un d’eux réponde. L’utilisation d’une liste implicite crée des problèmes évidents de gestion de réseau (la liaison précoce est non flexible). D’un autre côté, l’interrogation de tous ses voisins est lente si on doit générer des adresses d’hôte plausibles, et si on doit les essayer jusqu’à ce que l’une d’elles fonctionne. Sur l’ARPANET, par exemple, il y a en gros 65 000 numéros d’hôte plausibles. La plupart des mises en œuvre IP ont utilisé des listes implicites (par exemple, les adresses des routeurs "principaux".) Heureusement, la diffusion donne un moyen simple et rapide pour qu’un hôte joigne tous ses voisins.

Un hôte peut aussi utiliser la diffusion pour fournir des informations à tous ses voisins ; par exemple, un routeur peut annoncer sa présence aux autres routeurs.

Une façon de voir la diffusion est de la considérer comme un substitut imparfait de l’envoi groupé, l’envoi de messages à un sous-ensemble des hôtes sur un réseau. En pratique, les diffusions sont habituellement utilisées lorsque c’est l’envoi groupé qui est désiré ; les paquets sont diffusés au niveau matériel, mais le logiciel de filtrage chez les hôtes de réception rend l’effet de l’envoi groupé.

D’autres exemples d’applications de diffusion figurent dans [1, 3].

4. Classes de diffusion

Il y a plusieurs classes de diffusion IP :

- Diffusion de datagrammes à une seule destination sur le réseau matériel local : un datagramme est destiné à un hôte IP spécifique, mais l’hôte qui envoie le diffuse à la couche de liaison des données, peut-être pour éviter d’avoir à faire le routage. Comme ce n’est pas une diffusion IP, la couche IP n’est pas impliquée, sauf qu’un hôte devrait éliminer les datagrammes qui ne lui sont pas destinés sans agitation inutile (c’est-à-dire, sans imprimer un message d’erreur).

- Diffusion à tous les hôtes sur le réseau matériel local : une valeur distinctive pour la partie numéro d’hôte de l’adresse IP indique la diffusion plutôt qu’un hôte spécifique. La couche IP de réception doit être capable de reconnaître cette adresse aussi bien que la sienne propre. Cependant, il pourrait encore être utile de faire la distinction à de plus hauts niveaux entre diffusion et non diffusion, en particulier dans les routeurs. C’est le cas de diffusion le plus utile ; il permet à un hôte de découvrir les routeurs sans tableaux incorporés, c’est la base des protocoles de résolution d’adresse, et c’est aussi utile pour accéder à des commodités comme les serveurs de nom, les serveurs de l’heure, etc., sans avoir besoin d’adresses incorporées.

- Diffusion à tous les hôtes sur un réseau matériel distant : il est occasionnellement utile d’envoyer une diffusion à tous les hôtes sur un réseau non local ; par exemple, pour trouver la dernière version d’une base de données de noms d’hôtes, pour lancer un hôte sur un réseau IP sans serveur de lancement, ou pour surveiller les serveurs de l’heure sur le réseau IP. Ce cas est le même que les diffusions sur réseau local ; le datagramme est acheminé par les mécanismes normaux jusqu’à ce qu’il atteigne un routeur rattaché au réseau IP de destination, point auquel il est diffusé. Cette classe de diffusion est aussi appelée "diffusion dirigée", ou de façon pittoresque comme une "lettre explosive" [1].

- Diffusion à tous les hôtes sur un réseau IP divisé en sous-réseaux (diffusion multi sous-réseaux) : une valeur distinctive de la partie numéro de sous-réseau de l’adresse IP est utilisée pour indiquer "tous les sous-réseaux". Les diffusions à tous les hôtes d’un réseau IP distant divisé en sous-réseaux sont faites juste comme si elles étaient diffusées directement à un seul sous-réseau.

- Diffusion à l’ensemble de l’Internet : ceci n’est probablement pas utile, et presque certainement pas souhaitable.

Pour des raisons de performances ou de sécurité, un routeur peut choisir de ne pas retransmettre les diffusions ; en particulier, il peut être une bonne idée d’interdire les diffusions à l’intérieur ou en sortie d’un groupe autonome de réseaux.

5. Méthodes de diffusion

La couche IP de réception d’un hôte doit être modifiée pour prendre en charge la diffusion. En l’absence de diffusion, un hôte détermine si il est le receveur d’un datagramme en confrontant l’adresse de destination à toutes ses adresses IP. Avec la diffusion, un hôte doit comparer l’adresse de destination non seulement aux adresses de l’hôte, mais aussi à toutes les adresses de diffusion possibles pour cet hôte.

Le problème de savoir quelle est la meilleure méthode d’envoi d’une diffusion a été exposé en détail dans [1, 3, 4, 13, 14]. Comme nous supposons que le problème a déjà été résolu à la couche de liaison des données, un hôte IP qui souhaite envoyer une diffusion locale ou une diffusion dirigée a seulement besoin de spécifier l’adresse de destination appropriée et d’envoyer le datagramme comme d’habitude. Les algorithmes sophistiqués ne sont nécessaires que dans les routeurs.

Le problème de la diffusion à tous les hôtes sur un réseau IP divisé en sous-réseaux est apparemment un peu plus difficile. Cependant, même dans ce cas, il ressort que les algorithmes les plus connus n’exigent pas de complexité supplémentaire dans les hôtes qui ne sont pas des routeurs. Une bonne méthode de diffusion satisfera aux critères additionnels suivants :

- Pas de modification du format du datagramme IP.

- Efficacité raisonnable en termes de nombre de copies excédentaires générées et de coût des chemins choisis.

- Minimisation des modifications de routeurs, à la fois en code et en espace de données.

- Haute vraisemblance de livraison.

L’algorithme qui semble le meilleur est la méthode de transmission de chemin inverse (RPF, Reverse Path Forwarding) [4]. Bien que RPF soit sous optimal en coût et en fiabilité, il est assez bon, et est extrèmement simple à mettre en œuvre, n’exigeant aucun espace de données additionnel dans un routeur.

6. Routeurs et diffusions

L’essentiel de la complexité de la prise en charge des diffusions réside dans les routeurs. Si un routeur reçoit une diffusion dirigée pour un réseau auquel il n’est pas connecté, il la transmet simplement en utilisant le mécanisme usuel. Autrement, il doit faire un peu de travail supplémentaire.

6.1 Diffusions locales

Lorsqu’un routeur reçoit un datagramme de diffusion locale, il y a plusieurs choses qu’il pourrait avoir à en faire. La situation est sans ambiguïté, mais si on n’y prend garde, il est possible de créer des boucles infinies.

L’action appropriée à effectuer à réception d’un datagramme en diffusion dépend de plusieurs choses : du sous-réseau sur lequel il est reçu, du réseau de destination, et des adresses du routeur.

- La règle principale pour éviter les boucles est de "ne jamais diffuser un datagramme sur le réseau matériel sur lequel il a été reçu". Il n’est pas suffisant de simplement éviter de répéter les datagrammes qu’un routeur a écouté en provenance de lui-même ; cela permet encore les boucles si il y a plusieurs routeurs sur un réseau matériel.

- Si le datagramme est reçu sur le réseau matériel auquel il est adressé, il ne devrait alors pas être retransmis. Cependant, le routeur devrait se considérer lui-même comme une destination du datagramme (par exemple, il pourrait être une mise à jour de tableau d’acheminement.)

- Autrement, si le datagramme est adressé à un réseau matériel auquel est connecté le routeur, il devrait être envoyé comme une diffusion (de couche de liaison des données) sur ce réseau. Cette fois encore, le routeur devrait se considérer comme destination du datagramme.

- Autrement, le routeur devrait utiliser sa procédure d’acheminement normale pour choisir un routeur suivant, et lui envoyer le datagramme.

6.2 Diffusions multi sous-réseaux

Lorsqu’un routeur reçoit une diffusion destinée à tous les sous-réseaux d’un réseau IP, il doit utiliser l’algorithme de transmission de chemin inverse pour décider quoi faire. La méthode est simple : le routeur devrait transmettre des copies du datagramme sur toutes les liaisons connectées, si et seulement si le datagramme est arrivé sur la liaison qui fait partie de la meilleure route entre le routeur et la source du datagramme. Autrement, le datagramme devrait être éliminé.

Cet algorithme peut être amélioré si certains ou tous les routeurs échangent entre eux des information s supplémentaires ; cela peut être fait de façon transparente du point de vue des autres hôtes et même des autres routeurs. Voir d es précisions en [4, 3].

6.3 Algorithme pseudo-Algol d’acheminement

Voici une descrition en pseudo-Algol de l’algorithme d’acheminement que devrait utiliser un routeur. L’algorithme est décrit par la Figure 1. Voici quelques définitions :

RouteLink(host) : fonction qui prend l’adresse de l’hôte comme un paramètre et retourne la liaison du premier bond à partir du routeur vers l’hôte.
RouteHost(host) : comme ci-dessus mais retourne l’adresse de l’hôte du premier bond.
ResolveAddress(host) : Retourne l’adresse de matériel pour un hôte IP.
IncomingLink : liaison sur laquelle le paquet est arrivé.
OutgoingLinkSet : ensemble des liaisons sur lesquelles le paquet devrait être envoyé.
OutgoingHardwareHost : adresse d’hôte matériel à laquelle envoyer le paquet.
Destination.host : partie hôte de l’adresse de destination.
Destination.subnet : partie sous-réseau de l’adresse de destination.
Destination.ipnet : partie réseau IP de l’adresse de destination.

BEGIN
IF Destination.ipnet IN AllLinks THEN
BEGIN
IF IsSubnetted(Destination.ipnet) THEN
BEGIN
IF Destination.subnet = BroadcastSubnet THEN
BEGIN /* utiliser l’algorithme de transmission de chemin inverse */
IF IncomingLink = RouteLink(Source) THEN
BEGIN IF Destination.host = BroadcastHost THEN
OutgoingLinkSet <- AllLinks -
IncomingLink;
OutgoingHost <- BroadcastHost;
Examiner le paquet pour une éventuelle utilisation interne ;
END
ELSE /* dupliqué d’un autre routeur, éliminer */
Discard;
END
ELSE
IF Destination.subnet = IncomingLink.subnet THEN
BEGIN /* la transmision causerait une boucle */
IF Destination.host = BroadcastHost THEN
Examiner le paquet pour une éventuelle utilisation interne ;
Discard;
END
ELSE BEGIN /* transmettre au sous-réseau (éventuellement local) */
OutgoingLinkSet <- RouteLink(Destination);
OutgoingHost <- RouteHost(Destination);
END
END
ELSE BEGIN /* destiné à un de nos réseaux locaux */
IF Destination.ipnet = IncomingLink.ipnet THEN
BEGIN /* la transmision causerait une boucle */
IF Destination.host = BroadcastHost THEN
Examiner le paquet pour une éventuelle utilisation interne ;
Discard;
END
ELSE BEGIN /* pourrait être une diffusion */
OutgoingLinkSet <- RouteLink(Destination);
OutgoingHost <- RouteHost(Destination);
END
END
END
ELSE BEGIN /* transmettre à un réseau IP non local */
OutgoingLinkSet <- RouteLink(Destination);
OutgoingHost <- RouteHost(Destination);
END
OutgoingHardwareHost <- ResolveAddress(OutgoingHost);
END

Figure 1 : Algorithme en pseudo-Algol pour l’acheminement de diffusions par les routeurs

7. Adressage des diffusions IP - Conventions

Si des mises en œuvre IP différentes doivent être compatibles, il doit y avoir un numéro distinctif convenu pour noter "tous les hôtes".

Comme la couche réseau locale peut toujours transposer une adresse IP en adresse de couche liaison des données, le choix d’un "numéro d’hôte de diffusion" IP est un peu arbitraire. Par souci de simplicité, il devrait être d’un type qu’il est peu vraisemblable d’allouer à un hôte réel. Un numéro dont les bits sont tous à un possède cette propriété ; cette allocation avait d’abord été proposée dans [6]. Dans les quelques cas où il a été alloué à un hôte une adresse avec une partie numéro d’hôte tout à un, il ne semble pas exorbitant d’exiger une renumérotation.

Le numéro "tous les sous-réseaux" est aussi tout à un ;cela signifie qu’un hôte qui souhaite diffuser à tous les hôtes sur un réseau IP distant n’a pas besoin de savoir comment d’adresse de destination est subdivisée en champs sous-réseau et hôte, ou si même elle a des subdivisions. Par exemple, 36.255.255.255 peut noter tous les hôtes sur un seul réseau matériel, ou tous les hôtes sur un réseau IP subdivisé en sous-réseaux avec un octet de champ sous-réseau et deux octets de champ hôte, ou toute autre division possible.

L’adresse 255.255.255.255 note une diffusion sur un réseau matériel local, qui ne doit pas être retransmise. Cette adresse peut être utilisée, par exemple, par des hôtes qui ne connaissent pas leur numéro de réseau et le demandent à un serveur.

Et donc, un hôte sur le réseau 36, par exemple, peut :

- diffuser à tous ses voisins immédiats en utilisant 255.255.255.255

- diffuser à tout le réseau 36 en utilisant 36.255.255.255

sans savoir si le réseau est subdivisé en sous-réseaux ; si il ne l’est pas, les adresses ont toutes deux le même effet. Une application robuste peut essayer la première adresse, et si elle ne reçoit pas de réponse, essayer alors la seconde. Voir dans [1] un exposé sur de telles techniques "de recherche par anneau d’expansion".

Si l’utilisation de "tout à un" dans un champ d’une adresse IP signifie "diffusion", l’utilisation de "tout à zéro" pourrait être comprise comme signifiant "non spécifié". Il n’y a probablement aucune raison qu’une telle adresse apparaisse quelque part sauf comme adresse de source d’un datagramme de demande d’informations ICMP. Cependant, comme convention rédactionnelle, on se réfère aux réseaux (par opposition aux hôtes) en utilisant des adresses avec des champs de zéros. Par exemple, 36.0.0.0 signifie "réseau numéro 36" alors que 36.255.255.255 signifie "tous les hôtes sur le réseau numéro 36".

7.1 Serveurs ARP et diffusions

Le protocole de résolution d’adresse (ARP, Address Resolution Protocol) décrit en [11] peut, s’il est mise en œuvre de façon incorrecte, causer des problèmes lorsque les diffusions sont utilisées sur un réseau où tous les hôtes ne partagent pas la compréhension de ce qu’est une adresse de diffusion. IL est tentant de modifier le serveur ARP de façon à ce qu’il fournisse la transposition entre l’adresse de diffusion IP et l’adresse de diffusion matérielle.

On doit résister à cette tentation. Un serveur ARP ne devrait jamais répondre à une demande dont la cible est une adresse de diffusion. Une telle demande ne peut venir que d’un hôte qui ne reconnaît pas l’adresse de diffusion comme telle, et donc y donner suite conduirait presque certainement à une boucle de transmission. Si il y a N hôtes de ce type sur le réseau physique qui ne reconnaissent pas cette adresse comme une diffusion, un datagramme envoyé alors avec une durée de vie de T pourrait éventuellement donner naissance à T**N (T N) diffusions parasites.

8. Références

1. David Reeves Boggs. “Internet Broadcasting”. Thèse de doctorat, Stanford University, janvier 1982.

2. D.D. Clark, K.T. Pogran et D.P. Reed. "An Introduction to Local Area Networks". Proc. IEEE 66, 11, pp1497-1516, 1978.

3 Yogan Kantilal Dalal. “Broadcast Protocols in Packet Switched Computer Networks”. Thèse de doctorat, Stanford University, avril 1977.

4. Yogan K. Dalal et Robert M. Metcalfe. "Reverse Path Forwarding of Broadcast Packets". Comm. ACM 21, 12, pp1040-1048, décembre 1978.

5. “The Ethernet, a Local Area Network: Data Link Layer and Physical Layer Specifications”. Version 1.0, Digital Equipment Corporation, Intel, Xerox, septembre 1980.

6. Robert Gurwitz and Robert Hinden. “IP - Local Area Network Addressing Issues”. IEN-212, Bolt Beranek and Newman, septembre 1982.

7. R.M. Metcalfe and D.R. Boggs. "Ethernet: Distributed Packet Switching for Local Computer Networks". Comm. ACM 19, 7, pp395-404, juillet 1976. Aussi CSL-75-7, Xerox Palo Alto Research Center, repris dans CSL-80-2.

8. Jeffrey Mogul. “Sous-réseaux Internet”. RFC-917, Stanford University, octobre 1984.

9 David A. Moon. “Chaosnet”. A.I. Memo 628, Massachusetts Institute of Technology Artificial Intelligence Laboratory, juin 1981.

10 William W. Plummer. “Internet Broadcast Protocols ” . IEN-10, BBN, mars 1977.

11 David Plummer. “Protocole Ethernet de résolution d’adresse”. RFC 826, Symbolics, septembre 1982.

12 Jon Postel. “Protocole Internet”. RFC 791, ISI, septembre 1981.

13 David W. Wall. “Mechanisms for Broadcast and Selective Broadcast”. Thèse de doctorat, Stanford University, juin 1980.

14 David W. Wall and Susan S. Owicki. “Center-based Broadcasting ” . Computer Systems Lab Technical Report TR189, Stanford University, juin 1980.