Modeling and analysis of the effects of QoS and reliability on pricing, profitability, and risk management in multiperiod grid-computing networks

In this paper we develop a network equilibrium model for optimal pricing and resource allocation in Computational Grid Network. We consider a general network economy model with Grid Resource Providers, Grid Resource Brokers and Grid Users. The proposed framework allows for the modeling and theoretical analysis of Computational Grid Markets that considers a non-cooperative behavior of decision-makers in the same tier of the grid computing network (such as, for example, Grid Resource Providers) as well as cooperative behavior between tiers (between Resource Providers and Grid Brokers). We introduce risk management into the decision making process by analyzing the decision-marker's reliability and quality of service (QoS) requirement. We analyze resource allocation patterns as well as equilibrium price based on demand, supply, and cost structure of the grid computing market network. We specifically answer the following questions with several numerical examples: How do system reliability levels affect the QoS levels of the service providers and brokers under competition? How do system reliability levels affect the profits of resource providers and brokers in a competitive market? How do system reliability levels influence the pricing of the services in a competitive environment? How do users' service request types, QoS requirements, and timing concerns affect users' behaviors, costs and risks in equilibrium? How does the market mechanism allocate resources to satisfy the demands of users? We find that for users who request same services certain timing flexibility can not only reduce the costs but also lower the risks. The results indicated that the value of QoS can be efficiently priced based on the heterogeneous service demands.     

Bertrand equilibria and efficiency in markets for congestible network services

This paper is motivated by study of the economics of Quality of Service (QoS) of congestible services. We introduce a queueing game framework to study such problems. We consider multiple competing providers, each offering a queued service. Users are sensitive to both access price and expected delay, and pick providers with the smallest price plus delay cost. We study equilibrium of the pricing (Bertrand) game between the congestible network service providers. We establish the existence of a Nash equilibrium under some natural assumptions. We then consider a setting with multiple classes of differentiated service. Differentiated Services (DiffServ) technologies of the Internet that can provide QoS guarantees have failed to catch on, primarily due to economic impediments. Each provider is now modeled as operating a multi-class queue. We provide sufficient conditions for the existence of a Nash equilibrium in the Bertrand (pricing) game between the providers. We characterize the inefficiency (price of anarchy) due to strategic pricing to be 2/3. Surprisingly, the price of anarchy for the multi-class setting is the same as for the single-class setting.     

SPAD: A distributed middleware architecture for QoS enhanced alternate path discovery

In the next generation Internet, the network will evolve from a plain communication medium into one that provides endless services to the users. These services will be composed of multiple cooperative distributed application elements. We name these services overlay applications. The cooperative application elements within an overlay application will build a dynamic communication mesh, namely an overlay association. The Quality of Service (QoS) perceived by the users of an overlay application greatly depends on the QoS experienced on the communication paths of the corresponding overlay association. In this paper, we present super-peer alternate path discovery (SPAD), a distributed middleware architecture that aims at providing enhanced QoS between end-points within an overlay association. To achieve this goal, SPAD provides a complete scheme to discover and utilize composite alternate end-to-end paths with better QoS than the path given by the default IP routing mechanisms.     

A Novel Approach to Charge for IP Services with QoS Support

If the Internet is to become a network supporting differentiated application and transfer services, advanced architectures must be deployed to efficiently support hard Quality of Service (QoS) and usage-based charging. In this paper we present a novel pricing scheme for IP services with guaranteed quality. Our approach is built on the basis of the virtual delay, which is a novel, simple and effective QoS index that describes an advanced IP service. We propose a model to compute the virtual delay from a purely technical point of view, taking into account not only guaranteed performance, but also traffic and system parameters. We then analyze the sensitivity of both the virtual delay and the tariff towards the involved parameters, taking into account both the users’ benefit and the operators’ income. We also extend the pricing model to make it dependent on service demand. Finally, we also present an economic analysis, the aim of which is to establish a model to set the QoS level and the relevant price, taking into account revenue, social fairness, and service availability.

Utilizing call admission control for pricing optimization of multiple service classes in wireless cellular networks

In this paper, we utilize admission control algorithms designed for revenue optimization with QoS guarantees to derive optimal pricing of multiple service classes in wireless cellular networks. A service provider typically adjusts pricing only periodically. Once a “global” optimal pricing is derived, it would stay static for a period of time, allowing users to be charged with the same rate while roaming. We utilize a hybrid partitioning-threshold admission control algorithm to analyze a pricing scheme that correlates service demand with pricing, and to periodically determine optimal pricing under which the system revenue is maximized while guaranteeing that QoS requirements of multiple service classes are satisfied.     

Efficiency loss in a network resource allocation game: the case of elastic supply

We consider a resource allocation problem where individual users wish to send data across a network to maximize their utility, and a cost is incurred at each link that depends on the total rate sent through the link. It is known that as long as users do not anticipate the effect of their actions on prices, a simple proportional pricing mechanism can maximize the sum of users' utilities minus the cost (called aggregate surplus). Continuing previous efforts to quantify the effects of selfish behavior in network pricing mechanisms, we consider the possibility that users anticipate the effect of their actions on link prices. Under the assumption that the links' marginal cost functions are convex, we establish existence of a Nash equilibrium. We show that the aggregate surplus at a Nash equilibrium is no worse than a factor of 4/spl radic/2-5 times the optimal aggregate surplus; thus, the efficiency loss when users are selfish is no more than approximately 34%.     

Mobility management in ubiquitous environments

Ubiquitous computing is aiming at providing users with intelligent human-centric context-aware services at anytime anywhere. However, mobility increases dynamism and uncertainty conditions. This study therefore explores the management and uses of various contexts for automatically providing appropriate services to individual users. This issue is explored from an open framework perspective referred to as ubiquitous gate (U-gate). In this framework, a distributed context management architecture and a communication model based on standard protocols are proposed. To fit user requirements and to achieve complete mobility management, a context-aware path planning mechanism (UbiPaPaGo) and a context-aware handoff mechanism (UbiHandoff) are proposed based on context stored in an open and distributed context management server U-gate. Based on the path planning results of UbiPaPaGo, UbiHandoff derives a minimum access point (AP) handoff plan that satisfies multiple QoS requirements for individual users and services. The UbiHandoff mechanism includes multiple-attribute decision making method (MADM)–based handoff planning, referred to as MADM-based UbiHandoff, and genetic algorithm (GA)–based handoff planning, referred to as GA-based UbiHandoff. In the proposed MADM-based UbiHandoff, analytic hierarchy process (AHP) and technique for order preference by similarity to ideal solution (TOPSIS) provide efficient and seamless AP handoff to gain higher QoS performance. In GA-based UbiHandoff, genetic algorithm is employed to minimize handoff by finding appropriate APs along the path under QoS constraints. Finally, the effectiveness of the proposed mechanisms is evaluated through simulations. Numerical results demonstrate that both mechanisms minimize handoffs and ensure compliance with QoS requirements.     

基于模糊积分和博弈论的QoS组播路由机制

下一代互联网NGI(next generation Intemet)需要提供服务质量QoS(quality of service)路由能力.由于NGI网络状态难以精确测量与表达,因此,QoS路由基于的信息应该是模糊的.随着网络运营的渐趋商业化,付费上网要求实现QoS计费,而网络提供方与用户的利益冲突要求实现效用双赢.设计了一种基于模糊积分和博弈论的QoS组播路由机制.该机制由边评判、博弈分析和组播路由树建立算法组成,基于模糊积分和适合隶属度函数对边进行模糊综合评判,通过博弈分析确定网络提供方与用户在边上的效用能否达到Nash均衡,通过组播路由树建立算法使得在建立的组播路由树上不仅用户QoS要求得到满足,而且网络提供方效用与用户效用达到或接近Nash均衡下的Pareto最优.仿真结果表明,与QoSMIC等机制相比,该机制具有较好的性能.     

Genetic algorithms for route discovery.

Packet routing in networks requires knowledge about available paths, which can be either acquired dynamically while the traffic is being forwarded, or statically (in advance) based on prior information of a network's topology. This paper describes an experimental investigation of path discovery using genetic algorithms (GAs). We start with the quality-of-service (QoS)-driven routing protocol called "cognitive packet network" (CPN), which uses smart packets (SPs) to dynamically select routes in a distributed autonomic manner based on a user's QoS requirements. We extend it by introducing a GA at the source routers, which modifies and filters the paths discovered by the CPN. The GA can combine the paths that were previously discovered to create new untested but valid source-to-destination paths, which are then selected on the basis of their "fitness." We present an implementation of this approach, where the GA runs in background mode so as not to overload the ingress routers. Measurements conducted on a network test bed indicate that when the background-traffic load of the network is light to medium, the GA can result in improved QoS. When the background-traffic load is high, it appears that the use of the GA may be detrimental to the QoS experienced by users as compared to CPN routing because the GA uses less timely state information in its decision making.     

Unlocking the Advantages of Dynamic Service Selection and Pricing

Bandwidth limitations, resource greedy applications verbose mark-up languages and an increasing number of voice and data users are straining the air interface of wireless networks. Hence, novel approaches and new algorithms to manage wireless bandwidth are needed. In addition, usage based pricing is becoming increasingly prevalent (pre-paid cell phones, calling cards, non-contract minutes, etc.). This paper unlocks the potential to improving the performance of overall system behavior by allowing users to change service level and/or service provider for a (small) price. The ability to dynamically re-negotiate service gives the user the power to control QoS while minimizing usage cost. On the other hand, the ability to change service level pricing dynamically allows the service providers to manage traffic better, improve resource usage and most importantly maximize their profit. This provides a surprising win-win situation for BOTH the service providers AND the users. In this paper we present easy to implement on-line algorithms to minimize the overall usage cost to individual mobile users. This on-line algorithm continuously receives pricing information and evaluates minimum QoS requirements. The algorithm then determines appropriate service level, chooses a service provider and sets a time for re-negotiation dynamically. Our algorithm can handle many practical issues such as capacity limitations, arbitrary price fluctuations and loss/gain of service providers due to mobility. Our results do not assume any specific technologies and can be applied to any environment that can employ dynamic pricing, including wired networks. In fact, dynamic pricing is becoming increasingly desirable since service provider and capacity changes are a growing by-product of mobility. Arriving and departing users at/from a cell tower (or wireless LAN) can effectively reduce or increase the available bandwidth in a cell (or LAN transmission area) and represents a natural opportunity for a pricing change.     

基于贝叶斯策略的网格资源分配方法

考虑网格应用QoS需求,以最大化网格系统的经济收益为目标,提出了一种基于贝叶斯策略的网格资源分配方法。该方法基于价格可代表资源QoS综合性能的思想,利用历史QoS匹配记录,运用朴素贝叶斯定理根据用户提交的价格参数来分配与其级别相对应的符合要价范围资源,并优先考虑QoS水平较高的任务,将当前时刻QoS水平较高的资源预留给下一时刻到达的QoS水平较高的任务,而忽略当前时刻QoS水平较低的任务。实验结果表明,该资源分配方法不仅能有效地保障用户QoS,而且能使网格系统获得较大的经济收益。     

基于组织进化的ABC支持型单播路由机制

提出一种支持总最佳连接ABC(Always Best Connected)的服务质量QoS(Quality of Scrvicc)单播路由机制。该机制采用区间形式刻画用户QoS需求和网络链路参数;引入偏好序列,以满足用户对不同类型网络的偏爱;引入概率密度函数、满意度函数和评价函数,以精确测量网络链路参数值和准确表达用户QoS需求;引入成本、价格、费用和博弈机制,兼顾用户和网络提供方利益;基于组织进化算法OEA(Organizational Evolutionary Algorithm),寻找使各方效用达到或接近Nash均衡下Paret。最优的QoS单播路径。仿真结果表明,该机制是可行和有效的。     

Highly responsive and efficient QoS routing using pre- and on-demand computations along with a new normal measure

Multi-constrained path (MCP) selection is one of the great challenges that QoS routing (QoSR) faces. To address it in an efficient and highly responsive manner, we propose a new QoSR algorithm, namely NM_MCP (normal measure-based multiple constrained path). Using the Dijkstra’s algorithm with respect to each link metric, NM_MCP pre-computes k primary paths in advance, where k is the number of link weights. When a routing request arrives, NM_MCP executes a modified version of the Dijkstra’s algorithm using a newly proposed, normal-measure-based nonlinear cost function. Extensive simulations show that NM_MCP achieves higher success rate in finding feasible paths with less computational cost than existing algorithms. To further improve the performance, we incorporate Pareto and nonlinear look-ahead mechanisms into the algorithm.     

认知无线电网络中基于公平性的功率控制方案

针对现有非合作功率控制博弈算法中存在用户“远近性公平”问题,在主次用户共享频谱的认知无线电上行链路中,给出一种基于代价函数的高效和公平的功率控制博弈算法。在该博弈模型中,代价函数的设定依据次用户接收端信号质量需满足次用户的服务质量要求。改进后的效用函数能够同时兼顾认知无线电系统的总吞吐量和次用户获取资源的公平性,并利用超模理论证明了该模型存在纳什均衡,然后得到求解发射功率纳什均衡解的迭代过程。仿真结果表明,相比已有的研究,该算法不仅能提高认知系统的吞吐量,还能降低发射功率,改善系统效用,而且兼顾了远近用户吞吐量的公平性。     

Online pricing for bandwidth provisioning in multi-class networks

We consider the problem of pricing for bandwidth provisioning over a single link, where users arrive according to a known stochastic traffic model. The network administrator controls the resource allocation by setting a price at every epoch, and each user’s response to the price is governed by a demand function. We formulate this problem as a partially observable Markov decision process (POMDP), and explore two novel pricing schemes––reactive pricing and spot pricing––and compare their performance to appropriately tuned flat pricing. We use a gradient-ascent approach in all the three pricing schemes. We provide methods for computing unbiased estimates of the gradient in an online (incremental) fashion. Our simulation results show that our novel schemes take advantage of the known underlying traffic model and significantly outperform the model-free pricing scheme of flat pricing.     

Game theoretic distributed uplink power control for CDMA networks with real-time services

In this paper, the issue of efficient power allocation in the uplink of CDMA wireless networks supporting real-time services with various QoS constraints, is addressed. Within the proposed framework, utility functions are adopted to reflect a user’s degree of satisfaction with respect to its actual throughput requirements satisfaction and respective power consumption. The corresponding problem is formulated as a non-cooperative game where users aim selfishly at maximizing their utility-based performance under the imposed limitations. The existence and uniqueness of a Nash equilibrium point of the proposed Uplink Power Control (UPC) game is proven, at which all users have attained a targeted SINR threshold value or transmit with their maximum power, leading essentially to an SINR-balanced system. Moreover, a distributed iterative algorithm for reaching UPC game’s equilibrium is provided. The properties of equilibrium in a pure optimization theoretical framework are studied, and the tradeoffs between users’ overall throughput performance and real-time services’ QoS requirements satisfaction, in channel aware resource allocation processes, are revealed and quantified. Through modeling and simulation the efficacy of the introduced framework and proposed UPC algorithm are demonstrated and evaluated.     

SLA-controlled interconnection charging in next generation networks

Next generation network (NGN) should facilitate a single party to establish quality of service (QoS) enabled path between the two IP providers mutually interconnected by one or more transit providers. For that purpose, an end-to-end service level agreement (SLA) should be negotiated and maintained. In this article, we propose interconnection charging, which is controlled by the end-to-end SLA. Relationships between the required, offered, and actually achieved inter-provider QoS are quantified through the degrees of offering and provisioning, at both end-to-end and per-domain levels. Nominal retail price offered to end users and interconnection costs related with particular SLA are then corrected if needed, depending on the offered and provisioned QoS levels. We further propose five policies for interconnection charging and compare them under different QoS provisioning scenarios. Results of the analysis indicate that a properly selected SLA-controlled interconnection charging policy should encourage providers: (1) to offer services with different QoS levels; (2) to offer service that perfectly or most approximately matches the required QoS and (3) to achieve the contracted QoS level.     

Competition yields efficiency in load balancing games

We study a nonatomic congestion game with N parallel links, with each link under the control of a profit maximizing provider. Within this ‘load balancing game’, each provider has the freedom to set a price, or toll, for access to the link and seeks to maximize its own profit. Given prices, a Wardrop equilibrium among users is assumed, under which users all choose paths of minimal and identical effective cost. Within this model we have oligopolistic price competition which, in equilibrium, gives rise to situations where neither providers nor users have incentives to adjust their prices or routes, respectively. In this context, we provide new results about the existence and efficiency of oligopolistic equilibria. Our main theorem shows that, when the number of providers is small, oligopolistic equilibria can be extremely inefficient; however as the number of providers N grows, the oligopolistic equilibria become increasingly efficient (at a rate of 1/N) and, as N→∞, the oligopolistic equilibrium matches the socially optimal allocation.     

Managing database server performance to meet QoS requirements in electronic commerce systems

The performance of electronic commerce systems has a major impact on their acceptability to users. Different users also demand different levels of performance from the system, that is, they will have different Quality of Service (QoS) requirements. Electronic commerce systems are the integration of several different types of servers and each server must contribute to meeting the QoS demands of the users. In this paper we focus on the role, and the performance, of a database server within an electronic commerce system. We examine the characteristics of the workload placed on a database server by an electronic commerce system and suggest a range of QoS requirements for the database server based on this analysis of the workload. We argue that a database server must be able to dynamically reallocate its resources in order to meet the QoS requirements of different transactions as the workload changes. We describe Quartermaster, which is a system to support dynamic goal-oriented resource management in database management systems, and discuss how it can be used to help meet the QoS requirements of the electronic commerce database server. We provide an example of the use of Quartermaster that illustrates how the dynamic reallocation of memory resources can be used to meet the QoS requirements of a set of transactions similar to transactions found in an electronic commerce workload. We briefly describe the memory reallocation algorithms used by Quartermaster and present experiments to show the impact of the reallocations on the performance of the transactions. Published online: 22 August 2001     

Scheduling of a meta-task with QoS requirements in heterogeneous computing systems

Due to the development of new applications and the increasing number of users with diverse needs who are exposed to heterogeneous computing (HC), providing users with quality of service (QoS) guarantees while executing applications has become a crucial problem that needs to be addressed. Motivated by this fact, this paper investigates the problem of scheduling a set of independent tasks with multiple QoS needs, which may include timeliness, reliability, security, data accuracy, and priority, in a HC system. This problem is referred to as the QoS-based scheduling problem and proved to be NP-hard. In the first part of this study, we formulate the QoS-based scheduling problem by using utility and penalty functions, where a utility function associated with a task is used to measure how much the owner of this task will benefit from a given scheduling decision, while penalty functions associated with resources are used to provide incentives to users to set their QoS requirements in accordance with their needs. In order to solve the QoS-based scheduling problem, a computationally efficient static scheduling algorithm (QSMTS_IP) which assumes time-invariant penalty functions is developed. We later extend the QSMTS_IP to the case where penalty functions are time varying. Furthermore, it is shown that the QSMTS_IP can be modified to run as a dynamic scheduling algorithm. The simulation studies carried out show that the QSMTS_IP is capable of meeting diverse QoS requirements of many users simultaneously, while minimizing the number of users whose tasks cannot be scheduled due to the scarcity of machines.