"paged" CAM table hash

Discussion in 'Cisco' started by Ben Low, Oct 5, 2004.

  1. Ben Low

    Ben Low Guest

    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/en/us/guest/netsol/ns304/c649/ccmigration_09186a008014edf3.pdf
    also
    http://www.arp-sk.org/doc/bh-us-02-convrey-switches.pdf
     
    Ben Low, Oct 5, 2004
    #1
    1. Advertising

  2. Ben Low

    AnyBody43 Guest

    (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.
     
    AnyBody43, Oct 5, 2004
    #2
    1. Advertising

  3. Ben Low

    Ben Low Guest

    (AnyBody43) wrote in message news:<>...
    ....
    > 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 :).
     
    Ben Low, Oct 5, 2004
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Joachim Krais
    Replies:
    2
    Views:
    15,115
    Andre Beck
    Nov 23, 2003
  2. John Ramsden
    Replies:
    0
    Views:
    911
    John Ramsden
    Jul 24, 2004
  3. *** JB
    Replies:
    3
    Views:
    30,064
    ┬░Mike┬░
    Aug 17, 2004
  4. Ben
    Replies:
    11
    Views:
    10,322
  5. yuvanyag

    Hash table in Borland c++

    yuvanyag, Jul 24, 2007, in forum: Software
    Replies:
    0
    Views:
    1,213
    yuvanyag
    Jul 24, 2007
Loading...

Share This Page