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
Resource Allocation in Operator-owned Content Delivery Systems
KTH, School of Electrical Engineering (EES), Communication Networks.ORCID iD: 0000-0001-7528-9994
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: urn:nbn:se:kth:diva-180060ISBN: 978-91-7595-835-4 (print)OAI: oai:DiVA.org:kth-180060DiVA: diva2:891697
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
List of papers
1. Distributed Algorithms for Content Caching in Mobile Backhaul Networks
Open this publication in new window or tab >>Distributed Algorithms for Content Caching in Mobile Backhaul Networks
2016 (English)In: Proceedings of the 28th International Teletraffic Congress, ITC 2016, Institute of Electrical and Electronics Engineers (IEEE), 2016, 313-321 p., 7809666Conference paper, Published paper (Refereed)
Abstract [en]

The growing popularity of mobile multimedia content and the increase of wireless access bitrates are straining backhaul capacity in mobile networks. A cost-effective solution to reduce the strain, enabled by emerging all-IP 4G and 5G mobile backhaul architectures, could be in-network caching of popular content during times of peak demand. In this paper we formulate the problem of content caching in a mobile backhaul as a binary integer programming problem, and we propose a 2-approximation algorithm for the problem. The 2-approximation requires full information about the network topology and the link costs, as well as about the content demands at the different caches, we thus propose two distributed algorithms that are based on limited information on the content demands. We show that the distributed algorithms terminate in a finite number of steps, and we provide analytical results on their approximation ratios. We use simulations to evaluate the proposed algorithms in terms of the achieved approximation ratio and computational complexity on realistic mobile backhaul topologies.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2016
Keyword
edge caching, in-network caching, content placement, tree, mobile backhaul, algorithms
National Category
Computer Systems
Research subject
Electrical Engineering; Telecommunication; Computer Science
Identifiers
urn:nbn:se:kth:diva-180056 (URN)10.1109/ITC-28.2016.149 (DOI)000393569000040 ()2-s2.0-85013046216 (Scopus ID)9780988304512 (ISBN)
Conference
28th International Teletraffic Congress, ITC 2016, University of WurzburgWurzburg, Germany, 12 September 2016 through 16 September 2016
Funder
Swedish Research Council, 621-2014-6035Swedish Foundation for Strategic Research
Note

QC 20160811

Available from: 2016-01-07 Created: 2016-01-07 Last updated: 2017-06-09Bibliographically approved
2. Cache Bandwidth Allocation for P2P File Sharing Systems to Minimize Inter-ISP Traffic
Open this publication in new window or tab >>Cache Bandwidth Allocation for P2P File Sharing Systems to Minimize Inter-ISP Traffic
2016 (English)In: IEEE/ACM Transactions on Networking, ISSN 1063-6692, E-ISSN 1558-2566, Vol. 24, no 1, 437-448 p.Article in journal (Refereed) Published
Abstract [en]

Many Internet service providers (ISPs) have deployed peer-to-peer (P2P) caches in their networks in order to decrease costly inter-ISP traffic. A P2P cache stores parts of the most popular contents locally, and if possible serves the requests of local peers to decrease the inter-ISP traffic. Traditionally, P2P cache resource management focuses on managing the storage resource of the cache so as to maximize the inter-ISP traffic savings. In this paper we show that, when there are many overlays competing for the upload bandwidth of a P2P cache, then in order to maximize the inter-ISP traffic savings the cache's upload bandwidth should be actively allocated among the overlays. We formulate the problem of P2P cache bandwidth allocation as a Markov decision process, and propose three approximations to the optimal cache bandwidth allocation policy. We use extensive simulations and experiments to evaluate the performance of the proposed policies, and show that the bandwidth allocation policy that prioritizes swarms with a small ratio of local peers to all peers in the swarm can improve the inter-ISP traffic savings in BitTorrent-like P2P systems by up to 30 to 60 percent.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2016
Keyword
Peer-to-peer content distribution, caching, Markov decision process, Inter-ISP traffic management
National Category
Communication Systems
Research subject
Electrical Engineering
Identifiers
urn:nbn:se:kth:diva-155324 (URN)10.1109/TNET.2014.2367021 (DOI)000370969300033 ()
Funder
Swedish Research Council, 2010:5812
Note

QC 20141204

Available from: 2014-11-04 Created: 2014-11-04 Last updated: 2017-12-05Bibliographically approved
3. Convergence in Player-Specific Graphical Resource Allocation Games
Open this publication in new window or tab >>Convergence in Player-Specific Graphical Resource Allocation Games
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.

Keyword
resource allocation, graphical games, player-specific congestion games, best reply dynamics
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-109783 (URN)10.1109/JSAC.2012.121211 (DOI)000311673200011 ()2-s2.0-84870277594 (Scopus ID)
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
4. Distributed Algorithms for Content Allocation in Interconnected Content Distribution Networks
Open this publication in new window or tab >>Distributed Algorithms for Content Allocation in Interconnected Content Distribution Networks
2015 (English)In: Proc. of IEEE Infocom, IEEE , 2015Conference paper, Published paper (Refereed)
Abstract [en]

Internet service providers increasingly deploy internal CDNs with the objective of reducing the traffic on their transit links and to improve their customers' quality of experience. Once ISP managed CDNs (nCDNs) become commonplace, ISPs would likely provide common interfaces to interconnect their nCDNs for mutual benefit, as they do with peering today. In this paper we consider the problem of using distributed algorithms for computing a content allocation for nCDNs. We show that if every ISP aims to minimize its cost and bilateral payments are not allowed then it may be impossible to compute a content allocation. For the case of bilateral payments we propose two distributed algorithms, the aggregate value compensation (AC) and the object value compensation (OC) algorithms, which differ in terms of the level of parallelism they allow and in terms of the amount of information exchanged between nCDNs. We prove that the algorithms converge, and we propose a scheme to ensure ex-post individual rationality. Simulations performed on a real AS-level network topology and synthetic topologies show that the algorithms have geometric rate of convergence, and scale well with the graphs' density and the nCDN capacity.

Place, publisher, year, edition, pages
IEEE, 2015
National Category
Computer Systems Communication Systems Telecommunications
Identifiers
urn:nbn:se:kth:diva-179041 (URN)10.1109/INFOCOM.2015.7218624 (DOI)000370720100264 ()2-s2.0-84954245249 (Scopus ID)978-1-4799-8381-0 (ISBN)
Conference
IEEE Infocom
Note

QC 20151211

Available from: 2015-12-09 Created: 2015-12-09 Last updated: 2016-03-29Bibliographically approved
5. Coordinated Selfish Distributed Caching for Peering Content-centric Networks
Open this publication in new window or tab >>Coordinated Selfish Distributed Caching for Peering Content-centric Networks
2016 (English)In: IEEE/ACM Transactions on Networking, ISSN 1063-6692, E-ISSN 1558-2566, Vol. PP, no 99, 1-12 p.Article in journal (Refereed) Accepted
Keyword
Resource management, Internet, Routing, IEEE transactions, Protocols, Convergence, Numerical models
National Category
Communication Systems
Identifiers
urn:nbn:se:kth:diva-180059 (URN)10.1109/TNET.2016.2541320 (DOI)
Note

QS 2016

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

Open Access in DiVA

Thesis(2624 kB)214 downloads
File information
File name FULLTEXT01.pdfFile size 2624 kBChecksum SHA-512
5c2e8752d694d1b1c696b9b4b6c8d843ff5733f5558acdadfd52bdd3b5deada01fd8d489f3c0211e234d8d2b034da9ffe9c2c81a06a68c3c8846d06ddf3a721c
Type fulltextMimetype application/pdf

Authority records BETA

Pacifici, Valentino

Search in DiVA

By author/editor
Pacifici, Valentino
By organisation
Communication Networks
Communication Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 214 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 685 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