On utility-fair bandwidth adaptation for multi-class traffic QoS provisioning in wireless networks

The ability to adjust the allocated bandwidth of ongoing calls to cope with wireless network resource fluctuations is becoming increasingly important. In this paper, we describe a utility-based bandwidth adaptation scheme for multi-class traffic quality-of-service (QoS) provisioning in wireless networks. With the proposed scheme, each call is assigned a utility function according to its adaptive characteristics. Depending on the network load the allocated bandwidth of ongoing calls are upgraded or degraded dynamically such that each call receives fair utility. The quantization of utility function by dividing the utility range into a fixed number of equal intervals is a key feature of our proposed utility-fair algorithm. Appropriate call admission control and bandwidth reservation policies are also integrated into the proposed scheme to provide QoS guarantees to the new and handoff calls. Extensive simulation experiments have been conducted to evaluate the performance of the proposed scheme compared with two other existing ones. Results show that our bandwidth adaptation scheme is effective in achieving utility fairness while keeping the call blocking and handoff dropping probabilities substantially low.     

Dynamic service migration and workload scheduling in edge-clouds

Edge-clouds provide a promising new approach to significantly reduce network operational costs by moving computation closer to the edge. A key challenge in such systems is to decide where and when services should be migrated in response to user mobility and demand variation. The objective is to optimize operational costs while providing rigorous performance guarantees. In this paper, we model this as a sequential decision making Markov Decision Problem (MDP). However, departing from traditional solution methods (such as dynamic programming) that require extensive statistical knowledge and are computationally prohibitive, we develop a novel alternate methodology. First, we establish an interesting decoupling property of the MDP that reduces it to two independent MDPs on disjoint state spaces. Then, using the technique of Lyapunov optimization over renewals, we design an online control algorithm for the decoupled problem that is provably cost-optimal. This algorithm does not require any statistical knowledge of the system parameters and can be implemented efficiently. We validate the performance of our algorithm using extensive trace-driven simulations. Our overall approach is general and can be applied to other MDPs that possess a similar decoupling property.     

Optimal Threshold Levels in Stochastic Fluid Models via Simulation-based Optimization

A number of important problems in production and inventory control involve optimization of multiple threshold levels or hedging points. We address the problem of finding such levels in a stochastic system whose dynamics can be modelled using generalized semi-Markov processes (GSMP). The GSMP framework enables us to compute several performance measures and their sensitivities from a single simulation run for a general system with several states and fairly general state transitions. We then use a simulation-based optimization method, sample-path optimization, for finding optimal hedging points. We report numerical results for systems with more than twenty hedging points and service-level type probabilistic constraints. In these numerical studies, our method performed quite well on problems which are considered very difficult by current standards. Some applications falling into this framework include designing manufacturing flow controllers, using capacity options and subcontracting strategies, and coordinating production and marketing activities under demand uncertainty.     

A QoS-based dynamic pricing approach for services provisioning in heterogeneous wireless access networks

In this paper we propose a simple QoS-based dynamic pricing approach for services provisioning in a heterogeneous wireless access network environment which attempts to increase user’s satisfaction level by firstly, maximizing the provided QoS level, and secondly, by applying dynamic pricing strategies according to the QoS. These strategies will allow service providers to maximize their profits. Simulation results demonstrate that the proposed dynamic pricing approach benefits both users and wireless service providers (WSPs). Results also suggest that users have better overall satisfaction due to a better QoS level and fairer prices. The analysis shows that our proposed pricing approach contributes to an increase in WSPs profits compared to the application of the flat-rate pricing model in a competitive market-model.     

A wise cost-effective supplying bandwidth policy for multilayer wireless cognitive networks

Inventory management is one of the most important research areas in Operations Research and Logistics. It mainly aims to efficiently manage inventories at different facilities (for example, warehouses and plants in Supply Chains (SCs)), minimizing the total cost and satisfying the service levels. Some exact inventories management approaches are successfully proposed and applied to different real scenarios, traditionally related to the SCs, even if the extreme versatility of these techniques could make them attractive to new challenging scenarios such as those related to telecommunications networks. Starting from this vision, the focus of this paper is to show the new benefits of applying an adaptive period inventory management policy to a wireless cognitive telecommunication scenario in which radio transmission resources are treated as short-term life time goods which supplies wisely in order to maximize both economic profit and quality of service offered to wireless users. The system behavior is tested using an agent-based simulator and computational results show that introducing this wise control on the bandwidth supplying mechanism guarantees a more reactive and effective telecommunication network, reaching a good compromise between the total profit and the service levels.     

Infinitesimal perturbation analysis of a multi-stage tandem of fluid queue with additive loss feedback

In this paper Infinitesimal Perturbation Analysis (IPA) is used to derive the gradient estimators for loss volume and queue workload in a multi-stage tandem of stochastic fluid queues with instantaneous additive loss-feedback for overall congestion control. These gradient estimators are then used to drive a standard stochastic approximation algorithm to optimize, with respect to the buffer limits of the individual queues, an objective function which is the weighted sum of loss volume and queue workload of the queues that make up the tandem.     

An auction mechanism for allocating the bandwidth of networks to their users

We present a mechanism for auctioning bandwidth on a network-wide basis to end users or ISPs that will utilize it for the same time period. This mechanism consists of a set of simultaneous multi-unit descending-price (i.e. Dutch) auctions, one per link of the network. The per unit prices of bandwidth at the various links are asymmetric, thus reflecting the asymmetry of demand for these links. A user can be instantly allocated bandwidth over a certain path, by simultaneously bidding for the quantity desired at all relevant auctions. This winner determination rule is complemented by a payment rule of the VCG (Vickrey–Clarke–Groves) type, which provides users with the incentive to bid truthfully, thus simplifying bidding. Also, the mechanism enables the auctioneer to use his prior information on market demand anticipated and its spreading among the various links in order to set effectively the auction’s parameters. We argue that our mechanism attains nearly efficient allocation of the network’s bandwidth (i.e. the resulting social welfare is close to the respective maximum for the quantity decided to be sold by the auctioneer), while it is simple, scalable and applicable to real networks, even for auctioning the capacity of links owned by multiple providers and then splitting the revenue among them. Alternatively, the mechanism offers the provider the opportunity to optimize his revenue, rather than the social welfare. Since our mechanism’s computational complexity is low it can serve as a fast, practical, and near-optimal solution to a generally NP-hard optimization problem.     

计算机系统与计算机网络中的动态优化:模型、求解与应用

动态优化是计算机系统与计算机网络中进行资源分配与任务调度等方面研究所采用的主要理论工具之一.目前,国内外已开展大量研究,致力于深化动态优化的理论研究与工程应用.文中从模型、求解与应用3个角度,对马尔可夫决策过程动态优化理论模型进行了综述,并重点介绍了将动态优化理论与随机Petri网理论相结合的马尔可夫决策Petri网和随机博弈网模型,详细讨论了这些模型的建模方法、求解算法与一些应用实例.最后,对全文进行了总结,并对未来可能的研究方向进行了展望.     

无线多媒体通信网适应带宽配置在线优化算法

基于强化学习的方法,提出一种无线多媒体通信网适应带宽配置在线优化算法,在满足多类业务不同QoS(quality of service)要求的同时,提高网络资源的利用率.建立事件驱动的随机切换分析模型,将无线多媒体通信网中的适应带宽配置问题转化为带约束的连续时间Markov决策问题.利用此模型的动态结构特性,结合在线学习估计梯度与随机逼近改进策略,提出适应带宽配置在线优化算法.该算法不依赖于系统参数,如呼叫到达率、呼叫持续时间等,自适应性强,计算量小,能够收敛到全局最优,适用于复杂应用环境中无线多媒体通信网适应带宽配置的在线优化.仿真实验结果验证了算法的有效性.     

Infinitesimal Perturbation Analysis and Optimization for Make-to-Stock Manufacturing Systems Based on Stochastic Fluid Models

In this paper we study Make-To-Stock manufacturing systems and seek on-line algorithms for determining optimal or near optimal buffer capacities (hedging points) that balance inventory against stockout costs. Using a zStochastic Fluid Model (SFM), we derive sample derivatives (sensitivities) which, under very weak structural assumptions on the defining demand and service processes, are shown to be unbiased estimators of the sensitivities of a cost function with respect to these capacities. When evaluated based on the sample path of discrete-part systems, we show that these estimators are greatly simplified. Thus, they can be easily implemented and evaluated on line. Though the implementation on discrete-part systems does not necessarily preserve the unbiasedness property, simulation results show that stochastic approximation algorithms that use such estimates do converge to optimal or near optimal hedging points. Supported in part by the National Science Foundation under Grants EEC-0088073 and DMI-0330171, by AFOSR under contract F49620-01-0056, and by ARO under grant DAAD19-01-0610.     

基于MDP支持弹性服务质量的接入控制

在网络服务系统中,满足业务请求的服务质量需求是系统要解决的主要问题之一。接入控制方法和资源分配策略常用来保证业务的服务质量要求。本文基于Markov决策过程(MDP)对视频点播(VOD)系统进行建模,同时考虑了弹性服务质量这一机制。弹性服务质量可以用一个QoS的需求范围来体现。策略梯度算法常用来解决MDP问题,它能够以比较好的速度收敛到最优解。通过算法实例对本文的接入控制方法进行性能分析,发现所采用的方法相对于一般的完全接入策略具有较优的性能。     

Stochastic learning and optimization—A sensitivity-based approach

We introduce a sensitivity-based view to the area of learning and optimization of stochastic dynamic systems. We show that this sensitivity-based view provides a unified framework for many different disciplines in this area, including perturbation analysis, Markov decision processes, reinforcement learning, identification and adaptive control, and singular stochastic control; and that this unified framework applies to both the discrete event dynamic systems and continuous-time continuous-state systems. Many results in these disciplines can be simply derived and intuitively explained by using two performance sensitivity formulas. In addition, we show that this sensitivity-based view leads to new results and opens up new directions for future research. For example, the n th bias optimality of Markov processes has been established and the event-based optimization may be developed; this approach has computational and other advantages over the state-based approaches.     

Optimal resource allocation in synchronized multi-tier Internet services

Modern Internet systems have evolved from simple monolithic systems to complex multi-tiered architectures. For these systems, providing good response time performance is crucial for commercial success. In practice, the response-time performance of multi-tiered systems is often degraded by severe synchronization problems, causing jobs to wait for responses from different tiers. Synchronization between different tiers is a complicating factor in the optimal control and analysis of performance. In this paper, we study a generic multi-tier model with synchronization in a queuing-theoretical setting. The system is able to share processing capacity between arriving jobs that need to be sent to other tiers and the responses that have arrived after processing from these tiers. We provide structural results on the optimal resource allocation policy and provide a full characterization of the policy in the framework of Markov decision theory. We also highlight important effects of synchronization in the model. We validate our expressions through extensive experimentations for a wide range of resource configurations.     

动态电源管理的随机切换模型与在线优化

考虑系统参数未知情况下的动态电源管理问题,提出一种基于强化学习的在线策略优化算法. 通过建立事件驱动的随机切换分析模型,将动态电源管理问题转化为带约束的Markov 决策过程的策略优化问题. 利用此模型的动态结构特性,结合在线学习估计梯度与随机逼近改进策略,提出动态电源管理策略的在线优化算法．随机切换模型对电源管理系统的动态特性描述精确,在线优化算法自适应性强,运算量小,精度高,具有较高的实际应用价值．     

Actor-critic algorithms for hierarchical Markov decision processes

We consider the problem of control of hierarchical Markov decision processes and develop a simulation based two-timescale actor-critic algorithm in a general framework. We also develop certain approximation algorithms that require less computation and satisfy a performance bound. One of the approximation algorithms is a three-timescale actor-critic algorithm while the other is a two-timescale algorithm, however, which operates in two separate stages. All our algorithms recursively update randomized policies using the simultaneous perturbation stochastic approximation (SPSA) methodology. We briefly present the convergence analysis of our algorithms. We then present numerical experiments on a problem of production planning in semiconductor fabs on which we compare the performance of all algorithms together with policy iteration. Algorithms based on certain Hadamard matrix based deterministic perturbations are found to show the best results.     

Optimization-based resource allocation in communication networks

The continuously growing number of applications competing for resources in current communication networks highlights the necessity for efficient resource allocation mechanisms to maximize user satisfaction. Optimization Theory can provide the necessary tools to develop such mechanisms that will allocate network resources optimally and fairly among users. The aim of this paper is to provide a starting point for researchers interested in applying optimization techniques in the resource allocation problem for current communication networks. To achieve that we, first, describe the fundamental optimization theory tools necessary to design optimal resource allocation algorithms. Then, we describe the Network Utility Maximization (NUM) framework, a framework that has already found numerous applications in network optimization, along with some recent advancements of the initial NUM framework. Finally, we summarize some of our recent work in the area and discuss some of the remaining research challenges towards the development of a complete optimization-based resource allocation protocol.     

A pricing approach for bandwidth allocation in differentiated service networks

We present a decentralized auction-based scheme for bandwidth allocation and pricing in a differentiated service-based network. Different classes of clients provide their own expected bandwidth price and required amount of bandwidth. A service provider decides the admission price and differentiated service provided for each class of clients. We introduce mathematical formulations and provide a solution approach to maximize the service provider's revenue. For a single bottleneck link case, a polynomial-time algorithm is developed to obtain an optimal solution. For a multiple bottleneck link case, a heuristic algorithm is developed to solve the problem. The effectiveness of our solution approach is validated by simulation results, which compare our algorithms against the traditional flat-rate pricing approach.     

On the existence of stationary optimal policies for partially observed MDPs under the long-run average cost criterion

This paper studies the problem of the existence of stationary optimal policies for finite state controlled Markov chains, with compact action space and imperfect observations, under the long-run average cost criterion. It presents sufficient conditions for existence of solutions to the associated dynamic programming equation, that strengthen past results. There is a detailed discussion comparing the different assumptions commonly found in the literature.     

The application of DBF neural networks for object recognition

On the basis of DBF nets proposed by Wang Shoujue, the model and properties of DBF neural network were discussed in this paper. When applied in pattern recognition, the algorithm and implement on hardware were presented respectively. We did experiments on recognition of omnidirectionally oriented rigid objects on the same level, using direction basis function neural networks, which acts by the method of covering the high dimensional geometrical distribution of the sample set in the feature space. Many animal and vehicle models (even with rather similar shapes) were recognized omnidirectionally thousands of times. For total 8800 tests, the correct recognition rate is 98.75%, the error rate and the rejection rate are 0.5% and 1.25% respectively.     

串行生产线的参数优化

对随机离散事件系统模型,用实验(或模拟)方法进行扰动分析(Perturbation Analysisi,简称PA),对固定的样本,得到性能指标(设为J(θ))对可调参数θ的梯度dJ(θ)/dθ的估计.用固定长度的观测值(如L个顾客)估计dJ(θ)/dθ,将估计值代入随机逼近算法,递推地求最优参数,得到了基于扰动分析的优化算法.实验结果表明.这种优化算法,有较好的收敛速度.对串行生产线,提出每离开L个顾客递推一次参数的优化算法,并证明了这种算法可收敛到使J(θ)达极小的θ.