Valley Free Explorer

valley-free crate 是一个 Rust 包，用于读取 CAIDA 的 AS-relationship 数据 并使用 valley-free 模型探索 AS 级路径。

核心思想

拓扑构建

进行 valley-free 路径模拟的第一步是获取 AS 级拓扑和 AS 间关系。在这个库中，我们使用 CAIDA 的 AS-relationship 数据 来获取 AS 关系和拓扑。

CAIDA 的 AS-relationship 数据格式如下

## 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
...

数据格式是

<provider-as>|<customer-as>|-1
<peer-as>|<peer-as>|0

数据集中的非注释行表示

• 两个 AS 之间存在 AS 级链接
• 关系要么是端到端 (0) 要么是提供者到客户 (-1)

路径传播

不是从流量源到源头 AS 查找路径，而是模拟从源头和记录传播到的所有路径的 AS 路径传播。例如，当搜索指向 AS15169 的所有潜在路径时，它从拓扑中的 as15169 开始，找到所有符合无谷路由的下一个跳（即下一个跳仍然是无谷的路径），然后递归地进行深度优先搜索，直到找不到更多符合无谷路由的下一个跳。因此，路径应该包含指向 asn 的所有可能路径。

对于每个给定的源头 ASN，递归地进行模拟。递归中断条件如下

1. 检测到循环；
2. 之前已从 AS 传播；
3. 所有 有效下一个跳 AS 已传播

有效下一个跳 确定如下

1. 如果当前路径是从客户传播的，则它可以传播到其所有客户、提供者和对等方；
2. 如果当前路径是从提供者或对等方传播的，则它只能传播到其客户。

使用方法

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

该包可在 PyPi 上找到，网址为 https://pypi.ac.cn/project/valley-free/。对于安装，可以使用 pip3 install valley-free。

#!/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

手动构建 Python 包

为当前 Python 环境构建： maturin build --release

使用许多Linux环境构建： docker run --rm -v $(pwd):/io konstin2/maturin build