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)
    53 Downloads (Pure)


    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
    Publication statusPublished - Jul 2015


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


    Dive into the research topics of 'Characterizing topological bottlenecks for data delivery in CTP using simulation-based stress testing with natural selection'. Together they form a unique fingerprint.

    Cite this