Description¶
Goals:- find a suitable algorithm to compute betweenness centrality in networks of size that can range up thousands of nodes.
- 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
- fastest exact algorithm for betwenness computation is in (Brandes 2001)
- 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)
- approximated algorithms exist (Brandes 2007) with recent improvements (Riondato, 2015)
- 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)
- read the papers, excluding for the moment (Riondato, 2015)
- download and compile the openWRT sdk
- 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)
- implement exact computation, test the results on synthetic graphs, compare the results with the results easily obtained with python+networkx libraries.
- 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
- (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