【學(xué)習(xí)課件】第十一章應(yīng)用層網(wǎng)絡(luò)

1、第十一章 應(yīng)用層網(wǎng)絡(luò)精選課件應(yīng)用層網(wǎng)絡(luò)對(duì)等網(wǎng)絡(luò)應(yīng)用層組播彈性重疊網(wǎng)應(yīng)用層網(wǎng)絡(luò)(ON): Overlay Networks，也稱為重疊網(wǎng)絡(luò)對(duì)等網(wǎng)絡(luò)(P2P): Peer-to-Peer Networks彈性重疊網(wǎng)絡(luò)(RON): resilient Overlay Networks精選課件應(yīng)用層網(wǎng)絡(luò)對(duì)等網(wǎng)絡(luò)應(yīng)用層組播彈性重疊網(wǎng)精選課件Resources綜述羅杰文，Peer-To-Peer 綜述，/users/luojw/P2P/ChordI. Stoica, R. Morris, D. Karger, F. Kaashoek, H.Balakrishnan. Chord: A Scalable P

2、eer-to-Peer Lookup Service for Internet Applications. In Proceedings ACM Sigcomm 2001, San Diego, CA, Aug. 2001.PastryA. Rowstron and P. Druschel, “Pastry: Scalable, distributed objectlocation and routing for large-scale peer-to-peer systems,” in IFIP/ACMInternational Conference on Distributed Syste

3、ms Platforms (Middleware), 2001 CANSylvia Rathasamy, Paul Francis, Mark Handley, Richard Karp and Scott Shenker.A Scalable Content-Addressable Network.In ACM SIGCOMM01, 2001 TapestryB. Y. Zhao, J. D. Kubiatowicz, and A. D. Joseph, Tapestry: An infrastructure for fault-tolerant wide-area location and

4、 routing, UC Berkeley, Tech. Rep. UCB/CSD-01-1141, April 2001.精選課件對(duì)等網(wǎng)絡(luò)(P2P: Peer-to-Peer)1. 概述P2P的引入背景，P2P的定義，P2P的特征，2. P2P網(wǎng)絡(luò)的分類非結(jié)構(gòu)化P2P結(jié)構(gòu)化P2P3. 幾種非結(jié)構(gòu)化P2P網(wǎng)絡(luò)完全分布式的P2P網(wǎng)絡(luò)、基于目錄服務(wù)器的P2P網(wǎng)絡(luò)、層次P2P網(wǎng)絡(luò)4. 幾種結(jié)構(gòu)化P2P網(wǎng)絡(luò)Hash函數(shù)、基于分布式hash表的P2P網(wǎng)絡(luò)原理Chord、 Pastry、CAN、Tapestry精選課件1.1 P2P引入背景(1)傳統(tǒng)客戶/服務(wù)器模式的不足瓶頸問題：服務(wù)器的帶寬、存儲(chǔ)、計(jì)算

5、等資源受限，容易成為網(wǎng)絡(luò)瓶頸單點(diǎn)失效問題：服務(wù)器是整個(gè)網(wǎng)絡(luò)的中心，失效將會(huì)導(dǎo)致服務(wù)無法訪問資源定義為網(wǎng)絡(luò)節(jié)點(diǎn)的計(jì)算、存儲(chǔ)等能力精選課件1.1 P2P引入背景(2)網(wǎng)絡(luò)邊緣閑置資源利用的需求隨著計(jì)算技術(shù)的發(fā)展,位于Internet邊緣的接入設(shè)備(也就是網(wǎng)絡(luò)的最終用戶)擁有越來越強(qiáng)的計(jì)算、存儲(chǔ)等能力，傳統(tǒng)的網(wǎng)絡(luò)結(jié)構(gòu)無法有效地利用這些資源資源定義為網(wǎng)絡(luò)節(jié)點(diǎn)的計(jì)算、存儲(chǔ)等能力精選課件1.1 P2P引入背景(3)P2P網(wǎng)絡(luò)服務(wù)器功能分布化分布式網(wǎng)絡(luò)結(jié)構(gòu)客戶/服務(wù)器模式的不足(瓶頸問題, 單點(diǎn)失效問題)2.網(wǎng)絡(luò)邊緣閑置資源的利用需求精選課件1.2 P2P網(wǎng)絡(luò)結(jié)構(gòu)完全分布式的網(wǎng)絡(luò)結(jié)構(gòu)將服務(wù)器的功能分布到各個(gè)

6、網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)，充分利用這些節(jié)點(diǎn)的計(jì)算、存儲(chǔ)、帶寬等資源無中心服務(wù)器，網(wǎng)絡(luò)中的節(jié)點(diǎn)既是客戶端又是服務(wù)器P2P網(wǎng)絡(luò)中的節(jié)點(diǎn)也叫做對(duì)等節(jié)點(diǎn)(Peer)精選課件1.3 P2P的定義P2P通信模式中各方都具有相同的能力，其中任何一方都可以發(fā)起一個(gè)通信會(huì)話。在P2P通信過程中，每個(gè)通信節(jié)點(diǎn)同時(shí)具有服務(wù)器和客戶端的功能。P2P網(wǎng)絡(luò)中的節(jié)點(diǎn)間采用P2P通信模式，它是構(gòu)筑在現(xiàn)有網(wǎng)絡(luò)基礎(chǔ)設(shè)施上的一個(gè)分布式的重疊網(wǎng)絡(luò)（Overlay Network）精選課件1.4 P2P重疊網(wǎng)P2P重疊網(wǎng)絡(luò)構(gòu)筑在已有的Internet基礎(chǔ)設(shè)施網(wǎng)絡(luò)之上，也稱為應(yīng)用層網(wǎng)絡(luò)InternetP2P網(wǎng)絡(luò)(overlay Network)

7、精選課件1.5 P2P網(wǎng)絡(luò)的特征P2P網(wǎng)絡(luò)是一個(gè)應(yīng)用層網(wǎng)絡(luò)，一般由網(wǎng)絡(luò)邊緣節(jié)點(diǎn)構(gòu)成網(wǎng)絡(luò)的擴(kuò)展性好，但節(jié)點(diǎn)可隨意加入退出，因而動(dòng)態(tài)性強(qiáng)資源分布在各個(gè)節(jié)點(diǎn)中，而不是集中在一個(gè)服務(wù)器上進(jìn)行管理節(jié)點(diǎn)之間可直接建立連接，交互共享資源精選課件1.6 P2P網(wǎng)絡(luò)需要解決的問題定位(Locating)：找到資源的存放位置路由(Routing)：將消息發(fā)送到目的節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)洌汗?jié)點(diǎn)的組織方式，例如物理網(wǎng)絡(luò)有星型拓?fù)?、網(wǎng)狀拓?fù)涞?，而?duì)于P2P網(wǎng)絡(luò)來說是拓?fù)涫且粋€(gè)邏輯上概念，和具體的物理連接無關(guān)P2P網(wǎng)絡(luò)的最終目標(biāo)是要實(shí)現(xiàn)資源共享，這些資源包括計(jì)算、存儲(chǔ)等，其中內(nèi)容存儲(chǔ)類應(yīng)用是P2P目前最主要的應(yīng)用物理網(wǎng)絡(luò)拓?fù)銹2P

8、邏輯拓?fù)渚x課件2. P2P網(wǎng)絡(luò)分類(1)非結(jié)構(gòu)化P2P網(wǎng)絡(luò)拓?fù)涫侨我獾膬?nèi)容的存儲(chǔ)位置與網(wǎng)絡(luò)拓?fù)錈o關(guān)結(jié)構(gòu)化P2P網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是有規(guī)律的每個(gè)節(jié)點(diǎn)都隨機(jī)生成一個(gè)標(biāo)識(shí)(ID)內(nèi)容的存儲(chǔ)位置與網(wǎng)絡(luò)拓?fù)湎嚓P(guān)內(nèi)容的存儲(chǔ)位置與節(jié)點(diǎn)標(biāo)識(shí)之間存在著映射關(guān)系精選課件2. P2P網(wǎng)絡(luò)分類(2)內(nèi)容索引在P2P網(wǎng)絡(luò)中，內(nèi)容一般使用內(nèi)容索引來表示,內(nèi)容索引包括key和value兩部分,其中key是內(nèi)容的關(guān)鍵字,value是存放內(nèi)容的實(shí)際位置,因此內(nèi)容索引也表示為對(duì)內(nèi)容索引表示電影夜宴可以從/yeyan.avi處獲得P2P網(wǎng)絡(luò)中實(shí)現(xiàn)內(nèi)容共享的步驟索引發(fā)布：告訴別人擁有或者知道的內(nèi)容信息內(nèi)容定位：查找到內(nèi)容所在的位置，即根

9、據(jù)key，找到value內(nèi)容下載：從value處下載內(nèi)容精選課件2.1 幾種非結(jié)構(gòu)化P2P完全分布式的P2P網(wǎng)絡(luò)不存在任何中心節(jié)點(diǎn)，peer通過網(wǎng)絡(luò)泛洪查找key所對(duì)應(yīng)的valuePeer之間直接建立連接下載內(nèi)容基于目錄服務(wù)器的P2P網(wǎng)絡(luò)所有peer將索引發(fā)布到目錄服務(wù)器上Peer通過目錄服務(wù)器來查找key所對(duì)應(yīng)的valuePeer之間直接建立連接下載內(nèi)容層次P2P網(wǎng)絡(luò)Peer根據(jù)能力的不同，例如是否擁有足夠強(qiáng)的計(jì)算存儲(chǔ)能力，是否擁有公網(wǎng)IP，分為超級(jí)節(jié)點(diǎn)和一般節(jié)點(diǎn)超級(jí)節(jié)點(diǎn)之間構(gòu)成完全分布式的P2P網(wǎng)絡(luò)超級(jí)節(jié)點(diǎn)和其所連接的一般節(jié)點(diǎn)構(gòu)成基于目錄服務(wù)器的P2P網(wǎng)絡(luò)，其中超級(jí)節(jié)點(diǎn)具有目錄服務(wù)器的功能

10、精選課件2.1.1 完全分布式的P2P網(wǎng)絡(luò)： Gnutella(1)擁有 xyz.mp3的節(jié)點(diǎn)擁有 xyz.mp3的節(jié)點(diǎn)誰擁有xyz.mp3?查詢Key=xyz.mp3應(yīng)答Value=IP下載精選課件2.1.1 完全分布式的P2P網(wǎng)絡(luò)： Gnutella(2)特點(diǎn)實(shí)現(xiàn)簡單、不存在單點(diǎn)失效問題，但泛洪即全網(wǎng)廣播查詢消息的增加了網(wǎng)絡(luò)負(fù)擔(dān)，而且隨著網(wǎng)絡(luò)規(guī)模的增大，查詢延時(shí)增加，因而不能保證查詢結(jié)果精選課件2.1.2 基于目錄服務(wù)器的P2P網(wǎng)絡(luò)： Napster(1)擁有xyz.mp3的節(jié)點(diǎn)發(fā)布(key=xyz.mp3, value = )Insert(xyz.mp3,)AIP=目錄服務(wù)器索引發(fā)布目錄

11、服務(wù)器上存儲(chǔ)的是內(nèi)容索引，而不是真正的內(nèi)容！精選課件2.1.2 基于目錄服務(wù)器的P2P網(wǎng)絡(luò)： Napster(2)內(nèi)容定位擁有xyz.mp3的節(jié)點(diǎn)AIP=目錄服務(wù)器誰擁有xyz.mp3?查詢Key=xyz.mp3應(yīng)答Value=Search(xyz.mp3)B精選課件2.1.2 基于目錄服務(wù)器的P2P網(wǎng)絡(luò)： Napster(3)內(nèi)容下載AIP=目錄服務(wù)器下載B直接從peer下載，不再需要經(jīng)過目錄服務(wù)器！擁有xyz.mp3的節(jié)點(diǎn)精選課件2.1.2 基于目錄服務(wù)器的P2P網(wǎng)絡(luò)： Napster(4)特點(diǎn)索引發(fā)布和內(nèi)容定位通過目錄服務(wù)器進(jìn)行,因此查詢簡單、高效，但是和客戶/服務(wù)器模式一樣，目錄服務(wù)器

12、存在瓶頸和單點(diǎn)失效問題，而且可擴(kuò)展性差精選課件2.1.3 層次P2P網(wǎng)絡(luò)： KazaA(1)索引發(fā)布擁有 xyz.mp3的節(jié)點(diǎn)發(fā)布(key=xyz.mp3,vaule=)Insert (xyz.mp3,)超級(jí)節(jié)點(diǎn)超級(jí)節(jié)點(diǎn)上存放有其連接的一般節(jié)點(diǎn)的內(nèi)容索引精選課件2.1.3 層次P2P網(wǎng)絡(luò)： KazaA(2)內(nèi)容定位誰擁有xyz.mp3?查詢Key=xyz.mp3應(yīng)答Value=超級(jí)節(jié)點(diǎn)Search(xyz.mp3)擁有 xyz.mp3的節(jié)點(diǎn)精選課件2.1.3 層次P2P網(wǎng)絡(luò)： KazaA(3)內(nèi)容下載超級(jí)節(jié)點(diǎn)擁有 xyz.mp3的節(jié)點(diǎn)下載直接從peer下載，不再需要經(jīng)過超級(jí)節(jié)點(diǎn)！精選課件2.1

13、.3 層次P2P網(wǎng)絡(luò)： KazaA(4)特點(diǎn)考慮到了節(jié)點(diǎn)能力的不同，將其分為一般節(jié)點(diǎn)和超級(jí)節(jié)點(diǎn)，泛洪只在超級(jí)節(jié)點(diǎn)之間進(jìn)行，與完全分布式的P2P網(wǎng)絡(luò)相比，減少了泛洪開銷當(dāng)網(wǎng)絡(luò)規(guī)模比較大時(shí)，隨著超級(jí)節(jié)點(diǎn)數(shù)量的增加，泛洪的范圍也將增大，因此查詢時(shí)間具有不確定性精選課件2.1.4 幾種非結(jié)構(gòu)化P2P總結(jié)非結(jié)構(gòu)化P2P的內(nèi)容下載采用完全在節(jié)點(diǎn)之間進(jìn)行,不需要任何中心節(jié)點(diǎn)但是內(nèi)容定位(也稱為索引查詢)或者采用泛洪,或者采用目錄服務(wù)器的方式,缺乏有效的、可擴(kuò)展的索引查詢機(jī)制，不能滿足大規(guī)模網(wǎng)絡(luò)的需求精選課件2.2 幾種結(jié)構(gòu)化P2PChordPastryCANTapestry基于分布式Hash表(DHT： D

14、istributed Hash Table )結(jié)構(gòu)化P2P: 直接根據(jù)查詢內(nèi)容的關(guān)鍵字定位其索引的存放節(jié)點(diǎn)精選課件2.2.1 Hash函數(shù)概述Hash函數(shù)可以根據(jù)給定的一段任意長的消息計(jì)算出一個(gè)固定長度的比特串，通常稱為消息摘要（MD：Message Digest），一般用于消息的完整性檢驗(yàn)。Hash函數(shù)有以下特性：給定 P，易于計(jì)算出 MD（P）只給出 MD（P），幾乎無法找出 P無法找到兩條具有同樣消息摘要的不同消息Hash函數(shù)MD5：消息摘要長度固定為128比特SHA-1：消息摘要長度固定為160比特精選課件2.2.1 Hash函數(shù)應(yīng)用于P2P的特性唯一性：不同的輸入明文，對(duì)應(yīng)著不同的輸

15、出摘要將節(jié)點(diǎn)IP地址的摘要作為節(jié)點(diǎn)ID，保證了節(jié)點(diǎn)ID在P2P環(huán)境下的唯一性SHA-1(“”) =24b92cb1d2b81a47472a93d06af3d85a42e463eaSHA-1(“”) =e1d9b25dee874b0c51db4c4ba7c9ae2b766fbf27精選課件2.2.2 DHT原理(1)將內(nèi)容索引抽象為對(duì)K是內(nèi)容關(guān)鍵字的Hash摘要K = Hash(key)V是存放內(nèi)容的實(shí)際位置，例如節(jié)點(diǎn)IP地址等所有的對(duì)組成一張大的Hash表，因此該表存儲(chǔ)了所有內(nèi)容的信息每個(gè)節(jié)點(diǎn)都隨機(jī)生成一個(gè)標(biāo)識(shí)(ID)，把Hash表分割成許多小塊，按特定規(guī)則(即K和節(jié)點(diǎn)ID之間的映射關(guān)系)分布

16、到網(wǎng)絡(luò)中去，節(jié)點(diǎn)按這個(gè)規(guī)則在應(yīng)用層上形成一個(gè)結(jié)構(gòu)化的重疊網(wǎng)絡(luò)給定查詢內(nèi)容的K值，可以根據(jù)K和節(jié)點(diǎn)ID之間的映射關(guān)系在重疊網(wǎng)絡(luò)上找到相應(yīng)的V值，從而獲得存儲(chǔ)文件的節(jié)點(diǎn)IP地址精選課件2.2.2 DHT原理(2)內(nèi)容內(nèi)容關(guān)鍵字key內(nèi)容存儲(chǔ)位置等信息value內(nèi)容索引K=Hash(key)提取k vHash表電影夜宴電影、夜宴/yeyan.avi內(nèi)容索引K=hash(電影, 夜宴)V = /yeyan.avi精選課件2.2.2 DHT原理(3)k va. Hash表b. 分布式Hash表規(guī)則?K VN1N48N16N32N8K VK VK VK VChord、CAN、Tapestry、Pastry

17、在許多情況下,節(jié)點(diǎn)ID為節(jié)點(diǎn)IP地址的Hash摘要精選課件2.2.2 DHT原理(4)插入(K1,V1)K VK VK VK VK VK VK VK VK VK VK V(K1,V1)查詢(K1)ABK1=Hash(xyz.mp3)V1=xyz.mp3C索引發(fā)布和內(nèi)容定位精選課件2.2.2 DHT原理(5)定位(Locating)節(jié)點(diǎn)ID和其存放的對(duì)中的K存在著映射關(guān)系，因此可以由K獲得存放該對(duì)的節(jié)點(diǎn)ID路由(Routing)在重疊網(wǎng)上根據(jù)節(jié)點(diǎn)ID進(jìn)行路由，將查詢消息最終發(fā)送到目的節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)需要到其鄰近節(jié)點(diǎn)的路由信息，包括節(jié)點(diǎn)ID、IP等網(wǎng)絡(luò)拓?fù)渫負(fù)浣Y(jié)構(gòu)由節(jié)點(diǎn)ID和其存放的對(duì)中的K之間的映

18、射關(guān)系決定拓?fù)鋭?dòng)態(tài)變化，需要處理節(jié)點(diǎn)加入/退出/失效的情況在重疊網(wǎng)上節(jié)點(diǎn)始終由節(jié)點(diǎn)ID標(biāo)識(shí)，并且根據(jù)ID進(jìn)行路由精選課件2.2.3 Chord：概述UC Berkeley和MIT共同提出采用環(huán)形拓?fù)?Chord環(huán))應(yīng)用程序接口Insert(K, V)將對(duì)存在放到節(jié)點(diǎn)ID為Successor(K)上Lookup(K)根據(jù)K查詢相應(yīng)的VUpdate(K, new_V)根據(jù)K更新相應(yīng)的VJoin(NID)節(jié)點(diǎn)加入Leave()節(jié)點(diǎn)主動(dòng)退出精選課件2.2.3 Chord：Hash表分布規(guī)則Hash算法SHA-1Hash節(jié)點(diǎn)IP地址m位節(jié)點(diǎn)ID(表示為NID)Hash內(nèi)容關(guān)鍵字m位K(表示為KID)節(jié)點(diǎn)

19、按ID從小到大順序排列在一個(gè)邏輯環(huán)上存儲(chǔ)在后繼節(jié)點(diǎn)上Successor(K)：從K開始順時(shí)針方向距離K最近的節(jié)點(diǎn) ID=hash(IP)=14N56K=hash(key)=54N1N8N14N21N32N38N42N48N51m=6精選課件2.2.3 Chord：簡單查詢過程每個(gè)節(jié)點(diǎn)僅維護(hù)其后繼節(jié)點(diǎn)ID、IP地址等信息查詢消息通過后繼節(jié)點(diǎn)指針在圓環(huán)上傳遞直到查詢消息中包含的K落在某節(jié)點(diǎn)ID和它的后繼節(jié)點(diǎn)ID之間速度太慢 O(N)，N為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)N56K54Lookup(K54)N56N1N8N14N21N32N38N42N48N51m=6精選課件2.2.3 Chord：指針表N56指針表N8

20、+1N8+2N8+4N8+8N8+16N8+32N14N14N14N21N32N42節(jié)點(diǎn)S的第i個(gè)指針successorn+2(i-1), 1im 精選課件2.2.3 Chord：基于指針表的擴(kuò)展查找過程指針表中有O (log N)個(gè)節(jié)點(diǎn)查詢經(jīng)過O (log N)跳N56K54指針表N8+1N8+2N8+4N8+8N8+16N8+32N14N14N14N21N32N42Lookup(K54)指針表N42+1N42+2N42+4N42+8N42+16N42+32N48N48N48N51N1N14精選課件2.2.3 Chord：網(wǎng)絡(luò)波動(dòng)(Churn)Churn由節(jié)點(diǎn)的加入、退出或者失效所引起每個(gè)節(jié)

21、點(diǎn)都周期性地運(yùn)行探測協(xié)議來檢測新加入節(jié)點(diǎn)或退出/失效節(jié)點(diǎn)，從而更新自己的指針表和指向后繼節(jié)點(diǎn)的指針 精選課件2.2.3 Chord：節(jié)點(diǎn)加入新節(jié)點(diǎn)N事先知道某個(gè)或者某些結(jié)點(diǎn)，并且通過這些節(jié)點(diǎn)初始化自己的指針表，也就是說，新節(jié)點(diǎn)N將要求已知的系統(tǒng)中某節(jié)點(diǎn)為它查找指針表中的各個(gè)表項(xiàng) 在其它節(jié)點(diǎn)運(yùn)行探測協(xié)議后，新節(jié)點(diǎn)N將被反映到相關(guān)節(jié)點(diǎn)的指針表和后繼節(jié)點(diǎn)指針中 新結(jié)點(diǎn)N的第一個(gè)后繼結(jié)點(diǎn)將其維護(hù)的小于N節(jié)點(diǎn)的ID的所有K交給該節(jié)點(diǎn)維護(hù)；精選課件2.2.3 Chord：節(jié)點(diǎn)退出/失效當(dāng)Chord中某個(gè)結(jié)點(diǎn)M退出/失效時(shí)，所有在指針表中包含該結(jié)點(diǎn)的結(jié)點(diǎn)將相應(yīng)指針指向大于M結(jié)點(diǎn)ID的第一個(gè)有效結(jié)點(diǎn)即節(jié)點(diǎn)M的

22、后繼節(jié)點(diǎn)為了保證節(jié)點(diǎn)M的退出/失效不影響系統(tǒng)中正在進(jìn)行的查詢過程，每個(gè)Chord節(jié)點(diǎn)都維護(hù)一張包括r個(gè)最近后繼節(jié)點(diǎn)的后繼列表。如果某個(gè)節(jié)點(diǎn)注意到它的后繼節(jié)點(diǎn)失效了，它就用其后繼列表中第一個(gè)正常節(jié)點(diǎn)替換失效節(jié)點(diǎn) 精選課件2.2.3 Chord：拓?fù)涫鋯栴}(1)O(LogN)邏輯跳數(shù)，但是每一邏輯跳可能跨越多個(gè)自治域，甚至是多個(gè)國家的網(wǎng)絡(luò)重疊網(wǎng)絡(luò)與物理網(wǎng)絡(luò)脫節(jié)實(shí)際的尋路時(shí)延較大精選課件2.2.3 Chord：拓?fù)涫鋯栴}(2)提取物理網(wǎng)絡(luò)的拓?fù)湫畔⒏脑霤hord存在w個(gè)界標(biāo)站點(diǎn)每個(gè)節(jié)點(diǎn)測量它到w個(gè)界標(biāo)的RTT將RTT遞增排列具有相同RTT序列的節(jié)點(diǎn)在物理網(wǎng)絡(luò)上臨近精選課件2.2.3 Chord：

23、總結(jié)算法簡單可擴(kuò)展：查詢過程的通信開銷和節(jié)點(diǎn)維護(hù)的狀態(tài)隨著系統(tǒng)總節(jié)點(diǎn)數(shù)增加成對(duì)數(shù)關(guān)系(O (log N)數(shù)量級(jí)) 拓?fù)涫鋯栴}精選課件2.2.4 Pastry：概述Microsoft研究院和Rice大學(xué)共同提出考慮網(wǎng)絡(luò)的本地性,解決物理網(wǎng)絡(luò)和邏輯網(wǎng)絡(luò)的拓?fù)涫涞膯栴}基于應(yīng)用層定義的鄰近性度量,例如IP路由跳數(shù)、地理距離、往返延時(shí)等節(jié)點(diǎn)ID分布采用環(huán)形結(jié)構(gòu)精選課件2.2.4 Pastry： Hash表分布規(guī)則Hash算法SHA-1Hash節(jié)點(diǎn)IP地址m位節(jié)點(diǎn)ID(表示為NID)Hash內(nèi)容關(guān)鍵字m位K(表示為KID)NID和KID是以2b為基的數(shù),共有m/b個(gè)數(shù)位b是一個(gè)配置參數(shù),一般為4節(jié)點(diǎn)按

24、ID從小到大順序排列在一個(gè)邏輯環(huán)上存儲(chǔ)在NID與KID數(shù)值最接近的節(jié)點(diǎn)上N0002N0201N0322N2001N1113N2120N2222N3001N3033N3200m=8K1320K1201K0220K2120K31222m-10b=2精選課件2.2.4 Pastry：節(jié)點(diǎn)維護(hù)狀態(tài)表(1)路由表R路由表包括 log2b N (m/b)行，每行包括2b -1個(gè)表項(xiàng) 路由表第n行與節(jié)點(diǎn)ID的前n個(gè)數(shù)位相同，但是第n+1個(gè)數(shù)位不同，也稱為n數(shù)位前綴相同路由表中的每項(xiàng)包含節(jié)點(diǎn)ID，IP地址等根據(jù)鄰近性度量選擇距離本節(jié)點(diǎn)近的節(jié)點(diǎn)鄰居節(jié)點(diǎn)集M鄰居節(jié)點(diǎn)集包含|M|個(gè)在鄰近性度量上最接近于本節(jié)點(diǎn)的節(jié)點(diǎn)

25、，|M|為2b或者2X2b 鄰居節(jié)點(diǎn)集通常不用于路由查詢消息，而是用來維護(hù)本地性葉子節(jié)點(diǎn)集L葉子節(jié)點(diǎn)集包含|L|個(gè)節(jié)點(diǎn)ID最接近本節(jié)點(diǎn)的節(jié)點(diǎn)，其中|L|/2個(gè)節(jié)點(diǎn)的ID大于本節(jié)點(diǎn)，|L|/2個(gè)ID小于本節(jié)點(diǎn)，|L|為2b或者2X2b 精選課件2.2.4 Pastry：節(jié)點(diǎn)維護(hù)狀態(tài)表(2)Node ID 10233102Leaf setRouting TableNeighborhood set0022121021223012033120320311301233122302031302102221003120310132102103233023310222302102002301021130210

26、230322102310001023212110233001102331201023323210213021022102002301130123331301233022121022230120331203203332133211023303310233021102331201023312210233001102330001023323010233232節(jié)點(diǎn)ID最接近本節(jié)點(diǎn)的節(jié)點(diǎn)b=2，因此節(jié)點(diǎn)ID的基數(shù)為4 (16 bits)m/b 行依據(jù)鄰近性度量最接近本節(jié)點(diǎn)的節(jié)點(diǎn)每行2b-1個(gè)表項(xiàng)第n行的前n個(gè)數(shù)位與本節(jié)點(diǎn)相同 相同前綴 下一數(shù)位 其它 當(dāng)前節(jié)點(diǎn)的第n個(gè)數(shù)位第m列表項(xiàng)的下一數(shù)位為m沒有合適

27、節(jié)點(diǎn)的表項(xiàng)為空b=2m=16精選課件2.2.4 Pastry：查詢過程當(dāng)一個(gè)K為D的查詢消息到達(dá)節(jié)點(diǎn)A節(jié)點(diǎn)A首先看D是否在當(dāng)前節(jié)點(diǎn)的葉子節(jié)點(diǎn)集中，如果是，則查詢消息直接被轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)，也就是葉子節(jié)點(diǎn)集中節(jié)點(diǎn)ID與D數(shù)值最接近的那個(gè)節(jié)點(diǎn)(有可能就是當(dāng)前節(jié)點(diǎn))，否則進(jìn)行下一步在路由表中查找與D具有更長相同前綴的表項(xiàng)(至少比本節(jié)點(diǎn)多一個(gè)數(shù)位)，如果該表項(xiàng)不為空，則將查詢消息直接轉(zhuǎn)發(fā)到該節(jié)點(diǎn)，否則進(jìn)行下一步例如路由D= 0629的查詢消息 5324 0748 0605 0620 0629將消息轉(zhuǎn)發(fā)到具有相同前綴,但是節(jié)點(diǎn)ID在數(shù)值上更接近D的節(jié)點(diǎn)。除非查詢消息已經(jīng)到達(dá)目的節(jié)點(diǎn)，否則該節(jié)點(diǎn)一定位于葉子

28、節(jié)點(diǎn)集中。例如路由D=0629的查詢消息5324 0748 0605 0609 0620 0629路由查詢消息的邏輯跳數(shù)： O(log2b N) 精選課件2.2.4 Pastry：節(jié)點(diǎn)狀態(tài)表和查詢節(jié)點(diǎn)路由表R中的每項(xiàng)與本節(jié)點(diǎn)具有相同的n數(shù)位長度前綴，但是下一個(gè)數(shù)位不同例如，對(duì)于節(jié)點(diǎn)N0201：N-: N1?, N2?, N3?N0: N00?, N01?, N03?N02: N021?, N022?, N023?N020: N0200, N0202, N0203當(dāng)有多個(gè)節(jié)點(diǎn)時(shí)，根據(jù)鄰近性度量選擇最近的節(jié)點(diǎn)維持了較好的本地性N0002N0201N2001N1113N2120N2222N3001N

29、3033N3200m=82m-10b=2N0122N0212N0221N0233RoutingtableK2120lookup(K2120)N0322精選課件2.2.4 Pastry：節(jié)點(diǎn)加入(1)初始化狀態(tài)表新節(jié)點(diǎn)開始時(shí)知道一個(gè)根據(jù)鄰近性度量接近自己的節(jié)點(diǎn)A節(jié)點(diǎn)A可以通過使用擴(kuò)展環(huán)IP組播等機(jī)制自動(dòng)定位，或者由系統(tǒng)管理員通過其它手段獲得新節(jié)點(diǎn)通過運(yùn)行SHA-1算法計(jì)算自己的IP地址(或者public key)的摘要得到節(jié)點(diǎn)ID為X節(jié)點(diǎn)X向節(jié)點(diǎn)A發(fā)送K為X的join消息，Pastry將該消息路由到節(jié)點(diǎn)ID在數(shù)值上最接近X的節(jié)點(diǎn)Z接收到j(luò)oin消息的節(jié)點(diǎn)，包括A、Z，以及A到Z路徑上所有的節(jié)點(diǎn)將

30、發(fā)送它們的狀態(tài)表給X，X檢查這些信息，并且可能從其它的節(jié)點(diǎn)請(qǐng)求狀態(tài)，然后節(jié)點(diǎn)根據(jù)下面的過程初始化狀態(tài)表:由于A與X在鄰近性度量上接近,所以使用A的鄰居節(jié)點(diǎn)集來初始化X的鄰居節(jié)點(diǎn)集由于Z的節(jié)點(diǎn)ID與X最相近,因此使用Z的葉子節(jié)點(diǎn)集來初始化X的葉子節(jié)點(diǎn)集X將join消息經(jīng)過的第i個(gè)節(jié)點(diǎn)的路由表的第i行作為自己路由表的第i行Join消息經(jīng)過的第i個(gè)節(jié)點(diǎn)與X的前i個(gè)數(shù)位相同向其它相關(guān)節(jié)點(diǎn)通告自己的到來新節(jié)點(diǎn)向鄰居節(jié)點(diǎn)集、葉子節(jié)點(diǎn)集和路由表中的每個(gè)節(jié)點(diǎn)發(fā)送自己的狀態(tài)，以更新這些節(jié)點(diǎn)的狀態(tài)表精選課件2.2.4 Pastry：節(jié)點(diǎn)加入(2)X0629節(jié)點(diǎn)加入Join消息A5324X 知道 A(A 與 X鄰近

31、)C0605Z0620B0748路由消息到節(jié)點(diǎn)ID在數(shù)值上最接近X的節(jié)點(diǎn)A鄰居節(jié)點(diǎn)集D的葉子節(jié)點(diǎn)集A0 ?B1 0?C2 06?D4 062?0629s routing table精選課件2.2.4 Pastry：節(jié)點(diǎn)退出/失效葉子節(jié)點(diǎn)集L中的節(jié)點(diǎn)失效：聯(lián)系L中失效節(jié)點(diǎn)一邊具有最大索引的存活節(jié)點(diǎn)(即節(jié)點(diǎn)ID最小或者最大的存活節(jié)點(diǎn))，并且請(qǐng)求該節(jié)點(diǎn)的葉子節(jié)點(diǎn)集除非|L|/2個(gè)節(jié)點(diǎn)同時(shí)失效，否恢復(fù)過程始終是有效的失效檢測：和葉子節(jié)點(diǎn)集中的節(jié)點(diǎn)周期性交互存活消息路由表R中的節(jié)點(diǎn)失效：如果失效節(jié)點(diǎn)對(duì)應(yīng)的表項(xiàng)為Rdl (第l行第d列) ，則聯(lián)系同一行中的Ril, id所指向的存活節(jié)點(diǎn)并且獲取該節(jié)點(diǎn)的Rd

32、l表項(xiàng)，如果l行中沒有存活節(jié)點(diǎn)，則從下一行選擇一個(gè)節(jié)點(diǎn)失效檢測：和路由表中的節(jié)點(diǎn)聯(lián)系(例如發(fā)送查詢消息)如果無反應(yīng)則檢測到節(jié)點(diǎn)失效鄰居節(jié)點(diǎn)表M中的節(jié)點(diǎn)失效：向M中的其它節(jié)點(diǎn)請(qǐng)求鄰居節(jié)點(diǎn)表，檢查每個(gè)新發(fā)現(xiàn)節(jié)點(diǎn)的距離(根據(jù)鄰近性度量)，然后更新自己的鄰居節(jié)點(diǎn)表失效檢測：和鄰居節(jié)點(diǎn)表中的每個(gè)節(jié)點(diǎn)周期性的聯(lián)系，以確認(rèn)節(jié)點(diǎn)存活精選課件2.2.4 Pastry：路由本地性根據(jù)鄰近性度量為消息選擇一條好的路由鄰近性度量包括IP路由跳數(shù)、地理距離、往返延時(shí)等應(yīng)用層為每個(gè)節(jié)點(diǎn)提供了根據(jù)鄰近性度量確定到其它節(jié)點(diǎn)距離的功能，例如traceroute等新節(jié)點(diǎn)加入過程保持了本地性首先：A必定與X相接近A路由表中第0行表

33、項(xiàng)A0與A相接近，而A與X接近，因此X0可作為X0由于節(jié)點(diǎn)路由表中的下一行節(jié)點(diǎn)的可選擇集合指數(shù)遞減,因此B1中的節(jié)點(diǎn)到B的距離要比A到比的距離大得多(B在A0中),因此B1可作為X1,依此類推,C2可作為X2X向路由表和鄰居節(jié)點(diǎn)集中的每個(gè)節(jié)點(diǎn)請(qǐng)求狀態(tài),并且使用更近的節(jié)點(diǎn)來更新自己的狀態(tài)由于鄰居節(jié)點(diǎn)集根據(jù)鄰近性度量而不是節(jié)點(diǎn)ID前綴來維護(hù)節(jié)點(diǎn)信息,因此在這個(gè)過程中發(fā)揮重要作用實(shí)踐中Pastry保持了良好的本地性伸展度(Stretch)大約為23伸展度(Stretch)：邏輯網(wǎng)絡(luò)的路由延時(shí)/IP網(wǎng)絡(luò)的單播路由延時(shí)精選課件2.2.4 Pastry：總結(jié)邏輯網(wǎng)絡(luò)路由跳數(shù)O(log2b N) 路由表開銷

34、log2b N *(2b -1)路由本地性：狀態(tài)表(路由表、鄰居節(jié)點(diǎn)集、葉子節(jié)點(diǎn)集)中的表項(xiàng)選擇在鄰近性度量上與本節(jié)點(diǎn)相近的節(jié)點(diǎn)穩(wěn)健性：只有在|L|/2個(gè)葉子節(jié)點(diǎn)完全失效時(shí)才會(huì)路由失敗精選課件2.2.5 CAN：概述Content Addressable Network，內(nèi)容尋址網(wǎng)絡(luò)UC Berkeley提出節(jié)點(diǎn)ID分布分布在d維笛卡爾坐標(biāo)空間坐標(biāo)空間完全是邏輯的，和任何物理坐標(biāo)沒有任何關(guān)系精選課件2.2.5 CAN：Hash表分布規(guī)則每個(gè)節(jié)點(diǎn)都維護(hù)d維笛卡爾坐標(biāo)空間中的一塊區(qū)域新加入節(jié)點(diǎn)時(shí)劃分坐標(biāo)空間對(duì)于每個(gè)，通過Hash函數(shù)將K映射到坐標(biāo)空間中的某點(diǎn)P，存儲(chǔ)在維護(hù)該點(diǎn)所在區(qū)域的節(jié)點(diǎn)上在每一

35、維都對(duì)k進(jìn)行hash運(yùn)算1121231432d=2hx(k)hy(k)insert(k,data)retrieve(k)精選課件2.2.5 CAN：查詢過程節(jié)點(diǎn)在坐標(biāo)路由表中只需維護(hù)它直接鄰居的信息，包括鄰居的IP地址及其維護(hù)的區(qū)域兩個(gè)節(jié)點(diǎn)互為鄰居是指：在d維坐標(biāo)空間中，兩個(gè)節(jié)點(diǎn)維護(hù)的區(qū)域在d1維的坐標(biāo)上有重疊而在剩下的一維坐標(biāo)上相互鄰接，例如圖中節(jié)點(diǎn)A的鄰居為(N, S, E, W)查詢消息沿著坐標(biāo)空間從發(fā)起請(qǐng)求的點(diǎn)到目的點(diǎn)之間的一條路徑轉(zhuǎn)發(fā)查詢消息路由到能夠減少坐標(biāo)空間距離的鄰居節(jié)點(diǎn)有多條路徑可以選擇，在路由時(shí)能夠繞開失效節(jié)點(diǎn)WNASEBd=2精選課件2.2.5 CAN：節(jié)點(diǎn)加入新加入的節(jié)

36、點(diǎn)在CAN中查找已經(jīng)存在的節(jié)點(diǎn)，即bootstrap節(jié)點(diǎn)找到可以劃分空間的一個(gè)節(jié)點(diǎn)進(jìn)行空間劃分bootstrap節(jié)點(diǎn)提供系統(tǒng)中有效的并且可以劃分區(qū)間的節(jié)點(diǎn)A，新節(jié)點(diǎn)向節(jié)點(diǎn)A發(fā)送一個(gè)加入消息，該消息經(jīng)過CAN的路由機(jī)制發(fā)送到A 通知被劃分的節(jié)點(diǎn)的鄰居節(jié)點(diǎn)進(jìn)行路由表更新節(jié)點(diǎn)F的鄰居表是由節(jié)點(diǎn)A的鄰居節(jié)點(diǎn)的子集合，再加上節(jié)點(diǎn)A構(gòu)成節(jié)點(diǎn)A刷新它的鄰居節(jié)點(diǎn)空間，以刪除那些現(xiàn)在已不是鄰居節(jié)點(diǎn)的節(jié)點(diǎn) 新節(jié)點(diǎn)F發(fā)送刷新信息更新鄰居節(jié)點(diǎn)的坐標(biāo)路由表 bootstrapd=2AFBCDEGC精選課件2.2.5 CAN：節(jié)點(diǎn)退出/失效(1)失效檢測每個(gè)節(jié)點(diǎn)周期性向鄰居節(jié)點(diǎn)發(fā)送更新消息，如果消息中包括自身的區(qū)域范圍、

37、它的鄰居列表以及這些鄰居節(jié)點(diǎn)負(fù)責(zé)的區(qū)域范圍。如果多次沒有接收到某個(gè)鄰居的更新消息，那么節(jié)點(diǎn)就認(rèn)為這個(gè)鄰居失效了，這時(shí)將啟動(dòng)接管機(jī)制精選課件2.2.5 CAN：節(jié)點(diǎn)退出/失效(2)接管機(jī)制當(dāng)節(jié)點(diǎn)離開CAN時(shí)，必須保證它的區(qū)域被系統(tǒng)中剩余的節(jié)點(diǎn)接管，也即分配給其他仍然在系統(tǒng)中的節(jié)點(diǎn)。一般是由某個(gè)鄰居節(jié)點(diǎn)來接管這個(gè)區(qū)域和所有的索引數(shù)據(jù)（K，V）對(duì)接管鄰居節(jié)點(diǎn)的選擇如果某個(gè)鄰居節(jié)點(diǎn)負(fù)責(zé)的區(qū)域可以和離開節(jié)點(diǎn)負(fù)責(zé)的區(qū)域合并形成一個(gè)大的區(qū)域，那么將由這個(gè)鄰居節(jié)點(diǎn)執(zhí)行合并操作 否則該區(qū)域?qū)⒔唤o其鄰居節(jié)點(diǎn)中區(qū)域最小的節(jié)點(diǎn)負(fù)責(zé) 失效節(jié)點(diǎn)的每個(gè)鄰居獨(dú)立地啟動(dòng)一個(gè)時(shí)鐘，每個(gè)時(shí)鐘大小都和相應(yīng)節(jié)點(diǎn)負(fù)責(zé)的區(qū)域面積成比例。如

38、果時(shí)鐘超時(shí)，節(jié)點(diǎn)將向失效節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)發(fā)送接管消息，該消息中包括它自己的區(qū)域面積信息。當(dāng)某個(gè)節(jié)點(diǎn)接收到接管消息后，如果它的區(qū)域面積比發(fā)出消息的節(jié)點(diǎn)大，那么它將取消接管操作。否則它將發(fā)出自己的取代消息精選課件A2.2.5 CAN：節(jié)點(diǎn)退出/失效(3)ABBBB節(jié)點(diǎn)失效后的區(qū)間合并 節(jié)點(diǎn)失效后由面積最小的鄰居節(jié)點(diǎn)接管精選課件2.2.5 CAN：負(fù)載均衡問題(1)負(fù)載均衡節(jié)點(diǎn)負(fù)擔(dān)的面積越大，負(fù)載就越重假設(shè)整個(gè)坐標(biāo)空間的面積是S ，整個(gè)空間中共有n個(gè)節(jié)點(diǎn)，那么理想情況的均衡劃分的結(jié)果應(yīng)該是每個(gè)節(jié)點(diǎn)的面積都是V=S/n采用原始CAN節(jié)點(diǎn)加入劃分機(jī)制，只有43%的節(jié)點(diǎn)面積為V精選課件2.2.5 CAN

39、：負(fù)載均衡問題(2)解決方案組播法尋找重負(fù)荷節(jié)點(diǎn)新加入系統(tǒng)的節(jié)點(diǎn)首先通過引導(dǎo)節(jié)點(diǎn)在全網(wǎng)范圍內(nèi)泛洪查找面積最大的節(jié)點(diǎn)，對(duì)其空間進(jìn)行劃分邏輯結(jié)構(gòu)自適應(yīng)調(diào)整法通過目的節(jié)點(diǎn)向所有四周鄰居進(jìn)行泛洪，獲取面積最大的節(jié)點(diǎn)，劃分此節(jié)點(diǎn)空間缺點(diǎn)：需要泛洪消息，網(wǎng)絡(luò)開銷太大精選課件2.2.5 CAN：總結(jié)可擴(kuò)展性：如果d維坐標(biāo)空間劃分成N個(gè)相等的區(qū)域，則每個(gè)節(jié)點(diǎn)維護(hù)2d個(gè)鄰居節(jié)點(diǎn)的信息平均路由跳數(shù)(dN1/d)/4 增加維數(shù)可以減少在邏輯上的路由跳數(shù)，但是增加了節(jié)點(diǎn)維護(hù)的狀態(tài)信息節(jié)點(diǎn)增加時(shí)節(jié)點(diǎn)維護(hù)的狀態(tài)信息不變，而路由長度只是以O(shè)(N1/d)的數(shù)量級(jí)增長，可擴(kuò)展性好穩(wěn)健性：一個(gè)節(jié)點(diǎn)的一個(gè)或幾個(gè)鄰居節(jié)點(diǎn)失效時(shí)，它依

40、然可以沿著有效的鄰居節(jié)點(diǎn)進(jìn)行尋路負(fù)載均衡問題拓?fù)涫鋯栴}精選課件2.2.6 基于DHT的結(jié)構(gòu)化P2P比較ChordPastryCAN拓?fù)浣Y(jié)構(gòu)節(jié)點(diǎn)ID分布在單向環(huán)形空間節(jié)點(diǎn)ID分布在單向環(huán)形空間，并且表示為以2b為基的數(shù)節(jié)點(diǎn)分布在d維笛卡爾坐標(biāo)空間存儲(chǔ)儲(chǔ)存在K的后繼節(jié)點(diǎn)即節(jié)點(diǎn)ID大于K的第一個(gè)節(jié)點(diǎn)上存儲(chǔ)在節(jié)點(diǎn)ID與K最接近的節(jié)點(diǎn)上通過在每一維對(duì)K進(jìn)行Hash運(yùn)算將K映射到坐標(biāo)空間中的一點(diǎn)，存儲(chǔ)在維護(hù)該點(diǎn)所在區(qū)域的節(jié)點(diǎn)上路由查詢消息通過后繼節(jié)點(diǎn)指針或者指針表找到K的后繼節(jié)點(diǎn)比較K和節(jié)點(diǎn)ID的前綴，下一跳節(jié)點(diǎn)的ID具有更長的前綴或者在數(shù)值上更接近K下一跳節(jié)點(diǎn)在坐標(biāo)空間上距離目標(biāo)節(jié)點(diǎn)更近節(jié)點(diǎn)維護(hù)狀態(tài)后

41、繼節(jié)點(diǎn)指針或者指針表：O(logN)葉子節(jié)點(diǎn)集、鄰居節(jié)點(diǎn)集：2b或者2*2b路由表：log2bN*(2b-1)坐標(biāo)路由表：平均2d路由性能O(logN)O(log log2bN)(dN1/d)/4 穩(wěn)健性維護(hù)r個(gè)最近的后繼節(jié)點(diǎn)只有在|L|/2個(gè)葉子節(jié)點(diǎn)完全失效時(shí)才會(huì)路由失敗鄰居節(jié)點(diǎn)失效時(shí)沿其它有效鄰居節(jié)點(diǎn)路由路由本地性狀態(tài)表(路由表、鄰居節(jié)點(diǎn)集、葉子節(jié)點(diǎn)集)中表項(xiàng)選擇在鄰近性度量上與本節(jié)點(diǎn)相近的節(jié)點(diǎn)精選課件2.2.7 幾種結(jié)構(gòu)化P2P總結(jié)完全分布式，不存在任何中心節(jié)點(diǎn)直接根據(jù)查詢內(nèi)容的關(guān)鍵字定位其索引的存放節(jié)點(diǎn)，查找具有確定性節(jié)點(diǎn)失效時(shí)表現(xiàn)出很好的健壯性 可擴(kuò)展性好，系統(tǒng)開銷小自動(dòng)配置，不需要

42、手工干預(yù)就可自動(dòng)把新加入節(jié)點(diǎn)合并到系統(tǒng)中幾個(gè)需要研究的問題模糊查找問題網(wǎng)絡(luò)波動(dòng)(Churn)問題路由本地性問題負(fù)載均衡問題安全問題精選課件2.2.8 基于DHT的P2P應(yīng)用DHT接口APIDHT層次體系結(jié)構(gòu)OpenDHTIndirect Internet Infrastructure (i3)精選課件DHT接口API必須的接口Inset(K, V)：將存儲(chǔ)到合適的節(jié)點(diǎn)上Lookup(K) ：獲取K所對(duì)應(yīng)的V，例如節(jié)點(diǎn)IP地址支持各種應(yīng)用K不需要任何語義上的意義V與應(yīng)用相關(guān)具體的API在底層的DHT重疊網(wǎng)絡(luò)中實(shí)現(xiàn)Lookup(K)Return Value精選課件DHT層次體系結(jié)構(gòu)DHT層,例如C

43、hord，Pastry，CAN等(自組織的重疊網(wǎng)絡(luò))精選課件基于DHT的P2P應(yīng)用File sharing CFS, PAST, Event notification ScribeNaming systems ChordDNS, Query and indexing Kademlia, Communication primitives I3, .精選課件OpenDHT：概述OpenDHT一個(gè)公共的DHT服務(wù)平臺(tái)htpp:/基于Bamboo DHT，改寫自Pastry設(shè)計(jì)原則：易于部署，易于使用客戶端不需要運(yùn)行DHT軟件，而是通過OpenDHT服務(wù)平臺(tái)獲取所需的服務(wù)，從而實(shí)現(xiàn)基于DHT的P2P應(yīng)

44、用客戶端接口APIPut(K, V, t)：將發(fā)布到OpenDHT網(wǎng)絡(luò)，t為有效期Get(K)：根據(jù)K從OpenDHT網(wǎng)絡(luò)獲取對(duì)精選課件OpenDHT：體系結(jié)構(gòu)精選課件Indirect Internet Infrastructure (i3)傳統(tǒng)的Internet提供端到端通信模型通信一般在固定主機(jī)之間進(jìn)行發(fā)送主機(jī)知道接收主機(jī)的IP地址，將分組直接發(fā)送給接收主機(jī)間接通信模型(i3)接收主機(jī)位置不固定，可能移動(dòng)Mobility發(fā)送主機(jī)不知道接收主機(jī)的標(biāo)識(shí)Multicast, Anycast精選課件i3原理(1)利用DHT網(wǎng)絡(luò)提供的索引發(fā)布和查詢，具有穩(wěn)健性高效性可擴(kuò)展性DHT網(wǎng)絡(luò)實(shí)現(xiàn)可以使Cho

45、rd、Pastry、CAN、Tapestry等DHT網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)都為i3服務(wù)器i3中節(jié)點(diǎn)通信過程每個(gè)分組都帶有一個(gè)標(biāo)識(shí)，接收主機(jī)根據(jù)標(biāo)識(shí)來獲取相應(yīng)的分組接收主機(jī)在DHT網(wǎng)絡(luò)中插入trigger (id, R), 其中id為希望接收的分組的標(biāo)識(shí)，R是接收主機(jī)的IP地址， (id, R)根據(jù)id存儲(chǔ)到DHT網(wǎng)絡(luò)中相應(yīng)的服務(wù)器節(jié)點(diǎn)（例如對(duì)于chord，(id, R)存儲(chǔ)在id的后繼節(jié)點(diǎn)即節(jié)點(diǎn)ID大于id的第一個(gè)節(jié)點(diǎn)上）發(fā)送主機(jī)發(fā)送標(biāo)識(shí)為id的分組，該分組以id為k，根據(jù)DHT路由查詢算法在網(wǎng)絡(luò)中轉(zhuǎn)發(fā)，如果接收到該分組的服務(wù)器注冊(cè)了標(biāo)識(shí)為id的trigger，則將分組發(fā)送給trigger中指定的

46、接收主機(jī)IP精選課件i3原理(2)DHT網(wǎng)絡(luò)DHT網(wǎng)絡(luò)a. 接收主機(jī)R在DHT網(wǎng)絡(luò)中插入trigger(id, R)b. 發(fā)送主機(jī)向DHT網(wǎng)絡(luò)發(fā)送分組(id, data)，該分組被DHT網(wǎng)絡(luò)中的服務(wù)器轉(zhuǎn)發(fā)給相應(yīng)的接收主機(jī)精選課件I3原理(3)應(yīng)用程序接口APIsendPacket(p)：發(fā)送分組insertTrigger(t)：插入triggerremoveTrigger(t)：刪除trigger基于OpenDHT的實(shí)現(xiàn)需要擴(kuò)展put/get接口以實(shí)現(xiàn)服務(wù)器轉(zhuǎn)發(fā)功能Sean Rhea, Brighten Godfrey, et al., OpenDHT: A Public DHT Servic

47、e and Its Uses, Proceedings of ACM SIGCOMM 2005, August 2005精選課件i3應(yīng)用：移動(dòng)Mobility移動(dòng)對(duì)于發(fā)送節(jié)點(diǎn)完全透明，接收節(jié)點(diǎn)只需更新相應(yīng)的trigger精選課件i3應(yīng)用：組播組播接收節(jié)點(diǎn)向DHT網(wǎng)絡(luò)插入具有相同標(biāo)識(shí)的trigger精選課件i3應(yīng)用：大規(guī)模組播使用層次觸發(fā)器構(gòu)造組播樹,以減輕服務(wù)器的負(fù)擔(dān)具有相同標(biāo)識(shí)的trigger的數(shù)量代表在服務(wù)器上分組的復(fù)制因子需要分布式算法來構(gòu)造和維護(hù)trigger的層次LAKSHMINARAYANAN, K., RAO, et al. Flexible and robust large s

48、cale multicast using i3. Tech. Rep. CS-02-1187, University of California-Berkeley, 2002.精選課件應(yīng)用層網(wǎng)絡(luò)對(duì)等網(wǎng)絡(luò)應(yīng)用層組播彈性重疊網(wǎng)精選課件Resources章淼,吳建平, 應(yīng)用層組播研究綜述, 清華大學(xué)計(jì)算機(jī)系網(wǎng)絡(luò)研究所，2003 Yeo C K,Lee B S,Er M H.A, A survey of application level multicast techniques, Computer Communications,2004ESMY Chu, S Rao, S Seshan, H Zha

49、ng, R Vedantham, Enabling conferencing applications on the internet using an overlay muilticast architecture, In Proceedings of ACM SIGCOMM Computer Communication Review, 2001 HMTPB Zhang, S Jamin, L Zhang, Host Multicast: A Framework for Delivering Multicast To End Users, in Proceedings of IEEE INF

50、OCOM, 2002 NICES Banerjee, B Bhattacharjee, C Kommareddy, Scalable Application Layer Multicast, in Proceedings of ACM SIGCOMM 2002;精選課件應(yīng)用層組播IP組播回顧應(yīng)用層組播概述應(yīng)用層組播技術(shù)應(yīng)用層組播評(píng)價(jià)指標(biāo)應(yīng)用層組播方案舉例總結(jié)精選課件應(yīng)用層組播1.IP組播回顧IP組播概述IP組播體系結(jié)構(gòu)IP組播的局限性2.應(yīng)用層組播概述3.應(yīng)用層組播技術(shù)4.應(yīng)用層組播評(píng)價(jià)指標(biāo)5.應(yīng)用層組播方案舉例6.總結(jié)精選課件1.1 IP組播概述組播(Multicast)也稱為多播，發(fā)送分組

51、給一群感興趣的接收者，包括1對(duì)多、多對(duì)多模式可用于會(huì)議電視，分布式計(jì)算，視頻轉(zhuǎn)播，網(wǎng)絡(luò)游戲，討論組等應(yīng)用IP組播由網(wǎng)絡(luò)層來復(fù)制和轉(zhuǎn)發(fā)分組給接收者IP組播采用特定的地址格式844112比特1111 1111標(biāo)志區(qū)域Group ID428比特1110Group IDIPv6組播地址格式IPv4組播地址格式精選課件單播和組播單播：發(fā)送端向每個(gè)接收端都發(fā)送單播分組，路由器只轉(zhuǎn)發(fā)分組組播：發(fā)送端只發(fā)送一份分組，路由器根據(jù)需要復(fù)制并且向接收端轉(zhuǎn)發(fā)分組組播與單播相比，有效地降低了網(wǎng)絡(luò)負(fù)載精選課件1.2 IP組播體系結(jié)構(gòu)組播路由協(xié)議，如DVMRP，PIM功能：構(gòu)造連接擁有組成員的組播路由器的組播樹，以路由轉(zhuǎn)發(fā)

52、組播分組組播管理協(xié)議，IGMP功能：組成員的加入和退出路由器之間主機(jī)和路由器之間IP組播需要網(wǎng)絡(luò)即路由器支持精選課件組播樹基于源的組播樹最短路徑樹，每個(gè)源都會(huì)通過最有效的路徑向每個(gè)接收端發(fā)送分組路由器必須跟蹤所有的源，需要更多的存儲(chǔ)資源共享組播樹組播分組先被發(fā)送到一個(gè)公共點(diǎn)(也稱為集合點(diǎn))，再從該點(diǎn)發(fā)送到各個(gè)接收端所需的存儲(chǔ)資源較少，但是并不總能使用最短路徑精選課件1.4 IP組播的局限性可擴(kuò)展性問題路由器需要為每個(gè)組維護(hù)狀態(tài)，有時(shí)甚至需要為組播組中的每個(gè)源維護(hù)狀態(tài)組播地址不易實(shí)現(xiàn)聚合，路由器的路由表和轉(zhuǎn)發(fā)表需要為每個(gè)組播組維護(hù)一個(gè)表項(xiàng)難以支持高層功能IP組播提供盡力(best-effort)

53、多點(diǎn)傳送業(yè)務(wù)，終端系統(tǒng)負(fù)責(zé)處理高層功能在IP組播中實(shí)現(xiàn)可靠性和擁塞控制非常復(fù)雜試圖用統(tǒng)一的組播模型來適應(yīng)所有的應(yīng)用缺乏有效的網(wǎng)絡(luò)管理和計(jì)費(fèi)模型IP組播大規(guī)模部署困難而緩慢應(yīng)用層（或者終端系統(tǒng)end-system）組播的出現(xiàn)導(dǎo)致精選課件應(yīng)用層組播1.IP組播回顧2.應(yīng)用層組播概述應(yīng)用層組播概念應(yīng)用層組播優(yōu)勢應(yīng)用層組播應(yīng)用3.應(yīng)用層組播技術(shù)4.應(yīng)用層組播評(píng)價(jià)指標(biāo)5.應(yīng)用層組播方案舉例6.總結(jié)精選課件2.1 應(yīng)用層組播概念A(yù)pplication-Layer (or end-system) Multicast終端系統(tǒng)通過重疊網(wǎng)進(jìn)行通信，由終端節(jié)點(diǎn)來進(jìn)行分組的復(fù)制和轉(zhuǎn)發(fā)即組播功能底層網(wǎng)絡(luò)只提供單播功能I

54、P組播應(yīng)用層組播IP組播的帶寬利用率最高，但是實(shí)驗(yàn)表明只要重疊網(wǎng)構(gòu)建適當(dāng)，應(yīng)用層組播能達(dá)到“合理”的開銷精選課件2.2 應(yīng)用層組播優(yōu)勢可擴(kuò)展性好不需要路由器支持，因此也就不需要路由器為組播組維護(hù)狀態(tài)端系統(tǒng)維護(hù)組播組狀態(tài)，但由于端系統(tǒng)只會(huì)加入少量的組播組，因此開銷不大易于部署不需要網(wǎng)絡(luò)（路由器）支持簡化了對(duì)高層功能的支持端系統(tǒng)根據(jù)自身的資源（例如計(jì)算、存儲(chǔ)等）做出合理的決策計(jì)算和存儲(chǔ)均衡，例如緩存分組，編碼轉(zhuǎn)換(transcoding)，ACK聚合等端系統(tǒng)可以使用已有的基于單播的解決方案來實(shí)現(xiàn)可靠性和擁塞控制靈活地根據(jù)應(yīng)用需求增加各種特性精選課件2.3 應(yīng)用層組播應(yīng)用視頻會(huì)議流媒體分發(fā),例如視頻

55、廣播訂閱/分發(fā)系統(tǒng)(Publish/Subscribe System)主要用于實(shí)時(shí)流媒體的傳輸,所以也稱為P2P Streaming精選課件應(yīng)用層組播1.IP組播回顧應(yīng)用層組播概述3.應(yīng)用層組播技術(shù)應(yīng)用層組播要素Mesh-first方法Tree-first方法Implicit方法4. 應(yīng)用層組播評(píng)價(jià)指標(biāo)5.應(yīng)用層組播方案舉例6.總結(jié)精選課件3.1 應(yīng)用層組播要素控制拓?fù)淇刂仆負(fù)渲械慕M成員周期性的交互刷新消息以相互標(biāo)識(shí)身份并從節(jié)點(diǎn)失效中恢復(fù)控制拓?fù)湟话憔哂芯W(wǎng)狀結(jié)構(gòu)，也稱為網(wǎng)(Mesh)數(shù)據(jù)拓?fù)鋽?shù)據(jù)拓?fù)渫ǔＪ强刂仆負(fù)涞淖蛹?，它用于?biāo)識(shí)組播轉(zhuǎn)發(fā)分組時(shí)使用的路徑數(shù)據(jù)拓?fù)湟话銥闃錉罱Y(jié)構(gòu)，被稱為樹(Tre

56、e) 控制消息 精選課件應(yīng)用層組播分類根據(jù)構(gòu)造控制拓?fù)浜蛿?shù)據(jù)拓?fù)涞捻樞?，?yīng)用層組播可以分為3類Mesh-first方法Tree-first方法Implicit方法精選課件3.2 Mesh-first方法首先，組成員構(gòu)造一個(gè)基于應(yīng)用層的重疊網(wǎng)絡(luò)作為自己的控制拓?fù)淦浯?，在重疊網(wǎng)上使用標(biāo)準(zhǔn)的組播路由協(xié)議例如DVMRP (Distance Vector Multicast Routing Protocol) 生成基于源的組播樹(數(shù)據(jù)拓?fù)?典型方法：ESM、ScatterCast等 精選課件3.3 Tree-first方法首先，組成員采用分布式算法構(gòu)建共享組播樹(數(shù)據(jù)拓?fù)?其次，然后各個(gè)組成員通過主動(dòng)探

57、測，發(fā)現(xiàn)該組播樹中的其它節(jié)點(diǎn)（不一定是自己鄰居節(jié)點(diǎn)），并和這些節(jié)點(diǎn)保持控制連接控制拓?fù)?共享組播樹+控制連接典型方法：HMTP、Yoid、ALMI等 根節(jié)點(diǎn)精選課件3.4 Implicit方法使用面向大規(guī)模P2P網(wǎng)絡(luò)的路由機(jī)制創(chuàng)建帶有某些特殊屬性的控制拓?fù)?。在控制拓?fù)渲芯碗[含定義了數(shù)據(jù)轉(zhuǎn)發(fā)路徑Mesh和Tree同時(shí)根據(jù)應(yīng)用層網(wǎng)絡(luò)路由機(jī)制創(chuàng)建，組成員之間并不需要進(jìn)行額外的信息交互典型方法： NICE、CAN、Bayeux等精選課件應(yīng)用層組播1.IP組播回顧應(yīng)用層組播概述應(yīng)用層組播分類4. 應(yīng)用層組播評(píng)價(jià)指標(biāo)分組轉(zhuǎn)發(fā)路徑質(zhì)量協(xié)議開銷網(wǎng)絡(luò)動(dòng)態(tài)自適應(yīng)性其它性能指標(biāo)5.應(yīng)用層組播方案舉例6.總結(jié)精選課件

58、3.1 分組轉(zhuǎn)發(fā)路徑質(zhì)量強(qiáng)度(stress)：每條鏈路或者每個(gè)路由器在傳輸組播分組時(shí)發(fā)送相同分組的次數(shù)IP組播不進(jìn)行多余的復(fù)制，因此強(qiáng)度總是1 伸展度(stretch)：平均每個(gè)組成員在重疊網(wǎng)絡(luò)中的從源到目的的距離和對(duì)應(yīng)的單播路徑距離的比值精選課件示例圖(c)中,AB間伸展度1,AD為6/4=1.5,AC間為9/3=3,因此總的伸展度為: (1+1.5+3)/3=1.83(a) IP組播(b) IP單播(c) 應(yīng)用層組播(d) 應(yīng)用層組播精選課件3.2 協(xié)議開銷協(xié)議開銷=所有非數(shù)據(jù)業(yè)務(wù)/所有數(shù)據(jù)業(yè)務(wù)非數(shù)據(jù)業(yè)務(wù)控制消息網(wǎng)絡(luò)測量消息精選課件3.3 網(wǎng)絡(luò)動(dòng)態(tài)自適應(yīng)性當(dāng)節(jié)點(diǎn)/鏈路失效時(shí)，節(jié)點(diǎn)的發(fā)現(xiàn)、反

59、應(yīng)以及修復(fù)時(shí)間發(fā)現(xiàn)(Discovery)：節(jié)點(diǎn)/鏈路失效到檢測到鏈路惡化的時(shí)間反應(yīng)(React)：檢測到鏈路惡化到初次改變組播樹的時(shí)間修復(fù)(Repair)：初次改變組播樹到完全修復(fù)組播樹的時(shí)間Discover TimeReact TimeRepair TimeLink failureDetectedFirst attemptLast attempt精選課件3.4 其它性能指標(biāo)數(shù)據(jù)傳輸延時(shí)(Delay)失效容忍度(Failure Tolerance)單點(diǎn)失效例如集合點(diǎn)(RP: Rendezvous Point )大量節(jié)點(diǎn)/鏈路失效可擴(kuò)展性(Scalability)用來建立大規(guī)模組播樹所需的時(shí)間和

60、資源可擴(kuò)展性受限于：組播路由算法協(xié)議開銷精選課件應(yīng)用層組播1.IP組播回顧應(yīng)用層組播概述應(yīng)用層組播分類4. 應(yīng)用層組播評(píng)價(jià)指標(biāo)5. 應(yīng)用層組播方案舉例ESMHMTPNICE應(yīng)用層組播方案比較6.總結(jié)精選課件5.1 ESMEnd System MulticastCarnegie Mellon University提出，最早提出的應(yīng)用層組播方案之一ESM的核心是Narada協(xié)議Mesh-first方法適用于中小規(guī)模的實(shí)時(shí)視頻流媒體服務(wù)(Live Streaming Video)精選課件Narada：Mesh構(gòu)建不存在集合點(diǎn)(rendezvous point)節(jié)點(diǎn)可以通過聯(lián)系任何已知的活躍組成員執(zhí)行