1、2022/7/241Paper critiques2022/7/242廣域網(wǎng)系統(tǒng)中的對象定位(1998)本文提出了一種新的在廣域網(wǎng)系統(tǒng)中定位移動對象的方案主要思想：分離對象名字與對象地址，引入一個中間層：對象句柄，兩層解析對象名字與對象句柄綁定（名字服務(wù)），再由對象句柄映射到對象的地址（定位服務(wù)）本文重點：由對象句柄到對象地址的映射（定位服務(wù)）2022/7/243簡介網(wǎng)絡(luò)的變化趨勢：對象數(shù)量增加移動對象（硬件或軟件）支持移動對象對網(wǎng)絡(luò)的要求：客戶機可以在完全不知道對象當前位置的情況下聯(lián)系到這個對象對象的位置的變化對于客戶機來說是透明的傳統(tǒng)的名字服務(wù)： 維護對象名字和對象的地址（一個或多個）之間

2、的綁定。對于移動對象，對象名字應(yīng)該被解析到當前地址上（關(guān)鍵：映射要隨對象地址的改變而改變） 2022/7/244簡介挑戰(zhàn):當對象地址很少改變，世界范圍的可擴展的名字服務(wù)較易實現(xiàn)DNS ，X.500 Directory Service對象地址改變頻繁時，問題復(fù)雜性顯著增加本文提出了一種提供靈活的名字-地址綁定的定位服務(wù)系統(tǒng)目標：支持一個全球范圍內(nèi)的面向?qū)ο蠓植际较到y(tǒng)，系統(tǒng)規(guī)模達到 1 億用戶每個擁有上千個對象2022/7/245名字到地址的綁定名字里是否要包含地址信息？利于解析不利于處理對象的移動（對象地址改變引起名字的變化）問題的解決本文提出的兩級分層命名機制名字服務(wù)：對象名字到對象句柄的映射

3、定位服務(wù)：對象句柄到對象地址（可能有多個）的映射意義：對象名和地址可以獨立的改變通過對象句柄（唯一的與地址無關(guān)的）聯(lián)系起來，對象名字與對象地址完全的分離開來2022/7/246名字到地址的綁定定位服務(wù)與命名無關(guān)，主要設(shè)計用來支持頻繁的聯(lián)系地址更新和查找操作Anycast:分布式系統(tǒng)中的一種定位服務(wù)的方式客戶機只請求特定的服務(wù)，而不在意服務(wù)由那個對象來處理。本系統(tǒng)實現(xiàn)的就是Anycast,服務(wù)被分配一個句柄，實現(xiàn)此服務(wù)的服務(wù)器在這個句柄下注冊自己的網(wǎng)絡(luò)地址，客戶機的服務(wù)請求被解析到這個服務(wù)的對象句柄，然后被解析到任意一個可以處理此服務(wù)的服務(wù)器上。2022/7/247名字到地址的綁定對定位服務(wù)的要

4、求擴展性： 1012個對象就近性 ?（Locality):系統(tǒng)確定路由時應(yīng)該就近（不走冤枉路）比如如果所請求對象與客戶機距離很近，那么應(yīng)該很容易找到這個對象穩(wěn)定性：對于穩(wěn)定（在某個區(qū)域內(nèi)）的對象處理應(yīng)該簡單一些容錯性：從結(jié)點，連接錯誤中恢復(fù)，出現(xiàn)網(wǎng)絡(luò)分割時能繼續(xù)操作2022/7/248分布對象的跟蹤本文提出的全球的可擴展定位服務(wù)的體系結(jié)構(gòu)（框架）模型整個網(wǎng)絡(luò)分成若干層次區(qū)域區(qū)域：每個區(qū)域?qū)?yīng)一個目錄結(jié)點目錄結(jié)點：存儲相應(yīng)區(qū)域內(nèi)的地址（地址是依賴與位置的）構(gòu)成一個邏輯上的樹型結(jié)構(gòu)2022/7/249分布對象的跟蹤插入新地址：新地址通常插入到地址所在區(qū)域的葉結(jié)點上新對象建立一條從根到其所在位置的指

5、針鏈這些指針以及對象實際地址存貯在聯(lián)系記錄中未注冊對象的插入請求從葉結(jié)點自下而上傳遞，傳遞過程中一路上生成鏈接（到下層）指針已注冊的對象的插入請求只在不重復(fù)的部分建立新指針2022/7/2410分布對象的跟蹤刪除聯(lián)系地址先由地址找到地址所在區(qū)域（地址中是包含所在區(qū)域信息的）從代表這個區(qū)域的葉結(jié)點開始向上查找直到找到這個地址為止，刪除之如果刪除聯(lián)系地址后這個聯(lián)系記錄內(nèi)不再有聯(lián)系地址或指針就刪除這個聯(lián)系記錄如果刪除了聯(lián)系記錄還要向上檢查它的祖先看是否需要刪除2022/7/2411分布對象的跟蹤查找聯(lián)系地址客戶機進程把所請求對象的句柄傳到自身所在區(qū)域的葉結(jié)點上從這個葉結(jié)點向上搜索直到第一個發(fā)現(xiàn)有請求

6、對象的目錄結(jié)點從這個目錄結(jié)點向下找到請求對象的地址把這個地址傳遞給請求者一致性規(guī)則對同一個葉結(jié)點的更新請求按請求順序執(zhí)行對不同葉結(jié)點的更新請求執(zhí)行順序隨意2022/7/2412分布對象的跟蹤動態(tài)優(yōu)化（提高查找速度,減少更新負擔(dān)）指針緩存使用指針緩存要求對象地址存放位置穩(wěn)定缺省時對象地址保存在葉結(jié)點聯(lián)系記錄中，當對象的位置有規(guī)律的一定的區(qū)域內(nèi)改變，可以直接把對象的地址保存在區(qū)域的目錄結(jié)點的聯(lián)系記錄中（例）這樣就可以把指向穩(wěn)定的目錄結(jié)點的指針緩存起來2022/7/2413分布對象的跟蹤擴展性前面給出的搜索樹模型擴展性并不好，隨著對象的增加，高層結(jié)點要處理大量的請求，存儲大量的數(shù)據(jù)。解決方法：分裂目

7、錄結(jié)點每個目錄結(jié)點分裂出的子結(jié)點負責(zé)原來目錄結(jié)點上存儲的記錄的一個子集一個分裂目錄結(jié)點的例子2022/7/2414相關(guān)工作針對不同類別的移動對象（移動硬件，移動軟件）不同的特點，已經(jīng)提出了不同的服務(wù)定位方法。2022/7/2415相關(guān)工作移動硬件：往往隨著使用者的移動而移動移動速度：不超過人的最大移動速度因而可以采用這種策略：其中數(shù)據(jù)結(jié)構(gòu)隨著對象的移動而變化（不需要很快的處理位置變化）幾個定位服務(wù)成功的利用這個特點提出了自己的模型一個對象同一時刻只有一個地址不必處理一個對象多地址的情況本文提出的模型沒有利用這兩個特點，因為這個模型還要致力于處理移動軟件對象2022/7/2416相關(guān)工作移動軟件

8、對象一個主機上有多個對象（數(shù)量巨大,擴展性問題不容忽視）針對對象的移動模式使用指針鏈跟蹤對象，需要時縮短長指針鏈，其它方法失效時使用廣播（不適合大型系統(tǒng)）-Emerald系統(tǒng)依賴于一個全球名字服務(wù)，假定更新/查找的值很小-LII（Location Independent Invocation)本文系統(tǒng)目標：廣域系統(tǒng)，對象移動頻繁（大量更新）2022/7/2417相關(guān)工作SSP鏈：(似乎是一種適用于大型系統(tǒng)的可行方案)思路:對象引用可以在進程之間透明的移交,代價是同時生成指向這個對象的指針鏈缺點:完全不能利用就近性( Locality)缺少對容錯性的支持結(jié)論:SSP鏈不適合擴展到世界范圍的大型系

9、統(tǒng)2022/7/2418結(jié)論一種新的在廣域網(wǎng)中定位對象的方法，使用與位置無關(guān)的對象句柄而不是用戶定義的名字2022/7/2419一個INS的設(shè)計與實現(xiàn)本文主要貢獻:設(shè)計和實現(xiàn)了一個INS(Intentional Naming System),用于動態(tài)的移動設(shè)備和計算機網(wǎng)絡(luò)中的資源發(fā)現(xiàn)和服務(wù)定位何謂Intentional:分布式網(wǎng)絡(luò)中應(yīng)用往往不知道滿足其需求的最優(yōu)網(wǎng)絡(luò)資源的位置Intentional命名機制和解析方法:應(yīng)用表達自己的意愿:要什么而不是在哪得到由名字解析器維護服務(wù)描述與其網(wǎng)絡(luò)位置的映射,負責(zé)把請求傳遞到最適合的位置2022/7/2420簡介未來的網(wǎng)絡(luò)環(huán)境:大量移動無線設(shè)備出現(xiàn)網(wǎng)絡(luò)環(huán)

10、境的動態(tài)特性移動網(wǎng)絡(luò)中的消息包路由問題已經(jīng)得到了較好的解決資源發(fā)現(xiàn)和服務(wù)定位2022/7/2421簡介實現(xiàn)動態(tài)資源發(fā)現(xiàn)和服務(wù)定位的名字系統(tǒng)的設(shè)計目標表達力:處理大量設(shè)備和服務(wù),表達任意的服務(wù)描述和查詢響應(yīng)度:迅速感知對網(wǎng)絡(luò)中服務(wù)的網(wǎng)絡(luò)定位有影響的服務(wù)和結(jié)點的移動,性能波動以及其它因素魯棒性:能從名字解析器或服務(wù)的失敗,以及解析器之間的內(nèi)部不一致中恢復(fù)易配置:解析器應(yīng)該盡量自動配置少手工干涉,服務(wù)應(yīng)不需手工注冊,系統(tǒng)應(yīng)自動在解析器之間分配解析負載2022/7/2422系統(tǒng)結(jié)構(gòu)INR:形成一個應(yīng)用級網(wǎng)絡(luò)用來交換服務(wù)描述,建立本地CACHE服務(wù):與INR聯(lián)系,報告基于屬性-值對的服務(wù)描述客戶端:使用

11、一個查詢表達式向INR請求服務(wù) INS結(jié)構(gòu)圖示2022/7/2423系統(tǒng)結(jié)構(gòu)綁定: 客戶端消息到達INR時,INR根據(jù)客戶端的請求決定是完成解析還是轉(zhuǎn)發(fā) 早綁定:解析器直接返回一個IP地址列表(類似與DNS和現(xiàn)存的名字發(fā)現(xiàn)系統(tǒng)),這種情況適用于相對穩(wěn)定的服務(wù),客戶機從中選擇一個遲綁定:INR不直接返回IP地址而是轉(zhuǎn)發(fā)名字和應(yīng)用負載(Intentional Anycast):選擇一個來轉(zhuǎn)發(fā)(根據(jù):metric)(Intentional Multicast):轉(zhuǎn)發(fā)到所有與這個名字相關(guān)的INR(最終消息發(fā)送到所有與這個名字一致的目標接點)2022/7/2424系統(tǒng)結(jié)構(gòu)INR網(wǎng)絡(luò)的拓撲結(jié)構(gòu):INR是可

12、以終止也可以生成新的INR,INR的鄰居不是靜態(tài)的而是動態(tài)的,隨著網(wǎng)絡(luò)狀態(tài)的改變可能改變名字說明(name-specifier):客戶端在消息頭中用名字說明來指定消息目的地屬性(分類標準)-值對(av-pair)(可擴充的)名字說明是av-pair的分層次排列(例)匹配:可使用精確匹配或通配符(*),范圍查找(,=,=)2022/7/2425系統(tǒng)結(jié)構(gòu)發(fā)現(xiàn)服務(wù)名字:服務(wù)周期性的發(fā)布自己的名字來描述其所提供的服務(wù)INR在一個端口上監(jiān)聽來發(fā)現(xiàn)新服務(wù)INR在INR網(wǎng)絡(luò)上發(fā)散更新消息(周期性的和觸發(fā)性的)來彼此復(fù)制每個名字有一個生存期,如果在生存期結(jié)束之前沒有刷新就自動拋棄,這樣新的信息自動取代過時信息

13、,INR可自動從錯誤中恢復(fù) 服務(wù)也不用注冊和注銷2022/7/2426系統(tǒng)結(jié)構(gòu)名字查找和提取:INR的主要活動是從名字說明解析到相應(yīng)網(wǎng)絡(luò)位置名字樹:每個INR維護一個,是這個INR所知的所有名字說明的迭加名字記錄(name record):到鄰居INR的路由,IP地址,路由次數(shù),終點距離,名字記錄的期限2022/7/2427系統(tǒng)結(jié)構(gòu)名字查找(根據(jù)名字說明n從名字樹T中查找名字記錄)算法思想:一系列遞歸調(diào)用來減少名字記錄候選集S,算法結(jié)束S為所求名字記錄集合)S初始化為包括這個INR上所有可能的名字記錄根據(jù)名字說明在樹中查找相應(yīng)av-pair如果到n或者T的葉結(jié)點,求交集否則遞歸調(diào)用對子樹的查找

14、通配符2022/7/2428系統(tǒng)結(jié)構(gòu)名字提取(INR發(fā)送給鄰居更新消息需要根據(jù)名字記錄r從自己的名字樹T中提取出名字說明)算法思想:根據(jù)名字記錄在名字樹中向上走直到根,一路上經(jīng)歷的av-pair的結(jié)構(gòu)就是相應(yīng)的名字說明給名字樹中所有值結(jié)點加一個PTR指針指向名字說明中的相應(yīng)的av-pair,初始化設(shè)置所有PTR為nul,設(shè)置根的PTR指向一個新的名字說明從r的所有父結(jié)點出發(fā),向上追溯,如果相應(yīng)av-pair的PTR指針為空就生成av-pair并把PTR指向它,如果不為空就把已經(jīng)生成的子樹移植到它下面 2022/7/2429系統(tǒng)結(jié)構(gòu)INR網(wǎng)絡(luò):是INR根據(jù)反映INR之間輪詢延遲的距離來自我配置(

15、分布式)形成的生成樹用INR-ping來獲取INR之間的輪詢延遲 DSR(域空間解析器,眾所周知)維護活躍和侯選INR的信息新INR進入網(wǎng)絡(luò)首先和DSR聯(lián)系獲得INR名單,然后與這些INR逐一聯(lián)系選距離最小者作為自己的鄰居,最終結(jié)果是樹形拓撲結(jié)構(gòu) 問題:非最小生成樹,單點失效2022/7/2430系統(tǒng)結(jié)構(gòu)負載平衡與擴展?jié)撛诘男阅芎蛿U展瓶頸:查找和更新查找的處理:查找負擔(dān)過重的INR根據(jù)從DSP處獲得的未激活的候選者解析器上產(chǎn)生新實例,負擔(dān)過輕的可以在負載小于一定閾值的時候終止自己,并通知它了鄰居和DSP更新問題:把名字空間劃分為幾個虛擬空間,保證每個INR只需處理名字空間的某個子集.這樣每個虛

16、擬名字空間對應(yīng)一個INR網(wǎng)絡(luò),服務(wù)填加一個Vspace屬性,如何找到處理相應(yīng)空間的INR(cache,DSR)2022/7/2431待解決問題解析過程中操作符的擴充INR網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化INR網(wǎng)絡(luò)的單點失效問題安全機制2022/7/2432相關(guān)工作異構(gòu)網(wǎng)絡(luò)中的服務(wù)發(fā)現(xiàn):Jini:RMI但是缺少對動態(tài)網(wǎng)絡(luò)的支持(可以使用INS?)Universal Plug&Play:用XML的子集描述資源SLP(服務(wù)定位協(xié)議):使用集中式的目錄代理來來幫助發(fā)現(xiàn)和使用異構(gòu)網(wǎng)絡(luò)中的資源SDS(服務(wù)發(fā)現(xiàn)服務(wù)):擴展了SLP的想法,并且使用安全的經(jīng)過驗證的通信,操作的層次結(jié)構(gòu)固定,與前幾種不同:可以處理動態(tài)網(wǎng)絡(luò),通過遲

17、綁定2022/7/2433相關(guān)工作基于屬性的目錄服務(wù)X.500分布式目錄,與INR區(qū)別: 沒有遲綁定,解析器網(wǎng)絡(luò)是靜態(tài)的,因而不適用于動態(tài)網(wǎng)絡(luò)廣域網(wǎng)中的命名和解析ActivenamesINS與Activenames目標類似,實現(xiàn)機制不同:使用了表達性強的命名機制(名字說明)來表達意愿,遲綁定來處理變化2022/7/2434Active Names:廣域資源的靈活定位與傳輸(1999)Active Names:支持廣域網(wǎng)絡(luò)服務(wù)的一種靈活的可擴展的名字服務(wù)方法。擴展性:它由一些運行在不同位置的程序組成,只需要下載并在自己機器上運行該程序即可加入這條服務(wù)鏈。位置無關(guān):，用戶只需知道服務(wù)名，而不需要知

18、道服務(wù)的網(wǎng)絡(luò)地址Anycast:對于不同的客戶端，會根據(jù)它的特性返回不同的結(jié)果。高效的，由于使用了Cache技術(shù)和Distillation技術(shù)，使它能夠在較短時間內(nèi)響應(yīng)用戶。 2022/7/2435Active Names:廣域資源的靈活定位與傳輸方法概要:客戶端想要使用某一服務(wù)，它首先自己建立一個namespace進程，對服務(wù)名進行解析，然后把沒有解析完全的服務(wù)名發(fā)給和它最近的解析器，實際上就是其他機器上的namespace進程，由它繼續(xù)解析，并把結(jié)果發(fā)到另一個解析器解析，解析完畢時服務(wù)器就和客戶端建立了一條通訊線路。當服務(wù)名完全被解析的時候，服務(wù)器能夠按照這個流水線回溯到客戶端,傳遞服務(wù)結(jié)

19、果。 2022/7/2436使用DNS解析URI(1996)URI(統(tǒng)一資源標識):包括URL,URN等從統(tǒng)一資源定位(URL)到統(tǒng)一資源名(URN)URL面對的挑戰(zhàn):資源位置的改變和復(fù)制原因:URL中包含了過多的位置信息高效但卻缺少靈活性 2022/7/2437定位復(fù)制的服務(wù)器的最近副本(1995)問題:在服務(wù)器有多個副本的情況下,如何根據(jù)網(wǎng)絡(luò)的結(jié)構(gòu)選擇最合適的一個以減少網(wǎng)絡(luò)負擔(dān)本文是一篇基于實驗的論文,提出一種方法對一系列的定位服務(wù)的方法進行測試和比較,計算成本效益比.2022/7/2438Cricket定位支持系統(tǒng)本文設(shè)計實現(xiàn)和評估了一種室內(nèi)的移動,依賴位置的定位系統(tǒng):Cricket設(shè)計目標:隱私保護,分散管理,異構(gòu)網(wǎng)絡(luò),低成本實現(xiàn)方法:在不同位置處每隔一定距離就安裝一個beacon,beacon都發(fā)送各不相同的超聲波和電磁波兩種形式的信號來標識自己。用戶使用一個listener來接收這些信號，信號都是一對對的形式