skip to main content
10.1145/2901378.2901401acmconferencesArticle/Chapter ViewAbstractPublication PagespadsConference Proceedingsconference-collections
research-article
Public Access

Efficient Monte Carlo Evaluation of SDN Resiliency

Published: 15 May 2016 Publication History

Abstract

Software defined networking (SDN) is an emerging technology for controlling flows through networks. Used in the context of industrial control systems, an objective is to design configurations that have built-in protection for hardware failures in the sense that the configuration has "baked-in" back-up routes. The objective is to leave the configuration static as long as possible, minimizing the need to have the controller push in new routing and filtering rules We have designed and implemented a tool that enables us to determine the complete connectivity map from an analysis of all switch configurations in the network. We can use this tool to explore the impact of a link failure, in particular to determine whether the failure induces loss of the ability to deliver a flow even after the built-in back-up routes are used. A measure of the original configuration's resilience to link failure is the mean number of link failures required to induce the first such loss of service. The computational cost of each link failure and subsequent analysis is large, so there is much to be gained by reducing the overall cost of obtaining a statistically valid estimate of resiliency. This paper shows that when analysis of a network state can identify all as-yet-unfailed links any one of whose failure would induce loss of a flow, then we can use the technique of importance sampling to estimate the mean number of links required to fail before some flow is lost, and analyze the potential for reducing the variance of the sample statistic. We provide both theoretical and empirical evidence for significant variance reduction.

References

[1]
H. Cancela, M. E. Khadiri, G. Rubino, and B. Tuffin. Balanced and approximate zero-variance recursive estimators for the network reliability problem. ACM Trans. Model. Comput. Simul., 25(1):5:1--5:19, Nov. 2014.
[2]
M. Casado, M. J. Freedman, J. Pettit, J. Luo, N. Gude, N. McKeown, and S. Shenker. Rethinking enterprise network control. IEEE/ACM Transactions on Networking (TON), 17(4):1270--1283, 2009.
[3]
O. N. Foundation. Openflow switch specification 1.3. "https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/openflow/openflow-spec-v1.3.0.pdf".
[4]
P. W. Glynn and D. L. Iglehart. Importance sampling for stochastic simulations. Manage. Sci., 35(11):1367--1392, Nov. 1989.
[5]
P. Heidelberger. Fast simulation of rare events in queueing and reliability models. ACM Trans. Model. Comput. Simul., 5(1):43--85, Jan. 1995.
[6]
D. Jin and D. M. Nicol. Parallel simulation of software defined networks. In Proceedings of the 2013 ACM SIGSIM conference on Principles of advanced discrete simulation, pages 91--102. ACM, 2013.
[7]
H. Kahn and A. W. Marshall. Methods of reducing sample size in monte carlo computations. Journal Operations Research, pages 263--278, 1953.
[8]
P. Kazemian, M. Chan, H. Zeng, G. Varghese, N. McKeown, and S. Whyte. Real time network policy checking using header space analysis. In NSDI, pages 99--111, 2013.
[9]
P. Kazemian, G. Varghese, and N. McKeown. Header space analysis: Static checking for networks. In NSDI, pages 113--126, 2012.
[10]
A. Khurshid, W. Zhou, M. Caesar, and P. Godfrey. Veriflow: verifying network-wide invariants in real time. ACM SIGCOMM Computer Communication Review, 42(4):467--472, 2012.
[11]
K. Kirkpatrick. Software-defined networking. Commun. ACM, 56(9):16--19, Sept. 2013.
[12]
B. Lantz, B. Heller, and N. McKeown. A network in a laptop: rapid prototyping for software-defined networks. In Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks, page 19. ACM, 2010.
[13]
P. J. Smith, M. Shafi, and H. Gao. Quick simulation: a review of importance sampling techniques in communications systems. IEEE Journal on Selected Areas in Communications, 15(4):597--613, May 1997.

Cited By

View all
  • (2020)Estimating Loss Due to Cyber-Attack in the Presence of Uncertainty2020 IEEE 19th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)10.1109/TrustCom50675.2020.00057(361-369)Online publication date: Dec-2020

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SIGSIM-PADS '16: Proceedings of the 2016 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation
May 2016
272 pages
ISBN:9781450337427
DOI:10.1145/2901378
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 May 2016

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. fast fail-over
  2. importance sampling
  3. monte carlo
  4. reliability
  5. software defined networking

Qualifiers

  • Research-article

Funding Sources

Conference

SIGSIM-PADS '16
Sponsor:

Acceptance Rates

Overall Acceptance Rate 398 of 779 submissions, 51%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

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

Other Metrics

Citations

Cited By

View all
  • (2020)Estimating Loss Due to Cyber-Attack in the Presence of Uncertainty2020 IEEE 19th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)10.1109/TrustCom50675.2020.00057(361-369)Online publication date: Dec-2020

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media