CEF Adjacency Table Entry

Previous post talks about the CEF FIB Table Entries which resides in the FIB table. As we know CEF is built of two tables one is FIB and another is Adjacency. We will talk more about the different kind of adjacencies available in the CEF table.

• Auto adjacencies actually contain a MAC header rewrite string, and can be used to forward traffic. These are either valid, meaning they are useable, or invalid, meaning the MAC header rewrite string isn’t available.

• Punt adjacencies indicate the packet should be queued to the next slower switching method (generally fast switching) because switching the packet requires a feature that isn’t supported in the CEF switching path. Generally, in newer code, punt adjacencies should be rare.

• The glean adjacency indicates the destination should be directly attached and reachable via a broadcast network, but there is no MAC header rewrite string available to forward traffic.

• Drop adjacencies indicate the packet cannot be CEF switched, but there is no alternate switching path to punt the packet.

• Discard adjacencies indicate the packet should be dropped because it is destined to a loopback address on the router. All the addresses that fall outside the loopback’s actual address (which will have a /32 receive FIB entry) will point to discard adjacencies.

• Any addresses which should be forwarded through a NULL interface on the router (NULL0), will point to the null adjacency.

• The FIB can cache a copy of the MAC header rewrite string directly in the FIB entry itself for faster lookups; load shared destinations cannot have their MAC header rewrite strings cached, so their adjacencies are marked uncached.

(Difference between Optimum, Fast and CEF Switching)

Click Here To Read Rest Of The Post...

CEF FIB Table Entries

Cisco Express Forwarding aka CEF is made of two tables called Forwarding Information Base(FIB) and Adjacency table. Every table has its own data structure and passes some kind of information about the destination network.

CEF FIB table has special type of entries as listed below:-
1. Attached FIB entry:- Attached FIB entries are built for destinations which are actually attached to the router and for destinations which are configured via static routes to appear connected to the router e.g. ip route x.y.z.x via an interface.
2. Connected Entry:- A FIB entry is marked as connected entry if it is actually created because of an ip address command on a router’s interface.
3. Receive FIB Entry:- Receive FIB entries are built when the router should receive (process locally) packets destined to the address.
4. Recursive FIB Entry:- Recursive FIB entries indicate that the destination is reachable through some other route (Normally happens when the interface is not directly connected).

(How to check that the packets are CEF switched or Process Switched)

Click Here To Read Rest Of The Post...

GRE Tunnel IP Facing Latency But Destination Address Doesn't

According to the customer, when he pings the GRE tunnel ip address a latency of 300-400ms is receiving but the latency of destination address of tunnel is 40ms. Really such a weird issue and ping outputs are phenomenal. During the analysis, we find backbone is having two equal cost path and destination based packet forwarding is configured. After running show ip cef exact route , we find that the packet forwading is occuring from the second path which is very less utilize and ist path is fully choked. But not able to check the same results with GRE ip address. There after, per packet based forwarding is configured and problem completely vanishes.
Does anyone know how to check the cef exact route for GRE tunnel address?

Click Here To Read Rest Of The Post...

FEC in traditional IP routing and MPLS

In my FEC post I describe the basic working of FEC. In MPLS it’s always said FEC is performed only at the ingress time but in traditional ip cloud it does at all the hops which requires more cpu processes and memory for the routes. During the reading of Jeff Doyle chapter second I saw a good explanation of FEC. Excerpt from Jeff Doyle TCP/IP Routing Vol 2 – Chapter 2
“Here is where things go wrong. Provo does a route lookup for 196.223.18.0/24 and sees that the network is reachable via Salt Lake. It then does a lookup for Salt Lake's IP address and sees that it is reachable via the next-hop router, Ogden. So the packet destined for 196.223.18.0/24 is forwarded to Ogden. But the external routes are shared between Salt Lake and Provo via IBGP; the OSPF routers have no knowledge of the external routes. Therefore, when the packet is forwarded to Ogden, that router does a route lookup and does not find an entry for 196.223.18.0/24. The router drops the packet and all subsequent packets for that address. Traffic for the network 196.223.18.0/24 is black-holed.
Of course, if the OSPF routers know about the external routes, the situation just described will not happen. Ogden will know that 196.223.18.0/24 is reachable via Salt Lake and will forward the packet correctly. Synchronization prevents packets from being black-holed within a transit AS by an IGP with insufficient information.”

The lines in bold explicitly states that on every hop IGP checks for the external routes in the routing table & forward the packets correctly, if the no routes in the IGP routing table the packets would be dropped. It means FEC is performing at each and every step in traditional ip routing but not in MPLSVPN case because here the FEC is performed only at the ingress after that only labels are swapped that’s why the core routers doesn’t require the information of external routes. If FEC were being in MPLS also then core routers couldn’t forward the traffic without the knowledge of external routes.

Remember one thing when one talk about FEC, it means he is talking about the route lookups, next hop adjacency, longest prefix match in one algorithm. The algorithm is called on every hop in traditional ip routing but called once in MPLSVPN routing.


regards
shivlu jain
Click Here To Read Rest Of The Post...

How CEF understands overlapping of ip addresses ?

Yesterday I was reading Jeff Doyle TCP IP/Routing and got a overlapping problem. In that Jeff Doyl explained how BGP selects the best route in case of overlapping. The excerpt is given cite

“A BGP-speaking router can transmit overlapping routes to another BGP speaker. Overlapping routes are nonidentical routes that point to the same destination. For example, the routes 206.25.192.0/19 and 206.25.128.0/17 are overlapping. The first route is included in the second route, although the second route also points to other more-specific routes besides 206.25.192.0/19.When making a best-path decision, a router always chooses the more-specific path. When advertising routes, however, the BGP speaker has several options for dealing with overlapping routes:”

In the above excerpt jeff has explicitly cited that route always choose more-specfic path but BGP has many options for dealt. But the question comes in mind how router process the overlapping of routes because now-a-days cisco routers are using CEF, it means all the routing information stored in FIB which is forwarding information base.

Without wasting any time let’s see how the information is stored & processed by FIB in case of overlapping of ip addresses. CEF will create the table given in figure for storing the prefixes. As per the figure the first block is responsible till 191 & another block is responsible for rest of the prefixes. Only pointer will be used which will point towards the addresses.


regards
shivlu jain
Click Here To Read Rest Of The Post...

Difference Between Optimum , Fast and CEF Switching

With reference to my last post on Interrupt Context Switching Vs Process Switching; I am explaining more on to the Interrupt Context Switching Mechanism which is being used by Fast Switching, Optimum Switching & CEF Switching. All the three mentioned switching techniques uses the cache. So you can see how the cache is used by the switching methods and becasue of that cache fact it is said that cisco uses interrupt context switching.

Fast Switching
Fast switching stores the forwarding information and MAC header rewrite string using a binary tree for quick lookup and reference. In Fast Switching, the reachability information is indicated by the existence of a node on the binary tree for the 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. In order 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 are 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.

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. 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.

CEF (Cisco Express Forwarding) Switching
Cisco Express Forwarding also uses a 256 way data structure to store forwarding and MAC header rewrite information, but it does not use a tree. Cisco Express Forwarding uses a trie, which means the actual information being searched for is not in the data structure; instead, the data is stored in a separate data structure, and the trie simply points to it. In other words, rather than storing the outbound interface and MAC header rewrite within the tree itself, Cisco Express Forwarding stores this information in a separate data structure called the adjacency table.


regards
shivlu jain
Click Here To Read Rest Of The Post...

CEF LoadbalancingProblem

Sometimes you may face the problem in which if you ping from R7 to R6 it works perfect but when you try to ping from R5 to R6 you may face drops. Whats the reason for that ? Do you know ?
Needn’t worry about that I will let you know the reason behind this. Actually what happens when you ping from R7 the packets are process switched and then from R5 they are CEF switched because of cef switched by default it takes per destination based. So your packets always path either R5-R3 or R5-R1. Lets assume packets takes R5-R3 path and R5-R1 paths has some CRC errors etc. So in this case your packets will always follow R5-R3 path never R5-R1 and you find no more drops. But in latter case when you ping from R5 to R6, you always find drops because packets originated from R5 always process switched, so packets are always load balanced across both paths and you may drops becasue of this.
You can check with the help of " show ip cef exact-route " command which will tell you which path is being taken by the packets.

Click Here To Download
Click Here To Read Rest Of The Post...

CEF Enhanced Scalability (CSSR)

After waiting for long time, CISCO has added new data structuted named CSSR in CEF which is actually going to enhance the performance of CEF. It is available on 12.4(20)T platform.

Secret Of CSSR: Actually CEF uses adjacency table for next-hop and mac-address resolution. If you are having n entries in the routing table with the same next-hop then for every entry it has to maintain the adjacency table which acquires more space. By adding new data structure into CEF, it will save only a single entry in the adjacency table for all the routes who are having same next-hop address.
Click Here To Read Rest Of The Post...

CEF Troubleshooting With Ping

Few days back I faced problem related to the CEF. I tried to ping from one router to another but found packet drops. SO I initiated the first step with ping. By using extended ping I set the record option and find ping reply.
So what is the difference when we use the ping with record option and without record option. Actually by setting record option ping packets uses the fast switching and without record option it uses the cef switching. So I conclude there might be problem with the CEF in the path.

Shivlu_rtr#ping
Protocol [ip]:
Target IP address: 10.10.20.20
Repeat count [5]:
Datagram size [100]:
Timeout in seconds [2]:
Extended commands [n]: y
Source address or interface: FastEthernet0/0.50
Type of service [0]:
Set DF bit in IP header? [no]:
Validate reply data? [no]:
Data pattern [0xABCD]:
Loose, Strict, Record, Timestamp, Verbose[none]: Record
Number of hops [ 9 ]:
Loose, Strict, Record, Timestamp, Verbose[RV]:
Sweep range of sizes [n]:
Type escape sequence to abort.
Sending 5, 100-byte ICMP Echos to 10.10.20.20, timeout is 2 seconds:
Packet sent with a source address of 71.5.100.69
Packet has IP options: Total option bytes= 39, padded length=40
Record route: <*>
Click Here To Read Rest Of The Post...

CEF Basics

When the packet is being received by the router what it does. Actually it looks for the destination network in the routing table and corresponding to that which next hop is used and which interface is used for outgoing. It means if the next hop is reachable then it will look for the arp entry for the directly connected router and header rewrite process will occur & packet will be forwarded towards the destination. All the packets are fast switched, I will let you know how to check the fast and cef switched packets later on my discussion. So it means on every packet the same process has to be initiated & uses most of the CPU processes and all. To overcome this problem cisco introduces a new switching mechanism that is CEF (Cisco Express Forwarding). CEF maintains two tables

a)      FIB (Forwarding Information Base)

FIB is forwarding information base which is as such the copy of the routing table. Whatever route comes in the routing table a same copy is created in the CEF table and that is known as FIB. So we can say FIB is nothing but a copy of the routing table. With the help of show ip cef you can check the cef table

 

b)      Adjacency Table (Which is used to store arp information)

This is the table which actually stores your outgoing interface with the arp of that interface.

You can check with the help of given command

Show adjacency internal

 

Structure Of CEF

FIB	Adjacency Table

 

                                                                                        

 

So we can say FIB & Adjacency tables are the data structures which are using for handing the information.

 

FIB		Adjacency Table
10.10.10.0	Pointer  à	Next Hop 1.1.1.1,Arp & Outgoing Interface
		Next Hop 2.2.2.2 & Arp & Outgoing Interface

 

Routing table is having entry of 10.10.10.0 with next hop 20.20.20.20 and which is reachable by 1.1.1.1 if this interface is down then the pointer will move towards the 2.2.2.2 so there is no change in the routing table no change in the FIB table only change occurs at the pointer end which actually saves lots of processes and of course calculations. 

regards

shivlu

Click Here To Read Rest Of The Post...