Introducción a Técnicas de Contienda
 
  I.2.1.1 - Contienda Simple: ALOHA Fue diseñado en los años 70 por Norman Abramson para resolver el problema de interconexión del campus de la universidad de Hawai. Dada la geografía, se tenía un número alto de terminales "tontos" en las distintas islas que accedían vía radio a un ordenador central en otra de las islas.

F1: de terminal a central (contienda). F2: de central a terminales (no hay compartición).

Los terminales comparten un canal para acceder a C. No son capaces de escuchar su propia transmisión ni la de otros terminales (el sistema no está diseñado para ello). Por tanto es la central la que avisa a todos los terminales si ha habido o no colisión.

El algoritmo básico es el siguiente:

• Cuando un terminal tiene datos los transmite. 
• Si dos o más terminales se solapan en su transmisión, hay colisión.  
• Después de transmitir las estaciones esperan un acuse de recibo por parte del ordenador central. Si éste no llega, se retransmite.  

En 1972 Roberts propuso una modificación a este modelo con el objetivo de mejorar la eficiencia del sistema que como veremos más tarde es muy baja. Esta modificación se denomina ALOHA RANURADO (Slotted Aloha) y el funcionamiento es:

• Se sigue transmitiendo sin escucha previa 
• El tiempo se divide en cuantos, denominados ranuras o slots y de duración igual a una trama (se transmite un reloj para sincronización).
• Se transmite al comienzo de cada ranura. Es decir, si llega una nueva trama, no se transmite hasta el comienzo del siguiente slot.

Gráficamente se puede ver por qué es mejor esta modificación. Se reducen los casos en que se producen colisiones debido a la espera en la transmisión. 
Sin embargo esto traerá consigo también un aumento del retardo para transmitir un paquete. Además debe haber una sincronización (que mandará la central) y un tiempo de guarda ya que las distancias entre todos los terminales no son iguales (el slot será algo más grande a una trama).
 

  I.2.1.2 - Primer modelo de ALOHA: Modelo Poissoniano

Estudiaremos en primer lugar un modelo sencillo del sistema ALOHA, basado principalmente en el supuesto de que el tráfico soportado por el canal radio se comporta como un proceso de Poisson.  Este modelo nos permitirá obtener una primera estimación de la eficiencia del sistema.

Posteriormente, analizaremos otro modelo más completo y a la vez complejo, basado en cadenas de Markov. Este segundo modelo nos permitirá analizar con detalle la dinámica del sistema y obtener una serie de importantes conclusiones sobre su comportamiento.

Modelo de estación y supuestos de partida

Vamos a modelar las estaciones como procesos de Poisson.

La probabilidad de que existan k llegadas en t segundos viene definida por:

• Tráfico Generado (I, tasa). Es la intensidad de tráfico que van a tratar de transmitir las estaciones.
• Tráfico Cursado (S, tasa ). Es la intensidad de tráfico que van a recibir las estaciones. En situaciones normales (estabilidad) se cumple que S = I (todo lo que entra sale del sistema).
• Tráfico Ofrecido (G, tasa). Es la intensidad de tráfico que va a tener que soportar la red. Incluye el tráfico generado más las posibles retransmisiones.

Un mensaje generado da lugar, en general, a varios mensajes ofrecidos y a uno cursado.

1.	Llegadas Poissonianas: cada estación es un proceso de Poisson independiente. La tasa de llegadas global es. Esta hipótesis no es realista ya que en general los mensajes son multipaquete. Trabajaremos con los parámetros normalizados a la capacidad del canal de forma que el margen de variación de I, S y G será de [0,1]. Así: Tramas de longitud fija: lp (bits). Tiempo de transmisión de una trama:  La capacidad del canal medida en tramas/seg será: Como máximo el tráfico cursado será la capacidad del canal, por tanto normalizando:
2.	Sistema ranurado: tramas de longitud fija y tiempo dividido en slots del tamaño del tiempo de transmisión de una trama.
3.	Colisión o recepción perfecta: si envía una sola estación se recibe perfectamente, sin errores; si dos o más envían no llega nada (ignoramos errores de transmisión).
4.	Realimentación inmediata: al final del slot de transmisión la estación sabe inmediatamente si se ha recibido bien (han transmitido 1 o varios).
5.	Retransmisión de colisiones: los paquetes involucrados en colisiones, se retransmiten hasta su transmisión con éxito. Decimos que un nodo con retransmisiones pendientes está retraido (backlogged).
6a.	No hay "buffers": si una estación está esperando para transmitir un paquete (nuevo o retransmitido), descarta los paquetes nuevos que lleguen. Esta situación no es realista porque, en la práctica, seguiría llegando tráfico. Al analizar el retardo de transmisión, el obtenido será, por tanto, menor que el real ya que hay pérdidas y esto no se tiene en cuenta. Obtendremos un LÍMITE INFERIOR DEL RETARDO.
6b.	Población infinita: cada trama nueva llega a un terminal distinto. El tráfico global es de tramas/seg pero cada terminal genera un tráfico infinitesimal (no habrá probabilidad de que llegue trama y no se haya transmitido la anterior). De nuevo la suposición es poco realista y nos dará en el análisis un LIMITE SUPERIOR al retardo con número finito de terminales.

Análisis de ALOHA Simple

Como hemos visto en la introducción, en Aloha simple las estaciones transmiten sin ninguna restricción y siempre que tengan información preparada. Esto va a provocar que se produzcan colisiones en el caso de que dos o más estaciones deseen transmitir simultáneamente. Cuando se produce una colisión, las estaciones involucradas detectan la situación y retransmiten las tramas perdidas.

Las hipótesis que aplicaremos en este análisis son 1, 3, 4, 5 y 6b (población infinita: aproximación válida si Nº > 50). Las tramas son de longitud constante l_p bits. La principal simplificación que haremos en este modelo es suponer que el tráfico ofrecido (G) se comporta como un proceso de Poisson. Esta idealización no es real ya que el tráfico tendrá un retardo de retransmisión que hará que el tiempo entre llegadas no sea exponencial y por tanto el tráfico total no sea de Poisson. Sin embargo veremos que los resultados serán parecidos a los que se obtendrán con otros modelos más ajustados.

El modelo para esta situación es el siguiente:

Vamos a calcular la relación entre G, tráfico ofrecido, y S, tráfico cursado. Vemos que S=Gp_nc. Por tanto calculo p_nc:

P_nc =  P{ Tx éxito / Tx } = P{ t₀ - t_a > X_p } . P { t_b - t₀ > X_p } =
= P {0 llegadas X_p entre t_a,t_b} . P {0 llegadas X_p entre t_a,t_b} = 
= ( P(0 , X_p) )² =  (1 - P (t_llegadas <= X_p))²;

A partir de este resultado de rendimiento del Aloha simple, podemos ver que esta técnica tiene bastante poca eficiencia (máxima del 18%), y se colapsa para cargas altas.

Definimos INTERVALO DE VULNERABILIDAD como el intervalo de tiempo en el que hay que garantizar que no hay llegadas para que no se produzca una colisión.

Para tratar de aumentar la eficiencia del Aloha simple se diseñó Aloha-R que reduce el intervalo de vulnerabilidad a la mitad y, por tanto, disminuye el número de colisiones.

ALOHA RANURADO (SLOTTED ALOHA)

Nuestro modelo es ahora el siguiente, en el que vemos que el intervalo de vulnerabilidad es x_p.

Calculamos ahora la probabilidad de no colisión:

Comentarios:

Vemos que el uso está muy por debajo del ideal (para G=1, S=1). Además para un mismo tráfico cursado (utilización) podemos estar en dos situaciones distintas: una deseable, en la que el tráfico ofrecido es bajo (hay pocas colisiones y los paquetes salen del sistema); otra no deseable, en la que el tráfico ofrecido es muy alto (hay muchísimas colisiones y no sale casi nada del sistema, los paquetes están todo el rato colisionando, retransmitiéndose y volviendo a colisionar). ¿Podemos llegar a la situación no deseable y que el sistema permanezca ahí, se colapse? En principio como no sabemos cómo se comporta el sistema podría suceder que viniera de pronto una ráfaga alta de tráfico y falle, de ahí que luego propongamos un segundo modelo con el objeto de saber cómo se comporta el sistema ante situaciones transitorias. Estamos en Aloha ranurado: ¿QUÉ SUCEDE CUANDO G=1? La probabilidad de k llegadas en un slot (normalizado: t=1) es: Pk(t) = Gk.e-G/k! =  1/e.k! Por tanto el número de slots en media de cada tipo: Slots con transmisiones exitosas: probabilidad de que sólo haya 1 llegada  P1 = S = 1/e = 0.37    El 37% de los slots lleva tramas exitosas. Slots que van vacíos: probabilidad de 0 llegadas  P0 = 1/e =0.37      El 37% de los slots van vacíos.  Slots con colisiones: probabilidad de 2 o más tramas, o sea, el resto  Pcolis = 1 - P0 - P1 = 0.26    El 26% de los slots llevan colisiones. La utilización es muy pobre, sólo el 37%. G es 1 porque se transmiten muchas tramas en un mismo slot que, al sumarse, usan la capacidad del canal total (1), aunque en realidad la mayoría no llega (S no es 1).

ALOHA y ALOHA-R CON RETARDO DE PROPAGACION

En el análisis anterior hemos despreciado el tiempo de propagación del canal (t_r). Si queremos tenerlo en cuenta, deberemos volver a calcular los intervalos de vulnerabilidad considerando dicho retardo y repetir, posteriormente, el mismo análisis.

• Aloha simple.

Hay colisión si B tx a X_p+ t_r antes de t_o. (Donde t_r es el tiempo de propagación)
Hay colisión si C tx a X_p+ t_r después de t_o.

• Aloha ranurado.

Realizando un análisis similar al caso anterior obtenemos:
 





Comentarios:

Cuando el retardo, tr, sea despreciable frente a Xp quedarán las fórmulas ya vistas. Sin embargo en algunos casos este retardo tiene un efecto importante en el sistema, como por ejemplo en el caso de transmisión por satélite donde el retardo es muy alto.

ANÁLISIS DE RETARDOS EN ALOHA

Vamos a calcular el retardo que sufren los paquetes al transmitirse. Definimos:

RETARDO DE TRÁNSITO, T, intervalo de tiempo que transcurre desde que se produce una llegada al sistema hasta que se recibe con éxito en el destino (la central). Este tiempo incluirá las retransmisiones si hay colisiones.

Cuando llega la trama se transmite y se espera el asentimiento de la central (destino) durante un plazo P_e. Según el supuesto (4) la realimentación era inmediata, luego sería P_e = 0. Consideramos el caso más general de que exista ese período de espera.
Si no llega el asentimiento (ha habido colisión), la retransmisión se efectúa después de un tiempo de espera aleatorio, retroceso aleatorio.
Esto se sucederá cada vez que se retransmita, luego tenemos un ciclo. El retardo de tránsito será la suma de todos los ciclos que se dan. Para hallar lo que queremos necesitaremos hacer el promedio del nº de ciclos que se dan. 

El retardo medio será el tiempo que dura un ciclo por el número medio de retransmisiones que hay más el tiempo de la última transmisión, la que llega correctamente. 
No se incluye el último P_e en el tiempo porque la central ya ha recibido la información, ya está en el destino. Esa P_e es para el nodo pero no retarda la llegada de la información. Por tanto es:

• Aloha simple: 
• Aloha ranurado: 

En el retardo de aloha ranurado hay que incluir el término x_p/2 ya que es el retardo medio que tiene un paquete para transmitirse ya que hay que esperar al siguiente slot, no se transmite inmediatamente como el aloha simple.

Suponemos que T_r es una v.a. uniforme entre x_p y kx_p:

Para calcular N_r medio despejamos del número medio de transmisiones en el sistema que es: 

Usaremos el retardo normalizado al tiempo de transmisión de una trama:  con lo que en cada caso resulta:

NOTA: Según nuestra definición se incluye el tiempo de la última transmisión (de ahí el sumando 1). Dependiendo del libro consultado se incluye o no este término.

El primer modelo de Aloha que analizamos en la sección anterior nos daba una idea de lo que sucedía en media  en el sistema (tasa media de llegadas, retardos medios...), pero no nos permite analizar como se comporta, por ejemplo, ante picos de tráfico.

Es decir, el modelo anterior no refleja la dinámica real del sistema en el caso de que se produzcan colisiones. En él suponíamos, por simplicidad, que las llegadas, tanto si eran nuevas como si procedían de retransmisiones, seguían un patrón poissoniano. Este supuesto no es cierto, ya que, aunque el tráfico de entrada al sistema es poissoniano, cuando se produce una retransmisión, las tramas sufren un retardo aleatorio que provoca que el patrón de tráfico retransmitido deje de ser poissoniano.

Por todo ello vamos a introducir un análisis más detallado que refleje con más precisión el comportamiento del sistema cuando se produce una colisión. 

El nuevo modelo utilizará la hipótesis 6a de población finita, (m nodos, cada uno de ellos generando /m  tramas/s). La principal consecuencia de asumir esta hipótesis es que la tasa de llegadas al sistema deja de ser constante.
Con el primer modelo,si muchos nodos colisionaban, siempre había otros que seguían transmitiendo puesto que teníamos infinitos nodos. En el nuevo modelo, cada vez que un nodo pase a estar retraido, la tasa de entradas al sistema se verá reducida, ya que ese nodo no generará tráfico nuevo hasta conseguir transmitir con éxito la trama pendiente.
Podrá darse el caso de que ante ráfagas indeseadas el sistema comience a colapsarse y todos los nodos pasen a estar retraídos durante un espacio de tiempo. Esta es una situación real que no quedaba contemplada con el primer modelo, y que aquí si podremos estudiar gracias a un concepto que introduciremos posteriormente: la deriva.

Algoritmo de Retransmisiones.

 Vamos a suponer que cada nodo que ha colisionado retransmite con probabilidad q_r en cada slot sucesivo hasta que logra el exito (de forma independiente).Por lo tanto:

Ya sabemos como es el modelo de retransmisiones. Si quisieramos,aunque no nos va a hacer falta para el estudio posterior, podríamos calcular el número medio de slots antes de retransmitir:

Cadenas de Markov.

El comportamiento de este modelo Aloha ranurado puede ser descrito mediante una CADENA DE MARKOV DISCRETA EN EL TIEMPO. El estado de esa cadena será el número de nodos con retransmisiones pendientes (nodos retraídos); entre los distintos estados tenemos las probabilidades de transición o probabilidades de pasar de unos estados a otros:

• P00: Probabilidad de que no se transmita nada, o que se transmita con éxito. 
• P12: El único nodo retraído que había retransmite y otro que no lo estaba transmite: pasamos a tener dos nodos retraídos.
• P02: Dos llegadas nuevas y las dos colisionan.
• Y así sucesivamente.

• Número medio de nodos retraídos.
• El retardo medio.

Si analizaramos los resultados de este análisis, veríamos que son más precisos respecto a los del anterior modelo, pero no difieren tanto de él como para no dar por válido el sencillo estudio que ya vimos para aloha ranurado. 

Sin embargo, el problema principal AÚN no lo hemos eliminado:

• Seguimos teniendo resultados en media... y queremos saber como se comporta ante las ráfagas.

 
Análisis probabilístico.

Sea n el número de nodos con retransmisiones pendientes. Cada uno transmite en el slot siguiente con probabilidad q_r. El resto de nodos (m-n) transmite en ese slot si se ha producido una llegada en el slot anterior. Dado que las llegadas nuevas si son Poissonianas:
 
 

Po=P(no llega nada en un slot). t=1 es la duración del slot. 0=/m.

Con esto, la probabilidad de que un nodo sin retransmisiones pendientes transmita (con colisión si otros no retraídos transmiten al mismo tiempo)en un slot es:

Es decir, es la probabilidad de que se produzca al menos una llegada poissoniana, o en otras palabras, procedente de tráfico nuevo;las procedentes de retransmisiones recordamos que no lo son.

Estando el sistema en estado n, es decir, estando n nodos retraídos entre los m del sistema, definimos Qa(i,n) como la probabilidad de que i nodos sin retransmisiones pendientes envíen tramas en un slot dado, y Qr(i,n) como la probabilidad de que i nodos retraídos transmitan:

es decir,estamos haciendo todas las combinaciones posibles de : En Qa, que no transmitan m-n-i nodos no retraídos y que transmitan i nodos. En Qr,que no transmitan n-i nodos retraídos y transmitan i nodos. Ya estamos en condiciones de calcular las probabilidades de transición de la cadena de Markov, siendo: Pn,n+i la probabilidad de pasar del estado n al n+i en el siguiente slot.

Y según sea i, Pn,n+i tomará los siguientes valores:

2<=i<=m-n	Qa(i,n)	Probabilidad de que i nodos nuevos transmitan a la vez y pasen a retraídos.El estado se puede incrementar de forma arbitraria, mientras que decrece sólo en una unidad por transición.
i=1	Qa(1,n)(1-Qr(0,n))	Algún nodo "nuevo" transmite al mismo tiempo que alguno con retransmisiones pendientes (Pn,n+1).
i=0	Qa(1,n)Qr(0,n)+Qa(0,n)(1-Qr(1,n))	Transmite con éxito algún nodo "nuevo" o bien los que esperaban vuelven a colisionar (Pn,n).
i=-1	Qa(0,n)Qr(1,n)	Con i=-1, tenemos la probabilidad de volver al estado anterior. Se halla como la probabilidad de que transmita un nodo retraído con éxito, es decir,con todos los nodos "nuevos" en silencio.
-n<=i<=-2	0	Es cero porque no puedo eliminar de golpe dos o más nodos retraídos, tendría que esperar a otro slot.

Para resolver el modelo, calcularíamos las probabilidades estacionarias:

• Pj= Proporción del tiempo que el sistema está en el estado j.

donde j=0,1,2...

Para calcular las distintas pj, habría que hacerlo de forma iterativa, pn en función de p0 y p0 como una constante normalizada.

No vamos a entrar en esos cálculos, basta con repasar un poco la asignatura Redes y Servicios I, pero si conocieramos estas probabilidades es inmediato hallar el número medio de nodos retraídos y, partiendo del TEOREMA DE LITTLE, el retardo medio.

Y en definitiva, ya tenemos los parámetros que definen el sistema.

Es importante comentar que el sistema tiene un comportamiento extraño para un número grande de nodos retraídos. Veamos el porqué:

• q_r hay que elegirla moderadamente alta para evitar esperas largas, porque significa que retransmito con bastante probabilidad.
1. Si la tasa de llegadas es baja, el sistema funciona bien.
2. Si hay una ráfaga de tráfico que provoca un aumento en el número de nodos retraídos, de forma que qr*n>>1 ,entonces el número de colisiones en slots posteriores será grande y el sistema permanecerá en ese estado durante un tiempo largo,(y eso hay que evitarlo, si todo el mundo quiere sacar dinero al mismo tiempo de un cajero, éste no puede colapsarse).
• Sin embargo,si qr es baja:
1. Si el sistema está descargado, los retrasos serán altos y sería una situación indeseable.
2. Por otra parte, si estuviera cargado SÍ ME INTERESA una qr baja.

Análisis cuantitativo.

 Definimos la Deriva en el estado n o D_n como el cambio esperado en el número de nodos retraídos en el siguiente slot. Esto es:

D_n= Número esperado de llegadas al sistema - Número esperado de transmisiones con éxito.

• Numero esperado de llegadas al sistema: (m-n)qa 
• Número esperado de transmisiones con éxito: S

Donde S viene dada por     S = Qa(1,n)Qr(0,n)+Qa(0,n)Qr(1,n)   (1) 

1. El primer término significa que se transmite con éxito en un slot dado si llega un nuevo nodo, no retraído, y envía información con los otros "callados".El segundo término, que los nuevos nodos no transmiten y uno retraído sí lo consigue.
2. Si qr y qa pequeñas, S=G(n)*exp(-G(n)); esto viene de que (1-x)^y --> exp(-xy) para x<<1, sustituyendo en (1).

 Observemos la siguiente gráfica:

Si S>(m-n)qa --> Dn<0 --> Evolución hacia estados mejores. Si S<(m-n)qa --> Dn>0 --> Evolución hacia estados peores. Como la deriva es el cambio esperado de un slot al siguiente, el sistema tenderá a moverse en la dirección de la deriva, entorno a los dos puntos estables del sistema (a y c), con excursiones entre ambos.

En la zona donde Dn<0, cuando desaparezca la causa que generó nodos retraídos, se volverá a la estabilidad. En la zona donde Dn>0, pasará todo lo contrario.

1. (a) es un punto ESTABLE Y DESEABLE. Si el sistema se aleja de dicho punto, la deriva lo hará volver a él.
2. (b) es un punto de EQUILIBRIO INESTABLE. Si nos desplazamos a la derecha, la deriva "empujará" al sistema más a la derecha; Si nos desplazamos hacia la izquierda, la deriva "empujará" al sistema más a la izquierda.
3. (c) es un punto de EQUILIBRIO ESTABLE NO DESEABLE.Estoy en una mala zona donde la tasa de salidas es prácticamente cero; el sistema está en equilibrio... pero porque está tan colapsado que no es capaz de salir de ese estado. No es capaz de cursar tráfico alguno y las probabilidades de salir de esa situación son bajas. 

 Veamos algunas conclusiones:

1. Se observa en las gráficas que si m>>1, entonces Smax=1/e.

	Si qr aumenta, la probabilidad de llegar al desastre antes también aumenta.                Los puntos (a) y (b) se acercan, disminuyendo la zona deseable, comprimiéndose la curva S.
	Si qr disminuye, parece que la deriva es únicamente negativa, y podría pensarse que es una buena situación.          El problema es que para este caso,los retardos aumentan muchísimo. Se observa que la curva S se ensancha y sólo aparece un punto de equilibrio.  Parece que conforme el sistema se sobrecargara, lo ideal sería que qr disminuyera.
	Si usamos la hipótesis de población infinita,desaparece el punto no deseable. Esto es así porque siempre habrá nodos nuevos que mantengan la tasa de entradas constante, mientras que el número de nodos retraídos crecerá constantemente a partir del punto de equilibrio inestable. Ahora, G(n)=+n*qr.

Estudiamos la estabilidad basándonos en el segundo modelo aloha ranurado.
 
 

Habíamos visto que para G=1: Número de slots con éxito: 36.8%. Número de slots libres: 36.8% Número de slots con colisiones: 26.4%  Para G=1, obtengo el máximo de mi tráfico cursado(G=1,S=0.368); por tanto nos interesa que el sistema permanezca en torno a ese valor de G. Si <<1/e y qr es moderada, es sistema estará la mayor parte del tiempo en la zona estable,pero tenemos que evitar que una ráfaga lo lleve a zonas peligrosas. Para que el sistema no se colapse ante estas ráfagas, habrá que tocar el modelo de retransmisiones.

He de conseguir G=1 adaptando q_r. En principio, q_r deberá modificarse en función de la situación que se prevea en un instante... pero esto es imposible. Los nodos no saben lo que sucede en cada momento, pero si saben como van los slots que pasan por ellos:

• Aumentaremos q_r si vemos un slot libre.
• Disminuiremos q_r si vemos una colisión.

1.Algoritmo pseudo-bayesiano

Las nuevas llegadas se consideran retransmisiones. Es decir, no transmitimos en el siguiente slot sin más, sino que transmitimos con probabilidad q_r, (se consideran nodos retraídos).

• Si el sistema está poco cargado, q_r será próxima a 1; si llega alguien y comprueba que q_r=1, transmitirá en el siguiente slot.
• Si el sistema va mal,reduciré q_r.

Cada nodo mantiene una estimación (que llamaremos ñ) del número de nodos retraídos, a partir de un algoritmo, y de esta estimación se obtienen los valores de qr para tratar de reproducir lo que pasa cuando el sistema funciona bien.Matemáticamente:

Es decir, estimo n, y la probabilidad en el siguiente slot será 1/ñ;si la estimación es buena, conseguiré que G=n*qr sea próxima a 1, y viceversa si es mala.

Otra dificultad añadida a esta estimación, es que no conocemos (desde una isla no sabemos el tráfico que aportan las otras).

Tenemos dos alternativas:

1. Estimar . Esto estaría bien si pudiera ver el tráfico, pero no es el caso.
2. Poner  fija, y tomarla como 1/e.

Retroceso exponencial binario.

Recordamos que los análisis los estamos basando en la hipótesis 4: realimentación inmediata..., la cual no representa la situación real. Por ello, en la práctica tratamos de estabilizar el sistema suponiendo realimentación limitada(sólo hay realimentación en los slots donde transmito).
Ahora el algoritmo de retransmisiones será el siguiente:
 

"Si una trama se transmite sin éxito "i" veces: Se retransmitirá en cualquiera de los 2^i slots siguientes y de forma equiprobable". Esto significa que yo transmito la trama sin saber como de cargado está el sistema.  Si hay colisión,amplio el margen para retransmisiones y así la probabilidad de que vuelva a colisionar es muy baja.

No hay que olvidar que las retransmisiones introducen retardos, y esto no es bueno para nuestro sistema.
Este sistema se usa en la ethernet; se impone un límite de 10 colisiones: a partir de la décima, ya no aumento más el número de slots donde puedo retransmitir.
Tiene un segundo límite:si después de 16 colisiones no se ha transmitido, el MAC informa al nivel superior de que hay un error que no sabe resolver, para que éste actúe en consecuencia.
I.2.1.5 - Contienda con Escucha: CSMA y CSMA/CD
El principal problema de Aloha y Aloha ranurado es la baja utilización del canal alcanzada. Esto es debido principalmente a que las estaciones transmiten libremente sin prestar atención a lo que ocurre en el medio. Esto es, no se preocupan de saber si el medio está o no vacío antes de transmitir, y, por tanto, la probabilidad de que colisionen con otras estaciones es alta. 

Las técnicas de contienda con escucha (CSMA = Carrier Sense Multiple Access) se basan en que las estaciones "escuchan" el medio antes de transmitir, con el objeto de conocer si está libre. En caso de que esté ocupado,  postponen la transmisión para evitar colisionar con otras estaciones.

Como veremos a lo largo de esta sección, la reducción del número de colisiones debida a la escucha, mejora el tiempo de uso útil del canal, incrementando sensiblemente las prestaciones del método de acceso, sobre todo si las comparamos con las obtenidas en Aloha u otras técnicas sin escucha.

La escucha funciona razonablemente bien para entornos con un retardo de propagación pequeños, como sucede en la mayoría de las redes de área local (LAN). Sin embargo, en los casos en que el retardo de propagación es alto en comparación con el tiempo de transmisión de una trama (a>1), las mejoras debidas a la escucha pueden llegar a desaparecer. Aunque una estación escuche y encuentre el medio libre, puede suceder que realmente esté ocupado por una trama que no ha llegado todavía.
La siguiente figura representa dicha situación:

En este croquis se ve la importancia del tiempo de propagación, ya que es el retardo con que las otras estaciones se enteran de que el medio está ocupado. Si alguna transmite durante este intervalo creyendo que el medio está libre habrá colisión. 

VARIANTES DE CSMA

1. CSMA no persistente

Antes de transmitir se escucha para ver el estado del medio. Si está vacío, se transmite; si está ocupado, se espera un tiempo aleatorio (generalmente largo, del orden de la transmisión de una trama, siguiendo una función densidad de probabilidad determinada) y se vuelve a escuchar el medio. 
La principal desventaja de esta variante es que se pierde mucho tiempo, sobre todo con bajas cargas, ya que aunque haya tramas esperando, el canal estará desocupado al final de una transmisión.
2. CSMA 1-persistente

Es el otro extremo: antes de transmitir se escucha el estado del medio. Si está vacío, se transmite, y si no es así, se vuelve a escuchar el medio para ver su estado, o sea, permanecemos escuchando hasta que termina la transmisión y en ese momento transmitimos. Vemos que este sistema tiene la ventaja de que en cuanto se termina de enviar una trama la estación que quería transmitir lo hace, y por tanto no se pierde tiempo.
El problema llega si lo que había era más de una estación esperando: tenemos una colisión segura. Además de esto tendremos otro problema que es que cuando dos o más estaciones colisionan, tienden (si no se hace nada más) a transmitir de forma más o menos sincronizada (vuelven a querer transmitir a la vez), lo que genera al final un proceso que sincroniza todas las estaciones y hace aumentar las colisiones.
3. CSMA p-persistente

Es un caso intermedio entre ambos esquemas. Antes de transmitir se escucha el estado del medio. Si está vacío, transmito con una probabilidad p ("tiro a los dados y transmito si he tenido suerte") y por tanto no transmito con probabilidad 1-p: lo que se hace en este caso es esperar un tiempo aleatorio antes de volver a escuchar el medio. Si el medio está ocupado, se vuelve a escuchar el medio.
En este caso la espera es del orden del tiempo de propagación (corto) puesto que es raro que dos estaciones que estaban esperando decidan transmitir a la vez. Se cumple que siendo p la probabilidad de transmitir y n el número de estaciones que esperan para transmitir, si np > 1 habrá bastantes colisiones y habrá menos colisiones (lo que se busca) si np < 1.

NO PERSISTENTE

procedure EnviarTrama (trama);
begin
   while ocupado do
      esperar plazo aleatorio;
   end;
   Transmitir(trama);
end;

  1-PERSISTENTE

  procedure EnviarTrama (trama);
  begin
     while ocupado do
       nada;
     end;
     Transmitir(trama);
  end;

CSMA CON DETECCIÓN DE COLISIONES

CSMA/CD = Carrier Sense Multiple Access with Collission Detection

Con las técnicas estudiadas hasta ahora, cuando se produce una colisión, las estaciones implicadas continuan transmitiendo las tramas hasta el final. Esto implica un desaprovechamiento del canal, ya que cuando se produce una colisión, las tramas se pierden por completo y deben ser retransmitidas. 

Las técnicas de Escucha con Detección de Colisiones tratar de mejorar las prestaciones mediante la detección prematura de las colisiones, con el objeto de que las estaciones cesen su transmisión una vez que éstas se han producido. Con ello se consigue un ahorro importante de tiempo, que de otra forma se desperdiciaría, y se acelera el proceso de retransmisión de las tramas que han colisionado.

El algoritmo utilizado por las estaciones con escucha es muy simple: escuchan el canal no sólo antes de transmitir, sino también durante la transmisión; si detectan una colisión, dejan de transmitir e inician el proceso de retransmisión (esperan un tiempo aleatorio). 

Es interesante estudiar la manera de detectar las colisiones. Usar en este caso un código binario no es lo más apropiado porque no es sencillo detectar bien las colisiones y porque es vulnerable al ruido. Por todo eso se usa la codificación Manchester y Manchester diferencial: 

MODELO GENERICO DE CSMA/CD

Nuestro modelo de CSMA/CD consiste en una alternancia de periodos de inactividad, transmisión y, por supuesto, de contienda:

La pregunta es: ¿Cuanto tiempo tardan dos estaciones que han transmitido a la vez en darse cuenta de que tenemos una colisión? Esto es lo que va a determinar la longitud del periodo de contienda. 

Para ello definimos:
 

Veamos el caso peor, que es cuando la colisión ocurre entre las dos estaciones más distantes para las que el cable tiene un retardo de propagación de t_p (será el mayor de todos, si se normaliza pasa a ser "a"):

Como se puede apreciar en el dibujo, el caso peor es cuando B transmite justo antes de que le llegue el paquete de A, ya que en este caso A tarda 2t_p (en el límite) en darse cuenta de la colisión y por consiguiente dejar de transmitir. Vemos que habrá ahorro de tiempo cuando 2t_p sea menor que el retardo por la transmisión de una trama (lo que es normal en una red LAN). 

Comparemos cuanto valen el intervalo de vulnerabilidad (t_v) y el tiempo de reacción para las principales técnicas estudiadas (tiempos normalizados a x_p):

Podemos concluir que:

Si a >= 1: CSMA=Aloha, no vale para nada la escucha.
Si b >= 1 --> a >= 1/2: CSMA=CSMA/CD, no vale para nada la detección.

Modelo utilizado

Usaremos el modelo general de Aloha ranurado visto pero con variaciones introducidas por la técnica de CSMA:

• El tiempo se divide en dos tipos de slots (valores normalizados a x_p):
• Slots libres que tienen una duración igual al tiempo de propagación, a.
• Slots de transmisión que duran el tiempo de transmisión de una trama, 1.


• No hay detección de colisiones.
• Usa una técnica CSMA no persistente pero distinta a la definición vista anteriormente. (Es una variante ya que no hay retardo aleatorio y se hace una especie de mezcla con CSMA persistente según se explica después).
• Si llega una trama y el canal está ocupado, el nodo pasa a estar retraído y reintenta la transmisión con probabilidad q_r después de cada slot libre (algoritmo de p-persistente).
• Si llega una trama durante un slot libre se transmite en el siguiente slot siempre (algoritmo de Aloha Ranurado).
• Según se ha descrito el funcionamiento, un slot con transmisión (sea con éxito o con colisión siempre va seguido de un slot vacío (los nodos sólo pueden transmitir cuando detectan un slot vacío y el mínimo tiempo de escucha debe ser del tiempo de propagación).

Modelamos el sistema mediante una CADENA DE MARKOV, donde n representa el número de nodos retraídos en cada momento.

Es un modelo discreto en el tiempo. Las transiciones entre estados (posibles cambios de estado) se dan siempre al término de un slot libre. En el caso de Aloha ranurado estas transiciones eran periódicas ya que los slots duraban siempre 1. En este caso las transiciones (posibles cambios) se podrán dar cada a (si es slot vacío) o cada 1+a (si hay transmisión ya que después de trama siempre hay uno vacío).

Podríamos resolver el modelo (calcular probabilidades de la cadena) y obtener las probabilidades estacionarias y valores medios de tráfico y retardo. Sin embargo, nos concentrarmos en calcular lo que nos interesa: la deriva para así poder analizar la estabilidad del sistema. 

Estabilidad

Estando en un slot vacío, tenemos que:

P{siguiente vacío} = P{0 llegadas en slot anterior} * P{0 tx de nodos retraídos} = e-a. (1-qr)n

P{siguiente ocupado} = 1 - P{siguiente vacío} = 1 - e-a . (1-qr)n

Queremos obtener la media del tiempo que hay entre 2 transiciones en la cadena de Markov (OJO que transición hay siempre que termina un slot, haya o no cambio de estado: puede haber una transición al mismo estado). La transición se dará siempre después de un slot vacío ya que sólo puede transmitirse después de haber detectado un slot vacío (de ahí que siempre hay slot vacío después de una trama de transmisión).

Por tanto podemos hacer una tabla: 

Probabilidad	Duración slot sig
e-a . (1-qr)n	a
1 - e-a . (1-qr)n	1 + a

Y definimos:

Queremos hallar la deriva que es:

D_n = llegadas - salidas =  - P_éxito

Y la probabilidad de éxito:

Péxito = P{éxito de tx de nodo NO retraído} + P{éxito de tx de nodo retraído} =

=P{1 llegada en slot anterior (duración a)} . P{ninguna tx de nodos retraídos} +               P{ninguna llegada nueva} . P{1 tx de cualquier nodo retraído}

Luego: Péxito = a..e-a . (1-qr)n + e-a . qr.(1-qr)

NOTA: Hay que contar que cualquiera de los n nodos retraídos retransmita, por tanto deben estar todas las combinaciones distintas: "n sobre 1".

Si la desarrollamos es:

Si q_r es pequeña (caso muy habitual) se puede hacer la aproximación:

• g(n) se puede ver como el número esperado de transmisiones en

• El numerador es el número esperado de salidas por transición de estado.
• El denominador es la duración esperada del período entre cambios de estado.
• Por tanto el cociente se interpreta como el ritmo de salidas por unidad de tiempo (intensidad de tráfico S) en el estado n (salidas del sistema durante el período medio de transición entre estados). Si representamos la gráfica de D_n:
  
  

• Si a << 1 el máximo está aproximadamente en el punto señalado: g=(2a)^½.

En este modelo tenemos población infinita y por eso las llegadas son constantes.

CSMA-Aloha tiene el mismo problema de estabilidad que Aloha normal. Tenemos dos puntos de equilibrio: 1, estable y deseado; y 2, inestable. Si q_r es fija: si n crece al partir del punto 2 de igualdad, entonces el ritmo de salida es menor que el de llegadas y n aumenta indefinidamente --> el sistema se bloquea.

Sin embargo, el problema es menos serio ya que los slots de espera son mucho más cortos y q_r puede ser pequeña sin causar retardos apreciables.

Para mejorar la estabilidad del sistema se podría usar la misma técnica con p-persistente:

• Slot vacío: transmito con probabilidad p en siguiente slot (para nuevas llegadas).
• Si colisiones, retransmitimos con probabilidad q_r << p.

De la misma forma que para Aloha ranurado se pueden usar algoritmos de estabilización:

• Consideramos todos los nodos retraídos nada más llegar una trama.
• Calculamos el valor de q_r estimando el valor de n, sabiendo que el máximo rendimiento se da en g=(2a)^½.

I.2.1.7 - Comparación de Técnicas de Contienda

Vamos a realizar una comparación cualitativa y con la ayuda de unas gráficas de las técnicas de contienda. 

1. Si a es mayor o igual a 1, esto significa que el retardo de propagación es mayor que el de transmisión y según se ha visto: ALOHA es equivalente a CSMA.
2. Si a es mayor o igual que 0.5, esto significa que el retardo de propagación es mayor que la mitad del de transmisión y que detectar o no colisiones no mejora nada: CSMA/CD es equivalente a CSMA
3. Si a es muy inferior a uno, el intervalo vulnerable de ALOHA (igual al de transmisión de una trama) es mucho mayor que el de CSMA y CSMA/CD que son ambos el retardo de propagación en el medio. Si ocurre una colisión, CSMA y ALOHA pierden el mismo tiempo que es el de transmitir una trama completa, mientras que CSMA/CD pierde como mucho 2 veces el retardo de propagación.

Veamos ahora el efecto del retardo sobre las diferentes técnicas de contienda: Notar que si a aumenta las diferencias entre técnicas van disminuyendo. 


 

Retardo de Aloha-r estabilizado comparado con TDM. En la siguiente gráfica, se considera W como el retardo desde la llegada de una trama hasta que comienza la transmisión que acaba con éxito, o sea, no incluye la transmisión final.

En esta gráfica se compara el retardo en Aloha-r estabilizado con el sufrido en un sistema TDM en el que cada usuario tiene un slot reservado y por tanto el retardo es fijo en principio aunque puede incrementarse. Así para 8 usuarios (8 slots) el retardo medio será de 4 slots (debo esperar a mi siguiente slot desde que llega la trama) si el sistema no está muy cargado. Análogamente para 16 usuarios el retardo inicial es de 8. Con cargas bajas TDM da mucho peor retardo que Aloha-r. Sin embargo cuando la carga empieza a subir el retardo de Aloha-r es indefinido mientras que TDM se comporta mucho mejor, su retardo sube muy poco.
 

Comparándolo con Aloha-r sin estabilizar, vemos que cuando I está por debajo del límite (S_max) el retardo es bastante menor y se mantiene bajo a pesar de acercarse a S_max, pero a partir de ese punto el retardo crece indefinidamente también en este caso. Sin embargo ahora S no baja sino que se mantiene: el sistema ya no se colapsa como antes. I.2.2 - Técnicas de Selección
Como ya se ha visto, los protocolos de contienda no funcionan bien ni a alta carga ni cuando el retardo de propagación (a) es mayor que la unidad (el retardo de propagación es el cociente entre el tiempo de propagación, t_p y el tiempo empleado en transmitir la trama, x_p). Por esta razón necesitamos las técnicas de selección, que se basan en la existencia de un turno que da derecho a transmitir. 

Existen dos tipos de control: 

• Control centralizado: existe un moderador que concede el turno. 

• Control distribuido: no existe una estación central, todas las estaciones son iguales. 

I.2.2.1 Selección Centralizada

Hay dos clases distintas de operaciones: 

• Sondeo: La estación principal comprueba si las secundarias quieren transmitir 

• Selección: La estación principal le indica a una estación secundaria que tiene datos que va a transmitirle . El dibujo de la derecha corresponde a una clase especial de selección que recibe el nombre de Fast Select. 

T_sondeo = t_prop + t_s + t_proc + t_prop + t_NAK = 2 · t_prop + t_s + t_proc + t_NAK

T_{sondeo + datos} = 2 · t_prop + t_s + t_proc + t_D + t_proc + t_prop + t_ACK

I.2.2.2 Paso de testigo (control distribuido)

En este tipo de técnicas, existe un concepto fundamental: 

• Testigo: es el derecho o turno para transmitir. Cuando una estación recibe el testigo, si tiene algo que transmitir, lo hace hasta que acaba o llega a un límite superior y pasa el testigo; en caso contrario, sencillamente pasa el testigo a la siguiente estación. 

• Paso de testigo en anillo (anillo físico ). 
• Paso de testigo en bus ( puede ser un anillo lógico ). 

Paso de testigo en anillo (Token Ring)

Cuando una estación desea transmitir, espera a que le llegue el testigo libre. Cambia los bits del testigo ( ahora el testigo está ocupado ) y pone su trama de datos detrás. La trama viaja por el anillo, pasando por todas las estaciones ( cada estación introduce un retardo de 1 bit y la estación a la que va destinada la trama hace una copia de ella) hasta que vuelve a la estación que la envió que se encarga de liberar el testigo ( para liberarlo se tienen que cumplir estas dos condiciones: que la estación haya terminado de transmitir la trama y que el testigo ocupado haya vuelto ); de esta forma se puede estar seguro de que sólo hay una trama en el anillo. 

Paso de testigo en bus (Token Bus)

En este caso la topología física de la red es un bus, pero se forma un anillo lógico entre las estaciones participantes con el objeto de establecer un orden a la hora de intercambiarse el téstigo. Una vez creado el anillo lógico, el funcionamiento es similar al caso anterior.

I.2.2.3 Análisis de prestaciones Token Ring
 

Hay N estaciones y el retardo normalizado es:     a = t_p / x_p. 

Hipótesis: cada estación está siempre preparada para transmitir una trama. 

Sabiendo que T₁ es el tiempo medio para transmitir una trama y que T₂ es el tiempo medio para transmitir el testigo, se calcula el throughput ( S ) : 

Como se puede observar en los siguientes dibujos, hay dos casos claramente diferenciados:

En unidades normalizadas (para normalizar, se divide por el tiempo medio necesario para transmitir una trama), T₁ = 1: 

• a < 1 :    T_ciclo = 1 + a/N 
• a > 1 :    T_ciclo = a + a/N 

• a < 1:    S = 1 / ( 1 + a/N ) 
• a > 1:    S = 1 / a ( 1 + 1/N ) 

• El tiempo de propagación tiende a cero, pues las estaciones están muy cercanas. 
• a < 1 :    S = 1. 
• a > 1 :    S = 1/a. 

En función del retardo normalizado: 

• a < 1 :    D = N + a - 1 
• a > 1 :    D = aN 

Vamos a calcular el tiempo que tiene que esperar una estación para poder transmitir. 

W_e = tiempo de espera hasta que la estación puede transmitir. 

t_c = tiempo de ciclo ( una variable aleatoria ). Depende del número de estaciones que quieran transmitir; el caso peor se producirá cuando todas deseen hacerlo. 

CASO 1 

El tiempo medio de ciclo es igual a T_c.

CASO 2 

El tiempo de ciclo no es constante:

Sea C_d² el coeficiente de dispersión: 

El tiempo de espera para transmitir es:

Hay que calcular el tiempo medio de ciclo ( T_c), para lo que se usan una serie de parámetros: 

• T_R ( tiempo de ronda ) : es el tiempo necesario para que el testigo de una vuelta entera al anillo si ninguna estación tiene tramas que transmitir. 
• l: es la tasa global de llamadas. 
• x_T: tiempo medio de ocupación del canal por trama. ( Nótese que dependiendo del valor de a x_T será o no igual a x_p). 

Para determinar el valor de T_R, se definen: 

• t_r: retardo introducido por la estación al retransmitir el testigo. 
• t_p: retardo de propagación. 

1. Si a < 1 : 

      T_R = N t_r + t_p
      X_T = X_p
2. Si a > 1 : 

      T_R = N t_r + t_p = X_T

I.2.2.4 Análisis de prestaciones Token Bus

Como ya se ha visto, el anillo físico impone un Tiempo de Ronda que depende de la carga y del número de estaciones que desean transmitir. Sin embargo en la topología en bus, el tiempo que se tarda en transmitir el testigo es siempre el mismo. Además presenta la ventaja de que su rendimiento aumenta con el número de estaciones y con la carga. 

Se puede transmitir a continuación del testigo ( no hay que esperar a que vuelva la trama de datos para emitir el testigo, se emite el testigo cuando se acaba con los datos).

Cálculo del tiempo de ciclo:

Siendo:

• X_k: duración del testigo ( normalmente es 0, y se supondrá igual a 0, a menos que se indique lo contrario ). 
• X_T = X_p 

1. LAN 
• Mapa de bits. 
• BRAP. 
• MLMA. 
• Cuenta atrás binaria. 
2. REDES SÁTELITE. 
• Esquema de Binder. 
• Aloha con reserva implícita. 
• Aloha con reserva explícita. 

Mapa de bits 

Supongamos que existen ocho estaciones ordenadas según un número del 0 al 7 que utilizan este método (Figura 1). En el siguiente periodo de contienda, las estaciones 0, 2 y 4 reservan sus ranuras. Inmediatamente después de la reserva, las estaciones transmiten en orden. Del mismo modo, si sólo la estación 7 reserva su ranura, podrá transmitir tras el periodo de reserva. Obviamente, si nadie reserva, los periodos de contienda se suceden de forma continua.  

A continuación se analizan las prestaciones de esta técnica:  

Eficiencia  

Con carga baja (1 estación quiere transmitir):  

Números bajos: se espera N/2 + N = 1,5 N  
(ya que, cuando desee reservar su ranura, se encontrará, en media, en la ranura N/2, con lo que deberemos dejar pasar el restante N/2 del periodo de contienda más otro periodo de contienda adicional)  

Números altos: se espera N/2 = 0,5N  
(ya que, cuando desee reservar su ranura, se encontrará, en media, en la ranura N/2, con lo que deberemos dejar pasar el restante N/2 del periodo de contienda)  

En media, esperaremos N bits de cabecera por cada d bits de datos, con lo que la eficiencia es d/(d+N).  

Con carga alta (todas las estaciones quieren transmitir):  

Se esperan N bits de cabecera por cada N tramas de datos, o sea, Nd bits, con lo que la eficiencia es d/(d+1).  

Retardo  

Con carga alta :  

T_delay= t_cola + N/2 + N/2 d = t_cola + N(d + 1 )/2  
(ya que, en media, debemos esperar a que transcurran N/2 ranuras del periodo de contienda y, además, a que transmitan la mitad de las estaciones)  

Conclusiones:  

• Esta ténica no es ecuánime, penaliza a las estaciones con números bajos: las estaciones con números altos tienen mejor servicio que las de números bajos. 
• Siempre hay que esperar N ranuras para transmitir, lo que produce esperas altas cuando la carga es baja. 
• En general, el período de reserva es demasiado largo. 

BRAP (Broadcast Recognition with Alternating Priorities)

En BRAP, en cuanto una estación pone un 1 en su ranura, empieza a transmitir. Cuando termina, la primera ranura de reserva corresponde a la estación siguiente a la que ha transmitido. En resumen, cada vez que alguien anuncia que quiere transmitir, consigue el canal inmediatamente. Este comportamiento se ilustra en la Figura 2.  

BRAP - FIGURA 2 

Eficencia  

La eficiencia de esta ténica es equivalente a la de Mapa de Bits  

Retardo  

El retardo es:  

• Con carga baja N/2. 
• Con carga alta es aproximadamente igual al de mapa de bits, pues la mayor parte del retardo proviene de las tramas de información y no de las ranuras. 

MLMA: Multi-Level Multi-Access protocol 

Si disponemos de N estaciones, utilizaremos grupos 10 bits para codificar cada cifra del número de cada estación. Así, si contamos con 1000 estaciones, haremos uso de 3 grupos de 10 bits (de 0 a 999). Cuando una estación quiera transmitir, esperará hasta las siguientes ranuras de contienda. Pondrá un 1 en ciertas ranuras, de acuerdo con la codificación del primer dígito de su número de estación. Si sólo quiere transmitir una estación;, hará lo mismo con el resto de sus dígitos, y transmitirá tras las ranuras que llevan su número codificado. Si varias estaciones desean transmitir al mismo tiempo, colocarán sus números en las mismas ranuras de contienda. Todas las estaciones que no hayan puesto a 1 un bit en estas ranuras esperarán hasta que transmitan las que sí lo hayan hecho. Para clarificar el orden de transmisión, se utiliza un criterio similar en el resto de las cifras de los números de estación. Nos serviremos de un ejemplo para explicarlo. 

MLMA - FIGURA 3 

En la Figura 3 observamos la progresión de una contienda en MLMA. Supongamos que las estaciones que desean transmitir son 122, 125, 705, 722 y 725. Durante las ranuras correspondientes a la primera década, se ponen a 1 los bits correspondientes a las cifras 1 y 7, primeros dígitos de los números de las estaciones. 122 y 125 saben que hay estaciones con números mayores que van a transmitir, así que esperan hasta que terminen de emitir sus números. En la segunda ranura, se emiten los segundos dígitos, 2 y 0. La estación 705 sabe que debe esperar. Finalmente, se emite el tercer dígito. En este momento se decide que la primera estación será 725, la segunda, 722 y la tercera 705. Para decidir entre 122 y 125, dichas estaciones transmiten su segundo bit. En este caso sigue habiendo confusión con respecto al orden, de modo que se recurre al tercer bit. Cuando transcurre esta quinta ranura de contienda transcurre la transmisión de las estaciones de acuerdo con el orden establecido en estas etapas.  
Obviamente, la cantidad de ranuras de contienda dependerá de cuántas estaciones deseen hacer uso del canal, y de sus números.  

Como se puede observar, este método permite acceso más rápido (con menor retardo) a las estaciones de números mayores; es decir, no es igualitario.  

Otra característica interesante de MLMA es la elección de la base para la numeración de las estaciones: nada nos impedía utilizar 10 dígitos de base 2 (de 0 a 1023). Si llamamos a la base r y al número de "dígitos" de esa base l, deberá cumplirse que r^l sea igual o mayor que el número de estaciones. Si queremos minimizar el tamaño de la cabecera, o sea, rl, bajo la condición de r^l=N, obtenemos que r=e.  

Eficiencia  

La eficiencia exacta de este método resulta difícil de calcular, pero es posible hacer ciertas estimaciones, referidas a nuestro ejemplo. En condiciones de baja carga, la eficiencia es d/(d+30), donde d es el tamaño de la trama y 30 el tamaño de una cabecera completa. Si todas las estaciones desean transmitir, necesitaremos 111 ranuras: la inicial, para separar las estaciones en grupos de cien; 10, para separar por décadas cada grupo de cien; y 100, para separar cada estación en cada década. Así, en alta carga, son necesarios 1110 bits por cada 1000 tramas de datos, de manera que la eficiencia es d/(d+1,11), muy próxima a la de mapa de bits.  

Retardo  

El retardo medio, en condiciones de baja carga, es de 25 bits: 20 para las estaciones que comienzen por 0 y 30 para las que empiezen por 9; el resto, entre esas dos cifras.  
 
 

Cuenta atrás binaria 

Si tenemos N estaciones, necesitamos log₂ N niveles. Cuando una estación tiene algo que enviar, escribe su dirección en la cabecera como un número binario. Para evitar conflictos, se utiliza la siguiente regla: cada estación coloca su dirección, y se realiza un OR de cada bit de la cabecera. En cuanto una estación detecte que los bits en el medio son distintos de los de su número, desiste. Es decir, que antes transmite quien mayor número tenga.  

Sobre este sistema se pueden realizar mejoras:  

• Como se ha visto, este sistema no es democrático. El número asignado a una estación actúa como una prioridad: una estación sólo transmite si las anteriores (de números menores) no lo hacen. Como solución a este problema, se puede asignar las direcciones de forma dinámica: cada vez que una estación transmite, se le asigna la última posición. 
• Otra posibilidad consiste en diseñar la cabecera para que su primer campo sea la dirección de origen, con lo que se ahorra el período de reserva, pues ambos coinciden. Sin embargo, de esta forma se complica el cambio de direcciones dinámico. 

Estas técnicas surgen para solucionar el problema del retardo: al ser muy grande las colisiones resultan muy costosas. Como solución se utilizan combinaciones de Aloha y reserva.  

Binder 

Se reserva al menos una ranura para cada estación (a cada letra le corresponde una estación). Si una estación está transmitiendo en su ranura, nadie más puede utilizarla. Pero si no la utiliza en un perído de tiempo determinado T, la ranura queda libre y las otras estaciones pueden hacer uso de ella a partir del siguiente perído, T+1, mediante contienda. Cuando una estación quiere recuperar su ranura provoca una colisión; después de una colisión en una ranura, sólo su propietario puede utilizarla.  

En las ranuras libres ( R - N ) se utiliza Aloha Ranurado.  

Por último, Binder presenta el problema de que hay que conocer el número de estaciones a priori (lo cual no sucede muy a menudo).  

Prestaciones  

Con carga baja, resulta algo peor que Aloha Ranurado, pues la proporción de ranuras sin utilizar es mayor. Pero con cargas altas, Binder es mucho mejor: cada estación transmite en su ranura sin provocar colisiones.  

Crowther (Aloha con reserva implícita)

Aquí tambié tenemos N estaciones y R ranuras en cada período de tiempo.  

En este caso R < N y además se hace reserva a priori. Si una estación consigue transmitir con éxito en una ranura, la ranura pasa a ser suya. Es posible incluir alguna condición para "expulsar" una estación de una ranura, a fin de evitar que acapare el canal.  

Roberts (Aloha con reserva explícita)

Las ranuras de reserva se dividen en subranuras. Cada vez que una estación quiere transmitir, tiene que reservar una ranura de información en una subranura. La parte de reserva funciona como Aloha: se compite por los subranuras de reserva. Por esto, las colisiones se producen en los ranuras pequeñas y se pierden pocos bits.  

Las estaciones deben registrar cuántas ranuras se reservan en total en cada período, a fin de saber qué ranura les corresponde.