lian maze iptps06

Information about lian maze iptps06

Published on December 19, 2007

Author: luie

Source: authorstream.com

Content

Robust Incentives via Multi-level Tit-for-tat:  Robust Incentives via Multi-level Tit-for-tat Qiao Lian, Zheng Zhang (MSRA) Yu Peng, Mao Yang, Yafei Dai, Xiaoming Li (PKU) IPTPS, Feb. 2006 P2P file-sharing needs incentives to work:  P2P file-sharing needs incentives to work genuine incentives: must collaborate/share to benefit E.g. block exchange in BT Problems: only works within a large session Nearly 80% sessions contain 2 peers only, i.e. there is only one downloader No one else to collaborate with! A simple breakdown of the spectrum:  A simple breakdown of the spectrum Artificial incentive: Produce/record evidence of collaboration for future reference Incentives Private history Shared history subjective Non-subjective genuine incentives Artificial incentives The sum of contribution from the perspective of other peers, weighted by their reputation (e.g. EigenTrust) Absolute contribution (e.g. Maze) Brittle to collusion and other problems Talk organization:  Talk organization The Maze p2p file sharing system Existing collusion behaviors Why simple algorithms do not work EigenTrust and Tit-for-Tat Multi-trust algorithm Evaluation Summary and Related work Conclusion Maze: architecture:  Maze: architecture A sends query server responses with file / replica info A sends download requests B and C response with file data B and C upload traffic log A B C centralize maintained index / membership user cloud Our work starts from these logs Vital statistics:  Vital statistics Popular Population: 1.4 million registered accounts; 30,000+ online users More than 200 million files More than 13TB (!) transfer everyday Completely developed, operated and deployed by an academic team Logs added since the collaboration w/ MSRA in 2004 Enable detailed study at all angles Maze:Incentive Policies:  Maze:Incentive Policies New users: points == 4096 Point change: Uploads: +1.5 points per/MB Downloads: at most -1.0 point/MB Gives user more motivation to contribute Benefit of high point Climbing ladder  social status Service differentiation: Order download requests by T = Now – 3log(Point) Users with P < 512 have a download bandwidth of 200Kb/s Available in Maze5.0.3; extensively discussed in Maze forum before implemented Talk organization:  Talk organization The Maze p2p file sharing system Existing collusion behaviors Why simple algorithms do not work EigenTrust and Tit-for-Tat Multi-trust algorithm Evaluation Summary and Related work Conclusion What is collusion:  What is collusion Definition (Webster dictionary): secret agreement or cooperation especially for an illegal or deceitful purpose And in the Maze context: Multiple peers collude to defeat the incentive system What makes the study hard: Even with all the traffic logs, we will never know for sure But we can identify suspicious colluding patterns See our technical report for more details the collusion workingset:  the collusion workingset Repeat traffic detector Hint: colluders are lazy for peer pair link: duplication degree = total traffic / unique data 221,000 pairs whose duplication degree > 1 the top 100 pairs with most redundant traffic A closer look…:  A closer look… (David, Alice, Quincy) e.g. Alice uploads MSDN DVD image (~3GB) for 29 times (Fred, Gary) (Olga, Pam) (Harry, Cindy) Pair-wise collusion Ted: 3.8TB Ingrid: 78GB Sam: 47GB Mary: 73GB Star-shape collusion (spam account): colluding + whitewashing account Talk organization:  Talk organization The Maze p2p file sharing system Existing collusion behaviors Why simple algorithms do not work EigenTrust and Tit-for-Tat Multi-trust algorithm Evaluation Summary and Related work Conclusion What about EigenTrust?:  What about EigenTrust? EigenTrust: clone of PageRank Basic idea: Consider recommender’s reputation Trust matrix M: mi,j: trust of peer i to peer j (e.g download quantity) normalize each row of M: EigenTrust vector: The left principal eigenvector T The rank of peer i is Ti What about EigenTrust?:  What about EigenTrust? EigenTrust: clone of PageRank Basic idea: Consider recommender’s reputation Trust matrix M: mi,j: trust of peer i to peer j (e.g download quantity) normalize each row of M: EigenTrust vector: The left principal eigenvector T The rank of peer i is Ti 9GB 9GB 1GB 10GB 1GB 10GB B C A 30GB False negative of EigenTrust :  False negative of EigenTrust Does the 734KB upload to Ted really matter? No, Ted is an irrational user It downloads only 124MB, but uploads 3.8TB. How the leg-hugger has high score: leg-hugger Larry False positive of EigenTrust (local distributor Wayne):  False positive of EigenTrust (local distributor Wayne) Wayne is in a satellite cluster Wayne uploads 290GB. Its EigenRank equals to a peer in majority community with 10GB upload Is it fair? At least, Wayne should have high rank inside the satellite cluster. We need personalized rank for each peer, e.g. Tit-for-Tat Local distributor Wayne 5600GB Talk organization:  Talk organization The Maze p2p file sharing system Existing collusion behaviors Why simple algorithms do not work EigenTrust and Tit-for-Tat Multi-trust algorithm Evaluation Summary and Related work Conclusion Private history: Tit-for-Tat:  Idea: trust peers (friends) who has helped me before Used in eMule and BitTorrent (the 2 popular P2P filesharing system) Private history: Tit-for-Tat Private history: Tit-for-Tat:  Idea: trust peers (friends) who has helped me before Used in eMule and BitTorrent (the 2 popular P2P filesharing system) Problem: extremely small coverage Private history: Tit-for-Tat Limited coverage even with longer history Talk organization:  Talk organization The Maze p2p file sharing system Existing collusion behaviors Why simple algorithms do not work EigenTrust and Tit-for-Tat Multi-trust algorithm Evaluation Summary and Related work Conclusion Multi-trust incentive algorithm:  Multi-trust incentive algorithm get friends’ 1-hop friends build friends’ friend list, i.e., 2-hop friend list get friends’ 2-hop friends build 3-hop friend list Idea: we need more than one tier of trust! Multi-trust incentive algorithm:  Multi-trust incentive algorithm get friends’ 1-hop friends build friends’ friend list, i.e., 2-hop friend list get friends’ 2-hop friends build 3-hop friend list Idea: we need more than one tier of trust Multi-trust incentive algorithm:  Multi-trust incentive algorithm get friends’ 1-hop friends build friends’ friend list, i.e., 2-hop friend list get friends’ 2-hop friends build 3-hop friend list Idea: we need more than one tier of trust Multi-trust incentive algorithm:  Multi-trust incentive algorithm get friends’ 1-hop friends build friends’ friend list, i.e., 2-hop friend list get friends’ 2-hop friends build 3-hop friend list Idea: we need more than one tier of trust Multi-trust incentive algorithm:  Multi-trust incentive algorithm Idea: needs more than one tier of trust get friends’ 1-hop friends build friends’ friend list, i.e., 2-hop friend list get friends’ 2-hop friends build 3-hop friend list …… A C D E F B A C D E F B 1-hop friends 2-hop friends 3-hop friends other peers Multi-trust incentive algorithm:  Multi-trust incentive algorithm get friends’ 1-hop friends build friends’ friend list, i.e., 2-hop friend list get friends’ 2-hop friends build 3-hop friend list M M2 M3 Mathematically answer: use full spectrum { M, M2, … M∞ } Idea: needs more than one tier of trust Multi-trust incentive algorithm:  Multi-trust incentive algorithm Evaluation: Coverage: real trace driven simulation of one month Effectiveness: statically evaluate the next 2 weeks traffic Metric: colluder’s queue position at the data source peer multi-trust: the full spectrum incentive algorithm Tit-for-Tat M∞T: EigenTrust Coverage { M, M2, … M∞ } Personalization Talk organization:  Talk organization The Maze p2p file sharing system Existing collusion behaviors Why simple algorithms do not work EigenTrust and Tit-for-Tat Multi-trust algorithm Evaluation Summary and Related work Conclusion Multi-trust incentive algorithm Coverage experiment:  Multi-trust incentive algorithm Coverage experiment The coverage of {M, M2} is already good enough We can choose using {M, M2, M∞ } Multi-trust incentive algorithm: Effectiveness expr. methodology:  Multi-trust incentive algorithm: Effectiveness expr. methodology Setup Generating rank based on one months history Evaluate the next two weeks Metric: We don’t have a global rank … Queue Position at each source peer: Source peers: who holds interested resource to me Multi-trust incentive algorithm: dealing with colluders:  Multi-trust incentive algorithm: dealing with colluders Spam account colluder 5/7 punish Ingrid equally Peer 7 punishes more in multi-trust Peer 4 punishes less in multi-trust since it downs from Ingrid Pair-wise colluder 7/9 punish Cindy equally 2/9 punish more in multi-trust Friends get ahead! Desirable: as good as EigenTrust Multi-trust incentive algorithm: solve problems in EigenTrust:  Multi-trust incentive algorithm: solve problems in EigenTrust Leg-hugger 78% peers rank Larry lower 22% are still affect by super peers Ted. Local distributor Inside: 2/3 peers promote Wayne’s rank 1/3 is too young to know Wayne’s good Outside: another friend False-negative False-positive Talk organization:  Talk organization The Maze p2p file sharing system Existing collusion behaviors Why simple algorithms do not work EigenTrust and Tit-for-Tat Multi-trust algorithm Evaluation Summary and Related work Conclusion Summary and Related Work:  Summary and Related Work Conclusion:  Conclusion EigenTrust and Tit-for-tat each have their own pitfall Multi-trust as a hybrid achieves better balance Thank you:  Thank you Q&A

Related presentations


Other presentations created by luie

Biomass part 2
07. 01. 2008
0 views

Biomass part 2

hladik iogen
16. 11. 2007
0 views

hladik iogen

Ethanol Tank Fire
09. 11. 2007
0 views

Ethanol Tank Fire

ADSL Introduction
30. 11. 2007
0 views

ADSL Introduction

Ted Bundy and John Wayne Gacy1
06. 11. 2007
0 views

Ted Bundy and John Wayne Gacy1

Britain Alone
13. 11. 2007
0 views

Britain Alone

dm2
19. 11. 2007
0 views

dm2

I 10 relocation
17. 12. 2007
0 views

I 10 relocation

alimentazione
21. 11. 2007
0 views

alimentazione

LAMAQUINA
31. 12. 2007
0 views

LAMAQUINA

H114j
04. 01. 2008
0 views

H114j

3 LifeCycles
04. 01. 2008
0 views

3 LifeCycles

Kids
30. 12. 2007
0 views

Kids

China 4
10. 10. 2007
0 views

China 4

Corepartnerpresentat ions070128
29. 12. 2007
0 views

Corepartnerpresentat ions070128

RJanda Keynote SCEA2002
29. 12. 2007
0 views

RJanda Keynote SCEA2002

standard minimill stiffness
28. 02. 2008
0 views

standard minimill stiffness

Lecture12 spring05 POST
06. 03. 2008
0 views

Lecture12 spring05 POST

PPF Apr11
10. 03. 2008
0 views

PPF Apr11

anderson e
12. 03. 2008
0 views

anderson e

2007 Travel in the UK and Europe
14. 03. 2008
0 views

2007 Travel in the UK and Europe

204 011 06 Lonc PPT
18. 03. 2008
0 views

204 011 06 Lonc PPT

swanoverview
21. 03. 2008
0 views

swanoverview

pandemicplanning
27. 03. 2008
0 views

pandemicplanning

introess
07. 04. 2008
0 views

introess

ComissionErasmusMund usECW
30. 03. 2008
0 views

ComissionErasmusMund usECW

AustEnergySummitv2
13. 04. 2008
0 views

AustEnergySummitv2

Probate
14. 11. 2007
0 views

Probate

bhatt ethics
07. 01. 2008
0 views

bhatt ethics

7 K Chang presentation final
04. 03. 2008
0 views

7 K Chang presentation final

Goerens
04. 01. 2008
0 views

Goerens

QuickTourOfHowNow
03. 10. 2007
0 views

QuickTourOfHowNow

DeaconDrive
02. 10. 2007
0 views

DeaconDrive

ACM CCSM3 Tutorial
28. 11. 2007
0 views

ACM CCSM3 Tutorial

Eisenberg David Langmuir Probe
03. 01. 2008
0 views

Eisenberg David Langmuir Probe