Optimization of links cost for unicast and anycasttraffic

• Autorzy: Gładysz J.

Warianty tytułu

PL

Optymalizacja kosztu łączy kandydujących dla połączeń unicast oraz anycast

• Języki publikacji: EN

Abstrakty

EN

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).

PL

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.

Słowa kluczowe

EN

unicast; anycast; capacity; CFA; heuristic algorithms

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2011
• Tom: Vol. 23, No. 3-4
• Strony: 163--176
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Gładysz J.

• Chair of Systems and Networks Computer Networks Wroclaw University of Technology ul. Wybrzeże Wyspianskiego 27, Wroclaw, Poland,

Bibliografia

• 1. J. Gładysz, K. Walkowiak: Analysis of cut inequalities for the uncapacitated network design problem with simultaneous unicast and anycast flows, Advanced simulation of systems, Proceedings of the [31st International] Autumn Colloquium, MARQ, 2009. s. 47-52.
• 2. J. Gładysz, K. Walkowiak: Design of MPLS over DWDM architecture for unicast and any castflows, Lecture Notes in Computer Science. 2010, vol. 6294, s. 172-183.
• 3. M. Hofmann, L. Beaumont: Content networking :architecture, protocols, and practice,Morgan Kaufmann, San Francisco, 2005.
• 4. ILOG CPLEX 11.0 User’s Manual, France, 2007.
• 5. Ch. Metz:IP Anycast Point-to-(Any) Point Communication, IEEE Internet Computing,March-April 2002, pp. 94-98.
• 6. G. Peng: CDN: Content Distribution Network, Technical Report, sunysb.edu/tr/rpe13.ps.gz, 2003.
• 7. M. Pioro, D. Medhi: Routing, Flow, and Capacity Design in Communication and Computer Networks, Morgan Kaufmann Publishers, 2004.
• 8. SNDLIB Library of test instances for Survivable fixed telecommunication Network Design. http://sndlib.zib.de/home.action (online) 2008.
• 9. K. Walkowiak: Anycast Communication – A new Approach to Survivability of Connection-Oriented Networks, Communications in Computer and Information Science, Springer Verlag, pp. 378-389.
• 10.J. Wu: Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless and Peer-to-Peer Networks, Auerbach Publications 2006.