论文部分内容阅读
OSPF协议是由IETF开发的一种内部网关协议(IGP)，特别适用于Internet环境，提供IP Subnetting和基于TOS的路由信息，并提供路由变更的认证机制，它充分利用了IP multicast功能来实现路由变更信息的收发。另外，OSPF采用了多种措施快速响应拓扑结构的改变，极大地减少了网络上路由信息的数量。
OSPF基于IP目的地址和IP包头的TOS域来路由IP包。它根据自治系统内部拓扑结构的改变快速地计算出无环路的路由表。在运行OSPF的每一个路由器中都维护一个描述自治系统拓扑结构的统一的数据库，该数据库由每一个路由器的局部状态信息（该路由器可用的接口信息、邻居信息）、路由器相连的网络状态信息（该网络所连接的路由器）、外部状态信息（该自治系统的外部路由信息）等组成。每一个路由器在自治系统范围内扩散相应的状态信息。所有的路由器并行运行同样的算法，根据该路由器的拓扑数据库构造出以它自己为根节点的最短路径树，该最短路径树的叶子节点是自治系统内部的其它路由器。应该强调的是， OSPF根据不同的TOS计算出不同的路由表（即不同的最短路径树）。当到达同一目的路由器存在多条相同代价的路由时，OSPF能够实现在多条路径上分配流量。
OSPF 协议原理
一、 自治系统分区
OSPF在设计上采取了把自治系统划分成不同区域(Area)的做法，区域由一组网络和它所联接的路由器组成。每个区域内部路由器的拓扑数据库实际上只包含着该区域的拓扑信息，在同一个区域内的路由器拥有同样的拓扑数据库。
OSPF定义了一个必须存在的骨干区(area 0)， OSPF的中枢区域，它与其它区域通过区域边界路由器(ABR)相连。OSPF规定骨干区必须连续，然而，在实际环境下并不一定能够保证骨干区连续，这时候可以通过配置虚链(Virtual Link)的方法保持骨干区的连续。虚链将属于骨干区的两个ABR连接起来，虚链本身属于骨干区，OSPF将通过虚链连接的两个路由器看作是通过未编号的点对点链路（unnumbered point-to-point）连接。
图一 自治系统分区
图二 虚链
二、区域间路由
当在两个区域间路由IP包的时候，必须通过骨干区。每一个区域的ABR自动总结到外部网络（其它区域或外部自治系统）路由信息和路由代价，并将该信息扩散到它所在的区域中。另外，如果自治系统中的某一区域被断开，导致该区域分解成两个区域，OSPF并不试图修复这个区域，原来经过区域内路由即可抵达的目的路由器在区域分解后要经过以上区域间的三步路由才能抵达。
三、外部路由和Stub区
对于该自治系统外部路由信息，可以通过该自治系统的区域边界路由器（ASBR）透明地扩散到整个自治系统的各个区域中。但是在OSPF中有一种特殊的区域，称为Stub区，该区域不允许外部路由信息的进入，因此如果Stub区要进行外部访问，则必须在该区域的ABR上配置缺省路由信息，这个缺省路由信息被ABR广播到Stub区的每一个路由器中，但不超出该区域的范围。
四、DR和BDR
在OSPF自治系统内部的每一个多路访问网络（multi-access network），通过Hello协议选举出一个指派路由器（Designated Router）和备份指派路由器（Backup Designated Router），指派路由器完成两个主要的功能：
* DR产生有关于该网络的网络链路广播，该广播由DR所在网络中的路由器列表组成。
* DR和该网络内的其它路由器建立一种邻接关系（星型结构），使区域内部各个路由器的链路状态（拓扑）数据库同步。
另一个比较重要的路由器是BDR， 它的设立是为了保证当DR发生故障时尽快接替DR的工作，而不至于出现由于需重新选举DR和重新构筑拓扑数据库而产生大范围的数据库震荡。当DR存在的情况下，BDR不生成网络链路广播消息。
在DR、BDR的选举后，该网络内其它路由器向DR、BDR发送链路状态信息，并经DR转发到和DR建立邻接关系的其它路由器。当链路状态信息交换完毕时，DR和其它路由器的邻接关系进入了稳定态，区域范围内统一的拓扑（链路状态）数据库也就建立了，每个路由器以该数据库为基础，采用SPF算法计算出基于TOS的路由表，就可以进行路由转发了。
协议实现
一、 OSPF协议包与链路状态广播
在路由器之间交换的OSPF协议包分为以下五种类型： Hello协议包；数据库描述包；链路状态请求包；链路状态变更包；链路状态确认包。
所有的OSPF协议包都只在具有邻接关系的路由器之间发送，除了Hello包，它是用来发现相邻的OSPF路由器的。除了在虚链中发送协议包外，每一个协议包仅仅只有一跳(TTL = 1)，邻接路由器（一般是DR）接受到协议包后，再判断是否在其它端口上转发该协议包。在不同的物理网络上，协议包的目的地址也不相同。
相应地，各种协议包承载的链路状态广播可以有五种形式：路由器链路状态广播；网络链路广播；总结链路广播（两种）；自治系统外部路由链路广播。
二、 Hello 协议
Hello协议的作用是发现和维护邻居关系、选举DR和BDR。通过Hello协议包的交换，网络中的路由器之间建立了双向通信，并得知了希望成为DR和BDR的路由器以及他们的优先级。
三、 DR选举
在初始状态下，网络中的DR和BDR被设置成0.0.0.0，这意味着没有DR和BDR被选举出来。经过Hello协议交换过程后，每一个路由器获得了希望成为DR和BDR的那些路由器的信息，按照下列步骤选举DR和BDR：
1．选择希望成为BDR的路由器中有最高优先级的那个路由器为BDR，如果有多个具有相同优先级的候选BDR存在，则选择具有最高Router ID（和每一个路由器相关的32位数字，一般为该路由器各个接口所配置的IP地址中最大的IP地址）的路由器为BDR。如果没有路由器声称希望成为BDR，则选择具有最高Router ID 的路由器为BDR。
2．选择希望成为DR的路由器中有最高优先级的那个路由器为DR，情况同上。
3．如果路由器X被选举为DR或BDR，或X不再是DR或BDR，重复1、2两步，以确保没有既是DR又是BDR的路由器的出现。
4．如果路由器X被选举为DR或BDR，设定该路由器接口的状态为DR或BDR。
5．如果路由器X被选举为DR或BDR，并且该网络是非广播型网络，路由器X必须向那些不适合成为DR或BDR的路由器（路由器优先级为0）发送Hello包。
DR在大多数情况下是邻接关系的终点。在多路访问网络中，DR和BDR与该网络内所有其它的路由器建立邻接关系。由于DR和BDR的引入，简化了网络的逻辑拓扑结构，将一个网状网络转变成一个星型网络，使协议包的扩散、计算变得简单，并有效防止了邻接关系震荡的发生。
四、数据库同步
通过建立并保持邻接关系，OSPF使具有邻接关系的路由器的数据库同步，进而保证了区域范围内所有路由器数据库同步。每一个路由器向它的邻居发送数据库描述包来描述自己的数据库，每一个数据库描述包由一组链路状态广播组成，邻居路由器接收该数据库描述包，并返回确认消息。以上的过程被称为“数据库交换过程”。此过程结束之后，从路由器得知主路由器中有一些最新的链接状态记录存在，于是向主路由器发送数据库请求包，请求相应的记录，主路由器收到后，向从路由器发送数据库变更包，更新从路由器中相关的记录。当所有的数据库请求包都已被主路由器处理后，主从路由器也就进入了邻接完成状态。当DR与整个区域内所有的路由器都完成邻接关系时，整个区域中所有路由器的数据库也就同步了。
图三 主从路由器协议包交换过程
五、路由表查找
在链路状态数据库完全同步后，OSPF计算最短路径树，构造出路由表。当有IP包需要查询路由表时，按照以下规则完成路由查找：
* 在路由表中选择相匹配的路由记录。相匹配的记录是指需转发IP包的目的地址“落在”该匹配路由记录的目的地址范围内。（该匹配记录可能有多个）
* 在这组匹配路由记录中，首先查找是否有路由记录属于区域内路由，如有，则转向下一步；否则，再查找是否有区域间路由记录存在、最后查找是否有外部路由记录存在。
* 根据第二步过滤的结果，取符合条件的路由中具有“最长匹配”的路由记录。
* 如果依然有多条路由记录存在，则根据需转发的IP包头的TOS类型选择经过第三步过滤后的路由记录。如果IP包头的TOS类型是x，而相应的TOS x类型的路由记录不存在，则选择TOS 0的路由记录。
根据以上路由表查找的步骤，我们就可以选择基于OSPF协议的最优路由，完成IP选路功能。
OSPF基于IP目的地址和IP包头的TOS域来路由IP包。它根据自治系统内部拓扑结构的改变快速地计算出无环路的路由表。在运行OSPF的每一个路由器中都维护一个描述自治系统拓扑结构的统一的数据库，该数据库由每一个路由器的局部状态信息（该路由器可用的接口信息、邻居信息）、路由器相连的网络状态信息（该网络所连接的路由器）、外部状态信息（该自治系统的外部路由信息）等组成。每一个路由器在自治系统范围内扩散相应的状态信息。所有的路由器并行运行同样的算法，根据该路由器的拓扑数据库构造出以它自己为根节点的最短路径树，该最短路径树的叶子节点是自治系统内部的其它路由器。应该强调的是， OSPF根据不同的TOS计算出不同的路由表（即不同的最短路径树）。当到达同一目的路由器存在多条相同代价的路由时，OSPF能够实现在多条路径上分配流量。
OSPF 协议原理
一、 自治系统分区
OSPF在设计上采取了把自治系统划分成不同区域(Area)的做法，区域由一组网络和它所联接的路由器组成。每个区域内部路由器的拓扑数据库实际上只包含着该区域的拓扑信息，在同一个区域内的路由器拥有同样的拓扑数据库。
OSPF定义了一个必须存在的骨干区(area 0)， OSPF的中枢区域，它与其它区域通过区域边界路由器(ABR)相连。OSPF规定骨干区必须连续，然而，在实际环境下并不一定能够保证骨干区连续，这时候可以通过配置虚链(Virtual Link)的方法保持骨干区的连续。虚链将属于骨干区的两个ABR连接起来，虚链本身属于骨干区，OSPF将通过虚链连接的两个路由器看作是通过未编号的点对点链路（unnumbered point-to-point）连接。
图一 自治系统分区
图二 虚链
二、区域间路由
当在两个区域间路由IP包的时候，必须通过骨干区。每一个区域的ABR自动总结到外部网络（其它区域或外部自治系统）路由信息和路由代价，并将该信息扩散到它所在的区域中。另外，如果自治系统中的某一区域被断开，导致该区域分解成两个区域，OSPF并不试图修复这个区域，原来经过区域内路由即可抵达的目的路由器在区域分解后要经过以上区域间的三步路由才能抵达。
三、外部路由和Stub区
对于该自治系统外部路由信息，可以通过该自治系统的区域边界路由器（ASBR）透明地扩散到整个自治系统的各个区域中。但是在OSPF中有一种特殊的区域，称为Stub区，该区域不允许外部路由信息的进入，因此如果Stub区要进行外部访问，则必须在该区域的ABR上配置缺省路由信息，这个缺省路由信息被ABR广播到Stub区的每一个路由器中，但不超出该区域的范围。
四、DR和BDR
在OSPF自治系统内部的每一个多路访问网络（multi-access network），通过Hello协议选举出一个指派路由器（Designated Router）和备份指派路由器（Backup Designated Router），指派路由器完成两个主要的功能：
* DR产生有关于该网络的网络链路广播，该广播由DR所在网络中的路由器列表组成。
* DR和该网络内的其它路由器建立一种邻接关系（星型结构），使区域内部各个路由器的链路状态（拓扑）数据库同步。
另一个比较重要的路由器是BDR， 它的设立是为了保证当DR发生故障时尽快接替DR的工作，而不至于出现由于需重新选举DR和重新构筑拓扑数据库而产生大范围的数据库震荡。当DR存在的情况下，BDR不生成网络链路广播消息。
在DR、BDR的选举后，该网络内其它路由器向DR、BDR发送链路状态信息，并经DR转发到和DR建立邻接关系的其它路由器。当链路状态信息交换完毕时，DR和其它路由器的邻接关系进入了稳定态，区域范围内统一的拓扑（链路状态）数据库也就建立了，每个路由器以该数据库为基础，采用SPF算法计算出基于TOS的路由表，就可以进行路由转发了。
协议实现
一、 OSPF协议包与链路状态广播
在路由器之间交换的OSPF协议包分为以下五种类型： Hello协议包；数据库描述包；链路状态请求包；链路状态变更包；链路状态确认包。
所有的OSPF协议包都只在具有邻接关系的路由器之间发送，除了Hello包，它是用来发现相邻的OSPF路由器的。除了在虚链中发送协议包外，每一个协议包仅仅只有一跳(TTL = 1)，邻接路由器（一般是DR）接受到协议包后，再判断是否在其它端口上转发该协议包。在不同的物理网络上，协议包的目的地址也不相同。
相应地，各种协议包承载的链路状态广播可以有五种形式：路由器链路状态广播；网络链路广播；总结链路广播（两种）；自治系统外部路由链路广播。
二、 Hello 协议
Hello协议的作用是发现和维护邻居关系、选举DR和BDR。通过Hello协议包的交换，网络中的路由器之间建立了双向通信，并得知了希望成为DR和BDR的路由器以及他们的优先级。
三、 DR选举
在初始状态下，网络中的DR和BDR被设置成0.0.0.0，这意味着没有DR和BDR被选举出来。经过Hello协议交换过程后，每一个路由器获得了希望成为DR和BDR的那些路由器的信息，按照下列步骤选举DR和BDR：
1．选择希望成为BDR的路由器中有最高优先级的那个路由器为BDR，如果有多个具有相同优先级的候选BDR存在，则选择具有最高Router ID（和每一个路由器相关的32位数字，一般为该路由器各个接口所配置的IP地址中最大的IP地址）的路由器为BDR。如果没有路由器声称希望成为BDR，则选择具有最高Router ID 的路由器为BDR。
2．选择希望成为DR的路由器中有最高优先级的那个路由器为DR，情况同上。
3．如果路由器X被选举为DR或BDR，或X不再是DR或BDR，重复1、2两步，以确保没有既是DR又是BDR的路由器的出现。
4．如果路由器X被选举为DR或BDR，设定该路由器接口的状态为DR或BDR。
5．如果路由器X被选举为DR或BDR，并且该网络是非广播型网络，路由器X必须向那些不适合成为DR或BDR的路由器（路由器优先级为0）发送Hello包。
DR在大多数情况下是邻接关系的终点。在多路访问网络中，DR和BDR与该网络内所有其它的路由器建立邻接关系。由于DR和BDR的引入，简化了网络的逻辑拓扑结构，将一个网状网络转变成一个星型网络，使协议包的扩散、计算变得简单，并有效防止了邻接关系震荡的发生。
四、数据库同步
通过建立并保持邻接关系，OSPF使具有邻接关系的路由器的数据库同步，进而保证了区域范围内所有路由器数据库同步。每一个路由器向它的邻居发送数据库描述包来描述自己的数据库，每一个数据库描述包由一组链路状态广播组成，邻居路由器接收该数据库描述包，并返回确认消息。以上的过程被称为“数据库交换过程”。此过程结束之后，从路由器得知主路由器中有一些最新的链接状态记录存在，于是向主路由器发送数据库请求包，请求相应的记录，主路由器收到后，向从路由器发送数据库变更包，更新从路由器中相关的记录。当所有的数据库请求包都已被主路由器处理后，主从路由器也就进入了邻接完成状态。当DR与整个区域内所有的路由器都完成邻接关系时，整个区域中所有路由器的数据库也就同步了。
图三 主从路由器协议包交换过程
五、路由表查找
在链路状态数据库完全同步后，OSPF计算最短路径树，构造出路由表。当有IP包需要查询路由表时，按照以下规则完成路由查找：
* 在路由表中选择相匹配的路由记录。相匹配的记录是指需转发IP包的目的地址“落在”该匹配路由记录的目的地址范围内。（该匹配记录可能有多个）
* 在这组匹配路由记录中，首先查找是否有路由记录属于区域内路由，如有，则转向下一步；否则，再查找是否有区域间路由记录存在、最后查找是否有外部路由记录存在。
* 根据第二步过滤的结果，取符合条件的路由中具有“最长匹配”的路由记录。
* 如果依然有多条路由记录存在，则根据需转发的IP包头的TOS类型选择经过第三步过滤后的路由记录。如果IP包头的TOS类型是x，而相应的TOS x类型的路由记录不存在，则选择TOS 0的路由记录。
根据以上路由表查找的步骤，我们就可以选择基于OSPF协议的最优路由，完成IP选路功能。