Velocity Reviews > "paged" CAM table hash

# "paged" CAM table hash

Ben Low
Guest
Posts: n/a

 10-05-2004
A number of Cisco documents note that the "128,000 [CAM] entries are
organized as 8 pages that can store approximately 16,000 entries. A 17
bit hash algorithm is used to place each entry in the CAM table.". [1]

Yet 2^17 = 128k. This, in conjunction with the diagram on p. 16 of
Convrey's "Fun with Ethernet Switches" presentation [2] that shows the
a table with 8 columns of 16,000 rows and MAC addresses filling across
each row, suggests that the algorithm hashes the (VLAN, MAC, etc) to a
14 bit value (16384) and then places the result in the first available
page (i.e. linear list?). (though Convey also states a 17 bit hash)

Is this "page" business correct? If so, given that the table is
permanently allocated and fixed in size, why the bother with pages and
the linear list? Surely it'd be better to have a flat 128k-entry table
and a 17 bit hash for the index?

I'm guessing the paging mechanism is described correctly, as it would
certainly explain why I often see flooded traffic on switches that do
not have an overflowed CAM table (i.e. more than 8 collisions on the
14 bit hash = flood). Though "why" is still a mystery to me...

Ben

[1]
http://www.cisco.com/application/pdf...008014edf3.pdf
also
http://www.arp-sk.org/doc/bh-us-02-convrey-switches.pdf

AnyBody43
Guest
Posts: n/a

 10-05-2004
http://www.velocityreviews.com/forums/(E-Mail Removed) (Ben Low) wrote in
> A number of Cisco documents note that the "128,000 [CAM] entries are
> organized as 8 pages that can store approximately 16,000 entries. A 17
> bit hash algorithm is used to place each entry in the CAM table.". [1]
>
> Yet 2^17 = 128k. This, in conjunction with the diagram on p. 16 of
> Convrey's "Fun with Ethernet Switches" presentation [2] that shows the
> a table with 8 columns of 16,000 rows and MAC addresses filling across
> each row, suggests that the algorithm hashes the (VLAN, MAC, etc) to a
> 14 bit value (16384) and then places the result in the first available
> page (i.e. linear list?). (though Convey also states a 17 bit hash)
>
> Is this "page" business correct? If so, given that the table is
> permanently allocated and fixed in size, why the bother with pages and
> the linear list? Surely it'd be better to have a flat 128k-entry table
> and a 17 bit hash for the index?
>
> I'm guessing the paging mechanism is described correctly, as it would
> certainly explain why I often see flooded traffic on switches that do
> not have an overflowed CAM table (i.e. more than 8 collisions on the
> 14 bit hash = flood). Though "why" is still a mystery to me...

Thanks for the references, interesting reading.

I cannot help much with the puzzle however, how about:-

It turns out that the number of overflows is reduced when a 14 bit
hash is used with 8 pages when compared with a single page 17 bit hash.
For example in the latter case a hash collision guarantees a CAM table
overflow. There may be a difference in the proportion of collisions
between random inputs to the hash function and real world inputs.

In other words, the probabilty of a CAM table overflow might be
reduced in the 14 bit by 8 page case when compared with the 17 bit
by one page case. Maybe someone can do the maths?

It does appear that 17 bits must be wrong.

Ben Low
Guest
Posts: n/a

 10-05-2004
(E-Mail Removed) (AnyBody43) wrote in message news:<(E-Mail Removed). com>...
....
> For example in the latter case a hash collision guarantees a CAM table
> overflow. There may be a difference in the proportion of collisions
> between random inputs to the hash function and real world inputs.

Good point. I guess when you can't predict the distribution of your
inputs, allowing a smallish number of collisions is a reasonable
compromise bet. performance and collisions ("overflow").

> It does appear that 17 bits must be wrong.

Thanks for the validation.

I must be weird though, to me this issue seems fairly important in
understanding CAM operation and overflow, yet it's not mentioned in at
all in say BCMSN; yet there are pages of (incomplete) information on
TCAM which, whilst interesting, won't result in MITM attacks .