skip to main content
article

Large-scale network parameter configuration using an on-line simulation framework

Published: 01 August 2008 Publication History

Abstract

As the Internet infrastructure grows to support a variety of services, its legacy protocols are being overloaded with new functions such as traffic engineering. Today, operators engineer such capabilities through clever, but manual parameter tuning. In this paper, we propose a back-end support tool for large-scale parameter configuration that is based on efficient parameter state space search techniques and on-line simulation. The framework is useful when the network protocol performance is sensitive to its parameter settings, and its performance can be reasonably modeled in simulation. In particular, our system imports the network topology, relevant protocol models and latest monitored traffic patterns into a simulation that runs on-line in a network operations center (NOC). Each simulation evaluates the network performance for a particular setting of protocol parameters. We propose an efficient large-dimensional parameter state space search technique called "recursive random search (RRS)." Each sample point chosen by RRS results in a single simulation. An important feature of this framework is its flexibility: it allows arbitrary choices in terms of the simulation engines used (e.g., ns-2, SSFnet), network protocols to be simulated (e.g., OSPF, BGP), and in the specification of the optimization objectives. We demonstrate the flexibility and relevance of this framework in three scenarios: joint tuning of the RED buffer management parameters at multiple bottlenecks, traffic engineering using OSPF link weight tuning, and outbound load-balancing of traffic at peering/transit points using BGP LOCAL_PREF parameter.

References

[1]
R. Mahajan, D. Wetherall, and T. Anderson, "Understanding BGP misconfiguration," in Proc. ACM SIGCOMM, 2002, pp. 3-16.
[2]
D. Katz, "Why are we scared of SPF? IGP scaling and stability," in NANOG 25, Toronto, Canada, Jun. 2002 {Online}. Available: http:// www.nanog.org/mtg-0206/katz.html
[3]
N. Feamster, J. Rexford, and J. Borkenhagen, "Controlling the impact of BGP policy changes on IP traffic," in NANOG 25, Toronto, Canada, Jun. 2002 {Online}. Available: http://www.nanog.org/mtg-0206/feamster.html
[4]
C. Carothers, D. Bauer, and S. Pearce, "Ross: A high-performance, low memory, modular time warp system," in Proc. Workshop on Parallel and Distributed Simulation, May 2000, pp. 53-60.
[5]
H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, and Willinger, "Network topology generators: Degree-based vs. structural," in Proc. ACM SIGCOMM, 2002, pp. 147-159.
[6]
N. Spring, R. Mahajan, and D. Wetherall, "Measuring ISP topologies with Rocketfuel," in Proc. ACM SIGCOMM, 2002, pp. 133-145.
[7]
W. Leland, M. Taqqu, W. Willinger, and D. Wilson, "On the self-similar nature of Ethernet traffic (extended version)," IEEE/ACM Trans. Networking, vol. 2, no. 1, pp. 1-15, Feb. 1994.
[8]
A. Feldmann, A. Greenberg, C. Lund, N. Reingold, J. Rexford, and F. True, "Deriving traffic demands for operational IP networks: Methodology and experience," IEEE/ACMTrans. Networking, vol. 9, no. 3, pp. 265-278, Jun. 2001.
[9]
D. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, MA: Addison Wesley, 1989.
[10]
F. Glover, "Tabu search-part I," ORSA J. Computing, vol. 1, no. 3, pp. 190-206, 1989.
[11]
E. Aarts and J. Korst, Simulated Annealing and Boltzmann Machines . New York: Wiley, 1989.
[12]
T. Ye and S. Kalyanaraman, "A recursive random search algorithm for large-scale network parameter configuration," in Proc. ACM SIGMETRICS 2003, San Diego, CA, Jun. 2003, pp. 196-205.
[13]
NS Network Simulator. {Online}. Available: http://www.isi.edu/ nsnam/ns/
[14]
SSFNET Network Simulator. {Online}. Available: http://www. ssfnet.org
[15]
A. Törn and A. Žilinskas, Global Optimization. New York: Springer-Verlag, 1989, vol. LNCS 350.
[16]
D. H. Wolpert and W. G. Macready, "No Free Lunch theorems for optimization," IEEE Trans. Evolutionary Computing, vol. 1, no. 1, pp. 67-82, Apr. 1997.
[17]
T. C. Hu, V. Klee, and D. Larman, "Optimization of globally convex functions," SIAM J. Control and Optimization, vol. 27, no. 5, pp. 1026-1047, 1989.
[18]
K. D. Boese, A. B. Kahng, and S. Muddu, "A new adaptive multistart technique for combinatorial global optimizations," Oper. Res. Lett., vol. 16, pp. 101-113, 1994.
[19]
J. A. Boyan and A. W. Moore, "Learning evaluation functions to improve optimization by local search," J. Machine Learning Res., vol. 1, no. 2000, pp. 77-112, 2000.
[20]
R. H. Leary, "Global optimization on funneling landscapes," J. Global Optimization, vol. 18, no. 4, pp. 367-383, Dec. 2000.
[21]
Z. B. Zabinsky, "Stochastic methods for practical global optimization," J. Global Optimization, vol. 13, pp. 433-444, 1998.
[22]
M. Mitchell, An Introduction to Genetic Algorithms. Cambridge, MA: The MIT Press, 1996.
[23]
S. Kirkpatrick, D. Gelatt, and M. Vechhi, "Optimization by simulated annealing," Science, vol. 220, pp. 671-680, 1983.
[24]
W. L. Price, "Global optimization by controlled random search," J. Optimization Theory and Applications, vol. 40, pp. 333-348, 1978.
[25]
S. Rana, L. D. Whitley, and R. Cogswell, "Searching in the presence of noise," in Parallel Problem Solving from Nature--PPSN IV. Berlin: Springer, 1996, vol. LNCS 1141, pp. 198-207.
[26]
S. Floyd and V. Jacobson, "Random early detection gateways for congestion avoidance," IEEE/ACM Trans. Networking, vol. 1, no. 4, pp. 397-413, Aug. 1993.
[27]
W.-C. Feng, D. D. Kandlur,D. Saha, and K. G. Shi, "A self-configuring RED gateway," in Proc. IEEE INFOCOM, 1999, vol. 3, pp. 1320-1328.
[28]
M. Christiansen, K. Jeffay, D. Ott, and F. D. Smith, "Tuning RED for web traffic," in Proc. ACM SIGCOMM, 2000, pp. 139-150.
[29]
T. Bonald, M. May, and J.-C. Bolot, "Analytic evaluation of RED performance," in Proc. IEEE INFOCOM, 2000, pp. 1415-1444.
[30]
C. Hollot, V. Misra, D. Towsley, and W.-B. Gong, "A control theoretic analysis of RED," in Proc. IEEE INFOCOM, 2001, vol. 3, pp. 1510-1519.
[31]
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, Nov. 2001, pp. 39-53.
[32]
W. Fang and L. Peterson, "Inter-AS traffic patterns and their implications," in Proc. Globecom'99, Rio de Janeiro, Brazil, 1999, vol. 3, pp. 1859-1868.
[33]
A. Khanna and J. Zinky, "The revised ARPANET routing metric," in Proc. ACM SIGCOMM, 1989, pp. 45-56.
[34]
D. W. Glazer and C. Tropper, "A new metric for dynamic routing algorithms," IEEE Trans. Commun., vol. 38, no. 3, pp. 360-367, Mar. 1990.
[35]
Z. Wang and J. Crowcroft, "Analysis of shortest-path routing algorithms in a dynamic network environment," ACM Comput. Commun. Rev., vol. 22, no. 2, pp. 63-71, 1992.
[36]
B. Fortz and M. Thorup, "Internet traffic engineering by optimizing OSPF weights," in Proc. IEEE INFOCOM, 2000, pp. 519-528.
[37]
A. Feldmann, A. Greenberg, C. Lund, N. Reingold, and J. Rexford, "NetScope: traffic engineering for IP networks," IEEE Network, vol. 14, no. 2, pp. 11-19, Mar./Apr. 2000.
[38]
R. Nagarajan, J. F. Kurose, and D. Towsley, "Approximation techniques for computing packet loss in finite-buffered voice multiplexers," IEEE J. Select. Areas Commun., vol. 9, no. 4, pp. 368-337, Apr. 1991.
[39]
H. G. Perros, Queueing Networks With Blocking, Exact and Approximate Solutions. Oxford, U.K.: Oxford Univ. Press, 1994.
[40]
B. Fortz and M. Thorup, "Increasing Internet capacity using local search," Computation Optimization and Applications, vol. 29, no. 1, pp. 13-48, 2004.
[41]
G. Huston, "Commentary on inter-domain routing in the Internet," RFC 3221, Dec. 2001.
[42]
T. Ye, S. Yadav, M. Doshi, A. Gandhi, S. Kalyanaraman, and H. T. Kaur, "Load balancing in BGP environment using online simulation and dynamic NAT," presented at the ISMA Workshop by CAIDA, San Diego, CA, Dec. 2001.
[43]
J. Stewart, III, BGP-4 Inter-Domain Routing in the Internet. Reading, MA: Addison-Wesley, 1999.
[44]
L. A. Hall, Approximation Algorithms for NP-Hard Problems . Boston, MA: PWS Publishing, 1995, ch. Approximation Algorithms for Scheduling.
[45]
C. N. Potts, "Analysis of a linear programming heuristic for scheduling unrelated parallel machines," Discrete Appl. Math., vol. 10, pp. 155-164, 1985.

Cited By

View all
  • (2018)UAV-DirectProceedings of the 4th ACM Workshop on Micro Aerial Vehicle Networks, Systems, and Applications10.1145/3213526.3213537(57-62)Online publication date: 10-Jun-2018
  • (2017)A high-performance Two-Phase Multipath scheme for data-center networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2016.09.025112:C(36-51)Online publication date: 15-Jan-2017
  • (2017)Dynamic data driven transportation systemsMultimedia Tools and Applications10.1007/s11042-016-4318-x76:23(25253-25269)Online publication date: 1-Dec-2017
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 16, Issue 4
August 2008
249 pages

Publisher

IEEE Press

Publication History

Published: 01 August 2008
Revised: 02 June 2008
Received: 04 January 2004
Published in TON Volume 16, Issue 4

Author Tags

  1. black-box optimization
  2. network performance management
  3. network protocol configuration
  4. on-line simulation

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)1
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2018)UAV-DirectProceedings of the 4th ACM Workshop on Micro Aerial Vehicle Networks, Systems, and Applications10.1145/3213526.3213537(57-62)Online publication date: 10-Jun-2018
  • (2017)A high-performance Two-Phase Multipath scheme for data-center networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2016.09.025112:C(36-51)Online publication date: 15-Jan-2017
  • (2017)Dynamic data driven transportation systemsMultimedia Tools and Applications10.1007/s11042-016-4318-x76:23(25253-25269)Online publication date: 1-Dec-2017
  • (2016)Optimal multi-element VLC bulb design with power and lighting quality constraintsProceedings of the 3rd Workshop on Visible Light Communication Systems10.1145/2981548.2981553(7-12)Online publication date: 3-Oct-2016
  • (2016)Research Challenges in Parallel and Distributed SimulationACM Transactions on Modeling and Computer Simulation10.1145/286657726:4(1-29)Online publication date: 2-May-2016
  • (2015)Parallel and distributed simulationProceedings of the 2015 Winter Simulation Conference10.5555/2888619.2888624(45-59)Online publication date: 6-Dec-2015
  • (2015)Toward Scalable Emulation of Future Internet Applications with Simulation SymbiosisProceedings of the 19th International Symposium on Distributed Simulation and Real Time Applications10.1109/DS-RT.2015.19(68-77)Online publication date: 14-Oct-2015
  • (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
  • (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
  • (2014)Past and future treesProceedings of the 2014 Winter Simulation Conference10.5555/2693848.2694214(2884-2895)Online publication date: 7-Dec-2014
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media