Design issues in communications networks : reliability and traffic analysis

Citation

Yu, Zhong (1997) Design issues in communications networks : reliability and traffic analysis. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/pa8m-ay72. https://resolver.caltech.edu/CaltechETD:etd-03192008-090303

Abstract

This thesis aims to investigate two rather separate issues: network reliability and traffic analysis. The first concerns the reliability for unreliable systems, including communications networks with possible link failures, and more general fault-tolerant systems. The second concerns the traffic characteristics specifically in ATM networks with respect to the performance of statistical multiplexers.

One way in which we studied the reliability issue is via mean time to failure (MTTF) which considers systems that have component failures and repairs with exponential distributions. Such systems can be modeled by continuous-time discrete- state Markov chains. We investigated the MTTF from a more general framework of fault-tolerant systems (FTS), and developed two systematic approaches, the allpath-weight approach and the signal-flow-graph approach, to compute the MTTF. We also derived a simple asymptotic formula for estimating the MTTF, and obtained asymptotically the optimal networks in terms of the MTTF.

The other way in which we studied the reliability issue is via reliability polynomials for a system with component failures with certain fixed probability that is independent of time, but a function of the size of the system. No repair is allowed. We modeled such systems by random graphs, and analyzed reliability polynomials in a framework of random graph theory. We specifically focused on certain regular random graphs and analyzed the evolution of the regular random graphs, by showing a transition phenomenon when such a regular random graph evolves from edge probability zero to probability one because of the expansion of graph size, and identified its threshold function. Our work extends the study of the evolution of random graphs to regular random graphs which do not appear in the literature of random graphs, and our results are generalizations of some famous previously known results in random graph theory.

As for the second issue of traffic analysis in ATM networks, we first studied, via the approach of generating functions, Markov on-off traffic and the performance behavior of a statistical multiplexer with such traffic. We developed a heuristic procedure which allowed us to compute the expected buffer occupancy of a statistical multiplexer with Markov on-off traffic, and obtained closed form formulas showing that the expected buffer occupancy under such traffic not only depends on the incoming traffic intensity, but also largely on the burstiness of incoming traffic. The expected buffer occupancy becomes unbounded with large enough traffic burstiness, even though the traffic intensity is small. These results showed that burstiness control of traffic was very critical in designing ATM networks.

We then introduced a class of burst-constrained traffic sources, the periodic interchangeable (PI) traffic, and applied generalized Ballot theorems to analyze the buffer occupancy in a statistical multiplexer with PI traffic. We derived closed form formulas for survivor functions, expected buffer occupancy, and simple asymptotic formula that can be used as a rule of thumb for dimensioning buffer size in designing a statistical multiplexer. The results obtained could shed light on the study of worst case performance of statistical multiplexers for burst-constrained traffic sources in ATM networks.

Thesis Files