engleski

On Cost Allocation for Multicasting

We analyze the cost allocation problem associated with broadcasting information of common interest from some source to specific network users. Multicast routing uses a minimum cost tree connecting all the receivers to the source. This routing also allows use of some non-user nodes as switching points. Namely, whenever a message needs to be broadcast to a subset of receivers, multicast routing chooses the so-called minimum cost Steiner Tree (ST) that spans the source and all the receivers. It is well known that finding the minimum cost ST is computationally intractable. Consequently, several heuristic approaches for solving this problem have been developed in the literature. The objective of this paper is to address the cost allocation associated with practical methods used in multicasting. We assume that the best-known Steiner tree is obtained using distributed minimum spanning tree-based heuristic. We must then allocate the cost of edges to the users who are represented as receiver nodes. We define the associated multicasting cooperative game in the characteristic function form. We then construct a cost allocation scheme that efficiently finds some cost allocations that are in the core of the above multicasting game. These cost allocations stimulate cooperation and are fair in the sense that no subset of users (receivers) has monetary incentive to secede. Namely, each subset of users does not pay more than they would pay if they secede and form their own network.

network design; cost allocation; cooperative games

nije evidentirano