## 2 Materials and Methods
### Problem Modelisation
#### 2.1.4 Penalty Terms and Feasibility Constraints  
We model two penalty terms and two feasibility constraints for our optimization problem. The first penalty term is the **Quality of Service penalty term** and is modeled as follows. The acceptance ratio during time-step \(t\) is computed as:  
\[\chi^{t}_{Q}=\frac{\sum_{r\in R_{t}}v_{r}}{|R_{t}|} \tag{1}\]  
where the binary variable \(v_{r}\) indicates if the SFC assigned to \(r\) respects or not its maximum tolerable RTT, denoted by \(T_{r}\):  
\[v_{r}= \begin{cases}1,&\text{if }RTT_{r}<=T_{r}\\ 0,&\text{otherwise}\end{cases}  \tag{2}\]  
Notice that \(RTT_{r}\) is the round-trip-time of \(r\) and is computed as:  
\[RTT_{r}=\sum_{i,j\in N}\sum_{k\in K}z^{r}_{i,j,k}\cdot d_{i,j}+\sum_{i\in N_{H }}\sum_{k\in K}x^{k}_{r,j}\cdot\{(1-a^{t,k}_{i})\cdot I_{k}+\rho^{t}_{i,k}\} \tag{3}\]  
where:  
* The binary variable \(z^{r}_{i,j,k}\) equals 1 if the link between nodes \(i\) and \(j\) is used to reach \(f^{k}_{r}\), and 0 otherwise,
* The parameter \(d_{i,j}\in\mathbb{R}^{+}\) represents the data-propagation delay between the nodes \(i\) and \(j\). (We assume a unique path between every node \(i\) and \(j\)),
* The binary variable \(x^{k}_{r,i}\) equals 1 if \(f^{k}_{r}\) is assigned to \(f^{k}_{i}\), and 0 otherwise,
* The binary variable \(a^{t,k}_{i}\) equals 1 if \(f^{k}_{i}\) is instantiated at the beginning of \(t\), and 0 otherwise,
* \(I_{k}\) is a parameter indicating the instantiation time of any \(k\)-type VNF. * \(\rho^{r}_{i,k}\) is the processing time of \(r\) in \(f^{k}_{i}\). Notice that, by modeling \(RTT_{r}\) with (3), we include data-propagation delays, processing time delays, and VNF instantiation times when needed: We will include the delay to the content provider in such RTT only in the case of a cache MISS. In other words, if \(i\) is a CP node, then \(z^{r}_{i,j,cache}\) will be 1 only if \(f^{cache}_{j}\) was not ingesting content from \(i\) at the time of receiving the assignation of \(f^{cache}_{r}\). On the other hand, whenever \(f^{k}_{r}\) is assigned to \(f^{k}_{i}\), but \(f^{k}_{i}\) is not instantiated at the beginning of \(t\), then the VNO will instantiate \(f^{k}_{i}\), but adequate delay penalties are added to \(RTT_{r}\), as shown in (3). Notice that we approximate the VNF instantiation states in the following manner: Any VNF that is not instantiated during \(t\) and receives a VNF request to manage starts its own instantiation and finishes such instantiation process at the beginning of the \(t+1\). From that moment on, unless the VNF has been turned off in the meantime because all its managed sessions are timed out, the VNF is considered ready to manage new incoming requests without any instantiation time penalty. Recall that we model three resource types for each VNF: CPU, Bandwidth, and Memory. We model the processing time of any \(r\) in \(f^{k}_{i}\) as the sum of the processing times related to each of these resources:  
\[\rho^{r}_{i,k}=\rho^{r}_{cpu,j,k}+\rho^{r}_{mem,j,k}+\rho^{r}_{bw,j,k} \tag{4}\]where \(\rho^{r}_{res,j,k},\forall res\in\{cpu,mem,bw\}\) are each of the resource processing time contributions for \(r\) in \(f^{t}_{i}\), and each of such contributions is computed as:  
\[\rho_{res,j,k}= \begin{cases}\rho^{*}_{res,k}\cdot\psi^{r_{max,j-1}}_{res,k},& \text{if }\frac{\mu_{res,j,k}}{\alpha_{res,k}}>1\\ \rho^{*}_{res,k},&\text{otherwise}\end{cases}  \tag{5}\]  
where:  
* the parameter \(\rho^{*}_{res,k}\) is the processing-time contribution of _res_ in any \(k\)-type VNF assuming optimal utilization conditions,
* \(\psi_{res,k}\) is a parameter representing the _degradation base_ for _res_ in any \(k\)-type VNF,
* the variable \(\mu_{res,k,i}\) is the _res_ utilization in \(f^{k}_{i}\) at the moment when \(f^{k}_{r}\) is assigned. Note that (5) models utilization-dependent processing times. The resource utilization in any \(f^{k}_{i}\), denoted as \(\mu_{res,k,i},\forall res\in\{cpu,mem,bw\}\) is computed as:  
\[\mu_{res,k,i}=