DESIGNING HIERARCHICAL SURVIVABLE NETWORKS

As the computer, communication, and entertainment industries begin to integrate phone, cable, and video services and to invest in new techno logies such as fiber-optic cables, interruptions in service can cause considerable customer dissatisfaction and even be catastrophic. In thi s environment, network providers want to offer high levels of service- in both serviceability (e.g., high bandwidth) and survivability (failu re protection)-and to segment their markets, providing better technolo gy and more robust configurations to certain key customers. We study c ore models with three types of customers (primary, primary but critica l, and secondary) and two types of services/technologies (primary and secondary). The network must connect all primary customers using prima ry (high bandwidth) services and, additionally, contain a back-up path connecting the critical primary customers. Secondary customers requir e only single connectivity to other customers and can use either prima ry or secondary facilities. We propose a general multi-tier survivable network design model to configure cost effective networks for this ty pe of market segmentation, When costs are triangular, we show how to o ptimally solve single-tier subproblems, with two critical customers, a s a matroid intersection problem. We also propose and analyze the wors t-case performance of tailored heuristics for several special cases of the two-tier model. Depending upon the particular problem setting, th e heuristics have worst-case performance ratios ranging between 1.25 a nd 2.6. We also provide examples to show that the performance ratios f or these heuristics are the best possible.