Universidad Politecnica de Cartagena Simulador de Aloha Ranurado ETSIT


ver código

1. Introducción

Los medios de transmisión que utilizan las redes de comunicación pueden ser clasificados en dos categorías: los constituidos por enlaces punto a punto y aquellos que utilizan un canal broadcast al que se conectan físicamente todos los nodos de la red (p.ej. la conexión mediante un cable coaxial de todos los nodos). La denominación broadcast se debe a que cada nodo en la red puede escuchar todas las transmisiones, aunque en la práctica sólo recibirá aquellas tramas de datos que vayan dirigidas a él (lo cual es posible añadiendo unos cuantos bits de dirección en cada trama). La característica más interesante de estos canales broadcast es cómo se asigna de forma eficiente el derecho a transmitir a los nodos que desean hacerlo (algoritmo o protocolo de Control de Acceso al Medio). Si la red es de datos, no suele ser eficiente el asignar de forma permanente canales frecuenciales (FDM) o temporales (TDM) a cada uno de los nodos. Ello se debe a que el tráfico de datos es normalmente muy racheado: un nodo suele permanecer en "silencio" durante casi todo el tiempo y sólo emite ráfagas de información en períodos relativamente breves.

De ahí que la mayoría de métodos empleados para controlar el acceso en redes broadcast usen técnicas denominadas "de acceso aleatorio" o "por contienda" o también "de asignación dinámica del canal". Son de asignación dinámica del canal porque se decide "sobre la marcha" qué nodo transmitirá a continuación en función de cuáles desean hacerlo.

Son de acceso aleatorio en el sentido de que no es predecible, o no está planificado a priori, el instante en que un nodo podrá transmitir. Son también de contienda porque en un momento dado podemos tener varios nodos compitiendo por el control del medio y por tanto será necesario resolver estas contiendas cuando se produzcan. Hay que tener en cuenta que en los mecanismos de control de acceso por contienda no hay ninguna estación central que decida quién transmite a continuación, sino que el control está distribuido de forma uniforme entre los nodos de la red.

El propósito de esta práctica es estudiar el comportamiento del método de control de acceso al medio por contienda conocido por "ALOHA-ranurado".

1.1. Protocolos ALOHA y ALOHA-ranurado

ALOHA fue la primera técnica de control de acceso por contienda desarrollada en los albores de las redes locales (LAN). Aunque se desarrolló en principio para redes de paquetes con transmisión sobre radio-broadcast (a través de satélite), es utilizable para cualquier medio de tipo broadcast. Las sucesivas mejoras a que fue sometido llevaron al método de acceso CSMA-CD (Carrier Sense Multiple Access with Collision Detection) utilizado en la redes Ethernet que constituyen actualmente más de la mitad del parque mundial de LANs.

Desde un punto de vista académico el estudio de las redes ALOHA es muy interesante ya que pese a su relativa sencillez permite extraer conclusiones sobre las prestaciones de protocolos más complejos. No obstante, aquí nos limitaremos a dar una descripción mínima1 del método que permita construir un modelo de simulación sencillo, sin entrar en un estudio detallado que iría más allá del propósito de esta práctica.

1.1.1. Aloha

La idea básica del método es realmente simple: cuando un nodo quiere transmitir una trama, la envía sobre el canal sin "mirar" si ya había otro nodo transmitiendo. Evidentemente, la transmisión de varias tramas se puede solapar en el tiempo y se produce entonces lo que se denomina una "colisión", no pudiéndose, en este caso, realizar una recepción correcta de ninguna de las tramas implicadas.

Afortunadamente, suele ser relativamente simple detectar cuándo se ha producido una colisión gracias a que, generalmente, la señal eléctrica durante la colisión presenta características anómalas que la diferencian de la señal en una transmisión "correcta". Así pues, simplemente "escuchando" el canal durante la transmisión, el emisor puede saber si la trama ha sido transmitida con éxito, o por el contrario si ha sido destruida por una colisión (de forma análoga los receptores también descartan estas tramas). En caso de colisión, el emisor espera un tiempo aleatorio y lo intenta de nuevo. Este tiempo de espera debe ser aleatorio ya que en caso contrario las mismas tramas volverían a colisionar en los nuevos reintentos. No obstante, hay que decir que le método ALOHA original no define en principio ningún método para elegir el tiempo de espera. Si la transmisión de una trama requiere un tiempo t, y se empieza a realizar en el instante t0, sufrirá una colisión si algún otro nodo decide transmitir en el intervalo, o "ventana de colisión", [t0 - t, t0], por lo que disminuye la probabilidad de error.

El algoritmo de retransmisión de las tramas colisionadas que se va a utilizar en esta práctica es conocido como algoritmo de back-off . Según este algoritmo, cuando un nodo transmite una trama y se detecta una colisión, elige, con probabilidad uniforme, un número entero en el intervalo [0;K - 1], espera una cantidad de ranuras igual al número escogido (tiempo de espera o back-off ) y reintenta de nuevo. Si vuelve a producirse otra colisión repite el proceso una vez más, utilizando ahora un valor de K mayor, y así sucesivamente hasta que consigue transmitir la trama con éxito. En la práctica, es usual tomar K=2 para el primer reintento, y en cada nuevo reintento que colisione se duplica este valor hasta conseguir una transmisión exitosa. Para evitar que el tiempo de espera se pueda disparar, la duplicación de K se detiene cuando llega a cierto valor (el número de nodos en la red, o si este se desconoce, el número máximo de nodos que pueden conectarse a la red). Además si el número de reintentos no fructíferos llega a cierto valor (típicamente 15), se desiste de transmitir esta trama y se le notifica al usuario.

Se pueden encontrar estudios más detallados de ALOHA y similares (según orden creciente de profundidad) en:


Autor

Valid HTML 3.2!