Distributed Research & Implementation Of OSPF Protocol

In this paper, we deal with the problem of a distributed implementation of OSPF protocol to T bit router with scalable architecture. Based on the analysis and comparison on the normal design methods of distributing system, we propose a wholely distributed implementation method of OSPF based on WARR(With-Area-Routing-Region), lay an Emphasis on the parallel routing table computation and the design of the link state database, and describe the OSPF protocol processing in detail. In the chapter four we give a software implementation of our design. The test of implementation proves that our design is feasible and correct. The performance analysis showes that our design satifies the requirement of Tbit router. The main work of this paper is as follows:Firstly, we analyze the characteristic of Tbit router architecture and the deficiencies of centralized implementation of OSPF protocol, and draw the conclusion that Tbit router leads to the use of distributed routing protocol. By analyzing the normal parallel method and comparing parallel routing table computation based WARR and Jesper's parallel Dijkstra algorithm, propose a scheme of distributed implementation of OSPF protocol.Secondly, based on the WARR, we propose a wholely distributed implementation method of OSPF. In this method,each routing node runs a same OSPF dameon and they do the routing computation and protocol processing independently based on their own WARR. OSPF damenoas commuciate by message delivery, with little semaphores needed to do the synchronization work between the dameons, and so we can get highly parallel degree between the dameons. Also we design a link state database storage scheme of distributed storage and redundance backup which ease the implementation of the routing table computation in routing node and synchronization between neighbor routers.Thirdly, we study an efficient parallel routing table computation algorithm, we describe Xipeng's parallel routing table computation algorithm with formal method, and improve the dividing algorithm of area. The automatic finding and maintenance can be completed in the division. The performance analysis showes the speedup comparing this method with controlized processing is N to N2, and N is the sum of routing node.Fourthly, we propose a load balance policy of OSPF parellel implementation for balancing the loades between the routing nodes. In order to avoid too heavy load of the routing node computing routing table in some circumstance, we use a maneuver of load balance between the routing nodes computing routing table and nodes not computing routing table. So the routingnode computing routing table doesn't exist the things with too heavy load in the long term because of routing computation.Fifthly, we imeplement the scheme of the wholely distributed OSPF, give the modules dividing policy and design the interfaces between them. At the same time, we build a real environment to test our scheme, and the result proves our scheme's correctness and feasibility. What's more, we give a theoretical analysis on performance.