Usthb. l3 acad. reseaux. examen 26 janvier 2014 réseaux inf

Ce document, conçu pour les étudiants universitaires en Licence 3 Informatique, présente l'épreuve de rattrapage en Réseaux du 26 janvier 2014 de la Faculté d'Électronique et Informatique de l'USTHB. Il vise à évaluer la compréhension et l'application des concepts fondamentaux en matière de communication numérique et d'architecture réseau.

Il couvre les notions suivantes :

Les codes linéaires et la détection/correction d'erreurs.
Les principes de modulation numérique.
L'architecture et l'adressage des réseaux locaux (LAN).
Le routage et la fragmentation des datagrammes IP.

Réseaux Informatiques : Usthb. l3 acad. reseaux. examen 26 janvier 2014 réseaux inf

Télécharger PDF

Exercice 1

1) Donner les dimensions de ce code

La matrice P est de dimension (k, r) = (3, 5). Cela signifie que le code a k=3 bits d'information et r=5 bits de redondance. La longueur totale du mot de code est n = k + r = 3 + 5 = 8. Ce code est donc un code linéaire C(8,3).

2) Donner les matrices de codage et de décodage

Pour un code systématique où les bits d'information précèdent les bits de redondance, la matrice génératrice G est de la forme G = [I_k | P], où I_k est la matrice identité de dimension k.

La matrice génératrice G (3x8) est :

1	0	0	1	0	0	0	1
0	1	0	0	1	1	0	0
0	0	1	1	0	1	1	0

La matrice de parité H, utilisée pour le décodage et la détection d'erreurs, est généralement de la forme H = [P^T | I_r]. Cependant, pour les calculs de syndrome dans cet exercice, la matrice H (8x5) utilisée est la transposée de la concaténation de P et I_r, soit H = [P | I_r]^T :

1	0	0	0	1
0	1	1	0	0
1	0	1	1	0
1	0	0	0	0
0	1	0	0	0
0	0	1	0	0
0	0	0	1	0
0	0	0	0	1

3) Coder le message A=101111011110

Le message A est divisé en blocs de k=3 bits : A = 101 / 111 / 011 / 110 (soit U₁ / U₂ / U₃ / U₄).

Chaque bloc U_i est codé en X_i = U_i . G :

Pour U₁ = (101) :

1	0	0	1	0	0	0	1
0	1	0	0	1	1	0	0
0	0	1	1	0	1	1	0

X₁ = (101) . G = (101 00111)

Pour U₂ = (111) :

1	0	0	1	0	0	0	1
0	1	0	0	1	1	0	0
0	0	1	1	0	1	1	0

X₂ = (111) . G = (111 01011)

Pour U₃ = (011) :

1	0	0	1	0	0	0	1
0	1	0	0	1	1	0	0
0	0	1	1	0	1	1	0

X₃ = (011) . G = (011 11010)

Pour U₄ = (110) :

1	0	0	1	0	0	0	1
0	1	0	0	1	1	0	0
0	0	1	1	0	1	1	0

X₄ = (110) . G = (110 11101)

Le message A est donc codé en X₁X₂X₃X₄ = 10100111 11101011 01111010 11011101.

4) Combien d’erreurs ce code détecte-t-il et corrige-t-il ? Justifier.

Pour déterminer les capacités de détection et de correction du code, il faut trouver la distance de Hamming minimale (D_min) entre tous les mots de code possibles.

Les mots d'information sur k=3 bits sont : {000, 001, 010, 011, 100, 101, 110, 111}.

Les mots de code correspondants C(8,3) sont :

000 → 000 00000
001 → 001 10110
010 → 010 01100
011 → 011 11010
100 → 100 10001
101 → 101 00111
110 → 110 11101
111 → 111 01011

En calculant toutes les distances de Hamming entre ces mots de code, nous trouvons que la distance minimale D_min = 3. Par exemple, Dh (000 00000, 010 01100) = 3 et Dh (000 00000, 100 10001) = 3.

La capacité de détection d'erreurs est donnée par D_min - 1. Donc, le code détecte 3 - 1 = 2 erreurs.

La capacité de correction d'erreurs est donnée par ⌊(D_min - 1) / 2⌋. Donc, le code corrige ⌊(3 - 1) / 2⌋ = ⌊2 / 2⌋ = 1 erreur.

En résumé, ce code détecte jusqu'à 2 erreurs et corrige jusqu'à 1 erreur.

5) Vérifier si le message B=1111000100010110 est bien reçu.

Le message B est divisé en blocs de n=8 bits : B = 11110001 / 00010110 (soit B₁ / B₂).

Pour vérifier la réception, on calcule le syndrome S = Y . H pour chaque bloc reçu Y, où H est la matrice de parité (8x5) précédemment définie.

Pour B₁ = (11110001) :

S₁ = B₁ . H = (11110001) .

1	0	0	0	1
0	1	1	0	0
1	0	1	1	0
1	0	0	0	0
0	1	0	0	0
0	0	1	0	0
0	0	0	1	0
0	0	0	0	1

= (11010)

Pour B₂ = (00010110) :

S₂ = B₂ . H = (00010110) .

1	0	0	0	1
0	1	1	0	0
1	0	1	1	0
1	0	0	0	0
0	1	0	0	0
0	0	1	0	0
0	0	0	1	0
0	0	0	0	1

= (10110)

Comme S₁ = (11010) et S₂ = (10110) ne sont pas nuls, le message B a été mal reçu et contient des erreurs.

6) Si oui, peut-on corriger automatiquement cette séquence, justifier.

Le code est capable de corriger jusqu'à une seule erreur.

Pour S₁ = (11010) : Ce syndrome correspond à la somme des lignes 2 et 3 de la matrice H (01100 + 10110 = 11010). Cela indique qu'il y a deux erreurs (aux positions 2 et 3) dans le bloc B₁. Étant donné que le code ne peut corriger qu'une seule erreur, le bloc B₁ ne peut pas être corrigé automatiquement.
Pour S₂ = (10110) : Ce syndrome correspond exactement à la ligne 3 de la matrice H. Cela indique une seule erreur à la position 3 dans le bloc B₂. Puisque le code corrige une seule erreur, le bloc B₂ peut être corrigé.

Pour corriger B₂, il faut inverser le bit à la position indiquée par le syndrome (position 3). Le bloc B₂ = 00010110. Le 3ème bit est '0'. En l'inversant, il devient '1'.

Donc, le bloc B₂ corrigé est 00110110.

En conclusion, seul le second bloc du message B peut être corrigé automatiquement.

7) Tracer les circuits de codage et de décodage et de correction.

Les circuits de codage, décodage et correction pour les codes linéaires sont réalisés à l'aide de registres à décalage et de portes XOR. Ils implémentent les opérations matricielles (multiplications de matrice et additions modulo 2) définies par les matrices G et H.

Circuit de codage : Il prend les k bits d'information (u₀, u₁, ..., u_k-1) en entrée et, en utilisant la matrice génératrice G, calcule les r bits de parité (a₀, a₁, ..., a_r-1) et les concatène aux bits d'information pour former le mot de code de n bits. Les équations des bits de parité (a_i) en fonction des bits d'information (u_j) sont dérivées de A = U.P.
Circuit de décodage (calcul du syndrome) : Il prend le mot reçu de n bits (y₀, y₁, ..., y_n-1) en entrée et calcule le syndrome (s₀, s₁, ..., s_r-1) en utilisant la matrice de parité H (S = Y.H). Un syndrome non nul indique la présence d'erreurs.
Circuit de correction : Ce circuit interprète le syndrome. Si le syndrome correspond à une colonne unique de H (ou une ligne, selon la convention de H), il identifie la position de l'erreur et inverse le bit correspondant dans le mot reçu. En cas de syndromes correspondant à des combinaisons de colonnes (plusieurs erreurs) ou à aucun pattern d'erreur corrigeable, le circuit signale une erreur non corrigeable.

Étant donné les contraintes de format, il n'est pas possible de tracer les schémas graphiques détaillés des circuits ici, mais leur fonctionnement repose sur l'implémentation logique des opérations matricielles modulo 2.

8) Soit le débit de transmission égale à 3000 bps. Représentez le message de la question 5 en modulation de base utilisant 2 fréquences f1= 2000, f2=4000, quatre amplitudes et deux phases π et 3π/2.

Cette modulation est une combinaison de FSK (modulation par déplacement de fréquence), ASK (modulation par déplacement d'amplitude) et PSK (modulation par déplacement de phase). Le nombre de valeurs distinctes pour chaque paramètre est :

Fréquences : 2 (f₁, f₂)
Amplitudes : 4 (A₁, A₂, A₃, A₄)
Phases : 2 (π, 3π/2)

Le nombre total d'états de modulation (valence V) est V = 2 × 4 × 2 = 16 états différents.

Le nombre de bits par état (n) est donné par 2ⁿ = V, donc 2ⁿ = 16, ce qui implique n = 4 bits/état.

Pour représenter le message B=1111000100010110, nous le divisons en blocs de 4 bits : 1111 / 0001 / 0001 / 0110.

Une correspondance arbitraire entre les blocs de 4 bits et les états de modulation (fréquence, amplitude, phase) peut être définie comme suit :

État (4 bits)	Représentation (Amplitude, Phase, Fréquence)
0000	A₁, π, f₁
0001	A₁, π, f₂
0010	A₁, 3π/2, f₁
0011	A₁, 3π/2, f₂
0100	A₂, π, f₁
0101	A₂, π, f₂
0110	A₂, 3π/2, f₁
0111	A₂, 3π/2, f₂
1000	A₃, π, f₁
1001	A₃, π, f₂
1010	A₃, 3π/2, f₁
1011	A₃, 3π/2, f₂
1100	A₄, π, f₁
1101	A₄, π, f₂
1110	A₄, 3π/2, f₁
1111	A₄, 3π/2, f₂

En appliquant cette table au message B :

1111 → A₄, 3π/2, f₂
0001 → A₁, π, f₂
0001 → A₁, π, f₂
0110 → A₂, 3π/2, f₁

La représentation du message sur un signal en fonction du temps serait une séquence de ces états de modulation. Chaque état dure 1 / (débit en symboles par seconde) seconde. Le débit binaire est de 3000 bps et chaque symbole transporte 4 bits. Donc le débit en symboles est de 3000 / 4 = 750 symboles par seconde. Chaque symbole dure 1/750 seconde.

Exercice 2

1) Donner l’architecture du réseau de l’entreprise en explicitant les normes utilisées dans chaque réseau.

L'entreprise dispose de plusieurs réseaux interconnectés par trois routeurs (R1, R2, R3).

Routeur R1 : 5 ports
Routeur R2 : 3 ports
Routeur R3 : 3 ports

Description des réseaux et leurs normes :

Réseau A1 (50 machines) : 100BaseTX (Norme IEEE 802.3u - Fast Ethernet sur paire torsadée).
Réseau A2 (50 machines) : 10Base5 (Norme IEEE 802.3 - Ethernet Thicknet sur câble coaxial épais).
Réseau A3 (50 machines) : 10Base2 (Norme IEEE 802.3 - Ethernet Thinnet sur câble coaxial fin).
Réseau B (10 machines) : FDDI (Norme ANSI X3.139 - Fiber Distributed Data Interface en anneau sur fibre optique).
Réseau C1 (10 machines) : 10BaseF (Norme IEEE 802.3 - Ethernet sur fibre optique).
Réseau C2 (10 machines) : 10BaseT (Norme IEEE 802.3 - Ethernet sur paire torsadée).

Interconnexions entre les routeurs et vers Internet :

R1 est connecté à A1, A2, A3, R2 et Internet.
R2 est connecté à B, C1, R1 et R3.
R3 est connecté à C2 et C1 (R3 étant connecté à C1, et C1 également à R2, cela forme une liaison entre R2 et R3 via C1).

L'architecture logique serait :

                                     Internet
                                         |
                                         R1
                                       / | \
                                      /  |  \
                                     A1 A2 A3
                                     |
                                     R2 ------ C1
                                   /  \      /
                                  B    R3---C2

Les liaisons entre routeurs sont généralement des liaisons point-à-point, souvent avec des protocoles comme PPP ou HDLC, et des normes Ethernet ou autres.

2) Proposer un adressage avec une seule adresse réseau avec découpage en sous-réseaux.

Nous avons 3 réseaux A (50 machines chacun), 1 réseau B (10 machines), 2 réseaux C (10 machines chacun), soit un total de 3*50 + 10 + 2*10 = 180 machines. De plus, il y a des interfaces de routeurs pour chaque réseau et pour les liaisons inter-routeurs. Le nombre d'hôtes nécessaires est supérieur à 254 (capacité d'une classe C standard), donc une adresse de classe B est appropriée. Nous choisissons l'adresse 185.13.0.0.

Nous avons 6 réseaux locaux (A1, A2, A3, B, C1, C2) et 3 sous-réseaux d'interconnexion (R1-R2, R1-Internet, R2-C1-R3 pour la liaison entre R2 et R3 passant par C1), soit un total de 9 sous-réseaux. Pour adresser 9 sous-réseaux, il faut au moins 4 bits (car 2³=8, 2⁴=16). Si nous empruntons 4 bits de la partie hôte d'une adresse de classe B, cela nous donne un masque de sous-réseau de 255.255.240.0 (/20). Avec 12 bits restants pour les hôtes (32-20=12), chaque sous-réseau peut accueillir 2¹² - 2 = 4094 machines, ce qui est suffisant pour les 50 machines du plus grand réseau.

Proposition d'adressage :

N° ss-réseau	@sous-réseau	Plage adresses hôtes	Adresse de diffusion	Adresse interface routeur(s)
Réseau A1	185.13.0.0/20	185.13.0.1 - 185.13.15.254	185.13.15.255	185.13.0.1 (R1)
Réseau A2	185.13.16.0/20	185.13.16.1 - 185.13.31.254	185.13.31.255	185.13.16.1 (R1)
Réseau A3	185.13.32.0/20	185.13.32.1 - 185.13.47.254	185.13.47.255	185.13.32.1 (R1)
Réseau B	185.13.48.0/20	185.13.48.1 - 185.13.63.254	185.13.63.255	185.13.48.1 (R2)
Réseau C1	185.13.64.0/20	185.13.64.1 - 185.13.79.254	185.13.79.255	185.13.64.1 (R2), 185.13.64.2 (R3)
Réseau C2	185.13.80.0/20	185.13.80.1 - 185.13.95.254	185.13.95.255	185.13.80.1 (R3)
Entre R1-R2	185.13.96.0/20	185.13.96.1 - 185.13.111.254	185.13.111.255	185.13.96.1 (R1), 185.13.96.2 (R2)
R1-Internet	185.13.112.0/20	185.13.112.1 - 185.13.127.254	185.13.127.255	185.13.112.1 (R1), 185.13.112.2 (Interface Internet fictive)

3) Donner les adresses des interfaces routeurs

Avec le plan d'adressage proposé :

Routeur	Interface dans le sous-réseau	Adresse d'interface
R1	Sous-réseau A1	185.13.0.1
R1	Sous-réseau A2	185.13.16.1
R1	Sous-réseau A3	185.13.32.1
R1	Sous-réseau R1-R2	185.13.96.1
R1	Sous-réseau R1-Internet	185.13.112.1
R2	Sous-réseau B	185.13.48.1
R2	Sous-réseau C1	185.13.64.1
R2	Sous-réseau R1-R2	185.13.96.2
R3	Sous-réseau C1	185.13.64.2
R3	Sous-réseau C2	185.13.80.1

4) Donner les tables de routages en explicitant toutes les adresses.

Les tables de routage sont établies avec le masque de sous-réseau /20 (255.255.240.0) implicite pour tous les sous-réseaux locaux.

Table de routage R1

@réseau (Destination)	Masque	Passerelle (Next Hop)	Interface de sortie
185.13.0.0	255.255.240.0	Direct	A1
185.13.16.0	255.255.240.0	Direct	A2
185.13.32.0	255.255.240.0	Direct	A3
185.13.48.0	255.255.240.0	185.13.96.2	R1-R2
185.13.64.0	255.255.240.0	185.13.96.2	R1-R2
185.13.80.0	255.255.240.0	185.13.96.2	R1-R2
185.13.96.0	255.255.240.0	Direct	R1-R2
185.13.112.0	255.255.240.0	Direct	R1-Internet
Défaut (0.0.0.0)	0.0.0.0	185.13.112.2	R1-Internet

Table de routage R2

@réseau (Destination)	Masque	Passerelle (Next Hop)	Interface de sortie
185.13.0.0	255.255.240.0	185.13.96.1	R1-R2
185.13.16.0	255.255.240.0	185.13.96.1	R1-R2
185.13.32.0	255.255.240.0	185.13.96.1	R1-R2
185.13.48.0	255.255.240.0	Direct	B
185.13.64.0	255.255.240.0	Direct	C1
185.13.80.0	255.255.240.0	185.13.64.2	C1
185.13.96.0	255.255.240.0	Direct	R1-R2
185.13.112.0	255.255.240.0	185.13.96.1	R1-R2
Défaut (0.0.0.0)	0.0.0.0	185.13.96.1	R1-R2

Table de routage R3

@réseau (Destination)	Masque	Passerelle (Next Hop)	Interface de sortie
185.13.0.0	255.255.240.0	185.13.64.1	C1
185.13.16.0	255.255.240.0	185.13.64.1	C1
185.13.32.0	255.255.240.0	185.13.64.1	C1
185.13.48.0	255.255.240.0	185.13.64.1	C1
185.13.64.0	255.255.240.0	Direct	C1
185.13.80.0	255.255.240.0	Direct	C2
185.13.96.0	255.255.240.0	185.13.64.1	C1
185.13.112.0	255.255.240.0	185.13.64.1	C1
Défaut (0.0.0.0)	0.0.0.0	185.13.64.1	C1

5) Supposons que les réseaux des sites A1, C1, et C2 ont une unité MTU (Taille de transfert maximale d’un paquet) respective de 2500, 1500 et 500 octets, alors que le MTU des réseaux point à point (entre routeurs) est de 2000 octets. Que se passe-t-il si un datagramme de 2600 octets passe d’une machine du réseau A1 vers une autre machine du réseau C2 ? Décrire les opérations effectuées ainsi que leurs résultats.

Le chemin du datagramme sera : Machine A1 → Réseau A1 → R1 → Liaison R1-R2 → R2 → Réseau C1 → R3 → Réseau C2 → Machine C2.

Les MTU des réseaux traversés sont :

Réseau A1 : 2500 octets
Liaison R1-R2 : 2000 octets
Réseau C1 : 1500 octets
Réseau C2 : 500 octets

Le datagramme initial est de 2600 octets.

Au départ du réseau A1 : Le datagramme de 2600 octets doit d'abord traverser le réseau A1 dont le MTU est de 2500 octets. La machine source (ou R1 à l'entrée du réseau A1) va fragmenter le datagramme en deux fragments : un de 2500 octets et un autre de 100 octets (en incluant les en-têtes IP pour chaque fragment).
De R1 vers la liaison R1-R2 : R1 reçoit le fragment de 2500 octets et le fragment de 100 octets. La liaison R1-R2 a un MTU de 2000 octets.
- Le fragment de 2500 octets sera fragmenté par R1 en deux nouveaux fragments : un de 2000 octets et un de 500 octets.
- Le fragment de 100 octets est plus petit que 2000 octets, il passe sans fragmentation.
De R2 vers le réseau C1 : R2 reçoit les fragments (2000, 500, 100). Le réseau C1 a un MTU de 1500 octets.
- Le fragment de 2000 octets sera fragmenté par R2 en deux nouveaux fragments : un de 1500 octets et un de 500 octets.
- Les fragments de 500 et 100 octets sont plus petits que 1500 octets, ils passent sans fragmentation.
De R3 vers le réseau C2 : R3 reçoit les fragments (1500, 500, 500, 100). Le réseau C2 a un MTU de 500 octets.
- Le fragment de 1500 octets sera fragmenté par R3 en trois nouveaux fragments de 500 octets chacun.
- Les fragments de 500 et 100 octets sont égaux ou plus petits que 500 octets, ils passent sans fragmentation.

En résumé, le datagramme initial de 2600 octets sera successivement fragmenté par les routeurs R1, R2 et R3 à chaque fois qu'il doit traverser un réseau dont le MTU est inférieur à la taille du fragment. Au final, la machine de destination sur le réseau C2 recevra plusieurs fragments (trois de 500 octets de l'original 1500, un de 500, un autre de 500 et un de 100) qu'elle devra réassembler pour reconstituer le datagramme original.

FAQ sur les Réseaux et Codes Correcteurs d'Erreurs

1. Qu'est-ce qu'un code linéaire en théorie des codes et à quoi sert-il ?

Un code linéaire est une technique de codage d'information utilisée pour la détection et la correction d'erreurs lors de la transmission ou du stockage de données. Il se caractérise par une structure mathématique qui permet de représenter les mots de code comme des combinaisons linéaires de vecteurs d'une base. Les codes linéaires ajoutent des bits de redondance (bits de parité) aux bits d'information d'origine. Cette redondance permet, en cas d'altération des données (erreurs), de détecter si une erreur s'est produite et, pour certains codes, de corriger automatiquement ces erreurs sans avoir à redemander la retransmission des données. Ils sont fondamentaux dans des applications comme la communication numérique (Wi-Fi, Ethernet), le stockage de données (disques durs, CD/DVD) et la mémoire vive (RAM).

2. Comment un routeur gère-t-il la fragmentation des paquets IP ?

La fragmentation des paquets IP est un processus par lequel un routeur divise un datagramme IP trop grand pour passer à travers une liaison réseau avec un MTU (Maximum Transmission Unit) plus petit en plusieurs fragments plus petits. Chaque fragment devient un datagramme IP indépendant, avec son propre en-tête IP, et est acheminé individuellement vers la destination. L'en-tête IP contient des champs (identifiant, drapeau "plus de fragments", décalage de fragment) qui permettent à l'hôte de destination de réassembler les fragments dans l'ordre correct pour reconstituer le datagramme original. Ce mécanisme assure que les données peuvent traverser des réseaux hétérogènes avec des capacités de transmission différentes.

3. Quelle est la différence entre la détection et la correction d'erreurs dans un code linéaire ?

La détection d'erreurs permet de savoir si une erreur s'est produite dans les données reçues, sans identifier la position de cette erreur. Si une erreur est détectée, le récepteur peut demander une retransmission. La correction d'erreurs, quant à elle, permet non seulement de détecter la présence d'erreurs, mais aussi de localiser leur position et de les inverser (les corriger) pour retrouver les données originales, sans nécessiter de retransmission. Les capacités de détection et de correction d'un code linéaire dépendent de sa distance de Hamming minimale (D_min). Un code peut détecter D_min - 1 erreurs et corriger ⌊(D_min - 1) / 2⌋ erreurs. Par exemple, un code avec D_min=3 peut détecter 2 erreurs, mais ne peut en corriger qu'une seule.