Login | Register

New tree-based algorithms for network spare capacity design


New tree-based algorithms for network spare capacity design

Zhang, Yunzan (2004) New tree-based algorithms for network spare capacity design. Masters thesis, Concordia University.

PDF - Accepted Version


Survivable network design has become increasingly important due to the need for reliable communication service. One of its important components is the spare capacity design. Its main purpose is to provide cost-efficient spare capacity reservation at certain survivability level in case of predicted failures. In this thesis, we study various kinds of network survivability techniques and the corresponding algorithms. Subsequently; we introduce our two pre-planned path restoration algorithms for spare capacity design in mesh-like networks. They can get higher utilization of spare capacity and reasonable reaction time. First one is a spanning tree based algorithm with backup parents, which needs much less spare capacity than the well known hierarchical tree algorithm while the restorability is slightly higher or lower. The second algorithm is a cycle tree based algorithm with backup parents and some extra cycle edges. Simulation results show that this algorithm works much better on restorability than the other two algorithms. The time complexities of the two new algorithms are: O ( n 4 ), where n is the total number of nodes in the network. The space complexities are the same too: O ( n 3 )

Divisions:Concordia University > Faculty of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Zhang, Yunzan
Pagination:ix, 73 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science
Thesis Supervisor(s):Harutyunyan, Hovhannes A
ID Code:7831
Deposited By: Concordia University Libraries
Deposited On:18 Aug 2011 18:07
Last Modified:19 Aug 2011 08:10
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page


Downloads per month over past year

Back to top Back to top