3 unstable releases
0.2.0 | Nov 25, 2021 |
---|---|
0.1.1 | Feb 2, 2021 |
0.1.0 | Feb 1, 2021 |
#14 in #topology
785KB
229 lines
Valley Free Explorer
valley-free
crate is a Rust package that reads CAIDA's AS-relationship data
and explores AS-level paths using valley-free
model.
Core Ideas
Topology Building
The first step for doing valley-free
paths simulation is to obtain AS-level
topology and inter-AS relationships. Here in this library, we utilize CAIDA's
AS-relationship data data to obtain both the AS relationships and the
topology.
The CAIDA's AS-relationship data is formatted as follows:
## A FEW LINES OF COMMENT
## A FEW LINES OF COMMENT
## A FEW LINES OF COMMENT
1|7470|0
1|9931|-1
1|11537|0
1|25418|0
2|35000|0
2|263686|0
...
The data format is:
<provider-as>|<customer-as>|-1
<peer-as>|<peer-as>|0
A non-comment row in the dataset means:
- there is a AS-level link between the two ASes
- the relationships are either peer-to-peer (0) or provider-to-customer (-1)
Path Propagation
Instead of finding paths from traffic sources to origins ASes, it simulates the AS paths propagation from the origins and recording all the paths the propagation reaches. For example, when searching for all potential paths toward AS15169, it starts from as15169 on the topology, and find all next hops that conform with valley-free routing (i.e. the path with the next hop is still valley-free), and then recursively doing depth-first search until no more valley-free-conforming next hops can be found. As a result, the paths should contain all possible paths toward an asn.
The simluation is recursively done for each given origin ASN. Recursion breaking conditions are:
- loop detected;
- previously propagated from the AS;
- all valid next-hop ASes have been propagated
Valid next-hops are determined as follows:
- if the current path is propagated from a customer, then it can propagate to all of its' customers, providers, and peers;
- if the current path is propagated from a provider or a peer, it can only propagate to its customers.
Usage
Rust
[dependencies]
valley_free="0.2"
use std::{fs::File, io::BufReader};
use valley_free::*;
use bzip2::read::BzDecoder;
fn main(){
let mut topo = Topology::new();
let file = match File::open("20161101.as-rel.txt.bz2") {
Ok(f) => f,
Err(_) => panic!("cannot open file"),
};
let reader = BufReader::new(BzDecoder::new(&file));
let res = topo.build_topology(reader);
assert!(res.is_ok());
assert_eq!(topo.ases_map.len(), 55809);
let mut all_paths = vec![];
let mut seen = HashSet::new();
topo.propagate_paths(&mut all_paths, 15169, Direction::UP, vec![], &mut seen);
dbg!(all_paths.len());
}
Python
The package is available on PyPi at https://pypi.org/project/valley-free/. For installation, pip3 install valley-free
should do the trick.
#!/usr/bin/env python3
import valley_free
topo = valley_free.load_topology("20161101.as-rel.txt.bz2")
paths = valley_free.propagate_paths(topo, 15169)
print(len(paths))
# 55483
Manually build Python package
Build for current Python environment:
maturin build --release
Build using manylinux environment:
docker run --rm -v $(pwd):/io konstin2/maturin build
Dependencies
~3.5MB
~57K SLoC