Two-person zero-sum Markov games: receding horizon approach

We consider a receding horizon approach as an approximate solution to two-person zero-sum Markov games with infinite horizon discounted cost and average cost criteria. We first present error bounds from the optimal equilibrium value of the game when both players take "correlated" receding horizon policies that are based on exact or approximate solutions of receding finite horizon subgames. Motivated by the worst-case optimal control of queueing systems by Altman, we then analyze error bounds when the minimizer plays the (approximate) receding horizon control and the maximizer plays the worst case policy. We finally discuss some state-space size independent methods to compute the value of the subgame approximately for the approximate receding horizon control, along with heuristic receding horizon policies for the minimizer.     

M/M/1-PS queue and size-aware task assignment

We consider a distributed server system in which heterogeneous servers operate under the processor sharing (PS) discipline. Exponentially distributed jobs arrive to a dispatcher, which assigns each task to one of the servers. In the so-called size-aware system, the dispatcher is assumed to know the remaining service requirements of some or all of the existing jobs in each server. The aim is to minimize the mean sojourn time, i.e., the mean response time. To this end, we first analyze an M/M/1-PS queue in the framework of Markov decision processes, and derive the so-called size-aware relative value of state, which sums up the deviation from the average rate at which sojourn times are accumulated in the infinite time horizon. This task turns out to be non-trivial. The exact analysis yields an infinite system of first order differential equations, for which an explicit solution is derived. The relative values are then utilized to develop efficient dispatching policies by means of the first policy iteration (FPI). Numerically, we show that for the exponentially distributed job sizes the myopic approach, ignoring the future arrivals, yields an efficient and robust policy when compared to other heuristics. However, in the case of highly asymmetric service rates, an FPI based policy outperforms it. Additionally, the size-aware relative value of an M/G/1-PS queue is shown to be sensitive with respect to the form of job size distribution, and indeed, the numerical experiments with constant job sizes confirm that the optimal decision depends on the job size distribution.     

一种开放混合实时系统的开放自适应调度算法

开放计算环境下的实时与非实时任务不确定并发,以及多种实时约束混合的复杂约束系统,即开放混合实时系统的需求越来越广泛.通过引入接收控制、调度服务器、自适应调节机制,提出一种开放环境下的自适应实时系统调度架构--OARtS(open adaptive real-time scheduling).它能适应开放计算环境的不确定性,有控制地接受实时任务运行;可根据系统空闲计算带宽变化,自适应地调节任务的实时等级,使得系统运行在最优的实时性能上;对于软实时任务,可根据其计算带宽需求变化,自适应地调节其计算带宽分配,以适应任务执行时间时变引起的实时不确定性.     

Video Packet Selection and Scheduling for Multipath Streaming

This paper addresses the problem of choosing the best streaming policy for distortion optimal multipath video delivery, under network bandwidth and playback delay constraints. The streaming policy consists in a joint selection of the network path and of the video packets to be transmitted, along with their sending time. A simple streaming model is introduced, which takes into account the video packet importance, and the dependencies between packets. A careful timing analysis allows to compute the quality perceived by the receiver for a constrained playback delay, as a function of the streaming policy. We derive an optimization problem based on a video abstraction model, under the assumption that the server knows, or can predict accurately the state of the network. A detailed analysis of constrained multipath streaming systems provides helpful insights to design an efficient branch and bound algorithm that finds the optimal streaming strategy. This solution allows to bound the performance of any scheduling strategy, but the complexity of the algorithm becomes rapidly intractable. We therefore propose a fast heuristic-based algorithm, built on load-balancing principles. It allows to reach close to optimal performance with a polynomial time complexity. The algorithm is then adapted to live streaming scenarios, where the server has only a partial knowledge of the packet stream, and the channel bandwidth. Extensive simulations show that the proposed algorithm only induces a negligible distortion penalty compared to the optimal strategy, even when the optimization horizon is limited, or the rate estimation is not perfect. Simulation results also demonstrate that the proposed scheduling solution performs better than common scheduling algorithms, and therefore represents a very efficient low-complexity multipath streaming algorithm, for both stored and live video services     

用连续Hopfield网络实现无限时域上的最优控制

为避免直接采用Riccati方程求解时变系统无限域最优控制问题时的计算困难,本文提出一种基于时间连续状态连续型Hopfield网络(CTCSHNN)实现无限域动态最优控制的方法．该方法通过建立CTCSHNN能量函数与移动域控制指标间的等价关系,可在线构建CTCSHNN．理论分析表明,依据该方法设计的CTCSHNN具有稳定性,而且移动域控制量可由网络稳态输出直接产生．将该方法与滚动优化策略相结合,可实现无限时域上的闭环最优控制．仿真实验验证了理论设计的正确性与采用基于CTCSHNN的移动域控制实现无限域闭环最优控制的可行性．     

Receding Horizon Control for a Class of Discrete-Event Systems With Real-Time Constraints

We consider discrete-event systems (DES) involving the control of tasks with real-time constraints. When future event time information is limited, we propose a receding horizon (RH) controller in which only some future information is available within a time window. Analyzing sample paths obtained under this scheme and comparing them to optimal sample paths (obtained when all event times are known), we derive a number of attractive properties of the RH controller, including: the fact that it still guarantees all real-time constraints; there are segments of its sample path over which all controls are still optimal; the error relative to the optimal task departure times is decreasing under certain conditions. Simulation results are included to verify the properties of the controller and show that its performance can be near-optimal even if the RH window size is relatively small     

COORDINATED SENSING OF NETWORKED BODY SENSORS USING MARKOV DECISION PROCESSES

This article describes a Markov decision process (MDP) framework for coordinated sensing between correlated sensors in a body-area network. The technique is designed to extend the life of mobile continuous health-monitoring systems based on energy-constrained wearable sensors. The technique enables distributed sensors in a body-area network to adapt their sampling rates in response to changing criticality of the detected data and the limited energy reserve at each sensor node. The relationship between energy consumption, sampling rates, and utility of coordinated measurements is formulated as an MDP. This MDP is solved to generate a globally optimal policy that specifies the sampling rates for each sensor for all possible states of the system. This policy is computed offline before deployment and only the resulting policy is stored within each sensor node. We also present a method of executing the global policy without requiring continuous communication between the sensors. Each sensor node maintains a local estimate of the global state. Communication occurs only when an information-theoretic model of the uncertainty in the local state estimates exceeds a predefined threshold. We show results on simulated data that demonstrate the efficacy of this distributed-control framework and compare the performance of the proposed controller with other policies.     

Stochastic Receding Horizon Control of Constrained Linear Systems With State and Control Multiplicative Noise

We develop a receding horizon control approach to stochastic linear systems with control and state multiplicative noise that also contain constraints. Our receding horizon formulation is based upon an on-line optimization that utilizes open-loop plus linear feedback and is solved as a semi-definite programming problem. We also provide a characterization of stability, performance, and constraint satisfaction properties of the receding horizon controlled system under a specific choice of terminal weight and terminal constraint. A simple numerical example is used to illustrate the approach.      

Scheduling of multi-class multi-server queueing systems with abandonments

Many real-world situations involve queueing systems in which customers may abandon if service does not start sufficiently quickly. We study a comprehensive model of multi-class queue scheduling accounting for customer abandonment, with the objective of minimizing the total discounted or time-average sum of linear waiting costs, completion rewards, and abandonment penalties of customers in the system. We assume the service times and abandoning times are exponentially distributed. We solve analytically the case in which there is one server and there are one or two customers in the system and obtain an optimal policy. For the general case, we use the framework of restless bandits to analytically design a novel simple index rule with a natural interpretation. We show that the proposed rule achieves near-optimal or asymptotically optimal performance both in single- and multi-server cases, both in overload and underload regimes, and both in idling and non-idling systems.     

Improving the performance for task assignment in distributed server systems by partitioning the large tasks

Task Assignment in distributed server systems focuses on the policy that assigns the tasks reached these systems in order to improve the response time. These tasks, generally, have the property that there is a tiny fraction (about 3%) of the large tasks that makes half (50%) of the total load. However, this property creates additional problems: the large tasks make the load difficult to balance among the servers, and the small tasks will be delayed by the large ones when they are in the same queue. In this paper, we propose a new policy for the Web clusters that we call Partitioning Large Tasks (PLT) and which deals with these problems mostly under a high traffic demand and a high variability of task sizes. PLT partitions each large task into fragments and assigns them to be processed in a parallel way and completing at the same time to improve the mean response time, and separates the small tasks from the large tasks to avoid being delayed. Performance tests show a significantly improvement in performance of PLT over the existing task assignment policies.     

How useful is old information?

We consider the problem of load balancing in dynamic distributed systems in cases where new incoming tasks can make use of old information. For example, consider a multiprocessor system where incoming tasks with exponentially distributed service requirements arrive as a Poisson process, the tasks must choose a processor for service, and a task knows when making this choice the processor queue lengths from T seconds ago. What is a good strategy for choosing a processor in order for tasks to minimize their expected time in the system? Such models can also be used to describe settings where there is a transfer delay between the time a task enters a system and the time it reaches a processor for service. Our models are based on considering the behavior of limiting systems where the number of processors goes to infinity. The limiting systems can be shown to accurately describe the behavior of sufficiently large systems and simulations demonstrate that they are reasonably accurate even for systems with a small number of processors. Our studies of specific models demonstrate the importance of using randomness to break symmetry in these systems and yield important rules of thumb for system design. The most significant result is that only small amounts of queue length information can be extremely useful in these settings; for example, having incoming tasks choose the least loaded of two randomly chosen processors is extremely effective over a large range of possible system parameters. In contrast, using global information can actually degrade performance unless used carefully; for example, unlike most settings where the load information is current, having tasks go to the apparently least loaded server can significantly hurt performance     

Further results on linear nonquadratic optimal control

Continues an investigation by the authors of minimizing the transient response of a linear system as measured by nonquadratic penalty functions, in particular, penalty functions which have linear growth. First, this note shows that the optimal state feedback which minimizes the transient response in the case of no exogenous inputs also minimizes the induced l¹ norm in case exogenous inputs are present. Second, it considers the case of constrained systems and derives bounds which establish the stability and performance of receding horizon control laws. Finally, this note illustrates the results for scheduling of reliable manufacturing systems     

基于混合蚁群优化的边缘计算细粒度任务调度方法

为缓解中心服务器的压力,制定合理的调度方案,基于混合蚁群优化算法提出了边缘计算细粒度任务调度方法。描述边缘计算任务调度问题,并设置假设条件,简化调度求解难度。通过计算任务的优先指数,按照从大到小的顺序排列后组成任务队列。分析边缘服务器性能特征,明确边缘服务器处理能力。构建能耗以及时延多目标函数,并设置约束条件,利用混合蚁群优化算法求解多目标函数,完成边缘计算细粒度任务调度方案设计。结果表明：该方法应用下的任务调度能耗和时延更小,说明所提方法性能更优,所获得的调度方案更合理。     

融合模糊逻辑与马尔可夫决策过程的边缘计算切换策略

在边缘计算切换策略中,针对马尔可夫决策过程（Markov decision process,MDP）传输时延高且环境适应能力差等问题,提出了一种融合模糊逻辑与马尔可夫决策过程的边缘计算切换策略。采用模糊逻辑算法将系统参数模糊化,并且将模糊值引入适应度函数,保证系统参数能够有效融合;利用差分进化算法求解适应度函数最大值,从而选取出该环境的最优规则,提高边缘计算对环境的适应能力;将适应度函数引入MDP,提高系统综合性能。该方案将移动智能设备作为任务卸载发起方,将边缘服务器作为任务卸载对象,对一维MDP切换策略、一维仅时延MDP切换策略、二维MDP切换策略、模糊逻辑MDP切换策略、最小距离切换算法和最小时延切换算法进行仿真。仿真结果表明,模糊逻辑MDP的边缘计算切换策略的任务执行平均时长为608.8 s,较一维MDP切换策略、一维仅时延MDP切换策略、二维MDP切换策略、最小距离切换算法和最小时延切换算法分别降低了27.2%、8.6%、37.1%、41%和22.3%。该方案在提高了基于MDP的边缘计算切换策略的环境适应性的同时,大幅降低了边缘计算的传输时延。     

边缘计算中协作计算卸载与动态任务调度

在边缘计算场景中,通过将部分待执行任务卸载到边缘服务器执行能够达到降低移动设备的负载、提升移动应用性能和减少设备开销的目的.对于时延敏感任务,只有在截止期限内完成才具有实际意义.但是边缘服务器的资源往往有限,当同时接收来自多个设备的数据传输及处理任务时,可能造成任务长时间的排队等待,导致部分任务因超时而执行失败,因此无法兼顾多个设备的性能目标.鉴于此,在计算卸载的基础上优化边缘服务器端的任务调度顺序.一方面,将时延感知的任务调度建模为一个长期优化问题,并使用基于组合多臂赌博机的在线学习方法动态调整服务器的调度顺序.另一方面,由于不同的任务执行顺序会改变任务卸载性能提升程度,因而影响任务卸载决策的有效性.为了增加卸载策略的鲁棒性,采用了带有扰动回报的深度Q学习方法决定任务执行位置.仿真算例证明了该策略可在平衡多个用户目标的同时减少系统的整体开销.     

基于连续Hopfield网络的多变量时变系统最优控制

针对多变量时变系统提出了一种基于连续Hop fie ld网络的最优控制系统设计方法.该方法不仅从理论上建立了移动时域上的LQ性能指标与连续Hop fie ld网络能量函数间的等价关系,并在此基础上设计出可求解LQ最优控制问题的连续Hop fie ld网络,而且将滚动优化控制策略引入控制系统,形成了包括连续Hop fie ld网络在内的闭环控制结构,实现了多变量时变系统无限域上的动态最优控制.仿真结果验证了该设计方法的有效性.     

Dynamic non-preemptive re-allocation policies between two sites with reconfigurable servers

Dynamic server re-allocation can be very useful in real life computing applications. Since the load on many computing systems is not uniformly distributed to each server, it may be effective to transfer the less loaded servers to help the other more loaded ones. However, since transferring takes time, it may not be profitable to actually make the transfer. In this study we model this case with two queues. Each queue is served by one server which can be re-allocated, i.e. an operator may decide to switch a server to serve the other queue. The re-allocation policies we examine are non-preemptive, which implies that a server can be re-allocated if it is idle or has just served a customer. The model is studied with respect to the average cost criterion. We find the optimal re-allocation policy for various instances of the parameters. In addition, we provide a heuristic policy and use simulation experiments to compare it with the optimal one as well as the policy that uses no re-allocation at all.     

On Choosing a Task Assignment Policy for a Distributed Server System

We consider a distributed server system in which each host processes tasks in First-Come-First-Served order and each task's service demand is known immediately upon task arrival. We consider four task assignment policies commonly proposed for such distributed server systems: Round Robin; Random; Size-Based, in which all tasks within a given size range are assigned to a particular host; and Dynamic-Least-Work-Remaining, in which a task is assigned to the host with the least outstanding work. Using analysis and simulation, we explore the influence of task size variability on which task assignment policy is best. Surprisingly, we find that not one of the above task assignment policies is best. In particular, we find that when the task sizes are not highly variable, the Dynamic policy is preferable. However, when task sizes show the degree of variability more characteristic of empirically measured workloads, the size-based policy is the best choice. We use the resulting observations to argue in favor of a specific size-based policy, SITA-E, that shows very good performance for realistic task size distributions.     

Receding Horizon Control of Mixed Line Flow Shop Systems

We consider reliable mixed line flow shop systems that are composed of controllable and uncontrollable machines. These systems are assumed to receive arrivals at random instants and process jobs deterministically in the order of arrival so as to depart them before their deadlines that are revealed at the time of arrival. We model these flow shops as serial networks of queues operating under a non-preemptive first-come-first-served policy. Defining completion-time costs for jobs and process costs at controllable machines, a stochastic convex optimization problem is formulated where the control variables are the constrained service times of jobs at the controllable machines. As an on-line solution method to determine these service times, we propose a receding horizon controller, which solves a deterministic problem at each decision instant. We quantify the available future information by the look-ahead window size. Numerical examples demonstrate the value of information and that the no-waiting property of the full-information case is not observed in the partial-information case.     

Task assignment in multiple server farms using preemptive migration and flow control

Existing task assignment policies proposed for assigning tasks in stand-alone server farms are not efficient in multiple server farm environments because they have not been designed to exploit the properties of such environments. With the emergence of high speed networks and operating systems that have features such as preemptive migration, the importance of designing task assignment policies for assigning tasks in multiple server farms has increased. Such policies can result in better overall performance compared to those that optimise performance in stand-alone server farms.This paper proposes a task assignment policy suitable for assigning tasks in multiple server farms. The proposed policy, called Multi-Cluster Task Assignment based on Preemptive Migration (MCTPM) is based on a multi-tier host architecture that reduces the variance of task sizes in host queues by processing tasks with similar sizes using a set of hosts that have a distinct task size range. MCTPM controls the traffic flow into server farms via a global dispatching device so as to optimise the performance. MCTPM supports preemptive task migration between servers in the same farm and between servers in different farms.Performance analysis of the proposed policy indicates that significant performance improvements are possible under a wide range of workload scenarios. For example, MCTPM outperforms existing policies such as MC-Random, MC-TAGSPM and MC-MTTPM by factors of 190, 5 and 10.5 respectively under certain scenarios.