A low complexity shortest path tree restoration scheme for IP networks

Author

Chen, Huan ; Tseng, Po-Kai

Author_Institution

Dept. of Electr. Eng., Nat. Chung Cheng Univ., Chiayi, Taiwan

Volume

14

Issue

6

fYear

2010

fDate

6/1/2010 12:00:00 AM

Firstpage

566

Lastpage

568

Abstract

This letter proposes a novel low complexity shortest path tree restoration scheme to address link cost perturbation problem for link state routing in IP Networks. The proposed scheme can reduce the number of unnecessary shortest path tree recomputations and also provides a low-complexity computation when the Shortest Path Tree (SPT) restoration process executes. The proposed scheme has been designed based on the Network Simplex Method (NSM) and Sensitivity Analysis (SA) techniques to perform the optimality test for the current shortest path tree. The computational overhead is compared with various dynamic schemes over six network benchmarks.

Keywords

IP networks; sensitivity analysis; telecommunication network routing; trees (mathematics); IP Networks; NSM techniques; SA techniques; SPT restoration; link cost perturbation problem; link state routing; network simplex method; optimality test; sensitivity analysis techniques; shortest path tree restoration scheme; Convergence; Costs; Delay; IP networks; Integer linear programming; Network topology; Performance evaluation; Routing protocols; Sensitivity analysis; Vectors; Link state routing, shortest path tree; network simplex method, sensitivity analysis;

fLanguage

English

Journal_Title

Communications Letters, IEEE

Publisher

ieee

ISSN

1089-7798

Type

jour

DOI

10.1109/LCOMM.2010.06.092480

Filename

5474945