| Popis: |
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. |
