文摘

资源分配的一个重要问题是公平分配的。例如,计算机网络管理希望公平向用户分配网络资源。描述资源的公平分配,公平定量评分功能提出了在1984年由耆那教等。本文的目的是提出一个修改网络公平分享功能,这样用户就可以根据他们的优先级级别区别对待。的数学性质进行了讨论。提出了公平评分功能让所有的好属性并提供更好的性能,当网络用户具有不同的优先级。

1。介绍

当一个固定数量的用户或接收器共享有限的资源,分布的公平性一直是一个重要的问题。资源分布可以是任何类型的如社会福利资源分配、人力资源分布、和计算机网络资源分布。假设用户分享一定数量的资源。让是用户收到大量的资源,分别。假设所有用户拥有相同的权利分享整个资源。的值之间的差异不应太大。如果之间的差异值太大,那么它可以声称整个资源的分配是不公平的。这里需要做一定的规则来确定资源分配是公平的还是不公平的。为了解决这样的问题,有两个重要的步骤。第一步是找到一个合适的定量测量,这是一个函数,定量测量可用于描述资源的公平分配。定量测量时应增加资源分布变得更加公平。另一方面,应该减少当资源分布越来越不公平。第二步是确定当一个可以得出这样的结论:资源分布明显不公平。统计检验的概念可以采用这一目的。一定的意义,可以得出这样的结论:资源分布明显不公平,当定量测量低于某个值。这样的价值被称为关键值统计分析。本文修改常用公平测量,这样修改后的公平可以更好地适应现实世界的应用程序。

在过去的几十年里,许多研究论文已发表在这一领域的文献。耆那教等。1)提出了一个定量的测量来评估网络资源的公平分配。贾殷等人提出的公平得分函数被定义为 正如上面提到的,一个公平的分数函数必须具备一些不错的属性,以便它可以用来描述资源的公平分配,可以用来确定资源分配是否公平。事实上,公平的评分功能中定义的(1)具有一些很好的性质。它可以很容易地显示对于任何非负。这是完全不公平的分配,也就是说,只有一个用户占据了整个资源,而其他用户不会收到任何的价值是。另一方面,如果分布是完全公平的,也就是说,所有用户分享整个资源同样的价值是1。如果只有的用户分享整个资源同样而其他人则不会收到任何,那么公平的分数。它也可以看到不依赖于规模。此外,人们可以发现这个公平得分函数不断反映分配的变化。引用在这个领域,看到Bertsekas Gallager [2),赵和耆那教徒的3),凯利et al。4],Mazumdar et al。5]。

注意资源分配的公平性得分函数可以使用当所有的用户权利平等分享整个资源。然而在实践中,可能用户可能有不同的优先级。例如,当互联网资源分配给用户,高级用户和普通用户应该区别对待。当社会利益资源分布、残疾人、孕妇、低收入或无收入的人都有不同的优先级。同样整个资源分配所有用户,事实上,整个资源分配不公平的方法。因此,一些修改是需要公平的评分函数中定义(1),这样修改后的公平得分函数可用于用户的情况下有不同的优先级级别共享整个资源。这是本文的目的。不是同样的所有用户分配网络资源,整个资源分配给所有用户根据他们的优先级。它可以显示公平功能提出了让所有的有价值的属性即使对的用户在不同的优先级。

2。修改公平得分函数

现在假设用户共享整个资源有不同的优先级。更具体地说,让用户收到的大量资源,分别。也让这些用户的相应的优先因素。这意味着用户收到应该是大量的资源对于一些。公平的评分函数摘要的定义是 这个公平得分函数的泛化公平得分函数中定义(1)。如果所有的用户都在同一优先级,也就是说, 公平的评分函数;就变成了这是一样的一个定义在(1)。使用这个公平得分函数来描述资源的公平分配和使用统计分析来确定资源分配是否公平,必须具备一些不错的属性上一节中提到的。事实上,它将显示公平的评分功能拥有相同的有价值的属性吗所做的事。从定义可以看出那 总是正确的。两个极端的情况下,是完全公平分配情况和完全不公平的情况,介绍了定理1和2。在完美的公平分配的情况下,公平的评分函数中定义(2)达到它的最高价值。在完全不公平的分布情况下,公平得分函数达到最小值。

定理1。 当且仅当分布是完全公平的。这里完全公平分配是指所有用户分享整个网络资源比例根据他们的优先级。

证明。的定义;, 当且仅当 这句话是真的当且仅当 它相当于 这个定理的证明。

定理2。 是最小当且仅当分布是完全不公平的。这里的分布是完全不公平的是只有一个用户优先级最低的占据了整个资源。

证明。排序从最小到最大。让是最小的数。不失一般性,它可以假定 因此。然后 定义 请注意, 自是固定的数字,然后最大化,它需要最大化 自 然后最大化当且仅当一个吗 值为1,其余的都是零。
另一方面,注意 为了最大化Q, 必须对这些术语满意吗。这是等效的条件必须是0的条件满意吗。这意味着用户收到的金额,其优先级级别不是最低的,必须是零。结合上述讨论的结果,证明。

固定优先级、最小值公平得分函数中定义(2)可以达到 在的情况下,这个量就。这个结果是一样的一个公平的分数时函数中定义(1)使用,如预期。下一个定理处理的情况用户同样分享整个资源假设所有的用户都在同一优先级。

定理3。如果所有的用户在同一优先级,如果出了用户分享整个资源同样而另一n - k用户不共享任何,然后

证明。不失一般性,假设第一用户收到相同的金额,x,其余的用户不会收到任何。然后 证明已经完成。

应该注意的是,定理3只处理一个特殊情况,所有用户具有相同的优先级。有人可能会怀疑可以容纳的用户具有不同的优先级,只有吗出了用户分享整个资源比例,另根据他们的优先级- - - - - -用户不共享任何。事实上,这并非如此。下面是一个反例。假设有三个用户优先级级别3,2,分别和1。还假设用户优先级级别3和2分享整个资源比例与优先级的优先级级别和用户1不接收任何份额。然后

定理4。为定义 然后

证明。的定义,这就可以证明 有相同的信号。这是真的,因为 定理的证明。

定理4显示,当用户给了少量用户,如果用户新分配更公平相对歧视。如果用户新分配不公平相对青睐。这个想法是采用从耆那教等。1)结合考虑的优先级。

下面的结果表明,如果所有的用户将获得额外的大量的网络资源比例根据他们的优先级,那么公平的分配就不会减少。

定理5。对于任何,

证明。它可以显示 现在它需要表明 是一个递减函数δ。这是真的,因为 证明。

除了上面的属性,它可以轻易地看到公平函数中定义(2)并不依赖于规模。公平的属性得分函数确保公平得分函数可以用来评估资源的公平分配。

3所示。结论和讨论

公平是一个重要的问题,当资源分配给用户。在这里可以任何形式的资源分配。例如,当网络资源分配给用户,一个希望分发整个资源相当的用户。另一个例子是社会福利资源分配。资源分配的公平衡量最初讨论计算机网络领域的资源分布。公平的评分函数,耆那教等提出的。1)已被广泛用于评估网络资源的公平分配。公平的评分函数然而,假设所有的用户都在同一优先级;也就是说,所有的用户都应该平等对待,当整个资源分配。在实践中,用户可能有不同的优先级,应该区别对待。当计算机网络资源提供者整个资源分发给他们的用户,他们通常把他们的用户根据其优先级levels-basic用户、高级用户,VIP用户,等等。社会效益的资源也分发给接收器根据他们的优先级。例如,残疾人通常有更高的优先级获得的社会效益。因此,一些需要修改公平得分函数,这样修改后的公平得分函数可以处理的用户具有不同的优先级。这是本文的目的。一个新的公平得分函数本文提出了。公平的评分函数提出了让所有的好属性即使用户具有不同的优先级。

新的公平得分函数的值增加资源分配时变得更公平,更公平。价值减少时,资源分布越来越不公平。资源分配的一个极端是,所有用户分享整个资源根据他们的优先级。在这种情况下,公平得分函数达到最大值1。另一方面,当资源分布是最不公平的情况下,公平的评分功能达到最小值。此外,公平的状态分布的变化从一个极端走向另一个极端,公平的评分功能能够反映出相应的改变。这些属性确保公平的评分功能可以用来评估资源的公平分配。

它可以表明的分布无标度。因此,分位数的可以通过蒙特卡罗模拟。基于这些分位数,统计测试可以检查是否进行网络资源分布是统计用户明显不公平。在计算机网络资源管理中,如果资源分布明显不公平,应该调整资源分配方案。

承认

作者感谢两位匿名裁判他们详细的意见和建议,大大提高了纸的质量。