Algorithme de fragmentation pour MDS

GNU/Linux Magazine n° 099 | novembre 2007 | Yann Guidon
Creative Commons
  • Actuellement 0 sur 5 étoiles
0
Merci d'avoir participé !
Vous avez déjà noté cette page, vous ne pouvez la noter qu'une fois !
Votre note a été changée, merci de votre participation !
Le format MDS (« Multiplexed Data Stream ») est un « conteneur » à vocation musicale (un peu comme les formats MPG ou OGG), destiné au stockage et à la transmission de flux de données comprimées. Comme la plupart des conteneurs, les informations doivent être découpées en petits paquets pour faciliter la transmission et confiner les erreurs. Bien que la conception de MDS soit loin d'être terminée, cet article explique comment un algorithme simple (mais très astucieux) permet de « fragmenter » les blocs de données de manière quasiment optimale.

Introduction à MDS

MDS a été conçu comme une plate-forme commune pour développer une grande variété d'algorithmes expérimentaux de compression du son et de la musique, suite à plusieurs articles à ce sujet dans ce magazine. Cela va des algorithmes les plus simples et rapides, à très faible latence, à des algorithmes très sophistiqués qui analysent de longs blocs d'échantillons pour réduire au maximum la taille des données numériques.

La possibilité d'encoder plusieurs canaux sonores dans des flux séparés permet aussi d'expérimenter différentes techniques de corrélations, et élargit le champ des applications de MDS à l'audionumérique professionnel (pour les studios d'enregistrement ou l'audiovisuel). Il en résulte que MDS se distingue de la plupart des autres formats existants par sa granularité temporelle très flexible. Le conteneur MDS conserve aussi la synchronisation précise entre les flux d'échantillons qu'il transporte, même si leurs fréquences d'échantillonnage sont différentes entre les flux.

Il existe de nombreuses fréquences standards d'échantillonnage, dont le seul point commun est d'être exprimées en hertz, donc basées sur la seconde. Ainsi, la granularité de MDS est d'une seconde, ce qui est aussi la durée maximale d'un bloc d'échantillons et de la plupart des algorithmes. En cas de perte de flux (si quelqu'un se prend les pieds dans un câble de transmission), il faut alors au maximum une seconde pour que tout recommence à fonctionner normalement. Cela signifie aussi que les algorithmes de traitement et de compression des échantillons ne dépendent pas des secondes précédentes.

Cette indépendance entre les secondes consécutives est importante, car elle conditionne le comportement de toute la chaîne d'encapsulation et de transmission des données. Un algorithme de compression fournit ainsi, chaque seconde, d’un (pour les compresseurs très complexes) à plusieurs centaines de blocs de données (pour les algorithmes orientés vers la très faible latence), chaque bloc étant plus ou moins indépendant des autres (en fonction des algorithmes). Et ces blocs doivent être transmis le plus vite possible, sans attendre les suivants.

Figure 1 : Structure simplifiée des informations dans un canal au format MDS

Le format MDS ne spécifie pas la taille maximale d'un bloc de données. Durant une seconde, un compresseur peut générer d’1 octet (silence) à 1 Mi octets (son incompressible, échantillonné sur 32 bits à 256 KHz). Par contre, la taille d'un fragment de bloc est comprise entre 1 et 4096 octets (c'est d'ailleurs la taille des données signées par tGFSR32x4, dont il est question dans d'autres articles de ce magazine).

Dans la plupart des cas, un algorithme de compression fabrique des blocs dont la taille dépasse celle d'un fragment. Il faut évidemment découper ce bloc en de multiples fragments pour en permettre la transmission. Une couche logicielle est chargée de ce découpage (la « fragmentation », qui est le sujet central de cet article), de la signature des fragments (le sujet d'une série d'articles en cours) et de leur encapsulation (ajout de l'en-tête et chaînage entre les fragments).

Figure 2 : Structure d'une chaîne complète de traitement du signal utilisant le format MDS

Contrainte liée au multiplexage

Comme le nom MDS l'indique, plusieurs flux de données peuvent être multiplexés temporellement. Un ou plusieurs multiplexeurs peuvent être ajoutés dans la chaîne de transmission pour concentrer plusieurs flux dans un seul.

La conception d'un multiplexeur n'est pas évidente. Elle ne se résume pas à prendre un fragment de données sur chaque flux d'entrée à tour de rôle, car chaque fragment dépend de contraintes temporelles qui sont propres à chaque flux, à chaque seconde. Par exemple, imaginons un flux stable qui fournit 100 fragments (de taille identique) par seconde avec une grande régularité. Il ne peut pas être mélangé directement avec un autre flux (disons, fournissant entre 50 et 300 fragments par seconde en fonction des données transmises) de manière naïve sans introduire rapidement une désynchronisation relative. Pour garantir une latence minimale à tous les flux, le multiplexeur doit donc assurer la régulation temporelle de la transmission.

Pour aider le multiplexeur à faire du bon travail, on peut lui donner des informations à l'avance : c'est la « déclaration de bande passante ». Toutes les secondes, un paquet peut être envoyé pour indiquer les propriétés du flux, comme le nombre maximal d'octets par seconde, ce qui permet au multiplexeur d'adapter son comportement.

Une autre manière de l'aider est de ne pas envoyer de flux trop irrégulier. Des brusques envois de nombreux fragments, ou bien l'arrêt brutal, pourraient poser quelques petits soucis dans la régulation des autres flux. Voici donc une première contrainte pour l'algorithme de fragmentation.

Fragmentation naïve et problématique

L'autre contrainte (similaire) découle du coût (en ressources et en calculs) du traitement des fragments. Chaque fragment nécessite, en émission comme en réception, l'allocation d'une zone contiguë en mémoire, le calcul de la signature, et la fabrication ou l'examen de l'en-tête, ce qui représente beaucoup de travail pour de si petites puces. Tous ces efforts devraient être aussi utiles que possible, la fragmentation doit donc augmenter le ratio d'information par fragment. Puisque l'en-tête est de taille fixe, cela revient à maximiser la taille des fragments.

Imaginons maintenant que nous voulons transmettre, après encodage, un bloc de données contenant 8200 octets. Celui-ci sera découpé en 3 fragments, et une approche simple donnera le résultat suivant :

Figure 3 : Fragmentation naïve

Pour l'ensemble des algorithmes de gestion des flux MDS, le souci est le petit fragment résiduel, dont la taille dépend de celle du bloc initial. Il est dommage de se retrouver avec un tout petit fragment d’1, 10 ou 100 octets seulement, car son traitement nécessite autant de temps que celui des fragments plus longs (ce qui, dans des applications temps réel ou embarquées, est toujours trop long).

Pour visualiser ce qui se passe, voici un peu de code source et un histogramme des tailles de fragments générées par l'algorithme naïf. Pour faciliter l'affichage, nous considérons dans cet article que la taille des fragments est comprise entre 1 et 64 octets (il suffit de changer le #define pour retrouver les 4096 octets de MDS). L'histogramme a été obtenu en fragmentant toutes les tailles de blocs possibles entre 64 et 2048 octets inclus.

/* Algorithme de fragmentation n°1 (naïf) */

#include <stdio.h>

#define TAILLE_FRAGMENT 64

/* le programme n'envoie pas réellement les données

mais on observe son comportement : */

int histo[TAILLE_FRAGMENT+1];

#define SEND(x) { histo[x]++; }

void main() {

  int i, taille_bloc;

  /* pour toutes les tailles de blocs de 64 à 2K */

  for (i=TAILLE_FRAGMENT; i<=TAILLE_FRAGMENT*32; i++) {

    taille_bloc = i;

    /* approche "greedy" : */

    while (taille_bloc > TAILLE_FRAGMENT) {

      SEND(TAILLE_FRAGMENT);

      taille_bloc-=TAILLE_FRAGMENT;

    }

    /* envoie le reste */

    SEND(taille_bloc);

  }

  /* imprime l'histogramme sur stdout pour gnuplot */

  for (i=0; i<=TAILLE_FRAGMENT; i++) {

    printf("%d %d\n",i, histo[i]);

}

}

Figure 4 : Histogramme des tailles de fragments générés par l'algorithme naïf.

Note

Attention, tous les histogrammes de cet article sont générés avec les mêmes paramètres graphiques et avec une échelle logarithmique pour les tailles de fragments. Sur l'histogramme ci-dessus, la barre la plus haute mesure 31776 unités et les plus basses mesurent 31 unités, ce qu'il n'aurait pas été facile de représenter avec une échelle linéaire.

Sur 33729 fragments générés, 1953 ne sont pas de taille maximale, dont la moitié a une taille inférieure à la moitié de la taille maximale d'un fragment. En ce qui concerne MDS, il serait désirable de ne pas avoir de fragment de taille inférieure à 2048 octets environ (lorsque c'est possible). Cette approche simpliste ne le permet évidemment pas, alors regardons du côté de l'arithmétique pour trouver une solution théorique et idéale.

Application mathématique

Posons le problème simplement : nous désirons diviser le bloc original en parties quasiment égales. Par exemple, pour un bloc de 4098 octets, nous désirons obtenir deux fragments de 4098/2=2049 octets, pour éviter d'envoyer un fragment contenant uniquement deux octets. Pour un bloc de (x<TAILLE_FRAGMENT)+(N×TAILLE_FRAGMENT) octets, il faudrait que la taille de chaque fragment soit au pire de TAILLE_FRAGMENT-(TAILLE_FRAGMENT/N), ce qui converge vers TAILLE_FRAGMENT quand N augmente.

Taille du bloc taille des fragments nombre de fragments
1 - 4O96 1 - 4O96 1
4O97 - 8192 2048 - 4O96 2
8193 - 12288 2730 - 4O96 3
12289 - 16384 3072 - 4O96 4

C'est donc juste l'histoire d'une division, me direz-vous. Mais ce n'est pas si simple, puisque les fragments ont une taille entière et la division entière arrondit à l'unité inférieure (par défaut). En pratique, sur un très gros bloc à fragmenter, les erreurs d'arrondis peuvent se cumuler et le dernier fragment, qui devra compenser toutes les erreurs, aura une taille supérieure aux autres. Dans le pire des cas, il pourrait même dépasser la taille maximale d'un fragment !

Pour filtrer les erreurs d'arrondis, la solution la plus conservatrice consiste à recommencer à chaque fois le calcul en tenant compte des calculs précédents, ce qui maintient la taille moyenne des fragments à une valeur stable.

/* Algorithme de fragmentation n°2

(divisions multiples) */

int i, taille_bloc, taille_fragment, nombre_fragments;

/* pour toutes les tailles de paquets de 64 à 2K */

for (i=TAILLE_FRAGMENT; i<=TAILLE_FRAGMENT*32; i++) {

  taille_bloc = i;

  /* fragmentation par divisions multiples */

  while (taille_bloc > TAILLE_FRAGMENT) {

    nombre_fragments =

      (taille_bloc+TAILLE_FRAGMENT-1)/TAILLE_FRAGMENT;

    taille_fragment = taille_bloc / nombre_fragments;

    SEND(taille_fragment);

    taille_bloc-=taille_fragment;

  }

  SEND(taille_bloc); /* envoie le reste */

}

Figure 5 : L'utilisation de divisions entières permet à l'histogramme de suivre une répartition exponentielle presque idéale, mais l'opération de division entière est lourde.

L'histogramme montre que la répartition des tailles des fragments est presque idéale, si on accepte que la taille maximale est relativement peu utilisée (à cause de la tendance naturelle de la division à arrondir par défaut).

Cependant, cette approche a un autre défaut encore plus gênant : elle utilise non pas une, mais deux divisions entières, et cela pour chaque fragment. Il faut rappeler qu'une seule division entière peut occuper un processeur SPARC pendant 230 cycles. Les autres processeurs sont habituellement plus rapides, de l'ordre de 40 cycles, mais comme MDS doit travailler en temps réel sur des processeurs peu puissants, il ne faut pas compter sur une exécution rapide de l'algorithme n°2.

Faites chauffer les Hackmem !

La division entière dure des dizaines de cycles, mais il existe plusieurs alternatives. En particulier, il est possible d'effectuer des divisions en un seul cycle (généralement) au moyen de décalages, mais il faut que le diviseur soit une puissance de deux. C'est une voie bien plus prometteuse, mais qui nécessite de nombreuses adaptations de l'algorithme précédent.

D'abord, on remarque que le calcul du nombre de fragments divise la taille du bloc par la taille maximale d'un fragment. Puisque TAILLE_FRAGMENT est fixé à 4096, soit 2^12, cette division peut être effectuée par un décalage de 12 positions vers la droite. Voilà déjà une division éliminée.

/* code original : */

nombre_fragments =

  (taille_bloc+TAILLE_FRAGMENT-1)/TAILLE_FRAGMENT;

/* code amélioré : */

nombre_fragments = (taille_bloc+TAILLE_FRAGMENT-1)>>12;

On peut encore faire mieux si on remarque que ce code est dans la boucle afin d'empêcher le cas extrême où les erreurs d'arrondis changeraient le nombre de fragments. Puisque notre code est numériquement stable grâce à des recalculs en cours de route, nous pouvons sortir cette opération hors du corps de la boucle. Par contre, il ne faut pas oublier de décrémenter la variable nombre_fragments à chaque itération.

La division suivante, qui détermine taille_fragment en fonction de taille_bloc, est beaucoup plus délicate. J'ai d'ailleurs pas mal tourné en rond, jusqu'à ce que je m'aperçoive qu'il n'était pas nécessaire de recalculer taille_fragment tout le temps :-) Et si on peut choisir de ne pas effectuer la division, on peut l'effectuer uniquement lorsqu'elle est facile, c'est-à-dire lorsque nombre_fragments est une puissance de deux. Une division par décalages successifs est possible, et la boucle s'arrête lorsque taille_fragment devient inférieur à TAILLE_FRAGMENT.

Pour déterminer si nombre_fragments est une puissance de deux, j'utilise une vieille astuce tirée selon mes souvenirs d'un Hackmem du MIT. Le principe est simple : les nombres qui sont des puissances de deux sont les seuls qui ont les mêmes bits de poids faible que leur complément. C'est valable pour les entiers signés « en complément à deux », c'est-à-dire sur tous les ordinateurs conçus depuis les années 80.

/* retourne "vrai" si x est une puissance de 2 */

#define ISPOW2(x) (((- x) & x) == x)

représentation

x      binaire        -x    (-x & x) résultat

1          1        111111       1      vrai

2         10        111110      10      vrai

3         11        111101       1      faux

4        100        111100     100      vrai

5        101        111011       1      faux

Que faire lorsque nombre_fragments n'est pas une puissance de deux ? On pourrait calculer une première valeur de taille_fragment hors de la boucle, mais ce calcul nécessiterait une division classique. En fait, il est beaucoup plus simple et efficace d'initialiser taille_fragment avec la taille maximale permise.

/* Algorithme de fragmentation n°3

(divisions conditionnelles par décalages) */

#define TAILLE_SHIFT 6

#define TAILLE_FRAGMENT (1 << TAILLE_SHIFT)

#define ISPOW2(x) (((- x) & x) == x)

int i, taille_bloc, taille_fragment, nombre_fragments;

for (i=TAILLE_FRAGMENT; i<=TAILLE_FRAGMENT*32; i++) {

  taille_bloc = i;

  /* arrondit la taille du bloc au multiple de fragment

supérieur avant de diviser par la taille du fragment */

  nombre_fragments =

   (taille_bloc+TAILLE_FRAGMENT-1)>>TAILLE_SHIFT;

  /* valeur de départ par défaut : */

  taille_fragment = TAILLE_FRAGMENT;

  while (taille_bloc > TAILLE_FRAGMENT) {

    if (ISPOW2(nombre_fragments)) {

      /* recalcule la taille par division

à décalages successifs */

      taille_fragment = taille_bloc;

      while (taille_fragment > TAILLE_FRAGMENT)

        taille_fragment >>= 1; /* division par 2 */

    }

    SEND(taille_fragment);

    taille_bloc-=taille_fragment;

    nombre_fragments--;

  }

  SEND(taille_bloc); /* envoie le reste */

}

Figure 6 : Les divisions par des puissances de deux accélèrent le code et l'histogramme ressemble vaguement au précédent.

Toujours plus simple, plus beau, plus rapide...

Dans l'ensemble, l'algorithme n°3 est un grand bond en avant. En plus d'éviter une division classique, l'exécution conditionnée par une puissance de deux réduit encore le nombre de calculs. Pourtant, avec plus d'astuces, il est possible de faire bien mieux en réorganisant les opérations.

En particulier, la boucle de la division itérative est tout à fait superflue. Comme elle sera exécutée à chaque fois que nombre_fragments est une puissance de 2, et puisque ce nombre décroît, on peut simplifier encore les opérations au moyen de tout ce que nous savons déjà. Mais il faudrait disposer, avant la boucle, d'un logarithme qui nous donnerait le nombre de décalages à effectuer au début. Ensuite, il suffit de décrémenter ce logarithme et d'attendre le tour suivant, où nombre_fragments est encore une puissance de deux.

Pour calculer le logarithme, j'utilise encore une petite boucle d'approximation (d'autres méthodes sont possibles, mais j'ai choisi la facilité). Cela permet de préparer deux variables : log_fragments et limite_multiple. Le rôle de log_fragments est de mémoriser le nombre de décalages à effectuer dans la boucle de fragmentation principale, comme décrit précédemment.

Le rôle de limite_multiple est très important et beaucoup plus subtil. Dans l'algorithme précédent, la boucle de division par décalages est terminée lorsque le dividende est inférieur au diviseur. C'est une simple application de la technique de division apprise à l'école primaire, mais aussi une autre opportunité de déplacer les calculs. Puisque nous disposons maintenant du logarithme de la taille du bloc à fragmenter, il n'y a plus besoin d'effectuer une boucle de division. Par contre, il faut encore déterminer quand le recalcul a lieu, et le Hackmem nécessite plusieurs opérations pour chaque fragment.

En fait, limite_multiple permet d'enlever le Hackmem et de faire fusionner la boucle de division avec la boucle de fragmentation. La valeur de limite_multiple est une puissance de deux, multipliée par la taille maximale des fragments. Lorsque la taille restante du bloc descend en dessous de cette limite, il n'y a plus que deux décalages et une décrémentation à exécuter.

/* Algorithme de fragmentation n°4

(sans test de puissance de 2 à chaque itération) */

int i, taille_bloc, taille_fragment,

    limite_multiple, log_fragments;

for (i=TAILLE_FRAGMENT; i<=TAILLE_FRAGMENT*32; i++) {

  taille_bloc = i;

  /* prépare deux variables avec un log2() primaire */

  limite_multiple = TAILLE_FRAGMENT;

  log_fragments = 0;

  while (limite_multiple <= taille_bloc) {

    limite_multiple <<= 1;

    log_fragments++;

  }

  /* boucle principale de fragmentation : */

  taille_fragment = TAILLE_FRAGMENT;

  while (taille_bloc > TAILLE_FRAGMENT) {

    /* recalcule la taille par simple décalage */

    if (limite_multiple > taille_bloc) {

      taille_fragment = taille_bloc >> log_fragments;

      log_fragments--;

      limite_multiple >>= 1; /* division par 2 */

    }

    SEND(taille_fragment);

    taille_bloc-=taille_fragment;

  }

  SEND(taille_bloc);   /* envoie le reste */

}

Figure 7 : La simplification de l'algorithme accélère encore le code, mais les fragments de taille maximale sont peu utilisés.

La version finale

Il reste encore quelques petits défauts à gommer et l'algorithme sera parfait. Pour commencer, les tailles maximales de fragments restent sous-utilisées, ce qui est un peu gênant (chipotons un peu...).

Il faut aussi tenir compte du fait que le traitement des fragments est plus efficace lorsque les adresses et les tailles sont alignées sur 4 octets. D'une part, les accès aux mots non alignés sont souvent lents ou interdits, et d'autre part, lorsque les fragments sont concaténés lors de la reconstruction du bloc, une taille non multiple de 4 va désaligner tous les fragments suivants.

Ces deux défauts sont résolus par une seule technique : il faut arrondir les tailles de fragments à l'excès, sur 4 octets. L'alignement des blocs est donc favorisé, et les fragments de taille maximale redeviennent majoritaires. Et pour arrondir la taille, il suffit de deux opérations arithmétiques simples :

#define ROUND_MASK 3 /* 4-1 */

taille_fragment =

   (taille_fragment + ROUND_MASK) & ~ROUND_MASK;

Un autre petit inconvénient est la boucle de calcul de logarithme. Il n'y a pas d'intérêt à la faire tourner trop longtemps, puisque l'arrondi des tailles de fragments va les maintenir au maximum dans la plupart des cas. Par la suite, je limite la boucle à 3 itérations, ce qui permet de répartir les reliquats d'un bloc sur 2^3=8 fragments. Plus n'apporterait aucune amélioration, et l'histogramme suivant montre que le résultat est déjà très bon.

Enfin, il faut souligner un détail très bien caché : le code suivant n'effectue aucune division par TAILLE_FRAGMENT. Cela signifie que TAILLE_FRAGMENT peut prendre n'importe quelle valeur autre qu'une puissance de deux. La seule condition est d'être multiple de 4. C'est extrêmement intéressant, puisque l'algorithme de fragmentation peut travailler avec d'autres tailles de fragments que MDS, par exemple 1500 octets pour les trames Ethernet. Dans l'exemple suivant, j'ai fixé la taille à 44 octets, et le seul effet visible est l'apparition de quelques fragments de taille légèrement inférieure à 44/2=22 octets (ce qui est complètement bénin).

/* Algorithme de fragmentation n°5

tailles arrondies à des multiples de 4

et fragments de tailles presque arbitraires */

#define MAX_APPROX 3

#define ROUND_MASK 3

#define TAILLE_FRAGMENT 44

/* doit être multiple de (ROUND_MASK+1) */

int i, taille_bloc, taille_fragment,

    limite_multiple, log_fragments;

for (i=TAILLE_FRAGMENT; i<=TAILLE_FRAGMENT*32; i++) {

  taille_bloc = i;

  /* prépare deux variables avec un log2() limité */

  limite_multiple = TAILLE_FRAGMENT;

  log_fragments = 0;

  while ((limite_multiple <= taille_bloc)

      && (log_fragments < MAX_APPROX)) {

    limite_multiple <= 1;

    log_fragments++;

  }

  /* boucle principale de fragmentation : */

  taille_fragment = TAILLE_FRAGMENT;

  while (taille_bloc > TAILLE_FRAGMENT) {

    /* recalcule la taille par simple décalage */

    if (limite_multiple > taille_bloc) {

      taille_fragment = taille_bloc >> log_fragments;

      /* arrondit au multiple supérieur */

      taille_fragment =

          (taille_fragment + ROUND_MASK) & ~ROUND_MASK;

      log_fragments--;

      limite_multiple >= 1; /* division par 2 */

    }

    SEND(taille_fragment);

    taille_bloc-=taille_fragment;

  }

  SEND(taille_bloc); /* envoie le reste */

}

Figure 8 : L'algorithme de fragmentation final favorise les tailles multiples de 4, et suit une répartition proche de celle de l'algorithme n°2 sans utiliser une seule division.

Et comment fait TCP/IP ?

Les contraintes et les objectifs des protocoles à la base d'Internet sont bien différents de MDS. En particulier, un flux MDS ne prend qu'un seul chemin, alors que des paquets TCP/IP peuvent (théoriquement) transiter par une multitude de chemins différents. La fragmentation de MDS est gérée plus simplement qu'avec TCP, puisque l'ordre des fragments MDS n'est pas destiné à être changé (il serait étonnant qu'un disque dur réordonne ses données...). Si un flux MDS devait être transmis sur Internet, il faudrait utiliser une connexion TCP et non-IP, car ce dernier n'assure pas la retransmission et ne garantit pas l'ordre d'arrivée des données.

La taille des données est aussi différente. Un datagramme du protocole TCP a une taille maximale de 65536 octets, et il est fragmenté en cours de transmission en fonction du chemin parcouru. D'un autre côté, la taille des blocs transmis dans un flux MDS n'est pas limitée.

En ce qui concerne la fragmentation par TCP, effectuée au niveau des routeurs, la question des reliquats minuscules ne semblait pas être la préoccupation majeure de ses concepteurs. Les exemples de fragmentation trouvés sur le web présentent tous l'algorithme naïf que nous avons déjà vu au début de l'article. La description la plus précise que j'ai pu trouver provient de la RFC791 (Internet Protocol Specification, septembre 1981) :

Page 8 :

To fragment a long internet datagram, an internet protocol module (for example, in a gateway), creates two new internet datagrams and copies the contents of the internet header fields from the long datagram into both new internet headers. The data of the long datagram is divided into two portions on a 8 octet (64 bit) boundary (the second portion might not be an integral multiple of 8 octets, but the first must be). [...]

This procedure can be generalized for an n-way split, rather than the two-way split described.

Page 26 :

An Example Fragmentation Procedure

The maximum sized datagram that can be transmitted through the next network is called the maximum transmission unit (MTU).

If the total length is less than or equal the maximum transmission unit then submit this datagram to the next step in datagram processing; otherwise cut the datagram into two fragments, the first fragment being the maximum size, and the second fragment being the rest of the datagram. The first fragment is submitted to the next step in datagram processing, while the second fragment is submitted to this procedure in case it is still too large.

Nous avons donc bien affaire à l'algorithme naïf. La RFC prévoit tout de même d'améliorer cette technique, en donnant l'exemple d'un autre algorithme, qui est moins bon puisqu'il ne minimise pas le nombre de paquets :

In the above procedure each fragment (except the last) was made the maximum allowable size. An alternative might produce less than the maximum size datagrams. For example, one could implement a fragmentation procedure that repeatly divided large datagrams in half until the resulting fragments were less than the maximum transmission unit size.

Je ne suis pas en mesure de déterminer si tous les routeurs actuels travaillent comme le décrit la RFC791 (qui a maintenant 26 ans). Rien n'empêche un fabricant de routeurs d'implémenter l'algorithme de fragmentation décrit dans cet article, puisqu'il est aussi adapté à TCP/IP. Il faut juste changer la granularité de l'arrondi à 8 octets au lieu de 4.

Conclusion

MDS est conçu pour accepter presque n'importe quel flux de données, tant qu'il est suffisamment bien formaté, pour assurer la flexibilité et la résilience de l'ensemble du système. Malgré cette tolérance, il est recommandé d'utiliser l'algorithme décrit dans cet article lorsque les blocs à transmettre sont de taille supérieure à celle d'un fragment. Cela assure que la taille de tous les fragments est supérieure à la moitié de la taille maximale (sauf quelques rares exceptions sans importance, à cause de l'arrondi), ce qui permet une utilisation optimale de toutes les ressources d'un système MDS.

En dessous de 4096 octets (le MTU standard de MDS), il n'est évidemment pas possible d'agir au niveau de l'encapsulation, puisque la responsabilité d'envoyer des blocs courts est prise par l'algorithme de compression. Le coût relatif du traitement des données augmente, mais c'est parfois un compromis nécessaire pour réduire la latence du flux.

Un algorithme de fragmentation n'est pas utile seulement pour les systèmes de transmission de données par paquets. Tout autre système qui alloue dynamiquement des ressources à des utilisateurs hétérogènes pourrait en bénéficier, comme le scheduler d'un noyau de système d'exploitation...

Liens

- Miroir des sources : http://ygdes.com/sources/

- RFC 791 : Internet Protocol Specification (septembre 1981) (décrit la fragmentation et le réassemblage) : http://www.ietf.org/rfc/rfc0791.txt

Voir aussi :

- RFC 879 : The TCP Maximum Segment Size and Related Topics (novembre 1983)

- RFC 1122 : Requirements for Internet Hosts-Communication Layers (novembre 1990)

- Hackmem du MIT (mais pourquoi je n'ai jamais mis ce lien dans mes articles précédents ???) : http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html