requests and cache servers.

We measure the MILP execution time for various numbers of clients’ requests
and cache servers (Fig. 3.5). Considering the optimization interval duration,
the proposed MILP model can handle about 60, 100, and 210 different requests
for 2, 4, and 6 sec. segments, respectively, in a topology with four cache
servers (see Fig. 3.5). The number of requests decreases when increasing the
number of cache servers. We now calculate the maximum number of clients that
each VRP can handle in a topology with four cache servers. As we discussed
earlier, in our experiments, each client sends 150 requests to download 150
segments with 2 seconds duration. We showed that the maximum time slot
duration should be less than or equal to 52 milliseconds; that means we have
about 5700 ($\frac{300}{0.052}$) time slots in each experiment. Assuming a
uniform distribution, each client sends a request in a given time slot with a
probability of 0.026 ($\frac{150}{5700}$). For instance, in the case of 60
requests as the maximum number of requests that can be handled by the proposed
MILP model in each time slot, one VRP can serve up to a maximum of 2300
clients and send 60 distinct requests per time slot
($2300\leq\frac{60}{0.026}$).

To investigate the behavior of the framework regarding different values of
$\alpha_{1}$, $\alpha_{2}$, and $\alpha_{3}$, we define three metrics:

  1. 1.

ACS: the usage percentage of cache servers with the shortest fetching time
(since the first term of the objective function (Eq. 3.6) forces the model to
select a cache server with the shortest fetching time).

  2. 2.

AMD: the average (for different $m$) of the maximum deviation between
requested quality and forwarded quality (second term of the objective function
(Eq. 3.6).

  3. 3.

AQB: the average of the video quality bitrate for all received segments in
Mbps (third term of the objective function (Eq. 3.6).

Fig. 3.6: Requested quality levels by the (a) BOLA and (b) SQUAD algorithms
vs. forwarded quality levels for client 1.

In the next experiment, we investigate the reactions of clients’ ABR
algorithms when their decisions are overwritten by replacement qualities. For
this purpose, we prioritize the quality coefficient ($\alpha_{3}=0.8$) and
select the identical small values for the fetching time and deviation
coefficients ($\alpha_{1}=0.1,\alpha_{2}=0.1$) to force the model to choose
appropriate replacement qualities in cache miss situations. Moreover, we set
$m=3$ to give the model a wider range of options for selecting the potential
replacement quality levels. All requested qualities and forwarded qualities
are logged by the VRP. As shown in Fig. 3.6 (client I), the requested quality
levels by the BOLA and SQUAD algorithms are overwritten multiple times by
better replacement qualities (e.g., segments 46 and 15 requested by BOLA (Fig.
3.6(a)) and SQUAD (Fig. 3.6(b)) respectively); however, that does not have a
negative impact on the overall playback quality of subsequent segments. Other
clients have a similar reaction to the replacement quality.

We extend our experiments by various values of $\alpha$ and $m$ and
investigate their impact on the aforementioned metrics. Table 3.3 shows the
results for group I of clients. As expected, most of the requested quality
levels are delivered from cache server I (denoted $c_{1}$) for a high
$\alpha_{1}$ value, which forces the system to emphasize low fetching time
($\alpha_{1}=0.8$, $\alpha_{2}=0.1$, $\alpha_{3}=0.1$). On the other hand,
setting $\alpha_{2}=0.8$ forces the model to deliver the quality levels as
requested by the clients and keeps AMD to zero ($\alpha_{1}=0.1$,
$\alpha_{2}=0.8$, $\alpha_{3}=0.1$). By setting $\alpha_{3}$ to a high value,
the model can serve higher quality levels to clients ($\alpha_{1}=0.1$,
$\alpha_{2}=0.1$, $\alpha_{3}=0.8$). Although increasing $m$ and $\alpha_{3}$
increases the AMD, the model performs negligible improvement in AQB since it
has a wider range to select replacement quality levels ($\alpha_{1}=0.1$,
$\alpha_{2}=0.1$, $\alpha_{3}=0.8$, and $m=3$).

Table 3.3: Impact of $m$, $\alpha_{1}$, $\alpha_{2}$, and $\alpha_{3}$ on MILP model behavior. m | Metric | ($\alpha_{1}$,$\alpha_{2}$,$\alpha_{3}$): (.8,.1,.1) | ($\alpha_{1}$,$\alpha_{2}$,$\alpha_{3}$): (.1,.8,.1) | ($\alpha_{1}$,$\alpha_{2}$,$\alpha_{3}$): (.1,.1,.8)
---|---|---|---|---
| ACS |  $c_{1}:56\%$, $c_{2}:25\%$ |  $c_{1}:51\%$, $c_{2}:31\%$ |  $c_{1}:46\%$, $c_{2}:36\%$
1 | AMD | 0 | 0 | 0
| AQB | 3.73 | 3.73 | 3.73
| ACS |  $c_{1}:55\%$, $c_{2}:26\%$ |  $c_{1}:53\%$, $c_{2}:29\%$ |  $c_{1}:54\%$, $c_{2}:29\%$
2 | AMD | 1 | 0 | 1
| AQB | 3.75 | 3.73 | 3.75
| ACS |  $c_{1}:56\%$, $c_{2}:36\%$ |  $c_{1}:52\%$, $c_{2}:31\%$ |  $c_{1}:52\%$, $c_{2}:32\%$
3 | AMD | 1 | 0 | .437
| AQB | 3.75 | 3.75 | 3.8
Fig. 3.7: (a) CDF of average playback bitrate, (b) average number of stalls,
(c) number of requests for each quality level, and (d) average number of
quality switches in pure client-based ABR, SABR, and ES-HAS systems for 60
clients.

As another experiment, we compare the performance of ES-HAS with the pure
client-based (video players in client groups I and II directly send their
requests to CDN edge servers I and IV, respectively) and the SABR Bhat et al.
(2017) approaches. Because Bhat et al. (2017) used different components than
we have in our testbed, we implemented the SABR approach and reproduced its
results without using its available source code. The $\alpha_{1}$,
$\alpha_{2}$, $\alpha_{3}$, and $m$ values are set to 1, 0, 0, and 0,
respectively, to have fair comparisons among the schemes; i.e., the VRP only
transmits the original requested quality from the optimal cache server. As
illustrated in Fig. 3.7 (a) and Fig. 3.7(d), the ES-HAS framework outperforms
the pure client-based method in terms of playback bitrate and the number of
quality switches since it fetches segments from the cache server with the
shortest fetching time. Although SABR and ES-HAS show (almost) identical
results in terms of the number of quality switches for both ABR methods (Fig.
3.7(d)), ES-HAS results in better performance in terms of playback bitrate
(Fig. 3.7(a)), the number of requests for the highest quality level (Fig.
3.7(c)), and the number of stalls compared to SABR (Fig. 3.7(b)). Recognizing
similar requests (video/segment/quality) and sending only one request instead
of several requests to the selected cache server, plus employing an
optimization-based approach for the cache/segment selection policy, are the
main reasons for ES-HAS performance improvements over SABR.

###  3.2 CSDN Framework

This section introduces the CSDN framework Farahani et al. (2021a) as a CDN-
aware QoE optimization solution in SDN-assisted HTTP Adaptive Video Streaming.
CSDN actually extends the ES-HAS framework by equipping its edge servers with
transcoding capabilities, making it suitable for both VoD and live streaming
scenarios. We motivate this work through an example in Section 3.2.1 and
elaborate on its architecture and optimization model in Section 3.2.2. The
CSDN evaluation setup and obtained results are described in Section 3.2.3.

####  3.2.1 CSDN Motivating Example and Problem Description

We present our primary motivation by an example shown in Figure 3.8. In this
example, we consider a simplistic scenario with only two cache servers, an
origin server, one VRP server, and a group of DASH clients. We assume DASH
clients request the segments of video $v$ in (i) a pure client-based approach
(Fig. 3.8(a)), (ii) the ES-HAS framework described in section 3.1 (Fig.
3.8(b)), and (iii) a CSDN-enabled system (Fig. 3.8(c)). In the pure client-
based approach, clients have to send their requests to only a preset cache
server, e.g., CS2 (the nearest cache server in terms of geographical location)
(step $1$). In case of a cache hit, CS2 directly replies to the requests
($4$). However, the cache server must hold the requests and fetch the
requested segments from the origin server for cache miss events ($2-3$).

As illustrated in Figure 3.8(b) and explained previously, ES-HAS utilizes an
edge component (called VRP) that aggregates clients’ requests (i.e., it
forwards only one request for a set of identical requests) in a time-slotted
fashion. After collecting requests for segments of a video $v$ ($1$) and
associated network information (i.e., the presence of representations of video
segments and available bandwidth from cache servers), the VRP runs an
optimization model with the depicted action list ($2$). In fact, ES-HAS
improves users’ QoE by (i) selecting an optimal cache server that has the most
available bandwidth or the least fetching time than other servers (denoted by
$t_{origin},t_{cs1},t_{cs2}$ for origin server and cache servers,
respectively) or (ii) using a replacement quality level (denoted by $q$) to
serve the originally requested quality (denoted by $p$) with the minimum
deviation (only from cache servers denoted by $d_{cs1}^{pq},$ $d_{cs2}^{pq}$).
Although ES-HAS solves the aforementioned problems of a pure client-based
system, it still suffers from some constraints. Imagine a scenario that the
demanded quality levels are available only on one cache server (e.g., CS2);
ES-HAS forces the VRP to fetch the original segments from CS2 ($2-4$).
Finally, the fetched segments are transferred to clients ($5$). In this case,
if another server (i.e., CS1) with more available bandwidth could serve the
requested segments with higher quality levels, ES-HAS ignores it. In another
scenario, imagine the requested segments are unavailable in all cache servers,
and the quality deviation is unacceptable for the clients. Hence, the desired
quality levels must be fetched from the origin server to the VRP and cache
servers, leading to a considerable backhaul bandwidth consumption.

CSDN framework equips the ES-HAS VRP with the transcoding capability to remedy
the aforementioned problems. As shown in Figure 3.8(c), the clients send
requests ($1$) to the VRP for the desired segments’ qualities, and the VRP
collects these requests in each time slot with the aggregation technique.
After receiving the mentioned demanded network information, plus user
preferences, the VRP runs an optimization program by taking into account two
different groups of actions, i.e., fetching- and transcoding-based actions
($2$). The first group, like ES-HAS, considers the fetching time and quality
deviations, while the latter group is based on the serving time (i.e.,
fetching time and transcoding time ($T_{pq}$) values).

Fig. 3.8: (a) Pure client-based, (b) ES-HAS, and (c) CSDN approaches.

For simplicity, let us proceed by turning to the considered scenarios. In both
scenarios, CSDN uses a hybrid approach i.e., fetches the quality level $q$ as
a replacement quality from CS1 (i.e., quality with the minimum fetching time,
and cache server with a higher bandwidth value) ($3-4$), and transcodes it to
the quality level $p$ at the edge ($5$). Next, it forwards the desired
segments back to the clients ($6$). The details of CSDN will be discussed in
the next section. In this work, we introduce the CSDN VRP at the edge of the
network as an ES-HAS VRP extended with transcoding capabilities, which
increases the computational costs of the system. However, the backhaul
bandwidth consumption and users’ QoE (based on their preferences) are
significantly improved by the VRP possibly performing additional actions.
According to the presented motivating example, we can define the following
problem: “How should VRPs serve many clients’ requests to minimize the quality
deviations and serving times (i.e., fetching and transcoding time) based on
the stated action list and different categories of clients?”

####  3.2.2 CSDN System Design

This section introduces the CSDN architecture and its main components before
elaborating on the CSDN’s problem formulation.

#####  3.2.2.1 CSDN Architecture

Inspired by the overall architecture of an SDN-enabled network, we design the
CSDN architecture in three main layers (Figure 3.9), where each layer consists
of a set of components that are described as follows:
$(1)$ Data Layer: This layer consists of four groups of entities, i.e., (i)
DASH clients, (ii) CDN components, including an origin server and multiple
cache servers, (iii) several VRP servers as gateways for DASH clients to the
network and vice versa, and (iv) OpenFlow (OF) switches that are connected to
an SDN controller, CDN servers, and VRPs.
$(2)$ Control Layer: An SDN controller is placed in this layer.
$(3)$ Application Layer: The application layer comprises different components
that are categorized into four groups regarding their functionalities: (i) VRP
server modules, (ii) databases, (iii) third-party service, and (iv) controller
modules.
These entities in the CSDN architecture collaborate as follows to serve DASH
clients’ requests efficiently. The SDN controller periodically monitors the
cache servers’ occupancy information (cache maps) and paths’ available
bandwidths and stores them in its database (C-DB). We define a Resource
Monitoring Module (RM) as one of the main controller modules to collect the
aforementioned CDN- and network-level information from the OF switches. The
C-DB data will be used by the controller’s Data Path Selection Module (DPS) in
order to set up new routes in the network (i.e., between VRP and CDN
components), or by the VRP server modules in order to select the next
segments/servers efficiently.

Fig. 3.9: Proposed CSDN architecture.

It is worth noting that, like our previous system ES-HAS does, CSDN operates
in a time-slotted manner with an equal time slot duration of $\theta$. Each
time slot consists of two modified intervals: (i) Data Collecting and (ii)
Optimization Intervals.

In the first interval, user- and device-level information (e.g., user
identity, the associated devices, and users’ video requests) are gathered and
aggregated by the VRP’s User/Device Data Collector Module (UDC). This data is
provided by the User Classifier Module (UC) of a third-party service to which
the user is subscribed (e.g., Netflix or Amazon Prime). It is assumed that the
aforementioned information will be available by the third-party service.
Consequently, when clients request video segments during each time slot, the
UDC fetches the associated profiles and collects the basic specifications
(e.g., display size, buffer size, type of device, and subscription plan), and
assigns a user priority to each client.

To prevent sending identical requests (issued by multiple clients in a given
time slot), the VRP’s Request Analyzer Module (RA) identifies received user-
level information from the UDC, considers only one request per segment, and
stores the requests in the VRP’s database (V-DB). Moreover, using RESTful
messages, the VRP periodically retrieves the required information (i.e., cache
maps plus available bandwidths between each cache server and the VRP that are
available in the C-DB) from the SDN controller. In the second interval, the
VRP’s Service Optimizer Module (SO) is executed to serve clients’ requests
optimally.

The data transmission will start in the first interval of the next time slot
according to the SO’s results. Actually, for each request the SO selects an
appropriate cache server that hosts the requested quality by using the
optimization model presented later in this section. However, in some
situations, e.g., when the requested quality is not available in a cache
server, the SO chooses one of the following solutions based on users’
preferences, then the VRP’s Transcoder/Fetching Module (T/F) prepares the
optimal segment from an optimal server: (i) determine the optimal replacement
quality level on a cache server (with the minimum deviation from the original
requested quality level) and forward it to the associated clients; (ii)
determine the optimal replacement quality level on a cache server and
transcode it to the original requested quality level;
(iii) fetch the original requested quality from the origin server.

Like in ES-HAS, we utilize the notion that a requested quality level of a
segment may be overwritten by a replacement quality, based on Consumer
Technology Association’s Common Media Client Data (CMCD) standard Consumer
Technology Association (2020). To do that, we assume that a client can accept
only better replacement quality levels instead of the actual requested quality
of a segment. Furthermore, we employ the replacement quality levels determined
by the SO as reference segments for the transcoding process in T/F. For the
sake of simplification, we assume that each DASH client can request just one
segment during each time slot. However, it is possible to take into account
multiple requests from each client in each time slot without significant
changes in the proposed model. We will demonstrate how to determine the time
slot duration in Section 3.2.3.

Table 3.4: CSDN Notation. Input Parameters |  |  |  |
---|---|---|---|---
| $\mathcal{S}$
---
$\mathcal{C}$
$\mathcal{T}$
$\mathcal{A}$
$a^{c,s}_{q}$
$\mu^{c}_{q,p}$
$\omega^{c}_{q,p}$
$\mathcal{R}$
$R_{s}$
$i_{c}$
$m$
$\mathcal{K}_{c}$
$\delta^{c}_{q}$
$\pi^{c}_{q}$
$\theta$
$\Omega$
| Set of cache servers and origin server, $s\in\mathcal{S}$
---
Set of clients, $c\in\mathcal{C}$
Set of transcoding status, $t\in\mathcal{T}$
Set of available quality levels in $\mathcal{S}$
$a^{c,s}_{q}=1$ if quality $q$ requested by client $c$ is available in server
$s$, $a^{c,s}_{q}=0$ otherwise
Required time to transcode quality $p$ requested by client $c$ from quality
$q$ at VRP
Required computational resource (CPU usage in %) to transcode quality $p$
requested by client $c$ from quality $q$ at VRP
Set of available bandwidth values
The available bandwidth between the VRP to server $s$
Quality level requested by client $c$
Integer number to limit the range of potential replacement quality levels for
$i_{c}$
Set of eligible quality levels for a quality requested by client $c$, where
$\mathcal{K}_{c}=\\{i_{c},{i_{c}}+1,...,min[{i_{c}}+m,q_{max}]\\}$
Size of the segment of quality level $q$
Bitrate of the segment of quality level $q$
Time slot duration
Compute resource threshold (max. CPU usage in %) for transcoding
|  |  |
Variables |  |  |  |
| $B^{c,s}_{q,t}$
---
$D_{c}$
$T^{c,s}_{q}$
$\tau_{c}$
$\Gamma^{c,s}_{q}$
|  $B^{c,s}_{q,0}$=1 if quality $q$ requested by $c$ is served from server
$s$, $B^{c,s}_{q,1}$=1
---
if quality $q$ requested by $c$ is served from server $s$ and transcoded
at the VRP, $B^{c,s}_{q,1}$=0 otherwise
Deviation of quality level to serve client $c$ w.r.t. $i_{c}$
Required time to fetch quality $q$ for client $c$ from server $s$
Required transcoding time of quality level to serve client $c$ w.r.t. $i_{c}$
Serving time consisting of $T^{c,s}_{q}$ and $\tau_{c}$
|  |  |

#####  3.2.2.2 CSDN Optimization Problem Formulation

As discussed earlier, the VRPs’ SO module is responsible for executing a
server/segment selection policy to serve clients’ requests optimally, i.e.,
(i) determine an optimal server, and (ii) select appropriate actions (i.e.,
fetch-based or transcoding-based actions) based on users’ preferences. For
that, we introduce a mixed-integer linear programming (MILP) optimization
model. The proposed MILP model finds the optimal solution by minimizing the
serving times, including server fetching time and transcoding time, and the
segments’ quality level deviations.

Let set $\mathcal{A}$ denote the cache map (i.e., availability of
segments/bitrates) that a VRP receives from the SDN controller, where
$a^{c,s}_{q}=1$ means that the quality level $q$ requested by client
$c\in\mathcal{C}$ is available on the server $s\in\mathcal{S}$ (see Table 3.4
for notations). Moreover, let a VRP’s database (V-DB) host set $\mathcal{R}$
containing available bandwidth values between the cache servers and the VRP.
We derive the following constraints that must be satisfied to achieve an
optimal solution. Let us define $i_{c}$ as the quality level requested by
client $c\in\mathcal{C}$. We also define
$\mathcal{K}_{c}=\\{i_{c},{i_{c}}+1,...,min[{i_{c}}+m,q^{c}_{max}]\\}$ as the
set of eligible (potentially, replacement) quality levels for the segment
requested by client $c$, where $m$ and $q^{c}_{max}$ denote the maximum
deviation from $i_{c}$ and the maximum quality level of the segment requested
by $c$, respectively.

In each optimization interval, we select only one server to serve the client
$c$. For this purpose, we introduce binary variable $B^{c,s}_{q,t}$, with the
meaning defined in Table 3.4. As mentioned earlier, in the case of a cache
miss, i.e., when $i_{c}$ is not available in any cache server, the VRP can
fetch it from the origin server, use other quality levels available in cache
servers, or transcode it from the fetched replacement quality from a cache
server. Thus, constraint ($1$) must be satisfied:

$\displaystyle\sum_{t\in\mathcal{T}}\sum_{s\in\mathcal{S}}\sum_{q\in\mathcal{K}_{c}}B^{c,s}_{q,t}~{}.~{}{a}^{c,s}_{q}=1,$
$\displaystyle\hskip 11.38092pt\forall c\in\mathcal{C}$ (3.7)

Moreover, we should force the model not to select a replacement quality from
the origin server by constraint ($2$):

$\displaystyle\sum_{t\in\mathcal{T}}\sum_{q\in\mathcal{K}_{c}}B^{c,s}_{q,t}~{}.~{}q=i_{c}$
$\displaystyle\forall c\in\mathcal{C},\text{where }s=Origin$ (3.8)

The required time to fetch the quality level $q$ for client $c$ from server
$s$, denoted by $T^{c,s}_{q}$, is determined by constraint ($3$):

$\displaystyle\delta^{c}_{q}~{}.~{}\sum_{t\in\mathcal{T}}B^{c,s}_{q,t}\leq
T^{c,s}_{q}~{}.~{}R_{s},$ $\displaystyle\forall
c\in\mathcal{C},q\in\mathcal{K}_{c},s\in\mathcal{S},$ (3.9)

where $\delta^{c}_{q}$ is the size of the quality $q$ requested by client $c$
and $R_{s}$ is the available bandwidth between the VRP and cache server $s$.
We also define $\tau_{c}$ as the transcoding time to serve client
$c\in\mathcal{C}$ according to constraint ($4$):

$\displaystyle\sum_{q\in\mathcal{K}_{c}}B^{c,s}_{q,t}~{}.~{}\mu^{c}_{q,p}\leq\tau_{c},$
$\displaystyle\forall c\in\mathcal{C},s\in\mathcal{S},p=i_{c}\text{ and }t=1$
(3.10)

where $\mu^{c}_{q,p}$ is defined based on the meaning in Table 3.4. Moreover,
the model should consider the resource limitations, i.e., available bandwidth
on network paths and the available VRPs’ computational resources. For this
purpose, the selected quality should not violate $R_{s}$, the available
bandwidth between the server $s$ to VRP, and $\Omega$, the VRP’s computational
resource threshold for transcoding (expressed as maximum CPU usage in %). Thus
the following constraints ($5-6$) must be satisfied:

$\displaystyle\sum_{t\in\mathcal{T}}\sum_{c\in\mathcal{C}}\sum_{q\in\mathcal{K}_{c}}B^{c,s}_{q,t}~{}.~{}\pi^{c}_{q}\leq
R_{s}$ $\displaystyle\forall s\in\mathcal{S}$ (3.11)
$\displaystyle\sum_{s\in\mathcal{S}}\sum_{c\in\mathcal{C}}\sum_{q\in\mathcal{K}_{c}}B^{c,s}_{q,t}~{}.~{}\omega^{c}_{q,p}\leq\Omega,$
$\displaystyle\text{where }t=1\text{ and }p=i_{c}$ (3.12)

where $\pi^{c}_{q}$ is the bitrate of the selected quality level $q$ for
serving client $c$, and $\omega^{c}_{q,p}$ is the required computational
resource (i.e., CPU usage in %) to transcode quality $p$ requested by client
$c$ from quality $q$ at the VRP. To determine the quality deviation when the
requested quality $i_{c}$ is not available in $\mathcal{K}_{c}$ or the
requested quality has to be transcoded from the replacement quality, we
introduce constraint ($7$):

$\displaystyle\sum_{s\in\mathcal{S}}\sum_{q\in\mathcal{K}_{c}}(B^{c,s}_{q,t}~{}.~{}q)-i_{c}\leq
D_{c}$ $\displaystyle\forall c\in\mathcal{C},\text{where }t=0$ (3.13)

Finally, the optimization problem can be written as follows:

Minimize $\displaystyle\hskip
14.22636pt\sum_{c\in\mathcal{C}}\sum_{s\in\mathcal{S}}\sum_{q\in\mathcal{K}_{c}}\alpha_{c}~{}.~{}\frac{\Gamma^{c,s}_{q}}{\mathbf{M}_{\Gamma}}+\sum_{c\in\mathcal{C}}\beta_{c}~{}.~{}\frac{D_{c}}{\mathbf{M}_{D}}$
(3.14) $\displaystyle s.t.$ $\displaystyle\hskip
14.22636pt\text{Constraints}\hskip
14.22636pt\text{Eq.}(\ref{CSDN:eq:1})-\text{Eq.}(\ref{CSDN:eq:7})$
$\displaystyle\hskip 14.22636ptT^{c,s}_{q}+\tau_{c}=\Gamma^{c,s}_{q},\hskip
42.67912pt\forall c\in\mathcal{C},q\in\mathcal{K}_{c},s\in\mathcal{S}$
$\displaystyle vars.$ $\displaystyle\hskip
14.22636ptT^{c,s}_{q},\tau_{c},\Gamma^{c,s}_{q},D_{c}\geq
0,B^{c,s}_{q,t}\in\\{0,1\\}$

where $\mathbf{M}_{\Gamma}$ and $\mathbf{M}_{D}$ are the maximum values for
the serving time and the quality level deviation, respectively. The SO runs
the above model for all clients’ requested qualities in a time-slotted manner
to minimize the serving times (i.e., fetching time plus transcoding time) and
the quality level deviations. Moreover, we define two weight coefficients
$\alpha_{c}$ and $\beta_{c}$ to set desirable priorities for
$\Gamma^{c,s}_{q}$ and $D_{c}$. These weights can be adjusted based on each
user’s preference where $\alpha_{c}+\beta_{c}$ =1.

####  3.2.3 CSDN Performance Evaluation

In this section, we first describe the evaluation setup and then discuss the
performance evaluation of CSDN compared to ES-HAS (Section 3.1), SABR Bhat et
al. (2017), and a pure client-based approach.

#####  3.2.3.1 Evaluation Setup

Our testbed consists of 114 nodes running on Ubuntu 18.04 LTS inside Xen
virtual machines. The VRPs use a 2.6 GHz, 6 Core CPU with 32 GB RAM. The
proposed network topology is instantiated in the CloudLab Ricci et al. (2014)
environment.

As illustrated in Figure 3.10, it consists of five OpenFlow (OF) switches, 100
AStream DASH players Juluri et al. (2015); AStream (2020) in headless mode,
four VRP servers with the modules described in Section 5.5. Note that, in the
current implementation, we assume homogeneous devices for all users,
therefore, we use the client IP addresses as their identifiers. Moreover, we
use four cache servers and one additional server that jointly hosts an origin
server and a dockerized SDN controller. Cache servers I, II, III, IV are
considered as local cache servers for client groups I, II, III, IV,
respectively. The bandwidth values in different paths between cache servers I,
II, III, IV, and the origin server to each VRP server are adjusted as follows:
VRP I:{120, 100, 60, 80, 20}, VRP II:{100, 120, 80, 60, 20}, VRP III:{60, 100,
120, 80, 20}, VRP IV:{80, 60, 100, 120, 20} (all in Mbps), which explicitly
prioritize downloading segments from local cache servers. Apache Apache (2020)
and MongoDB MongoDB (2020) with supporting RESTful APIs for cache map exchange
are installed on all cache servers. Moreover, Least Recently Used (LRU) is
considered in all cache servers as the cache replacement policy.

The policy on a cache miss is that the requested quality will be fetched from
the origin server to all cache servers. Floodlight Floodlight (2020) is
utilized as an SDN controller. Among other tasks, it monitors the network to
find paths’ available bandwidths (in one-second intervals) and then assigns
the path with the highest available bandwidth between each cache server and a
VRP server. For the sake of simplicity, we assume that all clients already
joined the network and users’ information is available in the third-party
service (see Fig. 3.9).

Fig. 3.10: CSDN evaluation testbed.

Ten test videos Lederer et al. (2012) with 300 seconds durations each are used
in our experiments. These videos comprise two-second segments in five
representations (0.089, 0.262, 0.791, 2.4, 4.2 Mbps).

Although different strategies, e.g., a popularity-based approach, could be
used for the distribution of videos over CDN servers and for the clients’
requests patterns, for the sake of simplicity we adopt the following scheme.
60% of the videos’ segments are stored in each cache server randomly in most
scenarios (only in one scenario, we store 30% to 60% videos segments on cache
servers). Moreover, each client requests one video where $video_{1}$ is
streamed to clients (1,11,21,31,41,51, 61,71,81,91), $video_{2}$ is streamed
to clients (2,12,22,32,42,52,62,72,82,92), and so on. The time slot duration
is adjusted to 32 milliseconds in all experiments. (We will discuss how to
obtain the time slot duration in the next subsection). Two different ABR
algorithms, BOLA Spiteri et al. (2016) and SQUAD Wang et al. (2016),
representing buffer-based and hybrid approaches, are used in all experiments.
Computational resource threshold (i.e., $\Omega$) is set to 50% of the overall
VRPs’ CPU usage. Python and the PuLP library PuLP (2020) are employed to
implement and solve the CSDN MILP model. We use bitrate as the representative
metric to evaluate the quality of segments, i.e., the higher the bitrate, the
higher the quality. The “veryfast” preset of FFmpeg FFmpeg (2020) is used for
transcoding since we found it to induce less video distortion compared to
“ultrafast” or “superfast” presets, at good transcoding speed.

#####  3.2.3.2 Evaluation Results

As mentioned in Section 3.2.2, gathering different information items (in the
data collecting interval) and running the MILP model (in the optimization
interval) to determine the optimal servers/segments are done in a time-slotted
manner. An inaccurate time slot value imposes an additional delay in the
client’s request-response interval (due to an overly long time slot duration
in the VRP) and may convey an incorrect network situation to the client;
consequently, the client may request a lower quality level for the next
segment. Therefore, in the first experiment, we investigate various time slot
durations for two-second segment durations in order to determine suitable
values of $\theta$.

We connect four clients to a server with limited bandwidth of 20 Mbps and
start the experiment with the initial value of $\theta=2$ sec and gradually
decrease it in each run by 10 milliseconds. When we set $\theta=0$, all four
clients request the highest quality levels (i.e., 4 x 4.2 Mbps) and receive
the highest qualities (4 x 4.2 Mbps) from the server with 20 Mbps bandwidth.
The results show that clients start to request lower quality levels for time
slot durations longer than 32 milliseconds (e.g., the results for four
$\theta$ values are shown in Fig. 3.11). Repeating the experiment shows that
these values are 70 and 165 milliseconds for 4 and 6 sec. segments,
respectively. We also studied the time slot duration in more complex settings
(like the one used for the experiments, Fig. 3.10), with the same results. Let
us consider the worst-case and imagine that clients’ requests arrive at the
beginning of the optimization interval; then, they will wait to be processed
in the next optimization interval. In other words, a request could wait for
two optimization intervals plus a data collecting interval. To avoid
optimization interval overlapping, similar to ES-HAS, we assume the
optimization interval should be less than or equal to $\frac{\theta}{2}$.
Therefore, based on the first experiment, the optimization interval should be
shorter than 16, 35, and 82 milliseconds for 2, 4, and 6 sec. segments,
respectively.

Fig. 3.11: Impact of changing $\theta$ on playback bitrate: (a) $\theta$ =
0.5s, (b) $\theta$ = 50 milliseconds, (c) $\theta$ = 32 milliseconds, and (d)
$\theta$ = 0.

In the second experiment, similar to ES-HAS evaluation strategy, we
numerically study the scalability of the proposed MILP model. For that, we
increase the number of clients’ requests gradually (by four requests) and
measure the proposed MILP execution times on the same server that runs the
VRP’s modules. The results show that CSDN MILP model can handle about 13, 35,
and 72 different requests at the discussed optimization times (i.e.,
$\frac{\theta}{2}$) for 2-, 4-, and 6-sec. segments, respectively, in a
topology including four cache servers. This is less than in ES-HAS, which
could process about 60, 100, and 210 requests per optimization interval in the
same condition. Now, let us calculate the maximum number of clients that can
be handled by a VRP in the aforementioned topology. Each client sends 150
requests to download 150 segments with 2 seconds in our experiments. With a
time slot duration of 32 milliseconds, we have 9375 ($\frac{300}{0.032}$) time
slots in each experiment. Assuming a uniform distribution, each client sends a
request in a given time slot with a probability of 0.016 ($\frac{150}{9375}$).
Assuming that up to 13 distinct requests can be handled by the CSDN MILP model
in each time slot, one VRP can serve up to a maximum of 812 clients
($812\leq\frac{13}{0.016}$); this number is 2300 in the ES-HAS approach.
Utilizing transcoding-based actions leads to an increase of the MILP model
execution time; in conjunction with different time slot durations, this
decreases the number of managed requests/clients in CSDN as compared to ES-
HAS.

Fig. 3.12: Requested quality levels by (a) CSDN-BOLA and (b) CSDN-SQUAD vs.
forwarded quality levels for client 50.

In the next experiment, we study the reactions of clients’ ABR algorithms when
replacement qualities overwrite their decisions. To do that, we set $\alpha$,
$\beta$, and $m$ to 0.9, 0.1, and 4 for all clients to permit the MILP model
transmitting replacement quality levels in case of cache misses. All events in
the system, e.g., requested qualities, forwarded qualities, selected servers
are logged by the VRP. As shown in Figure 3.12, the requested quality levels
of the BOLA and SQUAD algorithms are overwritten multiple times by replacement
qualities (depicted by blue circles); however, the overall playback quality of
subsequent segments is not significantly damaged. Other clients have a similar
reaction to the replacement quality.

Fig. 3.13: (a) Average number of downloaded video quality levels, (b) average
number of quality switches, and (c) average number of stalls for pure client-
based ABR algorithms, SABR, ES-HAS, and CSDN for 100 clients.

In another scenario, we compare the performance of CSDN with the pure client-
based, SABR Bhat et al. (2017), and ES-HAS (Section 3.1) approaches, when 60%
of the video dataset is uploaded on cache servers randomly. In the pure
client-based approach, video players in the four client groups I to IV
directly send their requests to their preset cache server (i.e., cache server
I for client group I, cache server II for client group II, and so on). Because
SABR employed different components than we have in our testbed (e.g., the SDN
controller, the monitoring module), we implemented the SABR system and
reproduced its results without using its available source code. The ES-HAS
model’s parameters (i.e., $\alpha_{1}$, $\alpha_{2}$, $\alpha_{3}$, and $m$)
and the CSDN model’s parameters ($\alpha$, $\beta$, and $m$) are set to (0.9,
0.1, 0, 4) and (0.9, 0.1, 4), respectively, to prioritize serving time and let
both systems use the replacement quality levels on cache misses. Figures 3.13
and 3.14(a) depict that the CSDN framework (for both ABR algorithms)
outperforms the other methods in terms of the average bitrate distribution
(Fig. 3.13(a)), the average number of quality switches (Fig. 3.13(b)), the
average number of stalls (Fig. 3.13(c)), the number of fetches from the origin
server, and backhaul bandwidth (Fig. 3.14(a)). In fact, CSDN outperforms the
pure client-based method by fetching demanded segments from the cache server
with the shortest serving time. Moreover, our proposed approach improves over
SABR’s results by (i) identifying identical client requests
(video/segment/quality), (ii) sending only one request instead of several
requests to the selected cache server, and (iii) applying an optimization-
based approach for the server/segment selection policy. Employing an expanded
action list (i.e., transcoding-based actions besides fetch-based actions) and
deciding accurately about server/segment selection helps CSDN fetch the
requested segments from (i) a cache server with higher available bandwidth
(effective on reducing the number of fetches from the origin server, backhaul
bandwidth usage, and the number of stalls), and (ii) with minimum deviation
(effective on reducing the number of quality switches), consequently improving
over the ES-HAS results.

Fig. 3.14: (a) Network backhaul bandwidth usage and number of fetches from the
origin server for different approaches, and (b) network backhaul bandwidth
usage and number of transcoded segments for different percentages of preloaded
segments on cache servers for BOLA-CSDN for 100 clients.

In the next scenario, we upload different amounts of the videos’ segments
(i.e., from 30% to 60%) on cache servers randomly and measure the backhaul
bandwidth usage and the number of transcoded segments in the CSDN system. The
results for BOLA-CSDN (Fig. 3.14(b)) show that, when cache servers contain a
small number of video sequences/segments, the number of fetches from the
origin server (to VRPs or cache servers) and the backhaul bandwidth
consumption increase; moreover, CSDN needs to apply more transcoding actions
to save backhaul traffic. However, less content distribution in the caches
causes the number of transcoding not to increase significantly. An in-depth
analysis shows that CSDN consumes less network bandwidth than other frameworks
even with less content in the caches. For instance, CSDN consumes less than
900 Mbps of backhaul bandwidth by using only 40% of cache storage (Fig.
3.14(b)), which is almost equal to the ES-HAS bandwidth consumption with 60%
of content in the caches (see BOLA-ES-HAS in Fig. 3.14(a)).

Fig. 3.15: CDF of average playback bitrate (a–b) and number of replacement
quality levels and maximum quality deviation (c–d) for two types of users (I,
II); parameters in (a) and (c): type I: $\alpha$=0.9, $\beta$=0.1; type II:
$\alpha$=0.1, $\beta$=0.9; parameters in (b) and (d): type I: $\alpha$=0.1,
$\beta$=0.9 and type II: $\alpha$=0.9, $\beta$=0.1.

As a final scenario, we investigate the behavior of the CSDN system for two
different types of users. For that, we set various values of $\alpha$ and
$\beta$ as serving time and quality level deviation coefficients,
respectively, to create two types of users. For instance, by setting
($\alpha_{c}=0.9$ and $\beta_{c}=0.1$) for users’ type I, and
($\alpha_{c}=0.1$ and $\beta_{c}=0.9$) for users’ type II, CSDN serves their
requests based on serving times, and quality level deviations, respectively.
The results for user types I and II, including 40 and 60 clients,
respectively, are illustrated in Figure 3.15. As shown, SQUAD-CSDN has better
performance for both user types compared to BOLA-CSDN in terms of playback
bitrate, the number of replacement qualities, and maximum quality deviation.
Moreover, the results show prioritizing $\beta$ does not necessarily force the
model to fetch fewer replacement quality levels; in fact, the replacement
quality can be used for transcoding actions too.

###  3.3 Summary

This chapter proposed the ES-HAS framework as an edge- and SDN-assisted
framework for HAS clients. In an ES-HAS-enabled system, cache server
occupancy, available bandwidth values, and requested video quality levels are
considered as feasible and useful information from the CDN/SDN and HAS
clients. Virtualized Reverse Proxy (VRP) servers at the edge of the ES-HAS
system are introduced to assist clients in receiving requested quality levels
from the cache servers with the shortest fetching time. In case of a cache
miss, a client’s request is served by a replacement quality (only better
quality levels with minimum deviation) from a cache server, or by the
originally requested quality level from the origin server. This goal is
achieved through a comprehensive network view provided by the SDN controller,
collecting relevant information from the CDN (cache server occupancy) and from
clients (requested video qualities) in a time-slotted manner. We formulated
our problem as an MILP model considering resource constraints. We designed a
midscale testbed, including 60 HAS clients and ran several experiments to
evaluate the ES-HAS performance through QoE parameters and compared the
obtained results with another state-of-the-art approach Bhat et al. (2017) and
two client-based schemes Spiteri et al. (2016); Wang et al. (2016). The
experimental results showed that, although the SABR state-of-the-art system
Bhat et al. (2017) and ES-HAS performed (almost) identically in terms of the
number of quality switches, ES-HAS outperformed SABR in terms of playback
bitrate (by at least 70%) and the number of stalls (by at least 40%).

We equipped the ES-HAS VRPs with transcoding capability and introduced a CDN-
Aware QoE Optimization in SDN-Assisted HTTP Adaptive Video Streaming framework
called CSDN. We also introduced a new server/segment selection policy and
formulated it as an MILP model to serve clients’ requests from servers with an
appropriate fetching time. This MILP model was enabled to determine a
replacement quality (with the minimum quality deviation) instead of the
originally requested quality or to decide on transcoding the requested quality
from an available higher quality at the edge in case that quality is not
available in the cache servers. We scaled up the ES-HAS architecture and
deployed CSDN on a testbed, including 100 clients and four edge devices. The
obtained results demonstrated that CSDN not only (i) improved the users’ QoE,
e.g., the overall video playback bitrate (7.5%), the number of quality
switches (19%), or the number of stalls (19%) at the client, but also (ii)
reduced backhaul bandwidth usage (63%) compared to the SABR and ES-HAS
systems.

##  Chapter 4 SFC-Enabled Architecture for HAS

5G and 6G networks are expected to support various novel emerging adaptive
video streaming services (e.g., live, VoD, immersive media, and online gaming)
with versatile QoE requirements such as high bitrate, low latency, and
sufficient reliability. It is widely agreed that these requirements can be
satisfied by adopting emerging networking paradigms like SDN, NFV, and MEC.
Previous studies have leveraged these paradigms to present NAVS frameworks,
but mostly in isolation without devising chains of VNFs that consider the QoE
requirements of various types of multimedia services (MSs). To bridge the
aforementioned gaps, in this chapter, we first introduce a set of multimedia
VNFs, i.e., Virtual Proxy Function (VPF), Virtual Transcoding Function (VTF),
and Virtual Cache Function (VCF) at the edge of an SDN-enabled network. We
also form diverse Service Function Chains (SFCs) based on the QoE requirements
of different MSs. We then propose SARENA as an SFC-enabled architecture for
adaptive video streaming applications. Next, we formulate the problem as a
central scheduling optimization model executed at the SDN controller. We also
present a lightweight heuristic solution consisting of two phases that run on
the SDN controller and edge servers to alleviate the time complexity of the
optimization model in large-scale scenarios. Finally, we design a large-scale
cloud-based testbed including 250 HAS players requesting two popular MS
applications (i.e., live and VoD), conduct various experiments, and compare
SARENA’s effectiveness with baseline systems. Experimental results illustrate
that SARENA outperforms the baseline schemes in terms of users’ QoE and
network utilization in both MSs.
The contribution of this chapter, i.e., “SARENA: SFC-Enabled Architecture for
Adaptive Video Streaming Applications” has been accepted for publication at
the IEEE International Conference on Communications (ICC) 2023 Farahani et al.
(2023b).

###  4.1 SARENA Framework

This section introduces SARENA Farahani et al. (2023b) as an SFC-enabled
architecture for adaptive video streaming applications. We explain the details
of the SARENA architecture and problem formulation in Section 4.1.1. We then
propose a lightweight heuristic method to solve the problem in Section 4.1.2.
The SARENA evaluation setup, methods, metrics, and obtained results are
described in Section 4.1.3.

####  4.1.1 SARENA System Design

In this section, we first delve into the SARENA architecture and then model
the problem as an MILP optimization problem.

#####  4.1.1.1 SARENA Architecture

SARENA consists of three network layers as shown in Fig. 4.1. These layers
are:

  1. 1.

Edge Layer (EL). This layer includes edge servers close to base stations
(e.g., gNodeB in 5G) and clients. Inspired by the Consumer Technology
Association CTA-5004 standard CTA-5004 (2020), each edge server periodically
communicates with the SDN controller and shares its available computational
resources’ status, e.g., CPU and RAM (in so-called comp stat messages), the
number of connected clients (client stat messages), the number/type of
multimedia service requests (MS stat messages), and the cache occupancy (in
edge stat messages) with the SDN controller. All edge devices are equipped
with the following VNFs:
1 Virtual Proxy Function (VPF), which enables an edge server to play the role
of a gateway between its associated clients and the network, i.e., receiving
clients’ demands for different MS services, employing determined decisions by
the SDN controller, and responding to them.
2 Virtual Cache Function (VCF), utilized to store a limited number of popular
segments for different MS services.
3 Virtual Transcoding Function (VTF), responsible for using computational
resources and transcoding high quality segments to the required lower quality
levels. These functions are placed at the edge can collaborate and/or use
other layer services to build SFCs and serve clients with desired service
requirements.

Fig. 4.1: Proposed SARENA architecture.

  2. 2.

Infrastructure Layer (IL). This layer consists of a group of CDN servers
(either OTT servers or purchased services from CDN providers) denoted by  4;
each CDN contains various parts of video sequences. Like the EL layer, CDN
servers periodically inform the SDN controller about their cache occupancy
through CDN stat messages. Moreover, an origin server (shown by  5) contains
all video segments in multiple representations is placed in this layer.
OpenFlow (OF) switches form an SDN-enabled backbone network.

  3. 3.

Core Layer (CL). An SDN controller is placed in this layer, as shown in Fig.
4.1, augmented with a Network/Service (N/S) Monitoring module to monitor the
EL and IL layers and collect the stat information about the network and MS
services. Operating in a time-slotted fashion, the N/S monitoring module feeds
a central decision-maker optimization module, called Requests Scheduler. This
module optimally serves different MS requests with diverse requirements
invoked by all edge servers. For this purpose, the requests scheduler module
must respond to the following crucial questions:

    1. (a)

Where is the optimal place (i.e., edge, CDN servers, or origin server) for
fetching the content quality level requested by each client, while efficiently
employing layers’ available resources and satisfying service requirements
(e.g., service deadlines)?

    2. (b)

How can we use the functions/services provided in the EL and IL layers to form
MS function chains (SFCs)?

    3. (c)

What is the optimal SFC for responding to the requested quality level with
specific service requirements?

To respond to these questions, the requests scheduler considers all possible
functions/services to make the following SFCs, then runs an optimization model
to determine the optimal node and optimal SFC, considering the service
requirements. We will elaborate on the optimization model in more detail in
Section 4.1.1.2. Possible SFC chains are:
SFC#1: Fetch the demanded quality level directly from the edge server (
1$\rightarrow$ 2).
SFC#2: Transcode the demanded quality level from a higher quality at the edge
( 1$\rightarrow$ 2$\rightarrow$ 3).
SFC#3: Fetch the requested quality level directly from the best CDN server
(i.e., in terms of the available bandwidth) ( 1$\rightarrow$ 4).
SFC#4: Fetch the requested quality from the origin server ( 1$\rightarrow$ 5).
SFC#5: Fetch a higher quality level from the best CDN server and transcode it
into the demanded one at the edge ( 1$\rightarrow$ 4$\rightarrow$ 3).

Notably, the SDN controller informs the VPF of edge servers about the optimal
SFC and location; accordingly, edge servers serve their clients’ requests from
the determined server based on their service requirements. Furthermore, the
SDN controller employs a QoE Analyzer module to periodically analyze each edge
server’s served MS requests. Indeed, it uses information provided by the N/S
monitoring and requests scheduler modules as inputs of a QoE model (see
Section 4.1.3), and if the calculated QoE value cannot meet the service
threshold, it triggers the Edge Configurator module to adjust the edge
configurations automatically. The auto-scaling feature utilized in the edge
configurator, recently popular in both academia Aslanpour et al. (2020) and
industry Amazon (2020a), assists the edge servers in providing assured service
for streaming applications requiring varying amounts of computing resources in
response to dynamic client behavior over time.

Table 4.1: SARENA Notation. Input Parameters |  |  |  |
---|---|---|---|---
| $\mathcal{E}$
---
$\mathcal{S}$
$\mathcal{C}$
$\mathcal{R}$
$\mathcal{R}_{e}$
$\mathcal{Q}^{r}$
$\mathcal{A}^{q,r}_{i}$
$\delta^{q,r}$
$\sigma^{q,r}$
$\eta^{q,r}$
$\mu^{q,r}$
$\pi_{e}$
$\omega_{i,e}$
$\theta^{r}$
| Set of $n$ edge servers
---
Set of $k$ cloud servers, including CDNs and an origin (i.e., $s=0$)
Set of SFC chains, where $c=\\{1,2,3,4,5\\}$
Set of $x$ various MS requests received by the SDN controller from
$\mathcal{E}$
Set of various MS requests issued by edge server $e\in\mathcal{E}$
Set of possible quality levels for serving quality $q^{*}$ issued by
$r\in\mathcal{R}$,
where $\mathcal{Q}^{r}=\\{q^{*},q^{*}+1,...,q^{*}_{max}\\}$ and $q^{*}_{max}$
is the maximum quality
level for the requested segment
Available quality levels in edge VCF (i.e., $i\in\mathcal{E}$) or cloud
servers
(i.e., $i\in\mathcal{S}$) to serve $r\in\mathcal{R}$; $\alpha^{q,r}_{i}=1$
means $i$ hosts quality $q$ to serve
$r\in\mathcal{R}$, otherwise $\alpha^{q,r}_{i}=0$
Segment size in quality $q$ requested by $r\in\mathcal{R}$
Required resources (i.e., CPU time in seconds) for transcoding quality
$q\in\mathcal{Q}^{r}$ requested by $r\in\mathcal{R}$
Bitrate associated to quality level $q\in\mathcal{Q}^{r}$ requested by
$r\in\mathcal{R}$
Required time for transcoding quality $q\in\mathcal{Q}^{r}$ into the quality
$q^{*}$
requested by $r\in\mathcal{R}$
Available computational resource (available CPU) of VTF in $e\in\mathcal{E}$
Available bandwidth on path between $i\in\mathcal{S}$ and $e\in\mathcal{E}$
Given deadline for delivering request $r\in\mathcal{R}$ based on its MS type
|  |  |
Variables |  |  |  |
| $D^{q,r}_{i,e,c}$
---
$\mathcal{P}^{q,r}_{e}$
$\mathcal{T}^{q,r}_{i,e}$
$\chi$
| Binary variable where $D^{q,r}_{i,e,c}=1$ indicates edge $i=e$ or
$i\in\mathcal{S}$
---
serves request $r$ with quality level $q\in\mathcal{Q}^{r}$ via SFC chain
$c\in\mathcal{C}$,
otherwise $D^{q,r}_{i,e,c}=0$
Required transcoding time at VTF in $e\in\mathcal{E}$ for serving
$r\in\mathcal{R}$ with
quality level $q\in\mathcal{Q}^{r}$
Required time for transmitting quality $q\in\mathcal{Q}^{r}$ in response to
request
$r\in\mathcal{R}$ issued by $e\in\mathcal{E}$ from $i\in\mathcal{S}$ and
$c\in\\{3,4,5\\}$
Total serving latency consisting of $\mathcal{P}^{q,r}_{e}$ and
$\mathcal{T}^{q,r}_{i,e}$ for all MS services
|  |  |

#####  4.1.1.2 SARENA Optimization Problem Formulation

We introduce an MILP optimization model consisting of four constraint groups:
Chain Selection, Latency Calculation, Service/Policy, and Resource Utilization
constraints. Table 4.1 summarizes the notations used in this work.

(i) Chain Selection constraint. Let us define the binary decision-making
variables $\mathcal{D}^{q,r}_{i,e,c}$ where $D^{q,r}_{i,e,c}=1$ shows edge
$i=e$ or $i\in\mathcal{S}$ serves request $r$ with quality level
$q\in\mathcal{Q}^{r}$ via SFC chain $c\in\mathcal{C}$, otherwise
$D^{q,r}_{i,e,c}=0$. Therefore, Eq. (4.1) chooses the best SFC chain for each
request $r$ issued by edge server $e\in\mathcal{E}$ by setting the
$D^{q,r}_{i,e,c}$ to assure that each request is not parallelized, i.e., split
over multiple chains:

$\displaystyle\sum_{i\in\mathcal{S}\cup{e}}\sum_{c\in\mathcal{C}}\sum_{q\in\mathcal{Q}^{r}}\mathcal{D}^{q,r}_{i,e,c}~{}.~{}\alpha^{q,r}_{i}=1,$
$\displaystyle\forall e\in\mathcal{E},r\in\mathcal{R}_{e}$ (4.1)

(ii) Latency Calculation constraints. Eq. (4.2) measures the transmission time
$\mathcal{T}^{q,r}_{i,e}$, if cloud server $i$ in one of the SFC#3, SFC#4, or
SFC#5 is selected to transmit quality level $q\in\mathcal{Q}^{r}$ to edge
server $e$:

$\displaystyle\sum_{c\in\mathcal{C}}\mathcal{D}^{q,r}_{i,e,c}~{}.~{}\delta^{q,r}\leq\mathcal{T}^{q,r}_{i,e}~{}.~{}\omega_{i,e},$
$\displaystyle\forall r\in\mathcal{R}_{e},q\in\mathcal{Q}^{r},i\neq e$ (4.2)

Furthermore, Eq. (4.3) determines the required transcoding time
$\mathcal{P}^{q,r}_{e}$ at edge $e$ in case of serving the quality demanded by
$r$ from a higher quality $q$ in SFC#2 or SFC#5:

$\displaystyle\sum_{c\in\mathcal{C}\setminus{\\{1,3,4}\\}}\sum_{q\in\mathcal{Q}^{r}}\mathcal{D}^{q,r}_{i,e,c}~{}.~{}\mu^{q,r}\leq\mathcal{P}^{q,r}_{e},$
$\displaystyle\forall e\in\mathcal{E},i\in\mathcal{S}\cup
e,r\in\mathcal{R}_{e}$ (4.3)

(iii) Service/Policy constraints. The first constraint (Eq. (4.4)) of this
group guarantees that the total request’s serving latency for preparing the
requested quality $q$ of request $r$ must respect the request service deadline
(denoted by $\theta^{r}$):

$\displaystyle{\sum_{i\in\mathcal{S}\cup
e}\sum_{q\in\mathcal{Q}^{r}}{\mathcal{T}^{q,r}_{i,e}+\mathcal{P}^{q,r}_{e}}}\leq\theta^{r},$
$\displaystyle\forall e\in\mathcal{E},r\in\mathcal{R}_{e}$ (4.4)

The total services’ serving latency, namely $\chi$, i.e., fetching time plus
transcoding time, for all requests can be expressed as the following
constraints (Eq. (4.5)):

$\displaystyle\sum_{r\in\mathcal{R}}\sum_{i\in\mathcal{S}\cup
e}\sum_{e\in\mathcal{E}}\sum_{q\in\mathcal{Q}^{r}}\mathcal{T}^{q,r}_{i,e}+\mathcal{P}^{q,r}_{e}\leq\chi$
(4.5)

Moreover, Eq. (4.6) sets the IL policy by forcing the model to fetch the exact
quality $q^{*}$ from the origin server when the origin server (i.e., $s=0$) is
selected to serve $r$.

$\displaystyle\sum_{q\in\mathcal{Q}^{r}}\mathcal{D}^{q,r}_{i=0,e,c=4}~{}.~{}q=q^{*},$
$\displaystyle\forall e\in\mathcal{E},r\in\mathcal{R}_{e}$ (4.6)

(iv) Resource Utilization constraints. Eq. (4.7) ensures that the required
bandwidth for transmitting quality $q$ on the link between cloud server $i$
and edge $e$ must respect the available bandwidth (denoted by $\omega_{i,e}$):

$\displaystyle\sum_{r\in\mathcal{R}_{e}}\sum_{c\in\mathcal{C}}\sum_{q\in\mathcal{Q}^{r}}\mathcal{D}^{q,r}_{i,e,c}~{}.~{}\eta^{q,r}\leq\omega_{i,e},$
$\displaystyle\forall e\in\mathcal{E},i\in\mathcal{S},i\neq e$ (4.7)

Furthermore, Eq. (4.8) restricts the maximum required processing capacity for
transcoding to the available computational resource on each edge server $e$
(denoted by $\pi_{e}$):

$\displaystyle\sum_{r\in\mathcal{R}_{e}}\sum_{i\in\mathcal{S}\cup
e}\sum_{c\in\mathcal{C}\setminus{\\{1,3,4}\\}}\sum_{q\in\mathcal{Q}^{r}}D^{q,r}_{i,e,c}~{}.~{}\sigma^{q,r}\leq\pi_{e}$
$\displaystyle\forall e\in\mathcal{E}$ (4.8)

Central Scheduling Optimization Model. An ABR algorithm embedded in a HAS
player assesses the network’s bandwidth by measuring the time between sending
the request to download a segment and receiving the segment’s last packet.
Thus, minimizing the serving latency in the optimization model directly
impacts the HAS clients’ performance. To this end, the model for minimizing
total requests’ serving latency, denoted by $\chi$, can be expressed as
follows:

Minimize $\displaystyle\hskip 8.5359pt\chi$ (4.9) $\displaystyle s.t.$
$\displaystyle\hskip 14.22636pt\text{constraints}\hskip
14.22636pt\text{Eq.}(\ref{SARENA:eq:1})-\text{Eq.}(\ref{SARENA:eq:8})$
$\displaystyle vars.$ $\displaystyle\hskip
14.22636pt\mathcal{T}^{q,r}_{i,e},\mathcal{P}^{q,r}_{e},\chi\geq
0,D^{q,r}_{i,e,c}\in\\{0,1\\}$

By running the MILP model (Eq. (4.9)), an optimal chain will be selected for
each request to minimize the total serving time. However, since the MILP model
is NP-hard Garey and Johnson (1983), it suffers from high time complexity and
is impractical for large-scale scenarios. Thus, we introduce a lightweight
heuristic solution in the next section to cope with the aforementioned
problems.

####  4.1.2 SARENA Lightweight Heuristic Algorithms

This section proposes two simple lightweight algorithms distributed on the SDN
controller and edge servers. Our solution aims at satisfying the constraints
(4.1)–(4.8) by reducing the responsibilities of the SDN controller in terms of
MS requests’ scheduling and introducing a new VNF called Virtual Scheduler
Function (VSF) deployed at the edge. The VSF function utilizes constraints
(4.1)–(4.8) in the form of a lightweight heuristic algorithm to produce a
nearly-optimal solution for its local edge server instead of running a central
complex optimization model for all edge servers. Although we split the central
MILP model (4.9) into edge VSFs, the SDN controller, as a coordinator node,
still collects stats information from the layers (i.e., by N/S monitoring),
advertises this information to edge servers, and analyzes served requests’ QoE
(i.e., by the QoE analyzer) and reconfigures edge servers if their associated
MS services cannot meet the defined service thresholds (i.e., by the edge
configurator).

Like the centralized model, the VSF-based solution works in a time-slotted
manner. A time slot consists of two intervals: (i) Stats/Requests Collector
(SRC) interval and (ii) Requests Scheduler (RES) interval. In the SRC
interval, an edge server simultaneously receives stats information and MS
requests provided by the SDN controller and the VPF function, respectively.
Considering the provided data, the VSF function in the RES interval runs Alg.
1 to serve MS requests by choosing suitable SFCs, i.e., SFC#1:  2, SFC#2:
2$\rightarrow$ 3, SFC#3:  4, SFC#4:  5, or SFC#5:  4$\rightarrow$ 3, and
minimizes the total serving latency w.r.t. the service requirements and
objective function of Eq. (4.9). We present the proposed algorithms separately
in Alg. 1 and Alg. 2, which are deployed on the edge servers and the SDN
controller, respectively.

#####  4.1.2.1 Edge-based Scheduling Heuristic Algorithm

As shown in Alg. 1, each edge server receives data provided by the SDN
controller, i.e., $stat\\_info$ and information on bandwidth to CDN/origin
servers (i.e., $BW\\_info$) in the SRC interval. The edge server calls the
ExtractFeatures function to extract some essential features of input requests,
e.g., MS types, requested video sequences/channels, requested qualities,
request receiving time, and service deadlines (line 2). After that, based on
the extracted features stored in the $features$ list, the MakeQueues function
is utilized to form different queues of requests (line 3). For instance, two
popular MS applications, i.e., VoD and live requests, are placed in separate
queues based on MS type, requested live channel/VoD video IDs, and bitrate
levels. Considering the system’s current state, i.e., available information on
resources (i.e., $stat\\_info$) and queues of MS requests, the edge server in
the RES interval must run multiple threads of a VSF function (one thread per
MS type) to answer the questions mentioned in Section 4.1.1.1.

Algorithm 1 SARENA edge server heuristic algorithm.

1:Input $requests$, $stat\\_info$, $BW\\_info$, $on\\_the\\_fly$

2:$features\leftarrow$ ExtractFeatures($requests$)

3:$MS\\_queues\leftarrow$ MakeQueues($requests,features$)

4:*//Each $MS_{m}$ Thread: VSF()

5:sort($MS\\_queue_{m},features_{m}$)

6:for each $req$ in $MS\\_queues_{m}$ do

7: if req $\in$ $on\\_the\\_fly$ then

8: HoldReq($req$)

9: else

10: $on\\_the\\_fly$.add($req$)

11: $SFC\\_set\leftarrow$SFCDetector()

12: $SFC\\_cost\leftarrow\text{CostFunction($SFC\\_set$)}$

13: $opt\\_SFC\leftarrow$OptimalSFC($SFC\\_set$,$SFC\\_cost$)

14: ServeRequest($req$,$opt\\_SFC$)

15: UpdateVariables$()$

16: end if

17:end for

At the start of each VSF thread, associated MS queues are sorted based on the
extracted information, like service deadline using the sort function (line 5).
Next, each MS request ($req$) is compared to $on\\_the\\_fly$ requests (i.e.,
requests currently being served). If $req$ is in the $on\\_the\\_fly$ list,
then it calls HoldReq to hold the request and prevent network resource wastage
and congestion (lines 7–8). Otherwise, the $on\\_the\\_fly$ list is updated by
the $req$ to be processed (line 10). In the next step, the SFCDetector
function determines all feasible SFCs (i.e., SFC#1–SFC#5) and stores them in
the $SFC\\_set$ list (line 11).

Considering the objective function (4.9) and defined constraints (4.1)–(4.8),
the serving latencies of the SFCs contained in $SFC\\_set$ are calculated by
calling the CostFunction function and then the results are saved in
$SFC\\_cost$ (line 12). Next, the OptimalSFC function calculates the minimum
value (i.e., serving latency) in the $SFC\\_cost$ structure, retrieves its
associated SFC from $SFC\\_set$, and saves it as the optimal SFC (line 13).
Finally, the ServeRequest and UpdateVariables functions are utilized to serve
the clients’ request with the optimal SFC and to upgrade stat information and
the $on\\_the\\_fly$ list, respectively (lines 14–15). Note that since more
than one queue can proceed and might violate all/several resource constraints
(e.g., the bandwidth and/or computational limits), they are evaluated in a
priority order where the queue with more requests and earlier service
deadlines comes first. This process will be repeated in each RES interval
until the MS session ends and all queues are served. Assume $\beta_{1}$,
$\beta_{2}$, and $\beta_{3}$ indicate the number of MS services, number of
channels/video sequences, and number of bitrates per channel/video. In the
worst case, the time complexity of the multi-threaded Alg. 1 employed by each
edge server would be $O(\beta_{1}~{}.~{}\beta_{2}~{}.~{}\beta_{3})$ in each
time slot.

Algorithm 2 SARENA SDN controller heuristic algorithm.

1:while $True$ do

2: $stat\\_info,BW\\_info\leftarrow$ N/S-Monitoring()

3: for each $e$ in $\mathcal{E}$ do

4: $MS\\_QoE\\_e\leftarrow QoEAnalyzer(e)$

5: if $MS\\_QoE\\_e<MS\\_QoE\\_{th}$ then

6: EdgeConfigurator($e$)

7: end if

8: end for

9: Update($\mathcal{E}$)

10: Wait ($\tau$)

11:end while

#####  4.1.2.2 SDN-based Management Heuristic Algorithm

In Alg. 2, the SDN controller uses the N/S-Monitoring function to collect the
stats and bandwidth information from the network and servers, plus average QoE
parameters for the served requests in the previous time slot (line 2). Based
on the collected data, the QoE_Analyzer function is called to calculate the MS
QoE scores for each edge server and store values in each edge $MS\\_QoE\\_e$
list (line 4) (see Section 4.1.3 for the used MS QoE model). Next, if the
calculated values violate the service QoE thresholds (denoted by
$MS\\_QoE\\_{th}$), which is adjusted by the network or video operator based
on their business plans and services, the EdgeConfigurator function is called
to reconfigure the edge server (lines 5–6) and then updates all edge servers
(line 9). We note that any policy on QoE analyzing and auto-scaling can be
applied. This explained procedure will repeat periodically after $\tau$
seconds, where $\tau$ is the duration of the SRC interval within the while
loop (line 10). The overall time complexity of Alg. 2 can be given as $O(n)$,
where $n$ is the number of edge servers.

####  4.1.3 SARENA Performance Evaluation

In this section, we first describe SARENA’s evaluation setup, metrics, and
methods and then compare SARENA’s performance against baseline solutions in
various experiments.

#####  4.1.3.1 Evaluation Setup

To evaluate the performance of SARENA in a realistic large-scale environment,
we instantiate our testbed on the CloudLab Ricci et al. (2014) and use
InternetMCI Zoo (2020) as a real backbone network topology. Our testbed
includes 280 components, i.e., (i) 250 AStream AStream (2020); Juluri et al.
(2015) DASH players running the BOLA Spiteri et al. (2016) ABR algorithm in
headless modes (five groups of 50 peers); (ii) five Apache HTTP servers (i.e.,
four CDN servers with a total cache size of 40% of the MS video datasets and
an origin server, holding all MS video sequences); (iii) 19 OpenFlow (OF)
backbone switches and 45 backbone layer-2 links; (iv) five edge servers, each
of which is responsible for one group of clients and includes a partial cache
size of only 5% of the MS video sequences; and a FloodLight SDN controller.
Note that each element is run on Ubuntu 18.04 LTS inside Xen virtual machines
within separated Linux namespaces.

To emulate the auto-scaling feature, a basic configuration (i.e., 4 CPU cores
and 6 GB RAM) of virtual machines supporting a maximum of 10 CPU cores and 16
GB RAM is assigned to all edge servers at the beginning of all experiments.
Next, the edge servers’ configurations scale up edge configurations by adding
2 CPU cores and 2 GB RAM whenever the SDN edge configurator module is
triggered. Although SARENA is independent of the caching policy, for the sake
of simplicity, Least Recently Used (LRU) cache replacement policy is
considered in all CDNs and VCFs. Note that the most popular MS VoD video
sequences are pre-cached on the VCFs to avoid a slow startup of the system.
Python 3.7 is used to implement all modules of the SDN controller and the
VNFs. Moreover, the Python PuLP library with the CPLEX solver and Dockerimage
jrottenberg/ffmpeg FFmpeg (2020) are employed to implement the MILP model and
VTSs, respectively.

We evaluate the performance of SARENA through two prevalent MS services, i.e.,
VoD and live streaming applications. ($MS\\_{QoE}\\_{th}$, $\theta_{r}$)
values associated with live and VoD services are set to (4, 2 s) and (3.5, 4
s), respectively, to make different service requirements. We consider five
live channels, where each of which plays a unique video Lederer et al. (2012)
with 300 s duration, comprising two-second segments of the following bitrate
ladder {(0.089,320p), (0.262,480p), (0.791,720p), (2.4,1080p), (4.2,1080p)}
[Mbps, resolution]. Moreover, 20 video sequences Lederer et al. (2012) with
300 seconds duration and four-second segments in seven representations
{(0.128,320p), (0.320,480p), (0.780,720p), (1.4,720p), (2.4,1080p),
(3.3,1080), (3.9,1080)} are employed for the VoD services. For simplicity, we
assume each client requests only one MS type during its streaming session.

The live channel and VoD video access probability are generated following a
Zipf distribution with the skew parameter $\alpha=0.75$. The probability of an
incoming request for the $i^{th}$ most popular live channel or VoD video are
given as $prob(i)=\frac{1/i^{\alpha}}{\sum_{j=1}^{K}1/j^{\alpha}}$, where
$K=5$ and $K=20$ for the live and VoD services, respectively. In the
literature, the bandwidth value from the CDN servers to an edge server is
assumed to be higher than from the origin server to an edge server. Al-Abbasi
et al. (2019). Therefore, the Linux Wondershaper tool is employed to set 50
and 100 Mbps as a bottleneck bandwidth in different paths from the CDN and
origin servers to edge servers, respectively. In addition, we use a real 4G
network trace Raca et al. (2018) (average bandwidth 3780 kbps and standard
deviation 3190 kbps) collected on bus rides for links between clients to edge
servers in all experiments. The SDN QoE analyzer module uses the ITU-T Rec.
P.1203 model in mode 0 P.1203 (2020), as a standard comprehensive QoE model.
The computational and bandwidth costs are set to $0.029\$$ per CPU per hour
and $0.12\$$ per GB, respectively Amazon (2020b).

#####  4.1.3.2 Evaluated Methods and Metrics

Since there are no SFC-enabled frameworks supporting various HAS applications
in the literature, we compare the results obtained by SARENA with the
following baseline methods:

  1. 1.

CDN-assisted (CDA): this is a regular CDN-based streaming method.

  2. 2.

Non VNF-assisted (NVA): edge devices without VCF and VTF functions are used to
find the best CDN server with maximum available bandwidth.

  3. 3.

Non VTF-enabled (NTE): edge servers are equipped with the VCFs, but do not
support VTFs.

  4. 4.

Non Reconfiguration-enabled (NRE): this approach employs a simple version of
SARENA without the SDN edge configurator module.

For fair comparisons, the results of all systems are derived with respect to
the same settings and the same topology in our testbed. Moreover, each
experiment is run 20 times, and the average and standard deviation values are
reported in the experimental results. We use the following evaluation metrics
to compare SARENA results with the above-mentioned methods:

  1. 1.

Average Segment Bitrate (ASB) of all the downloaded segments.

  2. 2.

Average Number of Quality Switches (AQS), the average number of segments whose
bitrate level changed compared to the previous one.

  3. 3.

Average Stall Duration (ASD), the average of total video freeze time of all
clients.

  4. 4.

Average Number of Stalls (ANS), the average number of rebuffering events.

  5. 5.

Average Perceived Overall QoE (APQ) calculated by the ITU-T Rec. P.1203 model
in mode 0 P.1203 (2020).

  6. 6.

Average Serving Latency (ASL), defined as the overall time for serving all
clients, including fetching latency plus transcoding latency.

  7. 7.

Backhaul Traffic Load (BTL), the volume of segments downloaded from the origin
server.

  8. 8.

Edge Transcoding Ratio (ETR), the fraction of segments reconstructed by the
VTFs.

  9. 9.

Network Cost Value (NCV), consisting of computational and bandwidth costs.

Note that the arrows in each metric plot (Figs. 4.2 (a)–(f) and 4.3 (a)–(c))
indicate which direction (up or down) represents a better result. We use the
following method to calculate the results reported in the next section to show
whether SARENA outperforms a specific baseline method in terms of the
aforementioned metrics:
$\%~{}increase~{}or~{}\%~{}decrease=(\frac{SARENA\\_obtained\\_metric~{}-~{}Baseline\\_obtained\\_metric}{Baseline\\_obtained\\_metric})\times
100$

#####  4.1.3.3 Evaluation Results

In the first scenario, we conduct experiments to assess SARENA’s performance
in terms of the QoE metrics and compare the results with described baseline
systems. As plotted in Fig. 4.2(a–d), SARENA downloads VoD and live streaming
segments with higher ASBs, improves AQSs and ANSs, and shortens ASDs in both
VoD and live streaming applications. Although enhancing the aforementioned
common QoE parameters can generally improve the users’ satisfaction, the
standard comprehensive QoE model is utlized by the APQ metric to evaluate
overall users’ QoE. Note that stalling events (measured by ASD and ANS)
seriously impact APQ compared to other parameters. Utilizing the VCFs and VTFs
in SFCs enables the SARENA system to download MS segments with improved QoE
metrics, especially ASD, and leads to achieving better APQ by at least 53% and
39.6% for VoD and live streaming, respectively, compared to the baseline
approaches (Fig. 4.2(e)). Moreover, as illustrated in Fig. 4.2(f), the average
serving latency values (ASL) obtained by SARENA in VoD and live applications
are reduced by at least 32.5% and 29.3% compared to other methods. This is
because SARENA (i) uses latency- and QoE-sensitive policies to meet
$\theta_{r}$ and $MS\\_{QoE}\\_{th}$ values, (ii) utilizes all layers of
possible resources employed in SFCs, and (iii) operates an auto-scaling policy
provided by the SDN controller, for serving MS requests.

Fig. 4.2: QoE results for the CDA, NVA, NTE, NRE, and SARENA systems for 250
clients. Fig. 4.3: Network utilization results for the CDA, NVA, NTE, NRE, and
SARENA systems for 250 clients.

The second scenario studies the effectiveness of SARENA in terms of network
utilization (i.e., BTL and ETR) and network cost metrics (i.e., NCV). Since
SARENA (i) fetches requested or higher MS quality levels from the VCF or CDN
servers and (ii) transcodes requested MS quality levels by VTF, it downloads
fewer segments from the origin server, consequently outperforms the CDA, NVA,
and NTE systems in terms of BTL (Fig. 4.3(a)). Moreover, the auto-scaling
capability provided by the SDN controller assists SARENA in yielding a better
BTL (40% and 30% for VoD and live applications, respectively) compared to the
NRE system. Moreover, the ETR metric indicates that the auto-scaling feature
allows SARENA to operate more computational resources of the edge servers to
transcode MS applications, especially for serving live streaming requests, as
latency-sensitive demands (Fig. 4.3(b)). Note that the ETR metrics for not
transcoding-enabled systems, i.e., CDA, NVA, and NTE, are zero. Although the
SARENA uses more edge computational resources, our final experiment (Fig
4.3(c)) demonstrates that its NCV metric is still lower than for CDA and
(almost) identical to the NRE system. This is because SARENA improves the
costly BTL metric.

###  4.2 Summary

In this chapter, we introduced an SFC-enabled architecture for various
adaptive video streaming applications, named SARENA. We virtualized several
multimedia functions as VNFs, designed chains of VNFs, and utilized all
possible CDN and edge servers’ resources for serving different multimedia
service requests, e.g., VoD and live video streaming, in an SDN-enabled
network. We formulated the problem as a central MILP optimization model to
provide a scheduling policy for various multimedia services. SARENA’s edge
servers were augmented with lightweight scheduling functions to improve the
scalability and alleviate time complexity problems of the MILP model and make
it deployable in practical environments. We also utilized the SDN controller’s
capability to scale edge server resources based on service requirements
dynamically. The performance evaluation of SARENA over a large-scale cloud-
based testbed, including 250 HAS clients, confirmed that SARENA outperformed
baseline systems in terms of users’ QoE (by at least 39.6%), latency (by at
least 29.3%), and network utilization (by at least 30%) for both live and VoD
services.

##  Chapter 5 Collaborative Edge-Assisted Frameworks for HAS

Multi-Access Edge Computing (MEC) is considered one of the leading networking
paradigms for designing NAVS systems by providing video processing and caching
close to the end users. Despite the wide usage of this technology, designing
NAVS architectures for HAS-based clients that support low-latency and high-
quality video streaming, including edge collaboration, is still a challenge.
To address these issues, this chapter leverages the SDN, NFV, and MEC
paradigms to propose two collaborative edge-assisted systems, named LEADER and
ARARAT (LEADER’s extension), that work for live and VoD applications. Aiming
at minimizing HAS clients’ serving time and delivery cost (in the ARARAT
framework), besides considering available resources and all possible serving
actions, we design multi-layer architectures and formulate the problems as a
centralized optimization model executed by the SDN controller. However, to
cope with the high time complexity of the centralized models, we introduce
heuristic approaches that produce lightweight solutions through efficient
collaboration between the SDN controller and edge servers. The proposed
heuristics are equipped with fair bandwidth allocation strategies to provide
sufficient bandwidth for each edge server based on its requirements. Finally,
we implement the LEADER and ARARAT frameworks, conduct our experiments on a
large-scale cloud-based testbed including 250 HAS players, and compare their
effectiveness with state-of-the-art systems within comprehensive scenarios.
The experimental results illustrate that the proposed solutions improve users’
QoE, decrease the streaming cost, and enhance network utilization compared to
their competitors. Moreover, the ARARAT results indicate that network fairness
provided by the bandwidth allocation strategy indirectly improves users’ QoE
fairness.
The first contribution of this chapter, i.e., “LEADER: A Collaborative Edge-
and SDN-Assisted Framework for HTTP Adaptive Video Streaming” was presented at
the IEEE International Conference on Communications (ICC) 2022 Farahani et al.
(2022d) and the second one, i.e., “ARARAT: A Collaborative Edge-Assisted
Framework for HTTP Adaptive Video Streaming” was published in the IEEE
Transactions on Network and Service Management (TNSM) journal Farahani et al.
(2022c).

###  5.1 LEADER Framework

This section presents LEADER Farahani et al. (2022d), a collaborative edge-
and SDN-assisted framework for HTTP adaptive video streaming. The details of
the LEADER architecture, action tree, and optimization MILP model are
explained in Section 5.1.1. A distributed heuristic approach is introduced in
Section 5.1.2 to solve the proposed optimization model. The LEADER evaluation
setup, methods, metrics, and results are presented in Section 5.1.3.

####  5.1.1 LEADER System Design

This section explains the LEADER architecture and then formulates the problem
as an MILP optimization model.

#####  5.1.1.1 LEADER Architecture

The proposed hierarchical architecture of LEADER, which includes three layers,
is illustrated in Fig. 5.1. These layers are:

  1. 1.

Edge Layer. Edge servers close to base stations (gNodeB) are located in this
layer. On behalf of clients, each edge server periodically communicates with
the SDN controller, sends the status of its available resources, e.g., CPU and
RAM (in so-called comp map messages), and its cache occupancy (in edge map
messages) to the SDN controller, and responds to the clients. In our design,
edge servers are categorized into Local Edge Servers (LES) and Neighbor Edge
Servers (NES). LESs serve their clients’ requests directly, while NESs can
collaborate with LESs for transcoding and caching during cache miss situations
or lack of processing resources.

Fig. 5.1: LEADER architecture.

Each edge server includes the following components: (i) Transcoding Module
(Tran.), which is responsible for transcoding segments’ higher quality levels
to the demanded quality levels; (ii) Partial Cache (PC), which is utilized to
store a limited number of segments.

  2. 2.

CDN Layer. The CDN Layer is constructed by multiple CDN servers (CS) where
each of them contains various parts of video sequences and periodically
informs the SDN controller about its cache occupancy through cache map
messages.

  3. 3.

Backbone Layer. An origin server that contains all video segments in multiple
representations and an SDN controller are placed in this layer. The SDN
controller consists of the following modules:

    1. (a)

Bandwidth Monitoring Module (BMM): It monitors the available bandwidth of
different paths between each LES and other servers, i.e., NESs, CSs, or the
origin server. The output of the BMM will be stored in a repository called
bandwidth map.

    2. (b)

Path Selection Module (PSM): It selects the best path with maximum available
bandwidth between each LES and NESs, CSs, or the origin server.

    3. (c)

Central Optimization Module (COM): COM runs an MILP optimization model to
respond to the following key questions:

      1. i.

Where is the optimal place (i.e., LES, NESs, CSs, or the origin server) in
terms of the minimum serving time for fetching each client’s requested content
quality level from?

      2. ii.

What is the optimal approach for answering to the requested quality level,
i.e., fetch or transcode?

      3. iii.

What is the optimal action to reach the requested quality?

Fig. 5.2: LEADER action tree.

To do that, COM utilizes the received items, i.e., cache map, edge map, comp
map, and bandwidth map and finds an optimal solution (i.e., in terms of lowest
serving time) from the Action Tree (Fig. 5.2):

  1. 1

Fetch the requested quality level directly from the LES (action $1$ in the
action tree).

  2. 2

Transcode the requested quality from a higher quality at the LES.

  3. 3

Fetch a higher quality from the best adjacent NES and transcode it at the LES.

  4. 4

Fetch the requested quality directly from the best NES server.

  5. 5

Transcode the requested quality from a higher quality at the best NES and then
transmit it from the NES to the LES.

  6. 6

Fetch the requested quality from the origin server.

  7. 7

Fetch a higher quality from the best CDN server and transcode it at the LES.

  8. 8

Fetch the requested quality from the best CDN server.

Finally, the SDN controller informs edge servers about optimal actions;
consequently, they can serve their clients’ requests from the determined
server in minimum serving time.

Table 5.1: LEADER Notation. Input Parameters |  |  |  |
---|---|---|---|---
| $\mathcal{C}$
---
$\mathcal{V}$
$\mathcal{R}$
$R_{i}$
$\mathcal{Q}^{r}$
$\mathcal{T}$
$\alpha^{p,r}_{i}$
$\omega_{i,j}$
$\delta^{r}_{p}$
$\pi^{r}_{p}$
$\Omega_{i}$
$\mu^{r}_{p}$
$\eta_{p}$
| Set of $k$ CDN servers and an origin server (i.e., $c=0$)
---
Set of $n$ edge servers
Set of $m$ requests received by the SDN controller from $\mathcal{V}$
Set of requests issued by edge server $i\in\mathcal{V}$
Set of possible quality levels for serving quality $p^{*}$ requested by
$r\in\mathcal{R}$, where $\mathcal{Q}^{r}=\\{p^{*},p^{*}+1,...,p^{*}_{max}\\}$
and $p^{*}_{max}$ is the maximum
quality level for the requested segment
Set of possible transcoding statuses: $\mathcal{T}=\\{0,1,2\\}$; $t$ is 1 or 2
if
the requested quality is transcoded from a higher quality
$p\in\mathcal{Q}^{r}$
at the NES or at the LES, respectively; otherwise t=0
Available quality levels in server $i\in\mathcal{V}\cup\mathcal{C}$;
$\alpha^{p,r}_{i}=1$ means server
$i$ hosts quality $p$ to serve $r\in\mathcal{R}$, otherwise
$\alpha^{p,r}_{i}=0$
Available bandwidth on path between $i\in\mathcal{V}$ and
$j\in\\{\mathcal{V}\cup\mathcal{C}\\}\setminus i$
Size of segment in quality $p$ requested by $r\in\mathcal{R}$ [bytes]
Computational cost (CPU usage in %) for transcoding quality
$p\in\mathcal{Q}^{r}$
into the quality requested by $r\in\mathcal{R}$
Available processing capacity (available CPU in %) of $i\in\mathcal{V}$
Required time for transcoding quality $p\in\mathcal{Q}^{r}$ into the quality
requested by $r\in\mathcal{R}$
Bitrate associated to quality level $p\in\mathcal{Q}^{r}$
|  |  |
Variables |  |  |  |
| $B^{p,r,t}_{i,j}$
---
$\tau^{r}_{i}$
$T^{p,r}_{i,j}$
$\Gamma^{p,r}_{i,j}$
| Binary variable where $B^{p,r,t}_{i,j}=1$ shows server
$i\in\mathcal{V}\cup\mathcal{C}$ transmits
---
quality $p\in\mathcal{Q}^{r}$ to server $j\in\mathcal{V}$ for request $r$ with
transcoding status $t$,
otherwise $B^{p,r,t}_{i,j}=0$
Required transcoding time at server $i\in\mathcal{V}$ for serving
$r\in\mathcal{R}$
Required time of transmitting quality level $p\in\mathcal{Q}^{r}$ in response
to
request $r\in\mathcal{R}$ from server $i\in\mathcal{V}\cup\mathcal{C}$ to
$j\in\mathcal{V}$
Serving time consisting of $\tau^{r}_{i}$ and $T^{p,r}_{i,j}$
|  |  |

#####  5.1.1.2 LEADER Optimization Problem Formulation

Let set $\mathcal{C}$ consist of $k$ CDN servers and an origin server, where
$c=0$ indicates the origin server. (See Table 5.1 for a summary of the
notation.) Moreover, let us define $\mathcal{R}$ as the set of $m$ requests
received by the SDN controller from the set $\mathcal{V}$ of $n$ edge servers.
The subset $R_{i}\subseteq\mathcal{R}$ shows all requests issued by edge
server $i\in\mathcal{V}$. Furthermore, we assume that the SDN controller
periodically receives the cache map and the edge map from cache and edge
servers, respectively; thus, let $\alpha^{p,r}_{i}$ denote the availability of
quality level $p$ of a segment demanded by request $r$ at cache/edge server
$i$. In LEADER, it is assumed that the SDN controller defines a data path
between two servers $i\in\mathcal{V}$ and
$j\in\\{\mathcal{C}\cup\mathcal{V}\\}\setminus i$ where $\omega_{i,j}$ shows
its available bandwidth accordingly. As mentioned earlier, when a LES requests
quality $p^{*}$, it is possible to receive the requested quality or a higher
one since all edge servers can run the transcoding function; therefore, for
each request $r$, we define
$\mathcal{Q}^{r}=\\{p^{*},p^{*}+1,...,p^{*}_{max}\\}$ as the set of possible
quality levels for serving requested quality $p^{*}$, where $p^{*}_{max}$ is
the maximum quality level for the requested segment. In the following, we
introduce an MILP model with four groups of constraints: Action Selection
(AS), Serving Time (ST), CDN/Origin (CO), and Resource Consumption (RC)
constraints.

(i) AS Constraint. The first constraint determines a suitable action from the
introduced action tree (Fig. 5.2) for each request $r$ issued by LES server
$j$. It selects appropriate values of the binary variable $B^{p,r,t}_{i,j}$
(see Table 5.1 for the definition):

$\displaystyle\sum_{i\in\mathcal{C}\cup\mathcal{V}}\sum_{t\in\mathcal{T}}\sum_{p\in\mathcal{Q}^{r}}B^{p,r,t}_{i,j}~{}.~{}\alpha^{p,r}_{i}=1,$
$\displaystyle\forall j\in\mathcal{V},r\in R_{j}$ (5.1)

(ii) ST Constraints. The first ST constraint determines the required time
(denoted by $T^{p,r}_{i,j}$) for transmitting quality level
$p\in\mathcal{Q}^{r}$ from each server $i\in\mathcal{V}\cup\mathcal{C}$ to
each LES $j\in\mathcal{V}$:

$\displaystyle\frac{\sum_{t\in\mathcal{T}}B^{p,r,t}_{i,j}~{}.~{}\delta^{r}_{p}}{\omega_{i,j}}\leq
T^{p,r}_{i,j},$ $\displaystyle\forall r\in R_{j},p\in\mathcal{Q}^{r},i\neq j$
(5.2)

The next constraint measures the required transcoding time $\tau_{i}^{r}$ at
server $i\in\mathcal{V}$ in case of serving the quality requested by $r\in R$
from a higher quality $p$ by means of transcoding:

$\displaystyle\sum_{j\in\mathcal{V}}\sum_{p\in\mathcal{Q}^{r}}B^{p,r,t=1}_{i,j}~{}.~{}\mu^{r}_{p}\leq\tau_{i}^{r}$
$\displaystyle\forall i\in\mathcal{V},r\in\mathcal{R}$ (5.3)

(iii) CO Constraints. This group of constraints forces the model to fetch the
exact quality $p^{*}$ from the origin server when the origin server is
selected to serve the LES:

$\displaystyle\sum_{t\in\mathcal{T}}\sum_{p\in\mathcal{Q}^{r}}B^{p,r,t}_{i=0,j}~{}.~{}p=p^{*},$
$\displaystyle\forall j\in\mathcal{V},r\in R_{j}$ (5.4)

Note that $i=0$ in Eq. (5.4) means that the origin server is serving requests.
We also should prevent CSs from performing transcoding functions, expressed by
the following equation:

$\displaystyle\sum_{i\in\mathcal{C}}\sum_{r\in
R_{j}}\sum_{p\in\mathcal{Q}^{r}}B^{p,r,t=1}_{i,j}~{}.~{}p=0$
$\displaystyle\forall j\in\mathcal{V}$ (5.5)

(iv) RC Constraints. The first constraint in this group guarantees that the
required bandwidth for transmitting segments on the link between two servers
$j\in\mathcal{V}$ and $i\in\mathcal{C}\cup\mathcal{V}$ should not exceed the
available bandwidth:

$\displaystyle\sum_{t\in\mathcal{T}}\sum_{r\in
R_{j}}\sum_{p\in\mathcal{Q}^{r}}B^{p,r,t}_{i,j}~{}.~{}\eta_{p}\leq\omega_{i,j}$
$\displaystyle\forall j\in\mathcal{V},i\in\mathcal{C}\cup\mathcal{V}$ (5.6)

Similarly, the next constraint limits the maximum required processing capacity
for the transcoding operation to the available computational resource.

$\displaystyle\sum_{r\in\mathcal{R}}\sum_{p\in\mathcal{Q}^{r}}(\sum_{i\in\mathcal{C}\cup\mathcal{V}}B^{p,r,t=2}_{i,j}+\sum_{i\in\mathcal{V}\setminus
j}B^{p,r,t=1}_{j,i})~{}.~{}\pi^{r}_{p}\leq\Omega_{j}$ $\displaystyle\forall
j\in\mathcal{V}$ (5.7)

Central MILP Optimization Model. The model minimizes the serving time (i.e.,
fetching time plus transcoding time), denoted by $\Gamma^{p,r}_{i,j}$, and can
be formulated as follows:

Minimize
$\displaystyle\sum_{r\in\mathcal{R}}\sum_{i\in\mathcal{V}\cup\mathcal{C}}\sum_{j\in\mathcal{V}}\sum_{p\in\mathcal{Q}^{r}}{\Gamma^{p,r}_{i,j}}$
(5.8) $\displaystyle s.t.$ $\displaystyle\text{constraints}\hskip
14.22636pt\text{Eq.}(\ref{LEADER:eq:1})-\text{Eq.}(\ref{LEADER:eq:7})$
$\displaystyle T^{p,r}_{i,j}+\tau^{r}_{i}=\Gamma^{p,r}_{i,j},\forall
r\in\mathcal{R},i\in\mathcal{V}\cup\mathcal{C},j\in\mathcal{V},p\in\mathcal{Q}^{r}$
$\displaystyle vars.~{}$ $\displaystyle
T^{p,r}_{i,j},\tau^{r}_{i},\Gamma^{p,r}_{i,j}\geq
0,B^{p,r,t}_{i,j}\in\\{0,1\\}$

By running the MILP model, the SDN controller should select an optimal action
for each request $r\in\mathcal{R}$ such that the total serving time is
minimized.

Preposition. Considering shared links in Eq. (5.8) changes the model to a
mixed integer non-linear programming (MINLP) model. The proposed model (5.8)
minimizes the total serving time assuming disjoint paths from edge servers in
$\mathcal{V}$ to other servers in $\mathcal{V}\cup\mathcal{C}$. Let
$\omega^{a,b}_{i,j}$ be an optimally allocated bandwidth between server $i$
and $j$ over the link $(a,b)$. Thus, the required time $T^{p,r}_{i,j}$ for
transmitting quality level $p\in\mathcal{Q}^{r}$ from server
$i\in\mathcal{V}\cup\mathcal{C}$ to each LES $j\in\mathcal{V}$ for each $r\in
R_{j},p\in\mathcal{Q}^{r}$ is obtained as follows:

$\displaystyle\frac{\sum_{t\in\mathcal{T}}B^{p,r,t}_{i,j}~{}.~{}\delta^{r}_{p}}{\bar{\omega}_{i,j}}\leq
T^{p,r}_{i,j},$ (5.9) $\displaystyle\text{where
}\bar{\omega}_{i,j}\leq\omega^{a,b}_{i,j}\hskip 42.67912pt\forall\text{ links
}(a,b),i\in\mathcal{V}\cup\mathcal{C},j\in\mathcal{V}$

Although we should also apply the change to constraint (5.6), replacing (5.2)
by (5.9) turns the proposed MILP model (5.8) into an MINLP model that is NP-
complete Lee and Leyffer (2011) and suffers from high time complexity. In the
following, we will propose a heuristic approach to remedy this time complexity
problem.

####  5.1.2 LEADER Distributed Heuristic Approach

Motivated by the characteristics of the objective function (5.8), we propose a
lightweight heuristic algorithm. Our method aims at satisfying the proposed
constraints (5.1)–(5.7) by considering shared links among servers in
$\mathcal{C}$ and $\mathcal{V}$. First, let us define the time slot structure
shown in Fig. 5.3(a) that consists of two intervals: (i) Edge Update (EU)
interval and (ii) Serving Requests (SR) interval. In the EU interval, the SDN
controller sends some important resource data from the network and servers
(i.e., bandwidth, cache, edge, and comp maps) to the edge servers in
$\mathcal{V}$; moreover, the SDN controller efficiently assigns appropriate
bandwidth to each edge server on shared links. Having the provided
information, edge servers in the SR interval serve their requests by selecting
appropriate actions that minimize serving time according to the objective
function in (5.8). Let us consider a simple topology shown in Fig. 5.3(b)
where five data paths from each edge server (LES and NES) to the neighboring
edge server, three cache servers (CS1, CS2, and CS3), and an origin server are
illustrated. The paths from LES and NES to other servers are depicted by the
blue and dashed red lines, respectively.

#####  5.1.2.1 SDN Controller Heuristic Algorithm

As shown in Fig. 5.3(b), LES uses the shared link connecting OpenFlow (OF)
switches S1 and S2 to reach CS2 and CS3, while NES utilizes it to fetch data
from CS1. Let us follow the proposed algorithm in Alg. 3. In an infinite loop,
the SDN controller first collects resource data from the network and servers
(line 2), it then determines one path from each edge server in $\mathcal{V}$
to each server in $\mathcal{C}$ (line 3). We note that any policy on selecting
the paths can be applied. We here used the shortest path policy. Let
$\mathcal{L}$ be the set of all links in the considered topology. To assign an
appropriate bandwidth to each edge server on a shared link (lines 4–10), the
SDN controller considers two main criteria: ($i$) the number of reachable
cache servers and ($ii$) their hop counts.

Fig. 5.3: Proposed time slot structure (a), and example of bandwidth
allocation strategy (b-c).

Suppose edge server $i\in\mathcal{V}$ is reaching server $j\in\mathcal{C}$
through link $l\in\mathcal{L}$ that is shared with a subset of edge servers
denoted by $V^{i}_{l}$. Let $b^{i,j}_{l}$ be the amount of allocated bandwidth
to server $i\in\mathcal{V}$ for reaching server $j\in\mathcal{C}$ through
shared link $l$ among edge servers in $V^{i}_{l}$; thus, regarding the
considered criteria, $b^{i,j}_{l}$ can be computed as follows:

$\displaystyle b_{l}^{i,j}=\frac{H_{l}-h^{i,j}_{l}}{\sum_{k\in
V^{i}_{l}}(H_{l}-h^{k,j}_{l})}~{}.~{}\omega_{l},$ $\displaystyle\forall
i\in\mathcal{V},j\in\mathcal{C},l\in\mathcal{L}$ (5.10)

where $H_{l}=\sum_{k\in{V^{i}_{l}}}\sum_{j\in\mathcal{C}}h^{k,j}_{l}$ and
$h^{i,j}_{l}$ indicates the hop counts of the path containing link $l$ from
$i\in\mathcal{V}$ to server $j\in\mathcal{C}$. Using this strategy, as shown
in Fig. 5.3(c), the bandwidth values allocated to shared link S1–S2 for LES
and NES to reach CS2 and CS1, respectively, are more than the amount allocated
to LES for accessing CS3. Next, the SDN controller finds the available
bandwidth in each path by determining the minimum bandwidth of used links as a
bottleneck (lines 11–13), and then updates all edge servers (line 14). This
described procedure will repeat after each $\tau+\xi$ seconds, where $\xi$ is
the duration of the EU interval, within the while loop (line 15). Assume $n$,
$s$, and $h$ indicate the number of edge servers, number of all shared links,
and maximum hop counts of selected paths. The overall time complexity of Alg.
3 can be given as $O(s^{2}~{}.~{}n)+O(n~{}.~{}h)$.

Algorithm 3 LEADER SDN controller heuristic algorithm.

1:while $True$ do

2: UpdateSet($cache\\_map$, $edge\\_map$, $bw\\_map$, $comp\\_map$)

3: SelectPath()

4: for each $l$ in $\mathcal{L}$ do

5: for each $i\in\mathcal{V}$ use $l$ do

6: for each $j\in V^{i}_{l}$ do

7: AllocateBW()

8: end for

9: end for

10: end for

11: for each (LES, $\mathcal{V}\cup\mathcal{C}$, path) do

12: AvailableBw()

13: end for

14: Update $\mathcal{V}$ in EU interval

15: Wait ($\tau$)

16:end while

#####  5.1.2.2 Edge Server Heuristic Algorithm

Each edge server runs Alg. 4 in the SR interval to serve its own clients’
requests with minimum serving times. For this purpose, each LES server
receives cache and edge maps ($cache\\_map$, $edge\\_map$), bandwidth maps to
other servers $\in\mathcal{V}\cup\mathcal{C}$ ($bw\\_map$), and the NESs’
available computational information ($comp\\_map$) from the SDN controller.
Next, it compares the received request ($req$) to $on\\_the\\_fly$ requests
(i.e., requests currently being served). If $req$ is in the $on\\_the\\_fly$
set, then it calls HoldReq to hold the request and prevent network resource
wastage and congestion (lines 2–3). Otherwise, this set is updated by the new
request to be processed (line 5). All feasible actions (Fig. 5.2) are
calculated by the ValidAction function and stored in the $action\\_set$
repository (line $6$). After that, based on the proposed objective function in
(5.8), the serving times of actions in $action\\_set$ are calculated by
utilizing the CostFunction function and the results are saved in
$action\\_cost$ (line 7). Next, the minimum value (i.e., serving time) in the
$action\\_cost$ is determined by the OptimalAction function, and its
associated action is retrieved from $action\\_set$ and saved as the optimal
action, $opt\\_action$ (line 8). Finally, the edge server utilizes the
ServeRequest function to serve the client’s request (line 9), and upgrades
cache, edge, bandwidth, and comp maps, plus the $on\\_the\\_fly$ repository by
the UpdateVariables function (line 10). Assume $a$ denotes the number of
discussed actions. Employing the Quicksort approach, the time complexity of
Alg. 4 in the worst case would be $O(a*log(a))$.

Algorithm 4 LEADER edge server heuristic algorithm.

1:Input $req$, $cache\\_map$, $edge\\_map$, $bw\\_map$, $comp\\_map$,
$on\\_the\\_fly$

2:if req $\in$ $on\\_the\\_fly$ then

3: HoldReq($req$)

4:else

5: $on\\_the\\_fly$.add($req$)

6: $action\\_set\leftarrow$ValidAction()

7: $action\\_cost\leftarrow\text{CostFunction($action\\_set$)}$

8: $opt\\_action\leftarrow$OptimalAction($action\\_set$,$action\\_cost$)

9: ServeRequest($req$,$opt\\_action$)

10: UpdateVariables$()$

11:end if

####  5.1.3 LEADER Performance Evaluation

In this section, we describe LEADER’s evaluation setup, metrics, and methods
and evaluate LEADER’s performance in two scenarios.

#####  5.1.3.1 Evaluation Setup

To evaluate the LEADER framework in a realistic large-scale environment, we
consider a real network topology called Geant Zoo (2020) (40 OF switches, 61
layer-2 links) and instantiate our testbed including 301 components (each of
them runs on Ubuntu 18.04 LTS inside Xen virtual machines) on the CloudLab
Ricci et al. (2014) environment. We implement all modules of five considered
edge servers and an SDN controller (i.e., FloodLight) in Python to serve
requests received from 250 AStream Juluri et al. (2015) DASH players. For
simplicity, we assume that all clients already joined the network.

The BOLA Spiteri et al. (2016) quality adaptation algorithm is used in our
testbed. Each edge server decides for its own clients’ group (50 clients) and
collaborates with other edge servers. Moreover, we employ four CDN servers
(with a total cache size of 40% of the video dataset) and an origin server
(containing the entire video sequences) that run an Apache HTTP server and
MongoDB. Each edge server contains a partial cache with only 5% of the video
dataset. The most popular video sequences are pre-cached on the edge servers
to avoid a slow startup of the system. Note that LEADER is independent of the
caching policy and could be compatible with any type of caching strategies.
However, for simplicity, Least Recently Used (LRU) is considered in all CDN
and partial caches as the cache replacement policy. Fifty video sequences
Lederer et al. (2012) with 300 seconds duration, comprising two-second
segments in five representations (0.089, 0.262, 0.791, 2.4, 4.2 Mbps) are used
in our experiments.

For the sake of simplicity, we assume that the popularity of each video is
known in advance and sorted in descending order. The video access probability
is generated following a Zipf distribution Cherkasova and Gupta (2004) with
the skew parameter $\alpha=0.75$, i.e., the probability of an incoming request
for the $i^{th}$ most popular video is given as
$prob(i)=\frac{1/i^{\alpha}}{\sum_{j=1}^{K}1/j^{\alpha}}$, where $K=50$. The
Docker image jrottenberg/ffmpeg FFmpeg (2020) is utilized to measure the
segment transcoding time on edge servers. We set the bandwidth values of all
links in different paths from each LES to the origin server, cache servers,
and other NES servers to 50, 100, and 200 Mbps, respectively.

#####  5.1.3.2 Evaluation Methods and Metrics

In our performance evaluation, we compare the acquired results by LEADER with
the following methods:

  1. 1.

Non Edge Collaborative (NECOL): Like in most of the existing works, there is
not any edge collaboration possibility in this approach. In a NECOL-based
system, each LES serves its associated clients’ requests separately via one of
the actions $1,2,6,7$, or $8$ (Fig. 5.2).

  2. 2.

Default Edge Collaborative (DECOL): In this method, all edge servers
collaborate in both caching and transcoding. However, the SDN controller does
not take into account any bandwidth allocation policy for the shared links.

Note that our testbed with a similar setup is used for all schemes to produce
fair and robust comparisons. The performance of the aforementioned approaches
is evaluated with common QoE-related parameters and network utilization
metrics as follows:

  1. 1.

Average Segment Bitrate (ASB) of all the downloaded segments,

  2. 2.

Average Number of Quality Switches (AQS) as the average number of segments
whose bitrate levels are changed compared to their previous one,

  3. 3.

Average Number of Stalls (ANS) that is equal to the average number of
rebuffering events,

  4. 4.

Average Stall Duration (ASD) that is the average of total video freeze time in
all clients,

  5. 5.

Average Perceived QoE (APQ) calculated by ITU-T Rec.P.1203 mode 0 P.1203
(2020),

  6. 6.

Cache Hit Ratio (CHR) defined as the fraction of segments fetched from the
CDNs or edge servers,

  7. 7.

Edge Transcoding Ratio (ETR) that is the fraction of segments transcoded at
the edge servers,

  8. 8.

Backhaul Traffic Load (BTL) as the volume of segments downloaded from the
origin server.

Note that we use the method discussed in Section 4.1.3 to calculate the
results reported in the next section.

#####  5.1.3.3 Evaluation Results

Fig. 5.4: QoE (a–c), and network utilization (d–e) results for the NECOL,
DECOL, and LEADER systems for 250 clients.

In the first scenario, we evaluate LEADER’s performance in terms of the QoE
parameters and compare the results with NECOL and DECOL. As shown in Fig.
5.4(a–c), DECOL serves clients with higher ASB, decreases AQS, improves ANS,
and shortens ASD, consequently increases APQ by up to 20% compared to NECOL
(Fig. 5.4(c)), since it uses NESs’ cooperation and can shorten clients’
serving time through fetching/transcoding actions by NESs. Because LEADER
employs a bandwidth allocation strategy, each LES has sufficient bandwidth for
accessing other servers, specifically when competing with other NESs in shared
links. Consequently, LEADER’s LESs download segments with higher ASB, decrease
AQS, ANS, ASD, and thus improve APQ by about 47% and 22% compared to NECOL and
DECOL, respectively.

The effectiveness of LEADER regarding the network utilization aspect is
evaluated in the second scenario. Note that the NECOL-enabled system
encounters a cache miss event when (i) the requested or higher quality levels
do not exist in the LES cache or CDNs, (ii) available bandwidth values are
insufficient to fetch the requested or higher quality levels from CDNs, or
(iii) the available LES’s processing capability is not enough to transcode the
requested quality from a higher quality. In addition, a cache miss occurs in
DECOL and LEADER if the LES cannot fetch or transcode the requested quality by
NESs’ assistance.

The CHR metric shows that DECOL outperforms the NECOL system due to its
capability for fetching requested or higher quality levels from NESs or using
NESs’ idle resources for performing transcoding (see Fig. 5.4(d)). Therefore,
it downloads fewer segments from the origin server and improves backhaul
bandwidth usage (Fig. 5.4(e)), but uses more computational resources at the
edge servers due to performing transcoding tasks, as compared to NECOL (Fig.
5.4(d)). Although LEADER and DECOL have a similar behavior of using NESs’
resources for fetching/transcoding, the bandwidth strategy helps LEADER to
provide sufficient bandwidth between LESs and cache servers and fetch more
segments directly from CDNs with less serving time (i.e., without
transcoding); LEADER thus outperforms the DECOL system in terms of CHR, BTL,
and ETR. However, LEADER and DECOL as collaborative systems increase the
number of communicated messages (cache, edge, bandwidth, comp maps) to/from
the SDN controller compared to the NECOL system.

###  5.2 ARARAT Framework

This section introduces the ARARAT system Farahani et al. (2022c) as another
collaborative edge-assisted framework for HTTP adaptive video streaming. We
first discuss the motivation and problem definition for designing the ARARAT
framework in Section 5.2.1. We also explain the proposed hierarchical
architecture, formulate the problem as a central optimization model, and
analyze its time complexity. Section 5.2.2 describes our proposed heuristic
approaches. The evaluation setup and results are presented in Section 5.2.3.

####  5.2.1 ARARAT System Design

#####  5.2.1.1 ARARAT Problem Statement

As discussed in Section 2.2, there are many NAVS systems essentially studying
a single-edge server in an SDN-enabled environment. However, a single-edge
server does not include enough cache and computing resources to satisfy
different users’ demands. Edge servers collaborating on caching and
transcoding can potentially improve edge servers’ resource utilization,
decrease backhaul bandwidth usage, and improve users’ QoE. Let us consider a
simple example including two types of edge servers, i.e., Local Edge Server
(LES) and Neighboring Edge Servers (NESs), which are adjacent to the LES. Both
the LES and the NESs are equipped with transcoding (Tran) and partial caching
(PC) functions. (We will elaborate on this in more detail in Section 5.2.1.2).

A LES serves its clients’ requests directly, while NESs collaborate with the
LES on transcoding and caching in case of lack of processing resources or on
cache misses. Note that a LES concurrently can play the NES role for other
NESs. Moreover, we consider multiple CDN servers containing various parts of
video sequences and an origin server including all video segments in various
representations. In such systems, like illustrated in Fig. 5.5, a bunch of
requests is collected by each LES in specified time slots (intervals). Then,
the SDN controller runs a centralized approach (e.g., an optimization model)
to come up with appropriate decisions for serving all clients’ requests. The
ARARAT system aims at achieving the best solutions to respond to the following
key questions:

Fig. 5.5: ARARAT action tree.

  1. 1.

Where is the optimal server (i.e., LES, NES, CDN node, or the origin) in terms
of the minimum serving time (i.e., fetching, potentially plus transcoding) for
acquiring each client’s requested content quality level from?

  2. 2.

What is the optimal approach for delivering each client’s requested quality
level, i.e., fetch or transcode it from a higher quality, considering edge
servers’ bandwidth and computational limitations?

  3. 3.

What is the optimal action to reach each client’s requested quality?

To this end, ARARAT considers clients’ serving times, edge resource
limitations, and network costs to find the solution by utilizing actions from
the Action Tree depicted in Fig. 5.5 (action numbering as in the figure):

  1. 1

Fetch the requested quality level directly from the LES.

  2. 2

Transcode the requested quality from a higher quality at the LES.

  3. 3

Fetch a higher quality from the best adjacent NES and transcode it at the LES.

  4. 4

Fetch the requested quality directly from the best NES.

  5. 5

Transcode the requested quality from a higher quality at the best NES and then
transmit it from the NES to the LES.

  6. 6

Send a higher quality from LES to the best NES (“best” in terms of available
processing capability), transcode it at the NES, and then forward it back from
the NES to the LES.

  7. 7

Fetch the requested quality from the best CDN server.

  8. 8

Fetch a higher quality from the best CDN server and transcode it at the LES.

  9. 9

Fetch the requested quality from the origin server.

Sections 5.2.1.2 and 5.2.1.3 will describe how the SDN controller communicates
with edge and CDN servers to determine the optimal actions in terms of serving
time and network cost.

#####  5.2.1.2 ARARAT Architecture

Regarding our discussion above and the problem statement, we here propose a
multi-layer architecture for ARARAT consisting of three core layers: edge
layer, CDN/origin layer, and control layer (see Fig. 5.6).

  1. 1.

Edge Layer. As introduced in Section 5.2.1.1, edge servers are categorized
into LES and NESs and located close to base stations (e.g., gNodeB in 5G).
Each of them periodically communicates with the SDN controller, sends the
status of its available resources, e.g., CPU and RAM (in so-called comp_map
messages), and its cache occupancy (in edge_map messages) to the SDN
controller, and responds to the clients. Each edge server consists of the
following components: (i) Transcoding Module (Tran) to transcode segments from
a higher quality level to the demanded quality level; (ii) Partial Cache (PC)
that stores a limited number of segments; and (iii) Request Analyzer Module
(RAM), which is designed to aggregate identical requests (issued by several
clients) and consider only one request for each segment. Note that the network
slicing method is employed to design an independent logical network-assisted
video streaming instance over the common edge layer; therefore, the edge layer
can be utilized to serve various network services, e.g., video streaming
services with different requirements.

Fig. 5.6: ARARAT architecture.

  2. 2.

CDN/Origin Layer. The CDN/origin layer is constructed by multiple CDN servers
(CSs) where each of them contains various parts of video sequences and
periodically informs the SDN controller about the availability of the stored
segments and their quality levels through cache_map messages. The cache_map
structure is depicted in Fig. 5.6. Moreover, an origin server that contains
all video segments in multiple representations is placed in this layer.

  3. 3.

Control Layer. An SDN controller is placed in this layer. The SDN controller
consists of the following modules: (i) Bandwidth Monitoring Module (BMM): It
monitors the available bandwidth of different paths between each LES and other
servers, i.e., NESs, CSs, and the origin server. The output of the BMM will be
stored in a sub-repository called bandwidth_map which is part of a large
repository named resource maps. (ii) Path Selection Module (PSM): It uses BMM
results and selects the shortest paths with maximum available bandwidth
between each LES and NESs, CSs, and the origin server. (iii) Central
Optimization Module (COM): COM runs an optimization model to determine an
appropriate solution for the questions listed in Section 5.2.1.1. For this
purpose, COM utilizes the received items that are stored in resource maps,
i.e., cache_map, edge_map, comp_map, and bandwidth_map, and finds an optimal
solution (i.e., in terms of lowest serving time, and network cost) from the
Action Tree (Fig. 5.5).

Table 5.2: ARARAT Notation. Input Parameters |  |  |  |
---|---|---|---|---
| $\mathcal{C}$
---
$\mathcal{V}$
$\mathcal{R}$
$R_{i}$
$\mathcal{Q}^{r}$
$\mathcal{T}$
$\alpha^{p,r}_{i}$
$\omega_{i,j}$
$l$
$\delta^{r}_{p}$
$\pi^{r}_{p}$
$\Omega_{i}$
$\mu^{r}_{p}$
$\eta_{p}$
$\Delta_{tr}$
$\Delta_{bw}$
$\beta_{1},\beta_{2}$
| Set of $k$ CDN servers and an origin server (i.e., $c=0$)
---
Set of $n$ edge servers
Set of $m$ requests received by the SDN controller from $\mathcal{V}$
Set of requests issued by edge server $i\in\mathcal{V}$
Set of possible quality levels for serving quality $p^{*}$ requested
by $r\in\mathcal{R}$, where
$\mathcal{Q}^{r}=\\{p^{*},p^{*}+1,...,p^{*}_{max}\\}$ and $p^{*}_{max}$
is the maximum quality level for the demanded segment
Set of possible transcoding statuses: $\mathcal{T}=\\{0,1,2\\}$; $t$ is 1 or 2
if the requested quality is transcoded from a higher quality
$p\in\mathcal{Q}^{r}$ at the NES or at the LES, respectively; otherwise t=0
Availability of quality level $p$ in server $i\in\mathcal{V}\cup\mathcal{C}$;
$\alpha^{p,r}_{i}=1$
means server $i$ hosts quality $p$ to serve $r\in\mathcal{R}$, otherwise
$\alpha^{p,r}_{i}=0$
Available bandwidth on path between $i\in\mathcal{V}$ and
$j\in\\{\mathcal{V}\cup\mathcal{C}\\}\setminus i$
Action index, where $l=1$, if the selected action from the
action tree is action $6$, otherwise $l=0$
Size of segment in quality $p$ requested by $r\in\mathcal{R}$ (in bytes)
Required resources (i.e., CPU time in seconds) for transcoding
quality $p\in\mathcal{Q}^{r}$ into the requested quality by $r\in\mathcal{R}$
Available computational resources (available CPU) of $i\in\mathcal{V}$
Required time for transcoding quality $p\in\mathcal{Q}^{r}$ into the quality
requested by $r\in\mathcal{R}$
Bitrate associated to quality level $p\in\mathcal{Q}^{r}$
Computational cost per CPU core per second
Bandwidth cost per bit per second
Adjustable weighting coefficients for the serving time and the
network cost, respectively
|  |  |
Variables |  |  |  |
| $B^{p,r,t}_{i,j,l}$
---
$\tau^{r}_{i}$
$T^{p,r}_{i,j}$
$\Gamma$
$\Pi,\Lambda$
$\Psi$
| Binary variable where $B^{p,r,t}_{i,j,l}=1$ shows server
$i\in\mathcal{V}\cup\mathcal{C}$
---
transmits quality $p\in\mathcal{Q}^{r}$ to server $j\in\mathcal{V}$ for
request $r$ with
transcoding status $t$ and action index $l$, otherwise $B^{p,r,t}_{i,j,l}=0$
Required transcoding time at server $i\in\mathcal{V}$ for serving
$r\in\mathcal{R}$
Required time of transmitting quality level $p\in\mathcal{Q}^{r}$ in response
to request $r\in\mathcal{R}$ from server $i\in\mathcal{V}\cup\mathcal{C}$ to
$j\in\mathcal{V}$
Serving time consisting of $\tau^{r}_{i}$ and $T^{p,r}_{i,j}$
Costs of computation and bandwidth for serving clients’ requests,
respectively
Total network cost consisting of $\Pi$ and $\Lambda$
|  |  |

#####  5.2.1.3 ARARAT Centralized Optimization Model

Let set $\mathcal{C}$ consist of $k$ CDN servers and an origin server, where
$c=0$ indicates the origin server (see Table 5.2 for a summary of the
notation). Moreover, let us define $\mathcal{R}$ as the set of $m$ requests
received by the SDN controller from the set $\mathcal{V}$ of $n$ edge servers.
The subset $R_{i}\subseteq\mathcal{R}$ shows all requests issued by edge
server $i\in\mathcal{V}$. Furthermore, we assume that the SDN controller
periodically receives the cache_map and the edge_map from cache and edge
servers, respectively. $\alpha^{p,r}_{i}$ denotes the availability of quality
level $p$ of a segment demanded by request $r$ at cache/edge server $i$.

We assume that the SDN controller defines a data path between two servers
$i\in\mathcal{V}$ and $j\in\\{\mathcal{C}\cup\mathcal{V}\\}\setminus i$ where
$\omega_{i,j}$ shows its available bandwidth between $i$ and $j$ accordingly.
As mentioned earlier, when a LES $i$ requests quality $p$ from server
$j\in\\{\mathcal{C}\cup\mathcal{V}\\}\setminus i$, it is possible to receive
the requested quality or a higher one from $j$. In fact, if $p$ is available
in the cache of $j$, $p$ can be directly forwarded to $i$; otherwise, since
all edge servers can run the transcoding function, $j$ can send a higher
quality to $i$; therefore, for each request $r$, we define
$\mathcal{Q}^{r}=\\{p^{*},p^{*}+1,...,p^{*}_{max}\\}$ as the set of possible
quality levels for serving requested quality $p^{*}$, where $p^{*}_{max}$ is
the maximum quality level for the requested segment. In the following, we
introduce an MILP optimization model that decides an optimal action for each
request $r\in\mathcal{R}$ based on the given resource maps information in such
a way that the total serving time and network cost are minimized. For this
purpose, the following aspects are required to be taken into account to force
the model to:

  1. 1.

select only one action for each request $r\in\mathcal{R}$.

  2. 2.

determine the best action in terms of serving time (i.e., fetching and
transcoding) among all feasible actions for each request $r\in\mathcal{R}$.

  3. 3.

not violate the given available network resources by the selected action.

  4. 4.

not violate essential regulations defined by stakeholders.

  5. 5.

determine the best action in terms of network cost (i.e., bandwidth and
computation) among all feasible actions for each request.

Therefore, the model should satisfy five groups of constraints: Action
Selection (AS), Serving Time (ST), CDN/Origin (CO), Resource Consumption (RC),
and Network Cost (NC) constraints, which are described as follows.

(i) AS Constraint. The first constraint determines a suitable action from the
introduced action tree (Fig. 5.5) for each request $r$ issued by LES $j$. As
explained in Section 5.2.1.1, action 6 of the action tree forces (i) the LES
to send a higher quality to the NES with highest available computational
resources, and (ii) the NES to send back the requested quality to the LES
after completing the transcoding process. However, the LES does not need to
transmit a higher quality to other servers in other actions. To distinguish
action 6, we define an action index $l$, where $l=1$ if the selected action is
action 6, otherwise $l=0$. Moreover, $t\in\\{0,1,2\\}$ defines the following
transcoding statuses: $t=0$ indicates that the requested quality is
transferred without transcoding, and $t=1$ or $t=2$ means the requested
quality is transcoded from a higher quality at the NES or the requesting LES,
respectively. Therefore, the first constraint selects appropriate values of
the binary variable $B^{p,r,t}_{i,j,l}$, where $B^{p,r,t}_{i,j,l}=1$ indicates
server $i$ (i.e., CDN, origin, or NES) replies to request $r$ issued by LES
$j$ through sending quality $p$ with transcoding status $t$, and action index
$l$ (refer to Table 5.2 for notations):

$\displaystyle 1\leq$
$\displaystyle\sum_{i\in\mathcal{C}\cup\mathcal{V}}\sum_{t\in\mathcal{T}}\sum_{p\in\mathcal{Q}^{r}}(B^{p,r,t}_{i,j,l=0}~{}.~{}\alpha^{p,r}_{i})+\sum_{i\in\mathcal{V}\setminus
j}\sum_{p\in\mathcal{Q}^{r}}(B^{p,r,t=0}_{j,i,l=1}~{}.~{}\alpha^{p,r}_{j}+B^{p,r,t=1}_{i,j,l=1}~{}.~{}(1-\alpha^{p,r}_{i}))\leq
2,$ $\displaystyle\forall j\in\mathcal{V},r\in\mathcal{R}_{j}$ (5.11)

Note that since the 6th action of the action tree forces the LES to send a
higher quality to the NES with the highest available computational resources,
and, it receives the requested quality from that NES, the MILP model needs to
set both binary variables $B^{p,r,t=0}_{i,j,l=1}$ and $B^{p,r,t=1}_{i,j,l=1}$.
Therefore, the upper bound will be equal to two when MILP selects action 6.
Moreover, $\alpha^{p,r}_{i}$ is used to assure the quality $p$ requested by
request $r$ is available in server $i$.

(ii) ST constraints. The first ST constraint determines the required time,
denoted by $T^{p,r}_{i,j}$, for transmitting quality level
$p\in\mathcal{Q}^{r}$ in response to request $r$ from each server $i$ to each
LES $j\in\mathcal{V}$:

$\displaystyle
T^{p,r}_{i,j}=\begin{cases}\frac{B^{p,r,t=0}_{j,i,l=1}~{}.~{}\delta^{r}_{p}+B^{p,r,t=1}_{i,j,l=1}~{}.~{}\delta^{r}_{p^{*}}}{\omega_{i,j}}\hskip
11.38092pt\forall r\in\mathcal{R}_{j},i\in\mathcal{V}\setminus j\\\ \\\
\frac{\sum_{t\in\mathcal{T}}B^{p,r,t}_{i,j,l=0}~{}.~{}\delta^{r}_{p}}{\omega_{i,j}}\hskip
11.38092pt\forall
r\in\mathcal{R}_{j},i\in\\{\mathcal{C}\cup\mathcal{V}\\}\setminus
j\end{cases}$ (5.12)

where $\delta^{r}_{p}$ and $\delta^{r}_{p^{*}}$ show the size (in bytes) of
quality $p$ and $p^{*}$ of the segment requested by $r\in\mathcal{R}$,
respectively, where $p^{*}\leq p$. The next constraint measures the required
transcoding time $\tau_{i}^{r}$ at server $i\in\mathcal{V}$ in case of serving
the quality requested by $r\in R$ from a higher quality $p$ by transcoding:

$\displaystyle\sum_{j\in\mathcal{V}}\sum_{l\in\\{0,1\\}}\sum_{p\in\mathcal{Q}^{r}}B^{p,r,t=1}_{i,j,l}~{}.~{}\mu^{r}_{p}\leq\tau_{i}^{r},$
$\displaystyle\hskip 19.91684pt\forall i\in\mathcal{V},r\in\mathcal{R}$ (5.13)

Therefore, the serving time, namely $\Gamma$, i.e., fetching time plus
transcoding time can be expressed as follows:

$\displaystyle\sum_{r\in\mathcal{R}}\sum_{i\in\mathcal{V}\cup\mathcal{C}}\sum_{j\in\mathcal{V}}\sum_{p\in\mathcal{Q}^{r}}T^{p,r}_{i,j}+\tau^{r}_{i}\leq\Gamma$
(5.14)

(iii) CO constraints. This group of constraints forces the model to fetch the
exact quality $p^{*}$ from the origin server when the origin server is
selected to serve the LES; so, we have:

$\displaystyle\sum_{t\in\mathcal{T}}\sum_{p\in\mathcal{Q}^{r}}B^{p,r,t}_{i=0,j,l=0}~{}.~{}p=p^{*},$
$\displaystyle\forall j\in\mathcal{V},r\in R_{j}$ (5.15)

Note that $i=0$ in Eq. (5.15) means that the origin server is serving
requests. We also should prevent CSs from performing transcoding functions by
the following equation:

$\displaystyle\sum_{i\in\mathcal{C}}\sum_{r\in
R_{j}}\sum_{p\in\mathcal{Q}^{r}}B^{p,r,t=1}_{i,j,l=0}~{}.~{}p=0,$
$\displaystyle\forall j\in\mathcal{V}$ (5.16)

(iv) RC constraints. This group of constraints guarantees that the required
bandwidth for transmitting segments on the link between two servers
$j\in\mathcal{V}$ and $i\in\mathcal{C}\cup\mathcal{V}$ should not exceed the
available bandwidth:

$\displaystyle\sum_{t\in\mathcal{T}}\sum_{l\in\\{0,1\\}}\sum_{r\in
R_{j}}\sum_{p\in\mathcal{Q}^{r}}B^{p,r,t}_{i,j,l}~{}.~{}\eta_{p}\leq\omega_{i,j},$
$\displaystyle\forall
j\in\mathcal{V},i\in\\{\mathcal{C}\cup\mathcal{V}\\}\setminus{j}$ (5.17)

where $\eta_{p}$ is the bitrate associated to quality level $p$. Similarly,
the next constraint limits the maximum required processing capacity for the
transcoding operation to the available computational resource on each server
$j\in\mathcal{V}$ (denoted by $\Omega_{j}$):

$\displaystyle\sum_{r\in\mathcal{R}}\sum_{p\in\mathcal{Q}^{r}}\sum_{l\in\\{0,1\\}}(\sum_{i\in\mathcal{C}\cup\mathcal{V}}B^{p,r,t=2}_{i,j,l}+\sum_{i\in\mathcal{V}\setminus
j}B^{p,r,t=1}_{j,i,l})~{}.~{}\pi^{r}_{p}\leq\Omega_{j},$ $\displaystyle\forall
j\in\mathcal{V}$ (5.18)

where $\pi_{p}^{r}$ is the required computational resources (i.e., CPU time in
seconds) for transcoding a higher bitrate $p$ into bitrate $p^{*}$ requested
by $r$.

(v) NC constraints. The last group of constraints formulates the total
bandwidth cost $\Lambda$ for transmitting segments on the link between two
servers $j\in\mathcal{V}$ and
$i\in\\{\mathcal{C}\cup\mathcal{V}\\}\setminus{j}$ as follows:

$\displaystyle\Delta_{bw}~{}.~{}\sum_{t\in\mathcal{T}}\sum_{l\in\\{0,1\\}}\sum_{r\in
R_{j}}\sum_{p\in\mathcal{Q}^{r}}B^{p,r,t}_{i,j,l}~{}.~{}\eta_{p}\leq\Lambda,$
$\displaystyle\forall
j\in\mathcal{V},i\in\\{\mathcal{C}\cup\mathcal{V}\\}\setminus{j}$ (5.19)

where $\Delta_{bw}$ refers to the bandwidth cost per bit per second.
Similarly, the next constraint specifies the total required computational cost
$\Pi$ for transcoding processes:

$\displaystyle\Delta_{tr}~{}.~{}\sum_{r\in\mathcal{R}}\sum_{p\in\mathcal{Q}^{r}}\sum_{l\in\\{0,1\\}}(\sum_{i\in\mathcal{C}\cup\mathcal{V}}B^{p,r,t=2}_{i,j,l}+\sum_{i\in\mathcal{V}\setminus
j}B^{p,r,t=1}_{j,i,l})~{}.~{}\pi^{r}_{p}\leq\Pi,$ $\displaystyle\forall
j\in\mathcal{V}$ (5.20)

where $\Delta_{tr}$ indicates resource computational cost per CPU core per
second. Therefore, the total network cost, i.e., $\Psi$ can be obtained as
follows:

$\displaystyle\Pi+\Lambda\leq\Psi$ (5.21)

Central optimization model. As mentioned earlier, a HAS client runs an ABR
algorithm to estimate the network’s bandwidth by measuring the time between
sending the request to download a segment and receiving the segment’s last
packet. Thus, minimizing the serving time in the optimization model directly
affects the HAS clients’ performance. On the other hand, the optimization
model must have the ability to be adjusted by the network operator based on
their business plans and desired network costs. Therefore, making a trade-off
between serving time and network cost in the objective enables the model to
select actions based on the operators’ desired policies. To this end, the
following model, in a multi-objective fashion, minimizes the clients’ total
serving time as well as the total network cost:

Minimize $\displaystyle\hskip
8.5359pt\beta_{1}~{}.~{}\frac{\Gamma}{\Gamma^{*}}+\beta_{2}~{}.~{}\frac{\Psi}{\Psi^{*}}$
(5.22) $\displaystyle s.t.$ $\displaystyle\hskip
14.22636pt\text{constraints}\hskip 14.22636pt\text{Eq.
}(\ref{ARARAT:eq:1})-\text{Eq. }(\ref{ARARAT:eq:11})$ $\displaystyle vars.$
$\displaystyle\hskip
14.22636ptT^{p,r}_{i,j},\tau^{r}_{i},\Gamma,\Psi,\Pi,\Lambda\geq
0,B^{p,r,t}_{i,j,l}\in\\{0,1\\}$

The first term in the objective function is the total serving time for all
clients’ requests in $\mathcal{R}$ while the second term determines the total
network cost. By minimizing the objective function (5.22), the SDN controller
can determine an optimal action for each request $r\in\mathcal{R}$. Two
weighting coefficients ($\beta_{1}$ and $\beta_{2}$) are defined to set
desirable priorities for serving time and network cost, respectively. These
weights can be adjusted by operators based on network policies where
$\beta_{1}+\beta_{2}=1$. Since $\Gamma$ and $\Psi$ have different units (i.e.,
seconds and dollars, respectively), a normalization strategy is required to
form the objective function. Therefore, we normalize each term by dividing it
by its associated maximum calculated value (i.e., $\Gamma^{*}$ and $\Psi^{*}$,
respectively). To determine $\Gamma^{*}$, we run the MILP model with
$\beta_{1}=0$ to achieve the minimum network cost, in other words, the maximum
delay. Similarly, we set $\beta_{2}=0$ to get $\Psi^{*}$. The obtained
$\Gamma^{*}$ and $\Psi^{*}$ are then used to run the model for different sets
of $(\beta_{1},\beta_{2})$.

#####  5.2.1.4 Complexity Analysis of the Optimization Model

Theorem I: The proposed MILP model (5.22) is an NP-hard problem.
Proof. The combination of introduced binary and non-binary variables makes the
optimization model (12) a MILP model. Using methods introduced by Conforti et
al. (2014), the proposed MILP model can be reduced to the Multiple Knapsack
Problem (MKP), which is a well-known NP-hard problem Garey and Johnson (1983),
in polynomial time.

Theorem II: Considering shared links between edge servers to reach other
servers (in $\mathcal{V}\cup\mathcal{C}$) in Eq. (5.22) changes the model to a
mixed integer non-linear programming (MINLP) model.
Proof: The proposed model (5.22) minimizes the clients’ serving time plus
network cost, assuming disjoint paths from edge servers in $\mathcal{V}$ to
other servers in $\mathcal{V}\cup\mathcal{C}$. Let us define two variables,
$\bar{\omega}_{i,j}$ and $\omega^{a,b}_{i,j}$ as optimal allocated bandwidth
between server $i$ and $j$ and optimal allocated bandwidth between server $i$
and $j$ over the link $(a,b)$, where
$\bar{\omega}_{i,j}\leq\omega^{a,b}_{i,j},\forall$ links
$(a,b),i\in\\{\mathcal{V}\cup\mathcal{C}\\}\setminus j,j\in\mathcal{V}$ for
considering bottleneck links. Thus, the required time $T^{p,r}_{i,j}$ for
transmitting quality level $p\in\mathcal{Q}^{r}$ from server $i$ to each LES
$j\in\mathcal{V}$ for each request $r\in R_{j}$ and quality
$p\in\mathcal{Q}^{r}$ is obtained as follows:

$\displaystyle
T^{p,r}_{i,j}=\begin{cases}\frac{B^{p,r,t=0}_{j,i,l=1}~{}.~{}\delta^{r}_{p}+B^{p,r,t=1}_{i,j,l=1}~{}.~{}\delta^{r}_{p^{*}}}{\bar{\omega}_{i,j}}\hskip
39.83368pt\forall i\in\mathcal{V}\setminus j\\\ \\\
\frac{\sum_{t\in\\{0,1,2\\}}B^{p,r,t}_{i,j,l=0}~{}.~{}\delta^{r}_{p}}{\bar{\omega}_{i,j}}\hskip
39.83368pt\forall i\in\\{\mathcal{C}\cup\mathcal{V}\\}\setminus j\end{cases}$
(5.23)

Moreover, the formulation of required bandwidth for transmitting segments on
the link between two servers $j\in\mathcal{V}$ and
$i\in\\{\mathcal{C}\cup\mathcal{V}\\}\setminus j$ should be updated as
follows:

$\displaystyle\sum_{l\in\\{0,1\\}}\sum_{t\in\\{0,1,2\\}}\sum_{r\in
R_{j}}\sum_{p\in\mathcal{Q}^{r}}B^{p,r,t}_{i,j,l}~{}.~{}\eta_{p}\leq\bar{\omega}_{i,j},$
$\displaystyle\forall
j\in\mathcal{V},i\in\\{\mathcal{C}\cup\mathcal{V}\\}\setminus j$ (5.24)

Therefore, replacing Eqs. (5.12) and (5.17) by Eqs. (5.23) and (5.24),