SPT-BASED LOCAL LANDMARK SCHEME FOR SHORTEST DISTANCE CALCULATION IN NETWORK ROUTING

Abstract

Shortest distance query is mostly used in large scale networks to achieve fastest routing speed in a network using link state protocols such as OSPF and IS-IS. The Landmark embedding approach is mostly used to get results of such kind of queries. In this approach, set of graph nodes needs to be selected as landmarks and distance from those graph nodes is calculated as an embedding. The precomputed distance from those landmark nodes is calculated as part of the answer shortest distance query using old approach. This approach doesn’t give accurate and error free results. Depending on the factors related to landmark embedding new approach have been proposed to solve these problem as query dependent local landmark scheme. In this approach a local landmarks with respect to queried nodes are identified and shortest distance is calculated which is more accurate than traditional approaches. Based on this theory, better solution is provided which is Shortest Path Tree based on Local Landmark scheme to achieve fastest routing speed in large network.