Change search
ReferencesLink to record
Permanent link

Direct link
Optimal network locality in distributed virtualized data-centers
Telecom Bretagne.
Telecom Bretagne.
Telecom Bretagne.
Linköping University, The Institute of Technology. Linköping University, Department of Science and Technology, Communications and Transport Systems.
2011 (English)In: Computer Communications, ISSN 0140-3664, E-ISSN 1873-703X, Vol. 34, no 16, 1968-1979 p.Article in journal (Refereed) Published
Abstract [en]

Cost efficiency is a key aspect in deploying distributed service in networks within decentralized service delivery architectures. In this paper, we address this aspect from an optimization and algorithmic standpoint. The research deals with the placement of service components to network sites, where the performance metric is the cost for acquiring components between the sites. The resulting optimization problem, which we refer to as the k-Component Multi-site Placement Problem, is applicable to service distribution in a wide range of communication networking scenarios. We provide a theoretical analysis of the problems computational complexity, and develop an integer programming model for providing reference results for performance benchmarking. On the algorithmic side, we present four approaches: an algorithm with approximation guarantee and three heuristics algorithms. The first heuristic is derived from graph theory on domatic partition. The second heuristic, built on intuition, admits distributed computation. The third heuristic emphasizes on fairness in cost distribution among the sites. We report simulation results for sets of networks where cost is represented by round-trip time (RTT) originating from real measurements. For small networks, the integer model is used to study algorithm performance in terms of optimality. Large networks are used to compare the algorithms relatively to each other. Among the algorithms, the heuristic based on intuition has close-to-optimal performance, and the fairness heuristic achieves a good balance between single-site cost and the overall one. In addition, the experiments demonstrate the significance of optimization for cost reduction in comparison to a the random allocation strategy.

Place, publisher, year, edition, pages
Elsevier , 2011. Vol. 34, no 16, 1968-1979 p.
Keyword [en]
Distributed services, Network locality, Optimization problem, Peer-to-peer, Approximation algorithm
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-72030DOI: 10.1016/j.comcom.2011.06.002ISI: 000296123400008OAI: diva2:455988
Funding Agencies|Vipeer project||Agence Nationale de la Recherche, France||CENIIT, Linkoping University, Sweden||Available from: 2011-11-11 Created: 2011-11-11 Last updated: 2012-06-25

Open Access in DiVA

fulltext(495 kB)281 downloads
File information
File name FULLTEXT01.pdfFile size 495 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Yuan, Di
By organisation
The Institute of TechnologyCommunications and Transport Systems
In the same journal
Computer Communications
Engineering and Technology

Search outside of DiVA

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

Altmetric score

Total: 68 hits
ReferencesLink to record
Permanent link

Direct link