itpub论坛 - rfc 1058 路由信息协议（routing information protocol）.htm

著名的RFC文档,其中有一些文档是已经翻译成中文的的.

<br />
1.2. 本文档的组成
<br />

<br />
本文档的主体内容分为两部分，占据下面两章：
<br />
2 从概念上了解距离向量算法的发展和原理。
<br />
3 实际协议的描述
<br />

<br />
这两章大致按这样的范围叙述。第2章给出了算法大致的数学模型，一开始先描述简单算法，然后再逐渐细致，呈“螺旋上升”的方法。第3章描述实际的协议，将第2章的内容具体化。通过第3章的描述，就可以实现整个RIP。
<br />

<br />
</font></p>
	
	<p><font face="verdana, arial, helvetica" size="2" ><br>
__________________<br>
不用告诉问路者最近的路，而要告诉他最好找的路
<br />
email : [e-mail]</font></p>
	<p></p>
	<p align="right"><font face="verdana,arial,helvetica" size="1" >
 <a HREF="report.php?s=&postid=142678"><IMG SRC="images/warn.gif" BORDER=0 ALT="向版主反映这个帖子"></A><a href="postings.php?s=&action=getip&postid=142678"><img src="images/ip.gif" border=0 alt="查看马儿快跑 的IP地址"</a></font></p>
	</td>
</tr>
<tr>
	<td bgcolor="#DFDFDF" width="175" height="16" nowrap><font face="verdana,arial,helvetica" size="1" ><img src="images/off.gif" border="0" alt="马儿快跑 不在线" align="absmiddle"> <img src="images/posticon.gif" border="0" alt="旧帖">
	02-04-25 <font color="#666686">13:43</font></font></td>
	
	<td bgcolor="#DFDFDF" width="100%" valign="middle" height="16">
		<table width="100%" border="0" cellpadding="0" cellspacing="0">
		<tr valign="bottom">
			<td><font face="verdana,arial,helvetica" size="1" >
			<a href="member.php?s=&action=getinfo&userid=10" target="_blank"><img src="images/profile.gif" border="0" alt="点这里查看 马儿快跑 的个人资料"></a> <a href="private.php?s=&action=newmessage&userid=10"><img src="images/sendpm.gif" border="0" alt="点这里给 马儿快跑发送一条悄悄话"></a>   <a href="search.php?s=&action=finduser&userid=10"><img src="images/find.gif" border="0" alt="查找 马儿快跑 的更多帖子"></a> <a href="member2.php?s=&action=addlist&userlist=buddy&userid=10"><img src="images/buddy.gif" border="0" alt="将 马儿快跑 添加到你的好友列表"></a>
			 &nbsp; <a href="http://search.tencent.com/cgi-bin/friend/user_show_info?ln=35945104" target=_blank><img src="images/oicq.gif" alt="马儿快跑 的OICQ号码:35945104" border=0></a> &nbsp;&nbsp;<!-- $ post[aimicon] --> <!-- $ post[yahooicon] --> 
			</font></td>
			<td align="right" nowrap><font face="verdana,arial,helvetica" size="1" >
			<a href="editpost.php?s=&action=editpost&postid=142678"><img src="images/edit.gif" border="0" alt="编辑/删除"></a>
			<a href="newreply.php?s=&action=newreply&postid=142678"><img src="images/quote.gif" border="0" alt="引用/回复"></a>
			</font></td>
		</tr>
		</table>
	</td>
</tr>
</table>
</td></tr></table>

<!-- spacer --></td><td width="10"><img width="10" height="1" src="images/space.gif" alt=""></td></tr></table>
<table bgcolor="#FFFFFF" width="100%" cellpadding="0" cellspacing="0" border="0"><tr><td width="10"><img width="10" height="1" src="images/space.gif" alt=""></td><td width="100%"><!-- spacer -->

<table cellpadding="0" cellspacing="0" border="0" bgcolor="#FFFFFF"  width="100%" align="center"><tr><td>
<table cellpadding="4" cellspacing="1" border="0"  width="100%">
<tr>
	<td bgcolor="#F1F1F1" width="175" valign="top" nowrap>
	<a name="post142685"></a>
	
	<font face="verdana, arial, helvetica" size="2" >马儿快跑</font><br>
	<font face="verdana,arial,helvetica" size="1" >版主</font><br>
	<img src="avatar.php?userid=10&dateline=1008034726" border="0" alt=""><p>
	<font face="verdana,arial,helvetica" size="1" >注册日期: 2001 Sep<br>
	来自: 苏州<br>
	发帖数量: 719<br>
                <!--论坛积分:--></font></td>
	
	<td bgcolor="#F1F1F1" width="100%" valign="top">
	<font face="verdana,arial,helvetica" size="1" > </font>
	<p><font face="verdana, arial, helvetica" size="2" >2. 距离向量算法
<br />

<br />
路由的任务就是找到一条从源到目标的路径。在IP“Catenet model”中，这被简化为寻找网络间的网关。当通讯处于一个网络或子网时，由该特定的网络来解决路由问题。如以太网和ARPANET都定义了方法，使在一个网络中，任何源能够和指定的目标通讯。当源和目标不在同一网段时，IP路由才变的必要。这时，通讯必须通过连接网络的网关。当网络不邻接时，通讯将通过一系列用网关相连的网络。当通讯到达与目标处于同一网络的网关后，将使用该网络自身的方法到达目标。
<br />

<br />
在本章中，术语“网络(network)”包含单一广播网络(如以太网)、点对点线路或ARPANET。其关键点是网络被作为IP的单一实体。即便在不需要路由(如点对点线路)，或路由被设置为对IP透明的情况，都允许IP将整个网络作为是一个完全连接的系统(如以太网或ARPANET)。这里的术语“网络”和在讨论IP地址时使用的“网络”有所不同。在讨论IP地址时，一个网络可能被分为多个“子网(subnet)”。而在这里，我们对子网同样使用“网络”这个术语。
<br />

<br />
在网络间寻找路径有多种方法。最常用的分类方法是按照网关间交换信息的不同类型。距离向量算法仅交换少量信息，每个参与路由协议的实体(网关或主机)都保留所有目标的信息。通常，同一个网络中所有实体的信息被汇总成一个路由项，用以表示到达该网络上所有目标的路径。这是因为对IP而言，一个网络内的路由是不存在的。路由数据中的每一个项都包含了到达目标的下一跳网关，以及衡量到达目标距离的“尺度(metric)”。距离没有明确的概念，可以是到达目标的延迟、或发送信息的货币成本等等。距离向量算法的得名来源于比较不同的距离来得到最佳路径。此外，信息只在邻接，即共享同一网络的实体间交换。
<br />

<br />
虽然路由通常是基于网络信息，有时也需要保持到达独立主机的路径信息。RIP协议对待网络与主机没有差别。不管是网络还是主机，RIP都交换其信息(但是，有一些实现不支持主机路由，见3.2节)。事实上，在数学模型中将其做转换是很方便的。当在抽象描述算法的时候，最好将到达一个网络的路由项看作为所有连接该网络的实体项的缩写。这是因为在IP层，一个网络内部没有层次结构。我们也将一个给定网络中的所有项赋予同样的距离。
<br />

<br />
上面曾说到每个实体都要为每个路由项保留所有的信息。在实际中一般需要保留以下信息：
<br />

<br />
- 地址：该算法的IP实现中，必须有主机或网络的IP地址。
<br />

<br />
- 网关：到达目标的路径上的第一个网关。
<br />

<br />
- 接口：到达第一个网关的物理网段。
<br />

<br />
- 尺度：表示到达目标距离的数值。
<br />

<br />
- 时间：表示自从该项上次更新以来的时间。
<br />

<br />
此外还包括多种标志和内部信息。这些信息在初始时包含了直接相连的实体。当从邻居网关接收到信息后，信息将会被更新。
<br />

<br />
主机和网关之间的信息主要通过更新来传递。每个参与路由协议的实体都将自己当前的路由信息作为更新信息发送。这样仅通过与邻居实体交换信息，就可以得到整个系统的最佳路径。算法将在下一节中描述。
<br />

<br />
如上所述，路由的任务是寻找到达最终目标的路径。距离向量算法是基于一张给出系统内各目标最佳路径的表。为了定义什么样的路径是最好的，需要对路径进行衡量。这就是“尺度(metric)”。
<br />

<br />
在简单系统中，常常使用的尺度是计算信息需要经过多少个网关。复杂些的系统中，将信息传输所需的延迟、所需的成本等作为尺度。还需要将各个跳数的“成本”相加。
<br />

<br />
如果实体i、j直接相连而不通过其他网关，公式d(i,j)和i、j间的费用相关。在正常情况下，给定网络上的所有实体被平等看待，其d(i,j)表示使用该网络的成本，且其值相同。衡量一条完整的路径，要将各跳的成本相加。在本备忘录中，设定成本为正整数。
<br />

<br />
公式D(i,j)表明实体i、j间的最佳尺度。这在每一对实体间都需定义。d(i,j)表示的是独立的一步。当实体i、j直接相连时，d(i,j)表示其连接成本；对实体i、j不直接相连的情况d(i,j)为无穷大。(注意d(i,i)为无穷大，因为不认为一个节点直接连接到自己。)因为费用被考虑，下面列出的是最佳尺度的计算公式。
<br />

<br />
             D(i,i) = 0,                      所有的i
<br />
             D(i,j) = min [d(i,k) + D(k,j)],  不同的k
<br />

<br />
最佳的路径是使d(i,k) + D(k,j)达到最小的邻居k。（这样的计算在路由器上会作多次）第二个等式中的k可以被限定为i的直接邻居，不然d(i,k)将是无穷大，总的等式不可能最小。
<br />

<br />
计算就是基于这样简单的算法。实体i从其邻居k发送的信息中得到目标j的距离。当收到后，i加上i、k之间的费用d(i,k)。并比较所有的邻居取得最小值。
<br />

<br />
在[2]中证明了，当拓扑结构不变时，算法可以在有限的时间内使D(i,j)正确汇聚。作者没有假设各个实体发送信息的次序，也没有指出何时重新计算最小值。基本上，实体将不断的发送信息并重计算尺度，而且网络不能延迟这些信息(实体的崩溃将导致拓扑改变)。他们同样证明，除了可以肯定是非负数，不要对D(i,j)的初始值作出假设。事实上，不需要假设是很好也很重要的。不对实体发送信息的次序作出假设，可以使各实体按照其各自的时钟异步的运行算法；更新信息也可以被网络丢弃，只要不被全部丢弃。不对初始值作出假设，可以使算法处理拓扑改变。当系统改变后，路由算法可以从旧的状态向新的状态稳定。不然，可能会有导致不汇聚的情况。
<br />

<br />
上面的算法(以及说明)都假设每一个实体都保持了从其邻居获得信息的所有备份，并在其中得出一个最小值。实际的实现不需这样，仅仅记住一个最佳尺度，及发送这个尺度的邻居。当发现一个更好(更小)的尺度后再替换。这样可以不用存储所有邻居的信息而计算出最小值。
<br />

<br />
上面的描述和实际的RIP协议还有一个不同：在描述中，每个实体有其自身的一项，其距离为0。而事实上一般不这样。
<br />

<br />
回忆上面所说，同一个网络中所有实体的信息被汇总成一个路由项。考虑以下情况：主机或网关G连接到网络A上。C为使用网络A的成本(通常是1)。(再回忆：对IP而言，一个网络内的路由是不存在的，一个网络中的两个实体有同样的成本）在理论上，G可以得到网络A上所有实体H的信息，并认为到自身的成本为0。G将计算出到H的成本为C+0，G将仅维持一条到网络A、成本是C的项，而不是为每个H建立一项。这一项可以被认为是到达网络A上所有实体的汇总；唯一不能被汇总的项是到G自身，其成本是0而不是C。但我们从不使用0实体，可以将其和网络A的项合并。考虑这一策略的另一含义：因为我们不使用0实体，不作为网关的主机就不需要发送更新信息。不作为网关的主机(也就是只连接到一个网络的主机)，只会发送自身的一项D(i,i)=0。因为这些主机只有一个接口，要到达其他网络的路径如果到达该端口也会被从同一端口返回。这样其成本就会比C大。所以非网关根本不需要参与路由协议。
<br />

<br />
让我们来汇总一下主机或网关G的工作：对于系统中的每一个目标，G都保持当前的尺度，和发送这一尺度的邻居网关。如果目标在与G直接相连的网络上，G将使用表示网络成本的一项，而不使用任何网关。显然，当计算汇聚到正确的尺度后，按这种技术记录下的邻居将是到达目标的路径上的第一个网关(如果有多条等价路径，第一个网关将是其中之一)。也就是说将通过网关可以用多少成本到达目标。
<br />

<br />
仅当有更小的尺度到达的时候，当前保留的尺度才能被降低。尺度也可能被增加，因为一开始的估计较小。可以做这样的规定：设当前到目标的路径是使用网关G，尺度D；对于从其他网关得到的信息，只有当其尺度比D好时才使用；而对于从G来的信息，不管好坏都将被使用。可以看到，通过这样的规定得到的路由表与保持所有从邻居得到的信息得到的路由表是一致的。(注意在这里的讨论中，网络被认为是静态的，系统中没有网络会失效。)
<br />

<br />
以上是距离向量算法的简单概述。(这还不是RIP协议的描述，仍需要更精确的描述)。每一个参与路由协议的实体都需要按照下面的步骤。每个网关都必须包括，非网关主机也可以参与。
<br />

<br />
- 保持到达系统中每个目标的表项。每一项都包括到达目标的距离和路径上的第一个网关。理论上讲，需要有指向自身，尺度为0的一项。但事实上可以不包括。
<br />

<br />
- 向每一个邻居周期性的发送路由更新。更新中的信息包括路由表中的所有信息。包含到达每个目标的项，及到达目标的距离。
<br />

<br />
- 邻居G'发送路由更新，将其尺度加上G'相关联的网络成本(是更新信息到达的网络)得到新的距离D'。将结果与当前路由表中的项比较。如果D'比现有的D小时，采用新的路径；即将新的路径改为使用G'，距离D'。当G'=G时，使用新的尺度，即使尺度变大。
<br />

<br />
2.1. 拓扑结构改变时的处理
<br />

<br />
以上的讨论都假设网络拓扑是固定的。实际上，网关和线路经常会出错和恢复。我们需要对算法作出一些细小的变动来处理这些情况。在理论化的算法中包括了所有的直接邻居，如果拓扑改变，在下一次计算中就会有反映。而在实际算法中，简化了算法，仅保持给定目标的最佳路径。当包含在路径中的网关或网络崩溃后，计算将不会反映这一变化。算法依赖于其邻居发现尺度改变，如果网关崩溃，就不会向其邻居报告变化。
<br />

<br />
为了解决这类问题，距离向量协议必须使用路径时效来进行预防。不同的协议，其细节不同。例如，RIP网关每30秒周期性的向其所有的邻居发送更新信息。如使用网关G到达网络N，如果有180秒没有收到G的更新，就假设网关G或连接G的网络崩溃了。这样我们就可以标志路径无效。如果从另一邻居得到到达网络N的有效路径，就将其替代无效的项。注意因为信息在传输中可能被丢失，所以将等待180秒即使每30秒就将会有更新信息。仅因为一次信息的遗失而使路径失效是不适合的。
<br />

<br />
正如我们下面将说的，将无效的路径通知其邻居是非常有用的。RIP和许多其他同类协议一样，通过在普通更新信息中标识网络为不可到达来实现。一个比最大的有效尺度更大的数值用来表示不可到达，在当前的RIP中使用16。16虽然是一个非常小的数字，但在这里通常被称为“无穷大”，很多实现都是这样规定的。其原因下面很快就要讲到。</font></p>
	
	<p><font face="verdana, arial, helvetica" size="2" ><br>
__________________<br>
不用告诉问路者最近的路，而要告诉他最好找的路
<br />
email : [e-mail]</font></p>
	<p></p>
	<p align="right"><font face="verdana,arial,helvetica" size="1" >
 <a HREF="report.php?s=&postid=142685"><IMG SRC="images/warn.gif" BORDER=0 ALT="向版主反映这个帖子"></A><a href="postings.php?s=&action=getip&postid=142685"><img src="images/ip.gif" border=0 alt="查看马儿快跑 的IP地址"</a></font></p>
	</td>
</tr>
<tr>
	<td bgcolor="#F1F1F1" width="175" height="16" nowrap><font face="verdana,arial,helvetica" size="1" ><img src="images/off.gif" border="0" alt="马儿快跑 不在线" align="absmiddle"> <img src="images/posticon.gif" border="0" alt="旧帖">
	02-04-25 <font color="#666686">13:44</font></font></td>
	
	<td bgcolor="#F1F1F1" width="100%" valign="middle" height="16">
		<table width="100%" border="0" cellpadding="0" cellspacing="0">
		<tr valign="bottom">
			<td><font face="verdana,arial,helvetica" size="1" >
			<a href="member.php?s=&action=getinfo&userid=10" target="_blank"><img src="images/profile.gif" border="0" alt="点这里查看 马儿快跑 的个人资料"></a> <a href="private.php?s=&action=newmessage&userid=10"><img src="images/sendpm.gif" border="0" alt="点这里给 马儿快跑发送一条悄悄话"></a>   <a href="search.php?s=&action=finduser&userid=10"><img src="images/find.gif" border="0" alt="查找 马儿快跑 的更多帖子"></a> <a href="member2.php?s=&action=addlist&userlist=buddy&userid=10"><img src="images/buddy.gif" border="0" alt="将 马儿快跑 添加到你的好友列表"></a>
			 &nbsp; <a href="http://search.tencent.com/cgi-bin/friend/user_show_info?ln=35945104" target=_blank><img src="images/oicq.gif" alt="马儿快跑 的OICQ号码:35945104" border=0></a> &nbsp;&nbsp;<!-- $ post[aimicon] --> <!-- $ post[yahooicon] --> 
			</font></td>
			<td align="right" nowrap><font face="verdana,arial,helvetica" size="1" >