Groupe de travail Réseau

R. Braden, ISI

Request for Comments : 1071

D. Borman, Cray Research

 

C. Partridge, BBN Laboratories

Traduction Claude Brière de L'Isle

septembre 1988

 

 

Calcul de la somme de contrôle Internet

 

 

Statut de ce mémoire

Le présent mémoire récapitule les techniques et algorithmes pour un calcul efficace de la somme de contrôle Internet. Ce n'est pas une norme, mais un ensemble utile de techniques de mise en œuvre. La distribution du présent mémoire n'est soumise à aucune restriction.

 

1.   Introduction

 

Le présent mémoire expose les méthodes de calcul efficace de la somme de contrôle Internet qui est utilisée par les protocoles standard de l'Internet IP, UDP, et TCP.

 

Une mise en œuvre efficace de somme de contrôle est critique pour de bonnes performances. Alors que les avancées des techniques de mise en œuvre rationalisent le traitement du protocole, le calcul de la somme de contrôle devient, par exemple, un des facteurs de limitation des performance de TCP. Il est normalement approprié de soigner la routine de somme de contrôle, en exploitant toutes les astuces possibles offertes par la machine ; une fraction de microseconde par octet de données TCP peut ajouter une économie globale de temps de CPU significative.

 

Dans les grandes lignes, l'algorithme de somme de contrôle Internet est très simple :

 

(1)   Les octets adjacents dont il faut faire la somme de contrôle sont mis par paires pour former des entiers de 16 bits, et on forme la somme des compléments à un de ces entiers de 16 bits.

 

(2)   Pour générer une somme de contrôle, le champ Somme de contrôle est lui-même éliminé, la somme des compléments à 1 de 16 bits est calculée sur les octets concernés, et le complément à 1 de cette somme est placé dans le champ Somme de contrôle.

 

(3)   Pour vérifier une somme de contrôle, la somme des compléments à 1 est calculée sur le même ensemble d'octets, y compris le champ somme de contrôle. Si le résultat donne tous les bits à 1 (-0 en arithmétique de complément à un), la vérification est réussie.

 

Supposons qu'une somme de contrôle soit à calculer sur la séquence d'octets A, B, C, D, ... , Y, Z. En utilisant la notation [a,b] pour l'entier de 16 bits a*256+b, où a et b sont des octets, alors la somme de 16 bits des compléments à 1 de ces octets est donnée par une des expressions suivantes :

 

[A,B] +' [C,D] +' ... +' [Y,Z]   [1]

[A,B] +' [C,D] +' ... +' [Z,0]   [2]

 

où +' indique l'addition de complément à 1. Ces cas correspondent respectivement à un compte pair ou impair d'octets.

 

Sur une machine à complément à 2, la somme des compléments à 1 doit être calculée au moyen d'un "report circulaire" (end around carry), c'est-à-dire, que tout débordement des bits de plus fort poids est ajouté aux bits de moindre poids. Voir les exemples ci-après.

 

La section 2 explore les propriétés de cette somme de contrôle qui peuvent être exploitées pour accélérer le calcul. La section 3 contient des exemples numériques des plus importantes techniques de mise en œuvre. Finalement, la section 4 comporte des exemples d'algorithmes spécifiques pour divers types de CPU communs. Merci à Van Jacobson et Charley Kline pour leur contribution aux algorithmes de cette section.

 

Les propriétés de la somme de contrôle Internet ont été à l'origine exposées par Bill Plummer dans l'IEN-45, intitulée "Conception de la fonction de Somme de contrôle". Comme l'IEN-45 n'a pas été largement diffusée, elle est incluse comme appendice à la présente RFC.

 

2.   Calcul de la somme de contrôle

 

Cette simple somme de contrôle a un certain nombre de merveilleuses propriétés mathématiques qui peuvent être exploitées pour accélérer son calcul, comme nous allons le montrer maintenant.

 

(A)   Commutative et associative

Tant que l'allocation des octets pairs/impairs est respectée, la somme peut être faite dans n'importe quel ordre, et elle peut être partagée en groupes arbitraires.

 

Par exemple, la somme [1] peut être séparée en :

 

( [A,B] +' [C,D] +' ... +' [J,0] ) +' ( [0,K] +' ... +' [Y,Z] )   [3]

 

(B)   Indépendance à l'ordre des octets

La somme des entiers de 16 bits peut être calculée avec les octets dans n'importe quel ordre. Et donc, si nous calculons la somme intervertie :

 

[B,A] +' [D,C] +' ... +' [Z,Y]   [4]

 

le résultat est le même que celui de [1], excepté que les octets sont intervertis dans la somme ! Pour voir pourquoi il en est ainsi, observons que dans les deux ordres les reports sont les mêmes : du bit 15 au bit 0 et du bit 7 au bit 8. En d'autres termes, un échange cohérent des octets effectue simplement une rotation des bits au sein de la somme, mais n'affecte pas leur ordre interne.

 

Donc, la somme peut être calculée exactement de la même façon sans considération de l'ordre des octets ("gros boutien" ou "petit boutien") du matériel sous-jacent. Par exemple, supposons une machine "petite boutienne" qui somme les données qui sont mémorisées dans l'ordre du réseau ("gros boutien"). Aller chercher chaque mot de 16 bits va échanger les octets, d'où résultera la somme [4] ; cependant, mémoriser le résultat ramènera la somme à nouveau dans l'ordre des octets du réseau.

 

L'échange des octets peut aussi être utilisé explicitement pour traiter les problèmes d'alignement de frontière. Par exemple, le second groupe dans [3] peut être calculé sans se préoccuper de son origine paire/impaire, comme :

 

[K,L] +' ... +' [Z,0]

 

si les octets de la somme sont échangés avant qu'elle soit ajoutée au premier groupe. Voir l'exemple ci-dessous.

 

(C)   Sommation parallèle

Sur les machines qui ont des tailles de mot qui sont des multiples de 16 bits, il est possible de développer des mises en œuvre encore plus efficaces. Parce que l'addition est associative, nous n'avons pas à additionner les entiers dans l'ordre où ils apparaissent dans le message. On peut les ajouter en "parallèle" en exploitant la plus grande taille du mot.

 

Pour calculer une somme de contrôle en parallèle, on additionne simplement un complément à 1 du message en utilisant la taille de mot d'origine de la machine. Par exemple, sur une machine à 32 bits, on peut ajouter 4 octets à la fois : [A,B,C,D]+'... Lorsque la somme a été calculée, on "replie" la longue somme en 16 bits en ajoutant les segments de 16 bits. Chaque addition de 16 bits peut produire de nouveaux reports circulaires qui doivent être ajoutés.

 

De plus, cette fois encore, l'ordre des octets n'a pas d'importance ; on pourrait à la place sommer des mots de 32 bits : [D,C,B,A]+'... ou [B,A,D,C]+'... et ensuite échanger les octets de la somme finale de 16 bits comme nécessaire. Voir les exemples ci-dessous. Toute permutation est permise qui collecte tous les octets de données pairs en un octet de somme et les octet de données impairs dans l'autre octet de somme.

 

Il y a d'autres techniques de codage qui peuvent être exploitées pour accélérer le calcul de la somme de contrôle.

 

(1)   Reports différés

Selon la machine, il peut être plus efficace de différer l'ajout des reports circulaires jusqu'à ce que la boucle principale de sommation soit finie.

 

Une approche est de sommer les mots de 16 bits dans un accumulateur de 32 bits, de façon que le débordement se construise dans les 16 bits de plus fort poids. Cette approche évite normalement une instruction de détection de report mais exige deux fois plus d'additions que l'ajout des segments de 32 bits ; ce qui est plus rapide dépend de l'architecture précise du matériel.

 

(2)   Boucles déroulantes

Pour réduire la redondance de boucle, il est souvent utile de "dérouler" la boucle interne de sommation, en répliquant une série de commandes d'addition au sein d'une seule traversée de boucle. Cette technique donne souvent des économies significatives, bien qu'elle puisse considérablement compliquer la logique du programme.

 

(3)   Combiner avec la copie des données

Comme la somme de contrôle, la copie des données d'une localisation de mémoire à une autre implique une redondance pour chaque octet. Dans les deux cas, le goulot d'étranglement est essentiellement le bus de mémoire, c'est-à-dire à quelle vitesse on peut aller chercher les données. Sur certaines machines (en particulier celles qui sont relativement lentes et des micro-ordinateurs simples), la redondance peut être réduite de façon significative en combinant la copie de mémoire à mémoire à la somme de contrôle, en allant chercher les données une seule fois au lieu de deux.

 

(4)   Mise à jour incrémentaire

Finalement, on peut parfois éviter de recalculer la somme de contrôle entière lorsque un champ d'en-tête est mis à jour. Le meilleur exemple connu est un routeur qui change le champ TTL dans l'en-tête IP, mais il y a d'autres exemples (par exemple, lors de la mise à jour d'une route de source). Dans ces cas, il est possible de mettre à jour la somme de contrôle sans examiner le message ou datagramme.

 

Pour mettre à jour la somme de contrôle, ajouter simplement les différences des entiers de seize bits qui ont été changés. Pour voir pourquoi cela fonctionne, observer que chaque entier de 16 bits a un inverse additif et que l'addition est associative. De cela il s'ensuit qu'étant données la valeur d'origine m, la nouvelle valeur m' et l'ancienne somme de contrôle C, la nouvelle somme de contrôle C' est :

 

C' = C + (-m) + m' = C + (m' - m)

(Sur cette équation, voir les RFC 1141 et 1624 qui la précisent.)

3.   Exemple numériques

 

Nous présentons maintenant des exemples explicites du calcul d'une simple somme de compléments à 1 sur une machine à compléments à 2. Les exemples montrent la même somme calculée octet par octet, par mots de 16 bits en ordre normal et en changement d'ordre, et de 32 bits à la fois en trois ordres différents. Tous les nombres sont en hexadécimal.

 

 

Octet par octet

Ordre "normal"

Ordre changé

Octet 0/1 :

00 01

0001

0100

Octet 2/3 :

f2 03

f203

03f2

Octet 4/5 :

f4 f5

f4f5

f5f4

Octet 6/7 :

f6 f7

f6f7

f7f6

Somme1 :

2dc 1f0

2ddf0

1f2dc

 

dc f0

ddf0

f2dc

Reports :

1 2

2

1

Somme2 :

dd f2

ddf2

f2dd

Échange final :

dd f2

ddf2

ddf2

 

Octet 0/1/2/3 :

0001f203

010003f2

03f20100

Octet 4/5/6/7 :

f4f5f6f7

f5f4f7f6

f7f6f5f4

Somme1 :

0f4f7e8fa

0f6f4fbe8

0fbe8f6f4

 

Reports :

0

0

0

 

 

 

 

Moitié supérieure

f4f7

f6f4

fbe8

Moitié inférieure

fbe8

f6f4

 

Somme2 :

1ddf1

1f2dc

1f2dc

 

ddf1

f2dc

f2dc

Reports :

1

1

1

Somme3 :

ddf2

f2dd

f2dd

Échange final :

ddf2

ddf2

ddf2

 

 

 

Finalement, voici un exemple de séparation de la somme en deux groupes, le second groupe commençant sur une frontière impaire :

 

 

Octet par octet

Ordre normal

Octet 0/1 :

00 01

0001

Octet 2/ :

f2 (00)

f200

Somme1 :

f2 01

f201

Octet 4/5 :

03 f4

03f4

Octet 6/7 :

f5 f6

f5f6

Octet 8/ :

f7 (00)

f700

Somme2 :

 

1f0ea

Somme2 :

 

f0ea

Report :

 

1

Somme3 :

 

f0eb

Somme1 :

 

f201

Somme3 octet changé :

 

ebf0

Somme4 :

 

1ddf1

Somme4 :

 

ddf1

Report :

 

1

Somme5 :

 

ddf2

 

4.   Exemples de mise en œuvre

 

Dans cette section, nous donnons des exemples d'algorithmes de mise en œuvre de somme de contrôle Internet qui se sont trouvés efficaces sur divers CPU. Dans chaque cas, nous montrons le cœur de l'algorithme, sans inclure de code environnemental (par exemple, des liaisons de sous-programmes) ou de code de cas particuliers.

 

4.1   "C"

 

L'algorithme de code "C" suivant calcule la somme de contrôle avec une boucle interne qui additionne 16 bits à la fois dans un accumulateur de 32 bits.

 

in 6

{

/* Calcule la somme de contrôle Internet pour les octets "count" commençant à la localisation "addr".

*/

register long sum = 0;

while( count > 1 ) {

/* C'est la boucle interne */

sum += * (unsigned short) addr++;

count -= 2;

}

/* Ajoute l'octet en plus, s'il en est */

if( count > 0 )

sum += * (unsigned char *) addr;

/* Replie la somme en 32 bits sur 16 bits */

while (sum>>16)

sum = (sum & 0xffff) + (sum >> 16);

checksum = ~sum;

}

 

4.2   Motorola 68020

 

L'algorithme suivant est donné en langage assembleur pour un processeur Motorola 68020. Cet algorithme effectue la somme des 32 bits à la fois, et déroule la boucle avec 16 réplications. Pour la clarté de l'exposé, nous avons omis la logique pour ajouter le dernier mot plein lorsque la longueur n'est pas un multiple de 4. Le résultat est laissé dans le registre d0.

 

Avec une horloge à 20 MHz, cette routine a été mesurée à 134 µs/kB pour sommer les données aléatoires. Cet algorithme a été développé par Van Jacobson.

 

movl d1,d2

lsrl #6,d1   | compte/64 = n° de traversées de boucle

andl #0x3c,d2   | Puis trouver les fractions d'un tronçon

negl d2

andb #0xf,cc   | Éliminer X (fanion de report étendu)

 

jmp pc@(2$-.-2:b,d2)   | Saute dans la boucle

 

1$:   | Commence la boucle interne..

 

movl a0@+,d2   | Va chercher un mot de 32 bits

addxl d2,d0   | Ajoute le mot + le report précédent

movl a0@+,d2   | Va chercher un mot de 32 bits

addxl d2,d0   | Ajoute le mot + le report précédent

 

   | ... encore 14 réplications

2$:

dbra d1,1$   | (NB- dbra n'affecte pas X)

 

movl d0,d1   | Replie la somme de 32 bits en 16 bits

swap d1   | (NB – l'échange n'affecte pas X)

addxw d1,d0

jcc 3$

addw #1,d0

3$:

andl #0xffff,d0

 

4.3   Cray

 

L'exemple suivant, en langage assembleur pour un CPU Cray, a été apporté par Charley Kline. Il met en œuvre le calcul de somme de contrôle comme une opération vectorielle, additionnant jusqu'à 512 octets à la fois avec une unité de sommation de base de 32 bits. Cet exemple omet de nombreux détails en rapport avec les blocs courts, par souci de clarté.

 

Le registre A1 contient l'adresse d'un bloc de mémoire de 512 octets sur lequel effectuer la somme de contrôle. On charge d'abord deux copies des données dans deux registres vectoriels. L' un a un décalage vectoriel à droite de 32 bits, alors que l'autre subit l'addition vectorielle ET avec un gabarit de 32 bits. Les deux vecteurs sont ensuite additionnés. Comme toutes ces opérations s'enchaînent, cela produit un résultat par cycle d'horloge. Il réduit ensuite le vecteur résultant en une boucle qui ajoute chaque élément à un registre scalaire. Finalement, le report circulaire est effectué et le résultat est replié sur 16 bits.

EBM

A0   A1

VL   64   utilise les vecteurs pleins

S1   <32   forme un gabarit de 32 bits à partir de la droite.

A2   32

V1   ,A0,1   charge le paquet dans V1

V2   S1&V1   Forme des groupes de 32 bits à droite dans V2.

V3   V1>A2   Forme des groupes de 32 bits à gauche dans V3.

V1   V2+V3   Ajoute les deux ensemble.

A2   63   Prépare la réduction en un scalaire.

S1   0

S4   <16   Forme un gabarit de 16 bits à partir de la droite.

A4   16

CK$LOOP   S2   V1,A2

A2   A2-1

A0   A2

S1   S1+S2

JAN   CK$LOOP

S2   S1&S4   Forme un groupe de 16 bits à droite dans S2

S1   S1>A4   Forme un groupe de 16 bits à gauche dans S1

S1   S1+S2

S2   S1&S4   Forme un groupe de 16 bits à droite dans S2

S1   S1>A4   Forme un groupe de 16 bits à gauche dans S1

S1   S1+S2

S1   #S1   Prend le complément à un

CMR   À ce moment, S1 contient la somme de contrôle.

 

4.4   IBM 370

 

L'exemple suivant, en langage assembleur pour un CPU IBM 370, additionne quatre multiplets de données à la fois. Pour être plus clairs, nous avons omis la logique d'addition de dernier mot entier lorsque la longueur n'est pas un multiple de 4, et d'inverser les multiplets lorsque nécessaire. Le résultat est laissé dans le registre RCARRY.

Ce code a été chronométré sur un CPU IBM 3090 à 27 µs/kOctet en additionnant des bits tous à un. Ce temps est réduit à 24,3 µs/kOctet si on prend la peine d'aligner les cumulateurs sur les mots (ce qui exige des cases spéciales à la fois au début et à la fin, et un échange d'octets quand nécessaire pour compenser les débuts sur un octet impair).

 

* Les registres RADDR et RCOUNT contiennent l'adresse et la longueur du bloc à sommer-vérifier.

* (RCARRY, RSUM) doit être une paire de registres pair/impair.

* (RCOUNT, RMOD) doit être une paire de registres pair/impair.

*

CHECKSUM SR RSUM,RSUM   Libère les registres de travail.

SR RCARRY,RCARRY

LA RONE,1   Établit la constante 1.

*

SRDA RCOUNT,6   Count/64 to RCOUNT.

AR RCOUNT,RONE   +1 = nombre de fois dans la boucle.

SRL RMOD,26   Taille de tronçon partiel à RMOD.

AR RADDR,R3   Ajuste l'addr pour compense le saut dans la boucle.

S RADDR,=F(64)  

SRL RMOD,1   (RMOD/4)*2 est l'index de demi mot.

LH RMOD,DOPEVEC9(RMOD)   Utilise le vecteur magique dope pour le décalage,

B LOOP(RMOD)   et saute dans la boucle...

*

*   Boucle interne :

*

LOOP AL RSUM,0(,RADDR)   Ajoute des mots pleins logiques.

BC 12,*+6   Branche si il n'y a pas de report.

AR RCARRY,RONE   Ajoute un de report circulaire.

AL RSUM,4(,RADDR)   Ajoute un mot plein logique.

BC 12,*+6   Branche si il n'y a pas de report

AR RCARRY,RONE   Ajoute 1 de report circulaire

*

*   ... 14 duplications à venir...

*

   A   RADDR,=F'64'   Incrémente l'adresse ptr

   BCT   RCOUNT,LOOP   Branche sur el compte

*

*   Ajoute les reports dans la somme, et replie sur 16 bits

*

   ALR   RCARRY,RSUM   Ajoute les mots SUM et CARRY

   BC   12,*+6   et prend soin des reports

   AR   RCARRY,RONE

   SRDL   RCARRY,16   Replie la somme de 32 bits en 16-bits

   SRL   RSUM,16  

   ALR   RCARRY,RSUM

   C   RCARRY,=X'0000FFFF'   et fait attention au tout dernier report

   ²BNH   DONE

   S   RCARRY,=X'0000FFFF'

DONE   X   RCARRY,=X'0000FFFF'   complément à un

 

IEN 45

Section 2.4.4.5

Conception de la fonction somme de contrôle de TCP

William W. Plummer

Bolt Beranek and Newman, Inc.

50 Moulton Street

Cambridge MA 02138

5 juin 1978

 

1.   Introduction

 

Les sommes de contrôle sont incluses dans les paquets afin de pouvoir détecter les erreurs rencontrées durant la transmission. Pour les protocoles de l'Internet comme TCP [1,9] ceci est particulièrement important parce que les paquets peuvent avoir traversé des réseaux sans fil comme le réseau radio par paquets [2] et le réseau satellites Atlantic [3] où les paquets peuvent être corrompus. Les protocoles de l'Internet (par exemple, ceux pour la transmission de la parole en temps réel) peuvent tolérer un certain niveau d'erreurs de transmission et les techniques de correction d'erreur directe ou éventuellement pas de somme de contrôle du tout peut être mieux. Cet article se concentre sur la fonction somme de contrôles pour des protocoles comme TCP où la fiabilité de livraison requise est réalisée par la retransmission.

 

Même si la somme de contrôle paraît bonne sur un message reçu, le message peut quand même contenir une erreur non détectée. La probabilité de cet événement est bordée par 2**(-C) où C est le nombre de bits de somme de contrôle. Les erreurs peuvent provenir de dysfonctionnements du matériel (et du logiciel) aussi bien que d'erreurs de transmission. Les erreurs découlant du matériel se manifestent normalement de certaines façons bien connues et il est souhaitable d'en tenir compte dans la conception de la fonction somme de contrôle. Idéalement, aucune erreur du type "défaillance courante de matériel" ne devrait rester indétectée.

 

Un exemple de défaillance que la fonction somme de contrôle actuelle traite avec succès est de prélever un bit dans l'interface réseau (ou le bus I/O, le canal mémoire, etc.). Cela va toujours rendre mauvaise la somme de contrôle. À titre d'exemple de l'inadéquation de la fonction actuelle, supposons qu'un signal de contrôle cesse de fonctionner dans l'interface réseau et que l'interface mémorise des zéros à la place des données réelles. Ces messages "tout à zéro" paraissent avoir des sommes de contrôle valides. Des parasites sur la ligne "There's Your Bit" de l'interface ARPANET [4] peuvent rester indétectés parce que les entrées de bits supplémentaires causent une perturbation de la somme de contrôle (c'est-à-dire, décalée) de la même façon que les données.

 

Bien que les messages qui contiennent des erreurs non détectées soient à l'occasion passés à des couches de protocole plus élevées, il est vraisemblable qu'elles n'auront pas de sens à ce niveau. Dans le cas de TCP, la plupart de ces messages seront ignorés, mais certains pourraient causer l'interruption d'une connexion. Des données mutilées pourraient être vues comme un problème pour une couche de protocole supérieure à TCP qui peut elle-même avoir un schéma de somme de contrôle.

 

Cet article est la première étape de la conception d'une nouvelle fonction somme de contrôle pour TCP et quelques autres protocoles de l'Internet. Plusieurs propriétés utiles de la fonction actuelle ont été identifiées. Elles devraient si possible être conservées dans toute nouvelle fonction. Un certain nombre de schémas de somme de contrôle plausibles sont examinés. Parmi eux, seul le "code de produit" semble assez simple pour être pris en considération.

 

2.   La fonction Somme de contrôle actuelle de TCP

 

La fonction actuelle est orientée vers les machines à seize bits telles que le PDP-11 mais elle peut être calculée facilement sur d'autres machines (par exemple, PDP-10). Un paquet est vu comme une chaîne de multiplets de 16 bits et la fonction somme de contrôle est la somme des compléments à un (additionnés avec report circulaire) de ces multiplets. C'est le complément à un de cette somme qui est mémorisé dans le champ somme de contrôle de l'en-tête TCP. Avant de calculer la valeur de la somme de contrôle, l'envoyeur place un zéro dans le champ somme de contrôle du paquet. Si la valeur de la somme de contrôle calculée par un receveur du paquet est zéro, le paquet est supposé être valide. Ceci est une conséquence du nombre "négatif" dans le champ somme de contrôle qui annule exactement la contribution du reste du paquet.

 

Ignorant la difficulté d'évaluer réellement la fonction somme de contrôle pour un paquet donné, la façon d'utiliser la somme de contrôle décrite ci-dessus est assez simple, mais elle suppose certaines propriétés de l'opérateur somme de contrôle (l'addition de complément à un, "+" dans ce qui suit) :

 

(P1)   + est commutatif. Et donc, l'ordre dans lequel les multiplets de 16 bits sont "additionnés" est sans importance.

 

(P2)   + a au moins un élément d'identité (la fonction actuelle en a deux : +0 et -0). Cela permet à l'envoyeur de calculer la fonction somme de contrôle en plaçant un zéro dans le champ somme de contrôle du paquet avant de calculer la valeur.

 

(P3)   + a un inverse. Et donc, le receveur peut évaluée la fonction somme de contrôle et attendre un zéro.

 

(P4)   + est associatif, permettant au champ somme de contrôle d'être n'importe où dans le paquet et aux multiplets de 16 bits d'être examinés séquentiellement.

 

Mathématiquement, ces propriétés de l'opération binaire "+" sur l'ensemble des nombres de16 bits forment un groupe Abélien [5]. Bien sûr, il y a beaucoup de groupes Abéliens mais tous ne seraient pas satisfaisants à utiliser comme opérateur de somme de contrôle. (Un autre opérateur directement disponible dans l'ensemble des instructions du PDP-11 qui dispose de toutes ces propriétés est le OU exclusif, mais le OUX n'est pas satisfaisant pour d'autres raisons.)

 

Bien qu'imprécis, une autre propriété qui doit être préservée dans tout futur schéma de somme de contrôle est :

 

(P5)   + est rapide à calculer sur diverses machines avec des exigences de mémorisation limitées.

 

La fonction actuelle est assez bonne à cet égard. Sur le PDP-11, la boucle interne ressemble à :

 

LOOP:   ADD (R1)+,R0   ; Ajoute le prochain multiplet de 16 bits

   ADC R0   ; Fait le report circulaire

   SOB R2,LOOP   ; Fait le bouclage sur l'ensemble du paquet

 

( 4 cycles de mémoire par multiplet de 16 bits)

 

Sur le PDP-10, les propriétés du P1-4 sont exploitées plus avant et deux multiplets de 16 bits sont traités par boucle :

 

LOOP:   ILDB THIS,PTR   ; Obtient 2 multiplets de 16 bits

   ADD SUM,THIS   ; Additionne la somme actuelle

   JUMPGE SUM,CHKSU2   ; Saute si moins de 8 de report

   LDB THIS,[POINT 20,SUM,19]   ; Reste 16 et reporte

   ANDI SUM,177777   ; Garde juste les 16 de faible poids

   ADD SUM,THIS   ; Replie les reports

   CHKSU2: SOJG COUNT,LOOP   ; Fait le bouclage sur l'ensemble du paquet

 

( 3,1 cycles de mémoire par multiplet de 16 bits )

 

L'instruction "en plus" dans les boucles ci-dessus est nécessaire pour convertir les instructions ADD de complément à deux en add de complément à un en rendant les reports circulaires. L'arithmétique de complément à un est meilleure que celle des compléments deux parce qu'elle est également sensible aux erreurs dans toutes les positions binaires. Si on utilisait l'addition de compléments à deux, un nombre pair de uns pourrait être ôté (ou ajouté) le canal des bits de plus forts poids sans affecter la valeur de la somme de contrôle. C'est justement cette propriété qui rend cette sorte d'addition préférable à un simple OU exclusif qui est fréquemment utilisé mais permet un nombre pair d'abandons (d'ajouts) dans tout canal binaire. Le format RIM10B de bande de papier utilisé sur les PDP-10 [10] utilise l'addition de complément à deux à cause de l'espace extrêmement limité du programme de chargement.

 

Une autre propriété du schéma actuel de somme de contrôle est :

 

(P6)   L'ajout de la somme de contrôle à un paquet ne change pas les multiplets d'information. Peterson [6] appelle cela un code "systématique".

 

Cette propriété permet à des ordinateurs intermédiaires comme des routeurs d'agir sur les champs (c'est-à-dire, l'adresse de destination Internet) sans avoir d'abord à décoder le paquet. Le contrôle de redondance cyclique utilisé pour détecter les erreurs n'est pas non plus systématique. Cependant, la plupart des applications de CRC tendent à privilégier la détection d'erreur plutôt que la correction et par conséquent, elles envoient le message inchangé, avec les bits de vérification du CRC ajoutés à la fin. Le CRC de 24 bits utilisé par les IMP d'ARPANET et les interfaces Very Distant Host [4] ainsi que les normes ANSI pour les bandes magnétiques à 800 et 6250 bits par pouce (décrites en [11]) utilisent ce mode.

 

Noter que le fonctionnement des protocoles de niveau supérieur n'est pas (par conception) affecté par quoi que ce soit qui pourrait être fait par un routeur qui agirait sur des paquets éventuellement invalides. Il est permis aux routeurs de valider la somme de contrôle sur les paquets entrants, mais en général les routeurs ne vont pas savoir comment faire si la somme de contrôle est un dispositif spécifique du protocole.

 

Une dernière propriété du schéma de somme de contrôle actuel qui est en réalité une conséquence de P1 et P4 est :

 

(P7)   La somme de contrôle peut être modifiée par incréments

 

Cette propriété permet à un routeur intermédiaire d'ajouter des informations à un paquet, par exemple un horodatage, et d'"ajouter" un changement approprié au champ somme de contrôle du paquet. Noter que la somme de contrôle va toujours être de bout en bout car elle n'est pas entièrement recalculée.

 

3.   Codes de produit

 

Certains "codes de produit" peuvent être utiles pour les besoins du calcul de somme de contrôles. Ci-après figure une brève description des codes de produit dans le contexte de TCP. Un traitement plus général se trouve dans Avizienis [7] et probablement dans d'autres travaux plus récents.

 

Le concept de base de ce codage est que le message (paquet) à envoyer est formé par la transformation du message source original et l'ajout de quelques bits de "vérification". En les lisant et en y appliquant une transformation (éventuellement différente), un receveur peut reconstruire le message d'origine et déterminer si il a été altéré durant la transmission.

 

Mo Ms Mr

----- ----- -----

| A | code | 7 | décode | A |

| B | ==> | 1 | ==> | B |

| C | | 4 | | C |

----- |...| -----

| 2 | info plus fanion "valide"

----- vérif

Original Envoyé Reconstruit

 

Avec les codes de produit, la transformation est Ms = K * Mo. C'est-à-dire que le message envoyé est simplement le produit du message d'origine Mo et de quelque constante K bien connue. Pour décoder, le message reçu Ms est divisé par K ce qui donnera Mr comme quotient et 0 comme reste si Mr est à considérer comme le même que Mo.

 

Le premier problème est de choisir une "bonne" valeur pour K, le "facteur de preuve". K doit être premier par rapport à la base choisie pour exprimer le message. (Exemple : les messages binaires avec un K incorrect de 8. Cela signifie que Ms va ressembler exactement à Mo excepté que trois zéros ont été ajoutés. La seule façon pour que le message semble mauvais à un receveur qui divise par 8 est que l'erreur survienne dans un de ces trois bits.)

 

Pour TCP la base R sera choisie à 2**16. C'est-à-dire, tous les multiplets de 16 bits (taille de mot du PDP-11) seront considérés comme un chiffre d'un grand nombre et ce nombre est le message. Et donc,

 

Mo    = SIGMA [ Bi * (R**i)] ,   Bi est le i ème multiplet, i = 0 à N

Ms    = K * Mo

 

Altérer un seul chiffre de Ms donnera Ms' = Ms +ou- C*(R**j) pour une position de base j. Le receveur calculera
Ms'/K = Mo +ou- C(R**j)/K. Comme R et K sont premiers entre eux, C*(R**j) ne peut être un multiple exact de K. Donc, la division aura un reste différent de zéro qui indique que Ms' est une version altérée de Ms. Comme on le voit, un bon choix pour K est (R**b - 1), pour b qui est la "longueur de preuve" qui contrôle de degré de détection à avoir pour les erreurs de salve qui affectent une chaîne de chiffres (c'est-à-dire, des multiplets de 16 bits) dans le message. En fait b sera choisi à 1, de sorte que K sera 2**16 - 1 afin que les opérations arithmétiques soient simples. Cela signifie que toute salve de 15 bits ou moins sera détectée. Conformément à [7], ce choix de b résulte en l'expression suivante pour la fraction des erreurs indétectée de poids 2 :

 

f = 16(k-1)/[32(16k-3) + (6/k)]   où k est la longueur du message.

 

Pour les grands messages, f se rapproche de 3,125 pour cent quand k tend vers l'infini.

 

Les multiplications et divisions multiples précises sont normalement des opérations assez complexes, en particulier sur les petites machines à qui font normalement défaut même ces opérations de multiplication et divisions précise uniques. L'exception est justement le cas dont nous parlons ici -- le facteur est 2**16 - 1 sur les machines avec une longueur de mot de 16 bits. La raison est l'identité suivante :

 

Q*(R**j) = Q, mod (R-1) 0 <= Q < R

 

C'est à dire que tout chiffre Q dans la base choisie (0, 1, ... R-1) multipliée par toute puissance de la base aura un reste de Q lorsque divisée par la base moins 1.

 

Exemple : En décimal R = 10. Prenons Q = 6.

 

6    = 0 * 9 + 6 = 6, mod 9

60    = 6 * 9 + 6 = 6, mod 9

600    = 66 * 9 + 6 = 6, mod 9, etc.

 

De plus, le reste de (31415/9) = rem((30000+1000+400+10+5)/9)

   = (3 mod 9) + (1 mod 9) + (4 mod 9) + (1 mod 9) + (5 mod 9)

   = (3+1+4+1+5) mod 9

   = 14 mod 9

   = 5

 

Ainsi, le reste d'un nombre divisé par la base moins un se trouve en additionnant simplement les chiffres du nombre. Comme dans le cas de TCP, on peut choisir la base comme étant 2**16 et le facteur de preuve comme 2**16 - 1, on peut rapidement vérifier un message en additionnant tous les mots de 16 bits (sur un PDP-11) avec un report circulaire. Si le résultat est zéro, le message peut être considéré comme valide. Et donc, vérifier un message à code de produit est exactement de la même complexité qu'avec la somme de contrôle TCP actuelle !

 

Afin de former Ms, l'envoyeur doit multiplier le "nombre" Mo de précision multiple par 2**16 - 1. Ou,
Ms = (2**16)Mo - Mo. Ceci est effectué en permutant Mo d'une précision pour une valeur d'un mot complet et en soustrayant Mo. Comme les reports doivent se propager entre les chiffres, mais que c'est seulement le chiffre en cours qui nous intéresse, c'est l'arithmétique de complément à un qui est utilisée.

 

(2**16)Mo    = Mo0 + Mo1 + Mo2 + ... + MoX + 0

- Mo    = - ( Mo0 + Mo1 + ......... + MoX)

---------   ----------------------------------

Ms    = Ms0 + Ms1 + ... - MoX

 

Une boucle qui met en œuvre cette fonction sur PDP-11 pourrait ressembler à :

LOOP: MOV -2(R2),R0   ; Prochain multiplet de (2**16)Mo

SBC R0    ; Propage les reports du dernier SUB

SUB (R2)+,R0   ; Soustrait un multiplet de Mo

MOV R0,(R3)+   ; Mémorise dans Ms

SOB R1,LOOP   ; Boucle sur le message entier, 8 cycles de mémoire par multiplet de 16 bits

 

Noter que la procédure de codage n'est pas faite sur place car elle n'est pas systématique. En général, la copie originale, Mo, devra être conservée par l'envoyeur pour les besoins de la retransmission, et elle devra donc rester lisible. Et donc, le MOV R0,(R3)+ qui prend deux des huit cycles de mémoire par boucle est nécessaire.

 

La procédure de codage va ajouter exactement un mot de 16 bits au message car Ms < (2**16)Mo. Ces 16 bits additionnels devront être en queue de message, mais peuvent être déplacés à la localisation définie de l'en-tête TCP immédiatement avant la transmission. Le receveur devra défaire cela pour remettre Ms dans le format standard avant de décoder le message.

 

Le code pour que le receveur décode pleinement le message peut être déduit en observant que tout mot dans Ms contient la différence entre deux mots successifs de Mo moins les reports provenant du mot précédent, et que le mot de moindre poids contient en moins le mot de moindre poids de Mo. Ainsi le mot de moindre poids (c'est-à-dire le plus à droite) de Mr est juste le négatif du multiplet de moindre poids de Ms. Le prochain mot de Mr est le prochain mot de Ms plus le mot juste calculé de Mr plus le report du calcul précédent.

 

Un léger raffinement de la procédure est nécessaire afin de se protéger contre un message tout à zéro envoyé à la destination. Il apparaîtrait comme ayant une somme de contrôle valide parce que Ms'/K = 0/K = 0 avec reste 0. Le raffinement est de rendre le codage par Ms = K*Mo + C où C est une constante arbitraire bien connue. L'ajout de cette constant exige un second passage sur le message, mais ce sera normalement très court car on peut l'arrêter aussitôt que les reports cessent de se propager. Choisir C = 1 est suffisant dans la plupart des cas.

 

La somme de contrôle à code de produit doit être évaluée en termes des propriétés P1 à P7 désirées. On a montré qu'un facteur de deux cycles machine supplémentaires sont consommés par le calcul ou la vérification d'une somme de contrôle à code de produit (P5 satisfaite ?).

 

Bien que le code ne soit pas systématique, la somme de contrôle peut être vérifiée rapidement sans décoder le message. Si l'adresse de destination Internet est située à l'extrémité de moindre poids du paquet (où commence le calcul du code de produit) il est alors possible à un routeur de ne décoder qu'assez du message pour voir ce champ sans avoir à décoder la totalité du message. Et donc, P6 est au moins partiellement satisfaite. Les propriétés algébriques de P1 à P4 ne sont pas satisfaites, mais il suffit de quelques calculs pour le prendre en compte -- le message doit être reformaté comme mentionné précédemment.

 

P7 est satisfaite car la somme de contrôle de code de produit peut être mise à jour par incréments pour tenir compte du travail ajouté, bien que cela implique un peu de procédure. Imaginons que le message original a deux moitiés, H1 et H2. Et donc, Mo = H1*(R**j) + H2.

Le mot d'horodatage doit être inséré entre ces deux moitiés pour former un Mo' = H1*(R**(j+1)) + T*(R**j) + H2 modifié. Comme K a été choisi comme étant R-1, Le message transmis Ms' = Mo'(R-1). Donc,

 

Ms'    = Ms*R + T(R-1)(R**j) + P2((R-1)**2)

   = Ms*R + T*(R**(j+1)) + T*(R**j) + P2*(R**2) - 2*P2*R - P2

 

On se souvient que R est 2**16, la taille de mot sur le PDP-11. Multiplier par R signifie recopier un mot en mémoire. Donc, le premier terme de Ms' est simplement le message copié moins un mot. Le prochain terme est les nouvelles données T ajoutées dans le Ms' en cours de formation qui commence au (j+1) è mot. L'addition est ici très facile car après l'ajout dans T tout de qui reste est de propager le report, et cela peut s'arrêter aussitôt qu'il n'y a plus de report produit. Lest autres termes sont traités de même façon.

 

4.   Codes plus compliqués

 

Il existe des quantités de théories sur la détection d'erreur et les codes de correction. Peterson [6] est une excellente référence. La plupart de ces schémas de "CRC" sont conçus pour être mis en œuvre en utilisant un registre à décalage avec un réseau de rétroactions composé de OU exclusifs. La simulation d'un tel circuit logique par un programme serait trop lente pour être utile sauf à découvrir quelque astuce de programmation.

 

Une telle astuce a été proposée par Kirstein [8]. En bref, quelques bits (quatre ou huit) de l'état actuel du registre à décalage sont combinés avec les bits du flux entrant (provenant de Mo) et le résultat est utilisé comme l'index d'un tableau qui donne le nouvel état du registre à décalage et, si le code n'est pas systématique, les bits pour le flux de sortie (Ms). Un essai de codage d'une fonction de CTC particulièrement "bonne" en utilisant des multiplets de quatre bits a montré que cette technique est quatre fois plus lente que la fonction somme de contrôle actuelle. Ceci était vrai pour les machines PDP-10 et PDP-11. Des propriétés souhaitées énumérées ci-dessus, les schémas de CRC ne satisfont que P3 (Il a un inverse.), et P6 (Il est systématique.). Le placement du champ somme de contrôle dans le paquet est critique et le CRC ne peut pas être modifié par incréments.

 

Bien que le gros des théorie de codage traite de codes binaires, la plus grande partie de la théorie fonctionne si l'alphabet contient q symboles, où q est une puissance d'un nombre premier. Par exemple q pris comme 2**16 devrait grande une grande partie de la théorie utile sur une base mot à mot.

 

5.   Traitement extérieur

 

Lorsqu'une fonction comme le calcul d'une somme de contrôle exige un traitement extensif, une solution est de mettre ce traitement sur un processeur externe. De cette façon le "coder le message" et "décoder le message" deviennent des instructions qui ne chargent pas le processeur de l'hôte principal. L'ordinateur VAX/780 de Digital Equipment Corporation est équipé de matériels spéciaux pour générer et vérifier les CRC [13]. En général ce n'est pas une très bonne solution car un tel processeur doit être construit pour chaque machine d'hôte différente qui utilise des messages TCP.

 

On peut concevoir que les fonctions de routeur pour un grand hôte puissent être effectuées entièrement dans une "machine frontale Internet". Cette machine serait chargée de transmettre les paquets reçus du ou des réseaux ou des modules de protocole Internet dans l'hôte raccordé, et de réassembler les fragments Internet en segments puis de les passer à l'hôte. Une autre capacité de cette machine serait de vérifier la somme de contrôle de sorte que les segments donnés à l'hôte soient réputés valides au moment où ils quittent le frontal. Comme les cycles d'ordinateurs sont supposés être à la fois peu coûteux et disponible sur le frontal, cela semble raisonnable.

 

Le problème de la validation des sommes de contrôle sur le frontal est que cela détruit le caractère de bout en bout de la somme de contrôle. S'il en est, c'est la caractéristique la plus puissante de la somme de contrôle TCP ! IL y a un moyen pour faire couvrir la liaison hôte – frontal par la somme de contrôle de bout en bout. Un petit protocole distinct doit être développé pour couvrir cette liaison. Après avoir validé un paquet entrant en provenance su réseau, le frontal le passerait à l'hôte en disant "voici un segment Internet pour vous. Appelons le n° 123". L'hôte mémoriserait ce segment, et en renverrait une copie au frontal en disant, "Voila ce que tu m'a envoyé comme n° 123. Est-ce d'accord ?" Le frontal ferait alors une comparaison mot à mot avec la première transmission, et dirait alors à l'hôte soit "Revoilà n° 123", soit "Vous avez reçu n° 123 correctement. Livrez le au module approprié pour traitement ultérieur."

 

Les en-têtes des messages traversant la liaison hôte – frontal seraient très vraisemblablement couverts par une somme de contrôle bien forte de sorte que les informations comme quelle fonction est en cours de traitement et les numéros de référence de message soient fiables. Ces en-têtes seraient assez courts, peut-être seulement seize bits, de façon que la somme de contrôle pourrait être assez forte. Le gros du message ne serait pas inclus dans la somme, bien sûr. La raison pour laquelle ce schéma réduit la charge de calcul de l'hôte est que tout ce qui est exigé pour valider le message utilisant la somme de contrôle de bout en bout est de le renvoyer à la machine frontale. Dans le cas du PDP-10, cela n'exige que 0,5 cycles de mémoire par multiplet de 16 bits du message Internet, et seulement quelques cycles de processeur pour établir les transferts nécessaires.

 

6.   Conclusions

 

Il y a un ordre dans les fonctions de somme de contrôle : la première et la plus simple, ou rien du tout, est celle qui ne fournit ni détection ni correction d'erreur. En second est l'envoi d'une constante qui est vérifiée par le receveur. Cela aussi est extrêmement faible. Troisièmement, l'opération OU exclusif des données peut être envoyée. OUX prend la quantité minimale du temps de l'ordinateur pour générer et vérifier, mais ce n'est pas une bonne somme de contrôle. Une somme des compléments à deux des données est quelque peu meilleure et ne prend plus de temps à calculer. En cinquième vient la somme des compléments à un qui est actuellement utilisée par TCP. C'est un peu plus coûteux en termes de temps d'ordinateur. L'étape suivante est un code de produit. Le code de produit est fortement relaté à la somme des compléments à un, il consomme plus de temps d'ordinateur, fournit un peu plus de protection contre les défaillances courantes de matériel, mais a quelques propriétés discutables. Ensuite vient un authentique code de CRC polynomial, utilisé uniquement à des fins de vérification. C'est très coûteux à mettre en œuvre pour un programme. Finalement, on peut utiliser un schéma de CRC de pleine correction et détection des erreurs.

 

Pour les applications TCP et Internet, le schéma de code de produit est viable. Il souffre principalement de ce que les messages doivent être décodés (au moins partiellement) par des routeurs intermédiaires afin de pouvoir être transmis. Si le codes de produit ne devaient pas être choisis pour améliorer la somme de contrôle, quelques légères modification du schéma existant seraient possibles. Par exemple la fonction "ajout et rotation" utilisée pour les bandes papier par le groupe PDP-6/10 au laboratoire d'intelligence artificielle du M.I.T. Le projet MAC [12] pourrait être utile si il pouvait être prouvé qu'il vaut mieux que le schéma actuel et peut être calculé efficacement sur des machines diverses.

 

Références

 

[1]   Cerf, V.G. and Kahn, Robert E., "A Protocol for Packet Network Communications," IEEE Transactions on Communications, vol. COM-22, No. 5, May 1974.

 

[2]   Kahn, Robert E., "The Organization of Computer Resources into a Packet Radio Network", IEEE Transactions on Communications, vol. COM-25, no. 1, pp. 169-178, January 1977.

 

[3]   Jacobs, Irwin, et al., "CPODA - A Demand Assignment Protocol for SatNet", Fifth Data Communications Symposium, September 27-9, 1977, Snowbird, Utah

 

[4]    Bolt Beranek and Newman, Inc. "Specifications for the Interconnection of a Host and an IMP", Report 1822, January 1976 edition.

 

[5]   Dean, Richard A., "Elements of Abstract Algebra", John Wyley and Sons, Inc., 1966

 

[6]   Peterson, W. Wesley, "Error Correcting Codes", M.I.T. Press Cambridge MA, 4th edition, 1968.

 

[7]   Avizienis, Algirdas, "A Study of the Effectiveness of Fault-Detecting Codes for Binary Arithmetic", Jet Propulsion Laboratory Technical Report No. 32-711, September 1, 1965.

 

[8]   Kirstein, Peter, communication privée.

 

[9]   Cerf, V. G. and Postel, Jonathan B., "Specification of Internetwork Transmission Control Program Version 3", University of Southern California Information Sciences Institute, January 1978.

 

[10] Digital Equipment Corporation, "PDP-10 Reference Handbook", 1970, pp. 114-5.

 

[11] Swanson, Robert, "Understanding Cyclic Redundancy Codes", Computer Design, November, 1975, pp. 93-99.

 

[12] Clements, Robert C., communication privée.

 

[13] Conklin, Peter F., and Rodgers, David P., "Advanced Minicomputer Designed by Team Evaluation of Hardware/Software Tradeoffs", Computer Design, April 1978, pp. 136-7.