Network graph processing in Rust by stevenengler · Pull Request #1573 · shadow/shadow

stevenengler · 2021-08-12T14:43:36Z

This replaces shadow's topology parsing and processing with a Rust version. The GML is parsed using nom, and the graph processing is done using petgraph. The GML parser is in src/lib/gml-parser and the graph processing code is in src/main/routing. This also removes the igraph dependency. This PR will be easiest to review as individual commits.

Network graph changes:

ignore country_code, city_code, and ip_address node fields (these will be used by tornettools instead)
renamed bandwidth_down and bandwidth_up to host_bandwidth_down and host_bandwidth_up

Shadow config changes:

removed city_code_hint, country_code_hint, and ip_address_hint host fields
added ip_addr and network_node_id (required) host fields
added ~~gml_lzma~~ gml_xz graph type

For the GML parser, I'm not super happy with it as a general GML parser and with its memory usage. But it has all of the required functionality required for shadow, so I think it's good enough for now. I might re-visit this in the future. Shadow can also now read ~~lzma-compressed~~ xz-compressed network graph files.

In Shadow's routing code, the IP address assignment was moved out of the DNS type and into a new IpAssignment type. The hosts with the ip_addr field set are assigned their IP addresses first, and then the remaining hosts are assigned IP addresses starting at 11.0.0.1 (skipping any that end in .0 or .255). Shadow computes a lookup table (a RoutingInfo object) that contains computed latencies and packet loss fractions for all pairs of nodes that have hosts assigned to them. Rather than computing these values as-needed during the simulation, we now compute these all before the simulation starts. This lets us free the graph object before starting the simulation.

If the use_shortest_paths config option is true (the default), shadow will compute the shortest paths between all graph nodes that have hosts assigned to them (but using the full graph during the shortest path calculation). For the path from a node to the same node (the path from node X to node X), rather than using a latency of 0, shadow will find the shortest path that contains at least one edge. This is consistent with shadow's current behaviour (shadow's current behaviour technically has a bug when the graph is directed, but that's fixed in this rust version).

If the use_shortest_paths config option is false, the graph must be complete with self-loops (and have at most one edge between any two nodes), and shadow will simply use the direct edge between the two nodes.

The configuration conversion script will no longer generate a valid shadow 2.0 config (for example it doesn't compute the network_node_id fields). But the generated config file should still be useful if someone does need to convert a shadow 1.0 config, and will require a small amount of manual editing to get working. We think this is an okay compromise since the shadow config format has changed a lot, and we don't think the conversion scripts will be used very often.

This PR won't be merged until we have a tornettools PR that's also ready to merge.

codecov · 2021-08-13T19:44:43Z

Codecov Report

Merging #1573 (c6ce2e2) into main (d64d07c) will increase coverage by 1.82%.
The diff coverage is 59.79%.

❗ Current head c6ce2e2 differs from pull request most recent head 8db4e22. Consider uploading reports for the commit 8db4e22 to get more accurate results

@@            Coverage Diff             @@
##             main    #1573      +/-   ##
==========================================
+ Coverage   52.51%   54.33%   +1.82%     
==========================================
  Files         141      141              
  Lines       21286    18548    -2738     
  Branches     5380     4452     -928     
==========================================
- Hits        11178    10078    -1100     
+ Misses       7148     5810    -1338     
+ Partials     2960     2660     -300

Flag	Coverage Δ
tests	`54.33% <59.79%> (+1.82%)`	⬆️

Flags with carried forward coverage won't be shown. Click here to find out more.

Impacted Files	Coverage Δ
src/main/host/syscall/socket.c	`78.42% <0.00%> (+0.11%)`	⬆️
src/lib/gml-parser/src/gml.rs	`19.73% <19.73%> (ø)`
src/lib/gml-parser/src/lib.rs	`40.00% <40.00%> (ø)`
src/main/routing/dns.c	`60.60% <57.14%> (-1.97%)`	⬇️
src/main/core/controller.c	`66.26% <57.69%> (-10.41%)`	⬇️
src/main/core/manager.c	`69.16% <62.50%> (-1.75%)`	⬇️
src/lib/gml-parser/src/parser.rs	`40.67% <70.71%> (ø)`
src/main/host/host.c	`69.96% <81.25%> (+1.06%)`	⬆️
src/main/core/worker.c	`74.75% <86.66%> (+0.09%)`	⬆️
src/main/core/main.c	`50.73% <100.00%> (+0.37%)`	⬆️
... and 32 more

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update d64d07c...8db4e22. Read the comment docs.

sporksmith · 2021-08-16T15:39:39Z

added gml_lzma graph type
...
Shadow can also now read ~~lzma-compressed~~ xz-compressed network graph files.

Would it make more sense to decouple the compression type from the graph type? e.g. add a 'compression' attribute?

stevenengler · 2021-08-16T15:45:27Z

added gml_lzma graph type
...
Shadow can also now read ~~lzma-compressed~~ xz-compressed network graph files.

Would it make more sense to decouple the compression type from the graph type? e.g. add a 'compression' attribute?

I think it would make more sense generally, but also brings up weird situations like if someone specifies type: 1_gbit_switch, compression: xz, which wouldn't make sense. But we could just add more error log statements to cover those.

stevenengler · 2021-08-16T17:11:05Z

added gml_lzma graph type
...
Shadow can also now read ~~lzma-compressed~~ xz-compressed network graph files.

Would it make more sense to decouple the compression type from the graph type? e.g. add a 'compression' attribute?

I think it would make more sense generally, but also brings up weird situations like if someone specifies type: 1_gbit_switch, compression: xz, which wouldn't make sense. But we could just add more error log statements to cover those.

@sporksmith What do you think about changing the config format from:

network:
  graph:
    type: gml_xz
    path: graph-compressed.gml.xz

to:

network:
  graph:
    type: gml
    file:
      path: graph-compressed.gml.xz
      compression: xz

sporksmith

Still reviewing a commit at a time - stopped at "f784149fe3329c3266e9520537d8ef9887eb1762 Add support for compressed network graphs"

.gitignore

src/lib/gml-parser/src/gml.rs

src/lib/gml-parser/src/lib.rs

src/main/core/controller.c

src/main/routing/network_graph.rs

src/main/routing/petgraph_wrapper.rs

sporksmith · 2021-08-16T17:36:08Z

@sporksmith What do you think about changing the config format from:

LGTM. I just got to that commit in the review - maybe it makes sense for me to skip that commit for now, and you can push a fixup?

stevenengler · 2021-08-16T18:02:27Z

@sporksmith What do you think about changing the config format from:

LGTM. I just got to that commit in the review - maybe it makes sense for me to skip that commit for now, and you can push a fixup?

I pushed it as a new commit rather than a fixup since it changes the old uncompressed behaviour as well.

sporksmith

Finished - no further comments :)

The parser is currently unused.

stevenengler · 2021-08-23T16:22:33Z

The tornettools PR is shadow/tornettools/pull/31.

stevenengler added this to the Updates to and new formats for Shadow configuration milestone Aug 12, 2021

stevenengler self-assigned this Aug 12, 2021

stevenengler force-pushed the rust-gml branch 2 times, most recently from 03f6be2 to 464edcf Compare August 13, 2021 19:36

github-actions bot added the Component: Tools Peripheral tools like parsing log files or visualizing results label Aug 13, 2021

stevenengler force-pushed the rust-gml branch from 464edcf to 19374b0 Compare August 13, 2021 19:51

stevenengler requested a review from sporksmith August 13, 2021 22:13

stevenengler marked this pull request as ready for review August 16, 2021 06:14

sporksmith reviewed Aug 16, 2021

View reviewed changes

sporksmith requested changes Aug 16, 2021

View reviewed changes

sporksmith approved these changes Aug 17, 2021

View reviewed changes

stevenengler added 8 commits August 23, 2021 11:00

Make configuration types and fields public

ef3587c

Added Rust GML parser

c5a7058

The parser is currently unused.

Added Rust network graph parsing

badce8c

Remove unused C topology and path code

822f04f

Add support for compressed network graphs

7ce34a8

Updated tests for new graph+config format

cc8627e

Remove igraph dependency

ef7899d

Updated docs for new graph+config format

4c72a8d

stevenengler added 2 commits August 23, 2021 11:00

Updated config conversion scripts

4a9630a

Reorganized shadow's GML file options

8db4e22

stevenengler force-pushed the rust-gml branch from c6ce2e2 to 8db4e22 Compare August 23, 2021 15:02

stevenengler merged commit bd13002 into shadow:main Aug 23, 2021

stevenengler deleted the rust-gml branch August 23, 2021 16:19

stevenengler mentioned this pull request Sep 15, 2021

Move topology parsing and processing from igraph to Rust #1365

Closed

robgjansen mentioned this pull request Oct 14, 2021

Use hash instead of RNG for hintless hosts #690

Closed

Conversation

stevenengler commented Aug 12, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

codecov bot commented Aug 13, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

sporksmith commented Aug 16, 2021

Uh oh!

stevenengler commented Aug 16, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

stevenengler commented Aug 16, 2021

Uh oh!

sporksmith left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

sporksmith commented Aug 16, 2021

Uh oh!

stevenengler commented Aug 16, 2021

Uh oh!

sporksmith left a comment

Choose a reason for hiding this comment

Uh oh!

stevenengler commented Aug 23, 2021

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

stevenengler commented Aug 12, 2021 •

edited

Loading

codecov bot commented Aug 13, 2021 •

edited

Loading

stevenengler commented Aug 16, 2021 •

edited

Loading