Wednesday, March 23, 2011

How bgp works

Networking 101: Understanding BGP Routing
The Border Gateway Protocol is the routing protocol of the Internet. BGP itself isn’t too complex, but the concepts behind autonomous-system-based routing can be strange to newcomers. In this article we hope to provide a short overview of how BGP works, along with the problems it solves and causes.
From last week’s overview of Internet routing, you should realize that routing in the Internet is comprised of two parts: the internal fine-grained portions that are managed by an IGP such as OSPF, and the interconnections of those autonomous systems (AS) via BGP.
Everyone on the Internet has at least one unique AS number, and they use BGP to advertise their networks to their peers. BGP is a path-vector protocol, because it advertises the paths required to get to a certain destination. BGP does not say anything about how a packet will get routed within the AS, nor does it know about the entire network as OSPF does. BGP can be called a distance-vector protocol, because it’s similar, excluding a few twists.
Related Articles
• Networking 101: Understanding RIP Routing
• Networking 101: Understanding OSPF Routing
• Networking 101: Understanding Internet Routing and Peering
BGP itself is a Layer 4 protocol that sits on top of TCP. BGP is much simpler than OSPF, because it doesn’t have to worry about the things TCP will handle. This works because BGP is very connection-oriented anyway, since it requires two manually configured peers, who configure their routers then exchange routes. BGP peers (neighbors) will generally be directly connected, but some masochists like to set up BGP sessions between multi-hop peers—which is okay, since BGP uses TCP (port 179) and doesn’t rely on broadcasts or link-local multicast.
BGP-4 (BGP-3 didn’t do CIDR) updates are packets comprised of the following: a network, a subnet, and some attributes. We make routing decisions based on the attributes, mainly the AS-Path attribute. A BGP update could contain the following information: “I can get to network 1.1.1.0/12 via AS numbers 8,19,2000,5.” A very important aspect of BGP to understand is that the AS-Path itself is an anti-loop mechanism. Routers will not import any routes that contain themselves in the AS-Path.
If you, as a router, import a route and then advertise it to one of your peers, you must prepend your own AS to the AS-Path before announcing the route. Naturally, this provides a “path” that one can take, as the route is advertised further from the source AS. Generally, but not always, routers will choose the shortest path to an AS. BGP only knows about these paths based on updates it receives. Unlike RIP (that distance-vector protocol) BGP does not broadcast its entire routing table. At boot, your peer will hand over their entire table, but after that everything relies on updates received.
Route updates are stored in a Routing Information Base (RIB). A routing table will only store one route per destination, but the RIB usually contains multiple paths to a destination. It is up to the router to decide which routes will make it into the routing table, i.e. which paths will actually be used. In the event that a route is withdrawn, another to the same place can be taken from the RIB. The RIB is only used to keep track of possible routes we could use. We never advertise a route to a peer that we aren’t using, because that would be false information. We only advertise what we have in our routing table. If a route withdrawal is received and it only existed in the RIB, we don’t need to send an update to our peers, instead we silently delete it from the RIB. The RIB entries never time out, they stick around until we think that route is no longer valid.
A great deal of routing on the Internet is said to be policy-based. Sometimes you’ll have an expensive link that you only want to use when necessary, or perhaps you’ll have a link that you can use to send traffic only to certain parties. Many times the BGP attribute “Community” will be used to identify a set of routes. If you want to let your neighbor know some secret information about a route, you can set a community number before you export those routes. These numbers are completely arbitrary, so whatever you send must be agreed upon a priori to have some sort of meaning.
Another important BGP attribute is the Multi-Exit Discriminator (MED). This is used to tell a remote AS that we prefer a specific exit point, even though we may have many. This is very important in iBGP, the IGP version of BGP that will be covered next time.
To get a true sense of how BGP works, it’s important to spend some time talking about the issues that plague the Internet.
First, we have a very big problem with routing table growth. If someone decides to deaggregate a network that used to be a single /16 network, they could potentially start advertising hundreds of new routes. Every router on the Internet will get every new route when this happens. People are constantly pressured to aggregate, or combine multiple routes into a single advertisement. Aggregation isn’t always possible, especially if you want to break up a /19 into two /20’s that will be geographically separate. Routing tables are approaching 200,000 routes now, and for a time they were appearing to grow exponentially.
Second, there is always a concern that someone will “advertise the Internet.” If some large ISP’s customer suddenly decides to advertise everything, and the ISP accepts the routes, all of the Internet’s traffic will be sent to the small customer’s AS. There’s a simple solution to this, and it’s called route filtering. It’s quite simple to set up filters so that your routers won’t accept routes from customers that you aren’t expecting, but many large ISPs will still accept the equivalent of “default” from peers that have no likelihood of being able to provide transit.
Finally, we come to flapping. BGP has a mechanism to “hold down” routes that appear to be flaky. Routes that flap, or come and go, usually aren’t reliable enough to send traffic to. If routes flap frequently, the load on all Internet routes will increase due to the processing of updates every time someone disappears and reappears. Dampening will prevent BGP peers from listening to all routing updates from flapping peers. The amount of time one is in hold-down increases exponentially with every flap. It’s annoying when you have a faulty link, since it can be more than an hour before you can get to many Internet sites, but it is very necessary.
This has been a very quick discussion of BGP; enough to get you thinking the right way about the protocol but is by no means comprehensive. Spend some time reading the RFCs if you’re tasked with operating a BGP router: your peers will appreciate it.
In a Nutshell
• BGP is the path-vector protocol that provides routing information for autonomous systems on the Internet via its AS-Path attribute.
• Peers that have been manually configured to exchange routing information will form a TCP connection and begin speaking BGP. There is no discovery in BGP.
• Medium-sized business usually get into BGP for the purpose of true multi-homing for their entire network.