Breadcrumb

 
 

New tree-based algorithms for network spare capacity design

Title:

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.

[img]
Preview
PDF - Accepted Version
2591Kb

Abstract

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
Date:2004
Thesis Supervisor(s):Harutyunyan, Hovhannes A
ID Code:7831
Deposited By:Concordia University Libraries
Deposited On:18 Aug 2011 14:07
Last Modified:19 Aug 2011 04: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

Document Downloads

More statistics for this item...

Concordia University - Footer