PDF de programación - Enrutamiento Introducción y Distance-Vector

ARQUITECTURA DE REDES, SISTEMAS Y SERVICIOS
Área de Ingeniería Telemática

Enrutamiento

Introducción y Distance-Vector

Area de Ingeniería Telemática

http://www.tlm.unavarra.es

Arquitectura de Redes, Sistemas y Servicios

Grado en Ingeniería en Tecnologías de Telecomunicación, 2º

,

Temario

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I

I



I

a
c
i
t

l



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

i

I



e
d
a
e
r
Á

Introducción
Arquitecturas de conmutación y protocolos
Introducción a las tecnologías de red

1.
2.
3.
4. Control de acceso al medio
5. Conmutación de circuitos
6.
7.

Transporte fiable
Encaminamiento

2

,

Temario

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I

I



I

a
c
i
t

l



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

i

I



e
d
a
e
r
Á

Introducción
Arquitecturas de conmutación y protocolos
Introducción a las tecnologías de red

1.
2.
3.
4. Control de acceso al medio
5. Conmutación de circuitos
6.
7.

Transporte fiable
Encaminamiento

3

El problema del encaminamiento

,

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I

I



I

a
c
i
t

l



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

i

I



e
d
a
e
r
Á

El nivel de red reenvía paquetes hacia su destino

•
• Usando el nivel de enlace que permite enviar a los vecinos

– Al otro lado de un enlace
– Vecinos en la misma red de área local

• Nivel de red : reglas de reenvío basadas en el destino del datagrama

– Si el destino es vecino enviar usando el nivel de enlace
– Si el destino no es vecino decidir el mejor vecino al que delegar y enviarle

el datagrama para que el se encargue
Encaminamiento / enrutamiento / routing
Cómo decidir que caminos poner en las tablas de reenvio (tabla de rutas)
Es uno de los problemas fundamentales de redes

•

•

,

I



I

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I

a
c
i
t

l



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

i

I



e
d
a
e
r
Á

Enrutamiento estático

• Solución más fácil: let the human do it

¿En esta red cual deberían ser las tablas de rutas?

• Parece fácil de pensar con un poco de paciencia

– Se pueden resumir redes
– Se pueden usar rutas por defecto
– Al menos en una red sencilla

Exterior
desconocido

,



I

I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



I

a
c
i
t

l



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

i

I



e
d
a
e
r
Á



Enrutamiento estático: problemas
• No es tan fácil cuando no hay exterior
• No es tan fácil cuando el numero de nodos crece
• No es tan fácil cuando hay caminos alternativos y ciclos
• Los administradores se equivocan
• Los administradores pertenecen a diferentes empresas que

no confían entre si

• ¿Qué hacemos para poner un nuevo router, una nueva red,

añadir enlaces?

• ¿Se puede hacer que el encaminamiento funcione de forma

automática?

• Encaminamiento dinámico

Enrutamiento dinámico

,

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I

I



I

a
c
i
t

l



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

i

I



e
d
a
e
r
Á

• En redes de datagramas

– Cada paquete es reenviado según la información de

enrutamiento que hay en cada nodo en cada momento.

– Si cambian las condiciones de la red entre un paquete y otro

los paquetes pueden seguir distintos caminos

– Robusto, se adapta rápido a los cambios
• En redes de circuitos/circuitos virtuales

– Al establecer el circuito/camino se utiliza la información de

enrutamiento disponible en ese momento

– Una vez establecido el circuito se reenvía más rápido. Pero
si cambian las condiciones de la red el camino ya no es el
mejor

– Las decisiones de enrutamiento son menos frecuentes
(=podemos la misma capacidad en usar algoritmos mas
complicados para decidir el camino)

¿Cuál es el destino?

,



I

I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



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

• Unicast: un solo destino
• Broadcast: el destino son todos los nodos
• Multicast: el destino es un conjunto de nodos, un

mensaje tiene que llegar a todo el conjunto

• Anycast: el destino es un conjunto de nodos, un

mensaje tiene que llegar a uno cualquiera del
conjunto

• Nos centraremos en unicast
• Las herramientas/algoritmos son también la base del

enrutamiento broad-, multi-, any- cast

Enrutamiento dinámico

,

I

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



I



a
c
i
t

l



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

i

I



e
d
a
e
r
Á

• ¿Qué información necesitamos de la red?

– Un mapa de la red entera?
– Se puede hacer algo con información parcial?
– Se puede hacer algo sin información?

• Para programar y mantener lo mejor es lo mas

simple...

,



I

I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I

I



a
c
i
t

l



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

i

I



e
d
a
e
r
Á

Empezando desde cero
• ¿Hay algún algoritmo simple que permita que los

paquetes lleguen a su destino, sin mucha
complicación?
• En realidad si
• Y con información mínima en cada router

(sin tabla de rutas)

Enrutamiento aleatorio !!

,

I

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I

I



a
c
i
t

l



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

i

I



e
d
a
e
r
Á

•

•
•

•
•
•

•

Cuando tengo que reenviar un paquete que no es para mi (podria extenderse a ni
para mis redes conectadas)...
elige un siguiente salto aleatorio entre todos los posibles y envíaselo a el
No es muy eficiente
El paquete puede tardar mucho en llegar pero al final llega (con TTL infinito) o bien
podemos jugar con TTLs y probabilidades de entrega
Puede pasar mas de una vez por los nodos
Normalmente no llega por el camino mas corto
Ni todos los paquetes que llegan van por el mismo camino =no mantiene el orden de
paquetes
Pero funciona (es mejor que no tener algoritmo)

,

I

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

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

Enrutamiento por inundación

•

Cuando tengo que reenviar un paquete que no es para mi (podria extenderse a ni
para mis redes conectadas)...
envíalo a todos los siguientes saltos menos por el que llego

• Genera tráfico extra. Cuanto?
•
•
•

El paquete llega seguro (salvo que se usen TTLs)
El paquete llega por el camino mas corto
El paquete llega probablemente mas de una vez. Hay que usar técnicas para
garantizar que solo se entrega una vez (identidad del paquete)

,



I

I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I

I



a
c
i
t

l



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

i

I



e
d
a
e
r
Á



Enrutamiento por inundación

•
•

•

¿Podemos resolver todos los problemas?
El paquete llega probablemente mas de una vez. No queremos entregar duplicados
– Campo de Identidad en el paquete. Hay que garantizar que no se use de nuevo

la misma identidad en el marco de tiempo en que podría confundirse con una
copia

Si hay ciclos en el grafo la inundación genera tráfico infinito
– TTL en los paquetes (facil, pero ya no podemos garantizar que llegue seguro)
– No reenviar paquetes recientes

Parece facil... pero... que es un paquete reciente? Implica guardar los paquetes
que hemos reenviado en los últimos T segundos. Estado en el router

Enrutamiento sin información

,

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I

I



I

a
c
i
t

l



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

i

I



e
d
a
e
r
Á

•
•
•
•
•
•

•

Enrutamiento aleatorio y por inundación
Presentan problemas de poca eficiencia/mucho tráfico extra
Pero son simples y funcionan
Hay situaciones en las que tiene sentido usarlos
Incluso hoy en dia
A veces combinados con otros sistemas de enrutamiento
– Por ejemplo la inundación se puede controlar más facil si estamos en un entorno

en que hay otro protocolo de enrutamiento funcionando
Esto se usa para conseguir broadcast y multicast

– Por ejemplo la inundación puede ser aceptable si solo se usa al establecer un

circuito porque garantiza encontrar el camino mas corto.

Pero en general en una red tan compleja y de la extensión de Internet los protocolos
de este tipo no escalan.
– Mejor mantener los paquetes a que vayan solo por un camino hacia el destino

Mejor si es el mas corto

– Para eso hace falta utilizar información en el enrutamiento

,

I



I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I

I

a
c
i
t

l



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

i

I



e
d
a
e
r
Á



Enrutamiento con información de la red
• Simplificaremos el problema pensando que las redes son una

serie de nodos interconectados entre si
formando un grafo. Las redes de area local se pueden pensar
simplement como destinos
Los detalles de como se distinguen redes y routers quedan para
los protocolos de enrutamiento concretos en proximas clases

Exterior

Enrutamiento con información de la red
• Tenemos un grado en el que los elementos son reenviadores de

paquetes: nodos

• Los enlaces son conexiones entre estos (punto a punto, LAN...)
• Los nodos son posibles origenes y destinos
•

...

,

I



I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I

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

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



I



a
c
i
t

l



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

i

I



e
d
a
e
r
Á

Enrutamiento con información de la red
Los enlaces pueden ser iguales o no

•
• Normalmente asignamos un peso a cada enlace que mide cuanto nos

cuesta o queremos evitar ese enlace comparado con otro
Se supone que el peso es aditivo
Preferimos A-B-C-D (1+1+1) que A-D (4)

• Si asignamos pesos 1 lo que nos interesa es el numero de saltos del

camino total

• Por simplicidad suponemos un grafo no dirigido

(= los enlaces son bidireccionales)