Description¶

Goals:

1. find a suitable algorithm to compute betweenness centrality in networks of size that can range up thousands of nodes.
2. implement it in the openwrt toolchain

Motivations:
Centrality can be used to fine-tune some network parameters in routing protocols. Read this paper to have the big picture: main.pdf

Theory:

1. fastest exact algorithm for betwenness computation is in (Brandes 2001)
2. heuristics improve it but with no exact estimation on complexity (Puzis, 2012) (you should be able to download this pdf if you are in the university, else ask me)
3. approximated algorithms exist (Brandes 2007) with recent improvements (Riondato, 2015)

Setting:

• We consider relatively small network graphs (generally <1000 nodes) but very time-variable (small variations often happen, rare large topology reconfigurations).
• We must run the algorithm on constrained devices (wifi-routers)

Steps:

1. read the papers, excluding for the moment (Riondato, 2015)
2. download and compile the openWRT sdk
3. add an empty package to openwrt, check what is the overhead (in terms of occupied space and dependencies) if the package is written in:
   • python (with networkx/igraph or any other graph library)
   • c++ (with STL and boost::graph libraries)
   • C language (fallback choice)
4. implement exact computation, test the results on synthetic graphs, compare the results with the results easily obtained with python+networkx libraries.
5. check its performance on embedded systems
   • if performance is ok (with "ok" to be defined), work on a variation of the heuristic that will update the centrality instead of re-computing at each network change
   • else, consider approximate algorithms
6. (optional, if we have time) run the software in an emulated network, parsing the topology directly from the interface given by the OLSRd routing daemon

Resources:¶

1. dataSets