Abstract:

Cost efficiency is a key aspect in deploying distributed service in networks
within decentralized service delivery architectures.  We have addressed 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 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 problem's 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 (3/2k-5/2)-approximate algorithm is inspired by a recent
work on Facility Location Problem. 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 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 solution 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 random allocation strategy.


Short bio
=========
Gwendal Simon received his PhD degree in Computer Science in December
2004 from University of Rennes (France), after three years at both France
Telecom R&D and IRISA. During his PhD, he conceived and developed the
Solipsis system, a distributed shared virtual world.
Then, he had worked as a researcher at Orange Labs for almost two years.
Since September 2006, he is Associate Professor at Telecom Bretagne, a
graduate engineering school within the Institut Telecom.
His main research interests are related with large-scale distributed and
networking systems.