We now formalize power-demand routing as multiobjective network optimization problem, that can be formulated as the following multiobjective optimization problem solved at the beginning of each time interval.

SUBJECT TO THE FOLLOWING CONSTRAINTS: \[ \begin{aligned} \mathrm{C1:\;\;\;}& \sum_{j=1}^n x_{s_i j}=r_{s_i} &\text{for } i=1,\ldots,m\\ \mathrm{C2:\;\;\;}& \sum_{i=1}^m x_{s_i j}- x_{j t_i}=0 &\text{for } j=1,\ldots,n\\ \mathrm{C3:\;\;\;}& x_{j t_i}\leq u_{j t_i} & \text{for } j=1,\ldots,n\\ \mathrm{C4:\;\;\;}& L_{\mathrm{ave}}=\frac{1}{\sum_{i=1}^m r_{s_i}}\sum_{i=1}^m \sum_{j=1}^n x_{s_i j}l_{s_i j}(x_{j,t_j})&\\ \mathrm{C5:\;\;\;}&L_{\mathrm{ave}}\leq D_{\max}&\\ \mathrm{C6:\;\;\;}&x_{s_i j}\geq 0,\;\;x_{j t_j}\geq 0& \text{for } i=1,\ldots,m, \; j=1,\ldots,n \end{aligned} \]

We now describe the constraints that determine the set of feasible solutions (the set of feasible flows of requests) \( \mathbb{X}\subset{R}^{m\times n +n}\) in the above network model, where \(\mathbf{x}\in \mathbb{X}\) is a feasible flow of requests in the network. Namely:

Constraints C1: The constraints are mass balance ones, which state that the number of requests \(r_{s_i}\) arriving at each ingress node \(s_i\) is equal to the sum of the requests outgoing the ingress for \(i=1,\ldots,m\).

Constraints C2: The constraints are also mass balance ones. They state that the sum of the requests entering the cluster server node \(j\) is equal to the number of requests server cluster \(j\) must service, \(j=1,\ldots,n\).

Constraints C3: The constraints are flow bound constraints. They bound by the capacity \(u_{j t_i} \) the number of requests routed to the cluster \(j\), \(j=1,\ldots,n\).

Constraints C4 and C5: These constraints will be described later (see, System performance costs \(C_P\)).

Constraints C6: The constraints model non-negativity of the decision variables that represent numbers of requests on arcs in the network.

We now specify the objective functions (the cost functions), represented by the three component vector \((C_E(\mathbf{x}),C_N(\mathbf{x}), C_P(\mathbf{x}))^T\), \(\mathbf{x}\in \mathbb{X}\), in the multiobjective network optimization problem. There are cost components for energy consumption, network and the system performance. In the following we describe each cost component:

Energy costs \(C_E\): In power-demand routing the main focus is on optimizing energy costs in the system. A significant component of these costs are the server clusters' energy costs. Each energy cost of the server cluster \(j\) is model by a non-decreasing function \(E_{j t_j}\) depending on the amount of electrical energy used by the cluster. Thus the function \(E_{j t_j}\) of \(x_{j t_j}\) requests that are serviced at cluster \(j\) has the form \(E_{j t_j}(\epsilon_{j t_j}(x_{j t_j}))\), where \(\epsilon_{j t_j}(x_{j t_j})\) is the energy (in \(kWh\)) used when \(x_{j t_j}\) requests are serviced at cluster \(j\). It is worth pointing out that \(E_{j t_j}(\epsilon_{j t_j}(x_{j t_j}))\) is one of components, denoted by \(C^E_{j t_j}(x_{j t_j})\), of a vector of cost functions \(\mathbf{C}_{j t_j}(x_{j t_j})\) assigned to server cluster arc \((j,t_j)\) in the network flow model, i.e. \[ C^E_{j t_j}(x_{j t_j}) \stackrel{\mathrm{def}}{=} E_{ ,t_j}(\epsilon_{j t_j}(x_{j t_j})). \] Therefore, the total cost of energy consumed in the system is the sum of costs of energy consumed in the clusters, \[ C_E(\mathbf{x})=\sum_{j=1}^n C^E_{j t_j}(x_{j t_j})=\sum_{j=1}^n E_{j t_j}(\epsilon_{j t_j}(x_{j t_j})), \; \mathbf{x}\in \mathbb{X}. \] In order to express the cost of energy in monetary units, one can use the following function: \[ C^E_{j t_j}(x_{j t_j})=E_{j t_j}(\epsilon_{j t_j}(x_{j t_j}))=\epsilon_{j t_j}(x_{j t_j}) \cdot \mathrm{price}^{E}_{j t_j}, \] where \(\mathrm{price}^{E}_{j t_j}\) is the price-per-\(kWh\) of electricity at a geographic location of cluster \(j\). Of course, electricity prices can vary with time and geographic location - to cope with this problem, we refer the reader to   : 1 .

Pollution: One may minimize an impact of the energy consumed in the system on environment, for instance in terms of carbon footprints, instead of minimizing energy costs. In order to do this it suffices to express \(C^E_{j t_j}(x_{j t_j})\) in pollution units (in \(kg \;\;CO_2\)) or replace \(\mathrm{price}^{E}_{j t_j}\), in the above formulae, with a term specifying a time-varying pollution per \(kWh\).

Network costs \(C_N\): In power-demand routing the focus is also on optimizing network usage costs in the system. Obviously, network usage prices can vary with geographic location or with time in the same location. Each network usage cost of the server cluster \(j\) can be modeled by the following increasing function: \[ C^N_{j t_j}(x_{j t_j})\stackrel{\mathrm{def}}{=} x_{j t_j} \cdot \mathrm{price}^{N}_{j t_j}, \] where \(\mathrm{price}^{N}_{j t_j}\) is the price-per-\(request\) at a geographic location of cluster \(j\). Note that \(C^N_{j t_j}(x_{j t_j})\) is one of components of a vector of cost functions \(\mathbf{C}_{j t_j}(x_{j t_j})\) assigned to server cluster arc \((j,t_j)\) in the network flow model. Thus, the total network cost~\(C_N\) in the system is the sum of network usage costs of the clusters, \[ C_N(\mathbf{x})=\sum_{j=1}^n C^N_{j t_j}(x_{j t_j}), \; \mathbf{x}\in \mathbb{X}. \] For more realistic network usage cost functions see   : 1 .

System performance costs \(C_P\): The last criterion that one focuses on, during the course of the optimization process, is the criterion that expresses the system performance. Clearly, poor system performance causes a loss of revenue. A reasonable metric of system performance is end-to-end request latency. The end-to-end request latency is included in the network flow model by defining the average end-to-end request latency \(L_{\mathrm{ave}}\) over the system, i.e. \[ L_{\mathrm{ave}}(\mathbf{x})=\frac{1}{\sum_{i=1}^m r_{s_i}}\sum_{i=1}^m \sum_{j=1}^n x_{s_i j}l_{s_i j}(x_{j,t_j}). \] Two bounds are specified on the request latency in the system. The first one is the upper bound \(D_{\max}\) whose violating causes degrading the system performance and in the result, for example a loss of revenue. Hence, we arrive to the following constraint (see Constraints C4 and C5): \[ L_{\mathrm{ave}}(\mathbf{x})\leq D_{\max}. \] The second one is the lower bound \(D_{\min}\) on the request latency whose violating causes no additional utility to the system operators. Thus, we have the third component of the three component vector, namely: \[ C_N(\mathbf{x})=\max\{ 0, L_{\mathrm{ave}(\mathbf{x})}-D_{\min}\}, \; \mathbf{x}\in \mathbb{X}. \]

One can try to express \(C_N(\mathbf{x})\) in monetary units to tread the cost functions in the model equivalently.