1、第第5章章 命名系統(tǒng)主要內(nèi)容5.1 基本概念5.2 無(wú)結(jié)構(gòu)命名5.3 結(jié)構(gòu)化命名5.4 基于屬性的命名5.1 基本概念n實(shí)體（entity）：系統(tǒng)中的任何對(duì)象n物理資源型：主機(jī)、文件、打印機(jī)、磁盤(pán)n邏輯抽象型：進(jìn)程、用戶(hù)、郵箱、新聞組、主頁(yè)、報(bào)文、會(huì)話n實(shí)體的名字（Name）:一個(gè)位串或字符串，可唯一地標(biāo)識(shí)一個(gè)實(shí)體n如主機(jī)名、文件名、進(jìn)程名、用戶(hù)名n命名（Naming）:賦予名字名字與地址n實(shí)體訪問(wèn)點(diǎn)（access point）：用于訪問(wèn)該實(shí)體的接口n可以有多個(gè)訪問(wèn)點(diǎn)n實(shí)體可以改變?cè)L問(wèn)點(diǎn)n訪問(wèn)點(diǎn)可賦給另一個(gè)實(shí)體n地址（address）：n實(shí)體訪問(wèn)點(diǎn)的名字，指向?qū)嶓w的一個(gè)訪問(wèn)點(diǎn)n例如：服務(wù)器地址

2、：IP+端口號(hào)n位置獨(dú)立性n實(shí)體的名字與它的地址無(wú)關(guān)學(xué)號(hào)姓名電話名字與標(biāo)識(shí)符n標(biāo)識(shí)符（Identifier）：特殊類(lèi)型的名字1.一個(gè)標(biāo)識(shí)符最多引用一個(gè)實(shí)體2.每個(gè)實(shí)體被一個(gè)標(biāo)識(shí)符所引用3.一個(gè)標(biāo)識(shí)符總是引用同一個(gè)實(shí)體（不準(zhǔn)重用）n機(jī)器可讀的名字n數(shù)字位串，如網(wǎng)卡地址：0020AF0B9876hn用戶(hù)友好的名字（human-friendly name）n有意義的字符串，如目錄名“home”固定實(shí)體和移動(dòng)實(shí)體n固定實(shí)體：固定位置n移動(dòng)實(shí)體（mobile entity）：可變位置n位置改變 后，需查找DNS數(shù)據(jù)庫(kù)，進(jìn)行更新記錄地址：上層硬鏈接，更新效率低記錄名字：下層符號(hào)鏈接，查找效率低DNS數(shù)據(jù)庫(kù)

3、名字地址命名與實(shí)體定位(a) 傳統(tǒng)方法：在名字和地址之間的直接的單級(jí)映射(b) 新方法：使用標(biāo)識(shí)符的T-級(jí)映射 -定位服務(wù)5.2 無(wú)結(jié)構(gòu)命名n無(wú)結(jié)構(gòu)名稱(chēng)n名稱(chēng)中不包含任何訪問(wèn)點(diǎn)的信息n例：72550（工作證號(hào)）n結(jié)構(gòu)化名稱(chēng)n簡(jiǎn)單的、可讀的名稱(chēng)n例：（URL地址）廣播和多播方法n廣播方法（broadcast）n例：地址解析協(xié)議（ARP ）：由IP地址找到它的鏈路地址n在大規(guī)模網(wǎng)絡(luò)環(huán)境中，效率低n多播方法（multicast）n多播組、多播地址n定位點(diǎn)到點(diǎn)網(wǎng)絡(luò)中的實(shí)體n定位多個(gè)實(shí)體：同一組織n定位實(shí)體的副本：最近的副本n問(wèn)題：可伸縮性n只適用于小規(guī)模網(wǎng)絡(luò)，如局域網(wǎng)絡(luò)AB轉(zhuǎn)發(fā)指針?lè)椒╪當(dāng)實(shí)體從A移到

4、B之后，在A上設(shè)置一個(gè)指向B的引用n優(yōu)點(diǎn)：客戶(hù)可利用傳統(tǒng)的命名服務(wù)n缺點(diǎn)：間址鏈可能會(huì)很長(zhǎng)、鏈的中間節(jié)點(diǎn)需要維護(hù)轉(zhuǎn)發(fā)信息、鏈的容易斷n目標(biāo)：限制鏈的長(zhǎng)度，保證鏈的魯棒性轉(zhuǎn)發(fā)指針 (1)n分布式對(duì)象遷移原理nSSP鏈：（stub,scion）=(proxy, skeleton)n舉例：當(dāng)O從A移到B后，在A上保留原來(lái)的proxy,并設(shè)立一個(gè)代表O的skeleton.引用傳遞AB轉(zhuǎn)發(fā)指針(2)n轉(zhuǎn)發(fā)指針的優(yōu)化策略n例：通過(guò)在proxy中存儲(chǔ)一個(gè)捷徑(shortcut)，重定向轉(zhuǎn)發(fā)指針。n調(diào)整策略：n單獨(dú)：僅有發(fā)請(qǐng)求的proxy建立短路（如圖b）n全部：轉(zhuǎn)發(fā)鏈上的所有proxy建立短路基于宿主位置的

5、方法（1）n可用于大規(guī)模網(wǎng)絡(luò)n宿主(Home)位置n實(shí)體的創(chuàng)建位置n用于跟蹤實(shí)體的當(dāng)前位置n舉例：移動(dòng) IP原理n每個(gè)主機(jī)有一個(gè)固定IP地址n固定IP地址對(duì)應(yīng)有一個(gè)Home代理n主機(jī)移動(dòng)后的臨時(shí)地址(care-of轉(zhuǎn)交地址)在它的Home代理上登記n當(dāng)Home代理收到packet后，轉(zhuǎn)發(fā)到轉(zhuǎn)交地址基于宿主位置的方法（2）n舉例：n客戶(hù)位置：曼谷（亞洲）n宿主位置：紐約（北美洲）n當(dāng)前位置：開(kāi)普敦（非洲）基于宿主位置的方法（3）n缺點(diǎn)：n可能舍近求遠(yuǎn)：主機(jī)的當(dāng)前位置比宿主位置近，增加通信開(kāi)銷(xiāo)。n固定的宿主位置：無(wú)法根據(jù)需要改變，如主機(jī)已永遠(yuǎn)移動(dòng)后。n解決方案：n將宿主位置記錄在傳統(tǒng)的名字服務(wù)器中

6、分布式散列表（DHT）nChord系統(tǒng)n節(jié)點(diǎn)：具有標(biāo)識(shí)符idn實(shí)體：具有鍵值knk的存儲(chǔ)節(jié)點(diǎn)succ(k)nminid | id kn實(shí)體k的查找（線性）n為節(jié)點(diǎn)p建立的鏈表nsucc(p+1):p的后繼節(jié)點(diǎn)，npred(p)：p的前趨節(jié)點(diǎn)n如果pred(p)kp，則為pn時(shí)間復(fù)雜度：O(N)例：5個(gè)節(jié)點(diǎn)（1，4，7，12，15） 16個(gè)健值（實(shí)體）例1： 從節(jié)點(diǎn)7解析鍵值15分布式散列表n查找的優(yōu)化n指示表(Finger table)nFTpi=succ(p+2i-1)nq=FTpj k FTp j+1n時(shí)間復(fù)雜度：O(log(N)n指示表的更新n檢查FTq1的一致性n后臺(tái)進(jìn)程完成例2： 從

7、節(jié)點(diǎn)28解析鍵值12例1： 從節(jié)點(diǎn)1解析鍵值26利用網(wǎng)絡(luò)鄰近進(jìn)行優(yōu)化n目標(biāo)：減少因特網(wǎng)中的廣域消息傳輸n考慮底層網(wǎng)絡(luò)的三種設(shè)計(jì)n基于節(jié)點(diǎn)的標(biāo)識(shí)符賦值n兩個(gè)鄰接節(jié)點(diǎn)所賦給的標(biāo)識(shí)符是靠近的n不適合chord系統(tǒng)n鄰近路由n每個(gè)結(jié)點(diǎn)維護(hù)一個(gè)轉(zhuǎn)發(fā)請(qǐng)求的可選列表nchord系統(tǒng)n鄰近鄰居節(jié)點(diǎn)選擇n選擇離最近的節(jié)點(diǎn)為鄰居節(jié)點(diǎn)層次方法(1)n將一個(gè)定位服務(wù)分層組織成域（ domain）n每個(gè)域擁有相關(guān)的目錄節(jié)點(diǎn)n根節(jié)點(diǎn)：最頂層域的目錄節(jié)點(diǎn)n葉子域：對(duì)應(yīng)于局域網(wǎng)（LAN）.層次方法(2)n定位紀(jì)錄n 葉子域目錄節(jié)點(diǎn)：n上層域目錄節(jié)點(diǎn)：n 根節(jié)點(diǎn)：包含域中所有的實(shí)體的定位紀(jì)錄n 一個(gè)實(shí)體E可以有n個(gè)地址n在葉子

8、域上，保留有一個(gè)地址n在最小共同祖先域上，保留n個(gè)子域指針層次方法(3)n舉例：具有兩個(gè)地址的實(shí)體的目錄信息層次方法(4)n在層次型定位服務(wù)中，查找一個(gè)位置n局部性原則：從最小的域開(kāi)始，自底向上查找層次方法 (5)階段2：建立一個(gè)指向葉子節(jié)點(diǎn)的指針鏈階段1：插入請(qǐng)求被轉(zhuǎn)發(fā)給記錄實(shí)體E的第一個(gè)節(jié)點(diǎn)n 舉例：自上而下的插入方法5.2 結(jié)構(gòu)化命名n名字空間（name space）：n分布式系統(tǒng)中名字集合的組織形式n例：文件目錄系統(tǒng)（目錄名，文件名）名字空間 (1)n一個(gè)名字空間可表示為用帶標(biāo)號(hào)的有向圖n葉子節(jié)點(diǎn)：命名實(shí)體的信息（地址、狀態(tài)）n目錄節(jié)點(diǎn)：具有一定數(shù)量的分支邊，每條邊用一個(gè)名稱(chēng)來(lái)標(biāo)記。，

9、目錄表n根節(jié)點(diǎn)：只有出邊，沒(méi)有入邊。通常只有一個(gè)。名字空間 (2)n路徑名：對(duì)應(yīng)于邊的標(biāo)號(hào)序列nN:n絕對(duì)路徑名: n從根節(jié)點(diǎn)開(kāi)始，如n0:n相對(duì)路徑名n從非根節(jié)點(diǎn)開(kāi)始，如n1:n路徑的表示n/home/steen/mboxn名字的種類(lèi)n全局名（global），絕對(duì)名，適用于整個(gè)系統(tǒng)n局部名（local），相對(duì)名，與具體目錄有關(guān)名字空間(3)n舉例：UNIX文件名字空間nUNIX文件系統(tǒng)的一般結(jié)構(gòu)n目錄節(jié)點(diǎn)：表示文件目錄n葉子節(jié)點(diǎn)：表示文件n引導(dǎo)塊（boot block）:操作系統(tǒng)加載信息n超級(jí)塊（supper block）：文件系統(tǒng)信息名字解析n名字解析（Resolution）n找到名字所對(duì)

10、應(yīng)實(shí)體，進(jìn)而可訪問(wèn)關(guān)于實(shí)體的信息n終止機(jī)制(Closure)n知道如何以及從何處開(kāi)始名字解析n從名字空間中選擇開(kāi)始名字解析的初始節(jié)點(diǎn)n例：02424683113n命名系統(tǒng)n實(shí)現(xiàn)命名和名字解析鏈接n別名（alias）：同一個(gè)實(shí)體的其他名字n別名的實(shí)現(xiàn)方法：鏈接(link)n硬鏈接（hard）：用多個(gè)絕對(duì)路徑名標(biāo)識(shí)節(jié)點(diǎn)，例如節(jié)點(diǎn)n5鏈接方法n符號(hào)鏈接(symbolic)：用葉節(jié)點(diǎn)表示實(shí)體，存儲(chǔ)絕對(duì)路徑名。n掛接（mount）：合并兩個(gè)不同的名字空間n外地名字空間（foreign name space）n掛接點(diǎn)（mount point） n存儲(chǔ)外地節(jié)點(diǎn)標(biāo)識(shí)符的本地目錄節(jié)點(diǎn)n掛載點(diǎn)（mounting

11、point） n需安裝的外地名字空間的目錄節(jié)點(diǎn)掛接外地NS本地NS掛接方法n分布式系統(tǒng)中掛接的實(shí)現(xiàn)n訪問(wèn)協(xié)議的名字n服務(wù)器的名字n外地名字空間中掛載點(diǎn)的名字n名字的表示n例：URL名，如ftp:/ ftpn服務(wù)器： n安裝點(diǎn)：home/pub/music掛接方法(1)n使用專(zhuān)門(mén)訪問(wèn)協(xié)議，掛接遠(yuǎn)程名字空間n例：解析名稱(chēng)/remote/vu/mboxn 利用NFS協(xié)議與文件服務(wù)器flits.cs.vu.nl聯(lián)系名字空間的實(shí)現(xiàn)n名字服務(wù)n添加、刪除和查找名字n名字服務(wù)器n實(shí)現(xiàn)名字服務(wù)的軟件系統(tǒng)n名字空間的分布方式n區(qū)域(zone):水平劃分n三層結(jié)構(gòu)：垂直劃分名字空間的分布(1)n區(qū)域(zone):

12、n不相交的子空間n每個(gè)區(qū)設(shè)有一個(gè)名字服務(wù)器，負(fù)責(zé)本區(qū)的名字服務(wù)n名字空間的層次n全局層(global)：根節(jié)點(diǎn)，穩(wěn)定不變n行政層(administrational)：目錄節(jié)點(diǎn)，很少改變n管理層(managerial)：底層節(jié)點(diǎn)，可能經(jīng)常改變名字空間的分布(2)nDNS名字空間的三層劃分.名字空間的分布(3)n不同層次上名字服務(wù)器之間的比較項(xiàng)目項(xiàng)目全局層全局層行政層行政層管理層管理層網(wǎng)絡(luò)的地理范圍全世界組織部門(mén)總的節(jié)點(diǎn)個(gè)數(shù)少許多個(gè)巨量查找響應(yīng)性秒毫秒立即更新傳播滯后立即立即副本的個(gè)數(shù)多個(gè)無(wú)或少許無(wú)客戶(hù)端緩存?是是有時(shí)名字解析的實(shí)現(xiàn) (1)n名字解析器(NR)n客戶(hù)端執(zhí)行名字解析的程序n迭代式方法

13、n名字解析器從根名字服務(wù)器開(kāi)始，逐個(gè)與名字服務(wù)器交互，實(shí)現(xiàn)名字的解析n遞歸式方法n名字解析器委托根名字服務(wù)器，由各個(gè)名字服務(wù)器之間交互，實(shí)現(xiàn)名字的解析NRNS1NS2NRNS1NS2NS3NS3名字解析的實(shí)現(xiàn)(2)n例：迭代式名字解析nroot:名字解析的實(shí)現(xiàn)(3)n例：遞歸式名字解析nroot:名字解析的實(shí)現(xiàn)(4)n解析中的緩存作用n舉例：遞歸式名字解析節(jié)點(diǎn)服節(jié)點(diǎn)服務(wù)器務(wù)器解析解析查找查找傳給傳給子節(jié)點(diǎn)子節(jié)點(diǎn)接收和緩存接收和緩存返回給返回給請(qǐng)求者請(qǐng)求者cs#-#vu#ni#root#名字解析的實(shí)現(xiàn)(5)n遞歸式和迭代式在通信代價(jià)方面的比較DNS:英特網(wǎng)域名系統(tǒng)nDNS（domain name

14、 system）: nInternet中查找主機(jī)和email服務(wù)器地址nDNS名字空間n一個(gè)有根樹(shù)n域（domain）:一個(gè)子樹(shù)n域名：從根節(jié)點(diǎn)開(kāi)始的路徑名n區(qū)域（zone）：域的劃分，對(duì)應(yīng)一個(gè)名字服務(wù)器n資源紀(jì)錄：節(jié)點(diǎn)包含的內(nèi)容DNS名字空間n資源記錄記錄類(lèi)型記錄類(lèi)型 管理實(shí)體管理實(shí)體描述描述SOAZone保留所表示區(qū)域的有關(guān)信息AHost包含該節(jié)點(diǎn)表示的主機(jī)的IP地址MXDomain指向用于處理發(fā)給該節(jié)點(diǎn)的郵件的郵件服務(wù)器SRVDomain指向處理專(zhuān)門(mén)服務(wù)的服務(wù)器NSZone指向?qū)崿F(xiàn)所表示區(qū)域的名字服務(wù)器CNAMENode所表示節(jié)點(diǎn)的主名字的符號(hào)連接PTRHost包含主機(jī)的規(guī)范名字HINF

15、OHost保留該節(jié)點(diǎn)表示的主機(jī)的信息TXTAny kind包含實(shí)體有用的特別信息5.3 基于屬性的命名n基于屬性的命名:n一個(gè)實(shí)體擁有一個(gè)相關(guān)的屬性集n例：一個(gè)人，名字，Alicen用（屬性，值）來(lái)描述實(shí)體n目錄服務(wù)：n基于屬性的命名系統(tǒng)n可使用實(shí)體的屬性查找實(shí)體n資源描述框架（RDF）：描述資源的統(tǒng)一方法nn例：分層實(shí)現(xiàn)：LDAPn輕量級(jí)目錄訪問(wèn)協(xié)議（LDAP）nOSI X.500目錄服務(wù)n國(guó)際電信聯(lián)盟（ITU）關(guān)于目錄服務(wù)的建議標(biāo)準(zhǔn)nLDAP目錄項(xiàng)n目錄項(xiàng): 由多個(gè)記錄（屬性，值）組成。n多值屬性:用數(shù)組或鏈表表示n目錄信息庫(kù)(DIB)n所有目錄項(xiàng)的集合。n相對(duì)區(qū)分名（RDN）：命名屬性n

16、每個(gè)目錄項(xiàng)具有全局唯一的記錄名：RDN值序列LDAP目錄服務(wù)(1)n舉例：LDAP目錄項(xiàng)n/c=NL/O=Vrije University/OU=Comp.Sc.n=nl.vu.cs屬性屬性縮寫(xiě)縮寫(xiě)值值CountryCNLLocalityLAmsterdamOrganizationLVrije UniversiteitOrganizationalUnitOUMath. & Comp. Sc.CommonNameCNMain serverMail_Servers-, 192.31.231, 6FTP_Server-1WW

17、W_Server-1LDAP目錄服務(wù)(2)n目錄信息樹(shù)(DIT)n用于描述目錄項(xiàng)集合的層次結(jié)構(gòu)，命名圖n舉例：局部的目錄信息樹(shù)LDAP目錄服務(wù)(3)n例：使用 Host_Name作為 RDN.目錄項(xiàng)1目錄項(xiàng)2屬性屬性值值屬性屬性值值CountryNLCountryNLLocalityAmsterdamLocalityAmsterdamOrganizationVrije UniversiteitOrganizationVrije UniversiteitOrganizationalUnitMath. & Comp. Sc.OrganizationalUnitMath. & Comp. Sc.CommonNameMain serverCommonNameMain serverHost_NamestarHost_Namez