Please use this identifier to cite or link to this item:
Title: Capacity Allocation Games for Network-Coded Multicast Streaming
Authors: Anshelevich, Elliot
Çaşkurlu, Buğra
Kar, Koushik
Zhang, Hang
Keywords: Capacity allocation game
Multicast streaming
Issue Date: Apr-2014
Publisher: IEEE-INST Electrical Electronics Engineers Inc.
Source: Anshelevich, E., Caskurlu, B., Kar, K., & Zhang, H. (2014). Capacity allocation games for network-coded multicast streaming. IEEE/ACM Transactions on Networking (TON), 22(2), 595-607.
Abstract: In this paper, we formulate and study a capacity allocation game between a set of receivers (players) that are interested in receiving multicast data (video/multimedia) being streamed from a server through a multihop network. We consider fractional multicast streaming, where the multicast stream from the source (origin-server) to any particular receiver (end-user) can be split over multiple paths. The receivers are selfish and noncooperative, but must collaboratively purchase capacities of links in the network, as necessary for delivery of the multicast stream from the source to the individual receivers, assuming that the multicast stream is network-coded. For this multicast capacity allocation (network formation) game, we show that the Nash equilibrium is guaranteed to exist in general. For a 2-tier network model where the receivers must obtain the multicast data from the source through a set of relay nodes, we show that the price of stability is at most 2, and provide a polynomial-time algorithm that computes a Nash equilibrium whose social cost is within a factor of 2 of the socially optimum solution. For more general network models, we show that there exists a 2-approximate Nash equilibrium, whose cost is at most two times the social optimum. We also give a polynomial-time algorithm that computes a (2+epsilon)-approximate Nash equilibrium for any epsilon > 0 , whose cost is at most two times the social optimum. Simulation studies show that our algorithms generate efficient Nash equilibrium allocation solutions for a vast majority of randomly generated network topologies.
ISSN: 1558-2566
Appears in Collections:Bilgisayar Mühendisliği Bölümü / Department of Computer Engineering
WoS İndeksli Yayınlar Koleksiyonu / WoS Indexed Publications Collection

Show full item record

CORE Recommender


checked on Sep 23, 2022


checked on Sep 24, 2022

Page view(s)

checked on Dec 26, 2022

Google ScholarTM



Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.