Click here to load reader

La couche Réseau IP - hyon/SupportsCours/Old_RES_IP.pdf · PDF fileCouche liaison Couche physique Couche réseau. 2007-2008 8 Routage Utilisation de l’algorithmique de graphes

  • View
    249

  • Download
    0

Embed Size (px)

Text of La couche Réseau IP - hyon/SupportsCours/Old_RES_IP.pdf · PDF fileCouche liaison...

  • La couche Rseau IP

    Master MIAGEEC Rseaux

    EmmanE

    E Hyon

  • 2007-2008 2

    Fonctions de la couche rseau Transport de paquets de lhost

    metteur vers le rcepteur Les protocoles de couche rseau

    sont dans chaque host et routeur

    Trois fonctions importantes : Dtermination du chemin : route

    prise par les paquets de la source au dest. Algorithmes de routage

    Commutation : aiguiller les paquets de lentre du routeur vers la sortie approprie

    tablissement dappel : dans certains rseaux, avant le transfert des donnes

    networkdata linkphysical

    networkdata linkphysical

    networkdata linkphysical

    networkdata linkphysical

    networkdata linkphysical

    networkdata linkphysical

    networkdata linkphysical

    networkdata linkphysical

    applicationtransportnetworkdata linkphysical

    applicationtransportnetworkdata linkphysical

  • 2007-2008 3

    Le service rseau : quel modle ?

    Modle de service Les caractristiques du

    service fourni par le canal qui transporte les paquets de lmetteur au rcepteur

    Garantie de BP ? Prservation du dlai inter-paquet

    ? Remise de paquets sans perte ? Remise de paquets en squence ? Informations de congestion pour

    lmetteur ?

    ? ??circuit virtuel

    ou datagramme ?

    Labstraction la plus importante

    fournie par la couche rseau :

    abs

    trac

    tion

    de

    serv

    ice

  • 2007-2008 4

    chemin tabli dans le rseau entre la source et la destination

    Circuits virtuels (ex: ATM, X25)

    tablissement dappel, pour chaque appel avant que le flux de donnes commence

    Chaque paquet porte lidentifiant du CV (et non lID de lhost destination)

    Chaque routeur sur le chemin maintient ltat de chaque connexion Les connexions TCP impliquent uniquement les deux

    systmes terminaux Des liens, des ressources routeur (BP, buffers) peuvent tre allous au CV

  • 2007-2008 5

    Datagramme : le modle Internet

    Pas dtablissement dappel routeurs: pas dtat sur les connexions

    Pas de concept de connexion au niveau rseauLes paquets sont routs daprs lID host destination

    Les paquets dune paire identique (source-dest) peuvent emprunter des routes diffrentes

    applicationtransportnetworkdata linkphysical

    applicationtransportnetworkdata linkphysical

    1. Send data 2. Receive data

  • 2007-2008 6

    Le modle de service Internet(IP)

    NetworkArchitecture

    Internet

    ServiceModel

    best effort

    Bandwidth

    none

    Loss

    no

    Order

    no

    Timing

    no

    Congestionfeedback

    no (inferredvia loss)

    Guarantees ?

    Extension possibles du modle Internet Intserv : fournir des garanties de QoS individualises pour des

    sessions individuelles dune applicationRservation de ressources, tablissement dappelGarantie de QoS pour des flux individuels

    Diffserv : distinguer des classes de service diffrentesGarantie de QoS pour des catgories de flux (profils)

  • 2007-2008 7

    La couche rseau dans Internet

    table de routage

    Ensemble de fonctions implantes dans les hosts et les routeurs

    Protocoles de routageSlection de cheminsRIP, OSPF, BGP

    Protocole IP Conventions dadressageFormat de datagrammeConventions de manip de paquets

    Protocole ICMP Remonte derreursignaling des routeurs

    Couche transport : TCP, UDP

    Couche liaison

    Couche physique

    Coucherseau

  • 2007-2008 8

    Routage

    Utilisation de lalgorithmique de graphes pour dfinir les algorithmes de routage

    Les nuds du graphe sont les routeurs

    Les artes du graphe sont les liens physiques

    Le cot dun lien : dlai, cot , ou niveau de congestion

    But: dterminer le bon chemin(suite de routeurs) travers

    le rseau de la source la dest.

    Protocole de routage

    A

    ED

    CB

    F2

    21

    3

    1

    1

    2

    53

    5

    bon chemin : Chemin au cot le moins

    lev Mais autres dfinitions

    possiblesRgles de gestion

  • 2007-2008 9

    Routage (2)

    Les algorithmes de routagesservent dterminer la

    table de routage.

    Indique la meilleure liaison utiliser (le prochain routeur utiliser), afin de transfrer des donnes vers un noeud.

    Table de routage

    A

    ED

    CB

    F2

    21

    3

    1

    1

    2

    53

    5

    Dest prochain noeud

    B BD DE DC D

  • 2007-2008 10

    Classification des algo de routageInformation globale ou

    dcentralise ?Globale Tous les routeurs ont une info

    complte de la topolgie et des cots des liens

    Diffusion des info tous les nuds

    Algorithmes tat de lienDcentralise Un routeur a les info sur ses

    voisins (routeurs qui lui sont physiquement rattachs)

    Processus itratif de calcul, change dinfo entre voisins

    Algorithmes vecteur de distance

    Statique ou dynamique ?Statique Les routes ne changent pas

    frquemment Intervention humaine

    Dynamique Les routes changent

    MAJ priodique En rponse aux

    changements des cots des liens (fct du trafic ou de la topologie)

  • 2007-2008 11

    Algorithme tat de lien(link state)

    Algorithme de Dijkstra Topologie rseau et cots des liens

    connus de tous les nuds link state broadcast Tous les nuds ont la mme

    info Calcule les chemins les moins chers

    dun nud (source) tous les autres

    Fournit la table de routage de ce nud

    Itratif : aprs k itrations, connat le chemin de moindre cot vers k destinataires

    Notation: c(i,j): cot du lien entre nud i et

    j. Infini si i et j ne sont pas voisins

    D(v): cot actuel du chemin de la source dest. v

    p(v): nud prdcesseur de v sur le chemin de la source v

    N: ensemble des nuds pour lesquels le chemin de moindre cots est connu

  • 2007-2008 12

    Exemple de lalgorithme de Dijkstra

    A

    ED

    CB

    F2

    21

    3

    1

    1

    2

    53

    5

    Step012345

    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)infinity

    2,D

    D(F),p(F)infinityinfinity

    4,E4,E4,E

    Le parcours des prdcesseurs dun nud vers la source donne le chemin = TABLE de ROUTAGE de ce nud

  • 2007-2008 13

    Algorithme Vecteur de distance

    itratif continue jusqu ce que

    plus aucun nud nchange de linfo.

    self-terminating: pas de signal de fin

    asynchrone Les nuds nont pas

    besoin dchanger des info et ditrer en tapes verrouilles

    distribu chaque nud ne

    communique quavec ses voisins directs (nuds qui lui sont attachs)

    Aucun nud na linformation globale

    Table de Distance Chaque nud a la sienne Une range par destination possible Une colonne pour chaque voisin du

    nud Exemple : nud X, pour dest. Y via

    voisin Z :

    DX (Y,Z)distance de X vers Y, via Z comme prochain saut

    c(X,Z) + minw {DZ (Y,w)}

    =

    =

    Cot minimal de Z Y

    Algorithme de Bellman-Ford

    DX (Y,Z)

  • 2007-2008 14

    Dans chaque noeud

    Itratif, asynchrone Chaque itration locale gnre

    par : Le changement de cot dun

    lien local La rception dun message

    dun voisin (son chemin de cot minimal a chang)

    Distribu Chaque nud notifie ses

    voisins uniquement quand son chemin de cot minimum vers une destination a chang

    Les voisins prviendront les voisins si ncessaire

    Un noeud ne connat pas les cots des liens qui ne lui sont pas adjacents, il ne connat que le cot du chemin

    attend (changement de cot local ou msg dun voisin)

    recalcule sa table de distance

    Si le chemin de cot minimum a chang pour une quelconque destination, prvient les voisins

    Chaque nud

  • 2007-2008 15

    Table de Distance : Exemple

    A

    E D

    CB7

    81

    2

    1

    2

    DE (C,D) c(E,D) + minw{DD (C,w)}== 2+2 = 4

    DE (A,D) c(E,D) + minw {DD (A,w)}== 2+3 = 5

    DD (x,y) donn par les voisinsLe calcul du min est fait de proche en proche

    Boucle par E !

    Distance de E vers C via D

    Distance de E vers A via D

    Distances obtenues par voisins

    D ()

    A

    B

    C

    D

    A

    1

    7

    6

    4

    B

    14

    8

    9

    11

    D

    5

    5

    4

    2

    E cot de destination via

    dest

    inat

    ion

    Prochain nud sur le chemin

  • 2007-2008 16

    De la table de distance la table de routage

    D ()

    A

    B

    C

    D

    A

    1

    7

    6

    4

    B

    14

    8

    9

    11

    D

    5

    5

    4

    2

    E cot de destination via

    dest

    inat

    ion

    DE ()

    A

    B

    C

    D

    A,1

    D,5

    D,4

    D,2

    Lien de sortie, cot

    dest

    inat

    ion

    Table de Distance de E Table de Routage de E

  • 2007-2008 17

    Comparaison entre LS et DV

    Complexit en MessageOn suppose : LS: avec n noeuds, et E liens,

    O(nE) msg envoys chaq. fois DV: change juste entre voisins

    Vitesse de convergence LS: O(n**2)

    mais il y a des oscillations DV: temps de convergence

    varie : en cas de boucles de

    routage en cas de problmes de

    count-to-infinity

    Robustesse : Que se passe-t-il en cas de problmes avec des routeurs ?

    LS: noeuds informent des cots

    de liens incorrects chaque noeud calcule slt sa

    propre tableDV:

    noeuds informent de cots de path incorrects

    La table d'un noeud est