搜索
NetworkWorkingGroupC.HedrickRequestforComments:1058RutgersUniversityJune1988翻译：马儿快跑2002.4路由信息协议（RoutingInformationProtocol）本备忘录的状态本备忘录描述了一个已经存在的协议，它用以在网关(gateways)和其他主机(hosts)间交换路由信息。它被作为在Internet开发网关软件的基础。引用本备忘录没有限制。目录1.简介1.1.协议的局限性1.2.本文档的组成2.距离向量算法2.1.拓扑结构改变时的处理2.2.避免不稳定性2.2.1.水平分割2.2.2.触发更新3.协议详述3.1.信息格式3.2.考虑地址3.3.记时器3.4.输入进程3.4.1.请求3.4.2.回应3.5.输出进程3.6.兼容性4.控制功能综述本备忘录包含以下内容：-说明一种已经被广泛使用而没有被正式成文的路由协议和算法，-改进算法以提高其在大型网络中的稳定性。这些改进不会引起已有网络的不兼容，这些改进可以和原有的实现方式容为一体。-建议一些功能以提供更好的配置和控制，这些功能用以解决在NSFnet通讯中显示出的问题。当然，它们应当提供更通用的功能。这里提到的路由信息协议(RIP)，是由伯克莱(Berkeley)4.3的“routed”项目发布的。当然还有很多其他的实现方式。很不幸，多种实现在细节上有很多不同。这里描述的是各个实现功能上的组合。我们相信根据本文设计的程序可以和其他RIP的实现协同工作。本文对尺度(metrics)增加采取了与大多数实现不同的视角。通过对本地网段的尺度做相应的调整，保持了和其他实现方式的兼容性。详见3.6节1.简介本备忘录描述了一种使用Bellman-Ford(或称为距离向量)算法的协议。这种算法早先在ARPANET上被用于计算网络路由信息。具体的协议描述、包格式是基于伯克莱(Berkeley)UNIX的“routed”项目。这已经成为了网关和主机间交换路由信息的事实标准，用以不同厂商的网关产品间通讯。虽然，同一厂商的产品往往使用其自己的协议。这个协议是作为“内部网关协议(interiorgatewayprotocol)”而使用的。如当前Internet般的大型网络，是不可能在整个网络上使用一种单一的路由协议的。网络将被分成为一系列的“自治系统(autonomoussystems)”。每个自治系统都被赋予为一个实体，提供技术上和管理上的控制。每个自治系统可以有不同的路由方式。在自治系统中使用的路由协议被称为内部网关协议(IGR)。另一种路由协议面向自治系统，最早的这类协议是“EGP(外部网关协议/exteriorgatewayprotocol)”,目前还在Internet上使用。这些协议现在被叫做自治系统间(inter-AS)路由协议。RIP在同类协议中被设计为适合于中等规模网络使用。适合于那些网络间连接线路的速度差别不大的网络作为IGP。关于RIP适用条件的详细说明见：[3]BradenandPostel。RIP使用一类叫做“距离向量”的算法。这类算法最早是由FordandFulkerson[6]提出的。所以这也被称为Ford-Fulkerson算法。有时也被称为Bellman-Ford算法，这是因为这一描述是基于Bellman公式。(这一领域的介绍见[1]）其描述文档见[2]，该文讲述了路由算法的数学模型，并描述且证明了算法中的变量，及其他相关内容。该算法的最初实现在1969年被用于ARPANET。这一协议家族还包括Xerox网络协议(XNS),PUP协议(见[4])。一个较新的版本使用了XNS的结构，并更名为路由信息协议(见[7])。Berkeley的算法与其大致相同，不过将XNS的地址转换为一种更通用的格式用以包括IP等地址，并将路由更新时间限定在30秒。因为其相似性，RIP这一名称被用于XNS协议和其他协议中。RIP被设计为在基于IP的Internet中使用。Internet可以被理解成通过网关相连的一系列网络。在这里网络可以是点对点的连接，或复杂些的网络如以太网或ARPANET。主机和网关使用IP地址在网络中出现。路由是指主机和网关决定向何处发送包的方法。当目标在主机或网关直接相连的网络时，包将被直接发送到目标。令人感兴趣的是，当目标不直接可达时，主机或网关将试图将包发往更靠近目标的网关。路由协议的目标很简单：支持需要被路由的信息。1.1.协议的局限性本协议不解决所有的路由问题。如上所述，是被设计为适合中等规模网络做为IGP使用。另外，还要注意一下限制：-协议限定网络最大路径为15跳。设计者认为这一协议不适合于大型网络。注意，这一限定声明是在假设经过每个网络的成本(cost)为1，正如RIP一般配置的情况。如果管理员选择了较大的成本,15的上限可能成为问题。-协议使用“记数到无穷大”表示一些特殊情况(将在下一节中说明)。如果系统中有几百个网络，路由回路(routingloop)将会充斥其间。解决路由回路或需要很多时间(如果路由更新的频率受到限制)，或需要很多带宽(如果每次改变都发送更新)。这样在回路被纠正前会消耗很多带宽。我们相信，在现实情况下，这不会产生问题(除非是低速线路)。即使这样，这个问题还需要被认真对待，而且使用多种预防措施来避免在大多数情况下出现这样的问题。-协议使用固定的“尺度(metrics)”来描述不同的路径。当路径选择需要基于实时参数，如：延迟、可靠性、负载时是不适合的。使用这类实时参数会明显产生不稳定性。1.2.本文档的组成本文档的主体内容分为两部分，占据下面两章：2从概念上了解距离向量算法的发展和原理。3实际协议的描述这两章大致按这样的范围叙述。第2章给出了算法大致的数学模型，一开始先描述简单算法，然后再逐渐细致，呈“螺旋上升”的方法。第3章描述实际的协议，将第2章的内容具体化。通过第3章的描述，就可以实现整个RIP。2.距离向量算法路由的任务就是找到一条从源到目标的路径。在IP“Catenetmodel”中，这被简化为寻找网络间的网关。当通讯处于一个网络或子网时，由该特定的网络来解决路由问题。如以太网和ARPANET都定义了方法，使在一个网络中，任何源能够和指定的目标通讯。当源和目标不在同一网段时，IP路由才变的必要。这时，通讯必须通过连接网络的网关。当网络不邻接时，通讯将通过一系列用网关相连的网络。当通讯到达与目标处于同一网络的网关后，将使用该网络自身的方法到达目标。在本章中，术语“网络(network)”包含单一广播网络(如以太网)、点对点线路或ARPANET。其关键点是网络被作为IP的单一实体。即便在不需要路由(如点对点线路)，或路由被设置为对IP透明的情况，都允许IP将整个网络作为是一个完全连接的系统(如以太网或ARPANET)。这里的术语“网络”和在讨论IP地址时使用的“网络”有所不同。在讨论IP地址时，一个网络可能被分为多个“子网(subnet)”。而在这里，我们对子网同样使用“网络”这个术语。在网络间寻找路径有多种方法。最常用的分类方法是按照网关间交换信息的不同类型。距离向量算法仅交换少量信息，每个参与路由协议的实体(网关或主机)都保留所有目标的信息。通常，同一个网络中所有实体的信息被汇总成一个路由项，用以表示到达该网络上所有目标的路径。这是因为对IP而言，一个网络内的路由是不存在的。路由数据中的每一个项都包含了到达目标的下一跳网关，以及衡量到达目标距离的“尺度(metric)”。距离没有明确的概念，可以是到达目标的延迟、或发送信息的货币成本等等。距离向量算法的得名来源于比较不同的距离来得到最佳路径。此外，信息只在邻接，即共享同一网络的实体间交换。虽然路由通常是基于网络信息，有时也需要保持到达独立主机的路径信息。RIP协议对待网络与主机没有差别。不管是网络还是主机，RIP都交换其信息(但是，有一些实现不支持主机路由，见3.2节)。事实上，在数学模型中将其做转换是很方便的。当在抽象描述算法的时候，最好将到达一个网络的路由项看作为所有连接该网络的实体项的缩写。这是因为在IP层，一个网络内部没有层次结构。我们也将一个给定网络中的所有项赋予同样的距离。上面曾说到每个实体都要为每个路由项保留所有的信息。在实际中一般需要保留以下信息：-地址：该算法的IP实现中，必须有主机或网络的IP地址。-网关：到达目标的路径上的第一个网关。-接口：到达第一个网关的物理网段。-尺度：表示到达目标距离的数值。-时间：表示自从该项上次更新以来的时间。此外还包括多种标志和内部信息。这些信息在初始时包含了直接相连的实体。当从邻居网关接收到信息后，信息将会被更新。主机和网关之间的信息主要通过更新来传递。每个参与路由协议的实体都将自己当前的路由信息作为更新信息发送。这样仅通过与邻居实体交换信息，就可以得到整个系统的最佳路径。算法将在下一节中描述。如上所述，路由的任务是寻找到达最终目标的路径。距离向量算法是基于一张给出系统内各目标最佳路径的表。为了定义什么样的路径是最好的，需要对路径进行衡量。这就是“尺度(metric)”。在简单系统中，常常使用的尺度是计算信息需要经过多少个网关。复杂些的系统中，将信息传输所需的延迟、所需的成本等作为尺度。还需要将各个跳数的“成本”相加。如果实体i、j直接相连而不通过其他网关，公式d(i,j)和i、j间的费用相关。在正常情况下，给定网络上的所有实体被平等看待，其d(i,j)表示使用该网络的成本，且其值相同。衡量一条完整的路径，要将各跳的成本相加。在本备忘录中，设定成本为正整数。公式D(i,j)表明实体i、j间的最佳尺度。这在每一对实体间都需定义。d(i,j)表示的是独立的一步。当实体i、j直接相连时，d(i,j)表示其连接成本；对实体i、j不直接相连的情况d(i,j)为无穷大。(注意d(i,i)为无穷大，因为不认为一个节点直接连接到自己。)因为费用被考虑，下面列出的是最佳尺度的计算公式。D(i,i)=0,所有的iD(i,j)=min[d(i,k)+D(k,j)],不同的k最佳的路径是使d(i,k)+D(k,j)达到最小的邻居k。（这样的计算在路由器上会作多次）第二个等式中的k可以被限定为i的直接邻居，不然d(i,k)将是无穷大，总的等式不可能最小。计算就是基于这样简单的算法。实体i从其邻居k发送的信息中得到目标j的距离。当收到后，i加上i、k之间的费用d(i,k)。并比较所有的邻居取得最小值。在[2]中证明了，当拓扑结构不变时，算法可以在有限的时间内使D(i,j)正确汇聚。作者没有假设各个实体发送信息的次序，也没有指出何时重新计算最小值。基本上，实体将不断的发送信息并重计算尺度，而且网络不能延迟这些信息(实体的崩溃将导致拓扑改变)。他们同样证明，除了可以肯定是非负数，不要对D(i,j)的初始值作出假设。事实上，不需要假设是很好也很重要的。不对实体发送信息的次序作出假设，可以使各实体按照其各自的时钟异步的运行算法；更新信息也可以被网络丢弃，只要不被全部丢弃。不对初始值作出假设，可以使算法处理拓扑改变。当系统改变后，路由算法可以从旧的状态向新的状态稳定。不然，可能会有导致不汇聚的情况。上面的算法(以及说明)都假设每一个实体都保持了从其邻居获得信息的所有备份，并在其中得出一个最小值。实际的实现不需这样，仅仅记住一个最佳尺度，及发送这个尺度的邻居。当发现一个更好(更小)的尺度后再替换。这样可以不用存储所有邻居的信息而计算出最小值。上面的描述和实际的RIP协议还有一个不同：在描述中，每个实体有其自身的一项，其距离为0。而事实上一般不这样。回忆上面所说，同一个网络中所有实体的信息被汇总成一个路由项。考虑以下情况：主机或网关G连接到网络A上。C为使用网络A的成本(通常是1)。(再回忆：对IP而言，一个网络内的路由是不存在的，一个网络中的两个实体有同样的成本）在理论上，G可以得到网络A上所有实体H的信息，并认为到自身的成本为0。G将计算出到H的成本为C+0，G将仅