sgsim: A Simple Skip Graph Simulator and Visualizer

Overview

sgsim is a simple skip graph simulator and visualizer.

sgsim can:

• construct a skip graph overlay network based on a random membership vector,
• perform some simple experiments,
• render routing paths over a skip graph topology, and
• compute some statistics and output graphs.

sgsim is written in Python and uses pandas for statistics.

sgsim is developed by Kota Abe at Osaka City University, Japan [Link]

License

MIT License

Installation

Tested with Python3.9.

Install dependencies:

% pip install -r requirements.txt

Usage

% python sg_main.py -h
usage: sg_main.py [-h] [-n N] [-a ALPHA] [--exp {basic,unicast,unicast_vary_n}]
                  [--unicast-algorithm {greedy,original}] [--fast-join] [--seed SEED] [--interactive]
                  [--output-topology-max-level OUTPUT_TOPOLOGY_MAX_LEVEL] [--output-hop-graph] [--diagonal]
                  [-v]

sgsim: Skip Graph Simulator and Visualizer

optional arguments:
  -h, --help            show this help message and exit
  -n N                  number of nodes (default: 8)
  -a ALPHA, --alpha ALPHA
                        base of membership vector (default: 2)
  --exp {basic,unicast,unicast_vary_n}
                        experiment type
  --unicast-algorithm {greedy,original}
                        unicast algorithm
  --fast-join           use fast (cheat) join
  --seed SEED           give a random seed
  --interactive         display graphs on a window rather than save to files
  --output-topology-max-level OUTPUT_TOPOLOGY_MAX_LEVEL
                        render a topology from level 0 to the specified level (use with --exp basic)
  --output-hop-graph    render a hop graph (use with --exp unicast)
  --diagonal            draw diagonal line (use with --output-hop-graph)
  -v, --verbose         verbose output

Currently, a real (event-based) node insertion algorithm is not implemented.
You have to give --fast-join option to instruct statistically constructing a skip graph.

Basic options:

• --exp basic Do statistics about routing tables.
• --exp basic --output-topology-max-level=3 Output a topology graph from level 0 to 3 (sg_topology.png).
• --exp unicast Do simple unicast experiments. Output histograms of the number of hops (sg_hops_hist.png) and of messages (sg_msgs_hist.png).
• --exp unicast --output-hop-graph Output hop graphs (unicast-(algorithm)-#.png).
• --exp unicast_vary_n Compute an average number of hops, varying number of nodes. Output a graph (sg_hops_vs_n.png).
• --unicast-algorithm greedy Use a greedy algorithm for unicast
• --unicast-algorithm original Use an algorithm based on the article "Skip Graphs" for unicast

Examples

• python sg_main.py --fast-join --exp unicast --output-hop-graph -n 15 --unicast-algorithm original