RFC1982 序列号算法

组织：中国互动出版网（http://www.china-pub.com/）
RFC文档中文翻译计划（http://www.china-pub.com/compters/emook/aboutemook.htm）
E-mail：ouyang@china-pub.com
译者：李密（smartsnake    smartsnake@sina.com）
译文发布时间：2002-1-30
版权：本中文翻译文档版权归中国互动出版网所有。可以用于非商业用途自由转载，但必须保留本文档的翻译及版权信息。

序列号算法
（RFC1982――Serial Number Arithmetic）

本备忘录状态
本文档描述了一个用于Internet社团的Internet标准跟踪协议，希望得到有关进一步改进的讨论及建议。有关本协议的标准状态及状态，请参照“Internet正式协议标准”（STD1）  的当前版本。本备忘录的发布不受任何限制。

摘要
   本备忘录定义了用于DNS的序列号算法。域名系统长期依赖于序列号算法，尽管序列号算法已经得到了广泛地理解，但它是一个从未被真正定义过的概念，当然在IETF的文档中也一样。本备忘录提供这份被遗忘的定义，它将用于更新RFC1034和RFC1035两份文档。

1．介绍
   在RFC1035中定义SOA资源档案的序列号领域如下：
   序列号   在存储区中原份拷贝的32位无符号数码。传送拷贝时保留这个数据。这个数据被封装并通过空间序列算法来进行比较。
   当对副服务器存储区连接程序进行定义时，RFC1034使用相同的术语。
   但是“空间序列算法”这个术语不仅没有在RFC1034或RFC1035中进行定义，也没有在它们的参考文献中提供更多的信息。
   这个术语似乎一直试图在TCP序列号[RFC793]中指定算法并在[IEN-74]中进行定义。
   不幸的是，在[IEN-74]中定义的这个算法并不适合DNS的需要，因为它没有定义通用的比较运算符。
   为了避免在这个单一领域中出现更多的问题，这份文件将对这个领域及相关可能的操作进行定义。这份定义仅仅是试图澄清RFC1034和RFC1035中的有关意图而且将主要遵循当前已经生效的声明。然而，某些旧的、淘汰的声明将序列号看成是一个简单的无符号整数，并不试图实现任何形式的“空间序列算法”。虽然它们已经被解释过，但却忽略了数据封装的要求。只有放弃这些声明，否则用它们什么都干不成。

2．序列号算法
   序列号是由非负整数组成的，它是所有整数列的一个有限子集。用于这个目的的每个子集中最小的整数是零，最大的总是比2的乘方小1。
   当一个数被看成是一个序列号，那么无论它的值是多少都不具备任何特殊的含义，没有最小的或者是最大的序列号，每个数值都有一个前继和一个后继。
   用这种方式来定义一个序列号，必须给定序列号的空间大小。这个数值，称之为“比特位”，是2的乘方，比相应序列号的最大值大1。同样，指定的位数必须在已经定义好的序列号的可能数值范围之中。序列号的操作方法如下章所示。

3．序列号的操作
   对序列号仅定义了两种操作，一个是有限正整数数列的加法，另一个是同其他序列号进行对比。

3.1 加法
   序列号可以通过加上一个正整数n来增大数值，其中n属于整数列[0 .. (2^(比特位 - 1) - 1)]。设原序列号为s，增加后的序列号为s', s'的计算公式如下：
         s'=(s + n) 模 (2 ^ 比特位)
   这儿增加数值的加法和取模操作都是利用整数运算的一般法则来求得的一个非负极限值。
   在[0 .. (2^(比特位 - 1) - 1)]之外的数的加法没有定义。

3.2 比较
   任何两个序列号，s1和s2，都能进行比较。比较的结果定义如下：
   为了建立这个定义，先比较两个整数，i1和i2，这两个数都是非负的极限值，i1是s1的极限值，i2是s2的极限值。求得i1和i2的运算和比较符合普通的极限运算法则。
   如果i1等于i2，那么就认为s1和s2相等。如果是其他情况，那么s1和s2不相等。
   如果有(i1 < i2 and i2 - i1 < 2^(比特位 - 1)) 或 (i1 > i2 and i1 - i2 > 2^(比特位 - 1))成立，那么s1小于s2。
   如果有(i1 < i2 and i2 - i1 > 2^(比特位 - 1))或(i1 > i2 and i1 - i2 < 2^(比特位 - 1))成立，那么s1大于s2。
   值得注意的是存在某些数组使得s1和s2不相等，但是同时s1既不大于也不小于s2。试图用这种数组进行的操作将得到不确定的结果。
   造成这样的原因是这些数组是仅作了简单的定义，如（s1,s2）定义为s1比s2小，这样当数组为（s2,s1）时就是s2比s1小。这将意味着对某个测试的不同选择顺序将使得计算结果发生变化，最终导致不可预测的执行结果。
   当不使用这种方式定义测试时，不等式将不会出现这个奇怪的性质；但若被定义为适合所有的数值时，那么这种定义将导致没必要的繁琐执行结果，而且难于理解，甚至会导致当s1 < s2却有 (s1 + 1) > (s2 + 1)这样明显不符合逻辑的结果出现。
   因此，这个问题被留下未作定义，执行结果将返回任意的可能结果，或者是一个实际值，或者标志一个错误，所以用户必须注意不要依赖于任何特殊的返回值。通常这将意味着用户要避免允许让那些特殊的数组导致退出程序。
   两个序列号的关系是大于等于还是小于等于，服从以上所作的普通定义。

4.推论
   这些定义得到以下推论。

4.1推论1
   对于任意序列号s和任意整数n，n加上s的结果定义为 (s + n) >= s，当且仅当n=0时，才有(s + n) = s，而对于其他数值均有：(s + n) > s 。

4.2推论2
   设序列号s加上一个不为零的整数n的结果为s'，m为另一个整数且能够和一个序列号相加，s''是m和s'相加的结果，那么尽管可以肯定s''和s不相等，但并不明确s''究竟是大于s还是小于s 

4.3推论3
   如果s''是从先前的结果增加而来的，那么将不再明确s和s''之间的关系。

4.4推论4
   如果在推论2中，(n + m)确定是序列号s的增加值，那么将产生一个有定义的结果，由推论1可知，s''是大于s的。

5.例子

5.1一个简单的例子
   最简单的序列号，其比特位等于2。在这种情况下，符合这个条件的整数有0，1，2，3。那是因为3 = 2^比特位 - 1 。
   推广这个结果，那么能和一个序列号相加的最大的整数应该为2^(比特位 - 1) - 1 ，即1 。
   因此，若定义0+1 = 1, 1+1 = 2, 2+1 = 3, 并且 3+1 = 0，那么我们得到1 > 0, 2 > 1, 3 > 2, 且 0 > 3 。但究竟是2 > 0 还是 0 > 2 或者 1 > 3 还是 3 > 1 ，这个没有作出定义。

5.2一个稍微复杂的例子
   假设在这个例子中，比特位为8。那么符合这个序列号比特位条件的整数是0，1，2，... 254, 255 。其中255=2^比特位 - 1 。
   在这种情况下，能和一个序列号相加的最大的整数为2^(比特位 - 1) - 1 ，即127 。
   这时，加法被期望作如下定义，例：255+1 = 0, 100+100 = 200, 200+100 = 44 。
   比较大小将变得更为有趣，如：1 > 0, 44 > 0, 100 > 0, 100 > 44, 200 > 100, 255 > 200, 0 > 255, 100 > 255, 0 > 200, 44 > 200 。
   注意到如下情况：100+100 > 100, 但是 (100+100)+100 < 100 。对一个序列号进行加法将导致它变得“更小”。当然，如果和一个足够小的数值相加将使得序列号变大而不是变小。我们要避免上述情况发生，因为这将导致某些奇怪的错误，或者将它定义为代表一个序列号的减小也可以使得这种情况变得有用。
   从0 和128, 1 和 129, 2 和 130, 直到 127 和 255 ，这些数组都不相等，但在每一对数中，既没有定义哪个比哪个大，或哪个比哪个小。
   当然，对于以上的问题，我们能够通过改变比较运算符来定义（非常武断地）128 > 0, 129 > 1,130 > 2, ..., 255 > 127 ，然而值得注意的是会导致如下问题：由于0 < 128 ，所以有(255 + 1) < (127 + 1) ，但是实际上255 > 127 。这样的定义，即使不武断，也将在处理中付出昂贵的代价。

6.引用
   这个已定义的算法除了用于DNS序列号，还能够用于其他领域，所有这些都将参考于“序列号算法”（RFC1982）。任何参考都意味着本文档的第2章到第5章的规则将应用于一定数值的计算。

7.DNS SOA序列号
   用于DNS SOA资源档案的序列号即上述所定义的具有32个比特位的序列号。这意味着，这个序列号是一个非负整数，其数值从0 一直到 4294967295 。这也就是一个32位无符号整数的范围。
   最大的增加值是2147483647 = (2^31 - 1) 。
   值得注意的是，在SOA.expire的数值内，不能一步或多步增加序列号数值，使之超过上述的最大值。否则，将可能导致一些副服务器出现存储区数据越限，使得序列号比主服务器的序列号还要“大”。当然，特殊的环境下可能需要放弃这个规则，例如，由于某种原因需要降低序列号数值的时候。如果这种情况出现了，请密切关注所有的服务器在主服务器的序列号变化的每一步下是否工作正常。
   请注意，对于序列号的每一个增量都必须看作是为了这个目的所得到的一个新序列的开始。同样，这也是SOA.expire所指定的期限中所有先前序列继续的开端。
   同样值得注意的是将序列号清零的情况。因为这个数值在序列号算法中没有任何特殊作用，而且在DNS SOA序列号中，DNS执行管理器会错误地把零当作一个特殊的情况，赋予特殊的性质。如果零用作一个DNS SOA序列号，那么将有可能导致一些不平常的处理结果。

8.文档更新
   RFC1034和RFC1035被看作是“序列空间算法”的参考，它将被这个文档中所定义的序列号算法所取代。

9.安全考虑
   这份文档没有考虑安全因素。
   在这份文档中没有加入了任何安全条款，即使它可能存在于DNS之中，与此同时，也没有加入任何降低系统安全的条款。

参考文献
   [RFC1034]   Domain Names - Concepts and Facilities,
               P. Mockapetris, STD 13, ISI, November 1987.
   [RFC1035]   Domain Names - Implementation and Specification
               P. Mockapetris, STD 13, ISI, November 1987
   [RFC793]    Transmission Control protocol
               Information Sciences Institute, STD 7, USC, September 1981
   [IEN-74]    Sequence Number Arithmetic
               William W. Plummer, BB&N Inc, September 1978

致谢
   感谢Rob Austein的建议，它澄清了一些未定义的比较算符，感谢Michael Patton为了这份文档查找了其他的参考书。同样还要感谢IETF DNSIND 1995-6 工作组的成员们，特别是Paul Mockapetris 。

作者的地址
   Robert Elz   
Computer Science University of Melbourne Parkville, Vic, 3052  Australia.    
EMail: kre@munnari.OZ.AU

   Randy Bush
        RGnet, Inc. 10361 NE Sasquatch Lane Bainbridge Island, Washington, 98110 United States.
EMail: randy@psg.com



RFC1982――Serial Number Arithmetic                               序 列 号 算 法




1
RFC文档中文翻译计划