System for controlling look-ups in a data table in a network...

Details System for controlling look-ups in a data table in a network... System for controlling look-ups in a data table in a network...

1999-10-12

2003-06-17

Cangialosi, Salvatore (Department: 2661)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S395310

Reexamination Certificate

active

06580712

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to the organisation and use of databases of addresses in network devices such as bridges or routers wherein address data obtained from a packet is employed in reduced form in order to look-up further address data required for the onward transmission of a packet.
The invention particularly relates to the management of look-ups in a switch which employs a hash table for the accessing of associated data including address data.
BACKGROUND OF THE INVENTION
Network devices (herein called switches) are generally required to obtain address data, which may be media access controlled data or network address data depending upon the type of switch. Generally, media access control (MAC) addresses i.e. layer
2
addresses in the OSI model, relate to the devices in the communication system and are generally used to perform bridging, that is to say switching packets from one port of a device to another. Network addresses, namely layer addresses in the OSI model, are commonly used for routing and generally direct a packet to another network or sub network. Nevertheless, a router may need to map a network address of, for example, an end station to its MAC address and to place the MAC address of the packet as the packet leaves the router. Furthermore, current network switches may perform both bridging and routing.
In particular, bridges need to respond to media access control (MAC) addresses to look up for example a relevant port mask whereas routers, in addition, may need to form a similar operation after a preliminary mapping, using an address resolution protocol, between a network address and a relevant media access control address.
In modern communication networks a media access control address is quite wide, normally having forty-eight bits. A network device must respond to a MAC address in order to access relevant associated data necessary for the onward transmission of a packet. It is not normally desirable to make provision for the storage of all possible MAC addresses and data associated with them and accordingly it is common practice to employ the address data in a reduced form, known as the hash table. A hash table is a table of addresses obtained by performing arithmetic operations on a MAC address. The operation may be, for example, an exclusive-OR function and normally reduces the width of the MAC address from typically forty-eight bits to ten or sixteen bits. The ‘hashed’ address constitutes a to pointer to a stored table, the entry in the stored table comprising the original MAC address and associated data such as, for example, port masks, VLAN identification and so on, depending on the requirements of the system.
It will be apparent that although a hash table is intended to be a sparsely populated table, so that a particular MAC address will map to a unique entry in the hash table which in tern maps to a single entry in the associated data table, the manner of generation of a hash table does not preclude the mapping of two, and often many more than two, MAC addresses to the same location in the hash table. When this occurs, the pointer of the hash table points to a first entry in the associated data table but the associated data table is organised so that that entry contains a pointer to another entry in which the MAC address can be represented by the same hash entry and so on. In this way a linked list of MAC addresses is built. The process of obtaining the data associated with an incoming MAC address is therefore to respond to the MAC address by recourse to the hash table, building the list of linked MAC address entries from the associated data table and examining this built list to find the MAC address which uniquely corresponds to the incoming MAC address. When the list of addresses becomes long, a longer time is necessary to find the correct MAC address in the list In order to speed up the search the list of addresses may be re-organised so that, for example, a MAC address found at the end of the list is moved one step forward up the list so that the next search for this MAC address will be faster. This adjustment of the order of the addresses is controlled by an algorithm known as a least recently used (LRU) algorithm and enables the most commonly used MAC addresses to be found more quickly than those that are less used.
At network speeds of 10 Mbps per second and 100 Mbps per second it has proved feasible to implement this form of look-up using a single search engine, i.e. that combination of hardware and software which responds to an incoming MAC address to access the hash table obtain the list of list addresses and search through them in a given order until a MAC address matching the incoming MAC address is found. At the end of a search performed by the single search engine the search would cease look-ups and move a MAC address up one place in the list. However, it is desirable particularly when operating at a higher data rate, such as 1000 Mbps, to employ a multiplicity of look-up engines which share the same database. Such look-up engines will be searching the hash table and the linked lists at the same time. It is desirable for a least recently used algorithm to be employed but since potentially two engines may be searching the same list of linked addresses it is not desirable for both engines to implement a least recently used algorithm at the same time and it is not desirable, and not feasible at gigabit speeds, to wait until all the look-up engines have stopped before the order of the extracted media access control addresses in a list can be changed.
Accordingly the general object of the invention is to provide a method of operating databases in these circumstances to enable more than one look-up engine to use the database while avoiding conflicting operation of least recently used algorithms and avoiding the cessation of look-ups while a least recently used algorithm is performed to alter the order of addresses in a linked list.
SUMMARY OF THE INVENTION
The invention is based on the use of a specific or dedicated engine to execute the algorithm. In a specific form of the invention, a token is passed around each look-up engine in turn allowing it to use the dedicated engine. Accordingly, no two look-up engines will attempt to update the associated data table at the same time. Furthermore, updates are prevented from occurring when to engines are searching the same linked list.
A further disadvantage which may occur in known practice is that (especially at high speeds) continuous alteration of the order of media access control addresses in the associated data table may occur so that excessive time is occupied in writing data to the random access memory which contains the associated data table. Using the present invention, the frequency of updates can be limited by the dedicated engine to a selected rate which will normally ensure that the most common media access control addresses are at the top of the list.


REFERENCES:
patent: 5708659 (1998-01-01), Rostoker et al.
patent: 0594196 (1994-04-01), None
patent: 2346519 (2000-09-01), None
patent: WO 97/36407 (1997-10-01), None
patent: WO 98/29986 (1998-07-01), None
patent: WO 99/000820 (1999-01-01), None

Affiliated with

Also associated with

Rating

System for controlling look-ups in a data table in a network... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System for controlling look-ups in a data table in a network..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for controlling look-ups in a data table in a network... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3145913