06-05-2011, 11:45 AM
Abstract
Westudy multicast in a noncooperative environment where information flows selfishly route themselves through the cheapestpaths available. The main challenge is to enforce such selfish multicast flows to stabilize at a socially optimal operating point incurringminimum total edge cost, through appropriate cost allocation and other economic measures, with replicable and encodable properties ofinformation flows considered. We show that known cost allocation schemes are not sufficient. We provide a shadow-price-based costallocation for networks without capacity limits and show that it enforces minimum-cost multicast. This improves previous result where a2-approximate multicast flow is enforced. For capacitated networks, computing cost allocation by ignoring edge capacities will not yieldcorrect results. We show that an edge tax scheme can be combined with a cost allocation to strictly enforce optimal multicast flows in thismore realistic case. If taxes are not desirable, they can be returned to flows while maintaining weak enforcement of the optimal flow. Werelate the taxes toVCGpayment schemes and discuss an efficient primal-dual algorithm that simultaneously computes the taxes, the costallocation, and the optimal multicast flow, with potential of fully distributed implementations.Index Terms—Communication/networking, multicast, graph algorithms.
1 INTRODUCTION
THE classic min-cost flow problem [1], [2] studies the mincosttransmission of commodity flows across a flownetwork, where each unit edge capacity utilization incurs acost, and the goal is to minimize the total edge cost whilesustaining a target end-to-end flow rate. We consider in thispaper the min-cost transmission of information flows in adata network and focus on multicast transmissions wherecommon data is disseminated from a source to multipledestinations. Multicast models real-world applications suchas media streaming or the dissemination of popular files.The cost of a communication page link is an abstraction of realworldcost, including delay latency, power consumption,and monetary charges.While both commodity flows and information flows needto confine to the network topology and respect page link capacitylimits, information flows are unique in that they are replicableand encodable. Replication and encoding are in generalnecessary in achieving the full capacity of a data network,and such coding operations applied at potentially any node inthe network are referred to as network coding [3], [4].Traditional models of multicast are usually based on Steinertrees, in which either maximizing multicast rate or minimizingmulticast cost is computationally intractable [5], [6].Recent research in network coding reveals a dramaticallydifferent structure of multicast: in a directed network, amulticast rate d is feasible if and only if (iff) it is feasible as anindependent unicast from the sender to each receiver Based on the above result, efficient optimization algorithmsfor both multicast rate and multicast cost have beensuccessfully designed in the cooperative environment, byexploiting the underlying network flow structure [7], [8].We consider in this paper a noncooperative environmentwhere flows selfishly minimize their own cost by routingthemselves through the cheapest available paths. Suchselfish behavior is a well-studied phenomenon in gametheory, and the stable state of such selfish routing games ischaracterized as a Nash Equilibrium, where no flow hasincentive to deviate from its current route alone, assumingthe rest of the flows stick to their routes. It is known thatsuch Nash solutions can lead to very bad performances [9],[10] in general. Therefore, it is necessary to imposecalculated economic regulations in the network such thatindividual decisions of selfish flows jointly lead to a sociallydesirable operation state of the network.Previous research has considered the enforcement ofoptimal multicommodity flows [11], [12], [13]. While theyalso employ economic measures to regulate the routing offlows among potential paths, it is unique and vital in themulticast problem to encourage flow cost sharing. It is wellknown that cost sharing can be achieved through combiningindividual unicast paths into multicast trees. However,two problems are evident along the traditional multicasttree direction. First, the cost may not be really minimum,since a different multicast flow with lower cost may befound by also exploiting the encodable property ofinformation flows [7], [6] (an example is shown in Fig. 1).Second, since optimal routing based on multicast trees isNP-hard to compute, it is unlikely that it would be exactlyenforced by any efficiently computable regulation schemein general network topologies [14]. The best result prior tothis work is a bicriteria analysis by Bhadra et al. [15], whichshows that there always exist cost sharing
Download full report
http://citeseerx.ist.psu.edu/viewdoc/dow...1&type=pdf
Westudy multicast in a noncooperative environment where information flows selfishly route themselves through the cheapestpaths available. The main challenge is to enforce such selfish multicast flows to stabilize at a socially optimal operating point incurringminimum total edge cost, through appropriate cost allocation and other economic measures, with replicable and encodable properties ofinformation flows considered. We show that known cost allocation schemes are not sufficient. We provide a shadow-price-based costallocation for networks without capacity limits and show that it enforces minimum-cost multicast. This improves previous result where a2-approximate multicast flow is enforced. For capacitated networks, computing cost allocation by ignoring edge capacities will not yieldcorrect results. We show that an edge tax scheme can be combined with a cost allocation to strictly enforce optimal multicast flows in thismore realistic case. If taxes are not desirable, they can be returned to flows while maintaining weak enforcement of the optimal flow. Werelate the taxes toVCGpayment schemes and discuss an efficient primal-dual algorithm that simultaneously computes the taxes, the costallocation, and the optimal multicast flow, with potential of fully distributed implementations.Index Terms—Communication/networking, multicast, graph algorithms.
1 INTRODUCTION
THE classic min-cost flow problem [1], [2] studies the mincosttransmission of commodity flows across a flownetwork, where each unit edge capacity utilization incurs acost, and the goal is to minimize the total edge cost whilesustaining a target end-to-end flow rate. We consider in thispaper the min-cost transmission of information flows in adata network and focus on multicast transmissions wherecommon data is disseminated from a source to multipledestinations. Multicast models real-world applications suchas media streaming or the dissemination of popular files.The cost of a communication page link is an abstraction of realworldcost, including delay latency, power consumption,and monetary charges.While both commodity flows and information flows needto confine to the network topology and respect page link capacitylimits, information flows are unique in that they are replicableand encodable. Replication and encoding are in generalnecessary in achieving the full capacity of a data network,and such coding operations applied at potentially any node inthe network are referred to as network coding [3], [4].Traditional models of multicast are usually based on Steinertrees, in which either maximizing multicast rate or minimizingmulticast cost is computationally intractable [5], [6].Recent research in network coding reveals a dramaticallydifferent structure of multicast: in a directed network, amulticast rate d is feasible if and only if (iff) it is feasible as anindependent unicast from the sender to each receiver Based on the above result, efficient optimization algorithmsfor both multicast rate and multicast cost have beensuccessfully designed in the cooperative environment, byexploiting the underlying network flow structure [7], [8].We consider in this paper a noncooperative environmentwhere flows selfishly minimize their own cost by routingthemselves through the cheapest available paths. Suchselfish behavior is a well-studied phenomenon in gametheory, and the stable state of such selfish routing games ischaracterized as a Nash Equilibrium, where no flow hasincentive to deviate from its current route alone, assumingthe rest of the flows stick to their routes. It is known thatsuch Nash solutions can lead to very bad performances [9],[10] in general. Therefore, it is necessary to imposecalculated economic regulations in the network such thatindividual decisions of selfish flows jointly lead to a sociallydesirable operation state of the network.Previous research has considered the enforcement ofoptimal multicommodity flows [11], [12], [13]. While theyalso employ economic measures to regulate the routing offlows among potential paths, it is unique and vital in themulticast problem to encourage flow cost sharing. It is wellknown that cost sharing can be achieved through combiningindividual unicast paths into multicast trees. However,two problems are evident along the traditional multicasttree direction. First, the cost may not be really minimum,since a different multicast flow with lower cost may befound by also exploiting the encodable property ofinformation flows [7], [6] (an example is shown in Fig. 1).Second, since optimal routing based on multicast trees isNP-hard to compute, it is unlikely that it would be exactlyenforced by any efficiently computable regulation schemein general network topologies [14]. The best result prior tothis work is a bicriteria analysis by Bhadra et al. [15], whichshows that there always exist cost sharing
Download full report
http://citeseerx.ist.psu.edu/viewdoc/dow...1&type=pdf
