Cisco Cram or: How I Learned to Stop Lolling and Love the Book: Notes: Choosing the Best Router Switching Path

Introduction

A plethora of switching paths available in various Cisco IOS releases.
Which is the best, and how do they all work?
Three steps to forwarding a packet through a router:

Determine if the packet's destination is reachable.
Determine the next hop toward the destination, and the interface through which that next hop is reachable.
Rewrite the MAC header on the packet so it will successfully reach its next hop.

Process Switching

Lowest common denominator in switching paths.
Available on every version of IOS, on every platform, and for every type of traffic being switched.
Defined by two essential concepts:

The forwarding decision and MAC rewrite information are taken from the routing table (RIB) and ARP cache (or another Layer 3 to Layer 2 mapping table).
The packet is switched by a normal process running within IOS. The forwarding decision is made by a process scheduled through the IOS scheduler. Processes that normally run on the router are not interrupted to process switch a packet.

Examine the diagram in more detail:

The interface processor first detects there is a packet, and transfers this packet to the input/output memory on the router.
The interface processor generates a receive interrupt. During this interrupt, the central processor determines the type of packet (assume an IP packet), and copies it into processor memory if necessary. Finally, the processor places the packet on the appropriate process' input queue and the interrupt is released.
When the scheduler runs next, it notes the packet in the input queue of IP Input, and schedules this process to run.
When IP Input runs, it consults the RIB to determine the next hop and the output interface, then refers to the ARP cache to find the MAC information.
IP Input then rewrites the MAC header, and places the packet on the output queue of the correct outbound interface.
The packet is copied from the output queue to the transmit queue. Any outbound QoS is applied between these two queues.
The outbound interface processor detects the packet on its transmit queue, and transfers the packet.

Interrupt Context Switching

The primary differences between interrupt context switching and process switching are:

The process currently running on the processor is interrupted to switch the packet. Packets are switched on demand, rather than switched only when the IP Input process is scheduled.
The processor uses some form of route cache to find all the information needed to switch the packet.

In more detail:

The interface processor first detects a packet, and transfers it to the input/output memory on the router.
The interface processor generates a receive interrupt. During this interrupt, the central processor determines the type of packet (assume an IP packet), and then begins to switch the packet.
The processor searches the route cache to determine if the packet's destination is reachable, what the output interface should be, what the next hop towards the destination is, and what MAC header the packet should have. The processor rewrites the MAC header using this information.
The packet is copied to the transmit or output queue of the outbound interface (depending on various factors). The process that was running on the processor before the interrupt occurred continues running.
The output interface processor detects the packet on its transmit queue, and transfers it.

What is this cache?

Three possible answers, depending on the type of interrupt context switching:

Fast Switching
Optimum Switching
Cisco Express Forwarding

Fast Switching

Stores the forwarding information and MAC header rewrite string using a binary tree for quick lookup and reference.

The binary tree can actually have 32 levels (the illustration is extremely abbreviated).
To search the binary tree, the binary string is read from left to right (starting from the most significant bit), and branching left or right in the tree based on the number.
The bits are compared in order, until the end is reached.

Results of the binary tree structure and the storage of MAC header rewrite information as part of the tree nodes:

Building the cache entries must be done in process switching. Fast cache entries are built as packets are process switched.
When the ARP table changes, some portion of the fast cache must be invalidated (and recreated through the process switching of packets).
The fast cache can only build entries at one depth (one prefix length) for any particular destination within the routing table.
There is no way to point from one entry to another within the fast cache. Recursive routes cannot be resolved within the fast cache itself. To keep fast switching entries from losing their synchronization with the routing table and ARP cache, and to keep unused entries from unduly consuming memory, 1/20th of the fast cache is invalidated, randomly, every minute. If the routers memory drops below a very low watermark, 1/5th of the fast cache entries are invalidated every minute.

Fast Switching Prefix Length

The rules for deciding what prefix length to build a given cache entry are:

If building a fast policy entry, always cache to /32.
If building an entry against an MPOA VC, always cache to /32.
If the network is not subnetted (it's a major network entry):

if it is directly connected, use /32
otherwise use the major net mask

If it is a supernet, use the supernet's mask
If the network is subnetted:

if directly connected, use /32
if there are multiple paths to this subnet, use 32
in all other cases, use the longest prefix length in this major net

Fast switching is entirely destination-based; load sharing occurs on a per-destination basis.
If there are multiple equal-cost paths for a destination network, fast cache has one entry for each host reachable within that network, but all traffic destined to a particular host follows one link.

Optimum Switching

Stores the forwarding information and the MAC header rewrite information in a 256 way multiway tree (256 way mtree).
Looking up a prefix takes fewer steps when using an mtree.

Each octect is used to determine which of the 256 branches to take at each level of the tree.
There are, at most, 4 lookups in finding any destination.
The MAC header rewrite and output interface information are stored as part of the tree node, so cache invalidation and aging still occur as in the fast switching.
Determines the prefix length for each cache entry in the same way as fast switching.

Cisco Express Forwarding (CEF)

Also uses a 256 way data structure but does not use a tree.
Uses a trie, i.e. the searched information is actually not in the data structure but stored in a separate datastrucutre, and the trie simply points to it.
Instead of storing the outbound interface and MAC header rewrite within the tree itself, CEF stores this information in a separate data structure called the adjacency table.

The separation of the reachability information (FIB) and the forwarding information (the adjacency table) provides a number of benefits:

Both can be built without process switching packets.
MAC header rewrite is not stored in cache entries, so changes do not require invalidation of cache entries.
Can point directly to the forwarding information, rather than to a the recursed next hop.

Essentially, all cache aging is eliminated, and the cache is pre-built based on the information contained in the routing table and ARP cache.
No need to process switch any packets to build a cache entry.

Entries in The Adjacency Table

The adjacency table can contain entries other than MAC header rewrite strings and outbound interface information:

cache - A MAC heaeder rewrite string and outbound interface used to reach a particular adjacent host or router.
receive - Packets destined to this IP address should be received by the router (broadcast addresses and interface IP addresses).
drop - Packets destined to this IP address should be dropped (denied by an access-list, or routed to NULL interface).
punt - CEF cannot switch this packet; pass it to the next best switching method (generally fast switching).
glean - The next hop is directly connected, but there are no MAC header rewrite strings currently available.

How are glean adjacencies built and used?

A CEF router attached to a broadcast network builds a number of adjacency table entries by default.
Four adjacency table entries are built by default: three receives, and one glean.

Receive entries represent a broadcast address or an address configured on the router.
Glean entry represents the remainder of the address space on the connected network.
If a packet to host 10.1.1.50 is received, the router attempts to switch it, and finds it resolved to the glean adjacency.
CEF signals that an ARP cache entry is need for 10.1.1.50.
The ARP process sends an ARP request, and the appropriate adjacency table entry is built from the new ARP cache information.
The next packet to 10.1.1.50 is switched through the new adjacency.

10.1.1.0/24, version 17, attached, connected
0 packets, 0 bytes
via Ethernet2/0, 0 dependencies
    valid glean adjacency
10.1.1.0/32, version 4, receive
10.1.1.1/32, version 3, receive
10.1.1.50/32, version 12, cached adjacency 208.0.3.2
0 packets, 0 bytes
via 208.0.3.2, Ethernet2/0, 1 dependency
    next hop 208.0.3.2, Ethernet2/0
    valid cached adjacency
10.1.1.255/32, version 5, receive

CEF Load Sharing

Also takes advantage of the separation between the CEF table and the adjacency table.
Better form of load sharing than any other interrupt context switching mode.
A loadshare table is inserted between the CEF table and the adjacency table.

CEF table points to the loadshare table, which contains pointers to the adjacency table entries for available parallel paths.
The source and destination addresses are passed through a hash algorithm to determine which loadshare table entry to use for each packet.
Each loadshare table has 16 entries that are distributed between the available paths according to the traffic share counter in the routing table.
If the traffic share counter is 1 (as is the case of multiple equal-cost paths), each possible next hop receives an equal number of pointers from the loadshare table.
If the number of available paths is not evenly divisible into 16, some paths will have more entries than others.
From IOS Realease 12.0, the number of entries is reduced to provide a proportionate number of loadshare table entries for each path.
For example, only 15 loadshare table entries are used for three equal-cost paths.

Which Switching Path Is The Best?

Cisco Express Forwarding
CEF is definitely faster and better than any other switching mode.
Recommended if the IOS supports it.
Particularly true if there are parallel links across which traffic should be load-shared.
As a second option, use fast switching.
Avoid process switching.

References

How to Choose the Best Router Switching Path for Your Network

Cisco Cram or: How I Learned to Stop Lolling and Love the Book

Tuesday, December 16, 2014

Notes: Choosing the Best Router Switching Path