Tipos de algoritmos de enrutamiento...Protocolos de enrutamiento 5/27 I S Á r í m á a Tipos de Algoritmos de Enrutamiento • Deben informar de la topología y los cambios en la

LABORATORIO DE PROGRAMACIÓN DE REDESÁrea de Ingeniería Telemática

Tipos de algoritmos deenrutamiento

Area de Ingeniería Telemáticahttp://www.tlm.unavarra.es

Laboratorio de Programación de Redes3º Ingeniería Técnica en Informática de Gestión

Protocolos de enrutamiento 1/27

LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

Objetivo• Características de los tipos de

algoritmos de enrutamiento


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

Contenido• Introducción• Algoritmos Link-State• Algoritmos Distance-Vector

– Descripción– Bellman-Ford

• Algoritmos Path-Vector


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica





LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

Tipos deProtocolos de Enrutamiento

Enrutamiento 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


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

Tipos deAlgoritmos de Enrutamiento

• Deben informar de la topologíay los cambios en la misma

• 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


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

Tipos deAlgoritmos de Enrutamiento

AB

CD

12

31

AB

CD

12

31A

B

CD

12

31A

B

CD

12

31

Link

Sta

teD

ista

nce

Vect

orPa

th V

ecto

r

0

0

1

3

AB

CD

12

31A

B

CD

12

31A

B

CD

12

31

D

D

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]


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica





LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

Link State

Tres pasos1. Descubrir a los vecinos2. Diseminar la información sobre los

enlaces– Flooding (… …)– Todos conocen la topología (…)

3. Calcular las rutas– Caminos de menor coste– Todos calculan los mismos– Algoritmo de Dijkstra

• OSPF, IS-IS

AS 2

A B D

E

C


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

Link State

Tres pasos1. Descubrir a los vecinos2. Diseminar la información sobre los

enlaces– Flooding (… …)– Todos conocen la topología (…)

3. Calcular las rutas– Caminos de menor coste– Todos calculan los mismos– Algoritmo de Dijkstra

• OSPF, IS-IS

AS 2

A B D

E

C1 1 1

1

1

1 1 1

1

1

1 1 1

1

1

1 1 1

1

1

1 1 1

1

1

(etc…)


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica





LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

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


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

E1DD

∞-C4BB1AA

CostNextDest

D1EE

∞-C3BB

∞-ACostNextDest

C∞-E

∞-D1BB

∞-ACostNextDest

B4EE3DD1CC1AA

CostNextDest

A1EE

∞-D

∞-C1BB

CostNextDest

Algoritmo de Bellman-Ford• Comienzo

A B D

E

C1

1 3

11 4


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

E1DD

∞-C4BB1AA

CostNextDest

D1EE

∞-C3BB

∞-ACostNextDest

C∞-E

∞-D1BB

∞-ACostNextDest

B4EE3DD1CC1AA

CostNextDest

A1EE

∞-D

∞-C1BB

CostNextDest

A envíaD(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


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

E1DD

∞-C2 (4)A (B)B

1AACostNextDest

D1EE

∞-C3BB

∞-ACostNextDest

C∞-E

∞-D1BB

∞-ACostNextDest

B2 (4)A (E)E

3DD1CC1AA

CostNextDest

A1EE

∞-D

∞-C1BB

CostNextDest

A envíaD(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


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

E1DD

∞-C2AB1AA

CostNextDest

D1EE

∞-C3BB

∞-ACostNextDest

C∞-E

∞-D1BB

∞-ACostNextDest

B2AE3DD1CC1AA

CostNextDest

A1EE

∞-D

∞-C1BB

CostNextDest

D envíaD(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


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

E1DD

∞-C2AB1AA

CostNextDest

D1EE

∞-C3BB

∞-ACostNextDest

C∞-E

∞-D1BB

∞-ACostNextDest

B2AE3DD1CC1AA

CostNextDest

A1EE

∞-D

∞-C1BB

CostNextDest

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


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

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


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

EDC

BA

1DD5BC2AB1AA

CostNextDest

1EE4BC3BB4BA

CostNextDest

3BE4BD1BB2BA

CostNextDest

2AE3DD1CC1AA

CostNextDest

1EE4BD2BC1BB

CostNextDest

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


A B D

E

C1

1 3

11 4


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

EDC

BA

1DD5BC2AB1AA

CostNextDest

1EE4BC3BB4BA

CostNextDest

3BE4BD1BB2BA

CostNextDest

2AE3DD1CC1AA

CostNextDest

1EE4BD2BC1BB

CostNextDest

E envíaD(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


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

EDC

BA

1DD5BC2AB1AA

CostNextDest

1EE4BC3BB

2 (4)E (B)ACostNextDest

3BE4BD1BB2BA

CostNextDest

2AE3DD1CC1AA

CostNextDest

1EE2 (4)E (B)D

2BC1BB

CostNextDest

E envíaD(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


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

EDC

BA

1DD5BC2AB1AA

CostNextDest

1EE4BC3BB2EA

CostNextDest

3BE4BD1BB2BA

CostNextDest

2AE3DD1CC1AA

CostNextDest

1EE2ED2BC1BB

CostNextDest

A envíaD(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


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

EDC

BA

1DD3 (5)A (B)C

2AB1AA

CostNextDest

1EE4BC3BB2EA

CostNextDest

3BE4BD1BB2BA

CostNextDest

2AE3DD1CC1AA

CostNextDest

1EE2ED2BC1BB

CostNextDest

A envíaD(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


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

EDC

BA

1DD3AC2AB1AA

CostNextDest

1EE4BC3BB2EA

CostNextDest

3BE4BD1BB2BA

CostNextDest

2AE3DD1CC1AA

CostNextDest

1EE2ED2BC1BB

CostNextDest

D envíaNo hay cambios

B envíaNo hay cambios

C envíaNo hay cambios

E envíaNo hay cambios

A envíaNo hay cambios


A B D

E

C1

1 3

11 4


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

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


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica





LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

Path Vector• Similar a Distance Vector• Cálculo distribuido• Informan a sus vecinos de las rutas calculadas• Incluyen todo el camino hasta el destino para cada

ruta• Protocolos: BGP

AB

CD

12

31A

B

CD

12

31A

B

CD

12

31

0

0

B,D

C,D

No me gusta “B”


LAB

OR

ATO

RIO

DE

PRO

GR

AM

AC

IÓN

DE

RED

ESÁ

rea

de In

geni

ería

Tel

emát

ica

Resumen• Link State• Distance Vector• Path Vector

Documents

Tipos de algoritmos de enrutamiento...Protocolos de enrutamiento 5/27 I S Á r í m á a Tipos de Algoritmos de Enrutamiento • Deben informar de la topología y los cambios en la