Computer Science Thesis Oral

— 4:00pm

In Person - Reddy Conference Room, Gates Hillman 4405

MICHAEL HARRISON RUDOW , Ph.D. Candidate, Computer Science Department, Carnegie Mellon University

Efficient loss recovery for videoconferencing via streaming codes and machine learning

Packet loss degrades the quality of experience (QoE) of live communication. However, conventional methods for loss recovery are inefficient at protecting against the bursty losses that arise in practice. Instead, a new class of theoretical erasure codes, called “streaming codes,” efficiently communicates a sequence of frames over a bursty packet loss channel. Existing streaming codes apply when all frames are of the same fixed size, but many applications like videoconferencing involve sending frames of varying sizes. This thesis presents a generalized model for streaming codes that incorporates frames of variable sizes, studies the fundamental limits on the optimal rate for the new model, designs new high-rate streaming codes using machine learning and coding theory, and integrates streaming codes into a videoconferencing application to assess their positive impact on the QoE.

We start by examining the fundamental limits on the “offline” communication rate, wherein the sizes of all future frames are known. We show that the variability in the sizes of frames (a) induces a new trade-off between the rate and the decoding delay under lossless transmission and (b) impacts the optimal rate of transmission. We then design rate-optimal streaming codes for the practically relevant “online” setting-- without access to the sizes of the future frames—when each frame is sent immediately. We then use a learning-augmented algorithm to spread frame symbols over one extra frame to design approximately rate-optimal streaming codes. 

However, many real-world applications experience what we dub “partial burst” losses of only some packets per frame, unlike the existing model, which assumes all or no packets are lost for each frame. To address this gap, we introduce a new streaming-codes-based approach to videoconferencing called Tambur. When assessed over emulated networks, Tambur improves several key metrics of QoE compared to conventional methods (e.g., it reduces the frequency of freezes by 26%). We then extend the theoretical streaming model to accommodate partial bursts and design an online approximately rate-optimal streaming code. The code combines (a) a building block construction given any choice of how much parity to allocate per frame with (b) a learning-augmented algorithm to allocate parity per frame.

Thesis Committee:

Rashmi Vinayak (Chair)
Anupam Gupta
Ryan O’Donnell
Venkatesan Guruswami (University of California, Berkeley)

Add event to Google
Add event to iCal