A closed-form solution for a queueing model of energy efficient ethernet links
Journal of Computer Science and Cybernetics, V.37, N.4 (2021), 453–464
DOI 10.15625/1813-9663/37/4/16126
A CLOSED-FORM SOLUTION FOR A QUEUEING MODEL OF
ENERGY EFFICIENT ETHERNET LINKS
1,∗
2
TIEN VAN DO , CSABA ROTTER
1Department of Networked Systems and Services,
Budapest University of Technology and Economics
H-1111, Magyar tud´osok k¨oru´tja 2., Budapest, Hungary
2Nokia Bell Labs Hungary
H-1083, B´okay J´anos utca 36 - 42, Budapest, Hungary
Abstract. To save energy consumption of Ethernet switches, IEEE has standardized a new energy-
efficient operation for Ethernet links with a low-power state and transition mechanisms between
the high-power state for transporting traffic and the low-power state. In this paper, we propose a
queueing model with the Markov Modulated Compound Poisson Process that is able to characterize
backbone packet traffic. We derive a closed-form solution for the stationary distribution of the
proposed queueing model. We show that our model can capture an entire system where the transition
times are constant.
Keywords. Energy efficient Ethernet; Queueing model; Markov modulated compound Poission
process.
1. INTRODUCTION
Legacy Ethernet links are active during non-traffic periods, which could lead to the waste
states for the operation of green Ethernet links: Active (A), Sleep (S), Wake (W) and Low
90% power save in state L where there is no traffic. IEEE, however, did not standardize
the triggering mechanism on which conditions state L should be reached. As a result, many
performance evaluations using simulation models and simple analytical models (with Poisson
Dedicated to Professor Phan Dinh Dieu on the occasion of his 85th birth anniversary.
*Corresponding author.
2021 Vietnam Academy of Science & Technology
454
TIEN VAN DO, CSABA ROTTER
traffic and a fixed batch packet size) for Ethernet links based on new standards. These
models provided a qualitative comparison between algorithms and evaluated the effect of
model to estimate the energy consumption of a two-state link and presented a performance
comparison of cooper based versus optical Ethernet. The links’ bidirectional behaviour is
shows a good approximation, minor discrepancies appear when burst traffic alters from
the Poisson assumption. An additional effective triggering mechanism to reach state L is
proposed a generalized predictive control mechanism to adjust the time window parameter
automatically. However, there are no available analytical models with stochastic processes
In this paper, we propose a new model that assumes packet arrivals according to the
Markov Modulated Compound Poisson Process, which is a generalization of the Markov
Modulated Poisson Process – an attractive model for characterizing backbone packet traffic.
It is worth emphasizing that only approximate Markov models are possible due to the fixed
transition times between the modes of energy-efficient Ethernet links. Therefore, we assume
that the transition times between the states of Ethernet links are exponentially distributed
to obtain a tractable model. We validate our model with the exact simulation of energy-
efficient Ethernet links. Furthermore, we derive the exact solution for the proposed analytical
model to compare alternatives concerning the operation modes of green Ethernet links in an
efficient way.
The rest of this paper is organized as follows. A queueing model is proposed in Section
2. Numerical results are shown in Section 3. Finally, Section 4 concludes our paper.
2. A NEW ANALYTICAL MODEL
Green Ethernet links have four states: Active (A), Sleep (S), Wake (W) and Low Power
Idle (L). The transitions between the states for EEE 10GBASE-T links and for EEE
are the transition times between the modes of energy efficient Ethernet links.
We assume that packets arrive at an Ethernet link according to the Markov Modulated
Compound Poisson Process (MMCPP).
The modulating Markov process has two states ON and OFF with parameters α and
β.
In the OFF state, there are no packet arrivals.
In the ON state, packets arrive according to the CPP with parameters (λ, ω). Note that
0 ≤ ω < 1. The probability distribution function of inter-arrival times τ for customers
is defined by Pr(τ = 0) = ω and Pr(0 < τ < t) = (1 − ω)(1 − e−λt). Therefore,
during ON state, the arrival process can be seen as batch-Poisson, with batches having
geometric size distribution. The probability that a batch is of size s is (1 − ω)ωs−1
.
Let J(t) be the number of packets in the system heading for the specific link (including
the number of packet in the transmission buffer and a packet being transmitted) at time
instant t.
A CLOSED-FORM SOLUTION FOR A QUEUEING MODEL
455
No frame
to serve
A
S
j=2
A
S
L
LW
LW
after Ts
After Tw
A
S
W
j=1
j=0
New frame
to serve
S
(a)
LW
A
(c)
S
No frame
to serve
j=2
LW
LW
A
S
A
S
After Tw
New frame
to serve
after Ts
j=1
j=0
W
L
S
New frame
to serve
LW
(b)
(d)
Figure 1: The state transitions
To jointly describe the state of the link and the state of the modulating process at time
is never in state L when there are packets heading for the link (i.e., when J(t) > 0),
is never in state W when no packet is in the system (i.e., when J(t) = 0).
Therefore, we join state L and W in our analytical model into state LW. If J(t) = 0 and
the model is in state LW then the link is in state L. If J(t) ≥ 1 and the model is in state
LW, then the link is in state W. We assume that the transition times between the states
of Ethernet links are exponentially distributed to obtain a tractable model. The transition
times from the state S to state L and the transition times from the state W to state A are
exponentially distributed with rate νs and νW , respectively. Note that νs = Ts and νw = Tw.
Now it is easy to identify the value set of I(t) if we lexicographically sort the states
continuous time Markov chain (CTMC) {I(t), J(t)}. The possible transitions of the CTMC
transitions of the CTMC for EEE 100BASE-TX or 1000BASE-T links when 1 ≤ I(t) ≤ 3
Table 1: Values of I(t)
I(t)
The state of the link
The state of the modulating Markov process
1
A
2
S
ON
3
LW
4
A
5
6
LW
S
OFF
Let the steady state probabilities of CTMC {I(t), J(t)} be denoted by
456
TIEN VAN DO, CSABA ROTTER
πi,j = lim Pr(I(t) = i, J(t) = j).
t→∞
Define the row vector vj = [π1,j, . . . , π6,j]. We have π1,0 = π4,0 = 0 due to the operation rule
of the link.
blocks contain the transitions of the Markov chain as follows.
(j)
0,s
(j)
0,s
(a) Block Q includes element Q (i, k) that is the s−step upward transition from state
(i, j) to state (k, j + s) (1 ≤ i, k ≤ 6; j = 0, 1, . . .). These transitions are caused by the
arrivals of customers.
(b) Block Q(1j) consists of element Q(1j)(i, k) that denotes the purely phase transition from
state (i, j) to state (k, j) (1 ≤ i, k ≤ 6, k
̸
(c) Block Q(2j) contains element Q(2j)(i, k) that is the one−step downward transition from
state (i, j) to state (k, j − 1) (1 ≤ i, k ≤ 6; j = 1, . . .). These transitions are caused by
the departures of customers from the system.
Based on the operation of the link, we can write the transition matrices and the infinitesimal
10GBASE-T, EEE 100BASE-TX and EEE 1000BASE-T links.
The balance equations and the normalization equation can be written as follows
v0Q(10) + v1Q(21) = 0,
(1)
j−1
X
v0Q(00,j)
+
vj−sQ(j−s) + vjQ1 + vj+1Q2 = 0, j ≥ 1,
0,s
s=1
∞
6
X X
Theorem 1. For j > 1, the following equation holds between the stationary probabilities
πi,j = 1.
(2)
(3)
j=0 i=1
e
e
e
vj−1Q0 + vjQ1 + vj+1Q2 = 0,
e
e
e
where Q0 = (Q0,1 − Q1Ω), Q1 = (Q1 − Q2Ω) and Q2 = Q2.
Proof. Let us define ωs = λ(1 − ω)ωs−1, Ω = Diag[ω, ω, ω, 0, 0, 0], Λ = Diag[λ, λ, λ, 0, 0, 0]
Then, we obtain
(j)
0,s
Q
Q
= Λ(I − Ω)Ωs−1 = Q0(j,s)−1Ω,
(4)
(5)
(0)
0,j
(0)
0,j−1
= Q
Ω.
Multiplying balance equation concerning level j − 1, j ≥ 2, with Ω, we get
j−2
X
v0Q(00,j)−1Ω +
vj−1−sQ(j−1−s)Ω = −vj−1Q1Ω − vjQ2Ω = 0, j ≥ 2.
0,s
s=1
■
0,1
A CLOSED-FORM SOLUTION FOR A QUEUEING MODEL
457
Table 2: Transition matrices for modeling an EEE 10GBASE-T link
0
0
0
0
0
0
0
ωs
0
0
0
0
0
ωs
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
(0)
0,s
Q
=
, s ≥ 1 ;
0
0
ωs
0
ωs
0
0
0
0
0
ωs
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
(j)
0,s
Q
= Q0,s
=
, j ≥ 1, s ≥ 1;
0
0
0
0
0
0
0
0
0
0
νs
0
0
α
0
0
0
α
0
−λ − α − νs
0
0
0
0
0
0
0
β
0
−λ − α
Q(10)
=
,
0
0
β
0
−β − νs νs
0
−β
−λ − α − µ
0
0
νs
α
0
0
0
α
0
0
0
α
0
νs
0
νw
β
−λ − α − νs
0
0
β
0
−λ − α − νw
Q(1j) = Q1 =
,
0
0
β
−β − µ
0
0
0
0
νw
−β − νs
0
−β − νw
j ≥ 1,
0
0
0
0
0
0
µ
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
µ
0
0
0
0
0
0
0
0
Q(21)
=
,
µ
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
µ
0
0
0
0
0
0
0
0
0
0
0
0
Q(2j) = Q2 =
, j > 1.
458
TIEN VAN DO, CSABA ROTTER
Table 3: Transition matrices for modeling an EEE 100BASE-TX or 1000BASE-T link
0
ωs
0
0
0
0
0
0
0
0
0
0
0
ωs
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
(0)
0,s
Q
=
=
, s ≥ 1,
0
0
ωs
0
0
0
0
0
0
0
0
0
0
0
0
ωs
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
(j)
0,s
Q
= Q0,s
, j ≥ 1, s ≥ 1,
0
0
0
0
0
0
0
0
0
0
νs
0
0
α
0
0
0
α
0
−λ − α − νs
0
0
0
0
0
0
0
β
0
−λ − α
Q(10)
=
,
0
0
β
0
−β − νs νs
0
−β
−λ − α − µ
0
0
0
α
0
0
α
0
0
0
α
0
0
νw
β
0
0
−α
0
0
β
0
−λ − α − νw
0
−β − µ
0
Q(1j) = Q1 =
, j ≥ 1,
0
0
β
0
−β − νs
νs
νw
0
−β − νw
Table 4: Infinitesimal generator matrix
(0)
0,1
(0)
0,2
(1)
(0)
0,j−1
(0)
0,j
(0)
0,j+1
(1)
0,j
(2)
(0)
0,j+2
(1)
0,j+1
(2)
0,j
(3)
(0)
0,j+3
(1)
0,j+2
(2)
0,j+1
Q(10)
Q(21)
Q
Q
Q
. . .
. . .
. . .
. . .
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
. . .
. . .
. . .
. . .
(1)
0,j−2
(1)
Q(11)
Q(22)
0
0,1
0,j−1
(2)
0,j−3
(2)
0,j−2
0
Q(12)
Q(23)
0,j−1
(3)
0,j−4
(3)
0,j−3
(3)
0,j−2
(3)
0,j
0
. . .
0,j−1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Q =
,
.
(j)
0,1
Q(1j+1)
Q(2j+2)
(j)
0,2
(j+1)
0,1
Q(1j+2)
(j)
0,3
(j+1)
0,2
Q(0j+2)
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
.
.
.
Q(2j)
Q(1j)
Q(2j+1)
. . .
Q
Q
Q
. . .
. . .
Q
Q
. . .
. . .
.
.
.
. . .
.
.
.
. . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
A CLOSED-FORM SOLUTION FOR A QUEUEING MODEL
459
6
X
vj
=
bkψkxj−1 (j ≥ 1);
(6)
k
k=1
where
e
e
(xk, ψk), k = 1, . . . , 6 are the left eigenvalue-eigenvector pairs of Q(x) = Q0 + Q1x +
2
e
that the left eigenvalue-eigenvector pairs satisfy ψkQ(xk) = 0 and det[Q(xk)] = 0, k =
1, . . . , 6.
e
e
e
ties (e.g., the non-negative elements) of the rate matrix do not hold because Q0 + Q1 + Q2
is not a stochastic matrix.
1
0.8
0.6
0.4
0.2
0
1
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
0.8
1
0
0.2
0.4
0.6
0.8
1
ω
ω
(a)
(b)
1
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
0.8
1
ω
(c)
Figure 2: Probability vs ω for ρ = 0.1
2.1. The left-eigenvalues for an EEE 10GBASE-T link model
Utilizing Theorem 1, we obtain
2
3
e
e
e
det[Q(x)] = det[Q0 + Q1x + Q2x ] = (x − 1)x f1(x)f2(x)f3(x),
460
TIEN VAN DO, CSABA ROTTER
1
0.8
0.6
0.4
0.2
0
1
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
0.8
1
0
0.2
0.4
0.6
0.8
1
ω
ω
(a)
(b)
1
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
0.8
1
ω
(c)
Figure 3: Probability vs ω for ρ = 0.2
where
f1(x) = µ2x2 − (αµ + βµ + λµ + µ2 + µ2ω)x + βλ + λµ + αµω + βµω + µ2ω,
f2(x) = (βλ + ανs + βνs + λνs + νs2)x − βλ − λνs − ανsω − βνsω − νs2ω,
f3(x) = (βλ + ανw + βνw + λνw + νw2 )x − βλ − λνw − ανwω − βνwω − νw2 ω.
As a consequence, det[Q(x)] has 8 roots. The roots inside the unit circle are
x1 = x2 = x3 = 0,
βλ + λνs + ανsω + βνsω + νs2ω
x4
x5
x6
=
=
=
,
βλ + ανs + βνs + λνs + νs2
βλ + λνw + ανwω + βνwω + νw2 ω
βλ + ανw + βνw + λνw + νw2
αµ + βµ + λµ + µ2 + µ2ω
,
2µ2
p
(αµ + βµ + λµ + µ2 + µ2ω)2 − 4µ2(βλ + λµ + αµω + βµω + µ2ω)
2µ2
−
.
A CLOSED-FORM SOLUTION FOR A QUEUEING MODEL
461
2.2. The left-eigenvalues for an EEE 100BASE-TX or 1000BASE-T link model
In this case, det[Q(x)] can be expressed as follows
det[Q(x)] = ανs(x − 1)x3(x − ω)f4(x)f5(x),
where
f4(x) = x(βλ + ανw + βνw + λνw + νw2 ) − βλ − λνw − ανwω − βνwω − νw2 ω,
f5(x) = βλ + λµ + αµω + βµω + µ2ω − x(αµ + βµ + λµ + µ2 + µ2ω) + µ2x2.
Thus, the roots inside the unit circle are
x1 = x2 = x3 = 0,
x4 = ω,
βλ + λνw + ανwω + βνwω + νw2 ω
βλ + ανw + βνw + λνw + νw2
αµ + βµ + λµ + µ2 + µ2ω
x5
x6
=
=
,
2µ2
p
(αµ + βµ + λµ + µ2 + µ2ω)2 − 4µ2(βλ + λµ + αµω + βµω + µ2ω)
2µ2
−
.
The corresponding eigenvectors of zero-eigenvalues are [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 1]. Using ψkQ(xk) = 0, we can easily determine the exact formula of ψk for
non zero eigenvalues. Then, the expressions for v0 and bk, k = 1, . . . , 6, can be derived as
well (we do not write here because the long formulae).
2.3. Performance measures
The probability of state A, S, L and W can be determined as
6
3
X
X
bk(ψk,1 + ψk,4
1 − xk
)
)
PA = π1,0 + π4,0
+
+
+
+
bk(ψk,1 + ψk,4),
bk(ψk,2 + ψk,5),
k=4
k=1
6
3
X
X
bk(ψk,2 + ψk,5
1 − xk
PS = π2,0 + π5,0
PL = π3,0 + π6,0
k=4
k=1
,
PW = 1 − PA − PS − PL.
3. NUMERICAL RESULTS
To show that the queueing model can evaluate the performance of Energy Efficient Eth-
ernet links, we compare results obtained by a simulation where transition times Tw and Ts
between states are fixed. Note that in the proposed queueing model, the transition times
follow the exponential distribution. Simulations are performed with a confidence level of
462
TIEN VAN DO, CSABA ROTTER
ms), β = 0.000110 (the average OFF period is 9.09 ms), the average packet size is of 1500
rON
λ
agreement between the simulation and analytical results is excellent.
1
0.8
0.6
0.4
0.2
0
0.001
0.0001
0
0.2
0.4
0.6
0.8
1
0
0.2
0.4
0.6
0.8
1
ω
ω
(a)
(b)
0.001
0.0001
0
0.2
0.4
0.6
0.8
1
ω
(c)
Figure 4: Probability vs ω for ρ = 0.5
achieved. At the same load (the same amount of packets), the burstiness (packets in batches
of more packets) would have a better impact on energy saving.
For an EEE 1000BASE-T link model, we plot the probability in state L versus Tw and
4. CONCLUSIONS
We have proposed a queueing model for Energy Efficient Ethernet links. In the model
packets arrive according to the Markov Modulated Compound Poisson Process and the
transition times between the states of Ethernet links are exponentially distributed. We have
derived the exact solution for the steady-state probabilities of the analytical model. The
comparison between our model and the simulation of energy-efficient Ethernet links shows
that the proposed model can capture the behaviour of Energy Efficient Ethernet links.
A CLOSED-FORM SOLUTION FOR A QUEUEING MODEL
463
1
ρ=0.1
ρ=0.2
ρ=0.3
ρ=0.4
ρ=0.5
ρ=0.6
ρ=0.7
ρ=0.8
ρ=0.9
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
0.8
1
ω
Figure 5: Probability in state L
0.5
0.48
0.46
0.44
0.42
0.4
PrL
0.38
0.36
20
18
16
14
12
0
10
20
40
8
Tw
60
80
6
100
4
120
140
2
160
Ts
180
0
200
Figure 6: Probability in state L vs Ts and Tw, 1000BASE-T links
REFERENCES
[1] M. Ajmone Marsan, A. Anta, V. Mancuso, B. Rengarajan, P. Vasallo, and G. Rizzo, “A simple
analytical model for energy efficient Ethernet,” IEEE Communications Letters, vol. 15, no. 7,
pp. 773 –775, July 2011.
[2] A. Cenedese, F. Tramarin, and S. Vitturi, “An energy efficient Ethernet strategy based on
traffic prediction and shaping,” IEEE Transactions on Communications, pp. 1–1, 2016. [Online].
Available: https://doi.org/10.1109/tcomm.2016.2623702
P
K
[3] R. Chakka and T. V. Do, “The MM k=1 CPPk/GE/c/L G-Queue with Heterogeneous Servers:
Steady state solution and an application to performance evaluation,” Performance Evaluation,
vol. 64, no. 3, pp. 191–209, March 2007.
[4] A. Chatzipapas and V. Mancuso, “An M/G/1 model for gigabit energy efficient
Ethernet links with coalescing and real-trace-based evaluation,” IEEE/ACM Transactions
464
TIEN VAN DO, CSABA ROTTER
[5] K. Christensen, P. Reviriego, B. Nordman, M. Bennett, M. Mostowfi, and J. Maestro, “IEEE
802.3az: the road to energy efficient Ethernet,” Communications Magazine, IEEE, vol. 48, no. 11,
pp. 50 –56, November 2010.
[6] K. Christensen, P. Reviriego, B. Nordman, M. Bennett, M. Mostowfi, and J. A. Maestro, “Ieee
802.3az: the road to energy efficient Ethernet,” IEEE Communications Magazine, vol. 48, no. 11,
pp. 50–56, 2010.
[7] M. Gupta, S. Grover, and S. Singh, “A feasibility study for power management in LAN switches,”
in Proceedings of the 12th IEEE International Conference on Network Protocols, 2004. ICNP
2004., 2004, pp. 361–371.
[8] S. Herreria-Alonso, M. Rodriguez-Perez, M. Fernandez-Veiga, and C. Lopez-Garcia, “A power
saving model for burst transmission in energy-efficient Ethernet,” Communications Letters,
IEEE, vol. 15, no. 5, pp. 584 –586, May 2011.
[9] ——, “A GI/G/1 Model for 10 Gb/s Energy Efficient Ethernet Links,” IEEE Transactions
on Communications, vol. 60, no. 11, pp. 3386–3395, Nov. 2012. [Online]. Available:
[10] W. Jiang, J. Wang, L. Peng, and J. Wang, “Generalized predictive control of the time window
for energy efficient Ethernet with prediction,” IEEE Communications Letters, vol. 25, no. 5,
pp. 1491–1495, May 2021. [Online]. Available: https://doi.org/10.1109/lcomm.2021.3051626
[11] D. Larrabeiti, P. Reviriego, J. Hern´andez, J. Maestro, and M. Uruen˜a, “Towards an
energy efficient 10 Gb/s optical Ethernet: Performance analysis and viability,” Optical
Switching and Networking, vol. 8, no. 3, pp. 131–138, Jul. 2011. [Online]. Available:
[12] G. Latouche and V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Model-
ing. ASA-SIAM Series on Statistics and Applied Probability, 1999.
[13] L. Muscariello, M. Mellia, M. Meo, M. A. Marsan, and R. L. Cigno, “Markov models of internet
traffic and a new hierarchical MMPP model,” Computer Communications, vol. 28, no. 16, pp.
1835–1851, 2005.
[14] B. Nordman, “Eee savings estimate,” IEEE 802.03az Task Force Information”,year =2008.
[15] P. Reviriego, K. Christensen, J. Rabanillo, and J. A. Maestro, “An initial evaluation of energy
efficient Ethernet,” IEEE Communications Letters, vol. 15, no. 5, pp. 578–580, 2011.
[16] P. Reviriego, J. Hernandez, D. Larrabeiti, and J. Maestro, “Performance evaluation of energy
efficient Ethernet,” Communications Letters, IEEE, vol. 13, no. 9, pp. 697 –699, Sept. 2009.
[17] P. Reviriego, J. Maestro, J. Hern´andndez, and D. Larrabeiti, “Burst transmission for energy-
efficient Ethernet,” Internet Computing, IEEE, vol. 14, no. 4, pp. 50 –57, july-aug. 2010.
[18] M. Rodriguez-Perez, S. Herreria-Alonso, M. Fernandez-Veiga, and C. Lopez-Garcia, “Improved
opportunistic sleeping algorithms for lan switches,” in GLOBECOM 2009 - 2009 IEEE Global
Telecommunications Conference, 2009, pp. 1–6.
Received on June 7, 2021
Accepted on August 21, 2021
12 trang
16060
Free
Bạn đang xem tài liệu "A closed-form solution for a queueing model of energy efficient ethernet links", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- a_closed_form_solution_for_a_queueing_model_of_energy_effici.pdf
