Rising energy costs and the push for green computing have inspired a lot of research effort towards energy efficient computing. Incorporating low energy sleep states in server farms is one of the proposed solutions. This paper studies the trade-off between energy and performance that is inherent in such solutions using the popular cost metric Energy-Response-time-Weighted-Sum (ERWS). We apply the Markov Decision Process (MDP) theory to the task assignment problem, and derive a near-optimal dynamic task assignment policy for minimizing the ERWS cost metric. Furthermore, we consider a performance constrained energy minimization problem, and provide an algorithm that builds a dynamic task assignment policy by choosing the right energy weight value for the ERWS cost metric. We also show that the resulting task assignment policy behaves like a modified version of the Join the Shortest Queue (JSQ), having a near-optimal performance by minimizing energy consumption while still obeying response time constraint.

We explore the performance of different resource allocation schemes for transferring elastic traffic in a cellular network that is either overlaid or underlaid with D2D traffic. To this end, we model a single cell during uplink transmissions and jointly consider the presence of a randomly varying number of D2D and cellular users in the system. We use different processor sharing queueing models to characterize the performance of the overlaying and underlaying schemes and measure the performance as the mean flow level delay. In the overlaying approach, depending on the load a certain fraction of the radio resources is reserved for the D2D traffic and the cellular traffic, and hence there is no interference between the D2D and cellular users. In the underlaying approach, the D2D users are allowed to opportunistically transmit unless being interfered by a cellular user nearby. Our numerical studies reveal that the underlaying D2D traffic scheme provides a good performance compared to other methods, especially if the interference range of a cellular user is small compared with the cell dimensions. Moreover, the so-called dynamic overlay method we propose appears to perform better than the static overlay scheme.

We study the cell selection techniques for M2M traffic between an LTE macrocell and WLAN femtocells in a heterogeneous network deployment scenario. With the dense deployment of femtocells (operating in WLAN), M2M traffic can primarily be served by them while the macrocell (operating in LTE) can be used by the machines in case of congestion in their own femtocell. We study various load balancing strategies that aid the machines to select a proper cell in such a multi-RAT heterogeneous network deployment scenario so that the access delay for the M2M traffic is minimized. In particular, we derive the optimal static policy of choosing between the WLAN femtocell and the LTE macrocell. In addition, we develop dynamic policies based on the information about the arrivals and the number of backlogged users, and compare their performance against each other and with the optimal static policy. Our results indicate that the potential gains from the dynamic policies can be significant. Moreover, simple backlog-based heuristics perform close to or better than the optimal static policy.

We consider the optimal opportunistic scheduling problem for downlink data traffic in a wireless cell with time-varying channels. The scheduler itself operates in a very fast timescale of milliseconds, but the objective function is related to minimizing the holding costs in a much longer timescale, at the so-called flow level. The Whittle index approach is a powerful tool in this context, since it renders the flow level optimization problem with heterogeneous users tractable. Until now, this approach has been applied to the opportunistic scheduling problem to generate non-anticipating index policies that may depend on the amount of attained service but do not utilize the exact size information. In this paper, we produce a size-aware (i.e., anticipating) index policy by applying the Whittle index approach in a novel way. By a numerical study based on simulations, we demonstrate that the resulting size-aware index policy systematically improves performance. As a side result, we show that the opportunistic scheduling problem is indexable when the file sizes follow the Pascal distribution, and we derive the corresponding Whittle index, which generalizes earlier results.

In heterogeneous LTE networks, an incoming user can either join the femto or the macro base station at the random access stage. We consider a system that has a single macro base station and a number of femtocells in its coverage area. We study the problem of optimally choosing either the femto or the macro station based on the knowledge of the traffic arrival rate and the number of backlogged users in both cells. In this paper, we derive the optimal static policy of choosing the base stations that minimizes the average access delay. We also develop various dynamic policies based on the information about the arrivals and backlogged users, and compare their performance against each other and with the optimal static policy. We observe that some of these dynamic policies give very good performance, which provides a lower bound of performance. In addition, a dynamic policy that utilizes only the backlog levels, although not always as good as the optimal static policy, is robust and still stable for a wide range of arrival rates.

We consider an opportunistic content sharing system designed to store and distribute local spatio-temporal “floating” information in uncoordinated P2P fashion relying solely on the mobile nodes passing through the area of interest, referred to as the anchor zone. Nodes within the anchor zone exchange the information in opportunistic manner, i.e., whenever two nodes come within each others' transmission range. Outside the anchor zone, the nodes are free to delete the information, since it is deemed relevant only for the nodes residing inside the anchor zone. Due to the random nature of the operation, there are no guarantees, e.g., for the information availability. By means of analytical models, we show that such a system, without any supporting infrastructure, can be a viable and surprisingly reliable option for content sharing as long as a certain criterion, referred to as the criticality condition, is met. The important quantity is the average number of encounters a randomly chosen node experiences during its sojourn time in the anchor zone, which again depends on the communication range and the mobility pattern. The theoretical studies are complemented with simulation experiments with various mobility models showing good agreement with the analytical results.

Content sharing using personal web pages, blogs, or online social networks is a common means for people to maintain contact with their friends, colleagues, and acquaintances. While such means are essential to overcome distances, using infrastructure services for location-based services may not be desirable. In this paper, we analyze a fully distributed variant of an ephemeral content sharing service, solely dependent on the mobile devices in the vicinity using principles of opportunistic networking. The net result is a best effort service for floating content in which: 1) information dissemination is geographically limited; 2) the lifetime and spreading of information depends on interested nodes being available; 3) content can only be created and distributed locally; and 4) content can only be added, but not explicitly deleted. First we present our system design and summarize its analytical modeling. Then we perform extensive evaluation for a map-based mobility model in downtown Helsinki to assess the operational range for floating content, which, at the same time also validate the analytical results obtained for a more abstract model of the system.

We consider service systems where new jobs not only increase the load but also improve the service ability of such a system, cf. opportunistic scheduling gain in wireless systems. We study the optimal trade-off between the SRPT (Shortest Remaining Processing Time) discipline and opportunistic scheduling in the systems characterized by compact and symmetric capacity regions. The objective is to minimize the mean delay in a transient setting where all jobs are available at time 0 and no new jobs arrive thereafter. Our main result gives conditions under which the optimal rate vector does not depend on the sizes of the jobs as long as their order (in size) remains the same. In addition, it shows that in this case the optimal policy applies the SRPT principle serving the shortest job with the highest rate of the optimal rate vector, the second shortest with the second highest rate etc. We also give a recursive algorithm to determine both the optimal rate vector and the minimum mean delay. In some special cases, the rate vector, as well as the minimum mean delay, have even explicit expressions as demonstrated in the paper. For the general case, we derive both an upper bound and a lower bound of the minimum mean delay.

The fundamental P2P principle that downloading peers help other peers can be applied in the context of video-on-demand. This represents a demanding application combining aspects of other well-known P2P applications, i.e., live streaming and traditional file sharing. We seek to provide insight on fundamental questions about the performance and scalability of the system. A deterministic fluid model is derived that explicitly takes into account the video transfer and playback phases. The analytical results are complemented with extensive simulations from the corresponding stochastic model, as well as traces from a more realistic BitTorrent simulator.

We consider the problem of finding the maximum directed packet flow that can be sustained in an infinite wireless multihop network. This ability of the network to relay traffic is called the forwarding capacity, and the problem appears when the spatial scales corresponding to the end-to-end paths (routing) and the neighboring nodes (forwarding) are strongly separated in a massively dense network. We assume a Boolean interference model. The infinite network is approximated with a finite but large network where the node locations form a spatial Poisson process. We study two constructive approaches to tighten the lower bound for the forwarding capacity by a significant amount. In path scheduling the packets traverse the network using predefined paths that do not interfere with each other, and coordination is thus required only between the nodes of a path. In greedy maximum weight scheduling, the transmissions are scheduled greedily according to queue-length based weights of the links. In addition to a fixed transmission radius, we consider greedy maximum weight scheduling with a transmission radius adjustable up to a given maximum. We are able to produce numerical results that characterize the achievable forwarding capacity under global coordination of the transmissions, providing, e.g., concrete points of reference for practical distributed implementations.

We study the maximum forwarding capacity for the relay traffic that can be transmitted through a wireless multihop network in a single direction. The problem appears as the microscopic level problem in a dense multihop network where the routing and forwarding tasks can be considered independently (separation of scales). Ultimately, the problem of finding the maximum forwarding capacity involves solving a max-flow problem in an infinite plane with an infinite dimensional scheduling vector as an additional parameter to be optimized. In this paper, we approximate the infinite network by a finite but large network consisting of nodes distributed as a spatial Poisson process, and give the problem an LP formulation assuming a Boolean interference model. The computational complexity is further reduced by relaxing the necessary and sufficient constraints and solving the LP problem with a reduced set of necessary clique constraints. This gives a new significantly tighter upper bound on the achievable forwarding capacity compared with our previous (non-achievable) upper bound corresponding to the maximum capacity in one time slot.

HSDPA/HDR systems allow the use of sophisticated opportunistic schedulers that can utilize information on instantaneous channel conditions. On the other hand, for elastic data traffic the size of the files can be used in size-dependent scheduling methods, e.g., the well known SRPT scheduler, to minimize the flow delays. In this paper, we consider the optimal use of both size and channel information for minimizing the flow delay. We derive several heuristics which utilize both types of information. In a static setting with two flows and two rates, the optimal policy can be constructed via dynamic programming and can be compared against the policies using exact size knowledge. In the dynamic setting (stochastically arriving flows with random sizes), extensive simulations have been performed to evaluate the performance of the schedulers under heavy traffic. In the symmetric setting, the differences between the schedulers are clearly visible, while in the asymmetric setting the dynamics are more complex. The results still show that significant gains can be achieved with additionally using size information.

We study the maximal forwarding capacity of a massively dense wireless multi-hop network where a typical path consists of a vast number of hops. In such a network, the macroscopic level, corresponding to the scale of an end-to-end path, and the microscopic level, corresponding to the scale of a single hop, can be separated. At the macroscopic level the task is that of routing, while at the microscopic level the packets are forwarded based on the information received from the macroscopic level. We give a formulation for the forwarding problem and devise simulation algorithms based on an augmentation of the max-flow min-cut theorem for obtaining upper bounds for the maximal forwarding capacity. We compare the upper bounds with feasible forwarding methods and find out that the tightest bound is about three times the highest achieved performance.

We consider dimensioning of data networks. The network is modeled in a dynamic setting where elastic flows (file transfers) arrive randomly and share the bandwidth according to balanced fairness. Simple methods are derived for determining the link capacities so that given flow-level throughput requirements are satisfied. We consider two different approaches to define the throughput requirements: single constraint on average throughput in the network and separate constraint for every route. The results enable a simple characterization of the order- of-magnitude of the required capacities, which can be utilized in practical network planning and dimensioning.

In this paper we introduce a Markovian random waypoint model which allows us to create diverse mobility patterns in the given movement domain. The model allows adjusting random pause times and the momentary velocity. Furthermore, the distribution used to pick the next waypoint may depend on the current location, which allows, e.g., creation of typical routes. As an application for the Markovian random waypoint we consider modelling hotspots. There are several mechanisms which may be causing a hotspot and we present how the parameters of the proposed model can be adjusted accordingly to match the scenario in question. We further illustrate how two seemingly similar mobility patterns lead to highly different estimates of achievable performance levels. Finally, we show how the state of the MWP model can be initialised in simulations such that the node starts from the stationary state without any initial transient.

The random waypoint model (RWP) is one of the most widely used mobility models in performance analysis of ad hoc networks. We analyze the stationary spatial distribution of a node moving according to the RWP model in a given convex area. For this, we give an explicit expression, which is in the form of a one-dimensional integral giving the density up to a normalization constant. This result is also generalized to the case where the waypoints have a nonuniform distribution. As a special case, we study a modified RWP model, where the waypoints are on the perimeter. The analytical results are illustrated through numerical examples. Moreover, the analytical results are applied to study certain performance aspects of ad hoc networks, namely, connectivity and traffic load distribution.

We consider the problem of estimating blocking probabilities in a multicast loss system via simulation, applying the static Monte Carlo method with importance sampling. An approach is introduced where the original estimation problem is first decomposed into independent simpler sub-problems, each roughly corresponding to estimating the blocking probability contribution from a single link. Then we apply importance sampling to solve each sub-problem. The importance sampling distribution is the original distribution conditioned on that the state is in the blocking state region of a single link. Samples can be generated from this distribution using the so called inverse convolution method. Finally, a dynamic control algorithm is used for optimally allocating the samples between different sub-problems. The numerical results demonstrate that the variance reduction obtained with the method is remarkable, between 400 and 36000 in the considered examples.