Please use this identifier to cite or link to this item:
Title: Dynamic SPT update for multiple link state decrements in network routing
Authors: Xiao, B 
Cao, J 
Lu, Q 
Keywords: Dynamic update
Multiple link state decrements
Network routing
Shortest path tree
Issue Date: 2008
Source: Journal of supercomputing, 2008, v. 46, no. 3, p. 237-256 How to cite?
Journal: Journal of Supercomputing 
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.
ISSN: 0920-8542
DOI: 10.1007/s11227-007-0164-y
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record


Last Week
Last month
Citations as of Oct 22, 2018

Page view(s)

Last Week
Last month
Citations as of Oct 22, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.