Keywords: Content-Centric Networking, Caching, Markov chains, Cache allocation, Multi-objective optimization, GRASP

REMERCIEMENTS

Je tiens tout d'abord à remercier mes directeurs de thèse et mes encadrants Yassine HADJADJ AOUL, Gerardo RUBINO et Soraya AIT CHELLOUCHE, de m'avoir donné la chance d'effectuer cette thèse. Leur suivi et leurs conseils avisés m'ont apporté beaucoup d'aide et m'ont permis d'aboutir aux travaux présentés dans ce manuscrit.

Je veux également exprimer toute ma gratitude envers les membres du jury de soutenance. Je remercie Chadi BARAKAT et André-Luc BEYLOT d'avoir accepté d'être rapporteurs de cette thèse et de m'avoir fourni des conseils et des retours très intéressants sur mes travaux. Je remercie aussi Christine FRICKER pour l'intérêt qu'elle a bien voulu porter à mon travail en acceptant de prendre part à ce jury et pour ses remarques enrichissantes.

Merci aussi à tous les membres des équipes CAIRN et GRANIT pour les moments agréables qu'on a passé durant ces dernières années que ce soit au labo ou en dehors du cadre du travail comme par exemple pendant nos réunions de CST/CSID/CSI, à ne pas confondre avec le Comité de Suivi de Thèse, devenu Comité de Suivi Individuel du Doctorant et qui se nomme maintenant Comité de Suivi Individuel (Really ?). Leur bonne humeur et leurs blagues pas racistes (officiellement) m'ont permis de survivre aux BdP/BdR/BdL subis durant toute la thèse (seul les vrais savent !). En particulier, je remercie Cédric et Antoine que je considère comme mes encadrants de thèse (TMTC) pour leur soutien et leurs conseils qui ont permis d'enrichir mes travaux de recherche et merci aussi à Gabriel et Christophe de m'avoir soutenu tout le long de ma thèse, surtout durant les moments les plus critiques (BWAAAAAAAH !).

Pour finir, un grand merci à mon oncle Charif, à toute ma famille et surtout à mes parents Hamadi et Rafika qui m'ont soutenu tout au long de mes études et qui m'ont aidé à aller au bout de mes envies.

2.13

Cache hit ratio at different layers of the network using the LCE scheme.

2.14 Cache hit ratio at different layers of the network using the 2Q scheme. .

2.15

Cache hit ratio at different layers of the network using the LCD scheme.

RÉSUMÉ

Au cours des dernières années, les fournisseurs de contenu ont connu une forte augmentation des demandes de contenus vidéo et de services riches en média. Compte tenu des limites de la mise à l'échelle du réseau et au-delà des réseaux de diffusion de contenu, les fournisseurs de services Internet développent leurs propres systèmes de mise en cache pour améliorer la performance du réseau. En effet, la diffusion de caches dans l'infrastructure permet non seulement d'absorber la congestion du réseau, mais aussi de rapprocher les contenus aux utilisateurs, ce qui contribue à améliorer leur qualité d'expérience. Ces facteurs expliquent l'enthousiasme de l'industrie et des académiques à l'égard du concept de réseau centré sur le contenu (Content-Centric Network) et de sa fonction de mise en cache en réseau. La quantification analytique de la performance de la mise en cache n'est toutefois pas suffisamment explorée dans la littérature. De plus, la mise en place d'un système de caching efficace au sein d'une infrastructure réseau est très complexe et demeure une problématique ouverte.

Pour traiter ces questions, nous présentons d'abord dans cette thèse un modèle générique de noeuds de caching nommé MACS (Markov chain-based Approximation of Caching Systems) qui peut être adapté très facilement pour représenter différents schémas de mise en cache et qui peut être utilisé pour calculer différentes mesures de performance des réseaux multi-cache, y compris le cache hit moyen. Les essais effectués ont démontré la précision de notre modèle et plusieurs conclusions ont été tirées sur l'efficacité et les limites de la mise en cache. Nous avons ensuite abordé le problème de l'allocation des ressources de cache dans les réseaux avec capacité de caching. Moyennant notre outil analytique MACS, nous avons proposé une approche permettant de résoudre le compromis entre différentes mesures de performance en utilisant l'optimisation multi-objectif. Ensuite, une adaptation de la métaheuristic GRASP (Greedy Randomized Adaptive Search Procedure) pour résoudre le problème a été présentée et nous avons pu en savoir plus sur le placement optimal des ressources de cache distribuées.

Mots clés : Réseau centré sur le contenu, Mise en cache, Chaînes de Markov, Allocation de caches, Optimization multi-objectif, GRASP. CHAPTER 0 L'usage de l'Internet a radicalement changé depuis ses débuts. Conçu pour établir des communications point-à-point entre hôtes, l'usage qu'on en fait aujourd'hui, est de plus en plus centré sur l'accès à des contenus et services, indépendamment des hôtes qui les fournissent. Ce décalage entre le modèle conversationnel sur lequel il est conçu et l'usage qui en est fait, résulte en de nombreuses limites et contraintes, en termes de capacité, de performance et de fiabilité.

RÉSUMÉ ÉTENDU

Des solutions, sous forme de patchs, ont été proposées et déployées de manière incrémentale, afin de pallier à ces limites. Comme exemple de ces solutions, on peut citer les réseaux de diffusion de contenu (Content Delivery Networks ou CDNs) et les réseaux pair-à-pair déployés pour répondre aux problèmes liés au passage à l'échelle de la distribution des contenus. Cependant, ces solutions ne prennent souvent pas en considération les réseaux de transport sous-jacents.

Les réseaux centrés sur l'information (Information-Centric Networks ou ICNs) représentent une alternative à l'architecture actuelle de l'Internet. Ces réseaux ont été proposés pour répondre à plusieurs problématiques liées aux différentes tendances actuelles dans l'usage qui en est fait. Le réseau centré sur les contenus (Content Centric Network ou CCN), proposé par le Palo Alto Research Center, représente une des architectures ICN qui a suscité un vif intérêt de la part de la communauté de recherche. Basée, d'une part, sur le déploiement de caches au sein même du réseau (on parle de "in-network caching") et d'autre part, sur la séparation du nommage de la localisation, cette architecture permet de fournir, de par sa nature, un meilleur support pour la mobilité, le multicast, la gestion des ressource, la sécurité, etc. L'intégration des caches aux équipements réseau est une fonctionnalité inhérente aux réseaux centrés sur les contenus. En effet, ce paradigme consiste à placer des caches dans un plus grand nombre d'équipements réseau tels que des routeurs ou des boxes. Ces équipements sont certes plus nombreux et plus proches des utilisateurs, mais ils sont également plus limités en ressources, comparés aux caches utilisés dans les architectures plus traditionnelles telles que les CDNs. De nouvelles stratégies de gestion de caches prenant en compte ce nouveau contexte de déploiement sont donc nécessaires afin d'arriver à un compromis entre une meilleure disponibilité des contenus et une utilisation optimale des ressources réseau. Un utilisateur demande un contenu spécifique en diffusant son intérêt dans le réseau. Tout noeud qui reçoit l'intérêt et a les données sollicitées peut répondre avec un paquet de données et dans ce cas, l'intérêt sera consommé. Comme nous l'avons déjà mentionné, le nom du contenu dans CCN est le seul identificateur des données et les échanges d'informations qui reposent sur l'établissement de canaux de communication sont abandonnés. Les noms sont structurés hiérarchiquement comme le nom de chemin d'un système de fichiers (voir Figure 1). La structure arborescente permet d'agréger les contenus et donc de faciliter la découverte du contenu. Par exemple, comme le montre la Figure 1, tout le contenu fourni par "parc" peut partager le même préfixe "parc.com/". Un même objet de contenu dans CCN peut avoir plusieurs versions et il peut être divisé en plusieurs fragments appelés "chunks" (ou morceaux) afin d'ajuster la couche de transport. Pour simplifier la recherche et le transfert de contenu, le nom se termine généralement par la version et les informations sur les morceaux. Un exemple de traitement et de transfert de paquets dans un CCN est présenté dans la Figure 3. Une fois que le paquet d'intérêt est reçu du noeud A (qui demande l'objet x), le noeud C qui ne trouve pas de correspondance dans son cache ni dans la table des intérêts, transmet le paquet au noeud source D. Lorsque le noeud C reçoit le paquet de données de la part de D, il le renvoie au client attaché à A et il peut ensuite avec sa copie en cache servir la demande provenant du noeud B pour le même contenu x.

Content-Centric Networking

Contributions

Comme mentionné précédemment, la fonctionnalité de caching est l'une des caractéristiques les plus importantes de CCN. Elle joue un rôle majeur dans l'amélioration des performances du réseau. C'est pourquoi il est crucial d'utiliser efficacement les ressources de caches afin d'avoir un meilleur accès aux contenus. L'optimisation de la fonctionnalité de caching peut être traitée à différents niveaux :

-Algorithme de remplacement de cache : c'est l'algorithme responsable de la gestion du cache. The last few years witnessed a shift on the Internet usage that switched from a host-centric model to a content-centric approach, especially when dealing with content retrieval and data dissemination [1]. This evolution is mostly driven by the rapid growth of media-enriched services, e.g., Peer-to Peer file sharing, Video on Demand, video/audio streaming and social networks, which has significantly changed the way that people experience the Internet, making media traffic, and especially video traffic, one of the main drivers of the Internet Economy. According to the Cisco Visual Networking Index [2]- [3], the global IP traffic will reach 396 exabytes (EB) per month in 2022, up from 72 EB per month in 2015 (see Figure 4). Besides, video services and To deal with these new trends of the Internet usage and the important challenges that have raised with it [4], it is obvious that current IP-based infrastructures should evolve in a way to optimize the content delivery. Such data consumption context allowed CDNs (Content Delivery Networks) [START_REF] Hau | Multihoming, content delivery networks, and the market for Internet connectivity[END_REF] to be at the center of the content distribution value chain. Internet Service Providers (ISPs), for their part, are struggling to benefit from this traffic increase [START_REF] Karagiannis | Should Internet Service Providers Fear Peer-assisted Content Distribution?[END_REF]. On the contrary, this trend incurs large expenditures to meet the increasing demand and satisfy subscribers. Besides, given the adopted flat rate business models and even though that ISPs are payed by CDNs for hosting their data centers, the Average Revenues Per User (ARPU) is getting lower. ISPs are, thus, investigating the possibilities to extend their infrastructure with caching capabilities [START_REF] Tuncer | More control over network resources: An ISP caching perspective[END_REF] as a way to be part of this content distribution value chain (see Figure 5). The term cache [START_REF] Smith | Cache Memories[END_REF] was first employed in computing systems to describe a data storing technique that provides the ability to access data or files at a higher speed.

INTRODUCTION

Caches can be implemented both in hardware and software and they are used to serve as an intermediary component between the primary storage appliance and the recipient hardware or software device to reduce the latency in data access. The concept of caching was later adopted by the Internet [START_REF] Breslau | Web caching and Zipflike distributions: evidence and implications[END_REF]. By storing popular contents from previous requests, web caching solutions can help enhancing the content access time significantly. The rapid growth of Internet traffic has led to the emerging of Content Delivery Networks, that have become an important layer in the Internet ecosystem. CDNs are used to enhance the delivery of content by replicating commonly requested files across a globally distributed set of caching servers. The aim is to reduce the load on origin servers and to improve the experience of the clients by delivering a local copy of the content from a nearby cache edge.

More recently, there has been a growing emphasis on the Information-Centric Networking paradigm (ICN) [START_REF] Ahlgren | A survey of information-centric networking[END_REF]- [START_REF] Xylomenos | A survey of information-centric networking research[END_REF]- [4], which is emerging as one of the most interesting alternatives to the existing network architecture. The ICN paradigm consists in redesigning the future Internet architecture by focusing on named data instead of the end-to-end principle and the host-centric paradigm. One major feature considered in ICN to achieve service scalability and performance, is the in-network caching, where each node equipped with a content store module has the ability to cache the content that passes by it. The advent of ICNs represents, thus, a real opportunity for ISPs [START_REF] Jacobson | Networking Named Content[END_REF]. In fact, ICN networks enable focusing on the content itself and not on its location, which allows to overcome the limitations of the current Internet network. Thus, end-users' requests that are routed toward the Content Providers' servers (CPs), can be satisfied by intermediate caching nodes, which allows reducing the network traffic and the servers' loads while shortening the latency for end-users.

Motivations and contributions

When content caching is possible, a significant improvement can be achieved, as shown in several studies [START_REF] Rossini | A dive into the caching performance of Content Centric Networking[END_REF]- [START_REF] Paschos | The Role of Caching in Future Communication Systems and Networks[END_REF]. The analytical quantification of caching performance is, however, not sufficiently explored in the literature. In fact, several issues need to be addressed in order to understand the behavior of such a caching network. Indeed, in addition to the cache hit probability, other metrics deserve a deeper analysis, such as the average distance to reach a particular content, the content provider load or the impact of cache size and traffic pattern on performance.

INTRODUCTION

Moreover, setting up an optimal caching system within a network infrastructure, up to the edge of the latter at the Multi-access Edge Computing (MEC) level [START_REF] Taleb | On Multi-Access Edge Computing: A Survey of the Emerging 5G Network Edge Cloud Architecture and Orchestration[END_REF], is very complex and remains an open issue in the literature [START_REF] Reddy | Effects of storage heterogeneity in distributed cache systems[END_REF]. In fact, if we want to optimize the use of caches, we will tend to put everything in the same place at the exit of the network (at Point of Presence level), where users requests will be aggregated. This allows, indeed, to maximize the hit rate, but has the drawback of overloading the network. However, if one wants to maximize user satisfaction while at the same time reducing network load, the ideal would be to put everything on the edge. The problem here is that there will be more redundancy at the edge because of the multitude of access networks and the origin server will be more solicited. The performance of distributed caches is also strongly related to the popularity profile of content that generally follows a Zipf law [START_REF] Reddy | Effects of storage heterogeneity in distributed cache systems[END_REF] [START_REF] Mahanti | A tale of the tails: Power-laws in internet measurements[END_REF]. In such a distribution, the popularity of a content of rank r is proportional to 1/r α for some α. The larger the factor α, the smaller the number of very popular files, with therefore less caching needs. The smaller it is, the larger is the number of very popular files, with consequently a much greater caching requirement.

The contributions of this thesis work focus on these aforementioned issues related to caching optimization in multi-cache networks in general and more specifically in Content-Centric Networks and they can be summarized as follows. We start first by introducing an analytical model based on Markov chains named MACS (Markov chainbased Approximation of Caching Systems). This model allows us to estimate the hit probability of an LRU cache (Least Recently Used) operating under the default caching scheme where the contents are always saved when received. Then, an extension of MACS was presented by proposing a methodology that allows modeling the caching decision process independently from the strategy of caching that will be adopted. We have shown how the versatility of our cache modeling tool enables to mimic efficient caching strategies from the state-of-the-art and it can be easily adapted to represent an interconnection of caches under different schemes. We tackled after that the problem of cache resources allocation, which consists on studying how limited storage capacities should be distributed across the network's nodes in order to ensure an effective use of caches. The proposed approach solves the trade-off between minimizing the hit rate in the origin server and minimizing the distance between clients and the requested contents. To do so, the problem was modeled as a multi-objective integer nonlinear program and we proposed the use of the Greedy Randomized Adaptive Search Procedure (GRASP) due to the NP-hardness of the problem.

INTRODUCTION 3 Thesis outline

The rest of the thesis is organized as follows:

-In chapter one, we start first by giving an overview of the Information-Centric Networking paradigm to focus after that on Content-Centric Network, which represents a promising ICN solution for the future Internet. Then, we analyze the existing works related to the caching feature of ICNs and of multi-cache systems in general. More specifically, we discuss the issues related to cache modeling and cache resources allocation in multi-cache networks. -In chapter two, we present an analytical model named MACS capable of computing the hit ratio of an LRU cache [START_REF] Ben-Ammar | A Markov chain-based Approximation of CCN caching Systems[END_REF]. By proposing a methodology that allows modeling the caching decision process in the general case, we were able to extend MACS so that it can be used to analyze different caching algorithms [START_REF] Ben-Ammar | A versatile Markov chain model for the performance analysis of CCN caching systems[END_REF]. We aim with our proposal to gain more insights on the efficiency and limits of CCN caching strategies, with a focus on the schemes having a good performance/overhead trade-off through the analysis of different network performance metrics. We have shown how the versatility of our cache modeling tool enables to mimic existing efficient caching strategies and it can be easily adapted to represent an interconnection of caches under different schemes [START_REF] Ben-Ammar | On the performance analysis of distributed caching systems using a customizable Markov chain model[END_REF]. Even though our proposal was first used in the context of CCN networks, it can of course be applied to multi-cache networks in general. In addition to the cache hit, MACS can be used to compute different performance metrics like the content provider load and the distance reduction ratio. The conducted tests have shown the accuracy of our model in estimating the cache hit rate of a multi-cache system under different caching schemes and several conclusions were drawn on the efficiency and limits of caching that we hope it will help designing optimized caching strategies. -In chapter three, the optimal placement of caching resources is investigated. The cache allocation issue is one of the most important problems to address when studying multi-cache networks due to the expensive cost of deploying distributed storage resources along the network. In this context, we propose an approach that solves the trade-off between minimizing the hit rate in the origin server and minimizing the distance to retrieve contents. To do so, we modeled the cache allocation problem as a multi-objective integer nonlinear program where our an-INTRODUCTION alytic tool MACS is used to evaluate the objective functions. Our formulation of the problem turned out to be an NP-hard problem. Thus, we proposed an adaptation of the metaheuristic GRASP to solve the problem using different evaluation functions to generate the solutions [START_REF] Ben-Ammar | Efficiently allocating distributed caching resources in future smart networks[END_REF]. The conducted tests have showed the closeness of the metaheuristic's outcomes to the optimal ones. The aim of the work presented in this chapter is to give a tool capable of efficiently allocating distributed caching resources that takes into account more than one performance metric and versatile enough to adapt to specific desired network performance and constraints. -Finally, this dissertation closes by summarizing our thesis work and the different conclusions that were drawn and perspectives on future work are outlined for the overall thesis.

CHAPTER 1 BACKGROUND Contents

Introduction

The aim of this chapter is to give first an overview of the Information-Centric Networking paradigm. We will start by giving a brief description of ICN and some of its important features. Then, we will focus on the legacy and state-of-the-art proposals related to the caching feature of ICNs and of multi-cache systems in general, which is the core of this thesis work. More specifically, we will discuss the issues related to cache modeling and cache resources allocation in multi-cache networks.

1 Information-Centric Networking

Motivations

In the last years, accessing content has become the most important usage of the Internet. This evolution is mostly driven by the increased popularity of content-oriented services, e.g., Peer-to Peer file sharing, Video on Demand, video/audio streaming and social networks where users focus more on contents and not on the physical locations from which contents can be retrieved. Unlike its usage, the Internet was designed for host-to-host communications. To overcome this mismatch between usage and design, many projects have been carried on in order to propose a network infrastructure capable of providing services better suited to today's applications requirements. These studies led to a new paradigm named Information-Centric Networking [START_REF] Ahlgren | A survey of information-centric networking[END_REF]- [START_REF] Xylomenos | A survey of information-centric networking research[END_REF]- [4].

ICN description

ICN represents a promising new paradigm for the Internet of the future, where the communications are no longer depending on named hosts (host-to-host communications) but relies on named data (see Figure 1.1). Contrarily to IP network where users before accessing any data or starting any activity should tell the network which location they want to communicate with (IP addresses), end-users in ICN express only their interests for contents or information objects (IO) that are identified only by their names [4]. The network entities are in charge of routing the clients requests (based only on the content names) towards the machines that host an authorized copy of the demanded items. Once found, the requested contents will be delivered through the reverse paths ICN aims with this design to simplify the content delivery experience and to optimize the network performance by including natively into the networking design the following features:

-Multicast: it consists on aggregating in one ICN node the requests coming from different end-users who are demanding the same content. When the content is found, each requester will get a copy of it. -Multipath: in case where a content object is available in more than one location within the network, an ICN node can send a request for a specific data through multiple interfaces in order for example to find out the best container for the requested content. -Content security: ICN adopt a content-oriented security model. Unlike IP network where safeness is achieved via securing the communication channels, the contents in ICN are protected with the content provider's signatures and only the authorized users can verify their validity by resolving the signature. -In-network caching: in order to enhance the network resource usage and data availability, the ICN architecture exploits the possibility of the in-network caching.

The network nodes, equipped with a local cache store, can save contents or pieces of them that are flowing in the network and thus, the next requests of the cached data will be served more rapidly. In the last years, several projects have been put in work by several research teams with the objective to carry out an ICN concrete solution. Among the most important of those works results, we can quote:

-Publish Subscribe Internet Routing Paradigm or PSIRP [START_REF] Zahemszky | Experimentally-Driven Research in Publish/Subscribe Information-Centric Inter-Networking[END_REF].

-Network of Information or NetInf [START_REF] Dannewitz | Elsevier Network of Information (NetInf) -An information-centric networking architecture[END_REF].

-Data Oriented Networking Architecture or DONA [START_REF] Koponen | A Data-oriented (and Beyond) Network Architecture[END_REF].

-Content Centric Network or CCN [START_REF] Jacobson | Networking Named Content[END_REF].

ICN proposals 1.3.1 Publish Subscribe Internet Routing Paradigm

This approach is based on the publish/subscribe concept where hosts can publish data or Named Data Object (NDO) in the network and subscribe to any published data. Publishing content in the network does not imply a data transfer, this transfer only take place when a node subscribes to an NDO. The network, in this case, looks for the publication and establishes a delivery path from the publisher to the subscriber [START_REF] Zahemszky | Experimentally-Driven Research in Publish/Subscribe Information-Centric Inter-Networking[END_REF].

The PSIRP network architecture is basically composed of four modules (Figure 1.2): -The RendezVous module: which consists on a distributed database that maps the requested data to the subscriber. -The forwarding module: it handles the data delivery from one location to another based on the labels of the packets. -The topology module: it manages the forwarding traffic accomplished by the forwarding module by creating and maintaining delivery trees. -The Branching module: it provides a routing map for routing the subscriber requests toward the inter-domain or intra-domain content locations by using the topology maintained by the topology module. The PSIRP network is divided into Domains and each domain has one RendezVous Node (RN), one Topology Node (TN), one Branching Node (BN) and one or several Forwarding Nodes (FN). A subscriber can express its subscription of a content to the local RN of its domain to get the content container. Then, the BN uses the networking topology managed by the TN to forward the subscription to the content location. The FNs finally ensure the returning of the required content to the subscriber.

Network of Information

The Network of Information provides access to Named Data Objects (NDO) that are independent of the objects' locations in the network topology. To access and distribute data in NetInf, three pairs of messages are used:

-Search/Search-Resp: the requester uses the Search message to send a set of queries. A node receiving the Search message will respond to the requester using the Search-Resp message if it has the NDO demanded in its cache. Otherwise, it will forward the Search message. -Publish/Publish-Resp: the publisher can post an NDO with a Publish message using a Name Resolution Service (NRS). The node that receives the Publish message will either choose, depending in the local policy adopted and the availability of resources, to cache the data and returns a Publish-Resp message or to forward the Publish message to other nodes. -Get/Get-Resp: a requester, demanding an NDO from the network, will approach the NRS using the Get message, which will lead him to the information publisher.

A node would send a Get-Resp message to respond to the Get request.

Figure 1.3 shows an example of a routing scheme in NetInf. The name-based routing (NBR) (steps from A1 to A4) forwards a GET request between the NetInf nodes until a cached copy of the NDO or a server having the requested data is found. In case where the router does not have enough routing information to perform an NBR (step A2), it can perform a name resolution step (steps from A1.1 to A1.2) before forwarding the request (step A2) based on the retrieved routing hints. The object can be cached on the return path in intermediate nodes for subsequent demands. Alternatively, the initial client can query an NRS (steps from B1 to B4) via a GET message to resolve the object name into a set of routing hints. Subsequently, the routing hints are used to retrieve the object via the underlying transport network.

Data Oriented Networking Architecture

The DONA relies on a new class of network entities called Resolution Handlers (RHs). Name resolution is conducted through employing two basic functions:

-Register: Register packets are used by nodes that are approved to act as data sources to register their Named Data Objects (NDO) within the RHs. -Find: to locate and access to specific data (identified by NDO), clients use Find packets.

An example of the routing mechanisms in DONA is showed in Figure 1.4. Each RHs keeps up a registration table that contains three tuples:

-The content name "P : L", where P and L represent respectively the content provider and the content label chosen by its provider. -The next hop from where the node receives the content name advertisement. -The distance.

A client, seeking access to certain data, issues a Find packet to the local RHs. Once receiving the client request and depending on the information provided by the registration table, the Find packet will be routed hierarchically in order to find the demanded content that is closest to the user. When a copy of the requested data is found, it will be returned over the reverse RHs path.

Content-Centric Network

To request and retrieve data in CCN (Figure 1.5), two types of packets are used:

-Interest packet: it contains the content name requested by a client.

-Data packet: it is used to deliver data to its destination.

Clients can ask for specific data objects by sending Interest packets, which are forwarded towards data sources. Then, using the Data packets, data objects will be routed back to the clients on the reverse path and any node along this path can store a copy of the data to eventually answer to future requests for the same content.

Among these ICN solutions, we choose for our study the Content Centric Networking, which has quickly gained consensus in the scientific community and represents a promising architecture in ICN networks for the future Internet.

2 Content-Centric Networking

CCN naming and message exchange

Content-Centric Networking [START_REF] Jacobson | Networking Named Content[END_REF] was proposed in 2009 by Palo Alto Research Center (PARC). CCN proposes a complete content-based networking model (content naming, content-based routing, etc.) where a content is accessed by its name instead of the IP address of the host possessing it.

The communication and data retrieval in CCN [START_REF] Jacobson | Networking Named Content[END_REF] are managed using two types of packets (Figure 1.6):

-Interest packet: it is used to send the user's requests. It carries: � Nonce: it is a sequence of random number by which a router detects whether the interest is duplicated or not. -Data packet: it contains the following fields: � The content name. � Signature and signed info: according to the signed info, users can get the public key of the content publisher to verify the received data with the rule specified in the signature field and decide to accept the data or not.

� Data: which is the data that match the content name in the interest packet. A user asks for a specific content by broadcasting its interest in the network. Any node that receives the interest and has the solicited data can respond with a Data packet and in that case, the interest will be consumed.

As mentioned before, the content name in CCN is the only identifier of data and the information exchanges that are based on establishing communication channels is abandoned. Names are hierarchically structured like a path-name of a file system (see Figure 1.7). The tree-like structure enables the aggregations of contents and thereby facilitates the content discovery. For example, as shown in the Figure 1.7, all the content supplied by "parc" can share the same prefix "parc.com/". A same content object in CCN can have many versions, and it can be divided into multiple fragments called "chunks" in order to adjust the transport layer. To simplify content discovery and forwarding, the content name generally finishes with the version and the chunk information. -Content Store (CS): the CS is a buffer set that provides the in-network caching feature by caching the data that passes by in order to optimize the network performance (minimizing the latency, reducing network overload, etc.

CCN node model

The Interest/Data packets routing in CCN

In CCN networks, only Interest packets are routed and as they head upstream at potential data sources, they leave a track of "bread crumbs" so that Data packets can follow to get to the requester(s) [START_REF] Jacobson | Networking Named Content[END_REF]. The packet processing and forwarding in CCN nodes is performed as follows:

1. First, a CCN node receives an Interest packet where the content name carried by this packet is checked in the content store.

2. If there is a Data packet in the CS that matches the request, it is then sent back through the incoming face of the processed Interest. Otherwise, the content name is checked in the PIT.

3. If there is a matching entry in the PIT, then the Interest packet is discarded and his incoming face is added to the existing PIT entry (aggregation of Interest packets). If not, a new entry is created and the Interest is forwarded based on the information of the FIB table.

4. When the request content is found, the Data packet will track the traces left by the Interest packets in order to reach its requester(s).

5. Once a node receives a Data packet, its content name is checked in the CS.

6. If there is a match, the Data packet should be discarded since it already exists in the CS. Otherwise, the content name is looked up in the PIT.

7. If a matching entry in the PIT is found, then the Data packet is sent out through the faces where the Interest was received. The corresponding PIT entry is then deleted and based on the caching strategy, the node can keep a copy of the content in the CS.

An example of the packets processing and forwarding in CCN is shown in Figure 1.9. Once receiving the Interest Packet from node A (who requests the object x), the node C which doesn't find a match in its content store nor in the pending interest table, forwards the packet to the source node D. When the node C receives the Data packet from D, it forwards it back to the requester A and can thereafter with its cached copy serve the request coming from node B for the content x.

Discussion

As mentioned before, the on-path caching functionality is one of the most important features provided by CCN. It plays a major role on increasing the network performance. That is why it is crucial to use efficiently the cache resources in order to realize a suitable content retrieval. The caching optimization can be treated at different levels:

-Cache replacement algorithm: it is the algorithm responsible of managing the cache. When the cache is full, an item is chosen by the algorithm to be discarded. We can cite from the existing algorithms First In First Out (FIFO), Least Recently Used (LRU), etc. -Cache decision policy: it determines which content should be cached and at which node. In other words, a node should decide when receiving a content and depending on the applied strategy whether to cache or not the data. -Cache resources placement: since the cache capacity that can be allowed to a CCN node is limited, cache placement consists on studying the optimal distribution of storage resources between the network's nodes (e.g.: adopting a fair distribution, giving more storage spaces to edge routers, etc.).

The focus on this thesis was on problems related to cache modeling and cache resources allocation in CCN and multi-cache networks in general. A state-of-the-art pertaining to these subjects will be presented in the next two sections.

3 Cache modeling in multi-cache networks

Related work

Many studies have been conducted these last years to deal with the performance analysis of a single cache and a network of caches using mathematical modeling [START_REF] Kurose | Information-centric networking: The evolution from circuits to packets to content[END_REF] [27] [START_REF] Jin | Information-centric mobile caching network frameworks and caching optimization: a survey[END_REF]. We limit ourselves to the papers most relevant to our work.

Several works modeled and analyzed the behaviour of a caching system using Markov Process. The study in [START_REF] King | Analysis of Paging Algorithms[END_REF] was probably the first attempt to evaluate and model caching systems. The author proposed an exact model for predicting the buffer hit probability under the LRU and FIFO replacement policies using Markov chains. Flajolet and co-authors [START_REF] Flajolet | Birthday paradox, coupon collectors, caching algorithms and self-organizing search[END_REF] derived a simpler alternate expression of the cache hit rate to the one presented in [START_REF] King | Analysis of Paging Algorithms[END_REF] using a different approach. Unfortunately and in both cases, the computational complexity grows exponentially with the cache size N and the number of data items R. In [START_REF] Dan | An Approximate Analysis of the LRU and FIFO Buffer Replacement Schemes[END_REF], Dan and Towsley proposed an approximate analysis of the cache behaviour by exploiting the stack properties of an LRU cache using Markov chains. They derived an iterative algorithm with a complexity of O(N R) to predict the hit probability for a cache of size N using the hit rates of a cache of size N + 1 under the LRU replacement policy. The proposed solution is, however, limited to the case of a single cache and the tests were done only with very low values of cache size and catalog capacity. In [START_REF] Rosensweig | Approximate Models for General Cache Networks[END_REF], the authors extended the algorithm of [START_REF] Dan | An Approximate Analysis of the LRU and FIFO Buffer Replacement Schemes[END_REF] to the case of a network of caches. Psaras et al. proposed, in [START_REF] Psaras | Modelling and Evaluation of CCN-caching Trees[END_REF], a Markov chain-based model to estimate the proportion of time a given piece of content is cached in the case of a single router, which then has been extended to cover the case of multiple caching nodes. However, the assumptions and approximations made by the authors in their cache model can lead to high error rate in terms of hit ratio accuracy.

One of the most interesting proposals related to cache modeling was presented in [START_REF] Che | Hierarchical Web caching systems: modeling, design and experimental results[END_REF] by Che and co-authors. Using a different method compared to the previous mentioned works, Che et al. propose a simpler and more efficient approach to estimate the hit rate of an LRU cache. Their solution, known as the "Che approximation", allows identifying a characteristic time approximation for each item in the cache, which was used to estimate the cache hit rate per content. Their proposal has proved to be very accurate, with a low complexity (O(R)). Their work was further investigated in [START_REF] Fricker | A versatile and accurate approximation for LRU cache performance[END_REF], where the authors provided a mathematical explanation for the success of the Che approximation even in configurations that are more general than those presented in the original work. In [START_REF] Fofack | Performance evaluation of hierarchical TTL-based cache networks[END_REF], the authors extended the work of [START_REF] Che | Hierarchical Web caching systems: modeling, design and experimental results[END_REF] and proposed Time-To-Live (TTL) based caching model that assigns a timer to each content stored in the cache and redraws it every time the content is requested. Nevertheless, the aforementioned proposals are applicable only when the Leave Copy Everywhere caching strategy (LCE) is used, where every data packet is always stored once received by a caching node.

Other studies have been conducted in order analyze the modeling behavior and performance of caching systems where alternative caching strategies to the LCE are considered. By means of the "Che approximation", Laoutaris et al. presented in [START_REF] Laoutaris | The LCD interconnection of LRU caches and its analysis[END_REF] an analytical model of their caching algorithm called Leave Copy Down (LCD). Instead of storing the contents in all intermediate nodes like in LCE, LCD consists on caching an item only in the immediate downstream cache of the hit location. Their model was validated only in the case of two-cache LCD/LRU tandem with a small sized catalog of contents. In [START_REF] Garetto | A Unified Approach to the Performance Analysis of Caching Systems[END_REF], the authors extended the work of [START_REF] Che | Hierarchical Web caching systems: modeling, design and experimental results[END_REF] and proposed a unified framework to analyze the performance of caches (both isolated and interconnected). Their model covers various insertion and eviction policies (including LRU and LCE). They evaluated the accuracy of their proposal through simulation. However, in the case of interconnected caches, the tests were conducted only in the case of a 6-nodes chain with fixed network settings. Extending the work presented in [START_REF] Che | Hierarchical Web caching systems: modeling, design and experimental results[END_REF], the authors in [START_REF] Gast | TTL approximations of the cache replacement algorithms LRU(m) and h-LRU[END_REF] developed algorithms to approximate the hit probability of the cache replacement policy LRU-K [START_REF] O'neil | The LRU-K Page Replacement Algorithm for Database Disk Buffering[END_REF] [41] and variants of it. Nevertheless, their proposal is limited only to the case of a single cache.

If we look closely at the state of the art and the aforementioned works, we can see that most of the advanced proposals related to cache modeling are based on the work presented in [START_REF] Che | Hierarchical Web caching systems: modeling, design and experimental results[END_REF] by Che et al., which is referred to as the "Che approximation". A more in-depth analysis of this work will be presented in the next section.

Che approximation

In [START_REF] Che | Hierarchical Web caching systems: modeling, design and experimental results[END_REF], Che et al. proposed a modeling technique to analyze the caching performance by estimating the hit rate of a cache where the LRU replacement policy is used. Their work was investigated further in [START_REF] Fricker | A versatile and accurate approximation for LRU cache performance[END_REF], where a mathematical analysis for the remarkable accuracy of the approximation is given.

Consider a cache with a capacity size of N items operating under the LRU algorithm and let C = {c 1 , . . . , c R } be the set of catalog's contents available for users and that can be saved in the cache. Following the IRM model [START_REF] Fricker | A versatile and accurate approximation for LRU cache performance[END_REF], the probability p r to request an item c r from the set of available contents in the network is constant and follows a popularity law (e.g. Zipf law), where the contents are ranked decreasingly according to their popularity from one to R. Let's define τ r as the generic exponentially distributed inter-request interval for object c r . In other words, it represents a sequence of inde-pendent exponential random variables with respective rates (p r ). We define now the following random variables, for t ≥ 0,

X r (t) = R � i=1,i� =r 1 {τ i <t} , T C (r) = inf {t > 0 : X r (t) = N }. (1.1)
X r (t) and T C (r) are respectively the number of how much distinct items were requested up to time t (excluding content c r ) and the time at which exactly N different items, other than c r , have been requested. Therefore, a hit for content c r will occur in the cache if X r (τ r ) < N , which is equivalent to T C (r) > τ r . If we denote by h(r) the hit probability in the cache of an object c r , then we have

h(r) = P (T C (r) > τ r ) = 1 -e -prT C (r) .
(1.2)

Since at T C (r), we have exactly N objects in the cache, then

N = R � i=1,i� =r 1 {τ i <T C (r)} = R � i=1,i� =r 1 -e -prT C (r) . (1.3)
In [START_REF] Che | Hierarchical Web caching systems: modeling, design and experimental results[END_REF], the following two approximations were made:

1. T C (r) is a constant for each item c r (r ∈ {1, 2, . . . , R}).

2. T C (r) is a constant with respect to c r , which will be denoted T C .

The idea behind these two approximations as explained in [START_REF] Che | Hierarchical Web caching systems: modeling, design and experimental results[END_REF] is based on the following intuition: as the aggregated arrival rate of all the content requests grows and as long as the cache size is reasonably large, this rate becomes more and more deterministic and reaches a constant. These approximations are made not only for the tractability of the mathematical development, but also for the identification of T C as an important characteristic time of a given cache. The first approximation implies that the random variable T C (r) is now a constant that solves

N = R � i=1,i� =r (1 -e -prt ), (1.4)
and the hit rates are approximated by

h(r) = 1 -e -prT C (r) . (1.5)
The second approximation means that T C (r) = T C for r ∈ {1, 2, . . . , R}, where T C is the unique root of the equation

N = R � i=1 (1 -e -prt ). (1.6)
With these approximations techniques, the problem of modeling the hit performance of an LRU cache is now greatly simplified since the interaction between the caching process and a content c r and all the other operations is mediated by the "characteristic time" T C .

To sum up and following the Che approximation, the hit rate h(r) of an item c r (r ∈ {1, 2, . . . , R}) is equal to

h(r) = 1 -e -prT C , (1.7)
where

T C solves N = R � i=1
(1e -prt ).

(1.8)

Discussion

We presented and discussed in this section most of the important state-of-the-art proposals related to cache modeling. As we have seen, the work of Che et al. [START_REF] Che | Hierarchical Web caching systems: modeling, design and experimental results[END_REF] is one of the most interesting proposals when dealing with cache modeling and the majority of the works conducted after the publication of the "Che approximation" were built upon on it. Their approximation was first intended to deal with LRU caches operating under the LCE policy and extending it to other caching schemes is not straightforward. We will present later in chapter two our first contribution in this thesis, which consists on a Markov chain-based analytic tool capable of modeling the caching decision process in general in order to be used to model many caching schemes, without being limited to a specific algorithm.

Cache allocation in multi-cache networks 4.1 Related work

Many studies have investigated the problem of cache resources allocation and placement in the context of multi-cache networks [START_REF] Sahoo | A Survey on Replica Server Placement Algorithms for Content Delivery Networks[END_REF] (e.g., CDN, ICN, etc.).

The work presented in [START_REF] Krishnan | The Cache Location Problem[END_REF] by Krishnan et al. was one of the earliest studies that tackled the problem of the optimal cache resources placement. They examined the cache location problem in the case of transparent in-route caches in the context of web caching. The problem was modeled as a k-median problem, where the objective is to minimize the network traffic flow, and solutions were proposed based on dynamic programming and greedy heuristics. The classic k-median problem consists on finding k centers (i.e. cache resources) such that the clusters they form are the most compact (i.e. lower cost). The authors in [START_REF] Laoutaris | On the optimization of storage capacity allocation for content distribution[END_REF] and [START_REF] Laoutaris | Joint object placement and node dimensioning for Internet content distribution[END_REF] studied the storage capacity allocation in hierarchical content distribution systems through a multi-commodity problem, which generalizes the single commodity k-median problem. They propose a two-step algorithm capable of solving such problem when tree graphs are considered, which has been extended through approximations to cover the case of general graphs. They also provided a greedy algorithm due to the high complexity of the exact solution. The authors in [START_REF] Jamin | Constrained mirror placement on the Internet[END_REF] addressed the problem of placing mirrors of Internet content on a restricted set of hosts through modeling it as a slightly different version of the minimum k-center problem, considering the latency as the cost function to be optimized. In the minimum k-center problem, which is an NP-complete one, the objective is to find a placement of a given number of centers (i.e. content servers) such that the maximum distance from a node (i.e. end-user) to the nearest center is minimized. They proposed a greedy algorithm and a heuristic based on nodes degrees to solve the problematic.

Later on and with the proliferation of Content Delivery Networks, many works have focused on replica server (or cache resources) placement solutions in traditional and emerging CDN-based paradigms (cloud-based CDN, NFV-based CDN, etc.). In [START_REF] Yin | NetClust: A Framework for Scalable and Pareto-Optimal Media Server Placement[END_REF], the authors proposed a solution to the media server placement problem by modeling it using the uncapacitated facility location problem. To ensure the scalability of their algorithm, they have considered the case where all the end-users locations can be potential placement of replica servers. In [START_REF] Rodolakis | Replicated Server Placement with QoS Constraints[END_REF], Rodolakis et al. introduce polynomial and pseudo-polynomial algorithms to solve the replica server placement problem using the splittable soft capacitated facility location model. Their aim is to find the best location of replica servers and the number of servers that should be used and assigned to end-users groups in a way that minimizes the cost and satisfies the Quality of Service (QoS). In [START_REF] Chen | Intra-cloud lightning: Building CDNs in the cloud[END_REF], Chen et al. studied the problem of building distribution paths and placing Web server replicas in cloud CDNs to minimize the cost incurred on the CDN providers while satisfying QoS requirements for user requests. They provide an ILP formulaion of the problem that happened to be NP-hard, and propose offline and online heuristics to solve it. In [START_REF] Benkacem | Optimal VNFs Placement in CDN Slicing Over Multi-Cloud Environment[END_REF], the authors presented a CDNaaS platform (CDN as a Service) that enables the creation of CDN slices across multiple cloud domains and the deployment of virtual resources (including virtual caches) from multiple IaaS providers (Infrastructure as a Service), where different VNFs (Virtual Network Functions) are running. They studied in their work the optimal placement of these VNFs by modeling this problem as two distinct Linear Integer problems, where the aim is to minimize the incurred cost of resource placement and maximize the Quality of Experience (QoE) of the virtual streaming service. By means of the bargaining game theory, they propose a solution that ensures a fair trade-off between the cost and the QoE.

The study in [START_REF] Rossi | On sizing CCN content stores by exploiting topological information[END_REF] was probably the first attempt to investigate the cache allocation problem in CCN. They used in their study different metrics to measure the centrality of routers like degree, closeness and betweenness in order to decide where the cache should be distributed along the network's nodes. They suggest that deploying more cache resources at the core nodes of the network is better than at the edge. In later works [START_REF] Psaras | In-Network Cache Management and Resource Allocation for Information-Centric Networks[END_REF] [53], the authors have concluded the opposite, suggesting that placing larger caches at the edge is more effective. Wang et al., in their work [START_REF] Wang | Design and Evaluation of the Optimal Cache Allocation for Content-Centric Networking[END_REF], have studied the impact of content popularity distribution on caching performance in CCN. They show that placing caches into the network core is better suited for content requests with uniform distribution and that in case of highly skewed popularity demands patterns, pushing cache resources to the edge yields better performance.

Discussion

Considering a single metric or objective when dealing with the cache allocation problem clearly reduces the complexity of the problem, but has led many studies to find results that appear contradictory. There are many aspects in our proposal in this matter, which will be presented in chapter three, that makes it different from the existing works. We propose a versatile solution that takes into account at the same time more than one performance metric to solve the cache allocation problem and it can be tuned in order to seek some specific results. Moreover, the proposed tool builds a solution by measuring the contribution of all the nodes by the means of an analytic model capable of estimating the network performance, which will allow to take into account the impact of a node's performance on the others. In addition, more than one solution can be generated for the same use case, which gives more flexibility and enables adapting to additional constraints. We will see later that placing most (or all) of the cache resources at the edge or in the network core cannot be an absolute solution since it will depend on what performance metrics we try to optimize and what outcomes we aim to obtain.

Conclusion

We started this chapter by exposing a new paradigm in the computer network area called ICN. We focused after that on one of the ICN solutions, which is the Content-Centric Networking. We have given the necessary theoretical background to help understand the functioning of CCN and specifically its in-network caching feature and how it can improve the network performance. Then, we presented and discussed stateof-the-art proposals that dealt with cache modeling and cache allocation problem and what more could be done when studying these two issues. In the next two chapters, we will present our major contributions related to the different problems that we discussed earlier. CHAPTER

Introduction

The previous chapter presented the Information-Centric Networking paradigm with an emphasis on the in-network caching and the different issues related to this feature. In this chapter, we introduce an analytical model based on Markov chains named MACS (Markov chain-based Approximation of Caching Systems) [START_REF] Ben-Ammar | A Markov chain-based Approximation of CCN caching Systems[END_REF]. This model allows us to estimate the cache hit probability under the popular Least Recently Used replacement scheme for a system with multiple caching nodes, where the default caching strategy of CCN, called Leave Copy Everywhere (LCE), is used. Then, an extension of MACS [START_REF] Ben-Ammar | A versatile Markov chain model for the performance analysis of CCN caching systems[END_REF] is presented. We proposed a methodology that allows modeling the caching decision process in a more general way, so that it can be used to analyze different caching algorithms other than LCE. We will show how its versatility enables it to mimic efficient caching strategies [START_REF] Ben-Ammar | On the performance analysis of distributed caching systems using a customizable Markov chain model[END_REF] such as Leave Copy Down (LCD) [START_REF] Laoutaris | The LCD interconnection of LRU caches and its analysis[END_REF] and Two Queue (2Q) [START_REF] O'neil | The LRU-K Page Replacement Algorithm for Database Disk Buffering[END_REF]- [START_REF] Johnson | 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm[END_REF]. We aim with our model to gain more insights on the efficiency of CCN caching strategies, with a focus on the schemes having a good performance/overhead trade-off, by analyzing different network performance metrics like cache hit rate, content provider load and distance reduction ratio. It has to be noted that, even though our model MACS was first proposed in the context of CCN networks, it can also be applied to multi-cache networks in general (e.g., CDN, cloud based CDN, NFV based CDN, etc.).

Motivations

Due to the Internet usage evolution over these last years, the current IP-based architecture becomes heavier and less efficient for providing some Internet services. Beyond Content Delivery Networks, Network Operators (NOs) are developing caching capabilities within their own network infrastructure, in order to face the rise in data consumption and to avoid the potential congestion at peering links. Indeed, disseminating caches in the infrastructure not only helps in absorbing the network's congestion, but in addition, brings content closer to users, which allows a reduced latency. These factors explain the enthusiasm of industry and academics around the Content-Centric Networking concept and its in-network caching feature as a mean to improve network's performance and services scalability. Hit probability of content c r P miss (r)

Miss probability of content c r MS(r, u) Outgoing miss stream ratio from a node u for a content c r η r (v)

Incoming miss stream ratio at a node v for a content c r Dist(i)

Distance from where the clients requests were generated to the node v i

System description

Let's recall that in CCN, the content's name is the only identifier of data. To request and retrieve data, two types of packets are commonly used [START_REF] Jacobson | Networking Named Content[END_REF]: Interest Packet and Data Packet. Clients can ask for specific data objects by sending Interest packets, which are forwarded towards the data sources using the Forwarding Information Base. A record of the forwarded Interests is kept in the Pending Interest Table in order to keep track of the Interests waiting for a data packet. When a node receives multiple requests for the same content, the Interest packets will be aggregated in one entry in the PIT and only the first one is routed. Once the requested content is found, it is automatically routed back to the clients on the reverse path. All the nodes along this path can store a copy of data to answer future demands.

Let G = (V, E) be the graph representing a general network of caches, where V = {v 1 , . . . , v M } depicts the nodes of the network and E ⊂ V × V is the set of links connecting the nodes. Each node in the network is equipped with a caching module used to store contents locally. Let C = {c 1 , . . . , c R } be the set of the catalog's contents available for the users. We assume that all the accessible contents in the system have an identical size and are divided into small packets or chunks, which are in turn of the same size. The cache capacity is then expressed in terms of the number of contents or chunks that can be stored. All the available contents are stored permanently at one or more servers attached to some nodes within the network. In the rest of the paper and for the sake of readability, we will use the term node/cache interchangeably as well as the terms rank/popularity and content/item/object. Clients, which are attached to the network nodes, send requests into the network looking for contents. The pattern of these requests is characterized by the Independent Reference Model (IRM) [START_REF] Dan | An Approximate Analysis of the LRU and FIFO Buffer Replacement Schemes[END_REF]. Suiting the IRM model, users generate an independent and identically distributed sequence of requests from the catalog C of R objects. Specifically, the probability p r to request an item c r from the set of available contents in the network is constant and follows a popularity law, where the contents are ranked decreasingly according to their popularity from 1 to R. Since about 80% of Internet traffic is generated by video related applications [2], we address in our work videos services, where the contents feature a skewed popularity distribution. As already argued in many previous studies [START_REF] Fricker | Impact of traffic mix on caching performance in a content-centric network[END_REF], the latter fits the Zipf law: the probability to request the content of rank r is:

p r = r -α / � R i=1 i -α
, where α, the skew of the distribution, depends on the type of the accessible objects [START_REF] Fricker | A versatile and accurate approximation for LRU cache performance[END_REF]. For our approach, we only need to assume that

0 < p r < 1, with R ≥ 2.
We use here the LRU algorithm to manage the node's content store. Other memory management algorithms have been studied in the case of cache modeling like First In First Out (FIFO) and Random Replacement (RR). However, LRU is known to perform much better than FIFO [START_REF] Chrobak | LRU is Better than FIFO[END_REF] and the expected long-run performances of both RR and FIFO replacement policies were shown to be the same [START_REF] Gelenbe | A Unified Approach to the Evaluation of a Class of Replacement Algorithms[END_REF]. The Least Frequently Used (LFU) algorithm, which requires a more complex replacement process, is also interesting. However, it presents several shortcomings related to the insertion of new popular contents or the purge of older ones [START_REF] Podlipnig | A Survey of Web Cache Replacement Strategies[END_REF]. Moreover, the complexity of the LFU functioning makes it harder to be modeled and analyzed.

A single LRU cache model under LCE 3.1 A comprehensive analysis of LRU caches

Let's consider a single node in a Content-Centric Network operating under the LRU replacement policy and having clients attached to it. Whenever a user requests a con-tent of rank r in the catalog, it will generate either a cache miss if the content is not present in the cache or a hit otherwise. In the latter case, the object will be sent back to the user. In the case of a cache miss, the client's interest is forwarded to the next nodes in the direction of the nearest content server storing a permanent copy (i.e. origin server). Once the object located, it is sent on the reverse path and depending on the caching strategy used in the network, the content will be cached or not at each node that passes by it. In CCN, a node uses a caching scheme in order to decide whether an incoming item should be saved or not. In the case where the default caching strategy LCE is used [START_REF] Laoutaris | The LCD interconnection of LRU caches and its analysis[END_REF], the contents will always be cached at each node that pass by it.

Consider a cache sized to contain N ≤ R items (the usual case is, of course, N � R). The position occupied by a content in a cache goes from 1 to N , where block 1 represents the top up position and N is the bottom down one (last block before the eviction from the cache). Whenever a local cache hit or a caching decision occurs for a content c r , it will then be placed at the top position in the cache. Consequently, for any given content c r � occupying position i in the cache, with r � � = r, three actions are possible when a request for c r is received:

c � r � will be moved down if the requested content c r is either not present in the cache or if it occupies block j with j > i; c � r � will remain at the same position if c r occupies a block j with j < i; c � r � will be evicted from the cache if it occupies the N th and last position. When analyzing the performance of a caching system, we usually focus on hits or misses, which means that we consider the system only when requests for content arrive. This means that in case of a miss, we don't look at the time needed to get a copy of that content in the cache; we only consider which contents are in which positions at arrival times.

Let us call a configuration of the cache any vector � x = (x 1 , . . . , x N ) where x i is the content present at block or position i. We only consider the case where all positions are occupied because the cases where the cache is partially filled concern only the initial transient phase. Let us denote by S the set of all possible configurations; we have |S| = R!/(R -N )!. For realistic values of N and R, |S| is huge. If we consider the evolution of the cache's configuration "just after" the arrival of a request, we define a discrete time homogeneous Markov chain X = (X n ), where X n is the configuration just after the arrival of the n th request at the node. Chain X is clearly irreducible: from any configuration (x 1 , . . . , x N ), we can move to any other configuration (y 1 , . . . , y N ) after the arrival of a request for content y N , then for content y N -1 , etc. (this event has probability

p y 1 • • • p y N > 0).
Of course, we consider the case here of always deciding to store the arriving content. It is also aperiodic because if X n = (x 1 , . . . , x N ), then, with probability p x 1 next state is still (x 1 , . . . , x N ). So, X is ergodic.

Knowing the steady-state distribution of X,

� π � x � � x∈S
, allows (in theory) to evaluate important performance metrics of a caching system such as the hit probability per content. Assuming the system is in equilibrium, we have that for any c r ∈ C,

Pr(hit for a request of c r ) = � � x s.t. ∃i∈{1,...,N }|x i =cr π � x .
(2.1)

For illustration purposes, let us consider the case of R = 3 and N = 2, when the content is always cached when received (see Figure 2.1). The state space is

S = {(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)}.
The stationary distribution π � x satisfies the equations

       π (i,j) = p i (π (i,j) + π (j,i) + π (j,k) ), k � ∈ {i, j}, � (i,j) ∈ S π (i,j) = 1. (2.2)
Solving the equations (2.2), we have that for a generic configuration (i, j) ∈ S,

π (i,j) = p i p j (1 -p i ) -1 .
If we want to compute for example the hit probability of content c 1 , we obtain

Pr(hit for a request of c 1 ) = π (1,2) + π (1,3) + π (2,1) + π (3,1) = p 1 (1 -p 2 p 3 ) (1 -p 2 )(1 -p 3 )
.

We can see through this example how the steady-state distribution of the Markov chain representing the dynamics of an LRU cache can be used to evaluate important performance metrics of the caching system. By investigating further the exact Markov chain-based model of on LRU cache, we have found that in the general case (i.e.

2 ≤ N < R), π � x = N � i=1 � p i (1 - i-1 � j=1 p j ) -1 � , � x = (x 1 , . . . , x N ).
(

2.3)

To compute the cache hit probability of any content c r , we use the formula (2.1), which as we can see is very costly, as it requires a summation over the permutations of all the subsets of size N containing the content index r of the set {1, . . . , R}.

As we can see, the problem with the exact analysis of an LRU cache's hit rate is the huge size of the state space S and the complexity of the model. In the next section, we describe an efficient way of obtaining an approximation for such a metric (i.e. cache hit or miss) that is shown to be very accurate by comparing its output to the results of simulations.

Markov chain-based approximation of an LRU cache

To reduce the complexity of modeling an LRU cache using Markov chains, the process is modeled by considering only one content at a time. Let us consider a Markov chain

X(r) = � X h (r) � h≥0
with N + 1 states, as depicted in Figure 2.2. This chain will represent the evolution in time of the position occupied by content c r in the cache, where state N + 1 means that content c r is absent, state 1 means that the object is at the top of the cache and state N where it is at the bottom. Using this approximation, the size of the state space will then be S = (N + 1) × R. The probability of a content staying at the same position upon the reception of an item is represented by γ s (r).

Assume we know γ i (r), i = 1, 2, . . . , N, N + 1, satisfying 0 < γ i (r) < 1. This means that X(r) is irreducible and aperiodic. Let us denote by π(r) = (π 1 (r), π 2 (r), . . . , π N +1 (r)) its equilibrium distribution. Assume now that π(r) is exactly the marginal distribution corresponding to content c r and that the chains X(1), . . . , X(R) are independent of each other. The probability that a content of rank r remains in the state s of the chain, with (s ∈ {1, 2, . . . , N + 1}), upon the arrival of a request is equal to

1 -p r -γ 2 (r) 1 -p r -γ s-1 (r) 1 -γ 1 (r) 1 -p r -γ N-1 (r) 1 -p r -γ s (r) . . . . . . . . . . 1 2 S N γ 1 (r) γ 2 (r) γ N (r) γ s (r) N+1 γ N+1 (r) p r p r p r p r 1 -p r -γ N (r)
                 γ 1 (r) = p r , γ s (r) = R � i=1,i� =r p i ( s-1 � j=1 π j (i)), 2 ≤ s ≤ N, γ N +1 (r) = 1 -p r . (2.4)
Let's denote by T i,j the transition probability from state i to state j. Then, T i,j is equal to

                         T i,i = γ i (r), 1 ≤ i ≤ N + 1, T i,1 = p r , 2 ≤ i ≤ N + 1, T 1,2 = 1 -γ 1 (r), T i,i+1 = 1 -p r -γ i (r), 2 ≤ i ≤ N, T i,j = 0, j � = {1, i, i + 1}.
(2.5)

The distribution π(r) satisfies the Chapman-Kolmogorov equations:

             π i (r) = N +1 � j=1 π j (r)T j,i , 1 ≤ i ≤ N + 1, N +1 � i=1 π i (r) = 1.
(2.6)

If we develop the system of equations defined in (2.5) and (2.6), we obtain:

                                             π 1 (r) = γ 1 (r)π 1 (r) + p r (π 2 (r) + . . . + π N +1 (r)), π 2 (r) = γ 2 (r)π 2 (r) + (1 -γ 1 (r))π 1 (r), π 3 (r) = γ 3 (r)π 3 (r) + (1 -p r -γ 2 (r))π 2 (
π N (r) = γ N (r)π N (r) + (1 -p r -γ N -1 (r))π N -1 (r), π N +1 = γ N +1 (r)π N +1 + (1 -p r -γ N (r))π N (r), π 1 (r) + π 2 (r) + . . . + π N +1 (r) = 1.
(2.7)

The equations derived in (2.7) can be easily solved using (2.4) to finally get:

                           π 1 (r) = p r , π 2 (r) = p r (1 -p r ) 1 -γ 2 (r) , π i (r) = p r (1 -p r ) � i-1 j=2 (1 -p r -γ j (r)) � i j=2 (1 -γ j (r)) , 3 ≤ i ≤ N + 1, π 1 (r) + π 2 (r) + . . . + π N +1 (r) = 1.
(2.8)

The closed-form expression π N +1 (r) represents the cache miss probability for a content c r in a single cache. Its computational complexity is O(N ) where N represents the cache capacity (we suppose that the complexity of calculating each π i (r) is a constant).

To get the cache hit rate of a content c r , we simply do

P hit (r) = N � i=1 π i (r) = 1 -π N +1 (r).

A general Markov chain model of a single LRU cache 4.1 A comprehensive analysis of generic LRU caches

Let's recall that in CCN, a node uses a caching scheme in order to decide whether an incoming item should be saved or not. In the general case, this decision can be seen as the probability that we denote β(r), with which a received content c r will be stored in a cache. The value of β(r) will then depend on the caching strategy adopted by the node. When using the LCE policy, for example, all arriving objects are cached that is, β(r) = 1 for any content c r . We will see later in more details the values taken by β(r) when a specific caching strategy is used.

As we did in the previous section, let's consider a cache sized to contain N ≤ R items. Now, in the general case and whenever a local cache hit or a caching decision occurs for a content c r , it will then be placed at the top position in the cache with probability β(r). Consequently, for any given content c r � occupying position i in the cache, with r � � = r, three actions are possible when a request for c r is received:

c r � will be moved down by one position if the requested content c r is either outside the cache and it has been decided to cache it (with probability β(r)) or it occupies the block j with j > i; c r � will remain at the same position if c r occupies the block j, with j < i, or if it is outside the cache and it has been decided to not cache it (with probability 1β(r)); c r � will be evicted from the cache if it occupies the N th position (last block) and it has been decided to cache c r (with probability β(r)), which is outside the cache.

A generic model of a single LRU cache

Like the case of an LRU cache under the LCE scheme (i.e. β(r) = 1), we modeled this process using Markov chain 2.3). The major differences are the transition from state N + 1 to 1, which now includes the caching probability β(r), and the probability of a content staying at the same state s (that we denote by γ � s (r)). Assume we know γ � i (r), i = 1, 2, . . . , N, N + 1, satisfying 0 < γ � i (r) < 1. This means that X(r) is irreducible and aperiodic. Let us denote by π(r) = (π 1 (r), π 2 (r), . . . , π N +1 (r)) its equilibrium distribution. Assume now that π(r) is exactly the marginal distribution corresponding to content c r and that the chains X(1), . . . , X(R) are independent of each other. The probability that a content of rank r remains in state s of the chain upon the arrival of a request, with s ∈ {1, 2, . . . , N + 1}, is equal to

X(r) = � X h (r) � h≥0 (Figure
         γ � s (r) = γ s (r) + R � i=1,i� =r (1 -β(i))p i P miss (i), 1 ≤ s ≤ N, γ � N +1 (r) = 1 -p r β(r).
(2.9)

The value of P miss (i) used in (2.9) represents the cache miss probability of content c i (its calculation will be detailed later) and the value of γ s (r) is a special case of γ � s (r) where β(i) = 1. The first term of the expression of γ � s (r) (i.e. γ s (r)) represents the case where a content c r remains at the same position i when the received item occupies a position j, with j < i. The second term of γ � s (r) (i.e.

� R i=1,i� =r (1β(i))p i P miss (i)) corresponds to the event where the received content is not in the cache and it has been decided to discard it. Again, observe that (2.9) is an approximation, but as we will see, its form makes that it leads to a very accurate approximation algorithm. Let's denote by T i,j the transition probability from state i to j in our model. Then, T i,j is defined as follows:

                               T i,i = γ � i (r), 1 ≤ i ≤ N + 1, T i,1 = p r , 2 ≤ i ≤ N, T N +1,1 = p r × β(r), T 1,2 = 1 -γ � 1 (r), T i,i+1 = 1 -p r -γ � i (r), 2 ≤ i ≤ N, T i,j = 0, j � ∈ {1, i, i + 1}.
(2.10)

The distribution π(r) satisfies the Chapman-Kolmogorov equations:

             π i (r) = N +1 � j=1 π j (r)T j,i , 1 ≤ i ≤ N + 1, N +1 � i=1 π i (r) = 1.
(2.11)

If we develop the system of equations defined in (2.10) and (2.11), we obtain

                                           π 1 (r) = γ � 1 (r)π 1 (r) + p r N � i=2 π i (r) + p r β(r)π N +1 (r), π 2 (r) = γ � 2 (r)π 2 (r) + (1 -γ � 1 (r))π 1 (r), π 3 (r) = γ � 3 (r)π 3 (r) + (1 -p r -γ � 2 (r))π 2 (r), • • • • • • = • • • • • • π N (r) = γ � N (r)π N (r) + (1 -p r -γ � N -1 (r))π N -1 (r), π N +1 (r) = γ � N +1 (r)π N +1 (r) + (1 -p r -γ � N (r))π N (r), π 1 (r) + π 2 (r) + . . . + π N +1 (r) = 1.
(2.12) By computing π N +1 (r), which represents the cache miss probability, we can obtain the cache hit rate 1π N +1 (r). We can see from (2.12) that each π i (r) depends on π i-1 (r) (2 ≤ i ≤ N + 1), and once we get π 1 (r), we can calculate π N +1 (r) and deduce the cache hit. When β(r) = 1, we have π 1 (r) = p r . The equations then derived in (2.12) can be easily solved using (2.4) to finally get

                           π 1 (r) = p r , π 2 (r) = p r (1 -p r ) 1 -γ 2 (r) , π i (r) = p r (1 -p r ) � i-1 j=2 (1 -p r -γ j (r)) � i j=2 (1 -γ j (r)) , 3 ≤ i ≤ N + 1, π 1 (r) + π 2 (r) + . . . + π N +1 (r) = 1.
(2.13)

In the general case (0 ≤ β(r) ≤ 1), π 1 (r) cannot be computed directly, and it depends on all the other values of π i (r) (for 2 ≤ i ≤ N + 1). One way to resolve this problem is to modify the expression of π 1 (r) in order to reduce its dependency on the other variables. To do so, we first add and subtract in the initial expression of π 1 (r) in (2.12) the values p r π 1 (r) and p r π N +1 (r). Then, using the expression of γ � 1 (r) and since

� N +1
i=1 π i (r) = 1 and γ 1 (r) = p r , we get a new expression of π 1 (r) as follows:

π 1 (r) = γ � 1 (r)π 1 (r) + p r N � i=2 π i (r) + p r β(r)π N +1 (r), = γ � 1 (r)π 1 (r) + p r N � i=2 π i (r) + p r β(r)π N +1 (r) + p r (π N +1 (r) -π N +1 (r) + π 1 (r) -π 1 (r)), = p r ( N +1 � i=1 π i (r)) + (γ � 1 (r) -γ 1 (r))π 1 (r) + p r β(r)π N +1 (r) -p r π N +1 (r), = p r + (γ � 1 (r) -γ 1 (r))π 1 (r) + p r (β(r) -1)π N +1 (r).
(2.14) The expression of π 1 (r) can be rewritten as

π 1 (r) = p r (1 + (β(r) -1)π N +1 (r)) 1 -(γ � 1 (r) -γ 1 (r))
.

(2.15)

Now, π 1 (r) depends only on π N +1 (r). The idea then is to use a fixed-point iteration in order to generate successive approximations of the solution, which consists on finding π N +1 (r), by starting from an initial guess. To do so, we start by considering an approximate value of π N +1 (r) (that we denote by π � N +1 (r)) by using the one obtained when β(r) = 1, to compute π 1 (r). Once we have π 1 (r), we can calculate π i (r) (2 ≤ i ≤ N + 1) to finally obtain a new value of π N +1 (r).

                               π 1 (r) = p r (1 + (β(r) -1)π � N +1 (r)) 1 -(γ � 1 (r) -γ 1 (r)) , π 2 (r) = γ � 2 (r)π 2 (r) + (1 -γ � 1 (r))π 1 (r), π i (r) = (1 -p r -γ � i-1 (r))π i-1 (r) 1 -γ � i (r) , 3 ≤ i ≤ N + 1, N +1 � i=1 π i (r) = 1.
(2.16)

The value of π � N +1 (r) is also used to calculate γ � s (r) (s ∈ 1, . . . , N ) by replacing P miss (r) with π � N +1 (r). These steps are repeated until we converge to the final solution by replacing in each step π � N +1 (r) by the new computed value π N +1 (r) (see Algorithm 1). As for the computational complexity of our model, let's recall first that the state space contains N + 1 elements. The complexity of computing the cache hit of one content c r is then O(N ) (we suppose here that the complexity of calculating each π i (r), 1 ≤ i ≤ N + 1, Algorithm 1 Cache hit rate of a content with popularity r and caching decision β(r)

1: function GET_CACHE_HIT(r, β(r)) 2:
π � N +1 (r) ← Get_cache_miss(r, 1) //Starting point of the iterative procedure (β(r) = 1)

3:

π N +1 (r) ← Get_cache_miss(r, β(r))

4:

� : Arbitrarily small positive quantity 5:

while |π N +1 (r) -π � N +1 (r)| ≥ � do 6: π � N +1 (r) ← π N +1 (r) 7:
π N +1 (r) ← Get_cache_miss(r, β(r))

8:

end while 9:

return 1π N +1 (r) 10: end function is a constant). To compute the total cache hit, we have to apply MACS to each content of the catalog. Since we have R available items in the catalog, then the complexity of computing the average hit of a single cache is O(N R). Now, in case where we have a multi-cache system containing M nodes and if we want to compute the average hit ratio of all the caches, we obtain a complexity of O(N RM ).

Single cache model for 2Q

In [START_REF] O'neil | The LRU-K Page Replacement Algorithm for Database Disk Buffering[END_REF], the authors proposed LRU-K, a page replacement algorithm for database disk buffering. The proposal is an enhancement of the classical LRU replacement policy in the sense that a history of requests is maintained for the elements of the cache. Indeed, LRU-K keeps track of the timing of the K last occurrences, which allows having a better idea of the contents' popularity. Thus, the element whose K th most recent access was furthest in the past will be evicted when the cache is full. When K is equal to one (LRU-1), the approach is equivalent to the classical LRU. Note that, most of the LRU-K method gain is achieved when K = 2 (LRU-2) [START_REF] O'neil | The LRU-K Page Replacement Algorithm for Database Disk Buffering[END_REF]. However, LRU-2 suffers from a high complexity, as each element access requires log(N ) operations to manipulate a priority queue (N being the cache size).

Johnson et al. proposed the Two Queue scheme (2Q) [START_REF] Johnson | 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm[END_REF], which is similar and performs as well as LRU-2 algorithm, but having a constant time overhead. Instead of cleaning cold elements from the main buffer like LRU-2, 2Q admits only the hot ones to the cache. When a request is received by a cache using 2Q, the requested object's hash is first placed in a virtual cache (called A1), which is managed as a FIFO. If an item is requested during its A1 residency, it is then promoted to the main cache (called Am). The authors, then, proposed another version of 2Q in which the A1 queue is partitioned into A1in and A1out. The A1in queue along with Am form the physical cache and A1out is a virtual cache, which will contain only items hashes. The most recent first accesses will be stored in A1in, which will be managed as a FIFO queue. When objects are evicted from A1in, they will be remembered in A1out. Upon arrival of a request and if it is present in the A1out queue, then it is cached in Am. The item to be discarded in 2Q is chosen either from A1in or Am. However, the sizes of the different queues (A1in, A1out and Am) are sensitive to the requests patterns and should be tuned carefully.

In our work, we considered a caching scheme similar to the first version of 2Q where the virtual buffer and the main cache are both managed using LRU. If we apply the model MACS presented previously to the 2Q scheme, β(r) will then be equal to the hit probability in the virtual cache of the received content c r . Since the virtual cache is managed as a classic LRU (i.e. each received item is always cached), β(r) of a node v is obtained using equations (2.13):

β(r, v) = 1 -π N +1 (r, VC(v)).
(2.17)

The value of π N +1 (r, VC(v)) represents the miss probability of content c r in the virtual cache of node v (i.e. VC(v)). We can see from Figure 2.4 that the solutions of our algorithm converge quickly in the different tested configurations. The convergence speed depends on the content popularity and the network settings, but in general, it takes about 8-10 iterations for all the contents to converge.

Single cache model for LCD

The authors in [START_REF] Laoutaris | The LCD interconnection of LRU caches and its analysis[END_REF] proposed a caching scheme called Leave Copy down. Under the LCD scheme, a new copy of the requested object is cached only on the node that resides immediately below the location of the hit on the path to the requesting client. Compared to LCE, LCD moves the requested contents progressively from the origin server towards the clients, with each request advancing a new copy of the document one hop closer to the client. LCD aims to reduce the redundancy of the same items at multiple nodes by caching an object at one node at a time and to avoid the amplification of replacement errors. The conducted experiments in [START_REF] Laoutaris | The LCD interconnection of LRU caches and its analysis[END_REF] had shown the efficiency and good performance of LCD under different configurations and in addition, it is an easy scheme to implement that does not need additional overhead.

If we model the LCD caching strategy using MACS, the value of β(r) in this case will be the hit probability of content c r in the next-hop cache. Using equations (2.16), the β(r) of a node v is equal to:

β(r, v) = 1 -π N +1 (r, NH(v)).
(2.18)

The value of π N +1 (r, NH(v)) depicts the miss probability of c r in the next-hop or parent cache of v (i.e. NH(v)). We can see from Figure 2.5 that the solutions of our algorithm converge quickly in the different tested configurations (it takes about 8-10 iterations for all the contents to converge).

Multiple caches systems

Following common practice [START_REF] Dan | An Approximate Analysis of the LRU and FIFO Buffer Replacement Schemes[END_REF]- [START_REF] Che | Hierarchical Web caching systems: modeling, design and experimental results[END_REF], we assume in this work that after a cache miss and when a content is decided to be cached by a node, it will be downloaded instantaneously. Let's consider a system of multiple CCN nodes where the contents are forwarded according to the Shortest Path Routing (SPR) algorithm [START_REF] Wang | OSPFN: An OSPF based routing protocol for Named Data Networking[END_REF]. With SPR, when a client's interest cannot be satisfied by a node, it is forwarded along the shortest path to the closest permanent copy of the requested content. In this case, each node has to take into account, in addition to the local requests, the interests that come from other nodes due to a cache miss (we denote this stream of interests by "miss stream" or MS). The outgoing miss stream rate from a node u of a content c r is equal to

MS r (u) = req(r, u) × π N +1 (r, u), (2.19)
where req(r, u) is the total proportion of requests for c r received by u and π N +1 (r, u) is the miss probability of content c r at u. In CCNs, the interests for the same object received by a node will be aggregated and only the first one is sent to the next nodes. This feature should be considered when computing the total miss stream received by a node having more than one child node. The incoming miss stream ratio for an object with a rank r at a node v, that we denote by η r (v), is equal to

η r (v) = � u:NH(u)=v � MS r (u) � w� =u:NH(w)=v (1 -MS r (w)) � . (2.20)
The set {u : NH(u) = v} represents the nodes having v as the next hop in the shortest path toward the source. The value 1 -MS r (w) represents the case where an interest sent from the node w is discarded because it was already received by another node.

If we consider a multi-cache network where the requests aggregation feature is not present, η r (v) in this case will be simply equal to

η r (v) = � u:NH(u)=v MS(r, u). (2.21)
Now, when dealing with an interconnected network of caching nodes, the probability that a node v will receive a request for c r will no longer be p r , but another value that we denote as p � r , which will take into account in addition to the local requests, the interests due to a cache miss from previous nodes. For each node v, this value is equal to

p � r = p r + η r (v) � R k=1 (p k + η k (v)) = p r + η r (v) 1 + � R k=1 η k (v)
.

(2.22)

In other words, p � r represents here the proportion of requests received for c r coming either from clients directly attached to the node (i.e. p r ) or from previous nodes (i.e. η r (v)) over the total requests received by the node v for all the items. In the case where a CCN node does not have local requests, p � r will be then equal to

p � r = η r (v) � R k=1 η k (v)
.

(2.23)

Consider again the Markov chain of a generic single LRU cache that we presented previously (see Figure 2.3). For every node v, we can compute the stationary state probabilities as we did in the case of a single node by replacing p r with p � r :

                               π 1 (r) = p � r (1 + (β(r) -1)π � N +1 (r)) 1 -(γ � 1 (r) -γ 1 (r)) , π 2 (r) = γ � 2 (r)π 2 (r) + (1 -γ � 1 (r))π 1 (r), π i (r) = (1 -p � r -γ � i-1 (r))π i-1 (r) 1 -γ � i (r) , 3 ≤ i ≤ N + 1, N +1 � i=1 π i (r) = 1.
(2.24)

As we mentioned in the previous section, the cache hit probability of a content with popularity r is equal to 1π N +1 (r). To compute the cache hit performance of a multi-cache system operating under LCE or 2Q, we start by treating the leaf nodes of the network since in our model each node needs to know all the incoming stream of requests, including those received due to a cache miss from a previous node. Starting from the leaves where there is no miss stream requests, we go through the core nodes of the network until arriving at the source (or root) node where the permanent copies of the catalog's objects are attached.

When a multi-cache system is operating under the LCD strategy, we cannot produce the steady-state hit rates in a bottom up way, like we did with the previous schemes. This is due to the bidirectional dependency a cache's state has with its upstream or downstream node (and vice versa). When modeling LCD and to compute the cache hit, each node in the network needs to have the incoming stream of requests received from previous nodes due to cache misses. At the same time, it is necessary for each node to know the cache hit rate of the upstream node in order to decide whether the object should be cached or not. To resolve these dependencies, we use a fixed-point iteration method. As a start, we compute the different incoming streams of all nodes assuming that the network operates under the LCE strategy. Since the root node represents the origin server containing all the available contents in the network, its cache hit probability is then equal to one for all the items. Therefore, we can in a top down manner compute the hit ratio of the different caches starting from the root node and going down to the rest of the network using the request streams obtained with LCE. Then, we can repeat these steps using, each time, the new obtained values of equilibrium hit probabilities to recalculate the request streams and then, deduce the different hit ratios until their convergence. The operations needed to compute the hit rates of the different nodes forming a network when the LCD scheme is used are summarized in the iterative procedure below:

1. Calculate the incoming stream of requests of all the nodes starting from the leaves of the network assuming that the network operates under the LCE strategy (i.e., β(r) = 1, r ∈ {1, . . . , R}).

2. Compute the hit ratio of each node starting from the network's root where permanent copies of the available contents are attached using the LCD scheme.

3. Recalculate the incoming stream of requests of the network nodes using the new obtained cache hit rates.

4. Update the network's hit rate using the last obtained values of the incoming stream of requests received by each node.

5. Repeat step three and four until convergence of the cache hit values.

6 Model Evaluation

Tests environment

In order to evaluate the accuracy of our proposals, we compared the analytical models presented, in the previous section, with the results of simulations under ccnSim [START_REF] Chiocchetti | ccnSim: An highly scalable CCN simulator[END_REF], which is a discrete-event and a chunk-level simulator for CCN networks. The accuracy of MACS, compared to the simulation results, can be affected by many parameters. Our focus on the conducted experiments was on the following key settings: cache size and Zipf law's skew distribution value. As for the network topology, a complete binary tree of 31 nodes was chosen to validate our model where the distance and the latency between each two adjacent nodes are the same1 .

We measured during the tests three metrics: cache hit rate, content provider load and distance reduction ratio. The cache hit rate metric represents the ratio of requests that were served by the caches over the total number of requests sent in the network. The content providers load is defined as the proportion of requests not served by the intermediate caches of the network and thus, retrieved from the main source of contents. The distance reduction ratio represents the average gain obtained in terms of distance that an interest travels before finding a copy of the requested object. The content provider load and the distance reduction ratio (denoted respectively as CPL and DRR) are both expressed as a percentage and are computed as follows:

CPL = s � i=1 P miss (i) × 100, DRR = Dist(s) - � s i=1 � � � i-1 j=1 P miss (j) � × P hit (i) × Dist(i) � Dist(s) × 100.
In the definition of CP L and DRR and for sake of clarity, we supposed that the network is formed by a line of s nodes numbered from 1 to s where the clients are attached to node 1 and the content repository is located just after node s. It should be noted that of course, we can compute these metrics in any type of network topology. The values P miss (i) and P hit (i) used here represent respectively the cache hit and cache miss of a network's node v i . The expression Dist(i) is the distance from where the clients requests were generated to the node v i (we could also consider the delay between nodes instead of distance and thus calculate the average network delay.). The index s represents the nearest node v s to the clients to which a content provider is attached (i.e. where a permanent copy of the accessible contents is available).

In the simulation settings, we considered a catalog of contents containing 20, 000 1-chunk sized objects whose popularity distribution follows the Zipf's law. Permanent copies of the available contents are hosted on one repository attached to the root node of the network. We set a uniform cache store capacity on the CCN nodes, which was defined as a proportion of the catalog size. Different simulations were conducted with a cache store size varying from 0.1% to 1.0% of the catalog capacity. The clients, attached to the network's leaves, generate requests according to a Poisson process with a rate per client corresponding to one request per second (each client representing an aggregate of users). We tested also different values of the Zipf law's skew parameter α going from 0.8 to 1.2. As shown in many studies [START_REF] Fricker | Impact of traffic mix on caching performance in a content-centric network[END_REF], these two values correspond to the Zipf popularity exponent in the case of User Generated Content (UGC) and Video on Demand (VoD), respectively. The Least Recently Used (LRU) scheme is used as a cache replacement policy and the virtual buffer capacity used in the 2Q algorithm is equal to the main cache size, to see the model accuracy with different values of the virtual cache size. Next, we will expose and compare the cache hit results obtained with our analytical model and with the ccnSim simulation tool. The simulation results of ccnSim, shown in the graphs, depict the mean values taken over 30 runs, where 10 6 requests are sent in the network after it reaches its stability (i.e., all the caches become full). The error bars represent 99% confidence intervals.

Model results and analysis

Before we proceed further and go through the different results obtained with our model in the case of multi-cache networks, we evaluate in Figure 2.6 the accuracy of Table 2.2 -Hit ratio accuracy comparison (in %) between different models of a 2Q single cache under the IRM model with a Zipf's distribution parameter α = 0.8. Simulations are based on 10 runs of 10 3 × R requests with a warm-up period of 33 %.

Cache/Catalog MACS (e1/e2) Eq.( 13) of [START_REF] Gast | TTL approximations of the cache replacement algorithms LRU(m) and h-LRU[END_REF] (e1/e2) Eq.( 10) of [START_REF] Garetto | A Unified Approach to the Performance Analysis of Caching Systems[END_REF] . We can see from the graphs how MACS has the same precision as the Che approximation and that both models are very accurate. As mentioned in Chapter 1, many models from the state-of-the-art proposed 2Q models based on the approximation of Che [START_REF] Garetto | A Unified Approach to the Performance Analysis of Caching Systems[END_REF]- [START_REF] Gast | TTL approximations of the cache replacement algorithms LRU(m) and h-LRU[END_REF].

A quick comparison of these proposals with MACS is shown in Table 2.2, where e1 and e2 represent respectively the percent errors in terms of hit ratio relatively to ccnSim and the simulator used in [START_REF] Gast | TTL approximations of the cache replacement algorithms LRU(m) and h-LRU[END_REF] and the virtual cache has the same size as the cache itself. The results in Table 2.2 show a good accuracy of the different tested models without a clear difference between them. Compared to MACS, the Che approximation has a lower complexity, but as we discussed earlier in the previous sections and as we will see in the next results, our proposal is a more general model that can be used not only with a specific caching scheme, but covers various caching strategies.

Figures 2.7-2.8-2.9 compare LCE, 2Q and LCD models (i.e. MACS), respectively, with the simulations conducted under different scenarios within ccnSim, in terms of average cache hit ratio as a function of content popularity. For the sake of clarity, we considered in the graphs only the objects whose popularity goes from 1 to 500. We can see from the charts that our analytical model give in average an accurate hit rate for the whole range of item population with different network settings. When the cache size is set to a low value (0.1% of the catalog), the model performs better even with distinct values of α and for different types of content popularity (see Figures 2.7(a)-2.7(b)-2.7(c)-2.8(a)-2.8(b)-2.8(c)-2.9(a)-2.9(b)-2.9(c)). A slight accuracy reduction in the cache hit ratio per content is observed when the cache capacity is set to 1% of the catalog size (see Figures 2.7(d)-2.7(e)-2.7(f)-2.8(d)-2.8(e)-2.8(f)-2.9(d)-2.9(e)-2.9(f)). An increase of the cache size means more states to be considered in MACS for each content, which makes it harder to estimate the hit ratio of each item in the whole network.

In Figures 2.10-2.11-2.12, we plot the network's total hit rate as a function of the cache size and the Zipf's law skew parameter α of LCE, 2Q and LCD models along with ccnSim. Our aim here is to try a large range of values in the network configurations and see the model's performance in terms of accuracy. The results from the charts show a good accuracy in estimating the overall cache hit performance of the network with various settings. Compared to 2Q and LCE, the error rate in LCD model is a little higher. Let's recall that the complexity of modeling LCD with MACS is higher, as it requires the addition of a fixed-point iteration method to compute the cache hit performance of a multi-cache system, as explained previously, which may increase the error rate. Figures 2.13-2.14-2.15 display the cache hit accuracy at different levels of the network topology using LCE, 2Q and LCD. Level one represents the leaf caches and level five being the root node. The models accuracy is slightly reduced at higher levels within the network, especially with the LCD model. The main cause of this inaccuracy is related to the estimation of the request streams due to cache miss. Indeed, at the leaf nodes, the requests received contain only those generated by the clients, which can be easily estimated. However, the incoming miss streams of the nodes located at the core of the network are more difficult to estimate since they are computed using the cache hit rate of previous nodes.

Caching algorithms comparison

We compare, in the following, the performance of the different caching strategies that we have modeled and analyzed previously: LCE, LCD, 2Q and Opt (only analytical results are shown). Opt represents the maximum cache hit ratio that we can achieve when the objective is to reduce the distance travelled to retrieve contents. More specifically, if we consider a network where the caches have the same size N (in terms of number of items that can be stored) and the contents popularities are known in advance, then Opt consists on caching in the nodes located at 1-hop from the clients the most N popular contents of the catalog (c 1 , . . . , c N ). Then, the second N most popular items (c N +1 , . . . , c 2N ) will be cached at the 2-hop nodes, etc. The results of Opt shown in the graphs were obtained using MACS by fixing to one the value of β(r) for the contents that should be cached at each node and β(r) is set to zero for the other items. The cache hit metric is an indicator of caching efficiency in multi-cache networks and generally, as the cache hit of each node increases, the network performance becomes better. Particularly, in traditional network topologies, we have many access caches and fewer core caches (a tree topology is a good example of this type of network). In this type of topology, access caches are linked to clients and often have similar content in the same region and the total cache hit is calculated as the average hit of the different caches in the network. As there is more caches at the access layer level, improving the overall cache hit would first require improving the hit of the access caches. This approach seems to be appropriate since it consists on bringing content closer to users and thus improving their quality of experience. This also has the advantage of reducing traffic in the operator's network. This strategy represents the main objective behind LCD and 2Q. For this reason, and when we made the comparison in terms of cache hit ratio, the target of Opt was to maximize the hop saving in order to cope with the aim of the caching schemes used in the state-of-the-art.

In Figure 2.16, we display the total hit rate of the network as a function of the α value (the Zipf law skew parameter) and the cache size using different caching schemes. The virtual cache size in 2Q was set to 20, which represents approximately the best tuning in the different use cases that were evaluated. We can see from the charts that LCD outperforms LCE, as it reduces the content redundancy in the network nodes and thus, more distinct objects are available in the caches. Each time a content is requested in LCD, it gets one-hop closer to the leaf nodes, which is an efficient way to detect and keep the popular items as closest as possible to the clients and to let the unpopular ones on higher levels of the network. Despite the efficiency of LCD, the results show the superiority of 2Q compared to the other caching schemes. Thanks to an effective filtering effect by means of a virtual buffer, 2Q admits more popular contents into the cache than the other techniques.

As the cache size increases (Figures 2.16(a)-2.16(b)-2.16(c)), the performance difference between the evaluated caching schemes is reduced and gets closer to the optimal values. Increasing the storage capacity will diminish the impact of caching unpopular items, and the cache will become less affected by the adopted caching scheme. However, a limited cache size will increase the probability of discarding valuable contents to the benefit of the unpopular ones. In this case, the efficiency of the decision caching strategy in accepting only the most popular items is crucial. For example, when α is set to 1.0 and the cache size is equal to 0.1% of the catalog, LCE achieves 53% of the optimal performance. However, if we set the cache size value to 1.0% of the catalog and we keep the same value of α, LCE performance reaches 63% of the optimal one.

The results also show a clear impact of the contents popularity distribution on the caching efficiency (Figures 2.16(d)-2.16(e)-2.16(f)). A high value of α (above one) means that fewer contents will receive most of the requests and, thus, decreasing the probability of caching many distinct unpopular items independently from the caching strategy. However, when α is set to a low value (below one), the contents popularity becomes more uniform, which makes it harder for the caching scheme to anticipate the most demanded items. For example, when the cache size is set 0.5% of the catalog and α is equal to 0.8, LCE achieves 47% of the optimal performance. In case where the α is set to 1.2 and without changing the cache size value, LCE performance reaches %71 of the optimal one. Figure 2.17 displays the cache hit ratio at different layers of the networks with different settings and using different caching schemes. We can see from the different graphs that the cache hit performance is much higher at the first level than the other ones, independently from the used caching scheme. The nodes at level one will be the first to receive the clients' requests, which increases their probability to serve the most popular contents demanded by the users. This will result in nodes at higher levels to cache less popular contents and thus, decreasing their performance. Compared to the total cache hit ratio of the network, it is clear that the first level nodes achieve most of it. The storage capacities located at higher levels of the network cannot be used efficiently and can be considered as wasted resources. As we have highlighted previously during the analysis of the results depicted in Figure 2.16, the cache size and the Zipf law parameter α values have a significant impact on the caching efficiency, as it can be seen from the performance of the nodes at the first level of the network (Figure 2.17). As the cache size and α increase, caching the most popular objects and keeping them in the cache becomes easier, which will result in low performance difference between the considered caching schemes. Figure 2.18 gives an idea about the contents getting the most hits at each level of the network, for different parameters and caching schemes. For the sake of clarity, the objects having a very low cache hit rate are not shown on the graphs. These results clearly confirm the superiority of LCD and especially, 2Q over the other ones. Indeed, the graphs show clearly that 2Q succeeds in keeping at the nodes of level one more popular items than the other techniques. In LCD or LCE, the top most requested objects that increasing the cache size improves, of course, the network performance, but not in a uniform manner. In fact, doubling the cache size does not necessarily double the caching scheme efficiency. Now, if we compare the results of LCD and especially, 2Q to Opt (see Figures 2.16-2.17-2.19-2.20), we can see that there is no much room left for improvement. In addition, a caching scheme that can reach or get closer to the theoretical optimal outcomes, in terms of network performance (i.e., cache hit ratio, content provider load, etc.), will necessarily increase the network operations overhead. The efficiency of the 2Q algorithm and its performance/overhead trade-off makes it a good candidate to be used as a caching strategy in CCN networks.

Conclusion

The Content-Centric Networking (CCN) paradigm is one of the most promising architectures for the future Internet. The in-network caching feature provided by CCN has a direct impact on the system performance, and it is important to analyze and evaluate the caching behavior in order to gain insights for optimized CCN caching schemes. We presented in this chapter MACS, a Markov chain-based Approximation of Caching Systems to estimate the cache hit probability under the popular LRU replacement policy. The model can be applied to different caching systems, not only to CCN, and can be used to compute different performance metrics in addition to the cache hit, such as the content provider load and the distance reduction ratio. The versatility of MACS enables us to model and analyze different caching schemes like LCE, LCD and 2Q. The conducted experiments clearly show the accuracy of our model in estimating the cache hit rate of a multi-cache system and also indicate the efficiency of 2Q in terms of network performance, which makes it a good candidate to be used as a caching strategy.

In the next chapter, we will investigate the impact of cache resources placement in CCN and in multi-cache systems in general. By means of our analytic tool MACS, a new approach is proposed to tackle this problem, and we will see how it can improve significantly the network performance.

Introduction

After presenting our model MACS in the previous chapter, we investigate in this chapter the optimal placement of caching resources. When studying multi-cache networks, the cache allocation problem is one of the most important issues to address, especially due to the very expensive cost of deploying distributed storage capacities along the network. More specifically, it consists on finding how a limited storage budget should be distributed across the network's nodes in order to ensure an effective use of caches. The proposed approach in this chapter [START_REF] Ben-Ammar | Efficiently allocating distributed caching resources in future smart networks[END_REF], which is based on joint cache management between ISPs and CPs, solves the trade-off between minimizing the hit rate in the origin server (with the risk of degrading the quality of experience) and minimizing the distance between clients and the requested contents (with the risk of ineffective caching for the same amount of cache). We model the cache allocation problem as a multi-objective integer nonlinear program (the nonlinearity is confined to the objective functions). Since it is an NP-hard problem [START_REF] Hemmecke | Nonlinear integer programming[END_REF], we propose the use of the Greedy Randomized Adaptive Search Procedure (GRASP) [START_REF] Feo | Greedy Randomized Adaptive Search Procedures[END_REF], which has shown its effectiveness in solving combinatorial optimization problems. Moreover, unlike other metaheuristics like evolutionary algorithms, GRASP requires fewer parameters (only one parameter in its basic version).

Motivations

During the last decade, ISPs and CPs infrastructures underwent a major metamorphosis driven by new networking paradigms, namely: Software Defined Networks (SDN) [START_REF] Matias | Toward an SDN-enabled NFV architecture[END_REF] and Network Function Virtualization (NFV) [START_REF] Han | Network function virtualization: Challenges and opportunities for innovations[END_REF]. The upcoming advent of 5G will certainly represent the most important achievement of this evolution [START_REF] Andrews | What Will 5G Be?[END_REF]. In this context, static (planning) or dynamic (on-demand) network resources placement, especially caching, remains an open issue. Indeed, co-locating caching resources at the core of the network optimizes caches, but not the network. Distributing caches optimizes network resources, but reduces the efficiency of caches, due to the existing redundancy at the edge. The optimal placement of caching resources is one of the most important issues to address in multi-cache networks in general, especially due to the very expensive cost of deploying distributed storage capacities along the network.

In previous works that addressed the cache allocation problem, only one perfor-mance gain metric is generally considered (e.g. access latency, cache hit, etc.) to find a storage distribution solution or to compare between different possibilities. In this work, we use jointly the following two performance metrics to evaluate the cache gain: content provider load and average distance ratio. The first metric represents the amount of contents that were served by the origin server over all the requests sent in the network. The second one depicts the average distance travelled to get contents in the network over the obtained distance without caching. We chose these two metrics for their importance in representing the cost and gain obtained from the use of the in-network caching. A high content provider load means most of the requested contents are not served by the intermediate caches, and thus retrieved from their original location. Accessing the main source of contents is very expensive for network operators, and this is why it is important for them to keep the content provider load as low as possible. On the other hand, a low average distance to get contents means a better Quality of Experience for users (QoE). Hence, a good cache allocation strategy should find the best trade-off between these two metrics.

2 Multi-objective cache placement strategy

System assumptions

Let G = (V, E) be the graph representing a general network of caches, where V = {v 1 , ..., v M } depicts the nodes of the network and E ⊂ V × V is the set of links connecting the nodes. Each node in the network is equipped with a caching module used to store contents locally. Let C = {c 1 , ..., c R } be the set of the catalog's contents available for the users. We assume that all the accessible contents in the system have an identical size and are divided into small packets or chunks, which are in turn of the same size. The cache capacity is then expressed in terms of the number of contents or chunks that can be stored. All the available contents are stored permanently at one or more servers attached to some nodes within the network. In the rest of the chapter and for the sake of readability, we will use the term node/cache interchangeably as well as the terms rank/popularity and content/item/object.

Clients, which are attached to the network nodes, send requests into the network looking for contents. The pattern of these requests is characterized by the Independent Reference Model (IRM) [START_REF] Dan | An Approximate Analysis of the LRU and FIFO Buffer Replacement Schemes[END_REF]. Suiting the IRM model, users generate an independent and identically distributed sequence of requests from the catalog C of R objects. As it was described in the previous chapter, the probability p r to request an item c r from the set of available contents in the network is constant and follows a popularity law (i.e. Zipf law), where the contents are ranked decreasingly according to their popularity from 1 to R. In the present work, the LRU algorithm is used to manage the node's content store and two caching schemes will be considered: LCE and 2Q.

Problem formulation

A cache allocation solution (taken for example by an NFV orchestrator), can be defined by a vector X = (x 1 , . . . , x M ), where x i represents the amount of storage capacity placed in node v i . To compute the content provider load or the average distance ratio of a configuration of caches X, we use our model MACS (Markov chain-based Approximation of Caching Systems), which we presented in the previous chapter. MACS is an analytic tool that allows us to estimate the cache hit ratio of an interconnection of caches, which can be used to compute other performance metrics like the content provider load and the average distance ratio. By using MACS and for each cache allocation configuration X, we can evaluate the performance of the whole system in its steady-state and not just during a transient phase.

Since in this work the caching capacity is expressed in terms of the number of contents that can be stored, then we have x i ∈ N. As we measure the caching gain through evaluating the content provider load and the average distance ratio in the network, our objective is to find a cache distribution solution such that the evaluation metrics that we have chosen are optimized (i.e. minimized). The cache placement is then formulated as a multi-objective optimization problem as follows: minimize

X=(x 1 ,...,x M ) f 1 (X), f 2 (X) subject to M � i=1 x i ≤ T c , i = 1, . . . , M, x i ∈ N, i = 1, . . . , M. (3.1)
The value of T c represents the total cache resources to be distributed in the network. The expressions f 1 (X) and f 2 (X) are both expressed as a percentage and represent, respectively, the content provider load and the average distance ratio of a cache placement configuration X using MACS. The primary function of MACS is to calculate the cache hit ratio of the network's nodes. Then, we can compute f 1 (X) and f 2 (X) as follows:

f 1 (X) = � s � i=1 P miss (i) � × 100, f 2 (X) = � s i=1 � � � i-1 j=1 P miss (j) � × P hit (i) × Distance(i) � Distance(s) × 100.
(3.

2)

The values P miss (i) and P hit (i) represent, respectively, the cache hit and cache miss of a network's node v i . The expression Distance(i) is the distance from where the clients requests were generated to the node v i . The index s represents the nearest node v s to the clients to which a content provider is attached (i.e. where a permanent copy of the contents is available). In the definition of f 1 (X) and f 2 (X) and for sake of clarity, we supposed that the network is formed by a line of s nodes numbered from 1 to s where the clients are attached to node v 1 and the content repository is located just after node v s . It has to be noted that of course, we can compute these metrics in any type of network topology and that we could consider the delay between nodes instead of distance and thus calculate the average network delay.

Since here we are dealing with a multi-objective optimization problem, in which we want to minimize f 1 (X) and f 2 (X), the solutions will be a set of efficient points usually called the Pareto frontier. Pareto efficiency or optimality implies that a solution to a multi-objective problem is such that no single objective can be improved without deteriorating another one. In our case, a solution X * is said to be efficient if there is no other solution X such that f 1 (X) < f 1 (X * ) and f 2 (X) ≤ f 2 (X * ) at the same time, or f 2 (X) < f 2 (X * ) and f 1 (X) ≤ f 1 (X * ). Given that integer nonlinear programming is an NP-hard problem, solving the cache allocation problem as we modeled below will come at a very high computational cost. More specifically and due to the nonlinearity of the objective functions, we need to perform an exhaustive search method in order to enumerate all possible candidates that respect the problem constraints and find the set of optimal cache distributions. If we look closely to our formulation of the problem, the task of enumerating all possible candidates comes down to computing the weak composition of an integer n into k parts, i.e., writing n as the sum of a sequence of non-negative integers. A weak composition C n,k [START_REF] Page | Generalized Algorithm for Restricted Weak Composition Generation[END_REF] has a cardinality of Solution ← Greedy_Randomized_Construction(λ);

|C n,k | =   n + k -1 k -1   = (n + k -1)! n!(k -1)! . ( 3
3:

Solution ← Local_Search(Solution);

4:

Best_Solution ← Solution;

5:

for k = 1, . . . , Max_Iterations -1 do 6:

Solution ← Greedy_Randomized_Construction(λ);

7:

Solution ← Local_Search(Solution);

8: if f (Solution) < f (Best_Solution) then 9:
Best_Solution ← Solution;

Solving cache allocation problem using GRASP

Mono-objective GRASP

The Greedy Randomized Adaptive Search Procedure or GRASP [START_REF] Feo | Greedy Randomized Adaptive Search Procedures[END_REF] is an iterative process, where each iteration consists basically of two steps: construction and local search. The construction phase seeks to build a feasible solution using a greedy randomized approach, whose neighborhood will be investigated during the local search in order to find a local optimum. The pseudo-code of Algorithm 2 depicts the main blocks of a mono-objective GRASP procedure, where Max_Iterations is the number of iterations that are performed (we will see later the role of the parameter λ and the case of multi-objective GRASP). The best overall solution is, then, kept as the final result. The construction phase operations are shown in Algorithm 3. Let's recall first that the solution S to be built during the construction phase is defined by a vector X = (x 1 , . . . , x M ), where x i represents the amount of storage capacity placed in node v i . Initially, no cache resources is allocated to the nodes, so at the beginning, for i = 1, . . . , M do // Create candidate set CS 10:

x i ← x i + P c ; 11: X ← (x 1 , . . . , x M ); 12:
CS ← CS ∪ {X}; 13:

x i ← x i -P c ; Evaluate the incremental costs f (X) ∀X ∈ CS;

16: f min ← min{f (X) | X ∈ CS}; 17: f max ← max{f (X) | X ∈ CS}; 18: RCL ← {X ∈ CS|f (X) ≤ f min + λ(f max -f min )}; 19:
Select an element X * from the RCL at random; for i = 1, . . . , M do 22:

x i ← x * i ;

23:

end for

24:

end while

25:

return S; 26: end function S = (0, . . . , 0). The set CS will contain the candidate elements, which will be used for the solution S. In our case and at each step, CS will contain a set of cache placement configurations X i where a partial resource that we denote P c , is taken from the total available cache T c and allocated to one of the network's nodes. If we have, for example, a network with three nodes, T c = 100 and P c = 10, the initial candidate set will then be: CS = {(10, 0, 0), (0, 10, 0), (0, 0, 10)}.

Each candidate is then evaluated with a greedy function in order to build a restricted candidate list RCL, which will contain some of the candidate set who have the best evaluation values (e.g., RCL = {(10, 0, 0), (0, 10, 0)}). The limitation criteria of the list cardinality can be either based on the number of elements or based on their quality, as we did in Algorithm 3 (line 18). The elements added to the RCL list will then be those hav- for i = 1, . . . , M do 5:

x i ← x i -P c ; 6:

for j = 1, . . . , i -1 do // Cache resources transfer between nodes to improve the current solution 7:

x j ← x j + P c ; x j ← x j -P c ; for j = i + 1, . . . , M do // Cache resources transfer between nodes to improve the current solution 14:

8: if f (x 1 , . . . , x M ) < f (S)
x j ← x j + P c ; x j ← x j -P c ; while Solution S is not locally optimal 22: return S; 23: end function ing an evaluation value inferior to the threshold (i.e., f (X) ∈ [f min , f min +λ(f max -f min )]). The value of λ will control the insertion condition of candidate elements to RCL (λ ∈ [0, 1]). The case λ = 1 is equivalent to a random construction, while λ = 0 corresponds to a pure greedy algorithm. Once RCL is built, one element is randomly selected and added to the solution S being built. The candidate list CS and the evaluation function f (CS) are then updated and the construction is repeated (line 7 to 24) until the total use of the cache budget T c . If we consider for example that the second element from RCL has been chosen, the current partial solution will then be S = (0, 10, 0) and the new candidate list will contain: CS = {(10, 10, 0), (0, 20, 0), (0, 10, 10)}.

15: if f (x 1 , . . . , x M ) < f (S)
Once the cache budget T c is distributed, the local search will seek to improve the generated solution (e.g., S = [START_REF] Ben-Ammar | On the performance analysis of distributed caching systems using a customizable Markov chain model[END_REF][START_REF] O'neil | The LRU-K Page Replacement Algorithm for Database Disk Buffering[END_REF][START_REF] O'neil | The LRU-K Page Replacement Algorithm for Database Disk Buffering[END_REF]) by evaluating its neighborhood (Algorithm 4). The efficiency of a local search method depends on many aspects, such as the neighborhood structure of the considered solution, the neighbors search technique and the starting solution itself. Two methods can be used for the neighborhood search: the bestimproving strategy or the first-improving one. The best-improving strategy consists on investigating all the neighbors and the current solution will then be replaced by the best neighbor found. In the case when a first-improving method is used, the current solution will be replaced by the first neighbor whose evaluation value is better. In our case, we used for the neighborhood search a best-improving strategy as follows: starting from the solution generated by the greedy randomized construction, we transfer an amount of cache P c from one node to another and explore all the possible cases looking for a cache configuration whose evaluation function value is better than the current one (e.g., Neighbor(S) = {(10, 50, 40), [START_REF] Flajolet | Birthday paradox, coupon collectors, caching algorithms and self-organizing search[END_REF][START_REF] Flajolet | Birthday paradox, coupon collectors, caching algorithms and self-organizing search[END_REF][START_REF] O'neil | The LRU-K Page Replacement Algorithm for Database Disk Buffering[END_REF], etc.}). We repeat these steps until the current solution can no longer be improved, which then will be returned as the output of the local search procedure of GRASP.

As for the complexity of GRASP algorithms (i.e. construction and local search) applied to our formulation of the cache allocation problem, we have a complexity of O(T c M ) for the construction phase and O(M 2 ) for the local search phase.

Multi-objective GRASP

In single-objective GRASP, only one greedy function is used to evaluate the candidate solutions during the construction and local search phases. In multi-objective GRASP [START_REF] Marti | Multiobjective GRASP with Path Relinking[END_REF], we have in the general case k functions (f 1 (X), . . . , f k (X)) to evaluate a candidate element X and the objective functions can be used mainly in two ways:

-Pure construction/local search: this method consists on using one single objective during each phase of the solution generation. The selection of which evaluation function to be used in each iteration can be done using the following approaches:

� Pure-random approach: using this method means that the entire construction or local search is guided by only one single evaluation function that we select randomly from the set of the objective functions (f 1 (X), . . . , f k (X)).

� Pure-ordered approach: when this method is adopted, we select the greedy function in an ordered way and one at a time and use it in all the steps of the construction phase or the local search. In other words, the candidate elements are evaluated with f 1 (X) during the first iteration. Then, we use f 2 (X) in the second iteration, and so on until we reach the k + 1-th iteration, in which we go back again to f 1 (X).

-Combined construction/local search: this method consists on using more than one greedy function in each iteration by means of one of the following approaches:

� Sequential combined approach: by using this process, each step of the construction or local search is guided by a different evaluation function. The choice of which objective to choose between each construction step can be done either randomly or in an ordered way.

� Weighted combined approach: with this method, a weighted combination of the objective functions is used in each step of the construction or local search 1 . We can either change the weights between the steps of each phase or keep them the same during the whole process. It has to be noted that the weights can help us scale evaluations functions having significantly varied magnitudes into similar and comparable ones. In addition, some greedy functions in multi-objective optimization can be minimized while others maximized. In this case, the weights can take positive and negative values in order to take into account this fact.

In our case, we have two evaluation functions to be used in the multi-objective GRASP: f 1 (X) and f 2 (X) and there are many methods that can be used to compute the outcome of each configuration in the construction and local search phases. For example, one can use f 1 (X) in the construction phase and f 2 (X) during the local search and vice versa, or choose randomly between the objective functions during each GRASP iteration. We can also consider a weighted combined method (f (X) = w 1 f 1 (X)+w 2 f 2 (X)). The choice of which method to be used to evaluate a candidate solution (or partial solution) can depend on some desired results that should be achieved or some constraints that should be respected.

In our work, we considered two methods to generate the solutions based on the defined objective functions f 1 (X) and f 2 (X). In the first method, which matches a pureordered approach, we use in each iteration one objective function (f 1 (X) or f 2 (X)) during the construction phase. The other one is then used during the local search. Then, we alternate between the selected functions for each phase in the next iteration. For example, if we chose in the first iteration respectively f 1 (X) and f 2 (X) for the construction and local search phases then, in the second iteration, we will use f 1 (X) in the local search and f 2 (X) in the construction phase, etc. This approach will allow us to produce diversified solutions of good quality. In the second method, we used a weighted combination of the evaluation functions as follows:

f (X) = � 0.5 × |f 1 (X) -100| |Opt(f 1 (X)) -100| + 0.5 × |f 2 (X) -100| |Opt(f 2 (X)) -100| � × 100. (3.4)
The expressions Opt(f 1 (X)) and Opt(f 2 (X)) represent respectively the theoretical optimal values of the metrics f 1 (X) and f 2 (X) for a fixed cache resources budget T c . More specifically, Opt(f 1 (X)) is obtained by allocating all the available cache resources at the root node and then, computing the content provider load. As for Opt(f 2 (X)), it is obtained by computing the average distance ratio metric where all the total cache resources are placed at one-hop from the clients. Since here we want to minimize f 1 (X) and f 2 (X) (expressed as percentages), then the range of values taken by these functions is: [Opt(f i (X)), 100] (i = 1, 2). The value 100 represents the worst case, i.e., where no cache resources were allocated and thus, all the contents are retrieved from the main source and the average distance to get objects is not reduced. So, what we did is to compute how much improvement can be achieved in each of these performance metrics relatively to the optimal values that can be reached. For example, and for a certain configuration X = (x 1 , . . . , x M ), if we have f 1 (X) = 40% and Opt(f 1 (X)) = 20%, then (|40 -100|/|20 -100|) × 100 = 75%. This value means that we have achieved 75% of the optimal outcome of the content provider load.

The evaluation function f (X) can be seen as a ratio of efficiency and it can be used in a case scenario where the aim is to improve as much as possible the network's overall performance. It is also a mean to scale the evaluation functions f 1 (X) and f 2 (X) into similar and comparable magnitudes. In addition, the weighting coefficients (fixed to 0.5 in our case) can be tuned in order to give more importance to one metric over the other. In the case where the weighted combined approach defined by f (X) is adopted, the cache placement is then formulated as the following optimization problem: maximize

X=(x 1 ,...,x M ) f (X) subject to M � i=1 x i ≤ T c , i = 1, . . . , M, x i ∈ N, i = 1, . . . , M.

Performance evaluation

In this section, we present the evaluation results of the cache allocation problem using the methods presented previously. We will expose at first different results comparing the outcomes of the metaheuristic to the optimal solutions (i.e. obtained using an exhaustive search approach). Then, we will display some of the results obtained using our application of GRASP to the problem that we have formulated, to have an idea about the solutions that can be proposed by our approaches.

Model configuration

The different tests were conducted on a typical three-level network that contains 21 nodes forming a perfect 4-ary tree topology where the distance and the latency between each two adjacent nodes are the same (see Figure 3.1). We considered in our experiments a catalog of contents containing 20, 000 1-chunk sized objects whose popularity distribution follows the Zipf's law. Permanent copies of the available contents are hosted on one repository attached to the root node of the network, and the users are attached to the network's leaves (i.e. level 1 of the network). We tested different values of the Zipf law's skew parameter α going from 0.8 to 1.2. The parameter λ that controls the amounts of greediness and randomness in GRASP was set to 0.5 and the total cache T c is expressed as a ratio of the catalog size. Two caching strategies were used during the experiments: LCE and 2Q. The 2Q policy is of course more efficient than LCE as it was shown in the previous chapter but the aim here to see the behaviour of our model where different caching strategies are used. As we mentioned previously, the network performance is evaluated using the content provider load and average distance ratio metrics. For sake of simplicity, the cache resources are allocated in a way that the nodes located on the same level of the network have the same cache size. Since there are 16 nodes on the first level of the network, P c should be a multiple of 16 and in our case, it was set to 16. Thus, a cache resource placement can be described as X = (x 1 , x 2 , x 3 ), where x i represents the total cache allocated at level i of the network.

Model results and analysis

In Figures 3.2 front using the separate evaluation functions approach (content provider load and average distance ratio metrics). We can see from the plots how the solutions produced by GRASP, independently from the used caching scheme, are very close to the set of dominant points in the different tested scenarios, which reflects the good quality of the metaheuristic outcomes.

In Figure 3.4-3.5, we compare the solutions obtained using the weighted combined approach with the optimal values (only the best solution obtained with GRASP is shown). The results in these graphs also show the efficiency of the metaheuristic in giving solutions close to the optimal ones. When the Zipf's parameter α is set to 0.8, we observe that the solutions generated by GRASP are not as close to the optimal values as the results obtained in the other cases. Having a low value of α (α < 1) means a lower difference in popularity between the different contents, which makes it more difficult to construct cache distribution solutions using GRASP that approach the optimal performance. In Tables 3.1-3.2, we display the cache allocation solutions generated by GRASP (only the results of four iterations of GRASP are shown) using separate evaluation functions approach and testing two different caching schemes: LCE (Table 3.1) and 2Q (Table 3.2). Depending on the Zipf law's parameter α, the total cache resources available T c and the adopted caching strategy, different solutions will be generated by GRASP. The choice of the final solutions between the different proposed ones can be based on some constraints that should be respected. For example, and under the LCE policy, if T c = 20% and α = 1.2 (Table 3.1) and if the priority is to minimize the content provider load (f 1 (X)), then the allocation X = (1088, 800, 2208) is the best one.

T c = 20% α = 1.0 α X f 1 (X) f 2 (X) T c X f 1 (X) f 2 (X) 0
In case when the 2Q scheme is used, if α = 1.0 and T c = 15% (Table 3.2) and one wants to minimize first the average distance ratio (f 2 (X)), then the allocation X = (1408, 768, 896) is the one to choose. In Tables 3.3-3.4, we expose the cache allocation solutions generated by GRASP using a weighted combined evaluation approach. In this case scenario, the objective is to optimize the overall network performance without considering separately the evaluation metrics. The proposed solution will be the cache allocation that gives the best outcome. For example, and under the LCE strategy, if T c = 20% and α = 1.0 (Table 3.3), the solution X = (1056, 816, 2224) is the best one. In case when the 2Q scheme is used and if we have for example α = 1.0 and T c = 25% then, the cache distribution X = (1328, 1056, 2736) is the best solution generated by GRASP. Table 3.2 -Cache allocation solutions using GRASP with two separate evaluation functions when 2Q is used.

T c = 20% α = 1.0 α X f 1 (X) f 2 (X) T c X f 1 (X) f 2 (X)
Table 3.3 -Cache allocation solutions using GRASP with weighted combined evaluation function when LCE is used.

T c = 20% α = 1.0 α X f (X) T c X f (X)
Table 3.4 -Cache allocation solutions using GRASP with weighted combined evaluation function when 2Q is used. If we compare between LCE and 2Q in terms of network performance when different cache allocation solutions are used, the 2Q policy generally has better outcomes than LCE. However, it can be possible that LCE has better results in certain cases. For example, if we look at Tables 3.1-3.2 and in the case where α = 1.0 and T c = 25%, the cache allocation X = (1264, 1184, 2672) when LCE is used achieves better performance than the cache allocation X = (64, 3200, 1856) when 2Q is applied. This result reinforces the importance of placing the cache resources in distributed networks and how it can affect drastically the network performance.

T c = 20% α = 1.0 α X f (X) T c X f (
We can see from the exposed different results that there is no absolute solution for the cache allocation problem and it is not a question about whether to cache at the edge or in the core. Depending on the network's configuration and the objectives that one wants to achieve, multiple solutions can be adopted. Other metrics can be used as evaluation functions during the building of the solutions instead of those that we used in this work like, for example, the financial cost of cache resources deployment. The aim of our proposal is to give a tool capable of efficiently allocating distributed caching resources and versatile enough to adapt to specific desired network performance and constraints.

Conclusion

We addressed in this chapter the problem of how to efficiently allocate cache resources in multi-cache networks. We first model it as a multi-objective optimization problem where our analytic tool MACS is used to evaluate the objective functions. Our formulation of the problem turned out to be an NP-hard problem and finding the optimal solutions in this case is not always practical. Thus, we propose an adaptation of the GRASP metaheuristic to solve the problem using different evaluation methods to generate the solutions. The experimental results have showed how the outcomes of our algorithm are very close to the optimal ones and how the proposed solutions depend on different parameters like the total cache budget. The versatility of our proposal allows it to be applied to any arbitrary network topology, and it can include other cost functions to be used as objective functions.

CCN and multi-cache networks in general.

In chapter one, we start first by giving an overview of the Information-Centric Networking paradigm to focus after that on Content-Centric Network, which represents a promising ICN solution for the future Internet. Then, we analyze the existing works related to the caching feature of ICNs and of multi-cache systems in general. More specifically, we discuss the issues related to cache modeling and cache resources allocation in multi-cache networks, which represent the core of this thesis work.

The second chapter starts by introducing an analytical model based on Markov chains named MACS (Markov chain-based Approximation of Caching Systems). This model allows us to compute the hit probability of an LRU cache operating under the default caching scheme called LCE where the contents are always saved when received. By proposing a methodology that allows modeling the caching decision process in the general case, we were able to extend MACS so that it can be used to analyze different caching algorithms different from LCE. We aim with our proposal to gain more insights on the efficiency and limits of CCN caching strategies, with a focus on the schemes having a good performance/overhead trade-off through the analysis of different network performance metrics. We have shown how the versatility of our cache modeling tool enables to mimic efficient caching strategies such as LCD and 2Q and it can be easily adapted to represent an interconnection of caches under different schemes. Even though our proposal was first used in the context of CCN networks, it can of course be applied to multi-cache networks in general. In addition to the cache hit, MACS can be used to compute different performance metrics like the content provider load and the distance reduction ratio. The conducted tests have shown the accuracy of our model in estimating the cache hit rate of a multi-cache system under different caching schemes. The obtained results also indicate the efficiency of the 2Q algorithm and its performance/overhead trade-off makes it a good candidate to be used as a caching strategy.

In the third chapter, the optimal placement of caching resources is investigated. The cache allocation issue is one of the most important problems to address when studying multi-cache networks because of the expensive cost of deploying distributed storage resources along the network. In this context, we propose an approach that solves the trade-off between minimizing the hit rate in the origin server and minimizing the distance to retrieve contents. To do so, we modelled the cache allocation problem as a multi-objective integer nonlinear program where our analytic tool MACS is used to evaluate the objective functions. Our formulation of the problem turned out to be an NP-hard problem. Thus, we proposed an adaptation of the metaheuristic GRASP to solve the problem using different evaluation functions to generate the solutions. The conducted tests have showed the closeness of the metaheuristic's outcomes to the optimal ones. By analyzing the different obtained results, we have shown that there is no absolute solution for the cache allocation problem and in contrast to the conclusions made in previous works, it is not a question about whether to cache at the edge or in the core of the network. The distribution of cache resources will depend on the network's configuration and the objectives that one wants to achieve. The aim of the work presented in the third chapter is to give a tool capable of efficiently allocation distributed caching resources that takes into account more than one performance metric and versatile enough to adapt to specific desired network performance and constraints.

Perspectives

The state-of-the-art presented in chapter one shows the extent of an active research domain in the areas of cache modeling and cache optimization in Content-Centric Networks and multi-cache systems in general. With the proliferation of CDN-based paradigms and the upcoming advent of 5G, this domain is rapidly evolving and multiple research opportunities that were not addressed in this thesis and related to our work deserve in our opinion to be looked at.

Dynamic content popularity

Understanding the evolution of content popularity plays a key role on the cache optimization. It has a direct effect on how caching resources are distributed within networks and on the design of efficient caching strategies and thus, impacting the overall performance of networks. A large amount of existing works in the literature (including our work) that studied caching uses the well-known Independent Reference Model (IRM) along with the Zipf law to shape the content popularity. Under the IRM model, the requests for contents occur in an independent and identically distributed (i.i.d.) sequence. In other words, the probability to request an item c r from the set of available contents in the network is proportional to a popularity law p r and does not evolve in time. However, the popularity and the catalog of contents in reality and in many cases can be far from being stationary, as they are more likely to evolve quickly [START_REF] Zhou | Video Popularity Dynamics and Its Implication for Replication[END_REF]. Proposing a model to capture the popularity of contents with non-stationary behaviour remains an open issue.

Caching from an economic point of view

The endless race of content providers towards even more content and even more quality is increasing data consumption as never before. This growth is such that it is undermining the infrastructures of Internet Service Providers, which require to be constantly upgraded in order to relieve the load on the ISPs networks [START_REF] Bertin | Next-Generation PoP with Functional Convergence Redistributions[END_REF] with huge capital investments. This led to the proliferation of Content Delivery Networks, which has become an essential part of the Internet ecosystem and has been a reliable solution for Content Providers to deliver their content. The advent of NFV [START_REF] Han | Network function virtualization: Challenges and opportunities for innovations[END_REF] and ICN-based paradigms, especially caching, as well as the dynamic orchestration of resources bring much more flexibility to cache-based infrastructures and their management. These features will be, therefore, major drivers that will certainly accelerate these developments and make them available to Content Providers [START_REF] Parvez | A Survey on Low Latency Towards 5G: RAN, Core Network and Caching Solutions[END_REF]. These recent developments represent a great opportunity for ISPs by allowing them to easily develop caching capabilities within their infrastructures, in order to offer services with better Quality of Experience (QoE) for end-users as well as the reduction of traffic at peering levels, transport and core networks. In addition, they will be able to share their infrastructure by offering these caching capabilities to third parties, which makes it possible to multiply sources of revenues. The study of caching along with the cooperation of CDNs and multi-cache networks with ISPs from an economic point of view is becoming a more interesting area to look at due to the enhancement of flexibility in managing cache resources and it is in our opinion a hot topic to investigate.

Caching in wireless networks

During these last years, there is growing consensus that caching is placed to play a key role in future communication systems and networks, especially with the upcoming advent of 5G [START_REF] Paschos | The Role of Caching in Future Communication Systems and Networks[END_REF]. In the different proposals that we have presented in this thesis, the focus was basically on static networks where the system configuration does not evolve much in time, which is not the case in cache-enabled wireless networks. Studying caching in this type of networks has already started in the literature [START_REF] Alfano | Content-centric wireless networks with limited buffers: When mobility hurts[END_REF]- [START_REF] Liu | Caching at the wireless edge: design aspects, challenges, and future directions[END_REF] and many different research directions have been not sufficiently explored yet. One interesting subject that we did not have the opportunity to investigate in this thesis and that in our opinion needs to be addressed is the analytic modelisation and performance evaluation of cache-enabled wireless networks. In chapter two of this thesis, we proposed a generic model of static multi-cache networks and it is not straightforward to apply it to multi-cache wireless networks. In these latter, features like users mobility and heterogeneity of cache resources (caching at users devices, caching at base stations, etc.) impose additional difficulties and should be taken into account when studying such systems. Designing analytical models of cache-enabled wireless networks remains an open issue. Title: On models for performance evaluation and cache resources placement in multicache networks. Abstract: In the last few years, Content Providers (CPs) have experienced a high increase in requests for video contents and rich media services. In view of the network scaling limitations and beyond Content Delivery Networks (CDNs), Internet Service Providers (ISPs) are developing their own caching systems in order to improve the network performance. These factors explain the enthusiasm around the Content-Centric Networking (CCN) concept and its in-network caching feature. The analytical quantification of caching performance is, however, not sufficiently explored in the literature. Moreover, setting up an efficient caching system within a network infrastructure is very complex and remains an open problem. To address these issues, we provide first in this thesis a fairly generic and accurate model of caching nodes named MACS (Markov chain-based Approximation of Caching Systems) that can be adapted very easily to represent different caching schemes and which can be used to compute different performance metrics of multi-cache networks. We tackled after that the problem of cache resources allocation in cache-enabled networks. By means of our analytical tool MACS, we present an approach that solves the trade-off between different performance metrics using multi-objective optimization and we propose an adaptation of the metaheuristic GRASP to solve the optimization problem.

Keywords: Content-Centric Networking, Caching, Markov chains, Cache allocation, Multi-objective optimization, GRASP.

FIGURE 1 -

 1 FIGURE 1 -Le nommage du contenu en CCN.

FIGURE 2 -

 2 FIGURE 2 -Modèle d'un noeud CCN.

FIGURE 3 -

 3 FIGURE 3 -Traitement des paquets dans CCN.

Figure 4 -

 4 Figure 4 -Cisco Visual Networking Index: Global IP traffic evolution and forecast, 2015-2022.

Figure 5 -

 5 Figure 5 -Network architecture with the in-network caching capability.

Figure 1 . 1 -

 11 Figure 1.1 -ICN networking Overview.

Figure 1 . 2 -

 12 Figure 1.2 -Overview of PSIRP [22].

Figure 1 . 3 -

 13 Figure 1.3 -Routing scheme of NetInf [23].

Figure 1 . 4 -

 14 Figure 1.4 -Routing scheme of DONA [24].

Figure 1 . 5 -

 15 Figure 1.5 -Overview of CCN [12].

Figure 1 . 6 -

 16 Figure 1.6 -CCN packet types [12].

Figure 1 . 7 -

 17 Figure 1.7 -The naming of contents in CCN [12].

Figure 1 . 8 -

 18 Figure 1.8 -The node model in CCN [12].

  In a CCN network, each node is basically composed by three data structures (Figure 1.8):

Figure 1 . 9 -

 19 Figure 1.9 -Packets processing in CCN [25].

3 Figure 2

 32 Figure 2.1 -A Markov chain model of an LRU cache where the LCE strategy is adopted with R = 3 and N = 2.

Figure 2 . 2 -

 22 Figure 2.2 -Markov chain model for a content c r in an LRU cache.

  r), . . . . . . = . . . . . . . . . . . . = . . . . . .

1 - 1 -Figure 2 . 3 -

 1123 Figure 2.3 -General Markov chain model for a content c r in an LRU cache.

Figure 2 . 4 -

 24 Figure 2.4 -Cache hit ratio of contents with various popularities vs iterations number of the 2Q fixed-point solution under a single node (catalog = 20000, cache size = 200).

Figure 2 . 5 -

 25 Figure 2.5 -Cache hit ratio of contents with various popularities vs iterations number of the LCD fixed-point solution under a single node (catalog = 20000, cache size = 200).

Figure 2 . 6 -

 26 Figure 2.6 -Comparison of MACS and Che approximation in the case of a single cache.

  (cache size = 1%, α = 1.2)

Figure 2 . 7 -

 27 Figure 2.7 -Average hit rate vs content popularity with different parameters and using the LCE scheme.

Figure 2 . 8 -

 28 Figure 2.8 -Average hit rate vs content popularity with different parameters and using the 2Q scheme.

Figure 2 . 9 -

 29 Figure2.9 -Average hit rate vs content popularity with different parameters and using the LCD scheme.

Figure 2 . 10 -Figure 2 . 11 -

 210211 Figure 2.10 -Total hit rate of the network vs different configurations using the LCE scheme.

Figure 2 . 12 -

 212 Figure2.12 -Total hit rate of the network vs different configurations using the LCD scheme.

Figure 2 . 13 -

 213 Figure 2.13 -Cache hit ratio at different layers of the network using the LCE scheme.

Figure 2 . 14 -

 214 Figure 2.14 -Cache hit ratio at different layers of the network using the 2Q scheme.

  (cache size = 1.0%, α = 1.2)

Figure 2 . 15 -

 215 Figure 2.15 -Cache hit ratio at different layers of the network using the LCD scheme.

Figure 2 . 16 -

 216 Figure 2.16 -Total hit rate of the network with different parameters and various caching strategies.

Figure 2 . 17 -

 217 Figure 2.17 -Total hit rate at different layers of the network with different parameters and various caching strategies.

Figure 2 . 18 -

 218 Figure 2.18 -Cache hit ratio vs content popularity at different layers of the network with different parameters and various caching strategies.

Figure 2 . 20 -

 220 Figure 2.20 -Content provider load of the network with different parameters and various caching strategies.

. 3 ) 2

 32 Algorithm Application of GRASP to the cache allocation problem 1: function GRASP(Max_Iterations, λ) 2:

  end function In our case, n = T c and k = M , where the set of M non-negative integers has a sum equal to T c and represents the cache resources allocated to each node of the network. It is clear that |C n,k | is huge for high values of n and k. Therefore, we propose the use of the meta-heuristic GRASP to solve the cache placement problem (see the model (3.1)).

Algorithm 3 2 :S

 32 Construction phase 1: function Greedy_Randomized_Construction(λ) for i = 1, . . . , M do 3: x i ← 0; // Cache allocated for each node v i ← (x 1 , . . . , x M ); // Current solution 6: CS ← ∅; // Initial candidate set CS 7: while T c � = 0 do // Construction of the solution S 8:T c ← T c -P c 9:

20 :S

 20 ← {X * = (x * 1 , . . . , x * M )}; // S gets the partial solution X * 21:

Algorithm 4

 4 Local search phase 1: function Local_Search(S) 2:

do 3 :

 3 (x 1 , . . . , x M ) ← S; 4:

  then

9 :S

 9 ← (x 1 , . . . , x M )

  then

16 :S

 16 ← (x 1 , . . . , x M )

Figure 3 . 1 -

 31 Figure 3.1 -An example of a network architecture for content delivery with cacheenabled nodes.

35Figure 3 . 2 -

 32 Figure 3.2 -Comparison between the Pareto front and GRASP solutions under the LCE scheme.

Figure 3 . 3 -

 33 Figure 3.3 -Comparison between the Pareto front and GRASP solutions under the 2Q scheme.

Figure 3 . 4 -Figure 3 . 5 -

 3435 Figure 3.4 -Performance optimization vs total cache size using GRASP compared to the optimal values under the LCE scheme.

  Titre : Sur des modèles pour l'évaluation de performance et le placement des ressources de cache dans les réseaux multi-cache. Résumé : Au cours des dernières années, les fournisseurs de contenu ont connu une forte augmentation des demandes de contenus vidéo et de services riches en média. Compte tenu des limites de la mise à l'échelle du réseau et au-delà des réseaux de diffusion de contenu, les fournisseurs de services Internet développent leurs propres systèmes de mise en cache afin d'améliorer la performance du réseau. Ces facteurs expliquent l'enthousiasme à l'égard du concept de réseau centré sur le contenu et de sa fonction de mise en cache en réseau. La quantification analytique de la performance de la mise en cache n'est toutefois pas suffisamment explorée dans la littérature. De plus, la mise en place d'un système de caching efficace au sein d'une infrastructure réseau est très complexe et demeure une problématique ouverte. Pour traiter ces questions, nous présentons d'abord dans cette thèse un modèle générique et précis de cache nommé MACS (Markov chain-based Approximation of Caching Systems) qui peut être adapté très facilement pour représenter différents schémas de mise en cache et qui peut être utilisé pour calculer différentes mesures de performance des réseaux multicache. Nous avons ensuite abordé le problème de l'allocation des ressources de cache dans les réseaux avec capacité de caching. Moyennant notre outil analytique MACS, nous présentons une approche permettant de résoudre le compromis entre différentes mesures de performance en utilisant l'optimisation multi-objectif et nous proposons une adaptation de la métaheuristique GRASP pour résoudre le problème d'optimisation. Mots clés : Réseau centré sur le contenu, Mise en cache, Chaînes de Markov, Allocation de caches, Optimization multi-objectif, GRASP.

  System assumptions . . . . . . . . . . . . . . . . . . . . . . . . . 95 2.2 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . 96 2.3 Solving cache allocation problem using GRASP . . . . . . . . . 98 2.3.1 Mono-objective GRASP . . . . . . . . . . . . . . . . . . 98 2.3.2 Multi-objective GRASP . . . . . . . . . . . . . . . . . . 3 Performance evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Model configuration . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Model results and analysis . . . . . . . . . . . . . . . . . . . . . 4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Le nommage du contenu en CCN. . . . . . . . . . . . . . . . . . . . . . 2 Modèle d'un noeud CCN. . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Traitement des paquets dans CCN. . . . . . . . . . . . . . . . . . . . . . General Markov chain model for a content c r in an LRU cache. . . . . . 2.4 Cache hit ratio of contents with various popularities vs iterations number of the 2Q fixed-point solution under a single node (catalog = 20000, cache size = 200). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Cache hit ratio of contents with various popularities vs iterations number of the LCD fixed-point solution under a single node (catalog = 20000, cache size = 200). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Average hit rate vs content popularity with different parameters and using the LCE scheme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8 Average hit rate vs content popularity with different parameters and using the 2Q scheme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.9 Average hit rate vs content popularity with different parameters and using the LCD scheme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.10 Total hit rate of the network vs different configurations using the LCE scheme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.11 Total hit rate of the network vs different configurations using the 2Q scheme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	LIST OF FIGURES
	1
	4	Cisco Visual Networking Index: Global IP traffic evolution and forecast,
	Conclusion 2015-2022.	113
	1 Overview . . Publications	119
	Bibliography	121
		1.3	ICN proposals . . . . . . . . . . . . . . . . . . . . . . . . . . . .
			1.3.1	Publish Subscribe Internet Routing Paradigm . . . . . .
			1.3.2	Network of Information . . . . . . . . . . . . . . . . . .
			1.3.3	Data Oriented Networking Architecture . . . . . . . . .

Introduction 1 Context of the work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Motivations and contributions . . . . . . . . . . . . . . . . . . . . . . . . 3 Thesis outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Background 1 Information-Centric Networking . . . . . . . . . . . . . . . . . . . . . . . 1.1 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 ICN description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.4 Content-Centric Network . . . . . . . . . . . . . . . . . 2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Dynamic content popularity . . . . . . . . . . . . . . . . . . . . . 2.2 Caching from an economic point of view . . . . . . . . . . . . . . 2.3 Caching in wireless networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Network architecture with the in-network caching capability. . . . . . . . 1.1 ICN networking Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Overview of PSIRP [22]. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Routing scheme of NetInf [23]. . . . . . . . . . . . . . . . . . . . . . . . 1.4 Routing scheme of DONA [24]. . . . . . . . . . . . . . . . . . . . . . . . 1.5 Overview of CCN [12]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 CCN packet types [12]. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7 The naming of contents in CCN [12]. . . . . . . . . . . . . . . . . . . . . 1.8 The node model in CCN [12]. . . . . . . . . . . . . . . . . . . . . . . . . 1.9 Packets processing in CCN [25]. . . . . . . . . . . . . . . . . . . . . . . 2.1 A Markov chain model of an LRU cache where the LCE strategy is adopted with R = 3 and N = 2. . . . . . . . . . . . . . . . . . . . . . . . 2.2 Markov chain model for a content c r in an LRU cache. . . . . . . . . . . 2.3 2.6 Comparison of MACS and Che approximation in the case of a single cache. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 2.12 Total hit rate of the network vs different configurations using the LCD scheme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  Comparison between the Pareto front and GRASP solutions under the LCE scheme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 3.3 Comparison between the Pareto front and GRASP solutions under the 2Q scheme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 3.4 Performance optimization vs total cache size using GRASP compared to the optimal values under the LCE scheme. . . . . . . . . . . . . . . . 107 3.5 Performance optimization vs total cache size using GRASP compared to the optimal values under the 2Q scheme. . . . . . . . . . . . . . . . . 107LIST OF TABLES1 Un exemple d'une table PIT. . . . . . . . . . . . . . . . . . . . . . . . . . 2 Un exemple d'une table FIB. . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 An example of a CCN PIT. . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 An example of a CCN FIB. . . . . . . . . . . . . . . . . . . . . . . . . . .

	FIB	ACRONYMS Forwarding Information Base IRM Independent Reference Model
	FIFO	RR	First In First Out Random Replacement
	LRU	ICN LFU	Information-Centric Networking Least Recently Used Least Frequently Used
	TTL	PSIRP 2Q	Publish Subscribe Internet Routing Paradigm Time-To-Live Two Queue
	LCE	NetInf UGC	Network of Information Leave Copy Everywhere User Generated Content
	LCD	DONA VoD	Data Oriented Networking Architecture Leave Copy Down Video on Demand
	CDN	CCN GRASP	Content-Centric Network Content Delivery Network Greedy Randomized Adaptive Search Procedure
	NFV	NDO MEC	Named Data Object Network Function Virtualization Multi-access Edge Computing
	QoS	RN PoP	RendezVous Node Quality of Service Point of Presence
	ILP	TN RCL	Topology Node Integer Linear Programming Restricted Candidate List
	BN CDNaaS	Branching Node CDN as a Service
	VNF	FN	Forwarding Node Virtual Network Function
	QoE	NRS	Name Resolution Service Quality of Experience
	NBR MACS	Name Based Routing Markov chain-based Approximation of Caching Systems
	ISP	RH	Resolution Handler Internet Service Provider
	CP	CS	Content Store Content Provider
	PIT ARPU	Pending Interest Table Average Revenues Per User

2.16 Total hit rate of the network with different parameters and various caching strategies. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.17 Total hit rate at different layers of the network with different parameters and various caching strategies. . . . . . . . . . . . . . . . . . . . . . . . 2.18 Cache hit ratio vs content popularity at different layers of the network with different parameters and various caching strategies. . . . . . . . . 2.19 Average distance reduction ratio of the network with different parameters and various caching strategies. . . . . . . . . . . . . . . . . . . . . . . . 2.20 Content provider load of the network with different parameters and various caching strategies. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 An example of a network architecture for content delivery with cacheenabled nodes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 3.2 2.1 Summary of the notations. . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Hit ratio accuracy comparison (in %) between different models of a 2Q single cache under the IRM model with a Zipf's distribution parameter α = 0.8. Simulations are based on 10 runs of 10 3 × R requests with a warm-up period of 33 %. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Cache allocation solutions using GRASP with two separate evaluation functions when LCE is used. . . . . . . . . . . . . . . . . . . . . . . . . 108 3.2 Cache allocation solutions using GRASP with two separate evaluation functions when 2Q is used. . . . . . . . . . . . . . . . . . . . . . . . . . 109 3.3 Cache allocation solutions using GRASP with weighted combined evaluation function when LCE is used. . . . . . . . . . . . . . . . . . . . . . 109 3.4 Cache allocation solutions using GRASP with weighted combined evaluation function when 2Q is used. . . . . . . . . . . . . . . . . . . . . . . 110

TABLE 1 -

 1 Un exemple d'une table PIT.

	Noms des contenus	Faces entrantes
	ccn :/spotify.com/music1.mp3	301
	ccn :/irisa.com/documents/doc1.docx	201,203
	ccn :/youtube.com/videos/video1.mp4	102,105
	...	...

2.1 Modèle d'un noeud CCN

Dans un réseau CCN, chaque noeud est essentiellement composé de trois structures de données (voir Figure

2

) : -Le Content Store (CS) : le CS est une mémoire tampon qui fournit la fonction de mise en cache dans le réseau en sauvegardant des copies des données qui circulent afin d'optimiser les performances du réseau (minimiser la latence, réduire la surcharge du réseau, etc.). -La table PIT (Pending Interest Table) : elle contient deux types d'informations (voir Table 1) : les noms des contenus dans les messages d'intérêt reçus et les faces entrantes associées (les faces jouent un rôle similaire aux interfaces dans le réseau IP). Une table PIT a deux rôles. Le premier consiste à garder la trace des intérêts transférés en attente d'un paquet de données retourné, en enregistrant le nom du contenu demandé et la face associée. Le deuxième rôle est d'éviter de transmettre plusieurs intérêts qui demandent le même contenu ; lorsqu'un noeud CCN reçoit de la part de différentes interfaces plusieurs messages d'intérêt qui demandent le même contenu, ces paquets d'intérêt seront regroupés en une seule entrée dans le PIT et seul le premier sera acheminé.

TABLE 2 -

 2 Un exemple d'une table FIB.Dans les réseaux CCN, seuls les paquets d'intérêts sont acheminés et lorsqu'ils remontent vers des sources de données potentielles, ils laissent des traces dans les noeuds par lesquelles ils sont passés afin que les paquets de données puissent suivre pour atteindre leurs destinations.

	Préfixes	Faces sortantes
	ccn :/spotify.com/	101
	ccn :/irisa.com/documents/	204,206
	ccn :/youtube.com/videos/	301,302
	...	...

2.2 Le routage des paquets d'intérêts/de données dans les CCN Le traitement et le transfert de paquets dans les noeuds CCN s'effectuent comme suit : 1. Tout d'abord, un noeud CCN reçoit un paquet d'intérêt où le nom du contenu porté par ce paquet est vérifié dans le Content Store. 2. S'il y a un paquet de données dans le CS qui correspond à la demande, il est alors renvoyé par l'interface entrante de l'intérêt traité. Sinon, le nom du contenu est vérifié dans le PIT. 3. S'il y a une entrée correspondante dans le PIT, alors la requête est rejetée et sa face entrante est ajoutée à l'entrée PIT existante (agrégation des paquets Intérêt). Si ce n'est pas le cas, une nouvelle entrée est créée et les intérêts sont transmis sur la base des informations de la table FIB. 4. Lorsque le contenu de la requête est trouvé, le paquet de données suivra les traces laissées par les paquets d'intérêt afin d'atteindre la destination. 5. Une fois qu'un noeud reçoit un paquet de données, son nom de contenu est vérifié dans le CS. 6. S'il y a une correspondance, le paquet de données doit être écarté puisqu'il existe déjà dans le CS. Sinon, le nom du contenu est recherché dans le PIT.

  Lorsque le cache est plein, un élément est choisi par l'algorithme pour être rejeté. Nous pouvons citer les algorithmes de mise en cache First In First Out (FIFO), Least Recently Used (LRU), etc. -Politique de décision de caching : elle détermine quel contenu doit être mis en cache et dans quel noeud. En d'autres termes, un noeud doit décider quand il reçoit un contenu et selon la stratégie appliquée, s'il doit mettre les données en cache ou pas. -Placement des ressources de caches : la capacité du cache pouvant être al-Après avoir étudié comment placer et utiliser de façon efficace les ressources limitées de mise en cache de données dans un réseau distribué, nous avons proposé une modélisation du problème sous forme d'optimisation combinatoire, où notre outil MACS est utilisé pour évaluer les fonctions objectifs. Une application de la métaheuristique GRASP (Greedy randomized adaptive search procedure) sur notre modèle d'optimisation a été ensuite proposée et une analyse a été faite sur les différents résultats que nous avons obtenus. Cela nous a permis de mieux comprendre l'impact du placement des ressources du cache sur les performances du réseau et de voir comment notre solution peut s'adapter aux différentes contraintes et objectifs établies dans un système de multi-cache.

	modé-
	liser et analyser deux techniques de caching très intéressantes nommées 2Q
	(Two Queue) et LCD (Leave Copy Down) connues pour avoir un bon rapport
	efficacité/complexité. Les différents résultats générés ont montré la précision du
	modèle proposé sous différentes configurations du réseau et ils nous ont permis
	d'en savoir plus sur les stratégies de caching qu'il faudra utiliser pour avoir les
	meilleures performances.

louée à un noeud CCN étant limitée, le placement de cache consiste à étudier la répartition optimale des ressources de stockage entre les noeuds du réseau (ex : adopter une répartition équitable, donner plus d'espace de stockage aux routeurs du edge, etc).

Les travaux de cette thèse se sont concentrés sur les problèmes liés à la modélisation du cache et à l'allocation des ressources du cache dans les réseaux

CCN

et les réseaux multi-cache en général. Les contributions réalisées et validées peuvent être résumées comme suit : -Un modèle analytique basé sur les chaînes de Markov nommé MACS (Markov chain-based Approximation of Caching Systems) a été proposé. Il permet de modéliser la gestion des caches dans les réseaux CCN et d'estimer ainsi les performances du système. Ce travail couvre la technique de mise en cache LCE (Leave Copy Everywhere) et l'algorithme de remplacement de données dans le cache LRU. -Ensuite, une extension du modèle MACS a été développée. Elle nous permet de modéliser le mécanisme de caching dans le cas général afin de pouvoir analyser plusieurs stratégies de mise en cache intéressantes. Le modèle a été validé théoriquement et par simulation. Grâce à cet outil, nous avons pu -

Table 1 .

 1 ). -Pending Interest Table (PIT): it consists on a table that contains two types of information (see Table 1.1): the contents names within the received Interest messages and the associated incoming faces (the faces play a similar role of inter-1 -An example of a CCN PIT.

	CONTENT NAMES	IN FACES
	ccn:/spotify.com/music1.mp3	301
	ccn:/irisa.com/documents/doc1.docx	201,203
	ccn:/youtube.com/videos/video1.mp4	102,105
	...	...

faces in IP network). The PIT has two roles. The first one consists on keeping

Table 1 .

 1 2 -An example of a CCN FIB.

	PREFIXES	OUT FACES
	ccn:/spotify.com/	101
	ccn:/irisa.com/documents/	204,206
	ccn:/youtube.com/videos/	301,302
	...	...

track of the forwarded interests that are awaiting for a returned Data packet by saving the content name of the requested content and the associated face. The second role is to avoid forwarding multiple Interests that request the same content; when a CCN node receives from different faces several Interest messages that are demanding the same content, these Interest packets will be aggregated in one entry in the PIT and only the first one is routed. -Forwarding Information Base (FIB): The FIB is used to guide Interest packets toward potential sources of the requested data by saving in a table two types of information (see Table

1

.2): the content name (or the aggregated prefixes of the names) and the associated outgoing faces. A content having a list of outgoing faces means that a data can have multiple sources.

Table 2 .

 2 1 -Summary of the notations.

	Term	Desciption
	M	Number of nodes in the network
	R	Number of items in the catalog
	N	Cache size
	S	State space of an LRU cache model
	c r	Content with a popularity/rank r
	p r	Probability to request an item c r
	p � r α	Probability that a node receives an item c r in a multi-cache network Zipf law distribution parameter
	β(r)	Cache decision probability
	γ � s (r) π(r)	Probability of a content c r staying at the same position s of the cache Steady state distribution of the Markov chain
	P hit (r)

  MACS and CHE in terms of hit ratio of a single cache by comparing their outcomes to those obtained with the simulation tool ccnSim where the LCE scheme is used. The different plots exposed in Figure2.6 represent the hit ratio as a function of the cache size

				(e1/e2)
	100/1000	47.533 (1.312/0.161)	47.641 (1.543/0.064)	47.808 (1.899/0.415)
	100/10000	27.215 (0.665/0.391)	27.352 (1.172/0.109)	27.404 (1.364/0.302)
	1000/10000	52.720 (1.497/0.248)	52.596 (1.288/0.013)	52.746 (1.577/0.300)

(Figures 2.6(a)-2.6(b)-2.6(c)) and Zipf's parameter α (Figures 2.6(d)-2.6(e)-2.6(f))

Table 3 .

 3 1 -Cache allocation solutions using GRASP with two separate evaluation functions when LCE is used.

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Realistic network topologies can be also used as we did in[START_REF] Ben-Ammar | A Markov chain-based Approximation of CCN caching Systems[END_REF].

Weighted combined construction: f (X) = � k i=1 w i f i (X), where w i is the weight of the evaluation function f i (X).

are not served exclusively by the first level nodes, which will increase the average distance to get contents. We can also see from the graphs how the popularity of cached contents and their hit ratio decrease as we go up on higher levels of the network. This can be explained by the fact that caching contents that already exists on previous nodes makes them useless, which increases the replacement errors of items in the cache and, thus, decreases the nodes performance.

In Figures 2.19-2.20, we display the distance reduction ratio and the content provider's load using different caching schemes. The results of Opt presented in Figure 2.19 are obtained by setting as its objective the reduction of distance to retrieve contents, as we explained it previously. In Figure 2.20, Opt was configured to minimize the usage of the content provider, which is achieved by caching the most popular items as near as possible to it. In other words, Opt, in this case, consists on caching in the nodes located at 1-hop from the content provider the most N popular contents of the catalog (c 1 , . . . , c N ). Then, the second N most popular items (c N +1 , . . . , c 2N ) will be cached at the 2-hop nodes, etc. The graphs in Figures 2. [START_REF] Ben-Ammar | A versatile Markov chain model for the performance analysis of CCN caching systems[END_REF]

CONCLUSION 1 Overview

Over the past few years, the Internet usage has switched from a host-centric model to a content-centric approach, especially when dealing with content retrieval and data dissemination. This evolution is mostly driven by the increased popularity of contentoriented services, e.g., Peer-to-Peer file sharing, Video on Demand, video/audio streaming and social networks where users focus more on contents and not on the physical locations from which contents can be retrieved. These new trends in the Internet usage have raised important challenges in the current IP-based infrastructures, especially in terms of content delivery.

To address these challenges, the Content-Centric Networking has been proposed and emerged as one of the most interesting alternatives to the existing network architecture. Instead of the end-to-end principle, the CCN paradigm consists in redesigning the future Internet architecture by focusing on named data and leveraging new features, such as in-network caching, multipath connectivity and multicast data delivery. The content name in CCN is the only identifier of data, and the information exchanges based on establishing communication channels are abandoned.

The ubiquitous in-network caching certainly represents one of the most important features, which impacts directly the content delivery performance. In fact, CCN nodes are equipped with content store modules and have the ability to cache the data that passes by them. Therefore, the end-users' requests (known as interests in CCN), that are routed toward the Content Providers' servers, can be satisfied by the cached data at the intermediate nodes.

In-network caching as provided by CCN has brought a renewed interest in developing efficient tools to study the caching performance of interconnected systems of caches. This will help, indeed, in giving guidance and offering insights about the behaviour of a network of caches. Besides, this can be used to optimize the caching efficiency while increasing the overall system performance, which was the aim of this thesis work where the focus was on cache modeling and cache resources allocation in