CEF Load balancing

Dieg0M

When 2 destination networks have the same AD and metric, load-balancing will be done. In CEF per-destination mode or per-packet mode, which interface does CEF choose to send the first flow? Is it by interface number; the highest or lowest is chosen?

Example:

R2#sh ip route
Codes: C - connected, S - static, R - RIP, M - mobile, B - BGP
D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area
N1 - OSPF NSSA external type 1, N2 - OSPF NSSA external type 2
E1 - OSPF external type 1, E2 - OSPF external type 2
i - IS-IS, su - IS-IS summary, L1 - IS-IS level-1, L2 - IS-IS level-2
ia - IS-IS inter area, * - candidate default, U - per-user static route
o - ODR, P - periodic downloaded static route

Gateway of last resort is not set

1.0.0.0/32 is subnetted, 1 subnets
O 1.1.1.1 [110/11] via 192.168.1.1, 00:29:21, FastEthernet0/1
[110/11] via 192.168.0.1, 00:30:04, FastEthernet0/0
2.0.0.0/32 is subnetted, 1 subnets
C 2.2.2.2 is directly connected, Loopback0
C 192.168.0.0/24 is directly connected, FastEthernet0/0
C 192.168.1.0/24 is directly connected, FastEthernet0/1
R2#sh ip cef 1.1.1.1
1.1.1.1/32, version 29, epoch 0, per-destination sharing
0 packets, 0 bytes
via 192.168.1.1, FastEthernet0/1, 0 dependencies
traffic share 1
next hop 192.168.1.1, FastEthernet0/1
valid adjacency
via 192.168.0.1, FastEthernet0/0, 0 dependencies
traffic share 1
next hop 192.168.0.1, FastEthernet0/0
valid adjacency
0 packets, 0 bytes switched through the prefix
tmstats: external 0 packets, 0 bytes
internal 0 packets, 0 bytes


Thank you

Scales

It uses a hash function (I believe similar to the way ether-channel load-balancing works)
This is the command to configure the hash load sharing function

ip cef load-sharing algorithm include-ports source destination

http://www.cisco.com/en/US/docs/switches/lan/catalyst4500/12.2/54sg/configuration/guide/cef.pdf

Dieg0M

Scales wrote: »

It uses a hash function (I believe similar to the way ether-channel load-balancing works)
This is the command to configure the hash load sharing function

ip cef load-sharing algorithm include-ports source destination

http://www.cisco.com/en/US/docs/switches/lan/catalyst4500/12.2/54sg/configuration/guide/cef.pdf

How are the Hash functions compared to determine where the traffic will be routed to first?

networker050184

I believe how it is done is a next-hop interface list is created in numerical order (based on interface index number which coincides with interface numbering you see in your output). So say you have g1/0 and g1/1 your next-hop list would be as follows.

g1/0
g1/1

So then you have each source/dest pair hash assigned to a next-hop.

hash1 bucket 1 - g1/0
hash2 bucket 2- g1/1
hash3 bucket 3 - g1/0

So on and so fourth. If a new next hop interface is added it is then next in line even if numerically lower. I can't remember where I read this though but some googling might find it for you. In the end it doesn't really matter though. You can easily figure out what interface a source/dest pair is assigned to through show commands.

Dieg0M

You say numerical, do you mean only numbers are taken into account? What if I have 10G interfaces and Gig ones (Te3/1 and Gi3/) or even serial interfaces or 10mb. Is it going to be in alphabetical order and is it going to be lowest first? I have tried google but CEF is Cisco proprietary so there's no RFC and documentation is poor.

networker050184

It goes off interface index number. To the router g1/1 is for example 12345 and t1/1 might be 12344 etc. so it's not really about the alphabet. Usually you aren't going to load balance over a 10G and 10Mb serial though so I've never really thought about that one.

A good source is Cisco Express Frowarding. It hasn't been updated in a while but still good info.

Dieg0M

networker050184 wrote: »

It goes off interface index number. To the router g1/1 is for example 12345 and t1/1 might be 12344 etc. so it's not really about the alphabet. Usually you aren't going to load balance over a 10G and 10Mb serial though so I've never really thought about that one.

A good source is Cisco Express Frowarding. It hasn't been updated in a while but still good info.

Thanks for your response. I just tested it and it seems to go off the highest IP address as next-hop, not the index number or interface information.

networker050184

So possibly it's a next-hop index derived from the IP. I'll have to lab this up and dig into the CEF table outputs. If you start digging into CEF you will see everything is tied to index numbers.

Thanks for sharing. Always good to dig deeper.

networker050184

It would be interesting to see if it is being pulled from the local IP or higher remote IP from the adjacency table.... Did you check that?

Dieg0M

As far as I can tell, it works similarily to an RPF unicast check, it is pulled from the highest remote next-hop ip.

Lamps

Hi to everyone! I have similar question about CEF. I don't understand concept of buckets (CEF per-destination load sharing scenario). What is that? For example, packet arrive to the router/switch, and router/switch hashe packet's source/destination ip, what's next? Cisco says:
"The Cisco Express Forwarding table points to 16 hash buckets (load share table), which point to the adjacency table for parallel paths. Each packet to be switched is broken up into the source and destination address pair and checked against the loadshare table".
Checked against what? What does loadshare have inside to check against hash of packet? I am not native English speaker, so I hope you can understand me.

EdTheLad

Without reading through cef details i would imagine the following.

The bucket will refer to a virtual bandwidth allocation i.e. a scheduler
CEF will assign hash results to the bucket as follows:

16 buckets, which means 2^4, i.e. 0000,0001,0010 ....1111 , so four bits of the hash output will be examined and placed in a virtual bucket queue.
Depending on how many parallel paths there are, will decide as to how the bucket is assigned to the outgoing interface.Lets say there are 2 equal cost paths, that means buckets 0000 - 1000 will be assigned to the first and 1001-1111 to the second.

So, to summarize, a packet arrives, the src dst addresses get hashed, 4 bits of the hash are checked, result is 0110, that means bucket 6 which is assigned to the first link.

Lamps

EdTheLad wrote: »

Without reading through cef details i would imagine the following.

The bucket will refer to a virtual bandwidth allocation i.e. a scheduler
CEF will assign hash results to the bucket as follows:

16 buckets, which means 2^4, i.e. 0000,0001,0010 ....1111 , so four bits of the hash output will be examined and placed in a virtual bucket queue.
Depending on how many parallel paths there are, will decide as to how the bucket is assigned to the outgoing interface.Lets say there are 2 equal cost paths, that means buckets 0000 - 1000 will be assigned to the first and 1001-1111 to the second.

So, to summarize, a packet arrives, the src dst addresses get hashed, 4 bits of the hash are checked, result is 0110, that means bucket 6 which is assigned to the first link.

Very interesting idea! I issued command on my lab equipment (1841 with 15 IOS) sh ip cef 172.16.16.0 internal and got this:
16 hash buckets
< 0 > IP adj out of Serial0/1/0 67B0A040
< 1 > IP adj out of Serial0/1/1 66FB9240
< 2 > IP adj out of Serial0/0/0 67B0A300
< 3 > IP adj out of Serial0/0/1 67B0A1A0
< 4 > IP adj out of Serial0/1/0 67B0A040
< 5 > IP adj out of Serial0/1/1 66FB9240
< 6 > IP adj out of Serial0/0/0 67B0A300
< 7 > IP adj out of Serial0/0/1 67B0A1A0
< 8 > IP adj out of Serial0/1/0 67B0A040
< 9 > IP adj out of Serial0/1/1 66FB9240
<10 > IP adj out of Serial0/0/0 67B0A300
<11 > IP adj out of Serial0/0/1 67B0A1A0
<12 > IP adj out of Serial0/1/0 67B0A040
<13 > IP adj out of Serial0/1/1 66FB9240
<14 > IP adj out of Serial0/0/0 67B0A300
<15 > IP adj out of Serial0/0/1 67B0A1A0

The same result with other destination addresses (by this I mean the same right numbers). What do you think about this numbers? These numbers different on other router.

EdTheLad

I would guess those hex numbers are internal port numbers, each is unique to a physical port.