Model-Driven Joint Optimization of Power and Latency Guarantee in Data center Applications

Abstract

Cloud data centers try to achieve two primary but competing goals for latency-sensitive services: meeting latency service-level objective (SLO) and reducing energy utilization. In this paper, we perform a joint optimization of both goals, such that given a tail latency constraint and request rate, the number of active servers and their corresponding core frequencies which cause the least energy overhead can be derived. Both the server sleep mode and setup delay are taken into account. Based on the assumption that requests arrive following a Poisson process, we provide a numerical method to compute the optimal number of active servers and a closed-form expression for their corresponding core frequency. We propose how the optimization technique can be used for real, bursty, non-Poisson data center traffic.

Appendices

Appendix A: Proof of Proposition 1

The pdf of response time is given by:

$$\begin{aligned} p(t)= {\left\{ \begin{array}{ll} \frac{\alpha (\mu -\lambda )}{\mu -\lambda -\alpha }[e^{-\alpha t}-e^{-(\mu -\lambda )t}] &{} \text {if} \quad \mu -\lambda \ne \alpha \\ p(t)=\alpha ^2 t e^{-\alpha t} &{} \text {if} \quad \mu -\lambda =\alpha \end{array}\right. } \end{aligned}$$

(15)

based on which the tail performance is calculated through $P(T>x)=\int _x^\infty p(t)dt$. Moreover, the distribution function is continuous, since

$$\begin{aligned}&\lim \limits _{\mu -\lambda \rightarrow \alpha }\left [\frac{\mu -\lambda }{\mu -\lambda -\alpha }e^{-\alpha x}-\frac{\alpha }{\mu -\lambda -\alpha }e^{-(\mu -\lambda )x}\right ]\\&\quad = \lim \limits _{t\rightarrow 0}\left [\frac{t+\alpha }{t}e^{-\alpha x}-\frac{\alpha }{t}e^{-(t+\alpha )x}\right ]\\&\quad = e^{-\alpha x}+\alpha e^{-\alpha x}\lim \limits _{t\rightarrow 0}\frac{1-e^{-tx}}{t}\\&\quad = e^{-\alpha x}\left(1 +\alpha \lim \limits _{t\rightarrow 0}xe^{-tx}\right)\\&\quad = e^{-\alpha x}(1 +\alpha x). \end{aligned}$$

Appendix B: Proof of Proposition 2

$$\begin{aligned}&P(T>D_0)=\frac{\mu -\lambda }{\mu -\lambda -\alpha }e^{-\alpha D_0}-\frac{\alpha }{\mu -\lambda -\alpha }e^{-(\mu -\lambda )D_0}\le \epsilon \end{aligned}$$

(16)

$$\begin{aligned}&\Longleftrightarrow e^{-\alpha D_0}-\epsilon \le \frac{\alpha }{\mu -\lambda -\alpha }[e^{-(\mu -\lambda )D_0}-e^{-\alpha D_0}]. \end{aligned}$$

(17)

If $\mu -\lambda >\alpha$, we have $e^{-(\mu -\lambda )D_0}-e^{-\alpha D_0}<0$, and thus, $\frac{\alpha }{\mu -\lambda -\alpha }[e^{-(\mu -\lambda )D_0}-e^{-\alpha D_0}]<0$; if $\mu -\lambda <\alpha$, there is $e^{-(\mu -\lambda )D_0}-e^{-\alpha D_0}>0$, and $\frac{\alpha }{\mu -\lambda -\alpha }[e^{-(\mu -\lambda )D_0}-e^{-\alpha D_0}]<0$. As a result, a sufficient condition to satisfy the QoS (tail delay requirement) constraint is $e^{-\alpha D_0}-\epsilon < 0$, which equals $\alpha >\frac{1}{D_0}\ln \frac{1}{\epsilon }$.

Before simplifying the delay constraint, assume that $\varGamma =\frac{\alpha D_0}{e^{-\alpha D_0}-\epsilon }<0$, which can be transformed into $\varGamma e^{\epsilon \varGamma }=e^{\alpha D_0+\epsilon \varGamma }(\alpha D_0+\epsilon \varGamma )$. Based on this equation, we have:

$$\begin{aligned} \alpha D_0+\epsilon \varGamma \!=\!\left\{ \begin{array}{ll} \mathbf {W}_{0}\left[\varGamma e^{\epsilon \varGamma }\right], \quad &{}\!\! \!\hbox {if }\alpha \!\ge \! \frac{1}{D_0} \left(-\!\mathbf {W}\!_{-1}\left[-\frac{\epsilon }{e}\right]-1 \right); \\ \mathbf {W}_{-1}\left[\varGamma e^{\epsilon \varGamma }\right], \quad &{}\! \!\!\hbox {if }\alpha \!<\! \frac{1}{D_0}\left(-\!\mathbf {W}\!_{-1}\left[-\frac{\epsilon }{e}\right]-1 \right), \end{array} \right. \end{aligned}$$

(18)

where $\alpha D_0+\epsilon \varGamma \ge -1$ in the first case, and $\alpha D_0+\epsilon \varGamma <-1$ otherwise.

• (1) If $\mu -\lambda >\alpha$:

  $$\begin{aligned}&P(T>D_0)\le \epsilon \end{aligned}$$

  (19)
  $$\begin{aligned}&\Longleftrightarrow \frac{\mu -\lambda }{\mu -\lambda -\alpha }e^{-\alpha D_0}-\frac{\alpha }{\mu -\lambda -\alpha }e^{-(\mu -\lambda )D_0}\le \epsilon \end{aligned}$$

  (20)
  $$\begin{aligned}&\Longleftrightarrow e^{-\alpha D_0}-\epsilon +\frac{\epsilon \alpha }{\mu -\lambda }\le \frac{\alpha }{\mu -\lambda }e^{-(\mu -\lambda )D_0} \end{aligned}$$

  (21)
  $$\begin{aligned}&\Longleftrightarrow e^{(\mu -\lambda )D_0}\left[(\mu -\lambda )(e^{-\alpha D_0}-\epsilon )+\epsilon \alpha \right]\le \alpha \end{aligned}$$

  (22)
  $$\begin{aligned}&\Longleftrightarrow e^{(\mu -\lambda )D_0} \left[(\mu -\lambda )D_0+\frac{\epsilon \alpha D_0}{e^{-\alpha D_0}-\epsilon }\right]\ge \frac{\alpha D_0}{e^{-\alpha D_0}-\epsilon } \end{aligned}$$

  (23)
  $$\begin{aligned}&\Longleftrightarrow e^{[(\mu -\lambda )D_0+\epsilon \varGamma ]}[(\mu -\lambda )D_0+\epsilon \varGamma ]\ge \varGamma e^{\epsilon \varGamma }. \end{aligned}$$

  (24)

• When $\alpha \ge \frac{1}{D_0}(-\mathbf {W}_{-1}[-\frac{\epsilon }{e}]-1)$, we have $(\mu -\lambda )D_0+\epsilon \varGamma >\alpha D_0+\epsilon \varGamma \ge -1$, and thus, $P(T>D_0)\le \epsilon$ equals to $(\mu -\lambda )D_0+\epsilon \varGamma \ge \mathbf {W}_{0}[\varGamma e^{\epsilon \varGamma }]=\alpha D_0+\epsilon \varGamma$, which is $\mu \ge \lambda +\alpha$.

• When $\alpha < \frac{1}{D_0}(-\mathbf {W}_{-1}[-\frac{\epsilon }{e}]-1)$, which means $\alpha D_0+\epsilon \varGamma < -1$, the constraint equals $(\mu -\lambda )D_0+\epsilon \varGamma \ge \mathbf {W}_{0}[\varGamma e^{\epsilon \varGamma }]$ or $(\mu -\lambda )D_0+\epsilon \varGamma \le \mathbf {W}_{-1}[\varGamma e^{\epsilon \varGamma }]$. For the first case, we have $\mu \ge \lambda +\frac{1}{D_0}(\mathbf {W}_{0}[\varGamma e^{\epsilon \varGamma }]-\epsilon \varGamma )>\lambda +\frac{1}{D_0}(\mathbf {W}_{-1}[\varGamma e^{\epsilon \varGamma }]-\epsilon \varGamma )=\lambda +\alpha$. For the second case, there is $\mu \le \lambda +\frac{1}{D_0}(\mathbf {W}_{-1}[\varGamma e^{\epsilon \varGamma }]-\epsilon \varGamma )=\lambda +\alpha$, which contradicts with the condition $\mu -\lambda >\alpha.$

Therefore, the delay constraint equals: $\mu >\lambda +\alpha$ when $\alpha \ge \frac{1}{D_0}(-\mathbf {W}_{-1}[-\frac{\epsilon }{e}]-1)$, and $\mu \ge \lambda +\frac{1}{D_0}(\mathbf {W}_{0}[\varGamma e^{\epsilon \varGamma }]-\epsilon \varGamma )$ when $\alpha < \frac{1}{D_0}(-\mathbf {W}_{-1}[-\frac{\epsilon }{e}]-1)$.

• (2) Similarly, if $\mu -\lambda <\alpha$, we can obtain that

  $$\begin{aligned}&P(T>D_0)\le \epsilon \end{aligned}$$

  (25)
  $$\begin{aligned}&\Longleftrightarrow e^{[(\mu -\lambda )D_0+\epsilon \varGamma ]}[(\mu -\lambda )D_0+\epsilon \varGamma ]\le \varGamma e^{\epsilon \varGamma }. \end{aligned}$$

  (26)

• When $\alpha \ge \frac{1}{D_0}(-\mathbf {W}_{-1}[-\frac{\epsilon }{e}]-1)$, the constraint equals $\mathbf {W}_{-1}[\varGamma e^{\epsilon \varGamma }] \le (\mu -\lambda )D_0+\epsilon \varGamma \le \mathbf {W}_{0}[\varGamma e^{\epsilon \varGamma }]$, which is $\lambda +\frac{1}{D_0}(\mathbf {W}_{-1}[\varGamma e^{\epsilon \varGamma }]-\epsilon \varGamma ) \le \mu \le \lambda +\alpha$.

• When $\alpha < \frac{1}{D_0}(-\mathbf {W}_{-1}[-\frac{\epsilon }{e}]-1)$, $(\mu -\lambda )D_0+\epsilon \varGamma<\alpha D_0+\epsilon \varGamma <-1$, and thus, $(\mu -\lambda )D_0+\epsilon \varGamma \ge \mathbf {W}_{-1}[\varGamma e^{\epsilon \varGamma }]=\alpha D_0+\epsilon \varGamma$, which is $\mu -\lambda \ge \alpha$. This contradicts with the condition $\mu -\lambda <\alpha$.

Therefore, the delay constraint equals: $\lambda +\frac{1}{D_0}(\mathbf {W}_{-1}[\varGamma e^{\epsilon \varGamma }]-\epsilon \varGamma ) \le \mu <\lambda +\alpha$ when $\alpha \ge \frac{1}{D_0}(-\mathbf {W}_{-1}[-\frac{\epsilon }{e}]-1)$:

• 3. If $\mu -\lambda =\alpha$,

  $$\begin{aligned}&P(T>D_0)\le \epsilon \end{aligned}$$

  (27)
  $$\begin{aligned}&\Longleftrightarrow \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!(1+\alpha D_0)e^{-\alpha D_0}\le \epsilon \end{aligned}$$

  (28)
  $$\begin{aligned}&\Longleftrightarrow \!\!\!\!\!-(1+\alpha D_0)e^{-(1+\alpha D_0)}\ge -\frac{\epsilon }{e} \end{aligned}$$

  (29)
  $$\begin{aligned}&\Longleftrightarrow \!\!\!\!\!\!\!\!\!\!\!\!\!\!-(1+\alpha D_0)\le \mathbf {W}_{-1}\left[-\frac{\epsilon }{e}\right] \end{aligned}$$

  (30)
  $$\begin{aligned}&\Longleftrightarrow \alpha \ge \frac{1}{D_0}\left(-\mathbf {W}_{-1}\left[-\frac{\epsilon }{e}\right]-1 \right)>0. \end{aligned}$$

  (31)

Combining the above three cases, the delay constraint equals to:

$$\begin{aligned} \left\{ \begin{array}{ll} \!\!\mu \! \ge \! \lambda \! +\!\frac{1}{D_0}(\!\mathbf {W}\!_{-1}[\varGamma e^{\epsilon \varGamma }]\!-\!\epsilon \varGamma \!), \quad&{} \!\!\!\!\!\hbox {if }\alpha \!\ge \! \frac{1}{D_0}\left(\!-\!\mathbf {W}\!_{-1} \left[-\frac{\epsilon }{e} \right]\!-\!1 \right); \\ \!\!\mu \!\ge \!\lambda \! +\!\frac{1}{D_0}(\!\mathbf {W}\!_{0}[\varGamma e^{\epsilon \varGamma }]\!-\!\epsilon \varGamma \!) , \quad&{} \!\!\!\!\!\hbox {if }\frac{\ln \frac{1}{\epsilon }}{D_0}\!<\! \alpha \! < \! \frac{1}{D_0} \left(\!-\!\mathbf {W}\!_{-1}\left[-\frac{\epsilon }{e}\right]\!-\!1 \right). \end{array} \right. \end{aligned}$$

Here, $\frac{1}{D_0}\ln \frac{1}{\epsilon } < \alpha$ is the sufficient condition to satisfy the delay constraint. Since $\ln \epsilon <0$, there is $-\frac{\epsilon }{e}>(\ln \epsilon -1)e^{\ln \epsilon -1}$, and thus, $\mathbf {W}_{-1}[-\frac{\epsilon }{e}]<\ln \epsilon -1$. As a result, it is readily to prove that $\frac{\ln \frac{1}{\epsilon }}{D_0}<\frac{1}{D_0}(-\mathbf {W}_{-1}[-\frac{\epsilon }{e}]-1)$.

Appendix C: Proof of Proposition 5

We prove Proposition 4 under the quadratic power consumption model here. The proof for the linear power consumption model, which is much easier, can be obtained similarly.

Given the number of servers in use K, the proof is divided into two steps. (1) First, given the routing variable $\mathbf {p}$, the service of each server is independent with each other, and thus, we focus on solving the optimal frequency of each server with arrival rate $p_i\lambda$, which is also the proof of Proposition 3. (2) Second, substituting the optimal frequency into Eq. (2), the power consumption of each server is a function of its routing parameter $p_i$, which is denoted as $P(p_i)$. Our objective is to prove that $P(p_i)$ is a convex function, and thus, it satisfies that, for any $[p_1, p_2, ...,p_K]$ with $\sum _{i=1}^{K}p_i=1$, $P(p_1) + P(p_2) + ... +P(p_K) \ge KP(\frac{1}{K})$.

Step 1 The power consumption of single server with quadratic model can be simplified as:

$$\begin{aligned} P(s_i, p_i) = P_s+\frac{p_i\lambda l}{s_i}\left[ b-P_s+\frac{(s_i-s_b)^2}{k^2_2}\right] , \end{aligned}$$

(32)

which is a convex function, and has the extreme point

$$\begin{aligned} s_e=\sqrt{(b-P_s){k_2}^2+{s_b}^2} > s_b. \end{aligned}$$

(33)

The constraint on the frequency is $\max \{s_b, (p_i\lambda +X)l\}\le s_i \le s_c$, where $X = \frac{1}{D_0}(\mathbf {W}_{-1}[\varGamma e^{\epsilon \varGamma }]-\epsilon \varGamma )$ when $\alpha \ge \frac{1}{D_0}(-\mathbf {W}_{-1}[-\frac{\epsilon }{e}]\!-\!1)$, and $X = \frac{1}{D_0}(\mathbf {W}_{0}[\varGamma e^{\epsilon \varGamma }]-\epsilon \varGamma )$ when $\frac{1}{D_0}\ln \frac{1}{\epsilon }<\alpha < \frac{1}{D_0} (-\mathbf {W}_{-1}[-\frac{\epsilon }{e}]-1)$.

• 1. When $s_b\ge (p_i\lambda +X)l$, the constraint on the frequency is $s_b \le s_i \le s_c$, the optimal frequency that minimizes the power consumption is:

  $$\begin{aligned} s^*=\left\{ \begin{array}{ll} s_c, \quad&{} \hbox {if }s_e > s_c; \\ s_e, \quad&{} \hbox {if }s_e \le s_c. \end{array} \right. \end{aligned}$$

• 2. When $s_b < (p_i\lambda +X)l$, the constraint on the frequency is $(p_i\lambda +X)l\le s_i \le s_c$, and the optimal frequency that minimizes the power consumption is:

  $$\begin{aligned} s^*=\left\{ \begin{array}{ll} s_c, \quad&{} \hbox {if }s_e > s_c; \\ (p_i\lambda +X)l, \quad&{} \hbox {if }s_e < (p_i\lambda +X)l;\\ s_e, \quad&{} \hbox {if }(p_i\lambda +X)l \le s_e \le s_c. \end{array} \right. \end{aligned}$$

Combining the upper two cases, given $p_i$, the optimal frequency that minimizes the power consumption $P(s_i, p_i)$ in Eq. (32) under the constraint $\max \{s_b, (p_i\lambda +X)l\}\le s_i \le s_c$ is:

$$\begin{aligned} s^*=\left\{ \begin{array}{ll} s_c, &{} \hbox {if }s_e > s_c; \\ (p_i\lambda +X)l, &{} \hbox {if }s_e < (p_i\lambda +X)l;\\ s_e, &{} \hbox {if }(p_i\lambda +X)l \le s_e \le s_c. \end{array} \right. \end{aligned}$$

Step 2: Substituting the optimal frequency into Eq. (32), the power consumption of each server $P(p_i)$ is given in Eq. (34):

$$\begin{aligned} P(p_i)=\left\{ \begin{array}{l} P_s+\frac{p_i\lambda l}{s_c}\left[ b-P_s+\frac{(s_c-s_b)^2}{k^2_2}\right] , ~~~~ \text {if } s_e > s_c; \\ P_s+\frac{p_i\lambda l}{p_i\lambda l+Xl}\left[ b-P_s+\frac{(p_i\lambda l+Xl-s_b)^2}{k^2_2}\right] , \\ ~~~~~~~~ \hbox {if }s_e < (p_i\lambda +X)l;\\ P_s+\frac{p_i\lambda l}{s_e}\left[ b-P_s+\frac{(s_e-s_b)^2}{k^2_2}\right] , \\ ~~~~~~~~~ \hbox {if }(p_i\lambda +X)l \le s_e \le s_c. \end{array} \right. \end{aligned}$$

(34)

(1) When $s_e =\sqrt{(b-P_s){k_2}^2+{s_b}^2} > s_c$ $P(p_i) = P_s+\frac{p_i\lambda l}{s_c}\left[ b-P_s+\frac{(s_c-s_b)^2}{k^2_2}\right]$ is a linear function of $p_i$, and thus, it is convex.

(2) When $s_e =\sqrt{(b-P_s){k_2}^2+{s_b}^2} \le s_c$, $P(p_i)$ is a continuous function composed of two segments, with the junction point $p_i = (\frac{s_e}{l} - X)/\lambda$. For the left segment with $p_i \le (\frac{s_e}{l} - X)/\lambda$, $P_l(p_i)=P_s+\frac{p_i\lambda l}{s_e}\left[ b-P_s+\frac{(s_e-s_b)^2}{k^2_2}\right]$ is a linear function of $p_i$. For the right segment with $p_i > (\frac{s_e}{l} - X)/\lambda$, it is readily to prove that $P_r(p_i)=P_s+\frac{p_i\lambda l}{p_i\lambda l+Xl}\left[ b-P_s+\frac{(p_i\lambda l+Xl-s_b)^2}{k^2_2}\right]$ is an increasing convex function of $p_i$. Moreover, there is:

$$\begin{aligned} \frac{d}{d p_i}P_l(p_i)\Big |_{p_i=(\frac{s_e}{l} - X)/\lambda } = \frac{d}{d p_i}P_r(p_i)\Big |_{p_i=(\frac{s_e}{l} - X)/\lambda }. \end{aligned}$$

(35)

As a result, $P(p_i)$ is also convex when $s_e \le s_c$.

Combining the upper two cases, $P(p_i)$ is a convex function, and thus, it satisfies that, for any $[p_1, p_2, ...,p_K]$ with $\sum _{i=1}^{K}p_i=1$, there is always $P(p_1) + P(p_2) + ... +P(p_K) \ge KP(\frac{1}{K})$. This means that given the number of servers in use K, the optimal routing policy that minimizes the total power consumption is to evenly distribute the load among the K severs.