Token Bucket Filter

Dans ce 2ème travail pratique du cours " Structure des réseaux informatiques et multimédia", vous étudierez des mécanismes de shaping et de policing en utilisant un token bucket et un leaky bucket. Cela permet de montrer que les sources ont tout intérêt à mettre en forme leur trafic pour ne pas perdre des paquets dans les noeuds qui imposent une limite sur le débit.

Vous rendrez un fichier tgz contenant le rapport, les scripts ns représentant les simulations que vous avez faites, les scripts ou programmes annexes que vous auriez utilisé et les traces (pas celles pour nam) qui ont servi à faire le rapport.

Scénario

Les réponses aux différentes questions se feront à partir de la topologie sur la figure ci-dessous que l'on vous demande de construire à l'aide d'un script ns (OTcl + Tcl). Les différents agents présents aux noeuds seront adaptés selon la question étudiée. La présence ou l'absence d'un filtre à la source ou à la destination dépend de la question étudiée.

La page de tutoriel est toujours une bonne source d'informations.

Voici quelques indications qui vous aideront à créer vos simulations:

• Un TBF (Token Bucket Filter) possède trois paramètres dans ns:
  1. bucket_ est la taille du seau en bits (le sigma du cours).
  2. rate_ est le débit d'arrivée des jetons dans le seau en jeton/s, chaque jeton correspondant à un bit (le rho du cours).
  3. qlen_ est la capacité de la file du TBF en nombre de paquets.
• Un policer est un TBF qui jette (ou marque) les paquets non conformes càd un TBF dont la capacité de la file est nulle. Dans notre cas, le policer sera toujours un TBF qui jette les paquets.
• Regardez les fichiers d'exemple suivants: tbf.tcl et test-tbf.tcl (présent dans la distribution de ns).
• Une source exponential on/off (Documentation, page 265) possède quatre paramètres dans ns:
  1. packetSize_ est la taille constante des paquets générés exprimée en octets.
  2. burst_time_ est le temps moyen pendant lequel le générateur est "on" exprimé en secondes.
  3. idle_time_ est le temps moyen pendant lequel le générateur est "off" exprimé en secondes.
  4. rate_ est le débit auquel sont envoyés les paquets pendant les périodes "on" et est exprimé en bits/secondes.
• Important. La formule du cours théorique donne la taille maximale d'une rafale pour un cas idéal non discrétisé (fluide). Cependant lorsque l'on veut exprimer la taille de la rafale en terme de paquets de taille fixe, il faut utiliser la formule suivante où est la taille de la rafale en paquets, sigma est exprimé en paquets, P et rho sont exprimés en paquets par seconde: .
  Pour les simulations de ce travail on utilisera cette dernière formule.
  Remarque: Plus précisément, la différence entre la formule du cours et celle-ci provient du fait qu'on parle de paquets de taille fixe au lieu d'un fluide et que ns ne calcule le nombre de tokens dans le seau que lorsqu'on est susceptible de pouvoir envoyer un paquet (envoi conditionné uniquement par la taille du seau). Donc le remplissage du seau est discrétisé dans le temps.

Partie 1: Source On/Off + Shaper

Dans un premier temps, il n'y a pas de policer. La source On/Off a les caractéristiques suivantes:

• paquets de taille fixe 1000 octets
• débit pendant la période "On"de 2 Mbits/s.
• Une période "on" de 0.01 seconde.
• Une période "off" de 0.15 seconde.

L'enveloppe de trafic souhaitée à la sortie du shaper (TBF au noeud 0) possède les caractéristiques suivantes:

• MBS (Maximum Burst Size) = 5 paquets
• Peak rate équivalent à la capacité de la ligne = 1 Mbits/s
• Average rate = 200 Kbits/s

La bande passante du lien entre les noeuds 1 et 2 est de 200Kbits/s.

1. Le paramètre qlen_ est fixé à 10 paquets. Trouvez les paramètres bucket_ (sigma) et rate_ (rho) du TBF pour obtenir l'enveloppe de trafic souhaitée. Indiquez vos calculs.
2. Vérifiez sur un graphique que la courbe du nombre de paquets envoyés sur le lien 0-1 en fonction du temps est comprise dans l'enveloppe specifiée précédemment.
3. Trouvez la capacité minimum de la file d'attente au noeud 1 pour qu'il n'y ait pas de pertes de paquets à ce noeud.

Partie 2

Tout en conservant les paramètres rho, sigma et qlen_ du TBF de la partie 1, ajoutez un deuxième TBF de façon à limiter le peak rate de sortie du noeud 0 à 500Kbits/s.

1. Vérifiez sur un graphique que la courbe du débit envoyé sur le lien 0-1 en fonction du temps respecte la nouvelle enveloppe.
2. Quel est l'impact sur la capacité minimale de la file d'attente au noeud 1?

Partie 3: Source On/Off + Shaper + Policer

Reprenez la topologie de la partie 1 et ajoutez un policer à l'entrée du noeud 1 qui "police" le trafic à 200Kbits/s et permet des rafales de 5 paquets. La bande passante du lien entre les noeuds 1 et 2 est de 1Mbits/s.

1. Y a-t-il des pertes au policer du noeud 1 ? Pourquoi ?

Partie 4: Source FTP

La source FTP émet 150Ko (1200Kbit) par paquets de 1000 octets.

La bande passante du lien entre les noeuds 1 et 2 est de 200 Kbits/s. La file d'attente au noeud 1 a une capacité de 10 paquets.

Dans un premier temps, il n'y a pas de policer ni de shaper.

1. Calculez le débit effectif de la source, et le pourcentage de pertes.

Augmentez la capacité du lien entre les noeuds 1 et 2 à 1 Mbits/s. Introduisez un policer à l'entrée du noeud 1. Ce policer doit posséder les caractéristiques suivantes:

• MBS (Maximum Burst Size) = 5 paquets
• Average rate = 200 Kbits/s

2. Calculez le débit effectif de la source, et le pourcentage de pertes.

Introduisez un shaper à la sortie du noeud 0. Prenez le même rho et le même sigma du policer. Trouvez la longueur minimale de la file d'attente du shaper de manière à ce qu'il n'y ait pas de pertes au shaper.

3. Calculez le débit effectif de la source, et le pourcentage de pertes.
4. Comparez les débits effectifs et les pourcentages de pertes obtenus dans les trois cas (questions 1, 2 et 3). Expliquez les différences observées.

Références

• S. Keshav, An Engineering Approach to Computer Networking, Addison-Wesley, 1997.

Ok si les browsers étaient compatibles CSS2:

Last modified: Fri Jan 26 09:41:10 CET 2001