基于分形漏桶整形器的通用处理器共享系统性能分析

doi:1000-436X(2006)06-0029-07

摘要/Abstract

摘要：

为了分析自相似业务流对通用处理器共享（GPS）系统性能的影响，研究了GPS系统性能与业务流自相似参数等因素之间的关系。通过使用分形漏桶的包络曲线对进入GPS系统的自相似业务流进行整形，推导了利用自相似业务流作为输入的GPS系统的队列长度和时延统计上界。数值结果与分析显示，基于分形漏桶的GPS系统性能模型对自相似业务流具有较好的性能。

关键词: 自相似业务流, 通用处理器共享, 分形漏桶, 队列长度, 时延

Abstract:

In order to analyze the effect of self-similar traffic on the generalized processor sharing (GPS),the relationship was explored between the performance of a GPS system and the parameter of self-similar traffic. The self-similar traffic getting into the GPS system was regulated using the envelope curve of the fractal leaky bucket (FLB). The upper bounds on queue length and delay of the GPS system with self-similar traffic input was derived. Numerical simulations demonstrate that the performance model of a GPS system based on fractal leaky bucket regulators is suited for the self-similar traffic.

Key words: self-similar traffic, generalized processor sharing, fractal leaky bucket, queue size, delay

陈志刚,张连明,邓晓衡,赵明. 基于分形漏桶整形器的通用处理器共享系统性能分析[J]. 通信学报, 2006, 27(6): 29-35.

Zhi-gang CHEN,Lian-ming ZHANG,Xiao-heng DENG,Ming ZHAO. Performance analysis of generalized processor sharing based on fractal leaky bucket regulators[J]. Journal on Communications, 2006, 27(6): 29-35.

图/表 11

表1

图1

图2

图3

图4

图5

表2

图6

图7

图8

图9

参考文献 19

1	LELAND W E , TAQQU M , WILLINGER W . On the self-similar nature of Ethernet traffic(extended version)[J]. IEEE/ACM Transac-tions on Networking, 1994,2(1): 1-15.
2	CROVELLA M E , BESTAVROS A . Self-similarity in World-Wide Web traffic: evidence and possible causes[J]. IEEE/ACM Transactions on Networking, 1997,5(6): 835-846.
3	BERAN J , SHERMAN R , TAQQU M . Long-range dependence in variable–bit–rate video traffic[J]. IEEE Transactions on Communica-tions, 1995,43(2): 1566-1579.
4	吴援明，宁正容，梁恩志 . 网络自相似业务模型进展[J]. 通信学报 2004,25(3): 97-104. WU Y M, NING Z R , LIANG E Z . Review of self-similarity models of networks traffic[J]. Journal of China Institute of Communications, 2004,25(3): 97-104.
5	PARK K , WILLINGWER W . Self-Similar Network Traffic and Per-formance Evaluation[M]. New York: Wiley, 2000.
6	PAREKH A K , GALLAGER R G . A generalized processor sharing approach to flow control in integrated services networks: the single node case[J]. IEEE Network, 1993,1(3): 344-357.
7	ZHANG H . Service disciplines for guaranteed performance service in packet-switching networks[J]. Proceedings of the IEEE, 1995,83(10): 1374-1399.
8	YU Z , THNG L J , JIANG Y . Generalized processor sharing with long-range dependent traffic input[A]. Proceedings of the Ninth Inter-national Symposium in Modeling,Analysis and Simulation of Com-puter and Telecommunication Systems (MASCOTS '01)[C]. Wash-ington 2001. 224-232.
9	BORST S , BOXMA O , JELENKOVIC P . Asymptotic behavior of generalized processor sharing with long-tailed traffic sources[A]. Pro-ceedings of INFOCOM '00[C]. Tel Aviv 2000. 912-921.
10	PRESTI F L , ZHANG Z , TOWSLEY D . Bounds,approximations and applications for a two-queue GPS system[A]. Proceedings of INFO-COM '96[C]. San Francisco,CA 1996. 1310-1317.
11	MANNERSALO P , NORROS I . GPS schedulers and Gaussian traf-fic[A]. Proceedings of INFOCOM '02[C]. New York 2002. 1660-1667.
12	FLAVIO M P , NELSON L S F , DALTON S A . On the performance of generalized processor sharing servers under long-range dependent traffic[R]. the Institution of Computer Science,State University of Campinas, 2001.
13	宋舰，李乐民 . 无线网络中的分组调度算法[J]. 通信学报 2003,24(3): 42-48. SONG J, LI L M . Packet scheduling algorithms in wireless networks[J]. Journal of China Institute of Communications, 2003,24(3): 42-48.
14	NORROS I . A storage model with self-Similar input[J]. Queueing Systems, 1994,6: 387-396.
	CRUZ R L . A calculus for network delay and a note topologies of inter-connection networks[D]. University of Illinois, 1987.
16	简贵胃，葛宁，冯重熙 . 漏桶算法对输出业务流自相似特性的影响[J]. 电子与信息学报 2004,26(4): 654-658. JIAN G Z, GE N , FENG C X . Effect on self-similar characteristics of the leak-bucket output traffic[J]. Journal of Electronics ＆ Information Technology, 2004,26(4): 654-658.
17	PROCISSI G , GARG A , GERLA M et al. Token bucket characteriza-tion of long-range dependent traffic[J]. Computer Communication, 2002,25(11): 1009-1017.
18	BOORSTYN R , BURCHARD A , LIEBEHERR J et al. Statistical service assurances for traffic scheduling algorithms[J]. IEEE Journal on Selected Areas in Communications,Special Issue on Internet QoS, 2002,18(12): 2651-2664.
19	SARIOWAN H , CRUZ R , POLVZOS G . Scheduling for quality of service guarantees via service curves[A]. Proceedings of the Interna-tional Conference on Computer Communications and Networks (ICCCN '95)[C]. Las Vegas 1995. 512-520.

A_i(s,t)	在时间间隔[s,t]内，会话i (session_i)的汇聚流量
S_i(s,t)	在[s,t]内，会话i被服务的总流量
A_i,k_i,k (s,t)	在[s,t]内，会话i中流k (flow_i,k)的流量
A*_i,k (t-s)	A_i,k(s,t)的包络曲线
C	GPS系统的输出链路带宽
ρ	GPS系统的输出链路带宽利用率
c_i	会话i的flow数目
μ_i	会话i的GPS权重
r_i	A_i(s,t)的长期平均速率
r_i,k	A_i(s,t)的长期平均速率
σ_i	A_i(s,t)的标准偏差
σ_i,k	A_i,k(s,t)的标准偏差
H_i	A_i(s,t)的自相似参数
H_i,k	A_i,k(s,t)的自相似参数
Q_i(t)	会话i在时刻t的队列长度
D_i(t)	会话i在缓存区中的等待时延

会话	flow	μ_i	r_i,k	σ_i,k	H_i,k
	1		20	15	0.90
1	2	0.450	30	25	0.80
	3		32	30	0.75
	1		20	10	0.75
2		0.350
	2		35	25	0.60
3	1	0.200	40	25	0.80

[1]	郭锐, 刘洋. 基于简化序列重复节点的极化码快速串行抵消译码算法[J]. 通信学报, 2023, 44(5): 158-168.
[2]	张小贝, 张权, 方明, 秦琨, 张琦. 宽带数字阵列雷达通道固定时延误差估计技术的研究[J]. 通信学报, 2023, 44(3): 24-32.
[3]	秦武韬, 王鹏, 李玉峰. 基于周期耦合处理的CAN总线数据组合加密方法[J]. 通信学报, 2023, 44(1): 29-38.
[4]	邢旺, 唐晓刚, 周一青, 张冲, 潘振岗. 面向OTFS的时延-多普勒域信道估计方法综述[J]. 通信学报, 2022, 43(12): 188-201.
[5]	裴金川, 胡宇翔, 田乐, 胡涛, 李子勇. 联合路由规划的时间敏感网络流量调度方法[J]. 通信学报, 2022, 43(12): 54-65.
[6]	朱政宇, 陈鹏飞, 王梓晅, 巩克现, 吴迪, 王忠勇. 基于Swin-Transformer的短波协议信号识别[J]. 通信学报, 2022, 43(11): 127-135.
[7]	李国军, 龙锟, 叶昌荣, 梁佳文. 高速移动环境下低复杂度OTSM迭代rake均衡方法[J]. 通信学报, 2022, 43(10): 86-93.
[8]	王鹏, 张修社, 索龙, 史可懿. 基于随机时变图的时间确定性网络路由算法[J]. 通信学报, 2021, 42(9): 21-30.
[9]	李劲夫, 冯文江, 王文收, 蒋卫恒, 杨崇海. 下行MIMO广播信道中基于偏袒干扰消除的回溯干扰对齐方案[J]. 通信学报, 2021, 42(6): 94-106.
[10]	骆冰清, 王佩佩, 王正康, 孙知信. 低功耗蓝牙5.0邻居发现协议时延模型研究[J]. 通信学报, 2021, 42(6): 226-237.
[11]	蔡艳, 吴凡, 朱洪波. D2D协作边缘缓存系统中基于传输时延的缓存策略[J]. 通信学报, 2021, 42(3): 183-189.
[12]	孙雷, 王健全, 林尚静, 马彰超, 李卫, Qilian Liang, 黄蓉. 基于无线信道信息的5G与TSN联合调度机制研究[J]. 通信学报, 2021, 42(12): 65-75.
[13]	陈迪, 邱菡, 张万里, 朱会虎, 朱俊虎, 王清贤. 基于路由状态因果链的域间路由不稳定溯源检测方法[J]. 通信学报, 2021, 42(12): 76-87.
[14]	王蕊, 申敏, 何云, 刘香燕. Cell-Free大规模MIMO系统中基于传输时延的缓存策略研究[J]. 通信学报, 2021, 42(12): 134-143.
[15]	王泽南, 张娇, 汪硕, 黄韬, F.RichardYu. 端到端时延上限确定的服务链部署算法[J]. 通信学报, 2021, 42(11): 66-78.