Java教程

DRF算法比较篇

本文主要是介绍DRF算法比较篇,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Asset Fairness

Asset Fairness的设计想法是不同资源的相同占用率是等值的,比如1%的cpu使用率和1%内存和1%的带宽使用率是相同的。在这个前提之下,Asset Fairness 尝试去均衡分配给每个用户的聚合资源值(各种资源的累加)。特别地,Asset Fairness会计算每个用户i的聚合资源占用率

 ,其中Si,j是用户i对于资源j的占用率。然后在用户的总占用率上使用max-min fairness,比如总是重复地运行拥有最小聚合资源占用率用户的任务。考虑第四章中的例子,系统拥有9CPUS和18GB RAM,既然RAM的GB数量是CPU数量的两倍,一个CPU相当于2GB的RAM。假设1GB的RAM为$1,那么1CPU为¥2,那么可以用户A的每个任务需要花费¥6,而用户B的每个任务需要花费¥7。设置x和y分别为Asset fairness算法分配给用户A和用户B的任务数。

Asset-fair分配问题可以通过求解以下问题来得到(这个问题假设用户A和用户B最后得到了相同的聚合资源占用率)

求解上面这个问题,可以得到x=2.52,以及y=2.16,。因而用户A得到了{2.5 CPUS,10.1GB},用户B得到了{6.5CPUs,2.2 GB}。

这个分配策略的简单性很吸引人,但它有一个重大的缺陷:它违反了sharing incentive特性。Assert fairness可以导致一个用户获取了小于总资源的1/n,其中n为总的用户数目。

5.2 Competitive Equilibrium from Equal Incomes

在微经济理论中,公平分配资源的首选方法是Competitive Equilibrium from Equal Incomes(CEEI),在CEEI中,每个用户在初始化时接收到所有资源的1/n,接下来每个用户会在一个完全竞争的市场与其他用户交易资源。CEEI的输出同时满足envy-free和pareto efficient。

更加精准描述是:CEEI分配是由nash bargaining solution给出的,nash bargaining solution会选择可行的分配策略,使得 

最大化,其中

 是用户i获取资源 

的方式或功能,为了简化对比,我们将一个用户得到其资源分配的方式简化为就是其dominant share, 

考虑第四章两用户的例子,回忆一下用户A的dominant share为4x/18 = 2x/9,而用户B的dominant share为3y/9 = y/3。其中x为用户A的任务数目,y为用户B的任务数目。最大化商品的dominant shares就等同于最大化商品的x.y。因为CEEI就变为解决如下的优化问题:

                              

解决以上问题可以得到x= 45/11,y=18/11。因而用户A获得了{4.1 CPUs, 16.4 GB},同时用户B获得了{4.9 CPUs, 1.6GB}。不幸的是,虽然CEEI同时满足envy-free和Pareto efficient,但不满足strategy-proof特性,因而用户可以通过谎报他们的资源需求来提升他们的资源分配。

5.3 Comparison with DRF

为了给读者对Asset Fairness和CEEI有一个直观的理解,我们在下图中,将三种算法资源分配进行对比。

                              

我们看DRF使得用户的dominant share趋于均衡。而Asset Fairness使得用户的总资源分配的百分比趋于均衡。最后,因为CEEI假设有一个充分竞争市场,它找到了一个满足市场结清的解决方案,使得所有资源都得到分配,不幸的是这个精确的特性使得CEEI可能会被欺骗,用户可以通过声明它需要更多地未充分利用的资源,导致CEEI向这个用户赋予更多的任务来达到市场结清的目标。

6 Analysis

第六章主要从第三章提出的8种分配特性来分析asset fairness、CEEI和DRF。下面这个表显示了三种分配策略支持的不同特征。

                            

这篇关于DRF算法比较篇的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!