基于QoS的超级节点模式网格调度研究

doi:10.3969/j.issn.1000-0801.2014.02.003

Abstract

Abstract:

Firstly，a kind of grid resource management model——super-peer model was proposed.For this model，economic mechanism was introduced，allowing a grid user to put forward the task’s expected execution deadline，cost limit and the weight parameters between them.Those are the QoS parameters of application-level.Then，a corresponding resource scheduling algorithm was shown.Next，hierarchical colored Petri net and price timed Petri net were used to model and the dynamic process of grid resource scheduling was simulated.Lastly，reachable task graph（RTG）of Petri net model was constructed and the system’s scheduling performance was analyzed，such as throughout capacity，load-balancing，scheduling time and cost through an example.

Key words: grid scheduling, QoS parameter, Petri net

Shanliang Pan,Xi Huang,Qinjiao Mao. Research on Grid Scheduling of Super-Peer Model Based on QoS[J]. Telecommunications Science, 2014, 30(2): 21-32.

Figures/Tables 12

References 21

1	Foster I ， Kesselman C . The Grid：Blueprint for New Computing Infrastructure. Morgan Kaufmann Publishers， San Francisco，CA， 1999
2	Mastroianni C ， Talia D ， Verta O . A super-peer model for resource discovery services in large-scale grids. Future Generation Computer Systems， 2005，21（10）： 1235～1248
3	Foster I ， Kesselman C ， Jeffrey M ， et al. Grid services for distributed system integration. IEEE Computer， 2002，35（6）： 37～46
4	The web services resource framework.
5	Mastroianni C ， Talia D ， Verta O . Designing an information system for grids：comparing hierarchical，decentralized P2P and super-peer models. Parallel Computing， 2008（34）： 593～611
6	Kwan S K ， Muppala J K . Resource discovery and scheduling in unstructured peer-to-peer desktop grids. Proceedings of the International Conference on Parallel Processing Workshops， San Diego，CA， 2010： 303～312
7	Merz P ， Wolf S ， Schwerdel D ， et al. A self-organizing super-peer overlay with a Chord core for desktop grids. Proceedings of IWSOS 2008， Vienna，Austria， 2008： 23～34
8	Li Y ， Huang X L ， Ma F Y ， et al. Building efficient super-peer overlay network for DHT systems. Proceedings of GCC 2005， Beijing，China， 2005： 787～798
9	Cozza P ， Talia D . A Super-Peer Model for Multiple Job Submission on a Grid. Core GRID Technical Report Number TR-0067， 2007
10	Wu C C ， Chin J H ， Lin Y S ， et al. G2G：a meta-grid framework for the convergence of P2P and grids. Proceedings of GPC 2009， Geneva，Switzerland， 2009
11	Zhao S H ， Chen G L ， Wu G X ， et al. A strategy for selecting super-peer in P2P and grid based hybrid system. Proceedings of Edutainment 2008， Nanjing，China， 2008： 192～199
12	Colored J K . Petri Nets-Basic Concepts，Analysis Methods and Practical Use：Basic Concepts（2nd Edition）. Springer-Verlag， Heidelberg，Berlin， 1996
13	熊曾刚，杨扬，曾明 . 基于Petri 网的两阶段网格任务调度模型与分析. 通信学报， 2009，30（8）： 69～77
14	Andrade ， Brasileiro N ， Cirne F ， et al. Discouraging free riding in a peer-to-peer CPU-sharing grid. High Performance Distributed Computing， 2004，12（3）： 129～137
15	熊曾刚，杨扬，刘丽等. 网络资源管理的 Grid 和 P2P 集成方案及其关键技术分析. 控制与决策， 2008，23（1）： 1～7
16	Foster I ， Jennings N R ， Kesselman C . Brain meets brawn：why grid and agents need each other. Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems， New York，USA， July 2004
17	Xiong Z G ， Yang Y ， Zhang X M . Integrated agent and semantic P2P grid resource discovery model. Proceedings of Eighth ACIS International Conference on Software Engineering， Artificial Intelligence，Networking，and Parallel/Distributed Computing， IEEE Computer Society Press， Qingdao，China， 2007
18	袁崇义 . Petri网原理与应用. 北京：电子工业出版社， 2005
19	吴哲辉 . Petri网导论. 北京：机械工业出版社， 2006
20	吉罗，瓦尔克 . 系统工程Petri网建模、验证与应用指南. 北京：电子工业出版社， 2005
21	刘卫东，宋佳兴，林闯 . 基于价格时间 Petri 网的网格计算应用模型及分析. 电子学报， 2005，33（8）： 1416～1420

Metrics

Recommended 0

No Suggested Reading articles found!

库所	含义说明
s1	超级节点管理域内某一资源节点上用户准备提交的任务
s2	超级节点接收到来自资源节点提交的任务
s3	接收的任务是不可分解的
s4	接收的任务是复合任务，可以进行分解
s5	复合任务分解后具有时间先后依赖关系的子任务集合
s6	从等待调度的子任务集合里挑选出来准备调度的子任务
s7	已确认调度去向及目标的任务（子任务）
s8	在本地网格社区某一资源节点上准备执行的任务（子任务）
s9	任务（子任务）的执行结果
s10	待在本地网格社区某一资源节点上执行的远程任务（子任务）
s11	远程任务（子任务）的执行结果
s12	本网格社区内某一资源节点处于故障状态
s13	资源的状态信息
in	本地超级节点接收远程超级节点发送的待调度任务（子任务）、本地任务（子任务）的执行结果或远程超级节点管理域内资源节点状态信息的单元
out	本地超级节点向远程超级节点发送任务（子任务）、远程任务（子任务）执行结果或本地资源节点状态信息的单元

变迁	含义说明	变迁发生产生的时延、价格
t1	用户在资源节点向本地超级节点提交任务	0，0
t2	判断任务是否可以进行分解	0，0
t3	为不可分解的任务查询资源的状态信息	0，0
t4	将复合任务分解为具有时间先后依赖关系的子任务集合	0，0
t5	根据执行时间的先后顺序选择将要调度的子任务（并行任务可以同时调度），具有前驱的子任务必须等所有前驱执行完成后才能进行调度	0，0
t6	为挑选出来的子任务查询资源的状态信息	0，0
t7	将任务（子任务）传送到超级节点的发送单元，进行远程任务调度	0，0
t8	将任务（子任务）传送到本超级节点管理域内的某一资源节点	0，0
t9	本网格社区内的某一资源节点在执行任务（子任务）	若资源节点为任务（子任务）的提交节点，则价格为0，时延为一个正数，否则时延、价格均为正数
t10	接收从远程超级节点发送的本地任务（子任务）的执行结果	0，0
t11	判断任务（子任务）是否顺利执行。如果是，则子任务的后继可能获得调度的机会；否则准备进行重调度	0，0
t12	将接收到的远程任务（子任务）分配到本网格社区内的某一资源节点	0，0
t13	本地网格社区某一资源节点正在执行远程任务（子任务）	时延、价格均为正数
t14	将远程任务（子任务）的执行结果从某一资源节点传送到超级节点的发送单元	0，0
t15	本地网格社区某一资源节点发生故障	0，0
t16	为远程任务（子任务）生成一个含有错误报告的执行结果	0，0
t17	为本地任务（子任务）生成一个含有错误报告的执行结果	0，0

抑止弧	含义说明
s8与t12之间	资源节点优先执行本网格社区内的任务（子任务）
s10与t12之间	当资源节点执行远程任务（子任务）时，避免新的远程任务（子任务）分配到此资源节点，有利于资源节点间的负载平衡

任务（子任务）	到达时间	截止期限	费用上限		估计执行时间				估计执行费用			α	β
任务（子任务）	到达时间	截止期限	费用上限	节点1	节点2	节点3	节点4	节点1	节点2	节点3	节点4	时间权重	费用权重
GT1	0	180	160	210	180	170	220	0	170	150	175	0.6	0.4
GT1-1	0	40	35	30	35	40	50	0	50	30	45
GT1-2（5次循环）		150（5次循环后）	19/单次	26/单次	22/单次	12/单次	14/单次	0/单次	18/单次	8/单次	8/单次
GT1-3		180	30	50	35	70	100	0	30	70	90
GT2	40	270	210	235	320	260	220	210	208	0	202	0.3	0.7
GT2-1		60	10	10	60	15	20	10	8	0	15
GT2-2		90	15	30	90	25	30	20	10	0	12
GT2-3		190	60	105	100	120	110	45	50	0	60
GT2-4		190	80	135	130	140	120	90	85	0	75
GT2-5		270	45	90	70	100	60	45	55	0	40

[1]	Shanliang Pan,Xi Huang,Qinjiao Mao. Grid Scheduling of Super-Peer Model Based on Price Timed Petri Net [J]. Telecommunications Science, 2013, 29(11): 52-59.
[2]	Zhang Zhengming,Ma Bingxian and Xiang Dongming. Research and Implementation of Web Service Registration Method Based on Petri Network [J]. Telecommunications Science, 2012, 28(11): 86-91.
[3]	Bai Lirui,Li Tong,Xie Zhongwen and Song Chen. Charging Model Research of Application Layer in Cloud Computing Based on Cost-Profit Petri Net [J]. Telecommunications Science, 2012, 28(1): 58-62.
[4]	Lirui Bai,Tong Li,Zhongwen Xie,Chen Song. Charging Model Research of Application Layer in Cloud Computing Based on Cost-Profit Petri Net [J]. Telecommunications Science, 2012, 28(1): 62-66.
[5]	Xiaoming Bu. Application of Petri Net in the Control of Telecom Billing System Disaster Recovery [J]. Telecommunications Science, 2011, 27(7): 109-116.

Research on Grid Scheduling of Super-Peer Model Based on QoS

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 21

Related Articles 5

Metrics

Recommended 0