Dynamic SPT update for multiple link state decrements in network routing |
| |
Authors: | Bin Xiao Jiannong Cao Qin Lu |
| |
Affiliation: | (1) Department of Computing, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong |
| |
Abstract: | Previous approaches to the dynamic updating of Shortest Path Trees (SPTs) have in the main focused on just one link state
change. Not much work has been done on the problem of deriving a new SPT from an existing SPT for multiple link state decrements
in a network that applies link-state routing protocols such as OSPF and IS-IS. This problem is complex because in the process
of updating an SPT there are, firstly, no simple forms of node set to presumable contain all nodes to be updated and, secondly,
multiple decrements can be accumulated to make the updating much harder. If we adopt the updating mechanisms engaged in one
link state change for the case of multiple link state decrements, the result is node update redundancy, as a node changes
several times before it reaches its final state in the new SPT. This paper proposes two dynamic algorithms (MaxR, MinD) for obviating unnecessary node updates by having part nodes updated in a branch on the SPT only after selecting a particular
node from a built node list. The algorithm complexity analysis and simulation results show that MaxR and MinD require fewer node updates during dynamic update procedures than do other algorithms for updating SPT of multiple link state
decrements.
|
| |
Keywords: | Network routing Shortest path tree Dynamic update Multiple link state decrements |
本文献已被 SpringerLink 等数据库收录! |
|