Multicasting is a natural paradigm for streaming live multimedia to
multiple end receivers. Since IP multicast is not widely deployed, many application-layer multicast protocols have been proposed. However, all of these schemes focus on the construction of multicast trees, where a relatively small number of links carry the multicast streaming load, while the capacity of most of the other links in the overlay network remain unused. In this paper, we propose <i>CodedStream</i>, a high-bandwidth live media distribution system based on end-system overlay multicast. In CodedStream, we construct a <i>k</i>-redundant multicast graph (a directed acyclic graph) as the multicast topology, on which <i>network coding </i>is applied to work around bottlenecks. Simulation results have shown that the combination of <i>k</i>-redundant multicast graph and network coding may indeed bring significant benefits with respect to improving the quality of live media at the end receivers.