Title :
Generalized Survivable Network
Author :
Ho, Kwok Shing ; Cheung, Kwok Wai
Author_Institution :
Chinese Univ. of Hong Kong, Hong Kong
Abstract :
Two important requirements for future backbone networks are full survivability against link failures and dynamic bandwidth provisioning. We demonstrate how these two requirements can be met by introducing 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. A rigorous mathematical framework for designing the GSN is presented. In particular, we focus on the GSN capacity planning problem, which finds the edge capacities for a given physical network topology with the input/output constraints at the nodes. We employ fixed single-path routing which leads to wide-sense nonblocking GSNs. We show how the initial, infeasible formal mixed integer linear programming formulation can be transformed into a more feasible problem using the duality transformation. A procedure for finding the realizable lower bound for the cost is also presented. A two-phase approach is proposed for solving the GSNCPP. We have carried out numerical computations for ten networks with different topologies and found that the cost of a GSN is only a fraction (from 39% to 97%) more than the average cost of a static survivable network. The framework is applicable to survivable network planning for ASTN/ASON, VPN, and IP networks as well as bandwidth-on-demand resource allocation.
Keywords :
IP networks; integer programming; linear programming; resource allocation; telecommunication network planning; telecommunication network routing; telecommunication network topology; virtual private networks; ASTN-ASON; GSN; IP networks; VPN; backbone networks are full survivability against; capacity planning; dynamic bandwidth provisioning; generalized survivable network; link failures; mixed integer linear programming; network planning; network topology; resource allocation; single-path routing; Bandwidth; Capacity planning; Computer networks; Costs; Mixed integer linear programming; Network topology; Routing; Spine; Telecommunication traffic; Virtual private networks; ASON; ASTN; IP network; VPN; network design; nonblocking network; survivable network;
Journal_Title :
Networking, IEEE/ACM Transactions on
DOI :
10.1109/TNET.2007.893889