PROTOCOLOS LIBRES DE COLISIONES Aunque Las colisiones no ocurren en CSMA/CD una vez que una estación ha tomado sin ambigüedades el canal, aún puede ocurrir durante el periodo de contención. Estas colisiones afectan adversamente el desempeño del sistema, especialmente cuando el cable es largo y los marcos cortos. En los protocolos que describiremos suponemos que hay N estaciones, cada una con una dirección única de 0 a N − 1 incorporada en hardware. El que unas estaciones puedan estar inactivas parte del tiempo no importa. La pregunta básica persiste: ¿qué estación toma el canal tras una transmisión exitosa? UN PROTOCOLO DE MAPA DE BITS En el protocolo libre de colisiones denominado método básico de mapa de bits cada periodo de contención consiste en exactamente N ranuras. Si la estación 0 tiene un marco por enviar, transmite un bit durante la ranura 0. No está permitido a ninguna otra estación transmitir durante este intervalo. Sin importar lo que haga la estación 0, la estación 1 tiene la oportunidad de transmitir un 1 durante la ranura 1, pero sólo si tiene en cola un macro. En general la estación j puede anunciar que tiene un macro por enviar introduciendo un bit 1 en la ranura j. Una vez que han pasado las N ranuras, cada estación tiene conocimiento completo de las estaciones que quieren transmitir. En este punto, las estaciones comienzan a transmitir en orden numérico (véase la siguiente figura). HN DV Dado que todos están de acuerdo en quién continúa, nunca habrá colisiones. Un a vez que la última estación lista haya transmitido su marco, evento que pueden detectar fácilmente todas las estaciones, comienza otro período de contención de N bits. Si una estación queda lista justo después de que ha pasado su ranura de bit, ha tenido mala suerte y deberá permanecer callada hasta que cada estación haya tenido su oportunidad y el mapa de bits haya comenzado de nuevo. Los protocolos como éste en los que el deseo de transmitir se difunde antes de la transmisión se llaman protocolos de reservación. Analicemos brevemente el desempeño de este protocolo. Por conveniencia, mediremos el tiempo en unidades de la ranura de bit de contención, con marcos de datos consistentes en d unidades de tiempo. En condiciones de carga baja, el mapa de bits simplemente se repetirá una y otra vez, debido a la falta de marcos de datos. Considere la situación desde el punto de vista de una estación de número bajo, como 0 o 1. Típicamente, cuando la estación queda lista para transmitir, la ranura actual estará en algún lugar a la mitad del mapa de bits. En promedio, la estación tendrá que esperar N /2 ranuras para que el barrido actual termine, y otras N ranuras para que el siguiente barrido se ejecute hasta su terminación, antes de poder comenzar a transmitir. Las perspectivas para las estaciones de número alto son mejores. En general, éstas sólo tendrán que esperar la mitad de un barrido (N /2 ranuras de bit) antes de comenzar a transmitir. Las estaciones de número alto pocas veces tienen que esperar el siguiente barrido. Dado que las estaciones de número bajo deben esperar un promedio de 1.5N ranuras y las estaciones de número alto deben esperar un promedio de 0.5N ranuras, la media de todas las estaciones es de N ranuras. La eficiencia del canal cuando la carga es baja es fácil de calcular. La información extra por marco es de N bits, y al cantidad de datos es de d bits, dando una eficiencia de d / (N + d). Si la carga es alta y todas las estaciones tienen algo que enviar todo el tiempo, el periodo de contención de N bits se prorratea entre N marcos, arrojando una información extra de sólo 1 bit por marco, o una eficiencia de d / (d + 1). El retardo medio de un marco es igual a la suma del tiempo que está en cola en su estación más un 1

N (d + 1) /2 adicional una vez que llaga a la cabeza de su cola interna. CONTEO DESCENDENTE BINARIO Un problema con el protocolo básico de mapa de bits es que la información extra es de 1 bit por estación. Podemos tener mejores resultados usando direcciones de estación binarias. Una estación que quiere usar el canal ahora difunde su dirección como una cadena binaria de bits, comenzando por el bit de orden mayor. Se supone que todas la direcciones tienen la misma longitud. A los bits en cada posición de dirección de las diferentes estaciones se aplica un OR BOOLEANO a todos juntos. Llamaremos a este protocolo conteo descendente binario; el cual se usa en Datakit (Fraser, 1987). Para evitar conflictos, debe aplicarse una regla de arbitraje: tan pronto una estación ve que en una posición de bit de orden alto que en su dirección es 0 ha sido sobrescrita con un 1, se da por vencida. Por ejemplo, si las estaciones 0010, 0100, 1001 y 1010 están todas tratando de obtener el canal, en el primer tiempo de bit las estaciones transmiten 0, 0, 1 y 1 respectivamente. A éstos se les aplica el OR para formar un 1. Las estaciones 0010 y 0100 ven el 1 y saben que una estación de número mayor está compitiendo por el canal, por lo que se dan por vencidas durante esta ronda. Las estaciones 1001 y 1010 continúan. El siguiente bit es 0, y ambas estaciones continúan. El siguiente bit es 1, por lo que la estación 1001 se da por vencida. La ganadora es la estación 1010, debido a que tiene la dirección mayor. Tras ganar el concurso, ahora puede transmitir un marco, después de lo cual comienza otro ciclo de concurso. El protocolo se ilustra en la siguiente figura. La eficiencia de canal de este método es de d /( d + ln N). Sin embargo, si el formato de marco se escoge ingeniosamente de modo que la dirección del transmisor sea el primer campo del marco, ni siquiera estos ln N bits se desperdician, y la eficiencia es del 100%. Mok y Ward (1979) han descrito una variación del conteo descendente binario usando una interfaz paralela en lugar de serial. También sugieren el uso de números virtuales de estación, permutándose circularmente tras cada transmisión los números virtuales de estación desde 0 hasta el de la estación ganadora, inclusive, a fin de darle mayor prioridad a las estaciones que han estado en silencio demasiado tiempo. Por ejemplo, si las estaciones C, H, A, G, B, E, D. Por tanto, C permanece como la estación virtual 7, pero A sube de 4 a 5 y D cae de 5 a 0. La estación D ahora sólo srá capaz de adquirir el canal si ninguna otra estación lo quiere. 1 1 1 1 1 3 7 1 1

2

1 5 1 2 0 1 2 3 4 5 6 7 7 4 3 2 1 5 0 6 7 4 3 2 1 5

3

0 6 1 d 8 ranuras de contención 8 ranuras de contención Marcos 0010 0100 1001 1010 Tiempo de bit 0123 0−−− 0−−− 100− 1010 1010 Resultado Las estaciones 0010 y 0100 ven este 1 y se dan por vencidas La estación 1001 ve este 1 y se da por vencida FIGURA: Protocolo de conteo descendente binario. Los guiones indican silencios. FIGURA: Protocolo básico de mapa de bits

4