7
Network Working Group R. Elz
8
Request for Comments: 1982 University of Melbourne
9
Updates: 1034, 1035 R. Bush
10
Category: Standards Track RGnet, Inc.
14
Serial Number Arithmetic
18
This document specifies an Internet standards track protocol for the
19
Internet community, and requests discussion and suggestions for
20
improvements. Please refer to the current edition of the "Internet
21
Official Protocol Standards" (STD 1) for the standardization state
22
and status of this protocol. Distribution of this memo is unlimited.
26
This memo defines serial number arithmetic, as used in the Domain
27
Name System. The DNS has long relied upon serial number arithmetic,
28
a concept which has never really been defined, certainly not in an
29
IETF document, though which has been widely understood. This memo
30
supplies the missing definition. It is intended to update RFC1034
35
The serial number field of the SOA resource record is defined in
38
SERIAL The unsigned 32 bit version number of the original copy of
39
the zone. Zone transfers preserve this value. This value
40
wraps and should be compared using sequence space
43
RFC1034 uses the same terminology when defining secondary server zone
44
consistency procedures.
46
Unfortunately the term "sequence space arithmetic" is not defined in
47
either RFC1034 or RFC1035, nor do any of their references provide
50
This phrase seems to have been intending to specify arithmetic as
51
used in TCP sequence numbers [RFC793], and defined in [IEN-74].
53
Unfortunately, the arithmetic defined in [IEN-74] is not adequate for
54
the purposes of the DNS, as no general comparison operator is
58
Elz & Bush Standards Track [Page 1]
60
RFC 1982 Serial Number Arithmetic August 1996
65
To avoid further problems with this simple field, this document
66
defines the field and the operations available upon it. This
67
definition is intended merely to clarify the intent of RFC1034 and
68
RFC1035, and is believed to generally agree with current
69
implementations. However, older, superseded, implementations are
70
known to have treated the serial number as a simple unsigned integer,
71
with no attempt to implement any kind of "sequence space arithmetic",
72
however that may have been interpreted, and further, ignoring the
73
requirement that the value wraps. Nothing can be done with these
74
implementations, beyond extermination.
76
2. Serial Number Arithmetic
78
Serial numbers are formed from non-negative integers from a finite
79
subset of the range of all integer values. The lowest integer in
80
every subset used for this purpose is zero, the maximum is always one
81
less than a power of two.
83
When considered as serial numbers however no value has any particular
84
significance, there is no minimum or maximum serial number, every
85
value has a successor and predecessor.
87
To define a serial number to be used in this way, the size of the
88
serial number space must be given. This value, called "SERIAL_BITS",
89
gives the power of two which results in one larger than the largest
90
integer corresponding to a serial number value. This also specifies
91
the number of bits required to hold every possible value of a serial
92
number of the defined type. The operations permitted upon serial
93
numbers are defined in the following section.
95
3. Operations upon the serial number
97
Only two operations are defined upon serial numbers, addition of a
98
positive integer of limited range, and comparison with another serial
103
Serial numbers may be incremented by the addition of a positive
104
integer n, where n is taken from the range of integers
105
[0 .. (2^(SERIAL_BITS - 1) - 1)]. For a sequence number s, the
106
result of such an addition, s', is defined as
108
s' = (s + n) modulo (2 ^ SERIAL_BITS)
114
Elz & Bush Standards Track [Page 2]
116
RFC 1982 Serial Number Arithmetic August 1996
119
where the addition and modulus operations here act upon values that
120
are non-negative values of unbounded size in the usual ways of
123
Addition of a value outside the range
124
[0 .. (2^(SERIAL_BITS - 1) - 1)] is undefined.
128
Any two serial numbers, s1 and s2, may be compared. The definition
129
of the result of this comparison is as follows.
131
For the purposes of this definition, consider two integers, i1 and
132
i2, from the unbounded set of non-negative integers, such that i1 and
133
s1 have the same numeric value, as do i2 and s2. Arithmetic and
134
comparisons applied to i1 and i2 use ordinary unbounded integer
137
Then, s1 is said to be equal to s2 if and only if i1 is equal to i2,
138
in all other cases, s1 is not equal to s2.
140
s1 is said to be less than s2 if, and only if, s1 is not equal to s2,
143
(i1 < i2 and i2 - i1 < 2^(SERIAL_BITS - 1)) or
144
(i1 > i2 and i1 - i2 > 2^(SERIAL_BITS - 1))
146
s1 is said to be greater than s2 if, and only if, s1 is not equal to
149
(i1 < i2 and i2 - i1 > 2^(SERIAL_BITS - 1)) or
150
(i1 > i2 and i1 - i2 < 2^(SERIAL_BITS - 1))
152
Note that there are some pairs of values s1 and s2 for which s1 is
153
not equal to s2, but for which s1 is neither greater than, nor less
154
than, s2. An attempt to use these ordering operators on such pairs
155
of values produces an undefined result.
157
The reason for this is that those pairs of values are such that any
158
simple definition that were to define s1 to be less than s2 where
159
(s1, s2) is such a pair, would also usually cause s2 to be less than
160
s1, when the pair is (s2, s1). This would mean that the particular
161
order selected for a test could cause the result to differ, leading
162
to unpredictable implementations.
164
While it would be possible to define the test in such a way that the
165
inequality would not have this surprising property, while being
166
defined for all pairs of values, such a definition would be
170
Elz & Bush Standards Track [Page 3]
172
RFC 1982 Serial Number Arithmetic August 1996
175
unnecessarily burdensome to implement, and difficult to understand,
176
and would still allow cases where
178
s1 < s2 and (s1 + 1) > (s2 + 1)
180
which is just as non-intuitive.
182
Thus the problem case is left undefined, implementations are free to
183
return either result, or to flag an error, and users must take care
184
not to depend on any particular outcome. Usually this will mean
185
avoiding allowing those particular pairs of numbers to co-exist.
187
The relationships greater than or equal to, and less than or equal
188
to, follow in the natural way from the above definitions.
192
These definitions give rise to some results of note.
196
For any sequence number s and any integer n such that addition of n
197
to s is well defined, (s + n) >= s. Further (s + n) == s only when
198
n == 0, in all other defined cases, (s + n) > s.
202
If s' is the result of adding the non-zero integer n to the sequence
203
number s, and m is another integer from the range defined as able to
204
be added to a sequence number, and s" is the result of adding m to
205
s', then it is undefined whether s" is greater than, or less than s,
206
though it is known that s" is not equal to s.
210
If s" from the previous corollary is further incremented, then there
211
is no longer any known relationship between the result and s.
215
If in corollary 2 the value (n + m) is such that addition of the sum
216
to sequence number s would produce a defined result, then corollary 1
217
applies, and s" is known to be greater than s.
226
Elz & Bush Standards Track [Page 4]
228
RFC 1982 Serial Number Arithmetic August 1996
233
5.1. A trivial example
235
The simplest meaningful serial number space has SERIAL_BITS == 2. In
236
this space, the integers that make up the serial number space are 0,
237
1, 2, and 3. That is, 3 == 2^SERIAL_BITS - 1.
239
In this space, the largest integer that it is meaningful to add to a
240
sequence number is 2^(SERIAL_BITS - 1) - 1, or 1.
242
Then, as defined 0+1 == 1, 1+1 == 2, 2+1 == 3, and 3+1 == 0.
243
Further, 1 > 0, 2 > 1, 3 > 2, and 0 > 3. It is undefined whether
244
2 > 0 or 0 > 2, and whether 1 > 3 or 3 > 1.
246
5.2. A slightly larger example
248
Consider the case where SERIAL_BITS == 8. In this space the integers
249
that make up the serial number space are 0, 1, 2, ... 254, 255.
250
255 == 2^SERIAL_BITS - 1.
252
In this space, the largest integer that it is meaningful to add to a
253
sequence number is 2^(SERIAL_BITS - 1) - 1, or 127.
255
Addition is as expected in this space, for example: 255+1 == 0,
256
100+100 == 200, and 200+100 == 44.
258
Comparison is more interesting, 1 > 0, 44 > 0, 100 > 0, 100 > 44,
259
200 > 100, 255 > 200, 0 > 255, 100 > 255, 0 > 200, and 44 > 200.
261
Note that 100+100 > 100, but that (100+100)+100 < 100. Incrementing
262
a serial number can cause it to become "smaller". Of course,
263
incrementing by a smaller number will allow many more increments to
264
be made before this occurs. However this is always something to be
265
aware of, it can cause surprising errors, or be useful as it is the
266
only defined way to actually cause a serial number to decrease.
268
The pairs of values 0 and 128, 1 and 129, 2 and 130, etc, to 127 and
269
255 are not equal, but in each pair, neither number is defined as
270
being greater than, or less than, the other.
272
It could be defined (arbitrarily) that 128 > 0, 129 > 1,
273
130 > 2, ..., 255 > 127, by changing the comparison operator
274
definitions, as mentioned above. However note that that would cause
275
255 > 127, while (255 + 1) < (127 + 1), as 0 < 128. Such a
276
definition, apart from being arbitrary, would also be more costly to
282
Elz & Bush Standards Track [Page 5]
284
RFC 1982 Serial Number Arithmetic August 1996
289
As this defined arithmetic may be useful for purposes other than for
290
the DNS serial number, it may be referenced as Serial Number
291
Arithmetic from RFC1982. Any such reference shall be taken as
292
implying that the rules of sections 2 to 5 of this document apply to
295
7. The DNS SOA serial number
297
The serial number in the DNS SOA Resource Record is a Serial Number
298
as defined above, with SERIAL_BITS being 32. That is, the serial
299
number is a non negative integer with values taken from the range
300
[0 .. 4294967295]. That is, a 32 bit unsigned integer.
302
The maximum defined increment is 2147483647 (2^31 - 1).
304
Care should be taken that the serial number not be incremented, in
305
one or more steps, by more than this maximum within the period given
306
by the value of SOA.expire. Doing so may leave some secondary
307
servers with out of date copies of the zone, but with a serial number
308
"greater" than that of the primary server. Of course, special
309
circumstances may require this rule be set aside, for example, when
310
the serial number needs to be set lower for some reason. If this
311
must be done, then take special care to verify that ALL servers have
312
correctly succeeded in following the primary server's serial number
313
changes, at each step.
315
Note that each, and every, increment to the serial number must be
316
treated as the start of a new sequence of increments for this
317
purpose, as well as being the continuation of all previous sequences
318
started within the period specified by SOA.expire.
320
Caution should also be exercised before causing the serial number to
321
be set to the value zero. While this value is not in any way special
322
in serial number arithmetic, or to the DNS SOA serial number, many
323
DNS implementations have incorrectly treated zero as a special case,
324
with special properties, and unusual behaviour may be expected if
325
zero is used as a DNS SOA serial number.
338
Elz & Bush Standards Track [Page 6]
340
RFC 1982 Serial Number Arithmetic August 1996
345
RFC1034 and RFC1035 are to be treated as if the references to
346
"sequence space arithmetic" therein are replaced by references to
347
serial number arithmetic, as defined in this document.
349
9. Security Considerations
351
This document does not consider security.
353
It is not believed that anything in this document adds to any
354
security issues that may exist with the DNS, nor does it do anything
359
[RFC1034] Domain Names - Concepts and Facilities,
360
P. Mockapetris, STD 13, ISI, November 1987.
362
[RFC1035] Domain Names - Implementation and Specification
363
P. Mockapetris, STD 13, ISI, November 1987
365
[RFC793] Transmission Control protocol
366
Information Sciences Institute, STD 7, USC, September 1981
368
[IEN-74] Sequence Number Arithmetic
369
William W. Plummer, BB&N Inc, September 1978
373
Thanks to Rob Austein for suggesting clarification of the undefined
374
comparison operators, and to Michael Patton for attempting to locate
375
another reference for this procedure. Thanks also to members of the
376
IETF DNSIND working group of 1995-6, in particular, Paul Mockapetris.
380
Robert Elz Randy Bush
381
Computer Science RGnet, Inc.
382
University of Melbourne 10361 NE Sasquatch Lane
383
Parkville, Vic, 3052 Bainbridge Island, Washington, 98110
384
Australia. United States.
386
EMail: kre@munnari.OZ.AU EMail: randy@psg.com
394
Elz & Bush Standards Track [Page 7]
added
removed
doc/rfc/rfc1982.txt
