Back to results
US 8,542,686 B2Granted
Ethernet forwarding database method
AssigneeGnodal Limited
InventorDavid Charles Hewson
Life of this patent
Estimating the term…
Abstract
A technique is described for retrieving data from a hash table in an Ethernet bridge. The table has a plurality of columns, each of which has a hash function, thereby creating respective different hash key values.
Claims20
A method of routing Ethernet frames between ports of an Ethernet bridge device, the method comprising the steps of:
- defining a routing table having a plurality of routing columns, each column having a plurality of entries, and each entry in a column having a unique index value;
- defining respective hash functions for the routing columns;
- receiving incoming address information from a port of the Ethernet bridge device;
- for each routing column:
- calculating a hash value from the incoming address information and the hash function defined for the column;
- determining if an entry having an index value equal to such a calculated hash value is empty;
- for those routing columns having such an empty entry:
- determining a usage value based upon the number of entries in the column in which data are stored;
- and
- storing address and port information in the empty entry of the routing column having the highest usage value, the port information identifying the port of the Ethernet bridge device from which the incoming address information is received.
7 more elements
An Ethernet bridge device comprising:
- a plurality of ports for reception and transmission of Ethernet frames;
- a routing unit for directing an Ethernet frame received at an ingress port of the device to an egress port of the device,
- wherein the routing unit is operable:
- to define a routing table having a plurality of routing columns, each column having a plurality of entries, and each entry in a column having a unique index value;
- to define respective hash functions for the routing columns;
- to receive incoming address information from a port of the Ethernet bridge device;
- to calculate, for each routing column, a hash value from the incoming address information and the hash function defined for the column;
- and
- to determine, for each routing column, if an entry having an index value equal to such a calculated hash value is empty;
- to determine, for those routing columns having such an empty entry, a usage value based upon the number of entries in the column in which data are stored;
- and
- to store address and port information in the empty entry of the routing column having the highest usage value, the port information identifying the port of the Ethernet bridge device from which the address information is received.
9 more elements
A method for storing and retrieving data in a table, the method comprising:
- defining the table having a plurality of storage columns, each of which has a plurality of storage entries with respective associated column index values;
- defining respective hash functions for the plurality of storage columns;
- receiving a lookup value, and an associated data value;
- for each storage column, calculating a hash value from the lookup value and the hash function defined for the column;
- for each storage column, determining if the entry having an index value equal to the calculated hash value is empty;
- for those storage columns having such an empty entry, determining a usage value based upon the number of entries in the column in which data are stored;
- and
- storing the associated data value in the empty entry of the storage column having the highest usage value.
5 more elements
Dependencies are inferred from the claim text.