Blog Posts by Author

If you are among the upper echelon of network administrators who happen to have BGP administration within their scope of duties you probably have access to a lot of interesting, albeit quite verbose, information about the Internet at large. Generally, any network with a BGP configuration accepting a full feed from their upstream will have data on just about every entity connected to the Internet. How much you decide to use that information is up to you.

BGP information from your upstream generally has the following pieces of data within it:

• a network prefix and length
• the next hop for the prefix
• path of AS numbers through which the advertisement has passed (subject to some manipulation)
• information on the originating routing protocol
• community settings
• various other BGP settings

After making a decision based on all of these factors, the border router will insert a route into the routing table to reach the advertised network and after this point essentially the data is unused (aside from optionally being passed on to other border routers). There are so many more possibilities for this data however – you may use it for diagnosis of network issues or you may want to use it to visualise your BGP router’s view of the Internet (which is far more interesting).

Here we will use the Quagga routing suite to provide the BGP data. You are free to use Cisco or other proprietary equipment but I find having a server running Quagga to allow you a lot more flexibility, especially in this case of getting data out of the BGP system.

BGP table version is 0, local router ID is 202.4.236.8
Status codes: s suppressed, d damped, h history, * valid, > best, i - internal
Origin codes: i - IGP, e - EGP, ? - incomplete

   Network          Next Hop            Metric LocPrf Weight Path
* i3.0.0.0          202.4.236.9                    90      0 4826 703 2914 9304 80 i
*>                  114.31.193.74                  90      0 4826 703 2914 9304 80 i
*                   203.134.70.37                  10      0 9443 2914 9304 80 i
*> 4.0.0.0          114.31.193.74                  90      0 4826 3356 i
* i                 202.4.236.9                    90      0 4826 3356 i
*                   203.134.70.37                  10      0 9443 11867 7018 3356 i
*> 4.0.0.0/9        114.31.193.74                  90      0 4826 3356 i
* i                 202.4.236.9                    90      0 4826 3356 i
*                   203.134.70.37                  10      0 9443 11867 7018 3356 i

...

Total number of prefixes 275034

The above is a small snippet of BGP data, straight from the proverbial horse’s mouth (the BGP router). Immediately we can see that there is a lot of information for us to use – almost 300,000 unique network prefixes with associated paths through various entities identified by their AS numbers. With this path information we can build a visualisation of the entire Internet. It must be stressed though that this “view” of the Internet is only as seen from our network’s point of view and could be vastly different if generated from a different network. Due to the decentralised nature of the Internet, there is not one categorically “authoritative” view of it (even if you took the BGP data from a very well-connected network), but that doesn’t mean that our view is not useful!

Making the Data Usable

I started out with a copy of the full BGP feed from one of our border routers. Using Quagga’s BGPD you can output the entire feed (post-filtering of course) into a file by using the command-line `vtysh` tool:

# vtysh -c 'show ip bgp' > /data/bgp.txt

You will end up with the entire feed in Quagga output format in the file `/data/bgp.txt`, unfortunately not in a well-formatted data structure but in a format we can work with (the format shown in the excerpt above).

From here, we need to pass the file through a little bit of manipulation so that our graphing backend of choice can use it. I hacked up a very quick perl script which takes the output from the “show ip bgp” and attempts to break it down into unique paths between ASs. It strips out unnecessary headers and other text, then goes through each AS path and adds direct links between ASs to a hash table (so we can automatically remove doubled-up entries). It spits out the list of paths in a fairly Graphviz-centric format but can be easily adjusted to fit the requirements of most other graphing engines.

#!/usr/bin/perl

#use strict;
my %aslist;
my %asnodes;
my $numpaths = 0;

while (<STDIN>) {
	# Skip the first 5 lines of header data
	if ($. < 6) { next; }
	chomp;

	# Skip any blank lines
	if ( m/^$/ ) { next; }

	# Skip lines without an AS path
	if ( m/ 0 (i|e|\?)$/ ) { next; }
	unless (m/ 0 / ) { next; }

	# Skip the last summary line
	if ( m/^Total number of prefixes.*$/ ) { next; }

	# Grab just the AS path bit
	s/^.* 0 (.*) (i|e|\?)$/\1/;
	s/(\{|\})//g;
	s/,/ /g;

	# Turn the AS path string into an array
	my @path = split(' ', $_);
	$numpaths++;

	# Grab the path between each pair of nodes in the array
	$current = pop(@path);
	while ( $next = pop(@path) ) {
		# Don't include AS path prepends
		if ( $current == $next ) { next; }

		# Add both ASs to our global list of ASs
		$asnodes{$_}=1 foreach "$current";
		$asnodes{$_}=1 foreach "$next";

		# Add the path between ASs global hash, so we have no duplicates.
		if ( scalar($current) < scalar($next) ) { $aslist{$_}=1 foreach "$current:$next"; }
		else { $aslist{$_}=1 foreach "$next:$current"; }
		$current = $next;
	}
}

while (($key, $value) = each(%aslist)){
	$key =~ s/:/ /;
	print "$key\n";
}

Graphing Engines

This blog post was originally going to be a full-fledged wiki article, but while I originally thought it was a nifty idea I could knock over in a day or so, it turns out that graphing problems can be really, really hard. Who would have thought? So I spent a couple of days on this but didn’t end up getting the pretty yet functional graphs that I had hoped to get. I also stupidly neglected to take screenshots, but due to the graphing engines churning away on my computer in most cases due to the complexity of the data it wouldn’t have been nice to add insult to injury on my little workstation.

But all that is by the by. If this blog posting has piqued your interest in BGP data graphing at all, you’ll hopefully find my summary of a few of the better graphing engines below useful in some way. None of them suited my requirements perfectly but at a very least it is a start for what you could no doubt work on.

• Graphviz
  • very popular and flexible graphing library.
  • with the number of nodes and paths in this graph, it consumed too much memory and processing time to be effective
• Large Graph Layout (LGL)
  • very good at handling large graphs, not picky about directed/undirected and has a very simple input format
  • uses a separate java frontend for 2D visualisation after building its meta-data files, and produces VRML output for 3D visualisation (you must provide your own VRML frontend)
  • I found the 2D visualisation to be satisfactory but not very useful for this type of data. I haven’t had much success with VRML viewers with the 3D graph of this size.
• Walrus
  • entirely java which handles parsing as well as visualisation
  • requires the Java3D library
  • only accepts directed graphs and has a fairly strict input syntax
• Nodes3D
  • takes relatively simple LUA-files as input
  • quite flexible, and uses standard OpenGL libraries to perform the graphing
  • sadly has a hard-coded limit of a maximum of 2000 nodes, and doesn’t handle more nodes efficiently (with respect to memory allocation) if you alter the limit and recompile
• aiSee
  • A commercial program that seems to be quite well-rounded and professional-looking
  • Sadly only produces 2D visualizations, with 3D “imitation” with a fish-eye lens effect.
  • It was able to handle my large graph well (not blowing out memory usage) but the resulting visualization in force-directed mode was not sufficient
• Tulip
  • Relies heavily on QT4. If you are compiling from source grab a cup of coffee while it completes.
  • Has many visualisation possibilities, and can deal with up to one million elements
  • The 3D visualisations aren’t really suitable for this type of data.
• Lanet-Vi
  • Calculations and visualisation rendering is taken care of for you
  • Has probably the most lenient restrictions on input format
  • An easy option if you don’t want to spend days/weeks/months researching graphing, but would like something quickly
  • source code for local calculation is also available

Other Resources

If you are interested in graphs, the following will probably be interesting to you:

• http://www.google.com/Top/Science/Math/Combinatorics/Software/Graph_Drawing/
• http://www.visualcomplexity.com/
  • These guys host some pretty amazing graphs on their site, check it out!
• http://www.caida.org/research/topology/as_core_network/