MODELING AND OPTIMIZATION OF TRANSMISSION NETWORKS

Diploma

ABSTRACT

This dissertation focuses on transmission networks. These networks play an important role in communication (including data and voice), energy transmission (such as gas, electrical, and oil), and micro-electronics among other areas. In this dissertation, we consider two different problems associated with transmission networks: the dynamics on a data communication network and the optimal design of a general transmission network located on a non-uniform landscape. The first two parts of this dissertation develop and apply mathematical models of congested Internet connections and describe possible extensions to network traffic state estimation and network security. The third part looks at an optimal network design problem through a variation on the Euclidean Steiner tree problem, a well-known network optimization problem.

Introduction

This dissertation focuses on transmission networks. These networks play an important role in communication (including data and voice), energy transmission (such as gas, electrical, and oil), and micro-electronics among other areas. In this dissertation, we consider two different problems associated with transmission networks: the dynamics on a data communication network and the optimal design of a general transmission network located on a non-uniform landscape. Chapters two and three develop and apply mathematical models of congested Internet connections and describe possible extensions to network traffic state estimation and network security. Chapter four looks at an optimal network design problem through a variation on the Euclidean Steiner tree problem, a well-known network optimization problem.
In chapter two, we introduce two deterministic models aimed at capturing the dynamics of congested Internet connections. The first model is a continuous-time model that combines a system of differential equations with an impulse, or sudden change in one of the state variables.
The second model is a discrete-time model with a time step that arises naturally from the system. Results from these models show good agreement with the well-known ns network simulator, better than the results of a previous, similar model. This is due in large part to the use of the impulse to reflect the impact of lost data packets. We also discuss the potential use of these models in network traffic state estimation. This chapter is an extended version of a paper [1] that appeared in the Proceedings of the IASTED International Conference on Communications and Computer Networks (CCN ’04).
In chapter three we consider a network consisting of one TCP sender and one non-TCP sender that transmits uniformly sized bursts of packets at regular intervals. The non-TCP flow can represent probing activity of either a diagnostic measurement or attack. Using bifurcation diagrams we study how the network’s behavior changes as a function of the probing frequency.
These diagrams reveal interesting, non-intuitive behavior. We first apply a stochastic version of our continuous-time model to this system. Results from the model show good qualitative agreement with those of the simulator. Next we show that a simpler deterministic version of the model is able to capture many of the main features of the behavior of this network as well. We then further simplify our representation of the system by introducing a piece-wise linear, one-dimensional map that is still able to reproduce much of the dynamics seen in the more complicated model. This map helps explain the structure of the bifurcation diagram, and allows us to directly determine Lyapunov exponents, which give a measure of the system’s predictability. As a result, we are able to more precisely describe and categorize the dynamics, including chaos, exhibited by this network.
Chapter four discusses an algorithm we developed for the optimal design of transmission networks. These networks can be utilized for communication, power transmission, and other applications. We consider a variation of the Euclidean Steiner tree problem in which the space underlying the set of nodes has a specified non-uniform cost structure. This problem is significant in many practical situations, such as laying cable networks, where the cost for laying a cable can be highly dependent on the location and the nature of the area through which it is to be laid. We present a genetic-algorithm-based procedure and apply it to a variety of test cases of this problem. We show that our procedure is able to find optimal or near-optimal solutions in a small fraction of the time taken by an exact algorithm. In addition, we show that because of its novel features, our genetic algorithm outperforms a more traditional genetic algorithm. This chapter is based in part on an earlier paper that appeared in the Proceedings of the INFORMS Computing Society
Conference (ICS ’05).