overlay-tools

Data organization

Under the data directory, there is a separate directory for each overlay topology. In the examples below, we will assume data is in the data_geni subdirectory.

The required input data is:

overlay_pos.txt: This is a list of the geographic coordinates (latitude and longitude) of each overlay node in the topology. The expected input format is <node_id> <latitude> <longitude> (e.g. 1 34.048810 -118.259457 # CENIC)
overlay_lat.txt: This is a list of pairwise latencies for every pair of overlay nodes. For GENI, this can be generated using the geni-tools ping_all.sh and format_pingout.py tools. The expected format is <src_id> <dst_id> <rtt_in_ms>, where src_id and dst_id are overlay node IDs (corresponding to nodes in overlay_pos.txt).
overlay_topo.txt: This is the list of edges that make up the overlay topology, along with their roundtrip latencies (i.e. it is a subset of overlay_lat.txt). The expected format is the same as overlay_lat.txt.

Overlay topologies may be hand constructed. If you would like to automatically generate a topology from a complete set of pairwise latencies, you can use:

python topology_generation/spanner_fault.py -e data/data_geni/overlay_lat.txt -p data/data_geni/overlay_pos.txt -n 3

copy list of edges into data/data_geni/overlay_topo.txt

We typically use the same sets of clients when evaluating different overlays, so client data is located in data/client_data. We typically use the input file data/client_data/clients_contig.csv, which includes all cities in the contiguous US with populations of at least 100,000. Note that we exclude cities from this list in Hawaii and Alaska to focus on the contiguous US.

To get updated client data in the needed format, you can copy and paste the table from the Wikipedia page into an Excel spreadsheet, then export as a csv clients_raw.csv. Then, you can reformat with:

python client_calculation/format_input.py -i data/client_data/clients_new_raw.csv > data/client_data/clients_new.csv

Note that this unfortunately depends on the Wikipedia page not changing its format, but the it should be fairly easy to modify the format_input.py script to match an updated format if needed. The current version works as of May 10, 2023.

In addition to the overlay_pos.txt, overlay_lat.txt and overlay_topo.txt files, each data subdirectory also includes a file cluster_assignments.txt that lists the edges connecting each client to the overlay. This is generated as described under "Generating Clusters" below.

Generating Clusters

To get list of clusters from pairwise overlay latencies

python client_calculation/gen_clusters.py -i data/data_geni/overlay_lat.txt -o data/data_geni/overlay_pos.txt -cf data/client_data/clients_contig.csv -c 3 --print-clusters

To get list of client-to-cluster assignments:

python client_calculation/gen_clusters.py -i data/data_geni/overlay_lat.txt -o data/data_geni/overlay_pos.txt -cf data/client_data/clients_contig.csv -c 3 --print-assignments > data/data_geni/cluster_assignments.txt