Comparison of p-cycles and p-trees in a unified mathematical framework
Tóm tắt
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.
Tài liệu tham khảo
Grover, W. D., & Stamatelakis, D. (2000). Bridging the ring-mesh dichotomy with p-cycles. Proceedings of IEEE/VDE design of reliable communication networks (DRCN 2000) (pp. 92–104). Munich, Germany, April 2000.
Grover, W. (2003). Mesh-based survivable networks: Options and strategies for optical, MPLS, SONET and ATM Networking, Prentice-Hall PTR.
Stamatelakis, D. (1997). Theory and algorithms for preconfiguration of spare capacity in mesh restorable networks, M. Sc. Thesis. University of Alberta, Spring 1997.
Lan, T., Steenhaut, K., & Nowe, A. (2002). Shared backup tree protection in MPλS networks. Proceedings of 8th international conference on communication systems 2002 (Vol. 2, pp. 1237–1241). Brussels, Belgium, November 2002.
Groebbens A., Colle D., Maesschalck S.D., Lievens I., Pickavet M., Demeester P. (2003). Efficient protection in MPλS networks using backup trees: Part one–concepts and heuristics. Photonic Network Communications 6(3): 191–206
Groebbens A., Colle D., Maesschalck S.D., Lievens I., Pickavet M., Demeester P. (2003). Efficient protection in MPλS networks using backup trees: Part two–simulations. Photonic Network Communications 6(3): 207–222
Médard M., Finn S.G., Barry R.A. (1999). Redundant trees for preplanned recovery in arbitrary vertex-redundant or edge-redundant graphs. IEEE/ACM Transactions on Network 7(5): 641–652
Xue G., Chen L., Thulasiraman K. (2002). Delay reduction in redundant trees for pre-planned protection against single link/node failure in 2-connected graphs. Proceedings of GLOBECOM 2002 - IEEE Global Telecommunications Conference 21(1): 2698–2702
Xue G., Chen L., Thulasiraman K. (2003). Quality of service and quality of protection issues in preplanned recovery schemes using redundant trees. IEEE Journal on Selected Areas in Communications 21: 1332–1345
Shah-Heydari, S., & Yang, O. (2001). A tree-based algorithm for protection/restoration in optical mesh networks. Proceedings of Canadian conference on electrical and computer engineering CCECE’2001 (pp. 1169–1173). Toronto, Canada, May 2001.
Shah-Heydari S., Yang O. (2004). Hierarchical protection tree scheme for failure recovery in mesh networks. Photonic Network Communications 7(2): 145–159
Yang, O., & Zhang, Y. (2002). A distributed tree algorithms for WDM network protection/restoration. Proceedings of high speed networks and multimedia communications 5th IEEE international conference (pp. 289–294). Jeju Island, Korea, July 2002.
Shah-Heydari, S. (2007). Self-repairing hierarchical tree-based Link restoration scheme for mesh networks, Ph.D. Thesis. University of Ottawa, Spring 2007.
Tang, F., & Ruan, L. (2005). A protection tree scheme for first-failure protection and second-failure restoration in optical networks. Proceedings of international conference on computer network and mobile computing 2005 (pp. 620–631). Zhangjiajie, China, August 2005.
Schupke, D. (2004). Cycle-based protection for optical transport networks, Ph.D. Dissertation. Technical University of Munich, Fall 2004.