Skip to content

Utilities

Prefix trees

Everything that measures a radix.Radix tree lives in quickrib.radix_utils.

quickrib.radix_utils

Everything that reads a radix.Radix prefix tree.

The RIB is a radix tree per vantage point (see :data:~quickrib.rib_table.RIBData), and several observers measure the address space one holds. Those measurements used to be spread across the observers that happened to need them first; they live here so there is one implementation of each and one place to test them (tests/test_radix.py).

Two questions come up, and they are not the same one:

  • How much space does this one node contribute? :func:radix_prefix_size subtracts the node's direct children, so a prefix and the more specifics announced inside it do not both claim the same addresses. This is what AS hegemony weights a path by.
  • How much space does the whole tree cover? :func:radix_size (in addresses) and :func:radix_block_count (in /24s or /48s) sum only the least specific nodes, since anything nested inside one of them is already counted. This is the union, and it is what IODA's visible-/24s signal reports.

Every function reads the address family off each node, so a tree holding both IPv4 and IPv6 prefixes is measured correctly.

PRECOMPUTED_BLOCK_SIZES_IPV4 = {plen: (2 ** (32 - plen)) for plen in (range(33))} module-attribute

Number of addresses in an IPv4 prefix, by prefix length.

PRECOMPUTED_BLOCK_SIZES_IPV6 = {plen: (2 ** (128 - plen)) for plen in (range(129))} module-attribute

Number of addresses in an IPv6 prefix, by prefix length.

PRECOMPUTED_BLOCK_COUNTS_IPV4 = {plen: (1 << 24 - plen) for plen in (range(25))} module-attribute

Number of /24s in an IPv4 prefix, by prefix length. Empty above /24.

PRECOMPUTED_BLOCK_COUNTS_IPV6 = {plen: (1 << 48 - plen) for plen in (range(49))} module-attribute

Number of /48s in an IPv6 prefix, by prefix length. Empty above /48.

tree_size(rtree)

Number of prefixes in rtree.

py-radix defines no __len__. nodes() materialises a list, but it does so in C and is several times faster than iterating the tree from Python (16ms against 60ms for 160k prefixes).

Source code in src/quickrib/radix_utils.py 
48
49
50
51
52
53
54
55
def tree_size(rtree: radix.Radix) -> int:
    """Number of prefixes in ``rtree``.

    ``py-radix`` defines no ``__len__``. ``nodes()`` materialises a list, but it
    does so in C and is several times faster than iterating the tree from
    Python (16ms against 60ms for 160k prefixes).
    """
    return len(rtree.nodes())

block_size(prefix)

Nominal number of addresses in prefix, ignoring any tree it sits in.

Cheap enough for a hot path: one string split and one dict lookup.

Source code in src/quickrib/radix_utils.py 
58
59
60
61
62
63
64
65
66
def block_size(prefix: str) -> int:
    """Nominal number of addresses in ``prefix``, ignoring any tree it sits in.

    Cheap enough for a hot path: one string split and one dict lookup.
    """
    plen = int(prefix.rsplit("/", 1)[1])
    if ":" in prefix:
        return PRECOMPUTED_BLOCK_SIZES_IPV6[plen]
    return PRECOMPUTED_BLOCK_SIZES_IPV4[plen]

direct_children(rtree, rnode)

Yield the nodes whose immediate parent in rtree is rnode.

search_covered returns the whole subtree, including rnode itself and every grandchild; the parent test keeps only the first generation. A node is never its own parent, so rnode drops out without a special case.

Source code in src/quickrib/radix_utils.py 
69
70
71
72
73
74
75
76
77
78
79
def direct_children(rtree: radix.Radix, rnode: RadixNode) -> Iterator[RadixNode]:
    """Yield the nodes whose *immediate* parent in ``rtree`` is ``rnode``.

    ``search_covered`` returns the whole subtree, including ``rnode`` itself and
    every grandchild; the parent test keeps only the first generation. A node is
    never its own parent, so ``rnode`` drops out without a special case.
    """
    prefix = rnode.prefix
    for child in rtree.search_covered(prefix):
        if child.parent is not None and child.parent.prefix == prefix:
            yield child

radix_prefix_size(rtree, rnode)

Addresses rnode contributes, after deaggregation.

Its own block minus its direct children's: the space they cover is theirs to account for, and counting it twice is what makes a naive sum over a peer's table exceed the address space it actually routes. Grandchildren are already subtracted from their own parent, so they must not be subtracted again here.

Source code in src/quickrib/radix_utils.py 
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
def radix_prefix_size(rtree: radix.Radix, rnode: RadixNode) -> int:
    """Addresses ``rnode`` contributes, after deaggregation.

    Its own block minus its direct children's: the space they cover is theirs to
    account for, and counting it twice is what makes a naive sum over a peer's
    table exceed the address space it actually routes. Grandchildren are already
    subtracted from their own parent, so they must not be subtracted again here.
    """
    sizes = (
        PRECOMPUTED_BLOCK_SIZES_IPV6
        if ":" in rnode.prefix
        else PRECOMPUTED_BLOCK_SIZES_IPV4
    )
    return sizes[rnode.prefixlen] - sum(
        sizes[child.prefixlen] for child in direct_children(rtree, rnode)
    )

radix_size(rtree)

Number of addresses the union of rtree's prefixes covers.

Source code in src/quickrib/radix_utils.py 
120
121
122
def radix_size(rtree: radix.Radix) -> int:
    """Number of **addresses** the union of ``rtree``'s prefixes covers."""
    return _union(rtree, PRECOMPUTED_BLOCK_SIZES_IPV4, PRECOMPUTED_BLOCK_SIZES_IPV6)

radix_block_count(rtree)

Number of /24s (or /48s for IPv6) the union of rtree covers.

:func:radix_size in the unit operators route in. A prefix longer than the block contributes nothing, so a lone /25 counts as zero /24s.

Source code in src/quickrib/radix_utils.py 
125
126
127
128
129
130
131
def radix_block_count(rtree: radix.Radix) -> int:
    """Number of **/24s** (or /48s for IPv6) the union of ``rtree`` covers.

    :func:`radix_size` in the unit operators route in. A prefix longer than the
    block contributes nothing, so a lone /25 counts as zero /24s.
    """
    return _union(rtree, PRECOMPUTED_BLOCK_COUNTS_IPV4, PRECOMPUTED_BLOCK_COUNTS_IPV6)

Elements

What an observer is handed, and what a radix node stores.

quickrib.elements

What QuickRIB puts in front of its observers.

pybgpflux yields a :class:~pybgpflux.BGPElement whose fields is a total=False TypedDict shared by every kind of MRT record it can parse, so as-path is typed as the wire string and everything is optional.

QuickRIB narrows both of those before an element reaches an observer:

  • :func:~quickrib.quickrib.process_path rewrites as-path in place from the wire string to a list of ASNs, and drops the element entirely if the path is malformed or contains an AS set. :class:ParsedElement is that same element with the field typed truthfully.
  • Only R, A and W elements exist. pybgpflux never yields BGP state-change records: its bgpdump parser filters them and its element type is Literal["R", "A", "W"]. A prefix is therefore always present on the elements QuickRIB handles, even though ElementFields allows its absence. The old-state / new-state keys there are vestigial, inherited from pybgpstream, which does emit state changes.

:class:RIBNodeData is the other half: what a radix node's .data holds, and what observers are handed as data / old_data.

ParsedFields = TypedDict('ParsedFields', {'prefix': str, 'as-path': list[str], 'communities': list[str], 'next-hop': NotRequired[str]}) module-attribute

fields of a route (R or A), after QuickRIB has parsed the AS path.

Everything a route carries is required: process_path drops any element whose path is missing or malformed, so by the time an observer sees one, the prefix, the path and the community list are all there. Only next-hop, which QuickRIB never reads, may be absent.

AnyElement = ParsedElement | WithdrawalElement module-attribute

Either kind. Use it for helpers that only touch what both carry: the peer, the collector, the timestamp, and fields["prefix"].

RIBNodeData = TypedDict('RIBNodeData', {'as-path': list[str], 'communities': list[str], 'time': float, 'as-path-history': NotRequired['deque[list[str]]']}) module-attribute

What a radix node's .data holds, and what observers get as data.

RIBTable writes all three on every insert, so all three are required. as-path-history is the exception: it only exists when the RIB is a :class:~quickrib.observers.update_tagger.RIBTablePathHistory.

WithdrawalFields

Bases: TypedDict

fields of a withdrawal, which names a prefix and nothing else.

Source code in src/quickrib/elements.py 
46
47
48
49
class WithdrawalFields(TypedDict):
    """``fields`` of a withdrawal, which names a prefix and nothing else."""

    prefix: str

ParsedElement

Bases: NamedTuple

A route whose as-path has been parsed into a list of ASNs.

Structurally identical to :class:~pybgpflux.BGPElement. QuickRIB does not build a new object per message; it just stops lying about the field types once the path has been rewritten.

Source code in src/quickrib/elements.py 
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class ParsedElement(NamedTuple):
    """A route whose ``as-path`` has been parsed into a list of ASNs.

    Structurally identical to :class:`~pybgpflux.BGPElement`. QuickRIB does not
    build a new object per message; it just stops lying about the field types
    once the path has been rewritten.
    """

    time: float
    type: Literal["R", "A"]
    collector: str
    peer_asn: int
    peer_address: str
    fields: ParsedFields

WithdrawalElement

Bases: NamedTuple

A withdrawal, whose fields hold only the prefix being withdrawn.

Source code in src/quickrib/elements.py 
68
69
70
71
72
73
74
75
76
class WithdrawalElement(NamedTuple):
    """A withdrawal, whose ``fields`` hold only the prefix being withdrawn."""

    time: float
    type: Literal["W"]
    collector: str
    peer_asn: int
    peer_address: str
    fields: WithdrawalFields