technology from back to front

RFC 1982 limits itself to powers of two unnecessarily

RFC 1982 defines a “Serial Number Arithmetic”, for use when you have a fixed number of bits available for some monotonically increasing sequence identifier, such as the DNS SOA record serial number, or message IDs in some messaging protocol. It defines all its operations with respect to some power of two, (2^SERIAL\_BITS). It struck me just now that there’s no reason why you couldn’t generalise to any number that simply has two as a factor. You’d simply replace any mention of (2^SERIAL\_BITS) by, say, N, and any mention of (2^(SERIAL\_BITS-1)) by (N/2). The definitions for addition and comparison still seem to hold just as well.

One of the reasons I was thinking along these lines is that in Erlang, it’s occasionally useful to model a queue in an ETS table or in a process dictionary. If one didn’t mind setting an upper bound on the length of one’s modelled queue, then by judicious use of RFC 1982-style sequence number wrapping, one might ensure that the space devoted to the sequence numbering required of the model remained bounded. Using a generalised variant of RFC 1982 arithmetic, one becomes free to choose any number as the queue length bound, rather than any power of two.

by
tonyg
on
17/02/07
  1. I’m not sure I understand what RFC1982 is trying to achieve – could you clarify?

  2. RFC 1982 seems to be making explicit the arithmetic of the serial numbers that are used to version DNS zone information, in particular how to determine the order of two of these serial numbers. This “Serial Number Arithmetic” is referred to in the DNS RFCS 1034 and 1035.

    Was the power of two limit perhaps chosen because a serial with an arbitrary maximum would generally be represented in the same number of bits that would be used if the next higher power of two was the maximum? For example if the N mentioned above was 10 then 4 bits would be needed to represent the largest serial number anyway, the same as if N was 16 (i.e. if SERIAL_BITS was 4).

 
 


+ two = 11

2000-14 LShift Ltd, 1st Floor, Hoxton Point, 6 Rufus Street, London, N1 6PE, UK+44 (0)20 7729 7060   Contact us