Transcript BGP messages

•BGP overview
•BGP operations
•BGP messages
•BGP decision algorithm
•BGP states
Internet Routing Protocols
• Routing protocols in Internet are arranged in a
hierarchy that involves two types of protocols:
IGP
- Interior Gateway protocol
EGP
- Exterior Gateway protocol
• For routers to communicate within
an AS (autonomous system)
• Relies on IP addresses to construct
paths
• Routing Information Protocol (RIP)
• Open Shortest Path First (OSPF)
• For router to communicate among
different Ass
• Relies on AS numbers to construct
AS paths
• Border Gateway Protocol (BGP)
BGP overview
• Currently in version 4.
• InterAS (or Interdomain) routing protocol for
exchanging network reachability information among
BGP routers.
• Uses TCP on port 179 to send routing messages.
• BGP is a distance vector protocol, but unlike in RIP,
routing messages in BGP contain complete routes.
• Network administrators can specify routing policies.
BGP overview (cont.)
Relationship with IGP
• BGP carries full Internet routing table
• IGP’s are used to carry next hop and interior
network information.
• Routes are never redistributed from BGP into
IGP, and vice versa.
• Recursive route lookup
BGP operations
• Two BGP routers exchanging information on a connection are called
peers.
– Initially, BGP peers exchange the entire BGP routing table.
– A BGP router retains the current version of the entire BGP routing
tables of all of its peers for the duration of the connection.
– Subsequently, only incremental updates are sent as the routing
tables change.
– Keepalive messages are sent periodically to ensure that the
connection between the BGP peers is alive.
– Notification messages are sent in response to errors or special
conditions.
BGP operations (cont.)
• A route is defined as a unit of information that pairs a
destination with the attributes of a path to that destination.
• Routes are stored in the Routing Information Bases (RIBs).
• A RIB within a BGP router consists of three distinct parts:
– Adj-RIBs-In: contains unprocessed routing information that has
been advertised to the local BGP router by its peers;
– Loc-RIB: contains the routes that have been selected by the local
BGP router's Decision Process;
– Adj-RIBs-Out: organizes the routes for advertisement to specific
peers by means of the local speaker‘s UPDATE messages.
eBGP and iBGP
• BGP can also be used within an AS. BGP connections inside an AS are
called internal BGP (iBGP), and BGP connections between different Ass
are called external BGP (eBGP).
R2
iBGP
R3
AS2
eBGP
eBGP
R1
R4
AS1
AS4
• The purpose of iBGP is to ensure that network reachability information is
consistent among multiple BGP routers in the same AS.
BGP messages
• BGP header format
0
16
24
31
Marker
Length
Type
– Marker: authenticates incoming BGP messages or detects loss of
synchronization between a pair of BGP peers.
– Length: indicates the total length of the message in octets, including the
BGP header.
– Type: indicates the type of the message.
OPEN message
0
8
16
24
31
Marker
Length
Type=OPEN
My autonomous system
Version
Hold time
BGP identifier
Optional parameter length
Optional parameters
• Version: the protocol version number of the message.
• My autonomous system: The AS number of the sending router.
• Hold time: the number of seconds between the transmission of successive
KEEPALIVE messages.
• BPG identifier: the sending BGP router.
• Optional parameter: a list of optional parameters, encoded in TLV structure.
KEEPALIVE message
0
8
16
24
31
Marker
Length
Type=KEEPALIVE
• If the hold time is zero, then KEEPALIVE messages
will not be sent.
NOTIFICATION message
0
8
16
24
31
Marker
Length
Error subcode
Type=NOTIFICATION
Error code
Data
• Error code: the type of error condition.
• Error subcode: specific information about the nature
of the error.
• Data: the reason for the notification.
UPDATE message
BGP header
Unfeasible routes length (2 octets)
Length (1 octet)
Prefix (variable)
……
Length (1 octet)
Prefix (variable)
Withdrawn routes (variable)
Attribute type Attribute length Attribute value
Total path attribute length (2 octets)
……
Path attributes (variable)
Attribute type Attribute length Attribute value
Network layer reachability information (variable)
Length (1 octet)
Prefix (variable)
……
Length (1 octet)
•
•
•
•
•
Prefix (variable)
Unfeasible routes length: the total length of the withdrawn routes field in octets.
Withdrawn routes: a list of IP address prefixes for the routes that need to be
withdrawn from BGP routing tables.
Total path attribute length: the total length of the Path Attributes field in octets.
Path attributes: a variable length sequence of path attributes.
NLRI: a list of IP prefixes.
Update message (cont.)
Attribute type
OT P E
0
Attribute length Attribute value
Attribute type code
• Attribute flag (1 octet):
– O bit: attribute is optional (O=1), or required (O=0).
– T bit: an optional attribute is transitive (T=1), or non-transitive (T=1).
– P bit: the information in the optional transitive attribute is partial (P=1), or
complete (P=0).
– E bit: the attribute length is two octets (E=1), or one octet (E=0).
Update message (cont.)
• Attribute type code:
– ORIGIN (type code 1): defines the origin of the NLRI.
– AS_PATH (type code 2): lists the sequence of Ass that the route have traversed
to reach the destination.
– NEXT_HOP (type code 3): defines the IP address of the border router that
should be used as the next hop to the destination listed in the NLRI.
– MULTI_NEXT_DISC (type code 4): discriminates among multiple entry/exit
points to a neighboring AS and gives a hint to the neighboring AS about the
preferred path.
– LOCAL_PREF( type code 5): informs other BGP routers within the same AS
of its degree of preference for an advertised route.
– ATOMIC_AGGREGATE (type code 6): informs other BGP routers that it
selected a less specific route without selecting a more specific one that is
included in it.
– AGGREGATOR (type code 7): specifies the last AS number that formed the
aggregate route followed by the IP address of the BGP router that formed the
aggregate route.
The BGP decision algorithm
• After BGP router receives updates about different
destinations from peers, the protocol will have to
decide which paths to choose in order to reach a
specific destination.
• BGP will choose only a single path to reach a specific
destination.
• The decision process is based on different attributes,
such as next hop, local preference, the route origin,
and so on.
• BGP will always propagate the best path to its
neighbors.
How BGP selects a Path
1.
2.
3.
4.
If NextHop is inaccessible do not consider it.
Prefer the largest Weight.
If same weight prefer largest Local Preference.
If same Local Preference prefer the route that the specified
router has originated.
5. If no route was originated prefer the shorter AS path.
6. If all paths are external prefer the lowest origin code
(IGP<EGP<INCOMPLETE).
7. If origin codes are the same prefer the path with the lowest MED.
8. If path is the same length prefer the External path over Internal.
9. If IGP synchronization is disabled and only internal path remain
prefer the path through the closest IGP neighbor.
10.Prefer the route with the lowest ip address value for BGP router
ID.
BGP finite state machine
• Idle state: In this state BGP refuses all incoming BGP
connections. No resources are allocated to the peer.
• Connect state: In this state BGP is waiting for the transport
protocol connection to be completed.
• Active state: In this state BGP is trying to acquire a peer by
initiating a transport protocol connection.
• OpenSent state: In this state BGP waits for an OPEN message
from its peer.
• OpenConfirm state: In this state BGP waits for a
KEEPALIVE or NOTIFICATION message.
• Established state: In the Established state BGP can exchange
UPDATE, NOTIFICATION, and KEEPALIVE messages with
its peer.