Cisco Express Forwarding - that thing that "just works". You don't really need to know anything about it...until it stops just working. Here's my notes.
1.1.b Identify Cisco express forwarding concepts
CEF maintains its tables to facilitate the routing of packets purely in memory, with no CPU overhead.
If the CPU can’t handle the packet, it “punts” the packet to the software for processing. Examples of things which require punting are:
- IP Header Options;
- The outgoing interface is not on supported media;
- The packet is destined for the router;
- Or the router has to send a reply (i.e. ICMP destination unreachable, etc).
1.1.b (i) RIB, FIB, LFIB, Adjacency table
RIB – Routing Information Base. The normal routing table.
show ip route. There can be multiple RIB’s on a router (VRF’s).
FIB – Forwarding Information Base. Used by CEF. It is more optimised and
much faster to parse. There is a FIB per VRF. Viewed with
show ip cef.
LFIB – The MPLS version of the FIB – a faster to parse version of the LIB.
Adjacency Table – Maintains the layer 2 forwarding information for each
FIB entry – meaning no ARP’s needed. Viewed with
show adjacency <interface> detail. “Adjacent” means reachable by a single layer 2
- Cache Adjacency – Correct outbound interface and correct MAC for FIB entry – the MAC is either the next hop, or the end host if on the same subnet;
- Receive Adjacency – Packets destined for the router (including broadcasts and multicasts);
- Null Adjacency – Packets to be sent to Null0 and dropped;
- Punt Adjacency – Packets which cannot be CEF switched and must be “punted” to a higher process;
- Glean Adjacency – Like a cache, but before the ARP – the router knows the next hop or knows it is not directly connected, but does not have a MAC address. Glean Adjacencies will trigger an ARP.
- Discard Adjacency – No layer 2 mapping exists so the packet is dropped. No ICMP Unreachable response is sent.
- Drop Adjacency – No layer 2 mapping exists so the packet is dropped. ICMP Unreachable IS sent.
1.1.b (ii) Load balancing Hash
- Prefix – Describes a destination IP network.
- Path – A valid route to reach a destination. Each path has a cost.
- Session – A unidirectional communication flow between two IP nodes. All packets in one session use the same source and destination address.
The Load Share Table contains 16 hash buckets which point to the paths. For equal cost paths, the buckets are split evenly (for 2 paths, 8 buckets each; for 3 paths, 5 buckets each + 1 disabled bucket). For unequal cost each path gets a different number of buckets according to the load sharing ratio.
Per-destination (or per-session) – Original Mode creates a 4 bit hash of source and destination IP which controls bucket assignment. Universal (default) mode adds an ID hash to this which is local to the router – this randomises the bucket assignments between routers across the path. Tunnel mode is for use in environments where tunnels are used – which means there are very few source/destination pairs.
ip cef load-sharing algorithm original
- ip cef load-sharing algorithm tunnel
ip cef load-sharing algorithm universal
Per-packet – Round robin each packet through the buckets. Not recommended as it causes out of sync data, which means more overhead for TCP and data loss for UDP.
- ip load-sharing per-packet
Per-port – Adds the layer 4 source and/or destination ports in the 4 bit hashing function to create more even distribution.
ip cef load-sharing algorithm include-ports destination
ip cef load-sharing algorithm include-ports source
ip cef load-sharing algorithm include-ports source destination
1.1.b (iii) Polarization concept and avoidance
If all routers are making the same decision based on a source/dest hash, if the first router allocates 2 streams to link 1, then every subsequent router will also allocate the same two streams to link 1. This causes some links to be permanently under-utilised, and could end up causing congestion on over-utilised links.
- Use different load balancing algorithms across different routers in the network so that each router makes an independent decision.
- Alternate between an even and off number of links between each network layer – if every layer is linked by two paths then distribution could be polarised – if the number of paths differs then the CEF bucket allocation will change.
- Use the universal algorithm – This adds a unique local ID into the hash algorithm meaning each router will make an independent decision.