Enforcing Minimum-Cost Multicast Routing against Selfish Information Flows

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 relate the taxes toVCGpayment 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.




Algorithm / Technique used:

An Efficient Primal-Dual Algorithm.




Algorithm Description:
We formulate the min-cost multicast problem into a pair of primal and dual linear programs, based on the aforementioned multicast feasibility result with network coding due to Ahlswede et al. and propose to allocate edge costs based on the shadow prices of flow merging constraints. We show that a Nash Equilibrium exists and that any optimal multicast flow has a corresponding cost allocation which makes it a Nash flow. The flow-cost pair at Nash Equilibrium also achieves a balanced budget, i.e., the total charges to flows exactly equal the total cost incurred at edges across the network.


Existing System:

Conventionally, most network protocols assume that the network entities that participate in the network activities will always behave as instructed. However, in practice, most network entities will try to maximize their own benefits instead of altruistically contribute to the network by following the prescribed protocols, which is known as selfish. Thus, new protocols should be designed for the non-cooperative network, which is composed of selfish entities. In this paper, we specifically show how to design strategy proof multicast protocols for non-cooperative networks such that these selfish entities will follow the protocols out of their own interests. By assuming that a group of receivers is willing to pay to receive the multicast service, we specifically give a general framework to decide whether it is possible, and how if possible to transform an existing multicast protocol to a strategy proof multicast protocol. We then show how the payments to those relay entities are shared fairly among all receivers so that it encourages collaboration among receivers. As a running example, we show how to design the strategy proof multicast protocol for the currently used core-based multicast structure.

Proposed System:

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.


Hardware Requirements:

¢ System : Pentium IV 2.4 GHz.
¢ Hard Disk : 40 GB.
¢ Floppy Drive : 1.44 Mb.
¢ Monitor : 15 VGA Colour.
¢ Mouse : Logitech.
¢ Ram : 256 Mb.


Software Requirements:

¢ Operating system : - Windows XP Professional.
¢ Coding Language : - Java.
¢ Tool Used : - Eclipse.

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