Evolutionary Local Search for Designing Peer-to-Peer Overlay Topologies based on Minimum Routing Cost Spanning Trees
In: Thomas Philip Runarsson and Hans-Georg Beyer and Edmund Burke and Juan J. Merelo-Guerv{\'o}s and L. Darrell Whitley and Xin Yao ed., Proceedings of the 9th International Conference on Parallel Problem Solving from Nature - PPSN IX. LNCS, Volume 4193, Springer, P. 272--281, 2006
Authors
Abstract
Finding overlay topologies for peer-to-peer networks on top of the Internet can be regarded as a network design problem, in which a graph with minimum communication costs is desired. An example of such a graph is a spanning tree connecting all nodes in the overlay. We present evolutionary algorithms incorporating local search for the minimum routing cost spanning tree problem in which the overall routing/communication cost is minimized. We present three types of local search for this problem as well as an evolutionary framework for finding (near)optimal solutions to the problem. Moreover, we present results from a fitness landscape analysis for the three types of local optima that reveal interesting properties of the problem data based on real measurements in the Internet. We demonstrate that our proposed algorithms find near optimum solutions reliably by comparing against a lower bound of the problem.
Full Text
BibTeX
@Proceedings{ Merz2006MRCST,
title = { Evolutionary Local Search for Designing Peer-to-Peer Overlay Topologies based on Minimum Routing Cost Spanning Trees },
author = { Peter Merz and Steffen Wolf },
editor = { Thomas Philip Runarsson and Hans-Georg Beyer and Edmund Burke and Juan J. Merelo-Guerv{\'o}s and L. Darrell Whitley and Xin Yao },
booktitle = { Proceedings of the 9th International Conference on Parallel Problem Solving from Nature - PPSN IX },
series = { LNCS },
volume = { 4193 },
publisher = { Springer },
pages = { 272--281 },
year = 2006,
}
This publication belongs to the project
DeNDeMA.
