Tools for Large-Scale Network Testbed Experimentation

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.

Book chapters

1. C. J. Colbourn and V. R. Syrotiuk, “There Must be 50 Ways to Miss a Cover,” 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,” In Finite Fields and their Applications, J. A. Davis, ed., De Gruyter Proceedings in Mathematics, 2020, pages 189-198. Chapter DOI: 10.1515/9783110621730-013
3. C. J. Colbourn and V. R. Syrotiuk, “Detecting Arrays for Effects of Single Factors,” European Congress of Mathematics, EMS Press, 2023, pages 693-718. DOI 10.4171/8ECM/19
4. V. R. Syrotiuk, C. J. Colbourn, E. De Poorter, M. Tetemke Mehari, and I. Moerman, “An Efficient Screening Method for Identifying Parameters and Interactions that Impact Wireless Network Performance,” New Advances in Designs, Codes and Cryptography, C. J. Colbourn, J. H. Dinitz (eds.), Fields Institute Communications 86, 2024, pages 409-425.

Journal papers

1. 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).
2. M. Wagner, C. J. Colbourn, and D. E. Simos, “In-Parameter-Order Strategies for Covering Perfect Hash Families,” Applied Mathematics and Computation 421 (2022), Article 126952. DOI: https://doi.org/10.1016/j.amc.2022.126952
3. Y. Akhtar, F. Zhang, C. J. Colbourn, J. Stufken, and V. R. Syrotiuk, “Scalable Level-wise Screening Experiments using Locating Arrays,” Journal of Quality Technology, July 2023. DOI: 10.1080/00224065.2023.2220973
4. R. E. Dougherty, K. Kleine, M. Wagner, C. J. Colbourn, and D. E. Simos, “Algorithmic Methods for Covering Arrays of Higher Index,” Journal of Combinatorial Optimization 45:28, 2023. DOI: https://doi.org/10.1007/s10878-022-00947-x
5. C. J. Colbourn, “Covering Perfect Hash Families and Covering Arrays of Higher Index,” International Journal of Group Theory, Volume 13, Issue 3, September 2024, pages 293-305. doi 10.22108/ijgt.2023.137230.1836
6. C. J. Colbourn and V. R. Syrotiuk, “Detecting Arrays for Effects of Multiple Interacting Factors,” Information and Computation, Volume 301, Part B, December 2024, 105202. doi https://doi.org/10.1016/j.ic.2024.105202

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
4. E. Lanus. and C. J. Colbourn, “Algorithms for Constructing Anonymizing Arrays.” L. Gąsieniec, R. Klasing, T. Radzik (eds) Combinatorial Algorithms. IWOCA 2020. Lecture Notes in Computer Science, vol 12126. Springer. https://doi-org.ezproxy1.lib.asu.edu/10.1007/978-3-030-48966-3_29
5. Y. Akhtar, C. J. Colbourn, and V. R. Syrotiuk, “Mixed Covering, Locating, and Detecting Arrays via Cyclotomy,” Springer Proceedings in Mathematics & Statistics, Combinatorics, Graph Theory, and Computing, Volume 448, Issue 2194-1009, pages 37-50, 2024. doi https://doi.org/10.1007/978-3-031-52969-6_4

Contributed, invited and keynote presentations

1. 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, Annual INFORMS Conference, November 4, 2018.
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, “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.
4. 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.
5. 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.
6. C. J. Colbourn, “Covering Perfect Hash Families with Index Greater Than One,” Invited Talk, Canadian Mathematical Society, 75th+1 Anniversary Summer Meeting, Ottawa, Canada, June 7-11, 2021.
7. C. J. Colbourn, “Testing Arrays for Fault Localization,” Invited Talk, 8th European Congress of Mathematics, Portorož, Slovenia, June 20-26, 2021.
8. C. J. Colbourn, “Fault Localization via Combinatorial Testing,” Invited Talk, 6th Congreso Latinoamericano de Matemáticos (CLAM2021), Montevideo, Uruguay. September 13-17, 2021.
9. V. R. Syrotiuk, “Requirements and Challenges in Scalable Wireless Testbed Experimentation” Invited presentation, IEEE Future Networks Testbed Requirements, Challenges and Opportunities, February 7, 2022 (online).
10. V. R. Syrotiuk, “Combinatorial Requirements for Large Scale Experimentation”, Keynote presentation, Combinatorics 2022, May 31, 2022 (online).
11. V. R. Syrotiuk, “Screening using Locating Arrays,” Invited presentation, 5th International Conference on Econometrics and Statistics (EcoSta 2022), Ryukoku University, Kyoto, Japan, June 5, 2022 (online).
12. V. R. Syrotiuk, “Cover-Free Families and Topology-Transparent Scheduling (…contrasting the Combinatorial Requirements with those of Locating Arrays for Screening),” Invited presentation, Conference in Celebration of Prof. Douglas Stinson, Fields Institute, Toronto, Canada, June 17, 2022.
13. C. J. Colbourn, “Covering Perfect Hash Families,” Invited presentation, Combinatorics, Computing, Group Theory and Applications, Boca Raton, Florida, August 2022.
14. V. R. Syrotiuk, “Combinatorial Requirements for Large Scale Experimentation in Computer Networks,” Invited presentation, Networked Systems Tech Talk series, Illinois Tech, April 2023 (online).
15. C. J. Colbourn, “Covering Arrays: Many Hands Make Light Work,” Invited presentation, 10th Slovenian Conference on Graph Theory, Kranjska Gora, Slovenia, June 2023.
16. V. R. Syrotiuk, “Analysis of Screening Results from Locating Arrays,” Invited presentation, 10th Slovenian Conference on Graph Theory, Kranjska Gora, Slovenia, June 2023.
17. V. R. Syrotiuk, “Towards Explainability in Experimentation,” Invited speaker, “Distinguished Speaker Seminar Series,” NSF AI-EDGE Institute at Ohio State University, September 30, 2022 (online).
18. C. J. Colbourn, “Efficient Greedy Algorithms with Accuracy Guarantees for Combinatorial Restrictions,” Plenary Invited Speaker, 55th Southeastern International Conference on Combinatorics, Graph Theory & Computing, March 8, 2024.
19. C. J. Colbourn, “An Accuracy Guarantee for One-Column-at-a-Time Greedy Construction Algorithms,” Contributed Talk, Combinatorics 2024, Carovigno, Italy, June 6, 2024.
20. V. R. Syrotiuk, “Locating Arrays: Construction, Screening, and Screening Effectiveness,” Contributed Talk, Combinatorics 2024, Carovigno, Italy, June 6, 2024.

Theses/dissertations

1. Stephen A. Seidel, “Locating Arrays: Construction, Analysis, and Robustness,” MS Thesis, Arizona State University, Fall 2018.
2. Vincent Miller, “Constructing Locating Arrays with Constraints using Constraint Satisfaction,” Senior Honours Thesis, Arizona State University, Spring 2019.
3. Erin Lanus, “Interaction Testing, Fault Location, and Anonymous Attribute-Based Authorization,” Ph.D. Dissertation, Arizona State University, Spring 2019
4. Daniel Kulenkamp, “Improving on 802.11: Streaming Audio and Quality of Service,” Senior Honours Thesis, YArizona State University, Fall 2019.
5. Daniel J. Kulenkamp, “Extending REACT to Support Quality of Service: Algorithms and Implementation, With Screening and Performance Experiments on a Wireless Testbed,” MS Thesis, Arizona State University, Spring 2021.
6. Michael Poirier-Shelton, “The Effectiveness of Locating Arrays in Model Recovery,” M.S. Thesis, Arizona State University, Fall 2024.”

Websites or other internet sites

1. Tools for Large-Scale Network Testbed Experimentation, R Package. Rajat Aayush Jha incorporated the work of Stephen Seidel, Isaac Jung, Leah Darwin, and Yasmeen Akhtar into the package. It also includes links to data collected from various network testbeds by Brandon Hang, Daniel Kulenkamp, Stephen Seidel, and Michael Poirier-Shelton. https://github.com/RajatAayushJha/LocatingArrayGeneratorAndAnalysis
2. Tools (Construction, Verifier, and Analysis), written in C++ by Stephen Seidel. https://github.com/sseidel16/v4-la-tools
3. Tools (Construction and Verifier), written in C++ by Isaac Jung. https://github.com/gato flaco/Array-Checker
4. Initial R Package, written by Leah Darwin. https://github.com/leahdarwin/LATools

REUs, in alphabetical order

1. Leah Darwin
2. Brandon Hang
3. Isaac Jung
4. Daniel J. Kulenkamp
5. Vincent Miller
6. Stephen A. Seidel
7. Michael Poirier-Shelton

Postdoctoral fellows

1. Yasmeen Akhtar

International collaborations, in alphabetical order

1. Eli De Poorter and Ingrid Moerman, and their team. Department of Information Technology, Internet and Data Science Lab, Ghent University — IMEC, Ghent, Belgium.
2. Professor Jeroen Famaey, and his team. IDLab Research Group University of Anterwep – imec, Antwerp, Belgium.
3. Dr. Dimitris E. Simos, and his team. Applied Discrete Mathematics for Information Security research area at SBA Research, and Associate Professor with Graz University of Technology, Vienna, Austria.
4. Professor Ilenia Tinnerello, and her team, Department of Electrical Engineering, University of Palermo, Palermo, Italy.

National collaborations, in alphabetical order

1. Ryan E. Dougherty, Assistant Professor, Department of Electrical Engineering and Computer Science, United States Military Academy, West Point, NY, USA.
2. Professor John Stufken, and his team. Department of Statistics, George Mason University, Fairfax, VA, USA.

Outcomes

Engineered systems, such as the Internet, shape modern society becoming part of the critical infrastructure of government, businesses, homes, and schools. They have evolved in complexity, with behavior and characteristics that cannot be characterized using traditional techniques for modeling, analysis, and design.

Experimentation is one way to understand complex systems. However, due to the huge set of factors potentially impacting the performance of such systems, screening is required to reduce the set to those that are most significant. Complicating matters is that some systems, such as the Internet, are known to have interactions between factors that are also significant. Traditional tools for screening both factors and their interactions in a huge factor space are infeasible because the screening experiment is too large to run in a reasonable time.

To address this problem, this project introduced a locating array (LA) to capture the minimum requirements for screening factors and interactions targeting huge factor spaces. The number of runs in a locating array grows logarithmically in the number of factors, making them well-suited for efficiently screening complex systems. This allows an order of magnitude more factors to be screened by an LA than by other screening designs and created a pressing need for new tools based on LAs to support large-scale experimentation.

This project has contributed to methodologies for the evaluation of complex engineered systems with a focus on the development of rigorous scientific methods for screening experiments. The methodologies are integrated into a publicly available R package with software tools to construct and verify locating arrays, and analyze data collected from experiments based on them.

The research conducted as part of this project resulted in four chapters in books, six journal papers, six peer reviewed conference papers, twenty invited talks and keynote presentations. It contributed towards NSF and national research priorities, working to educate the next generation of scientists and engineers, including one postdoctoral fellow, one doctoral student, two Masters students, and seven undergraduate students, with both strong mathematical foundations and expertise in network testbeds and experimental work.

Experimentation was conducted on physical testbeds such as the w-iLab.t wireless testbed, the CloudLab cloud testbed, and the state-of-the-art FABRIC testbed. Experimentation was also conducted in simulation with IEEE 802.11ah, or Wi-Fi HaLow, the new Wi-Fi draft aiming to address the major challenges of the Internet of Things (IoT), and with LoRa, which enables large scale deployment of low power wide area networks (LPWANs). Results of classical screening experiments were validated using locating arrays and our novel analysis method.

The ability to screen huge factor spaces effectively and efficiently has broad impact to science and engineering, beyond computer and communication networks. Screening designs are used in testing software, hardware, composite materials, biological networks, among many others. Advances in the construction of locating arrays reaches into all of these areas. An investment in locating arrays is a shift, rather than a step forward, in the field of experimental design and analysis. The analysis of data collected from unbalanced designs such as locating arrays has already reached into the literature on the science of the designed experiments and statistics. The recovery approach based on locating arrays works to address some of the grand challenges for new data-driven mathematical models. Such models will facilitate quantitative evaluation and contribute to our understanding of complex engineered systems.