Re: [ethmac] about the hash table

["Jim Dempsey" <tapedisk@ameritech.net>]

This is a very good description. The concept of a hash table to quickly
identify an item has been around for a long time. This technique has been
used in compilers for symbol table look-ups for as long as I can remember
(35 years). The trick is to use a simple algorithm that converts a larger
entry into a smaller entry with even distribution across the number of
available addresses. If the MAC addresses were truly random then
taking ten LSBs would be sufficient to obtain a good distribution.
You will get collisions (multiple MAC addresses resolving to same
table entry) but if your hashing function is good then your table size
need only be approximately 115% larger than the number of different
MAC addresses that are actively in use. A 10 bit table address would
work well up to 85% of 1024 (870) addresses before collisions start
to become significant.

Note, if all the MACs were built by the same manufacture and in the
same lot then it is likely that the addresses would be evenly distributed.
mod1024(start+0), mod1024(start+1), mod1024(start+2), ...

If in practice you observe sparse and dense areas of distribution then
a little randomization could be introduced with a simple hash algorithm.
Such as 10 bits of the XOR of the three 16-bit zones of the 48 bit address.

Jim Dempsey


----- Original Message -----
From: "Illan Glasner" <IGlasner@mrv.com>
To: <ethmac@opencores.org>
Sent: Tuesday, January 21, 2003 2:06 PM
Subject: RE: [ethmac] about the hash table


>
>    Hi,
>
>    I don;t know what exact application you use but Generly speaking
> the purpose of the hash is to allow you to use a small memorey to cover
> large range of addresses.
>
> the simplest way to show example is assume your hash funciton take the 48
> bit of addrss remove the 38 MSB bits so you are left with 10 bit.
>
> so now no matter what Mac address come your hash result will need only a
10
> bit depth of memorey.
>
> now that we have this we have a second parameter and it come to solve the
> problem of multiple address hit the same entry as take the above example
if
> the 10 bit LSB remiain the same the entry will be the same so what is
usualy
> done is that you allow 15 hits meaning let say the hash result was the
nuber
> 200 and let say you know search the memorey for learning purpose than if
> this entry is filled already you will try to put it in 201 and if this is
> also used 202 and so on for 15 consecutive address and if all are full you
> drop the address.
> of course this also mean you need some sort of aging to clear old entry to
> allow new addres to be learned.
> similry when you access the memorey for search if 200 don;t have the right
> hit you try 201 and so on and if after 15 no hit was found you treat the
> address as unknown and most likely send it through all the ports.
>
> there are many type of hash function but the all solve this issue. as for
> which fucntion to use there is no simple answer as it is more a network
> dependent as it mainly depend on what Mac address you anticipate to have
and
> make the hash finction such that will spread them all over the memorey you
> have so there will be as little as possible need for multi-serach and if
> possiably to avoid miss-hit.
>
> have a nice day
>
>    Illan
>
>
>
>
>
> -----Original Message-----
> From: wilton@mail.usa.com [mailto:wilton@mail.usa.com]
> Sent: Tuesday, January 21, 2003 1:25 AM
> To: ethmac@opencores.org
> Subject: [ethmac] about the hash table
>
>
> Hi All,
>
> Could anyone provide me the detail information about the hash talble for
> Ethernet MAC? what is it and how to generate/use it?
>
> Thanks in advance,
>
> Wilton
> --
> To unsubscribe from ethmac mailing list please visit
> http://www.opencores.org/mailinglists.shtml
> --
> To unsubscribe from ethmac mailing list please visit
http://www.opencores.org/mailinglists.shtml

--
To unsubscribe from ethmac mailing list please visit http://www.opencores.org/mailinglists.shtml