Many businesses possess a small infrastructure that they can use for their computing tasks, but also often buy extra computing resources from clouds. Cloud vendors such as Amazon EC2 offer two types of purchase options: on-demand and spot instances. As tenants have limited budgets to satisfy their computing needs, it is crucial for them to determine how to purchase different options and utilize them (in addition to possible self-owned instances) in a cost-effective manner while respecting their response-time targets. In this paper, we propose a framework to design policies to allocate self-owned, on-demand and spot instances to arriving jobs. In particular, we propose a near-optimal policy to determine the number of self-owned instances and an optimal policy to determine the number of on-demand instances to buy and the number of spot instances to bid for at each time unit. Our policies rely on a small number of parameters and we use an online learning technique to infer their optimal values. Through numerical simulations, we show the effectiveness of our proposed policies, in particular that they achieve a cost reduction of up to 64.51 percent when spot and on-demand instances are considered and of up to 43.74 percent when self-owned instances are considered, compared to previously proposed or intuitive policies.

We study the M/D/1 queue when jobs have firm deadlines for waiting (or sojourn) time. If a deadline is not met, a job-specific deadline violation cost is incurred. We derive explicit value functions for this M/D/1 queue that enable the development of efficient cost-aware dispatching policies to parallel servers. The performance of the resulting dispatching policies is evaluated by means of simulations.

We study the Round-Robin (RR) routing to a system of parallel queues, which serve jobs according to FCFS or preemptive LCFS scheduling disciplines. The cost structure comprises two components: a service fee and a queueing delay related component. With Poisson arrivals, the inter-arrival time to each queue obeys the Erlang distribution. This allows us to study the mean and transient behavior of the queues separately. The service fee is independent of the scheduling and queueing, and we obtain the corresponding mean cost rate and value function in closed forms. With respect to queueing delay, we first derive integral expressions enabling efficient computation of the corresponding size-aware value functions. By decomposition, these yield also the value function for the whole system of m parallel queues fed by RR. Given the value function, one can carry out the first policy iteration step with arbitrary holding cost rates (e.g., delay, slowdown, etc.) yielding efficient size-, cost- and state-aware policies. Moreover, the mean waiting and sojourn times in the corresponding systems get resolved at the same time. The results are demonstrated in the numerical examples, where we compute near optimal job routing policies for sample systems.

Hop count limitation helps controlling the spread of messages as well as the protocol complexity and overhead in a distributed network. For a mobile opportunistic network, we examine how the paths between any two nodes change with increasing number of hops a message can follow. Using the all hops optimal path (AHOP) problem, we represent the total delay of a route from a source node to a destination node as additive weight and use the number of encounters as a representation of bottleneck weight. First, we construct a static (contact) graph from the meetings recorded in a human contact trace and then analyze the change in these two weights with increasing hop count. Alternatively, we aggregate all the contact events in a time interval and construct several time-aggregated graphs over which we calculate the capacity metrics. Although, we observe differences in the properties of the static and the time-aggregated graphs (e.g., higher connectivity and average degree in static graph), our analysis shows that second hop brings most of the benefits of multi-hop routing for the studied networks. However, the optimal paths —path that provides the most desirable bottleneck/additive weight— are achieved at further hops, e.g, hop count ≈ 4. Our finding, which is also verified by simulations, is paramount as it puts an upper bound on the hop count for the hop-limited routing schemes by discovering the optimal hop count for both additive and bottleneck weights.

While there is a drastic shift from host-centric networking to content-centric networking, how to locate and retrieve the relevant content efficiently, especially in a mobile network, is still an open question. Mobile devices host increasing volume of data which could be shared with the nearby nodes in a multi-hop fashion. However, searching for content in this resource-restricted setting is not trivial due to the lack of a content index, as well as, desire for keeping the search cost low. In this paper, we analyze a lightweight search scheme, hop-limited search, that forwards the search messages only till a maximum number of hops, and requires no prior knowledge about the network. We highlight the effect of the hop limit on both search performance (i.e., success ratio and delay) and associated cost along with the interplay between content availability, tolerated waiting time, network density, and mobility. Our analysis, using the real mobility traces, as well as synthetic models, shows that the most substantial benefit is achieved at the first few hops and that after several hops the extra gain diminishes as a function of content availability and tolerated delay. We also observe that the return path taken by a response is on average longer than the forward path of the query and that the search cost increases only marginally after several hops due to the small network diameter.

Recent computer systems research has proposed using redundant requests to reduce latency. The idea is to run a request on multiple servers and wait for the first completion (discarding all remaining copies of the request). However there is no exact analysis of systems with redundancy.

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

Searching content in mobile opportunistic networks is a difficult problem due to the dynamically changing topology and intermittent connections. Moreover, due to the lack of global view of the network, it is arduous to determine whether the best response is discovered or search should be spread to other nodes. A node that has received a search query has to take two decisions: (i) whether to continue the search further or stop it at the current node (current search depth) and, independently of that, (ii) whether to send a response back or not. As each transmission and extra hop costs in terms of energy, bandwidth and time, a balance between the expected value of the response and the costs incurred must be sought. In order to better understand this inherent trade-off, we assume a simplified setting where both the query and response follow the same path. We formulate the problem of optimal search for the following two cases: a node holds (i) exactly matching content with some probability, and (ii) some content partially matching the query. We design static search in which the search depth is set at query initiation, dynamic search in which search depth is determined locally during query forwarding, and learning dynamic search which leverages the observations to estimate suitability of content for the query. Additionally, we show how unreliable response paths affect the optimal search depth and the corresponding search performance. Finally, we investigate the principal factors affecting the optimal search strategy.

We study delay tolerant networking (DTN) and in particular, its capacity to store, carry and forward messages to their final destination(s). We approach this broad question in the framework of percolation theory. To this end, we assume an elementary mobility model, where nodes arrive to an infinite plane according to a Poisson point process, move a certain distance ℓ, and then depart. In this setting, we characterize the mean density of nodes required to support DTN style networking. Under the given assumptions, we show that DTN communication is feasible when the mean node degree v is greater than 4 ηc(γ), where parameter γ= ℓ /d is the ratio of the distance ℓ to the transmission range d, and ηc(γ) is the critical reduced number density of tilted cylinders in a directed continuum percolation model. By means of Monte Carlo simulations, we give numerical values for ηc(γ). The asymptotic behavior of ηc(γ) when γ tends to ∞ is also derived from a fluid flow analysis.

We consider a system of parallel queues where tasks are assigned (dispatched) to one of the available servers upon arrival. The dispatching decision is based on the full state information, i.e., on the sizes of the new and existing jobs. We are interested in minimizing the so-called mean slowdown criterion corresponding to the mean of the sojourn time divided by the processing time. Assuming no new jobs arrive, the shortest-processing-time-product (SPTP) schedule is known to minimize the slowdown of the existing jobs. The main contribution of this paper is three-fold: 1) To show the optimality of SPTP with respect to slowdown in a single server queue under Poisson arrivals; 2) to derive the so-called size-aware value functions for M/G/1-FIFO/LIFO/SPTP with general holding costs of which the slowdown criterion is a special case; and 3) to utilize the value functions to derive efficient dispatching policies so as to minimize the mean slowdown in a heterogeneous server system. The derived policies offer a significantly better performance than e.g., the size-aware-task-assignment with equal load (SITA-E) and least-work-left (LWL) policies.

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.

We consider a dynamic dispatching problem where jobs are assigned upon arrival into parallel queues. Jobs have an arbitrary size distribution and each queue has its own service rate, queueing discipline, and operating power while serving jobs. Our goal is to minimize a weighted sum of delay and energy consumption under the assumption that the dispatcher is aware of the remaining service time of each job in the system, including that of the arriving job. We devise efficient dispatching heuristics based on the first policy iteration procedure of Markov Decision Processes. The resulting policies are illustrated by numerical examples. Direct control over the trade-off between performance and energy consumption will be increasingly important in future ICT equipment designs wherever dynamic queue assignment is needed.

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.

Fountain codes provide an efficient way to transfer information over erasure channels. We give an exact performance analysis of a specific type of fountain codes, called LT codes, when the message length N is small. Two different approaches are developed. In a Markov chain approach the state space explosion, even with reduction based on permutation isomorphism, limits the analysis to very short messages, N < 4. An alternative combinatorial method allows recursive calculation of the probability of decoding after N received packets. The recursion can be solved symbolically for values of N < 10 and numerically up to N ap30. Examples of optimization results give insight into the nature of the problem. In particular, we argue that a few conditions are sufficient to define an almost optimal LT encoding.

We consider the load balancing problem in large wireless multi-hop networks, often referred to as massively dense wireless multi-hop networks. A network is considered to be massively dense if there are nodes practically everywhere and a typical distance between two nodes is much larger than the transmission range necessitating communication over a large number of hops. The task is to choose the routes in such a way that the maximum relayed traffic load in the network is minimized. In fixed networks the multi-path routes generally yield a lower congestion and thus allow higher throughput. In contrast, we show that in the case of massively dense wireless multi-hop networks the optimal load balancing can be achieved by single-path routing. In particular, we show how any given multi-path routing can be transformed to a single-path routing with at least the same level of performance. The concepts are illustrated by numerical examples where the network nodes are assumed to reside inside a unit disk with uniform traffic demands. The shortest path routes, corresponding to straight line segments, yield a maximum traffic load of 0.637, whereas the single-path routes obtained by numerical optimization yield 0.343, corresponding to 46% reduction in the traffic load.

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.

In This work we present a linear programming formulation for the routing problem in optical burst switching networks (OBS). Unlike in conventional wavelength routed networks, in an OBS network (light)paths are allowed to clash. One should, however, try to minimize the number of clashes as each of them can potentially cause a burst occassionally to be blocked. Thus, by choosing the paths and wavelength channels carefully one can decrease the blocking probability and also improve fairness among the different connections. In This work we propose an OBS-aware routing policy, which is shown to improve the overall performance in terms of blocking probability and fairness.

With standard assumptions the routing and wavelength assignment problem (RWA) can be viewed as a Markov decision process (MDP). The problem, however defies an exact solution because of the huge size of the state space. Only heuristic algorithms have been presented up till now. We propose an approach where, starting from a given heuristic algorithm, one obtains a better algorithm by the first policy iteration. In order to estimate the relative costs of states, we make a simulation on the fly studying, at each decision epoch, the consequences of all the alternatives actions. Being computationally intensive, this method can be used in real time only for systems with slow dynamics. Offline it can be used to assess how close the heuristic algorithms come to the optimal policy. Numerical examples are given about the policy improvement.