More Web Proxy on the site http://driver.im/

article

A recursive random search algorithm for network parameter optimization

Authors:

Shivkumar KalyanaramanAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 32, Issue 3

Pages 44 - 53

https://doi.org/10.1145/1052305.1052306

Published: 01 December 2004 Publication History

Abstract

This paper proposes a new heuristic search algorithm, Recursive Random Search(RRS), for black-box optimization problems. Specifically, this algorithm is designed for the dynamical parameter optimization of network protocols which emphasizes on obtaining good solutions within a limited time frame rather than full optimization. The RRS algorithm is based on the initial high-efficiency property of random sampling and attempts to maintain this high-efficiency by constantly "restarting" random sampling with adjusted sample spaces. Due to its basis on random sampling, the RRS algorithm is robust to the effect of random noises in the objective function and it performs especially efficiently when handling the objective functions with negligible parameters. These properties have been demonstrated with the tests on a suite of benchmark functions. The RRS algorithm has been successfully applied to the optimal configuration of several network protocols. One application to a network routing algorithm is presented.

References

[1]

D. H. Ackley. A Connectionist Machine for Genetic Hillclimbing. Boston: Kluwer Academic Publishers, 1987.

Digital Library

[2]

M. Ali, C. Storey, and A. Törn. Application of stochastic global optimization algorithms to practical problems. Journal of Optimization Theory and Applications, 95(3):545--563, 1997.

Digital Library

[3]

L. Armijo. Minimization of functions having lipschitz continuous first partial derivatives. Pacific Journal of Mathematics, 16:1--3, 1966.

[4]

J. Beveridge, C. Graves, and C. E. Lesher. Local search as a tool for horizon line matching. Technical Report CS-96-109, Colorado State University, 1996.

[5]

S. Bhattacharyya, C. Diot, J. Jetcheva, and N. Taft. Pop-level and access-link-level traffic dynamics in a tier-1 pop. In ACM SIGCOMM Internet Measurement Workshop, November 2001.

Digital Library

[6]

P. Brachetti, M. D. F. Ciccoli, G. D. Pillo, and S. Lucidi. A new version of the price's algorithm for global optimization. Journal of Global Optimization, 10:165--184, 1997.

Digital Library

[7]

W. C. Davidon. Variable metric method for minimization. SIAM Journal on Optimization, 1:1--17, 1991. The article was originally published as Argonne National Laboratory Research and Development Report May 1959(revised November 1959).

[8]

W. Fang and L. Peterson. Inter-as traffic patterns and their implications. In Proceedings of Global Internet 99, Rio, Brazil, 1999.

[9]

B. Fortz and M. Thorup. Internet traffic engineering by optimizing ospf weights. In Proceedings of the INFOCOM 2000, pages 519--528, 2000.

[10]

T. Y. H. T. Kaur and S. Kalyanaraman. Minimizing packet loss by optimizing ospf weights using online simulation. In Proceedings of IEEE MASCOTS 2003, Orlando, FL, Oct. 2003.

[11]

R. Hooke and T. Jeeves. Direct search solution of numerical and statistical problems. Journal of the ACM, 8(2):212--229, April 1961.

Digital Library

[12]

D. S. Johnson and L. A. McGeoch. The travelling salesman problem: a case study in local optimization. In E. H. L. Aarts and J. K. Lenstra, editors, Local Search in Combinatorial Optimization. Wiley and Sons, 1997.

[13]

A. Juels and M. Wattenberg. Stochastic hillclimbing as a baseline method for evaluating generic algorithms. In D. S. Touretzky, M. C. Mozer, and M. E. Hasselmo, editors, Advances in Neural Information Processing Systems, volume 8, pages 430--436. 1996.

[14]

A. H. Kan and G. T. Timmer. Stochastic global optimization methods part I: Clustering methods. Mathematical Programming, 39:27--56, 1987.

Digital Library

[15]

S. Kirkpatrick, D. Gelatt, and M. Vechhi. Optimization by simulated annealing. Science, 220:671--680, 1983.

[16]

R. MEAD and J. A. NELDER. A simplex method for function minimization. Computer Journal, 7(4):308--313, 1965.

[17]

M. Mitchell. An Introduction to Genetic Algorithms. The MIT Press, 1996.

Digital Library

[18]

W. L. Price. Global optimization by controlled random search. Journal of Optimization Theory and Applications, 40:333--348, 1978.

[19]

S. Rana, L. D. Whitley, and R. Cogswell. Searching in the presence of noise. In H. Voigt, W. Ebeling, I. Rechenberg, and H.-P. Schwefel, editors, Parallel Problem Solving from Nature - PPSN IV (Berlin, 1996) (Lecture Notes in Computer Science 1141), pages 198--207, Berlin, 1996. Springer.

Digital Library

[20]

L. A. Rastrigin. Systems of Extremal Control. Nauka, 1974.

[21]

A. Törn and A. Žilinskas. Global Optimization, volume, 350 of Lecture Notes in Computer Science. Springer-Verlag, 1989.

[22]

M. W. Trosset. On the use of direct search methods for stochastic optimization. Technical report, Department of Computational and Applied Mathematics, Rice University, 2000.

[23]

M. A. Wolfe. Numerical Methods for Unconstrained Optimization. Van Nostrand Reinhold Company, New York, 1978.

[24]

T. Ye and et al. Traffic management and network control using collaborative on-line simulation. In Proc. of IEEE ICC'01, Helsinki, Finland, 2001.

[25]

T. Ye and S. Kalyanaraman. A recursive random search algorithm for large-scale network parameter configuration. In Proceedings of ACM SIGMETRICS 2003, San Diego, CA, June 2003.

Digital Library

[26]

Z. B. Zabinsky. Stochastic methods for practical global optimization. Journal of Global Optimization, 13:433--444, 1998.

Digital Library

Cited By

Yoo M(2023)Development of a Simulator for Household Refrigerator Using Equation-Based Optimization Control with Bayesian CalibrationMachines10.3390/machines1201001212:1(12)Online publication date: 23-Dec-2023
https://doi.org/10.3390/machines12010012
Li MLiu ZShi XJin H(2020)ATCS: Auto-Tuning Configurations of Big Data Frameworks Based on Generative Adversarial NetsIEEE Access10.1109/ACCESS.2020.29798128(50485-50496)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2979812
Arslan EYuksel MGunes M(2015)Training network administrators in a game-like environmentJournal of Network and Computer Applications10.1016/j.jnca.2015.03.00553:C(14-23)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1016/j.jnca.2015.03.005
Show More Cited By

Recommendations

A recursive random search algorithm for large-scale network parameter configuration
SIGMETRICS '03: Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

Parameter configuration is a common procedure used in large-scale network protocols to support multiple operational goals. It can be formulated as a black-box optimization problem and solved with an efficient search algorithm. This paper proposes a new ...
A recursive random search algorithm for large-scale network parameter configuration

Parameter configuration is a common procedure used in large-scale network protocols to support multiple operational goals. It can be formulated as a black-box optimization problem and solved with an efficient search algorithm. This paper proposes a new ...
A discrete gravitational search algorithm for solving combinatorial optimization problems

Metaheuristics are general search strategies that, at the exploitation stage, intensively exploit areas of the solution space with high quality solutions and, at the exploration stage, move to unexplored areas of the solution space when necessary. The ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 32, Issue 3

December 2004

51 pages

ISSN:0163-5999

DOI:10.1145/1052305

Issue’s Table of Contents

Copyright © 2004 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2004

Published in SIGMETRICS Volume 32, Issue 3

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
337
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yoo M(2023)Development of a Simulator for Household Refrigerator Using Equation-Based Optimization Control with Bayesian CalibrationMachines10.3390/machines1201001212:1(12)Online publication date: 23-Dec-2023
https://doi.org/10.3390/machines12010012
Li MLiu ZShi XJin H(2020)ATCS: Auto-Tuning Configurations of Big Data Frameworks Based on Generative Adversarial NetsIEEE Access10.1109/ACCESS.2020.29798128(50485-50496)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2979812
Arslan EYuksel MGunes M(2015)Training network administrators in a game-like environmentJournal of Network and Computer Applications10.1016/j.jnca.2015.03.00553:C(14-23)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1016/j.jnca.2015.03.005
Gonen BGunduz GYuksel M(2015)Automated network management and configuration using Probabilistic Trans-Algorithmic SearchComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2014.11.01376:C(275-293)Online publication date: 15-Jan-2015
https://dl.acm.org/doi/10.1016/j.comnet.2014.11.013
Kusetogullari HLeeson MKole BHines E(2014)Meta-heuristic algorithms for optimized network flow wavelet-based image codingApplied Soft Computing10.1016/j.asoc.2013.09.00114(536-553)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1016/j.asoc.2013.09.001
Poland MNugent CWang HChen L(2012)Genetic algorithm and pure random search for exosensor distribution optimisationInternational Journal of Bio-Inspired Computation10.1504/IJBIC.2012.0514084:6(359-372)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.1504/IJBIC.2012.051408
Poland MNugent CWang HChen L(2011)Pure random search for ambient sensor distribution optimisation in a smart home environmentTechnology and Health Care10.5555/2019478.201948019:3(137-160)Online publication date: 1-Aug-2011
https://dl.acm.org/doi/10.5555/2019478.2019480
Arslan EYuksel MGunes M(2011)Network management game2011 18th IEEE Workshop on Local & Metropolitan Area Networks (LANMAN)10.1109/LANMAN.2011.6076939(1-6)Online publication date: Oct-2011
https://doi.org/10.1109/LANMAN.2011.6076939
Gonen BYuksel M(2011)Network Configuration and Management via Two-Phase Online Optimization2011 IEEE Global Telecommunications Conference - GLOBECOM 201110.1109/GLOCOM.2011.6133523(1-6)Online publication date: Dec-2011
https://doi.org/10.1109/GLOCOM.2011.6133523
Paule IGirard PTod M(2011)Empirical Bayes estimation of random effects of a mixed-effects proportional odds Markov model for ordinal dataComputer Methods and Programs in Biomedicine10.1016/j.cmpb.2011.04.006104:3(505-513)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1016/j.cmpb.2011.04.006
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents