BGP

Super Sparrow makes use of BGP -- Border Gateway Protocol -- to determine which point of presence a client should contact. More specifically, Super Sparrow uses BGP-4 -- Border Gateway Protocol version 4 -- a routing protocol, as defined in RFC 1773. BGP is used to communicate routing information between different providers on the Internet and for this reason reflects the path that traffic will take from a given point on the Internet.

Routing Protocols

A route is a a set of addresses and the next hop used to send traffic to the addresses. A router is nominally a host that has more than one network interface and makes decisions about to which interface a given packet should be sent. As network topologies become more complex, the number of different routes increases, as does the frequency of routes changing. For this reason it is useful for routers to have a method for dynamically updating routes as the network topology changes, that is, as other routers come and go from the network either because of administrative changes or failures of routers or links between routers.

Routing protocols are a mechanism for routers to communicate routes with each other. Routers that communicate routes with each other are referred to as peers. When routes are sent between routers they contain information in addition to the addresses that the route covers and the next hop for this traffic. The additional information may be used to expire the route and to determine the cost of the route relative to other routes. When a router sends such a route it is said to be advertising. A route advertisement can be seen as a promise to deliver traffic for a given set of addresses. Advertising routes that cannot be satisfied leads to either routing loops or black-holing. A routing loop refers to traffic bouncing between routers until the maximum hop count is reached. Black-Holing refers to receiving traffic and then discarding it. In either case the addresses covered by the route is effectively removed from the network.

A prefix is a set of network addresses that a given route covers. In routing protocols this is given as either a classful network or in the case of more recently developed routing protocols a CIDR network. Classless Inter-Domain Routing (CIDR) is defined in RFC 1519. CIDR networks allow networks to be defined as a network address and a netmask, enabling more flexible division of networks than classful routing.

When peers are configured to communicate routes with each other they are said to have a session running. When the session is established the routers advertise routes to each other and each router uses this information to determine the best route for each prefix that has been advertised to it or is advertised by it. When a session goes down, either administratively or because of a timeout, the prefixes advertised by the peer in question are removed, enabling the network to adapt to failures.

Routing protocols are divided into two types: Interior Gateway Protocol (IGP) and Exterior Gateway Protocol (EGP). An IGP is concerned with managing routes within a single network, ensuring that each point of the network is able to get to all other points in the network. An EGP communicates information about which addresses are within a network or may be accessed through a network. When BGP is used to communicate routes between different networks on the Internet, it is being used as an EGP.

Autonomous Systems

When networks communicate routes using BGP, individual networks are identified using an Autonomous System (AS) Number as defined in RFC 1930. Each route communicated using BGP contains an AS path, an ordered list of ASes that the route has been advertised by.

As an example suppose that there are three networks, imaginatively named Network A, B and C. These Networks have the AS numbers 64600, 64601 and 64602 respectively. Networks A and C are each directly connected to B. A border router is a router on the edge of a network that communicates directly with routers on other networks. BGP peering sessions are run between border routers in Networks A and B and Networks B and C. There is no direct link between Networks A and C, rather these networks see routes to each other that transit through Network B. This given, the AS path on a router in Network A for a prefix advertised by Network C would be 64601 64602, showing that the route originated from AS64602 and was transited through AS64601. In other words, traffic will travel through Network B to get to its ultimate destination, Network C.

Finding The Peer Closest to a Client

Now suppose that a provider has two Points Of Presence (POPs), one on each of Network A and C, called POP X and Y respectively. By obtaining BGP information from upstream networks and the other POP it is possible for a POP to determine which POP is closest to a given IP address. That IP address could be that of a client wanting to access a service available on both POPs. The result could be used to determine which POP the client should connect to.

To do this each POP has an AS Number, this may be from the range 64512 to 65535, which is reserved for private use by the Internet Assigned Numbers Authority (IANA) as described in RFC 1930. All ASes used in theses examples are from this range.

Each POP sets up a BGP session with its upstream network or networks. In this example POP X will have a BGP session with a router in Network A. Similarly for POP Y and Network C. As the POPs will not be originating any valid routes it is important that the POPs are configured not to send any routes to the upstreams and the upstreams are configured not to accept any routes from the POPs. This is referred to as filtering. Once these BGP sessions are established each POP has a view of all the routes that its respective upstream has. This is extendable to POPs with multiple upstreams by the POP in question establishing BGP sessions with each of its upstreams. By establishing a multi-hop BGP Session between POPs X and Y is is possible for each POP to see the view of the network that POP has, and in turn the view that POP's upstream has.

If the router running the BGP sessions to Network A from POP X is queried for the prefix used to route traffic to an address in Network C then there are two probable answers; A prefix with the AS path 64600 64601 64602 as learned through the BGP session with Network A, or a prefix with AS path 64702 64602 as learned through the multi-hop BGP session with POP Y. The latter prefix should be preferred as it has a shorter AS path, though it is possible to change this using weights. As the preferred path contains the AS number of POP Y, this must be closer to the the queried address in terms of the BGP routing topology. This means that if the AS number for one of the POPs appears in the AS path for a preferred prefix then the corresponding POP must be closer to the addresses covered by the prefix that the POP making the request. If the AS numbers of multiple POPs appear in the AS path then the last POP in the AS path must be closest, as AS numbers at the end of the AS path are closer to the origin than those at the beginning.

Super Sparrow and Route Servers

Super Sparrow accesses BGP information by querying routers or a host running a routing daemon for the preferred prefix covering ip address. More information on how this is done, and supported routers and routing daemons please see Route Servers.

References

Please see references.

Copyright © 2000 Horms

Last Updated: Thu Nov 13 16:27:49 2003