Scalable On-Demand Media Streaming with Packet Loss Recovery

Mahanti, Eager, Vernon, Sundaram-Stukel. SIGCOMM '01

Background

Data-centered: Data is served without considering request arrivals. Clients simply joins some multicast stream to retrieve data. Examples: various broadcasting protocols
Demand-driven: Data is served when requests arrive, but different clients can be merged. Examples: batching, patching, stream merging

An example: skyscraper broadcasting (See Figure 1)
Divide a media file into K segments with increasing sizes (exponentially increasing). For skyscraper, 1,2,2,5,5,12,12,25....
Broadcast each segment on a separate channel.
Usually, assume each client can retrieve two segments
The small first segment permits low startup delay; the large later segments keep the total number of channels small.
Property: B ~ ln ( T/d ), close to the lower bound

Bandwidth skimming (considers limited client bandwidth, See Figure 2)
The client immediately starts playing, meanwhile, it listen to ongoing streams (initiated by other clients)
Stream merging occurs when the clients goes on.
It is possible client bandwidth < twice the stream bit-rate, (n<2). So the server will divide a stream to k sub-streams (using fine-grain interleaving); each is multicasted at rate 1/k.
Property: B ~ ln ( N ), with a small constant factor (depends on the client bandwidth, e.g., if n=2, the constant is 1.?)

For any protocol providing immediate service, server bandwidth requirement is at least ln(N+1), where N is the number of requests during the time of a complete stream, N=\lambda T, T is the duration of the streaming object.
If delay is allowed, server bandwidth requirement is at least ln(N / (\lambda d + 1) + 1). Periodic broadcasting considers arbitrary large \lambda, so its lower bound is ln (T/d+1)

Delayed service(for example periodic broadcasting), using erasure code: ln(T/d+1) divided by (1-p)
Immediate service, using erasure code: ln(N+1) divided by (1-p)
Immediate service, using unicast retransmission, ln(N+1) + pN/(1-p)
Immediate service, using multicast retransmission, numerically solved
See Figure 3, comparing loss recovery strategies for immediate service
Erasure coding strategy is the best (scalability)

Optimize periodic broadcast protocols such that each segment is received entirely before its first byte is played. Why?

Notations: segment streaming rate (r), maximum number of streams a client listens to (s). It means each client has bandwidth n = r * s
Under this constraint, achieve the maximum possible segment size increase = maximum scalability, see equation(7)
If K channels are used, delay is T divided by r*sum(l_k), where l_kare the segment sizes.
If r=1, and s=2, Fibonacci series, from equation (6)
Since l_kincreases exponentially, bandwidth, here K ~ ln(T/d), close to the lower bound, equation (4). See Figure 5

+ Reduced server bandwidth when client request rate decreases

+ Can support interactive requests

- Less efficient with respect to the amount of data received by each client ?

- Less robust to tolerate bursty loss

- More client feedback to initiate streams

Dividing: RBS divides the media file into segments of fixed (and as short as possible) duration.
Stretching: Each segment is stretched using erasure codes.
Transmitting: The server needs to transmit 1/(1-p) times the number of packets received by a client. To do this, the server uses a rate 1.0 primary stream and a rate p/(1-p) secondary stream.

Each of the primary and secondary streams can be transmitted on k channels with rate divided by k.
For stream merging to be possible, clients must received more than k primary streams and k secondary streams
If the client wants to receive (k+1) primary streams and (k+1) secondary streams, its aggregated bandwidth is n=(1+1/k) * (1/(1+p)). So it's possible 1<n<2

See Figure 10 (only this figure is obtained through simulation).
When client bandwidth is limited, server bandwidth is still close to the lower bound ln(N+1)/(1-p)