Struct valley_free::Topology

pub struct Topology {
    pub ases_map: HashMap<u32, As>,
}

Definition of Topology

Fields

ases_map: HashMap<u32, As>

Hashmap of ASes: ASN (u32) to As

Implementations

impl Topology

pub fn new() -> Topology

Constructor of the Topology struct

pub fn build_topology(&mut self, reader: impl BufRead) -> Result<(), String>

Build the Topology using CAIDA AS-relationship datafile.

This function takes an reader that implements BufRead trait, read lines from the reader, and parse the input.

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

pub fn propagate_paths(
    &self,
    all_paths: &mut Vec<Path>,
    asn: u32,
    dir: Direction,
    path: Path,
    seen: &mut HashSet<u32>
)

Recursively calculate path propagation results.

Recursion breaking conditions:

1. loop detected;
2. previously propagated from the AS;
3. all connected ASes have been called

Propagation logic:

1. if the current path is propagated from a customer, then it can propagate to all of its’ customers, providers, and peers
2. if the current path is propagated from a provider or a peer, it can only propagate to its customers (thus achiving valley-free)

Full example: to explore all paths toward AS123, call

use std::{fs::File, io::BufReader, collections::HashSet};
use valley_free::*;
use bzip2::read::BzDecoder;

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);

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());

Arguments:

• all_paths: a muttable Vector of Paths passed in to store explored paths
• asn: the current ASN that will propagate paths
• dir: the Direction of the propagation
• path: the path so far(not including the current AS)
• seen: a HashSet of ASes that it has explored already

Trait Implementations

impl<'source> FromPyObject<'source> for Topology

fn extract(obj: &'source PyAny) -> PyResult<Self>

Extracts Self from the source PyObject.

impl IntoPy<Py<PyAny>> for Topology

fn into_py(self, py: Python<'_>) -> PyObject

Performs the conversion.

impl PyClass for Topology

type Dict = PyClassDummySlot

Specify this class has #[pyclass(dict)] or not.

type WeakRef = PyClassDummySlot

Specify this class has #[pyclass(weakref)] or not.

type BaseNativeType = PyAny

The closest native ancestor. This is PyAny by default, and when you declare #[pyclass(extends=PyDict)], it’s PyDict.

impl PyClassDescriptors<Topology> for PyClassImplCollector<Topology>

fn py_class_descriptors(self) -> &'static [PyMethodDefType]

impl PyClassImpl for Topology

const DOC: &'static str

Class doc string

const IS_GC: bool

#[pyclass(gc)]

const IS_BASETYPE: bool

#[pyclass(subclass)]

const IS_SUBCLASS: bool

#[pyclass(extends=…)]

type Layout = PyCell<Self>

Layout

type BaseType = PyAny

Base class

type ThreadChecker = ThreadCheckerStub<Topology>

This handles following two situations:

fn for_each_method_def(visitor: &mut dyn FnMut(&[PyMethodDefType]))

fn get_new() -> Option<newfunc>

fn get_alloc() -> Option<allocfunc>

fn get_free() -> Option<freefunc>

fn for_each_proto_slot(visitor: &mut dyn FnMut(&[PyType_Slot]))

fn get_buffer() -> Option<&'static PyBufferProcs>

impl PyTypeInfo for Topology

type AsRefTarget = PyCell<Self>

Utility type to make Py::as_ref work.

const NAME: &'static str

Class name.

const MODULE: Option<&'static str>

Module name, if any.

fn type_object_raw(py: Python<'_>) -> *mut PyTypeObject

PyTypeObject instance for this type.

fn is_type_of(object: &PyAny) -> bool

Checks if object is an instance of this type or a subclass of this type.

fn is_exact_type_of(object: &PyAny) -> bool

Checks if object is an instance of this type.