Detta dokument undersöker effekten av antalet fil repliker på sökprestanda i ostrukturerade peer-to-peer-nätverk. Vi observerar att för en sökning nätverk med en slumpmässig graf topologi där fil repliker är jämnt fördelade, humle avståndet till en kopia av en fil är logaritmisk i antalet repliker. Med hjälp av denna observation visar vi att översvämningsbaserad sökning optimeras när antalet repliker står i proportion till filförfrågan. Denna replika distribution är också optimal för nedladdningstid och eftersom översvämningar har logaritmiskt bättre söktid än slumpmässig promenad under sin optimala replika distribution, undersöker vi frågebehandling last med hjälp av denna distribution. Kategorier och ämnesdeskriptorer C.4 [Performance of Systems]: Designstudier Prestanda, Design. Peer-to-peer, Replication, Search Performance, slumpmässiga diagram, ostrukturerade nätverk, översvämning, optimal fileplikering. I helt distribuerade ostrukturerade peer-to-peer-nätverk upprätthålls innehållsindexet för en nod endast vid den noden och därför måste en sökning efter en fil undersöka enskilda deltagare för att hitta platsen för filen. Eftersom dessa nätverk vanligtvis är mycket stora och mycket dynamiska, varje nod lagrar bara adresser för en delmängd av kamrater och andra noder nås via dessa grannar. Med tanke på denna sökning overlay nätverk, i avsaknad av någon information om platsen för det ifrågasatta objektet, de två huvudalternativen för sökning är översvämningssökning och slumpmässig gångsökning. Som namnet antyder, i översvämningar sök, frågan skickas till alla grannar och om de inte har objektet de vidarebefordrar frågan till alla sina grannar och så vidare. I kontrast, i slumpmässig gång sökning, den frågande noden skickar frågan till en slumpmässigt vald granne och om den grannen inte har det önskade objektet, det kommer att vidarebefordra frågan till en av sina grannar (väljs slumpmässigt). Prestandamåtten för varje sökmekanism är (genomsnittlig) söktid, dvs. Hur lång tid tar det att hitta en fil, och (genomsnitt) frågebehandling last, dvs. antalet noder som måste frågas per sökning. Prestandan beror på många faktorer, bland annat sököverläggningsnätverket, sökmekanismen och antalet tillgängliga kopior för den fil som söks. I detta papper begränsar vi oss till att söka overlay nätverk som kan modelleras som Erdos-Renyi slumpmässiga grafer, även om resultaten är liknande för en mängd andra topologier [4]. Vi fokuserar på söktiden i översvämningssökning och härleda resultat på effekten av antalet kopior av en fil på söktiden för den filen förutsatt att filen repliker är jämnt fördelade över hela nätverket. Söktiden för en fil uppskattas av humleavståndet till kopian av den fil som ligger närmast noden som begär filen. Efter att ha hittat söktiden för en fil under ovannämnda antaganden, utforskar vi prestandan av kontrollerad översvämningssökning (översvämningar som slutar så snart den första replika hittas) och ger resultat på den optimala replika distributionen, det genomsnittliga sökavståndet och frågebehandlingsbelastningen för denna optimala replika distribution. Eftersom denna replika distribution också garanterar rättvisa i nedladdningsbelastning distribution och minimerar nedladdningstiden [3] jämför vi frågebehandlingsbelastningen vid denna replika distribution med den optimala frågebehandling belastningen. Slutligen jämför vi den kontrollerade översvämningssökningen och den slumpmässiga sökningen på replikadistributionerna som minimerar deras respektive söktider. Vi är intresserade av det kortaste avståndet från en "querying" nod (noden söker efter en fil) till en kopia av filen mätt i antal humle (dvs.. antalet humle som tagits genom en breddsökning från "querying"-noden). Låt τ i (n i ) vara den förväntade kortaste avståndet från en fråga nod till en kopia av fil jag när det finns n i kopior av filen i nätverket och n i ≥ 1. Vi simulerade ett antal av Erdos-Renyi slumpmässiga graf topologier med ett varierande antal noder och varierande per-node genomsnittsgrad. Resultaten visas i figurerna 1 och 2. Som vi kan se, τ i (n i ), är negativ-logaritmiskt relaterad till n i /M, den del av noder som har filen, oberoende av det totala antalet noder och öka per-node genomsnittsgrad minskar lutningen av förhållandet mellanτ i (n i ) och −ln(n i /M). Vid ytterligare undersökningar fann vi att lutningen var omvänt proportionell mot den genomsnittliga pernodegraden (se [4] ). Således får vi: Detta kan analytiskt visas för finita n i med M → ∞ [4]. För att undersöka sökprestandaoptiman använder vi peer-topeer-systemmodellen som beskrivits tidigare och lägger till följande beskrivning. Det finns N unika filer i systemet, var och en med en tillhörande begäran λ i för fil i per nod. Varje fil antas vara lika stor. Noder har begränsat lokalt lagringsutrymme för att lagra filkopior. Lagringsutrymmet vid varje nod antas vara
I REF undersöks effekten av antalet repliker på sökprestandan i ostrukturerade P2P-nätverk.
Analysis of search and replication in unstructured peer-to-peer networks
{'venue': "SIGMETRICS '05", 'journal': None, 'mag_field_of_study': ['Computer Science']}