Post on 24-Jan-2016
Redes 2-1Universidad de Valencia Rogelio Montañana
Tema 2
El Nivel de Red: Generalidades
Rogelio MontañanaDepartamento de Informática
Universidad de Valenciarogelio.montanana@uv.es
http://www.uv.es/~montanan/
Redes 2-2Universidad de Valencia Rogelio Montañana
Sumario
• Aspectos generales del nivel de red
• Algoritmos de routing
• Control de congestión
Redes 2-3Universidad de Valencia Rogelio Montañana
La Capa de Red
¿Por donde deboir a w.x.y.z?
Routers
Redes 2-4Universidad de Valencia Rogelio Montañana
El nivel de Red
• Es la capa por antonomasia, la más importante, la única que ‘ve’ los caminos que forman la red.
• Se constituye con enlaces que interconectan dos tipos de nodos:– Nodos terminales: Hosts– Nodos de tránsito: Routers o Conmutadores
• Normalmente los routers tienen varias interfaces y los hosts una (pero puede haber routers con una sola interfaz y hosts con más de una, que se llaman hosts ‘multihomed’).
• Los routers y las líneas que los unen constituyen la subred, que es gestionada por el proveedor u operador.
• En una comunicación dentro de una LAN el nivel de red es casi inexistente (no hay ‘nodos de tránsito’, todas las comunicaciones son directas).
Redes 2-5Universidad de Valencia Rogelio Montañana
Puente vs router
Física
MAC
LLC
Red
Física
MAC
LLC
Red
Física
MAC
LLC
Red
Física
MAC
LLC
Red
FísicaFísica
MAC
FísicaFísica
MAC MAC
Trans.
LLC
Red
LLC
Trans.
El puente actúa a nivel de enlace
El router actúa a nivel de
red
Los dos son
útiles, cada uno
en su papel
A B C D
A B C D
AD AD
CDAB AB CD
X Y
XY XY
A, B, C, D son
direcciones MAC.
X e Y son direcciones
de red
Redes 2-6Universidad de Valencia Rogelio Montañana
Funciones del nivel de Red
• Elegir la ruta óptima de los paquetes– En un servicio CONS: sólo en el momento de establecer el
VC(Virtual Circuit o Virtual Channel)– En un servicio CLNS: para cada datagrama de forma
independiente
• Controlar y evitar la congestión• Controlar que el usuario no abuse del servicio• Resolver (‘mapear’) las direcciones de nivel de red
con las de nivel de enlace (p. ej. en LANs encontrar la dirección MAC que corresponde a una dir. IP).
Redes 2-7Universidad de Valencia Rogelio Montañana
1.11.3 1.2
2.12.3 2.2
1.1
1.31.2
2.1
2.32.2
B.1B.3 B.2
C.1C.3 C.2
B.1
B.3B.2
C.3
C.2C.1
Red CONS
Red CLNS
VC 1
VC 2
A
A
B
B
C
C
Cada paquete lleva elnúmero del circuito virtual
al que pertenece
Cada datagrama lleva ladirección de destino
El orden se respeta siempre
El orden no siemprese respeta
Todos los paquete quevan por un mismo VC
usan la misma ruta
La ruta se elige deforma independientepara cada datagrama
Servicio CONS vs CLNS
Redes 2-8Universidad de Valencia Rogelio Montañana
Red CLNS (datagramas)
RED CONS (circuitos virtuales)
Establecimiento
conexión
Innecesario Requerido (permanente o temporal)
Direccionamiento Cada paquete lleva la dirección completa de
origen y destino
Los paquetes solo llevan el número del VC (generalmente
pequeño)
Routing La ruta se elige de forma independiente para cada datagrama
La ruta se elige al establecer el VC; todos los paquetes siguen
esa ruta
Efecto en caso de fallo en un router
Se pierden los paquetes en tránsito solamente
Todos los VC que pasan por ese conmutador se terminan
Información
de estado
Ni los routers ni la subred conservan
ninguna
Cada VC requiere una entrada en las tablas de cada
conmutador por donde pasa
Calidad de servicio Difícil Fácil
Control de congestión Difícil Menos difícil
CONS vs CLNS (II)
Redes 2-9Universidad de Valencia Rogelio Montañana
Sumario
• Aspectos generales del nivel de red
• Algoritmos de routing
• Control de congestión
Redes 2-10Universidad de Valencia Rogelio Montañana
Redes en estrella y redes malladas
• La topología en estrella es la más simple:– Necesita n-1 enlaces para unir n nodos. – Si falla algún enlace algún nodo queda inaccesible– Solo hay una ruta posible para ir de un nodo a otro
• Las topologías malladas:– Tienen más enlaces que los estrictamente necesarios– Si falla algún enlace es posible que no se pierda
conectividad– Puede haber más de una ruta de un nodo a otro; en estos
casos interesa elegir la mejor (algoritmos de routing)
Redes 2-11Universidad de Valencia Rogelio Montañana
Algunas topologías típicas
Estrella Anillo Estrella jerárquica, árbol sinbucles o ‘spanning tree’
Malla completa Anillos interconectadosTopología irregular
(malla parcial)
Redes 2-12Universidad de Valencia Rogelio Montañana
Principio de optimalidad
Si Valencia está en la ruta óptima de Murcia a Barcelona, entonces el camino óptimo de Valencia a Barcelona está incluido en la ruta óptima de Murcia a Barcelona
Corolario: Todas las rutas óptimas para llegar a Barcelona desde cualquier sitio forman un árbol sin bucles (spanning tree) con raíz en Barcelona.
Redes 2-13Universidad de Valencia Rogelio Montañana
Murcia
Valladolid
Bilbao
Madrid
Valencia
Zaragoza
Sevilla
Barcelona
Badajoz
La Coruña
La red de autopistas españolas
Principio de optimalidad (II)
Árbol de rutas óptimas hacia Barcelona
Barcelona
Bilbao Murcia
Valladolid
Madrid
ValenciaZaragoza
BadajozLa Coruña Sevilla
Los trazos en rojo indican la ruta óptima a seguir en cada caso
Redes 2-14Universidad de Valencia Rogelio Montañana
Algoritmos de routing• Los algoritmos de routing pueden ser:
– Estáticos: las decisiones se toman en base a información recopilada con anterioridad (horas, días o meses). Normalmente el cálculo de la ruta es costoso y se realiza de forma centralizada. Por eso una vez fijada la ruta raramente se cambia.
– Dinámicos: deciden la ruta óptima en base a información obtenida en tiempo real. Requieren un protocolo de routing para recoger la información. La ruta óptima puede cambiar a menudo.
• En redes malladas se suele utilizar routing dinámico.
Redes 2-15Universidad de Valencia Rogelio Montañana
Encaminamiento por inundación
• Consiste en enviar cada paquete por todas las interfaces, excepto por la que ha llegado.
• Utilizado en:– Puentes transparentes (tramas broadcast/multicast)– Algunos algoritmos de routing (estado del enlace)– Algunos algoritmos de routing multicast.
• Si hay bucles se envían paquetes duplicados, el tráfico se multiplica y la red se bloquea. Soluciones:– Bloquear interfaces (spanning tree)– Incorporar contador de saltos retrospectivo y descartar
cuando sea cero– Mantener lista de enviados y descartar duplicados
Redes 2-16Universidad de Valencia Rogelio Montañana
A
G
D E F
CB
A
G
D E F
CB
A
G
D E F
CB
Encaminamiento por inundación: Contador de saltos
Primer salto: 3 paquetes
Segundo salto: 5 paquetes
Tercer salto: 8 paquetes
Redes 2-17Universidad de Valencia Rogelio Montañana
Encaminamiento dinámico
• Requiere recabar información en tiempo real sobre el estado de los enlaces
• Permite responder a situaciones cambiantes, p. ej.: fallo o saturación de un enlace. Pero sólo si hay mallado (ruta alternativa).
• Dos algoritmos:– Vector distancia o Bellman-Ford– Estado del enlace, Dijkstra o Shortest Path First
• En ambos casos el cálculo de rutas óptimas se realiza entre todos los routers de la red, de forma distribuida.
Redes 2-18Universidad de Valencia Rogelio Montañana
Algoritmo del vector distancia o de Bellman-Ford
• Cada router conoce:– Su identificador– Sus interfaces– La distancia hasta el siguiente router de cada interfaz
• Cada router construye una tabla (base de datos) de destinos, que le indica por que interfaz debe enviar los paquetes para cada posible destino.
• Para ello intercambia con sus vecinos vectores distancia, que indican la distancia a cada destino
Redes 2-19Universidad de Valencia Rogelio Montañana
j
k
m
n
Distancia 3
Distancia 2 Distancia 7
Distancia 2
0 5 3 2 19 9 5 22 2 4 7
6 2 0 7 8 5 8 12 11 3 2
5 8 3 2 10 7 4 20 5 0 15
1 2 3 4 5 6 7 8 9 10 11
Recibido de j (+3):
Recibido de k (+2):
Recibido de m (+2):
Recibido de n (+7):
Distancia mínima:
Interfaz de salida:
12 3 15 3 12 5 6 18 0 7 15
Destino:
4
9
10
1
3
Ejemplo del algoritmo de vector distancia
2 6 5 0 12 8 6 19 3 2 9
m j m 0 k j k n j k n
Redes 2-20Universidad de Valencia Rogelio Montañana
Dist. 1A se enciende
Dist. 1
El problema de la cuenta a infinito
C
0 1 0 1 2
- 3 4- 5 4
- 5 6
- 7 6- 7 8- 9 8
. . .
. . .
. . .
A
0 - Distancias hacia A
- 3 2A se apaga
B
-
Redes 2-21Universidad de Valencia Rogelio Montañana
El problema de la cuenta a infinito (II)
• Las noticias buenas viajan deprisa, las malas despacio.
• Hay diversos ‘trucos’ para evitar el problema de la cuenta a infinito, pero ninguno infalible.
• El vector distancia se utiliza actualmente en diversos protocolos de routing:– Internet: RIP, BGP, IGRP, EIGRP
– También en Appletalk y versiones antiguas de DECNET e IPX
Redes 2-22Universidad de Valencia Rogelio Montañana
Algoritmo del estado del enlace• Cada router contacta con sus vecinos y mide su distancia a
ellos.• Construye un paquete LSP (Link State Packet) que dice:
– Quién es él– La lista de sus vecinos y sus distancias a ellos
• Envía su LSP por inundación a todos los routers de la red• Recaba los LSPs de todos los demás nodos• Calcula las rutas óptimas por el algoritmo de Dijkstra:
– Se pone él mismo como raíz del árbol, y coloca a sus vecinos– Mira los LSP de sus vecinos y despliega el árbol; cuando aparece
más de un camino hacia un nodo toma el más corto y descarta los demás.
– Las ramas son en principio provisionales. Una rama se confirma cuando es más corta que todas los demás provisionales.
Redes 2-23Universidad de Valencia Rogelio Montañana
A
B/6
D/2
B
A/6
C/2
E/1
C
B/2
F/2
G/5
D
A/2
E/2
E
B/1
D/2
F/4
F
C/2
E/4
G/1
G
C/5
F/1
Link State Packets
D
A
E F
G
CB
2
4
5
26
1
2 1
2
Algoritmo del estado del enlace (Dijkstra)
Redes 2-24Universidad de Valencia Rogelio Montañana
C(0)
G(5)B(2) F(2)
Coloca C en el árbol.Examina el LSP de C
G(5)
C(0)
B(2) F(2)
G(3) E(6)Coloca F en el árbol.Examina el LSP de F.Encontrado mejor camino a G
C(0)
B(2) F(2)
G(3) E(6)A(8) E(3)Coloca B en el árbol.Examina el LSP de B.Encontrado mejor camino a EC(0)
B(2) F(2)
G(3)
D(5)
E(3)A(8)
Coloca E en el árbol.Examina el LSP de E.
C(0)
B(2) F(2)
G(3)
D(5)
E(3)A(8)
Coloca G en el árbol.Examina el LSP de G.
E(3)
C(0)
B(2) F(2)
G(3)
D(5)
A(8)
A(7)Coloca D en el árbol.Examina el LSP de D.
E(3)
C(0)
B(2) F(2)
G(3)
D(5)A(7)
Coloca A en el árbol.Examina el LSP de A.No quedan nodos. terminar
Algoritmo de Dijkstra
A
B/6
D/2
B
A/6
C/2
E/1
C
B/2
F/2
G/5
D
A/2
E/2
E
B/1
D/2
F/4
F
C/2
E/4
G/1
G
C/5
F/1
Redes 2-25Universidad de Valencia Rogelio Montañana
Árbol de rutas óptimas desde C para la red ejemplo
CA
G
D E F
CB6
2
2
2
1
41
2
5B
E
D
A
F
G
Enlaces no utilizados
Redes 2-26Universidad de Valencia Rogelio Montañana
Algoritmo de estado del enlace
• Los LSPs se transmiten por inundación.• Sólo se envían LSPs cuando hay cambios en la red
(enlaces que aparecen o desaparecen, o bien cambios en la métrica).
• Los LSPs se numeran secuencialmente. Además tienen un tiempo de vida limitado.
• Para evitar bucles solo se reenvían los LSPs con número superior a los ya recibidos y que no están expirados.
• Cada LSP pasa una vez o a lo sumo dos veces (pero no más de dos) por el mismo enlace
Redes 2-27Universidad de Valencia Rogelio Montañana
Reparto de LSPs de C por inundación
C
C
CA
G
D E F
CB
I
C
C
CC
C
A
G
D E F
CB
II
C
C C
A
G
D E F
CB
III
C
A
G
D E F
CB
IV
Redes 2-28Universidad de Valencia Rogelio Montañana
Origen Secuen. Edad B F G B F G Datos
A 21 60 0 1 1 1 0 0 B/6, D/2
B 21 60 0 1 1 1 0 0 A/6, C/2, E/1
D 21 60 0 1 1 1 0 0 A/2, E/2
E 20 58 0 1 1 1 0 0 B/1, D/2, F/4
F 21 59 1 0 1 0 1 0 C/2, E/4, G/1
G 21 62 1 0 1 0 1 0 C/5, F/1
C 21 61 1 1 1 0 0 0 B/2, F/2, G/5
FlagsenvíoLSP
FlagsenvíoACK
LSPsD/2
B/6
A
E/1
C/2
A/6
B
G/5
F/2
B/2
C
E/2
A/2
D
F/4
D/2
B/1
E
G/1
E/4
C/2
F
F/1
C/5
GA B D E
GF
Distribución de los LSPs en el router C
A
G
D E F
CB6
2
2
2
1
41
2
5
C
B
E
D
A
F
G
Base de datos de LSPs en C
Redes 2-29Universidad de Valencia Rogelio Montañana
Routing por estado del enlace
• Con routing por el estado del enlace cada nodo conoce la topología de toda la red (no era así con vector distancia).
• La información sobre la red no se usa para optimizar la distribución de LSPs, sino que estos viajan por inundación haciendo uso de toda la red (si no fuera así no se sabría si las rutas alternativas siguen operativas)
• Generalmente se considera que los algoritmos del estado del enlace son mas fiables y eficientes que los del vector distancia.
• Se utiliza en diversos protocolos de routing:– Internet: OSPF, IS-IS– ATM: PNNI– DECNET– IPX: NLSP
Redes 2-30Universidad de Valencia Rogelio Montañana
Routing jerárquico• Problema: los algoritmos de routing no son escalables. La
cantidad de información intercambiada aumenta de forma no lineal con el tamaño de la red. Lo mismo ocurre con la complejidad de los cálculos (requerimientos de CPU y memoria).
• Solución: crear regiones (niveles jerárquicos). Solo algunos routers de cada región comunican con el exterior. Las rutas son menos óptimas, pero se reduce la información de routing.
• Parecido a la forma como se organizan las rutas en la red de carreteras (internacionales, nacionales, regionales).
Redes 2-31Universidad de Valencia Rogelio Montañana
1A
1B
1C
3A 3B
4A
4E4D
4C
4B
2D2C
2B2A
Región 1 Región 2
Región 3
Región 4
Destino Vía Saltos
1A - -
1B 1B 1
1C 1C 1
2A 1B 2
2B 1B 3
2C 1B 3
2D 1B 3
3A 1C 3
3B 1C 2
4A 1C 3
4B 1C 4
4C 1B 4
4D 1C 5
4E 1C 4
Destino Vía Saltos
1A - -
1B 1B 1
1C 1C 1
2 1B 2
3 1C 2
4 1C 3
Routing jerárquico Tabla de vectores para 1A
No jerárquica Jerárquica
En este caso la ruta de la región 1 a
cualquier destino de la región 4 pasa
por la 3
Redes 2-32Universidad de Valencia Rogelio Montañana
Sumario
• Aspectos generales del nivel de red
• Algoritmos de routing
• Control de congestión
Redes 2-33Universidad de Valencia Rogelio Montañana
Control de congestión• No es posible ocupar una línea (o un router) al
100% ( el tiempo de servicio sería infinito).• Los tiempos de servicio aumentan de forma
dramática cuando la capacidad de una línea o los recursos de un router (CPU o memoria) se aproximan a la saturación.
• Los buffers grandes permiten no descartar paquetes, pero aumentan el retardo. Esto puede causar retransmisiones y generar aún más tráfico.
• Cuando hay congestión severa el rendimiento global disminuye.
Redes 2-34Universidad de Valencia Rogelio Montañana
Carga
Ren
dim
ien
to
SinCongestión
CongestiónFuerte
CongestiónModerada
Efecto de la ocupación de un enlace en el tiempo de servicio y el rendimiento
SinCongestión
CongestiónFuerte
CongestiónModerada
Tie
mp
o d
e S
ervi
cio
Carga
Redes 2-35Universidad de Valencia Rogelio Montañana
Control de AdmisiónUsuario: Quiero enviar tráfico de este tipo y quiero esta QoS
Red: ¿puedo soportar Red: ¿puedo soportar esto de forma fiableesto de forma fiablesin perjudicar otrossin perjudicar otros
contratos?contratos?
Red
No, o sí y pactar un contrato de tráfico
Solicitud de QoS garantizada
Si se supera el Control de Admisión (es decir si se admite la petición) la red y el usuario pactan un contrato de tráfico
Host
Redes 2-36Universidad de Valencia Rogelio Montañana
Como detectar la congestión
• A nivel de red:– Porcentaje de paquetes descartados
– Longitud media de las colas en las interfaces de los routers
• A nivel de transporte:– Retardo medio de los paquetes
– Desviación media del retardo (jitter)
– Porcentaje de paquetes perdidos (suponiendo que no se debe a errores)
Redes 2-37Universidad de Valencia Rogelio Montañana
Mecanismos para notificar situaciones de congestión
Tipo Mecanismo Ejemplo
Implícito Descarte de paquetes, RED (*)
IP + TCP, ATM
Explícito
Paquetes informativos ad hoc
ATM (celdas RM), Frame Relay
Aviso embebido en paquetes de datos
hacia emisor
Frame Relay (bit BECN)
Aviso embebido en paquetes de datos
hacia receptor
Frame Relay (bit FECN),
ATM (bit campo PTI)
(*) RED: Random Early Discard
Redes 2-38Universidad de Valencia Rogelio Montañana
Medidas a adoptar ante una situación de congestión
• Reducir o congelar el envío de paquetes en los emisores (los hosts).
• Retener los paquetes en los buffers de los routers intermedios.
• Descartar paquetes. A veces estos llevan alguna indicación de su importancia para el descarte (paquetes de 1ª y 2ª clase).
• Se puede descartar inteligentemente, por ej. si se descarta un fragmento de un paquete descartar también los demás.
Redes 2-39Universidad de Valencia Rogelio Montañana
Problemas del control de congestión
• Se pueden dar situaciones oscilantes que impidan un aprovechamiento eficiente de los recursos (todos los hosts bajan y suben el ritmo a la vez). Para evitarlo se utiliza la técnica denominada RED (Random Early Discard)
• El uso de notificación explícita ad hoc puede agravar aún más las cosas (generar tráfico extra cuando más problema hay)
• Algunos creen que la lucha contra la congestión por mecanismos sofisticados (explícitos) es una batalla perdida (los remedios llegarán demasiado tarde para ser útiles).
Redes 2-40Universidad de Valencia Rogelio Montañana
LAN A LAN B
Redes ‘oscilantes’
Enlaces WAN
Una respuesta excesivamente rápida a la congestión puede causar situaciones oscilantes
Redes 2-41Universidad de Valencia Rogelio Montañana
Perfil de tráfico y vigilancia
• Perfil de tráfico o conformado de tráfico (traffic shaping): condiciones máximas de uso de la red que el usuario se compromete a cumplir con el proveedor del servicio.
• Vigilancia de tráfico (traffic policing): labor de monitorización que el proveedor realiza para asegurarse que el usuario cumple su palabra.
• Si el usuario incumple el proveedor puede:a) Descartar el tráfico no conformeb) Marcarlo como de ‘segunda clase’ y pasarlo a la red, oc) Pasarlo a la red sin mas (no es habitual)
Redes 2-42Universidad de Valencia Rogelio Montañana
Traffic Shaping y Traffic Policing
Algoritmo del pozal agujereado
• Limitar pico y tamaño de ráfagas
Conformado de Tráfico: Cumplir el contrato
¿El tráfico recibido cumple el contrato?
Si no cumple el policía puede:
•Marcar como 2ª clase (bit CLP) las celdas excedentes, o
•Descartar las celdas excedentes
Vigilancia de Tráfico: Vigilar y obligar su cumplimiento
Datos reales
Host
Datos Conformados
Switch
Sh
aper
Sh
aper
Redes 2-43Universidad de Valencia Rogelio Montañana
Pozal agujereado (‘leaky bucket’)
• El pozal agujereado se utiliza para:– Suavizar las ráfagas que el usuario produce (conformado
de tráfico o traffic shaping): – Asegurar que el tráfico introducido se corresponde con lo
acordado (vigilancia de tráfico o traffic policing):• Se define con dos parámetros:
: caudal constante máximo que se puede inyectar en la red (el agujero del pozal). Se expresa en Mb/s
– C: buffer (la capacidad del pozal) que absorberá las ráfagas que produzca. Se expresa en Mb
• Si el buffer se llena el tráfico excedente se considera no conforme. Normalmente se descarta o se pasa como tráfico de ‘segunda’ clase (candidato a descartar).
Redes 2-44Universidad de Valencia Rogelio Montañana
(Mb/s)
C (Mb)