advancednetworkingsystems/prince

Implementing PopRouting

prince's Issues

Compiling against LEDE v17.01 fails

Here is the output from the relevant error compiling against the EdgeRouter X

make[4]: Entering directory '/root/openwrt/build_dir/target-mipsel_24kc_musl-1.1.16/prince-v0.2'
mkdir -p prince/build/
make -C graph-parser_c/src/
make[5]: Entering directory '/root/openwrt/build_dir/target-mipsel_24kc_musl-1.1.16/prince-v0.2/graph-parser_c/src'
mkdir -p ../build/lib/
mipsel-openwrt-linux-musl-gcc -fPIC -pthread  -shared -Wl,-soname,libgraphcparser.so -o ../build/lib/libgraphcparser.so graph_parser.o brandes.o biconnected.o graph/graph.o graph/list.o  
make[5]: Leaving directory '/root/openwrt/build_dir/target-mipsel_24kc_musl-1.1.16/prince-v0.2/graph-parser_c/src'
make -C prince/src
make[5]: Entering directory '/root/openwrt/build_dir/target-mipsel_24kc_musl-1.1.16/prince-v0.2/prince/src'
cp common_c.h common.h
mipsel-openwrt-linux-musl-gcc -std=gnu11 -fPIC -D_GNU_SOURCE -o ../build/prince_c prince.o lib/ini.o parser.o -L../../graph-parser_c/build/lib -lgraphcparser -ldl -ljson-c -lm
../../graph-parser_c/build/lib/libgraphcparser.so: undefined reference to `round_decimal'
collect2: error: ld returned 1 exit status
Makefile:16: recipe for target 'prince_c' failed
make[5]: *** [prince_c] Error 1
make[5]: Leaving directory '/root/openwrt/build_dir/target-mipsel_24kc_musl-1.1.16/prince-v0.2/prince/src'
Makefile:2: recipe for target 'all' failed
make[4]: *** [all] Error 2
make[4]: Leaving directory '/root/openwrt/build_dir/target-mipsel_24kc_musl-1.1.16/prince-v0.2'
Makefile:46: recipe for target '/root/openwrt/build_dir/target-mipsel_24kc_musl-1.1.16/prince-v0.2/.built' failed
make[3]: *** [/root/openwrt/build_dir/target-mipsel_24kc_musl-1.1.16/prince-v0.2/.built] Error 2
make[3]: Leaving directory '/root/openwrt/feeds/routing/poprouting'
package/Makefile:105: recipe for target 'package/feeds/routing/poprouting/compile' failed
make[2]: *** [package/feeds/routing/poprouting/compile] Error 2
make[2]: Leaving directory '/root/openwrt'
package/Makefile:101: recipe for target '/root/openwrt/staging_dir/target-mipsel_24kc_musl-1.1.16/stamp/.package_compile' failed
make[1]: *** [/root/openwrt/staging_dir/target-mipsel_24kc_musl-1.1.16/stamp/.package_compile] Error 2
make[1]: Leaving directory '/root/openwrt'
/root/openwrt/include/toplevel.mk:197: recipe for target 'world' failed
make: *** [world] Error 2

I'm attaching the config file to reproduce this build

config

Parse Json files in prince

A Json parser in prince must be implemented using json_c and a different interface must be defined to communicate over the graph_parser interface.

Use http-parser to parse the json response

Using https://github.com/nodejs/http-parser would be helpful to receive the olsr1 jsoninfo http response

Write tests for prince

olsr.c and oonf.c are not tested.
Boost unit tests must be implemented

Check if graphparser counts endpoints in BC calculation

betweenness centrality scale factor is wrong

in brandes.c:293
double scale = 1 / (((double) (node_num - 1)) * ((double) (node_num - 2)));
The scaling factor for the BC is wrong.
see networkx/networkx#2709

Heuristic on weighted graph not working

The heuristic algorithm is not calculating correctly the bc of a weighted graph.

BetwennessCentralityHeuristic calculations have an approximation ~ 5% on PLaw Graw

Prince fails the test with the PLaw Graph Generator if the Heuristic is enabled.
The percentage difference between python (reference val) and c++ (prince) timers calculation is up to the 5%.
Analizing the values of the BC calculated using the heuristic in c++ and using pure networx in python i got these values:
Timers diff: tc: 0.73% hello: 1,3%

BC values differences mean: 8,2 Variance: 168
Excluding one node with a completely different BC (0.0017 vs 0.041) the mean and variance are: 6,45 and 8,8 (still to high)

Dynamic initial timers for OONF are not working

In the latest versions of prince the funcionality of getting the initial hello and tc timers directly from the routing daemon has been added.
For the olsr module there's the function:

int get_initial_timers(routing_plugin *o, struct timers *t){
	t->h_timer = get_initial_timer(o, "/HelloTimer");
	t->tc_timer = get_initial_timer(o, "/TcTimer");
	if(t->h_timer && t->tc_timer){
		printf("Inital timers:%f\t %f\n", t->h_timer, t->tc_timer);
		return 1;
	}
	return 0;
}

A similar function should be created for OONF using the remote config plugin that already provides that API.

directed graph are not supported

Currently Prince and graph_parsers supports only undirected graphs.
OLSR2 uses directed graph, so we should implement them somehow.

Verify if graphparser works with DAT metric

OONF's DAT metric is a directional metric. So each we have 2 directed edges for each link. Each of this edges has a cost value.
Must check if graph parser is managing this correctly while calculating the BC.

connect hangs if host is not reachable

If the host is not reachable connect don't return thus the program is locked.

A non-blocking connect with a timer should be implemented.

c_graph_parser do not calculate centrality with linear graph of 36 nodes

When calculating the centrality of a 36 nodes linear graph, the centrality appear to be "nan" for all the nodes except the first and the last one.
I think that somewhere in c_graph_parser a division by 0 occurs.
netjson of the graph:
{"type": "NetworkGraph", "protocol": "olsrv2", "version": "poprouting custom", "revision": "0.11.3", "metric": "ff_dat_metric", "router_id": "h31_31", "nodes": [{"id": "h4_4"}, {"id": "h28_28"}, {"id": "h24_24"}, {"id": "h25_25"}, {"id": "h3_3"}, {"id": "h33_33"}, {"id": "h30_30"}, {"id": "h5_5"}, {"id": "h29_29"}, {"id": "h0_0"}, {"id": "h23_23"}, {"id": "h7_7"}, {"id": "h14_14"}, {"id": "h6_6"}, {"id": "h2_2"}, {"id": "h1_1"}, {"id": "h21_21"}, {"id": "h11_11"}, {"id": "h34_34"}, {"id": "h18_18"}, {"id": "h32_32"}, {"id": "h31_31"}, {"id": "h20_20"}, {"id": "h15_15"}, {"id": "h16_16"}, {"id": "h22_22"}, {"id": "h8_8"}, {"id": "h12_12"}, {"id": "h26_26"}, {"id": "h17_17"}, {"id": "h9_9"}, {"id": "h27_27"}, {"id": "h19_19"}, {"id": "h10_10"}, {"id": "h13_13"}, {"id": "h35_35"}], "links": [{"source": "h4_4", "cost": 1.0, "target": "h5_5"}, {"source": "h4_4", "cost": 1.0, "target": "h3_3"}, {"source": "h28_28", "cost": 1.0, "target": "h29_29"}, {"source": "h28_28", "cost": 1.0, "target": "h27_27"}, {"source": "h24_24", "cost": 1.0, "target": "h25_25"}, {"source": "h24_24", "cost": 1.0, "target": "h23_23"}, {"source": "h25_25", "cost": 1.0, "target": "h26_26"}, {"source": "h3_3", "cost": 1.0, "target": "h2_2"}, {"source": "h33_33", "cost": 1.0, "target": "h34_34"}, {"source": "h33_33", "cost": 1.0, "target": "h32_32"}, {"source": "h30_30", "cost": 1.0, "target": "h29_29"}, {"source": "h30_30", "cost": 1.0, "target": "h31_31"}, {"source": "h5_5", "cost": 1.0, "target": "h6_6"}, {"source": "h0_0", "cost": 1.0, "target": "h1_1"}, {"source": "h23_23", "cost": 1.0, "target": "h22_22"}, {"source": "h7_7", "cost": 1.0, "target": "h8_8"}, {"source": "h7_7", "cost": 1.0, "target": "h6_6"}, {"source": "h14_14", "cost": 1.0, "target": "h13_13"}, {"source": "h14_14", "cost": 1.0, "target": "h15_15"}, {"source": "h2_2", "cost": 1.0, "target": "h1_1"}, {"source": "h21_21", "cost": 1.0, "target": "h20_20"}, {"source": "h21_21", "cost": 1.0, "target": "h22_22"}, {"source": "h11_11", "cost": 1.0, "target": "h12_12"}, {"source": "h11_11", "cost": 1.0, "target": "h10_10"}, {"source": "h34_34", "cost": 1.0, "target": "h35_35"}, {"source": "h18_18", "cost": 1.0, "target": "h17_17"}, {"source": "h18_18", "cost": 1.0, "target": "h19_19"}, {"source": "h32_32", "cost": 1.0, "target": "h31_31"}, {"source": "h20_20", "cost": 1.0, "target": "h19_19"}, {"source": "h15_15", "cost": 1.0, "target": "h16_16"}, {"source": "h16_16", "cost": 1.0, "target": "h17_17"}, {"source": "h8_8", "cost": 1.0, "target": "h9_9"}, {"source": "h12_12", "cost": 1.0, "target": "h13_13"}, {"source": "h26_26", "cost": 1.0, "target": "h27_27"}, {"source": "h9_9", "cost": 1.0, "target": "h10_10"}]}

Manage exceptions in lib_graphparser's C bindings

The C bindings for graphparser lib are not catching the exceptions.

get_initial_timers

When prince try to get initial timers inside nepa test it crashes

configurations issues

The json configuration parser has some issues. the configuration schema must be clarified with optional/default and mandatory parameters.

Refactor C++ Code and use late bindings.

The classes BetweennessCentrality and BetwennessCentralityHeuristic should implement the same interface.
Doing this way we could access the interface method without caring of the implementation.

Read self_id from json file

The Originator (or Main IP) of the node now must be explicitly setted in the config file.
The parser should read it from the json.

Initial timers are hardcoded

Initial values of timers should be polled by prince.

Load Prince plugins dynamically

Routing protocol specific plugins should comply with the plugin interface defined in plugin_interface.h

Implement ini config file

A config file reader must be set to load the following parameters:

rp_host (hostname)
rp_port = (int)
rp_type = (olsr/oonf)
node_id = (string of main ip / originator)