Peer-to-peer fractal models: a new approach to describe multiscale network processes

Abstract.

Because of the packet switching-oriented applications, LAN and WAN data traffics are characterised by high burstiness and nonstationary operation. Knowledge of the statistical and dynamical features of packet flow has a wide potential for QoS management purposes. This paper reviews a fractional calculus formalism that could be employed to analyse the nature of network traffic and to predict packet-level processes. We refer to this as the telenetics model design. The application potential and the limitations of the methods used to describe the differential and integral properties of network packet dynamics are discussed.

Keywords: fractal calculus, traffic models, burstiness.

1. Introduction.

This work belong to a line of research that attempts to develop new models of the data traffic at the different layers of WAN/LAN protocol hierarchy. Such models have to become an important issue of empirical analysis of traffic behaviour. It has been confirmed by many studies [1,2,3] that network signals such as the time series of number of packets indicates random fractals properties like similar burst structure, multiscale variability and multiplicative cascades. Such peculiarities may be caused by several reasons main of which are: high dynamics of individual connections and heavy-tailed statistical distributions of congested periods.

Figure. 1: Round trip time (RTT) process. The top - absolute values of RTT delay; the bottom - fractal structure of packets flow which exceed 600 ms threshold.

From the models design point of view fractal properties implies the existence of concentrated periods at wide range of time intervals (see time intervals 1530-1550 sec, or 3050-3060 sec, Fig.1). In contrast to Gaussian process which can take negative value real traffic is inherently positive. If X there is a positive value process and average value is not equal to zero, neither X nor X-M{X} can not be precisely self-similar processes , however sequence X-M{X} can be asymptotically self-similar. Moreover self-similarity features on all scales hold in statistical sense and as a result correlation function of the network process like RTT delay decays much more slowly than by an exponential. So, correlation structure of packet streams in modern computer network stand in contrast with classical statistical models. That is why the traffic models such as Poisson, Markov or ARMA models could not be used to explain the empirical observed fractal-like behaviour of packets flow. Therefore there is a great need for new analytical model to help improve modern networks and understand fractal behaviour of network processes. In any case fractal is real-world general phenomena and its features has to be analysed from the theoretical and practical points of view both.

2. Experimental analysis.

The packets traffic transmitted via virtual path are queued at intermediate nodes or routers and multiplexed with local data tributaries. Due to experiencing casual delays each packets exhibit non-trivial dynamics behaviour which affected close-loop feedback control protocol which often use for congestion control (Fig.2). Therefore routers queues where data are delayed and often dropped is critical part of all virtual path. A better understanding of the traffic dynamics and statistical features is a key issue in the design and development of control algorithms and protocols. It is well known that the first-order statistics of random delays in internal router's buffers provide informational regarding the length of a burst, when the second-order statistics - holds parameters of neighbouring irregularities and its spectral density. The negative difference between inter departure and inter arrival times of packets corresponds to a clustering of packets but positive one - to dispersion of packets and excessive delay.

In any case clustering of packets increases the probability of loss and has an influence on the QoS parameters of network traffic. To provide a complete description of such influence it is necessary to get a handle of small and large time scaling features of network traffic. In this case only multiscales models allow us to refine the fractal nature of network traffic both qualitatively and quantitatively

Fig.2. Internal structure of network virtual path.

Virtual path is given by a finite sequence of intermediate nodes xi and links. Each intermediate node x_i is characterised by causal value t or time of packet transfer from the node x_i to the next node x_i+1. The variable t includes the packet delay in the router's buffer and the packet propagation time to the next node. Network environment and traffic behaviour can be reflected in the two types of observed characteristics: packet per second rate p/s(k) and round trip time sequence or RTT(k) delay (Fig.3). Variable k is a discrete time variable which corresponds to measuring process.

Fig 3. Two types of network processes: top - RTT(k) delay,
bottom - packet per second rate p/s(k).

To investigate a fractal-like of property of the network process (X_k k=1,2,... for example) it is possible used an absolute statistical moments function defined by expression

(1)

where - statistical operator. If process (1) has of self-similarity property, then the value is proportional to value . Therefore for the fixed values q the following condition hold

(2)

and it is possible to write down

(3)

On can use (3) as a constructive definition of fractal properties. In this case a self-similarity feature is a linear dependence of changes at change of log(m). So used an inclination of on the diagram in double logarithmic scale it is possible to define a value of fractal parameters. For the analysis of fractal properties it is not enough to use first or second absolute statistical moments. In this case we shall use of non-parametrical statistics for the aggregated series given by

(4)

If changes linearly, it is possible to consider process as a multifractal. Exactly such type of changes is observed on Fig.4. On this diagrams X_k k=1,2,... is packets per second rate process or packet traffic. Parameter is a mean slope of statistical characteristics for different values of q parameter.

Fig.4. A dependence of the statistical moments
from first order (a) till fourth order (d).

The time-scale burstiness of network traffic in terms of second-order self-similarity can be investigate based on the following expression.

The experimental dependence of log{var[RTT^(m)]} from log(m), where m=1,2,..., number of blocks or RTT(m)={RTT^(m)(k)}, k=1,2,... depict on Fig.5.

Fig.5. Temporal co-variation function of RTT process.

Mean squared approximation (--- line) of experimental data has the following expression: -0.484-2.175.It is well understood that experimental discrete-time random process RTT(m) represent scaling low corresponding to parameter which less then -1. Parameter =-1 correspond to pure Poisson process. So, the statistical structure of network traffic exhibit the presence of long-range dependence and displayed fractal behaviour.

3. Analytical generalisation - statistical aspect

The motion of packets in each virtual path can be presented as a sequence of discrete spatial-temporal "jumps" between intermediate nodes on connecting lines. The time interval between "jumps" is a random variable. This variable shapes statistical dynamics of the packet switching process and directly influence the observable characteristics of network traffic. There are three possible types of models of packets trajectory (Fig.6).

Fig.6. Three types of models of packets trajectory.

Without loss of generality, we shall assume that the connection under investigation is created by the TCP protocol, and that there is end-to-end transmission control. Nevertheless, in our development of the packet flow model we shall consider processes occurring at intermediate sites and in communication lines. Let us focus our attention on the packet delivery time. Considering the problem at the level of intermediate sites the sender-to-receiver packet transmission time T can be presented as a sum of packet delays at each hop:

where t_i^L is the packet transmission time between nodes i and i+1 (the link propagation delay), t_i^B is the processing/buffering delay of the packet at node i, and M is the total number of nodes in the connection. A packet may be dropped due to a buffer overflow or routing error at an intermediate node. From the receiver's point of view, the intermediate site acts as a "trap" of packages, so in this case one may assign to variable t^B the value of infinity. Now we can construct adequate statistical model for such processes.

For this purpose we shall invoke the function of the probability density f(t) for the transition of a packet from site x_i to site x_i=1. We assume that: all intermediate sites of a virtual path contribute equally to the value of the end-to-end transmission time; the possible packet loss is due to the packet not leaving the intermediate site x_i and, thus, staying at this site forever.

Then the average time of packet delay at a site will satisfy the following statistical condition

(5)

. The corresponding expression for f(t) can be written as

(6)

Now we can evaluate the most probable number of packets at site õ at the moment t using the expression

(7)

where n₀(x) is the number of packets at site x before the packet's arrival from site x-1, and

The value of n(x) is not limited to the size of the buffer and may include all packets of the virtual connection which go through and are dropped at site x . In this notation, the equation of packet migration can be presented as

(8)

where the left part of equation (5) or

is the fractional derivative of function n(x;t) with an exponent . Analytical definition of such derivative given by the expression [4]

(9)

Taking into account the discrete character of change of the variable x, we shall solve equation (7) subject to the following initial conditions: n₀(0) = n₀ and n₀(k) = 0, k = 1,2,...,. We finally obtain

Taking into account the asymptotic property of the obtained solution, we can write

For k=1, we obtain the following expression

The calculations can be continued for any k. Now it easy to calculate the correlation function for the obtained solution. For the initial conditions one can write

As seen from this expression, the correlation function decays hyperbolically with increasing t. Therefore for <1, such processes are characterised by a fractal-like scaling behaviour (see Fig.3,4). For m=0, we obtain an expression for the variance

(10)

which is characteristic of processes with a long range dependence and an asymptotic second-order self-similarity (see Fig.5).

4. Analytical generalisation - dynamics aspect

It is necessary to make a several remarks. The fractal properties of network traffic can be directly connected with the packet switching methods. The dynamics of packet transfer can be described using fractional order differential equations, which can be solved by invoking the fractional calculus formalism. Differential equations with fractional derivatives can be formulated based on fine analysis of relevant processes. In the spatial-temporal realisation of process depict on Fig.2 the dynamic structure of virtual channel and queuing behaviour can be represent by sequence of integral operators (Fig.7). Packets travelling from source to destination pass through several internal routers and as a result demonstrate the impact of packets lost. In common case the number of intermediate nodes is a random parameter of virtual path. The mean value of this parameter is real number.

Fig.7. Dynamics structure of network virtual path.

In this case dynamic process at the destination node can be written as

This expression is fractional integral operator which corresponded to network temporal process in virtual channel. To provide a complete description of such process it is necessary to get a handle of small and large time scaling features. The non-trivial decision of this equation is

where A - border parameter, ; - Mittag-Leffler function; - fractional equation order; - microscopic parameter or packets discovering time; - macroscopic parameter of virtual channel.

The last decision allows to define a wide class of scale invariant models based on set of fractal parameters. So, dynamical and statistical features of packet traffic in virtual connection can be described by the means of fractional derivatives or fractional integral operators, which approximate processes with packets discard property and long range dependence.

Conclusion

We have shown that the assumption of a possibility of an indefinitely long packet delay at an intermediate node in packet switching networks models adequately the dropping of physical packets at a node. The "heavy-tailed" probability density function of the packet buffering delay satisfies this assumption. We have shown also that the dynamics of packet passage at a virtual connection in TCP/IP networks can be described by equations in fractional derivatives, which approximate processes with long-range-dependence. We hope that the use of the well-developed formalism of fractional calculus will contribute to our understanding of how packet traffic behaves. We believe that the LRD observed in computer network traffic measurements is a property of a general nature, characteristic of transfer processes in media and systems with losses.

References

1. Leland W.E., Taggu M.S., Willinger and Wilson D.V. On the Self-Similar Nature of Ethernet Traffic. Proceedings of ACM SIGCOMM'93, San Francisco, 1993, v 23, N 4.
2. Klivansky S.M., Mukherjee A. and Song C. On Long-Range Dependence in NSFNET Traffic, Technical Report CIT-CC-94-61, 1994, 38p.
3. Nigmatullin R.R. //Phisica Status Solidi (b) 1984. V. 124. P.389-393.
4. Nigmatulin R.R.. Fractional Integral.Theoretics and mathematics Physics , v.90, N3, 1992. ñ.354-367.(In Russian).
5. Oldham K., Spanier J. Fractional Calculus. London, New York: Press, 1973.
6. G. Babic, B. Vandalore, and R. Jain, "Analysis and Modeling of Traffic in Modern Data Communication Networks," Ohio State University Technical Report, OSU-CISRC-1/98-TR02, Feburary 1998,
7. Hosking J.R.M. Fractional Differencing. // Biometrica 68.- 1981., p. 165-176.