eBGP Multi-Path

jezg76jezg76 Member Posts: 97 ■■□□□□□□□□
in CCNP Service Provider
Greetings all. I hope everyone is having a fantastic 2009, although I can't believe it's already October, but I digress...

I want to seek the opinions on folks much smarter than I about the BGP Multi-Path route selection process. I have googled the far reaches of the Internet universe only to find a barren wasteland of info regarding my question. First, my topolgy:

bgp-multipath.png

All links are as follows:
R1 - R2 131.1.12.1 <--> 131.1.12.2
R1 - R3 131.1.13.1 <--> 131.1.13.3
R1 - R4 131.1.14.1 <--> 131.1.14.4
R2 - R5 131.1.25.2 <--> 131.1.25.5
R3 - R5 131.1.35.3 <--> 131.1.35.5
R4 - R5 131.1.45.4 <--> 131.1.45.5

All subnets are a /24.

RIDs:
R1 131.1.14.1
R2 131.1.25.2
R3 131.1.35.3
R4 131.1.45.4
R5 131.1.45.5

I have the following configured on R1:
router bgp 65001
 template peer-session eBGP-Peer-Session-65002
  remote-as 65002
  description eBGP to AS 65002
 exit-peer-session
 !
 no synchronization
 bgp log-neighbor-changes
 neighbor 131.1.12.2 inherit peer-session eBGP-Peer-Session-65002
 neighbor 131.1.13.3 inherit peer-session eBGP-Peer-Session-65002
 neighbor 131.1.14.4 inherit peer-session eBGP-Peer-Session-65002
 maximum-paths 2
 no auto-summary

R5 is advertising the 1.0.0.0/8 network.

On R1, the following is the output of the "show ip bgp 1.0.0.0" command
R1#sh ip bgp 1.0.0.0
BGP routing table entry for 1.0.0.0/8, version 3
Paths: (3 available, best #3, table Default-IP-Routing-Table)
Multipath: eBGP
  Advertised to update-groups:
     1
  65002 65003
    131.1.14.4 from 131.1.14.4 (131.1.45.4)
      Origin IGP, localpref 100, valid, external, multipath
  65002 65003
    131.1.13.3 from 131.1.13.3 (131.1.35.3)
      Origin IGP, localpref 100, valid, external
  65002 65003
    131.1.12.2 from 131.1.12.2 (131.1.25.2)
      Origin IGP, localpref 100, valid, external, multipath, best

The following is the output of "debug ip bgp events"
*Mar  1 00:52:44.175: BGP: Import walker start version 0, end version 1
*Mar  1 00:52:44.175: BGP: ... start import cfg version = 0
*Mar  1 00:52:45.283: %BGP-5-ADJCHANGE: neighbor 131.1.12.2 Up
*Mar  1 00:52:45.375: BGP(0): 131.1.12.2 rcvd UPDATE w/ attr: nexthop 131.1.12.2, origin ?, metric 0, path 65002
*Mar  1 00:52:45.375: BGP(0): 131.1.12.2 rcvd 131.1.25.0/24
*Mar  1 00:52:45.379: BGP(0): 131.1.12.2 rcvd 131.1.12.0/24
*Mar  1 00:52:45.379: BGP(0): 131.1.12.2 rcvd UPDATE w/ attr: nexthop 131.1.12.2, origin i, path 65002 65003
*Mar  1 00:52:45.383: BGP(0): 131.1.12.2 rcvd 1.0.0.0/8
*Mar  1 00:52:45.383: %BGP-5-ADJCHANGE: neighbor 131.1.13.3 Up
*Mar  1 00:52:45.699: BGP(0): 131.1.13.3 rcvd UPDATE w/ attr: nexthop 131.1.13.3, origin ?, metric 0, path 65002
*Mar  1 00:52:45.699: BGP(0): 131.1.13.3 rcvd 131.1.35.0/24
*Mar  1 00:52:45.699: BGP(0): 131.1.13.3 rcvd 131.1.13.0/24
*Mar  1 00:52:45.703: BGP(0): 131.1.13.3 rcvd UPDATE w/ attr: nexthop 131.1.13.3, origin i, path 65002 65003
*Mar  1 00:52:45.703: BGP(0): 131.1.13.3 rcvd 1.0.0.0/8
*Mar  1 00:52:46.751: %BGP-5-ADJCHANGE: neighbor 131.1.14.4 Up
*Mar  1 00:52:46.855: BGP(0): 131.1.14.4 rcvd UPDATE w/ attr: nexthop 131.1.14.4, origin ?, metric 0, path 65002
*Mar  1 00:52:46.855: BGP(0): 131.1.14.4 rcvd 131.1.45.0/24
*Mar  1 00:52:46.859: BGP(0): 131.1.14.4 rcvd 131.1.14.0/24
*Mar  1 00:52:46.859: BGP(0): 131.1.14.4 rcvd UPDATE w/ attr: nexthop 131.1.14.4, origin i, path 65002 65003
*Mar  1 00:52:46.863: BGP(0): 131.1.14.4 rcvd 1.0.0.0/8
*Mar  1 00:52:46.927: BGP(0): process mpath after bestpath selection comparing bestpath 131.1.12.2 (best_idx: 0) with
*Mar  1 00:52:46.927: BGP(0): Non-multipath (bestpath) -> 1 of 2 multipath (bestpath) for 1.0.0.0/8 from 131.1.12.2
*Mar  1 00:52:46.927: BGP(0): Non-multipath -> 2 of 2 multipath for 1.0.0.0/8 from 131.1.14.4
*Mar  1 00:52:46.927: BGP(0): process mpath after bestpath selection comparing bestpath 131.1.12.2 (best_idx: 0) with
*Mar  1 00:52:46.927: BGP(0): process mpath after bestpath selection comparing bestpath 131.1.13.3 (best_idx: 0) with
*Mar  1 00:52:46.927: BGP(0): process mpath after bestpath selection comparing bestpath 131.1.14.4 (best_idx: 0) with
*Mar  1 00:52:46.927: BGP(0): process mpath after bestpath selection comparing bestpath 131.1.12.2 (best_idx: 0) with
*Mar  1 00:52:46.927: BGP(0): process mpath after bestpath selection comparing bestpath 131.1.13.3 (best_idx: 0) with
*Mar  1 00:52:46.927: BGP(0): process mpath after bestpath selection comparing bestpath 131.1.14.4 (best_idx: 0) with
*Mar  1 00:52:46.927: BGP(0): Revise route installing 1 of 2 routes for 1.0.0.0/8 -> 131.1.14.4(main) to main IP table
*Mar  1 00:52:46.927: BGP(0): Revise route installing 2 of 2 routes for 1.0.0.0/8 -> 131.1.12.2(main) to main IP table
*Mar  1 00:52:46.931: BGP(0): Revise route installing 1 of 1 routes for 131.1.12.0/24 -> 131.1.12.2(main) to main IP table
*Mar  1 00:52:46.935: BGP(0): Revise route installing 1 of 1 routes for 131.1.13.0/24 -> 131.1.13.3(main) to main IP table
*Mar  1 00:52:46.935: BGP(0): Revise route installing 1 of 1 routes for 131.1.14.0/24 -> 131.1.14.4(main) to main IP table
*Mar  1 00:52:46.935: BGP(0): Revise route installing 1 of 1 routes for 131.1.25.0/24 -> 131.1.12.2(main) to main IP table
*Mar  1 00:52:46.939: BGP(0): Revise route installing 1 of 1 routes for 131.1.35.0/24 -> 131.1.13.3(main) to main IP table
*Mar  1 00:52:46.943: BGP(0): Revise route installing 1 of 1 routes for 131.1.45.0/24 -> 131.1.14.4(main) to main IP table
*Mar  1 00:52:46.943: BGP(0): Revise route installing 1 of 1 routes for 131.1.12.0/24 -> 131.1.12.2(main) to main IP table
*Mar  1 00:52:46.947: BGP(0): Revise route installing 1 of 1 routes for 131.1.13.0/24 -> 131.1.13.3(main) to main IP table
*Mar  1 00:52:46.947: BGP(0): Revise route installing 1 of 1 routes for 131.1.14.0/24 -> 131.1.14.4(main) to main IP table
*Mar  1 00:52:46.951: BGP(0): 131.1.12.2 send UPDATE (format) 1.0.0.0/8, next 131.1.12.1, metric 0, path 65002 65003
*Mar  1 00:52:46.951: BGP(0): 131.1.12.2 send UPDATE (format) 131.1.14.0/24, next 131.1.12.1, metric 0, path 65002
*Mar  1 00:52:46.955: BGP(0): 131.1.12.2 send UPDATE (prepend, chgflags: 0x820) 131.1.13.0/24, next 131.1.12.1, metric 0, path 65002
*Mar  1 00:52:46.955: BGP(0): 131.1.12.2 NEXT_HOP part 1 net 131.1.12.0/24, next 131.1.12.2
*Mar  1 00:52:46.959: BGP(0): 131.1.12.2 send UPDATE (format) 131.1.12.0/24, next 131.1.12.2, metric 0, path 65002
*Mar  1 00:52:46.959: BGP(0): 131.1.12.2 send UPDATE (prepend, chgflags: 0x820) 131.1.45.0/24, next 131.1.12.1, metric 0, path 65002
*Mar  1 00:52:46.963: BGP(0): 131.1.12.2 send UPDATE (prepend, chgflags: 0x820) 131.1.35.0/24, next 131.1.12.1, metric 0, path 65002
*Mar  1 00:52:46.963: BGP(0): 131.1.12.2 NEXT_HOP part 1 net 131.1.25.0/24, next 131.1.12.2
*Mar  1 00:52:46.967: BGP(0): 131.1.12.2 send UPDATE (prepend, chgflags: 0x820) 131.1.25.0/24, next 131.1.12.2, metric 0, path 65002
*Mar  1 00:52:47.067: BGP(0): updgrp 1 - 131.1.12.2 updates replicated for neighbors: 131.1.13.3 131.1.14.4

And now, after all of that, the million dollar question...

Why does R1 choose those two routes of the available three? By the output above, it chooses the route from R2 and R4, but why?

Is it because it will compare the 1.0.0.0/8 route from R2 and R3, and chooses the route from R2 due to it having the lower RID of 131.1.25.2. Installs that in the routing table, then just add the route from R4 because it is the only one left and the maximum-paths is set to 2?

I just don't see why R3 gets chosen as an unused route.

If anyone can shed some light on that for me, I would be greatly appreciative.

Thanks.
policy-map type inspect TACO
class type inspect BELL
drop log
· Share on FacebookShare on Twitter

Comments

  • tim100tim100 Member Posts: 162
    The route to R4 was the most recently received path from the multipath candidates. So let's say the order of routes received was:

    1.0.0.0/8 via R4
    1.0.0.0/8 via R3
    1.0.0.0/8 via R2

    with the route to R4 being the most recently received path and and the route to R2 being the oldest. R2 is chosen as the best path during the best path selection process leaving the order of paths received as:

    1.0.0.0/8 via R4
    1.0.0.0/8 via R3

    you configured "maximum paths 2" making R4 and R3 multipath candidates. The route to R4 is then selected since it was the most recently received path.
    · Share on FacebookShare on Twitter
  • jezg76jezg76 Member Posts: 97 ■■□□□□□□□□
    Awesome explanation, Tim. Thank you for that!

    If I could ask one more question that sparked in my head during your explanation...

    You said the path via R2 is selected as best due to the fact is was received first (the oldest). Is there a show command that will tell you what the oldest route is for BGP routes? With that process for best route selection, why would it ever come down to RID, then IP address? The odds of a routes being received at the exact same point in time has got to be slim. I wonder if there is a within-a-certain-amount-of-time-they-are-equal deal.

    I do appreciate your time or anyone who knows the answer. :)
    policy-map type inspect TACO
    class type inspect BELL
    drop log
    · Share on FacebookShare on Twitter
  • tim100tim100 Member Posts: 162
    jezg76 wrote: »
    Awesome explanation, Tim. Thank you for that!

    If I could ask one more question that sparked in my head during your explanation...

    You said the path via R2 is selected as best due to the fact is was received first (the oldest). Is there a show command that will tell you what the oldest route is for BGP routes? With that process for best route selection, why would it ever come down to RID, then IP address?

    R2 is selected because of the best path selection algorithm. The following link explains the best path selection algorithm and why it would come down to the RID or finally the neighbor IP:

    BGP Best Path Selection Algorithm [IP Routing] - Cisco Systems
    · Share on FacebookShare on Twitter
  • jezg76jezg76 Member Posts: 97 ■■□□□□□□□□
    Tim, the lightbulb just went on. I sincerely thank you for flicking the switch for me. :)
    policy-map type inspect TACO
    class type inspect BELL
    drop log
    · Share on FacebookShare on Twitter
Sign In or Register to comment.