The most common Exterior Gateway Protocol protocol in
use on the Internet is the Border Gateway Protocol (BGP), ensuring that packets
get to their destination network regardless of current network conditions.
the BGP algorithm provides great network stability, guaranteeing that if
BGP routers can quickly adapt to send packets through another
following subsections provide information on how
BGP was invented, how BGP works, the BGP algorithm,
BGP was invented. BGP
was initially created in three different implementations. Then, in a
standard Internet approach, they were used together to show that separate
of the protocol could interoperate without problems.
Lougheed of Cisco systems developed a proprietary version of BGP for Cisco router
- Jeff Honig from Cornell
University and Dennis Ferguson from the University of Toronto developed a BGP
called gated to
run on Unix computers, enabling Unix machines to become BGP routers, and
then put the code in the public domain for others to use.
Rekhter from the IBM Thomas J. Watson Research Center wrote a BGP version for
BGP works. When
a BGP router first comes up on the Internet, either for the first time or after
being turned off, it establishes connections with the other BGP routers
with which it directly communicates. The first thing it does is download the
entire routing table of each neighboring router. After that it only exchanges
update messages with other routers.
BGP routers send and receive update messages to indicate a change
in the preferred path to reach a computer with
a given IP address. If the router decides to update
its own routing tables because this new path is better, then it will subsequently
propagate this information to all of the other neighboring BGP routers to which
it is connected, and they will in turn decide whether to update their own tables
and propagate the information further.
uses the TCP/IP protocol on port 179 to establish
connections. It has strong security features, including the incorporation of
a digital signature in all communications between BGP routers.
BGP router contains a Routing Information Base (RIB) that contains the routing
information maintained by that router. The RIB contains three types of information:
- Adj-RIBs-In. The
unedited routing information sent by neighboring routers.
- Loc-RIB. The actual
routing information the router uses, developed from Adj-RIBs-In.
- Adj-RIBs-Out. The
information the router chooses to send to neighboring routers.
routers exchange information using four types of messages:
Used to open an initial connection with a neighboring router.
- Update. These messages
do most of the work, exchanging routing information between neighboring routers,
and contain one of the following pieces of information.
- Withdrawn routes.
The IP addresses of computers that the router no longer can route messages to.
A new preferred route for an IP address. This path consists of two pieces of
information -- the IP address, and the address of the next router in the path
that is used
to route messages destined for that address.
Used to indicate errors, such as an incorrect or unreadable message received,
and are followed by an immediate close of the connection with the neighboring
Each BGP router sends a 19 byte Keepalive message to each neighboring router to
let them know that it is still operational about every 30 seconds, and
no more often than every three seconds. If any router does not receive a Keepalive
message from a neighboring router within a set amount of time, it closes its connection
with that router, and removes it from its Routing Information Base, repairing
what it perceives as damage to the network.
Routing messages are
the highest precedence traffic on the Internet, and each BGP router gives them
first priority over all other traffic. This makes sense -- if routing
can't make it through, then nothing else will.
BGP algorithm. The
BGP algorithm is run after a BGP router receives an update message from a neighboring
router, and consists of the following three steps performed for each IP address
If the path information for an IP address in the update message is different
from the information previously received from that router, then the Adj-RIBs-In
is updated with the newest information.
If it was new information, then a decision process is run that determines which
BGP router, of all those presently recorded in the Adj-RIBs-In database,
has the best
routing path for the IP address in the update message. The algorithm is not mandated,
and BGP administrators can set local policy
the decision process such as how long it takes to communicate with each
neighboring router, and how long each neighboring router takes to communicate
in the path. If the best path chosen as a result of this decision process is
different from the one currently recorded in the Loc-RIB database, then
the database is
If the decision process found a better path, then the Adj-RIBs-Out database is
updated as well, and the router sends out update messages to all of its
BGP routers to tell them about the better path. Each neighboring
router then runs their own BGP algorithm in turn, decides whether or not to update
their routing databases, and then propagates any new and improved paths
to neighboring routers in turn.
of the other important functions performed by the BGP algorithm is to eliminate
loops from routing information. For example, a routing loop would occur when
router A thinks that router B has the best path to send messages for some computer
and B thinks the best path is through C, but C thinks
the best path is back through A. If these sort of routing
loops were allowed
to happen, then any message to that computer that passed through routers
A, B, or C would circulate among them forever, failing to deliver the message
up increasing amounts of network resources. The BGP algorithm traps and stops
any such loops.
BGP protocol has been periodically revised, and is now at version 4.
Each version can support all earlier versions. Different BGP routers may run
of BGP, so the protocol includes the following clever method for
ensuring that different versions can communicate. When one BGP router tries
time with a second BGP router, it sends it an Open message including the highest
version of BGP that it supports. If the second router cannot support that
it sends back a Notification message with the highest version that it can
support. The first router then opens a connection using that lower version,
the two routers can then communicate at the highest version of BGP they both
information. Request For Comment documentation on BGP can be found below:
1265; Rekhter, Y.; BGP Protocol Analysis, October 1991.
1266; Rekhter, Y.; Experience with the BGP Protocol; October 1991.
1771; Rekhter, Y.; Li, T.; A Border Gateway Protocol 4 (BGP-4), March
1772; Gross, P.; Rekhter, Y.; Application of the Border Gateway Protocol
in the Internet, March 1995.