A logically centralized controller architecture for SDN deployments is a well understood and implemented method, however because of issues such as scalability, privacy and more, there is a need to develop and implement a robust physically distributed SDN controller architecture. In a distributed SDN environment, a centralized logical network view needs to be maintained, which means the distributed controllers need a robust method of remaining informed about other controller's network through synchronization. This is specially true in mobile, wireless networks with changing controller and network environment, so to this end we develop a deep reinforcement and transfer learning based method that provides the controllers with an efficient policy for synchronizing with other controllers and maintaining a logically centralized view in such networks. We show that our application-centric method performs well for different kinds of applications including shortest path routing and load balancing, outperforming a reinforcement learning based method as well as a round robin method.

360-degree panoramic videos have gained considerable attention in recent years due to the rapid development of head-mounted displays (HMDs) and panoramic cameras. One major problem in streaming panoramic videos is that panoramic videos are much larger in size compared to traditional ones. Moreover, the user devices are often in a wireless environment, with limited battery, computation power, and bandwidth. To reduce resource consumption, researchers have proposed ways to predict the users’ viewports so that only part of the entire video needs to be transmitted from the server. However, the robustness of such prediction approaches has been overlooked in the literature: it is usually assumed that only a few models, pre-trained on past users’ experiences, are applied for prediction to all users. We observe that those pre-trained models can perform poorly for some users because they might have drastically different behaviors from the majority, and the pre-trained models cannot capture the features in unseen videos. In this work, we propose a novel meta learning based viewport prediction paradigm to alleviate the worst prediction performance and ensure the robustness of viewport prediction. This paradigm uses two machine learning models, where the first model predicts the viewing direction, and the second model predicts the minimum video prefetch size that can include the actual viewport. We first train two meta models so that they are sensitive to new training data, and then quickly adapt them to users while they are watching the videos. Evaluation results reveal that the meta models can adapt quickly to each user, and can significantly increase the prediction accuracy, especially for the worst-performing predictions.

While recent years have witnessed a steady trend of applying Deep Learning (DL) to networking systems, most of the underlying Deep Neural Networks (DNNs) suffer two major limitations. First, they fail to generalize to topologies unseen during training. This lack of generalizability hampers the ability of the DNNs to make good decisions every time the topology of the networking system changes. Second, existing DNNs commonly operate as "blackboxes" that are difficult to interpret by network operators, and hinder their deployment in practice. In this paper, we propose to rely on a recently developed family of graph-based DNNs to address the aforementioned limitations. More specifically, we focus on a network congestion prediction application and apply Graph Attention (GAT) models to make congestion predictions per link using the graph topology and time series of link loads as inputs. Evaluations on three real backbone networks demonstrate the benefits of our proposed approach in terms of prediction accuracy, generalizability, and interpretability.

Mobile edge computing provides the opportunity for wireless users to exploit the power of cloud computing without a large communication delay. To serve data-intensive applications (e.g., video analytics, machine learning tasks) from the edge, we need, in addition to computation resources, storage resources for storing server code and data as well as network bandwidth for receiving user-provided data. Moreover, due to time-varying demands, the code and data placement needs to be adjusted over time, which raises concerns of system stability and operation cost. In this paper, we address these issues by proposing a two-time-scale framework that jointly optimizes service (code and data) placement and request scheduling, while considering storage, communication, computation, and budget constraints. First, by analyzing the hardness of various cases, we completely characterize the complexity of our problem. Next, we develop a polynomial-time service placement algorithm by formulating our problem as a set function optimization, which attains a constant-factor approximation under certain conditions. Furthermore, we develop a polynomial-time request scheduling algorithm by computing the maximum flow in a carefully constructed auxiliary graph, which satisfies hard resource constraints and is provably optimal in the special case where requests have homogeneous resource demands. Extensive synthetic and trace-driven simulations show that the proposed algorithms achieve 90% of the optimal performance.

Reinforcement Learning (RL) based methods have seen their paramount successes in solving serial decision-making and control problems in recent years. For conventional RL formulations, Markov Decision Process (MDP) and state-action-value function are the basis for the problem modeling and policy evaluation. However, several challenging issues still remain. Among most cited issues, the inefficiency in utilizing training data is an important factor that causes difficulties in accurately approximating the state-action-value function. We observe that although actions directly define the agents' behaviors, for many problems the next state after a state transition matters more than the action taken, in determining the return of such a state transition. In this regard, we propose a new learning paradigm, State Action Separable Reinforcement Learning (sasRL), wherein the action space is decoupled from the value function learning process for higher learning efficiency. Then, a light-weight transition model is learned to assist the agent to determine the action that triggers the associated state transition. Our convergence analysis reveals that under certain conditions, the convergence time of sasRL is O(T1/k), where T is the convergence time for updating the value function in the MDP-based formulation and k is a weighting factor. Experiments on several gaming scenarios show that sasRL outperforms state-of-the-art MDP-based RL algorithms by up to 75%.

Security threats arising in massively connected Internet of Things (IoT) devices have attracted wide attention. It is necessary to equip IoT gateways with firewalls to prevent hacked devices from infecting a larger amount of network nodes. The match-and-action mechanism of Software Defined Networking (SDN) provides the means to differentiate malicious traffic flows from normal ones, which mirrors the past firewall mechanisms but with a new flexible and dynamically reconfigurable twist. However, vulnerabilities of IoT devices and heterogeneous protocols coexisting in the same network challenge the extension of SDN into the IoT domain. To overcome these challenges, we leverage the high level of data plane programmability brought by the P4 language and design a novel two-stage deep learning method for attack detection tailored to that particular language. Our method is able to generate flow rules that match a small number of header fields from arbitrary protocols while maintaining high performance of attack detection. Evaluations using network traces of different IoT protocols show significant benefits in accuracy, efficiency and universality over state-of-the-art methods.

Recent advances in network virtualization and programmability enable innovative service models such as Service Chaining (SC), where flows can be steered through a pre-defined sequence of service functions deployed at different cloud locations. A key aspect dictating the performance and efficiency of a SC is its instantiation onto the physical infrastructure. While existing SC Embedding (SCE) algorithms can effectively address the instantiation of SCs consuming computation and communication resources, they lack efficient mechanisms to handle the increasing data-intensive nature of next-generation services. Differently from computation and communication resources, which are allocated in a dedicated per request manner, storage resources can be shared to satisfy multiple requests for the same data. To fill this gap, in this paper, we formulate the data-intensive SCE problem with the goal of minimizing storage, computation, and communication resource costs subject to resource capacity, service chaining, and data sharing constraints. Using a randomized rounding technique that exploits a novel data-aware linear programming decomposition procedure, we develop a multi-criteria approximation algorithm with provable performance guarantees. Evaluation results show that the proposed algorithm achieves near-optimal resource costs with up to 27.8% of the cost savings owed to the sharing of the data.

The proliferation of innovative mobile services such as augmented reality, networked gaming, and autonomous driving has spurred a growing need for low-latency access to computing resources that cannot be met solely by existing centralized cloud systems. Mobile Edge Computing (MEC) is expected to be an effective solution to meet the demand for low-latency services by enabling the execution of computing tasks at the network edge, in proximity to the end-users. While a number of recent studies have addressed the problem of determining the execution of service tasks and the routing of user requests to corresponding edge servers, the focus has primarily been on the efficient utilization of computing resources, neglecting the fact that non-trivial amounts of data need to be pre-stored to enable service execution, and that many emerging services exhibit asymmetric bandwidth requirements. To fill this gap, we study the joint optimization of service placement and request routing in dense MEC networks with multidimensional constraints. We show that this problem generalizes several well-known placement and routing problems and propose an algorithm that achieves close-to-optimal performance using a randomized rounding technique. Evaluation results demonstrate that our approach can effectively utilize available storage, computation, and communication resources to maximize the number of requests served by low-latency edge cloud servers.

In distributed software-defined networks (SDN), multiple physical SDN controllers, each managing a network domain, are implemented to balance centralized control, scalability and reliability requirements. In such networking paradigm, controllers synchronize with each other to maintain a logically centralized network view. Despite various proposals of distributed SDN controller architectures, most existing works only assume that such logically centralized network view can be achieved with some synchronization designs, but the question of how exactly controllers should synchronize with each other to maximize the benefits of synchronization under the eventual consistency assumptions is largely overlooked. To this end, we formulate the controller synchronization problem as a Markov Decision Process (MDP) and apply reinforcement learning techniques combined with deep neural network to train a smart controller synchronization policy, which we call the Deep-Q (DQ) Scheduler. Evaluation results show that DQ Scheduler outperforms the anti-entropy algorithm implemented in the ONOS controller by up to 95.2% for inter-domain routing tasks.

In distributed software-defined networks (SDN), multiple physical SDN controllers, each managing a network domain, are implemented to balance centralised control, scalability, and reliability requirements. In such networking paradigms, controllers synchronize with each other, in attempts to maintain a logically centralised network view. Despite the presence of various design proposals for distributed SDN controller architectures, most existing works only aim at eliminating anomalies arising from the inconsistencies in different controllers' network views. However, the performance aspect of controller synchronization designs with respect to given SDN applications are generally missing. To fill this gap, we formulate the controller synchronization problem as a Markov decision process (MDP) and apply reinforcement learning techniques combined with deep neural networks (DNNs) to train a smart, scalable, and fine-grained controller synchronization policy, called the Multi-Armed Cooperative Synchronization (MACS), whose goal is to maximise the performance enhancements brought by controller synchronizations. Evaluation results confirm the DNN's exceptional ability in abstracting latent patterns in the distributed SDN environment, rendering significant superiority to MACS-based synchronization policy, which are 56% and 30% performance improvements over ONOS and greedy SDN controller synchronization heuristics.

The proliferation of innovative mobile services such as augmented reality, networked gaming, and autonomous driving has spurred a growing need for low-latency access to computing resources that cannot be met solely by existing centralized cloud systems. Mobile Edge Computing (MEC) is expected to be an effective solution to meet the demand for low-latency services by enabling the execution of computing tasks at the network-periphery, in proximity to end-users. While a number of recent studies have addressed the problem of determining the execution of service tasks and the routing of user requests to corresponding edge servers, the focus has primarily been on the efficient utilization of computing resources, neglecting the fact that non-trivial amounts of data need to be stored to enable service execution, and that many emerging services exhibit asymmetric bandwidth requirements. To fill this gap, we study the joint optimization of service placement and request routing in MEC-enabled multi-cell networks with multidimensional (storage-computation-communication) constraints. We show that this problem generalizes several problems in literature and propose an algorithm that achieves close-to-optimal performance using randomized rounding. Evaluation results demonstrate that our approach can effectively utilize the available resources to maximize the number of requests served by low-latency edge cloud servers.

Since the early development of Software-Defined Network (SDN) technology, researchers have been concerned with the idea of physical distribution of the control plane to address scalability and reliability challenges of centralized designs. However, having multiple controllers managing the network while maintaining a “logically-centralized” network view brings additional challenges. One such challenge is how to coordinate the management decisions made by the controllers which is usually achieved by disseminating synchronization messages in a peer-to-peer manner. While there exist many architectures and protocols to ensure synchronized network views and drive coordination among controllers, there is no systematic methodology for deciding the optimal frequency (or rate) of message dissemination. In this paper, we fill this gap by introducing the SDN synchronization problem: how often to synchronize the network views for each controller pair. We consider two different objectives; first, the maximization of the number of controller pairs that are synchronized, and second, the maximization of the performance of applications of interest which may be affected by the synchronization rate. Using techniques from knapsack optimization and learning theory, we derive algorithms with provable performance guarantees for each objective. Evaluation results demonstrate significant benefits over baseline schemes that synchronize all controller pairs at equal rate.

Software defined networking (SDN) can be beneficial in mobile ad hoc networks (MANETs) to increase flexibility, provide programmability and simplify management. The high dynamics in mobile networks, however, raise new reliability challenges to the conventional centralized control plane of SDN. To increase reliability, methods such as placing multiple controllers in the network have been considered that add redundancy in the control plane in a brute force manner. However, these methods cannot by themselves fundamentally solve the reliability problem. To address this issue, this paper complements the controller placement methods with a new architecture that has a hybrid structure splitting the routing decision logic between the controllers and the data plane nodes. Specifically, the controllers can break the routing path into segments, similar to the segment routing technique, and broadcast the list of segment labels to the data plane nodes. The latter are able to make the actual forwarding decisions for each segment in a distributed manner, e.g., by running an existing MANET protocol like OLSR. Experiments on a testbed built from commercial mobile devices with integrated SDN functionality highlight the feasibility and benefits of the proposed architecture.

In-network caching constitutes a promising approach to reduce traffic loads and alleviate congestion in both wired and wireless networks. In this article, we study the joint caching and routing problem in congestible networks of arbitrary topology (JoCRAT) as a generalization of previous efforts in this particular field. We show that JoCRAT extends many previous problems in the caching literature that are intractable even with specific topologies and/or assumed unlimited bandwidth of communications. To handle this significant but challenging problem, we develop a novel approximation algorithm with guaranteed performance bound based on a randomized rounding technique. Evaluation results demonstrate that our proposed algorithm achieves near-optimal performance over a broad array of synthetic and real networks, while significantly outperforming the state-of-the-art methods.

WiFi is increasingly used by carriers for opportunistically offloading the cellular network infrastructure or even for increasing their revenue through WiFi-only plans and WiFi on-demand passes. Despite the importance and momentum of this technology, the current deployment of WiFi access points (APs) by the carriers follows mostly a heuristic approach. In addition, the prevalent free-of-charge WiFi access policy may result in significant opportunity costs for the carriers, as this traffic could yield non-negligible revenue. In this paper, we study the problem of optimizing the deployment of WiFi APs and pricing the WiFi data usage with the goal of maximizing carrier profit. Addressing this problem is a prerequisite for the efficient integration of WiFi to next-generation carrier networks. Our framework considers various demand models that predict how traffic will change in response to alteration in price and AP locations. We present both optimal and approximate solutions and reveal how key parameters shape the carrier profit. Evaluations on a dataset of WiFi access patterns indicate that WiFi can indeed help carriers reduce their costs while charging users about 50% lower than the cellular service.

Distributed caching architectures have been proposed for bringing content close to requesters, and the key problem is to design caching algorithms for reducing content delivery delay, which determines to an extent the user Quality of Experience (QoE). This problem obtains an interesting new twist with the advent of advanced layered-video encoding techniques such as Scalable Video Coding. In this paper, we show that the problem of finding the caching configuration of video encoding layers that minimizes delivery delay for a network operator is NP-Hard, and we establish a pseudopolynomial-time optimal solution by using a connection with the multiple-choice knapsack problem. Next, we design caching algorithms for multiple network operators that cooperate by pooling together their co-located caches, in an effort to aid each other, so as to avoid large delays due to fetching content from distant servers. We derive an approximate solution to this cooperative caching problem by using a technique that partitions the cache capacity into amounts dedicated to own and other operators' caching needs. Trace-driven evaluations demonstrate up to 25 percent reduction in delay over existing caching schemes. As a side benefit, our algorithms achieve smoother playback for video streaming applications, with fewer playback stalls and higher decoded quality.

Nowadays, there is a fast-paced shift from legacy telecommunication systems to novel software-defined network (SDN) architectures that can support on-the-fly network reconfiguration, therefore, empowering advanced traffic engineering mechanisms. Despite this momentum, migration to SDN cannot be realized at once especially in high-end networks of Internet service providers (ISPs). It is expected that ISPs will gradually upgrade their networks to SDN over a period that spans several years. In this paper, we study the SDN upgrading problem in an ISP network: which nodes to upgrade and when we consider a general model that captures different migration costs and network topologies, and two plausible ISP objectives: 1) the maximization of the traffic that traverses at least one SDN node, and 2) the maximization of the number of dynamically selectable routing paths enabled by SDN nodes. We leverage the theory of submodular and supermodular functions to devise algorithms with provable approximation ratios for each objective. Using real-world network topologies and traffic matrices, we evaluate the performance of our algorithms and show up to 54% gains over state-of-the-art methods. Moreover, we describe the interplay between the two objectives; maximizing one may cause a factor of 2 loss to the other. We also study the dual upgrading problem, i.e., minimizing the upgrading cost for the ISP while ensuring specific performance goals. Our analysis shows that our proposed algorithm can achieve up to 2.5 times lower cost to ensure performance goals over state-of-the-art methods.

Fog architectures at the network edge are becoming a popular research trend to provide elastic resources and services to end-users, where the processing capacity resides at the network periphery as opposed to traditional data-centers. Despite their momentum, the control plane of these architectures remains complex and challenging to implement. To enhance control capability, in this work, we propose to use Software Defined Networking. SDN moves the control logic off data plane devices and onto external network entities, the controllers. We provide a proof-of-concept implementation of a multi-controller edge system and measure traffic delay and overheads. The results reveal the sensitivity of delay to the location of controllers and the magnitude of inter-controller and controller-node overheads. Guided by the above, we model the problem of determining the placement of controllers in the edge network. Using linearization and supermodular function techniques, we present approximation solutions which perform close to optimal and better than state-of-the-art methods.

Fog architectures at the network edge are becoming a popular research trend to provide elastic resources and services to end-users, where the processing capacity resides at the network periphery as opposed to traditional data-centers. Despite their momentum, the control plane of these architectures remains complex and challenging to implement. To enhance control capability, in this paper, we propose to use software defined networking (SDN). SDN moves the control logic off data plane devices and onto external network entities, the controllers. We provide a proof-of-concept implementation of a multi-controller edge system and measure traffic delay and overheads. The results reveal the sensitivity of delay to the location of controllers and the magnitude of inter-controller and controller-node overheads. Guided by the above, we model the problem of determining the placement of controllers in the edge network. Using linearization and supermodular function techniques, we present approximation solutions which perform close to optimal and substantially better than state-of-the-art methods. Finally, we analyze the interplay between various performance and reliability objectives.

Nowadays, there is a fast-paced shift from legacy telecommunication systems to novel Software Defined Network (SDN) architectures that can support on-the-fly network reconfiguration, therefore, empowering advanced traffic engineering mechanisms. Despite this momentum, migration to SDN cannot be realized at once especially in high-end cost networks of Internet Service Providers (ISPs). It is expected that ISPs will gradually upgrade their networks to SDN over a period that spans several years. In this paper, we study the SDN upgrading problem in an ISP network: which nodes to upgrade and when. We consider a general model that captures different migration costs and network topologies, and two plausible ISP objectives; first, the maximization of the traffic that traverses at least one SDN node, and second, the maximization of the number of dynamically selectable routing paths enabled by SDN nodes. We leverage the theory of submodular and supermodular functions to devise algorithms with provable approximation ratios for each objective. Using real-world network topologies and traffic matrices, we evaluate the performance of our algorithms and show up to 54% gains over state-of-the-art methods. Moreover, we describe the interplay between the two objectives; maximizing one may cause a factor of 2 loss to the other.

Caching popular content files at small-cell base stations (SBSs) has emerged as a promising technique to meet the overwhelming growth in mobile data demand. Despite the plethora of work in this field, a specific aspect has been overlooked. It is assumed that all users remain stationary during data transfer and therefore a complete copy of the requested file can always be downloaded by the associated SBSs. In this work, we revisit the caching problem in realistic environments where moving users intermittently connect to multiple SBSs encountered at different times. Due to connection duration limits, users may download only parts of the requested files. Requests for files that failed to be delivered on time by the SBSs are redirected to the coexisting macro-cell. We introduce an optimization framework that models user movements via random walks on a Markov chain aimed at minimizing the load of the macro-cell. As the main contribution, we put forward a distributed caching paradigm that leverages user mobility predictions and innovative information-mixing methods based on the principle of network coding. Systematic experiments based on measured traces of human mobility patterns demonstrate that our approach can offload 65 percent more macro-cell traffic than existing caching schemes in realistic settings.

Distributed caching architectures have been proposed for bringing content close to requesters and the key problem is to design caching algorithms for reducing content delivery delay. The problem obtains an interesting new twist with the advent of advanced layered-video encoding techniques such as Scalable Video Coding (SVC). We show that the problem of finding the caching configuration of video encoding layers that minimizes average delay for a network operator is NP-Hard, and we establish a pseudopolynomial-time optimal solution using a connection with the multiple-choice knapsack problem. We also design caching algorithms for multiple operators that cooperate by pooling together their co-located caches, in an effort to aid each other, so as to avoid large delays due to downloading content from distant servers. We derive an approximate solution to this cooperative caching problem using a technique that partitions the cache capacity into amounts dedicated to own and others' caching needs. Numerical results based on real traces of SVC-encoded videos demonstrate up to 25% reduction in delay over existing (layer-agnostic) caching schemes, with increasing gains as the video popularity distribution gets steeper, and cache capacity increases.

WiFi data offloading provides a promising auxiliary to alleviate network congestion by diverting traffic from the cellular infrastructure onto WiFi access points (APs). Despite the importance and momentum of this method, the current deployment of APs by the carriers follows mostly a heuristic approach. In addition, the prevalent free-of-charge WiFi access approach may result in significant opportunity costs for the carriers as this traffic could yield non-negligible revenues. In this paper, we propose and study the problem of optimizing the deployment of WiFi offloading infrastructure, and pricing the offloading service with the goal of maximizing carrier profits. Addressing this problem is a prerequisite for the efficient integration of WiFi technology to next generation of cellular systems and the development of carrier-grade offloading solutions. Our framework considers a fundamental, intuitive model of carrier costs and revenues, and two demand models that predict how traffic will change in response to alteration in the price and the set of deployed APs. We present both analytical and approximate solutions for this intricate problem, and reveal how key network parameters shape the offloading benefits. Using a dataset of WiFi access patterns collected from real users, we evaluate the impact of offloading for different regional markets around the world. We find that in mature markets WiFi can help carriers reduce their costs, while charging users up to 50% lower than the cellular service. The gains are higher for small "virtual carriers" who resell other's mobile data services (up to a factor of 2). However, in less mature markets where the AP deployment or access costs are higher, deploying APs can actually lead to a net loss for the carrier. Our evaluation code is publicly available for the benefit of research community.

The ever increasing demand for content is straining operators' networks, thereby necessitating development of alternative content delivery mechanisms. Distributed caching architectures constitute a promising solution for mitigating the effects of demand growth by placing popular content files in proximity to users, rather than in a central site. In this paper, we study the content placement problem in multiple-level hierarchical caching networks where user requests for files are routed upwards toward content servers, satisfied by intermediate nodes if the latter have cached the requested files. Our goal is to reduce the server load by serving as many requests as possible by the caches. We show that the problem is NP-Hard in its general form, but it can be solved optimally in polynomial-time when the caches are installed on a single hierarchy path. For the general case, we develop an algorithm achieving a provably better approximation ratio than the best-known counterparts. Numerical experiments show up to 56% reduction in server load over existing algorithms, with gains increasing as the content popularity distributions get steeper and more diverse across nodes, and the cache capacities at the upper hierarchy levels increase. Our evaluation code is publicly available for the benefit of research community.

As the ever growing mobile data traffic challenges the economic viability and performance of cellular networks, innovative solutions that harvest idle user-owned network resources are gaining increasing interest. In this work, we propose leasing wireless bandwidth and cache space of residential 802.11 (WiFi) access points (APs) for offloading mobile data. This solution not only reduces cellular network congestion, but, due to caching, improves also the user-perceived network performance without overloading the backhaul links of the APs. To encourage residential users to contribute their bandwidth and cache resources, we design monetary incentive (reimbursement) schemes. The offered reimbursements directly determine the amounts of available bandwidth and cache space in every AP, which in turn affect the caching policy (where to cache each content file) and the routing policy (where to route each mobile data request). In order to reduce operator's total cost for serving mobile data requests and leasing resources, we introduce a framework for the joint optimization of incentive, caching, and routing policies. Using a novel WiFi usage dataset collected from 167 residences, we show that in densely populated areas with relatively costly network capacity upgrades, our proposal can halve operator's total cost, while reimbursing up to 9€ per month each residential user.

The landscape toward 5G wireless communication is currently unclear, and, despite the efforts of academia and industry in evolving traditional cellular networks, the enabling technology for 5G is still obscure. This paper puts forward a network paradigm toward next-generation cellular networks, targeting to satisfy the explosive demand for mobile data while minimizing energy expenditures. The paradigm builds on two principles; namely caching and multicast. On one hand, caching policies disperse popular content files at the wireless edge, e.g., pico-cells and femto-cells, hence shortening the distance between content and requester. On other hand, due to the broadcast nature of wireless medium, requests for identical files occurring at nearby times are aggregated and served through a common multicast stream. To better exploit the available cache space, caching policies are optimized based on multicast transmissions. We show that the multicast-aware caching problem is NP-hard and develop solutions with performance guarantees using randomized-rounding techniques. Trace-driven numerical results show that in the presence of massive demand for delay tolerant content, combining caching and multicast can indeed reduce energy costs. The gains over existing caching schemes are 19% when users tolerate delay of three minutes, increasing further with the steepness of content access pattern.

Heterogeneous cellular networks that overlay cache-endowed small-cell networks with macro-cell networks have emerged as a promising solution towards ultra-low latency, extra-high throughput, and sub-multiple energy consumption compared to the conventional cellular paradigm. A technique to further improve the energy efficiency of such multi-tier networks is to apply activation mechanisms, that dynamically power on/off a subset of the small-cells and macro-cells. In this work, we show that the activation policy should be jointly derived with the caching policy, that places popular content files at the base station caches. As a result content is fetched effectively closer to the mobile end-users and can be transported via energy-prudent links, while at the same time as many as possible of the base stations are powered off. We then formulate the energy-minimizing problem, which is NP-hard, and introduce a novel approximation framework for its efficient solution. Numerical results, that are based on system parameters driven from real trace datasets, show that our approach provides an excellent performance that is far better than the schemes that perform caching and base station activation in a disjoint manner.

Fueled by the increasing demands for content, Internet has become one of the leading players in energy consumption, with a worldwide share of more than 10%. Network devices typically consume close to the maximum energy even if lightly loaded. Hence, straight-forward energy saving techniques that power-off network devices during periods of low demand constitute the most promising mechanism for reducing energy expenses. In this work, we show how caching policies, that place popular content close to the requesters, can bring opportunities for powering-off network devices. We then formalize the energy-minimizing caching problem, prove that it is NP-Hard to approximate within any constant factor, and present a bicriteria approximation solution. Trace-driven numerical results indicate the superiority of our approach as compared to traditional caching schemes.

In recent years, ISPs in mature residential broadband markets have been moving away from flat-rate pricing schemes to ones that involve usage limits (or "data caps"). These changes have led to a lively debate about the merits of data capping. While previous work has studied the theoretical benefits of data capped pricing models, there is relatively little work that provides insights into exactly how to design data capped tariffs, and their impact on the parties involved, i.e., ISPs and their broadband subscribers. In this paper, we formulate the problem of selecting optimal data capped tariffs based on a simple, extensible model of ISP costs and revenues, and a novel model that captures how users evaluate a set of offered tariffs.

Video delivery to mobile users is one of the largest challenges that network operators face today. In this work we consider a heterogeneous cellular network with storage capable small-cell base stations, and study this problem for pre-stored video files that can be encoded with two different schemes, namely versions or layers, in various qualities. We introduce a framework for the joint derivation of video caching and routing policies for users with different quality requirements. This allows the operator to optimize a balanced objective of incurred servicing cost, and users experienced delay, according to his priorities. The numerical results indicate that versions and layers may have different impact on the delay and servicing cost, depending on the diversity of users' demand, and that the cost-delay trade off is affected by the network's load.

Recently, network coding has emerged as an effective way to increase the efficiency of the content placement in the caching networks and thus boost the content delivery to the requesters. Its superiority compared to network coding-agnostic caching schemes lies on the increased availability of the content, which can be extracted by the requesters after they receive and decode a sufficiently large amount of encoded data. Although the topics surrounding network coding and caching have been already studied in the previous literature, their potential on enhancing mobile content delivery has not been fully explored yet. Namely, most of the existing works restrict the encoded data combinations to involve only parts of the same file, since this guarantees a low number of choices and thus simplifies the analysis. In this work, we study the problem of caching linear combinations of different files in a small-cell network. Our goal is to mitigate the pressure on the macrocellular base station by serving as many as possible content requests by the cache-endowed small-cell base stations that are deployed in the cell. Because of the NP-hardness of this problem, we propose a heuristic algorithm that gradually increases the performance of the obtained solution. Numerical results for typical popularity distributions reveal the performance benefits of our approach.

Cache-endowed small cell networks constitute a timely and effective solution for mobile network operators (MNOs) who strive to serve the massive content demand of the mobile users. However, the deployment of small cell base stations (SBSs) requires significant economic investments, while site acquisition issues render it infeasible in several cases. Yet, one potentially explosive factor for network expansion remains unexploited, namely, an increasing number of residential users install in their premises privately-owned SBSs (femtocell or WiFi access points) in order to serve their own needs. In this work, we envision an MNO offering incentives to the SBS owners to cache and deliver content items requested by the nearby mobile users. We model the interaction between the MNO and the SBS owners as a Stackelberg game, and show that the incentive design problem requires to know the content caching policy, which in turn should be jointly derived with the request routing policy. We then introduce a framework for the joint derivation of incentive, caching and routing policies. Numerical results indicate that our mechanism provides a substantial potential for reducing the MNO's costs, depending on the willingness of the SBS owners to lease their resources and the spatio temporal characteristics of the mobile data demand.

The deployment of small cells is expected to gain huge momentum in the near future, as a solution for managing the skyrocketing mobile data demand growth. Local caching of popular files at the small cell base stations has been recently proposed, aiming at reducing the traffic incurred when transferring the requested content from the core network to the users. In this paper, we propose and analyze a novel caching approach that can achieve significantly lower traffic compared to the traditional caching schemes. Our cache design policy carefully takes into account the fact that an operator can serve the requests for the same file that happen at nearby times via a single multicast transmission. The latter incurs less traffic as the requested file is transmitted to the users only once, rather than with many unicast transmissions. Systematic experiments demonstrate the effectiveness of our approach, as compared to the existing caching schemes.

Utilization of device-to-device communication links provides an alternative way for mitigating the skyrocketing mobile data growth that challenges cellular operators nowadays. Namely, the owners of these devices can serve requests of their neighbors for the files that are stored at their caches. However, users are unwilling in general to serve requests of others, since data transmission incurs energy consumption. The issue is further perplexed, if one considers realistic parameters such as the limited capacity of the device's battery. In this work, we explicitly take into account the above aspects and formulate the content request routing problem aiming to minimize the load of the macrocellular base station. This problem is challenging to solve due to its discrete nature. We derive an optimal polynomial-time solution based on a reduction to a matching problem. Besides, we present a light-weight distributed algorithm for its solution. Simulation results reveal the performance benefits of our approach.

Small cells constitute a promising solution for managing the mobile data growth that has overwhelmed network operators. Local caching of popular content items at the small cell base stations (SBSs) has been proposed to decrease the costly transmissions from the macrocell base stations without requiring high capacity backhaul links for connecting the SBSs with the core network. However, the caching policy design is a challenging problem especially if one considers realistic parameters such as the bandwidth capacity constraints of the SBSs that can be reached in congested urban areas. We consider such a scenario and formulate the joint routing and caching problem aiming to maximize the fraction of content requests served locally by the deployed SBSs. This is an NP-hard problem and, hence, we cannot obtain an optimal solution. Thus, we present a novel reduction to a variant of the facility location problem, which allows us to exploit the rich literature of it, to establish algorithms with approximation guarantees for our problem. Although the reduction does not ensure tight enough bounds in general, extensive numerical results reveal a near-optimal performance that is even up to 38% better compared to conventional caching schemes using realistic system settings.

Small cells constitute a promising solution for managing the mobile data growth that has overwhelmed network operators. Local caching of popular content items at the small cell base stations has been proposed in order to decrease the capacity-and hence the cost- of the backhaul links that connect these base stations with the core network. However, deriving the optimal caching policy remains a challenging open problem especially if one considers realistic parameters such as the bandwidth limitation of the base stations. The latter constraint is particularly important for cases when users requests are massive. We consider such a scenario and formulate the joint caching and routing problem aiming to maximize the fraction of content requests served by the deployed small cell base stations. This is an NP-hard problem and hence we cannot obtain an exact optimal solution. Thus, we present a novel approximation framework based on a reduction to a well known variant of the facility location problem. This allows us to exploit the rich literature in facility location problems, in order to establish bounded approximation algorithms for our problem.

Hierarchical topologies have been applied in many existing systems that provide public IPTV or massive content delivery services. The efficient operation of these services requires massive bandwidth resources. Data caching has emerged as an effective way in reducing bandwidth consumption and accelerating content access. In hierarchical caching systems requests for content are routed upwards until they reach a cache that stores a copy of the requested file. When the requested file is found, it is sent on the reverse path to the client. In this work, we focus on the problem of caching redundant copies of content in intermediate caches on the reverse path in order to minimize the bandwidth consumption within a given time horizon. The above problem is known to be NP-hard. However, we show that replacing the cache capacity constraints by a cost term paid each time we store a file in a cache, results to the tractable problem of minimizing the overall bandwidth and caching expenses. We use its optimal solution to establish a novel algorithm for the efficient solution of the original problem. We furthermore study the case that segments of encoded versions of the files instead of only complete files are allowed to be stored at the caches. We show that this problem is of polynomial complexity. Numerical experiments for typical popularity distributions reveal the performance distance between the proposed algorithms and heuristic algorithms that are commonly applied nowadays.

As the processing and transport capacity of the information and communication technologies (ICT) infrastructure increased vastly the last few years, the bottleneck of the information exchange process moved to the end points of the process, i.e. the consumers and the producers of information. On one hand there is the limited time that a consumer has to access the information and on the other hand there is the minimum utility level that a provider needs to provide to the society of consumers to cover it's investment cost. In this paper we present a novel decision model for a set of competing providers that wish to enter a market. It may happen that due to the competition, some competitors will not be able to cover their investment cost and therefore will disappear. We analyze the optimum way of forming the market, in order to maximize the aggregate utility of it. We show that this problem is NP-complete and present a linear programming rounding heuristic algorithm to solve it. Besides, we study a game where every player (provider) is to choose whether to join the market or not. We compute the price of anarchy of the game and present a heuristic algorithm that belongs to the family of best response dynamic algorithms. Systematic experiments on a real world data set have demonstrated the effectiveness of our proposed approach.

We consider the problem of storing segments of encoded versions of content files in a set of base stations located in a communication cell. These base stations work in conjunction with the main base station of the cell. Users move randomly across the space based on a discrete-time Markov chain model. At each time slot each user accesses a single base station based on it's current position and it can download only a part of the content stored in it, depending on the time slot duration. We assume that file requests must be satisfied within a given time deadline in order to be successful. If the amount of the downloaded (encoded) data by the accessed base stations when the time deadline expires does not suffice to recover the requested file, the main base station of the cell serves the request. Our aim is to find the storage allocation that minimizes the probability of using the main base station for file delivery. This problem is intractable in general. However, we show that the optimal solution of the problem can be efficiently attained in case that the time deadline is small. To tackle the general case, we propose a distributed approximation algorithm based on large deviation inequalities. Systematic experiments on a real world data set demonstrate the effectiveness of our proposed algorithms.