[PPT]Part I: Introduction · Web viewPrincipes du routage Routage hiérarchique IP Protocole de routage dans Internet intra-domaine inter-domaine Architecture de routeur ? Objectifs

4 : Network Layer 4a-1

Couche réseauObjectifs : Comprendre les principes

sous-jacents de la couche réseau : routage (choix du chemin) Passage à l’échelle Comment fonctionne un

routeur Description du routage

dans Internet

Sommaire : Services de couche

réseau Principes du routage Routage hiérarchique IP Protocole de routage

dans Internet intra-domaine inter-domaine

Architecture de routeur ?


Fonctionnalités de la couche réseau Transporter des paquets de

l’émetteur vers le récepteur Les protocoles de couche

réseau s’exécutent dans dans chaque hôte et routeur.

Trois fonctions principales : Choix du chemin : route suivie

par les paquets de la source à la dest. Algorithmes de routage

Commutation : transporter les paquets du port d’ entrée vers le bon port de sortie.

Mise en place de l’appel : Dans les réseaux à commutation de circuits, la mise en place du circuit est effectuée par la couche réseau.

networkdata linkphysical








application

transportnetworkdata linkphysical

application



Modèle de service de la couche réseau

Q : Quel est le modèle de service pour les canaux transportant des paquets de la source à la destination ?

Bande passante garantie ? Préservation du délai inter-

paquet (pas de gigue) ? Transmission sans pertes ? Réception dans l’ordre ? Annoncer une indication de

congestion à l’émetteur ?

? ? ?Circuit virtuel

ou datagramme ?

L’abstraction que donne la couche réseau :

serv

ice a

bstra

ctio

n


Circuits virtuels

Avant d’émettre des données, le circuit doit être mis en place Chaque paquet contient un identificateur de VC (et non pas l’adresse de la

destination) Chaque routeur maintient un « état » pour chaque connexion qui traverse le

routeur Les connexions dans la couche transport ne mettent en jeu que les systèmes

terminaux Des ressources du lien (bande passante) ou du routeur (mémoire) peuvent

être allouées au VC Pour garantir des performances

Le « chemin » de la source à la destination se comporte comme un circuit téléphonique


Circuits virtuels : protocoles de signalisation Utilisés pour mettre en place et gérer un VC Utilisés dans ATM, frame-relay et X.25 Ne sont pas utilisés (du moins de façon visible)

dans l’Internet actuel

application


application


1. Initiate call 2. incoming call3. Accept call4. Call connected

5. Data flow begins 6. Receive data


Réseaux Datagramme : le modèle Internet

Pas de mise en place de circuit routeurs : aucun état mémorisé au sujet des connexions

Pas de notion de connexion au niveau réseau Les paquets sont typiquement routés en fonction de

l’adresse de destination Des paquets avec la même source et destination peuvent

suivre des trajets différents

application


application


1. Send data 2. Receive data


Modèle de service de la couche réseau

ArchitectureRéseau

Internet

ATM

ATM

ATM

ATM

Modèle deService

Au mieux

CBR

VBR

ABR

UBR

BandePassanteaucun

Constante

Débit garantie MinimumgarantieAucun

pertes

non

oui

oui

non

non

Ordre

non

oui

oui

oui

oui

Délai

non

oui

oui

non

non

Feedback deCongestion

non (inférencepar les pertes)Pas decongestionPas decongestionoui

non

Garanties ?

Extension au modèle Internet : Intserv, Diffserv


Datagramme ou VC ?Internet Échange de données entre

ordinateurs Service “élastique”, pas

de contrainte de délai stricte

Systèmes terminaux intelligents Pouvant s’adapter,

contrôler leur émission et faire de la compensation de pertes

Réseau simple, complexité aux extrémités

ATM Évolution de la

téléphonie Parole humaine :

Contrainte de délai stricte

Besoin de qualité de services garanties

Systèmes terminaux “simplistes” téléphones La complexité est

interne au réseau


Routage

Abstraction du réseau en graphe

Les nœuds sont des routeurs

Les liens sont les liaisons physiques Coût du lien : délai,

prix du lien ou niveau de congestion

Objectif : choisir un « bon chemin » (suite de routeurs) dans le réseau de la source à la destination.

Protocole de routage

A

ED

CB

F2

21 3

1

12

53

5

«Bon chemin» : Typiquement un chemin

de coût minimal Autres définitions

possibles


Classification des algorithmes de routageInformation globale ou

locale ?Globale : Chaque routeur connaît

toutes les informations de topologie, de coût des liens, etc.

Algorithme “link state (LS)”Locale : Le routeur ne connaît que le

côut des liens vers les voisins. Calcul itératif et échange

régulier d’infos avec les voisins

Algorithmes “distance vector (DS)”

Statique ou dynamique ?

Statique : Les routes ne changent

pas dans le tempsDynamique : Les routes changent

régulièrement Mise à jour régulière En réponse aux

changement de coût des liens


Un Algorithme de routage Link-StateAlgorithme de Dijkstra La topologie et le coût des liens

sont connus de tous les nœuds accompli avec une

diffusion de l’état des liens Tout les nœuds ont la

même info Calculer le plus court chemin

(le chemin le moins coûteux) d’un nœud à tout les autres Génère la table de routage

du noeud De façon itérative : après k

itérations, on connaît le chemin le plus cours vers K destinations

Notation : c(i,j) : coût du lien de i à

j. Est infini si i et j ne sont pas voisins

D(v) : Valeur courante du coût du chemin de la source à la destination V

p(v) : noeud précédant v dans le chemin de la source à v

N : Ensemble des nœuds dont on connaît le coût minimal


Algorithme de Dijksra1 Initialisation : 2 N = {A} 3 Pour tout noeud v 4 si v est adjacent à A 5 alors D(v) = c(A,v) 6 Sinon D(v) = infinity 7 boucle8 Trouver w N tel que D(w) est minimal10 ajouter w à N 11 Mettre à jour D(v) pour tout les nœuds v N adjacents à w 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 jusqu’à la fin des nœuds de N


Algorithme de Dijkstra : exemple

étapes012345

start NA

ADADE

ADEBADEBC

ADEBCF

D(B),p(B)2,A2,A2,A

D(C),p(C)5,A4,D3,E3,E

D(D),p(D)1,A

D(E),p(E)inf

2,D

D(F),p(F)infinf

4,E4,E4,E

A

ED

CB

F2

21 3

1

12

53

5


DiscussionComplexité de l’algorithme : n noeuds n*(n+1)/2 comparaisons : O(n**2) implémentation plus efficace possible : O(nlogn)Oscillations possibles : Ex : coût du lien = niveau de trafic

AD

CB

1 1+e

e0

e1 1

0 0A

DC

B2+e 0

001+e1

AD

CB

0 2+e

1+e10 0

AD

CB

2+e 0

e01+e1

initialement … recalculer le routage

… recalcul … recalcul


Algorithme de routage DVitératif : Continue jusqu’à ce

que les nœuds ne s’échangent plus d’info

Auto-terminaison : pas de «signal» d’arrêt

asynchrone : L’échange des infos ne

nécessite pas d’horlogedistribué : Chaque nœud ne

communique qu’avec ses voisins

Structure de la Table de distance Propre à chaque nœud Une ligne par destination possible Une colonne par voisin exemple : dans le noeud X, pour la

dest. Y via le voisin Z :

D (Y,Z)X

distance de X àY, via Z

c(X,Z) + min {D (Y,w)}Zw

=

=


Table de distance : exemple

A

E D

CB78

12

1

2D ()

A

B

C

D

A

1

7

6

4

B

14

8

9

11

D

5

5

4

2

Ecoût destination via

dest

inat

ion

D (C,D)E

c(E,D) + min {D (C,w)}Dw=

= 2+2 = 4

D (A,D)E

c(E,D) + min {D (A,w)}Dw=

= 2+3 = 5

D (A,B)E

c(E,B) + min {D (A,w)}Bw=

= 8+6 = 14

boucle!

boucle!


Table de routage

D ()

A

B

C

D

A

1

7

6

4

B

14

8

9

11

D

5

5

4

2

Ecoût destination via

dest

inat

ion

A

B

C

D

A,1

D,5

D,4

D,4

Lien sortant , coût

dest

inat

ion

Table de distance Table de routage


Algorithme de routage DVItératif, asynchrone :

chaque itération locale est causée par :

Changement de coût d’un lien adjacent

Message d’un voisin du au changement de sa table de distance

Distribué : Chaque nœud annonce à

ces voisins seulement quand sa table de distance change

attend (un changement dans le coût local ou un msg du voisin)

Recalcule la table de distance

Si la table de distance change, annonce aux voisins

Chaque noeud :


Algorithme de routage DV

1 Initialisation : 2 Pour tout nœud adjacent v : 3 D (*,v) = inf4 D (v,v) = c(X,v) 5 pour toute destination y 6 envoyer min D (y,w) à tous les voisins w

XX

Xw

Dans chaque nœud, X :


Algorithme de routage DV : exemple

X Z12

7

Y


Algorithme de routage DV : exemple

X Z12

7

Y

D (Y,Z)X c(X,Z) + min {D (Y,w)}w=

= 7+1 = 8

Z

D (Z,Y)X c(X,Y) + min {D (Z,w)}w=

= 2+1 = 3

Y


Comparaison des algorithmes LS et DVcomplexité LS : avec n noeuds, E liens,

O(nE) msgs sont envoyés DV : échange entre les

voisins seulement Le temps de convergence

varieVitesse de Convergence LS : O(n**2)

Peut osciller DV : Le temps de

convergence varie Boucle possible Comptage à l’infini

possible

Robustesse : Qu’arrive t’il si le routeur tombe en panne ?

LS : Le nœud peut annoncer un

coût erroné Chaque nœud ne calcule

que sa propre table de routage

DV : Le nœud peut annoncer un

coût erroné Tout les nœuds utilisent la

table des autres nœuds• L’erreur se propage dans

le réseau


Routage Hiérarchique

Facteur d’échelle : avec 50 millions de destinations :

On ne peut enregistrer toutes les destinations dans la table de routage!

autonomie administrative

internet = réseau des réseaux

Chaque administrateur de réseau veut contrôler le routage dans son réseau

Jusqu’ici nous avons étudié un réseau idéal Tous les routeurs sont identiques Un seul réseau… pas vrai en pratique


Routage Hiérarchique Agréger les routeurs

en régions autonomes, “autonomous systems” (AS)

Les routeurs d’un même AS exécutent le même protocole de routage protocole de routage

“intra-AS”

Routeurs spéciaux dans un AS

Exécutent les protocoles de routage intra-AS

Responsables du routage à des destinations extérieurs à l’AS exécutent des

protocoles de routage inter-AS avec d’autres routeurs de passerelle

routeurs de passerelle


Routage Intra-AS et Inter-ASPasserelles :

•Exécutent le routage inter-AS entre elles•Exécutent le routage intra-AS avec les autres routeurs de l’AS

Routage inter-AS, intra-AS dans la

passerelle A.c

Couche réseauCouche liaisonCouche

physique

a

b

ba

aC

A

Bd

A.aA.c

C.bB.a

cb

c


Routage Intra-AS et Inter-AS

Host h2a

b

ba

aC

A

Bd c

A.aA.c

C.bB.a

cb

Hosth1

Routage Intra-AS dans l’AS A

Routage Inter-ASentre A et B

Routage Intra-AS Dans l’AS B


Couche réseau dans Internet

Tablede

routage

Protocoles de Routage •Choix du chemin•RIP, OSPF, BGP

Protocole IP•Adressage•Format des datagrammes•Traitement des paquets

Protocole ICMP•Rapport d’erreur•signalisation

Couche Transport : TCP, UDP

Couche de liaison

Couche Physique

CoucheRéseau


Routage Intra-AS Plus connus sous le nom de Interior Gateway Protocols (IGP) IGPs les plus utilisés :

RIP : Routing Information Protocol OSPF : Open Shortest Path First IGRP : Interior Gateway Routing Protocol (Cisco propr.)


RIP Algorithme Distance vector Inclu dans BSD-UNIX depuis 1982 métrique de coût : # de hops (max = 15

hops) Vecteurs de Distance : échangés toutes les 30

sec via des advertisements Chaque advertisement est envoyé à au plus 25

réseaux


OSPF “open” : dans le domaine public Algorithme Link State

Utilise l’ algorithme de Dijkstra’s Les advertisement OSPF sont envoyés à tout

l’AS par inondation (flooding)


Fonctionnalités avancées d’OSPF Sécurité : tous les messages OSPF sont

authentifiés ; des connexions TCP sont utilisées

Multipath est autorisé (pas dans RIP) Pour chaque lien, plusieurs métriques de coût

en fonction des TOS peuvent être définies Support intégré de l’unicast et du multicast :

Multicast OSPF (MOSPF) utilise la même topologie qu’OSPF

OSPF Hiérarchique dans les grands domaines.


OSPF hiérarchique


Routage inter-AS : BGP BGP (Border Gateway Protocol) : standard de

facto Protocole Path Vector :

similaire au protocole Distance Vector Chaque Border Gateway diffuse à ces

voisins la totalité du chemin entire path (I.e, la suite des ASs) jusqu’à la destination

Ex : la passerelle X envoie son chemin à la dest. Z :

Path (X,Z) = X,Y1,Y2,Y3,…,Z


Routage inter-AS : BGPHypothèse : la passerelle X envoie son chemin

à la passerelle W W peut choisir ou ne pas choisir le chemin

offert par X coût, politique (ne pas router via les autres

ISPs) Si W choisit le chemin annoncé par X, alors :

Path (W,Z) = w, Path (X,Z) Note : X peut contrôler le trafic entrant en

contrôlant ces advertisements Ex : nous ne voulons pas router le trafic de

Z -> ne rien annoncer à Z


Adresse IP : introduction Addresse IP :

identificateur sur 32 bits identifie pour chaque

interface hôte et routeur interface : connexion

entre un hôte ou routeur et la couche physique Les routeurs ont

typiquement plusieurs interfaces

Les hôtes peuvent avoir plusieurs interfaces

Les adresses IP sont associées à une interface

223.1.1.1

223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2223.1.3.1

223.1.3.27

223.1.1.1 = 11011111 00000001 00000001 00000001

223 1 11


Adresse IP Adresse IP

Partie réseau (bits de poids forts)

Partie hôte (bits de poids faible)

Réseau ? (du point de vue IP) Les interfaces avec la

même partie réseau de l’adresse IP

Et qui peuvent communiquer sans avoir besoin d’un routeur de passerelle

223.1.1.1

223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2223.1.3.1

223.1.3.27

Le réseau est constitué de 3 réseaux IP (Les 24 premiers bits sont l’adresse réseau)

LAN


Adresse IP

0réseau hôte

10 réseau hôte

110 réseau hôte

1110 Adresse multicast

A

B

C

D

classe1.0.0.0 to127.255.255.255128.0.0.0 to191.255.255.255192.0.0.0 to223.255.255.255224.0.0.0 to239.255.255.255

32 bits

“classe” d’adressage :


Adresse IP : CIDR Adressage par classe :

utilisation inefficace de l’espace d’adressage Ex : une adresse de classe B a assez de place pour pour

65K hôtes, même si il n’y a que 2K hôtes dans ce réseau CIDR : Classless InterDomain Routing La taille de la partie réseau est arbitraire Format de l’adresse : a.b.c.d/x, où x est le # de bits dans

la partie réseau de l’adresse

11001000 00010111 00010000 00000000

networkpart

hostpart

200.23.16.0/23


Adresse IP : the last word...

Q : Comment un ISP récupère-t-il un bloc d’adresses IP ?

R : ICANN : Internet Corporation for Assigned Names and Numbers

alloue les adresses Gère le DNS Assigne les noms de domaines


Adressage hiérarchique : agrégation de route

“Envoie-moi tout ce dont l’adresse commence par 200.23.16.0/20”

200.23.16.0/23

200.23.18.0/23

200.23.30.0/23

Fly-By-Night-ISP

Organisation 0

Organisation 7Internet

Organisation 1

ISPs-R-Us “Envoie-moi tout ce dont l’adresse commence par 199.31.0.0/16”

200.23.20.0/23Organisation 2

...

...


Envoyer un datagramme de la source à la dest.

Datagramme IP :

223.1.1.1

223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2223.1.3.1

223.1.3.27

A

BE

Champsdivers

addr IPsource

addr IPdest data

Le datagramme reste inchangé durant sa traversé du réseau

Dest. Ner. next router Nhops223.1.1 1223.1.2 223.1.1.4 2223.1.3 223.1.1.4 2

table de routage de A



223.1.1.1

223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2223.1.3.1

223.1.3.27

A

BE

Regarder la partie réseau de l’adresse de B

Vérifier si B est sur le même réseau que A

La couche liaison envoie directement le datagramme à B B et A sont directement

connectés

Dest. Net. next router Nhops223.1.1 1223.1.2 223.1.1.4 2223.1.3 223.1.1.4 2

Champsdivers223.1.1.1223.1.1.3data



223.1.1.1

223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2223.1.3.1

223.1.3.27

A

BE

Dest. Net. next router Nhops223.1.1 1223.1.2 223.1.1.4 2223.1.3 223.1.1.4 2

Regarder la partie réseau de l’adresse de E

E est sur un réseau différent A et E ne sont pas

directement attachés Regarder dans la table

de routage : le routeur suivant pour le réseau de E est 223.1.1.4

La couche liaison envoie le datagramme au routeur 223.1.1.4

Champsdivers223.1.1.1223.1.2.3 data



223.1.1.1

223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2223.1.3.1

223.1.3.27

A

BE

Arrivée à 223.1..1.4 d’un paquet destiné à 223.1.2.2

Regarde la partie réseau de l’adresse de E

E est sur le même réseau que l’interface routeur 223.1.2.9 Envoyer le paquet à ce routeur

La couche liaison envoie le datagramme à 223.1.2.2 via l’interface 223.1.2.9

Le datagramme arrive à 223.1.2.2!!!

Champsdivers223.1.1.1223.1.2.3 data network router Nhops interface

223.1.1 - 1 223.1.1.4 223.1.2 - 1 223.1.2.9

223.1.3 - 1 223.1.3.27

Dest. next


Format de datagramme IP

ver length

32 bits

data (variable length,typically a TCP

or UDP segment)

16-bit identifierInternet

checksumtime to

live32 bit source IP address

IP protocol versionnumber

header length (bytes)

max numberremaining hops

(decremented at each router)

forfragmentation/reassembly

total datagramlength (bytes)

upper layer protocolto deliver payload to

head.len

type ofservice

“type” of data flgs fragment offset

upper layer

32 bit destination IP addressOptions (if any) E.g. timestamp,

record routetaken, pecifylist of routers to visit.

Documents

[PPT]Part I: Introduction · Web viewPrincipes du routage Routage hiérarchique IP Protocole de routage dans Internet intra-domaine inter-domaine Architecture de routeur ? Objectifs