Wyniki wyszukiwania - BazTech

1

Anycasting in connection-oriented computer networks: Models, algorithms and results

Walkowiak K.

International Journal of Applied Mathematics and Computer Science

|

2010

|

Vol. 20, no 1

207-220

EN

Our discussion in this article centers around various issues related to the use of anycasting in connection-oriented computer networks. Anycast is defined as a one-to-one-of-many transmission to deliver a packet to one of many hosts. Anycasting can be applied if the same content is replicated over many locations in the network. Examples of network techniques that apply anycasting are Content Delivery Networks (CDNs), Domain Name Service (DNS), Peer-to-Peer (P2P) systems. The role of anycasting is growing concurrently with the popularity of electronic music, movies, and other content required by Internet users. In this work we focus on the optimization of anycast flows in connection-oriented networks. We formulate a model of anycast connections and next propose a heuristic algorithm based on the Lagrangean relaxation aimed to optimize jointly routes for anycast and unicast connections. Results of numerical experiments are presented and evaluated. Finally, we analyze briefly problems related to anycasting in dynamic routing and multi-layer networks.

2

Congestion control protocol for connection oriented networks with aperiodic feedback and non-persistent sources

Ignaciuk P., Bartoszewicz A.

Theoretical and Applied Informatics

|

2007

|

Vol. 19, No. 3

217-233

EN

In this paper the congestion control problem in a connection-oriented communication network is addressed. In the considered mutli-source network the feedback information is provided by means of control units generated by each source once every M data packets. Since the sources adjust the transmission rate only at the control unit arrival, the interval between successive rate modifications is input dependent and varies with time. A new, nonlinear strategy effectively combining the Smith principle with the proportional controller with saturation is proposed. Conditions for data loss elimination and full bottleneck link bandwidth utilization are formulated and strictly proved. The presented strategy allows for full resource usage even though the sources are not persistent. Moreover, since the controller saturation limits are fully adjustable, the algorithm performance may be easily tuned according to the existing system resources.

PL

W artykule rozważano zagadnienie kontroli przeciążeń´ w połączeniowej sieci teleinformatycznej o wielu źródłach. W analizowanej sieci informacja zwrotna o bieżącym stanie układu przekazywana jest do nadajników w jednostkach sterujących generowanych przez każde ze źródeł co M pakietów z danymi. Jednostki steruja˛ce pokonuja˛ te˛ sama˛ trase˛, co pakiety danych, zbierając informacje˛ zwrotna˛ z węzłów pośredniczących. W odbiorniku jednostki sterujące są˛ zawracane i przesyłane z powrotem do źródła, gdzie docierają˛ po okresie pełnego obiegu (ang. round trip time). Ponieważ˙ każde źródło dostosowuje prędkość´ nadawania wyłącznie w momencie odebrania jednostki sterującej, okres dyskretyzacji zależy od poprzednich szybkości emisji danych, a zatem zmienia się w czasie. W artykule zaproponowano nowy, nieliniowy algorytm sterowania prędkością˛ nadawania danych, bezpośrednio uwzględniający zmienny okres próbkowania układu. Zaproponowana strategia wykorzystuje predyktor Smitha oraz regulator proporcjonalny z nasyceniem. Zastosowanie prezentowanego rozwiązania pozwala wyeliminować´ ryzyko gubienia danych, a zarazem w pełni wykorzystać´ dostępne pasmo i uzyskać´ maksymalna˛ wydajność sieci. Pełne wykorzystanie dostępnych zasobów zagwarantowane jest również w sytuacji, gdy źródła, z uwagi na czasowe ograniczenia, nie są˛ w stanie zrealizować sygnału sterującego i nadają˛ dane z prędkością˛ mniejsza˛ od ustalonej przez regulator. Prędkości generowane przez algorytm są˛ zawsze nieujemne i ograniczone, co pozwala zastosować´ proponowana˛ strategie˛ w warunkach działania rzeczywistej sieci telekomunikacyjnej. Co więcej zaprezentowany algorytm ułatwia obsługę˛ administracyjna˛ węzła sieciowego umożliwiając elastyczne dopasowanie poziomów nasycenia regulatora do pojemności łącz przesyłowych. Wymienione właściwości zostały sformułowane w postaci twierdzeń i ściśle udowodnione, a następnie zweryfikowane symulacyjnie.

3

Quasi-hierarchical evolution algorithm for flow assignment in survivable connection-oriented networks

Przewoźniczek M., Walkowiak K.

International Journal of Applied Mathematics and Computer Science

|

2006

|

Vol. 16, no 4

487-502

EN

The main objective of this paper is to develop an effective evolutionary algorithm (EA) for the path-assignment problem in survivable connection-oriented networks. We assume a single-link failure scenario, which is the most common and frequently reported failure event. Since the network flow is modeled as a non-bifurcated multicommodity flow, the discussed optimization problem is NP-complete. Thus, we develop an effective heuristic algorithm based on an evolutionary algorithm. The main novelty of this work is that the proposed evolutionary algorithm consists of two levels. The “high” level applies typical EA operators. The “low” level is based on the idea of a hierarchical algorithm. However, the presented approach is not a classical hierarchical algorithm. Therefore, we call the algorithm quasi-hierarchical. We present its description and the results of simulation runs over various networks.

4

The Branch and Bound Algorithm for joint optimization of primary and Backup routes in Survivable Networks

Walkowiak K.

Archiwum Informatyki Teoretycznej i Stosowanej

|

2003

|

T. 15, z. 4

273-296

EN

Survivability of computer networks is an important subject. Organizational and individual users of computer network expect reliable services with guarantees of data delivery. In high-speed network technologies like Asynchronous Transfer Mode (ATM) and Multiprotocol Label Switching (MPLS) a large amount of data can be lost due to a network failure and cause significant economics loses. In this work we focus on problems of network survivability. Several network restoration methods are presented and discussed. A new optimization problem of Joint Primary and Backup Routes Assignment is formulated. As the rerouting strategy the local-destination rerouting is applied. The function of lost flow due to a failure of any single link is used as an objective function. The problem of finding the optimal assignment of connections in NP-complete. Therefore we develop an exact algorithm based on the branch and bound approach. Moreover two heuristic algorithms are proposed. Numerical results are included.

PL

Przeżywalność sieci komputerowych jest ważnym zagadnieniem. Użytkownicy indywidualni i instytucjonalni oczekują niezawodnych usług gwarantujących dostarczenie przesyłanych danych. W szybkich sieciach komputerowych takich jak ATM ( Asynchronous Transfer Mode) oraz MPLS (Multiprotocol Label Switching) wiele ważnych i cennych informacji może być utraconych wskutek awarii. W tej pracy koncentrujemy się na zagadnieniach przeżywalności sieci komputerowych. Przedstawiono i porównano kilka metod zapewniania przeżywalności w sieciach. Nowy problem optymalizacyjny równoczesnego wyznaczania tras podstawowych i zapasowych został sformułowany. Jako metodę restoracji sieci po awarii wybrano restorację lokalno-globalną. Funkcja utraconego przepływu po awarii pojedynczego łącza została użyta jako funkcja kryterialna. Rozważany problem jest NP.-zupełny. Dlatego zaproponowano algorytm dokładny oparty na metodzie podziału i oszacowań. Dodatkowo przedstawiono dwa algorytmy przybliżone. Dołączono wyniki eksperymentów obliczeniowych.

5

Niezawodność w sieciach komputerowych zorientowanych połączeniowo

Walkowiak K.

Telekomunikacja Cyfrowa : technologie i usługi

|

2001/2002

|

T. 4

38--48

PL

W ostatnich latach jesteśmy świadkami szybkiego rozwoju sieci komputerowych. W wielu dziedzinach życia sieci komputerowe używane są jako podstawowy środek służący do przesyłania wielu rodzajów informacji. Awaria elementu sieci komputerowej może mieć duże znaczenie, gdyż nawet krótkotrwała przerwa w transmisji powoduje utratę wielu informacji. Konsekwencją awarii mogą być: straty finansowe, konflikty polityczne, ludzkie zdrowie. Stąd wzrost znaczenia kryteriów niezawodnościowych służących do projektowania przeżywalnych (ang. survivable) i samonaprawialnych (ang. selfhealing) sieci komputerowych. W tej pracy poruszono zagadnienia związane z niezawodnością sieci komputerowych zorientowanych połączeniowo, gdyż w większości sieci szkieletowych używane są techniki połączeniowe. Skoncentrowano się na dwóch popularnych technikach: ATM (ang. Asynchronous Transfer Mode) oraz MPLS (ang. Multiprotocol Label Switching). Przedstawiono oraz porównano najważniejsze metody służące do zapewniania niezawodności. Dodatkowo przeanalizowano różne sposoby oraz algorytmy służące do projektowania niezawodnych sieci komputerowych.

EN

Currently we are witnesses of tremendous development of computer networks. Many organizations, institutions, companies use computer networks as a primary medium for transmitting of many kind of information. Service disruptions in modern networks, are expected to be important, since loss of services and traffic in high-speed fiber systems could cause a lot of damages including economic loses, significant revenue loss, political conflicts, human health. Hence engineers and network companies work on self-healing restoration methods to provide network reliability and survivability. In this paper problems of network reliability and survivability in connection oriented networks are addressed, since most of backbone network technologies are connection oriented. Two techniques: ATM and MPLS are presented, discussed and compared with special focus on main methods proposed to provide reliability and survivability. Furthermore the most important techniques and algorithms applied in the process of reliable network design are analyzed.