BGP4 -  Border Gateway Protocol( version 4)

Motivation

• Managing inter-connectivity between large number of networks( providers and customers).
• Improvment over the earlier BGP versions - CIDR and supernettting
• Policy - Based Routing
• Mainly concentrates on the reachability of networks based on certain policy constraints, while IGP focuses on the efiiciency of network reachability.

Basic Operation

• BGP runs over a TCP( port 179)

 
• A BGP Speaker( one hwich runs BGP ) has two types of peers ( conections )

EBGP and IBGP. A peer connection to a BGP speaker in other AS is a EBGP connection, while a peer connection with a BGP speaker in the same AS is a IBGP connection.
 
• EBGP connections are used to exchange network reachability information between ASs.

• IBGP connections are used to distribute between all the BGP speakers in the AS:

The routes received by each BGP speaker through EBGP connections. Generally the routers running IBGP are connected by a full mesh (n*n). An alternative way to do this is to use a route-reflector, which follows a  hub-and-spoke approach.
 
• BGP Connection Initiation:

A BGP speaker initiates a connection to other BGP speaker by sending a OPEN message. A BGP version to be used is negotiated first, this may involve closing of a BGP connection and reinitiating a new connnection. The next  info to be decided is the HOLDTIME value which is the minimun of the two values exchanged. The AS Number info in the OPEN packet is used to decide  whether the connection is a EBGP connection or a IBGP connection. Additonal authnetication is also possible using the OPEN message ( MD5 is used ). When  the BGp speaker which initiates the connections receives a KEEPALIVE message then the connetions state is ESTABLISHED. From now on the both can exchange route information using the UPDATE messages.

• Exchange of Routing Inforamtion:

A route inforamtion is exchanged using the UPDATE packets. The route information consists of two things
 (1) Advertisement of a route to new Network.
 (2) Withdrawl of routes to networks.

A route inforamtion consists of various attrubutes which will describe the route to the network advertised. The various attributes and their usage are
described later. Only one route/path information can be advertised in a single UPDATE packet. But many routes can be withdrawn using a single UPDATE packet.
The networks advertised are called NLRI( Network Layer Reachability Information).

Each BGP speaker has a Routing Inforamtion Base ( RIB ), where the it stores the routes it received from other BGP speakers. There are three types of RIBs in a BGP speaker

(1) Adj-RIBs-In :
Contains the routing info received from all the BGP speakers. A decision process is applied to the routes in this RIB to construct the local RIB. There is a Adj-RIBs-In assocaited with each BGP peer connection(?).

(2) Local-RIB:
Contains the routes that are used by the local BGP process.

(3) Adj-RIBs-In :
Contains list of routes that are to be sent to the BGP speakers peers.

Message Types

(1) OPEN

The OPEN message is sent after the tcp connection is successful. the OPEN message contains the version number, AS number, hold timer, BGP identifier and other optional parameters. the BGP version to be used is decided by exchanging the OPEN pmackets. the The hold timer is decided as the smallest configured value in both the BGP speakers. The OPEN message may alos contain the authentication information.

 (2) KEEPALIVE

Once the BGP peer connection is established the connection is maintained by sending the keepalive messages. There are the Hold Timer and the Keep Alive timer which are maintained regarding the sending and receiving of KeepAlive Packets.

 (3) UPDATE

The Update packets are sent to advertize or withdraw routes to the peer. In each update packet only one route is advertised, each route has a set of PATH Attributes associated with it. But many routes can be withdrawn using the Update packet.

A Notification packet is sent whenever a error occurs. the various types of errors are
  (a) Message Header Error
  (b) OPEN Message Error
  (c) UPDATE message Error
  (d) HOLD Time expired
  (e) FSM Error
  (f) Cease
     Along with the error code there is a error subcode field and a optional data field.

Path Attributes

The various attrubutes arecan be classified as below
 1.    Well-Known Mandatory

• must be sent with all routes
• must be processed in all the BGP receivers

•   need not be sent along with all the routes
•   need to be processed in all the BGP receivers

•   may or may not be implemneted in BGP
•   if the route is to be sent to other AS then the optional transitive attributes are set

• may or may not be implemneted in BGP
• these attributes are not sent to other ASs

The various path attributes are discussed below

 (1) ORIGIN
     It is a wellknown mandatory attribute and it indicates from where the route is be generated - IGP, EGP and from other sources.

 (2) AS_PATH
     The AS_PATH attribute is a wellknown mandatory attribute that
     should be send to along with the route. It indicates the list of Autonomous
     systems through which I can reach destination network. the list of AS is
     either represented as a sequence or a set. A sequence can be used to list the
     path taken. A set is used if the exact path is not known but know the list of
     AS through which we can reach the detination network.

 (3) NEXT_HOP
     The NextHop attribute is used to indicate the border router to
     which the packet has to be sent.

 (4) Multi-Exit-Disc (MED)
     The MED is used by routers to choose among the multiple entry
     points to a AS. By setting the MED properly, we can direct the OUT-BOUND traffic
     accordingly.

 (5) LocalPreference
     The local preference is used within the AS to choose between
     multiple routes to same destination. It is used to direct the IN-BOUND traffic
     accordingly.

 (6) AtomicAggregate
     The atomic attribute is set if the route advertised is an aggreate
     of many more specific routes.

 (7) Aggregator
     It is the router which last performed the aggregation of routes.
 

 There are various other optional attributes like communities, etc.
 

Finite State Machine(FSM)

The BGP process goes through various states and the state changes according to
various events.

• When a BGP process is initialized it goes into the IDLE state. In the IDLE state it does not do anything. In order for the BGP process to go from the IDLE state to ACTIVE state or Connect State we have to issue a START event.

• In the CONNECT state the BGP process tries to initiate a transport  connection to its configured peers. If the transport connection succeds then it goes to  the OpenSent state, where it sends a OPEN message to the peer. If the transport connect fails then it resets the  ConnectionRetry timer to a particualr value and goes to the Active state.

 
• Whenever the ConnectionRetry timer fails then it goes back to the Connect  state where it tries to initiate a transport connection.

 
•  In the Active State the BGP process listens to the transport connections  from the peer. If the connection suceeds then the it goes to the OpenSent State.

• In the OpenSent State if the BGP process receives a OPEN message from the  peer then it goes to the OpenConfirm State. In the OpenConfirm state the BGP process sends a KeepAlive message.

 
•  When a BGP process is in the OpenConfirm State and it receives KeepAlive message then it goes to Established state. Only in the Established state can  we sent a update packet describing the routing information. During the  exchange of Open messages the BGP version and the hold timer values are  decided.

 
•  If in Established state, it receives a Notificcation packet then it goes to  the idle state. When in the Established state if the HoldTimer expires then  sends a notification saying that the HoldTimer Expired and goes to the Idle  state. If the KeepAlive Timer expires then sends a keepalive message to the  peer.

Decision Process

A BGP Router is configured with a Policy Information Base and the decision process involves the information in the PIB. The decision process operates on
the Adj-RIBs-In, Local RIB,  Adj-RIBs-Out. The Decision process follows three phases
 

• In Phase one, the routes in the Adj-RIBs-In are selected and given a  particular Local Preference Value before sending it to its internal peers.

• In Phase two, the routes are selected to fill the Local RIB, the routes in  the Local RIB are used by the BGP Process itself.

• In Phase three, the routes to be sent to its exteral peers are processed and  stored in the Adj-RIBs-Out.

General Configuration of BGP for Networks

( Soon.............)