We consider a priority queueing system where a single processor serves k classes of packets that are generated randomly following Poisson processes. Our objective is to compute the expected Peak Age of Information (PAoI) under various scenarios. In particular, we consider two situations where the buffer size at each queue is one and infinite, and in the infinite buffer size case we consider First Come First Serve (FCFS) and Last Come First Serve (LCFS) as service disciplines. For the system with buffer size one at each queue, we derive PAoI exactly for the case of exponential service time and bounds (which are excellent approximations) for the case of general service time, with small k. For the system with infinite buffer size, we provide closed-form expressions of PAoI for both FCFS and LCFS where service time is general and k could be large. Using those results we investigated the effect of ordering of priorities and service disciplines for the various scenarios. We perform extensive numerical studies to validate our results and develop insights.insights.

Although networks based on 802 standards were initially designed to transport best-effort traffic, they now can accommodate all sorts of traffic, including time-sensitive ones. The latter is possible through a group of standards developed and maintained by the Time-Sensitive Networking (TSN) Task Group. This set of protocols ensures bounds and latency guarantees for streams of periodically arriving data. However, no bounds or guarantees are specified for stochastically arriving data. In this work, we propose an approximation for the end-to-end average latency that randomly arriving frames experience in a flow over a TSN path. These are non-scheduled frames arriving at a scheduled network. We based our approximation on a classic model from urban traffic literature called Fixed-Cycle Traffic Light (FCTL). Our approach is effective and extremely fast to compute compared to exact models or simulations.

The integration of condition monitoring with queueing systems to support decision making is not well explored. This paper addresses the impact of condition monitoring of the server on the system-level performance experienced by entities in a queueing system. The system consists of a queue with a single-server subject to Markovian degradation. The model assumes a Poisson arrival process with service times and repair times according to general distributions. We develop stability conditions and perform steady-state analysis to obtain performance measures (average queue length, average degradation, and so on). We propose minimizing an objective function involving four types of costs: repair, catastrophic failure, quality, and holding. The queue performance measures derived from steady-state analysis are benchmarked and compared to those from a discrete event simulation model. After verifying the queuing model, a sensitivity analysis is performed to determine the relationships between system performance and model parameters. Results indicate that the total cost function is convex and, thus, subject to an optimal repair policy. The model is sensitive to service time, quality costs, and failure costs for late-stage policy repairs decisions and sensitive to expected repair times and repair costs for early stage policy repair decisions.

A common pitfall when hosting applications in today's cloud environments is that virtual servers often experience varying execution speeds due to the interference from co-located virtual servers degrading the tail sojourn times specified in service level agreements. Motivated by the significance of tail sojourn times for cloud clusters, we develop a model of N parallel virtual server queues, each of which processes jobs in a processor sharing fashion under varying execution speeds governed by Markov-modulated processes. We derive the tail distribution of the workloads for each server and the approximation for the tail sojourn times based on large deviation analysis. Furthermore, we optimize the cluster sizes that fulfill the requirements of target tail sojourn times. Extensive simulation experiments show very good matches to the derived analysis in a variety of scenarios, i.e., large numbers of servers experiencing a high number of different execution speeds, under various traffic intensities, workload variations and cluster sizes. Finally, we apply our proposed analysis to estimating the tail sojourn times of a Wikipedia system hosted in a private cloud, and the testbed results strongly confirm the applicability and accuracy of our analysis.

Motivated by applications in data centers, we consider a scenario where multiple classes of requests arrive at a dispatcher at time-varying rates which historically has daily or weekly patterns. We assume that the underlying environment is such that at all times the load from each class is very high and a large number of servers are necessary which, for example, is fairly common in many data centers. In addition, each server can host one or more classes. Design, control and performance analysis under such heterogeneous and transient conditions is extremely difficult. To address this shortcoming we have suggested a holistic approach that includes a combination of sizing, assignment, and routing in an integrated fashion. Our proposed approach decomposes a multi-dimensional and non-stationary problem into a one-dimensional, simpler and stationary one, and achieves time-stability by introducing an insignificant number of dummy requests. Based on time-stability, our suggested approach can provide performance bounds and guarantees for time-varying and transient system. Moreover, we can operate the data centers in an energy-efficient manner via suggested approach.

In this paper, multiple relays capable of harvesting energy from radio-frequency (RF) signals are employed to collaboratively forward data from a source transmitter to its destined receiver. Due to the relays' inability to harvest energy and transmit data simultaneously, the source needs to optimally schedule the relays' energy harvesting (EH) and data transmission. Considering different channel conditions and energy constraints, the relays need to optimally design a beamforming vector that specifies each relay a power amplifier coefficient to forward the source signal and suppress the noise. By joint EH scheduling and beamforming, we maximize the overall throughput formulated in a nonconvex problem. We first propose a centralized scheme that achieves the optimal throughput by exploiting the monotonicity in the problem structure. We further propose a distributed suboptimal scheme in a game theoretic approach, which requires the source and the relays to iteratively update EH scheduling and beamforming vector, respectively. We show that the suboptimal scheme has a threshold-based structure for the relays' power control depending on the source-relay channel conditions. Numerical results show near-optimal performance of the distributed scheme compared with the centralized optimal scheme.

The dynamic and unpredictable nature of energy harvesting sources that are used in wireless sensor networks necessitates the need for adaptive duty cycling techniques. Such adaptive control allows sensor nodes to achieve energy-neutrality, whereby both energy supply and demand are balanced. This paper proposes a framework enabling an adaptive duty cycling scheme for sensor networks that takes into account the operating duty cycle of the node, and application-level QoS requirements. We model the system as a Continuous Time Markov Chain (CTMC), and derive analytical expressions for key QoS metrics - such as latency, loss probability and power consumption. We then formulate and solve the optimal operating duty cycle as a non-linear optimization problem, using latency and loss probability as the constraints. Simulation results show that a Markovian duty cycling scheme can outperform periodic duty cycling schemes.

The dynamic and unpredictable nature of energy harvesting sources available for wireless sensor networks, and the time variation in network statistics like packet transmission rates and link qualities, necessitate the use of adaptive duty cycling techniques. Such adaptive control allows sensor nodes to achieve long-run energy neutrality, where energy supply and demand are balanced in a dynamic environment such that the nodes function continuously. In this paper, we develop a new framework enabling an adaptive duty cycling scheme for sensor networks that takes into account the node battery level, ambient energy that can be harvested, and application-level QoS requirements. We model the system as a Markov decision process (MDP) that modifies its state transition policy using reinforcement learning. The MDP uses continuous time Markov chains (CTMCs) to model the network state of a node to obtain key QoS metrics like latency, loss probability, and power consumption, as well as to model the node battery level taking into account physically feasible rates of change. We show that with an appropriate choice of the reward function for the MDP, as well as a suitable learning rate, exploitation probability, and discount factor, the need to maintain minimum QoS levels for optimal network performance can be balanced with the need to promote the maintenance of a finite battery level to ensure node operability. Extensive simulation results show the benefit of our algorithm for different reward functions and parameters.

We consider a node in a multihop wireless network that is responsible for transmitting messages in a timely manner while being prudent about energy consumption. The node uses energy harvesting in the sense that it is powered by batteries that are charged by renewable energy sources such as wind or solar. To strike a balance between latency and availability, we develop a multi-timescale model. At a faster timescale, the node makes decisions based on local information such as queue lengths of packets in input buffers and available energy levels. The decisions include scheduling packets on the output buffers that would be transmitted at the next opportunity, possibly using network coding. At the slower timescale, we model the energy levels in the battery using a stochastic fluid-flow model to determine the availability and time-averaged latency. Ultimately, we present a unified framework that iteratively sets model parameters to satisfy latency and availability targets. The methods are based upon Markov decision processes, Markov chains, and semi-Markov process analysis.

It has been well established that wireless network coding can significantly improve the efficiency of multihop wireless networks. However, in a stochastic environment, some of the packets might not have coding pairs, which limits the number of available coding opportunities. In this context, an important decision is whether to delay packet transmission in hope that a coding pair will be available in the future or transmit a packet without coding. This paper addresses this problem by establishing a stochastic dynamic framework whose objective is to minimize a long-run average cost. We identify an optimal control policy that minimizes the costs due to a combination of transmissions and packet delays. We show that the optimal policy would be stationary, deterministic, and threshold-type based on queue lengths. Our analytical approach is applicable for many cases of interest such as time-varying on/off channels. We further substantiate our results with simulation experiments for more generalized settings.

We consider a relay node that stochastically receives packets from two opposing flows. Whenever opportunities exist, the relay performs network coding to efficiently transmit packets. However, on one hand, because of the stochastic nature, as well as possible asymmetry between the opposing flows, it would not be possible to always code packets. On the other hand, waiting for a coding opportunity could result in excessive latency, and one may be better off transmitting packets without coding. Thus, one needs to decide at each transmission opportunity whether to transmit a packet uncoded or wait for a future transmission opportunity. To enable us to optimally make that decision, we consider costs for transmission and delay, and formulate our problem as a Markov decision process. We show that the optimal policy is threshold type under a sufficient condition, and we compute it by modeling the resulting system as a Markov chain. Through numerical analysis, we show the effectiveness of the threshold policy in the relay node network, as well as in a line network scenario. Further, we compare the threshold policy against a number of simple heuristic policies and identify situations where these policies can be effective.

We consider wireless networks in which multiple paths are available between each source and destination. We allow each source to split traffic among all of its available paths, and we ask the question: How do we attain the lowest possible number of transmissions per unit time to support a given traffic matrix? Traffic bound in opposite directions over two wireless hops can utilize the “reverse carpooling” advantage of network coding in order to decrease the number of transmissions used. We call such coded hops “hyper-links.” With the reverse carpooling technique, longer paths might be cheaper than shorter ones. However, there is a peculiar situation among sources—the network coding advantage is realized only if there is traffic in both directions of a shared path. We consider the problem of routing with network coding by selfish agents (the sources) as a potential game and develop a method of state-space augmentation in which additional agents (the hyper-links) decouple sources' choices from each other by declaring a hyper-link capacity, allowing sources to split their traffic selfishly in a distributed fashion, and then changing the hyper-link capacity based on user actions. Furthermore, each hyper-link has a scheduling constraint in terms of the maximum number of transmissions allowed per unit time. We show that our two-level control scheme is stable and verify our analytical insights by simulation.

In this paper, we consider time-varying multiserver queues with abandonment and retrials. For their performance analysis, fluid and diffusion limits utilizing strong approximations have been widely used in the literature. Although those limits are asymptotically exact, they may not accurately approximate performance of multiserver queues even if the number of servers is large. To address that concern, this paper focuses on developing a methodology by taking fluid and diffusion limits in a nontraditional fashion. We show that our approximation is significantly more accurate and also asymptotically true. We illustrate the effectiveness of our methodology by performing several numerical experiments.

It has been well established that reverse-carpooling based network coding can significantly improve the efficiency of multi-hop wireless networks. However, in a stochastic environment when there are no opportunities to code because of packets without coding pairs, should these packets wait for a future opportunity or should they be transmitted without coding? To help answer that question we formulate a stochastic dynamic program with the objective of minimizing the long-run average cost per unit time incurred due to transmissions and delays. In particular, we develop optimal control actions that would balance between costs of transmission against those of delays. In that process we seek to address a crucial question: what should be observed as the state of the system? We analytically show that just the queue lengths is enough if it can be modeled as a Markov process. Subsequently we show that a stationary policy based on queue lengths is optimal and describe a procedure to find such a policy. We further substantiate our results with simulation experiments for more generalized settings.

We consider wireless networks in which multiple paths are available between each source and destination. We allow each source to split traffic among all of its available paths, and ask the question: how do we attain the lowest possible number of transmissions per unit time to support a given traffic matrix? Traffic bound in opposite directions over two wireless hops can utilize the ``reverse carpooling'' advantage of network coding in order to decrease the number of transmissions used. We call such coded hops as ``hyper-links''. With the reverse carpooling technique longer paths might be cheaper than shorter ones. However, there is a prisoners dilemma type situation among sources -- the network coding advantage is realized only if there is traffic in both directions of a shared path. We develop a two-level distributed control scheme that decouples user choices from each other by declaring a hyper- link capacity, allowing sources to split their traffic selfishly in a distributed fashion, and then changing the hyper-link capacity based on user actions. We show that such a controller is stable, and verify our analytical insights by simulation.

For a wide range of devices and servers, Dynamic Frequency Scaling (DFS) can reduce energy consumption to various degrees by appropriately trading-off system performance. Efficient DFS policies are able to adjust server frequencies by extrapolating the transition of the highly varying workload without incurring much of implementation overhead. This paper models DFS policies of a single server using Markov Decision Processes (MDP). To accommodate the highly varying nature of workload in the proposed MDP, we adopt fluid approximation based on continuous time Markov chain and discrete time Markov chain modeling for the fluid workload generator respectively. Accordingly, we design two frequency controllers (FC), namely C-FC and D-FC, corresponding to the continuous and discrete modeling of the workload generator. We evaluate the proposed policies on synthetic and Web traces. The proposed C-FC and D-FC schemes ensure performance satisfaction with moderate energy saving as well as ease of implementation, in comparison with existing DFS policies.

There are several important properties of modern software systems. They tend to be large-scale with distributed and component-based architectures. Also, dynamic nature of operating environments leads them to utilize alternative algorithms. However, on the other hand, these properties make it hard to provide appropriate control mechanisms due to the increased complexity. Components are sharing resources and each component can have alternative algorithms. As a result, the behavior of a software system can be controlled through resource allocation, as well as algorithm selection. This novel control problem is worthy of investigation in order to double the benefits of those properties. In this paper, we design a control mechanism for such systems. The quality-of-service we are considering is a product of the value of solution and the time for generating solution for a given problem. We build a mathematical programming model that trades off these two conflicting objectives, and decentralize the model through an auction market. By periodically opening the auction market for each existing system state, a closed-loop policy is formed. Though similar problems can be found in multiprocessor scheduling literature, they have limitations in addressing this control problem. They commonly consider so-called workflow applications in which each component only has to process one task after all of its predecessors complete their tasks. In contrast, a component in the networks under consideration processes multiple tasks in parallel with its successors or predecessors.

The growing cost of tuning and managing computer systems is leading to out-sourcing of commercial services to hosting centers. These centers provision thousands of dense servers within a relatively small real-estate in order to host the applications/services of different customers who may have been assured by a service-level agreement (SLA). Power consumption of these servers is becoming a serious concern in the design and operation of the hosting centers. The effects of high power consumption manifest not only in the costs spent in designing effective cooling systems to ward off the generated heat, but in the cost of electricity consumption itself. It is crucial to deploy power management strategies in these hosting centers to lower these costs towards enhancing profitability. At the same time, techniques for power management that include shutting down these servers and/or modulating their operational speed, can impact the ability of the hosting center to meet SLAs. In addition, repeated on-off cycles can increase the wear-and-tear of server components, incurring costs for their procurement and replacement. This paper presents a formalism to this problem, and proposes three new online solution strategies based on steady state queuing analysis, feedback control theory, and a hybrid mechanism borrowing ideas from these two. Using real web server traces, we show that these solutions are more adaptive to workload behavior when performing server provisioning and speed control than earlier heuristics towards minimizing operational costs while meeting the SLAs.

Synthesizing I/O requests that can accurately capture workload behavior is extremely valuable for the design, implementation and optimization of disk subsystems. This paper presents a synthetic workload generator for TPC-H, an important decision-support commercial workload, by completely characterizing the arrival and access patterns of its queries. We present a novel approach for parameterizing the behavior of inter-mingling streams of sequential requests, and exploit correlations between multiple attributes of these requests, to generate disk block-level traces that are shown to accurately mimic the behavior of a real trace in terms of response time characteristics for each TPC-H query.

To predict the delay between a source and a destination as well as to identify anomalies in a network, it is possible to monitor the network continuously by sending probes between all sources and destinations. However, it is of prime importance to keep the number of probes to a minimum and yet be able to predict the delays and identify anomalies reasonably. We state and solve a mathematical programming problem, namely the zone recovery methodology (ZRM), to select an optimal subset of ping-like probes to monitor networks where the topology and routing information are not known. A polynomial-time heuristic is developed. The application of ZRM on randomly generated topologies yielded 73.55% reduction in the number of monitored paths on average. In other words, networks can be successfully monitored using only 26.45% of the available probes. Moreover, the performance of ZRM increases (percentage of the monitored paths decreases) as the size of the topology increases.

Scheduling in large-scale parallel systems has been and continues to be an important and challenging research problem. Several key factors, including the increasing use of off-the-shelf clusters of workstations to build such parallel systems, have resulted in the emergence of a new class of scheduling strategies, broadly referred to as dynamic coscheduling. Unfortunately, the size of both the design and performance spaces of these emerging scheduling strategies is quite large, due in part to the numerous dynamic interactions among the different components of the parallel computing environment as well as the wide range of applications and systems that can comprise the parallel environment. This in turn makes it difficult to fully explore the benefits and limitations of the various proposed dynamic coscheduling approaches for large-scale systems solely with the use of simulation and/or experimentation.To gain a better understanding of the fundamental properties of different dynamic coscheduling methods, we formulate a general mathematical model of this class of scheduling strategies within a unified framework that allows us to investigate a wide range of parallel environments. We derive a matrix-analytic analysis based on a stochastic decomposition and a fixed-point iteration. A large number of numerical experiments are performed in part to examine the accuracy of our approach. These numerical results are in excellent agreement with detailed simulation results. Our mathematical model and analysis is then used to explore several fundamental design and performance tradeoffs associated with the class of dynamic coscheduling policies across a broad spectrum of parallel computing environments.