Muchos protocolos y algoritmos requieren la serialización o enumeración de entidades relacionadas. Por ejemplo, un protocolo de comunicación debe saber si algún paquete viene "antes" o "después" de otro paquete. El IETF ( Grupo de trabajo de ingeniería de Internet ) RFC 1982 intenta definir "aritmética de números de serie" con el fin de manipular y comparar estos números de secuencia .
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 por última vez y se "ajustan" alrededor de sus rangos numéricos máximos (pasa 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 usan 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 aritmética de números de serie a 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]
Operaciones con números de secuencia
Solo se discute la adición de un pequeño entero positivo a un número de secuencia y la comparación de dos números de secuencia. Sólo se discuten las implementaciones binarias sin firmar, con un tamaño arbitrario en bits anotado en todo el RFC (y más abajo) como "SERIAL_BITS".
Adición
Agregar 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 adición sin signo, en la mayoría de las arquitecturas):
s '= (s + n) módulo (2 ^ SERIAL_BITS)
Adición de un valor fuera del rango
[0 .. (2 ^ (SERIAL_BITS - 1) - 1)]
es indefinido. Básicamente, agregar valores más allá de este rango hará que el número de secuencia resultante se "ajuste" y (a menudo) resulte en un número que se considera "menor que" el número de secuencia original.
Comparación
Se presenta un medio para comparar dos números de secuencia i1
y i2
(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 "mayor" que la primera secuencia. número. Por i1
lo tanto, se considera menos que i2
solo si
(i1(i1> i2 y i1 - i2> 2 ^ (SERIAL_BITS - 1))
Asimismo, i1
se considera mayor que i2
solo si
(i12 ^ (SERIAL_BITS - 1)) o (i1> i2 y i1 - i2 <2 ^ (SERIAL_BITS - 1))
Deficiencias
Los algoritmos presentados por el RFC tienen al menos una deficiencia significativa: hay números de secuencia para los que la comparación no está definida. Dado que muchos algoritmos se implementan de forma independiente por múltiples partes cooperantes independientes, a menudo es imposible evitar que ocurran todas estas situaciones.
Los autores de RFC 1982 reconoce 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 se definiera para todos los pares de valores, tal definición sería innecesariamente onerosa de implementar y difícil de entender, y aún así sería permitir casos donde
s1(s2 + 1) que es igual de no intuitivo.
Por lo tanto, el caso del problema se deja sin definir, las implementaciones son libres de devolver cualquier resultado o marcar un error, y los usuarios deben tener cuidado de no depender de ningún resultado en particular. Por lo general, esto significará evitar 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 mapear los números de secuencia sin signo en 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".
Solución general
La 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 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 para cualquier operando que se les proporcione, ya que cualquier número binario de N bits puede contener 2 N valores distintos, y dado que uno de ellos está tomado por el valor 0, hay un número impar. de lugares que quedan para todos los números positivos y negativos distintos de cero. Simplemente hay un número representable más negativo que positivo. Por ejemplo, un valor de complemento a 2 de 16 bits puede contener números que van desde -32768 a +32767.
Por lo tanto, si simplemente modificamos 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 "mayor que", deberíamos poder utilizar 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 firmar con signodistancia de 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 "rotamos" 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 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 i1
y i2
son las representaciones binarias sin signo de los números de secuencia s 1 y s 2 , la distancia entre s 1 y 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" s 2 . Simple, limpio y eficiente, y completamente definido. Sin embargo, no sin sorpresas.
Toda la aritmética de números de secuencia debe ocuparse de "encapsular" los 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 "menos que" 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 usando aritmética de complemento a dos implica números de serie de una longitud de bits que coinciden con los tamaños enteros de la máquina; generalmente 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 ))