A recursive random search algorithm for large-scale network parameter configuration

ABSTRACT

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 heuristic search algorithm, Recursive Random Search(RRS), for large-scale network parameter optimization. The RRS algorithm is based on the initial high-efficiency feature of random sampling and it attempts to maintain this high efficiency by constantly "restarting" random sampling with adjusted sample spaces. Besides the high efficiency, the RRS algorithm is robust to the effect of random noise and trivial parameters in the objective function because of its root in random sampling. These features are very important for the efficient optimization of network protocol configuration. The performance of RRS is demonstrated with the tests on a suite of benchmark functions. The algorithm has been applied to the configuration of several network protocols, such as RED, OSPF and BGP. One example application in OSPF routing algorithm is presented.

REFERENCES

• 1: Ratul Mahajan , David Wetherall , Tom Anderson, Understanding BGP misconfiguration, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 2: Tao Ye and et al. Traffic management and network control using collaborative on-line simulation. In Proc. of IEEE ICC'01, pages 204--209, Helsinki, Finland, June 2001.
• 3: W. L. Price. Global optimization by controlled random search. Journal of Optimization Theory and Applications, 40:333--348, 1978.
• 4: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 5: S. Kirkpatrick, D.C. Gelatt, and M.P. Vechhi. Optimization by simulated annealing. Science, 220:671--680, 1983.
• 6: D. h. Wolpert and W. G. Macready. No free lunch theorems for optimization. IEEE Transaction on Evolutionary Computing, 1:67--82, 1997.
• 7: Aimo Törn and Antanas Zilinskas. Global Optimization, volume 350 of Lecture Notes in Computer Science. Springer-Verlag, 1989.
• 8: T. C. Hu , V. Klee , D. Larman, Optimization of globally convex functions, SIAM Journal on Control and Optimization, v.27 n.5, p.1026-1047, Sept. 1989 [doi>10.1137/0327055]
• 9: K. D. Boese, A. B. Kahng, and S. Muddu. On the big valley and adaptive multi-start for discrete global optimizations. Technical Report TR-930015, UCLA CS Department, 1993.
• 10: K. D. Boese, A. B. Kahng, and S. Muddu. a new adaptive multi-start technique for combinatorial global optimizations. Operation Research Letters, 16:101--113, 1994.
• 11: Justin Boyan , Andrew W. Moore, Learning evaluation functions to improve optimization by local search, The Journal of Machine Learning Research, 1, p.77-112, 9/1/2001
• 12: Robert H. Leary, Global Optimization on Funneling Landscapes, Journal of Global Optimization, v.18 n.4, p.367-383, December 2000 [doi>10.1023/A:1026500301312]
• 13: P. Brachetti , M. De Felice Ciccoli , G. Di Pillo , S. Lucidi, A New Version of the Price‘s Algorithm for Global Optimization, Journal of Global Optimization, v.10 n.2, p.165-184, March 1997 [doi>10.1023/A:1008250020656]
• 14: Zelda B. Zabinsky, Stochastic Methods for Practical Global Optimization, Journal of Global Optimization, v.13 n.4, p.433-444, December 1998 [doi>10.1023/A:1008350230239]
• 15: Melanie Mitchell, An introduction to genetic algorithms, MIT Press, Cambridge, MA, 1996
• 16: V. P. Plagianakos and M. N. Vrahatis. A derivative-free minimization method for noisy functions. In P.M. Pardalos A. Migdalas and R. Burkard, editors, Advances in Combinatorial and Global Optimization, pages 283--296. 2001.
• 17: L. Armijo. Minimization of functions having lipschitz continuous first partial derivatives. Pacific Journal of Mathematics, 16:1--3, 1966.
• 18: Robert Hooke , T. A. Jeeves, `` Direct Search'' Solution of Numerical and Statistical Problems, Journal of the ACM (JACM), v.8 n.2, p.212-229, April 1961 [doi>10.1145/321062.321069]
• 19: Soraya B. Rana , L. Darrell Whitley , Ronald Cogswell, Searching in the Presence of Noise, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.198-207, September 22-26, 1996
• 20: A. H. G Rinnooy Kan , G. T. Timmer, Stochastic global optimization methods. part 1: clustering methods, Mathematical Programming: Series A and B, v.39 n.1, p.27-56, September 1, 1987 [doi>10.1007/BF02592070]
• 21: 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).
• 22: R. MEAD and J. A. NELDER. A simplex method for function minimization. Computer Journal, 7(4):308--313, 1965.
• 23: H. Mühlenbein M. Schomisch and J. Born. The parallel genetic algorithm as function optimizer. In Richard K. Belew and Lashon B. Booker, editors, Proceedings of the Fourth Intl. Conf. on Genetic Algorithms, pages 271--278. Morgan-Kaufman, 1991.
• 24: M. M. Ali , C. Storey , A. Törn, Application of stochastic global optimization algorithms to practical problems, Journal of Optimization Theory and Applications, v.95 n.3, p.545-563, Dec. 1997 [doi>10.1023/A:1022617804737]
• 25: 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.
• 26: D. S. Johnson and L. A. McGeoch. The travelling salesman problem: a case study in local optimizaiton. In E. H. L. Aarts and J. K. Lenstra, editors, Local Search in Combinatorial Optimization. Wiley and Sons, 1997.
• 27: 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.
• 28: Michael W. Trosset. On the use of direct search methods for stochastic optimization. Technical report, Department of Computational and Applied Mathematics, Rice University, 2000.
• 29: Tao Ye and Shivkumar Kalyanaraman. A recursive random search for optimizing network protocol parameters. Technical report, ECSE Department, Rensslaer Polytechnique Institute, Dec 2002.
• 30: Tao Ye, Hema T. Kaur, and Shivkumar Kalyanaraman. Automatic network performance management with on-line simulation. Technical report, ECSE Department, Rensslaer Polytechnique Institute, 2002.
• 31: Bernard Fortz and Mikkel Thorup. Internet traffic engineering by optimizing ospf weights. In Proceedings of the INFOCOM 2000, pages 519--528, 2000.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Stochastic programming; Unconstrained optimization

General Terms:
Algorithms, Management, Performance

Keywords:
black-box optimization, global optimization, network management, random sampling