Groupe de travail Réseau |
A. Rijsinghani, éditeur |
Request for Comments : 1624 |
Digital Equipment Corporation |
RFC mise à jour : 1141 |
mai 1994 |
Catégorie : Information |
Traduction Claude Brière de L'Isle |
Calcul de somme de contrôle Internet via mise à jour incrémentaire
Statut de ce mémoire
Le présent mémoire donne des informations pour la communauté de l'Internet. Il ne spécifie aucune sorte de norme de l'Internet. La distribution du présent mémoire n'est soumise à aucune restriction.
Résumé
Le présent mémoire décrit une technique mise à jour pour le calcul incrémentaire de la somme de contrôle standard Internet. Il met à jour la méthode décrite dans la RFC 1141.
La mise à jour incrémentaire de somme de contrôle est utile pour accélérer plusieurs types d'opérations effectuées de façon routinière sur les paquets IP, comme les mises à jour de TTL, la fragmentation IP, et la mise à jour de route de source.
La RFC 1071, au paragraphe 2.(C) point (4), décrit une procédure pour mettre à jour de façon incrémentaire la somme de contrôle Internet standard. L'exposé qui s'y rapporte, bien que compréhensible, n'était pas complète. La RFC 1141 a donc été publiée pour remplacer cette description de la mise à jour incrémentaire. En particulier, la RFC 1141 fait un exposé plus détaillé de la procédure décrite dans la RFC 1071. Cependant, elle calcule un résultat qui pour certains cas diffère de celui obtenu à partir des données d'origine (complément à un de la somme des compléments à un des champs d'origine).
Pour être complet, le présent mémoire souligne brièvement les points clés à partir des RFC 1071 et 1141. Sur la base de ces discussions, une procédure mise à jour pour le calcul par incréments de la somme de contrôle Internet standard est développée et présentée.
Soit la notation suivante :
HC - vieille somme de contrôle dans l'en-tête
C - somme des compléments à un de l'ancien en-tête
HC' - nouvelle somme de contrôle dans l'en-tête
C' - somme des compléments à un du nouvel hn-tête
m - ancienne valeur d'un champ de 16 bits
m' - nouvelle valeur d'un champ de 16 bits
La RFC 1071 déclare que C' est :
C' = C + (-m) + m' -- [Eqn. 1]
= C + (m' - m)
Comme le souligne la RFC 1141, l'équation ci-dessus n'est pas directement utile pour la mise à jour par incrément car C et C' ne se réfèrent pas à la somme de contrôle réellement mémorisée dans l'en-tête. De plus, elle souligne que la RFC 1071 ne spécifiait pas que toute l'arithmétique doit être effectuée en utilisant l'arithmétique de complément à un.
Finalement, pour compléter l'équation ci-dessus et obtenir la bonne somme de contrôle, la RFC 1141 présente ce qui suit :
HC' = ~(C + (-m) + m')
= HC + (m - m')
= HC + m + ~m' -- [Eqn. 2]
Bien que cette équation paraisse fonctionner, il y a des conditions limites dans lesquelles elle produit un résultat qui diffère de celui obtenu en calculant la somme de contrôle à partir des données brutes. Ceci est dû à la façon dont zéro est traité dans l'arithmétique de complément à un.
Dans le complément à un, il y a deux représentations du zéro : la valeur avec les bits tous à zéro et celle avec les bits tous à un, souvent mentionnées comme +0 et -0. L'addition des compléments à un des entrées non à zéro peut produire -0 comme résultat, mais jamais +0. Comme il est garanti qu'il y a au moins un champ non zéro dans l'en-tête IP, et que le champ somme de contrôle dans l'en-tête de protocole est le complément de la somme, le champ somme de contrôle ne peut jamais contenir ~(+0), qui est -0 (0xFFFF). Il peut, par contre, contenir ~(-0), qui est +0 (0x0000).
La RFC 1141 donne une somme de contrôle d'en-tête mise à jour de -0 alors qu'elle devrait être +0. Cela parce que l'on suppose que le complément à un a une propriété distributive, ce qui ne tient pas lorsque le résultat est 0 (voir la déduction de [Eqn. 2]).
Le problème est évité en ne supposant pas cette propriété. L'équation correcte est données ci-dessous :
HC' = ~(C + (-m) + m') -- [Eqn. 3]
= ~(~HC + ~m + m')
Considérons un en-tête de paquet IP dans lequel un champ de 16 bits m = 0x5555 se change en m' = 0x3285. Aussi, la somme des compléments à un de tous les autres octets de l'en-tête est 0xCD7A.
La somme de contrôle de l'en-tête devrait être :
HC = ~(0xCD7A + 0x5555)
= ~0x22D0
= 0xDD2F
La nouvelle somme de contrôle via le recalcul est :
HC' = ~(0xCD7A + 0x3285)
= ~0xFFFF
= 0x0000
En utilisant l'[Eqn. 2], comme spécifié dans la RFC 1141, la nouvelle somme de contrôle est calculée comme :
HC' = HC + m + ~m'
= 0xDD2F + 0x5555 + ~0x3285
= 0xFFFF
ce qui ne correspond pas à celle calculée à partir des données d'origine, et de plus qu'on ne peut jamais obtenir pour un en-tête IP.
En appliquant l'[Eqn. 3]à l'exemple ci-dessus, on obteint le résultat correct :
HC' = ~(C + (-m) + m')
= ~(0x22D0 + ~0x5555 + 0x3285)
= ~0xFFFF
= 0x0000
Si un système d'extrémité vérifie la somme de contrôle en incluant le champ de somme de contrôle lui-même dans la somme des compléments à un et en comparant ensuite le résultat à -0, comme recommandé par la RFC 1071, il est sans importance qu'un système intermédiaire ait généré un -0 à la place du +0 du fait de la propriété que la RFC 1141 a décrit ici. Dans l'exemple ci-dessus :
0xCD7A + 0x3285 + 0xFFFF = 0xFFFF
0xCD7A + 0x3285 + 0x0000 = 0xFFFF
Cependant, il existe des mises en œuvre qui vérifient la somme de contrôle en la calculant et en la comparant au champ Somme de contrôle de l'en-tête.
Il est recommandé que les systèmes intermédiaires calculent la somme de contrôle incrémentaire en utilisant la méthode décrite dans le présent document, et que les systèmes d'extrémité vérifient la somme de contrôle selon la méthode décrite dans la RFC 1071.
La méthode de [Eqn. 3] est légèrement plus coûteuse que celle de la RFC 1141. Si cela pose un problème, les deux instructions supplémentaires peuvent être éliminées en soustrayant les compléments qui font une retenue [voir la Section 7]. Il en résulterait l'équation suivante :
HC' = HC - ~m - m' -- [Eqn. 4]
Dans l'exemple donné ci-dessus,
HC' = HC - ~m - m'
= 0xDD2F - ~0x5555 - 0x3285
= 0x0000
Parenthèse historique : le fait que l'arithmétique standard de complément à un produise des résultats de zéros négatifs est un des principaus inconvénients ; cela donne des difficultés d'interprétation. Dans la série des ordinateurs CDC 6000 [4], ce problème était évité en utilisant la soustraction comme primitive dans l'arithmétique de complément à un (c'est-à-dire, l'addition est la soustraction du complément).
L'auteur remercie de leur contribution au travail qui a conduit au présent ouvrage les personnes suivantes :
Manu Kaycee - Ascom Timeplex, Incorporated
Paul Koning - Digital Equipment Corporation
Tracy Mallory - 3Com Corporation
Krishna Narayanaswamy - Digital Equipment Corporation
Atul Pandya - Digital Equipment Corporation
La condition d'échec a été découverte par suite d'essais IP sur un produit mettant en œuvre l'algorithme de la RFC 1141. Il a été analysé, et la mise à jour de l'algorithme a été imaginée. Cet algorithme a aussi été vérifié par simulation. Il a aussi été montré que la condition d'échec disparaît si la vérification de la somme de contrôle est faîte conformément à la RFC 1071.
Les questions de sécurité ne sont pas abordées dans le présent mémoire.
Il est recommandé que [Eqn. 3] ou [Eqn. 4] soient les mises en œuvre techniques utilisées pour la mise à jour incrémentaire de la somme de contrôle Internet standard.
Anil Rijsinghani
Digital Equipment Corporation
550 King St
Littleton, MA 01460
téléphone : (508) 486-6786
mél : anil@levers.enet.dec.com
[1] J. Postel, éd., "Protocole Internet - Spécification du protocole du programme Internet DARPA", STD 5, RFC 791, USC/Information Sciences Institute, septembre 1981.
[2] R. Braden, D. Borman et C. Partridge, "Calcul de la somme de contrôle Internet", RFC 1071, septembre 1988.
[3] T. Mallory et A. Kullberg, "Mise à jour incrémentaire de la somme de contrôle Internet", RFC 1141, janvier 1990.
[4] J. Thornton, "Design of a Computer -- the Control Data 6600", Scott, Foresman and Company, 1970.