第5講-P2P網(wǎng)絡(luò)的增強(qiáng)機(jī)制

P2P網(wǎng)絡(luò)的增強(qiáng)機(jī)制

1在完成核心、基礎(chǔ)部件之后，P2P網(wǎng)絡(luò)還應(yīng)該是一個(gè)高效、高可用的分布式網(wǎng)絡(luò)，為提高性能所要做的工作，統(tǒng)稱為“P2P增強(qiáng)機(jī)制”2章節(jié)內(nèi)容5.1P2P系統(tǒng)的性能5.2復(fù)制與緩存5.3分片5.4負(fù)載均衡、異構(gòu)性與熱點(diǎn)問題5.5拓?fù)湟恢滦詥栴}35.1P2P系統(tǒng)的性能結(jié)點(diǎn)度：通常為路由表項(xiàng)數(shù)，一個(gè)結(jié)點(diǎn)連接到的其它結(jié)點(diǎn)數(shù)，也稱“鄰居數(shù)”。結(jié)點(diǎn)度決定了每個(gè)P2P結(jié)點(diǎn)所要維護(hù)的路由表項(xiàng)數(shù)，也就決定了結(jié)點(diǎn)自適應(yīng)工作的開銷，并且對(duì)于整個(gè)網(wǎng)絡(luò)的連通度有基礎(chǔ)性作用定位效率：定位任意一個(gè)結(jié)點(diǎn)或者數(shù)據(jù)對(duì)象所需要走過的覆蓋網(wǎng)路由跳數(shù)，或理解為任意一條消息從源結(jié)點(diǎn)出發(fā)要到達(dá)目的結(jié)點(diǎn)所走過的覆蓋網(wǎng)跳數(shù)。P2P網(wǎng)絡(luò)最重要的外在性能4定位時(shí)延：定位所需要的時(shí)間，反映了真正的物理網(wǎng)工作情況，為簡(jiǎn)化，通常用物理跳數(shù)（如IP跳數(shù)）近似Stretch(伸展性)：描述P2P覆蓋網(wǎng)與物理網(wǎng)之間一致性程度的主要參數(shù)，通常定義為Stretch=物理網(wǎng)跳數(shù)/覆蓋網(wǎng)跳數(shù)，也可以用時(shí)延來定量定義異構(gòu)性：反映P2P網(wǎng)絡(luò)中結(jié)點(diǎn)能力的差異，開發(fā)異構(gòu)性的目的是為了充分利用結(jié)點(diǎn)能力5負(fù)載均衡：數(shù)據(jù)對(duì)象在網(wǎng)絡(luò)結(jié)點(diǎn)中分布得是否均勻，以及每個(gè)結(jié)點(diǎn)為其他結(jié)點(diǎn)消息路由所承擔(dān)的負(fù)載是否均衡，由分布式散列表所決定。對(duì)均衡的理解有兩種態(tài)度：“平均”或“各盡所能”查詢負(fù)載：為查詢一個(gè)數(shù)據(jù)對(duì)象，P2P網(wǎng)絡(luò)需要付出的開銷，即需要路由多少消息，也是P2P網(wǎng)絡(luò)的重要外在性能6自適應(yīng)開銷：隨著新結(jié)點(diǎn)不斷加入、舊結(jié)點(diǎn)不斷離開或失效，為維護(hù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和保持結(jié)點(diǎn)狀態(tài)更新所需要的消息，用以衡量P2P網(wǎng)絡(luò)動(dòng)態(tài)結(jié)點(diǎn)算法的工作效率可擴(kuò)展性：當(dāng)P2P網(wǎng)絡(luò)規(guī)模增大、結(jié)點(diǎn)增多時(shí)，是否還能正常工作，其他各項(xiàng)性能發(fā)生的變化是否仍然合理、可以接受?？蓴U(kuò)展性是衡量一個(gè)分布式系統(tǒng)性能的關(guān)鍵屬性7可用性：表示P2P網(wǎng)絡(luò)中一個(gè)數(shù)據(jù)對(duì)象能被獲取到的概率（包括副本）容錯(cuò)性：含義廣泛，粗略地講表示P2P網(wǎng)絡(luò)對(duì)錯(cuò)誤行為的容忍程度匿名性：P2P網(wǎng)絡(luò)能否保護(hù)用戶的隱私和重要信息安全性：P2P網(wǎng)絡(luò)在一個(gè)不可靠的環(huán)境中能否正常工作，在受到惡意結(jié)點(diǎn)攻擊時(shí)能否正常工作，以及應(yīng)對(duì)攻擊的合理措施85.2復(fù)制與緩存P2P系統(tǒng)中復(fù)制技術(shù)的優(yōu)點(diǎn)效率：通過復(fù)制數(shù)據(jù)對(duì)象到多個(gè)結(jié)點(diǎn)，可以有效地減少獲取該對(duì)象所需要的路由跳數(shù)可用與容錯(cuò)：復(fù)制是一種冗余技術(shù)，可提高可用性與容錯(cuò)性復(fù)制技術(shù)的問題冗余代價(jià)副本一致性問題緩存：一般采用路徑緩存9從可用性角度看復(fù)制假設(shè)要求某個(gè)數(shù)據(jù)對(duì)象的可用性為a，單個(gè)副本的可用性為p，則副本數(shù)r應(yīng)該為：計(jì)算的可用性為：a=1-(1-p)^r，從而有若p=0.9，要求可用性a=0.999，則只需要復(fù)制3份10無結(jié)構(gòu)P2P網(wǎng)絡(luò)的復(fù)制方案均勻復(fù)制：所有數(shù)據(jù)對(duì)象復(fù)制份數(shù)相同比例復(fù)制：數(shù)據(jù)對(duì)象復(fù)制的份數(shù)正比于其被查詢到的概率，越熱門的數(shù)據(jù)復(fù)制份數(shù)越多方根復(fù)制：數(shù)據(jù)對(duì)象復(fù)制的份數(shù)正比于它被查詢到的概率的平方根問題：哪種方案好？評(píng)估數(shù)據(jù)對(duì)象的平均查詢距離和副本的利用率11無結(jié)構(gòu)P2P網(wǎng)絡(luò)的復(fù)制方案假設(shè)網(wǎng)絡(luò)中共有n個(gè)節(jié)點(diǎn)、m個(gè)數(shù)據(jù)對(duì)象,qi表示對(duì)第i個(gè)數(shù)據(jù)對(duì)象的查詢概率。設(shè)R代表系統(tǒng)資源總量(即所有節(jié)點(diǎn)可存放的對(duì)象數(shù)總和），設(shè)ρ代表系統(tǒng)資源在節(jié)點(diǎn)上的平均分配量，則ρ=R/n。。ri：復(fù)制份數(shù)ri相關(guān)于復(fù)制策略Ai：數(shù)據(jù)對(duì)象i的平均查詢距離Ai

=n/ri,i∈{1,m}A：整網(wǎng)的平均查詢距離

A=ΣriAi/R(所有key查詢的平均距離）Ui：數(shù)據(jù)對(duì)象i的一個(gè)副本平均被查詢到的次數(shù)（利用率）12方根復(fù)制能產(chǎn)生最小的平均查詢距離，而其利用率介于均勻復(fù)制、比例復(fù)制之間且可以接受，綜合性能最好方根復(fù)制的實(shí)現(xiàn)方法：每當(dāng)完成一次查詢后，對(duì)象i的cn/ri個(gè)副本被復(fù)制到網(wǎng)絡(luò)不同結(jié)點(diǎn)上以符號(hào)ri’表示ri的導(dǎo)數(shù)，有對(duì)該式積分可知13結(jié)構(gòu)化P2P網(wǎng)絡(luò)中的復(fù)制和緩存普遍采用“ID鄰近復(fù)制”：ID鄰近的結(jié)點(diǎn)能很快找到；這些結(jié)點(diǎn)均勻分布在網(wǎng)絡(luò)中，同時(shí)失效的可能性很小，數(shù)據(jù)可用性高數(shù)據(jù)緩存在查詢路徑上：提高定位和數(shù)據(jù)獲取速度CAN的“隱式”復(fù)制方法：多空間、多散列、區(qū)域超載OceanStore的“冗余編碼”技術(shù)，次要副本復(fù)制PAST的“副本轉(zhuǎn)移”與“文件轉(zhuǎn)移”技術(shù)145.3分片傳統(tǒng)的分片方法把一個(gè)文件分成多個(gè)等大小的片，將這些分片分散存儲(chǔ)或者分開傳輸，從而獲得并發(fā)效果新的分片技術(shù)如“冗余編碼”除了提高效率外，能以適度的存儲(chǔ)開銷獲得可用性、容錯(cuò)性的大幅提升15冗余編碼技術(shù)P：源數(shù)據(jù)可用性n：編碼后的數(shù)據(jù)塊數(shù)k:重構(gòu)源數(shù)據(jù)需要的塊數(shù)N：網(wǎng)絡(luò)中計(jì)算機(jī)（結(jié)點(diǎn)）總數(shù)M：當(dāng)前不可用的計(jì)算機(jī)（結(jié)點(diǎn)）總數(shù)16在數(shù)據(jù)可用性上冗余比復(fù)制的優(yōu)勢(shì)設(shè)網(wǎng)絡(luò)中共有100萬臺(tái)計(jì)算機(jī)，其中10%不可用（失效），即N=100萬，M=10萬。假設(shè)對(duì)源數(shù)據(jù)只以復(fù)制的方法存儲(chǔ)2個(gè)副本，那么其可用性是1-0.1*0.1=0.99若使用冗余編碼，在消耗同樣的存儲(chǔ)容量情況下，冗余編碼率應(yīng)該為r=1/2（因?yàn)閺?fù)制了2個(gè)副本）。如果將源數(shù)據(jù)編碼為64塊(n=64)，需要其中32塊來重構(gòu)（k=32)，低入P中可得17冗余編碼vs.復(fù)制圖7.3-3：橫坐標(biāo)為服務(wù)器可用性（即單個(gè)結(jié)點(diǎn)可用性），縱坐標(biāo)為“Replication/StretchRatio”，Replication為復(fù)制的存儲(chǔ)開銷（即副本數(shù)），StretchRatio為冗余編碼的存儲(chǔ)開銷(編碼率的倒數(shù)）。三條曲線分別表示可用性為0.999、0.9999、0.99999。服務(wù)可用性高有利于復(fù)制，數(shù)據(jù)可用性高有利于冗余。因此，冗余宜在服務(wù)器可用性低并且數(shù)據(jù)可用性需求高時(shí)使用(OceanStore)。18冗余編碼技術(shù)的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：服務(wù)器可用性較低、所要求的數(shù)據(jù)可用性較高時(shí)，冗余編碼的效果好，可以在同樣的開銷下將可用性提高很多個(gè)數(shù)量級(jí)缺點(diǎn)：系統(tǒng)實(shí)現(xiàn)代價(jià)高；從多個(gè)節(jié)點(diǎn)下載多個(gè)分塊所需時(shí)延可能很大（取決于最遠(yuǎn)的那個(gè)分塊）更新文件困難結(jié)論：除非對(duì)數(shù)據(jù)可用性要求極高，并且網(wǎng)絡(luò)環(huán)境非常不可靠時(shí)考慮使用冗余編碼，否則，簡(jiǎn)單的復(fù)制方法是正確的選擇。195.4負(fù)載均衡、異構(gòu)性與熱點(diǎn)問題P2P網(wǎng)絡(luò)的負(fù)載均衡本質(zhì)上來源于其分布式散列表，但沒有考慮結(jié)點(diǎn)異構(gòu)性，并未做到“各盡所能”異構(gòu)性網(wǎng)絡(luò)異構(gòu)性：在像Internet這樣的大規(guī)模網(wǎng)絡(luò)中，任意兩個(gè)結(jié)點(diǎn)間的連接，在傳輸時(shí)延和帶寬上各不相同，在覆蓋網(wǎng)中的邏輯連接差別更大節(jié)點(diǎn)異構(gòu)性：網(wǎng)絡(luò)結(jié)點(diǎn)的帶寬、存儲(chǔ)容量、處理速度的差異20設(shè)計(jì)利用異構(gòu)性結(jié)構(gòu)化之P2P網(wǎng)絡(luò)如Chord的設(shè)計(jì)中，采用每個(gè)實(shí)際的網(wǎng)絡(luò)結(jié)點(diǎn)負(fù)責(zé)多個(gè)“虛擬服務(wù)器”的方法，并在某個(gè)結(jié)點(diǎn)負(fù)載過重時(shí)轉(zhuǎn)移到負(fù)載較輕的結(jié)點(diǎn)。[Raoetal.,2003]設(shè)計(jì)了靜態(tài)環(huán)境下的負(fù)載均衡方案(virtualserver)；[Godfreyetal.,2004]在此基礎(chǔ)上設(shè)計(jì)了動(dòng)態(tài)環(huán)境下的負(fù)載均衡算法[Raoetal.03]Ananth

Rao,Karthik

Lakshminarayanan,Sonesh

Surana,RichardKarp,IonStoica.LoadBalancinginStructuredP2PSystems.InIPTPS2003,pp.68-79.[Godfreyetal.04]BrightenGodfrey,Karthik

Lakshminarayanan,RichardKarp,IonStoica.LoadBalancinginDynamicStructuredPeer-to-PeerSystems.InINFOCOM2004,pp.46-50.無結(jié)構(gòu)P2P網(wǎng)絡(luò)通過使用“超結(jié)點(diǎn)+普通結(jié)點(diǎn)”的雙層結(jié)構(gòu)開發(fā)了結(jié)點(diǎn)的異構(gòu)性21VirtualServersChordRingContiguousregionoftheIDspace.Eachnodecanberesponsibleformanyvirtualservers.UsedinChord/CFS.NodeANodeCNodeB22VirtualServersContiguousregionoftheIDspace.Eachnodecanberesponsibleformanyvirtualservers.UsedinChord/CFS.ChordRingNodeANodeCNodeB23StaticMappingofVirtualServersHeterogeneity:Numberofvirtualserversisproportionaltonode’scapacity.T=50T=15T=35ChordRingHeavyL=45L=31L=3L=41NodeCNodeBNodeA202011310153024ChordRing20113102015DynamicMappingofVirtualServersAllowdynamicre-mappingofloadinasystem.Virtualserveristhebasicunitofloadmovement.NodeANodeCNodeBT=50T=15T=35HeavyL=45L=31L=3L=413025DynamicMappingofVirtualServersAllowdynamicre-mappingofloadinasystem.Virtualserveristhebasicunitofloadmovement.ChordRing20113103015NodeANodeCNodeBT=50T=15T=35L=45L=31L=14L=3026LoadBalancingScheme-DirectoriesDirectoryNodesAllnodes,heavyorlight,periodicallyreportinformationtodirectories.SoftStateDirectoriesperiodicallycomputethetransferscheduleandreportitbacktothenodes,whichthendotheactualtransfer.HeavynodesH3H2H1DirectoriesD1D2L4LightnodesL1L2L3L4L527Unload2576410843T=6,L=7T=20,L=17T=24,L=25ABCPoolT=6,L=5AT=24,L=2228Insert5764108423ABCT=24,L=22T=20,L=17T=6,L=5T=20,L=20PoolT=24,L=2429Gia——異構(gòu)性自適應(yīng)的無結(jié)構(gòu)P2P網(wǎng)絡(luò)模型Gia：無結(jié)構(gòu)P2P網(wǎng)絡(luò)，充分利用節(jié)點(diǎn)異構(gòu)性，優(yōu)化網(wǎng)絡(luò)拓?fù)銰ia是SIGCOMM’03會(huì)議上由P2P領(lǐng)域的多位專家提出的無結(jié)構(gòu)P2P網(wǎng)絡(luò)理論模型，對(duì)Gnutella進(jìn)行改進(jìn)：拓?fù)渥赃m應(yīng)：核心設(shè)施，其作用在于不斷調(diào)整無結(jié)構(gòu)P2P網(wǎng)絡(luò)的組織方式，讓高能力結(jié)點(diǎn)擁有高的連接度，形成“集群效應(yīng)”，以開發(fā)網(wǎng)絡(luò)異構(gòu)性流控制：每個(gè)結(jié)點(diǎn)周期性地發(fā)給鄰居正比于自身能力的一定數(shù)量的令牌，只有擁有令牌的鄰居可以向自己發(fā)送消息一跳復(fù)制：每個(gè)結(jié)點(diǎn)動(dòng)態(tài)地維護(hù)其鄰居結(jié)點(diǎn)所擁有數(shù)據(jù)的索引，以提高查詢速度30Gia拓?fù)渥赃m應(yīng)算法（鄰居選擇）31熱點(diǎn)問題熱點(diǎn)問題：網(wǎng)絡(luò)領(lǐng)域中“flashcrowds”，形象地描述某個(gè)網(wǎng)絡(luò)資源在極短的時(shí)間內(nèi)，發(fā)生不可預(yù)料的、大量的、快速增長(zhǎng)的獲取請(qǐng)求，導(dǎo)致難以應(yīng)付的擁擠解決方法：結(jié)構(gòu)化P2P網(wǎng)絡(luò)中的對(duì)象索引路徑緩存、Gia中的一跳復(fù)制（對(duì)索引的熱點(diǎn)問題）；傳統(tǒng)的數(shù)據(jù)復(fù)制或緩存（對(duì)象本身的熱點(diǎn)問題）；32用P2P技術(shù)來解決C/S熱點(diǎn)問題PROOFS(P2PRandomizedOverlaystoObviateFlash-crowdSymptoms)[Stavrouetal.,2004]為消除熱點(diǎn)現(xiàn)象而構(gòu)建的無結(jié)構(gòu)P2P隨機(jī)覆蓋網(wǎng)隨機(jī)交換拓?fù)?，減少查詢熱點(diǎn)隨機(jī)、局部性查詢相結(jié)合[Stavrouetal.04]Angelos

Stavrou,DanRubenstein,Sambit

Sahu.ALightweight,RobustP2PSystemstoHandleFlashCrowds.IEEEJournalonSelectedAreasinCommunications,2004,Vol.22,No.1,pp.6-17.33ShuffleShufflingisusedtoproduceanoverlaythatis“well-mixed”intheaclient’sneighborsareessentiallydrawnatrandomfromthesetofallclientsthatparticipateintheoverlay.Thereisnoattempttooptimizetheoverlaysuchthatneighborsaretopologicallyadjacent.

PROOFS’scalabilityreliesonthefactthattheobjectaclientsearchesforisalsobeingsearchedforbymanyotherclientsinthenetwork.In34BackSlash:handleflashcrowdsPeer-to-PeerCachingSchemestoAddressFlashCrowdsIPTPS2002BackSlash:acollaborativewebmirroringsystemrunbyacollectiveofwebsitesthatwishtoprotectthemselvesfromflashcrowdsBackSlashvs.PROOFSStructuredvs.UnstructuredHandleflashcrowdsinthesamewebserver(C/SP2P)vs.Handleflashcrowdsforpopularobjects(P2P).35BackSlash：解決FTP/HTTP分發(fā)問題問題描述：FTPTraffic:17%oftotaltraffic.78%ofthemarelargerthan10MB.11%ofthemwerefailedduringtransfer.ThelargefilestransferredbyFTPgeneratemuchtraffic,

andmanyofthemtakeslongtime.P2P技術(shù)引入：大文件下載問題熱點(diǎn)緩存，減輕流量擁塞減小時(shí)延，提高傳輸速度

解決方法：構(gòu)建一個(gè)BackSlash[Stadingetal.,2002]結(jié)構(gòu)化P2P網(wǎng)絡(luò)來主動(dòng)緩存“熱點(diǎn)對(duì)象”，并通過“重定向”方法將大量的查詢請(qǐng)求分散到緩存的多個(gè)副本中36Os1ConnectivityCloudPeer1OS1

,OS2

:Smallobject

OL1,OL2

:LargeobjectBackSlashModel

HTTP/FTPServerALocalAreaNetworkPeer2Peern,Os2OL1OL2OL1OL1Peer-to-PeerStorageOs1OL1WebProxyCache

withFTPsupportingmoduleHTTP/FTPServerBOs1

Cachewithtwo-layerstorage37實(shí)現(xiàn)架構(gòu)2newcomponentstosupportFTPandlargefiles.PreservetransparencyofFileLocationFTPCacheDaemonStorethestateofFTPconnectionMaketheURLoffilestransferredbyFTPCheckconsistency.P2PStorageManagerControlitsownstorage.Managedbyobjecttableincentralcache.HTTPCacheDaemonFTPCacheDaemonObjectTable

Storage

Manager

FTP/HTTPServerFTP/

HTTPClientP2PStorageManagerFTP/

HTTP

ClientP2PStorageManager134442ControlDataControlandDataconnectionbetweencomponents3839RequestFileCheckProtocolLookupObjectTableCheckConsistencyCheckCachedLocationOpenFTPcontrolconnectionstobothpeerwhichhasfileandpeerwhichrequestsis.MakeFTPdataconnectionsbetweentwothepeers.HTTPFTPnotcachedcachedinconsistentconsistentpeerHandlearequest

likewebproxycacheTransferfileCheckFileSizeCentralcacheopensdataconnectiontoclient.centralserverUpdateObjectTableTransferfileOpensdataconnectionbetweenserverandclientTransferfileServeropensdataconnectiontocentralcache.UpdateObjectTablesmallLargeCentralcacheopensdataconnectiontoclient.TransferfileUpdateObjectTable流程圖405.5拓?fù)湟庾R(shí)和一致性問題處理一致性問題的三種傳統(tǒng)方法PRS-鄰近路由選擇(proximityrouteselection)：路由的下一跳選擇不僅僅考慮邏輯距離，還根據(jù)鄰居結(jié)點(diǎn)的時(shí)延信息進(jìn)行折中.如CFSPNS-鄰近鄰居選擇(proximityneighborselection)：路由表中維護(hù)一定數(shù)量物理上鄰近、時(shí)延很小的鄰近鄰居，如Pastry的鄰居集PIS-鄰近ID選擇(proximityidentifierselection)：也稱為“地理規(guī)劃”(geographicalayout)，讓映射到的ID能反映結(jié)點(diǎn)的地理信息或物理網(wǎng)位置信息。最先使用該方法的是“有拓?fù)湟庾R(shí)的CAN”。在一維時(shí)，可采用HilbertCoding。41CFS的下一跳選擇——鄰近路由選擇CFS在定位過程中，盡量選擇那些時(shí)延小、在底層物理網(wǎng)中靠近的結(jié)點(diǎn)作為下一跳。CFS論文中稱之為ServerSelection.用表示當(dāng)前結(jié)點(diǎn)n取ni作為下一跳的預(yù)計(jì)開銷，有其中表示n取ni作為下一跳后估計(jì)剩余的Chord跳數(shù)，di表示n到ni的時(shí)延，d’表示n所取的每跳平均時(shí)延(經(jīng)驗(yàn)值)。42時(shí)延是通過finger建立時(shí)得到，從而沒有引入extrameasurementsforthelatency若滿足三角測(cè)量a+b>c，時(shí)延估計(jì)的效果為更好詳細(xì)分析及證明見[Dabeketal.01]FrankDabek,M.Frans

Kaashoek,DavidKarger,RobertMorris,IonStoica.Wide-areacooperativestoragewithCFS.InSOSP2001,pp.202-215.以及FrankDabek的碩士論文FrankDabek

的個(gè)人主頁/research.html博士論文下載：2005

ADistributedHashTable

(pdf)

FrankDabek.PhD.Thesis(MIT)43Pastry的路由表構(gòu)造——鄰近鄰居選擇當(dāng)P2P路由局限在某個(gè)區(qū)域內(nèi)時(shí)，物理網(wǎng)和覆蓋網(wǎng)之間的差別不會(huì)太大，即通過“局部性”帶來一致性Pastry中，每次為新結(jié)點(diǎn)X構(gòu)造路由表時(shí)都進(jìn)行“鄰近鄰居選擇”，則在三角關(guān)系近似滿足的情況下，可以推出：X從自舉結(jié)點(diǎn)A中復(fù)制第0行作為自己的路由表第0行、從A中復(fù)制鄰居集作為自己的鄰居集、并用鄰居集修正過第0行后，X的路由表第0行結(jié)點(diǎn)跟X在物理上都是鄰近的隨著跳數(shù)的增加，鄰近鄰居選擇的效果會(huì)減弱44Pastry的“鄰近鄰居選擇”。X為新加入結(jié)點(diǎn)，A為其自舉結(jié)點(diǎn)，Level表示路由表行數(shù)或路由跳數(shù)，圓弧和半徑表示物理網(wǎng)距離或時(shí)延（圖片來自[Pastry01]）。

45希爾伯特編碼——鄰近ID選擇Hilbertcoding：用一條曲線無交叉地穿過一個(gè)多維空間的所有單元格，沿著曲線走向，從小到大給每個(gè)格子編碼，每個(gè)大格子里的小格子編碼都是緊鄰的。該曲線稱為“希爾伯特曲線”；將希爾伯特曲線的首尾相連構(gòu)成一個(gè)環(huán)，相當(dāng)于一個(gè)使用希爾伯特編碼作為散列函數(shù)的環(huán)結(jié)構(gòu)希爾伯特編碼與SHA相比雖然不安全，但能保證在環(huán)上鄰近的結(jié)點(diǎn)在地理上也是鄰近的46左圖為穿過2維空間的希爾伯特曲線，右圖為用希爾伯特曲線貫穿左圖形成的數(shù)值環(huán)47Hilbert編碼的性質(zhì)如果兩個(gè)結(jié)點(diǎn)編碼值(nodeID)相差1，它們?cè)诘乩砩弦欢ㄊ蔷o密相鄰的兩個(gè)結(jié)點(diǎn)的編碼值相差越小，即它們的nodeID前綴比特匹配越多，則在物理上越臨近，反之卻未必如果要從編碼值完整地反映出結(jié)點(diǎn)的鄰近關(guān)系，必須有一個(gè)算法對(duì)編碼值反運(yùn)算，從而得到結(jié)點(diǎn)的地理位置希爾伯特編碼是可調(diào)節(jié)的：編碼越長(zhǎng)則劃分越細(xì)，反映出的位置信息越多48均衡希爾伯特編碼：雖然地理位置是均衡分布的，但網(wǎng)絡(luò)結(jié)點(diǎn)在地理上的分布是不均衡的，因此人為地劃分地理區(qū)域，使網(wǎng)絡(luò)結(jié)點(diǎn)分布越密的區(qū)域其區(qū)域編碼越短49LMT——?jiǎng)討B(tài)鄰近鄰居選擇location-awaretopolotymatchingtechnique，位置意識(shí)的拓?fù)淦ヅ浼夹g(shù)：在維持原查詢范圍和減少查詢回復(fù)時(shí)間的前提下，通過主動(dòng)斷開低效連接和冗余連接并選擇物理上更接近的結(jié)點(diǎn)作為覆蓋網(wǎng)鄰居，來緩解無結(jié)構(gòu)P2P覆蓋網(wǎng)與其底層物理網(wǎng)之間的不一致性，盡量減少不必要的通信開銷Liuetal.04(a)]YunhaoLiu,XiaomeiLiu,LiXiao,LionelM.Ni,XiaodongZhang.Location-AwareTopologyMatchinginP2PSystems.InINFOCOM2004,pp.2220-2230劉云浩

1995年畢業(yè)于清華大學(xué)自動(dòng)化系，獲工學(xué)學(xué)士學(xué)位；在北京外國(guó)語大學(xué)獲文學(xué)碩士學(xué)位；并在美國(guó)密歇根州立大學(xué)計(jì)算機(jī)系獲得碩士和博士學(xué)位。50無結(jié)構(gòu)P2P網(wǎng)絡(luò)低效的三個(gè)原因無結(jié)構(gòu)P2P覆蓋網(wǎng)上的消息路由常常在物理網(wǎng)上走過太多重復(fù)或者完全不必要的路徑，既導(dǎo)致通信開銷增加，又導(dǎo)致通信時(shí)延變長(zhǎng)同樣的查詢消息常常沿多條路徑到達(dá)同樣的目的地，而其中只有一條是有意義的兩個(gè)鄰居結(jié)點(diǎn)收到同樣的查詢消息時(shí)，仍會(huì)互發(fā)消息，明顯多余51S與其鄰居N1、N2及其兩跳鄰居P的四種關(guān)系建立模型時(shí)延分析：TTL=2，通過時(shí)戳來計(jì)算52LMT使用的三種主要操作第一種操作：讓每個(gè)結(jié)點(diǎn)S周期性地洪泛廣播一種“兩跳探測(cè)消息”(TTL2-Detector)，S在消息中填入自己的IP和發(fā)送時(shí)間，第一跳的鄰居也填入信息第二、三種操作：兩跳后的P可以根據(jù)信息比較出覆蓋網(wǎng)連接的合理性，從而主動(dòng)斷開低效連接和冗余連接，建立高效連接53LMT的三種操作并未減小無結(jié)構(gòu)P2P網(wǎng)絡(luò)的洪泛查詢范圍，但通過主動(dòng)斷開低效連接和冗余連接、主動(dòng)建立高效連接，一定程度上緩解了覆蓋網(wǎng)與底層物理網(wǎng)之間的不一致性，從局部性的角度看確實(shí)減少了重復(fù)的通信開銷；但頻繁斷開和建立連接，加劇了P2P網(wǎng)絡(luò)的動(dòng)態(tài)性54思考題：1、Sigcomm02[Cohen2002]建立的無結(jié)構(gòu)P2P網(wǎng)絡(luò)復(fù)制的模型指出三種復(fù)制模型。請(qǐng)思考下為何他會(huì)提出方根模型？他的Intuition在哪里？還有第四種復(fù)制模型嗎？2、在什么情況下適用冗余編碼而不用復(fù)制技術(shù)？3、P2P是一種思想，可以用P2P來解決熱點(diǎn)問題。此外，P2P的特性還適合解決什么問題？4、Gia提出自適應(yīng)、流控及一跳復(fù)制這些技術(shù)改進(jìn)了無結(jié)構(gòu)的各方面的效率。這些技術(shù)其實(shí)都是不太復(fù)雜，關(guān)鍵在于，如何才能夠看到Gnutella無結(jié)構(gòu)拓?fù)渌嬖诘膯栴}。如果我們今天來看P2P網(wǎng)絡(luò)及其應(yīng)用，我們還能夠看到什么問題？555、閱讀CFS論文，理解其對(duì)時(shí)延問題的分析。http:///research.html博士論文下載：2005

ADistributedHashTable

(pdf)

FrankDabek.PhD.Thesis(MIT)6、鄰近ID技術(shù)存在的問題是什么？它帶來了負(fù)載不均衡，如何解決？7、理解LTM的研究問題的著眼點(diǎn)以及建立模型解決問題的研究方法。56學(xué)期論文idea之四：復(fù)制/查詢優(yōu)化AbsenceofEvidenc