Routing basics/CEF


System is processing data
Please download to view
  • Routing basics/CEF May 4, 2016 Dmitry Figol CCIE R&S #53592
  • Intro to routing and switching Routing • Finding the optimal way towards destination Switching • Moving packet between interfaces 2
  • Packet forwarding When the packet comes in, the router does the following: 0. Checks and removes L2 header, gets destination IP 1. Routing process 2. Switching process 3. L2 encapsulation 3
  • Routing process • Find the longest match based on destination IP in routing table (RIB) • The goal is to find outgoing interface and Next Hop IP address (if applicable) 4
  • Routing table - example 5
  • Routing table (cont.) • Recursive Lookup • Contains useless information for forwarding: • For example, Administrative Distance and Metric • Single lookup has linear complexity O(n) • Stored in RAM • Verification: show ip route [ip-address [mask]] 6
  • Routing table (cont.) Metric (maximum is 232-1 = 4294967295): • Used to choose the best route within a single routing protocol (*not always true) Administrative distance (0..255): • Used to choose the best route between routing protocols 7
  • Routing table (cont.) - AD 8 Route Source Value Connected 0 Static 1 EIGRP summary 5 eBGP 20 EIGRP internal 90 IGRP 100 OSPF 110 IS-IS 115 Route Source Value RIP 120 EGP 140 ODR 160 EIGRP external 170 iBGP 200 NHRP 250 DHCP learned 254 Unknown* (Not installed) 255
  • Routing protocols • Static • Dynamic: • IGP: • Distance-vector (RIP, EIGRP) • Link-state (OSPF, IS-IS) • EGP: • Path-vector (BGP) 9
  • Switching process • Process-switching • Fast-switching • Cisco Express Forwarding (CEF) 10
  • L2 Encapsulation Knowing outgoing interface and Next Hop address is not always enough for “packet rewrite” • Point-to-point links (PPP, HDLC) – no additional information required • Point-to-multipoint links (Ethernet, Frame-relay, ATM) – L2 Destination Address is required (from ARP cache, Frame- Relay/ATM mappings) 11
  • Traffic types Data plane – traffic through the device Control plane – traffic to the device: • Routing protocols hello/updates • BPDU • FHRP and others Management plane – part of control plane: • SSH/Telnet • SNMP 12
  • Processors: CPU and ASIC • Central processing unit (CPU) is the brains of the network device • Handles control plane • Can do anything • Can’t do packet forwarding with high throughput* *Note: DPDK project enables x86 multi-core processors to forward 200+ Gbps 13
  • Processors: CPU and ASIC • Application specific integrated circuit (ASIC) is circuit with transistors • Very fast, but dumb • Designed specifically to move packets • Expensive • Not possible to program new features • Responsible for data plane 14
  • Memory: RAM, CAM and TCAM Random Access Memory (RAM) is the most common type of memory • Value is accessed by pointer (memory address) • Cheap 15
  • Memory: RAM, CAM and TCAM Content-addressable memory (CAM) • Value is accessed by a key, not a pointer • Very fast • Expensive • High power consumption • O(1) constant time lookup • Used in switches for MAC address table 16
  • Memory: RAM, CAM and TCAM Ternary Content-addressable memory (TCAM) • Value is accessed by a key, which consists of not only “0” and “1”, but also “don’t care” bits. • Very expensive • High power consumption • O(1) constant time lookup! • Used for next-hop lookup (CEF table), ACL (security and QoS) 17
  • Process-switching • Recursive lookup is performed by CPU in RIB • There is special process responsible for process-switching “IP Input” • The following traffic is process-switched: • Control plane • Locally generated (not all) • No L2 adjacency information • ACL logging 18
  • Fast-switching • First packet for source-destination IP pair is process-switched • IP pair and corresponding encapsulation information is added to the cache • Following packets are forwarding based on the entry in cache • Deprecated 19
  • Cisco Express Forwarding (CEF) The idea is to precompute and optimize information in RIB: • Resolve recursive lookup and get rid of useless information • Add pointer to pre-built L2 header in Adjacency table The new table is called Forwarding Information Base (FIB) or CEF table: • Contains prefix, NH, outgoing interface, pointer to L2 header • Stored in DRAM [O(1) using 256-way mtrie data structure] and TCAM [if exists, also O(1), but much faster] The lookup is done during the interrupt (process scheduling is not required) 20
  • CEF (cont.) Verification: show ip cef [ip-address [mask]] [detail] [internal] Shows NH, outgoing interface, MPLS labels (if applicable) Internal keyword shows pointer to Adjacency entry and hash buckets Disable CEF: (config)# no ip cef 21
  • CEF – Adjacency table • CEF process takes information from all L3-to-L2 mappings and builds L2 header • Adjacency table contains NH, interface, associated L2 Header • Stored in RAM • Pitfall: CEF process does not allow adjacency to age out (clear arp won’t delete ARP entry if it can be revalidated) • Verification: show adjacency [detail] 22
  • CEF – Adjacency types • Cache • Glean • Receive • Punt • Null • Discard • Drop 23
  • CEF on hardware-based platforms • CEF basically allows to forward traffic without CPU • Depending on platform there can be zero, one or more ASICs. • The same applies for TCAM • All L3 switches have TCAM, only some routers have it • That’s why generally speaking L3 switches forward traffic faster than routers • TCAM stores not only FIB, but ACL and QoS rules, the allocation is predefined though • On some platforms you can change allocation profile 24
  • CEF on hardware-based platforms (cont.) 25 RIB ARP Cache Other L2 information FIB (CEF Table) Adjacency table TCAM RAM ASIC
  • CEF – Load balancing • Routing protocols can install several routes for the same prefix • How will CEF decide where to send packet? • CEF is doing load-balancing per-flow • By default, it takes source-destination IP pair, feeds it to the hashing algorithm, returns the number of the bucket • Buckets are allocated automatically per NH, depending on the traffic share count in RIB 26
  • CEF – Load balancing (cont.) Verification: show ip cef [ip [mask]] internal – shows NH-to-bucket distribution show ip cef exact-route src-ip dst-ip – shows NH and interface for source/destination IP pair Change load balancing method (not recommended): (config-if)# ip load-sharing per-packet 27
  • CEF polarization • Hash algorithm is deterministic, meaning that for the same source/destination IP pair the bucket (outgoing link) is the same. • Result is that some links can be underutilized (especially if we have chain of routers with ECMP). • One possible solution is to include L4 ports in hashing (if supported): (config)# ip cef load-sharing algorithm include-ports [source [destination]] 28
  • Static Routing • The way to install an entry in RIB manually • Usually overrides entries installed via dynamic routing protocols • Advantage: gives full control over path selection in your network • Main disadvantage: huge administrative burden • Syntax: (config)# ip route prefix mask [NH-IP | interface [NH-IP]] [distance] [track track] • Verification: # show ip route [static] 29
  • Static Routing (cont.) There are three different ways to configure where the traffic should go for specific prefix: • By specifying next-hop IP address • By specifying outgoing interface • By specifying both 30
  • Static Routing to next-hop • Recursive lookup is required to find outgoing interface • On multipoint interfaces resolution of next-hop IP address is required (ARP cache, Frame Relay/ATM mapping) • Static route is installed into RIB only if recursive lookup is successful (outgoing interface was found) • It will stay in RIB even if next-hop is covered only by valid default route 31
  • Static Routing to outgoing interface • Recursive lookup is not required because we know outgoing interface • On point-to-point interface we can send the packet right away • On multipoint interface first we need to find L2 address for destination IP • For every new destination IP address in the packet we will install entry in ARP cache • It can still work if Proxy Arp is enabled (which is enabled by default in IOS) • Static route is installed into RIB only if line protocol (for outgoing interface) is up • Use only for point-to-point interfaces! 32
  • Static Routing to outgoing interface and NH • Recursive lookup is not required because we know outgoing interface • On point-to-point interface we can send the packet right away • On multipoint interface first we need to find L2 address for next- hop IP address • Static route is installed into RIB only if line protocol of outgoing interface is up 33
  • Floating static routes • Floating static route is a route that has AD higher than default and is not installed into RIB under normal operation, because there is another preferred path • Once primary path fails floating static route can be installed • For example: • Primary static default route with AD 1 and tracking (based on IP SLA) or BFD • Secondary static default route with AD 2 or higher • Once tracking object/BFD goes down, primary route is deleted from RIB and secondary route is installed 34
  • Recursive lookup for static routes - exercise • R1 has one interface up/up with IP in subnet You configure the following: Question: Which static routes will be installed in RIB? 35
  • Recursive lookup for static routes - rule Answer: Rule: If the best route for the next hop also covers the entire address space of the static route under the question, it will NOT be installed. 36
  • Additional Resources • Inside Cisco IOS Software Architecture (Russ White) book • IP Routing FAQ • Switching Paths • Load Balancing with CEF • Troubleshooting load balancing with CEF • CAM vs TCAM • CEF polarization 37
  • Questions? 38