[go: up one dir, main page]

CN102904750B - 一种基于网络拓扑结构的作业分配方法 - Google Patents

一种基于网络拓扑结构的作业分配方法 Download PDF

Info

Publication number
CN102904750B
CN102904750B CN201210359410.6A CN201210359410A CN102904750B CN 102904750 B CN102904750 B CN 102904750B CN 201210359410 A CN201210359410 A CN 201210359410A CN 102904750 B CN102904750 B CN 102904750B
Authority
CN
China
Prior art keywords
node
nodes
interchanger
interchangers
equal
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN201210359410.6A
Other languages
English (en)
Other versions
CN102904750A (zh
Inventor
原帅
张涛
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Dawning Information Industry Beijing Co Ltd
Dawning Information Industry Co Ltd
Original Assignee
Dawning Information Industry Beijing Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Dawning Information Industry Beijing Co Ltd filed Critical Dawning Information Industry Beijing Co Ltd
Priority to CN201210359410.6A priority Critical patent/CN102904750B/zh
Publication of CN102904750A publication Critical patent/CN102904750A/zh
Application granted granted Critical
Publication of CN102904750B publication Critical patent/CN102904750B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Landscapes

  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

本发明提供一种基于网络拓扑结构的作业分配方法，应用于计算机集群，选择节点的方法包括：步骤S1，选取一个节点，得到所述节点所属的交换机；步骤S2，根据所述节点所属交换机和拓扑关系，获得与所述节点所属交换机的拓扑距离小于等于TopologyChoosedDepth的所有交换机，判断所述所有交换机包含的所有节点的总数是否符合要求，是执行步骤S3，否，执行步骤S1；所述TopologyChoosedDepth为网络拓扑结构的调查深度；步骤S3，选取所述所有节点中权值最大的节点，结束。本发明提供一种基于网络拓扑结构的作业分配方法，根据服务器所处网络位置，将同一作业的任务尽可能的调度至同一网络区域中，能够提升高“通信/计算”比率作业的运行效率，网络模型更为精确，适应性更好，执行效率提升更加明显。

Description

一种基于网络拓扑结构的作业分配方法
技术领域
本发明涉及网络管理技术领域，具体涉及一种基于网络拓扑结构的作业分配方法。
背景技术
随着信息产业的发展，大规模计算机集群越来越普及，节点数量大幅增长，网络结构越来越复杂。作业运行节点之间的网络质量和联系程度，对作业运行效率的影响越来越大。根据网络拓扑结构进行节点分配，减少网络通信对作业的影响，能明显提升高“通信/计算”比率作业的运行效率。
现有技术中，Cray XT3/XT4systems：使用第一个可用的处理器；Maui和Slurm：忽视拓扑结构，看做平面网络；用节点序号的差值当做网络距离。blue gene family：同一应用的任务调度到8*4*4的节点上。可以看出，许多作业调度系统对基于网络拓扑的调度方法有简单的支持。
而节点规模越大，节点分配策略对执行速度的影响越大，节点分配对应用的影响程度取决于通信/计算的比率，该比率越大，影响越明显。
大多数调度器的网络模型过于简单了，并没有考虑具体的网络结构。忽视了异构节点，以及不同型号交换机、路由器的区别。简单的用节点序号的差值当做网络距离，或者调度至某一个物理区域的服务器上。这样的方案只能一定程度缓解网络的影响，效果有限。
发明内容
本发明一种基于网络拓扑结构的作业分配方法，所述方法应用于计算机集群，选择节点的方法包括：
步骤S1，选取一个节点，得到所述节点所属的交换机；
步骤S2，根据所述节点所属交换机和拓扑关系，获得与所述节点所属交换机的拓扑距离小于等于TopologyChoosedDepth的所有交换机，判断所述所有交换机包含的所有节点的总数是否符合要求，是，执行步骤S3，否，执行步骤S1；
所述TopologyChoosedDepth为网络拓扑结构的调查深度；
步骤S3，选取所述所有节点中权值最大的节点，结束。
本发明提供的第一优选实施例中：所述步骤S1从可用节点中的第一个节点，依次选取一个节点，步骤S2中在得到的所有交换机包含的所有节点的总数不符合要求时，执行步骤S1，选取下一个节点，具体操作方法为：
步骤S1中，设置节点的编号i=0，选取编号为i的节点，得到所述编号为i的节点所属的交换机；
步骤S2中，在得到的所有交换机包含的所有节点的总数不符合要求时，对所述编号i进行加一操作后，执行所述步骤S1选取下一个节点。
本发明提供的第二优选实施例中：在对所述编号i进行加一操作后，判断所述i小于或等于节点长时执行步骤S1。
本发明提供的第三优选实施例中：判断所述i大于所述节点长时，根据尽可能交付MaximumDelivery值判断是否放弃调度。
本发明提供的第四优选实施例中：根据所述MaximumDelivery值判断是否放弃调度的方法为：
判断所述MaximumDelivery值是否为1，是，按照顺序选取可用节点，否，放弃调度，结束。
本发明提供的第五优选实施例中：步所述骤S2中根据所述节点所属交换机和拓扑关系获得与所述节点所属交换机的拓扑距离小于等于TopologyChoosedDepth的所述所有交换机的方法为：
步骤S201，设置拓扑距离j=0；
步骤S202，判断所述j是否满足小于或等于TopologyChoosedDepth，是，执行步骤S203，否，执行步骤S3；
步骤S203，获得与所述节点所属交换机的拓扑距离小于或等于j的所有交换机，判断所述所有交换机包含的所有节点的总数是否符合要求，是，执行步骤S3，否，对所述j进行加一操作后执行步骤S202。
本发明提供的第六优选实施例中：所述步骤S203中，判断所述所有节点的总数是否符合要求的方法为，判断所述所有节点的总数是否满足大于或等于要求的节点数值，如果满足则该节点的总数符合要求。
本发明提供的第七优选实施例中：所述步骤S3包括：
步骤S301，计算所述所有节点中各个所述节点的权值；
步骤S302，将所述各个节点按照权值进行排序；
步骤S303，选取所述所有节点中权值最高的所述节点。
本发明提供的一种基于网络拓扑结构的作业分配方法的有益效果包括：
本发明提供的一种基于网络拓扑结构的作业分配方法，基于网络拓扑结构的调度算法根据服务器所处网络位置，将同一作业的任务尽可能的调度至同一网络区域中，能够提升高“通信/计算”比率作业的运行效率，比率越高，提升效果越好。相对于其他现有技术，网络模型更为精确，适应性更好，执行效率提升更加明显。
附图说明
如图1所示为本发明提供的一种基于网络拓扑结构的作业分配方法中选择节点的方法流程图；
如图2所示为本发明提供的一种基于网络拓扑结构的作业分配方法中选择节点的实施例的方法流程图。
具体实施方式
本发明提供一种基于网络拓扑结构的作业分配方法，该方法应用于计算机集群，节点为计算机集群系统中的单个计算机，选择节点的方法如图1所示，包括：
步骤S1，选取一个节点，得到该节点所属的交换机。
步骤S2，根据节点所属交换机和拓扑关系，获得与该节点所属交换机的拓扑距离小于等于TopologyChoosedDepth的所有交换机，判断该所有交换机包含的所有节点的总数是否符合要求，是，执行步骤S3，否，执行步骤S1。
TopologyChoosedDepth为网络拓扑结构的调查深度。
步骤S3，选取所有节点中权值最大的节点，结束。
实施例一：
本发明提供的实施例为一种基于网络拓扑结构的作业分配方法中选择节点的实施例，其方法流程图如图2所示。
具体的，步骤S1从可用节点中的第一个节点，依次选取一个节点，步骤S2中在得到的所有交换机包含的所有节点的总数不符合要求时，执行步骤S1，选取下一个节点，具体操作方法为：
步骤S1中，设置节点的编号i=0，选取编号为i的节点，得到编号为i的节点所属的交换机。
步骤S2中，在得到的所有交换机包含的所有节点的总数不符合要求时，对编号i进行加一操作后，执行步骤S1选取下一个节点。
优选的，在对编号i进行加一操作后，判断i是否小于或等于节点长，是，执行步骤S1，否，根据尽可能交付MaximumDelivery值判断是否放弃调度。具体为：
判断尽可能交付MaximumDelivery值是否为1，是，按照顺序选取可用节点，否，放弃调度，结束。
步骤S2中根据节点所属交换机和拓扑关系获得与该节点所属交换机的拓扑距离小于等于TopologyChoosedDepth的所有交换机的方法为：
步骤S201，设置拓扑距离j=0。
步骤S202，判断j是否满足小于或等于TopologyChoosedDepth，是，执行步骤S203，否，执行步骤S3。
步骤S203，获得与节点所属交换机的拓扑距离小于或等于j的所有交换机，判断该所有交换机包含的所有节点的总数是否符合要求，是，执行步骤S3，否，对j进行加一操作后执行步骤S202。
具体的，判断所有节点的总数是否符合要求的方法为，判断该所有节点的总数是否满足大于或等于要求的节点数值，如果满足则该节点的总数符合要求。
步骤S3包括：
步骤S301，计算所有节点中各个节点的权值。
步骤S302，将该各个节点按照权值进行排序。
步骤S303，选取所有节点中权值最高的节点。
以上虽然根据附图对本发明的实施例进行了详细说明，但不仅限于此具体实施方式，本领域的技术人员根据此具体技术方案进行的各种等同、变形处理，也在本发明的保护范围之内。

Claims (8)

1.一种基于网络拓扑结构的作业分配方法，所述方法应用于计算机集群，其特征在于，选择节点的方法包括：
步骤S1，选取一个节点，得到所述节点所属的交换机；
步骤S2，根据所述节点所属交换机和拓扑关系，获得与所述节点所属交换机的拓扑距离小于等于TopologyChoosedDepth的所有交换机，判断所述所有交换机包含的所有节点的总数是否符合要求，是，执行步骤S3，否，执行步骤S1；
所述TopologyChoosedDepth为网络拓扑结构的调查深度；
步骤S3，选取所述所有节点中权值最大的节点，结束。
2.如权利要求1所述的方法，其特征在于，所述步骤S1从可用节点中的第一个节点，依次选取一个节点，步骤S2中在得到的所有交换机包含的所有节点的总数不符合要求时，执行步骤S1，选取下一个节点，具体操作方法为：
步骤S1中，设置节点的编号i＝0，选取编号为i的节点，得到所述编号为i的节点所属的交换机；
步骤S2中，在得到的所有交换机包含的所有节点的总数不符合要求时，对所述编号i进行加一操作后，执行所述步骤S1选取下一个节点。
3.如权利要求2所述的方法，其特征在于，在对所述编号i进行加一操作后，判断所述i小于或等于节点长时执行步骤S1。
4.如权利要求3所述的方法，其特征在于，判断所述i大于所述节点长时，根据尽可能交付MaximumDelivery值判断是否放弃调度。
5.如权利要求4所述的方法，其特征在于，根据所述MaximumDelivery值判断是否放弃调度的方法为：
判断所述MaximumDelivery值是否为1，是，按照顺序选取可用节点，否，放弃调度，结束。
6.如权利要求1所述的方法，其特征在于，步所述骤S2中根据所述节点所属交换机和拓扑关系获得与所述节点所属交换机的拓扑距离小于等于TopologyChoosedDepth的所述所有交换机的方法为：
步骤S201，设置拓扑距离j＝0；
步骤S202，判断所述j是否满足小于或等于TopologyChoosedDepth，是，执行步骤S203，否，执行步骤S1；
步骤S203，获得与所述节点所属交换机的拓扑距离小于或等于j的所有交换机，判断所述所有交换机包含的所有节点的总数是否符合要求，是，执行步骤S3，否，对所述j进行加一操作后执行步骤S202。
7.如权利要求6所述的方法，其特征在于，所述步骤S203中，判断所述所有节点的总数是否符合要求的方法为，判断所述所有节点的总数是否满足大于或等于要求的节点数值，如果满足则该节点的总数符合要求。
8.如权利要求1所述的方法，其特征在于，所述步骤S3包括：
步骤S301，计算所述所有节点中各个所述节点的权值；
步骤S302，将所述各个节点按照权值进行排序；
步骤S303，选取所述所有节点中权值最高的所述节点。
CN201210359410.6A 2012-09-24 2012-09-24 一种基于网络拓扑结构的作业分配方法 Active CN102904750B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201210359410.6A CN102904750B (zh) 2012-09-24 2012-09-24 一种基于网络拓扑结构的作业分配方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201210359410.6A CN102904750B (zh) 2012-09-24 2012-09-24 一种基于网络拓扑结构的作业分配方法

Publications (2)

Publication Number Publication Date
CN102904750A CN102904750A (zh) 2013-01-30
CN102904750B true CN102904750B (zh) 2017-06-23

Family

ID=47576799

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201210359410.6A Active CN102904750B (zh) 2012-09-24 2012-09-24 一种基于网络拓扑结构的作业分配方法

Country Status (1)

Country Link
CN (1) CN102904750B (zh)

Families Citing this family (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN108537619A (zh) * 2018-03-05 2018-09-14 新智数字科技有限公司 一种基于最大流算法的任务分配方法、装置及设备
CN116775258A (zh) * 2022-03-08 2023-09-19 华为技术有限公司 资源调度方法、装置及相关设备

Citations (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100749822B1 (ko) * 2006-11-17 2007-08-17 한국전자통신연구원 센서 네트워크의 노드에서 동시에 발생하는 트래픽처리방법
CN101414975A (zh) * 2008-11-28 2009-04-22 中兴通讯股份有限公司 基于对等网络的服务节点选择方法及装置、索引实体
CN101478426A (zh) * 2009-01-16 2009-07-08 中国人民解放军信息工程大学 网络拓扑模型生成方法和系统
CN101539800A (zh) * 2009-05-05 2009-09-23 曙光信息产业(北京)有限公司 一种低功耗作业调度计算方法
CN101635732A (zh) * 2009-08-27 2010-01-27 迈普通信技术股份有限公司 一种融合ip网络与集群网络的网络管理系统及其方法
CN101645022A (zh) * 2009-08-28 2010-02-10 曙光信息产业(北京)有限公司 用于多个集群的作业调度管理系统及方法
CN101694630A (zh) * 2009-09-30 2010-04-14 曙光信息产业(北京)有限公司 一种作业调度方法、系统及设备
CN101986661A (zh) * 2010-11-04 2011-03-16 华中科技大学 一种改进的虚拟机群下MapReduce数据处理方法
CN102118297A (zh) * 2009-12-31 2011-07-06 联想(北京)有限公司 一种计算机机群作业调度方法和系统
CN102402461A (zh) * 2011-12-08 2012-04-04 曙光信息产业(北京)有限公司 一种基于作业规模的均衡调度方法
WO2012087767A2 (en) * 2010-12-20 2012-06-28 Microsoft Corporation Scheduling and management in a personal datacenter

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101819540B (zh) * 2009-02-27 2013-03-20 国际商业机器公司 在集群中调度任务的方法和系统

Patent Citations (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100749822B1 (ko) * 2006-11-17 2007-08-17 한국전자통신연구원 센서 네트워크의 노드에서 동시에 발생하는 트래픽처리방법
CN101414975A (zh) * 2008-11-28 2009-04-22 中兴通讯股份有限公司 基于对等网络的服务节点选择方法及装置、索引实体
CN101478426A (zh) * 2009-01-16 2009-07-08 中国人民解放军信息工程大学 网络拓扑模型生成方法和系统
CN101539800A (zh) * 2009-05-05 2009-09-23 曙光信息产业(北京)有限公司 一种低功耗作业调度计算方法
CN101635732A (zh) * 2009-08-27 2010-01-27 迈普通信技术股份有限公司 一种融合ip网络与集群网络的网络管理系统及其方法
CN101645022A (zh) * 2009-08-28 2010-02-10 曙光信息产业(北京)有限公司 用于多个集群的作业调度管理系统及方法
CN101694630A (zh) * 2009-09-30 2010-04-14 曙光信息产业(北京)有限公司 一种作业调度方法、系统及设备
CN102118297A (zh) * 2009-12-31 2011-07-06 联想(北京)有限公司 一种计算机机群作业调度方法和系统
CN101986661A (zh) * 2010-11-04 2011-03-16 华中科技大学 一种改进的虚拟机群下MapReduce数据处理方法
WO2012087767A2 (en) * 2010-12-20 2012-06-28 Microsoft Corporation Scheduling and management in a personal datacenter
CN102402461A (zh) * 2011-12-08 2012-04-04 曙光信息产业(北京)有限公司 一种基于作业规模的均衡调度方法

Also Published As

Publication number Publication date
CN102904750A (zh) 2013-01-30

Similar Documents

Publication Publication Date Title
CN103885831B (zh) 虚拟机宿主机的选择方法与装置
CN104484233B (zh) 一种资源分配方法
CN110163469A (zh) 调度任务排序方法及装置
CN101303749A (zh) 面向客户需求的车间作业调度方法
CN103338461B (zh) 基于业务量预测的网络规划方法及装置
CN102262567A (zh) 虚拟机调度决策的系统、平台及方法
CN103576829A (zh) 基于混合遗传算法的云计算虚拟机动态调度方法
CN108170530A (zh) 一种基于混合元启发式算法的Hadoop负载均衡任务调度方法
CN107529656A (zh) 一种社交网络社区的划分方法及服务器
CN101568127A (zh) 一种网络仿真中确定话务分布的方法及装置
CN102323957A (zh) 基于垂直划分模式的分布并行Skyline查询方法
CN102904750B (zh) 一种基于网络拓扑结构的作业分配方法
CN106325976A (zh) 一种渲染任务调度处理方法及服务器
CN105825437A (zh) 一种复杂水库群共同供水任务分配方法
CN102541622A (zh) 一种负载相关的虚拟机放置方法
CN114205830A (zh) 一种智能电网通信网规划方法、系统、设备及存储介质
CN107506233A (zh) 一种虚拟资源调度方法、装置及服务器
CN109976879B (zh) 一种基于资源使用曲线互补的云计算虚拟机放置方法
CN108428155A (zh) 一种基于业务特征模型的行为处理分析方法
CN104507166A (zh) 一种基带池内共享虚拟资源配置方法
CN113326135A (zh) 一种多目标下的云资源调度方法
CN107589980A (zh) 一种云计算资源的调度方法
CN116501272A (zh) 一种基于改进遗传算法的3d打印订单任务调度方法
CN104182853B (zh) 一种引航员指派模型建立及其求解方法
CN118312312A (zh) 基于多目标强化学习的云数据中心负载均衡智能优化方法

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant
TR01 Transfer of patent right
TR01 Transfer of patent right

Effective date of registration: 20220803

Address after: 100193 No. 36 Building, No. 8 Hospital, Wangxi Road, Haidian District, Beijing

Patentee after: Dawning Information Industry (Beijing) Co.,Ltd.

Patentee after: DAWNING INFORMATION INDUSTRY Co.,Ltd.

Address before: 100193 No.36 Zhongguancun Software Park, No.8 Dongbeiwang West Road, Haidian District, Beijing

Patentee before: Dawning Information Industry (Beijing) Co.,Ltd.