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

Tabu Search Algorithm for Survivable Network Design Problem with Simultaneous Unicast and Anycast Flows

Gładysz J., Walkowiak K.

International Journal of Electronics and Telecommunications

|

2010

|

Vol. 56, No. 1

41-47

EN

In this work we focus on the problem of survivable network design for simultaneous unicast and anycast flows. This problem follows from the growing popularity of network services applying the anycast paradigm. The anycasting is defined as one-to-one-of-many transmission and is applied in Domain Name Service (DNS), peer-to-peer (P2P) systems, Content Delivery Networks (CDN). In this work we formulate two models that enables joint optimization of network capacity, working and backup connections for both unicast and anycast flows. The goal is to minimize the network cost required to protect the network against failures using the single backup path approach. In the first model we consider modular link cost, in the second we are given a set of link proposal and we must select only one of them. Because these problems are NP-hard, therefore optimal solutions of branch-and-bounds or branch-and-cut methods can be generated for relatively small networks. Consequently, we propose a new heuristic algorithm based on Tabu Search method. We present results showing the effectiveness the proposed heuristic compared against optimal results. Moreover, we report results showing that the use of anycast paradigm can reduce the network cost.

5

Wdrażanie usług korzystających z adresacji anykast - dyskusja problemów i zagrożeń

Chodorek A., Chodorek R. R., Pach A. R.

Telekomunikacja Cyfrowa : technologie i usługi

|

2005

|

T. 7

1--10

PL

Schemat adresacji anykastowej został wprowadzony w 1993 roku dokumentem RFC 1546. Dwa lata później, adresacja anykastowa została włączona do nowej wersji (szóstej) protokołu IP. Anykast pozwala na transmisję typu 1-do(1zN), zorientowaną na usługę. Anykastowy datagram IP jest przesyłany do najbliższej stacji należącej do grupy stacji identyfikowanych przez ten sam adres anykastowy. W artykule zostanie przedstawiona dyskusja problemów i zagrożeń związanych z wdrażaniem usług korzystających z adresacji anykast.

EN

The IP anycast address scheme was introduced by RFC 1546 in 1993. Two years later, anycasting became a part of IPv6 networks. Anycast allows the service-oriented, one-to-one-of-many transmission. The IP anycast datagram is delivered to the nearest host, which belongs to the group of hosts identified by common anycast address. In the paper, the main challenges of practical application of anycast-based services will be discussed.

6

Koncepcja systemu multikastowej aktualizacji zasobów serwerów korzystających z adresacji anykastowej

Chodorek R. R., Chodorek A., Pach A. R.

Telekomunikacja Cyfrowa : technologie i usługi

|

2005

|

T. 7

29--38

PL

Anykast jest nowym schematem adresacji, dostarczającym usługi transmisyjnej typu 1-do(1 zN). Anykast jest adresacją zorientowaną na usługę - każda usługa ma swój predefiniowany adres IP, identyczny dla wszystkich serwerów, które świadczą tę usługę, niezależnie od ich lokalizacji geograficznej. Wybór serwera, który będzie świadczył usługę danemu użytkownikowi (najlepiej najbliższego), następuje w sposób automatyczny. Aby usługa korzystająca z adresacji anykast mogła efektywnie funkcjonować, dane na wszystkich serwerach informacyjnych, z którymi może połączyć się użytkownik muszą być spójne i muszą być aktualizowane jednocześnie. W artykule zaprezentowana zostanie koncepcja efektywnej aktualizacji zawartości serwerów, zrealizowana na bazie transmisji multikastowej.

EN

Anycast is a new addressing scheme, which provides a one-to-one-of-many communication service. Anycast is a service-oriented addressing - each service has its own, pre-defined IP address, identical for all servers provides the service, apart from their geographical location. The IP packet is delivered to the one of servers with the same anycast address (preferably the closest one) and the server selection take place automatically. The anycast-based service will work effectively only if data stored in all servers are coherent and if they are updated simultaneously. In the paper, a concept of multicast updating of content of servers which utilize anycast addressing is presented.

7

IPv6 jako platforma dla nowych usług sieciowych

Chodorek R.

Telekomunikacja Cyfrowa : technologie i usługi

|

2000

|

T. 3, z. 1

52-62

PL

Rozwijające się aplikacje multimedialne stawiają duże wymagania w stosunku do sieci transmisyjnej. Nie wystarczy zwiększyć szybkość transmisji danych. Dla wielu aplikacji trzeba wprowadzić nowe usługi sieciowe. Dlatego też wprowadza się nowe schematy adresacji, a co za tym idzie - nowe usługi związane z dostarczaniem danych: multicast i anycast. Pozwalają one na zwiększenie efektywnej przepustowości sieci. Innym ważnym zagadnieniem jest zapewnienie wiarygodności i poufności przesyłanych danych. W artykule zostaną przedstawione nowe usługi warstwy sieciowej zaimplementowane w IPv6. Pozwalają one na zwiększenie efektywności pracy sieci i tworzenie nowych usług sieciowych.

EN

New application required new effective services. Current network use new technologies in physical and data layer and can transmit data in higher rates with lower error bit rate. Application requirements grow up faster than network performance. New services in network layer: multicast and anycast can speed up some application and reduce network traffic. In paper new services in IPv6 was presented. The IPv6 protocol improves network performance and allows build new network services.