21CAN的路由-哈尔滨理工大学网络信息中心.ppt

内容寻址网络————CAN CAN (Content-Addressable Network)介绍 CAN的设计 CAN的改进 未来的工作 1.CAN介绍 哈希表是一种有效地将key映射为value的数据结构，并且在软件系统的实现中作为核心基础。许多大范围的分布式系统同样会从哈希表的函数型中获益。我们使用CAN来表述这种分布式的因特网际的哈希表。 CAN由很多个体节点组成。每个CAN节点存储哈希表的一块(称为“zone”)。此外，一个节点还维护表中的小部分相邻zone。对一个特定key的请求（输入、查找或着删除）被通过CAN的中间节点路由向目的节点。CAN设计是完全分布式的（不需要中心化的控制、协作和配置）、经济的（节点只维护少量的与系统中节点数量无关的控制信息—state）和错误容忍的（节点可以绕过错误进行路由）。与DNS和IP路由系统不同，CAN的设计不由任何力求经济的严格的分级命名结构的形式组成。 2.CAN的设计 CAN的设计中心围绕着一个在d-平面上虚拟的坐标空间。这个坐标空间是完全逻辑上的，与任何物理坐标系无关。在任意时刻内，整个坐标空间在系统内所有的节点间被动态地划分，每个节点在全部空间内“拥有”自己单个的、不同的区域。例如，下图显示了一个2维[0,1]x[0,1]坐标空间被5个CAN节点所划分。 2.CAN的设计 A~E分别是5个CAN 节点，每个节点都有 自己所拥有的信息， 并且独立地拥有属于 自己的区域—zone。 虚拟的坐标空间用来 存储（key，value） 对：（K，V）对， 关键字K通过唯一的哈希函数被映射到一个坐标空 间之中的一个点P上。相应的（key，value）对， 便被存储到拥有P点所坐落的区域的节点上。 2.CAN的设计 CAN中的节点自组织到一个呈现为虚拟坐标空间的覆盖网中。每个节点学习并且维护与它的坐标zone相邻的那些节点的IP地址。坐标中的直接邻居节点集作为坐标的路由表，使路由能在这个空间中的任意两个节点之间进行。 下面，我们将描述这个设计的三个最基本部分：CAN路由、CAN覆盖坐标结构和CAN覆盖的维持。 2.1 CAN的路由 直观地讲，CAN中的路由沿着穿过虚拟空间的直线从 源节点到目的节点进行。一个CAN节点维护一张坐标路由表，这张表持有IP地址和在坐标空间中这个节点的每一个 直接邻居的虚拟坐标zone。在一个d维坐标空间中，如果 两个节点的坐标有d-1维是重合的，而剩下1维是相邻的， 那么他们就是邻居节点。比如，在下图中，节点5的是节点 1的邻居，因为他的坐标zone在Y轴上重合，在X轴上相邻。这个纯粹的本地邻居足以在空间中的任意两个节点间路由。一个朝向它的目的节点的信息，用它邻居节点的坐标集， 简单而贪婪地路由向与目的节点坐标最接近的邻居节点的 坐标，下图显示了一个简单的路由路径。 2.1 CAN的路由 如果节点1向（x,y） 对发起查找，那么节点1首先 检查自己的邻居节点，找到 距离点P（x,y）最近的邻居 节点，即4，将CAN消息发送 给节点4。依次类推，直到找 到目的点P（x,y）所在的节 点。如果内容存在，则寻址成 功；否则，寻址失败。 2.2 节点的加入 节点加入： 在拥有了自己的zone之后，新节点从先前的zone占有者那里学习到他的坐标邻居集中的IP。这个集合是先前的zone持有者的邻居的子集，再加上先前的持有者。类似的，先前的持有者更新他的邻居节点集合以删除那些不再是邻居的节点。最后，新的和老的邻居几点都要被这个重分配的空间所通知。跟随者周期性的刷新，每个系统中的节点向它的所有邻居几点发送一个内有它当前所属zone的“立即更新消息(immediately update message)”。这些soft-state风格的更新保证了所有节点能够快速地获悉系统的变化并且有章可循地更新自己的邻居节点集合。 新节点的加入仅仅对坐标系中一个小区域内的一小部分已存在节点产生作用。一个节点维护的节点数量只依赖于坐标空间的维数，独立于系统的总结点数。因此，节点加入仅影响O (d)（d为维数）个已存在的节点，这是大规模CAN的关键。 2.2 节点的加入 示例：节点加入 1.新节点首先找到一个已经存在的CAN节点； 2.新节点应用路由机制，找到一个属于自己的区域； 3.执行分割操作，然后原有区域的临界区域被告知发生了分割，各自更新邻居集，这样新节点才能被别的节点路由到。 2.3 节点的退出 当节点离开CAN时，我们需要