Tema 2. Nivel de Red
Transcript of Tema 2. Nivel de Red
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
1 de 70
Enrique Alba Torres
Universidad de Málaga (UMA)
Tema 2. Nivel de Red
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
2 de 70
Servicios del Nivel de Red
Los servicios más importantes prestados por el nivel de red al nivel de transporte son:
• Encaminamiento de los Datos (Routing)
• Control de la Congestión (CdC)
• Interconexión de Redes
• Multiplexado de datos
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
3 de 70
Encaminamiento de Datos
• El nivel de red de un nodo dado (IMP) debe decidir cual es el enlace de salida para cada paquete que llega al nodo (routing).
• Estas decisiones son independientes para cada paquete, si la implementación se basa en Datagramas.
• Por el contrario, todos los paquetes de una conexión dada siguen la misma línea de salida si pertenecen al mismo Circuito Virtual.
• Comúnmente se denomina host al nodo origen o destino de los paquetes y los nodos intermedios se denominan IMP (Interface Message Processor) o PSN (PacketSwitch Node).
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
4 de 70
Control de la Congestión• El nivel de red es en general el encargado de que el
tráfico que entra en la red de comunicación no sobrepase la capacidad máxima de entrega de dicha red.
• El control de la congestión es una característica que afecta a toda la red y no debe confundirse con el control del flujo que afecta a un par de equipos origen/destino.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
5 de 70
Interconexión de Redes
• Es a nivel de red donde se abordan los problemas y protocolos necesarios para llevar a cabo la conexión de dos redes distintas.
• La capa de red debe especificar cómo interaccionar con su homóloga en una red distinta.
• También debe especificar la manera de adaptar los servicios que oferta en base a los servicios de que dispone a nivel de enlace lógico (nivel 2 en OSI).
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
6 de 70
Multiplexado de Datos• La interacción entre las capas del modelo se hace mediante los
Puntos de Acceso al Servicio (SAP, Service Access Point).
• El multiplexado consiste en que esta interacción no sea 1 a 1:
El nivel de red puede utilizar el mismo punto de acceso a los servicios de enlace lógico para entregar distintos flujos de información y así ahorrar enel coste final de la comunicación.
Por el contrario, también podría usar varios puntos distintos de acceso al servicio de enlace para enviar un mismo flujo de información a mayor velocidad hacia el destino final.
1
3
2
Puntos deacceso del nivelde red (N-SAP)
Puntos de accesodel nivel de enlace
(DL-SAP)
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
7 de 70
Tipo vs. Implementación
• Nunca debe confundirse el tipo de servicio que presta el nivel de red con la implementación usada para proporcionar dicho servicio.
• Tipo de servicio:
Orientado a la conexiónSin conexión
• Implementación del servicio:
DatagramaCircuito VirtualCircuito Físico
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
8 de 70
Propuesta OSI para el Nivel de Red
Según OSI, el nivel de red está dividido en tres subcapas:
• La subcapa de acceso depende de la red usada. Está en contacto con la red física y define el protocolo de acceso a la misma. Si cambia la red, cambia el software de esta capa.
• La subcapa de mejora adapta los servicios disponibles en la red a los servicios esperados en el nivel inter-red (añade u oculta servicios). No existe en redes reales que siguen el estándar OSI para el acceso.
• La subcapa inter-red permite interconectar nodos: - Encamina- Fragmenta- Direcciona (busca el nodo destino)- Traduce entre protocolos distintos- Proporciona servicios al nivel de transporte
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
9 de 70
Propuesta OSI para el Nivel de Red
Según OSI, el nivel de red está dividido en tres subcapas:
SUBCAPA DE MEJORA
SUBCAPA DE ACCESO
SUBCAPA INTER-RED
Subred deComunicación
Nivelde Red
Interconexión entreredes posiblemente
distintas
Definición de serviciosinter-red esperados
Protocolo de acceso ala red física usada
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
10 de 70
Funciones del Nivel de Red
Los problemas que resolver a nivel de red son los siguientes:
- Implementación
- Servicio
- Direccionamiento
- Congestión
- Control del Flujo
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
11 de 70
ImplementaciónEsquemas de implementación de una red:
Circuito FísicoSe establece un camino reservado físicamente para cada par.
Circuito Virtual (CV)Se envía un paquete de apertura reservando recursos en los nodos por los que pasará el CV (buffers para los paquetes, tablas de encaminamiento, …). Todos los paquetes del mismo CV visitan los mismos nodos. Los paquetes llegan ordenados y sin errores a su destino final. Por último, se envía un paquete de cierre, para liberar la memoria de los nodos. (Tres fases: apertura, uso y cierre.)
DatagramaLas decisiones de encaminamiento se toman sobre cada paquete de forma independiente del resto de los paquetes. Los paquetes pueden perderse o llegar desordenados. Es optativo el servicio de confirmaciones.
Los dos últimos tipos son los más comunes actualmente
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
12 de 70
Implementación
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
13 de 70
Implementación
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
14 de 70
Implementación
EJEMPLO
CreacióndeCV
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
15 de 70
Implementación
Servicio orientado a conexión
Servicios orientados a conexión y sin conexiónApropiado para
En la capa de redEn la capa de transporteComplejidad
Fácil, si se pueden asignar por adelantado bufferssuficientes en cada CV
DifícilControl de la Congestión
Todos los circuitos virtuales que pasan por el nodo que
cae se cierran
Ninguno, excepto para los paquetes perdidos durante la
caída
Efectos de la caída de nodos
Se escoge una ruta cuando se establece el CV y todos los
paquetes siguen esa ruta
Cada paquete es encaminado de forma diferenteEncaminamiento
Cada CV requiere espacio de tabla en la subred
La subred no contiene información de estadoInformación de estado
Cada paquete contiene un número de CV corto
Cada paquete contiene las direcciones completas de
origen y destinoDireccionamiento
RequeridaNo necesariaEstablecimiento del circuito
CIRCUITO VIRTUALDATAGRAMACARACTERÍSTICA
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
16 de 70
ServicioEl servicio puede ser de dos tipos:
Orientado a la conexión
El usuario percibe la red como una cola ordenada donde no ocurren errores: fácil uso pero difícil implementación si la red falla. Es fácil de implementar con CV y complejo de implementar con Datagramas (aunque deseable en este caso).
Sin conexión
La red puede desordenar los envíos e incluso no entregarlos. Casi cualquier red puede ofrecer este servicio de fácil implementación, pero los usuarios son reticentes a utilizarlo (depende de la aplicación). Es fácil de implementar con Datagramas y raro (aunque posible) encontrarlo sobre redes CV.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
17 de 70
Relación entre Servicio e Implementación
Fácil¿Deseable?
ComplejoDeseable
DATAGRAMA
¿Fácil? (si, pero no eficiente)¿Deseable?
FácilDeseable
CIRCUITO VIRTUAL
SIN CONEXIÓNORIENTADO A CONEXIÓN
SERVICIOIMPLEMENT.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
18 de 70
DireccionamientoLas direcciones de red son necesarias a la hora de intercambiar información. La idea es que haya protocolos que traduzcan direcciones lógicas a direcciones físicas.
El direccionamiento supone definir un formato para estas direcciones y proporcionar mecanismos de traducción.
El direccionamiento debe definir:
El formato de las direcciones: por ejemplo, en IP v.4 las direcciones están formadas por 32 bits, mientras que en X.25 están formadas por 14 dígitos decimales.
La traducción entre protocolos distintos, que es por lo general difícil.
La resolución de direcciones de red:Dirección Lógica Dirección Física
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
19 de 70
CongestiónSe debe prevenir y resolver el uso excesivo de ciertas regiones de la red, ya que los paquetes pueden dejar de entregarse o reducirse la tasa de entregas notablemente.
Tiene relación con un mal diseño, una red muy dinámica o un algoritmo de encaminamiento inadecuado.
Cuando hay mucho tráfico se produce congestión, con lo que el rendimiento cae en picado.
Capacidad máxima deentrega de la subred
Perfecta
Deseable
Congestionada
Paq
uete
s en
trega
dos
Paquetes enviados
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
20 de 70
Control del FlujoSe debe evitar desbordar al ordenador o en general al terminal de destino.
Es necesario aplicar control del flujo en aplicaciones multimedia y en la interacción con elementos antiguoso con terminales de poca capacidad (teléfonos móviles, PDAs, etc.).
Se suele limitar el número de paquetes en tránsito sin confirmar, bien pidiendo un permiso explícito al destino, o bien limitando el número de paquetes por circuito virtual (si procede).
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
21 de 70
Algoritmos de Encaminamiento• El encaminamiento es la principal función del nivel de red
en OSI.
• Un algoritmo de encaminamiento es aquella parte del software de la capa de red encargada de decidir la línea desalida por la que se transmitirá un paquete de entrada.
• El algoritmo debe manejar cambios en la topología y en el tráfico sin abortar los trabajos en los hosts o reiniciar la red (por ejemplo cuando cae un host o un enlace).
• Propiedades deseables:
OptimalidadEstabilidadSimplicidad
JusticiaRobustezCorrección
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
22 de 70
Algoritmos de Encaminamiento
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
23 de 70
Algoritmos de Encaminamiento• Problemas:
Justicia y Optimalidad están frecuentemente reñidas:
Supongamos que hay suficiente tráfico entre A y A’, entre B y B’ y entre C y C’ para saturar los enlaces horizontales. A fin de aumentar al máximo el flujo total, el tráfico entre X y X’ debe suspenderse por completo. Por desgracia X y X’ podrían no verlo de esta manera y estar en desacuerdo...
Es evidente que se requiere un compromiso entre la eficiencia global y la justicia hacia las conexiones individuales en igualdad de condiciones del sistema (si pagan lo mismo, por ejemplo).
A B C
A' B' C'
X'X
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
24 de 70
Algoritmos de Encaminamiento• Problemas:
Decidir el objeto de la optimización (qué optimizar):
- ¿Minimizar retraso medio por paquete, o bien
- Maximizar las prestaciones globales?
Estas dos metas están en conflicto, ya que la operación de cualquier sistema de colas cerca de su capacidad máxima implica un retardo de encolamiento grande.
Compromiso: minimizar el numero de saltos por paquete, puesto que la reducción de la cantidad de escalas tiende a reducir el retardo y también el consumo de ancho de banda, lo que tiende a mejorar el rendimiento.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
25 de 70
Algoritmos de Encaminamiento• Atendiendo a su frecuencia de revisión de las decisiones:
NO ADAPTATIVOSNo basan sus decisiones de reenvío en mediciones o estimaciones del tráfico y la topología actuales. La elección de las rutas se calcula por adelantado, fuera de línea, y se carga en los routers al arrancar la red. Son rígidos pero rápidos y de diseño más simple, aunque toman peores decisiones en general.
ADAPTATIVOSCambian sus decisiones de encaminamiento atendiendo a la topología actual y a cambios en el tráfico. Son flexibles, pero de difícil diseño y costosos, aunque toman mejores decisiones.
• Atendiendo a la información que utilizan:
Centralizados (usan información recolectada de toda la red)
Aislados (usan información local a cada nodo)
Distribuidos (usan una mezcla de información local y global)
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
26 de 70
Encaminamiento Centralizado• En los algoritmos de encaminamiento centralizado existe un nodo
especial, el RCC (Routing Control Center) que realiza las siguientes tareas:
Recopila información de toda la red.Calcula las rutas.Distribuye las rutas a todos los nodos para que las usen.
• En teoría son los mejores algoritmos, ya que tienen a su disposición toda la información de la red, pero presentan varios problemas:
No son muy robustos: si cae el RCC cae toda la red.Se congestionan las líneas cercanas al RCC al recalcular rutas.Se produce una actualización asíncrona de las tablas de encaminamiento, ya que los nodos más cercanos al RCC las reciben antes y los más lejanos pueden estar trabajando mientras tanto con tablas más antiguas, lo que puede provocar descoordinación en los Caminos elegidos para la información.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
27 de 70
Encaminamiento Aislado• En este tipo de encaminamiento cada nodo toma decisiones
basadas sólo en información propia (local).
• Hay múltiples algoritmos de encaminamiento aislado, entre los que destacan:
Algoritmo de la Patata Caliente (Baran 1964)
Algoritmo de Aprendizaje Hacia Atrás (Baran)
Encaminamiento DELTA (δ) (Rudin 1976)
Inundación (flooding)
Multipaso
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
28 de 70
Encaminamiento AisladoALGORITMO DE LA PATATA CALIENTE (BARAN 1964)
• El paquete que llega a un IMP se saca poniéndolo en la línea cuya cola de espera es la más corta, sin importar a dónde lleve dicha línea.
• Variantes: (combinándolo con encaminamiento estático para tener en cuenta el peso estático de cada línea y la longitud de sus colas)
Combinación 1: Usar mejor elección estática a menos que su cola exceda cierta longitud umbral.
Combinación 2: Usar la cola más corta a menos que su peso estático sea muy pequeño.
Combinación 3: Ordenar las líneas por pesos y después por tamaño de cola, y elegir la línea con suma de posiciones menor (combinación lineal de criterios).
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
29 de 70
Encaminamiento AisladoALGORITMO DE APRENCIZAJE HACIA ATRÁS (BARAN)• En cada paquete se incluye la identidad del nodo fuente y un contador. El
contador cuenta el número de saltos dados hasta llegar al nodo actual.
• Si se recibe un paquete por la línea K desde el nodo H con contador a 4 se sabe que H no está a más de 4 saltos atrás por K.
• Si la mejor ruta actual supone más de 4 saltos se puede usar la descubierta ahora (línea K para llegar a H).
• Tras un tiempo todo nodo descubre las rutas más cortas para llegar a cualquier otro nodo.
• Inconveniente: no se registran caídas de líneas o sobrecargas. Sólo se detectan mejoras. Por tanto, los nodos deben olvidar periódicamente la información aprendida y empezar a reconocer nuevas rutas mínimas.
• Solución de compromiso: - Si es muy frecuente la purga, la calidad de las rutas será desconocida- Si se purgan de tarde en tarde la adaptación es lenta
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
30 de 70
Encaminamiento AisladoENCAMINAMIENTO DELTA (δ) (RUDIN 1976)
• Se trata de un algoritmo híbrido entre centralizado y aislado.
• Existe una fase centralizada en la que cada IMP mide periódicamente el coste de cada línea (retraso, colas, uso...) e informa al RCC. Éste calcula los K mejores caminos entre cualquier par de IMPs declarando caminos de coste equivalente que se diferencian por la línea inicial. El RCC informa a los IMPs de los caminos calculados.
• El grado utilizado como valor de equivalencia (δ) permite controlar el sistema respecto a quien toma la decisiones:
Si se considera una equivalencia muy estricta (δ muy pequeño), casi ningún camino es equivalente al mejor, y es el RCC quien decide (similar a encaminamiento centralizado).
Cuando se relaja el criterio de equivalencia (δ grande), aparecen muchos caminos como adecuados y son los IMPs los que toman las decisiones basándose en información local actualizada (similar a encaminamiento aislado).
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
31 de 70
Encaminamiento Aislado
ENCAMINAMIENTO DELTA (δ)
• Con respecto a las clases de equivalencia, se calcula para cada ruta la diferencia de coste con la mejor, y mediante el valor de δ se definen dos clases de equivalencia:
Las rutas cuya diferencia de coste con la mejor es menor o igualque δ y
Las rutas cuya diferencia de coste con la mejor es mayor que δ.
• Si la diferencia de coste de una ruta con la mejor es menor o igual que δsignifica que esta ruta es equivalente a la mejor, por lo que puede utilizarse.
• Es un algoritmo mejor que el aislado o el centralizado puro.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
32 de 70
Encaminamiento AisladoINUNDACIÓN (FLOODING)
• Se trata de un tipo extremo de algoritmo aislado: el paquete entrante se envía por cada línea de salida excepto por la que llegó.
• Aplicaciones típicas: Militares (resistencia a fallos), Bases de Datos (actualizaciones concurrentes), o para comprobar la bondad de otros encaminamientos, ya que por inundación se encuentra siempre el mejor camino porque se prueban todos (ignoremos la gran sobrecarga).
• Si no se controlan puede aparecer un número infinito de paquetes en la red. Tipos de control:
Incluir un contador de saltos en la cabecera que se decrementa en cada visita. Se descarta el paquete al caer a 0. Idealmente el contador debe inicializarse al peor caso (diámetro de la red) o a la distancia entre emisor y receptor (si se conoce).
El IMP fuente numera los paquetes. Cada IMP tiene una lista por cada IMP fuente y número de paquete ya visto. Para evitar grandes listas se usa un contador K para indicar que todos los números de secuencia hasta K se han visto. Se descartan los duplicados que lleguen (se reconocen por su número de secuencia e IMP origen).
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
33 de 70
Encaminamiento AisladoINUNDACIÓN (FLOODING)
• Existen variaciones del algoritmo:
Flooding Selectivo
Sólo se repite el paquete por las líneas orientadas en la dirección de destino correcta (si se conoce la topología de la red).
Random Walk
Cada IMP elige aleatoriamente la línea de salida para cada paquete.
Si añadimos un intento de seleccionar la línea en la direcciónadecuada y la red está muy interconectada, este algoritmo aprovecha muy bien las rutas alternativas y el muy robusto.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
34 de 70
Encaminamiento AisladoMULTIPASO
• Permite equilibrar los envíos a un mismo destino, ya que puede usar líneas distintas según las necesidades.
• Para un destino dado existe una lista de líneas de salida posibles y una probabilidad o frecuencia de uso asociada, por ejemplo:
0.1S0.4M0.5BC
0.2Y0.2F0.6RB
0.3R0.3S0.4AA
probnodoprobnodoprobnodo
Línea 3Línea 2Línea 1Destino
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
35 de 70
Encaminamiento AisladoMULTIPASO
• El algoritmo consiste en lo siguiente:
Cuando llega un paquete para un nodo determinado se genera un número aleatorio entre 0 y 1 que sirve de umbral para elegir la línea de salida del paquete.
Se compara el umbral con el peso de la primera línea de salida que haya fijada para ese destino:
- Si el peso es mayor se envía el paquete por esa línea.
- Si es menor se le suma el peso de la siguiente línea de salida y así se van acumulando pesos hasta que superen el umbral.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
36 de 70
Encaminamiento AisladoMULTIPASO
• Se puede implementar según el siguiente pseudo-código:acc = 0.0; i = 0; lineout = -1;u = Random(0,1);
repeatacc += rtable[destino][i].prob;if (acc >= u) lineout = rtable[destino][i].nodo;else i++;
until lineout <> -1;
• Para el ejemplo anterior, si llega un paquete hacia el nodo A dependiendo del umbral tenemos:
u = 0.2 lineout = Au = 0.5 lineout = Su = 0.8 lineout = R
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
37 de 70
Encaminamiento AisladoMULTIPASO
• El algoritmo acumula probabilidades hasta que se iguala o supera el valor umbral aleatorio en [0,1]. Este valor se genera de nuevo para cada paquete que deba encaminarse.
• Evita tener que predefinir el orden de envío y, en la medida de lo posible, el uso dos veces consecutivas de la misma línea, lo que supondría un tiempo de espera obligatorio entre dos envíos por razones de transmisión física por el enlace.
• Si las probabilidades no cambian en el tiempo el algoritmo es estático, mientras que si cambian se denomina dinámico.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
38 de 70
Encaminamiento Distribuido• Este tipo de encaminamiento es el usado originalmente por
ARPANET.
• Periódicamente cada IMP intercambia información con cada uno de sus vecinos (nodos adyacentes).
• En las tablas de encaminamiento cada IMP tiene una entrada por cada uno del resto de IMPs, y por cada entrada tiene dos campos:
Línea preferida de salida.Estimación de tiempo o distancia (nº de saltos, retraso...)
• Además, se supone que cada IMP es capaz de medir la distancia o coste hasta sus vecinos. La métrica puede ser diferente:
Saltos: la distancia es 1.Longitud de colas: examina cada cola de salida.Retraso: lo mide con paquetes ECHO que el receptor devolverá.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
39 de 70
Encaminamiento Distribuido• El algoritmo de Bellman-Ford es muy utilizado, especialmente
en Internet (algoritmo Vector-Distancias):
d(X,Z) = mín { d(X,A)+d(A,Z), d(X,B)+d(B,Z), d(X,C)+d(C,Z), ... }
• Ejemplo:
Supongamos en la siguiente red que queremos calcular la mejor ruta desde el nodo J hasta el nodo G:
A
A
I
H
K
8
10
12
6
Retraso de Ja sus vecinosB C D
I J K L
HE F G
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
40 de 70
Encaminamiento DistribuidoEl nodo J recibe las siguientes listas de retardos desde sus nodos vecinos:
29L
24K
9J
21I
17H
18G
23F
14E
40D
25C
12B
0A
A
33L
22K
11J
0I
20H
31G
20F
7E
27D
18C
36B
24A
I
9L
22K
7J
14I
0H
6G
19F
30E
8D
18C
31B
22A
H
9L
0K
10J
22I
19H
31G
40F
22E
24D
36C
28B
21A
K
d(J,G) = mínd(J,A) + d(A,G) = 8 + 18 = 26d(J,I) + d(I,G) = 10 + 31 = 41d(J,H) + d(H,G) = 12 + 6 = 18d(J,K) + d(K,G) = 6 + 31 = 37
El mejor camino desde J hasta G es vía H.
• Igualmente cada nodo realiza la misma operación para el resto de los destinos de forma que sus tablas de encaminamiento quedan actualizadas.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
41 de 70
Encaminamiento Óptimo• Incluso si no se conoce la topología ni el tráfico de una red se
puede razonar sobre rutas óptimas.
• Principio de Optimalidad: Si el IMP J está en el camino óptimo desde I a K entonces el camino óptimo de J a K cae sobre la misma ruta.
• Consecuencia: Las rutas óptimas hacia el mismo destino forman un árbol (mínimo) con raíz en dicho destino. No contiene bucles y cualquier paquete se entrega en un número finito y acotado de saltos.
• Si el tráfico de X en su camino a un destino pasa por Y en el árbol mínimo se dice que X es el upstream desde Y e Y se dice que es el downstream desde X.
• Cuando un enlace o nodo cae, el IMP no puede desviar el tráfico a otro nodo en el upstream, sino que debe buscar otro vecino conectado a otra rama.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
42 de 70
Encaminamiento Basado en Flujo• Se basa en una teoría formal (no es tan empírico como los
anteriores).
• Supone que el flujo entre cualquier par de nodos es relativamente estable y predecible.
• Dada la capacidad de un enlace y su flujo medio se puede calcular el retraso medio por paquete en dicha línea usando la teoría de colas. Utilizando una media ponderada por flujo es fácil obtener el retraso medio por paquete para toda la red.
• Encaminar es encontrar un algoritmo que minimice el retraso medio en la red.
• Se necesita conocer a priori la topología de la red, la matriz de flujo F(i,j), la matriz de capacidad C(i,j) en bits por segundo y elegir un Algoritmo de Encaminamiento inicial tentativo.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
43 de 70
Encaminamiento Basado en Flujo• Se puede combinar con encaminamiento simple o multipaso.
• Debemos optimizar el tiempo medio de retardo para cada línea:
T = 1 / (µC-λ)
donde:
- T es el retraso medio de un paquete en la línea- 1/µ es el tamaño medio de un paquete, en bits- C es la capacidad media, en bits por segundo- λ es el flujo medio, en paquetes por segundo
• Para calcular el tiempo medio de retardo de la red completa tomamos la suma ponderada del retardo de cada línea por su peso.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
44 de 70
Encaminamiento Jerárquico• A medida que crece el tamaño de una red, crecen
proporcionalmente las tablas de encaminamiento de los IMPs.
• Estas tablas no sólo consumen memoria en el IMP, sino que también requieren más tiempo de CPU para ser examinadas y más ancho de banda para enviar informes de estado entre IMPs.
• El encaminamiento jerárquico permite reducir el tamaño de estas tablas y por tanto el tiempo de CPU y el ancho de banda.
• Los IMPs se agrupan en regiones, donde cada IMP conoce los detalles de la manera de encaminar paquetes dentro de su propia región, pero desconoce la estructura interna del resto de regiones. Típico en interconexión de redes.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
45 de 70
Encaminamiento Jerárquico
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
46 de 70
Encaminamiento Jerárquico• En redes grandes puede ser insuficiente una jerarquía de dos
niveles: puede ser necesario agrupar las regiones en clusters, los clusters en zonas, las zonas en grupos, etc...
Regiones Clusters Zonas Grupos
• Cada agrupación tiene un IMP distinguido que sabe enviar a otra de mayor nivel.
• Desventajas:
Incremento en la longitud de los caminos.
Cuando la red crece debemos decidir cuántos niveles tendrá la jerarquía.
• Kamoun y Kleinrock (1979):
El número óptimo de niveles para una subred de N IMPses Ln(N) y se requiere e Ln(N) entradas por IMP.
Demostraron que el incremento de la longitud media en el camino es despreciable en la práctica.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
47 de 70
Encaminamiento por Difusión• Este tipo de encaminamiento es usado cuando un host necesita
enviar mensajes al resto de hosts: para repartir trabajo, actualizar una BD distribuida, actualizar tablas de encaminamiento, etc...
• El envío simultáneo de un paquete a múltiples destinos se llama difusión y se han propuesto varios métodos para llevarla a cabo.
• Método 1: no requiere características especiales de la subred. Consiste en que el origen envíe copias del paquete a todos los destinos. Esto supone mucho ancho de banda consumido por la difusión y que el origen debe tener una lista de todo el resto de IMPs destino. Es la peor de las implementaciones factibles.
• Método 2: usar Inundación (flooding), pero esto genera muchos paquetes y consume mucho ancho de banda.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
48 de 70
Encaminamiento por Difusión• Método 3: usar encaminamiento Multidestino. Cada paquete
contiene una lista de destinos o un mapa de bits indicando los destinos deseados. Al llegar al IMP, éste chequea los destinos para determinar el conjunto de líneas de salida que necesitará. Una línea de salida es necesaria si es la mejor ruta al menos para un destino. Después genera una nueva copia del paquete para cada línea de salida a usar, e incluye en cada paquete sólo los destinos que usan la línea. El grupo de destinos se divide entre las líneas de salida. Tras múltiples saltos cada paquete llevará un solo destino y será tratado como un paquete normal.
• Método 4: árbol mínimo con raíz en el IMP origen. Cada IMP debe conocer las líneas que pertenecen al árbol (desventaja) y copia el paquete por cada una de ellas menos por la de entrada. Es el mejor usando el ancho de banda porque genera el mínimo número de paquetes.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
49 de 70
Encaminamiento por Difusión• Método 5: envío por Camino Inverso. Cuando llega un paquete a un
IMP desde un origen se comprueba si los envíos a dicho IMP fuente se hacen normalmente por la línea en la que ha aparecido el paquete. Si es así, copia el paquete por todas las demás líneas de salida. Si no es así probablemente se trata de un paquete duplicado. Ventajas:
Es eficiente.Es simple de implementar.No necesita conocer árbol alguno.No sobrecarga a los paquetes con listas o mapas de bits.No necesita mecanismos especiales para detener el proceso (como ocurre con el flooding).
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
50 de 70
Control de la Congestión (CdC)• Cuando hay demasiados paquetes presentes en la red hay una
degradación de las prestaciones de la red. • Esta situación se llama congestión.• Cuando la cantidad de paquetes enviados por los hosts está dentro de
la capacidad de entrega de la red, todos se entregan (excepto unos pocos afectados por errores de transmisión).
• Sin embargo, a medida que aumenta el tráfico los routers ya no pueden manejarlo y empiezan a perder paquetes.
• A muy alto tráfico, el desempeño se desploma por completo y casi no hay entrega de paquetes.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
51 de 70
Control de la Congestión (CdC)• Principales mecanismos para el control de la congestión:
CdC por preasignación de buffersCdC por descarte de paquetesCdC isarrítmicoCdC por control del flujoCdC por paquetes de calma (choke)
• Pueden usarse por separado, mezclados o bien aplicar las ideas subyacentes en cada uno de ellos.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
52 de 70
CdC por Preasignación de Buffers• Este mecanismo está asociado al uso de Circuitos Virtuales.
• El paquete de setup abre entradas y reserva buffers en los IMPs intermedios.
• Si un IMP no tiene buffers libres bien se busca una ruta alternativa o bien se devuelve al llamante una señal de ocupado. Esta situación también es posible con las peticiones de nuevas entradas en las tablas de encaminamiento.
• Para un CV simplex basta un buffer por IMP y para dúplex un buffer en cada sentido, suponiendo protocolos stop-and-wait. No se confirma al emisor hasta enviar el paquete, de forma que se confirma recepción y espacio libre para uno nuevo. Si el protocolo IMP-IMP permite múltiples paquetes sin confirmar cada IMP necesitaría reservar toda una ventana de paquetes para cada IMP y CV si se desea evitar la congestión.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
53 de 70
CdC por Preasignación de Buffers• Hace un uso potencialmente malo de los recursos, ya que
pueden haber buffers asignados pero no usados, como puede ocurrir en un CV (como en conmutación de circuitos).
• Puesto que reservar buffers para un CV es caro si éste estáinactivo, algunas subredes aplican este método únicamente cuando es esencial un bajo retraso y un alto ancho de banda (p.e. audio digital).
• En caso de CV normal (el retraso no es crítico) es razonable asociar un temporizador a los buffers: si están inactivos mucho tiempo se liberan y se piden de nuevo cuando llegue el próximo paquete por el mismo CV.
• Esto mejora el aprovechamiento, pero produce pequeños retrasos tras inactividad hasta restablecer la comunicación en todos los IMPs de la ruta de nuevo.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
54 de 70
CdC por Descarte de Paquetes• Si llega un paquete a un IMP y no hay buffers libres simplemente lo
descarta (!).
• Si la red ofrece un servicio sin conexión la congestión se controla descartando.
• Si la red ofrece un servicio orientado a la conexión se retransmitirá una copia tras un timeout hasta que la recepción quede confirmada. Tras un máximo de reintentos se recomienda el envío completo (es sólo una posibilidad, existen múltiples).
• Podría ocurrir que no haya sitio para recibir la confirmación de una recepción, con lo cual no se liberaría el paquete que se está intentando confirmar. La solución a este problema es reservar permanentemente un buffer por línea de entrada para inspeccionar paquetes. Los que sean confirmaciones se dejan entrar porque dejan liberar espacio y se podrían almacenar en el buffer recién liberado.
• Problema: una sola línea de salida puede monopolizar todos los buffers, ya que se asignan de manera FIFO (por orden de petición).
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
55 de 70
CdC por Descarte de Paquetes• Heurístico de Irland (1978)
Limita el número de buffers dedicados a una misma línea de salida.
No es drástico pues en general se retransmitirá un posible paquete descartado incluso antes de que su buffer en el origen sea necesario para otro nuevo.
Un IMP tendrá una cola de tamaño máximo m supuestos k buffersen total (sin contar con los permanentes de entrada). El caso incontrolado es m=k.
Para s líneas m=k/s es justo en la media (un buffer pertenece a una sola línea) pero nadie puede tomar prestados buffers y es ineficiente.
El valor de m es una función complicada del tráfico medio. Pero como es muy irregular no sirve que cada IMP mida el suyo y ajuste m. Una regla simple aunque no óptima es m=k/sqrt(s).
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
56 de 70
CdC por Descarte de Paquetes• Heurístico de Kamoun (1976)
Dedica un número mínimo de buffers por línea, evitando a las líneas acaparar buffers.
Si una línea está inactiva continúa reteniendo sus buffers.
ARPANET combina las ideas de Irland y Kamoun para imponer límites inferior y superior al número de buffers por línea de salida.
• Las desventajas de descartar paquetes son las siguientes:
Se precisa ancho de banda extra debido a los duplicados. Si la probabilidad de descartar es p el número esperado de transmisiones antes de que sea aceptado es de 1/(1-p).
Se requiere un timeout de compromiso: si es muy corto muchos duplicados malgastan el ancho de banda (congestionan) y si es muy largo el retraso sube.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
57 de 70
CdC por Descarte de Paquetes• Soluciones:
Minimizar el malgasto de ancho de banda por retransmisiones de descartados, descartando sistemáticamente paquetes que no hayan viajado muy lejos (han usado pocos recursos).
Un caso extremo es descartar los paquetes que vienen del host alIMP antes que a los que van de paso si el número de buffersocupados es mayor que un umbral.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
58 de 70
CdC Isarrítmico• Consiste en mantener constante el número de paquetes que pueden estar
en la subred de comunicación al mismo tiempo.
• Existen paquetes de permiso circulando. Para enviar un paquete de datos, un IMP debe primero capturar y retener un permiso. El IMP destino recogerá el paquete y generará el permiso de nuevo.
• Por lo tanto: Nº paquetes ≤ Nº permisos iniciales
• Problemas:
La subred en conjunto no se congestionará pero nada impide que un IMP en particular sí sea desbordado con paquetes.No es trivial la forma de distribuir los permisos. Para minimizar el retraso de captura la distribución debe ser uniforme para cada IMP. Se debe acotar el número máximo de permisos por IMP.Los permisos cargan más la red.Si se pierden permisos es difícil detectarlo y la capacidad se puede mermar notablemente por mucho tiempo.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
59 de 70
CdC por Control del Flujo• El control del flujo puede servir para controlar la congestión
indirectamente.
• A nivel de transporte el control del flujo (CdF) extremo a extremo para control de la congestión es difícil.
• El CdF no puede evitar la congestión porque el tráfico es muy irregular: teclas pulsadas frente a grandes transferencias de ficheros. El pico es mucho mayor que la tasa media.
• Desventajas:
Si el CdF limita al usuario a la tasa media el servicio será malo si es frecuente la transferencia de ficheros.
Si el CdF permite la transmisión al ritmo de los picos de uso para dar mejor servicio aparecerá congestión cuando varios usuarios pidan a ritmo de pico a la vez.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
60 de 70
CdC por Control del Flujo• El control del flujo para evitar la congestión se puede aplicar a
pares de:
Procesos de usuario (p.e. un mensaje esperando por CV como máximo).
Hosts (independientemente del número de CVs abiertos).
IMPs fuente y destino (sin importar los hosts).
• Además se podría limitar el número de CVs abiertos a la vez.
• Limitar el tráfico entre los IMPs o hosts puede aliviar indirectamente la congestión pero el precio es reducir las prestaciones aún cuando no existe peligro de congestión.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
61 de 70
CdC por Paquetes de Calma• Es un mecanismo de control que se activa cuando el sistema
presenta congestión.
• Cada IMP monitoriza el porcentaje de uso de cada una de sus líneas de salida: u ∈ [0..1]. Para actualizar este valor se toman muestras instantáneas f con valor 0 o 1 con cierta frecuencia y se modifica u en cada instante de tiempo:
unuevo = a * uantiguo + (1 - a) * f
• Si unuevo > uumbral la línea entra en estado de precaución.
• Cuando llega un paquete se chequea si su línea de salida está en precaución.
• Si es así se envía un paquete de “choque” para calmar al origen del paquete. Se activa un bit en la cabecera del paquete de datos para evitar que genere futuros paquetes de calma (estrangulamiento) y sigue hacia el destino.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
62 de 70
CdC por Paquetes de Calma• El host que recibe un paquete de calma reduce su tráfico al
destino indicado en un porcentaje X. Como puede haber enviado ya paquetes al mismo destino ignorará los futuros paquetes de calma a dicho destino durante un intervalo de tiempo fijo, tras el cual les vuelve a prestar atención si aparecen.
• Si llegan más reducirá aún más su tráfico.
• Si transcurre un tiempo de escucha sin paquetes de calma incrementará de nuevo su flujo de datos.
• Este mecanismo impide la congestión y no añade tráfico a la red hasta que realmente se necesita controlar la congestión.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
63 de 70
CdC por Paquetes de Calma• Existen algunas variantes:
Variante 1: Cada IMP mantiene dos niveles. Por encima del inferior devuelve paquetes de calma y por encima del superior descarta paquetes, ya que el host fue previamente avisado. Es difícil saber a quién se envió paquetes de calma y para qué destinos sin usar extensas tablas.
Variante 2: Usar la longitud de la cola como señal de activación usando la misma fórmula en vez del uso de la línea.
Variante 3: Los IMPs propagan información sobre congestión junto con la del encaminamiento para que las decisiones no se tomen sólo con información local a cada IMP. Esto permitiría enviar paquetes de calma antes de que aparezca congestión por una ruta determinada.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
64 de 70
Interbloqueo• El máximo exponente de la congestión es un bloqueo entre IMPs:
cada uno espera a que el otro haga algo (y así de forma cíclica).
• Lockup de envío directo: es el caso más simple. Dos IMPsesperan enviarse datos mutuamente y no les queda espacio para recibir ningún paquete del otro.
• Lockup de envío indirecto: Existe un ciclo en anillo de IMPsintentando enviar a un vecino y que no tienen sitio para recibirningún paquete del vecino en sentido inverso.
• Cuando un IMP está bloqueado también lo están todas sus líneas, incluidas las no relacionadas con el bloqueo.
• Existen diversos algoritmos para evitar el interbloqueo:Algoritmo de Merlin y Schweitzer (1980)Algoritmo de Blazewicz (1987)Bloqueo por reensamblado
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
65 de 70
Algoritmo de Merlin y Schweitzer• Se construye un grafo dirigido cuyos nodos son pares de buffers
en IMPs adyacentes. Para una red cuyos IMPs no distan más de M saltos se necesitan M+1 (desde 0 a M) buffers por IMP. Los paquetes que sigan la numeración de este grafo implícito no producirán bloqueo.
• El host envía un paquete a su IMP quien lo almacenará en el buffer 0 (si no es posible lo descarta). Después saltará a un IMP adyacente pero sólo a su buffer número 1 y así hasta el destino.
• Un paquete se descarta si llega al buffer M y no es su destino. Si M es mayor que la ruta más larga entonces se descarta porque está dando vueltas.
• El algoritmo de encaminamiento es quien determina el próximo IMP y puede ser estático o dinámico, no importa en este algoritmo.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
66 de 70
Algoritmo de Merlin y Schweitzer• Variante:
Un paquete en el buffer i puede saltar a cualquier buffer en el IMP adyacente j con un número mayor (secuencia monótona creciente). Es decir, no se exige saltar de i a i+1, sino de i a j con j>i.
• Problemas:
Se malgastan muchos buffers por ausencia de paquetes apropiados.
Las líneas estarán frecuentemente inactivas porque el paquete a enviar no tiene libre en el IMP adyacente el buffer que necesita.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
67 de 70
Algoritmo de Blazewicz• Cada paquete lleva un sello global único con el tiempo de su creación
en los bits más significativos y el número de la máquina en los menos significativos. No es necesaria la sincronización pero el algoritmo es más justo cuanto mejor sea ésta.
• Cada IMP reservará un buffer por línea de entrada para la recepción. El resto pueden contener paquetes en tránsito.
• Los paquetes se ordenan en una cola separada para cada línea de salida según su marca temporal.
• Se distinguen 3 condiciones: (si A tiene un paquete para B)
B tiene un buffer libre A envía su paquete.
B no tiene buffers libres pero tiene un paquete para A A y B intercambian sus paquetes.
B no tiene buffers libres ni paquetes para A Se fuerza a B a elegir un paquete en el sentido de A y se intercambia con A.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
68 de 70
Algoritmo de Blazewicz• Desventajas:
En teoría, un paquete podría viajar muy lejos de su destinohasta que se le encamine bien. En la práctica no ocurre excepto cuando aparece mucha congestión.
Si un “reloj” IMP se adelanta en varios segundos sus paquetes están en desventaja respecto a los de los demás. No es un gran inconveniente. Si cada par de IMPs adyacentes intercambian periódicamente sus relojes y ponen su reloj a la media de sus vecinos ninguno escapará mucho de los demás.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
69 de 70
Bloqueo por Reensamblado• Los mensajes los envía el host al IMP y requieren normalmente
ser fragmentados en paquetes para la red.
• Si parte de los fragmentos de varios mensajes llenan el espacio de almacenamiento en el IMP destino o bien los fragmentos de un mensaje llegan desordenados en número mayor al de buffers en el destino entonces el IMP destino no puede reensamblar el mensaje para entregarlo a su host ni recibir más fragmentos.
• En ARPANET el origen pide permiso al destino y éste le reserva espacio para un mensaje multi-paquete. Se podría usar un bloqueo por ventana para cada circuito virtual.
• En ARPANET el 96% son mensajes de un paquete pero usando CVs con ventanas todos los mensajes son multi-paquete. La situación se parece a la Internet globalizada.
Servicios
Propuesta OSI
Funciones
Encaminamiento
Control de Congestión
Interbloqueo
01/03/2005
Tema 2. Nivel de Red
Índice
70 de 70
Bloqueo por Reensamblado• Problemas:
Si un IMP falla e informa de que su retraso es 0, repentinamente se dirigirá el tráfico hacia él, disminuyendo las prestaciones reales.
Puede que un host falle en su identidad y se identifique como otro distinto, provocando así desvíos en la red (caos).
• Solución: hacer periódicamente chequeos de los identificadores y de las tablas.