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
Distributed Algorithms for Content Caching in Mobile Backhaul Networks
KTH, School of Electrical Engineering (EES), Communication Networks. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.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-6466-8304
KTH, School of Electrical Engineering (EES), Communication Networks. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0002-4876-0223
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. 313-321 p., 7809666
Keyword [en]
edge caching, in-network caching, content placement, tree, mobile backhaul, algorithms
National Category
Computer Systems
Research subject
Electrical Engineering; Telecommunication; Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-180056DOI: 10.1109/ITC-28.2016.149ISI: 000393569000040Scopus ID: 2-s2.0-85013046216ISBN: 9780988304512 (print)OAI: oai:DiVA.org:kth-180056DiVA: diva2:891648
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
In thesis
1. 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

fulltext(473 kB)32 downloads
File information
File name FULLTEXT01.pdfFile size 473 kBChecksum SHA-512
3f6bb4871ede9d390d11fde6acea89f9dcb7d33e1f0c3d33d21d38a70be8d68bda55b8a16d9e575ca4157e2837c47cf2e29b781af0f32685e5c4f54a3cfaea9f
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopusConference webbsite

Authority records BETA

Pacifici, ValentinoDán, György

Search in DiVA

By author/editor
Pacifici, ValentinoJosilo, SladjanaDán, György
By organisation
Communication NetworksACCESS Linnaeus Centre
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 32 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

doi
isbn
urn-nbn

Altmetric score

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