Pricing multicasting in more practical network models
Micah Adler, Dan Rubenstein · 2002
In [9], Feigenbaum, Papadimitriou and Shenker initiate the study of pricing algorithms for multicast transmission. In this paper, we build on this work by studying the eect on the complexity of pricing when two practical considerations are incorporated into the network model. In particular, we study a model where the session is oered at a number of dierent rates of transmission, and where there is a cost for enabling multicasting at each node of the network. As a test case for the dierent types of pricing that can occur, we consider a pricing mechanism, called Marginal Cost, that has seen considerable attention in simpler network models. We demonstrate that the details of how multiple rates are provided has a signicant impact on the complexity of pricing. For multiple rates provided via the layered paradigm, we provide a distributed algorithm for computing Marginal Cost eciently in terms of local computation and message complexity. The bit complexity (per edge) of this algorithm depends linearly on the product of the tree height and the number of possible rates. However, we provide two lower bounds on bit complexity, demonstrating that computing Marginal Cost (a) with multiple rates requires a bit complexity that is linear in the number of rates, and (b) with a cost for enabling multicasting requires a bit complexity that is linear in the height of the tree. A modication of our algorithm for the layered paradigm also applies to the split session paradigm of providing multiple rates, but in this case, both the local computation and the bit complexity become exponential in the number of possible rates. However, we also demonstrate that for the split session paradigm, the problem becomes NP-Hard even to approximate if the number of possible rates i...