- Tytuł:
-
Optimization of links cost for unicast and anycasttraffic
Optymalizacja kosztu łączy kandydujących dla połączeń unicast oraz anycast - Autorzy:
- Gładysz, J.
- Powiązania:
- https://bibliotekanauki.pl/articles/375728.pdf
- Data publikacji:
- 2011
- Wydawca:
- Polska Akademia Nauk. Czytelnia Czasopism PAN
- Tematy:
-
unicast
anycast
capacity
CFA
heuristic algorithms - Opis:
-
This work presents optimization model and computational results of Capacity and Flow Assignment Problem for multilayer networks with unicast and anycast traffic. Capacity of each channel is expressed in a set of link proposal. Anycast is a network addressing and routing methodology in which datagrams from a single sender are routed to the topologically nearest node in a group of potential receivers all identified by the same destination address. We propose two heuristic algorithms based on Flow Deviation and Tabu Search method. The results of algorithms will be compared with optimal solution obtained using CPLEX package. To improve execution time of exact algorithm we introduce cut inequalities. Cut inequalities are added to the optimization problem, enabling the branching phase to use this information in calculation of more effective bounds. Next, we want to examine testing networks depend on different percentage of anycast traffic, number of distribution centers (servers or replicas) and the different size of network (number of nodes, links, routes).
Poniższa praca prezentuje model optymalizacyjny oraz eksperymenty obliczeniowe dla problemu jednoczesnego wyznaczania przepustowości kanałów oraz przepływów unicast oraz anycast. Jako przepustowości kanałów użyte zostaną tzw. przepustowości kandydujące - spośród dostępnych przepustowości w danym kanale wybieramy dokładnie jedną. Takie rozwiązanie przyjęte zostanie w górnej warstwie. W dolnej warstwie będziemy rozważać przepustowości modularne - przepustowość kanału wyrażona jest w ilości modułów potrzebnych do zainstalowania w łączu. Anycast jest nowym rodzajem przepływów w sieciach komputerowych, możliwym do zastosowania w szóstej wersji protokołu IP. Jest to transmisja jeden do wielu, w której użytkownik może wysłać/pobrać dane do jednego spośród serwerów w sieci oferujących daną usługę. W pracy zaproponowane zostały dwa algorytmy heurystyczne. Pierwszy oparty jest o metodę FlowDeviation, drugi na zaproponowanej przez Glovera metodzie Tabu Search. Oba algorytmy zostały wcześniej zaproponowane i opisane przez autora dla przepustowości modularnych. Do znalezienia rozwiązań optymalnych zostanie użyty pakiet programowania liniowego CPLEX. Rozważany problem jest problemem NP.- zupełnym. Oznacza to iż dla dużych sieci komputerowych znalezienie rozwiązania optymalnego może okazać się niemożliwe. Z tego powodu do badanego problemu wprowadzone zostały tzw. funkcje odcinające. Zadaniem funkcji odcinających jest zmniejszenie przestrzeni dopuszczalnych rozwiązań, a co za tym idzie skrócenie czasu poszukiwania rozwiązania optymalnego. Do konstrukcji odpowiednich funkcji odcinających wykorzystywane są właściwości badanego problemu. Zaproponowane funkcje odcinające oraz algorytmy heurystyczne zostały przebadane dla trzech sieci komputerowych. Są to sieci komputerowe o różnej topologii, różnej liczby węzłów oraz połączeń pomiędzy węzłami. Badania miały na celu zbadanie wpływu ruchu anycast w sieci, porównanie czasu rozwiązań optymalnych z zastosowaniem funkcji odcinających oraz ocenę algorytmów heurystycznych. Wyniki przeprowadzonych eksperymentów pokazują, iż zastosowanie przepływów anycast (kosztem unicast) zmniejsza sumaryczny przepływ w sieci przy takim samym strumieniu danych wprowadzanych do sieci. Można to zaobserwować porównując proporcje przepływów unicast oraz anycast. W przypadku badań dotyczących funkcji odcinających można zaobserwować zmniejszenie czasu poszukiwania rozwiązania po dodaniu ograniczenia dotyczącego górnego ograniczenia funkcji kryterialnej. Wartość ta pochodzi z algorytmów heurystycznych. Jest to kolejny powód do dalszych prac nad tymi algorytmami. W badaniach dotyczących algorytmów heurystycznych można zaobserwować iż algorytm FlowDevation znajduje rozwiązanie dopuszczalne w czasie rzędu kilku sekund, jednak jest ono odległe od rozwiązania optymalnego o ok. 7-9%. W przypadku algorytmu Tabu Search otrzymujemy rozwiązanie dopuszczalne odległe od optymalnego o 1-3%, niemniej jednak czas działania algorytmu jest dłuższy i wynosi kilkanaście do kilkudziesięciu sekund. Należy zatem odpowiednio dobrać parametry algorytmy Tabu Search - długość listy tabu oraz liczba iteracji. W pracy dotyczącej przepustowości modularnych znajdują się szczegółowe badania dotyczące tych dwóch parametrów. - Źródło:
-
Theoretical and Applied Informatics; 2011, 23, 3-4; 163-176
1896-5334 - Pojawia się w:
- Theoretical and Applied Informatics
- Dostawca treści:
- Biblioteka Nauki
Artykuł