Control de Errores

Control de ErroresSe trata en este caso de detectar y corregir errores aparecidos en las

transmisiones.

El control de errores en el nivel de enlace de datos se basa en la repetición automática (ARQ), que implica la retransmisión de datos en tres casos: tramas dañadas, tramas perdidas y reconocimiento perdido.

Tipos de errores:Tramas perdidas: cuando una trama enviada no llega a su destinoTramas dañadas: cuando llega una trama con algunos bits erróneos.

Técnicas más usuales de control (ARQ Solicitud de repetición automática) Detección de errores: Cuanto mayor es la trama que se transmite,

mayor es la probabilidad de que contenga algún error. Para detectar errores, se añade un código en función de los bits de la trama de forma que este código señale si se ha cambiado algún bit en el camino. Este código debe de ser conocido e interpretado tanto por el emisor como por el receptor.

Técnicas de control Confirmaciones positivas: el receptor devuelve una confirmación de

cada trama recibida correctamente. Retransmisión después de la expiración de un intervalo de tiempo:

cuando ha pasado un cierto tiempo, si el emisor no recibe confirmación del receptor, reenvía otra vez la trama.

Confirmación negativa y retransmisión: el receptor sólo confirma las tramas recibidas erróneamente, y el emisor las reenvía. Todos estos métodos se llaman ARQ (solicitud de repetición automática). Entre los más utilizados destacan:

Variantes del ARQ normalizadas:ARQ con parada y esperaARQ con adelante atrás NARQ con rechazo selectivo

CLASES DE CONTROL DE ERRORES

Control de Errores Ventana

Deslizante con ARQ

Con vuelta atrás n

Rechazo selectivo

Parada y Espera con ARQ

ARQ con parada y espera Se basa en la técnica de control de flujo de parada-y-espera.

Consiste en que el emisor transmite una trama y hasta que no recibe confirmación del receptor, no envía otra.

Para que la retransmisión funcione se han añadido cuatro características al mecanismo básico de control de flujo:

o El dispositivo emisor mantiene una copia de la última trama transmitida hasta que recibe un reconocimiento para la trama.

o Para poder identificarlas, tanto las tramas de datos como las tramas ACK se numeran alternativamente 0 y 1.

o Si se descubre un error en una trama de datos, lo que indica que ha sido dañada durante la transmisión, se devuelve una trama NAK. Las tramas NAK, que no están numeradas, le dicen al emisor que retransmita la última trama enviada.

ARQ con parada y esperao El dispositivo emisor está equipado con un temporizador. Si el

reconocimiento esperado no se recibe dentro del periodo de tiempo permitido, el emisor asume que la última trama de datos se perdió en el transito y la envía de nuevo.

Puede ocurrir que: La trama no llegue al receptor, en cuyo caso, como el emisor guarda una

copia de la trama y además tiene un reloj, cuando expira un cierto plazo de tiempo sin recibir confirmación del receptor, reenvía otra vez la trama.

La trama llegue defectuosa, en cuyo caso no es confirmada como buena por el receptor. Pero puede ocurrir que el receptor confirme una trama buena pero la confirmación llegue al emisor con error, entonces, el emisor enviaría otra vez la trama. Para solucionar esto, las tramas se etiquetan desde 0 en adelante y las confirmaciones igual. Es una técnica sencilla y barata pero poco eficiente.

Ventana deslizante con ARQEntre los distintos mecanismos populares para el control de errores en transmisión

continua, dos protocolos son los más populares: vuelta atrás n con ARQ y rechazo selectivo con ARQ. Para extender la ventana deslizante de forma que cubra la retransmisión de las tramas perdidas o dañadas, se añaden tres características:

El dispositivo emisor mantiene copias de todas las tramas transmitidas hasta que sean reconocidas.

Además de las tramas ACK, el receptor tiene la opción de devolver la trama NAK si los datos se han recibido con errores. La trama NAK le dice al emisor que retransmita una trama dañada. En este mecanismo al ser continuo las tramas ACK y NAK deben de estar numeradas para su identificación.

Al igual que en la parada y espera con ARQ, el dispositivo emisor en la ventana deslizante con ARQ está equipada con un temporizador que le permite manejar la pérdida de reconocimientos. En la ventana deslizante con ARQ, se pueden enviar n-1 trama (el tamaño de la ventana) antes de recibir un reconocimiento

Vuelta atrás n con ARQ

Con el método de vuelta atrás n con ARQ, si una trama se pierde o tiene errores, se retransmiten todas las tramas desde la última reconocida.

Trama dañada. ¿Qué ocurre si se han enviado las tramas 0, 1, 2 y 3, pero el primer reconocimiento recibido es un NAK 3? Un NAK significa dos cosas: (1)un reconocimiento positivo de todas las tramas recibidas antes de la dañada y (2) un reconocimiento negativo de la trama indicada. Que el primer reconocimiento es un NAK 3, significa que las tramas de datos 0, 1 y 2 se recibieron correctamente. Solamente es necesario reenviar la trama 3.

Trama dañada.

Trama de datos perdida. Los protocolos con ventana deslizante necesitan que las tramas de datos se transmitan secuencialmente. Si una o más tramas están dañadas por el ruido que se pierden en la transmisión, la trama siguiente que llega al receptor no seguirá la secuencia adecuada. El receptor comprueba el número de identificación de cada trama, descubre que se han saltado una o mas tramas y devuelve un NAK para la primera trama perdida. Una trama NAK no especifica si la trama se ha perdido o tiene errores, solamente que debe ser retransmitida. El dispositivo receptor retransmite la trama indicada en el NAK, así como todas las tramas que hubiera transmitido después de la perdida.

Trama de datos perdidos

Reconocimiento perdido. El emisor no espera recibir una trama ACK para cada trama de datos que envía. Por ello, no puede usar la ausencia de números secuenciales ACK para identificar tramas ACK o NAK perdidas. En su lugar, usa un temporizador. El dispositivo emisor puede enviar tantas tramas como le permita su ventana antes de esperar reconocimiento. Una vez que se ha alcanzado este limite o que el servidor no tiene más tramas que enviar, debe esperar.

Si el ACK (o el NAK) enviado por el receptor se pierde, el emisor podría esperar para siempre. Para evitar bloquear ambos dispositivos, el emisor está equipado con un temporizador que empieza a contar cada ves que se excede la capacidad de la ventana. Si no se recibe un reconocimiento antes del plazo del tiempo, el emisor retransmite todas las tramas transmitidas desde el último ACK.

Reconocimiento perdido

Rechazo selectivo con ARQ

En el rechazo selectivo con ARQ, solamente se retransmite la trama especifica que tiene errores o se ha perdido. Si una trama se corrompe en tránsito, se devuelve un NAK y la trama se reenvía fuera de secuencia. El dispositivo receptor debe ser capaz de ordenar las tramas que tiene e insertar la trama retransmitida en e lugar adecuado de la secuencia. Para que esta selectividad sea posible, un sistema con rechazo selectivo ARQ difiere de un sistema con vuelta atrás n ARQ de la forma siguiente:

El dispositivo receptor debe tener lógica de ordenación para permitirle reordenar tramas recibidas fuera de secuencia.

El dispositivo emisor debe contener un dispositivo de búsqueda que le permita encontrar y seleccionar solamente la trama cuya retransmisión ha sido solicitada.

Rechazo selectivo con ARQ Un buffer receptor debe almacenar todas las tramas recibidas

anteriormente a la espera de que todas las retransmisiones hayan sido ordenadas y de que se identifiquen y descarten todas las tramas duplicadas.

Para ayudar con la selección, los números de ACK, como los números de NAK, deben referirse a la trama recibida (o perdida) y no a la siguiente trama esperada.

Para que sea eficiente, esta complejidad necesita un tamaño de ventana más pequeño que el necesario para el método vuelta atrás n. Es recomendable que el tamaño de la ventana sea menor o igual que (n+1)/2, donde n-1 es el tamaño de ventana atrás n.

Rechazo selectivo con ARQ La diferencia del receptor en un sistema de vuelta

atrás n, el receptor en un sistema de rechazo selectivo continúa aceptando tramas nuevas mientras espera que se corrija el error. Sin embargo, debido a que un ACK implica la recepción correcta no solo de la trama especifica indicada sino de todas las anteriores, las tramas recibidas después del error no pueden ser reconocidas hasta que las tramas dañadas hayan sido retransmitidas. En el receptor es necesario tener cierta lógica para ordenar las retransmisiones fuera de orden y seguir la pista a las tramas perdidas que todavía deben ser conocidas.

Rechazo selectivo con ARQ Tramas de datos. Aunque las tramas se pueden recibir fuera de

orden, no se pueden reconocer fuera de orden. Si se pierde una trama, la siguiente llegará desordenada. Cuando el receptor trata de reordenar las tramas que tiene para incluirla, descubrira una discrepancia y enviara un NAK. Por supuesto, el receptor reconocera la omision si se han recibido mas tramas después.

Reconocimiento perdido. Las tramas ACK y NAK perdidas se tratan del metodo de rechazo selectivo con ARQ igual que si se hace en el método vuelta atrás n con ARQ. Cuando el dispositivo emisor alcanza la capacidad de ventana o llega al final de su transmisión activa un temporizador. Sino llega un reconocimiento en el tiempo establecido, el emisor retransmite las tramas pendientes de reconocimiento.

Rechazo selectivo con ARQ

ARQ con rechazo selectivo

Con este método, las únicas tramas que se retransmiten son las rechazadas por el receptor o aquellas cuyo temporizador expira sin confirmación. Este método es más eficiente que los anteriores. Para que esto se pueda realizar, el receptor debe tener un buffer para guardar las tramas recibidas tras el rechazo de una dada, hasta recibir de nuevo la trama rechazada y debe de ser capaz de colocarla en su lugar correcto (ya que deben de estar ordenadas). Además, el emisor debe de ser capaz de reenviar tramas fuera de orden. Estos requerimientos adicionales hacen que este método sea menos utilizado que el de adelante-atrás-N.

Términos y Conceptos Clave

Buffer Rechazo Selectivo con ARQ

Control de errores Reconocimiento (ACK)

Control de flujo Reconocimiento negativo (NAK)

Disciplina de línea Selección

Estación primaria Solicitud/Reconocimiento(ENQ/ACK)

Estación secundaria Sondeo

Fin de transmisión(EOT) Sondeo/Selección

Parada y espera Ventana deslizante

Parada y espera con ARQ Ventana deslizante ARQ

Petición de repetición Automática (ARQ)

Vuelta atrás n con ARQ

Códigos de control de errores

Los códigos de control de errores son siempre redundantes. Un código redundante es el que utiliza más bits de los estrictamente necesarios para la transmisión de los datos; gracias a esta característica se pueden detectar y corregir los errores.

Se dividen en sistemáticos y no sistemáticos, según la forma de añadir los bits redundantes.

Códigos no sistemáticos: En los códigos no sistemáticos los bits redundantes se añaden implícitamente en el código. Se les llama códigos M entre N, como por ejemplo el 3 entre 8, que para emitir un carácter de 8 bits añade otros 3 de control. Los bits de control siempre se ponen a 1 flanqueando el carácter.

Códigos de control de errores

Códigos sistemáticos: En los códigos sistemáticos para determinar el valor de los bits redundantes se aplica un algoritmo a la información a transmitir.

Ejemplos de códigos sistemáticos

Código de paridad horizontal   Con este código se añade un único bit redundante para hacer que el número total de bits sea par o impar.

Código de paridad vertical   Se aplica a más de una palabra de información. Es necesario saber cuántas palabras forman el bloque al que se aplica el algoritmo. A cada palabra se le aplica un código de paridad horizontal y al bloque la paridad vertical, como se ve en el siguiente ejemplo, en el que se ha aplicado paridad par.

Códigos de control de errores

Código de paridad vertical

01001 0

00110 0

00111 1

01000 1

Con este código si hay un error no sólo se detecta sino que se corrige, ya que se puede saber en qué bit se ha producido el error.

Código de Hamming   Con el código de Hamming se añade un número de bits redundantes que depende del número de bits que se usan para representar una palabra de información, de modo que se cumpla la desigualdad

2P ³ P+N+1

donde N es el número de bits por palabra y P el número de bits redundantes.

Códigos de control de errores

Los bits redundantes se añaden intercalándose con los bits que forman la palabra en las posiciones 1, 2, 4, 8, ..., empezando por los bits menos significativos.

Este código es difícil de implementar por circuitería pero sencillo a nivel de software. Sólo es capaz de detectar y corregir un bit erróneo.

Códigos lineales   En este caso se considera que los bits de la palabra forman un vector. A partir de este vector y de un polinomio generador establecido se obtiene otro vector final, según la fórmula

c = i×G

siendo i el vector inicial, G el polinomio generador y c el vector resultante.

Estos códigos facilitan la implementación en hardware, por lo que son más utilizados que los códigos anteriores.

Códigos de control de errores

Dentro de los códigos lineales los más utilizados son los CRC, códigos de redundancia cíclica. En éstos los bits del carácter a enviar son los coeficientes de un polinomio. Utilizan la siguiente fórmula:

P(x) = C(x)·C(x)+R(x), (1)

con R(x) = resto(C(x), G(x)). Lo que se envía por la línea es la información C(x) y el resto R(x), de forma que el destino puede detectar errores mediante la fórmula (1).

Con estos códigos se pueden detectar errores de uno o varios bits en bloques grandes.

Referencias http://www.uhu.es/diego.lopez/Docs_ppal/Transparencias%20Redes%20te

ma3%2005-06.pdf http://www.emagister.com/curso-redes-transmicion-datos-1/transmision-da

tos-deteccion-control-errores http://www2.rhernando.net/modules/tutorials/doc/redes/error.html