计算机网络管理论文计算机网络维护论文计算机网络技术论文：可靠多播网络中的自适应主动缓存管理协议

《计算机网络管理论文计算机网络维护论文计算机网络技术论文：可靠多播网络中的自适应主动缓存管理协议》由会员分享，可在线阅读，更多相关《计算机网络管理论文计算机网络维护论文计算机网络技术论文：可靠多播网络中的自适应主动缓存管理协议（15页珍藏版）》请在装配图网上搜索。

1、计算机网络管理论文计算机网络维护论文计算机网络技术论文可靠多播网络中的自适应主动缓存管理协议摘要:缓存管理是影响可靠多播协议性能的重要因素。在可靠多播领域，现有大多数缓存管理机制的设计目标限于单多播组的网络环境。在缓存资源被多个多播组所共享的Internet环境中采用单组缓存管理方案无法获得预期目标。为了解决该问题，基于主动式网络中路由器能够执行预设计算并缓存数据的特点，提出并实现了一种全新的多播网络缓存管理协议(Adaptive and Active Cache Pool，简称AACP)。AACP提出全局动态分配，Borrow-In和Return3种核心策略，首次提出采用全局加权移动平均计算

2、缓存配额，并设计出分级TTL缓存替换算法。NS2模拟实验的结果数据表明，AACP能为多播网络在恢复延迟，带宽消耗和网络吞吐等方面带来显著的性能提升。这同时也意味着AACP将为对数据完整性和实时性要求极高的多播应用，如金融电子化实时系统和电子白板等，提供高质量的基础支撑。关键词:可靠多播;AACP;主动网络;缓存管理;缓存分配在Internet中实现可靠多播面临系列困难，包括NACK爆炸(NACKimplosion)，分布式丢失恢复(distributed loss recovery)以及受限重传(retrans-mission scoping)等等。Lehman等提出的主动式可靠多播协议 (A

3、ctive Reliable Multicast，简称ARM)，利用网络核心部分的主动路由器(ActiveRouter，简称AR)缓存数据，抑制重复NACK包，并实现本地重传。最近，研究人员提出多种在单多播组环境中有效分配AR的缓存资源的方案和协议。在Internet中，AR通常同时服务于多个多播组，由于流经同一AR的各个多播组流量可能分别穿越异构的下游链路，导致各组的丢包率不同，因而各组对AR缓存资源的需求程度也存在差别。若在这样的网络场景中采用为单多播组环境设计的缓存分配算法将导致分配结果不公平和缓存利用率低下等问题。AACP协议通过设计动态分配算法和分配策略，有效并且公平地为每个多播组计

4、算缓存配额，最大化资源利用率。实验结果表明，AACP从全局共享而非局部独享为基点进行的设计为多播网络带来了整体性能的提升。1问题定义ARM协议采用带TTL的FIFO策略进行内存管理。首先通过一个简单模型(图1)阐述现有缓存管理方案的缺陷。模型中存在2个可靠多播组X和Y。节点0是两个多播组的发送者。节点2，3和4为接收者。节点2和节点3加入多播组X，节点3和节点4加入多播组Y。节点1是主动路由器。链路a，b和c是可靠链路，链路d是不可靠链路。假设数据包在可靠链路的传输过程中不会丢失，因此路由器1不会收到X组的NACK包，但可能收到来自Y组接收者4的NACK包。如果路由器1的缓存容量无限大可以缓存

5、所有流经的数据包，当收到NACK后，路由器便总能在其缓存中找到对应的数据包并作为修复包转发。然而，在真实网络环境中的路由器缓存资源有限。假设路由器1的缓存资源已耗尽，但是多播组X和Y的数据包仍然持续到达。在此场景中，ARM采用的两种缓冲管理方案如下:首先讨论部署Simple FIFO作为缓冲管理方案可能导致的问题。如果组X和组Y的传输速度基本相同，路由器缓存空间将被两组平分。当X组传输速率远高于Y组时，大部分缓存空间将被X组数据包占据。在实验模型中，Y组数据包应该尽可能被路由器缓存以应付可能出现的重传。然而由于Y组传输率较低导致其仅获得很少的缓存空间。当丢失发生后，路由器在缓存中难以找到对应的

6、数据包，因此不得不向上游的发送者继续转发NACK，这将增加修复延迟时间。由此可见，在多个多播组具有不同丢包率和传输率的场景中，Simple FIFO策略可能导致糟糕的丢失恢复性能。针对Simple FIFO的不足，一种可能的改进是采用Per-flow FIFO方案。路由器缓存空间被平均分配给组X和组Y。与Simple FIFO相比，Per-flowFIFO在隔离“侵略性”的数据源方面更具优势。然而，上述场景中的路由器1不会收到组X的NACK。因此，为组X分配的空间的使用率永远为0。这意味着路由器1中50%的缓存空间被浪费。Per-flowFIFO协议在缓存物理配额上平均分配的结果与实际需求脱节

7、，分配结果的有效性和公平性都无法得到保证。从以上对Simple FIFO和Per-flow FIFO的讨论可知，多播网络的恢复延迟与各多播组的不同特性相关，特别是传输速率，丢包概率以及下游接收者数量等因素都需要在设计缓冲管理方案和调度规则时被综合考虑。2自适应主动缓存管理AACPAACP由缓存动态预分策略(缓存分配算法)、动态调整策略(Borrow-In策略和Return策略)以及丢包策略三部分组成。AACP采用缓存动态预分策略为多个共享资源的多播组动态事先预分配缓存配额。当某个多播组的数据包DP到达路由器时，AACP首先尝试将DP放入该组的缓存空间;若该组已无剩余配额可用，AACP采用动态调

8、整策略进行调整，先尝试从其他尚有空闲空间的组BorrowIn缓存资源，若没有可借用的缓存，则采用Return策略;若没有可还回的缓存，表明路由器中所有组的缓存资源皆已耗尽，AACP启动丢包策略，若AACP丢包策略还不能得到缓存，则直接向各下游链路转发新到的数据包。2.1核心策略适应性策略1:动态缓存分配策略AACP在保证公平的基础上，将主动路由器缓存资源尽量分配给“最”需要的多播组，即那些最可能要求本地重传的组。某个多播组的NACK数量180四川大学学报(工程科学版)第42卷在一定程度上反映了该组的丢包概率。NACK数目越多，丢包概率越大，对重传的需求也更大。AACP记录每个多播组在单位时间内

9、到达AR的NACK数量及NACK数量的波动幅度，根据AACP缓存分配算法动态估算各组的缓存配额，并采用AACP校正算法(确保分配结果的公平性。本策略保证在公平的原则下，尽量将缓存分配给有重传需求的组，这种方式提高了资源动态利用率，并将资源浪费最小化。适应性策略2:Borrow-In策略Borrow-In策略一旦有空闲的缓存空间，AACP将尽最大努力缓存数据包。从动态缓存分配策略可知，每个流经AR的多播组都可能拥有部分缓存配额，AACP将AR缓存设计成能根据网络丢包状况进行动态调整的共享缓存池。AACP为多个并发的多播组统一分配缓存配额，配额大小与多播组总数和各组数据传输的可靠程度等因素相关。在

10、下述两个条件具备时，AACP允许某个多播组使用Borrow-In策略获取缓存池中的空闲资源。1)该组自身的配额空间已全部用完;2)其他组尚有未用的缓存空间。Borrow-In策略意味着一个多播组能够临时占用超出自身配额数量的缓存资源。本策略保证了路由器能最大化缓存的利用率。适应性策略3:Return策略Return策略借用者被动归还借入的缓存空间。如前述，Borrow-In行为是临时性的。与其相反的Return行为保证每个组总是能在需要的时候使用自己最大的配额来缓存数据，即使自己的缓存空间已被其他组临时占用。Return策略是一种被动归还策略。借用者一旦成功借入缓存空间，那么将尽可能久地占据这

11、些空间。最终，将由AACP负责回收借出的空间。当缓存资源皆耗尽时，AACP激活Return策略，要求借用者向出借者归还空间。如果有多个组都已使用Borrow-In策略，重传需求最小的组将首先被要求归还借用的空间。这种归还优先级return-priority-order意味着AACP将尽量缓存重传可能性最大的那部分数据包。2.2缓存分配算法AACP采用指数加权移动平均(exponentialweighted moving average，简称EWMA)算法估算多播组平均丢包情况。EWMA中的加权因子呈指数级下降，其值反映了多播组在单位时间内的平均丢包数量，同时能够消除由突发流量引起的NACK数目

12、跳变。若仅采用丢包数量作为缓存分配标尺，数量越大配额越大，那么分配算法将明显有利于高丢包率的多播组。在各组丢包量接近，或者仅有少数不可靠组的场景中，这种分配算法能够最大化缓存利用率。然而，当网络中一旦存在某些高丢包率的组时，该算法的计算可能出现不公平的分配结果。因此，AACP分配算法由两个阶段构成:第1阶段，估算阶段，通过计算NACK数量的加权移动均值估算多播组缓存配额。设多播组i在第m个计时周期内的NACK总数为NACKi，m，计算多播组i在第m个计时周期结束时的NACK指数加权移动平均值EWMAi，m的公式如下:EWMAi，m=(1)EWMAi，m1+NACKi，m，1。可推出:EWMAi

13、，m=m1j=1(1)jNACKi，mj。设NACKtotal，m是所有多播组在计时周期m结束时的NACK指数加权移动平均值的总数。假设总的缓存资源为C，计时周期m结束时分配给多播组i的缓存配额用Ci，m表示，NACKtotal，m=EWMA1，m+EWMA2，m+.+EWMAn，m，Ci，m=?EWMAi，mNACKtotal，mC=?EWMAi，mnj=1EWMAj，mC。其中，函数?x表示小于或者等于x的最大整数。第2阶段，校正阶段，检查每组获得的配额是否能够满足其重传要求，对所有配额不能满足重传要求的组，采用校正算法修改其缓存配额。设PACKETi表示多播组i在估算周期内到达AR的数据

14、包数量验证第1阶段的配额估算结果1)若Ci，mPACKETi，该组缓存配额不做调整;2)若Ci，mPACKETi，并且Ci，m?1nC，n为共享AR的多播组总数，该组缓存配额不做调整。3)若Ci，mPACKETi，并且Ci，m?1nC，n表示共享AR的多播组总数。根据Return策略，该组缓存配额调整为:Ci，m第1期张靖宇，等:AACP:可靠多播网络中的自适应主动缓存管理协议181=?1nC，n表示共享AR的多播组总数。第1阶段的估算结果真实地反应了各多播组的丢包情况。依照此结果为多播组进行缓存分配可以克服由于NACK瞬间跳变所引发的缓存“非理性”重分配。在校正阶段，如果发现某个多播组的配额

15、无法满足其重传要求，即配额数量少于单位时间内到达的数据包数量，并且配额数量少于按多播组数量进行平均分配的配额(C/n)，AACP的分配算法将调整该组配额至平均数C/n，同时调低超出平均水平最多的组的配额。在第1节曾讨论过，按组均分的方式可能导致缓存资源的浪费，数量上的均等不代表实际分配结果的公平。这一结论与校正阶段进行的配额均值调整并不矛盾。当多播组缓存配额不能满足其重传需求时，表明总资源不足，此时按组均分的方式将不会产生资源浪费。相反，在此情况下调高该组配额至均值正是分配算法公平性的体现。如果由于多播组内成员结构发生变化而引发丢包率改变，或者由于新组加入或旧组退出而导致共享AR资源的组总数发

16、生改变，AACP的Borrow-In策略和缓存分配算法将协同修正多播组的缓存配额。2.3 AACP丢包策略当AR缓存资源耗尽时，AACP缓冲管理协议中的丢包策略决定如何处理新到达的数据包。不恰当的丢包策略可能导致全局同步(global synchroniza-tion)和公平性(fairness)问题。AACP丢包策略与ARM中的缓存管理机制存在明显区别。ARM中，一旦TTL终止，无论是否存在空闲空间，超时的缓存包都将被删除。而AACP协议尽可能长时间的保留缓存包，只要AR存在空闲存储资源，无论是否TTL终止，皆不启动丢包机制。AACP丢包机制包含3个过程，“完全过期”替换过程，“过期”替换过

17、程和直接转发过程。当丢包机制启动后，AACP首先在所有多播组的缓存区域中查找“完全过期”的缓存包。当缓存包i的缓存时间TCACHE，iTTLi并且TCACHE，i(2RTT)，这个包被AACP协议称为“完全过期”的缓存包。AACP认为，若一个缓存包TTL终止，并且其缓存时间已经超过2RTT，那么它在未来还会用于本地重传的可能性可以忽略不计。如果AACP发现存在完全过期的缓存包，则将其删除，并将新到达的数据包存入该删除包的空间。如果AACP未能在全局缓存区域中找到“完全过期”的缓存包，将启动Return策略回收外借的缓冲空间。若Return过程结束后也未找到新的空间，AACP将转而在新到数据包所

18、属的多播组缓存区域中查找“过期”的缓存包。当缓存包i的缓存时间TCACHE，iTTLi并且TCACHE，i(2RTT)，AACP协议称之为“过期”的缓存包。AACP在新到包所属的多播组空间中找到“过期”缓存包后，将其删除，并将新到达的数据包存入该删除包的空间。在查找“完全过期”与“过期”两类缓存包时，AACP查找的缓存空间并不相同。前者是在整个路由器的全局缓存空间中进行，而后者仅限于新到包所属的多播组的缓存空间中进行。这是因为AACP不仅考虑最大化缓存空间的利用率，同时也兼顾到不同组之间缓存分配的公平性。DP的TTL终止表明从统计学角度分析，NACK到达概率已小于平均水平，但并非完全排除其可能

19、性。只有当缓存时间大于2RTT后，才能基本排除NACK到达的可能性。AACP在启动丢包机制后，对同一个多播组的缓存空间采用Drop-from-Front的丢包策略。最后，当AR缓存资源全部耗尽，并且两类过期包都不存在时，AACP认为目前缓存中所有数据包都很重要，不能丢弃。于是AR直接向各下游链路转发新到的数据包，而不对其做任何缓存操作。3 AACP性能评估目前有多种衡量标准被用于可靠多播网络的性能评估。例如本文采用的评估标准:Total HopsNACKs Traverse to Recover a Single Loss和numberof repair packets from sender

20、 to repair a packet loss。第1个评估指标反应了用于丢失恢复的相关带宽消耗量:NACK跳数越大意味着重传路径更长。第2个评估指标用于评估与发送者直接相连的HeadLink的负载情况。实验采用与4ARM分析模型中相同的网络模拟平台LBNL NS2。，每一个叶子节点皆为多播组的成员。节点0是两个多播组的CBR(Constant Bit Rate)数据源。在模拟环境中，CBR源的发送速率为4096 kbps。数据包大小固定为256 B。节点1和节点2是主动路由器。节点3和节点4作为接收者加入多播组1。节点5和节点6作为接收者加入多播组2。每条链路延迟皆为10ms，带宽100 M

21、bps。路由器是主动或是非主动节点在实验中随机决定。每台路由器的缓存大小在各实验中随机选择为100/200/400包空间。在实验中假设AACP统计信息不消耗AR的缓存资源。在实验网络拓扑中，每一个叶子节点(一共50个叶子节点)皆是一个多播组的接收者。每一个接收者随机选择加入一个多播组。随机选择部分链路作为不可靠链路，并赋予它们5%的随机丢包概率。假设在模拟环境中的丢包皆源于不可靠链路的随机丢包，而非网络拥塞。并假设只有数据包DP和修复包RP可能出现丢失。每个多播组的大小(接收者数量)为k。k从10逐一增加到50。对每一个k规模的多播，实验重复执行100次后取实验结果的平均值作为最终结果。每次实

22、验包含2次模拟过程，一次是AACP，另一次是ARM+FIFO。AACP协议由AR(active router)负责丢失重传，任意多播子树的“根”路由器皆可成为AR，AR的选择策略与网络成员信息无关。AACP的这一特性使其更易于在Internet中实现。如果将多播网络核心部分所有路由器皆部署成AR，可能增加网络部署的成本。实施成本过高也将减少协议的实际操作价值。对于层次较深的多播子树，如果只在其最上层根节点部署AR，将导致与DM部署类似的修复延迟问题。可见，AR位置的选择是影响AACP多播网络性能的重要因素。多播网络管理员需要仔细规划，有选择性地在某些合适位置部署AR。本节将讨论两种不同的AR部

23、署方案对网络性能产生的影响，并通过模拟实验比较AACP和ARM在不同AR部署场景中的表现。3.1全局部署AR模拟实验中，缓存命中率与发送者送出的修复包数量是两个相关的评估标准。反映了这种相关性。完成K个数据包的多播传输(X轴)需要发送者送出的修复包数量(Y轴)。从图中可以看到，在多播网络中部署AACP后，只需发送者发送更少的修复包即可完成指定数量的数据传输。这是由于大部分的包丢失重传工作都被网络中的主动路由器完成。AACP的重传命中率也明显高于ARM+Perflow FIFO。因此AACP减少了到达瓶颈链路的(连接发送者的链路)回馈包数量和重传流量，并降低整个多播网络的带宽消耗。3.2关键位置

24、部署AR根据AACP协议的特性，当网络中的一台路由器同时为多个可靠或者不可靠的多播组服务，并且当不可靠组的数量小于可靠组数量时，AACP称这台路由器处于关键位置。相比3.1中的全局部署方案，仅在多播网络的关键位置部署主动节点和AACP，一方面将获得相似的网络性能提升，另一方面却能够大幅降低部署成本。在模拟实验中，多播树中少于50%的节点作为关键位置。实验结果表明，在关键位置部署AACP将获得与在所有位置上部署AACP相似的性能。等:AACP:可靠多播网络中的自适应主动缓存管理协议结论提出并实现了一种新型可用于大规模可靠多播网络的缓存管理机制AACP。AACP的贡献包括:首次提出3种自适应分配策

25、略及分配算法，自适应策略能够最大化共享缓存使用率，同时也能兼顾分配结果的公平性;提出基于分级TTL的包替换策略，从全局视角分析各多播组中缓存数据包的有效级别并执行相应的替换操作，解决了由于传统可靠多播协议仅从局部视角分析单组数据替换而造成的资源利用率低下以及分配不公的问题。实验结果表明，在大多数场景下，AACP在减少恢复延迟，降低带宽消耗以及增加网络吞吐方面，表现出明显优于ARM的性能。在多播网络中的关键位置部署AACP路由器将不仅获得与在所有位置部署AACP路由器相似的性能，这种方式还能够显著降低网络的部署成本。关键位置指下游可靠链路数量多于不可靠链路数量的路由器，诸如拥有大量无线下游链路的

26、路由器节点。然而，如何跟随网络拓扑的改变动态判断出关键位置的研究仍在进行中。参考文献:1Constantinescu P A，Erman D，Ilie D，et al.A survey of relia-ble multicast communicationC/Next Generation InternetNetworks.3rdEuroNGI Conference，2007:111118.2Xie Feng，Feng Gang，Yang X.Optimizing caching policy forloss recovery in reliable multicastC/IEEE Proc

27、eedings ofIEEE INFOCOM 2006.2006:112.3Lehman L H，Garland S J，Tennenhouse D L.Active reliablemulticastC/IEEE Proceedings of IEEE INFOCOM98.1998，2(1):581589.4Keidar M R，Araneola I:A scalable reliable multicast systemfor dynamic environmentsJ.Journal of Parallel and Dis-tributed Computing，2008，68(12):1

28、5391560.5Ryan G Lane，Scott D，Xin Yuan.An empirical study of re-liable multicast protocols over Ethernet-connected networksJ.Performance Evaluation，2007，64(3):210228.6Levine B N，Garcia-Luna-Aceves J J.A comparison of relia-ble multicast protocolsJ.Multimedia Systems，1998，6(5):334348.7Yavatkar R，Griff

29、ioen J，Sudan M.A reliable disseminationprotocol for interactive collaborative applicationsC/Pro-ceedings of the Third ACM International Conference on Mul-timedia.1995:333344.8Feng Gang，Zhang Jinyu，Xie Feng，et al.Buffer managementfor local loss recovery of reliable multicastC/IEEE Pro-ceedings of IEE

30、E GLOBECOM04.2004，2:11521156.9Feng Gang，Siew C K，Yeung K L.Active resource allocationfor active reliable multicastC/IEEE Proceedings onCommunications.2003，150(2):6979.10Kiwior D，Zabele S.Active resource allocation in active net-worksC/IEEE INFOCOM98.1998，2:581589.11Ji Ping，Kurose J F，Towsley D F.Act

31、ivating and deactiva-ting repair servers in active multicast treesC/Proceed-ings of the Thyrrhenian International Workshop on DigitalCommunications.2001:507523.12Brandauer C，Iannaccone G，Diot C，et al.Comparison of taildrop and active queue management performance for bulk-dataand web-like internet tr

32、afficC/Proceedings of the SixthIEEE Symposium on Computers and Communications.Washing-ton，DC，USA:IEEE Computer Society，2001:122.13Iannaccone G，May M，Diot C.Aggregate traffic perform-ance with active queue management and drop from tailJ.ACM SIGCOMM Computer Communication Review，2001，31(3):413.14Byun S S，Yoo C.Placement of repair proxies to improve in-ter-receiver delivery delay fairness in hierarchical reliablemulticast networksC/AICT-SAPIR-ELETE05.2005: