## 2 Materials and Methods
### Problem Modelisation
#### 2.1.1 Network Elements and Parameters  
We model three-node categories in the network infrastructure of a vCDN. The _content provider (CP) nodes_, denoted as \(N_{CP}\), produce live-video streams that are routed through the SFC to reach the end-users. The VNF _hosting nodes_, \(N_{H}\), are the cloud-hosted virtual machines that instantiate container VNFs and interconnect through each other to form the SFCs. Lastly, we consider nodes representing geographic clusters of clients, \(N_{UC}\). Geographic client clusters are created in such a way that every client in the same geographic cluster is considered to have the same data-propagation delays with respect to the hosting nodes in \(N_{H}\). Client cluster nodes will be referred to as _client nodes_ from now on. Notice that different hosting nodes may be deployed on different cloud providers. We denote the set of all nodes of the vCDN substrate network as:  
\[N=N_{CP}\cup N_{H}\cup N_{UC}\]  
We assume that each live-streaming session request \(r\) is always mapped to a VNF chain containing a Streamer, a Compressor, a Transcoder, and a Cache module [19; 50]. In a live-streaming vCDN context, the caching module acts as a proxy that ingests video chunks from a Content Provider, stores them on memory, and sends them to the clients towards the rest of the SFC modules. Caching modules accelerate session startup time and prevent origin server overloads, keep an acceptable total delay, improving session startup times which is a measure of QoE in the context of live-streaming. Compressors, instead, may help to decrease video quality when requested. On the other hand, transcoding functionalities are necessary whenever the requested video codec is different from the original one. Finally, the streamer acts as a multiplexer for the end-users [19]. The order in which the VNF chain is composed is explained by Figure 1.  
We will denote the set of VNF types considered in our model as \(K\):  
\[K=\{streamer,compressor,transcoder,cache\}\]  
Any \(k\)-type VNF instantiated at a hosting node \(i\) will be denoted as \(f_{i}^{k},\forall k\in K,\forall i\in N_{H}\). We assume that every hosting node is able to instantiate a maximum of one \(k\)-type VNF. Note that, at any time, there might be multiple SFCs whose k-type module is assigned to a single hosting node \(i\). We define fixed-length time windows denoted as \(t,\forall t\in\mathbb{N}\) which we call simulation time-steps following [14]. At each \(t\), the VNO releases resources for timed-out sessions and processes the incoming session requests denoted as \(R_{t}=\{r_{1},r_{2},...,r_{|R_{t}|}\}\). It should be stressed that every \(r\) will request for a SFC composed of all the VNF types in \(K\). We will denote the \(k\)-type VNF requested by \(r\) as \(\widehat{f}_{r}^{k},\forall k\in K,r\in R_{t}\). Key notations for our vCDN SFC Deployment Problem are listed in Table 1.  
We now enlist all the network elements and parameters that are part of the proposed optimization problem:  
* \(N=N_{CP}\cup N_{H}\cup N_{UC}\) as the set of all **nodes** of the CDN network,
* \(K=\{streamer,transcoder,compressor,cache\}\) is the set of **VNF types** considered in our model,
* \(L(N\times N)\), is the set of **links** between nodes in \(N\), so that \((i,j)\in L,\forall i,j\in N\),
* \(\mathbf{R}=\{CPU,Bandwidth,andMemory\}\), is the set of **resource types** for every VNF container,
* The **resource cost** matrix \(\Gamma\in\mathbb{M}(|\mathbf{R}|,|N_{H}|)\), where \(\gamma_{res,i}\) is the per-unit resource cost of resource _res_ at node \(i\),
* \(D\in\mathbb{M}(|N|,|N|)\), is the **link delay** matrix so that variable \(d_{i,j}\in\mathbb{R}^{+}\) represents the data propagation delay between the nodes \(i\) and \(j\). We assume \(d_{i,j}=0\) for \(i=j\). Notice that \(D\) is symmetric,
* \(O\in\mathbb{M}(|N|,|N|)\), is the **data-transportation costs** matrix, where \(o_{i,j}\in\mathbb{R}^{+}\) is the unitary data-transportation cost for the link that connects \(i\) and \(j\). We assume \(o_{i,j}=0\) for \(i=j\).