PDF de programación - Características del enrutamiento dinámico en Internet

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

Características del enrutamiento

dinámico en Internet

Area de Ingeniería Telemática

http://www.tlm.unavarra.es

Laboratorio de Programación de Redes

3º Ingeniería Técnica en Informática de Gestión





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Objetivos

• Conceptos básicos del enrutamiento

jerárquico en Internet

Routing dinámico

1/26





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Contenido

• Introducción
• Enrutamiento jerárquico

– IGPs
– EGPs

• Estructura de Internet

Routing dinámico

2/26





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I



E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Contenido

• Introducción
• Enrutamiento jerárquico

– IGPs
– EGPs

• Estructura de Internet

Routing dinámico

3/26

Nivel de red

• Objetivo:



S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

– Llevar paquetes del origen al destino
– Usar los enlaces de forma “eficiente”

• Direccionamiento:

– Que permita identificar a los nodos
– Tiene una estructura (no es plano)
– Ésta reduce la información en los routers

• Enrutamiento

es la red

– Elementos de encaminamiento deben “aprender” cómo

– Deben cacular “buenos” caminos a los destinos
– Esto se almacena en las “tablas de rutas”

Routing dinámico

4/26





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Routing

•
•

“Ruta” es un camino (path) ⇒ acíclico (…)
“Routing” = proceso de calcular los caminos que deben seguir los
paquetes

• Se pueden calcular en función de:

– Flujo
– Tipo de tráfico
– (origen, destino)
– Destino

Red A

Red B

Red D

R1
R1

R5
R5

R3
R3

R2
R2

R6

R4
R4

Red C

Routing dinámico

5/26

Conmutación

• Reenviar los bits por el camino
• Servicios posibles

– Circuitos (telefonía, longitud de



S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Red A

Red B

onda)

– Paquetes

• Circuitos virtuales (…)
• Datagramas (…)

Cada paquete del mismo flujo
sigue la misma ruta

Cada paquete es conmutado
independientemente

Red D

R1
R1

R5
R5

R3
R3

R2
R2

R6

R4
R4

Red C

Routing dinámico

6/26





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I



E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Características de IP

• Nivel de red
• Servicio de datagramas, sin conexión
• Routing en función de la dirección destino
• No fiable
• Best effort
• Provee:

– Independencia de las tecnologías de cada red
– Direccionamiento global
– TOS
– Fragmentación y reensamblado

Routing dinámico

7/26





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Otros aspectos

• Direccionamiento

– Nivel 2: local, plano ⇒ no escalable
– Nivel 3: según lugar, jerárquico ⇒ escalable
– Direcciones temporales
– Network Address Translation para

reducir

direcciones

• Routing basado en la dirección destino

Routing dinámico

8/26





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Routing en IP

• Llevado a cabo por un proceso que
se ejecuta en cada router (cálculo
distribuido) (…)

• Resultado: una “tabla de rutas” en

cada router (…)

Red A

Red B

Routing
process

R1
R1

Routing
process

R5
R5

Routing
process

R3
R3

Routing
process

R2
R2

R6

Routing
process

R4
R4
Routing
process

Red C

Routing dinámico

Red D

9/26





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Routing en IP

• Llevado a cabo por un proceso que
se ejecuta en cada router (cálculo
distribuido) (…)

• Resultado: una “tabla de rutas” en

cada router (…)

Destino
Red A
Red B
Red C
Red D
…

Next-hop
IP de if1 de R1
IP de if0 de R3
IP de if0 de R4
IP de if0 de R4
…

Red A

Red B

Routing
process

if0

R1
R1

if1

Routing
process

if0

if1

Routing
process

if1

R5
R5

if0

Routing
process
if2

R2
R2

if0

if1

R3
R3

if1

if0
Routing
process

R6

if1

R4
R4
Routing
process

if2
Red C

Routing dinámico

Red D

10/26





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Forwarding en IP

• Tarea de

“reenviar” por el

interfaz

adecuado el paquete recibido

• En base a la tabla de rutas del router
• La tabla indica cuál es el siguiente router

(next-hop) en el camino

• El router tendrá conectividad a nivel 2

con él

Destino
Red A
Red B
Red C
Red D
…

Next-hop
IP de if1 de R1
IP de if0 de R3
IP de if0 de R4
IP de if0 de R4
…

Red A

Red B

Routing
process

if0

R1
R1

if1

Routing
process

if0

if1

Routing
process

if1

R5
R5

if0

Routing
process
if2

R2
R2

if0

if1

R3
R3

if1

if0
Routing
process

R6

if1

R4
R4
Routing
process

if2
Red C

Routing dinámico

Red D

11/26





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I



E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Principio de optimalidad

• Si router J está en el camino óptimo
desde I a K entonces el camino óptimo
de J a K está en la misma ruta (…)

• Si existiera una ruta mejor de J a K se

podría concatenar con el de I a J

• El conjunto de rutas óptimas a un

destino es un árbol = sink tree (…)

• Árbol ⇒ sin lazos (loops)

K

J

I

Routing dinámico

12/26





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

¿Camino óptimo?

• Shortest path
• ¿Cómo medirlo?
– Número de saltos
– Distancia geográfica
– Retardo

• Peso de cada vértice:

– BW
– Tráfico medio
– Coste (€€)
– Longitud media de cola
– Combinación

1

1

1

1
1

1

1
1

1

1
1 1

1

1

1

1

1

33

56

5

56
10

5

37

102

40

20
20
1

12

67

22

25

3

1
1

1

3

2

4

2

4

3

3

2
22

1

3

10

25

7
4
3
2
1

1

3

Routing dinámico

13/26





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Construcción de las tablas de rutas

¿Estática o dinámica?
Estática:
• Configuración manual
• Cambios lentos
Dinámica:
• Mediante un protocolo de

enrutamiento
– Escalabilidad
– Adaptabilidad
– Complejidad

¿Información

descentralizada?

global

o

Global:
•

routers

completa de

Todos
los
tienen
información
la
topología y los costes de los
enlaces
Algoritmos “link state”

•
Descentralizada:
•

El router conoce solo a sus
vecinos

• Mediante un proceso

iterativo
intercambia esa información con
sus vecinos
Algoritmos “distance vector”

•

Routing dinámico

14/26





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I



E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Contenido

• Introducción
• Enrutamiento jerárquico

– IGPs
– EGPs

• Estructura de Internet

Routing dinámico

15/26





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Enrutamiento jerárquico

•

Escala: con centenares de

millones de destinos
¡No se pueden tener todos
los destinos en las tablas de
rutas!
– Memoria
– CPU
– BW para informar de rutas

• Autonomía administrativa
• Cada administrador de red
quiere
el
enrutamiento dentro de su
red

controlar

Routing dinámico

16/26





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á



I

E
D
O
R
O
T
A
R
O
B
A
L

Enrutamiento jerárquico

• Agrupar

routers en

regiones:

“Autonomous Systems” (AS)

• Routers de un AS un solo

administrador

• Normalemente los routers en el
mismo AS emplean el mismo
protocolo de enturamiento
– IGP = Interior Gateway Protocol
– Routers en diferentes AS pueden

emplear diferente IGP

– Interior oculto

• Comunicar

información de

enrutamiento entre los AS
– EGP = Exterior Gateway

Protocol

– Entre los border routers o
routers frontera de los
AS

Border router

AS 2

AS 1

Routing dinámico

17/26

AS 3

Border router
tabla de
• La

rutas es



S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

IGP da las rutas internas

•
• ¿Si hay más de un enlace al

exterior?
– EGP debe informar de a
qué destinos se puede
llegar por cada uno

Enrutamiento jerárquico

•

configurada por ambos
IGP:
internos

rutas a destinos

• EGP:

rutas a destinos

externos

IGP

EGP

Tabla de rutas

Border router

AS 2

AS 1

Routing dinámico

18/26

AS 3





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I



E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Interior Gateway Protocols (IGP)

Características:
• Simples
• Calculan caminos eficientes

respecto a una métrica

• Recalculan

ante cambios

rápidamente

• No escalan bien para redes

grandes

Los más comunes:
• RIP: Routing Information Protocol
• OSPF: Open Shortest Path First
•

EIGRP: Interior Gateway Routing
Protocol (propietario de Cisco)

AS 1

AS 2

AS 3

Routing dinámico

19/26





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Características:
• Mejor es