ip cef hash

[Cooky]

Depending on configuration, Cisco cef takes certain information, such as src-dst-ip and sometimes, port number into consideration for the cef hash.

Wouldn't ping or the same communication flow (same tcp/udp port number) between two specific hosts always take the same path then?

Why is it that the traceroute between two servers sometimes take the same path several times, and then a different path for a few times, and then change it back to the original path?

 

[imagoon]

I don't have a lot of experience in this area but I think the basics are more like this: The table keeps track of paths to hosts and uses line {link} loading to make a decision about where to send it out. On totally quiet lines it should pick the low port number but even on quiet lines there will be enough chatter to make it choose the links (apparently at random but it is just the frame count going up and down on each line) to send data out.

 

[Cooky]

thanks for the reply.
Just to clarify though, what you described is more like how an application load balancer could function.
Without something like PfR, routers & L3 switches usually can't load share based on utilization of each link.
The cef hash is based on things like source/destination mac/IP, and port number, which is why I think a particular flow between two specific hosts should always take the same path.

 

[ScottMac]

CEF also uses the port number. Sending a PING uses a different port number than traceroute/tracert, which is different for FTP, SSH, etc. Each of the above would gain an entry in the express forwarding table for each source-destination pair.

The entries do expire, and if the table fills before the entry expires, then a process selects an entry to delete (I don't recall if it's an "oldest entry" or "least used" selection).

I think imagoon was describing "flows" for a (layer two) switch, CEF is a layer three / router process.

 

[m1ldslide1]

Also keep in mind that other factors can influence cef path selection: port-channel hashing algorithms & L3 equal-cost multi-pathing come to mind. Your mileage may vary depending on design and configuration, and the same / similar flow may or may not take the same path each time.

 

[drebo]

CEF is voodoo, and it can do "load balancing" and that "load balancing" will average out to roughly 50% over time, but it's relatively unpredictable.

Also, ICMP is a separate L4 protocol...it doesn't have "ports" per se, so CEF may treat it slightly differently.

 

[Qrilock]

The CEF table is built based on what routes are inserted into the FIB by the routing process. If you do a 'show ip route' any routes displayed will have a corresponding entry in the CEF table. You can see this with 'show ip cef'. The packets will be load balanced the same way they would be if they were process routed. This is usually equal distribution, but you can configure unequal path selections if so desired.

 

[spidey07]

Depending on platform, your CEF load balancing can take into consideration L4 information in the hash. They've been adding this into their router/switch ASICs for some time now as EQPM has been really taking off. I think even the super modern platforms can have it totally randomize it instead of a hash.

 

[Cooky]

thanks everyone for your response.
Going back to my original question though:

Shouldn't traceroute from host A to host B always follow the same path, since CEF is taking the exact same information into its hash algorithm?

Yes, we have ECMP for both our L2 ether-channels & L3 redundant routed links.
At each hop though, the result of the hash should be the same...no?

How can 1+1=2 for one traceroute, but 1+1=3 for the next one?
Am I missing something fundamental here?

 

[drebo]

If CEF has two+ potential paths in the RIB, it will randomly loadbalance between them.

 

[alkemyst]

also once on the internut, your paths can be borken.

 

[Gryz]

Cooky, your question is completely valid. And it made me feel puzzled for a bit.

CEF switching is designed so that one "flow" of packets will always go over the same path. Flow meaning "a tcp connection" or a "udp session by an application". The reason for this is that you want to prevent out-of-order packets. Per-packet load-balancing can cause out-of-order delivery. TCP/IP has been designed so that it should be no problem when packets arrive out of order. However, reality is different. There used to be many TCP implementations that would consider out of order packets the same as dropped packets. And retransmissions would occur. The rule of thumb was that 1% packet drops would create a 50% performance loss (because of needless retransmissions, and waiting for retransmissions).

Older forwarding methods did stuff which was easiest to implement. I believe process-switching did round-robin. Can't remember the details of other switching methods. (Fast, flow, sse, what had you ?). When FIB-switching was build, it was by design that packets of the same flow would go over the same path. FIB-switching was renamed by marketing into CEF-switching. I believe a knob was later implemeneted to do round-robin load-balancing.

Back to the question. Why do you see that behaviour ?

Quick look at the Linux man-page of traceroute.
http://linux.die.net/man/8/traceroute
I see this switch:

-p port
For UDP tracing, specifies the destination port base traceroute will use (the destination port number will be incremented by each probe).
For ICMP tracing, specifies the initial icmp sequence value (incremented by each probe too).
For TCP specifies just the (constant) destination port to connect.

So it seems traceroute does not use the same portnumber for every packet it sends. The destination portnumber changes all the time. That would imply that the hash could vary every probe. And would explain why you see the behaviour you see.

If everything else fails .... read the man page.

I don't know what version of traceroute you are using. Maybe you're using a Windows flavor of traceroute. Windows traceroute does not have a -port flag. And I can't find any documentation about the Windows flavor. As usual. But I wouldn't be surprised if it did the same thing.

You could do a tcpdump or something to look at the portnumbers of your traceroute to confirm our suspicion.