skip to main content
10.1145/2535771.2535799acmconferencesArticle/Chapter ViewAbstractPublication PagescommConference Proceedingsconference-collections
research-article

Answering why-not queries in software-defined networks with negative provenance

Published: 21 November 2013 Publication History

Abstract

When debugging an SDN, it is sometimes necessary to explain the absence of an event: why a certain rule was not installed, or why a certain packet did not arrive. Existing SDN debuggers offer some support for explaining the presence of events, usually by providing the equivalent of a "backtrace" in conventional debuggers, but they are not very good at answering "Why not?" questions: there is simply no starting point for a possible backtrace.
In this paper, we show that the concept of negative provenance can be used to explain the absence of events in SDNs. Negative provenance relies on counterfactual reasoning to identify the conditions under which the missing event could have occurred. We outline a simple technique that can track negative provenance in SDNs, and we present a case study to illustrate how our technique can be used to answer concrete "Why not?" questions. Using our approach, it should be possible to build SDN debuggers that can explain both the presence and the absence of events.

References

[1]
P. Buneman, S. Khanna, and W. C. Tan. Why and where: A characterization of data provenance. In Proceedings of the 8th International Conference on Database Theory (ICDT), Jan. 2001.
[2]
M. Canini, D. Venzano, P. Perešíni, D. Kostić, and J. Rexford. A NICE way to test OpenFlow applications. In Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation (NSDI), Apr. 2012.
[3]
A. Chapman and H. V. Jagadish. Why not? In Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2009.
[4]
A. Feldmann, O. Maennel, Z. M. Mao, A. Berger, and B. Maggs. Locating Internet routing instabilities. In Proceedings of the ACM SIGCOMM Conference, Aug. 2004.
[5]
N. Foster, R. Harrison, M. J. Freedman, C. Monsanto, J. Rexford, A. Story, and D. Walker. Frenetic: A network programming language. In Proceedings of the 16th ACM SIGPLAN international conference on Functional programming (ICFP), Sept. 2011.
[6]
T. J. Green, G. Karvounarakis, N. E. Taylor, O. Biton, Z. G. Ives, and V. Tannen. ORCHESTRA: Facilitating collaborative data sharing. In Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2007.
[7]
N. Handigol, B. Heller, V. Jeyakumar, D. Mazières, and N. McKeown. Where is the debugger for my software-defined network? In Proceedings of the 1st Workshop on Hot Topics in Software Defined Networking (HotSDN), Aug. 2012.
[8]
J. Huang, T. Chen, A. Doan, and J. F. Naughton. On the provenance of non-answers to queries over extracted data. Proceedings of the VLDB Endowment, 1(1): 736--747, Aug. 2008.
[9]
R. Ikeda, H. Park, and J. Widom. Provenance for generalized map and reduce workflows. In Proceedings of the 5th Biennial Conference on Innovative Data Systems Research (CIDR), Jan. 2011.
[10]
E. Katz-Bassett, H. V. Madhyastha, J. P. John, A. Krishnamurthy, D. Wetherall, and T. Anderson. Studying black holes in the Internet with Hubble. In Proceedings of the 5th USENIX Conference on Networked Systems Design and Implementation (NSDI), Apr. 2008.
[11]
P. Kazemian, G. Varghese, and N. McKeown. Header space analysis: Static checking for networks. In Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation (NSDI), Apr. 2012.
[12]
B. T. Loo, T. Condie, M. Garofalakis, D. E. Gay, J. M. Hellerstein, P. Maniatis, R. Ramakrishnan, T. Roscoe, and I. Stoica. Declarative networking. Communications of the ACM, 52(11): 87--95, Nov. 2009.
[13]
H. Mai, A. Khurshid, R. Agarwal, M. Caesar, P. B. Godfrey, and S. T. King. Debugging the data plane with Anteater. In Proceedings of the ACM SIGCOMM Conference, Aug. 2011.
[14]
A. Meliou and D. Suciu. Tiresias: The database oracle for how-to queries. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (SIGMOD), May 2012.
[15]
C. Ré, N. Dalvi, and D. Suciu. Efficient top-k query evaluation on probabilistic data. In Proceedings of the 23rd International Conference on Data Engineering (ICDE), Apr. 2007.
[16]
Q. T. Tran and C.-Y. Chan. How to ConQueR why-not questions. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2010.
[17]
M. Welsh. What I wish systems researchers would work on. Blog post, http://matt-welsh.blogspot.com/2013/05/what-i-wish-systems-researchers-would.html, May 2013.
[18]
J. Widom. Trio: A system for integrated management of data, accuracy, and lineage. In Proceedings of the 2nd Biennial Conference on Innovative Data Systems Research (CIDR), Jan. 2005.
[19]
H. Zeng, P. Kazemian, G. Varghese, and N. McKeown. Automatic test packet generation. In Proceedings of the 8th International Conference on Emerging Networking Experiments and Technologies (CoNEXT), Dec. 2012.
[20]
W. Zhou, Q. Fei, A. Narayan, A. Haeberlen, B. T. Loo, and M. Sherr. Secure network provenance. In Proceedings of the 23rd ACM Symposium on Operating Systems Principles (SOSP), Oct. 2011.
[21]
W. Zhou, M. Sherr, T. Tao, X. Li, B. T. Loo, and Y. Mao. Efficient querying and maintenance of network provenance at Internet-scale. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2010.

Cited By

View all
  • (2020)Packet Reachability Verification in OpenFlow NetworksProceedings of the 2020 9th International Conference on Software and Computer Applications10.1145/3384544.3384573(227-231)Online publication date: 18-Feb-2020
  • (2020)Provenance for Intent-Based Networking2020 6th IEEE Conference on Network Softwarization (NetSoft)10.1109/NetSoft48620.2020.9165519(195-199)Online publication date: Jun-2020
  • (2019)Co-evolving tracing and fault injection with box of painProceedings of the 11th USENIX Conference on Hot Topics in Cloud Computing10.5555/3357034.3357061(22-22)Online publication date: 8-Jul-2019
  • Show More Cited By

Index Terms

  1. Answering why-not queries in software-defined networks with negative provenance

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    HotNets-XII: Proceedings of the Twelfth ACM Workshop on Hot Topics in Networks
    November 2013
    188 pages
    ISBN:9781450325967
    DOI:10.1145/2535771
    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 the author(s) 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: 21 November 2013

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. debugging
    2. negative provenance
    3. software-defined networks

    Qualifiers

    • Research-article

    Funding Sources

    Conference

    HotNets-XII
    Sponsor:
    HotNets-XII: Twelfth ACM Workshop on Hot Topics in Networks
    November 21 - 22, 2013
    Maryland, College Park

    Acceptance Rates

    HotNets-XII Paper Acceptance Rate 26 of 110 submissions, 24%;
    Overall Acceptance Rate 110 of 460 submissions, 24%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

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

    Other Metrics

    Citations

    Cited By

    View all
    • (2020)Packet Reachability Verification in OpenFlow NetworksProceedings of the 2020 9th International Conference on Software and Computer Applications10.1145/3384544.3384573(227-231)Online publication date: 18-Feb-2020
    • (2020)Provenance for Intent-Based Networking2020 6th IEEE Conference on Network Softwarization (NetSoft)10.1109/NetSoft48620.2020.9165519(195-199)Online publication date: Jun-2020
    • (2019)Co-evolving tracing and fault injection with box of painProceedings of the 11th USENIX Conference on Hot Topics in Cloud Computing10.5555/3357034.3357061(22-22)Online publication date: 8-Jul-2019
    • (2019)Fault Management in Software-Defined Networking: A SurveyIEEE Communications Surveys & Tutorials10.1109/COMST.2018.286892221:1(349-392)Online publication date: Sep-2020
    • (2019)DAPV: Diagnosing Anomalies in MANETs Routing With Provenance and VerificationIEEE Access10.1109/ACCESS.2019.29031507(35302-35316)Online publication date: 2019
    • (2019)SRDPVWireless Networks10.1007/s11276-017-1625-825:4(1731-1747)Online publication date: 1-May-2019
    • (2018)DlogThe Journal of Supercomputing10.1007/s11227-017-2165-974:2(845-867)Online publication date: 1-Feb-2018
    • (2017)Correct by construction networks using stepwise refinementProceedings of the 14th USENIX Conference on Networked Systems Design and Implementation10.5555/3154630.3154686(683-698)Online publication date: 27-Mar-2017
    • (2016)Automating Failure Testing Research at Internet ScaleProceedings of the Seventh ACM Symposium on Cloud Computing10.1145/2987550.2987555(17-28)Online publication date: 5-Oct-2016
    • (2016)CoSEL: Control-plane Only Scalable Efficient and Lightweight SDN Debugger2016 Twenty Second National Conference on Communication (NCC)10.1109/NCC.2016.7561171(1-6)Online publication date: Mar-2016
    • Show More Cited By

    View Options

    Login options

    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