�Enabling Contribution Awareness in an Overlay Broadcasting System

Yu-Wei (Eric) Sung

Michael Bishop, Sanjay Rao

School of ECE

SIGCOMM, Pisa, September 14, 2006

Video Broadcast using Overlay Multicast

2

Tokyo

LA

San Francisco

Boston

NYC

Pisa

Tokyo

NYC

LA

Boston

San Francisco

Pisa

Encoder

A/V Signal

Overlay Tree

Ethernet

DSL

E

D

E

E

D

D

D

E

State-of-Art in Overlay Multicast

• Key successes already achieved
• Architecture Validation and Protocol Design
• Narada, Yoid, Overcast, NICE, SplitStream, ALMI, CoopNet, Bullet…
• Significant progress on scaling, resiliency
• Real Deployments
• Tmesh (Michigan), CoolStreaming (HK), ESM (CMU)
• Much success to date:
• Homogeneous environments with abundant bandwidths

​

• Can we go further? Is overlay multicast feasible in mainstream Internet environments?

3

Focus of This Paper

• Heterogeneity in node upload/forwarding bandwidth:
• Upload access bandwidth varies widely
• Hosts may choose to forward differently

​

​

​

• Resource-scarce
• E.g. 80% DSL/Cable modem, 20% Ethernet, Src Rate : 300Kbps
• Insufficient resources to provide full source rate to all receivers
• Critical problem: not received enough attention

​

4

Bandwidth Resources

Key Contributions

• Comprehensive solution to enable overlay broadcasting in resource-scarce, heterogeneous environments
• Implementation on top of an operational broadcasting system
• Internet study using traces from operational deployments

5

Talk Outline

• Application Framework and System Design
• Distributed bandwidth allocation policy
• Multi-tree overlay structure
• Experimental Methodology
• Important Results
• Summary

6

How to allocate bandwidth?

• Host i “contributes/forwards” f_i :
• Bandwidth actually served to children in the broadcast
• May be less than access bandwidth
• How much bandwidth r_i should host i receive?
• Simple policy: bit-for-bit 🡪 r_i = f_i , inadequate since
• Resource-rich host can contribute more than src rate
• Resource-poor hosts are constrained by their upload bandwidth.

7

Our Approach

• Provide support for bandwidth allocation policies
• More generic than bit-for-bit
• Amenable to distributed implementation
• Differential and Equitable Distribution

​

​

r_i = α × f_i + ( 1–α ) × ( avg f )

​

​

• Motivated by recent work on linear taxation

[Sigcomm 04 PINS workshop]

8

Entitled bandwidth

0 < α < 1

Contribution

Multiple Overlay Trees [Coopnet,SplitStream]

9

Source

S/3

S/3

S/3

• With support from MDC, split into T-equally sized stripes
• T trees, each distributes a single stripe of size S/T
• Overall quality depends on the number of stripes received
• Number of trees node i is entitled to =

S Kbps

Entitled Bandwidth: Example

• S=400Kbps, T=4, S/T=100Kbps, f_E=500Kbps, f_D=100Kbps, avg f =300Kbps,α=0.5
• r_E=0.5*500+0.5*300=400Kbps 🡪 entitled to 4 trees
• r_D=0.5*100+0.5*300=200Kbps 🡪 entitled to 2 trees

10

Source

E

E

E

E

D

D

100Kbps

100Kbps

100Kbps

100Kbps

Excess Bandwidth

• Unused bandwidth may still exist after peers receive their entitled bandwidth
• When found: Excess Bandwidth
• Peer D: entitled to 2 trees, excess in other trees

11

Source

E

E

E

E

D

D

100Kbps

100Kbps

100Kbps

100Kbps

D

D

Key Design Issues

• Entitled Bandwidth Computation

​

r_i = α × f_i + ( 1–α ) × ( avg f )

​

• Distributed global state sampling
• Smoothing entitled bandwidth
• Excess Bandwidth Discovery
• Fair distribution while minimizing oscillation
• Achieved by active probes with Backoff, Prioritization

12

Evaluation Goals

• How effective are these heuristics in providing incentives?
• Bandwidth
• How stable is the resulting system?
• Time between tree reductions
• Reconnection time

13

Evaluation Methodology

• Playback 20-min segments of real traces on Planetlab:

​

​

​

​

​

​

​

• Use Slashdot to evaluate 2 systems:
• Cont-Agnostic: multi-tree broadcast system
• Cont-Aware: multi-tree + contribution-aware heuristics
• S=400Kbps, T=4, stripe size S/T=100Kbps
• 2 types of peers: Ethernet f_max ≤800Kbps, DSL f_max ≤100Kbps
• HC: 700-800Kbps, LC: 75-100Kbps

14

Mainstream Internet

Conferences

Performance: High Contributors

15

Better

Cont-Aware gives HC better performance

Performance: Low Contributors

16

Similar performance among similar contributors

Better

Better

Stability

• Time between Tree Reductions
• Cont-Aware performs slightly worse
• Reductions => slight dips in quality
• Not complete disconnection, 63.4% from 4🡪3, 34.1% from 3🡪2, only 2.5% from 2🡪1 and 1🡪0
• Reconnection time (in sec)

​

​

​

17

Performance across traces for high contributors

18

Summary

• Focus: Video broadcasting in resource-scarce, heterogeneous environments
• Comprehensive solution to address this challenge
• Leverages two key ideas: Multi-trees and Linear Taxation
• Implemented on top of an operational Broadcast System
• Internet study using traces from operational deployments
• Key step to extend overlay broadcasting in mainstream Internet environments
• Future work: exploration of resource allocation policies, cheating of nodes, detecting node capabilities.

19

​

​

​

Thank you!

Questions?

20