DOC PREVIEW
CMU CS 15441 - BitTorrent Optimization Techniques

This preview shows page 1-2-23-24 out of 24 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

BitTorrent Optimization Techniques (from various online sources)Announcement • No recitation next week! • Final review session – Next Sunday (5/2) 5-7pm, GHC 4215 – Let us know what you want at http://www.doodle.com/6qvsnubhmam2zkxp – More specifics will be announced on the course webpage.Announcement (2) • TA Evaluations! – Your comments / feedbacks are welcomed • Any reasonable criticism • Anything you liked or didn’t like • Anything you would like to do / see – Helps us improve the recitations and our teaching style!Evaluation links • 441 A Kaushik Lakshminarayanan http://www.surveymonkey.com/s/3WJKHTM • 441 B Rui Meireles http://www.surveymonkey.com/s/3WQSLXV • 441 C Daegun Won http://www.surveymonkey.com/s/3WSD2VWBefore we start • Everything we discuss here is about BitTorrent • Not everything might be useful for the project – We’d like to make it your work to figure it out – It wouldn’t be hard Two Important Aspects • Peer selection – How to choose other peers to exchange data with • Chunk selection – How to choose / prioritize chunks to downloadPeer selection • Employs a ‘Tit-for-Tat’ strategy 1. Unless provoked, the agent will always cooperate 2. If provoked, the agent will retaliate 3. The agent is quick to forgive 4. The agent must have a good chance of competing against the opponent more than once. • Called choking algorithmGood choking algorithm • Caps the number of simultaneous uploads • Avoids choking/ unchoking too quickly • Reciprocate to peers who – let the peer download – try to use unused peers once in a while (get out of local maxima)More specificially... • Peer A chokes Peer B if it decides not to upload to B – Choking = temporary refusal to upload • Each peer (A) unchokes at most 4 peers that have chunks that A doesn’t have – 3 peers with fastest upload rate (to A) – 1 randomly chosen peers • Called ‘Optimistic Unchoking’Optimistic Unchoking • Finds potentially faster peers • Allow new peers to receive their first piece • Helps out ‘snubbed’ users – Snubbed users = Choked by all its peersChunk Selection Strategies • Random First Piece • Rarest First • Endgame ModeChunk Overlaps • Small overlap – Every pair can exchange something – Better utilization of bandwidth • Big overlap – Only a few peers are very ‘valuable’ – Less utilization of bandwidthWhat do we want? • Ultimately, we want to maximize the total transfer rate of all simultaneous transfers • It would be nice if every pair has something to exchange – So that we can utilize most of the possible end-to-end connectionsWhat does it have to do with chunk selection? • If something is … – Too popular • So much supply but not many looking for it – Too rare • So much demand but not many having it • Then it is much less likely to utilize all end-to-end connectionsMaximizing Bandwidth Utilization • Keep all chunks as evenly popular as possible – So that we can maximize the number of simultaneous transfersPrioritizing algorithm should aim towards uniform distribution!Chunk Selection Strategies • Random First Piece • Rarest First • Endgame ModeRandom First Piece • Initially, the peer has nothing – Important to have some pieces to reciprocate for the choke algorithm. • Need something ASAP – Randomly chosen chunks are likely to be more replicated • Can download them faster – Then the peer can upload something • First four piece, then switch to Rarest FirstRarest First • Look at all chunks at all peers • Request the ‘rarest’ piece – Owned by fewest peers • Yes, aim towards UNIFORM DISTRIBUTION! • What if the original seeder leaves before no one downloads the whole file? – Oh no!Rarest First • What if the original seeder leaves before no one downloads the whole file? – This policy increases the likelihood that everything is still available!Endgame Mode • Happens near the end – Request the missing blocks to everyone. – Cancel pending requests when the chunk is downloaded • A bit wasteful, but… – Speeds up the completion – Not too much waste in practice – Prevents slow completion due to a single peer with slow transfer rateAnything else you can do? There are more things you can improve…Other things you can do • You can easily improve your congestion-avoidance algorithm – Check out other algorithms such as TCP new-Reno(highly recommended) • The network topology might be not totally random – May have a number of clusters and so on… • And of course, look up for more on the web!Sources • http://www.rasterbar.com/products/libtorrent/bittorrent.pdf • http://www.ict.kth.se/courses/ID2210/lectures/Lecture08-BitTorrent.pdf – If the above doesn’t work, try http://docs.google.com/viewer?a=v&q=cache:tW513GkEkXkJ:www.ict.kth.se/courses/ID2210/lectures/Lecture08-BitTorrent.pdf+bittorrent+lecture+pdf&hl=en&gl=us&pid=bl&srcid=ADGEESgjwWMdTDIEQMWa6wRklCax3kOIhy4GKlRk-rIhFlhViP6x5dGyDsIkSlsQDkv6lquNlMycLDED-VlsocwV1i9k1AGftgzXIOgYbp7IozD2xTcR3WtLlN7Ha9j3o67o7Y5TL_RF&sig=AHIEtbSh2BXqAKN8ck4kEj-p6yg-J_DcTA • http://www.cs.cornell.edu/Courses/cs514/2008sp/bittorrent.pdf •


View Full Document

CMU CS 15441 - BitTorrent Optimization Techniques

Documents in this Course
lecture

lecture

34 pages

lecture

lecture

38 pages

lecture

lecture

18 pages

lecture

lecture

28 pages

lecture

lecture

11 pages

Lecture

Lecture

64 pages

lecture

lecture

10 pages

lecture

lecture

19 pages

Lecture 6

Lecture 6

43 pages

Exam

Exam

14 pages

lecture

lecture

38 pages

Debugging

Debugging

23 pages

lecture

lecture

60 pages

review

review

27 pages

lecture

lecture

12 pages

The Web

The Web

28 pages

Lecture

Lecture

40 pages

lecture

lecture

42 pages

lecture

lecture

9 pages

lecture

lecture

10 pages

lecture

lecture

49 pages

lecture

lecture

26 pages

Project

Project

5 pages

lecture

lecture

40 pages

lecture

lecture

9 pages

lecture

lecture

41 pages

lecture

lecture

32 pages

lecture

lecture

36 pages

lecture

lecture

34 pages

lecture

lecture

45 pages

lecture

lecture

26 pages

lecture

lecture

6 pages

lecture

lecture

51 pages

Project

Project

16 pages

lecture

lecture

44 pages

lecture

lecture

13 pages

lecture

lecture

42 pages

lecture

lecture

36 pages

Project

Project

13 pages

Project

Project

33 pages

lecture

lecture

43 pages

lecture

lecture

49 pages

Load more
Download BitTorrent Optimization Techniques
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view BitTorrent Optimization Techniques and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view BitTorrent Optimization Techniques 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?