Número de serie aritmética

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 que viene "antes" o "después" de algunos otros paquetes. El IETF (Internet Engineering Task Force) RFC 1982 intenta definir "Número de serie aritmética" a los efectos de manipular y comparar estos números de secuencia.

Esta tarea es bastante más compleja que el primero podría parecer, porque la mayoría algoritmos usan tamaño fijo ()binario) representaciones de números de secuencia. A menudo es importante para el algoritmo no para "romper" cuando los números se convierten tan grandes que están incrementado una última vez y "envolver" alrededor de sus rangos numéricos máximas (ir al instante de un gran número positivo a 0, o un gran número negativo). Desafortunadamente, algunos protocolos opta por ignorar estos temas, y simplemente uso enteros muy grandes para sus contadores, con la esperanza de que el programa será reemplazado (o se retirarán), antes de que el problema ocurre (véase Y2K.)

Operaciones con números de secuencia

Sólo la adición de un pequeño positivo número entero a un número de secuencia y la comparación de la secuencia de dos números se discuten. Sólo las implementaciones binarias sin signo se discuten, con un tamaño arbitrario en bits observado a lo largo de la RFC como (y debajo) como "SERIAL_BITS".

Adición

Agregar un entero a un número de secuencia es adición simple entero sin signo, seguido sin firmar Modulo de operación para traer de vuelta el resultado en gama (generalmente implícito en la adición sin firmar, en la mayoría de las arquitecturas).

s' = (s + n) modulo (2 ^ SERIAL_BITS)

Adición de un valor fuera del intervalo

[0 .. (2 ^(SERIAL_BITS-1) - 1)]

No está definido. Básicamente, agregando valores fuera de este rango hará que el número de secuencia resultante de "wrap" y (a menudo) resultado en un número que se considera "menos de" número de la secuencia original.

Comparación

Un medio de comparar dos secuencia números i1 y i2 (las representaciones entero sin signo de secuencia números s1 y s2) se presenta.

La igualdad se define como simple igualdad numérica. El algoritmo presentado para la comparación es muy complejo, tener que tomar en cuenta si el primer número de secuencia está cerca del "final" de su rango de valores, y por lo tanto un menor número de "envuelta" en realidad puede ser considerado "mayor" que el primer número de secuencia. Así s1 es considerado menos de s2, sólo si:

(i1 < i2 y i2 - i1 < 2 ^(SERIAL_BITS-1)) o (i1 > i2 y i1 - i2 > 2 ^(SERIAL_BITS-1))

Asimismo, se considera superior a s2, s1 sólo si:

(i1 < i2 y i2 - i1 > 2 ^(SERIAL_BITS-1)) o (i1 > i2 y i1 - i2 < 2 ^(SERIAL_BITS-1))

Insuficiencias

Los algoritmos presentados por el RFC tienen al menos un defecto importante: hay un número de secuencia para que la comparación es indefinido. Puesto que muchos algoritmos se aplican independientemente por múltiples partes cooperantes independientes, a menudo es imposible evitar todas estas situaciones ocurran.

Los autores de RFC 1982 simplemente Batea:

Mientras que sería posible definir la prueba de tal manera que la desigualdad no tendría este sorprendente propiedad, mientras que se define para todos los pares de valores, tal definición sería innecesariamente gravoso a implementar y difícil de entender y aún así les permitiría casos donde s1 < s2 y (s1 + 1) > (s2 + 1) que es simplemente como no intuitivo.
  
  Por lo tanto el caso del problema es izquierda indefinida, las implementaciones son libres para devolver cualquier resultado, o a un error de la bandera y los usuarios deben prestar atención para no depender de ningún resultado concreto.  Generalmente esto significa evitar permitir a esos pares particulares de números para coexistir.

Por lo tanto, es a menudo difícil o imposible de evitar todas las comparaciones "indefinidas" de números de secuencia. Sin embargo, existe una solución relativamente sencilla. Mediante la asignación de los números de secuencia sin firmar a firmado Complemento a dos operaciones aritméticas, cada comparación de cualquier número de secuencia se define, y la propia operación de comparación se simplifica considerablemente. Todas las comparaciones especificadas por el RFC conservan sus valores originales de verdad; son afectadas sólo las comparaciones anteriormente "indefinidas".

Solución general

El RFC 1982 algoritmo especifica que, para los números de secuencia de N bits, existen 2^(N−1)−1 valores considerados "mayor que" y 2^(N−1)−1 considerados "menores". Comparación con el valor restante (exactamente 2^N−1 distantes) es considerada como "indefinido".

Más modernos implementos hardware firmados Complemento a dos operaciones aritméticas binarias. Estas operaciones están completamente definidas para toda la gama de valores para cualquier operandos son dadas — desde cualquier N-bit número binario puede contener 2^N valores distintos, y puesto que uno de ellos es tomado por el valor 0, hay un número impar de izquierda puntos para todos los cero positivos y negativos los números. Simplemente hay una negativa más número que hay positivos. Por ejemplo, complemento valor de un 16-bit 2 puede contener números que van desde −32768 a +32767.

Entonces, si nosotros simplemente volver a echar números de secuencia como de 2 complementan enteros y permitir que haya un número de secuencia más considerados "menores" que allí son números de secuencia considerados "mayor que", deberíamos poder utilizar simples comparaciones aritméticas firmadas en lugar de la formulæ lógicamente incompletas propuesto por el RFC.

Estos son algunos ejemplos (en 16 bits, otra vez), una secuencia al azar que compararan números, contra el número de secuencia con el valor 0.

binario sin signo firmado distancia del valor de secuencia---------32767 == 0x7fff == 32767 1 == 0x0001 == 1 0 == 0 x 0000 == 0 65535 0xffff == == −1 65534 0xfffe == == −2 32768 == 0x8000 == −32768

Es fácil ver que la interpretación firmada de los números de secuencia en el orden correcto, mientras el número de secuencia en cuestión "rotar" para que sus partidos 0 para arriba con el número de secuencia estamos comparando contra. Resulta que esto simplemente se hace, mediante una sustracción sin firmar, y simplemente interpretar el resultado como un signo dos complementan de número. El resultado es la "distancia" firmada entre los números de dos secuencia. Una vez más, si i1 y i2 son las representaciones binarias sin firmar de la secuencia números s1 y s2, la distancia entre s1 y s2 es:

distancia = (firmado) (i1 - i2)

Si la distancia es 0, los números son iguales. Si es < 0, entonces s1 es "menos" o "antes" de s2. Sencillo, limpio y eficiente y totalmente definido. Sin embargo, no sin sorpresas.

Todos los números de secuencia aritmético deben lidiar con "envoltura" de números de secuencia; el número 2^N−1 es equidistante en ambas direcciones, en RFC 1928 términos de número de secuencia. En nuestras cuentas, ambos son considerados para ser "menos" unos a otros:

Distance1 = (firmado)(0x8000-0x0) = 0x8000 =-32768 (firmado) < 0 distancia2 = (firmado)(0x0-0x8000) = 0x8000 =-32768 (firmado) < 0

Esto es obviamente cierto para cualquier número de dos secuencia con distancia de 0x8000 entre ellos.

Además, aplicación de número de serie aritmética utilizando de dos aritmética de complemento implica números de serie de una longitud de bit emparejar tamaños entero de la máquina; generalmente 16 bits, 32 bits y 64 bits. Aplicación de números de serie de 20 bits necesita cambios (suponiendo que 32 bits ints):

distancia = (firmado) ((i1 << 12)-(i2 << 12))

Ver los casos de prueba de unidad en la aplicación de C++ de ejemplo abajo para ver más ejemplos.

Véase también

• Piruleta secuencia de numeración
• Aritmética modular

Enlaces externos

• RFC 2182
• RFC 1982
• Una aplicación de C++

Otras Páginas

• Trastorno de desregulacion disruptiva del estado de animo
• Grupo Armstrong (redireccion de Armstrong Cable servicios)
• Lucy hace un anuncio de TV
• Malato de magnesio
• Entropico valor en riesgo
• Hollingsworth v. Perry
• El poder de la verdad