查找的处理课件

1、2022/7/241Paper critiques2022/7/242广域网系统中的对象定位(1998)本文提出了一种新的在广域网系统中定位移动对象的方案主要思想：分离对象名字与对象地址，引入一个中间层：对象句柄，两层解析对象名字与对象句柄绑定（名字服务），再由对象句柄映射到对象的地址（定位服务）本文重点：由对象句柄到对象地址的映射（定位服务）2022/7/243简介网络的变化趋势：对象数量增加移动对象（硬件或软件）支持移动对象对网络的要求：客户机可以在完全不知道对象当前位置的情况下联系到这个对象对象的位置的变化对于客户机来说是透明的传统的名字服务： 维护对象名字和对象的地址（一个或多个）之间

2、的绑定。对于移动对象，对象名字应该被解析到当前地址上（关键：映射要随对象地址的改变而改变） 2022/7/244简介挑战:当对象地址很少改变，世界范围的可扩展的名字服务较易实现DNS ，X.500 Directory Service对象地址改变频繁时，问题复杂性显著增加本文提出了一种提供灵活的名字-地址绑定的定位服务系统目标：支持一个全球范围内的面向对象分布式系统，系统规模达到 1 亿用户每个拥有上千个对象2022/7/245名字到地址的绑定名字里是否要包含地址信息？利于解析不利于处理对象的移动（对象地址改变引起名字的变化）问题的解决本文提出的两级分层命名机制名字服务：对象名字到对象句柄的映射

3、定位服务：对象句柄到对象地址（可能有多个）的映射意义：对象名和地址可以独立的改变通过对象句柄（唯一的与地址无关的）联系起来，对象名字与对象地址完全的分离开来2022/7/246名字到地址的绑定定位服务与命名无关，主要设计用来支持频繁的联系地址更新和查找操作Anycast:分布式系统中的一种定位服务的方式客户机只请求特定的服务，而不在意服务由那个对象来处理。本系统实现的就是Anycast,服务被分配一个句柄，实现此服务的服务器在这个句柄下注册自己的网络地址，客户机的服务请求被解析到这个服务的对象句柄，然后被解析到任意一个可以处理此服务的服务器上。2022/7/247名字到地址的绑定对定位服务的要

4、求扩展性： 1012个对象就近性 ?（Locality):系统确定路由时应该就近（不走冤枉路）比如如果所请求对象与客户机距离很近，那么应该很容易找到这个对象稳定性：对于稳定（在某个区域内）的对象处理应该简单一些容错性：从结点，连接错误中恢复，出现网络分割时能继续操作2022/7/248分布对象的跟踪本文提出的全球的可扩展定位服务的体系结构（框架）模型整个网络分成若干层次区域区域：每个区域对应一个目录结点目录结点：存储相应区域内的地址（地址是依赖与位置的）构成一个逻辑上的树型结构2022/7/249分布对象的跟踪插入新地址：新地址通常插入到地址所在区域的叶结点上新对象建立一条从根到其所在位置的指

5、针链这些指针以及对象实际地址存贮在联系记录中未注册对象的插入请求从叶结点自下而上传递，传递过程中一路上生成链接（到下层）指针已注册的对象的插入请求只在不重复的部分建立新指针2022/7/2410分布对象的跟踪删除联系地址先由地址找到地址所在区域（地址中是包含所在区域信息的）从代表这个区域的叶结点开始向上查找直到找到这个地址为止，删除之如果删除联系地址后这个联系记录内不再有联系地址或指针就删除这个联系记录如果删除了联系记录还要向上检查它的祖先看是否需要删除2022/7/2411分布对象的跟踪查找联系地址客户机进程把所请求对象的句柄传到自身所在区域的叶结点上从这个叶结点向上搜索直到第一个发现有请求

6、对象的目录结点从这个目录结点向下找到请求对象的地址把这个地址传递给请求者一致性规则对同一个叶结点的更新请求按请求顺序执行对不同叶结点的更新请求执行顺序随意2022/7/2412分布对象的跟踪动态优化（提高查找速度,减少更新负担）指针缓存使用指针缓存要求对象地址存放位置稳定缺省时对象地址保存在叶结点联系记录中，当对象的位置有规律的一定的区域内改变，可以直接把对象的地址保存在区域的目录结点的联系记录中（例）这样就可以把指向稳定的目录结点的指针缓存起来2022/7/2413分布对象的跟踪扩展性前面给出的搜索树模型扩展性并不好，随着对象的增加，高层结点要处理大量的请求，存储大量的数据。解决方法：分裂目

7、录结点每个目录结点分裂出的子结点负责原来目录结点上存储的记录的一个子集一个分裂目录结点的例子2022/7/2414相关工作针对不同类别的移动对象（移动硬件，移动软件）不同的特点，已经提出了不同的服务定位方法。2022/7/2415相关工作移动硬件：往往随着使用者的移动而移动移动速度：不超过人的最大移动速度因而可以采用这种策略：其中数据结构随着对象的移动而变化（不需要很快的处理位置变化）几个定位服务成功的利用这个特点提出了自己的模型一个对象同一时刻只有一个地址不必处理一个对象多地址的情况本文提出的模型没有利用这两个特点，因为这个模型还要致力于处理移动软件对象2022/7/2416相关工作移动软件

8、对象一个主机上有多个对象（数量巨大,扩展性问题不容忽视）针对对象的移动模式使用指针链跟踪对象，需要时缩短长指针链，其它方法失效时使用广播（不适合大型系统）-Emerald系统依赖于一个全球名字服务，假定更新/查找的值很小-LII（Location Independent Invocation)本文系统目标：广域系统，对象移动频繁（大量更新）2022/7/2417相关工作SSP链：(似乎是一种适用于大型系统的可行方案)思路:对象引用可以在进程之间透明的移交,代价是同时生成指向这个对象的指针链缺点:完全不能利用就近性( Locality)缺少对容错性的支持结论:SSP链不适合扩展到世界范围的大型系

9、统2022/7/2418结论一种新的在广域网中定位对象的方法，使用与位置无关的对象句柄而不是用户定义的名字2022/7/2419一个INS的设计与实现本文主要贡献:设计和实现了一个INS(Intentional Naming System),用于动态的移动设备和计算机网络中的资源发现和服务定位何谓Intentional:分布式网络中应用往往不知道满足其需求的最优网络资源的位置Intentional命名机制和解析方法:应用表达自己的意愿:要什么而不是在哪得到由名字解析器维护服务描述与其网络位置的映射,负责把请求传递到最适合的位置2022/7/2420简介未来的网络环境:大量移动无线设备出现网络环

10、境的动态特性移动网络中的消息包路由问题已经得到了较好的解决资源发现和服务定位2022/7/2421简介实现动态资源发现和服务定位的名字系统的设计目标表达力:处理大量设备和服务,表达任意的服务描述和查询响应度:迅速感知对网络中服务的网络定位有影响的服务和结点的移动,性能波动以及其它因素鲁棒性:能从名字解析器或服务的失败,以及解析器之间的内部不一致中恢复易配置:解析器应该尽量自动配置少手工干涉,服务应不需手工注册,系统应自动在解析器之间分配解析负载2022/7/2422系统结构INR:形成一个应用级网络用来交换服务描述,建立本地CACHE服务:与INR联系,报告基于属性-值对的服务描述客户端:使用

11、一个查询表达式向INR请求服务 INS结构图示2022/7/2423系统结构绑定: 客户端消息到达INR时,INR根据客户端的请求决定是完成解析还是转发 早绑定:解析器直接返回一个IP地址列表(类似与DNS和现存的名字发现系统),这种情况适用于相对稳定的服务,客户机从中选择一个迟绑定:INR不直接返回IP地址而是转发名字和应用负载(Intentional Anycast):选择一个来转发(根据:metric)(Intentional Multicast):转发到所有与这个名字相关的INR(最终消息发送到所有与这个名字一致的目标接点)2022/7/2424系统结构INR网络的拓扑结构:INR是可

12、以终止也可以生成新的INR,INR的邻居不是静态的而是动态的,随着网络状态的改变可能改变名字说明(name-specifier):客户端在消息头中用名字说明来指定消息目的地属性(分类标准)-值对(av-pair)(可扩充的)名字说明是av-pair的分层次排列(例)匹配:可使用精确匹配或通配符(*),范围查找(,=,=)2022/7/2425系统结构发现服务名字:服务周期性的发布自己的名字来描述其所提供的服务INR在一个端口上监听来发现新服务INR在INR网络上发散更新消息(周期性的和触发性的)来彼此复制每个名字有一个生存期,如果在生存期结束之前没有刷新就自动抛弃,这样新的信息自动取代过时信息

13、,INR可自动从错误中恢复 服务也不用注册和注销2022/7/2426系统结构名字查找和提取:INR的主要活动是从名字说明解析到相应网络位置名字树:每个INR维护一个,是这个INR所知的所有名字说明的迭加名字记录(name record):到邻居INR的路由,IP地址,路由次数,终点距离,名字记录的期限2022/7/2427系统结构名字查找(根据名字说明n从名字树T中查找名字记录)算法思想:一系列递归调用来减少名字记录候选集S,算法结束S为所求名字记录集合)S初始化为包括这个INR上所有可能的名字记录根据名字说明在树中查找相应av-pair如果到n或者T的叶结点,求交集否则递归调用对子树的查找

14、通配符2022/7/2428系统结构名字提取(INR发送给邻居更新消息需要根据名字记录r从自己的名字树T中提取出名字说明)算法思想:根据名字记录在名字树中向上走直到根,一路上经历的av-pair的结构就是相应的名字说明给名字树中所有值结点加一个PTR指针指向名字说明中的相应的av-pair,初始化设置所有PTR为nul,设置根的PTR指向一个新的名字说明从r的所有父结点出发,向上追溯,如果相应av-pair的PTR指针为空就生成av-pair并把PTR指向它,如果不为空就把已经生成的子树移植到它下面 2022/7/2429系统结构INR网络:是INR根据反映INR之间轮询延迟的距离来自我配置(

15、分布式)形成的生成树用INR-ping来获取INR之间的轮询延迟 DSR(域空间解析器,众所周知)维护活跃和侯选INR的信息新INR进入网络首先和DSR联系获得INR名单,然后与这些INR逐一联系选距离最小者作为自己的邻居,最终结果是树形拓扑结构 问题:非最小生成树,单点失效2022/7/2430系统结构负载平衡与扩展潜在的性能和扩展瓶颈:查找和更新查找的处理:查找负担过重的INR根据从DSP处获得的未激活的候选者解析器上产生新实例,负担过轻的可以在负载小于一定阈值的时候终止自己,并通知它了邻居和DSP更新问题:把名字空间划分为几个虚拟空间,保证每个INR只需处理名字空间的某个子集.这样每个虚

16、拟名字空间对应一个INR网络,服务填加一个Vspace属性,如何找到处理相应空间的INR(cache,DSR)2022/7/2431待解决问题解析过程中操作符的扩充INR网络结构的优化INR网络的单点失效问题安全机制2022/7/2432相关工作异构网络中的服务发现:Jini:RMI但是缺少对动态网络的支持(可以使用INS?)Universal Plug&Play:用XML的子集描述资源SLP(服务定位协议):使用集中式的目录代理来来帮助发现和使用异构网络中的资源SDS(服务发现服务):扩展了SLP的想法,并且使用安全的经过验证的通信,操作的层次结构固定,与前几种不同:可以处理动态网络,通过迟

17、绑定2022/7/2433相关工作基于属性的目录服务X.500分布式目录,与INR区别: 没有迟绑定,解析器网络是静态的,因而不适用于动态网络广域网中的命名和解析ActivenamesINS与Activenames目标类似,实现机制不同:使用了表达性强的命名机制(名字说明)来表达意愿,迟绑定来处理变化2022/7/2434Active Names:广域资源的灵活定位与传输(1999)Active Names:支持广域网络服务的一种灵活的可扩展的名字服务方法。扩展性:它由一些运行在不同位置的程序组成,只需要下载并在自己机器上运行该程序即可加入这条服务链。位置无关:，用户只需知道服务名，而不需要知

18、道服务的网络地址Anycast:对于不同的客户端，会根据它的特性返回不同的结果。高效的，由于使用了Cache技术和Distillation技术，使它能够在较短时间内响应用户。 2022/7/2435Active Names:广域资源的灵活定位与传输方法概要:客户端想要使用某一服务，它首先自己建立一个namespace进程，对服务名进行解析，然后把没有解析完全的服务名发给和它最近的解析器，实际上就是其他机器上的namespace进程，由它继续解析，并把结果发到另一个解析器解析，解析完毕时服务器就和客户端建立了一条通讯线路。当服务名完全被解析的时候，服务器能够按照这个流水线回溯到客户端,传递服务结

19、果。 2022/7/2436使用DNS解析URI(1996)URI(统一资源标识):包括URL,URN等从统一资源定位(URL)到统一资源名(URN)URL面对的挑战:资源位置的改变和复制原因:URL中包含了过多的位置信息高效但却缺少灵活性 2022/7/2437定位复制的服务器的最近副本(1995)问题:在服务器有多个副本的情况下,如何根据网络的结构选择最合适的一个以减少网络负担本文是一篇基于实验的论文,提出一种方法对一系列的定位服务的方法进行测试和比较,计算成本效益比.2022/7/2438Cricket定位支持系统本文设计实现和评估了一种室内的移动,依赖位置的定位系统:Cricket设计目标:隐私保护,分散管理,异构网络,低成本实现方法:在不同位置处每隔一定距离就安装一个beacon,beacon都发送各不相同的超声波和电磁波两种形式的信号来标识自己。用户使用一个listener来接收这些信号，信号都是一对对的形式