ALOHAnet

ALOHAnet (o simplemente ALOHA) fue un sistema de redes de ordenadores pionero desarrollado en la Universidad de Hawái. Fue desplegado por primera vez en 1970, y aunque la propia red ya no se usa, uno de los conceptos esenciales de esta red es la base para la cuasi-universal Ethernet.

Visión general

Uno de los primeros diseños de redes de ordenadores, la red ALOHA, fue creada en la Universidad de Hawái en 1970 bajo la dirección de Norman Abramson. Al igual que el grupo ARPANET, la red ALOHA se construyó con fondos de DARPA.
De modo similar a ARPANET, la red ALOHA se construyó para permitir a personas de diferentes localizaciones acceder a los principales sistemas informáticos.
Pero mientras ARPANET usaba líneas telefónicas arrendadas, ALOHA usaba packet radio, esto se debía a que los diferentes centros de investigación estaban repartidos en varias islas, por lo que se buscaba un sistema de transmisión de datos inalámbrico, como las ondas de radio.

La importancia de ALOHA se basa en que usaba un medio compartido para la transmisión. Esto reveló la necesidad de sistemas de gestión de acceso como CSMA/CD, usado por Ethernet. A diferencia de ARPANET donde cada nodo sólo podía comunicarse con otro nodo, en ALOHA todos usaban la misma frecuencia. Esto implicaba la necesidad de algún tipo de sistema para controlar quién podían emitir y en qué momento. La situación de ALOHA era similar a las emisiones orientadas de la moderna Ethernet y las redes Wi-Fi.

Este sistema de transmisión en medio compartido generó bastante interés. El esquema de ALOHA era muy simple. Dado que los datos se enviaban vía teletipo, la tasa de transmisión normalmente no iba más allá de 80 caracteres por segundo. Cuando dos estaciones trataban de emitir al mismo tiempo, ambas transmisiones se enrevesaban, y los datos tenían que ser reenviados manualmente. ALOHA demostró que es posible tener una red útil sin resolver este problema, lo que despertó interés en otros estudiosos del tema, especialmente Robert Metcalfe y otros desarrolladores que trabajaban en Xerox PARC. Éste equipo crearía más tarde el protocolo Ethernet.

El protocolo ALOHA

ALOHA puro.

ALOHA puro.

ALOHA ranurado.

El protocolo ALOHA es un protocolo del nivel de enlace de datos para redes de área local con topología de difusión.

La primera versión del protocolo era básica:

• Si tienes datos que enviar, envíalos.
• Si el mensaje colisiona con otra transmisión, intenta reenviarlos más tarde.

Muchos han estudiado el protocolo. El quid de la cuestión está en el concepto de más tarde. ¿Qué es más tarde? Determinar un buen esquema de parada también determina gran parte de la eficiencia total del protocolo, y cuan determinístico será su comportamiento (cómo de predecibles serán los cambios del protocolo).

La diferencia entre ALOHA y Ethernet en un medio compartido es que Ethernet usa CSMA/CD: comprueba si alguien está usando el medio antes de enviar, y detecta las colisiones desde el emisor.

Aloha puro tiene aproximadamente un 18,4% de rendimiento máximo. Esto significa que el 81,6% del total disponible de ancho de banda se está desperdiciando básicamente debido a estaciones tratando de emitir al mismo tiempo. El cálculo básico del rendimiento implica la asunción de que el proceso de llegada de tramas sigue una distribución de Poisson con un número medio de llegadas de 2G por cada 2X segundos. Por tanto, el parámetro lambda en la distribución de Poisson será 2G. Dicho máximo se alcanza para G = 0,5, obteniendo un rendimiento máximo de 0,184, es decir, del 18,4%.

Una versión mejorada del protocolo original fue el Aloha ranurado, que introducía ranuras de tiempo e incrementaba el rendimiento máximo hasta 36,8%. Una estación no puede emitir en cualquier momento, sino justo al comienzo de una ranura, y así las colisiones se reducen. En este caso, el número promedio de llegadas es de G por cada 2X segundos. Esto disminuye el parámetro lambda a G. El rendimiento máximo se alcanza para G = 1.

Debe apreciarse que estas características de ALOHA no difieren mucho de las experimentadas hoy día con Ethernet centralizado, Wi-Fi y sistemas similares. Existe una cierta cantidad de ineficiencia inherente a estos sistemas. Por ejemplo, 802.11b otorga alrededor de 2-4 Mbps de rendimiento real con unas pocas estaciones emitiendo, en contra del máximo teórico de 11 Mbps. Es común ver cómo el rendimiento de estos tipos de redes desciende significativamente a medida que el número de usuarios y mensajes aumenta. Por ello, las aplicaciones que requieren un comportamiento altamente determinístico a menudo usa esquemas de paso de testigo (como Token Ring) en su lugar. Por ejemplo, ARCNET es muy popular en aplicaciones empotradas. No obstante, los sistemas basados en disputa (como ALOHA) también tienen ventajas significativas, incluyendo la facilidad de gestión y la velocidad en una comunicación inicial.

Debido a que los sistemas de escucha antes de enviar (CSMA), como el usado en Ethernet, trabajan mucho mejor que ALOHA para todos los casos en los que todas las estaciones pueden escuchar a cada una de las demás, sólo se usa Aloha ranurado en redes tácticas de satélites de comunicaciones del ejército de los Estados Unidos con un bajo ancho de banda.

ALOHA ranurado

Para mejorar las prestaciones de Aloha se definió Aloha ranurado (slotted) (Roberts 1972), con la única diferencia de que las estaciones sólo pueden transmitir en unos determinados instantes de tiempo o slots. De esta manera se disminuye el periodo vulnerable a t. Este sincronismo hace que cuando un terminal quiera transmitir debe esperar al inicio del nuevo periodo para hacerlo.

Observamos que la línea del tiempo esta dividida en slots, y que existen dos terminales que quieren transmitir (una representada en la parte de arriba y otra en la de abajo). En primer lugar las dos estaciones quieren transmitir, y esperan hasta el siguiente slot, produciéndose una colisión. Vuelven a intentarlo una vez más, produciéndose una nueva colisión. A partir de ahí las dos estaciones consiguen transmitir con éxito. De esta manera el número de colisiones producidas es menor que si trabajáramos con aloha simple (en el que se hubieran producido cuatro colisiones que aquí han sido transmisiones con éxito (3+4)).

Para comparar ambas técnicas partimos de unas hipótesis de partida: Modelo de una estación:

- Tenemos n estaciones independientes. - La probabilidad de generar una trama en un intervalo(t) de tipo es l*t, siendo l la tasa de tráfico de una estación.

- Las estaciones se bloquean hasta finalizar la transmisión. Modelo del canal: - Canal Semidúplex (el dúplex no se amortiza) - Todas las estaciones transmiten y reciben. Modelo de colisiones: - Solapamiento de tramas. - Todas las estaciones son capaces de detectar colisiones. - No existe otro tipo de error. - Una vez que las tramas colisionan son retransmitidas. Modelo del tiempo: - Tiempo continuo: una estación transmite en cualquier instante (Aloha simple) - Tiempo discreto: la estación sólo transmite al comienzo del slot (Aloha ranurado). Portadora: - Sistemas con detección de portadora. Los sistemas "escuchan" el canal y saben cuando está ocupado. - Sistemas sin detección de portadora. No saben cuando el canal está libre u ocupado.

Normalizaremos también los parámetros I,G y S por el tiempo de trama, de tal manera que I pertenece al intervalo [0,1].

Sabemos que el tráfico generado se distribuye según la siguiente fórmula:

P(t) = (l*t)k exp (-*t)/ k!

Siendo p(t) la probabilidad de K llegadas en un tiempo t l el tráfico generado. El tráfico cursado S= G* (1-Pcolisión) = G*Pno colisión En Aloha Simple: Donde Pno colisión = P(2tt) = (*tt)0 exp (-2*tt)/0! = 0 exp (-2*tt) siendo tt el tiempo de duración de una trama G = *tt, por lo que el tráfico cursado resulta: S= G exp (-2G) Aloha Un estudio más detallado de esta función nos hace ver que el máximo ocurre cuando G= 0.5, en el que S=0.18. Obviamente esta función está muy lejos de lo esperado idealmente. Para Aloha Ranunado, el procedimiento es el mismo, pero hay que tener en cuenta que el periodo vulnerable es la mitad, por lo que en este caso resulta S= G exp (-G) Aloha ranurado Ocurriendo el máximo cuando G=1, con un valor de S = 0.37, algo mayor que en el caso anterior (doble aproximadamente).

Historia

Norman Abramson era profesor de ingeniería en Stanford, pero también era un ávido surfista. Después de visitar Hawái en 1969, preguntó a la Universidad de Hawái si estaban interesados en contratar a un profesor de ingeniería. Se incorporó a la plantilla en 1970 y comenzó a trabajar en un sistema de comunicaciones de datos basado en radio para interconectar las islas hawaianas, con fondos de Larry Roberts.

A finales de 1970 el sistema ya se estaba utilizando, la primera red de paquetes conmutados inalámbrica del mundo. Abramson logró entonces conseguir un IMP de Roberts y conectó ALOHAnet a ARPANET en el continente en 1972. Fue la primera vez que otra red se conectaba a ARPANET, aunque otras lo harían más tarde.

Descripción

Antes de ALOHAnet, la mayoría de las comunicaciones entre computadoras tendían a utilizar rasgos similares. Los datos que iban a ser enviados se convertían en una señal analógica utilizando un mecanismo similar a un módem, que sería enviada sobre un método de conexión conocido, como podría ser una línea telefónica. La conexión era punto a punto, y normalmente se establecía de modo manual.

Por el contrario, ALOHAnet era una auténtica red. Todas las computadoras conectadas a ALOHAnet podían enviar datos en cualquier momento sin necesidad de intervención por parte de un operador, y se podía ver envuelto cualquier número de computadoras. Como la transmisión se realizaba por radio, no había costes fijos, por lo que el canal se dejaba abierto y se podía utilizar en cualquier momento.

Usar una señal compartida de esta manera conlleva un importante problema: si dos sistemas en la red (conocidos como nodos) enviaban al mismo tiempo, ambas señales se estropearían. Era necesario algún tipo de sistema para evitar este problema. Existen varios modos de hacerlo.

Uno sería utilizar una frecuencia de radio diferente para cada nodo, sistema conocido como multiplexación en frecuencia. Comoquiera que este sistema requiere que cada nodo que se añada sea capaz de sintonizarse con el resto de máquinas, pronto se necesitarían cientos de frecuencias distintas y radios capaces de escuchar este número de frecuencias al mismo tiempo, lo que sería demasiado costoso.

Otra solución es tener ranuras de tiempo asignadas a cada nodo para enviar, lo que se conoce como multiplexación por división de tiempo. Este sistema es más fácil de implementar, dado que los nodos pueden seguir compartiendo una única frecuencia de radio. El inconveniente es que si un nodo en particular no tiene nada que enviar, su ranura estaría siendo desperdiciada. Esto nos lleva a situaciones en las que el tiempo disponible está vacío en gran parte y un nodo con datos que enviar lo tendría que hacer muy despacio por si acaso alguno de los otros 100 nodos decidiera enviar algo.

En cambio, ALOHAnet utilizó una nueva solución al problema, que más tarde se convertiría en el estándar, el Acceso múltiple por detección de portadora. En este sistema no hay multiplexación fija en absoluto. En su lugar, cada nodo escucha para saber si alguien está utilizando el canal, y si no escucha a nadie comienza a emitir.

Normalmente esto significaría que el primer nodo que empiece a transmitir tendría la posesión del medio por tanto tiempo como quisiera, lo que supone que los otros nodos no podrían tomar parte en la comunicación. Para evitar este problema, ALOHAnet hizo que los nodos partieran sus mensajes en pequeños paquetes, y que los enviasen de uno en uno y dejando huecos entre ellos. Esto permitía a los otros nodos enviar sus paquetes entre medias, por lo que todo el mundo podía compartir el medio al mismo tiempo.

Existe un último problema a considerar: si dos nodos intentan comenzar su transmisión al mismo tiempo, tendrán los mismos problemas que tendrían en cualquier otro sistema. En este caso, ALOHAnet inventó una solución muy inteligente. Después de enviar cualquier paquete, los nodos escuchaban el medio para saber si su propio mensaje les había sido devuelto por un hub central. Si recibían de vuelta su mensaje, podían avanzar al siguiente paquete.

Si, en cambio, no recibían su paquete de vuelta, eso significaría que algo había impedido que llegase al hub (posiblemente una colisión con un paquete de otro nodo). En ese caso, simplemente debería esperar un tiempo aleatorio e intentarlo de nuevo. Como cada nodo esperaría un tiempo aleatorio, alguno debería ser el primero en reintentarlo, y el resto de nodos podrían ver que el canal está en uso al intentar emitir. En la mayoría de los casos, esto serviría para evitar las colisiones.

Este tipo de sistema de prevención de colisiones tiene la ventaja de permitir a cualquier nodo usar la capacidad total de la red si ningún otro nodo la está usando. Además, no necesita inicialización, cualquiera puede conectarse y comenzar a emitir sin establecer información adicional como la frecuencia o la ranura temporal a usar.

El inconveniente es que, si la red está saturada, el número de colisiones puede crecer drásticamente hasta el punto de que todos los paquetes colisionen. Para ALOHAnet el uso máximo del canal estaba en torno al 18%, y cualquier intento de aumentar la capacidad de la red simplemente incrementaría el número de colisiones, y el rendimiento total de envío de datos se reduciría, fenómeno conocido como colapso por congestión.

Con Aloha ranurado, un reloj centralizado envía pequeños paquetes con la señal de reloj a las estaciones periféricas. Las estaciones sólo tienen permitido enviar sus paquetes inmediatamente después de recibir la señal de reloj. Si hay una sola estación con intención de emitir un paquete, esto garantiza que nunca habrá una colisión para ese paquete. Por otra parte, si hay dos estaciones con paquetes para enviar, este algoritmo garantiza que habrá una colisión y se malgastará toda la ranura de tiempo hasta la siguiente señal de reloj. Con algunas matemáticas es posible demostrar que este protocolo mejora la utilización total del canal, reduciendo la probabilidad de colisiones a la mitad.

La relativamente baja utilización resulta ser un pequeño precio a pagar a cambio de las ventajas. Una ligera modificación de este sistema para redes con conectadas (con cables) realizada por Robert Metcalfe mejoró la prevención de colisiones en redes saturadas, y se convirtió en el estándar para Ethernet. Hoy en día la técnica es conocida como CSMA/CD, Acceso Múltiple con Detección de Portadora y Detección de Colisiones.

Los mecanismos de detección de colisiones son mucho más difíciles de implementar en sistemas inalámbricos en comparación con los sistemas cableados, y ALOHA no intentó siquiera comprobar las colisiones. En un sistema cableado, es posible detener la transmisión de paquetes que colisionen, detectando primero la colisión y notificándolo a continuación al remitente. En general, esta no es una opción viable en sistemas inalámbricos, por lo que ni siquiera se intentó en el protocolo ALOHA.

ALOHAnet se ejecutaba usando módems de 9.600 baudios de un extremo a otro de Hawái. El sistema usaba dos canales (secciones de frecuencia) de 100 kHz: uno conocido como canal de emisión a 413'475 MHz; y el otro, canal de acceso aleatorio a 407'350 MHz. La red tenía una topología de estrella, con un único computador central (un HP 2100) en la universidad que recibía todos los mensajes en el canal de acceso aleatorio, y reenviándolos entonces a todos los nodos por el canal de emisión. Este montaje reducía el número posible de colisiones, ya que no había colisiones en absoluto en la frecuencia de emisión, por lo que merecía la pena. Posteriores mejoras añadieron repetidores que también actuaban como hubs, incrementando enormemente el área y la capacidad total de la red.

Los paquetes enviados y recibidos eran idénticos. Cada paquete tenía una cabecera de 32 bits con un test de paridad de 16 bits, seguidos de hasta 80 bytes de datos con otros 16 bits de test de paridad.

Los detalles históricos sobre la red inalámbrica original son ahora bastante difíciles de obtener.

Referencias

• NCommunications, Proceedings of Fall Joint Computer Conference, AFIPS Conference, 1970 http://www.isoc.org/internet/history/brief.shtml

Enlaces externos

• Dynamic Sharing of Radio Spectrum: A Brief History (pdf en inglés)
• http://www.nap.edu/readingroom/books/far/ch7.html (en inglés)
• http://www.laynetworks.com/ALOHA%20PROTOCOL.htm (en inglés)
• http://research.microsoft.com/~gbell/Computer_Structures_Principles_and_Examples/csp0432.htm (en inglés)