Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Pricing multicasting in more flexible network models

Pricing multicasting in more flexible network models The problem of designing efficient algorithms for sharing the cost of multicasting has recently received considerable attention. In this article, we examine the effect on the complexity of pricing when two flexibility-enhancing mechanisms are incorporated into the network model. In particular, we study a model where the session is offered at a number of different rates of transmission, and where there is a cost for enabling multicasting at each node of the network. We consider two techniques that have been used in practice to provide multiple rates: using a layered transmission scheme (called the layered paradigm ) and using different multicast groups for each possible rate (called the split session paradigm ). We demonstrate that the difference between these two paradigms has a significant impact on the complexity of pricing multicasting.For the layered paradigm, we provide a distributed algorithm for computing pricing efficiently in terms of local computation and message complexity. For the split session paradigm, on the other hand, we demonstrate that this problem can be solved in polynomial time if the number of possible rates is fixed, but if the number of rates is part of the input, then the problem becomes NP-Hard even to approximate. We also examine the effect of delivering the transmissions for the various rates from different locations within the network. We show that, in this case, the pricing problem becomes NP-Hard for the split session paradigm even for a fixed constant number of possible rates but if layering is used, then it can be solved in polynomial time by formulating the problem as a totally unimodular integer program. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

Pricing multicasting in more flexible network models

Download PDF
26 pages

Loading next page...
 
/lp/association-for-computing-machinery/pricing-multicasting-in-more-flexible-network-models-Fts5PhpitS
Publisher
Association for Computing Machinery
Copyright
Copyright © 2005 by ACM Inc.
ISSN
1549-6325
DOI
10.1145/1077464.1077469
Publisher site
See Article on Publisher Site

Abstract

The problem of designing efficient algorithms for sharing the cost of multicasting has recently received considerable attention. In this article, we examine the effect on the complexity of pricing when two flexibility-enhancing mechanisms are incorporated into the network model. In particular, we study a model where the session is offered at a number of different rates of transmission, and where there is a cost for enabling multicasting at each node of the network. We consider two techniques that have been used in practice to provide multiple rates: using a layered transmission scheme (called the layered paradigm ) and using different multicast groups for each possible rate (called the split session paradigm ). We demonstrate that the difference between these two paradigms has a significant impact on the complexity of pricing multicasting.For the layered paradigm, we provide a distributed algorithm for computing pricing efficiently in terms of local computation and message complexity. For the split session paradigm, on the other hand, we demonstrate that this problem can be solved in polynomial time if the number of possible rates is fixed, but if the number of rates is part of the input, then the problem becomes NP-Hard even to approximate. We also examine the effect of delivering the transmissions for the various rates from different locations within the network. We show that, in this case, the pricing problem becomes NP-Hard for the split session paradigm even for a fixed constant number of possible rates but if layering is used, then it can be solved in polynomial time by formulating the problem as a totally unimodular integer program.

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Jul 1, 2005

There are no references for this article.