Design And Implementation Of A Lightweight Adjacent-State Routing Protocol For Large-scale Networks

With the increase of the size and complexity of computer networks, routing protocols become more and more critical for the scalability of computer networks. Distance-vector routing protocol and link-state routing protocol are two common type of routing protocols widely used in computer networks. Another important routing protocol type is path-vector routing protocol, such as the Border Gateway Protocol (BGP). Other protocols based on exchanging of shortest-path trees, e.g., Topology dissemination Based on Reverse Path Forwarding (TBRPF), Source Tree Adaptive Routing (STAR), can also be classified into this category.This paper analyzes and compares three routing protocol types and discusses their scalabilities. Based on link-state routing algorithm, a new optimized routing algorithm is presented adopting the idea of exchanging of shortest-path trees. When a network topology changes, nodes only send necessary information to their neighbors selectively in the algorithm. Thus the network overhead is reduced.A lightweight adjacency-state routing protocol (LASR) is designed based on the above algorithm for large-scale networks. The data structures, procedures, main modules of the protocol are designed. And the interfaces with Vx Works in implementation are also discussed. Then LASR is compared with ideal link-state algorithm on message overhead using NS2. In LASR, only necessary routing information is exchanged. It reduces the amount of information to be exchanged while maintaining loop-free property. The simulation results show that LASR outperforms ideal link-state algorithm. It reduces control overhead and improves routing efficiency.