Solved: CEF Load sharing

PyotrKhaimov · ‎02-15-2014

Hi. I have question about CEF. I don't understand concept of buckets (CEF per-destination load sharing scenario). For example, packet arrives to the router/switch, and router/switch hashes 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?

Vishesh Verma · ‎02-17-2014

Let's get back to original question -

"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?

Following is a load share table that identifies 4 paths and hash buckets are distributed equally among the 4 paths. The hex numbers(68D03140, 6A9B1220, 68D02FE0, 6A9B1380) simply identifies the path and these simple indicate which hash bucket belong to which path.

    16 hash buckets

      < 0 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      < 1 > IP adj out of GigabitEthernet2/0, addr 13.0.0.3 6A9B1220

      < 2 > IP adj out of GigabitEthernet3/0, addr 14.0.0.4 68D02FE0

      < 3 > IP adj out of GigabitEthernet4/0, addr 15.0.0.5 6A9B1380

      < 4 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      < 5 > IP adj out of GigabitEthernet2/0, addr 13.0.0.3 6A9B1220

      < 6 > IP adj out of GigabitEthernet3/0, addr 14.0.0.4 68D02FE0

      < 7 > IP adj out of GigabitEthernet4/0, addr 15.0.0.5 6A9B1380

      < 8 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      < 9 > IP adj out of GigabitEthernet2/0, addr 13.0.0.3 6A9B1220

      <10 > IP adj out of GigabitEthernet3/0, addr 14.0.0.4 68D02FE0

      <11 > IP adj out of GigabitEthernet4/0, addr 15.0.0.5 6A9B1380

      <12 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      <13 > IP adj out of GigabitEthernet2/0, addr 13.0.0.3 6A9B1220

      <14 > IP adj out of GigabitEthernet3/0, addr 14.0.0.4 68D02FE0

      <15 > IP adj out of GigabitEthernet4/0, addr 15.0.0.5 6A9B1380

As a packet enters the inbound interface, the router looks up the destination address in CEF. The load distribution table indicates that there are multiple paths to this destination. In this case, four equal-cost paths exist.
CEF combines and hashes the source and destination addresses along with a unique ID (depending on the Cisco IOS version) to find a number between 0 and 15. This number is an index into the load distribution table. (The hash function is Cisco properietry and you don't need to worry about it)
The load distribution table then indicates which adjacency entry in the path table should be used based on the hash information.
The path table then points into the adjacency table, so the router uses the correct next hop to reach the destination.

Following figure shows how this works for a destination of 192.168.1.1 which has 2 paths -

-Vishesh

View solution in original post

Vishesh Verma · ‎02-18-2014

Hi,

1). The hex numbers are not associated with the physical port, but with next-hop (path) instead. These number are arbitrary and can change upon a reload or FIB adjacency change of the next-hop.

R1#show ip cef 1.1.1.0/24 internal                                           

1.1.1.0/24, epoch 0, RIB[I], refcount 5, per-destination sharing

  sources: RIB 

  feature space:

   IPRM: 0x00028000

  ifnums:

   GigabitEthernet1/0(4): 12.13.0.2, 12.13.0.3

  path 68C15808, path list 68C15350, share 1/1, type attached nexthop, for IPv4

  nexthop 12.13.0.2 GigabitEthernet1/0, adjacency IP adj out of GigabitEthernet1/0, addr 12.13.0.2 68C887C0

  path 68C15878, path list 68C15350, share 1/1, type attached nexthop, for IPv4

  nexthop 12.13.0.3 GigabitEthernet1/0, adjacency IP adj out of GigabitEthernet1/0, addr 12.13.0.3 68C88660

  output chain:

    loadinfo 68C30604, per-session, 2 choices, flags 0083, 8 locks

    flags: Per-session, for-rx-IPv4, 2buckets

    2 hash buckets

      < 0 > IP adj out of GigabitEthernet1/0, addr 12.13.0.2 68C887C0

      < 1 > IP adj out of GigabitEthernet1/0, addr 12.13.0.3 68C88660




R1#show ip cef adjacency gigabitEthernet 1/0 12.13.0.2 detail | se ^12.13.0.2

12.13.0.2/32, epoch 0, flags attached

  Adj source: IP adj out of GigabitEthernet1/0, addr 12.13.0.2 68C887C0

   Dependent covered prefix type adjfib, cover 12.13.0.0/24

  attached to GigabitEthernet1/0




After reload, numbers switched, 12.13.0.2 now has 68C88660, which was previously allocated to 12.13.0.3 -




R1#show ip cef 1.1.1.0/24 internal             

1.1.1.0/24, epoch 0, RIB[I], refcount 5, per-destination sharing

  sources: RIB 

  feature space:

   IPRM: 0x00028000

  ifnums:

   GigabitEthernet1/0(4): 12.13.0.2, 12.13.0.3

  path 6A7DE5BC, path list 6A7DE104, share 1/1, type attached nexthop, for IPv4

  nexthop 12.13.0.2 GigabitEthernet1/0, adjacency IP adj out of GigabitEthernet1/0, addr 12.13.0.2 68C88660

  path 6A7DE62C, path list 6A7DE104, share 1/1, type attached nexthop, for IPv4

  nexthop 12.13.0.3 GigabitEthernet1/0, adjacency IP adj out of GigabitEthernet1/0, addr 12.13.0.3 68C887C0

  output chain:

    loadinfo 68C30604, per-session, 2 choices, flags 0083, 8 locks

    flags: Per-session, for-rx-IPv4, 2buckets

    2 hash buckets

      < 0 > IP adj out of GigabitEthernet1/0, addr 12.13.0.2 68C88660

      < 1 > IP adj out of GigabitEthernet1/0, addr 12.13.0.3 68C887C0

2). Yes the path table is FIB.

I suggest you to keep your studies towards understanding it's functionality and how to troubleshoot it, else it can overwhelm as there are a lot of programming and H/W level details that outputs can show. And these values in outputs are only required when we troubleshoot an issue with software code's perspective, bug/unpredictable behavior in TAC.

-Vishesh

View solution in original post

Vishesh Verma · ‎02-19-2014

Correct, with 3 equal paths 16th hash bucket is unused. With 2 equal paths, in newer IOS codes hash function is improved and only uses 2 buckets, but older IOS codes used to have 16 buckets divided equally 8 to each path.

-Vishesh

View solution in original post

Richard Burts · ‎02-15-2014

This can be a difficult thing to understand. So let me try to explain it in this way. First of all if you are having difficulty in understanding the concept of buckets, then let me try to explain it without using bucket. I will just talk about a logical container. There are 16 logical containers that CEF will use. CEF looks at a particular destination and determines how many paths can be used to get to that destination. A lot of the time there will be a single path to the destination and there is no load sharing. But if there are 2 or 3 or 4 paths then there is load sharing and CEF must determine how to allocate traffic to each path. So CEF decides how many logical containers are associated with each path (if there are 2 paths then each path has 8 logical containers associated with it, and if there are 4 paths then each path has 4 logical containers associated with it, and if there are 3 paths then each path has 5 logical containers associated with it and the last container is associated with one of the paths). Then CEF takes the combination of source address and destination address and does a hash calculation. The results of the calculation will match one of the logical containers. Then CEF determines whether this particular logical container is associated with the first path, the second path, the third path, etc.

I hope that this provides some clarity.

HTH

Rick

HTH

Rick

PyotrKhaimov · ‎02-16-2014

Dear Richard, many thanks for your answer! Your answer is very useful for me with respect to concept of buckets.

But, I think there is need to precise my question. I know that packets are getting hashed and then being checked against loadshare table which consist of 16 buckets. So my second question was - what do the buckets consist of? As I understand the buckets consist of some kind of hashes, but if it so where they (hashes) are getting from? Maybe there is default hash value to put them in buckets or something like that?

Richard Burts · ‎02-16-2014

I am glad that my answer has been helpful. So let me try to explain a bit more about the buckets. As I said the bucket is a logical container. It really does not contain much though. CEF does a hash calculation using the source and destination addresses. The result of the hash calculation is a hex value. CEF evaluates the hex value and determines which of the buckets that it matches. So you might think of the buckets as containing the results of the hash calculations and the choice of which path to use is based on which bucket the hex value of the hash calculation went into.

I believe that 6A9B1220, 68D03140 etc are the hex values that identify each of the buckets.

HTH

Rick

HTH

Rick

PyotrKhaimov · ‎02-16-2014

Dear Richard, did you mean that CEF perform some hash calculation for particular route before (some kind of hash pre-calculation) the first packet arrive to router/switch, put it into bucket and then when packet arrives to the router hashes it and checks against buckets with a hex-value of pre-calculated hash? Right? Or buckets filled with hash at the same time as packets arrive, and this hash is actual hash of arriving packets (not hash pre-calculation)? Sorry for bothering you, but this is really interesting area for me.

With regard to numbers, I test them on various routes and routers. For every destination on the same router they are the same. On another router they are different compared to the first router, but again the same for every destination networks which second router has. So I think these numbers are hardware based, but I don't know what they are, hex values of hash or maybe physical port identifiers or maybe something else.

canttalkeating · ‎10-04-2018

Great explanation Richard, many thanks

Vishesh Verma · ‎02-15-2014

Cisco Express Forwarding Load Balancing Internal Mechanisms

Each session is assigned to an active path.(seession is a unidirectional communication flow between two IP nodes. All packets in a session use the same source and destination IP address.)

The session-to-path assignment is done using a hash function that takes the source and destination IP addresses and, in recent releases of Cisco IOS, a unique hash ID that randomizes the assignment across the end-to-end path.

Active paths are assigned internally to several of 16 hash buckets. The path-to-bucket assignment varies with the type of load balancing and the number of active paths.

The result of the hash function is used to pick one of the enabled buckets, and thus which path to use for the session.

For all sessions being forwarded by the router, each active path carries the same number of sessions.

Route with 2 next-hops




R1#show ip route 2.2.2.0

Routing entry for 2.2.2.0/24

  Known via "eigrp 1", distance 90, metric 128256, type internal

  Redistributing via eigrp 1

  Last update from 21.0.0.2 on GigabitEthernet2/0, 00:01:56 ago

  Routing Descriptor Blocks:

    21.0.0.2, from 21.0.0.2, 00:01:56 ago, via GigabitEthernet2/0

      Route metric is 128256, traffic share count is 1

      Total delay is 5010 microseconds, minimum bandwidth is 1000000 Kbit

      Reliability 255/255, minimum MTU 1500 bytes

      Loading 1/255, Hops 1

  * 12.0.0.2, from 12.0.0.2, 00:01:56 ago, via GigabitEthernet1/0

      Route metric is 128256, traffic share count is 1

      Total delay is 5010 microseconds, minimum bandwidth is 1000000 Kbit

      Reliability 255/255, minimum MTU 1500 bytes

      Loading 1/255, Hops 1




R1#show ip cef 2.2.2.0/24 detail

2.2.2.0/24, epoch 0, per-destination sharing

  nexthop 12.0.0.2 GigabitEthernet1/0

  nexthop 21.0.0.2 GigabitEthernet2/0




R1#show ip cef 2.2.2.0/24 internal 

2.2.2.0/24, epoch 0, RIB[I], refcount 5, per-destination sharing

  sources: RIB 

  feature space:

   IPRM: 0x00028000

  ifnums:

   GigabitEthernet1/0(4): 12.0.0.2

   GigabitEthernet2/0(5): 21.0.0.2

  path 6AA14A80, path list 6A9D23E0, share 1/1, type attached nexthop, for IPv4

  nexthop 12.0.0.2 GigabitEthernet1/0, adjacency IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68CDA840

  path 6AA14F50, path list 6A9D23E0, share 1/1, type attached nexthop, for IPv4

  nexthop 21.0.0.2 GigabitEthernet2/0, adjacency IP adj out of GigabitEthernet2/0, addr 21.0.0.2 68CDA6E0

  output chain:

    loadinfo 68C81704, per-session, 2 choices, flags 0083, 5 locks

    flags: Per-session, for-rx-IPv4, 2buckets

    2 hash buckets

      < 0 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68CDA840

      < 1 > IP adj out of GigabitEthernet2/0, addr 21.0.0.2 68CDA6E0







Route with 3 next-hops




R1#show ip route 2.2.2.0   

Routing entry for 2.2.2.0/24

  Known via "eigrp 1", distance 90, metric 128256, type internal

  Redistributing via eigrp 1

  Last update from 21.0.0.2 on GigabitEthernet2/0, 00:00:49 ago

  Routing Descriptor Blocks:

    21.0.0.2, from 21.0.0.2, 00:00:49 ago, via GigabitEthernet2/0

      Route metric is 128256, traffic share count is 1

      Total delay is 5010 microseconds, minimum bandwidth is 1000000 Kbit

      Reliability 255/255, minimum MTU 1500 bytes

      Loading 1/255, Hops 1

    13.0.0.3, from 13.0.0.3, 00:00:49 ago, via GigabitEthernet3/0

      Route metric is 128256, traffic share count is 1

      Total delay is 5010 microseconds, minimum bandwidth is 1000000 Kbit

      Reliability 255/255, minimum MTU 1500 bytes

      Loading 1/255, Hops 1

  * 12.0.0.2, from 12.0.0.2, 00:00:49 ago, via GigabitEthernet1/0

      Route metric is 128256, traffic share count is 1

      Total delay is 5010 microseconds, minimum bandwidth is 1000000 Kbit

      Reliability 255/255, minimum MTU 1500 bytes

      Loading 1/255, Hops 1




R1#show ip cef 2.2.2.0/24 detail 

2.2.2.0/24, epoch 0, per-destination sharing

  nexthop 12.0.0.2 GigabitEthernet1/0

  nexthop 13.0.0.3 GigabitEthernet3/0

  nexthop 21.0.0.2 GigabitEthernet2/0




R1#show ip cef 2.2.2.0/24 internal 

2.2.2.0/24, epoch 0, RIB[I], refcount 5, per-destination sharing

  sources: RIB 

  feature space:

   IPRM: 0x00028000

  ifnums:

   GigabitEthernet1/0(4): 12.0.0.2

   GigabitEthernet2/0(5): 21.0.0.2

   GigabitEthernet3/0(6): 13.0.0.3

  path 6AA15030, path list 6A9D2750, share 1/1, type attached nexthop, for IPv4

  nexthop 12.0.0.2 GigabitEthernet1/0, adjacency IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68CDA840

  path 6AA14EE0, path list 6A9D2750, share 1/1, type attached nexthop, for IPv4

  nexthop 13.0.0.3 GigabitEthernet3/0, adjacency IP adj out of GigabitEthernet3/0, addr 13.0.0.3 67A21AC0

  path 6AA150A0, path list 6A9D2750, share 1/1, type attached nexthop, for IPv4

  nexthop 21.0.0.2 GigabitEthernet2/0, adjacency IP adj out of GigabitEthernet2/0, addr 21.0.0.2 68CDA6E0

  output chain:

    loadinfo 68C81508, per-session, 3 choices, flags 0003, 5 locks

    flags: Per-session, for-rx-IPv4

    15 hash buckets

      < 0 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68CDA840

      < 1 > IP adj out of GigabitEthernet3/0, addr 13.0.0.3 67A21AC0

      < 2 > IP adj out of GigabitEthernet2/0, addr 21.0.0.2 68CDA6E0

      < 3 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68CDA840

      < 4 > IP adj out of GigabitEthernet3/0, addr 13.0.0.3 67A21AC0

      < 5 > IP adj out of GigabitEthernet2/0, addr 21.0.0.2 68CDA6E0

      < 6 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68CDA840

      < 7 > IP adj out of GigabitEthernet3/0, addr 13.0.0.3 67A21AC0

      < 8 > IP adj out of GigabitEthernet2/0, addr 21.0.0.2 68CDA6E0

      < 9 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68CDA840

      <10 > IP adj out of GigabitEthernet3/0, addr 13.0.0.3 67A21AC0

      <11 > IP adj out of GigabitEthernet2/0, addr 21.0.0.2 68CDA6E0

      <12 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68CDA840

      <13 > IP adj out of GigabitEthernet3/0, addr 13.0.0.3 67A21AC0

      <14 > IP adj out of GigabitEthernet2/0, addr 21.0.0.2 68CDA6E0







Route with 4 next-hops




R1#show ip route 10.10.10.0

Routing entry for 10.10.10.0/24

  Known via "eigrp 1", distance 90, metric 130816, type internal

  Redistributing via eigrp 1

  Last update from 15.0.0.5 on GigabitEthernet4/0, 00:01:14 ago

  Routing Descriptor Blocks:

    15.0.0.5, from 15.0.0.5, 00:01:14 ago, via GigabitEthernet4/0

      Route metric is 130816, traffic share count is 1

      Total delay is 5010 microseconds, minimum bandwidth is 1000000 Kbit

      Reliability 255/255, minimum MTU 1500 bytes

      Loading 1/255, Hops 1

    14.0.0.4, from 14.0.0.4, 00:01:14 ago, via GigabitEthernet3/0

      Route metric is 130816, traffic share count is 1

      Total delay is 5010 microseconds, minimum bandwidth is 1000000 Kbit

      Reliability 255/255, minimum MTU 1500 bytes

      Loading 1/255, Hops 1

  * 13.0.0.3, from 13.0.0.3, 00:01:14 ago, via GigabitEthernet2/0

      Route metric is 130816, traffic share count is 1

      Total delay is 5010 microseconds, minimum bandwidth is 1000000 Kbit

      Reliability 255/255, minimum MTU 1500 bytes

      Loading 1/255, Hops 1

    12.0.0.2, from 12.0.0.2, 00:01:14 ago, via GigabitEthernet1/0

      Route metric is 130816, traffic share count is 1

      Total delay is 5010 microseconds, minimum bandwidth is 1000000 Kbit

      Reliability 255/255, minimum MTU 1500 bytes

      Loading 1/255, Hops 1




R1#show ip cef 10.10.10.0 detail 

10.10.10.0/24, epoch 0, per-destination sharing

  nexthop 12.0.0.2 GigabitEthernet1/0

  nexthop 13.0.0.3 GigabitEthernet2/0

  nexthop 14.0.0.4 GigabitEthernet3/0

  nexthop 15.0.0.5 GigabitEthernet4/0




R1#show ip cef 10.10.10.0/24 internal 

10.10.10.0/24, epoch 0, RIB[I], refcount 5, per-destination sharing

  sources: RIB 

  feature space:

   IPRM: 0x00028000

  ifnums:

   GigabitEthernet1/0(4): 12.0.0.2

   GigabitEthernet2/0(5): 13.0.0.3

   GigabitEthernet3/0(6): 14.0.0.4

   GigabitEthernet4/0(7): 15.0.0.5

  path 6A9B262C, path list 67A36D74, share 1/1, type attached nexthop, for IPv4

  nexthop 12.0.0.2 GigabitEthernet1/0, adjacency IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

  path 6A9B269C, path list 67A36D74, share 1/1, type attached nexthop, for IPv4

  nexthop 13.0.0.3 GigabitEthernet2/0, adjacency IP adj out of GigabitEthernet2/0, addr 13.0.0.3 6A9B1220

  path 6A9B277C, path list 67A36D74, share 1/1, type attached nexthop, for IPv4

  nexthop 14.0.0.4 GigabitEthernet3/0, adjacency IP adj out of GigabitEthernet3/0, addr 14.0.0.4 68D02FE0

  path 6A9B270C, path list 67A36D74, share 1/1, type attached nexthop, for IPv4

  nexthop 15.0.0.5 GigabitEthernet4/0, adjacency IP adj out of GigabitEthernet4/0, addr 15.0.0.5 6A9B1380

  output chain:

    loadinfo 68CA9644, per-session, 4 choices, flags 0003, 5 locks

    flags: Per-session, for-rx-IPv4

    16 hash buckets

      < 0 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      < 1 > IP adj out of GigabitEthernet2/0, addr 13.0.0.3 6A9B1220

      < 2 > IP adj out of GigabitEthernet3/0, addr 14.0.0.4 68D02FE0

      < 3 > IP adj out of GigabitEthernet4/0, addr 15.0.0.5 6A9B1380

      < 4 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      < 5 > IP adj out of GigabitEthernet2/0, addr 13.0.0.3 6A9B1220

      < 6 > IP adj out of GigabitEthernet3/0, addr 14.0.0.4 68D02FE0

      < 7 > IP adj out of GigabitEthernet4/0, addr 15.0.0.5 6A9B1380

      < 8 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      < 9 > IP adj out of GigabitEthernet2/0, addr 13.0.0.3 6A9B1220

      <10 > IP adj out of GigabitEthernet3/0, addr 14.0.0.4 68D02FE0

      <11 > IP adj out of GigabitEthernet4/0, addr 15.0.0.5 6A9B1380

      <12 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      <13 > IP adj out of GigabitEthernet2/0, addr 13.0.0.3 6A9B1220

      <14 > IP adj out of GigabitEthernet3/0, addr 14.0.0.4 68D02FE0

      <15 > IP adj out of GigabitEthernet4/0, addr 15.0.0.5 6A9B1380




Unequal cost routes in routing table




R1#show ip route eigrp | be Gate

Gateway of last resort is not set




      10.0.0.0/24 is subnetted, 1 subnets

D        10.10.10.0 [90/258560] via 13.0.0.3, 00:01:07, GigabitEthernet2/0

                    [90/130816] via 12.0.0.2, 00:01:07, GigabitEthernet1/0




R1#show ip route 10.10.10.0     

Routing entry for 10.10.10.0/24

  Known via "eigrp 1", distance 90, metric 130816, type internal

  Redistributing via eigrp 1

  Last update from 13.0.0.3 on GigabitEthernet2/0, 00:02:08 ago

  Routing Descriptor Blocks:

    13.0.0.3, from 13.0.0.3, 00:02:08 ago, via GigabitEthernet2/0

      Route metric is 258560, traffic share count is 121

      Total delay is 10000 microseconds, minimum bandwidth is 1000000 Kbit

      Reliability 255/255, minimum MTU 1500 bytes

      Loading 1/255, Hops 1

  * 12.0.0.2, from 12.0.0.2, 00:02:08 ago, via GigabitEthernet1/0

      Route metric is 130816, traffic share count is 240

      Total delay is 5010 microseconds, minimum bandwidth is 1000000 Kbit

      Reliability 255/255, minimum MTU 1500 bytes

      Loading 1/255, Hops 1




R1#show ip cef 10.10.10.0 detail

10.10.10.0/24, epoch 0, per-destination sharing

  nexthop 13.0.0.3 GigabitEthernet2/0

  nexthop 12.0.0.2 GigabitEthernet1/0




R1#show ip cef 10.10.10.0 internal

10.10.10.0/24, epoch 0, RIB[I], refcount 5, per-destination sharing

  sources: RIB 

  feature space:

   IPRM: 0x00028000

  ifnums:

   GigabitEthernet1/0(4): 12.0.0.2

   GigabitEthernet2/0(5): 13.0.0.3

  path 6A9B277C, path list 68F10960, share 121/121, type attached nexthop, for IPv4

  nexthop 13.0.0.3 GigabitEthernet2/0, adjacency IP adj out of GigabitEthernet2/0, addr 13.0.0.3 6A9B1220

  path 6A9B254C, path list 68F10960, share 240/240, type attached nexthop, for IPv4

  nexthop 12.0.0.2 GigabitEthernet1/0, adjacency IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

  output chain:

    loadinfo 68CA9644, per-session, 2 choices, flags 0003, 5 locks

    flags: Per-session, for-rx-IPv4

    16 hash buckets

      < 0 > IP adj out of GigabitEthernet2/0, addr 13.0.0.3 6A9B1220

      < 1 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      < 2 > IP adj out of GigabitEthernet2/0, addr 13.0.0.3 6A9B1220

      < 3 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      < 4 > IP adj out of GigabitEthernet2/0, addr 13.0.0.3 6A9B1220

      < 5 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      < 6 > IP adj out of GigabitEthernet2/0, addr 13.0.0.3 6A9B1220

      < 7 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      < 8 > IP adj out of GigabitEthernet2/0, addr 13.0.0.3 6A9B1220

      < 9 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      <10 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      <11 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      <12 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      <13 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      <14 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      <15 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

In this case buckets are also distributed unequally. so load sharing would be unequal which is we say in unequal cost load-balancing for EIGRP.

-Vishesh

PyotrKhaimov · ‎02-16-2014

Vishesh Verma, thank you for your answer, it was aslo very useful for me. But as I wrote above my main question was about consisting of buckets (you can read my answer to Richard). And by the way, what is this numbers (6A9B1220, 68D03140 and so on) are all about?

Vishesh Verma · ‎02-17-2014

Let's get back to original question -

"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?

Following is a load share table that identifies 4 paths and hash buckets are distributed equally among the 4 paths. The hex numbers(68D03140, 6A9B1220, 68D02FE0, 6A9B1380) simply identifies the path and these simple indicate which hash bucket belong to which path.

    16 hash buckets

      < 0 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      < 1 > IP adj out of GigabitEthernet2/0, addr 13.0.0.3 6A9B1220

      < 2 > IP adj out of GigabitEthernet3/0, addr 14.0.0.4 68D02FE0

      < 3 > IP adj out of GigabitEthernet4/0, addr 15.0.0.5 6A9B1380

      < 4 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      < 5 > IP adj out of GigabitEthernet2/0, addr 13.0.0.3 6A9B1220

      < 6 > IP adj out of GigabitEthernet3/0, addr 14.0.0.4 68D02FE0

      < 7 > IP adj out of GigabitEthernet4/0, addr 15.0.0.5 6A9B1380

      < 8 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      < 9 > IP adj out of GigabitEthernet2/0, addr 13.0.0.3 6A9B1220

      <10 > IP adj out of GigabitEthernet3/0, addr 14.0.0.4 68D02FE0

      <11 > IP adj out of GigabitEthernet4/0, addr 15.0.0.5 6A9B1380

      <12 > IP adj out of GigabitEthernet1/0, addr 12.0.0.2 68D03140

      <13 > IP adj out of GigabitEthernet2/0, addr 13.0.0.3 6A9B1220

      <14 > IP adj out of GigabitEthernet3/0, addr 14.0.0.4 68D02FE0

      <15 > IP adj out of GigabitEthernet4/0, addr 15.0.0.5 6A9B1380

As a packet enters the inbound interface, the router looks up the destination address in CEF. The load distribution table indicates that there are multiple paths to this destination. In this case, four equal-cost paths exist.
CEF combines and hashes the source and destination addresses along with a unique ID (depending on the Cisco IOS version) to find a number between 0 and 15. This number is an index into the load distribution table. (The hash function is Cisco properietry and you don't need to worry about it)
The load distribution table then indicates which adjacency entry in the path table should be used based on the hash information.
The path table then points into the adjacency table, so the router uses the correct next hop to reach the destination.

Following figure shows how this works for a destination of 192.168.1.1 which has 2 paths -

-Vishesh

PyotrKhaimov · ‎02-17-2014

Great! This is exactly what I wanted to understand! Please, clarify these things:

1) "these simple indicate which hash bucket belong to which path" - this is about the hex numbers (68D03140, 6A9B1220, etc)? I think these numbers are hardware based and indicate physical ports, I think so because I have tested some CEF scenario on two routers, and as I mentioned above - for every destination on the same router these hex numbers are the same.On another router they are different compared to the first router, but again the same for every destination networks which second router has. What do you think they indicates physical ports?

2) What do you mean by path table? FIB (forwarding information base)?

Thank you very much for answer!!!

Vishesh Verma · ‎02-18-2014

Hi,

1). The hex numbers are not associated with the physical port, but with next-hop (path) instead. These number are arbitrary and can change upon a reload or FIB adjacency change of the next-hop.

R1#show ip cef 1.1.1.0/24 internal                                           

1.1.1.0/24, epoch 0, RIB[I], refcount 5, per-destination sharing

  sources: RIB 

  feature space:

   IPRM: 0x00028000

  ifnums:

   GigabitEthernet1/0(4): 12.13.0.2, 12.13.0.3

  path 68C15808, path list 68C15350, share 1/1, type attached nexthop, for IPv4

  nexthop 12.13.0.2 GigabitEthernet1/0, adjacency IP adj out of GigabitEthernet1/0, addr 12.13.0.2 68C887C0

  path 68C15878, path list 68C15350, share 1/1, type attached nexthop, for IPv4

  nexthop 12.13.0.3 GigabitEthernet1/0, adjacency IP adj out of GigabitEthernet1/0, addr 12.13.0.3 68C88660

  output chain:

    loadinfo 68C30604, per-session, 2 choices, flags 0083, 8 locks

    flags: Per-session, for-rx-IPv4, 2buckets

    2 hash buckets

      < 0 > IP adj out of GigabitEthernet1/0, addr 12.13.0.2 68C887C0

      < 1 > IP adj out of GigabitEthernet1/0, addr 12.13.0.3 68C88660




R1#show ip cef adjacency gigabitEthernet 1/0 12.13.0.2 detail | se ^12.13.0.2

12.13.0.2/32, epoch 0, flags attached

  Adj source: IP adj out of GigabitEthernet1/0, addr 12.13.0.2 68C887C0

   Dependent covered prefix type adjfib, cover 12.13.0.0/24

  attached to GigabitEthernet1/0




After reload, numbers switched, 12.13.0.2 now has 68C88660, which was previously allocated to 12.13.0.3 -




R1#show ip cef 1.1.1.0/24 internal             

1.1.1.0/24, epoch 0, RIB[I], refcount 5, per-destination sharing

  sources: RIB 

  feature space:

   IPRM: 0x00028000

  ifnums:

   GigabitEthernet1/0(4): 12.13.0.2, 12.13.0.3

  path 6A7DE5BC, path list 6A7DE104, share 1/1, type attached nexthop, for IPv4

  nexthop 12.13.0.2 GigabitEthernet1/0, adjacency IP adj out of GigabitEthernet1/0, addr 12.13.0.2 68C88660

  path 6A7DE62C, path list 6A7DE104, share 1/1, type attached nexthop, for IPv4

  nexthop 12.13.0.3 GigabitEthernet1/0, adjacency IP adj out of GigabitEthernet1/0, addr 12.13.0.3 68C887C0

  output chain:

    loadinfo 68C30604, per-session, 2 choices, flags 0083, 8 locks

    flags: Per-session, for-rx-IPv4, 2buckets

    2 hash buckets

      < 0 > IP adj out of GigabitEthernet1/0, addr 12.13.0.2 68C88660

      < 1 > IP adj out of GigabitEthernet1/0, addr 12.13.0.3 68C887C0

2). Yes the path table is FIB.

I suggest you to keep your studies towards understanding it's functionality and how to troubleshoot it, else it can overwhelm as there are a lot of programming and H/W level details that outputs can show. And these values in outputs are only required when we troubleshoot an issue with software code's perspective, bug/unpredictable behavior in TAC.

-Vishesh

PyotrKhaimov · ‎02-19-2014

Great as always! And the last question You wrote above: "CEF combines and hashes the source and destination addresses along with a unique ID (depending on the Cisco IOS version) to find a number between 0 and 15". If there are only two equal paths with 2 hash buckets (< 0 > and < 1 >), obviously hash function have to find numbers not between 0 and 15, but between 0 and 1. I think It is done by changing hash function, am I right? The same applies to scenario where 3 equal paths exist (0 - 14).

Vishesh Verma · ‎02-19-2014

Correct, with 3 equal paths 16th hash bucket is unused. With 2 equal paths, in newer IOS codes hash function is improved and only uses 2 buckets, but older IOS codes used to have 16 buckets divided equally 8 to each path.

-Vishesh