This thesis presents network design and operations algorithms suitable for use in
an autonomic management system for communication networks with emphasis on
network robustness. We model a communication network as a weighted graph and
we use graph-theoretical metrics such as network criticality and algebraic connectivity
to quantify robustness. The management system under consideration is composed of
slow and fast control loops, where slow loops manage slow-changing issues of the
network and fast loops react to the events or demands that need quick response.
Both of control loops drive the process of network management towards the most
robust state.
We fist examine the topology design of networks. We compare designs obtained
using different graph metrics. We consider well-known topology classes including
structured and complex networks, and we provide guidelines on the design and simplification of network structures. We also compare robustness properties of several
data center topologies. Next, the Robust Survivable Routing (RSR) algorithm is presented to assign working and backup paths to online demands. RSR guarantees 100%
single-link-failure recovery as a path-based survivable routing method. RSR quanti es each path with a value that represents its sensitivity to incremental changes in
external traffic and topology by evaluating the variations in network criticality of the
network. The path with best robustness (path that causes minimum change in total
network criticality) is chosen as primary (secondary) path.
In the last part of this thesis, we consider the design of robust networks with
emphasis on minimizing vulnerability to single node and link failures. Our focus
in this part is to study the behavior of a communication network in the presence
of node/link failures, and to optimize the network to maximize performance in the
presence of failures. For this purpose, we propose new vulnerability metrics based on
the worst case or the expected value of network criticality or algebraic connectivity
when a single node/link failure happens. We show that these vulnerability metrics
are convex (or concave) functions of link weights and we propose convex optimization problems to optimize each vulnerability metric. In particular, we convert the
optimization problems to SDP formulation which leads to a faster implementation
for large networks.
| Identifer | oai:union.ndltd.org:TORONTO/oai:tspace.library.utoronto.ca:1807/32667 |
| Date | 20 August 2012 |
| Creators | Bigdeli, Alireza |
| Contributors | Leon-Garcia, Alberto |
| Source Sets | University of Toronto |
| Language | en_ca |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0019 seconds