Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Computing > Cisco > "paged" CAM table hash

Reply
Thread Tools

"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
 
Reply With Quote
 
 
 
 
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.
 
Reply With Quote
 
 
 
 
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 .
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
hash of hash of hash of hash in c++ rp C++ 1 11-10-2011 04:45 PM
Hash#select returns an array but Hash#reject returns a hash... Srijayanth Sridhar Ruby 19 07-02-2008 12:49 PM
Using the 'show cam' and 'clear cam' commands Chris Cisco 7 05-03-2006 09:34 PM
Video cam as a web cam bpaulson@sasktell.net Computer Support 1 05-29-2004 11:52 PM
easy 1 step auto PC download pics digital cam ? no need extract memory media from cam Mario Digital Photography 3 10-13-2003 01:50 PM



Advertisments