File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: ILP-based design of survivable broadcast trees

TitleILP-based design of survivable broadcast trees
Authors
KeywordsBlue/red tree
Integer linear programming (ILP)
Survivable broadcast trees
Issue Date2009
PublisherIEEE.
Citation
2009 International Conference On High Performance Switching And Routing, Hpsr 2009, 2009 How to Cite?
AbstractWe study survivable broadcast in high-speed networks against a single link/node failure. We follow the classic approach of blue/red tree [1] to construct a pair of spanning trees (i.e. a blue tree and a red tree) such that the connectivity between the root and an arbitrary node is ensured (via at least one tree) in the presence of a single link/node failure. To ensure that the blue and red trees are constructed in a cost-efficient way, heuristic algorithms have been designed to minimize the cost involved in tree construction. In this paper, we tackle the same problem but resorting to Integer Linear Programming (ILP) for optimal solutions. Two efficient ILPs are formulated, one for protecting against single link failure (MinCost-E) and the other for node failure (MinCost-V). Numerical results show that our ILPs can generate optimal solutions in relatively short amount of time. As compared with the existing heuristic algorithms, we observe a significant improvement in performance. © 2009 IEEE.
DescriptionProceedings of the IEEE Workshop on High Performance Switching and Routing, 2009, p. 1-6
Persistent Identifierhttp://hdl.handle.net/10722/62000
ISBN
References

 

DC FieldValueLanguage
dc.contributor.authorMao, Men_HK
dc.contributor.authorWu, Ben_HK
dc.contributor.authorYeung, KLen_HK
dc.date.accessioned2010-07-13T03:51:51Z-
dc.date.available2010-07-13T03:51:51Z-
dc.date.issued2009en_HK
dc.identifier.citation2009 International Conference On High Performance Switching And Routing, Hpsr 2009, 2009en_HK
dc.identifier.isbn978-1-4244-5174-6-
dc.identifier.urihttp://hdl.handle.net/10722/62000-
dc.descriptionProceedings of the IEEE Workshop on High Performance Switching and Routing, 2009, p. 1-6en_HK
dc.description.abstractWe study survivable broadcast in high-speed networks against a single link/node failure. We follow the classic approach of blue/red tree [1] to construct a pair of spanning trees (i.e. a blue tree and a red tree) such that the connectivity between the root and an arbitrary node is ensured (via at least one tree) in the presence of a single link/node failure. To ensure that the blue and red trees are constructed in a cost-efficient way, heuristic algorithms have been designed to minimize the cost involved in tree construction. In this paper, we tackle the same problem but resorting to Integer Linear Programming (ILP) for optimal solutions. Two efficient ILPs are formulated, one for protecting against single link failure (MinCost-E) and the other for node failure (MinCost-V). Numerical results show that our ILPs can generate optimal solutions in relatively short amount of time. As compared with the existing heuristic algorithms, we observe a significant improvement in performance. © 2009 IEEE.en_HK
dc.languageengen_HK
dc.publisherIEEE.-
dc.relation.ispartof2009 International Conference on High Performance Switching and Routing, HPSR 2009en_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.rightsIEEE Workshop on High Performance Switching and Routing Proceedings. Copyright © IEEE.-
dc.rights©2009 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.-
dc.subjectBlue/red treeen_HK
dc.subjectInteger linear programming (ILP)en_HK
dc.subjectSurvivable broadcast treesen_HK
dc.titleILP-based design of survivable broadcast treesen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=978-1-4244-5174-6&volume=&spage=1&epage=6&date=2009&atitle=ILP-based+design+of+survivable+broadcast+trees-
dc.identifier.emailYeung, KL:kyeung@eee.hku.hken_HK
dc.identifier.authorityYeung, KL=rp00204en_HK
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1109/HPSR.2009.5307443en_HK
dc.identifier.scopuseid_2-s2.0-74949100962en_HK
dc.identifier.hkuros163996en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-74949100962&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.spage1-
dc.identifier.epage6-
dc.identifier.scopusauthoridMao, M=35325266400en_HK
dc.identifier.scopusauthoridWu, B=24605804500en_HK
dc.identifier.scopusauthoridYeung, KL=7202424908en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats