基于分段线性函数的广义效用max-min公平分配算法研究

doi:1000-436X(2006)10-0025-06

通信学报 ›› 2006, Vol. 27 ›› Issue (10): 25-30.doi: 1000-436X(2006)10-0025-06

基于分段线性函数的广义效用max-min公平分配算法研究

徐童,廖建新

北京邮电大学网络与交换国家技术重点实验室，北京 100876

出版日期:2006-10-25 发布日期:2017-06-15
基金资助:
国家杰出青年科学基金资助项目;新世纪优秀人才支持计划基金资助项目;高等学校博士学科点专项科研基金资助项目

Research on the generalized utility max-min fair algorithm based on piecewise linear function

Tong XU,Jian-xin LIAO

State Key Laboratory of Networking and Switching Technology,Beijing University of Posts and Telecommunications,Beijing 100876,China

Online:2006-10-25 Published:2017-06-15
Supported by:
The National Science Fund for Distinguished Young Scholars;The Program for New Century Ex-cellent Talents in University;The Specialized Research Fund for the Doctoral Program of Higher Education

摘要/Abstract

摘要：

提出了一种基于分段线性函数的广义效用max-min（UMM）公平分配算法，可支持资源分配的上下限以及各种严格单调增和连续的效用函数。该算法避免了迭代计算，复杂度低于UMM公平的注水法。简化后的算法的复杂度与现有的基于分段线性函数的狭义UMM公平分配算法相同。该算法可应用于计算机和通信领域中的各种资源分配问题中。

关键词: 效用, 最大最小公平性, 资源分配算法, 分段线性函数

Abstract:

A generalized utility max-min (UMM) fair algorithm of resource allocation based on piecewise linear function was provided,which supported the upper/lower bounds of resource allocation as well as strictly increasing and continu-ous utility functions.Because of the avoidance of iterative procedure,this algorithm was less complex than water-filling,another UMM fair algorithm.And its simplified version had the same complexity as the narrow-sense UMM fair algo-rithm based on piecewise linear function.This algorithm can be applied in various problems of resource allocation in the field of computer and communication.

Key words: utility, max-min fairness, resource allocation algorithm, piecewise linear function

徐童,廖建新. 基于分段线性函数的广义效用max-min公平分配算法研究[J]. 通信学报, 2006, 27(10): 25-30.

Tong XU,Jian-xin LIAO. Research on the generalized utility max-min fair algorithm based on piecewise linear function[J]. Journal on Communications, 2006, 27(10): 25-30.

图/表 4

图1

表1

仿真模型参数"

应用	$u_{i} (x), x \in [M_{R_{i}}, P_{R_{i}}]$	$M_{R_{i}}$	$P_{R_{i}}$	$u_{i} (M_{R_{i}})$	$u_{i} (P_{R_{i}})$
a1	$u_{1} (x) = x$	4	20	4	20
a2	$u_{2} (x) = 6 \times x^{1 / 3}$	0	18	0	15.72
a3	$u_{3} (x) = 9.28 \times 7 \times \arctan ((x - 8) / 2)$	0	16	0	18.56
a4	$u_{4} (x) = 8$	6	6	8	8

表1

图2

表2

用本算法分配资源的结果"

R	PLu(R)	各应用的资源				各应用的分段线性效用				各应用的状态
R	PLu(R)	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$P L u_{1} (x_{1})$	$P L u_{2} (x_{2})$	$P L u_{3} (x_{3})$	$P L u_{4} (x_{4})$	$S_{1}$	$S_{2}$	$S_{3}$	$S_{4}$
10	0	4.000	0.000	0.000	6.000	4.000	0.000	0.000	8.000	M	M	M	MP
14	1.937	4.000	0.056	3.944	6.000	4.000	1.937	1.937	8.000	M	O	O	MP
20	5.958	5.958	1.106	6.936	6.000	5.958	5.958	5.958	8.000	O	O	O	MP
35	12.002	12.002	8.163	8.835	6.000	12.002	12.002	12.002	8.000	O	O	O	MP
45	14.571	14.571	14.494	9.935	6.000	14.571	14.571	14.571	8.000	O	O	O	MP
53	16.922	16.922	18.000	12.078	6.000	16.922	15.720	16.922	8.000	O	P	O	MP
59	19.000	19.000	18.000	16.000	6.000	19.000	15.720	18.560	8.000	O	P	P	MP
65	/	20.000	18.000	16.000	6.000	20.000	15.720	18.560	8.000	P	P	P	MP

表2

参考文献 10

[1]	RADUNOVIˊC B , BOUDEC J Y . A unified framework for max-min and min-max fairness with applications[A]. Proceedings Allerton'02[C]. 2002.
[2]	ATM Forum.Traffic management specification,version 4.1.AF-TM20121.000[EB/OL]. .
[3]	HOU Y T , TZENG H , PANWAR S S . A generalized max-min rate allocation policy and its distributed implementation using the ABR flow control mechanism[A]. IEEE Infocom'98[C]. San Francisco,CA,USA 1998,1266-1375.
[4]	VANDALORE B , FAHMY S , JAIN R , et al . General weighted fair-ness and its support in explicit rate switch algorithms[J]. Computer Communications, 2000,23(2): 149-161.
[5]	CAO Z , ZEGURA E . Utility max-min:an application-oriented band-width allocation scheme[A]. INFO-COM'99[C]. 1999. 793-801.
[6]	RUBENSTEIN D , KUROSE J , TOWSLEY D . The impact of multi-cast layering on network fairness[J]. IEEE/ACM Transactions on Networking, 2002,10(2): 169-182.
[7]	黄力菲，黄颖，李衍达 . 效用max-min公平准则及其在ABR业务中的应用[J]. 通信学报， 2001,22(T): 10-17. HUANG L F , HUANG Y,YING , LI Y D . Utility max-min fairness and its application in ABR service[J]. Journal of China Institute of Communica-tions, 2001,22(T): 10-17.
[8]	RAYMOND R , LIAO F , ANDREW T . A utility-based approach quantitative adaptation in wireless packet networks[J]. Wireless Net-works, 2001,7(5): 541-557.
[9]	王玉峰，王文东，程时端 . 基于效用的资源适配机制公平性研究[J]. 北京邮电大学学报， 2004,27(3): 38-42. WANG Y F , WANG W D , CHENG S D . Study of fairness of resource adaptation based on utility[J]. Journal of Beijing University of Posts and Telecommunications, 2004,27(3): 38-42.
[10]	SHENKER S . Fundamental design issues for the future Internet[J]. IEEE Journal on Selected Areas in Communications, 1995,13(7): 1176-1188.

[1]	陈赓, 齐书虎, 沈斐, 曾庆田. 面向B5G多业务场景基于D3QN的双时间尺度网络切片算法[J]. 通信学报, 2022, 43(11): 213-224.
[2]	徐勇军,胡圆,李国权,林金朝,陈前斌. 异构携能通信网络顽健资源分配算法[J]. 通信学报, 2019, 40(7): 186-196.
[3]	周异辉,鲁来凤,吴振强. 随机响应机制效用优化研究[J]. 通信学报, 2019, 40(6): 74-81.
[4]	谭国真,韩国栋,张福新,丁男,刘明剑. 基于网络效用最大化理论的分布式车联网拥塞控制策略[J]. 通信学报, 2019, 40(2): 82-91.
[5]	吴昊,范九伦,赖成喆,刘建华. 基于攻防博弈和蒙特卡洛模拟的网站防御策略选取方法[J]. 通信学报, 2018, 39(8): 48-55.
[6]	程子敬,赵俊楠,崔玉文,石乐义. 基于纳什议价解的地外驻留平台网络可靠性与效用代价分析[J]. 通信学报, 2017, 38(2): 10-15.
[7]	金顺福,郝闪闪,王宝帅. 融合双速率和工作休眠的虚拟机调度策略及参数优化[J]. 通信学报, 2017, 38(12): 10-20.
[8]	姚建盛,马春光,袁琪. 基于效用的机会网络“物—物交换”激励机制[J]. 通信学报, 2016, 37(9): 102-110.
[9]	刘明剑,谭国真,李帅兵,丁男,宋彩霞. 基于信道拥塞代价计算的车联网自适应消息发送速率控制方法[J]. 通信学报, 2016, 37(10): 108-116.
[10]	谷勇浩,林九川. 基于多变量信源编码的隐私效用均衡方法[J]. 通信学报, 2015, 36(12): 172-177.
[11]	王大鸣,陈松,崔维嘉,王强. 多用户MIMO-OFDM系统基于QoE效用函数的跨层资源分配[J]. 通信学报, 2014, 35(9): 175-183.
[12]	陈赓，夏玮玮，沈连丰. 基于传输速率自适应的动态带宽分配算法[J]. 通信学报, 2014, 35(5): 4-32.
[13]	丁长松1,2，王志英2，胡志刚3. 基于效用驱动的网格资源协同预留策略[J]. 通信学报, 2014, 35(5): 14-107.
[14]	陈赓,夏玮玮,沈连丰. 基于传输速率自适应的动态带宽分配算法[J]. 通信学报, 2014, 35(5): 25-32.
[15]	丁长松,王志英,胡志刚. 基于效用驱动的网格资源协同预留策略[J]. 通信学报, 2014, 35(5): 101-107.

基于分段线性函数的广义效用max-min公平分配算法研究

Research on the generalized utility max-min fair algorithm based on piecewise linear function

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 10

相关文章 15

Metrics

推荐阅读 0