File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: ILP formulations for p-cycle design without candidate cycle enumeration

TitleILP formulations for p-cycle design without candidate cycle enumeration
Authors
KeywordsInteger linear program (ILP)
P-cycle (preconfigured protection cycle)
Protection
Wavelength division multiplexing (WDM) mesh networks
Issue Date2010
PublisherI E E E. The Journal's web site is located at http://www.comsoc.org/livepubs/net
Citation
Ieee/Acm Transactions On Networking, 2010, v. 18 n. 1, p. 284-295 How to Cite?
AbstractThe concept of p-cycle (preconfigured protection cycle) allows fast and efficient span protection in wavelength division multiplexing (WDM) mesh networks. To design p-cycles for a given network, conventional algorithms need to enumerate cycles in the network to form a candidate set, and then use an integer linear program (ILP) to find a set of p-cycles from the candidate set. Because the size of the candidate set increases exponentially with the network size, candidate cycle enumeration introduces a huge number of ILP variables and slows down the optimization process. In this paper, we focus on p-cycle design without candidate cycle enumeration. Three ILPs for solving the problem of spare capacity placement (SCP) are first formulated. They are based on recursion, flow conservation, and cycle exclusion, respectively. We show that the number of ILP variables/constraints in our cycle exclusion approach only increases linearly with the network size. Then, based on cycle exclusion, we formulate an ILP for solving the joint capacity placement (JCP) problem. Numerical results show that our ILPs are very efficient in generating p-cycle solutions. © 2009 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/139270
ISSN
2015 Impact Factor: 2.186
2015 SCImago Journal Rankings: 1.795
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorWu, Ben_HK
dc.contributor.authorYeung, KLen_HK
dc.contributor.authorHo, PHen_HK
dc.date.accessioned2011-09-23T05:47:48Z-
dc.date.available2011-09-23T05:47:48Z-
dc.date.issued2010en_HK
dc.identifier.citationIeee/Acm Transactions On Networking, 2010, v. 18 n. 1, p. 284-295en_HK
dc.identifier.issn1063-6692en_HK
dc.identifier.urihttp://hdl.handle.net/10722/139270-
dc.description.abstractThe concept of p-cycle (preconfigured protection cycle) allows fast and efficient span protection in wavelength division multiplexing (WDM) mesh networks. To design p-cycles for a given network, conventional algorithms need to enumerate cycles in the network to form a candidate set, and then use an integer linear program (ILP) to find a set of p-cycles from the candidate set. Because the size of the candidate set increases exponentially with the network size, candidate cycle enumeration introduces a huge number of ILP variables and slows down the optimization process. In this paper, we focus on p-cycle design without candidate cycle enumeration. Three ILPs for solving the problem of spare capacity placement (SCP) are first formulated. They are based on recursion, flow conservation, and cycle exclusion, respectively. We show that the number of ILP variables/constraints in our cycle exclusion approach only increases linearly with the network size. Then, based on cycle exclusion, we formulate an ILP for solving the joint capacity placement (JCP) problem. Numerical results show that our ILPs are very efficient in generating p-cycle solutions. © 2009 IEEE.en_HK
dc.languageengen_US
dc.publisherI E E E. The Journal's web site is located at http://www.comsoc.org/livepubs/neten_HK
dc.relation.ispartofIEEE/ACM Transactions on Networkingen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.rightsIEEE/ACM Transactions on Networking. Copyright © IEEE.-
dc.rights©2010 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.subjectInteger linear program (ILP)en_HK
dc.subjectP-cycle (preconfigured protection cycle)en_HK
dc.subjectProtectionen_HK
dc.subjectWavelength division multiplexing (WDM) mesh networksen_HK
dc.titleILP formulations for p-cycle design without candidate cycle enumerationen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1063-6692&volume=18&issue=1&spage=284&epage=295&date=2010&atitle=ILP+formulations+for+p-cycle+design+without+candidate+cycle+enumeration-
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/TNET.2009.2025769en_HK
dc.identifier.scopuseid_2-s2.0-77249151401en_HK
dc.identifier.hkuros195072en_US
dc.identifier.hkuros163986-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-77249151401&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume18en_HK
dc.identifier.issue1en_HK
dc.identifier.spage284en_HK
dc.identifier.epage295en_HK
dc.identifier.isiWOS:000274732400022-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridWu, B=35231472500en_HK
dc.identifier.scopusauthoridYeung, KL=7202424908en_HK
dc.identifier.scopusauthoridHo, PH=7402211578en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats