SplitStream: high-bandwidth multicast in cooperative environments

M. CastroP. DruschelAnne-Marie KermarrecAnimesh NandiA. RowstronAtul Singh

article2003SOSP1,611 citations

Proposes a peer-to-peer multicast system that distributes forwarding load evenly across participating nodes by striping content over a forest of interior-node-disjoint trees, enabling high-bandwidth streaming and resilience to node failures.

Listen

Distributing high-bandwidth data such as video streams or large files over the Internet is challenging without specialized network infrastructure. Traditional peer-to-peer multicast systems rely on a single distribution tree, which places an unfair forwarding burden on a small fraction of interior nodes while leaving most participants idle as leaves. In cooperative environments where participants contribute resources according to their own capacity, this structural imbalance limits scalability, increases vulnerability to node failures, and causes severe performance bottlenecks.

The article designs and evaluates SplitStream, a decentralized peer-to-peer multicast system that balances forwarding loads across all participants. The system divides content into multiple stripes and distributes each stripe across a separate multicast tree, ensuring that a node acting as an internal forwarder in one tree serves only as a leaf in the others while honoring individual bandwidth constraints.

To evaluate the system, the authors conducted large-scale discrete-event network simulations on topologies ranging up to 102,639 routers and 40,000 participating nodes, testing various bandwidth configurations and dynamic peer arrival and departure traces. They also deployed a live prototype on the PlanetLab Internet testbed across 36 hosts and 72 nodes in the United States and Europe to assess real-world performance during abrupt node failures.

The findings show that SplitStream distributes transmission loads effectively while keeping system overhead remarkably low. First, during forest construction, the maximum node stress in SplitStream was 13.5 times lower than the load on a centralized server distributing the same content. Second, during active multicasts, the system utilized 98% of available network links to distribute traffic, reducing average link stress to within 28% of theoretical optimal network multicast and achieving a maximum link stress roughly three times lower than single-tree peer-to-peer systems. Third, SplitStream proved highly resilient to churn and failures: when 25% of a 10,000-node network failed simultaneously, surviving nodes recovered to receive all content stripes within three minutes, while continuous high-churn evaluations showed that 99.5% of nodes consistently received at least 75% of content stripes with control overhead staying below 1.6 messages per second per node. Finally, the PlanetLab deployment confirmed practical viability, with 90% of packets delivered in under one second.

These results demonstrate that organizations can reliably distribute high-volume content without investing in expensive centralized server infrastructure or dedicated multicast hardware. By spreading forwarding requirements across all participating nodes and pairing the stream with fault-tolerant data encodings, the system dramatically lowers bandwidth costs and minimizes service disruptions caused by sudden node departures.

Organizations adopting SplitStream should pair the system with appropriate content encodings, such as multiple description coding for video streams or erasure coding for bulk file transfers, to seamlessly absorb temporary stripe losses during tree repairs. Additionally, operators deploying the technology in open consumer networks should implement incentive or enforcement mechanisms to prevent free-riding and ensure nodes contribute sufficient forwarding capacity.

The primary limitation noted in the article is that SplitStream assumes network bottlenecks occur only at the sending or receiving endpoints rather than within intermediate backbone transit links. While empirical confidence in the system's performance and scalability is high across diverse simulated topologies and small-scale live testbeds, real-world deployments across varied consumer access networks should incorporate dynamic bandwidth monitoring to detect and circumvent intermediate link congestion.

Microsoft Rice University high bandwidth multicast tree node failure SplitStream multicast tree multicast routing

Castro et al (2003).pdf

Paper: Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, Antony Rowstron et al. (2001). This paper establishes decentralized load-balancing and routing techniques over structured peer-to-peer overlays that provide the foundational networking primitives used in cooperative multicast distribution.
Paper: Resilient overlay networks, David G. Andersen et al. (2001). This work demonstrates how application-layer overlay routing can effectively bypass wide-area Internet path failures and optimize throughput among cooperating end hosts.

Paper: PeerTrust: supporting reputation-based trust for peer-to-peer electronic communities, Li Xiong et al. (2004). This research provides a decentralized, reputation-based framework that solves the incentive, accountability, and free-riding challenges essential for sustaining cooperative peer-to-peer distribution networks.

Cover for SplitStream: high-bandwidth multicast in cooperative environments

Abstract

In tree-based multicast systems, a relatively small number of interior nodes carry the load of forwarding multicast messages. This works well when the interior nodes are highly-available, dedicated infrastructure routers but it poses a problem for application-level multicast in peer-to-peer systems. SplitStream addresses this problem by striping the content across a forest of interior-node-disjoint multicast trees that distributes the forwarding load among all participating peers. For example, it is possible to construct efficient SplitStream forests in which each peer contributes only as much forwarding bandwidth as it receives. Furthermore, with appropriate content encodings, SplitStream is highly robust to failures because a node failure causes the loss of a single stripe on average. We present the design and implementation of SplitStream and show experimental results obtained on an Internet testbed and via large-scale network simulation. The results show that SplitStream distributes the forwarding load among all peers and can accommodate peers with different bandwidth capacities while imposing low overhead for forest construction and maintenance.

Topics

high bandwidth multicast tree node failure peer-to-peer available bandwidth

Keywords

SplitStream multicast tree multicast routing peer overlay networks data dissemination video streaming application-level group communication system cooperative environments

1. INTRODUCTION
2. THE SPLITSTREAM APPROACH
2.1 Tree-based multicast
2.2 SplitStream
2.3 Applications
2.4 Properties
3. BACKGROUND
3.1 Pastry
3.2 Scribe
4.1 Building interior-node-disjoint trees
4.2 Limiting node degree
4.3 Locating parents
4.4 Spare capacity group
4.5 Correctness and complexity
5. EXPERIMENTAL EVALUATION
5.1 Experimental setup
5.2 Forest construction overhead
5.3 Forest multicast performance
5.4 Resilience to node failures
5.5 PlanetLab results
6. RELATED WORK
7. CONCLUSIONS
Acknowledgements
8. REFERENCES

Knowls

Knowl 1 — SplitStream Forest Construction via Prefix-Disjoint Multicast Trees
model/method
SplitStream distributes high-bandwidth multicast data by dividing content into $k$ distinct stripes and transmitting each stripe over an independent application-level multicast tree built on top of the Pastry structured peer-to-peer overlay network using Scribe.

To balance forwarding workloads across participating nodes and prevent interior-node bottlenecks, the trees are constructed to be interior-node-disjoint: each peer participates as an interior (forwarding) node in at most one multicast tree and acts as a leaf node in all other $k-1$ trees.

Pastry routes messages by prefix-matching node identifiers (nodeIds) and group identifiers (groupIds) in base $2^b$ , routing towards nodes whose nodeIds share progressively longer prefix matches with the destination key. SplitStream exploits this property by configuring Pastry with parameter $b$ such that $2^b = k$ , and assigning each stripe a group identifier (stripeId) starting with a distinct first digit in base $2^b \in \{0, \dots, k-1\}$ .

Because a Scribe multicast tree for a given stripeId is formed by the union of Pastry routes from all members toward that stripeId, every intermediate (interior) node on a route shares at least the first digit with the stripeId. Consequently, a node whose nodeId starts with digit $d$ can only serve as an interior forwarding node in the multicast tree for stripe $d$ , and is guaranteed to be a leaf node in all remaining $k-1$ stripe trees. When nodeIds are distributed uniformly at random across the identifier space, the forwarding responsibility is evenly balanced across all participants.
Knowl 2 — Feasibility Conditions for Multicast Forest Construction Under Bandwidth Constraints
theoretical result
Let $N$ denote the set of participating nodes and $k$ denote the total number of content stripes. Each node $i \in N$ specifies a desired indegree $I_i \in \{1, \dots, k\}$ (the number of distinct stripes it wants to receive) and a forwarding capacity $C_i \ge 0$ (the maximum number of children it is willing to serve across all trees). A subset of nodes $S \subseteq N$ ( $1 \le |S| \le k$ ) serves as sources, where each source $s \in S$ originates $T_s$ distinct stripes with forwarding capacity $C_s \ge T_s$ . For non-source nodes $i \in N \setminus S$ , $T_i = 0$ .

Forest construction is feasible if there exists a connection topology such that every node $i \in N$ receives $I_i$ distinct stripes and forwards stripes to at most $C_i$ child nodes.

Necessary Condition: The total forwarding capacity across all nodes must be at least the total desired indegree across all nodes: $\sum_{i \in N} I_i \le \sum_{i \in N} C_i$

Sufficient Condition: The necessary condition is not sufficient on its own because forwarding capacity could be concentrated in nodes that only subscribe to a subset of stripes. A sufficient condition for feasibility requires that the necessary condition holds and that any node whose forwarding capacity exceeds its desired indegree originates or receives all $k$ stripes: $\forall i \in N : C_i > I_i \implies I_i + T_i = k$ Under this condition, nodes with spare forwarding capacity possess all $k$ stripes and can therefore satisfy child requests for any stripe in the system.
Knowl 3 — Failure Probability Upper Bound for SplitStream Forest Construction
theoretical result
Assume a system of $|N|$ nodes and $k$ multicast stripes satisfying the sufficient feasibility condition, where each node receives at least $I_{\min} = \min_{i \in N} I_i$ stripes ( $1 \le I_{\min} \le k$ ), and the total spare capacity in the system is defined as: $C = \sum_{i \in N} C_i - \sum_{i \in N} I_i$ where $C_i$ is the forwarding capacity and $I_i$ is the desired indegree of node $i$ .

When an orphaned node attempts to locate a parent for a desired stripe by anycasting to the spare capacity group (which maintains all nodes with unused forwarding capacity), the probability $P_f$ that an anycast fails to find a node receiving that stripe is bounded by: $P_f \le \left(1 - \frac{I_{\min}}{k}\right)^{\frac{C}{k-1}}$ Across all $|N|$ joining nodes, with each node joining at most $k$ stripes, the total number of anycasts that can potentially fail is at most $|N| \times k$ . The overall probability $P_{\text{failure}}$ that SplitStream fails to construct a feasible forest is upper-bounded by: $P_{\text{failure}} \le |N| \times k \times \left(1 - \frac{I_{\min}}{k}\right)^{\frac{C}{k-1}}$ When all nodes subscribe to all stripes ( $I_{\min} = k$ ), $P_{\text{failure}} = 0$ , guaranteeing feasible forest construction even with zero spare capacity ( $C = 0$ ). For configurations where $I_{\min} < k$ , even a modest amount of spare capacity (e.g., $C = 0.01 \times |N|$ ) yields an extremely low failure probability (e.g., $< 10^{-11}$ for $|N| = 10^6$ and $k=16$ ).
Knowl 4 — Parent Selection and Child Eviction via Push-Down
algorithm
When a SplitStream node receives a join request from a prospective child for stripe $s$ but has already reached its forwarding capacity limit $C_u$ , it enforces its outdegree constraint by temporarily adopting the prospective child and evicting an existing child according to a preference rule designed to preserve tree efficiency.
Input: Local node $u$ with forwarding capacity $C_u$ , current set of children $Children(u)$ where $|Children(u)| = C_u$ , prospective child $v$ requesting to join stripe $s$
Output: Updated $Children(u)$ , orphaned child $w$ and the stripe $s'$ for which $w$ is orphaned
$Children(u) \leftarrow Children(u) \cup \{(v, s)\}$
$Mismatched \leftarrow \{(c, s_c) \in Children(u) \mid \text{first digit of } s_c \neq \text{first digit of } u\text{'s nodeId}\}$
if $Mismatched \neq \emptyset$ then
    if $(v, s) \in Mismatched$ then
         $(w, s') \leftarrow (v, s)$
    else
         $(w, s') \leftarrow \text{select uniform random element from } Mismatched$
else
     $MinMatch \leftarrow \{(c, s_c) \in Children(u) \mid \text{prefix match length between } c\text{'s nodeId and } s_c \text{ is minimal}\}$
    if $(v, s) \in MinMatch$ then
         $(w, s') \leftarrow (v, s)$
    else
         $(w, s') \leftarrow \text{select uniform random element from } MinMatch$
$Children(u) \leftarrow Children(u) \setminus \{(w, s')\}$
Notify $w$ that it is orphaned for stripe $s'$
return $Children(u)$ , $(w, s')$
Once orphaned for stripe $s'$ , node $w$ attempts to attach to a former sibling that shares a prefix match with $s'$ . This push-down search recurses down the tree until a descendant sibling with spare capacity adopts $w$ , or no matching siblings remain. If push-down fails, $w$ locates a parent via the spare capacity group.
Knowl 5 — Spare Capacity Group Anycast and Multicast Cycle Resolution
algorithm
When a node $u$ orphaned for stripe $s$ cannot find a parent through local push-down, it discovers a parent with spare forwarding capacity via anycast to a dedicated Scribe group called the spare capacity group. All nodes in the overlay with unused forwarding outdegree (current children $< C_i$ ) are members of this group.
Input: Orphaned node $u$ seeking a parent for stripe $s$
Output: Success (parent assigned) or Notification of capacity failure
Send anycast join request for stripe $s$ to the spare capacity group
Scribe delivers anycast to an overlay node $v$ near $u$ in physical network
Start Depth-First Search (DFS) on the spare capacity group tree from $v$ :
for each visited node $w$ in DFS do
    if $w$ receives stripe $s$ and $u$ is not an ancestor of $w$ in stripe $s$ tree then
         $w$ adopts $u$ as a child for stripe $s$
        if $w$ reaches its forwarding capacity limit then
             $w$ leaves the spare capacity group
        return Success
    else if $w$ has untried children in spare capacity tree then
        Forward request to next child
    else
        Forward request back to parent in spare capacity tree
Search stripe $s$ multicast tree for any leaf node $z$ that is not a descendant of $u$
if such leaf $z$ is found then
     $u$ replaces $z$ in stripe $s$ tree
     $z$ becomes an orphan and discovers a new parent via spare capacity group anycast
    return Success
return Failure (system has insufficient forwarding capacity for stripe $s$ )
Cycle prevention is maintained because each node stores its path to the root for each stripe it receives. If adding $u$ as a parent to a spare node would create a cycle, $u$ swaps positions with a non-descendant leaf node $z$ (which is guaranteed to exist because nodes must forward the stripe sharing their nodeId prefix), allowing $z$ to safely attach elsewhere through the spare capacity group.
Knowl 6 — Communication Optimizations for SplitStream Forest Construction
model/method
SplitStream incorporates three distributed optimizations during forest construction to minimize control message overhead:
1. Conditional Path Maintenance for Cycle Detection: In standard operation, cycle avoidance requires every node to maintain and broadcast its full path to the stripe root to all its descendants. By exploiting Pastry's prefix routing invariants, cycles can only occur when a parent node does not share a longer prefix match with stripeId than its child. SplitStream restricts path state maintenance and propagation exclusively to these prefix-divergent links, reducing forest construction message overhead by up to 40%.
2. Anycast Batching: When a joining node requires parents across multiple stripes simultaneously, it batches these requests into a single composite anycast message to the spare capacity group rather than dispatching independent anycasts per stripe. This reduces the number of anycasts during forest construction by up to a factor of 8.
3. Optimized Depth-First Search (DFS) Anycast Traversal: During the DFS traversal of the spare capacity group tree, an evaluating parent attaches the list of its child nodes to the anycast message before forwarding it downward. If a child cannot satisfy the request, it removes itself from the list and forwards the anycast directly to an untried sibling, eliminating redundant round-trip traversals back up to the parent node.
Knowl 7 — Complexity of SplitStream Forest Construction and Maintenance
theoretical result
In a network of $|N|$ nodes using base- $2^b$ Pastry routing with $k = 2^b$ multicast stripes:
- Per-Node State: Each node maintains routing table state and stripe tree neighbor pointers scaling as $O(\log |N|)$ .
- Join Message Complexity: A node joining a stripe tree requires $O(\log |N|)$ messages to route to the tree root or a branch point via Pastry prefix routing. If evicted via push-down, the traversal down balanced tree branches requires $O(h_s) = O(\log |N|)$ messages, where $h_s$ is the height of tree $s$ . Anycast traversals to the spare capacity group similarly execute in expected $O(\log |N|)$ messages.
- Total Forest Construction Overhead: For balanced trees (achieved when each node forwards its prefix-matched stripe to at least two children), the expected total number of control messages across all $|N|$ nodes constructing all $k$ stripe trees is $O(|N| \log |N|)$ . In the theoretical worst-case of completely unbalanced trees, the total message overhead is $O(|N|^2)$ .
Empirical observations show that average per-node construction overhead remains largely invariant to total network size $|N|$ , because the increasing cost of $O(\log |N|)$ routing hops is counterbalanced by higher density and reduced search paths in larger spare capacity groups.

Knowl 8 — Node Stress During SplitStream Forest Construction Across Capacity Configurations

data/table

Node stress measures the number of control messages received by a node during the concurrent construction of a 16-stripe SplitStream forest with 40,000 nodes on a transit-stub network topology (GATech, 5050 routers). The configurations vary the uniform desired indegree $x$ and forwarding capacity $y$ (notation $x \times y$ ), unbounded forwarding capacity ( $16 \times \text{NB}$ ), symmetric capacity with partial subscription ( $d \times d$ ), and realistic asymmetric consumer bandwidth distributions sampled from Gnutella traces.

Configuration	$16 \times 16$	$16 \times 18$	$16 \times 32$	$16 \times \text{NB}$	$d \times d$	Gnutella
Max Stress	2971	1089	663	472	2532	1054
Mean Stress	57.2	52.6	35.3	16.9	42.1	56.7
Median Stress	49.9	47.4	30.9	12.0	36.6	54.2

The data demonstrates that providing a modest 12.5% spare forwarding capacity ( $16 \times 18$ vs. $16 \times 16$ ) reduces the maximum node stress by a factor of 2.7 (from 2971 to 1089 messages) because nodes experience significantly fewer push-down evictions and anycast queries. The nodes bearing maximum stress are those closest to the spare capacity group root in the Pastry identifier space. In the Gnutella configuration (where average spare capacity is 6.9 per node and 90% of nodes subscribe to all 16 stripes), mean stress is 56.7 messages, showing that SplitStream accommodates heterogeneous and asymmetric peer capacities with low overhead.

Knowl 9 — Multicast Link Stress Comparison of SplitStream, Scribe, IP Multicast, and Centralized Unicast

data/table

Multicast distribution performance was evaluated on a 40,000-node Pastry overlay on the GATech topology by multicasting 16 data packets (one packet per stripe in SplitStream; 16 packets to a single tree in Scribe and IP multicast; 16 unicast packets to all clients in centralized unicast). Link stress measures the number of packets transmitted across each physical network link.

Metric	Centralized Unicast	Scribe	IP Multicast	SplitStream ( $16 \times 16$ )
Max Link Stress	639,984	3,990	16	1,411
Mean Link Stress	128.9	39.6	16.0	20.5
Median Link Stress	16.0	16.0	16.0	16.0
Fraction of Used Links	0.43	0.47	0.43	0.98

SplitStream utilizes 98% of physical links in the topology because it actively utilizes both inbound and outbound access links across all nodes, whereas single-tree multicast (Scribe) only uses outbound access links for the small fraction of nodes acting as interior tree nodes. Consequently, SplitStream reduces maximum link stress by a factor of 2.8 compared to Scribe (1411 vs. 3990) and achieves a mean link stress only 28% higher than optimal IP multicast (20.5 vs. 16.0), compared to Scribe whose mean link stress is 247% higher than IP multicast (39.6 vs. 16.0).

In terms of delivery latency, SplitStream achieves a Relative Average Delay (RAD, ratio of average tree delay to IP multicast delay) between 1.5 and 2.5 across stripes, demonstrating efficient proximity routing without excessive tree depth.

Knowl 10 — SplitStream Robustness to Single Failures, Catastrophic Node Loss, and Churn
empirical result
SplitStream's resilience to node failures was evaluated through simulations on GATech topologies and live PlanetLab deployments:
- Single Node Failure Impact: Across a 40,000-node network in the $16 \times 16$ configuration, failure of a random interior node causes the loss of only 1 stripe on average and median. Even when a node's worst-case ancestor fails, the mean number of lost stripes is 2.1 (median 2), demonstrating path diversity across independent trees.
- Catastrophic Failure Recovery: When 25% of nodes in a 10,000-node network fail simultaneously, surviving nodes experience an immediate stripe loss but recover rapidly: most nodes receive at least 14 of 16 stripes within 30 seconds (one failure detection heartbeat period), all stripes within 60 seconds, and 100% of nodes receive all stripes in under 3 minutes. Total control overhead during normal operation is 1.6 messages/sec/node, briefly increasing during repair before returning to baseline.
- Dynamic Churn Resilience: Under a 60-hour real-world Gnutella churn trace (17,000 unique nodes, average session duration 2.3 hours, active population 1300–2700 nodes), 99.5% of nodes receive at least 75% of stripes (12/16) almost all the time, with average stripe reception maintained between 15 and 16. Control traffic consumes less than 0.17% of total bandwidth for a 1 Mb/s media stream.
- PlanetLab Deployment: In a 72-node live Internet deployment across 36 sites streaming 320 kbps data, 90% of packets experienced delays under 1.0 second, and tree repair completed promptly upon node terminations.

Coverage note — None was omitted; the knowls cover the architecture, theoretical feasibility conditions, failure bounds, parent assignment algorithms, optimization techniques, complexity bounds, and empirical evaluations across node stress, link stress, latency, and fault resilience.

References

1.Planetlab. http://www.planet-lab.org.
2.E. Adar and B. Huberman. Free riding on Gnutella. First Monday, 5(10), Oct. 2000. http://firstmonday.org/issues/issue5_10/adar/index.html.
3.D. Andersen, H. Balakrishnan, F. Kaashoek, and R. Morris. Resilient overlay networks. In SOSP’01, Banff, Canada, Dec. 2001.
4.J. G. Apostolopoulos. Reliable video communication over lossy packet networks using multiple state encoding and path diversity. In Visual Communications and Image Processing, Jan. 2001.
5.J. G. Apostolopoulos and S. J. Wee. Unbalanced multiple description video communication using path diversity. In IEEE International Conference on Image Processing, Oct. 2001.
6.S. Banerjee, B. Bhattacharjee, and C. Kommareddy. Scalable application layer multicast. In Proceedings of ACM SIGCOMM, Aug. 2002.
7.M. Bawa, H. Deshpande, and H. Garcia-Molina. Transience of peers and streaming media. In HotNets-I, New Jersey, USA, Oct. 2002.
8.K. Birman, M. Hayden, O. Ozkasap, Z. Xiao, M. Budiu, and Y. Minsky. Bimodal multicast. ACM Transactions on Computer Systems, 17(2):41–88, May 1999.
9.R. Blahut. Theory and Practice of Error Control Codes. Addison Wesley, MA, 1994.
10.J. Byers, J. Considine, M. Mitzenmacher, and S. Rost. Informed content delivery across adaptive overlay networks. In SIGCOMM’2002, Pittsburgh, PA, USA, Aug. 2002.
11.M. Castro, P. Druschel, Y. C. Hu, and A. Rowstron. Exploiting network proximity in peer-to-peer overlay networks. Technical Report MSR-TR-2002-82, Microsoft Research, 2002.
12.M. Castro, P. Druschel, Y. C. Hu, and A. Rowstron. Proximity neighbor selection in tree-based structured peer-to-peer overlays. Technical Report MSR-TR-2003-52, Microsoft Research, Aug. 2003.
13.M. Castro, P. Druschel, A.-M. Kermarrec, and A. Rowstron. SCRIBE: A large-scale and decentralized application-level multicast infrastructure. IEEE JSAC, 20(8), Oct. 2002.
14.M. Castro, P. Druschel, A.-M. Kermarrec, and A. Rowstron. Scalable application-level anycast for highly dynamic groups. In Networked Group Communications, Oct. 2003.
15.M. Castro, M. Jones, A.-M. Kermarrec, A. Rowstron, M. Theimer, H. Wang, and A. Wolman. An evaluation of scalable application-level multicast built using peer-to-peer overlay networks. In INFOCOM’03, 2003.
16.Y. Chu, S. Rao, and H. Zhang. A case for end system multicast. In Proc. of ACM Sigmetrics, pages 1–12, June 2000.
17.Y. K. Dalal and R. Metcalfe. Reverse path forwarding of broadcast packets. Communications of the ACM, 21(12):1040–1048, 1978.
18.S. Deering and D. Cheriton. Multicast routing in datagram internetworks and extended LANs. ACM Transactions on Computer Systems, 8(2), May 1990.
19.P. Eugster, S. Handurukande, R. Guerraoui, A.-M. Kermarrec, and P. Kouznetsov. Lightweight probabilistic broadcast. In Proceedings of The International Conference on Dependable Systems and Networks (DSN 2001), July 2001.
20.J. Gemmell, E. Schooler, and J. Gray. Fcast multicast file distribution. IEEE Network, 14(1):58–68, Jan 2000.
21.R. Govindan and H. Tangmunarunkit. Heuristics for internet map discovery. In Proc. 19th IEEE INFOCOM, pages 1371–1380, Tel Aviv, Israel, March 2000. IEEE.
22.J. Jannotti, D. Gifford, K. Johnson, M. Kaashoek, and J. O’Toole. Overcast: Reliable multicasting with an overlay network. In Proc. OSDI 2000, San Diego, CA, 2000.
23.D. Kostic, A. Rodriguez, J. Albrecht, A. Bhirud, and A. Vahdat. Using random subsets to build scalable network services. In USITS’03, Mar. 2003.
24.M. Luby. LT Codes. In FOCS 2002, Nov. 2002.
25.R. Mahajan, M. Castro, and A. Rowstron. Controlling the cost of reliability in peer-to-peer overlays. In IPTPS’03, Feb. 2003.
26.P. Maymounkov and D. Mazières. Rateless Codes and Big Downloads. In IPTPS’03, Feb. 2003.
27.A. Mohr, E. Riskin, and R. Ladner. Unequal loss protection: Graceful degredation of image quality over packet erasure channels through forward error correction. IEEE JSAC, 18(6):819–828, June 2000.
28.T. Ngan, P. Druschel, and D. S. Wallach. Enforcing fair sharing of peer-to-peer resources. In IPTPS ’03, Berkeley, CA, Feb. 2003.
29.T. Nguyen and A. Zakhor. Distributed video streaming with forward error correction. In Packet Video Workshop, Pittsburgh, USA., 2002.
30.V. Padmanabhan, H. Wang, P. Chou, and K. Sripanidkulchai. Distributing streaming media content using cooperative networking. In The 12th International Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV ’02), Miami Beach, FL, USA, May 2002.
31.S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable content-addressable network. In Proc. ACM SIGCOMM’01, San Diego, CA, Aug. 2001.
32.S. Ratnasamy, M. Handley, R. Karp, and S. Shenker. Application-level multicast using content-addressable networks. In NGC’2001, Nov. 2001.
33.A. Rowstron and P. Druschel. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In Proc. IFIP/ACM Middleware 2001, Heidelberg, Germany, Nov. 2001.
34.S. Saroiu, P. K. Gummadi, and S. D. Gribble. A measurement study of peer-to-peer file sharing systems. In Proceedings of the Multimedia Computing and Networking (MMCN), San Jose, CA, Jan. 2002.
35.A. Snoeren, K. Conley, and D. Gifford. Mesh-based content routing using XML. In SOSP’01, Banff, Canada, Dec. 2001.
36.I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for Internet applications. In Proc. ACM SIGCOMM’01, San Diego, CA, Aug. 2001.
37.H. Tangmunarunkit, R. Govindan, D. Estrin, and S. Shenker. The impact of routing policy on internet paths. In Proc. 20th IEEE INFOCOM, Alaska, USA, Apr. 2001.
38.E. Zegura, K. Calvert, and S. Bhattacharjee. How to model an internetwork. In INFOCOM96, San Francisco, CA, 1996.
39.B. Zhao, J. Kubiatowicz, and A. Joseph. Tapestry: An infrastructure for fault-resilient wide-area location and routing. Technical Report UCB//CSD-01-1141, U.C. Berkeley, April 2001.
40.S. Zhuang, B. Zhao, A. Joseph, R. Katz, and J. Kubiatowicz. Bayeux: An architecture for scalable and fault-tolerant wide-area data dissemination. In NOSSDAV’2001, June 2001.

Citation

MLA

Castro, M., et al. “SplitStream”. Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles, 2003, pp. 298–313, https://doi.org/10.1145/945445.945474.

APA

Castro, M., Druschel, P., Kermarrec, A.-M., Nandi, A., Rowstron, A., & Singh, A. (2003). SplitStream. Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles, 298–313. https://doi.org/10.1145/945445.945474

Chicago

Castro, M., P. Druschel, A.-M. Kermarrec, A. Nandi, A. Rowstron, and A. Singh. 2003. “SplitStream”. Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles, 298–313. https://doi.org/10.1145/945445.945474.

Harvard

Castro, M. et al. (2003) “SplitStream”, Proceedings of the nineteenth ACM symposium on Operating systems principles. ACM, pp. 298–313. Available at: https://doi.org/10.1145/945445.945474.

Vancouver

1. Castro M, Druschel P, Kermarrec A-M, Nandi A, Rowstron A, Singh A (2003) SplitStream. In: Proceedings of the nineteenth ACM symposium on Operating systems principles. ACM, pp 298–313

BibTeX

@inproceedings{Castro_2003, series={SOSP03}, title={SplitStream: high-bandwidth multicast in cooperative environments}, url={http://dx.doi.org/10.1145/945445.945474}, DOI={10.1145/945445.945474}, booktitle={Proceedings of the nineteenth ACM symposium on Operating systems principles}, publisher={ACM}, author={Castro, Miguel and Druschel, Peter and Kermarrec, Anne-Marie and Nandi, Animesh and Rowstron, Antony and Singh, Atul}, year={2003}, month=Oct, pages={298–313}, collection={SOSP03} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

SplitStream: high-bandwidth multicast in cooperative environments

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — SplitStream Forest Construction via Prefix-Disjoint Multicast Trees

Knowl 2 — Feasibility Conditions for Multicast Forest Construction Under Bandwidth Constraints

Knowl 3 — Failure Probability Upper Bound for SplitStream Forest Construction

Knowl 4 — Parent Selection and Child Eviction via Push-Down

Knowl 5 — Spare Capacity Group Anycast and Multicast Cycle Resolution

Knowl 6 — Communication Optimizations for SplitStream Forest Construction

Knowl 7 — Complexity of SplitStream Forest Construction and Maintenance