近十年来，随着计算机网络规模的不断扩大，大型互连网络的迅猛发展，路由技术在网络技术中已逐渐成为关键部分，路由器也随之成为最重要的网络设备。在目前情况下，任何一个有规模的计算机网络，都离不开路由器，否则就无法正常运作和管理。 路由选择协议使路由器可以动态地学习到目的主机和网络的路径。如果没有某种学习新的或失败的网段的路由机制，路由器将不能转发数据报。不管是哪个类型，每一种路由选择协议的目的都是一样的：把数据报送到目的地。 路由算法是指通信子网的节点机在接收到一个分组之后，应选择哪条链路把它输送出去所采用的策略。路由算法类型有确定型路由算法(即静态路由算法)和适应型路由算法(即动态路由算法)。现代计算机网络通常使用动态路由算法，有两种动态算法，即距离矢量路由选择算法(RIP)和链路状态路由选择算法(也称SPF算法)是最常 太原理工大学硕士研究生学位论文见的。 链路状态路由选择算法的主要优点是路由器可以独立地计算出路由;排错较为容易;确保了路由算法的收敛性;报文的长短独立于互连网络中的网络数。因此，SPF算法的性能优于RIP，更适于大规模互连网络的情况。 链路状态路由选择在实际网络中得到了广泛的应用。OSPF协议和工S一IS协议就是两个广泛使用的链路状态路由选择的例子。工S一15协议被用于多种因特网骨干网中和一些数字蜂窝系统;OSPF协议被越来越多地应用于因特网。 OSPF属于内部网关协议，OSPF协议的基本要素包括:LSA、链路状态数据库、可靠的泛洪和路由选择计算。每个路由器都会生成一个或多个LSA，所有路由器产生的LSA形成的集合被称为链路状态数据库。通过可靠的泛洪使每个路由器有一个同样的链路状态数据库。采用链路状态数据库作为输入，每个路由器采用Dijkstra算法，可计算出其自身的IP路由表，从而可以正确地转发IP数据流。 基于四叉堆优先级队列的·Dijkstra算法，是己经在地理信息系统中得以实现的一种算法。本论文通过论证交通网络和Intemet网络在图论上的相同性，从而得出可以在 II太原理工大学硕士研究生学位论文Intemet网络中引用此算法的结论。在论文中不仅从理论上证明一了在点到点的网络，}，新算法的执行效率高于旧算法，而且通过网络仿真模拟路径的选择过程，证明新算法的搜索时间低于旧算法。