Generalized Survivable Network (GSN) can improve the performance of Optical Flow Switched (OFS) network in short
flow scenario (< 1 second) and enhance the application of OFS network. The design problem of OFS network with GSN
becomes an important problem. In this paper, we propose a solution approach to solve the problem of designing OFS
network with GSN for arbitrary mesh topologies. We demonstrate the performance of our proposed approach by some
One of the main focuses for network planning is on the optimization of network resources required to build a network
under certain traffic demand projection. Traditionally, the inputs to this type of network planning problems are treated as
deterministic. In reality, the varying traffic requirements and fluctuations in network resources can cause uncertainties in
the decision models. The failure to include the uncertainties in the network design process can severely affect the
feasibility and economics of the network. Therefore, it is essential to find a solution that can be insensitive to the
uncertain conditions during the network planning process. As early as in the 1960's, a network planning problem with
varying traffic requirements over time had been studied. Up to now, this kind of network planning problems is still being
active researched, especially for the VPN network design.
Another kind of network planning problems under uncertainties that has been studied actively in the past decade
addresses the fluctuations in network resources. One such hotly pursued research topic is survivable network planning. It
considers the design of a network under uncertainties brought by the fluctuations in topology to meet the requirement
that the network remains intact up to a certain number of faults occurring anywhere in the network. Recently, the authors
proposed a new planning methodology called Generalized Survivable Network that tackles the network design problem
under both varying traffic requirements and fluctuations of topology. Although all the above network planning problems
handle various kinds of uncertainties, it is hard to find a generic framework under more general uncertainty conditions
that allows a more systematic way to solve the problems. With a unified framework, the seemingly diverse models and
algorithms can be intimately related and possibly more insights and improvements can be brought out for solving the
problem. This motivates us to seek a generic framework for solving the network planning problem under uncertainties.
In addition to reviewing the various network planning problems involving uncertainties, we also propose that a unified
framework based on robust optimization can be used to solve a rather large segment of network planning problem under
uncertainties. Robust optimization is first introduced in the operations research literature and is a framework that
incorporates information about the uncertainty sets for the parameters in the optimization model. Even though robust
optimization is originated from tackling the uncertainty in the optimization process, it can serve as a comprehensive and
suitable framework for tackling generic network planning problems under uncertainties.
In this paper, we begin by explaining the main ideas behind the robust optimization approach. Then we demonstrate the
capabilities of the proposed framework by giving out some examples of how the robust optimization framework can be
applied to the current common network planning problems under uncertain environments. Next, we list some practical
considerations for solving the network planning problem under uncertainties with the proposed framework. Finally, we
conclude this article with some thoughts on the future directions for applying this framework to solve other network
Future backbone networks shall require full-survivability and support dynamic changes of traffic demands. The Generalized Survivable Networks (GSN) was proposed to meet these challenges. GSN is fully-survivable under dynamic traffic demand changes, so it offers a practical and guaranteed characterization framework for ASTN / ASON
survivable network planning and bandwidth-on-demand resource allocation4. The basic idea of GSN is to incorporate
the non-blocking network concept into the survivable network models. In GSN, each network node must specify its I/O capacity bound which is taken as constraints for any allowable traffic demand matrix. In this paper, we consider the following generic GSN network design problem: Given the I/O bounds of each network node, find a routing scheme (and the corresponding rerouting scheme under failure) and the link capacity assignment (both working and spare) which minimize the cost, such that any traffic matrix consistent with the given I/O bounds can be feasibly routed and it is single-fault tolerant under the link restoration scheme. We first show how the initial, infeasible formal mixed integer programming formulation can be transformed into a more feasible problem using the duality transformation of the linear program. Then we show how the problem can be simplified using the Lagrangian Relaxation approach. Previous work has outlined a two-phase approach for solving this problem where the first phase optimizes the working capacity assignment and the second phase optimizes the spare capacity assignment. In this paper, we present a jointly optimized framework for dimensioning the survivable optical network with the GSN model. Experiment results show that the jointly optimized GSN can bring about on average of 3.8% cost savings when compared with the separate, two-phase approach. Finally, we perform a cost comparison and show that GSN can be deployed with a reasonable cost.
We introduce a new survivable network concept called the “Generalized Survivable Network” (GSN), which has the special property that it remains survivable no matter how traffic is provisioned dynamically, as long as the input and output constraints at the nodes are fixed. We study a network synthesis problem called the Virtual Topology Mapping Problem (VTMP), which aims at finding the edge capacities for a given physical network topology with the I/O constraints at the nodes that will make it a GSN. Two concepts, tau-matization and sigma-tization are introduced. Tau-matization refers to the conversion of any physical network into a non-blocking network. Sigma-tization refers to the conversion of a multi-edge-connected network into a fully survivable network with the necessary edge capacities. We develop a basic framework for solving the VTMP problem of GSN. We obtain a lower bounding procedure, an upper bounding procedure and a heuristic called MMRA for solving the tau-matization problem. The lower bounding procedure has a very nice analytic form that can be solved by the simplex method in polynomial time. Some experimental results are given. We have shown that the actual cost of developing a GSN with the MMRA heuristic is within 10 - 35% from the absolute lower bound and much less than the tremendous cost that is generally thought would be needed to realize a GSN (a reduction of 85% to 95% from the upper bound). The framework is applicable to ASTN / ASON survivable network planning and bandwidth-on-demand resource allocation.
We consider the problem of designing an optical survivable mesh network with undetermined topology. In this class of problems, only the geographic locations of n network nodes and the traffic demand between these node-pairs are given. The objective is to optimize the total network cost that is characterized by three parameters for each link, namely, the installation cost (α), the bandwidth cost (β) and the equipment cost (γ). We tackle this NP-hard problem by incorporating a modified drop algorithm (MDA) or a genetic algorithm (GA) into the previously developed heuristic called SCAPE. We have previously shown that joint optimization of the topology design, working- and spare-capacity planning using MDA for a 10-node network can result in 20% cost reduction over separate optimization planning. Here, we compare the performance of GA versus MDA with respect to 10 different sets of cost parameters. It is shown that GA slightly outperforms MDA when β is dominant while MDA outperforms GA by about 20% when α is dominant. By eliminating the nodal degree effect, we also show that the joint optimization of MDA with SCAPE result in a 14% net improvement.
Future communication networks will carry many WDM channels at very high bit rate. Thus, it is desirable to avoid electronic switching at the core. The all-optical backbone network can be interconnected by optical cross-connects at strategic locations to allow for flexible capacity provisioning and fault-tolerant rerouting. Such an all-optical core layer nicely decouples the long-term capacity planning problem from the short-term dynamic bandwidth allocation problem which can be better tackled in the electronic domain. An essential requirement for the all-optical core layer is that it must be fully fault-tolerant, otherwise, a single failed link can cause a disaster for the entire network.
We consider the problem of how to allocate the required capacities and spare capacities on a given all-optical core network so as to make the network fully single-fault (or multi-faults) tolerant. The objective function is the total cost of the spare fibers. Based on a given traffic requirement on all source-destination pairs, the optimal bandwidth requirement for each link in the given topology is first computed. We then consider link failures one-by-one for the entire network. For each link failure, we show how spare capacity can be added in other links so as to take advantage of existing spare capacities that have already been added. The algorithm is based on the shortest path routing algorithm and has a polynomial time complexity. Preliminary investigations suggest that the algorithm can give results comparable to those obtained by integer programming.