OSPF路由协议的算法原理与仿真实现

刘炳松　洪伟珍

摘要：OSPF（Open Shortest Path First，开放式最短路径生成树协议）是处于TCP/IP协议族的IP层协议，是目前应用最广泛的IGP协议。该文将详细介绍OSPF路由协议的核心算法原理，并通过虚拟仪器对OSPF路由协议进行仿真实现，最后，文章将简单分析该协议的安全性问题。

关键词：通信协议；SPF算法；OSPF路由协议；虚拟仪器

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2014）12-2723-03

Algorithm and Simulation of OSPF Routing Protocol

LIU Bing-song，HONG Wei-zhen

（Guangdong Technical School of Electronic Information，Guangzhou 510450，China）

Abstract： OSPF routing protocol， which is short for Open Shortest Path First， is in the IP layer in TCP/IP protocols， and is also the most widely used IGP protocol currently. This paper firstly introduces the algorithm principles of the OSPF routing protocol. Then the protocol is simulated with virtual instrument. Lastly， the paper briefly analyzes the security issues of the OSPF protocol.

Key words： communication protocol； SPF algorithm； OSPF routing protocol； virtual instrument

近年来，随着Internet技术在全球范围的飞速发展，应用于TCP/IP协议组中的网路层协议OSPF路由协议已发展成为在各类大型网络中应用最广泛的路由协议之一，也是TCP/IP包含的路由协议中最具有代表行的路由协议之一[1]。OSPF路由协议通过SPF（Shortest Path First，最短路径生成树算法）来计算到各节点的最短路径，该文将就该路由协议的基本原理及仿真实现展开详细介绍。

1 SPF算法与OSPF路由协议原理

SPF算法也被称为Dijkstra算法，是OSPF路由协议的基础。Dijkstra算法本身是一种应用在通信网模型中的单源最短路径算法。SPF算法则是根据目前网络的实际情况设定参数，可应用在实际大型网络中的最短路径算法[2]。这一部分主要介绍Dijkstra算法、SPF算法及OSPF路由协议的基本原理。

1.1 Dijkstra算法

Dijkstra算法是用于计算一个节点到其他所有节点的最短路径的一种单源最短路径算法，算法以起始点为中心向外层层扩展，直到扩展至终点为止。Dijkstra算法通常采用永久/临时标号和OPEN、CLOSE表两种表述方式，这里我们采用永久/临时标号的方式介绍Dijkstra算法的思想和具体实现步骤。

Dijkstra算法要求图中不存在负权边，设G=（V，E）是一个带权有向图，v为Dijkstra算法的源点，以该场景为例，我们介绍Dijkstra算法的基本思想如下：该算法将图G中的顶点集合V分为两组：一组是已求出最短路径的顶点集合S，算法开始时S中只有一个源点，随着算法的继续，每求得一条最短路径就将其加入到集合S中，当图中所有顶点都加入到S中时算法结束；另一组为其余未确定最短路径的顶点集合U，算法进行的过程是按最短路径的递增顺序依次把U中顶点加入S中。在这一过程中，要始终保持从源点v到集合S中各顶点的最短路径长度不大于从源点v到集合U中任何顶点的最短路径长度。为方便读者理解，这里列出Dijkstra算法的具体步骤：

步骤一：算法初始状态，集合S中只有一个源点，即S={v}；集合U中包含除v外的其他所有顶点。如果集合U中顶点u与源点v之间存在边或u不是v的出边邻接点，则该边上的权即代表顶点u的距离；

步骤二：选取集合U中与源点v距离最小的顶点u1，把u1加入集合S中。此时，该选定距离就是源点v到顶点u1的最短路径长度；

步骤三：将u1作为重新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过中间点u1后）比原来距离（不经过中间点u1时）短，则修改顶点u的距离值，修改后的距离值为到顶点u1的距离与边上的权值之和；

步骤四：重复步骤二和步骤三，直到图中所有顶点都包含到集合S中，算法结束。

1.2 SPF算法

SPF算法将路由域中的路由器作为根节点，计算这些节点到每一个目的节点（即目的地路由器）的距离。算法执行过程中，根节点根据一个统一的数据库计算得到结构类似于一棵树的路由域的拓扑结构图，即SPF算法中的最短路径图，在该最短路径图上完成OSPF路由协议。最短路径树的树干长度代表OSPF路由器至每一个目的地路由器的距离，即OSPF的Cost，计算方法如式1：

Cost = 100×106/链路带宽 （1）

其中，链路带宽以bps来表示。可以看出，OSPF的Cost 与链路带宽成反比，带宽越高，Cost越小，表示OSPF到目的地的距离越近。

1.3 OSPF路由协议

OSPF路由协议是一种链路状态的协议，主要适用于同一个路由域。这个路由域内的所有OSPF路由器都维护一个相同的数据库，其中存放的是该路由域中相应链路的状态信息，而OSPF路由器就是根据该数据库计算其路由表的[3]。endprint

OSPF遵循链路状态路由协议的统一算法，可简单概括为路由器在两种状态下的动作：第一，当路由器完成初始化或网络结构发生变化时，路由器产生链路状态广播数据包，包含路由器上的所有相连链路，即所有端口的状态信息。所有路由器通过“刷新”的方法交换链路状态数据。第二，当网络稳定下来时，即OSPF路由协议收敛下来时，所有的路由器根据其各自的链路状态信息数据库计算各自的路由表，包含路由器到每一个可到达目的地的Cost以及到达该目的地所要转发的下一跳路由[4]。

以上步骤反映了OSPF路由协议的一个特性，也正是链路状态路由协议区别于距离矢量路由协议的一大特性：当网络状态较稳定时，网络中传递的链路状态信息较少，也就是说，此时网络中是比较安静的[5]。

2 OSPF路由协议的仿真与安全性分析

本文通过虚拟设备LabVIEW对OSPF路由协议进行简单的仿真实现。LabVIEW（Laboratory Virtual Instrument Engineering Workbench）全称是实验室虚拟仪器工程平台，是美国国家仪器公司（NI）的创新软件产品。自NI公司1986年正式推出LabVIEW1.0至今，经历了多次改版与完善，目前包括控制与仿真、高级数字信号处理、统计过程控制、模糊控制、PDA和PID等众多附加软件包，可运行于Windows、Linux、Macintosh和Unix等多种平台，已成为目前应用最广、发展最快、功能最强的图形化软件开发继承环境之一。

本文将仿真由四个路由器通过OSPF路由协议组成的系统，该系统的数据输入部分共包括手动输入起点终点及已知路由模块、信息传递模块和连接表二维数组生成模块三部分构成。其中，手动输入起点终点及已知路由模块只需在LabVIEW前面板中输入参数即可，这里不做详细介绍。图2和图3分别列出了信息传递模块和连接表二维数组生成模块的实现流程图。

以上介绍的三大模块完成了OSPF路由协议在LabVIEW虚拟仪器平台的仿真，要通过此系统计算路由器的生成，需要将SPF算法引入该系统。读者可根据前文介绍的SPF算法原理设计最短中继计算模块，通过此模块即可得到系统中路由器的连接方式。

相对于其他一些内部网关路由协议，OSPF有比较复杂的内部状态机，因此攻击发起的复杂度较高。另外，层次化路由结构、可靠的泛洪机制、报文验证机制、报文接收与状态机等OSPF协议本身的保护机制也为其提供了安全性。但是，该协议仍存在一些安全漏洞。OSPF提供了空认证、明文认证、加密认证三种认证模式，如果OSPF启用空认证，攻击者无需获取密钥即可实现伪造攻击和重放攻击；如果OSPF启用密钥认证（明文认证或加密认证），攻击者无法获得密钥不能进行伪造攻击，但可以进行重放攻击。综上，针对OSPF的安全漏洞问题，我们仍需要进一步的研究，目前已经提出的解决方案主要是利用更合理的密码体制。另外，也有研究者提出了新的研究方向，利用密码体制安全性的同时引入入侵检测技术，更好实现OSPF的安全性[6]。

3 结束语

本文对TCP/IP协议族中目前大型网络中应用最为广泛的路由协议OSPF协议的核心算法进行了介绍，并通过虚拟仪器LabVIEW对其进行了仿真与实现，用以呈现此协议在实际运行时的实际情况，文章最后对OSPF协议的安全性问题进行了分析，该协议目前存在的安全漏洞仍需要进一步的研究与完善。

参考文献：

[1] （美国）特南鲍姆.计算机网络[M].北京：清华大学出版社，2004，8：290-310.

[2] Cory L.Clark.LabVIEW Digital Signal Processing and Digital Communications.The McGraw-Hill Companies[M].Inc.May，2005：23-50.

[3] （美国）史蒂文斯.TCP/IP详解.卷1：协议[M].北京：人民邮电出版社出版.2010.04：50-90.

[4] （美国）史蒂文斯.TCP-IP详解.卷三：TCP事务协议，HTTP，NNTP和UNIX域协议[M].北京：人民邮电出版社出版，2010.

[5] 张芳.OSPF路由协议的研究与实现[D].北京：北京邮电大学图书馆.北京邮电大学，2004，3.

[6] 康威，罗守山，辛阳.OSPF 路由协议安全性研究分析[J].计算机科学技术，2009.endprint

OSPF遵循链路状态路由协议的统一算法，可简单概括为路由器在两种状态下的动作：第一，当路由器完成初始化或网络结构发生变化时，路由器产生链路状态广播数据包，包含路由器上的所有相连链路，即所有端口的状态信息。所有路由器通过“刷新”的方法交换链路状态数据。第二，当网络稳定下来时，即OSPF路由协议收敛下来时，所有的路由器根据其各自的链路状态信息数据库计算各自的路由表，包含路由器到每一个可到达目的地的Cost以及到达该目的地所要转发的下一跳路由[4]。

以上步骤反映了OSPF路由协议的一个特性，也正是链路状态路由协议区别于距离矢量路由协议的一大特性：当网络状态较稳定时，网络中传递的链路状态信息较少，也就是说，此时网络中是比较安静的[5]。

2 OSPF路由协议的仿真与安全性分析

本文通过虚拟设备LabVIEW对OSPF路由协议进行简单的仿真实现。LabVIEW（Laboratory Virtual Instrument Engineering Workbench）全称是实验室虚拟仪器工程平台，是美国国家仪器公司（NI）的创新软件产品。自NI公司1986年正式推出LabVIEW1.0至今，经历了多次改版与完善，目前包括控制与仿真、高级数字信号处理、统计过程控制、模糊控制、PDA和PID等众多附加软件包，可运行于Windows、Linux、Macintosh和Unix等多种平台，已成为目前应用最广、发展最快、功能最强的图形化软件开发继承环境之一。

本文将仿真由四个路由器通过OSPF路由协议组成的系统，该系统的数据输入部分共包括手动输入起点终点及已知路由模块、信息传递模块和连接表二维数组生成模块三部分构成。其中，手动输入起点终点及已知路由模块只需在LabVIEW前面板中输入参数即可，这里不做详细介绍。图2和图3分别列出了信息传递模块和连接表二维数组生成模块的实现流程图。

以上介绍的三大模块完成了OSPF路由协议在LabVIEW虚拟仪器平台的仿真，要通过此系统计算路由器的生成，需要将SPF算法引入该系统。读者可根据前文介绍的SPF算法原理设计最短中继计算模块，通过此模块即可得到系统中路由器的连接方式。

相对于其他一些内部网关路由协议，OSPF有比较复杂的内部状态机，因此攻击发起的复杂度较高。另外，层次化路由结构、可靠的泛洪机制、报文验证机制、报文接收与状态机等OSPF协议本身的保护机制也为其提供了安全性。但是，该协议仍存在一些安全漏洞。OSPF提供了空认证、明文认证、加密认证三种认证模式，如果OSPF启用空认证，攻击者无需获取密钥即可实现伪造攻击和重放攻击；如果OSPF启用密钥认证（明文认证或加密认证），攻击者无法获得密钥不能进行伪造攻击，但可以进行重放攻击。综上，针对OSPF的安全漏洞问题，我们仍需要进一步的研究，目前已经提出的解决方案主要是利用更合理的密码体制。另外，也有研究者提出了新的研究方向，利用密码体制安全性的同时引入入侵检测技术，更好实现OSPF的安全性[6]。

3 结束语

本文对TCP/IP协议族中目前大型网络中应用最为广泛的路由协议OSPF协议的核心算法进行了介绍，并通过虚拟仪器LabVIEW对其进行了仿真与实现，用以呈现此协议在实际运行时的实际情况，文章最后对OSPF协议的安全性问题进行了分析，该协议目前存在的安全漏洞仍需要进一步的研究与完善。

参考文献：

[1] （美国）特南鲍姆.计算机网络[M].北京：清华大学出版社，2004，8：290-310.

[2] Cory L.Clark.LabVIEW Digital Signal Processing and Digital Communications.The McGraw-Hill Companies[M].Inc.May，2005：23-50.

[3] （美国）史蒂文斯.TCP/IP详解.卷1：协议[M].北京：人民邮电出版社出版.2010.04：50-90.

[4] （美国）史蒂文斯.TCP-IP详解.卷三：TCP事务协议，HTTP，NNTP和UNIX域协议[M].北京：人民邮电出版社出版，2010.

[5] 张芳.OSPF路由协议的研究与实现[D].北京：北京邮电大学图书馆.北京邮电大学，2004，3.

[6] 康威，罗守山，辛阳.OSPF 路由协议安全性研究分析[J].计算机科学技术，2009.endprint

OSPF遵循链路状态路由协议的统一算法，可简单概括为路由器在两种状态下的动作：第一，当路由器完成初始化或网络结构发生变化时，路由器产生链路状态广播数据包，包含路由器上的所有相连链路，即所有端口的状态信息。所有路由器通过“刷新”的方法交换链路状态数据。第二，当网络稳定下来时，即OSPF路由协议收敛下来时，所有的路由器根据其各自的链路状态信息数据库计算各自的路由表，包含路由器到每一个可到达目的地的Cost以及到达该目的地所要转发的下一跳路由[4]。

以上步骤反映了OSPF路由协议的一个特性，也正是链路状态路由协议区别于距离矢量路由协议的一大特性：当网络状态较稳定时，网络中传递的链路状态信息较少，也就是说，此时网络中是比较安静的[5]。

2 OSPF路由协议的仿真与安全性分析

本文通过虚拟设备LabVIEW对OSPF路由协议进行简单的仿真实现。LabVIEW（Laboratory Virtual Instrument Engineering Workbench）全称是实验室虚拟仪器工程平台，是美国国家仪器公司（NI）的创新软件产品。自NI公司1986年正式推出LabVIEW1.0至今，经历了多次改版与完善，目前包括控制与仿真、高级数字信号处理、统计过程控制、模糊控制、PDA和PID等众多附加软件包，可运行于Windows、Linux、Macintosh和Unix等多种平台，已成为目前应用最广、发展最快、功能最强的图形化软件开发继承环境之一。

本文将仿真由四个路由器通过OSPF路由协议组成的系统，该系统的数据输入部分共包括手动输入起点终点及已知路由模块、信息传递模块和连接表二维数组生成模块三部分构成。其中，手动输入起点终点及已知路由模块只需在LabVIEW前面板中输入参数即可，这里不做详细介绍。图2和图3分别列出了信息传递模块和连接表二维数组生成模块的实现流程图。

以上介绍的三大模块完成了OSPF路由协议在LabVIEW虚拟仪器平台的仿真，要通过此系统计算路由器的生成，需要将SPF算法引入该系统。读者可根据前文介绍的SPF算法原理设计最短中继计算模块，通过此模块即可得到系统中路由器的连接方式。

相对于其他一些内部网关路由协议，OSPF有比较复杂的内部状态机，因此攻击发起的复杂度较高。另外，层次化路由结构、可靠的泛洪机制、报文验证机制、报文接收与状态机等OSPF协议本身的保护机制也为其提供了安全性。但是，该协议仍存在一些安全漏洞。OSPF提供了空认证、明文认证、加密认证三种认证模式，如果OSPF启用空认证，攻击者无需获取密钥即可实现伪造攻击和重放攻击；如果OSPF启用密钥认证（明文认证或加密认证），攻击者无法获得密钥不能进行伪造攻击，但可以进行重放攻击。综上，针对OSPF的安全漏洞问题，我们仍需要进一步的研究，目前已经提出的解决方案主要是利用更合理的密码体制。另外，也有研究者提出了新的研究方向，利用密码体制安全性的同时引入入侵检测技术，更好实现OSPF的安全性[6]。

3 结束语

本文对TCP/IP协议族中目前大型网络中应用最为广泛的路由协议OSPF协议的核心算法进行了介绍，并通过虚拟仪器LabVIEW对其进行了仿真与实现，用以呈现此协议在实际运行时的实际情况，文章最后对OSPF协议的安全性问题进行了分析，该协议目前存在的安全漏洞仍需要进一步的研究与完善。

参考文献：

[1] （美国）特南鲍姆.计算机网络[M].北京：清华大学出版社，2004，8：290-310.

[2] Cory L.Clark.LabVIEW Digital Signal Processing and Digital Communications.The McGraw-Hill Companies[M].Inc.May，2005：23-50.

[3] （美国）史蒂文斯.TCP/IP详解.卷1：协议[M].北京：人民邮电出版社出版.2010.04：50-90.

[4] （美国）史蒂文斯.TCP-IP详解.卷三：TCP事务协议，HTTP，NNTP和UNIX域协议[M].北京：人民邮电出版社出版，2010.

[5] 张芳.OSPF路由协议的研究与实现[D].北京：北京邮电大学图书馆.北京邮电大学，2004，3.

[6] 康威，罗守山，辛阳.OSPF 路由协议安全性研究分析[J].计算机科学技术，2009.endprint