查找的处理课件.ppt

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

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

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

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

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

6、对象的句柄传到自身所在区域的叶结点上n从这个叶结点向上搜索直到第一个发现有请求对象的目录结点n从这个目录结点向下找到请求对象的地址把这个地址传递给请求者n一致性规则n对同一个叶结点的更新请求按请求顺序执行n对不同叶结点的更新请求执行顺序随意2022-8-412分布对象的跟踪n动态优化（提高查找速度,减少更新负担）n指针缓存n使用指针缓存要求对象地址存放位置稳定n缺省时对象地址保存在叶结点联系记录中，当对象的位置有规律的一定的区域内改变，可以直接把对象的地址保存在区域的目录结点的联系记录中（例）n这样就可以把指向稳定的目录结点的指针缓存起来2022-8-413分布对象的跟踪n扩展性n前面给出的搜

7、索树模型扩展性并不好，随着对象的增加，高层结点要处理大量的请求，存储大量的数据。n解决方法：分裂目录结点n每个目录结点分裂出的子结点负责原来目录结点上存储的记录的一个子集n一个分裂目录结点的例子2022-8-414相关工作n针对不同类别的移动对象（移动硬件，移动软件）不同的特点，已经提出了不同的服务定位方法。2022-8-415相关工作n移动硬件：往往随着使用者的移动而移动n移动速度：不超过人的最大移动速度n因而可以采用这种策略：其中数据结构随着对象的移动而变化（不需要很快的处理位置变化）n几个定位服务成功的利用这个特点提出了自己的模型n一个对象同一时刻只有一个地址n不必处理一个对象多地址的情

8、况n本文提出的模型没有利用这两个特点，因为这个模型还要致力于处理移动软件对象2022-8-416相关工作n移动软件对象n一个主机上有多个对象（数量巨大,扩展性问题不容忽视）n针对对象的移动模式n使用指针链跟踪对象，需要时缩短长指针链，其它方法失效时使用广播（不适合大型系统）-Emerald系统n依赖于一个全球名字服务，假定更新/查找的值很小-LII（Location Independent Invocation)n本文系统目标：广域系统，对象移动频繁（大量更新）2022-8-417相关工作nSSP链：(似乎是一种适用于大型系统的可行方案)n思路:对象引用可以在进程之间透明的移交,代价是同时生成

9、指向这个对象的指针链n缺点:n完全不能利用就近性(Locality)n缺少对容错性的支持n结论:SSP链不适合扩展到世界范围的大型系统2022-8-418结论n一种新的在广域网中定位对象的方法，使用与位置无关的对象句柄而不是用户定义的名字2022-8-419一个INS的设计与实现n本文主要贡献:n设计和实现了一个INS(Intentional Naming System),用于动态的移动设备和计算机网络中的资源发现和服务定位n何谓Intentional:n分布式网络中应用往往不知道满足其需求的最优网络资源的位置nIntentional命名机制和解析方法:n应用表达自己的意愿:要什么而不是在哪得

10、到n由名字解析器维护服务描述与其网络位置的映射,负责把请求传递到最适合的位置2022-8-420简介n未来的网络环境:大量移动无线设备出现n网络环境的动态特性n移动网络中的消息包路由问题已经得到了较好的解决n资源发现和服务定位2022-8-421简介n实现动态资源发现和服务定位的名字系统的设计目标n表达力:处理大量设备和服务,表达任意的服务描述和查询n响应度:迅速感知对网络中服务的网络定位有影响的服务和结点的移动,性能波动以及其它因素n鲁棒性:能从名字解析器或服务的失败,以及解析器之间的内部不一致中恢复n易配置:解析器应该尽量自动配置少手工干涉,服务应不需手工注册,系统应自动在解析器之间分配解

11、析负载2022-8-422系统结构nINR:形成一个应用级网络用来交换服务描述,建立本地CACHEn服务:与INR联系,报告基于属性-值对的服务描述n客户端:使用一个查询表达式向INR请求服务 INS结构图示2022-8-423系统结构n绑定:客户端消息到达INR时,INR根据客户端的请求决定是完成解析还是转发 n早绑定:解析器直接返回一个IP地址列表(类似与DNS和现存的名字发现系统),这种情况适用于相对稳定的服务,客户机从中选择一个n迟绑定:INR不直接返回IP地址而是转发名字和应用负载n(Intentional Anycast):选择一个来转发(根据:metric)n(Intention

12、al Multicast):转发到所有与这个名字相关的INR(最终消息发送到所有与这个名字一致的目标接点)2022-8-424系统结构nINR网络的拓扑结构:INR是可以终止也可以生成新的INR,INR的邻居不是静态的而是动态的,随着网络状态的改变可能改变n名字说明(name-specifier):客户端在消息头中用名字说明来指定消息目的地n属性(分类标准)-值对(av-pair)(可扩充的)n名字说明是av-pair的分层次排列(例)n匹配:可使用精确匹配或通配符(*),范围查找(,=,=)2022-8-425系统结构n发现服务名字:n服务周期性的发布自己的名字来描述其所提供的服务nINR在

13、一个端口上监听来发现新服务nINR在INR网络上发散更新消息(周期性的和触发性的)来彼此复制n每个名字有一个生存期,如果在生存期结束之前没有刷新就自动抛弃,这样新的信息自动取代过时信息,INR可自动从错误中恢复 服务也不用注册和注销2022-8-426系统结构n名字查找和提取:INR的主要活动是从名字说明解析到相应网络位置n名字树:每个INR维护一个,是这个INR所知的所有名字说明的迭加n名字记录(name record):到邻居INR的路由,IP地址,路由次数,终点距离,名字记录的期限2022-8-427系统结构n名字查找(根据名字说明n从名字树T中查找名字记录)n算法思想:一系列递归调用来

14、减少名字记录候选集S,算法结束S为所求名字记录集合)nS初始化为包括这个INR上所有可能的名字记录n根据名字说明在树中查找相应av-pairn如果到n或者T的叶结点,求交集n否则递归调用对子树的查找n通配符2022-8-428系统结构n名字提取(INR发送给邻居更新消息需要根据名字记录r从自己的名字树T中提取出名字说明)n算法思想:根据名字记录在名字树中向上走直到根,一路上经历的av-pair的结构就是相应的名字说明n给名字树中所有值结点加一个PTR指针指向名字说明中的相应的av-pair,初始化设置所有PTR为nul,设置根的PTR指向一个新的名字说明n从r的所有父结点出发,向上追溯,如果相

15、应av-pair的PTR指针为空就生成av-pair并把PTR指向它,如果不为空就把已经生成的子树移植到它下面 2022-8-429系统结构nINR网络:是INR根据反映INR之间轮询延迟的距离来自我配置(分布式)形成的生成树n用INR-ping来获取INR之间的轮询延迟 nDSR(域空间解析器,众所周知)维护活跃和侯选INR的信息n新INR进入网络首先和DSR联系获得INR名单,然后与这些INR逐一联系选距离最小者作为自己的邻居,最终结果是树形拓扑结构 n问题:非最小生成树,单点失效2022-8-430系统结构n负载平衡与扩展n潜在的性能和扩展瓶颈:查找和更新n查找的处理查找的处理:查找负担

16、过重的INR根据从DSP处获得的未激活的候选者解析器上产生新实例,负担过轻的可以在负载小于一定阈值的时候终止自己,并通知它了邻居和DSPn更新问题更新问题:把名字空间划分为几个虚拟空间,保证每个INR只需处理名字空间的某个子集.这样每个虚拟名字空间对应一个INR网络,服务填加一个Vspace属性,如何找到处理相应空间的INR(cache,DSR)2022-8-431待解决问题n解析过程中操作符的扩充nINR网络结构的优化nINR网络的单点失效问题n安全机制2022-8-432相关工作n异构网络中的服务发现:nJini:RMI但是缺少对动态网络的支持(可以使用INS?)nUniversal Pl

17、ug&Play:用XML的子集描述资源nSLP(服务定位协议):使用集中式的目录代理来来帮助发现和使用异构网络中的资源nSDS(服务发现服务):扩展了SLP的想法,并且使用安全的经过验证的通信,操作的层次结构固定,与前几种不同:可以处理动态网络,通过迟绑定2022-8-433相关工作n基于属性的目录服务nX.500分布式目录,与INR区别:没有迟绑定,解析器网络是静态的,因而不适用于动态网络n广域网中的命名和解析nActivenamesnINS与Activenames目标类似,实现机制不同:使用了表达性强的命名机制(名字说明)来表达意愿,迟绑定来处理变化2022-8-434Active Nam

18、es:广域资源的灵活定位与传输(1999)nActive Names:支持广域网络服务的一种灵活的可扩展的名字服务方法。n扩展性:它由一些运行在不同位置的程序组成,只需要下载并在自己机器上运行该程序即可加入这条服务链。n位置无关:，用户只需知道服务名，而不需要知道服务的网络地址nAnycast:对于不同的客户端，会根据它的特性返回不同的结果。n高效的，由于使用了Cache技术和Distillation技术，使它能够在较短时间内响应用户。2022-8-435Active Names:广域资源的灵活定位与传输n方法概要:客户端想要使用某一服务，它首先自己建立一个namespace进程，对服务名进行

19、解析，然后把没有解析完全的服务名发给和它最近的解析器，实际上就是其他机器上的namespace进程，由它继续解析，并把结果发到另一个解析器解析，解析完毕时服务器就和客户端建立了一条通讯线路。当服务名完全被解析的时候，服务器能够按照这个流水线回溯到客户端,传递服务结果。2022-8-436使用DNS解析URI(1996)nURI(统一资源标识):包括URL,URN等n从统一资源定位(URL)到统一资源名(URN)nURL面对的挑战:资源位置的改变和复制n原因:URL中包含了过多的位置信息高效但却缺少灵活性 2022-8-437定位复制的服务器的最近副本(1995)n问题:在服务器有多个副本的情况

20、下,如何根据网络的结构选择最合适的一个以减少网络负担n本文是一篇基于实验的论文,提出一种方法对一系列的定位服务的方法进行测试和比较,计算成本效益比.2022-8-438Cricket定位支持系统n本文设计实现和评估了一种室内的移动,依赖位置的定位系统:Cricketn设计目标:隐私保护,分散管理,异构网络,低成本n实现方法:在不同位置处每隔一定距离就安装一个beacon,beacon都发送各不相同的超声波和电磁波两种形式的信号来标识自己。用户使用一个listener来接收这些信号，信号都是一对对的形式出现，在接收的多个beacon发出的信号对中，通过两个信号之间到达的时间间隔来计算距离，并选择

21、最近的beacon作为自己的定位。2022-8-439分布式网络中的资源发现n问题:分布式网络中需要协同处理一项任务的计算机如何得知其它机器的存在和位置n解决:本文提出一种分布式算法(Name Dropper)来解决这个问题n算法思想:通过询问已知计算机来获得全局信息n横向比较2022-8-440对象名字到对象地址的双层解析(名字服务和定位服务)2022-8-441 虚拟查找树的逻辑结构2022-8-442 插入新对象(1)2022-8-443 插入新对象(2)2022-8-444查找2022-8-445在目录结点联系记录中直接保存地址2022-8-446目录结点的分裂2022-8-447INS的体系结构2022-8-448名字说明2022-8-449名字说明2022-8-450名字树2022-8-451名字提取2022-8-452Overview2022-8-453OverviewnWhat are the main research issues in the field?nWhat are the main methods to deal with these issues?nWhat are the scientists doing now in the field?nWhat directions will the research go forward?