CAN算法的分析与仿真
算法的分析与仿真
组长：SC06023108 顾菁华
组员：SC06023103 徐其
SC06023105 周楠
SC06023106 丁晟
SC06023107 李理敏CAN
,小组分工
组长 顾菁华 SC06023108 CAN算法C 语言实现以及负载均组员 周楠 SC06023105 CAN
丁晟 SC06023106 CAN
李理敏 SC06023107 CAN
徐其 SC06023103 衡的优化 原理研究以及结构分析 寻路性能优化 算法负载均衡问题研究 基于CAN 的应用层组播研究
,摘要
内容寻址网络（CAN ）是一种用于结构化对等网络P2P 的分布式哈希查找系统，可以在Internet 规模的大型对等网络上提供类似哈希表的功能，具有可扩展、容错和完全自组织等特点。
本文介绍了CAN 的基本结构和工作原理，对其关键技术寻路性能、负载均衡作了优化和改进。在VC 6.0中实现了CAN 的基本功能、负载均衡优化。最后，介绍了基于CAN 算法的应用层组播。
【关键字】 CAN，寻路性能，负载均衡，组播
II
,目录
摘要........................................................................................................................................... I 目录.........................................................................................................................................III
1. 概述...................................................................................................................................1
1.1 CAN基础结构.....................................................................................................1
1.1.1
1.1.2 数据模型......................................................................................................1 接入模型......................................................................................................2
1.1.3 CAN路由.....................................................................................................2
1.2 CAN构造.............................................................................................................3
1.2.1
1.2.2
1.2.3
2.
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
3.
3.1
3.2
3.3 节点插入......................................................................................................4 节点离开......................................................................................................4 节点失效......................................................................................................4 寻路性能优化...................................................................................................................6 多维坐标空间.......................................................................................................6 多实体（reality ）结构.........................................................................................6 过载坐标区...........................................................................................................7 更好的CAN 路由metrics....................................................................................7 最大面积寻路.......................................................................................................8 修改邻居表沿对角线寻路...................................................................................8 层次化结构...........................................................................................................8 多个哈希函数.......................................................................................................9 多播发现(MD)算法:...........................................................................................10 梯度法(GR)........................................................................................................10 分布式堆.............................................................................................................11
3.3.1
3.3.2 堆定义........................................................................................................11 分布式堆(Distributed Heap method)算法.................................................12 负载均衡.........................................................................................................................10
4. CAN基本操作的C 语言实现.......................................................................................14
4.1 CAN算法的基本操作.......................................................................................14
4.2
5.1
5.2
III 对CAN 算法负载均衡的优化..........................................................................18 组播组结构.........................................................................................................21 组播消息传递机制.............................................................................................215. CAN在应用层组播中的应用.......................................................................................21
,1. 概述
对等网络（Peer-to-Peer Network，P2P ）的核心是P2P 路由算法，算法的优劣直接关系到P2P 系统的性能和可扩展性。但P2P 最初设计时在扩展性方面存在重大问题，如早期Napster 使用集中目录服务而存在单点故障问题，Gnutella 采用类似OSPF 路由协议的洪泛搜索机制，不仅造成过多的网络流量，同时可扩展性也较差。为了解决P2P 系统可扩展性差问题，一些研究工作组提出了新一代支持分布式哈希表（DHT ）技术的结构化可扩展P2P 系统，这是一种采用纯分布式的消息传递机制和根据关键字进行查找的资源定位服务，是目前扩展性最好的P2P 路由方式之一。此类路由算法主要包括加州大学伯克利分校的CAN （ Content-Addressable Network ，内容寻址网络）和Tapestry ，麻省理工学院的Chord 、IRIS ，以及微软研究院的Pastry 。它们采用各自的DHT 算法，而不同的DHT 算法决定了P2P 网络不同的逻辑拓扑，比如CAN 是一个d 维坐标空间，Chord 是一个环形拓扑，Tapestry 则是一个网状的拓扑。
CAN 是一种用于结构化对等网络P2P 的分布式哈希查找系统，可以在Internet 规模的大型对等网络上提供类似哈希表的功能，具有可扩展、容错和完全自组织等特点。
1.1 CAN基础结构
1.1.1 数据模型
在CAN 的构造中，借助于一个虚拟的d 维笛卡儿坐标空间。这是一个完全逻辑化的坐标空间，并且在每一维上都是周期循环的。举例来说，我们假设一个一维的，[0,1]的坐标空间，这样一个空间由一个圆圈表示，见图1。空间的大小等于圆的直径。在这样一个一维空间中，两点之间的距离等于它们之间最短的弧长。
1
,CAN 系统相当于一张哈希表，它是由很多单个的节点组成，这些节点存储了整张哈希表的一部分。在这里，一个节点并不等同于一台对等主机，它更像是一个仅提供信息引索的服务器。在CAN 中，一块哈希表叫做一块空间。即CAN 的d 维笛卡儿空间中被节点划分为若干空间，每个节点占据一块空间。CAN 中的空间可有不同的大小。但是在二维中，这些空间必须是正方形。
1.1.2 接入模型
用户和P2P 系统之间的第一步交互就是接入系统。CAN 提供一种使用bootstrap 的机制。假设CAN 有一个可以帮助解析CAN 中bootstrap 节点的IP 地址的DNS 域名系统。一个bootstrap 节点拥有一张含有部分节点信息的表。当这个模型中的一个用户发出请求，并且使用了CAN 域名，它的客户端就能自动的从一个bootstrap 节点那里建立起一个连接，同任意一个可连接的节点相连。
1.1.3 CAN 路由
对分布式路由表（DHT ）系统来说，路由算法是非常重要的。因为它定义了询问的相应时间和数据的可达性。一个不好的分布式系统的路由算法会降低系统的性能。简单说来CAN 的路由就是由源节点向目的节点沿着笛卡儿坐标的直线前行的。一个CAN 节点维护了一张坐标路由表，这张表包含这个节点的相邻节点的IP 地址和虚拟坐标空间。在d 维坐标空间中，两个节点相邻的定义就是如果它们在d-1维空间中重叠并且在一维空间中相邻，那么它们则在d 维空间中相邻。一个包含目的节点坐标的CAN 消息，通过它的邻居坐标集和简单的贪心算法（greedy forwarding）找到目的坐标。
这里还有一个错误忍耐路由（Fault tolerance routing）的概念。就是说如果一个节点丢
2
,失了它所有邻居节点信息，这样上面这个路由算法就失效了。为了避免这种情况，我们要在基础的路由算法之上扩展下面的规则：在达到节点之前先查询当前节点的邻居节点是否都是可达的。在这种情况下，数据可能不是最优的，但是所选择的路径都是可达的。下图就是错误忍耐路由的图示：
对一个划分为n 等份的d 维空间来说，平均路由长度为(d /4)(n 1/d ) 跳，并且单个节点有2d 个邻居。这样的结果意味着对d 维空间来说，我们可以增加节点（也就是空间）的数量而不增加每个节点状态，因为平均路径长度是成(n
1/d ) 的整数倍增长。
1.2 CAN 构造
这部分主要说明CAN 是如何构造的。我们假设在这个系统中原先已有起码一个节点。 在CAN 中，信息以关键字－数据对（Key ，Value ）的形式存储，其中Key 通过两个独立的均匀哈希函数映射到CAN 空间中的一点P （x ，y ），如果P 点属于某一节点所占的区域，则该节点实际存储这一关键字的数据对。此外，每个节点都存储了其每个邻居节点的IP 、物理IP 等信息，并定时对这些信息进行更新以保持邻居间的互连。
在CAN 中，主要提供三种对于（Key ，Value ）的基本操作，即插入、查询、离开或失效。下面我们介绍其中的节点插入、离开和失效，节点的查询将在第二部分详述。
3
,1.2.1 节点插入
一个新的节点到达之后，我们首先要给它分配一块空间。这里要说明的是我们没有空闲的空间可供分配，新的节点的达到我们都需要从已有的节点空间中划分出来。最简单的方法就是把一个节点的空间一分为二。下面就是这个新的节点要找到这块分配给它的空间，这就需要一个寻找空间的路由算法，如下：
一个新的节点同CAN 中任意节点相连都要使用2.2中所述的接入机制。当新节点发送一个加入请求之后，CAN 节点随机的选择笛卡儿坐标空间中的一个点。这个点的空间就被一分为二。这个加入请求由2.3所述的普通的CAN 路由算法实现。
一旦新节点找到自己的坐标，下一步就是要启动这个新节点。首先，这个新节点以及它的另一半得到它的邻居列表，然后它要把新的系统状态通知它的邻居来修改它们的邻居列表。这样整个系统得到更新。
1.2.2 节点离开
当一个节点正常的离开系统，它将告知系统它将离开。在这种情况下，很有必要保持物理完整性，替代离开节点的空间和逻辑完整性。为此，CAN 提供了如下的算法：
将要离开的节点找到这样一个节点，这个节点首先要求合并之后面积最小，若有若干面积最小的代选节点，则选择离开节点的空间合并之后组成一个方形空间的节点。
将离开的节点空间被已被选中的邻居覆盖，物理完整性得到保护。
为这个空间提供一个路由，这个系统需要更新它的状态。离开节点的邻居节点将得到通知，另外一个节点现在开始变为它们的邻居节点。接受这个空间的节点也将改变自己的邻居列表并通知它的邻居节点。
1.2.3 节点失效
在这种情况下，节点离开之前不通知系统。这将通过一个接管算法来处理，这个接管算法将保证失效节点的一个邻居节点接管这块空间。然而失效节点包含的（Key ，Value ）对就会丢失直到数据拥有者刷新状态，在这种情况下，P2P 文件分布系统的用户将会再次连接CAN 并且共享他们的文件。
在一般情况下，普通节点发送周期性的更新消息给它的邻居节点，这些消息包含它的空间坐标和它邻居节点坐标的列表。如果很长时间邻居节点没有收到这样的消息则表明它失效。如果某个节点判断出它的某个邻居节点失效它就会初始化TAKEOVER 机制。需要指出 4
,的是，几个邻居节点可以同时独立的开始TAKEOVER 机制。
TAKEOVER 机制如下：
每个节点初始化一个正比于它的空间大小的计时器。
如果一个计时器到期了，它就会发送TAKEOVER 信息给所有失效的邻居节点。
收到TAKEOVER 信息的邻居节点和它自己的空间大小比较，如果发送TAKEOVER 的空间比自己的空间小，则发送新的TAKEOVER 消息。
一个没有收到一个较小空间的TAKEOVER 消息的失效节点将会接管离开节点的空间。 5
,2. 寻路性能优化
前面描述的CAN 的基本算法提供了低节点状态（d 维空间为O （d ））和最短路径长度（d 维空间n 个节点为O
（d ）跳）之间的平衡。这里所说的跳数是应用层的跳数，不是IP 层的跳数，并且每跳的延迟是真实的。在CAN 中相邻的节点实际上可能相隔几里或中间经过很多IP 跳，查找的平均总延迟是CAN 平均跳数乘以每个CAN 跳的平均延迟。我们希望能够得到一个可以与请求者和拥有关键字的节点之间的真实IP 延迟相比较的查找延迟。可以用以下几种方法进行寻路性能优化。
2.1 多维坐标空间
改进寻路延迟的最简单的方法是增加坐标空间的维数。平均路径长度为O
（d ），假设n 为常数，很容易找到一个最优的维数值d 使平均路径长度最小。表2-1是节点数为1000时的一个例子。 d
2
3
6
7
8
10
20平均路径长度200 30 18.973 18.778 18.970 19.952 28.250
表2-1 1000个节点时维数最优值
2.2 多实体（reality ）结构
设计多个独立的坐标空间，系统中每个节点在不同的坐标空间中分配不同的区。假设将坐标空间称为“实体”，因此对于有r 个实体的CAN ，每个节点将被分配r 个坐标区，并且维护r 个独立的邻接表。
这样，哈希表的内容在每个实体上复制，提高了数据的可用性。例如，指向某个文件的指针存在坐标空间（x ，y ，z ）中，对于四个实体的情况，指针会存在每个实体坐标空间（x ，y ，z ）的四个不同的节点中，这样，只有当四个节点都失效时，数据才不可用。多个实体也
6
版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。
