主动队列管理RED算法改进与实验仿真研究

第３２卷　第１７期　１１ｏＬ３２　・计算机工程　２００６年９月　Ｓｅｐｔｅｍｂｅｒ　２００６　№ｌ７　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　网绛｝与通信・　文章编号：ｌＩ）００－．＿３４２８（２００６）ｌ７—｛ｌ１５９—｛ｌ３　文献标识码：Ａ　中图分类号：ＴＰ３９３　主动队列管理ＲＥＤ算法改进与实验仿真研究　陈军‘，邓晓衡２　９陈志刚２　９刘佳琦　惠州学院计算机科学系，惠州５１６０１５；！　ｆＩｌ南大学信息科学与工程学院，长沙４１００８３）　摘要：分析了ＲＥＤ及其改进算法的原　和局限性，提Ｕ　ｒ一种非线性高阶ＲＥＤ拥搴控制机制。该算法利用一个高Ｉ价分组丢弃函数，在　下限阂值附近以较低的概率标记丢弃分绑，住上：限闽值附近迅速提高分组的标记丢弃概率。并对网络仿真器ＮＳ２进行扩展，通过系列仿真　实验验证ｒ改进算法有效提高ｒ　络性能。　关健词：拥窄控制；早期随机丢弃；主动队列管理　Ｓｔｕｄｙ　０ｎ　Ａｃｔｉｖｅ　Ｑｕｅｕｅ　Ｍａｎａｇｅｍｅｎｔ　ＲＥＤ　ｌｍＤｒｏｖｅｍｅｎｔ　ａｎＩＴ　Ｊ　１　ｌｍｕｌａｔｉＯｎ　’　，１●　●　・●　ＣＨＥＮ　Ｊｕｎ　，ＤＥＮＧ　Ｘｉａｏｈｅｎｇ　，ＣＨＥＮ　Ｚｈｉｇａｎｇ　，ＬＩＵ　Ｊｉａｑｉ　（１．Ｄｅｐａｌ’ｔｍｅｎｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｈｕｉｚｈｏｕ　Ｕｎｉｖｅｒｓｉｔｙ．Ｈｕｉｚｈｏｕ　５　１　６０　１　５：　２．Ｃｏｌｌｅｇｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｃｅｎｔｒａｌ　Ｓｏｕｔｈ　Ｕｎｉｖｅｒｓｉｔｙ．Ｃｈａｎｇｓｈａ　４　１（）０８３】　［Ａｂｓｔｒａｃｔ］Ｔｈｉｓ　ｐａｐｅｒ　ｉｎｖｅｓｔｉｇａｔｅｓ　ＲＥＤ　ａｌｇｏｒｉｔｈｍｓ‘ｅｌｅｍｅｎｔｓ　ａｎｄ　ｌｉｍｉｔａｔｉｏｎ　ａｎｄ　ｉｎｔｒｏｄｕｃｅｓ　ａ　ｎｅｗ　ｎｏｎｌｉｎｅａｒ　ｈｉｇｈ　ｏｒｄｅｒ　ＲＥＤ　ａｌｇｏｒｉｔｈｍ　ｗｈｉｃｈ　ｅｍｐｌｏｙｓ　ａ　ｈｉｇｈ—ｏｒｄｅｒ　ｆｕｎｃｔｉｏｎ　ｔｏ　ｍａｒｋ　ｏｒ　ｄｉｓｃａｒｄ　ｆｒａｇｍｅｎｔｓ　ｗｉｔｈ　ｌｏｗｅｒ　ａｎｄ　ｈｉｇｈｅｒ　ｐｒｏｂａｂｉｌｉｔｙ　ｎｅａｒ　ｌｏｗ　ａｎｄ　ｈｉｇｈ　ｔｈｒｅｓｈｏｌｄ　ｒｅｓｐｅｃｔｉｖｅｌｙ　Ｆｈｅ　ｅｎｈａｎｃｅｄ　ＲＥＤ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ａｌｓｏ　ｉｍｐｌｅｍｅｎｔｅｄ　ｉｎ　ｔｈｅ　ｎｅｔｗｏｒｋ　ｓｉｍｕｌａｔｏｒ　ＮＳ２，ｔｈｅ　ｒｅｓｕｌｔｓ　ｏｆ　ｓｅｒｉｅｓ　ｓｉｍｕｌａｔｉｏｎ　ｅｘｐｅｒｉｍｅｍｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｉｍｐｒｏｖｅｓ　ｐｅｒｆｏｒｍａｎｃｅ　ｓｔａｂｌｅｎｅｓｓ　ａｎｄ　ｒｅｌｉａｂｉｌｉｔｙ　ｏｆ　ｎｅｔｗｏｒｋ．　［Ｋｅｙ　ｗｏｒｄｓ］Ｃｏｎｇｅｓｔｉｏｎ　ｃｏｎｔｒｏｌ：Ｒａｎｄｏｍ　ｅａｒｌｙ　ｄｅｔｅｃｔｉｏｎ（ＲＥＤ）：Ａｃｔｉｖｅ　ｑｕｅｕｅ　ｍａｌｌａｇｅｍｅｌｌｔ　中间节点流量控制算法是重要的拥塞控制增强机制，当　其采用传统的队列管理机制如Ｄｒｏｐ—ｔａｉｌ时，往往会在拥塞的　路由器一ｋ出现大的队列延时，凶此Ｄｒｏｐ—ｔａｉｌ队列管理机制在　输入：一个分组到来　输ｍ：该分组按概率Ｐ进行标记或丢弃　ｔ１）　始化：　维持高的带宽利用率（较大的缓存）和低的队列延时（较小　的缓存）之间存在着一种矛盾，为了解决这一矛盾，Ｂ．Ｂｒｄｅｎ　等提出了主动队列管理机制的研究…动议。Ｓ、Ｆｌｏｙｄ等提出的　早期随机丢弃（Ｒａｎｄｏｍ　Ｅａｒｌｙ　Ｄｅｔｅｃｔｉｏｎ．ＲＥＤ）［２１是主动队列管　理策略中最有代表性的，已经成为ＩＥＴＦ推荐的唯一的ＡＱＭ　候选策略。　（２）一个分组到来：　（３）ｉｆ队列非空ｔｈｅｎ　Ｑ　＝（１一ｗ　，）×Ｏ　＋¨’　，×Ｑ　ｆ，　：（１一ｗ　）　‘　’　Ｑ　＋Ｗｑ×　／　ｔ为当前时间，ｔｎ　为队列披区空的时间　／　（４）ｉｆＱ　＜ｅ．．ｉ　ｔｈｅｎ　ｌ　ＲＥＤ算法　１．１　ＲＥＤ算法原理　ＲＥＤ算法通过检测路由器的平均队列长度ｑ（路由器缓冲　区内数据包的平均数目）来检测网络拥塞，并以一定的概率丢　弃数据包来通知ＴＣＰ发送方发生拥塞。ＲＥＤ算法中的数据包　丢弃概率是一个关于ｑ的函数，它通过将　限制在一定水平　以下就可以避免突发式的连续丢掉来自于同一个连接的包，　Ｐ＝０；　分组全部通过　／　（５）ｅｌｓｅ　ｉｔ＂Ｑ　ｉ　＜Ｑ　、＜Ｑ　．　｛　Ｐ川　＝Ｐｍ，，ｘ（Ｑ—Ｑ　ｉ　．）／（Ｑ　Ｑ　ｉ．　）：　Ｐ＝Ｐ，ｎｐ／（Ｉ—ｃｏｕｎｌ×Ｐ　）：ｌ　／　Ｐ为分组标记或丢弃的概率　／　／　ｃｏｕｎｔ表示Ｑ　ｉ　＜Ｑ　＜Ｑ　时排队（没有被丢弃）的分组数目　／　ｆ６）ｅｌｓｅ　Ｐ＝ｌ；　全部标记或丢弃到来的数据包　／　ｆ７）ｅｎｄ；　将ｑ跟２个阈值（最小阈值ｑ…和最大闽值ｑｍａ０相比较，就可　以计算出数据包丢弃概率，如式ｆｉ）：　０．　ｑ　ｑ　基于端到端的拥塞控制机制在网络空闲时不断增大发送　速率，直到分组丢失，再被动进行拥塞挖制，网络的吞吐最　总是处十一种周期振荡。显然，ＲＥＤ算法是一种主动拥塞控　Ｐ（ｑ）　Ｐ　ｑ　二　＿，　．　（１）　一　ｍｉｎ　制机制，通过监测平均队列长度来确定网络拥塞的程度，采　基金项目：教育部高校博士点基金资助项目ｆ２００４０５３３０３６）；国家　自然科学基金资助项目ｆ６０５７３１２７）　１，　ｑ＞　其中Ｐｍａ　为路由缓冲队列达到最大阈值ｑ　时的丢弃概率。　ＲＥＤ的缺点在于选择参数（ｑ　ｑ　¨＂ｐ　）非常困难，如果参　数配置不当，网络性能会显著降低　，因此得到大黾的研　究　。ＲＥＤ算法具体实现分组标记／丢弃的策略如下：　作者简介：陈军（１９６２一），男，副教授，主研方向：计算机Ｉ叫络；　邓晓衡，博士；陈志刚，博士、教授；刈佳琦，硕士生　收稿日期：２００６—０３—２５　Ｅ－ｍａｉｌ：ｄｘｈ＠ｃｓｕ．ｅｄｕ．ｃｎ　】５９—　维普资讯 http://www.cqvip.com

用按一定比例随机地标记或丢弃分组的方法，有效地克服了　源端算法的往返时间倒数关系的不公平性和全局同步及存在　振荡的缺陷，利用低通滤波器计算平均队列长度，有效解决　了网络流量的突发性对网络稳定性的影响，实验结果显示　ＲＥＤ性能优于ＤｒｏｐＴａｉｌ　。　１．２　ＲＥＤ算法局限性　虽然ＲＥＤ算法具有上节所述的多种优点，但它存在两个　主要缺陷：　（１）ＲＥＤ对参数的设置敏感，参数变化对性能影响大。　这是ＲＥＤ自提出以来被大量地研究却并没有被广泛应用的　重要原因。下面着重讨论ＲＥＤ算法中的几个重要参数：　Ｊ）　为平均队列长度，作为动态计算分组丢弃标记概　率的依据，计算公式如Ｆ：　（ｂ）ＨＯ—ＲＥＤ　Ｑ　＝（Ｊ—　）×Ｑ　＋Ⅵ　×Ｑ　，　图１改进前后丢包率同平均　长的关系　Ｑ　为瞬时队列长度，ｗｑ为滑动平均函数的权值。ｗｑ　我们可以确定Ｐ～Ｑ　的曲线。综合所述，得出ＨＯ—ＲＥＤ　的大小决定了Ｑ　对Ｑ　、的影响严重程度，ｗ　越小，表明　分组丢弃概率Ｐ如式（２）。　Ｑ　随Ｑ　的变化不明显，ｗｑ越大，说明Ｑ　紧随Ｑ　的变　化而变化，选择合适的帅确保Ｑ　适度的灵敏性使网络缓解　Ｐ＝：　ｆｉ　Ｑ　＜Ｑ　＜Ｑ　（２）　突发＿流量的影响，又能对网络的拥塞作出适度反应，避免多　个数据流的同步。　ｅｌｓｅ　２）Ｑ　。　、Ｑ　两个门限值分男０为分组全部通过时最大甲　２　ＮＳ２：扩展与实验仿真　均队列长度和分组全部丢弃时的最小平均队列长度，中间节　２．１仿真器原理　点的平均队列长度一般局限于这两个门限之间变化，如何充　ＮＳ２由美国ＤＡＲＰＡ和ＮＳＦ项目资助开发，是一个面向　分利用缓存资源又减少分组通过中间节点的延迟，同时保证　对象的、离散的、事件驱动的网络仿真工具，已经能够完成　网络的高吞吐量，这本身就存在矛盾，要充分利用缓存资源，　从网络物理层到应用层的多种仿真实验。ＮＳ２的开放式的代　就要增加队列长度，而队列长度增加，又会增加网络的延迟。　码和模块化的设计使得用户有可能根据新设计的网络协议特　３）Ｐ。　为分组丢弃概率跳转到ｌ之前的最大丢弃概率，　点增加新的功能模块，通过对原有ＮＳ２系统的功能扩展，实　ＲＥＤ算法中分组丢弃概率随Ｑ　从Ｑ　。　到Ｑ　由０线性增　现ＲＥＤ改进算法，再编写仿真测试ＴＣＬ脚本，进行仿真实　长到Ｐ　。Ｐ　决定了拥塞指示程度，取值偏大会导致拥塞　验，获得ｔｒａｃｅ数据进行分析，评估算法的性能。ＮＳ２使用　指示过重，分组丢弃过多，网络吞吐量降低，缓存区占用也　ｃ＋＋和ＯＴｃｌ两种编程语言模型，保证了仿真效率和灵活性的　随之下降，取值偏小会导致拥塞指示过轻，缓存区容易溢出，　高度统一，对于需要涉及处理字节、分组以及大量数据集的　形成ＤｒｏｐＴａｉｌ方式，使系统增加了计算　却不能发挥应有的　基本算法操作，而不会频繁修改的任务，利用Ｃ＋＋编译型语　控制作用，其性能甚至比ＤｒｏｐＴａｉｌ更差。　言实现：．对于需要频繁的修改协议对象的配置和数据流的配　由于ＲＥＤ算法对参数非常敏感，许多研究者试图找到一　置，利用ＯＴｃｌ脚本解释性语言编写仿真脚本，可以是交互的，　种普适的参数设定规律，然而，网络连接和业务是多样的且　便于多；欠模拟配置，实现非常灵活。　不断变化，很难找到一种普适的规律。　基ｆ－ＮＳ２的网络仿真的一般步骤是，首先判断ＮＳ２中是　（２）ＲＥＤ算法中的平均队列长度随着加入网络的连接数　否包含需仿真算法对应的功能模块，如果有，则只需根据仿　的增加而增加。这使得分组通过中间节点的延迟会因此而增　真需要编写Ｔｃｌ测试脚本执行，然后再分析实验所记录的数　加，将对许多对延迟敏感的网络业务产生影响。　据，得出结论；如果不包含该功能模块，则必须对ＮＳ２进行　１．３ＲＥＤ算法改进　功能扩展，构成新的ＮＳ２仿真系统，再进行前述的工作。具　ＲＥＤ算法的丢包率与ｆ均队列长度是一种线性关系，在　体过程　２口图２所示。　最小阂值附近容易产生较高的丢包率，而此时网络并非　处于一种严重拥塞状态，因此有必要对丢包率函数进行　改进，我们引入基于队列长度的高阶函数，改进算法称　为ＨＯ—ＲＥＤ，本文中采用二阶函数。因为高阶函数在队　列长度接近最小阈值时丢包率比较低，但是又不像增加　最小阈值大小方法，将丢包率设置为零而失去对网络的　调节能力，高阶函数在最小阂值附近变化平滑，随着平　图２ＮＳ２网络仿真过程　均队列的增长慢慢增长。当平均队列接近最大阀值时，其丢　２．２　ＮＳ２　仿真器扩展　包概率的增长速度也随之较快，能较快从网络严重拥塞状态　新算法修改的对象是ＮＳ一２中的Ｑｕｅｕｅ／ＲＥＤ队列管理算　下解脱出来，因此ＨＯ—ＲＥＤ能够在网络相对空闲时，降低网　法，其通过继承ＴｃｌＯｂｊｅｃｔ来实现模拟和仿真。ＲＥＤ算法又　络丢包率，而在拥塞状态下迅速提高丢包率，从而增强了对　是从Ｑｕｅｕｅ类继承下来的，其类结构层次如图３所示，根据　网络拥塞的调节能力，提高网络资源的利用率，提高吞吐量。　中间节点各类的层次结构和继承关系，ＲＥＤ算法Ｑｕｅｕｅ父　ＲＥＤ与ＨＯ—ＲＥＤ算法原理如图Ｊ所示。　类中３个需要雨载的关键函数：　】６０－－　维普资讯 http://www.cqvip.com

（１）函数ｃｏｍｍａｎｄ（），该函数是提供给ＯｔｃＩ脚本对一些　参数和选项进行设置的接口。　（２）函数ｄｅｑｕｅ（），出队列函数，返回一个数据包指针，　这个数据包将会被转发。　（３）函数ｅｎｑｕｅ（），进队列函数，在这个函数中实现　ＳＣＯＲＥ算法来进行路由器的缓存管理，决定是否转发新接收　到的数据包。　ＨＯ—ＲＥＤ算法的扩展无需构建新的类，只需对ＲＥＤ算法　基础进行适当修改，通过引入一个控制开关，决定是调用　数据流和ＦＴＰ数据流分组廷迟比较如图５和网６所示。　０　０　５　１　０　１　５　２　０　２　５　３　０　３　５　４　０　４　５　Ｔｉｍ　ｅ（ｓ）　ＲＥＤ算法或改进算法。在ｒｅｄ．ＣＣ文件中新算法主要修改的部　分包括：构造函数ＲＥＤＱｕｅｕｅ（）对相关参数进行初始化，同时　圈５改进前后ｃｂｒ数据流的延迟比较　将ｃ＋＋类的变量与Ｏｔｃｌ中的变量进行绑定，这样就可以在用　户编写的Ｔｃｌ脚本中构造Ｏｔｃｌ变量来调用这些ｃ＋＋变量；以　及对计算概率的函数ｃａｌｃｕｌａｔｅ—Ｐ—ｎｅｗ（）根据第１节所述原理　进行修改。类结构层次图见图３。　／／，匝亟　ｌ　ｉｎｉｔＰａｒａｍ　ｓ（）］　１　Ｃｏｍｍａｎｄ（）１　。。。。。。。。。。。。。Ｅ。。。‘ｎ。ｑ‘　ｕ。。　‘ｅ（。　）　‘——　［　１ｄｅｑｕｅ（）］　一∞一　Ｂ１∞ｏ　—１　１　１　０　０　０　０　０　０　０　ｒｅｓｅｔ（—）］２　１　０　９　８　　７　６　５　４　３　　Ｉｅ　ｓｔｉｍａｔｏｒ（）］　　ｌｃａｌｃｕｌａｔｅ—ｐ　ｎｅ—ｗ（）Ｊ　｛　ｃａｌｃｕｌａｔｅ　ｐ（）］　ｌ臣　回　臣五　图３类结构层次图　３实验仿真与分析　实验拓扑结构如图４所示，源端Ｈｉ（．＝ｌ…．，ｎ）产生ｆｌｐ　数据流，经由中问节点ｎｌ（路由器１）和ｎ２（路由器２）到　达终端ＲＥｉ（ｉ＿ｌ…．，ｎ），设两个路由器中间的链路为瓶颈链　路，带宽和延迟分别为１０Ｍｂ／ｓ和３０ｍｓ，设拓扑结构的其它　所有链路带宽为３０Ｍｂ／ｓ，传输延迟为ｌ　５ｍｓ。路由器分别使　用ＲＥＤ和ＨＯ—ＲＥＤ队列管理算法，缓冲区容量为２０个分组　大小。　图４仿真实验拓扑图　ＨＯ—ＲＥＤ算法只需要在仿真实验脚本中通过对控制开关　赋值，ＱｕｅｕｅＲＥＤ　ｓｅｔ　ＨＯ—ＲＥＤ—ＯＮ一＝ｌ，即切换到ＨＯ—ＲＥＤ　算法起作用。　试验ｌ通过对ＣＢＲ、ＦＴＰ业务流分别对ＲＥＤ和ＨＯ－ＲＥＤ　算法进行实验，结果表明ＨＯ—ＲＥＤ提高了ｆｔｐ流源端发送数　据包，使ＣＢＲ数据流源端发送数据包数量不变的情况下增大　３．６３％的丢包率，从而使ｆｌｐ数据流获得更多的网络资源；对　于ＣＢＲ数据流的平均延迟减少了３．２７ｍｓ。对于改进前后ＣＢＲ　Ｒ　ＥＤ—ＦＴ　Ｐ　Ｈｏ—Ｒ　Ｅ　Ｄ—ＦＴ　Ｐ　０　０　０　５　１　０　１　５　２　０　２　５　Ｔｉｍ　ｅｆ　ｓ　圈６改进前后ｒｔｐ数据流的延迟比较　实验２在多个ｆｌｐ数控据流竞争网络资源的情况下，　ＨＯ－ＲＥＤ较ＲＥＤ算法的吞吐量提高了１．５％；网络平均延迟　一∞Ｅ—　ＢＩ∞凸　Ｏ　９　８　７　６　５　４　３　２，Ｏ　降低了约２ｍｓ，吞吐量和分组延迟结果如图７和图８。∞　加　∞　　０　１　２　３　４　５　６　７　８　Ｔｉｍｅ（ｓ）　图７改进前后延迟比较　窗　口　：　２　［　０　１　２　３　４　５　６　７　８　９　１　０　Ｔｉｍ　ｅｆｓ）　图８改进前后吞吐量比较　从以上实验结果可以得出，ＨＯ—ＲＥＤ算法在相同的网络　环境下对于部分网络性能有一定的提高。该改进算法实现简　单。可以很方便地将该算法应用到各种实施主动队列管理的　场景，获得比ＲＥＤ算法更优的网络性能。　４结论　本文分析了网络中间节点的分组丢弃／标记策略基本原　理，阐述了现有算法的不足，提出了一种基于非线性高阶　ＲＥＤ算法。该算法在缓存占用率低的情况下以较低的分组丢　弃率丢弃分组，可以保证较好的网络吞吐量，同时当缓存区　占有率较高时，分组丢弃概率也迅速提高，能够使网络较快　地从拥塞中解除出来，提高了系统的效率。进一步的工作是　（下转第ｌ６４页）　ｌ６１—　维普资讯 http://www.cqvip.com

和响应时间的，其中ＲＤ＝０．０５，Ｔ　。　＝Ｔ　㈨。＝０．１　ｓ，　Ｔ　ｌ＝１ｍｓ，ＶＩＲＤ的ＴＴＬ　＝４，ｆｌｏｏｄｉｎｇ的ＴＴＬ　分　ｍ　长十Ｆ４，Ｆ５和Ｆ６，这足因为它们只在很小的范围内查找，　所以对　｝　成功的请求来说响应时间很短，但足它们的查找成　孔　０　别为４～Ｉ】，ｒａｎｄｏｍ　ｗａｌｋ的ＴＴＬ　分别为１Ｏ０，３００和１　０００　２中，ＶＩＲＤ的ＴＴ［　为４，ｆｌｏｏｄｉｎｇ的ＴＴＬ是３～１Ｉ，ｒａｎｄｏｍ　ｗａｌｋ的ＴＴＬ是１００，３００和１　０００。冈３的条件同　２。从图　功率很低（５６．７９％～８１．０３％），对于一个资源查找系统来说，　这样的成功率是很难接受的。从这组测试可以看出，在相同　２中可以看到ＶＩＲＤ方法在ＴＴＬ　＝４时（简称ＶＩＲＤ　４）的　请求查找成功率（９９．９９％）比Ｆ１　１的查找成功率（９８．９５％）　都要高，Ｆ７的查找成功率仅为８７．０５＇７，。当请求频率增加时，　查找成功率　，ｖＩＲＤ的通信量远小于ｆｌｏｏｄｉｎｇ系统的通信　ＶＩＲＤ的请求响应时问也小于ｆｌｏｏｄｉｎｇ系统的请求响应　，时间　Ｔｒａｆｆｉｃ　并不增加，增加的只是Ｔｒａｆｆｉｃ　。图３和图４都是　以ｆｌｏｏｄｉｎｇ在ＴＴＬ　＝７时（Ｆ７）的值为标准值Ｉ，取得的　３表明ＶＩＲＤ４的Ｔｒａｆｌ’ｉｃ　以及　相对值。之所以以Ｆ７为标准，是　为大多数Ｇｎｕｔｅｌｌａ系统默　认的ＴＴＬ　就是７。　Ｔｒａｆｆｉｃ　和Ｔｒａｆｆｉｃ　分别只是Ｆ７的３．４８％￣ｔｌ　２６．８３％，更是　只有Ｆ１１的０．３０％和２．３Ｉ％。　Ｊ＿　ｖ　ＪＲ［２４　｝０　Ｆ５　６　　Ｉ７　｜８　１’Ｉ【Ｊ　１Ｉ　ＲｗＩ（　ＫＷ３００ＲＷＩ（ＸＸ）　＿ｒ兀　ＭＡＸ　图４　ＶＩＲＤ，ｆｌｏｏｄｉｎｇ和ｒａｎｄｏｍ　ｗａｌｋ的响应时间　４结论　本文提出　一种Ｃ／Ｓ和Ｐ２Ｐ结合的刚格环境中的资源发　现机制…¨【１　Ｆｌｌ　ＲＷ…（）ＲＷ３０（）ＲＷＩ（ＨＨ）　ＶＩＲＤ。它采用属性．值对的请求描述方法，提供　了比恭ｆ　ＩＤ更强的查询能力。ＶＩＲＤ的３层结构能够便于用　户和资源的注册、信用管理。从试验可以看到，即使在资源　ＴＴＬＭＡＸ　图２　ＶＩＲＤ，ｆｌｏｏｄｉｎｇ和ｒａｎｄｏｍ　ｗａｌｋ的成功率　频度比！疫ｌ低的状况下，使用很小的ＴＴＩ　，ＶＩＲＤ仍能获得　比较高ｆｌ勺查找成功率　通过对ＶＩＲＤ与ｆｌｏｏｄｉｎｇ和ｒａｎｄｏｍ　ｗａｌｋ的比较，叮以看出，在相同查找成功率的情况下，ＶＩＲＤ　所需要的刚络上的通信　：和响应时间都远小于ｆｌｏｏｄｉｎｇ和　ｒａｎｄｏｍ　ｗａｌｋ系统。　参考文献　Ｉ　Ｇｏｎｇ　Ｙ，Ｉ）ｏｎｇ　Ｆ　Ｌｉ　ｗ－ｅｔ　ａ１．ＶＥＧＡ　１ｎｆＪａｓｈｕｃｔｕｒｅ　ｆｏｒ　Ｒｅｓｏｕｒｃｅ　Ｄｉｓｃｍ　ｅｌ’Ｙ＿Ｉ１　Ｇｒｉｄｓ［Ｊ　１　Ｉｏｕｌ　ｎａｌ　ｏｌ、Ｃｏｍｐｔｌｔｅｒ　Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ．　２００３，Ｉ８（４）：４Ｉ　３－４２２　２　Ｃｚａｊｋｏｗｓｋｉ　Ｋ．Ｆｉｔｚｇｅｒａｌｄ　Ｓ．Ｆｏｓｔｅｒ　１，ｃ【ａ１．Ｇｒｉｄ　ｉｎｆｏｒｍａｔｉｏｎ　Ｓｅｒｖｉｃｅｓ　Ｆ８　１：９　ＦＩ【】ＦＩ　１　ＲＷｌ｛）０　ＲＷ　３００　ＲＷ¨）０１）　ｌｂｒ　Ｄｉ￣ｔｒｉｂｕｔｅｄ　Ｒｅｓｏｕｒｃｅ　Ｓｈａｒｉｎｇ［ＣＩ．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１０　ＩＥＥＥ　ｌｎｔｅｒｎｔ，ｔｉｏｎａｌ　Ｓｙｍｐｏｓｉｕｍ　Ｏｉｌ　Ｈｉｇｈ—・ｐｅｒｆｏｒｍａｎｃｅ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｃｏｍｐｕ・－　ｔｉｎｇ（｝！ＰＤＣ—Ｉ（））．Ｓａｎ　Ｆｒａｎｃｉ：￣ｃｏ，ＣＡ．２００１—０８：Ｉ　８Ｉ一１９４．　ＴＴＬＭＡＸ　图３　ＶＩＲＩ），ｆｌｏｏｄｉｎｇ和ｒａｎｄｏｍ　ｗａｌｋ的网络开销　图４的条件刚罔２。从图４叮以看出，ＶＩＲＤ４的响应时　、日］是Ｆ７的９７．４８％，比ＦＩ１快１５．２５％。ＶＩＲＤ　４的响　时间　３　Ｌｕ　Ｄ　１）ｉｎｄａ　Ｐ　Ｓｙｎｔｈｅｓｉｚｉｎｇ　Ｒｅａｌｉｓｔｉｃ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｇｒｉｄｓ［Ｃ］．　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　Ｓｕｐｅｒｃｎｍｐｕｌｉｎｇ，Ｐｈｏｅｎｉｘ，ＡＺ，２００３一ｌ　１：１６　（上接第１６１页）　结合中间节点和终端节点ｊ）｛Ｉ塞控制技术研究网络突发流量对　ｌ　３２０－ｌ　３２　于网络的影响和有效克服网络突发流　的策略与技术。　４　Ｏｔｔ　Ｔ　Ｊ　Ｌａｋｓｈｍａｎ　Ｔ　Ｖ．Ｗｏｎｇ　Ｉ　Ｈ．ＳＲＥＤ：Ｓｔａｂｉｌｉｚｅｄ　ＲＥＤ［Ｃ］．Ｐｒｏｃ　ｏｌ’ＩＥＥＥ　ｌｎｆｏｃｏｍ．Ｎｅｗ　Ｙｏｒｋ．１ＥＥＥ　Ｃｏｎｌｎｌｕｎｉｃａｔｉｏｎｓ　Ｓｏｃｉｅｔｙ，１９９９　ｌ　３４６一ｌ　３５５　参考文献　Ｉ　Ｂｒａｄｅｎ　Ｂ．Ｒｅｃｏｍｍｅｎｄａｔｉ（ｍｓ　ｏｎ　Ｑｕｅｕｅ　Ｍａｎａｇｅｍｅｎｔ　ａｎｄ　Ｃｏｎｇｅｓｔｉｏｎ　Ａｖｏｉｄａｎｃｅ　ｉｎ　ｔｈｅ　ｉｎｔｅｒｎｅｔ［Ｓｌ　ＲＦＣ２３（）９．１９９８—０４　２　Ｆｌｏｙｄ　Ｓ，Ｊａｃｏｂｓｏｎ　Ｖ．Ｒａｎｄｏｍ　Ｅａｒｌｙ　Ｄｅｔｅｃｔｉｏｎ　Ｇａｔｅｗａｙｓ　ｆｏｒ　５　Ｃｉｓｃｏ　Ｃｏｒｐ　Ｗｅｉｇｈｔｅｄ　Ｒａｎｄｏｍ　Ｅａｒｌｙ＇Ｄｅｃｔｅｃｔｉｏｎ（ＷＲＥＤ）［Ｚ】　ｈｔｔｐ：／／ｗｗｗ　ｃｉｓｃｏ　ｃｏｍ／ｕｎｉｖｅ￣ｃｄ／ｃｃ／ｔｄ／ｄｏｃ／ｐｒｏｄｕｃｔ／ｓｏｆｔｗａｒｅ／ｉｏｓｌ２０／ｌ２　ｃｇｃｒ／ｑｏｓｃ／ｑｃｐａｒｔ３／ｑＣＷｌ。ｅｄ．ｐｄｆ．　Ｃｏｎｇｅｓｔｉｏｎ　ＡｖｏｉｄａｎｃｅｌＪＩ．ＩＥＥＥ／ＡＣＭ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　ｒ，＇ｅｔｗｏｒｋｉｎｇ，　１９９３，ｌ（４）：３９７－４ｌ３．　３　Ｆｅｎｇ　Ｗ　Ｃ，Ｋａｎｄｌｕｒ　Ｄ，Ｓａｈａ　Ｄ，ｅｔ　ａ１．Ａ　Ｓｅｌｆ－ｃｏｌ１　ｒｉｇｕｒｉｎｇ　Ｒｅｄ　６　ＮＳ　Ｐｒｏｊｅｃｔ１　ＥＢ／ＯＬ］ｈｔｔｐ：／／ｗｗｗ．ｉｓｉ．ｅｄｕ／ｎｓｎａｍ．　７李方敏，李仁发，叶澄清．网络仿真软件ｎｓ的结果输出和分析…　计算　工程，２０００，２６（９）：１４—１６．　Ｇａｔｅｗａｙ［Ｃ　ｌ　Ｐｒｏｃ．ｏｆ　１ＥＥＥ　ｌｎｆｏｃｏｍ，Ｎｅｗ　Ｙｏｒｋ，ＵＳＡ，ｌ　９９９：　１６４一