自愿计算中重叠网络拓扑对面向结点能力的非集中式调度方法的影响分析  

Influence of Overlay Topology on Capability-Centered Decentralized Resource Scheduling in Volunteer Computing Environment

作　　者：朱承[1] 刘忠[1] 张维明[1] 徐振宁[1] 阳东升[1] 

机构地区：[1]国防科学技术大学信息系统与管理学院,长沙410073

出　　处：《计算机学报》2005年第10期1638-1644,共7页Chinese Journal of Computers

基　　金：国家自然科学基金(70271004)资助.~~

摘　　要：自愿计算在大规模计算模式中正在扮演着越来越重要的角色.目前的自愿计算环境大多是专用和集中控制的,因而存在着某些可用性和可扩展性的问题.最新的研究提出了基于对端重叠网络的自愿计算环境构造方式,通过在各参与结点间建立更灵活的连接形成对端重叠网络来实现计算资源更灵活、有效的共享.面向结点能力的调度方法是为适应这一变化而提出的自愿计算中的一种非集中式资源调度方法,具有简单易行的特点.这一方法的效果在很大程度上取决于底层的重叠网络拓扑结构.文中建立了相应的理论分析模型,计算了该调度方法在具有不同度均值和聚合系数的对端重叠网络中搜索步长和最终所定位结点能力水平的期望.模型计算通过迭代进行,将时间复杂度控制在O(n3).利用3种不同的拓扑生成算法所产生的不同特征的重叠拓扑结构进行了仿真验证.模型的理论计算结果与仿真结果吻合良好,表明在具有较小的聚合系数和较大结点度均值的重叠网络中,面向结点能力的资源调度方法具有更好的效果.Current volunteer computing systems are essentially centralized systems, which lead to scalability and accessibility problems. The latest developments of volunteer computing introduce a new infrastructure based on P2P overlay topology. It facilitates more flexible and effective computing resource sharing by constructing P2P overlays among participants. Capability-centered resource scheduling is a new decentralized scheduling for the new volunteer computing environments, which is simple and lightweight. However, its effectiveness is influenced by the underlying overlay topologies. A theoretical analysis model is built in this paper, by which effectiveness of this decentralized scheduling method is evaluated. The model estimates expectations of searching hops as well as capability level of the final node located by the scheduling method under P2P overlay topologies with different degrees and cluster coefficients. The estimation is performed by iteration, which controls time complexity into O（na）. Simulation study is also performed on different overlay topologies generated by 3 different topology-generating methods. The estimation results of theoretical analysis model coincide with simulation results well. Both results show that, capability-centered resource scheduling method works better in overlay topologies with smaller cluster coefficient and bigger average degrees.

关 键 词：自愿计算 对等网 网络 资源 资源调度 模型 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]