Monitoring wireless BGP internets - Part 3

This is a rough sketch of a network monitor for community owned wireless BGP internets.

Consider a BGP internet monitoring system with access to
many BGP tables across the internet
and a Number Authority-Node Database eg: WiND or NodeDB

I am trying to figure out a process to attach levels of certainty to the information in the tables, find ghost links and ghost prefixes, and throw alarms.

The process aka the order algorithm:

We detect and filter out Prepends

Now, every path that contains an Autonomous System many times indicates a Loop and it should be alarmed and excluded from the following process.

Links: We split the table in pairs of AS numbers to get the links.

To attach a level of certainty to a pair we calculate a weight by adding a point for every hop starting from the AS in which we found the pair.
eg: consider the following as-path on the AS 1
2 3 4 5 6
the weight w of the pair 1 2 is equal to 0+1=1 w(1,2)=1 and w(2,3)=3 the smaller the weight is the most probable is that it exists

While we traverse the BGP Tables lower weights replace higher weights.

When, for an AS number x there is a w(x,y)=1 ( we have access to its table )
a pair x,z with w(x,z)=33 is invalid for sure and it should be alarmed.


For every prefix in the tables we check if it is assigned by the Number Authority, if not we alarm.

For every prefix in the tables we check if it is advertized by the AS in which is assigned by the Number Authority, if not we alarm.

We detect prefixes announced multiple times and according to our Number Authority should not be Anycast If we find such prefixes we use the information from the Number Authority to figure out who is cheating or messed up to alarm.

Ghost Prefixes:

If we see a path leading to a node in which we have access with a prefix not announced there, then this is a Ghost Prefix. This is the easy part. We may attempt to guess Ghost Prefixes with paths leading to Autonomous Systems in which we do not have access using weights.

For the prefix weight we use the size of the as-path.
Again, the smaller the weight, the higher the probability the prefix exists.

Again, while we traverse the tables lower weights replace higher weights.

This BGP monitoring system combined with
  • information from a Node Database eg: WiND or NodeDB
  • some classic nagios stuff
  • and some not so classic nagios stuff ( nagios1 , nagios2-missinglink router_scripts-missinglink )
can create monitoring systems that can throw meaningful alarms, draw near real time maps, and even do some shelf-healing.

thoughts on monitoring wirelless BGP internets