©Oscar Agudelo. 2000-2003. Todos los derechos reservados.
En ocasiones, los paquetes de datos al moverse de un nodo a otro pueden alterarse, generando errores en la información que transportan. Este tipo de errores deben evitarse para que la información que transporte la red sea confiable. Sin esta confiabilidad las personas (los usuarios) no utilizarían las redes.
La idea básica detrás de los esquemas de detección de errores en redes es adicionar información redundante al paquete, de tal forma que permita determinar si un error ha sido introducido mientras se llevaba de un nodo a otro. Un esquema de detección de errores que podemos imaginar es la transmisión completa de dos copias del mismo paquete. Si las dos copias son idénticas cuando lleguen al receptor, es muy probable que la información esté correcta. Si no son iguales, un error fue introducido en una de las copias (o en ambas) y deben ser descartadas. Este esquema de detección de errores es deficiente: se requieren n bits de correción de errores para un mensaje de n bits y además, si por alguna razón, los errores ocurren en el mismo lugar en los dos paquetes, no serán detectados.
Afortunadamente se pueden hacer cosas mejores. En general, se puede proporcionar una capacidad de detección de errores más fuerte enviando sólo k bits redundandes en un mensaje de n-bits, donde k << n (k mucho más pequeño que n). Por ejemplo, el frame de Ethernet puede llevar hasta 12000 bits (1500 bytes) y utiliza sólo 32 bits redundantes para detectar errores (usa un código de redundancia cíclica conocido como CRC-32).
Los bits adicionados al mensaje son redundantes pues no adicionan nueva información al mensaje sino que se calculan directamente del mensaje original utilizando un algoritmo bien definido. El nodo que transmite y el que recibe deben conocer exactamente el algoritmo utilizado. El transmisor del mensaje aplica el algoritmo al mensaje que desea enviar para generar los bits redundantes y envía el mensaje y los bits extras. Cuando el receptor aplica el mismo algoritmo al mensaje recibido, el resultado debe ser (en ausencia de errores) el mismo enviado por el transmisor. Al concordar los dos resultados, el receptor sabe, con una alta probabilidad, que no hubo errores durante el movimiento del paquete. En caso de no concordar, el receptor debe tomar la acción apropiada (descartar el paquete y esperar su retransmisión o, si le es posible, corregir los errores).
En general, los bits adicionados a un mensaje para detectar errores se llaman error-detecting codes. En ciertos casos específicos, cuando el algoritmo para crear el código se basa en la adición, reciben el nombre de checksums. Infortunadamente, la palabra checksum se usa de manera incorrecta, queriendo nombrar con ella cualquier código de detección de errores, incluyendo aquellos que no son sumas, como los CRCs. El checksum de Internet recibe el nombre correcto, pues es un chequeo de errores que utiliza un algoritmo de suma.
2. El algoritmo de checksum
La idea en la que se basa la suma de chequeo de Internet es muy sencilla: se suman todas las palabras de 16 bits que conforman el mensaje y se transmite, junto con el mensaje, el resultado de dicha suma (este resultado recibe el nombre de checksum). Al llegar el mensaje a su destino, el receptor realiza el mismo cálculo sobre los datos recibidos y compara el resultado con el checksum recibido. Si cualquiera de los datos transmitidos, incluyendo el mismo checksum, esta corrupto, el resultado no concordará y el receptor sabrá que ha ocurrido un error.
El checksum se realiza de la siguiente manera: los datos que serán procesados (el mensaje) son acomodados como una secuencias de enteros de 16 bits. Estos enteros se suman utilizando aritmética complemento a uno para 16 bits y, para generar el checksum, se toma el complemento a uno para 16 bits del resultado.
En aritmética complemento a uno, un entero negativo -x se representa como el complemento de x; es decir, cada bit de x es invertido. Cuando los números se adicionan, si se obtiene un acarreo (carry) en el bit más significativo, se debe incrementar el resultado. Por ejemplo, sumemos -5 y -3 en aritmética complemento a uno con enteros de 4 bits. En este caso +5 se representaría con 0101 y -5 con 1010; +3 se representaría con 0011 y -3 con 1100. Al sumar 1010 y 1100, ignorando el acarreo (carry) que queda en el bit más significativo, tendremos como resultado 0110. En la aritmética complemento a uno, cuando una operación genera un acarreo (carry) en el bit más significativo, se debe incrementar el resultado; es decir que 0110 se convierte en 0111, que es la representación complemento a uno de -8 (obtenido de invertir los bits 1000).
El uso del algoritmo de checksum de Internet en los headers
de los protocolos se puede resumir en tres pasos simples.
0110011001100110
0101010101010101
0000111100001111
La suma de las dos primeras palabras sería:
0110011001100110
0101010101010101
1011101110111011
Adicionando ahora la tercera "palabra" al resultado anterior tenemos
1011101110111011
0000111100001111
1100101011001010
La suma complemento a uno se obtiene convirtiendo todos los ceros en unos y todos los unos en ceros. De esta forma la suma complemento a uno de 1100101011001010 sería 0011010100110101. Que vendría a ser el checksum. Al llegar al receptor las cuatro palabra de 16 bits, incluyendo el checksum son sumados y el resultado debe ser 1111111111111111. Si uno de los bits es cero, un error ha sido detectado.
Dependiendo del protocolo, se deben seleccionar ciertos campos de los headers para realizar los cálculos del checksum. En IP el checksum se calcula sólo sobre los octetos que componen el header del datagrama (RFC791), en UDP (RFC768) se calcula sobre un seudo-header , el header UDP y los datos que transporta UDP y en TCP (RFC793) se hace un cálculo similar que en UDP. Si desea conocer los detalles del cáculo del checksum puede ver los siguientes ejemplos.
La siguiente rutina es una implementación directa del algoritmo de checksum de Internet. El argumento cantidad trae la longitud del buffer medido en unidades de 16 bits. La rutina asume que buffer ha sido rellenado de ceros (0) para que se ajuste a un tamaño múltiplo de 16 bits.
u_short checksum (u_short *buffer, int cantidad) {
register u_long suma = 0;
while (cantidad--) {
suma += *buffer++;
if (suma & 0xFFFF0000) {
/* hubo acarreo,
se debe incrementar el resultado */
suma &= 0xFFFF;
suma++;
}
}
return ~(suma & 0xFFFF);
}
Este código asegura que el cálculo utiliza aritmética complemento a uno, antes que aritmética complemento a dos que es la utilizada por la mayoría de máquinas. Observe el if dentro del ciclo while. Si existe un acarreo (carry) al final de la suma de 16 bits, entonces se incrementa suma.
Al utilizar este checksum, se agregan 16 bits al mensaje original como código de detección de errores, pero esta no es una técnica fuerte de detección de errores. ¿por qué? Por ejemplo, si una pareja de bits individuales, uno de los cuales incrementa una palabra de 16 bits, de las que conforman el mensaje, en cierta cantidad y el otro bit decrementa otra palabra de 16 bits en la misma cantidad, al realizar la suma de chequeo no será detectado el error. La razón por la cual un algoritmo como éste es utilizado, aunque tenga una protección débil contra errores, es simple: este algoritmo es fácil de implementar en software (el algoritmo de CRC utilizado en los protocolos de la capa de enlace, como Ethernet y Token Ring se implementan en el hardware de las tarjetas de red). Además la experiencia observada en ARPANET sugirió que un checksum era adecuado: este checksum es la última línea de defensa en los protocolos de TCP/IP pues la gran mayoría de errores son descubiertos por algoritmos de detección de errores más fuertes, tales como los CRCs utilizados en la capa de enlace (capa 2 del modelo OSI).
3. Detección de errores versus la corrección de errores
A primera vista uno puede suponer que corregir errores es mucho mejor que sólo detectarlos, ya que evitaría tener que reenviar el paquete completo que, entre otras cosas, aumenta el uso de ancho de banda y produce un tiempo de latencia mientras se retransmite el mensaje. Sin embargo, la corrección de errores tiene su lado malo: requiere un mayor número de bits redundantes para que sea tan fuerte (es decir capaz de corregir el mismo rango de errores) como un código que sólo detecta errores. De esta forma, mientras la detección de errores requiere que más bits sean enviados cuando algún error ocurre, la corrección de errores requiere enviar más bits todas las veces. Como resultado, la corrección de errores es útil en dos condiciones:
1. Cuando los errores son demasiado probables. Por ejemplo, en ambientes
inalámbricos.
2. Cuamdo el costo de retransmisión es demasiado alto. Por ejemplo,
el tiempo de latencia involucrado en la retransmisión de un paquete
sobre un enlace de satélite.
El uso de códigos de corrección de errores es llamado, en redes, FEC (forward error correction) porque la corrección de errores es manejada de antemano, con información extra, en lugar de esperar a que los errores sucedan y manejarlos con retransmisión.