A note on querying the size of the BGP routing table using SNMP

[gdt]

When running BGP it is useful to graph the number of routes in the BGP routing information base. Unfortunately this isn't in a SNMP variable. So to calculate this statistic SNMP-using code typically walks through bgp4PathAttrTable (or the MBGP equivalent MIB) counting the number of rows. Unfortunately, the global IP routing table is about a third of a million routes so it doesn't take long until collecting this useful statistic starts to have a high cost.

SNMP ObjectIDs are ordered. This means that we can do a binary search of the OIDs to find the last OID in the bgp4PathAttrTable. There's a small wrinkle: we don't know the upper bound. But any close-ish guess is good enough -- we simply keep doubling the upper search limit (and bringing up the lower search limit) until we exceed the OIDs which represent the bgp4PathAttrTable.

The concepts of halving and doubling are a little complicated by the values of the OID being IP addresses rather than random integers. But the complication isn't massive.

Binary search is log₂(N), so the size of the BGP routing table can be determied in under 20 SNMP GETs.

On a related topic, the test for a non-zero-sized routing table is a single GETNEXT for the OID of the bgp4PathAttrTable. This makes it cheap to test that a BGP neighbour is up (one GET) and that we are receiving some routes (one GETNEXT).