ALOHAnet , también conocido como Sistema ALOHA , [1] [2] [3] o simplemente ALOHA , fue un sistema de redes informáticas pionero desarrollado en la Universidad de Hawái . ALOHAnet comenzó a funcionar en junio de 1971, proporcionando la primera demostración pública de una red inalámbrica de datos por paquetes . [4] [5]
ALOHAnet utilizaba un nuevo método de acceso al medio, llamado acceso aleatorio ALOHA , y una frecuencia ultraalta (UHF) experimental para su funcionamiento. En su forma más simple, conocida posteriormente como ALOHA puro, las unidades remotas se comunicaban con una estación base (Menehune) a través de dos frecuencias de radio independientes (para la entrada y la salida, respectivamente). Los nodos no esperaban a que el canal estuviera libre antes de enviar, sino que esperaban el acuse de recibo de un mensaje y lo volvían a enviar si no lo recibían. Los nodos también se detenían y retransmitían datos si detectaban otros mensajes durante la transmisión. Aunque es sencillo de implementar, esto da como resultado una eficiencia de solo el 18,4 %. Un avance posterior, ALOHA ranurado, mejoró la eficiencia del protocolo al reducir la posibilidad de colisión, mejorando el rendimiento al 36,8 %.
ALOHA se empleó posteriormente en la red basada en cable Ethernet en la década de 1970, y tras los desarrollos regulatorios de principios de la década de 1980 se hizo posible utilizar las técnicas de acceso aleatorio ALOHA tanto en Wi-Fi como en redes de telefonía móvil. Los canales ALOHA se utilizaron de forma limitada en la década de 1980 en teléfonos móviles 1G para fines de señalización y control. A fines de la década de 1980, el grupo de estandarización europeo GSM que trabajó en el sistema de comunicación móvil digital paneuropeo GSM expandió en gran medida el uso de canales ALOHA para acceder a canales de radio en telefonía móvil. A principios de la década de 2000 se agregaron canales ALOHA adicionales a los teléfonos móviles 2.5G y 3G con la introducción generalizada del Servicio General de Radio por Paquetes (GPRS), utilizando un canal de acceso aleatorio ALOHA con ranuras combinado con una versión del esquema ALOHA de reserva analizado por primera vez por un grupo de BBN Technologies .
La red ALOHA, uno de los primeros diseños de redes informáticas, se inició en septiembre de 1968 en la Universidad de Hawái bajo la dirección de Norman Abramson y Franklin Kuo , junto con Thomas Gaarder, Shu Lin, Wesley Peterson y Edward ("Ned") Weldon. El objetivo era utilizar equipos de radio comerciales de bajo coste para conectar a los usuarios de Oahu y de las demás islas hawaianas con una computadora central de tiempo compartido en el campus principal de Oahu. La primera unidad de transmisión de paquetes entró en funcionamiento en junio de 1971. Los terminales se conectaron a una unidad de conexión de terminales de propósito especial utilizando RS-232 a 9600 bit/s. [6]
ALOHA era originalmente un acrónimo inventado que significaba Additive Links On-line Hawaii Area. [7]
La versión original de ALOHA utilizaba dos frecuencias distintas en una configuración de concentrador: la máquina central transmitía paquetes a todos los usuarios del canal de salida y las distintas máquinas cliente enviaban paquetes de datos al concentrador por el canal de entrada . Si los datos se recibían correctamente en el concentrador, se enviaba un breve paquete de confirmación al cliente; si una máquina cliente no recibía una confirmación después de un breve tiempo de espera, retransmitía automáticamente el paquete de datos después de esperar un intervalo de tiempo seleccionado al azar. Este mecanismo de confirmación se utilizaba para detectar y corregir las colisiones que se creaban cuando dos máquinas cliente intentaban enviar un paquete al mismo tiempo.
La principal importancia de ALOHAnet fue el uso de un medio compartido para las transmisiones de los clientes. A diferencia de ARPANET , donde cada nodo sólo podía comunicarse con un único nodo en el otro extremo de un cable o circuito satelital, en ALOHAnet todos los nodos clientes se comunicaban con el concentrador en la misma frecuencia. Esto significaba que se necesitaba algún tipo de mecanismo para controlar quién podía hablar y en qué momento. La solución de ALOHAnet fue permitir que cada cliente enviara sus datos sin controlar cuándo se enviaban e implementar un esquema de reconocimiento/retransmisión para lidiar con las colisiones. Este enfoque redujo radicalmente la complejidad del protocolo y del hardware de red, ya que los nodos no necesitan negociar quién puede hablar.
Esta solución se conoció como ALOHA puro, o canal de acceso aleatorio, y fue la base para el posterior desarrollo de Ethernet y, posteriormente, de las redes Wi-Fi . [5] Varias versiones del protocolo ALOHA (como Slotted ALOHA) también aparecieron más tarde en las comunicaciones por satélite , y se utilizaron en redes de datos inalámbricas como ARDIS , Mobitex , CDPD y GSM .
La red Aloha introdujo el mecanismo de acceso múltiple aleatorio, que resolvía las colisiones de transmisión de dispositivos transmitiendo un paquete inmediatamente si no había acuse de recibo y, si no se recibía acuse de recibo, la transmisión se repetía después de un tiempo de espera aleatorio. [8] La distribución de probabilidad de este tiempo de espera aleatorio para la retransmisión de un paquete que no ha sido reconocido como recibido es de importancia crítica para la estabilidad de los sistemas de comunicación de tipo Aloha. El tiempo de espera promedio para la retransmisión es típicamente más corto que el tiempo promedio para la generación de un nuevo paquete desde el mismo nodo cliente, pero no se debe permitir que sea tan corto como para comprometer la estabilidad de la red, causando un colapso en su rendimiento general. [9]
También fue importante el uso que ALOHAnet hizo del canal saliente del concentrador para transmitir paquetes directamente a todos los clientes en una segunda frecuencia compartida y usar una dirección en cada paquete para permitir la recepción selectiva en cada nodo cliente. [4] Se usaron frecuencias separadas para las comunicaciones entrantes y salientes al concentrador para que los dispositivos pudieran recibir reconocimientos independientemente de las transmisiones.
La versión original del protocolo (ahora llamada Pure ALOHA, y la implementada en ALOHAnet) era bastante simple:
ALOHA puro no comprueba si el canal está ocupado antes de transmitir. Dado que pueden producirse colisiones y es posible que haya que volver a enviar datos, ALOHA no puede utilizar de forma eficiente el 100% de la capacidad del canal de comunicaciones. El tiempo que una estación espera hasta que retransmite y la probabilidad de que se produzca una colisión están interrelacionados y ambos afectan a la eficiencia con la que se puede utilizar el canal. Esto significa que el concepto de retransmisión posterior es un aspecto crítico; la calidad del esquema de backoff elegido influye significativamente en la eficiencia del protocolo, la capacidad final del canal y la previsibilidad de su comportamiento.
Para evaluar Pure ALOHA, es necesario predecir su rendimiento, la tasa de transmisión (exitosa) de tramas. [10] Primero, hagamos algunas suposiciones simplificadoras:
Sea T el tiempo necesario para transmitir una trama en el canal y definamos el tiempo de trama como una unidad de tiempo igual a T. Sea G la media utilizada en la distribución de Poisson sobre las cantidades de intentos de transmisión. Es decir, en promedio, hay G intentos de transmisión por tiempo de trama .
Considere lo que debe suceder para que una trama se transmita con éxito. Sea t el momento en el que se pretende enviar una trama. Es preferible utilizar el canal durante un tiempo de trama que comience en t y que todas las demás estaciones se abstengan de transmitir durante este tiempo.
Para cualquier intervalo de tiempo, la probabilidad de que haya k intentos de transmisión durante ese intervalo de tiempo es:
El número promedio de intentos de transmisión para dos tramas consecutivas es 2G . Por lo tanto, para cualquier par de tramas consecutivas, la probabilidad de que haya k intentos de transmisión durante esas dos tramas es:
Por lo tanto, la probabilidad ( ) de que haya cero intentos de transmisión entre tT y t+T (y, por lo tanto, de una transmisión exitosa para nosotros) es:
El rendimiento se puede calcular como la tasa de intentos de transmisión multiplicada por la probabilidad de éxito, y se puede concluir que el rendimiento ( ) es:
El rendimiento máximo es de 0,5/e cuadros por tiempo de cuadro (alcanzado cuando ), lo que equivale aproximadamente a 0,184 cuadros por tiempo de cuadro. Esto significa que, en Pure ALOHA, solo se utiliza alrededor del 18,4 % del tiempo para transmisiones exitosas.
Una mejora del protocolo ALOHA original fue Slotted ALOHA, que introdujo intervalos de tiempo discretos y aumentó el rendimiento máximo. [11] Una estación puede iniciar una transmisión solo al comienzo de un intervalo de tiempo, y por lo tanto se reducen las colisiones. En este caso, solo se deben considerar los intentos de transmisión dentro de un intervalo de tiempo de 1 trama y no de 2 tramas consecutivas, ya que las colisiones solo pueden ocurrir durante cada intervalo de tiempo. Por lo tanto, la probabilidad de que haya cero intentos de transmisión por parte de otras estaciones en un solo intervalo de tiempo es:
La probabilidad de que una transmisión requiera exactamente k intentos es (k-1 colisiones y 1 éxito): [10]
El rendimiento es:
El rendimiento máximo es de 1/e cuadros por tiempo de cuadro (alcanzado cuando G = 1), lo que equivale aproximadamente a 0,368 cuadros por tiempo de cuadro, o 36,8 %.
El ALOHA ranurado se utiliza en redes de comunicaciones satelitales tácticas de baja velocidad de datos por parte de fuerzas militares, en redes de comunicaciones satelitales basadas en suscriptores, en el establecimiento de llamadas de telefonía móvil, en comunicaciones mediante decodificadores y en tecnologías RFID sin contacto .
La Reserva ALOHA, o R-ALOHA, es un esfuerzo por mejorar la eficiencia de la ALOHA con ranuras. Las mejoras con la Reserva ALOHA son demoras notablemente más cortas y la capacidad de soportar de manera eficiente niveles más altos de utilización. Como contraste de eficiencia, las simulaciones han demostrado que la Reserva ALOHA exhibe menos demoras con una utilización del 80% que la ALOHA con ranuras con una utilización del 20-36%. [12]
La principal diferencia entre ALOHA con ranuras y ALOHA con reserva es que con ALOHA con ranuras, cualquier ranura está disponible para su uso sin tener en cuenta el uso anterior. Según el esquema de reserva basado en contención de ALOHA con reserva , la ranura se considera temporalmente "propiedad" de la estación que la utilizó con éxito. Además, ALOHA con reserva simplemente deja de enviar datos una vez que la estación ha completado su transmisión. Como regla, las ranuras inactivas se consideran disponibles para todas las estaciones que luego pueden reservar (utilizar) implícitamente la ranura en base a la contención.
El uso de un canal de acceso aleatorio en ALOHAnet condujo al desarrollo del acceso múltiple con detección de portadora (CSMA), un protocolo de acceso aleatorio de escucha antes de enviar que se puede utilizar cuando todos los nodos envían y reciben en el mismo canal. El CSMA en canales de radio se modeló ampliamente. [13] El protocolo de radio por paquetes AX.25 se basa en el enfoque CSMA con recuperación de colisiones, [14] basado en la experiencia adquirida en ALOHAnet. Una variación de CSMA, CSMA/CD, se utiliza en las primeras versiones de Ethernet .
ALOHA y otros protocolos de acceso aleatorio tienen una variabilidad inherente en sus características de rendimiento de procesamiento y retardo. Por este motivo, las aplicaciones que necesitan un comportamiento de carga altamente determinista pueden utilizar esquemas maestro/esclavo o de paso de tokens (como Token Ring o ARCNET ) en lugar de sistemas de contención .
El procesador de comunicaciones del nodo central era un miniordenador HP 2100 llamado Menehune, que es la palabra en lengua hawaiana para referirse a los enanos, [15] y recibió ese nombre por su función similar a la del procesador de mensajes de interfaz (IMP) original de ARPANET que se estaba implementando aproximadamente al mismo tiempo. En el sistema original, el Menehune enviaba los datos de usuario recibidos correctamente al ordenador central UH, un sistema de tiempo compartido IBM System 360/65. Los mensajes salientes del 360 eran convertidos en paquetes por el Menehune, que se ponían en cola y se transmitían a los usuarios remotos a una velocidad de datos de 9600 bit/s. A diferencia de las radios semidúplex en las TCU de los usuarios, el Menehune estaba interconectado a los canales de radio con equipos de radio full-duplex. [16]
La interfaz de usuario original desarrollada para el sistema era una unidad de hardware llamada Unidad de Control de Terminal (TCU) de ALOHAnet y era el único equipo necesario para conectar un terminal al canal ALOHA. La TCU estaba compuesta por una antena UHF, un transceptor, un módem, un búfer y una unidad de control. El búfer estaba diseñado para una longitud de línea completa de 80 caracteres, lo que permitía manejar los paquetes de longitud fija de 40 y 80 caracteres definidos para el sistema. El terminal de usuario típico en el sistema original consistía en un Teletipo Modelo 33 o un terminal de usuario CRT tonto conectado a la TCU mediante una interfaz RS-232 estándar . Poco después de que la red ALOHA original entrara en funcionamiento, la TCU fue rediseñada con uno de los primeros microprocesadores Intel, y la actualización resultante se denominó Unidad de Control Programable (PCU).
Las funciones básicas adicionales que realizaban las TCU y las PCU eran la generación de un vector de código de comprobación de paridad cíclica y la decodificación de los paquetes recibidos para la detección de errores de paquetes, y la generación de retransmisiones de paquetes utilizando un generador de intervalo aleatorio simple. Si no se recibía un acuse de recibo del Menehune después del número prescrito de retransmisiones automáticas, se utilizaba una luz intermitente como indicador para el usuario humano. Además, dado que las TCU y las PCU no enviaban acuses de recibo al Menehune, se mostraba una luz de advertencia fija para el usuario humano cuando se detectaba un error en un paquete recibido. Se incorporó una simplificación considerable al diseño inicial de la TCU, así como de la PCU para interconectar a un usuario humano con la red.
En versiones posteriores del sistema, se pusieron en funcionamiento relés de radio simples para conectar la red principal de la isla de Oahu con otras islas de Hawái, y se ampliaron las capacidades de enrutamiento de Menehune para permitir que los nodos de usuario intercambiaran paquetes con otros nodos de usuario, ARPANET y una red satelital experimental. [4]
Dos decisiones fundamentales que dictaron gran parte del diseño de ALOHAnet fueron la configuración en estrella de dos canales de la red y el uso de acceso aleatorio para las transmisiones de los usuarios.
La configuración de dos canales se eligió principalmente para permitir una transmisión eficiente del flujo de tráfico total relativamente denso que la computadora central de tiempo compartido devolvía a los usuarios. Una razón adicional para la configuración en estrella fue el deseo de centralizar tantas funciones de comunicación como fuera posible en el nodo de red central (Menehune) para minimizar el costo de la unidad de control de terminal (TCU) original, compuesta íntegramente por hardware, en cada nodo de usuario.
El canal de acceso aleatorio para la comunicación entre los usuarios y el Menehune fue diseñado específicamente para las características de tráfico de la informática interactiva. En un sistema de comunicación convencional, a un usuario se le puede asignar una parte del canal ya sea mediante un acceso múltiple por división de frecuencia o mediante un acceso múltiple por división de tiempo . Como era bien sabido que en los sistemas de tiempo compartido (circa 1970), los datos de los usuarios y de los ordenadores se transmiten a ráfagas, estas asignaciones fijas suelen suponer un desperdicio de ancho de banda debido a las altas velocidades de datos pico a promedio que caracterizan el tráfico.
Para lograr un uso más eficiente del ancho de banda para el tráfico en ráfagas, ALOHAnet desarrolló el método de conmutación de paquetes de acceso aleatorio que se conoce como canal ALOHA puro . Este enfoque asigna dinámicamente y de manera efectiva el ancho de banda de manera inmediata a un usuario que tiene datos para enviar, utilizando el mecanismo de reconocimiento y retransmisión descrito anteriormente para lidiar con colisiones de acceso ocasionales. Si bien la carga promedio del canal debe mantenerse por debajo del 10 % aproximadamente para mantener una tasa de colisiones baja, esto aún da como resultado una mejor eficiencia del ancho de banda que cuando se utilizan asignaciones fijas en un contexto de tráfico en ráfagas.
En el sistema implementado se utilizaron dos canales de 100 kHz en la banda UHF experimental, uno para el canal de acceso aleatorio de usuario a computadora y otro para el canal de transmisión de computadora a usuario. El sistema se configuró como una red en estrella, permitiendo que solo el nodo central recibiera transmisiones en el canal de acceso aleatorio. Todas las TCU de usuario recibieron cada transmisión realizada por el nodo central en el canal de transmisión. Todas las transmisiones se realizaron en ráfagas a intervalos regulares.9600 bit/s , con datos e información de control encapsulados en paquetes.
Cada paquete constaba de un encabezado de 32 bits y una palabra de verificación de paridad de 16 bits, seguidos de hasta 80 bytes de datos y una palabra de verificación de paridad de 16 bits para los datos. El encabezado contenía información de dirección que identificaba a un usuario en particular, de modo que cuando Menehune transmitía un paquete, solo el nodo del usuario en cuestión lo aceptaba.
En la década de 1970, el acceso aleatorio ALOHA se empleó en la naciente red basada en cable Ethernet [17] y luego en la red satelital Marisat (ahora Inmarsat ). [18]
A principios de la década de 1980 se pusieron a disposición frecuencias para redes móviles y en 1985 se asignaron en Estados Unidos frecuencias adecuadas para lo que se conocería como Wi-Fi . [19] Estos avances regulatorios hicieron posible el uso de las técnicas de acceso aleatorio ALOHA tanto en Wi-Fi como en redes de telefonía móvil.
Los canales ALOHA se utilizaron de forma limitada en la década de 1980 en los teléfonos móviles 1G para fines de señalización y control. [20] A fines de la década de 1980, el grupo de estandarización europeo GSM que trabajó en el sistema de comunicación móvil digital paneuropeo GSM expandió en gran medida el uso de canales ALOHA para el acceso a canales de radio en telefonía móvil. Además, se implementó la mensajería de texto SMS en teléfonos móviles 2G. A principios de la década de 2000 se agregaron canales ALOHA adicionales a los teléfonos móviles 2.5G y 3G con la introducción generalizada del Servicio General de Radio por Paquetes (GPRS), utilizando un canal de acceso aleatorio ALOHA con ranuras combinado con una versión del esquema ALOHA de reserva analizado por primera vez por un grupo de BBN Technologies . [21]
