P2P系统中的tracker主要是用来查找各个peer所持有的档

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

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

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

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

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

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

clientserver的設計方式會比DHT簡單，這就是原始tracker的設計方式都是使用clientserver的原因。法律與管理責任Legalliabilityormanagementresponsibility：

執行tracker時也許會有些法律責任的問題，也會帶來一些管理上的瑣事，所以DHT的設計方式比較令人滿意成本Costs:

執行tracker需要一些成本，例如server跟頻寬，如果是使用DHT的方式，這些成本將由peer承擔。設計時需要考慮的事情安全性Security：

server-based的tracker容易遭受到DoS的攻擊，在存取上也容易遭到過濾(如果某ISP想要禁止使用P2P系統)，另一方面，server-based的tracker可以設定一些規則來控制存取的權限。上面的那些都是很重要的，而且可以用來決定tracker的設計方式。另一個重點就是可靠度的問題，這將直接影響使用者的感覺。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.原作者投影片說明模型的觀察根據簡單的模型我們可以觀察到一些事情：server-basedtracker的設計方式遇到高負載時會惡化的非常快速。而DHT-basedtracker的設計方式會根據負載的高低自動增減server的數目，如圖2。模型的觀察把server-based與DHT-basedtracker的平均錯誤時間拉長，將如預期的可以改善tracker的可靠度。但是有趣的是，針對這組參數，DHT比server-based還敏感，如圖3。原因是我們的模型中，當server發生錯誤時，需要時間修復才能再度啟動，所以DHT會比server-based好。模型的觀察針對server-based與DHT-basedtracker，replication的增加也如預期中的有助於改善可靠度，在這個案例中，兩種設計方式都具有同樣的敏感度，如圖4。結論在這篇文章中，我們提供p2p系統tracker設計的初步概念與評估，更進一部的modeling與分析正在