Powiadomienia systemowe
- Sesja wygasła!
Tytuł artykułu
Autorzy
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
This monograph is devoted to optimisation models and algorithms for designing contemporary telecommunications transport networks. The particular focus is on the conceptual framework of transport network design and on the decomposition of the design problem and the design process. The presented conceptual framework is based on an original layered model of network resources, which is consistent with the functional architecture of transport networks contained in the ITU-T standards as well as can be directly expressed using mathematical models of multicommodity flow networks. The framework introduces an abstract generic model of the transport network design problem, its decomposition with respect to network layers and States, and an abstract generic network design procedure of solving the problem. The framework encompasses the models of the physical architecture and the organisational structure of the transport network. and the model of the network planning process. The presented work introduces an original complete mathematical description of the transport network based on the multicommodity network flow model complemented with elements pertaining to the notions of layers and states. Also, an original extension of the classical necessary and sufficient conditions of the existence of a multicommodity flow to the case of multiple layers and multiple slates is described. It is shown how the basic network model can be extended and generalised to consistently tackle fundamental phenomena and mechanisms of transport network operations related to traffic routing, network resilience to failures, quality of service and equitable allocation of network resources, variations and uncertainty of traffic demands, and network evolution. Applications of the basic methods of mathematical programming that are commonly used for network design are analysed in detail. In particular, the work analyses the branch-and-bound approach, the cutting plane method, the column generation and the constraint generation techniques of mixed integer linear programming, problem decomposition methods based on Benders' decomposition and Lagrangian relaxation, and the lesicographic maximization and max-min fair optimisation methods of multiple criteria decision making, The usage of the methods is analysed by means of original studies of difficult network optimization problems such as shortest-path routing design, connection restoration design in GMPLS networks, inter-domain traffic routing optimisation, and minimisation of label usage in GMPLS networks. A particularly important theoretical element of this work is a comprehensive analysis and classification of the complexity of designing transport networks resilient to failures. Original proofs of the NP-hardness of the resilient network design are presented that pertain to all major variants of the problem, in particular, providing a final answer to a number of so-far unresolved questions.
Przedmiotem pracy są modele i algorytmy projektowania współczesnych telekomunikacyjnych sieci transportowych. Szczególną uwagę poświecono kwestii modelu pojęciowego problemu projektowania sieci oraz zagadnieniom dekompozycji problemu i procesu projektowania. Zaproponowany w pracy model pojęciowy jest oparty na oryginalnym warstwowym modelu zasobów sieci transportowej, który jest zgodny z podstawową architekturą funkcjonalną sieci transportowej zawartą w standardach 1TU-T poświęconych zagadnieniom sterowania i zarządzania sieciami, a jednocześnie może być wyrażony wprost poprzez modele optymalizacyjne sieci przepływów wielotowarowych. Elementami modelu pojęciowego są również model abstrakcyjnego generycznego problemu projektowania sieci transportowej dekomponowalnego wzglądem warstw i stanów sieci oraz abstrakcyjna generyczna procedura projektowania wielowarstwowej wielostanowej sieci transportowej. Uzupełnieniem modelu pojęciowego są modele architektury fizycznej i struktury organizacyjnej sieci transportowej, oraz model procesu planowania sieci. W pracy przedstawiono oryginalny kompletny opis matematyczny sieci transportowych oparty na modelu sieci przepływów wielotowarowych, uzupełnionym o pojęcia wielowarstwowości i wielostanowości. Zaprezentowano oryginalne rozszerzenie klasycznych warunków koniecznych i dostatecznych istnienia przepływu wielotowarowego na przypadek wielu warstw i wielu stanów sieci. Pokazano jak poprzez ograniczone rozszerzenia lub uogólnienia podstawego matematycznego opisu siec: jest możliwe jednolite zamodelowanie podstawowych zjawisk i mechanizmów działania sieci transportowej, związanych w szczególności z kierowaniem ruchu, zabezpieczeniem sieci przed awariami, zapewnieniem jakości obsługi ruchu i sprawiedliwym wykorzystaniem zasobów, zmiennością i niepewnością zapotrzebowani ruchowych oraz ewolucją sieci w czasie. Praca analizuje sposoby wykorzystania najważniejszych metod programowania matematycznego, w szczególności optymalizacji dyskretnej, stosowanych w projektowaniu sieci transportowych: metod programowania liniowego całkowitoliczbowego - metody podziałów i ograniczeń, metody płaszczyzn odcinających; metod dekompozycji - metody dekompozycji Bendersa, metody relaksacji Lagrange'a; metod optymalizacji wielokryterialnej – metod maksymalizacji leksykograficznej t optymalizacji sprawiedliwej. Przedstawiono oryginalne wykorzystanie tych metod w trudnych problemach projektowania sieci, takich jak problem kierowania ruchu po najkrótszych ścieżkach, problem projektowania sieci GMPLS zabezpieczonych mechanizmem Fast Reroute, problem kierowania ruchu międzydomenowego czy problem minimalizacji liczby etykiet w sieci GMPLS. Szczególnym elementem teoretycznym pracy jest wyczerpująca analiza i klasyfikacja złożoności problemów projektowania sieci zabezpieczonych przed awariami, której wynikiem jest zbiór oryginalnych dowodów NP-zupełność i wszystkich podstawowych wariantów problemu projektowania, w szczególności w części do niedawna nierozstrzygniętych.
Słowa kluczowe
telecommunications
transport networks
network architecture
multi-layer networks
network planning
network design
traffic routing
network resilience
traffic uncertainty
multicommodity flow networks
mathematical programming
mixed-integer programming
discrete optimisation
decomposition methods
branch-and-cut
column generation
cutting plane
telekomunikacja
sieci transportowe
architektura sieci
sieci wielowarstwowe
planowanie sieci
projektowanie sieci
sterowanie ruchu
elastyczność sieci
niepewność ruchu
sieci przepływowe
programowanie matematyczne
programowanie mieszane
dyskretna optymalizacja
metoda rozkładu
kolumna generacji
płaszczyzna cięcia
Rocznik
Tom
Strony
9--190
Opis fizyczny
Bibliogr. 185 poz., rys., tab.
Twórcy
autor
- Institute of Telecommunications, Faculty of Electronics and Information Technologies
Bibliografia
- [1] R. Ahuja, T. Magnanti, and J. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.
- [2] C. Alexander, S. Ishikawa, and M. Silverstein. A Pattern Language: Towns, Buildings, Construction. Oxford, 1977.
- [3] A. Altin, H. Yaman, and M. Pinar, The robust network loading problem under polyhedral demand uncertainty: Formulation, polyhedral analysis and computations. INFORMS Journal on Computing, 23:75-89, 2011.
- [4] F. Alvelos and J. Valerio de Carvalho. Comparing branch-and-price algorithms for the unsplittable multicommodity flow problem. In Proceedings of the 1st International Network Optimization Conference INOC 2003, Evry-Paris, France, 2003.
- [5] E. Amaldi, S. Coniglio, L. Gianoli, and C. Ileri. On single-path network routing subject to max-min fair flow allocation. In Proceedings of the 6th International Network Optimization Conference INOC 2013, Tenerife, Spain, 2013.
- [6] D. Applegate and E. Cohen. Making intra-domain routing robust to changing and uncertain traffic demands: Understanding fundamental tradeoffs. In Proceeding of the ACM S1GCOMM 2003, Karlsruhe, Germany, 2003.
- [7] D. Applegate and M. Thorup. Load optimal MPLS routing with N+M labels. In Proceedings of the 22nd IEEE Conference on Computer Communications INFOCOM 2003, San Francisco, California, USA, 2003.
- [8] A. Assad. Multicommodity network flows: A survey. Networks, 8:37-91, 1978.
- [9] Y. Azar, E. Cohen, A. Fiat, H. Kaplan, and H. Racke. Optimal oblivious routing in polynomial time. In Proceedings of the 35th ACM Symposium on the Theory of Computing, San Diego, California, USA, 2003.
- [10] F. Barahona and R. Anbil. The volume algorithm: Producing primal solutions with a subgradient method. Mathematical Programming, 87(3):385-399, 2000.
- [11] C. Barnhart, C. Hane, and P. Vance. Using branch-and-price -and-cut-to solve
- [12] C. Barnharl, E, Johnson. G. Nemhauser, M. Savelsbergh, and P. Vance. Branch-and- price: Column generation for solving huge integer programs, Operations Research, 46(3):316-329, 1998.
- [13] F. Behringer. A simplex based algorithm for the lexicographically extended linear max-min problem. European Journal of Operational Research, 7:274-283,1981.
- [14] M. Belaidouni and W. Ben-Ameur. A superadditive approach to solve the minimum cost single path routing problem: Preliminary results. In Proceedings of the 1st International Network Optimization Conference INOC 2003, Evry-Paris, France, 2003.
- [15] M. Belaidouni and W. Ben-Ameur. On the minimum cost multiple-source unsplittable flow problem. RAIRO - Operations Research, 41 (3): 253-273, 2007.
- [16] W. Ben-Ameur. Between fully dynamic routing and robust stable routing. In Proceedings of the 3rd International Network Optimization Conference INOC 2007, Spa, Belgium, 2007.
- [17] W. Ben-Ameur and E. Gourdin. Internet routing and related topology issues. SIAM Journal on Discrete Mathematics, 17(l): 18-49, 2003.
- [18] W. Ben-Ameur, E. Gourdin, B. Liau, and N. Michel. Dimensioning of Internet networks. In Proceedings of the 2nd International Workshop on the Design of Reliable Communication Networks DRCN 2000, Munich, Germany, 2000.
- [19] W. Ben-Ameur and H. Kerivin. Routing of uncertain demands. In Proceedings Of the INFORMS2001, Miami, Florida, USA, 2001.
- [20] W. Ben-Ameur and H. Kerivin. New economical virtual private networks. Communications of the ACM, 46(6):69-73, 2003.
- [21] W. Ben-Ameur and H. Kerivin. Routing of uncertain traffic demands. Optimization and Engineering, 3:283-313, 2005.
- [22] W. Ben-Ameur, P. Pavón Marino, and M. Pióro. On traffic domination in communication networks. Lecture Notes in Computer Science, 6821:191-202, 2011.
- [23] W. Ben-Ameur and M. Żotkiewicz. Robust routing and optimal partitioning of a traffic demand polytope. International Transactions in Operational Research, 18(3):307-333,2011.
- [24] J. Benders. Partitioning procedures for solving mixed variable programming problems. Numerische Mathematik, 4:238-252, 1962.
- [25] J-C. Bermond, D. Coudert, J. Moulierac, S. Perennes, H, Rivano, I. Sau, and F. Solano. Designing hypergraph layouts to GMPLS routing strategies. In Proceedings of the 16th International Colloquium on Structural Information and Communication Complexity SIROCCO 2009, Piran, Slovenia, 2009.
- [26] J-C. Bermond, D. Coudert, J. Moulierac, S, Perennes, H. Rivano, L Sau, and F. Solano. MPLS label stacking on the line network. In Proceedings of the IFIP Networking 2009, Aachen, Germany, 2009.
- [27] D. Bertsekas and R. Gallager. Data Networks. Prentice Hali, 2nd edition, 1999.
- [28] D. Bertsimas and M. Sim. Robust discrete Optimization and network flows. Mathematical Programming, 98:49-71,2003.
- [29] D. Bertsimas and M. Sim. The price of robustness. Operations Research, 51(1):35-53,2004.
- [30] S. Bhatnagar, S. Ganguly, and B. Nath. Creating multipoint-to-point LSPs for traffic engineering. IEEE Communications Magazine, 43(1):95-100, 2005.
- [31] A. Bley. On the approximability of the minimum congestion unsplittable shortest path routing problem. In Proceedings of the 11th Conference on Integer Programming and Combinatorial Optimization IPCO 2005, Berlin, Germany, 2005.
- [32] A. Bley. Inapproximability results for the inverse shortest paths problem with integer lengths and unique shortest paths. Networks, 50(l):29-36, 2007,
- [33] A. Bley. Routing and Capacity Optimization for IP Networks. PhD thesis, Technische Universitat Berlin, Berlin, Germany, 2007.
- [34] A. Bley, B. Fortz, E. Gourdin, K. Holmberg, O. Klopfenstein, M. Pióro, A. Tomaszewski, and H. Umit. Optimization of OSPF routing in IP networks. In A. Koster and X. Munoz, editors, Graphs and Algorithms in Communication Networks - Studies in Broadband, Optical, Wireless, and Ad Hoc Networks. Springer-Verlag, 2009.
- [35] A. Bley and T. Koch. Integer programming approaches to access and backbone IP-network planning. In Modeling, Simulation and Optimization of Complex Processes: Proceedings of the 3rd International Conference on High Performance Scientific Computing, Hanoi, Vietnam, 2006.
- [36] N. Bourquia, W. Ben-Ameur, E. Gourdin, and P. Tolla. Optimal shortest path routing for Internet networks. In Proceedings of the 1st International Network Optimization Conference INOC 2003, Evry-Paris, France, 2003.
- [37] S. Boyd and L. Vanderberghe. Convex Optimization. Cambridge University Press, 2004.
- [38] G. Brightwell, G. Oriolo, and F. Shepherd. Reserving resilient capacity in a network. SIAM Journal on Discrete Mathematics, 14:524—539, 2001.
- [39] P. Brostrom and K. Holmberg. Compatible weights and valid cycles in non-spanning OSPF routing patterns. In P. Brostrom PhD Dissertation, Optimization Models and Methods for Telecommunication Networks Using OSPF, Linkoping. Sweden, 2006. Linkoping University.
- [40] P. Brostrom and K. Holmberg. Design of OSPF networks using subpath consistent routing patterns. In P. Brostrom PhD Dissertation, Optimization Models and Methods for Telecommunication Networks Using OSPF, Linkoping, Sweden, 2006. Linkoping University.
- [41] P. Brostrom and K. Holmberg. Multiobjective design of survivable IP networks. In P. Brostrom PhD Dissertation, Optimization Models and Methods for Telecommunication Networks Using OSPF, Linkoping, Sweden, 2006. Linkoping University.
- [42] P. Brostrom and K. Holmberg. Stronger neccessary conditions for the existence of a compatible OSPF metric. In P. Brostrom PhD Dissertation, Optimization Models and Methods for Telecommunication Networks Using OSPF. Linkoping University, Linkoping, Sweden, 2006.
- [43] P. Brostrom and K. Holmberg. Valid cycles: A source of infeasibility in OSPF routing. In P. Brostrom PhD Dissertation, Optimization Models and Methods for Telecommunication Networks Using OSPF, Linkoping, Sweden, 2006. Linkoping University.
- [44] A. Chames and W. Cooper. Chance-constrained programming. Management Science, 5:73-79, 1959.
- [45] C. Chekuri. Routing and network design with robustness to changing or uncertain traffic demands. ACM SIGACT News, 38(3):106-129. 2007.
- [46] C. Chekuri, G. Oriolo, M. Scutella, and F. Shepherd. Hardness of robust network design. Networks, 50(I):50-54, 2007.
- [47] H. Crowder, E. Johnson, and M. Padberg. Solving large-scale zero-one linear programming problems. Operations Research, 31:803-834, 1983.
- [48] G. Dahl and M. Stoer. A cutting plane algorithm for mullicommodity survivable network design problems. 1NFORMS Journal on Computing, 10( l ) 180-188 1998.
- [49] L. de Giovanni, B. Fortz, and M. Labbe. A lower bound for the Internet Protocol network design. In Proceedings of the 2nd International Network Optimization Conference INOC2005, Lisbon, Portugal, 2005.
- [50] N. Duffield, P. Goyal, A. Greenberg, P. Mishra, K. Ramakrishnan, and J. van der Merive. A flexible model for resource management in virtual private networks. In Proceedings of the ACM SIGCOMM1999, Cambridge, Massachusetts USA 1999.
- [51] A. Farrel, J.-P Vasseur, and J. Ash. A path computation element (PCE)-based architecture, August 2006. Internet RFC 4655, http://www.ietf.org/rfc/rfc4655.txt.
- [52] N. Feamster, J. Borkenhagen, and J. Rexford. Guidlines for interdomain traffic engineering. ACM SIGCOM Computer Communications Review, 33(5)-19-30 2003.
- [53] A. Feldmann, A. Greenberg, C. Lund, N. Reingold, and J. Rexford. Netscope: Traffic engineering for IP networks. IEEE Transactions on Networking 14-11-19, 2000.
- [54] L. Ford and D. Fulkerson. Flows in Networks. Princeton University Press 1962.
- [55] B. Fortz and M. Thorup. Internet traffic engineering by optimizing OSPF weights. In Proceedings of the 19th IEEE Conference on Computer Communication INFOCOM 2000, Tel-Aviv, Israel, 2000.
- [56] M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co, 1979.
- [57] N. Garg and J. Konemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM Journal of Computing 37(2):630—652, 2007.
- [58] J. Geffard. A 0-1 model for singly routed traffic in telecommunications. Annales des Telecommunications, 56:140-149, 2001.
- [59] E. Gourdin. Optimizing Internet networks. OR/MS Today, 28(2):46-49. 2001.
- [60] D. Gross and C. Harris. Fundamentals of Queueing Theory, John Wiley & Sons, 1998.
- [61] Z. Gu, G. Nemhauser, and M. Savelsbergh. Lifted cover inequalities for 0-1 linear programs: Computation. 1NFORMS Journal on Computing, 10:427-437, 1998.
- [62] Z. Gu, G. Nemhauser, and M, Savelsbergh. Lifted cover inequalities for 0-1 linear programs: Complexity. INFORMS Journal on Computing, 11:117-123, 1999.
- [63] A. Gunnar and M. Johansson. Routing and network design with robustness to changing or uncertain traffic demands. In Proceedings of the 3rd Conference on Next Generation Internet Networks Traffic Engineering NGI2005, Aveiro, Portugal, 2009.
- [64] A. Gunnar and M. Johansson. Robust load balancing under traffic uncertainty - tractable models and efficient algorithms. Telecommunication Systems, 2010. published online.
- [65] A. Gupta, A. Kumar, and R. Rastogi. Exploring the trade-off between label size and stack depth in MPLS routing. In Proceedings of the 22nd IEEE Conference on Computer Communications INFOCOM 2003, San Francisco, California, USA, 2003.
- [66] M. Hartmann, D. Hock, C. Schwartz, and M. Menth. Objective functions for optimization for resilient and non-resilient IP routing. In Proceedings of the 7th International Workshop on Design of Reliable Communication Networks DRCN 2009, Washington. DC, USA, 2009.
- [67] C. Helmberg. ConicBundle 0. l. Technical report, Fakultal fur Mathematik, Technische Universitat, Chemnitz, Germany, 2005. (http://www-user.tu-chemnitz.de/~helmberg/ConicBundle/).
- [68] J-B. Hiriart-Urruty and C. Lemarechal. Convex Analysis and Minimization I, II. Springer-Verlag, 1996.
- [69] D. Hock, M. Hartmann, M. Menth, and C. Schwartz. Optimizing unique shortest paths for resilient routing and fast reroute in IP-based networks. In Proceeding of the IEEE Network Operations and Management Symposium NOMS 2010, Osaka. Japan, 2010.
- [70] J. Hu. Diverse routing in optical mesh networks. IEEE Transactions on Communications, 51(3):489—494, 2003.
- [71] R. Huelsermann, M. Gunkel, C, Meusburger, and D. Schupke. Cost modeling and evaluation of capital expenditures in optical multilayer networks. Journal of Optical Networking, 7{9):814-833, 2008.
- [72] H. Isermann. Linear lexicographic optimization. OR Spektrum, 4:223-228, 1982.
- [73] ITU-T. Network node interface for the synchronous digital hierarchy (SDH). ITU, 1988-2007. Recommendation G.707/Y.1322.
- [74] ITU-T. Generic functional architecture of transport networks. ITU, 1995-2001. Recommendation G.805.
- [75] ITU-T. Requirements for automatic switched transport networks (ASTN), ITU, 2001. Recommendation G.807/Y.1302.
- [76] ITU-T. Architecture for the automatically switched optical network. ITU, 2001-2012. Recommendation G.8080/Y.1304 (G.ason).
- [77] ITU-T. Interfaces for the optical transport network. ITU, 2001-2012, Recommendation G.709/Y.1331.
- [78] ITU-T. Functional architecture of connectionless layer networks. ITU, 2003. Recommendation G.809.
- [79] D. Jungnickel. Graphs, Networks and Algorithms. Springer-Verlag, 1999.
- [80] F. Kelly, A. Mauloo, and D. Tan. Rate control for communication networks: Shadow prices, proportional fairness and stability. Journal of the Operations Research Society, 49:237-252, 1998.
- [81] J. Kleinberg, Y. Rabani, and E. Tardos. Fairness in routing and load balancing. In Proceedings of the 35th IEEE Symposium on the Foundations of Computer Science, Santa Fe, New Mexico, USA, 2000.
- [82] O. Klopfenstein. Tractable algorithms for chance-constrained combinatorial problems. RAIRO Operational Research, 43:157-187. 2009.
- [83] O. Klopfenstein. Solving chance-constrained combinatorial problems to optimality. Computational Optimization and Applications, 45(3):607-638, 2010.
- [84] B. Korte and J. Vygen. Combinatorial Optimization. Theory and Algorithms. Springer-Verlag, 5th edition, 2012.
- [85] A. Koster, A. Zymolka, M. Jager, and R. Hulsermann. Demand-wise shared protection for meshed optical networks. Journal of Network and Systems Management, 13(l):33-55. 2005.
- [86] T. Larsson and Z. Liu. A primal convergence result for dual subgradient optimization with application to multicommodity network flows. Technical report, Department of Mathematics, Linkoping Institute of Technology, Linkoping, Sweden, 1989.
- [87] L. Lasdon. Optimization Theory for Large Systems. MacMillan, 1970.
- [88] M.S. Lobo, L. Vanderberghe, S. Boyd, and H. Lebert. Applications of second-order cone programming. Linear Algebra and Its Applications, 284; 193-228, 1998.
- [89] J. Lubacz, M. Jarociński, M. Pióro, and O. Soto. On the atm network architecture and routing principles. In Proceedings of the 7th ITC Specialist Seminar, Morristown 1990, Morristown, New Jersey, USA, 1990.
- [90] J. Lubacz and A. Tomaszewski. Generic network design procedures. COST 242 document, Institute of Telecommunications, Warsaw University of Technology, Warsaw, Poland, 1995.
- [91] J. Lubacz and A. Tomaszewski. Generic architecture and design of core network. In J. Roberts, U. Mocci, and J. Virtamo, editors, Methods for the Performance Evaluation and Design of Broadband Multiservice Networks. Springer-Verlag,.1996.
- [92] J. Lubacz and A. Tomaszewski. A network planning model. In Proceedings of the 1st Polish-German Teletraffic Symposium PGTS 2000, Dresden, Germany, 2000.
- [93] J. Lubacz, A. Tomaszewski, and D. Bursztynowski. A generic approach to network design - virtual network design. COST 242 document, Institute of Telecommunications, Warsaw University of Technology, Warsaw, Poland, 1994.
- [94] J. Lubacz, A. Tomaszewski, D. Bursztynowski, and M. Pióro. A framework for network design and management. COST 242 document, Institute of Telecommunications, Warsaw University of Technology, Warsaw, Poland, 1993.
- [95] J. Lubacz, A. Tomaszewski, and M. Średniawa. A reference model for next generation networks and hybrid services. In Proceedings of the International Symposium on Telecommunications VITEL 2002, Ljubljana, Slovenia, 2002.
- [96] J. Lubacz, A. Tomaszewski, and M. Wojciechowski. Introduction of interurban SDH network in Poland. In Proceedings of the 6th International Telecommunications Network Strategy and Planning Symposium NETWORKS 1994, Budapest, Hungary, 1994.
- [97] H. Luss. On equitable resource allocation problems: A lexicographical mini-max approach. Operations Research, 47:361-378, 1999.
- [98] H. Luss. Equitable Resource Allocation: Models, Algorithms and Applications. John Wiley& Sons, 2012.
- [99] E. Mannie. Generalized Multi-Protocol Label Switching(GMPLS) Architecture. IETF, October 2004. Internet RFC 3945, http://www.ietf.org/rfc/rfc3945.txt.
- [100] E. Marchi and J. Oviedo. Lexicographic optimality in the multi objective linear programming: the nucleolar solution. European Journal of Operational Research, 57:355-359, 1992.
- [101] P. Pavón Marino and M. Pióro. On total traffic domination in non-complete graphs. Operations Research Letters, 39:40-43, 2011.
- [102] R. Martin and M. Menth. Backup capacity requirements for MPLS fast reroute. In Proceedings of the 7th ITG Workshop on Photonic Networks, Leipzig, Germany, 2006.
- [103] J.-F. Maurras and S. Vanier. Network synthesis under survivability constraints. 4OR - A Quarterly Journal of Operations Research, 2(1):53-67, 2004.
- [104] M. Menth, M. Hartmann, and R. Martin. Robust IP link costs for multilayer resilience. In Proceedings of the IFIP Networking 2007, Atlanta, Georgia USA, 2007.
- [105] M. Menth, R. Martin, M. Hartmann, and U. Spoerlein. Efficiency of routing and resilience mechanisms in packet-switched communication networks. European Transactions on Telecommunications, 21(2), 2010.
- [106] M. Minoux. Mathematical Programming: Theory and Algorithms. John Wiley&Sons, 1986.
- [107] M. Minoux. Network synthesis and optimum network design problems: Models, solution methods and applications. Networks, 19:313-360, 1989.
- [108] J. Moy. OSPF: Anatomy of on Internet Routing Protocol. Addison-Wesley 1998.
- [109] D. Nace. A linear programming based approach for computing optimal fair splittable routing. In Proceedings of the 7th IEEE International Symposium on Computer and Communications 1SCC 2002, Taormina, Italy, 2002,
- [110] D. Nace, M. Pióro, A. Tomaszewski, and M. Żotkiewicz. A polynomial multicommodity flow problem with difficult path generation. In Proceedings of the 3rd International Congress on Ultra Modern Telecommunications ICUMT 2011, Budapest, Hungary, 2011.
- [111] D. Nace, M. Pióro, A. Tomaszewski, and M. Żotkiewicz. Complexity issues for a multicommodity flow problem with difficult dual separation, Networks, 2013.
- [112] G. Nemhauser and L. Wolsey. Integer and Combinatorial Optimization. John Wiley&Sons, 1988.
- [113] W. Ogryczak. On the lexicographic minmax approach to location problems. European Journal of Operational Research, 100:566-587, 1997.
- [114] W. Ogryczak. Wielokryterialna optymalizacja liniowa i dyskretna. Modele preferencji i zastosowania do wspomagania decyzji (in Polish). Wydawnictwa Uniwersytetu Warszawskiego, Warszawa, Poland, 1997.
- [115] W. Ogryczak, M. Pióro, and A. Tomaszewski. Telecommunications network design and max-min Optimization problem. Journal of Telecommunications and Information Technology, 3:43-53, 2005.
- [116] W. Ogryczak and T. Śliwiński. On solving linear programs with ordered weighted averaging objective. European Journal of Operational Research, 148:80-91, 2002.
- [117] D. Oran. OSI IS-IS Intra-Domain Routing Protocol. IETF, February 1990. Internet RFC 1142, http://www.ietf.org/rfc/rfc1142.txt.
- [118] G. Oriolo. Domination between traffic matrices. Mathematics of Operations Research, 33(1):91-96, 2008.
- [119] S. Orlowski. Local and global restoration of node and link failures in telecommunication networks. Master's thesis, Technische Universität Berlin, Berlin, Germany, 2003.
- [120] S. Orlowski. Optimal Design of Survivable Multi-layer Telecommunication Networks. PhD thesis, Technische Universität Berlin, Berlin, Germany, 2009.
- [121] S. Orlowski and M. Pióro. On the complexity of column generation in survivable network design with path-based survivability mechanisms. In Proceedings of the 4th International Network Optimization Conference INOC 2009, Pisa, Italy, 2009.
- [122] S. Orlowski and M. Pióro. On the complexity of column generation in network design with path-based survivability mechanisms. Networks, 59(1):132-147, 2012.
- [123] S. Orlowski, M. Pióro, A. Tomaszewski, and R. Wessäly. SNDlib 1.0-Survivable Network Design library. In Proceedings of the 3rd International Network Optimization Conference INOC 2007, Spa. Belgium, 2007.
- [124] S. Orlowski, M. Pióro, A. Tomaszewski, and R. Wessaly. SNDlib 1.0-survivable network design library. Networks, 55(3):276-286, 2010.
- [125] M. Padberg. Classical cuts for mixed-integer programming and branch-and-cut. Mathematical Methods of Operations Research, 53:173-203, 2001.
- [126] P. Ping Pan. Fast Reroute Extensions w RSVP-TE for LSP Tunnels. IETF, July 2003. Internet Draft, draft-ietf-rnpls-rsvp-lsp-fastreroute-03.txt.
- [127] K. Park, S. Kang, and S. Park. An integer programming approach to the bandwidth packing problem. Management Science, 42(9): 1277-1291, 1996.
- [128] S. Park, D. Kim, and K. Lee, An integer programming approach to the path selection problems. In Proceedings of the 1st International Network Optimization Conference INOC 2003, 2003.
- [129] M. Parker and J. Ryan. A column generation algorithm for bandwidth packing. Telecommunications Systems, 2:185-195, 1994.
- [130] M, Pióro, J. Lubacz, A. Tomaszewski, and D. Bursztynowski. Traffic management in the Warsaw metropolitan network. In Proceedings of the ITC Regional Seminar, St. Petersburg 1993, St. Petersburg, Russia, 1993.
- [131] M. Pióro, J. Lubacz, A. Tornaszewski, and D. Bursztynowski. Traffic routing in a rapidly developing network - a deployment strategy. IEEE Journal on Selected Areas of Telecommunications, 12(7):1192-1198, 1994.
- [132] M. Pióro and D. Medhi. Routing, Flow, and Capacity Design in Communication and Computer Networks. Morgan Kaufman, 2004.
- [133] M. Pióro, D. Nace, A. Tomaszewski, and M. Żotkiewicz. On a survivable network design problem with one or two failing links and elementary paths. In Proceedings of the 21st International Symposium on Mathematical Programming, Berlin, Germany, 2012.
- [134] M. Pióro, P, Nilsson, E. Kubilinskas, and G. Fodor. On efficient max-min fair routing algorithms. In Proceedings of the 8th IEEE International Symposium on Computer and Communications ISCC 2003, Kiris-Kemer, Turkey, 2003.
- [135] M. Pióro, A. Szentesi, J. Harmatos, A. Juttner, P. Gajowniczek, and S. Kozdrowski. On OSPF related network optimization problems. In Proceedings Of the 8th IFIP Workshop on Performance Modelling and Evaluation of ATM & IP Networks, Ilkley, United Kingdom, 2000.
- [136] M. Pióro, A. Szentesi, J. Harmatos, A. Juttner, P. Gajowniczek, and S. Kozdrowski. On OSPF related network optimization problems. Performance Evaluation, 48:201-223, 2002. (A preliminary version of this paper appeared in the proceedings of the 8th IFIP Workshop on Performance Modelling and Evaluation of ATM & IP Networks 2000, Ilkley, United Kingdom).
- [137] M. Pióro and A. Tomaszewski. Feasibility issues in shortest-path routing with traffic flow split. In Proceedings of the 3rd International Network Optimization Conference INOC 2007, Spa, Belgium, 2007.
- [138] M. Pióro and A. Tomaszewski. Optimization models and methods for integrated transport networks design with varying, evolving and uncertain traffic demands. Technical report, Institute of Telecommunications, Warsaw University of Technology, Warsaw, Poland, 2012.
- [139] M. Pióro, A. Tomaszewski, M. Dzida, M. Mycek, and M. Zagożdżon. Exact and heuristic methods for single-path routing problems. Technical report, Institute of Telecommunications, Warsaw University of Technology, Warsaw, Poland, 2006.
- [140] M. Pióro, A. Tomaszewski, M. Dzida, M. Mycek, and M. Zagożdżon. Literature survey, models, polyhedral results, and exact and heuristic methods for shortest-path routing problems. Technical report, Institute of Telecommunications, Warsaw University of Technology, Warsaw, Poland, 2007.
- [141] M. Pióro, A. Tomaszewski, M. Dzida, M. Mycek, and M. Zagożdżon. A subgradient optimization approach to inter-domain routing in IP/MPLS networks. Lecture Notes in Computer Science (LNCS), 4479:1241-1244, 2007.
- [142] M. Pióro, A. Tomaszewski, M. Dzida, M. Mycek, and M. Zagożdżon. A subgradient optimization approach to inter-domain routing in IP/MPLS networks. In Proceedings of the IFIP Networking 2007, Atlanta, Georgia, USA, 2007.
- [143] M. Pióro, A. Tomaszewski, J. Lubacz, and M. Jarociński. Design of two-level PSTN, In Proceedings of the ITC Regional Seminar, Cracow 1991, Cracow, Poland, 1991.
- [144] M. Pióro, A. Tomaszewski, C. Żukowski, D. Hock, M. Hartmann, and M. Menth. Optimized IP-based vs. explicit paths for one-to-one backup in MPLS fast reroute. In Proceedings of the 14th International Telecommunications Network Strategy and Planning Symposium NETWORKS 2010, Warsaw, Poland, 2010.
- [145] M. Prytz and A. Forsgren. Dimensioning of a multicast network that uses shortest path routing distribution trees. In M. Prytz PhD Thesis, On Optimization in Design of Telecommunication Networks with Multicast and Unicast Traffic, Stockholm, Sweden, 2002. Royal Institute of Technology.
- [146] H. Racke. Minimizing congestion in general networks. In Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science FOCS 2002, Vancouver, British Columbia, Canada, 2002.
- [147] J. Rawls. The Theory of Justice. Harvard University Press, 1971.
- [148] D. Ryan and B. Foster. An integer programming approach to scheduling. In A. Wren, editor, Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling. North-Holland, 1981.
- [149] M. Scutella. On improving optimal oblivious routing. Operations Research Letters, 37(3):197-200, 2009.
- [150] H. Sherali and G. Choi. Recovery of primal solutions when using subgradient optimization methods to solve Lagrangean duals of linear programs, Operations Research Letters, 19:105-113, 1996.
- [151] N. Shor. Minimization Methods for Nondifferentiable Functions. Springer-Verlag, 1985.
- [152] G. Shrimali, A. Akella, and A. Mutapcic. Cooperative inter-domain traffic engineering using Nash bargaining and decomposition. In Proceedings of the 26th IEEE Conference on Computer Communication INFOCOM 2007, Anchorage, Alaska, USA, 2007.
- [153] F. Solano, R. Van Caenegem, D. Colle, J. Marzo, M. Pickavet, R. Fabregat, and P. Demeester. All-optical label stacking: Easing the trade-offs between routing and architecture cost in all-optical packet switching. In Proceedings of the 27th IEEE Conference on Computer Communications INFOCOM 2008, Phoenix, Arizona, USA, 2008.
- [154] F. Solano, R. Fabregat, Y. Donoso, and J. Marzo. Asymmetric tunnels in P2MP LSPs as a label space reduction method. In Proceedings of the IEEE International Conference on Communications ICC 2005, Seoul, Korea, 2005.
- [155] F. Solano, R. Fabregat, and J. Marzo. Full label space reduction in MPLS networks: Asymmetric merged tunneling. IEEE Communications Letters, 9(11):1021-1023, 2005.
- [156] F. Solano, R. Fabregat, and J. Marzo. On optimal computation of MPLS label binding for MultiPoint-to-Point connections. IEEE Transactions on Communications, 56(7): 1056-1059, 2007.
- [157] F. Solano, T. Stidsen, R. Fabregat. and J. Marzo. Label space reduction in MPLS networks; How much can a single stacked label do? IEEE/ACM Transactions on Networking, 16(6):1308-1320, 2008.
- [158] D. Stahle, S. Köhler, and U. Kohlhaas. Towards an optimization of the routing parameters for IP networks. Technical report, Department of Computer Science, University of Würzburg, Wurzburg, Germany, 2000.
- [159] R. Steuer. Multiple Criteria Optimization - Theory, Computation & Applications. John Wiley & Sons, 1986.
- [160] T. Stidsen, B. Petersen, K. Rasmussen, S. Spoorendonk, M. Zachariasen, F. Rambach, and M. Kiese. Optimal routing with single backup path protection. In Proceedings of the 3rd International Network Optimization Conference INOC 2007. Spa, Belgium, 2007.
- [161] J. Suurballle. Disjoint paths in a network. Networks, 4:125-145, 1974.
- [162] S. Terblanche. Contributions towards Survivable Network Design with Uncertain Traffic Requirements. PhD thesis, North-West University, RSA, 2009.
- [163] S. Terblanche, R. Wessaly, and J. Hattingh. Solution strategies for the multihour network design problem. In Proceedings of the 3rd International Network Optimization Conference INOC 2007, Spa, Belgium, 2007.
- [164] A. Tomaszewski. A polynomial algorithm for solving a general max-min fairness problem. In Proceedings of the 2nd Polish-German Teletraffic Symposium PGTS2002, Gdańsk, Poland, 2002.
- [165] A. Tomaszewski. A polynomial algorithm for solving a general max-min fairness problem. European Transactions on Telecommunications, 16(3):233-240, 2005.
- [166] A. Tomaszewski. Optimization models for multi-layer networks - grooming design modelling and decomposition. In Proceedings of the COFIN-Matheon Workshop, Lake Como, Italy, 2006.
- [167] A. Tomaszewski. The final answer to the complexity of a basic problem in resilient network design. In Proceedings of the 6th International Network Optimization Conference INOC 2013, Tenerife, Spain, 2013.
- [168] A. Tomaszewski and N. LeHoang. Design of transport networks with multicast communications. In Proceedings of the 1st Polish-German Teletraffic Symposium PGTS 2000, Dresden, Germany, 2000.
- [169] A. Tomaszewski and M. Pióro. Minimizing label usage in MPLS networks. In Proceedings of the 43rd Asilomar Conference on Signals, Systems and Computers, Asilomar, California, USA, 2009.
- [170] A. Tomaszewski, M. Pióro, M. Dzida, M. Mycek, and M. Zagożdżon. Towards distributed inter-domain routing optimization for IP/MPLS networks. Technical report, Institute of Telecommunications, Warsaw University of Technology, Warsaw, Poland, 2007.
- [171] A. Tomaszewski, M. Pióro, M. Dzida, M- Mycek, and M. Zagożdżon. Valid inequalities for a shortest-path routing optimization problem. In Proceedings of the 3rd International Network. Optimization Conference INOC 2007, Spa, Belgium, 2007.
- [172] A. Tomaszewski, M. Pióro, M. Dzida, and M. Zagożdzon. Optimization of administrative weights in IP networks using the branch-and-cut approach. In Proceedings of the 2nd International Network Optimization Conference INOC 2005, Lisbon, Portugal, 2005.
- [173] A. Tomaszewski. M. Pióro, and M. Mycek. Distributed inter-domain link capacity optimization for inter-domain IP/MPLS routing. In Proceedings of the IEEE Global Telecommunications Conference Globecom 2007, Washington, DC, USA, 2007.
- [174] A. Tomaszewski, M. Pióro, and M. Mycek. A distributed scheme for inter-domain routing optimization. Annals of Telecommunications, 63(11-12):631-638,2008.
- [175] A. Tomaszewski, M. Pióro, and M. Żotkiewicz. On the complexity of resilient network design. Networks, 55(2): 108-118, 2010.
- [176] S. Verbrugge. Methodology and input availability parameters for calculating OpEx and CapEx costs for realistic network scenarios. Journal of Optical Networking, 5(6):509-520, 2006.
- [177] R. Wessäly. DImensioning Survivable Capacitated NETworks. PhD thesis, Technische Universität Berlin, Berlin, Germany, 2000.
- [178] R. Wessäly, S. Orlowski, A. Zymolka, A. Koster, and C. Gruber. Demand-wise shared protection revisited: A new model for survivable network design. In Proceedings of the 2nd International Network Optimization Conference INOC 2005, Lisbon, Portugal, 2005.
- [179] J. Winnick, S. Jamin, and J. Rexford. Trafffic engineering between neighboring domains. Technical report, Princeton University, Princeton, New Jersey, USA, 2002. (http://www.es.princeton.edu/~jrex/publications.html).
- [180] L. Wolsey. Integer Programming, John Wiley & Sons, 1998.
- [181] R. Yager. Constrained OWA aggregation. Fuzzy Sets Systems, 81:89-101, 1996.
- [182] R. Yager. On the analytic representation of the leximin ordering and its application to flexible constraint propagation. European Journal of Operational Research, 102:176-192, 3997.
- [183] M. Żotkiewicz and W. Ben-Ameur. More adaptive robust stable routing. In Proceedings of the GLOBECOM 2010, Miami, Florida, USA, 2010.
- [184] M. Żotkiewicz and W. Ben-Ameur. Volume-oriented routing and its modifications. Telecommunication Systems, 2011. published online.
- [185] M. Żotkiewicz, M. Pióro, and A. Tomaszewski. Complexity of resilient network optimization. European Transactions on Telecommunications, 20(7):701-709, 2009.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-81247d7d-ea7e-47ea-9156-89c66c3249b0