Calculating a potential route of a packet offline

StackOverflow https://stackoverflow.com/questions/8555574

  •  20-03-2021
  •  | 
  •  

Question

I'm trying to find a method for enumerating a few possible routes a packet may take on the internet, specifically counting ASes it might pass on the route.

Is this possible at all, and will I be able to collect all the necessary information to compute them offline (namely a possibly consistent snapshot of all the BGP routes)?

Was it helpful?

Solution

Writing the kind of algorithm I think you are asking about is probably not as easy as you may hope for.

  1. The answer to whether you can calculate potential AS paths for packets is an unqualified yes. You can obtain a large picture of the internet by connecting to a BGP Looking Glass. There are a number of BGP Looking Glasses that you can connect to and pull entire BGP tables from.

  2. Whether you can calculate a packet's future path with any consistent degree of probability is a significantly more difficult endeavor for the following reasons:

    • There are statistically only a few BGP Looking Glasses compared to the number of Autonomous Systems on the internet.
    • A portion of the BGP routing table will get aggregated into a larger route blocks in-transit for some AS's local policy (perhaps completely hiding the path of Autonomous Systems behind said aggregator, if they choose not to display the set of aggregated Autonomous Systems). If the Looking Glass that you use as the source of your information gets such an aggregate, you will loose path ordering information, and you may loose path membership information for that route.
    • You will get almost no visibility into the local Autonomous System's internal decision-making policy regarding transit traffic. Although BGP announces the best path for traffic, local routers within an Autonomous System may be configured to over-ride the AS-wide decision for reasons of load-balancing policy, politics, or whatever.
    • Link flapping will always change path dynamics, at least temporarily.

Sample output from routeviews.org's Cisco IOS BGP Looking Glass:

bgp-views>show ip bgp 4.0.0.0
BGP routing table entry for 4.0.0.0/9, version 658263
Paths: (35 available, best #13, table Default-IP-Routing-Table)
  Not advertised to any peer
  19214 25973 3356, (aggregated by 3356 4.69.130.2)
    208.74.64.40 from 208.74.64.40 (208.74.64.40)
      Origin IGP, localpref 100, valid, external, atomic-aggregate
  852 1299 3356, (aggregated by 3356 4.69.130.18)
    154.11.98.225 from 154.11.98.225 (154.11.98.225)
      Origin IGP, metric 0, localpref 100, valid, external, atomic-aggregate
      Community: 852:180
  852 1299 3356, (aggregated by 3356 4.69.130.10)
    154.11.11.113 from 154.11.11.113 (154.11.11.113)
      Origin IGP, metric 0, localpref 100, valid, external, atomic-aggregate
      Community: 852:180
  3561 3356, (aggregated by 3356 4.69.130.2)
    206.24.210.102 from 206.24.210.102 (206.24.210.102)
      Origin IGP, localpref 100, valid, external, atomic-aggregate
  812 6461 3356, (aggregated by 3356 4.69.130.12)
    64.71.255.61 from 64.71.255.61 (64.71.255.61)
      Origin IGP, localpref 100, valid, external, atomic-aggregate
  3277 3267 1273 1273 3356, (aggregated by 3356 4.69.130.76)
    194.85.102.33 from 194.85.102.33 (194.85.4.4)
      Origin IGP, localpref 100, valid, external, atomic-aggregate
      Community: 3277:3267 3277:65321 3277:65323 3277:65330
  6939 1299 3356, (aggregated by 3356 4.69.130.2)
    216.218.252.164 from 216.218.252.164 (216.218.252.164)
      Origin IGP, localpref 100, valid, external, atomic-aggregate
  286 3356, (aggregated by 3356 4.69.130.82)
    134.222.87.1 (inaccessible) from 134.222.87.1 (134.222.85.99)
      Origin IGP, localpref 100, valid, external, atomic-aggregate
      Community: 286:18 286:19 286:29 286:800 286:888 286:3031 286:4010
  [table manually truncated for brevity]
bgp-views>

Some relevant links associated with BGP analysis...

This is a sample AS graph from bgplay that you may find interesting... This is a screenshot from a time replay of BGP path information going to NASA's BGP Autonomous System (AS297).

enter image description here

EDIT:

I am a professional network engineer; coding is something I do to enhance my network engineering skills. Regarding your question about whether routeviews.org has got good data, when I was working with the development team for a large network equipment manufacturer who shall remain nameless, Routeviews.org was my defacto source of live BGP table information. Plus, I always use Routeviews when debugging internet routing issues. Their raw bgp Looking Glass data is as good as you will get for free.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top