5G networks will support network slicing to address the diverging needs of 5G applications. In this paper, we lay out a system model and mathematical framework to analyze the impact of resource granularity of network slicing on service availability and densification. We establish closed form expressions for service/slice availability in two extremum points of system operation that correspond to very fine and very coarse resource allocation for slice instances. We call the system operation around these extremum points as micro-slicing and macro-slicing regimes, respectively. Our analysis indicates that micro-slicing can achieve multiple orders of magnitude difference in service availability against macro-slicing even with as few as two slice types. Our results also indicate that in the short run, macro-slicing with resource over-provisioning is a viable approach to support few slice types at carrier-grade availability, but this approach fails to scale to higher densities of slice types. Another crucial outcome of our analysis is that the relationship between the slice availability and resource granularity (of slice instances) is not monotonic due to a quantization effect. Thus, rather than adopting a gradual reduction in slice instance sizes, system architects should consider moving directly into the micro-slicing regime in order to support higher service densities in 5G cloud.

Telecommunication networks are converging to a massively distributed cloud infrastructure interconnected with software defined networks. In the envisioned architecture, services will be deployed flexibly and quickly as network slices. Our paper addresses a major bottleneck in this context, namely the challenge of computing the best resource provisioning for network slices in a robust and efficient manner. With tractability in mind, we propose a novel optimization framework which allows fine-grained resource allocation for slices both in terms of network bandwidth and cloud processing. The slices can be further provisioned and auto-scaled optimally based on a large class of utility functions in real-time. Furthermore, by tuning a slice-specific parameter, system designers can trade off traffic-fairness with computing-fairness to provide a mixed fairness strategy. We also propose an iterative algorithm based on the alternating direction method of multipliers (ADMM) that provably converges to the optimal resource allocation and we demonstrate the method's fast convergence in a wide range of quasi-stationary and dynamic settings.

Online social networks (OSNs) serve today as a platform for information dissemination. At the same time, mobile devices provide ubiquitous network access through the cellular infrastructure. In this paper, we develop mechanisms for minimizing the peak load of the cellular network due to information cascades spreading on social media. First, we exploit the social ties for predicting information dissemination and we propose Proactive Seeding-a technique for minimizing the peak load of cellular networks. Much of such a load is due to information cascades spreading in social media, and we address it by proactively pushing (“seeding”) content to selected users before they actually request it. We develop a family of algorithms that take as input information primarily about: (i) cascades on the OSN, (ii) the background traffic load in the cellular network, and (iii) the local connectivity among mobiles; the algorithms then select which nodes to seed and when. We prove that Proactive Seeding is optimal when the prediction of information cascades is perfect. We perform simulations driven by traces from Twitter and cellular networks and we find that Proactive Seeding reduces the peak cellular load by 20-50 percent. Then, we exploit the fact that there is correlation between social ties and physical proximity and we combine Proactive Seeding with device-to-device communication to further reduce the peak load.

We present a new set of solutions for topology verification and failure localization in Software Defined Networks (SDNs). Our solutions are targeted towards offloading the control plane as much as possible and bringing more resilience against congestion or partitioning in the control plane. The core idea is to define control flows for network diagnosis and utilize a fraction of the forwarding table rules on the switches to serve these control flows. For topology verification, we present provably optimal or order-optimal solutions in total number of static forwarding rules and control messages. For single link failure localization, we present a solution that requires at least 3 |E| but at most 6 |E| forwarding rules using at most 1+log2 |E| control messages, where |E| denotes the number of bidirectional links in the forwarding plane. We analyze the latency vs. rule and control message optimality trade-offs showing that sub-second failure localization is possible even in data center scale networks without significant additional overhead in the number of static rules and control messages. We further simulate the performance of failure localization in identifying multiple link failures.

Recent literature including our past work provides analysis and solutions for using: 1) erasure coding; 2) parallelism; or 3) variable slicing/chunking (i.e., dividing an object of a specific size into a variable number of smaller chunks) in speeding up the I/O performance of storage clouds. However, a comprehensive approach that considers all three dimensions together to achieve the best throughput-delay tradeoff curve had been lacking. This paper presents the first set of solutions that can pick the best combination of coding redundancy ratio and object chunking/slicing options as the load dynamically changes. Our specific contributions are as follows: 1) We establish via measurements that combining variable redundancy ratio and chunking is mostly feasible over a popular public cloud. 2) We relate the delay-optimal values for chunking level and code redundancy ratio to the queue backlogs via an approximate queuing analysis. 3) Based on this analysis, we propose TOFEC that adapts the chunking level and redundancy ratio against the queue backlogs. Our trace-driven simulation results show that TOFEC's adaptation mechanism converges to an appropriate code that provides the optimal throughput-delay tradeoff without reducing system capacity. Compared to a nonadaptive strategy optimized for throughput, TOFEC delivers 2.5× lower latency under light workloads; compared to a nonadaptive strategy optimized for latency, TOFEC can scale to support over 3× as many requests. 4) We propose a simpler greedy solution that performs on a par with TOFEC in average delay performance, but exhibits significantly more performance variations.

We consider a heterogeneous network scenario where macro cells provide continuous coverage and many small cells with short transmission ranges within the coverage area of each macro cell provide high capacity access. We focus on scenarios where most small cells can be put on the sleep mode and macro cell capacity is sufficient for serving a large fraction of user population. Few users generate high demand and thus a small fraction of small cell base stations (SC-BS) that can serve these users should be ideally powered on to offload the macro cell base station (MC-BS). As different sets of users create demand surge over time, a network controller should keep track of peak demand locations and power on a minimal number of SC-BSs. We propose a new solution to this end. Our solution iteratively determines which SC-BSs should be turned on and performs power control to dictate the coverage area of each SC-BS. We use the flow byte counters on the MC-BS and active SC-BSs to form a system of linear equations and use linear optimization using L1norm of the demand vector as the objective function to localize the demand. Our evaluations indicate that the solution is quite effective in tracking the peak demand locations. For instance in one particularly challenging scenario with heavy-tailed i.i.d. spatial distribution for peak demand, 80% of the peak demand locations were identified correctly more than 90% of the time using less than 7% of the SC-BSs.

We investigate near-optimal load balancing and auto-scaling solutions that can get the best delay performance while attaining high utilization in two-tier cloud storage systems. The first tier consists of a distributed cache composed of leased resources from a computing cloud (e.g., Amazon EC2) and the second tier consists of a persistent distributed storage (e.g., Amazon S3). At any point in time our solutions dynamically determine how many cache servers should be active as the incoming load, object popularities, and service rate of persistent storage are subject to change. We first present a load balancing solution for a given set of cache servers that can evenly distribute the load against workloads with an unknown Zipf distribution while keeping the overall cache hit ratios close to the maximum. Building on this load balancer, we then present our auto-scaling solution that uses the request backlogs in the caching tier to determine the number of active cache servers to be used in the next epoch. Via simulations, we show that the end-to-end design is quite effective in converging to the right amount of service capacity against the system dynamics.

Storage clouds, such as Amazon S3, are being widely used for web services and Internet applications. It has been observed that the delay for retrieving data from and placing data into the clouds is quite random, and exhibits weak correlations between different read/write requests. This inspires us to investigate a key problem: can we reduce the delay by transmitting data replications in parallel or using powerful erasure codes? In this paper, we study the problem of reducing the delay of downloading data from cloud storage systems by leveraging multiple parallel threads, assuming that the data has been encoded and stored in the clouds using fixed rate forward error correction (FEC) codes with parameters (n, k). That is., each file is divided into k equal-sized chunks, which are then expanded into n chunks such that any k chunks out of the n are sufficient to successfully restore the original file. The model can be depicted as a multiple-server queue with arrivals of data retrieving requests and a server corresponding to a thread. However, this is not a typical queueing model because a server can terminate its operation, depending on when other servers complete their service (due to the redundancy that is spread across the threads). Hence, to the best of our knowledge, the analysis of this queueing model remains quite uncharted. Real traces from Amazon S3 show that the time to retrieve a fixed size chunk is random and can be accurately approximated as an i.i.d. exponentially distributed random variable. We show that any work-conserving scheme is delay-optimal when k = 1. When k > 1, we find that a simple greedy scheme, which allocates all available threads to the head of line request, is delay optimal, which appears surprising.

Software Defined Networks (SDN) decouple the forwarding and control planes from each other. The control plane is assumed to have a global knowledge of the underlying physical and/or logical network topology so that it can monitor, abstract and control the forwarding plane. When parts of the control plane become unavailable or unreliable, individual controllers should still be able to monitor the forwarding plane and run diagnostics to take the correct routing actions. In our paper, we present solutions that install an optimal or near-optimal number of static forwarding rules on switches/routers for any controller to be able to verify the topology connectivity and detect/locate link failures at data plane speeds without relying on state updates from forwarding plane nodes and other controllers while requiring reachability to only one (arbitrary) forwarding node. Our upper bounds on performance indicate that sub-second link failure localization is possible even at data-center scale networks. For networks with hundreds or few thousand links, tens of milliseconds of latency is achievable.

Our paper presents solutions using erasure coding, parallel connections to storage cloud and limited chunking (i.e., dividing the object into a few smaller segments) together to significantly improve the delay performance of uploading and downloading data in and out of cloud storage. TOFEC is a strategy that helps front-end proxy adapt to level of workload by treating scalable cloud storage (e.g. Amazon S3) as a shared resource requiring admission control. Under light workloads, TOFEC creates more smaller chunks and uses more parallel connections per file, minimizing service delay. Under heavy workloads, TOFEC automatically reduces the level of chunking (fewer chunks with increased size) and uses fewer parallel connections to reduce overhead, resulting in higher throughput and preventing queueing delay. Our trace-driven simulation results show that TOFEC's adaptation mechanism converges to an appropriate code that provides the optimal delay-throughput trade-off without reducing system capacity. Compared to a non-adaptive strategy optimized for throughput, TOFEC delivers 2.5× lower latency under light workloads; compared to a non-adaptive strategy optimized for latency, TOFEC can scale to support over 3× as many requests.

Our paper presents solutions that can significantly improve the delay performance of putting and retrieving data in and out of cloud storage. We first focus on measuring the delay performance of a very popular cloud storage service Amazon S3. We establish that there is significant randomness in service times for reading and writing small and medium size objects when assigned distinct keys. We further demonstrate that using erasure coding, parallel connections to storage cloud and limited chunking (i.e., dividing the object into a few smaller objects) together pushes the envelope on service time distributions significantly (e.g., 76%, 80%, and 85% reductions in mean, 90th, and 99th percentiles for 2-MB files) at the expense of additional storage (e.g., 1.75$\times$). However, chunking and erasure coding increase the load and hence the queuing delays while reducing the supportable rate region in number of requests per second per node. Thus, in the second part of our paper, we focus on analyzing the delay performance when chunking, forward error correction (FEC), and parallel connections are used together. Based on this analysis, we develop load-adaptive algorithms that can pick the best code rate on a per-request basis by using offline computed queue backlog thresholds. The solutions work with homogeneous services with fixed object sizes, chunk sizes, operation type (e.g., read or write) as well as heterogeneous services with mixture of object sizes, chunk sizes, and operation types. We also present a simple greedy solution that opportunistically uses idle connections and picks the erasure coding rate accordingly on the fly. Both backlog-based and greedy solutions support the full rate region and provide best mean delay performance when compared to the best fixed coding rate policy. Our evaluations show that backlog-based solutions achieve better delay performance at higher percentile values than the greedy solution.

We propose novel load balancers for key-value data stores running as a service over geographically distributed data centers. We assume that the key-value store has the following properties: (i) The requests (e.g., put/write, get/read, copy, etc.) can be directed to any one of the cluster nodes regardless of which cluster nodes store the information; (ii) Different objects can have different number of replicas and applications can set their desired consistency levels; and (iii) it is possible for intermediate (authorized) proxies to query/learn cluster topology and key space to node mappings. We propose two load balancing strategies that would be useful under these assumptions: (i) Static strategy that makes assignment decisions solely based on where the majority of the hosting nodes are located for a given key. (ii) Dynamic strategy where proxy nodes actively probe the performance of different cluster nodes as a function of their location (i.e., which data center they belong) and key-specific operational parameters (e.g., consistency level and replication factor) to select the best cluster node to serve each request. Our evaluations show that 2× gains for average read/write delays against random load balancers, while dynamic approach significantly outperforming the static approach between 60th and 90th percentiles.

We propose a new framework for wireless network virtualization. In this framework, service providers (SPs) and the network operator (NO) are decoupled from each other: The NO is solely responsible for spectrum management, and SPs are responsible for quality-of-service (QoS) management for their own users. SPs compete for the shared wireless resources to satisfy their distinct service objectives and constraints. We model the dynamic interactions among SPs and the NO as a stochastic game. SPs bid for the resources via dynamically announcing their value functions. The game is regulated by the NO through: 1) sum-utility optimization under rate region constraints; 2) enforcement of Vickrey-Clarke-Groves (VCG) mechanism for pricing the instantaneous rate consumption; and 3) declaration of conjectured prices for future resource consumption. We prove that there exists one Nash equilibrium in the conjectural prices that is efficient, i.e., the sum-utility is maximized. Thus, the NO has the incentive to compute the equilibrium point and feedback to SPs. Given the conjectural prices and the VCG mechanism, we also show that SPs must reveal their truthful value functions at each step to maximize their long-term utilities. As another major contribution, we develop an online learning algorithm that allows the SPs to update the value functions and the NO to update the conjectural prices iteratively. Thus, the proposed framework can deal with unknown dynamics in traffic characteristics and channel conditions. We present simulation results to show the convergence to the Nash equilibrium prices under various dynamic traffic and channel conditions.

Online social networks (OSNs) play an increasingly important role today in informing users about content. At the same time, mobile devices provide ubiquitous access to this content through the cellular infrastructure. In this paper, we exploit the fact that the interest in content spreads over OSNs, which makes it, to a certain extent, predictable. We propose Proactive Seeding-a technique for minimizing the peak load of cellular networks, by proactively pushing (“seeding”) content to selected users before they actually request it. We develop a family of algorithms that take as input information primarily about (i) cascades on the OSN and possibly about (ii) the background traffic load in the cellular network and (iii) the local connectivity among mobiles; the algorithms then select which nodes to seed and when. We prove that Proactive Seeding is optimal when the prediction of information cascades is perfect. In realistic simulations, driven by traces from Twitter and cellular networks, we find that Proactive Seeding reduces the peak cellular load by 20%-50%. Finally, we combine Proactive Seeding with techniques that exploit local mobile-to-mobile connections to further reduce the peak load.

Online social networks (OSNs) provide new means of disseminating information about applications and contents served by network providers. OSN members often reveal their usage information and opinion about applications and contents to their neighbors within their social networks. Consequently, sudden popularity and viral propagation of applications among OSN members can put significant burden on network resources and degrade network performance. Further, viral exchanges might propagate malicious applications and such propagation might need to be kept in check. Accordingly, we propose a novel content distribution architecture that controls the resource utilization within an operator's network by utilizing the existing social connections between users and building a model of information diffusion within the social network. Our method is based upon computing a reward function that takes into account the influence of users over each other in a given social network in terms of application adoption and content consumption. Based on this reward function and assuming that not only the users but also the network operator can limit the exposure of application usage and content consumption over the online social networks, we present algorithms to slow down or speed up the adoption/consumption of different applications/contents given the current state of both the physical network and the social network. We evaluate the effectiveness of this method over a Flickr data set. Results suggest that such a control is indeed possible and the proposed method significantly outperforms other approaches that employs mainly degree-based mechanisms for controlling the information dissemination over the social graphs.

Erasure coding has been proposed in distributed storage systems for both high data reliability and low storage redundancy. With virtualization, virtual machines (VMs) are essentially defined by software and by their memory states, and erasure coding can be used in the same manner as in storage for high reliability and availability. Each VM can backup its memory state to a hot spare, and multiple memory states are coded at the hot spare to provide data reliability and low redundancy. This poses a new set of challenges. Both synchronization and recovery of the VMs consume significant bandwidth which may impede the performance of a data center. To guarantee high availability, recovery from a machine failure (decoding) at the hot spare must be fast. When (de)coding is done in-network, computation can be distributed over hosts, routers or switches and bandwidth for synchronization and recovery can be reduced significantly. We show the conditions needed to support optimal rates for synchronization and recovery for many-to-one backup in arbitrary networks. Furthermore, we propose routing and code construction algorithms that run in polynomial-time.

We consider a cellular system where (i) wireless spectrum is divided into resource blocks in time and frequency, (ii) each wireless receiver is assigned one or more resource blocks as the exclusive (primary) user of these blocks, (iii) some of the resource blocks are under-utilized due to the mismatch between the primary user's application payload and the capacity of the dedicated resources, and (iv) there are users with backlogged traffic that cannot be fully served by only utilizing their own dedicated resource blocks. We show how partially utilized resource blocks in a given cell can be reutilized by conveying extra information to the backlogged users in the system (secondary users) by coding over the transmission patterns of the primary users. Specifically, we propose to create on-off transmission patterns (referred to as silence coding), where during on periods the base-station sends primary user's symbols and during off periods the base-station keeps silent. Distinct transmission patterns in return are used to carry different messages for a given secondary user. We first analyze the achievable rate region for primary and secondary users from an information theoretical point of view for randomly generated codebooks. Then, we propose practical schemes that use permutation codes for silence coding with and without forward error correction. Finally, we evaluate the performance of these practical schemes.

We propose a virtualization framework to separate the network operator (NO) who focuses on wireless resource management and service providers (SP) who target distinct objectives with different constraints. Within the proposed framework, we model the interactions among SPs and NO as a stochastic game, each stage of which is played by SPs (on behalf of the end users) and is regulated by the NO through the Vickrey-Clarke-Groves (VCG) mechanism. Due to the strong coupling between the future decisions of SPs and lack of global information at each SP, the stochastic game is notoriously hard. Instead, we introduce conjectural prices to represent the future congestion levels the end users potentially will experience, via which the future interactions between SPs are decoupled. Then, the policy to play the dynamic rate allocation game becomes selecting the conjectural prices and announcing a strategic value function (i.e., the preference on the rate) at each time. We prove that there exists one Nash equilibrium in the conjectural prices and, given the conjectural prices, the SPs have to truthfully reveal their own value function. We further prove that this Nash equilibrium results in efficient rate allocation in our virtualized wireless network. In other words, there are enough incentives for NO to advertise such a conjectural price and SPs to follow this advice.

We investigate optimal resource allocation and power management in virtualized data centers with time-varying workloads and heterogeneous applications. Prior work in this area uses prediction based approaches for resource provisioning. In this work, we take an alternate approach that makes use of the queueing information available in the system to make online control decisions. Specifically, we use the recently developed technique of Lyapunov Optimization to design an online admission control, routing, and resource allocation algorithm for a virtualized data center. This algorithm maximizes a joint utility of the average application throughput and energy costs of the data center. Our approach is adaptive to unpredictable changes in the workload and does not require estimation and prediction of its statistics.

Virtualization is a key enabler to autonomic management of hosted services in data centers. We show that it can be used to manage reliability of these virtual entities with virtual backups. An architecture is proposed to autonomously manage and allocate the physical resources, ensure reliability guarantees, and manage the pools of virtual backups for failure recovery and resource conservation. It is fault tolerant by design so that component failures do not bring down the entire data center.

Media flows coexist with TCP-based data traffic on the Internet and are required to be TCP-friendly. The TCP protocol slowly increases its sending rate until episodes of congestion occur, and then it quickly reduces its rate to remove congestion. However, media flows can be sensitive to even brief episodes of congestion. In this paper, we are interested in protecting media flows from TCP-induced congestion while maintaining their TCP friendliness. In particular, we consider media flows carried over the TCP-Friendly Rate Control (TFRC) protocol and we design algorithms that dynamically adapt the level of forward error correction (FEC) based on the congestion state of the network. To this end, first, we investigate the loss and delay characteristics of TFRC flows in several TCP-induced congestion scenarios, and we develop novel predictors of loss events based on packet delay information. Second, we use these predictors to dynamically adapt the level of FEC protection based on the predicted level of congestion. We show that this technique can significantly improve the overhead versus reliability trade-off compared to fixed FEC. Third, we select the FEC and original media packets within each FEC block, in a rate-distortion optimized way, and we show that this technique significantly improves media quality.

In this paper, we propose a method for peer assisted on demand delivery of scalable video using an optimal, distributed caching algorithm for cache constrained peers. We assume that there are one or more content delivery servers that are provisioned to support delivery of the base layer for all of the peers, and the enhancement layer is only supported for a fraction of peers. It has been shown that in such an application, peer assisted content distribution improves the delivery of the content. In this paper, we use peer assisted delivery of the enhancement layer and show that in a cache constrained video-on-demand environment, availability of the cached content becomes a bottleneck. By using peer arrival rates and supply-demand analysis of the peers, we propose better caching policies at each peer. One proposed policy (referred to as "static optimal") optimizes the utility of the currently available caching opportunities. The other proposed policy (referred to as "dynamic programming" solution) on the other hand performs utility optimization by further considering the future caching opportunities during the streaming operation. Experimental results show that the proposed methods allow more peers to access the enhancement layer; hence, more peers experience improved video quality compared to traditional caching methods.

We propose an admission control policy that admits users into a public access network as soon as possible while limiting the overall security impact on the network and other users. In our model, each user has a particular reputation level when first requesting network access. Before admitting a user into the network, the initial risk of a user is assessed by the admission control system using past history and a scanning of the user's device which delays the user's admission into the network and updates the user's reputation level accordingly. We formulate the trade-off between the admission delay and security risk as a convex optimization problem, which can be solved for an admission control policy. The evaluation suggests that our approach can substantially increase the system security for public access networks while minimizing admission delay, in contrast to current approaches widely used in enterprise networks. The proposed framework extends the traditional quality of service- based admission control mechanisms with a well-defined notion of quality of security.

In this paper, we study rate control and scheduling over wireless networks with intersession network coding, as a utility maximization problem. We demonstrate that making rate control and scheduling aware of the underlying network coding increases throughput. The key intuition is that network coding introduces new network coded flows and eventually new conflicts between nodes, which should be taken into account both in rate control and in scheduling. We compare the network coding-aware to the network coding-unaware schemes in two cases: (i) optimal control and (ii) practical, suboptimal control. Our main goal is to make the case for network coding-aware rate control and scheduling, via simulation of representative examples. Along the way, we also propose a practical scheme that approximates the optimal control.

Interference between neighboring femtocells may have a critical impact on their performances. In this paper, impact of resource spreading is investigated on the capacity of two neighboring femtocell networks. It exploits the fact that at a given time, the number of active femtocell users may be much smaller than the maximum allowed, and the allocated spectrum may typically be under-utilized. The behavior of the capacities of two neighboring femtocell networks (one being under-utilized, and the other being fully-utilized) with respect to the spreading factor are analyzed for different interference conditions. Also, a rate-constrained resource utilization approach in the underutilized network is discussed. Through spreading the resources of the under-utilized femtocell, it is shown to improve the capacity of the fully utilized femtocell network in most scenarios.

In this paper, we consider a hybrid P2P video on-demand architecture that utilizes both the server and the peer resources for efficient transmission of popular videos. In our system architecture, each peer dedicates some cache space to store a particular segment of a video file as well as some of its upload bandwidth to serve the cached segment to other peers. Peers join the system and issue a streaming request to a control server. Control server directs the peers to streaming servers or to other peers who have the desired video segments. Control server also decides which peer should cache which video segment. Our main contribution in this paper is to determine the proper caching strategies at peers such that we minimize the average load on the streaming servers.

In this paper, we investigate the performance of opportunistic scheduling for delivering multicast information in an OFDM-based cellular network. The problem is formulated as a system throughput maximization problem subject to the fairness constraints derived from each user's specific minimum QoS requirement. As a solution we design an opportunistic scheduling algorithm based on a priority metric that follows an exponential rule. The metric takes into account the current channel state information to take advantage of the better channel states observed by different subsets of the multicast users at different time slots and sub-bands in order to increase the system throughput. The metric also explicitly includes a term to compensate the deviations observed by individual users from their QoS targets. Hence, our proposed algorithm jointly considers two issues in multicasting: throughput maximization and fairness in terms of the targeted QoS levels. In the paper, we further investigate the impact of feedback frequency on the system performance. For scenarios where feedback is not available for every time slot, a probabilistic scheduling algorithm is proposed based on a finite state Markov channel (FSMC) that models the underlying fading channel. Our simulation results show that our algorithm can achieve significantly better performance compared to other commonly used algorithms. Moreover, the solution can also achieve graceful performance degradation when CSI feedback is not available at every time slot.

In this paper, we concentrate on opportunistic scheduling for multicast information. We pose the problem as a multicast throughput optimization problem. As a solution we present how one can jointly utilize fixed-rate and rateless erasure coding along with simple rate adaptation techniques in order to achieve the optimal multicast throughput per user. We first investigate the performance of the proposed system under i.i.d. channel conditions. Our analysis shows a linear gain for the multicast capacity over i.i.d. Rayleigh fading channels with respect to the number of users. Since the established results require coding over large number of blocks and hence induce large decoding delays, we extend our analysis to the cases where we code over shorter block lengths and thus quantify the delay-capacity tradeoffs under a simple setting. We further look into non-i.i.d. channel conditions and show achievable gains by modifying a scheduling heuristic whose fairness is well- established for opportunistic scheduling of unicast flows. Our overall evaluations demonstrate that under both i.i.d. and non-i.i.d. channel conditions, opportunistic multicasting with erasure coding can significantly improve the performance over the traditional techniques used in today's communication systems.

Due to the low cost and ease of deployment, singlehop and multi-hop 802.11 networks have become attractive solutions for providing last-mile broadband (wireless) access in urban environments. However, a critical issue in using such networks to support applications such as Voice over IP is the widely known overheads in the Medium Access Control (MAC) layer and Physical (PHY) layer for each transmission. The effect of these overheads can be more severe in multi-hop deployments, and can limit the number of VoIP calls per Gateway Access Point (GAP) in a multi-hop system to be no greater than that of a single-hop single-GAP system. In this paper, we build upon our previous work that showed that a multi-hop network, with one GAP using a single channel, can in fact support more users than a single-hop network. To do so functions such as aggregation have to be intelligently used at relays in the network. We build on this prior work giving a theoretical framework that considers the joint tradeoff of aggregation, bursting, and PHY rate adaptation given a set of admission and routing decisions. We compare call-capacity estimates from the theory to those derived from simulations, and illustrate through examples the advantages of considering routing/ admission decisions jointly with bursting and aggregation.

We present a method for network coding over time-varying networks with attractive tradeoffs between throughput and decoding-delay. We model the time-varying networks as a sequence of topology graphs. The method relies on designing a deterministic network code for a fixed virtual graph derived from the actual sequence of topologies, and on exploiting proper buffering in order to implement the code over the actual network. We show that, under certain conditions, this approach can achieve the maximum achievable throughput over the given time- varying network. We also present simulation results that validate the theoretical findings.

In this paper, we are interested in the design and performance of unequal error protection (UEP) rateless codes. These codes have interesting properties in the deployment of mobile peer to peer (MP2P) and mobile broadcast systems. As our main contribution, we propose a new UEP rateless code structure that is composed of a bank of precoders and a common rateless code. Through the bank of precoders, information layers are first expanded into encoded layers with a diminishing coding rate as the priority of the layer increases. The output of precoders are then concatenated and fed into a rateless encoder. The output of the rateless encoder naturally constitutes UEP encoding blocks carrying disproportionately more information on the higher priority layers. The decoder at the receiver end performs the inverse operations to recover each layer separately. We evaluate our proposed scheme comparing against the alternative solutions. Results show that over a broad class of rateless code structures the proposed scheme can substantially reduce the time required to recover higher priority layers while minimally impacting the time required to recover the lower priority layers.

We propose a gaining architecture, called the overlay server system (OSS), for supporting multiparty online games over mobile networks. In OSS architecture, overlay server nodes (OSN) are distributed across the core network architecture of the mobile operator and each node is responsible for both running the game applications and performing the overlay routing. The architecture allows third party game servers that are located outside the core network of the mobile operator to push the execution of delay and bandwidth constrained game components into the core to achieve better quality of service (QoS). When a game consists of multiple mutually exclusive game objects such that each object can be maintained independently, OSS allows per object QoS optimization via selecting the jointly optimal location (i.e. OSN) and overlay routes for each object. This fine-grain optimization benefits most when different objects have different QoS requirements and they are accessed by different users. OSS dynamically adapts to the changes in game and network conditions by switching to better OSN and overlay routes. Our performance analysis on different core network topologies and usage patterns demonstrates that OSS has significant advantages over the alternative peer to peer (P2P), proxy-server, and client-server architectures. The analysis also underlines the individual contributions of object placement and jointly performed overlay route optimization to the performance gain.

Wireless local area networks (WLANs) are emerging as a popular technology for access to the Internet and enterprise networks. In the long term, the success of WLANs depends on services that support mobile network clients. Although other researchers have explored mobility prediction in hypothetical scenarios, evaluating their predictors analytically or with synthetic data, few studies have been able to evaluate their predictors with real user mobility data. As a first step towards filling this fundamental gap, we work with a large data set collected from the Dartmouth College campus-wide wireless network that hosts more than 500 access points and 6,000 users. Extending our earlier work that focuses on predicting the next-visited access point (i.e., location), in this work we explore the predictability of the time of user mobility. Indeed, our contributions are two-fold. First, we evaluate a series of predictors that reflect possible dependencies across time and space while benefiting from either individual or group mobility behaviors. Second, as a case study we examine voice applications and the use of handoff prediction for advance bandwidth reservation. Using application-specific performance metrics such as call drop and call block rates, we provide a picture of the potential gains of prediction. Our results indicate that it is difficult to predict handoff time accurately, when applied to real campus WLAN data. However, the findings of our case study also suggest that application performance can be improved significantly even with predictors that are only moderately accurate. The gains depend on the applications’ ability to use predictions and tolerate inaccurate predictions. In the case study, we combine the real mobility data with synthesized traffic data. The results show that intelligent prediction can lead to significant reductions in the rate at which active calls are dropped due to handoffs with marginal increments in the rate at which new calls are blocked.

We present an empirical registration model derived from the WLAN registration patterns of the mobile users. There exist models that accurately describe individually the spatial and temporal aspects of user registration, and demonstrate the importance of this modeling. The main distinction of the new model from the previous empirical models is that we are able to formulate the inter-dependence of space and time explicitly by a set of few equations. Our extensive studies of the WLAN traces indicate that a simple but proper notion of popularity radient suffices to capture the correlation across space and time. Indeed, when locations (i.e., AP coverage area) are differentiated with respect to the number of visits they are receiving (i.e., AP popularity), the time spent at each location i before user moves from i to k turns out to be closely related to the difference of popularity between locations i and k This observation led to the design of a joint time-space registration model (referred to as ModelT++) that builds upon the Model T, which itself models only the space aspect of the registration, but is derived from the same campus WiFi network. As part of the process of generating a joint space-time model, we further extend spatial aspects of the Model T. We evaluate our model using various metrics against a random walk model as well as the Model T by superimposing location independent time series on these space-only registration models. Our results suggest that with a slight increase in the model complexity, our joint time-space registration model is able to better capture the real network registration than the independent time models. Model T++ can be easily integrated into both WLAN and multi-hop wireless mesh network simulations that require realistic registration models.

Wireless Local Area Networks (WLANs) based on IEEE 802.11 standards are becoming widespread and are now being considered as potential solutions for providing "last-mile" wireless IP-based services. One of the challenges to this end however comes from the grave inefficiencies in the CSMA-based 802.11 medium access control (MAC) when used with application payloads that are relatively small. This is the case seen in the important application of Voice over IP (VoIP). The inefficiencies becomes even more severe in multi-hop wireless mesh systems that use 802.11 radio interfaces. In this paper we present novel strategies that are in conformance with the 802.11 mechanism while at the same time providing significant performance improvements for such applications. Our main approach will be one of jointly combining routing and traffic shaping decisions together to improve the efficiency of DCF functions. Specifically we try to change the traffic characteristics at different hops in the network by combining multiple flows to produce new traffic and flow statistics. Correct routing enables one to do such changes and, therefore, by performing routing and traffic shaping decisions jointly we can improve the efficiency of 802.11 mesh networks. To demonstrate the effectiveness of the proposed scheme, we focus on the two-hop mesh architectures and consider the VoIP traffic as the application of interest. We specifically investigate the achievable throughput region with and without the traffic shaping mechanisms. Our experiments show that more than a 3-fold call-capacity improvements can be gained over the conventional transport methods.

Next generation wireless CDMA systems will provide high and variable data rates by using multicode structures, controllable code spreading gains, and transmit power adaptation. We address the emerging resource allocation problem in that context and consider maximizing the total achievable user rate while satisfying minimum rate requirements of users. We devise symbol-synchronous and asynchronous models that capture different communication scenarios. The synchronous model holds for down-link transmission in one cell. The asynchronous model captures up-link single-cell communication and down-link or up-link scenarios in multicell systems. It can also account for multipath with each path corresponding to a virtual user. We propose a class of two-stage resource allocation algorithms. First, an admissible set of codes is constructed with criteria that capture code cross-correlation, induced interference to the system, and code rates. Next, the codes are allocated to users so as to satisfy their rate requirements. In the synchronous case, the problem structure allows the distinction of the two stages. In the asynchronous case, this distinction is not feasible due to different user delay profiles perceived at the receiver. Our models and numerical results indicate interesting trends and lead to useful conclusions and design guidelines for resource allocation algorithms under the aforementioned regimes.

In recent years, it has become common consensus that independent consideration of communication layers often turns out to be inadequate in terms of providing the desired quality of service (QoS) and power efficiency in wireless networks. The need for a synergistic, cross-layer design framework has already been identified. In that respect, our work constitutes an important step towards a better understanding of the cross-layer paradigm by simultaneously targeting both the power efficiency and the end-to-end QoS in multi-hop wireless networks. More specifically, we address the joint problem of power control and scheduling with the objective of minimizing the total transmit power subject to the end-to-end bandwidth guarantees and the bit error rate constraints of each communication session. After identifying the inherent difficulty of the problem, we propose two classes of heuristic algorithms that rely on graph theory principles as well as on derived metrics such as effective interference. The first heuristic follows a top-down design strategy by solving the schedule feasibility problem as the initial step and then targeting the total power efficiency. On the other hand, the second heuristic follows a bottom-up approach that schedules one wireless link at a time by greedily filling up the available time slots. The simulation results reveal valuable insights about the performance of each strategy. The top-down design strategy turns out to address power efficiency issues better, whereas the bottom-up design strategy with a properly selected cost function for link scheduling shows better performance in finding a feasible solution, namely one that satisfies both the QoS and the transmit power constraints. Our results also illustrate the impact of routing decisions on the feasibility and the power efficiency of multi-hop wireless networks through employing different routing criteria in the experiments

Efficient use of energy while providing an adequate level of connection to individual sessions is of paramount importance in multi-hop wireless networks. Energy efficiency and connection quality depend on mechanisms that span several communication layers due to the existing co-channel interference among competing flows that must reuse the limited radio spectrum. Although independent consideration of these layers simplifies the system design, it is often insufficient for wireless networks when the overall system performance is examined carefully. The multi-hop wireless extensions and the need for routing users' sessions from source to the destination only intensify this point of view. In this work, we present a framework for cross-layer design towards energy-efficient communication. Our approach is characterized by a synergy between the physical and the medium access control (MAC) layers with a view towards inclusion of higher layers as well. More specifically, we address the joint problem of power control and scheduling with the objective of minimizing the total transmit power subject to the end-to-end quality of service (QoS) guarantees for sessions in terms of their bandwidth and bit error rate guarantees. Bearing to the NP-hardness of this combinatorial optimization problem, we propose our heuristic solutions that follow greedy approaches.

The existing naming schemes for pooling resources are suitable only for static networks. We propose dynamic survivable resource pooling (DSRP) that provides a survivable naming scheme to the pool users in mobile ad-hoc networks. DSRP dynamically places the name servers (NSs) on a virtual backbone (VB): a highly distributed, scalable, and survivable mesh network formed and maintained through one-hop beacons. In this paper, DSRP focuses on pooling resources such as servers and services that are common in robotics and battlefield applications. It provides an abstraction of all the functionally equivalent servers, whereby the client can access these servers as a single entity, termed server pool. A distributed backbone mesh of NSs is used to propagate service registrations, requests, and replies.

Service discovery is an integral part of the ad hoc networking to achieve stand-alone and self-configurable communication networks. In this paper, we discuss possible service discovery architectures along with the required network support for their implementation, and we propose a distributed service discovery architecture which relies on a virtual backbone for locating and registering available services within a dynamic network topology. Our proposal consists of two independent components: (i) formation of a virtual backbone and (ii) distribution of service registrations, requests, and replies. The first component creates a mesh structure from a subset of a given network graph that includes the nodes acting as service brokers and a subset of paths (which we refer as virtual links) connecting them. Service broker nodes (SBNs) constitute a dominating set, i.e. all the nodes in the network are either in this set or only one-hop away from at least one member of the set. The second component establishes subtrees rooted at service requesting nodes and registering servers for efficient dissemination of the service discovery probing messages. Extensive simulation results are provided for comparison of performance measures. i.e. latency, success rate, and control message overhead, when different architectures and network support mechanisms are utilized in service discovery.

In this paper, we consider the transport capacity of ad hoc networks with a random flat topology under the present support of an infinite capacity infrastructure network. Such a network architecture allows ad hoc nodes to communicate with each other by purely using the remaining ad hoc nodes as their relays. In addition, ad hoc nodes can also utilize the existing infrastructure fully or partially by reaching any access point (or gateway) of the infrastructure network in a single or multi-hop fashion. Using the same tools as in [1], we show that the per source node capacity of T(W/log(N)) can be achieved in a random network scenario with the following assumptions: (i) The number of ad hoc nodes per access point is bounded above, (ii) each wireless node, including the access points, is able to transmit at W bits/sec using a fixed transmission range, and (iii) N ad hoc nodes, excluding the access points, constitute a connected topology graph. This is a significant improvement over the capacity of random ad hoc networks with no infrastructure support which is found as T(W/vN log(N)) in [1]. Although better capacity figures may be obtained by complex network coding or exploiting mobility in the network, infrastructure approach provides a simpler mechanism that has more practical aspects. We also show that even when less stringent requirements are imposed on topology connectivity, a per source node capacity figure that is arbitrarily close to T(1) cannot be obtained. Nevertheless, under these weak conditions, we can further improve per node throughput significantly.

In this paper, we propose the virtual dynamic backbone protocol (VDBP) for ad hoc networks. VDBP constructs a backbone from a subset of the nodes in the network satisfying these two properties: (i) Any node in the network is either a backbone node or is a neighbor of a backbone node (dominating set property), (ii) any pair of backbone nodes is connected via other backbone nodes (connectivity property). VDBP provides explicit mechanisms to handle the mobility of the nodes and depends on local computations to a large extent. Thus it is highly self-organizing even under highly dynamic topologies. Such a backbone can be potentially used by a routing protocol to disseminate broadcast or multicast messages as well as to handle QoS traffic in mobile ad hoc networks. We present the performance of VDBP in terms of backbone size and connectivity using simulations.

In this paper we present RBRP, a TDMA-based distributed medium access control (MAC) protocol for broadcast reservations in mobile ad hoc networks. The primary design goal of RBRP is robustness of broadcast reservations in the presence of hidden terminals, reservation deadlocks and mobility. Specifically, RBRP is characterized by four important features: (i) a two step signaling process in which the reservation signaling part is completely decoupled from the data portion of the frame; (ii) a multiple mini-slot reservation request phase within a reservation slot to prevent deadlocks; (iii) special signaling at the beginning of every data slot to adapt to topology changes and (iv) an optimization to improve the spatial reuse of the channel, and hence the utilization, with unicast traffic. Using a detailed simulation model in ns-2, we evaluated the performance of RBRP in comparison with the IEEE 802.11 distributed coordination function (DCF) MAC. Our simulation results show that RBRP achieves more than 100% throughput improvement over 802.11 DCF in the presence of hidden terminals and mobility, both for broadcast and unicast traffic, while having comparable performance in a fully connected network.