图论结课小论文.pdfVIP

图论及其应用结课小论文 题目：Dijkstra 算法在OSPF 协议中的应用 姓 名 学 院 班 级 学 号 授课教师 2016 年 01 月 Dijkstra 算法在OSPF 协议中的应用 在网络设备中路由器实现了网络的互联，其最基本的功能是路由与交换，路 由即是寻找数据包传输的最佳路径的过程，路由器将寻找到的路径以表的形式存 储在路由表中，当路由器需要转发数据包时就通过查找路由表来完成。 OSPF(Open Shortest Path First 开放式最短路径优先）是一个运行在路由器上 的内部网关协议，功能之一就是在单一自治系统内寻找路由。该协议用著名 Dijkstra 算法来计算最短路径树。 Dijkstra 算法在OSPF 协议中又被称为SPF （Shortest Path First ）算法即最短路 径优先算法。各个路由器由SPF 算法计算出以自己为起点的最短生成树从而得到 自己的路由表。 由此可见，对应于图论中的数学模型：每个路由器相当于一张图中的各个结 点，每个点都会分配一个唯一的 IP 地址来标识。路由器之间的连接情况相当于 图中的边，每条边的权重相当于相链接的路由器之间的开销，在OSPF 协议中开 销称为cost ，其计算方法为：cos t 100*106 / bps ，bps 表示链路带宽，与网络时 延和吞吐量有关。也即是说，OSPF 的cost 与链路的带宽成反比，带宽越高，cost 越小，表示到目的路由器的距离越近。 上图所示的是某台OSPF 路由器建立路由表的过程。每个运行 OSPF 协议的 路由器都会周期性的维护一个链路状态数据库，其中包含了它相邻的路由器的IP 地址和到达的开销等信息。一旦路由器收到它所相邻的所有路由器的信息就会使 用Dijkstra 的最短路径优先(SPF)算法创建一个SPF 树。随后根据SPF 树，使用通 向每个路由器的最佳路径填充IP 路由表。 例如下图所示的两幅简易图，第一幅图表示网络连接情况，图中数字表示链 路的开销，其中每条链路的开销与数据包传递的方向也有关比如RB 到 RE 的开 销为10，RE 到RB 的开销为2，第二幅图以表的形式来体现图一，当每个路由器 通过初期的信息交流都建立起这张表之后路由器就开始运行基于Dijkstra 算法的 代码来计算以各自为起点到其他各个路由器的最短路。为了方便起见将用于标识 每个路由器的IP 地址用RA~RH 来代替了。 为了加深对该算法的理解与应用，使用了MATLAB 对dijkstra 算法进行了代 码实现，简单模拟了一下上述过程。 设所求解的图的权值矩阵为 W=[0 50 inf 40 25 10 50 0 15 20 inf 25 inf 15 0 10 20 inf 40 20 10 0 10 25 25 inf 20 10 0 55 10 25 inf 25 55 0]; 以表的形式体现为 1 2 3 4 5 6 结点 ○ ○ ○ ○ ○ ○  1 0 50 40 25 10 ○  2 50 0 15 20