[Discussion] Represent the topology as a graph

[guissalustiano]

Hi, I'm trying to use this library to research the AS routings (specifically the Tier 1 bypass, replication this Todd Arnold strudy but I'm having a problem with the methods exposed by this library.

First, the graph implementation with hash maps is hard to manage, I would like to remove some AS from the topology but is hard do to it because I need to remove it from all AS providers, peers, and customer hash_set.

I tried to bypass this by analyzing just all paths and removing the paths with the specific AS, but then I discovered that all_paths do not really return all paths, but just one path to all AS (what makes sense for the method name) and this path propagation do not have one clear policy.

With these concerns, I tried to imagine a better interface that allows more use cases to be contemplated, and It was hard to run away from graphs because there are many well-known algorithms for analyzing paths, I just needed to create a DAG with the valley-free model. I explore that on my valley-free-graph, here is one example of using the A* algorithm prioritizing peers to find the path between two AS's, and here my research changing the topology structure.

I would like to merge my repo with this library, it makes more sense to keep it in the bgpkit org and it implements the same idea (the path generator was inspired by your first path propagation implementation), but I see two main problems:

• This will break all the current interface of the library
• I'm not sure how to expose this to Python, since I'm using petgraph to organizate the graph.

From my paths_graph, it is possible to generate the path propagation using a DFS if you want to keep the path_propagation function.

[digizeph]

Hey @guissalustiano, thank you for the discussion here! Your work on petgraph is very insightful!

This crate has been an experimental crate that reproduce some of my previous Python work in Rust. The goal is to study how ASes on the Internet can reach a given source AS. It is not meant to handle the entire Internet topology, although theoretically it can by just running the path propagation for all ASes. I still hasn't got the chance to review in details your work on #4 and #5, but I think you are definitely right that HashMap iteration will produce random orders that may end up in different results in multiple runs. I am not sure fixing that would help resolve your research questions (probably not as you started the new crate).

In terms of merging your work into this library, I don't know enough about petgraph to tell how it handles different cases, but from the looks of your code and some examples, it seems to be able to achieve everything this crate heads out to do. I am onboard with you creating a PR and merge it over here. I can help handle the Python bindings and probably also CLI tools if needed. Don't worry about breaking changes, we just need to make sure tell inform users (if any) to use version 0.2 for the recursion-based non-graph version if they choose so. This probably also means the new PR will resolve #4 and deprecate #5.

Let me know what you think!

[guissalustiano]

Hi @digizeph, thanks for the return!

My PR #5 solves the problem that sometimes some AS are not reachable, and other times it is (this regression test maybe explain better). After solving that I discovered more problems with my approach, which led me to try to change the topology, but in the current implementation changing the topology is hard, because you need to remove the node from the topology hash map and also from all other providers, peers, and customers that reference them, so my goal with new crate was used a graph library instead of implement the graph by hand, that way is easy to change the topology and we gain accesses to the others graph algorithm methods.

Thanks for the receptivity! I will open a new PR with the graph implementation and we can talk about work on the CLI and Python bindings there!

(I am still developing my English so if something is not clear please let me know!)

[guissalustiano]

PR opened! Maybe we can create a new branch to accommodate this before consolidating the Python bindings?

[digizeph]

main as target is fine. we will hold 0.3 release until python bindings are ready.