Cross-layer network survivability under multiple cross-layer metrics

Abstract

Given a cross-layer network with logical and physical topologies, the survivable logical topology routing problem is to route each link in the logical layer with a path in the physical topology between the end nodes of a logical link such that the logical topology remains connected after a physical link fails. The mixed-integer linear programming (MILP) formulation to determine such a routing has been considered in a recent paper. Using this formulation as a basic building block, in this paper we present unified MILP formulations to determine a survivable logical topology routing that also satisfies one of four crosslayer metrics: 1) minimizing the number of logical links to be added to guarantee the existence of survivable logical topology routing, 2) maximizing the capacity of the logical topology, 3) maximizing the connectivity of the logical topology after a physical link failure, and 4) maximizing the minimum cross-layer cut. We also provide heuristics for these problems and compare the performance of these heuristics and MILPs using extensive simulations.