Cellular networks are carefully planned to provide sufficient coverage and capacity under normal circumstances. However, in emergency scenarios like floodings, wildfires, earthquakes or even terrorist attacks, part of the network may no longer be operational while at the same time a traffic hotspot may occur as a consequence of such an event. In such scenarios it is of utmost importance to quickly restore wireless coverage with sufficient capacity. To achieve this goal, we consider the dynamic deployment of drone-mounted base stations and propose a data-driven algorithm which optimizes the positions of the drone base stations based on measurement values that are readily available. We demonstrate that the use of well-positioned drones yields significant performance improvements and that the proposed method outperforms relevant benchmarks and is able to achieve close to optimal performance. For example, in rural scenarios we may observe in certain cases a twofold reduction in the fraction of failed calls compared to a pre-planned deployment of drones, and an even greater improvement over a setting without drones.

Reliable mobile communications is of critical importance, and should be maintained even in case of extremely crowded events or emergency scenarios. In such scenarios the deployment of drone-mounted base stations offers an agile and cost-efficient way to sustain coverage and/or provide capacity relief. In this paper we develop an analytical method to estimate the blocking and coverage probabilities of drone-assisted cellular networks using information that is readily available from network planning tools. We demonstrate how this method can be used to determine the minimum required number of drones and their corresponding locations for a given target performance level.

In this paper we establish a necessary and sufficient stability condition for a stochastic ring network. Such networks naturally appear in a variety of applications within communication, computer, and road traffic systems. They typically involve multiple customer types and some form of priority structure to decide which customer receives service. These two system features tend to complicate the issue of identifying a stability condition, but we demonstrate how the ring topology can be leveraged to solve the problem.

We consider a large-scale service system where incoming tasks have to be instantaneously dispatched to one out of many parallel server pools. The user-perceived performance degrades with the number of concurrent tasks and the dispatcher aims at maximizing the overall quality of service by balancing the load through a simple threshold policy. We demonstrate that such a policy is optimal on the fluid and diffusion scales, while only involving a small communication overhead, which is crucial for large-scale deployments. In order to set the threshold optimally, it is important, however, to learn the load of the system, which may be unknown. For that purpose, we design a control rule for tuning the threshold in an online manner. We derive conditions that guarantee that this adaptive threshold settles at the optimal value, along with estimates for the time until this happens. In addition, we provide numerical experiments that support the theoretical results and further indicate that our policy copes effectively with time-varying demand patterns. Summary of Contribution: Data centers and cloud computing platforms are the digital factories of the world, and managing resources and workloads in these systems involves operations research challenges of an unprecedented scale. Due to the massive size, complex dynamics, and wide range of time scales, the design and implementation of optimal resource-allocation strategies is prohibitively demanding from a computation and communication perspective. These resource-allocation strategies are essential for certain interactive applications, for which the available computing resources need to be distributed optimally among users in order to provide the best overall experienced performance. This is the subject of the present article, which considers the problem of distributing tasks among the various server pools of a large-scale service system, with the objective of optimizing the overall quality of service provided to users. A solution to this load-balancing problem cannot rely on maintaining complete state information at the gateway of the system, since this is computationally unfeasible, due to the magnitude and complexity of modern data centers and cloud computing platforms. Therefore, we examine a computationally light load-balancing algorithm that is yet asymptotically optimal in a regime where the size of the system approaches infinity. The analysis is based on a Markovian stochastic model, which is studied through fluid and diffusion limits in the aforementioned large-scale regime. The article analyzes the load-balancing algorithm theoretically and provides numerical experiments that support and extend the theoretical results.

We consider a system with several job types and two parallel server pools. Within the pools the servers are homogeneous, but across pools possibly not in the sense that the service speed of a job may depend on its type as well as the server pool. Immediately upon arrival, jobs are assigned to a server pool, possibly based on (partial) knowledge of their type. In case such knowledge is not available upon arrival, it can however be obtained while the job is in service; as the service progresses, the likelihood that the service speed of this job type is low increases, creating an incentive to execute the job on different, possibly faster, server(s). Two policies are considered: reroute the job to the other server pool, or replicate it there.We determine the effective load per server under both the rerouting and replication policy for completely unknown as well as partly known job types. We also examine the impact of these policies on the stability bound, which is defined as the maximum arrival rate of jobs for which the effective load per server is smaller than one. We demonstrate that the uncertainty in job types may significantly reduce the stability bound, and that for (highly) unbalanced service speeds full replication achieves the largest stability bound. Finally, we discuss how the use of threshold-based policies can help improve the expected latency for completely or partly unknown job types.

The use of drone base stations offers an agile mechanism to safeguard coverage and provide capacity relief when cellular networks are under stress. Such stress conditions can occur for example in case of special events with massive crowds or network outages. In this paper we focus on a disaster scenario with emergence of a hotspot, and analyze the impact of the drone position (altitude, horizontal position) and selection bias on the network performance. We determine the optimal settings of these control parameters as a function of the hotspot location, and demonstrate that the optimized values can drastically reduce the fraction of failed calls.

Drone base stations can help safeguard coverage and provide capacity relief when cellular networks are under stress. Examples of such stress scenarios are events with massive crowds or network outages. In this paper we focus on a disaster scenario with emergence of a traffic hotspot, where agile drone positioning and load management is a critical issue. In order to address this challenge, we propose and assess a data-driven algorithm which leverages real-time measurements to dynamically optimize the 3D position of the drone as well as a cell selection bias tuned for optimized load management. We compare the performance with three benchmark scenarios: i) no drone; ii) a drone positioned above the failing site; and iii) a drone with a statically optimized position and cell selection bias. The results demonstrate that the proposed algorithm significantly improves the call success rate and achieves close to optimal performance.

Load balancing plays a critical role in efficiently dispatching jobs in parallel-server systems such as cloud networks and data centers. A fundamental challenge in the design of load balancing algorithms is to achieve an optimal trade-off between delay performance and implementation overhead (e.g. communication or memory usage). This trade-off has primarily been studied so far from the angle of the amount of overhead required to achieve asymptotically optimal performance, particularly vanishing delay in large-scale systems. In contrast, in the present paper, we focus on an arbitrarily sparse communication budget, possibly well below the minimum requirement for vanishing delay, referred to as the hyper-scalable operating region. Furthermore, jobs may only be admitted when a specific limit on the queue position of the job can be guaranteed. The centerpiece of our analysis is a universal upper bound for the achievable throughput of any dispatcher-driven algorithm for a given communication budget and queue limit. We also propose a specific hyper-scalable scheme which can operate at any given message rate and enforce any given queue limit, while allowing the server states to be captured via a closed product-form network, in which servers act as customers traversing various nodes. The product-form distribution is leveraged to prove that the bound is tight and that the proposed hyper-scalable scheme is throughput-optimal in a many-server regime given the communication and queue limit constraints. Extensive simulation experiments are conducted to illustrate the results.

We investigate the stability condition for redundancy-d systems where each of the servers follows a processor-sharing (PS) discipline. We allow for generally distributed job sizes, with possible dependence among the d replica sizes being governed by an arbitrary joint distribution. We establish that for homogeneous servers the stability condition for the associated fluid-limit model is characterized by the expectation of the minimum of d replica sizes being less than the mean interarrival time per server. In the special case of identical replicas, the stability condition is insensitive to the job size distribution given its mean, and the stability threshold is inversely proportional to the number of replicas. In the special case of i.i.d. replicas, the stability threshold decreases (increases) in the number of replicas for job size distributions that are NBU (NWU). We also discuss the extension to heterogeneous servers. For heavy-tailed job sizes we characterize the tail behavior of the response time distribution. In particular, for regularly varying job sizes with tail index −ν it is shown that the tail index of the response time equals −ν and −dν for identical and i.i.d. replicas, respectively.

Abstract Due to the rising concerns of energy consumption in wireless networks, base station (BS) sleeping strategies were introduced to save energy in low traffic scenarios. In this paper we analyse a weighted trade-off between energy consumption and user-perceived performance in dense cellular networks. We present an optimization problem representing this trade-off and derive properties of its optimal solutions. Using these properties we design a self-organizing strategy that dynamically (online) makes load-aware user association and BS operation decisions. Our strategy is self-organizing in the sense that it does not need any information or optimization beforehand, it simply relies on real-time load measurements at the BSs and user-reported SINR values. We furthermore present extensive simulation results, demonstrating the effectiveness of our self-organizing strategy and the impact of increased energy consumption on the user-perceived performance.

A Network Inventory Manager (NIM) is a software solution that scans, processes and records data about all devices in a network. We consider the problem faced by a NIM that can send out a limited number of probes to track changes in a large, dynamic network. The underlying change rate for the Network Elements (NEs) is unknown and may be highly non-uniform. The NIM should concentrate its probe budget on the NEs that change most frequently with the ultimate goal of minimizing the weighted Fraction of Stale Time (wFOST) of the inventory. However, the NIM cannot discover the change rate of a NE unless the NE is repeatedly probed.We develop and analyze two algorithms based on Reinforcement Learning to solve this exploration-vs-exploitation problem. The first is motivated by the Thompson Sampling method and the second is derived from the Robbins-Monro stochastic learning paradigm. We show that for a fixed probe budget, both of these algorithms produce a potentially unbounded improvement in terms of wFOST compared to the baseline algorithm that divides the probe budget equally between all NEs. Our simulations of practical scenarios show optimal performance in minimizing wFOST while discovering the change rate of the NEs.

A key option to further increase mobile network capacity is to deploy dense cellular networks (DCNs). This densification of cellular networks raises challenging issues though, as it likely increases the spatial variation and temporal fluctuations in load. To harness the full potential of DCNs, cell selection algorithms must take these varying load conditions into account. In this paper we study the optimal user association in DCNs based on a Linear Program (LP). Since several system parameters tend to be unknown and time-varying in practice, we develop a dynamic, self-organizing, and load-aware cell selection algorithm: the Shadow Price Assignment (SPA) algorithm. Our algorithm realizes an optimal user association without explicit knowledge of the system parameters by using a parsimonious set of dynamically adapted control parameters. We establish convergence of the control parameters under suitable assumptions. For larger systems the convergence may be slower, and we propose a local clustering approach to further improve the user-perceived performance in systems with many APs. Extensive simulations confirm that the SPA algorithm substantially outperforms conventional approaches.

Network slicing provides a key functionality in emerging 5G networks, and offers flexibility in creating customized virtual networks and supporting different services on a common physical infrastructure. This capability critically relies on a MAC scheduler to deliver performance targets in terms of aggregate rates or resource shares for the various slices. A crucial challenge is to enforce such guarantees and performance isolation while allowing flexible sharing to avoid resource fragmentation and fully harness channel variations. In the present paper we propose a MAC scheduler which meets these objectives and preserves the basic structure of utility-based schedulers such as the Proportional Fair algorithm in terms of per-user scheduling metrics. Specifically, the proposed scheme involves counters tracking the aggregate rate or resource allocations for the various slices against pre-specified targets, and computes offsets to the scheduling metrics accordingly. This design provides transparency with respect to other scheduling modules, such as link adaptation and beam-forming. We analytically establish that the proposed scheme achieves optimal overall throughput utility subject to the various slicing constraints. In addition, extensive 3GPP-compliant simulation experiments are conducted to assess the impact on best-effort applications and demonstrate substantial gains in overall throughput utility over baseline approaches.

Network densification has emerged as a powerful paradigm to boost spectral efficiency and accommodate the continual rise in demand for wireless capacity. In dense cell deployments however, overlapping coverage areas may cause highly varying interference conditions among different cells. Moreover, denser networks experience more temporal load fluctuations due to daily and hourly changing usage patterns. The currently applied universal reuse frequency allocation is not suitable to deal with these issues, and needs to be tailored to dense cell deployments to ensure adequate performance in such scenarios. In this paper we present a dynamic, load aware and self-adapting frequency allocation scheme designed for dense cellular networks: the DyCRA scheme (Dynamic Cost/Reward based Allocation). The scheme makes decisions based on cost-reward trade-offs: rewards arise in the form of capacity, and costs arise in the form of interference (under spatial reuse). We quantify these costs and rewards based on SINR, and use periodic load estimates to determine if access points are in need of extra frequencies, or can spare them, and the cost/reward structure is used to determine which frequencies are allocated or released. Extensive simulation results show that the DyCRA scheme provides efficient resource allocations that adapt to changing traffic conditions and yields significant performance gains in scenarios with nonstationary traffic demands.

The development of 5G wireless networking is flourishing, introducing major paradigm shifts and key new technologies such as Radio- over-Fiber (RoF). A fundamental concept for achieving the 5G design objectives is dynamically allocating frequencies, sub-bands and wavelengths. While these allocation problems have been extensively studied in wireless and optical domains in isolation, the combination has received little attention so far. However, with the advances in software-defined radio access networking and RoF technologies, there is increasing need and scope for joint optimization across the two domains, in order to harness the full potential of these networks. Motivated by these observations, we introduce a model for jointly optimal sub-band and wavelength allocation in pico-cell networks where virtual access points (APs) transmit via remote radio heads (RRHs) connected through RoF technology. We specifically account for the optical network topology, which introduces a distinct set of constraints in both the optical and wireless domain. Since the resulting load balancing problem is NP-hard, we introduce a heuristic for obtaining a stabilizing allocation which provides all RRHs with sufficient spectrum capacity to deal with their load. Numerical experiments demonstrate that the heuristic provides near-optimal solutions.

As the Internet-of-Things (IoT) emerges, connecting immense numbers of sensors and devices, the continual growth in wireless communications increasingly manifests itself in terms of a larger and denser population of nodes with intermittent traffic patterns. A crucial issue that arises in these conditions is how to set the activation rates as a function of the network density and traffic intensity. Depending on the scaling of the activation rates, dense node populations may either result in excessive activations and potential collisions, or long delays that may increase with the number of nodes, even at low load. Motivated by the above issues, we examine optimal activation rate scalings in ultra-dense networks with intermittent traffic sources. We establish stability conditions, and provide closed-form expressions which indicate that the mean delay is roughly inversely proportional to the nominal activation rate. We also discuss a multi-scale mean-field limit, and use the associated fixed point to determine the buffer content and delay distributions. The results provide insight in the scalings that minimize the delay while preventing excessive activation attempts. Extensive simulation experiments demonstrate that the mean-field asymptotics yield highly accurate approximations, even when the number of nodes is moderate.

The Blockchain paradigm provides a popular mechanism for establishing trust and consensus in distributed environments. While Blockchain technology is currently primarily deployed in crypto-currency systems like Bitcoin, the concept is also expected to emerge as a key component of the Internet-of-Things (IoT), enabling novel applications in digital health, smart energy, asset tracking and smart transportation. As Blockchain networks evolve to industrial deployments with large numbers of geographically distributed nodes, the block transfer and processing delays arise as a critical issue which may create greater potential for forks and vulnerability to adversarial attacks. Motivated by these issues, we develop stochastic network models to capture the Blockchain evolution and dynamics and analyze the impact of the block dissemination delay and hashing power of the member nodes on Blockchain performance in terms of the overall block generation rate and required computational power for launching a successful attack. The results provide useful insight in crucial design issues, e.g., how to adjust the `difficulty-of-work' in the presence of delay so as to achieve a target block generation rate or appropriate level of immunity from adversarial attacks. We employ a combination of analytical calculations and simulation experiments to investigate both stationary and transient performance features, and demonstrate close agreement with measurements on a wide-area network testbed running the Ethereum protocol.

Network densification has emerged as a powerful paradigm to boost spectral efficiency and accommodate the continual rise in demand for wireless capacity. The corresponding reduction in cell sizes also results however in greater spatial and temporal uncertainty and variation in traffic patterns and more extreme and unpredictable interference conditions. These features create unprecedented challenges for efficient allocation of spectral resources compared to conventional cellular networks. As a further challenge, the allocation of spectral resources needs to be jointly optimized with the assignment of wavelengths in the optical backhaul of Radio-over-Fiber (RoF) networks, which are increasingly used in dense deployments and indoor environments. Motivated by these issues, we develop online algorithms for joint radio frequency and optical wavelength assignment in RoF networks. The proposed algorithms rely on load measurements at the various access points, and involve configurable thresholds for triggering (re)assignment of spectral resources. We provide a detailed specification of a system implementation, and conduct extensive simulation experiments to examine the behaviour in various scenarios and assess the impact of key parameters. The results in particular demonstrate that the proposed algorithms are capable of maintaining adequate load levels for spatially heterogeneous and time-varying traffic conditions, while providing favourable throughput performance.

Load balancing algorithms play a crucial role in delivering robust application performance in data centers and cloud networks. Recently, strong interest has emerged in Join-the-Idle-Queue (JIQ) algorithms, which rely on tokens issued by idle servers in dispatching tasks and outperform power-of-d policies. Specifically, JiQ strategies involve minimal information exchange, and yet achieve zero blocking and wait in the many-server limit. The latter property prevails in a multiple-dispatcher scenario when the loads are strictly equal among dispatchers. For various reasons it is not uncommon however for skewed load patterns to occur. We leverage product-form representations and fluid limits to establish that the blocking and wait then no longer vanish, even for arbitrarily low overall load. Remarkably, it is the least-loaded dispatcher that throttles tokens and leaves idle servers stranded, thus acting as bottleneck. Motivated by the above issues, we introduce two enhancements of the ordinary JIQ scheme where tokens are either distributed non-uniformly or occasionally exchanged among the various dispatchers. We prove that these extensions can achieve zero blocking and wait in the many-server limit, for any subcritical overall load and arbitrarily skewed load profiles. Extensive simulation experiments demonstrate that the asymptotic results are highly accurate, even for moderately sized systems.

Emerging 5G networks will not only offer higher link rates, but also integrate a variety of Radio Access Technologies (RATs) in order to provide ultra-reliable broadband access to a wide range of applications with high throughput and low latency requirements. SDN-enabled dynamic path selection is of critical importance in exploiting the collective transmission resources in such heterogeneous multi-RAT environments and delivering excellent user performance. In the present paper we propose the `best-rate' path selection algorithm for multi-RAT networks with various types of traffic flows. The best-rate algorithm accounts for the radio conditions and performance requirements of individual flows as well as the load conditions at the various access points. We analytically establish that the rates received by the various flows under the best-rate path selection, in conjunction with local fair resource sharing at the individual access points, are close to globally Proportional Fair. Detailed simulation experiments demonstrate that the best-rate algorithm achieves significant gains in terms of user-perceived throughput performance over various baseline policies.

Most load balancing techniques implemented in current data centers tend to rely on a mapping from packets to server IP addresses through a hash value calculated from the flow five-tuple. The hash calculation allows extremely fast packet forwarding and provides flow `stickiness', meaning that all packets belonging to the same flow get dispatched to the same server. Unfortunately, such static hashing may not yield an optimal degree of load balancing, e.g. due to variations in server processing speeds or traffic patterns. On the other hand, dynamic schemes, such as the Join-the-Shortest-Queue (JSQ) scheme, provide a natural way to mitigate load imbalances, but at the expense of stickiness violation.In the present paper we examine the fundamental trade-off between stickiness violation and packet-level latency performance in large-scale data centers. We establish that stringent flow stickiness carries a significant performance penalty in terms of packet-level delay. Moreover, relaxing the stickiness requirement by a minuscule amount is highly effective in clipping the tail of the latency distribution. We further propose a bin-based load balancing scheme that achieves a good balance among scalability, stickiness violation and packet-level delay performance. Extensive simulation experiments corroborate the analytical results and validate the effectiveness of the bin-based load balancing scheme.

With the rapid advance of the Internet of Everything, both the number of devices and the range of applications that rely on wireless connectivity show huge growth. Driven by these pervasive trends, wireless networks grow in size and complexity, supporting immense numbers of nodes and data volumes, with highly diverse traffic profiles and performance requirements. While well-established methods are available for evaluating the throughput of persistent sessions with saturated buffers, these provide no insight in the delay performance of flows with intermittent packet arrivals. The occurrence of empty buffers in the latter scenario results in a complex interaction between activity states and packet queues, which severely complicates the performance analysis. Motivated by these challenges, we develop a mean-field approach to analyze buffer contents and packet delays in wireless networks in a many-sources regime. The mean-field behavior simplifies the analysis of a large-scale network with packet arrivals and buffer dynamics to a low-dimensional fixed-point calculation for a network with saturated buffers. In particular, the analysis yields explicit expressions for the buffer content and packet delay distribution in terms of the fixed-point solution. Extensive simulation experiments demonstrate that these expressions provide highly accurate approximations, even for a fairly moderate number of sources.

The proliferation of smartphones has unleashed a tremendous growth in wireless traffic, which is projected to continue for the foreseeable future, and put yet greater strain on the capacity of cellular networks. Deployment of pico base stations, reducing cell sizes and allowing more efficient reuse of limited radio spectrum, provides a powerful approach to cope with traffic hot spots and bring capacity relief. This network densification raises a critical need for more intelligent cell selection algorithms, which not only take signal strength values into account, but also load conditions in order to harness the full potential of the pico cells. We describe how the problem of optimally balancing traffic loads among pico cells may be formulated as a linear program (LP), and show how the dual version of the LP provides insight in the structure of the optimal user association. Since the LP formulation involves several system parameters that tend to be time-varying and hard to estimate in practice, the optimal user association can not be calculated in a direct way. Hence, we develop various online cell selection algorithms that solve the LP and determine the optimal user association in a measurement-based manner, without requiring explicit knowledge of the system parameters. Extensive simulation experiments confirm that the algorithms are quite effective in optimally balancing the traffic loads, and further demonstrate that they substantially outperform conventional approaches in terms of user-perceived throughput performance.

We consider the problem of optimal rate allocation and admission control for adaptive video streaming sessions in wireless networks with user dynamics. The central aim is to achieve an optimal tradeoff between several key objectives: maximizing the average rate utility per user, minimizing the temporal rate variability, and maximizing the number of users supported. We derive sample path upper bounds for the long-term net utility rate in terms of either a linear program or a concave optimization problem, depending on whether the admissible rate set is discrete or continuous. We then show that the upper bounds are asymptotically achievable in large-scale systems by policies which either deny access to a user or assign it a fixed rate for its entire session, without relying on any advance knowledge of the duration. Moreover, the asymptotically optimal policies exhibit a specific structure, which allow them to be characterized through just a single variable, and have the further property that the induced offered load is unity. We exploit the latter insights to devise parsimonious online algorithms for learning and tracking the optimal rate assignments and establish the convergence of these algorithms. Extensive simulation experiments demonstrate that the proposed algorithms perform well, even in relatively small-scale systems.

This paper considers the problem of server-side scheduling for jobs composed of multiple pieces with consecutive (progressive) deadlines. One example is server-side scheduling for video service, where clients request flows of content from a server with limited capacity, and any content not delivered by its deadline is lost. We consider the simultaneous goals of 1) minimizing overall loss, and 2) differentiating loss fractions across classes of flows in proportion to relative weights. State-of-the-art policies, like Discriminatory Processor Sharing and Weighted Fair Queueing, use a fixed static proportional allocation of service rate and fail to achieve both goals. The well-known Earliest Deadline First policy minimizes overall loss, but fails to provide proportional loss across flows, because it treats packets as independent jobs. This paper introduces the Earliest Progressive Deadline First (EPDF) class of policies. We prove that all policies in this broad class minimize overall loss. Furthermore, we demonstrate that many EPDF policies accurately differentiate loss fractions in proportion to class weights, satisfying the second goal.

Mobile operators increasingly share their wireless networks to save cost. Some network parameters in the shared environment are operator-specific whereas others apply globally to all operators so their choice may lead to a disagreement between operators. We suggest that this problem can be solved by a voting system where operators cast weighted votes. We compare two weighting methods, namely the Proportional method and the so-called Penrose method for different operators' shares and benefits. We observe that the Penrose method performs especially well in cases where the foreseeable benefit of a decision is rather ambiguous for operators (in contrast, the distribution of operators' shares hardly influences which method is better). Even when operators' benefits of a decision are biased in one or the other direction according to a binomial distribution, the Penrose method performs better than the Proportional method overall. These findings are particularly relevant for multi-operator self-organizing networks (SON).

The deployment of pico cells to cover traffic hot spots within the footprint of a macro cell provides a powerful approach to meet the massive growth in traffic demands fueled by smartphones and bandwidth-hungry applications. Joint optimization of resource allocation and user association is critical to achieve the maximum capacity benefits and performance gains in such heterogeneous network deployments (HetNets). In order to gain insight in the achievable capacity gains, we examine in the present paper the stability and performance of a HetNet system in the presence of flow-level dynamics. The stability condition reveals that in stationary traffic conditions the maximum capacity can be achieved with a static resource split and traffic association rule, provided that these are suitably selected. This suggests that dynamic adaptation on time scales commensurate with the variations in traffic parameters suffices to extract most of the achievable capacity gains. For the case of static cell boundaries and Proportional Fair scheduling, we also present a method for evaluating the flow-level performance in terms of the distribution of the number of active file transfers and expected transfer delay.

We consider the problem of optimal rate allocation and admission control for adaptive video streaming sessions in wireless networks with user dynamics. The central aim is to achieve an optimal tradeoff between several key objectives: maximizing the average rate utility per user, minimizing the temporal rate variability, and maximizing the number of users supported. We identify the structure of algorithms that achieve asymptotically optimal performance in large-capacity systems, and exploit the insight into this structure to devise parsimonious and robust online algorithms. Extensive simulation experiments demonstrate that the proposed online algorithms perform well, even in systems with relatively small capacity.

As the use of wireless sensor networks increases, the need for (energy-)efficient and reliable broadcasting algorithms grows. Ideally, a broadcasting algorithm should have the ability to quickly disseminate data, while keeping the number of transmissions low. In this paper we develop a model describing the message count in large-scale wireless sensor networks. We focus our attention on the popular Trickle algorithm, which has been proposed as a suitable communication protocol for code maintenance and propagation in wireless sensor networks. Besides providing a mathematical analysis of the algorithm, we propose a generalized version of Trickle, with an additional parameter defining the length of a listen-only period. This generalization proves to be useful for optimizing the design and usage of the algorithm. For single-cell networks we show how the message count increases with the size of the network and how this depends on the Trickle parameters. Furthermore, we derive distributions of inter-broadcasting times and investigate their asymptotic behavior. Our results prove conjectures made in the literature concerning the effect of a listen-only period. Additionally, we develop an approximation for the expected number of transmissions in multi-cell networks. All results are validated by simulations.

Motivated by challenging resource allocation issues arising in large-scale wireless and wireline communication networks, we study distributed network utility maximization problems with a mixture of concave (e.g., best-effort throughputs) and nonconcave (e.g., voice/video streaming rates) utilities. In the first part of the paper, we develop our methodological framework in the context of a locally coupled networked system, where nodes represent agents that control a discrete local state. Each node has a possibly nonconcave local objective function, which depends on the local state of the node and the local states of its neighbors. The goal is to maximize the sum of the local objective functions of all nodes. We devise an iterative randomized algorithm, whose convergence and optimality properties follow from the classical framework of Markov Random Fields and Gibbs Measures via a judiciously selected neighborhood structure. The proposed algorithm is distributed, asynchronous, requires limited computational effort per node/iteration, and yields provable convergence in the limit. In order to demonstrate the scope of the proposed methodological framework, in the second part of the paper we show how the method can be applied to two different problems for which no distributed algorithm with provable convergence and optimality properties is available. Specifically, we describe how the proposed methodology provides a distributed mechanism for solving nonconcave utility maximization problems: 1) arising in OFDMA cellular networks, through power allocation and user assignment; 2) arising in multihop wireline networks, through explicit rate allocation. Several numerical experiments are presented to illustrate the convergence speed and performance of the proposed method.

Cloud providers may operate large-scale data centers in a few locations. We argue that deploying many small-scale data centers at network edge can significantly improve user experience in terms of latency. Small-scale data centers, however, may not be able to provide elastic services. In this paper, we investigate distributed small-scale data centers with load reallocation where jobs that cannot be suitably processed locally will be reallocated to remote data centers. We formulate an optimization problem for load reallocation in distributed data centers, provide performance comparisons among different alternatives and offer insights on handling multiple job types. We develop online optimization algorithms that can be operated in a decentralized and measurement-based fashion to dynamically reallocate load in response to sudden load surges. The experimental results demonstrate that elasticity can be practically provided by small-scale data centers enhanced with effective load reallocation techniques.

The deployment of pico cells to cover traffic hot spots within the footprint of a macro cell provides a powerful approach to meet the massive growth in traffic demands fueled by smartphones and bandwidth-hungry applications. Joint optimization of resource allocation and user association is of critical importance to achieve the maximum capacity benefits in such heterogeneous network deployments (HetNets). We first examine the problem of minimizing the amount of resources required to satisfy given traffic demands. We characterize the structure of the optimal solution, and identify a simple optimality condition in terms of the physical transmission rates of the edge users between the macro cell and the various pico cells. We further demonstrate how these structural properties can be leveraged in designing a distributed online algorithm for achieving a max-min fair throughput allocation across all users. Numerical experiments are presented to illustrate the results.

We explore the achievable delay performance in wireless random-access networks. While relatively simple and inherently distributed in nature, suitably designed backlog-based random-access schemes provide the striking capability to match the optimal throughput performance of centralized scheduling mechanisms. The specific type of activation rules for which throughput optimality has been established, may however yield excessive backlogs and delays. Motivated by that issue, we examine whether the poor delay performance is inherent to the basic operation of these schemes, or caused by the specific kind of activation rules. We derive delay lower bounds for backlog-based activation rules, which offer fundamental insight in the cause of the excessive delays. For fixed activation rates we obtain lower bounds indicating that delays and mixing times can grow dramatically with the load in certain topologies as well.

Recent advances have resulted in queue-based algorithms for medium access control which operate in a distributed fashion, and yet achieve the optimal throughput performance of centralized scheduling algorithms. However, fundamental performance bounds reveal that the "cautious" activation rules involved in establishing throughput optimality tend to produce extremely large delays, typically growing exponentially in 1/(1-r), with r the load of the system, in contrast to the usual linear growth. Motivated by that issue, we explore to what extent more "aggressive" schemes can improve the delay performance. Our main finding is that aggressive activation rules induce a lingering effect, where individual nodes retain possession of a shared resource for excessive lengths of time even while a majority of other nodes idle. Using central limit theorem type arguments, we prove that the idleness induced by the lingering effect may cause the delays to grow with 1/(1-r) at a quadratic rate. To the best of our knowledge, these are the first mathematical results illuminating the lingering effect and quantifying the performance impact.

The deployment of pico cells to cover traffic hot spots within the footprint of a macro cell provides a powerful approach to meet the massive growth in traffic demands fueled by smartphones and bandwidth-hungry applications. Joint optimization of resource allocation and user association is of critical importance to achieve the maximal capacity benefits in such heterogeneous network deployments (HetNets). We specifically examine the problem of maximizing the aggregate throughput utility of the various users. We characterize the structure of the optimal solution, and identify a simple optimality condition in terms of the transmission rates of the edge users between the macro cell and the various pico cells. Exploiting the structural properties, we develop distributed online algorithms for the broad class of alpha-fair utility functions, which includes several common fairness notions. Numerical experiments are presented to illustrate the results.

This paper considers the scheduling problem for networks with interference constraints and switchover delays, where it takes a nonzero time to reconfigure each service schedule. Switchover delay occurs in many telecommunication applications such as satellite, optical or delay tolerant networks (DTNs). Under zero switchover delay it is well known that the Max-Weight algorithm is throughput-optimal without requiring knowledge of the arrival rates. However, we show that this property of Max-Weight no longer holds when there is a nonzero switchover delay. We propose a class of variable frame based Max-Weight (VFMW) algorithms which employ the Max-Weight schedule corresponding to the beginning of the frame during an interval of duration dependent on the queue sizes. The VFMW algorithms dynamically adapt the frame sizes to the stochastic arrivals and provide throughput-optimality without requiring knowledge of the arrival rates. Numerical results regarding the application of the VFMW algorithms to DTN and optical networks demonstrate a good delay performance.

MaxWeight scheduling has gained enormous popularity as a powerful paradigm for achieving queue stability and maximum throughput in a wide variety of scenarios. The maximum-stability guarantees however rely on the fundamental premise that the system consists of a fixed set of flows with stationary ergodic traffic processes. In the present paper we examine networks where the population of active flows varies over time, as flows eventually end while new flows occasionally start. We show that MaxWeight policies may fail to provide maximum stability due to persistent inefficient spatial reuse. The intuitive explanation is that these policies tend to serve flows with large backlogs, even when the resulting spatial reuse is not particularly efficient, and fail to exploit maximum spatial reuse patterns involving flows with smaller backlogs. These results indicate that instability of MaxWeight scheduling can occur due to spatial inefficiency in networks with fixed transmission rates, which is fundamentally different from the inability to fully exploit time-varying rates shown in prior work. We discuss how the potential instability effects can be countered by spatial traffic aggregation, and describe some of the associated challenges and performance trade-offs.

We examine threshold-based transmission strategies for distributed opportunistic medium access in a scenario with fairly general probabilistic interference conditions. Specifically, collisions between concurrent transmissions are governed by arbitrary probabilities, allowing for a form of channel capture and covering binary interference constraints as an important special case. We address the problem of setting the threshold values so as to optimize the aggregate throughput utility of the various users, and particularly focus on a weighted logarithmic throughput utility function (Proportional Fairness). We provide an adaptive algorithm for finding the optimal threshold values in a distributed fashion, and rigorously establish the convergence of the proposed algorithm under mild statistical assumptions. Moreover, we discuss how the algorithm may be adapted to achieve packet-level stability with only limited exchange of queue length information among the various users. We also conduct extensive numerical experiments to corroborate the theoretical convergence results.

The delivery of video content is expected to gain huge momentum, fueled by the popularity of user-generated clips, growth of VoD libraries, and wide-spread deployment of IPTV services with features such as CatchUp/PauseLive TV and NPVR capabilities. The `time-shifted' nature of these personalized applications defies the broadcast paradigm underlying conventional TV networks, and increases the overall bandwidth demands by orders of magnitude. Caching strategies provide an effective mechanism for mitigating these massive bandwidth requirements by replicating the most popular content closer to the network edge, rather than storing it in a central site. The reduction in the traffic load lessens the required transport capacity and capital expense, and alleviates performance bottlenecks. In the present paper, we develop light-weight cooperative cache management algorithms aimed at maximizing the traffic volume served from cache and minimizing the bandwidth cost. As a canonical scenario, we focus on a cluster of distributed caches, either connected directly or via a parent node, and formulate the content placement problem as a linear program in order to benchmark the globally optimal performance. Under certain symmetry assumptions, the optimal solution of the linear program is shown to have a rather simple structure. Besides interesting in its own right, the optimal structure offers valuable guidance for the design of low-complexity cache management and replacement algorithms. We establish that the performance of the proposed algorithms is guaranteed to be within a constant factor from the globally optimal performance, with far more benign worst-case ratios than in prior work, even in asymmetric scenarios. Numerical experiments for typical popularity distributions reveal that the actual performance is far better than the worst-case conditions indicate.

The design of scheduling policies for wireless data systems has been driven by a compromise between the objectives of high overall system throughput and the degree of fairness among users, while exploiting multi-user diversity, i.e., fast-fading variations. These policies have been thoroughly investigated in the absence of user mobility, i.e., without slow fading variations. In the present paper, we examine the impact of intra- and inter-cell user mobility on the trade-off between throughput and fairness, and on the suitable choice of alpha-fair scheduling policies. We consider a dynamic setting where users come and go over time as governed by random finite-size data transfers, and explicitly allow for users to roam around. It is demonstrated that the overall performance improves as the fairness parameter alpha is reduced, and in particular, that proportional fair scheduling may yield relatively poor performance, in sharp contrast to the standard scenario with only fast fading. Since a lower alpha tends to affect short-term fairness, we explore how to set the fairness parameter so as to strike the right balance between overall performance and short-term fairness. It is further established that mobility tends to improve the performance, even when the network operates under a local fair scheduling policy as opposed to a globally optimal strategy. We present extensive simulation results to confirm and illustrate the analytical findings.

MaxWeight scheduling algorithms provide an effective mechanism for achieving queue stability and guaranteeing maximum throughput in a wide variety of scenarios. The maximum-stability guarantees however rely on the fundamental premise that the system consists of a fixed set of sessions with stationary ergodic traffic processes. In the present paper we examine a scenario where the population of active sessions varies over time, as sessions eventually end while new sessions occasionally start. We identify a simple necessary and sufficient condition for stability, and show that MaxWeight policies may fail to provide maximum stability. The intuitive explanation is that these policies tend to give preferential treatment to flows with large backlogs, so that the rate variations of flows with smaller backlogs are not fully exploited. In the usual framework with a fixed collection of flows, the latter phenomenon cannot persist since the flows with smaller backlogs will build larger queues and gradually start receiving more service. With a dynamic population of flows, however, MaxWeight policies may constantly get diverted to arriving flows, while neglecting the rate variations of a persistently growing number of flows in progress with relatively small remaining backlogs. We also perform extensive simulation experiments to corroborate the analytical findings.

We examine threshold-based transmission strategies for distributed opportunistic medium access, and specifically address the problem of setting the threshold values so as to optimize the aggregate throughput utility of the various users. In the case of weighted logarithmic throughput utility (proportional fairness) we provide an adaptive algorithm for finding the optimal threshold values in a distributed fashion. Moreover, we discuss how the algorithm may be adapted to achieve packet-level stability with only limited exchange of queue length information among the various users. We also present numerical results to demonstrate the convergence of the proposed adaptive algorithm.

One of the key questions in dimensioning a hybrid P2P content distribution system is that of the required infrastructure support in terms of server bandwidth. In this paper, we develop and propose simple mathematical models for analyzing and dimensioning hybrid peer-to-peer content distribution networks. We first use a deterministic fluid model to capture the essential peer and server dynamics within a single swarm, and subsequently derive a stochastic fluid model to capture the dynamics in the case of multiple swarms, i.e., concurrent swarms of a number of content objects. Based on the models, we derive solutions for estimating the server capacity required to support a single swarm as well as a number of concurrent file swarms at a given level of service quality. Numerical results demonstrate how a hybrid P2P approach can yield substantial performance gains and capacity savings compared to a pure client/server system, with churn rate and upload bandwidth being critical factors. Compared to a pure peer-to-peer scenario, the hybrid approach can dramatically boost the performance and improve reliability.

Channel-aware scheduling strategies have emerged as an effective mechanism for improving the throughput of wireless data users by exploiting rate variations. The improvement in throughput comes however at the expense of an increase in the variability of the service rate received over time. While the larger variability only has a limited impact on delay-tolerant data transfers, it does severely affect delay-sensitive applications. In order to examine the merits of channel-aware scheduling for the latter users, we consider a wireless system supporting a combination of streaming and elastic traffic. We first examine a scenario with rate-adaptive streaming traffic, and analyze the flow-level performance in terms of transfer delays and user throughputs for various canonical resource sharing schemes. Simulation experiments demonstrate that the analytical results yield remarkably accurate estimates, and indicate that channel-aware scheduling achieves significant performance gains. Next we investigate a scenario where the streaming sources have an intrinsic rate profile and stringent delay requirements. In that case, channel-aware scheduling yields only modest performance gains, and may even be harmful.

Valiant's concept of randomized load balancing (RLB), also promoted under the name 'two-phase routing', has previously been shown to provide a cost-effective way of implementing overlay networks that are robust to dynamically changing demand patterns. RLB is accomplished in two steps; in the first step, traffic is randomly distributed across the network, and in the second step traffic is routed to the final destination. One of the benefits of RLB is that packets experience only a single stage of routing, thus reducing queueing delays associated with multi-hop architectures. In this paper, we study the queuing performance of RLB, both through analytical methods and packet-level simulations using ns2 on three representative carrier networks. We show that purely random traffic splitting in the randomization step of RLB leads to higher queuing delays than pseudo-random splitting using, e.g., a round-robin schedule. Furthermore, we show that, for pseudo-random scheduling, queuing delays depend significantly on the degree of uniformity of the offered demand patterns, with uniform demand matrices representing a provably worst-case scenario. These results are independent of whether RLB employs priority mechanisms between traffic from step one over step two. A comparison with multi-hop shortest-path routing reveals that RLB eliminates the occurrence of demand-specific hot spots in the network.

Bandwidth-sharing networks as considered by Massoulie & Roberts provide a natural modeling framework for describing the dynamic flow-level interaction among elastic data transfers. Although valuable stability results have been obtained, crucial performance metrics such as flow-level delays and throughputs in these models have remained intractable in all but a few special cases. In particular, it is not well understood to what extent flow-level delays and throughputs achieved by standard bandwidth-sharing mechanisms such as alpha-fair strategies leave potential room for improvement. In order to gain a better understanding of the latter issue, we set out to determine the scheduling policies that minimize the mean delay in some simple linear bandwidth-sharing networks. While admittedly simple, linear networks provide a useful model for flows that traverse several links and experience bandwidth contention from independent cross-traffic. Even for linear topologies it is rarely possible however to explicitly identify optimal policies except in a few limited cases with exponentially distributed flow sizes. Rather than aiming for strictly optimal policies, we therefore focus on a class of relatively simple priority-type strategies that only separate large flows from small ones. To benchmark the performance of these strategies, we compare them with proportional fair as the prototypical alpha-fair policy, and establish that the mean delay may be reduced by an arbitrarily large factor when the load is sufficiently high. In addition, we show the above strategies to be asymptotically optimal for flow size distributions with bounded support. Numerical experiments reveal that even at fairly moderate load values the performance gains can be significant.

We study the problem of efficiently scheduling users in a Gaussian broadcast channel withMtransmit antennas andKindependent receivers, each with a single antenna. We first focus on a scenario with two transmit antennas and statistically identical users, and analyze the gap between the full sum capacity and the rate that can be achieved by transmitting to a suitably selected pair of users. In particular, we consider a scheme that picks the user with the largest channel gain, and selects a second user from the nextL- 1 strongest ones to form the best pair, taking channel orientations into account as well. We prove that the expected rate gap converges to 1/(L- 1) nats/symbol when the total number of usersKtends to infinity. AllowingLto increase withK, it may be deduced that transmitting to a properly chosen pair of users is asymptotically optimal, while considerably reducing the feedback overhead and scheduling complexity. Next, we tackle the problem of maximizing aweightedsum rate in a scenario with heterogeneous user characteristics. We establish a novel upper bound for the weighted sum capacity, which we then use to show that the maximum expected weighted sum rate can be asymptotically achieved by transmitting to a suitably selected subset of at mostMCusers, whereCdenotes the number of distinct user classes. Numerical experiments indicate that the asymptotic results are remarkably accurate and that the proposed schemes operate close to absolute performance bounds, even for a moderate number of users.

Abstract—The performance of wireless data systems has been thoroughly studied in the context of a single base station. In the present paper we analyze networks with several interacting base stations, and specifically examine the capacity impact of intraand inter-cell mobility. We consider a dynamic setting where users come and go over time as governed by random finite-size data transfers, and explicitly allow for users to roam around over the course of their service. We show that mobility tends to increase the capacity, not only in case of globally optimal scheduling, but also when each of the base stations operates according to a fair sharing policy. The latter approach offers the advantages that it avoids complex centralized control, and grants each user a fair share of the resources, preventing the potential starvation that may occur under a globally optimal strategy. An important implication is that a simple, conservative capacity estimate is obtained by ‘ignoring’ mobility, and assuming that users remain stationary for the duration of their service. We further demonstrate that the capacity region for globally optimal scheduling is in general strictly larger than the stability region for a fair sharing discipline. However, if the users distribute themselves so as to maximize their individual throughputs, thus enabling some implicit coordination, then a fair sharing policy is in fact guaranteed to achieve stability whenever a globally optimal strategy is able to do so.

Channel-aware scheduling strategies provide an effective mechanism for improving the throughput performance in wireless data networks by exploiting channel fluctuations. The performance of channel-aware scheduling algorithms has mainly been examined at the packet level for a static user population, often assuming infinite backlogs. Recently, some studies have also explored the flow-level performance in a scenario with user dynamics governed by the arrival and completion of random service demands over time. Although in certain cases the performance may be evaluated by means of a Processor-Sharing model, in general the flow-level behavior has remained largely intractable, even basic stability properties. In the present paper we derive simple necessary stability conditions, and show that these are also sufficient for a wide class of utility-based scheduling policies. This contrasts with the fact that the latter class of strategies generally fail to provide maximum-throughput guarantees at the packet level.

The capacity region of the Gaussian multi-antenna broadcast channel was characterized recently in [19]. It was shown that a scheme based on Dirty Paper Coding [2] achieves the full capacity region when the transmitter has perfect channel state information. However, this scheme potentially involves considerable amounts of feedback and complex algorithms for coding and user selection. This has led to a quest for practical transmission schemes and ways to reduce the amount of channel state information required. In particular, it has been shown that when the total number of users is large, the sum capacity can be closely approached by transmitting to a small subset of near-orthogonal users. In order to further quantify the latter observation, we study a Gaussian broadcast channel with two transmit antennas and K statistically identical, independent users each with a single receive antenna. We obtain an exact asymptotic characterization of the gap between the full sum capacity and the rate that can be achieved by transmitting to a suitably selected pair of users. Specifically, we consider various simple schemes for user-pair selection that take into account the channel norms as well as the relative orientation of the channel vectors. We conclude that a scheme that picks the strongest user and selects a second user to form the best pair, is asymptotically optimal, while also being attractive in terms of feedback and operational complexity.

We consider a multi-class queueing system operating under the discriminatory processor-sharing (DPS) discipline. The DPS discipline provides a natural approach for modeling the flow-level performance of differentiated bandwidth-sharing mechanisms. Motivated by the extreme diversity in flow sizes observed in the Internet, we examine the system performance in an asymptotic regime where the flow dynamics of the various classes occur on separate time scales. Specifically, from the perspective of a given class, the arrival and service completions of some of the competing classes (called mice) evolve on an extremely fast time scale. In contrast, the flow dynamics of the remaining classes (referred to as elephants) occur on a comparatively slow time scale. Assuming a strict separation of time scales, we obtain simple explicit expressions for various performance measures of interest, such as the distribution of the numbers of flows, mean delays, and flow throughputs. In particular, the latter performance measures are insensitive, in the sense that they only depend on the service requirement distributions through their first moments. Numerical experiments show that the limiting results provide remarkably accurate approximations in certain cases.

Channel-aware scheduling strategies, such as the Proportional Fair algorithm for the CDMA 1xEV-DO system, provide an effective mechanism for improving throughput performance in wireless data networks by exploiting channel fluctuations. The performance of channel-aware scheduling algorithms has mostly been explored at the packet level for a static user population, often assuming infinite backlogs. In the present paper, we focus on the performance at the flow level in a dynamic setting with random finite-size service demands. We show that in certain cases the user-level performance may be evaluated by means of a multiclass Processor-Sharing model where the total service rate varies with the total number of users. The latter model provides explicit formulas for the distribution of the number of active users of the various classes, the mean response times, the blocking probabilities, and the throughput. In addition we show that, in the presence of channel variations, greedy, myopic strategies which maximize throughput in a static scenario, may result in sub-optimal throughput performance for a dynamic user configuration and cause potential instability effects.

The potential for exploiting rate variations to increase the capacity of wireless systems by opportunistic scheduling has been extensively studied at packet level. In the present paper, we examine how slower, mobility-induced rate variations impact performance at flow level, accounting for the random number of flows sharing the transmission resource. We identify two limit regimes, termed fluid and quasistationary, where the rate variations occur on an infinitely fast and an infinitely slow time scale, respectively. Using stochastic comparison techniques, we show that these limit regimes provide simple performance bounds that only depend on easily calculated load factors. Additionally, we prove that for a broad class of fading processes, performance varies monotically with the speed of the rate variations. These results are illustrated through numerical experiments, showing that the fluid and quasistationary bounds are remarkably tight in certain usual cases

The performance of wireless data systems has been extensively studied in the context of a single base station. In the present paper we investigate the flow-level performance in networks with multiple base stations. We specifically examine the complex, dynamic interaction of the number of active flows in the various cells introduced by the strong impact of interference between neighboring base stations. For the downlink data transmissions that we consider, lower service rates caused by increased interference from neighboring base stations result in longer delays and thus a higher number of active flows. This in turn results in a longer duration of interference on surrounding base stations, causing a strong correlation between the activity states of the base stations. Such a system can be modelled as a network of multi-class processor-sharing queues, where the service rates for the various classes at each queue vary over time as governed by the activity state of the other queues. The complex interaction between the various queues renders an exact analysis intractable in general. A simplified network with only one class per queue reduces to a coupled-processors model, for which there are few results, even in the case of two queues. We thus derive bounds and approximations for key performance metrics like the number of active flows, transfer delays, and flow throughputs in the various cells. Importantly, these bounds and approximations are insensitive, yielding simple expressions, that render the detailed statistical characteristics of the system largely irrelevant.

Channel-aware scheduling strategies, such as the Proportional Fair algorithm for the CDMA 1xEV-DO system, provide an effective mechanism for improving throughput performance in wireless data networks by exploiting channel fluctuations. The performance of channel-aware scheduling algorithms has mostly been explored at the packet level for a static user population, often assuming infinite backlogs. In the present paper, we focus on the performance at the flow level in a dynamic setting with random finite-size service demands. We show that in certain cases the user-level performance may be evaluated by means of a multiclass Processor-Sharing model where the total service rate varies with the total number of users. The latter model provides explicit formulas for the distribution of the number of active users of the various classes, the mean response times, the blocking probabilities, and the mean throughput. In addition we show that, in the presence of channel variations, greedy, myopic strategies which maximize throughput in a static scenario, may result in sub-optimal throughput performance for a dynamic user configuration and cause potential instability effects.

The Medium Access Control (MAC) scheme proposed by DAVIC/DVB, IEEE 802.14 and DOCSIS for the upstream channel of Hybrid Fiber Coaxial (HFC) access networks is based on a mixable contention-based/contention-less time slot assignment. Contention-less slots are assigned by the head end to end stations according to a reservation scheme. Contention-based slots are randomly accessed by active terminals without any preliminary allocation, so that collisions may occur. To resolve contention, the contention tree algorithm has been widely accepted by the DVB/DAVIC, IEEE 802.14 and DOCSIS standards for MAC because of higher throughput and lower access delay. In this paper we propose a novel contention resolution mechanism and compare its performance with that of existing procedures. The proposed procedure is termed as static arrival slot mechanism. In this mechanism, one slot in each frame is exclusively reserved for new arrivals that wish to access the channel using contention resolution, and at least one slot is reserved for resolving their contention if there was one in the arrival slot. The performance of the proposed mechanism is evaluated through analysis and simulation. The results show that the proposed mechanism outperforms existing contention resolution procedures under heavy traffic.

We consider a queue fed by a mixture of light-tailed and heavy-tailed traffic. The two traffic flows are served in accordance with the generalized processor sharing (GPS) discipline. GPS-based scheduling algorithms, such as weighted fair queueing, have emerged as an important mechanism for achieving service differentiation in integrated networks. We derive the asymptotic workload behavior of the light-tailed traffic flow under the assumption that its GPS weight is larger than its traffic intensity. The GPS mechanism ensures that the workload is bounded above by that in an isolated system with the light-tailed flow served in isolation at a constant rate equal to its GPS weight. We show that the workload distribution is in fact asymptotically equivalent to that in the isolated system, multiplied with a certain pre-factor, which accounts for the interaction with the heavy-tailed flow. Specifically, the pre-factor represents the probability that the heavy-tailed flow is backlogged long enough for the light-tailed flow to reach overflow. The results provide crucial qualitative insight in the typical overflow scenario.

We consider a queue fed by a mixture of light-tailed and heavy-tailed traffic. The two traffic classes are served in accordance with the generalized processor sharing (GPS) discipline. GPS-based scheduling algorithms, such as weighted fair queueing (WFQ), have emerged as an important mechanism for achieving service differentiation in integrated networks. We derive the asymptotic workload behavior of the light-tailed class for the situation where its GPS weight is larger than its traffic intensity. The GPS mechanism ensures that the workload is bounded above by that in an isolated system with the light-tailed class served in isolation at a constant rate equal to its GPS weight. We show that the workload distribution is in fact asymptotically equivalent to that in the isolated system, multiplied with a certain pre-factor, which accounts for the interaction with the heavy-tailed class. Specifically, the pre-factor represents the probability that the heavy-tailed class is backlogged long enough for the light-tailed class to reach overflow. The results provide crucial qualitative insight in the typical overflow scenario.

The relative delay tolerance of data applications, together with the bursty traffic characteristics, opens up the possibility for scheduling transmissions so as to optimize throughput. A particularly attractive approach, in fading environments, is to exploit the variations in the channel conditions, and transmit to the user with the currently 'best' channel. We show that the 'best' user may be identified as the maximum-rate user when the feasible rates are weighed with some appropriately determined coefficients. Interpreting the coefficients as shadow prices, or reward values, the optimal strategy may thus be viewed as a revenue-based policy. Calculating the optimal revenue vector directly is a formidable task, requiring detailed information on the channel statistics. Instead, we present adaptive algorithms for determining the optimal revenue vector on-line in an iterative fashion, without the need for explicit knowledge of the channel behavior. Starting from an arbitrary initial vector, the algorithms iteratively adjust the reward values to compensate for observed deviations from the target throughput ratios. The algorithms are validated through extensive numerical experiments. Besides verifying long-run convergence, we also examine the transient performance, in particular the rate of convergence to the optimal revenue vector. The results show that the target throughput ratios are tightly maintained, and that the algorithms are well able to track changes in the channel conditions or throughput targets.

We consider networks where traffic is served according to the generalised processor sharing (GPS) principle. GPS-based scheduling algorithms are considered important for providing differentiated quality of service in integrated-services networks. We are interested in the workload of a particular flow i at the bottleneck node on its path. Flow i is assumed to have long-tailed traffic characteristics. We distinguish between two traffic scenarios, (i) flow i generates instantaneous traffic bursts and (ii) flow i generates traffic according to an on/off process. In addition, we consider two configurations of feedforward networks. First we focus on the situation where other flows join the path of flow i. Then we extend the model by adding flows which may branch off at any node, with cross traffic as a special case. We prove that under certain conditions the tail behaviour of the workload distribution of flow i is equivalent to that in a two-node tandem network where flow i is served in isolation at constant rates. These rates only depend on the traffic characteristics of the other flows through their average rates. This means that the results do not rely on any specific assumptions regarding the traffic processes of the other flows. In particular, flow i is not affected by excessive activity of flows with 'heavier-tailed' traffic characteristics. This confirms that GPS has the potential to protect individual flows against extreme behaviour of other flows, while obtaining substantial multiplexing gains.

We consider a fluid queue fed by multiple on-off flows with heavy-tailed (regularly varying) on-periods. Under fairly mild assumptions, we prove that the workload distribution is asymptotically equivalent to that in a reduced system. The reduced system consists of a dominant subset of the flows, with the original service rate subtracted by the mean rate of the other flows. We describe how a dominant set may be determined from a simple knapsack formulation. We exploit a powerful intuitive argument to obtain the exact asymptotics for the reduced system. Combined with the reduced-load equivalence, the results for the reduced system provide an asymptotic characterization of the buffer behavior.

Consider two M/G/1 queues that are coupled in the following way. Whenever both queues are non-empty, each server serves its own queue at unit speed. However, if server 2 has no work in its own queue, then it assists server 1, resulting in an increased service speed r/sub 1//sup *//spl ges/1 in the first queue. This kind of coupling is related to generalized processor sharing. We assume that the service request distributions at both queues are regularly varying at infinity of index -v/sub 1/ and -v/sub 2/, namely, they are heavy-tailed. Under this assumption, we present a detailed analysis of the tail behaviour of the workload distribution at each queue. If the guaranteed unit speed of server 1 is already sufficient to handle its offered traffic, then the workload distribution at the first queue is shown to be regularly varying at infinity of index 1-v/sub 1/. But if it is not sufficient, then the workload distribution at the first queue is shown to be regularly varying at infinity of index 1-min(v/sub 1/,v/sub 2/). In particular, traffic at server 1 is then no longer protected from worse-behaved (heavier-tailed) traffic at server 2.

We analyze the asymptotic behavior of long-tailed traffic sources under the generalized processor sharing (GPS) discipline. GPS-based scheduling algorithms, such as weighted fair queueing, have emerged as an important mechanism for achieving differentiated quality-of-service in integrated-services networks. Under certain conditions, we prove that in an asymptotic sense an individual source with long-tailed traffic characteristics is effectively served at a constant rate, which may be interpreted as the maximum feasible average rate for that source to be stable. Thus, asymptotically, the source is only affected by the traffic characteristics of the other sources through their average rate. In particular, the source is essentially immune from excessive activity of sources with 'heavier'-tailed traffic characteristics. This suggests that GPS-based scheduling algorithms provide an effective mechanism for extracting high multiplexing gains, while protecting individual connections.

We derive bounds for the performance of dynamic channel assignment (DCA) schemes which strengthen the existing Erlang bound. The construction of the bounds is based on a reward paradigm as an intuitively appealing way of characterizing the achievable carried traffic region. In one-dimensional networks, our bounds closely approach the performance of maximum packing (MP), which is an idealized DCA scheme. This suggests not only that the bounds are extremely tight, but also that no DCA scheme, however sophisticated, can be expected to outperform MP in any significant manner, if at all. Our bounds extend to scenarios with varying re-use which may arise in the case of dynamic re-use partitioning or measurement-based DCA schemes. In these cases, the bounds slightly diverge from the performance of MP, which inflicts higher blocking on outer calls than inner calls, but not to the extent required to maximize carried traffic. This reflects the trade-off that arises in the case of varying re-use between efficiency and fairness. Asymptotic analysis confirms that schemes which minimize blocking intrinsically favor inner calls over outer calls, whereas schemes which do not discriminate among calls inevitably produce higher network-average blocking.

We describe the simulation of a new dynamic channel assignment algorithm in FDMA/TDMA wireless networks. The algorithm relies on periodic interference measurements by each of the base stations on the inactive frequencies, so as to identify appropriate candidate channels. The adaptive nature provides automatic configuration at the time of system initialization and adaptation to system expansion and traffic patterns with spatial or temporal variations. By eliminating the manual frequency planning process inherent to today's fixed channel assignment procedures, the self-organizing capability guarantees ease of operation for service providers, while increasing both capacity and voice quality. Our simulation experiments demonstrate stability of the algorithm and confirm its self-organizing capability. They also indicate a significant decrease of call blocking and dropping and other quality-of-service improvements.

We consider virtual partitioning (VP), which is a scheme for sharing a resource among several traffic classes in an efficient, fair, and robust manner. In the preliminary design stage, each traffic class is allocated a nominal capacity, which is based on expected offered traffic and required quality of service. During operations, if the current capacity usage by a class exceeds its nominal allocation, then it is declared to be in "overload," and a state-dependent trunk reservation mechanism gives it lower priority in the admission of new calls. We develop efficient computational algorithms for the case of heterogeneous traffic, and perform extensive numerical experiments to demonstrate the accuracy of the various approximations. The performance of VP is examined and compared to that of complete sharing and complete partitioning. Particular weight is placed on robustness, meaning that traffic classes with arrival rates conforming to the design continue to receive the required quality of service, despite the presence of misbehaving classes with excessive arrival rates. We adopt a reward-penalty paradigm as a combined measure for efficiency and fairness, and show that not only is the revenue generated by VP extremely close to the maximum achievable value, but that the structural form of the optimal policy also closely resembles that of VP. The numerical results confirm that the scheme is efficient, fair, and very robust.

The model under consideration consists of n customer types attended by m parallel non-identical servers. Customers are allocated to the servers in a probabilistic manner; upon arrival customers are sent to one of the servers according to an m × n matrix of routing probabilities. We consider the problem of finding an allocation that minimizes a weighted sum of the mean waiting times. We expose the structure of an optimal allocation and describe for some special cases in detail how the structure may be exploited in actually determining an optimal allocation.

Time limits are the major mechanisms used for controlling a large variety of multistation single-medium computer-communication systems like the FDDI network and the IEEE 802.4 Token Bus. The proper use of these mechanisms is still not understood and rules for efficient system operation are not available. The authors' objective is the derivation of such rules. They use a cyclic polling model with different service limits (k-limited service) at the different queues, thus emulating time limits. They are interested in determining these k-limit values so as to minimize the mean waiting cost of messages in the system. A simple approximative approach is proposed for two major problems: one in which a limit is set on the token rotation time and one in which no limits are imposed. The approach is tested for a variety of cases and is shown to be very effective.>

This paper analyses a variant of the ikl/G/l queue in which the service times of arriving customers depend on the length of the interval between their arrival and the previous arrival.The dependence structure corresponds to the case of customers arriving according to an ordinary Poisson arrival process, and customer collectors being sent out according to a Poisson process to collect the customers and to bring them to the service facility.In this case collected numbers of customers, and hence total collected service requests, are positively correlated with the corresponding collect intervals.Viewing a batch of collected customers as one (super) customer gives rise to an itf/G/l queue with a positive correlation between service times of such customers and their interarrival times.Both for individual customers and for batches of collected customers we derive the transforms of the sojourn time and waiting time distributions.We also compare our results with those for the ordinary M/G/l queue without dependence.