（通信与信息系统专业论文）i3网络的信息查询与存储机制研究.pdf

摘要 摘要 随着i n t e m e t 技术的迅猛发展，以腰分组交换技术为代表网络技术已经对人 们的工作和生活产生了深远的影响。用户业务种类急剧增长，移动办公，视频会 议等新的业务和应用不断涌现，这就要求网络增加更多针对这些新业务的新基础 设施来支持这些新业务的开展，同时还需要网络具有很强的可扩展性和容错能力。 然而，当前i n t e r n e t 的体系结构蹙基于点对点的单播通信模式设计的，它对移动性， 多播等这些网络中更般的通信抽象存在着根本的不兼容。因特网间接基础设施 ( i n t e r n e ti n d i r e c t i o ni n f r a s t r u c t u r e - i 3 ) 正是基于解决上述鼹络中存在的闯题丽提出 的。 基于i 3 的名址分离技术是一个较薪的研究领域，它是对下一代i n t e m e t 体系结 构设计的有益尝试，同时也为下代i n t e m e t 体系结构提供了一个参考模型。所以 本文的第一部分工作的贡献是研究了i 3 的基本思想，体系架构，网络模型，及其 核心协议c h o r d 等，同时研究了i 3 如何实现对移动性、多播、任播等更一般的抽 象的支持。 由于网络中一些薪的大容量业务 、蝓 圈3 - 9 改进憨主动式c d i 3 考氇镱查询转发过程 我们采用主动p u s h 的方法来解决上述问题，如图3 - 9 所示，服务器s 1 根据自 己的访阅来源统计表的统计结果来决定将服务i d sp u s h 给c d i 3 网络中酶哪个服务 器，以便减轻本服务器的压力，更好的为用户提供服务。当s 1 统计到来崮节点s 2 的对服务i d s 的查询较多时，它就会将服务i d s 发送到服务器s 2 上，s 2 在收到服 务盾，将它们存储奁热点鸯容存褚嚣，并将对瘦的瑟务器t r i g g e r 统诗表中的存储 标志位置1 ，当再有来自本地的对服务i d s 的查询时，s 2 就直接从本地的热点内同 存储区将服务发送给用户；这样裁减轻了服务器s 重静负载，暴时减少查询分组的 由于排队所导致的较大的延迟，同时也减少了s 1 给大量网络边缘的终端发送分组 所占用的大量的网络带宽。上述方案是c d i 3 缀务器s l 在受载过大镌清况下主动 将服务p u s h 给用户需求较大的其它c d i 3 服务器。 3 5 本章内容小节 本章对原始只转发露不存储的舀模型进行了改进，设计了具有数据存储耪蠹 容分发功能的新的模型一c d i 3 模型，掇出了两种实现c d i 3 模型的方案，并详细 描述了它们的设计思想及其各良的优势。考虑到c d i 3 机制需要对网络边缘的集中 式服务器进行改进，造成更大的麻烦，本章又提出了一种主动式的c d i 3 机制，它 将对热点服务的监控和统计转移到c d i 3 服务器上，从薅省去了对网络边缘的集中 。3 8 第三章c d i 3 一i 3 的存储机制研究 式服务器的更改，同时本章针对以上提出的机制，为其设计了查询信息来源统计 表、c d i 3 服务器的目录结构，服务器模型及新的t r i g g e r 的存储格式等。最后，本 章详细描述了c d i 3 网络中分组的查询及存储机制的流程。同时本章还基于c d i 3 模型提出了一个新的技术，使得c d i 3 可以支持通信双方不同时在线的通信，这对 现有的i n t e r n e t 有线通信又是一个重要改进和提高，同时也提高了网络的容错和错 误恢复能力。 3 9 电子科技大学硕士学位论文 第四章两种基于c h o r d 的改进查询机制设计t c h o r d 和p c h o r d 4 1c h o r d 简介 c h o r d 1 0 】实现了这样一种操作：给定一个关键字( k e y ) ，将k e y 映射到某个节点。 如果给对等网络应用的每个对象都分配一个k e y ( 例如i 3 中的资源i d ) ，那么对等网 络中的数据查找问题就可以用c h o r d 很容易地解决了。 相容哈希 c h o r d 采用了相容哈希的一种变体为节点分配关键字。相容哈希有几个很好的 特点，首先是哈希函数可以做到负载平衡，也就是说所有的节点可以接收到基本 相同数量的关键字。另外，当第n 个节点加入或者离开网络时，只有1 n 的关键 字需要移动到另外的位置。c h o r d 进一步改善了相容哈希的可扩展性。在c h o r d 中， 节点并不需要知道所有其他节点的信息。每个c h o r d 节点只需要知道关于其他节 点的少量的“路由”信息。在由n 个节点组成的网络中，每个节点只需要维护其他 0 ( 1 0 9 n ) 个节点的信息，同样，每次查找只需要o ( 1 0 9 n ) 条消息。当节点加入 或者离开网络时，c h o r d 需要更新路由信息，每次加入或者离开需要传递o ( 1 0 9 2 n ) 条消息。相容哈希函数为每个节点和关键字分配m 位的标识符，此标识符可以用 s h a 1 1 4 】等哈希函数产生。节点的标识符可以通过哈希节点的m 地址产生，而关 键字的标识符可以直接哈希此关键字。 在相容哈希中，每个关键字都保存在它的后继( s u c c e s s o r ) 节点中，后继节点是 节点标识符大于等于关键字k 标识符的第一个节点，我们将其记为s u c c e s s o r ( k ) 。 相容哈希的一个特点就是当节点加入或者离开网络时对网络带来的冲击可以达到 最小。当节点n 加入网络时，为了保持相容哈希映射，某些原来分配给i 1 的后继 节点的关键字将分配给r l 。当节点n 离开网络时，所有分配给它的关键字将重新分 配给n 的后继节点。除此之外，网络中不会发生其他的变化。 图4 1 给出了节点n 1 6 在c h o r d 环上的加入和离开过程，如图( b ) 所示当服务 器节点n 1 6 加入网络时，它会通知它的后继节点n 2 2 及前驱节点n 8 更新指针表， n 2 2 收到信息后就将比关键字1 6 小k e y 值发送给n 1 6 ，然后将自己表中的小于1 6 的关键字删除，如图( c ) 所示；图( d ) 给出了节点n 1 6 退出网络的过程，它会先通知 4 0 第四章c d i 3 中基于c h o r d 的改进的查淘机制没计( t - c h o r d l 其后继节点并将关键字发送到n 2 2 ，同时通知n 2 2 和n 8 更新指针表。 n 2 2 圈 图4 1c h o r d 环上的节点加入和离开过程 关键字查找 在c h o r d 中，每个节点维护少量的路由信息，通过这些信息，可以提高查询 的效率。每个节点只需要维护一张最多m 个表项的路由表，我们称之为指针表 ( f i n g e rt a b l e ) 。节点1 1 的查找表的第i 个表项包括的是s = s u e c e s s ( n + 2 i 1 ) ，这里 l = 承= m 并且所有的计算都要进行m o d2 m ，s 称为节点n 的第f 个指针，我们用 n f i n g e r i n o d e 表示，指针表中的其他项的含义如表4 1 所示： 表4 1c h o r d 指针表各表项含义 符肇 定义 r m g e 啦 s t a r t ( n + 2 k 1 ) 瑚d 严l - l c ：m i m m - a l 弛g e f 【k 】s t a r t , f m g e r k t l 。s 搬】 a o d e 第一拿大予等子n _ f i n g e r k s t a r t 豹绣煮 皱k c e s 鞠蕾 标谖簿环中静下一拿续点；f i a g e r i n o d e p r e d e c e s s o r 标後蟹环中兹籍一个绦点 4 1 6 一”一 圜 胧圈 电子科技大学硕士学位论文 以图4 。2 为例，节点1 的指针表的表项应该分别指向标识符n + 2 0 ) m o d2 3 = 2 ， ( 1 + 2 1 ) m o d2 3 = 3 ，( 1 + 2 e ) m o d2 3 5 。而标识符2 的蜃继是节点3 ，因为它是2 之后的第一个节点，标识符3 的后继是节点3 ，而标识符5 的后继是节点0 。 这一方案有两个重要的特性：首先，每个节点都只需要知道一部分节点的信 息，丽且离它越近的节点，它就知道越多的信息。其次，每个节点的指针表通常 并不包括足够的信息可以确定任意一个关键字的位置。例如，图4 2 中的节点3 就不知道关键字l 的位置，因为l 的藤继节点信患并没有包含在节点3 的指针表 中。 图4 - 2c h o r d 环上节点的f i n g e rt a b l e 夺铡 当节点1 1 不知道关键字k 的后继节点时怎么办? 如果n 能够找到一个节点， 这个节点熬标识符更接近k ，酃么这个节点将会知道该关键字昀更多信息。根据这 一特性，n 将查找它的指针表，找到节点标识符大于k 的第一个节点j ，并询问节 点j ，看j 是否知道哪个节点更靠近k 。通过重复这个过程，1 1 最终将会知道k 的矗 继节点。 仍然考虑图4 2 中的例子，节点3 需要查找关键字l 的后继节点。由于l 属于 循环区间 3 6 】，它属于3 。f i n g e r 3 。i n t e r v a l ，因此节点3 查找其指针表的第3 项， 返回0 。由于0 在1 之前，因此节点3 将要求0 去寻找关键字l 的后继节点。依此 类推，节点0 将查找它的指针表并发现l 的后继节点是l 本身，于是节点0 将告 诉节点3 节点1 是它要找的节点。 4 2 第四章c d i 3 中基于c h o r d 的改进的查询机制设计( t - c h o r d ) 新节点的加入 节点n 的加入分为三个阶段： 【1 】初始化新节点的指针表。假设节点n 在加入网络之前通过某种机制知道网 络中的某个节点n 。这时，为了初始化n 的指针表，n 将要求节点n 为它查找指针 表中的其他表项。 2 】更新现有其他节点的指针表。 节点加入网络后将调用其他节点的更新函 数，让其他节点更新其指针表。 3 】从后继节点把关键字传递到节点n 。 这一步是把所有后继节点是n 的关键 字转移到n 上。整个加入操作的时间复杂度是o ( 1 0 9 2 n ) ，如果采用更复杂的算 法【2 7 1 ，可以把复杂度降低到o ( 1 0 9 n ) 。 失效节点处理 在i 3 网络中，对故障服务器节点的处理是一个重要的问题，因为它涉及到i 3 网络的容错和故障处理能力。在i 3 中，利用c h o r d 算法，当节点n 失效时，所有 在指针表中包括n 的节点都必须把n 替换成n 的后继节点，并且节点n 的失效不 能影响系统中正在进行的查询过程，因此对i 3 服务器来说，维护正确的后继指针 是非常重要的。为此每个c h o r d 节点都维护一张包括r 个最近后继的后继列表。当 节点n 知道其后继节点失效了，它就用后继列表中第一个正常节点替换失效节点。 4 2 c d i 3 中基于c h o r d 的改进的查询机制设计t - c h o r d 在c d i 3 网络中我们将i d 分为了三类：终端i d ，个人i d 和服务i d 。为了提高 i d 在c h o r d 环上的查找效率，我们为每一类i d 设计了一个c h o r d 环，也就是说每 个c d i 3 服务器上有三类路由表，终端i d 的路由查询表，个人i d 的路由查询表， 和服务i d 的路由查询表，由这三类路由表在c d i 3 服务器上就组成了三个平行的 c h o r d 环，为此我们为每个i d 设置了i d 类型信息字段，并为每个t r i g g e r 和数据分 组设置了类型变量。以便服务器收到分组后进行判断如何进行查询和转发。 由于原来由一个c h o r d 环来完成的查询和存储t r i g g e r 的工作现在由三个c h o r d 环来完成，每个c h o r d 环对应的查询后继节点的f i n g e r 表的长度就变小了，这样也 就较好的提高了c h o r d 的查询效率，同时在每个c d i 3 服务器节点负责的i d 的数 量巨大的情况下，会有大量的查询信息条目，在本地服务器上查询速度会很慢， 因此我们对一个服务器节点负责范围的每一类i d 都采用折半查找算法进行查询。 4 3 电子辩技火学硕士学位论文 4 2 1基于c h o r d 的改进的查询机制设计 在c d i 3 霜络中我们利麓| 薅样的c d i 3 照务器为每类试帮建立了一个c h o r d 环，这样就产生了三个平行的c h o r d 环，三个c h o r d 环各自拥有自己的f i n g e r 表， 以及后缝节点表。蠢此服务器节点只需要在判断凄i d 类型轰，根据判断的结果将 其发送到对应类型的c h o r d 环上进行焱询即可。为此我们为每个i d 设置了i d 类型 信息字段，并为每个t r i g g e r 帮数据分组设置了类型变量。以便服务器收到分组震 进行判断如何进行查询和转发。 黢务i dc h o r d 滔； 终端i dc h o r d 环 令太i de | 弼穗薹l ： 三重c h o r d 环结构 图毒。3t - c h o r d 结构匿 由于i d 的总数为终端i d ，个人i d 和服务i d 三者之和，所以现在每台c d i 3 服 务器上每个类型的c h o r d 环的f i n g e r 表的长度将会变短，露对对瘦盼本地本c h o r d 环的i d 的数餐将会大大减少，所以本方案同时提高了c h o r d 环上对后继节点的查 询效率，同时也提高了在本地路由表的查找效率。当服务器节点定位蜃，就需要 在本服务器上进行查询，如果服务器上对应的i d 的数量巨大，那么传统的采用顺 序查找的方式必然会耗费大量的查询时间，因此我们在此引入了折半查找算法对 本地服务上的信息进行查询匹配，因为顺序查找的复杂度为o ( n ) ，丽折半查我 的复杂度为o ( 1 0 9 n + 1 ) ，这又将查询效率提离了。 折半查找蕊过程： 先确定待查找记录所在的范围，然后逐步缩小范围或到找不到该记录为止。 两我们将折半查找算法用在服务器本地信息的查找，也就是善先确定了查找煞蔻 4 4 第四章c d i 3 中基于c h o r d 的改进的查询机制设计( t - c h o r d ) 围就在本地服务器，然后再进行折半查找。 我们设定三个指针b e g i n ，e n d 和m i d d l e ，令它们分别指向待查i d 范围的上界、 下界和中间位置，也就是m i d d l e = b e g i n + e n d 2 。当要查找的i d 定位到本地服务器 时，我们就将要查找的值i d c 与指针m i d d l e 所指向的值i d m 进行比较，如果i d c 5 6 ，则说明待查元素若存在，必在区间 m i d d l e + l ，e n d 】 的范围内，也就是必在7 和1 1 号i d 之间，此时b e g i n 和e n d 的值分别为7 和1 1 ， 它们对应的元素为6 4 和9 2 ，m i d d l e 的值此时为9 ，对应的元素为8 0 ，而8 5 8 0 ， 这说明要查找的i d 若存在，必在区间 m i d d l e + l ，h i g h l 范围内。此时令b e g i n 指向 第m i d d l e + 1 个元素，b e g i n = l o ，它所指向的值为8 8 ，然后比较i d = 8 5 与m i d d l e 当 前所指向的值8 8 ，此时8 5 5 4 第五章实现 5 2 3主动式c d i 3 机制的分组处理 配置服务器信息包 括i p 、p o r t 及c h o r d 。i d e n t i f i e r 所有信息： 从c o n ff i l e 巾获擞 二一! ：二 设置服务器的输入 和输 h 套接 。，- 。 至i 说明i d 不存小i 3 服务器 ；i ：，则利用c h o r d 查找i 的s t a t i s t i cf l a g + + 否 将分组转发给t r i g g e r 中对应的服务提供 者 将分组转发给t r i g g e r 中对应的服务提供者 否 发送针对i d 的服 务器请求分组 给集中式服务 器，收到分组 后存储并转发 给来源统计表 中的节点 本地有存储，则 直接将i d 对应的分 组发送给请求者； 发送针对i d 的服 务请求给上述集 中式服务器，收 到分组后存储， 将对应t r i g g e r 的s t o r a g ef l a g 位置1 ； 程序结束 图5 2 主动式c d i 3 机制流程图 5 5 电子科技大学硕士学位论文 5 2 4 增加及改进的主要数据结构： t y p e d e f s t n l c t c d i 3 _ t r i g g e r i d i d ： 书本t r i g g e r 的d i 3 一a d d r 卓t o ； 木和t r i g g e ri d 匹配的p a c k e t 将转发到的目的地址 u i n t 8 一t s t o r a g ef l a g ；幸服务i d 在i 3 服务器上对应的存储标志位； u i n t l 6 一t s e r v i e e s t a t i s t i c _ f l a g ；宰服务器本地服务对应t r i g g e r 的统计变量； u i n t l 6 一t n o d e s t a t i s t i e _ _ f l a g ；乖查询来源统计表中的统计变量； u i n t l 6tt t l s * i d 对应服务的生命周期 u i n t l 6 一t t t l n 宰节点统计查询来源的统计生命周期 u i n t 8 一tf l a g s ；幸可能的1 3 一t r i g g e r f l a g a l l o w s h o r t c u t 标志 u i n tl6 一t p r e f i x _ l e n ；幸p a c k e ti d 需要匹配t r i g g e ri d 的前m a x ( p r e f i x _ l e n ， m i np r e f i xl e n ) b i t s 或者更多丰 c d i 3 _ t r i g g e r s t r u c tr e q u e s t _ s o u r c e _ n o d e _ i t e m 查询来源统计表表项 i n ti ；产节点编号 i di d ；* 节点i d u i n t l 6 一t n o d e _ s t a t i s t c _ f l a g ；查询来源统计表中的统计变量 u i n t l 6 一t t t l n 节点统计查询来源的统计生命周期 ) ； s t r u c tn o d e 节点 读入关键字 f o r ( ；) 设定时间s t a b i l i z e _ w a i t ； s t a b i l i z e ( s e r v e r 母s r v ) ； 存储或转发接收到的数据 幸让节点n 查找i d 的后继节点母 1 1 f i n ds u c c e s s o r ( i d ) ； 产由本地f i n g e r 表查找离i d 最近的前驱节点吖 n c l o s e s t _ p r e e e d i n gn o d e ( i a ) ； 6 0 第五章实现 5 3 2c h o r d 机制的流程 配置服务器信息，包括 i p 、p o r t i a c h o r di d e n t i f i e r ，所 有信息从c o n f _ f i l e d p 获取 事 设置服务器的输入和输出套l 接字，i n i t i a l i z e ( s e r v e r + s r v ) i f 划定需要更新指针列表的节点i d 范围，c h o r d _ u p d a t e _ r a n g e ( c h o r d l d + l ，c h o r d l d + r ) r 设定下次执行s t a b i l i z e 函数的时i 间，s e t s t a b i l i z e _ t i m e r ( v o i d ) 专 判断指针表里是否有节点 无效，p i n g ( s e n ，c r * s r v ) i ， 更新后继列表和前驱列表的表 项，f i xs u c c s _ p r e d s ( s e r v e r + s l y ) 专 更新一个指针列表表 项，f i x _ f i n g e r s ( s e r v e r4 s i y ) v 将指针表中的所有无效表项清 除，c l e a n _ f i n g e r l i s t ( s e r v e r + s r v ) 检查服务器节点的指针表是否为 空，s t a b i l i z e ( s e r v e r + s n ，) 从文件+ c o n ff i l e d p 得到所有其他主机的网络地 址和端口地址j o i n ( s e r v e r * s r v 。f i l e * f p ) 读入关键字 让节点n 查找i d 的后继节点， n f i n d _ s u c c e s s o r ( i d ) ： 由本地f i n g e r 3 良查找离i d 最近的前驱节点 n c l o s e s t _ p r e c e d i n g _ n o d e ( i m ； 图5 3c h o r d 机制的实现流程图 可以看出，上述c h o r d 协议体系结构框架只包含了c h o r d 协议中的控制和管理 6 1 电子科技大学硕士学位论文 部分，而并不包含查找算法。说明在c h o r d 协议体系中最关键的工作实际上是对表 项的维护工作。至于查找算法，其核心部分即找到最近前驱的过程，已在本节开 始介绍过。 5 4t - c h o r d 机制实现 5 4 1原理描述： 根据c d i 3 中对i d 的分类，我们为每一类i d 设计了一个c h o r d 环，也就是说 t c h o r d 是由三个平行的c h o r d 环组成的。每一类i d 有一个独立的c h o r d 环。 由于原来由一个c h o r d 环来完成的查询和存储t r i g g e r 的工作现在由三个c h o r d 环来完成，每个c h o r d 环对应的查询后继节点的f i n g e r 表的长度就变小了，这样也 就较好的提高了c h o r d 的查询效率，同时在节点内部进行i d 的匹配时，我们采用 折半查找算法进行查询，这样在c d i 3 服务器节点负责的i d 的数量巨大的情况下