Characterizing topological bottlenecks for data delivery in CTP using simulation-based stress testing with natural selection

    Research output: Contribution to journalArticleAcademicpeer-review

    3 Citations (Scopus)
    20 Downloads (Pure)

    Abstract

    Routing protocols for ad-hoc networks, e.g., the Collection Tree Protocol (CTP), are designed with simple node-local behaviour, but are deployed on testbeds with uncontrollable physical topology; exhaustively verifying the protocol on all possible topologies at design time is not tractable. We obtain topological insights on CTP performance, to answer the question: Which topological patterns cause CTP data routing to fail? We stress-test CTP with a quantitative testing method which searches for topologies using evolutionary algorithms combined with protocol simulation. The method iteratively generates new test topologies, such that the execution of the protocol over these topologies shows increasingly worse data-delivery ratios (DDR). We obtain a large set of example topologies of different network sizes up to 50 nodes, network densities, data rates, table sizes, and radio-frequency noise models, which, although connected, trigger a data delivery of nearly zero. We summarize these topologies into three types of topological problems, the root cause of which is the presence of certain asymmetric links and cycles, combined with a certain size of the routing table. We verify causality, i.e., show that randomly generated topologies having these particular features do cause low DDR in CTP. This testing methodology, while computationally intensive, is sound, fully automated and has better coverage over the corner cases of protocol behaviour than testing a protocol over manually crafted or random topologies.
    Original languageEnglish
    Pages (from-to)22-45
    Number of pages24
    JournalAd hoc networks
    Volume30
    DOIs
    Publication statusPublished - Jul 2015

    Fingerprint

    Topology
    Network protocols
    Testing
    Ad hoc networks
    Testbeds
    Routing protocols
    Evolutionary algorithms
    Acoustic waves

    Keywords

    • EWI-26422
    • IR-98389
    • METIS-315009

    Cite this

    @article{9a6a170a56f64d298624c3d0dcf4d5de,
    title = "Characterizing topological bottlenecks for data delivery in CTP using simulation-based stress testing with natural selection",
    abstract = "Routing protocols for ad-hoc networks, e.g., the Collection Tree Protocol (CTP), are designed with simple node-local behaviour, but are deployed on testbeds with uncontrollable physical topology; exhaustively verifying the protocol on all possible topologies at design time is not tractable. We obtain topological insights on CTP performance, to answer the question: Which topological patterns cause CTP data routing to fail? We stress-test CTP with a quantitative testing method which searches for topologies using evolutionary algorithms combined with protocol simulation. The method iteratively generates new test topologies, such that the execution of the protocol over these topologies shows increasingly worse data-delivery ratios (DDR). We obtain a large set of example topologies of different network sizes up to 50 nodes, network densities, data rates, table sizes, and radio-frequency noise models, which, although connected, trigger a data delivery of nearly zero. We summarize these topologies into three types of topological problems, the root cause of which is the presence of certain asymmetric links and cycles, combined with a certain size of the routing table. We verify causality, i.e., show that randomly generated topologies having these particular features do cause low DDR in CTP. This testing methodology, while computationally intensive, is sound, fully automated and has better coverage over the corner cases of protocol behaviour than testing a protocol over manually crafted or random topologies.",
    keywords = "EWI-26422, IR-98389, METIS-315009",
    author = "Doina Bucur and Giovanni Iacca and {de Boer}, Pieter-Tjerk",
    note = "eemcs-eprint-26422",
    year = "2015",
    month = "7",
    doi = "10.1016/j.adhoc.2015.02.005",
    language = "English",
    volume = "30",
    pages = "22--45",
    journal = "Ad hoc networks",
    issn = "1570-8705",
    publisher = "Elsevier",

    }

    Characterizing topological bottlenecks for data delivery in CTP using simulation-based stress testing with natural selection. / Bucur, Doina ; Iacca, Giovanni; de Boer, Pieter-Tjerk .

    In: Ad hoc networks, Vol. 30, 07.2015, p. 22-45.

    Research output: Contribution to journalArticleAcademicpeer-review

    TY - JOUR

    T1 - Characterizing topological bottlenecks for data delivery in CTP using simulation-based stress testing with natural selection

    AU - Bucur, Doina

    AU - Iacca, Giovanni

    AU - de Boer, Pieter-Tjerk

    N1 - eemcs-eprint-26422

    PY - 2015/7

    Y1 - 2015/7

    N2 - Routing protocols for ad-hoc networks, e.g., the Collection Tree Protocol (CTP), are designed with simple node-local behaviour, but are deployed on testbeds with uncontrollable physical topology; exhaustively verifying the protocol on all possible topologies at design time is not tractable. We obtain topological insights on CTP performance, to answer the question: Which topological patterns cause CTP data routing to fail? We stress-test CTP with a quantitative testing method which searches for topologies using evolutionary algorithms combined with protocol simulation. The method iteratively generates new test topologies, such that the execution of the protocol over these topologies shows increasingly worse data-delivery ratios (DDR). We obtain a large set of example topologies of different network sizes up to 50 nodes, network densities, data rates, table sizes, and radio-frequency noise models, which, although connected, trigger a data delivery of nearly zero. We summarize these topologies into three types of topological problems, the root cause of which is the presence of certain asymmetric links and cycles, combined with a certain size of the routing table. We verify causality, i.e., show that randomly generated topologies having these particular features do cause low DDR in CTP. This testing methodology, while computationally intensive, is sound, fully automated and has better coverage over the corner cases of protocol behaviour than testing a protocol over manually crafted or random topologies.

    AB - Routing protocols for ad-hoc networks, e.g., the Collection Tree Protocol (CTP), are designed with simple node-local behaviour, but are deployed on testbeds with uncontrollable physical topology; exhaustively verifying the protocol on all possible topologies at design time is not tractable. We obtain topological insights on CTP performance, to answer the question: Which topological patterns cause CTP data routing to fail? We stress-test CTP with a quantitative testing method which searches for topologies using evolutionary algorithms combined with protocol simulation. The method iteratively generates new test topologies, such that the execution of the protocol over these topologies shows increasingly worse data-delivery ratios (DDR). We obtain a large set of example topologies of different network sizes up to 50 nodes, network densities, data rates, table sizes, and radio-frequency noise models, which, although connected, trigger a data delivery of nearly zero. We summarize these topologies into three types of topological problems, the root cause of which is the presence of certain asymmetric links and cycles, combined with a certain size of the routing table. We verify causality, i.e., show that randomly generated topologies having these particular features do cause low DDR in CTP. This testing methodology, while computationally intensive, is sound, fully automated and has better coverage over the corner cases of protocol behaviour than testing a protocol over manually crafted or random topologies.

    KW - EWI-26422

    KW - IR-98389

    KW - METIS-315009

    U2 - 10.1016/j.adhoc.2015.02.005

    DO - 10.1016/j.adhoc.2015.02.005

    M3 - Article

    VL - 30

    SP - 22

    EP - 45

    JO - Ad hoc networks

    JF - Ad hoc networks

    SN - 1570-8705

    ER -