Content Distribution Network (CDN) is a large distributed network deployed worldwide designed to push the content on the edge of the networks. It moves content to mitigate increase in video traffic and enhance user satisfaction. It finds an intermediate point between the origin server and the clients. Network virtualization features, with novel concepts such as Network Function Virtualization (NFV)

and Software Defined Network (SDN) solutions can answer user's demands and, subsequently increase the network efficiency. Therefore, we look at the potential benefits of virtualization combining with CDNs.

Therefore, in this thesis, we designed and implemented a tool which performs optimizations that reduce the number of migrations necessary for a delivery task.

We present our work on virtualization in the context of replication of video content servers. The work covers the design of a virtualization architecture for which there are also several algorithms that can reduce overall costs and improve system performance. The thesis is divided into six parts. 1) Optimal solutions: In this situation, we presented an exact optimization solution based on the linear programming method that takes into account new criteria based on the desired quality of service of video clients, the capacity of the operator's network links and also the system parameters related to NFV/SDN virtualization such as disk size, available RAM memory, CPU capabilities, etc. A migration cost is introduced. It is the cost of deploying a new instance on a remote site. Once the optimization is complete, it recommended a list of data center sites to which virtual content servers could be migrated and thus optimize the parameters previously introduced.

2) Greedy (heuristic) solutions: For reasons of scalability, we propose a new heuristic method based on graph theory and more precisely on Gomory-Hu algorithm. The idea behind this solution is to reduce the number of links to check before moving to the optimization phase. Thus, we arrive at almost linear resolu-

tion times. Simulations on high density networks are carried out. We evaluate the results and propose possible server migrations as before.

3) Orchestration of services: Given that content delivery network has several virtual components, the proposed (optimal and heuristic) solutions are adapted to this novel context where the optimization objective is to orchestrate and chain a set of delivery components. Simulations on different network deployment scenarios are carried out. We evaluate the results and propose possible server orchestration and chaining between instances. 4) Multi-objective optimization: Still, the main objective in the previous techniques is unique (reduce the overall migration cost). Therefore, we tried in this thesis to propose a multi-objective optimization algorithm that take into consideration different criteria from the involved actors (content provider, network operator, and client) in the delivery chain. The idea behind this technique is to select an optimization layer (i.e., core, aggregation and edge/access) to where a migration algorithm can be executed. 5) Complex Active Networks: For such active network (such as informationcentric networking (ICN) or Hadoop), the legacy optimization algorithms are no more valid and they need to be adjusted in this novel context. Therefore, we adapt the optimization constraint to these network types and we coma up by a "budget" based model. The idea is to set a specific budget to each network node that represent the work that each node can do. Then, active network is modeled and the previous optimization algorithms are adapted and evaluated on complex graphs. Par conséquent, dans cette thèse, on présente nos travaux sur la virtualisation dans le contexte de la réplication des serveurs de contenu vidéo. Les travaux couvrent la conception d'une architecture de virtualisation pour laquelle on présente aussi plusieurs algorithmes qui peuvent réduire les co ûts globaux à long terme et améliorer la performance du système. Le travail est divisé en six parties : 1) Les solutions optimales : Dans cette situation, on présente une solution d'optimisation exacte basée sur la méthode d'optimisation linéaire qui prend en compte de nouveaux critères basés sur la qualité de service désirée par les clients de la vidéo, la capacité des liens du réseau de l'opérateur et aussi des paramètres système liés à la virtualisation NFV/SDN comme la taille des disques, des conteneurs NFV, de la mémoire RAM disponible, des capacités CPU, etc. Un co ûts de migration est introduit. Il correspond au co ût de déploiement d'une nouvelle instance sur un site distant. Une fois l'optimisation est terminée, on propose une liste de sites de centre des données vers lesquels des serveurs de contenu virtuels pourraient être migrés et par conséquent optimiser les paramètres précédemment introduits.

2) Les solutions heuristiques : Pour des raisons de passage à l'échelle, on propose une nouvelle méthode heuristique basée sur la théorie des graphes et plus précisèment sur Gomory-Hu. L'idée derrière cette solution est de réduire le nombre de liens à vérifier avant de passer à la phase d'optimisation. Ainsi, nous arrivons à des temps de résolution presque linéaires. Des simulations sur les réseaux à très haute densité sont effectuées. On évalue les résultats et propose des migrations de serveurs potentiels comme précédemment. I would like to thank as well my co-supervisor Dr. Emad Abd-Elrahman for his motivation, dedication, and patience.

Besides, I would like to thank the members of the dissertation jury for accepting my invitation. I am particularly honored by their presence. I thank the dissertation reviewers Prof. Jean-Pierre Guedon and Prof. Enrico Natalazio for their insightful comments and helpful feedback. I also thank the dissertation examiners Prof. Houda Labiod, Prof. Ahmed Kamal, and and Prof. Hassine Moungla for their time and flexibility.

Last but certainly not least, I would like to thank my parents. Thank you for your continued support, kindly prayers and unconditional love. I sincerely thank my mother Nadia who loved me very much. She was always beside me during the whole thesis and without her I could not finish the thesis.

No words can express my appreciation and gratitude. Love you very much. I thank my brothers and sisters I thank my friends ... 6. Ibn-Khedher, H., Abd-Elrahman, E., & Afifi, H. (2016). OMAC: optimal migration algorithm for virtual CDN. In 23rd international conference on telecommunications, ICT 2016, thessaloniki, greece, may 16-18, 2016 (pp. 1-6).

7. Ibn-Khedher, H., Hadji, M., Abd-Elrahman, E., Afifi, H., & Kamal, A. E. (2016). Scalable and cost efficient algorithms for virtual CDN migration. In 41st IEEE conference on local computer networks, LCN 2016, dubai, united arab emirates, november 7-10, 2016 (pp. 112-120).

8. Abd-Elrahman, E., Ibn-Khedher, H., & Afifi, H. (2015). D2D group communications security. In International conference on protocol engineering, ICPE 2015, and international conference on new technologies of distributed systems, NTDS 2015, paris, france, july 22-24, 2015 (pp. 1-6). 9. Abd-Elrahman, E., Ibn-Khedher, H., Afifi, H., & Toukabri, T. (2015). Fast group discovery and non-repudiation in D2D communications using IBE.

In International wireless communications and mobile computing conference, IWCMC 2015, dubrovnik, croatia, august 24-28, 2015 (pp. 616-621).

10. Ibn-Khedher, H., Abd-Elrahman, E., Afifi, H., & Forestier, J. (2015). Network issues in virtual machine migration. In International symposium on networks, computers and communications, ISNCC 2015, yasmine hammamet, tunisia, may 13-15, 2015 (pp. [1][2][3][4][5][START_REF]Amazon cloudfront[END_REF]. are two paradigms which aim to virtualize certain network functions while adding more flexibility and increasing the overall network performance. ETSI has highlighted virtualized CDN (vCDN) among the major NFV use cases. The main purpose of vCDN is to allow the operator to dynamically deploy on demand virtual cache nodes to deal with the massive growing amount of video traffic. Scaling in/out, caching as a service etc. are also among the key benefits of vCDN. In this thesis we are motivated to review and address the overall virtualization challenges for CDN transition to vCDN.

Further, literature lacks a general virtualization architecture which leads us to study this network and to design recent architectures that adapt with the network type problems (i.e., placement, migration, orchestration, intermediate node activity, etc.). Furthermore, despite the importance of optimization tasks, such functions are missing in the global architecture. We are therefore, motivated in this thesis to contribute with novel optimization algorithms that may solve the major problems of vCDN deployment in current network operator environment. Coming up with a network simulator tool that help network operator to manage the deployment of vCDN is also incentive.

Contribution

Our contributions consist of the the design of a novel virtualization architecture for vCDN. Then, the main network issues in virtual machine migration and especially for vCDN use case and in an SDN/NFV optimization context is proposed.

Further, we propose different optimization algorithms for vCDN. Through the first optimization (i.e., Optimal Placement Algorithm for virtual CDN (OPAC)), we are going to formulate an exact algorithm based on a mathematical model for deciding the optimal location to migrate a vCDN or to instantiate (place) a new vCDN on demand to satisfy users quality requirements. Then, a slight modification to the algorithm is proposed in order to solve the vCDN migration problem.

As a result an Optimal Migration Algorithm for virtual CDN (OMAC) is formulated. Further, to cope with scalability problems of exact algorithms, we adapt a heuristic algorithm (i.e., Heuristic Placement Algorithm for virtual CDN (HPAC))

to deal with our constraints when large scale networks need to be optimized. In this algorithm, we exploit the well known Gomory-Hu method to find a near optimum point of operation.

Moreover, as CDN is a set of system components, optimizing CDN placement requires considering the vCDN orchestration problem. Therefore, we contribute by a different optimization algorithm. Through this optimization (Optimal vCDN Orchestration Algorithm), we are going to formulate an exact algorithm based on a linear programming model for deciding the optimal locations to place vCDN components to satisfy users quality requirements and minimize the overall load on the main nodes and links. The major objective from the proposed algorithm is to minimize the total orchestration cost of vCDN components(vCDNC) while minimizing the additional extra-costs needed for caching, streaming, and replicating the virtual instances.

Still, these optimization algorithms are mono-objective. Since vCDN collaborate with two other actors (content provider and end-user), we contribute in this thesis by a multi-criteria decision making technique, TOPSIS. It is adapted also in the context of vCDN migration. Finally, as the optimization algorithms (mono and multi-objective) deal with many heteroclite parameters, a clear view on how/where/when they are extracted and how they are reflected on a typical SDN/NFV architecture is diagrammed.

Among the major contributions in this thesis we highlight the implementation of vCDN Infrastructure Optimization Simulator (vIOS). It is a high level implementation of a network tool that uses the previous optimization algorithms on a real virtualization environment, OpenStack. An integration of this tool in Orange operator shows its feasibility and effectiveness to manage high complex graphs as inputs and recommend server migration lists for instance.

Up to now, network optimization can be easily modeled with classical tools or heuristic methods when the graph becomes too large. Introducing active nodes by means of ICN (or the Hadoop) concept introduces a modification in the graph equivalent to a negative resistance in electronic circuits (where active nodes supply an extra capacity/power if the input capacity measured is negative). Indeed, the ICN (or Hadoop) functions provide some kind of work inside the node. This transforms the two dimensional graph to a three dimensional one where the third dimension comes from the interaction between vertical layers within a node. Therefore, the previous conventional methods (OPAC, OMAC, HPAC, OCPA, and TOP-SIS) that can be used to optimize the graph are not anymore valid and we need to look for a more realistic optimization method that can take the third dimension into account. Therefore, in this thesis, we contribute by a proposed model and optimization algorithms that target general scenarios over ICN complex active network where active nodes add a third dimension to the traditional network topology representing local work (e.g., augmented reality, data mining, adaptation, publicity insertion, IoT data timing, etc.). Once the network flow of the ICN active network is defined, optimization algorithms aim to maximize the dynamic data rates under a total ICN budget.

Up to now, the most particular attention is being set to the exact or approximate approaches with performance guarantees on which very significant progress has been made in recent years and to a central problem in network flows which consists of calculating paths to steer/route traffic flows (demands) while minimizing congestion links (ratio of active traffic on capacity). For the best of your knowledge, the current implementation of these approaches are fully decentralized (i.e., a controller that collects topology parameters, live OpenStack statistics/metrics and user demands for a vCDN Service as input and recommends some decisions). In order to bybass the offline optimization that Gomory-Hu introduces when checking potential server migration and decentralize our optimization techniques, we contribute by a distributed maximum concurrent flow algorithm. It is inserted on each network nodes, collect user demands from children nodes and routes the maximum fraction of flow to multi-terminal while not exceeding the neighbor links capacities.

Outline

The remainder of this thesis is organized as follows. Chapter 2 describes the transition from CDN to vCDN. Chapter 3 analysis the overall networking issues in CDN virtualization and migration. Chapter 4 describes the optimal placement algorithm for vCDN, its parameters, constraints and objective function. Chapter 5 details our exact and heuristic optimization algorithms for vCDN migration.

Chapter 6 describes the orchestration algorithm (OCPA). Chapter 7 presents the multi-criteria decision making algorithm. Chapter 8 proposes a novel optimization technique over complex active networks. Chapter 9 concludes the thesis and discusses the future optimization techniques in virtualization. Given the limit size of the thesis, additional document is added at the end which represents further contributions (Annexes A, B, C, D, E, F).

Chapter 2

From CDN to vCDN: state of the art

Introduction

Content Distribution Network (CDN) is a large distributed network deployed worldwide designed to push the content on the edge of the networks (i.e. Point of Presence (PoP)). It solves two main problems that enhance the network performance: i) network latency for service access and ii) load balancing. CDN deployment is a major concern for network operators and service providers as video (either VoD or Live TV) represents more than half of the total Internet traffic (66% as per Orange) and will grow to more than 80% of all Internet traffic by 2019 1 .

The CDN moves content to mitigate increase in video traffic and enhance user satisfaction. It finds an intermediate point between the origin server and the clients for the replication. Network virtualization features, with new emerging concepts such as Network Function Virtualization (NFV) and Software Defined Network (SDN) solutions can answer users demands and, subsequently increase the network efficiency. Therefore, we look at the potential benefits of virtualization brought to CDNs. We tailor our state of the art to provide:

• A comprehensive state of the art on the traditional CDNs.

• Strength and weakness of different CDN services when used with different caching and replication algorithms including virtual ones.

• A new approach taking into account virtual content delivery networks through Network Function Virtualization (NFV) and Software Defined Networking (SDN) concepts.

CDN today is the result of many contributions that have improved the architecture and the design. So, we try to organize those contributions in a categorized way, easy to understand. Also, we include surveys of the most performing caching algorithms used in CDN systems.

The rest of this Chapter is organized as follows: Section 2.2 highlights the common architectures for CDN. Section 2.3 describes the main taxonomies of CDN. We study the evolution from CDN to virtualization aspects in Section 2.4 and the transition from physical cache to virtual ones with details about caching techniques. Finally, this chapter is concluded in Section 2.7. Those main components of a typical CDN can be defined as the following:

CDN overview

• Content delivery infrastructure [START_REF] Pathan | A taxonomy and survey of content delivery networks[END_REF]: It manages cache servers responsible for delivering the content to the end users.

• Request routing infrastructure: Its function is to redirect client's queries to the most appropriate CDN cache. Also, it interacts with the distribution infrastructure to make a global view of the up-to-date content stored in edge servers.

• Distribution infrastructure [START_REF] Pathan | A taxonomy and survey of content delivery networks[END_REF] Its function is to move content from the origin server to the CDN edge cache servers ensuring the consistency of cached data.

• In addition to the previous three plans, the accounting infrastructure [START_REF] Pathan | A taxonomy and survey of content delivery networks[END_REF] maintains the logs of client access and records the CDN server's utilization in order to prepare the billing records.

Several works have investigated the topic of content delivery networks. Peng et al. [START_REF] Peng | CDN: content distribution network[END_REF] gave an overview of CDN and introduced the encountered problems in building an efficient architecture. Further, they enumerated and proposed solutions to overcome such issues. Vakali et al. [START_REF] Vakali | Content delivery networks: Status and trends[END_REF] presented a survey on the CDN architecture and gave the benefits of CDNs. Dilly et al. [START_REF] Dilley | Globally distributed content delivery[END_REF] and Akamai [4] gave a state of the art of the existing CDN approaches. They also detailed the infrastructure of the Akamai network (currently, the most developed caching infrastructure)

and how it works. Kung et al. [START_REF] Park | Content networks: Taxonomy and new approaches[END_REF] proposed taxonomy for CDN classification and gave some proposed approaches for content aggregation and content placement.

Saroiu et al. [START_REF] Saroiu | An analysis of internet content delivery systems[END_REF] investigated CDN based on four content distributed systems:

HTTP web traffic, Akamai, Kazaa, Gnutella and they gave significant implication for large organizations. Honguk et al. [START_REF] Woo | A virtualized, programmable content delivery network[END_REF] proposed a virtualized, programmable content delivery network, in which the CDN is proposed as a service or on demand.

CDNs, sometimes also called Content Distribution Networks, are often deployed close to the end user when he makes data requests. Static content may be images, video, CSS files, scripts files, etc CDN customers are mainly Internet Service Providers (ISP) and Over the Top (OTT) service providers like YouTube and Netflix. They push the content to the edge servers over IP. Typically, they are looking to build a large farm of cache servers deployed worldwide in order to reduce the load on the OTT servers, reduce traffic overhead and provide the following services:

• Storage (popularity based)

• Management of cached content (i.e. cache management like replication, replacement, and placement)

• Distribution of content among cache servers (load balancing)

• Content Streaming

• Fault tolerance (i.e. Redundancy)

• Network performance (reduce overloads)

Taxonomy of CDN

CDN is considered as a center of many interests. The literature treats in priority the following aspects:

• CDN infrastructure and composition.

• CDN delivery and management.

• CDN request routing.

• CDN performance and user satisfaction.

CDN infrastructure and composition

Lazard and al. [START_REF] Lazar | Exploring content delivery networking[END_REF] introduced that CDN infrastructure can follow the overlay approach and cited CDNs deployed by companies as an example, i.e. using Peer to Peer (P2P) applications or an underlay of connected servers. In that case, the original content is always permanently stored in the underlay and copied on occasions to the dynamic substrate. We found several different compositions of CDN as shown in Table 2.1. Indeed, in the underlay method, caching nodes are centralized while in overlay method CDN can be assisted with P2P and other heterogeneous or decentralized methods. Further, we summarize the interaction between the different components of the CDN in two ways: either through the use of surrogates or through caching proxies.

CDN delivery and management

In this section, we investigated the issues of distributing CDN service to endusers and managing the delivery network. Thus, we are trying to study problems like replica placement, content selection in CDN, content outsourcing, content caching techniques, and content update.

Replica server placement

In this issue, CDN administrator decides on how and where he should deploy its own replica servers. In the literature CDN providers develop two main algorithms [START_REF] Vakali | Content delivery networks: Status and trends[END_REF] for determining the optimal number of replica server placement:

Single-ISP and Multi-ISP algorithms. In the second case, it is a multi-criteria optimization problem that may be difficult to solve.

Content selection

The selection of content targets to be copied is an important issue in CDN as it affects cache efficiency. Two approaches are proposed: full site and partial site approaches. In full site case, the replica server is responsible for delivering the entire content to the end users. In partial site, replica servers are responsible only for delivering the embedded object such as web page images. It is useful when the partial content is static (such as commercial catalogs).

Content outsourcing

The process of outsourcing content in CDN can be invoked after the decision about how many servers will be deployed and after the selection of content to be copied. Content outsourcing can be achieved through three methods: cooperative push based, cooperative pull based and non cooperative pull based:

• In Cooperative push based, content is pushed to the overlay network and user requests are redirected to the closest replica server or served directly by the origin server (in the case that there is no content replication in CDN overlay network) [START_REF] Kangasharju | Object replication strategies in content distribution networks[END_REF], [START_REF] Fujita | Coarsegrain replica management strategies for dynamic replication of web contents[END_REF], and [START_REF] Cheng | A framework for lazy replication in p2p vod[END_REF].

• In Cooperative pull based approach, content requests are redirected to surrogate servers and when there is a cache miss, replica servers cooperate to serve the end user by the desired content based on distributed index structure such as Distributed Hash Table (DHT) [START_REF] Michael | Democratizing content publication with coral[END_REF].

• In the Non cooperative pull based approach, after one of the following algorithms of request routing (DNS based algorithm, HTTP based algorithm, URL based algorithm), user requests are redirected to their closest replica servers. The main difference between this method and the previous is in case of cache miss. In this method, there is no cooperation between cache servers and replica servers to pull the desired content directly from the origin server [54] [133] [START_REF] Johnson | The measured performance of content distribution networks[END_REF].

Caching techniques

In caching, we highlight two main approaches: content replication and content update mechanisms. Those techniques are considered as the main role of any CDN network and they define its performance. • In Inter-cache approach, we need an inter-routing between different clusters (group of caches).

This algorithm is invoked when the content does not exist in the current cluster. We will detail in the next section the caching techniques in video service delivery.

2. Caching content update [START_REF] Peng | CDN: content distribution network[END_REF]: The update process is based on content expiration time (eg., Time-to-Live (TTL)). Four algorithms have been proposed

for content updates which are periodic update, update propagation, on demand update and invalidation. In periodic update, content is pushed automatically with a time to live. After time expiration, surrogates must check back the origin server. This approach suffers from high traffic requirement since the update process is static. In update propagation, origin streaming servers deliver always the updated content whenever a video document has been changed. This mechanism generates high update traffic for frequently changing video content. In on demand-update, video document is updated after a prior user demand. The drawback of this cache update mechanism is the excess traffic generation between the surrogate and the origin server in order to ensure that origin server has delivered the updated version of the video content. The latest cache update mechanism is invalidation in which origin server broadcast an invalidation message to all surrogate servers when a video content is changed or updated at the origin server. The disadvantage of this approach is that cache nodes have to seek for an updated version of the video individually after that video has been changed. This mechanism suffers also from inefficiency of content management and coherence among cache nodes.

Table 2.2 summarizes the most important management and delivery issues in CDN as mentioned before.

CDN request routing issues

Request routing redirects content requests from users to the nearest or best replica server based on load, capacity, and other metrics. In the literature, several In [START_REF] Jiu | Content delivery network and its regulation[END_REF] authors showed that the proximity factors used for serving clients don't always give the best performance. Hence, load and context information should be considered before switching to a replica server. Recall from the management of content that there are two ways of replication: full and partial site replication. If we use the first approach, the origin server redirects the content requests to the replica server. In the other approach, the origin server sends basic and embedded objects to the replica server and the latter redirects the response to the client.

Request routing systems have two parts:

• Request routing algorithm: how to choose the replica server after that a content provider receives a content request from the client.

• Request routing mechanism: the protocol, procedure or steps to inform the client (user) about the chosen replica server.

In Table 2.3, we show the related issues of CDN request routing procedures to redirect user requests to the optimal (nearby) CDN server.

Request routing algorithms

The main request routing algorithms are enumerated as follows:

1. Adaptive algorithms: The major request routing algorithms found under this technique are: • Round Robin Algorithm (RR): In this algorithm [START_REF] Szymaniak | Netairt: A dnsbased redirection system for apache[END_REF], requests are distributed to the CDN replica servers and each replica has a maximum load for serving requests. Authors showed that this approach assures load balancing, assuming a similarity among all the CDN replica servers (same capacity, same storage, etc...). This approach has a lot of disadvantages because it does not take into account the distance among replica servers and users. Further, authors in [START_REF] Vivek | Locality-aware request distribution in cluster-based network servers[END_REF] showed also that through RR algorithm, client may be served by more distant CDN while the nearest replica server was not loaded. Hence, we conclude that RR algorithm fits well when all the replica servers are in proximity (i.e., replica servers form one cluster).

• Predicted Load Algorithm: Predicted load is based on the number of requests on server recently served (served so far). This algorithm assures load balancing (load is distributed among replica servers) taking into consideration the distance between the client and the replica. Therefore, load and distance are the two essential metrics used in this algorithm [START_REF] Sivasubramanian | Replication for web hosting systems[END_REF].

• Random Request: In this algorithm, content provider redirects randomly content requests to replica servers [START_REF] Delgadillo | Cisco distributed director[END_REF].

• Statistics based redirection: In this algorithm, we calculate the percentage of client's request per CDN. Then, we always redirect content request to the CDN which receives the greatest request number [START_REF] Delgadillo | Cisco distributed director[END_REF].

• Geographic location: K. Delgadillo [START_REF] Delgadillo | Cisco distributed director[END_REF] 3 mentioned that some Cisco algorithms found in the literature are based on the geographic location of the request origin. In this approach, the redirection to a replica server is based on minimum distance between the provider and the consumer.

However, the process of redirecting the user's content request to the closest CDN replica server is not effective because close replica servers may be overloaded. Moreover, when serving cellular users (smart phones, tabs, etc), the origin IP address does not reflect the real mobile location.

• Hash function based algorithm: In [START_REF] Karger | Web caching with consistent hashing[END_REF] authors Proposed a hash function based solution for redirecting requests to replica servers. In their approach, they calculate the hash function of the URL of the content and then redirect the request to the replica server represented by the ID which is larger than the calculated hash function. This algorithm has many variations in P2P file sharing algorithms [START_REF] Balakrishnan | Looking up data in p2p systems[END_REF] and intra cluster caching [START_REF] Ni | Large-scale cooperative caching and applicationlevel multicast in multimedia content delivery networks[END_REF] [92].

Non Adaptive algorithm:

In the literature we can find several works that investigated non adaptive request routing algorithms:

• Network proximity: Pierre et al. [START_REF] Pierre | Globule: a collaborative content delivery network[END_REF] described an algorithm based on network proximity to redirect user requests to replica servers [START_REF] Broberg | Metacdn: Harnessing 'storage clouds' for high performance content delivery[END_REF]. They measure the path length and update it periodically. This approach based on the distance as a metric is not really effective as explained in [START_REF] Lazar | Exploring content delivery networking[END_REF].

• Latency: Andrews et al. [START_REF] Andrews | Clustering and server selection using passive monitoring[END_REF] and Ardaiz et al. [START_REF] Ardaiz | Improving the service time of web clients using server redirection[END_REF], proposed algorithms based on the measured latency between the provider and client. In those approaches, client requests are redirected to the replica server reporting minimum latency to users. This algorithm is very efficient but it requires extensive measurements.

• Weighted combination of latency and distance: Delgadillo et al. [START_REF] Delgadillo | Cisco distributed director[END_REF] in-troduced also a combination of three metric called: intra AS distance, inter AS distance, and end to end latency, to decide for the best target.

The measurement of those metrics makes the algorithm more complex since it adds an additional signaling traffic.

• Akamai algorithm: Peng et al. [START_REF] Peng | CDN: content distribution network[END_REF] And Vakali et al. [START_REF] Vakali | Content delivery networks: Status and trends[END_REF], proposed an adaptive request routing algorithm based on three metrics: load on the replica server, reliability between client and all the replica servers and bandwidth remaining on the replica server. Akamai's algorithm is complex but robust.

Request routing mechanisms

The Request routing mechanisms found in the literature are as follows:

1. Global Server Load balancing (GSLB): In the Global Server 4 mechanism, a group of GSLB switches distributed around the world are responsible for redirecting user requests to a web server in order to assure load balancing among replica servers. streaming receive (steps 9 and 10). In this way there is no dependency for the request routing process with a user's location information to select the Cache Server which is a the most important disadvantage as user may be far from the streaming point.

HTTP based request routing:

In HTTP based request routing 5 , clients send their requests to the web server. Then, through the HTTP protocol, the origin server redirects the client queries to another server holding the content.

This algorithm incurs some latency because of the many round trips between user, HTTP web server, and replica server which influence the quality of experience. Therefore, user's satisfaction can decrease. It is however the mostly used in video delivery. approach needs an extra space of IP addresses, and suffers from routing performance issues (because the anycast) that should be considered for request routing.

5. URL rewriting request routing: URL approach also called navigation hyper link, origin servers redirect content requests to different replica servers holding the embedded object. In this process, URL links of embedded object (images, CSS files, scripts) are dynamically rewritten and generated. Clients are then redirected to those surrogates. This algorithm is adapted to partial site content delivery in which origin server serves the original HTML page while the embedded content is retrieved from the cache servers. Youtube uses a routing technique close to this approach. CDNs is built in order to serve content to the end user. This approach can be considered as a CDN assisted with P2P overlay network. The goal of this algorithm is to increase fault tolerance and decrease the latency. However, since it is a distributed algorithm, it suffers from scalability and churn problems.

CDN performance and user satisfaction

The performance measurement of the ability of CDN to serve their customers is based on Hardware and software probes or on CDN's logs. Clients when requesting for a video, generate a feedback from the overlay infrastructure andn precisely from the CDN replica servers that indicate CDN performance measurement. Table 2.4. shows the related issues of CDN performance.

We deduce from the investigated state of the art that performance measurement can be achieved either through network procurement (collecting) or through simulation.

Network procurement

In network procurement, performance measurement uses either dependent or independent replica servers that collect the required metrics. In dependent replica servers, the surrogate server is equipped with a process calculating end-to-end metrics. This can be done either by the collection of the logs from the surrogate servers or through the deployment of probes (Hardware or software). In inde-pendent replica servers performance measurement is achieved by an independent third party that tells clients about the CDN replica servers performance.

In Network procurement, performance is based on the estimation of some metrics such as startup time, time to first byte, server load, jitter, geographic location, and packet loss. More sophisticated metrics can be subjective such as user engagement (i.e. duration of the video viewing by the end-user).

Simulation

In addition to the use of network procurement for measuring network and system performance, researchers resort to simulation tools to measure the performance of CDN because of the proprietary nature of commercial CDNs. Furthermore, many simulation tools are available to measure the performance of CDN [START_REF] Cheng | A framework for lazy replication in p2p vod[END_REF] and [START_REF] Kangasharju | Object replication strategies in content distribution networks[END_REF]. The use of these tools has some advantages such as the simplicity and the flexibility of implementation in analysis of results. However, those results may be unrealistic since the simulation tools do not take into consideration all the critical factors.

Network evolution from CDN to vCDN

As our thesis concentrates on virtualization and server optimization, and after investigating the state of the art of CDN, we found that CDNs can be additionally divided into two categories: physical CDN and virtual CDN:

• Physical CDNs: Physical CDNs are divided into commercial and academic development based CDNs. For the commercial CDNs we have Akamai [4],

Accellion [2], Lime Light Networks, Appstream, Globix and EdgeStream. For the academic CDNs we must mention CoDeeN [START_REF] Codeen | [END_REF], COMODIN [START_REF] Comodin | [END_REF], Coral, and Globule. Physical CDNs have many service types such as file delivery, network service, and video streaming service (live and on demand video) and so on.

• Virtual CDNs: In the literature we have few contributions on CDN assisted with cloud and network virtualization. We have MetaCDN [START_REF] Broberg | Metacdn: Harnessing 'storage clouds' for high performance content delivery[END_REF] based on edge cloud servers and Active CDN [START_REF] Suman Ramkumar Srinivasan | Activecdn: Cloud computing meets content delivery networks[END_REF] based on edge servers as software modules.

Caching taxonomy for video delivery In the literature, we found many researches and contributions that focus on caching service in order to enhance the performance of the network. For multimedia and video applications, network performance is a function of several parameters such as: video popularity, complexity, congestion, video size, hit rate, quality of experience, cache replacement algorithm and cache update mechanism. According to these metrics, we will compare the work of the state of the art detailed in the two Appendixes A and B. So to virtualize the CDN, we believe that the process can be achieved through one of the following techniques: cloudification, virtualization, and programmability.

Virtualization of CDN

Cloudified CDN

In CDN based cloud computing approach we quote MetaCDN [START_REF] Broberg | Metacdn: Harnessing 'storage clouds' for high performance content delivery[END_REF] that used an existing cloud infrastructure to deliver video service to end users. It implements several CDN services in the cloud to enhance the delivery process such as replication strategies, load balancing etc. However, it still uses preconfigured and physical edge servers deployed on cloud infrastructure through Infrastructure as s Service already deployed in an OpenStack open source project (IaaS).

Further, we cite ActiveCDN [START_REF] Suman Ramkumar Srinivasan | Activecdn: Cloud computing meets content delivery networks[END_REF] that uses the same previous cloud computing architecture to virtualized CDN service such as caching and acceleration techniques mainly for video delivery purpose. However, edge servers in this cloud computing approach are software based solutions. Those network functions are dynamically deployed on CDN caching nodes. The advantage of this approach is that it facilitates the removal, adding and changing of network functions through cloud monitoring systems.

CoDaaS [START_REF] Jin | Codaas: An experimental cloud-centric content delivery platform for user-generated contents[END_REF] is another solution to enable the virtualization of multimedia services and CDN network function. Further, it lets end users to generate their contents into the cloud. Furthermore, content providers rent a part of the cloud resources such as bandwidth, storage, and so on so as to host their contents in the cloud. This approach is better in the direction of user involvement for service video delivery. Florian et al. [START_REF] Dudouet | A case for cdnas-a-service in the cloud: A mobile cloud networking argument[END_REF] proposed a virtual architecture for implementing CDN services in the cloud environment. The main disadvantage is that CDN as a service proposed in their work missed more features like dynamic management of virtual CDNs, routing policy, and so on.

Tai-Won et al. [START_REF] Um | Dynamic resource allocation and scheduling for cloud-based virtual content delivery networks[END_REF] proposed cloud based virtual CDN architecture. They proposed a control plane formed by a cloud broker that configures a set of virtual machines (vCDNs). In their approach, content providers deliver their content to end users through a virtualization layer. Therefore, they proposed some entities in the control plane to monitor the virtualization layer and fulfill the service level agreement (SLA) needed for achieving media delivery service. We can conclude that these proposals are all cloud oriented CDN solutions strongly dependent on a cloud infrastructure.

Virtualized CDN

In this section, we illustrate the few works that have been done for CDNs based on virtualization (NFV) concepts.

Honguk et al. [START_REF] Woo | A virtualized, programmable content delivery network[END_REF] describe a new strategy for cache deployment. They propose a hierarchical tree structure for virtual content distribution network systems.

It is based on a tree construction algorithm. It can reduce content distribution times and minimize source streaming data rates by dividing the network in levels: level1 for local cache and level2 for regional cache. The disadvantages of their strategy are multiples: first of all, they do not give a clear concept for the virtualization. Secondly, the algorithm used for content chunks diffusion is static and do not take into account content popularity or size. Thirdly, it requires a lot of computational overhead since content are streamed per chunk without any consideration of content chunk size.

Niels et al. [START_REF] Bouten | Towards nfv-based multimedia delivery[END_REF] provide a framework for multimedia delivery (CDN) based on NFV. They gave a structure of the point of presence, PoP deployment within the network. They used layers (core network, aggregation layer, access layer) to seek for the optimal location of cache nodes. Their work missed an optimization algorithm to measure the QoS/QoE. Further, they don not take into consideration the cooperation between CDN edge servers to serve user requests. Also, the optimization equation missed a lot of constraints such as the maximum server storage and the migration of content from one server to the optimal one.

In ETSI [START_REF].1. Network functions virtualization (nfv); use cases[END_REF], authors introduced the virtualization of CDN (vCDN) by giving a principle of different distributed cache nodes deployment in the virtual environ-ment. However, the overall architecture of vCDN containing the request routing system, the content management, the distribution system, and the accounting system are still missed in this conceptual architecture.

Mangili et al. [START_REF] Mangili | Stochastic planning for content delivery: Unveiling the benefits of network functions virtualization[END_REF] I. Trajkovska et al. [START_REF] Georgopoulos | Towards network-wide qoe fairness using openflow-assisted adaptive video streaming[END_REF] leverage SDN to build their management framework in order to enhance the overall QoS of the delivery process. They showed that SDN paradigm enhances network management for video service delivery and brings flexibility and programmability to the route calculation while considering the QoS.

Moreover, they used a control algorithm based on bandwidth metric calculation.

The proposed approach has to take into account the QoE parameters which is necessary in video streaming and it missed different SDN/NFV criteria such as node throughput, service orchestration, and so on.

P. Georgopoulos et al. [START_REF] Georgopoulos | Towards network-wide qoe fairness using openflow-assisted adaptive video streaming[END_REF] introduced the OpenFlow protocol assisted with QoE Fairness Framework (QFF) in order to optimize the overage QoE of end users connecting to the home networks. Their framework considers monitoring the video delivery service. Therefore, they take into account the gathered network information and end users profiles in order to build their QFF. In their implementation, they used two standards for audio visual content delivery and management resources in network operators which are OpenFlow and MPAG-DASH. In their work, there is no correlation between the video bit rate and the QoE perceived by the end user. To optimize the efficiency of the network and assure a high QoE, authors proposed a new framework in which they quantified the non-linear mapping between the perceived QoE and video bit rate through an utility function.

Indeed, the utility function used is an exponential curve which binds a video bit rate at a fixed resolution to a perceived QoE. Moreover, they used an objective video quality assessment models (SSIM) in order to build the utility function. For the optimization function used in their work, they exploited the utility function in order to find the optimum set of bit rates that assure QoE Fairness requirements.

Further they added two exact optimization algorithms called promote in order to upgrade user with the minimum video quality. In their proposed approach, the utility function does not cover the context parameters but it is based only on video bit rate. Moreover, the approach does not involve the NFV QoE context.

H. E. Egilmez et al. [START_REF] Egilmez | Openqos: An openflow controller design for multimedia delivery with end-to-end quality of service over software-defined networks[END_REF] described a new approach for design an SDN controller in order to enhance the multimedia delivery process. They introduced a novel QoS method relying on dynamic routing from the server to the customer. The approach aims to assure the required network performance for multimedia traffic. Beside the IntServ and DiffServ QoS architecture, SDN approach

Conclusion

This chapter has surveyed research investigated on content delivery systems, mechanisms and algorithms. We classified and detailed the most important CDN systems. Further we followed the evolution of CDN to be virtual (vCDN). We classified then the most important caching techniques in both real and virtual CDNs.

Then we surveyed the virtualization of CDNs. We may conclude that the virtual delivery area is active and supports different caching techniques. There are still many unresolved issues dealing with caching, request routing, streaming and link utilization techniques. To date, and based on the CDN-NFV architecture proposed by the ETSI, aspects such as mobility or routing require extra attention and lack communications protocols.

In the next chapter, we are going to highlight the virtualization challenges in vCDN deployment using an open-source cloud platform.

Chapter 3

Network issues for vCDN migration

Introduction

The virtualization of resources has addressed the network architecture as a potential target. The basic tasks required in the virtualization substrate are instantiation of new network functions, migration and switching. These basic tasks are strongly dependent on the underlying network configuration and topology in a way that makes them tributary of the network conditions. It means that sometimes it will not be possible or not recommended to accomplish some virtualization tasks if the network is not presenting the minimum requirements. This brings back many déjà vu questions to networks theory but the answers to these questions require an understanding of the new context.

Most of the virtualization architectures such as NFV included in the SDN paradigm are relying on these tools to implement their technical solutions.

In this chapter, we consider the migration of network functions and we study problems that arise from this dynamic process. We present a specific use case for content distribution of multimedia services: CDN.

The rest of this Chapter is organized as follows: Section 3.

NFV, SDN and OpenStack

We investigate the state of the art of the recent networking technologies that can meet the virtualization domain. The main architectures used for that purpose are Network Functions Virtualization (NFV), Software Defined Networking (SDN) and OpenStack.

Network Functions Virtualization

NFV [START_REF] Han | Network function virtualization: Challenges and opportunities for innovations[END_REF] virtualizes the network equipment (Router, DPI, Firewall, etc). We

will not discuss about hardware. We will rather consider software based NFV architecture. It is a concept that decouples network functions from its underlying hardware. Then, it enables the software to run on virtualized generic environment.

Therefore, several virtual appliances can share the single hardware resources.

NFV brings several benefits [START_REF] Hawilo | Nfv: state of the art, challenges, and implementation in next generation mobile networks (vepc)[END_REF] such as reducing CAPEX and OPEX, promoting flexibility and innovation of the virtual network functions already implemented. Moreover, it has been introduced as a new networking facility that poised to amend the core structure of telecommunication infrastructure to be more cost efficient.

In a virtualized environment, the physical resources (CPU, Storage, RAM, etc.) are emulated and the guest operating system runs over the emulated hardware (vCPU, vRAM, vStorage) as if it is running on its own physical resources. By this virtualization, all the virtual machines share simultaneously the available resources.

This virtualization is based on deterministic framework which is constituted of three main components:

• Host machine: It is the physical machine (physical server) that owns the hardware's resources (CPU, RAM, Storage, Input output interfaces, etc.)

• Hypervisor: It is the controller of the virtual machines that controls their instantiation, dynamic migration, scaling in/out, etc.

• Guest machine: It is the virtual machine or the virtual appliance that is running and attached to the hypervisor.

The standardization of NFV began with ETSI and some use cases described in [START_REF].1. Network functions virtualization (nfv); use cases[END_REF]. The main use cases found are:

• Virtualization of the Radio Network Interface: In this approach we separate the digital function of the radio named Base Band Unit (BBU) from the underlying antenna hardware and distribute the Remote Radio Unit (RRH). The virtualization can be done in a data center that communicates with the RRH distributed functions through optical back-haul networks (optical fiber) in order to accelerate the resource allocation.

Bhaumik et al. [START_REF] Bhaumik | Cloudiq: A framework for processing base stations in a data center[END_REF] gave an important result utilizing cloud RAN in which they virtualized the BBU and distribute RRU units. They reported that Cloud RAN can decrease the network load by 22%.

• Virtualization of the Home Network: The virtualization of the home network includes the virtualization of the two main components: Residential Gateway and Set-Top Boxes that offer home services (internet access, multimedia service, etc.) to end users. This approach is based on implementing virtualized and programmable software based NFV solution such as: firewalls, DHCP servers, VPN Gateways, DPI Gateways. Then, move them to data centers in order to decrease the cost of devices and increase the QoS.

• Virtualization of Evolved Packed Core (EPC): In this use case, the virtualization targeted several functions such as: SGW, PGW, MME, HSS, and PCRF [START_REF] Han | Network function virtualization: Challenges and opportunities for innovations[END_REF]. The virtual EPC (vEPC) will include all the above functions as

Software Defined Networking

SDN [START_REF] Basta | Applying nfv and sdn to lte mobile core gateways, the functions placement problem[END_REF] is a networking concept that shares the same goals of NFV in the direction of promoting innovation; openness and flexibility. We emphasize that they are independent but complementary as explained in [START_REF] Jammal | Software-defined networking: State of the art and research challenges[END_REF].

It is characterized by the separation of control plane and data plane and consolidates the control plane in one logical centralized controller to decrease the network overload and increase enhancement the traffic engineering by adding policy and rules to devices enabled OpenFlow protocol.

It can be considered as a tool for traffic engineering to enhance the QoS and meet network issues following the integration of virtualization functions. SDN based on OpenFlow protocol can be used to direct the forwarding layer formed by Open Flow enabled devices such as OpenFlow Switches.

As shown in Fig. 3-1, the multimedia service delivery has evolved three times:

• Phase I: The operators adopt the Best Effort (BE) in service delivery from content providers to clients according to the available bandwidth and without any regards to delay issues, users' satisfaction or perception for QoE (i.e.

no control for QoS).

• Phase II: The operators use the CDN solution to cache the multimedia very near to the clients by using CDN network acceleration. In this phase, there is a remarkable enhancement in service delivery while still some restrictions remain between customers and content providers.

• Phase III: The operators aim to redirect the required services from content providers to selected network locations giving to clients good perception in QoS or QoE measures. In this phase, there is an application layer tunneling defined by SDN (QoS/QoE perception model) [START_REF] Tourad Diallo | Utility-based Approach for Video Service Delivery Optimization[END_REF].

Our concern in this chapter is to benefit from these complementarities in order to virtualize and migrate the multimedia network functions across hosts. Moreover, we aim to gain the advantages of scalability and cost reduction in a dynamic controlled service delivery context. We focus in this work on the mobility issues that arise when achieving the multimedia network function migration.

Mechanism of SDN in video service delivery

SDN will lead to Software Defined Data Centers (SDDC) where the roots of streaming points dynamically move. This dynamic adaptation will pass through 4 phases as follows:

• Resources Virtualization: It concerns the different resources needed during virtualization including bandwidth, system (memory, CPU, I/O).

• Roots & Links Virtualization: The virtual resources gathered and calculated in real time for the virtual node inserted among different nodes in the original tree of operators' networks.

• Network Virtualization: It is a kind of dynamic networks or nodes on demand to serve as streaming points.

• Flow Virtualization: It is a mapping of original root flows to the new elected roots through SDN tunnels between the old root and virtual root to new ones. However the main components of OpenStack are: Nova, Glance and Swift.

Glance service is the creator of image disks and Swift project is the manager of the storage in the private cloud (the equivalent of S3 service in Amazon EC2 project).

OpenStack has also an orchestrator module (Heat) that manages the virtual network functions (VNFs) in NFV based Framework. Their components are well cooperating so as to achieve dynamic instantiation of VMs in the container (VNF) through "Nova" module which is the most important service in this project. It included also Keystone which the Manager of the identity.

Network constraints in virtualization

We study mobility in the virtualization process. Several basic requirements are necessary before any virtualization procedure can take place. We think that QoS, mobility support and security are among the most important issues to be addressed:

3.3.1 QoS
This parameter is vital. Any virtualization process consumes in its transient state a huge amount of resources. Instantiation or migration of a VM requires very high speed links. Slow links do not only render the virtualization very hazardous but can simply make it impossible to accomplish. QoS is required in many situations. It is to be mentioned that virtual machine migration as of today is not optimized and very trivial approach where everything is copied from the origin to the destination. Hence, we can expect up to 90 % of the copied material is unnecessary because it is unchanged. We expect that efforts in live migration will be done to optimize what is being copied. The QoS of the link can hence be a decisive constraint on whether to migrate or not.

Mobility

Mobility of virtual instances is not a simple task. We can consider moving an NF or a complete instance of a server depending on the desired controller objective. So, from the operating system perspective, there will be a virtual machine, a process, a thread or a session migration as a result of this mobility. As explained before, moving a functionality is required when we want to create a new service in a different location. Off-loading, QoS improvement, interface management [START_REF] Barabasi | Emergence of scaling in random networks[END_REF] etc. may be the reasons for this mobility. When we consider moving a complete virtual machine, it is mainly for load balancing but can also have other reasons such firmware/OS upgrade, instantiation of a new service for a new customer, etc.

Security

Security is an important aspect in VM migration. Many attacks could stop the live or offloading migration at any point. Moreover, a large amount of tunnels has to be setup and configured leading to very load efficiency and redundancy.

So, securing this migration either in single domain or inter multiple domains is mandatory. Tools such as OpenStack do not authorize all the possible operations when different domains are involved. This could present a limitation in real deployment.

Networks issues for virtualized network function's mobility

Virtualized network functions need for an added network requirement in order to assure session moving, open session and live session migration. For basic knowledge, if a virtual machine that resides on a given network, obviously executed as a process, changes the network; it suffers from the continuity of the sessions offered to users which have connected to it. This of course is due to change of VM's IP.

Therefore, we must address this issue to ensure the continuity of the session after the migration of the virtual appliance to a remote host and a remote Hypervisor.

Hypervisor overview

The hypervisor is the virtual machine monitor that controls virtual machine issue and specially network issues of VM and during the live migration process. It allows to move virtual machines between different domains. Among the famous hypervisors, we cite VMware [START_REF] Mishchenko | VMware ESXi: Planning, Implementation, and Security[END_REF], Xen [START_REF] Barham | Xen and the art of virtualization[END_REF], Qemu [START_REF] Bellard | Qemu, a fast and portable dynamic translator[END_REF], and VirtualBox [START_REF] Dash | Getting Started with Oracle VM VirtualBox[END_REF] etc.

In this chapter, we use two tools to design our optimizing network function.

Qemu is first tested as an open-source hypervisor that can monitor the running virtual machine and deal with virtualization tools that can't be used in another virtualized environment such as KVM. We developed also a special tool for optimized migration based on OpenStack services [START_REF] Tamayo-Ibnkhedher | vios (virtual infrastructure optimization simulator)[END_REF]. using linear optimization [START_REF] Ibn-Khedher | Omac: Optimal migration algorithm for virtual cdn[END_REF] and [START_REF] Hatem Ibn-Khedher | Opac: An optimal placement algorithm for virtual fCDNg[END_REF].

The aforementioned hypervisors enabled VM live migration with continuity of the running service. However, they missed several requirements for assuring live migration and open session. Those requirements are mainly concerning IP mobility when VMs migrate from source host to destination one as it is explained in [START_REF] Awerbuch | Greedy distributed optimization of multi-commodity flows[END_REF] and [START_REF] Awerbuch | Distributed algorithms for multicommodity flow problems via approximate steepest descent framework[END_REF].

Q. Li at.al [START_REF] Li | Hypermip: Hypervisor controlled mobile ip for virtual machine live migration across networks[END_REF] introduced that mobility issue can be controlled either by the VM itself, by the host machine (or any intermediate network node) or by the hypervisor. We will focus on those ways of enabling and controlling IP mobility when

VMs migrate from one host to another and prove that the best way to control IP mobility is by the hypervisor.

In [START_REF] Kalim | Seamless migration of virtual machines across networks[END_REF], Kalim et al. introduced another approach to migrate virtual machines between different sub-nets. In their work, they decouple IP address from TCP transporting layer and enabling transport independent flow in order to solve mobility issues and network configuration problems when migrating VMs. This approach describes the requirements and the mechanisms used. However, it misses the description of live migration scenarios that still remain unclear in their prototype.

In live migration processes any of the VM or the network nodes knows the exact time of migration and the destination host. VM can't discover that the hypervisor on which it attached to the network has been changed after the migration. Therefore, the mobility problem in live migration can be easily resolved by letting the hypervisor do this work.

Basic concepts for MIP enabled live migration

The basic components in our conceptual architecture are the customer or the client, the home agent and the home node, the foreign agent, the Hypervisor (Qemu in our case) and the correspondent node. We keep the basis component names as in traditional Mobile IP Protocol (MIP). Fig. 3-3 shows the four steps for latter keeps alive its session without any interruption.

Networking system design

In our basic architecture, several virtualization tools were used in order to implement network functions and run on a virtualized environment. Fig. 34showed our networking scheme which relies on QEMU/KVM assisted by Libvirt daemon.

Those tools manage the running VMs and their issues. The networking scheme used with virtual managers is based on Network Address Translation (NAT) for connecting virtual machines to the physical host. Each VM has emulated interfaces by which they are differentiated. In Fig. 345, we show a simple scenario of live VM migration without context transfer. In this scenario, once the virtual machines are executed, the two physical machines share the same disk image.

In Fig. 3-6, we describe a more complex scenario: live migration of a network function with context transfer. Before the migration process, the migrated VM through the hypervisor transfers memory pages and the total disk to the remote host. After the Disk transfer, the hypervisor transfers the virtual machine context (storage, plug-in, packages, libraries, etc.) to the remote host. We have focused on network issues that we have faced in live migration in order to more understand the context transfer between the interacted physical and virtual machines. Some system and networking issues are evaluated in this paper.

We reported that live migration of running virtual machines needed much more We evaluated some experiment measurements basically related to network parameters such as: link speed that must be higher than 1Gbit/s, live migration time that is not significant with shred storage (4s) and without video session interruption in the case that we moved streaming point from one host to another.

Missed for live session

Coping memory pages

CDN use case 3.5.1 CDN

CDN is a large distributed network deployed worldwide in order to push content on the edge of the network. It was the solution of two major problems that decreased the performance of the network: congestion within the core network and overload at the origin server. It is often used to host static content so that they will be close to the end user when he made his request for online video streaming. In Fig. 345678, we show our hybrid solution that merges the two former virtual architectures to virtualize and program CDN software. In fact, we keep the design of vCDN based NFV solution and we add the SDN paradigm to control the virtual edge servers (vCDN nodes) based on NFV solutions rather than dedicated hardware.

We conclude this section with a performance comparison for the vCDN solutions against classical ones in Table 3.2.

Conclusion

In this chapter, we highlighted the impacts of main network parameters and criteria in the live migration process. We proposed some network virtualization concepts like SDN, NFV and OpenStack. We detailed network issues of VM migration in different scenarios. We concluded that NF context should be transferred for full VNF migration and open session. Virtualized network functions can be dynamically instantiated and migrated in a virtual environment but they need for high requirements to achieve the full context transfer and full virtualization. We explained also a use case of vCDN for multimedia service objective.

In the next chapter, we propose vCDN protocol using the aforementioned virtualization techniques. Then, we contribute by an optimization module that recommends optimal placement points where to instantiate vCDN nodes.

Chapter 4

OPAC: Optimal Placement Algorithm for virtual CDN

Introduction

Content Delivery Network (CDN) targets the deployment of multimedia content (images, files and videos) over multiple data centers through Internet Service Providers (ISPs). The main goal of a CDN is to serve content to the end users with better availability and higher performance [START_REF] Johnson | The measured performance of content distribution networks[END_REF] and [START_REF] Pallickara | Enabling hierarchical dissemination of streams in content distribution networks[END_REF]. It is also proposed to ISPs as an offloading solution for intra and inter data centers updating [START_REF] Frank | Pushing cdnisp collaboration to the limit[END_REF]. i) a content replication plane: it is the system responsible for content caching, streaming and distribution. ii) a request routing plane: it is the system responsible for redirecting end-user requests to the optimal surrogate server, and iii) a CDN management plane: it the centralized system responsible for cache management processes such as content eviction, placement, etc.. and it does the accounting and billing tasks. Moreover, this network can perform many file management actions like hosting/caching/fetching/swapping in order to satisfy the client's Quality of Experience (QoE) and enhance the overall Quality of Service (QoS) of the network [START_REF] Haílinger | Content delivery and caching from a network provider's perspective[END_REF].

77 In video streaming systems either live-streaming or on-demand services, the CDN placement is a key point in delivery optimization. In [START_REF] Tourad Diallo | Quality of experience for audio-visual services[END_REF], the video adaptation was considered in terms of users' perception (user experience). In [START_REF] Mamadou | A hybrid contextual user perception model for streamed video quality assessment[END_REF],

authors focused on the contextual QoE metrics and their effects on data retrieval or caching costs. The overall performance especially in video services cannot be only based on user perception models. In fact, major deployed data centers over the Internet such as Akamai [4], Amazon [START_REF]Amazon cloudfront[END_REF] or Google [START_REF] Koley | Software defined networking at scale[END_REF] have to consider other important parameters. Besides financial issues that are out of our scope, we claim that system and core network parameters are key issues in making content movements over the networks. To the best of our knowledge and despite the existence of placement techniques deployed by the above mentioned providers, the literature lacks optimization algorithms that take into consideration actual system, network, and quality parameters. In fact, each technique is based on a single criterion optimization.

Architectures for virtualizing network functions such as Network Functions Virtualization (NFV), Software Defined Networking (SDN) and OpenStack1 can add flexibility to the design of network applications as investigated in [START_REF] Luis | Operational, organizational and business challenges for network operators in the context of sdn and nfv[END_REF], [START_REF] Jain | Network virtualization and software defined networking for cloud computing: a survey[END_REF], [52], [START_REF] Wood | Toward a software-based network: integrating software defined networking and network function virtualization[END_REF], [START_REF] Martins | Clickos and the art of network function virtualization[END_REF], [START_REF] Matias | Toward an sdnenabled nfv architecture[END_REF], [START_REF] Farhady | Software-defined networking: A survey[END_REF], and [START_REF] García-Valls | Challenges in real-time virtualization and predictable cloud computing[END_REF]. They used a prioritization method to solve the multi-objective optimization problem which leads to sub-optimal results especially when the cost functions are orthogonal as in their case. Moreover, authors didn't take into consideration the virtual RAM which is most important virtualization parameter especially in service migration among virtualized launched instances.

Authors have not properly configured the latency constraint in the core layer (it should be lower than the remaining network layers). Furthermore, the problem was resolved through a math-heuristic algorithm assisted by a prioritization method which has several limitations such as non-optimal cost analysis. Literature lacks an optimization algorithm that introduces at the same time system, network, and user quality parameters. Moreover, none of the above work introduced a placement and/or migration protocol for virtual content delivery network functions. Hence, we contribute by OPAC protocol and optimization model.

OPAC: design concepts

We present an efficient solution for optimizing video streaming delivery according to the proposed system design. We build our system based on the SDN paradigm assisted with traffic engineering rules using Network Function Virtualization Infrastructure (NFVI presented in ETSI standard [START_REF].1. Network functions virtualization (nfv); use cases[END_REF]). We apply virtualization on content delivery networks.

NFV concept is used here to virtualize the CDN components (cache/stream nodes and a request router node) while SDN paradigm is used for controlling the behav- As shown in Fig. 4-3, OPAC is used for managing and orchestrating vCDN as a service. Further, the vRR proposed here is able to redirect user's requests to the optimal vCDN streaming node. Hence, once user requests are directed to the CDN server (VNF), the latter redirects the request to the optimal vCDN relative to the user location and other algorithm parameters.

The event sequence is that a Content Provider (CP) asks the network operator (virtualized CDN provider) to perform a cache process for its videos (referenced by URLs). URLs are classified as cacheable or not in the network (see Fig. 4-4).

Moreover, each content should be cached (the most popular and requested by end user) into an optimal vCDN node (content placement problem). Therefore, we use a cache function to track the migration of videos as follows:

Cache(v; t) = vCDN ID (4.1)
Where vCDN ID is the vCDN identifier, v is the video identifier (it is often a key file) and t is the time when we place/allocate the video identified by v. We can hence program and deploy our caching algorithm proposing better optimization to enhance the QoE/QoS of end users, decrease the load on the origin content provider (e.g., Youtube, Netflix, etc...), and let the operator host (allocate) the content on its content network (vCDN 1 , vCDN 2 ,... vCDN n ).

OPAC uses a Distributed Hash Tables (DHT) to index the content URLs over the vCDNs. vCDNs communicate periodically with vRR to maintain their connectivity and location.

An additional fast redirection happens as follows: if the video is cacheable, then it should be declared so. And then, the request is redirected based on Open-Flow rules and inserted in OpenFlow switches when the request is intercepted.

We use a greedy algorithm as follows: a user requests a video content. If it is cached. Then, the request is redirected to an optimal vCDN node based on OPAC protocol as detailed in the next section. Algorithm 1 summarizes the pseudo code of vCDN cache algorithm. Hereafter, we describe these main stages.

OPAC protocol

The main steps of the proposed protocol are detailed hereafter:

1. The end user i requests a video j , video i;j .

2. Network Service Provider (NSP) assisted with SDN network, management layer and NFV deployment (see Fig. 4-4) redirects customer's request to the optimal vCDN cache node (the optimal placement is derived with the help of an exact optimization algorithm, formulated and detailed later). 3. If video i;j is located in the optimal vCDN, then deliver(video i;j ) (see Fig. 45).

4. Else VoD origin server delivers the requested video to the user, and optimal vCDN node caches the video (see Fig. 456).

Notification of the caching controller about the mapping between the new vCDN address and video name.

For the sake of simplicity, we assume that the video service must be cached through the vCDN (we name it a vCDN cache as a service). Once the content is cached, requests from clients are dynamically redirected to the migrated vCDN (the deployment location has been proposed after executing OPAC optimization algorithm). Hence, We can enumerate the steps of the OPAC protocol as the following:

1. vCDN cache as a service (Fig. 4-4):

• Authorization: Either the Service Provider (SP) or the User Generated Content (UGC) must request authorization (step 1) in order to cache a popular video item (e.g., "/video.mp4").

• SP/UGC takes the authorization (step 2) from the Caching Controller (CC) which is part of the network operator.

• CC initiates policy rules (PRs) for redirection (step 3) by communicating with the database server (DB), then it interacts with SDN controller (step 4) to notify it by the PRs. The latter injects those PRs in OpenFlow switch device (step 5). Then, CC instantiates (if needed regarding to the available resource) the video service on vCDN. This virtual node can be a set-top box (STB) device that supports the virtualization technique (step 6).

• CC sends the vCDN address (@vCDN) to the requester (CP or UGC) (step 7).

• SP/UGC migrates/pushes the desired video content to the vCDN allocated on demand (step 8).

2. Video delivery (Fig. 4-5 and Fig. 456):

• Customer requests for a desired video (step 1)

• OpenFlow physical/virtual switch redirects under the previous PRs customer's request to the optimal vCDN streaming server (step 2)

• vCDN streaming server checks for the video (Fig. 4-5, step 3).

• If desired video is located in the local cache of vCDN (hit cache scenario) then it executes service video delivery process (Fig. 45step 4).

• Else (miss cache scenario) it retrieves the video from the origin VoD server (Fig. 456, steps 3 and 4).

• vCDN streaming server delivers the video to the end user (Fig. 456, step 5).

• vCDN streaming server notifies the CC in order to register the mapping between vCDN node identifier and video item (Fig. 4-6, step 6).

• CC updates/refreshes the database (Fig. 4-6, step 7).

OPAC optimization model

We propose an exact optimization algorithm that takes as an input the topology of the underlying network. It aims then to optimally place, and migrate the virtual content delivery functions (vCDN nodes) upon the virtualized infrastructure. Those virtual nodes move from one location to the optimal point in order to increase user satisfaction and decrease server and network loads. The optimization algorithm for placement is modeled, implemented, and evaluated in the next subsections.

Problem statement, constraints and main objectives

The problem considers delivering videos on demand or services, e.g., television programs, the movies, etc to a large group of users located in distant zones and served by an operator network. This operator may or may not be the service provider. Moreover, the problem supports users with different resolution requirements.

The statement is as follows: determine where to locate the VoD streaming headend, and how to migrate the virtual delivery node from one location the optimal one.

We consider different types of constraints in our virtualization process: system type constraints such as RAM, CPU, and storage, and network type constraints such as flow balance (conservation), QoE, link capacity, and server streaming constraints: maximum number of simultaneous connections per server). Recall that none of the previously described contributions considered the QoE parameter.

The latter aims to link context information such as the operator delivery network to video streaming. OPAC optimization will maximize the Mean Opinion Score (MOS) of end users having different devices and connected over different technologies (ADSL, WiFi, and Ethernet). Video delivery adaptation mechanisms using utility functions [START_REF] Tourad Diallo | Utility-based Approach for Video Service Delivery Optimization[END_REF] and MDASH (MOS Dynamic Adaptive Streaming over HTTP) can hence be supported by our work.

The objective is to minimize the cost of resources (i.e. bandwidth and migration).

The main goal of our study is to propose an algorithm and the underlying mechanisms to optimize video delivery networks. These mechanisms will guarantee the desired user's satisfaction level and on demand service optimization as:

1. Allocation mechanism and virtual delivery node migration: we introduce an optimization algorithm for vCDN allocation based on the maximum number of connections related to each file and its viewing rate (according to informa-tion calculated by counters such as DailyMotion/YouTube4 ). Our algorithm enables simple file movement between different domain vCDNs considering minimum cost of content access.

Service optimization mechanism (service on demand):

The second step is to analyze the virtualized delivery node and migrate them to the optimal PoP headend in order to achieve a better quality of experience (QoE) and better savings for network operator resources. This implies three levels of optimization:

1. Multi-criteria optimization: this first level aims to satisfy as maximum as possible the involved actors in the delivery process: the content provider that wants to push the maximum content to the CDN provider with minimum cost, the network operator which wants to decrease its server's load and save its resource (storage, bandwidth, ...) as possible, and the client who requests high quality of experience and better satisfaction with minimum price.

2. Network optimization: we optimize the load on the main network links and increase the operator's gain (delay reduction in content streaming).

3. QoE/QoS optimization: we focus on user's QoE by adapting the video streaming resolution to its context. We assume that vCDN users may require different video resolutions (Standard Definition (SD), High Definition (HD) and Ultra High Definition (UHD)). The quality parameter d f v corresponds to the resolution requirement per each cluster of end users is defined in Table 4.1.

The model can be easily extended to accommodate future ultra higher definition TV services like 8K.

We will detail the optimization problem constraints for vCDN migration and the objective function of our work in the next section. Binary variable indicating whether the link (i; j) is used to stream f to v

Mathematical formulation

In this section we specify the parameters and the constraints that are defined and proposed in formulating the optimization/analytic model. This formulation determines the migration of vCDN nodes to the optimal location.

• OPAC Parameters: OPAC deals with system, network, and QoS/QoE parameters as quoted in Table 4.1. We represent each by some parameters although it would be better to have them all detailed. For complexity issues, vCDN resource's size (f size ) (beside the other system/network parameters) is a normalized function of some relevant values that describes the size of the in-stance (system). Moreover, we introduce the QoS/QoE metric (d f v ) in our optimization problem. This parameter represents the consumer demands matrix. Periodically, the network operator feeds OPAC database with the existing demands: requests for vCDN services. A demand comes from a client group (v 2 V ) and targets a vCDN (f 2 F). This is to link end-users need (i.e., requesting vCDNs) with a specific throughput that is mentioned in their requests as a matching parameter between the requested quality (SD, HD, or U HD in terms of throughput) from the client group (v) and the streaming throughput from the vCDN serve (f ). The algorithm tries to satisfy all the user quality of streaming requests. Including all parameters would be too complex to solve in a reasonable time.

• Decision Variables: We quote in Table 4.1 the main system parameters and decision variables.

1. The binary variable x indicates the placement of the streaming headend, and its migration from one server s to another (best/optimal) location s 0 .

It is defined as:

x s;s 0 ;f = 8 > > > > < > > > > : 1 if f migrates to s 0 0 Otherwise (4.2)
2. The binary variable y indicates client request need for a vCDN service located on the optimal server. It is defined as :

y s 0 v;f = 8 > > > > < > > > > : 1 if v needs f and s 0 caches f 0 Otherwise (4.3)
3. The binary variable z v;f i;j indicates whether a link (i; j) is used (from i to j) to stream from a server s 0 replicating f (the one for which y s 0 v;f = 1) to client v.

• Constraints:

1. The binary variable y should be less than or equal to x. In fact, y equals 1 if and only if v needs f from the optimal server s 0 which has the functionality. This means that x should be equal to 1.

8s 0 2 S 0 ; v 2 V ; s 2 S : y s 0 v;f x s;s 0 ;f (4.4) 2.
Only one optimal server should serve the attached node that requests the functionality f :

8v 2 V j d f v 0 : X s 0 2S 0 y s 0 v;f = 1 (4.5)
3. The cost of streaming f by the optimal server should be less or equal to the maximum server capacity:

8s 0 2 S 0 : X v2V X f 2F y s 0 v;f d f v D s 0 (4.6)
4. The storage of the optimal server should not exceed its maximum size:

8s 0 2 S 0 : X s2S X f 2F x s;s 0 ;f f size C s 0 max (4.7)
5. Flow balance or conservation constraint (which is the laws of Kirchhoff)

between the optimal server s 0 and the client node v should be as the following:

X j z v;f i;j X j z v;f j;i = 8 > > > > > > > > < > > > > > > > > : 0 if i v; i s 0 y s 0 v;f if i = s 0 1 if i = v (4.8)
This is the network flow constraint. The sum of incoming flows must be equal to the outgoing ones.

6. Link capacity between source i and sink j should not exceed its maximum:

8i; j 2 V [ S 0 : X v2V X f 2F z v;f i;j d f v
C i;j (4.9)

Mono objective resolution

The objective function: the migration cost (transit) as formulated in equation [START_REF] Applegate | Making intra-domain routing robust to changing and uncertain traffic demands: Understanding fundamental tradeoffs[END_REF].

• Objective function:

min X s 0 2S 0 X s2S;f 2F x s;s 0 ;f c s;s 0 ;f (4.10)
where c s;s 0 ;f is the migration cost:

c s;s 0 ;f = f size (4.11)
Where is a parameter depending on the position of s 0 and the position of s (the server initially containing f before migration). depends also on the operator policy (e.g., the internal policy of the operator like configuration policy). • Analytical procedure (OPAC-based decision example): For the sake of clarity, we propose an example based on OPAC procedure for vCDN placement/migration context as shown in Fig. 4567. The algorithm is as follows:

1) As an input, OPAC controller gathers SDN/NFV architectural information such as the initial placement of vCDNs (f 1 2 s 1 , f 2 2 s 2 , etc.) and all necessary dynamic parameters (system capacity, network capacity, throughput, location, etc.) as shown in Fig. 4-7a representing the network state before migration, 3) as a result, end-users requesting vCDN YouTube®, to watch a popular video in a live event for example, will be redirected to the videos hosted in the new optimal calculated location as depicted in Fig. 4-7b representing the network state after migration. Recall that the network operator hosting the vCDN of YouTube content provider migrates the vCDN cache/stream node to an optimal PoP where resources are available and content quality streamed are satisfied.

Note that in a micro cache deployment (large scale) scenario, OPAC is still accept-able for vCDN placement/migration application. This is because the algorithm run time is in term of seconds. Therefore there is no need to develop a heuristic algorithm. OPAC algorithm is proposed to be executed in a virtual CDN controller/manager entity (vRR). It has to control/manage/orchestrate the VNFs running virtual CDN nodes. This placement is executed after three main triggers:

• System constraints (through f size and C s 0 parameters). and network constraint (through C i;j , D s 0 , and

d f v parameters).
• Service Level Agreements (SLA): It is QoS/QoE constraint through a contract between the content provider (the customer of the vCDN solution) and the network operator (the server or the provider of the NFV servers) (d f v resolution requirement per each cluster of end users). It (SLA) is considered through a valid range of streaming qualities: SD, HD, and U HD of each couple (client group-vCDN). The optimization process uses this requirement and the result satisfies the SLA.

• Storage/bandwidth prediction: OPAC makes the migration and assumes that the network and system parameters are available (through OpenStack dashboard). We mean by prediction that those parameters may change and cannot be known in advance. Recall that data centers are highly dynamic and shared, so live metrics and parameters are used from the virtual infrastructure manager (e.g., OpenStack data-centers) and update at the same time the OPAC database.

In the current implementation version of OPAC, triggers are not used to execute the optimization. However, as we use a database for our real-time parameters, all the dynamic values can be annotated with a triggering threshold that re-launches the process. The user demands, system parameters and network load are the potential triggers. Moreover, in this version OPACv1, we don't consider individual user demands, only groups (represented by the d f v matrix). Second we envision the execution of the algorithm in a predictive scenario. Till now, these demands

OPAC: optimization evaluation

We evaluate our work in a network that obeys the 3-tier layers architecture (access, aggregation and core layer) 5 . Fig. 45678shows the network topology used for the evaluation. Further, for the interest of assessing the efficiency of OPAC algorithm, we used CPLEX [START_REF]Ibm ilog cplex optimization studio community edition[END_REF] as an optimization tool.

We note that servers may be deployed in any network layer while client nodes are deployed only in the access network. We mention also that vCDN cache nodes are deployed on top of the physical servers that among NFVI and migrate from the source s to the optimal server s 0 . Further, we define the NFV cost and the placement time as follows:

• The NFV cost is defined as follows:

N FV cost = X s2S;s 0 2S 0 X f 2F
x s;s 0 ;f c s;s 0 ;f (4.12)

• The migration time is defined as follows:

P lacement time = X s2S;s 0 2S 0 X f 2F x s;s 0 ;f f size max (i;j)2P s;s 0 1 C i;j (4.13)
Where P s;s 0 is a given path from s to s 0 . In fact we are here assuming that placement is done in sequential way. If placement is performed in parallel, then the placement time would be given by max

s 0 2S 0 ;s2S;f 2F x s;s 0 ;f f size max (i;j)2P s;s 0 1 C i;j .
However, we will only consider Eq. (4.13).

Furthermore, for the sake of assessing the efficiency of OPAC algorithm, three main cost factors are defined as follows:

vCache cost = P s2S P s 0 2S 0 ;f 2F x s;s 0 ;f f size P s 0 2S 0 C s 0 (4.14) vStream cost = P s 0 2S 0 P v2V P f 2F y s 0 v;f d f v P s 0 2S 0 D s 0 (4.15)
Link utilization cost =

P v2V P f 2F z v;f i;j d f v P i;j2V [S 0 C i;j (4.16)
Where the cost UNIT represents the amount of system resources (vCache) or network resources (vStream and Link utilization cost) consumed when migrating a vCDN from a server to another one.

Hereafter, we evaluate the OPAC under different key performance indicators introduced above to assess impact of increasing virtual content delivery number, client group node number. Besides, we evaluate the virtual content delivery reso-lution impact, delivery capacity impact and delivery storage impact. We remark that the total NFV cost is linearly increasing. The vCDN placement time has an increasing slope for a vCDN number ranging from 3 to 9. This is due to the client node distribution which is not uniform. In Fig. 4-9c, cost unit 6 is plotted against the vCDN number. The storage cost for vCDNs in the network is constant, the virtual streaming cost and the link capacity cost are variable due to the demand variation of the end user.

Client node number impact

Secondly, we evaluate the impact of the client number on the overall cost taking into account the storage, network and streaming features. Therefore, we have fixed the total number of the virtualized content delivery networks that should be placed within the network (VNF deployed number = 10), and the same previous three-tier network. In Fig. 4-10a, we plot the placement time against client node number. In Fig. 4-10b, we represent the NFV cost needed for this placement. In Fig. 4-10c, we measure the virtual caching cost. It is in increasing till it reaches a constant value. We represent also link utilization cost, and we conclude that the streaming cost is still increasing because it is affected by the number of location from where clients receive the video service.

Virtual content delivery resolution impact

Thirdly, we evaluate the impact of virtual content delivery resolution. In Fourthly, in this subsection we show the impact of increasing the server's throughput on the cost of caching, streaming vCDNs and on the link utilization.

Fig. 4-12 includes 3 curves. These curves plot the cost unit against the server's throughput. We assume that clients may request either SD, HDV, or UHDV video quality. Regardless of the quality requested by clients, the caching cost is constant. There is no additional cost to deliver either SD, HD, or UHD to the client in terms of a caching cost in (GB). However, the streaming cost decreases when the server throughput increases. This leads to more efficient streaming and better QoE. This streaming cost increases when clients request high vCDN quality. Link utilization cost on the other hand is constant but it increases with high requested quality (from SD through UHD). In conclusion, in both cost factors (caching and streaming), the increment to get a better quality is not significant. It is only about 10 %.

Delivery storage impact

Finally, the impact of delivery storage is evaluated. In Fig. 4-13a, we plot the total migration cost needed for migrating a vCDN with random demand vector per

OPAC: comparisons

In this section, we introduce two main comparisons. First, we compare between OPAC (our optimal solution) and a non optimal approach. In the second, we compare between OPAC and the related work in two ways: 1) a comparison between OPAC and Bernadetta et al.'s work in term of link utilization cost, and 2) a comparison between OPAC and the state-of-the-art.

Comparison between OPAC and non optimal migration algorithm

The OPAC algorithm as detailed in Section 4.5 searches for the optimal placement to cache vCDN nodes according to the network constraints and users' demands. The network and system constraints are deterministic parameters and can be measured precisely over time. However users' demands can only be predicted as it is difficult to determine a priori what content the user will decide to watch next. Hence, some predictions can be erroneous and lead to non optimal placement of content. Thus, the optimal and the non-optimal definitions for our Figure 4-14 -comparison between the optimal and the non optimal algorithms using total virtualization cost parameter and under vCDN/client node variation implemented algorithm are defined as follows:

x s;s 0 ;f = 8 > > > > < > > > > :
1 if f migrates to s 0 (optimal) 0 if f migrates to Snfs 0 g (non optimal) (4.17)

In Fig. 4-14 , we made a comparison in terms of the total virtualization cost (accumulated percentage of delay (normalized resource costs used in virtualization of vCDNs)) 7 between our optimal algorithm and the non optimal one. It is clear that our exact and optimal allocation/migration algorithm outperforms the non optimal one. The operator's gain which is proportional to the reduction in delay is therefore obvious.

In Fig. 4-15, we plot the computation/execution time gained after the allocation/migration process. The gain is the reduction in delay if our optimal solution is adopted compared to the non optimal approach. The latter is obtained if the target PoPs that will host the virtual CDN is non optimal. It shows that the reduction in delay is noticeable and reaches 20 sec for vCDN number = 11. This can lead to a better QoE. However, the reduction delay is very important when client node number is increasing and reaches 3 minutes at v = 12. Recall that v represents an

Comparison between OPAC and related work Comparison between OPAC and Bernadetta et al. work

Network link utilization is a relevant metric. Thus, to evaluate the network performance of OPAC from the telecommunication operator perspective, we compared our solution with Bernadetta et al [3], who used the same network and NFV parameters.

At first glance, we quote the difference between our approach and Bernadetta approach as follows:

• First of all, Bernadetta protocol uses three flow balance constraints and imposes a single path flow balance. We believe that this increases the link utilization and causes bottlenecks in the network links (congestion).

• The second difference is that Bernadetta algorithm includes compression which we believe is unnecessary since it can be replaced by the VNF size. Moreover, in Fig. 4-16, we plot the link utilization cost which is clearly greater than our approach. Thus, their proposed algorithm is still efficient for placing but can not deal with user's demand dynamicity (d

f v = 10).
In the simulation, we kept the same parameter used by Bernadetta (2 VNF type, node capacities).

Brief comparison between OPAC and the state-of-the-art

We show in Table 4.2 a comparison between our optimization approach and a few recent work:

• Authors in [START_REF] Bouten | Towards nfv-based multimedia delivery[END_REF] [START_REF] Mangili | Stochastic planning for content delivery: Unveiling the benefits of network functions virtualization[END_REF] [27] [3] [122] introduced either system or network metrics in order to model the problem of placement of a VNF in general. However, we introduced in OPAC both: system and network metrics.

• Authors also did not introduce any parameter characterizing users' requirement. Therefore, we introduced an additional parameter to do this. • Authors also tried to solve an initial placement problem of a VNF through static and offline optimization, while our optimization solves the placement problem and adds the migration context in dynamic way and while the vCDN service is running.

• In OPAC, we introduced a virtual cache cost since our VNF (vCDN) is dedicated to streaming/caching services.

Conclusion

This chapter presents a new optimization technique for cache distribution with underlying virtualization tools. We proposed to integrate new constraints such as QoE, VNF mobility and system design. For this purpose, a redirection/cache/update protocol that defines the messages exchanges between end-user, virtual CDN, operator, and service provider was proposed. Furthermore, OPAC, an optimization algorithm was modeled, implemented and evaluated when demand on different content changes. It gave a short execution time (i.e., the running time was in terms of seconds). Different comparisons for our placement solution and the state-ofthe-art are conducted. The results show a net improvement in cache update. We also evaluate the update performance if the cache prediction is slightly imprecise.

Our Cache placement algorithm still gives satisfactory results. Decision time in LP techniques increases exponentially for large network inputs (vCDN instances).

They are not appropriate for large complex graphs. Therefore, in the next chapter, we try to propose scalable and cost efficient algorithms for vCDN migration problem in small large graphs.

Chapter 5

Scalable and cost efficient algorithms for vCDN migration

Introduction

In the previous chapter, we have proposed OPAC, an exact optimization algorithm for the problem of vCDN placement. In this chapter, we bypass the initial vCDN placement step that can be solved by a single execution of OPAC algorithm.

Then, we re-formulated the mathematical model to propose an exact algorithm for vCDN migration 1 . It recommends optimal location points where to migrate vCDN on-demand/live instances to satisfy users quality requirements. The major objective from the algorithm is to minimize the total cost of content migration while minimizing the additional extra-costs needed for caching, streaming, and replication number.

Then, we are going to cope with scalability problems of exact algorithms.

Therefore, we adapt a heuristic algorithm (i.e. HPAC: Heuristic Placement Algorithm for virtual CDN) to deal with our constraints when large scale networks need to be optimized. In this algorithm, we exploit the well known Gomory-Hu method to find a near to optimum point of operation. Finally, as the optimization algo-rithms deal with many heteroclite parameters, a clear view on how/where/when they are extracted and how they are reflected on a typical SDN/NFV architecture is diagrammed.

The rest of this chapter is organized as follows: Section 5.2 details the functioning of OPAC algorithm through a migration use case. Section 5.3 details our heuristic optimization algorithm (HPAC). Section 5.4 evaluates the two algorithms and gives a comparison between them under predetermined metrics besides an integration diagram in Section 5.5. Section 5.6 concludes the chapter.

OPAC: migration use case (OMAC)

In this section, we specify the parameters and the constraints that are defined and proposed in formulating the optimization model OPAC. This formulation determines the migration of vCDN nodes to the optimal locations. We quote in Table 5.1 the main system and network parameters, and decision variables.

• The decision variables: Binary variable indicating whether the link (i; j) is used to stream f to v 1. The binary variable x s f indicates the placement of the streaming headend, and its migration from one server to another (best/optimal) location s. It is defined as:

x s f = 8 > > > > < > > > > : 1 if f migrates to s 0 Otherwise (5.1)
2. The binary variable y s v;f indicates a client v needs a vCDN service, and the server s caches it. It is defined as :

y s v;f = 8 > > > > < > > > > : 1 if v needs f and s caches f 0 Otherwise (5.2)
3. The binary variable z v;f i;j indicates whether a link (i; j) is used (from i to j) to stream from a server s replicating f (the one for which y s v;f = 1) to client v.

• The constraints:

1. The binary variable y should be less than or equal to x. In fact, y equals to 1, if and only if v needs f , and f is located on server s. This means that x should be equal to 1. Otherwise, if y equals to 0, then x may be equal to 0 or 1.

8s 2 S : y s v;f x s f (5.3)
Note that a vCDN can be replicated more than once.

2. Only one optimal server should serve the client node that requests the functionality f :

8v 2 V j d f v 0 : X s2S y s v;f = 1 (5.4)
3. The cost of streaming f by a server s should be less than or equal to the 114CHAPTER 5. SCALABLE AND COST EFFICIENT ALGORITHMS FOR VCDN MIGRATION maximum server capacity:

8s 2 S : X v2V X f 2F y s v;f d f v D s (5.5)
4. The storage of the optimal server should not exceed its maximum capacity:

8s 2 S : X f 2F x s f f size C s (5.6)
5. Flow balance or conservation constraint between the server s and the client node v should be as the following:

X j z v;f i;j X j z v;f j;i = 8 > > > > > > > > < > > > > > > > > : 0 if i v; i s y s v;f if i = s 1 if i = v (5.7)
This is the network flow constraint. The sum of incoming flows must be equal to the outgoing ones.

6. Link capacity between source i and sink j should be larger than the flow on the link:

8i; j 2 V [ S : X v2V X f 2F z v;f i;j d f v L i;j (5.8)
The objective function is formulated in equation (5.9) (cost function):

min X s2S X f 2F x s f m s f (5.9)
where m s f is a parameter depending on the position of s, the position of s f (the server initially containing f before migration), and the position of s v (the server initially connecting to the client group v). m s f depends also on the size of f and the operator policy. as a result, end-users requesting vCDN YouTube®, to watch a popular video in a live event for example, will be redirected to the videos hosted in the new optimal calculated location.

Recall that the network operator hosting the vCDN of YouTube content provider migrates the vCDN cache/stream node to an optimal PoP where resources are available and content quality streamed are satisfied.

The above problem is NP-hard due to our combinatorial complex system and therefore the proposed exact algorithm is difficult to scale up to decide where to deploy vCDN nodes in a large scale scenario. As a consequence, an efficient heuristic algorithm is proposed in the next section.

HPAC: Heuristic Placement Algorithm for virtual CDN

Our proposal is strongly based on Gomory-Hu 2 tree transformation [START_REF] Gomory | Multi-Terminal Network Flows[END_REF] of the initial network (represented by access, aggregate and core nodes) as shown in Fig. 5-4). In other words, HPAC transforms the input network into a G-H tree. Then, 2 noted by G-H in the rest of the chapter replicating vCDNs is performed thanks to the G-H tree allowing to efficiently reduce the number of edges to be considered when migrating contents.

Algorithm 2 summarizes the pseudo code of HPAC. Hereafter, we describe these main stages.

Algorithm 2 Heuristic algorithm for virtual CDN placement and migration

1: Input: V , S, D s , F, f size , C s , L i;j , d f v , m s f , G = (V (G); E(G)), 2: s v , s f 3: Output: x s f ,

Gomory-Hu transformation

At this stage, our heuristic HPAC computes the G-H tree of the CDN network or graph. The main advantage of G-H tree transformation is to compact this network graph structure using cuts to retain only feasible candidate topology and consequently lead to a smaller scale vCDN placement problem. We will insert a figure of the example of a G-H transformation.

For sake of clarity, we introduce the G-H tree transformation of our initial graph G = (V (G); E(G)). The G-H tree GHT = (V (GHT ); E(GHT )) of the former graph can be built using the definition in [START_REF] Korte | Combinatorial Optimization: Theory and Algorithms[END_REF]. There exists many algorithms that can build the G-H tree in polynomial times [START_REF] Hariharan | An Õ(mn) gomory-hu tree construction algorithm for unweighted graphs[END_REF] by finding N 1 maximum flow or minimum cuts between each pair of nodes in the graph, where N = jV (G)j.

The G-H tree can be found in polynomial time according to the algorithm used to find a maximum flow/minimum cut in the initial graph. But, we describe only one selected strategy that relies on the minimum Steiner cut algorithm presented in [START_REF] Cole | A fast algorithm for computing steiner edge connectivity[END_REF].

The transformation starts by initializing V (GHT ) to the set of the graph nodes (i.e., fV (G)g and not V (G)). Concerning E(GHT ), it is initialized to an empty set.

Besides, we define a queue list Q to enable the G-H tree construction. Q is initialized to V (GHT ) value. Then, while Q is not empty, we pull the first element S from this queue and we apply the minimum Steiner cut algorithm with the current set S (i.e., first Q element).

As the Steiner set in the new graph is obtained by contracting the entire subtree rooted at each neighbor in GHT of S into a single node. Consequently, two new sets of nodes S 1 and S 2 are generated from S and S 1 ;S 2 is the cut size. Accordingly, V (GHT ) should be updated by removing S and adding S 1 and S 2 . Besides, E(GHT ) should be enhanced by adding a new edge between S 1 and S 2 with capacity S 1 ;S 2 (i.e., the cut size).

Furthermore, the queue Q will be enriched by adding S 1 (respectively S 2 ) if it includes at least two nodes, jS 1 j > 1 (respectively jS 2 j > 1). The former steps will be repeated until the G-H tree construction matches with an empty queue Q state.

The pseudo-code of the following G-H tree building strategy is summarized in Algorithm 3.

Algorithm 3 Gomory-Hu tree transformation algorithm

1: Input: A connected graph G = (V (G); E(G)) 2: Output: A tree GHT = (V (GHT ); E(GHT )) 3: V (GHT ) = V (G), E(GHT ) = ;, Q = fV (G)g 4: while Q ; do 5: S Pull(Q);//pull the first element from Q 6:
fS 1 ; S 2 g minimum-Steiner-Cut(S; GHT ) 7:

V (GHT ) = fV (GHT ) n Sg [ fS 1 ; S 2 g 8: E(GHT ) = E(GHT ) [ (S 1 ; S 2 ) 9:
if jS 1 j > 1 then 10:

5: Q Q [ S 1 11: end if 12:
if jS 2 j > 1 then

13: Q Q [ S 2 14:
end if 15: end while We give a simple example of a G-H tree transformation of a graph G as illustrated in Fig. 5-2. It is straightforward to see that the number of edges in the tree compared with the initial graph is reduced by 50%. Note that this G-H tree was built using only 6 iterations of Algorithm 3.

HPAC: placement and migration

Based on the G-H tree transformation, the number of nodes is equal to the number of nodes in the initial graph/network. However, the number of links in the derived G-H tree is at most equal to the number of nodes in the graph. Accordingly, the set of all paths can be easily computed. In fact, in the tree structure there is only one path between any couple of servers.

With this tree transformation leading to significantly reduced input sizes, the problem of vCDN placement and migration will be easily solved even for large problem instances (large number of nodes and arcs). This is due to the efficiency of the G-H tree transformation leading to reduce considerably the domain of feasible solutions. So, it allows us to find the near optimal solutions in few seconds. In the following, we give more details on the second stage of the HPAC algorithm to place and migrate vCDNs in a cost efficient manner.

The second stage of HPAC algorithm consists to explore the unique path from an access point to the server containing the vCDN. Thus, if the ingress flow cannot reach the destination (i.e. the vCDN), caused by a rupture node, then we will simply migrate the required vCDN to the rupture node of the G-H tree. We propose the following example (see Fig. 5-3 ) to illustrate HPAC algorithm for migrating and placing judiciously vCDNs. It depicts a scenario of con- tent replication/migration. In this scenario, a client cluster (group) representing grouped end-user requests for a vCDN with a specific throughput (i.e., content quality) equal to 40 Mbps. The proposed migration method searches to migrate the desired vCDN from its initial deployed position (server 1) to the suitable server (i.e., server 2 which has more than the required streaming capacity) in an efficient way (i.e., with minimum migration cost).

OPAC versus HPAC (exact versus heuristic)

For the interest of assessing the efficiency of OPAC and HPAC algorithms, we used [START_REF]Ibm ilog cplex optimization studio community edition[END_REF] and [START_REF] Pérez | IPython: a system for interactive scientific computing[END_REF] as optimization tools. In addition, different metrics/costfactors can be defined as follows:

Migration cost = X s2S X f 2F x s f m s f (5.10) Migration time = X s2S X f 2F x s f f size max (i;j)2P s f ;s 1 L i;j (5.11)
Where P s f ;s is a given path from s f to s. In fact, we are here assuming that the migration is done in a sequential way. If the migration is performed in parallel, then the migration time would be given by: max However, we will only consider (5.11).

s2S;f 2F x s f f size max (i;j)2P s f ;s 1 L i;j .
Replica number = X s2Snfs f g X f 2F
x s f (5.12)

vCache cost = P s2S P f 2F x s f f size P s2S C s
(5.13)

vStream cost = P v2V P f 2F y s v;f d f v P s2S D s (5.14)
Moreover, in order to decide which algorithm should we use and when, different network scales (i.e. small and large) and topologies are considered as follows:

Small scale scenario: a network operator snapshot

In this subsection, the optimization targets a small number of vCDNs. Therefore, a snapshot of a three-tier network operator architecture3 is used for the evaluation as show in Fig. 5-4. Moreover, the main dissimilarities between the two approaches according to the defined metrics are showed hereafter:

Algorithm complexity: The algorithmic complexity of G-H-based HPAC is polynomial while it is exponential in OPAC.

The run-time: The time convergence of the two algorithms is shown in the Fig.

5-5a

. HPAC outperforms OPAC since the latter is a combinatorial-based algorithm and has an exponential complexity.

The total migration time: It is the duration needed to migrate a vCDN to the optimal/near optimal point of the deployment. Fig. 5-5b shows the average migration time needed for migration vCDN delivery functions to the optimal instantiation point taking into account the NFV constraints including system, network, and content quality parameters which are related to the vCDN functionalities.

Although HPAC gives the shortest time as depicted in this figure, OPAC is still acceptable. Indeed, This metric is strongly related to the distance between servers as written in (5.11) and the time consumed for the vCDN migration process is less than 1minute for vCDN numbers equals 11.

The total migration cost: It is evaluated in both approaches (exact and heuristic). In Fig. 5-5c , the vCDN total migration cost is measured in terms of Gigabits (Gb) against vCDN number. The Fig. 5-5c shows that vCDN-migration cost is increasing in both approaches for vCDN number ranging from 3 to 6. This is due to the non uniform client group distribution. It is noticeable that OPAC outperforms HPAC for vCDN ranging from 6 to 11. Nevertheless, HPAC proofs a low variation cost which leads to a better save of operator resources.

The total replication number: Under a random end-users matrix demand, the total replication number in both approaches is not significant (small) as shown in Fig. 5-5d. However, HPAC is the strictest approach when replicating vCDN in small scale scenario.

Other cost-factors: OPAC and HPAC are compared in terms of vCache and vStream cost-units 4 . In Fig. 5-5e cost unit is plotted against vCDN number. The virtual in-networking caching cost increases in both algorithms but they are still insignificant. Similarly, in Fig. 5-5f the virtual in-network streaming cost increases with vCDN number in both algorithms but it is still insignificant. Although the 4 Cost-unit may be defined by the utilization percentage of the available system or network resource.

122CHAPTER HPAC is slightly cost-efficient, both algorithms proofed an efficient network resource saving.

SCALABLE AND COST EFFICIENT ALGORITHMS FOR VCDN MIGRATION

Experiments show that OPAC is still acceptable and saves about 96 % of the system resources and 94% of the network resources at jFj = 11. Nevertheless, it is still the most costly comparing to HPAC in terms of system and network resource usage.

For the sake of clarifying the effectiveness of the HPAC, we define the Gap metric as follows:

Gap(C) = C HP AC C OP AC C OP AC (5.15)
Where C is a cost factor (e.g., migration cost). while OPAC run-time explodes from vCDN number equals 20.

Interpretations

In this subsection, we quote the interpretations that can be revealed from the results above: In small scale scenario: (the order of ten servers, ten client groups, and ten vCDNs), the exact approach is suggested to be used because its run-time is in terms of a few seconds (see Fig. 5-5a. OPAC is what we should choose as an optimization mechanism because it gives the lowest migration cost as shown in Fig. 5-5c .

In large scale scenario: (the order of hundred servers, hundred client groups, and hundred vCDNs), the exact approach is suggested to be useful and the G-Hbased HPAC algorithm is the alternative to solve the vCDN migration problem since its algorithm run-time is in terms of a few seconds as shown in Fig. 5678.

A brief comparison between the two approaches which answers implicitly to the question when to use OPAC and when to use HPAC is given in the

Integration of the Algorithms

Practically, the proposed optimization algorithms have to be integrated in a vCDN controller (as seen Fig. 5-1 ). It interacts with the vCDN manager software in a legacy NFV-MANO framework [START_REF][END_REF]. Further, as the migration problem deals with different heteroclite parameters and variables, a clear view about how they are extracted and reflected on an SDN/NFV framework is necessary.

In Fig. 5-9 and for the sake of simplicity, the two main use cases needed for integrating OPAC/HPAC algorithms by the network operator are depicted. Indeed:

• Use case 1: The network operator checks the current placement of vCDNs.

To do this, he queries a Database using SQL structured language and an NFV/SDN controllers (e.g., Openstack [START_REF] Rosado | An overview of openstack architecture[END_REF]/Opendaylight [128]) using API interfaces. Openstack horizon and Opendaylight DLUX providing respectively the system and network resource information needed to complete the operator database.

• Use case 2: The network operator requests for the vCDN optimization placement/migration result using either OPAC or HPAC according to the actual network scale (small or large).

From an operator perspective, integrating the proposed algorithms may follow the sequence diagram represented by the Fig. 5-10 . Indeed, the main stakeholders are:

• User (Operator): Operator of the infrastructure, deciding the migration or not of a vCDN instance according to the current state of the environment and the result given by the optimization algorithms OPAC/HPAC.

• System: This system, offering the Users an interaction with the OPAC/HPAC algorithms inputs and results. It still maintains the operator database updated by the necessary information about the operator's servers (getHypervisor()) and the provider's vCDNs (getStatus()). • OPAC and HPAC Algorithms: Implementation of the optimization algorithms that optimize the vCDN placement and migration based on exact/heuristic optimization approaches. A file is given as an input and a file is returned as an output of the selected algorithm. The algorithm selection depends mainly on the network scale.

For simplicity, when the user (operator) executes the optimize command, the system fetches the operator databases to get the required information (get input())

in order to launch in turn the optimize command. Then, OPAC/HPAC algorithm decides where to place and migrate the vCDNs and provide the system/operator the result. Finally, the system executes the migration process according to our results and releases the dedicated resources in case of Service Level Agreement (SLA)-expiration/vCDN-delete-request.

Recall that the proposed algorithms involved also the content provider who wanted to rent a cloud of vCDN for its customers. Therefor, from a content provider perspective, the main exchanges between the content provider, the vCDN manager and the user (operator) are depicted:

• The content provider (e.g., YouTube) requests a vCDN creation during a specific time (e.g., 2 hours) and with a specific QoE (e.g., excellent) and to cover a specific region (e.g. Paris).

• The network operator, representing the owner of the NFV infrastructure, checks the current state of its NFV resources and call the proposed optimization algorithms through the provided system.

• This system interacts with a operator database server to retrieve the required information about network topology, NFV resources and update another database dedicated to the placement/migration decision.

• The NFV Infrastructure (NFVI) administrator interacts with the decision's database to migrate the resources while keeping the signed SLA between the content provider and the network operator valid and standing.

• Optionally, the NFVI administrator may let the content provider as the manager of the video content.

• The decision database is updated by the operator for security issues.

• In case of SLA expiration (e.g, covering time expiration, vCDN deleterequest, etc..), the operator releases the dedicated NFV resources.

Conclusion

This chapter presents two optimization solutions either for the placement or the migration problem of virtual CDNs. Multiple constraints that are strongly related to the CDN virtualization are taken into account such as vCDN size, content resolution and system/network requirements. In addition, the two optimization algorithms OPAC and HPAC target respectively different network scales. Then, they are modeled and implemented. In small scale networks, results show that jFj have more significant impact on the average migration cost in the case of using HPAC rather than OPAC. Nevertheless, it is noticeable that HPAC converges to the optimal solution and outperforms OPAC in specific metrics. In large scale, HPAC gives a short execution time (e.g. the run-time was in terms of a few seconds) which proofs its efficiency and scalability. In this network scale, The HPAC's results show that jFj have insignificant impact on the migration time, the migration cost and the replication number since the system reaches quickly its stability.

Moreover, the two approaches are integrated in an SDN/NFV framework and the main use case, sequence diagram from either an operator or content provider perspective.

In the next chapter, we extend the aforementioned placement algorithms to service orchestration problems. In this case, vCDN components should be orchestrated (chained) and service flows should be mixed together in order to satisfy end-user requirements (e.g. a content with ad flows).

Chapter 6

Optimal and cost efficient algorithm for vCDN orchestration

Introduction

In the previous chapter, we have investigated the main optimization techniques for vCDN placement and migration problems in small and large network scales.

Currently, despite the importance of vCDN optimization tasks, service orchestration module is still missing in the global architecture. We therefore, try in this chapter to contribute with vCDN management and orchestration architecture beside an optimal orchestration algorithm and explain how it is integrated in the operators virtual LAN.

The proposed optimization algorithm in this chapter considers vCDN orchestration problem inside the mobile network operator. Moreover, the major objec- We propose a simplified vCDN architecture With respect to the ETSI-MANO standard as depicted in Fig. 6-2. Indeed, it has the following communication 1 It is software that implements a network function. 1. Vertical interfaces:

• vCDN orchestrator-j-vCDN manager: It instantiates the vCDN manager and then manages the global CDN network services through resource management rules.

• vCDN manager-j-OpenStack: It has the role of virtual resource provisioning .

• OSS/BSS-j-vCDN's VNFs: It guarantees the end-to-end security of the allocated vCDN VNFs and provides the streamed QoS.

• vCDN's VNFs-j-VMs(NFVI): It assures the instantiation and deployment of the corresponding VNFs of vCDN (i.e., request routing, streaming, and caching). • vCDN orchestrator-j-OSS/BSS: It manages the CDN network services (NSs).

Horizontal interfaces:

• vCDN manager-j-EM/VNF: VNF life-cycle management including VNFs scaling, VNFs creation, VNFs deleting, VNFs stopping, VNFs releasing.

• OpenStack-j-NFVI/VMs: It has the role of VM resource allocation and provision. It manages VM creation, VM deleting, and VM importing.

In Table 6.1, we map the ETSI-MANO design to propose a practical vCDN architecture. Further, we propose different algorithms for orchestrating vCDN components, placing, and migration of the vCDN caching and streaming nodes.

vCDN must follow the VNF model. However, its specificity resides on the type of the used components, the OCPA orchestration algorithm that should be used, and its layer of integration (vCDN manager). In the next subsection, we define our enhanced vCDN architecture comparing to the traditional ETSI MANO model.

Global virtual CDN architecture

The global vCDN architecture is enriched by several computing, networking and management modules. In this section, we quote the baseline components as follows: NFVI space, VNF space, Orchestration space, and management space. This space includes three domains:

1. Virtual computing domain: The computing domain is the area of virtual machines computation.

2. Virtual storage domain: It is the area of allocating VM states, contexts and files.

Virtual networking domain: It is the area of virtual network interfaces (VNIs)

configuration.

VNF space

In the VNF space as shown in Fig. 6-3, we propose these virtual functions for vCDN:

1. Request routing: This function has the role of selecting a suitable cache node and redirecting end-user requests to it. It can be:

• DNS instance (vDNS): It is a DNS server software instance running on one virtual machine. This approach of redirection relies on DNS client IP address and not end-user IP address. It cannot be an optimal redirection.

• HTTP instance: It is a HTTP server software instance running on one virtual machine. • Load balance instance: It is software instance for balancing end user request between active streaming servers.

• Advertisement server Instance: It acts a mixer of the origin content and popular or desired advertisement.

• Mobility and prediction instance: It has the role of an entering point to the OPAC instance. It feeds it by a user requests traces and user location traces.

Those VNFs related to vCDN architecture should be interconnected, controlled, and orchestrated by the VNFM.

For the sake of simplicity, Fig. 6-3 depicts the low level design of VNF space for vCDN. First of all, content provider pushes his content in an origin server (OS). Secondly, the latter requests for distributing the content between distributed vCaches. This operation starts after a cryptography processing through AAA server (2-a, 2-b). Thirdly, vCaches push content is vStream virtual nodes (3).

Fourthly, user device sends a request to a virtual request routing server (4). Fifthly, vDNS redirects user's device request to a suitable vStream node.

Orchestration space

In the orchestration space, we propose to execute an optimization algorithm as an NFV instance in the centralized entity: vCDN Manager as designed in Fig. 6-2.

The vCDN Manager has to orchestrate the aforementioned VNFs already proposed for vCDN network function according to the output of the optimization algorithm.

The proposed OCPA orchestrator instances are optimal orchestration algorithm for vCDN that map vCDN VNFs to physical servers and dynamically migrate vCDN nodes to the optimal point of deployment. In other words, these instances are executed as NFV instances of orchestration on top of a VNFM2 . The OCPA algorithm provides a service instantiation graph, SIG representing the candidate NFV servers to where a set of vCDN components should be placed. The algorithm's execution is then triggered according to these factors:

• Constraint: It represents system, network, and quality constraints of the orchestration algorithm.

• Service Level Agreement (SLA): This trigger is translated from the upper layer.

• Storage Prediction: The available server storage at each time triggers the execution of the algorithm.

• Bandwidth Prediction: The available server storage at each time triggers the execution of the algorithm.

Recall that the output of the aforementioned algorithms is a mapping graph between the optimal NFV servers and each candidate VNF. This output information can be succeeded by a decision-making process giving place/migrate the VNF or not information.

Management space

In the management space, we propose a centralized entity for managing the CDN. It has three main roles:

• The creation of one or more orchestration spaces.

• The management of virtual machines allocation for each vCDN service or VNF. In Fig. 6-4, we propose adding a Manager entity to the above NFV and VNF spaces. This entity defines the management space. It interacts with the content provider (i.e., the vCDN customer) for content pushing inside the vCDN network provider. The Content provider signs with the manager the SLA, provides the vCDN service time (duration of the service), and the specifies the desired regions that it would cover. Moreover, for adaptive data center activation, end-user demands can be predicted through a data mining server. It communicates between the content provider and the manager entities.

In Table 6.2, we compare the proposed vCDN architecture to the ETSI-MANO reference. It is clear from the table that our design is more flexible as we added an API interface between CPs and NFVI.

OCPA: optimal vCDN orchestration algorithm

In this section, we specify the parameters and the constraints that are defined and proposed in formulating the optimization model, OCPA. This formulation determines the extension of vCDN component to the optimal locations. We quote in Table 6.3 the main system and network parameters, and decision variables. The OCPA optimization model considers three NFV server levels where vCDN components may be extended in the orchestration process: i) the PoP level, ii) the home level, and iii) the user device level.

• The decision variables:

1. The binary variable x s f indicates the placement (instantiation) of the vCDN component on the optimal location s. It is defined as:

x s f = 8 > > > > < > > > > : 1 if f is instantiated on s 0 Otherwise (6.1)
2. The binary variable y s v;f indicates a customer v needs a vCDN component, and the server s instantiates it. It is defined as : Flow balance binary variable which indicates whether the link (i; j) is used 3. The binary variable z v;f i;j indicates whether a link (i; j) is used (from i to j) to stream from a server s replicating f (the one for which y s v;f = 1) to customer's clients v.

y s v;f = 8 > > > > < > > > > : 1 if v needs f
• The constraints proposed in this model are:

1. Storage and bandwidth (S/B) capacity: the end user device level has less S/B capacity than the STB/RAN and the STB/RAN level has less S/B capacity than the PoP/EPC level.

2. The storage of the optimal server should not exceed its maximum size:

8s 2 S : X f 2F x s f f size C s (6.3)
3. The cost of streaming f by a server s should be less than or equal to the maximum server capacity:

8s 2 S : X v2V X f 2F y s v;f d f v D s (6.4)
4. Each replica server among the distributed NFV enabled infrastructure has also to serve one optimal user device. between the optimal server s and the customer's client node v should be as follows:

8i; j 2 V [ S : X v2V X f 2F z v;f i;j d f v
L i;j (6.6) 6. Network flow constraint that implies that incoming traffic equals to the out-coming traffic at any network link:

X j z v;f i;j X j z v;f j;i = 8 > > > > > > > > < > > > > > > > > : 0 if i v; i s y s v;f if i = s 1 if i = v (6.7)
Beside these constraints, we have considered Device-to-device (D2D) communication between end-users devices. Each end-user device acts as a cluster head and feeds a D2D cluster.

8v 2 V ; X f 2F d f v = D2D n (6.8)
Where D2D n is the number of D2D that requesting a vCDN service through the end-user device v 2 V . The end-user device may act as a cluster head in a typical D2D-assisted model. x s f p s f (6.10)

Where: (x s f ) jSj jFj is the decision binary variable matrix indicating that a vCDNC f 2 jFj should be migrated to the server s 2 X and p s f is a parameter depending on the position of s, the position of s f (the server initially containing f before orchestration), and the position of s v (the server initially connecting to the client group v). p s f depends also on the size of f and the operator policy.

For the sake of clarity, we propose an example of OCPA vCDN orchestration as shown in Fig. 6-5 . The algorithm is as follows: 1) As an input, the algorithm gathers SDN/NFV architectural information such as the components of vCDN (vCDNc for service caching, vCDNs for service streaming, and vCDNr for request routing) and all necessary dynamic parameters, 2) as a result, end-users requesting vCDN service streaming will be redirected to the optimal edge cloud location.

Recall that the network operator hosting the vCDN content provider orchestrates the vCDN instances (or components) to an optimal service instance graph (SIG) where resources are available and content quality streamed are satisfied.

Performance evaluation

For the interest of assessing the efficiency of OCPA algorithm, we used threetier as network topology (see Fig. 6-6 ) suggested by IETF standard for data center [START_REF]Nfvi pop network topology: Problem statement[END_REF] and [START_REF]Ibm ilog cplex optimization studio community edition[END_REF] as optimization tools. In addition, different metrics/cost-factors can be defined as follows: In Fig. 6-10, the total replication number of vCDN is plotted against jFj under a random client matrix demand. Result shows that replica number is not significant. However, vCDNTTP is the strictest approach when replicating vCDN in small scale scenario.

vCDN

OCPA: scenarios

In order to compare OCPA, we proposed two scenarios: 1) User-side and 2)

Network-side perspectives. The two approaches are defined as follows:

1. In user-side scenario, vCDN components are orchestrated toward the access level represented by home devices (STB, RAN, and and end-user equipment).

In other words, network operator outsources vCDNC functionalities. Recall that the network operator is still the manager of its resources despite its outsourcing to the user-side domain.

TOPSIS-based method for vCDN migration

Selecting the optimal place for migration a vCDN component is an important optimization task giving the large network scale and the complex parameters to • TOPSIS-algorithm: In this step, the network parameters are identified in order to carefully choose the decision criteria and the main alternatives.

• Layer selection& Migration-process: In this step, the network administrator selects the suitable layer of deployment. The vCDN nodes dynamically migrate to the optimal NFV servers according to the previous output of the TOPSIS technique. This reduces the number of parameters and constraints used by the optimization algorithm. Therefore, running time and algorithm complexity could be reduced.

For the sake of clarity, hereafter, we describe these main stages as follows:

TOPSIS formulation

TOPSIS is a multi-criteria decision analysis method. In other words it is a decision-making approach that could be used in different domains. Generally, it is based on two main features: options and criteria. Options are the list of alternatives that can be taken as a decision. Criteria are the metrics that can be considered to make an optimal decision. In vCDN migration context, TOPSIS can be used as follows:

• The potential options that may be proposed are vCDN-to-the-POP (vCD-NTTP), vCDN-to-the-home (vCDNTTH) and vCDN-to-the-User device (vCDNTTD) and in case of no migration will be vCDN-at-the-Origin server (vCDNATTO).

• They characterize the content provider, the network operator, and the customer requirements in terms of cost, quality and gain.

To define and enable the TOPSIS method, an option-criteria matrix is defined as follows: M = (d i;j ) i;j ; i 2 f1; mg; j 2 f1; ng. Where m is the number of options, and n is the number of alternatives or criteria. In the context of vCDN migration, we have (m = 4 alternatives) as: (vCDNTTP, vCDNTTH, vCDNTTD, vCDNATTO) and (n = 8 criteria) as explained hereafter:

• Content provider has three criteria: They are the cost of pushing content within the network operator, the internal configuration required, and the av- • Network operator has three criteria: They are the cost of migration and optimization, the QoS, and the gain. (i.e., network operator (op) cost, (op) quality, and (op) gain).

• Customer has two criteria: the cost of accessing to the network operator and benefiting of such vCDN service and the satisfaction's index (QoE) in terms of its profile (i.e., end-user (u) cost and (u) quality).

The pseudo-code of the TOPSIS decision-making strategy is summarized in Algorithm 5. Hereafter we explain its main stages for better calcification. After defining the main criteria and alternatives related to the vCDN service migration, TOPSIS formulates the decision making matrix (d ij ) m n which should be entered as an input (Algo:5 line 1). Note that the network operator should enter dynamically the matrix values related to the importance of the criteria and according to its objective (e.g., minimizing the cost, maximizing the QoE, etc.). Further, giving the decision matrix, we calculate the entropy weight of each criteria (w j ) where;

(j 2 f1; mg) according to the Shannon theory that tells the maximum benefit weight of each criteria (Algo:5 lines 5 7). This value is needed then to calculate the weighted and normalized decision matrix (wr ij ) m n Algo:5 lines 8 11). Furthermore, we calculate the Positive Ideal Solution (P IS = Ideal+) and the Negative Ideal Solution (N IS = Ideal ) in order to choose the optimal criteria related to the alternatives (Algo.5 lines 12 and 13). Basically, the best alternative should be the closest to (P IS) and the farthest from (N IS). This optimal criterion is calculated according to the L2 distance. Then, we calculate the (p ) and (p+) that represent the L2-norm distances from the vCDNTTX position to the worst and best conditions respectively (Algo:5 lines 14 15). Finally, for each alternative a similarity function to the worst condition (Algo:2 line 16) is calculated and sorted in a list representing the ranked alternatives (Algo:5 lines 16 17). Then, the list is given to the network operator as an output in order to select the appropriate layer to where a vCDN should be positioned.

Layer selection

The output of our algorithm is an ordered list of alternatives. The layer selection method outputs a ranked structure list giving a rank to each alternative.

Through the proposed context (e.g., vCDN migration), TOPSIS selects the best layer (vCDNTTP, vCDNTTH, vCDNTTU or vCDNATO) in which we can run the optimization algorithm for migrating vCDN nodes. Note here that the run-time needed for selecting the optimal layer is in terms of a few seconds (30 sec as measured in next subsection) which valid the feasibility of the proposed method.

Layer evaluation

To evaluate our context with TOPSIS, we used the computing environment MATLAB. Fig. 7-1a depicts the decision making matrix. Fig. 7-1b and Fig. 7 In this live migration scenario, we can summarize the following tests as firstly shown in Fig. 7-2b. As long as we have increased the size of the virtual machine, we will need more time to finish the migration. Through these tests, we concluded that the time required for VM migration is different if the size of the machine has changed and if the communication speed is also changed. As a result, the time will increase in the case of live session migration with video streaming although the diffused video has the same size or length. We present in Fig. 7-4 the workflow that integrates the TOPSIS technique beside optimal and near optimal vCDN migration algorithms [START_REF] Ibn-Khedher | Scalable and cost efficient algorithms for virtual cdn migration[END_REF]. Integrating the proposed methods can follow this diagram with the main stakeholders as:

CDNaaS workflow

• Content provider (OTT/CP): The owner of the origin video content and want to create a vCDN network.

• CDN Brokers: It is service orchestrator that interacts with the network Operator of the infrastructure, triggering the deployment of vCDN. • OPAC and HPAC algorithms: They are respectively the implementation of the optimization algorithms in small and large scale network that optimize the vCDN placement and migration based on exact (optimal) and heuristic (near optimal) optimization approaches. The vCDNTTX deployment solutions assisted by TOPSIS method are responsible for deciding whether to extend the migration of vCDN nodes till the Home/User devices or not.

• Databases: mainly two DBs: i) retrieving the vCDN system and network parameters (InitialDB) and then ii) updating a (statusDB) that maps the current location of vCDN (e.g., on which PoP it is running).

• OpenStack: The NFV platform, KVM: The hypervisor and the accelerator of the CPU in the kernel space.

• H/W: The physical infrastructure that supports the virtualization tasks such as cloning, migration, etc.

For the sake of clarifying the sequence vCDNaaS workflow, we propose that firstly different content providers may request for the creation of vCDN services, then after the deployment and the orchestration of the vCDN nodes, the network operator may execute the optimize command according to the client group demands, therefore, the system fetches the operator databases to get the required information in order to launch in turn the optimize command. Then, the optimization algorithms decide where to place/migrate (OPAC/HPAC) the vCDNs and provide the system/operator the result. Finally, the system executes the migration process according to our results and releases the dedicated resources in case of Service Level Agreement (SLA) expiration/vCDN-delete-request.

To enumerate the main advantages of the proposed virtual CDN, we compare the proposal of (vCDN) to physical CDN (pCDN). Thus, we quote:

• pCDN relied on a pre-fetching process. This process locates video caches in caches nodes before that end user made a request. The process is based on statistics and on prediction modules. It is an off-line optimization. In vCDN, caching process is used but in proactive manner so that it uses mobility and Bandwidth prediction modules. Further, using OPAC placement module in the orchestration space, the optimization is dynamic and on-line. Therefore, vCDN is more flexible and can deal with live events, unexpected high traffic while pCDN is still dependent to the static configuration based on peak hours which is not reliable.

• pCDN uses algorithm with no migration support while in vCDN, benefiting from virtualization, migration is enabled. For instance, server, content, and session migration are three categories for migration.

• pCDN is a hardware based solution while vCDN is virtual/software based solution. Different acceleration tools are used either in kernel space or in user space. For instance, DPKD, KVM, and virtual switches are software packages to do this.

• vCDN can imply multiple paths between OVS switches and nodes. Therefore, it offloads as max as possible the load on the network infrastructure. On the other hand, pCDN using single path TCP, increases network overhead, doesn't resist failure and not implies any fault tolerance module.

Conclusion

This chapter proposed a multi-criteria decision making technique called TOP-SIS for selecting the optimal deployment layer of vCDN migration problem. Then, the proposed technique is integrated in a CDNaaS workflow for vCDN orchestration with respect to the previous chapters. Still, TOPSIS is an heuristic solution that can deal with large scale systems. Therefore, a multi-objective optimization problem formulation may be proposed in the future work to recommend optimal solutions and assess the efficiency of TOPSIS.

In the next chapter, we are going to study complex active networks and see if traditional optimization constraints or multi-criteria methods are still valid.

Chapter 8

Service placement in complex active networks

Introduction

This chapter deals with the optimal planning of complex active networks.

Complex networks [START_REF] Erciyes | Complex Networks: An Algorithmic Perspective[END_REF] Information-Centric Networking (ICN) [START_REF] Pentikousis | Information-Centric Networking: Baseline Scenarios[END_REF] to serve video content distribution (caching) [START_REF] Mueller | Adaptive Video Streaming over Information-Centric Networking (ICN)[END_REF] [108] and IoT [START_REF] Zhang | ICN based Architecture for IoT -Requirements and Challenges[END_REF]. Complex active networks inherit the challenges of both of these networks which that make their evaluation or simulation/optimization problematic. Applying exact optimization techniques to the planning of these networks is not efficient due to their large sizes and the introduced by dynamic components. Still, we need to have some abstract methods and tools for network optimization and control of such important applications.

Network optimization can be easily modeled with classical tools or heuristic vertical layers within a node. Therefore, the conventional methods that can be used to optimize the graph are not anymore valid and we need to look for a more realistic optimization method that can take the third dimension into account.

Fig. 8

Related work

The main related work on cut-tree (Gomory-Hu1 ) algorithms are quoted in this section.

Ford Fulkerson [START_REF] Ford | Flows in Networks[END_REF] solves the problem of the maximum-flow between specific s and t nodes in the graph G and introduced (and proofed) the theorem of maximum-flow minimum-cut that indicates that the (s; t) maximum-flow (the maximum amount of flow that can be transmitted from s to t) is equal to the (s; t) minimum-cut (the minimum total weight of the edges that can separate (disconnect) s from t in G.

An Extension to the Ford Fulkerson method that solves the problem of the maximum-flow between a specific (s; t) vertices in the graph is the multi-terminal maximum flow problem that focuses on computing the maximum flow between all network nodes. It is originally studied by Gomory and Hu [START_REF] Hariharan | An Õ(mn) gomory-hu tree construction algorithm for unweighted graphs[END_REF] who propose a cut tree that concisely expresses all minimum cuts (maximum flows) of a given graph.

The authors demonstrate that there are only (n-1) non crossing edges representing this computation instead of n (n 1) 2

where n represents the set of network nodes.

Hence, the algorithm complexity is (n-1) min-cut computations. The baseline of the G-H idea is the concatenation process used for avoiding crossing and compute the s t min-cut values.

Dan Gusfield [START_REF] Gusfield | Very simple methods for all pairs network flow analysis[END_REF] proposes a simplification to the G-H algorithm by adding at least a three lines of code. The algorithm does not need to ensure (maintain) (n 1) non-crossing edges for constructing the cut tree and hence the algorithm complexity is reduced. Despite that, network target of the aforementioned algorithm is a communication network [START_REF] Hariharan | An Õ(mn) gomory-hu tree construction algorithm for unweighted graphs[END_REF] where main links load is uncertain and unknown in such cases, edge capacity is fixed and entered as an input beside the original graph in all the above methods and algorithms. Then, network modification and especially in the link capacity should be taken into account in the network flow algorithms.

Authors in [START_REF] Goldberg | A natural randomization strategy for multicommodity flow and related algorithms[END_REF] introduce an experimental study of the main cut tree algorithms described above (G-H and Gusfield). Then, in the spirit of Gomory Hu theorem, they proposed a fast implementation of the G-H tree comparing to the Gusfield method where the original Gomory Hu algorithm complexity is reduced. This fast implementation is due to the combination between the original G-H with some heuristics. In fact, authors through their experimental study try to incorporate some heuristics in the traditional implementation of G-H (not in the simplified G-H algorithm of Gusfield). Heuristic methods are implemented for picking the next (s; t) source-sink pairs in the original G-H algorithm where these vertices are chosen randomly.

T. Hartmann et al. [START_REF] Hartmann | Dynamic gomory-hu tree construction -fast and simple[END_REF] highlight cut-tree algorithms among the main network reports that help for network analysis and detection. They implement a fast and T. Akiba et al [5] raise another problem related to the construction of cut trees and propose an efficient G-H construction algorithm for today's large-scale graphs.

However, authors do not consider network load modification (remaining arc capacity) in their novel method which represents a main limitation of the work.

Background

Several algorithms have been proposed to optimize the planning and operation of complex networks in polynomial time. We proposed to use G-H algorithm to efficiently find the minimum cut in large video distribution networks that correspond to carrier grade service infrastructures. The proposed algorithm (HPAC in the chapter) is used in two steps. First, we find the G-H tree transformation of the initial graph and then we explore the unique shortest path from an access point to the server containing the vCDN. Thus, when the demands cannot be anymore served because of the bandwidth restrictions in the resulting tree, we migrate the vCDN server to the first node in the tree that does not create any conflict on the tree nodes and links.

Given the importance of the G-H transformation in network analysis, and believing that the network has to consider different intrinsic parameters that follow its behavior (network of distribution, processing, on demand services, etc.) this G-H has to take into account all these parameters to build an efficient network optimization algorithm. In the next two sections, novel network models are highlighted and detailed through a network's use case.

Complex active networks

Complex Active Networks (CANs) are novel concepts to networking architecture that allow intermediate nodes to process (enhance/downgrade) on the fly the real-time traffic flowing through them using external bandwidth amplifiers or power indicator tools.

CANs can be modeled through three main classes: i) Erdos-Renyi-based random models that target geometric graph and follow a linear degree distribution (P (k) = k n ), ii) Watts-Strogatz-based small world models that target large network size and follow a binomial (or a Poisson) degree distribution and ii) Barbasi-Albertbased scale-free models that target also large network size (suitable for distribution network) and follows a power degree distribution (p(k) = k ; 2 < < 3).

To date, these models still represent the baseline tools for network graph generation that target complex active networks. Moreover, CANs pose different problems and introduce serious challenges such as: link capacity prediction, network partitioning, and so on.

Novel use cases of CANs have been highlighted. We quote Information-Centric Networking (ICN) [START_REF] Van Jacobson | Networking named content[END_REF], Hadoop, and Internet of Things (IoT) [START_REF] Zhang | ICN based Architecture for IoT -Requirements and Challenges[END_REF]

Information-Centric Network

ICN names the content rather than the host in the networking level. Different ICN architectures are proposed such as: network of information (NetInf)

[126], content centric networking (CCN) [START_REF] Ccn | The ccnx project, parc a xerox company[END_REF], and data oriented network (DONA).

Most of these information-centric network architectures are implemented on top of TCP/UDP/IP/P2P layer. All of them are inspired from by the Google talk of van Jacobson [START_REF] Van Jacobson | A new way to look at networking[END_REF] who introduced the baselines and the fundamental features of the CCN architecture (node model, naming, routing, transport, caching, etc.) and the strategy layer for the adaptive forwarding.

Hence, CCN represents the baseline ICN architecture as a new look at networking for reshaping messages based on their names (name-based routing) pioneered by Van Jacobson in PARC [START_REF] Van Jacobson | Networking named content[END_REF]. In CCN, names are hierarchical and similar to URLs. Name resolution system (NRS) and data routing procedures are either integrated or coupled. The exchanged messages between consumers and producers are in the form of interest (question) and data (response). Indeed, end-users express only what they want (content name), and they let the CCN network respond to the where and how the content will be retrieved implicitly. Therefore, an appropriate CCN topology planning and dimensioning is an optimization per se. In fact, CCN network consists of consumers that request the content, producers that publish this content, and ICN routers that cache and ask for the content on behalf of the consumers. The content router (CR) of ICN has three main data structures as follows: i) Forwarding Information Base (FIB) table: it binds the content name to next hop as in IP layer that binds the IP prefix to the destination, ii) Pending Interest Table (PIT): it binds the content name of the unsatisfied requests to the requesting face, and iii) Content Store (CS) table: it binds the content name to the data per se.

Caching in CCN implies the on-path caching. CSs use by default the LRU replacement policy. Off-path is also supported by redirecting user interest to a CDN (as an example) and not to the source/publisher of the content. Mobility is handled by Kite model as mentioned in UCLA work [START_REF] Zhang | Kite: A mobility support scheme for ndn[END_REF]. Security is assured through binding name to the content by crypto signature field in a CCN data packet.

CCN brings many advantages. Indeed it assures an efficient content distribution. Further it implies cache consistency using unique named data object (NDO) and resolving by this way the problem of content moving (the content is independent from the storage and the location). It breaks the End-to-End security model and secures the content rather than the host through data integrity using hash function and Origin verification.It facilitates mobility, multi-homing (multi network access ) by just re-issuing requests for NDOs. Finally, it leverages hop-by-hop transport model as in Delay Tolerant Network (DTN) scenarios.

Problem statement and contributions

Negative resistance situation: We face this situation when the consumer demands going through the resulting G-H tree cannot be satisfied anymore. We demonstrated through a virtual Infrastructure Optimization Simulator (vIOS) 2 , implemented for deploying different vCDN/ICN functions, that a negative situation is occurred and there is a need to migrate a group of delivery functions to optimal data center locations. More precisely, given the high migration cost in CANs, our research problem is how to model the network infrastructure after adding active nodes in a complex graph and how to optimize the network planning and service placement in presence of these active nodes.

Our modification to G-H considers modeling the network infrastructure in the presence of active nodes that act as if they provide additional (or consuming) bandwidth in the transport network (e.g., by modifying the throughout traffic on the fly, adding advertisement, executing binary codes for computation, annotated video, augmented reality, insertion on the fly, etc.). Users requesting a critical service (e.g., public safety), or a real time service should be satisfied in an optimal time according to the application using the active networking facilities. The research objective is to leverage ICN caching and processing capabilities to propose scalable, optimal, and adaptive service placement algorithms of ICN nodes in CANs.

Active node budget

The dynamic nature of intermediary nodes, that can provide extra work during a session has to appear in the optimization process. We propose a budget in each node (less or greater than the unit). It can be passed onto the node links as an extra capacity. The introduced budget represents a flow multiplicity as follows: In Fig. 8-2, we give an example of active node budget mapping where a budget 2 of the server 2 is passed onto its outgoing links. The outgoing link weights of the server (X and Z) representing the residual flow are amplified by 2 .

Let us Know generalize the budget formulation. Suppose that F + and F are the outgoing and incoming traffic from an active node a 2 A. The traffic can be modeled as follows: 8a 2 A; l 2 + a : F + a = P l F(a; l) and 8a 2 A; l 2 a ; F a = P l F(l; a) where + and are the set of the in-degree and the out-degree of the active node a respectively.

Due to the work and effort that an ICN may introduce in the network there is no more flow balance at an active node. Hence, the adjusted Kirchhoff (flow balance) equation at each active node will be:

8a 2 A : F + a = F a
Where is a real number ((> 1) for flow augmentation and (< 1) for flow diminution) that represents the dynamic work inside an active node. This equation will also introduce a non conservation of all the network traffic (i.e., the sum of all outgoing traffic will be the sum of all incoming traffic multiplied by the budget ).

OPPA: Optimal Practical Placement Algorithm for ICN

We propose OPPA, an exact optimization algorithm that takes as an input the topology of the underlying network. It aims then to optimally upgrade some nodes by deploying ICN software (placement problem). The network flow problem dif-fers from the classical theory in order to model complex active networks where there is no more flow conservation at each node. The flow model is then used to solve a placement problem constrained by topology related parameters and budget parameters that determines the network operator capacity. The adjusted network flow model between each source-destination (s,t) (from s to t) node pairs is:

P j2 + (i) F i;j P j2 (i) i F j;i = 8 > > > > > > > > < > > > > > > > > : 0 if i s; i t A s if i = s B t if i = t
where A s and B t represent the quantity of flow streamed by the source s and received by the destination t. Non flow conservation implies that (A s B t ) for flow amplification and (A s B t ) for flow degradation.

ICN budget model

We formulate an Integer Linear Programming (ILP) to optimally model the ICN active network, and is shown below:

max X s2S;t2T F s;t (8.1)
Subject to: . The inserted amplification is positive and is constrained by the maximum node budget (Eq. (8.5) and Eq. (8.7)). Network operator also can not invest more than its total budge (Eq. (8.6)). It ensures the bandwidth amplification, capacity constraint, budget constraint, non-negativity budget, etc.

X j2 + (i) F i;j X j2 (i) i F j;i = 0 (8.2) X j2 + (s) F s;j X j2 (s) s F j;s = F s;t (8.3) 8i; j 2 S : F i;j i C i;j (8.4) 8i 2 S : i B i (8.5) X i2S i B (8.6) 8i 2 S : i 1 (8.

OPPA

We propose to enable only ICN nodes to modify the throughout traffic between all (s,t) node pairs. To do this we use the following flow balance constraint that determines an optimal placement of ICN software that enhances the streamed traffic between the producer p and the consumer c on the fly:

The OPPA based on the ICN's budget model is listed below:

min X s2S X f 2F x s f t s f (8.8)
subject to:

The equations (8.5), (8.6), and (8.7)

X j2 + (i) z v;f i;j X j2 (i) i z v;f j;i = 8 > > > > < > > > > : x i f if i v 1 if i = v (8.9)
i; j) is used to stream f to v 8s 2 S : y s v;f x s f (8.10) 8v 2 V j d f v 0 : X s2S y s v;f = 1 (8.11) 8s 2 S : X v2V X f 2F y s v;f d f v D s (8.12) 8s 2 S : X f 2F x s f f size C s (8.13) 8i; j 2 V [ S : X v2V X f 2F z v;f i;j d f v L i;j (8.14) 8i; j 2 V [ S : z v;f i;j i L i;j (8.15)
The above formulation of the network problem is optimal. However, it is an NPhard problem. Therefore, an extended cut tree algorithm is formulated (EGHT)

and used as input in our proposed HPPA algorithm (heuristic) that solves the negative resistance problem defined above.

HPPA: Heuristic and Practical Placement Algorithm for ICN scenario

Our proposal is based on the extended G-H of the initial network (represented by access, aggregate and core nodes). In other words, HPPA transforms the input network into a G-H tree. Then, upgrading some nodes by ICN software is performed thanks to our extended G-H tree allowing to efficiently reduce the number of edges to be considered when upgrading nodes, placing contents (in-network caching feature of ICN), and end users redirection to the optimal ICN (on-path caching).

Algorithm 6 summarizes the pseudo code of HPPA. Hereafter, we describe these main stages.

HPPA is the algorithm used for negative resistance networks (e.g., face to unexpected increase in consumer demands) and hereafter we explain how it works. Output: An Extended Gomory Hu Tree EGHT = (V (GHT ); E(GHT )) 3: V (GHT ) = V (G), E(GHT ) = ; 4: Initialize the tree: every edge points to node 0 5: For each source vertex except vertex zero, Find its neighbor 6: Find the minimum cut between s and t with the installed capacity 7: Find the minimum cut between s and t with the amplified capacity. 8: Update the tree 9: Construct the tree 8.6.1 EGHT: extended Gomory-Hu tree algorithm Our extension to the traditional Gomory Hu tree is to construct two cut-trees given the initial topology graph. Our implementation of EGHT is inspired from the Gusfield simplification of G-H tree where there is no need to maintain noncrossing edges in computing all the (s; t) min-cuts. This algorithm is optimal in the sens that is provides the maximum flow computation for all node pairs. It is entered as an input to any transportation problem related to CANs to resolve placement issue, network load reduction, and e-e QoS/QoE and so on. Hereafter, we propose an utilization of this EGHT to resolve representing the maximum flow value (W min s;t ) and its potential amplification W max s;t receptively.

Thirdly, consume demands method is invoked. In this step, all the consumer demands (e.g., ICN interests) are consumed by the two trees and consume the network capacity (of course system capacity is consumed also).

Then, we construct a consumed EGHT. At this step, a consumed EGHT is constructed and represented by two consumed G-H trees that has the remaining network capacity after that all the consumer demands have been satisfied. Further, a ranking-edges is performed. In this step, we rank the edge weights from increasing.

For each consumer demand, a shortest-path is found from the consumer's location to the provider on the original graph. The network links in this shortest-path have their capacity consumed to satisfy the demand bandwidth. After that all the demands have been analyzed, some of the network links will have no remaining link capacity (i.e.; (W min s;t = 0), some other links will have negative remaining link capacity (i.e.; (W min s;t < 0), and other links will still have. Otherwise, if all links have remaining capacity, it means that the network can easily serve all the consumer demands and there is no need to downgrade and upgrade some nodes with CCN software. Furthermore, enhance-Amplify process is triggered. This step is occurred When negative link is detected. It upgrades some server nodes with ICN software (e.g., CCNx) that amplify the maximum outgoing flows (from s to t). Sometimes, a downgrade process is needed. This step is occurred When positive link is detected. It means consume a set of the incoming flows to save network bandwidth.

The Return-ICN-Maximum-Flows method returns the maximum flow between all the node pairs in presence of ICN active nodes. Then, we enable the in-network feature of ICN which means the capability of a router to cache a requested content.

Next end users are redirected to this ICN active node.

In-network caching: The decision to amplify the bandwidth and cache the ICN data takes the following logic: First of all, every consumer demand is re-analyzed to verify if it traverses a saturated (s; t) link (negative link capacity). If it does, then a bandwidth amplification is needed. If there is an intermediate node in the demand path that can hold the requested ICN data (using the needed capacity values set for the ICN data and the current available resources and if the intermediate node has the network/system capacity to hold the streaming source (by calculating the difference between the installed bandwidth and the currently used bandwidth), then an amplification is occurred and its cost (hosting cost) is calculated.

However, if the ICN caching would take place between the producer and the consumer, all the other consumer demands requesting the same ICN data from the original producer would have to be satisfied (served) from the new ICN node (in-network caching feature of ICN) in the case of off-path caching, otherwise, the original producer will serve the requested data. Update-service-placement: The algorithm is dynamic in the sens that it updates the database of each ICN node (i.e., its content store). Novel demands benefit from the in network caching and increase the bandwidth gain. Indeed, ICN nodes become the producer of similar interests. We propose the following example (see Fig. 8-3) to illustrate ICN algorithm for treating judiciously ICN streamed data. It depicts a scenario of ICN insertion. In this scenario, consumers representing aggregated interests for a media data stored in media source repositories with a specific throughput (i.e., content quality) equal to 40 Mbps. The proposed ICN method searches to adapt the bandwidth capacity along the shortest path from consumers to publishers. Active ICN software are inserted in nodes 1 and 2 to enhance network capacity. In order to assess OPPA and HPPA algorithms in a small scale scenario, we used runtime, treatment cost and parallel task number as our performance key metrics.

Large scale scenario: a Barabási-Albert based network operator

In large scale network, we evaluated our HPPA algorithm using scale free topology. According to the IETF, Barbasi-Albert-based scale-free network may be a suitable solution for evaluation ICN in large scale [START_REF] Pentikousis | Information-Centric Networking: Evaluation and Security Considerations[END_REF]. The scenario relies on the

OPPA vs HPPA comparison

A brief comparison between the two approaches is given in the Table 8.2 .

Conclusion

This chapter presents a novel use case of complex active network based on ICN approach. Intermediate nodes are active and treat the data on the fly. Network optimization is modeled and quantified. Results are encouraging and proof that consumer delay is reduced and the network performance is enhanced under our defined key performance metrics. To provide a real networking tool, the decision of downgrading and enhancing the outgoing flows should be fully distributed.

Therefore, in the next chapter, we provide an enhanced version of network flow algorithm called maximum concurrent flow. Then a distributed version is implemented, tested and evaluated.

Chapter 9

Conclusions and Perspectives

Conclusions

In this thesis, we have studied virtual content distribution networks and answered to several problems that have arisen in the state of the art such as how, what, where, and when virtualize and optimize. Since this network helps to improve (optimize) end-user satisfaction, virtualization has been combined with optimization and several algorithms have been provided that can be applied to different networks.

Moreover, we contribute by a virtual infrastructure optimization simulator (vIOS): a high level application that optimizes vCDN services planning in both simple and complex active networks.

Perspectives

In this thesis we used exact and heuristic methods for software resources management. In next network generations, we have a lot of data, a great capacity of computation which favors the use of artificial intelligence techniques instead of building complex mathematical models.

185 m (e.g. with minimum utility) that is currently stored at node I, then replace item m by item n)

2. Multiple caches: Fan et al. [START_REF] Fan | Summary cache: A scalable wide-area web cache sharing protocol[END_REF] described another alternative to the previous approach also called summary caching. In this protocol, every caching disposes of a table of summaries related to each proxy server. Cooperation of several caches can reduce the total traffic but it suffers from service availability (miss content scenario). This happens when neighbor cache servers do not have the content. Further, this approach requires extra bandwidth when a cache server serves the cache's misses of the others.

Hierarchical caching: This caching technique is based on placing nodes of

caches in different levels of network structure (level1 core network, level 2 edge network level 3 access network). The first hierarchical proposal is probably the one in [START_REF] Leff | Policies for efficient memory utilization in a remote caching architecture[END_REF], where authors describe their time-based protocol aiming to solve hierarchical placing problems (HPP). This protocol may enhance the hit rate of a document. However, this hierarchical view increases the total latency because each level of the hierarchical caching structure introduced its latency. Further, storing documents in different level overloads the network and then decreases the quality of experience perceived by the user.

4. Distributed caching: Distributed caching algorithms place caching nodes only in the edge of the network and those nodes are the only ones that can cooperate in the distributed process. This algorithm is better than hierarchical caching as it is shown in [START_REF] Rodriguez | Analysis of web caching architectures: hierarchical and distributed caching[END_REF] because it reduces the total latency, decreases the load and the required bandwidth. All this is through the use of a single level of cache. The author also introduced another approach that mixes the two previous algorithms called: "Hybrid Caching System". We have to highlight here, that in the distributed caching; one can face some problems such as difficulty in updating caches because of the use of a single level cache (long network distance) as it shown in [START_REF] Yu | A distributed adaptive cache update algorithm for the dynamic source routing protocol[END_REF] and [START_REF] Laoutaris | Distributed selfish caching[END_REF].

5. Hybrid caching: In the Hybrid caching approach [START_REF] Rodriguez | Analysis of web caching architectures: hierarchical and distributed caching[END_REF], authors propose to place a minimum number of nodes at the edge of the network. This approach reduces latency, load and bandwidth but suffers from the lack of protocols for managing caches. They also require complex topologies that cannot fit with other scenarios.

6. En-route caching: En-route caching [START_REF] Tang | Coordinated en-route web caching[END_REF] is an approach that intercepts the requests from the user and when the content is in the local cache of the interceptor, it answers the requester by sending the content. It leaves the request otherwise unchanged. This operation has some advantages [START_REF] Tang | Coordinated en-route web caching[END_REF]. The most important one is that it decreases extra overhead. Authors do not say how the cache is filled originally. Therefore, this technique is not sufficient because they do not consider video popularity that should be only filtered by those cache nodes. It suffers also from the fact that many CDN operators encrypt the original request so as to prevent such operations and to keep the hand on the process (Youtube).

7. Cache cluster: Borst et al. [START_REF] Borst | Distributed caching algorithms for content distribution networks[END_REF] introduce an algorithm for caching services to minimize bandwidth cost instead of latency in [START_REF] Yeung | Hierarchical content routing in large-scale multimedia content delivery network[END_REF] and [START_REF] Rodriguez | Analysis of web caching architectures: hierarchical and distributed caching[END_REF]. They use the hybrid caching structure. The replication strategy uses cooperation and has two different scenarios, intra-level cache cooperation and inter-level cache cooperation. The first is based on Local greedy algorithm described above while the second is a more simplified version of the greedy algorithm. Borst

shows that the adopted algorithm improves cache performance but it does not take into consideration delay, QoE, network load which are important parameters/metrics for service video delivery optimization. Furthermore, they focused on a specific topology (they are not taking into account a general network topology) which made their solution fit only with such scenarios.

A.3 Indirect caching

In the indirect caching, caches are hosted by another operator. We can enumerate under this category the following techniques:

1. Collaborative cache mechanism based on resources auctions: Core networks in cellular systems manage their local subscribers and have their profiles. Jie et al. [START_REF] Dai | Collaborative caching in wireless video streaming through resource auctions[END_REF] introduced a new caching mechanism for collaboration between multiple Wireless Service Providers (WSPs). This collaboration is based on resource (Bandwidth) auctions. They propose that cache servers be deployed at Mobile Management Entities (MME) or Mobile Switching Center (MSC) so as to decrease the distance between contents and end users. This approach can enhance the QoE and maximize the response time for end users but it is inapplicable because of dynamicity of subscribers.

2. Content aware caching: Meghana et al. [START_REF] Amble | Content-aware caching and traffic management in content distribution networks[END_REF], start from the idea that cache sizes and link capacity are limited. Thus, she gives four techniques to properly manage the caches so as to minimize the response time for users:

• Technique 1: Periodic Max-Weight algorithm with random eviction.

• Technique 2: Iterative Max-Weight scheduling with Min-Weight Eviction Policy.

• Technique 3: Iterative Periodic Max-Weight algorithm.

• Technique 4: Iterative Periodic Max-Weight with Min-Weight algorithm.

3. Peer Aware Content Caching (PACC): Bjorkqvist et al. [START_REF] Bjorkqvist | Minimizing retrieval cost of multilayer content distribution systems[END_REF] introduce this approach to be dedicated to Content Distribution Networks (e.g. AKAMAI).

The advantage of this approach is that it has not been oriented to a specific topology. It divides the network to three layers: two vertical layers and one horizontal layer. They also propose two policies PACC-AR and PACC-CL to execute the caching mechanism between peer nodes. This approach has some disadvantages as it does not take into consideration video popularity for cache management and cache update processes.

4. Cooperative Hybrid caching strategy for P2P Mobile Network: Mo Zhou et al. [START_REF] Zhou | A cooperative hybrid caching strategy for p2p mobile network[END_REF] designed a caching system to optimize network bandwidth and guarantee high response time to mobile users in order to increase the QoE and the overall QoS. The introduced technique is based on two strategies: single greedy caching strategy and cooperative hybrid caching strategies. It is shown that the second strategy outperforms the first one in some cases. The structure used in this approach is not hierarchical or tree topology based but P2P. As authors focus on optimizing the traffic over the network, the caching strategy takes into account fvideo popularity, distance, video sizeg as metrics for the optimization. Cache replacement (eviction) procedures are managed through the single greedy caching. Cooperative hybrid caching is based on popularity of video content. This technique requires high computing and does not take into account user satisfaction. Moreover, authors do not give a clearly popularity function. Furthermore, they do not account for extra bandwidth needed to seek the closest desired video. requires high computational overhead and extra bandwidth to calculate the instantaneous value of the popularity.

2. Cache as a Service (CaaS): Cache as a Service [START_REF] Georgopoulos | Cache as a service: Leveraging sdn to efficiently and transparently support video-on-demand on the last mile[END_REF] is a new caching technique for fetching requested items and moving them to end users. The results showed that this approach improve network utilization and user QoS.

However, it requires a predefined architecture in order to deal with NFV and SDN technologies. The summary is in Table B.1.

B.2 Server moving replication

We will present in this subcategory the pertinent replication techniques in the literature.

1. Replication Algorithm with Load Balancing (RALB): In [START_REF] Zhou | On replication algorithm in p2p vod[END_REF], authors proposed the replication algorithm RALB to enhance video adaptation to the available bandwidth. This approach is based on content replication in P2P systems for video on demand scenarios. Peers store some movies in order to increase network bandwidth and reduce server's load. Authors use random replication assisted with load balancing. Firstly, they introduced a centralized approach where video replication is static. Then, they add a reactive and distributed algorithm in which peers decide, based on video popularity, to either store or discard the movie. Hence, the replication is amended after any peer views video. Therefore, this mechanism adapts to the dynamicity of nodes and peer churn. However, the authors did not specify neither the video popularity function used nor the cache update mechanism which are most important in video caching.

2. Optimal Replication Strategy ORA: Weijie Wu et al. [START_REF] Wu | Exploring the optimal replication strategy in p2pvod systems: Characterization and evaluation[END_REF] introduced ORA strategy which requires knowledge of video popularity. This approach addresses two issues. The first addressed the optimal replication ratio while the second addressed how to do this replication? Results showed that the algorithm increases optimality when we replicate more popular video and remains sub-optimal like proportional replication strategy. Authors showed that their technique reduces the cost and enhances the access latency.

5. Two-Level Result Caching (TLC): Erica et al. [START_REF] Rosas | Two-level result caching for web search queries on structured p2p networks[END_REF] introduced the problem of load balancing which can be defined as: where should we place the replica? [START_REF] Zhou | On replication algorithm in p2p vod[END_REF] Video adaptation Video popularity Increases computational load ORA [START_REF] Wu | Exploring the optimal replication strategy in p2pvod systems: Characterization and evaluation[END_REF] Gives popular videos

Replication threshold

Not fit with proportional replication HB-CDN [START_REF] Chellouche | Home-box-assisted content delivery network for internet video-on-demand services[END_REF] Reduce server's load, load balancing Load Extra time delay RBS [START_REF] Wu | On incentivizing caching for p2p-vod systems[END_REF] Increase satisfied user as possible Reduce the cost Miss QoS, high price TLC [START_REF] Rosas | Two-level result caching for web search queries on structured p2p networks[END_REF] Manages the cache

Cache position

High delay required PRA [START_REF] Tewari | Proportional replication in peer-to-peer networks[END_REF] Reduces server's load

Network bandwidth

Video popularity is not considered LAZY REPLICA [START_REF] Cheng | A framework for lazy replication in p2p vod[END_REF] The result shows that in small scale, the loose replication approach is slightly efficient in term of migration cost comparing to the static replication one. This is because in the case of one replication, the minimum distance between s f and s is great and therefore, the migration cost will be significant. In the other hand, in loose replication, we replicate more than one time, but there is no need to reach the access layer for example. Recall that we have focused on minimizing the migration cost and not the content retrieval delay or the response time.

Moreover, the total number of replica is measured as follows:

Replica number = X s2Snfs f g X f 2F x s f (C.2)
In strict replication, the replica number is less or equal to jFj while in loose replication scenario, which is the most efficient in terms of migration cost and network resource saving, the replica number is variable in response to the change in client group demand matrix defined above d an extra-constraint for limiting the replica number ? and is it efficient or not ? A first answer to this question could use an additional constraint as follows:

Replica number = X s2Snfs f g X f 2F x s f R f (C.3)
Where R f will be the maximum replica number of vCDN (f 2 F).

Therefore, such an open question may try to find the appropriate R f that can be fixed in the mathematical model ?

C.2 Conclusion

Two approaches for OMAC are proposed and results show that loose cache replication/migration algorithm is slightly more efficient.

is a centralized, decentralized, or distributed reservoir of networking and processing for concurrent flows. The objective is to maximize the throughput of traffic. Based on the underlying networking, the heuristic relaxation solution that iteratively pushes small/large amount of flow within the network is the main approach in MCF problem.

2. Distributed approaches follow the same logic to solve the problem but in a cooperative manner between processes installed on different node locations.

Still, the objective these approaches is to maximize the minimum and common fraction that satisfied the demands of each commodity. In approximation algorithm, a feasible concurrent flow vector is pushed initially from sources to destinations. Then, the approximate value of MCF is:

(1 + ")
Where is the exact MCF solution, "is the approximate parameter.

Among the main MCF approximation algorithms, we quote the primal-dual approach proposed by Danzig. Different works are also proposed in this field. Indeed, Shahrokhi et al. [START_REF] Shahrokhi | On solving large maximum concurrent flow problems[END_REF] propose the maximum concurrent problem with uniform capacity and exponential length metric. The proposed algorithm is initiated by choosing a length function (l(e)) and finding an initial feasible flow vector (generally a small amount of flow that can be routed concurrently). Then, a shortest path in terms of the proposed length function is found for each entering commodity. The algorithm then does a rerouting to the flow. It terminates in O (" n m 7 ).

Klein et al. [START_REF] Klein | Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts[END_REF] then proposed a faster algorithm with a different length function.

Using the amended length function, a larger amount of flow is sent by iteration.

Leighton et al. [START_REF] Leighton | An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms[END_REF] generalizes the MCF solution considering arbitrary edge capacities and demands.

We highlight also the work of Garg and koeneman [START_REF] Garg | Faster and simpler algorithms for multicommodity flow and other fractional packing problems[END_REF] that leverages the primal-dual method, the method of Karakostas [START_REF] Karakostas | Faster approximation schemes for fractional multicommodity flow problems[END_REF] that aggregates a set of commodities by the source, and the flow deviation method which is introduced by (c(e) f (e)) 2 . Note that the approximated solution not only depends on the " parameter but also on the size of the system inputs.

D.3 MCF computing models

MCF is a network flow problem which can use different computing models. In this section, we detail these frameworks.

D.3.1 Centralized MCF models

The idea in MCF centralized method is to have a super node acting as a traffic engineering server that routes the demand from production locations to appropriate destinations. Super node may use different heuristics to find approximate solutions for the MCF problem. It can iteratively add small amount of flow (incremental method) or it can add large amount of flow, then it redistribute (reroute) the flow from the most congested (loaded) edge/path to the less congested one.

In centralized computing, super node machine executes only one MCF instruction at a time. Giving this requirement, single CPU and RAM are allocated to execute the sequence of MCF instructions sequentially. Parallel computing for solving the MCF problem is beneficial in the way that multiple processors (CPUs) and RAMs collaborate to execute the set of the MCF instructions in parallel. Note that parallel computing use also one machine to execute the MCF problem.

D.3.2 Distributed MCF models

In the state of the art, we found a few relevant algorithms that aim to solve the distributed MCF problem (DMCF) (i.e., MCF in a distributed manner). In the classical DMCF, such an algorithm inheres the same baseline mathematical formulations of the multi-commodity flow problem. Then, the decision of forwarding the flows of the commodities is taken by local nodes (computing units) as proposed initially by Awerbuch et al. [START_REF] Awerbuch | Greedy distributed optimization of multi-commodity flows[END_REF]. Then, they improve the classical approach and present a novel decision model for the DMCF based on the multi-agent system or the billboard model [START_REF] Awerbuch | Distributed algorithms for multicommodity flow problems via approximate steepest descent framework[END_REF]. Computing units representing the agents that are responsible for commodities. In the billboard, each agent can read the total edge flow within the network in an algorithm round r, which is the sum of the edge flows of each commodity. Each agent then has information about the total edge flows and writes the next edge flow (to be routed) of its commodity in the next round r + 1. The complexity of this method is linear with the maximum path length size.

In the aforementioned distributed computing models, multiple machines (CPU, RAM) collaborate to solve the DMCF problem (DMCFP). Two types of communication between these machines are presented in this computing model: 1) communication using messages and 2) communication using a shared middleware. In each communication model, two main execution models may be presented: synchronous or asynchronous models.

Hereafter, we detail the main distributed algorithms which deal with the MCFP.

Local decision based DMCF

In this approach, the decision of routing network flows on an edge is taken locally by intermediate nodes. Network nodes balance the flow on its corresponding edges. The process ends in determined number of phases as proved by Awerbush et al. [START_REF] Awerbuch | Greedy distributed optimization of multi-commodity flows[END_REF]. The main algorithm works as follows: In the first phase, each source pushes (1+") d i i amount of flows on each of the i edges incident to each source S i .

Then, some instructions should be executed at each node which is very costive. Therefore, the following approach for the decision is introduced, the global decision.

Global decision based DMCF

In a Global decision based DMCF, a decision is related to each commodity. A multi-agent framework is used to solve this distributed problem rather than local decision procedure as defined above. Each agent is responsible for routing the flow of its commodity taking into account the current congestion (load) on each edge. O (1) ) where H is the maximum allowed path length.

As differentiation to all the previous flow control algorithms established for the TCP/IP stack (additive increase in the windows size representing the maximum of the allowed packets that the sender can send to the receiver), authors use here a multiplicative increase process which is more aggressive than the decrease. Their objective was "resource allocation in decentralized network architecture". Authors affirm that different compete applications over a shared network resources can be solved in greedy manner. Indeed, they enhance the current flow control (TCP) and the routing (IP) mechanisms based on shortest path calculation in terms of hops (TTL) because it does not guarantee the optimization of resources in a scenario of concurrent flow and demands. To deal then with this hard problem (MCF), authors propose a novel routing metric (link cost) that depends on the congestion that runs on an edge (i.e., the load). This routing metric may identify the network bottleneck (sparsest cut problem) and then ease the maximization of the concur- complex and uses oblivious routing as a basic tool but also requires many concepts (flow sparsification, electrical flow, solving Laplacian systems, etc.) but it seems very promising for the practical solving of routing problems in networks.

H. Räcke et al. [START_REF] Räcke | Minimizing congestion in general networks[END_REF] introduced the concept of oblivious on-line routing in which each origin-destination request is routed without any knowledge of the state of network congestion. The surprising result is that there is such a routing mechanism for which the network congestion is not more than 0(log n) of the optimal congestion. This work is interesting in more than one way: on one hand, because on-line routing gives a benchmark on the quality of the dynamic and distributed routing, and on the other hand, because this benchmark is relatively robust and good. Unfortunately, the method proposed in [START_REF] Azar | Optimal oblivious routing in polynomial time[END_REF] to calculate such routing requires solving NP-hard problems. This algorithmic complexity is reduced in [START_REF] Azar | Optimal oblivious routing in polynomial time[END_REF] to a super-linear polynomial complexity, which remains crippling for large networks. The notion of oblivious routing can also be analyzed in the context of robust routing, where one seeks to calculate an optimal routing when the demands are uncertain [START_REF] Applegate | Making intra-domain routing robust to changing and uncertain traffic demands: Understanding fundamental tradeoffs[END_REF].

D.4 How to execute DMCF

In DMCF, each processor has its local memory and it is responsible for executing a part of the DMCF algorithm. Basically, the algorithm is executed after a terminating a set of phases. In each phase, we have the notion of round or steps.

The execution of the algorithm instructions may be fully or partially synchronized or asynchronous.

In synchronous execution, each processor has its local memory and it is responsible for executing a part of the DMCF instructions.

f p 0 p 2 P (D.4)
where is the throughput and f p is the amount of flow on path p. Constraint set (D.2) ensures that the same proportion of demand is met for all demand pairs, constraint set (D.3) enforces the capacity limits on the edges, and (D.4) are nonnegativity constraints on the flow variables. We refer to a solution ff ; g to the edge-path formulation as an edge-path solution.

Triples formulation

The solution of the above formulations gives an exact value (throughput) of the MCF problem. However, the system size is high which causes significant running time. Matula et al. [START_REF] Dong | A compact linear programming formulation of the maximum concurrent flow problem[END_REF] proposes in a recent work a compact linear programming formulation of the MCF problem. Authors introduce the triples formulation to solve the problem. The idea is to include a novel variable such as x k i;j indicating that the edge (i, j) diverts this amount of flow through on an intermediate node In a distributed network, the transportation of commodities is based on bandwidth allocation mechanisms. MCF is used to solve this problem while minimizing the operation cost.

In circuit electric, multi-commodity flow problem is the sparsest cut used to route current between transistors. Further, MCF is used for the routing (rerouting) of commodities by proposing novel routing metrics. Further, Generating independent key for independent users simultaneously is problem that can be easy solved by MCF exact approaches. MCF is used also to control the traffic between endpoint in order to avoid congestion caused by concurrent end-to-end flow control mechanism MCF is then a potential hop by hop congestion control for ICN.

D.7 Proposed DMCF model

We propose a novel DCMF algorithm for routing data consumer demands and recommending caching points. It is an exact model, distributed using local decision computing model, and asynchronous in terms of execution. Hereafter we describe our algorithm. We leverage the theorem of decomposition to aggregate the set of commodities entering in our framework using the well known originspecific problem (OSP) formulation in the state of the art. In this formulation, The value of the maximum concurrent flow between s and T (s). In Alg. 8, we present a sequential MCF algorithm proposed in [START_REF] Bauguion | Efficient algorithms for the maximum concurrent flow problem[END_REF]. It represents an extension of the Edmonds-Karp [START_REF] Ford | Flows in Networks[END_REF] algorithm that finds in each iteration a shortest path tree instead of a shortest path. Then, an optimal concurrent flow fraction is calculated and updated in each iteration.

In, Alg. 9, we propose a distributed version of the sequential MCF algorithm.

Hereafter, we describe its main steps. Then, a computation of the shortest path of the next iteration is done until there is no shortest path tree. Once the DMCF is terminated, * is the exact maximum concurrent throughput we can push.

D.8 Comparison

In Table D.1, a brief comparison between our algorithm (SS-DMCF) and the relevant work in the state of the art is presented. The proposed solution outperforms the above work in three main axes:

1. Optimal and approximate solution.

2. Polynomial time solution: Since a shortest path spanning tree algorithm is used to calculate the generalized maximum flow between the single source and all the destinations, the solution is solved in polynomial time.

D.9 Conclusion

In this chapter we have surveyed the relevant framework of the sequential and distributed maximum concurrent flow problem (MCFP). Then, a single source distributed MCF (SS-DMCF) algorithm is introduced in the context of traffic engineering, flow (demands) routing, and QoS routing in data-driven networks such as ICN/NDN. In the future work, we plan to use machine learning techniques instead of building mathematical models.

Algorithm 10 Find the SPT, algorithm for the process i 1: Input:

• dist: a nonnegative real or 1, representing the shortest path known distance from v 0

• parent: a UID or undefined, initially undefined 2: At each round:

• Send a distance(dist) message to all neighbors

• Receive messages from neighbors; let d j bethedistancereceivedf romneighborj:

• Perform a relaxation step: dist = min (dist; min j (d j + weight i;j )) (D.5)

• If dist decreases then set parent j, where j is any neighbor that produced a new dist.

-Spanning -Shortest Path: the total weight of the tree branch to each node is the minimum total weight for any path from v 0 in G.

• Output: Each process i i 0 should output parent(j), distance(d), meaning that:

j's vertex is the parent of i's vertex on a shortest from v 0 -d is the total weight (distance) of a shortest path from v 0 to j.

SPT time complexity:

• Number of rounds until all the variables stabilize to their final values.

• n-1 round, where n is the number of nodes in the network.

SPT message complexity:

• Number of messages sent by all the processes during the entire execution.

• O(n jEj)

D.11 Annex B: destination node program

Destination node sends the flow to its parents.

D.12 Annex C: intermediate node program

G[parent(j)][parent][D]+ arc[i; parent(j)]

4:

SEM SEM 1 5: end while 6: arc[parent(j)][parent][D] G[parent(j)][parent][D]

Algorithm 12 Calculate the MCF 1: void (Indegree) 2: while SEM Indegree do 3:

G[parent(j)][parent][ ]+ C[i;parent(j)] D[i;parent(j)] 4: if minigamma G[parent(j)][parent][ ] then 5: minigamma = G[parent(j)][parent][ ] 6: end if 7: SEM SEM 1 8: end while 9: arc[parent(j)][parent][ ] G[parent(j)][parent][ ]
Algorithm 13 Calculate the residual capacities 1: void (Indegree) 2: while SEM Indegree do 3:

G[parent(j)][parent][C] G[parent(j)][parent][D]

4: C. Tschudin et al. [START_REF] Sifalakis | An information centric network for computing the distribution of computations[END_REF] investigate the relation between networking and computation and propose Named Function Networking (NFN) as an ICN extension.

G[parent][parent(j)][C]+ G[parent(j)][parent][D]
In their approach, consumers send named expression interests and the network is responsible for interpreting these interests, executing the related functions and caching the computed results. The approach is very interesting and it is adopted in the IETF standard [START_REF] Pentikousis | Information-Centric Networking: Baseline Scenarios[END_REF].

Routing protocols responsible for computing routes and handling network [START_REF] Van Jacobson | Networking named content[END_REF]. In the former message, the name of the data is defined. The latter message binds the name to the raw data.

It is a receiver-driven approach that focuses on information instead of nodes and where data transmission is triggered after a consumer interest.

The main key functionalities of ICN are request routing, caching and processing, mobility, and security. Indeed, ICN generates an optimal path toward the content through lookup and longest-prefix matching algorithms. Moreover, popular data are cached and processed on the fly in the intermediate routers in order to reduce the end-to-end consumer delay. Through ICN paradigm, caching solutions are on-path caching and off-path caching [START_REF] Zhang | Caching in information centric networking: A survey[END_REF]. ICN supports also different mobility management solutions [START_REF] Sabeur | Mobile party: A mobility management solution for wireless mesh network[END_REF]. Indeed, subscriber mobility is resolved by re-issuing interest of the same content, publisher mobility which is more difficult is resolved through interest tracing and chasing [START_REF] Zhang | Kite: A mobility support scheme for ndn[END_REF]. Security is also inherent in ICN architecture and assures data integrity and verification by binding name to content [START_REF] Yu | Schematizing trust in named data networking[END_REF].

E.3.2 Principle Hadoop components

Hadoop is a big data framework that eases data processing, analysis, and min- 2. Transport layer: ICN is used between named data nodes for bulk data transfer using hadoop interest and data packets. This layer is then will responsible for the flow control between interests and data.

E.3.4 HoICN layer responsibilities

E.4 HoICN: optimization algorithm

Although ICN may be used for caching and processing IoT data through a simple linkage to Hadoop, ICN standards do not specify how these nodes can be deployed in a large scale network. Implementing ICN-Hadoop nodes everywhere in the underlying topology induces high cost and is not efficient (only some intermediate nodes could host a treatment service). We believe that Hadoop will be deployed as a virtual service on behalf of content providers in the operators network.

In this context, we try to propose a HoICN placement algorithm to solve this issue.

Given a large network infrastructure, HOPA will solve this deployment problem and will give ICN instantiation graph for new ICN-Hadoop positions. Given an initial network topology, algorithm inputs are: massive IoT nodes, IoT gateways corresponding to all ICN-Hadoop nodes, and consumers requesting computation results related to IoT (e.g., average temperature in a year).

The proposed algorithm selects where to cache the Hadoop computation results based on: system parameters (intermediate node capacity of CPU and memory), network parameters (the network bandwidth), and quality of experience parameter (end user required quality). Hereafter, we present optimal and heuristic optimization approaches. The maximum memory capacity of the server s L i;j

The direct link capacity from node i to node j

d g(f ) v
The set of consumer group hadoop interests p s g(f )

The placement cost of g(f ) on s

Decision variables Definition x s g(f )

Placement binary variable which indicates that the ICN-Hadoop computation result (g(f )) should be placed on the (optimal) server s 2 S y s v;g(f )

Mapping binary variable which indicates that consumer group (v 2 V ) needs an ICN-Hadoop computation result which should be placed on the optimal server s 2 S z v;g(f ) i;j Flow balance binary variable which indicates whether the link (i; j) is used for satisfying consumer interest. The consumer is interesting in g(f)

E.4.1 HOPA: HoICN Optimal Placement Algorithm

In Table E.1, we show the proposed parameters (system, network and quality) and decision variables (placement, routing, and flow balance) of our optimization (exact and heuristic) algorithms.

The description of our decision variables are as follows:

1. The binary variable x indicates the placement of ICN node, and the migration of the computation result from one server to optimal location s. It is defined as:

x s g(f ) = 8 > > > > < > > > > : 1; if g(f ) migrates to s 0; Otherwise (E.1)
2. The binary variable y indicates that the consumer needs a computation result, and the server s caches it. It is defined as :

y s v;g(f ) = 8 > > > > < > > > > : 1 if v needs g(f ) and s caches g(f ) 0 Otherwise (E.2)
3. The binary variable z v;g(f ) i;j indicates whether a link (i; j) is used (from i to j) to route g(f) from a replica server (the one for which y s v;g(f ) = 1) to consumer v. It is defined as:

z v;g(f ) i;j = 8 > > > > < > > > > :
1; if there is a path P g(f );v using link (i; j)

0; Otherwise (E.3)
The optimization model of the optimal approach is quoted as follows:

1. The HoICN objective function is to minimize the total placement (deployment) cost. It is modeled as:

8g 2 G : F = X s2S X f 2F x s g(f ) p s g(f ) (E.4)
2. Consumer group interesting in a hadoop result where d g(f ) v not null retrieves the result from one optimal server:

8v 2 V j d g(f ) v 0 : X s2S y s v;g(f ) = 1 (E.5)
3. Satisfying the interests in cached computation results concurrently is limited by the network capacity of the optimal server as follows:

8s 2 S : X v2V X f 2F y s v;g(f ) d g(f ) v D s (E.6) 4.
The system constraint that assures that cached computation results is limited by the server system capacity is:

8g 2 G; 8s 2 S : X f 2F x s g(f ) g(f ) size C s (E.7)
5. The flow balance constraint guarantees that incoming flow (some computation results) equals to the out-coming flow except the source and the destination. In the source, there is only out-coming flows. In the sink, there is only incoming flows:

8g 2 G : X j z v;g(f ) i;j X j z v;g(f ) j;i = 8 > > > > > > > > < > > > > > > > > : 0 if i fv; sg y s v;g(f ) if i = s 1 if i = v (E.8)
6. The capacity constraint assuring that each network link is bounded by its capacity is modeled as follows:

8g 2 G; 8i; j 2 V [ S : X v2V X f 2F z v;g(f ) i;j d g(f ) v L i;j (E .

E.5 HoICN: performance evaluation

In this section we evaluate our optimization algorithm. The proposed network topology follows Watts-Strogatz1 that is highlighted in the IETF/IRTF standard [START_REF] Pentikousis | Information-Centric Networking: Evaluation and Security Considerations[END_REF]. We believe that it may fit with Hadoop clusterization and distribution nature where all the nodes are close to each other in terms of network distance. In

E.6 Conclusion

We [126], named data networking (NDN) [START_REF] Ndn | Named data networking[END_REF], content centric networking (CCN) [START_REF] Ccn | The ccnx project, parc a xerox company[END_REF], data oriented network (DONA), and publish and subscribe information protocol (PSIRP) [START_REF] Psirp | Publish-subscribe internet routing paradigm[END_REF]. for producer mobility is also found in [START_REF] Zhang | A survey of mobility support in named data networking[END_REF].

F.2.2 Why ICN for IoT

In this chapter we recommend leveraging ICN as a forwarding plane for IoT.

ICN features provide several advantages in IoT deployment as listed below:

• Content naming: most of IoT applications do not require establishing an endto-end communication between two devices, however rely on retrieving content (regardless its location). ICN content naming simplifies content retrieval by different IoT service providers representing multi-tenancy.

• Data-centricity: IoT consumers requesting (temperature measurement, etc..)

are not looking for the end host device but look for the data itself.

• In-network caching: ICN routers provide data from content store even regardless of the reachability to the data source, which reduces the latency and signaling to reach the original data source. Furthermore, by caching massive IoT data, composed services and data treatment can be extensively improved (efficient data analytics at the network edge).

• Data Authenticity: ICN provides object-based encryption, and names are used to verify content integrity and authenticity through binding name to data and its publisher or origin.

Although the advantages mentioned above, there are still some open issues for ICN over IoT as follows:

• Naming: Device Naming in some IoT applications is needed in different cases (e.g., actuation command, switch on/off a device, etc.). ICN caching may have a counter effect, and action may be delayed. Moreover, in video data "coming from IoT cameras" scenario, it is still unclear how ICN naming will work.

Handling delay sensitive application is also another scenario.

• Data size: Size of data in IoT is generally very small (a few bytes such as 1-on, 0-off), where the size of the "data name" may exceed the size of the "data" (i.e., memory issue). Naming overhead also appears in the case of hierarchical names that can be too long. Also, dynamic data generation of IoT is a challenge for hash-based content names.

• Data caching: Caching IoT data needs an adequate caching policy. Moreover, decoupling publisher/consumer is an advantage for content retrieval but it needs full name deduction from consumer.

We address some of the above mentioned issues in our solution, especially what concern the overall network performance (IoT data size, caching, etc). Still, IoT over ICN needs some requirements to be enough beneficial. Having an optimal placement for ICN/IoT nodes is a very important problem that is not yet solved.

Additionally, the following design factors need consideration in IoT over ICN architectures (note that our proposed solution considers these design factors):

• Network transport model: a combination of PULL (receiver-driven) and PUSH (sender-driven) models can be supported. Nevertheless, the base model design with reference to ICN standard should be PULL. Unlike TCP/IP, a design decision of IoT over ICN is to follow the barlund's transactional model of communication [START_REF] Mortensen | Communication Theory[END_REF], which models ICN active network where IoT producers, ICN nodes and consumers interact with data through feedbacks.

• Sequence numbers: Immutable data objects with sequence numbers are needed to support large scale distribution and valid data in ICN domains (as in dynamic databases).

• From the hardware perspective: ICN nodes and IoT device are not fully fledged in order to let IoT devices (highly mobile, low duty cycle) delegate the responsibility of responding to requests to more stable ICN node connections. These delegated nodes can be IoT Gateways (and not tiny IoT de-vices) instead of having them as separate nodes that are not part of the IoT world (they can still be IoT nodes but functioning as IoT Gateways. Moreover, resource constrained devices should not serve as data producers or ICN gateways (capability advertisements).

• Actuation: handling actuators in ICN network should be controlled through the ICN communication model without the ICN caching property. Enabling caching for actuation scenarios make data consumers unsure that the request reached the actuator and can lead to delay in the actuation process.

• Node architecture: ICN node should be extended with explicit support for time and data freshness. IoT nodes may periodically update their information/state.

• Security: it should be object-based rather than session-based. Instead of securing the communication pipe (the channel) such as the case in TLS, SSH, SSL, securing the content state in the network using advanced cryptographic tools is the adequate approach. However the big challenge that is not yet resolved is how to share and distribute the right cryptographic keys to the right nodes.

F.2.3 ICN in IoT: related Work

In-network caching has been widely investigated in ICN/NDN wired networks, while few contribution addressed NDN caching for wireless and IoT networks.

The work in [START_REF] Zhang | Caching in information centric networking: A survey[END_REF] presents a survey on the current approaches, which are usually considering fixed and wired connected content routers and also designed for multimedia content distribution. [START_REF] Psaras | Probabilistic innetwork caching for information-centric networks[END_REF] and [START_REF] Tarnoi | Performance of probabilistic caching and cache replacement policies for content-centric networks[END_REF] discuss probabilistic caching strategy with the key idea that each NDN node randomly caches incoming Data with a certain probability p, where 0 < p < 1. The (CE 2 ) strategy is a special case of the probabilistic scheme, where (p = 1). Decreasing p reduces the in-network caching probability and maximizes the diversity of Data cached in the network. How-ever, [START_REF] Psaras | Probabilistic innetwork caching for information-centric networks[END_REF] considers fixed networks with wired connected routers and [START_REF] Tarnoi | Performance of probabilistic caching and cache replacement policies for content-centric networks[END_REF] adds large amount of overhead and complexity to achieve performance, which is unsuitable for resource constrained devices in IoT. Only few work consider caching in IoT systems ( [START_REF] Baccelli | Information centric networking in the iot: Experiments with ndn in the wild[END_REF], [START_REF] Quevedo | Consumer driven information freshness approach for content centric networking[END_REF], [START_REF] Vural | Innetwork caching of internet-of-things data[END_REF]). The work in [START_REF] Baccelli | Information centric networking in the iot: Experiments with ndn in the wild[END_REF], evaluates the performance of content retrieval from different consumers with standard NDN in-network caching, however, the cache size of resource-constrained nodes (used in the experiments) is 1 Kbyte and information is ephemeral (short-lived, transient). The work in [START_REF] Quevedo | Consumer driven information freshness approach for content centric networking[END_REF] analyzes the impact of IoT information freshness over NDN caching through using a consumer driven freshness approach besides the freshness parameter included in Data packets (establishing how many seconds the content can be valid in the CS).

This improves the accuracy of the data received by consumers. The challenge here is how this caching approach sustains in the presence of big number of consumers with different freshness requirements. The work in [START_REF] Vural | Innetwork caching of internet-of-things data[END_REF] presents a first study on caching IoT content in Internet wired content routers (electrically powered static routers), proposing a distributed probabilistic caching algorithm where routers dynamically update their caching probability by considering their hop distances to the source and the consumers and the data freshness (i.e. the closer the caching location is to the source, the fresher the retrieved data packet is). This approach may not be always valid and depends on the type of data, sensor/IoT type emission rate. Unlike [START_REF] Vural | Innetwork caching of internet-of-things data[END_REF], wireless NDN-IoT multi-hop network composed of (mobile) resource constrained nodes is considered in [START_REF] Hail | Caching in named data networking for the wireless internet of things[END_REF]. A probabilistic caching strategy is proposed that considers the data freshness and the potential constrained capabilities of devices (mainly energy level and storage capacity).

The work in [START_REF] Imai | Energy-aware cache management for content-centric networking[END_REF] considers traffic optimization through caching less popular content on content routers near to the origin site and caching more popular content on content routers near to the users aiming to minimize the sum of cache allocation power and traffic transmission power. This approach may not be so suitable if IoT content are consumed near the origin site. The work in [START_REF] Imai | Energy efficient content locations for in-network caching[END_REF] designs content locations in order of descending popularity to minimize total power consumption. The proposed algorithm derives the optimal cache locations of a content item based on a 0-1 ILP (Integer Linear Programming). Any solver for large-scale ILP problems at high speed can be used to solve the 0-1 ILP model. F.3 OPA: Optimal Placement Algorithm for ICN/IoT nodes ICN does not specify how nodes can be deployed in a large scale network. One could simply say that it will be implemented everywhere in the underlying topology, but this is not efficient and can induce high cost (not all the network nodes could host an efficient caching or intermediate treatment service). Our algorithm, (Optimal Placement Algorithm, OPA), given a network infrastructure, will solve this deployment problem and will give ICN instantiation graph for new ICN positions. It takes as input, the global network topology consisting of :

• IoT group producer nodes "sensors, cameras, etc."

• IoT gateways "aggregation hubs, routers" corresponding to all network elements including larger Internet.

• and consumers "applications, servers in data centers"

The proposed algorithm finds the optimal deployment strategy for ICN/IoT nodes functionalities based on the following parameters:

• The required consumer end to end response time.

• The node system performance. It is the system overhead (memory and CPU resource) after deploying ICN functionality in the candidate nodes.

• migration cost (network optimization), which represents the total cost of moving ICN/IoT functionality in terms of network bandwidth.

Hereafter, we first state the system hypothesies and then present the placement models based on exact Integer Linear Programming (ILP) and heuristic graph theory optimization.

F.3.1 The placement algorithm

We consider two main hypothesis in our approach:

• Consumer groups (clients) that have no direct connectivity to the IoT devices (they connect to the IoT devices through a gateway).

• Refreshing periodicity between IoT-gateways and devices (to collect IoT data)

and that is smaller than the OPA evaluation periodicity.

Table F.1 defines the main system/network parameters and decision variables.

Exact ILP Solution The general formulation of the exact algorithm is as follows: The set of consumer group's interests

0 if i v; i s y s v;f if i = s 1 if i = v (F.6) 8i; j 2 V [ S : X v2V X f 2F z v;f i;j d f v L i;j (F.7)
The ICN instantiation graph results from the optimization process. It is applied on an input network graph (it can be considered as the larger Internet). After optimization, a set of nodes will host the ICN function. They are identified by a binary variable x s f (equals 1 if the node can be upgrade with ICN function and 0 otherwise).

When consumer v sends an interest message for a given ICN data, the request variable y s v;f is equal to 1 when data is available in the node s and 0 otherwise. Finally, if a link (i; j) is used in the instantiation graph, the binary variable z v;f i;j will be equal to equal to 0 otherwise. In eq. (F.1), we formulate the objective function that minimizes the total placement cost of ICN nodes in the IoT network.

In eq. (F.2), we ensure that the binary variable y is less than or equal x. In fact, y equals to 1, if and only if v needs f , and f is located on server s (we should not place an ICN function on node s if there is no interest for it).

Eq. (F.3) states that the optimal server s can serve the consumer nodes interested in the ICN data f . The sum prevents consumers from having to chose between different servers hosting the same ICN data.

Eq. (F.4) enforces network constraints. We cannot exceed the maximum downloading capacity.

Eq. (F.5), is relative to node system performance. It enforces the system caching feature of ICN nodes that should not exceed a maximum size.

Eq. (F.6) represents the network flow conservation between the intermediate ICN nodes and the consumers. In particular, if a node is upgraded to ICN, we ensure that flow balance equals to 1, meaning that it directly serves the incoming consumer interests. Otherwise, if the node is not upgraded, the flow balance is null. At the consumer side, there is no outgoing traffic (left sum is null). Hence the flow balance is negative.

In eq. (F.7), we ensure that the link capacity between network nodes should not exceed the available network bandwidth.

The above problem is NP-hard due to our combinatorial complex system and difficult to scale up. It can however be easily run on the CP LEX environment.

As we target very large ICN infrastructures, a graph based optimization algorithm has to be designed. We present hereafter, another scalable placement algorithm.

OPA Heuristic Algorithm OPA is based on the well know Gomory-Hu scalable algorithm and it aims at placing ICN/IoT software with the same above mentioned strategy and parameters. Gomory-Hu is an off-line optimization step that compacts the the larger network topology to construct a tree with maximum-flow between all pairs of nodes. Algorithm 14 summarizes the pseudo code of OPA. Hereafter, we describe these main stages. The initial network topology is supposed to be a scale-free network (the degree distribution follows power law). The output of this transformation is a cut-tree construction (Gomory-Hu tree, CTC) that represents the maximum-flow between all network server pairs. The cut-tree is used for bottleneck detection.

The model relies on the same information and parameters as in the exact ILP solution (number of servers, system capacity, network capacity, consumer interests). Then, an initial graph that holds the full parameters is created. Further, a Cut-Tree is constructed based on the topology capacity without including the consumer interests. The set of consumer interests is then passed on the tree. During this step, OPA algorithm explores the cut tree creating a path from the gateway to the server hosting the ICN/IoT. If the flow cannot reach the destination (i.e. the original server), caused by shortage in bandwidth on this path, we simply place the new ICN function before the rupture node of the cut tree. A test on system capacity is also performed to ensure that the target ICN node can host this new service. Although a path may not be obtained from the first trial, the problem is still polynomial compared to the NP-hard complexity of the exact solution. Finally, we would like to highlight that OPA was integrated in our virtual migration platform and outsourced in [START_REF] Tamayo-Ibnkhedher | vios (virtual infrastructure optimization simulator)[END_REF]. The Vios platform enables the placement and migration on NFV functions such as CDNs and ICN functions.

F.4 Security considerations

OPA places ICN/IoT nodes closer to consumers. Hence, the security of the IoT will be improved. Indeed, thanks to the ICN features, IoT data integrity is ensured through embedded encryption. We also minimize the network distance between the origin data producers (IoT devices) and consumers (that typically uses a LORA like protocol). If we assume that P r(attack) / N (N is the number of nodes from consumers to producers), in ICN, the P r(attack) < N A network security cost is proposed as the following:

N etwork Security Cost = d(P r; C) (F.8)

Where characterizes the node stability, P r is the ICN/IoT gateway (or an intermediate ICN/IoT container after using OPA), C is the consumer group, and finally d is the network distance between P r and C.

Finally, the security level may be introduced in our initial objective function (F.1) as an additional constraint.

OPA improves three security issues:

• ICN Caching: OPA acts as a cache relay benefiting from ICN security. Although Intermediate caching nodes may be untrusted, still the ICN infrastructure guarantees the trust for IoT data.

• Processing: OPA enables data analytics, treatment and processing of the cached IoT data. Cached data is treated by intermediate ICN nodes. A security SLA has to be valid between those entities.

• Energy Efficiency: Since OPA is designed for ICN/IoT, it eliminates the need to establish a secure connection between the resource-constrained devices acting as data producers and all the data consumers.

F.5 OPA: performance evaluation

IoT network uses the Ultra Narrow Band (UNB) for the Machine to Machine (M2M) communication. This network poses different problems such as increasing the end to end delay. In general, such network interconnects more than 7 million of devices and uses a point-to-point communication. In this section, the network is assisted with our intelligent algorithm that introduces ICN nodes in different levels. We show that network update upon upgrading optimal nodes by ICN/IoT We evaluate our scenario through the well known Barabási-Albert model [START_REF] Barabasi | Emergence of scaling in random networks[END_REF] 1 undirected and weighted graph. Vertex connectivities follow a scale-free power law distribution P (k). It represents the probability that a vertex interacts to k other vertices is: P (k) k . The initial graph has 100 vertices (IoT gateway nodes) with a degree distribution that follows the power of 2:5, and obeys to the scale-free implementation of psumtree. Its Cut-tree-based transformation (Gusfield transformation of the Gomory-Hu algorithm is used here [START_REF] Gusfield | Very simple methods for all pairs network flow analysis[END_REF]) has only 99 edges (49:5%). 1 Barabási-Albert graphs are not random topologies. Instead, they follow a power degree distribution (nonlinear model) so that can be used to assess network performance and as well as interpret the security benefits. x s f (F.12)

Eq. (F.9) defines the consumer delay metric that represents the response time while using OPA instead of the legacy IoT networking. sf and sv represent the data producer (aggregator or ICN gateway) and the data consumer point of attachments respectively. Equations (F.10) and (F.11) define the placement cost in terms of memory cost and placement delay (total delay to perform the placement along the shortest path from the IoT gateway to the optimal server node). Eq. (F.12)

represents the average number of instantiated ICN nodes. IoT networks such as Sigfox [START_REF] Bor | Lora for the internet of things[END_REF] are dedicated to low rate wireless data gathering. Several field trials and operational customers have started to use this facility.

LoRA corresponds to the wireless part between devices and gateways. As Lora networks cover very large geographical areas, an infrastructure has to be built for data collection and routing. OPA can enhance this core network and provide the flexible ICN function explained before.

In Table F.2, we highlight how an IoT network such as Sigfox could be improved by applying OPA.

F.7 Conclusion and Future Work

We proposed in this chapter using ICN for IoT deployment and we introduced a new notion, which is how to assign ICN functionality to ICN/IoT nodes in a dynamic way based on network load and required services latency. In this context, we presented an Optimal Placement Algorithm (OPA) to enhance the caching deployment by network providers. OPA selects optimal network locations to serve as intermediate IoT publisher and pursue in-network caching. We illustrated IoT benefits from the in-network caching feature in ICN especially when applying our proposed algorithm. And we compared OPA in IoT over ICN with IoT over SigFox network (as an example of a popular IoT network deployment in France). Encour- Using cloud data centers.

Delay

Minimize the end-toend consumer delay Significant.

Optimization cost

Additional cost of placement of ICN/IoT nodes Minimum deployment cost.

Bitrate

High throughput network due to the innetwork caching feature.

Low throughput network due to the UNB modulation.

Security

Object-based security that allows caching in untrusted intermediate nodes (proxies, caches, etc.).

Session-based security, frequency hopping.

Actuation latency

Bounded in with cache avoidance (OPA helps in routing).

Unbounded

Medium Access Control (MAC) layer

ICN networking stack that implies optimal bandwidth occupancy.

Without collisionavoidance that limits the bandwidth of IoT gateways [START_REF] Bor | Lora for the internet of things[END_REF].

aging results assure that OPA is scalable and efficient in terms of placing ICN/IoT nodes in a dynamic way. We will try to compare OPA in IoT over ICN against IoT solutions over WiFi and cellular networks without ICN. Finally, Vios platform will be enriched with ICN dockers.

6 )

 6 Integration of algorithms: Following the architecture derived from ETSI concerning the virtualization of network functions, we propose the integration of the previously designed and evaluated algorithms into a real architecture. A flow diagram is proposed and a prototype based on the open source software OpenStack, OpenDaylight and Open Virtual Switch is implemented and integrated into a real network operator. This part has been demonstrated and it gives very encouraging results. This thesis is supported by models, implementations and simulations which provide results that showcase our work, quantify the importance of evaluating optimization techniques and analyze the trade-off between reducing operator cost and enhancing end user satisfaction index. Key words-vCDN; SDN/NFV Optimization; Migration Algorithms; Scalability Algorithms Résumé Le Réseau de Distribution de Contenu (RDC) est un large réseau distribué qui est déployé dans le monde entier et est conc ¸u pour pousser le contenu à la périphérie des réseaux. Il déplace le contenu pour atténuer l'augmentation du trafic vidéo et améliorer la satisfaction des utilisateurs. Il trouve des points intermédiaires entre le serveur d'origine et les clients finaux. Les fonctions de virtualisation de réseau, avec les nouveaux concepts émergents tels que les solutions NFV (pour Network Function Virtualization) et SDN (pour Software-Defined Network), peuvent répondre aux demandes des utilisateurs et, par conséquent, augmenter l'efficacité du réseau. Ainsi, nous examinons les avantages potentiels de la virtualisation apportés aux RDC.

3 ) 6 )

 36 Orchestration de services : Etant donné que le réseau de diffusion de contenu comporte plusieurs composants virtuels, les solutions proposées (optimales et heuristiques) sont adaptées à ce nouveau contexte o ù l'objectif d'optimisation est d'orchestrer et d'enchaîner un ensemble de composants de livraison. Des simulations sur des différents scénarios de déploiement sont effectuées. Nous évaluons les résultats et proposons l'orchestration de serveurs candidats et le chaînage entre les instances. 4) Optimisation multi critères : L'objectif principal des techniques précédentes est unique (réduire le co ûts global de la migration). Nous avons donc essayé dans cette thèse de proposer un algorithme d'optimisation multi-objectif prenant en compte les différents critères des acteurs (fournisseur de contenu, opérateur réseau, client) impliqués dans le chaînage de livraison. L'idée derrière cette technique est de sélectionner une couche d'optimisation (c'est-à-dire, coeur du réseau, agrégation et accès) o ù un algorithme de placement, de migration, ou d'orchestration est exécuté. 5) Réseaux actifs et complexes : Pour un tel réseau actif et complexe (tel que le réseau centré sur l'information (ICN) ou Hadoop), les algorithmes d'optimisation traditionnels ne sont plus valables et doivent être ajustés dans ce nouveau contexte. Par conséquent, nous avons adapté les contraintes d'optimisation à ces types de réseaux et nous avons appliqué un modèle basé sur le budget . L'idée est de définir un budget spécifique pour chaque noeud de réseau qui représente le travail que chaque noeud peut faire. Ensuite, le réseau actif est modélisé et les algorithmes d'optimisation précéedents sont adaptés et évalués sur des graphes complexes. Intégration des algorithmes : Suivant l'architecture issue de l'ETSI qui concerne la virtualisation des fonctions de réseau, on propose l'intégration des algorithmes précédemment conc ¸us et évalués dans une architecture réelle. On propose un diagramme de flot et met en oeuvre un prototype basé sur les logiciels opensources tels que OpenStack, OpenDaylight et Open Virtual Switch. Cette partie a été démontrée à travers une implémentaion réelle et elle a donné de très bons résultats. Cette thèse est soutenue par des modèles mathématiques, des implémentations et des simulations qui fournissent des résultats qui mettent en valeur notre travail, quantifient l'importance de l'évaluation des techniques d'optimisation et analysent le compromis entre la réduction du co ûts de l'opérateur (la migration) et l'amélioration de l'indice de satisfaction de l'utilisateur final. Mots clés-RDC ; Optimisation ; SDN/NFV ; Algorithmes de migration ; Algorithmes d'évolutivité.

AcknowledgmentsI

  would like to thank the people who have directly or indirectly supported me and contributed to my work during the years of my Ph.D studies. Firstly, I would like to express my sincere gratitude to my supervisor and thesis director Prof. Hossam Afifi. His knowledge and expertise have guided me all the way through my research.

E. 3 . 5 F. 3 . 1 F. 4 F. 7 5 - 3 5 - 4 5 - 6 6 - 6 7 - 2 7 - 4 8 - 6 F- 2 45 3. 1 92 4. 2 25 B. 1 F. 1 F. 2

 35314753545666727486245192225112 Massive IoT data as a use case . . . . . . . . . . . . . . . . . . E.4 HoICN: optimization algorithm . . . . . . . . . . . . . . . . . . . . . E.4.1 HOPA: HoICN Optimal Placement Algorithm . . . . . . . . . E.4.2 HHPA: HoICN Heuristic Placement Algorithm . . . . . . . . E.5 HoICN: performance evaluation . . . . . . . . . . . . . . . . . . . . . E.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .F Optimal Placement Algorithm (OPA) for IoT over ICN 245 F.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . F.2 ICN in IoT and related work . . . . . . . . . . . . . . . . . . . . . . . F.2.1 ICN principles . . . . . . . . . . . . . . . . . . . . . . . . . . . F.2.2 Why ICN for IoT . . . . . . . . . . . . . . . . . . . . . . . . . F.2.3 ICN in IoT: related Work . . . . . . . . . . . . . . . . . . . . . F.3 OPA: Optimal Placement Algorithm for ICN/IoT nodes . . . . . . . The placement algorithm . . . . . . . . . . . . . . . . . . . . . Security considerations . . . . . . . . . . . . . . . . . . . . . . . . . . F.5 OPA: performance evaluation . . . . . . . . . . . . . . . . . . . . . . F.5.1 Scale free networks: a Barabási-Albert model-based network operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . F.6 OPA efficiency: comparison with IoT networks . . . . . . . . . . . . Conclusion and Future Work . . . . . . . . . . . . . . . . . . . . . . . 4-12 Network optimization costs: delivery capacity impact . . . . . . . . 4-13 Network optimization costs: delivery storage impact . . . . . . . . . 4-14 comparison between the optimal and the non optimal algorithms using total virtualization cost parameter and under vCDN/client node variation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-15 Operator gain after executed the optimal migration algorithm comparing to the non optimal . . . . . . . . . . . . . . . . . . . . . . . . . 4-16 Comparison between OPAC and Bernadetta et al work . . . . . . . . 5-1 OPAC: vCDN-YouTube migration use case . . . . . . . . . . . . . . . 5-2 Example of a Gomory-Hu tree transformation. . . . . . . . . . . . . . Example of HPAC vCDN content replication/migration. . . . . . . . Network topology used for small scale . . . . . . . . . . . . . . . . . 5-5 OPAC-HPAC comparison in the small network scale scenario. . . . . Network topology used for large network scale. . . . . . . . . . . . . 5-7 HPAC in large network scale. . . . . . . . . . . . . . . . . . . . . . . . 5-8 OPAC and HPAC run-time in large network scale. . . . . . . . . . . . 5-9 Main use-cases for OPAC/HPAC in an SDN/NFV framework. . . . . 5-10 Sequence diagram for OPAC/HPAC integration. . . . . . . . . . . . . 6-1 vCDN network orchestration . . . . . . . . . . . . . . . . . . . . . . . 6-2 virtual CDN architecture according to ETSI standard . . . . . . . . . 6-3 VNF space for virtual CDN . . . . . . . . . . . . . . . . . . . . . . . . 6-4 Management, orchestration, and VNF spaces for vCDN . . . . . . . 6-5 OCPA: vCDN orchestration example . . . . . . . . . . . . . . . . . . Network topology used for the OCPA evaluation . . . . . . . . . . . 6-7 vCDN total migration cost . . . . . . . . . . . . . . . . . . . . . . . . 6-8 vCDN migration time . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-9 vCDN network optimization costs . . . . . . . . . . . . . . . . . . . . 6-10 vCDN replica number . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-11 vCDN network optimization costs: user side . . . . . . . . . . . . . . 6-12 vCDN network optimization costs: network side . . . . . . . . . . . 7-1 The TOPSIS sequence for vCDNTTX decision . . . . . . . . . . . . . Testbed and VM migration times . . . . . . . . . . . . . . . . . . . . 7-3 VM migration and interruption times . . . . . . . . . . . . . . . . . . Optimization of CDNaaS workflow for DVD2C project . . . . . . . . 8-1 ICN based active network scenarios . . . . . . . . . . . . . . . . . . . 8-2 Active node budget mapping . . . . . . . . . . . . . . . . . . . . . . . 8-3 G-H based ICN insertion . . . . . . . . . . . . . . . . . . . . . . . . . 8-4 OPPA-HPPA decision time . . . . . . . . . . . . . . . . . . . . . . . . 8-5 OPPA-HPPA comparison in the small network scale scenario . . . . Network topology used for large scale . . . . . . . . . . . . . . . . . 8-7 HPPA in large network scale scenario . . . . . . . . . . . . . . . . . . C-1 Total migration cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . C-2 Replica number impact . . . . . . . . . . . . . . . . . . . . . . . . . . D-1 Intermediate node program . . . . . . . . . . . . . . . . . . . . . . . E-1 HoICN layer responsibilities . . . . . . . . . . . . . . . . . . . . . . . E-2 HoICN topology: Massive IoT data . . . . . . . . . . . . . . . . . . . E-3 Network topology used for large scale . . . . . . . . . . . . . . . . . E-4 HHPA: execution runtime . . . . . . . . . . . . . . . . . . . . . . . . E-5 HHPA: end-to-end consumer delay . . . . . . . . . . . . . . . . . . . F-1 ICN-based IoT distribution network. Given the network topology, consumers requests, and objects served by content providers, OPA model chooses which server should be upgraded with ICN/IoT software. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Data consumer delay . . . . . . . . . . . . . . . . . . . . . . . . . . . F-3 OPA run-time in scale-free network . . . . . . . . . . . . . . . . . . . F-4 ICN/IoT placement (in network caching) cost . . . . . . . . . . . . . 262 F-5 OPA in scale-free IoT network . . . . . . . . . . . . . . . . . . . . . . 263 List of Tables 2.1 CDN infrastructure and compositions . . . . . . . . . . . . . . . . . 35 2.2 CDN delivery and management . . . . . . . . . . . . . . . . . . . . . 39 2.3 CDN Request routing techniques . . . . . . . . . . . . . . . . . . . . 40 2.4 CDN performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Live migration requirements . . . . . . . . . . . . . . . . . . . . . . . 70 3.2 vCDN comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.1 OPAC mathematical notation . . . . . . . . . . . . . . . . . . . . . . Comparison between OPAC and state-of-the-art . . . . . . . . . . . . 5.1 OPAC mathematical notation in a migration use case . . . . . . . . . 5.2 Gap (migration cost): HPAC efficiency . . . . . . . . . . . . . . . . . 5.3 Efficiency comparison between OPAC and HPAC; SS: Small Scale,LS: Large Scale N = jV (G)j, M = jE(G)j . . . . . . . . . . . . . . . . . . . . 6.1 Mapping between simplified vCDN and ETSI-MANO . . . . . . . . 6.2 Comparison between vCDN and ETSI-MANO . . . . . . . . . . . . . 6.3 Mathematical Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1 Mathematical Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Efficiency comparison between OPPA and HPPA . . . . . . . . . . . A.1 Direct caching techniques . . . . . . . . . . . . . . . . . . . . . . . . Content moving techniques . . . . . . . . . . . . . . . . . . . . . . . B.2 Replication techniques . . . . . . . . . . . . . . . . . . . . . . . . . . D.1 Comparison between SS-DMCF and state-of-the-art . . . . . . . . . E.1 HoICN Mathematical Notation . . . . . . . . . . . . . . . . . . . . . Mathematical Notation . . . . . . . . . . . . . . . . . . . . . . . . . . Efficiency comparison for OPA and IoT SigFox network . . . . . . . Software Defined Networks (SDN) and Network Function Virtualization (NFV)

Section 2 .

 2 5 introduces the state of the art of the art the main virtual CDN solutions with details about our virtual CDN (vCDN) use cases based on network function virtualization principles: NFV and SDN. Section 2.6 highlights general optimization techniques used in the context of virtualization and video delivery service.

Fig. 2 -

 2 Fig.2-1 describes in a general way the different components of CDN. A typical CDN includes a content distribution system which has the role of content replication. In addition, a request routing system is necessary to receive requests from end users and redirect them in different ways discussed later. Further, a centralized management plan is used to distribute load over surrogates (it is defined as a device/function that interacts with other elements of the CDN for the control and distribution of content within the CDN and interacts with User Agents for the delivery of the content) 2 (CDN Mgmt). It has the role of cache management.

Figure 2 - 1 -

 21 Figure 2-1 -Main components of CDN

Figure 2 - 2 -

 22 Figure 2-2 -DNS-based request routing

Figure 3 - 1 -

 31 Figure 3-1 -Evolution of multimedia application delivery

Figure 3 - 2 -

 32 Figure 3-2 -OpenStack architecture

Figure 3 - 3 -

 33 Figure 3-3 -Hypervisor monitored live migration

Figure 3 - 4 -

 34 Figure 3-4 -VM networking scheme

Figure 3 - 5 -

 35 Figure 3-5 -Live migration with shared storage

Figure 3 - 6 -

 36 Figure 3-6 -Live VM context transfer

  Static contents are: images, video, CSS file, scripts files. CDN customers are mainly the Internet Service Providers (ISPs) and Over the Top (OTT) service providers like YouTube and Netflix. All those customers want to push their content to the edge servers over IP technology. A CDN is looking to build a large farm of cache servers deployed worldwide in order to reduce the load on the OTT servers and provide the following services: Storage (popularity based), Management of cached content (i.e. cache management like replication, replacement, and placement), Distribution of content among cache servers (load balancing), Content Streaming, Fault tolerance (i.e. Redundancy), and Network performance (reduce load).

3. 5 . 2

 52 Virtualization of CDN CDN federation can be proposed to improve performance. Virtual CDN, vCDN is a virtual solution for enhancing the utilization of the current CDNs. Most of the internet traffic is delivered through commercial CDN by allocating some cache servers to distribute the content to end users. We introduced that this process can be enhanced by three ways of virtualization: classical vCDN based Cloud brokers, vCDN based NFV solution, vCDN based SDN solution and vCDN based NFV and SDN. Among those virtualization ways, we have proposed three new solutions: 1. vCDN based on NFV. 2. vCDN based on SDN. 3. vCDN using the merger between NFV & SDN.

Fig. 3 -

 3 Fig.3-7a shows our vCDN architecture based on NFV solution. Different services issued from unique or multiple service providers can hence be deployed on virtual machines running as a streaming serves on physical servers (Common-Off-The-Shelf (COTS) Sever). End-user's requests are forwarded to the closest vCDN virtual machine. Several network issues must be resolved to complete NFV and network requirements such as mobility, QoS and QoE.

  Figure 3-7 -vCDN based virtualization solutions

Figure 3 - 8 -

 38 Figure 3-8 -vCDN using the merge of NFV & SDN

Fig. 4 -

 4 Fig. 4-1 depicts the main components of the typical CDN network. It includes:

Figure 4 - 1 -

 41 Figure 4-1 -Main components of Content Delivery Networks

Figure 4 - 2 -

 42 Figure 4-2 -vCDN architecture according to ETSI-NFV[START_REF][END_REF]

  They were recently adapted to the CDN context for video content placement. The goal was to decrease the load on the origin content providers (like YouTube, Netflix 2 ) and to let the operators/ISPs host the content on their network to decrease as much as possible the load on the external links. Yet, an additional optimization mechanism should be proposed to further improve the overall caching performance combining optimization, placement, and virtualization within the operator/ISP network. The overall virtualization challenges for CDN transition to vCDN are addressed in the research project DVD2C [129]. In a previous chapter, we have investigated the main network issues in virtual machine migration and especially for vCDN use case and in an SDN/NFV context. Fig. 4-2 depicts the proposed vCDN architecture based upon the ETSI-NFV reference architecture [171]. Note here that different vCDN implementations could exist. Indeed, as depicted in Fig. 2-1, a CDN network is composed of different systems such as caching, distribution, request routing, and management. Therefore, by making the transition from classical CDN to the NFV/SDN-based vCDN context, all theses system components can be virtualized and deployed as VNF instances, but given the growth of video delivery, virtualization has to target mainly the caching and streaming components (i.e., VNF caching, VNF streaming, etc.). Further, a VNF request routing system (vRR) is added to the vCDN proposed architecture in order to orchestrate the VNF caching/streaming nodes. Currently, despite the importance of optimization tasks in the novel virtualization context of SDN and NFV, such functions are missing in the global network architecture. We therefore, try in this chapter to contribute with OPAC (protocol and optimization model) as a potential optimization technique for vCDN placement and explain how it is integrated in the network operator. Although video on demand (VoD), assisted by cascaded caching, enhances the QoE and decreases the load, live video on the other hand can still benefit from our optimization algorithm.In this chapter, we introduce the concept of virtual CDN as a Service (vCD-NaaS) using NFV and SDN tools. Through our proposal, we focus on the framework architecture, design and placement of vCDN use case based on SDN controller, e.g, OpenDaylight[128]. Then, an optimization placement algorithm for vCDN including content caching and request redirecting is introduced with operating system, network, and quality of experience constraints.The rest of this chapter is organized as follows: Section 4.2 investigates the related work. Section 4.3 proposes the vCDN concept in terms of system requirements and design methodology. Section 4.4 details the steps of the proposed virtual caching protocol. The optimization model is introduced in Section 4.5. The final optimization evaluation is presented in Section 4.6. The update performance if the cache prediction is slightly imprecise is evaluated through a comparison in Section 4.7 and then the work is concluded in the last section 4.8.

4. 2

 2 Related workThis section highlights the relevant NFV/SDN optimization algorithms in the virtualization context. Thus, facing the difficult combinatorial optimization problem in the sense of the theory of algorithmic complexity, there are two main solutions for the Virtual Machine (VM)/Virtual Network Function (VNF) Placement Problem (PP): 1) Exact approaches (optimal algorithms) and 2) Heuristic approaches (e.g., best-fit decreasing, first-fit decreasing, genetic, and meta-heuristic algorithms). We try to give an overview of the recent works. Niels et al.[START_REF] Bouten | Towards nfv-based multimedia delivery[END_REF] provide a framework for multimedia delivery CDN-based on NFV. They gave a structure of Point of Presence (PoP) deployment within the network. They used the three-layer structure (core network, aggregation layer, access layer) of the network to seek the optimal locations of cache nodes. Their work missed an optimization algorithm to measure the QoS/QoE. Further, they don't take into consideration the cooperation between CDN edge servers to serve user request. Also, the optimization model lacked many constraints such as the maximum server's storage capacity and the migration of content from one server to the optimal one. Michele et al.[START_REF] Bouten | Towards nfv-based multimedia delivery[END_REF] after presenting the state of the art of NFV, CDN, and stochastic optimization techniques, use a mixed architecture where real and virtual CDN nodes coexist. Although they present an interesting hybrid solution, their architecture assumes that the distribution of the future traffic demand is known which is not a realistic assumption. Hendrick et al.[START_REF] Moens | Vnf-p: A model for efficient placement of virtualized network functions[END_REF] gave a model for resource allocation of VNFs within a virtualized environment (NFV Infrastructure). Cloud scaling technologies for VNF instantiation are criticized in order to prepare for NFV use cases inside the Network Service Provider (NSP). They affirm that the NFV paradigm was not designed to be used only in Data Centers (DCs). We agree with their affirmation since in data centers we don't have link or storage capacity shortage. Indeed, cloud administrators provision their deployed clouds with enough link speed, storage, and computation resources. However, it is not the case in NSP since we face dynamic constraints on network, storage, bandwidth and latency. Authors propose another hybrid solution inside the operator network that mixes between the legacy networks based dedicated hardware for each network function and the virtualized software/instance running on basic and standard hardware in NFVI environment.The NFV resource allocation proposed by the authors gives different approaches for task and service deployment in hybrid NFV networks such as VM deployment on physical servers, and service deployment either on physical server or on VM. That model named (VNF-P) for virtual network function placement aims to find an optimal way for deploying a service chain characterized by a chain of VNFs taking into account some optimization features to minimize the overall cost of the deployment. VNF-P is a good abstraction of the deployment of NFV in an operator's network. But still, it is too general and does not address CDN specificity. Further, among the shortcomings of the proposed placement model for VNF, authors didn't consider real virtualization constraints such as storage, virtual CPU, virtual streaming costs. Moreover we think that they did not use an adequate distribution of user's requests and that they did not consider any QoE parameter or constraints to deal with user's demands variation.Bernardetta et al.[3] highlight three aspects in the general NFV placement problem which are: 1) network modeling, 2) generic VNF placement algorithm, and 3) VNF routing problems. They raise an important network flow problem related to (de)compression processes applied on through-traffic passing by VNF instances. This problem of VNF chaining requires high resource allocation. Further, they propose a multi-level objective function for VNF placement optimization. In fact, they present the problem of minimizing the allocated computing resources in a first stage and in a second stage, they perform a second optimization: the minimization of the maximum link utilization. The limitations of their approach are:

  Mathieu et al. [27] propose a placement problem optimization for the Deep Packet Inspection (DPI) networks through designing a vDPI (virtualized DPI) solution. Moreover, they consider the strong relationship between NFV and ISPs in order to host dedicated cloud systems in ISP's Point of Presence (PoP). Their work was concentrated on where to instantiate vDPI in the network to reduce the cost and overcome challenges in the vDPI deployment process. They then gave their general placement model for vDPI cost based placement constrained by OPEX, CAPEX, and cybersecurity costs (since DPI is a security network function). Authors aimed to propose a model capable of minimizing network load and total number of deployed vDPI engines. This contribution is useful for our CDN placement problem. There are however major differences between the deployment of DPIs and CDNs. Moreover, authors assume the knowledge of the traffic flow distribution. This static parameter has limited their solution.

Figure 4 - 3 -

 43 Figure 4-3 -OPAC-based vCDN deployment architecture

  Fig. 4-3 and consists of two new entities (with respect to the SDN basic architecture [105]):

Figure 4 -

 4 Figure 4-4 -vCDN cache as a service

Figure 4 - 5 -

 45 Figure 4-5 -vCDN hit cache scenario

  Figure 4-7 -Example based OPAC-analytical procedure for vCDN placement

Figure 4 - 8 -

 48 Figure 4-8 -Network topology used for OPAC evaluation

4. 6 . 1 Figure 4 - 9 -

 6149 Figure 4-9 -Network optimization costs: vCDN number impact

Fig. 4 -

 4 Fig. 4-11a, we plot the cost of streaming against vCDN number. The vCDN caching/streaming nodes may serve SD, HD, or UHD content resolution to the clients. Recall that vCDN nodes serve the clients according to their initial requirements. Virtual streaming cost is increasing in each category when vCDN num-

  Figure 4-11 -Network optimization costs: vCDN resolution impact

  Figure 4-12 -Network optimization costs: delivery capacity impact

  Figure 4-13 -Network optimization costs: delivery storage impact

Figure 4 -

 4 Figure 4-15 -Operator gain after executed the optimal migration algorithm comparing to the non optimal

Figure 4 - 16 -

 416 Figure 4-16 -Comparison between OPAC and Bernadetta et al work

Figure 5 - 1 -

 51 Figure 5-1 -OPAC: vCDN-YouTube migration use case

118CHAPTER 5 .Figure 5 - 2 -

 552 Figure 5-2 -Example of a Gomory-Hu tree transformation.

Figure 5 - 3 -

 53 Figure 5-3 -Example of HPAC vCDN content replication/migration.

120CHAPTER 5 .Figure 5 - 4 -

 554 Figure 5-4 -Network topology used for small scale

Table 5 .Fig. 5 -

 55 Fig.5-7a and 5-7c depict the total migration delay time and the total migration cost respectively. Further, Fig.5-7b shows the total replication number. These

124CHAPTER 5 .Figure 5 - 6 -

 556 Figure 5-6 -Network topology used for large network scale.

Figure 5 - 7 -

 57 Figure 5-7 -HPAC in large network scale.

Figure 5 - 8 -

 58 Figure 5-8 -OPAC and HPAC run-time in large network scale.

Figure 5 - 9 -

 59 Figure 5-9 -Main use-cases for OPAC/HPAC in an SDN/NFV framework.

Figure 5 - 10 -

 510 Figure 5-10 -Sequence diagram for OPAC/HPAC integration.

131 132CHAPTER 6 .

 1316 Figure 6-1 -vCDN network orchestration

134CHAPTER 6 .Figure 6 - 2 -

 662 Figure 6-2 -virtual CDN architecture according to ETSI standard

Figure 6 - 3 -

 63 Figure 6-3 -VNF space for virtual CDN

Figure 6 - 4 -

 64 Figure 6-4 -Management, orchestration, and VNF spaces for vCDN

8s 2 S 5 .

 25 : Flow balance or conservation constraint (which is the Kirchhoff laws)

144CHAPTER 6 . 9 )

 69 OPTIMAL AND COST EFFICIENT ALGORITHM FOR VCDN ORCHESTRATION Moreover, NFV/SDN criteria are considered in the sense that each vCDN may serve either Standard Definition (SD), High Definition (HD), or Ultra HD (UHD) In order to maximize the average QoE of the customer's clients, extending the vCDN components in the orchestration process is important and reduces the endto end response time and the access delay. Therefore, the objective function has to minimize the response time of all the clients. This is equivalent to minimize the total migration cost. Hence, the proposed objective function is formulated in equation (6.10) (cost function): min X s2X=fP oP ;H;U g X f 2F

Figure 6 - 5 -

 65 Figure 6-5 -OCPA: vCDN orchestration example

Figure 6 - 6 -Fig. 6 -

 666 Figure 6-6 -Network topology used for the OCPA evaluation

Figure 6 - 8 -

 68 Figure 6-8 -vCDN migration time

Figure 6 - 9 -Figure 6 - 10 -vCDN replica number 2 .

 696102 Figure 6-9 -vCDN network optimization costs

Figure 6 -Figure 6 -

 66 Figure 6-11 -vCDN network optimization costs: user side

  be considered. In DVD2C project [129], we considered different layers of vCDN request deployment representing the extended position of vCDN: i) vCDN-to-the PoP layer which is representing the operator core data center, ii) vCDN-to-the home network which is representing by the home gateways or Set-Top-Boxes (STB) and iii) vCDN-to-the user devices layer which is represented by the end-user devices. Precisely, our proposal is strongly based on the Technique for Order of Preference by Similarity to Ideal Solution (TOPSIS) method [83]. This technique transforms the context of the end-user (QoE), network operator (cost of migration) into two parts: i) alternatives or options and ii) criteria or attributes. Algorithm 4 summarizes the pseudo code of TOPSIS based vCDN migration. It is based mainly on two steps:

154CHAPTER 7 .

 7 CDNAAS FRAMEWORK: TOPSIS AS MULTI-CRITERIA DECISION MAKING FOR VCDN M erage QoE measured and required according to the signed and valid SLA (i.e., content provider (cp) cost, (cp) config, and (cp) quality).

  -

Figure 7 - 1 -Fig. 7 -Figure 7 - 2 -

 71772 Figure 7-1 -The TOPSIS sequence for vCDNTTX decision

158CHAPTER 7 .Figure 7 - 3 -Fig. 7 -

 7737 Figure 7-3 -VM migration and interruption times

Figure 7 - 4 -

 74 Figure 7-4 -Optimization of CDNaaS workflow for DVD2C project

•

  TOPSIS-DB: a database that includes the ranking values (output of the TOP-SIS technique) representing the Layer selection work. Ranks are then entered as an input in the optimization model through inserting the rank values in the initial DB.

Figure 8 - 1 -

 81 Figure 8-1 -ICN based active network scenarios

  as examples. Hence, a new look at the networking model must follow these novel networking architectures for such potential matching between network architecture, model, and optimization. ICN, acting as a network compiler/interpreter (of interests and data), adds work to each intermediate node between the producer and the consumer. It can add or consume bandwidth. Therefore, we next give an overview of ICN (as a use case) and the features it brings to the networking layer.

Figure 8 - 2 -

 82 Figure 8-2 -Active node budget mapping

7 )

 7 Description of the model: The model considers the scenario of ICN active network where intermediate nodes participate in the content distribution process. The formulation maximizes the maximum flow between each pair of sourcedestination nodes (F s;t ) (Eq. (8.1)) under Kirchhoff law constraint on intermediate nodes and at the source node respectively (Eq. (8.2) and (8.3)). Then, an amended bandwidth constraint as defined in Eq. (8.4) where network flow is amplified by

Figure 8 -

 8 Figure 8-3 -G-H based ICN insertion

Fig. 8 -

 8 Fig. 8-4 depicts the runtime which is the execution time of the algorithms. Fig. 8-5a shows the treatment cost of the ICN data in terms of resource size (storage).The parallel task number is the total number of the treatment task (how many times we need to treat the requested data). It is plotted in

Figure 8 - 5 -Figure 8 - 6 -Fig. 8 -

 85868 Figure 8-5 -OPPA-HPPA comparison in the small network scale scenario

Figure 8 - 7 -

 87 Figure 8-7 -HPPA in large network scale scenario

3 .

 3 Home Box assisted CDN (HB-CDN): Soraya et al.[START_REF] Chellouche | Home-box-assisted content delivery network for internet video-on-demand services[END_REF] describe an algorithm introducing a new equipment or gateway as a middle-ware between the CDN and end users. This equipment is for content caching and acts as a content provider for the end users. It reduces server load, and minimizes time delays. Some DSL operators start to have an equivalent caching system in the box especially useful for replay and short delay replay (almost real-time broadcast).4. Incentive Caching For P2P-VOD Systems (RBS): Weijie et al.[START_REF] Wu | On incentivizing caching for p2p-vod systems[END_REF] proposed a reward-based scheme (RBS) in large scale p2p on demand streaming. This algorithm offers two pricing schemes where the content provider proposes strategies in order to serve the desired content to the end users while taking into account the operational cost of the content provider. The first strategy is used to meet the high demands of users. It takes into account the relationship between users demand and the number of replications of content. The second strategy is used to reduce the reward of items with high operational cost.

  Figure C-1 -Total migration cost

  f v . Fig. C-2 shows that the number of replica in "loose scenario" increases with jFj and jV j while it reaches a static value at jV j = 10. Therefore, in terms of migration cost, we have an open question that we do not answer: what will happen if we add

  Figure C-2 -Replica number impact

  Up to now, exact and heuristic algorithms proposed in the previous chapters are centralized by SDN. A global view of the network is needed to calculate an optimal topology of routing requests. The underlying infrastructure is dumpy and does not take any decision of traffic migration or optimization. Now, and following the introduction of active nodes such as ICN that decide an increase or degradation of flows, one needs a distributed version of the maximum flow algorithm used in the previous chapters. So we propose in this chapter, a distributed single source maximum concurrent flow algorithm called SS-DMCF. The rest of this chapter is organized as follows: Section D.2 highlights the state of the art of the MCF algorithms. Section D.3 introduces the potential MCF computing models. Then, Section D.4 gives execution methods of MCF. Section D.5 studies the combinatorial MCF optimization models. Section D.6 gives an idea about the potential applications the may rely on MCF. Section D.7 highlights our proposed distributed MCF algorithm. Section D.8 compares the MCF optimization techniques and the work is concluded in Section D.9. Different pseudocodes of the used algorithms are given in annexes.

Fratta [ 65 ]

 65 . The approximation algorithms for the MCF problem use in general either incremental or flow deviation based approaches. In the incremental based approach, length function is l (e) = e f (e) while in the flow deviation based approach, the length function is c(e)

" 2 ) 3 .

 23 Two distributed solution are proposed by Awerbush et al. called: 1) a greedy distributed optimization, and 2) an approximate steepest descendant framework.In the approximate steepest descendant framework, authors propose the following algorithm that solves the DMCF. It is executed in T phases and T p steps: For (T phases) do (a) T P steps O (L*log 2 (m)* log( k=")) (b) For (T p steps) do i. f e i f low current flow valueii. for (each commodity i, such that d i /T flow between (s i and t i ) not yet routed ) do in parallelA. C e i = " 2 log(m) f e i B.Compute fblocking flowg under capacities C e i from s t to t i that routes flows along (1+ ")-approximate shortest paths (in terms of congestion (l(e))C. Route this flow / d i /T this flowAuthors raise the potential use of MCF for QoS routing including the pure routing and flow control issues. They claim that MCF problem models exactly the pure routing problem in networks. The main idea is to route a small amount of flow (of all commodities) on edges. This amount need to be placed initially which determines a feasible flow. Then, this amount is increased in a multiplicative way.Authors fix an edge length function (the metric) as follows:The blocking flow technique used here is computed by sending flow from the source to the destination along the shortest path in terms of the previous length function.. In the greedy distributed framework, authors use the same framework. Indeed, multiple agents operate in cooperative manner but uncoordinated way. Congestion and bandwidth management are raised as the main application of their work. They propose a stateless greedy distributed algorithm for the concurrent multi-commodity flow problem with poly-logarithmic convergence. The approximation is done around 1+ " distance from the exact solution. The running time is O(H log O(1) m 1 "

  rent throughput (concurrent flow). Authors introduce then problem of concurrent multi-commodity flow problem by including the following congestion indicator: The objective function of their work is then as follows. Minimize (congestion) def = Min(Max( l (e) ) def = Min(jf j) They introduce then the billboard framework. It is a computing model that is distributed, based on multiple agents that operate in coordinate manner but uncoordinated way.

3 : Initialization 0 4 :• 4 :

 344 While there exists a shortest-path tree (in terms of hops) SPT spanning T (s) in R G : • Find the maximum flow such that d k can be concurrently routed in SPT between s and t k • Augment the flow and update R G Set flows in all edges to 0 • Set residual graph R G equal to initial graph 2: Output: The value of the maximum concurrent flow between s and T (s). 3: Initialization 0 While there is a flow augmenting path tree from s to T (s) in R G : • Find the shortest augmenting path tree SP T between s and T (s) in R G • Find the maximum concurrent flow along SP T • Broadcast SP T • Update flows • Update R G using SP T and • + end while we have multiple sources called S representing data producers and a set of destinations related to each source called T (S) representing their data consumers. A tree routed on S and spanning T (S) called Spanning tree represents the relation between the entities.

D. 7 . 1

 71 Finding single-source shortest path tree (SPT) Definition: Single-source shortest path tree: is the problem of finding shortest path between a single source vertex and every other vertex in the graph. Algorithm: It is based on Pregel, a Google library for asynchronous distributed (a) Emit ((i, j): c -*. D) (b) Emit ((i, j): *. D) 2. Else: emit ((i,j):c)

3 .

 3 Simple and not complex: It requires only QoS metrics that indicate the flow utilization of all commodities.

Figure D- 1 -

 1 Figure D-1 -Intermediate node program

Figure E- 1 -

 1 Figure E-1 -HoICN layer responsibilities

Figure E- 2 -

 2 Figure E-2 -HoICN topology: Massive IoT data

9 )

 9 Figure E-3 -Network topology used for large scale

Fig. E-

  Fig. E-3a, we show the initial topology used for the evaluation. It is undirected and weighted graph that has 100 vertices representing network nodes and 200 edges. The transformed graph based on Gomory-Hu method is shown in Fig. E-3b which has only 99 edges (49:5%). These figures depict the topology used for evaluating HoCCN placement algorithm in a large scale scenario.To assess HoICN optimization algorithm, we used the runtime and the consumer delay metric. It represents the response time when using ICN facility to cache the computation result instead of the legacy Hadoop process where intermediate network nodes do not interpret consumer interests. sg(f ) represents the server that initially executed the code on the local data and then it cached the computation result. s v represents the access point toward the consumer group. This

Figure E- 4 -

 4 Figure E-4 -HHPA: execution runtime

Fig. E- 4

 4 Fig.E-4shows the end-to-end consumer delay needed for retrieval a computation result. Result shows that HoICN method reduce the total delay. This is due to ICN deployment facility placed between the producer and the consumer. The legacy Hadoop network which does not imply this feature suffers from significant consumer delay comparing to our HoICN.

The proposed algorithm starts by ( 1 )

 1 getting content popularity and (2) selecting a target content in the order of popularity then (3) a route candidate is extracted to deliver the target content from a cache location to a requesting user on the shortest path tree rooted at the origin site of the target content and defining the route candidates as the design variables then (4) design the optimal cache locations for the target content based on the route candidate in consideration of the pre-designed routes for more popular content having the same origin site as that of the target content then (5) go to step (2) and execute the design of the next target content.The work in[START_REF] Choi | In-network caching effect on optimal energy consumption in content-centric networking[END_REF] investigate the minimum energy consumption that CCN can achieve with optimal cache locations by considering different caching hardware technologies, number of download per hours and content popularity. The authors firstly set up an energy consumption model for CCN and then formulate linear and non-linear programming problems to minimize total energy consumption of CCN. Also a heuristic approach through a Genetic Algorithm (GA) is proposed to find energy efficient cache locations. Using reported energy efficiency of computational hardware and network equipment, the chapter shows that CCN yields greater energy savings for very popular content and small sized catalog compared to conventional Content Delivery Network (CDN). The results also indicate that two aspects of the memory technology, energy-proportional caching and sufficient memory capacity are critical to the overall energy gain of NDN. This chapter focuses only on energy efficiency regarding data delivery and storage and do not consider energy consumption caused by other computations (e.g. name lookup and security). In a similar context, the work in[START_REF] Guan | On the energy efficiency of content delivery architectures[END_REF] examines energy consumption of content delivery architectures comparing the benefits of CCN and optical bypass. The chapter compares Content Delivery Network (CDN) versus CCN in content delivery efficiency. The authors show that by optimizing the content placement according to its popularity, CCN achieve good scalability in energy consumption in delivering popular content (i.e. the per-bit energy decreases as the download rate increases). On the other hand, dynamic optical bypass is more efficient in serving less popular content. In addition, equipment energy efficiency and network topology are two other factors impacting energy consumption in CCN. The results show that CCN consumes less energy in delivering a small sized catalog while conventional based CDNs consumes less energy in delivering a large sized catalog. Consequently, it is suggested that a synergy of CCN, server-based CDN and dynamic optical bypass architectures may improve the energy efficiency in serving content with heterogeneous popularity. The work in [29] presents energy efficiency issues in ICN showing how in network caching in ICN raises energy consumption concerns and showing the importance of quantifying the energy consumption of transmission links plus storage to best design the cache replication strategy in ICN. What's important to consider also are the frequency of content request and the content popularity. The chapter gives an overview on the energy consumption of different memory technologies, sizes, and access techniques. The chapter also discusses the impact of the layer of caching in the network on the consumption and the tradeoffs between energyefficiency and performance.

p sff

  The placement cost of f on sDecision variables Definition x sPlacement binary variable which indicates that the ICN/IoT (f 2 F) should be placed on the (optimal) server s 2 S y s v;f Mapping binary variable which indicates that consumer group (v 2 V ) needs an ICN/IoT container (f 2 F) and ICN/IoT is placed on the server s 2 S z v;f i;j Flow balance binary variable which indicates whether the link (i; j) is used for sending IoT data f to v

  OPA is based on a Gomory-Hu transformation of the initial graph G = (V (G); E(G)) where V are the set of vertices and E are the set of edges. Vertices represent the network servers and edges represent the relation between vertices.

Algorithm 14 OPA

 14 : Optimal Placement Algorithm for ICN/IoT1: Input: V , S, D s , F, f size , C s , L i;j , d f v , p s f , G = (V (G); E(G)), 2: s v , s f 3: Output: x s f ,total ICN placement cost 4: CT C Cut-Tree-Construction G, L i;j 5: Upgrading-ICN/IoT-software 6: ICN/IoT-Caching

Figure F- 1 -F. 5 . 1

 151 Figure F-1 -ICN-based IoT distribution network. Given the network topology, consumers requests, and objects served by content providers, OPA model chooses which server should be upgraded with ICN/IoT software.

Figure F- 2 -

 2 Figure F-2 -Data consumer delay

Fig. F- 2

 2 Fig. F-2 shows the impact of ICN nodes on the data consumer delay. Resultsshow that OPA reduces the total delay.

Figure F- 3 -

 3 Figure F-3 -OPA run-time in scale-free network

Fig. F- 4

 4 Fig. F-4 shows the OPA placement cost against ICN node number in scale-free based IoT network. Different ICN sizes (in terms of memory) are used. Fig. F-5a and Fig. F-5b show the OPA placement delay and the OPA caching respectively (OPA caching equals to the number of ICN migrating nodes which represents the caching policy strategy). The curves have an increasing slope up to jFj = 60 and then they decrease. This point represents the average ICN node number stabilizing the IoT network according to consumer group interests.

  Figure F-5 -OPA in scale-free IoT network

Table 2 .

 2

	1 -CDN infrastructure and compositions
	CDN composition issues		Taxonomy
	CDN infrastructure	Underlay		Overlay
	CDN servers	Origin		Surrogate	(Replica
				Server)
	CDN content type	Static or embedded	Dynamic
	CDN cache protocols	Intra-cache:	NECP,	Inter-cache: CARP, ICP,
		WCCP, SOCKS		HTCP, Cache digest
	CDN Interaction	Caching proxy		Surrogates and subnet

Table 2 .

 2

	2 -CDN delivery and management
	CDN delivery and management	Taxonomy
	Replica servers placement	Single-ISP	Multi-ISP
	Selection of content	Full site content delivery Partial site content de-
			livery
	Outsourcing of content	Cooperative push based (Non)Cooperative pull
			based
	Caching techniques	Content replication and	Caching content update
		caching

metrics are used for request routing such as closeness, latency, distance, and load.

Table 2 .

 2

		3 -CDN Request routing techniques
	CDN routing issues	Routing tech-
		niques
	Routing algorithms	Non-adaptive	Adaptive
	Routing mechanisms	GLSB	DNS	HTTP URL Anycasting CDN peering

Table 2 .

 2

		4 -CDN performance
	CDN performance issues		Taxonomy
	Network procurement	Dependent	replica	Independent	replica
		server		server
	Simulation		Simulation tools
	a content delivery network based on symmetric connections between peered

Table 3 .

 3

			1 -Live migration requirements
		CPU	Storage con-	Network connec-	Memory content
		State	tent		tion
	With	Same	Shared		ARB broadcast	Coping memory
	shared	context				pages
	SAN
	Without	Same	Transferred,
	shared	context	Needed	for
	SAN		high	link
			speed

Table 3 . 2

 32

				-vCDN comparison
		vCDN		vCDN		vCDN		vCDN
		based	on	based	on	based	on	based	on
		Cloud		NFV		SDN		SDN&NFV
	Programmablity No		No		Yes		Yes
	Migration	Yes		Yes		No		Yes
	Protocols	HTTP		None		OpenFlow	OpenFlow,
								JSON,
								HTTP
	QoS	Low		Low		Medium		High

Table 4 .

 4 1 -OPAC mathematical notation

	Parameters	Definition
	V	The set of client group nodes
	S	The set of server nodes
	S 0	The set of optimal server nodes
	D s 0	Maximum throughput of the streaming server s 0 2 S 0
	F	The set of vCDN nodes
	f size	vCDN	resource's	size
		vRAM; vCP U ; and vDISK f 2 F
	C s 0	Maximum storage capacity of the server s 0 2 S 0
	C i;j	Link capacity between two nodes i and j (from
		i to j)
	f v d
	Decision variables Definition
	x s;s 0 ;f	Placement and migration binary variable which indicates that f should move from from s to s 0
	y s 0 v;f	Binary variable which indicates the video hit from node v of f in server s
	v;f i;j z

Throughput used for streaming the vCDN functionality f 2 F to the client group v 2 V . It represents the user's demand requirements (SDT V ; HDT V ; U HDT V ) c s;s 0 ;f

The migration cost of the functionality f from s to s 0

Table 4 .

 4 2 -Comparison between OPAC and state-of-the-art

	Work	Metrics	Limitations
			No virtual node cooper-
	Niels et al. [28]	Bandwidth, deployment cost	ation, no QoE parame-ters, missed capacity and
			RAM constraints
			Known traffic distribu-
	Michele et al. [116]	Usage cost	tion (static), unreliable
			Virtual CPU, virtual
	Hendrick et al. [122]	Deployment cost, service request	storage, virtual capacity, and QoE constraints are
			missed
			Prioritization	method
		Allocated computing	with orthogonal cost
	Bernardetta et al. [3]	resources, link	functions, virtual RAM
		utilization	and QoE constraints are
			missed
	Mathieu et al. [27]	CAPEX, server's load Offline and no migration measurement,
		System, network, and
	OPAC algorithm	quality metrics	No limitations

Table 5 .

 5 1 -OPAC mathematical notation in a migration use case

	Parameters	Definition
	V	The set of client group nodes
	S	The set of server nodes
	s v	The default server that connects the client group node v 2 V
	s f	The server that initially caches the vCDN node f 2 F
	D s	Maximum throughput of the streaming server s 2 S
	F	The set of vCDN nodes
	f size C s	vCDN' s size (vRAM; vCP U ; vDISK) (f 2 F) Maximum storage capacity of the server s
	L i;j	Link capacity between two nodes i and j (from i to j)
	d v f	Throughput used for streaming the functionality f to the client group v 2 V . It represents the user's demand requirements
	m s f	The migration cost of the functionality f to s
	Decision variables	Definition
	x s f	Placement and migration binary variable which indicates that f should move from origin server to optimal server s
	y s v;f	Binary variable which indicates the video hit from node v of f in server s
	z	v;f i;j

Table 5 .

 5

		2 -Gap (migration cost): HPAC efficiency
	vCDN number	6	7	8	9	10	11
	Gap (%)	0:66	0:42	0:25	0:62	0:62	0:3

Table 5 .

 5

	Metrics	OPAC	HPAC
	Algorithm	Exponential	O(N 3 M 1=2 )
	complexity
	Run-time	A few seconds in SS; a	A few second in SS/LS
		few minutes in LS
	Total migration	Excellent in	Good in SS/LS
	cost	SS;unfeasible in LS
	Total migration	Good in SS;unfeasible	Excellent in both SS/LS
	time (i.e.,delay)	in LS
	Replication	Free/loose in SS;	Free/loose in SS/LS
	number	unfeasible in LS
	vCache/vStream	Good minimization in	Excellent minimization
	cost	SS	in both SS/LS

3 -Efficiency comparison between OPAC and HPAC; SS: Small Scale,LS: Large Scale N = jV (G)j, M = jE(G)j

Table 5

 5

.3 . 126CHAPTER 5. SCALABLE AND COST EFFICIENT ALGORITHMS FOR VCDN MIGRATION

Table 6 .

 6

	1 -Mapping between simplified vCDN and ETSI-MANO
	ETSI-	Our mapped entity
	MANO
	NFVO	CDN orchestration module
	VNFM	CDN Manager, OCPA
	VIM	OpenStack
	EM/VNFs	Caching and streaming nodes with
		a request routing node
	NFVI	VMs
	OSS/BSS	Not used here

Table 6 .

 6 2 -Comparison between vCDN and ETSI-MANO

	Our design	ETSI-MANO correspondence
	NFVI space	NFVI
	VNF space	VNF/EM
	Orchestration	VNFM, NFVO
	space
	Management	No entity, this space is specific for virtual
	space	CDN service. It interacts directly with a
		content provider which is the customer
		of CDN service.

Table 8 .

 8

			1 -Mathematical Notation
	Parameters	Definition
	V	The set of client group nodes
	S	The set of server nodes
	F	The set of virtual nodes (e.g., vCDN nodes)
	D s	Maximum throughput of the streaming server
			s 2 S
	C s	Maximum memory capacity of the server s
	f size	virtual node's size (vRAM; vCP U ; vDISK) (f 2
			F)
	L i;j	Link capacity between two nodes i and j (from
			i to j)
	d	f v	The set of consumer demands in terms of inter-ests
		s	A budget parameter that indicates the in-network processing in node s
	B	The total network budget for ICN node up-
			grade in terms of money
	B i	The budget of node i in terms of money
	t s f	The treatment cost of the functionality f to s
	Decision variables Definition
	x s f	binary variable which indicates that node s should be upgraded by ICN software to store
			and treat data.
	y s v;f	Binary variable which indicates the video hit from node v of f in server s
	z i;j v;f	Binary variable indicating whether the link (

Table 8 . 2

 82

	Metric	Small scale	Large scale
		OPPA HPPA	OPPA	HPPA
	Run-time(sec)	< 7	< 1	unfeasible	< 7
	total treatment cost(Gb)	low	high	unfeasible bounded(< 14)
	total task number	stric	loose	unfeasible bounded(< 90)

-Efficiency comparison between OPPA and HPPA

Table A

 A

		.1 -Direct caching techniques
	Technique	Advantage		Improved metric Limitations
	CP [34]	Simple	imple-	Video popularity Single point of
		mentation, QoE		failure, increase
		enhancement		server's load
	WCRP [152] Cache manage-	Network band-	Increases the de-
		ment		width	lay
	MDC [143]	Reduces server's	load	No scalability
		load
	PALC [164]	Cache efficiency	capacity	Maintain	only
					popular	video,
					no cache update

Table B .

 B

		1 -Content moving techniques
	Technique Advantage	Improved	Limitation
			metric
	PBC [31]	Scalability	Popularity	Complex
			function
	CaaS [70]	Network utiliza-	Throughput Missed architec-
		tion		ture

Table B

 B

		.2 -Replication techniques
	Technique	Advantage	Improved metric Limitation
	RLB/ARLB

  In asynchronous execution, each round corresponding to a commodity (agent) is started without a clock indicating the beginning of the round. This execution is used by Awerbush et al. in their work (distributed MCF) in which he gives an upper bound of the number of phases (rounds). Hence, there is a determined round number sufficient to estimate Edge-path, node-edge and tree formulationsWe denote the set of all paths between end nodes i and j for demand pair fi; jg 2 D by P ij . The union of P ij over all demand pairs is denoted by P , and the set of edges in path p is denoted by E p . According to these notations, the equivalent

	MCF formulations (edge-path model is modeled below) is given as follows using
	linear programming technique:
			max( )	(D.1)
			s.t.
	X	f p =	d i;j 8fi; jg 2 D	(D.2)
	p2P i;j
	X	f p c i;j 8fi; jg 2 E	(D.3)
	p2P :fi;jg2E p

  E. OPTIMAL HADOOP OVER ICN PLACEMENT ALGORITHM FOR NETWORKING AND D tributed nodes. For instance, HDFS layer is controlled by name nodes and is dis-ICN is used to compute, and to cache the computation result within the network. Hadoop is data agnostic and it can interact with heterogeneous data collectors (e.g., IoT data, call data record (CDR), etc...). For instance, it can process massive IoT data on the fly (in-network processing) instead of migrating data toward the centralized/consolidated cloud controllers (NFV/SDN). ICN node support of hadoop interest/data exchanged messages includes an extra data structure beside the legacy tables already proposed in the IRTF standard such as FIB, CS, and PIT. It is called Hadoop Information Table (HIT).

	tributed through different data nodes (caches). On the other hand, MapReduce
	layer is controlled by Job Tracker and is distributed through different Task track-
	ers (processors). The central/distributed (hybrid) architecture nature of hadoop
	may benefit from ICN networking architecture [108] that provides a distributed
	cache network able to process and cache on the fly massive data.
	HDFS and MapReduce layers cooperate together to allow storage and process-
	ing functionalities within the same system. MapReduce component processes and
	analyzes data traffic from different locations including network nodes, ICN cache
	nodes and buffers (memory). It is also adapted for quantifying/analyzing net-
	E.3.3 HoICN node architecture
	In general, HoICN will be useful when the big data request involves informa-
	tion available in the network (traffic analysis, IoT information, Video...). This net-
	work data is directly treated and mapped onto the data mining format (Hadoop
	ing in different disciplines such as information fetching, neural science and deep in our case). HoICN approach is based on two ICN packet types: hadoop inter-
	learning. It consists of two main components: Hadoop Distributed File System est packet corresponding to a consumer group request for a computation result
	(HDFS) and MapReduce. The former is responsible for data storage and presenta-(instead of data in the legacy ICN paradigm). Hadoop interest is a simple mathe-

tion (i.e., a storage layer) while the latter is responsible for parallel processing and distributed computation (i.e., a compute layer). From a design perspective, Hadoop is a decentralized (hybrid) architecture where each component (HDFS or MapReduce) is centralized and controls dis-234APPENDIX work behavior and detecting anomalies. MapReduce provides then the capability to run distributed computations and generate data sets needed for traffic analysis through analytic tools. For the sake of simplicity, in the proposed architecture, MapReduce aggregates data in the distributed ICN-enabled data nodes. Then, global data sets are generated and used by different tools to extract the requested aggregated information such as medical reports in a e-health context or environmental indicators in weather forecast one, etc. matical or statistical named function (e.g., max, min, average, etc...). The second HoICN packet type is a hadoop data packet corresponding to the computation result of executing this function on local data. Hadoop related functions are moved toward the data instead of data moving in order to save network bandwidth and storage.

  3. Strategy layer:The forwarding strategy of hadoop interest and data is as following: i) ICN router does a longest-prefix match lookup on the HIT table indexes, ii) If there is a computation result information (CRI) matches the hadoop interest name, then the named function is already executed and the result will be forwarded back to the consumer. Otherwise, the router binds the CRI name to the requesting face in PIT data structure. Then, the ICN router forwards the hadoop interest to where data reside.

	4. Storage: The network is in charge of caching the processed data results in
	different ICN nodes.
	5. Secure Hadoop (sHadoop): using ICN as hadoop distributed storage and pro-
	cessing will benefit from data integrity inherent is ICN.
	6. Analysis and recommendation: This layer is responsible for data analysis
	(through hadoop tools). It proposes some recommendations to end users.
	7. Browser and data science: This is the consumer application that injects
	hadoop interest within the ICN network. Extracting knowledge (data sci-
	ence) from data may enhance response feedback through recommendations
	given from the network.

E.3.5 Massive IoT data as a use case

Processing massive IoT data constitutes a big data network. Therefore, it is a potential use case for Hadoop. In Fig.

E-2

, we depict a merging network topol-

Table E

 E

		.1 -HoICN Mathematical Notation
	Parameters	Definition
	V	The set of consumers
	S	The set of server nodes
	D s	Maximum network capacity of the server s 2 S
	F	The set of ICN-Hadoop data nodes
	G	The set of named functions
	g(f ) size	The size of the computation result in terms of mem-ory (f 2 F, g 2 G)
	C s

  proposed in this chapter to use ICN for Hadoop-based systems and we map Hadoop functions onto ICN routing nodes. In this context, we presented two optimization algorithms (HOPA and HHPA) to deal with small and large network scales respectively. Experiments demonstrate that the integration of Hadoop with ICN benefits from the distributed nature of both concepts. Results show that the ICN support of Hadoop is feasible for large network scale and the end-to-end consumer delay is reduced. We are working on getting this architecture and optimization running on our virtual placement platform and outsourced in[START_REF] Tamayo-Ibnkhedher | vios (virtual infrastructure optimization simulator)[END_REF] 2 .As presented in this chapter, hadoop can benefit from ICN distributed file layer to analyze and mine the global knowledge and behavior of the IoT network. In the next chapter, we detail the IoT use case and propose a network optimization tool.rameters not only covering network issues but also limited system resources.

	As network optimization deals with very large graph topologies, classical exact
	optimization techniques do not fit our problem. Instead, we use the well known
	Gomory-Hu (G-H) method [73] to detect the network bottlenecks through the
	maximum-flow minimum-cut theorem [62] and to find different tree levels for
	potential upgrade in ICN/IoT nodes and gateways. G-H is an optimal network
	flow algorithm that compacts the network graph structure using cuts to retain
	only feasible candidate topology and consequently lead to a smaller scale ICN/IoT
	placement problem. Although each ICN/IoT node is secured since its production,
	we present some security considerations to emphasize the reduction in network
	security cost while enabling ICN for IoT with different security levels.
	F.2 ICN in IoT and related work
	F.2.1 ICN principles
	ICN names the content rather than the host in the networking level. Dif-
	ferent ICN architectures are proposed such as: network of information (NetInf)

The rest of this chapter is organized as follows: Section F.2 highlights ICN and its operation in IoT and the related work. Section F.3 presents our Optimal Placement Algorithm, (OPA) for ICN/IoT network architecture. Section F.4 discusses some security considerations and Section F.5 evaluates the algorithm performance over large graph topology. In Section F.6, we compare OPA in ICN/IoT with a traditional IoT network deployment. We conclude the chapter and present our future work in Section F.7.

  fundamental features of the ICN architecture (e.g., node model, naming, routing, transport, caching, etc.) and the strategy layer for the adaptive forwarding[START_REF] Van Jacobson | Networking named content[END_REF]. In ICN, names are hierarchical and similar to URLs. Name Resolution Service (NRS) and data routing procedures are in general integrated or coupled. The exchanged messages between consumers "data requestors" and producers "data original providers" are respectively in the form of interest packets and data packets. Indeed, end-users express only what they want (content name), and they let the ICN network respond to the where and how the content will be retrieved. Therefore, an appropriate ICN topology is an optimization per se. ICN network consists of consumers that request the content, producers that originally provide/publish these content, and ICN routers that cache/treat the content. The

	ducer mobility (publishers) in ICN network, through letting the consumers fetch
	the produced data easily after producer mobility. A survey of different solutions
	Caching in ICN usually implies the on-path caching and CSs use by default the
	Least Recently Used (LRU) replacement policy. Off-path is also supported by redi-
	recting user interest to a Content Delivery Network (CDN) (as an example) and not
	to the source/publisher of the content. ICN needs new mobility management so-
	lutions different from host-centric approaches. The Kite model [189] proposed by
	UCLA presents a novel solution for data producer mobility, leveraging the state of
	PIT table on each ICN router to reach Mobile Nodes (MNs). Kite supports different
	mobile application scenarios such as push, pull, share and upload. Firstly, a corre-
	spondent node contacts an anchor node, and each time it requests published data,

Most of these information-centric network architectures are implemented on top of TCP/UDP/IP/P2P layer. All of them, are originally inspired from the early work of van Jacobson

[START_REF] Van Jacobson | A new way to look at networking[END_REF]

who introduced the baselines and the content router (CR) in ICN has three main data structures as follows: i) Forwarding Information Base (FIB) table: it binds the content name to the next hop as in IP layer that binds the IP prefix to the destination, ii) Pending Interest Table (PIT): it binds the content name of the unsatisfied requests to the requesting face, and iii) Content Store (CS) table: it binds the content name to the data per se.

interests follow the PIT table to contact the anchor node, and then follow traced interests to reach the mobile node. The approach is relevant and requires interest packets targeting a mobile producer to always pass by anchor (which can present a single point of failure). Moreover, authors design how to support the data pro-

Table F

 F

		.1 -Mathematical Notation
	Parameters	Definition
	V	Data consumers (e.g., IoT-enabled vehi-
		cle)
	S	Data producers (e.g., mobile edge cloud)
	D s	Maximum network capacity of the server
		s 2 S
	F	The set of ICN/IoT nodes or containers
	f size	ICN/IoT container's size in terms of memory (f 2 F)
	C s	Maximum memory capacity of the server
		s
	L i;j	Link capacity between two nodes i and j
		(from i to j)
	f v d

Table F .

 F 2 -Efficiency comparison for OPA and IoT SigFox network

	Metrics	ICN/IoT assisted OPA	Sigfox
	Caching strat-	Migrating	ICN/IoT
	egy	nodes	acting	as
		edge/fog	computing
		nodes.

According to Internet IETF Draft, draft-jenkins-alto-cdn-use-cases-03

Cisco Distributed Director, Cisco White Paper, Cisco Systems

https://tools.ietf.org/html/draft-ietf-cdni-redirection-13

which decouples the control plane from the data plane and consolidates the control plane to a centralized entity

It is an opensource cloud computing platform.

It proposes an open CDN using NGINX web proxy server and other open source software: https://openconnect.netflix.com/software/

A first version of the software is available at: https://github.com/TelecomSudparis-RST/vIOS.

YouTube MyTop100Videos: https://www.youtube.com/user/MyTop10Videos

https://tools.ietf.org/pdf/draft-bagnulo-nfvrg-topology-00.pdf.

Cost unit is defined by the utilization percentage of the available resource.

Total virtualization cost is defined by the total utilization of the virtual resources (vCache, vStream, and Link utilization).

https://tools.ietf.org/pdf/draft-bagnulo-nfvrg-topology-00.pdf.

We still call this formulation OPAC.

NFVI PoP Network Topology (2016): https://tools.ietf.org/pdf/draft-bagnulo-nfvrg-topology-01.pdf

It is the software that implements the management function (migration, scaling in/out, etc.) of different VNFs already deployed in the network.

Cost factor may be defined by the utilization percentage of the available system or network resources. It is the amount of resources (in GBytes) consumed when orchestrating vCDNC to optimal locations.

G-H in the rest of the chapter

https://github.com/TelecomSudparis-RST/vIOS.

Watts-Strogatz small world models that target large network size and follows a binomial (or a Poisson) degree distribution.

 Chapter 7CDNaaS Framework: TOPSIS as multi-criteria decision making for vCDN migration

Introduction

According to multiplicities of criteria for migration, a vCDN migration process is complex. Further, there are some metrics needed to be maximized such as the QoE of the end-user and other factors and criteria that needed to be minimized as we proved in the previous chapters (i.e., in our vCDN placement, migration, and orchestration algorithms). What we propose here is to use a Multi-Criteria Decision Making (MCDM) method to assure a trade-off between all these metrics in an optimal way. Moreover, for optimal software resources utilization, vCDN migration needs an intelligent decision-making process for selecting the suitable point of operation where such vCDN components should be migrated. To do this, a multi-criteria decision analysis method (TOPSIS) is proposed in this context as a promising function that enables a flexible selection of the suitable area (core layer, distribution layer or access one) of instantiation of vCDN according to different criteria re-simple algorithm for dynamic construction of a G-H tree in response to network modifications such as vertex removal, vertex insertion, link cost increase, and link cost decrease. They claim that in the case of edge capacity change, the algorithm saves min-cut computations (there is no need to re-compute the min-cut of a specific sub-graph). Nevertheless, it is still not clear how the algorithm avoids the reconstruction of the G-H tree. Is a G-H needed for the remaining sub-graph ? if yes, what is the benefit of saving min-cut computation. Otherwise, how to compute the min-cuts of the remaining (s,t) nodes ? Further, from an algorithmic perspective, authors do not provide the algorithm complexity which is needed to assess the algorithm feasibility. Furthermore, we believe that the conditions defined for the re-usability of min-cuts in response to network modification can not help in a distribution network where any intermediate node is equipped by a budget regulator for assuring the balance between demands, services, performance, and budget.

In [START_REF] Aneja | Parametric min-cuts analysis in a network[END_REF], authors deal with the problem of all parametric min-cuts analysis in a communication network. Indeed, they consider the problem of finding the minimum cut of all the node pairs in a capacitated undirected network. They take into account the possibility of edge modification and propose an efficient algorithm for this parametric min-cut problem in a polynomial time. Exact formulation of the maximum flow problem is missing in their work. Moreover, the communication network is supposed to be a lossy network only where intermediate nodes (between the source and sink) can not enhance the throughout traffic.

In [START_REF] Hariharan | An Õ(mn) gomory-hu tree construction algorithm for unweighted graphs[END_REF], instead of using the traditional algorithms for construction the cut tree, authors use a Steiner edge connectivity through a tree packing algorithm. Authors present an alternative implementation of the G-H algorithm based on concatenation baseline to compute minimum Steiner-cut. Despite that, the algorithm capacity is reduced as much as possible and reaches O(m n), when edge capacities are equal to 1 which restricts the utilization of the algorithms in communication or distribution networks where network capacity is important and determine its performance. three main issues related to the ICN-based CANs:

• How to model the network infrastructure after (before it is already exist through exact/heuristic approaches) adding the ICN active nodes in a complex graph where Kirchhoff's law must be adjusted and other constraints should be updated.

• How to optimize the network dimensioning in presence of ICN nodes ?

• where to locate the streaming headend ?

• How to route the streams to the users ?

• Which budget should be placed on which nodes ?

• How to deal with dynamic operation: For instance, in case the client group membership changes, e.g., users join or leave ?, 1) upgrade the ICN node, 2) redirect the users to ICN node instead of requesting the source, 3) determine the ICN gain. The EGHT's algorithm complexity is 2 (N 1) minimum-cut computations (i.e., maximum flow computations). Hereafter, we describe our solution over an ICN scenario.

HPPA downgrading/enhancement on the fly

Firstly, HPPA requires an initialization step. In this step, a topology graph is built from the information about the network nodes (their physical locations) and the network links representing the relation ship between these nodes. Then streaming sources (e.g., ICN/IoT containers, hadoop data nodes, vCDN nodes, etc.) representing the producers and end-users representing the consumers are initially placed on this graph. Secondly, EGHT is executed. This step outputs two cut trees from the topology graph used for network analysis and then helps to determine the potential upgrade of ICN/CCN nodes. For each edge in EGHT, two maximum flows are computed Appendix A

Real cache overview

Real caching is the process that assures the caching service assisted with hardware H/W (CDNs equipment, video servers). We can enumerate three important sub-categories:

A.1 Intermediary caching

AKAMAI is a major company specialized in the provision of cache servers. Its server dissemination in the core network leads to serve quickly end users. In the literature, several algorithms exist to optimize the distance between the consumer and the content provider under the constraints of QoS. The question to answer was how to build a strong algorithm/architecture that intelligently places a lot of caches (centralized, decentralized or hybrid approaches). The relevant work is classified as follows:

1. Single cache: Shim et al. [START_REF] Shim | Proxy cache algorithms: design, implementation, and performance[END_REF] proposed a single cache algorithm using LNCRW3U (least Normalized Cost Replacement for the Web with Updates) as a management mechanism based on the local greedy algorithm (described below). This approach is inefficient because it does not consider the popularity of video. Algorithm Local greedy: Select a node I and an item n. If item n is currently not stored at node I, and it has higher utility than some item

A.2 Direct caching

In direct caching category, caches are hosted in the core network. We can enumerate under this category the following techniques:

1. Caching proxy (CP): Meeyoung et al. proposed in [START_REF] Cha | I tube, you tube, everybody tubes: Analyzing the world's largest user generated content video system[END_REF] a single and large cache with only popular videos so as to push them near the end user. This basic technique maximizes the QoE perceived by clients and enhances cache hit ratio to be close to 51%. However, the main limitation of this approach is that it maintains only popular videos requiring frequent cache updates.

2. Weighted-Rank Cache Replacement Policy: In [START_REF] Ponnusamy | Cache optimization on hotpoint proxy caching using weighted-rank cache replacemnt policy[END_REF], a caching algorithm based on weighted cost (WC) calculation of any object (video) is presented.

Objects with weak ranks are replaced from the cache. This technique assures better management of cache space and improves network bandwidth. However, it suffers from high delay required from WC calculation. [START_REF] Qadri | Effective video streaming using mesh p2p with mdc over manets[END_REF] presented a caching mechanism based on video segmentation assisted with Least Recently Used (LRU) algorithm. This technique reduces server load and overcomes churn problems related to user dynamism (join/leave) in P2P networks. However, this technique can not deal with high user demands.

Multiple Descriptions Coding (MDC): Authors in

4. Popularity Aware Limited Caching: Authors in [START_REF] Suresh | Popularity aware limited caching for reliable on demand p2p video streaming[END_REF] introduced PALC to enhance cache capacity. Their technique showed 95% of cache efficiency as it was explained in the work. However, maintaining only popular video presented the most important limitation to this approach. Moreover, video online streaming requires an efficient cache update algorithm which is missing in that proposed work. Table A.1 summarizes the important features of direct caching.

Virtual cache overview

The virtual caching is the process that assures the caching services and hardware independence. Precisely, we can enumerate three important sub-categories:

B.1 Content moving fetching

We will enumerate the few algorithms proposed for virtual caching techniques in video delivery content distributed networks:

1. Prediction Based caching (PBC): Bogdan et al. [START_REF] Carbunar | Predictive caching for video on demand cdns[END_REF] introduced a cache replacement algorithm that answers the question: which videos to evict from the cache? Authors describe then content moving algorithm based on decision making after a cache miss scenario. They describe an algorithm that works as follows:

• If (the requested video V is in the cache) then stream it.

• Else forward request to other site(V );

The decision was based on penalty in order to decide either keep a copy of the item and transfer the video or stream it and not cache. This technique enhanced CDN scalability but it still suffers from achieving high quality of service (including delay, bandwidth) due to the given penalty function which

C.1 OMAC: scenarios

In order to assess and quantify OMAC behavior, we proposed two scenarios: 1) strict replication, and 2) loose replication. The two approaches are defined as follows:

1. In strict replication, the total number of replica in the network is bounded and each vCDN node is replicated at most one time. The vCDN replication process obeys the following equation:

2. In loose replication, the total number of replica in the network is dynamic and the vCDN nodes are replicated freely.

Since we are focused on the total migration cost as the objective function, we

Introduction

In ICN protocol, data consumers send an Interest packet with a name or name prefix and retrieve, from the near LAN, a Data packet named under that prefix and it can be publicly verified.

To deploy this facility in network operators, optimization algorithms are necessary to select the appropriate placement of ICN functions. They supposed to take into consideration system, network and quality parameters. However, in complex active network where intermediate nodes not only intercept consumer interests and respond back but only treat the information and modify the original content (for example adding building plan in augmented reality use case, advertisement in video streaming scenario or even patient organs in medical treatment) each source of data (server) satisfies the request a group of consumers concurrently.

Streamed data are flowed from a single source to multiple destinations simultaneously. Target nodes correspond to consumer groups interested in source's data.

However each consumer group requests a specific quality of experience corresponding to a traffic class. It can be easily translated to a quality of service fol-203 lowing the exponential relationship as in IQX hypothesis.

The above problem is a pure QoS routing problem at origin that solves the following question:

How to route the quality of service from source s to all destinations ?

Currently, the maximum flow minimum cut theorem affirms that the maximum amount of data that can be shipped from a source to a destination is equal to the minimum cut capacity that separates the source from the destination. This theorem is important however it is not of practical interest in ICN network for two main reason: i) it is a centralized (sequential) approach which needs a global view of the topology beside the dynamic related parameters such as residual link bandwidth. ii) it is a point-to-point approach which does not fit with single source multi destinations scenario such as in this ICN use case. Giving these reasons, in this chapter we try to extend the above theorem (i.e., maximum flow minimum cut)

to design a distributed algorithm fitting with the ICN context. Further, the (multi) point to multi-point 1 communication model is adopted from the origin graph. We try therefore to propose efficient QoS routing algorithm that dynamically detects the bottleneck between the source and the set of destinations, place ICN functions to treat/process (amplify or downgrade) the streamed data in edge/optimal locations and stream the maximum quality (max-min fairness and throughput) to consumer groups.

In networking theory, minimizing the overall congestion is often referred to as maximum concurrent flow problem (MCFP). Several solutions are proposed to solve this problem in sequential or distributed manner. Each solution represents a computing model of the MCF problem:

1. Sequential approaches for solving this network problem are based on specific frameworks. Although each framework considers its specific algorithm and logic, the common idea is to route the concurrent demands from sources to destinations without violating the capacity constraint on each edge. Network 1 multi-source multi-destination is trivial step of single-source multi-destination

D.2 MCF state of the art

This section highlights the relevant Maximum Concurrent Flow (MCF) algorithms in data-centric context [START_REF] Pentikousis | Information-Centric Networking: Baseline Scenarios[END_REF].

Maximum concurrent flow problem is a generalization of sub-problems related to the multi-commodity network flow which make it harder when solving large scale deployment problem.

In 1930, Russian Railway System studies the maximum flow problem (MFP).

The objective was how to find the maximum amount of flow that can be pushed from a supply node (a source) to a demanding node (a sink or a destination).

Then, Fold Fulkerson gives the method of an augmenting path (called Ford Fulk- This metric is then used to encourage agents to reroute their traffic (flows) in the less congested paths (shortest paths in terms of congestion metric). As a summary, each agent i (responsible for the i th commodity) read the total flow on an edge, calculate the routing metric, and finally do the flow control and the re-routing of the traffic.

Previous DMCF work

Leighton et al. [START_REF] Leighton | An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms[END_REF] define the max-flow of a multi-commodity flow problem as the maximum throughput f such that f*d i units of commodity i is simultaneously routed for each i without violating the capacity constraint. Then,

where f is the maximum concurrent throughput, v is the complement of u, C is the capacity of the minimum sparsest cut, and D is the demand tagged on the corresponding cut.

Jonathan et al. [START_REF] Kelner | An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations[END_REF] propose an algorithm for calculating the "-approximated solution of a MCF problem in an almost linear time. The proposed approach is the MCF value. The execution model used is the hybrid model: authors synchronize the beginning of each round. Nevertheless, the execution of the instructions in each round (steps) is asynchronous.

D.5 MCF combinatorial optimization models

In combinatorial optimization (e.g., network flow, etc.), we quote exact and approximation algorithms. Most of the combinatorial optimization problems are Not Polynomial (NP) time (NP=? P). This means that those problems are hard to solve (in polynomial time) but easy to check the solution once it is given (yes/no answer).

Therefore, approximation algorithms are also used to solve such problems given Originally, the idea is derived from the node-triples formulation of Matula that gives a proof of the dual between Distance Elongation Problem (DEP) and the MCFP. The exact formulation (triples) is envisioned from the introduced "direct flow solution" (see heuristic model). In this formulation, authors present a linear programming (LP) system using an introduced variable indicating the total flow diverted off the edge fi, jg through the node k defined as x k i;j . It is introduced to satisfy the demand while keeping the edge capacity constraint not violated for all the edges which is not guaranteed in their heuristic relaxation procedure.

Formally, the total flow on an edge fi, jg equals to the initial direct flow plus [the amount of flow diverted onto fi, jg (through the nodes i or j)] minus [the amount of flow diverted off fi, jg (from the nodes i or j]. This amount of flow should not exceed the edge capacity C i;j . This introduces the triples formulation which is formulated as follows: max(Z) s.t.

Then, authors compare the LP sizes of the exact MCF formulations to show the efficiency of their triples formulation in terms of running time. Moreover, they propose a deriving procedure to move across formulations using basic mathematical models.

D.5.2 MCF approximation models

The approximation model is based on two main methods:

Maximum flow based approach

This approach is based on calculating the maximum flow and then saturating at least one edge for each commodity by sending the flow of this demand. Then,

given the flow concurrency behavior on the edge bandwidth, a rerouting process for deviating some flow from the loaded edge to the less congested ones is done in an intelligent way. This solution called also the re-routing procedure for MCFP.

Firstly, it is introduced by Shahroukhi et al. [START_REF] Shahrokhi | On solving large maximum concurrent flow problems[END_REF] by formulating an exponential

where jAj represents the cardinal of the edges, is a constant and f (e) is the total amount of flow circulating on an edge. Authors use this framework to reroute flow from highly congested (utilized) edges to less congested ones. The improvement of this framework is started by Klein et al. [START_REF] Klein | Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts[END_REF] and Leighton et al. [START_REF] Leighton | An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms[END_REF] who propose different edge length functions.

The main step of the maximum-flow based approach is as follows. First, an exponential length function is initiated as below:

Then, for each commodity defined by the triplet (s i ,t i ,d i ) the flow is sent from s i to t i along the path of minimum edges. Then, a comparison between max e f (e) and

is verified. If the first term is greater than the second term then we get the "-approximate value to the maximum concurrent flow. Otherwise, a shortest path for each commodity is calculated, and we choose the commodity with maximum l (longest path except the shortest path) where longest path is the path which larger hops between the source and the destination of the commodities.

Then, we re-route a small fraction of flow from the most congested (high l (e))

longest path to the shortest path. The termination condition of their algorithm is the satisfaction criteria in the comparison between the previous terms.

Following the same idea, Klein et al. [START_REF] Klein | Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts[END_REF] modified the length function to include maximum commodity flows aver all the edges jf j = max e f (e) . Later, Leighton et al. [START_REF] Leighton | An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms[END_REF], and Radzik et al. [START_REF] Radzik | Fast deterministic approximation for the multicommodity flow problem[END_REF] generalized the length function and consider an arbitrary capacity function (instead of uniform capacity in the work of Shahroukhi and Matula [START_REF] Shahrokhi | The maximum concurrent flow problem[END_REF] [157]).

To summarize the maximum flow based approach in calculating the maximum concurrent flow, we list below the main steps. First, we calculate the max-flow for each commodity. Then, we reroute independently, the max-flow value of each commodity. Finally, we re-route a small fraction of the flow from the loaded edge to the minimum-cost flow path.

Shortest path based approach

In this approach, new technique is introduced which is based mainly on finding a shortest path in terms of length function (less congested path) instead of hops.

In each iteration, the algorithm pushes a small amount of flow along the calculated shortest path. For more clarification, we push a unit of flow (for example) along the shortest path and then we update the flows.

Garg et al. [START_REF] Garg | Faster and simpler algorithms for multicommodity flow and other fractional packing problems[END_REF] solve the problem in a polynomial bound of phases. In each MCF phases, there is k iterations. For an iteration related to a commodity, authors push the minimum capacity (C min ) of the shortest path. Later, Madry et al. [START_REF] Madry | Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms[END_REF] improve this approach to execute Dijkstra for finding all pair shortest paths. The Matula et al. [START_REF] Dong | A compact linear programming formulation of the maximum concurrent flow problem[END_REF] inspired in their recent work a new solution for the MCF problem. The proposed heuristic is as follows:

1. Initially, the algorithm proposes to route z d i;j units of flow between all pairs fi, jg to find a feasible solution.

2. Then, it tries to satisfy (i.e., according to edge-path formulation) the equation that assure the data consumer demands satisfaction:

The proposed heuristic (direct flow solution) may not necessary satisfy the capacity constraint of edges defined as ( P p f p C i;j )

1. Then, at a throughput level (a fixed z value), we verify if z d i;j C i;j or not 2. If not, the heuristic selects a pair fi, jg that has too much flow (larger than the capacity).

3. Diverts an amount of flow from fi,jg to fi, kg.

4. Repeats the "divert procedure" until the edge capacity constraint is verified for all the network edges.

D.6 MCF applications

Among the main application in MCF, we quote the sparsest cut problem (SCP).

This problem finds the critical edges (bottleneck) in the distribution network.

Finding SCP is NP-hard problem. Therefore, for estimating the sparsest cut, we measure the sparsity ratio of the cuts. The cut with minimum sparsity ratio is the sparsest cut. in first superstep, only source vertex will update its value to zero and send update messages to its neighbors, iv) algorithm terminates when no more updates.

D.7.2 Finding the concurrent flow (maximum of gamma)

Once the shortest path tree (SPT) has been determined, the concurrent throughput pushed through SPT is set to be the minimum over all arcs of residual capacity to cumulative demands (of edges in SPT) given by the following equation: * = min a c a D a (i.e., the maximum concurrent throughput is smallest ratio which is equivalent to the concurrent throughput you can push along SPT to satisfy the cumulative demand without violating the capacity constraint).

D.7.3 Update the flows (augment/increment the flows)

Once we find the exact concurrent throughput, we update the flows by broadcasting the tree SPT and incrementing flows for every edge in the SPT in the classical way similar to the Ford-Fulkerson algorithm).

D.7.4 Update the residual graph

The residual graph is updated also in the classical way but in a distributed manner using the MapReduce facility (distributed computing of the residual capacity on each arc in the broad-casted SPT). The sub algorithm of building the residual graph is as follows:

1. If SPT contains edge (i,j) in R G : The requirements for this computing are:

• Connected graph G = (V ; E) where V is the set of vertices and E is the set of directed edges.

• weight u;v for edge fu; vg Large scale distributed computing is the predictable baseline process in our big data era. The Apache Hadoop [START_REF] Cutting | Apache hadoop[END_REF], a popular open-source framework for distributed storage and processing of large data sets has become the promising technology for processing multiple distributed applications such as traffic analysis, cache network update, network anomalies detection, data mining, machine learning, and bioinformatics research. The diversity of applications requires Hadoop to be more flexible, adaptive to different contexts while providing high performance, resulting in complicated networking protocol design, complex pieces of software that require non-trivial configuration and tuning for better performance [START_REF] Sifalakis | An information centric network for computing the distribution of computations[END_REF]. A candidate architecture, ICN [START_REF] Van Jacobson | Networking named content[END_REF] [184] shifts the networking focus from host-centric communication to multi-source content retrieval, a better fit to big data networking/computing that TCP/IP, the Internet communication protocol.

ICN can potentially provide enormous benefits in easing the deployment, improv-