CEF

  1. Cisco Express Forwarding (CEF)
    1. Process switching
    2. Fast switching
  2. Content-addressable memory (CAM)
  3. Ternary CAM (TCAM)
  4. FIB
  5. Adjacency types
  6. Load-balancing
    1. Polarization
    2. Polarization & failover
  7. ECMP group

Cisco Express Forwarding (CEF)

  • CAM table: if destination = own port, call FIB
  • FIB: address + mask, next-hop MAC, VLAN ID
  • TCAM: ACLs
  • operations in ASIC are parallel, match is found in single run
  • accelerated CEF: central FIB is cached on linecard
  • distributed CEF: each linecard has its own CEF
  • must be enabled on ingress interface, otherwise:
    • process switching: if egress interface is process switched
    • fast switching: if egress interface is fast switched or CEF-enabled
  • B-tree
    • 256 nodes on a level
    • leaves: pointer to adjacency entry or hash table (multipath)
    • hash table uses the number of buckets, divided by number of links in multipath

Process switching

  • done by CPU
  • ARP request/reply: CEF glean
  • IP packets that require a reply: TTL expired, MTU exceeded, ICMP redirect
  • relayed bcasts
  • IGP messages
  • CDP, LLDP
  • encryption, compression
  • ACL with log
  • NAT
  • legacy protocols (IPX, AppleTalk)
  • no entry in FIB or FIB is full
  • per-packet load-balancing

Fast switching

  • CPU + cache
  • per-destination load-balancing
  • cache aging:
    • 1/20 per minute
    • 1/5 per minute if memory is low
(config-if)# ip route-cache [cef]

Content-addressable memory (CAM)

  • if CAM gets full, switch → hub

Ternary CAM (TCAM)

  • ACL
    • 3 operations to verify a match
    • ACL search in one run
  • feature manager (FM) compiles ACEs into TCAM
  • entry:
    • value:
      • 134 bits
      • src + dst address, other info
    • mask:
      • 134 bits
      • bits of interest form value
    • result:
      • 134 bits
      • number (mapped to action)
  • table is sorted by mask
  • logical operation unit (LOU) performs comparisons
IP protocolIP ToSSrc IPSrc portSLOUDst IPDst portDLOUResult PTR
mask 1
src IP: 255.255.255.255
dst IP: 0.0.255.255		TCP192.168.199.1410.41.0.023→
UDP192.168.100.0→
mask 2:
dst IP: 0.0.0.255

LOU registers:

12
Agt 1024–
Brange start 1024range end 2047
# show platform tcam utilization

FIB

  • sorts the list: prefixes with longer mask – in the beginning
  • contains host routes
  • version: last modification
  • epoch: last flush&regenerate
  • references an entry in adjacency table
; CEF
# show ip cef

; fast-switching cache
# show ip cache

Adjacency types

  1. null
  2. drop
    • encapsulation failure
    • unresolved address (no intf):
      • recursive routing
      • next-hop is missing
    • unsupported protocol
    • no valid route
    • no valid adj:
      • no ARP reply
      • buffer is full
    • CRC error
  3. glean: ARP request is sent, no reply is yet received
  4. discard: reject because of ACL
  5. punt
    • send packets to CPU, CEF cannot process
    • incomplete adj: increases with ARP throttling timer tick
    • no_encap: no ARP reply, increases with every packet during ARP throttling
    • packet no supported
    • ICMP redirect
    • L3 engine, IP network/bcast address
    • IP options
    • ACL failure
    • fragmentation failure
# show adjacency [detail]
# show cef not-cef-switched

Load-balancing

  • modes:
    • per packet
      • no polarization
      • process switched
      • round-robin over egress links
    • per destination
      • default
      • hash(src, dst): CEF
      • hash(dst): fast switching
      • every flow follows a single path ⇒ no out-of-order packets
  • algorithm
    1. L4 ports: universal + L4 ports
    2. universal: default, original + seed
    3. tunnel: useful for polarized traffic across several tunnels
    4. original: unseeded, CEF polarization prone
  • MLS load-sharing
    1. default: src IP + dst IP + Universal ID
    2. full: src+dst IP+L4, prone to polarization
    3. simple: src IP + dst IP
    4. full simple: full with less HW utilization
  • universal ID makes hash over same data different on different devices ⇒ mitigates polarization (same hash into same buckets on every device, rest links are unused)
(config)# ip cef load-sharing universal|tunnel|include-ports <UNIVERSAL_ID>

; CEF starts counting packets and bytes
(config)# ip cef accounting per-prefix

(config)# mls ip cef load-sharing full|simple|full simple
; ingress interface, balancing using adjacency table
(config-if)# ip load-sharing per-packet|per-destination
# show ip cef exact-route <SRC_IP> <DST_IP>
# show ip cef summary
# show cef state
# debug ip cef drops

Polarization

  • hash is the same on every hop ⇒ matches same buckets ⇒ downstream flows are not distributed

Polarization & failover

ECMP group

  • prefixes with equal info in adjacency table
  • saves TCAM
  • per-prefix MPLS label allocation creates different ECMP groups: MPLS labels are different and labels are part of adjacency entry