51
Réseaux Locaux et Interconnexions (RLI S6) LICENCE 3 INFO Pascal Mérindol : [email protected] http://www-r2.u-strasbg.fr/~merindol/

Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

  • Upload
    others

  • View
    2

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

Réseaux Locaux et Interconnexions (RLI S6)

LICENCE 3 INFOPascal Mérindol : [email protected]

http://www-r2.u-strasbg.fr/~merindol/

Page 2: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

‣ CM (14h) : Mardi, 16h - 18h, C6

‣ TD (10h) : Mardi, 14h - 16h, C6

‣ TP (10h) : Mercredi, 13h30 - 15h30, T21

‣ Planning : https://ent.u-strasbg.fr/ (+ http://www-mathinfo.u-strasbg.fr/)

‣ onglet Services Pratiques -> S'organiser -> Emplois du temps (ADE)

‣ onglet UDS 2010-2011, Etudiants -> MATH-INFO -> L3 Informatique 3eA -> 1er Semestre -> S6-A

➡ Calendrier : Semaine 7 (1-7): néant

Semaine 8 : 1 CM - 1 TP

Semaine 9: 1 CM - 1 TP

Semaine 10: 1 TD - 1 TP

Semaine 11: 1 CM - 1 TD

Semaine 1 (13-19) : 1 CM

Semaine 2: néant

Semaine 3: 1 CM - 1 TD

Semaine 4 (4-10) : 1 TD - 1 TP

Semaine 5: 1 CM - 1 TP

Semaine 6: 1 CM - 1 TD

Septembre Octobre Novembre

INFOS PRATIQUES

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Page 4: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

• Présentation de l'architecture d'un réseau d'entreprise.

• Le réseau local : protocoles d'accès aux réseaux locaux (CSMA/CD, CSMA/CA, anneau à jeton, etc.), norme IEEE 802,

• les composants d'un réseau local (câblage et systèmes de câblage, répéteurs, ponts, commutateurs, analyseurs de trames).

• L'interconnexion de réseaux au niveau trame : les ponts, le Spanning Tree Protocol et ses extensions. Les VLAN.

• L'interconnexion de niveau paquet : le protocole IPv4 (adressage IP et masques de sous-réseaux, protocoles ARP et ICMP, DHCP) et IPv6. Le routage IP, étude du protocole OSPF et mise en oeuvre.

Contenu officiel

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Page 5: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

I. Introduction aux LANs

II. Couche liaison: méthodes d’accès au medium (~ 4h)

III. Ponts: inter-connexion au niveau trame (~ 4h)

IV. Routeurs: inter-connexion au niveau paquet (~ 5h)

Plan du cours

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Page 6: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

Le modèle OSIApplication

SessionPrésentation

TransportRéseauLiaisonPhysique

ApplicationSession

Présentation

TransportRéseauLiaisonPhysique

RéseauLiaisonPhysique

RéseauLiaisonPhysique

1m 10m 100m 1km 10km 100km 1000km

PAN: Réseau personnel

MAN: Réseau

Métropolitain

WAN: Réseau longue distance

LAN:Réseau local

Différentes échelles

Page 7: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

Différents composants

Routeur Couche 3 du modèle OSI (réseau) Table de routage Commute les paquets d'une interface vers une autre

Commutateur Couche 2 du modèle OSI (liaison de données) associe des adresses MAC avec des ports correspondants

Concentrateur permet la connexion de plusieurs appareils sur une même ligne de

communication

Différents supports physiques

Filaires

Fibres optiquesL’air…

Page 8: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

Topologies et échelles

Pajek

4 Niveaux:‣CANAL PARTAGE‣PONTS/SWITCHS‣ROUTEURS INTRA-DOMAINE (OSPF, IS-IS)‣ROUTEURS INTER-DOMAINE (BGP)

Page 9: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

LAN : Local Area NetworkConcept apparu au début années 80

Local : quelques mètres à quelques kilomètresDistances réduites (10m - 1km)

débits élevés à moindre coût infrastructure privée

• moins de contraintes réglementaires• propriétaire du réseau = propriétaire des murs

En général, réseau d’égal à égal Toute station communique avec toute autre

Réseaux Locaux

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Page 10: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

Objectifs & Contraintes LAN ↔ multiplexeur distribué Liaison fiable Partage équitable Connectivité transparente Extensible (débit, nombre de machines)

… et à faible coût (installation, maintenance)

➡ Le problème majeur est l’accès au médium !

Concurrence provoque des collisions !Comment garantir l’équité et temps d’attente limité…?

➡ Méthode d’accès au medium ↔ Couche Liaison - MAC : Medium Access Control

«Qui parle quand ?»L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Page 11: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Méthodes d’accès

Méthodes statiques Multiplexage fréquentiel ou temporel pas adapté au débit variable: gachis si rien à émettre

Méthodes dynamiques centralisées ( RELATION MAITRE-ESCLAVE )Le maitre donne le droit à la parole extensibilité et fiabilité ?

Méthodes dynamiques distribuées✓ préventives (pas de conflit) : JETON / TOKEN✓ curatives (résolution des conflits) : PROBABILISTE

‣Déterministe : «On parle quand on a le droit»

‣Concurrentiel : «On parle quand on le veut»

‣Hybride : «On parle quand on le veut (~peut), sauf si personne ne s’entend ...alors on s’organise de manière déterministe»

Page 12: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

‣ Préventives : (déterministe) Token Ring (anneau physique) Token Bus (anneau logique)

‣ Curatives : (concurrentiel) Aloha CSMA CSMA/CD CSMA/CA

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Méthodes d’accès

Page 13: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Anneau à jeton - Généralités Le jeton donne droit à la parole D’un point de vue architectural, les stations sont organisées sous la forme

d’un cycle uni- ou bi-directionnel Chaque station relaie les trames vers la suivante dans l’anneau

Le délai dépend de la longueur du cycle

3 modes :• 1- Émission – trame locale• 2- Répétition – chaque bit reçu est ré-émis après un court délai• 3- Répétition + Lecture Emeteur

Recepteur

In Out

In Out

Out In

In

Out 1

23

Page 14: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Le jeton Il s’agit d’une trame particulière, en général unique, en

transit sur l’anneau

Une station désirant émettre :

I. reste en mode répétition, attend passage du jetonII. « capture » le jetonIII. passe en mode émission et émet trame (s)IV. (attend éventuellement ~ acquittement)V. réémet jeton puis repasse en mode répétition

Seul un jeton en circulation : «le micro»

Page 15: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Capture et Adressage Le jeton est capturée «à la volée» :

•Le rème bit du jeton est différent de celui d’une trame normale•Une station doit donc «mémoriser» r bits, et suivant la valeur du dernier :

๏ Passe en mode répétition (ce n’est pas le jeton)๏ Passe en mode émission, puis relâche le jeton

chaque trame subit un délai d’au moins r bits

• Adressage :

• Le jeton n’est pas adressé car capturé à tour de role• Trames de données sont adressées (src+dst)• Si (dst=mon adresse) alors réception

Page 16: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Rotation du jeton Paramètres

• D : Débit• r (nb de bits) : délai répétition en bits par station (r/D en temps)• T : temps maximum d’émission en une fois = L/D

(L, nombre bits émis/ D, débit ~ durée capture jeton )• p : temps propagation total (dépend de la distance physique)• N : nombre de stations

‣ Capacité théorique de l’anneau et temps d’attentebits en propagation : D.pbits en répétition : N.rTotal : D.p + N.r

Réseau inactif (aucune demande) entre 0 et (D.p + N.r) /D : [0, p+N.r/D] moyenne 1/2(p + N.r/D) (moitié de tour, faible)

Ex: réseau métropolitain rapide (FDDI / Fiber Distributed Data Interface)– D = 100Mb/s, N =100, p = 500 µs => 50 000 + 100.r bits

Réseau actif : au pire~ p + N. T = p + N*L/DEx: L = 1 trame de 4 Ko à 4Mb/s ➾ T = 8 ms, 100 stations N.T = 800 ms.

Remarque: borne sup. => garantie de délai

Page 17: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Fiabilité Coupure d’un lien

• rebouclage (double anneau FDDI), rebouclage interne (étoile) Panne station => coupure 2 liens Perte jeton

• erreur de transmission, coupure temporaire anneau, panne possesseur du jeton arrêt du fonctionnement

Perte jeton: Solution « centralisée » vs. « distribuée »• élire une (seule) station : le moniteur• détection de perte via le moniteur basée sur délai de rotation max. du jeton• moniteur génère nouveau jeton• problème de la panne du moniteur ? (surveiller et élire nouveau moniteur ?)

...VERSUS... toutes stations surveillent jeton (délai max. rotation)

en cas de perte:• élection de celui qui génère nouveau jeton• trame spéciale avec identité station• seule meilleure identité fait un tour complet

Page 18: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

Avantages :+ garanties sur temps attente max+ garanties sur débit minimum+ possibilité priorité : QoS

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Token Ring (802.5), conclusion L’attente du jeton dépend de la charge et de L

Adapter L en fonction de la charge :Forte charge : L petit

Peu de données émise à chaque capture du jeton, délai d’attente faible pour favoriser les applications interactives

Faible charge : L grand Augmentation du débit mais temps d’attente plus long

• Le système est équitable car pas de famine si L est respecté, • possibilité de système à priorité/réservation pour avantager certaines

stations (mais risque de famine).

Inconvénients : - topologie physique anneau : fiabilité ?- # stations augmente

➡délai augmente et fiabilité diminue

Page 19: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Token Bus (802.4) Organisation en anneau logique

• fonction successeur {S1,…,Sn} :succ(Si) = si i < n alors Si+1 sinon S1 fsi

Jeton adressé circulant sur l’anneau• Si envoie jeton à succ(Si)

Toute station « voit » le jeton (bus) mais seul le destinataire Si+1 « capture » le jeton

• Lorsque Si+1 reçoit le jeton, soit il émet ses trames et transmet le jeton, soit il transmet le jeton directement

• Pas de mode répétition

Pas de problème de panne physique mais la perte de jeton est problématique :Sur un bus tout le monde peut surveiller la circulation du jeton

• absence jeton et trame données (silence) perte jeton et/ou panne station• si Si ne ré-émet pas le jeton, Si-1 peut lui renvoyer (perte)• si pas de résultat (panne Si ), Si-1 peut l’envoyer à Si+1

nécessite de connaître successeur du successeur écoute du jeton par exemple

Fiabilité:

Page 20: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

Token Bus : insertion de station

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Comment ajouter une station ? L’ insertion dans l’anneau logique implique la modification de la fonction successeur... Elle ne peut se faire connaître car on ne lui donne pas la parole (le jeton) idée :

- nouvel arrivant écoute bus- à intervalle régulier, le possesseur du jeton Si envoie requête (broadcast) du type « Y a-t-il un (des) nouveau(x) » ?

Nouveau répond avec son identité X Si lui envoie succ(Si) et son nouveau succ est X X s’insère donc entre Si et Si+1 Si plusieurs nouveaux en même temps ?

Collision ! ré-essayer après délai aléatoire : voir CSMA/CD

Possibilité de garanties délai et débit– similaire anneau jeton (déterminisme)

rotation jeton lente: - doit être ré-émis par chaque station ex: 200 bits, 10 Mb/s, 100 stations => 2ms

Moins sensible panne station– pas de rebouclage nécessaire

Difficulté insertion station– peu adapté réseaux dynamiques

Synthèse :

Page 21: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Aloha

«Bonjour» en Hawaïen, ALOHAnet Hawaii University 1970 Contexte : réseau radio

• Stations partagent le même canal radio ➾ émissions « simultanées » = collision

• Algorithme:si trame à émettre alors émettre trame

Délai avant émission nul Si collision : trames perdues

ré-émission prise en charge par couche supérieure fiable (par exemple TCP)

Délai élevé en cas de collision, perte bande passante

Page 22: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Perfomances AlohaHypothèses :

Un nombre arbitrairement grand de stations et des émetteurs indépendants• D = débit maximal théorique en trames/s , par exemple :

1 Mb/s, trames de L = 1000 bits : D = 1000 trame/s, durée émission trame t = 1ms• G = charge totale émissions + ré-émissions

– G = nombre de trames (ré)-émises /D– ex: 100 émetteurs envoient 8 trames/s => G = 0,8

Débit utile en fonction charge :• période de contention dure 2t :

[ t0 - t , t0+ t ] si la trame est émise en t0• Proba (émission réussie) = proba (0 émission en 2t)• Débit utile = G e-2G (cf. théorie des files d’attente et Distribution de Poisson)• Débit utile maximal pour G = 1/2 et vaut 1/2e = 0,184

Exemple: G=1/2 => 500 trames/s dont 184 « passent »G < 1/2 => moins de collisions mais moins de débitG > 1/2 => collisions augmentent

• Si G tend vers l’infini, débit utile tend vers 0

Page 23: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Problème Aloha•Nombre de collisions croissant avec la charge

peut-on en éviter tout ou partie ?•Durée d’une collision sur une trame complète

peut-on réduire cette durée ?•Durée de réparation d’une collision

• retransmission par une couche supérieure• délai de garde (HDLC, TCP, …)

peut-on réduire ce délai ?

Amélioration possible :• diminuer période de contention !• Aloha en tranche (ou discrétisé)

Emetteurs synchronisés : 1 top tous les t (= tranche)– Émetteur(s) n’envoie(nt) qu’à un top période de contention de t– Débit utile (rendement ) = G e –G maximum atteint pour G = 1– rendement max 1/e = 0,368 (double d’Aloha pur)

Page 24: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

CSMA Carrier Sense Multiple Access

• Réseau à diffusion et écoute du signal• Principe :

émetteur écoute le canal avant d’émettre• Algorithme :

Si trame à émettreSi canal occupé«attendre»recommencerSinon émettre trame

Page 25: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

CSMA• Plusieurs stratégies suivant politique d’attente

Emission dès que le canal est libre : CSMA persistant - risque d’accumuler les collisions après une trame+ délais courts deux stations attendent qu’une troisième ait fini son émission Attendre un délai aléatoire avant d’écouter de nouveau : CSMA non persistant avantage et inconvénients inversés

• Collisions toujours possiblesEmissions « simultanées » au temps de propagation près quelques dizaine de μs dans ethernet (contention) alors qu’émission de 10 000 bits à 10 Mb/s = 1 ms

• Temps perdu pendant les collisionsEmission d’une trame complète amélioré par CSMA/CD

Page 26: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

CSMA/CD (802.3)• CSMA with Collision Detection

CSMA avec détection de collision (par les émetteurs)

• Suppose que physiquement un émetteur émet une trame et écoute simultanément le signal Le principe : signal émis ≠ signal reçu collision

• Algorithme :

si trame à émettreattendre canal libre (suivant CSMA persistant ou non)commencer à émettre la trame

tant que émission non terminéesi collision détectée

arrêter émissionattendre puis recommencer au début

Page 27: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

• A priori s’il y a une collision :Elle est détectée après au plus 2t (t = temps de propagation aller)– au bout de t toutes les stations reçoivent signal

émettent au plus tard en t- ε– signal collision revient en au plus t (propagation retour) total < 2t– nécessite que le premier soit encore en émission

• Réduction temps perdu par collision ( ~ 2t)– intéressant si 2t << temps émission trame complète

• collision détectée rapidement ré-émission plus rapide

A

B

t

Condition: L/D > 2t

L/D

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

CSMA/CD (802.3)

L = TAILLE TRAMED = DEBIT

t = temps de propagation

Page 28: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

• Combien de temps attendre avant ré-émission ?– délais fixes identiques => collision se répète– délais fixes différents => système de priorités

Délais aléatoires✓intervalle court : attente faible, répétition collision fréquente✓intervalle long : l’inverse

Binary Exponential Backoff :

– à la kème tentative de retransmission d’une trame :

Tirer i aléatoirement dans [0, 2max(k,10)[Attendre un temps i . T (T est l’unité de temps > 2t)

-Collision se répète si et seulement parmi les «i» tirés par les émetteurs, deux d’entre eux ont tiré la (même) valeur minimale-Probabilité de collision décroit avec k croissant (k<16)

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

CSMA/CD - attente

Page 29: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

CSMA/CD - attente

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

CSMA/CD - synthèse

Avantages/Inconvénients :+ Attente nulle si réseau peu chargé (comme Aloha)+ Collisions limitées et retransmission rapide (niveau LAN)

- Pas de garantie de délai exemple: T = 50 μs, 210. T = 51,2 ms

- Pas de garantie que la trame sera transmise !!- Pas de garantie de débit minimum

+ Mais en pratique fonctionne très bien (ethernet)- si peu d’émetteurs- ou réseau non saturé (exemple 30%)

Page 30: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

CSMA/CA (WiFi 802.11) CSMA/CD pas toujours possible

• impossibilité émettre/écouter simultanément ou• signal autre émetteur non audible

– exemple du terminal caché dans les réseaux sans fil distance trop grande entre émetteurs ou obstacles

CSMA/CA Collision Avoidance« évitement de collision »

a b c

Terminal caché

Le poste a n’entend pas ccollisions

a b c

Terminal exposé

d

c entend a (alors il n’émet pas) alors qu’il pourrait parler à d

Page 31: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

CSMA/CA (MACA 802.11)

Multiple Access with Collision Avoidance• émetteur potentiel envoie trame RTS (Ready to Send) avec taille trame à

émettre + destinataire tout ceux à sa portée sont au courant

• récepteur (s’il a reçu RTS) envoie trame CTS (Clear To Send) (taille trame) tout ceux à sa portée sont au courant

• si émetteur reçoit CTS envoie trame • récepteur envoie acquittement dans la foulée• si échec (pas de CTS) : recommencer plus tard (aléatoire comme CSMA/CD)

améliorations : écouter avant d’émettre envoyer courte trame d’acquittement (remplace CD)

Page 32: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

Quelques exemples (depuis 1985): 802.3 : CSMA/CD « ethernet »802.4 : Token Bus - Bus à jeton802.5 : Token Ring - Anneau à jeton

Plusieurs débits et supports

802.11 : Wireless « WiFi » 802.15 : Wireless Personal Area Networks « Bluetooth »

802.16 : Broadband

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

LAN normalisés IEEE802

Work in Progress : Réseaux ad-hocRéseaux de capteurs

Page 33: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

LAN normalisés IEEE802 Architecture IEEE802

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

‣La couche liaison (2 de l’ISO)➡ découpée en deux sous-couches

• couche MAC : Medium Access Control définit une méthode d’accès (CSMA, …)

• couche LLC : Logical Link Control / multiplexage et controle d’erreurcommune aux différentes couches Macdéfinit un protocole de liaison : lien « virtuel » entre deux stations➡ 3 types de protocole suivant le service :✓LLC type 1 : datagramme non fiable (le + utilisé en pratique)✓LLC type 2 : avec connexion, fiable✓LLC type 3 : sans connexion, avec acquittements

‣Réseau local normalisé défini par:➡ une méthode d’accès (couche MAC)➡ une couche physique

• caractérisée par plusieurs paramètres:✓support (paire torsadée, coaxial, fibre, canal radio)✓débit✓encodage (adapté au support et au débit) => Ethernet = Manchester différentiel ✓paramètres du réseau (distance, nombre équipements, règle 5-4-3, …)

Page 34: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

Architecture IEEE802

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Management, bridging, ... 802.1

802.2LLC

...MAC1 MAC2 MAC3 MACn

Phy Phy Phy Phy

802.3/4/5...

Couche 2

Couche 1

Page 35: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

CSMA/CD - IEEE 802.3– Première norme en 1985

• norme actuelle > 2600 pages– Basé sur Ethernet (Digital/Intel/Xerox = DIX),

• avec quelques différences (à un champ près, compatilibité !)– Evolution constante débits/supports (2Mb => 10Gb? / 10base2 => 1000baseT, ...)– Modèle en bus

• trames (train de bits) circulent dessus : une à la fois, sinon collisions !

Ethernet est un réseau :-égalitaire (partage de l’accès équitable)-probabiliste (non déterministe)-sans chef d’orchestre (non centralisé)

Page 36: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

TRAME IEEE 802.3Format d’une trame :

préambule SFD @dst @srclongueur ou type

DATA FCS

Chaque champ occupe un nombre entier d’octets :

-préambule : synchronisation 7 octets 10101010 (début peut être perdu)-SFD (Start of Frame Delimiter) : début de l’info utile 1 octet 10101011

(exemple en 10baseT, dépend de la couche physique)-adresse destination : 6 octets-adresse source : 6 octets-longueur ou type : 2 octets-DATA (données) : 46 à 1500 octets (y compris bourrage/padding éventuel)

-FCS (Frame Check Sequence) : 4 octets ➾ code polynomial détecteur d’erreursX32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X1 + 1

Page 37: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Adressage IEEE 802.3• Codées sur 6 octets « adresses MAC »

– premier bit (= bit poids faible du 1er octet)• 0 : adresse individuelle (= adresse d’interface réseau classique)• 1 : adresse de groupe multicast (concerne seulement la destination)

– ex : 01:80:c2:00:00:00 (spanning tree)– cas particulier ff:ff:ff:ff:ff:ff broadcast

– deuxième bit• 1 : adresses allouées localement, ou non universelles

– Ex : adresses multicast• 0 : adresses universelles ➾ 24 bits fabricant, 24 bits numéro de série

– ex 00:0d:93:c8:91:9c «00:0d:93» = Apple– voir http://standards.ieee.org/regauth/oui/oui.txt– adresse MAC non volatile sur la carte

Longueur de la trame (hors préambule) :– garantir Lmin/D > 2t (car CSMA/CD)

• choix Lmin = 64 octets => 2t < 51,2 µs à D = 10Mb/s : limite taille réseau• si données < 46 octets : padding / bourrage

Même champ peut coder le type (hérité de l’ethernet initial ≠ 802.3)• identifie protocole supérieur (~Couche 3)• Ex (hexa) : 0800 : IPv4, 0806 : ARP, 88DD : IPv6 ➾ http://www.iana.org/assignments/ethernet-numbers• valeurs disjointes avec longueurs possibles

➾ cohabitation possible entre plusieurs types de trames dans le même réseau

Page 38: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Encapsulation 802.2 LLCComment choisir le bon service (trame de service) ?

APPLIIP

LLCMACPHYS

APPLIIP/APPLETALK

LLCMACPHYS

DSAP : Destination Service Acces point (1 byte)bit de poids faible : Individual/Group pour le SAP de destination

SSAP : Source Service Acces point (1 byte)bit de poids faible : Command/Reponse pour le SAP source indique comment interprèter le champs "CONTROL"

CONTROL : De nombreuses trames de service (1-2 byte)permettent de gérer les trois types de service Ethernet/IP n'utilisent que trois types de trames (LLC type 1) :

UI : cette trame est un simple Datagramme (que des données)XID : Echange Identification (classe supportée, ...)TEST : vérifier l'accessibilité, découvrir la route

I/G DSAP C/R SSAP CONTROL

SAP : Service Access Point

Page 39: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

SNAP : extension de LLC

Problème: L'espace est insuffisant pour tous les types de SAP !En particulier protocoles supérieurs famille IP

•En-tête complémentaireExtension de LLC pour utiliser "OUI" et "EtherType"

•SNAP Sub-Network Access Protocol

Par défaut : "Class 1" (LLC type 1) et trame UI

1 octet 1 octet 1 octet 3 octets 2 octets 1402 octets max

En-Tête LCC-SNAP dans le champ "DATA" RFC 1042 et 1700

SSAP=0xAA CONTROL=UI=03 OUI EtherType DATADSAP=0xAA

Page 40: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

© G.Requilé

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Encapsulation 802.2

Page 41: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Exemples de trames

Broadcast ethernet protocole ARP00:05:85:8a:5c:5d > ff:ff:ff:ff:ff:ff, ethertype ARP (0x0806), length 64: arp

Multicast 802.3 + 802.2 Spanning tree Protocol00:0e:d7:ff:1c:50 > 01:80:c2:00:00:00, 802.3, length 64: LLC, dsap STP (0x42),ssap STP (0x42), cmd 0x03, 802.1d

Ethernet : protocole IP unicast00:0d:93:c8:91:9c > 00:00:5e:00:01:33, ethertype IPv4 (0x0800), length 122: IP 130.79.90.153 > 130.79.200.11

Ethernet protocole IPv6 (et multicast)00:05:85:82:f8:3e > 33:33:00:00:00:09, ethertype IPv6 (0x86dd), length 1070:fe80::205:8500:282:f83e.521 > ff02::9.521:

802.3 + 802.2 + SNAP + IPX00:00:74:9d:2c:f4 > ff:ff:ff:ff:ff:ff, 802.3, length 64: LLC, dsap SNAP (0xaa), ssapSNAP (0xaa), cmd 0x03, (NOV-ETHII) 00000000.00:00:

Page 42: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

Algorithme récepteur• Interface ethernet peut accepter plusieurs adresses

• adresse de la carte (par défaut ou modifiée par ifconfig), adresse broadcast, liste adresses multicast (si configurées)

• Récepteur ethernet– vérifie trame valide

• longueur multiple 8 bits, checksum correct• longueur ≥ 64 octets (sinon résidu «fragment» collision) et ≤ 1518

➾ sinon ignorée– si oui et si adresse destination non acceptée

➾ trame ignorée (sauf mode promiscuous)– si trame valide et adresse destination acceptée

➾ trame fournie au protocole supérieur adéquat (d’après champ ethertype ou SNAP)

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Réception Ethernet

en1: flags=8863<UP,BROADCAST,SMART,RUNNING,SIMPLEX,MULTICAST> mtu 1500 ether 78:ca:39:ab:cd:da inet6 fe80::7aca:39ff:feae:eeda%en1 prefixlen 64 scopeid 0x5 inet 130.79.181.13 netmask 0xfffffc00 broadcast 130.79.183.255 inet6 2001:660:4701:2005:7aca:39ff:feae:eeda prefixlen 64 autoconf media: <unknown subtype> status: active

Page 43: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Ethernet, en pratique• Différentes instances débit/support/codage• Pour chaque instance

– codage (ex : 10 Mb/s : codage Manchester)– limitations sur le dimensionnement

• types et longueurs de câbles• équipement intermédiaires (répéteurs)• limitations globales (CSMA/CD )

• Répéteur (hub)– équipement interconnectant 2 ou plusieurs câbles– répétant le signal de chaque entrée vers toutes les sorties (~ampli)– permet augmentation distances et nombre stations– ne filtre pas : pas de limitation des collisions– câbles + répéteurs = 1 seul domaine de collision

– Exemple ethernet 10 Mb/s : L/D > 2t => 2t < 51,2 µs (= SlotTime)• on doit limiter la taille du réseau, ordres de grandeur:

• traversée d’un répéteur ~2,2 µs• propagation 500 m coaxial ~2,2 µs

➾ 5 segments de câble reliés par 4 répéteurs ~ 51 µs aller retour (< 512 bits)– limite de 4 répéteurs « en série »– Note : possibilité d’un + grand nombre de répéteurs (s’ils ne sont pas en série ➾ arbre)

Page 44: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Evolution Ethernet (1)- Initialement, 10Mb/s bande de base (half-duplex : CSMA/CD)

• 10base5 sur coaxial « épais » (segments 500m max)• 10base2 sur coaxial fin (segments de 185m max)• répéteurs coûteux à 2 ports + liens inter-répéteurs fibre• 10 base FL fibre optique (≤ 2km en PàP, half ou full duplex)

- Apparition du 10baseT• segments de 100m max sur 2 paires torsadées• répéteurs avec nombreux ports (8, 16, …)• PàP half ou full duplex (si pas de répéteur)• câblage systématique en étoile• répéteurs, câblage moins coûteux => expansion des LAN

- Apparition du 100Mb/s « fast ethernet »• nécessité de diviser le délai max par 10• 100baseTX jusqu’à 100m sur 2 paires torsadées cat5• 100baseFX en fibre multimode (jusqu’à 412m en half duplex, 2km en FD)• possibilité Full-Duplex• possibilité auto-négociation (10 ou 100, Full ou Half)• Maximum 2 répéteurs «rapide» classe II ou 1 répéteur « lent » classe I

=> réseau de petit diamètre (205m max en cuivre)

Page 45: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Evolution Ethernet (2)

- Apparition du 1000Mb/s « gigabit ethernet »•impossibilité de diviser encore le délai max par 10

•trames agrégées en burst si possible•sinon suivies de bourrage/padding ➾ 4096 bits minimum (délai max conservé, mais pertes d’efficacité si petites trames...)•1000baseTX (segment cuivre 100m)•1000baseLX ou SX (fibre)

• En pratique surtout des switchs (plus de CSMA/CD car plus de collisions ...)

- Généralisation des ponts/switchs/commutateurs ethernet• permettre de diviser le domaine de collision• interconnecter des débits différents

- Apparition du 10Gb/s• plus de half duplex (donc ni répéteur, ni CSMA/CD)• liens point-à-point entre machines ou switchs

- En cours : ethernet 100G …

Page 46: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

RJ 45• Prise RJ45 4 paires torsadées• 2 paires utilisées par 10baseT, 100baseTX, 4 paires pour 1000base-T• Câble droit entre machine et hub ou pont• Câble croisé entre 2 machines (paire émission sur paire réception)

câble 4 paires torsadées

câble coaxial

Page 47: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

Prise en main réseaux LINUX

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

La commande ifconfigConfiguration locale ou distante des équipements réseauxSyntaxe : ifconfig interface adresse [parametres]

Exemple : ifconfig eth0 192.168.1.2 Paramètres génériques up, down : activer, désactivermtu : unité de tranfertnetmask : masque de sous réseaubroadcast : adresse broadcast arp,-arp : activer, désactiver le cache arppromisc,-promisc : activer, désactiver le mode promiscuitémulticast : autoriser la communication hors réseau

La commande routeConfiguration statique des routes sur les réseaux locaux Syntaxe : route add [-net | -host] addr [gw passerelle] [métric coût] [netmask masque] [dev interface]Exemple : route add default gw 192.168.0.1 net ou host indique l'adresse de réseau ou de l'hôte pour lequel on établit une route, adresse de destination, adresse de la passerelle, valeur métrique de la route, masque de la route à ajouter, interface réseau à qui on associe la route.

Page 48: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

Prise en main réseaux LINUX

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

La commande netstatTester la configuration du réseau, visualiser l'état des connexions, établir des statistiques…

Syntaxe : netstat [-liste d’options]

Options génériques :

a afficher toutes les informations sur l'état des connexions, i affichage des statistiques, c rafraîchissement périodique de l'état du réseau, n affichage des informations en mode numérique sur l'état des connexions, r affichage des tables de routage, t informations sur les sockets TCP, u informations sur les sockets UDP.

Page 49: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

Prise en main réseaux LINUX

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Diverses commandes :• ping : envoyer des requêtes ICMP pour mesurer les temps de réponses…• nslookup, dig, host, whois : receuillir des informations sur les

serveurs DNS, diagnostiquer des problèmes DNS, déterminer correspondance adresse IP / nom de domaine…

• traceroute : déterminer un chemin sous la forme d’une suite de routeurs…

• arp –a,s,d : visualiser et modifier la table de correspondance adressage MAC / IP…

Les commandes WiFi : iwconfig Configurer la carte sans fil et la connexion au point d’accès

Syntaxe : iwconfig [ interface ] [ essid ] [ key ] [ ap ] … iwevent Observer les évènements généré par le pilote et les changements de configuration

iwlist Scanner le réseau et obtenir des infos sur la carte sans fil

Syntaxe : iwlist interface [scan|freq|rate|key…]

Page 50: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

Prise en main réseaux LINUX

L3 RLI 2010/2011 - Pascal Mérindol - http://www-r2.u-strasbg.fr/~merindol/

Les fichiers de configuration :/etc/hosts : résolution de noms/etc/networks : nom «logique» du réseau/etc/host.conf : configuration recherche de noms/etc/resolv.conf : affecter les serveurs de noms/etc/network/interfaces : configuration de la connexion/etc/services : liste des ports / services…

Page 51: Réseaux Locaux et Interconnexions (RLI S6)clarinet.u-strasbg.fr/~merindol/uploads/Teaching/CM-RLI-PARTIE1.pdf · •Présentation de l'architecture d'un réseau d'entreprise. •

RLI S6Fin première partie

LICENCE 3 INFOPascal Mérindol : [email protected]

http://www-r2.u-strasbg.fr/~merindol/