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. El RFC 1982 del 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 podría parecer a primera vista, porque la mayoría de los algoritmos utilizan representaciones de tamaño fijo ( binarias ) para números de secuencia. A menudo es importante que el algoritmo no se "descomponga" cuando los números se vuelven tan grandes que se incrementan una última vez y "envuelven" sus rangos numéricos máximos (pasan instantáneamente de un número positivo grande a 0 o a 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 (ver 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 protección contra números de secuencia ajustados (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]
Sólo se analiza la suma de un pequeño número entero positivo a un número de secuencia y la comparación de dos números de secuencia. Sólo 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".
Agregar un número 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, agregar valores más allá de este rango hará que el número de secuencia resultante "se ajuste" 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 comparación es complejo y 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 "mayor" que la primera secuencia. número. Por lo tanto, i 1 se considera menor que i 2 sólo si
Los algoritmos presentados por el RFC tienen al menos un inconveniente importante: hay números de secuencia cuya comparación no está definida. Dado que muchos algoritmos son implementados de forma independiente por múltiples partes cooperantes independientes, a menudo es imposible evitar que ocurran todas estas 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, aunque estuviera definida para todos los pares de valores, tal definición sería innecesariamente complicada de implementar y difícil de entender, y aún así permitir casos en los que
s1 < s2 y (s1 + 1) > (s2 + 1)lo cual es igualmente poco intuitivo.
Por lo tanto, el caso del problema queda indefinido, las implementaciones son libres de devolver cualquier resultado o señalar un error, y los usuarios deben tener cuidado de no depender de ningún resultado en particular. Por lo general, esto significará evitar permitir que esos pares de números particulares coexistan.
Por tanto, a menudo es 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 en 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 el RFC conservan sus valores de verdad originales; sólo se ven afectadas las comparaciones anteriormente "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 -distante) se considera "indefinida".
La mayoría del hardware moderno implementa operaciones aritméticas binarias en 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 dado que uno de ellos está ocupado por el valor 0, hay un número impar. de lugares restantes 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 en complemento a 2 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 enteros en complemento a 2 y permitimos que haya un número de secuencia más considerado "menor que" que los números de secuencia considerados "mayores que", deberíamos poder usar comparaciones aritméticas con signos simples en su lugar. de la fórmula lógicamente incompleta propuesta por el RFC.
Aquí hay algunos ejemplos (en 16 bits, nuevamente), comparando algunos números de secuencia aleatorios con el número de secuencia con el valor 0:
binario sin signo firmadodistancia 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 y cuando "rotemos" el número de secuencia en cuestión para que su 0 coincida con el número de secuencia con el que lo estamos comparando. Resulta que esto simplemente se hace usando una resta sin signo y simplemente interpretando el resultado como un número en 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 "antes" de s 2 . Simple, limpio y eficiente, y completamente definido. Sin embargo, no sin sorpresas.
Toda aritmética de números de secuencia debe ocuparse de la "agrupación" de números de secuencia; el número 2 N −1 es equidistante en ambas direcciones, en términos de números de secuencia 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 dos números de secuencia cualesquiera con una distancia de 0x8000 entre ellos.
Además, implementar la aritmética de números de serie utilizando la aritmética en 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 de 16 bits, 32 bits y 64 bits. La implementación de números de serie de 20 bits necesita cambios (asumiendo entradas de 32 bits):
distancia = ( con signo )(( i1 << 12 ) - ( i2 << 12 ))