Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/19591
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.
URI: http://hdl.handle.net/10397/19591
ISSN: 0920-8542
DOI: 10.1007/s11227-007-0164-y
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

2
Last Week
0
Last month
0
Citations as of Sep 15, 2017

Page view(s)

41
Last Week
4
Last month
Checked on Sep 25, 2017

Google ScholarTM

Check

Altmetric



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