Wyniki wyszukiwania - BazTech

1

Approximation models for the evaluation of TCP/AQM networks

Marek Dariusz, Domański Adam, Domańska Joanna, Szyguła Jakub, Czachórski Tadeusz, Klamka Jerzy, Filus Katarzyna

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2022

|

Vol. 70, nr 4

art. no. e141986

EN

The article proposes a model in which Diffusion Approximation is used to analyse the TCP/AQM transmission mechanism in a multinode computer network. In order to prevent traffic congestion, routers implement AQM (Active Queue Management) algorithms. We investigate the influence of using RED-based AQM mechanisms and the fractional controller PIγ on the transport layer. Additionally, we examine the cases in which the TCP and the UDP flows occur and analyse their mutual influence. Both transport protocols used are independent and work simultaneously. We compare our solution with the Fluid Flow approximation, demonstrating the advantages of Diffusion Approximation.

2

Heavy-traffic approximations for a layered network with limited resources

Aveklouris A., Vlasiou M., Zhang J., Zwart B.

Probability and Mathematical Statistics

|

2017

|

Vol. 37, Fasc. 2

497--532

EN

Motivated by a web-server model, we present a queueing network consisting of two layers. The first layer incorporates the arrival of customers at a network of two single-server nodes. We assume that the interarrival and the service times have general distributions. Customers are served according to their arrival order at each node and after finishing their service they can re-enter at nodes several times for another service. At the second layer, active servers act as jobs that are served by a single server working at speed one in a processor-sharing fashion. We further assume that the degree of resource sharing is limited by choice, leading to a limited processor-sharing discipline. Our main result is a diffusion approximation for the process describing the number of customers in the system. Assuming a single bottleneck node and studying the system as it approaches heavy traffic, we prove a state-space collapse property.

3

Diffusion approximation of recurrent schemes for financial markets, with application to the Ornstein-Uhlenbeck process

Mishura Y.

Opuscula Mathematica

|

2015

|

Vol. 35, no. 1

99--116

EN

We adapt the general conditions of the weak convergence for the sequence of processes with discrete time to the diffusion process towards the weak convergence for the discrete-time models of a financial market to the continuous-time diffusion model. These results generalize a classical scheme of the weak convergence for discrete-time markets to the Black-Scholes model. We give an explicit and direct method of approximation by a recurrent scheme. As an example, an Ornstein-Uhlenbeck process is considered as a limit model.

4

Badanie skalowalności modeli sieci komputerowych wykorzystujących aproksymację dyfuzyjną wraz ze zwiększeniem rozmiaru modelowanej sieci

Nycz M., Czachórski T.

Studia Informatica

|

2012

|

Vol. 33, nr 3A

63-78

PL

Zmienne natężenie ruchu generowanego przez aplikacje internatowe, np. multimedialne, a także przyjęta przez protokół TCP zasada regulacji natężenia transmisji w funkcji wykrytego obciążenia sieci, określanego na podstawie strat lub czasu transmisji, powodują, że natężenie transmisji interaetowych jest permanentnie zmienne w czasie, a zmiany natężenia i dynamika tych zmian muszą być uwzględnione w ocenie algorytmów sterowania ruchem i unikania przeciążeń. Modelowanie struktur w Bitemecie wymaga z kolei dostosowania istniejących metod i modeli do analizy bardzo dużych konfiguracji sieciowych. Niniejsza praca bada pod kątem obliczeń numerycznych znany model matematyczny, umożliwiający analizę stanów nieustalonych w stanowisku obsługi i ich sieci, wykorzystujący metodę aproksymacji dyfuzyjnej. Zbadano wpływ poszczególnych parametrów modelu i rozmiaru sieci na całkowity czas obliczeń, a więc na skalowalność metody.

EN

Varying intensity of traffic generated by Internet applications such as multimedia, together with the TCP protocol rules to regulate the intensity of the detected transmission as a function of network load which is determined on the basis of loss or transmission time, casue that the intensity of Internet broadcasts is continuously variable in time, therefore intensity changes and dynamics of these changes must be included in the evaluation of algorithms for traffic control and congestion avoidance. Modeling of the structures on the Internet, in turn, requires adaptation of existing methods and models for the analysis of transient states at the service station and their networks, using the diffusion approximation method. The influence of various parameters of the model and size of the network to the total compupation time was investigated and thus the scalability of the method.

5

Porównanie metod analizy efektywności na przykładzie serwera aplikacji w sieci lokalnej

Czachórski T., Grochla K., Józefiok A., Nycz T.

Studia Informatica

|

2011

|

Vol. 33, nr 3A

7-20

PL

W artykule przedstawiono model kolejkowy służący do oceny funkcjonowania dużego systemu sieciowego, w skład którego wchodzi rozbudowany system bazodanowy. Opisywany system jest systemem rzeczywistym. Zebrane wyniki pracy systemu posłużyły do budowy modelu działania aplikacji interakcyjnych, na podstawie łańcuchów Markowa, aproksymacji dyfuzyjnej i symulacji zdarzeń dyskretnych. Porównanie ich z rzeczywistymi wynikami umożliwiło sprawdzenie przydatności użytych metod w rzeczywistych warunkach.

EN

The article presents a queueing model for performance evaluation of a large database system at an assurance company. Measurements were collected inside the working system to construct a synthetic model of applications activities. We apply simulation, Markov and diffusion models - their comparison, based on real data, may better verify the utility of particular methods than usual academic examples.

6

Modeling the IEE 802.11 networks MAC layer using diffusion approximation

Czachórski T., Grochla K., Nycz T., Pekergin F.

Theoretical and Applied Informatics

|

2009

|

Vol. 21, No. 3-4

205-223

EN

The article presents an analytical model of wireless networks using the IEEE 802.11 protocol to access the transport medium. The model allows to determine such key factors of the quality of service as transmission delays and losses. The model is based on diffusion approximation approach whichwas proposed three decades ago to model wired networks. We show that it can be adapted to take into consideration the input streams with general interarrival time distributions and servers with general service time distributions. The diffusion approximation has been chosen because of fairly general assumptions of models based on it, hard to be represented in Markov models. A queueing network model can have an arbitrary topology, the intensity of transmitted flows can be represented by non-Poisson (even selfsimilar) streams, the service times at nodes can be defined by general distributions. These assumptions are important: because of the CSMA/CA algorithm, the overall times needed to sent a packet are far from being exponentially distributed and therefore the flows between nodes are non-Poisson. Diffusion approximation allows us also to analyse the of transient behaviour of a network when traffic intensity is changing with time.

PL

Przedstawiono model analityczny sieci bezprzewodowej, w której dostęp do łącza jest zgodny ze standardem IEEE 802.11. Model pozwala wyznaczyć podstawowe dla oceny efektywności pracy sieci parametry, takie jak opóźnienie transmisji i prawdopodobieństwo straty przesyłanych pakietów. Model wykorzystuje metodę aproksymacji dyfuzyjnej, jedną z metod tworzenia kolejkowych modeli sieci komputerowych, stosowaną od ponad trzydziestu lat w modelowaniu sieci przewodowych. Z punktu widzenia teorii kolejek, do zalet aproksymacji dyfuzyjnej nalezą: możliwość analizy stanów nieustalonych, a więc opisu zachowania się kolejek przy zmiennych w czasie natężeniach transmitowanych strumieni danych, uwzględnienie w opisie stanowisk dowolnych rozkładów między nadchodzącymi zadaniami i dowolnych czasów ich obsługi, opis dowolnych topologii sieci stanowisk obsługi. Są to cechy modelu bardzo pożądane także przy opisie sieci bezprzewodowych, gdzie w wyniku stosowania w standardzie IEEE 802.11 algorytmu CSMA/CA rywalizacyjnego dostępu do łącza, transmitowane strumienie danych odbiegają mocno od strumieni Poissona, a przesyły charakteryzują się zmiennym natężeniem. Artykuł pokazuje, jak rywalizacyjny algorytm dostępu do łącza wpływa na wartość średnią i wariancję czasu obsługi uwzględniane w modelu dyfuzyjnym, a następnie na parametry przesyłanych strumieni danych.

7

Priority Preemptive Queues - Transient State Models

Czachórski T., Nycz T., Pekergin F.

Theoretical and Applied Informatics

|

2008

|

Vol. 20, No. 2

99-115

EN

The article presents a diffusion approximation model applied to investigate the behaviour of priority queues. Diffusion approximation allows us to include in queueing models fairly general assumptions. First of all it gives us a tool to consider in a natural way transient states of queues, which is vary rare in classical queueing models. Then we may consider input streams with general interarrival time distributions and servers with general service time distributions. Single server models may be easily incorporated into the network of queues. Here, we apply the diffusion approximation formalism to study transient and steady-state behaviour of G/G/1 and G/G/1/N priority preemptive models. The models can be easily converted to nonpreemptive queueing discipline. Also the introduction of self-similar traffic is possible. The models may be useful in performance evaluation of mechanisms to differentiate the quality of service e.g. in WiMAX, metro networks, etc.

PL

Artykuł przedstawia kolejkowy model systemu z obsługą priorytetową. Wykorzystano w nim metodę aproksymacji dyfuzyjnej, która pozwala na przyjęcie bardziej ogólnych założeń niż jest to możliwe w przypadku dokładnych analitycznych modeli teorii kolejek. Rozwiązując równania dyfuzji aproksymujące liczbę klientów w kolejce każdego poziomu priorytetowego, możemy w naturalny sposób opisywać stany nieustalone kolejki, co jest istotne przy modelowaniu pracy sieci komputerowych, w których natężenie transmisji ulega ciągłym zmianom. Można też wprowadzić do modelu ogólne rozkłady odstępów czasu między nadejściami klientów oraz ogólne rozkładu czasów obsługi. Wykorzystanie aproksymacji dyfuzyjnej umożliwia też uwzględnienie w modelu samopodobnego (o długoterminowej autokorelacji) natężenia strumienia wejściowego. Model pojedynczego stanowiska jest łatwo rozszerzalny na sieć podobnych stanowisk. Przedstawione rezultaty dotyczą stanowisk typu G/G/1 i G/G/1/N z regulaminem priorytetowym przerywalnym (bezwzględnym), tzn. obsługa jest przerywana w momencie nadejścia klienta o wyższym priorytecie i kontynuowana w chwili, gdy w systemie nie ma już klientów wyższego priorytetu. Model może być rozszerzony na przypadek systemu z priorytetami nieprzerywalnymi. Wyniki mogą być przydatne w analizie różnicujących jakość usług mechanizmów szeregowania pakietów, np. w ruterach protokołu IP, w sieciach typu WiMAX, w elementach dostępowych lektroniczno-optycznych sieci metropolitalnych.

8

Diffusion model of parallel servers - transient state analysis

Czachórski T., Fourneau J.-M., Nycz T., Pekergin F.

Theoretical and Applied Informatics

|

2008

|

Vol. 20, No. 3

179-198

PL

Artykuł przedstawia model stacji obsługi typu G/G/N/N – a więc stacji zawierającej N równoległych kanałów obsługi, bez możliwości tworzenia kolejki, ze strumieniem wejściowym o dowolnym rozkładzie odstępów czasu pomiędzy nadejściem kolejnych klientów i z dowolnym rozkładem czasów obsługi. Zastosowanie metody aproksymacji dyfuzyjnej pozwala na opis zarówno stanów ustalonych, jak i nieustalonych (co jest niewykonalne przy zastosowaniu dokładnych klasycznych metod teorii kolejek) pracy takiego stanowiska. Dokładność metody jest oceniona przy użyciu dwu przykładów numerycznych, gdzie wyniki aproksymacji są porównane z wynikami symulacji. Symulacja stanów nieustalonych oznacza powtórzenie wiele tysięcy razy symulowanego przebiegu i uśrednienie wszystkich uzyskanych trajektorii. Opracowany model pojedynczego stanowiska może być łatwo rozwinięty do sieci o dowolnej topologii zawierającej stanowiska stanowiska G/G/N/N oraz G/G/1/N. Przykłady numeryczne pokazują też możliwości zastosowania modeli: jeden z przykładów odnosi się do modelowania centrów obsługi telefonicznej, a drugi przedstawia model działania mechanizmu przesuwnego okna – znanego algorytmu kontroli liczby pakietów wchodzących do sieci.

EN

The article presents a diffusion approximation model of a G/GN/N station – N parallel servers without queueing. Diffusion approximation allows us to include in queueing models fairly general assumptions. First of all it gives us a tool to consider in a natural way transient states of queues, which is very rare in classical queueing models. Then we may consider input streams with general interarrival time distributions and servers with general service time distributions. Single server models may be easily incorporated into a network of queues. Here, we apply the diffusion approximation formalism to study transient behaviour of G/G/N/N station and use it to construct a model of a typical call centre and to study the sliding window mechanism, a popular Call Admission Control (CAC) algorithm.

9

A model of TCP flows dynamics

Czachórski T., Grochla K., Pekergin F.

Theoretical and Applied Informatics

|

2006

|

Vol. 18, nr 4

293-310

EN

The fluid-flow approximation models iuvestigate with much success the dynamics and stability of TCP/RED connections. Their main assumption is that the fluctuations of variables characterizing the behaviour of the couuectioiis are relatively small, that enables the linearization of model and the use of traditional control analysis tools to obtain such measures as Bode gain, phase margins, tracking error or delay margin. The coutribution of this article is twofold: (i) preserving linear fluid-flow model, we propose its extension to the case when a network is composed of wired and wireless part. In this case we consider a variant of TCP algorithiu (TCP-DCR) and fluid-flow differential equations representing the size of congestion window. mean queue at the bottleneck router and loss probability at a RED queue are supplemented with terms representing constant loss probability due to transmission in wireless pait and probability that a fraction of these errors is recovered by a liuk levei mechanism. The decrease of congestion window due to TCP mechanism is delayed to allow the link protocol to deal with the errors. The nonlinear model is linearized and may be used to check the stability of closed-loop control. (ii) We propose to replace the linear fluid flow model of the congested router queue and its AQM politias by more complex one, based on diffusiou approximation. The model will allow us to follow the queue evolution and its dynamics as well as the dynamics of congestion control, also when the transmission is far from the working point, including the case of saturated buffer. It might be especially useful when the counection dynamics is investigated in presence of large uncontrolled flows of UDP.

PL

Modele oparte na aproksymacji płynnej pozwalają na analizy funcjonowania połączeń TCP w obecności aktywnych metod zarządzania kolejką, takich jak RED. Wykorzystując lineralizacje modelu aproksymacji płynnej wokół punktu pracy, można dokonać badania stabilności połączenia TCP wykreślając wykresy Bode'go oraz Nyquista. W artykule rozwinięto dwa zagadnienia: (i) Zaproponowano rozszerzenie modelu aproksymacji płynnej znanego z Literatury o przypadek sieci zbudowanej z 2 części - przewodowej i bezprzewodowej. Autorzy rozpatrują wariant algorytmu regulacji rozmiaru okna protokołu TCP o nazwie TCP-DCR, dla którego wyznaczono równania różniczkowe aproksymacji płytnnej opisujące rozmiar okna TCP. długość kolejki oraz prawdopodobieństwo strat pakietów w koejce RED, uwzględniające straty pakietów w bezprzewodowej części sieci. Opracowany model jest następnie zlineralizowarry w celu przeprowadzenia analizy stabilności, (ii) Autorzy proponują zastąpić liniowy model przeciążonego rutera modelem opartym na aproksymacji dyfuzyjnej, pozwalającym na bad zmian długości kolejki w obecności zewnętrznych źródeł ruchu np. UDP.

10

A novel diffusion process with jumps to study an electronic-optical edge router

Czachórski T., Pekergin F.

Archiwum Informatyki Teoretycznej i Stosowanej

|

2005

|

T. 17, z. 2

87-99

EN

The article presents a diffusion approximation model applied to investigate the process of filling a large optical packet by smaller and coming irregularly electronic packets. The use of diffusion approximation enables us to include the general distributions of interarrival times, also the self-similarity of representing the end of the filling the buffer due to arrival of too large packets and we give the transient solution to this process. The model allows us to study the distribution of interdeparture times and the distribution of the space occupied in the optical packet.

PL

Metoda aproksymacji dyfuzyjnej została wykorzystana do opisu pracy węzła brzegowego, leżącego na granicy sieci elektronicznej i sieci całkowicie optycznej, zajmującego się formowaniem dużych pakietów optycznych o stałej wielkości z pakietów elektronicznych - mniejszych, nadchodzących nieregularnie i charakteryzujących się zmienną wielkością. Zastosowanie aproksymacji dyfuzyjnej umożliwia uwzględnienie w modelu dowolnego charakteru strumienia wejściowego pakietów, w tym samopodobieństwa tego strumienia oraz badania stanów nieustalonych, wywołanych zmiennym w czasie natężeniem strumienia napływających pakietów. Zaproponowano proces dyfuzji ze skokami, które odzwierciedlają zakończenie napełniania bufora pakietu optycznego w całości lub w momencie nadejścia Pakietu elektronicznego, który już nie mieści się w pozostałej wolnej części bufora. Model pozwala analizować stopień wypełnienia pakietów optycznych, a także rozkład odstępów czasu pomiędzy wysłaniem kolejnych pakietów, a więc zbadać, czy samopodobieństwo obserwowane w strumieniach wejściowych jest przenoszone w strumieniu w strumieniu pakietów optycznych. Pozwala również określić stopień wypełnienia pakietów optycznych.

11

Diffusian approximation in analysis of ATM traffic control mechanisms

Chydziński A.

Archiwum Informatyki Teoretycznej i Stosowanej

|

2003

|

T. 15, z. 3

207-222

EN

In this paper a framework of analysis of threshold-based ATM traffic control mechanisms is presented. The proposed approach is based on two foundations: renewal decomposition and diffusion approximation. These tools enables us to carry out steady-state and transient analysis of the length of the queue in the buffer and gives quite accurate trough simple formulas. Detailed calculations and numerical examples for oscillating systems are presented.

PL

W artykule pokazane zostały podstawy analizy mechanizmów kontroli ruchu opartych o wartości progowe w sieciach ATM. Proponowane podejście wykorzystuje dwa narzędzia: teorię odnowy i aproksymację dyfuzyjną. Umożliwiają one analizę stanu kolejek w buforach zarówno w stanie ustalonym jak i nieustalonym dając dość precyzyjne, choć proste wzory przybliżone. Szczegółowa analiza przy wykorzystaniu tych narzędzi oraz przykładowe wyniki numeryczne zostały pokazane dla systemów oscylujących.

12

Diffusion approximation and Markovian models of RED control mechanism

Atmaca T., Czachórski T., Laalaoua R.

Archiwum Informatyki Teoretycznej i Stosowanej

|

2001

|

T. 13, z. 4

343-354

EN

The IP networks are faced today with difficult task of satisfying the needs of connections requiring QoS by sharing the same physical resources, e.g. bandwidth and buffers. Buffers are a key component of packet-switched network, as they absorb burst arrivals of packets and hence reduce losses. Larger buffers can absorb larger bursts but they tend to build up long queues and increase queuing delays. It is believed that RED (Random Early Defection) benefits brought by RED. In particular, we examine the impact of RED on the loss rate and the mean delay. We analyze transient and stationary states. We show that the loss probability is the same for TCP and UDP traffics if RED algorithm is used. This loss rate of a flow going trough a RED router does not will alleviate problems related to synchronization of flows and improve QsS by intelligent dropping. In this paper, we develop two types of analytical models (Markovian and diffusion approximation) for the RED buffer management schemes, and use these models to quantify the depend of the burstiness of this flow but only on the load it generates.

PL

Sieci z protokołem IP spotykają się dzisiaj z trudnym zadaniem zaspokojenia potrzeb połączeń wymagających różnej jakości usług (QsS) poprzez dzielenie tych samych zasobów, np. szerokości pasma i buforów. Bufory są kluczowym składnikiem sieci pracujących w systemie przełączania pakietów, jako że absorbują pakiety, które nadeszły w okresach wzmożonego natężenia ruchu i poprzez to zmniejszają straty. Większe bufory mogą absorbować większą liczbę pakietów, lecz prowadzi to do wydłużania kolejek i wzrostu opóźnień. Artykuł przedstawia dwa analityczne(markowowski i dyfuzyjny) modele kolejki z algorytmem RED (Random Early Detection), o którym sądzi się, że poprawi jakość przesyłu. W artykule sprawdza się wpływ algorytmu RED na współczynnik strat i średnie opóźnienie. Analiza jest przeprowadzona dla stanów ustalonych i nieustalonych. Pokazano, że użycie algorytmy RED daje to samo prawdopodobieństwo strat dla ruchu TCP i UDP. Wyniki modeli analitycznych porównano z symulacją.

13

Modelling Time-dependent Flows of Virtual Connections in ATM Networks

Czachórski T., Pekergin F.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2000

|

Vol. 48, nr 4

619-628

EN

The paper discusses the use of diffusion and fluid flow approximations in modelling the time-varying flows of cells which belong to different connections but are routed through the same ATM network switch. When the cells are leaving the switch, their class should be known to define the next routing. In steady-state queueing models the probability that customer belongs to a class k is obtained as the ratio of the class k through put to the whole throughput passing the node. We are interested in transient analysis where the throughputs are changing and the composition of multiclass flow at the entrance of a queue is not the same as at the output: we should consider the delay introduced by the queue the distribution of which is also changing with time. Numerical examples, validated by simulation, testify that diffusion approximation approach gives satisfactionary results in the solution of this problem. The fluid flow approximation is much simpler to implement and needs relatively less computation effort but gives worse results: the reason of it is that in the modelling the delay introduced by a switch queue, the distribution of the queue is important and the reasoning based only on its mean value is oversimplified.

14

Diffusion approximation and its numerical problems in implementation of computer network models

Czachórski T., Jędruś S., Pastuszka M., Pekergin F.

Archiwum Informatyki Teoretycznej i Stosowanej

|

1999

|

T. 11, z. 1

3-24

EN

The paper discusses numerical problems arising during implementation of a software tool the goal of wich is to analyse transient states in queueing network models representing computer networks. The software tool is also presented: it is a library of classes which are written in C++. The models have the form of open networks with arbitrary topology that include G/G/1 and G/G/1/N stations. Time-dependent and autocorrelated input streams are considered as well as time-dependent service time distributions. In this framework other stations such as G/G/1/c, G/G/1/Threshold, G/G/1/Push-out, leaky-bucket, jumping window, sliding window that we have already prepared and tested their diffusion models as separate stations are to be included. The software is especially well suited to analyse transient states and to evaluate various control algorithms that prevent traffic congestion in communication networks. We discuss the drawbacks of the method related to numerical Laplace transform inversion applied in these models.

PL

Artykuł dyskutuje problemy numeryczne zaobserwowane przy implementacji oprogramowania mającego na celu analizę stanów nieustalonych w sieciach komputerowych za pomocą ich modeli w postaci sieci stanowisk obsługi. Problemy obliczeniowe wynikają głównie z niedokładności numerycznegoodwracania transformat Laplace'a - a w takiej właśnie postaci dostepne jest analityczne rozwiązanie modelu.