Network slicing is a pivotal concept in the evolution of 5 G networks. It enables network operators to partition physical resources from edge to data center, allowing concurrent multiplexing of tenants while adhering to each tenant's Service Level Agreement. Efficient resource allocation is critical in this context, prompting recent research into deep neural networks (DNNs). However, challenges arise with edge resources, including the need to rapidly scale resources (within milliseconds) and the cost of transmitting large volumes of data to a cloud for centralized DNN-based processing. To address these issues, we previously investigated distributed deep neural network (DDNN) architectures based on CNN and LSTM with a single local exit, facilitating efficient edge-cloud collaboration. In this work, we aim to generalize the training methodology for such networks, identifying both shared and unique aspects across different models. Additionally, we propose an extended architecture that incorporates multiple local exits, which introduces new challenges. Unlike DDNNs with one local exit, multiple local exits observe different subsets of the input signals, while the remote exit processes a superset of these. This leads to partially coupled layers and exits, complicating both the model architecture and training process. Moreover, the offloading decision mechanism now involves more intricate trade-offs, such as determining whether to forward specific subsets of preprocessed features to the cloud for further processing. We explore the joint training of DDNN exits and an optimized offloading mechanism, demonstrating that our architecture resolves nearly 40 % of decisions at the edge without incurring additional penalty compared to centralized models.

Network slicing has been proposed as a paradigm for 5G+ networks. The operators slice physical resources from the edge all the way to the datacenter, and are responsible to micro-manage the allocation of these resources among tenants bound by predefined Service Level Agreements (SLAs). A key task, for which recent works have advocated the use of Deep Neural Networks (DNNs), is tracking the tenant demand and scaling its resources. Nevertheless, for the edge resources (e.g., RAN), a question arises on whether operators can: (a) scale them fast enough (often in the order of ms) and (b) afford to transmit huge amounts of data towards a remote cloud where such a DNN model might operate. We propose a Distributed DNN (DDNN) architecture for a class of such problems: a small subset of the DNN layers at the edge attempt to act as fast, standalone resource allocator; this is complemented by a mechanism to intelligently offload a percentage of (harder) decisions to additional DNN layers running at a remote cloud. To implement the offloading, we propose: (i) a Bayes-inspired method, using dropout during inference, to estimate the confidence in the local prediction; (ii) a learnable function which automatically classifies samples as “remote” (to be offloaded) or “local”. Using the public Milano dataset, we investigate how such a DDNN should be trained and operated to address (a) and (b). In some cases, our offloading methods are near-optimal, resolving up to 50% of decisions locally with little or no penalty on the allocation cost.

Efficient resource allocation among slices/users with different Service Level Agreements (SLAs) is a critical task in 5G+ networks, which has prompted recent research into Deep Neural Networks (DNNs). However, challenges arise when dealing with edge resources, including the ability to rapidly scale resources (in the order of milliseconds), and the cost of transmitting large data volumes to a cloud for centralized DNN-based processing. Addressing these issues, we introduce a novel architecture based on Distributed Deep Neural Networks (DDNN). This architecture features a compact set of DNN layers located at the network’s edge, designed to function as an autonomous resource allocation unit. Complementing this, there is an intelligent offloading mechanism that delegates a fraction of hard decisions to additional DNN layers situated in a remote cloud (when needed). To implement offloading, we propose a theoretically informed method that learns to mimic an oracle that knows which sample will benefit from additional processing in the cloud. We compare this to a previously proposed heuristic, based on a Bayesian-confidence mechanism. We investigate the interplay of (offline) joint training of the DDNN exits and the ML-based offloading mechanism, and demonstrate that our architecture resolves more than 50% of decisions at the edge with no additional penalty compared to centralized models as well as consistently outperforms previous methods.

Recommendations are employed by Content Providers (CPs) of streaming services in order to boost user engagement and their revenues. Recent works suggest that nudging recommendations towards cached items can reduce operational costs in the caching networks, e.g., Content Delivery Networks (CDNs) or edge cache providers in future wireless networks. However, cache-friendly recommendations could deviate from users' tastes, and potentially affect the CP's revenues. Motivated by real-world business models, this work identifies the misalignment of the financial goals of the CP and the caching network provider, and presents a network-economic framework for recommendations. We propose a cooperation mechanism leveraging the Nash bargaining solution that allows the two entities to jointly design the recommendation policy. We consider different problem instances that vary on the extent these entities are willing to share their cost and revenue models, and propose two cooperative policies, CCR and DCR, that allow them to make decisions in a centralized or distributed way. In both cases, our solution guarantees reaching a fair and Pareto optimal allocation of the cooperation gains. Moreover, we discuss the extension of our framework towards caching decisions. A wealth of numerical experiments in realistic scenarios show the policies lead to significant gains for both entities.

Caching algorithms try to predict content popularity, and place the content closer to the users. Additionally, nowadays requests are increasingly driven by recommendation systems (RS). These important trends, point to the following: \emph{make RSs favor locally cached content}, this way operators reduce network costs, and users get better streaming rates. Nevertheless, this process should preserve the quality of the recommendations (QoR). In this work, we propose a Markov Chain model for a stochastic, recommendation-driven \emph{sequence} of requests, and formulate the problem of selecting high quality recommendations that minimize the network cost \emph{in the long run}. While the original optimization problem is non-convex, it can be convexified through a series of transformations. Moreover, we extend our framework for users who show preference in some positions of the recommendations' list. To our best knowledge, this is the first work to provide an optimal polynomial-time algorithm for these problems. Finally, testing our algorithms on real datasets suggests significant potential, e.g.,$2\times$improvement compared to baseline recommendations, and 80\% compared to a greedy network-friendly-RS (which optimizes the cost for I.I.D. requests), while preserving at least 90\% of the original QoR. Finally, we show that taking position preference into account leads to additional performance gains.

This work presents a new way of exploiting non-uniform file popularity in coded caching networks. Focusing on a fully-connected fully-interfering wireless setting with multiple cache-enabled transmitters and receivers, we show how non-uniform file popularity can be used very efficiently to accelerate the impact of transmitter-side data redundancy on receiver-side coded caching. This approach is motivated by the recent discovery that, under any realistic file-size constraint, having content appear in multiple transmitters can in fact dramatically boost the speed-up factor attributed to coded caching. We formulate an optimization problem that exploits file popularity to optimize the placement of files at the transmitters. Consequently, we propose a search algorithm that solves the problem at hand while reducing the variable search space significantly. We also prove an analytical performance upper bound, which is in fact met by our algorithm in the regime of many receivers. Our work reflects the benefits of allocating higher cache redundancy to more popular files, but also reflects a law of diminishing returns where for example very popular files may in fact benefit from minimum redundancy. In the end, this work reveals that in the context of coded caching, employing multiple transmitters can be a catalyst in fully exploiting file popularity, as it avoids various asymmetry complications that appear when file popularity is used to alter the receiver-side cache placement.

To ensure a seamless mobility of users in the scenario with flying base stations (FlyBSs) and static ground base stations (GBSs), an efficient handover mechanism is required. In this paper, we introduce new framework simultaneously managing cell individual offset (CIO) for handover of both FlyBSs and mobile users. Our objective is to maximize capacity of the mobile users while considering also a cost of handover to reflect potential excessive signaling and energy consumption due to redundant handovers. This problem is of a very high complexity for conventional optimization methods and optimal solution would require knowledge of information commonly not available to the mobile network. Hence, we adjust the CIO of FlyBSs and GBSs via reinforcement learning. First, we adopt Q- learning to solve the problem. Due to practical limitations implied by a large Q-table, we also propose Q- learning with approximated Q-table. Still, for larger networks, even the approximated Q-table can require a large storage and computation time. Therefore, we apply also actor-critic-based deep reinforcement learning. Simulation results demonstrate that all three proposed algorithms converge promptly and increase the communication capacity by dozens of percent while the handover failure ratio and the handover ping-pong ratio are reduced multiple times compared to state-of-the-art.

Network slicing in beyond 5G systems facilitates the creation of customized virtual networks/services, referred to as “slices”, on top of the physical network infrastructure. Efficient and dynamic orchestration of slices is needed to ensure the stringent and diverse service level agreements (SLAs) required by different services. In this paper, we provide a model that attempts to capture the problem of dynamic slice embedding and reconfiguration supporting a multi-domain setup and diverse, end-to-end SLAs. We then show that such problems can be optimally solved, in theory, with (tabular) Reinforcement Learning algorithms (e.g., Q-learning) even under, a priori, unknown demand dynamics for each slice. Nevertheless, the state and action complexity of such algorithms is prohibitive, even for very small scenarios. To this end, we propose a novel scheme based on independent DQN agents: The DQN component implements approximate Q-learning, based on simple, generic DNNs for value function approximation, radically reducing state space complexity; the independent agents then tackle the equally important issue of exploding action complexity arising from the combinatorial nature of embedding multiple VNFs per slice, multiple slices, over multiple domains and computing nodes therein. Using realistic data, we show that the proposed algorithm reduces convergence time by orders of magnitude with minimum penalty of decision optimality.

Content recommendation systems, also known as recommenders, are pervasive and impact a significant portion of users demands over the Internet. Although recommenders have been primarily devised to account for users interests with respect to the content catalog, mobile users are typically served by a network that is unreliable and subject to losses and low QoS. Can content recommenders compensate for low QoS? To answer this question, we conducted experiments over the Internet, and report our findings on (i) the characterization of QoS and (ii) the compensation for low QoS. Our measurements suggest that content that is far from the trends tends to be far from the user. We quantify the extent at which unpopular content tends to be served with lower QoS and establish a methodology to determine the relationship between contents' popularity and its physical proximity to the users. Then, we verify that making requests a bit trendier can hit much closer content. In particular, our results suggest conditions under which a recommender can compensate for low QoS, at zero costs for operators.

In the context of on-demand video streaming services, both the caching and the recommendation decisions have an impact on the user satisfaction, and thus, financial implications for the Content Provider (CP). The idea of co-designing these decisions has been recently proposed in the literature as a way to minimize delivery costs and traffic at the backbone Internet. However, related work does not take into account that every content exists in multiple versions/streaming qualities, or at best treats each version as a separate content, when it comes to caching. In this paper, we explore how transcoding a content at the edge could avoid placing multiple related versions of this content in the same cache, thus better utilizing capacity (leading to an increase of the CP's profit). To this end, we formulate the problem of jointly deciding on caching, recommendations, and user-transcoder assignments with the goal of increasing the profit (revenue minus the incurred costs). We propose an iterative algorithm that is based on a decomposition of the formulated problem into two subproblems. We show that both subproblems, although NP-hard, are equivalent to problems in the literature for which algorithms with approximation guarantees exist. Our numerical evaluations in realistic scenarios show that the proposed policy leads to important financial gains of up to 29% when compared to the scenario where edge transcoding is not exploited.

Flying base stations (FlyBSs) are widely used to improve coverage and/or quality of service for users in mobile networks. To ensure a seamless mobility of the FlyBSs among the static base stations (SBSs), an efficient handover mechanism is required. We focus on the handover of FlyBSs among SBSs and we dynamically adjust the cell individual offset (CIO) of the SBSs based on their load to increase the sum capacity of the users served by the FlyBSs while considering also a handover cost. Due to complexity of the defined problem and limited knowledge of other parameters required for conventional optimization methods, we adopt Q-learning to solve the problem. For Q-learning, we define a reward function reflecting the tradeoff between the capacity of users and the cost of performed handovers. The proposed Q-learning based approach converges promptly and increases the sum capacity of the users served by the FlyBSs by up to 23% for eight deployed FlyBSs comparing to state-of-the-art algorithms. At the same time, the number of handovers performed by the FlyBSs is notably reduced (up to 25%) by the proposal.

Network slicing has been proposed as a paradigm for 5G+ networks. The operators slice physical resources from the edge, all the way to datacenter, and are responsible to micromanage the allocation of these resources among tenants bound by predefined Service Level Agreements (SLAs). A key task, for which recent works have advocated the use of Deep Neural Networks (DNNs), is tracking the tenant demand and scaling its resources. Nevertheless, for edge resources (e.g. RAN), a question arises whether operators can: (a) scale edge resources fast enough (often in the order of ms) and (b) afford to transmit huge amounts of data towards a cloud where such a DNN-based algorithm might operate. We propose a Distributed-DNN architecture for a class of such problems: a small subset of the DNN layers at the edge attempt to act as fast, standalone resource allocator; this is coupled with a Bayesian mechanism to intelligently offload a subset of (harder) decisions to additional DNN layers running at a remote cloud. Using the publicly available Milano dataset, we investigate how such a DDNN should be jointly trained, as well as operated, to efficiently address (a) and (b), resolving up to 60% of allocation decisions locally with little or no penalty on the allocation cost.

Joint caching and recommendation has been recently proposed as a new paradigm for increasing the efficiency of mobile edge caching. Early findings demonstrate significant gains for the network performance. However, previous works evaluated the proposed schemes exclusively on simulation environments. Hence, it still remains uncertain whether the claimed benefits would change in real settings. In this paper, we propose a methodology that enables to evaluate joint network and recommendation schemes in real content services by only using publicly available information. We apply our methodology to the YouTube service, and conduct extensive measurements to investigate the potential performance gains. Our results show that significant gains can be achieved in practice; e.g., 8 to 10 times increase in the cache hit ratio from cache-aware recommendations. Finally, we build an experimental testbed and conduct experiments with real users; we make available our code and datasets to facilitate further research. To our best knowledge, this is the first realistic evaluation (over a real service, with real measurements and user experiments) of the joint caching and recommendations paradigm. Our findings provide experimental evidence for the feasibility and benefits of this paradigm, validate assumptions of previous works, and provide insights that can drive future research.

Streaming platforms, like Netflix and YouTube, strive to offer high streaming quality (SQ), in terms of bitrate, delays, etc., to their users. Meanwhile, a significant share of content consumption of these platforms is heavily influenced by recommendations. In this setting, the user’s overall experience is a product of both the user’s interest in a recommended content,i.e., the recommendation quality (RQ), and the SQ of this content. However, network decisions (like caching) that affect the SQ are usually made without considering the recommender’s actions. Likewise, recommendations are chosen independently of the potential delivery quality. In this paper, we define a metric of streaming experience (MoSE) that captures the fundamental tradeoff between the SQ and RQ. We aim to jointly optimize caching and recommendations in a generic network of caches, with the objective of maximizing this metric. This is in line with the recent trend for content providers to simultaneously act as Content Delivery Network owners, implying that the same entity may handle both caching and recommendation decisions. We formulate this joint optimization problem and prove that it can be approximated up to a constant factor. To the best of our knowledge, this is the first polynomial algorithm to achieve a constant approximation ratio for the joint problem. Moreover, our numerical experiments show important performance gains of our algorithm over baseline schemes and existing algorithms in the literature.

In 5G and beyond network architectures, operators and content providers base their content distribution strategies on small cell networks. On top of such networks, edge caching and Coordinated Multi-Point (CoMP) Joint Transmissions are used to improve performance. Online solutions for average delay minimization problem have been studied in the related literature, although only under the strong assumption that files have equal sizes. In this paper we aim to fill this gap and propose an online caching policy, qLRU-HS, that takes into account heterogeneous sizes and asymptotically converges to the optimal cache allocation under the Independent Reference Model. Our experiments confirm such convergence in practice and reveal that qLRU-HS outperforms other state-of-the-art solutions.

Recommender systems have been established as a key component of video streaming services, shaping up to 80% of content requests. Hence, recommendations are employed by the Content Providers (CPs) of these services to increase the viewing time and their revenues. Furthermore, it has been recently suggested that recommendations could be a means to reduce the operational costs of the Content Delivery Networks (CDNs) when they are related to already cached items, i.e., when they are cache-friendly. Clearly, these conflicting objectives, i.e., increasing revenue for the CP and reducing costs for the CDN, can create tensions between the two entities, and hence, prevent the full utilization of recommendations. In this work, we propose a model for capturing these tradeoffs, and an economic mechanism, based on the Nash bargaining solution, for reconciling the potentially conflicting objectives of the CP and the CDN. Our scheme enables the CP and CDN to jointly design the recommendations in a way that balances the revenue gains and cost savings, ensuring a fair and Pareto optimal split of the accrued benefits for both entities. Our numerical experiments in realistic scenarios show that the proposed scheme leads to important financial gains of up to 30%.

Caching content over CDNs or at the network edge has been solidified as a means to improve network cost and offer better streaming experience to users. Furthermore, nudging the users towards low-cost content has recently gained momentum as a strategy to boost network performance. We focus on the problem of optimal policy design for Network Friendly Recommendations (NFR). We depart from recent modeling attempts, and propose a Markov Decision Process (MDP) formulation. MDPs offer a unified framework that can model a user with random session length. As it turns out, many state-of-the-art approaches can be cast as subcases of our MDP formulation. Moreover, the approach offers flexibility to model users who are reactive to the quality of the received recommendations. In terms of performance, for users consuming an arbitrary number of contents in sequence, we show theoretically and using extensive validation over real traces that the MDP approach outperforms myopic algorithms both in session cost as well as in offered recommendation quality. Finally, even compared to optimal state-of-art algorithms targeting specific subcases, our MDP framework is significantly more efficient, speeding the execution time by a factor of 10, and enjoying better scaling with the content catalog and recommendation batch sizes.

As mobile traffic is dominated by content services (e.g., video), which typically use recommendation systems, the paradigm of network-friendly recommendations (NFR) has been proposed recently to boost the network performance by promoting content that can be efficiently delivered (e.g., cached at the edge). NFR increase the network performance, however, at the cost of being unfair towards certain contents when compared to the standard recommendations. This unfairness is a side effect of NFR that has not been studied in literature. Nevertheless, retaining fairness among contents is a key operational requirement for content providers. This paper is the first to study the fairness in NFR, and design fair-NFR. Specifically, we use a set of metrics that capture different notions of fairness, and study the unfairness created by existing NFR schemes. Our analysis reveals that NFR can be significantly unfair. We identify an inherent trade-off between the network gains achieved by NFR and the resulting unfairness, and derive bounds for this trade-off. We show that existing NFR schemes frequently operate far from the bounds, i.e., there is room for improvement. To this end, we formulate the design of Fair-NFR (i.e., NFR with fairness guarantees compared to the baseline recommendations) as a linear optimization problem. Our results show that the Fair-NFR can achieve high network gains (similar to non-fair-NFR) with little unfairness.

Device-to-device (D2D) relaying is a concept, where some users relay data of cell-edge users (CUEs) experiencing a bad channel quality to a base station. While this research topic has received plenty of attention, a critical aspect of the D2D relaying remains a selfish nature of the users and their limited willingness to relay data for others. Thus, we propose a scheme to identify potential candidates for the relaying and provide a sound incentive to these relaying users (RUEs) to motivate them helping other users. First, we provide a detailed theoretical analysis showing when and if the relaying is beneficial for the CUE(s) and related RUE. Second, to choose among all possible incentive-compliant relaying options, we formulate the optimal CUE-to-RUE matching problem maximizing a network-wide performance. Since the optimal solution is hard to obtain for a high number of users, we propose a low-complexity greedy algorithm and prove its constant worst-case approximation guarantees to the optimum. Finally, we derive a closed-form expression for a fair allocation of the resources among the CUEs and the RUEs. The proposed framework more than doubles the users' capacity and/or reduces the energy consumption by up to 87% comparing to existing incentive-based relaying schemes.

We consider a dense cellular network, in which a limited-size cache is available at every base station (BS). Coordinating content allocation across the different caches can lead to significant performance gains, but is a difficult problem even when full information about the network and the request process is available. In this paper we present $q$ LRU- $\Delta $ , a general-purpose online caching policy that can be tailored to optimize different performance metrics also in presence of coordinated multipoint transmission techniques. The policy requires neither direct communication among BSs, nor a priori knowledge of content popularity and, under stationary request processes, has provable performance guarantees.

In 5G and beyond network architectures, operators and content providers base their content distribution strategies on Heterogeneous Networks, where macro and small cells are combined to offer better Quality of Service to wireless users. On top of such networks, edge caching and Coordinated Multi-Point (CoMP) joint transmissions are used to further improve performance. In this paper, we address the average delay minimization problem by first formulating it as a static optimization problem. Even though the problem is NP-hard we are able to solve it via an efficient algorithm that guarantees a 1/2-approximation ratio. We then proceed to propose two fully distributed and dynamic caching policies for the same problem. The first one asymptotically converges to the static optimal solution under the Independent Reference Model (IRM). The second one provides better results in practice under real (non-stationary) request processes. Our online policies outperform existing dynamic solutions that are PHY-unaware.

Caching popular content at the network edge can benefit both the operator and the client by alleviating the backhaul traffic and reducing access latency, respectively. Recommendation systems, on the other hand, try to offer interesting content to the user and impact her requests, but independently of the caching policy. Nevertheless, it has been recently proposed that designing caching and recommendation policies separately is suboptimal. Caching could benefit by knowing the recommender's actions in advance, and recommendation algorithms could try to favor cached content (among equally interesting options) to improve network performance and user experience. In this paper we tackle the problem of optimally making caching and recommendation decisions jointly, in the context of the recently introduced “soft cache hits” setup. We show that even the simplest (one user, one cache) problem is NP-hard, but that the most generic problem (multiple users, femtocaching network) is approximable to a constant. To the best of our knowledge, this is the first polynomial algorithm with approximation guarantees for the joint problem. Finally, we compare our algorithm to existing schemes using a range of real-world data-sets.

In 5G and beyond network architectures, operators and content providers base their content distribution strategies on Heterogeneous Networks, where macro and small(er) cells are combined to offer better Quality of Service (QoS) to wireless users. On top of such networks, edge caching and Coordinated Multi-Point (CoMP) transmissions are used to further improve performance. The problem of optimally utilizing the cache space in dense and heterogeneous cell networks has been extensively studied under the name of “FemtoCaching.” However, related literature usually assumes relatively simple physical layer (PHY) setups and known or stationary content popularity. In this paper, we address these issues by proposing a class of fully distributed and dynamic caching algorithms that take advantage of CoMP capabilities towards minimizing PHY-aware metrics, such as end-to-end (E2E) delay. Our policies outperform existing dynamic solutions that are PHY-unaware, under both synthetic and real (non-stationary) request processes, and converge to efficient centralized solutions, in static setups.

On streaming platforms such as Youtube and Netflix, recommendations influence a large share of content consumption. In this context, use rexperience depends on both the quality of the recommendations (QoR) and the quality of service (QoS) of the delivered content. However, network decisions (such as caching) affecting QoS are usually made without explicit knowledge of the recommender's actions. Similarly, recommendation decisions are made without considering the potential delivery quality of the recommended content. In this paper, we propose to jointly optimize caching and recommendations in a generic network of caches, towards maximizing the quality of experience (QoE). This coincides with the recent trend for large content providers to also act as Content Delivery Network (CDN) owners. We formulate this joint optimization problem and prove that it can be approximated up to a constant. To the best of our knowledge, this is the first polynomial algorithm to achieve a constant approximation ratio for the joint problem. Our numerical experiments show important performance gains of the proposed algorithm over baseline schemes and existing algorithms.

Densification through small cells and caching in base stations have been proposed to deal with the increasing demand for Internet content and the related overload on the cellular infrastructure. However, these solutions are expensive to install and maintain. Instead, using vehicles acting as mobile caches might represent an interesting alternative. In our work, we assume that users can query nearby vehicles for some time, and be redirected to the cellular infrastructure when the deadline expires. Beyond reducing costs, in such an architecture, through vehicle mobility, a user sees a much larger variety of locally accessible content within only few minutes. Unlike most of the related works on delay tolerant access, we consider the impact on the user experience by assigning different retrieval deadlines per content. In our paper, we provide the following contributions: (i) we model analytically such a scenario; (ii) we formulate an optimization problem to maximize the traffic offloaded while ensuring user experience guarantees; (iii) we propose two variable deadline policies; (iv) we perform realistic trace-based simulations, and we show that, even with low technology penetration rate, more than 60 percent of the total traffic can be offloaded which is around 20 percent larger compared to existing allocation policies.

The performance of the cell edge users (CUEs) can be improved if they transmit their data via suitable relay UEs (RUEs) exploiting device-to- device (D2D) communication. The critical aspect of the whole relaying concept is to offer convenient incentives for the RUEs to motivate them to act as relays. The contribution of this paper is twofold. First, we propose a new incentive mechanism for the RUEs that can exploit certain amount of resources allocated to the CUE. Depending on the preferences of users, the CUEs/RUEs can benefit from relaying in terms of capacity enhancement, reduction of energy consumption or both. In this respect, we provide a detailed analysis on how and when relaying is of benefit for both sides. Second, we propose a low-complexity greedy relay selection algorithm incorporating the incentive mechanism that increases capacity up to 32.1% and/or reduces energy consumption by up to 36.1% when compared to state-of-the-art schemes. Moreover, we show that the greedy approach gives close-to-optimal performance.

We study a class of online convex optimization problems with long-term budget constraints that arise naturally as reliability guarantees or total consumption constraints. In this general setting, prior work by Mannor et al. (2009) has shown that achieving no regret is impossible if the functions defining the agent’s budget are chosen by an adversary. To overcome this obstacle, we refine the agent’s regret metric by introducing the notion of a "K-benchmark", i.e., a comparator which meets the problem’s allotted budget over any window of length K. The impossibility analysis of Mannor et al. (2009) is recovered when K=T; however, for K=o(T), we show that it is possible to minimize regret while still meeting the problem’s long-term budget constraints. We achieve this via an online learning policy based on Cautious Online Lagrangiant Descent (COLD) for which we derive explicit bounds, in terms of both the incurred regret and the residual budget violations.

This paper addresses a fundamental challenge in cloud computing, that of learning an economical yet robust reservation, i.e. reserve just enough resources to avoid both violations and expensive over provisioning. Prediction tools are often inadequate due to observed high variability in CPU and memory workload. We propose a novel model-free approach that has its root in online learning. Specifically, we allow the workload profile to be engineered by an adversary who aims to harm our decisions, and we investigate a class of policies that aim to minimize regret (minimize losses with respect to a baseline static policy that knows the workload sample path). Then we propose a combination of the Lyapunov optimization theory [1] and a linear prediction of the future based on the recent past, used in learning and online optimization problems, see [2]. This enables us to come up with a no regret policy, i.e., a policy whose cost difference to the benchmark and violation constraint residual both grow sublinearly in time, and hence become amortized over the horizon. Our policy has then “no regret and eventually learns the minimum cost reservation subject to a time-average constraint for violations.

Caching has recently attracted a lot of attention in the wireless communications community, as a means to cope with the increasing number of users consuming web content from mobile devices. Caching offers an opportunity for a win-win scenario: nearby content can improve the video streaming experience for the user, and free up valuable network resources for the operator. At the same time, recent works have shown that recommendations of popular content apps are responsible for a significant percentage of users requests. As a result, some very recent works have considered how to nudge recommendations to facilitate the network (e.g., increase cache hit rates). In this paper, we follow up on this line of work, and consider the problem of designing cache friendly recommendations for long viewing sessions; specifically, we attempt to answer two open questions in this context: (i) given that recommendation position affects user click rates, what is the impact on the performance of such network-friendly recommender solutions? (ii) can the resulting optimization problems be solved efficiently, when considering both sequences of dependent accesses (e.g., YouTube) and position preference? To this end, we propose a stochastic model that incorporates position-aware recommendations into a Markovian traversal model of the content catalog, and derive the average cost of a user session using absorbing Markov chain theory. We then formulate the optimization problem, and after a careful sequence of equivalent transformations show that it has a linear program equivalent and thus can be solved efficiently. Finally, we use a range of real datasets we collected to investigate the impact of position preference in recommendations on the proposed optimal algorithm. Our results suggest more than 30% improvement with respect to state-of-the-art methods.

We propose a smart offloading policy that dynamically assigns data flows to the WiFi and cellular interfaces, so as to minimize a given cost function (related to energy consumption and cellular plan usage), while keeping the average per-flow delay bounded. The basic insight of the proposed Threshold Policy is to assign larger flows to the network that provides the best rate (often WiFi), and smaller flows to the other, since energy is generally related to the time needed to send/receive data. However, choosing the size cutoff optimally must also consider load-balancing and queueing aspects, WiFi availability, flow size statistics, and user/application preferences. We validate our model against simulations, and show that our policy outperforms other standard or smart policies, achieving considerably better energy-delay trade-offs, while only offloading a small percentage of (large)flows. Initial measurements performed on an Android-based offloading prototype further support our findings.

Caching content at the edge of mobile networks is considered as a promising way to deal with the data tsunami. In addition to caching at fixed base stations or user devices, it has been recently proposed that an architecture with public or private transportation acting as mobile relays and caches might be a promising middle ground. While such mobile caches have mostly been considered in the context of delay tolerant networks, in this paper we argue that they could be used for low cost video streaming without the need to impose any delay on the user. Users can prefetch video chunks into their playout buffer from encountered vehicle caches (at low cost) or stream from the cellular infrastructure (at higher cost) when their playout buffer empties while watching the content. Our main contributions are: (i) to model the playout buffer in the user device and analyze its idle periods which correspond to bytes downloaded from the infrastructure; (ii) to optimize the content allocation to mobile caches; and to minimize the expected number of non-offloaded bytes. We perform trace-based simulations to support our findings showing that up to 60 percent of the original traffic could be offloaded from the main infrastructure.

We study the user association problem in the context of dense networks, where standard adaptive algorithms become ineffective. This paper proposes a novel data-driven technique leveraging the theory of robust optimization. The main idea is to predict future traffic fluctuations, and use the predictions to design association maps before the actual arrival of traffic. Although, the actual playout of the map is random due to prediction error, the maps are robustly designed to handle uncertainty, preventing constraint violations, and maximizing the expectation of a convex utility function, which is used to accurately balance base station loads. We propose a generalized iterative algorithm, referred to as GRMA, which is shown to converge to the optimal robust map. The optimal maps have the intriguing property that they jointly optimize the predicted load and the variance of the prediction error. We validate our robust maps in Milano-area traces, with dense coverage and find that we can reduce violations from 25% (inflicted by a baseline adaptive algorithm) down to almost zero.

We study the problem of user association in Ultra Dense Networks (UDNs) for two network services; one requiring QoS guarantees to VIP flows, and one best effort service. The goal is to take advantage of statistical multiplexing in order to optimize the use of resources, while ensuring that the VIP flows enjoy active performance guarantees. We formulate this as an optimization problem, show that the problem is convex, and finally demonstrate that the optimum point can in fact be realized by distributed user association rules. In this way, our framework uses the fundamental problem of user association to show that both isolation and statistical multiplexing can be achieved in the context of UDNs, when different services or slices must share BS resources, as envisioned in 5G networks. We demonstrate no violations of the VIP flow constraint on real data traces for mobile network traffic, while a baseline best effort distributed policy applied to this setup inflicts up to 46.5% violations.

We study the user association problem in the context of dense networks, where standard adaptive algorithms become ineffective. The paper proposes a novel data-driven technique leveraging the theory of robust optimization. The main idea is to predict future traffic fluctuations, and use the predictions to design association maps before the actual arrival of traffic. Although the actual playout of the map is random due to prediction error, the maps are robustly designed to handle uncertainty, preventing constraint violations, and maximizing the expectation of a convex utility function, which allows to accurately balance base station loads. We propose a generic iterative algorithm, referred to as GRMA, which is shown to converge to the optimal robust map. The optimal maps have the intriguing property that they jointly optimize the predicted load and the variance of the prediction error. We validate our robust maps in Milano-area traces, with dense coverage and find that we can reduce violations from 25% (achieved by an adaptive algorithm) down to almost zero.

Ultra-dense small cell networks will require sophisticated user association algorithms that consider (i) channel characteristics, (ii) base station load, and (iii) uplink/downlink (UL/DL) traffic profiles. They will also be characterized by high spatio-temporal variability in UL/DL traffic demand, due to the fewer users per BS. In this direction, Dynamic TDD is a promising new technique to match BS resources to actual demand. While plenty of literature exists on the problem of user association, and some recent on dynamic TDD, most works consider these separately. In this paper, we argue that user association policies are strongly coupled with the allocation of resources between UL and DL. We propose an algorithm that decomposes the problem into separate subproblems that can each be solved efficiently and in a distributed manner, and prove convergence to the global optimum. Simulation results suggest that our approach can improve UL and DL performance at the same time, with an aggregate improvement of more than 2×, compared to user association under static TDD allocation.

Multi-connectivity is considered as a 5G key technique to improve both the user performance and the overall resource utilization. In this paper, we examine a resource allocation problem under multi-connectivity in evolved LTE and propose a utility proportional fair (UPF) resource allocation that preserves users quality-of-service (QoS) considering backhaul capacity limitations. The proposed policy is compared with proportional fair (PF) resource allocation through extensive simulations. Presented results show that multi-connectivity outperforms single-connectivity in terms of network aggregated rate and users QoS satisfaction in different network case studies, i.e., empty and loaded cell scenarios with fixed and variable backhaul capacity.

Caching has been successfully applied in wired networks, in the context of Content Distribution Networks (CDNs), and is quickly gaining ground for wireless systems. Storing popular content at the edge of the network (e.g, at small cells) is seen as a “win-win” for both the user (reduced access latency) and the operator (reduced load on the transport network and core servers). Nevertheless, the much smaller size of such edge caches, and the volatility of user preferences suggest that standard caching methods do not suffice in this context. What is more, simple popularity-based models commonly used (e.g, IRM) are becoming outdated, as users often consume multiple contents in sequence (e.g. YouTube, Spotify), and this consumption is driven by recommendation systems. The latter presents a great opportunity to bias the recommender to minimize content access cost (e.g, maximizing cache hit rates). To this end, in this paper we first propose a Markovian model for recommendation-driven user requests. We then formulate the problem of biasing the recommendation algorithm to minimize access cost, while maintaining acceptable recommendation quality. We show that the problem is non-convex, and propose an iterative ADMM-based algorithm that outperforms existing schemes, and shows significant potential for performance improvement on real content datasets.

Pushing popular content to small cells with local storage (“helper” nodes) has been proposed to cope with the ever-growing data demand. Nevertheless, the collective storage of a few nearby helper nodes may not suffice to achieve a high hit rate in practice. In this paper, we introduce the concept of “soft cache hits” (SCHs). An SCH occurs if a user's requested content is not in the local cache, but the user can be (partially) satisfied by a related content that is. In case of a cache miss, an application proxy (e.g., YouTube) running close to the helper node (e.g., at a multi-access edge computing server) can recommend the most related files that are locally cached. This system could be activated during periods of predicted congestion, or for selected users (e.g., low-cost plans), to improve cache hit ratio with limited (and tunable) user quality of experience performance impact. Beyond introducing a model for soft cache hits, our next contribution is to show that the optimal caching policy should be revisited when SCHs are allowed. In fact, we show that optimal caching with SCH is NP-hard even for a single cache. To this end, we formulate the optimal femto-caching problem with SCH in a sufficiently generic setup and propose efficient algorithms with provable performance. Finally, we use a large range of real datasets to corroborate our proposal.

Delay/Disruption Tolerant Networks target environments suffering from the instability or lack of end-to-end paths. Store-carry-and forward principle aims to sustain data sessions, and data replication to increase the probability of on-time delivery. However, these techniques require efficient scheduling and buffer management, to comply with limited resources availability (i.e., communication duration, storage). Multiple existing schemes aim to improve, or even optimize the resources usage. Nevertheless, their majority considers equally important application sessions. The few proposals considering different traffic classes, fail to provide real QoS guarantees. In this paper, we formulate the problem of maximizing the performance, subject to distinct QoS constraints (requirements) for each application class. We consider requirements related to delivery probability and delay. Then, we propose a distributed algorithm which: (i) guarantees satisfaction of the individual constraints, when this is feasible given the available resources, and (ii) allocates any remaining resources optimally, to maximize the desired performance metric. We first consider homogeneous mobility, and then extend our analysis to heterogeneous contact rates and sparse contact graphs, that better correspond to real life mobility. Simulation results, based on synthetic and real mobility scenarios, support our theoretical claims and show that our policy outperforms other existing schemes (i.e., ORWAR [1] and CoSSD [2] ).

Modern cellular networks are becoming denser, less regularly planned, and increasingly heterogeneous, making performance analysis challenging. We develop a flexible and accurate model of such heterogeneous networks (HetNets) consisting of K tiers of randomly located base stations (BSs), with different densities, transmit powers, and radio access technologies (RATs). Our main goal is to understand the impact of flow level dynamics on such a system, assuming non-saturated users that randomly generate download requests (“flows”). We do so by deriving analytically the per flow delay, the load, the utilization and the congestion probability of BSs in different tiers. We base our analysis on stochastic geometry, to understand the impact of topological randomness and intraand inter-tier interaction, and queueing theory, to model the competition between concurrent flows within the same BS, for each RAT. This allows us to model the interference more realistically as a function of network load. We apply our model to the case of a 2-tier network based on LTE and Wi-Fi and study different user inter-tier association criteria, such as off-load, max-SINR association, and min-delay association. Our results provide some interesting qualitative and quantitative insights about the impact of these association policies and different traffic intensities.

Pushing popular content to cheap ``helper'' nodes (e.g., small cells with local storage) during off-peak hours has recently been proposed to cope with the increase in mobile data traffic. If the requested content is available locally at a helper node, both user and operator performance could benefit. Nevertheless, the collective storage of a few nearby helper nodes does not usually suffice to achieve a high hit rate in practice. In this paper, we investigate the concept of ``soft cache hits'' where, if the original content is not available, some locally cached related contents can be recommended. Given that Internet content consumption is entertainment-oriented, we argue that there exist scenarios where a user might accept an alternative content (e.g., better download rate for alternative content, low rate plans), thus avoiding to access expensive/congested links. We formulate the problem of optimal edge caching with soft cache hits in a sufficiently generic setup, propose an efficient algorithm, and analyze the expected gains. We then show using synthetic and real datasets of related video contents that promising caching gains could be achieved in practice.

Thorough investigation of the Cloud-RAN (C-RAN) architecture has recently shown that C-RAN can bring advanced cooperated and coordinated processing capabilities as well as the multiplexing gains toward future radio access networks. The baseband processing of each base station instance can now be flexibly split into smaller functional components, that can be placed either at remote radio units (RRUs) or baseband units (BBUs), depending on the available fronthaul (FH) performance. Additionally, with the wide adoption of Ethernet in data centers and core networks, the Radio over Ethernet (RoE) approach is now considered as an off-the-shelf candidate for the FH link. To this end, we propose a unified RRU/BBU architectural framework for C-RAN that can support both a flexible functional split and a FH transport protocol over Ethernet. Furthermore, we experimentally evaluate the main key performance indicators (KPIs) of an operational C-RAN network built based on OpenAirInterface (OAI), a software implementation of LTE/LTE-A systems, under two functional splits and different deployment scenarios.

As cellular network operators are struggling to keep up with the rapidly increasing traffic demand, two key directions are deemed necessary for beyond 4G networks: (i) extensive cell densification to improve spatial reuse, and (ii) storage of content as close to the user as possible to cope with the backhaul constraints and increased interference. However, caching has mostly been studied with an exclusive focus either on the backhaul network (e.g. the “femto-caching” line of work) or on the radio access (e.g. through coded caching or cacheaided CoMP). As a result, an understanding of the impact of edge caching on network-wide and end-to-end performance is lacking. In this paper we investigate the problem of optimal caching in a context where nearby small cells (“femto-helpers”) can coordinate not just in terms of what to cache but also to perform Joint Transmission (a type of CoMP). We show that interesting tradeoffs arise between caching policies that improve radio access and ones that improve backhaul, and propose an algorithm that provably achieves an 1/2-approximation ratio to the optimal one (which is NP-hard), and performs well in simulated scenarios.

Densification through small cells and caching in base stations have been proposed to deal with the increasing demand for Internet content and the related overload on the cellular infrastructure. However, these solutions are expensive to install and maintain. Instead, using vehicles acting as mobile caches might represent an interesting alternative. In our work, we assume that users can query nearby vehicles for some time, and be redirected to the cellular infrastructure when the deadline expires. Beyond reducing costs, in such an architecture, through vehicle mobility, a user sees a much larger variety of locally accessible content within only few minutes. Unlike most of the related works on delay tolerant access, we consider the impact on the user experience by assigning different retrieval deadlines per content. In our paper, we provide the following contributions: (i) we model analytically such a scenario; (ii) we formulate an optimization problem to maximize the traffic offloaded while ensuring user experience guarantees; (iii) we propose a variable deadline policy; (iv) we perform realistic trace-based simulations, and we show that, even with low technology penetration rate, more than 60% of the total traffic can be offloaded which is around 20% larger compared to existing allocation policies.

In the current 4G era, the dual connectivity technique utilizes radio resources scheduled by two distinct base stations for a single user equipment to enhance the data throughput. Multi- connectivity, as a natural evolution of dual connectivity, is one of the key 5G techniques to improve both the user performance and overall resource utilization, allowing dynamic user traffic steering across multiple connections of one or more radio access technologies (RATs). However, one of the main challenge in multi-connectivity is to efficiently allocate resources across multiple connections under heterogeneous quality of service (QoS) requirements. In this paper, we examine a resource allocation problem under multi- connectivity in an evolved LTE network and propose a utility proportional fairness (UPF) resource allocation that supports QoS in terms of requested rates. We evaluate the proposed policy with the proportional fairness (PF) resource allocation through extensive simulations and characterize performance gain from both the user and network perspectives under different conditions.

An unprecedented increase in the mobile data traffic volume has been recently reported due to the extensive use of smartphones, tablets, and laptops. This is a major concern for mobile network operators, who are forced to often operate very close to their capacity limits. Recently, different solutions have been proposed to overcome this problem. The deployment of additional infrastructure, the use of more advanced technologies (LTE), or offloading some traffic through Femtocells and WiFi are some of the solutions. Out of these, WiFi presents some key advantages such as its already widespread deployment and low cost. While benefits to operators have already been documented, it is less clear how much and under what conditions the user gains as well. Additionally, the increasingly heterogeneous deployment of cellular networks (partial 4G coverage, small cells, etc.) further complicates the picture regarding both operatorand user-related performance of data off loading. To this end, in this paper we propose a queueing analytic model that can be used to understand the performance improvements achievable by Wi-Fi-based data off loading, as a function of Wi-Fi availability and performance, user mobility and traffic load, and the coverage ratio and respective rates of different cellular technologies available. We validate our theory against simulations for realistic scenarios and parameters, and provide some initial insights as to the offloading gains expected in practice.

Epidemic algorithms have found their way into many areas of computer science, such as databases and distributed systems, and recently for communication in Opportunistic or Delay Tolerant Networks (DTNs). To ensure analytical tractability, existing analyses of epidemic spreading predominantly consider homogeneous contact rates between nodes. However, this assumption is generally not true in real scenarios. In this paper, we consider classes of contact/mobility models with heterogeneous contact rates. Through an asymptotic analysis, we prove that a first-order, mean value approximation for the basic epidemic spreading step becomes exact in the limiting case (large network size). We further derive simple closed form approximations, based on higher order statistics of the mobility heterogeneity, for the case of finite-size networks. To demonstrate the utility of our results, we use them to predict the delay of epidemic-based routing schemes and analyze scenarios with node selfishness. We validate the analytic results through extensive simulations on synthetic scenarios, as well as on real traces to demonstrate that our expressions can be useful also in scenarios with significantly more complex structure. We believe these results are an important step forward towards analyzing the effects of heterogeneity (of mobility and/or other characteristics) on the performance of epidemic-based algorithms.

Operators have recently resorted to Wi-Fi offloading to deal with increasing data demand and induced congestion. Researchers have further suggested the use of delayed offloading: if no Wi-Fi connection is available, (some) traffic can be delayed up to a given deadline or until WiFi becomes available. Nevertheless, there is no clear consensus as to the benefits of delayed offloading, with a couple of recent experimental studies largely diverging in their conclusions, nor is it clear how these benefits depend on network characteristics (e.g., Wi-Fi availability), user traffic load, and so on. In this paper, we propose a queueing analytic model for delayed offloading, and derive the mean delay, offloading efficiency, and other metrics of interest, as a function of the user's patience, and key network parameters for two different service disciplines (First Come First Served and Processor Sharing). We validate the accuracy of our results using a range of realistic scenarios and real data traces. Finally, we use these expressions to show how the user could optimally choose deadlines by solving the variations of a constrained optimization problem, in order to maximize her own benefits.

Operators, struggling to continuously add capacity and upgrade their architecture to keep up with data traffic increase, are turning their attention to denser deployments that improve spectral efficiency. Denser deployments make the problem of user association challenging, and much work has been devoted to finding algorithms that strike a tradeoff between user quality of service, and network-wide performance (load-balancing). Nevertheless, the majority of these algorithms typically consider simple setups with a single type of traffic, usually elastic non-guaranteed bit rate (GBR). They also focus on the radio access part, ignoring the backhaul topology and potential capacity limitations. Backhaul constraints are emerging as a key performance bottleneck in future networks, partly due to the continuous improvement of the radio interface, and partly due to the need for inexpensive backhaul links to reduce capital and operational expenditures. To this end, we propose an analytical framework for user association that jointly considers radio access and backhaul network performance. Specifically, we derive an algorithm that takes into account spectral efficiency, base station load, backhaul link capacities and topology, and two traffic classes (GBR and non-GBR) in both the uplink and downlink directions. We prove analytically an optimal user association rule that ends up maximizing either an arithmetic or a weighted harmonic mean of the achieved performance along different dimensions (e.g., uplink and downlink performances or GBR and non-GBR performances). We then use extensive simulations to study the impact of: 1) traffic differentiation; and 2) backhaul capacity limitations and topology on key performance metrics.

In this paper, we develop a flexible and accurate analytical model of large networks with random base station (BS) placement, in order to understand the impact of key network parameters like BS density and load on the network performance. The main goal is to understand the flow level dynamics of such a system, assuming non-saturated users and studying the congestion statistics for BSs and the per flow delay. To achieve this, we base our analysis on two main tools: (a)stochastic geometry, to understand the impact of topological randomness and coverage maps and (b) queueing theory, to model the competition between concurrent flows within the same BS. Our model is then applied the populars Radio Access Technologies (RATs), such as LTE and WIFi. Our results provide some interesting qualitative and quantitative insights about the performance of those networks.

Being considered as a key enabler for beyond 4G networks, Cloud-RAN (CRAN) offers advanced cooperation and coordinated processing capabilities and brings multiplexing gains. The high capacity and low latency fronthaul (FH) links requirement in the CRAN architecture can be reduced by a flexible functional split of baseband processing between remote radio units (RRUs) and Baseband units (BBUs). Under the wide adoption of Ethernet in data centers and the core network, we consider the Radio over Ethernet (RoE) as an off-the-shelf alternative for FH link in this work. Moreover, the packetization process that packs each sample into Ethernet packets transported over the FH link will impact the CRAN performance. To this end, we investigate the impact of packetization on the proposed CRAN network and provide a packetization algorithm over the FH links. Furthermore, we also survey and analyze various packet scheduling policies applied at the aggregated RRU gateway in order to increase the multiplexing gain. Finally, the simulation results provide more in-depth insights on the potential multiplexing gains in terms of the maximum number of RRUs that can be supported over the Ethernet-based FH network.

Cloud-RAN (CRAN) is considered as one key enabler for beyond 4G networks, offering multiplexing gains, and advanced cooperation and coordinated signal processing. However, a key obstacle in the adoption of the CRAN architecture is that it requires very high capacity and low latency fronthaul (FH) links to carry raw I/Q samples between remote radio heads (RRH) and the baseband units (BBUs). These capacity requirements could be reduced by a more flexible split of baseband processing between BBUs and RRHs. Nevertheless, while moving some of the processing back into the RRH is expected to reduce FH rates, the amount of reduction mainly depends on the split, cell load, scenario and it might also introduce some delays. To this end, this paper studies the impact of different functional splits on the FH capacity for representative scenarios. Furthermore, we propose the use of a packet-based fronthaul network and study the joint impact of different packetization methods and RRH-BBU functional splits on the FH rate and latency. Based on this study, we provide some insights on the feasibility and optimality of different combinations, and the potential multiplexing benefits in terms of numbers of RRHs one could support over a single Ethernet-based FH network.

Operators, struggling to continuously add capacity and upgrade their architecture to keep up with data traffic increase, are turning their attention to denser deployments that improve spectral efficiency. Denser deployments make the problem of user association challenging, and much work has been devoted to finding algorithms that strike a tradeoff between user quality of service (QoS), and network-wide performance (load-balancing). Nevertheless, the majority of these algorithms typically consider only the radio access part, and ignore the backhaul topology and potential capacity limitations. Backhaul constraints are emerging as a key performance bottleneck in future heterogeneous networks, partly due to the continuous improvement of the radio interface, and partly due to the need for inexpensive backhaul links to reduce CAPEX/OPEX. To this end, we propose an analytical framework for user association that jointly considers radio access and backhaul performance. We derive an algorithm that takes into account spectral efficiency, base station load, backhaul link capacities and topology, and uplink and downlink traffic demand, and prove it converges to an optimal solution. We then use extensive simulations to study the impact of (i) backhaul capacity limitations and (ii) backhaul topology on key performance metrics.

In this work we propose a novel handover (HO) algorithm, that considers system performance from both user and network perspective, in the context of heterogeneous networks (HetNets), i.e., networks composed of BSs with asymmetrical transmission power. In such an environment, conventional HO algorithms that consider only the user perspective, e.g., received signal strength (RSS)-based, might offer suboptimal performance, since they mainly push users to cells with high transmission powers. Thus, new algorithms that take into account also the network perspective, e.g., cell load, are needed. In this work, a load-aware algorithm is proposed considering the service delay that a user experiences from the network. In addition, an implementable framework based on Software Defined Networking (SDN) architecture is sketched to support the algorithm. The proposed algorithm is compared with the traditional one we meet in long-term evolution (LTE) systems and a distance-based one. Extracted cell assignment probability and user service delay performance results show that the load-aware approach outperforms both of them.

The increasing demand for mobile data is overloading the cellular infrastructure. Small cells and edge caching is being explored as an alternative, but installation and maintenance costs for sufficient coverage are significant. In this work, we perform a preliminary study of an alternative architecture based on two main ideas: (i) using vehicles as mobile caches that can be accessed by user devices; compared to small cells, vehicles are more widespread and require lower costs; (ii) combining the mobility of vehicles with delayed content access to increase the number of cache hits (and reduce the load on the infrastructure). Contrary to standard DTN-type approaches, in our system max delays are guaranteed to be kept to a few minutes (beyond this deadline, the content is fetched from the infrastructure). We first propose an analytical framework to compute the optimal number of content replicas that one should cache, in order to minimize the infrastructure load. We then investigate how to optimally refresh these caches to introduce new contents, as well as to react to the temporal variability in content popularity. Simulations suggest that our vehicular cloud considerably reduces the infrastructure load in urban settings, assuming modest penetration rates and tolerable content access delays.

Mobile users are envisioned to exploit direct communication opportunities between their portable devices, in order to enrich the set of services they can access through cellular or WiFi networks. Sharing contents of common interest or providing access to resources or services between peers can enhance a mobile node's capabilities, offload the cellular network, and disseminate information to nodes without Internet access. Interest patterns, i.e., how many nodes are interested in each content or service (popularity), as well as how many users can provide a content or service (availability) impact the performance and feasibility of envisioned applications. In this paper, we establish an analytical framework to study the effects of these factors on the delay and success probability of a content/service access request through opportunistic communication. We also apply our framework to the mobile data offloading problem and provide insights for the optimization of its performance. We validate our model and results through realistic simulations, using datasets of real opportunistic networks.

Delay and Disruption Tolerant Networks (DTNs) have been proposed for challenging environments where the instability or lack of end-to-end paths is the rule rather than the exception. In this context, the principle of store-carry-and forward is used to sustain data sessions under intermittent connectivity, and data replication to increase the probability of on-time delivery. However, these techniques create the need for efficient scheduling and buffer management techniques, as the data load is generally larger than the amount of the available resources (i.e. bandwidth per communication opportunity, and buffer storage). A number of recent schemes have been proposed to make forwarding decisions that improve or even optimize the usage of these resources, in one way or another. Nevertheless, the majority of these schemes consider application sessions (and thus data messages) of equal importance. Furthermore, the few proposals that consider different traffic classes, do so in a somewhat "ad-hoc" manner, failing to provide real QoS guarantees. To this end, in this paper we formulate the problem of maximizing the network performance, in a limited resource network, subject to constraints corresponding to distinct QoS requirements (e.g., delivery probability) for each application class. Based on this formulation, we propose a distributed algorithm which: (i) guarantees that the individual QoS constraints are satisfied, when this is feasible given the amount of available resources, and (ii) allocates any remaining resources optimally, so as to maximize the desired performance metric. Simulation results, based on synthetic and realistic mobility scenarios, support our theoretical claims and further show that our policy outperforms other existing QoS prioritization schemes.

The widespread adoption of tablets and smartphones, and an abundance of data-hungry mobile applications, are overwhelming wireless networks with increased demand and introduce considerable traffic diversity. Operators struggling to continuously add capacity and upgrade their architecture have resorted instead to building denser deployments to improve spectral efficiency. By increasing the number of cells a user can associate with, (i) user quality of service (QoS) can be improved, and (ii) traffic can be offloaded from congested base stations, to achieve better load balancing. However, these two goals are not always aligned. To this end, we develop an analytical framework for optimal user association in future HetNets that investigates the potential tradeoffs between user- and network-related performance, in a more realistic setup encompassing additional key features: (i) different types of user flows, and (ii) uplink and downlink performance. We believe this better reflects the diversity of the services offered to users and their impact on system performance. We evaluate our proposed framework through extensive simulations, and provide some qualitative and quantitative insights on the related tradeoffs.

We consider a dynamic offloading problem arising in the context of mobile cloud computing (MCC). In MCC, three types of tasks can be identified: (i) those which can be processed only locally in a mobile device, (ii) those which are processed in the cloud, and (iii) those which can be processed either in the mobile or in the cloud. For type (iii) tasks, it is of interest to consider when they should be processed locally and when in the cloud. Furthermore, for both type (ii) and (iii) tasks, there is typically two ways to access the cloud: via a (costly) cellular connection or via intermittently available WLAN hotspots. The optimal strategy involves multi-dimensional considerations such as the availability of WLAN hotspots, energy consumption, communication costs and the expected delays. We approach this challenging problem in the framework of Markov decision processes and derive a near-optimal offloading policy.

Opportunistic networking has been proposed to support a number of novel applications, like content sharing or mobile data offloading, that follow a content-centric communication model, i.e., many users are interested in the same content. Users' traffic demand patterns can crucially affect the performance of such applications, but our knowledge about the characteristics of content demand is limited. Nevertheless, opportunistic networking is known to exhibit strong locality and social characteristics. For this reason, in this paper we argue that some initial insights about opportunistic traffic patterns could be inferred from geo-social network data. In particular, we study the check-in patterns of users in datasets of two real Location-Based Social Networks, towards understanding potential traffic characteristics and implications for opportunistic networking.

In opportunistic networks, direct communication between mobile devices is used to extend the set of services accessible through cellular or WiFi networks. Mobility patterns and their impact in such networks have been extensively studied. In contrast, this has not been the case with communication traffic patterns, where homogeneous traffic between all nodes is usually assumed. This assumption is generally not true, as node mobility and social characteristics can significantly affect the end-to-end traffic demand between them. To this end, in this paper, we explore the joint effect of traffic patterns and node mobility on the performance of popular forwarding mechanisms, both analytically and through simulations. Among the different insights stemming from our analysis, we identify conditions under which heterogeneity renders the added value of using extra relays more/less useful. Furthermore, we confirm the intuition that an increasing amount of heterogeneity closes the performance gap between different forwarding policies, making end-to-end routing more challenging in some cases, or less necessary in others. To our best knowledge, this is the first effort to model, analyze, and quantify effects of traffic heterogeneity. We believe this is an important step towards better protocol design and evaluation of the feasibility of applications in opportunistic networks.

Opportunistic or delay-tolerant networks (DTNs) may be used to enable communication in case of failure or lack of infrastructure (disaster, censorship, remote areas) and to complement existing wireless technologies (cellular, WiFi). Wireless peers communicate when in contact, forming an impromptu network, whose connectivity graph is highly dynamic and only partly connected. In this harsh environment, communication algorithms are mostly local search heuristics, choosing a solution among the locally available ones. Furthermore, they are routinely evaluated through simulations only, as they are hard to model analytically. Even when more insight is sought from models, these usually assume homogeneous node meeting rates, thereby ignoring the attested heterogeneity and nontrivial structure of human mobility. We propose DTN-Meteo, a new unified analytical model that maps an important class of DTN optimization problems over heterogeneous mobility/contact models into a Markov chain traversal over the relevant solution space. (Heterogeneous) meeting probabilities between different pairs of nodes dictate the chain's transition probabilities and determine neighboring solutions. Local optimization algorithms can accept/reject candidate transitions (deterministically or randomly), thus “modulating” the above transition probabilities. We apply our model to two example problems: routing and content placement. We predict the performance of state-of-the-art algorithms (SimBet, BubbleRap) in various real and synthetic mobility scenarios and show that surprising precision can be achieved against simulations, despite the complexity of the problems and diversity of settings. To our best knowledge, this is the first analytical work that can accurately predict performance for utility-based algorithms and heterogeneous node contact rates.

Small cell networks (SCNs) are widely considered as a promising solution for future cellular deployments. Lately, the benefits of small cells to improve spectrum utilization and the user quality of experience (QoE) have been well documented. In addition, the power consumption of current deployments, for instance due to idle power and cooling equipment, is a major concern for operators. Small cells offer the opportunity for more dynamic power management of base stations, due to coverage overlaps and larger spatio-temporal load fluctuations. Yet, such power management decisions (e.g. turning off a base station) should not lead to excessive performance degradation for users associated with it or additional power consumption. This tradeoff becomes significantly more challenging to evaluate in future networks, due to the diversity of services offered to users beyond the traditional voice calls, as well as the complexity of traffic scheduling algorithms. The goal of this paper is to make a first step towards an analytical investigation of this tradeoff. To this end, we propose a number of QoE constraints that a power management decision should consider, and analytically relate them to key parameters such as user traffic mix, cell load, user density, etc. We then use this framework to perform a preliminary study of the potential energy savings an operator could achieve, while guaranteeing the satisfaction of these constraints. Our results provide some qualitative and quantitative insights on the interesting tradeoff between switch-off duration and number of small cells one can safely switch off.

Operators have recently resorted to WiFi offloading to deal with increasing data demand and induced congestion. Researchers have further suggested the use of “delayed offloading”: if no WiFi connection is available, (some) traffic can be delayed up to a given deadline, or until WiFi becomes available. Nevertheless, there is no clear consensus as to the benefits of delayed offloading, with a couple of recent experimental studies largely diverging in their conclusions. Nor is it clear how these benefits depend on network characteristics (e.g. WiFi availability), user traffic load, etc. In this paper, we propose a queueing analytic model for delayed offloading, and derive the mean delay, offloading efficiency, and other metrics of interest, as a function of the user's “patience”, and key network parameters. We validate the accuracy of our results using a range of realistic scenarios, and use these expressions to show how to optimally choose deadlines.

Mobile users are envisioned to exploit direct communication opportunities between their portable devices, in order to enrich the set of services they can access through cellular or WiFi networks. Sharing contents of common interest or providing access to resources or services between peers can enhance a mobile node's capabilities, offload the cellular network, and disseminate information to nodes without internet access. Interest patterns, i.e. how many nodes are interested in each content or service (popularity), as well as how many users can provide a content or service (availability) impact the performance and feasibility of envisioned applications. In this paper, we establish an analytical framework to study the effects of these factors on the delay and success probability of a content/service access request through opportunistic communication. We also apply our framework to the data offloading problem and provide insights for its optimization.

An unprecedented increase in the mobile data traffic volume has been recently reported due to the extensive use of smartphones, tablets and laptops. Moreover, predictions say that this increase is going to be yet more pronounced in the next 3-4 years. This is a major concern for mobile network operators, who are forced to often operate very close to (or even beyond) their capacity limits. Recently, different solutions have been proposed to overcome this problem. The deployment of additional infrastructure, the use of more advanced technologies (LTE), or offloading some traffic through Femtocells and WiFi are some of the solutions. Out of these, WiFi presents some key advantages such as its already widespread deployment and low cost. While the benefits to operators have already been documented, with considerable amounts of traffic already switched over to WiFi, it is less clear how much and under what conditions the user gains as well. To this end, in this paper we propose a queueing analytic model that can be used to understand the performance improvements achievable by WiFi-based data offloading, as a function of WiFi availability and performance, and user mobility and traffic load. We validate our theory against simulations for realistic data and scenarios, and provide some initial insights as to the offloading gains expected in practice.

Cognitive Networks have been proposed to opportunistically discover and exploit (temporarily) unused licensed spectrum bands. With the exception of TV white spaces, secondary users (SUs) can access the medium only intermittently, due to deferring to primary user (PU) transmissions and scanning for new channels. This raises the following questions: (i) what sort of delays can an SU expect on a channel given the PU utilization of this channel? (ii) how do specific characteristics of the PU activity patterns (e.g. burstiness) further affect performance? These questions are of key importance for the design of efficient algorithms for scheduling, spectrum handoff, etc. In this paper, we propose a queueing analytical model to answer them. We model the PU activity pattern as an ON-OFF alternating renewal process with generic ON and OFF durations, and derive a closed form expression for packet delays by solving a variant of the M/G/1 queue. Contrary to the common belief that low utilization channels are good channels, we show that the expected SU delay on a channel, and thus the best channel to use, is a subtle interplay between the ON and OFF duration distributions of the primary users, and the SU traffic load. We validate our analysis against simulations for different PU activity profiles.

In technological or social networks, diffusion processes (e.g. information dissemination, rumour/virus spreading) strongly depend on the structure of the network. In this paper, we focus on epidemic processes over one such class of networks, Opportunistic Networks, where mobile nodes within range can communicate with each other directly. As the node degree distribution is a salient property for process dynamics on complex networks, we use the well known Configuration Model, that captures generic degree distributions, for modeling and analysis. We also assume that information spreading between two neighboring nodes can only occur during random contact times. Using this model, we proceed to derive closed-form approximative formulas for the information spreading delay that only require the first and second moments of the node degree distribution. Despite the simplicity of our model, simulations based on both synthetic and real traces suggest a considerable accuracy for a large range of heterogeneous contact networks arising in this context, validating its usefulness for performance prediction.

Emerging challenged networks require new protocols and strategies to cope with a high degree of mobility, high delays and unknown, possibly non-existing routes within the network. Researchers have proposed different store-carry-and-forward protocols for data delivery in challenged networks. These have been complemented with appropriate drop and scheduling policies that deal with the limitations of the nodes' buffers and the limited duration of opportunistic encounters in these networks. Nevertheless, the vast majority of these protocols and strategies are designed for end-to-end transmissions. Yet, a paradigm shift from the traditional way of addressing the endpoints in the network has been occurring towards content-centric networking. To this end, we present CEDO, a content-centric dissemination algorithm for challenged networks. CEDO aims at maximizing the total delivery-rate of distributed content in a setting where a range of contents of different popularity may be requested and stored, but nodes have limited resources. It achieves this by maintaining a delivery-rate utility per content that is proportional to the content miss rate and that is used by the nodes to make appropriate drop and scheduling decisions. This delivery-rate utility can be estimated locally by each node using unbiased estimators fed by sampled information on the mobile network obtained by gossiping. Both simulations and theory suggest that CEDO achieves its set goal, and outperforms a baseline LRU-based policy by 72%, even in relatively small scenarios. The framework followed by CEDO is general enough to be applied to other global performance objectives as well.

Cognitive Networks have been proposed to opportunistically discover and exploit (temporarily) unused licensed spectrum bands. For a number of applications, high throughput is the key figure of merit, while the application is still elastic enough to be supported at different rates. To this end, the cognitive node will try to discover and pool together a number of (at the time available) primary channels to provide a given target throughput. When a single radio is used for both transmission and channel scanning, an interesting tradeoff arises: when one or more channels of the currently available ones are lost (e.g. primary user returns), should the node start scanning immediately or continue transmitting over the remaining channels. Using renewal-reward theory, we show that if the goal is to maximize the average (long-term) throughput, the answer to this question depends on the statistics of the channel availability periods. Specifically, for relatively homogeneous channels, we show that it is optimal to start scanning immediately, while for heterogeneous channels, it is often better to defer scanning, even if multiple channels are lost. Simulations for a range of different channel characteristics validate our analytical findings and suggest that triggering the scanning function at the right times, can improve performance considerably.

We propose a transport protocol capable of dynamically adapting to network and receiver properties in multi-destination, multi-channel wireless networks. The key feature of our solution resides in its ability to convey common traffic to a group of users, while at the same time distributing information to each user as quickly as possible. This is achieved by clustering receivers in groups, each group being served at a suitable throughput. We emphasize in this study on the two groups of receivers case. We show analytically and through OMNet++ simulations that groups formation is decided by the wireless link performance and the proportion of receivers constituting each group. Our solution captures dynamically these effects. Indeed, our transport is capable to cope transparently with wireless links changes (i.e specturm handoff) by adapting dynamically its transmission rate and groups composition. It is therefore adapted for point-to-multipoint cognitive radio networks.

Opportunistic or Delay Tolerant Networks (DTNs) may be used to enable communication in case of failure or lack of infrastructure (disaster, censorship, remote areas) and to complement existing wireless technologies (cellular, WiFi). Wireless peers communicate when in contact, forming an impromptu network, whose connectivity graph is highly dynamic and only partly connected. In this harsh environment, communication algorithms are mostly greedy, choosing the best solution among the locally available ones. Furthermore, they are routinely evaluated through simulations only, as they are hard to model analytically. Even when more insight is sought from models, they usually assume homogeneous node meeting rates, thereby ignoring the attested heterogeneity and non-trivial structure of (human) mobility. We propose DTN-Meteo: a new unified analytical model that maps an important class of DTN optimization problems and the respective (greedy) algorithms into a Markov chain traversal over the relevant solution space. Fully heterogeneous node contact patterns and a range of algorithmic actions jointly (but separably) define transition probabilities. Thus, we provide closed-form solutions for crucial performance metrics under generic settings. While DTN-Meteo has wider applicability, in this paper, we focus on algorithms with explicitly controlled replication. We apply our model to two problems: routing and content placement. We predict the performance of state of the art algorithms (SimBet, BubbleRap) in various real and synthetic mobility scenarios and show that surprising precision can be achieved against simulations, despite the complexity of the problems and diversity of settings. To our best knowledge, this is the first analytical work that can accurately predict performance for utility-based algorithms and heterogeneous node contact rates.

Epidemic spreading is one of the most popular bio-inspired principles, which has made its way into computer networking. This principle naturally applies to Opportunistic or Delay Tolerant Networks (DTNs), where nodes probabilistically meet their neighbors thanks to mobility. Epidemic-based algorithms are often the only choice for DTN problems such as broadcast and unicast routing, distributed estimation etc. Existing analyses of epidemic spreading in various contexts only consider specific graph geometries (complete, random, regular etc) and/or homogeneous exponential node meeting rates. In addition, in wired networks, synchronous communication is usually assumed. In this paper, we relax these assumptions and provide a detailed analysis of epidemic spreading in DTNs with heterogeneous node meeting rates. We observe the special properties of a Markov model, describing the epidemic process and use them to derive bounds for the delay (expectation and distribution). We apply our analysis to epidemic-based DTN algorithms for routing and distributed estimation and validate the bounds against simulation results, using various real and synthetic mobility scenarios. Finally, we empirically show that the delay distribution is relatively concentrated, and that, depending on graph properties (communities, scale-freeness), the delay scales very well with network size.

In order to achieve data delivery in Delay Tolerant Networks (DTN), researchers have proposed the use of store-carry-and-forward protocols: a node there may store a message in its buffer and carry it along for long periods of time, until an appropriate forwarding opportunity arises. This way, messages can traverse disconnected parts of the network. Multiple message replicas are often propagated to further increase delivery probability. This combination of long-term storage and message replication imposes a high storage and bandwidth overhead. Thus, efficient scheduling and drop policies are necessary to 1) decide on the order by which messages should be replicated when contact durations are limited, and 2) which messages should be discarded when nodes' buffers operate close to their capacity. In this paper, we propose a practical and efficient joint scheduling and drop policy that can optimize different performance metrics, such as average delay and delivery probability. We first use the theory of encounter-based message dissemination to derive the optimal policy based on global knowledge about the network. Then, we introduce a method that estimates all necessary parameters using locally collected statistics. Based on this, we derive a distributed scheduling and drop policy that can approximate the performance of the optimal policy in practice. Using simulations based on synthetic and real mobility traces, we show that our optimal policy and its distributed variant outperform existing resource allocation schemes for DTNs. Finally, we study how sampled statistics can reduce the signaling overhead of our algorithm and examine its behavior under different congestion regimes. Our results suggest that close to optimal performance can be achieved even when nodes sample a small percentage of the available statistics.

Opportunistic or Delay Tolerant Networks (DTNs) are envisioned to complement existing wireless technologies (cellular, WiFi). Wireless peers communicate when in contact, forming a network "on the fly", whose connectivity graph is highly dynamic and only partly connected. Because of this stringent environment, solutions to common networking problems (routing, congestion control, etc.) in this context are greedy, choosing the best solution among the locally available ones. This shared trait motivates the common treatment of such greedy algorithms for DTNs and raises some interesting questions: Do they converge? How fast are they? Yet, existing models study individual solutions. Moreover, they often assume homogeneous node mobility. The study of real world traces reveals considerable heterogeneity and non-trivial structure in human mobility. While algorithms have been proposed, accounting for this heterogeneity, their analytical tractability is still a challenge. In this paper, we propose a new model for greedy DTN algorithms, supporting the full heterogeneity of node mobility. We provide closed form solutions for crucial performance metrics (delivery probability and delay) and prove necessary and sufficient conditions for algorithm convergence. For illustration, we apply our model to the content placement problem, a variant of distributed caching. We use real and synthetic mobility traces to validate our findings and examine the impact of mobility properties in depth.

Realistic mobility models are crucial for the simulation of Delay Tolerant and Opportunistic Networks. The long standing benchmark of reproducing realistic pairwise statistics (e.g., contact and inter-contact time distributions) is today mastered by state-of-the-art models. However, mobility models should also reflect the macroscopic community structure of who meets whom. While some existing models reproduce realistic community structure - reflecting groups of nodes who work or live together - they fail in correctly capturing what happens between such communities: they are often connected by few bridging links between nodes who socialize outside of the context and location of their home communities. In a first step, we analyze the bridging behavior in mobility traces and show how it differs to that of mobility models. By analyzing the context and location of contacts, we then show that it is the social nature of bridges which makes them differ from intra-community links. Based on these insights, we propose a Hypergraph to model time-synchronized meetings of nodes from different communities as a social overlay. Applying this as an extension to two existing mobility models we show that it reproduces correct bridging behavior while keeping other features of the original models intact.

Opportunistic networks use human mobility and consequent wireless contacts between mobile devices to disseminate data in a peer-to-peer manner. Designing appropriate algorithms and protocols for such networks is challenging as it requires understanding patterns of (1) mobility (who meets whom), (2) social relations (who knows whom) and (3), communication (who communicates with whom). To date, apart from few small test setups, there are no operational opportunistic networks where measurements could reveal the complex correlation of these features of human relationships. Hence, opportunistic networking research is largely based on insights from measurements of either contacts, social networks, or communication, but not all three combined. In this paper we report an experiment called Stumbl, as a step towards collecting rich datasets comprising social, mobility and communication ties. Stumbl is a Facebook application that provides participating users with a user-friendly interface to report their daily face-to-face meetings with other Facebook friends. It also logs user interactions on Facebook (e.g. comments, wall posts, likes). This way the contact graph, social graph, and activity graphs for the same set of users could be compared and analyzed. We report here preliminary results and analyses of a first experiment we have performed.

Interference is an inherent characteristic of wireless (multihop) communications. Adding interference-awareness to important control functions, e.g., routing, could significantly enhance the overall network performance. Despite some initial efforts, it is not yet clearly understood how to best capture the effects of interference in routing protocol design. Most existing proposals aim at inferring its effect by actively probing the link. However, active probe measurements impose an overhead and may often misrepresent the link quality due to their interaction with other networking functions. Therefore, in this paper we follow a different approach and: 1) propose a simple yet accurate analytical model for the effect of interference on data reception probability, based only on passive measurements and information locally available at the node; 2) use this model to design an efficient interference-aware routing protocol that performs as well as probing-based protocols, yet avoids all pitfalls related to active probe measurements. To validate our proposal, we have performed experiments in a real testbed, setup in our indoor office environment. We show that the analytical predictions of our interference model exhibit good match with both experimental results as well as more complicated analytical models proposed in related literature. Furthermore, we demonstrate that a simple probeless routing protocol based on our model performs at least as good as well-known probe-based routing protocols in a large set of experiments including both intraflow and interflow interference.

Recently, webmail interfaces, e.g., Horde, Outlook Web Access, and webmail platforms such as GMail, Yahoo!, and Hotmail have seen a tremendous boost in popularity. Given the importance of e-mail for personal and business use alike, and its exposure to imminent threats, there exists the need for a comprehensive view of the Internet mail system, including webmail traffic. We, in this paper, propose a novel, passive approach to identify webmail traffic solely based on network-level data in order to obtain a comprehensive view of the mail system. Key to our approach is that we leverage correlations across protocols and time to introduce three novel features for HTTPS webmail classification. Our first feature is based on the finding that webmail servers tend to reside close to legacy mail servers, e.g. IMAP and POP, which can be easily identified. Our second feature leverages that the usage of webmail services results in distinct patterns on sessions' duration and on the diurnal/weekly traffic usage profile. In addition, our third feature exploits the observation that traffic flows to webmail platforms exhibit inherent periodicities due to the fact that AJAX-based clients periodically check for new messages. We use these three features to build a simple classifier and detect webmail traffic on real-world NetFlow traces from a medium-sized backbone network. We believe that the major contribution of this paper -- exploring a set of new features that could classify applications that run over HTTPS ports solely based on NetFlow data -- will stimulate more general advance in the field of traffic classification.

Delay Tolerant Networks (DTN) are networks of self-organizing wireless nodes, where end-to-end connectivity is intermittent. In these networks, forwarding decisions are generally made using locally collected knowledge about node behavior (e.g., past contacts between nodes) to predict future contact opportunities. The use of complex network analysis has been recently suggested to perform this prediction task and improve the performance of DTN routing. Contacts seen in the past are aggregated to a social graph, and a variety of metrics (e.g., centrality and similarity) or algorithms (e.g., community detection) have been proposed to assess the utility of a node to deliver a content or bring it closer to the destination. In this paper, we argue that it is not so much the choice or sophistication of social metrics and algorithms that bears the most weight on performance, but rather the mapping from the mobility process generating contacts to the aggregated social graph. We first study two well-known DTN routing algorithms - SimBet and BubbleRap - that rely on such complex network analysis, and show that their performance heavily depends on how the mapping (contact aggregation) is performed. What is more, for a range of synthetic mobility models and real traces, we show that improved performances (up to a factor of 4 in terms of delivery ratio) are consistently achieved for a relatively narrow range of aggregation levels only, where the aggregated graph most closely reflects the underlying mobility structure. To this end, we propose an online algorithm that uses concepts from unsupervised learning and spectral graph theory to infer this 'correct' graph structure; this algorithm allows each node to locally identify and adjust to the optimal operating point, and achieves good performance in all scenarios considered.

Communication networks, whether they are wired or wireless, have traditionally been assumed to be connected at least most of the time. However, emerging applications such as emergency response, special operations, smart environments, VANETs, etc. coupled with node heterogeneity and volatile links (e.g. due to wireless propagation phenomena and node mobility) will likely change the typical conditions under which networks operate. In fact, in such scenarios, networks may be mostly disconnected, i.e., most of the time, end-to-end paths connecting every node pair do not exist. To cope with frequent, long-lived disconnections, opportunistic routing techniques have been proposed in which, at every hop, a node decides whether it should forward or store-and-carry a message. Despite a growing number of such proposals, there still exists little consensus on the most suitable routing algorithm(s) in this context. One of the reasons is the large diversity of emerging wireless applications and networks exhibiting such “episodic” connectivity. These networks often have very different characteristics and requirements, making it very difficult, if not impossible, to design a routing solution that fits all. In this paper, we first break up existing routing strategies into a small number of common and tunable routing modules (e.g. message replication, coding, etc.), and then show how and when a given routing module should be used, depending on the set of network characteristics exhibited by the wireless application. We further attempt to create a taxonomy for intermittently connected networks. We try to identify generic network characteristics that are relevant to the routing process (e.g., network density, node heterogeneity, mobility patterns) and dissect different “challenged” wireless networks or applications based on these characteristics. Our goal is to identify a set of useful design guidelines that will enable one to choose an appropriate routing protocol for the application or network in hand. Finally, to demonstrate the utility of our approach, we take up some case studies of challenged wireless networks, and validate some of our routing design principles using simulations.

Mobile wireless network research focuses on scenarios at the extremes of the network connectivity continuum where the probability of all nodes being connected is either close to unity, assuming connected paths between all nodes (mobile ad hoc networks), or it is close to zero, assuming no multi-hop paths exist at all (delay-tolerant networks). In this paper, we argue that a sizable fraction of networks lies between these extremes and is characterized by the existence of partial paths, i.e., multi-hop path segments that allow forwarding data closer to the destination even when no end-to-end path is available. A fundamental issue in such networks is dealing with disruptions of end-to-end paths. Under a stochastic model, we compare the performance of the established end-to-end retransmission (ignoring partial paths), against a forwarding mechanism that leverages partial paths to forward data closer to the destination even during disruption periods. Perhaps surprisingly, the alternative mechanism is not necessarily superior. However, under a stochastic monotonicity condition between current vs. future path length, which we demonstrate to hold in typical network models, we manage to prove superiority of the alternative mechanism in stochastic dominance terms. We believe that this study could serve as a foundation to design more efficient data transfer protocols for partially-connected networks, which could potentially help reducing the gap between applications that can be supported over disconnected networks and those requiring full connectivity.

Communication networks are traditionally assumed to be connected. However, emerging wireless applications such as vehicular networks, pocket-switched networks, etc., coupled with volatile links, node mobility, and power outages, will require the network to operate despite frequent disconnections. To this end, opportunistic routing techniques have been proposed, where a node may store-and-carry a message for some time, until a new forwarding opportunity arises. Although a number of such algorithms exist, most focus on relatively homogeneous settings of nodes. However, in many envisioned applications, participating nodes might include handhelds, vehicles, sensors, etc. These various "classes” have diverse characteristics and mobility patterns, and will contribute quite differently to the routing process. In this paper, we address the problem of routing in intermittently connected wireless networks comprising multiple classes of nodes. We show that proposed solutions, which perform well in homogeneous scenarios, are not as competent in this setting. To this end, we propose a class of routing schemes that can identify the nodes of "highest utility” for routing, improving the delay and delivery ratio by four to five times. Additionally, we propose an analytical framework based on fluid models that can be used to analyze the performance of various opportunistic routing strategies, in heterogeneous settings.

Delay Tolerant Networks are wireless networks where disconnections may occur frequently due to propagation phenomena, node mobility, and power outages. Propagation delays may also be long due to the operational environment (e.g. deep space, underwater). In order to achieve data delivery in such challenging networking environments, researchers have proposed the use of store-carry-and-forward protocols: there, a node may store a message in its buffer and carry it along for long periods of time, until an appropriate forwarding opportunity arises. Additionally, multiple message replicas are often propagated to increase delivery probability. This combination of long-term storage and replication imposes a high storage overhead on untethered nodes (e.g. handhelds). Thus, efficient buffer management policies are necessary to decide which messages should be discarded, when node buffers are operated close to their capacity. In this paper, we propose efficient buffer management policies for delay tolerant networks. We show that traditional buffer management policies like drop-tail or drop-front fail to consider all relevant information in this context and are, thus, sub-optimal. Using the theory of encounter-based message dissemination, we propose an optimal buffer management policy based on global knowledge about the network. Our policy can be tuned either to minimize the average delivery delay or to maximize the average delivery rate. Finally, we introduce a distributed algorithm that uses statistical learning to approximate the global knowledge required by the the optimal algorithm, in practice. Using simulations based on a synthetic mobility model and real mobility traces, we show that our buffer management policy based on statistical learning successfully approximates the performance of the optimal policy in all considered scenarios. At the same time, our policy outperforms existing ones in terms of both average delivery rate and delivery delay.

Delay tolerant networks (DTN) are wireless networks where disconnections may occur frequently. In order to achieve data delivery in DTNs, researchers have proposed the use of store-carry-and-forward protocols: there, a node may store a message in its buffer and carry it along for long periods of time, until an appropriate forwarding opportunity arises. Multiple message replicas are often propagated to increase delivery probability. This combination of long-term storage and replication imposes a high storage and bandwidth overhead. Thus, efficient scheduling and drop policies are necessary to: (i) decide on the order by which messages should be replicated when contact durations are limited, and (ii) which messages should be discarded when nodespsila buffers operate close to their capacity. In this paper, we propose an efficient joint scheduling and drop policy that can optimize different performance metrics, like average delay and delivery probability. Using the theory of encounter-based message dissemination, we first propose an optimal policy based on global knowledge about the network. Then, we introduce a distributed algorithm that can approximate the performance of the optimal algorithm, in practice. Using simulations based on a synthetic mobility model and a real mobility trace, we show that our optimal policy and its distributed variant outperform existing resource allocation schemes for DTNs, such as the RAPID protocol [4], both in terms of average delivery ratio and delivery delay.

Interference is an inherent property of wireless multihop networks. Adding interference-awareness to their control functions can significantly enhance the overall network performance. In this paper we present an analytical model for the probability that a transmission destined to an arbitrary network node is successful in the presence of interference from other nodes in the network. We introduce the concept of interference areas and interference zones to express this probability as a function of the network density, node transmission probability, radio propagation environment, and network card reception sensitivity. Our derivation includes a simpleMAC model, which captures the carrier sense function of many MAC protocols. Contrary to measurementbased models, our derivation only requires information that is locally available to the nodes, avoiding all measurement-related pitfalls. The validation of our model against experiments in a real testbed, set up for this purpose in our indoor office environment, shows good match of the experimental results with the analytical predictions. Interestingly our model predictions follow closely those of more elaborate state-of-the-art analytical models. Finally, to demonstrate the real utility of our model, we have implemented on our testbed a routing metric that explicitly takes interference into account via our derivation. The throughputs of the resulting routes compare favorably with those achieved by a well-known probe-based routing metric.

Realistic mobility models are important to understand the performance of routing protocols in wireless ad hoc networks, especially when mobility-assisted routing schemes are employed, which is the case, for example, in delay-tolerant networks (DTNs). In mobility-assisted routing, messages are stored in mobile nodes and carried across the network with nodal mobility. Hence, the delay involved in message delivery is tightly coupled with the properties of nodal mobility. Currently, commonly used mobility models are simplistic random i.i.d. model that do not reflect realistic mobility characteristics. In this paper we propose a novel time-variant community mobility model. In this model, we define communities that are visited often by the nodes to capture skewed location visiting preferences, and use time periods with different mobility parameters to create periodical re-appearance of nodes at the same location. We have clearly observed these two properties based on analysis of empirical WLAN traces. In addition to the proposal of a realistic mobility model, we derive analytical expressions to highlight the impact on the hitting time and meeting times if these mobility characteristics are incorporated. These quantities in turn determine the packet delivery delay in mobility-assisted routing settings. Simulation studies show our expressions have error always under 20%, and in 80% of studied cases under 10%.

Communication networks (wired or wireless) have traditionally been assumed to be connected at least most of the time. However, emerging applications such as emergency response, special operations, smart environments, VANETs, etc. coupled with node heterogeneity and volatile links will likely change the typical conditions under which networks operate. In fact, in such scenarios, networks may be mostly disconnected. To cope with frequent, long-lived disconnections, opportunistic routing techniques have been proposed in which, at every hop, a node decides whether it should either forward and/or store-and-carry a message. As a result, a number of message replicas may be created and routed independently ("spraying"). Most opportunistic routing schemes to-date perform greedy replication handing over a copy of a message to the first nodes encountered. Yet, in a network with heterogeneous nodes, where some nodes may be much "better" relays than others, such greedy schemes may waste valuable message replicas (and thus energy, storage space, etc.) on "useless" relays. For this reason, we propose the idea of utility-based replication, where some fitness or utility function is maintained for all nodes in a distributed fashion, and a small budget of message replicas is allocated according to this utility only to the fittest nodes. We describe a number of variations using different utility functions, and show that an improvement of up to 5-6× in delay can be achieved over greedy algorithms.

Traditionally, ad hoc networks have been viewed as a connected graph over which end-to-end routing paths had to be established.Mobility was considered a necessary evil that invalidates paths and needs to be overcome in an intelligent way to allow for seamless ommunication between nodes.However, it has recently been recognized that mobility an be turned into a useful ally, by making nodes carry data around the network instead of transmitting them. This model of routing departs from the traditional paradigm and requires new theoretical tools to model its performance. A mobility-assisted protocol forwards data only when appropriate relays encounter each other, and thus the time between such encounters, called hitting or meeting time, is of high importance.In this paper, we derive accurate closed form expressions for the expected encounter time between different nodes, under ommonly used mobility models. We also propose a mobility model that can successfully capture some important real-world mobility haracteristics, often ignored in popular mobility models, and alculate hitting times for this model as well. Finally, we integrate this results with a general theoretical framework that can be used to analyze the performance of mobility-assisted routing schemes. We demonstrate that derivative results oncerning the delay of various routing s hemes are very accurate, under all the mobility models examined. Hence, this work helps in better under-standing the performance of various approaches in different settings, and an facilitate the design of new, improved protocols.

Adaptive array antennas have the ability to respond automatically to an unknown interference environment, in real time, by steering nulls and reducing side lobe levels in the direction of interference, while retaining some desired signal beam characteristics. We present a protocol (ADAPT) that enables nodes in an ad hoc network to utilize adaptive array antennas efficiently to communicate. We compare our adaptive antenna configuration {ADAPT, adaptive array antennas} to both an omni-directional setting {802.11, omni-directional antennas} and a directional one {DMAC protocol, directional antennas} in terms of network throughput and end-to-end delay. The DMAC protocol is described by M. Takai et al. (see Proc. ACM MobiHoc, 2002) and R. Roychoudhury et al. (see Proc. MOBICOM 2002). Our protocol achieves up to a 60% throughput and 2-3 times delay improvement over the omni-directional case and up to a 40% throughput and 55% delay improvement over the directional one, in most scenarios considered.