Enforcing Minimum-Cost Multicast Routing against Selfish Information Flows
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
computer science topics
Active In SP
**

Posts: 610
Joined: Jun 2010
#1
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.
Use Search at http://topicideas.net/search.php wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion
Reply
seminar class
Active In SP
**

Posts: 5,361
Joined: Feb 2011
#2
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 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 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
citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.157.4671&rep=rep1&type=pdf
Reply

Important Note..!

If you are not satisfied with above reply ,..Please

ASK HERE

So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page

Quick Reply
Message
Type your reply to this message here.


Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  MABS: Multicast Authentication Based on Batch Signature seminar class 20 12,346 03-07-2014, 06:19 PM
Last Post: Guest
  Developing a web application to transfer image and patient information project report maker 2 4,977 17-03-2014, 03:03 PM
Last Post: MichaelKa
  Hop-by-Hop Routing in Wireless Mesh Networks with Bandwidth Guarantees Abstract seminar projects maker 2 777 08-03-2014, 12:43 PM
Last Post: seminar project topic
  DEFENDING AGAINST SYBIL ATTACKS USING SYBILLIMIT PROTOCOL smart paper boy 3 1,702 01-03-2014, 01:01 PM
Last Post: sujivijay
  Enhancing the Trust of Internet Routing With Lightweight Route Attestation Report project girl 2 966 10-01-2014, 04:16 PM
Last Post: seminar project topic
  Detecting Anomalous Insiders in Collaborative Information Systems project girl 1 796 11-11-2013, 10:22 PM
Last Post: Guest
  Routing Security in Ad Hoc Wireless Networks seminar projects maker 0 565 26-09-2013, 02:20 PM
Last Post: seminar projects maker
  Comparing AODV and OLSR Routing Protocols. seminar projects maker 0 353 26-09-2013, 02:19 PM
Last Post: seminar projects maker
  Risk-Aware Response for Mitigating MANET Routing Attacks seminar projects maker 0 363 26-09-2013, 02:11 PM
Last Post: seminar projects maker
  Information Theoretic Framework of Trust Modeling and Evaluation for Ad Hoc Networks seminar projects maker 0 356 26-09-2013, 02:08 PM
Last Post: seminar projects maker