Name
Abstract | ||
|---|---|---|
We study multicast in a noncooperative environment where information flows selfishly route themselves through the cheapest paths available. The main challenge is to enforce such selfish multicast flows to stabilize at a socially optimal operating point incurring minimum total edge cost, through appropriate cost allocation and other economic measures, with replicable and encodable properties of information flows considered. We show that known cost allocation schemes are not sufficient. We provide a shadow-price-based cost allocation for networks without capacity limits and show that it enforces minimum-cost multicast. This improves previous result where a 2-approximate multicast flow is enforced. For capacitated networks, computing cost allocation by ignoring edge capacities will not yield correct results. We show that an edge tax scheme can be combined with a cost allocation to strictly enforce optimal multicast flows in this more realistic case. If taxes are not desirable, they can be returned to flows while maintaining weak enforcement of the optimal flow. We relate the taxes to VCG payment schemes and discuss an efficient primal-dual algorithm that simultaneously computes the taxes, the cost allocation, and the optimal multicast flow, with potential of fully distributed implementations. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/TPDS.2008.229 | IEEE Trans. Parallel Distrib. Syst. |
Keywords | Field | DocType |
enforcing minimum-cost multicast routing,index terms—communication/networking,multicast,known cost allocation scheme,selfish information flows,cost allocation,optimal multicast flow,appropriate cost allocation,selfish multicast,computing cost allocation,graph algorithms.,minimum-cost multicast,2-approximate multicast flow,minimum total edge cost,shadow-price-based cost allocation,finance,routing,shadow price,game theory,linear programming,network coding,unicast,indexing terms,information flow,cost function,environmental economics | Linear network coding,Computer science,Operating point,Computer network,Implementation,Game theory,Linear programming,Unicast,Multicast,Cost allocation,Distributed computing | Journal |
Volume | Issue | ISSN |
20 | 9 | 1045-9219 |
Citations | PageRank | References |
0 | 0.34 | 21 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zongpeng Li | 1 | 2054 | 153.21 |
| C. Williamson | 2 | 2998 | 417.38 |