Université de La Manouba
Ecole Nationale des Sciences
de l’Informatique
Devoir Surveillé
Année Universitaire 2010/2011
Matière : Réseaux Locaux Classe : II2 Documents non autorisés
Questions indépendantes
1) Quelle est la différence entre un Hub et un Switch (commutateur) Ethernet ?
Lorsqu’un hub reçoit une trame Ethernet, il va la répliquer sur l’intégralité des fils qui lui sont branchés
dessus. Un switch n’ouvre qu’une connexion à la fois car il ’retient’ à quelle machine appartient
l’adresse IP et l’adresse physique demandée. Toute autre réponse s’approchant de cette dernière est
acceptée.
Durée : 2h00
2) Que se passe t-il lorsque la carte réseau Ethernet d’une station est configurée en duplex-intégral (full-
duplex) alors qu’elle est connectée à un Hub ? Est-il possible que la station échange des trames avec
d’autres stations connectées au même Hub ? Expliquer.
Le hub fonctionne en Half-duplex un problème Duplex-Mismatch se pose : à la suite d’un slot il n y a plus
de garantie de non collision, certaines trames subissent des collisions sans que ceci ne soit détecté et
donc sans qu’elles ne soient retransmises. Si une seule trame est envoyée à la fois celle-ci passe à travers
le réseau.
3) L’algorithme du retard exponentiel binaire (BEB : « Binary Exponential Backoff »), agrandit
l’intervalle suivant lequel est généré le retard aléatoire et ceci à la suite de chaque collision (tant que le
nombre de collisions n’a pas dépassé 10 collisions). Quel est l’intérêt de cette gestion dynamique de la
taille de l’intervalle ? Selon cet algorithme, est-ce qu’une trame, après qu’elle ait subi plusieurs collisions,
sera favorisée par rapport à celles ayant subi moins de collisions ? Expliquer.
Adapter la durée d’attente de façon à l’augmenter au fur et à mesure que le nombre de collision successif
augmente. Un petit intervalle conduirait à une probabilité de collision élevée en cas où le réseau est
chargé. Un grand intervalle conduirait à des temps d’attente considérables inutiles lorsque le réseau est
faiblement chargé. L’algorithme BEB défavorise les trames ayant subi le plus de collisions ce qui est un
inconvénient puisque le retard pour ces trames devient plus important ce qui n’est pas équitable.
4) Dans un réseau Ethernet, quelles sont les conséquences potentielles de la présence d’un segment dont
la longueur dépasse la limite autorisée ? Est-ce qu’une trame émise pourrait arriver à destination ?
Expliquer.
Sur ce segment, une fois la distance maximale est parcourue, le signal risque de s’affaiblir de manière à
devenir non significatif. La trame associée est alors perdue. De plus le temps d’allée-retour va ainsi
dépasser la limite autorisée et en conséquence la détection de collision par l’émetteur n’est plus garantie.
- Cas où une trame arrive à destination : la trame ne subit pas de collision et la destination de la
trame se trouve à un endroit du support de transmission qui lui permet de récupérer la trame
avant que le signal s’affaiblit
- Cas où une trame n’arrive à destination :(1) la trame subit une collision non détectée par
l’émetteur. (2) les signaux s’affaiblissent et deviennent non significatifs (ou incorrects)
Advertisement
5) La méthode d’accès CSMA/CA, retenue pour les réseaux Wifi, fait appel aux trames de contrôle
RTS/CTS, en quoi est-il utile le recours à ces trames de contrôle ?
- Utiliser des trames courtes pour la réservation du canal avant d’émettre de longues trames
- L’envoi du CTS étend la portée du « Virtual carrier sense »
Exercice 1
On considère un réseau local utilisant la méthode d’accès jeton sur anneau et comportant N stations.
Chaque station émet une trame (exactement) à chaque passage du jeton. Nous supposons que le jeton est
libéré dès que l’émetteur termine l’injection de sa trame dans le réseau. Le délai de passage du jeton
d’une station vers la suivante est D/N. le délai d’injection d’une trame D/A. Déterminer le taux
d’utilisation effectif du réseau en fonction de A. Comment peut-on expliquer que le taux d’utilisation
effectif du réseau est une fonction croissante en fonction du nombre de stations.
1
N/A+1
1/4
A chaque rotation du jeton un surcoût égal à D est dépensé pour l’envoi de N trames. Ce surcoût est mieux amorti
lorsque N augmente.
Exercice 2
On considère un réseau local IEEE 802.3 (Ethernet) comportant trois stations A, B et C. Nous rappelons
que la retransmission en cas de collision est effectuée selon l'algorithme du retard exponentiel binaire
BEB. Nous utilisons comme mesure de temps le "time slot" qui est le temps d’allée-retour. Les délais
d'espacement inter-trames ainsi que les durées de détection de voie libre sont négligés. Une collision
occupe 1 slot de temps. On suppose que toutes les trames sont de taille fixe et la durée de leur
transmission est égale à 2 slots.
Nous supposons qu'à l'instant t=0 l'écoute du canal retourne le résultat "voie libre". Le tableau suivant
précise pour chaque station et pour chaque trame à émettre l’instant à partir duquel la trame se trouve
dans les mémoires tampons de l’émetteur en attente d’être émise :
Ordre de la trame A
0
8
1ère trame
2ème trame
B C
5
0
17
13
Le tableau suivant précise pour chaque station et pour chaque trame à émettre le tirage aléatoire selon le
nombre de collisions successives (une trame ne subit pas, forcément, autant de collisions que ce qui est
prévu dans le tableau) :
1ère trame
Ordre de la trame Ordre du tirage A
1
Advertisement
1
2
8
0
2
2
3
1er tirage
2ème tirage
3ème tirage
4ème tirage
1er tirage
2ème tirage
3ème tirage
4ème tirage
2ème trame
B C
1
1
3
2
4
3
5
4
1
0
1
1
3
2
10
6
Compléter le diagramme suivant en indiquant pour chaque slot l'état de la voie.
Un slot occupé par la transmission d'un message correctement émis par la station A est représenté par
"A". Un slot occupé par une collision est représenté par "X". Un slot correspondant à une absence de
transmission est représenté par "—"
t=0 1
X
X
A
Advertisement
A
X
X
A
A
B
B
15
B
X
30
C
C
C
C
15
B
Exercice 2 :
Un réseau de type CSMA/CD comporte exactement deux stations utilisant l'algorithme de backoff BEB.
Au départ, les deux stations émettent simultanément une trame produisant ainsi une collision initiale.
Nous supposons qu’à chaque collision une tranche canal (un slot de temps) est systématiquement perdue
pour la détection de la collision.
Déterminer la durée maximale de la contention (temps perdu) si exactement 5 collisions successives se
produisent. Exprimer cette durée en nombre de slots.
5*1+ 1 + 3 + 7 + 15 + 31 =62 slots
Exercice 3
On considère un réseau local IEEE 802.3 (Fast Ethernet), dans lequel le signal électrique se propage à la
vitesse de 200 000 km/sec. et le débit est de 100 Mbits/sec. Une station A commence à émettre une trame
à l'instant t0 = 0.
1) Soit une station B, distante de 200 mètres de A, cette station peut commencer à son tour à émettre
jusqu'à l'instant t1 = 1 μs. Expliquer pourquoi.
2/4
Le signal émis par la station A n'atteint B qu'à l'instant t1 = 1 μs. Jusque là, le bus apparaît libre pour B,
qui peut donc émettre
2) On suppose que B commence effectivement à émettre à l'instant t1 - ε ; à quel instant t2 la station A
détectera-t-elle une collision ? Combien d'octets aura-t-elle transmis ?
La station A détectera la collision à l'instant t2 = t1 - ε + t1, puique le temps de propagation du signal de
B vers A est égal au temps t1 de propagation du signal de A vers B. Soit t2 = 2 t1 - ε = 2 - ε μs.
Une station transmet 100 bits par μs, donc A a tranmis un peu moins de 200 bits avant de détecter la
collision, soit un peu moins de 25 octets.
3) Sachant que 64 octets est la taille minimale d'une trame IEEE 802.3, déduire une distance maximale
Advertisement
entre deux stations, pour que le protocole fonctionne correctement. Calculer cette distance maximale.
Le protocole exige, pour fonctionner correctement, qu'une collision soit détectée par une station
émettrice avant que la totalité de la trame soit émise. 64 octets, soit 512 bits, sont émis en 5.12 μs, et la
question précédente montre que le temps nécessaire à la détection d'une collision est au pire celui d'un
aller-retour du signal entre les deux stations les plus éloignées. La distance maximale est donc de 512
mètres (résultat numérique qu'on peut déduire sans effort de la question précédente : si une distance de
200m permet l'émission de 200 bits avant détection d'une collision, une distance de 512m permet
l'émission de 512 bits)
4) Le temps est divisé en tranches de durée τ , on rappelle qu'après détection d'une première collision,
une station interrompt immédiatement sa transmission, laisse s'écouler aléatoirement 0 ou 1 tranche de
temps (période dite de contention), puis réémet sa trame dès que le canal est libre.
a. Montrer que si la durée τ d'une tranche de temps est légèrement inférieure à 2 μs, il existe un
scénario où malgré que les deux stations A et B choisissent un nombre aléatoire différent (parmi
0 et 1), les trames réémises entrent à nouveau en collision.
B détecte la collision à l'instant t1 = 1 μs, et A à l'instant t2 = 2 - ε μs. Si A choisit de réémettre
immédiatement, le signal émis par A arrive en B à l'instant t3 = 3 - ε μs, supérieur à t1 + τ si τ < 2 - ε μs.
Donc B, dans ce cas, croit le bus libre après avoir laissé s'écouler une tranche de temps, et l'on se
retrouve dans la situation de la question 1
b. En utilisant la question 3, calculer la valeur minimale de τ pour que le protocole fonctionne
correctement.
Si deux stations sont séparées de 512m (distance maximale calculée à la question 3), la question
précédente et une règle de trois montrent que la valeur minimale pour τ (valeur qui assure qu'un choix
aléatoire différent, avant retransmission, de la part des deux stations, évite une nouvelle collision) est de
5.12 μs
c. On suppose τ fixé à la valeur calculée à la question précédente (valeur qui figure dans la norme
802.3) ; il y a donc exactement une chance sur deux pour que se produise une seconde collision
entre les trames réémises par A et B. Calculer la probabilité pour qu'au moins quatre émissions (y
compris la tentative initiale) soient nécessaires au bon acheminement des trames, dans le cas où
seules les stations A et B sont actives.
Il y a une chance sur deux pour que se produise une nouvelle collision entre les trames réémises par A et
B ; dans ce cas, chaque station laisse s'écouler aléatoirement 0, 1, 2 ou 3 tranches de temps avant de
réémettre (si le bus est libre). La probabilité d'une nouvelle collision est donc de 1/4. Finalement, la
probabilité pour qu'au moins quatre émissions (y compris la tentative initiale) soient nécessaires au bon
acheminement des trames, est de 1/2 (échec de la première réémission) * 1/4 (échec de la seconde
réémission), soit 1/8. Note : cette formulation de la solution suppose qu'on est dans le scénario de la
question 2, et donc que la première émission a provoqué une collision.
3/4