6 EL NIVEL DE RED: GENERALIDADES

El principal objetivo de la capa de red es encaminar los paquetes del origen al destino. Esta es la única capa que ‘ve’ y conoce la topología de la red, que está formada por dos tipos de nodos:

o Nodos terminales: generan o reciben paquetes de otros nodos, nunca encaminan paquetes dirigidos a terceros.

o Nodos intermedios o de encaminamiento: se utilizan para encaminar paquetes entre los nodos terminales. Suelen ser ordenadores especializados dedicados y diseñados específicamente para esa función, con sistemas operativos en tiempo real, aunque en ocasiones también se utilizan para desempeñar esta función ordenadores normales.

La terminología de estos dos tipos de nodos es muy diversa y varía según el tipo de red y la ‘cultura’ de que se trate. La tabla 2.1 refleja las denominaciones más habituales, aunque la terminología no se sigue a rajatabla.

Tipo de nodo	Internet (IP)	X.25	ATM	ISO
Nodo terminal	Host	DTE (Data Terminating Equipment)	Host	End System (ES)
Nodo intermedio o de encaminamiento	Router o Gateway (obsoleta)	DCE (Data Communications Equipment)	Conmutadores o Switches	Intermediate System (IS)

Tabla 2.1.- Denominación de los dos tipos de nodos posibles en diferentes redes

A veces un mismo equipo desempeña ambas funciones a la vez, en diferentes redes. Por ejemplo si se utiliza una red ATM para interconectar routers IP éstos actuarán como nodos terminales (hosts) en la red ATM mientras que para la red IP serán routers.

Por otro lado, en ocasiones los nodos intermedios son origen o destino de los paquetes; por ejemplo un router en una red IP o un conmutador en una red ATM que participan en un protocolo de routing tienen que intercambiar información con sus homólogos; lo mismo ocurre cuando han de emitir o recibir mensajes de control, tales como avisos de congestión, reportar situaciones anómalas o errores que se producen por diversos motivos; en estos casos esos routers o conmutadores actúan como nodos terminales ya que son la fuente o destino de la información.

La denominación conmutador resulta particularmente confusa, pues se utiliza comúnmente para referirse al menos a tres tipos diferentes de dispositivos de comunicaciones, a saber:

Conmutadores LAN: los dispositivos ya descritos que conmutan tramas en base a la información contenida en la cabecera MAC. Actúan por tanto a nivel de enlace.

Conmutadores ATM: son los dispositivos que conmutan celdas ATM, que actúan a nivel de red.

Conmutadores de nivel 3: como su nombre indica estos dispositivos actúan a nivel de red, pero a diferencia de los conmutadores ATM lo hacen con protocolos no orientados a conexión, como IP e IPX. Se trata por tanto de routers, siendo su única diferencia respecto de estos la implementación en hardware de los algoritmos de enrutamiento más habituales, con lo que resultan especialmente rápidos [1]. Esta denominación suele emplearse sobre todo cuando la función de router está integrada en un dispositivo que también actúa como puente LAN. En este contexto también se hace alusión a veces a los conmutadores de nivel 2, para referirse a los conmutadores LAN.

Dado que su función es interconectar redes los nodos intermedios tienen normalmente varias interfaces físicas, y los nodos terminales normalmente una. Aunque poco frecuente (y poco útil) un nodo intermedio puede tener una sola interfaz; más frecuente es el caso en que un nodo terminal tiene varias interfaces por razones de rendimiento o fiabilidad. Cuando un nodo terminal tiene varias interfaces decimos que está 'multihomed'.

En cada interfaz física de un nodo funciona una instancia independiente del nivel físico y del nivel de enlace; por el contrario el nivel de red es normalmente global para todo el nodo. En IP cada interfaz física tiene una dirección de red diferente, al menos (puede tener varias).

Los nodos intermedios junto con las líneas que los unen constituyen la subred (recordemos que la subred es la frontera entre el usuario y el proveedor del servicio).

En una LAN broadcast (por ejemplo Ethernet) todos los nodos terminales comunican directamente entre sí, sin necesidad de nodos intermedios, por lo que la capa de red es prácticamente inexistente (esto incluye el caso en que la LAN incluya puentes o conmutadores de cualquier tipo). A cambio el nivel de enlace tiene una complejidad mayor (subcapa MAC y puentes).

Los puentes MAC, en especial los puentes por encaminamiento desde el origen, desempeñan una función hasta cierto punto equivalente a la de un router.

Los servicios que ofrece el nivel de red deberán en lo posible aislar al nivel de transporte de detalles tales como tipo de tecnología física utilizada (LAN, WAN, broadcast, etc.), número y topología de las subredes, etc. Las direcciones de red deberán tener un formato homogéneo, cualquiera que sea el medio físico o subred utilizados.

Los servicios de red pueden ser orientados a conexión (CONS) o no orientados a conexión (CLNS). Ejemplos de servicios CLNS son el protocolo IP, el ISO CLNS elaborado a imagen y semejanza de IP, y el IPX desarrollado por Novell para su sistema operativo en red Netware. Ejemplos de servicios CONS son X.25, Frame Relay y ATM. En los capítulos siguientes hablaremos en detalle de IP, Frame Relay y ATM.

La características principales de un servicio CLNS son:

o Se implementan las primitivas SEND PACKET y RECEIVE PACKET, y poco más.

o No se garantiza el orden de llegada de los datagramas.

o Cada datagrama ha de llevar la dirección de destino. Cada uno ha de averiguar la ruta por sí mismo.

o Cada router ha de mantener una tabla que indique por que interfaz debe encaminar los paquetes en función de su destino, pero no conserva información de las conexiones (pues no las hay); se dice que el router no tiene estados o que es 'stateless'.

o Si un router de la red queda fuera de servicio la única consecuencia será la pérdida de los datagramas que estuvieran en proceso allí en ese momento, no se pierde ninguna información sobre la conexión, ya que no había conexión; el resto de routers de la red intentará buscar una ruta alternativa para comunicarse.

o Es difícil llevar a cabo un control de congestión, u ofrecer una QoS (Quality of Service, calidad de servicio).

Las principales características de un servicio CONS son:

o Las dos entidades finales (hosts) establecen primero la conexión de forma explícita (un circuito virtual o VC) y le asignan un identificador. Esta conexión se utiliza para enviar todos los datos y luego se libera, también de forma explícita.

o El orden de entrega de los paquetes está garantizado.

o Los paquetes no necesitan llevar la dirección de destino (pero sí el número del VC por el que van a viajar). La ruta está marcada por el VC mientras éste está establecido. Cada nodo intermedio (conmutador) ha de tomar nota de los VCs existentes en cada momento (decimos que tiene estados o que es 'statefull'). Cada conmutador ha de mantener una tabla que le indique la interfaz de entrada y de salida para cada VC que pasa por él.

o Si un conmutador queda fuera de servicio desaparecerán todos los VCs que pasen por él en ese momento, y los nodos afectados dejarán de comunicar (aunque podrán establecer un nuevo VC si hay un camino alternativo); la información de los VCs no estará presente cuando el conmutador vuelva a entrar en servicio (salvo que se trate de PVCs).

o Es fácil efectuar un control de congestión, y también asegurar una QoS, ya que se tiene una información exacta de que conexiones discurren por cada línea física en cada momento.

En una red CLNS el nivel de transporte es normalmente más complejo pues ha de desempeñar mas funciones que en una red CONS.

Una red CONS puede ser fiable (X.25) o no fiable (Frame Relay o ATM), mientras que una red CLNS normalmente es no fiable [2]. Generalmente cuando se quiere un servicio fiable en una red CLNS se implementa un servicio CONS a nivel de transporte; este es el caso por ejemplo cuando se utiliza el transporte TCP (CONS) sobre una red IP (CLNS).

En este capítulo veremos en primer lugar las funciones principales del nivel de red y la forma como normalmente se realizan. En el siguiente veremos en detalle el funcionamiento del nivel de red de IP, tanto en lo que respecta al protocolo IP mismo como a los protocolos de control y de routing. Continuaremos con el nivel de red en Frame Relay y ATM que tienen algunos puntos en común.

6.2 ALGORITMOS DE ENCAMINAMIENTO

La función fundamental de la capa de red es el enrutamiento o encaminamiento, es decir averiguar por que interfaz se han de mandar los paquetes recibidos para que lleguen a su destino. Con redes basadas en datagramas esta decisión se toma para cada paquete y el nodo que la realiza se denomina router o encaminador. Con redes orientadas a conexión (basadas en circuitos virtuales) la decisión se toma en el momento de establecer el circuito virtual, y a partir de entonces solo se ‘conmutan’ paquetes, de ahí la denominación de conmutador. Se supone que la conmutación es una tarea sencilla y que puede hacerse con extrema rapidez, pues no requiere tomar complejas decisiones.

Para poder encaminar los paquetes es preciso primero conocer cual es la ruta a seguir hacia el destino especificado. El mecanismo que nos permite elegir la ruta a utilizar para posible destino es lo que denominamos un algoritmo de encaminamiento o de routing. Además de otras importantes virtudes un algoritmo de routing debe ser óptimo y justo. Estos conceptos a veces se contraponen, ya que el algoritmo que permite un aprovechamiento óptimo de los recursos no siempre es el que ofrece el reparto más equitativo.

Podemos dividir los algoritmos de routing en dos grandes grupos, estáticos y dinámicos. Los algoritmos de routing estático toman las decisiones utilizando información previamente recopilada sobre el estado de la red; en cambio los algoritmos de routing dinámico utilizan información recopilada en tiempo real sobre el estado de la red; dicha información se actualiza constantemente mediante paquetes de control que intercambian los routers a través de la misma red.

En el encaminamiento o routing estático las rutas se fijan en función de la capacidad de la línea, el tráfico medio u otros criterios similares. Las tablas de rutas se cargan de forma estática en cada router, por lo que no se necesita intercambiar información y por tanto no se requiere un protocolo de routing. Con el encaminamiento estático no es posible responder a situaciones cambiantes (p. ej. saturación, exceso de tráfico o fallo de una línea). En el encaminamiento estático los cálculos de las rutas óptimas se llevan a cabo en diferido, por lo que es posible aplicar algoritmos tan sofisticados como se quiera aun cuando requieran gran cantidad de recursos de cálculo o de memoria.

En cambio en el encaminamiento o routing dinámico las rutas óptimas se recalculan continuamente en función de la información que los routers reciben en tiempo real sobre el estado de la red. Es preciso utilizar un protocolo de routing que permita a los routers intercambiar continuamente esa información, pero a cambio se consigue un mecanismo autoadaptativo que puede responder a situaciones cambiantes intentando resolver los problemas que se produzcan. Los algoritmos no pueden ser demasiado complejos, pues han de implementarse en los routers y ejecutarse en tiempo real con los recursos de CPU y memoria de que el router dispone.

Haciendo un símil con un viaje en coche podríamos decir que el encaminamiento estático equivale a planificar la ruta para un viaje en coche antes de salir de casa utilizando los mapas y nuestro conocimiento a priori sobre el estado de las carreteras y la densidad de tráfico habitual en éstas; en cambio con encaminamiento dinámico iríamos fijando la ruta sobre la marcha en base a la información que obtuviéramos por radio, o de los puestos de información, sobre el estado de las carreteras, pudiendo así reaccionar a situaciones cambiantes tales como atascos, accidentes, puertos cerrados, fenómenos atmosféricos, etc. En el primer caso no intercambiamos ninguna información durante el viaje, mientras que en el segundo sí.

6.2.1 El principio de optimalidad

Aunque parezca una perogrullada es un principio fundamental para los algoritmos de encamiamiento que podemos enunciar así:

Si B está en la ruta óptima de A a C, entonces el camino óptimo de B a C está incluido en dicha ruta.

Una consecuencia importante de este principio es que todas las rutas óptimas para llegar a un punto determinado en una red forman un árbol con raíz en el punto de destino. El árbol no contiene bucles, decimos que es un spanning tree y siempre es posible llegar al punto de destino en un número finito de saltos ('hops').

6.2.2 Encaminamiento por el camino más corto y métricas

Existen diversos algoritmos que permiten calcular el camino más corto entre dos nodos de un grafo. Uno de los mas conocidos es debido a Dijkstra.

Esta técnica se utiliza tanto en routing estático como dinámico.

Para saber elegir el camino más corto primero debemos definir que entendemos por distancia. Es evidente que en redes telemáticas no tiene mucho sentido emplear la distancia física. En los casos más simples la distancia se mide como el número de saltos o ‘hops’ (hop = salto en inglés); a mayor número de saltos mayor distancia. Evidentemente esto es satisfactorio únicamente en casos muy simples en que todos los enlaces tiene la misma capacidad. Normalmente la ‘distancia’ se calcula a partir de uno o varios de los siguientes parámetros:

o La capacidad del enlace (información estática)

o El tráfico medio (puede ser información estática o dinámica)

o El retardo (información dinámica medida a partir de los paquetes enviados)

o La fiabilidad (información dinámica medida a partir de los paquetes enviados)

Combinando de determinada forma estos parámetros se calcula una cantidad que será la ‘distancia’ utilizada en el cálculo de las rutas óptimas. A menudo a esa distancia se la denomina métrica. La forma de calcular la métrica se elige al configurar el router, pero es importante que sea consistente en todos los routers que participan en el protocolo de routing ya que de lo contrario se pueden dar situaciones asimétricas generalmente absurdas.

Cuando el parámetro utilizado para el cálculo de la distancia es invariable con el tiempo (por ejemplo capacidad del enlace) puede aplicarse a un algoritmo de encaminamiento estático. Se calculan todas las rutas y se elige la óptima para cada caso; una vez realizado este proceso se cargan dichas rutas en la configuración de los routers.

Si se emplean parámetros dinámicos (por ejemplo el tráfico medio o la fiabilidad) debe utilizarse un algoritmo dinámico. En este caso la información se propaga en toda la red y los cálculos se hacen de manera descentralizada entre todos los routers.

6.2.3 Encaminamiento basado en el flujo

Este algoritmo toma en cuenta la cantidad de tráfico medio que soportan las líneas, y en base a esta información intenta optimizar el conjunto de las rutas para utilizar el camino menos congestionado en cada caso.

Para aplicarlo se ha de conocer la matriz de tráfico entre los nodos y es conveniente que tráfico sea regular. Esto se puede obtener a partir de medidas de tráfico real o, si esto no es posible, en base a estimaciones lo más aproximadas posible. Se pueden aplicar algoritmos relativamente sofisticados ya que el cálculo de rutas se hace offline y se carga en el router después como rutas estáticas. Puede ser útil para diseñar la topología de una red, por ejemplo si se conectan una serie de oficinas con enlaces punto a punto se pueden plantear diversas topologías y estudiar cual es la más adecuada; también es útil cuando se trata de PVCs Frame Relay o ATM. Este tipo de estudios y optimizaciones forman parte de lo que se conoce como ingeniería de tráfico.

6.2.4 Encaminamiento por inundación ('flooding')

La inundación consiste en enviar cada paquete por todas las interfaces, excepto por la que se ha recibido. Esta es la técnica que se aplicaba en las tramas de descubrimiento en los puentes por encaminamiento desde el origen y también en los puentes transparentes cuando la dirección de destino era desconocida.

La inundación puede multiplicar el tráfico si existen bucles en la topología, ya que en ese caso se envían paquetes duplicados. En el caso extremo la red puede llegar a bloquearse, como ocurría en los puentes transparentes para lo cual se desarrolló el protocolo spanning tree. Aparte del spanning tree, que es una solución drástica a este problema (puesto que sencillamente bloquea los caminso redundantes) existen dos posibles soluciones, a saber:

Incorporar en el paquete un campo contador decremental de saltos, de forma que su valor se reduzca en uno con cada salto y que cuando dicho campo sea cero el paquete se descarte. El valor inicial deberá ser adecuado para garantizar que el paquete llegará a todos los rincones de la red.

Identificar todos los paquetes de manera no ambigua (por ejemplo numerándolos) para que cada router mantenga una lista de los paquetes enviados; así puede evitar reenviarlos de nuevo; la lista no necesita ser exhaustiva, basta con indicar por ejemplo ‘recibidos del router X todos los paquetes hasta el 1900, y además el 1912 y 1915’.

Para limitar este problema los paquetes se fija un número máximo de saltos, que suele ser igual al número de saltos que hay entre los dos puntos más alejados de la red (decimos que ese número de saltos constituye el tamaño o diámetro de la red).

También puede usarse inundación selectiva. En este caso el paquete se envía sólo por las líneas que aproximadamente apuntan en la dirección correcta; por ejemplo si estamos en Madrid y el paquete va hacia Córdoba se enviará por las líneas que van al sur solamente.

La inundación es importante porque se utiliza como mecanismo para distribuir la información de routing en algunos algoritmos de routing que veremos y también en algunos algoritmos de routing multicast.

6.2.5 Encaminamiento por vector distancia

Este algoritmo se aplica en diversos protocolos de routing. También se conoce como algoritmo de Bellman-Ford o Ford-Fulkerson, que fueron los autores de la idea.

En el encaminamiento por vector distancia cada router mantiene una tabla o vector que le indica la distancia mínima conocida hacia cada posible destino y que línea o interfaz debe utilizar para llegar a él. La tabla se actualiza regularmente con información obtenida de los routers vecinos. Cada router manda la tabla completa de distancias a todos sus vecinos, y solo a ellos. A partir de la información que tiene y la recibida de sus vecinos cada router recalcula continuamente su tabla de distancias.

La métrica (el valor utilizado para elegir la ruta óptima) puede ser número de saltos, retardo, paquetes encolados, etc., o una combinación de estos u otros parámetros. Para medir el retardo el router puede enviar paquetes de prueba que deben ser respondidos por el router remoto, aunque también es frecuente que los retardos se asignen de acuerdo con un convenio preestablecido en función del tipo de interfaz y de la capacidad del enlace, sin hacer ninguna medida real sobre el terreno. Cada router sólo conoce el valor de los parámetros para los enlaces con sus vecinos, los valores correspondientes a enlaces más lejanos los conoce de manera indirecta en base a la información sumarizada que sus vecinos le facilitan.

En el routing por vector distancia las noticias buenas se propagan rápidamente, pero se reacciona lentamente a las malas. Esto se conoce como el problema de la cuenta a infinito. Se han ideado multitud de trucos para resolver este problema, pero para cada nueva propuesta se ha encontrado una situación patológica en la que falla. No existe al parecer una solución definitiva a este problema, si bien la combinación de varios de esos ‘trucos’ parece dar un resultado más que aceptable en la práctica. A pesar de sus inconvenientes el algoritmo del vector distancia se utiliza aun bastante en la actualidad, y tiene fervientes partidarios sobre todo debido a su sencillez y consiguiente economía de recursos.

El algoritmo del vector distancia fue utilizado en la ARPANET original. También se utilizó en DECNET e IPX, y se usa en Appletalk. Se usa actualmente en el protocolo RIP (Routing Information Protocol), que hasta 1988 era el único protocolo de routing utilizado en Internet. También se utiliza en los protocolos propietarios IGRP y EIGRP de Cisco, ampliamente extendidos.

6.2.6 Encaminamiento por el estado del enlace

El algoritmo de encaminamiento basado en el estado del enlace se conoce también como algoritmo de Dijkstra o algoritmo SPF (Shortest Path First).

Este algoritmo apareció como un intento de resolver los problemas que planteaba el encaminamiento por vector distancia, fundamentalmente el de la cuenta a infinito. Se trata de un algoritmo mas sofisticado y robusto, pero también más complejo. Su funcionamiento se describe mejor dividiéndolo en cuatro fases:

1. Descubrir los routers vecinos y averiguar sus direcciones.

2. Medir el retardo o costo de llegar a cada vecino

3. Construir un paquete que resuma toda esta información, y enviarlo a todos los routers de la red

4. Calcular el camino mas corto a cada router

Veamos con más detalle cada una de ellas:

1. Para darse a conocer cada router cuando arranca envía paquetes de presentación (HELLO) por todas sus interfaces; los paquetes HELLO son respondidos con mensajes identificativos por los routers que los reciben.

2. Para conocer el retardo de sus enlaces el router envía paquetes de prueba (ECHO) que son respondidos por los routers remotos; de esta forma el router puede medir el tiempo de ida y vuelta, del que puede deducirse el retardo.

3. Con la información obtenida el router construye un paquete de información (denominado LSP, Link State Packet) y lo envía a todos los routers de la red. Para ello utiliza inundación. Los paquetes se numeran para detectar y descartar duplicados, e ignorar paquetes obsoletos (por ejemplo si llega el paquete 26 después de haber recibido el 28 se ignora y se descarta). Además cada paquete tiene una vida limitada, al cabo de la cual es también descartado.

4. Con toda la información obtenida el router construye el árbol de expansión de las rutas óptimas a cada destino de la red aplicando el algoritmo de Dijkstra (inventado por Edsgar Dijkstra). De esta forma conoce la topología de la red.

En el routing por el vector distancia cada router envía información sólo a sus vecinos, pero esta información incluye a todos los nodos de la red. En cambio en el routing por el estado del enlace cada router envía su LSP a toda la red, pero éste solo contiene información relativa a sus vecinos más próximos. En el algoritmo basado en el estado del enlace cada router puede, a partir de la información obtenida, conocer su árbol de expansión o spanning tree completo, mientras que esto no es posible con routing por el vector distancia.

La distribución de los LSPs merece un comentario especial. Como hemos dicho, una vez distribuida la información de los LSPs en toda la red y convergida la topología cada router conoce perfectamente el árbol de expansión que le corresponde. Cabría pensar entonces en optimizar la distribución de los LSPs, haciéndola de acuerdo con dicho árbol de expansión en lugar de utilizar inundación. Sin embargo si en ese caso se produjera un fallo de alguno de los enlaces del árbol los LSPs no se distribuirían en toda la red, quedando esta dividida en dos. La red quedaría parcialmente fuera de servicio y se habría perdido una de las ventajas principales de utilizar un protocolo de routing, que es la posibilidad de reaccionar a los cambios en la topología debidos a fallos de la red. Por otro lado el uso de la inundación para distribuir los LSPs es menos problemático de lo que a primera vista podría parecer, ya que gracias a la detección de LSPs duplicados que realizan los routers el máximo número de veces que un mismo LSP puede pasar por un mismo enlace es de dos, y en muchos casos solo pasa una vez por cada enlace.

El algoritmo del estado del enlace no tiene el problema de la cuenta a infinito, es más robusto y fiable, pero también es más complejo, requiere mayor cantidad de cálculos y por tanto una CPU más potente y mayor cantidad de memoria RAM en el router.

Entre los protocolos de routing que utilizan algoritmos basados en el estado del enlace se encuentra OSPF (Open Shortest Path First) que es el protocolo de routing estándar de Internet (aunque también se utilizan otros). Otro protocolo basado en el algoritmo del estado del enlace también utilizado en Internet y que proviene del mundo OSI es IS-IS (Intermediate System-Intermediate System). IS-IS es multiprotocolo, es decir, soporta múltiples protocolos de red por encima. OSPF esta basado en IS-IS, pero no es multiprotocolo.

6.2.7 Encaminamiento jerárquico

Aplicamos encaminamiento jerárquico en la decisión de la ruta óptima cuando planificamos un viaje largo por carretera. Por ejemplo para ir en coche de Valencia a Bruselas utilizamos un mapa detallado de España y Bélgica, pero no empleamos normalmente un mapa detallado de Francia, nos basta con uno de las carreteras principales de ese país.

A medida que una red telemática crece la cantidad información de routing aumenta de forma no lineal, ya que cada router ha de calcular sus rutas óptimas a todos los demás. Generalmente el aumento en el número de routers de una red viene acompañado de un aumento aún mayor en el número de enlaces que los unen, lo cual hace crecer el número de vectores distancia o el tamaño de los LSP. El tráfico de routing en la red aumenta y lo mismo ocurre con la CPU y memoria consumida en los routers para realizar los cálculos necesarios para obtener las rutas óptimas. En resumen, los algoritmos de routing no son escalables [3].

Para resolver este problema muchos protocolos de routing contemplan la posibilidad de establecer dos o más niveles jerárquicos; la red se divide en regiones, y sólo un número reducido de routers de cada región (los routers interregionales) puede comunicar con el exterior. Las rutas pueden no ser tan óptimas en algún caso, pero se simplifica la gestión y el mantenimiento de las tablas de routing y se reduce el tráfico en la red debido al protocolo de routing.

6.2.8 Encaminamiento broadcast

En algunos casos se necesita enviar un paquete a todos los destinos posibles en una red, es decir se quiere hacer un envío broadcast.

La forma más sencilla de conseguirlo es inundación, técnica especialmente apropiada en este caso que ya hemos descrito en detalle anteriormente.

Otro método es el routing multidestino, que consiste en mandar un único paquete con todas las direcciones de destino; el paquete es replicado en cada router por las interfaces por donde debe enviarse, es decir, las que son parte de la mejor ruta para alguno de los destinos indicados.

Otro algoritmo es construir el árbol de expansión o spanning tree con raíz en el origen y seguirlo, replicando el paquete allí donde haya una bifurcación. El spanning tree no tiene bucles. Este sistema es óptimo, ya que se asegura que la distribución se hará generando el número mínimo de paquetes y sin envíos duplicados. Pero esto requiere que cada router conozca cuales de sus interfaces forman parte del spanning tree para el router origen y cuales no, es decir los routers han de conocer en detalle la topología de la red. Con routing del estado del enlace los routers poseen esta información.

Por último el algoritmo de encaminamiento por el camino inverso o RPF (Reverse Path Forwarding) es en cierto modo una aproximación o una versión simplificada del spanning tree que se puede aplicar cuando se tiene información parcial de la topología, como en el caso de los algoritmos basados en el vector distancia. El mecanismo es el siguiente: el router examina la dirección origen del paquete recibido, y la interfaz por la que le ha llegado; si esa interfaz es la que el router tiene identificada como el camino más corto para llegar a la dirección de origen se considera bastante probable que el paquete no sea un duplicado, por lo que lo reenviará por todas las interfaces, excepto por aquella por la que vino; si la interfaz por la que llegó el paquete no es la indicada para enviar paquetes a dicha dirección de origen se considera que se trata de un duplicado y se descarta. Esta técnica realiza dos envíos extra por cada posible bucle en la red, es decir consigue una eficiencia bastante buena aunque no es óptima ya que se generan algunos envíos duplicados. Además parte de la suposición de que las rutas óptimas son siempre simétricas; si esta condición no se cumple el algoritmo no funciona.

6.2.9 Encaminamiento multicast

El problema del encaminamiento multicast tiene dos partes: por un lado la gestión de los grupos multicast y por otro el encaminamiento multicast propiamente dicho.

Para el envío de paquetes multicast primero hay que crear un grupo multicast. Una vez creado el grupo los usuarios pueden unirse a él (join) o abandonarlo (leave). Las tareas de gestión del grupo son el objeto de un protocolo de gestión de grupos que es independiente del routing multicast.

Cuando un usuario (o más exactamente un proceso que depende de un host conectado a un router), se une a un grupo multicast debe informar a su router y éste informará de ello a sus vecinos.

Dentro de una red local sin routers que la dividan (una Ethernet conmutada, por ejemplo) el envío de paquetes multicast resulta especialmente sencillo, ya que al tener una topología plana desde el punto de vista del routing los paquetes simplemente se envían al medio físico y serán captados por todas aquellas estaciones que pertenezcan a ese grupo multicast. Como el tráfico multicast atraviesa los conmutadores los usuarios podrán unirse al grupo desde cualquier parte de la red local.

En una red con routers (una red de área extensa por ejemplo) la situación es mucho más compleja: los routers que constituyen el grupo multicast forman un árbol de distribución (spanning tree) con raíz en el router donde se encuentra el emisor de dicho tráfico multicast. Cuando un host quiere unirse a un grupo multicast notifica a su router, el cual solicita entonces unirse al grupo multicast correspondiente, es decir solicita ser añadido al árbol de distribución multicast (salvo que el router ya estuviera en el árbol, en cuyo caso solo toma nota del nuevo host interesado en el grupo y no manda ningún mensaje al exterior). Cuando más tarde el usuario quiere abandonar el grupo enviará un nuevo mensaje a su router indicándoselo; en este momento el router pedirá a su vez al siguiente en el árbol que le corte el flujo multicast que había pedido (suponiendo que no haya entonces ningún otro usuario dependiente de dicho router que quiera seguir participando en el grupo multicast). La labor de cortar la distribución multicast se conoce como 'pruning' o podado del árbol [4]. El objetivo del podado es dejar en el árbol sólo las ramas necesarias para hacer llegar el tráfico multicast a aquellos routers que tienen usuarios que forman parte del grupo multicast.

Un mismo grupo multicast puede tener varias fuentes, es decir varios emisores, en cuyo caso existirá un árbol de distribución diferente para cada fuente. Además una misma fuente puede emitir simultáneamente en varios grupos multicast. En principio un emisor en un grupo multicast no tiene por que ser miembro de dicho grupo; sin embargo por la forma como se desarrollan las aplicaciones multicast y como funcionan sus protocolos de control asociados en la práctica el emisor de un grupo multicast es también miembro de dicho grupo y viceversa, es decir los miembros en principio solo receptores de un grupo son también emisores, si bien ocasionales, del mismo.

Como puede intuirse por los aspectos comentados en este apartado el routing multicast es algo bastante más complejo que el routing unicast, más incluso que el routing broadcast, debido en buena medida al control que los routers han de mantener de los hosts activos en cada grupo en su red local. Esto obliga a los routers a mantener una cierta información de estado que si no responde rigurosamente a la realidad acaba por degradar completamente el servicio. Esta ha sido la principal causa de que el routing multicast siga siendo aun hoy en día un servicio experimental poco extendido en Internet.

6.3 ALGORITMOS DE CONTROL DE CONGESTIÓN

Denominamos congestión a la circunstancia en la que el rendimiento de la red (o una parte de ella) se degrada.

Un ejemplo típico de congestión sería la situación en la que un router con varias líneas de 2 Mb/s recibe tráfico entrante por todas ellas dirigido a una sola. Inicialmente el router intentará salvar la situación utilizando sus buffers, pero si la situación dura lo suficiente los buffers se llenarán y el router empezará a descartar paquetes Normalmente la congestión se produce por tráfico excesivo, pero también puede producirse por un router sobrecargado o de capacidad insuficiente para el tráfico que soporta (CPU lenta).

Conviene no confundir la congestión con el control de flujo, aunque ambas estén relacionadas. A diferencia de la congestión el control de flujo es una circunstancia que solo se da en conexiones punto a punto a nivel de enlace o a nivel de transporte. Una de las posibles consecuencias del control de congestión es ejercer control de flujo sobre el nodo o nodos que están produciendo la congestión.

La congestión es generalmente un problema más complejo que el control de flujo, ya que generalmente el emisor del tráfico es un router, es decir un intermediario que no tiene el control de la situación. Lo más que puede hacer un router es enviar un mensaje de control de congestión; a menudo para cuando el mensaje llega al verdadero causante de la congestión el tráfico ya ha cesado, con lo que resulta inútil tomar medidas. Este problema se acentúa especialmente en redes de alta velocidad y elevado retardo (gran distancia).

6.3.1 Principios generales del control de congestión

Para el control de la congestión caben dos planteamientos:

o Diseñar las cosas desde el principio para que la congestión no pueda llegar a ocurrir (medicina preventiva).

o Tomar medidas que permitan detectar la congestión y adoptar medidas correctoras en su caso (medicina curativa).

La primera técnica es mas segura, pero puede provocar ineficiencias si se aplican las limitaciones con demasiada severidad. La segunda permite aprovechar mejor la red, pero en caso de congestión puede ser difícil controlar la situación.

Entre los parámetros que permiten detectar la presencia de congestión se encuentran los siguientes:

A nivel de red:

o Porcentaje de paquetes descartados

o Longitud media de las colas en las interfaces de los routers

A nivel de transporte:

o Retardo medio por TPDU (Transport Protocol Data Unit)

o Desviación media del retardo por TPDU (jitter)

o Número de TPDUs que se pierden o dan timeout y se retransmiten (se supone que esto no se debe a errores)

Para informar sobre situaciones de congestión el receptor pueden utilizar paquetes de alerta generados a propósito o incluir la información en un campo especial de los paquetes de datos (aviso 'piggybacked'). También puede el emisor enviar paquetes de sondeo para averiguar el estado de la red.

Para resolver la congestión solo hay dos posibles medidas:

o Reducir el tráfico solicitando al emisor que pare de enviar.

o Aumentar la capacidad; a corto plazo esto puede hacerse por ejemplo activando canales RDSI o buscando rutas alternativas; a más largo plazo será preciso contratar enlaces de más capacidad o enlaces adicionales.

6.3.2 Factores que pueden influir en la congestión

Podemos encontrar factores que influyen en la congestión de una red en el nivel de enlace, el nivel de red y el nivel de transporte.

Entre los factores a nivel de enlace que pueden influir en la congestión se encuentran:

o El intervalo de timeout; si es pequeño originará retransmisiones innecesarias

o El tamaño de ventana; si es grande es más fácil que se produzca congestión

o El uso de retroceso n o repetición selectiva; el retroceso n genera más tráfico

o El uso o no de ACK piggybacked; si no se usa se genera más tráfico

Todos estos factores suponen la existencia a nivel de enlace de un protocolo orientado a conexión, es decir que solicita confirmación mediante ACK de los envíos realizados. Dado que hoy en día esto no es normal en la práctica el nivel de enlace tiene poco que ver con la congestión.

En el nivel de red los factores que influyen en la congestión son los siguientes:

o Servicio CONS vs CLNS, o uso de circuitos virtuales vs datagramas :hay mejor control de la congestión cuando se trata de circuitos virtuales.

o Mecanismos de encolamiento y criterios de selección y priorización de paquetes (Calidad de Servicio).

o Mecanismos de descarte de paquetes: a veces hay paquetes marcados como candidatos a la hora de descartar.

o Algoritmo de routing: si contempla la posibilidad de utilizar caminos alternativos quizá sea posible evitar una zona congestionada.

o Vida media de los paquetes, o timeout: si el valor es muy pequeño los paquetes tendrán que ser retransmitidos, si es excesivo serán descartados cuando lleguen y se habrán transmitido inútilmente.

En el nivel de transporte se dan básicamente los mismos factores que en el nivel de enlace; la principal diferencia está en la estimación del timeout adecuado, que es mucho más difícil al no tratarse de una comunicación entre entidades vecinas.

6.3.3 Perfiles de tráfico y vigilancia de tráfico ('traffic shaping' y 'traffic policing')

El tráfico a ráfagas es la principal causa de congestión. Si todos los ordenadores transmitieran siempre un flujo constante sería muy fácil evitar la congestión.

Los perfiles de tráfico (traffic shaping) establecen unos márgenes máximos al tráfico a ráfagas. Suelen utilizarse para fijar una Calidad de Servicio (Quality of Service, QoS) entre el operador y el usuario; entretanto el usuario respete lo establecido el operador se compromete a no descartar paquetes; el perfil de tráfico actúa pues como un contrato que vincula a ambas partes.

Se denomina vigilancia de tráfico (traffic policing) a la labor de monitorización o seguimiento del tráfico introducido por el usuario en la red para verificar que no excede el perfil pactado.

Uno de los sistemas más utilizados para establecer perfiles de tráfico es el conocido como algoritmo del pozal agujereado (leaky bucket): el host puede enviar ráfagas que son almacenadas en un buffer en la interfaz o conmutador de acceso a la red, de forma que la red recibe siempre un caudal constante; si la ráfaga es de tal intensidad o duración que el buffer (pozal) se llena, los paquetes excedentes son descartados, o bien son enviados a la red con una marca especial que les identifica como de ‘segunda clase’ (hasta cierto punto podríamos decir que son paquetes ‘ilegales’); dichos paquetes de segunda clase serán los primeros candidatos a descartar en caso de congestión, puesto que se supone que el usuario que los envió era consciente de que estaba ‘infringiendo las reglas’ y que por tanto viajaban sin garantías. Esta técnica se utiliza en ATM y en Frame Relay y se está experimentando su utilización en IP.

Para definir un pozal agujereado se utilizan dos parámetros: r especifica el caudal con que sale el flujo a la red, y C indica la capacidad del buffer. Por ejemplo supongamos que con un pozal agujereado de r=20 Mb/s y C= 10 Mbits un ordenador envía una ráfaga de 10 Mbits en 50 mseg (equivalente a 200 Mb/s), con lo cual casi 'llena' el pozal; la ráfaga tardará en enviarse a la red 500 mseg; momento en el que el pozal se vaciará. Si el ordenador envía otra ráfaga de 10 Mbits antes de que el pozal se haya vaciado por completo el buffer se llenará y se perderán los paquetes excedentes, o bien se enviarán marcados como descartables.

El pozal agujereado resuelve el problema de las ráfagas en la red, pero no estimula el ahorro. Supongamos dos hosts, A y B, ambos con pozales agujereados de r=20 Mb/s y C= 10 Mbits; el host A lleva una hora transmitiendo a la red con un caudal constante de 20 Mb/s, mientras que el segundo lleva una hora sin transmitir. De repente los dos hosts tienen necesidad de emitir una ráfaga y como ambos hosts tienen su pozal vacío los dos se encuentran en igualdad de condiciones, es decir al host B no le ha beneficiado en nada el menor consumo de recursos que ha hecho durante la hora anterior. El algoritmo del pozal con crédito (token bucket) es una versión mejorada del pozal agujereado que intenta resolver este problema, premiando al host inactivo (B en nuestro ejemplo) frente al que esta siempre transmitiendo (A). El mecanismo que sigue para ello es el siguiente: cuando el host no envía datos el pozal va sumando créditos (tokens) hasta un máximo igual a C, la capacidad del buffer; el crédito se acumula a la misma velocidad con que se vacía el pozal, es decir con un caudal igual al parámetro r; cuando hay tráfico el crédito acumulado puede utilizarse para enviar ráfagas con un caudal M mayor de lo normal; cuando se agota el crédito el caudal vuelve a su valor normal r y el algoritmo funciona como un pozal agujereado. Un detalle sutil a tener en cuenta es que mientras se consumen los créditos (es decir, mientras sale tráfico con caudal M) también se acumula crédito con un caudal r. Una vez agotado todo el crédito, cuando el funcionamiento revierte al de un pozal agujereado normal, deja de acumularse crédito entretanto esté saliendo tráfico a la red con el caudal r. Podemos imaginar el pozal con crédito como un pozal dotado de dos agujeros, uno pequeño (r) y uno grande (M), con un dispositivo mecánico que permite abrir uno u otro, pero no ambos a la vez; el agujero grande se abre cuando el usuario tiene crédito; cuando lo agota se cierra y se abre el agujero pequeño; el usuario acumula crédito siempre que el pozal no esté enviando tráfico por el agujero pequeño, bien porque tenga abierto el grande (y tenga por tanto cerrado el pequeño) o porque no haya tráfico que enviar. Los parámetros que definen un pozal con crédito son el caudal del agujero pequeño r, la capacidad del buffer C y el caudal del agujero grande M (normalmente igual a la velocidad de la interfaz física).

Supongamos que r=20 Mb/s, C= 10 Mbits y M = 200 Mb/s y que como en el ejemplo anterior el host envía una ráfaga de 10 Mbits en 50 mseg. Supongamos también tres posibles situaciones del pozal: a) lleno de créditos (10 Mbits), b) medio lleno de créditos (5 Mbits) y c) sin créditos. En el primer caso, si el buffer está lleno de créditos cuando llega la ráfaga ésta será enviada a la red a 200 Mb/s, o sea a la misma velocidad con que la envía el host. Si el buffer está solo medio lleno (5 Mbits de créditos) se producirá una ráfaga de 200 Mb/s durante 27,78 mseg y seguirá un caudal de 20 Mb/s durante 222,2 mseg (hay que tomar en cuenta que durante los primeros 27,78 mseg siguen llegando créditos pues esta cerrado el agujero pequeño, pero no después ya que se van consumiendo a medida que llegan). Por último, si no hubiera créditos disponibles cuando llegara la ráfaga el comportamiento sería idéntico al del pozal agujereado.

Quizá merece la pena comentar como se calcula el valor de 27,78 mseg del ejemplo anterior para el caso del pozal medio lleno de créditos. Sabemos que mientras esta abierto el agujero grande el pozal suma créditos a una velocidad de 20 Mb/s; por tanto el total de créditos obtenidos en un tiempo t será:

créditos totales = créditos iniciales + créditos acumulados = 5.000.000 + 20.000.000 * t

Por otro lado, sabemos que mientras está abierto el agujero grande los créditos se consumen a razón de 200 Mb/s, o sea:

créditos consumidos = 200.000.000 * t

Para calcular cuanto tiempo estará abierto el agujero grande igualamos las dos expresiones anteriores:

5.000.000 + 20.000.000 * t = 200.000.000 * t

De donde despejando obtenemos para t el valor de 0,02778 seg

El pozal con crédito supone una mejora respecto al pozal agujereado por cuanto que distingue entre un usuario que ha estado transmitiendo y otro que no ha transmitido nada, pero tiene el inconveniente de que mientras hay crédito inyecta tráfico en la red con un caudal M que normalmente coincide con la capacidad de la interfaz física, lo cual puede resultar excesivo en ocasiones. Para dosificar esta avalancha a veces se combina un pozal con crédito seguido de un pozal agujereado de r mayor, con lo que se permiten esas ráfagas pero de forma más controlada. Por ejemplo si el pozal con crédito del ejemplo anterior (r=20 Mb/s, C= 10 Mbits y M = 200 Mb/s) se combina con un pozal agujereado de r=50 Mb/s y C= 10 Mbits el resultado para cada uno de los tres supuestos anteriores será como sigue:

a) La ráfaga es enviada a la red a 50 Mb/s.

b) Se envía una ráfaga de 50 Mb/s durante un tiempo t donde t se calcula a partir de la siguiente fórmula:

Bits enviados a 50 Mb/s = Bits recibidos a 200 Mb/s + Bits recibidos a 20 Mb/s

que aplicada a este caso resulta:

50.000.000 * t = 0,02778 * 200.000.000 + (t – 0,02778) * 20.000.000

Despejando obtenemos un valor de t de 0,16668, por lo que la ráfaga de 50 Mb/s será de 166,7 ms, que irá seguida de un flujo de 20 Mb/s durante 83,3 ms, hasta completar el envío de los 10 Mb.

c) Al no haber crédito en el pozal en este caso la ráfaga se envía toda a 20 Mb/s por lo que el segundo pozal no tiene efecto en este caso.

6.3.4 Control de admisión

El control de admisión se aplica únicamente a las redes orientadas a conexión y consiste en evitar el establecimiento de nuevos circuitos virtuales que pasen por una zona de la red que se considera congestionada. Si se conoce la capacidad máxima que necesita cada circuito virtual en principio es posible controlar el acceso de forma que nunca se produzca congestión. Generalmente un control de admisión estricto no usa los recursos de manera eficiente ya que al reservar para cada circuito la capacidad máxima la red se encuentra infrautilizada la mayor parte del tiempo, por lo que a veces se preve un cierto grado de sobresuscripción, u 'overbooking' (de forma parecida a las compañías aéreas cuando venden mas billetes que el número de asientos disponibles en el avión).

La red telefónica es un ejemplo extremo de control de admisión; en esta red se asigna y reserva un circuito de 64 Kb/s en el momento de establecer el circuito, para cada comunicación telefónica; la posibilidad o no de comunicación depende exclusivamente de la disponibilidad de recursos en el momento de establecer la comunicación. Gracias a este control de admisión estricto la red telefónica no tiene nunca problemas de congestión, aunque esta ventaja se consigue a costa de un derroche de recursos y un sobredimensionamiento de la red.

6.3.5 Paquetes de alerta

Los paquetes de asfixia se puede aplicar tanto en redes de circuitos virtuales como de datagramas.

En esta técnica el router o conmutador comprueba regularmente cada una de sus líneas, monitorizando por ejemplo la carga relativa (nivel de ocupación) o la longitud de las colas en las interfases. Cuando el parámetro inspeccionado supera un determinado valor considerado umbral de peligro se envía un paquete de alerta al host considerado 'culpable' para que reduzca el ritmo.

Los paquetes de alerta tienen el riesgo de producir comportamientos oscilantes, ya que cuando se percibe una situación peligrosa se envían avisos que pueden bloquear a todos los emisores; más tarde al detectar que el problema está resuelto se pide reanudar los envíos, con lo que hay riesgo de caer nuevamente en la situación de alerta, y así sucesivamente. Este problema se resuelve en parte haciendo que el router reaccione con cierta inercia a los cambios que se producen en el parámetro monitorizado; para ello se suelen utiliza fórmulas del tipo:

u_n = au_n-1 + (1-a) f

donde f es el valor más reciente del parámetro medido (grado de utilización del enlace, por ejemplo), u_n el valor medio en la n-ésima iteración, y a una constante que permite regular el peso que se le quiere dar a los valores anteriores, o dicho de otro modo regular la rapidez con que se reaccionará a situaciones cambiantes. Cuanto mayor sea el valor de a mas lenta será la respuesta a los cambios. De este modo se evita responder a cambios momentáneos que harían mas mal que bien en el rendimiento de la red. Por ejemplo con a = 0,5 el valor actual sería la media aritmética entre el último valor instantáneo y el valor promedio anterior (que a su vez era la media aritmética entre el penúltimo valor instantáneo y el valor promedio anterior, y así sucesivamente).

Normalmente los paquetes de alerta se envían a los hosts que generan el tráfico, ya que son éstos y no los routers los verdaderos causantes de la congestión. Los hosts cuando reciben estos paquetes suelen reducir (por ejemplo a la mitad) la velocidad con la que envían datos a la red. Esto lo pueden hacer de varias maneras, por ejemplo reduciendo el tamaño de ventana del protocolo a nivel de transporte o cambiando los parámetros del pozal agujereado o del pozal con crédito, si utilizan alguno de estos algoritmos para controlar el flujo. En una situación de congestión normalmente muchos hosts recibirán este tipo de paquetes.

En ocasiones interesa que los paquetes de alerta tengan un efecto inmediato en cada uno de los routers por los que pasan en su camino hacia el host que provoca la congestión. De esta forma la congestión se reduce de forma inmediata, distribuyendo el tráfico en ruta entre los buffers de los routers que hay en el camino entretanto el mensaje de alerta llega al host que genera el tráfico. Esto es especialmente importante cuando se trata de una conexión de alta velocidad y elevado retardo.

Por desgracia la obediencia a los paquetes de alerta es completamente voluntaria. Si un host obedece las indicaciones y reduce su ritmo mientras otro no lo hace el primero saldrá perjudicado pues obtendrá una parte aún menor de la ya escasa capacidad disponible. No es posible obligar a los hosts a obedecer las indicaciones de los paquetes de alerta.

En situaciones de saturación se plantea el problema de como repartir la capacidad disponible de forma justa entre los usuarios. Existen varios algoritmos que intentan resolver este problema, por ejemplo:

o Encolamiento justo (fair queuing): el router mantiene una cola independiente por cada host y envía los paquetes en turno rotatorio ('round robin'). Aquí se da un problema parecido al de Ethernet, ya que el reparto es equitativo en paquetes por host por unidad de tiempo; en este caso los usuarios o aplicaciones que manejan paquetes grandes obtienen más recursos que los que manejan paquetes pequeños. Una versión mejorada de este algoritmo intenta hacer un reparto equitativo en número de bytes (o bits) transmitidos por host por unidad de tiempo.

o Encolamiento justo ponderado (weighted fair queuing): es similar al anterior, pero permite además establecer prioridades, ya que en ocasiones interesa dar más prioridad a algunos hosts (por ejemplo servidores) o a algún tipo de tráfico (aplicaciones en tiempo real). La prioridad se puede establecer por direcciones, por tipo de aplicación o por una combinación de estos u otros factores. Además de prioridades también se pueden reservar capacidades para ciertas direcciones o aplicaciones, por ejemplo ‘reservar el 30% de la capacidad para el servidor ftp’ o ‘reservar el 20% de la capacidad para paquetes provinientes de la dirección IP 147.156.1.1’.

6.3.6 Descarte de paquetes

El último recurso para resolver un problema de congestión es descartar paquetes. Esto evidentemente ayuda a reducir la congestión puesto que se reduce el tráfico en la red, pero además del alivio inmediato que supone el descarte de paquetes hay un efecto a más largo plazo debido a que en muchos casos los protocolos de transporte incorporan mecanismos de autorregulación que entran en funcionamiento cuando se detecta la pérdida de algún paquete. El ejemplo más claro en este sentido lo constituye TCP, que se basa en este mecanismo implícito de notificación para detectar y resolver las situaciones de congestión. Actualmente este es prácticamente el único mecanismo de control de congestión que funciona con carácter general en la Internet.

El descarte de paquetes puede dar lugar en ciertas circunstancias a situaciones oscilantes por razones similares a las comentadas al hablar de los paquetes de alerta. Supongamos que como consecuencia de la congestión el router descarta paquetes de muchos hosts a la vez; todos los hosts a los que se les haya descartado siquiera sea un paquete detectarán esta circunstancia y todos ellos bajarán drásticamente su ritmo de emisión de paquetes. Al ver que ya no se pierden más paquetes los hosts irán recuperando paulatinamente la confianza hasta que llegará un momento en que se repita la situación de congestión y se produzca de nuevo el descarte masivo, con lo que los hosts disminuirán de nuevo a ritmos mucho más conservadores. Como consecuencia de este comportamiento se producen situaciones cíclicas en las que se alternan unos períodos de congestión con otros de baja actividad en los que la red está infrautilizada. Como cabría esperar el resultado es nefasto desde el punto de vista del rendimiento de la red. La solución a este problema, que se viene utilizando desde hace varios años en los routers del ‘core’ de Internet, consiste en descartar paquetes mucho antes de que los indicadores de congestión lleguen a tener valores peligrosos, pero no descartar muchos paquetes sino solo algunos correspondientes a hosts elegidos al azar; de esta forma el aviso de congestión llega solo a una parte de los hosts que reducen su caudal de tráfico, pero la mayoría sigue normalmente. Esta técnica, conocida como RED [5], permite un aprovechamiento mucho más eficiente de los enlaces.

En ocasiones los paquetes llevan alguna indicación de su grado de importancia, en cuyo caso los routers intentan descartar los menos importantes primero. Por ejemplo, sería bastante grave si un router para resolver una situación de congestión descartara paquetes de alerta.

A veces el nivel de aplicación puede dar información sobre la prioridad de descarte de los paquetes. Por ejemplo en aplicaciones isócronas (audio y vídeo en tiempo real) suele ser preferible descartar el paquete viejo al nuevo ya que el viejo seguramente es inútil, mientras que en transferencia de ficheros ocurre lo contrario pues el receptor necesita recibirlos todos y el más antiguo causará antes retransmisión por agotamiento del timeout. En los ficheros MPEG [6], debido a la técnica de compresión utilizada algunos fotogramas son completos (los denominados fotogramas intra) y otros son diferencias respecto a los anteriores y/o posteriores (llamados fotogramas predictivos y bidireccionales); descartar un paquete perteneciente a un fotograma intra es más perjudicial para la calidad de la imagen que descartar uno de un fotograma predictivo o bidireccional, ya que el defecto repercutirá en todos los fotogramas que dependan de él . En ATM y Frame Relay existen situaciones en las que el usuario puede inyectar en la red un caudal superior al contratado, pero dicho tráfico excedente puede ser descartado en caso de congestión; para esto los conmutadores ATM y Frame Relay 'marcan' los paquetes o celdas que entran por encima del caudal pactado. Si la aplicación no marca ningún paquete como descartable la red marcará automáticamente aquellos que superen el caudal pactado, que podrían ser precisamente los más importantes para la aplicación. En vez de dejar en manos de la red tan importante decisión la aplicación puede especificar que paquetes deben marcarse como descartables porque sabe que son menos importantes. En cualquier caso la red se asegurará de que el tráfico no descartable inyectado nunca supere el caudal contratado.

En algunos casos el paquete transmitido por la red es parte de una secuencia correspondiente a otro paquete de mayor tamaño que viaja fragmentado. En estos casos si se descarta un paquete cualquiera de la secuencia se tendrá que reenviar todo el grupo, por lo que en caso de descartar uno es conveniente descartar todos los demás ya que son tráfico inútil. Un buen ejemplo de esto se da cuando se utiliza una red ATM para transportar datagramas IP; generalmente cada datagrama ocupa varias celdas ATM (los datagramas IP sobre ATM pueden llegar a tener una longitud de 9180 bytes, por lo que un paquete IP se puede llegar a ocupar hasta 192 celdas ATM). Si se descarta una sola celda de un datagrama ya no tiene sentido enviar el resto. La mayoría de los conmutadores ATM actuales implementan las técnicas conocidas como Early Packet Discard y Partial Packet Discard consistentes en que el conmutador realiza un descarte inteligente de celdas cuando transporta datagramas IP, es decir si se detecta que una celda perteneciente a un datagrama IP ha sido descartada automáticamente se descartan todas las demás celdas pertenecientes al mismo datagrama. Los conmutadores que no implementan estas técnicas sufren una mayor merma de rendimiento cuando se produce algún descarte de celdas. En una experiencia con un conmutador ATM de primera generación (que no disponía de descarte inteligente de celdas) se probó a inyectar por una línea E3 (34,368 Mb/s) un caudal IP ligeramente superior a la capacidad de la línea, con lo que se producía un cierto descarte de celdas; el resultado fue el que se muestra en la tabla 2.2.

Caudal inyectado (Mb/s)	Celdas perdidas (%)	Rendimiento UDP (Mb/s)
34	0,0	29,9
35	0,8	2,8
36	4,0	0,005

Tabla 2.2.- Rendimiento obtenido para tráfico UDP/IP

en un conmutador ATM sin descarte inteligente de celdas.

Como puede verse el efecto sobre el rendimiento es dramático. Esta experiencia se realizó con el protocolo de transporte UDP. De haber utilizado TCP el propio mecanismo de control de congestión que incorpora este protocolo habría forzado una autorregulación del tráfico con lo que la merma de rendimiento habría sido mucho menor.

6.4 EJERCICIOS

1. Indique si es verdadera o falsa cada una de las siguientes afirmaciones:

a) Los protocolos de routing basados en el estado del enlace emplean algoritmos mas complejos que los basados en el vector distancia, pero a cambio permiten obtener un detalle completo de la topología de la red.

b) La principal ventaja de utilizar múltiples niveles jerárquicos en un protocolo de routing estriba en la posibilidad de elegir la ruta óptima en cada caso.

c) La transmisión multicast optimiza el uso de las líneas de transmisión, al permitir que múltiples usuarios reciban un mismo flujo de datos enviados desde una fuente.

d) La noción de router 'stateless' (sin estados) está asociada a protocolos de red no orientados a conexión (p. ej. IP o CLNP).

e) En general los protocolos de red orientados a conexión (Frame Relay o ATM por ejemplo) permiten controlar mejor las situaciones de congestión que los no orientados a conexión, (IP o CLNP por ejemplo).

2. Cuando se estudian mecanismos de control de congestión en una red de ordenadores existen muchos paralelismos con los problemas de tráfico en las grandes ciudades; incluso algunas técnicas son comunes a ambas situaciones. Indique un mecanismo aplicado en el control de congestión de redes telemáticas que nunca será implementado (afortunadamente) en las vías públicas.

3. Una empresa dispone de una aplicación de audioconferencia (telefonía sobre Internet) y desea utilizarla para mantener reuniones regulares entre dos oficinas, las cuales disponen de sendas redes locales unidas entre sí por dos routers y una línea de 128 Kb/s; la línea tiene unos niveles de ocupación elevados a ciertas horas del día y su velocidad no puede aumentarse por problemas presupuestarios; afortunadamente el nivel de ocupación en dicha línea sigue un perfil muy regular en función de la hora del día, y se dispone de una gráfica que muestra el tráfico medio para cada hora del día.

La aplicación de audioconferencia codifica la voz con un sistema de compresión que genera un paquete de 164 bytes (incluidas las cabeceras a nivel de red) cada 40 milisegundos; para que la voz llegue de forma comprensible y sea posible la interactividad es preciso que el retardo medio no supere los 80 milisegundos.

Indique cual es el grado de ocupación (en Kb/s y en %) por encima del cual no merece la pena intentar establecer la audioconferencia, ya que esta no podrá celebrarse en condiciones aceptables.

Considere que todo el trafico por la línea esta formado por paquetes de 164 bytes.

Suponga ahora que la empresa decide sustituir la línea de 128 Kb/s por una línea de 2048 Kb/s. ¿Cual sería en ese caso el grado de ocupación máximo tolerable (en Kb/s y en %) para poder celebrar la audioconferencia?

6.5 SOLUCIONES

S1.-

a) Verdadera. El routing basado en el vector distancia solo permite saber cual es el siguiente nodo en el camino óptimo para cada destino, pero se desconoce la ruta, solo se sabe la distancia. En routing basado en el estado del enlace cada nodo sabe la mejor ruta a cada destino, con lo que dispone de un 'mapa' completo de la red; esto requiere algoritmos mas complejos de cálculo de las rutas, pero permite un routing mas robusto.

b) Falsa. La razón de establecer niveles jerárquicos es reducir la cantidad de información que maneja el protocolo de routing, pero esto puede hacer que las rutas no sean óptimas ya que cada nodo no 've' toda la red.

c) Verdadera.

d) Verdadera. Un router sin estados no ha de recordar nada relativo a las conexiones que pasan por él.

e) Verdadera. Al ser orientados a conexión pueden ejercer control de admisión, cosa que no es factible en los protocolos de red no orientados a conexión. Además pueden aplicar todas las técnicas habituales en éstos.

S2.-

El descarte de paquetes.

S3.-

Tamaño de los paquetes: 164 bytes = 1312 bits

Por teoría de colas sabemos que el retardo viene dado por:

retardo (en segundos) = 1 / (pps_max - pps_real)

Donde pps_max representa el número máximo de paquetes por segundo que pueden circular por la línea, y pps_real es el número de paquetes que están circulando.

En nuestro caso la línea es de 128 Kb/s, por lo que

pps_max= 128000 / 1312 = 97,56 pps

La audioconferencia emite un paquete cada 40 ms, o sea 25 paquetes por segundo (1/0,04). Si la audioconferencia ha de compartir la línea con un tráfico de x paquetes por segundo generado por otras aplicaciones el tráfico real (pps_real)será de x+25, por lo que para que el retardo no supere los 80 ms deberá cumplirse:

0,08 = 1 / (97,56 - x - 25)

Despejando obtenemos que x = 60,06 pps; con paquetes de 1312 bits esto equivale a 78,8 Kb/s, o una ocupación del 61,6%. Por encima de esta ocupación no debería celebrarse la audioconferencia.

En el caso de una línea de 2048 Kb/s los cálculos serían como sigue:

pps_max= 2048000 / 1312 = 1560,98 pps

0,08 = 1 / (1560,98 - x - 25)

En este caso el valor umbral es de 1523 pps, equivalente a 1998,8 Kb/s o una ocupación del 97,6%. Por tanto con la línea de 2 Mb/s se puede tener un nivel de ocupación mucho mayor manteniendo el mismo retardo que en la línea de baja velocidad.

[1] Llegados a este punto es justo indicar que en la actualidad muchos routers altos de gama también implementan en hardware los algoritmos de enrutamiento para los casos más normales.

[2] En este contexto entendemos por fiable que garantiza la entrega.

[3] Decimos que algo (un servicio, algoritmo, etc.) no es escalable cuando un incremento en las condiciones de partida (número de usuarios, cantidad de variables, etc.) requiere incrementar en mayor proporción los recursos asociados (para proveer el servicio, resolver el algoritmo, etc.). Por ejemplo en nuestro caso duplicar el número de routers hace aumentar en un factor superior a dos el tráfico de routing y la complejidad de los cálculos. En el caso de servicios a veces se considera que un aumento lineal no es suficiente, es decir, para que el servicio se pueda calificar de escalable es preciso que los recursos puedan crecer en una proporción menor, o mucho menor, que el número de usuarios.

[4] Podar = ‘to prune’ en inglés.

[5] El mecanismo RED fue inventado por Cisco. Inicialmente los ingenieros se referían a este acrónimo como Random Early Discard, ya que en esencia lo que hacía era descartar paquetes; sin embargo los especialistas de marketing consideraron que reconocer abiertamente que sus routers descartaban paquetes podía perjudicar la imagen de la marca. Por este motivo las siglas se mantuvieron, pero cambiando el significado oficial de la D a ‘Detect’ (Random Early Detect), lo cual bien pensado resulta aún peor, ya que parece indicar que la pronta detección de las situaciones de congestión se producirá de forma aleatoria, lo cual resultaría preocupante en caso de ser cierto. Aunque no guste a los especialistas de marketing incluso los mejores routers de Cisco (como los de cualquier otra marca) descartan paquetes cuando sufren congestión y sus buffers se llenan.

[6] MPEG es el formato estándar ISO de vídeo digital comprimido.