关键词：路由；OSPF；路由协议；网络
一、概述
最短路径算法应用于生活的方方面面，例如交通路线的规划、日程活动的安排、搜索引擎及网络爬虫等。在计算机网络中，最短路径算法对路由规划算法有重大的意义。路由，代表网络中一台主机访问另一台所要经过的路径，如何规划该路径并使得其具有成本最低、负载均衡，同时具有鲁棒性的特点是路由器算法的核心。
一般来说，配置路由器有两种方式，一种方式是手动方式配置，即网络管理人员通过手动的为每个路由器添加静态路由以使得网络间的各设备实现连通，这种配置方式通常适用于小型的网络，要求网络管理人员完全掌握网络拓扑，同时每次网络拓扑有变化（比如增加新的路由器等），网络管理人员都需要手动的进行配置更新。随着网络规模的日益扩大，这种配置方式逐渐的被路由器自动配置方式所取代，自动配置的核心思想在于，网络中的路由器向邻接路由器发送及接收来自邻接路由设备的周期性路由状态信息，通过不同的路由算法（这是路由器的核心算法）自动地维护、更新本路由器的路由表。
常用的动态路由算法包括距离矢量算法（D-V）及链路状态算法（L-S）。我们熟悉的RIP路由协议就是使用D-V算法，而OSPF协议则使用L-S算法，下面将对这两种路由协议进行解释。
二、距离矢量算法（D-V）原理及RIP协议
距离矢量路由算法的基本思想：
每个路由器维护一个距离矢量（通常是以延时或者跳数作变量）表，然后通过相邻路由器之间的距离矢量通告进行距离矢量表的更新。每个距离矢量表项包括两部分：到达目的结点的最佳输出线路，和到达目的结点所需时间或距离，通信子网中的其它每个路由器在表中占据一个表项，并作为该表项的索引。每隔一段时间，路由器会向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个邻居结点发来的距离表。这样以此类推，经过一段时间后便可将网络中各路由器所获得的距离矢量信息在各路由器上统一起来，这样各路由器只需要查看这个距离矢量表就可以为不同来源分组找到一条最佳的路由。通过上述的路由生成过程，我们不难发现D-V算法采用Bellman-Ford算法寻找最短路径，每一个路由器（对应图中的每一个结点），单纯的接收来自邻居路由器的路由通告（其他路由器计算好的路由表），并以此生成从本路由器到其他各结点的最短路径（进而得到本路由器的路由器表）。
首先，运行RIP协议的路由器将与本路由器直连的路由器视为邻居。
初始阶段，路由信息将通过Request和Response报文在邻居路由器之间共享。RIP协议使用UDP的520端口发送和接收RIP分组。
之后，RIP路由器每隔30秒以广播形式（Repsonse）发送一次路由信息，在邻居之间互传。RIP更新的原则通常可以以下归纳为三条：
若路由表无此路由则接受；
若路由表有此路由，但劣于本路由，则丢弃；
若路由表有此路由，但劣于本路由，但是来源于原来的通告者，则接受。
RIP协议在使用的过程中存在着路由环路的问题，需要有相应的放环机制，典型的设置有split-horizon，poison reverse，trigger updates等。
三、Dijkstra算法
Dijkstra算法是以其发明者荷兰数学家Dijkstra而命名的最短路径算法，该算法成功设计并实现了在有障碍物的两个地点之间找出一条最短路径的高效方法，解决了机器人学中的一个十分关键的问题，即运动路径规划问题。该算法至今仍被广泛应用，被认为是利用“贪心法”(greedy method)设计算法的一个成功范例。
Dijkstra算法使用广度优先搜索算法（Breadth First Search），即由图中某顶点出发，之后依次访问该点的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，使得先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
四、链路状态算法（L-S）原理及OSPF协议
RIP协议（也就是D-V算法）在实际应用过程中存在着路由环路、网络拓扑过小（16跳MAX）的问题，这些问题的存在与算法本身有关。由于RIP协议传递的信息为邻居路由器的路由通告，因此，本路由器对于邻居路由器之外的网络拓扑不了解，只是“道听途说”的方式获取到达某目的网段的路由信息，这种方式造成了路由环路的发生。链路状态算法（L-S）也被称为Dijkstra算法，这是由于每台路由器（对应于网络上的每个结点）获取的不再是邻接路由器计算好的路由信息，取而代之的是邻接路由器关于网络的拓扑知识（LSA），通过本路由器对于这些拓扑信息的整理计算，最终得到本路由的路由表。由于此时路由器获得的是一个整体的网络拓扑而不再限于邻居路由器的范围，因此，L-S算法有效的避免了路由环路的发生。如今普遍使用的OSPF协议（Open Shortest Path First开放式最短路径优先）正是使用了L-S算法，OSPF协议运行过程大致可以分为以下几个阶段（如下图1所示）：
.png)
图1 OSPF协议运行过程
1、每台路由器学习激活的直接相连的网络。
2、每台路由器和直接相连的路由器互交，发送Hello报文，建立邻居关系。
3、每台路由器构建包含直接相连的链路状态的LSA（Link-State Advertisement，链路状态通告）。链路状态通告(LSA)中记录了所有相关的路由器，包括邻路由器的标识、链路类型、带宽等。
4、每台路由器泛洪链路状态通告（LSA）给所有的邻路由器，并且自己也在本地储存邻路由发过来的LSA，然后再将收到的LSA泛洪给自己的所有邻居，直到在同一区域中的所有路由器收到了所有的LSA。每台路由器在本地数据库中保存所有收到的LSA副本，这个数据库被称作“链路状态数据库（LSDB，Link-State Database）”
5、每台路由器基于本地的“链路状态数据库(LSDB)”然后执行“最短路径优先（SPF）”算法，并以本路由器为根，生成一个SPF树，基于这个SPF树计算去往每个网络的最短路径，也就得到了最终的路由表。
对OSPF的运行过程进行简化可得：发Hello报文——建立邻接关系——形成链路状态数据库——SPF算法——形成路由表。（如下图2所示）
.png)
图2 OSPF形成路由表的过程
五、结束语
OSPF作为目前应用最广泛的动态路由协议，其特点就是能够根据网络承载能够自适应最优的路由规划。传统空管业务数据带宽较窄，以透传为主，在传输过程中完全可以利用OSPF的特点，即使在某节点发生故障或堵塞的情况下也能自动更改最优传输路径以达到负载均衡的目的，增加传输系统的可靠性。
参考文献
【1】王恒清，宋如敏最短路径算法Dijkstra算法在路由选择中的作用 计算机与网络 ：223
【2】吴军数学之美第二版 人民邮电出版社 2014年11月：89-90
【3】张子言常用算法深入学习实录 电子工业出版社 2013年8月：140-160
论文作者:赵林
论文发表刊物:《科学与技术》2019年第20期
论文发表时间:2020/4/28
标签：路由器论文; 算法论文; 路由论文; 网络论文; 路径论文; 最短论文; 结点论文; 《科学与技术》2019年第20期论文;