Carrier sense multiple access with collision detection

Existen dudas o desacuerdos sobre la exactitud de la información en este artículo o sección. Consulta el debate al respecto en la página de discusión. Uso de esta plantilla: {{Discutido|t={{sust:CURRENTTIMESTAMP}}}} o {{sust:Discutido}}

En comunicaciones, CSMA/CD (del inglés Carrier Sense Multiple Access with Collision Detection) o, en español, acceso múltiple con escucha de portadora y detección de colisiones, es un algoritmo de acceso al medio compartido. Su uso está especialmente extendido en redes Ethernet donde es empleado para mejorar sus prestaciones. En CSMA/CD, los dispositivos de red escuchan el medio antes de transmitir, es decir, es necesario determinar si el canal y sus recursos se encuentran disponibles para realizar una transmisión. Además, mejora el rendimiento de CSMA finalizando el envío cuando se ha detectado una colisión.

Historia

Una red en donde los equipos pueden transmitir de forma simultánea varios paquetes es propensa a sufrir colisiones que generan, en el mejor de los casos, retardos en la entrega de estos paquetes y, en otros, la pérdida de información. Para evitar estas situaciones se desarrollaron las técnicas de control de acceso al medio.

Las bajas prestaciones de los primeros mecanismos empleados: Aloha y Aloha ranurado, provocaron la aparición de nuevas técnicas encaminadas a la gestión más eficiente de los recursos de una red, dando lugar al algoritmo CSMA y posteriormente a su evolución CSMA/CD (CSMA con detección de colisiones).

Procedimiento

El siguiente procedimiento se usa para iniciar una transmisión. El procedimiento se completa cuando la trama se transmite con éxito o se detecta una colisión durante la transmisión.

1. ¿Hay una trama lista para transmitir? Si no, esperar por una trama.
2. ¿Está el medio inactivo? Si no, esperar hasta que esté listo.
3. Comenzar a transmitir y monitorear colisiones durante la transmisión.
4. ¿Ocurrió una colisión? De ser así, ir al procedimiento de colisión detectada.
5. Restablecer los contadores de retransmisión y completar la transmisión de la trama.

El siguiente procedimiento se usa para resolver una colisión detectada. El procedimiento se completa cuando se inicia la retransmisión o se cancela la retransmisión debido a numerosas colisiones.

1. Continuar la transmisión (con una señal de atasco en lugar de un encabezado de trama/datos/CRC) hasta que se alcance el tiempo mínimo para garantizar que todos los receptores detecten la colisión.
2. Incrementar el contador de retransmisión
3. ¿Se alcanzó el número máximo de intentos de transmisión? Si es así, abortar la transmisión.
4. Calcular y esperar el período de espera aleatorio según el número de colisiones.
5. Volver a ingresar al procedimiento principal en el paso 1.

Los métodos para la detección de colisiones dependen de los medios. En un bus eléctrico compartido, como 10BASE5 o 10BASE2, las colisiones se pueden detectar comparando los datos transmitidos con los datos recibidos o reconociendo una amplitud de señal superior a la normal en el bus. En todos los demás medios, una portadora detectada en el canal de recepción mientras se transmite desencadena un evento de colisión. Los repetidores o concentradores detectan colisiones por sí mismos y propagan señales de atasco.

El procedimiento de recuperación de colisión se puede comparar con lo que sucede en una cena, donde todos los invitados hablan entre sí a través de un medio común (el aire). Antes de hablar, cada invitado educadamente espera que termine el orador actual. Si dos invitados comienzan a hablar al mismo tiempo, ambos se detienen y esperan periodos de tiempo cortos y aleatorios (en Ethernet, este tiempo se mide en microsegundos). La esperanza es que al elegir un período de tiempo aleatorio, ambos invitados no elijan el mismo momento para tratar de hablar nuevamente, evitando así otra colisión.

Trama de CSMA/CD

La trama empleada en CSMA/CD está formada por ocho campos:

• El preámbulo, formado por 7 octetos, es el encargado de que el receptor pueda sincronizarse con el emisor, de forma que pueda localizarse el principio de la trama.

• Delimitador de inicio: es un byte empleado para indicar al receptor el inicio de la trama.

• Dirección de destino: contiene la dirección física (MAC) del equipo destinatario de la trama.

• Dirección de origen: contiene la dirección MAC de la estación emisora de la trama y tiene un formato similar al de la dirección de destino.

• Longitud: indica la longitud del campo de datos que se encuentra a continuación. Es necesaria para determinar la longitud del campo de datos en los casos que se utiliza un campo de relleno.

• Información: contiene los datos transmitidos. Es de longitud variable, por lo que puede tener cualquier longitud entre 42 y 1500 bytes.

• Relleno: es usado para que la trama alcance la longitud mínima requerida. Una trama debe contener un mínimo número de bytes para que las estaciones puedan detectar las colisiones con precisión.

• Chequeo: contiene un código de redundancia cíclica de 32 bits. Es utilizada como mecanismo de control de errores en la transmisión.

Tipos de CSMA/CD

El algoritmo CSMA/CD puede estar basado en cualquiera de los siguientes procedimientos:

• CSMA 1-persistente: cuando una estación quiere transmitir, primero escucha el canal. Si este está libre entonces transmite inmediatamente. En el caso contrario permanece a la escucha hasta que esté libre. En el momento en el que la estación considere que el canal está disponible, se transmite inmediatamente. El problema radica en que varias estaciones pueden estar esperando a que el canal esté libre para transmitir, dando lugar a una colisión de sus tramas.

• CSMA no persistente: funciona de forma análoga al anterior excepto en el hecho de que cuando detecta que el canal está ocupado, en vez de permanecer a la espera escuchándolo, espera un tiempo aleatorio y vuelve a escuchar el canal. Con este método se reducen las colisiones si el tráfico es elevado, mejorándose la utilización del canal. Sin embargo aumentan los retardos para cargas de tráfico bajas .

• CSMA p-persistente: al igual que en los casos anteriores se escucha el canal, sin embargo si este está libre, en vez de transmitir inmediatamente, se transmite con una probabilidad p, o bien se retrasa la emisión una ranura temporal con una probabilidad q=1-p . Esta ranura temporal suele ser igual al máximo retardo de propagación de la señal.

Habitualmente suele ser utilizado el algoritmo 1-persistente, pues es empleado en el estándar IEEE_802.3.

Funcionamiento

Funcionamiento general

En CSMA/CD, cada estación que desea transmitir debe realizar una escucha del medio –detección de portadora– para comprobar si este se encuentra libre, es decir, para comprobar que ninguna otra estación está en ese instante transmitiendo un mensaje. Si el medio se encuentra libre entonces tiene lugar dicha transmisión. Aun así, puede ocurrir que varias estaciones tengan mensajes para enviar y que comiencen a transmitir una trama en el mismo instante. Cuando esto se sucede, se dice que ha ocurrido una colisión en la red. La estación que ha detectado la colisión procederá a enviar un mensaje de jam de 32 bits al resto de estaciones para notificar dicho evento. Una vez que todas las estaciones han sido notificadas, automáticamente se paran todas las transmisiones y se ejecuta un algoritmo de backoff (o de postergación) que consiste en esperar un tiempo aleatorio (backoff) antes de volver a intentar la transmisión. Durante los 10 primeros intentos el valor medio del tiempo de espera se duplica mientras que durante los 6 siguientes intentos adicionales, se mantiene. Tras 16 intentos fallidos, el algoritmo notificará un error a las capas superiores.

Problemática en redes inalámbricas

En las redes inalámbricas proceder a la escucha del medio y por lo tanto detectar las colisiones producidas, puede resultar complicado. Esto se manifiesta en dos problemáticas:

• Problema del nodo oculto: una estación puede creer que el canal (medio) está libre cuando en realidad está ocupado por otra estación a la que no oye. En la siguiente imagen se muestra como A y C transmiten hacia B ya que ambos detectaron que el canal estaba libre. Sin embargo B escucha a ambos nodos, dando lugar a una colisión.

• Problema del nodo expuesto: una estación puede creer que el canal está ocupado cuando en realidad lo está ocupando otra estación que no interferiría en su transmisión a otro destino. En la figura se muestra como C está comunicándose con B. Como D detecta que el canal está ocupado, no puede transmitir hacia E, cuando lo idóneo sería que sí pudiese.

Estos problemas fueron resueltos con la implementación del algoritmo CSMA/CA (MultiAccess Collision Avoidance)

Eficiencia y características

CSMA/CD puede encontrarse en alguno de los siguientes estados:

• Período de contienda o contención: es el intervalo de tiempo durante el cual una trama es vulnerable a colisiones
• Período de transmisión: intervalo de tiempo durante el cual una estación transmite obteniendo el control del canal
• Período vacío: intervalo de tiempo durante el cual el canal está vacío

El período de contienda se encuentra formado por ranuras de longitud 2τ y será el tiempo que una estación tardará en darse cuenta de que su trama colisionó: si una estación A comienza a transmitir en el instante t0, la señal tardará un tiempo τ (tiempo de transmisión de la trama) en llegar a la estación más alejada de ella (llamémosla B). Ahora bien, B podrá comenzar a transmitir hasta un instante antes de que la señal de A llegue; si lo hace inmediatamente luego se dará cuenta de que hubo una colisión y abortará su transmisión. Sin embargo, el "ruido" causado por la colisión no llegará hasta la estación A hasta un tiempo igual al doble de propagación de la señal entre A y B, es decir, 2τ. Esto implica que una estación no pueda estar segura de que obtuvo el canal sino hasta haber transmitido durante 2τ sin tener una colisión.

Teniendo en cuento lo anterior, algunos de los parámetros de CSMA/CD quedan definidos como:

• Eficiencia:

${\displaystyle \eta ={\frac {Ge^{-2aG}}{1+(G-2aG)e^{-2aG}}}}$

G = intensidad de tráfico ofrecido

• Eficiencia máxima:

${\displaystyle \eta _{m}\approx {\frac {1}{1+(3.44a)}}}$

• Probabilidad de que el medio esté libre:

${\displaystyle p(medio\ libre)={\frac {1}{1+(G-2aG)e^{-2aG}}}}$

• Tiempo de transmisión de la trama :

${\displaystyle \tau ={\frac {L_{t}}{C}}}$

Lt = Longitud de la trama

• Relación entre el tiempo de propagación y retardo:

${\displaystyle a={\frac {t_{p}}{\tau }}}$

Aplicaciones

CSMA/CD fue usado en las -ahora obsoletas- variantes de Ethernet 10BASE5 y 10BASE2. Actualmente las modernas redes Ethernet construidas con switches y conexiones full-duplex lo mantienen como modo de retrocompatibilidad.

Véase también

• Ethernet
• ALOHAnet
• CSMA
• CSMA/CA (Carrier sense multiple access with collision avoidance)
• Acceso al medio
• Dirección MAC
• IEEE 802.3

Bibliografía

• Xavier Hesselbach Serra,Jordi Altés Bosch (2002). Análisis de redes y sistemas de comunicaciones. Edicions UPC. ISBN 84-8301-611-7. 
• Jorge Lázaro Laporta,Marcel Miralles Aguiñiga (2005). Fundamentos de telemática. Universidad Politécnica de Valencia. ISBN 84-9705-913-1. 
• Josep M. Barcelo Ordinas, Jordi Íñigo Griera, Jaume Abella I Fuentes (2009). Estructura de redes de computadores. UOC. ISBN 978-84-9788-791-5. 
• Larry L. Peterson,Bruce S. Davie (2011). Computer Networks: A Systems Approach. MK. ISBN 978-0-12-385059-1. 
• James F. Kurose, Keith W. Ross (2012). Computer Networking:A Top-Down Approach. Pearson Education. ISBN 90132856204,9780132856201. 
• Han sido empleados parte de los apuntes de la materia Redes y Servicios Telemáticos (Universidad de Vigo)

Enlaces externos

• Standards IEEE
• IEEE802.3