Wyniki wyszukiwania - BazTech

1

Optimization of links cost for unicast and anycasttraffic

Gładysz J.

Theoretical and Applied Informatics

|

2011

|

Vol. 23, No. 3-4

163-176

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.

2

Zastosowanie transmisji anycast do poprawy wybranych parametrów sieci komputerowych

Gładysz J.

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2011

|

nr 10

1544-1547

PL

Dokonano przeglądu oraz oceny zastosowania transmisji anycast w sieciach komputerowych. Opisano dwa rodzaje ruchu w sieci - unicast (połączenia jeden do jeden) oraz anycast (jeden do jeden z wielu). Zaprezentowano wyniki badań dotyczące optymalizacji ruchu w sieci przez zastosowanie przepływów anycast, jego wpływ na poprawę takich parametrów, jak koszt działania sieci komputerowej, średnie opóźnienie pakietów oraz zwiększanie niezawodności w sieci komputerowej. Przedstawiono wyniki implementacji algorytmów dokładnych oraz heurystycznych.

EN

In this paper we show review and adoption of anycast transmission in computer networks. For this purpose we describe two types of network traffic - unicast (one-to-one) and anycast (one-to-one-of-many). Next we present computational results on optimization of network traffic using anycast flows and improvement of network parameters like the network cost, total average delay function and increasing network survivability. We show some exemplary results of implementation exact and heuristic algorithms.

3

Zapewnianie przeżywalności w sieciach komputerowych wielowarstwowych z zastosowaniem przepływów anycast

Gładysz J., Mickiewicz B.

Metody Informatyki Stosowanej

|

2011

|

nr 3

49-58

EN

The paper presents problem of survivable network design in multilayer computer networks. Multilayer network is defined as such a model, which combines layers using different technologies, different protocols or different functionality. Each level has a well defined topology, type of flow, a set of proposed routes. As a model of multi-layer network we propose twolayers, based on MPLS over DWDM architecture. As a model problem, will be presented to the SCMC model (Spare Capacity Cost Multi-layer). Its objective is to minimize the cost of additional bandwidth, which shall be provided on the network to protected the network due to the failure of a single link. Since the problem is NP-complete to obtain the optimal solution will be used CPLEX optimization package. For larger networks will be proposed heuristic algorithm based on the Flow Deviation method.

4

Random Approach to Optimization of Overlay Public-Resource Computing Systems

Chmaj G., Walkowiak K.

International Journal of Electronics and Telecommunications

|

2010

|

Vol. 56, No. 1

55-61

EN

The growing need for computationally demanding systems triggers the development of various network-oriented computing systems organized in a distributed manner. In this work we concentrate on one kind of such systems, i.e. public-resource computing systems. The considered system works on the top of an overlay network and uses personal computers and other relatively simple electronic equipment instead of supercomputers. We assume that two kinds of network flows are used to distribute the data in the public-resource computing systems: unicast and peer-to-peer. We formulate an optimization model of the system. After that we propose random algorithms that optimize jointly the allocation of computational tasks and the distribution of the output data. To evaluate the algorithms we run numerical experiments and present results showing the comparison of the random approach against optimal solutions provided by the CPLEX solver.

5

Gwarancja jakości usług interaktywnych w mobilnych sieciach rozgłoszeniowych

Potrawka P., Gozdecki J., Pach A.

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2008

|

R. 81, nr 8-9

945-949

PL

Zaprezentowano rozwiązania, opracowane w ramach projektu DAIDALOS II, które mogą być w przyszłości wykorzystane do stworzenia wielodostępowej sieci, zgodnej z założeniami NGN spełniającej oczekiwania najbardziej wymagających użytkowników. Przedstawione zostały mechanizmy realizujące gwarancję jakości dla usług interaktywnych z wykorzy- staniem jednokierunkowej technologii rozgłoszeniowej, takiej jak DVB. Przedstawiono mechanizm rezerwacji zasobów sieciowych w tego typu środowisku oraz proces przełączenia użytkownika pomiędzy różnymi technikami dostępowymi z zachowaniem jakości transmisji.

EN

The goal of Next Generation Networks (NGN) and thus in DAIDALOS II network is to offer a common and scalable framework that provides communication through a number of access technologies, all supporting common signaling mechanisms for QoS session setup in unicast and multicast environments. In this paper we present solutions for the integration of unidirectional networks like DVB (Digital Video Broadcasting) in an end-to-end QoS architecture with ubiquitous access and seamless mobility for Interactive services.