Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Convergence in Player-Specific Graphical Resource Allocation Games
KTH, School of Electrical Engineering (EES), Communication Networks. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre. (Laboratory for Communication Networks)ORCID iD: 0000-0001-7528-9994
KTH, School of Electrical Engineering (EES), Communication Networks. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0002-4876-0223
2012 (English)In: IEEE Journal on Selected Areas in Communications, ISSN 0733-8716, E-ISSN 1558-0008, Vol. 30, no 11, 2190-2199 p.Article in journal (Refereed) Published
Abstract [en]

As a model of distributed resource allocation in networked systems, we consider resource allocation games played over a influence graph. The influence graph models limited interaction between the players due to, e. g., the network topology: the payoff that an allocated resource yields to a player depends only on the resources allocated by her neighbors on the graph. We prove that pure strategy Nash equilibria (NE) always exist in graphical resource allocation games and we provide a linear time algorithm to compute equilibria. We show that these games do not admit a potential function: if there are closed paths in the influence graph then there can be best reply cycles. Nevertheless, we show that from any initial allocation of a resource allocation game it is possible to reach a NE by playing best replies and we provide a bound on the maximal number of update steps required. Furthermore we give sufficient conditions in terms of the influence graph topology and the utility structure under which best reply cycles do not exist. Finally we propose an efficient distributed algorithm to reach an equilibrium over an arbitrary graph and we illustrate its performance on different random graph topologies.

Place, publisher, year, edition, pages
2012. Vol. 30, no 11, 2190-2199 p.
Keyword [en]
resource allocation, graphical games, player-specific congestion games, best reply dynamics
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-109783DOI: 10.1109/JSAC.2012.121211ISI: 000311673200011Scopus ID: 2-s2.0-84870277594OAI: oai:DiVA.org:kth-109783DiVA: diva2:584224
Funder
Swedish Research Council, 2010-5812ICT - The Next Generation
Note

QC 20130109

Available from: 2013-01-08 Created: 2013-01-08 Last updated: 2017-12-06Bibliographically approved
In thesis
1. Bandwidth and Storage Allocation for Operator-owned Content Management Systems
Open this publication in new window or tab >>Bandwidth and Storage Allocation for Operator-owned Content Management Systems
2014 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

The demand for Internet-based visual content delivery has increased significantly in recent years, triggered mainly by the widespread use of Internet enabled smartphones and portable devices, and by the availability of super HD content.As a consequence, live and on-demand video content has become the most important source of network traffic in mobile and fixed networks alike.In order to be able to efficiently deliver the increasing amount of video traffic, network operators have started to deploy caches and operator-owned CDNs. These solutions do not only reduce the amount of transit traffic of the operators but they may also improve the customers' quality of experience, through bringing the video content closer to customers. Nevertheless, their efficiency is determined by the algorithms and protocols used to allocate resources, both in terms of storage and bandwidth. The work in this thesis addresses the allocation of these two resources for operator-owned content management systems.

In the first part of the thesis we consider a cache maintained by a single network operator. We investigate how caching at a network operator affects the content distribution system as a whole, and consequently, the efficiency of content delivery. We propose a model of the decision process undertaken by a network operator that aims at optimizing the efficiency of a cache by actively managing its bandwidth. We design different algorithms that aim at approximating the optimal cache bandwidth allocation and we evaluate them through extensive simulations and experiments. We show that active cache bandwidth allocation can significantly increase traffic savings.

We then consider the potential interaction among caches maintained by different network operators.We consider the problem of selfish replication on a graph as a modelof network operators that individually deploy replication systems, and try to leverage their peering agreements so as to minimize the traffic through their transit providers. We use game-theoretical tools to investigate the existence of stable and efficient allocations of content at the network operators. We show that selfish myopic updates of content allocations at different network operators lead the system to a stable state, and that the convergence speed depends on the underlying network topology. In addition, we show that interacting operator-owned caches can reach a stable content allocation without coordination, but coordination leads to more cost efficient content allocations.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2014. vi, 33 p.
Series
TRITA-EE, ISSN 1653-5146 ; 2014:015
Keyword
Content management systems, resource allocation
National Category
Communication Systems
Research subject
Electrical Engineering; Information and Communication Technology
Identifiers
urn:nbn:se:kth:diva-143880 (URN)978-91-7595-088-4 (ISBN)
Presentation
2014-04-24, Q2, Osquldas väg 10, KTH, Stockholm, 09:00 (English)
Opponent
Supervisors
Note

QC 20140401

Available from: 2014-04-01 Created: 2014-04-01 Last updated: 2016-12-06Bibliographically approved
2. Resource Allocation in Operator-owned Content Delivery Systems
Open this publication in new window or tab >>Resource Allocation in Operator-owned Content Delivery Systems
2016 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Live and on-demand video content have become the most important source of network traffic in mobile and fixed networks in recent years. In order to be able to efficiently deliver the increasing amount of video content, network operators have started to deploy caches and operator-owned CDNs. These solutions do not only reduce the amount of transit traffic of the operators but they may also improve the customers' quality of experience, through bringing the video content closer to customers. Nevertheless, their efficiency is determined by the algorithms and protocols used to allocate resources, both in terms of storage and bandwidth. The work in this thesis proposes and analyses algorithms for the allocation of these two resources for operator-owned content management systems. In the first part of the thesis we consider a cache maintained by a single network operator. We formulate the problem of content caching in a mobile backhaul as an integer program and we show that there exists an efficient centralized solution to the problem. Due to the prohibitive space complexity of the centralized algorithm, we propose two distributed approximations based on local information on the content demands. We then consider the problem of managing cache bandwidth so as to minimize the traffic cost of content delivery and we propose various approximations of the optimal stationary policy. We then consider the interaction among content management systems maintained by different network operators. First, we consider the problem of selfish replication on a graph as a model of network operators that use their caches to prefetch popular content, and try to leverage their peering agreements so as to minimize the traffic through their transit providers. We design efficient distributed algorithms that compute a stable content allocation through selfish myopic updates of content allocations at different network operators. We show that, if the cost function is neighbor-specific, network operators need bilateral payments to compute a stable content allocation that is individually rational. We then consider the problem of coordinated caching in a network of autonomous systems engaged in content-level peering. We investigate whether interacting operator-owned caches need explicit coordination in order to reach a stable content allocation efficiently. Beyond the theoretical contributions made to the analysis of player-specific graphical congestion games and their generalizations, the results in thesis provide guidelines for the design of protocols for standalone and for interconnected operator-owned content management systems.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2016. vi, 44 p.
Series
TRITA-EE, ISSN 1653-5146 ; 2015:120
National Category
Communication Systems
Research subject
Electrical Engineering; Electrical Engineering
Identifiers
urn:nbn:se:kth:diva-180060 (URN)978-91-7595-835-4 (ISBN)
Public defence
2016-01-29, F3, Lindstedtsvägen 26, KTH, Stockholm, 10:00 (English)
Opponent
Supervisors
Note

QC 20160107

Available from: 2016-01-07 Created: 2016-01-07 Last updated: 2016-01-11Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Pacifici, ValentinoDán, György

Search in DiVA

By author/editor
Pacifici, ValentinoDán, György
By organisation
Communication NetworksACCESS Linnaeus Centre
In the same journal
IEEE Journal on Selected Areas in Communications
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 167 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf