Meta-Modelling for Complex Engineered Networks
PIs: Violet R. Syrotiuk and Charles J. Colbourn
NSF NeTS Award Number: 1421058
Overview. The use of complex engineered networks is pervasive in everyday life. A few examples include the internet, the power grid, and transportation networks. Yet our understanding of such networks remains limited. This proposal responds to the NSF NeTS highlighted area of meta-networking research, specifically tackling the development of scientific methods for planning and assessing experiments in order to improve our understanding of wireless networks, a type of complex engineered network.
Some methods for meta-modelling include polynomial regression models, splines, and neural networks. In some form, each effectively applies screening to identify the most important among a set of factors in an experiment and to develop the meta-model, an approximation of the factor (i.e., input variables) to response (i.e., performance measures) transformation. Various assumptions and limitations underlie many of these methods, including that: (1) the factors have only two levels; (2) the factors are not categorical; (3) the set of factors considered for experimentation is ``not too large;'' (4) the direction of response is known for specific factors; and (5) the data are normally distributed.
To address these assumptions and limitations a new approach to screening and meta-modelling is introduced. Locating arrays (LAs) are formulated to focus on identification rather than on measurement. Consequently, they exhibit logarithmic growth in the number of factors. This makes practical the consideration of an order of magnitude more factors in experimentation. As a result, LAs have the potential to transform experimentation in huge factor spaces such as those found in complex engineered networks. LAs also address the other assumptions and limitations, though they do rely on the principle of sparsity of effects. A ``heavy hitters'' approach, similar to that used in compressive sensing, is applied in developing the meta-model. Experimentation with simulation models of wireless networks, as well as physical wireless networks such as the CREW testbed federated with GENI, is planned. Assessing the validity (i.e., accuracy) and robustness (i.e., their sensitivity to the configuration of the factors) of the meta-models developed is essential to understanding their quality and usefulness for optimization, management, and control of the network.
Intellectual Merit. There is a vital need for methodologies for scientific evaluation of complex engineered networks. This proposal advances research in three primary areas: (1) The theory of LAs as a method for objective and efficient planning of experiments. (2) The application of LAs for meta-model development by experimentation in both simulated and physical wireless networks. (3) The assessment of the experiments, i.e., the validation and robustness of the developed meta-models.
Broader Impacts. Complex engineered networks have shaped modern society. These networks have evolved into complex systems with behaviour and characteristics that cannot be characterized using traditional techniques for modelling, analysis, and design. The meta-modelling approach based on LAs works to address some of the grand challenges in wireless networks for new data-driven mathematical models. Such models facilitate quantitative evaluation of new architectures and protocols through the development of scientific methods for planning and assessing experiments in networking. This will contribute to our understanding of complex engineered networks and continue to shape modern society.
- Kaushik Sarkar, ``Covering Arrays: Algorithms and Asymptotics,'' Ph.D. Dissertation, Fall 2016.
- Nathaniel Flick, ``Testbed Implementation of the Meta-MAC Protocol,'' Senior Honours Thesis, Spring 2016.
- Felipe Stall Rechia, ``An Evaluation of SDN Based Network Virtualization Techniques,'' MS Thesis, Spring 2016.
- Abraham N. Aldaco-Gastelum, ``A Framework for Screening Experiments and Modelling in Complex Systems,'' Ph.D. Dissertation, Spring 2015.
- Nicole Ang, ``Generating Mixed-Level Covering Arrays with λ = 2 and Test Prioritization,'' MS Thesis, Spring 2015.
- Rushang Karia, ``Covering Arrays: Generation and Post-Optimization,'' MS Thesis, Spring 2015.
Journal Papers :
- Randy Compton, Michael T. Mehari, Charles J. Colbourn, Eli De Poorter, Ingrid Moerman, and Violet R. Syrotiuk, ``An Efficient Screening Method for Identifying Parameters and Interactions that Impact Wireless Network Performance,'' manuscript submitted for publication. If and when the manuscript is accepted for publication, we will provide all the code, scripts, and tools necessary to run the screening experiment on the w-iLab.t wireless network testbed and analyze the measurements collected, or to analyze our data sets directly on this site, to enable reproducibility of our results.
- Charles J. Colbourn, Daniel Horsley, and Violet R. Syrotiuk, ``A Hierarchical Framework for Recovery in Compressive Sensing,'' to appear in Discrete Applied Mathematics, accepted October, 2017.
- Charles J. Colbourn, Erin Lanus, and Kaushik Sarkar, ``Asymptotic and Constructive Methods for Covering Perfect Hash Families and Covering Arrays,'' to appear in Designs, Codes and Cryptography, accepted May 2017.
- Kaushik Sarkar, Charles J. Colbourn, Annalisa De Bonis, and Ugo Vaccaro, ``Partial Covering Arrays: Algorithms and Asymptotics,'' to appear in Theory of Computing Systems, accepted May 2017.
- Darryn Bryant, Charles J. Colbourn, Daniel Horsley, and Padraig Ò Cathàin, ``Compressed Sensing with Combinatorial Designs: Theory and Simulations,'' IEEE Transactions on Information Theory 63 : 4850-4859, 2017.
- Kaushik Sarkar and Charles J. Colbourn, ``Upper Bounds on the Size of Covering Arrays,'' SIAM Journal on Discrete Mathematics 31 : 1277-1293, 2017.
- Charles J. Colbourn and Bingli Fan, ``Locating One Pairwise Interaction: Three Recursive Constructions,'' Journal of Algebra Combinatorics Discrete Structures and Applications, 3 : 125-134, 2016.
- Charles J. Colbourn, Bingli Fan, and Daniel Horsley, ``Disjoint Spread Systems and Fault Location,'' SIAM Journal on Discrete Mathematics. 30 : 2011-2016, 2016.
Conference Proceedings :
- Ilenia Tinnirello, Domenico Garlisi, Fabrizio Giuliano, Violet R. Syrotiuk, and Giuseppe Bianchi, ``Demo: MAC Learning: Enabling Automatic Combination of Elementary Protocol Components,'' Proceedings of the 10th ACM International Workshop on Wireless Testbeds, Experimenal evaluation and CHaracterization (WINTECH'16), in conjunction with the 22nd ACM International Conference on Mobile Computing and Networking (MobiCom'16), New York, New York, U.S.A., October 3, 2016.
- Kaushik Sarkar, Charles J. Colbourn, Annalisa De Bonis, and Ugo Vaccaro, ``Partial Covering Arrays: Algorithms and Asymptotics,'' Lecture Notes in Computer Science, Volume 9843 for the International Workshop on Combinatorial Algorithms (IWOCA'16), pages 437-448, Helsinki, Finland, August 18, 2016.
- Nathaniel Flick, Domenico Garlisi, Violet R. Syrotiuk, and Ilenia Tinnirello, ``Testbed Implementation of the Meta-MAC Protocol,'' Proceedings of the International Workshop on Computer and Networking Experimental Research Using Testbeds (CNERT'16), in conjunction with IEEE International Conference on Computer Communications (INFOCOM'16), San Francisco, California, U.S.A., April 11, 2016.
- Randy Compton, Michael T. Mehari, Charles J. Colbourn, Eli De Poorter, and Violet R. Syrotiuk, ``Screening Interacting Factors in a Wireless Network Testbed Using Locating Arrays,'' Proceedings of the International Workshop on Computer and Networking Experimental Research Using Testbeds (CNERT'16), in conjunction with IEEE International Conference on Computer Communications (INFOCOM'16), San Francisco, California, U.S.A., April 11, 2016.
- Charles J. Colbourn and Violet R. Syrotiuk, ``Coverage, Location, Detection, and Measurement,'' Proceedings of the 5th International Workshop on Combinatorial Testing (IWCT'16), in conjunction with IEEE International Conference on Software Testing, Verification and Validation (ICST'16), Chicago, Illinois, U.S.A., April 10, 2016.
- Domenico Garlisi, Fabrizio Giuliano, Alice Lo Valvo, Jonathan Lutz, Violet R. Syrotiuk, and Ilenia Tinnirello, ``Making WiFi Work in Multi-Hop Topologies: Automatic Negotiation and Allocation of Airtime,'' Proceedings of the International Workshop on Computer and Networking Experimental Research Using Testbeds (CNERT'15), in conjunction with the IEEE 35th International Conference on Distributed Computing Systems (ICDCS'15), Columbus, Ohio, U.S.A., June 29, 2015.
- Professor Eli De Poorter, Professor Ingrid Moerman and their team, IDLab - Internet Technology and Data Science Lab, Ghent University - IMEC, Ghent, Belgium.
- Professor Ilenia Tinnerello and her team, Department of Electrical Engineering, University of Palermo, Palermo, Italy.
- Professors Bingli Fan and Tao Feng, Department of Mathematics, Beijing Jiaotong University, Beijing, China.
- Professor Daniel Horsley, School of Mathematical Sciences, Monash University, Melbourne, Australia.
Professors Ugo Vaccaro and Annalisa De Bonis,
Department of Computer Science,
University of Salerno,