How to Choose the Best Router Switching Path for Your Network (Part I)

Introduction
There are a plethora of switching paths available to various Cisco routers and Cisco IOS releases. Which is the best one for your network, and how do they all work? This white paper is an attempt to explain each of the following switching paths so you can make the best decision about which switching path fits your network.
First, examine the forwarding process itself. There are three steps to forwarding a packet through a router:
1. 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.
2.Rewrite the Media Access Control (MAC) header on the packet so it will successfully reach its next hop.
3.Each of these steps is critical for the packet to reach its destination.

Note: Throughout this document, we use the IP switching path as an example; virtually all the information provided here is applicable to equivalent switching paths for other protocols, if they exist.

Process Switching
Process switching is the lowest common denominator in switching paths; it is available on every version of IOS, on every platform, and for every type of traffic being switched. Process switching is defined by two essential concepts:
The forwarding decision and information used to rewrite the MAC header on the packet are taken from the routing table (from the routing information base, or RIB) and the Address Resolution Protocol (ARP) cache, or from some other table that contains the MAC header information mapped to the IP address of each host that is directly connected to the router.
· The packet is switched by a normal process running within IOS. In other words, the forwarding decision is made by a process scheduled through the IOS scheduler and running as a peer to other processes on the router, such as routing protocols. Processes that normally run on the router aren't interrupted to process switch a packet.
The figure below illustrates the process switching path.

Examine this diagram in more detail:
The interface processor first detects there is a packet on the network media, and transfers this packet to the input/output memory on the router.
1.The interface processor generates a receive interrupt. During this interrupt, the central processor determines what type of packet this is (assume it is an IP packet), and copies it into processor memory if necessary (this decision is platform dependent). Finally, the processor places the packet on the appropriate process' input queue and the interrupt is released.
2.The next time the scheduler runs, it notes the packet in the input queue of ip_input, and schedules this process to run.
3.When ip_input runs, it consults the RIB to determine the next hop and the output interface, then consults the ARP cache to determine the correct physical layer address for this next hop.
4.ip_input then rewrites the packet's MAC header, and places the packet on the output queue of the correct outbound interface.
5.The packet is copied from the output queue of the outbound interface to the transmit queue of the outbound interface; any outbound quality of service takes place between these two queues.
6.The output interface processor detects the packet on its transmit queue, and transfers the packet onto the network media.
7.Almost all features that effect packet switching, such as Network Address Translation (NAT) and Policy Routing, make their debut in the process switching path. Once they have been proven, and optimized, these features may, or may not, appear in interrupt context switching.

Interrupt Context Switching
Interrupt context switching is the second of the primary switching methods used by Cisco routers. 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 can be scheduled.
The processor uses some form of route cache to find all the information needed to switch the packet.
The following figure illustrates interrupt context switching.

Examine this diagram in more detail:
The interface processor first detects there is a packet on the network media, and transfers this packet to the input/output memory on the router.
1.The interface processor generates a receive interrupt. During this interrupt, the central processor determines what type of packet this is (assume it is an IP packet), and then begins to switch the packet.
2.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 this destination is, and finally, what MAC header the packet should have to successfully reach the next hop. The processor uses this information to rewrite the packet's MAC header.
3.The packet is now copied to either the transmit or output queue of the outbound interface (depending on various factors). The receive interrupt now returns, and the process that was running on the processor before the interrupt occurred continues running.
4.The output interface processor detects the packet on its transmit queue, and transfers the packet onto the network media.
5.The first question that comes to mind after reading this description is "What is in the cache?" There are three possible answers, depending on the type of interrupt context switching:
· Fast Switching
· Optimum Switching
· Cisco Express Forwarding
We will look at each of these route cache types (or switching paths) one at a time.

Fast Switching
Fast switching stores the forwarding information and MAC header rewrite string using a binary tree for quick lookup and reference. The following figure illustrates a binary tree.

In Fast Switching, the reachability information is indicated by the existence of a node on the binary tree forthe destination of the packet. The MAC header and outbound interface for each destination are stored as part
of the node's information within the tree. The binary tree can actually have 32 levels?the tree above is extremely abbreviated for the purpose of illustration.
To search a binary tree, you simply start from the left (with the most significant digit) in the (binary) number you are looking for, and branch right or left in the tree based on that number. For instance, if you're looking for the information related to the number 4 in this tree, you would begin by branching right, because the first binary digit is 1. You would follow the tree down, comparing the next digit in the (binary) number, until you reach the end.

Characteristics of the Fast Switching
Fast Switching has several characteristics that are a result of the binary tree structure and the storage of the MAC header rewrite information as part of the tree nodes.
Since there is no correlation between the routing table and the fast cache contents (MAC header
rewrite, for example), building cache entries involves all the processing that must be done in the
process switching path. Therefore, fast cache entries are built as packets are process switched.
· Since there is no correlation between the MAC headers (used for rewrites) in the ARP cache and the structure of the fast cache, 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 (the MAC header and
outbound interface information are expected to be within the node), so all routing recursions must be resolved while a fast cache entry is being built. In other words, recursive routes can't be resolved within the fast cache itself.

Aging Fast Switching Entries
To keep the fast switching entries from losing their synchronization with the routing table and ARP cache, and
to keep unused entries in the fast cache from unduly consuming memory on the router, 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
What prefix length does the fast switching build entries for if it can only build to one prefix length for every
destination? Within the terms of the fast switching, a destination is a single reachable destination within the


routing table, or a major network. 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 Multiprotocol over ATM virtual circuit (MPOA VC), always cache to/32.
· If the network is not subnetted (it is 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 longest prefix length in this major net.

Load Sharing
Fast switching is entirely destination based; load sharing occurs on a per−destination basis. If there are multiple equal cost paths for a particular 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
Optimum switching stores the forwarding information and the MAC header rewrite information in a 256 way multiway tree (256 way mtree). Using an mtree reduces the number of steps which must be taken when looking up a prefix, as illustrated in the next figure.



Each octet is used to determine which of the 256 branches to take at each level of the tree, which means there are, at most, 4 lookups involved in finding any destination. For shorter prefix lengths, only one−three lookups may be required. 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. Optimum Switching also determines the prefix length for each cache entry in the same way as fast switching.