1.       引言

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

       CDN（Content Delivery Network）即内容分发网络，它的原理是通过在现有的Internet网络中加入一层新的网络架构，将要分发的内容发布到最接近用户的网络边缘节点EP（Edge Point），使用户能就近获得所需内容，CDN一般分为两级结构，有中心服务器节点CP（Center Point）和边缘节点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传统分发模型

小规模多源组播分发模型

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

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

代表是 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 内转发报文。这样可减少节点上维护的状态信息，提高数据传输的可靠性，但也会产生大量重复报文。存在的问题是，逻辑空间中节点间的关系并不能对应实际网络中的关系，得到的报文转发路径很有可能在性能方面存在问题。

BitTorrent分发模型

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

3       自适应聚类片选模型

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

3.1CP中HTS（Hash Table Service）服务

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

表1 HTS接口

3.2CP与EP片式内容传送

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

       内容分片的大小会影响到整个传送过程的效率，所以分片大小是一个很重要的参数，有研究表明，分片大小为256KB或者512KB时，效率最高，BitTorrent也是采用了256KB或者512KB（版本不同参数不同）的分片大小。本设计采用256K的内容分片，这样既不会因为分片太小造成EP之间内容片互传时IO开支过大，也避免了分片过大分片重传时的耗时低效^[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应该满足：

min{M,aC} ≤ K ≤ min{M,C}

a是一个系数，0.5 < a < 1,这种方法属于策略聚类算法，可根据节点间的邻近度来分配邻居，让物理网络上延迟低的节点形成邻居关系，按照节点的网络坐标来聚类，这样可以使自治域内的节点互相发现，网络传输的开销限制在自治域内部。假如EP数量过多，同一个自治域中可用EP数量大于K或者不同域中可用EP数量大于C-K时，需要从众多EP中选出邻居节点，这时采用BitTorrent所采用的随机邻居选择法，由CP随机指定x的邻居节点，这种方法能在动态变化的互联网环境中用最小的计算开销在很大的概率下达到次优的内容可用率，同时设定时间阀，时间阀值达到后重新选择邻居，保证了邻居之间相对保持高速的连接。

本文中采用的这种聚类算法，采用优先策略聚类和随机邻居选择算法的结合的方式，首先选择和自己在同一个域的适量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所示。

图1 片选示意图

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

3.6分发过程

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

图2 分发流程图

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

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

4       分析与总结

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

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

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

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

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

参考文献

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

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

[3]      FRANCIS P. Yoid: extending the multicast internet architecture[EB/OL].http://www.aciri.org/yoid,1999.

[4]      PENDAKARIS D,SHI S.ALMI: an application level multicast intfrastructure[A]. Aanderson T. The 3^rd USENIX Symposium on Internet Techonlogies and Systemes[C]. San Francisco, CA, USA: USENIX Association, 2001. 49-60.

[5]      CHU Y H, RAO S G, SESHAN S, ZHANG H. A case for end system multicast[J]. ACM SIGMETRICS Performance Evaluation Review, 2000, 28(1):1-12.

[6]      CHU Y H, RAO S G, SESHAN S, ZHANG H. Enabling conferencing applications on the internet using an overlay multicast architecture[J].ACM SIGCOMM Computer Communication Review 2001,31(4):55-67.

[7]      ZHUANG S Q, ZHAO B Y, JOSEPH A D. Bayeux: am architecture for scalable and fault-tolerant wide-area data dissemination[A]. NIEH J, SCHULZRINNE H. The Eleventh International Worshop on Network and Operating System Support for Digital Audio and Video[C]. New York, USA: ACM Press, 2001. 11-20.

[8]      RATNASAMY S, HANDLEYM, KARP R, SHENKER S. Application-level multicast using content-addressable networks[A]. CROWCROFT J, HOFMANN M. Networked Group Communication, Third International COST264 Workshop, NGC 2001[C]. London, UK: Springer, 2001. 14-29.

[9]      ZHAO B Y, KUBIATOWICZ J D, JOSEPH A D. Tapestry: an infrastructure for fault-tolerant wide-are location and routing[R]. Berkeley, USA: University of California, Computer Science Division, 2001.

[10]  BitTorrent Webside[EB/OL]. 2007-08-15, http://www.bittorrent.com/.

[11]  天瑞雄, 自组织覆盖网络建模与优化[D]. 北京: 清华大学, 2005.

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