DOC PREVIEW
CMU 15441 Computer Networking - Peer-to-Peer Protocols and Systems

This preview shows page 1-2-3-4-5 out of 14 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 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 14 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 14 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 14 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 14 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1Peer-to-PeerProtocols and SystemsTA: David Murray15-441 Spring 20064/19/20062P2P - Outline• What is P2P?• P2P System Types– 1) File-sharing– 2) File distribution– 3) Streaming• Uses & Challenges3Problem: Scalability• Hundreds of clients => 1 server–OK• Thousands of clients => 1 server– Maybe OK• Millions/billions of clients => 1 server– What happens?...45Solution:Distribute the cost among the end users6Three Classes of P2P Systems• 1) File-sharing– (old) Napster (centralized)– Gnutella (flooding)– KaZaA (intelligent flooding)– DHTs/Chord (structured overlay routing)• 2) File distribution–BitTorrent• 3) Streaming– End System Multicast (a.k.a. Overlay Multicast)21) P2P File-sharing Systems81) P2P File-sharing Systems• Centralized Database– (old) Napster• Query Flooding– Gnutella• Intelligent Query Flooding– KaZaA• Structured Overlay Routing– Distributed Hash Tables9File searchingInternetN1N2N3N6N5N4PublisherKey=“title”Value=MP3 data…ClientLookup(“title”)?10File searching• Needles vs. Haystacks– Searching for top 40, or an obscure punk track from 1981 that nobody’s heard of?• Search expressiveness– Whole word? Regular expressions? File names? Attributes? Whole-text search?• (e.g., p2p gnutella or p2p google?)11File-sharing: Framework• Common Primitives:– Join: how do I begin participating?– Publish: how do I advertise my file?– Search: how do I find a file?– Fetch: how do I retrieve a file?12P2P File-sharing Systems• Centralized Database– (old) Napster• Query Flooding– Gnutella• Intelligent Query Flooding– KaZaA• Structured Overlay Routing– Distributed Hash Tables313(old) Napster: History• 1999: Sean Fanning launches Napster• Peaked at 1.5 million simultaneous users• Jul 2001: Napster shuts down• [2003: Napster’s name reused for an online music service (no relation)]14(old) Napster: Overview• Centralized Database:– Join: on startup, client contacts central server– Publish: reports list of files to central server– Search: query the server => return someone that stores the requested file– Fetch: get the file directly from peer15Napster: PublishI have lots of TV show theme song files!Publishinsert(XenaThemeSong.mp3, 123.2.21.23)Insert(HerculesThemeSong.mp3, 123.2.21.23)...123.2.21.2316Napster: Search“Where is the XenaTheme song?”Replysearch(Xena)FetchQuery17Napster: Discussion•Pros:–Simple– Search scope is O(1)– Controllable (pro or con?)• Cons:– Server maintains O(N) State– Server does all processing– Single point of failure18P2P File-sharing Systems• Centralized Database– (old) Napster• Query Flooding– Gnutella• Intelligent Query Flooding– KaZaA• Structured Overlay Routing– Distributed Hash Tables419Gnutella: History• In 2000, J. Frankel and T. Pepper from Nullsoft released Gnutella• Soon many other clients: Bearshare, Morpheus, LimeWire, etc.• In 2001, many protocol enhancements including “ultrapeers”20Gnutella: Overview• Query Flooding:– Join: on startup, client contacts a few other nodes; these become its “neighbors”– Publish: (no need)– Search: ask neighbors, who ask their neighbors, and so on... when/if found, reply to sender.• TTL limits propagation– Fetch: get the file directly from peer21“I have XenaEpisode1.mpg”“I haveXenaEpisode1.mpg”Gnutella: Search“Where isXenaEpisode1.mpg?”QueryReply22Gnutella: Discussion•Pros:– Fully de-centralized– Search cost distributed– Processing @ each node permits powerful search semantics• Cons:– Search scope is O(N)– Search time is O(???)– Nodes leave often, network unstable• TTL-limited search works well for haystacks.– For scalability, does NOT search every node. May have to re-issue query later23P2P File-sharing Systems• Centralized Database– (old) Napster• Query Flooding– Gnutella• Intelligent Query Flooding– KaZaA• Structured Overlay Routing– Distributed Hash Tables24KaZaA: History• In 2001, KaZaA created by Dutch company Kazaa BV• Single network called FastTrack used by other clients as well: Morpheus, giFT, etc.• Eventually protocol changed so other clients could no longer talk to it525KaZaA: Overview• “Smart” Query Flooding:– Join: on startup, client contacts a “supernode” ... may at some point become one itself– Publish: send list of files to supernode– Search: send query to supernode, supernodesflood query amongst themselves.– Fetch: get the file directly from peer(s); can fetch simultaneously from multiple peers26KaZaA: Network Design“Super Nodes”27KaZaA: File InsertI have lots of files!Publishinsert(Xena.mp3,123.2.21.23)Insert(Hercules.mp3,123.2.21.23)123.2.21.2328KaZaA: File SearchWhere is Xena.mp3?Querysearch(Xena.mp3)-->123.2.0.18Repliessearch(Xena.mp3)-->123.2.22.50123.2.0.18123.2.22.5029KaZaA: Fetching• More than one node may have requested file...• How to tell?– Must be able to distinguish identical files– Not necessarily same filename– Same filename not necessarily same file...• Use Hash of file– KaZaA uses its own “UUHash”: fast, but not secure– Alternatives: MD5, SHA-1• How to fetch?– Get bytes [0..1000] from A, [1001...2000] from B– Alternative: Erasure Codes30KaZaA: Discussion•Pros:– Tries to take into account node heterogeneity:• Bandwidth• Host Computational Resources• Host Availability (?)– Rumored to take into account network locality•Cons:– Mechanisms easy to circumvent– Still no real guarantees on search scope or search time• Similar behavior to Gnutella, but better.631Stability and Superpeers• Why supernodes?– Query consolidation• Many connected nodes may have only a few files• Propagating a query to a sub-node would take more b/w than answering it yourself– Caching effect• Requires network stability• Supernode selection is time-based– How long you’ve been on is a good predictor of how long you’ll be around.32P2P File-sharing Systems• Centralized Database– (old) Napster• Query Flooding– Gnutella• Intelligent Query Flooding– KaZaA• Structured Overlay Routing– Distributed Hash Tables33Distributed Hash Tables• Academic answer to P2P•Goals– Guaranteed lookup success– Provable bounds on search time– Provable scalability• Makes some things harder– Fuzzy queries / full-text search / etc.• Read-write, not read-only• Hot Topic in networking since introduction


View Full Document

CMU 15441 Computer Networking - Peer-to-Peer Protocols and Systems

Documents in this Course
Lecture

Lecture

14 pages

Lecture

Lecture

19 pages

Lecture

Lecture

14 pages

Lecture

Lecture

78 pages

Lecture

Lecture

35 pages

Lecture

Lecture

4 pages

Lecture

Lecture

4 pages

Lecture

Lecture

29 pages

Lecture

Lecture

52 pages

Lecture

Lecture

40 pages

Lecture

Lecture

44 pages

Lecture

Lecture

41 pages

Lecture

Lecture

38 pages

Lecture

Lecture

40 pages

Lecture

Lecture

13 pages

Lecture

Lecture

47 pages

Lecture

Lecture

49 pages

Lecture

Lecture

7 pages

Lecture

Lecture

18 pages

Lecture

Lecture

15 pages

Lecture

Lecture

74 pages

Lecture

Lecture

35 pages

Lecture

Lecture

17 pages

lecture

lecture

13 pages

Lecture

Lecture

21 pages

Lecture

Lecture

14 pages

Lecture

Lecture

53 pages

Lecture

Lecture

52 pages

Lecture

Lecture

40 pages

Lecture

Lecture

11 pages

Lecture

Lecture

20 pages

Lecture

Lecture

39 pages

Lecture

Lecture

10 pages

Lecture

Lecture

40 pages

Lecture

Lecture

25 pages

lecture

lecture

11 pages

lecture

lecture

7 pages

Lecture

Lecture

10 pages

lecture

lecture

46 pages

lecture

lecture

7 pages

Lecture

Lecture

8 pages

lecture

lecture

55 pages

lecture

lecture

45 pages

lecture

lecture

47 pages

lecture

lecture

39 pages

lecture

lecture

33 pages

lecture

lecture

38 pages

lecture

lecture

9 pages

midterm

midterm

16 pages

Lecture

Lecture

39 pages

Lecture

Lecture

14 pages

Lecture

Lecture

46 pages

Lecture

Lecture

8 pages

Lecture

Lecture

40 pages

Lecture

Lecture

11 pages

Lecture

Lecture

41 pages

Lecture

Lecture

38 pages

Lecture

Lecture

9 pages

Lab

Lab

3 pages

Lecture

Lecture

53 pages

Lecture

Lecture

51 pages

Lecture

Lecture

38 pages

Lecture

Lecture

42 pages

Lecture

Lecture

49 pages

Lecture

Lecture

63 pages

Lecture

Lecture

7 pages

Lecture

Lecture

51 pages

Lecture

Lecture

35 pages

Lecture

Lecture

29 pages

Lecture

Lecture

65 pages

Lecture

Lecture

47 pages

Lecture

Lecture

41 pages

Lecture

Lecture

41 pages

Lecture

Lecture

32 pages

Lecture

Lecture

35 pages

Lecture

Lecture

15 pages

Lecture

Lecture

52 pages

Lecture

Lecture

16 pages

Lecture

Lecture

4 pages

lecture

lecture

27 pages

lecture04

lecture04

46 pages

Lecture

Lecture

46 pages

Lecture

Lecture

13 pages

lecture

lecture

41 pages

lecture

lecture

38 pages

Lecture

Lecture

40 pages

Lecture

Lecture

25 pages

Lecture

Lecture

38 pages

lecture

lecture

11 pages

Lecture

Lecture

42 pages

Lecture

Lecture

12 pages

Lecture

Lecture

36 pages

Lecture

Lecture

46 pages

Lecture

Lecture

35 pages

Lecture

Lecture

34 pages

Lecture

Lecture

9 pages

lecture

lecture

49 pages

class03

class03

39 pages

Lecture

Lecture

8 pages

Lecture 8

Lecture 8

42 pages

Lecture

Lecture

20 pages

lecture

lecture

29 pages

Lecture

Lecture

9 pages

lecture

lecture

46 pages

Lecture

Lecture

12 pages

Lecture

Lecture

24 pages

Lecture

Lecture

41 pages

Lecture

Lecture

37 pages

lecture

lecture

59 pages

Lecture

Lecture

47 pages

Lecture

Lecture

34 pages

Lecture

Lecture

38 pages

Lecture

Lecture

28 pages

Exam

Exam

17 pages

Lecture

Lecture

21 pages

Lecture

Lecture

15 pages

Lecture

Lecture

9 pages

Project

Project

20 pages

Lecture

Lecture

40 pages

L13b_Exam

L13b_Exam

17 pages

Lecture

Lecture

48 pages

Lecture

Lecture

10 pages

Lecture

Lecture

52 pages

21-p2p

21-p2p

16 pages

lecture

lecture

77 pages

Lecture

Lecture

18 pages

Lecture

Lecture

62 pages

Lecture

Lecture

25 pages

Lecture

Lecture

24 pages

Project

Project

20 pages

Lecture

Lecture

47 pages

Lecture

Lecture

38 pages

Lecture

Lecture

35 pages

Roundup

Roundup

45 pages

Lecture

Lecture

47 pages

Lecture

Lecture

39 pages

Lecture

Lecture

13 pages

Midterm

Midterm

22 pages

Project

Project

26 pages

Lecture

Lecture

11 pages

Project

Project

27 pages

Lecture

Lecture

10 pages

Lecture

Lecture

50 pages

Lab

Lab

9 pages

Lecture

Lecture

30 pages

Lecture

Lecture

6 pages

r05-ruby

r05-ruby

27 pages

Lecture

Lecture

8 pages

Lecture

Lecture

28 pages

Lecture

Lecture

30 pages

Project

Project

13 pages

Lecture

Lecture

11 pages

Lecture

Lecture

12 pages

Lecture

Lecture

48 pages

Lecture

Lecture

55 pages

Lecture

Lecture

36 pages

Lecture

Lecture

17 pages

Load more
Download Peer-to-Peer Protocols and Systems
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 Peer-to-Peer Protocols and Systems 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 Peer-to-Peer Protocols and Systems 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?