Jonatan Krolikowski

Optimal Content Management and Dimensioning in Wireless Networks

The massive increase in cellular traffic poses serious challenges to all actors concerned with wireless content delivery. While network densification provides access to additional users, high-speed and high-capacity backhaul connections are expensive. Caching popular content at the network edge promises to offload user traffic from these congestion prone connections as well as from the data centers in the backbone network.

This thesis proposes a business model in which a mobile network operator (MNO) pre-installs and maintains caches at its wireless equipment (Cacheequipped Base Stations, CBSs). Memory space together with computational capabilities is then leased to content providers (CPs) that want to bring their content closer to the user. For a financial compensation, a CP can then offload traffic from its data center and improve user Quality of Service.

The CP makes content placement decisions based on user traffic and content popularity data. In the delivery phase, users can be served from the caches in case they are associated to stations that have the requested content cached. This work investigates three aspects of the proposed business model: The first research question focuses on user association as a central element to the edge caching scheme. Cache-aware user association policies can allow for users in coverage overlap areas to be associated to a CBS that holds the requested content rather than conventionally to the one that provides the strongest signal. The thesis proposes an original decentralized algorithm for user association called Generalized Bucket-filling that allows gains beyond iii iv maximizing the hit ratio. Performance metrics such as network throughput and load balancing of users among CBSs are taken into account. Experiments show that cache-aware user association a) increases the hit ratio b) without overloading single CBSs while c) providing high system throughput.

The second problem treated considers a single CP that needs to decide how much cache space to lease at each CBS for a fixed price, and what content to place. Its choices should be based on estimates of file popularity as well as MNO user association policy. The cache leasing and content placement problem is formulated as a non-linear mixed-integer problem (NLMIP). In its solution, the problem is separated into a linear discrete CP subproblem and a nonlinear continuous subproblem using Benders decomposition. The CP and the MNO cooperate, helping the CP to make optimal decisions that benefit both parties: The CP maximizes its savings from caching while the MNO can find the optimal cache price and receive the maximum financial compensation.

A third research question widens the focus to the interaction between several CPs and one MNO. Now, the MNO does not set a fixed price per memory unit but instead reacts to CP demands for memory space that depend on the savings they can achieve from caching. I would like to thank § my PhD co-advisor Dr. Anastasios Giovanidis for the ideas the discussions and for

Résumé en Français Introduction

Le Cisco Visual Networking Index prévoit que le trafic Internet mobile mondial sera multiplié par sept entre 2016 et 2021. Il devrait atteindre 48,3 EB par mois, passant de 7 à 17% du trafic IP total au cours de cette période.

Le trafic vidéo Internet mobile devrait même être multiplié par 9, ce qui représenterait 21% du trafic vidéo total. Comment faire face à l'immense défi posé par cette forte augmentation de demande ? Cette thèse explore caching (ou : mise en cache) à la bordure des réseaux cellulaires. Le contenu populaire est temporairement stocké sur les noeuds d'accès sans fil de manière distribuée afin de rapprocher le contenu à l'utilisateur.

La mise en cache est conditionnée par divers aspects techniques et économiques des réseaux sans fil actuels et futurs, posant ainsi des défis distincts aux systèmes de mise en cache traditionnels des réseaux fixes. Au coeur de cette thèse, un modèle économique est proposé qui prend en compte ces conditions particulières pour servir les intérêts de toutes les parties prenantes de la diffusion de contenu. Caching est un concept bien connu. Il semble naturel d'étendre le concept de stockage de contenu distribué aux réseaux sans fil.

Cependant, la diffusion par les réseaux sans fil présente un ensemble de défis particulier dans le contexte de caching. Ces défis, et comment les surmonter, sont le sujet de cette thèse. v vi

Portée de la thèse et contributions

Dans cette thèse, trois questions fondamentales de la mise en cache à la bordure du réseau sans fil sont abordées : dimensionnement et économie du cache, placement du contenu, et association des utilisateurs. L'accent est mis sur les aspects économiques de la mise en cache à la bordure du réseau cellulaire sans fil. Les caches aux BSs (stations de base, anglais: base stations) sont installés par le MNO (opérateur de réseau mobile, anglais: mobile network operator). Les BSs sont équipées (ou non) avec des liaisons de transport à grande vitesse et peuvent avoir des portées différentes, mais nous supposons qu'elles utilisent des technologies d'accès radio équivalentes. Le MNO propose aux CPs l'espace de cache disponible en échange de compensation financière (leasing à prix fixe ou à prix adaptatif). Les CPs sont supposés prendre des décisions rationnelles en ce qui concerne l'espace de cache acquis ainsi que le placement de contenu. Des fichiers entiers sont placés dans une phase de pré-extraction (pendant les heures creuses), car c'est possible qu'il n y a pas de connexions de transport à grande vitesse. Pour les décisions de placement raisonnables, nous supposons que nous disponons des données sour la densité du trafic et de la popularité du contenu. L'importance des stratégies d'association d'utilisateurs de l'MNO, qu'elles soient ou non réactives à caching, est un élément central des décisions du CP. L'hypothèse sous-jacente est que les utilisateurs dans des zones de chevauchement de couverture peuvent potentiellement être associés à l'une des stations de couverture, en tenant compte du compromis entre la disponibilité du contenu local et les conditions radio.

En particulier, les contributions de cette thèse sont: § La thèse propose et analyse un modèle économique pour la location de caches à la bordure du réseau aux CPs. De cette façon, on considère les incitations économiques liées à la mise en cache des contours qui vii conditionnent la viabilité du concept. § On étudie les politiques d'association des utilisateurs prenant en compte le cache. Lorsque des utilisateurs situés dans des zones de chevauchement de couverture peuvent être associés à n'importe quel CBS (stations de base avec cache, anglais: cache-equipped base station) couvrant, ils peuvent potentiellement accéder au contenu de plusieurs caches.

La thèse présente de nouvelles stratégies d'association d'utilisateurs prenant en compte le cache, qui permettent un compromis entre la force du signal et la disponibilité du contenu mis en cache. Les stratégies peuvent atteindre différents objectifs tels que l'équilibrage de la charge des CBSs ou la maximisation du débit. La thèse démontre que ces stratégies améliorent les performances de la mise en cache à la bordure du réseau sans fil. § Fondée sur une association d'utilisateurs prenant en compte le cache, cette thèse, à la connaissance de l'auteur, est la première à optimiser conjointement les décisions de location, d'emplacement de contenu et d'association d'utilisateurs sur la base de données de trafic et de popularité de contenu précises, en supposant que des fichiers entiers soient mis en cache. La politique de tarification optimale est déterminée, ce qui rend l'activité de mise en cache plus rentable pour le MNO. § L'influence de la concurrence entre plusieurs CPs sur la tarification du cache est explorée.

Résumé des Résultats

Dans une première étape en chapitre 4, l'association des utilisateurs prenant en compte le cache est examinée. Un algorithme efficace appelé Generalized Bucket-filling est développé pour le calcul de l'association des utilisateurs prenant en compte le cache optimisant différents critères de performance. viii Les principales conclusions de l'application de l'algorithme sont les suivantes: § L'association es utilisateurs prenant en compte le cache offre des grands avantages par rapport à l'association des utilisateurs classique pour un placement de contenu donné. En particulier, les mesures de performance telles que le taux de réussite ou le débit du réseau sont considérablement améliorés. § Les performances des associations des utilisateurs sont améliorées, en particulier si les CBS voisins stockent un contenu différent. § Lorsque l'objectif est l'équilibrage de la charge des utilisateurs parmi les CBS, il est possible d'atteindre un taux de réussite élevé sans surcharger les CBSs, en transférant le trafic supplémentaire vers les stations moins utilisées. § Les meilleures performances par rapport à l'association des utilisateurs sont obtenues lorsque le contenu est placé d'une manière qui anticipe l'association des utilisateurs. § L'association es utilisateurs prenant en compte le cache fonctionne mieux lorsque les stations voisines utilisent différentes bandes de fréquences, ce qui réduit l'influence de l'interférence.

Dans une deuxième étape, chapitre 5, un scénario est examiné dans lequel un MNO loue de la mémoire cache à un CP. Le problème de la location optimale de cache et du placement de contenu utilisant une association des utilisateurs prenant en compte le cache est décomposé en une partie MNO et une partie CP. La stratégie de location et de placement qui en résulte, qui optimise le CLCP (Cache Leasing and Content Placement problem) lorsque l'association des utilisateurs Opt-h est appliquée, est également appelée Opt-h. Des expériences montrent la supériorité de Opt-h par rapport aux décisions optimales de location de cache et de placement de contenu utilisants la stratégie d'association cache-inconsciente Closest. Les conclusions sont: § Le plus grand soient les zones de chevauchement de couverture des ix CBSs, est le plus élevé soit le prix de location du cache, le meilleur est la performance de Opt-h par rapport à Closest. § La location de cache et le placement de contenu suivant Opt-h fournit un catalogue de contenu mis en cache plus varié que Closest. § Le MNO peut identifier le point opérationnel de la tarification qui maximise ses revenus. Le prix optimal dépend du rayon de couverture des CBSs. § L'efficacité de la mise en cache à la bordure du réseau dépend des statistiques sur la popularité du contenu. Le plus les statistiques sont faussées vers moins de fichiers populaires, le plus la mise en cache est efficace. § Alors que la stratégie de mise en cache proposé dépend des statistiques sur la popularité du contenu, des petites inexactitudes statistiques n'ont que des effets mineurs sur l'efficacité de la stratégie. § La location et le placement basés sur Opt-h sont supérieurs à Closest,en particulier dans les scénarios dans lesquels l'interférences inter-cellule est réduite grâce à l'utilisation de bandes de fréquences orthogonales en stations voisines.

Au-delà des résultats de Chapitres 4 et ??, Chapitre 6 présente un moyen d'évaluer des scénarios dans lesquels plusieurs CPs disputent les ressources de cache d'un opérateur de réseau. Dans un tel scénario, les CPs peuvent agir en tant que preneurs de prix (price takers), en acceptant le prix de leasing indiqué par le MNO, ou ils peuvent anticiper le prix. Dans ce dernier cas, les CPs préemptent les réactions des CPs concurrents, supposant que l'opérateur MNO souhaite louer tout l'espace de cache disponible. Dans le cas où les CP anticipent les prix, tout équilibre du jeu résultant ne perd pas plus de 25% d'efficacité par rapport à l'optimum social.

x Chapter 1

Introduction

The Cisco Visual Networking Index [START_REF]Cisco visual networking index: Global mobile data traffic forecast update[END_REF] predicts that global mobile internet traffic will increase by factor seven between 2016 and 2021. It is expected to reach 48.3 EB per month, rising from 7 to 17 percent of total IP traffic in said period. Mobile consumer internet video traffic is even expected to grow by factor 9, leading to a 21 percent share of all video traffic. How can the immense challenge posed by this massively increased demand be met? This thesis explores wireless edge caching in cellular networks. Popular content is temporarily stored at wireless access nodes in a distributed fashion to bring the content closer to the user. Wireless edge caching is conditioned by various technical and economical aspects of current and future wireless networks, thus posing challenges distinct to traditional caching schemes in fixed networks. At the core of the thesis, a business model is proposed that takes these particular conditions into account to serve the interest of all stakeholders in wireless content delivery.

Caching is a well-known concept. It seems natural to extend the concept of distrubuted content storage into wireless networks. However, wireless delivery presents a particular set of challenges to caching. These challenges, and how to overcome them, are the subject-matter of this thesis. 1

Current and Future Wireless Networks

Backhaul connection of wireless access points is a bottleneck in content delivery, particularly with the introduction of heterogeneous networks or HetNets [START_REF] Di Renzo | Average rate of downlink heterogeneous cellular networks over generalized fading channels: A stochastic geometry approach[END_REF]. However, interference in the wireless channel is also a problem that comes from network densification. Spectral efficiency can be significantly enhanced with increased spatial reuse. This, however, comes at the cost of increased interference. On the other hand, interference can be reduced by avoiding the simultaneous use of frequencies in neighboring BSs when a user is located at the cell edge, i.e. potentially receiving the signal and the interference with similar channel gain.

Cloud radio access networks (C-RAN) are part of the future 5G architecture. In C-RAN, remote radio heads (RRHs) are controlled and coordinated by baseband units (BBUs) [START_REF] Niu | Ran architecture options and performance for 5g network evolution[END_REF][START_REF] Yang | When icn meets c-ran for hetnets: an sdn approach[END_REF]. In this context, the backhaul bottleneck is overcome via highspeed fiber connections between RRHs and BBUs. Placing caches at the BBUs allows cached content to be served no matter which subset of RRHs is actively participating in the transmission.

C-RAN promises to cut certain costs compared to similar coverage by MBSs: § Cooperative transmission schemes allow for the reduction of interference. § Centralization of computational capacities are more energy-efficient than distributed MBSs that each need their independent infrastructure.

Caching at the Edge

To introduce caches into wireless networks, the location of these caches within the networks needs to be decided. Consider a network transmitting content from a central content storage to a wireless user as can be seen in Figure 1.1.

The centralized storage is denoted by DC for data center. The content is delivered via an interface (www IF) to the wireless core network. From there, in a heterogeneous network, content can be delivered to the user equipment (UE) through different wireless access nodes: macro BSs (MBSs), small BSs (SBSs) or C-RAN (BBU and several RRHs).

Where should caches be installed? The following three possibilities are considered in the literature:

Core Network or Baseband Unit

Caching in the LTE core network using TCP redundancy elimination has been proposed in [WJP `13]. The advantage of caching deeper in the network is that users associated to several BSs can be routed to the cache to make use of the cached content. However, it also implies that the caches are located behind the backhaul connection. Thus, such caches are not able to alleviate the expected bottleneck link of wireless networks. When caches are installed at the baseband unit in C-RAN architecture, they are closer to the user but as a consequence potentially accessible for fewer users.

Mobile Devices

Caching at mobile devices has been proposed in [START_REF] Golrezaei | Femtocaching and device-to-device collaboration: A new architecture for wireless video distribution[END_REF] making use of device-to-device (D2D) communication. Caching on mobile devices has the advantage of potential individualized caching strategies. D2D content transmission futhermore allows wider use of these caches without use of the BS backhaul connections. Still, it needs to be taken into account that device caches need to be comparatively small, and D2D file transfer depends on the relatively weak signal emitted by mobile user devices and is exposed to mobility of both the sending and the receiving device.

Base Stations

The original work suggesting to cache at the BSs is FemtoCaching by Shanmugam et al [SGD `13], i.e. edge caching. This work proposes to install wireless distributed caching helpers. These helpers are wireless access points equipped with large cache memory but have no high-speed backhaul connection. The main advantage of edge caching is that the fixed BS infrastructure allows for the installation of large inexpensive caching infrastructure that can serve large numbers of users and, in case the user-requested content is cached, offloads traffic from the scarce backhaul resources. The drawbacks of edge caching are that (1) traffic in the coverage area of BSs is difficult to predict and (2) conventional user association does not take caching decisions into account.

Note that the installation of caches at BSs changes their functionality. Conventionally, they are able to measure wireless channel conditions as well as to initiate, accomodate and manage communication requests. When equipped with caches, a controller is needed that can identify the requested content and determine whether it is cached. This controller can either be placed at the BS itself or deeper in the network, potentially even at the CP's content storage. When the controller induces content delivery from the cache, a mechanism is necessary for the packetization as well as for the encryption of the content.

Edge Caching Benefits

This work proposes the installation of caches at base stations (or, in the following equivalently: wireless access nodes), turning them into Cacheequipped base stations (CBSs). The main reasons for this decision are: § Load reduction on upstream infrastructure: Cache hits at CBSs reduce the load on upstream infrastructure. This includes the backhaul connections that are identified as probable bottlenecks in content delivery but also the CPs' content storage entities. Redundant transmissions can be avoided on long network paths: over time, multiple requests for the same content can be served from the cache while the delivery from the source to the cache only needs to occur once. § Reliability: In case of overload or other system failure at the central content storage, some system performance can be maintained. At the same time, base stations provide more reliable data transmissions than D2D connections in case of caching on user equipment. § Delay reduction: The closer to the user content is cached, the lower is the delivery delay, thus improving QoS. Especially when BSs are not equipped with high-speed backhaul connections, local caches provide significant delay reduction. While caching on user equipment reduces the physical distance even further, the delivery delay via D2D connections is dependent not only on the position and mobility of the receiving user but also on the sender. § Multi-coverage benefits: Particularly in dense urban networks, coverage areas of CBSs overlap. Given a cache-aware user association policy, users in multi-coverage areas (see Figure 1.2) potentially have access to all covering caches. Then, a diversified content in neighboring stations is particularly useful. § Localization: Caches at the wireless edge serve only a relatively small area, thus traffic is spatially fine grained. The caches can thus adapt better to local demands. While device caching is ultimately more fine grained, CBSs allow the use of content to several users at the same location. § Adaptation of Video Quality: Videos are usually offered in different image qualities that are provided in different chunks of files. The quality of the delivered video is adapted to the user channel quality and congestion. By storing a video in different quality levels in a cache, a user with good channel conditions can enjoy high-quality video without the need of high-speed download through the backhaul. When the channel quality decreases, the video quality adapts.

Edge Caching Challenges

There are several challenges that need to be faced to put edge caching into practice. § Cache Dimensioning and Economics: Caches need to be installed, physically maintained and supplied with energy. The example of Netflix Open Connect Appliances (OCA, see Section A.3.2) show an example in which a CP maintains caching infrastructure. At BSs, however, physical space is limited and generic boxes are not as easily placed.

This suggests that edge caches should be installed and managed by MNOs. The optimal dimensions of edge caches are then to be determined by the MNOs. Bigger caches can contain more content and thus increase the hit ratio, but also incur higher financial and energy costs.

While it is possible to operate edge caches in a content-agnostic way, e.g. by applying Last Recently Used (LRU) as a replacement policy, pervasive encryption of communication between clients and CPs make the involvement of CPs necessary. Thus, an MNO maintaining caches needs to decide which CPs should participate in the cache operation, and to which price. In short, a business model for edge caching in which MNOs offer cache space to CPs needs to be developped. § Content Placement: The usefulness of caches is maximized when they store content that will likely be downloaded. Thus, the question what content should be placed in the caches is central to the effectiveness of caching.

There are two different notions how to approach this problem: In the online caching model, when a cache miss occurs, the request is forwarded to the central storage. When the requested file passes through the network node while transmitted to the user, it is cached (or not).

The policy by which it is decided if the file is cached and which file is evicted from the cache instead is called replacement policy. The most commonly known policy replaces the Least Recently Used (LRU) file.

Prefetching means placing content into caches in a placement phase that is planned to occur before the content delivery. The basis for the placement decisions is expected traffic as well as content popularity.

The caches are filled in off peak hours, and the cached content is not changed during peak hours due to a lack of highspeed backhaul connections. The simplest placement policy is to cache the globally or locally most popular content. However, the opportunity to potentially access more than one cache allows for more involved content placement policies.

Finding an efficient content placement/replacement scheme is essential for the viability of edge caching. § User Association: For cache hits to occur, user requests need to be routed to caches that hold the content. For users that can only associate to one CBS, conventionally the one with the strongest signal, the effect of caching depends only on the content placement decisions at that particular cache. Particularly in dense heterogeneous networks, however, several wireless access nodes provide sufficient signal strength. Thus, users potentially can be associated to any such node. Then, a cache-aware user association policy can associate users to CBSs that cache the requested content, trading off signal strength for cache hit.

Another aspect that user association policies can take into account is load-balancing since the radio resources of access nodes are limited.

Proposed user association schemes such as coordinated multi-point help realize such user association.

In conventional web caching, users can be routed to caches using TCP/IP. In contrast, wireless edge caching requires users to be associated to a particular node to access its cache. This is a process that precedes the establishment of a TCP/IP connection. Thus, novel cache-aware user association policies need to be explored to bring edge caching to its full potential. § Traffic and Popularity Measurement: A good prediction of user traffic is basic for caching business decisions: The more users are likely to access a cache, the greater the variety of content requests, thus rendering a bigger investment in the cache more reasonable. Furthermore, in case content is placed in a prefetching phase, popularity data is required to make optimal placement decisions. Content popularity varies both in time and space. Machine-learning problems such as user type classification and demand prediction are promising related subjects: They are already applied to learn the preferences of individual users. This can be extended to spatio-temporal content popularity in wireless networks. § Mobility: Users are typically not static in wireless networks. This implies that radio conditions change, and handoffs between radio access points occur. The impact of these handoffs on caching decisions need to be explored. Furthermore, user mobility is of particular interest in device caching schemes. One promising research direction are ad-hoc networks of cache-equipped vehicles. § Fractional Caching: In conventional caching schemes, entire files are cached or the files might be partitioned into smaller chunks. Netflix and Youtube partition their videos into partial files of down to 2 seconds each. In this sense, the splitting of content into various files is already common practice [MSR `17]. Caching, for example, the first segments of videos can be a reasonable strategy when users regularly do not watch videos in their entirety. Following this logic, the total transmitted load can be reduced by partitioning content and delivering only the parts that are actually required.

In these cases of uncoded caching, the non-cached content entirely needs to be retrieved from upstream. Broadcast opportunities can be exploited when several requests for the same content coincide. With coded caching schemes, broadcasting is advantageous even if users simultaneously request different content. This can be achieved through coordinated prefetching of partial files and computational effort retrieving information from coded information transmission. § Privacy and Verification: Since May 2018, the General Data Protection Regulation (GDPR) is in effect in the European Union (EU). It requires strong measures to protect private customers's personal data.

It is built on "principles of data protection by design and data protection by default" [START_REF] Regulation | 679 of the European Parliament and of the Council of 27 April 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data, and repealing Directive 95/46/EC (General Data Protection Regulation)[END_REF]. At least for the EU market, this implies that the user behaviour in relation to a CP should not be known to any third party. In parcatice, a large share of data connections are end-to-end (E2E) encrypted. The challenge for caching schemes is to enable such secure and private connections while retaining the benefits that arise from caching.

Another aspect of private connections between user and CP is the verification of user identity for the distribution of restricted content. Especially subscription based video and audio distribution platforms such as Netflix and Spotify need to make sure that only their clients have access to their content. § Net neutrality: Net neutrality "prohibits Internet service providers from speeding up, slowing down or blocking Internet traffic based on its source, ownership or destination" [START_REF] Krämer | Net neutrality: A progress report[END_REF]. While the United States administration has recently distanced itself from the idea of net neutrality, EU law implements some aspects of it [Par15]. There is a legal debate if MNOs can be seen as regular Internet Service Providers (ISPs) and thus, if the net neutrality principle is applicable to wireless content delivery [START_REF] Yoo | Wireless Network Neutrality: Technological Challenges and Policy Implications[END_REF]. While a detailed legal analysis of the viability of the proposed business model needs to be performed before its implementation, such deliberations go beyond the scope of this thesis.

An Example

The complex relationship between the three aspects installation of caches, content placement and user association is illustrated by the simplified network shown in Figure 1.3. From the bottom, several CP users request content denoted by letters A to D. The dashed lines connect to the respective BS with the strongest signal. Some users are located in coverage overlap areas. In these cases, the dotted lines connect to the BSs that provide a weaker but sufficient signal for the users to associate to. The BSs 2.1 to 2.4 are connected via backhaul links to the inner network node 1.1. Node 1.1 has a connection to the backhaul data center in which files A to D are stored. Each hop that content traverses adds to the download delay.

Assume first that a large cache is installed at node 1.1. Then, if all content A to D is stored there, the traffic from the depicted users can be offloaded from the central storage. Associating all users to their strongest node will provide each of them with the best radio conditions. If there are no issues with regards to congestion in the backhaul connection or the wireless channel, this is the optimal user assocation.

If, however, the backhaul connections are prone to congestion due to a lack of capacity, the cache at node 1.1 becomes less useful. Consider, thus, as a second example, caches installed at the BSs 2.1 to 2.4. Then, some users can be served from these edge caches and offload traffic from the backhaul connections. The MNO's user association policy now becomes important. § All users are associated to the BS that provides the strongest signal. In the context of this work, such user association policy is called closest BS or simply Closest. Then, to achieve 100% hit ratio, 6 cache units are required (assuming unit-sized content). If only 4 cache units are available, a hit ratio of no more than 2/3 can be accomplished. § Cache-aware association. If users can be associated to any covering BS, a hit ratio of 100% can be achieved already with 4 cache units.

Scope of the Thesis and Contributions

In this thesis, three core questions of edge caching are addressed: cache dimensioning and economics, content placement and user association. The focus lies on the economics of edge caching in a wireless cellular network.

Caches are installed at the BSs by the MNO. The BSs may or may not be equipped with high-speed backhaul links and might have different ranges, but are assumed to use equivalent radio access technology. The MNO offers the available edge cache commodity to CPs for financial compensation (leasing for fixed price or price-adaptive). CPs are assumed to take rational decisions with regards to the acquired cache space as well as content placement. Entire files are placed in a prefetching phase (in off-peak hours) since high-speed backhaul connections might not be present. For good placement decisions, spatio-temporal traffic and popularity data are assumed to 1.6. SCOPE OF THE THESIS AND CONTRIBUTIONS be given. The significance of MNO user association policies, cache-aware or not, is a center-piece to the CP decisions. The underlying assumption is that users in coverage overlaps may potentially be associated to any of the covering stations, taking the trade-off between local content availability and radio conditions into account. Mobility is only implicitly taken into account, e.g. by assuming a correlation of content popularity in neighboring areas.

In particular, the contributions of this thesis are: § This thesis proposes and analyzes a business model for the leasing of edge caches from MNOs to CPs. This way, economic incentives of edge caching are considered that are a condition to the viability of the concept. § Cache-aware user association policies are studied. When users in the overlap of coverage areas may be associated to any covering CBS, they potentially can access the content of more than one cache. The thesis introduces new cache-aware user association policies, trading off signal strength and availability of cached content. They can achieve different objectives such as load-balancing or throughput maximization.

It is shown that these policies improve the perfomance of edge caching. § Based on cache-aware user association, this thesis to the best of the author's knowledge is the first to jointly optimize cache leasing, content placement and user association decisions based on fine grained traffic and content popularity data and assuming that entire files are cached. The optimal pricing policy is determined, making the caching business most profitable for the MNO. § The influence of competition between multiple CPs on cache pricing is explored.

Structure of the Thesis

The remainder of the thesis is structured as follows.

Chapter 2 provides an overview over the relevant literature on the wireless edge caching as it relates to the edge caching challenges outlined in Section 1.4.

Chapter 3 identifies the interests and incentives of the actors that participate in edge caching. The economic as well as technological conditions of edge caching are taken into account. A business model is proposed in which an MNO gives cache access to one or several CPs. A CP should rationally weigh the benefits from edge caching, e.g. traffic offloading from its own content storage, against the financial costs. It is examined how the MNO's user association policy is central to the CP decision.

Chapter 4 investigates user association in edge cache-equipped wireless networks. The problem of associating users to stations with given cached content is modelled as a (generally) non-linear Network Utility Maximization (NUM) problem by introducing a utility function per station. Choosing the utilities as concave functions may optimize the hit ratio while putting soft limitation on the served user load. Load-balancing among CBSs is of importance since the radio resources are limited, particularly when it is assumed that some CBSs can only serve a small number of users. The addition of weights for user-CBS associations allows for performance criteria such as system throughput.

A novel algorithm to optimally solve this problem in a distributed way is developped, called (Generalized) Bucket-filling. The calculations can be executed on the individual stations requiring a limited amount of information exchange. The resulting user association is shown to improve the desired 1.7. STRUCTURE OF THE THESIS objective over cache-oblivious association policies.

Chapter 5 In Chapter 5, the work focuses on the problem of cache leasing and content placement taking user association into account. A mixed integer NUM problem is formulated that aims to maximize the CP's caching benefits given the user association policy.

As solution technique, Generalized Benders decomposition of the NUM into Master and Slave sub-problems is applied which converges to the global optimum. One of its main advantages, aside optimality, is that it allows the separation of the user association problem (Slave) from the cache leasing and content placement problem (Master) in an iterative solution process.

The technique is completely original for solving NUM edge caching problems with non-linear utilities.

Extensive evaluation of the optimal leasing and content placement for linear and concave objective functions is provided. The results are compared to known content placement policies under cache-aware and cache-oblivious user association.

The evaluations can derive the optimal price that the MNO should set for its revenue maximization. Furthermore, they can suggest appropriate investment budget for the CP to attain a target hit ratio.

Chapter 6 develops a model for the allocation of cache space to several CPs. As preliminary results, the model is restricted to equal partition of cache space at each CBS with relaxed integrality constraint. A game is designed that helps allocate the memory even when the CPs anticipate MNO pricing. An algorithm towards a high quality Nash equilibrium is outlined. Lagrangian based solution does not converge to the global optimum due to weak duality (see p. 143 in [START_REF] Bertsimas | Optimization over integers[END_REF]) and other solution techniques are necessary to solve the problem optimally. In [START_REF] Araldo | Stochastic dynamic cache partitioning for encrypted content delivery[END_REF] and [START_REF] Dehghan | Sharing LRU cache resources among content providers: A utility-based approach[END_REF], the authors investigate blind cache splitting between several CPs. The partitioning of the caches remains under the control of the internet service provider, while the CPs are allowed to establish secure connections between caches and users. `17] develop a cache leasing system for small base stations within the framework of contract theory without considering optimal content placement. In the context of Information Centric Networking (ICN), joint cache partitioning and resource allocation has been proposed recently [CDL `17].

Liu et al. [LLS

Content Placement

Question: Which content should be placed into edge caches? There are two notions of how caches should be updated: Online Caching and Prefetching.

Online Caching

In 2002, Che et al analyzed hierarchical web caching systems with Poisson arrival rate and a Zipf-like content popularity [START_REF] Che | Hierarchical web caching systems: Modeling, design and experimental results[END_REF]. They derive an approximation (called Che approximation) for the expected time that content remains within the cache before being replaced under the LRU replacement policy, and subsequently approximate the hit ratio. This implies that LRU can be approximated by assigning an appropriate Time-to-live (TTL) to each cached file that is independent of the other files in the cache [START_REF] Fofack | Analysis of ttl-based cache networks[END_REF]. Another well-known cache replacement policy is Least Frequently Used (LFU)

[MWZ `17].

Online caching policies are evaluated with regard to knowledge of arriving request sequences. LRU optimizes the hit ratio under adversarial finite request sequences [START_REF] Dd Sleator | Amortized efficiency of list update and paging rules[END_REF] While the structure of the incoming content requests should be known in order to select the optimal replacement policy, online caching does not require knowledge about the specific content to be cached. If, however, the caches are not equipped with high-speed connections to the core network but rather are deployed at wireless helper cells, content placement policies are required that preempt what content should be cached. `13]) assumes a bipartite connectivity graph of potential user associations. The aim is to place content such that user delay is minimized. Baştug et al. [START_REF] Baştug | Cache-enabled small cell networks: Modeling and tradeoffs[END_REF] randomly place CBSs on the plane. They use metrics of outage probability and average delivery rate to analyse the performance of caching the most popular content. Poularakis, Iosifidis, and Tassiulas maximize in [START_REF] Poularakis | Approximation algorithms for mobile data caching in small cell networks[END_REF] the hit ratio by means of integer optimization. In their work, an approximation scheme for hit ratio maximization is provided. Naveen et al. [NMB `15] provide an optimal placement and user association scheme with fractional content placement. Deghan et al. [DSJ `15] also develop an approximation algorithm for the content placement problem minimizing net-work delay. In [START_REF] Giovanidis | Optimal geographic caching in cellular networks[END_REF], B laszczyszyn and Giovanidis develop a probabilistic content placement policy which maximizes the hit ratio by profiting from multi-coverage. Tuholukova, Neglia and Spyropoulos [START_REF] Tuholukova | Optimal cache allocation for femto helpers with joint transmission capabilities[END_REF] investigate optimal content placement for joint transmission schemes in small cell networks. Alfano et al. [START_REF] Alfano | Content-centric wireless networks with limited buffers: When mobility hurts[END_REF] include power control issues in this general problem.

Prefetching

Jaffres-Runser and Jakllari [START_REF] Jaffrès-Runser | Pcach: The case for precaching your mobile data[END_REF] performed field experiments that showed significant periods in which users are not connected to WiFi and only have cellular connection available. With the aim to avoid cellular downloads, they develop a data-driven algorithm that individually predicts what and how much content to cache on the wireless equipment during WiFi time.

Routing and User Association

Starting from the original FemtoCaching paper [SGD `13], multi-coverage is exploited: When a user can be associated to more than one cache, the available cached content is the union of the content of the covering caches.

Since users conventionally associate to the wireless node with the strongest signal, novel association techniques are required to take full advantage of multicoverage opportunities.

In the existing literature, user association is handled in different ways: In [START_REF] Borst | Distributed caching algorithms for content distribution networks[END_REF], the authors use caching to minimize bandwidth cost in a tree-like network. The routing decisions of users are, however, independent of each other. The authors of [SGD `13] associate users to any covering station that caches their requested content without balancing the traffic loads. In other works [START_REF] Giovanidis | Optimal geographic caching in cellular networks[END_REF][START_REF] Baştug | A transfer learning approach for cache-enabled wireless networks[END_REF], users are associated to the closest base station, not knowing if the requested content is stored in the cache or not. The authors of [START_REF] Poularakis | Approximation algorithms for mobile data caching in small cell networks[END_REF] The relationship between the popularity and location of online videos is studied in [START_REF] Brodersen | Youtube around the world: Geographic popularity of videos[END_REF]. The study finds that Youtube videos are essentially local: More than 50% of Youtube videos have more than 70% of their total views in a single country. Furthermore, it is found that video popularity expands as a wave: Video views immediately grow in the focus location and only then they expand across other regions. Li et al follow a more fine-grained approach studying how content popularity depends on the specific location within a big city such as Shanghai [LXL `14]. They find, for example, that the concentration of video popularity becomes higher as the region is closer to downtown. The prediction of video popularity based on historical information given by earlier popularity measures is proposed in [START_REF] Pinto | Using early view patterns to predict the popularity of youtube videos[END_REF].

Traffic and Popularity Measurement

In [START_REF] Xu | Forecasting popularity of videos using social media[END_REF], social media data are used to predict content popularity.

User location and mobility statistics combined with mobile application usage and the history of past cache queries are exploited for popularity estimates in [START_REF] Lim | Characterizing and predicting mobile application usage[END_REF]. A transfer learning-based approach is proposed to obtain an estimate of the popularity profile [START_REF] Bharath | Learning-based content caching with time-varying popularity profiles[END_REF]. Using ideas of Gibbs sampling, Chattopadhyay, Blaszczyszyn and Keeler [START_REF] Chattopadhyay | Gibbsian on-line distributed content caching strategy for cellular networks[END_REF] learn content popularity profiles in order to derive optimal content placement.

Mobility

Building on the original FemtoCaching paper, Wang, Song and Han [START_REF] Wang | Dynamic femtocaching for mobile users[END_REF] consider the constantly changing topology of wireless networks in terms of which users are covered by access nodes. The mobility-aware cache update problem is solved suboptimally. In [START_REF] Poularakis | Code, cache and deliver on the move: A novel caching paradigm in hyper-dense small-cell networks[END_REF], Poularakis and Tassiulas model user mobility as random walks. A mobility-adapted placement policy offloads traffic from a macro base station to cache-equipped small base stations. The authors of [GXF `14] follow a similar approach, naming their content placement policy "MobiCacher". Chen et al [CHH `17] add the aspect of green content delivery to mobility-aware content placement.

The opportunities of D2D communication of devices equipped with cache memory are exploited by Lan et al [START_REF] Lan | Device-to-device offloading with proactive caching in mobile cellular networks[END_REF]. Traffic is offloaded from the macro base station through proactive caching on mobile devices. Wang et al [START_REF] Wang | Mobility-aware caching in d2d networks[END_REF] follow a similar approach. They find that very slow and very fast moving users should cache the most popular files while mid-speed users should cache less popular content. `16] apply mobile device caching to connected cars. `12] propose the use of vehicles equipped with large caches for massive data transmissions. Lee et al [LGP `16] investigate Fog Computing opportunities in vehicular networks as Vehicular Fog.

Mahmood et al [MCC

Gorcitz et al [GJS

Fractional Caching

Some works on wireless caching consider fractional caching, in other words: fractions of files are stored instead of entire files. In some cases, partial caching is considered since it simplifies the content placement problem particularly if it is formulated as a mathematical optimization problem (e.g.

[NMB `15]).

From an information-theoretic point of view, the fundamental limits of caching have been analyzed making use of the idea that files can be partitioned into subfiles [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF]. Its basic premise is that broadcast opportunities can be exploited even if different users simultaneously request different files. Users cache subfiles on their devices in a prefetching phase following the centralized coded caching scheme that depends on the user configuration. In the delivery phase the users simultaneously request content. For any configuration of the requested files, a bitwise XOR combination exists from which each user can reconstruct its request. Transmitting this bit combination over the common (perfect) channel significantly saves wireless resources in comparison to uncoded file transfer through the global caching gain.

Coded caching is regarded in several works on wireless caching, mostly as a theoretical bound that is compared with uncoded caching gains, see for example [SGD `13].

While centralized coded caching can obtain optimal caching gains in theory, there are practical drawbacks: The problem is largely intractable, even though there exist 12-approximations. More importantly, the caching scheme assumes that files can be partitioned into sets of subfiles depending on the configuration of users present. Furthermore, a known user configuration in the prefetching phase is in conflict with the mobility inherent in wireless communication.

Privacy

Caches can be managed and trusted by a CP, as is the practice of Netflix OCAs [PBL `16, Izr16] (see also Section A.3.2). In this case, the cache is enabled to be the endpoint of secure E2E connections. Network management such as cache-aware user association can in this case only be performed if at least one of the two ends, user or CP, actively contributes.

If the caches are not managed and/or trusted by the CP, several attacks on communication privacy are identified in the literature. Acs et al [ACG `13] find as a major threat to user privacy the possibility of an adversary to measure round-trip time (RTT) to a local cache that operates with dynamic caching. Since the RTT to the cache is shorter than the one to the remote server, the adversary can then infer if content has been recently requested, assuming a replacement policy such as LRU. Several techniques that provide tradeoffs between privacy and latency are proposed to maintain lower latency through caching with privacy protection. Mohaisen et al [MZS `13] follow a similar approach, extending the model from a single cache-equipped router to a multi-hop path. Lauinger et al [LLR `12] propose replacement strategies that avoid caching of privacy-sensitive content.

Leguay et al [START_REF] Leguay | Cryptocache: Network caching with confidentiality[END_REF] develop a protocol that allows caching of encrypted content through pseudo-identifiers in order to balance privacy with caching performance. This technique opens the possibility for an MNO to identify and deliver encrypted files without knowing their content.

Chapter 3

Leasing and Managing Edge Caches 3.1 A Business Model

Stakeholders

The three main parties that are stakeholders in wireless content delivery are MNOs, CPs and users.

A user subscribes to the services of an MNO and pays a subscription fee that arises per time period (e.g. per month) or per transmitted data volume.

When the user is within the coverage area of one of the MNO's BSs and requests some CP's content, he/she expects content delivery via the wireless channel with satisfactory QoS, e.g. low latency and high throughput. At the same time, a certain level of data privacy needs to be provided that is related to E2E encryption of the connection to the respective CP.

CPs offer content to users. In exchange, users may have to pay a subscription fee and/or generate CP income by accepting the CP displaying advertisement and collecting data about user behaviour. Apart from the investment into production or licensing of the actual content, CPs also need 25 to pay for the storage of their content, be it in their own data centers or in CDNs. As has been shown above, an ever-increasing share of content delivery occurs to wireless users. This implies that CPs need to adapt to the wireless cellular networks to keep their customers satisfied.

An MNO builds and maintains a wireless cellular network. Its main source of income is user subscription fees. Since MNOs are in competition to each other, they have an incentive to provide good QoS to the users. This implies a good management of resources such as LTE resource blocks or backhaul capacity as well as sufficient investment into the network infrastructure to keep up with increasing demands.

Edge Cache Leasing

This thesis proposes the following business model for edge caching. § An MNO installs cache memories at the BSs of its network, making them Cache-equipped BSs (CBSs). Computational capacity contolling each cache is installed locally at the caches. The construction and maintenance of caches is left to the MNO since all hardware in a wireless network are maintained by the MNO. § The memory space at the CBSs is to be leased to one or several CPs for a certain time period. The cache management is thus in the hands of a CP. This includes the capacity to establish a secure connection between the cache and a user. The CPs are the owners of the content.

Secure connections between user and CP can be provided when the CP can encrypt its content at the caches. § The MNO chooses a pricing mechanism, either a fixed price (in case memory is leased to one CP) or a price-adapting scheme (several CPs).

The CPs financially reward the MNO in return for the service of using the caches since edge caching a) generates savings for a CP by offloading traffic from its central content storage and b) provides better user QoS. § Once a CP has leased memory space, it can place its own content into them in a prefetching phase. The basis of the content placement decisions are spatio-temporal traffic and popularity data. The CPs are the only entities that have traffic and popularity data to their disposal. § Content is transmitted to users in the delivery phase. Whenever a user is associated to a CBS that caches the requested content, it can be delivered directly from the cache. The MNO performs cache-aware or cache-oblivious user association. Cache-aware implies that, for users that may potentially be associated to more than one CBS, the placed content is taken into account. Cache-aware user association brings edge caching to its full potential. This business model is represented in Figure 3.1.

MNO and CP decisions

Based on the previous discussion, we summarize the actions taken by the MNO and the CP. The MNO makes three strategic decisions: MNO-1) How much storage space to install at each CBS? MNO-2) In case of fixed price: Which price to set for the leasing of one cache unit? For multi CP scenarios: Which mechanism is to be used to allocate cache space to CPs? MNO-3) Which user association policy to pursue?

The CP wants to lease sufficient cache space and place its content so that the savings exceed the cache leasing costs.

The two types of decisions that the CP takes are: CP-1) How much cache space to lease from the MNO at each CBS? CP-2) Which content to place into the leased caches?

For the decisions to be optimal, they need to be based on the estimated spatio-temporal popularity of the CP's content. Demand statistics evolve over time. The popularity data that are significant for the CP decisions are the aggregate data for the time window in which cache leasing and content placement decisions are fixed.

Interplay of User Association and Content Placement

The amount of savings generated by a cache leasing and content placement decision depends on the user association policy that the MNO declares. To understand this, we present the two perspectives: a) Given a fixed content placement over all the caches in the CBSs, different user associations lead to different hit ratios. Consider a policy where the users are associated to the station with the strongest signal without taking content placement into account. Such association will result in a lower hit ratio than an alternative policy which considers cache placement information. b) For a given user association policy, the CP can make leasing and placement decisions in a way that the hit ratio is maximized.

Instead of the hit ratio, other performance criteria can also be taken into account.

Performance Criteria

Cache-aware user association can be designed by various possible performance criteria.

The hit ratio or hit probability is the ratio of cache-related traffic, i.e. users that find their requested content cached, and total traffic. Since every cache-hit offloads traffic from the backhaul, the deeper network as well as the CP infrastructure, a maximum hit ratio is desirable. When user association aims to maximise hit ratio, users may suffer bad channel conditions. This problem can be addressed by associate users to CBSs with the aim to maximize network throughput, i.e. the sum of the throughput achieved by each individual user. This criterion incentivizes to associate users to CBSs that provide good radio conditions together with the requested content.

Load balancing should be performed so that wireless nodes with popular content are not be overloaded with cache-related traffic. At the same time, other nodes with less popular content could be underused. A solution for such imbalance can be to limit the maximum cache-related load per wireless node and redistribute, when possible, the remaining load among neighboring nodes.

User Association

We have seen that user association plays a critical role in defining the approporiate CP decisions and in determining the system performance. This can be better explained through the example shown in Figure 3.2. In a random wireless network, unit-size content is placed into space-limited caches according the content placement policy Random. This means that, at each cache, every k-subset of files uniformly has the same probability to be placed.

The file popularity follows a Zipf distribution. Now we compare two different user association policies on the same content placement. Opt is cache-aware user association where users will be associated to any covering CBS caching their content, if such CBS exists. Closest associates strictly to the closest station -or to the station that provides the best radio conditions. Fig. 3.2 now shows that Opt user association achieves a significantly higher hit ratio than Closest. Particularly, this is due to the fact that users in coverage overlap areas gain access to all covering caches with Opt association. With Closest, every user only has access to one cache.

User Association Policies

The following user association policies are considered in this work. They either do or do not take CP content placement decisions into account. Thus, they are either cache-oblivious or cache-aware.

Cache-oblivious Policy

Closest or Standard Association. The MNO associates each wireless user to the geographically closest CBS. This is the conventional policy in cellular networks that only takes signal quality (through distance) into account. In this case, users can be served locally only if their requested content is stored in that particular cache.

Cache-aware Policies

Closest Available or Closest Replica. Any user is associated to the closest covering CBS that caches the requested content.

Unsplittable or Geographically determined association. Users in the same geographic vicinity requesting the same content are associated to the same CBS. If users in an area are potentially associated to more than one station caching the content, it is selected apriori.

Opt-h. With Opt-h, association is a function of the placement decisions.

Different performance criteria that determine Opt-h association decisions are discussed in Section 3.3. The h in Opt-h refers to a savings function that measures said performance criterion, as will be discussed later. Such MNO association policy allows for more user requests to be served by the caches. If users can be associated to any single wireless node among those with sufficient signal quality, then each user has potential access to the union of sets of files cached in all covering stations. The MNO should associate users to CBSs in such a way that content requests are matched to the cached content.

As an example for the different association policies, consider the following scenario that is also depicted in Figure 3.3: Example 1. A user is located in a wireless network such that he/she is covered by the CBSs L(eft), C(enter), and R(ight). His/her received signal is best from CBS L, but the requested content is not cached. The signal from C is weaker and several users are associated to it already. On the other hand, the requested content is cached. An even weaker (but still sufficiently strong) signal is received from R which also stores the content but has less traffic load.

With Closest association, the user will receive the content from CBS L, even though the content has to be retrieved from the CP's upstream storage.

Closest Available associates to C since it has the strongest signal of the CBSs caching the content. Possible congestion issues are not taken into account. Opt-h will associate to C or R since the content is stored in these caches. Depending on the performance criterion, the decision might be taken in favor of the better signal of C or the lower congestion at R.

A further discussion on the practicalities of this matter follows in Section 3.7. The modelling and analysis of Opt-h vs Closest association in cached wireless networks is developped in Chapter 4.

Cache Leasing and Content Placement

Chapter 5 of this thesis develops a cache leasing and content placement policy that significantly improves on Random content placement. It will be based on the knowledge of the MNO user association policy: When a CP knows how the MNO will associate users to CBSs, it can make its decisions in a way that maximizes its performance criteria. The performance criteria considered in this work are discussed in Section 3.3.

MNO-CP Cooperation

In order to make optimal leasing and content placement decisions, a CP relies on the MNO's pre-announced user association policy. Of particular interest is the policy Opt-h that associates users according to a performance criterion.

In case Opt-h is applied, this thesis assumes that the MNO's and the CP's performance criteria for user association are the same. This should be part of the contract between MNO and CP.

Opt-h belongs to the cache-aware user association policies. Any cacheaware policy needs cooperation between the MNO and the CP. This is due to practical issues related to user privacy. Today's wireless systems do not allow an MNO to be aware of what content a user demands, and all information in encrypted as has been discussed in Section 1.4. However, the MNO is able to associate users in a cache-aware manner with guidance from the CP.

There are several ways in which this can be implemented: The MNO can initially associate each user to a large set of covering stations but only serve the user from a CBS having the content. Alternatively, associate each user to a single CBS and redirect afterwards to a station with the content. In both cases, after initial association, the CP becomes aware of the user request and communicates the appropriate serving station to the MNO.

Chapter 4 Cache-aware User Association

This chapter contains research from the published papers [START_REF] Krolikowski | Fair distributed user-traffic association in cache equipped cellular networks[END_REF], [START_REF] Krolikowski | Optimal cache leasing from a mobile network operator to a content provider[END_REF] and [START_REF] Krolikowski | A decomposition framework for optimal edge-cache leasing[END_REF]. In Section 4.2, the model is based on [START_REF] Krolikowski | Fair distributed user-traffic association in cache equipped cellular networks[END_REF]. The weighted savings function (4.3) comes from [START_REF] Krolikowski | Optimal cache leasing from a mobile network operator to a content provider[END_REF]. While the solution in 4.4 is based on [START_REF] Krolikowski | Fair distributed user-traffic association in cache equipped cellular networks[END_REF], the generalized solution presented here is developped in [START_REF] Krolikowski | A decomposition framework for optimal edge-cache leasing[END_REF]. The evaluation for load balancing in Section 4.5 comes from [START_REF] Krolikowski | Fair distributed user-traffic association in cache equipped cellular networks[END_REF]. Section 4.6 is unpublished work.

Introduction

User association is a central topic in cache-equipped wireless networks as is shown in Section 3.4. This chapter analyzes the benefits of cache-aware user association. A CP has leased caches at the CBSs of an MNO's network and placed content into them. Users arrive in the network and request content. The MNO's task is now to associate the users to the CBSs. A basic assumption is that the bottleneck in wireless content delivery is the backhaul connection. For delay and backhaul congestion reasons, it is always preferable to associate users to a CBS that caches the requested content if it provides sufficent signal strength. Such traffic is called cache-related.

In practice, user requests arrive in real-time and the association decisions 35 need to be taken immediately. Here, aggregate user association is considered.

The question is rather: "How many users will be associated to the CBSs after a time period, and to what effect?" rather than "Which CBS should the next incoming user request be associated to?". The main reason for this approach is that user association is seen here as a part of the cache leasing and content placement problem (CLCP, see Chapter 5). There, good cache leasing and content placement decisions are based on aggregate user traffic and populartity data. Thus, the expected aggregate user association needs to be calculated that follows the MNO's user association policy.

The large problem size when calculating user association for an entire cellular network makes centralized calculation of the optimal solution difficult.

Following the idea that Fog computing capabilities are deployed with the caches, we develop a distributed solution algorithm for the user association problem that requires limited data exchange between the computing entities. This way, scalability of the solution is provided.

Different user association policies have been introduced in Section 3.5. This chapter examines the advantages of cache-aware user association Opt-h over the cache-oblivious policy Closest as well as other cache-aware varieties Closest Available and Unsplittable. Opt-h has its name since it optimizes user association with regards to a certain performance criterion (see Section 3.3), and each such criterion is measured by a related savings function h. The criteria that will be used in this chapter are hit ratio, loadbalancing and throughput maximization. Content Popularity: For each region s P S Π and each content f P F, N s,f denotes the number of users in s requesting f . The content popularity vector is N " pN s,f q sPS Π ,f PF . The statistics of content popularity are considered static during a time window. The information on file popularity is considered locally available at each covering CBS. Note that the model does not assume spatially uniform traffic and that the vector N is general.

System Model and Problem Statement

In the context of this work, we are only interested in the users who find their request cached at the CBS they are associated to (cache-hit traffic). The association vector of cache-hit users to the CBSs is y " py m,s,f q mPM,sPS Π pmq,f PF , where y m,s,f represents the expected user traffic from region s requesting content f and associated with CBS m. S Π pmq is the subset of regions whose users can potentially be associated to m according to Π. The vector y has fractional non-negative entries.

User association is unique in the sense that a single user cannot be served by two or more CBSs simultaneously. The total population N s,f can be distributed among the CBSs Mpsq, and some of it is potentially not associated to any CBS at all. Thus,

ÿ mPMpsq y m,s,f ď N s,f , @ s P S Π , f P F. ( 4
y m,s,f ď N s,f x m,f , @ m P M, s P S Π pmq, f P F. (4.2)
This constraint set relates MNO association variables with CP cache placement decisions.

Savings Functions and Optimization Problem

As will be shown, every user association policy discussed here can be expressed as maximizing a savings function h under the aforementioned constraints. The savings function takes the user association vection y as input and maps it on the savings that can be achieved from it. Each of the savings functions is of the general form hpyq "

ÿ mPM U m pv w m pyqq, (4.3)
where each U m is a monotonously increasing, continuously differentiable and concave function that takes the weighted traffic volume at CBS m v w m pyq as its argument. Formally the latter is defined as

v w m pyq " ÿ sPS Π pmq ÿ f PF w m,s,f y m,s,f , (4.4)
with weights w m,s,f that are specific to users from region s requesting content f associated to CBS m. The vector of weights is w. The unweighted cacherelated traffic volume at m, in which all w m,s,f " 1, is denoted by v m pyq.

For a content placement vector x and a user association policy Π, the user association vector y Π pxq is found by solving the following problem:

pUA-Πq y Π pxq " arg max yPY Π hpyq s.t. (4.2).
Note that, due to the restrictions on h given in (4.3), UA-Π is a convex optimization problem in the context of network utility maximization (NUM).

Savings Functions

While this formulation is applicable to all user association policies that are taken into account, it particularly refers to the Opt-h policy where the savings function mirrors the different performance criteria (for introduction of association policies see Section 3.5). Before discussing the appropriate savings functions for the different performance criteria of user association policy Opt-h, we show that the optimization formulation UA-Π can also derive the user associations Closest and Unsplittable.

Policy i: Closest

For user association policy Π " Closest, finding the user association y Π pxq is trivial. The solution is simply the covered users within the Voronoi cell of each CBS that request cached content. This can be expressed as the solution of the problem UA-Π by choosing the savings function hpyq proportional to the total sum of cache-related traffic:

hpyq " ÿ mPM v m pyq.

For every region, all users located in it can only be associatiated to one unique CBS. Choosing the savings function this way assures that all users are associated that can find their requested content. Note that users that do not find their content cached are not counted into savings due to constraint (4.2).

Policy ii: Unsplittable

With the Unsplittable policy, there are regions in the overlap of several coverage areas. For each region and every content, association to a covering CBS is chosen apriori in case one of them caches the content. This association can be induced as the result of the problem UA-Π by introducing weights w m,s,f for each CBS m, the corresponding covered regions s and content f . while w m,s,f ă 0 leads to the association vector of the Unsplittable policy.

Policy iii: Hit Ratio Maximization

To maximize the hit ratio with Opt-h, the savings function can be chosen simply as the sum of the entries in the (unweighted) association vector y:

hpyq " ÿ mPM ÿ mPM v m pyq. (4.5)
Policy iv: Load Balancing

When the objective of Opt-h user association, the aim is both to put a soft limit on the maximum traffic associated with a CBS and balancing the cache-related traffic volume among the CBSs. This approach also guarantees the usefulness of each cache.

We can choose the utility function such that for volumes greater than a certain V m , the derivative of U m becomes close to zero. Such soft limitation entails that it is not beneficial to further route users to this station.

The overall objective is to maximize the sum of utilities subject to routing constraints, resulting in the savings function

hpyq " ÿ mPM U m p ÿ mPM v m pyqq. (4.6)
Traffic association is balanced if the available resources are used in a fair way. Some notions of fairness are max-min, α´and proportional fairness. Each of them is achieved by appropriate choice of the utility functions (see [START_REF] Kelly | Charging and rate control for elastic traffic[END_REF][MW00]). E.g. for proportional fairness, utilities could be chosen as (weighted) logarithms, depending also on the soft limit we want to achieve.

Policy v: Wireless Throughput

The weights can represent the downlink throughput between a user and a

CBS (other work with the same objective is [LBZL17]

). For such a weights choice, the channel quality between m and s is a constant value h m,s that depends on a reference distance and the path loss exponent. The emitted power level of m is denoted by p m and the noise level by σ 2 . Then, the signalto-interference-plus-noise ratio (SINR) of users in region s when associated

to covering CBS m is SINR s pmq " p m h m,s ˆÿ m covers s m‰m p mh m,s `σ2 ˙´1 , (4.7)
where we assume that the interference from CBSs not covering s is negligible.

For the downlink transmission from CBS m to region s, the throughput is equal to w m,s " B log 2 p1 `SINR s pmqq rin bits/secs (4.8)

s 1 s 2 s 3 s 4 s 5 s 6 s 7 where B [Hz] is a chunk of bandwidth allocated to each served user. The total service bandwidth per CBS is equal to the product of B [Hz] times the users routed to the CBS. Using the value (4.8) as weights, UA-Π takes into account that it is favorable for a CBS to serve users with good radio conditions in order to use its resources effectively. Note that, we can also define other weights that depend on file f , for example w m,s,f " gpw m,s {b f q,

where gp¨q is some increasing function and b f is the file size. Such expression would then evaluate throughput over the requested file-size, giving larger weight w to (and thus favoring) smaller file sizes.

]) together with zero leasing costs, the user association in FemtoCaching can be subsumed in out more general framework.

Solution

The user association problem UA-Π is a non-linear fractional optimization problem. As such, there are standard methods, such as gradient descent, that can solve it "out of the box". Here, we develop an algorithm to optimally solve the problem in a distributed way. The calculations can be executed on the individual stations requiring a limited amount of information exchange, thus making use of the Fog computing capabilities that come with the caches.

Simplification of the Problem

As a first step, we simplify the notation. Tuples of region s and file f are called region-files q " ps, f q if there is a CBS m covering s with f in its cache, i.e. Qpmq :" tps, f q | s P Spmq, f P F, x m,f " 1u. The index q will be used as equivalent to the double index s, f in this section, e.g. we write N q instead of N s,f . We denote the complete set of region-files by Q. Not included in Q are requests for files not stored in a covering CBS. The subset of CBSs that cache content f and cover region s is denoted by Mpqq Ď M. Conversely, Qpmq Ď Q are the region-files which can be served by the cache of m. Note that this definition renders constraint (4.2) redundant for y m,s,f " 0 for all ps, f q R Qpmq.

Recall that utility functions U m are monotonously increasing. Therefore, in an optimal solution of the routing problem, all traffic of q P Q is served from the cache of a CBS: For each region-file q " ps, f q P Q there is a station covering s with f in its cache. As a consequence, all user requests related to region-files in Q (and only they) are cache-related traffic. Thus, constraint (4.1) is always fulfilled with equality in the optimum. Overall, UA-Π is equivalent to the problem max yě0 hpyq s.t. ÿ mPMpqq y m,q " N q , @ q P Q with y m,s,f " 0 for all ps, f q R Qpmq.

Dual method for the Augmented Lagrangian

The UA-Π problem is solved using the dual method on the Augmented Lagrangian (see [START_REF] Bertsekas | Parallel and Distributed Computation: Numerical Methods[END_REF], Section 3.4.4). We use the Augmented instead of the regular Lagrangian to achieve a distributed solution. In our case, the regular Lagrangian is not appropriate since it is not strictly concave in the primal variables and hence the primal solution is not unique. This creates conflicts when different stations compete for the same users and convergence cannot be guaranteed. Like the regular Lagrangian, the Augmented one relaxes constraints of the UA-Π problem and introduces a price λ q for the violation of each constraint. The difference between them is an additional quadratic term penalizing the violation of each constraint together with a factor ą 0.

This penalty guarantees strict concavity in the primal variables. Denoting the Augmented Lagrangian by L p q , we get

L p q py, λq " ÿ mPM U m pv w m py m qq `ÿ qPQ λ q pN q ´ÿ mPMpqq y m,q q
´ 2 ÿ qPQ pN q ´ÿ mPMpqq y m,q q 2 , (4.10) where λ :" pλ q q, q P Q is the price vector. The domains of the dual variables are λ q P R for all q P Q, since the respective constraints are equalities.

The Duality theorem (see [START_REF] Bertsekas | Parallel and Distributed Computation: Numerical Methods[END_REF], Appendix C) applies, which means that the duality gap is 0, and the dual method can be used. The objective function of the dual problem is D p q pλq :" max 0ďymďNm,mPM L p q py, λq " L p q py ˚pλq, λq, where

y ˚pλq " arg max 0ďymďNm,mPM L p q py, λq (4.11)
is the primal maximum of (4.10) for a given price vector λ. The dual problem is then defined as pUA-dualq min

λPR Q D pλq.
Starting from an arbitrary initial dual vector λp0q, the dual vector is iteratively updated according to λ q pt `1q " λ q ptq ´ ´ÿ mPMpqq N q ´ym ,q pλptqq ¯, (4.12)

where the steplength ą 0 is the penalty used in (4.10). The convergence of this method is well known (see [START_REF] Ruszczyński | On convergence of an augmented lagrangian decomposition method for sparse convex optimization[END_REF] or Section 3.4.4 of [START_REF] Bertsekas | Parallel and Distributed Computation: Numerical Methods[END_REF]).

For practical implemetation issues of each update step of the region-file price λ q , q P Q, only the primal solutions of the covering CBSs need to be known. Thus, for a distributed implementation, exchange of such information among neighboring stations is sufficient.

The next subsection presents the distributed solution for the primal problem (4.11), which needs to be found for every iteration of the dual algorithm.

Distributed solution for the primal problem

The solution for (4.11) is unique since the domain of y is convex and compact and, for any fixed feasible vector λ, the Augmented Lagrangian L p q is strictly concave. We use the Diagonal Quadratic Approximation Method (DQA) [START_REF] Ruszczyński | On convergence of an augmented lagrangian decomposition method for sparse convex optimization[END_REF] to derive seperate problems which can be solved by each cache. A limited amount of exchanged information between neighboring caches is required.

The DQA overcomes the problem that the objective function L p q py, λq of (4.11) is not easily separable among the variables related to the different CBSs, since it contains quadratic terms combining different variables y m,q (see (4.10)). To achieve this, we introduce the functions

L p q m : R Qm ˆRř m Q m RQ Ñ R for all m P M:
L p q m py m , ỹ, λq :" U m pv w m py m qq `ÿ qPQpmq λ q y m,q

´ 2 ÿ qPQpmq p N m q pỹq ´ym,q q 2 , where N m q pỹq :" N q ´ř mPMpqq m‰m ỹ m,q is the number of requests in q not associated with caches other than m in the routing vector ỹ " pỹ m,q q, m P M, q P Qpmq which is here seen as a parameter. The primal problem to be solved by each cache m is defined as

pUA-primal-mq max 0ďymďNm L p q m py m , ỹ, λq. (4.13) Since L p q
m py m , ỹ, λq is strictly concave in y and the domain is compact, UA-primal-m has a unique solution which we call ỹm . The vector containing the solutions of UA-primal-m for all caches is ỹ˚.

The DQA method consists of parallel execution of UA-primal-m at the caches with consecutive update of the vector ỹ in the fashion of a nonlinear Jacobi algorithm. It produces a succession of vectors ỹp0q, ỹp1q, ỹp2q, . . .. Starting from some given vector ỹp0q, the vector ỹpτ `1q is defined as the convex combination of ỹpτ q and ỹ˚p τ q. Given a constant 0 ă α ď 1, we get ỹpτ `1q " ỹpτ q `αpỹ ˚pτ q ´ỹpτ qq.

(4.14)

In [START_REF] Ruszczyński | On convergence of an augmented lagrangian decomposition method for sparse convex optimization[END_REF] it is shown that the DQA method converges. Observe that the convergence depends on the uniqueness of the primal solutions ỹ˚p τ q. For every update (4.14), each station only requires results from its neighboring stations that cover a common region-file.

Separated Primal Solution

Before stating the separated primal problem, we again simplify the notation for this section. Since the problem is separated by CBS, we omit the index m, writing y q instead of y m,s,f , y instead of y m , and Q instead of Qpmq. The separated primal problem is then

y ˚" arg max 0ďyďN
Up ÿ qPQ w q y q q `ÿ qPQ λ q y q ´ 2 ÿ qPQ p Nq ´yq q 2 " arg max 0ďyďN U ´ÿ qPQ w q y q ¯´ÿ qPQ " p {2qy 2 q ´aq y q ‰ (4. 15) where Nq " p N m q pỹq is the remaining user population not served by other CBSs in the previous DQA step, and a q :" λ q ` Nq . The equation to (4. 15) comes from the development of the quadratic term and from omitting the additive constants which do not affect the optimal choice of values for the variables. In the following, we will denote the objective function of (4.15) by gpyq.

Problem (4.15) is a convex optimization problem. Methods for solving this type of problem such as the gradient descent method are well known.

However, their speed of convergence can be an issue. Here, we present a problem specific solution method that does not depend on convergence and solves (4.15) exactly and efficiently. Our method is based on the insight that the optimal solution lies within a one-dimensional subspace of its |Q|dimensional domain. The following theorem characterizes this subspace.

Proposition 1. Let y ˚be defined as in (4.15). Then, there exists ν ˚ě 0 such that for all q P Q y

q " $ ' ' ' ' & ' ' ' ' % 0, ν ˚ď β q
N q , ν ˚ě pw q{w q qN q `βq f q pν ˚q, otherwise (4.16) with β q " a q ´pw q{w q qa q . (4.17)

In the above, q :" arg max qPQ a q {w q and f q pνq " pw q {w qq ν ´pw q {w qqβ q .

In other words, the optimal vector y ˚can be determined by finding the optimal value ν ˚. This fact considerably reduces the complexity of finding y ˚. Before the formal proof of Proposition 1, consider the following illustration. The value ν ě 0 can be interpreted as the water level in a scenario in which |Q| buckets of varying width w q {w q and height pw q{w q qN q are positioned at different bottom levels. When the water level is below or exactly at bottom level β q of bucket q, the bucket is empty. Otherwise, the bucket is filled up to level ν unless the water level is higher than the upper edge of the bucket at pw q{w q qN q `βq . In that case, the bucket is filled to its capacity of N q . In between, the volume in the bucket is exactly f q pνq. This observation leads to an algorithm solving (4.15) efficiently: Starting from water level ν " 0, let the water level increase. The water volumes represent the variables in y. The algorithm (see Algorithm 1 for detailed presentation) terminates when the optimal value ν ˚is reached. This is true when the maximum of the objective function of (4.15) is reached or when all buckets are full. An example for such an arrangement of buckets is shown in Fig. 4.3. Each bucket q is placed with its bottom at level β q and has a width of w q {w q, a height of pw q{w q qN q and unit depth. The buckets are filled to a common level -or until they are full. The algorithm halts when further increasing the water level ν starts decreasing the objective value.

a) b) c) d) e) β 1 = 0 β 2 1 2 3 w 1 w 2 N 2 + β 2 w 1 w 3 N 3 + β 3 N 1 β 3 1 2 3 1 2 3 1 2 3 1 2 3
Proof of Proposition 1. Note first that f q pyq is invertible with f ´1 q pyq " pw q{w q qy `βq (4.18)

and f ´1 q is non-decreasing. The value f ´1 q pyq represents the reference water level ν if y is the non-zero water volume in bucket q. Let ŷq :" w q y q for all q P Q. Then, the following problem is equivalent to (4. q ´aq wq ŷq ı and N :" pw q N q q, q P Q.

Note that N q ą 0 for all q and thus the upper and the lower bound of y q cannot be fulfilled with equality simultaneously. The KKT conditions can thus be written in a compact way: There exist γ q P R for all q P Q such that B B ŷq ĝpŷ ˚q ´γq " 0 (4.19) for all q P Q where

γ q " $ ' ' ' ' & ' ' ' ' %
ě 0, if ŷq " w q N q ðñ y q " N q ď 0, if ŷq " 0 ðñ y q " 0 " 0, otherwise (4.20) and B B ŷq ĝpŷq " U 1 ´ÿ qPQ ŷq ¯´ w 2 q ŷq `aq w q .

For any p, q P Q, (4.19) implies that the following equation holds:

´ w 2 q ŷq `aq w q ´γq " ´ w 2 p ŷp `ap w p ´γp since the term U 1 ´řqPQ ŷq ¯is contained in both derivatives. A calculation resubstituting y p " ŷp {w p and y q " ŷq {w q results in y q " f q ˝f ´1 p py p q ` pw q { qpγ p ´γq q. Now, we will find a p P Q such that ν ˚:" f ´1 p py p q yields (4.16). Then, y q " f q pν ˚q `wq pγ p ´γq q (4.21)

Case 1: D p P Q with 0 ă y p ă N p . Define ν ˚:" f ´1 p py p q. Note that, in this case, γ p " 0 such that for all q P Q:

y q " f q pν ˚q ´wq γ q . (4.22)
With this equation, we deduce (4.16) for any q P Q: Firstly, if 0 ă y q ď N q `βq , then γ q " 0 follows from (4.20) and y q " f q pνq holds due to (4.22).

Secondly, if y q " 0, then γ q ď 0 by (4.20). Then (4.22) implies that f q pν ˚q ď y q " 0 which by definition of f q is true if and only if ν ˚ď β q . Lastly, if y q " N q , then γ q ě 0 by (4.20) and with (4.22): f q pν ˚q ě y q " N q . By definition, this holds if and only if ν ˚ě pw q{w q qN q `βq .

Case 2: E q P Q with 0 ă y q ă N q , but Dq P Q with y q " 0. Choose p such that f ´1 p p0q " β p ": ν ˚is minimal among all such lower-bound region-files, i.e. p " arg min qPQ,y q "0 β q . It suffices to show that f q pν ˚q ď 0 if y q " 0 and f q pν ˚q ě N q if y q " N q . Let firstly q P Q with y q " 0. Then f q pνq " f q pβ p q " pw q {w qqpβ p ´βq q ď 0 by definition of p. Secondly, let q P Q with y q " N q . Note that (4.20) implies that γ p ď 0 and γ q ě 0. Thus, (4.21) implies that f q pν ˚q ě N q which holds if and only if ν ˚ě pw q{w q qN q `βq . Case 3: y q " N q for all q P Q. Choose p :" arg max qPQ f ´1 q pN q q and ν :" f ´1 p pN p q ". Then, since f q is non-decreasing for q P Q, f q pν ˚q ě f q py q q " f q pN q q " pw q{w q qN q `βq .

It remains to be shown that ν ˚ě 0 in all cases. Note that ν " f ´1 p py p q Algorithm 1 Generalized Bucket-filling (solves UA-primal-m with objective function (4.3))

1: Choose q P Q such that a q{w q ě a q {w q for all q.

2: Sort Q by β q non-decreasingly.

3: Initialize the sets of active region-files as Q A " tq P Q | β q " β qu, inactive region-files Q I :" QzQ A and deactivated region-files as Q D :" H.

4: Set ν :" 0.

5: Increase ν until § ν " β q for some inactive q P Q, then Q A :" Q A Y tqu and Q I :" Q I ztqu § ν " pw q{w q qN q `βq for some active q, then Q A :" Q A ztqu and Q D :" Q D Y tqu or § B{By q gpyq " 0 for all q P Q A , B{By q gpyq ď 0 for all q P Q I , and B{By q gpyq ě 0 for all q P Q D , where y " py q q with y q " f q pνq for q P Q A , y q " 0 for q P Q D and y q " N q for q P Q I .

6: If the last condition is fulfilled, return y. Otherwise, go to step 5.

for some p P Q, f ´1 p is non-decreasing (see (4.18)) and y p ě 0. Then ν " f ´1 p py p q ě f ´1 p p0q " pw q{w p qβ p " w q a q{w q ´ap {w p ě 0.

The last step is true due to the choice of q " arg max qPQ a q {w q .

We can now describe the novel Generalized Bucket-filling algorithm that efficiently finds the optimal solution to UA-primal-m (see Algorithm 1).

Observe that step 2 can be done in Op|Q| logp|Q|qq operations with a sorting algorithm such as quicksort. Thus, it dominates steps 1 and 3 that each need Op|Q|q operations.

Step 5 is executed up to 2 |Q| times, since every region-file tuple is activated and deactivated no more than one time each. Assuming that f q and B{By q gpyq can be evaluated in Op1q, the runtime of the loop in steps 5 and 6 is Op|Q|q. This shows that the overall runtime is dominated by sorting in step 2 and thus is Op|Q| logp|Q|qq " Op Ŝ F logp Ŝ F qq where Ŝ is the largest number of regions covered by any CBS and F the largest number of files that can be cached by any CBS.

Algorithm

The complete algorithm that finds the globally optimal solution to the UA-Π problem is summed up in Algorithm 2.

Algorithm 2 Solve UA-Π 1: Choose dual vector λp0q, t " 0, ε ą 0.

2: while λptq ´λpt ´1q ą ε do 3:

Choose ỹp0q, τ " 0.

4:

while ỹpτ q ´ỹpτ ´1q ą ε do 5:

Find ỹm pτ q with Algorithm 1 at every m P M separately.

6:

Exchange results among neighboring stations, set ỹpτ `1q as in (4.14), τ " τ `1.

7:

end while

8:

Exchange results among neighboring stations, set λpt `1q as in (4.12)

, t " t `1.

9: end while

The choice of the first dual vector λp0q in line 1 is arbitrary. The first primal vector ỹp0q in line 3 can be chosen as the last primal vector of the iteration before.

Numerical Evaluation for Load Balancing

At first, the model is evaluated with concave utility functions for load balancing purposes. Consider an urban area of 2.5 km ˆ2.5 km with uniform user distribution. A catalog of 6 files of equal size is known. The popularity of the files follows a Zipf distribution with parameter 1. Throughout the simulations, CBSs are placed in the area following a Poisson Point Process (PPP) with density 8 CBS km 2 . This means that their total number in each run is a random Poisson realization, and their position is uniform in the simulation window. In this way we avoid the bias of testing only particular network topologies. We run two simulation scenarios, the first for single-tier and the second for two-tier netowrks. Each scenario consists of 1000 simulation runs and we consider the averaged results over the runs. Coverage follows the Boolean model where a disc area is centered on each wireless station with some defined radius. The surface of different overlapping areas is found in each run by the Monte-Carlo method. The users are routed to the CBSs following three different cache-aware policies:

1. The Opt-h policy from Algorithm 2 with logarithmic utility function for each cache (Policy iv from Section 4.3. This policy guarantees a proportionally fair (and also max-min fair) solution. We call this policy Fair.

2. The Closest Available policy, which associates each user with the closest CBS that both covers its position and has the requested content cached.

3. The Unsplittable policy which associates all users in a region requesting the same file with a unique random CBS among all covering CBSs having this content.

We want to evaluate the proportion of user traffic served by different CBSs over the total traffic routed to CBSs for each policy. In this way we can compare the policies based on how (un)equally they associate traffic load among the available CBSs. Observe that for all three policies, the total traffic volume associated to CBSs is the same, because in all scenarios the CBSs store the same cached content, and traffic is routed to a CBS whenever possible. Hence, the comparison is fair.

Single-tier Networks

In an ideal situation, all stations would serve exactly the same amount of traffic. This, however, is normally not possible in a random network. A routing policy is better than another, when the maximum load of a CBS is lower and at the same time the minimum load share is higher than in the other policy. This way, an overload of the stations is avoided while the usefulness of all stations is achieved. Simulating single-tier networks, we want to verify that the fair policy provides a more balanced distribution of traffic to CBSs than the other two. The coverage radius of the CBSs is varied between 62.5 m and 500 m. This can be translated to an expected number of covering CBSs per user between 1 and 6. This mapping comes from the Boolean model [START_REF] Giovanidis | Optimal geographic caching in cellular networks[END_REF]. Two different sets of content files with different popularities are placed uniformly randomly into the caches. Since we are only interested in traffic associated with CBSs, we disregard users not covered by any CBS. The results show that with an increasing average number of covering stations, the fair policy achieves a lower maximum load as well as a higher minumum load. Since the overall traffic routed to the CBSs is the same for all policies, we can conclude that the Fair policy makes the most balanced use of the available resouces. The resources which remain available for potential cache-unrelated traffic are spread evenly across the network.

Two-tier Network

In a second scenario, we simulate an area covered by two tiers [START_REF] Di Renzo | Average rate of downlink heterogeneous cellular networks over generalized fading channels: A stochastic geometry approach[END_REF]: one of large and one of small coverage. We show that the fair policy is better at offloading traffic from larger to smaller CBSs than the other policies (see Fig. 4.5). While the Fair policy burdens the small stations with a higher load, we demonstrate that it distributes the load more evenly among them so that no individual station is overburdened (see Fig. In Fig. 4.5, we show the percentage of all traffic routed to large CBSs for each of the three policies. The x-coordinate increases with the ratio of small stations over large stations in the network. When less traffic is routed to the large CBSs, then the policy provides a more efficient offloading of traffic towards the small CBSs. The figure shows that, increasing the amount of small CBSs, the Fair policy offloads significantly more traffic to the small stations than the Unsplittable policy, and slightly more than the Closest Available policy. 4.4) the maximum and minimum traffic load routed to a small CBS depending on each policy. Even though for the Fair policy more users are routed to the small CBSs overall, the maximum load share that one small CBS takes is almost the same for all policies. The increase in traffic load by the fair policy is distributed to the less loaded small CBSs. This is indicated by the higher minimum load among the stations.

When applying either the Closest Available or the Unsplittable policy these CBSs are underused. Thus, the fair policy utilizes the available resources better.

NUMERICAL EVALUATIONS FOR THROUGHPUT MAXIMIZATION59

Numerical Evaluations for Throughput Maximization

For evaluations for throughput maximization, 1000 cache-equipped networks were simulated on a square window of 8000 m ˆ8000 m of which the center 7000 m ˆ7000 m were evaluated to avoid edge effects. Users are distributed uniformly. The content placed into the CBSs comes from a 100 file catalog.

The popularity of the content follows a Zipf distribution with parameter 0.6. In each simulation, the CBSs were placed following a PPP with density 0.8 CBS km 2 , resulting in 39.2 simulated CBSs with an average distance of 560 m to the closest CBS. Each CBS has a circular coverage radius of 1000 m and a power of p " 1W . The coverage zone is divided into an inner strong signal zone and a weak signal outer zone. The channel h m,s is calculated assuming a path loss exponent of 4. For the calculation of the SINR (see (4.7)), the distance of any user in the zone with strong signal (ď 500m distance to the CBS) is assumed to be 500m, whereas in the weak signal zone it is assumed to be 1000m. The noise is σ 2 " 10 ´12 W.

For each network, three different frequency reuse scenarios are simulated.

In case of full frequency reuse ("1-freq"), each user uniformly gets assigned the bandwidth of B " 1MHz. All neighboring CBSs induce interference to each other. In a second scenario "2-freq", every station can operate on half of the total spectrum (random coin toss). To potentially serve the same number of users as in 1-freq, every associated user is served on half of the previous bandwidth, i.e. B " 0.5MHz. But in this case, the benefit is that only neighboring stations with the same half of the spectrum interfere. For "3-freq", the same principle is applied for a division of the spectrum into 3 orthogonal parts. For this run of experiments, the savings function is the linear weighted sum of traffic with the weights chosen as user throughputs (4.8). The content is placed into the CBSs according to three different content placement policies known from the literature: globally most popular content (MPC), uniformly randomly placed content (RANDOM) with which each k-subset of files has equal probability to be cached, and geographic caching (GEO, see [START_REF] Giovanidis | Optimal geographic caching in cellular networks[END_REF]) that places content in a probabilistic fashion taking coverage overlaps into account. User association is computed for each of these content placement policies with varying cache sizes, once maximizing throughput with Opt-h, once with conventional user association Closest.

Fig. 4.7 shows the hit ratio that can be achieved by Opt-h with the different content placement policies for the case 1-freq. For every content placement policy, the hit ratio increases with increasing cache size. The increases diminish when the cache size approaches 50% of the catalog. GEO is superior to the other policies in every case. For smaller cache sizes MPC is better than RANDOM, since the former provides the users with the most popular files. From a cache size of 12% of the catalog RANDOM performs better than MPC since more diverse content is offered to the users.

In Fig. 4.8, the relative gain of achieved hit ratio from Opt-h over Closest, i.e. the hit ratio achieved by Opt-h divided by the one achieved by

Closest. In each instance RANDOM achieves the highest gain, followed by GEO. MPC does not achieve any gains at all. This shows that for RANDOM placement, Closest performs badly. This is due to the fact that RANDOM has a high probability of placing unpopular content into a CBS such that there are not many close users that contribute to the hit ratio, while some further away CBS might well cache the more highly requested content. With GEO, Opt-h still performs significantly better than Closest. GEO produces a diverse placement for the typical user, while still emphasizing more popular content at every CBS. This explains that the gain is between RAN-DOM and MPC. Since MPC places the same content at every CBS, it can never be the case that a station that has weaker signal stores content that a stronger one does not. Thus, Closest association is optimal in this case.

The gains from Opt-h association decrease with increasing cache sizes, since more users find their requested content in the CBS that has the strongest signal. Overall, this plot shows that that user association policy makes a difference, particularly for content placement policies which emphasize content diversity amnong the CBSs.

Clearly, the gains in hit ratio from Opt-h over Closest come from the association of users with a weaker signal. In Fig. 4.9, we show that even if signal strength and interference are taken into account, Opt-h still is superior to Closest for GEO, the placement policy that achieved the best hit ratio. The metric used in this plot is the system throughput, the sum of users weighted by their achieved throughput ř mPM ř sPS ř f PF w m,s,f y m,s,f . The gain in thoughput from Opt-h over Closest, i.e. the ratio of respective system thoughput, shows that even for freq-1, Opt-h achieves throughput gains over Closest. These gains are even more pronounced for freq-2 and freq-3 networks which have reduced interference. When 3 frequency bands are assigned to the CBSs, a throughput gain of up to 45% can be achieved. While the gains diminish with increasing cache sizes, Opt-h provided a throughput gain of at least 10% in each simulated scenario, showing the significance of the user association under placement policies that diversify the content in neighboring CBSs.

Conclusions

This Chapter proposes an efficient distributed algorithm called Generalized Bucket-filling for cache-related user association. The algorithm can be applied for different purposes, for example hit ratio maximization, loadbalancing and throughput maximization. Simulations show that the algo-rithm effectively balances the user load, by distributing users from over-to underused CBSs. Furthermore, it is shown that under throughput maximization, the algorithm makes use of the possibility to associate CBSs to users that receive a weaker signal. This is particularly effective when orthogonal frequency bands are assigned to the CBSs.

Chapter 5 Cache Leasing and Content Placement

This chapter contains work from the published papers [START_REF] Krolikowski | Optimal cache leasing from a mobile network operator to a content provider[END_REF] and [START_REF] Krolikowski | A decomposition framework for optimal edge-cache leasing[END_REF]. Sections 5.2 and large parts of 5.4 are published in [START_REF] Krolikowski | Optimal cache leasing from a mobile network operator to a content provider[END_REF]. The complexity analysis in Section 5.3 and Corollary3 come from [START_REF] Krolikowski | A decomposition framework for optimal edge-cache leasing[END_REF]. The numerical evaluation (Section 5.2, in particular 5.6.3 to 5.6.6) are based on [START_REF] Krolikowski | Optimal cache leasing from a mobile network operator to a content provider[END_REF] while the remaining evaluation in the subsections 5.6.7 to 5.6.9 come from [START_REF] Krolikowski | A decomposition framework for optimal edge-cache leasing[END_REF]. Further analysis of the complexity of the problem SUR-T, in particular Corollary 1, is unpublished.

Introduction

Now, we change focus on the perspective of a CP. It is interested in placing its content closer to the user to improve QoS and to offload traffic from its central data storage infrastructure. An MNO offers to lease cache space at its CBSs for a certain time period for a fixed price per cache unit. Once the CP has decided how much memory to lease, it places its content, for example during an off-peak period. The cached content then remains static.

Assuming that an MNO fixes a price per cache unit at its CBSs, the 65 CP has two decisions to take: How much cache space to lease and what content to cache. As a basis for these decisions, we assume that the CP possesses fine grained spatio-temporal user traffic and content popularity data. The benefits, however, are only realized when users are associated to CBSs that cache the requested content. In order to predict which benefits can be generated from its cache leasing and content placement decisions, the CP needs to be informed about the MNO's user association policy (see previous chapter).

In this work, it is assumed that the CP's main objective is hit ratio maximization to offload traffic from its data storage. It will be shown that optimal leasing and placement decisions differ depending on the MNO association policy, Closest or Opt-h. The Opt-h policy, however, allows for different secondary objectives. In the context of this work, these may be § Load balancing among the CBSs: The CP may be interested to balance the cache-related load if it expects high traffic load to its cached content that threatens to overload the CBSs's wireless resources and thus diminish the QoS. The MNO might also incentivize the CP contractually not to overload any CBS by placing all its popular content in the same cache. § Throughput maximization: In order to provide good QoS, the CP is interested in providing optimal network throughput for the cache-related users.

While focusing on the aforementioned CP aims, the following model is more general and is applicable to any convex, monotonuously increasing and continuously differentiable objective. § Every CBS m covers a set of regions Spmq. The partition of the network area into regions S depends on the MNO's user association policy Π.

The set of CBSs covering region s is denoted by Mpsq. § For each region s, the CP has an estimate N s,f of the number of users requesting each file f . The vector of these popularity entries is denoted by N. Note that the model does not assume spatially uniform traffic and that the vector N is general.

CP Savings and MNO Policy

The CP's aim is to maximize its financial savings from edge caching. These can, for example, be proportional to the hit ratio, the wireless throughput or take load-balancing of cache-related traffic into account. Formally, the CP savings are measured by the CP savings function h CP p¨q that takes the placement vector x as argument and maps it onto the CP savings (in e).

To achieve maximum benefits from content placement decisions, the CP depends on the MNO's user association policy. Assume MNO pursues the conventional Closest user association. Then, each CBS is related to a unique region. Since the MNO associates all users in a region to the corresponding CBS, the CP can use its knowledge about user statistics in each region to place content according to its own criteria. If, however, the MNO applies a cache-aware user association policy such as Opt-h, the CP needs to take the MNO reactions to its own placement decisions into account. Particularly, the MNO has its own performance metric that is expressed in the savings function h MNO p¨q. The MNO maximizes this savings function performing user association.

The function h MNO p¨q measures one of the listed performance criteria for the MNO, e.g. throughput. Then, for a given content placement x the optimal association vecor is y Opt´h MNO pxq as defined in Section 4.2.2. In this work, we assume that in every instace the savings functions h CP and h MNO of the CP and the MNO, respectively, are UA-equivalent by the following definition: If for all px, zq, px 1 , z 1 q P X : Now, additionally to the previous assumptions, we assume that there is a convex, increasing and differentiable relationship g that maps the MNO savings onto the CP savings, i.e.

h CP pxq ď h CP px 1 q ðñ h MNO py
h CP pxq " g ˝hMNO py Opt´h MNO pxqq.

(5.3)

Then, let h " g ˝hMNO .

(5.4)

Note that h as the composition two increasing, continously differentiable, convex functions is itself increasing, continously differentiable and convex.

Three performance criteria for content placement are in the focus of this chapter:

HR) In case that the CP is solely interested in maximizing the hit ratio, the corresponding MNO savings function h MNO can be chosen as a linear function.

LB) If the CP maximizes the wireless throughput, the UA-equivalent function h MNO is weighted linear.

TP) The CP can include aspects such as soft resource requirements and load-balancing when h MNO is the sum of strictly concave functions (one function per CBS).

Problem statement

The objective of the CP is to lease cache memory at the CBSs and place content into it such that the relation of its expected savings to the leasing cost is optimal. As mentioned, the savings are given by the function h CP p¨q that takes as input the content placement action x.

ď N s,f x m,f , @ m, s, f,
where m is a CBS, s is a planar network region and f is a data file.

Special Case: For zero costs and unit file size under the Closest policy with linear savings function h, it is optimal to store k m locally Most Popular Content in each CBS m.

Complexity

Even with a linear savings function h and without taking cache leasing into account, the CLCP problem is NP-hard.

Proposition 2. The CLCP problem is NP-hard.

Proof. Assuming that h can be evaluated in polynomial time, a certificate can be checked in polynomial time, thus the problem is in NP. Choose hpyq " ř sPS ws ř f PF ř mPMpsq y m,s,f where the ws correspond to the weights in HD. Since ws ą 0 for all s by definition in HD, and since y m,s,f ď N s,f x m,f as well as (4.2) for all m, s, f , then whenever a CBS covering a region s stores the requested content f , all user traffic from the region will be associated with some CBS. Thus, ř mPMpsq y m,s,f " N s,f if x m,f " 1 for some m P Mpsq and 0 otherwise. Choosing N s,f (CLCP) as P f (HD) for all regions s shows that, defined this way, the objective function of CLCP is equivalent to the objective function of HD. This is a polynomial time transformation which concludes the proof. Note that in [SGD `13] NP-completeness is proved for catalog size two.

Solution

The CLCP problem is very difficult to be solved even numerically by existing software, due to its high complexity. It is a mixed-integer problem with non-linear objective. We thus need to proceed analytically. The solution technique that resolves this problem is Generalized Benders decomposition by Schrijver [START_REF] Schrijver | Theory of Linear and Integer Programming[END_REF] and Geoffrion [START_REF] Geoffrion | Generalized Benders decomposition[END_REF] which converges to the global optimum. This method can decompose our problem in a way that removes the non-linearity from the discrete problem. The decomposed discrete problem, called Master, is linear and thus simpler to deal with. As a second byproduct there appears a continuous convex subproblem called Slave, which can be solved by standard techniques (e.g. Lagrangian). Observe that due to Proposition 2, our solution algorithm cannot be polynomial even with linear savings function unless P " NP. However, a state-of-the-art MIP solver can be used for the iterative solution of Master. Its performance is shown in Section 5.6. In what follows, we give an overview over Generalized Benders decomposition applied to CLCP.

CLCP can be decomposed into two problems called Master and Slave.

Master decides about cache leasing and content placement in the prefetching phase. Slave computes the optimal user association for a fixed content placement in the delivery phase. We obtain

pMasterq max px,zqPX hpypxqq ´ÿ mPM p m z m ,
where hpypxqq is the objective value of pSlaveq ypxq " arg max Note that the Master problem can be treated by the CP, the Slave by the MNO. X is discrete and finite and Y Π is compact and convex. Slave is the UA-Π problem from Section 5.2.3 which is generally non-linear. Thus, Master cannot be solved directly. It can be solved, however, by following an iterative procedure that deals with this problem by solving a sequence of Slave problems for different values of x (and z). The solutions to Slave are used to construct (linear) Benders cuts that constitute approximations to Slave. The Benders cuts are iteratively introduced as constraints of the Surrogate Problems which are linear approximations to Master. With each iteration, the approximation improves until the optimal solution of Master is found.

Benders Cuts

Let tpx t , z t q P X | t " 1, . . . , T u be a set of vector tuples feasible to Master for some T ě 0. Let y t :" ypx t q denote a corresponding vector that optimizes Slave for given x t . Let λ t " pλ t m,s,f q mPM,sPS Π pmq,f PF be the vector of Lagrangian multipliers corresponding to the constraints (4.2).

Slave is a convex problem. Thus, the duality theorem of convex programming implies hpypxqq ď hpy t q `ÿ mPM

ÿ sPS Π pmq ÿ f PF λ t m,s,f pN s,f x m,f ´yt m,s,f q
for all feasible vectors x. This upper bound to Slave is called Benders cut.

Reformulated, we get hpypxqq ď Γ t `pv t q 1 x,

where Γ t :" hpy t q ´řmPM ř sPS Π pmq ř f PF λ t m,s,f y t m,s,f and pv t q 1 is the transpose of v t " pv t m,f q mPM,f PF with v t m,f "

ř sPS Π pmq λ t m,s,f N s,f .

Surrogate Problem

For a set of T Benders cuts (for some T ě 1), we obtain an upper bound to the original problem CLCP by solving the Surrogate IP

pSUR-T q max px,zqPX γPR ě0 γ ´ÿ mPM p m z m s. t. γ ď Γ t `pv t q 1 x t " 1, . . . , T.
The optimal objective value to the surrogate problem is denoted by sur T .

The optimal solution consists of x T `1, z T `1 and γ T `1. Note that the auxiliary variable γ, together with the Benders cuts, approximates Slave linearly. This way, SUR-T avoids the non-linearity which creates the difficulty for solving Master.

Benders Iteration and Convergence

Generalized Benders decomposition is an iterative process. We start in step 0 with an initial feasible tuple of leasing and placement vectors px 0 , z 0 q P X and without any Benders cuts. At the start of step T ě 0, we have the current leasing and placement px T , z T q P X and T Benders cuts.

Slave: We solve Slave with input x T to obtain the optimal association vector y T . Clearly, since the triple x T , z T and y T are feasible to the original problem CLCP, its corresponding objective value provides a lower bound to the optimal value of CLCP. Additionally, we compute the Lagrangian multipliers λ T and the corresponding pT `1q-th Benders cut (5.5).

Surrogate: With the Benders cut we obtain the surrogate MIP SUR-(T `1). Its optimal solution is the feasible leasing and placement vectors px T `1, z T `1q P X . The objective value sur T `1 is an upper bound to CLCP. This process iterates. At any step T , sur T is the current upper bound (note that sur T `1 ď sur T after every step T ), while the current lower bound is provided by the best found solution max tPt0,...,T u hpy t q ´řmPM p m z t m . The process terminates in the globally optimal cache leasing and content placement vectors z ˚and x ˚when the upper and lower bounds coincide. Convergence is guaranteed from the proof of Theorem 2.4 in [START_REF] Geoffrion | Generalized Benders decomposition[END_REF] and the fact that the domain X of the Master is finite.

Complexity of the Surrogate Problem

In every step T , an instance of the Surrogate problem needs to be solved.

In general, the Surrogate problem is not easily tractable as to the following proposition. It consists of a polynomial time reduction from the well-known Set Cover problem. Its minimization version is defined as follows:

Definition 1. Let T be an index set, called universe. Let F Ď 2 T be a family of subsets. Set Cover asks for a subset S Ď F of minimum size such that Ť S " T .

Proposition 3. For T P N and general parameters Γ t P R and v t P R |M||F | , t " 1, . . . , T , p m P R for m P M as well as domain X , the Surrogate problem SUR-T is NP-hard.

Proof. Objective function and constraints can be evaluated in polynomial time, thus the problem is in NP. Now, we reduce Set Cover to SUR-T . In the Set Cover decision problem, the question is if there is a subset S of a collection of sets F Ď 2 T with cardinality less than or equal to S such that Ť S " T where T is the universe . For the reduction, we identify the Benders cuts t with the elements in the universe T . The files f are in bijection to the sets in the family F.

Note that then, the Set Cover decision problem can be written as: Are there

γ P R, x P t0, 1u |F | with γ ě 1 γ ď ÿ f PF 1 tPf x f @ t ÿ f PF x f ď S,
where 1 tPf " 1 if t P f and 0 otherwise? Here, x f is a binary variable taking value 1 if and only if f is element of S and γ represents the lowest frequency of any element of T in S.

This is an instance of the SUR-T decision problem for only one CBS

(omitting the index m): The price is chosen as p m " 0. The memory capacity is chosen as k m " S, the file sizes as well as memory are all unit size (b f " b MU " 1). Then, the variable z m can be omitted since in the optimum,

ř f PF x f " z m . The constraint ř f PF x f ď S
is the combination of the constraints (5.1) and (5.2). Constraint set γ ď ř f PF 1 tPf x f comes from choosing Γ t " 0 for all t and v t m,f " 1 tPf .

The reduction is performed in polynomial time. This concludes the proof.

Set Cover is a well known problem. Bellare et al [START_REF] Bellare | Efficient probabilistically checkable proofs and applications to approximations[END_REF] proved that, unless P = NP, Set Cover cannot be approximated with constant factor in polynomial time. Feige [START_REF] Feige | A threshold of ln n for approximating set cover[END_REF] showed that, unless NP has slightly superpolynomial time algorithms, there is no better polynomial-time approximation than log T where T is the size of the universe T . It is well known that the greedy algorithm reaches the logairthmic bound [START_REF]A greedy heuristic for the set-covering problem[END_REF].

The polynomial time reduction from Set Cover to SUR-T then implies that SUR-T cannot be approximated with a constant factor.

Corollary 1. Unless P = NP, SUR-T cannot be approximated with constant factor in polynomial time.

Despite the fact that SUR-T is NP-hard, state of the art MIP solvers such as CPLEX are capable of solving SUR-T in reasonable runtime.

Implementation Considerations

Here, we provide a short discussion about information exchange between the entities solving Slave and SUR-T towards the global optimum. The SUR-T problem that solves the leasing and content placement aspect requires information on the price per cache unit. For each Benders cut, the vector of Lagrangian multipliers (dual prices) of the user association together with the optimal objective value of Slave need to be communicated. Knowledge of the spatial popularity statistics in this phase is reasonably assumed.

On the other hand, the Slave problem as formulated needs to know the exact utility h of the CP together with a subset of the popularity statistics which is related to the content the CP aims to cache. Hence, although the content placement and user association decisions are treated separately in two intertwined optimization problems, Slave does require sensitive information from the CP.

To overcome the implicit conflict of interest, a first suggestion can be that the MNO informs the CP about its general association policy Π to cooperate or not, together with the cache price. The CP can then solve both problems and after having identified the optimal association vector it can give association suggestions to the MNO each time a potential cache-related user emerges. Obviously, such approach requires a more integrated interaction between the two actors. A second proposal could be that the MNO solves Slave by using estimates on the CP savings function and popularity data. The resulting association solution communicated to the CP via the Lagrangian multipliers will generate a different set of Benders cuts for the CP. Obviously, in this case the final solution is suboptimal. An interesting extension of the current research would be to mathematically investigate the quality of such solution.

Distributed Solution Algorithm for Slave

A distributed solution algorithm for Slave is given in Chapter 4.

Experiments and Numerical Evaluation

Environment

We simulate cellular networks in an urban environment and calculate the optimal cache leasing and content placement for 6 cases which differ in savings function and user association policy: The savings function h is chosen as: HR) Linear as in (4.5) for hit ratio maximization. LB) The sum of utility functions as in (4.6) where all utility functions U m are chosen as the natural logarithm to achieve proportional fairness for the user traffic at the CBSs, thus balancing the load among CBSs. TP) The weighted sum of utilities as in (4.3) where the weights are defined as in (4.8) and the utility functions are identities. This way, the sum of utilities is equal to the network throughput.

For each of the three cases of savings functions, the MNO's user association policy is a) the MNO-CP cooperative policy Opt-h or b) the conventional policy Closest. In each case, we simulated 100 random sets of CBS positions as a Poisson Point Process. This means that their total number in each run is a random Poisson realization, and their positions are uniformly distributed in the simulation window. The density of the PPP is 0.8 CBS km 2 for the cases HR) (linear savings) as well as TP) (weighted linear savings) and 0.6 CBS km 2 for the cases LB) (log-savings). This implies an average minimal distance of 560m and 650m between the CBS positions, respectively. For the cases HR) and TP), the evaluation window has size 5000ˆ5000m 2 , while the cases LB) were evaluated in a 3000ˆ3000m 2 window. The expected number of CBSs in the evaluated windows is 20 for case HR) and TP) and 5.4 for case LB). In both cases, a larger area was simulated to avoid edge effects.

The coverage radius varies from 400m to 1200m. The MNO price per unit size cache memory at all CBSs varies (0.01e-2.00e). The user population is distributed uniformly over the network with a density of 30 users per km 2 . The total simulated file catalog contains 100 objects. The content popularity follows the Zipf distribution with parameter 0.6 unless explicitly stated otherwise. The available cache size from the MNO is set to the catalog size so that only the pricing influences cache leasing decisions.

Implementation

All simulations have been performed using a native JAVA simulation environment. User association corresponding to the solution of the slave problem in Sections 5.4 and Chapter 4 is entirely done by optimization algorithms developped in the context of this thesis. The surrogate problem SUR-T in Section 5.5 is solved using the state of the art mixed-integer problem solver IBM CPLEX 12.7.0 in combination with IBM ILOG CPLEX Optimization Studio. The experiments have been performed on a machine with a 2.40 GHz 16-core processor and 48 GB RAM. At first, we present the simulation results in which the CP aims at hit ratio maximization (case HR)). On average, the optimal solution was obtained after 2 Benders iterations. We emphasize case HR.a) which performs Opt-h user association and compare it with case i.b) Closest. Fig. 5.1 illustrates how the hit ratio in case HR.a) depends on the price per cache unit for different coverage radii. For all radii, the hit ratio decreases with increasing prices. With lowest price (0.01e/Unit), the CP leases in each CBS the entire memory available, so the hit ratio is 100%. As the price increases, the CP leases less units, and the hit ratio is reduced. This happens more quickly in networks with smaller coverage areas because there are less users covered by each CBS and also less coverage overlap area. When the price reaches a high level (2e), the cost from leasing cache memory exceeds the benefit from cache hits and the hit ratio drops to 0% for all coverage radii. The differences between the curves in Fig. 5.1 diminish with higher radii where multi-coverage is already high enough. Fig. 5.3 directly compares optimal CP decisions taken with Opt-h association with those taken with Closest association. For all prices the hit ratio achieved by Opt-h (case i.a) is higher than the one achieved by the Closest policy (case HR.b). The relative hit ratio differences are higher when the coverage area of the CBSs is higher. For higher prices, the Closest hit ratio is close to 0, therefore the relative differences can become very high.

Results for Hit Ratio Maximization

Leasing Costs for Hit Ratio Maximization

While Figures 5.1 to 5.3 show the caching benefits for the CP, the costs it has to pay in return to the MNO (in case Opt-h) are depicted in Fig. 5.4. The CP costs equal the MNO income. This amount can be calculated by multiplying the number of leased cache units with the price per unit. The maximum of the curve can be clearly identified for each radius. This is the operational point for the MNO when the latter aims for maximum income. The maxima are higher for larger coverage areas, while the difference in income decreases with increasing radius. Furthermore, the higher the coverage radius, the higher the cache leasing price at which the maximum is achieved. The relation between hit ratio and MNO income can be seen in Fig. 5.5:

The x-axis displays the hit ratio achieved, the y-axis shows the income the MNO earns. Again, the income is higher in networks with larger coverage area. The maximum income for all simulated networks can be found for an achieved hit ratio between 80-90%. Conversely, if the CP decides to invest a certain sum, it can maximally achieve the rightmost of the two corresponding hit ratio values under the condition that the MNO chooses the pricing strategy most favorable to the CP.

Varying Content Popularity

The experimental results presented until now are based on a Zipf parameter of 0.6. However, a varying Zipf parameter influences the results: Fig. 5.6 shows that the higher the price, the lower the hit ratio for any Zipf parameter in case HR.a). This is due to the fact that lower price implies more leased units for the CP. For all prices (except the lowest one which achieves a hit ratio of near 100% throughout), the hit ratio increases with increasing Zipf parameter: With higher Zipf parameter, the population share requesting the most popular files becomes higher, thus caching popular files becomes more profitable. Also, for the same price, the leased cache memory is more effective with higher Zipf parameters. The lower the Zipf parameter, the more pronounced the differences in hit ratio between different cache prices since the benefits from overlapping coverage are bigger when content popularity is more even.

Results for Load-Balancing among CBSs

Here, we present the experimental results for load balancing (case LB)) in which the savings function h MNO is the sum of logarithms. When such user association is performed, the CP aims at load balancing of cache-related traffic among the CBSs. The optimal solution was obtained after 8 Benders iterations on average. Fig. 5.7 shows the hit ratio for varying cache unit price both for the Opt-h (different coverage radii) and the Closest policies.

Due to the specific choice of the logarithmic savings function of case LB) the Closest association gives identical cache leasing and content placement results for all coverage radii. For every coverage radius and every cache unit price, the Opt-h policy achieves a higher hit ratio than the Closest policy. Furthermore, the higher the coverage radius in case LB.a), the higher the hit ratio. The hit ratio improvement can reach over 15 percentage points using Opt-h. With increasing prices, caching becomes less profitable and the hit ratio decreases.

The advantage to the hit ratio of the Opt-h policy (LB.a) can be explained by the optimal content placement shown in Fig. 5.8. Each pair of columns represents cache leasing and content placement for a certain unit price. Each left column represents the optimal decisions with Opt-h associ-

The main purpose of choosing the specific savings function in LB.a) is, however, the balancing of traffic load among the CBSs in order to avoid excess of resources by user overflow which will lead to service dissatisfaction. Fig. 5.9 shows that the additional load (from the increase in hit ratio using

Opt-h, see Fig. The three plots show that the optimal leasing and placement under the Opt-h policy achieves an increase in hit ratio (good for both the CP and the MNO) while at the same time diversifying the cached content (good for the user) and avoiding an overload of CBSs (good for everybody). Note that in this chapter, until now, the cache leasing and content placement decisions that have been considered are solutions of the CLCP problem, depending on the MNO user association policy Opt-h or Closest. In this section, the leasing mechanism is not considered, and instead a varying limit for the cache size is imposed. Here, the Opt-h results are the results of the In order to illustrate the true benefits of Opt-h over Closest (with linear savings) as well as over other content placement policies, spatially inhomogeneous content popularity should be considered. We evaluate here a traffic scenario in which the network window is symmetrically divided such that on each side, the popularity of files follows a Zipf distribution with parameter 0.6, but the ten most popular files on one side are swapped with the second most popular decile on the other side to give locally differing popularity distributions. We fix the cache sizes uniformly and do not consider the leasing mechanism, enabling comparisons with known content placement policies that do not take cache leasing into account. Fig. 5.10 shows that for a large range of cache sizes, Opt-h provides a 50% relative gain in hit ratio over Closest. Compared to other placement policies such as geographic caching (GEO, see [START_REF] Giovanidis | Optimal geographic caching in cellular networks[END_REF]), caching of globally Most Popular Content (MPC) and uniformly random caching (RANDOM), the Opt-h policy provides considerable gains in each case. This result works strongly in favour of our suggestion that the MNO and CP should closely collaborate for user-association decisions. The actual content request distribution can diverge from the statistics on which the cache leasing and content placement decisions are based. We evaluate the effect of a diverging Zipf parameter of the popularity distribution on the hit ratio of CP decisions based on parameter 0.6 (case HR)).

Policy Comparison

Sensitivity to Traffic Estimation Errors

From Fig. 5.11 it can be seen that if the Zipf parameter was underestimated for leasing and placement, the hit ratio will be higher than expected as well. Conversely, an overestimated Zipf parameter leads to a decrease in the obtained hit ratio.

Results for Throughput Maximization

Finally, we present the simulation results for throughput maximization (case TP)). On average, the optimal solution was obtained after 2 Benders iterations. The CBSs have a coverage radius of 1000m and a power of p " 1W .

Every station has two coverage zones, one in the inner half of the coverage radius, one in the outer half. The channel h m,s is calculated assuming a path loss exponent of 4. For the calculation of the SINR (see (4.7)), the distance of any user in the zone with strong signal (ď 500m distance to the CBS) is assumed to be 500m, in the weak signal zone it is assumed to be 1000m. The noise is σ 2 " 10 ´12 W.

For each network, three different frequency reuse scenarios are simulated.

In case of full frequency reuse ("1-freq"), each user uniformly gets assigned the bandwidth of B " 1MHz. All neighboring CBSs induce interference to each other. In a second scenario "2-freq", every station can operate on half of the total spectrum (random coin toss). To potentially serve the same number of users as in 1-freq, every associated user is served on half of the previous bandwidth, i.e. B " 0.5MHz. But in this case, the benefit is that only neighboring stations with the same half of the spectrum interfere. For "3-freq", the same principle is applied for a division of the spectrum into 3 orthogonal parts.

For this run of experiments, the savings function is the linear weighted sum of traffic with the weights chosen as user throughputs (4.9). The valuation of the savings is set to c " 1e/MBits which implies that any achieved throughput of more than 1MBits per invested Euro brings the CP into profit. Fig. 5.12 shows the total throughput per invested Euro ("caching efficiency") over cache leasing price (between 0.1e and 1.6e) for the user association policies Opt-h and Closest, each for the different frequency reuse scenarios. Observe that Opt-h yields a significantly higher caching efficiency than Closest throughout. The relative difference between the two user association policies is greatest in the 2-freq scenario whereas the absolute system performance is maximised with 1-freq. This is due to the fact that for 2-freq, center users receive less bandwidth than in 1-freq even though interference is low. Interference reduction and system performance of 2-freq and 3-freq can be improved, however, by assigning the parts of the spectrum to CBSs in a more intelligent way than uniformly randomly. Depending on frequency reuse, the MNO can offer profit through caching (ě 1MBits/e) to the CP even when the cache-price is set high.

Conclusions

Extensive experiments for random network topologies allow to compare the optimal CP decisions for different MNO association policies, cache prices, as well as CP savings functions. In all versions of the problem, we have identified a unique price that maximizes the MNO revenue. It depends on how much the CP valorizes traffic offloading achieved by the edge caches. This information is included in the CP's choice of the savings function. Another main conclusion is that MNO association policies which adhere to CP actions and exploit multi-coverage opportunities achieve higher offloading benefits for a given monetary investment. All these results suggest that the CP and MNO can jointly develop cooperative business models related to caching, that lead to considerable economic as well as operational benefits for both parties.

Chapter 6 Competition between Multiple CPs

This chapter contains unpublished research and premliminary results.

Introduction

In the previous chapter, a CP leases edge memory space from an MNO for a fixed price. Here, we look at a scenario in which several CPs compete for the same cache resources of one MNO.

Each of the CPs has its own separate content catalog, disjoint from the others. The CPs all deliver their content via the MNO's wireless network that is equipped with caches. The cache memory is allocated to the CPs by the MNO in an allocation phase that precedes the content placement and delivery phases from the previous chapters.

Assume, for example, that the MNO to allocates cache space to each CP separately for a fixed price. In that case, the analysis for cache leasing in Chapter 5 applies. The CPs may, however, have varying numbers of users overall or locally, different shapes of popularity profiles, or might value caching effects differently. It is thus possible that, if the MNO offers a fixed 93 amount of cache space to each CP, one or several CPs decide not to lease the entirety of their allocated cache space while other CPs would like to lease beyond what they have been allocated. A higher aggregated hit ratio could then be achieved by allocating unused cache space to CPs that are willing to pay for the additional cache units. From the MNO point of view, it is preferable to utilize the installed caches in their entirety since more leased cache space induces the offloading of more network traffic. In economic turns, this means that the MNO aims at clear the market. The question arises how much cache space should be allocated to each CP at each CBS. This chapter follows the idea of social welfare maximization: Every CP values a profile of allocated cache space through the savings that it can achieve. The social welfare is the sum of all CP savings. The aim of the MNO is to allocate its cache space to the MNOs that maximizes social welfare. The underlying assumption is that CPs that achieve higher savings help the MNO more since they are able to serve more users from the caches.

Once the CPs have cache space assigned, they will place their content into the caches in the content placement phase. The placement decisions are taken based on knowledge of their respective traffic and popularity data and the announced MNO user association policy. In the content delivery phase, cache hits generate savings to the CPs through the offloading of user traffic from their own data center infrastructure and through improvement of user QoS. The CPs are assumed to be rational entities that aim at maximizing their individual savings that they can achieve through such an edge caching scheme.

The CP savings, expressed through savings functions that map assigned cache space onto a financial value, are not necessarily known to the MNO.

The communication between MNO and CPs instead occurs through a financial transaction. This can take place through an allocation mechanism in which the CPs are price takers, or through a game in which the CPs antici-pate the bidding behaviour of their competitors.

System Model

Cache-equipped Network

Consider a cellular communications network with a finite set M of CBSs, operated by an MNO. Each CBS m is equipped with k m memory units. A set of CPs R competes for access to the cache space. The amount of memory units that CP r P R gets allocated at CBS m P M is denoted by z prq m . The allocation vector for r is z prq " pz prq m q, m P M. At each CBS, the MNO can assign no more cache units than are installed, which implies that the following constraint holds:

ÿ rPR z prq m ď k m , @ m P M. (6.1)
After CP r gets assigned memory space z prq , it can place content from its catalog F prq in it.

CP Savings

Through cache hits, the CP generates savings that are expressed through the savings function h prq : Ś mPM t0, . . . , k m u Ñ R that takes the cache allocation vector z prq as input and maps it onto the CPs savings. h prq is componentwise non-decreasing, i.e. there are never more savings generated to a CP by have less cache space allocated at a CBS, all others being equal.

The savings depend on the content that the CP places into the caches, and subsequently on the association of users to the caches. In Section 5.2.4, a function h CP (here specific for r h CP-prq ) is defined that takes the content placement vector x P t0, 1u |M||F | as input. Since CP r behaves rationally and places content optimally, the savings from the assigned cache space z prq are the solution of the problem

h prq pz prq q " max xPt0,1u |M||F | h CP-prq pxq s.t. ÿ f PF prq b f x m,f ď b MU z m , @ m P M,
where b f is the file size of file f and b MU is the size of a leased memory unit.

The above problem is a 0-1 knapsack problem with general componentwise non-decreasing objective. It is connected to the CLCP from Section 5.2.4: If all prices in a CLCP are set to p m " 0 and the leased cache units are fixed to the vector z prq , then the savings h prq pz prq q can be calculated with the methods from Chapter 5.

Problem Statement

The assignment of cache space by the MNO to the CPs that maximizes social welfare is the solution to the following problem: Note that, under the relaxation of the integrality constraints and the definition of the savings function h prq is reduced to

h prq pz prq q " max xPr0,1s |M||F | h CP-prq pxq s.t. ÿ f PF prq b f x m,f ď b MU z prq , @ m P M.
By the definition of h CP-prq , h prq is concave, non-decreasing and continuous.

Cache Allocation Mechanisms

CPs as Price Takers

A CP r acts as a price taker if, given a price per memory unit, the resulting bid d r does not take potential future price changes into account. Given a price p, a price taking CP aims at maximizing its payoff function P prq p pd r q " h prq pd r {pq ´dr . (6.3) If for some vector d " pd r q, r P R and a price p, it is true that the respective payoff function (6.3) is maximized and the equality (6.2) holds, then d is a competetive equilibrium. In [NRTV07, Chapter 21], it is shown that any competetive equilibrium is optimal for the problem SWsr.

This equilibrium can be achieved iteratively, letting the MNO adjust the price p step by step.

Price Anticipating CPs

In the previous section, CPs choose their bids maximizing their payoff function (6.3), treating the price p as a fixed parameter. Here, the CPs are aware that the price is set according to (6.2), i.e. that the share of the total memory k that CP receives depends on the other bids by the ratio d r { ř r 1 d r 1 . Knowing this, the CPs adjust their playoff accordingly. This makes the process a game between the CPs with the payoffs

Q prq pd r ; d ´rq " $ ' & ' % h prq pk ¨dr { ř r 1 d r 1 q ´dr if d r ą 0, h prq p0q otherwise,
where d ´r is the vector of all values d r 1 for r 1 ‰ r.

A Nash equilibrium of the game defined by Q r , r P R is a vector d such that for all r: Q r pd r ; d ´rq ě Q r p dr ; d ´rq for all dr ě 0.

Chapter 7

Conclusions and Future Work Beyond the results from Chapters 4 and 5, Chapter 6 shows a way towards evaluating scenarios in which several CPs compete for the cache resources of one MNO. In such a scenario, the CPs can act as price takers, accepting the leasing price given out by the MNO, or they can be price anticipating. In the latter case, the CPs preempt the behavior of the competing CPs, assuming that the MNO is interested in leasing out the entire available cache space.

In case the CPs are price anticipating, any equilibrium of the resulting game loses no more than 25% of efficiency against the social optimum.

Future Work

There are several ways in which these results can be extended.

Data Uncertainty

User association in this work is treated in an accumulative sense, based on user traffic and content popularity predictions. The resulting distribution of cache-related users is calculated, not the association of individual users.

While simulations show that slight inexactitudes in these predictions do not affect the effectiveness of the proposed edge caching scheme, further questions can be asked: § How can knowledge about data uncertainty be included in the model?

Competing CPs and competing MNOs

Chapter 6 shows a way towards a model for an edge cache market. The steps further in that direction include: § The model in Section 6.

Deeper or Interconnected Caches

The usefulness of edge caching has been shown throughout this thesis. The edge caching business model can, however, be enhanced by including caches deeper in the network. Research can be extended into the following direction: § Caches can be placed at internal network nodes by MNOs and their memory space leased to CPs. How would these additional caches affect cache leasing and content placement?

response is retained in the cache while a copy is transmitted to the client, and, for example, the least recently used (LRU) cached content is replaced. If soon after another request for the same content is passed to the cache agent, the request can be served from the cache instead of its original source. This way, the caches are populated based on previous user requests (pull caching).

A different caching paradigm is called push caching or prefetching [START_REF] Bestavros | Speculative data dissemination and service to reduce server load, network traffic and service time in distributed information systems[END_REF].

Here, content is placed a priori according to estimated content popularity.

All parties involved benefit from a high cache hit rate both in terms of page hit rate (share of requests served from cache) and byte hit rate (page hit rated weighted by file sizes). Assuming that web caches are maintained by an ISP, the following trade-offs are connected to caching: § CPs trade off a reduction of load on data center against less knowledge about its users since they cannot control who downloads cached content. § ISPs save financial cost for file transfer from other network operators and gain better Quality of Service (QoS) for their users but they incur financial cost for installation and maintenance of caches. § Client get improved delay and QoS while some security issues may arise. There are large CPs that rely completely on third-party infrastructure for content delivery. For example, Netflix does not operate any data centers any more but has migrated completely to AWS [START_REF] Izrailevsky | Completing the Netflix Cloud Migration[END_REF]. Additionally, Netflix Abstract : The massive increase in cellular traffic poses serious challenges to all actors concerned with wireless content delivery. While network densification provides access to additional users, high-speed and high-capacity backhaul connections are expensive. Caching popular content at the network edge promises to offload user traffic from these congestion prone connections as well as from the data centers in the backbone network. This thesis proposes a business model in which a mobile network operator (MNO) pre-installs and maintains caches at its wireless equipment (Cached Base Stations, CBSs). Memory space together with computational capabilities is then leased to content providers (CPs) that want to bring their content closer to the user. For a financial compensation, a CP can then offload traffic from its data center and improve user Quality of Service. The CP makes content placement decisions based on user traffic and content popularity data. In the delivery phase, users can be served from the caches in case they are associated to stations that have the requested content cached. This work investigates three aspects of the proposed business model: The first research question focuses on user association as a central element to the edge caching scheme. Cache-aware user association policies can allow for users in coverage overlap areas to be associated to a CBS that holds the requested content rather than conventionally to the one that provides the strongest signal. The thesis pro-poses an original decentralized algorithm for user association called Generalized Bucket-filling that allows gains beyond maximizing the hit ratio. Performance metrics such as network throughput and load balancing of users among CBSs are taken into account. Experiments show that cache-aware user association a) increases the hit ratio b) without overloading single CBSs while c) providing high system throughput. The second problem treated considers a single CP that needs to decide how much cache space to lease at each CBS for a fixed price, and what content to place. Its choices should be based on estimates of file popularity as well as MNO user association policy. The cache leasing and content placement problem is formulated as a non-linear mixed-integer problem (NLMIP). In its solution, the problem is separated into a linear discrete CP subproblem and a nonlinear continuous subproblem using Benders decomposition. The CP and the MNO cooperate, helping the CP to make optimal decisions that benefit both parties: The CP maximizes its savings from caching while the MNO can find the optimal cache price and receive the maximum financial compensation. A third research question widens the focus to the interaction between several CPs and one MNO. Now, the MNO does not set a fixed price per memory unit but instead reacts to CP demands for memory space that depend on the savings they can achieve from caching.

A.3.2 Data Centers and Content Delivery Networks

Universit é Paris-Saclay

Espace Technologique / Immeuble Discovery Route de l'Orme aux Merisiers RD 128 / 91190 Saint-Aubin, France

Figure 1

 1 Figure 1.1: Content delivery in a wireless network.

Figure 1

 1 Figure 1.2: Three BSs whose coverage areas overlap. Users in the overlap regions can potentially be associated to any covering BS.

Figure 1

 1 Figure 1.3: A tree-like network

Chapter 7

 7 schemes have been approached from a competitive [PMGEA16, MMPC17] and a cooperative [PIP `16, DEAH17] perspective. In [PIP `16], Poularakis et al. propose offloading of backhaul traffic to local caches jointly optimizing caching incentive, content placement and routing policies. However, their

  schemes.

In 2005 ,

 2005 Newman [New05] proposed and verified the Zipf distribution to well approximate the hit distribution of Internet content. Many works on wireless edge caching are based on this distribution as the assumption for content popularity, e.g. [SGD `13, PT13, BBD14, WCT `14]. However, it has been shown that spatio-temporal differences in user behaviour do affect the efficacy of caching-related decisions [MWZ `17, BNGP17].

Figure 3

 3 Figure 3.1: Cached wireless network run by the MNO, caches leased by the CP.

  Figure 3.2: Hit ratio for Random content placement policies with fixed cache sizes.

Figure 3

 3 Figure 3.3: A user that can potentially be associated to three CBSs.

  Figure 4.1: Toy example of network regions.

  w m,s,f ą 0 if users from region s requesting f are associated to CBS m

Figure 4

 4 Figure 4.2: A network with refined regions consisting of two CBSs.

Fig. 4 .

 4 Fig. 4.2 shows an example of network regions with corresponding wireless performance weights based on the SINR. The circular areas with solid line depict the areas around each CBS where the received signal emitted by thisstation is above a certain threshold. For each CBS, we choose here to differentiate between two zones of signal strength (strong, weak), separated by the dashed lines. In the regions where there is disc overlap, users experience interference from the CBS they are not associated to. We can identify in this way 7 different regions with different overlaps. The SINR represented in the weights w m,s,f value the signal of m as beneficial and the other's as

Figure 4 . 3 :

 43 Figure 4.3: Illustration of the Bucket-filling algorithm.

Figure 4 . 4 :

 44 Figure 4.4: Minimum and maximum load share of a CBS in the network depending on the mean coverage number.

Fig. 4 .

 4 Fig. 4.4 illustrates how the routing decisions of each of the three policies affect the distribution of load shares among all CBSs. It displays the average maximum (upper curve) and minimum load share (lower curve) over the

  4.6). The first tier consists of large CBSs having a 187.5 m coverage radius while the second tier of small CBSs has 62.5 m coverage radius. The large CBSs are equipped with caches and the two most popular files are stored in all of them. The smaller CBSs get one of these two files assigned uniformly randomly in their cache.

Figure 4 . 5 :

 45 Figure 4.5: Aggregate traffic share of large CBSs depending on the amount of small CBSs.

Figure 4 . 6 :

 46 Figure 4.6: Minimum and maximum load share of a small (2nd tier) CBS depending on the ratio of small CBS number over large CBS number.

Fig. 4

 4 Fig. 4.6 shows (as in Fig. 4.4) the maximum and minimum traffic load

Figure 4

 4 Figure 4.7: Hit ratio achieved for different content placements with user association maximizeing throughput under Opt-h and 1-freq.

Figure 4

 4 Figure 4.8: Relative Hit ratio gain with user association Opt-h maximizing throughput over Closest.

Figure 4

 4 Figure 4.9: System throughput gained with user association maximizing throughput over Closest.

  Now, we show a polynomial-time reduction from the Helper Decision problem (HD) presented in [SGD `13]. The reduction identifies users (in HD) with regions (in CLCP) and helpers (HD) with CBSs (CLCP). An instance of HD is transformed into a CLCP instance in the following way: Setting b f " b MU " 1 and k m " M and all prices p m to 0 eliminates the variables z m and provides that (5.1) and (5.2) are equivalent to the capacity constraint in HD.

Figure 5 . 1 :

 51 Figure 5.1: Hit ratio maximization: Hit ratio in relation to price for different coverage radii with Opt-h association.

Figure 5

 5 Figure 5.3: Linear savings function: Relative difference between the hit ratio achieved by optimal leasing and placement under Opt-h association to Closest association over cache unit price for different coverage radii.

Figure 5

 5 Figure 5.4: Hit ratio maximization: Income of MNO in relation to price per cache unit for different coverage radii with optimal leasing and placement under Opt-h association.

Figure 5 . 5 :

 55 Figure 5.5: Hit ratio maximization: MNO income/CP investment over hit ratio for different coverage radii with Opt-h. Achieving the hit ratio on the x-axis results in the MNO income on y-axis.

Figure 5 . 6 :Figure 5

 565 Figure 5.6: Hit ratio maximization: Hit ratio in relation to Zipf parameter for different prices with Opt-h.

  5.7), is distributed to the less loaded CBSs. The two upper (solid) lines in the graph represent the maximum load of a CBS in relation to the overall covered population per CBS both in the cases LB.a) and LB.b). The two lower (dashed) lines are the minium loaded CBS. The maximum loaded CBSs in both LB.a) and LB.b) coincide as the figure shows. The minimum loaded CBS of LB.a) is higher than the LB.b), showing that excess users coming from the higher hit ratio Figure 5.7) are associated to the less loaded stations.

Figure 5 .

 5 Figure 5.10: Hit ratio for different content placement policies with fixed cache sizes and spatially inhomogeneous traffic with linear savings function.

  CLCP problem with 0 prices under linear savings function with Opt-h user association. The Closest results are the respective results with Closest user association. All other results are derived from different content placement policies together with Opt-h user association. Similar results have already been presented in Section 4.6, in which the optimized content placement policies are not yet included.

Figure 5 .

 5 Figure 5.11: Hit ratio when the Zipf parameter of the actual content popularity diverges from the Zipf parameter on which the leasing and placement decisions are based.

Figure 5 . 12 :

 512 Figure 5.12: Throughput optimization by weighted savings function: Throughput per cache investment.

h

  prq pz prq q s.t.(6.1).This chapter provides a preliminary investigation of a relaxed and simplified version of SW, making three assumptions: a) SW is relaxed by removing the integrality constraint on the variables z prq m , as well as, implicitly, the variables x prq m,f . Thus, we allow assignment of fractional cache space. Fractional content placement can be interpreted as probabilistic content placement. b) SW is simplified by imposing that all CBSs have the same amount of cache space k installed. c) The cache memory is split in the same way at every CBS, i.e. z prq m " z prq m 1 for all m, m 1 . This uniform cache allocation to CP r is denoted by z prq . Then, the simplified and relaxed problem is pSWsrq max z prq PR |R| ě0 ,rPR ÿ rPR h prq pz prq q s.t. ÿ rPR z prq ď k.

7. 1

 1 scheme's effectiveness. § Leasing and placement based on Opt-h is superior to Closest particularly in scenarios in which inter-cell interference is reduced through the use of orthogonal frequency bands on neighboring stations.

  3 allocates the cache space to several CPs at a generic CBS. How can the more general model be solved when different cache allocations are allowed at each CBS? § In the solution to the cache allocation model, the integrality constraint on leasing and placement are relaxed. How can the model be solved including integrality, allocating entire cache units? § The model can furthermore be extended to include several competing MNOs that offer edge caching services to the CPs. The MNOs that potentially have different user demographics which implies different content popularity statistics per MNO for a CP. The MNOs might also offer different user association policies. Each CP then needs to decide how to split the financial resources among the MNOs to maximize their savings.

  Data CentersWith the rapid growth of Internet traffic in the late 1990s, the combination of E2E delivery and web caching proved to be insufficient. Smaller websites continue to be hosted on central servers that may consist only of one single computer, thus risking service outage in case of physical failure of the server or a request overload. Furthermore, single servers have limitations both regarding the data rate and the number of clients that can be served simultaneously. Even if server capacity constraints are not a limiting factor, delivery delay may be become an issue in case of greater network distance between client and server.Large CPs such as Youtube rely on much more involved networks of servers called data centers. Data centers are clusters of servers (or: computational nodes). The purpose of data centers is to handle massive numbers of content requests. Request load can be balanced between different servers.Content access from every server is provided by low latency, high capacity interconnections between the servers. Various architectures for these links are applied in practice[START_REF] Al-Fares | A scalable, commodity data center network architecture[END_REF].Content Delivery NetworksSeveral companies have emerged that combine large scale data centers around the world to Content Delivery Networks (CDNs). CDNs consist of several points of presence (PoPs) at which network caches are deployed, together with switches that provide server-load balancing and request routing. Following[START_REF] Hofmann | Content networking: architecture, protocols, and practice[END_REF], a CDN is defined as a communication network that deploys infrastructure components operating at protocol Layers 4-7. These components interconnect with each other, creating a virtual network layered on top of an existing packet network infrastructure. Its functions can include § Content distribution: Services for transmitting the requested content from the original data center or one of the caches to the user. § Request-routing: Services for navigating user requests to a location best suited for retrieving the requested content. § Content processing: Adapting the requested content to suit user preferences and device capabilities, i.e. adaptation of content to wireless devices. § Authorization, authentication, and accounting: Providing user tracking to the CP as well as ensuring user identity to all parties of the file transmission.CDNs resolve some of the drawbacks of traditional web caching, in particular regarding individualized content. The security/encryption question can only be resolved if user and CP trust the CDN provider to be an intermediary in their secure communication.As an example, Google/Youtube owns 15 data centers that are distributed around the world, thus decreasing geographic effects on the delivery delay to clients[Dat18]. In 2017, it was estimated that the total amount of servers in these Google data centers was around 2.5 million. According to Google itself, their recently opened Data Center in Eemshaven (Netherlands) alone was an investment of 600 million e that also includes fast and high capacity links to the surrounding network [Goo18].Other known CDN providers include Akamai and Amazon Web Services (AWS) that sell CDN services to various content providers. Some CDNs provide the named services only for the content of specific CPs, such as Google Global Cache (service for Youtube) and Facebook Photo CDN (see[PIT `18]).

FNywR

  itself offers caching infrastructure to network operators called Netflix Open Connect. This project consists of Netflix placing caches either within internet exchange points or inside the networks of ISPs[Net18]. The hardware for these Open Connect Appliances (OCAs) are provided by Netflix while the ISPs provide power, space and connectivity. The cache management remains with Netflix. The company executes cache updates in off-peak hours to bring their content closer to the user and decongest the ISP network. Content catalog of typical CP f Content file Π User association policy, e.g. Opt-h or Closest S Π Network regions depending on association policy Π S Network regions in case association policy is clear s Single network region x m,f decision variable/parameter indicating if file f is placed in CBS m x vector of placement variables N s,f Expected number of CP users in region s requesting file f Content popularity vector y m,s,f Variable indicating number of users in region s requesting file f associated to CBS m User association vector Y Π Domain of feasible user association vectors under association policy Π hp¨q Savings function of the MNO or CP, depending on context: h MNO p¨q, h CP p¨q or h prq p¨q w m,s,f Weights referring to user association U m p¨q Utility function for CBS m Weight vector referring to user association v w m pyq Weighted traffic volume associated to CBS m with user association y q q " ps, f q, tuple of region and file, called region-file Q Set of region-files k m Number of memory units installed at CBS m z m Variable indicating the number of memory units leased at m z Vector of cache leasing variables X Domain of feasible tuples px, zq b f Size of file f b MU Size of memory units p m Price per memory unit at CBS m Set of CPs r CP, in case several are considered d r Bid by CP r d ´r Vector of all bids except CP r P prq p p¨q Payoff function for price taking CP r for price p Q prq p¨q Payoff function for price anticipating CP r for price p Table C.2: Notation Titre :Gestion de contenu optimale et dimensionnement de memoire dans les r éseaux sans fil Mots cl és : Contenu, R éseau sans fil, Cache, Station de base, M émoire, Planification R ésum é : L'augmentation massive du trafic cellulaire pose de s érieux d éfis à tous les acteurs concern és par la diffusion de contenu sans fil. Alors que la densification du r éseau permet d'acc éder à des utilisateurs suppl émentaires, les liaisons de transport à grande vitesse et à grande capacit é sont co ûteuses. La mise en cache du contenu populaire au bord du r éseau promet permettre de d écharger le trafic utilisateur de ces connexions, susceptibles d' être encombr ées, ainsi que des centres de donn ées du r éseau f éd érateur. Cette th èse propose un mod èle commercial dans lequel un op érateur de r éseau mobile (MNO) pr éinstalle et entretient des caches sur son équipement sans fil (stations de base avec cache, CBS). L'espace m émoire ainsi que les capacit és de calcul sont ensuite lou és aux fournisseurs de contenu (CP) qui souhaitent rapprocher leur contenu à l'utilisateur. Pour une compensation financi ère, un CP peut alors d écharger le trafic de son centre de donn ées et am éliorer la qualit é de service des utilisateurs. Le CP prend des d écisions de placement de contenu en fonction des donn ées pr édictives sur le trafic des utilisateurs et la popularit é du contenu. Dans la phase de livraison, les utilisateurs peuvent être desservis à partir des caches au cas o ù ils seraient associ és à des stations sur lesquelles le contenu demand é est mis en cache. Ce travail examine trois aspects du mod èle commercial propos é: La premi ère question de recherche porte sur l'association des utilisateurs en tant qu' él ément central du sch éma de mise en cache au bord du r éseau. Les strat égies d'association des utilisateurs prenant en charge le cache peuvent permettre aux utilisateurs des zones de chevauchement de couverture d' être associ és à une CBS contenant le contenu demand é plut ôt que conventionnellement à celui qui fournit le signal le plus puissant. La th èse propose un algorithme d écentralis é original pour l'association d'utilisateurs appel ée Generalized Bucketfilling qui permet des gains au-del à de la maximisation du taux de r éussite (hit ratio). Les mesures de performance telles que le d ébit du r éseau et l' équilibrage de la charge des utilisateurs parmi les CBS sont prises en compte. Des exp ériences montrent que l'association des utilisateurs au cache a) augmente le taux de r éussite b) sans surcharger les CBS uniques c) tout en fournissant un d ébit élev é du syst ème. Le deuxi ème probl ème trait é concerne un seul CP qui doit d écider combien d'espace de cache à louer à chaque CBS pour un prix fixe et du contenu à placer. Ses choix doivent être bas és sur des estimations de la popularit é des fichiers ainsi que sur la politique d'association des utilisateurs MNO. Le probl ème de leasing et de placement du contenu du cache est formul é sous la forme d'un probl ème non lin éaire à nombres entiers mixtes (NLMIP). Dans sa solution, le probl ème est s épar é en un sous-probl ème CP lin éaire discret et un sous-probl ème continu non lin éaire utilisant la d écomposition de Benders. Le CP et le MNO coop èrent, aidant le CP à prendre des d écisions optimales qui profitent aux deux parties: Le CP maximise ses économies gr âce à la mise en cache tandis que le MNO peut trouver le prix de cache optimal et recevoir la compensation financi ère maximale. Une troisi ème question de recherche élargit la port ée de l'interaction entre plusieurs CPs et un op érateur de r éseau mobile. D ésormais, le MNO ne fixe pas de prix fixe par unit é de m émoire, mais r éagit aux demandes du CP en mati ère d'espace m émoire en fonction des économies r éalis ées gr âce à la mise en cache. Title : Optimal Content Management and Dimensioning in Wireless Networks Keywords : Content, Wireless Network, Cache, Base Station, Memory, Scheduling

. When the request sequence is stationary, LFU optimizes performance by giving advantage to content that is requested with

	works pursuing online caching policies include [LPG `16, TAG `15, NCM17,
	PIP `16, DJS `17, DCNT17, GH17].
	higher frequency [DMT `16]. With TTL policies, the hit rate of different files
	can be adjusted individually. More recent research focuses on time-varying
	content popularity [ER15, LSLS18] modelling eviction policies as Markov
	chains.
	Many works have applied variations of LRU to edge caching. Giovanidis
	and Avranas [GA16] exploit coverage overlaps in wireless networks under
	spatially varying content popularity. The resulting caching policy is called
	multi-LRU. The hit ratio is computed using the Che approximation. Other

  .1) This constraint allows for possible splitting of the population N s,f among the CBSs in Mpsq. The set of association vectors feasible to this constraint set Since we are only interested in cache-hit traffic, y m,s,f can only be nonzero if x m,f " 1, i.e. if object f is cached in station m. Since no more than the total population requesting content f in s can be included in y m,s,f , the following constraint set is valid:

	is denoted by
	Y Π :" y P R ř mPM |S Π pmq||F | ě0	ˇˇ(4.1) (	.

  Opt´h MNO pxqq ď h MNO py Opt´h MNO px 1 qq, then h CP and h MNO are UA-equivalent or h CP " h MNO . This can be justified by the leasing contract between CP and MNO, and also by the common interest in caching. Non-UA-equivalent savings functions are subject for future research.

In Section 4.3, it was shown how performance criteria for user association can be translated into MNO savings functions. The above definition allows the translation of performance criteria for content placement into CP savings functions: A CP savings function h CP measures a performance criterion, if an UA-equivalent MNO savings function h MNO exists that measures the performance criterion.

  Then, the MNO allocates the cache space to the CPs such that the values z prq are proportional to d r . This is achieved by making all CPs pay the same price p per memory unit such that z prq " d r {p. The entire cache memory is used, i.e. the market is cleared, if the price p is chosen such that

	6.3.1 Proportional Allocation
		ÿ rPR	d r k	" p.	(6.2)
	This is possible if	ř

Since the savings functions h prq are not available to the MNO, the problem SWsr is not solved in a straightforward way but through the proportional allocation mechanism [NRTV07, Chapter 21]. Each CP r places a bid d r to the MNO for cache access. The bid d r represents the financial investment that CP r is willing to make to gain access to the caches. rPR d r ą 0.

  For example, it is possible that traffic and popularity predictions for certain content is more exact than for other content, or the predictions differ depending on location. Statistics on data exactness can be taken into account applying methods of stochastic optimization. § How should a mechanism be designed that associates individual users to the CBSs in the delivery phase, such that the distribution of users closely matches the results of the accumulative user association in

	Chapter 4?
	7.2.2 Non-cooperation between MNO and CP

In Chapter 5, a CP optimizes cache leasing and content placement decisions, given the MNO user association policy. It is assumed that the objectives of CP and MNO regarding user association are equivalent, i.e. that the MNO associates users in a way that maximizes the CP savings. The work can be continued by investigating: § How are CP decisions affected if the MNO associates users aiming at a different objective than the MNO? For example, the CP might want to maximize throughput while the MNO aims at load balancing.

Acknowledgements

System Model and Problem Statement

Cache Leasing and Content Placement

We consider a cellular communications network with a finite set M of CBSs.

Each CBS m is equipped with k m memory units of size b MU (in MBytes, e.g. 1000) which the CP can lease. Leasing and placement decisions are taken at the beginning of a long time window (and stay fixed throughout) during which content popularity statistics are assumed static. Denoting the decision variable of how many cache units to lease (see CP-1, Section 3.1.3) at m by z m P Z ě0 , the bounded availability of memory gives the constraint set z m ď k m , @ m P M.

(5.1)

The vector of the cache leasing variables is z " pz m q mPM .

Having leased cache space at the CBSs, the CP places content from a finite object catalog F into the caches (see CP-2, Section 3.1.3). The decision to store content f in the cache of m will set the variable x m,f to 1, otherwise

x m,f " 0. The vector of content placement variables is x " px m,f q mPM,f PF .

Each file has a given file size b f (in MBytes), and all file-sizes are known.

The limited capacity of the leased cache space gives the second constraint set

For convenience, we define the set of feasible tuples of leasing and placement vectors as X :" px, zq P t0, 1u |M||F | ˆZ|M| ě0 ˇˇ(5.1), (5.2)

Wireless Environment

For the wireless communication model, see Section 4. of popularity rank 11 to 20 and so on. For the lowest cache price (0.01e), all 100 available units are leased: For both assignment policies, the amount of leased cache memory decreases with increasing price. For all prices, Fig. 5.2

shows that the less popular files are represented more frequently with Opt-h than with Closest, especially for prices ě 0.1e. There is more diversity of visible content with the Opt-h association. ation, each right column the optimal decisions taken for Closest association.

The height is the average amount of cache units leased per CBS. The inner sections of the columns represent the content placement in all of the CBSs:

The lowest section are the 10 most popular files, the second lowest the files ranked 11 to 20 and so on. It can be seen that particularly for low cache unit prices, the diversity of cached content is higher in case LB.a) than in case LB.b). For the lowest price (0.01e), Closest provides only content from the more popular half of the catalog, while the optimal content placement under Opt-h association places content from the tail of the catalog as well. In [NRTV07, Chapter 21] it is shown that such a Nash equilibrium exists with ř r d prq ą 0 and that it is unique. The related vector pz prq q, r P R is the solution to the following optimization problem:

where ĥprq pzq " p1 ´z{kq h prq pzq `pz{kq ´1{z

In [NRTV07, Chapter 21], the author shows that the Nash equilibrium loses no more than 25% in comparison to the optimal solution of SWsr, i.e. if z G " pz prq G q is a solution to GAME and z ˚" pz prq ˚q is optimal to SWsr, then

Conclusions

This section models multiple CPs that compete for the same cache resources.

The MNO acts as a neutral arbiter that sets cache prices such that the cache resources are completely used. A game is designed that, for the case that each cache is divided in the same way among the CPs and relaxing the integrality of cache units, provides a high quality Nash equilibrium. An optimization problem is given that helps attaining the Nash Equilibrium in practice.

The following questions, relating to the assumptions made in Section 6. This way, they were made available throughout Mesopotamia and ready to be enjoyed and studied by kings and priests without the need to travel to or even conquer neighboring archives.

According to estimates, the Library of Alexandria, founded around 300 BC, contained up to 600,000 scrolls of papyrus. Many works were lent from other parts of the ancient world, and copied and catalogued on arrival. Alexandria is considered revolutionary as a center of science of the ancient world.

The improvement of printing techniques around 1450 allowed the reproduction of texts allowed for the easier reproduction of religious as well as nonreligious texts. One of the most ambitious projects using printing techniques was the Encyclopédie (published between 1751 and 1772). Its objective was, among other political goals, to make the world's knowledge available to effectively all the French elite. It is considered that the spread of ideas through the Encyclopédie contributed to the French Revolution 1789.

These examples show that copy and distributed storage of information reaches back through the ages. Through the placement of copies in various locations, different objectives were achieved: Information was made available for certain publics. Thus, the information was spread more efficiently. Delay of information access as well as danger of information loss were decreased.

A.2 Caches in Computers

In computing and computer networks, hardware or software components that store data in order to serve future requests of that data faster than the main The memory hierarchy consists of several levels of memory storage. The higher the memory is in the hierarchy, the lower is its access time (MAT). At the same time, the faster the memory is, the more expensive and thus smaller it is. Caches are located in the memory hierarchy between the CPU registers (highest level) and the random access memory. In modern general-purpose computers, the caches make up three sublevels, L1 to L3. As an example, the minimum access times and sizes of the cache levels in the Intel Skylake microarchitecture (see [START_REF]Intel. Intel 64 and IA-32 Architectures Optimization Reference Manual[END_REF]), produced since 2015, are listed in a data request, it consecutively searches the memory hierarchy until it finds the data. This way, the illusion of a large and fast memory is created: The amount of data that is frequently requested is relatively small in comparison to the total amount of data in the lowest memory level. This is due to the temporal and the spatial locality principle. The former describes the probability tha data that was recently requested will soon be requested again.

The latter states that if a data location is referenced, data locations with nearby adresses will be referenced soon.

Read request run level by level through the memory hierarchy from top towards bottom until the data is found. From level to level, the hit time, i.e. the time it takes to retrieve the requested data, increases. The miss penalty for a memory level is the time it takes to retrieve the data from a lower memory level and place the content on all memory levels up to the top.

When a miss occurs, the retrieved from the lower level replaces some on the current level. One classic replacement policy is LRU, in which the item least recently used is replaced.

A.3 Existing Caching Infrastructure

A.3.1 World Wide Web and Network Caches

The World Wide Web is originally designed for end-to-end (E2E) data connections [START_REF] Huston | Web caching[END_REF]. Content requests are routed from the client's device to the CP's content storage. From there, the requested content is delivered via the backbone network and the network of the client's Internet Service Provider (ISP) to the client's device. This design has several advantages over a more decentralized approach: § Coherence: When content is modified at the central storage, the new version will be delivered at every future request. § Individualized Content: Using some form of security model, clients can be authenticated and receive privileged information. § Tracking: The IDs and contextual information of the clients can be tracked in a centralized fashion. § Security: E2E encryption, for example using Transport Layer Security (TLS), can be enabled.

There are, however, also significant drawbacks to the E2E architecture: Single servers as well as data centers providing very popular content are placed under considerable stress. Both the number of simultaneous client connections and the total data throughput are limited. The network surrounding the content storage has traffic limitations as well and can be prone to congestion. Furthermore, the redundant transmission of data to clients in similar locations can create a network overload, and it also incurs financial transmission costs.

With the increasing importance of computer networks in the 1990s, in order to address these drawbacks, the deployment of caching infrastructure became more and more prevalent. www content is cached in various locations of the network. On the one hand, caches are included in browsers making content available locally at the user equipment that has been previously requested. On the other hand, web caches are placed at various positions in the network, between the network edge and the content source. Whenever a client request is passed through a web cache agent, the latter forwards the request to the original source as a proxy for the client. The server's The contents in these publications refer to the following aspects of this thesis.

1. The workshop paper [START_REF] Krolikowski | Fair distributed user-traffic association in cache equipped cellular networks[END_REF] investigates load balancing through cacheaware user association. 2. The conference paper [START_REF] Krolikowski | Optimal cache leasing from a mobile network operator to a content provider[END_REF] establishes the cache leasing business model that is described here in Chapter 3. Furthermore: § The general formulation for the weighted savings function (4.3) in Section 4.2 originates in this paper. § The respective system model and problem statement from the CP perspective appear here in Section 5.2. § The solution in Section 5.4 is largely based on this work. § The numerical evaluation (Section 5.2, in particular 5.6.3 to 5.6.6) is partly based on this article as well.

3. The journal paper [START_REF] Krolikowski | A decomposition framework for optimal edge-cache leasing[END_REF] is an extension of [START_REF] Krolikowski | Optimal cache leasing from a mobile network operator to a content provider[END_REF]. Its original content is: § the generalized solution of user association (Section 4.4), § the complexity analysis of the cache leasing and content placement (CLCP) problem in Section 5.3 and Corollary3, § extended numerical results in Section 5.2, particularly the results discussed in the subsections on policy comparison (5.6.7), sensitivity analysis (5.6.8) and throughput maximization (5.6.9).

Appendix C

Abbreviations and Notation