Clase 13 Clic para editar estilo título Tipos de ...daniel/docencia/ro_is/ro_is05_06/... · Enrutamiento distance vector 2/25 Clic para editar estilo título patrón Haga clic para

Clic para editar estilo títulopatrón

Haga clic para modificar el estilo de texto delpatrónSegundo nivelTercer nivelCuarto nivelQuinto nivel

0

Clase 13

Tipos de algoritmos de enrutamientoEnrutamiento Distance-Vector

Tema 4.- Enrutamiento con IP

Dr. Daniel MoratóRedes de OrdenadoresIngeniero Técnico de Telecomunicación Especialidad enSonido e Imagen, 3º curso

Enrutamiento distance vector 1/25



1

Temario1.- Introducción2.- Nivel de enlace en LANs3.- Interconexión de redes IP4.- Enrutamiento con IP5.- Nivel de transporte en Internet6.- Nivel de aplicación en Internet7.- Ampliación de temas




2

Temario1.- Introducción2.- Nivel de enlace en LANs3.- Interconexión de redes IP4.- Enrutamiento con IP Carácterísticas del enrutamiento dinámico en Internet Tipos de algoritmos. Enrutamiento Distance-Vector RIP Problemas de RIP5.- Nivel de transporte en Internet6.- Nivel de aplicación en Internet7.- Ampliación de temas




3

Objetivo Características de los tipos de algoritmos

de enrutamiento




4

Contenido Tipos de algoritmos de enrutamiento Algoritmos Distance-Vector

Descripción Bellman-Ford




5






6

Tipos deProtocolos de EnrutamientoEnrutamiento jerárquico Sistemas Autónomos (AS) Dentro de un AS:

IGP = Interior Gateway Protocol Entre ASs:

EGP = Exterior Gateway Protocol

AS 1

AS 2

AS 3




7

Tipos deAlgoritmos de Enrutamiento Deben informar de la

topología y los cambios en lamisma

Según cómo diseminan lainformación

Link State: Comunican qué vecinos

tienen y el coste Inundan la red Cada nodo conoce la

topología entera

Distance Vector: Comunican estimación de

distancia a destinos Informan a vecinosPath Vector: Comunican estimación de

caminos preferidos a destinos

AS 1

AS 2

AS 3




8

Tipos deAlgoritmos de Enrutamiento

AB

CD

12

31

AB

CD

12

31A

B

CD

12

31A

B

CD

12

31

Link

Sta

teDi

stan

ce V

ecto

rPa

th V

ecto

r

0

0

1

3

AB

CD

12

31A

B

CD

12

31A

B

CD

12

31

0

0

B,D

C,D

No me gusta “B”

A: [B, 2], [C, 1]B: [A, 2], [D, 1]C: [A, 1], [D, 3]D: [B, 1], [C, 3]




9



Algoritmos Path-Vector




10

Distance Vector Cada nodo llega a conocer la distancia desde él a todos los

destinos D(X,di)

Inicialmente cada nodo solo conoce la distancia a sus vecinos D(X,d)=c(X,d)

Periódicamente comunica D(X,d) a todos sus vecinos Informan con un vector con las distancias a los destinos

( D(X,d1), D(X,d2), D(X,d3), D(X,d4)…) Asíncrono

Al recibir información actualiza: D(X,d)←mínj/c(X,j)<∞{c(X,j)+D(j,d)}

Algoritmo de Bellman-Ford distribuido Empleado desde los comienzos de la ARPANET




11

E1DD∞-C4BB1AA

CostNextDest

D1EE∞-C3BB∞-A

CostNextDest

C∞-E∞-D1BB∞-A

CostNextDest

B4EE3DD1CC1AA

CostNextDest

A1EE∞-D∞-C1BB

CostNextDest

Algoritmo de Bellman-Ford Comienzo

A B D

E

C1

1 3

11 4




12

E1DD∞-C4BB1AA

CostNextDest

D1EE∞-C3BB∞-A

CostNextDest

C∞-E∞-D1BB∞-A

CostNextDest

B4EE3DD1CC1AA

CostNextDest

A1EE∞-D∞-C1BB

CostNextDestA envía

D(E,d)←mín{c(E,A)+D(A,d)}D(B,d)←mín{c(B,A)+D(A,d)}(…)

Algoritmo de Bellman-Ford

A B D

E

C1

1 3

11 4




13

E1DD∞-C

2 (4)A (B)B1AA

CostNextDest

D1EE∞-C3BB∞-A

CostNextDest

C∞-E∞-D1BB∞-A

CostNextDest

B2 (4)A (E)E

3DD1CC1AA

CostNextDest

A1EE∞-D∞-C1BB


D(E,d)←mín{c(E,A)+D(A,d)}D(B,d)←mín{c(B,A)+D(A,d)}


A B D

E

C1

1 3

11 4




14

E1DD∞-C2AB1AA

CostNextDest

D1EE∞-C3BB∞-A

CostNextDest

C∞-E∞-D1BB∞-A

CostNextDest

B2AE3DD1CC1AA

CostNextDest

A1EE∞-D∞-C1BB

CostNextDestD envía

D(E,d)←mín{c(E,D)+D(D,d)}D(B,d)←mín{c(B,D)+D(D,d)}No hay cambios


A B D

E

C1

1 3

11 4




15

E1DD∞-C2AB1AA

CostNextDest

D1EE∞-C3BB∞-A

CostNextDest

C∞-E∞-D1BB∞-A

CostNextDest

B2AE3DD1CC1AA

CostNextDest

A1EE∞-D∞-C1BB

CostNextDestB envía

D(A,d)←mín{c(A,B)+D(B,d)}D(C,d)←mín{c(C,B)+D(B,d)}D(D,d)←mín{c(D,B)+D(B,d)}D(E,d)←mín{c(E,B)+D(B,d)}(…)


A B D

E

C1

1 3

11 4




16

EDC

BA

1DD5 (∞)B (-)C

2AB1AA

CostNextDest

1EE4 (∞)B (-)C

3BB4 (∞)B (-)ACostNextDest

3 (∞)B (-)E4 (∞)B (-)D

1BB2 (∞)B (-)ACostNextDest

2AE3DD1CC1AA

CostNextDest

1EE4 (∞)B (-)D2 (∞)B (-)C

1BBCostNextDest

B envíaD(A,d)←mín{c(A,B)+D(B,d)}D(C,d)←mín{c(C,B)+D(B,d)}D(D,d)←mín{c(D,B)+D(B,d)}D(E,d)←mín{c(E,B)+D(B,d)}


A B D

E

C1

1 3

11 4




17

EDC

BA

1DD5BC2AB1AA

CostNextDest

1EE4BC3BB4BA

CostNextDest

3BE4BD1BB2BA

CostNextDest

2AE3DD1CC1AA

CostNextDest

1EE4BD2BC1BB

CostNextDestC envía

D(B,d)←mín{c(B,C)+D(C,d)}No hay cambios


A B D

E

C1

1 3

11 4




18

EDC

BA

1DD5BC2AB1AA

CostNextDest

1EE4BC3BB4BA

CostNextDest

3BE4BD1BB2BA

CostNextDest

2AE3DD1CC1AA

CostNextDest

1EE4BD2BC1BB

CostNextDestE envía

D(A,d)←mín{c(A,E)+D(E,d)}D(B,d)←mín{c(B,E)+D(E,d)}D(D,d)←mín{c(D,E)+D(E,d)}(…)


A B D

E

C1

1 3

11 4




19

EDC

BA

1DD5BC2AB1AA

CostNextDest

1EE4BC3BB

2 (4)E (B)ACostNextDest

3BE4BD1BB2BA

CostNextDest

2AE3DD1CC1AA

CostNextDest

1EE2 (4)E (B)D

2BC1BB

CostNextDestE envía

D(A,d)←mín{c(A,E)+D(E,d)}D(B,d)←mín{c(B,E)+D(E,d)}D(D,d)←mín{c(D,E)+D(E,d)}


A B D

E

C1

1 3

11 4




20

EDC

BA

1DD5BC2AB1AA

CostNextDest

1EE4BC3BB2EA

CostNextDest

3BE4BD1BB2BA

CostNextDest

2AE3DD1CC1AA

CostNextDest

1EE2ED2BC1BB


D(E,d)←mín{c(E,A)+D(A,d)}D(B,d)←mín{c(B,A)+D(A,d)}(…)


A B D

E

C1

1 3

11 4




21

EDC

BA

1DD3 (5)A (B)C

2AB1AA

CostNextDest

1EE4BC3BB2EA

CostNextDest

3BE4BD1BB2BA

CostNextDest

2AE3DD1CC1AA

CostNextDest

1EE2ED2BC1BB


D(E,d)←mín{c(E,A)+D(A,d)}D(B,d)←mín{c(B,A)+D(A,d)}


A B D

E

C1

1 3

11 4




22

EDC

BA

1DD3AC2AB1AA

CostNextDest

1EE4BC3BB2EA

CostNextDest

3BE4BD1BB2BA

CostNextDest

2AE3DD1CC1AA

CostNextDest

1EE2ED2BC1BB

CostNextDestD envía

No hay cambiosB envía

No hay cambiosC envía

No hay cambiosE envía

No hay cambiosA envía

No hay cambios


A B D

E

C1

1 3

11 4




23

Distance Vector Cálculo distribuido Iterativo e incremental Asíncrono Converge a los caminos de menor coste Protocolos: RIP, IPX-RIP, DECnet,

IGRP, EIGRP, DSDV




24

Temario1.- Introducción2.- Nivel de enlace en LANs3.- Interconexión de redes IP4.- Enrutamiento con IP Carácterísticas del enrutamiento dinámico en Internet Tipos de algoritmos. Enrutamiento Distance-Vector RIP Problemas de RIP5.- Nivel de transporte en Internet6.- Nivel de aplicación en Internet7.- Ampliación de temas




25

Próxima clase

RIP

Lecturas recomendadas: [Forouzan03] 13.2 12 páginas

Documents

Clase 13 Clic para editar estilo título Tipos de ...daniel/docencia/ro_is/ro_is05_06/... · Enrutamiento distance vector 2/25 Clic para editar estilo título patrón Haga clic para