Une étude expérimentale du protocole BitTorrent... et de ses stratégies

Fabien De Montgolfiermehdi Nafa

Description

Strategies BitTorrentUne etude experimentale du protocole BitTorrent...et de ses strategiesFabien de Montgol erMehdi NafaLIAFA, Universite Paris 7, FranceP2P @ St-MaloStrategies BitTorrentAspects strategiques de BitTorrentEmetteur vs recepteurAspects strategiques de BitTorrentDu cotˆ e du recepteurChoix du bloc a recevoirI idee : les blocs rares se monnaient plus facilementI limite : connaissance localeDu cotˆ e de l’emetteurChoix du debit sortantI idee : je donne a ceux qui me donnentI limite : ma bande passante !Strategies BitTorrentAspects strategiques de BitTorrentStrategies de downloadStrategies de choix des blocsDemande du bloc le plus rareI Il permettra la meilleure plus-value !ValidationI Choix de Bram Cohen (et de tous les clients ulterieurs)I Etude experimentale par Fabien Mathieu (meilleur que’Random’ ou ’Discrimination Positive’)Pourquoi ca marche?Les blocs ne sont pas une marchandise !I La gestion de la penurie est donc ine caceEn pratique tous les blocs ont mˆeme frequence (sauf si deploiement)Strategies BitTorrentStrategies d’uploadStrategie BitTorrent originelleStrategie d’upload classiqueA qui vais-je o rir ma precieuse bande passante? Et pourquoi?Je donne a ceux qui m’ont le plus donne!...... tout en donnant un peu gratuitement, aussiProblemesI Et si je n’ai rien a o rir?I Et si je n’attend rien des autres (seed)?I Comment eviter les pro teurs (leeches)?I Quels ...

Informations

• Publié par: Omka
• Nombre de lectures: 87
• Langue: Français

Extrait

Strat´egiesBitTorrent

Une´etudeexp´erimentaleduprotocoleBitTorrent... etdesesstrat´egies

Fabien de Montgolfier Mehdi Nafa

LIAFA,Universit´eParis7,France

P2P @ St-Malo

Strate´giesBitTorrent Aspectsstrate´giquesdeBitTorrent ´ Emetteurvsr´ecepteur

Aspectsstrate´giquesdeBitTorrent

Ducoˆte´dure´cepteur Choix dublociorecev`ar I ide´e: les blocs rares se monnaient plus facilement I limite: connaissance locale

Ducˆote´del’e´metteur Choix duitebd´sortant I ide´edonnuenitmeeuxqe`acodnn:ej limite: ma bande passante ! I

Strate´giesBitTorrent Aspectsstrat´egiquesdeBitTorrent Strate´giesdedownload

Strat´egiesdechoixdesblocs

Demande du bloc le plusrare I Il permettra la meilleure plus-value !

Validation I ChoixdeBramCohen(etdetouslesclientsulte´rieurs) I ´ Etudeexpe´rimentaleparFabienMathieu(meilleurque ’Random’ ou ’Discrimination Positive’)

Pourquoi¸camarche? Les blocs ne sont pas une marchandise ! Lagestiondelap´enurieestdoncinefficace I Enpratiquetouslesblocsontmeˆmefre´quence s(uasfdie´lpoiement)

Strate´giesBitTorrent Strate´giesd’upload Strate´gieBitTorrentoriginelle

Strat´egied’uploadclassique

` Aquivais-jeoffrirmapr´ecieusebande passante?? Et pourquoi Jedonnea`ceuxquim’ontleplusdonne´!... ... tout en donnant un peu gratuitement, aussi

Proble`mes Etsijen’airien`aoffrir? I I Et si je n’attend rien des autres (seed) ? I Commente´viterlesprofiteurs(leeches)? I Quelsparame`tresutiliserpourcalculertoutc¸a?

Strate´giesBitTorrent Strate´giesd’upload Strate´giesnouvelles

Conside´rationsstrate´giques

Pour´ecrireunestrate´gieilfautr´efl´echir`a: 1.Algorithme de tri (pour choisir les meilleurs clients) 2.Nombre de clients 3.alabnoedsaasdnpeR´titieparstrenteentenliscle 4.´ruDniamedeeohxiitneedcs 5.nsid´er´eriodeco´Puqir)eh(eeotsi 6.t´sieenG´ro´e 7.p`aqucourbeaonneapds(nentaoimitiL)uepennodemiu

Strat´egiesBitTorrent Strat´egiesd’upload Strat´egiesnouvelles

Strate´giespossibles

M´echante Random Exclusive Exclusive (1) Proportionelle Proportionelle (1) Tit for tat Tit for tat (1) BitTorrent Roublarde Trisurefficacite´

sch´ema 0,0,.. 1,1,.. M,0,0.. M,0,0.. prop to 4 prop to 4 M,M,.. M,M,.. M M M M , , , 4 4 4 4 M,M,.. M,M,..

tri — rand dl dl dl dl dl dl dl dl dl/up

histo 1 1 20 1 20 1 20 1 20 20 20

dur´ee 1 1 1 1 1 1 1 1 10 1 1

g´ener 0% 0% 0% 0% 25% 25% 0% 0% 25% 0% 0%

limit — ∞ ∞ ∞ ∞ ∞ 0 0 ∞ -1 -1

Strat´egiesBitTorrent Exp´eriencesentournoistatique Protocole

Protocoleexpe´rimental eu(llstreorLutvreeuirApmo)!´tareige

Deuxmod`eles: I Blocsindiffe´renci´es I Blocsdistincts(etstrate´giederecherchedublocrare) Deuxtypesd’expe´riences: I Tournoi S´electiong´ene´tique I Plusdiversautresparam`etres: I pairsa`capacit´esd’uploadidentiquesounon I re´surrectionouarriv´eesre´alistes(poissonniennes) connaissancelimit´eeounondesautrespairs,... I

Strate´giesBitTorrent Expe´riencesentournoistatique R´esultats

Re´sultats:tempsmoyendete´le´chargement

Tournoi:100straacapic´t´tgeei,saolpu’deselage´drrsu´e,rontiec 5Me´chantes5Random5TitforTat 5 Exclusive 10 Proportionelle 10 Proportionelle (1) 40BitTorrent10Roublardes10Triefficacit´e Re´sultats 1`ereRoublarde388.36`emeProport.(1)425.6 2e`meproportionelle379.47`emeBitTorrent492.0 3e`meTitforTat391.88`emeRandom582.4 4`emeExclusive392.09`emeMe´chante1868.6 10e`meTrisurefficacit´e418.83 Moyenne(ide´ale):7000/16=437.5

Strat´egiesBitTorrent Se´lectionge´ne´tique Protocole

S´electiong´ene´tique

I g´enome:.)seuqire´munustos(reetm`raPa Taille : 3×(916+16)×20×20×101×32 = 361 466 880 I population initiale´mmon(etaruo,see)omndmpor:n’i crit`eredes´election: les 95 (100) meilleurs survivent I mutations: 3% gaussien + 1% random I reproduction: Les 5 meilleurs font un fils chacun avec un I conjoint random

Strat´egiesBitTorrent S´electiong´ene´tique Re´sultats

Re´sultats(d´ebitshomog`enes)

Convergeversdeuxsortesd’e´tatsstables.Eng´en´eralc¸adonne: sche´mahistoriquedur´eechoixlimiteg´ene´rosite´ 3,3,3,3,2,2 3 17 +5 4% 3,2,2,2,2,2 10 16 +7 4% 3,3,3,3,2,2 14 13 +10 7% 3,3,3,3,2,2 11 11 +4 5% 4,4,4,4 6 13 -2 2% 4,4,3,2,2,1 8 15 +15 4% 3,3,3,3,2,2 17 14 +11 6% 3,3,3,3,2,2 18 11 +1 1% 5,4,4,2,1 17 13 +8 0% 3,3,3,3,2,2 16 13 +9 6% 4,4,4,4 20 10 +16 (= +∞) 25%

Strat´egiesBitTorrent Se´lectiong´ene´tique R´esultats

Re´sultats(d´ebitsh´ete´rog`enes)

50 pairshtibe´dtua(upload=16) et 50e´ibabdst(upload=4). sche´mahistoriquedur´eechoixlimitege´ne´rosite´ 5,... 10 14 +4 0% 1,1,1,1,... 10 9 +3 1% 1,1,1,1,... 9 5 +6 4% 2,2,... 12 11 +4 0% 2,2,... 12 11 +4 0% 5,3,2,2,2,1,1 17 9 +3 36% 5,3,2,2,2,1,1 9 13 +4 1% 4,4,2,2,1,1 15 11 +3 0% 3,3,2,1,1,1,1,1,1 9 4 +3 0% 3,3,2,1,1,1,1,1,1 9 4 +1 0% 4,4,4,4 20 10 +16 (= +∞) 25%