Tools

Since BGP data is raw and can't be read without a tool to process and convert the information to human readable format, there are some tools which are capable of doing it. If my goal is to perform analyses of BGP then it is important to try out and understand these tools and their limitations. Quagga which is a routing suite software and some other routing suit softwares today use the MRT format to represent these raw data in readable form. MRT is basically, Multi-threaded Routing Toolkit which was developed to encapsulate,export, and archive routing information in a standardized data representation.

More about MRT can be followed here.

bgpdump:

This is a tool used created by RIPE network coordination center that converts BGP data to readable formats. This tool was written in C and uses the libbgpdump C library which was written by Dan Ardelean and later adopted by RIPE. After the installation of this software on my Ubuntu system,

i was presented with the main menu as such below after running the bgpdump command.

bgpdump version 1.4.99.14

Usage: bgpdump [-m|-M] [-t dump|-t change] [-O <output-file>] <input-file>

bgpdump translates binary MRT files (possibly compressed) into readable output

Output mode:

    -H         multi-line, human-readable (the default)

    -m         one-line per entry with unix timestamps

    -M         one-line per entry with human readable timestamps

    (there are other differences between -m and -M)

Common options:

    -O <file>  output to <file> instead of STDOUT

    -s         log to syslog (the default)

    -v         log to STDERR

Options for -m and -M modes:

    -t dump    timestamps for RIB dumps reflect the time of the dump (the default)

    -t change  timestamps for RIB dumps reflect the last route modification

Special options:

    -T         run unit tests and exit

So looking at the command line , it is possible to translate BGP data. I loaded sample BGP data for the Athens mobile community network which yielded the following output :

TIME: 07/24/13 19:00:00

TYPE: TABLE_DUMP_V2/IPV4_UNICAST

PREFIX: 10.0.10.0/24

SEQUENCE: 0

FROM: 10.255.9.4 AS172193

ORIGINATED: 07/24/13 14:39:56

ORIGIN: IGP

ASPATH: 172193 19601 14835 1286 18242

NEXT_HOP: 10.255.9.126

TIME: 07/24/13 19:00:00

TYPE: TABLE_DUMP_V2/IPV4_UNICAST

PREFIX: 10.0.11.0/24

SEQUENCE: 1

FROM: 10.255.9.4 AS172193

ORIGINATED: 07/24/13 15:05:08

ORIGIN: IGP

ASPATH: 172193 19601 14835 4758 15731 3341

NEXT_HOP: 10.255.9.126

TIME: 07/24/13 19:00:00

TYPE: TABLE_DUMP_V2/IPV4_UNICAST

PREFIX: 10.2.1.0/24

SEQUENCE: 2

FROM: 10.255.9.4 AS172193

ORIGINATED: 07/24/13 14:39:56

ORIGIN: IGP

ASPATH: 172193 19601 14835 1286 9533 16924

NEXT_HOP: 10.255.9.126

NB:This is just a fraction of the output.

So, looking at this output one can be able to deduce information like the Prefix, Originating AS, Timestamps, ASPATH and NEXT_HOP. Yet, to further analyse this information to fulfill my goals, this tool isn't complete. Could've been better if there was an interface to export this files to a database like mysql.

BGPtools

This is a very old tool that was created by the MIT in 2003 to part MRT -formatted BGP update dumps and provide a real-time analysis of BGP update data. This tool looked very promising and upon many tire of installing it into my Ubuntu 13.04, i was stuck at the ./configure phase since, it couldn't generate the make file for mysql++ which is a prerequisite . Upon going through many forums for answers, i just found of handful of people with the same problem while others solved it, same trick didn't apply to me. I hope to go deeper but for now i will look into other tools.

BGPlay

BGPlay is a java application that displays animated graphs of the routing activity of a certain prefix within a specified time interval.  This application is GUI in nature and its goal is to make the user understand the flow of BGP updates and it's effect of routing for a particular prefix. BGP gets it's data from Route Views project archive. 

LinkRank

Link-Rank is a large scale BGP tool meant for the visualization of BGP routing changes. Link-Rank gets it's BGP data from the Oregon Routeview project. This tool is no longer maintained as of 2011. The current release is 2.0 beta. This tool was written in java. After downloading the .jar file, i proceeded in trying to set it up without any documentations found and couldn't succeed. The issue is, in other to start using it, i needed to set the remote server path. I couldn't figure out how this works, and exactly what type of link was required there (the data format etc) because, i presented an online url to bgp ribs which didn't affect any changes in the tool. There isn't sufficient documentation of its use.

IBGPlay

Just like BGPlay, IBGPlay is a graphical tool that displays/animates BGP routing data which helps in diagnosing routing problems and anomalies. This tool can be good in identifying routes flapping, i haven't tested it yet since it requires me to do certain configurations which i don't yet have access to the devices.

BGP:Inspect

The goal of this project is to analyse BGP data from the RAW format to readable format and get very important information of it by pre-processing, indexing the data, removing redundancy and an interface for easy manipulation. This tool fetches for BGP raw data from the preset server and processes. BGP-inspect has it's own custom database which is known as BGPdb which is the core of the BGP-inspect sytem. It represents pre-processed database which is queries by the BGP-inspect interface. The BGPdb uses B-Tree indices for fast query performance, and does remove redundancy from BGP datasets like ASPATH, COMMUNITY, UPDATE messages which are often repeated.

BGP Analyses

A good routing protocol must be scalable and able to handle performance issues that arise. In this section, i will discuss about scalability and performance management wrt to BGP. All the routers in an AS are not required to participate in BGP but rather, a single router at the border is capable of handling BGP information with adjacent neighbors. It doesn't mean only a single router in an AS is capable of handling BGP updates and routing.Other routers within an AS can be set to act as multiple BGP gateway routers but however, these routers have to posses consistent BGP update information and accurate knowledge of the routes in their RIB.  Since, route processing uses the routers memory, the amount of information that the router receives and processes has to be managed for efficiency thus, incremental updates are used in BGP after the initial full update that routers exchange. This is to make sure that only what needs to be updated get updated to conserve bandwidth and power. To further ease the work of routers BGP implements route aggregation or summarisation whereby a group of networks could be represented as a single entity. For example :

12.19.0.0 is the IP block of an ISP, this ISP has about 100 networks (12.19.1.0 - 12.19.100.0) instead of this router advertising all these networks, just the block 12.19.0.0 in the routing update suffices.

In other to know an estimate amount of bandwidth information that is used during the initial update of BGP, lets assume that the total number of routes in the network is N, the mean of the AS path distance is M and the total number of the A. Assuming a uniform distribution, the worst case amount of bandwidth consumed is  O(N + M * A). 

BGP Packet Structure

BGP messages are processed only when they have been entirely received. The smallest messages that can be sent with BGP is 19 octets and the maximum being 4096 octets. 19 octets is the minimum because it is a BGP message without any information other than the header details. Further more, it will be clear where all these 4096 octets are used.

BGP PACKET HEADER

The BGP packet header consist of 3 items which are :-

note : the integer octets are unsigned.

Marker : The marker uses 15 octets. This field's information is valuable for the detection of un-synchronized BGP peers and also for BGP message authentication.

Length : The Length uses 2 octet unsigned integer which indicates the message length including the header(marker,length,type). It helps for the possibility of the  transport level stream to know the net message which is always between the boundaries of 19-4096.

Type : The Type is 1 octet which indicates what type if BGP message is transmitted. That brings us to the types of BGP messages which are OPEN, UPDATE, NOTIFICATION, KEEPALIVE.

OPEN MESSAGE FORMAT


The open message is the first message transmitted when the connection between two BGP peers have been established. If the OPEN message sent by one of the other BGP peers is accepted by the receiver, then KEEPALIVE message is sent to the source to confirm the OPEN message. As said earlier this is the first message.After this process so can other BGP message types be transmitted like UPDATE,EXCHANGE,NOTIFICATION which shall be seen later in detail. The OPEN message format consist of 5 fields added to the header which sums up to 25 octets with the OPEN message having 6. The fields are:

Version : 1 octet. Displays the current BGP protocol version number.
My Autonomous Systems : 2 octet. Contains the AS number of the source.
Hold Time : 2 octet. This is the holdtime "max sec: that may elapse upon receipt of successful messages (KEEPALIVE, UPDATE, etc)
Auth Code : The type if authentication used.
Auth Data : This is the authentication data sent it has no fixed octets but can be obtained with the subtraction of (25(which is the standard size of a message) + version + my autonomous system + holdtime + authcode ) with the current octet value.


UPDATE MESSAGE FORMAT

This is the message BGP uses to transmit information  of new and existing routes to other BGP peers. This is the info that can be used for graph creation and best path selection between different autonomous systems. This graph gives a clear view of the network in addition for the 19 fixed header size, the update message packet consist of 5 fields.

Unfeasible Routes Length : 2 octets. The total length of the Withdrawn Routes field in octets
Withdrawn Routes: This is a variable length field that contains a list of IP address prefixes for the routes that are being withdrawn from service.
Total Path Attributes Length : 2 octets. Indicates the total length of the path attribute field.
Path Attributes : 2 octets. Discussed later.
Network : These are the networks described in the path attributed can be one or more networks.

The update message length is = 19 + total path + 4 * #Networks


KEEPALIVE MESSAGE FORMAT

This just consist of the message header and uses no TCP based keep alive mechanism to ensure if the links between the peers are active.


NOTIFICATION MESSAGE FORMAT

This message is sent when an error is detected and the BGP session is immediately terminated after the transmission has taken place. It consist of 3 fields in the message format :-

Error Code : 1 octet. This is the type of error notification
Error  Subcode : 1 octet. This is the more specific error classification. Each type of BGP message like UPDATE, OPEN, has different types of errors which are regarded as error subcode.
Data : This contains the message of reason why the error occurred.


PATH ATTRIBUTES

These consist of optional ad mandatory attributes that all BGP systems must implement, The well known attributes are mandatory. Example of these well known attributes are :

ORIGIN : The source of the information with values of 0-2 having different source meanings.

AS_PATH : These are the ASes that must be traversed to reach the networks listed in the update message.

NEXT HOP : As next hop means, this is the gateway of the border router that is to be used as the next hop to other networks which are listed in the update message. The gateway must belong to the same AS the BGP that advertised it.

UNREACHABLE : This is as notification to the other BGP peers that the previously advertised route is now unreachable.

BGP FINITE STATE MACHINE

In other for they to be decision making between peers, each BGP peer uses a finite state machine that consist of six states. This is to avoid scenarios whereby, a BGP peer receives both incoming and outgoing connections from other peers resulting in the creation of 2 FSM instead of one. These states are, Idle, Connect, Active, OpenSent, OpenConfirm, Established. Below is a diagram that shows flow of these states.

1. IDLE: State when BGP peer refuses any incoming connections.
2. CONNECT: State in which BGP peer is waiting for its TCP State in which BGP peer is trying to acquire a connection to be completed.
3. ACTIVE: State in which BGP peer is trying to acquire a peer by listening and accepting TCP connection.
4. OPENCONFIRM: BGP peer is waiting for KEEPALIVE or NOTIFICATION
5. OPENSENT: BGP peer is waiting for OPEN message from its peer message from its peer. 
6. ESTABLISHED: BGP peer connection is established and exchanges UPDATE, NOTIFICATION, and KEEPALIVE messages with its peer.

Extracts from rfc 1163, 1771,1774.4271

An Introduction to BGP

BGP that stands for border gateway protocol came into existence because of the limitations faced by EGP which stands for the exterior gateway protocols. EGP was a type of protocol used for inter autonomous system routing but now, it is the TYPE of exterior gateway protocols. EGPs are ISP level routing protocols, not strictly ISP but saying this is just to give the idea of how huge it is. Other huge companies also do use this routing protocol. As defined in the RFC 4271, BGP is an Inter-Autonomous meant to exchange reachability information with other systems.An autonomous system could be a set of routers under a single administration.

These single ASes could use different interior gateway protocols (IGP) for communication within it's AS like OSPF, EIGRP, RIP and static routes. But for routing information to be exchanged across different autonomous systems,  BGP is THE routing protocol.The BGP comes up with a reachability graph provided by it's speaking system that includes information of the list of all autonomous systems reached.The figure below is a trivial view of the internet with different Autonomous Systems at different locations in the world. These ASes make routing decisions based on BGP and it's metrics.

About me

I am a current computer science student at the University of Antwerp majoring in distributed systems and networks who presently finds a kind interest in BGP (border gateway protocol). Just the thought of a routing protocol this big and important gives me the motivation to study it, analyse it and provide my own positive contribution towards it.
From this moment of writing, i am about to take a deep dive into it's RFCs, to help me get a detailed view of it. Hope everything you find here is useful for a start and please don't hesitate to comment and leave your opinions.