P2P系統(tǒng)中的tracker主要是用來(lái)查找各個(gè)peer所持有的檔

DesignsandEvaluationofaTrackerinP2PNetworksAdeleLuJiaandDahMingChiuDepartmentofInformationEngineeringTheChineseUniversityofHongKong介紹P2P系統(tǒng)中的tracker主要是用來(lái)查找各個(gè)peer所持有的檔案。trackerfunction有各種不同的設(shè)計(jì)方式，有single-servertracker,multiple-servertrackersystem,DHT-basedserverlesssystems。在本文中我們會(huì)將這些不同的設(shè)計(jì)方式做分類，並對(duì)這些設(shè)計(jì)方式做可靠度的評(píng)估。在P2P系統(tǒng)中，tracker主要是源自於一個(gè)大眾化的檔案分享系統(tǒng)”BitTorrent(BT)”。他最主要的功能是讓peer知道有哪些peer跟他下載同樣一個(gè)檔案。為了執(zhí)行這個(gè)功能，tracker會(huì)記錄peer所做的各種要求。Tracker設(shè)計(jì)方式的分類Tracker只需要處理兩種資訊：(a)objects,and(b)peers；並將兩者做對(duì)應(yīng)。Object指的是檔案；peer就是正在下載檔案的使用者。Peer會(huì)將它正在下載的檔案告訴tracker，並要求tacker提供跟他下載同樣檔案的peer清單。Tracker設(shè)計(jì)方式的分類Tacker的設(shè)計(jì)可以分成下面三個(gè)部份：誰(shuí)提供tracker的功能?

基本上有兩種選擇：deployedserver(DS)或peer(P)。後者有可能是靠功能比較強(qiáng)大的peer，也就是supernode。Object如何指派到trackernode?

指派的方式可分成手動(dòng)配置(M)或是透過(guò)distributedhashtable(DHT).peer如何指派到trackernode?

指派的方式主要是根據(jù)trackernode是deployedserver或peer。deployedserver：trackernode有明確的告知使用者，指派方式就是根據(jù)使用者的選擇(U)；

peer：如果trackernode必須靠DHT來(lái)尋找，便屬於自動(dòng)(A)。Tracker設(shè)計(jì)方式的分類讓我們來(lái)看看下面這些不同設(shè)計(jì)方式的例子：著名的BitTorrent，tracker就是server，並將trackernode與對(duì)應(yīng)的檔案寫在meta-file裡(torrent檔)。使用者可以從meta-file選取它想要的tracker，peer接下來(lái)會(huì)去找那個(gè)tracker並要求它提供跟它一樣在下載同個(gè)檔案的peer清單。我們稱這種設(shè)計(jì)方式為(DS+M+U)。Tracker設(shè)計(jì)方式的分類另一個(gè)大眾化的檔案分享系統(tǒng)eMule是使用DHT將tracker的功能分?jǐn)傇诟鱾€(gè)peer上。DHT演算法最基本的就是提供objectname跟targetnode的對(duì)應(yīng)。targetnode擁有該object的一些資訊。我們稱這種設(shè)計(jì)方式為(P+DHT+A)。第三種是PPLive

VoD，它的tracker是由deployedserver提供，而且使用DHT來(lái)指派object，所以他的設(shè)計(jì)方式就是(DS+DHT+A)。設(shè)計(jì)時(shí)需要考慮的事情在設(shè)計(jì)tracker時(shí)，我們需要考慮下面幾件事情：執(zhí)行的難易度Easeofimplementation:

clientserver的設(shè)計(jì)方式會(huì)比DHT簡(jiǎn)單，這就是原始tracker的設(shè)計(jì)方式都是使用clientserver的原因。法律與管理責(zé)任Legalliabilityormanagementresponsibility：

執(zhí)行tracker時(shí)也許會(huì)有些法律責(zé)任的問(wèn)題，也會(huì)帶來(lái)一些管理上的瑣事，所以DHT的設(shè)計(jì)方式比較令人滿意成本Costs:

執(zhí)行tracker需要一些成本，例如server跟頻寬，如果是使用DHT的方式，這些成本將由peer承擔(dān)。設(shè)計(jì)時(shí)需要考慮的事情安全性Security：

server-based的tracker容易遭受到DoS的攻擊，在存取上也容易遭到過(guò)濾(如果某ISP想要禁止使用P2P系統(tǒng))，另一方面，server-based的tracker可以設(shè)定一些規(guī)則來(lái)控制存取的權(quán)限。上面的那些都是很重要的，而且可以用來(lái)決定tracker的設(shè)計(jì)方式。另一個(gè)重點(diǎn)就是可靠度的問(wèn)題，這將直接影響使用者的感覺(jué)。PerformanceModelsofTrackerDesign

---ReliabilityLetRserver

andRDHT

denotethereliabilityofthetwotrackerdesigns;andletRs

andRp

denotethereliabilityofdeployedserversandpeersrespectively.Then:Rserver

=1?(1?Rs)n,(1) wherenisthenumberofdeployednodesservingasthetrackerforoneobject.RDHT

=(1?(1?Rp)m)k,(2) wherekistheexpectedpathlengthoftrackernodesvisitedbytheDHT,andmisthenumberofbackuppeersforeachtrackernode.PerformanceModelsofTrackerDesign

---ThePerformanceFactorInreality,bothdeployedserversorpeershavefinitecapacity,andtheycanbeoverwhelmedunderheavyload.SothenodereliabilityR(whichcanbeRs

orRp)canbeviewedastheproductofthefollowingfactors:

R=PupPqueuedPserved

(3) Thefirstterm,Pup,takestheoriginalvalueRs

orRp

respectively.Thelastterm,Pserved,theprobabilitythatthetrackernodestaysuptilltherequestisserved,isnormallyverycloseto1,andcanbeignored.Thesecondterm,Pqueued,theprobabilitythatthetrackernodeisnotoverwhelmed,canbederivedfromasimplequeueingmodel.PerformanceModelsofTrackerDesign

---ThePerformanceFactore.g.anM/M/1/hqueuewherehisthequeuelength(thenumberofsimultaneouslookuprequestacceptedbythetrackernode).

Therequestservicerates,μs

orμp,arepropertiesofthetrackernodes.

Therequestarrivalrate,λ,isgivenbytheworkloadofthemodel,derivedfromthepeerarrivalrateandtheaveragenumberofobjectseachpeeraccesseswhileinthesystem. Basedontheseparameters,wecanderivethereliabilityofaserver-basedtrackerasfollows:Whereassumingtherequestsareevenlydistributedtothenservernodes.PerformanceModelsofTrackerDesign

---ThePerformanceFactorThenodereliabilityforapeernode,Rp,canbewrittendowninasimilarfashion.Thereisasignificantdifference:sincetherearemorepeersinthesystemservingastrackernodes,therequestarrivalratetoeachpeer,ρp,wouldbemuchlowerthantherequestratetoatrackernodeinaserver-basedsystem.TheexactformuladependsontheparticularDHTalgorithm,andthecomputationofaveragepeerpopulationinthesystem,andisnotincludehereduetospacelimits.Thebottomlineisthatsinceρp<<1thereislittlereliabilityeffectduetoblocking,andRp≈Pp.Finally,Rs

andRp

canbepluggedintothereliabilityformulatoderivethelookupsuccessrateofbothserverbasedorDHT-basedtrackers.原作者投影片說(shuō)明模型的觀察根據(jù)簡(jiǎn)單的模型我們可以觀察到一些事情：server-basedtracker的設(shè)計(jì)方式遇到高負(fù)載時(shí)會(huì)惡化的非常快速。而DHT-basedtracker的設(shè)計(jì)方式會(huì)根據(jù)負(fù)載的高低自動(dòng)增減server的數(shù)目，如圖2。模型的觀察把server-based與DHT-basedtracker的平均錯(cuò)誤時(shí)間拉長(zhǎng)，將如預(yù)期的可以改善tracker的可靠度。但是有趣的是，針對(duì)這組參數(shù)，DHT比server-based還敏感，如圖3。原因是我們的模型中，當(dāng)server發(fā)生錯(cuò)誤時(shí)，需要時(shí)間修復(fù)才能再度啟動(dòng)，所以DHT會(huì)比server-based好。模型的觀察針對(duì)server-based與DHT-basedtracker，replication的增加也如預(yù)期中的有助於改善可靠度，在這個(gè)案例中，兩種設(shè)計(jì)方式都具有同樣的敏感度，如圖4。結(jié)論在這篇文章中，我們提供p2p系統(tǒng)tracker設(shè)計(jì)的初步概念與評(píng)估，更進(jìn)一部的modeling與分析正在