02-07-2010, 06:26 PM
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.
