Monday, August 12, 2013

Routing Protocols Basics : Must know

I like to classify routing protocols as following:

Class Algorithm Examples
Distance Vector(DV) Bellman-Ford Algorithm RIP, BGP
Link State Protocol(LSP) Dijkstra's Algoirthm OSPF, IS-IS
Advanced DV Bellman Ford + DUAL(Diffusing Update Algorithm) EIGRP

You can use multiple routing protocols in the same environment. Administrative Distance value is used for a selection of the best route when multiple routing protocols are in place. The lowest Administrative Distance value wins. For example: Static Routing is more trust worthy than EIGRP. EIGRP is more trust worthy than OSPF.

Main goal of Routing Protocol is a calculation of the optimum path. Fundamentally there are two base algorithms for the shortest path calculation:
  • Distance Vector (Bellman-Ford Algorithm)
    • Router sends a copy of routing table to it's neighbors
    • Periodic update
    • Slow convergence
    • Counting to infinity problem
      • Solutions to prevents count to infinity problem:
        • Define MAX count limit (e.g max 16 hop count in RIP; 15 hop count is the maximum diameter of RIP; Disadvantage: convergence is very slow i.e 15*30=450 seconds before routers know that network is not reachable)
        • Split Horizon: Don't advertise the route to the router from where it learned the route
        • Route Poisoning and Poisoning Reverse: If neighbor router goes down, router advertise that route is unreachable
[DV Analogy: When you are driving down to some place (say from Houston to Dallas), you look at the miles. If miles keep on going down, you know that you are heading in the right direction. ]
  • Links State Protocol (Dijkstra's Algorithm)
    • Router shares neighbors info with all the routers
    • No periodic update
    • Convergence is very fast (nearly 6 seconds)
    • Three different tables:
      • Adjacency Table
      • Topology Table
      • Forwarding Table
    • CPU and Memory intensive as changes in the network requires all the routers to update link state database, run the SPF algorithm, build the SPF tree and then rebuild the routing table.

Understanding Bellman-Ford Algorithm:

Understanding Dijkstra's Algorithm:
Really nice YouTube video:
http://www.youtube.com/watch?v=8Ls1RqHCOPw

Important notes to keep in mind:
  • Routing takes place at Layer 3(Network Layer). Packet Forwarding takes place at Layer 2(Data Layer).
  • MPLS (Multiprotocol Label Switching) is a mechanism that allows packet forwarding using labels, hence making it an independent of Protocol Type. It offers L3 VPN solution. MPLS is connection-oriented and packets are forwarded across pre-configured LSPs(Label Switched Paths).
[MPLS Analogy: Postal Service network uses ZIP code/ Postal Code as a label to forward your mail (could be anything like documents, TV, gifts, etc) to the recipient. After the mail reaches to the destination ZIP code/Postal code area, then actual address of the mail recipient is used to forward the mail. This process makes mail delivery much easier and efficient. MPLS works the same way.]
  • IGPs(RIP/OSPF/EIGRP) are used for routing within AS while EGP(BGP) is used for routing between different ASs. IGP is used to route within your own network and BGP is used when you are connecting to a network you don't control. 
[BGP/IGP Analogy: Considering US Interstate System: Interstates are BGP backbone and Interstates Exits are handoffs to IGPs ]
  • BGP relies on IGP for the routing table. If route is not in the table, BGP won't advertise it.
  • BGP (Border Gateway Protocol) is used to make core routing decisions on the Internet and decisions are made based on Path and Network Policies. BGP allows multihoming (connect to multiple ISPs) for better redundancy.
  • With MPLS in place inside providers network, BGP only need to be setup on PE(Provider Edge) routers.
  • VRF (Virtual Routing and Fowarding) allows multiple instances of a routing table to exist in a router and work simultaneously. VRF allows network path segmentation, thus increases network security. Thus, VRF is also referred as VPN routing and forwarding.
[ VRF Analogy: Running multiple VRFs on a router is just like running multiple Virtual Machines on a single hypervisor. Virtual Machines run independent of each other, likewise Routing Table of each VRFs are independent of each other. ].


>>>>>>Time to get your hand  dirty>>>>>>>

BGP Lab:


Scenario:
Customer edge router is connected to two different ISPs for redundancy.
IP Address and ASN info is shown in above topology.
Customer uses EIGRP for routing within it's own network. 
Customer uses BGP to connect to two different ISPs.

Step1: Configure IP addresses on the routers as show above

CPE-RTR-CORE#
interface Serial1/0
 ip address 169.153.1.2 255.255.255.0
 clockrate 64000
 no shut

CPE-RTR-EDGE#
interface Serial1/0
 ip address 169.153.1.1 255.255.255.0
 clockrate 64000
 no shut
interface FastEthernet0/0
 ip address 172.20.1.1 255.255.255.0
 no shut
interface FastEthernet0/1
 ip address 172.20.2.1 255.255.255.0
 no shut

ISP-1#
interface Loopback0
 ip address 2.2.2.2 255.255.255.0
 no shut
interface FastEthernet0/0
 ip address 172.20.1.2 255.255.255.0
 no shut

ISP-2#
interface Loopback0
 ip address 3.3.3.3 255.255.255.0
 no shut
interface FastEthernet0/0
 ip address 172.20.2.2 255.255.255.0
 no shut

Step2: Configure BGP

ISP-1#
router bgp 200
 network 2.2.2.0 mask 255.255.255.0
 neighbor 172.20.1.1 remote-as 100

ISP-2#
router bgp 300
 network 3.3.3.0 mask 255.255.255.0
 neighbor 172.20.2.1 remote-as 100

CPE-RTR-EDGE#
ip as-path access-list 10 permit ^$    
[Note: This allow only local routes being advertised to ISP. In other words, this filters internet routes from one ISP to go back to another ISP.]  

route-map localonly permit 10
 match as-path 10

router bgp 100
 network 169.153.1.0 mask 255.255.255.0
 neighbor 172.20.1.2 remote-as 200
 neighbor 172.20.1.2 route-map localonly out
 neighbor 172.20.2.2 remote-as 300
 neighbor 172.20.2.2 route-map localonly out

Detailed explaination on access-list and regex

Step3: Configure EIGRP 

CPE-RTR-CORE#
router eigrp 100
 network 169.153.1.0 0.0.0.255
 network 0.0.0.0 255.255.255.255  [This advertises all the routes known to this router]

CPE-RTR-EDGE#
router eigrp 100
 network 169.153.1.0 0.0.0.255
 network 0.0.0.0 255.255.255.255 [This advertises all the routes known to this router]


Some useful commands for troubleshooting:
#sh ip bgp
#sh ip bgp 
#sh ip bgp regexp ^$   [Display only local routes]
#sh ip bgp regexp ^100$  [Display routes learned from ASN 100 ]
#sh ip bgp regexp ^100_  [ Display routes with ASN 100 at front ]
#sh ip route
#clear bgp *   [Clear all BGP peers]
#debug bgp updates in
#debug bgp updates out



VRF Lab:





Scenario:
Say an ISP has two customers: Plano ISD (PISD) and Dallas ISD (DISD)
PISD and DISD both uses same subnet for IP addressing (172.20.0.0/24 & 172.20.1.0/24) and they can't change their addressing scheme.
As an ISP, you want to do business with both the customers. Your goal to isolate PISD network and DISD network ensuring network security. VRF is your solution.


Step1: Configure IP addresses on the routers as shown above

PISD1#
interface Loopback0
 ip address 1.1.1.1 255.255.255.0
interface FastEthernet0/0
 ip address 172.20.0.1 255.255.255.0

PISD2#
interface Loopback0
 ip address 2.2.2.2 255.255.255.0
interface FastEthernet0/0
 ip address 172.20.1.1 255.255.255.0

DISD1#
interface Loopback0
 ip address 1.1.1.1 255.255.255.0
interface Serial1/0
 ip address 172.20.0.1 255.255.255.0
 clockrate 64000

DISD2#
interface Loopback0
 ip address 2.2.2.2 255.255.255.0
interface Serial1/0
 ip address 172.20.1.1 255.255.255.0
 clockrate 64000

Note: You can't configure IP address on ISP router as it will throw an error that you are trying to configure duplicate IP address. In out network topology ISP s1/0 and f0/0 ports are going to have same IP address (i.e 172.20.0.2/24). ISP s1/1 and f0/1 are going to have same IP address (i.e 172.20.1.2/24).

Step2: Create VRF on ISP router and add interfaces to desired VRF so that you can configure IP address on ISP router to connect to CPE routers.

ISP#
ip vrf PISD
 rd 1:1
ip vrf DISD
 rd 2:2

Step3: Configure IP addresses on ISP router
ISP#
interface FastEthernet0/0
 ip vrf forwarding PISD
 ip address 172.20.0.2 255.255.255.0


interface FastEthernet0/1
 ip vrf forwarding PISD
 ip address 172.20.1.2 255.255.255.0

interface Serial1/0
 ip vrf forwarding DISD
 ip address 172.20.0.2 255.255.255.0
 clockrate 64000

interface Serial1/1
 ip vrf forwarding DISD
 ip address 172.20.1.2 255.255.255.0
 clockrate 64000

Step4: Configure OSPF on all the routers

CPE-ROUTERS(PISD1, PISD2, DISD1, DISD2)#
router ospf  1
 network 0.0.0.0 255.255.255.255 area 0 [This advertises all the routes known to this router]

ISP#
router ospf  1 vrf  PISD
 network 0.0.0.0 255.255.255.255 area 0 [This advertises all the routes known to this router]

router ospf  2 vrf  DISD
 network 0.0.0.0 255.255.255.255 area 0  [This advertises all the routes known to this router]

Some useful commands for troubleshooting:
#sh ip route
#sh ip route vrf  PISD
#sh ip router vrf DISD