Feedback-free multicast prefix protocols

Developing scalable, reliable multicast protocols for lossy networks presents an array of challenges. In this work we focus on scheduling policies which determine what data the sender places into each sent packet. Our objective is to develop scalable policies which provably deliver a long intact pre...

Full description

Saved in:
Bibliographic Details
Main Authors: Bartal, Y., Byers, J.W., Luby, M., Raz, D.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Computer science
Encoding
Error correction
Forward error correction
Liver
Multicast algorithms
Multicast protocols
Performance analysis
Scalability
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Developing scalable, reliable multicast protocols for lossy networks presents an array of challenges. In this work we focus on scheduling policies which determine what data the sender places into each sent packet. Our objective is to develop scalable policies which provably deliver a long intact prefix of the message to each receiver at each point in time during the transmission. To accurately represent conditions in existing networks, our theoretical model of the network allows bursty periods of packet loss which can vary widely and arbitrarily over time. Under this general model, we give a proof that there is an inherent performance gap between algorithms which use encoding schemes such as forward error correction (FEC) and those which do not. We then present simple, feedback-free policies which employ FEC and have guaranteed worst-case performance. Our analytic results are complemented by trace-driven simulations which demonstrate the effectiveness of our approach in practice.
DOI:10.1109/ISCC.1998.702473