基于拍卖机制的网格资源分配方法

网格资源的动态性、异构性、自治性等特点,使得网格资源分配成为一个难点。目前存在的大多数分配方法仅关注分配效率,却对提高资源分配的公平性缺乏深入的研究。针对此问题,提出一种基于拍卖机制的网格资源分配方法,利用资源分配比例的算法分配资源。通过仿真实验表明该方法适合网格系统中的资源分配,能有效分配资源,提高了资源利用率,同时资源分配的公平性也得到显著的提高。     

Congestion control in utility fair networks

This paper deals with a congestion control framework for elastic and real-time traffic, where the user’s application is associated with a utility function. We allow users to have concave as well as non-concave utility functions, and aim at allocating bandwidth such that utility values are shared fairly. To achieve this, we transform all utilities into strictly concave second order utilities and interpret the resource allocation problem as the global optimization problem of maximizing aggregate second order utility. We propose a new fairness criterion, utility proportional fairness, which is characterized by the unique solution to this problem. Our fairness criterion incorporates utility max–min fairness as a limiting case. Based on our analysis, we obtain congestion control laws at links and sources that (i) are linearly stable regardless of the network topology, provided that a bound on round-trip-times is known, (ii) provide a utility proportional fair resource allocation in equilibrium. We further investigate the efficiency of utility fair resource allocations. Our measure of efficiency is defined as the worst case ratio of the total utility of a utility proportional fair rate vector and the maximum possible total utility. We present a generic technique, which allows to obtain upper bounds on the efficiency loss. For special cases, such as linear and concave utility functions, and non-concave utility functions with bounded domain, we explicitly calculate such upper bounds. Then, we study utility fair resource allocations with respect to bandwidth fairness. We derive a fairness metric assessing the aggressiveness of utility functions. This allows us to design fair utility functions for various applications. Finally, we simulate the proposed algorithms using the NS2 simulator.     

EGALITARIAN NEGOTIATIONS IN AGENT SOCIETIES

Achieving fairness among the members of a society is an important issue in many resource allocation problems. The increasing focus of the computer sciences community is motivated by a large panel of applications where other welfare notions do not suit. Centralized approaches are usually used, but they suffer from important drawbacks. Because relationships among society members are not considered, the provided resource allocation may not be achievable in practice. This study seeks to provide an evenly distributed approach based on a multiagent system, which overcomes the main drawbacks of centralized approaches. We provide an adaptive, anytime, and scalable algorithm to hold efficient egalitarian negotiations. Negotiation processes lead to socially efficient allocations as an emergent phenomenon. We also evaluate the “price of the social graph” toward the negotiation efficiency, and we provide the agent behavior to implement in order to achieve fair allocations.     

多媒体系统多资源分配中效率与公平性的权衡

针对多媒体系统多资源分配问题,提出了一种权衡效率与公平性的有效方法。分析 -公平性与系统效用及公平性指标的关系,提出利用 -公平性来实现两者之间的权衡,并验证其合理性。为了获得满足 -公平性的资源分配,提出了一种基于定价机制的多资源分配算法。仿真结果表明,所提出的多资源分配算法能够在较短时间内获得近似最优的资源分配;通过调整 值能够实现效率与公平性之间的权衡, 值越大,越强调公平性。     

Fairness in broadband ISDNs

In order to achieve satisfactory performance in broadband Integrated Services Digital Networks (ISDNs), some techniques to control flow of information traffic, are necessary. Bandwidth allocation, bandwidth enforcement, and load balancing, are some of the examples of these techniques. Unfortunately, some of these techniques result in unfair distribution of resources among users. Recently, fairness in resource sharing systems has received significant attention among researchers.

In this paper, we discuss, in comparative terms, several resource allocation techniques along with their fairness aspects in broadband ISDNs. We will also propose a threshold-based scheme to minimize the blocking probability and improve fairness.     

The Efficiency of Fair Division

In this paper we study the impact of fairness on the efficiency of allocations. We consider three different notions of fairness, namely proportionality, envy-freeness, and equitability for allocations of divisible and indivisible goods and chores. We present a series of results on the price of fairness under the three different notions that quantify the efficiency loss in fair allocations compared to optimal ones. Most of our bounds are either exact or tight within constant factors. Our study is of an optimistic nature and aims to identify the potential of fairness in allocations.     

异构云计算体系结构及其多资源联合公平分配策略

资源分配策略是当前云计算研究领域中的一个重要研究热点,异构云计算体系结构下的复杂应用问题研究中,最基本的问题在于如何将总体有限的资源分配给多个租户或应用,以达到效率或收效最大化.但是,在经典的资源分配问题中,任务或者用户往往是“贪婪”的;因此,在总体资源有限的前提下,资源分配的公平性就显得尤为重要.为了满足不同的任务需求,达到多种资源分配的公平性,设计了一个虚拟化的异构云计算体系结构,提出了该体系结构下基于占优资源的多资源联合公平分配算法(maximizing multi-resource fairness based on dominant resource, MDRF),并且证明了算法的帕累托等相关属性;给出了占优资源熵(dominant resource entropy, DRE)和占优资源权重(dominant resource weight, DRW)的定义,占优资源熵更加精确地刻画了用户资源请求与任务所调度到的服务器资源之间的适应程度,使系统的自适应能力更强同时提高了资源利用率.占优资源权重保障了用户优先获取资源的优先次序,协同所采用保障公平性的Max-Min Fairness策略,使资源的分配更加有序.实验表明,我们的策略有更高的系统资源利用率,并且使需求与供给更加匹配,进而使用户的占优资源获取更多,提高了服务质量.     

Model checking with fairness assumptions using PAT

Recent development on distributed systems has shown that a variety of fairness constraints (some of which are only recently defined) play vital roles in designing self-stabilizing population protocols. Existing model checkers are deficient in verifying the systems as only limited kinds of fairness are supported with limited verification efficiency. In this work, we support model checking of distributed systems in the toolkit PAT (process analysis toolkit), with a variety of fairness constraints (e.g., process-level weak/strong fairness, event-level weak/strong fairness, strong global fairness). It performs on-the-fly verification against linear temporal properties. We show through empirical evaluation (on recent population protocols as well as benchmark systems) that PAT has advantage in model checking with fairness. Previously unknown bugs have been revealed against systems which are designed to function only with strong global fairness.     

SPRITE: a novel strategy-proof multi-unit double auction scheme for spectrum allocation in ubiquitous communications

With the increasing number of handheld and mobile devices, the demand for available spectrum resource is experiencing a rapid growth. Auction has been widely used for spectrum resource allocation in ubiquitous communications due to its fairness. However, many existing spectrum auction schemes inherently limit users’ ability to fully utilize the spectrum due to the assumption that the spectrum resource is single unit and indivisible. Besides, most of them fail to take into account of buyer/seller’s distinctive demands in auction and consider spectrum allocation as single-sided auction. In this paper, we consider the multi-unit double auction problem under the context that multiple buyers/sellers have different demands to buy/sell. Particularly, we present a novel strategy-proof multi-unit double auction scheme (SPRITE). SPRITE establishes a series of bid-related buyer group construction and winner determination strategies. It improves the spectrum reusability and achieves sound spectrum utilization, fairness, and essential economic properties. In the theoretical analysis, we have shown the correctness, effectiveness, and economic properties of SPRITE and prove that SPRITE is strategy-proof. In the evaluation study, we further show that SPRITE can achieve multi-unit spectrum auction with better auction efficiency compared with existing double auction mechanisms. To the best of our knowledge, SPRITE is the first multi-unit double auction approach that guarantees the competitive fairness among buyers while remaining strategy-proof for spectrum allocation. Furthermore, the multi-unit double auction mechanism proposed in this work helps increasing flexibility of the ubiquitous devices for spectrum usage.     

Distributed resource management with heterogeneous linear controls

Relative differentiation in distributed resource sharing can be implemented using heterogeneous linear controls with binary feedback and this method can provide efficient and weighted max–min fair resource allocations. We prove this using a discrete-time model of a single resource, shared among a number of users with heterogeneous Additive Increase Multiplicative Decrease (AIMD) controls. AIMD has been implemented in the congestion avoidance mechanism of Internet's Transmission Control Protocol (TCP) and beyond its simplicity it has been proved extremely efficient and robust. We show how AIMD can be parametrized in order to allow the scaling of user allocations according to a given set of weights. We also analyze the effects of different parameter choices on the performance and the oscillating behaviour of the system. Our analysis is supported by simulations and the results provide useful insights to the performance and the properties of distributed resource sharing.     

Competitive online adaptive scheduling for sets of parallel jobs with fairness and efficiency

We study online adaptive scheduling for multiple sets of parallel jobs, where each set may contain one or more jobs with time-varying parallelism. This two-level scheduling scenario arises naturally when multiple parallel applications are submitted by different users or user groups in large parallel systems, where both user-level fairness and system-wide efficiency are of important concerns. To achieve fairness, we use the well-known equi-partitioning algorithm to distribute the available processors among the active job sets at any time. For efficiency, we apply a feedback-driven adaptive scheduler that periodically adjusts the processor allocations within each set by consciously exploiting the jobs’ execution history. We show that our algorithm achieves asymptotically competitive performance with respect to the set response time, which incorporates two widely used performance metrics, namely, total response time and makespan, as special cases. Both theoretical analysis and simulation results demonstrate that our algorithm improves upon an existing scheduler that provides only fairness but lacks efficiency. Furthermore, we provide a generalized framework for analyzing a family of scheduling algorithms based on feedback-driven policies with provable efficiency. Finally, we consider an extended multi-level hierarchical scheduling model and present a fair and efficient solution that effectively reduces the problem to the two-level model.     

Hierarchical Scheduling for Symmetric Multiprocessors

Hierarchical scheduling has been proposed as a scheduling technique to achieve aggregate resource partitioning among related groups of threads and applications in uniprocessor and packet scheduling environments. Existing hierarchical schedulers are not easily extensible to multiprocessor environments because 1) they do not incorporate the inherent parallelism of a multiprocessor system while resource partitioning and 2) they can result in unbounded unfairness or starvation if applied to a multiprocessor system in a naive manner. In this paper, we present hierarchical multiprocessor scheduling (H-SMP), a novel hierarchical CPU scheduling algorithm designed for a symmetric multiprocessor (SMP) platform. The novelty of this algorithm lies in its combination of space and time multiplexing to achieve the desired bandwidth partition among the nodes of the hierarchical scheduling tree. This algorithm is also characterized by its ability to incorporate existing proportional-share algorithms as auxiliary schedulers to achieve efficient hierarchical CPU partitioning. In addition, we present a generalized weight feasibility constraint that specifies the limit on the achievable CPU bandwidth partitioning in a multiprocessor hierarchical framework and propose a hierarchical weight readjustment algorithm designed to transparently satisfy this feasibility constraint. We evaluate the properties of H-SMP using hierarchical surplus fair scheduling (H-SFS), an instantiation of H-SMP that employs surplus fair scheduling (SFS) as an auxiliary algorithm. This evaluation is carried out through a simulation study that shows that H-SFS provides better fairness properties in multiprocessor environments as compared to existing algorithms and their naive extensions.     

Resource allocation in decentralised computational systems: an evolutionary market-based approach

We present a novel market-based method, inspired by retail markets, for resource allocation in fully decentralised systems where agents are self-interested. Our market mechanism requires no coordinating node or complex negotiation. The stability of outcome allocations, those at equilibrium, is analysed and compared for three buyer behaviour models. In order to capture the interaction between self-interested agents, we propose the use of competitive coevolution. Our approach is both highly scalable and may be tuned to achieve specified outcome resource allocations. We demonstrate the behaviour of our approach in simulation, where evolutionary market agents act on behalf of service providing nodes to adaptively price their resources over time, in response to market conditions. We show that this leads the system to the predicted outcome resource allocation. Furthermore, the system remains stable in the presence of small changes in price, when buyers’ decision functions degrade gracefully.     

Max-Min Fair Scheduling in Input-Queued Switches

Fairness in traffic management can improve the isolation between traffic streams, offer a more predictable performance, eliminate transient bottlenecks, mitigate the effect of certain kinds of denial-of-service attacks, and serve as a critical component of a quality-of-service strategy to achieve certain guaranteed services such as delay bounds and minimum bandwidths. In this paper, we choose a popular notion of fairness called max-min fairness and provide a rigorous definition in the context of input-queued switches. We show that being fair at the output ports alone or at the input ports alone or even at both input and output ports does not actually achieve an overall max-min fair allocation of bandwidth in a switch. Instead, we propose a new algorithm that can be readily implemented in a distributed fashion at the input and output ports to determine the exact max-min fair rate allocations for the flows through the switch. In addition to proving the correctness of the algorithm, we propose a practical scheduling strategy based on our algorithm. We present simulation results, using both real traffic traces and synthetic traffic, to evaluate the fairness of a variety of popular scheduling algorithms for input-queued switches. The results show that our scheduling strategy achieves better fairness than other known algorithms for input-queued switches and, in addition, achieves throughput performance very close to that of the best schedulers.     

CSFQ算法分析与改进

核心无状态公平队列调度（CSVQ）算法提供了如同有状态网那样好的公平带宽分配,但它的丢包算法不适用于TCP流。针对TCP流的特点,对CSFQ算法进行如下改进：将缓存队列长度与丢包概率关联起来,用一种类似于RED（random early drop）缓存管理方法解决了缓存频繁溢出导致的一些问题;对TCP流的丢包率进行修正,使用多余带宽来转发TCP包,解决TCP流与UDP流的带宽分配公平性。仿真试验表明,新算法NEW-CSFQ更好地提供数据流公平的频宽共享,对突发流响应较原算法有所提高,且算法复杂度简单,容易在高速核心路由器上实现。     

Using traffic asymmetry to enhance TCP performance

A wealth of recent work has gone into optimizing the performance of Transmission Control Protocol (TCP) on the downlink channel of wireless networks such as for example, honing its congestion awareness mechanism so that it is minimally affected by random wireless losses, and optimizing achieved fairness of the end-to-end TCP rates. Other work has gone into balancing the allocation of a shared resource between the downlink and uplink in order to optimize TCP performance. We build on such previous research by proposing a cross-layer algorithm for resource allocation in OFDMA systems aiming not only to achieve optimal throughput for competing TCP flows but also to allocate resources appropriately between the downlink and uplink. This is important due to the increasing number of Internet applications where the mobile terminal is the TCP sender (social networking, peer-to-peer, etc.). Therefore, our scheme makes use of the asymmetry in the traffic and by defining the boundary between downlink and uplink capacity dynamically, enhance the TCP performance. Through numerical investigations we show the performance of the proposed scheme in terms of achieved fairness to the receivers and efficient allocation of downlink to uplink ratios based on the TCP traffic.     

OFDM中继系统的传输策略选择与资源分配

提出传输策略选择结合资源分配的迭代算法,证明其收敛性。进一步将算法简化为顺序进行的三步：子信道指配,传输策略选择和中继的发射功率分配,源的发射功率分配。仿真结果表明,所提资源分配迭代方案和简化方案的频谱效率性能均优于已有的两种资源分配方案,简化方案更适合实际应用。     

云环境下公平性优化的资源分配方法

针对云数据中心资源分配不均、效率不高、资源错位等问题,为了满足不同用户的需求,达到多种资源分配的公平性,实现资源的高效利用,提出了全局优势资源公平（GDRF）分配算法。GDRF算法采用多轮分配方式,即先通过用户已分配资源量确定分配资格,每轮再通过全局优势资源共享比和全局优势资源权重来确定具体的分配用户,分配过程充分考虑了资源的匹配情况,采用了max-min fairness思想的渐进填充方式,并且将多资源分配公平性统一度量模型运用到了算法中。实验基于一个Google集群数据模型与基于占优资源的多资源联合公平分配算法作了比较。实验结果表明,GDRF算法分配的虚拟机总量提高了12%,资源总利用率提高了0.5个百分点,公平评估值提高了约15%,并且该算法的资源组合分配的适应度较高,使得用户需求和供给更匹配。     

Dynamic radio resource allocation for 3G and beyond mobile wireless networks

Next generation of wireless cellular networks aim at supporting a diverse range of multimedia services to mobile users with guaranteed quality of service (QoS). Resource allocation and call admission control (CAC) are key management functions in future 3G and 4G cellular networks, in order to provide multimedia applications to mobile users with QoS guarantees and efficient resource utilization. There are two main strategies for radio resource allocations in cellular wireless networks known as complete partitioning (CP) and complete sharing (CS). In this paper, theses strategies are extended for operation in 3G and beyond network. First, two CS-based call admission controls, referred to herein as queuing priority call admission control (QP-CAC) and hybrid priority call admission control (HP-CAC), and one CP-based call admission control referred to as complete partitioning call admission control (CP-CAC) are presented. Then, this study proposes a novel dynamic procedure, referred to as the dynamic prioritized uplink call admission control (DP-CAC) designed to overcome the shortcomings of CS and CP-based CACs. Results indicate the superiority of DP-CAC as it is able to achieve a better balance between system utilization, revenue, and quality of service provisioning. CS-based algorithms achieve the best system utilization and revenue at the expense of serious unfairness for the traffic classes with diverse QoS requirements. DP-CAC manages to attain equal system utilization and revenue to CS-based algorithms without the drawbacks in terms of fairness and service differentiation.     

QoS-aware downlink packet scheduling for LTE networks

Scheduling for flows has been studied before. However, applying the previous schemes directly for LTE networks may not achieve good performance. To have good performance, both frequency domain allocations and time domain allocations for LTE resource blocks are suggested. Our method is suitable for real-time services and it consists of three phases. In frequency domain we design our method to utilize the RBs effectively. In time domain we first manage queues for different applications and propose a mechanism for predicting the packet delays. We introduce the concept of virtual queue to predict the behavior of future incoming packets based on the packets in the current queue. Then based on the calculated results, we introduce a cut-in process to rearrange the transmission order and discard those packets which cannot meet their delay requirements. We compare our scheduling mechanism with maximum throughput, proportional fair, modified largest delay first and exponential proportional fair. Simulation results show our scheduling method can achieve better performance than other schemes.