Slide 1
1
CMPT 471
Networking II
BGP
© Janice Regan, 2006
2
Flow of routing information
IP packet forwarding using the routing table to forward a packet to the correct host or router
The IRP controls the maintenance of the entries in the routing tables and the transfer of routing information between routers within the autonomous system.
The ERP summarizes the data provided by the IRP and shares that data with routers in other ASs. It also collects summary data for the networks connected to other participating border routers and passes the information to the IRP and the AS’s other internal routers
© Janice Regan, 2006
3
Flow of routing information
A border router can also choose to advertise routes received from other border routers in its AS (who received it from other border routers on other ASs). If it does this the AS becomes transit network for packets taking those routes.
© Janice Regan, 2006
4
“Large amounts” of data
limitations of distance vector algorithms make them unusable for an exterior routing protocol: how do you define a metric?
large size of the Internet makes a link state algorithm computationally infeasible.
A limit of ~ 200 routers is recommended for link state calculations.
The Internet was approaching 18,000 AS’s (July 2004), each of which is likely to have several boundary routers; many will have 100’s of boundary routers.
A BGP speaker must maintain two tables of route information for each of its neighbours (routes received and routes advertised), plus a route table for its own use The June 2004 IETF draft BGP protocol analysis report estimates the total memory requirement to be on the order of 100MB for a router with 100 BGP peers.
© Janice Regan, 2006
5
What approach to routing is right for an Exterior Router Protocol
Link-state and distance-vector not effective for exterior router protocol
ASs may have different priorities or restrictions that prohibit use of certain other ASs (those belonging to a competitor for instance),
Distance-vector gives no information about ASs visited on route, only about distance to destination, this is not always the most applicable information particularly when policy based routing is needed
© Janice Regan, 2006
6
ERP: Path Vector
No path cost information used
Each block of information lists all ASs visited on the way to the receiver, Each block is called a route
Allows the receiver to know the source for each path and whether the path originates in the local AS (coming from IRP or ERP)
Can be used to check for loops ( conceptually any node appearing more than once)
© Janice Regan, 2006
7
ERP: Path Vector
Each block of information lists all ASs visited on the way to the receiver, Each block is called a route
Enables router to perform policy routing based on
Avoiding transiting a particular AS
link speed, capacity, tendency to become congested, overall quality of operation, security
minimizing number of transit ASs
© Janice Regan, 2006
8
Border Gateway Protocol
BGP is the preferred ERP for or use with TCP/IP internets
RFC 1771 and 1772
A path vector protocol
Messages sent over reliable TCP connections
4 types: Open, Update, Keep Alive, Notification
All message types have a common header
Maximum size of a message is 4096 bytes
© Janice Regan, 2006
9
BGP message header format
Comer 2000: fig 15.5 and 15.6
© Janice Regan, 2006
10
BGP messages: common header
Marker: an agreed upon value to mark the start of a message, also can be used for authentication (contains 1’s in the initial message or an agreed upon authentication string)
Length: Length of the total message in octets (19-4096) Max length of message is 4096 octets
Type: code indicating type of message, Open(1), Update(2), Notification(3), KeepAlive(4)
© Janice Regan, 2006
11
Components of BGP operation
ALL BGP messages are sent through a TCP connection.
This eliminates the need for BGP to deal with flow control ( retransmission, acknowledgement, and sequencing) itself, and simplifies the BGP protocol removing the need for retransmission timers.
BGP assumes that TCP uses a graceful shutdown (all waiting packets are sent before connection is closed)
© Janice Regan, 2006
12
Additional Usage of Marker
The marker is also used for synchronization
A TCP connection is ‘always on’
How do we identify the beginning of a message?
Each message has a length indicated in the message header. Take the bit following the end of this packet as the start of the next packet
What if the length is wrong? Then the next message will not be interpreted correctly (off by one bit)
To avoid this difficulty use the marker for synchronization. Watch for the marker, use it to define the beginning of the message
© Janice Regan, 2006
13
Components of BGP operation
Neighbor acquisition: Determine if a router physically connected to this router is willing to be a neighbor and Initiate neighbor relationship, negotiating parameters
Neighbor reachability: maintain neighbor relationship
Network reachability: build/maintain routing database
Reporting of error conditions
© Janice Regan, 2006
14
BGP : neighbor acquisition
Open TCP connection between router1 and router2, a pair of connected (neighbor) routers, on port 179
Router1 and router2 both send an Open message
Router1 receives router2’s open message. If router1 agrees to become a neighbor of router2 it replies to router2 with a keep-alive message (like an ACK)
Router2 receives router1’s open message. If router2 agrees to become a neighbor of router1 it replies to router1 with a keep-alive message
© Janice Regan, 2006
15
BGP : neighbor acquisition
If either router does not agree, or some other problem occurs a notification message will be sent and the connection will eventually be terminated
When both routers have received a keep-alive from the other router, after sending a keep-alive to the other router, the neighbor relationship is established.
© Janice Regan, 2006
16
BGP OPEN message
Comer 2000: fig 15.7
(always the same interface)
© Janice Regan, 2006
17
Fields: BGP open message
BGP version number (current version is 4): Both routers must use the same version of BGP to be able to become neighbors
AS number: A number identifying the AS to which the sending router belongs
BGP option length: 0 if no options, otherwise the length of the options field
© Janice Regan, 2006
18
Fields: BGP open message
Hold time: maximum number of seconds between receipt of successive keep-alive messages. If no keep-alive or update message is received during the hold time the connection terminates
BGP Identifier: One of the IP addresses of the BGP router (sender) A BGP router will use the same identifier regardless of the interface through which the message is actually sent
BGP option length: 0 if no options, otherwise the length of the options field
© Janice Regan, 2006
19
BGP options fields
Each option takes at least 3 octets
One octet for type
One octet for length
A variable length data field (one or more octets)
Only one option, authentication information, is specified in RFC 1171.
This option is of limited use unless the TCP connection is secured.
© Janice Regan, 2006
20
BGP options fields
Only one option, authentication information, is specified in RFC 1171.
Contains one octet authentication code (how to interpret remaining information) identifies the authentication algorithm and the meaning of the authentication information.
Authentication information will determine the contents of the marker field in the common header for subsequent packets transferred between these neighbors
Values not defined in RFC would have to be previously agreed upon
© Janice Regan, 2006
21
Neighbor Acquisition
Negotiating BGP Parameters
When one router receives the other routers Open message it will
Check that the version specified in the request is supported
Versions must match for a neighbor relation
Check the requesting AS is acceptable to the local AS as a neighbor
Policy routing; is the router attempting to establish a neighbor relation in this routers list of acceptable neighbors?
© Janice Regan, 2006
22
Neighbor Acquisition
Negotiating BGP Parameters
When one router receives the other routers Open message it will
Select the minimum of local (sent) and received hold times as the hold time for this neighbor relationship
Minimum can be 0. This indicates no keep alive messages should be sent
Check the authentication
Check the Identifier
© Janice Regan, 2006
23
Neighbor Acquisition
Negotiating BGP Parameters
If any of the checks are negative an appropriate notification message will be sent and the TCP connection will be terminated
Otherwise a keep-alive message will be sent to indicate its willingness to be a member
© Janice Regan, 2006
24
Why secure TCP connection
An insecure connection can be compromised
A SYN flooding attack (tries to deny service by requiring creation of many half open connections)
A RST attack (tries to close the connection)
A data insertion attack (inserting forged packet into data stream)
A hijacking attack (substitute a third party for one of the endpoints of the connection)
© Janice Regan, 2006
25
Why secure TCP connection
If the TCP connection is carrying BGP traffic these attacks could bring down the BGP router and create havoc
Routes could be removed because a link in the connection was brought down. This could result in disconnecting networks
Hijacking could result in insertion of false routes that could cause problems such as loops, loss of traffic to ‘black holes’, or capture of traffic bound for some networks
© Janice Regan, 2006
26
How to prevent?
Use the authentication provided in BGP to authenticate the source.
Could also send over a secured IP connection
MD5 Signature option is now available (RFC-2358)
This is not a strong protection, and is vulnerable to known attacks
This is much stronger than the password used to protect BGP in its absence
© Janice Regan, 2006-2013
27
BGP messages: Keep-Alive
Contains only the header, (length 19 octets)
Used for neighbor reachability
exchanged to tell the other endpoint of the TCP connection that the connection is still live.
Needed because TCP only determines if the TCP connection is live when data are sent through the connection
TCP does not use available TCP feature to monitor connectivity
© Janice Regan, 2006-2013
28
BGP messages: Keep-Alive
Each neighbor must receive a keep-alive message (or an update) once per hold time to verify the TCP connection is still available
Each neighbor must send a keep-alive message (or an update) periodically to verify the TCP connection is still available
Since propagation times are not ‘constant’ messages are sent more often than 1 per hold time (usually 3x per hold time ~ every 2 minutes)
© Janice Regan, 2006-2013
29
BGP: neighbor reachability
Failure to receive either at least one keep-alive or at least one update during the hold time will indicate that the even if the connection is functioning the neighbor at the other end is not.
If a neighbor wishes to continue the neighbor relationship but has no routing update to send it will send a Keep Alive message
Each BGP router maintains a database of reachable networks. When a change is made to this database, that is when new or updated routing information is available, the router will send an Update Message containing this change
© Janice Regan, 2006-2013
30
Update messages
Update messages are also sent when a new neighbor relationship is being created
Consider routers A and B who have established a TCP connection and negotiated BGP connection parameters
All routing information to be shared must be exchanged
Each route in the router A’s data base will be sent to the router B (one per update message)
Each route in the router B’s data base will be sent to the router A (one per update message)
Each of it’s new neighbors routes will be received in an update message from that neighbor
© Janice Regan, 2006-2013
31
Update messages
Update messages are also sent when any BGP router receives new information that causes it to update it external routing database
The resulting changes to the BGP routers database will be sent to the BGP routers neighbors (one change per BGP update)
Note that only changes are sent in update packets. Routers must remember the contents of each update packet since that information will not be sent to them again
© Janice Regan, 2006-2013
32
Update messages
When a new path is received it will be compared to the presently used path:
The route is checked to assure it is usable (no loops, acceptable to router)
if the new path is usable and is better (define ‘better’ below) it will replace the old path
If the new path is usable and does not already exist in the data base it will be added
If the present path is declared ‘unreachable’ then check the most recent advertisements from all neighbors and find the best replacement path
© Janice Regan, 2006-2013
33
BGP update message
© Janice Regan, 2006-2013
34
Update Message
Update message include two sections one containing data for withdrawal of destinations and one containing information about addition of a path
One path can be added by one update message
For BGP versions 1-3 only one destination could be withdrawn by one update message and classfull addressing was used
For BGP 4 a list of destinations belonging to one or more paths can be withdrawn using a single update message and CIDR is supported
© Janice Regan, 2006-2013
35
What is a path?
In terms of BGP a path has two primary components
A list of ASs traversed or reached by the path
A list of networks reached by the path
The path can also include other attributes of the path that may later be used to choose between paths (more later)
© Janice Regan, 2006-2013
36
What is a destination?
A destination describes a network that can be reached by a path.
Each AS in a path may have several destinations that are reachable within or through that AS
Each destination is described using a CIDR prefix and a mask length. For example 197.8.2/23
© Janice Regan, 2006-2013
37
How to represent a destination
Within an update message destinations are represented as follows
A 1 octet length field containing the number of bits in the prefix (the number of bits in the netid of the network or the number of ones in the netmask)
A variable length field containing the prefix (netid). The field will be padded to the nearest octet boundary. The value used for padding is not relevant
© Janice Regan, 2006-2013
38
Update Message: withdrawal
The first section of an update message includes a list of destinations being withdrawn
Withdrawn destinations: A list of destinations to be withdrawn. Each destination in the list is represented as discussed on the previous slide
Withdrawn Length: length of the list of destinations being withdrawn. A withdrawn length of 0 indicates no routes are being withdrawn
© Janice Regan, 2006-2013
39
Withdrawing destinations
Multiple destinations can be withdrawn using 1 update message
These ‘destinations’ need not be parts of the same ‘path’
Note that to reduce the length of the ‘path’ aggregation of paths can be used (more later)
It is possible that ASs related to the withdrawn routes (including the withdrawn destinations) will become superfluous. These ASs remain part of the path but may no longer lead to any destinations
© Janice Regan, 2006-2013
40
BGP update message
© Janice Regan, 2006-2013
41
BGP update message
Can add 0 paths or 1 path using 1 update message
Path Length: length of the list of attributes that are part of the new path. (0 length implies no added path)
Path Attributes: list of attributes describing the ASs along the path (to base choice of ‘best’ path on)
The attributes will include AS_PATH which describes ASs traversed by the path
Destination networks: a list of destination networks that can be reached through the ASs given in the AS_PATH (minus those that have been withdrawn)
© Janice Regan, 2006-2013
42
BGP update: destination networks
Length of the destination networks field is 0 if the path length field is 0. (no path added)
Length of the destination networks field is not given explicitly in the update message (to reduce size of the update message).
Length of the destination networks field is calculated using the following relationship
UPDATE message Length – 32 – Total Path Attributes Length – Withdrawn Routes Length
© Janice Regan, 2006-2013
43
List of destinations for a path
Destinations in the list of destinations are represented in the same way as the withdrawn destinations were represented.
Adding one AS to the path may add more than one additional destination
© Janice Regan, 2006-2013
44
Attributes: AS_PATH (1)
AS_Path: list of ASs traversed on the path,
ordered sequences, and/or unordered sets describing a path from the source to a particular destination
Used to detect loops. Each time an AS is traversed it will check
Is this AS is already in the AS_PATH list?
If it is then a loop has occurred and the packet is dropped
© Janice Regan, 2006-2013
45
Attributes: AS_PATH (2)
AS_Path:
Is this AS is already in the AS_PATH list?
If it is not the information about the path is added to the routing database of the intermediate router
If it is not the information may also propagated to additional routers. To propagate the AS information for the current AS is added to the start (leftmost end) of the AS_Path as a sequenced entry of the list and the destinations in this AS are added to the list of destinations
© Janice Regan, 2006-2013
46
Customers of provider with AS T, have been allocated addresses that form AS X and Y
AS: T
197.8.4/23
197.8.0/23
AS: X
197.8.2/24
AS: Y
197.8.3/24
Example: AS path and aggregation
A
B
C
D
E
To AS Z
© Janice Regan, 2006-2013
47
Announcing paths
Want to send information about the path to AS T and the path through AS T to routers outside AS T to build a path from outside AS T to AS T
Consider a AS Z connected to T by a point to point connection from router C to router X in AS Z ( a neighbor of T)
Simplest way to advertise the networks reached in and through T is to announce three paths (1 to each AS)
Path 1: “T,” reaches 197.8.0/23 and 197.8.4/23
Path 2: “T,X, “ reaches 197.8.2/24
Path 3: “T,Y,” reaches 197.8.3/24
© Janice Regan, 2006-2013
48
Announcing paths
Path 1: “T,” reaches 197.8.0/23 and 197.8.4/23
Path 2: “T,X, “ reaches 197.8.2/24
Path 3: “T,Y,” reaches 197.8.3/24
Each of these paths includes an ordered list of ASs that are traversed and a list of networks that can be reached
The ordered list of ASs traversed gives an indication of the number of ASs along the path
To reduce the size of our path database at Z we want to minimize the number of paths advertised by T
© Janice Regan, 2006-2013
49
Aggregation of paths
Aggregate the four networks reached by the three paths to give 197.8.0/21
How do we aggregate the list of ASs?
We could include the entire list of ASs reached and announce that
Path 1: “T,X,Y” reaches 197.8.0/21
But this is misleading since in implies that Y is
reached by passing through T then X
(indicates 3 hops, which is not correct)
© Janice Regan, 2006-2013
50
Aggregation of paths
How do we aggregate the list of ASs?
We define two separate lists of ASs, one ordered list (called a sequence) and one unordered (list called a set)
In the sequence we place all ASs that must be passed through to reach all hosts in the aggregated destination network
In the set we place all ASs that can be reached by passing through the networks in the sequence
© Janice Regan, 2006-2013
51
Aggregation of paths
Aggregate the four networks reached by the three paths to give 197.8.0/21
Aggregate the three ASs reached into a sequence and a set
We now see that T is reached on the first hop and an additional hop will allow us to reach X and Y
Path1: ( Sequence (T), Set(X,Y) ) reaches 197.8.0/21
© Janice Regan, 2006-2013
52
Forwarding
Next consider AS Z.
AS Z may choose to propagate the path to AS T
AS Z is connected by a point to point link to AS T. If Z chooses to forward the path advertised by T to one of its other neighbors (not directly connected to T) then it will
Add its own AS name to the beginning of the sequence
Send the new extended path to its other neighbor
Path: (Sequence(Z,T), Set(X,Y))
© Janice Regan, 2006-2013
53
Multiple paths
A router may receive announcements of multiple paths to a particular destination
How does the router choose between those paths?
The simplest approach is to choose the path with the shortest sequence (that is consistent with the choosing AS’s policies)
However, we can also take into account other properties of each AS. These additional properties are communicated as additional attributes in the list of attributes.
© Janice Regan, 2006-2013
54
Internal and External BGP
We have been discussing BGP connections between BGP speakers that are members of different ASs. These are external BGP connections, eBGP connections)
In an AS containing multiple BGP speakers connections between these BGP speakers are needed. These connections are within the AS itself and are referred to as iBGP connections
All BGP speakers in the AS should be fully connected to all other BGP speaker in the AS
© Janice Regan, 2006-2013
55
iBGP
Internal BGP connections
Carry BGP routing information throughout the AS (independent of the IRP) so that all BGP speakers in the AS can coordinate their routing
Carry external BGP traffic through the AS independent of (without using) the IRP
The policy of the AS can determine if such transmission of BGP traffic through the network is permitted. (by determining which routes are advertised by each router
/docProps/thumbnail.jpeg