Join-the-shortest queue (JSQ) and its variants have often been used in solving load balancing problems. The aim of such policies is to minimize the average system occupation, e.g., the customer's system time. In this paper, we extend the load balancing setting to include constraints that may be imposed, e.g., due to the communication network. First, we cast the problem in the framework of constrained MDPs: this permits us to address both action-dependent constraints, such as, e.g, bandwidth limitation, and state-dependent constraints, such as, e.g., minimum queue utilization. Hence, unlike the state-of-the-art approaches in load balancing, we derive new policies that satisfy the constraints while minimizing system occupancy. Extensive numerical simulations have evaluated their performance under various system settings.

The Kelly or proportional allocation mechanism is a simple and efficient auction-based decentralized resource allocation scheme that distributes an infinitely divisible resource proportionally to the agents' bids. When agents are aware of the allocation mechanism, their interactions form a game. The properties of its Nash equilibria are well understood under the simplifying assumption of unbounded budgets. In this paper, we analyze the game in a more realistic budget-constrained setting, motivated by its optimality in terms of the liquid price of anarchy (LPoA). Specifically, we establish a sufficient condition for the uniqueness of the Nash equilibrium and design a distributed sequential learning procedure that provably converges to the equilibrium. In particular, our sufficient condition holds when the payoff functions of the agents are of the proportional fair type in the allocated fraction. Finally, extensive numerical experiments shed light on the interplay between the heterogeneity of the payoff functions and the agents' budgets.

In this paper, the worst-case probability measure over the data is introduced as a tool for characterizing the generalization capabilities of machine learning algorithms. More specifically, the worst-case probability measure is a Gibbs probability measure and the unique solution to the maximization of the expected loss under a relative entropy constraint with respect to a reference probability measure. Fundamental generalization metrics, such as the sensitivity of the expected loss, the sensitivity of the empirical risk, and the generalization gap are shown to have closed-form expressions involving the worst-case data-generating probability measure. Existing results for the Gibbs algorithm, such as characterizing the generalization gap as a sum of mutual information and lautum information, up to a constant factor, are recovered. A novel parallel is established between the worst-case data-generating probability measure and the Gibbs algorithm. Specifically, the Gibbs probability measure is identified as a fundamental commonality of the model space and the data space for machine learning algorithms.

Modern portable devices can execute increasingly sophisticated AI models on sensed data. The complexity of such processing tasks is data-dependent and has relevant energy cost. This work develops an Age of Information Markovian model for a system where multiple battery-operated devices perform data processing and energy harvesting in parallel. Part of their computational burden is offloaded to an edge server which polls devices at given rate. The structural properties of an optimal policy for a single device-server system are derived. They permit to define a new model-free reinforcement learning method specialized for monotone policies, namely Ordered Q-Learning, providing a fast procedure to learn the optimal policy. The method is oblivious to the devices’ battery capacities, the cost and the value of data batch processing and to the dynamics of the energy harvesting process. Finally, the polling strategy of the server is optimized by combining this policy improvement technique with stochastic approximation methods. Extensive numerical results provide insight into the system properties and demonstrate that the proposed learning algorithms outperform existing baselines.

The deployment of RISs in future 6G networks is expected to substantially improve mobile network coverage. This paper introduces a new cross-layer low-complexity scheme for the online optimization of RIS-assisted communication systems. It jointly combines BS and RIS configuration and fair UEs’ scheduling which is critical for high-performance deployments. A RIS beam synthesis method is especially proposed for RIS configuration. The proposed solution embeds two nested control loops: i) a fast control loop working at the OFDMA slot scale and consisting in a standard UEs proportional fair scheduler, and ii) a slow control loop operating at the OFDMA frame scale which adapts the RIS’ configuration to the UEs’ spatial distribution and maximizes the UEs’ aggregated performance. The slow control loop is based on an online stochastic approximation algorithm whose convergence to the optimal restpoint is proved. In a reference scenario, the proposed scheduler achieves a gain of 47% in mean spectral efficiency for NLOS UEs over a baseline scheme.

Modern portable devices can execute increasingly sophisticated AI models on sensed data. The complexity of such processing tasks is data-dependent and has relevant energy cost. This work develops an Age of Information markovian model for a system where multiple battery-operated devices perform data processing and energy harvesting in parallel. Part of their computational burden is offloaded to an edge server which polls devices at given rate. The structural properties of an optimal policy for a single device-server system are derived. They permit to define a new model-free reinforcement learning method specialized for monotone policies, namely Ordered Q-Learning, providing a fast procedure to learn the optimal policy. The method is oblivious to the devices' battery capacities, the cost and the value of data batch processing and to the dynamics of the energy harvesting process. Finally, the polling strategy of the server is optimized by combining this policy improvement technique with stochastic approximation methods. Extensive numerical results provide insight into the system properties and demonstrate that the proposed learning algorithms outperform existing baselines.

International audience

This paper characterizes an achievable information-energy region of simultaneous information and energy transmission over an additive white Gaussian noise channel. This analysis is performed in the finite block-length regime with finite constellations. More specifically, a method for constructing a family of codes is proposed and the set of achievable tuples of information rate, energy rate, decoding error probability (DEP) and energy outage probability (EOP) is characterized. Using existing converse results, it is shown that the construction is information rate, energy rate, and EOP optimal. The achieved DEP is, however, sub-optimal.

In this paper, the fundamental limits on the rates at which information and energy can be simultaneously transmitted over an additive white Gaussian noise channel are studied under the following assumptions: (a) the channel is memoryless; (b) the number of channel input symbols (constellation size) and block length are finite; and (c) the decoding error probability (DEP) and the energy outage probability (EOP) are bounded away from zero. In particular, it is shown that the limits on the maximum information and energy transmission rates; and the minimum DEP and EOP, are essentially set by the type induced by the code used to perform the transmission. That is, the empirical frequency with which each channel input symbol appears in the codewords. Using this observation, guidelines for optimal constellation design for simultaneous energy and information transmission are presented.

We study the symmetric version of the load balancing game introduced by H. Kameda. We consider a non-splittable atomic game with lossy links. Thus costs are not additive and flow is not conserved (total flow entering a link is greater than the flow leaving it). We show that there is no unique equilibrium in the game. We identify several symmetric equilibria and show how the number of equilibria depends on the problem's parameters. We compute the globally optimal solution and compare its performance to the equilibrium. We finally identify the Kameda paradox which was introduced initially in networks without losses.

The demand for Internet services that require frequent updates through small messages, also known as microblogging, has tremendously grown in the past few years. Although the use of such applications by domestic users is usually free, their access from mobile devices is subject to fees and consumes energy from limited batteries. If a user activates his mobile device and is in the range of a publisher, an update is received at the expense of monetary and energy costs. Thus, users face a tradeoff between such costs and their messages aging. The goal of this paper is to show how to cope with such a tradeoff, by devising aging control policies. An aging control policy consists of deciding, based on the utility of the owned content, whether to activate the mobile device, and if so, which technology to use (WiFi or cellular). We present a model that yields the optimal aging control policy. Our model is based on a Markov Decision Process (MDP) in which states correspond to content ages. Using our model, we show the existence of an optimal strategy in the class of threshold strategies, wherein users activate their mobile devices if the age of their poadcasts surpasses a given threshold and remain inactive otherwise. The accuracy of our model is validated against traces from the UMass DieselNet bus network.

We study in this paper optimal control strategy for Advanced Sleep Modes (ASM) in 5G networks. ASM correspond to different levels of sleep modes ranging from deactivation of some components of the base station for several micro-seconds to switching off of almost all of them for one second or more. ASMs are made possible in 5G networks thanks to the definition of so-called lean carrier radio access which allows for configurable signaling periodicities. We model such a system using Markov Decision Processes (MDP) and find optimal sleep policy in terms of a trade-off between saved power consumption versus additional incurred delay for user traffic which has to wait for the network components to be woken-up and serve it. Eventually, for the system not to oscillate between sleep levels, we add a switching component in the cost function and show its impact on the energy reduction versus delay trade-off.

In this paper, we develop an analytical framework to compute the Quality-of-Experience (QoE) metrics of video streaming in wireless networks. Our framework takes into account the system dynamics that arises due to the arrival and departure of flows. We also consider the possibility of users abandoning the system on account of poor QoE. Considering the coexistence of multiple services such as video streaming and elastic flows, we use a Markov chain based analysis to compute the user QoE metrics: probability of starvation, prefetching delay, average video quality and bitrate switching. Our simulation results validate the accuracy of our model and describe the impact of scheduler at eNB on the QoE metrics.

Dynamic Adaptive Streaming over HTTP (DASH) has become the standard choice for live events and on-demand video services. In fact, by performing bitrate adaptation at the client side, DASH operates to deliver the highest possible Quality of Experience (QoE) under given network conditions. In cellular networks, in particular, video streaming services are affected by mobility and cell load variation. In this context, DASH video clients continually adapt the streaming quality to cope with channel variability. However, since they operate in a greedy manner, adaptive video clients can overload cellular network resources, degrading the QoE of other users and suffer persistent bitrate oscillations. In this paper, we tackle this problem using a new eNB scheduler, named Shadow-Enforcer, which ensures minimal number of quality switches as well as efficient and fair utilization of network resources. Our scheduler works well under dynamic scenarios and mobility, and requires minimal information, i.e., just the set of video bitrates supported by DASH video clients. It consists of the cascade of a virtual scheduler, Shadow, and the actual scheduler, Enforcer, piloted by the virtual one. Extensive simulations demonstrate the efficiency, fairness and the smooth response to channel variations of the proposed solution.

When the base station density is sparse, users are often out of the coverage area of the cellular networks. In such scenarios, the users can rely on fellow users (willing to relay) to deliver delay tolerant information to a base station. Further, the users (and relays) can observe independent environments, during their traverse, if they are moving at considerable speeds. This provides them an opportunity to (independent) search for relays and or base stations at regular intervals of time. However, the user should beacon (transmit short pulses and wait for response), when it desires to be detected by the available relays in its neighbourhood. We derive the performance of such a system, accounting for the power utilized for beaconing, and obtain the beaconing policies that maximize the success (user/any previously contacted relay comes in contact with one of the base stations) probability of message delivery. The base stations and relays (at any given instance of time) are randomly distributed according to a Poisson Point process. We formulate the problem as a Markov Decision Process (MDP) to derive optimal policies depending on the system state (closed-loop). We show that the value function satisfies certain monotonicity properties and the optimal policy exhibits a certain switch-off property. We obtain an approximate solution for the continuous control and an exact solution for the ON-OFF (two action) control. Our investigations show that the closed-loop ON-OFF policies perform (almost) as good as the closed-loop continuous policies for all practically viable test cases. We further investigate open-loop policies for ON-OFF control, the policies that can be used when the system state is not known.

In this paper, we consider the problem of location-dependent opportunistic bandwidth sharing between static and mobile (i.e., moving) downlink users in a cellular network. Each cell of the network has some fixed number of static users. Mobile users enter the cell, move inside the cell for some time, and then leave the cell. In order to provide higher data rate to the highly mobile users whose fast fading channel variation is difficult to track, we propose location dependent bandwidth sharing between the two classes of static and mobile users; the idea is to provide higher bandwidth to the mobile users at favourable locations, and provide higher bandwidth to the static users in other times. Our approach is agnostic to the way the bandwidth is further shared within the same class of users; it can be combined with any particular bandwidth allocation policy employed for one of these two classes of users. We formulate the problem as a long run average reward Markov decision process (MDP) where the per-step reward is a linear combination of instantaneous data volumes received by static and mobile users, and find the optimal policy. The optimal policy is binary in nature; it allocates the entire bandwidth either to the static users or to the mobile users at any given time. The reward structure of this MDP is not known in general, and it may change with time. To alleviate these issues, we propose a learning algorithm based on single timescale stochastic approximation. Also, noting that the MDP problem can be used to maximize the long run average data rate for mobile users subject to a constraint on the long run average data rate of static users, we provide a learning algorithm based on multi-timescale stochastic approximation. We prove asymptotic convergence of the bandwidth sharing policies under these learning algorithms to the optimal policy. The results are extended to address the issue of fair bandwidth sharing between the two classes of static and mobile users, where the notion of fairness is motivated by the popular notion of α-fairness in the literature. Numerical results exhibit significant performance improvement by our scheme, as well as fast convergence, and also demonstrate the trade-off between performance gain and fairness requirement.

Video streaming over cellular network has become extremely popular in 4G and will be an integral part of future cellular networks. While most modern-day video clients continually adapt quality of video streams, they neither coordinate with network elements nor among each other. Consequently, a streaming client may quickly overload the cellular network, leading to poor Quality of Experience (QoE) for users in the network. Motivated by this problem, we present D-VIEWS - a scheduling paradigm that assures video bitrate stability of adaptive video streams while ensuring better system utilization. D-VIEWS only needs to be aware of the set of video bitrates and requires no changes to streaming clients and other network functions. Through simulations, we also study the performance of proportional fairness scheduler and D-VIEWS in the presence of user arrival and departure events.

The price-anticipating Kelly mechanism (PAKM) is one of the most extensively used strategies to allocate divisible resources for strategic users in communication networks and computing systems. The users are deemed as selfish and also benign, each of which maximizes his individual utility of the allocated resources minus his payment to the network operator. However, in many applications a user can use his payment to reduce the utilities of his opponents, thus playing a misbehaving role. It remains mysterious to what extent the misbehaving user can damage or influence the performance of benign users and the network operator. In this work, we formulate a non-cooperative game consisting of a finite amount of benign users and one misbehaving user. The maliciousness of this misbehaving user is captured by his willingness to pay to trade for unit degradation in the utilities of benign users. The network operator allocates resources to all the users via the price-anticipating Kelly mechanism. We present six important performance metrics with regard to the total utility and the total net utility of benign users, and the revenue of network operator under three different scenarios: with and without the misbehaving user, and the maximum. We quantify the robustness of PAKM against the misbehaving actions by deriving the upper and lower bounds of these metrics. With new approaches, all the theoretical bounds are applicable to an arbitrary population of benign users. Our study reveals two important insights: 1) the performance bounds are very sensitive to the misbehaving user's willingness to pay at certain ranges and 2) the network operator acquires more revenues in the presence of the misbehaving user which might disincentivize his countermeasures against the misbehaving actions.

In small cell networks, the high mobility of users results in frequent handoff and thus severely restricts the data rate for mobile users (MUs). To alleviate this problem, we propose use of the heterogeneous two-tier network structure where static users (SUs) are served by both macro and micro base stations (BSs), whereas the mobile (i.e., moving) users are served only by the macro BSs having larger cells; the idea is to prevent frequent data outage for MUs due to handoff. We use the classical two-tier Poisson network model with different transmit powers, and assume the independent Poisson process of SUs and doubly stochastic Poisson process of MUs moving at a constant speed along infinite straight lines generated by a Poisson line process. Using tools from stochastic geometry, we calculate the average downlink data rate of the typical static and mobile (i.e., moving) users, and the latter accounted for handoff outage periods. We consider also the average throughput of these two types of users defined as their average data rates divided by the mean total number of users co-served by the same base station. We find that if the density of a homogeneous network and/or the speed of MUs is high, it is advantageous to let the MUs connect only to some optimal fraction of BSs (i.e., an optimal random subset of BSs) to reduce the frequency of handoffs during which the connection is not assured. If a heterogeneous structure of the network is allowed, one can further jointly optimize the mean throughput of MUs and SUs. This joint optimization is done by appropriately tuning the powers of micro and macro BSs subject to some aggregate power constraint ensuring unchanged mean data rates of SUs via the network equivalence property.

Facebook News Feed personalization algorithm has a significant impact, on a daily basis, on the lifestyle, mood and opinion of millions of Internet users. Nonetheless, the behavior of such algorithms usually lacks transparency, motivating measurements, modeling and analysis in order to understand and improve its properties. In this paper, we propose a reproducible methodology encompassing measurements and an analytical model to capture the visibility of publishers over a News Feed. First, measurements are used to parameterize and to validate the expressive power of the proposed model. Then, we conduct a what-if analysis to assess the visibility bias incurred by the users against a baseline derived from the model. Our results indicate that a significant bias exists and it is more prominent at the top position of the News Feed. In addition, we found that the bias is non-negligible even for users that are deliberately set as neutral with respect to their political views.

In this paper, we consider a “generalized” fractional program in order to solve a popularity optimization problem in which a source of contents controls the topics of her contents and the rate with which posts are sent to a time line. The objective of the source is to maximize its overall popularity in an Online Social Network (OSN). We propose an efficient algorithm that converges to the optimal solution of the Popularity maximization problem.

To optimize routing of flows in datacenters, SDN controllers receive a packet-in message whenever a new flow appears in the network. Unfortunately, flow arrival rates can peak to millions per second, impairing the ability of controllers to treat them on time. Flow scheduling copes with such sheer numbers by segmenting the traffic between elephant and mice flows and by treating elephant flows in priority, as they disrupt short lived TCP flows and create bottlenecks. We propose a learning algorithm called SOFIA and able to perform optimal online flow segmentation. Our solution, based on stochastic approximation techniques, is implemented at the switch level and updated by the controller, with minimal signaling over the control channel. SOFIA is blind, i.e., it is oblivious to the flow size distribution. It is also adaptive, since it can track traffic variations over time. We prove its convergence properties and its message complexity. Moreover, we specialize our solution to be robust to traffic classification errors. Extensive numerical experiments characterize the performance of our approach in vitro. Finally, results of the implementation in a real OpenFlow controller demonstrate the viability of SOFIA as a solution in production environments.

Advanced Sleep Modes (ASMs) correspond to a gradual deactivation of the Base Station (BS)'s components in order to reduce its Energy Consumption (EC). Different levels of Sleep Modes (SMs) can be considered according to the transition time (deactivation and activation durations) of each component. We propose in this paper a management solution for ASMs based on Q-learning approach. The target is to find the optimal durations for each SM level according to the requirements of the network operator in terms of EC reduction and delay constraints. The proposed solution shows that even with a high constraint on the delay, we can achieve high energy savings in a low load scenario (up to 57% of EC reduction) without inducing any impact on the delay. When the delay constraint is relaxed, we can achieve up to almost 90% of energy savings.

Adaptive video streaming improves users' quality of experience (QoE), while using the network efficiently. In the last few years, adaptive video streaming has seen widespread adoption and has attracted significant research effort. We study a dynamic system of random arrivals and departures for different classes of users using the adaptive streaming industry standard DASH (Dynamic Adaptive Streaming over HTTP). Using a Markov chain based analysis, we compute the user QoE metrics: probability of starvation, prefetching delay, average video quality and switching rate. We validate our model by simulations, which show a very close match. Our study of the playout buffer is based on client adaptation scheme, which makes efficient use of the network while improving users' QoE. We prove that for buffer-based variants, the average video bit-rate matches the average channel rate. Hence, we would see quality switches whenever the average channel rate does not match the available video bit rates. We give a sufficient condition for setting the playout buffer threshold to ensure that quality switches only between adjacent quality levels.

This paper presents an online algorithm for mobile user speed estimation in 3GPP Long Term Evolution (LTE)/LTE-Advanced (LTE-A) networks. The proposed method leverages on uplink (UL) sounding reference signal (SRS) power measurements performed at the base station, also known as eNodeB (eNB), and remains effective even under large sampling period. Extensive performance evaluation of the proposed algorithm is carried out using field traces from realistic environment. The online solution is proven highly efficient in terms of computational requirement, estimation delay, and accuracy. In particular, we show that the proposed algorithm can allow for the first speed estimation to be obtained after 10 seconds and with an average speed underestimation error of 14 kmph. After the first speed acquisition, subsequent speed estimations can be obtained much faster (e.g., each second) with limited implementation cost and still provide high accuracy.

We consider an opportunistic wireless communication setting, in which two nodes (referred to as forwarders) compete to choose a relay node from a set of relays, as they ephemerally become available (e.g., wake up from a sleep state). Each relay, when it becomes available (or arrives), offers a (possibly different) “reward” to each forwarder. Each forwarder's objective is to minimize a combination of the delay incurred in choosing a relay and the reward offered by the chosen relay. As an example, we develop the reward structure for the specific problem of geographical forwarding over a common set of sleep-wake cycling relays. In general, our model can be considered as a game theoretic variant of the asset selling problem studied in the operations research literature. We study two variants of the generic relay selection problem, namely, the completely observable (CO) and the partially observable (PO) cases. These cases are based on whether a forwarder (in addition to observing its reward) can also observe the reward offered to the other forwarder. Formulating both problems as a two person stochastic game, we characterize the solutions in terms of Nash equilibrium policy pairs (NEPPs). For the CO case, we provide a general structure of the NEPPs. For the PO case, we prove that there exists an NEPP within the class of threshold policy pairs. Through numerical work, for a one-hop forwarding example, we compare the cost performance of various NEPPs with a simple forwarding (SF) policy, which causes each forwarder to act as if the other is not present. We find that if the forwarders are not very close then the SF policy suffices. Insights gained from this numerical work are then used in an end-to-end simulation of geographical forwarding in a large network, in which we are concerned with delivery of packets from a tagged source to a sink, in the presence of competition from other packet flows destined for the same sink.

In multi-rate IEEE 802.11 WLANs, the traditional user association based on the strongest received signal and the well-known anomaly of the MAC protocol can lead to overloaded access points (APs), and poor or heterogeneous performance. Our goal is to propose an alternative game-theoretic approach for association. We model the joint resource allocation and user association as a matching game with complementarities and peer effects consisting of selfish players solely interested in their individual throughputs. Using recent game-theoretic results, we first show that various resource sharing protocols actually fall in the scope of the set of stability-inducing resource allocation schemes. The game makes an extensive use of the Nash bargaining and some of its related properties that allow controlling the incentives of the players. We show that the proposed mechanism can greatly improve the efficiency of 802.11 with heterogeneous nodes and reduce the negative impact of peer effects such as its MAC anomaly. The mechanism can be implemented as a virtual connectivity management layer to achieve efficient APs-user associations without modification of the MAC layer.

Optimal stochastic control of delay tolerant networks is studied in this paper. First, the structure of optimal two-hop forwarding policies is derived. In order to be implemented, such policies require knowledge of certain global system parameters such as the number of mobiles or the rate of contacts between mobiles. But, such parameters could be unknown at system design time or may even change over time. In order to address this problem, adaptive policies are designed that combine estimation and control: based on stochastic approximation techniques, such policies are proved to achieve optimal performance in spite of lack of global information. Furthermore, the paper studies interactions that may occur in the presence of several DTNs which compete for the access to a gateway node. The latter problem is formulated as a cost-coupled stochastic game and a unique Nash equilibrium is found. Such equilibrium corresponds to the system configuration in which each DTN adopts the optimal forwarding policy determined for the single network problem.

As the demand for higher data rates is growing exponentially, homogeneous cellular networks have been facing limitations when handling data traffic. These limitations are related to the available spectrum and the capacity of the network. Heterogeneous networks (HetNets), composed of macro cells (MCs) and small cells (SCs), are seen as the key solution to improve spectral efficiency per unit area and to eliminate coverage holes. Due to the large imbalance in transmit power between MCs and SCs in HetNets, intelligent user association (UA) is required to perform load balancing and to favor some SCs attraction against MCs. As long term evolution (LTE) cellular networks use the same frequency sub-bands, user equipment may experience strong intercell interference (ICI), especially at cell edge. Therefore, there is a need to coordinate the resource allocation (RA) among the cells and to minimize the ICI. In this paper, we propose a generic algorithm to optimize UA and RA in LTE networks. Our solution, based on game theory, permits to compute cell individual offset and a pattern of power transmission over frequency and time domain for each cell. Simulation results show significant benefits in the average throughput and also cell edge user throughput of 40% and 55% gains respectively. Furthermore, we also obtain a meaningful improvement in energy efficiency.

Due to Orthogonal Frequency Division Multiple Access (OFDMA) mechanism adopted in LTE cellular networks, intra-cell interference is nearly absent. Yet, as these networks are designed for a frequency reuse factor of 1 to maximize the utilization of the licensed bandwidth, inter-cell interference coordination remains an important challenge. In both homogeneous and heterogeneous cellular networks, there is a need for scheduling coordination techniques to efficiently distribute the resources and mitigate inter-cell interference. In this paper, we propose a dynamic solution of inter-cell interference coordination performing an optimization of frequency sub-band reuse and transmission power in order to maximize the overall network utility. The proposed framework, based on game theory, permits to dynamically define frequency and transmission power patterns for each cell in the coordinated cluster. Simulation results show significant benefits in average throughput and also cell edge user throughput of 40% and 55% gains when performing the frequency sub-band muting and power control. Furthermore, we also obtain a meaningful improvement in energy efficiency.

In future networks, Radio Resource Management (RRM) could benefit from Geo-Localized Measurements (GLM) thanks to the Minimization of Drive Testing (MDT) feature introduced in Long Term Evolution (LTE). Such measurements can be processed by the network and be used to optimize its performance. The purpose of this paperais to use GLM to significantly improve scheduling. We introduce the concept of forecast scheduler for users in high mobility that exploits GLM. It is assumed that a Radio Environment Map (REM) can provide interpolated Signal to Interference plus Noise Ratio (SINR) values along the user trajectories. The diversity in the mean SINR values of the users during a time interval of several seconds allows to achieve a significant performance gain. The forecast scheduling is formulated as a convex optimization problem namely the maximization of an α-fair utility function of the cumulated rates of the users along their trajectories. Numerical results for thee different mobility scenarios illustrate the important performance gain achievable by the forecast scheduler.

Estimating mobile user speed is a problematic issue which has significant impacts to radio resource management and also to the mobility management of Long Term Evolution (LTE) networks. This paper introduces two algorithms that can estimate the speed of mobile user equipments (UE), with low computational requirement, and without modification of neither current user equipment nor 3GPP standard protocol. The proposed methods rely on uplink (UL) sounding reference signal (SRS) power measurements performed at the eNodeB (eNB) and remain efficient with large sampling period (e.g., 40 ms or beyond). We evaluate the effectiveness of our algorithms using realistic LTE system data provided by the eNB Layer1 team of Alcatel-Lucent. Results show that the classification of UE's speed required by LTE can be achieved with high accuracy. In addition, they have minimal impact to the central processing unit (CPU) and the memory of eNB modem. We see that they are very practical to today's LTE networks and would allow a continuous and real-time UE speed estimation.

The aim of this paperais to study new antenna array technologies in order to manage efficiently heterogeneous, fixed and mobile traffic. Traffic light close to the cell edge is introduced to generate non stationary mobility pattern in the cell. A car following model is used to model the mobility behavior of the vehicles. A heterogeneous antenna system with different large antenna array technologies is considered: Virtual Small Cell (VSC), virtual small cell with Self-Organizing Network (VSC-SON) and beamforming with multilevel global codebook that manages the heterogeneous antenna system at the Base Station (BS). The first two technologies improve the cell performance due to the capability to focus the signal at the traffic concentration near the traffic light. The novel beamforming solution with global codebook can further and significantly improve performance due to the capability to focus the signal along the road and to implicitly balance the traffic between the different antennas. Numerical simulations illustrate the benefits brought about by the different antenna technologies.

Complementing traditional cellular networks with the option of integrated small cells and WiFi access points can be used to further boost the overall traffic capacity and service level. Small cells along with WiFi access points are projected to carry over 60 percent of all the global data traffic by 2015. With the integration of small cells on the radio access network levels, there is a focus on providing operators with more control over small cell selection while reducing the feedback burden. Altogether, these issues motivate the need for innovative distributed and autonomous association policies that operate on each user under the network operator's control, utilizing only partial information, yet achieving near-optimal solutions for the network. In this paper, we propose a load-aware network selection approach applied to automated dynamic offset in heterogeneous networks (HetNets). In particular, we investigate the properties of a hierarchical (Stackelberg) Bayesian game framework, in which the macro cell dynamically chooses the offset about the state of the channel in order to guide users to perform intelligent network selection decisions between macro cell and small cell networks. We derive analytically the utility related to the channel quality perceived by users to obtain the equilibria, and compare it to the fully centralized (optimal), the full channel state information and the non-cooperative (autonomous) models. Building upon these results, we effectively address the problem of how to intelligently configure a dynamic offset which optimizes network's global utility while users maximize their individual utilities. One of the technical contributions of the paper lies in obtaining explicit characterizations of the dynamic offset at the equilibrium and the related performances in terms of the price of anarchy. Interestingly, it turns out that the complexity of the algorithm for finding the dynamic offset of the Stackelberg model is O(n4) (where n is the number of users). It is shown that the proposed hierarchical mechanism keeps the price of anarchy almost equal to 1 even for a low number of users, and remains bounded above by the non-cooperative model.

The Quality of Experience (QoE) of streaming service is often degraded by frequent playback interruptions. To mitigate the interruptions, the media player prefetches streaming contents before starting playback, at a cost of initial delay. We study the QoE of streaming from the perspective of flow dynamics. First, a framework is developed for QoE when streaming users join the network randomly and leave after downloading completion. We model the distribution of prefetching delay using partial differential equations (PDEs), and the probability generating function of playout buffer starvations using ordinary differential equations (ODEs) for constant bit-rate (CBR) streaming. The explicit form starvation probabilities and mean start-up delay are obtained by use of a matrix function approach. Second, we extend our framework to characterize the throughput variation caused by opportunistic scheduling at the base station, and the playback variation of variable bit-rate (VBR) streaming. Our study reveals that the flow dynamics is the fundamental reason of playback starvation. The QoE of streaming service is dominated by the first moments such as the average throughput of opportunistic scheduling and the mean playback rate. While the variances of throughput and playback rate have very limited impact on starvation behavior in practice.

We develop in this paper a trend detection algorithm, designed to find trendy topics being disseminated in a social network. We assume that the broadcasts of messages in the social network is governed by a self-exciting point process, namely a Hawkes process, which takes into consideration the real broadcasting times of messages and the interaction between users and topics. We formally define trendiness and derive trend indices for each topic being disseminated in the social network. These indices take into consideration the time between the detection and the message broadcasts, the distance between the real broadcast intensity and the maximum expected broadcast intensity, and the social network topology. The proposed trend detection algorithm is simple and uses stochastic control techniques in order to calculate the trend indices. It is also fast and aggregates all the information of the broadcasts into a simple one-dimensional process, thus reducing its complexity and the quantity of data necessary to the detection.

In this paper, we have two objectives: First we model the posting behavior in Social Networks in topics which have negative externalities, and the second objective is to propose content active filtering in order to increase content diversity. By negative externalities, we mean that when the quantity of posted contents about some topic increases the popularity of posted contents decreases. We introduce a dynamical model to describe the posting behavior of users taking into account these externalities. Our model is based on stochastic approximations and sufficient conditions are provided to ensure its convergence to a unique rest point. We provide a close form of this rest point. Content Active Filtering (CAF) are actions taken by the administrator of the Social Network in order to promote some objectives related to the quantity of contents posted in various topics. As objective of the CAF we shall consider maximizing the diversity of posted contents.

We propose power allocation among femto-base stations (femto-BSs) in a heterogeneous network (HetNet) based on non cooperative games. A minimum level of quality of service has to be guaranteed at macro-user terminals (macro-UTs). Femto-BSs are unaware of the exact values of the channel parameters between them and macro-UTs because of the lack of cooperation and fading. First, we consider the design criterion where the outage probability has to be below a certain threshold at macro-UTs. The equilibrium concept is based on the Normalized Nash Equilibrium (NNE) since it caters to the distributed setting. NNE is unique only for a few strictly concave utility functions in this case. We introduce the concept of Weakly Normalized Nash Equilibrium (WNNE) which keeps the most of the appealing features of NNE but can be extended to a wide class of utility functions and can be incorporated with low complexity. Finally, we consider the design criterion where the expected SINR at a macro-UT has to be greater than a threshold. In this case, the NNE is always unique for any strictly concave utility functions.

Virtual Sectorization (ViSn) aims at covering a confined area such as a traffic hot-spot using a narrow beam. The beam is generated by a remote antenna array located at- or close to the Base Station (BS). This paper develops the ViSn model and provides the guidelines for designing the Virtual Sector (ViS) antenna. In order to mitigate interference between the ViS and the traditional macro sector covering the rest of the area, a Dynamic Spectrum Allocation (DSA) algorithm that self-optimizes the frequency bandwidth split between the macro cell and the ViS is also proposed. The Self-Organizing Network (SON) algorithm is constructed to maximize the proportional fair utility of all the users throughputs. Numerical simulations show the interest in deploying ViSn, and the significant capacity gain brought about by the self-optimized bandwidth sharing with respect to a full reuse of the bandwidth by the ViS.

Vertical Sectorization (VS) consists in creating vertically separated sectors in the original cell using an Active Antenna Systems (AAS) supporting two distinct beams with different downtilts. The total transmit power is split between the two sectors, while the frequency bandwidth can be reused by each sector, creating additional interference between the two sectors. For low traffic demand, VS may lead to performance degradation, while for high traffic demand in both sectors, VS is likely to bring about important capacity gains. Hence intelligent activation policy of VS is needed to fully benefit from this feature. In this paper, we propose an approach taking advantage of the more focused downtilted beam. A dynamic alpha-fair bandwidth sharing is proposed for low and medium load. It is autonomously replaced by full bandwidth reuse for high load scenarios using a threshold-based controller. A flow-level dynamic simulator is used to numerically validate the proposed mechanisms.

We consider heterogeneous networks with multiple femtocells and macrocells. Femto-base stations (femto-BS) are constrained to allocate transmitting powers such that the total interference at each macro-user terminal (macro-UT) is below a given threshold. We formulate a power allocation problem as a concave game with femto-BSs as players and multiple macro-UTs enforcing coupled constraints. Equilibrium selection is based on the concept of normalized Nash equilibrium (NNE). When the interference at a femto-user terminal (femto-UT) from adjacent femto-BSs is negligible, for any strictly concave nondecreasing utility the NNE is unique and the NNE is the solution of a concave potential game. We also propose a distributed algorithm which converges to the unique NNE. When the interference is not negligible, an NNE may not be unique and the computation of NNE has exponential complexity. We introduce the concept of weakly normalized Nash equilibrium (WNNE) which keeps the most of NNEs' interesting properties but, in contrast to the latter, the WNNE can be determined with low complexity. We show the usefulness of the WNNE concept for the relevant case of Shannon capacity as femto-BS's utility.

We consider a delay tolerant network under two message forwarding schemes-a non-replicative direct delivery scheme and a replicative epidemic routing scheme. Our objective is to track the degree of spread of a message in the network. Such estimation can be used for on-line control of message dissemination. With a homogeneous mobility model with pairwise i.i.d. exponential inter-meeting times, we rigorously derive the system dynamic and measurement equations for optimal tracking by a Kalman filter. Moreover, we provide a framework for tracking a large class of processes that can be modeled as density-dependent Markov chains. We also apply the same filter with a heterogeneous mobility, where the aggregate inter-meeting times exhibit a power law with exponential tail as in real-world mobility traces, and show that the performance of the filter is comparable to that with homogeneous mobility. Through customized simulations, we demonstrate the trade-offs and provide several insightful observations on how the number of observers impacts the filter performance.

The goal of this paper is to study the behaviour of viewcount in YouTube. We first propose several bio-inspired models for the evolution of the viewcount of YouTube videos. We show, using a large set of empirical data, that the viewcount for 90% of videos in YouTube can indeed be associated to at least one of these models, with a Mean Error which does not exceed 5%. We derive automatic ways of classifying the viewcount curve into one of these models and of extracting the most suitable parameters of the model. We study empirically the impact of videos' popularity and category on the evolution of its viewcount. We finally use the above classification along with the automatic parameters extraction in order to predict the evolution of videos' viewcount.

In this paper, we develop a hierarchical Bayesian game framework for automated dynamic offset selection. Users compete to maximize their throughput by picking the best locally serving radio access network (RAN) with respect to their own measurement, their demand and a partial statistical channel state information (CSI) of other users. In particular, we investigate the properties of a Stackelberg game, in which the base station is a player on its own. We derive analytically the utilities related to the channel quality perceived by users to obtain the equilibria. We study the Price of Anarchy (PoA) of such system, where the PoA is the ratio of the social welfare attained when a network planner chooses policies to maximize social welfare versus the social welfare attained in Nash/Stackeleberg equilibrium when users choose their policies strategically. We show by means of a Stackelberg formulation, how the operator, by sending appropriate information about the state of the channel, can configure a dynamic offset that optimizes its global utility while users maximize their individual utilities. The proposed hierarchical decision approach for wireless networks can reach a good trade-off between the global network performance at the equilibrium and the requested amount of signaling. Typically, it is shown that when the network goal is orthogonal to user's goal, this can lead the users to a misleading association problem.

We propose a model to analyze the decisions taken by an Autonomous System (AS) when joining the Internet. We first define a realistic model for the interconnection costs incurred and then we use this cost model to perform a game theoretic analysis of the decisions related to the creation of new links in the Internet. The proposed model doesn't fall into the standard category of routing games, hence we devise new tools to solve it by exploiting peculiar properties of our game. We prove analytically the existence of multiple equilibria for specific cases, and provide an algorithm to compute the stable ones. The analysis of the model's outcome highlights the existence of a Price of Anarchy (PoA) and a Price of Stability (PoS), originated by the non-cooperative behavior of the ASes, which optimize their cost function in a selfish and decentralized manner. We further observe the presence of competition between the facilities providing either transit or peering connectivity, caused by the cost differences between these two interconnection strategies.

We consider storage devices located in the plane according to a general point process and specialize the results for the homogeneous Poisson process. A large data file is stored at the storage devices, which have limited storage capabilities. Hence, they can only store parts of the data. Clients can contact the storage devices to retrieve the data. We compare the expected cost of obtaining the complete data under uncoded as well as coded data allocation strategies. It is shown that for the general class of cost measures where the cost of retrieving data is increasing with the distance between client and storage devices, coded allocation outperforms uncoded allocation. The improvement offered by coding is quantified for two more specific classes of performance measures. Finally, our results are validated by computing the costs of the allocation strategies for the case that storage devices coincide with currently deployed mobile base stations.

Access to online contents represents a large share of the Internet traffic. Most such contents are multimedia items which are user-generated, i.e., posted online by the contents' owners. In this paper we focus on how those who provide contents can leverage online platforms in order to profit from their large base of potential viewers. Actually, platforms like Vimeo or YouTube provide tools to accelerate the dissemination of contents, i.e., recommendation lists and other re-ranking mechanisms. Hence, the popularity of a content can be increased by paying a cost for advertisement: doing so, it will appear with some priority in the recommendation lists and will be accessed more frequently by the platform users. Ultimately, such acceleration mechanism engenders a competition among online contents to gain popularity. In this context, our focus is on the structure of the acceleration strategies which a content provider should use in order to optimally promote a content given a certain daily budget. Such a best response indeed depends on the strategies adopted by competing content providers. Also, it is a function of the potential popularity of a content and the fee paid for the platform advertisement service. We formulate the problem as a differential game and we solve it for the infinite horizon case by deriving the structure of certain Nash equilibria of the game.

We consider in this paper dynamic Multiple Access (MAC) games between a random number of players competing over collision channels. Each of several mobiles involved in an interaction determines whether to transmit at a high or at a low power. High power decreases the lifetime of the battery but results in smaller collision probability. We formulate this game as an anonymous sequential game with undiscounted reward which we recently introduced and which combines features from both population games (infinitely many players) and stochastic games. We briefly present this class of games and basic equilibrium existence results for the total expected reward as well as for the expected average reward. We then apply the theory in the MAC game.

Small cells have been identified as an effective solution for coping with the important traffic increase that is expected in the coming years. But this solution is accompanied by additional interference that needs to be mitigated. The enhanced Inter Cell Interference Coordination (eICIC) feature has been introduced to address the interference problem. eICIC involves two parameters which need to be optimized, namely the Cell Range Extension (CRE) of the small cells and the ABS ratio (ABSr) which defines a mute ratio for the macro cell to reduce the interference it produces. In this paper we propose self-optimizing algorithms for the eICIC. The CRE is adjusted by means of load balancing algorithm. The ABSr parameter is optimized by maximizing a proportional fair utility of user throughputs. The convergence of the algorithms is proven using stochastic approximation theorems. Numerical simulations illustrate the important performance gain brought about by the different algorithms.

Our purpose in this paper is to characterize buffer starvations for streaming services. The buffer is modeled as a FIFO queue with exponential service time and Poisson arrivals. When the buffer is empty, the service restarts after a certain amount of packets are prefetched. With this goal, we propose two approaches to obtain exact distribution of the number of buffer starvations, one of which is based on Ballot theorem, and the other uses recursive equations. The Ballot theorem approach gives an explicit result. We extend this approach to the scenario with a constant playback rate using Tàkacs Ballot theorem. The recursive approach, though not offering an explicit result, allows us to obtain the distribution of starvations with non-independent and identically distributed (i.i.d.) arrival process in which an ON/OFF bursty arrival process is considered. We further compute the starvation probability as a function of the amount of prefetched packets for a large number of files via a fluid analysis. Among many potential applications of starvation analysis, we show how to apply it to optimize objective quality of experience (QoE) of media streaming, by exploiting the tradeoff between startup/rebuffering delay and starvations.

Representatives of several Internet service providers (ISPs) have expressed their wish to see a substantial change in the pricing policies of the Internet. In particular, they would like to see content providers (CPs) pay for use of the network, given the large amount of resources they use. This would be in clear violation of the “network neutrality” principle that had characterized the development of the wireline Internet. Our first goal in this article is to propose and study possible ways of implementing such payments and of regulating their amount. We introduce a model that includes the users' behavior, the utilities of the ISP and of the CPs, and, the monetary flow that involves the content users, the ISP and CP, and, in particular, the CP's revenues from advertisements. We consider various game models and study the resulting equilibria; they are all combinations of a noncooperative game (in which the ISPs and CPs determine how much they will charge the users) with a “cooperative” one on how the CP and the ISP share the payments. We include in our model a possible asymmetric weighting parameter (that varies between zero to one). We also study equilibria that arise when one of the CPs colludes with the ISP. We also study two dynamic game models as well as the convergence of prices to the equilibrium values.

We consider the problem of “fair” scheduling the resources to one of the many mobile stations by a centrally controlled base station (BS). The BS is the only entity taking decisions in this framework based on truthful information from the mobiles on their radio channel. We study the well-known family of parametric α-fair scheduling problems from a game-theoretic perspective in which some of the mobiles may be noncooperative. We first show that if the BS is unaware of the noncooperative behavior from the mobiles, the noncooperative mobiles become successful in snatching the resources from the other cooperative mobiles, resulting in unfair allocations. If the BS is aware of the noncooperative mobiles, a new game arises with BS as an additional player. It can then do better by neglecting the signals from the noncooperative mobiles. The BS, however, becomes successful in eliciting the truthful signals from the mobiles only when it uses additional information (signal statistics). This new policy along with the truthful signals from mobiles forms a Nash equilibrium (NE) that we call a Truth Revealing Equilibrium. Finally, we propose new iterative algorithms to implement fair scheduling policies that robustify the otherwise nonrobust (in presence of noncooperation) α-fair scheduling algorithms.

This paper tackles the issue of reliable transport in delay-tolerant mobile ad hoc networks (DTNs) that are operated by some opportunistic routing algorithm. We propose a reliable transport mechanism that relies on acknowledgements (ACKs) and coding at the source. The various versions of the problem depending on buffer management policies are formulated and a fluid model based on mean-field approximation is derived for the designed reliable transport mechanism. This model allows both the mean file completion time and the energy consumption to be expressed up to the delivery of the last ACK at the source. The accuracy of this model is assessed through numerical simulations and a detailed investigation of the impact of the system parameters on the performance is conducted. We eventually present a joint optimization of the mean completion delay with or without an energy constraint, to identify the optimal set of parameters to use.

Social networking sites pervade the World Wide Web and have millions of users worldwide. This provides ample opportunity for brands and organisations to reach out to a large and diverse audience. They do so by creating content and spreading it across the social network. Most popular social networks follow a timeline based homepage to display such content to the end users. Content once posted on the timeline, remains visible for a limited time, determined by the rate of content generation in the network. There are various ways by which brands can become more visible on the timeline of their followers, for instance by retransmitting/advertising their content from time to time. Hence, with multiple content creators in the network, there is a competition over a user's timeline, which we analyse in this paper. We first characterise the occupancy distribution of a given user's timeline and then use queueing techniques to analyse the period of time a content is present on a given timeline. We then study the competition between different content creators and characterise the equilibrium rate of content generation. We finally provide some numerical results, which provide insights into the effect of various system parameters.

Recommendation systems (RS) take advantage of products and users information in order to propose items to consumers.Collaborative, content-based and a few hybrid RS have been developed in the past.In contrast, we propose a new domain-independent semantic RS.By providing textually well-argued recommendations, we aim to give more responsibility to the end user in his decision.The system includes a new similarity measure keeping up both the accuracy of rating predictions and coverage.We propose an innovative way to apply a fast adaptation scheme at a semantic level, providing recommendations and arguments in phase with the very recent past.We have performed several experiments on films data, providing textually well-argued recommendations.

Social scientists have observed that human behavior in society can often be modeled as corresponding to a threshold type policy. A new behavior would propagate by a procedure in which an individual adopts the new behavior if the fraction of his neighbors or friends having adopted such behavior exceeds some threshold. In this paper we study the question of whether the emergence of threshold policies may be modeled as a result of some rational process which would describe the behavior of non-cooperative rational members of some social network. We focus on situations in which individuals take the decision whether to access or not some content, based on the number of views that the content has. Our analysis aims at understanding not only the behavior of individuals, but also the way in which information about the quality of a given content can be deduced from view counts when only part of the viewers that access the content are informed about its quality. In this paper we present a game formulation for the behavior of individuals using a meanfield model: the number of individuals is approximated by a continuum of atomless players and for which the Wardrop equilibrium is the solution concept. We derive conditions on the problem's parameters that result indeed in the emergence of threshold equilibria policies. But we also identify some parameters in which other structures are obtained for the equilibrium behavior of individuals.

In dense wireless networks, inter-cell interference highly limits the capacity and quality of service perceived by users. Previous work has shown that approaches based on frequency reuse provide important capacity gains. We model a wireless network with Inter-Cell Interference Coordination (ICIC) at the flow level where users arrive and depart dynamically, in order to optimize quality of service indicators perceivable by users such as file transfer time for elastic traffic. We propose an algorithm to tune the parameters of ICIC schemes automatically based on measurements. The convergence of the algorithm to a local optimum is proven, and a heuristic to improve its convergence speed is given. Numerical experiments show that the distance between local optima and the global optimum is very small, and that the algorithm is fast enough to track changes in traffic on the time scale of hours. The proposed algorithm can be implemented in a distributed way with very small signaling load.

The issue of energy efficiency (EE) in Orthogonal Frequency-Division Multiple Access (OFDMA) wireless networks is discussed in this paper. Our interest is focused on the promising concept of base station (BS) sleep mode, introduced recently as a key feature in order to dramatically reduce network energy consumption. The proposed technical approach fully exploits the properties of stochastic geometry, where the number of active cells is reduced in a way that the outage probability, or equivalently the signal to interference plus noise (SINR) distribution, remains the same. The optimal EE gains are then specified with the help of a simplified but yet realistic BS power consumption model. Furthermore, the authors extend their initial work by studying a non-singular path loss model in order to verify the validity of the analysis and finally, the impact on the achieved user capacity is investigated. In this context, the significant contribution of this paper is the evaluation of the theoretically optimal energy savings of sleep mode, with respect to the decisive role that the BS power profile plays.

The Quality of Experience (QoE) of streaming service is often degraded by frequent playback interruptions. To mitigate the interruptions, the media player prefetches streaming contents before starting playback, at a cost of delay. We study the QoE of streaming from the perspective of flow dynamics. First, a framework is developed for QoE when streaming users join the network randomly and leave after downloading completion. We compute the distribution of prefetching delay using partial differential equations (PDEs), and the probability generating function of playout buffer starvations using ordinary differential equations (ODEs). Second, we extend our framework to characterize the throughput variation caused by opportunistic scheduling at the base station in the presence of fast fading. Our study reveals that the flow dynamics is the fundamental reason of playback starvation. The QoE of streaming service is dominated by the average throughput of opportunistic scheduling, while the variance of throughput has very limited impact on starvation behavior.

A matching theoretic approach to study the partner selection in cooperative relaying is followed. Partner selection is considered as a special stable roommate problem where each player ranks its partners by some criterion. Each agent aims here at finding a “good” partner in order to exploit efficiently the spatial diversity achieved with cooperation. We adapt Irving's algorithm [3] for determining the partners of each player. The ranking criterion here is chosen to be outage probability such that each player comprises its own preference list according to outage probability from the lowest to the highest. The first player in the preference list provides the lowest outage probability. We introduce a decentralized version of Irving's algorithm. Then, we compare the results obtained by stable-matching with the global optimum and random selection results. From the computational results, we observe that stable-matching results are near to global optimum as well as superior than random selection in terms of average outage probability.

In this paper, a distributed algorithm for energy efficient virtual Multiple-input Multiple-output (MIMO) coalition formation is proposed. We model cooperation as a game theoretic approach derived from the concept of stable marriage with incomplete lists (SMI). Thus, single antenna devices such as mobile and relay stations are allowed to cooperate in order to improve the user's and system's energy efficiency. Our approach is focused on optimizing the circuit consumed power of the single antenna devices rather than on the transmitted power, thus the total device power consumption including the effect of the power amplifiers is taken into account. Furthermore, we show analytically and by simulation that under certain conditions cooperation does not improve the energy efficiency metric of network users, thus single antenna devices prefer to transmit independently in order to maintain the user's performance in the network. Additionally, our distributed approach reduces the communication overhead by 76% when compared with a centralized global optimum scheme, which is coordinated from the base station.

This paper studies a significant problem in green networking called switching off base stations in case of cooperating service providers by means of stochastic geometric and coalitional game tools. The coalitional game herein considered is played by service providers who cooperate in switching off base stations. When they cooperate, any mobile is associated to the nearest BS of any service provider. Given a Poisson point process deployment model of nodes over an area and switching off base stations with some probability, it is proved that the distribution of signal to interference plus noise ratio remains unchanged while the transmission power is increased up to preserving the quality of service. The coalitional game behavior of a typical player is called to be hedonic if the gain of any player depends solely on the members of the coalition to which the player belongs, thus, the coalitions form as a result of the preferences of the players over their possible coalitions' set. We utilize the Nash-stable core for determining the coalitions of service providers.

Performance of a delay-tolerant network has strong dependence on the nodes participating in data transportation. Such networks often face several resource constraints especially related to energy. Energy is consumed not only in data transmission, but also in listening and in several signaling activities. On one hand these activities enhance the system's performance while on the other hand, they consume a significant amount of energy even when they do not involve actual node transmission. Accordingly, in order to use energy efficiently, one may have to limit not only the amount of transmissions, but also the amount of nodes that are active at each time. Therefore, we study two coupled problems: 1) the activation problem that determines when a mobile will turn on in order to receive packets; and 2) the problem of regulating the beaconing. We derive optimal energy management strategies by formulating the problem as an optimal control one, which we then explicitly solve. We also validate our findings through extensive simulations that are based on contact traces.

The paper has two objectives. The first is to study rigorously the transient behavior of some peer-to-peer (P2P) networks whenever information is replicated and disseminated according to epidemic-like dynamics. The second is to use the insight gained from the previous analysis in order to predict how efficient are measures taken against P2P networks. We first introduce a stochastic model that extends a classical epidemic model and characterize the P2P swarm behavior in presence of free-riding peers. We then study a second model in which a peer initiates a contact with another peer chosen randomly. In both cases, the network is shown to exhibit phase transitions: A small change in the parameters causes a large change in the behavior of the network. We show, in particular, how phase transitions affect measures of content providers against P2P networks that distribute nonauthorized music, books, or articles and what is the efficiency of countermeasures. In addition, our analytical framework can be generalized to characterize the heterogeneity of cooperative peers.

We study the tradeoff between delivery delay and energy consumption in a delay-tolerant network in which a message (or a file) has to be delivered to each of several destinations by epidemic relaying. In addition to the destinations, there are several other nodes in the network that can assist in relaying the message. We first assume that, at every instant, all the nodes know the number of relays carrying the message and the number of destinations that have received the message. We formulate the problem as a controlled continuous-time Markov chain and derive the optimal closed-loop control (i.e., forwarding policy). However, in practice, the intermittent connectivity in the network implies that the nodes may not have the required perfect knowledge of the system state. To address this issue, we obtain an ordinary differential equation (ODE) (i.e., a deterministic fluid) approximation for the optimally controlled Markov chain. This fluid approximation also yields an asymptotically optimal open-loop policy. Finally, we evaluate the performance of the deterministic policy over finite networks. Numerical results show that this policy performs close to the optimal closed-loop policy.

In Delay Tolerant Networks (DTNs) the core challenge is to cope with lack of persistent connectivity and yet be able to deliver messages from source to destination. In particular, routing schemes that leverage relays' memory and mobility are a customary solution in order to improve message delivery delay. When large files need to be transferred from source to destination, not all packets may be available at the source prior to the first transmission. This motivates us to study general packet arrivals at the source, derive performance analysis of replication-based routing policies and study their optimization under two-hop routing. In particular, we determine the conditions for optimality in terms of probability of successful delivery and mean delay and we devise optimal policies, so-called it piecewise-threshold policies. We account for linear block-codes and rateless random linear coding to efficiently generate redundancy, as well as for an energy constraint in the optimization. We numerically assess the higher efficiency of piecewise-threshold policies compared with other policies by developing heuristic optimization of the thresholds for all flavors of coding considered.

This paper studies a power control game over a collision channel. Each player has an energy state and balances energy conservation and transmission success. When opting for higher transmission power, the chances of a successful transmission in the presence of interference increases at the cost of a larger drop in energy. We study this dynamic game when restricting to simple non-dynamic strategies: a power level is chosen at start-up and maintained during the lifetime of the battery. A thorough analysis of the existence and characterization of the equilibria of this evolutionary Hawk-Dove game is conducted. Moreover, we study the stability of our results under various classes of evolutionary dynamics, including replicator dynamics and Brown-von Neumann-Nash (BNN) dynamics and identify various surprising paradoxes. Simulation results validate our theoretical claims.

In this paper, we study a power control game over a collision channel. Each player has an energy state. When choosing a higher transmission power, the chance of a successful transmission (in the presence of other interference) increases at the cost of a larger decrease in the energy state of the battery. We study this dynamic game when restricting to simple non-dynamic strategies that consist of choosing a given power level that is maintained during the lifetime of the battery. We identify a surprising paradox in our Hawk-Dove game which we term the initial energy paradox.

This paper introduces self-optimization for wireless networks taking into account flow-level dynamics. Users arrive and leave the network according to a traffic model. Elastic traffic is considered here. The developed solutions self-optimize the network stability region using user feedback (measurements). The use case considered is cell size optimization. An algorithm is given, and its convergence is proven using stochastic approximation techniques. Convergence points are characterized, allowing performance gains to be evaluated rigorously. Performance gains are evaluated numerically, showing an important increase of the network capacity.

This paper studies the performance of Mobile Ad hoc Networks (MANETs) when the nodes, that form a Poisson point process, selfishly choose their Medium Access Probability (MAP). We consider goodput and delay as the performance metric that each node is interested in optimizing taking into account the transmission energy costs. We introduce a pricing scheme based on the transmission energy requirements and compute the symmetric Nash equilibria of the game in closed form. It is shown that by appropriately pricing the nodes, the selfish behavior of the nodes can be used to achieve the social optimum at equilibrium. The price of anarchy is then analyzed for these games. For the game with delay based utility, we bound the price of anarchy and study the effect of the price factor. For the game with goodput based utility, it is shown that price of anarchy is infinite at the price factor that achieves the global optima.

Our purpose in this paper is to obtain the exact distribution of the number of buffer starvations within a sequence of N consecutive packet arrivals. The buffer is modeled as an M/M/1 queue. When the buffer is empty, the service restarts after a certain amount of packets are prefetched. With this goal, we propose two approaches, one of which is based on Ballot theorem, and the other uses recursive equations. The Ballot theorem approach gives an explicit solution, but at the cost of the high complexity order in certain circumstances. The recursive approach, though not offering an explicit result, needs fewer computations. We further propose a fluid analysis of starvation probability on the file level, given the distribution of file size and the traffic intensity. The starvation probabilities of this paper have many potential applications. We apply them to optimize the quality of experience (QoE) of media streaming service, by exploiting the tradeoff between the start-up delay and the starvation.

It has been known that the throughput of the 802.11 WLAN is much smaller than the nominal bit rate offered when attempting to connect to an access point. A user may discover the quality of service offered by an access point only after taking the decision of which of the access points to connect to. In fact, the actual throughput of a user is a function of not only his channel state but also of that of the other connected users. This could likely lead to congestion and overload conditions in the Access Point (AP) in question (which offers the best signal strength) and all users would lose. The information available to users attempting to connect to an AP is thus misleading. In this paper, we develop a Nash-Bayesian game framework where users compete to maximize their throughput by picking the best locally serving radio access network (RAN) with respect to their own measurement, their demand and a partial statistical channel state information (CSI) of other users. We derive analytically the utilities perceived by users to obtain the equilibria. In particular, it is shown that equilibria strongly depend on the channel quality indicator.

This note is to correct the author list and authors' affiliations for the above listed paper (ibid., vol. 29, no. 8, pp. 1630-1640, Sep 2011). The acknowledgements are also revised.

This paper studies the performance of a wireless network when the nodes, that form a Poisson point process, selfishly choose their Medium Access Probability (MAP). We define the utility of each node as a weighted difference between a performance metric and some transmission costs. We consider expected goodput and expected delay as the performance metrics. The relative preference of nodes for their performance metrics and the transmission costs is represented by a tradeoff factor. We first consider a scenario in which nodes can be priced for the channel access. We relate the tradeoff factor to some pricing mechanism and compute the symmetric Nash equilibria of the game in closed form as a function of the price factor. We show that simple pricing mechanisms can be used to maximize system efficiency. In particular, we show that for a specific value of price factor, the selfish behavior of the nodes can be used to achieve the same performance as social optima at equilibrium. In the case without pricing where the dis-utility coincides with the transmission energy costs, we analyze the Price of Anarchy for these games. For the game with goodput based utility, we show that the Price of Anarchy is infinite at the tradeoff factor that achieves the global optimal goodput. For the game with delay based utility, we bound the Price of Anarchy and study the effect of the tradeoff factor.

Given the flexibility that software-based operation provides, it is unreasonable to expect that new malware will demonstrate a fixed behavior over time. Instead, malware can dynamically change the parameters of their infective hosts in response to the dynamics of the network, in order to maximize their overall damage. However, in return, the network can also dynamically change its counter-measure parameters in order to attain a robust defense against the spread of malware while minimally affecting the normal performance of the network. The infinite dimension of freedom introduced by variation over time and antagonistic and strategic optimization of malware and network against each other demand new attempts for modeling and analysis. We develop a zero-sum dynamic game model and investigate the structural properties of the saddle-point strategies. We specifically show that saddle-point strategies are simple threshold-based policies and hence, a robust dynamic defense is practicable.

A central scheduling problem in wireless communications is that of allocating resources to one of many mobile stations that have a common radio channel. Much attention has been given to the design of efficient and fair scheduling schemes that are centrally controlled by a base station (BS) whose decisions depend on the channel conditions reported by each mobile. The BS is the only entity taking decisions in this framework. The decisions are based on the reports of mobiles on their radio channel conditions. In this paper, we study the scheduling problem from a game-theoretic perspective in which some of the mobiles may be noncooperative or strategic, and may not necessarily report their true channel conditions. We model this situation as a signaling game and study its equilibria. We demonstrate that the only Perfect Bayesian Equilibria (PBE) of the signaling game are of the babbling type: the noncooperative mobiles send signals independent of their channel states, the BS simply ignores them, and allocates channels based only on the prior information on the channel statistics. We then propose various approaches to enforce truthful signaling of the radio channel conditions: a pricing approach, an approach based on some knowledge of the mobiles' policies, and an approach that replaces this knowledge by a stochastic approximations approach that combines estimation and control. We further identify other equilibria that involve non-truthful signaling.

The security threat posed by malware in mobile wireless networks can be countered through immunization using security patches. The distribution of patches, however, consumes bandwidth that is scarce in wireless networks, and must, there fore, be judiciously controlled in order to attain desired tradeoffs between security risks and bandwidth consumption. We consider both nonreplicative and replicative dissemination of patches: a predetermined set of dispatcher nodes distribute the patches in the former, whereas the dispatcher set continually grows in the latter as the nodes that receive the patch become dispatchers themselves. In each case, the desired tradeoffs can be attained by activating at any given time only fractions of dispatchers and selecting their packet transmission rates. We formulate the afore said tradeoffs as optimal control problems that seek to minimize the aggregate network costs that depend on security risks and the overall extra bandwidth used in the network for dissemination of the security patches. We prove that the dynamic control strategies have simple structures: when the cost function associated with the bandwidth consumed in patching is concave, the control strategies are bang-bang with at most one jump from the maximum to the minimum value. When the cost function is strictly convex, the aforesaid transition is strict but continuous. We compare the efficacy of different dispatch models and also those of the optimum dynamic and static controls using numerical computations.

We consider a dense, ad hoc wireless network, confined to a small region. The wireless network is operated as a single cell, i.e., only one successful transmission is supported at a time. Data packets are sent between source-destination pairs by multihop relaying. We assume that nodes self-organize into a multihop network such that all hops are of length d meters, where d is a design parameter. There is a contention-based multiaccess scheme, and it is assumed that every node always has data to send, either originated from it or a transit packet (saturation assumption). In this scenario, we seek to maximize a measure of the transport capacity of the network (measured in bit-meters per second) over power controls (in a fading environment) and over the hop distance d, subject to an average power constraint. We first motivate that for a dense collection of nodes confined to a small region, single cell operation is efficient for single user decoding transceivers. Then, operating the dense ad hoc wireless network (described above) as a single cell, we study the hop length and power control that maximizes the transport capacity for a given network power constraint. More specifically, for a fading channel and for a fixed transmission time strategy (akin to the IEEE 802.11 TXOP), we find that there exists an intrinsic aggregate bit rate (\Theta_{opt} bits per second, depending on the contention mechanism and the channel fading characteristics) carried by the network, when operating at the optimal hop length and power control. The optimal transport capacity is of the form d_{opt}(\bar{P_t}) \times \Theta_{opt} with d_{opt} scaling as \bar{P_t}^{{1\over \eta}}, where \bar{P_t} is the available time average transmit power and \eta is the path loss exponent. Under certain conditions on the fading distribution, we then provide a simple characterization of the optimal operating point. Simulation results are provided comparing the performance of the optimal strategy derived here with some simple strategies for operating the network.

Relay stations are an important component of heterogeneous networks introduced in the LTE-Advanced technology as a means to provide very high capacity and QoS all over the cell area. This paper develops a self-organizing network (SON) feature to optimally allocate resources between backhaul and station to mobile links. Static and dynamic resource sharing mechanisms are investigated. For stationary ergodic traffic we provide a queuing model to calculate the optimal resource sharing strategy and the maximal capacity of the network analytically. When traffic is not stationary, we propose a load balancing algorithm to adapt both the resource sharing and the zones covered by the relays based on measurements. Convergence to an optimal configuration is proven using stochastic approximation techniques. Self-optimizing dynamic resource allocation is tackled using a Markov Decision Process model. Stability in the infinite buffer case and blocking rate and file transfer time in the finite buffer case are considered. For a scalable solution with a large number of relays, a well-chosen parameterized family of policies is considered, to be used as expert knowledge. Finally, a model-free approach is shown in which the network can derive the optimal parameterized policy, and the convergence to a local optimum is proven.

We study the question of determining locations of base stations (BSs) that may belong to the same or to competing service providers. We take into account the impact of these decisions on the behavior of intelligent mobile terminals that can connect to the base station that offers the best utility. The signal-to-interference-plus-noise ratio (SINR) is used as the quantity that determines the association. We first study the SINR association-game: We determine the cells corresponding to each base stations, i.e., the locations at which mobile terminals prefer to connect to a given base station than to others. We make some surprising observations: 1) displacing a base station a little in one direction may result in a displacement of the boundary of the corresponding cell to the opposite direction; 2) a cell corresponding to a BS may be the union of disconnected subcells. We then study the hierarchical equilibrium in the combined BS location and mobile association problem: We determine where to locate the BSs so as to maximize the revenues obtained at the induced SINR mobile association game. We consider the cases of single frequency band and two frequency bands of operation. Finally, we also consider hierarchical equilibria in two frequency systems with successive interference cancellation.

Malware attacks constitute a serious security risk that threatens to slow down the large-scale proliferation of wireless applications. As a first step toward thwarting this security threat, we seek to quantify the maximum damage inflicted on the system due to such outbreaks and identify the most vicious attacks. We represent the propagation of malware in a battery-constrained mobile wireless network by an epidemic model in which the worm can dynamically control the rate at which it kills the infected node and also the transmission ranges and/or the media scanning rates. At each moment of time, the worm at each node faces the following tradeoffs: 1) using larger transmission ranges and media scanning rates to accelerate its spread at the cost of exhausting the battery and thereby reducing the overall infection propagation rate in the long run; or 2) killing the node to inflict a large cost on the network, however at the expense of losing the chance of infecting more susceptible nodes at later times. We mathematically formulate the decision problems and utilize Pontryagin Maximum Principle from optimal control theory to quantify the damage that the malware can inflict on the network by deploying optimum decision rules. Next, we establish structural properties of the optimal strategy of the attacker over time. Specifically, we prove that it is optimal for the attacker to defer killing of the infective nodes in the propagation phase until reaching a certain time and then start the slaughter with maximum effort. We also show that in the optimal attack policy, the battery resources are used according to a decreasing function of time, i.e., most aggressively during the initial phase of the outbreak. Finally, our numerical investigations reveal a framework for identifying intelligent defense strategies that can limit the damage by appropriately selecting network parameters.

This paper shows a Self-organizing networks (SON) algorithm for interference coordination in downlink Orthogonal Frequency-Division Multiple Access (OFDMA) networks. A distributed algorithm is introduced with a proof of convergence for a static user population. The algorithm uses closed-form formulas for the transmit powers update, and is therefore computationally light. The proposed algorithm is applied to a 117 cells dynamic network simulator with a File Transfer Protocol (FTP) service, showing significant performance gains over a Reuse 1. The Quality of Service (QoS) of cell-edge users improves without degrading the QoS of other users. The trade-off between Block Call Rate (BCR), which is the proportion of users rejected by admission control, and cell-edge users throughput is shown, and a simple method for the network operator to manage it is provided.

Epidemics dynamics can describe the dissemination of information in delay tolerant networks, in peer to peer networks and in content delivery networks. The control of such dynamics has thus gained a central role in all of these areas. However, a major difficulty in this context is that the objective functions to be optimized are often not additive in time but are rather multiplicative. The classical objective function in DTNs, i.e., the successful delivery probability of a message within a given deadline, falls precisely in this category, because it takes often the form of the expectation of the exponent of some integral cost. So far, models involving such costs have been solved by interchanging the order of expectation and the exponential function. While reducing the problem to a standard optimal control problem, this interchange is only tight in the mean field limit obtained as the population tends to infinity. In this paper we identify a general framework from optimal control in finance, known as risk sensitive control, which let us handle the original (multiplicative) cost and obtain solutions to several novel control problems in DTNs. In particular, we can derive the structure of state-dependent controls that optimize transmission power at the source node. Further, we can account for the propagation loss factor of the wireless medium while obtaining these controls, and, finally, we address power control at the destination node, resulting in a novel threshold optimal activation policy. Combined optimal power control at source and destination nodes is also obtained.

The paper has two objectives. The first is to study rigorously the transient behavior of some peer-to-peer (P2P) networks whenever information is replicated and disseminated according to epidemic-like dynamics. The second is to use the insight gained from the previous analysis in order to predict how efficient are measures taken against P2P networks. We first introduce a stochastic model which extends a classical epidemic model, and characterize the P2P swarm behavior in presence of free riding peers. We then study a second model in which a peer initiates a contact with another peer chosen randomly. In both cases the network is shown to exhibit phase transitions: a small change in the parameters causes a large change in the behavior of the network. We show, in particular, how phase transitions affect measures of content providers against P2P networks that distribute non-authorized music or books, and what is the efficiency of counter-measures.

Epidemic models based on nonlinear differential equations have been extensively applied in a variety of systems as diverse as infectious outbreaks, marketing, diffusion of beliefs, etc., to the dissemination of messages in MANET or p2p networks. Control of such systems is achieved at the cost of consuming the resources. We construct a unifying framework that models the interactions of the control and the elements in systems with epidemic behavior. Specifically, we consider non-replicative and replicative dissemination of messages in a network: a pre-determined set of disseminators distribute the messages in the former, whereas the disseminator set continually grows in the latter as the nodes that receive the patch become disseminators themselves. In both cases, the desired trade-offs can be attained by activating at any given time only fractions of disseminators and selecting their dissemination rates. We formulate the above trade-offs as optimal control problems that seek to minimize a general aggregate cost function which cogently depends on both the states and the overall resource consumption. We prove that the dynamic control strategies have simple structures: (1) it is never optimal to activate a partial fraction of the disseminators (all or none) (2) when the resource consumption cost is concave, the distribution rate of the activated nodes are bang-bang with at most one jump from the maximum to the minimum value. When the resource consumption cost is convex, the above transition is strict but continuous. We compare the efficacy and robustness of different dispatch models and also those of the optimum dynamic and static controls using numerical computations.

Given the flexibility that software-based operation provides, it is unreasonable to expect that new malware will demonstrate a fixed behavior over time. Instead, malware can dynamically change the parameters of their infective hosts in response to the dynamics of the network, in order to maximize their overall damage. However, in return, the network can also dynamically change its counter-measure parameters in order to attain a robust defense against the spread of malware while minimally affecting the normal performance of the network. The infinite dimension of freedom introduced by variation over time and antagonistic and strategic optimization of malware and network against each other demand new attempts for modeling and analysis. We develop a zero-sum dynamic game model and investigate the structural properties of the saddle-point strategies. We specifically show that saddle-point strategies are simple threshold-based policies and hence, a robust dynamic defense is practicable.

We study in this paper the problem of sharing the cost of a multicast service in a wireless network. In a wireless network, multiple users can decode the same signal of the base station provided the received power exceeds a certain minimum threshold. In this work, the cost for broadcasting is taken to be the transmission power. We begin by proposing various schemes to share the cost, and study their properties. We then study the association problem where an user has options of either joining the multicast group or opting for a unicast connection at a given cost. Next, we extend the association problem to the scenarios with partial information - a user knows his own power requirement, but has to make decision without knowledge of the number of other users in the network and their requirements. The unicast alternative that each mobile has, results in limitations on the coverage (area covered by the multicast service) and the capacity (number of users connected to the multicast service). We derive the expected capacity and coverage as a function of the cost sharing mechanism. We finally extend the model to the case where users have the option of joining any one from a given set of multicast service providers. A user's power requirement depends on its association, but its cost share depends on the association profile of all the users. We study the joint problem of the cost allocation and the equilibrium association.

We propose a new scheme for reliable transport, both for unicast and multicast flows, in Delay Tolerant Networks (DTNs). Reliability is ensured through the use of Global Selective ACKnowledgements (G-SACKs) which contain detailed (and potentially global) information about the receipt of packets at all the destinations. The motivation for using G-SACKs comes from the observation that one should take the maximum advantage of the contact opportunities which occur quite infrequently in DTNs. We also propose sharing of “packet header space” with G-SACK information and allow for random linear coding at the relay nodes. Our results from extensive simulations of the proposed scheme quantify the gains due to each new feature.

We consider a common object (data) that each mobile in the medium is interested to receive, and which can be obtained from any base station transmitting the data. For example, the broadcast object could be streaming transmission of a sport or cultural event, or it could be some signaling such as a beacon for time synchronization or for power control purposes. This problem can be conceived as a coalition game played by mobiles which we call as association game of mobiles. This game has an incentive to form grand coalition where all players join to the game. We prove that using Bondareva-Shapley theorem, this coalition game has a non-empty core which means that grand coalition is stable. Then, we examine the cost allocation policy for different methods such as egalitarian allocation, proportional repartition of total cost, the Shapley value and the nucleolus. We also conclude that if the nucleolus is used as the cost allocation algorithm, the players maintain the grand coalition satisfying the minimization of total cost for broadcast transmission.

We have recently extended the notion of alpha fairness to include time scale considerations for fair assignment of resources. Two extreme cases are elastic traffic (file transfer) and interactive voice. In this paper we consider time scale separation in the fairness that is related to the mobility of the users. We propose and solve the problem when the utilities are linear in the resources. We apply these results in the context of fair resource allocation in femtocell networks in a dynamic setting. We show how mobility and the constraints on the averaging durations impact the amount of resources each user gets.

In recent years there has been an increasing awareness that the deployment as well as utilization of new information technology may have some negative ecological impact. This includes awareness to energy consumption which could have negative consequences on the environment. In recent years, it was suggested to increase energy saving by deactivating base stations during periods in which the traffic is expected to be low. In this paper we study the optimal deactivation policies, using recent tools from Multimodularity (which is the analog concept of convexity in optimization over integers). We consider two scenarios: In the first case, a central control derives the optimal open loop policies so as to maximize the expected throughput of the system given that at least a certain percentage of Base stations are deactivated (switched OFF). In the second case, we derive optimal open loop polices, which each base station can employ in a decentralized manner to minimize the average buffer occupancy cost when the fraction of time for which the BS station is deactivated (idle mode) is lower bounded. In both the cases, we show that the cost structure is Multimodular and characterize the structure of optimal policies.

We study the trade-off between delivery delay and energy consumption in a delay tolerant network in which a message (or a file) has to be delivered to each of several destinations by epidemic relaying. In addition to the destinations, there are several other nodes in the network that can assist in relaying the message. We first assume that, at every instant, all the nodes know the number of relays carrying the packet and the number of destinations that have received the packet. We formulate the problem as a controlled continuous time Markov chain and derive the optimal closed loop control (i.e., forwarding policy). However, in practice, the intermittent connectivity in the network implies that the nodes may not have the required perfect knowledge of the system state. To address this issue, we obtain an ODE (i.e., fluid) approximation for the optimally controlled Markov chain. This fluid approximation also yields an asymptotically optimal open loop policy. Finally, we evaluate the performance of the deterministic policy over finite networks. Numerical results show that this policy performs close to the optimal closed loop policy.

Internet growth has allowed unprecedented widespread access to cultural creation including music and films, to knowledge, and to a wide range of consumer information. At the same time, it has become a huge source of business opportunities. Along with great benefits that this access to the Internet provides, the open and free access to the Internet has encountered large opposition based on political, economical and ethical reasons. An ongoing battle over the control on Internet access has been escalating on all these fronts. In this paper we describe first some of the ideological roots of free access to the Internet along with its main opponents. We then focus on the problem of “Internet piracy” and analyze the efficiency of efforts to reduce the availability of copyrighted creations that are available for non-authorized free download.

We consider a mobile connected to a base station, and study how to optimally schedule shutting off its transceiver. First, we study the model from optimal control perspective. We consider off-times (periods of inactivity) of (controlled) duration. We study the question of scheduling "waking up" instants in which the mobile communicates with the base station and checks whether the inactivity period is over. There is a cost proportional to the delay from the moment the off-time ends until the mobile discovers it, a (small) running cost while the mobile is sleeping and a cost for waking up. We present conditions for optimal sleep periods to be constant and derive the optimal period. For the case that the conditions do not hold, we obtain suboptimal solutions which perform strictly better than the optimal constant one. We then investigate optimality restricted to classes of policies with specific constraints. We adopt the parametric optimization approach which entails cost minimization for a given parameterized policy and selection of the best policy among a class. We then compare the performance of optimal policies, of the proposed suboptimal policies as well as that of standard policies like IEEE 802.16e.

Distributing Radio Resource Management (RRM) in heterogeneous wireless networks is an important research and development axis that aims at reducing network complexity. In this context, RRM decision making can be delegated to mobiles by incorporating cognitive capabilities into mobile handsets, resulting in the reduction of signalling and processing burden. This may however result in inefficiencies (such as those known as the "tragedy of commons") that are inherent to equilibria in non-cooperative games. Due to the concern for efficiency, centralized network architectures and protocols keep being considered and being compared to decentralized ones. From the point of view of the network architecture, this implies the co-existence of network-centric and terminal-centric RRM schemes. Instead of taking part within the debate among the supporters of each solution, we propose in this paper hybrid schemes where the wireless users are assisted in their decisions by the network that broadcasts aggregated load information. At some system's states, the network manager may impose his decisions on the network users. In other states the mobiles may take autonomous actions in reaction to information sent by the network. In order to improve the performance of the non-cooperative scenario, we investigate the properties of an alternative solution concept named Stackelberg game, in which the network tries to control the users' behavior by broadcasting appropriate information, expected to maximize its utility, while individual users maximize their own utility. We derive analytically the utilities related to the Quality of Service (QoS) perceived by mobile users and develop a Bayesian framework to obtain the equilibria. Numerical results illustrate the advantages of using our hybrid game framework in an association problem in a network composed of HSDPA and 3G LTE system that serve streaming and elastic flows.

Delay-tolerant ad hoc networks leverage the mobility of relay nodes to compensate for lack of permanent connectivity and thus enable communication between nodes that are out of range of each other. To decrease delivery delay, the information to be delivered is replicated in the network. Our objective in this paper is to study a class of replication mechanisms that include coding in order to improve the probability of successful delivery within a given time limit. We propose an analytical approach that allows to quantify tradeoffs between resources and performance measures (energy and delay). We study the effect of coding on the performance of the network while optimizing parameters that govern routing. Our results, based on fluid approximations, are compared to simulations that validate the model.

Motivated by the fact that when selfish users choose their policies independently without any coordination mechanism, Nash equilibria could result in a network collapse, we develop in this paper a hierarchical distributed learning framework for decision-making in heterogeneous cognitive networks. We introduce the Nash-Stackelberg fuzzy Q-learning, with the network as leader that aims at maximizing its utility (revenue) and the mobiles as followers that have their individual objectives (maximizing their QoS). We validate our results through extensive simulations of the algorithm in a practical setting of a geographical area covered by a global HSDPA and 3G LTE system that serves both streaming and elastic traffic.

Size-based (SB) scheduling policies have been shown to improve response times of small flows, without degrading the performance of large flows. But these differentiating policies are designed for Output-queued switch architecture, which is known to have scalability issues. On the other hand, the buffered-crossbar (BX) switch architecture is currently being pursued as a potential next-generation scalable switch architecture. This work looks into the problem of performing SB scheduling in BX switches. In particular, the design goals, w.r.t each output port, are (i) to transmit high-priority packet(s) as long as there is at least one present, and (ii) to respect the FIFO order among high-priority packets. In this direction, we propose to use PIFO queue at each crosspoint of a CICQ switch. The initial design presented as pCICQ-1 switch is simple and guarantees that packet-priorities are respected once they are in the crosspoint queues. But it does not maintain the FIFO order of high-priority packets, besides letting a bounded number low-priority packets to depart through an output, when there are one or more high-priority packets for the same output. To solve this, we propose an enhancement, as pCICQ-2 switch, that achieves both the design goals.

Relay selection combined with buffering of packets of relays can substantially increase the throughput of a cooperative network that uses rateless codes. However, buffering also increases the end-to-end delays due to the additional queuing delays at the relay nodes. In this paper we propose a novel method that exploits a unique property of rateless codes that enables a receiver to decode a packet from non-contiguous and unordered portions of the received signal. In it, each relay, depending on its queue length, ignores its received coded bits with a given probability. We show that this substantially reduces the end-to-end delays while retaining almost all of the throughput gain achieved by buffering. In effect, the method increases the odds that the packet is first decoded by a relay with a smaller queue. Thus, the queuing load is balanced across the relays and traded off with transmission times. We derive explicit necessary and sufficient conditions for the stability of this system when the various channels undergo fading. Despite encountering analytically intractable G/GI/1 queues in our system, we also gain insights about the method by analyzing a similar system with a simpler model for the relay-to-destination transmission times.

Much research has been devoted to maximize the life time of mobile ad-hoc networks. Life time has often been defined as the time elapsed until the first node is out of battery power. In the context of static networks, this could lead to disconnectivity. In contrast, Delay Tolerant Networks (DTNs) leverage the mobility of relay nodes to compensate for lack of permanent connectivity, and thus enable communication even after some nodes deplete their stored energy. One can thus consider the lifetimes of nodes as some additional parameters that can be controlled to optimize the performance of a DTN. In this paper, we consider two ways in which the energy state of a mobile can be controlled. Both listening and transmission require energy, besides each of these has a different type of effect on the network performance. Therefore we consider a joint optimization problem consisting of: i) activation, which determines when a mobile will turn on in order to receive packets, and ii) transmission control, which regulates the beaconing. The optimal solutions are shown to be of the threshold type. The findings are validated through extensive simulations.

We study replication mechanisms that include Reed-Solomon type codes as well as network coding in order to improve the probability of successful delivery within a given time limit. We propose an analytical approach to compute these and study the effect of coding on the performance of the network while optimizing parameters that govern routing.

The area of networking games has had a growing impact on wireless networks. This reflects the recognition in the important scaling advantages that the service providers can benefit from by increasing the autonomy of mobiles in decision making. This may however result in inefficiencies that are inherent to equilibria in non-cooperative games. Due to the concern for efficiency, centralized protocols keep being considered and compared to decentralized ones. From the point of view of the network architecture, this implies the co-existence of network-centric and terminal centric radio resource management schemes. Instead of taking part within the debate among the supporters of each solution, we propose in this paper hybrid schemes where the wireless users are assisted in their decisions by the network that broadcasts aggregated load information. We derive the utilities related to the Quality of Service (QoS) perceived by the users and develop a Bayesian framework to obtain the equilibria. Numerical results illustrate the advantages of using our hybrid game framework in an association problem in a network composed of HSDPA and 3G LTE systems.

Most theoretical research on routing games in telecommunication networks has so far dealt with reciprocal congestion effects between routed entities. Yet in networks that support differentiation between flows, the congestion experienced by a packet depends on its priority level. Another differentiation is made by compressing the packets in the low priority flow while leaving the high priority flow intact. In this paper we study such kind of routing scenarios for the case of non-atomic users and we establish conditions for the existence and uniqueness of equilibrium.

Malware attacks constitute a serious security risk that threatens to slow down the large scale proliferation of wireless applications. As a first step towards thwarting this security threat, we seek to quantify the maximum damage inflicted on the system owing to such outbreaks and identify the most vicious attacks. We represent the propagation of malware in a battery-constrained mobile wireless network by an epidemic model in which the worm can dynamically control the rate at which it kills the infected node and also the transmission range and/or the media scanning rate. At each moment of time, the worm at each node faces the following trade-offs: (i) using larger transmission range and media scanning rate to accelerate its spread at the cost of exhausting the battery and thereby reducing the overall infection propagation rate in the long run or (ii) killing the node to inflict a large cost on the network, however at the expense of loosing the chance of infecting more susceptible nodes at later times. We mathematically formulate the decision problems and utilize Pontryagin Maximum Principle from optimal control theory to quantify the damage that the malware can inflict on the network by deploying optimum decision rules. Next, we establish structural properties of the optimal strategy of the attacker over time. Specifically, we prove that it is optimal for the attacker to defer killing of the infective nodes in the propagation phase until reaching a certain time and then start the slaughter with maximum effort. We also show that in the optimal attack policy, the battery resources are used according to a decreasing function of time, i.e., mostly during the initial phase of the outbreak. Finally, our numerical investigations reveal a framework for identifying intelligent defense strategies that can limit the damage by appropriately selecting network parameters.

In this paper, we study precoded MIMO based small cell networks. We derive the theoretical sum-rate capacity, when multi-antenna base stations transmit precoded information to its multiple single-antenna users in the presence of inter-cell interference from neighboring cells. Due to an interference limited scenario, increasing the number of antennas at the base stations does not yield necessarily a linear increase of the capacity. We assess exactly the effect of multi-cell interference on the capacity gain for a given interference level. We use recent tools from random matrix theory to obtain the ergodic sum-rate capacity, as the number of antennas at the base station, number of users grow large. Simulations confirm the theoretical claims and also indicate that in most scenarios the asymptotic derivations applied to a finite number of users give good approximations of the actual ergodic sum-rate capacity.

In this paper we study the optimal placement and optimal number of active relay nodes through the traffic density in mobile sensor ad hoc networks. We consider a setting in which a set of mobile sensor sources is creating data and a set of mobile sensor destinations is receiving that data through multihop wireless paths. We make the assumption that the network is massively dense, i.e., there are so many sources, destinations, and relay nodes, that it is best to describe the network in terms of macroscopic parameters rather than in terms of microscopic parameters. A simple one-dimensional scenario is used to introduce the problem. We solve the two-dimensional scenario where the mobility of the nodes is deterministic and when it follows the brownian mobility model.

We consider the problem of centrally controlled 'fair' scheduling of resources to one of the many mobile stations connected to a base station (BS). The BS is the only entity making decisions in this framework based on truthful information from the mobiles on their radio channel. We study the well-known family of parametric α-fair scheduling problems from a game-theoretic perspective in which some of the mobiles may be noncooperative. We first show that if the BS is unaware of the noncooperative behavior from the mobiles, the noncooperative mobiles become successful in snatching the resources from the other cooperative mobiles, resulting in unfair allocations. If the BS is aware of the noncooperative mobiles, a new game arises with BS as an additional player. It can then do better by neglecting the signals from the noncooperative mobiles. The BS, however, becomes successful in eliciting the truthful signals from the mobiles only when it uses additional information (signal statistics). This new policy along with the truthful signals from mobiles forms a Nash Equilibrium (NE) called a Truth Revealing Equilibrium. Finally, we propose new iterative algorithms to implement fair scheduling policies that robustify the otherwise non-robust (in presence of noncooperation) α-fair scheduling algorithms.

Reliable security measures against outbreaks of malware is imperative to enable large scale proliferation of wireless technologies. Immunization and healing of the nodes through dissemination of security patches can counter the spread of a malware upon an epidemic outbreak. The distribution of patches however burdens the bandwidth which is scarce in wireless networks. The trade-offs between security risks and resource consumption can be attained by activating at any given time only fractions of dispatchers and dynamically selecting their packet transmission rates. We formulate the above trade-offs as an optimal control problem that seek to minimize the aggregate network costs that depend on security risks and resource consumed by the countermeasures. Using Pontryagin's maximum principle, we prove that the dynamic control strategies have simple structures. When the resource consumption cost is concave, optimal strategy is to use maximum resources for distribution of patches until a threshold time, upon which, the patching should halt. When the resource consumption cost is convex, the above transition is strict but continuous.

A system with ann-dimensional state vector and acontrollerand anactoris considered. The controller has complete information about the system state, and reveals a certain “minimum” amount of information to the actor. The actor takes certain actions based on the information the controller reveals, and the actions fetch certain utilities for each entity. Both the controller and actor seek to maximize their individual utilities by respectively selecting the information to reveal and the actions to adopt. This decision problem forms the basis of several technical and social systems, and can be formulated as a signaling game. It is shown that the Perfect Bayesian Equilibrium of this game has several counterintuitive properties and can be obtained as a saddle point of a different two person zero sum game. The computation time for saddle points using standard linear programs however turns out to be superexponential inn, which leads to computational intractability even for moderaten. Algorithms for computing saddle point policies using a computation time that is exponential innare presented. Finally, simple linear time computable policies that approximate the saddle-point policies within guaranteeable approximation ratios are obtained.

We consider a noncooperative interaction among a large population of mobiles that interfere with each other through many local interactions. The first objective of this paper is to extend the evolutionary game framework to allow an arbitrary number of mobiles that are involved in a local interaction. We allow for interactions between mobiles that are not necessarily reciprocal. We study 1) multiple-access control in a slotted Aloha-based wireless network and 2) power control in wideband code-division multiple-access wireless networks. We define and characterize the equilibrium (called evolutionarily stable strategy) for these games and study the influence of wireless channels and pricing on the evolution of dynamics and the equilibrium.

We considered a single hop ad-hoc network consisting of N source-destination pairs. Each transmitter is endowed with a finite buffer and accepts packets from a Poisson distributed arrival process. The channel is described by a Markov chain. We investigate distributed algorithms for joint admission control, rate and power allocation aiming at maximizing the individual or the global throughput defined as the average information rate successfully received. The decisions are based on the statistical knowledge of the channel and buffer states of the other communication pairs and on the exact knowledge of their own channel and buffer states. The problems are formulated as a cooperative and noncooperative games and reduced to the mathematical framework of the variational inequalities problems. The proposed algorithms provide sizable improvements with respect to straightforward extension of decentralized algorithms for multiple access channels to ad hoc networks.

We study in this paper the question of determining locations of base stations (BSs) that may belong to the same or to competing service providers, taking into account the impact of these decisions on the behavior of intelligent mobile terminals who can connect to the base station that offers the best utility. We first study the SINR association-game: we determine the cells corresponding to each base stations, i.e. the locations at which mobile terminals prefer to connect to a given base station than to other. The signal to interference and noise ratio (SINR) is used as the quantity that determines the association. We make some surprising observations: (i) displacing a base station a little in one direction may result in a displacement of the boundary of the corresponding cell to the opposite direction; (ii) A cell corresponding to a BS may be the union of disconnected sub-cells. We then study the Stackelberg equilibrium in the combined BS location and mobile association problem: we determine where to locate the BSs so as to maximize the revenues obtained at the induced SINR mobile association game. We consider the cases of single frequency band and two frequency bands of operation. Finally, we also consider Stackelberg equilibria in two frequency systems with successive interference cancellation.

In transportation network research, the main approach for predicting traffic distribution due to noncooperative vehicle choices has been through fluid type models. The basic model considers a continuum of infinitesimal "non-atomic" vehicles, each seeking the shortest path to its destination. The resulting equilibrium turns out to be much simpler to characterize in comparison to the finite-vehicle case, yet provides a good approximation to the latter. A less familiar fluid-type model uses a continuum limit for the network topology. The limit network is a continuum plane which inherits its cost structure from the original network, and the corresponding equilibrium is identified as the continuum traffic equilibrium. This paper considers a similar equilibrium notion in a framework of a load balancing problem involving two processors, each requiring non-negligible workload (or "flow") to be handled by network resources. Besides a congestion cost at each resource (which is identical to both processors), each resource induces a processor-dependent connection cost, which is a function of its geographic location. The processors autonomously route their flow onto the different resources, with the objective of minimizing (non-cooperatively) their total cost. Assuming that the number of resources is relatively large, we apply the continuum approximation within a line (or bus) topology and study the Nash equilibria of the processor interaction. This approximation enables us to explicitly characterize the equilibrium in several cases and to obtain insights on its structure, including tight bounds on the efficiency loss due to noncooperation.

We consider decentralized medium-access control in which many pairwise interactions occur between randomly selected users that belong to a large population. In each local interaction, the users involved compete over an access opportunity. A given user has a fixed number of access attempts and a fixed budget for buying different priority levels. In each time-slot, the access is attributed to the user with the largest priority level. We analyze this problem under both cooperative as well as competitive frameworks. We show that unlike many standard team problems, optimal pure policies do not exist in the team framework, but both an optimal solution as well as equilibria exist within the class of mixed policies. We establish structural properties as well as explicit characterization of these: We show that the optimal policy requires only three priority levels, whereas the noncooperative game possesses a unique symmetric equilibrium point that uses at most two priority levels. Our analysis is applied to power control over wireless capture channels, where the budget constraint corresponds to the battery lifetime.

We study in this paper optimal stochastic control issues in delay tolerant networks. We first derive the structure of optimal 2-hop forwarding policies. In order to be implemented, such policies require the knowledge of some system parameters such as the number of mobiles or the rate of contacts between mobiles, but these could be unknown at system design time or may change over time. To address this problem, we design adaptive policies combining estimation and control that achieve optimal performance in spite of the lack of information. We then study interactions that may occur in the presence of several competing classes of mobiles and formulate this as a cost-coupled stochastic game. We show that this game has a unique Nash equilibrium such that each class adopts the optimal forwarding policy determined for the single class problem.

Delay tolerant ad-hoc networks leverage the mobility of relay nodes to compensate for lack of permanent connectivity and thus enable communication between nodes that are out of range of each other. To decrease delivery delay, the information to be delivered is replicated in the network. Our objective in this paper is to study a class of replication mechanisms that include coding in order to improve the probability of successful delivery within a given time limit. We propose an analytical approach that allows to quantify tradeoffs between resources and performance measures (energy and delay). We study the effect of coding on the performance of the network while optimizing parameters that govern routing. Our results, based on fluid approximations, are compared to simulations which validate the model.

The problem of jamming plays an important role in ensuring the quality and security of wireless communications, especially at this moment when wireless networks are quickly becoming ubiquitous. Since jamming can be considered as a game in which jammer is playing against the user (transmitter) who would like to transmit signal with good quality and at the same time with a reasonable amount of energy, game theory is an appropriate tool for dealing with jamming. Here we investigate the effect of partially available information and correlation among sub-carriers on the user behavior. Specifically, to do so we deal with the scenario when the user does not know how jamming efforts are distributed among sub-carriers and the user does not know the fading channels' gains with certainty. As an object function for the user we consider SINR. We consider zero-sum games, so all of them can also be viewed as a minimax problem for the user playing against the nature. We study independent fading channel gains scenario as well as dependent fading channel gains scenario, both in discrete and continuous versions. We show that in all the scenarii the jammers equalize the quality of the best sub-carriers for the transmitter on as low level as their power constraints allow. Meanwhile the transmitter distributes his power among these jamming sub-carriers. We find the equilibrium strategies in closed form and specify the range of sub-carriers where the transmitter can expect the jamming attack. Also, we show for independent plot these strategies depend only on the expected value of the transmitters channel gains meanwhile for the dependent plot they depend on the whole spectra of these gains. Thus, for independent plot the behaviour of the jammer is less fine tuned under environment since it works with the expected gains. The user for both scenarios has to take the whole spectra of the jamming gains but, of course, for the independent scenario he is less specific because of the jammer.

We study a dynamic random access game with a finite number of opportunities for transmission and with energy constraints. We provide sufficient conditions for feasible strategies and for existence of Nash-Pareto solutions and show that finding Nash-Pareto policies of the dynamic random access game is equivalent to partitioning the set of time slot opportunities with constraints into a set of terminals. We further derive upper bounds for pure Nash-Pareto policies, and extend the study to non-integer energy constraints and unknown termination time, where Time Division Multiplexing policies can be suboptimal. We show that the dynamic random access game has several strong equilibria (resilient to coalition of any size), and we compute them explicitly. We introduce the (strong) price of anarchy concept to measure the gap between the payoff under strong equilibria and the social optimum.

In this paper, we present a systematic study of the uplink capacity and coverage of pico-cell wireless networks. Both the one dimensional as well as the two dimensional cases are investigated. Our goal is to compute the size of pico-cells that maximizes the spatial throughput density. To achieve this goal, we consider fluid models that allow us to obtain explicit expressions for the interference and the total received power at a base station. We study the impact of various parameters on the performance: the path loss factor, the spatial reuse factor and the receiver structure (matched filter or multiuser detector). We relate the performance of the fluid models to that of the original discrete system and show that the fluid model provides a bound for the discrete one.

We consider evolving games with finite number of players, in which each player interacts with other randomly selected players. The types and actions of each player in an interaction together determine the instantaneous payoff for all involved players. They also determine the rate of transition between type-actions. We provide a rigorous derivation of the asymptotic behavior of this system as the size of the population grows. We show that the large population asymptotic of the microscopic model is equivalent to a macroscopic evolutionary game in which a local interaction is described by a single player against an evolving population profile. We derive various classes of evolutionary game dynamics. We apply these results to spatial random access games in wireless networks.

This paper describes a multiuser power allocation strategy for fixed constellation over parallel Gaussian channels (e.g. OFDM systems). The criterion under consideration is mutual information, given arbitrary input distributions over users and over subcarriers. The algorithm achieves with very low complexity the multi-user aggregate sum mutual information upper bound. The algorithm is based on an iterative Mercury/waterfilling procedure. Moreover, we extend the framework to a decentralized scenario using a linear approximation of the MMSE function. We show, in particular that each user can, under certain assumptions, independently determine the power allocation without knowing the channel information of other users. Simulation results validate the theoretical claims.

We study power control in optimization and game frameworks. In the optimization framework there is a single decision maker who assigns network resources and in the game framework users share the network resources according to Nash equilibrium. The solution of these problems is based on so-called water-filling technique, which in turn uses bisection method for solution of non-linear equations for Lagrange multipliers. Here we provide a closed form solution to the water-filling problem, which allows us to solve it in a finite number of operations. Also, we produce a closed form solution for the Nash equilibrium in symmetric Gaussian interference game with an arbitrary number of users. Even though the game is symmetric, there is an intrinsic hierarchical structure induced by the quantity of the resources available to the users. We use this hierarchical structure to perform a successive reduction of the game. In addition to its mathematical beauty, the explicit solution allows one to study limiting cases when the crosstalk coefficient is either small or large. We provide an alternative simple proof of the convergence of the iterative water filling algorithm. Furthermore, it turns out that the convergence of Iterative water filling algorithm slows down when the crosstalk coefficient is large. Using the closed form solution, we can avoid this problem. Finally, we compare the non-cooperative approach with the cooperative approach and show that the non-cooperative approach results in a more fair resource distribution.

A decision maker (Actor) has to decide which of several available resources to use in the presence of an adversary (Controller) that can prevent the Actor of receiving information on the state of some of the resources. The Controller has a limitation on the amount of information it can conceal. We formulate this problem as a game and compute the most harmful behavior of the Controller and the best choice of a resource for the Actor. We identify cases in which the exact solution is computationally intractable, and provide approximate solutions with polynomial complexity.

No abstract available.

In this paper, we study the joint design of uplink and downlink resources in OFDMA-based systems. We first analyze the interactions between uplink and downlink, due essentially to the usage of time division duplexing (TDD) and the TCP ACKs. This analysis is based on analytical models for interference and throughputs that we develop for both directions. We next study the capacity of the system using a Markovian analysis and matrix geometric solutions. Our performance analysis study allows us to determine the optimal proportion of resources that has to be allocated to the uplink so as to minimize blocking. In addition to that, we show that an admission control policy reserving some uplink resources to TCP ACKs may improve the overall capacity of the system.

In this contribution, the performance of a multiuser system is analyzed in the context of frequency selective fading channels. Using game theoretic tools, a useful framework is provided in order to determine the optimal power allocation when users know only their own channel (while perfect channel state information is assumed at the base station). This scenario illustrates the case of decentralized schemes, where limited information on the network is available at the terminal. Various receivers are considered, namely the matched filter, the MMSE filter and the optimum filter. The goal of this paper is to extend previous work, and to derive simple expressions for the non-cooperative Nash equilibrium as the number of mobiles becomes large and the spreading length increases. To that end two asymptotic methodologies are combined. The first is asymptotic random matrix theory which allows us to obtain explicit expressions of the impact of all other mobiles on any given tagged mobile. The second is the theory of non-atomic games which computes good approximations of the Nash equilibrium as the number of mobiles grows.

We study in this paper a noncooperative approach for sharing resources of a common pool among users, wherein each user strives to maximize its own utility. The optimality notion is then a Nash equilibrium. First, we present a general framework of systems wherein a Nash equilibrium is Pareto inefficient, which are similar to the 'tragedy of the commons' in economics. As examples that fit in the above framework, we consider noncooperative flow-control problems in communication networks where each user decides its throughput to optimize its own utility. As such a utility, we first consider the power which is defined as the throughput divided by the expected end-to-end packet delay, and then consider another utility of additive costs. For both utilities, we establish the non-efficiency of the Nash equilibria.

A common feature of congestion control protocols is the presence of information packets used to signal congestion. We address here the question of how frequently such protocols need to generate information packets in order to optimize their performance. Through a number of congestion control models, we identify and quantify different types of effects of the frequency of generating information packets. We consider both TCP-type protocols, in which controlling the frequency of information packets is done through static or dynamic delayed ACK options, as well as ATM type flow control, where the optimal time spacing between the generation of network management packets is computed. We show how the spacing between information packets influences the throughput and the stability of the system.

We consider an uplink power control problem where each mobile wishes to maximize its throughput (which depends on the transmission powers of all mobiles) but has a constraint on the average power consumption. A finite number of power levels are available to each mobile. The decision of a mobile to select a particular power level may depend on its channel state. We consider two frameworks concerning the state information of the channels of other mobiles: (i) the case of full state information and (ii) the case of local state information. In each of the two frameworks, we consider both cooperative as well as non-cooperative power control. We manage to characterize the structure of equilibria policies and, more generally, of best-response policies in the non-cooperative case. We present an algorithm to compute equilibria policies in the case of two non-cooperative players. Finally, we study the case where a malicious mobile, which also has average power constraints, tries to jam the communication of the other mobile. Our results are illustrated and validated through various numerical examples.

We consider non-cooperative mobiles, each faced with the problem of which subset of WLANs access points (APs) to connect and multihome to, and how to split its traffic among them. Considering the many users regime, we obtain a potential game model and study its equilibrium. We obtain pricing for which the total throughput is maximized at equilibrium and study the convergence to equilibrium under various evolutionary dynamics. We also study the case where the Internet service provider (ISP) could charge prices greater than that of the cost price mechanism and show that even in this case multihoming is desirable.

Modeling TCP is fundamental for understanding Internet behavior. The reason is that TCP is responsible for carrying a huge quota of the Internet traffic. During last decade many analytical models have attempted to capture dynamics and steady-state behavior of standard TCP congestion control algorithms. In particular, models proposed in literature have been mainly focused on finding relationships among the throughput achieved by a TCP flow, the segment loss probability, and the round trip time (RTT) of the connection, which the flow goes through. Recently, Westwood+ TCP algorithm has been proposed to improve the performance of classic New Reno TCP, especially over paths characterized by high bandwidth-delay products. In this paper, we develop an analytic model for the throughput achieved by Westwood+ TCP congestion control algorithm when in the presence of paths with time-varying RTT. The proposed model has been validated by using the ns-2 simulator and Internet-like scenarios. Validation results have shown that this model provides relative prediction errors smaller than 10%. Moreover, it has been shown that a similar accuracy is achieved by analogous models proposed for New Reno TCP.

We found a formula for aggregate throughput of arbitrarily given number of competing additive-increase, multiplicative-decrease connections (TCP congestion avoidance mode) for a bottleneck, under assumption that loss events over connections are non synchronized. The formula captures throughput-deficiency due to the additive-increase and multiplicative-decrease adaptation. The formula suggests that already a few connections are sufficient to almost entirely eliminate this throughput deficiency. The result reveals the aggregate throughput insensitivity on the way losses are assigned over competing connections over time, for any given number of competing connections. The result is validated by simulations and Internet measurements. The latter validates the model in cases when analysis assumptions are met, but also encounters cases of the throughput deficiency due to synchronization of loss events and the receiver window constraint. The results would inform on the throughput efficiency of parallel TCP transfers, an approach used widely for bulk data transfer.

We consider a mobile ad hoc network consisting of three types of nodes: source, destination, and relay nodes. All the nodes are moving over a bounded region with possibly different mobility patterns. We introduce and study the notion of relay throughput, i.e. the maximum rate at which a node can relay data from the source to the destination. Our findings include the results that the relay throughput depends on the node mobility pattern only via its (stationary) node position distribution and that a node mobility pattern that results in a uniform steady-state distribution for all nodes achieves the lowest relay throughput. Random Waypoint and Random Direction mobility models in both one and in two dimensions are studied and approximate simple expressions for the relay throughput are provided. Finally, the behavior of the relay buffer occupancy is examined for the one-dimensional Random Walk, and an explicit form of its mean value is provided in the heavy-traffic case.

Abstract — In many cases, a mobile user has the option of connecting to one of several IEEE 802.11 access points (APs), each using an independent channel. User throughput in each AP is determined by the number of other users as well as the frame size and physical rate being used. We consider the scenario where users could multihome, i.e., split their traffic amongst all the available APs, based on the throughput they obtain and the price charged. Thus, they are involved in a non-cooperative game against each other. We convert the problem into a fluid model and show that under a pricing scheme, which we call the cost price mechanism, the total system throughput is maximized, i.e., the system suffers no loss of efficiency due to selfish dynamics. We also study the case where the Internet Service Provider (ISP) could charge prices greater than that of the cost price mechanism. We show that even in this case multihoming outperforms unihoming, both in terms of throughput as well as profit to the ISP. I.

Considered is a mobile ad hoc network consisting of three types of nodes (source, destination and relay nodes) and using the two-hop relay routing protocol. Packets at relay nodes are assumed to have a limited lifetime in the network. All nodes are moving inside a bounded region according to some random mobility model. Both closed-form expressions, and asymptotic results are provided for the packet delivery delay and the energy needed to transmit a packet from the source to its destination. Our model is validated through simulations for two mobility models (random waypoint and random direction mobility models), numerical results for the two-hop relay protocols are reported, and the performance of the two-hop routing and of the epidemic routing protocols are compared.

To this day, traffic in cellular networks is still mainly real-time. However, with the deployment of new technologies, such as HDR (High Date Rate) and HSDPA (High Speed Downlink Packet Access), this situation is bound to evolve rapidly and elastic traffic will significantly increase. These novel technologies implement opportunistic scheduling, taking advantage of the delay-tolerance of elastic traffic, to augment the global capacity of the system. Previous work has shown that "Proportional Fair" (PF) is an opportunistic scheduler that provides a good compromise between fairness and efficiency. Nevertheless, the hypotheses according to which these results are obtained are not always valid in real environments. In this paper, we propose a modified version of PF that not only introduces flexibility in sharing resources between active users but also allows for a fair allocation of resources in realistic environments.

The inherent nature of the physical setup and transmission mechanism in wireless ad hoc networks with random channel access, results in correlation between the link metrics of adjacent links, when considering path optimization problems. We identify a special structure inherent to the solution of Dynamic Programming (DP) problem arising in such an optimization over paths. According to this structure, the optimal policy tries to equalize the link metrics of adjacent links in a multi-hop route. We validate this structural property with simulations.

In a dense multi-hop network of mobile nodes capable of applying adaptive power control, we consider the problem of finding the optimal hop distance that maximizes a certain throughput measure in bit-metres/sec, subject to average network power constraints. The mobility of nodes is restricted to a circular periphery area centered at the nominal location of nodes. We incorporate only randomly varying path-loss characteristics of channel gain due to the random motion of nodes, excluding any multi-path fading or shadowing effects. Computation of the throughput metric in such a scenario leads us to compute the probability density function of random distance between points in two circles. Using numerical analysis we discover that choosing the nearest node as next hop is not always optimal. Optimal throughput performance is also attained at non-trivial hop distances depending on the available average network power.

In this contribution, the performance of an uplink CDMA system with random spreading and multi-cell interference is analyzed. A useful framework is provided in order to determine the base station coverage for wireless flat fading channels with very dense networks (in the number of users per meter) considering different receiver structures at the base station, namely the matched filter, the Wiener filter and the optimum filter. Using asymptotic arguments, analytical expressions of the spectral efficiency are obtained and provide a simple expression of the network capacity based only on a few meaningful parameters.

In this paper, we propose and analyze novel and efficient cross-layer designs involving joint optimization of physical, link, and TCP layers in wireless. Particularly, we investigate the design of symbol mapping diversity (SMD) schemes using M-QAM at the physical layer for optimal goodput performance at the TCP layer. We present the design and TCP goodput analysis of two SMD schemes, one applying SMD at the TCP packet level, termed as full packet SMD (FP SMD), and the other applying SMD at the link layer (LL) packet level, termed as LL ARQ SMD. We show that although the LL ARQ SMD scheme offers good TCP goodput at high SNR, it performs poorer compared to the FP SMD scheme at low SNR because of increased delays incurred due to increased LL retransmissions at low SNR. We therefore propose and analyze a hybrid SMD scheme which adaptively switches modes (between LL ARQ SMD and FP SMD) based on measured LL packet error rate. We show that the hybrid SMD scheme combines the best TCP performance of both LL ARQ SMD and FP SMD under varying channel conditions.

This paper presents an algorithm for resource allocation in satellite networks. It deals with planning a time/frequency plan for a set of terminals with a known geometric configuration under interference constraints. Our objective is to maximize the system throughput while guaranteeing that the different types of demands are satisfied, each type using a different amount of bandwidth. The proposed algorithm relies on two main techniques. The first generates admissible configurations for the interference constraints, whereas the second uses linear and integer programming with column generation. The obtained solution estimates a possible allocation plan with optimality guarantees, and highlights the frequency interferences which degrade the construction of good solutions.

The purpose of this paper is to investigate some performance measures of the discrete time infinite server queue under a general arrival process. We assume, more precisely, that at each time unit a batch with a random size may arrive, where the sequence of batch sizes need not be i.i.d. All we request is that it would be stationary ergodic and that the service duration has a phase type distribution. Our goal is to obtain explicit expressions for the first two moments of number of customers in steady state. We obtain this by computing the first two moments of some generic stochastic recursive equations that our system satisfies. We then show that this class of recursive equations allow to solve not only the G/PH//spl infin/ queue but also a network of such queues. We finally investigate the process of residual activity time in a G/G//spl infin/ queue under general stationary ergodic assumptions, obtain the unique stationary solution and establish coupling convergence to it from any initial state.

We study an adaptive window protocol (AWP) with a general increase and decrease profile in the presence of window dependent random losses. We derive a steady-state Kolmogorov equation and obtain its solution in analytic form. We obtain some stochastic ordering relations for a protocol with different bounds on window. A closed form necessary and sufficient stability condition using the stochastic ordering for the window process is established. Finally, we apply the general results to particular TCP versions such as NEW Reno TCP, scalable TCP and Highspeed TCP. We observe that Highspeed TCP can be used to approximate almost any kind of window behavior by varying only one design parameter.

The multiplicative increase multiplicative decrease (MIMD) congestion control algorithm in the form of scalable TCP has been proposed for high speed networks. We study fairness among sessions sharing a common bottleneck link, where one or more sessions use the MIMD algorithm. Losses, or congestion signals, occur when the capacity is reached but could also be initiated before that. Both synchronous as well as asynchronous losses are considered. In the asynchronous case, only one session suffers a loss at a loss instant. Two models are then considered to determine which source looses a packet: a rate dependent model in which the packet loss probability of a session is proportional to its rate at the congestion instant, and the independent loss rate model. We first study how two MIMD sessions share the capacity in the presence of general combinations of synchronous and asynchronous losses. We show that, in the presence of rate dependent losses, the capacity is fairly shared whereas rate independent losses provide high unfairness. We then study inter protocol fairness: how the capacity is shared in the presence of synchronous losses among sessions some of which use additive increase multiplicative decrease (AIMD) protocols whereas the others use MIMD protocols.

This paper analyzes a single server queuing system in which service is alternated between two queues and the server requires a (finite) switchover time to switch from one queue to the other. The distinction from classical results is that the sequence of switchover times from each of the queues need not be i.i.d. nor independent from each other; each sequence is merely required to form a stationary ergodic sequence. With the help of stochastic recursive equations explicit expressions are derived for a number of performance measures, most notably for the average delay of a customer and the average queue lengths under different service disciplines. With these expressions a comparison is made between the service disciplines and the influence of correlation is studied. Finally, through a number of examples it is shown that the correlation can significantly increase the mean delay and the average queue lengths indicating that the correlation between switchover times should not be ignored. This has important implications for communication systems in which a common communication channel is shared amongst various users and where the time between consecutive data transfers is correlated (for example in ad-hoc networks).

We study a fixed point formalisation of the well known analysis of Bianchi. We provide a significant simplification and generalisation of the analysis. In this more general framework, the fixed point solution and performance measures resulting from it are studied. Uniqueness of the fixed point is established. Simple and general throughput formulas are provided. It is shown that the throughput of any flow will be bounded by the one with the smallest transmission rate. The aggregate throughput is bounded by the reciprocal of the harmonic mean of the transmission rates. In an asymptotic regime with a large number of nodes, explicit formulas for the collision probability, the aggregate attempt rate and the aggregate throughput are provided. The results from the analysis are compared with ns2 simulations, and also with an exact Markov model of the back-off process. It is shown how the saturated network analysis can be used to obtain TCP transfer throughputs in some cases.

In this paper, we present an analytical procedure for the computation of the node isolation probability in an ad hoc network in the presence of channel randomness, with applications to shadowing and fading phenomena. Such a probability coincides with the complement of the coverage probability, given that nodes are distributed according to a Poisson point process. These results are used to obtain an estimate of the connectivity features for very dense networks. For the case of superimposed lognormal shadowing and Rayleigh fading, the connectivity improvements achievable by means of diversity schemes are investigated.

In this contribution, the performance of an uplink CDMA system with orthogonal spreading is analyzed. A useful framework is provided in order to determine if synchronization of the users gives a significant performance improvement. Using asymptotic arguments, analytical expressions of the spectral efficiency for the matched filter and Successive interference cancellation matched filter are derived. The results, applied in the general case of a multipath channel, provide a simple expression of the cell capacity based only on a few meaningful parameters

We consider the vector fixed point equations arising out of the analysis of the saturation throughput of a single cell IEEE 802.11e wireless local area network with nodes that have different back-off parameters, including different Arbitration InterFrame Space (AIFS) values. We consider balanced and unbalanced solutions of the fixed point equations arising in homogeneous and nonhomogeneous networks. We are concerned, in particular, with (i) whether the fixed point is balanced within a class, and (ii) whether the fixed point is unique. Our simulations show that when multiple unbalanced fixed points exist in a homogeneous system then the time behaviour of the system demonstrates severe short term unfairness (or multistability). Implications for the use of the fixed point formulation for performance analysis are also discussed. We provide a condition for the fixed point solution to be balanced within a class, and also a condition for uniqueness. We then provide an extension of our general fixed point analysis to capture AIFS based differentiation; again a condition for uniqueness is established. An asymptotic analysis of the fixed point is provided for the case in which packets are never abandoned, and the number of nodes goes to ∞. Finally the fixed point equations are used to obtain insights into the throughput differentiation provided by different initial back-offs, persistence factors, and AIFS, for finite number of nodes, and for differentiation parameter values similar to those in the standard.

Abstract We consider competitive routing in multicast networks from a noncooperative game theoretical perspective. There areNusers sharing a network, and each has to send a quantity of packets to a different set of addressees (each address must receive the same packets). To do this the user has only to send one copy of a packet, the network making the duplications of the packets at appropriate nodes (depending on the chosen trees). The routing choice of a user is how to split its flow between different multicast trees. We present different criteria for optimization of this type of game. We treat two specific networks and establish the uniqueness of the Nash equilibrium in these networks, as well as the uniqueness of link utilization at Nash equilibria for specific cost functions in networks with general topology. We also present a result for convergence to equilibria from an initial nonequilibrium state. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(1), 22–35 2005

In this paper, we present a model for TCP/IP congestion control mechanism. The rate at which data is transmitted increases linearly in time until a packet loss is detected. At this point, the transmission rate is divided by a constant factor. Losses are generated by some exogenous random process which is assumed to be stationary ergodic. This allows us to account for any correlation and any distribution of inter-loss times. We obtain an explicit expression for the throughput of a TCP connection and bounds on the throughput when there is a limit on the window size. In addition, we study the effect of the Timeout mechanism on the throughput. A set of experiments is conducted over the real Internet and a comparison is provided with other models that make simple assumptions on the inter-loss time process. The comparison shows that our model approximates well the throughput of TCP for many distributions of inter-loss times.

The throughput of AIMD protocols in general and of TCP in particular, has been computed in many existing works by modeling the round-trip time as a constant and thus replacing the round-trip time by its expectation. There are however many scenarios in which the delays of packets vary, causing a variation of the round-trip time. Many typical scenarios occur in wireless and mobile networks. We propose in this paper an analytical model that accounts for the variability of delay, while computing the throughput of an AIMD protocol. We derive a closed-form expression for the throughput that illustrates the impact of the variability of delay. We show by analysis and simulation, that an increase in the variability of delay improves the performance of an AIMD protocol. Thus, an analytical model that only considers the average delay could underestimate the performance of an AIMD protocol in scenarios where delay is variable.

In a previous paper, BonaId and Roberts (June 2001) studied non-persistent TCP connections in transient overload conditions, under the assumption that all connections have the same round-trip times. In this paper our goal is to develop theoretical tools that will enable us to relax this assumption and obtain explicit expressions for the rate of growth of the number of connections at the system, the rate at which TCP connections leave the system, as well as the time needed for the completion of a connection. To that end, we model the system as a DPS (discriminatory processor sharing) system which we analyze under very mild assumptions on the probability distributions related to different classes of arrivals: we only assume that the arrival rates of connections exist, and that the amount of information transmitted during a connection of a given type forms a stationary ergodic sequence. We then proceed to obtain explicit expressions for the growth rate of the number of connections at the DPS system for several specific probability distributions. We check through simulations the applicability of our queueing results for modeling TCP connections sharing a bottleneck.

We consider a random access network in which the nodes need to optimize their channel access rates. The nodes are assumed to be rational and interested in their performance seen as a transmitter as well as a receiver. By casting this problem as a non-cooperative game, we derive conditions for the Nash equilibrium. We also show the existence of a Nash equilibrium when the nodes are constrained by their battery power (for this case, the constraints on the access rates of the nodes become coupled). For the special case where all nodes are each other's neighbors, we find that the equilibrium is given by the solution of a system of linear equations. An adaptive distributed scheme is then proposed for learning this equilibrium and its convergence is studied numerically.

In this paper we analyse a feedback system consisting of a finite buffer fluid queue and a responsive source. The source alternates between silence periods and active periods. At random epochs of times the source becomes ready to send a burst of fluid. The length of the bursts (length of the active periods) are independent and identically distributed with some general distribution. The queue employs a threshold discarding policy in the sense that only those bursts at whose commencement epoch (the instant at which the source is ready to send), the workload (i.e., the amount of fluid in the buffer) is less than some preset threshold are accepted. If the burst is rejected then the source backs off from sending. Using techniques from Volterra integral equations we obtain an explicit characterization of the queue length distribution at commencement epochs of bursts from which we obtain an explicit characterization of the goodput ratio associated with such a feedback system. For the particular case of exponential distribution of on-periods we are able to obtain explicit closed form expression for the goodput ratio. Our explicit characterizations shall be quite helpful in studying the sensitivity of goodput ratio to different parameters, in selecting optimal discarding threshold etc. which will further provide useful "engineering" guidelines for better network designing.

We propose two novel on-line estimation algorithms to determine the size of a dynamic multicast group. We first use a Wiener filter to derive an optimal estimator for the membership size of the session in case the join process is Poisson and the lifetime of participants is distributed exponentially. We next develop the best first-order linear filter from which we derive an estimator that holds for any lifetime distribution. We apply this approach to the case where the lifetime distribution is hyperexponential. Both estimators hold under any traffic regime. Applying both estimators on real traces corresponding to video sessions, we find that both schemes behave well, one of which performs slightly better than the other in some cases. We further provide guidelines on how to tune the parameters involved in both schemes in order to achieve high quality estimation while simultaneously avoiding feedback implosion.

Traditional definitions of capacity of CDMA networks are either related to the number of calls they can handle or to the arrival rate that guarantees that the rejection rate is below a given fraction (Erlang capacity). We extend the latter definition to other quality of service (QoS). We consider best-effort (BE) traffic sharing the network resources with real-time (RT) applications. BE applications can adapt their instantaneous transmission rate to the available one and thus need not be subject to admission control or outages. Their meaningful QoS is the average delay. The delay aware capacity is defined as the arrival rate of BE calls that the system can handle such that their expected delay is bounded by a given constant. We compute both the blocking probability of the RT traffic having an adaptive grade of service (GoS) as well as the expected delay of the BE traffic for an uplink multicell WCDMA system. This yields the Erlang capacity for former and the delay capacity for the latter.

In third generation mobile networks, transmission rates can be assigned to both real time and non real time applications. We address in this paper the question of how to allocate transmission rates in a manner that is both optimal and fair. As optimality criterion we use the Pareto optimality notion, and as fairness criterion we use a general concept of which the max-min fairness (which is the standardized fairness concept in ATM networks) and the proportional fairness (which characterizes fairness obtained by transport protocols for the Internet) are special cases. We formulate the fair allocation problems as optimization problems and propose an approximating solution.

We consider in this paper packets which arrive according to a Poisson process into a finite queue. A group of consecutive packets forms a frame (or a message) and one then considers not only the quality of service (QoS) of a single packet but also that of the whole message. In order to improve the required QoS, either on the frame loss probabilities or on the delay, discarding mechanisms have to be used. We analyze in this paper the performance of the early message discard (EMD) policy at the buffer, which consists of (1) rejecting an entire message if upon the arrival of the first packet of the message, the buffer occupancy exceeds a threshold K, and (2) if a packet is lost, then all subsequent arrivals that belong to the same message are discarded.

We propose an efficient on-line estimation algorithm for determining the size of a dynamic multicast group. By using diffusion approximation and a Kalman filter, we derive an estimator that minimizes the mean square of the estimation error. As opposed to previous studies, where the size of the multicast group is supposed to be fixed throughout the estimation procedure, we consider a dynamic estimation scheme that updates the estimation at every observation step. The robustness of our estimator to violation of the assumptions under which it has been derived is addressed via simulations. Further validations of our approach are carried out on real audio traces.

We present an analytical model for the calculation of network load and drop probabilities in a TCP/IP network with general topology. First we formulate our model as a nonlinear complementarity problem. Then we transform the model into two equivalent formulations: fixed point formulation and nonlinear programming formulation. These equivalent formulations provide efficient computational procedures for the solution of our model. Furthermore, with the help of the fixed point formulation we are able to prove the existence of a solution. Our model has the main advantage of not requiring the pre-definition of bottleneck links. The model also takes into account the receiver congestion window limitation. Our approach can be used for TCP/IP networks with drop tail buggers as well as for TCP/IP networks with active queue management buggers. We solve the problem for some network examples and we show how the distribution of load varies with network parameters. The distribution of load is sometimes counter-intuitive which cannot be detected by other models making prior assumptions on the locations of bottlenecks.

A message (or a frame) is a group of consecutive packets (or cells in ATM terminology). Often a loss of one packet from the message can result in the loss of the whole message. Selective message discarding policies have been proposed to achieve the twin goal of increased goodput and reduced network congestion by discarding the packets which do not belong to (or have potential of not belonging to) good messages. In this paper we provide a fluid analysis of early message discard. We obtain approximations for performance metrics which are valid for heavy traffic conditions. In particular, we obtain exact expressions for the distribution of the stationary workload process and the fluid goodput ratio. Our analytical results will be quite helpful in selecting an optimal discarding threshold, in studying the sensitivity of goodput ratio to different parameters and also in problems related to buffer and/or capacity dimensioning to achieve a desired quality of service.

In this paper we compute the uplink capacity of power-control CDMA mobile networks with an idealized power control, that contain best-effort type applications, i.e. applications whose transmission rate can be controlled. An arriving best-effort call is assumed to have a fixed amount of traffic to send, so the transmission rate assigned to it determines the duration of the call. We allow for multi-services (so that mobile stations have different quality of service requirements). Unlike some previous published work where soft blocking was considered (and the system was thus allowed to operate beyond capacity), we assume that a call admission mechanism is implemented in order to prevent a new call to arrive when the system is already saturated. This guarantees the quality of service of ongoing calls. Our first result is that slowing the transmission rates in the case of a single cell with homogeneous quality of service characteristics increases capacity. This suggests that there is a limit capacity that can be approached when slowing down the transmission rates. We identify this limit and show that it has the following property: as long as the arrival rate of information is below some level, blocking probability can become arbitrarily small by sufficiently slowing down the transmission rates. We then extend the results to the general heterogeneous and multi-cell case.

We study in this paper a TCP-like linear-increase multiplicative-decrease flow control mechanism. We consider congestion signals that arrive in batches according to a Poisson process. We focus on the case when the transmission rate cannot exceed a certain maximum value. We write the Kolmogorov equations and we use Laplace transforms to calculate the distribution of the transmission rate in the steady state as well as its moments. Our model is particularly useful to study the behavior of TCP, the congestion control mechanism in the Internet. By a simple transformation, the problem can be reformulated in terms of an equivalent M/G/1 queue, where the transmission rate in the original model corresponds to the workload in the 'dual' queue. The service times in the queueing model are not i.i.d., and they depend on the workload in the system.

In interactive voice applications, FEC schemes are necessary for the recovery from packet losses. These schemes need to be simple with a light coding and decoding overhead in order to not impact the interactivity. The objective of this paper is to study a well known simple FEC scheme, in which for every packet n, some redundant information is added in some subsequent packet n+/spl phi/. If packet n is lost, it will be reconstructed in case packet n+/spl phi/ is well received. The quality of the reconstructed copy of packet n will depend on the amount of information on packet n we add to packet n+/spl phi/. We propose a detailed queueing analysis based on a ballot theorem and obtain simple expressions for the audio quality as a function of the amount of redundancy and its relative position to the original information. The analysis shows that this FEC scheme does not scale well and that the quality will deteriorate for any amount of FEC and for any offset /spl phi/.

In this paper, we consider call admission control of multiple classes without waiting room. We use event-based dynamic programming for our model. We show that sometimes the customer classes can be ordered: if it is optimal to accept a class, then to accept a more profitable class is optimal too. We demonstrate submodularity of the minimum cost for the 2-classes problem and establish some properties of optimal policies. Then we formulate a fluid model that allows us to study the optimal control for the large-capacity case. We show that in the case of same service time distributions, the control problem can be reduced to a model with a one-dimensional (1-D) state space, and a trunk reservation policy is optimal. We present numerical examples that validate our results.

Polling schemes are an important class of medium access control (MAC) protocols for wireless local area networks (WLANs). A major drawback of these schemes is their inefficiency when only a small number of mobile stations have packets to transmit. This inefficiency is due to the polling of mobile stations with no packets to transmit, which delays the transmissions of mobile stations with packets. In this paper, we suggest a new polling MAC which exploits the capture phenomena and enables simultaneous polling and transmissions of information packets. Mathematical analysis and simulation results show that the new MAC overcomes the above inefficiency considerably, and thus it is more efficient in the sense that it enables higher throughput and a lower access delay. For example, we show scenarios in which the average access delay is reduced by about 30% and the throughput increases by 66%-75%.

We study a class of noncooperative general topology networks shared by N users. Each user has a given flow which it has to ship from a source to a destination. We consider a class of polynomial link cost functions, adopted originally in the context of road traffic modeling, and show that these costs have appealing properties that lead to predictable and efficient network flows. In particular, we show that the Nash equilibrium is unique, and is moreover efficient, i.e., it coincides with the solution of a corresponding global optimization problem with a single user. These properties make the cost structure attractive for traffic regulation and link pricing in telecommunication networks. We finally discuss the computation of the equilibrium in the special case of the affine cost structure for a topology of parallel links.

We present a technique for identifying repetitive information transfers and use it to analyze the redundancy of network traffic. Our insight is that dynamic content, streaming media and other traffic that is not caught by today's Web caches is nonetheless likely to derive from similar information. We have therefore adapted similarity detection techniques to the problem of designing a system to eliminate redundant transfers. We identify repeated byte ranges between packets to avoid retransmitting the redundant data.

No abstract available.

No abstract available.

The objective pursued in this paper is two-fold. The first part addresses the following combinatorial problem: is it possible to construct an infinite sequence over n letters where each letter is distributed as “evenly” as possible and appears with a given rate? The second objective of the paper is to use this construction in the framework of optimal routing in queuing networks. We show under rather general assumptions that the optimal deterministic routing in stochastic event graphs is such a sequence.

In this paper we consider two types of sessions: Guaranteed Performance (GP) and point-to-multi point Best Effort (BE). The existence of different types of users sharing the same resource raises the need for a Call Admission Control (CAC) which will enable an efficient use of the shared network. As is commonly done in todays telecommunications network, CAC is assumed to be imposed only on the GP session. We analyse the effect of bandwidth reservation for BE sessions on the performance of the BE sessions (in terms of the expected delay) and of the GP sessions (in terms of their rejection probabilities). Our analysis is based on a matrix-geometric approach.

We investigate the performance of the EFCI-based (explicit forward congestion indication) and ER-based (explicit rate; EPRCA in particular) algorithms for the rate-based flow control of the ABR (available bit rate) traffic in an ATM network. We consider the case of multiple switches in tandem. We present several definitions of a bottleneck, and provide conditions that determine which queue is the bottleneck. We show that it is not necessarily the queue with the slowest transmission rate that is the first to notify congestion, and that queues with faster transmission rates can increase considerably the congestion. Moreover, a queue may build up in a faster node before it builds in a slower one. We derive analytic formulas for the maximum queue length. We compare our results to those obtained by approximating a network by a simpler one, containing only the bottleneck switch. We show that the maximum queue lengths under the approximating approach may largely underestimate the ones obtained in the real network.

The paper considers the design of explicit rate-based flow control for available bit rate (ABR) sources in an ATM network. The goal is to share the available capacity "fairly" among many sources while maintaining queue length at a bottleneck node at a desired level. This problem is formulated as a stochastic control problem, and in this framework rate-control mechanisms are developed, which stabilize the queue length even though different sources may have different round-trip delays to the bottleneck node. Various robustness properties of the solution are illustrated through simulation experiments.

Modern communication networks evolve towards integration of guaranteed-performance and best-effort service types. The co-existence of these two service types offers substantial benefits, such as resource sharing between service classes, and the ability of the user to select an appropriate service class according to its individual requirements and preferences. Notwithstanding, such interaction potentially complicates the system behavior, and gives rise to subtle optimization questions, which need to be explored and understood in order to allow efficient network operation. In this paper we address some essential performance and flow control issues associated with such service interactions. We propose a fluid model for session flow, which captures the two interaction mechanisms of resource sharing. In particular, our model incorporates the possibility of session migration, where sessions may shift from best effort to guaranteed performance service due to congestion experienced in the former. Within this model, we analyze the system performance and characterize its steady state behavior. We further show that under certain conditions the system exhibits bistable behavior, where some transient congestion may stir the system from a stable and efficient operating point to an inefficient and congested one, which might persist indefinitely. For the latter case, we propose a call admission control scheme which prevents the system from getting trapped in a congested-type equilibrium, while not interfering with normal system operation.

The purpose of this paper is to obtain the distribution of the number of lost packets within a sequence of n consecutive packet arrivals into a finite buffer M/M/1 queue. We obtain explicit expressions for the multidimensional generating function of these probabilities based on a recursive scheme introduced by Cidon et al. (1993). We then analyze the loss probabilities of a whole message, and analyze the effect of adding redundant packets. We show that in both heavy traffic as well as in light traffic conditions, adding redundant packets results in decreasing the message loss probabilities.

Flow and congestion control allow the users of a telecommunication network to regulate the traffic that they send into the network in accordance with the quality of service that they require. Flow control may be performed by the network, as is the case in asynchronous transfer mode (ATM) networks (the available bit rate (ABR) transfer capacity), or by the users themselves, as is the case in the Internet [transmission control protocol/Internet protocol (TCP/IP)]. We study both situations using optimal control and dynamic game techniques. The first situation leads to the formulation of a dynamic team problem, while the second one leads to a dynamic noncooperative game, for which we establish the existence and uniqueness of a linear Nash equilibrium and obtain a characterization of the corresponding equilibrium policies along with the performance costs. We further show that when the users update their policies in a greedy manner, not knowing a priori the utilities of the other players, the sequence of policies thus generated converges to the Nash equilibrium. Finally, we study an extension of the model that accommodates multiple traffic types for each user, with the switching from one type of traffic to another being governed by a Markov jump process. Presentation of some numerical results complements this study.

The best known congestion control mechanism for the TCP/IP protocols, is that proposed by Van Jacobson (1988) dubbed Tahoe. Revised two years after (Van Jacobson, 1990), by including fast recovery and fast retransmit (Stevens, 1994), the new version called Reno achieves more bandwidth utilization and retransmits less data than its predecessor. However its method of predicting the available bandwidth by provoking losses, is the main source of large averages and variances of rtt (round trip time) and also of aggressiveness (network saturation). Brakmo and Peterson (1995) proposed a new congestion avoidance algorithm dubbed Vegas based on some modifications to the source behavior of Reno. In this paper we use an analytic fluid approach in order to analyze the different features of both Vegas and Reno. We then use simulations to confirm our analytic results. When the available bandwidth is high, our results confirm the claims of Brakmo and Peterson (1995) and An et al. (1995); indeed Vegas can retransmit less than one-fifth as much data as Reno does, so that the higher the available bandwidth is, the more efficient Vegas is. However, under heavy congestion Vegas behaves like Reno and does not manage to make efficient use of its new mechanism for detection of congestion. The analytic results that we obtain are the evolution of the window size, round trip times and their averages, and the average throughput.

In polling systems that have been studied in the literature, one usually asserts independent Poisson arrivals. This assumption is, however, unrealistic when dealing with many applications, e.g., local area networks (LANs) using token-ring protocols. The arrival processes there may be quite irregular, highly bursty, and correlated. We use the new approach for modeling such arrival streams proposed by Cruz (1991), to obtain strict upper bounds on several performance measures. It is based on characterizing the inputs by bounds on the average arrival rate and the burstiness, and is especially useful in describing the arrival streams that are filtered (policed) by leaky buckets. We first obtain bounds for the gated, exhaustive, and globally-gated service disciplines, and then consider timed token rings (such as the FDDI). The results for the first three disciplines improve the general bounds obtained by Altman, Foss, Riehl and Stidham (see Proceedings of the 14th International Teletraffic Congress, France, p.811-20, June 1994). We further obtain improved exponential bounds of the type introduced by Chang (see IEEE Trans. Automat. Contr., vol.34, no.5, p.913-31, 1994), and Yaron and Sidi (see ibid., vol.1, no.3, p.372-85, 1993) for the globally-gated discipline.

We analyze the distribution of the delay of messages in an infinite capacity M/M/1 queue. A message is composed of n packets, and the arrival of the packets to the queue is Poisson. Our calculations are based on recursive schemes. We obtain explicit expressions for the Laplace-Stieltjes transform (LST) of the delays, which enables to obtain exact expressions for the moments of the delay in a complexity smaller than the one obtained by using recursive schemes. We repeat the above calculations for the case that messages are dispersed, i.e. packets from several sources arrive to an M/M/1 queue and are served according to the FIFO discipline. Hence, several packets of other messages may arrive between consecutive packets of a given message.

The purpose in the paper is to obtain the distribution of the number of lost packets within a sequence of n consecutive packet arrivals into a finite buffer M/M/1 queue. The authors obtain explicit expressions for the multi-dimensional generating function of these probabilities based on a recursive scheme introduced by Cidon et al. (1993)They then analyze the loss probabilities of a whole message, and analyze the effect of adding redundant packets. They show that in both heavy traffic as well as in light traffic conditions, adding redundant packets results in decreasing the message loss probabilities.>

The theory of Markov Control Model with Perfect State Information (MCM-PSI) requires that the current state of the system is known to the decision maker at decision instants. Otherwise, one speaks of Markov Control Model with Imperfect State Information (MCM-ISI). In this article, we introduce a new class of MCM-ISI, where the information on the state of the system is delayed. Such an information structure is encountered, for instance, in high-speed data networks.