Wyniki wyszukiwania - BazTech

1

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.

2

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.

3

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.

4

Stochastic Comparisons of cell losses with the PushOut access mechanism associated with arbitrary service policies

Fourneau J.-M., Pekergin F.

Theoretical and Applied Informatics

|

2006

|

Vol. 18, nr 4

279-292

EN

We compare thc number of lost cells in switches managed by the PushOut mechanism and scheduled under an arbitrary service policy, by applying the comparison of stochastic processes in the strong stochastic ordering sense. New telecommunication networks will provide Quality of Service differentiation. This implies buffer management mechanisms such as the PushOut mechanism to warrant quality for loss-sensitive sessions. Using sample-path arguments, we present the relationships between the speed of scheduling policies and the number of lost cells under PushOut mechanism.

5

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.

6

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.

7

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.

8

Dyfuzyjny model stanów nieustalonych w rozległej sieci ATM.

Czachórski T., Pekergin F.

Zeszyty Naukowe. Informatyka / Politechnika Śląska

|

1999

|

z. 36

117-132

PL

W modelowaniu pracy sieci komputerowej w warunkach zmiennego w czasie obciążenia ważną rolę spełnia właściwy opis podziału strumieni pakietów należących do różnych połączeń, które krzyżyją się w węźle sieci, a następnie rozchodzą w różnych kierunkach. Prawdopodobieństwa przynależności pakietu do danego połączenia są, w stanie nieustalonym sieci, funkcją czasu. Artykuł przedstawia sposób wyznaczania tych prawdopodobieństw i jego zastosowanie w modelowaniu sieci ATM.

EN

In modelling the performancies of computer networks working under time varying load it is important to properly describe the partitioning of traffic flows which belong to different connections and are interacting at a network switch before being dispatched further following their itinerary. The routing probabilities are time dependent. The article proposes a method to determine these probabilities, enabling this way modelling of flows in large ATM network.

9

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.

10

A diffusion model of the dynamic effects of closed-loop feedback control mechanisms in ATM networks

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

Archiwum Informatyki Teoretycznej i Stosowanej

|

1999

|

T. 11, z. 1

41-56

EN

This article proposes a model to study the performance of virtual connections in ATM networks. It is supposed that each connection has a closed-loop feedback control mechanism which allows the network to control the cell emission process at each source. When a defined congestion level is reached, ATM switches notify traffic sources contributing to the congestion. On receiving a congestion notification, the source reduces the maximal rate at which it transmits cells through the considered connection. If the source does not receive congestion messages during a certain time interval, it can start to increase its traffic rate. The model allows us to study the impact of the closed-loop control on the performance of the virtual connections through the network. The model is based on the diffusion approximation. The time-dependent queue length at each node is approximated by the value of diffusionprocess. The diffusion approximation allows to model various congestion indicators and control algorithms rather than analyse a particular protocol. Several numerical examples which relate to different types of traffic, various interconnection distances and transmission rates illustrate the use of the model.

PL

Artykuł proponuje model, za pomocą którego można badać efektywność pracy wirtualnego połączenia w sieci, wyposażonego w mechanizm kontrolny pracujący w pętli sprzężenia zwrotnego, pozwalający kontrolować natężenie strumienia pakietów emitowanego przez każde źródło. Gdy zostanie osiągnięty określony poziom zatłoczenia, przełączniki sieciowe zawiadamiają o tym źródła, strumienie których są z zatłoczeniem związane. Źródła są zobowiązane ograniczyć natężenie wysyłanego rozważanym połączeniem strumienia danych. Jeżeli źródło nie otrzymuje przez pewien czas komunikatów o zatłoczeniu, to może zwiększyć natężenie wysyłanego strumienia. Przedstawiony model pozwala badać wpływ sterowania w pętli sprzężenia zwrotnego na działanie połączenia. Model wykorzystuje metodę aproksymacji dyfuzyjnej: zależna od czasu długość kolejek w każdym węźle sieci jest przybliżona wartością procesu dyfuzji. Aproksymacja dyfuzyjna pozwala analizować stany nieustalone kolejek, uwzględnic dowolne typy strumieni wejściowych. Artykuł nie analizuje jednego ściśle określonego protokołu transmisji, lecz przedstawia zasady modelowania sterowania w pętli sprzężenia zwrotnego i możliwości adaptacji tego modelu do różnych pokrewnych algorytmów. Przykłady numeryczne uwzględniają różne typy ruchu podlegającego regulacji, szybkości transmisji i odległości między węzłami.

11

Dyfuzyjny model przełącznika sieciowego uwzględniający zmienny w czasie i skorelowany strumień pakietów.

Czachórski T., Pekergin F.

Zeszyty Naukowe. Informatyka / Politechnika Śląska

|

1998

|

z. 34

288-304

PL

Artykuł przedstawia model bufora kolejkującego pakiety w przełączniku sieci ATM przy założeniu strumienia pakietów o zmiennym natężeniu opisywanym za pomocą strumienia ON-OFF lub za pomocą strumienia modulowanego łańcuchem Markowa o większej liczbie stanów. Model wykorzystuje metodę aproksymacji dyfuzyjnej. Rozpatrzono wpływ mechanizmu cieknącego wiadra na pracę przełącznika.

EN

The article presents the performance evalution of an ATM switch queue with time-varying and correlated input. The input is modelled by a source ON-OFF or Markov modulated Poisson process having more states. The switch model is based on diffusion approximation method. The influence of the keaky-bucket control mechanizm on the switch performance is analysed.

12

Oparte na aproksymacji dyfuzyjnej modele zmiennego obciążenia w sieciach komórkowych

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

Telekomunikacja Cyfrowa : technologie i usługi

|

2001/2002

|

T. 4

31--37

PL

Artykuł przedstawia model kolejkowy fragmentu sieci komórkowej. Model jest złożony z wielu systemów obsługi typu G/G/N/N reprezentujących poszczególne komórki heksagonalne. System G/D/N/N to system z dowolnymi rozkładami czasów zgłoszeń i obsługi oraz N stanowiskami obsługi, bez możliwości tworzenia kolejki zgłoszeń. Pod pojęciem stanowiska obsługi należy rozumieć kanał, przydzielony komórce, a ściślej stacji bazowej, do realizacji połączeń, czyli do obsługi zgłoszeń. Pod pojęciem systemu obsługi należy rozumieć komórkę lub stację bazową. Metoda aproksymacji dyfuzyjnej, zastosowana przy rozwiązywaniu modelu, pozwala na analizę zachowania sieci przy zmiennym w czasie obciążeniu i umożliwia tworzenie modeli zawierających bardzo wiele stacji obsługi o dowolnej liczbie kanałów (co jest niemożliwe przy wykorzystaniu modeli markowowskich); pozwala też wyznaczać bardzo małe wartości prawdopodobieństw, co jest trudne przy stosowaniu modeli symulacyjnych.

EN

In the article, a part of a cellular mobile communication system is modelled by a queueing network of G/G/N/N service systems representing hexagonal cells, each system being connected to six neighbouring systems. Number N of parallel service stations corresponds to the number of channels. Traditional modelling techniques as Markov chain approach and simulation suffer at this type of models from their usual drawbacks: state number explosion for Markovian models and long run times necessary to obtain credible probabilities of rare events (connection loss when a user passes from one cell to another or refusal of new connection) in case of simulation models. Here, a method of diffusion approximation is used to study transient state probabilities and to investigate time-dependent performances of the network. Diffusion approximation allows one to consider a large number of cells, any number of channels and to obtain numerical results even in cases where loss probabilities are very small.