资源电驴关键词

162网格环境中资源发现方法研究网格环境中资源发现方法研究网格环境中资源发现方法研究网格环境中资源发现方法研究龚奕利龚奕利龚奕利龚奕利1,2李李李李伟伟伟伟1孙毓忠孙毓忠孙毓忠孙毓忠1(1.
中国科学院计算技术研究所软件研究室北京1000802.
中国科学院研究生院北京100039)摘摘摘摘要要要要提出了一种新的C/S和P2P结合的网格环境中的资源发现机制――VIRD它采用属性-值对的请求描述方法提供了比基于名字的方法更强的查询能力VIRD采用3层结构资源信息在同一域内定期更新传播用户请求先在域内进行查找如果不能满足再转发到域间试验显示即使在资源频度比较低允许的最大TTL值很小的情况下VIRD仍能获得比较高的查找成功率和flooding和randomwalk相比在相同查找成功率的情况下VIRD所需的网络通信量和响应时间远小于二者关键词关键词关键词关键词网格资源发现P2PVIRDResearchonResourceDiscoveryinGridEnvironmentsGONGYili1,2,LIWei1,SUNYuzhong1(1.
SoftwareDivision,InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100080;2.
GraduateSchoolofChineseAcademyofSciences,Beijing100039)AbstractThispaperproposesaC/SandP2Phybridresourcediscoveryframework,VIRD.
Itadoptsarequestdescriptionapproachbasedonattribute-valuepairs.
VIRDadoptsthethree-layerarchitecture.
Resourceinformationispropagatedwithinadomainperiodically.
Userrequestsarehandledindomainsfirst.
Iftherearenosatisfactoryresources,therequestwillbeforwardedtothebackbone.
Accordingtothesimulations,evenwhentheresourcedensityislowandthemaxTTLissmall,VIRDcanstillachievehighsuccessrate.
Comparedwithfloodingandrandomwalk,withthesamesearchsuccessrate,thenetworktrafficandrequestresponsetimeofVIRDaremuchlessthanthem.
KeywordsGrid;Resourcediscovery;Peer-to-peer;VIRD计计计计算算算算机机机机工工工工程程程程ComputerEngineering第第第第32卷卷卷卷第第第第17期期期期Vol.
32172006年年年年9月月月月September2006网络与通信网络与通信网络与通信网络与通信文章编号文章编号文章编号文章编号10003428(2006)17016203文献标识码文献标识码文献标识码文献标识码A中图分类号中图分类号中图分类号中图分类号TP393资源发现是网格系统中一个非常重要的部分指的是根据用户的请求找到满足条件的资源的过程然而网格环境具有动态性和异质性这些特性都对资源发现产生很大的影响造成一定的困难现有的资源查找方法主要有两种集中式的和分布式的集中式资源管理查找效率较高但可扩展性较差而且存在单一故障点而像P2P这样的分布式系统自治性和可扩展性好但基于属性的查找效率不够好文献[1]中给出了3层结构的VIRDVegaInfrastructureforResourceDiscovery但是没有给出具体的域间请求路由算法没有对整个3层结构进行验证和性能测试本文完善了VIRD结构给出了完整的域内信息更新算法域内和域间请求路由算法并进行了全面的测试并与P2Pflooding和randomwalk算法进行了比较由于网格中资源的数量和种类可能会很多而且还在不断地变化因此只用id描述是不够的我们提出了一种描述能力强使用简单的属性-值对描述方法VIRD的3层结构使得用户和资源接入到GRNS服务器能够进行注册信用管理等增强了可操作性可管理性和安全性资源信息在同一域内定期更新传播用户请求先由GRNS根据本地了解的域内资源信息进行查找如果域内不能满足再转发到相应的BGRNS直至找到满足条件的资源或者超时丢弃域间路由采用的是修改了的flooding算法从用户角度来看主要关注的是请求查找的成功率和请求响应时间而从系统角度来看主要关心的是网络通信量我们开发了一个可配置的事件驱动的模拟器即SimVIRD来验证我们的结构同时还将它与flooding和randomwalk算法进行了比较从试验数据可以看出在同一资源频度下请求查找成功率随允许的最大TTL值TTLmax的增大而提高而在相同TTLmax下资源频度越高查找成功率也越高根据比较测试知道在相同查找成功率下VIRD的通信量和响应时间都小于另外两种方法1相关工作相关工作相关工作相关工作针对网格环境中的资源发现人们已经做了大量的工作Condor的Matchmaker采用集中式结构来查找计算资源中央服务器负责对资源请求者和资源提供者的声明中的属性进行匹配Legion使用Collections在网格中搜索和定位资源当用户请求一个资源时Legion会在多个Collections中查询资源信息如果找到多个这样的资源Legion的资源调度器就会随机地选择一个Globus的MDS-2[2]是分布式的资源信息服务系统资源提供者使用注册协议将资源信息注册到GIIS而用户使用查询协议访问GIIS和GRIS的资源信息P2P技术主要可以分为两大类一类是无结构的包括GnutellaFreenet等另一类是有结构的例如PastryTapestryCAN和ChordGnutella使用的协议是基于广播的基金项目基金项目基金项目基金项目国家自然科学基金资助项目69925205国家863计划基金资助项目2002AA104310国家973计划基金资助项目2003CB3170082005CB321807中国科学院百人计划基金资助项目GrantNo.
20044040作者简介作者简介作者简介作者简介龚奕利(1976)女博士生主研方向网格分布式计算李伟副研究员博士孙毓忠研究员博士收稿日期收稿日期收稿日期收稿日期2005-11-24E-mailgongyili@ict.
ac.
cn163对带宽的要求比较高限制了系统的可扩展性有结构的查找效率会好于无结构的但是这类方法很难应用到网格资源查找中因为它们适用于具有唯一ID比如文件名的对象查找但是在网格中往往需要基于资源的属性值进行查找很难将具有多种可变属性的资源形式化为一个名字或者ID2VIRD的设计的设计的设计的设计2.
1总体结构总体结构总体结构总体结构一个VIRD系统如图1所示顶层是一个骨干网由边界网格资源名字服务器组成第二层包括多个域每个域都是由多个网格资源名字服务器组成的而第三层是叶子包括客户端和资源提供者BGRNSBGRNSBGRNSBGRNS主干网GRNSGRNSGRNS域CRPBGRNS:边界网格资源名字服务器GRNS:网格资源名字服务器RP:资源提供者C:客户端图图图图1VIRD的体系结构的体系结构的体系结构的体系结构(1)边界网格资源名字服务器BGRNS它连接着主干网和一个或者多个域在回答资源查询请求时它们在域间转发请求帮助查找满足条件的资源(2)网格资源名字服务器GRNS它动态地收集注册到它的资源的信息并将这些信息传播到域中其他的GRNS当GRNS收到来自客户端的请求时它会试着根据它的本地资源信息或者通过BGRNS来寻找合适的资源并返回给用户一个访问使用该资源的句柄或者返回查找失败(3)资源提供者当资源提供者启动时它把自己注册到一个GRNS这个GRNS称为该资源提供者的指定GRNS并定期向它报告自己的状态或者在状态发生改变时再报告同时资源提供者还接收用户请求并为之服务(4)客户端它向GRNS发送请求并接收回答一台主机可以同时既是客户端又是资源提供者2.
2域内更新算法域内更新算法域内更新算法域内更新算法域内更新算法是资源信息动态地在域内传播的算法GRNS周期性或者在下列情况中的一种或多种发生之时构造资源状态包RSP(1)发现一个新邻居(2)一个邻居下线(3)注册到它的资源状态发生改变如果使用了触发机制如果在一定的时间内没有触发事件发生GRNS也应该向它的邻居发送一个空的RSP否则邻居们可能认为它已经不可用了每个GRNS都会记录下它最后一次产生的RSP的序列号当它生成新的RSP时就会使用下一个序列号GRNS还会记录所有来自其他GRNS的RSP的最新序列号当它收到一个RSP时就会比较新收到的RSP的序列号和内存中记录的序列号如果前者较大表明这个RSP较新就会用它来更新路由表否则就丢掉2.
3域内路由算法域内路由算法域内路由算法域内路由算法当收到来自用户的请求时GRNS会首先检查它的本地资源如果有满足条件的资源就保留该资源并返回给用户一个访问句柄如果本地没有GRNS就会搜索域的资源表如果发现合适的资源就向该资源的指定GRNS发一个确认请求收到确认请求的GRNS根据资源的当前状况返回访问句柄或者确认失败如果请求确认失败一定次数或者域内没有满足条件的资源就把请求转发到相应的BGRNS交由域间路由算法来回答2.
4域间路由算法域间路由算法域间路由算法域间路由算法域间路由算法主要是在Gnutellaflooding协议的基础上做了一些修改考虑到BGRNS上数据量的大小以及两个BGRNS所代表的域内资源的距离造成的资源属性的时效性一个BGRNS不存储其他域内资源的信息我们的域间路由算法与Gnutella略有不同搜索响应不必沿着请求经过的路径返回至请求者而是由满足条件的GRNS节点直接向该请求的初始GRNS发送响应3试验试验试验试验3.
1模拟器模拟器模拟器模拟器我们设计实现了一个可配置的事件驱动的模拟器SimVIRD用于模拟VIRD还将它与flooding和randomwalk算法进行了比较3.
2标准标准标准标准我们感兴趣的指标为(1)响应时间从请求到达它的初始GRNS至有节点宣布本地有满足条件的资源为止所耗费的时间(2)通信量我们将VIRD的通信量分为系统通信量Trafficsys和用户通信量Trafficusr前者是资源信息更新引起的后者是回答用户请求引起的而flooding和randomwalk系统只有用户通信量通信量单位为包的个数(3)请求成功率找到满足要求的请求的百分比3.
3输入和参数输入和参数输入和参数输入和参数我们模拟的输入包括(1)网络拓扑各个域的GRNS网络和域间的BGRNS网络都是用GridG[3]生成的主干网有256个BGRNS每个域有64个GRNS(2)资源分布我们模拟的是计算资源它的属性由GridG生成其中有一个动态属性――机器的负载我们用资源密度来指示资源数量的多寡也就是()RDBGRSGRNS=*资源数量资源密度数量每个域中的数量(3)负载分布资源的动态属性负载的分布是根据GridG生成的资源的初始状态统计得出的(4)资源动态属性变化周期Tres_change负载每隔Tres_change就会发生一次变化变化后的值也服从初始分布(5)资源信息更新周期Tupdate资源信息更新周期是指每隔TupdateGRNS会将它知道的新信息传播到它的邻居(6)请求周期Trequest和分布假设有1000个用户请求每个请求在一个用户请求周期内随机到达的请求的内容就是寻找负载小于等于特定值的资源其值也服从与资源相同的分布(7)最大TTL值系统允许的最大TTL值3.
4结果结果结果结果每组仿真试验都重复了100次所有测试结果都取的是平均值第1组测试主要是比较在各种资源频度和TTLmax取值下VIRD的请求成功率和域间转发请求个数我们可以看到在相同资源频度下查找成功率随允许的最大TTL值的增长而提高而在相同TTLmax下资源频度越高查找成功率也高即使在资源频度很低的状况下使用很小的TTLmaxVIRD的查找成功率仍然很高例如RD=0.
005查找成功率为87.
31%而RD=0.
01时查找成功率为96.
15%在后面的测试中我们默认地将TTLmax设为4第2组测试是对比3种方法的请求查找成功率通信量164121086420TrafficstandardizedtoF7TTLMAXVIRD4F4F5F6F7F8F9F10F11RW100RW300RW1000和响应时间的其中RD=0.
05Tres_change=Tupdate=0.
1sTrequest=1msVIRD的TTLmax4flooding的TTLmax分别为4~11randomwalk的TTLmax分别为100300和1000图2中VIRD的TTL为4flooding的TTL是3~11randomwalk的TTL是100300和1000图3的条件同图2从图2中可以看到VIRD方法在TTLmax=4时简称VIRD4的请求查找成功率99.
99%比F11的查找成功率98.
95%都要高F7的查找成功率仅为87.
05%当请求频率增加时Trafficsys并不增加增加的只是Trafficusr图3和图4都是以flooding在TTLmax7时F7的值为标准值1取得的相对值之所以以F7为标准是因为大多数Gnutella系统默认的TTLmax就是7图3表明VIRD4的Trafficusr以及Trafficsys和Trafficusr分别只是F7的3.
48%和26.
83%更是只有F11的0.
30%和2.
31%Successrate(%)TTLMAX100806040200VIRD4F4F5F6F7F8F9F10F11RW100RW300RW1000图图图图2VIRD,flooding和和和和randomwalk的成功率的成功率的成功率的成功率图图图图3VIRDflooding和和和和randomwalk的网络开销的网络开销的网络开销的网络开销图4的条件同图2从图4可以看出VIRD4的响应时间是F7的97.
48%比F11快15.
25%VIRD4的响应时间长于F4F5和F6这是因为它们只在很小的范围内查找所以对于成功的请求来说响应时间很短但是它们的查找成功率很低56.
79%~81.
03%对于一个资源查找系统来说这样的成功率是很难接受的从这组测试可以看出在相同查找成功率下VIRD的通信量远小于flooding系统的通信量VIRD的请求响应时间也小于flooding系统的请求响应时间图图图图4VIRD,flooding和和和和randomwalk的响应时间的响应时间的响应时间的响应时间4结论结论结论结论本文提出了一种C/S和P2P结合的网格环境中的资源发现机制VIRD它采用属性-值对的请求描述方法提供了比基于ID更强的查询能力VIRD的3层结构能够便于用户和资源的注册信用管理从试验可以看到即使在资源频度比较低的状况下使用很小的TTLmaxVIRD仍能获得比较高的查找成功率通过对VIRD与flooding和randomwalk的比较可以看出在相同查找成功率的情况下VIRD所需要的网络上的通信量和响应时间都远小于flooding和randomwalk系统参考文献参考文献参考文献参考文献1GongY,DongF,LiW,etal.
VEGAInfrastructureforResourceDiscoveryinGrids[J].
JournalofComputerScience&Technology,2003,18(4):413-422.
2CzajkowskiK,FitzgeraldS,FosterI,etal.
GridInformationServicesforDistributedResourceSharing[C].
Proceedingsofthe10thIEEEInternationalSymposiumonHigh-performanceDistributedCompu-ting(HPDC-10),SanFrancisco,CA,2001-08:181-194.
3LuD,DindaP.
SynthesizingRealisticComputationalGrids[C].
ProceedingsofSupercomputing,Phoenix,AZ,2003-11:16.
上接第161页结合中间节点和终端节点拥塞控制技术研究网络突发流量对于网络的影响和有效克服网络突发流量的策略与技术参考文献参考文献参考文献参考文献1BradenB.
RecommendationsonQueueManagementandCongestionAvoidanceintheInternet[S].
RFC2309,1998-04.
2FloydS,JacobsonV.
RandomEarlyDetectionGatewaysforCongestionAvoidance[J].
IEEE/ACMTransactionsonNetworking,1993,1(4):397-413.
3FengWC,KandlurD,SahaD,etal.
ASelf-configuringRedGateway[C].
Proc.
ofIEEEInfocom,NewYork,USA,1999:1320-1328.
4OttTJ,LakshmanTV,WongLH.
SRED:StabilizedRED[C].
Proc.
ofIEEEInfocom.
NewYork.
IEEECommunicationsSociety,1999:1346-1355.
5CiscoCorp.
WeightedRandomEarlyDectection(WRED)[Z].
http://www.
cisco.
com/univercd/cc/td/doc/product/software/ios120/12cgcr/qos_c/qcpart3/qcwred.
pdf.
6NSProject[EB/OL].
http://www.
isi.
edu/nsnam.
7李方敏,李仁发,叶澄清.
网络仿真软件ns的结果输出和分析[J].
计算机工程,2000,26(9):14-16.
TTLMAX87651.
31.
00.
80.
50.
30.
0VIRD4F4F5F6F7F8F9F10F11RW100RW300RW1000ResponsetimestandardizedtoF7