Back

New traffic model on the base of fractional calculus

V.Zaborovski (vlad@stu.neva.ru)
State Technical University of Saint-Petersburg, Russia

Y.Podgurski (podg@stu.neva.ru)
Institute of Robotics and Technical Cybernetics, Russia

S.Yegorov (ye@stu.neva.ru)
State Technical University of Saint-Petersburg, Russia

Abstract.

The model represents network traffic as a stochastic process with possible infinite mean delay is proposed. Such model may be used to explain the appearance of long-range dependency and fractal-like feature of a network data flow. The formal relationship between heavy-tailed delay distributions, hyperbolically decaying of the packet delay auto-covariance function and fractional differential equation is shown. The new interpretation of fractional calculus opens up the new area of using this well-developed mathematical tool in order to understand the local and global characteristics of the packet traffic behaviour.

Keywords: packet traffic, long-range dependence, self-similarity, fractional calculus, fractional differential equation.

1. Introduction.

Recent measurements of network traffic have shown that traffic characteristics include features that are more efficiently described in terms of fractal than conventional stochastic processes. Fractal dimension and long-range dependency in statistical moments have been found in corporate, local and wide-area networks [1-3]. As a result a correlation function of network process R(k) decays much more slowly than exponential. In fact the measured data suggest a power-low decay, that is,

R(k)~Ak-b,

where k - 0, 1, 2,... , discreet time variable; A - scale coefficient, b - fractional exponent parameter; and implying a non-summable correlation function .

A functional behaviour one can be find in different areas of natural science. In several publications its authors try to explain dependence like (1) on the base of analysis of the diffusion processes and describes the evolution of the some system with a information loss property. In such case, the fractional parameter b characterises a degree of the system "residual memory". In [4] dependence (1) is contacted to the decision of a fractional derivative equations. Though this mathematical tool is enough well-developed [5], but absence of clear physical interpretation restrict a wide application of the fractional differential equations in model design. The main object of this paper - to show how a fractional calculus can be used effectively in QoS analysis and refine the universal mechanism of "system information loss" that typical for the packet switching networks. In the paper we present the new approach to traffic model design and the strict deriving of the packet traffic dynamics equation in the virtual connection.

2. Motivation.

The QoS engineering for Internet services require the adequate models of a virtual connection, formed by packet flow. In general case such connection consists of several intermediate nodes and links. Without loss of generality we shall assume that the connection under investigation is created by the TCP protocol and there is end-to-end transmission control. Despite of it we shall consider processes in intermediate sites and communication lines (Fig.1), while constructing the packet flow model.

These processes show themselves in different types of packet delays and the actions of packet drops. Let us turn our mind to the packet delivery time. At detailed elaboration up to a level of intermediate sites (Fig.2b), the sender-to-receiver packet transmission time T may be presented as sum of packet delays at each hop.

where tiL - packet transmission time between nodes i and i+1 (link propagation delay), tiB- processing/buffering delay of a packet in the node i, M - total number of nodes in the connection.

In the modern TCP/IP networks one can consider the link propagation delay tL for the allocated virtual connection as a constant value [1]. Therefore changes of a packet transmission time, that have an essential influence on the QoS parameters, are caused by the variations of buffering delay tB.

The packet may be dropped due to buffer overflow or routing error in the intermediate node. From the receiver point of view the intermediate site acts as a "trap" of packages, and detains them forever. In this case one may assign to tB value equal to infinity. Let's note, that despite of packet loss or infinite delay the transport level protocol will ensure delivery of the given information packet using retransmission. It results in increase of the total number of transmitted packets and, hence, affects effective productivity of virtual connection.

3. Spatial - temporal model of packet distribution in TCP/IP networks

The virtual channel is given by a finite sequence of intermediate nodes x i and links. Each intermediate node is characterised by casual time t of a packet transfer to the following node. A variable t includes a packet delay in the buffer and the packet propagation time up to the following site. In this case displacement of packets between intermediate nodes can be presented as a sequence of discrete spatial "jumps" on connecting lines (Fig.2 c). The time interval between "jumps" is a random variable which equal to time of a packet transfer to the following site. Such "jumps" form statistical dynamics of packet switching process and directly influence the observable characteristics of network traffic.

For construction of mathematical model of such processes we shall enter function of probability density f(t) of the transition of a packet from the site x to the site x+1. We assume that all intermediate sites of virtual connection are equal in rights and in their contributions to a value of the end-to-end transmission time. The possible packet loss is corresponds to a condition that the packet will not leave the intermediate site x and will stay at this site forever. Then the average time of packet delay at a site satisfies to a condition

,

f(t)>0; . The corresponds expression for f(t) can be written as

.

It appears, that exactly such structure of probability density function characterises the long range statistical dependence, which are widely observed in computer networks [1-3, 7]. For the further construction of model we shall enter function F()

,

where - time of a presence of a packet in the x intermediate site of virtual connection.

Let's evaluate the most probable number of packets in the site x at the moment t using the formula

.

where no(x) - the number of packets in the site x before the packets arrival from the x-1 site.

The value n(x) is not limited to the size of the buffer and may includes all packets of virtual connection which go through and dropped in the site x.

In these designations the equation of packet migration may be represented as

,

where the left part of the equation (6) is the fractional derivative from function n(x;t) with an exponent

.

Taking into account the discrete character of change of coordinate x, we shall solve the equation (6) with the initial conditions: n0(0)=n0 and n0(k)=0, k=1,2,...,

Then we shall receive

The dependences n(k,100)/n0 are shown at the Fig.3. Taking into account, the asymptotic property of received decision, it is possible to write down

,

The dependency n(0,t)/n0 is shown at the Fig.4.

For k=1, we shall receive the following expression

.

Thus, the calculations can be continued for any k. This approach allows to calculate the correlation function of the received decision.

For the initial conditions n(0;t)=n0(t), it is possible to write down

This expression shows, that the correlation function has hyperbolically decaying concerning change of t. Therefore under condition of <1, such processes are characterised by fractal-like scaling behaviour. With m=0 we have the expression for variance

characteristic for processes with long range dependency and asymptotic second-order self-similarity.

The behaviours of c(m,t)/n02 and D(t)/n02 as functions of time t are shown at the Fig.5 and Fig.6.

Thus, the properties of the network traffic, widely discussed in the modern literature, can directly be connected with the packet switching methods, used in computer network. The processes of packet transfer can be described with operator equations, which decision turns out with use of the fractional calculus tool. Using the temporal asymptotic decisions, differential equations with fractional derivatives can be formulated, that allows to receive expressions for the second order statistical moments of arising processes. Distinctive feature of such traffic characteristics is the hyperbolically decaying of their correlation functions which should be taken into account at construction of control systems of the traffic.

The conclusion

We have shown, that the assumption about a possibility of the indefinitely large packet delay in the intermediate node in the packet switching networks adequate models the dropping of physical packets in the node. The "heavy-tailed" function of probability density of a packet buffering delay satisfies to this assumption. We have shown, that dynamics of the packet passing in the virtual connection in TCP/IP networks is described by the equations in fractional derivative and corresponds to processes with long-range-dependency. We hope the usage of the well-developed tool of fractional calculus will promote understanding how packet traffic behaves. We assume, that LRD property noticed at measurement of the traffic in computer networks, is general property, characteristic for processes of carry in the mediums 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. Zaborovski V., Podgurski Y.,
  4. Nigmatullin R.R. //Phisica Status Solidi (b) 1984. V. 124. P.389-393.
  5. Nigmatulin R.R.. Fractional Integral.Theoretics and mathematics Physics , v.90, N3, 1992. .354-367.(In Russian)
  6. Oldham K., Spanier J. Fractional Calculus. London, New York: Press, 1973.
  7. 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,
  8. Hosking J.R.M. Fractional Differencing. // Biometrica 68.- 1981., p. 165-176.

Figures


Figure 1. Packet delay/drop processes on a TCP connection.



Figure 2. Packet transfer.



Figure 3.



Figure 4.



Figure 5.



Figure 6.


Back