Teleinformática y
Comunicaciones
ppt #10
Donde se explicarán los
conceptos de enrutamiento
Bibliografia
◗ Redes de Computadoras
• Cuarta Edición
• A. Tanenbaum
◗ TCP/IP
• Tercera Edición
• D. Comer
◗ TCP/IP Illustrated Vol1
• Stevens
2
Cap 5 de Tanenbaum
3
Agenda
◗ Aspectos de Diseño de la capa de red
• Servicios
• Orientado a la conexión
• No Orientado a la conexión
• Algoritmos de enrutamiento
• Terminología
• Características buscados
• Árbol
• Algoritmos básicos
– Vector – Distancia
– Estado de Enlace
4
Consideraciones de Diseno
◗ Conmutación de paquetes Store-
and-Forward
◗ Provee servicios a la Capa
Transporte Deben ser independientes de la
tecnología del ruteador
◗ Servicios
• Orientados a la conexión
• NO Orientados a la conexion
5
Conmutacion de paquetes
Store-and-Forward
El paqute se
almacena
ANTES de
reenviarlo
6
Servicio NO orientado a la conexion
1 2 3 4
Al momento de enviar el 4
cambia la tabla de A
F
Los
paque Paquetes de igual origen
tes
y destino pueden seguir
que
se caminos distintos
envia
naF
se
enrut
an
7
hacia
Orientado a la Conexion ( H1 H2 )
Cada paquete lleva un identificador
del CIRCUITO VIRTUAL (CV)
al que pertenece
Si llega de H1 con CV1
se envia hacia C Si llega de A con CV1
con CV 1 se envia hacia E Si llega de C con CV1
con CV 1 se envia hacia F
con CV 1
8
Orientado a la Conexion ( H3 H2 )
Cada paquete lleva un identificador
del CIRCUITO VIRTUAL (CV)
al que pertenece
Si llega de H3 con CV1
se envia hacia C Si llega de A con CV2
con CV 2 se envia hacia E Si llega de C con CV2
con CV 2 se envia hacia F
con CV 2
Todos los paquetes de
igual origen y destino
siguen caminos iguale
9
Comparacion
10
Dominios de enrutamiento
◗ Entidad administrativa
◗ Tiene redes y subredes asociadas
◗ Limita la diseminación de la informacion de
ruteo
◗ Relacionada con la administración de
seguridad
• En sus límites se suelen encontrar los firewall
Dominio de enrutamiento
RD A
A otro Dominio de “A”
RD A1
A otro Dominio
de “A”
PC Estación de trabajo
Enrutador
Entre Dominio
( Ej RD a y RD B )
Servidor
Estación de trabajo
se filtra la informacion RD A1
de ruteo PC
Servidor
Conexion de dominios de
ruteo
Ruteador Organizacion
de piramidal
Borde
RD A RD B
RD A1 RD B1
RD A2 RD B2
Ruteador de
Borde de su
subdominio
Ruteador de Borde : Responsable del intercambio de info de ruteo entre dominios
Conexion de dominios de
ruteo
“192.168.0.0/16
puede alcanzarse a
Es responsable del rango traves mio”
192.168.1.0 al 192.168.254.0
RD A RD B
RD A1 RD B1
RD A2 RD B2
Es responsable del rango Es responsable del rango
192.168.1.0 al 192.168.50.0 192.168.51.0 al 192.168.254.0
Sistemas Autonomos
◗ Sistema Autónomo
• Grupo de redes administradas como un todo
• Ej : Redes De Campus, Hospitales grandes etc
• Las redes estan conectadas entre si por ruteadores con mecanismos
propios
◗ Los SA se identifican mediante un número
• Números desde 1 a 65535
• Mediante el número se determinan como se alcanzan unos a otros
◗ Los SA se pueden subdividir en Areas
Protocolos Internos y
Externos
S.A. 1 S.A. 2
A IGP
C
IGP
IGP
B G1
IGP EGP
Descubrimiento de ruta
◗ Para poder llegar de un lugar a otro de la
red
◗ Se busca la MEJOR ruta
Basado en que se considera inportante
Para videoconferencia : Menor y mas cte. delay
Para transferencia Bancaria : Red con Encriptacion
17
Forwarding y Routing
Terminologia
Funciones de Interconexionado
Terminologia antigua
Route
Routing Discovery
Terminologia actual
Forwarding Routing
ENRUTAMIENTO Adquiere el
REENVIO: Usa la tabla de ruteo para la
conocimiento para crear la tabla
decision de encaminamiennto 18
de ruteo
Caracteristica de un
algoritmo de ruteo
◗ Exacto
• Calcula correctamente la mejor ruta Algoritmos
◗ Simple NO ADAPTATIVOS.
• Poco consumo dce recursos Toman la decisión
por adelantado sin
◗ Robusto mediciones de
• En caso de mucho tráfico no debe fallar campo
◗ Convergente ADAPTATIVOS: Las
• Se reconfigura rapidamente decisiones reflejan
los cambios de
◗ Flexible topología y trafico
• Debe soprtar diferentes métricas
19
Protocolos de Ruteo
Historico
◗ GGP ( Gateway to Gateway Protocol )
• Fuera de Uso
◗ EGP ( Externa Gateway Protocol )
• Reemplazo del anterior, Tambien fura de uso
◗ RIP ( Routing Information Protocol )
• Varias versiones, aun en uso en LAN
◗ OSPF ( Open Shortest Path First )
• Ampliamente uasdo actualmernte
◗ BGP ( Border Gateway Protocol )
• Usado entre dominios ISP
◗ IGRP, EIGRP
• Propietarios CISCO
Algoritmos mas importantes
◗ The Optimality Principle
◗ Shortest Path Routing
◗ Flooding
◗ Distance Vector Routing
◗ Link State Routing
◗ Hierarchical Routing
◗ Broadcast Routing
◗ Multicast Routing
◗ Routing for Mobile Hosts
◗ Routing in Ad Hoc Networks 21
Arbol ARBOL: Solo un camino para ir
desde cualquier nodo a
cualquier otro nodo ( No hay
loops )
El grupo de rutas optimas de todos los prigenes
a un destino forman un ARBOL
22
Ruta mas corta ( A D)
7 C
B
2 2 3 2
2 D
A E F
6 1 2
2
4
G H
• Iniciamos con el nodo origen ( A ) como único integrante del árbol
• Buscamos en nodos vecinos al árbol ( por ahora solo B y G ) el menor costo a
• En el EJ:
• B = 2 ( menor costo )
• G=6
• Marcamos en nodo de menor costo ( B ) como formando parte del ARBOL
• El árbol esta formado ahora por A y B
23
Ruta mas corta ( A D)
7
B C
2 2 3 2
2 D
A E F
6 1 2
2
4
G H
# Árbo B C D E F G H
#1
l A 2A - - - - 6A -
Iteración 1
Solamente B y G están a un
El Arbol inicial es salto del árbol y su costo
solo el origen al origen (A) es el indicada
24
Ruta mas corta ( A D) Se van sumando
los nodos que esté
7 a UN SALTO del
B C árbol y se indica s
2 2 3 2 costo al origen
2 D
A E F
6 1 2
2
4
G H
# Árbo B C D E F G H
#1
l A 2A - - - - 6A -
#2 AB 2A 9BA - 4BA - 6A -
El Árbol ahora es AB ( Se
toma como parte del
árbol el nodo de C, E y G están a un salto del árbol y se
menor peso de la indica su costo al origen y el camino
iteración anterior
25
Ruta mas corta ( A D)
7
B C
2 2 3 2
2 D
A E F
6 1 2
2
4
G H
# Árbo B C D E F G H
#1
l A 2A - - - - 6A -
#2 AB 2A 9BA - 4BA - 6A -
#3 ABE 2A 9BA - 4BA 6EBA 5EBA -
Se suma E al árbol por ser Costo de F al G cambia
el de menor costo de la origen A su
iteración anterior costo
26
Ruta mas corta ( A D)
7
B C
2 2 3 2
2 D
A E F
6 1 2
2
4
G H
# Árbo B C D E F G H
#1
l A 2A - - - - 6A -
#2 AB 2A 9BA - 4BA - 6A -
#3 ABE 2A 9BA - 4BA 6EBA 5EBA -
#4 ABEG 2A 9BA - 4BA 6EBA 5EBA 9GEBA
27
Ruta mas corta ( A D)
7
B C
2 2 3 2
2 D
A E F
6 1 2
2
4
G H
# Árbo B C D E F G H
#1
l A 2A - - - - 6A -
#2 AB 2A 9BA - 4BA - 6A -
#3 ABE 2A 9BA - 4BA 6EBA 5EBA -
#4 ABEG 2A 9BA - 4BA 6EBA 5EBA 9GEBA
#5 AB E G F
2A 9BA - 4BA 6EBA 5EBA 8GEBA
28
Ruta mas corta ( A D) Se4 continua hasta
7
B C que TODOS los
2 2 3 2 nodos formes parte
2 del arbol
A E F D
6 1 2
2
4
G H
# Árbo B C D E F G H
#1
l A 2A - - - - 6A -
#2 AB 2A 9BA - 4BA - 6A -
#3 ABE 2A 9BA - 4BA 6EBA 5EBA -
#4 ABEG 2A 9BA - 4BA 6EBA 5EBA 9GEBA
#5 AB E G F
2A 9BA - 4BA 6EBA 5EBA 8GEBA
#6 ABEGFC
2A 9BA 11CBA 4BA 6EBA 5EBA 8GEBA
29
Ruta mas corta ( A D) Se continua hasta
que TODOS los
7 nodos formen parte
B C del árbol
2 2 3 2
2 D
A E F
6 1 2
2
4
G H
# Árbo B C D E F G H
#1
l A 2A - - - - 6A -
#2 AB 2A 9BA - 4BA - 6A -
#3 ABE 2A 9BA - 4BA 6EBA 5EBA -
#4 ABEG 2A 9BA - 4BA 6EBA 5EBA 9GEBA
#5 AB E G F
2A 9BA - 4BA 6EBA 5EBA 8GEBA
#6 ABEGFC
2A 9BA 11CBA 4BA 6EBA 5EBA 8GEBA
#7 ABEGFCH
2A 9BA 10HFEB 4BA 6EBA 5EBA 8GEBA
30
Se indica la ruta
Ruta mas corta ( A D) mas corta desde
7 cada nodo al origen
B C
2 2 3 2
2 D
A E F
6 1 2
4 2
G H
# Árbo B C D E F G H
#1
l A 2A - - - - 6A -
#2 AB 2A 9BA - 4BA - 6A -
#3 ABE 2A 9BA - 4BA 6EBA 5EBA -
#4 ABEG 2A 9BA - 4BA 6EBA 5EBA 9GEBA
#5 AB E G F
2A 9BA - 4BA 6EBA 5EBA 8GEBA
#6 ABEGFC
2A 9BA 11CBA 4BA 6EBA 5EBA 8GEBA
#7 ABEGFCH
2A 9BA 10HFEB 4BA 6EBA 5EBA 8GEBA
31
#8 ABEGFCHD
2A 9BA 10HFEB 4BA 6EBA 5EBA 8GEBA
Inundación ( Flooding )
◗ Cada paquete de entrada se reenvía a todas las salidas
menos aquella por la que llego
◗ Desventajas: Genera gran cantidad de paquetes
• Contador de saltos, al llegar a cero elimina el paquete.
• Registro de paquetes difundidos, para no enviarlos por
segunda vez
• Reenviar solo por líneas que van en la dirección
aproximada del destino.
◗ Ventajas
• Robusto
• Retardo mas corto
32
Protocolos de Ruteo
◗ Dos Tipos
• Vector Distancia
• Busca el menor numero de saltos entgre origen y
destino
• Calculado por cada ruteador
• Distancia = Nro de saltos
• Estado de enlace
• Asigna un valor ( metrica ) a cada enlace
• El camino elegido es el que sume menor metrica
• Cada ruteador implementa el algoritmo basandose
en la misma base de datos que todos ayudan a
construir
Vector - Distancia
◗ Dinámico ( Adaptativo )
◗ Cada Routeador mantiene un tabla con la
mejor ruta conocida a cada destino y la
linea para llegar.
◗ Bellman – Ford / Ford – Fulkerson
◗ Cada T ms c/ruteador envía tablas a sus
vecinos ( típico: 30 seg.)
34
Vector - Distancia
◗ Usa Computacion Distribuida
• Cada ruteador calcula la “mejor” ruta
independientemente de los demas
• Cada ruteador notifica a sus vecinos el mejor
camino H1
R1 (1,1)
R2 (2,1) R3 (2,1)
Up-Date de Vector-
Distancia
M Tabla actual de K Up Date recibido
K
Q
J
Propagación
Estoy a 4 de G
Estoy a 3 de G Estoy a 2 de G
Estoy a 2 de G
Host Estoy en Estoy a 1 de G
contacto a G
Distacia medida por A, I, H, K a los
Vector - Distancia demás Ruteadores y enviadas a J
Tabla de Enrutamiento
del Router J
EJ para
llegar
a G:
Guarda
en
J tabla
el
Subred de ejemplo mejor
camin
Ej. Para llegar a G o
Por A: 8 + 18 = 26
Por I: 10 + 31 = 41
Por H: 12 + 6 = 18
Por K: 6 + 31 = 37 Retardo medido por J,
desde el a sus 38
vecinos
Vector – Distancia
El problema de cuenta a infinito - Buenas Noticias
A Inicialmente
desactivado
,
Primer intercambio
A se enciende y B
se entera que esta
a un salto
Segundo intercambio
C se entera que A esta
activo a distancia 2
Cada ruteador publica su tabla cada 30 seg
Al cabo de 4 intercambios toda la red
esta enterada de la activación de A 39
Vector – Distancia
El problema de cuenta a infinito – Malas Noticias
A Inicialmente
activado,
Primer intercambio
A se desactiva.
B se entera pero
cambia su tabla
para enviar por C
que dice estar a
costo 2
Segundo intercambio
C se entera que B esta
a 3 de A y cambia su
tabla a costo 4
Se requieren infinitos intercambios para llegar al
costo infinito ( Se suele tomar infinito igual a 16) 40
Estado de Enlace
◗ Cada ruteador anuncia el estado de sus
interfaces a los vecinos
◗ Se asigna un costo a cada link
◗ La información de ruteo se usa para crear
una base de datos que refleje la topología de
la red
Estado de enlace
Válido para cada ruteador:
◗ Descubre a sus vecinos y aprende las
direcciones de red
◗ Mide el retardo o costo a cada vecino.
◗ Arma un paquete con todo lo aprendido.
◗ Envía el paquete a otros ruteadores.
◗ Computa el camino mas corto a otros
ruteadores.
Cada ruteador conoce la topología completa de la red
42
Estado de B: D=1, A=1
D: C=2, B=1
Estoy a 9 de G por
B
enlace C: E=2, D=2, A=5
E: F=1, C=2
Estoy a 10 de G
por C
F: G=2, E=1 A
B 1
D: C=2, B=1
C: E=2, D=2, A=5 5
1 C: E=2, D=2, A=5 C: E=2, D=2, A=5
E: F=1, C=2
E: F=1, C=2 E: F=1, C=2
F: G=2, E=1
F: G=2, E=1 F: G=2, E=1
D C
2
Host 2 E: F=1, C=2
F:G=2, E=1
G 2 1 E
F F: G=2, E=1
Oscilación ( Eleccion del camino por carga )
Para el trafico W – E se elije el enlace de menor carga, que en ese
momento pasa a estar cargado, por lo cual se pasa al otro. Iniciando
una oscilacion
44
Paquetes de Estado de Enlace
Generado Retardo del router A
por nodo con el router B
A
Retardo del router A
con el router E
(a) A subnet. (b) The link state packets for this subnet.
45
Distribucion de paquetes de estado de enlace
Se debe reenviar
aCyF Se debe
Origen: Nodo
reconocer al
A
que lo genero:
A
Buffer
Un Paquete de NODO
Originado en E queB
llegó por EAB y por EFB, el Se reconoce a
único vecino que no lo tiene AyF 46
es C. se reenvía a C
Ruteo Jerárquico
TABLA ROUTER 1A TABLA ROUTER 1A
Con Jerarquía:
Una entrada por cada
Se forman niveles ruteador de la región +
( Agrupaciones de ruteadores) una entrada por cada
para disminuir el tamano de la tabla región
de ruteo.
Sin Jerarquía una 47
entrada por ruteador
Difusion
◗ Enviar mensajes a todos ( o varios ) host
• Enviar un paquete a cada uno de los host
• Desperdicia ancho de banda
• Requiere lista de host
• Inundación
• Generada demasiados paquetes
• Consume ancho de banda
• Enrutamiento multidestino
• Cada paquete con lista de destinos, el ruteador cuando reenvía
incluye solo los destinos que puede alcanzar, luego de una cantidad
de saltos los paquetes tienen solo un destino.
• Arbol de expansión
• Se reenvia al arbol de expansion 48
Difusión por arbol de expansión
I envía paquetes a F, H, J y N que
son aceptados por los nodos
E , K y O no
El árbol de expansión no tiene ciclos aceptan
Solo un camino entre dos nodos cualquiera los
paquetes
La difusión termina en 4 saltos por no
y 14 paquetes usando el método llegar por
de árbol de expansión para la difusión ruta del 49
árbol
Multidifusión
◗ Envío de mensajes a Grupos predeterminados.
◗ Cada ruteador debe saber cuales de sus host
pertenecen a que grupos.
◗ Procedimiento
• Cada ruteador calcula el árbol de expansión
• Se recorta el árbol eliminando líneas que no sean
del grupo
50
Multicast Routing
Subred considerada Árbol de expansión del nodo indicado
Árbol de multidifusion del grupo 1 Árbol de multidifusion del grupo 2 51
FIN
52
