Random walks with additive increase and multiplicative decrease are widely used for performance control and modeling in telecommunication, smart spaces and some biological systems as well. There exists in the literature two mainstream approaches which apply discrete stepwise and piecewise linear random processes. Meanwhile most real implementations of the algorithms used by the networking applications support discrete arithmetics for its key variables. Therefore piecewise linear models provide approximate results and the applicability of these results needs further studies. In the paper we consider the connection between discrete stepwise and piecewise linear models and provide the boundary estimation for the important characteristic of the stepwise random process in terms of the piecewise linear random process.
Random walks with additive increase and multiplicative decrease are widely used
in the modern networking environments for distributed control of the
communication parties activity [
More sophisticated variations of the algorithm based on AIMD-kind random walks are proposed to provide distributed performance control for highly congested publish/subscribe IoT environments and smart spaces [26], [15]. As for the data communication networks the algorithms are used by data sources so in IoT environments or smart spaces they are implemented by the clients subscribed for Semantic Information Brokers (SIB) service noti cations. The clients control the periods between noti cation requests. They increase it linearly if no losses of noti cations happened and decrease it by multiplication factor if the losses occurred. The factor depends on the number of losses and several other arguments.
Wide scope of the applications and strict demands to their performance de ne the importance of modeling and analysis studies of the signi cant properties of the random walks mentioned above.
In many cases their key performance metrics could be described by
stepwise random process with semi-markovian or renewal properties [
There exists in the literature two di erent approaches to the description of
TCP data loss process. The rst one considers the losses as a random ow. So
if k and k+1 are the moments of two consequent data losses, then the type of
distribution of [ k+1 k] intervals is an essential assumption of the model, see
e.g. [
This work considers the random walk implemented by AIMD algorithm as stepwise process and piecewise linear process and establishes boundary estimate which bounds steady state second moments of the congestion window size provided by these two models. To de ne data loss process we consider the sequence of data sent between two consequent loss events. Following most of publication we consider loss event as it is de ned by NewReno TCP version and evaluate the goodput.
The work is organized as follows. Section 2 describes two baseline models of the AIMD random walk, Section 3 presents the theorem about the boundary estimation and its proof. Section 4 contains conclusions. 2
Two baseline models of the additive increase and multiplicative decrease random walk First we describe the stepwise model of the random walk. Let us de ne the random process which describes a behavior of AIMD congestion window size in the terms of TCP segments.
Let tn be the moments of AIMD-rounds end-points. Hence [tn 1; tn] are round trip intervals, and RTT length is n = tn tn 1: Let us denote w(t) a congestion windows size under AIMD control at the time moment t: Then fw(t)gt>0 is a stepwise process such that w(tn + 0) = 8 > b w(tn)c ; if during the interval (TCP round) [tn 1; tn] < one or more TCP segment losses has happened, >: w(tn) + 1; if all data in the round were successfully delivered. Between the moments tn the process fw(t)gt>0 stays constant and < 1:
Let us suppose that n are independent identically distributed (iid.) random variables with distribution R(x); which is absolutely continuous on the set R+ and E[ n] < 1: Let us denote sequence fSngn>0 which describes amounts of data sent between two consecutive loss events. We assume that Sn are iid. random variables with nite expectation E[Sn] < 1: The count of data sent starts from the round next to the loss event. Let us denote wn = w(tn) and let k = tn if a loss event happened during n period, i.e.
w( k + 0) = b w( k)c : Also let us denote Wk = w( k) so Wk = wn if k = tn:
Then the sequence fWkgk>0 forms the Markov chain embedded in the random process fw(t)gt>0: Fig. 1 presents graphical example of fw(t)gt>0 evolution.
Now we consider a piecewise linear random process which presents the evolution of the random walk. Let fX(t)gt>0 take values from R+ growing linearly in the intervals [ n; n+1) n = 0; 1; : : : with the speed b = E[ n] 1; i.e. X(t) = X(t0) + bt; 8 [t0; t] [ n; n+1): At random moments f ngn 0 the process fX(t)gt>0 makes jumps X( n + 0) = X( n); where < 1 and X( n 0) = X(t0) + b n 6= X( n):
We assume that amounts of data sent between the moments f ngn 0 de ne a sequence f ngn>0 which forms renewal process with continuous density renewal function, cumulative distribution function F (x) and E[ n] < 1: We introduce a sequence fXngn>0 such that Xn = X( n); thus Xn = X(t) if X(t + 0) = X(t): So a multiplicative decrease happens after each Xn value. Let us notice that the sequence fXngn 0 possesses Markovian property and it is embedded in the process fX(t)gt>0: Fig. 2 presents graphical example of fX(t)gt>0 evolution.
There are many publication which derive E[Wn] or E[Xn] estimates under various conditions and assumptions. The following section studies relation between these two values. 3
Under assumptions formulated above the following relation between stationary (equipped with asterisk) expectations E[X 2 ] and E[W 2 ] holds Theorem 1. If E[Sn] = E[ n] and b = 1 then 2
E[W 2 ]
E[X 2 ]:
Proof. Simple geometrical considerations provide the following equation for the
sequence Wn2 in the following form [
Wn2+1
2Wn2 =
2
p
;
where p is data segment loss probability for Bernoulli loss process. Using
assumptions made on the piecewise process and following heuristic approach presented
in [
Wn2+1 = b 2Wn2c + 2Sn; where bxc is the largest integer not exceeding x. Discrete nature of the units and calculation methods used by networking software determine the using of the oor operation in the equation (1). Nevertheless the operation poses signi cant di culties for the further analysis. Therefore let us transform the equation (1) into the following form
Wn2+1 =
2Wn2
n + 2Sn;
where n is the random value and 0 n 1: According to [
W~ n2+1 = 2W~ n2 + (2Sn n): Applying recurrent equation (2) one can obtain stationary solution Wn 2
1 = X Notice that since < 1 and 8 n E[Sn] and E[ n] are converges absolutely and therefore nite the latter series 2 (2E[Sn]
E[ n]) :
n 1 then 0
Now let us consider the process X(t): According to [
(Xn+1 +
Xn) (Xn+1
1
Xn) 2b = n: Xn2+1 =
2Xn2 + 2b n:
Stochastic equation (4) satis es conditions of convergence theorem formulated
in [
E[Wn2 ] = X1
i=0 E[Wn2 ] = X1 i=0 2iE[2Sn i 1 (4) (5)
Xn2 = X1 i=0
2i (2b n i 1) E[Xn2 ] = 2b X1 i=0 2iE[ n i 1] and hence 2b
2 E[ n]: 2
E[W 2 ] which proves the theorem. tu
Let notice that e.g., NewReno version uses value = 1=2 and congestion window size normally uctuates from several tens to several hundreds of segments for wide range of applications. In the case according to the theorem the error of the piecewise model will be smaller than 4=3 which is insigni cant for the practical purposes.
Now let us consider the parameter b of the X(t) process and its role in the
modeling and estimates evaluation. The discrete stepwise models [
Bn =
Sn Tn
;
mn
Tn = X k:
b =
see [
In this paper the connection between stepwise and piecewise models of additive increase multiplicative decrease random walk is obtained. The random walk describes a behavior of the networking software critical algorithms, smart spaces applications and some biological systems. The Markov chain embedded in the stepwise random process and Markov sequence embedded in the piecewise linear random processes are considered, and the theorem relating their parameters and characteristics is proved. The results obtained demonstrate that piecewise linear model produces good estimation of the performance metrics for the discrete algorithms based on the additive increase multiplicative decrease random walk.