IP switching per-packet and per-destination

IP switching is the internal mechanism used by Cisco IOS to forward packets through a router. Available mechanisms include process switching, fast switching, and Cisco Express Forwarding. Depending on which of the three mechanisms is used to switch the majority of packets, the overall system performance and load balancing is affected.
IP switching mechanisms support two general modes, per-packet and per-destination. The following table outlines the advantages and disadvantages of both modes.

	Per-Destination	Per-Packet
IP Switching Mechanism	Fast switching and Cisco Express Forwarding per-destination.	Process switching and Cisco Express Forwarding per-packet.
Advantages	With fast switching, packets for a given destination are guaranteed to take the same path even if multiple paths are available. With Cisco Express Forwarding switching, packets for a given source-destination host pair are guaranteed to take the same path, even if multiple paths are available. Traffic destined for different pairs tend to take different paths.	Path utilization with per-packet load balancing is good because per-packet load balancing allows the router to send successive data packets over paths without regard to individual hosts or user sessions. It uses the round-robin method to determine which path each packet takes to the destination
Disadvantages	With fast switching, per destination switching may result in unequal load sharing because packets to one destination always follow the same path. Cisco Express Forwarding switching may result in unequal distribution with a small number of source-destination pairs. Per-destination load balancing depends on the statistical distribution of traffic; load sharing becomes more effective as the number of source-destination pairs increase.	Packets for a given source-destination host pair might take different paths, which could introduce reordering of packets. This is not recommended for Voice over IP (VoIP) and other flows that require in-sequence delivery.

Difference between PROCESS SWITCHING, FAST SWITCHING and CEF

Difference between PROCESS SWITCHING, FAST SWITCHING and CEF

Process Switching

Processed switched relies on the processor to switch packets. With this every packet is inspected by the processor. The original switching mechanism available on Cisco routers was process switching. However, process switching is very slow because it must find a destination in the routing table. Process switching must also construct a new Layer 2 frame header for every packet. As a result, process switching is no longer widely used in modern networks.

With process switching, when a packet comes in, the scheduler calls a process that examines the routing table, determines which interface the packet should be switched to and then switches the packet. The problem is, this happens for the every packet seen on every interface. This is why it is termed as slow.

The benefit of process switching is that is available on every Cisco router platform, regardless of size or age. SNMP traps from the router and telnet packets destined for the router are always process-switched.

There are no specific commands to enable Process switching just disable fast and CEF switching. 

Fast Switching

Cisco IOS platforms have the capability to overcome the slow performance of process switching. The platforms support several switching mechanisms that use a cache to store the most recently used destinations. Fast switching process-switching the first packet in a conversation, then stores the information learned about the destination for the packet in a table called route cache.

A cache uses a faster searching mechanism than process switching does while storing the entire Layer 2 frame header to improve the encapsulation performance. In cache-driven switching, an entry is created in the cache when the first packet whose destination is not found in the fast-switching cache is process switched. Rest of the packets are forwarded per destination basis. This is how the cache improves performance.

With the first packet, the router adds an entry to the fast-switching cache, sometimes called the route cache. The cache has the destination IP address, the next-hop information, and the data link header information (MAC) that needs to be added to the packet before forwarding. Future packets to the same destination address match the cache entry, so it takes the router less time to process and forward the packet.

Fast switching has a few drawbacks. The first packet must be process switched. The cache entries are timed out relatively quickly, because otherwise the cache could get overly large as it has an entry per each destination address, not per destination subnet/prefix. Also, load balancing can only occur per destination with fast switching not per packet basis.

While in the case of Fast Switching the IOS builds the Fast Switching cache entry after switching the first packet, and thus it will depend on the egress interface, thus if the ingress interface was Process or Fast Switching enabled, and the egress interface is Fast Switching enabled, thus the packet will be Fast switched on an interface that is currently process-switching, the interface command "ip route-cache" without arguments will enables fast switching.

Cisco Express Forwarding (CEF)

The most recent and preferred Cisco IOS platform switching mechanism is CEF, which incorporates the best of the previous switching mechanisms. One of the benefits of CEF is that this mechanism supports per-packet load balancing, which was previously supported only by process switching. CEF also supports per-source or per-destination load balancing, fast destination lookup, and many other features that are not supported by other switching mechanisms.

CEF uses a Forwarding Information Base (FIB) to make IP destination prefix-based switching decisions. The FIB is conceptually similar to a routing table or information base. It maintains a mirror image of the forwarding information contained in the IP routing table. When routing or topology changes occur in the network, the IP routing table is updated, and those changes are reflected in the FIB. The FIB maintains next-hop address information based on the information in the IP routing table.

Because there is a one-to-one correlation between FIB entries and routing table entries, the FIB contains all known routes and eliminates the need for route cache maintenance that is associated with switching paths such as fast switching.

CEF is enabled by default on all modern Cisco routers but if one wants to enable it on older routers "ip cef" command is used in global configuration mode. It can also be configured interface basis with command "ip route-cache cef". This command will load balance packets across

equal cost links. Per-destination load balancing is default but CEF support per destination load balancing and per-packet load balancing both, command "ip load-sharing <per-packet/per-destination>" is used.

If fast switching and CEF are both enabled, CEF will try to switch the packet first. If CEF cannot switch the packet, it will direct the packet to the next best available switching path-fast switching. If fast switching cannot process the packet, the router wills process-switch the packet. If all other switching paths are turned off, the router must process-switch all packets. "no ip route-cache” command will disable

CEF and fast switching both. CEF Switching is all about the ingress interface and has nothing to do with the egress interface because FIB is created before a packet is forwarded.

The ip cef global configuration command enables CEF for all interfaces on a Cisco router. The "no ip route-cache cef" interface subcommand can then be used to selectively disable CEF on an interface. On many of the higher-end Cisco platforms, CEF processing can be distributed to the linecards. Similarly, Cisco multilayer switches use CEF for Layer 3 forwarding, by loading CEF tables into the forwarding ASICs.

NOTE: IPv4 fast switching is removed with the implementation of the Cisco Express Forwarding infrastructure enhancements for Cisco IOS For these and later Cisco IOS releases, switching path are Cisco Express Forwarding switched or process switched. This makes the switching decision easier for future development of software features. Starting with the implementation of the Cisco Express Forwarding infrastructure enhancements and the removal of IPv4 fast switching, components that do not support Cisco Express Forwarding will work only in process switched mode.

CEF and load sharing

Top of Form

CEF and load sharing

Load-sharing is one of the clumsy areas that is full of confusing parts. In this post we should be covering its ABCs, and latter on we should be covering more parts in details. We chose the name “CEF and load sharing” as the post name due to the main role that CEF plays when talking about load sharing.

In IP routing context the forwarding/switching mechanism that the router uses is the actual controller of the load sharing process (data/forwarding plane operation), having multiple routes in the routing table has no significance on how exactly will load sharing be done, you might be left with poor load sharing or no load sharing at all, although you have multiple routes for a certain destination in the routing table.

The routing protocols are responsible for placing multiple paths in the routing table in the first place (control plane operation), by default all the IGPs are capable of inserting 4 equal cost paths, while BGP defaults to only 1 (BGP behaves completely different than the IGPs, we should be covering load-sharing with BGP in details in a later post). To control the maximum paths allowed per routing protocol we can use the maximum-paths command (The maximum was 4 in IOS releases earlier than 11.0, 8 with IOS Release 12.0S based software, 16 with IOS Release 12.3T based software, and 32 with IOS Release 12.2S based software.

NOTE This post is not meant to explain CEF operation, we’ll only be focusing on CEF load-sharing, however we might consider to have a dedicated CEF inside out post later.

The most popular forwarding/switching mechanisms with Cisco routers are; Process switching (performs per-packet load-sharing), fast switching (performs per-destination load-sharing) and CEF (can do both per-packet and per-destination (completely different than fast switching per-destination load-sharing), plus also a new flavor which is per-port load-sharing).

NOTE According to Cisco, IPv4 fast switching is removed with the implementation of the Cisco Express Forwarding infrastructure enhancements for Cisco IOS 12.2(25)S-based releases and Cisco IOS Release 12.4(20)T. For these and later Cisco IOS releases, switching path are Cisco Express Forwarding switched or process switched. This makes the switching decision easier for future development of software features. Starting with the implementation of the Cisco Express Forwarding enhancements and the removal of IPv4 fast switching, components that do not support Cisco Express Forwarding will work only in process switched mode.

Load-sharing with CEF

For each destination with multiple equal cost paths (or unequal-cost in the case of EIGRP using variance, or with BGP using the BGP Link Bandwidth feature and also in the case of MPLS-TE) the router creates a 16 hash buckets, each pointing to one of the available paths.

The load sharing is controlled by the ratio of the number of buckets pointing to each path (outgoing interface), with equal-cost paths the buckets are fairly distributed (two equal cost paths results in 8 buckets per each path, three equal cost paths results in 5 per each (yes, one bucket is omitted), 4 equal cost paths results in 4 per each, and so on). While with unequal-cost scenarios each path will be associated with different number of buckets (according to the load sharing ratio).

CEF has three load-sharing options:

• per-destination (per-session):

I prefer to name it per-session – as stated in the show ip cef x.x.x.x internal command output – since it is actually done based on both the source and the destination IP addresses in the IP packet rather than solely the destination, by hashing both into a 4-bit hash value that is used to select the outgoing interface) – This is the default CEF load sharing option.

It is clear that per-destination load-sharing performs statistical distribution of traffic, and accordingly load sharing becomes more effective as the number of source/destination pairs increases as compared to lower number of source/destination pairs. Obviously this might result in having one link overloaded while the other(s) underutilized, if a relatively heavy session flows between a certain source/destination pair over this link.

The hash calculation depends on the algorithm used. The original algorithm uses only the source and destination IP addresses to compute a 4-bit hash value, giving 16 probabilities, and thus choosing an outgoing bucket from the 16 available buckets pointing to one of the outgoing paths, this results in all the routers in the network running the same algorithm with the same results, which introduced a load sharing hitch called CEF Load-Sharing Polarization (you can see a good example for this in Cisco press book “Cisco Express Forwarding”). To circumvent this behavior the universal algorithm (the default in current IOS versions) adds a 32-bit router-specific value to the hash function (called Fixed ID, which can be manually controlled – a router uses its highest loopback IP address as this value when booting) and thus seeding the hash function on each router with a unique ID, ensuring that the same source/destination pair will hash into a different 4-bit value on different routers along the path and thus provides a better network wide load sharing and circumvent the Polarization issue.

NOTE There is a third available algorithm called the tunnel algorithm, I couldn’t find or understand its anatomy, but Cisco stated that this algorithm is meant to solve load sharing when tunneling techniques such as MPLS, GRE and L2TP are in operation, since with tunneling the traffic pattern is taken down to a small number of sessions (between the tunnel head/tail ends) which will introduce another form of traffic polarization. This algorithm also uses a unique per-router ID to work around this issue, again I can’t find more details about this algorithm, but if I do I’ll let you know.

• per-packet

Packets are handled in a round-robin fashion, ensuring that the traffic is balanced over multiple links. However, using Per-packet load sharing is not generally recommended, because it most commonly results in out-of-order packets, affecting TCP traffic throughput (since TCP will bother to fix the out-of-order) and UDP data loss (since UDP will not bother to fix the out-of-order) and to make things more scary out-of-order packets might be interpreted as an attack by firewalls.

The default CEF load sharing mode is per-destination, and we can change this using the ip load-sharing per-packet interface command on the outgoing interfaces involved.

NOTE Since load sharing decisions are made on the outbound interfaces, thus either choosing to do per-packet or per-destination load sharing should be done on the outbound interfaces.

• per-port (per-flow)

This is the most adequate option (was introduced with IOS 12.4(11)T release) with networks with low number of sources/destinations with the majority of the traffic between hosts that use different port numbers, commonly seen with Real-Time Protocol (RTP) streams, it simply adds the layer 4 source or destination ports or both in the CEF hashing function. This option is enabled via the ip cef load-sharing algorithm include-ports command in the global configuration.

The most common scenario with this option as the only effective solution is when having a subnet of hosts NATed to a single IP then having a router with multiple paths in the path to their traffic destination, per-destination option is obviously useless in this case if all the hosts are communicating with a single destination, since it is always a single source/destination pair, and accordingly if the layer 4 ports are involved in the hashing function this would enhance the load sharing process.

I hope that I’ve been informative.

Cisco Express Forwarding

  Cisco Express Forwarding (CEF) is a packet-switching technique that is the default for many of Cisco’s router over the last ten years. It provides the ability to switch packets through a device in a very quick efficient way while also keeping the load on the router’s processor low. This way the route process can be tasked with dealing with other duties that require larger amounts of processor time (Quality of Service, Encryption, etc.). This article takes a brief look at the different structures that are used by CEF and how they are built and interrelate.

Benefits

CEF offers the following benefits:

•Improved performance—CEF is less CPU-intensive than fast switching route caching. More CPU processing power can be dedicated to Layer 3 services such as quality of service (QoS) and encryption.

•Scalability—CEF offers full switching capacity at each line card when dCEF mode is active.

•Resilience—CEF offers an unprecedented level of switching consistency and stability in large dynamic networks. In dynamic networks, fast-switched cache entries are frequently invalidated due to routing changes. These changes can cause traffic to be process switched using the routing table, rather than fast switched using the route cache. Because the Forwarding Information Base (FIB) lookup table contains all known routes that exist in the routing table, it eliminates route cache maintenance and the fast-switch or process-switch forwarding scenario. CEF can switch traffic more efficiently than typical demand caching schemes.

 Cisco Express Forwarding Concepts

Cisco Express Forwarding components:

Information conventionally stored in a route cache is stored in several data structures for CEF switching. The data structures provide optimized lookup for efficient packet forwarding. The two main components of CEF operation are described in the following sections:

•Forwarding Information Base

•Adjacency Tables

CEF Operation Modes

CEF can be enabled in one of two modes described in the following sections:

•Central CEF Mode

•Distributed CEF Mode

Central CEF Mode

When CEF mode is enabled, the CEF FIB and adjacency tables reside on the RP, and the RP performs the express forwarding. You can use CEF mode when line cards are not available for CEF switching or when you need to use features not compatible with dCEF switching. 

Distributed CEF Mode

When dCEF is enabled, line cards, such as VIP line cards or GSR line cards, maintain an identical copy of the FIB and adjacency tables. The line cards perform the express forwarding between port adapters, relieving the RSP of involvement in the switching operation.

dCEF uses an Inter Process Communication (IPC) mechanism to ensure synchronization of FIB tables and adjacency tables on the RP and line cards.

 RIB, FIB, LFIB, Adjacency table

Control Plane - maintains routing information:

• Routing Information Base(RIB/Routing table) operates in software - sh ip route
• Directly connected
• Static Routes
• Dynamic routing information
• ARP Table  sh arp

Data/Forwarding Plane - responsible for moving data in and out(ingress/egress):

• Forwarding Information Base(FIB) - sh ip cef
• Built from RIB best routes and the ARP table
• RIB changes are reflected in FIB
• Adjacency Table - sh adjacency
• Contains L2 next hop information for all entries in FIB
• Label Forwarding Information Base(LFIB)
• Used for labeled packets(MPLS)

Adjacency Types:

• Glean - FIB maintains a subnet prefix and needs additional ARP information for specific hosts
• Null - Packets destined for Null0 are dropped(Bit Bucket/Black Hole/Discard/etc)
• Drop - Device drops packets that can't be forwarded normally(by default generates ICMP unreachables)
• Encapsulation Failure
• Unresolved Address
• Unsupported Protocol
• No Valid Route
• No Valid Adjacency
• Checksum Error
• Discard - Device discards packets based on policy(by default does not generate and ICMP unreachables)
• Unassigned Loopback IP addresses that belong to the interface subnet but are unassigned are also discarded; for example lo0 is assigned 1.1.1.1 255.255.255.0, 1.1.1.2-1.1.1.254 will be discard adjacencies
• Punt - CEF cannot forward the traffic, so packets are sent to the Control Plane(L3) for processing

CEF Load Balancing Hash

 CEF supports TCP/IP load balancing over parallel links, if there are multiple paths to the same  destination, the device will create a 16 row hash table with individual path pointers; sh ip cef <prefix> internal

• per-destination mode(default) - All packets to a given destination follow the same path, preserving packet order.  Can cause unequal usage of the links if the majority of traffic is               destined for one host.
• source and destination IP address is hashed and pointed to a specific entry in the adjacency table
• per-packet mode(ip load-sharing per-packet) - Guarantees equal load across links, but may cause an out of order packet situation 
• packets are distributed round robin across all paths

Polarization Concept and Avoidance

Polarization occurs when all devices use the same hash to reach the same destination.  Per-packet load sharing could be used as a solution, but due to the negative effect of out of order packets, it is not the preferred solution.

The preferred solution is to alternate between hashing inputs at each layer of the network.  The default load sharing is Source IP, Dest IP and unequal weights of the links

• mls ip cef load-sharing simple - Source IP and Dest IP equal weights
• mls ip cef load-sharing full - Source IP, Dest IP, and L4 port number unequal weights
• mls ip cef load-sharing full simple - Source IP, Dest IP, and L4 port number equal weight