Naslov
On Cost Allocation for Multicasting

Autori
Skorin-Kapov, Darko ; Skorin-Kapov, Jadranka

Vrsta, podvrsta i kategorija rada
Sažeci sa skupova, sažetak, znanstveni

Izvornik
6th Annual Conference of National Business and Economic Society / Mike Bond - : NBES, 2006

Skup
6th Annual Conference of National Business and Economic Society

Mjesto i datum
Los Cabos, Meksiko, 07.03.2006. - 11.03.2006

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
network design; cost allocation; cooperative games

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA