Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Telecommunication Systems
Erschienen in: Telecommunication Systems 1/2016

01.05.2016

Multi-commodity k-splittable survivable network design problems with relays

verfasst von: Ozgur Kabadurmus, Alice E. Smith

Erschienen in: Telecommunication Systems | Ausgabe 1/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The network design problem is a well known optimization problem with applications in telecommunication, infrastructure designs and military operations. This paper devises the first formulation and solution methodology for the multi-commodity k-splittable two-edge disjoint survivable network design problem with capacitated edges and relays. This problem realistically portrays telecommunications network design but has not been solved previously due to its computational difficulty. Edge capacity is considered as either a discrete or a continuous variable. An exact method and a practical heuristic method are presented, and computational results are discussed.
Vorheriger Artikel Secure and efficient data transmission in the Internet of Things
Nächster Artikel GREEN protocol: gradient based energy efficient routing with network coding capacity

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
1.
Altin, A., Belotti, P., & Pinar, M. C. (2010). OSPF routing with optimal oblivious performance ratio under polyhedral demand uncertainty. Optimization and Engineering, 11(3), 395–422.CrossRef
2.
Atamturk, A., & Rajan, D. (2002). On splittable and unsplittable flow capacitated network design arc-set polyhedra. Mathematical Programming, 92(2), 315–333.CrossRef
3.
Atamturk, A., & Rajan, D. (2008). Partition inequalities for capacitated survivable network design based on directed p-cycles. Discrete Optimization, 5(2), 415–433.CrossRef
4.
Azodolmolky, S., Angelou, M., Tomkos, I., Panayiotou, T., Ellinas, G., & Antoniades, N. (2012). Impairment-aware optical networking: A survey. In N. N. Antoniades, G. Ellinas, & I. Roudas (Eds.), WDM Systems and Networks, Optical Networks (pp. 443–479). New York: Springer.CrossRef
5.
Azodolmolky, S., Klinkowski, M., Marin, E., Careglio, D., Pareta, J. S., & Tomkos, I. (2009). A survey on physical layer impairments aware routing and wavelength assignment algorithms in optical networks. Computer Networks, 53(7), 926–944.CrossRef
6.
Beshir, A., Kuipers, F., Orda, A., & Van Mieghem, P. (2012). Survivable routing and regenerator placement in optical networks. In 4th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT) (pp. 684–690).
7.
Cabral, E., Erkut, E., Laporte, G., & Patterson, R. (2007). The network design problem with relays. European Journal of Operational Research, 180(2), 834–844.CrossRef
8.
Chen, S., Ivana, L., & Raghavan, S. (2010). The regenerator location problem. Networks, 55(3), 205–220.
9.
Cherubini, D., Fanni, A., Mereu, A., Frangioni, A., Murgia, C., Scutella, M., & Zuddas, P. (2011). Linear programming models for traffic engineering in 100% survivable networks under combined IS-IS/OSPF and MPLS-TE. Computers & Operations Research, 38(12), 1805–1815.
10.
Costa, A., Cordeau, J. F., & Gendron, B. (2009). Benders, metric and cutset inequalities for multicommodity capacitated network design. Computational Optimization and Applications, 42(3), 371–392.CrossRef
11.
Dahl, G., & Stoer, M. (1998). A cutting plane algorithm for multicommodity survivable network design problems. INFORMS Journal on Computing, 10(1), 1–11.CrossRef
12.
Dey, S. K., & Adhya, A. (2011). Dynamic connection allocation in WDM network with limited grooming and regeneration facilities. High Capacity Optical Networks and Enabling Technologies (HONET), 2011, 65–70.CrossRef
13.
Frangioni, A., & Gendron, B. (2009). 0–1 reformulations of the multicommodity capacitated network design problem. Discrete Applied Mathematics, 157(6), 1229–1241.CrossRef
14.
Gagnaire, M., & Zahr, S. (2009). Impairment-aware routing and wavelength assignment in translucent networks: State of the art. IEEE Communications Magazine, 47(5), 55–61.CrossRef
15.
Garcia-Manrubia, B., Pavon-Marino, P., Aparicio-Pardo, R., Klinkowski, M., & Careglio, D. (2011). Offline impairment-aware RWA and regenerator placement in translucent optical networks. Journal of Lightwave Technology, 29(3), 265–277.CrossRef
16.
Garg, M., & Smith, J. (2008). Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios. Omega, 36(6), 1057–1071.CrossRef
17.
Huang, S., Martel, C., & Mukherjee, B. (2011). Survivable multipath provisioning with differential delay constraint in telecom mesh networks. IEEE/ACM Transactions on Networking, 19(3), 657–669.CrossRef
18.
Katrinis, K., & Tzanakaki, A. (2011). On the dimensioning of WDM optical networks with impairment-aware regeneration. IEEE/ACM Transactions on Networking, 19(3), 735–746.CrossRef
19.
Kewcharoenwong, P., & Uster, H. (2014). Benders decomposition algorithms for the fixed-charge relay network design in telecommunications. Telecommunication Systems, 56(4), 441–453.CrossRef
20.
Klincewicz, J. (2006). Optimization issues in quality of service. In M. Resende & P. Pardalos (Eds.), Handbook of optimization in telecommunications (pp. 435–458). New York: Springer.CrossRef
21.
Klinkowski, M. (2012). On the effect of regenerator placement on spectrum usage in translucent elastic optical networks. In 14th International Conference on Transparent Optical Networks (ICTON) (pp. 1–6).
22.
Konak, A. (2012). Network design problem with relays: A genetic algorithm with a path-based crossover and a set covering formulation. European Journal of Operational Research, 218(3), 829–837.CrossRef
23.
Konak, A., Kulturel-Konak, S., & Smith, A. E. (2009). Two-edge disjoint survivable network design problem with relays. In J. Chinneck, B. Kristjansson, & M. Saltzman (Eds.), Operations research and cyber-infrastructure, operations research/computer science interfaces series (Vol. 47, pp. 279–292). New York: Springer.
24.
Laporte, G., & Pascoal, M. M. (2011). Minimum cost path problems with relays. Computers & Operations Research, 38(1), 165–173.CrossRef
25.
Marin, A. (2005). Formulating and solving splittable capacitated multiple allocation hub location problems. Computers & Operations Research, 32(12), 3093–3109.CrossRef
26.
Martinelli, F., Andriolli, N., Castoldi, P., & Cerutti, I. (2014). All-optical regenerator placement in WSON. In International Conference on Optical Network Design and Modeling (pp. 299–304).
27.
Martinelli, F., Andriolli, N., Castoldi, P., & Cerutti, I. (2014). Genetic approach for optimizing the placement of all-optical regenerators in WSON. Journal of Optical Communications and Networking, 6(11), 1028–1037.CrossRef
28.
Pioro, M., Szentesi, A., Harmatos, J., Juttner, A., Gajowniczek, P., & Kozdrowski, S. (2002). On open shortest path first related network optimisation problems. Performance Evaluation, 48(1–4), 201–223.CrossRef
29.
Rahman, Q., Bandyopadhyay, S., & Aneja, Y. (2015). Optimal regenerator placement in translucent optical networks. Optical Switching and Networking, 15, 134–147.CrossRef
30.
Rajan, D., & Atamturk, A. (2004). A directed cycle-based column-and-cut generation method for capacitated survivable network design. Networks, 43(4), 201–211.CrossRef
31.
Ramirez-Marquez, J., Rocco, S., & Claudio, M. (2009). Stochastic network interdiction optimization via capacitated network reliability modeling and probabilistic solution discovery. Reliability Engineering & System Safety, 94(5), 913–921.CrossRef
32.
Santos, D., de Sousa, A., & Alvelos, F. (2013). A hybrid column generation with GRASP and path relinking for the network load balancing problem. Computers & Operations Research, 40(12), 3147–3158.CrossRef
33.
Tipper, D. (2014). Resilient network design: Challenges and future directions. Telecommunication Systems, 56(1), 5–16.CrossRef
34.
Tomaszewski, A. M., Pióro, M., & Zotkiewicz, M. (2010). On the complexity of resilient network design. Networks, 55(2), 108–118.
35.
Truffot, J., & Duhamel, C. (2008). A branch and price algorithm for the \(k\)-splittable maximum flow problem. Discrete Optimization, 5(3), 629–646.CrossRef
36.
Varvarigos, E., & Christodoulopoulos, K. (2014). Algorithmic aspects in planning fixed and flexible optical networks with emphasis on linear optimization and heuristic techniques. Journal of Lightwave Technology, 32(4), 681–693.CrossRef
37.
Xu, D., Chiang, M., & Rexford, J. (2007). DEFT: Distributed exponentially-weighted flow splitting. In 26th IEEE International Conference on Computer Communications (INFOCOM 2007) (pp. 71–79).
38.
Xu, J., Chiu, S., & Glover, F. (1997). Tabu search for dynamic routing communications network design. Telecommunication Systems, 8(1), 55–77.CrossRef
Metadaten
Titel
Multi-commodity k-splittable survivable network design problems with relays
verfasst von
Ozgur Kabadurmus
Alice E. Smith
Publikationsdatum
01.05.2016
Verlag
Springer US
Erschienen in
Telecommunication Systems / Ausgabe 1/2016
Print ISSN: 1018-4864
Elektronische ISSN: 1572-9451
DOI
https://doi.org/10.1007/s11235-015-0067-9

Weitere Artikel der Ausgabe 1/2016

Telecommunication Systems 1/2016 Zur Ausgabe

OriginalPaper

Effective network security monitoring: from attribution to target-centric monitoring

OriginalPaper

A context-aware search system for Internet of Things based on hierarchical context model

OriginalPaper

Blocking probabilities of elastic and adaptive calls in the Erlang multirate loss model under the threshold policy

OriginalPaper

Dynamic collaborative in-network event detection in wireless sensor networks

OriginalPaper

An adaptive cache invalidation technique for wireless environments

OriginalPaper

EMIP: energy-efficient itinerary planning for multiple mobile agents in wireless sensor network

Neuer Inhalt

    Bildnachweise