Comparison of p-cycles and p-trees in a unified mathematical framework
Autor: | Wayne D. Grover, Aden Grue |
---|---|
Rok vydání: | 2007 |
Předmět: |
Optimal design
Mathematical optimization Network Access Protection Computer Networks and Communications Computer science Rank (computer programming) Network science Tree (graph theory) Atomic and Molecular Physics and Optics Field (computer science) Hardware and Architecture Selection (linguistics) Electrical and Electronic Engineering Integer programming Software |
Zdroj: | Photonic Network Communications. 14:123-133 |
ISSN: | 1572-8188 1387-974X |
DOI: | 10.1007/s11107-007-0059-0 |
Popis: | As high-speed networks grow in capacity, network protection becomes increasingly important. Recently, following interest in p-cycle protection, the related concept of p-trees has also been studied. In one line of work, a so-called “hierarchical tree” approach is studied and compared to p-cycles on some points. Some of the qualitative conclusions drawn, however, apply only to p-cycle designs consisting of a single Hamiltonian p-cycle. There are other confounding factors in the comparison between the two, such as the fact that, while the tree-based approach is not 100% restorable, p-cycles are. The tree and p-cycle networks are also designed by highly dissimilar methods. In addition, the claims regarding hierarchical trees seem to contradict earlier work, which found pre-planned trees to be significantly less capacity-efficient than p-cycles. These contradictory findings need to be resolved; a correct understanding of how these two architectures rank in terms of capacity efficiency is a basic issue of network science in this field. We therefore revisit the question in a definitive and novel way in which a unified optimal design framework compares minimum capacity, 100% restorable p-tree and p-cycle network designs. Results confirm the significantly higher capacity efficiency of p-cycles. Supporting discussion provides intuitive appreciation of why this is so, and the unified design framework contributes a further theoretical appreciation of how pre-planned trees and pre-connected cycles are related. In a novel further experiment we use the common optimal design model to study p-cycle/p-tree hybrid designs. This experiment answers the question “To what extent can a selection of trees compliment a cycle-based design, or vice-versa?” The results demonstrate the intrinsic merit of cycles over trees for pre-planned protection. |
Databáze: | OpenAIRE |
Externí odkaz: |