BGP Part 2 and Failure Recovery

Question 1

BGP Recap

Answer 1

• Whereas intradomain routing protocols such as OSPF run between a set of routers all managed by the same AS/domain, BGP runs between different ASes or domains.
• Consequently:
  
  • One AS may not wish to advertise reachability of certain routes to some of its neighbours, because the neighbour might then send traffic, increasing the AS’s network load
  • An AS may wish to preferentially route its traffic via one neighbour than via another
• BGP extends the basic distance vector approach, to allow policy-driven routing
• BGP allows routers to exchange information about the reachability of IP destination address prefixes
• Border Gateway Protocol (BGP) is a Path Vector protocol

Question 2

Basic BGP Message Exchange

Answer 2

• 4 BGP message types
• OPEN: initial message sent at the start of a BGP session. It allows each BGP peer to identify itself and agree optional parameters
• UPDATE: advertises paths to destinations, and associates attributes with these paths. This is the principal BGP message we are concerned with, see following slides
• NOTIFICATION: error reporting
• KEEPALIVE: allows BGP peers to confirm they are still running; based on a hold time interval
  (~some tens of seconds)

Question 3

BGP UPDATE Message Structure

Answer 3

• BGP UPDATE message advertises routes to destinations and associates attributes with these routes. Its structure is:
  
  • Withdrawn routes: IP destination prefixes which have been withdrawn (i.e. a path to these destination prefixes is no longer supported by the sender of the UPDATE message)
  • Path attributes: a set of values associated with each IP destination prefix in the NLRI field
  • Network Layer Reachability Information (NLRI): a set of IP destination prefixes
• IP destination prefix format: network prefix, and the number of bits in the prefix (i.e. the address mask). Example: 128.234.208.0/20 (CIDR)

Question 4

BGP Attributes

Answer 4

• Attributes define information about the path to each destination prefix. They help BGP to select the best paths to IP destination prefixes while remaining scalable for the large number of ASs that constitute the Internet
• The principal attributes that we consider are the following:
  • Local preference, LOCAL_PREF
  • Autonomous System Path, AS_PATH
  • Multi-exit discriminator, MED
  • Next hop, NEXT_HOP

Question 5

BGP Attributes: LOCAL_PREF

Answer 5

• If there are multiple paths to a given destination prefix, the LOCAL_PREF attribute allows BGP to specify a preference within an AS for one route over the other(s)
• Only used locally within an AS
• The higher the LOCAL_PREF value, the more preferred a route is

Question 6

BGP Attributes: AS_PATH

Answer 6

• Each AS in the Internet is assigned its own unique AS number
• The BGP AS_PATH attribute contains a list of all the AS numbers of the ASs through which the prefix announcement has passed
• The number of entries in the AS_PATH attribute is therefore effectively a measure of the “hop count” to reach the prefix(es) (where one hop = one domain / AS)

Question 7

BGP NEXT_HOP: iBGP and eBGP

Answer 7

Using eBGP session between 3a and 1c, AS3 sends prefix reachability info to AS1.
- 1c can then use iBGP do distribute new prefix information to all routers in AS1
- 1b can then re-advertise new reachability info to AS2 over 1b-to-2a eBGP session

When a router learns of a new prefix, it creates entry for prefix in its forwarding table.

Question 8

BGP Attributes: NEXT_HOP

Answer 8

• The NEXT_HOP attribute specifies the IP address of the router in the adjacent domain that is the next hop to the destination prefixes listed in the UPDATE message NLRI field
• The NEXT_HOP address is usually the same as the IP address of the of the BGP router that
  is sending the message that contains the NEXT_HOP attribute
  
  • e.g. C advertises reachability of 128.1.192.0/20 to B, specifying as NEXT_HOP the IP address of C

Question 9

BGP Attributes: MULTI_EXIT_DISCRIMINATOR (MED)

Answer 9

• MED is used when two ASs have two or more direct connections. It allows one AS to express to the other AS a relative preference for each of the links: one AS sets the MED value, the other AS uses this
• The lower the MED value, the more preferred a path is (Note MED is a preference, not a
  rule, as we shall see in a later slide)
• Example:
  • AS3 and AS4 are connected by two links, A and B
  • BGP sessions run over each link
  • AS1 is connected to AS3 close to link A; AS2 is connected to AS3 close to link B
  • AS3 sets MED values so as to prefer link A for prefixes in AS1, and to prefer link B for prefixes in AS2
  • AS3 here could have only sent one advertisement over its preferred link, why does it advertise the destination over multiple links?

Question 10

BGP Route Selection Process

Answer 10

• If BGP learns about more than one route for a given address prefix, the following rules are applied:
  
  • Select the route with the highest LOCAL_PREF value. If still a tie, then
  • Select the route with the shortest AS_PATH (=hop count, in distance vector terms). If still a tie, then
  • Select the route with the lowest MULTI_EXIT_DISCRIM, if multiple routes were learned from the same AS. If still a tie, then
  • Select the route with the minimum cost to the NEXT_HOP. If still a tie, then
  • Select the route learned via eBGP (if only one), or the route learned via eBGP with the lowest BGP identifier. If still a tie, then
  • Select the route learned from the iBGP neighbour with the lowest BGP identifier (this is usually one of the router’s IP addresses)

Question 11

Example: LOCAL_PREF and AS_PATH

Answer 11

• AS5 selects link A as the path to forward packets destined for 128.1.192.0/20 because of the LOCAL_PREF settings, even though this is not the shortest path (measured by the size of AS_PATH)

Question 12

Inter-domain Structure: Business Relationships

Answer 12

The various functions of the domains allow us to define a set of relationships:

• Customer-provider relationship:
  
  • The customer pays the provider for access to the rest of the Internet. In the same way that a residential customer pays a monthly fee to their ISP, so a (smaller) domain pays a (larger) domain for access
• Peering relationship:
  
  • Two domains (typically of similar size) agree to exchange traffic between their respective customers. Traffic flow volumes in either direction of the peering relationship are usually similar
• These business relationships between
  domains impact the routing information
  exchanged between the domains

Question 13

BGP Export Policies

Answer 13

Example: AS2’s BGP policies
* AS2 learns the following routes:
* From AS1: AS1, 3, 6, 7
* From AS3: AS3, 6, 7
* From AS4: AS4
* From AS5: AS5

• AS2 exports the following routes:
  
  • To its provider AS1: AS2, 4, 5
  • To its peer AS3: AS2, 4, 5
  • To its customer AS4: AS1, 2, 5, 3, 6, 7
  • To its customer AS5: AS1, 2, 4, 3, 6, 7
• AS2 does not advertise to AS3 the fact that it can reach AS1, since it does not wish to carry transit traffic for AS3
• Similarly, AS2 does not advertise to AS1 the fact that it can reach AS3

Question 14

BGP Export Policies

Answer 14

• C advertises path Cy to x.
• 1. Should x advertise xCy path to B?
• A advertises path Aw to B
• B advertises path BAw to x
• 2. Should B advertise path BAw to C?

Question 15

BGP: Controlling Outbound Traffic

Answer 15

• Definition: TE that optimises the flow of traffic leaving a domain
• Approach: configure the LOCAL_PREF attribute
• Example: 2 links between AS5 and AS8; link A
  is high bandwidth, link B is low bandwidth
  • Assign a higher LOCAL_PREF (=60) to the high bandwidth link and a lower LOCAL_PREF (=5) to the low bandwidth link; all traffic will then be routed over the high bandwidth link (Link A)
  • The low bandwidth link still exists as a backup path in the event of failure of the high bandwidth link

Question 16

BGP: Controlling Inbound Traffic(1)

Answer 16

• Definition: TE that optimises the flow of traffic entering a domain
• Approach 1: announce different advertisements on different links
  
  • Example: AS3 announces reachability of all AS1 addresses on Link A only, and reachability of all AS2 addresses on Link B only
  • AS4 therefore sends 10.10.0.0/16 traffic on Link A and 20.20.0.0/16 traffic on Link B
  • Disadvantage: if one link fails the corresponding destination becomes unreachable

Question 17

BGP: Controlling Inbound Traffic(2)

Answer 17

• Approach 2: configure MULTI_EXIT_DISCRIM (MED) attribute
  
  • MED only works when two ASs have 2 or more direct links and they agree to implement MED
  • The lower the MED value the more preferred a path is; so AS3 will receive from AS 4 traffic destined to 10.10.0.0/16 on Link A and traffic destined to 20.20.0.0/16 on Link B
  • Advantage: backup path availability: Link A is a backup for 20.20.0.0/16 and Link B is a backup for 10.10.0.0/16

Question 18

BGP: Controlling Inbound Traffic(3)

Answer 18

• Approach 3: artificially extend the AS Path length
  (AS_PATH prepending)
• Example: AS2 announces reachability of AS1 on its inter-domain links to AS3 and AS4, but uses
  AS_PATH prepending on the link to AS3 so as to discourage traffic destined to AS1 from using this link
  (it uses twice its own AS to make the path appear longer, which is common)
• Based on the AS_PATH attributes, AS5 will therefore select AS4 when forwarding traffic to 10.10.0.0 / 16

Question 19

Statistics of Network Failures

Answer 19

• Around 20% of network failures are attributed to planned maintenance that can be completely anticipated, in which case “make-before-break” can be fully applicable
• Around 70% of unexpected failures are single link failures, i.e. the breakdown of a single
  interface
• Around 80% of link failures are transient ones – for most of the cases the link can be recovered within 10 minutes, and about 50% of them last less than a minute (e.g. due to router rebooting)

Question 20

Network Recovery Cycle

Answer 20

Question 21

Post-failure Re-convergence

Answer 21

• The time procedure between the link fails and all the routers within an AS reach
  consistent views on the new network topology and accordingly finish updating their routing/forwarding tables is known as re-convergence

Question 22

Re-convergence Example (1)

Answer 22

Question 23

Re-convergence Example (2)

Answer 23

Question 24

Fast Reroute (FRR)

Answer 24

• Basic Idea
  – The router directly attached to the failing link is responsible for local rerouting. This router is called the repairing router of the failing link
  – Backup solutions need to be pre-configured at the repairing router
  – Link State Advertisement (LSA) about the failed link is suppressed – none of the remote routers are aware of the failure, and hence they do not need to update their routing/forwarding tables accordingly

The routers pre-installs a backup alternative next-hop for each destination. This alternative next-hop must be a directly attached neighbour to the head node, but is NOT necessarily on the shortest path towards
the destination

 – In case the protected link fails, the head node immediately forwards the packets towards the destination on the pre-installed backup alternative next-hop from where it can be natively delivered to the destination

Question 25

An Example for Success

Answer 25

Question 26

An Example for Failed Protection

Answer 26

Question 27

A Necessary Condition

Answer 27

Question 28

Hot Potato Routing – A Failure Example

Answer 28

Question 29

Hot Potato Routing – A Failure Example 2

Answer 29

Question 30

Hot Potato Routing – A Failure Example 3

Answer 30