未来网络的服务命名机制与寻址方法研究(编辑修改稿)

未来网络的服务命名机制与寻址方法研究(编辑修改稿)内容摘要：

之后的分段哈希处理做了详细的叙述，对所用到的哈希函数位数的合理性和哈希之后的冲突率通过数学方法进行验证。 第四章：寻址部分，提出了未来网络体系结构，提出了一种新的路由算法。 第五章：对改进后的路由算法进行验证，使用实验平台对路由算法进行了功能和性能测试，最后分析了测试结果。 第六章：总结了本文所做的工作，提出了下一步的研究开发方向。 重庆邮电大学硕士论文 关键技术介绍第二章 关键技术介绍 哈希算法介绍本文中对服务的名字定义后需要通过哈希函数来对服务名字进行分段处理，以便进行存储和查找，通过分段哈希也大大降低了哈希后的冲突率。 通过哈希处理后的服务名字具有区域唯一性，在查找时，不需要进行任何对比，可以一次性找到所需要的服务所对应的地址，使对服务地址的查找更加高效。 哈希算法定义哈希算法也称为散列算法，是通过关键字（key值）来进行访问的一种数据结构，具有高效匹配特性。 Hash函数定义：Hash函数是一个将任意长度的消息（message）映射成固定长度消息的函数。 ，关键字（v1，v2，…v8）通过哈希函数H（v.）生成哈希值（H（v1），H（v2）…H（v8）），这个过程就是一个哈希过程。 哈希的结果是一个哈希列表，是关键字通过哈希函数处理后得到哈希值的一个对应关系表，在理想情况下，关键字与哈希值是一个一一对应关系，不会存在重复的情况，所以读取时一次就可以成功读取到想要的数据，哈希之后的散列表中可以进行直接寻址，可以在O（1）的时间内访问表中任意元素。 当采用合适的哈希函数时，生成的哈希值与关键字是一对一的关系，没有重复的哈希值，这样的哈希函数成为完美哈希。 但是实际应用中，由于选取哈希函数的不同，得到的哈希值的空间大小也就不一样，就会造成不同的关键字通过哈希函数后得到相同的哈希值，就出现了冲突。 哈希函数实例冲突也称为哈希函数的碰撞，设x、x’是两个不同的消息，如果 h(x) = h(x’)则称x和x’是Hash函数h的一个（对）碰撞。 在对哈希函数的选用时也需要注意关键字空间的大小，要注意冲突率和哈希值空间大小的配合。 比如说关键字有64位，最大值就是2^64，一共需要对1000个这样的关键字进行哈希，如果选取64位的哈希函数的话，固然可以实现一一对应，使得冲突率为0，提高查找效率，但是也同时浪费了巨大的存储空间；若哈希函数位数选的过于小，又会造成大量的哈希值冲突，使得查询效率降低，所以需要根据关键字的位数来选择合适的哈希函数。 减少冲突需要注意的除了哈希函数的位数外还需要注意该哈希函数是否为均匀哈希函数。 若对于关键字集合中任一个关键字，经过哈希函数映像到地址集合中任何一个地址的概率是相等的，则此类哈希函数称之为均匀的哈希函数。 也就是说，使关键字经过焊锡函数得到一个“随机的地址”，以便使关键字的哈希地址均匀的分布在整个地址区间中，从而减少冲突。 常见的哈希函数构造法有：①直接定址法；②数字分析法；③平方去中法；④折叠法；⑤除留余数法。 而处理冲突的方法有：①开放地址法；②再哈希法；③链地址法；④建立一个公共溢出区。 在本文中，哈希函数的选取也是研究的一个重点，通过选取适当的哈希函数，尽可能的使冲突率降低到可以忽略不计的程度，所以本文并没有对采用怎样的冲突处理方法进行描述。 哈希函数的分类（1）单向Hash函数（oneway）给定一个Hash值y，如果寻找一个消息x，使得y=h (x)是计算上不可行的，则称h是单向Hash函数. （2）弱抗碰撞Hash函数（weakly collisionfree）任给一个消息x，如果寻找另一个不同的消息x’，使得h(x) =h(x’)是计算上不可行的，则称h是弱抗碰撞Hash函数. （3）强抗碰撞Hash函数 （strongly collisionfree）如果寻找两个不同的消息x和x’，使得h(x)=h(x’)是计算上不可行的，则称h是强抗碰撞Hash函数. 安全Hash函数h应具有以下性质：① 对任意的消息x，计算h(x)是容易的；② h是单向的；③ h是弱抗碰撞的，或是强抗碰撞的。 经典chord算法介绍Chord[10]环为第三代结构化P2P网络，是一个分布式系统，提供数据对象的缓存、查询、复制和存储等功能，作为分布式散列表，chord几乎具有最优的路由效率[11]。 Chord算法采用相容哈希函数对关键字和节点IP进行哈希，生成m位字符的标识符，哈希的结果都是尽可能的平均分布在chord环上。 在chord中每个关键字的路由信息都是保存在它的后继节点中，每个节点最多保存m条路由信息，称为finger表。 Chord查找路由过程中，每一个节点只需要知道它在chord环中的后继节点，环中每个节点的路由法则就是按照finger表来进行，每个节点的查找公式为：fingeri=n+2i1mod 2m, 1≤i≤m 如图，节点N8上的路由信息表，N8+2i1，1≤i≤m，当m=6时，节点N8上一共有6条路由信息，finger表第一列表示要查询的节点的范围，第二列则表示要查询的节点的信息在哪个具体的节点上。 图 （1） Chord查找实例例如，给出节点ID为54，则先在N8的finger表上，查询到N54是属于N8+32，N42以后的节点，则先通过m=6的最后一行找到N40的节点所在的后继节点N42，再在N42节点上比较N54和表中每个节点的大小来确定下一个查找节点是谁，直至查找到N54为止。 查找路线为N8—N42—N51—N56，节点N54的信息就存储在离N54最近的后继节点N56上。 在我们的寻址系统中，将每个节点处的内容索引抽象为K，V对，K是内容关键字的Hash摘要，即为服务名称的哈希值，K = Hash（服务名称）；V是存放服务内容的实际位置即为IP地址，V = IP，K，V =（hash（key），IP）。 关键字通过hash函数得到相应的hash值存储在它的后继节点上，在chord中的寻址也就是对服务IP地址的查找。 K，V对组成一张Hash表，因此该表存储了所有服务SID到服务位置的对应信息。 注意，这里存储的只是服务名字与服务所在地址的对应关系，并不是服务本身。 N1N48N16N32N8k vk v Vk v Vk v Vk v图 （2） Chord环中的K，V对 小结本章介绍了本文中用到的关键技术，哈希函数基本理论和经典chord算法的寻址原理，为后面介绍本文提出的命名规则和类chord算法改进算法奠下了基础。 重庆邮电大学硕士论文 寻址体系与算法研究第三章 未来网络服务命名方法（机制。 ） 课题分析互联网络上数据通信的实质是数据包的转发，这里就涉及到两个问题——对象和地址，转发的对象（who）、转发对象所在的地址（where）和转发的目的地址。 在互联网命名与寻址中一共涉及四个概念：名字、地址、路由以及寻址。 在网络中，用户所查找的资源的名字是相对不变的，因为一旦名字改变，也就说明这个服务消失或者有所变动，就不再是原先的服务了。 但是服务的地址是相对变化的，当服务经过迁移后，同一个服务可能同时存在于多个地方，也就出现了一个服务名字对应多个服务地址的现象。 而路由则是知道服务的地址后，怎么通过地址在网络中找到服务，通过服务名字找到服务所在的地址的过程称为寻址。 简单的说四者之间的关系就是，名字是你要找什么，地址是你在哪里可以找得到，路由是通过怎样的路径可以得到这个服务，通过检索服务名字从而得到服务地址的过程称为寻址。 本文中，按照身份位置相分离原则，提出服务身份的命名规则，服务所在的地址依旧采用IP地址，将服务名字通过分段哈希算法后得到域内唯一的哈希值，通过唯一的域内哈希值可以在服务注册中心处找到相对应的服务所在IP地址，通过提出新的路由算法，在域内或者域间快速找到目的地址。 身份标识与位置标识网络信息传输中需要知道被传输对象是什么以及服务所在地和传输的目的地在哪里，传输对象就是服务的身份标识，而服务所在地和传输的目的地就是位置标识。 其中，身份标识是网络区域内服务唯一的标识，具有区域唯一性和不变性。 位置标识是服务所在的位置，不具有唯一性。 身份标识一般就指服务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得到， 基于身份位置相分离的服务命名方法本文认同NDN[2]（Named Data Networking）思想，认为每一片服务都有自己的名字，并针对服务对服务的identity进行命名。 基于身份位置相分离，得到的服务名字和服务的位置是一种对应关系，有一个名字位置对（pair）， SID：locator。 这意味着，每一个服务ID至少有一个locator与之对应。 Locator只用于路由，而identifier只在应用层负责对服务身份的判断，不再与locator绑定用于路由。 将服务的identifier与locator分离，服务的identifier是不会随着服务迁移后的位置的变化而改变，通信不会发生中断可很好的解决移动性问题。 当基于身份位置相分离来介绍未来因特网架构，identifier必须满足一些要求。 以下是根据ITU[3]的提议总结的一些通常的要求：l 服务的名字可以与多个服务位置相关联并且不随位置变化而变化；l 服务的名字是在应用层；l 与服务名字有关的session不会因为服务位置的变动而中断；l 服务的名字在一个指定范围内是全球唯一的；用户对名字的关心问题[12]有三点不变性、可达性和可信性。 不变性是指不管服务迁移到任何地方，服务的名字始终唯一；可达性是指即使网络和服务失败名字的内容或者服务也达；可信性是指用户不考虑内容在哪儿，但是希望内容是可信的。 在未来网络架构中，服务命名基于以上设计原则和用户所关心的问题，提出名字由两部分组成，服务属性和服务提供商。 其中服务的属性是一个六元组，S = N、V、Ts、Te、P、M，分别由字母和数字组成。 服务属性六元组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 /… sina其中的XXXnews为服务的名字，后面接着是服务发布时间等，允许服务属性中的项为空值。 用户描述的服务名字与服务属性进行匹配，服务属性和提供商也通过分段哈希得到唯一标识符UID，从而对服务IP进行查找。 服务名称的哈希处理对于每一个服务都有一个唯一的标识，就像每个人都有自己唯一的指纹一样。 为了避免重复存储同一个服务，每当新发布一个服务时，新服务在服务注册表中就会有相应的记录，来表示这些已经发布的服务，但是若是在服务注册表中，直接以字符串的形式存储，既费内存又费查找时间，因为服务的ID字符串是不定长的。 若要存储200亿个服务信息本身至少需要2TB，即为两千GB的容量，而哈希表的存储效率一般只为50%，那也就是需要4TB以上的空间，并且就算把这些服务全部存储在计算机内存中，由于服务字符串长度的不固定，以字符串形式来进行查找就需要依次比对，以最长匹配原则来进行筛选，这样的效率会很低。 所以，本文使用Hash函数，将服务ID的每一部分随机的映射为一个64位二进制即8个字节的整数空间，服务的两段标识总共需要128位16字节的整数空间，这样大大的节省了存储服务信息所需要的存储空间，这128位二进制就相当于服务ID的指纹[4]。 并且，哈希函数能够保证数据的完整性和认证性。 当一个服务发布到该注册中心时，先在Hash表中查找是否有这个服务对应的服务ID指纹，来决定是否要发布这个服务。 对Hash之后的值查找的速度要比直接对字符串查找的速度快几倍到几十倍。 本文结合结构化P2P网络信息搜索方式来进行名字与位置关系搜索，利用chord[5]算法来实。