BazTech - Yadda

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: płaszczyzna cięcia

Sortuj według:

Ogranicz wyniki do:

Optimisation of telecommunications transport networks

Tomaszewski A.

Prace Naukowe Politechniki Warszawskiej. Elektronika

2013

z. 189

9-190

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.