Contributions towards survivable network design with uncertain traffic requirements

Abstract

The objective in designing a communications network is to find the most cost efficient network design that specifies hardware devices to be installed, the type of transmission links to be installed, and the routing strategy to be followed. The volume of traffic that will be supported by the network is dependent on the capacity of the hardware devices and the transmission links. Different hardware devices and transmission media will have different capacities and costing structures depending on the choice of vendor. The outputs expected from solving the network design problem are, therefore, the proposed topology with a list of hardware devices and transmission technologies that should be installed at the node and link locations respectively, as well as the proposed routing strategy in order to satisfy all routing restrictions and traffic requirements. In addition to finding the most cost efficient network design, ensuring quality of service, is considered to be another primary objective in planning communication networks. Two issues pertinent to quality of service are robustness and survivability. The contributions of this thesis are, therefore, towards solving the survivable network design problem by taking into account uncertainty in the traffic requirements for general IP networks. The model under consideration makes provision for a detailed representation of hardware devices typically found in SDH transmission networks, and both dynamic and static routing models are presented, with details on appropriate metric inequalities needed for characterising feasible capacities. Details are provided on separation strategies as well as an iterative approach for obtaining solutions that significantly reduces computing times. In order to maintain tractability a problem reduction approach is suggested based on the theory of domination. Computational results are provided based on data collected from an operational network. From the results it is observed that the suggested approach for solving the survivable network design problem with uncertain traffic requirements successfully reduces computing times.