The Network-Probing Algorithm Simulator (NetPAS) is a testbed for evaluating the performance of network-probing algorithms. NetPAS produces numerous metrics to do this. These are produced by running repeated simulations of the algorithms on various topologies. The metrics capture information about the timing/frequency of probing different network elements (nodes or edges) and the number of probes that impact a network element during each timestep.
To run a simulation, NetPAS needs a topology and some paths to use for probing the network. Only network elements that lie on these paths can be probed. The paths might be specified directly or by choosing a set of "beacons" and then routing between some or all pairs of distinct beacons.
Experimental simulations use discrete timesteps. The load on a network element during a timestep is the number of probes in that timestep that go through that network element. A single simulation is run for a specified number of timesteps and the various metrics for that simulation are recorded and written to disk.
NetPAS is set up to run repeated trial simulations for a given set of inputs.
The metrics computed by NetPAS include the staleness (time since the beginning of the experiment or the most recent probing of an element), load (number of probes impacting a network element), and rate (number of probes per unit time). These can be computed for different network elements. The staleness and load metrics are combined in a variety of ways across time (over the course of an experimental trial) and across network elements. This is done with a variety of operators (e.g., maximum or minimum; mean, median, or other percentile; standard deviation).
NetPAS also computes statistics about each trial such as the number of unprobed network elements, weight statistics, and topology statistics.
NetPAS supports various topologies. These can be read in (as from the Topology Zoo noted below) or generated using various algorithms. NetPAS currently supports the use of Barab'asi--Albert construction (and a fractional version of this), G_{n,m} random graphs, and data-center-network topologies (either DCells [3] or XGFTs [4]).
NetPAS supports the use of probing strategies that are : due to Barford et al. [1]; due to Cohen et al. [2]; based on a set-cover algorithm; and randomized, memoryless.
NetPAS uses (and stores) one master seed per experimental trial. This is used to seed the generation of other seeds for that trial, which are potentially used for the graph topology, the selection of beacons, the choice of probing paths, the weighting, the choice of probing "tests," and the running of the simulation.
NetPAS includes rewritten versions of NetworkX functions that enable these seeds to be used to control random choices, e.g., in generating random graphs or making random choices in path construction.
The directory netpas/experiments/gnm-rng/ contains CSV files with seeds corresponding to connected instances of G_{n,m} graphs. These were generated by netpas/experiments/gnm-seeds.py. The file netpas/experiments/gnm-rng/gnm-seeds-<b>-<n>-<m>.csv contains the first 10,000 seeds that, when given to the jr_gnm_random_graph function from jrnx.py, result in a connected G_{n,m} graph. (The parameter corresponds to a number of probing beacons that might be used, but that is unrelated to connectivity.)
NetPAS allows the use of different weights. These can affect some probing strategies (e.g., the one due to Barford et al.) and the computation of (weighted) statistics.
We will refer to the directory into which this repository is cloned as netpas/, although the code does not assume any particular name.
netpas/catalog/ contains data for some randomly generated network topologies (the "catalog topologies"). These are supported by the code, but that support may be removed in the future (in favor of other mechanisms for reproducibility). Unless catalog toplogies are specified when running experiments, removing netpas/catalog/ should not cause any problems.
netpas/experiments/ contains code to run experiments using the testbed as described below. Running experiments will produce a directory netpas/data/, and various subdirectories, if they do not already exist.
The testbed supports the use of network topologies from The Internet Topology Zoo http://www.topology-zoo.org/index.html . To use these topologies, create a directory netpas/zoo/ and put the .gml and .graphml files from the Zoo into that directory. Unless Zoo toplogies are specified when running experiments, not having the netpas/zoo/ directory should not cause any problems.
The testbed has been developed under Python 2.7.
The packages used are described in the pip requirements file netpas/requirements.txt.
netpas/experiments/ contains scripts exp-<strategy>.py (where <strategy> is one of bdrs, chkmrt, randbasic, and setcover) that run repeated experiments for a single set of parameters. These parameters can be set on the command line and include topology class to use, number of trials, and strategy-specific parameters.
The shell scripts netpas/experiments/run-<strategy>-exp.sh (where <strategy> ranges over strategy names as above) loop through different topology classes and strategy options, running experiments with the named strategy.
This is experimental and under ongoing development. The directory structure, file formats, and other things may change in future releases.
See LICENSE.TXT for licensing information.
Developed by Aaron D. Jaggard (U.S. Naval Research Laboratory; aaron.jaggard@nrl.navy.mil) and Vijay Ramachandran (Colgate University; vramachandran@colgate.edu).
[1] Paul Barford, Nick Duffield, Amos Ron, and Joel Sommers. 2009. Network Performance Anomaly Detection and Localization. In IEEE INFOCOM 2009. 1377--1385. https://doi.org/10.1109/INFCOM.2009.5062053
[2] Edith Cohen, Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Danny Raz, and Yoav Tzur. 2014. Probe scheduling for efficient detection of silent failures. Performance Evaluation 79 (2014), 73--89. https://doi.org/10.1016/j.peva.2014.07.005
[3] Chuanxiong Guo, Haitao Wu, Kun Tan, Lei Shi, Yongguang Zhang, and Songwu Lu. 2008. DCell: A Scalable and Fault-tolerant Network Structure for Data Centers. In ACM SIGCOMM 2008. 75--86. https://doi.org/10.1145/1402958.1402968
[4] Sabine R. "Ohring, Maximilian Ibel, Sajal K. Das, and Mohan J. Kumar. 1995. On Generalized Fat Trees. In IPPS ’95. 37--44. https://doi.org/10.1109/IPPS.1995.395911