Survivable Mapping of Virtual Topologies for Double-Node Failure
| Autor: | Norbert Radics, Lajos Bajzik, Zsolt Lakatos |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Computer Networks and Communications
business.industry Computer science Heuristic (computer science) Distributed computing Node (networking) Logical topology Physical layer Network topology Computer Science Applications Network planning and design Algorithm design Electrical and Electronic Engineering business Integer programming Software Computer network |
| Zdroj: | IEEE/ACM Transactions on Networking. 23:1903-1916 |
| ISSN: | 1558-2566 1063-6692 |
| Popis: | In multilayer network design, the mapping of logical links onto the physical layer plays a critical role in failure tolerance of the network. Since a single link or node failure in the physical layer can bring several logical links down, it is important to find a mapping of logical links on the physical layer that ensures the logical topology remains connected in case of physical failures. A mapping that preserves the logical-layer connectivity in case of any given failure of the physical layer is called survivable. The problem of finding a survivable mapping for single-link failure for a given logical network over a given physical network is known to be NP-complete. We show that it is also true for both single- and double-node failure. Thus, for practical applications, only scalable heuristic methods can be used. In the literature, efficient and scalable combinatorial mapping algorithms were proposed for single- or multiple-link failures and single-node failures of the physical network, which are based on specific properties of the network graphs. As a new result, in this paper we present a graph-theoretic heuristic method to find a survivable mapping for double-node failures. We also present an integer linear programming (ILP) model and evaluate the efficiency of the algorithm by comparing it to the ILP method. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|