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





l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i



Objetivos

•  Conceptos básicos del enrutamiento

jerárquico en Internet

1/26





l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i



Contenido

•  Introducción
•  Enrutamiento jerárquico

– IGPs
– EGPs

•  Estructura de Internet

2/26





l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i



Nivel de red

•  Objetivo:

–  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”

4/26

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:



• 
• 



l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i

–  Flujo
–  Tipo de tráfico
– 
–  Destino

(origen, destino)

Red A


Red B


R1

R1


R5

R5


R3

R3


R2

R2


R6


R4

R4


Red C


Red D


5/26





l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i



Conmutación

•  Reenviar los bits por el camino
•  Servicios posibles

–  Circuitos (telefonía, longitud de

onda)

–  Paquetes

•  Circuitos virtuales (…)
•  Datagramas (…)

Cada paquete del mismo flujo
sigue la misma ruta

Cada paquete es conmutado
independientemente

Red A


Red B


R1

R1


R5

R5


R3

R3


R2

R2


R6


R4

R4


Red C


Red D


6/26





l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I



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

I

i



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

7/26





l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i



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

8/26





l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i



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 Next-hop
Red A
Red B
Red C
Red D
…

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

if1

R5
R5

if0

if1

Routing
process
if2

R2
R2

if0

Routing
process

if0

if1

R3
R3

if1

if0
Routing
process

R6

if1

R4
R4
Routing
process

if2
Red C

Red D

10/26





l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i



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 Next-hop
Red A
Red B
Red C
Red D
…

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

if1

R5
R5

if0

if1

Routing
process
if2

R2
R2

if0

Routing
process

if0

if1

R3
R3

if1

if0
Routing
process

R6

if1

R4
R4
Routing
process

if2
Red C

Red D

11/26





l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I



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

I

i



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


12/26

¿Camino óptimo?



l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i



•  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

12

67

33

56

56
10

5

5

25

3

22

37

102

40

20
20
1

25

10

1
1

1

3

2

4

2

4

3

3

2
2 2

1

3

7
4
3
2
1

1

3

13/26





l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I


I



I



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

i



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

global

o

descentralizada?

Global:
•  Todos

routers

los
tienen
información
la
topología y los costes de los
enlaces

completa de

•  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”

14/26

l



i



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I


I



I



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



• 

Escala: con centenares de

Enrutamiento jerárquico
•  Autonomía administrativa
•  Cada administrador de red
quiere
el
enrutamiento dentro de su
red

controlar

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

16/26

Enrutamiento jerárquico



l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i

•  Agrupar

routers en

regiones:

“Autonomous Systems” (AS)

•  Routers de un AS un solo



administrador

•  Normalmente los routers en el
mismo AS emplean el mismo
protocolo de enturamiento
– 
–  Routers en diferentes AS pueden

IGP = Interior Gateway Protocol

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

AS 3

17/26





l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I



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

I

i



Enrutamiento jerárquico

tabla de

Border router
•  La
• 
•  EGP:

configurada por ambos
IGP:
internos

rutas a destinos

rutas es

rutas a destinos

externos

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

IGP

EGP

Tabla de rutas

Border router

AS 2

AS 1

AS 3

18/26





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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i

l



Interior Gateway Protocols (IGP)

Características:
•  Simples
•  Calculan caminos eficientes
•  Recalculan
•  No escalan bien para redes

respecto a una métrica

ante cambios

rápidamente

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

19/26





l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I



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

I

i



Exterior Gateway Protocols (EGP)

Características:
•  Mejor escalabilidad
•  Habilidad para agregar
•  Habilidad para expresar

rutas

políticas

•  Mayor carga en el router

BGP (Border Gateway Protocol):
•  Estándar de facto
•  Algoritmo path-vector : anuncia el
camino completo al destino (como
una secuencia de ASs)

•  Los

emplean
conexiones TCP entre los routers

anuncios

AS 1

AS 2

AS 3

20/26

Estructura de Internet

•  Tier-1 ISPs o Internet backbone networks

–  Grandes proveedores internacionales (AT&T, BBN, BT, Cable&Wireless,

Sprint, UUNET, etc.)

–  Conexión completamente mallada
–  No emplean “ruta po