IPv6中k-Anycast通信模型的研究与设计.doc

第6期王晓喃等：IPv6中k-Anycast通信模型的研究与设计125IPv6中k-Anycast通信模型的研究与设计王晓喃1,2，唐振民2，钱焕延2（1常熟理工学院，江苏 常熟 215500；2南京理工大学 计算机与技术学院，江苏 南京 210094）摘 要：扩展了原有IPv6中Anycast概念，提出了一个IPv6中k-Anycast通信模型概念，此模型允许k个服务器协同工作共同完成一项服务，它很好地实现了k-Anycast 组节点动态加入和离开。此外，在本模型中k-Anycast服务请求消息会被距离最近的k-Anycast树节点处理，这样使得k-Anycast服务请求均衡地分布在k-Anycast 树节点之间从而得到高效的处理。在IPv6模拟环境下，将k-Anycast模型应用到CDN技术中，实验数据证明，k-Anycast模型的应用不仅大幅度地提高了服务质量而且也有效地节省了网络带宽，充分证明了k-Anycast通信模型的有效性、可行性以及实用性。关键词：IPv6；k-Anycast通信模型；权值；节点；多播中图分类号：TP393.04 文献标识码：B 文章编号：1000-436X(2009)06-0120-06Study and design of k-Anycast communication model in IPv6WANG Xiao-nan1,2, TANG Zhen-min2, QIAN Huan-yan2(1. Changshu Institute of Technology, Changshu 215500, China;2. School of Computer and Technology, Nanjing University of Science & Technology, Nanjing 210094, China)Abstract: The original anycast concept of IPv6 was extended and a k-Anycast concept in IPv6 was proposed which allowed k servers to cooperate with each other to accomplish a task. This model could achieve dynamic join, leave of k-Anycast nodes and route k-Anycast service requested messages to the nearest k-Anycast tree nodes which could provide the requested service, and all k-Anycast service request messages could be evenly distributed around the k-Anycast tree nodes and be transacted effectively and efficiently. In IPv6 emulation environment, this k-Anycast communication model was applied to CDN and the experimental data demonstrates that the k-Anycast communication model not only enhances the service quality but also effectively saves the network bandwidth, which proves the k-Anycast communication models validity, feasibility and practicability.Key words: IPv6; k-Anycast communication model; weight; node; multicast1 引言收稿日期：2007-03-08；修回日期：2009-05-05网络技术的飞速发展使Internet成为信息社会的基础载体，从而导致网络用户急剧增长，超过了现有网络的负载能力。因此，Internet的访问速度和服务质量还有待于提高，主要表现在长时间的传输延迟以及这种延迟的不可预知性。随着Internet上新的传输内容流媒体的出现，网络传输对象（例如视频文件）的数据量也变得越来越大，这就迫使必须找出一种有效的办法来提高这些大数据量网络传输对象的下载时间并且尽量节省网络带宽。在这种情况下，本文提出了k-Anycast通信模型。Anycast是IPv6所提供的一种特殊网络服务，它允许服务申请者访问共享同一Anycast 地址所标识的一组组成员中最近的一个（这里的最近是按路由协议的距离量度来计算）1。Multicast是一种在IPv4中就已经存在的网络服务，它允许服务申请者访问共享同一Multicast地址所标识的一组组成员。它与Anycast的区别在于：Anycast只访问一个Anycast组中距离源主机最近的一个组成员，而Multicast是访问一个Multicast组中的所有组成员2。k-Anycast是介于Anycast与Multicast之间的一种网络服务。本文中定义k-Anycast组中的每个组成员都具有一个QoS参数，而被选中的最优n(nk)个组成员必须符合以下2个条件：1) 此组成员的QoS参数值必须达到某种特定服务所要求的QoS要求；2) 在满足1)的情况下，要求此组成员距离源节点最近（这里的距离最近可以根据不同服务的需要采用不同的度量单位来计算，例如组成员性能、跳数等）。从上述所描述的k-Anycast定义不难看出，Anycast与Multicast是k-Anycast的2种特殊情况，即当k-Anycast组所有组成员都满足某种服务的特定QoS要求的情况下，k=1时为Anycast，而k=m（这里m为k-Anycast组成员的总数）为Multicast。k-Anycast模型具有广泛的应用价值，例如如果将k-Anycast模型应用到CDN（content distribution network）技术中，其服务性能会大幅度提高；k-Anycast模型也可以应用到密码学以及大规模并行计算处理技术中去。2 相关工作在参考文献3,4提出了针对MANET的k-Anycast通信模型概念，并且给出了在MANET模拟环境下3种实现k-Anycast通信模型的实施方案。但是参考文献3, 4中的k-Anycast通信模型概念只是针对MANET网络，而且是选取距离源节点最近的任意k个组成员，而没有考虑每个k-Anycast组组成员的QoS参数值是否达到某些特殊服务的QoS要求，也就是说，参考文献3,4中所提出的k-Anycast通信模型概念只适用如下情况：k-Anycast组所有组成员所提供的应用与服务都是彼此的镜像。但是，在某些应用中，一个服务是由多个服务器协同工作，共同完成的，服务器之间并不是简单的镜像关系。例如，在CDN技术中，一个大型文件被分成n个块，而这n个文件块按照一定规则分散地存储在遍布于网络各个角落的m个文件服务器中，如果想获取第i和j个文件块，很显然，参考文献3,4中所提出的k-Anycast通信模型概念是行不通的。因此，本文针对IPv6网络，提出了一个全新的k-Anycast通信模型概念，使其具有更广泛的应用前景。总结起来，本文具有如下特点：1）在IPv6网络中，本文提出k-Anycast通信模型概念；2）针对IPv6网络，给出了k-Anycast通信模型的具体实现方案；3）在IPv6模拟环境下，将k-Anycast模型应用到CDN技术中，不仅大幅度地提高了其服务质量而且也非常有效地节省了网络带宽。下面对k-Anycast模型进行详细的讨论和分析。3 通信模型3.1 基本描述在k-Anycast通信模型中，每个k-Anycast地址代表一种k-Anycast服务，一种k-Anycast服务又被分为n个子服务，一个k-Anycast组必须能够提供完整的k-Anycast服务。在本模型中， k-Anycast组具有如下定义：每个k-Anycast组包含m个节点(mk)，它们是按照树状拓扑结构排列的，其中，树的根节点被称作k-Anycast中心节点，此节点所在的网络区域的Unicast地址空间必须与其所拥有的Anycast地址空间相同，即目的地址为Anycast地址的数据包可以按照正常的Unicast路由方式被路由到此根节点；其余节点又被分成中间节点以及叶子节点，其中中间节点也称作树节点，它们不能提供任何k-Anycast子服务而只用于支撑k-Anycast树框架，这类节点一般都是路由器；叶子节点也称作组节点，它们可以提供一种或者多种k-Anycast子服务，这类节点一般都是k-Anycast服务器，一个k-Anycast树中的所有组节点必须可以协同工作，共同完成一个完整的k-Anycast服务。在本模型中，k-Anycast中心节点所在的网络区域称作主域，一种k-Anycast服务对应唯一的一个k-Anycast（组）树，一个k-Anycast树对应唯一的一个k-Anycast中心节点。在本模型中，k-Anycast中心节点的Anycast地址与Unicast地址是相同的，而其他组节点以及树节点都具有自己本身的Unicast地址，它与Anycast地址是不同的。在本k-Anycast通信模型中，客户端获取k-Anycast服务的过程可以描述如下：当客户端发送k-Anycast服务请求数据包时，此数据包会被路由到距离自己最近的某个k-Anycast树节点上，如果以此树节点为根节点的子树能独立完成客户的k-Anycast服务请求，那么它直接向客户端提供此服务，否则它会将该请求转发给它的上一级节点（即父节点），然后重复上述过程，直到一个节点，此节点能够提供客户端要求的完整的k-Anycast服务或者此节点为k-Anycast中心节点。一般情况下，客户端的k-Anycast服务请求都是由多个k-Anycast组节点协同工作共同完成的。3.2 k-Anycast地址IPv6中的Anycast地址模型与RFC1546最初建议的完全不同，前者提出在Unicast地址空间中分配Anycast地址，这样Unicast和Anycast地址从结构上没有任何区别，而后者则推荐使用独立的地址模型，本方案采用后者的观点，使用Anycast的独立地址模型5,6。IPv6的地址是分层的。根据IPv6地址的特点，本k-Anycast通信模型采用如表1所示的Anycast地址格式。表1k-Anycast地址格式36164k-Anycast PrefixHome IDGroup ID如表1所示，地址的前3bit是k-Anycast的地址前缀，其取值范围与可聚合全局单播地址相同，为001。而随后的Home ID的值则与k-Anycast组中心节点所在网络区域的Unicast地址空间相同。3.3 k-Anycast树的建立在k-Anycast通信模型中，一个k-Anycast地址代表一个k-Anycast组，而一个k-Anycast组对应一个k-Anycast树，其中k-Anycast中心节点（根节点）所在网络区域的Unicast地址空间与k-Anycast地址空间相同，因此，k-Anycast地址同时也是k-Anycast中心节点的Unicast地址。这样，当一个主机请求加入一个k-Anycast组的时候，它首先将自己标记为该组的组节点，然后构建Join消息，此消息包括主机本身的Unicast地址、所要加入的k-Anycast组选择最优组成员所采用的距离度量参数（比如跳数，当前处理的会话数或者是主机的处理能力等）、申请加入的k-Anycast组地址以及它本身所能提供的k-Anycast子服务的标识符等信息，Join消息的源地址为主机本身的Unicast地址，目的地址为请求加入的k-Anycast组地址，然后将其发送出去，同时记录下本节点父节点的Unicast地址（即Join消息的下一跳的Unicast地址）。这样，网络系统会把该消息朝着k-Anycast树根节点的方向路由推进。在路由过程中，Join消息所经过的每个路由器在接收到它之后，都会检查自身是否为该消息中的k-Anycast组地址所确定的k-Anycast树的树节点，如果不是，那么此路由器首先将自己标记为k-Anycast树节点，同时，建立一个孩子节点记录表，将申请加入k-Anycast组的源主机作为自己的第一个孩子节点加入到孩子节点记录表中，并记录下Join消息中的相关参数，即申请加入k-Anycast组的主机的Unicast地址，它到达此树节点的距离参数、申请加入的k-Anycast组地址以及它本身所能提供的k-Anycast子服务的标识符等信息，同时记录下本节点的子节点的Unicast地址（即Join消息的源Unicast地址）以及父节点的Unicast地址（即Join消息的下一跳的Unicast地址），然后用自己的Unicast地址取代原有Join消息中的源地址，目的地址不变，并修改相应的距离度量参数（例如跳数），将其发送出去；如果是树节点，那么它将申请加入Anycast组的源主机加入到自己的孩子节点记录表中，并记录下Join消息中相关参数（参数内容同上）以及子节点的Unicast地址（即Join消息的源Unicast地址），然后用自己的Unicast地址取代原有Join消息中的源地址，目的地址不变，并修改相应的距离度量参数，将其发送出去。然后，每个接收到Join消息的路由器都会重复上述过程，直到此Join消息到达k-Anycast树根节点为止。至此，该主机成功加入到所请求的Anycast组中，如图1所示。图1 k-Anycast树的建立过程不难看出，上述的k-Anycast组节点的加入过程可以保证所有的k-Anycast节点（包括树节点和组节点）组成一个树状结构。下面分析一个k-Anycast组节点如何离开所在的k-Anycast树。如果一个k-Anycast组节点申请离开其所在的k-Anycast组，它首先删除自身组节点的信息与身份，然后发送一个Leave消息给它的父节点，此Leave消息包括此组节点的Unicast地址以及所在的k-Anycast组地址，父节点接收到这个Leave消息之后，它会检查自身对应Leave消息中k-Anycast地址的k-Anycast树的孩子节点记录表并从中删除此组节点，然后判断此时的记录表是否为空，如果为空，那么它将删除自身的树节点信息。无论此时的记录表是否为空，它都将继续转发这个Leave消息给它的父节点，父节点接收到Leave消息之后，继续重复上述过程直到根节点为止。3.4 权值计算本模型采用权值的方式来获取最优k-Anycast组节点集合以提供完整的k-Anycast服务。一个k-Anycast树节点的孩子节点记录表中记录着以这个树节点为根节点的子树的所有叶子节点（组节点）的相关信息，其中权值域就是记录每个叶子节点在此树节点的权值。在本模型中，假设一个树节点有n个叶子节点，Di表示其第i个叶子节点到达此树节点的距离（此处的距离可以选择多种度量单位，例如跳数、综合处理能力或者是当前正在处理的会话数等），那么采用式(1)来计算第i个叶子节点的权值Wi，其中i1，2，n。(1)其中，r为非负实数。在式（1）中，如果r0，那么一个树节点的n个叶子节点的权值都相同，也就是它们被选择成为最优k-Anycast组节点的几率是相同的。而当r的值趋向无穷大时，对于任意DjDi，其中i，j1，2，n，并且 ij，可以用i/Dj来代替Di，此处0i1，这样就有，可以得到如下结果：(2)(3)其中，i，j1，2，n，并且ij。上述结果表明，当r趋于无穷大时，树节点总是会选择距离自己最近的叶子节点作为最优k-Anycast组节点。在本模型中，如果网络比较稳定，就可以选取一个固定的r值，否则就根据网络的拥塞情况动态地调整r值。下面分2种情况讨论如何选取r值。1) 网络没有拥塞的情况。一般情况下，客户发送的k-Anycast服务请求数据包要经过如下3个过程：网络传输、路由器排队并且被转发以及Anycast服务器处理，这里只对前2个过程感兴趣，因为它们往往决定着客户获取k-Anycast服务的响应时间。当网络没有拥塞情况发生的时候，数据包到达路由器排队的时间可以忽略不计，那么网络传输时间就决定着客户获取k-Anycast服务的响应时间。这种情况下，就希望距离树节点最近的k-Anycast组成员被选取为最优k-Anycast组成员，因此，在网络没有拥塞的情况下， r值要尽量大。2) 网络出现拥塞的情况。当网络出现拥塞的情况，数据包到达路由器排队等待转发的时间会成为客户获取k-Anycast服务响应时间的决定因素，这种情况下，就希望把客户的k-Anycast服务请求数据包分散到以树节点为子树的不同的k-Anycast组成员上被处理，以便减少排队所带来的延迟，因此，在网络出现拥塞的情况下，r值要尽量小。3.5 路由分析当一个客户端想申请k-Anycast服务的时候，它首先发送一个k-Anycast服务请求消息，此消息包括所要得到的k-Anycast子服务标识符，即说明客户端需要哪些k-Anycast子服务。k-Anycast服务请求消息的目的地址为k-Anycast组地址，源地址为本身的Unicast地址。这样，网络系统按照正常路由方式会把该消息朝着k-Anycast中心节点的方向路由推进，每途径一个路由器，这个路由器都会检查自己是否为此k-Anycast 树节点，如果是，那么它会检查自身此k-Anycast树对应的孩子记录表以确定以自己为根节点的子树的叶子节点是否能提供客户端所要求的k-Anycast（子）服务，如果不能，它会将k-Anycast服务请求消息转发给自己的父节点，父节点重复上述过程，直到到达一个节点，以此节点为根节点的子树能提供客户端所要求的k-Anycast（子）服务。然后，这个树节点会根据子树内的叶子节点的权值选择出一个最优k-Anycast组节点集合，这个集合能完成客户所要求的k-Anycast（子）服务。然后，树节点会给集合中的每个k-Anycast组节点发送一个树内服务请求消息，此消息包括要求叶子节点所要完成的子服务标识符，树节点发送的所有消息所包含的子服务标识符的并集等于客户端k-Anycast服务请求消息中所要求的子服务标识符。这样，这些最优k-Anycast组节点在接收到树内服务请求之后，根据消息中的子服务标识符将子服务结果返回给子树的根节点（树节点）。这样，子树根节点（树节点）在接收到所有返回信息之后，进行整理和包装，最后向客户端返回一个完整的子服务应答。如果k-Anycast服务请求消息途径的路由器不是k-Anycast树节点，那么它将按照正常路由方式继续转发客户发送的k-Anycas服务请求消息，一直到达k-Anycast中心节点为止。k-Anycast中心节点接收到客户发送的服务请求消息之后，同样重复上述过程，根据整个k-Anycast树内的叶子节点的权值选择出一个最优k-Anycast组节点集合，然后向集合中的每个最优k-Anycast组节点发送一个树内服务请求消息，此消息包括要求组节点所要完成的子服务标识符，最后将这些最优k-Anycast组节点返回的子服务结果进行整理，返回给客户一个完整的k-Anycast（子）服务应答。在本模型中，叶子节点到达树节点的距离可以根据不同的服务质量要求而采取不同的度量单位，比如当前所处理的会话数，组节点到达树节点的跳数等。本文采用跳数为度量单位，为了计算方便，计算权值公式里的r取值为1，那么根据图1可以得到如下的k-Anycast权植树，如图2所示。如图2所示，组节点1在树节点1的权值为1；而组节点1与组节点2在树节点2的权值分别为1/3与2/3，而组节点1与组节点2在根节点的权值分别为2/5与3/5。这样，当一个k-Anycast服务请求消息（此消息内的子服务标识符为1、2）到达树节点2时，因为树节点2本身是此k-Anycast地址所对应的k-Anycast树的一个树节点，以它为根节点的子树的叶子节点组节点1与组节点2都能提供子服务1，所以，它选取权值最大的组节点2来提供子服务1，而只有组节点1可以提供子服务2，所以，它选取组节点1来提供子服务2。这样，组节点1与组节点2组成了最优的k-Anycast最优组节点集合。然后，树节点2向组节点1发送一个树内服务请求，图2 k-Anycast树节点的权值其内容为子服务2，向组节点2也发送一个树内服务请求，其内容为子服务1。这样，组节点1与组节点2分别向树节点2返回子服务2和1的服务结果。最后，树节点2整理这些返回的子服务结果，并将其发送给客户端。在本通信模型中，由于网络的拥塞情况可能随时变化，所以，本模型中的每个树节点可以根据当前的网络拥塞情况来动态地选取r值（在本文的IPv6实验环境中，认为当前占用的带宽占总体带宽的80%的情况是拥塞，因为此时路由器出现了排队情况），以便更好地提供k-Anycast服务。对于同一个子服务，如果在一个树节点中有多个叶子节点的权值相同，那么采用轮流分配的原则，依次将它们作为最优k-Anycast组节点。4 性能分析为了证明本文提出的IPv6网络中k-Anycast通信模型的有效性以及高效性，本文将此模型应用到CDN（content distribution networks）技术中去。实验采用Modelnet模仿IPv6网络物理拓扑结构，仿真结构中包括40个k-Anycast服务器节点以及5台路由器，5台路由器将整个网络分割为5个子网，每个子网包括8个k-Anycast服务器节点，任意2台路由器之间有且仅有一条链路连接。在实验中，路由器之间、服务器之间以及路由器与服务器之间的链路通信能力为100Mbit/s，路由器与客户端之间链路层通信能力为50Mbit/s。实验将一个大文件分为1 000数据块，每个块的大小为45Mbit。初始化状态下，1 000数据块都保存在k-Anycast中心节点上，然后每个k-Anycast服务器节点按照随机性原则从k-Anycast中心节点下载任意个（随机数为25100之间）数据块。在上述IPv6模拟环境中采用3种方案实现一个客户端下载一个完整文件的过程，第1种是随机方案，即根据客户的要求，采用随机选取服务器的原则为客户端提供服务；第2种是距离最近方案，即选取当前距离源客户距离相对较近的服务器为客户端提供服务；第3种就是利用k-Anycast通信模型为客户端提供服务。在本实验中，在网络拥塞的情况下，r取值为0，不拥塞的情况下，r取值为1 000，如图3所示。图3 3种方案比较的结果综上所述，本文提出的IPv6网络中k-Anycast通信模型具有如下特点：1）本文提出了在IPv6环境下的k-Anycast通信模型概念，本模型允许k个服务器协同工作，共同完成某项任务；2）客户端发送的k-Anycast服务请求总是到达整个k-Anycast树中距离客户端最近的树节点，然后以此树节点为子树根节点，根据子树叶子节点所能提供的子服务以及树权值（可以采用多种度量方式，本模型采用跳数）来确定最优组节点集合；3）本模型允许k-Anycast 组节点动态地加入或离开；4）本模型中，各种控制消息的传输只需要跨越很小的物理网络并且这些消息的数据传输量很小；5）本模型根据网络的拥塞情况会采取动态的策略把不同客户发出的服务请求消息的子服务分配给不同的最优k-Anycast组节点处理。5 结束语本文提出了IPv6网络中的k-Anycast通信模型，并将此模型应用于CDN技术，实验结果证明了此模型的有