Distributed Placement of Service Facilities in Large-Scale Networks (bibtex)
by Nikolaos Laoutaris, Georgios Smaragdakis, Konstantinos Oikonomou, Ioannis Stavrakakis, Azer Bestavros
Abstract:
The effectiveness of service provisioning in large-scale networks is highly dependent on the number and location of service facilities deployed at various hosts. The classical, centralized approach to determining the latter would amount to formulating and solving the uncapacitated k-median (UKM) problem (if the requested number of facilities is fixed), or the uncapacitated facility location (UFL) problem (if the number of facilities is also to be optimized). Clearly, such centralized approaches require knowledge of global topological and demand information, and thus do not scale and are not practical for large networks. The key question posed and answered in this paper is the following: ``How can we determine in a distributed and scalable manner the number and location of service facilities?'' We propose an innovative approach in which topology and demand information is limited to neighborhoods, or balls of small radius around selected facilities, whereas demand information is captured implicitly for the remaining (remote) clients outside these neighborhoods, by mapping them to clients on the edge of the neighborhood; the ball radius regulates the trade-off between scalability and performance. We develop a scalable, distributed approach that answers our key question through an iterative re-optimization of the location and the number of facilities within such balls. We show that even for small values of the radius (1 or 2), our distributed approach achieves performance under various synthetic and real Internet topologies that is comparable to that of optimal, centralized approaches requiring full topology and demand information.
Reference:
Nikolaos Laoutaris, Georgios Smaragdakis, Konstantinos Oikonomou, Ioannis Stavrakakis, Azer Bestavros, "Distributed Placement of Service Facilities in Large-Scale Networks", In IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications, pp. 2144-2152, 2007.
Bibtex Entry:
@inproceedings{laoutaris2007distributed,
	Abstract = {The effectiveness of service provisioning in large-scale networks is highly dependent on the number and location of service facilities deployed at various hosts. The classical, centralized approach to determining the latter would amount to formulating and solving the uncapacitated k-median (UKM) problem (if the requested number of facilities is fixed), or the uncapacitated facility location (UFL) problem (if the number of facilities is also to be optimized). Clearly, such centralized approaches require knowledge of global topological and demand information, and thus do not scale and are not practical for large networks. The key question posed and answered in this paper is the following: ``How can we determine in a distributed and scalable manner the number and location of service facilities?'' We propose an innovative approach in which topology and demand information is limited to neighborhoods, or balls of small radius around selected facilities, whereas demand information is captured implicitly for the remaining (remote) clients outside these neighborhoods, by mapping them to clients on the edge of the neighborhood; the ball radius regulates the trade-off between scalability and performance. We develop a scalable, distributed approach that answers our key question through an iterative re-optimization of the location and the number of facilities within such balls. We show that even for small values of the radius (1 or 2), our distributed approach achieves performance under various synthetic and real Internet topologies that is comparable to that of optimal, centralized approaches requiring full topology and demand information.},
	Author = {Laoutaris, Nikolaos and Smaragdakis, Georgios and Oikonomou, Konstantinos and Stavrakakis, Ioannis and Bestavros, Azer},
	Booktitle = {IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications},
	Doi = {10.1109/INFCOM.2007.248},
	Issn = {0743-166X},
	Keywords = {own, boston, exceptional, refereed, ana},
	Month = {May},
	Pages = {2144-2152},
	Title = {{{Distributed Placement of Service Facilities in Large-Scale Networks}}},
	Venue = {Barcelona, Spain},
	Year = {2007},
	Bdsk-Url-1 = {https://doi.org/10.1109/INFCOM.2007.248}}
Powered by bibtexbrowser