Design of reconfigurable networks with link failures allowed

Abstract

This thesis investigates three different models of configuring both backbone and logical networks in various reconfigurable networks with unreliable links. In those models, the network reliability issue, as well as the network capacity expansion issue, is analytically treated to take into account routing and rerouting polices desired at each link failure occurrence. Moreover, the models consider economic trade-offs between backbone link capacity expansion cost and inferior network performance penalty in a situation where the associated networks are subject to link failures. The first model considers the problem of configuring backbone and logical networks in a reconfigurable circuit-switched network where network topological states are subject to link failures, which is formulated as a zero-one nonlinear mixed integer programming problem. The objective of the problem is to find jointly the link capacities of the backbone network, the physical paths for logical links on the backbone network, the capacities of the logical links, and the routings on the logical network that minimize the network cost, given the topology of a backbone network and its associated logical network topologies for each network operation (failure) state, and the traffic demand between each origin-destination pair. In the problem, the network cost includes the backbone link capacity expansion cost, the expected lost-call traffic cost and the hop cost. The expected lost-call traffic and the number of hops are incorporated to reflect the network performance in circuit-switched networks. A solution procedure is derived based on a Lagrangean relaxation that generates feasible solutions, together with lower bounds on the optimal objective function value. Two heuristic methods, for generating a good initial primal feasible solution and for improving the upper bounds, are also incorporated into the solution procedure. The solution procedures are exploited and their efficiencies are tested with va...