1 Network Working Group R. Elz
2 Request for Comments: 1982 University of Melbourne
3 Updates: 1034, 1035 R. Bush
4 Category: Standards Track RGnet, Inc.
5 August 1996
6
7
8 Serial Number Arithmetic
9
10 Status of this Memo
11
12 This document specifies an Internet standards track protocol for the
13 Internet community, and requests discussion and suggestions for
14 improvements. Please refer to the current edition of the "Internet
15 Official Protocol Standards" (STD 1) for the standardization state
16 and status of this protocol. Distribution of this memo is unlimited.
17
18 Abstract
19
20 This memo defines serial number arithmetic, as used in the Domain
21 Name System. The DNS has long relied upon serial number arithmetic,
22 a concept which has never really been defined, certainly not in an
23 IETF document, though which has been widely understood. This memo
24 supplies the missing definition. It is intended to update RFC1034
25 and RFC1035.
26
27 1. Introduction
28
29 The serial number field of the SOA resource record is defined in
30 RFC1035 as
31
32 SERIAL The unsigned 32 bit version number of the original copy of
33 the zone. Zone transfers preserve this value. This value
34 wraps and should be compared using sequence space
35 arithmetic.
36
37 RFC1034 uses the same terminology when defining secondary server zone
38 consistency procedures.
39
40 Unfortunately the term "sequence space arithmetic" is not defined in
41 either RFC1034 or RFC1035, nor do any of their references provide
42 further information.
43
44 This phrase seems to have been intending to specify arithmetic as
45 used in TCP sequence numbers [RFC793], and defined in [IEN-74].
46
47 Unfortunately, the arithmetic defined in [IEN-74] is not adequate for
48 the purposes of the DNS, as no general comparison operator is
49
50
51
52 Elz & Bush Standards Track [Page 1]
53 RFC 1982 Serial Number Arithmetic August 1996
54
55
56 defined.
57
58 To avoid further problems with this simple field, this document
59 defines the field and the operations available upon it. This
60 definition is intended merely to clarify the intent of RFC1034 and
61 RFC1035, and is believed to generally agree with current
62 implementations. However, older, superseded, implementations are
63 known to have treated the serial number as a simple unsigned integer,
64 with no attempt to implement any kind of "sequence space arithmetic",
65 however that may have been interpreted, and further, ignoring the
66 requirement that the value wraps. Nothing can be done with these
67 implementations, beyond extermination.
68
69 2. Serial Number Arithmetic
70
71 Serial numbers are formed from non-negative integers from a finite
72 subset of the range of all integer values. The lowest integer in
73 every subset used for this purpose is zero, the maximum is always one
74 less than a power of two.
75
76 When considered as serial numbers however no value has any particular
77 significance, there is no minimum or maximum serial number, every
78 value has a successor and predecessor.
79
80 To define a serial number to be used in this way, the size of the
81 serial number space must be given. This value, called "SERIAL_BITS",
82 gives the power of two which results in one larger than the largest
83 integer corresponding to a serial number value. This also specifies
84 the number of bits required to hold every possible value of a serial
85 number of the defined type. The operations permitted upon serial
86 numbers are defined in the following section.
87
88 3. Operations upon the serial number
89
90 Only two operations are defined upon serial numbers, addition of a
91 positive integer of limited range, and comparison with another serial
92 number.
93
94 3.1. Addition
95
96 Serial numbers may be incremented by the addition of a positive
97 integer n, where n is taken from the range of integers
98 [0 .. (2^(SERIAL_BITS - 1) - 1)]. For a sequence number s, the
99 result of such an addition, s', is defined as
100
101 s' = (s + n) modulo (2 ^ SERIAL_BITS)
102
103
104
105
106
107 Elz & Bush Standards Track [Page 2]
108 RFC 1982 Serial Number Arithmetic August 1996
109
110
111 where the addition and modulus operations here act upon values that
112 are non-negative values of unbounded size in the usual ways of
113 integer arithmetic.
114
115 Addition of a value outside the range
116 [0 .. (2^(SERIAL_BITS - 1) - 1)] is undefined.
117
118 3.2. Comparison
119
120 Any two serial numbers, s1 and s2, may be compared. The definition
121 of the result of this comparison is as follows.
122
123 For the purposes of this definition, consider two integers, i1 and
124 i2, from the unbounded set of non-negative integers, such that i1 and
125 s1 have the same numeric value, as do i2 and s2. Arithmetic and
126 comparisons applied to i1 and i2 use ordinary unbounded integer
127 arithmetic.
128
129 Then, s1 is said to be equal to s2 if and only if i1 is equal to i2,
130 in all other cases, s1 is not equal to s2.
131
132 s1 is said to be less than s2 if, and only if, s1 is not equal to s2,
133 and
134
135 (i1 < i2 and i2 - i1 < 2^(SERIAL_BITS - 1)) or
136 (i1 > i2 and i1 - i2 > 2^(SERIAL_BITS - 1))
137
138 s1 is said to be greater than s2 if, and only if, s1 is not equal to
139 s2, and
140
141 (i1 < i2 and i2 - i1 > 2^(SERIAL_BITS - 1)) or
142 (i1 > i2 and i1 - i2 < 2^(SERIAL_BITS - 1))
143
144 Note that there are some pairs of values s1 and s2 for which s1 is
145 not equal to s2, but for which s1 is neither greater than, nor less
146 than, s2. An attempt to use these ordering operators on such pairs
147 of values produces an undefined result.
148
149 The reason for this is that those pairs of values are such that any
150 simple definition that were to define s1 to be less than s2 where
151 (s1, s2) is such a pair, would also usually cause s2 to be less than
152 s1, when the pair is (s2, s1). This would mean that the particular
153 order selected for a test could cause the result to differ, leading
154 to unpredictable implementations.
155
156 While it would be possible to define the test in such a way that the
157 inequality would not have this surprising property, while being
158 defined for all pairs of values, such a definition would be
159
160
161
162 Elz & Bush Standards Track [Page 3]
163 RFC 1982 Serial Number Arithmetic August 1996
164
165
166 unnecessarily burdensome to implement, and difficult to understand,
167 and would still allow cases where
168
169 s1 < s2 and (s1 + 1) > (s2 + 1)
170
171 which is just as non-intuitive.
172
173 Thus the problem case is left undefined, implementations are free to
174 return either result, or to flag an error, and users must take care
175 not to depend on any particular outcome. Usually this will mean
176 avoiding allowing those particular pairs of numbers to co-exist.
177
178 The relationships greater than or equal to, and less than or equal
179 to, follow in the natural way from the above definitions.
180
181 4. Corollaries
182
183 These definitions give rise to some results of note.
184
185 4.1. Corollary 1
186
187 For any sequence number s and any integer n such that addition of n
188 to s is well defined, (s + n) >= s. Further (s + n) == s only when
189 n == 0, in all other defined cases, (s + n) > s.
190
191 4.2. Corollary 2
192
193 If s' is the result of adding the non-zero integer n to the sequence
194 number s, and m is another integer from the range defined as able to
195 be added to a sequence number, and s" is the result of adding m to
196 s', then it is undefined whether s" is greater than, or less than s,
197 though it is known that s" is not equal to s.
198
199 4.3. Corollary 3
200
201 If s" from the previous corollary is further incremented, then there
202 is no longer any known relationship between the result and s.
203
204 4.4. Corollary 4
205
206 If in corollary 2 the value (n + m) is such that addition of the sum
207 to sequence number s would produce a defined result, then corollary 1
208 applies, and s" is known to be greater than s.
209
210
211
212
213
214
215
216
217 Elz & Bush Standards Track [Page 4]
218 RFC 1982 Serial Number Arithmetic August 1996
219
220
221 5. Examples
222
223 5.1. A trivial example
224
225 The simplest meaningful serial number space has SERIAL_BITS == 2. In
226 this space, the integers that make up the serial number space are 0,
227 1, 2, and 3. That is, 3 == 2^SERIAL_BITS - 1.
228
229 In this space, the largest integer that it is meaningful to add to a
230 sequence number is 2^(SERIAL_BITS - 1) - 1, or 1.
231
232 Then, as defined 0+1 == 1, 1+1 == 2, 2+1 == 3, and 3+1 == 0.
233 Further, 1 > 0, 2 > 1, 3 > 2, and 0 > 3. It is undefined whether
234 2 > 0 or 0 > 2, and whether 1 > 3 or 3 > 1.
235
236 5.2. A slightly larger example
237
238 Consider the case where SERIAL_BITS == 8. In this space the integers
239 that make up the serial number space are 0, 1, 2, ... 254, 255.
240 255 == 2^SERIAL_BITS - 1.
241
242 In this space, the largest integer that it is meaningful to add to a
243 sequence number is 2^(SERIAL_BITS - 1) - 1, or 127.
244
245 Addition is as expected in this space, for example: 255+1 == 0,
246 100+100 == 200, and 200+100 == 44.
247
248 Comparison is more interesting, 1 > 0, 44 > 0, 100 > 0, 100 > 44,
249 200 > 100, 255 > 200, 0 > 255, 100 > 255, 0 > 200, and 44 > 200.
250
251 Note that 100+100 > 100, but that (100+100)+100 < 100. Incrementing
252 a serial number can cause it to become "smaller". Of course,
253 incrementing by a smaller number will allow many more increments to
254 be made before this occurs. However this is always something to be
255 aware of, it can cause surprising errors, or be useful as it is the
256 only defined way to actually cause a serial number to decrease.
257
258 The pairs of values 0 and 128, 1 and 129, 2 and 130, etc, to 127 and
259 255 are not equal, but in each pair, neither number is defined as
260 being greater than, or less than, the other.
261
262 It could be defined (arbitrarily) that 128 > 0, 129 > 1,
263 130 > 2, ..., 255 > 127, by changing the comparison operator
264 definitions, as mentioned above. However note that that would cause
265 255 > 127, while (255 + 1) < (127 + 1), as 0 < 128. Such a
266 definition, apart from being arbitrary, would also be more costly to
267 implement.
268
269
270
271
272 Elz & Bush Standards Track [Page 5]
273 RFC 1982 Serial Number Arithmetic August 1996
274
275
276 6. Citation
277
278 As this defined arithmetic may be useful for purposes other than for
279 the DNS serial number, it may be referenced as Serial Number
280 Arithmetic from RFC1982. Any such reference shall be taken as
281 implying that the rules of sections 2 to 5 of this document apply to
282 the stated values.
283
284 7. The DNS SOA serial number
285
286 The serial number in the DNS SOA Resource Record is a Serial Number
287 as defined above, with SERIAL_BITS being 32. That is, the serial
288 number is a non negative integer with values taken from the range
289 [0 .. 4294967295]. That is, a 32 bit unsigned integer.
290
291 The maximum defined increment is 2147483647 (2^31 - 1).
292
293 Care should be taken that the serial number not be incremented, in
294 one or more steps, by more than this maximum within the period given
295 by the value of SOA.expire. Doing so may leave some secondary
296 servers with out of date copies of the zone, but with a serial number
297 "greater" than that of the primary server. Of course, special
298 circumstances may require this rule be set aside, for example, when
299 the serial number needs to be set lower for some reason. If this
300 must be done, then take special care to verify that ALL servers have
301 correctly succeeded in following the primary server's serial number
302 changes, at each step.
303
304 Note that each, and every, increment to the serial number must be
305 treated as the start of a new sequence of increments for this
306 purpose, as well as being the continuation of all previous sequences
307 started within the period specified by SOA.expire.
308
309 Caution should also be exercised before causing the serial number to
310 be set to the value zero. While this value is not in any way special
311 in serial number arithmetic, or to the DNS SOA serial number, many
312 DNS implementations have incorrectly treated zero as a special case,
313 with special properties, and unusual behaviour may be expected if
314 zero is used as a DNS SOA serial number.
315
316
317
318
319
320
321
322
323
324
325
326
327 Elz & Bush Standards Track [Page 6]
328 RFC 1982 Serial Number Arithmetic August 1996
329
330
331 8. Document Updates
332
333 RFC1034 and RFC1035 are to be treated as if the references to
334 "sequence space arithmetic" therein are replaced by references to
335 serial number arithmetic, as defined in this document.
336
337 9. Security Considerations
338
339 This document does not consider security.
340
341 It is not believed that anything in this document adds to any
342 security issues that may exist with the DNS, nor does it do anything
343 to lessen them.
344
345 References
346
347 [RFC1034] Domain Names - Concepts and Facilities,
348 P. Mockapetris, STD 13, ISI, November 1987.
349
350 [RFC1035] Domain Names - Implementation and Specification
351 P. Mockapetris, STD 13, ISI, November 1987
352
353 [RFC793] Transmission Control protocol
354 Information Sciences Institute, STD 7, USC, September 1981
355
356 [IEN-74] Sequence Number Arithmetic
357 William W. Plummer, BB&N Inc, September 1978
358
359 Acknowledgements
360
361 Thanks to Rob Austein for suggesting clarification of the undefined
362 comparison operators, and to Michael Patton for attempting to locate
363 another reference for this procedure. Thanks also to members of the
364 IETF DNSIND working group of 1995-6, in particular, Paul Mockapetris.
365
366 Authors' Addresses
367
368 Robert Elz Randy Bush
369 Computer Science RGnet, Inc.
370 University of Melbourne 10361 NE Sasquatch Lane
371 Parkville, Vic, 3052 Bainbridge Island, Washington, 98110
372 Australia. United States.
373
374 EMail: kre@munnari.OZ.AU EMail: randy@psg.com
375
376
377
378
379
380
381
382 Elz & Bush Standards Track [Page 7]
383
The IETF is responsible for the creation and maintenance of the DNS RFCs. The ICANN DNS RFC annotation project provides a forum for collecting community annotations on these RFCs as an aid to understanding for implementers and any interested parties. The annotations displayed here are not the result of the IETF consensus process.
This RFC is included in the DNS RFCs annotation project whose home page is here.
This RFC is implemented in BIND 9.18 (all versions).