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