OSPF Algorithm Based On Quadheap PRI Queue

In the past ten years, with the constant enlargement of the computer network scale and quickly development of the large-scale internet, route technology has gradually become the key part of the network technologies.Router becomes the most important network equipment too. At present, any scaled computer network can't work without router. Otherwise it is unable to operate and manage normally.Routing protocol can make the router find a way dynamically to purpose host and network. Without route mechanism which can study new or failed section, router can't transmit datagram. No matter which type it belongs to, the purpose of routing protocol is the same: send datagram to destination.Route algorithm is a strategy that can send the datagram to a proper path after the node machine of the communication subnet receives data. Route algorithm includes deterministic algorithm (namely static routing algorithm) and adaptive algorithm (namely dynamic routing algorithm). Modern network usually uses dynamic routing algorithm and there are two kinds of dynamic routing algorithms: distance vector routing algorithm (RIP ) and link- state routing algorithm (call SPF algorithm too ),which are most common.Major advantage of link-state routing algorithm is thatrouter can independently calculate route; It is comparatively easy to devoid and get rid of mistakes; It guarantes the astringency of the route algorithm; The size of datagram is independent of the network figure. So, the performance of SPF algorithm is superior to RIP, and it is more suitable for large-scale internet.Link-state routing protocol is widely used in practicl network. OSPF protocol and IS-IS protocol are two examples that used link-state routing. IS-IS protocol is widely used in some digital honeycomb systems and many kinds of backbone network in Internet; OSPF protocol is more and more applied to Internet.OSPF is a interior gateway protocol.The basic elements of OSPF protocol includes: LSA, link-state database , reliable flooding and routing. Each router can produce one or more LSAs and the set that all LSA produced by router is link-state database. Each router has a same link-state database by reliable flooding. After inputting link-state database, every router can calculate its own IP route form by Dijkstra algorithm, thus can transmit IP dataflow correctly .Dijkstra algorithm based on quadheap PRI has already been realized in geography information system. The paper draws the conclusion that Dijkstra algorithm based on quadheap PRI can be quoted in Internet by proving similarity in graph theory between traffic network and Internet network,. The conclusion not only proved that execution efficiency of new algriothm is higher than the old one in point-to-point network, but also proved that the' search time of the new algorithm is lower than the old one by simulating route in network emulation,...