实验五：路由算法之OSPF协议分析.docx

计 算 机 网 络 实 验 实 验 指 导 书 实验名称 路由算法之OSPF协议分析 实验目的 1．掌握观察和配置主机、路由器 2．观察路由器的OSPF协议的现象 3．掌握OSPF的工作原理及过程 4．掌握OSPF的报文格式 实验背景 链路状态（OSPF）路由是第二类主要的域内路由协议。链路状态协议的基本思想非常简单：每个节点都知道怎样到达它的邻接点，如果我们确保这种信息被完整地传播到每个节点，那么每个节点都有足够的网络信息来建立一个完整的网络映像。显然这是找到到达网络中任一点的最短路径的充分（但不必要）条件。因此，链路状态路由协议依靠两种机制：链路状态信息的可靠传播，根据所有积累的链路状态知识的总和进行的路由计算。 可靠扩散 可靠扩散（Reliable Flooding）是确保参与路由协议的所有节点都能得到来自其他节点的一个链路状态信息副本的处理过程。正如术语扩散（flooding）所揭示的，它的基本思想是一个节点沿着所有的与其直接相连的链路把其链路状态信息发送出去，接收到这个信息的每个节点再沿着所有与它直接相连的链路进行转发。这个过程一直继续，直到该信息到达网络中的所有节点。 路由计算 首先我们用图论的术语来回顾一下路由计算中所用到的Dijkstra算法。设想一个节点将它接收到的所有LSP（链路状态分组）信息构造成一个代表网络的图，其中N代表图中的节点集合，l(i,j)表示两个节点i,j∈N之间的边上的非负开销（权值），如果在i、j之间没有边相连，则l(i,j)=∞。在下面的描述中，我们令s表示这个节点，s∈N，也就是执行算法寻找到达N中其他所有节点的最短路径的节点。此外，算法还维护以下两个变量：M代表到目前位置参与算法的节点集，C(n)表示从节点s到每个节点n的路径开销。给出这些定义后，算法的定义如下： M=(s) for N-{s}中的每个n C(n)=l(s,n) While (n≠M) M=M∪{w}以致C(w)对于(N-M)中的所有w而言是最小的 for(N-M)中的每个n C(n)=MIN(C(n),C(w)+l(w,n)) 算法基本执行过程如下。首先从含有节点s的M开始，并使用到直接相连节点的已知开销初始化到其他节点的开销表C(n)。然后寻找能以最小开销(w)到达的节点，并把这个节点加入M中。最后考虑用经过w到达节点的开销来更新开销表。在算法的最后一行中，如果从源点s到w，加上从w到n总的开销小于已有的从s到n旧的路径的开销，那么我们就选择这条经w到n的新路径，重复这个过程，知道所有节点都归入M中。 实际上，每台交换机使用一种称为向前搜索（forward search）的Dijkstra算法实现，从它收集的LSP中直接计算路由表。具体地说，每台交换机维护两张表：试探表和证实表。每张表中有多条记录，每条记录包含（目的地，开销，下一跳）。 链路状态路由算法有许多优点：它可以很快达到稳定状态，不产生过多的通信量，而且对拓扑结构改变或节点故障反应迅速。但缺点是每个节点存储的信息量（一个网络中其他所有节点的LSP）可能非常大。这是路由的基本问题之一，也是可扩展性这个更一般性问题的一个例证。 开放最短路径优先协议（OSPF） 一个使用最广泛的链路状态路由协议是开放最短路径优先（Open Shortest Path First）协议。OSPF为以上描述过的基本链路状态算法增加了相当多的特性，这些特性包括： 路由消息的认证：OSPF早期的版本使用一个简单的8字节口令进行认证。虽然这个认证尚不足以防止那些恶意用户，但是它减少了由错误配置引起的很多问题。 附加的层次：分层是使系统具有更好的可扩展性的基本工具之一。OSPF通过允许将域划分成区（area）给路由层次结构引入了另外一层。这意味着域内的路由器无须知道如何到达域内的每个网络，只需知道如何到达正确的区就足够了。这样，必须传送及存储在每个节点中的信息量将会减少。 负载平衡：OSPF允许到同一位置的多条路由有相同的开销，这样可以使通信量均匀地分布于这几条路由上。 实验原理 OSPF报文格式 OSPF报文是由多重封装构成的，封装在IP头部内的是5种OSPF报文类型中的一种， 每一种报文类型都是由一个OSPF报文头部开始，这个OSPF报文头部对于所有的报文类型都是相同的。 OSPF所有报文类型都共享一个相似的报文结构，从一个通用的24字节首部开始，这种通用的首部使某些标准信息能够按照一致的方式进行传递，它还使收到OSPF报文的设备能够快速确定自己收到的是哪种类型的报文，以便了解是否还需要检查报文的剩余部分。如下图所示。 图 2-1 OSPF报文由一系列封装组成 OSPF有5种分组类型，这5种分组类型直接封装到IP分组的有效负载中，如图，OSFP分组不使用传输控制协议（TC