Tag Archives: 1.1b

1.1.b Identify Cisco express forwarding concepts

RIB and FIB

Routers and MLS were once centralized, cache based systems combining the control and data planes. The control plane is comprised of the technologies that create and maintain the routing table. The data plane is comprised of the technologies that move data from ingress to egress.

This architecture has since split into the RIB and FIB (Routing Information Base, and Forwarding Information Base). The RIB operates in software, and the FIB takes the RIB’s best routes and places them in it’s own data construct which resides in faster hardware resources. Cisco’s implementation of this architecture is know as CEF (Cisco Express Forwarding).

Process Switching, Fast Switching and the evolution to CEF

Process Switching requires the Router/MLS to process every packet to make a forwarding decision.

Fast Switching evolved from Process Switching, whereby the initial packet’s forwarding decision is still derived from the Route Processor, but that destination is then held in cache for subsequent forwarding precluding the processor’s involvement.

With CEF, Cisco took fast switching a step further by introducing the FIB and Adjacency tables into the equation.

The FIB is a mirror image of the IP routing table. Changes to the routing table and next hop ip’s are reflected in the FIB. Fast switching route cache maintenance is thereby eliminated.

The adjacency table is populated with l2 next hop addresses for all FIB entries, hence adjacency. When an adjacency is established, as through ARP, a link layer header for that adjacency is stored in the adjacency table.

For a thorough overview click the link below.

http://www.cisco.com/en/US/docs/ios-xml/ios/ipswitch_cef/configuration/12-4t/isw-cef-overview.html

1.1.b Identify Cisco express forwarding concepts

1.1.b Identify Cisco express forwarding concepts
1.1.b (i) RIB, FIB, LFIB, Adjacency table
1.1.b (ii) Load balancing Hash
1.1.b (iii) Polarization concept and avoidance

http://www.cisco.com/en/US/tech/tk827/tk831/technologies_tech_note09186a0080c15610.shtml

Here is a description of how the hashing algorithm works:

When there are only two paths, the switch/router performs an exclusive-OR (XOR) operation on the lower-order bits (one bit when either of two links need to be selected, two bits for 3-4 links, and so on) of the SIP and DIP. The XOR operation of the same SIP and DIP always results in the packet use of the same link.

The packet then passes onto the distribution layer, where the same hashing algorithm is used along with the same hash input, and picks a single link for all flows, which leaves the other link underutilized. This process is called CEF polarization (use of the same hash algorithm and same hash input which results in the use of a single Equal-Cost Multi-Path (ECMP) link for ALL flows)

http://ccieordie.com/?cat=74 

fib_adj

http://www.cisco.com/en/US/products/hw/modules/ps2033/prod_technical_reference09186a00800afeb7.html

How CEF load balancing works

CEF is an advanced Layer 3 switching technology inside a router. Usually a router uses a route cache to speed up packet forwarding. The route cache is filled on demand when the first packet for a specific destination needs to be forwarded. If the destination is on a remote network reachable via a next hop router, the entry in the route cache is consisting of the destination network. If parallel paths exist this does not provide load balancing, as only one path would be used. Therefor the entry in the route cache now relates to a specific destination address, or host. If multiple hosts on the destination network are receiving traffic a route cache entry for each individual host is made, balancing the hosts over the available paths. This provides per destination load balancing. The problem that arises is that for a backbone router carrying traffic for several thousands of destination hosts a respective number of cache entries is needed. This consumes memory and makes cache maintenance a demanding task. In addition the decision about which path to use is done at the time the route-cache is filled, and it is based on the utilization of the individual links at that point in time. However the amount of traffic on individual connections can change over time, possibly leading to a situation where some links carry mostly idle connections and others are congested. CEF takes a different approach as it calculates all information necessary for the forwarding task in advance and decouples the forwarding information from the next hop adjacency, which allows for effective load balancing.

The two main components of CEF operation are the

Forwarding Information Base

Adjacency Tables

Forwarding Information Base

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 earlier switching paths such as fast switching and optimum switching.

Adjacency Tables

Network nodes in the network are said to be adjacent if they can reach each other with a single hop across a link layer. In addition to the FIB, CEF uses adjacency tables to prepend Layer 2 addressing information. The adjacency table maintains Layer 2 next-hop addresses for all FIB entries.

The adjacency table is populated as adjacencies are discovered. Each time an adjacency entry is created (such as through the ARP protocol), a link-layer header for that adjacent node is precomputed and stored in the adjacency table. Once a route is determined, it points to a next hop and corresponding adjacency entry. It is subsequently used for encapsulation during CEF switching of packets. A route might have several paths to a destination prefix, such as when a router is configured for simultaneous load balancing and redundancy. For each resolved path a pointer is added for the adjacency corresponding to the next-hop interface for that path. This mechanism is used for load balancing across several paths. For per destination load balancing a hash is computed out of the source and destination IP address. This hash points to exactly one of the adjacency entries in the adjacency table, providing that the same path is used for all packets with this source/destination address pair. If per packet load balancing is used the packets are distributed round robin over the available paths. In either case the information in the FIB and adjacency tables provide all the necessary forwarding information, just like for non-load balancing operation. The additional task for load balancing is to select one of the multiple adjacency entries for each forwarded packet.

1.1.b Identify Cisco express forwarding concepts

On Page 59, Router Security Strategies: Securing IP Network Traffic Planes:

The adjacency table contains information necessary for encapsulation of the packets that must be sent to given next-hop network devices. CEF considers next-hop devices to be neighbors if they are directly connected via a shared IP subnet.
Each adjacency entry stores pre-computed frame headers used when forwarding a packet using a FIB entry referencing the corresponding adjacency entry. The adjacency table is populated as adjacencies are discovered. Each time an adjacency entry is created, such as through the ARP protocol, a link-layer header for that adjacent node is pre-computed and stored in the adjacency table.

Routes might have more than one path per entry, making it possible to use CEF to switch packets while load balancing across multiple paths.
In addition to next-hop interface adjacencies (in other words host-route adjacencies), certain exception condition adjacencies exist to expedite switching for nonstandard conditions. These include, among others: punt adjacencies for handling features that are not supported in CEF (such as IP options), and drop adjacencies for prefixes referencing the Null0 interface. Packets forwarded to Null0 are dropped, making an effective, effcient form of access fltering.

Router Security Strategies: Securing IP Network Traffic Planes By Gregg Schudel – CCIE No. 9591, David J. Smith – CCIE No. 1986 ISBN: 9781587053368 Publisher: Cisco Press

here is a graphic i built some time ago… it’s very pretty…

fib_adj