自适应聚类片选内容分发模型*

董丁维 ，王 晶 ，沈奇威

（1.北京邮电大学网络与交换技术国家重点实验室 北京100876；2.东信北邮信息技术有限公司 北京100191）

1 引言

随着多媒体技术的发展和普及，网络上信息的形式及应用的类型日益丰富，人们对于Internet内容的需求也在飞速增长。传统的窄带网络及单一的Web页面内容已经不能满足人们的需要，网络上用户访问速度慢、体验差正逐渐成为制约信息技术发展的障碍。很多人认为网络技术的不完善是Web性能差的主要原因，增加网络带宽、采用高速的路由器等方法就能加速Web访问，但实际上带宽不足并不是惟一原因。随着宽带网络的普及，网络的访问速度在一定程度上得到了缓解，同时海量并发用户密集访问型的应用（如网络电视点播业务）迅速发展，仍然会引起网络拥塞，因此单纯依赖网络带宽并不能完全解决稳定性和服务质量的问题，需要引入一种高效的内容服务网络——内容分发网络（content delivery network，CDN）[1]。

CDN的原理是通过在现有的Internet中加入一层新的网络架构，将要分发的内容发布到最接近用户的网络边缘节点 （edge point，EP），使用户能就近获得所需内容，CDN一般分为两级结构：由中心服务器节点（center point，CP）和EP构成的第一级网络结构，内容发布的流程在这一级上进行；第二级网络是由EP和终端用户之间构成的P2P分发网络，主要用于内容向最终用户下发[2]。

内容分发模型是指在CDN的第一级网络中，通过构建合理的拓扑结构，采用有效的传输方式，同时结合聚类算法，让EP更加合理地选择邻居节点，采用片选策略，使EP快速地从邻居节点处下载适当的内容，完成内容在CP和EP之间的快速分发。不同的CDN根据其业务需求不同，往往采用不同的内容分发模型。

实践证明，CDN的出现很大程度上改善了Internet的网络拥塞状况，提高了用户访问内容的响应速度和质量，特别是多媒体服务的质量。在以往的工程应用中，业务和内容的差异十分明显，有的业务要求块式内容最短时间到达，因此CDN的分发模型侧重于聚类算法的有效性；有的业务注重流式内容的有序传输，因此要求分发模型的片选机制更加完善。随着网络技术的发展，兼有块式和流式内容海量访问的业务会日渐增多，这就对内容分发模型提出了新的要求。本文针对这一趋势，设计了一种兼顾块式和流式内容分发的模型。

2 研究背景

2.1 应用层组播

内容分发模型利用组播技术将内容从CP向多个EP快速高效地分发下去。组播技术是指单个信息发送者对应多个接收者的一种网络通信，现在常见的两种技术是IP组播和应用层组播。IP组播的主要思想是在Internet单播的框架上进行扩展，功能主要通过路由器实现，网络资源利用率较高，但存在很多问题，主要表现在：路由器需要为所有组播保存状态，扩展性较差；对路由器的依赖过高，并不是所有路由器都支持IP组播，可行性差；IP组播中的算法设计复杂，维护开销大[3]。应用层组播技术，保持了互联网原有的简单、不可靠、单播的转发模型，由端系统实现组播转发功能，同时克服了IP组播需要对路由器改造的不足，可以有效节省带宽，提高分发效率[4]。

本文设计的内容分发模型采用应用层组播技术。

2.2 传统分发模型

（1）小规模多源组播分发模型

代表是 End System Multicast和ALMI[5]，针对小规模、多数据源的情况，典型应用是视频会议系统。

End System Multicast首先将组播组的成员组织成一个“网”（mesh），每个成员都维护所有组成员的列表，提高了组播组的可靠性；在mesh上以每个数据源为根各构造一个生成树（spanning tree），这样可针对每个数据源进行性能优化。其缺点是系统开销比较大，降低了系统的可扩展性，适合小规模组播组的情况。ALMI在组播成员之间维护一个“最小生成树”（minimum spanning tree，MST），减小了维护开销，但从每个源出发传输开销无法单独优化。生成树的维护开销限制了组播组的规模[6]。

（2）基于特定逻辑结构的分发模型

代表是 Bayeux[7]和CAN(content-addressable network)[8]，使用特殊的逻辑结构对组播节点映射或编址，组播转发可使用简单的规则实现，从而减少状态维护开销和转发开销，避免路由协议的使用。

Bayeux基于Tapestry[9]，每个节点拥有全局惟一的ID，并维护一个邻居表，这些邻居节点的ID和本节点的ID在一定数量的位上相同。转发中第n跳节点ID和目的节点ID至少有n位相同。Bayeux在Tapestry的基础上将组播树的状态信息保存在“中间节点”上，其主要问题是会限制算法的可扩展性。CAN组播是对CAN的扩展。CAN将一个d维坐标空间划分成若干部分，每个节点拥有其中某部分。两个直接相邻部分的坐标在d-1维上相同，而在另一维上不同。转发报文时把报文发给邻居中和目标坐标最接近的节点。CAN组播将组播组构造为CAN，使用“洪泛”方法在CAN内转发报文，这样可减少节点上维护的状态信息，提高数据传输的可靠性，但也会产生大量重复报文。存在的问题是，逻辑空间中节点间的关系并不能对应实际网络中的关系，得到的报文转发路径很有可能在性能方面存在问题。

（3）BitTorrent分发模型

BitTorrent可以被认为是一种P2P的应用层组播技术，采用网状拓扑，以最小化平均内容分发时间为目标，同时采用激励机制遏制节点自私行为，以保障内容分发的效率[10]。BitTorrent一般被块式内容分发系统所采用。

3 自适应聚类片选模型

传统的分发模型由于采用固定的算法和结构，对特定类型（块式或流式）的分发有较好的效果，但由于算法上的缺陷，很难同时支持块式或者流式内容的分发。本文设计的自适应聚类片选分发模型，可以通过算法参数的动态调整，针对不同应用、不同类型的分发内容，提供分发功能，并达到良好的效果。

3.1 HTS

Hash表的键是一个存储对象的标识，值则为存储对象的属性信息。在本模型的CP中提供的HTS（Hash table service，Hash表的维护服务），用来保存和同步EP的状态信息，使CP与EP之间的元数据保持一致并动态更新。HTS的接口设计见表1。

3.2 CP与EP片式内容传送

为了保证内容的传送效率，降低丢失后的重传损耗，内容分发时一般把内容分成许多大小相同的分片，以内容片作为传送单位。当一个EP接收一个完整内容片之后，立即向用户客户端提供内容下载，也可以在邻居EP内进行内容片互传，充分利用有限带宽；当传送过程中出现某个内容片损坏或者丢失时，只需重传单个内容片而无需重传所有内容，节省了传送资源，提高了效率。

表1 HTS接口

内容分片的大小会影响到整个传送过程的效率，所以分片的大小是一个很重要的参数，有研究表明，分片大小为256 KB或者512 KB时，效率最高，BitTorrent也是采用了256 KB或者512 KB（版本不同参数不同）的分片大小。本设计采用256 KB的内容分片，既不会因为分片太小造成EP之间内容片互传时I/O开支过大，也避免了分片过大造成分片重传时的耗时低效[11]。

3.3 网状拓扑结构

网状拓扑结构有效避免了单树和多树结构的不足，也是分发系统中最常见的结构，既能支持块式内容（如光盘镜像）的分发，又能支持流式内容（如流媒体）的分发，可以针对不同的应用需求，提供不同的内容支持，并易于扩展和优化。由于每个节点在网状拓扑结构中都有很多邻居节点，可靠性较好，可规避节点失效的风险，保证连通性。网状拓扑结构既支持Pull方式也支持Push方式的内容分发，但需要每个节点维护其邻居节点的信息，有一定的系统开销。

由于本分发模型重点在于聚类算法和动态调整片选策略，网状结构能灵活地适应变化的网络情况和应用需求，因此采用网状拓扑结构。

3.4 聚类算法

内容分发模型中的聚类算法体现在如何为一个EP选择一组其他的EP组成一个邻居网，目的是生成一个覆盖网络的拓扑结构。邻居网的形成直接影响到分发的性能和网络结构的健壮性。

结合CP中的HTS功能，每个EP都被指定惟一的ID，某个时段内EP会有一个描述信息，称为EP元数据，元数据中包含EP的IP地址和接收发送内容的端口号以及EP所在自治域（电信、网通）的名称，如某台EP的ID为“EP1号”，元数据为“IP:210.1.70.231；Port:8088;AS:EB”。每个 EP都会调用CP的HTS，将自己的ID和元数据信息在CP注册，在聚类时再次调用HTS查询其他EP元数据，寻找自己的邻居节点。在开始发布流程时，CP会连接所有参与发布的EP，把其他EP的元数据信息通知EP，EP就获得了其他参加发布的EP的地址和信息。

动态聚类算法的数学描述为：对某一个EP x而言，设参与发布的EP的总数为N，x的最大邻居节点数为C，参与发布的其他EP中与x在同一个自治域的个数为M，如果用K表示邻居节点中同一个自治域内EP的个数，则K应该满足：

其中，a是一个系数，0.5

本文中采用的聚类算法，采用优先策略聚类和随机邻居选择算法结合的方式，首先选择和自己在同一个域的适量EP作为邻居，同时与其他域的少量EP相连，这样EP可以了解到其他域中内容分片的存储情况，避免了同一个域中所有EP都缺少某些分片而从CP重传的情况，减少了网间流量，提高了分发效率。

3.5 片选策略

确定好邻居节点后，EP需要从邻居节点或CP上下载内容分片，片选策略指的是EP采用何种策略从邻居节点或CP处取得内容分片，往往与分发的内容类型有关，块式内容和流式内容通常采用不同的分发策略。

最常用的片选策略是最少片优先策略，即EP优先选择邻居节点中存在副本数量最少并且自身还没有获得的内容片下载，使内容片均匀扩散到各个节点，避免最后一片出现问题时整个邻居网内无法互传的现象，缓解了CP和主干网络的压力，优化平均分发时间，但只适用于块式内容。流式内容最重要的是按内容流的顺序获取分片，最少片优先并没有考虑到内容分片的顺序，因此无法满足流式内容的分发要求。

本文采用的片选策略先将内容片设定优先级，根据优先级的高低将内容片划分为紧急和非紧急两个集合分别存取，将顺序靠前和备份最少的内容片放入紧急集合，将其他分片放入非紧急集合，这样既可以保证流式内容的按序分发，同时兼顾了块式内容的备份最少片优先传输的要求。分发过程中内容片优先级是动态变化的，两个集合的内容分片会不断调整，适应实际的请求状况和网络情况。

假设内容分片的编号代表内容片在文件中的偏移量，由小到大排列。EP中内容片分为两个集合存储，一个为紧急集合，存储当前紧急需要按序分发的流式内容，必须优先下载，否则内容流会中断；另一个为非紧急集合，没有时间紧迫性内容片。紧急集合中的内容片可以用数对（S，L）表示，S代表最小的内容片序号，L表示集合的大小，即内容片的数量，因此紧急集合中的内容片可表示为{S，S+1，S+2，…，S+L-1}。对于一个EP来说，紧急集合的补集即为非紧急集合。两个集合中都含有已经被邻居节点下载过的内容片，也有未曾下载的内容片。内容片的下载优先级用P表示，P越大，内容片越优先被下载，通常P取值为0.5～1。在分发开始之前，EP会先将内容片分成两个集合，选定要下载的分片集合后，在两个集合内部采用最少片优先的算法下载当前邻居中副本数目最少的分片。传统片选策略与自适应片选策略的比较如图1所示。

这种片选策略是自适应的，S、L、P都是可动态调整的参数。如固定S为0，L为内容片数目，此时两个集合合并，就变成了完全的最少片优先片选，适合非流式内容的分发；如果S随时间的推移逐渐变大，L固定一个小于内容片总数的值，P根据内容的急迫性不断调整，就可以支持流式内容的分发，适合流媒体业务。这样就可以让片选策略适应不同类型内容、不同业务的分发情况，达到良好的分发性能。

3.6 分发过程

内容分发过程是指自适应聚类片选分发模型的工作过程，包括分发模型从CP获得分发任务到成功分发到EP的流程。假定所有参与分发的EP已经在CP注册了HTS，分发流程如图2所示。

在分发流程中，EP与邻居节点交换分片信息时，用二进制的串表示内容片的下载与否[12]。如规定某位为0代表此内容片未下载，1代表已下载，这样可用少量存储空间表示内容分片的下载情况，当内容分片为256 KB时，1 GB的内容文件仅需要512 byte的空间。当某节点有新的内容分片加入时，EP将直接向其邻居节点广播新加入的内容分片序号，邻居收到广播信息后，更新自身中此节点的内容片位图。当EP的邻居节点中没有要下载的分片的聚类时间达到阈值之后，将会重新聚类，这也是自适应的一种体现，动态地适应变化的网络状况，最大效率地获取内容分片。当EP内的所有内容分片均被下载 （内容的二进制标志串各位都为1）时表示此EP已经接收完毕，向CP返回接收完毕信号，此时该EP停止聚类和片选，只向邻居节点提供自身内容片的上传。

图1 片选示意

图2 分发流程

在分发过程中CP会不断向参与分发的EP发送轮询消息，直到接收到EP的接收完毕的反馈信息，记录当前分发进度。若此过程中某EP有失败消息返回，CP将立即对该EP启动重传，并记录错误信息，若依旧收到失败返回消息，则调用HTS对此EP的属性情况进行更新，然后放弃此EP，重新选择替代EP加入分发流程。当所有EP都接收完毕之后，CP收到EP的成功接收信号，分发流程完成。

4 性能分析

当前的工程应用中，分发服务多采用BitTorrent模型，这种模型对于块式内容的分发能达到比较好的效果，并且支持流式内容分发。为了验证本文设计的分发模型的性能，在实验室环境下设计实现了一个简单分发模拟器，用于模拟自适应聚类片选模型和BitTorrent模型的分发过程，并且比较其性能。设计一个分发模拟器，其固定的聚类算法标准参数a为0.75，最少片优先最佳概率P为0.8，采用平均分发时间作为衡量块式内容的性能标准，采用连续索引比（continuity index，CI）作为衡量流式内容性能标准，CI是指播放期限内下载的内容片与全部内容片的比值，比值越大，下载越流畅。块式内容分发性能对比如图3所示。流式内容分发性能见表2。

图3 块式内容分发性能对比

表2 流式内容分发性能记录

从图3和表2可以看出，在多域的流式块式混合分发的应用场景中，采用参数集为{C=50，a=0.75，K=35，P=0.8}，本文所采用的分发模型的性能明显优于传统的BitTorrent模型。

5 结束语

本文采用的自适应聚类片选内容分发模型，采用网状拓扑结构和自治域优先+随机选择的聚类算法，结合紧急内容最少片优先的动态片选策略，通过算法参数的调整，自适应地完成流式内容和块式内容的快速分发，从而适应不同业务的分发需求，弥补了其他分发模型在支持内容类型上的不足，具有良好的扩展性。由于分发模型中网状结构和邻居节点的设置，分发过程中CP需要不断调整EP的状态，EP需要随时维护自己的邻居节点的内容信息，增加了开销，一定程度上影响了分发性能，还有进一步改进的空间。

1 廖建新.移动智能网技术的研发现状及未来发展.电子学报,2003(11)

2 程久军,李玉宏,程时端等.移动P2P体系结构与关键技术的研究.北京邮电大学学报,2006,29(4):86～89

3 Francis P.Yoid:extending the multicast Internet architecture.http://www.aciri.org/yoid,1999

4 Pendakaris D,ShiS.ALMI:an application levelmulticast intfrastructure.In:The 3rd USENIX Symposium on Internet Techonlogies and Systemes,San Francisco,CA,USA,2001

5 Chu Y H,Rao S G,Seshan S,et al.A case for end system multicast.ACM SIGMETRICS Performance Evaluation Review,2000,28(1):1～12

6 Chu Y H,Rao S G,Seshan S,et al.Enabling conferencing applications on the Internet using an overlay multicast architecture.ACM SIGCOMM Computer Communication Review 2001,31(4):55～67

7 Zhuang S Q,Zhao B Y,Joseph A D.Bayeux:an architecture for scalable and fault-tolerant wide-area data dissemination.In:the Eleventh InternationalWorshop on Network and Operating System Support for Digital Audio and Video,New York,2001

8 RatnasamyS,Handleym,Kapp R,etal.Application-level multicast using content-addressable networks.In:Networked Group Communication,Third International COST264 Workshop,London,UK,2001

9 ZhaoB Y,KubiatowiczJD,Joseph A D.Tapestry:an infrastructure for fault-tolerant wide-are location and routing.USA:University of California,Computer Science Division,2001

10 BitTorrent Webside.http://www.bittorrent.com/,2007

11 天瑞雄.自组织覆盖网络建模与优化.清华大学硕士学位论文,2005

12 杨妙,王晶.IDP中消息分发模块的改进.电信工程技术与标准化,2009,22(6)