Wyniki wyszukiwania - BazTech

1

Bandwidth Estimation Using Network Calculus in Practice

Wasielewska Katarzyna, Borys Andrzej

International Journal of Electronics and Telecommunications

|

2019

|

Vol. 65, No. 1

133--138

EN

An available bandwidth at a link is an unused capacity. Its measuring and/or estimation is not simple in practice. On the other hand, we know that its continuous knowledge is crucial for the operation of almost all networks. Therefore, there is a continuous effort in improving the existing and developing new methods of available bandwidth measurement and/or estimation. This paper deals with these problems. Network calculus terminology allows to express an available bandwidth in terms of a service curve. The service curve is a function representing a service available for a traffic flow which can be measured/estimated in a node as well as at an end-to-end connection of a network. An Internet traffic is highly unpredictable what hinders to a large extent an execution of the tasks mentioned above. This paper draws attention to pitfalls and difficulties with application of the existing network calculus methods of an available bandwidth estimation in a real Internet Service Provider (ISP) network. The results achieved in measurements have been also confirmed in simulations performed as well as by mathematical considerations presented here. They give a new perspective on the outcomes obtained by other authors and on their interpretations.

2

Detailed Consideration of Graphical Calculation of Min-Plus Convolution in Deterministic Network Calculus

Borys A.

International Journal of Electronics and Telecommunications

|

2018

|

Vol. 64, No. 2

217--222

EN

The convolution operation used in deterministic network calculus differs from its counterpart known from the classic systems theory. A reason for this lies in the fact that the former is defined in terms of the so-called min-plus algebra. Therefore, it is oft difficult to realize how it really works. In these cases, its graphical interpretation can be very helpful. This paper is devoted to a topic of construction of the min-plus convolution curve. This is done here in a systematic way to avoid arriving at non-transparent figures that are presented in publications. Contrary to this, our procedure is very transparent and removes shortcomings of constructions known in the literature. Some examples illustrate its usefulness.

3

Operacja splotu w rachunku sieciowym - interpretacja graficzna

Borys A.

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2017

|

nr 8-9

860--863, CD

PL

Ponieważ rachunek sieciowy wykorzystuje algebrę min-plus w analizie ruchu telekomunikacyjnego, definiowana w nim operacja splotu różni się splotu znanego z klasycznej teorii systemów. Z tego też powodu czasem niełatwo sobie wyobrazić jego działanie. Jednakże pomocna może być w tym interpretacja graficzna. Temu zagadnieniu jest poświęcony ten artykuł. Wykorzystano w nim inny sposób konstrukcji krzywej splotowej niż używany w literaturze. Jest on bardziej przejrzysty i usuwa mankamenty dotychczasowego sposobu prezentacji. Jego użyteczność wykazano na paru przykładach.

EN

As network calculus uses min-plus algebra in the teletraffic analysis, the convolution operation defined in it differs from the convolution used in the classic systems theory. Because of this reason, it is sometimes difficult to imagine its operation. However, graphical interpretation can be helpful in this instance. This paper is devoted to this topic. Another way of constructing the convolution curve than the one used in the literature is used here. It is more transparent and removes drawbacks of the present one. Its usefulness is shown on a couple of examples.

4

Some remarks on practical aspects of the effective service curve use in ad hoc networks

Borys A.

Zeszyty Naukowe Akademii Morskiej w Gdyni

|

2015

|

nr 90

26--36

EN

The so-called ∈-effective service curve has been thought out for the use in a distributed call admission procedure for wireless ad hoc networks. Its practical usefulness relies upon the fact that it can be constructed on-line exploiting the measured data, and modified accordingly, when the intensity of the cross traffic changes, allowing the call admission to be matched to the system actual traffic load. In this paper, we demonstrate that this curve can be approximated by system parametric service curve for through traffic, depending upon the intensity of system cross traffic, too. We show also that an expression published in the literature that describes the ∈-effective service must be corrected and its right form is given here. This form allows the correct interpretation of servicing the through traffic in absence of the cross traffic. Moreover, we demonstrate that the use of the so-called greedy pattern of probing packets can be interpreted approximately as applying the Dirac impulse to the system through traffic input.

PL

Tak zwana ∈-efektywna krzywa serwisowa pojawiła się w literaturze przedmiotu przy rozpatrywaniu rozproszonej obsługi żądań dostępu w bezprzewodowych sieciach typu ad hoc. Jej praktyczna użyteczność polega na tym, że może ona być konstruowana w czasie rzeczywistym przy wykorzystaniu danych pomiarowych. Może ona być również na bieżąco modyfikowana w zależności od zmian intensywności tzw. ruchu krzyżowego w sieci, dopasowując obsługę żądań do aktualnego obciążenia sieci. W tym artykule pokazano, jak ∈-efektywną krzywą serwisową można aproksymować za pomocą parametrycznej krzywej serwisowej sieci dla ruchu głównego, która w tym przypadku będzie zależeć od intensywności ruchu krzyżowego. Pokazano również, że podane w literaturze wyrażenie, opisujące ∈-efektywną krzywą serwisową, nie do końca jest poprawne i musi być skorygowane. W tej pracy wyprowadzono wzór w pełni poprawny, który pozwala również na poprawny opis obsługi głównego ruchu przy braku w sieci ruchu krzyżowego. Ponadto pokazano, że użycie w pomiarach tzw. łapczywej (ang. greedy) próbkującej sekwencji bitów można zinterpretować w przybliżeniu jako użycie impulsu Diraca na wejściu do sieci dla ruchu głównego.

5

A Contribution to the System : Theoretic Approach to Bandwidth Estimation

Borys A., Wasielewska K., Rybarczyk D.

International Journal of Electronics and Telecommunications

|

2013

|

Vol. 59, No. 2

141-149

EN

The network calculus provides a theoretical background for description of traffic in computer networks. Using this tool in explanation of the so-called pathchirp method of measuring the available bandwidth, the validity and range of application of some relationships exploited are verified in this paper. The derivations are carried out in a wider context than that considered in a recent paper by Liebeherr et al. published in IEEE/ACM Transactions on Networking on network bandwidth estimation, providing thereby new insights and outcomes. These results, summarized in a table, show a means of bounding the service curve, depending upon its convexity or non-convexity property assumed and upon the linearity or non-linearity of a network considered. Moreover, it is shown here that the nonlinear network example analyzed by Liebeherr et al. can be viewed equivalently as a linear parametric network. For this network, the behaviour of the cross traffic is considered in a more detail, too.

6

Comparison of descriptions of continuous-time and teletraffic systems

Borys A., Aleksiewicz M.

Zeszyty Naukowe. Telekomunikacja i Elektronika / Uniwersytet Technologiczno-Przyrodniczy w Bydgoszczy

|

2012

|

z. 16

5--15

EN

In a fundamental book [5] on the so-called network calculus and research papers using this technique, as for example those cited in this paper, the notion of causal linear time-invariant teletraffic systems (networks) is used. It has been mentioned in [5] that these systems are analogous to the causal linear time-invariant systems (circuits) described by integral convolution (or convolution sum in the case of discrete ones) in classical systems theory. Note that networks considered in the network calculus are described by other type of convolution that uses the infimum operation. Moreover, the algebra used in the above technique is also different. This is the so-called min-plus (or max-plus) algebra. Therefore, it is not obvious that the teletraffic systems (networks) described by the infimum convolution fulfill the following basic properties: linearity, causality, time-invariance, associativity and commutativity of their convolution operator, known from the classical theory of systems. The objective of this paper is to prove or show in detail that the above properties hold.

PL

W znanej monografii nt. rachunku sieciowego (network calculus), napisanej przez J.-Y. Le Boudeca i P. Thirana, zostało wprowadzone pojęcie liniowych systemów teleinformatycznych niezależnych od czasu. Wskazano w niej na podobieństwa istniejące pomiędzy powyższą klasą systemów a liniowymi systemami analogowymi niezależnymi od czasu, jednakże zrobiono to w sposób dosyć pobieżny. W tym artykule podobieństwa te są przeanalizowane w sposób systematyczny, a także bez uciekania się do bardzo abstrakcyjnej teorii systemów opisywanych za pomocą algebry min-plus – jedynie przy wykorzystaniu elementarnych pojęć matematyki wyższej. Wiele przedstawionych tutaj wyprowadzeń nie było dotychczas nigdzie publikowanych, jak na przykład twierdzenie 1.

7

On Bounds on Cumulative Teletraffic Using Min-Plus Convolution

Borys A.

International Journal of Electronics and Telecommunications

|

2012

|

Vol. 58, No. 4

315-322

EN

Ideas and results published in two papers by R. L. Cruz in IEEE Transactions on Information Theory in 1991 gave rise to what is called now network calculus. A key role in it plays a certain inequality characterizing the behaviour of cumulative traffic curves. It defines the so-called burstiness constraint by which many kinds of traffics can be described, as for example those occurring in computer networks. Interpretation of this constraint, which can be expressed in two equivalent forms: with and without the use of min-plus convolution, can be found in papers of R. L. Cruz. Nothing however was said about how to obtain it practically, for example, for each of representatives of a family of measured cumulative traffic curves being upperbounded. This problem is tackled in this paper, and as a result, a relation between the Cruz's constraining function and an upper-bounding function of measured traffic curves is found. The relation obtained is quite general and valid also for the case of non-fulfilment of the so-called sub-additivity property by traffic curves. For the purpose of its derivation, a notion of sub-additivity property with some tolerance Δ was introduced, and the corresponding theorem exploiting it formulated and proved. Further, to complement discussion of the above relation, a minimal burstiness constraint was added to the original Cruz's inequality and related with a lower bound of a family of measured cumulative traffic curves. The derivations presented in this paper are illustrated by examples.

8

Some Principles of Network Calculus Revisited

Borys A., Aleksiewicz M., Rybarczyk D., Wasielewska K.

International Journal of Electronics and Telecommunications

|

2011

|

Vol. 57, No. 3

279-284

EN

Network calculus is a mathematical theory dealing with queueing problems in packet-switched computer networks. It provides algorithms to determine resource requirements of traffic flows using arrival and service curves and describes delays and backlogs in network systems. Network calculus framework is based on a min-plus algebra which allows to transform complex network optimization problems into analytically tractable ones. Recently, a fundamental book on principles, tools, techniques, and applications of network calculus, entitled: Network Calculus. A Theory of Deterministic Queuing Systems for the Internet, has been published by J. Y. Le Boudec and P. Thiran. Here, we refer to it in our refinements of proof of one important theorem and its extension. The objective of this paper is twofold. First, we complete one of basic results regarding a network element that is called in network calculus a greedy shaper. Second, we present also the results of some illustrative calculations and measurements of network service curve. They aim in better understanding of its properties.