Serial Number Arithmetic

Serial Number Arithmetic

Many protocols and algorithms require the serialization or enumeration of related entities. For example, a communication protocol must know whether some packet comes "before" or "after" some other packet. The IETF (Internet Engineering Task Force) RFC 1982 attempts to define "Serial Number Arithmetic" for the purposes of manipulating and comparing these sequence numbers.

This task is rather more complex than it might first appear, because most algorithms use fixed size (binary) representations for sequence numbers.It is often important for the algorithm not to "break down" when the numbers become so large that they are incremented one last time and "wrap" around their maximum numeric ranges (go instantly from a large positive number to 0, or a large negative number).Unfortunately, some protocols choose to ignore these issues, and simply use very large integers for their counters, in the hope that the program will be replaced (or they will retire), before the problem occurs (see Y2K.)

Operations on Sequence Numbers

Only addition of a small positive integer to a sequence number, and comparison of two sequence numbers are discussed.Only unsigned binary implementations are discussed, with an arbitrary size in bits noted throughout the RFC as (and below) as "SERIAL_BITS".

Addition

Adding an integer to a sequence number is simple unsigned integer addition, followed by unsigned Modulo operation to bring the result back into range (usually implicit in the unsigned addition, on most architectures.)

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

Addition of a value outside the range

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

is undefined. Basically, adding values beyond this range will cause the resultant sequence number to "wrap", and (often) result in a number that is considered "less than" the original sequence number!

Comparison

A means of comparing two sequence numbers i1 and i2 (the unsigned integer representations of sequence numbers s1 and s2) is presented.

Equality is defined as simple numeric equality.The algorithm presented for comparison is very complex, having to take into account whether the first sequence number is close to the "end" of its range of values, and thus a smaller "wrapped" number may actually be considered "greater" than the first sequence number. Thus s1 is considered less than s2, only if:

(i1 < i2 and i2 - i1 < 2^(SERIAL_BITS - 1)) or (i1 > i2 and i1 - i2 > 2^(SERIAL_BITS - 1))

Likewise, s1 is considered greater than s2, only if:

(i1 < i2 and i2 - i1 > 2^(SERIAL_BITS - 1)) or (i1 > i2 and i1 - i2 < 2^(SERIAL_BITS - 1))

hortfalls

The algorithms presented have several shortcomings.First, there are numbers for which comparison is simply undefined!Since many algorithms are implemented independently by multiple, independent cooperating parties, it is often impossible to prevent all such situations from occurring.

The authors of RFC 1982 simply punt:

While it would be possible to define the test in such a way that the inequality would not have this surprising property, while being defined for all pairs of values, such a definition would be unnecessarily burdensome to implement, and difficult to understand, and would still allow cases where s1 < s2 and (s1 + 1) > (s2 + 1) which is just as non-intuitive. Thus the problem case is left undefined, implementations are free to return either result, or to flag an error, and users must take care not to depend on any particular outcome. Usually this will mean avoiding allowing those particular pairs of numbers to co-exist.

Fortunately, many other programmers are more persistent...

General Solution

Most modern hardware implements signed Two's complement binary arithmetic operations.These operations are fully defined for the entire range of values for any operands they are given -- since any N-bit binary number can contain 2 ^ N distinct values, and since one of them is taken up by the value 0, there are an odd number of spots left for all the non-zero positive and negative numbers.There is simply one more negative number representable, than there are positive.For example, a 16-bit Two's complement value may contain numbers ranging from -32768 to +32767.

So, if we simply re-cast sequence numbers as Two's complement integers, and allow there to be "one more" sequence number "less than", than there are sequence numbers "greater than", we should be able to use simple signed arithmetic comparison, instead of the clunky, logically incomplete formulæ presented above.

Here are some examples (in 16 bits, again), comparing some random sequence numbers, against the value 0.

unsigned binary signed sequence value distance -------- ------ -------- 32767 = 0x7fff = 32767 1 = 0x0001 = 1 0 = 0x0000 = 0 65535 = 0xffff = -1 65534 = 0xfffe = -2 32768 = 0x8000 = -32768

It is easy to see that the signed interpretation of the sequence numbers are in the correct order, so long as we "rotate" the sequence number in question so that it's 0 matches up with the sequence number we are comparing it against. It turns out that this is simply done, using an unsigned subtraction, and simply interpreting the result as a signed number! The result is the signed "distance" between the two sequence numbers! Once again, if i1 and i2 are the unsigned binary representations of the sequence numbers s1 and s2, the distance from s1 to s2 is:

distance = (signed)( i1 - i2 )

If distance is 0, the numbers are equal. If it is < 0, then s1 is "less than" or "before" s2!Simple, clean and efficient.

It is easy to see that despite all the simplicity and elegance of this formula, it is still the same logic as in RFC 1982, but with shortcuts that are provided by automatic wrap-around of integers and Two's complement representation of negative integers. In other words, this formula depends on sequence number type being one of the C native types and on negative integers being represented as Two's complement. Other than that it produces the same results and has the same shortcomings.One example, comparison of 0x8000 and 0 in 16-bit serial number space:

distance1 = (signed)(0x8000 - 0x0) = (signed)0x8000 = -32768 < 0 distance2 = (signed)(0x0 - 0x8000) = (signed)0xffff = -1 < 0

So, we have that both 0x8000 and 0x0 are "less than" each other. This is obviously true for any two serial numbers with distance of 0x8000 between them.

And once again, this formula doesn't work, for example, for 20-bit serial numbers. So it is hard to see why it is being described as "General Solution" rather than "Particular Implementation".

ee also

*Lollipop sequence numbering

External links

*RFC 2182
*RFC 1982
* [http://enbridge.kundert.2y.net/sequence A C++ implementation]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Serial number — from an identity document A serial number is a unique number assigned for identification which varies from its successor or predecessor by a fixed discrete integer value. Common usage has expanded the term to refer to any unique alphanumeric… …   Wikipedia

  • Modular arithmetic — In mathematics, modular arithmetic (sometimes called clock arithmetic) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value the modulus. The Swiss mathematician Leonhard Euler pioneered the modern… …   Wikipedia

  • Number — For other uses, see Numbers (disambiguation). A number is a mathematical object used to count and measure. In mathematics, the definition of number has been extended over the years to include such numbers as zero, negative numbers, rational… …   Wikipedia

  • International Standard Book Number — ISBN redirects here. For usage of ISBNs in Wikipedia, see Wikipedia:ISBN. A 13 digit ISBN, 978 3 16 148410 0, as represented by an EAN 13 bar code. The International Standard Book Number (ISBN) is a unique[1][2 …   Wikipedia

  • Cardinal number — This article describes cardinal numbers in mathematics. For cardinals in linguistics, see Names of numbers in English. In mathematics, cardinal numbers, or cardinals for short, are generalized numbers used to measure the cardinality (size) of… …   Wikipedia

  • Paced Auditory Serial Addition Test — (PASAT) is a neuropsychological test, used to assess capacity and rate of information processing and sustained and divided attention [1]. Originally the test was known as the Paced Auditory Serial Addition Task (PASAT). The subjects are given in… …   Wikipedia

  • 12 (number) — ← 11 13 → 12 ← 10 11 12 13 14 15 16 …   Wikipedia

  • RFC 1982 — Serial Number Arithmetic. R. Elz R. Bush. August 1996. (Updates RFC 1034 , RFC 1035) …   Acronyms

  • RFC 1982 — Serial Number Arithmetic. R. Elz R. Bush. August 1996. (Updates RFC 1034 , RFC 1035) …   Acronyms von A bis Z

  • DNS zone transfer — DNS zone transfer, also sometimes known by its (most common) opcode mnemonic AXFR, is a type of DNS transaction. It is one of the many mechanisms available for administrators to employ for replicating the databases containing the DNS data across… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”