An algorithm for optimal multicast of multimedia streams
Nachum Shacham, James S. Meditch · 2002
Flexibility and efficiency of multipoint, multimedia communications will be greatly enhance if participants get delivery of only the streams, each at a specified level of quality, each user wishes to receive. The authors investigate the problem of optimal distribution of multiple streams from a source to a set of destinations, subject to the destinations' requirements and the limitations on available link capacities. Users' requests are expressed by means of bids, which are non-negative values assigned by each destination to each offered stream. Assuming that the source gains an amount equal to a user's bid whenever a stream is delivered to that user, we seek distributions that maximize the sources' gain. The optimal assignment of streams to the links of a multicast tree is formulated as an integer programming problem, and an algorithm for determining the optimal assignment is presented. The algorithm consists of three procedures: listing candidate assignments on a single link, listing candidate assignments on tree paths, and evaluating the gain for each assignment. The algorithm's correctness is proved, and its computational complexity is ascertained.>