Routing reconfiguration in ip networks
Paolo Narvaez, Kai-Yeung Sunny Siu · 2000
This thesis will focus on new methods for efficient IP routing reconfiguration in the presence of topological changes. A fast response to changing network conditions is essential to prevent network routing instability as well as to ensure quality of service parameters. We will identify problems with the current degree of adaptiveness of existing IP routing schemes. New algorithms and protocols will be presented to improve such adaptiveness at different time scales. The first problem is about the recomputation of shortest path trees performed in link-state protocols. This recomputation is generally done by static SPT algorithms. This means that all the previous information on the previous SPT is deleted and needs to be recomputed from scratch. We develop many new and different dynamic shortest path algorithms to perform this recomputation in an efficient way. By using information from the previous tree, these new dynamic algorithms can achieve great savings in computational complexity. Furthermore...