Human-readable reachability info

[julianofischer]

Hello, @jwhitbeck
Thanks in advance for helping.

When I run:
ditl graphs r store.jar 1 1 30
a new directory is created inside store.jar, named: edges_t1_d30.

This directory contains 3 files: index, info, and trace.
index and trace are binary files.

info contains information about the trace, as following
{ "type": "reachability", "eta": 1, "tau": 1, "delay": 30, "min time": 7, "max time": 31619667, "time unit": "s", "max update interval": 81082, "default priority": 100 }

However, I am interested in evaluating the reachability information. I suppose the information I need is in the file named trace. Am I right? Is there a way to convert trace to a human-readable format?

PS.: For an old version of ditl which I have access, the created directory is named "links" and there is a readable file named "snapshot".

[jwhitbeck]

Hi @julianofischer,

It's been a while since I last had to do this, but have you tried exporting it using something like: ditl graphs export-arcs --arcs edges_t1_d30 ?

[julianofischer]

It works very well for edges or arcs exporting.
However, there is no option for exporting reachability reports.
If I try the command you suggest, an error occurs:

java.lang.ClassCastException: ditl.graphs.ReachabilityTrace cannot be cast to ditl.graphs.EdgeTrace at ditl.graphs.cli.ExportEdges.run(ExportEdges.java:64) at ditl.cli.App.exec(App.java:113) at ditl.cli.CLI.startApp(CLI.java:129) at ditl.cli.CLI.parseArgs(CLI.java:80) at ditl.cli.CLI.main(CLI.java:158) java.lang.ClassCastException: ditl.graphs.ReachabilityTrace cannot be cast to ditl.graphs.EdgeTrace
What I am looking for is a way to view and evaluate the reachability, i.e., which nodes reach which nodes given some distinct parameters (tau, eta and delay).

Sorry if I am missing something.

[jwhitbeck]

It looks like you are using "export-edges". ReachabilityTrace extends ArcTrace, so I would expect "export-arcs" to work.

[julianofischer]

You're right.
It works.
However, the output is an arcs trace as following, not the reachability graph.

26	5	102.0	145.0
16	8	7.0	214.0
8	16	7.0	214.0
16	8	231.0	274.0
8	16	231.0	274.0
27	19	14.0	709.0
19	22	10.0	710.0
19	27	14.0	710.0
22	19	10.0	710.0

In the older version which I have access, when I run ditl graphs r, I get a trace (name snapshot) like this:

0
1195000
1 2
1 7
1 8
1 14
1 15
1 17
1 18
1 21
1 25
1 26
1 29
1 35
1 33
1 51
1 54
1 52
1 56
2 35

which shows the reachability graph.

It is this information I need, however I would like to use the most updated ditl version.

[jwhitbeck]

Got it. It sounds like you would like to print a snapshot of the reachability graph at a specific point in time.

Does this work for you?

ditl ps store.jar edges_t1_d30 0

[julianofischer]

Hi John, thank you.
ditl ps store.jar edges_t1_d30 0
returned

	at ditl.StatefulReader.seek(StatefulReader.java:43)
	at ditl.cli.PrintState.run(PrintState.java:51)
	at ditl.cli.App.exec(App.java:113)
	at ditl.cli.CLI.startApp(CLI.java:129)
	at ditl.cli.CLI.parseArgs(CLI.java:69)
	at ditl.cli.CLI.main(CLI.java:158)
java.io.IOException: Cannot seek before initial state

However
ditl ps store.jar edges_t1_d30 1000

worked!

There is a way to get snapshots for every 30 seconds?

In this context, it is valuable to mention that when I run (for this update version):
ditl graphs reachability STORE.jar 1 1 30.

a new directory called edges_t1_d30 is created into the store.jar

Since the trace file is binary, I'm not sure if it is really a edges trace or a reachability trace.
You previously mentioned that the ReachabilityTrace extends ArcTrace.

Do you remember which trace is saved into this directory generated by the command ditl graphs reachability?

[jwhitbeck]

ditl graphs reachability generates reachability traces, not edge traces. You should be able to verify that by looking at the info file in each trace, which uses a JSON format.

There isn't currently a way of printing the state every 30 seconds, but you should be able to achieve that by extending the PrintTrace code.

[julianofischer]

What about print the entire reachability trace?
Is there a way?

[jwhitbeck]

The reachability trace is just an arc trace with a few extra config params (tau, eta, delay). All the arc export functionality should work on reachability traces.

[julianofischer]

Thank you very much, John.
I wasn't getting it.
Just for clarifying:

I performed:
ditl graphs reachability store.jar 1 1 30

A directory named edges_t1_d30 was created into store.jar

So I ran:
ditl graphs xa --arcs edges_t1_d30 --output output_t1_d30 store.jar
and a file output_t1_d30 was created. Some lines (head -10) of this file are following

26	5	102.0	145.0
16	8	7.0	214.0
8	16	7.0	214.0
16	8	231.0	274.0
8	16	231.0	274.0
27	19	14.0	709.0
19	22	10.0	710.0
19	27	14.0	710.0
22	19	10.0	710.0

1. Does this means that node 5 reach node 26 at the instant 102 in at maximum 30 seconds considering an edge traversal equals to 1?
2. In turn, does this means that if a message is generated at the node 5 at instant 102, this message will reach node 26 (ignoring possible fails) within a max delay of 30 seconds?
3. Last but not least, the previous condition remains true from the instant 102 to through the instant 145?

Thank you very much in advance for your attention and kindness. You're awesome.

[jwhitbeck]

Hi Juliano,

Your understanding is correct except that you have to flip nodes 5 and 26. The first line means that a message generated on node 26 between instants 102 and 145 can reach node 5 within a max delay of 30 seconds (assuming an edge traversal time of 1).

[julianofischer]

Hello John, thank you again.
However, I think you did a mistake.

I performed the following sanity test.

1. I created a arcs trace (as we discussed previously on the format of this trace, I'm considering that the format is FROM TO BEGIN END) :

0	1	1	14
1	0	9	15
2	1	12	15
1	2	11      15

2. The arcs were imported

ditl graphs ia --orig-time-unit s --dest-time-unit s sanity.jar sanity.txt 

3. I tried to generate the reachability information:

ditl graphs r sanity.jar 1 1 5
java.io.IOException: No such trace 'edges'
	at ditl.Store.getTrace(Store.java:105)
	at ditl.graphs.cli.Reachability.run(Reachability.java:191)
	at ditl.cli.App.exec(App.java:113)
	at ditl.cli.CLI.startApp(CLI.java:129)
	at ditl.cli.CLI.parseArgs(CLI.java:80)
	at ditl.cli.CLI.main(CLI.java:158)
java.io.IOException: No such trace 'edges'

The first observation valuable observation is that altough we have the arcs trace, reachability is always using edges traces, so we need to convert arcs to edges.

4. Arcs trace was converted to edges trace

ditl graphs a2e sanity.jar

5. Extracting reachability information

ditl graphs r sanity.jar 1 1 5
ditl graphs r sanity.jar 1 1 10

6. Exporting "arcs":
   ditl graphs xa --arcs edges_t1_d5 --output t1d5 sanity.jar
   ditl graphs xa --arcs edges_t1_d10 --output t1d10 sanity.jar

Another obvervation: reachability uses edges traces, the directory created is named "edges_tn_dm", however, in order to export, we need to "export arcs", creating confusion with the names.

2	0	9.0	12.0
0	1	5.0	13.0
0	2	8.0	13.0
1	0	5.0	13.0
1	2	8.0	14.0
2	1	8.0	14.0

---

Comments

1. The use of edges results in symmetric reachabilty for neighbor nodes. These are the cases of 0 and 1 (5.0 - 13.0 in both directions) and 2 and 1 (8.0 - 14.0 in both directions).

2. When converting arcs to edges, if we have two arcs involving two nodes and corresponding to an intersecting instant of time (e.g. one from 0 to 1 [9-15] and other from 1 to 0 [1-14]), the edge is considered starting at the higher time. As example, for nodes 0 and 1, the edge starts at instant 9, otherwise the reachability among it would start at instant 1 and not at instant 5.

3. Similarly, when converting arcs to edges, if we have two arcs involving two nodes and corresponding to an intersecting instant of time (e.g. one from 0 to 1 [9-15] and other from 1 to 0 [1-14]), the edge is considered ending at the higher time. As example, for nodes 0 and 1, the edge ends at instant 15, otherwise the reachability among it would ends at instant 13 and not at instant 14 (because the edge traversal time is set to 1 second).

4. Lastly, contradicting what you have said above, the line 1 means the node 2 reaches node 0 from instant 9.0 to the instant 12.0. Since node 0 is two hops away (meaning that two seconds are enough if there is a end-to-end path between 0 and 2) and the connection between 2 and 1 begins at the instant 12, if the message is generated at the instant 9.0, 3 seconds pass until the end-to-end path arises and 2 seconds are required to go through 2 edges, reaching the destination within the deadline.

What do you think about it?
Am I right?
Sorry if I am letting something missing.

[jwhitbeck]

Hi Juliano,

Your understanding seems correct.

I think we are hitting the point where you need to write some code to get the results you want. Specifically, it sounds like you have an arcs trace that you directly want to compute reachability from (which is certainly doable but not currently supported), and the arcs-to-edges converter (which, by definition, looses information) doesn't meet your needs.

You should be able to adapt the EdgesToReachableConverter class to an ArcsToReachablaeConverter class and the hook it up to the rest of the code.

Feel free to open a Pull Request.