This thesis presents a robust design approach for communication networks that includes capacitation and routing strategy design. Robustness is a mandatory property of core networks to respond to perturbations in network parameters for performance stability and reliable service delivery to different customers. Our proposed design approach is applicable to any system that is modelled by a weighted directed graph. To quantify the robustness measure, we borrow and develop different concepts and properties from Markov chain literatures as well as graph theory survivability discussions. We propose a new robustness definition for Markov chains. The new Markov chain robustness definition has different applications in network design. We define robustness as the sensitivity of the mean first passage time between any two states of the Markov chain. This sensitivity is measured based on the variations of the mean first passage times to the perturbations in transition probabilities. We show that this definition of robustness is related to the sensitivity of the betweenness of a node/state in a Markov chain, which is defined as the number of visits by a random walker that wanders around in the Markov chain according to its transition probabilities. It was shown that for an infinite walk, the proportion of number of visits to the total number of hops converges to the stationary probabilities. Therefore, an analogy can be seen between the well-known condition number and the robustness factor in a Markov chain. We also extend the robustness factor definition to network design problems. We show that the robustness factor can be used as a design criterion. The newly defined robustness factor is a function of the network capacitation, routing and external input and output traffic. We also emphasize the importance of the newly discovered graph theoretic metric, called the Kemeny constant, in network design problems. We discuss that a function of the Kemeny constant and robustness factor limits the sensitivity of network performance parameters to the perturbations in the network.
Identifer | oai:union.ndltd.org:TORONTO/oai:tspace.library.utoronto.ca:1807/35829 |
Date | 07 August 2013 |
Creators | Ghayoori, Armin |
Contributors | Leon-Garcia, Alberto |
Source Sets | University of Toronto |
Language | en_ca |
Detected Language | English |
Type | Thesis |
Page generated in 0.002 seconds