System for controlling look-ups in a data table in a network switch
Assignee3Com Technologies
InventorsKevin Jennings, Christopher Hay, Edele O'Malley, Gareth E Allwright
Life of this patent
Estimating the term…
Abstract
A system including an ordered data table containing linked lists of MAC addresses has a multiplicity of search engines which have their access to an LRU engine under the control of a token which is passed from one search engine to the next when the LRU engine has completed reordering the table after an address look-up. The system avoids conflicts between searching and reordering and allows reordering to be performed at a controlled rate.
Claims3
A system for performing address look-ups in an ordered data table within a switching device for a packet-based communication network, the data table containing entries which are in a defined searchable order and each include a media access control address, some of said entries each containing a respective pointer to another entry in the data table, the system comprising:
- a multiplicity of look-up engines for performing a look-up to locate an address in said data table;
- an LRU engine which is accessed by any of the look-up engines and is operative, in response to the location of an address in the table, to reorder the data table in accordance with a least recently used algorithm;
- and
- a token-based control for the look-up engines, said control including a token which is passed from look-up engine to look-up engine and allows only a look-up engine which is in possession of the token to access the LRU engine and thereby cause reordering of said data table.
A method of performing address look-ups in an ordered data table within a switching device for a packet-based communication network, the data table containing entries which are in a defined searchable order and each include a media access control address, some of said entries each containing a respective pointer to another entry in the data table, the method comprising:
- operating a multiplicity of look-up engines to perform look-ups to locate addresses in said data table;
- operating an LRU engine, in response to the location of an address in the table, to reorder the data table in accordance with a least recently used algorithm;
- operating a token-based control for the look-up engines, including passing a token from look-up engine to look-up engine and allowing only a look-up engine which is in possession of the token to access the LRU engine and thereby cause reordering of said data table;
- and
- controlling by means of said LRU engine the passage of the token from one look-up engine to another to occur after a reordering of the data table.
Dependencies are inferred from the claim text.