## 5 Distributed Mapping Algorithms  
Since the problem outlined in (6) is NP-hard due to the presence of multiple segments to be deployed on multiple nodes while respecting the time constraints as defined in (3), we resort to two heuristic algorithms. In particular, we focus on two algorithms, named _marginal gain maximization_ and _quality downgrade_. While in the first, we aim at minimizing the difference between the delivery deadline and the latency through a proper mapping, in the second algorithm, we aim at respecting the latency as a hard constraint while allowing a quality downgrade in selecting the proper segment. The marginal gain maximization algorithm gains from the fact that for reducing the outage defined in (5), we can first of all assign the segments that have the highest marginal gain between the playback rate and the transmission rate, i.e.,  
\[\max\left\{\frac{d_{ps}^{l}}{VBR(q)}-t^{k,n}(p_{m})\right\}\quad\forall p_{m},n \tag{8}\]  
This can be implemented by selecting the best assignment among the available nodes starting from the first segment of any requested video. We can rank the mapping of all the marginal gains and assign them in decreasing order. The best assignment will be the one allowing to have the highest marginal gain, hence minimizing the outage probability. As shown in Algorithm 1, the algorithm works by processing over all the nodes (line 1). It is initialized by reading the video request table, the related video for each user as well as the initial segments allocation map \(\mathbf{A}^{0}\) (lines 2-4). These data are used for evaluating the delays of all the possible placements of the segments in the allocation map on all the fog nodes in the network (lines 5-9). This evaluation is used for changing the placement of the chunks for maximizing the marginal gain of each segment (lines 11-14). The algorithm has a computational complexity of \(O(N\times P_{m}\times K)\). ```
1:\(\mathcal{U}\), \(\mathcal{V}\), \(\mathcal{F}\), \(\mathbb{P}\)
2:A
3:for all\(n\in\mathcal{U}\)do
4: Read the Video Request Table \(\mathbb{P}\)
5: Select the video \(m\) requested by the user \(n\)
6: Read the segments Allocation Map \(\mathbf{A}^{0}\)
7:for all\(p_{m}\in\mathbf{A}^{0}\)do
8:for all\(k\in\mathcal{F}\)do
9: Calculate \(\delta(n,k,p_{m})=\frac{d_{ps}^{l}}{VBR(q)}-t^{k,n}(p_{m})\)
10:endfor
11:endfor
12:for\(p_{m}\in\mathbf{A}^{0}\)do
13: Find \(\bar{k}=\arg\max\delta(n,k,p_{m})\)
14:\(A(\bar{k},p_{m})=q\)
15:endfor
```  
**Algorithm 1** Marginal gain maximization. The second algorithm, named _quality downgrade_, is based on (8) to check the marginal gain for every user having its own segments on any fog node. For any segment not respecting the constraint, the quality related to it will be reduced so as to respect the latency constraint. To this aim, a proper decision is taken based on the evaluation of the latency outage, defined as:  
\[\delta(n,k,p_{m})=\sum_{p_{m}=1_{m}}^{p_{m}}t^{k,n}(p_{m})-\sum_{p_{m}=1_{m}}^{ p_{m}}\frac{d^{\bar{q}p_{m}}}{VBR(\bar{q})} \tag{9}\]The goal of the algorithm is to offer an uninterrupted stream, even if it means providing segments with a lower quality than the user requested. This is more suitable in time-sensitive applications where the stream interruption would be avoided. As shown in Algorithm 2, it is possible to notice that each time the marginal gain is calculated, in the case that the latency outage in (9) is not respected, the quality is downgraded up to the lower level, i.e., \(q=1\), and the map allocation table updated accordingly. The computational complexity of the algorithm is \(O(N\times P_{m}\times K\times X)\), where \(X\) stands for the number of iterations in the while loop.