DOC PREVIEW
U of I CS 525 - SplitStream

This preview shows page 1-2-3-22-23-24-44-45-46 out of 46 pages.

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

Unformatted text preview:

SplitStream: High-Bandwidth Multicast in Cooperative EnvironmentsMiguel Castro, Peter Druschel, Anne-Marie Kermarrec, Animesh Nandi, Antony Rowstron, Atul SinghPresented by Ramses MoralesStreaming from servers• Bandwidth at video service and number of servers have to grow with demand– Flash crowds have to be taken into account……clientsVideo serviceserversP2P Streaming• Use the participating node’s bandwidth– More nodes watching stream = more shared bandwidth• App-level multicast– How?Live stream source(could be a member of the p2p network)P2P networkPeers watching streamStreaming in a single treeSourceFramescoder3 2 1packets321321(using RTP/UDP)…………Single tree issues• Leaves do not use their outgoing bandwidth• Packets are lost while recovering after a parent leaves/fails• Finding unsaturated peer could take a whileMultiple Trees• Challenge: a peer must be internal node in only one tree, leaf in the rest122 3 1 331 2SourceAre nodes 1, 2, 3 receiving the same data multiple times?Multiple Description Coding (MDC)• Each description can be independently decoded (only one needed to reproduce audio/video)– More descriptions received result in higher qualitycoderFrames302010Packets for description 0Packets for description n…3n2n1nStreaming in multiple-trees using MDC• Assume 2 description– Need only two sub-trees below source412 3312302010312111(using RTP/UDP)Multiple Tree Streaming in Pastry DHT• Pastry routes messages using id prefix matchingMultiple Tree Streaming in Pastry DHT• Assign an id to each coded description– If most significant digit is different, then trees will be interior-node-disjoint, example,• Id tree 1: d46a1c• Id tree 2: a1321d• 65a1fc: route(m, d46a1c) -> d13da3 -> d4213f -> d462ba• 65a1fc: route(m, a1321d) -> a0b14f -> a1b987 -> a1321a • Stream flows through reverse pathMultiple Tree Streaming in Pastry DHT • Peer is internal node in only one tree, due to interior-node-disjoint trees and Pastry’s routingd462bad4213fd13da365a1fca1321aa1b987a0b14f65a1fcStripe 0 (Description 0)d462bad4213fd13da3a1321aa1b987Stripe 1 (Description 1)a0b14fIs the forest feasible?• Condition 1:– indegreei<= capacityi• Condition 1 is necessary but not sufficient:• Condition 2:– Condition 1 holds and– For all i: capacityi> indegreeithen Ti + indegreei= k (number of stripes)Is the forest feasible?• Probability of failure:– N = number of nodes– K = number of stripes– Imin= minimum number of stripes that a node receives– C = spare capacity• Success rate is high• Iminis expected to be close to k -> higher successLocating a parentNode 001* requests description 0800 through node 080*. Node 080* has reached capacity limitNode 080* takes 001* as child, and drops 9* because 9* is subscribed to description 1800 -- prefix does not match085* requests description 0800 through node 080*Node 080* takes 085* as child after dropping 001*. Node 001* had shorter prefix match to 0800Spare Capacity Group• Used when a node cannot subscribe to a stripe• Nodes with spare capacity are members• (node 0 eventually subscribes to stripe 6 under node 3)Experimental setup• Simulation– Models propagation delay• Topologies– GATech: 5050 routers, 10 transit domains, 10 stub domains per router, 10 topologies– Mercator: 102,639 routers, measured from the Internet, 2,662 ASes– CorpNet: 298 routers from Microsoft’s network• Stripes: 2^b = 16• Stream: 320kbpsNode stress• N=40,000• Spare capacity group has impact on stressNode Stress 2• Stress largely independent of network sizeLink Stress• Max link stress is at least 6.8 times lower than the max link stress in a centralized systemLink Stress• Splitstream uses 98% of the linksDelay penalty• Penalty increases as capacity decreases– (RAD = avg delay stripe tree : avg delay IP multicast)Massive Failure• 25% out of 10,000 fail• Fast recoveryChurn (Gnutella)• 99.5% of the nodes receive at least 75% of the stripesPlanetLab deployment• 36 hosts * 2 SplitStream nodes• Four hosts die between 32s and 50sCorona: A High Performance Publish-Subscribe System for the World Wide WebVenugopalan Ramasubramanian, Ryan Peterson, EminGun SirerNSDI 2006Presented by Ramses MoralesMotivation• Web users like to keep track of multiple webistes– Twitter, blogs, Slashdot, Digg, etc.• Content is frequently updatedMotivation• Users can subscribe to a website’s feed– Constant pollingSome BlogUsing RSSRssreaderRssreaderRssreaderRssreaderRssreader“new content?”Goal• Perform asynchronous update notifications• Efficiently disseminate the updates to subscribers• Balance bandwidth vs update latencyBasic idea: cooperative pollingWeb serverWeb serverRssreaderpollpollRssreadernotifysubscribeCorona nodesResource allocation for cooperative polling• How many nodes do polling?• Which nodes do polling?• Polling rate?• Depends on– Popularity– Size– Update rateCooperative polling using PastryCoronaLevel 2Level 1Home nodeAll the nodes with at least 2 matching prefix digits in their identifiersAll the nodes with at least 1 matching prefix digits in their identifiersServers (or feeds) are assigned a Pastry ID and a LevelAnalytical Modeling• Analytically model cost-performance tradeoffs– Number of polling nodes = N/bℓ– Update Detection Time= (τ /2) (bℓ/N)– Bandwidth Cost = τ (N /bℓ) s• Optimize for application specific performance goals– min. avg. update detection, while bounding the load on serversmin. qibℓi/ N s.t. siN/ bℓi≤ qi– min. load on servers, while achieving target update detectionmin. siN/ bℓis.t. qibℓi/ N ≤ T qiτ: polling interval, s: size of content, p: number of subscribers, ℓ: polling level, b: base of overlay, qi:clients for channel iDecentralized optimization• The optimizations are NP-hard• Honeycomb optimization toolkit– Approximate answer– O(M log M log N) time• Global optimum require global information– Local knowledge leads to sub-obtimal solutions• Solution– Approximate tradeoffs (functions) for non-local channels– Aggregate coarse-grained information between neighborsDecentralized Optimization 2• Approximate Tradeoffs– Cluster channels with similar values of P(ℓ) / C(ℓ)– Constant number of clusters per levelDecentralized Optimization 3• Aggregating Clusters– Exchange clusters with one-hop neighbors– Hierarchical aggregation through structured


View Full Document

U of I CS 525 - SplitStream

Documents in this Course
Epidemics

Epidemics

12 pages

LECTURE

LECTURE

7 pages

LECTURE

LECTURE

39 pages

LECTURE

LECTURE

41 pages

P2P Apps

P2P Apps

49 pages

Lecture

Lecture

48 pages

Epidemics

Epidemics

69 pages

GRIFFIN

GRIFFIN

25 pages

Load more
Download SplitStream
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 SplitStream 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 SplitStream 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?