未来网络的服务命名机制与寻址方法研究.docx

分类号 TP393.4 密级 重庆邮电大学硕士学位论文 论文题目 未来网络的服务命名机制与寻址方法研究 英文题目 Research of the Future network service naming scheme and addressing 硕士研究生 贾 雯 轩 指导教师 赵国锋 教授 学科专业 测试测量技术及仪器 论文提交日期 论文答辩日期 论文评阅人 答辩委员会主席 年 月 日独 创 性 声 明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 重庆邮电大学 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名： 签字日期： 年 月 日学位论文版权使用授权书本学位论文作者完全了解 重庆邮电大学 有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权 重庆邮电大学 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后适用本授权书）学位论文作者签名： 导师签名：签字日期： 年 月 日 签字日期： 年 月 日重庆邮电大学硕士论文 摘要摘 要当前互联网路由系统面临着严峻的扩展性问题，产生这一问题的根源在于IP地址语义过载，即IP地址既充当节点身份标识又代表了节点的位置标识，同时也束缚了移动性的实现。因此，身份与位置分离机制被普遍认为是解决这些问题的可行方法。而现有的寻址系统多是采用分布式结构模型，一个设计较好的分布式系统能够有效的支持寻址系统的解析，提高解析效率。当前多种拓扑分布式系统中，最常用的是树形拓扑结构（如DNS）和扁平结构。这两种拓扑各有优缺点。树形结构最大的好处是分级管理，有良好的容错能力和很好的扩展性，但是根节点容易构成瓶颈，造成通信堵塞；而扁平形结构是采用集中相应服务请求，安全性问题相对比较容易解决，但是不易于实现访问分布。在本文架构中，基于身份与位置相分离的IP重定义原则，并且根据P2P中对等网络的思想，结合chord模型提出了一个服务身份位置相分离的类chord寻址模型架构。论文主要工作如下： 服务命名设计在身份位置相分离原则下对网络中服务进行命名定义，以服务名字六元组和服务提供商一起组成服务名字，再通过分段哈希得到域内唯一标识符，以便查询时能够很快的查找到相应的服务以及服务所对应的IP地址。 服务命名验证通过极值法对哈希函数的位数进行验证，通过数学方法对所选用的哈希函数的冲突率进行验证，结果证明本文中所选用的哈希函数完全能满足。 寻址架构设计本文合P2P中对等网络的思想，我们将每一个注册中心主节点都看作类似于P2P网络中的节点，彼此是相互对等的关系。这里我们采用改进后的chord算法来作为节点间的路由算法，通过仿真来实现寻址过程。 Chord算法改进对各种现有的chord改进算法研究后根据本文的未来网络架构的特点，结合二分法提出了折半查找算法。 寻址效率验证通过P2Psim对改进后的chord算法进行验证，通过节点数的增长来验证新算法的效率。本文遵循身份位置相分离原则，网络中的每一片服务都应有自己的名字为服务设计了命名规则，并结合chord模型设计出更符合未来网络的寻址模型，对其进行寻址效率验证。关键词：身份位置相分离 服务命名 chord模型 折半查找28重庆邮电大学硕士论文 AbstractAbstract重庆邮电大学硕士论文 目录目录摘 要IAbstractII目录I插图和附表清单I第一张 绪论II1.1 研究背景及意义II1.1.1 研究背景II1.1.2 研究意义III1.2 研究现状IV1.2.1 现有的命名规则IV1.2.2 现有的chord算法改进VI1.3 论文主要工作及贡献IX1.4 组织结构X第二章 关键技术介绍22.1哈希算法介绍22.1.1 哈希算法定义22.1.2 哈希函数的分类32.2 经典chord算法介绍42.3 小结5第三章 未来网络服务命名方法（机制？）63.1 课题分析63.2 身份标识与位置标识63.3 基于身份位置相分离的服务命名方法73.4 服务名称的哈希处理83.5 哈希服务ID所需位数验证93.6 Hash函数碰撞103.6.1 生日悖论推导103.6.2 生日悖论构造对Hash函数的攻击113.7 小结12第四章 寻址体系与寻址算法研究134.1 寻址课题分析134.2 寻址体系介绍144.2.1 经典寻址技术介绍144.2.2154.3 chord折半查找算法174.4 小结18第五章 P2psim实现路由过程195.1 仿真软件p2psim介绍195.2 仿真实现225.3 仿真结果分析225.4小结22第六章 总结与展望236.1 总结236.2 展望23参考文献24致谢27附录A：攻读硕士学位期间从事的科研工作及取得的研究成果28重庆邮电大学硕士论文 插图和附表清单插图和附表清单表2.2 Hiimap命名格式VI表Content of UID fields corresponding to different typesVI图 1.2.2（1） Full-chord中节点路由表VII图 1.2.2（2） Full-chord查询图VII图 1.2.2（3） 三阶chord 路由指针示意图VIII图 1.2.2（4） 双chord结构图VIII图2.1.1 哈希函数实例2图 2.2（1） Chord查找实例4图 2.2（2） Chord环中的对5表3.1 服务属性六元组7图3.4 服务名称哈希生成UID9图3.6 分别把消息m和M表示成r和R个变形的消息11图4.1(1) 服务发布到服务查找流程图13图 4.1(2)14图4.2.2（1） 注册中心的寻址结构图15图4.2.2(2) 服务查找过程16表4.1 DRMC管理中心每个节点的存储信息示意图16图 4.3 折半查找算法图17图 5.1 P2Psim中主要参数构成图20重庆邮电大学硕士论文 绪论第一张 绪论1.1 研究背景及意义1.1.1 研究背景传统的互联网是为工作在可信环境下的静态主机设计的，经过近40年的发展，在取得巨大成功的同时也逐渐暴露出其最初设计所存在的问题。另外，网络的使用已从主机为中心转向以数据检索和服务获取为主，互联网越来越扮演着服务分发平台的角色，这些服务往往分布在多个位置以获得更好的性能。同时，网络用户也更加关心如何获取服务而不是服务所处的位置。正因为新的需求、使用环境与最初互联网设计原则存在矛盾，致使当前网络架构面临严峻挑战移动性、多宿主、安全性及路由可扩展性1-2等方面缺乏很好的支持。针对这些挑战及问题，关于未来网络的研究项目正在积极开展，如美国的GENI3及FIND4计划，欧洲的FIRE5计划，以及亚洲的AKARI6（日本）和Future Internet Forum7（韩国）。目前，研究者们已普遍认为，产生问题的根源在于IP地址的语义过载，即IP地址既在网络层充当位置标识（locator）进行包转发及寻址目的主机，又用在传输层及上层协议标识终端（identifier）。因此，国际internet架构委员会IAB提出身份与位置分离（Locator/indentifier split）8-10 机制，即使用不同的命名空间来分别代表节点位置和标识以此来解决IP地址过载问题40，并被认为是解决上述问题的一种有希望的方案，随着研究的深入，该机制已逐渐成为未来网络路由架构的一项设计原则。现在国际上对未来网络主要由两大阵营，“革命式”1516和“演进式”。其中演进式主要还是依赖于IP地址寻址，大多数的演进式研究方式基本上都是在现有的OSI七层网络架构中增添或者整合新的层级，以一种不断打补丁的方式对当前网络进行“修补”，并没有从根本上对网络架构进行改动。其中以layered naming architecture (LNA) 1、TRIAD为代表。其中TRIAD是2000年斯坦福大学提出的支持名字路由的网络路由架构，在网络架构中新增了一个“内容层”，内容通过内容路由器进行选路，需要在现有的internet协议上增加新协议，增加协议后的路由器是同时支持内容路由和IP路由。当前的内容分发网络就采用的这种路由方式。而革命式的主要思路是打破原有的七层模型，定义新的数据包和传输介质，不再以IP为载体，可以从根本上解决IP语义重复问题，其中以Named Data Network(NDN)、SOA、Content Centric Networking（CCN）为代表。其中NDN是美国国家科学基金会2010年8月资助的一个未来网络项目，其基本思想是以服务名字代替IP地址，用户要想找到一个服务，就必须知道服务的名字，而不需要服务所在的地址（IP地址），重新设计数据包格式和OSI各层协议，替换整个IP架构。国内北京交通大学的张宏科教授领导的973项目“一体化可信网络与普适服务体系基础研究”也致力于未来网络的研究，同样采用身份未知相分离思想，提出了两层体系结构的未来网络模型41。他将网络的七层模型整合成了“网络层”和“服务层”，网络层着重于传输，服务层着重于应用。清华大学的吴建平教授也提出了可信任下一代互联网体系结构，该结构为分层模型，从基础设施、安全服务、可信应用三个层面解决互联网的可信任问题。无论是革命式或者演进式、国内或者国外，其研究基础大多都是以身份位置相分离的以服务为中心的未来网络进行设计。主流思想都是将网络中的主体由地址变为内容，因为用户对网络的需求是对网络上服务的需求，用户关心的是服务的内容而不是服务的位置，所以很有必要提出的是一种以服务为核心，面向服务的网络，将重点转移到服务的内容。1.1.2 研究意义互联网是信息社会的重要基础设施，物联网、云计算、社会网络等新型计算机模式的出现使得以计算机互联和资源共享为目的的设计互联网已经无法满足需求，对未来互联网的研究已经成为世界各国占领信息技术制高点、增强国际竞争力的战略性需求。国外从2005年起展开的对未来互联网领域的研究，如美国国家自然科学基金委2010年资助的NDN、MobilityFirst等对未来互联网体系结果的探索研究，以及GENI、FIRE、OpenFlow、JGN2+等对未来互联网实验床与实验机制等研究项目，目前已取得一系列的研究成果。从国家核心利益的角度来看，互联网直接影响到国家产业战略调整和经济增长方式的转变，节能减排以及成为其中首要考虑的关键指标。但互联网自身的能耗问题同样不容忽视。据统计，目前网络设备的使用引起每年高达6%的能源消耗，而整个信息通信产业设备的碳排量以及站到全世界排放量的2.5%，相当于航空运输业的排放量。高能耗下，互联网以往的高速发展将不可持续，节能环保应从网络结构和优化网络体系入手，需要从体系、技术等方面开发高效、节能的未来互联网。目前，美国处于互联网产业链的顶端，占据了从标准制定到设备研发再到应用模式创新等各方面的优势地位。是否尽早开展未来互联网领域的研究，将关系到我们能否在未来互联网的发展演进以及产业竞争格局中是否拥有先机和话语权，也关系到我们的信息技术水平是否可以支撑国家产业战略调整和经济增长方式的转变。本项目的实施，使得我们面向未来业务创新需求，深入探索革命性的未来互联网体系结构和机理，解决互联网可持续发展问题，使得互联网真正的作为信息社会可持续发展的可靠基础设施，在社会发展中发挥更大的作用，也将使我们在世界信息技术的竞争格局中占据优势。1.2 研究现状1.2.1 现有的命名规则当前的网络仅有两个命名空间1，DNS和IP地址，一个映射机制，DNS到IP的映射机制。IP地址同时代表位置（locator）和身份（identifier），使得IP语义超载，IP同时代表身份又代表位置的特性使得网络移动性和多宿主、流量工程等受到限制。当前网络是一个以IP为传输核心的架构，用户需要找到某个服务或者数据，必须要先DNS域名转化为IP，再进行寻址查找，一旦IP改变，传输就会中断，并没有一种对服务本身进行查找。但是用户并不关系服务在什么位置，与自己所在网络的远近，用户对服务的需求是对服务本身的需求。所以我们提出面向服务的命名机制，使得服务不再作为网络二等公民31和地址绑定，更好的有利于服务迁移。近年来也有许多科研机构在针对服务网络进行研究，提出新的命名机制，大多数主要是针对网络中的主机进行命名，或者在网络层中添加新的层，以达到IP身份位置相分离的目的。直接对网络中服务命名的很少。 如MILSA31,32,42,43中设计了一种新的HUI地址名字空间，HUI架构包括两部分：1、水平加密部分和2、层次逻辑部分。水平加密部分：是公钥的hash，唯一标志一个对象。水平部分类似于HIP的HIT，用于端到端身份鉴定和数据安全。同样也可以合并其他新的全球端到端机制。层级逻辑部分：定义组织间的从属关系，realm中对象的物理位置逻辑关系。这个和DNS不一样，在HUI中，是单指逻辑上的从属关系，但是在DNS中，位置和逻辑上的从属关系有时候会重叠，就像identifier和locator在当前IP地址中是重叠的一样。其不足之处在，在这两种情况下，会造成覆盖问题。更者，DNS名字只是用于应用层，而HUI同样用于传输层和网络层。伯克利加州大学提出的RoutingonFlatLabels（ROFL）19是一种扁平的命名机制，丢弃locator，使用标识完全取代地址在全网范围内的路由。支持移动性，多宿主和具有稳定的标识符。但是它没有新的基础架构和因特网命运共享（发送数据包之前，不需要联系解析设施，数据包的传输不依赖任何数据路径）；简单的分配（IP地址需要仔细的分配来保证唯一性和对新拓扑的粘合性，ROFL中只需要保证标识符的唯一性）；更适合接入控制（网络层次的接入控制，更大层次的是基于IP地址）。同样是伯克利加州大学提出的Internet Indirection Infrastructure（I3）20也是一种扁平的命名机制，给Identifier提供了全球唯一的新的扁平名字空间，增加了一种对于网络路由间接的方式，更好的支持多播，任播和移动性。Identifier到Locator的映射被称为Trigger，存储在覆盖服务中。但是这种trigger对移动性的支持是有限的，对于扩展性的支持也很有限。HIP21主要目标是解决主机移动和多宿主，提供基于加密主机标识的端节点身份认证机制和DoS攻击保护功能。HIP将位置(IP)与端节点标识相互分离，在传输层和网络层之间加入了主机标识层(host identity)，高层应用中，表示主机身份的IP地址被HIT（Host Identity Tag）替换，用HIT作为固定的主机标识符，应用层通信也基于HIT，IP地址仅仅用于路由转发而不再用来标识主机身份。主机标识是一个抽象概念，表示一个静态的全局唯一名字，在实际中使用的是主机标识符。在HIP DNS中，一个域名被首先映射为一组主机标识，主机标识再被映射为一组IP地址。不足：需要更新大量主机，只能支持IPv6，不支持流量工程和多播，增加了中间设备的复杂性。PeerNet25：把节点的身份标识和位置标识进行分离，避免IP地址同时拥有双重功能。但PeerNet是一个全新的网络层协议，它的目的是取代IP协议。PeerNet网络中的每个节点都有一个节点标识和一个地址标识。节点标识可靠地代表节点的身份，不随节点的移动而改变。地址标识则严格地反映节点在网络中的当前位置，当节点移动时，节点的地址标识随之动态改变。由于地址标识是完全层次化分配的，PeerNet中就可以运用P2P网络的路由思想来组织路由。 因此，PeerNet中实际上引入了两个新的全局名字空间，以取代现在的IP 地址空间。节点标识空间是全局的、非唯一分配的，但对节点标识空间的其他性质， PeerNet中并没有进行明确定义。地址标识空间是全局的、固定长度的、层次化结构的; 而且是唯一分配的，一个节点虽然可能负责管理多个地址，但只能使用反映当前网络拓扑位置的唯一地址标识; 如果把网络拓扑位置认为是网络层地址所表示的实体，则可以认为地址标识的分配是一次性的。 不足：很难保证P2P 路由表中的紧邻项也位于实际网络的紧邻位置，这对路由表的维护和路由效率都有影响; 其次，由于每个节点只能使用反映当前网络拓扑的唯一地址，PeerNet不能支持Multi-homing。FARA【27】：主机与主机之间的通信概念不再存在，取而代之的是实体与实体之间通过底层分组交换结构进行的连接。FARA中用不同的Association ID(AID) 来标识一个实体的多个不同连接，由于AID 只在每个实体上是唯一的，所以分组携带一个(源AID、目的AID)对。显然AID是一个局部名字空间，类似于现在传输层的端口号。FARA中的实体依赖于底层的分组交换结构来进行通信，包括操作系统和网络。FARA中用转发指示(for warding directive)作为分组交换结构的地址标识。在进行通信时，实体需要通过另外的机制找到目的实体的转发指示。不足：FARA中的通信实体并没有一个全局标识，需要带外的机制来寻找通信实体的位置，这在实际应用中并不容易做到。而且对于如何进行移动切换、保证通信安全等许多问题，FARA中并没有具体的实现机制。SHIM6【26】：主要关注流量工程，提供了基于主机的多宿主机制。没有引入新的地址空间，locator和identifier均使用IPv6地址空间，将IPv6的高64位作为路由 locator，低64位作为identifier。SHIM6采用了基于主机的方式，可以根据链路状态动态选择locator，并实现了对多播的支持。机制过于复杂，需要更新大量的主机，仅支持IPv6地址。HRA【29】：层次式的标识，采用层次路由机制解决路由可扩展性问题。该体系结构基于位置与标识分离的思想。HRA中的每个主机都有一个HI(host identifier)和一个HIT(host identity tag)。其中，HIT是HI的hash值与AD ID(administrative domain ID)的结合。这种层次结构的标识空间，能够体现主机的归属区域，同时保证安全性和唯一性，改善了映射系统的查询效率。此外，提出基于LD的路由和基于地址前缀的路由相结合的层次路由机制。在LD之间进行报文转发时使用基于LD的路由机制，在LD内部使用基于地址前缀的路由机制。HRA为下一代多层互联网设计了一个通用的架构，但是为了支持IPv6需要改变主机和边缘路由器。德国慕尼黑技术大学提出了一种基于身份位置相分离的命名规则，Hiimap30的，这个规则不仅是针对网络中的服务，而是一个通用式，如图所示，一共由五部分组成，其中RP代表区域的前缀，剩下四部分为UID，UID定长为128bit，分别由4位的类型号，76位的服务名字哈希值，32位的Ext1和16位的Ext2组成。RPTHash（name）Ext1Ext2UID 表2.2 Hiimap命名格式其中每一部分的具体内容如下表：TypeInput to hash（name）Ext1Ext2Static hostNon-static hostContentPersonPlain text domain nameGlobal prefix assigned by providePlain text content nameFirst + last nameHash of local hostnameHash of local hostnameChild contentRandomServiceServiceVersion numberCommunication channel表Content of UID fields corresponding to different types1.2.2 现有的chord算法改进在本文寻址系统中，主要采用chord模型来作为服务注册中心之间的路由模型，当前对chord算法的研究已经非常多，在经典chord寻址模型上提出了很多改进算法，如下：（1）full-chordChord中查询路由信息，只能从顺时针方向查询，找到被查询节点路由表中值最大的节点，再查询该最大节点的路由表中是否包含目的节点值，直到找到目的节点为止。如果目的节点比较大，存在于chord环的后半段，这样顺时针查询很花费时间和资源。Full-chord23的提出使得每个节点的路由信息都包含了两个路由表，分别是正向的路由表和逆向的路由表。使得路由信息的查询可以逆向查询，使得环中的每个节点的finger表都包含有整个环中的某些节点的信息，这样第一步就可以将查询范围限制在半个环中。finger1i=n+2i-1mod 2m, 1im (1)finger2i=n-2i-1mod 2m, 1im (2)公式(1)是经典chord顺时查找的公式，公式（2）是full-chord中逆向查找公式。图 2.5.1（1）是full-chord的节点路由表。相比经典chord full-chord中一个节点包含了两倍的路由信息， 并且同时包含正向和反向路由，使得如果需要正向跳转多次的路径，可以通过反向路由跳转1、2次即可到达。图 1.2.2（1） Full-chord中节点路由表例如从N8节点想要查找到key值等于54的后继节点，在full-chord中从N8点可以直接通过公式(2)找到离54最近的节点为N51，再通过N51的后继节点找到存储有54的节点N56。这样就比顺时的从N8找到正向表中最大的N42，再从N42顺时查找节省了很多时间和带宽。图 1.2.2（2） Full-chord查询图2） 高阶chord经典chord算法中，chord中的节点将chord环不断的2等分，使得每个节点维护的路由表长度为m，而高阶chord28将chord环不断的K等分，使得chord环中每个节点处的指针更加密集，提高在chord上的查询效率。三阶chord路由表公式为：ID+3k-1mod N 1 kmID+2*3k-1mod N 1 km三阶chord的路由表指针模型为：图 1.2.2（3） 三阶chord 路由指针示意图由上图可以看出，三阶chord是将chord环不断的三等分，相比经典chord的二等分使指针更加紧密，查找速度更快。（3） 双chord在双层chord模型26中，主要分为主干层和子网层，每一层都是基于chord模型来进行查询和定位资源。在双层chord中，存储信息被哈希为一个64为的标识符，其高32位表示该信息在主干网上的位置，低32位表示在子网层中的位置。主干层和子网层由超级节点连接，超级节点即是子网层中的一个普通节点，同时也是向主干层发起查询请求的节点。图 1.2.2（4） 双chord结构图查询时由查询节点从本地的子网层从开始按chord环顺序查找，如果查询失败，就将查询请求转交给超级节点，由超级节点在主干层中发起查询请求，找到相应的子网后再进行查找。当前对chord算法的改进主要是单纯的对算法本身的改进，改进过后的chord算法仍需要在每个节点处对自己的finger表进行查找匹配，并没有完全跳出经典chord算法的思维模式，本文中的chord算法改进后，已经不存在finger表，每个节点不光是chord环中的转发节点，而是一个服务注册中心，存储有服务ID和服务所在IP地址的对应信息，这部分在第四章有详细的介绍。1.3 论文主要工作及贡献整个未来网络体系结构以及机理是由一个团队共同进行研究，本文主要研究其中的服务命名机制以及寻址研究。本文在未来网络发展的大背景下，了解国内外研究现状，分析比较了各种新型未来网络架构的优势与劣势，在以身份位置相分离的前提下，提出了以服务为中心的网络结构。在本文架构中，基于身份与位置相分离的IP重定义原则，并且根据P2P中对等网络的思想，结合chord模型提出了一个服务身份位置相分离的类chord寻址模型架构和新的路由算法。论文主要工作如下： 服务命名设计在身份位置相分离原则下对网络中服务进行命名定义，以服务名2314662002字六元组和服务提供商一起组成服务名字，再通过分段哈希得到域内唯一标识符，以便查询时能够很快的查找到相应的服务以及服务所对应的IP地址。 服务命名验证通过极值法对哈希函数的位数进行验证，通过数学方法对所选用的哈希函数的冲突率进行验证，结果证明本文中所选用的哈希函数完全能满足。 寻址架构设计本文合P2P中对等网络的思想，我们将每一个注册中心主节点都看作类似于P2P网络中的节点，彼此是相互对等的关系。这里我们采用DHT模型中的chord模型来仿真节点间的选择寻路过程。 Chord算法改进对各种现有的chord改进算法研究后根据本文的未来网络架构的特点，结合二分法提出了折半查找算法。 寻址效率验证通过P2Psim对改进后的chord算法进行验证，通过节点数的增长来验证新算法的效率。本文遵循身份位置相分离原则，网络中的每一片服务都应有自己的名字为服务设计了命名规则，并结合chord模型设计出更符合未来网络的寻址模型，对其进行寻址效率验证。1.4 组织结构本论文组织结构如下：第一章：绪论，阐述论文的选题背景，研究现状，主要工作以及论文的组织结构。 第二章：对未来网络服务命名以及寻址机制的现状做了简要的描述。第三章：命名部分，提出了新的基于身份位置相分离的未来网络服务命名机制，以及对命名之后的分段哈希处理做了详细的叙述，对所用到的哈希函数位数的合理性和哈希之后的冲突率通过数学方法进行验证。第四章：寻址部分，提出了未来网络体系结构，提出了一种新的路由算法。第五章：对改进后的路由算法进行验证，使用实验平台对路由算法进行了功能和性能测试，最后分析了测试结果。第六章：总结了本文所做的工作，提出了下一步的研究开发方向。重庆邮电大学硕士论文 关键技术介绍第二章 关键技术介绍2.1 哈希算法介绍本文中对服务的名字定义后需要通过哈希函数来对服务名字进行分段处理，以便进行存储和查找，通过分段哈希也大大降低了哈希后的冲突率。通过哈希处理后的服务名字具有区域唯一性，在查找时，不需要进行任何对比，可以一次性找到所需要的服务所对应的地址，使对服务地址的查找更加高效。2.1.1 哈希算法定义哈希算法也称为散列算法，是通过关键字（key值）来进行访问的一种数据结构，具有高效匹配特性。Hash函数定义：Hash函数是一个将任意长度的消息（message）映射成固定长度消息的函数。如图2.1中，关键字（v1，v2，v8）通过哈希函数H（v.）生成哈希值（H（v1），H（v2）H（v8），这个过程就是一个哈希过程。哈希的结果是一个哈希列表，是关键字通过哈希函数处理后得到哈希值的一个对应关系表，在理想情况下，关键字与哈希值是一个一一对应关系，不会存在重复的情况，所以读取时一次就可以成功读取到想要的数据，哈希之后的散列表中可以进行直接寻址，可以在O（1）的时间内访问表中任意元素。当采用合适的哈希函数时，生成的哈希值与关键字是一对一的关系，没有重复的哈希值，这样的哈希函数成为完美哈希。但是实际应用中，由于选取哈希函数的不同，得到的哈希值的空间大小也就不一样，就会造成不同的关键字通过哈希函数后得到相同的哈希值，就出现了冲突。图2.1.1 哈希函数实例冲突也称为哈希函数的碰撞，设x、x是两个不同的消息，如果 h(x) = h(x)则称x和x是Hash函数h的一个（对）碰撞。在对哈希函数的选用时也需要注意关键字空间的大小，要注意冲突率和哈希值空间大小的配合。比如说关键字有64位，最大值就是264，一共需要对1000个这样的关键字进行哈希，如果选取64位的哈希函数的话，固然可以实现一一对应，使得冲突率为0，提高查找效率，但是也同时浪费了巨大的存储空间；若哈希函数位数选的过于小，又会造成大量的哈希值冲突，使得查询效率降低，所以需要根据关键字的位数来选择合适的哈希函数。减少冲突需要注意的除了哈希函数的位数外还需要注意该哈希函数是否为均匀哈希函数。若对于关键字集合中任一个关键字，经过哈希函数映像到地址集合中任何一个地址的概率是相等的，则此类哈希函数称之为均匀的哈希函数。也就是说，使关键字经过焊锡函数得到一个“随机的地址”，以便使关键字的哈希地址均匀的分布在整个地址区间中，从而减少冲突。常见的哈希函数构造法有：直接定址法；数字分析法；平方去中法；折叠法；除留余数法。而处理冲突的方法有：开放地址法；再哈希法；链地址法；建立一个公共溢出区。在本文中，哈希函数的选取也是研究的一个重点，通过选取适当的哈希函数，尽可能的使冲突率降低到可以忽略不计的程度，所以本文并没有对采用怎样的冲突处理方法进行描述。2.1.2 哈希函数的分类（1）单向Hash函数（one-way）给定一个Hash值y，如果寻找一个消息x，使得y=h (x)是计算上不可行的，则称h是单向Hash函数. （2）弱抗碰撞Hash函数（weakly collision-free）任给一个消息x，如果寻找另一个不同的消息x，使得h(x) =h(x)是计算上不可行的，则称h是弱抗碰撞Hash函数. （3）强抗碰撞Hash函数 （strongly collision-free）如果寻找两个不同的消息x和x，使得h(x)=h(x)是计算上不可行的，则称h是强抗碰撞Hash函数. 安全Hash函数h应具有以下性质： 对任意的消息x，计算h(x)是容易的； h是单向的； h是弱抗碰撞的，或是强抗碰撞的。2.2 经典chord算法介绍Chord10环为第三代结构化P2P网络，是一个分布式系统，提供数据对象的缓存、查询、复制和存储等功能，作为分布式散列表，chord几乎具有最优的路由效率11。Chord算法采用相容哈希函数对关键字和节点IP进行哈希，生成m位字符的标识符，哈希的结果都是尽可能的平均分布在chord环上。在chord中每个关键字的路由信息都是保存在它的后继节点中，每个节点最多保存m条路由信息，称为finger表。Chord查找路由过程中，每一个节点只需要知道它在chord环中的后继节点，环中每个节点的路由法则就是按照finger表来进行，每个节点的查找公式为：fingeri=n+2i-1mod 2m, 1im 如图，节点N8上的路由信息表，N8+2i-1，1im，当m=6时，节点N8上一共有6条路由信息，finger表第一列表示要查询的节点的范围，第二列则表示要查询的节点的信息在哪个具体的节点上。图 2.2（1） Chord查找实例例如，给出节点ID为54，则先在N8的finger表上，查询到N54是属于N8+32，N42以后的节点，则先通过m=6的最后一行找到N40的节点所在的后继节点N42，再在N42节点上比较N54和表中每个节点的大小来确定下一个查找节点是谁，直至查找到N54为止。查找路线为N8N42N51N56，节点N54的信息就存储在离N54最近的后继节点N56上。在我们的寻址系统中，将每个节点处的内容索引抽象为对，K是内容关键字的Hash摘要，即为服务名称的哈希值，K = Hash（服务名称）；V是存放服务内容的实际位置即为IP地址，V = IP， =（hash（key），IP）。关键字通过hash函数得到相应的hash值存储在它的后继节点上，在chord中的寻址也就是对服务IP地址的查找。对组成一张Hash表，因此该表存储了所有服务SID到服务位置的对应信息。注意，这里存储的只是服务名字与服务所在地址的对应关系，并不是服务本身。N1N48N16N32N8k vk v Vk v Vk v Vk v图 2.2（2） Chord环中的对2.3 小结本章介绍了本文中用到的关键技术，哈希函数基本理论和经典chord算法的寻址原理，为后面介绍本文提出的命名规则和类chord算法改进算法奠下了基础。重庆邮电大学硕士论文 寻址体系与算法研究第三章 未来网络服务命名方法（机制？）3.1 课题分析互联网络上数据通信的实质是数据包的转发，这里就涉及到两个问题对象和地址，转发的对象（who）、转发对象所在的地址（where）和转发的目的地址。在互联网命名与寻址中一共涉及四个概念：名字、地址、路由以及寻址。在网络中，用户所查找的资源的名字是相对不变的，因为一旦名字改变，也就说明这个服务消失或者有所变动，就不再是原先的服务了。但是服务的地址是相对变化的，当服务经过迁移后，同一个服务可能同时存在于多个地方，也就出现了一个服务名字对应多个服务地址的现象。而路由则是知道服务的地址后，怎么通过地址在网络中找到服务，通过服务名字找到服务所在的地址的过程称为寻址。简单的说四者之间的关系就是，名字是你要找什么，地址是你在哪里可以找得到，路由是通过怎样的路径可以得到这个服务，通过检索服务名字从而得到服务地址的过程称为寻址。本文中，按照身份位置相分离原则，提出服务身份的命名规则，服务所在的地址依旧采用IP地址，将服务名字通过分段哈希算法后得到域内唯一的哈希值，通过唯一的域内哈希值可以在服务注册中心处找到相对应的服务所在IP地址，通过提出新的路由算法，在域内或者域间快速找到目的地址。3.2 身份标识与位置标识网络信息传输中需要知道被传输对象是什么以及服务所在地和传输的目的地在哪里，传输对象就是服务的身份标识，而服务所在地和传输的目的地就是位置标识。其中，身份标识是网络区域内服务唯一的标识，具有区域唯一性和不变性。位置标识是服务所在的位置，不具有唯一性。身份标识一般就指服务ID，可以通过对服务的名称、属性、操作及服务提供者等信息进行hash获得，由于服务迁移，服务ID与位置标识可能存在一对多的映射关系。而位置标识一般指服务所在的IP地址，可以通过对服务IP进行hash获得，代表节点或服务在网络拓扑中的位置。（1）身份标识（ID）ID（Identifier）是网络域内服务的唯一标识，服务的ID一旦产生或被分配，将不会改变且长期有效。服务ID主要用于应用层及传输层，即时的、端到端、可迁移的场景，如服务的分布式存储，同时服务ID与服务所在位置可能是一对多的映射关系，服务ID可以通过对服务的名称、属性、操作及服务提供者等信息进行hash获得。（2）位置标识（locator）位置标识（Locator）主要是指服务所在的IP地址，多数情况下，位置标识是不可变的，但是由于服务进过服务迁移会存在于多个位置上，所以一般而言，服务ID一般对于多个位置标识，但一个位置标识只对应于一个服务ID。节点ID与节点位置是一一对应映射关系，节点ID可以通过对节点IP地址进行hash得到，3.3 基于身份位置相分离的服务命名方法本文认同NDN2（Named Data Networking）思想，认为每一片服务都有自己的名字，并针对服务对服务的identity进行命名。基于身份位置相分离，得到的服务名字和服务的位置是一种对应关系，有一个名字位置对（pair）， SID：locator。这意味着，每一个服务ID至少有一个locator与之对应。Locator只用于路由，而identifier只在应用层负责对服务身份的判断，不再与locator绑定用于路由。将服务的identifier与locator分离，服务的identifier是不会随着服务迁移后的位置的变化而改变，通信不会发生中断可很好的解决移动性问题。当基于身份位置相分离来介绍未来因特网架构，identifier必须满足一些要求。以下是根据ITU3的提议总结的一些通常的要求：l 服务的名字可以与多个服务位置相关联并且不随位置变化而变化；l 服务的名字是在应用层；l 与服务名字有关的session不会因为服务位置的变动而中断；l 服务的名字在一个指定范围内是全球唯一的；用户对名字的关心问题12有三点不变性、可达性和可信性。不变性是指不管服务迁移到任何地方，服务的名字始终唯一；可达性是指即使网络和服务失败名字的内容或者服务也达；可信性是指用户不考虑内容在哪儿，但是希望内容是可信的。在未来网络架构中，服务命名基于以上设计原则和用户所关心的问题，提出名字由两部分组成，服务属性和服务提供商。其中服务的属性是一个六元组，S = ，分别由字母和数字组成。表3.1 服务属性六元组N为服务的名字，是对服务的描述性名字，不需要唯一，可以同一个名字对应多个服务，也可以一个服务对应多个描述名字；V为服务的版本号；Ts为服务发布时间；Te为服务的有效时间，在这个时间内服务是可用的，过了有效时间，则需要重新发布或者更新服务；P为服务的私有性，表示该服务是否属于私有，是否允许访问；M表示是否允许迁移，因为有些服务虽然不是私有，但是也不允许迁移，所以需要将私有性和可迁移性区别对待。这些属性都是由服务提供商来确定的，在这里统称为服务属性。在服务名字中，因特网服务提供商（SISP）由字母和数字组成。服务提供商最终被Hash为一个64位的数。服务属性也同样是被分段Hash为一个64位的值。这两部分的64位值再组合，就得到了最终的128位的UID（unique identifier），这是一个全球唯一的服务ID，保证了服务SID的全球唯一性。Nname和SISP之间的关系为，一个SISP可以提供多个Nname，一个Nname也可以是由多个SISP提供的。例子： XXXnews /2.0/ 2011.4/describe/ #sina其中的XXXnews为服务的名字，2.0为版本号，后面接着是服务发布时间等，允许服务属性中的项为空值。用户描述的服务名字与服务属性进行匹配，服务属性和提供商也通过分段哈希得到唯一标识符UID，从而对服务IP进行查找。3.4 服务名称的哈希处理对于每一个服务都有一个唯一的标识，就像每个人都有自己唯一的指纹一样。为了避免重复存储同一个服务，每当新发布一个服务时，新服务在服务注册表中就会有相应的记录，来表示这些已经发布的服务，但是若是在服务注册表中，直接以字符串的形式存储，既费内存又费查找时间，因为服务的ID字符串是不定长的。若要存储200亿个服务信息本身至少需要2TB，即为两千GB的容量，而哈希表的存储效率一般只为50%，那也就是需要4TB以上的空间，并且就算把这些服务全部存储在计算机内存中，由于服务字符串长度的不固定，以字符串形式来进行查找就需要依次比