Study And Implement On Routing Computation Approach Of IS-IS Routing Protocol

With the rapid development of the network technology and quick expansion of the network scale, routers have become more important and we have higher requirements on them. Routing protocols are in charge of exchanging information between routers, which essence is to collect the routing information and choose the best path to the entire known network. So the process of routing computation and the organization, management of routing table play a key role in improving router's performance.This thesis proposed a design and implement of IS-IS (Intermediate System-to-intermediate System) routing-computed algorithm, on the base of deeply understand the mechanism of IS-IS routing protocol, which was according to the RFC and ISO standard. According to distributary's characteristic of network prefix, an organization of route table was proposed, which was based on Hash, and then improved it. In the end, we proposed a parallel routing computation, which was aimed at the scalable and multi-route nodes IP routers on core network. The primary contributions of this thesis include the following four parts. Firstly, IS-IS routing protocol is a link-state routing protocol, which used Shortest Path First (SPF) algorithm to compute the routing path. So on the base of deeply understand the SPF algorithm, we design and implement the process of routing computation for IS-IS routing protocol.Secondly, the organization and management of routing table was studied in the paper. Based on analysis of the common organization of routing table, this thesis proposed an organization method, which based Hash, and modified it with experiment according to distributary's characteristic of network prefix. The thesis also analyzed the performance of the algorithm in the theory, and compared it with other algorithms with experiments.Last, a generic scalable IP router that was used in nowadays core network is typically composed of a number of routing nodes. Aimed at this character, by dividing an IS-IS area into a number of disjoint Routing Sub-Area (RSAs), the computation required to calculate the routing table can be divided into multiple independent portions and done by different RNs in parallel. Then we analyzed the feasibility and correctness of this algorithm, Compared to conventional approaches, this approach can have a speedup between n and n2 for within-area link state updates and n for outside-area link state updates, where n is the number of RNs in the router.