Tools for Large-Scale Network Testbed Experimentation

PIs: Violet R. Syrotiuk and Charles J. Colbourn

NSF NeTS Award Number: 1813729

Project Summary:

Overview. Network testbeds are complex engineered systems. In addition to the parameters of the network stack, there are parameters of the operating system, the hardware, and the operating environment that may impact the network performance. Most protocols of a TCP/IP stack have at least 5-10 configurable parameters making 25-50 parameters to vary in experimentation without considering wider system aspects!

A crucial question is: What parameters should be selected for experimentation? Screening experiments are designed to answer this question and are an important first step. Their goal is to identify the significant parameters impacting performance. However, networks are known to have cross-layer interactions, and these may involve parameters different from the main effects. Traditional tools for screening both main effects and two-way interactions in a large parameter space are infeasible.

The minimum requirements for screening in this setting are captured in a locating array (LA). LAs exhibit logarithmic growth in the number of parameters, making practical the consideration of an order of magnitude more parameters in experimentation. Hence there is a pressing need for tools based on LAs to support large-scale network testbed experimentation.

An LA and the analysis to recover the significant parameters and two-way interactions impacting the measured performance are tightly coupled. This proposal investigates the trade-off in the LA structure and recovery. While the basic requirements of screening are known, the basic requirements of recovery are not well understood. If balance is required, then the Rao bound applies, and the array must grow polynomially in the number of parameters and two-way interactions. Approaches include either making the recovery algorithm work with the lack of balance in the LA, or making the LA be more suitable for recovery. Practical networking applications motivate new structure on the LA that in turn impacts recovery. Quantifiying the uncertainty in the recovery is planned. The goals of this project are to produce tools (1) to generate and validate screening designs for large-scale testbed experimentation, and (2) for their subsequent analysis.

Intellectual Merit. Experimentation is a cornerstone of scientific advancement. This project contributes to the NSF core area seeking fundamental scientific understanding of, and advances in, large-scale complex communication networks. It advances research in two primary areas: (1) Understanding the requirements for recovery, and the trade-offs in array structure and recovery, helps to build a bridge between novel LAs and traditional screening designs. (2) The effective use of screening designs requires the deployment of tools to support them. Novel open source tools to construct, verify, and analyze LAs will be developed, made available in a community wide repository and be equipped with documentation and training materials.

Broader Impacts. Wireless networked systems have enabled improved productivity in almost every sector of the national economy. Over the last decade, the use of wireless Internet-connected devices has nearly doubled in the U.S.\ with users fueling new socially useful applications. While expected to behave predictably under a wide set of circumstances, these engineered networks have behaviour and characteristics that cannot be characterized using traditional techniques. Experimentation is one way to improve our understanding, starting with the question of which parameters should be selected. Tools for screening and analysis based on LAs work to address some of the grand challenges in wireless networks for new data-driven mathematical models. Thee will contribute to our understanding of complex engineered networks and continue to shape modern society.

Publications:

Book Chapters:

1. C. J. Colbourn and V. R. Syrotiuk, ``There Must be 50 Ways to Miss a Cover,'' to appear as Chapter 18, 50 Years of Combinatorics, Graph Theory, and Computing, F. Chung, R. Graham, R. Hoffman, L. Hogben, R. Mullin, and D. West (eds.), Chapman and Hall/CRC, 2019, Chapter 18, pages 319-334.
2. C. J. Colbourn and V. R. Syrotiuk, ``Covering Strong Separating Hash Families,'' J. A. Davis, ed., De Gruyter Proceedings in Mathematics, 2020, pages 189-198.

Journal Papers:

1. Y. Akhtar, F. Zhang, C. J. Colbourn, J. Stufken, and V. R. Syrotiuk, ``Scalable Level-wise Screening Experiments using Locating Arrays,'' to appear in Journal of Quality Technology, (accepted May 2023). (The data that supports the findings of this study (.zip file).) (Updated analysis tool using R^2 used in this study (.tar.gz file).)
2. C. J. Colbourn and V. R. Syrotiuk, ``Detecting Arrays for Effects of Single Factors,'' under review.
3. Y. Chang, C. J. Colbourn, A. Gowty, D. Horsley, and J. Zhou, ``New Bounds on the Maximum Size of Sperner Partition Systems,'' European Journal of Combinatorics 90 (2020), 103165 (18pp).
4. C. J. Colbourn and V. R. Syrotiuk, ``On a Combinatorial Framework for Fault Characterization,'' Mathematics in Computer Science 12(4), 429-451, December 2018. doi http://link.springer.com/article/10.1007/s11786-018-0385-x

Juried Conference Proceedings:

1. C. J. Colbourn and V. R. Syrotiuk, ``Detecting Arrays for Main Effects,'' Proceedings of the 8th International Conference on Algebraic Informatics (CAI), LNCS 11545, M. Ciric, M. Droste, and J.-E. Pin (eds.), 112-123, 2019. doi https://doi.org/10.1007/978-3-030-21363-3_10
2. S. A. Seidel, C. J. Colbourn, and V. R. Syrotiuk, ``Robustness of Recovery in Locating Array-based Screening Experiments,'' Proceedings of the SCS Spring Simulation Conference (SpringSim), Tucson, Arizona, U.S.A., April 29-May 2, 2019. doi https://doi.org/10.23919/SpringSim.2019.8732911
3. E. Lanus, C. J. Colbourn, and D. C. Montgomery, ``Partitioned Search with Column Resampling for Locating Array Construction,'' Proceedings of the 2019 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), Xi'an, China, April 22-27, 2019. doi https://doi.org/10.1109/ICSTW.2019.00056

Other Conference Presentations/Papers:

Conference presentations:

1. Y. Akhtar, ``Constructing High Index Covering Arrays and Their Application to Design of Experiments,'' The 7th Biennial Canadian Discrete and Algorithmic Mathematics Conference (CanaDAM), Vancouver, B.C., Canada, May 28-31, 2019.
2. Y. Akhtar, ``A Finite Field Construction of Covering Arrays,'' Proceedings of the 14th International Conference on Finite Fields and their Applications (FQ14), Vancouver, B.C., Canada, June 3-7, 2019.

Other Products:

1. V. R. Syrotiuk, ``Realizing Airtime Allocations in Multi-Hop Wi-Fi Networks: A Stability and Convergence Study with Testbed Evaluation,'' Seminar IDLab, Department of Elektronics-ICT, University of Antwerp - imec, Antwerp, Belgium, April 26, 2019.
2. V. R. Syrotiuk, ``Design and Analysis of Experiments,'' Keynote Address, Chameleon User Meeting, Austin, Texas, U.S.A., February 6, 2019.
3. V. R. Syrotiuk, ``Locating Arrays: A New Experimental Design for Complex Engineered Systems,” Invited Presentation, Cybersecurity Analytics and Applications session of the Military Applications Society track at the Annual INFORMS Conference, November 4, 2018.

Theses/Dissertations:

1. Erin Lanus, ``Interaction Testing, Fault Location, and Anonymous Attribute-Based Authorization,'' Ph.D. Dissertation, Arizona State University, Spring 2019
2. Stephen A. Seidel, ``Locating Arrays: Construction, Analysis, and Robustness,'' MS Thesis, Arizona State University, Fall 2018.
3. Vincent Miller, ``Constructing Locating Arrays with Constraints using Constraint Satisfaction,'' Senior Honours Thesis, Arizona State University, Spring 2019.

Collaborations, in alphabetical order:

1. Professor Jeroen Famaey and his team, IDLab Research Group University of Anterwep - imec, Antwerp, Belgium.
2. Professor John Stufken, and his team, Department of Mathematics and Statistics University of North Carolina, Greensboro Greensboro, NC 27402-6170 U.S.A.
3. Professor Ilenia Tinnerello and her team, Department of Electrical Engineering, University of Palermo, Palermo, Italy.