Muchos protocolos y algoritmos requieren la serialización o enumeración de entidades relacionadas. Por ejemplo, un protocolo de comunicación debe saber si un paquete viene "antes" o "después" de otro paquete. La RFC 1982 de la IETF ( Internet Engineering Task Force ) intenta definir la "aritmética de números de serie" con el fin de manipular y comparar estos números de secuencia . En resumen, cuando el valor absoluto del número de serie disminuye en más de la mitad del valor máximo (por ejemplo, 128 en un valor de 8 bits), se considera que está "después" del primero, mientras que otras disminuciones se consideran "antes".
Esta tarea es bastante más compleja de lo que parece a primera vista, porque la mayoría de los algoritmos utilizan representaciones de tamaño fijo ( binarias ) para los números de secuencia. A menudo es importante que el algoritmo no "falle" cuando los números se vuelven tan grandes que se incrementan una última vez y "regresan" a sus rangos numéricos máximos (pasan instantáneamente de un número positivo grande a 0 o un número negativo grande). Algunos protocolos optan por ignorar estos problemas y simplemente utilizan números enteros muy grandes para sus contadores, con la esperanza de que el programa sea reemplazado (o se retire) antes de que ocurra el problema (consulte Y2K ).
Muchos protocolos de comunicación aplican la aritmética de números de serie a los números de secuencia de paquetes en su implementación de un protocolo de ventana deslizante . Algunas versiones de TCP utilizan la protección contra números de secuencia envueltos (PAWS) . PAWS aplica la misma aritmética de números de serie a las marcas de tiempo de los paquetes, utilizando la marca de tiempo como una extensión de los bits de orden superior del número de secuencia. [1]
Solo se analiza la adición de un entero positivo pequeño a un número de secuencia y la comparación de dos números de secuencia. Solo se analizan las implementaciones binarias sin signo, con un tamaño arbitrario en bits indicado en todo el RFC (y a continuación) como "SERIAL_BITS".
Sumar un entero a un número de secuencia es una simple suma de enteros sin signo, seguida de una operación de módulo sin signo para devolver el resultado al rango (generalmente implícito en la suma sin signo, en la mayoría de las arquitecturas):
La adición de un valor inferior a 0 o superior a 2 SERIAL_BITS−1 − 1 no está definida. Básicamente, la adición de valores que superen este rango provocará que el número de secuencia resultante se "enrolle" y (a menudo) dé como resultado un número que se considera "menor que" el número de secuencia original.
Se presenta un medio para comparar dos números de secuencia i 1 e i 2 (las representaciones enteras sin signo de los números de secuencia s 1 y s 2 ).
La igualdad se define como igualdad numérica simple.
El algoritmo presentado para la comparación es complejo, ya que debe tener en cuenta si el primer número de secuencia está cerca del "final" de su rango de valores y, por lo tanto, un número "envuelto" más pequeño puede considerarse en realidad "mayor" que el primer número de secuencia. Por lo tanto, i 1 se considera menor que i 2 solo si
Los algoritmos presentados en la RFC tienen al menos un defecto importante: hay números de secuencia para los que no está definida la comparación. Dado que muchos algoritmos son implementados independientemente por múltiples partes que cooperan de manera independiente, a menudo es imposible evitar que se produzcan todas esas situaciones.
Los autores del RFC 1982 reconocen esto sin ofrecer una solución general:
Si bien sería posible definir la prueba de tal manera que la desigualdad no tuviera esta propiedad sorprendente, al estar definida para todos los pares de valores, dicha definición sería innecesariamente complicada de implementar y difícil de entender, y aún permitiría casos en los que
s1 < s2 y (s1 + 1) > (s2 + 1)lo cual es igualmente poco intuitivo.
De esta manera, el caso del problema queda sin definir, las implementaciones tienen la libertad de devolver cualquiera de los resultados o de marcar un error, y los usuarios deben tener cuidado de no depender de ningún resultado en particular. Por lo general, esto significa evitar que esos pares de números en particular coexistan.
Por lo tanto, a menudo resulta difícil o imposible evitar todas las comparaciones "indefinidas" de números de secuencia. Sin embargo, existe una solución relativamente sencilla. Al asignar los números de secuencia sin signo a operaciones aritméticas de complemento a dos con signo , se define cada comparación de cualquier número de secuencia y la operación de comparación en sí se simplifica drásticamente. Todas las comparaciones especificadas por la RFC conservan sus valores de verdad originales; solo se ven afectadas las comparaciones que antes eran "indefinidas".
El algoritmo RFC 1982 especifica que, para números de secuencia de N bits, hay 2 N −1 − 1 valores considerados "mayores que" y 2 N −1 − 1 considerados "menores que". La comparación con el valor restante (exactamente 2 N −1 de distancia) se considera "indefinida".
La mayoría de los equipos modernos implementan operaciones aritméticas binarias de complemento a dos con signo . Estas operaciones están completamente definidas para todo el rango de valores de cualquier operando que se les dé, ya que cualquier número binario de N bits puede contener 2 N valores distintos, y como uno de ellos está ocupado por el valor 0, queda un número impar de espacios para todos los números positivos y negativos distintos de cero. Simplemente hay un número negativo más representable que positivos. Por ejemplo, un valor de complemento a dos de 16 bits puede contener números que van desde−32 768 a+32 767 .
Entonces, si simplemente reformulamos los números de secuencia como números enteros de complemento a 2 y permitimos que haya un número de secuencia más considerado "menor que" que números de secuencia considerados "mayores que", deberíamos poder usar comparaciones aritméticas con signo simples en lugar de la fórmula lógicamente incompleta propuesta por el RFC.
A continuación se muestran algunos ejemplos (de nuevo en 16 bits) que comparan algunos números de secuencia aleatorios con el número de secuencia con el valor 0:
binario sin signo con signodistancia del valor de secuencia-------- ------ -------- 32767 == 0x7FFF == 32767 1 == 0x0001 == 1 0 == 0x0000 == 0 65535 == 0xFFFF == −1 65534 == 0xFFFE == −2 32768 == 0x8000 == −32768
Es fácil ver que la interpretación con signo de los números de secuencia está en el orden correcto, siempre que "rotemos" el número de secuencia en cuestión de modo que su 0 coincida con el número de secuencia con el que lo estamos comparando. Resulta que esto se hace simplemente utilizando una resta sin signo y simplemente interpretando el resultado como un número de complemento a dos con signo. El resultado es la "distancia" con signo entre los dos números de secuencia. Una vez más, si i1y i2son las representaciones binarias sin signo de los números de secuencia s 1 y s 2 , la distancia de s 1 a s 2 es
distancia = ( con signo )( i1 - i2 ) Si la distancia es 0, los números son iguales. Si es < 0, entonces s 1 es "menor que" o "anterior" a s 2 . Sencillo, claro y eficiente, y completamente definido. Sin embargo, no sin sorpresas.
Toda aritmética de números de secuencia debe tratar con el "envolvimiento" de números de secuencia; el número 2 N −1 es equidistante en ambas direcciones, en términos de números de secuencia de RFC 1982. En nuestras matemáticas, ambos se consideran "menores" entre sí:
distancia1 = ( con signo )( 0x8000 - 0x0 ) == ( con signo ) 0x8000 == -32768 < 0 distancia2 = ( con signo )( 0x0 - 0x8000 ) == ( con signo ) 0x8000 == -32768 < 0 Obviamente, esto es cierto para cualesquiera dos números de secuencia con una distancia de 0x8000 entre ellos.
Además, la implementación de la aritmética de números de serie mediante la aritmética de complemento a dos implica números de serie de una longitud de bits que coincida con los tamaños de enteros de la máquina; normalmente, 16 bits, 32 bits y 64 bits. La implementación de números de serie de 20 bits necesita cambios (suponiendo que son enteros de 32 bits):
distancia = ( con signo )(( i1 << 12 ) - ( i2 << 12 ))