Paper #22

A Centralized, Tree-Based Approach to
Network Repair Service for Multicast Streaming

Dan Rubenstein
University of Massachusetts at Amherst

Nicholas F. Maxemchuk & David Shur
AT&T Labs - Research


IP multicast provides best-effort delivery. Packets encounter variable delays and may be lost because of transmission errors and buffer overflows. Real-time multimedia streaming services require that most packets arrive at the receivers prior to an application deadline. Multicast quality on the current Internet is often inadequate for these applications. We have solved this problem by placing repair servers inside the network. The repair servers recover missing packets by communicating with each other, then re-multicast the re-paired stream to nearby receivers on a new address. Multicast reception in the constrained area is typically much better than in the wide area Internet.

In this paper we address the problem of constructing a repair graph. The repair graph shows which repair servers each repair server communicates with to recover missing messages. Our objectives when constructing this graph conflict with each other. We want high reliability: every repair server to recover as many missing messages as possible, as quickly as possible. But we also want low cost: this recovery should use as little of the network bandwidth as possible. We present a centralized algorithm to generate re-pair graphs. We demonstrate through simulation that these graphs achieve a level of reliability that is almost as high as that achieved by repair graphs specifically designed for high reliability. At the same time, our graphs maintain a cost that is almost as low as the cost in repair graphs designed for low cost.

Download a copy of this paper in either: Compressed PostScript (59K) - or - PDF (96K) format.

Back to the NOSSDAV 2000 On-Line Proceedings.


- Last revised: Weds Jun 27 20:56:29 EDT 2000