Electrical computers and digital processing systems: memory – Address formation – Hashing
Reexamination Certificate
1998-11-20
2001-08-21
Yoo, Do Hyun (Department: 2759)
Electrical computers and digital processing systems: memory
Address formation
Hashing
C711S205000, C711S206000, C711S207000, C370S255000
Reexamination Certificate
active
06279097
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to address lookup tables used in computer networking devices, and more particularly, to a method and apparatus for generating such an address lookup table.
2. Description of the Related Art
Local area networks are used on a regular basis to link together multiples nodes, such as personal computers, workstations, servers, etc., to allow the nodes to share information and resources with each other. For small networks, a simple configuration may be used wherein each of the nodes is coupled directly to the network backbone. For more complicated networks having large numbers of nodes, however, direct coupling becomes highly inefficient. To improve efficiency on the more complicated networks, the method of “segmenting” is often applied.
According to the segmenting method, the various nodes in the network are separated into a plurality of groups known as “segments”, with each segment typically comprising a plurality of nodes which communicate regularly with each other. All of the nodes in a segment are usually networked to each other to form a sub-network, and the segment is coupled to the network backbone through a single segment port. By coupling the nodes to the network and to each other in this manner, connectivity with the network backbone is preserved while keeping to a minimum the number of ports actually coupled to the backbone. For even more complicated networks, each segment may be divided into sub-segments, and these sub-segments may be further divided into super sub-segments to create a complex hierarchy. The segmenting principle can be extended to any desired level. Segmenting nodes in this manner has been found to improve network efficiency.
A device which is commonly used in segmenting applications is a bridge. A bridge provides a link between two entities. The coupled entities may be two separate segments or they may be a network and a segment. Currently, a wide variety of bridges are available, with many bridges being general purpose bridges having two sides, each side dealing with a large number of nodes as well as other bridges. A typical bridge comprises a first controller for dealing with a first side of the bridge, and a second controller for dealing with a second side of the bridge. A bridge, however, is just one example of a network device that may be used for interfacing a plurality of nodes to a network. Examples of other such network devices are hubs, switches, routers, gateways, etc.
The various network devices that are used for interfacing a plurality of nodes to a network typically include a plurality of working ports for coupling to the plurality of nodes, an address lookup table for storing the addresses of the working ports, an attachment port for coupling to a network, an incoming packet controller, and an outgoing packet controller. During operation these devices receive an incoming data packet from the network through the attachment port. The packet is passed on to the incoming packet controller. The controller extracts a destination address from the packet and determines whether it matches one of the addresses stored in the address lookup table. The address lookup table includes information indicating the specific port with which each address is associated. If an address match is found, then it is determined that the packet is destined for one of the working ports, and in response, the controller sends the incoming packet to that working port.
The destination address that is extracted from the packet typically comprises a large number of bits, such as for example, 48-bits. Although the entire 48-bit destination addresses and corresponding port information are normally stored as data in the address lookup table, the entire 48-bit destination addresses are normally not used to address, or point to memory locations within, the address lookup table. In other words, the entire 48-bit destination addresses are normally not used to point to the specific memory locations and memory slots within the address lookup table where the destination addresses and corresponding port information are stored. The entire 48-bits are not used to point to memory locations within the address lookup table because this would require an extremely large address lookup table which would make operation impractical.
Instead, memory locations within the address lookup table are addressed, or pointed to, by using less than the entire 48-bits of the destination addresses. By using a smaller number of bits, the size of the address lookup table can be reduced to a more practical size. One method that has been used to address the address lookup table by using less than the entire 48-bits of the destination addresses is to first compress the 48-bit destination addresses to a compressed address having fewer than 48-bits. For example, the 48-bit destination addresses may be compressed to a compressed address having 32-bits. Then, a number of adjacent bits, fewer than all 32-bits, of the compressed address are used to address the address lookup table. For example, the 5 least significant bits of the 32-bit compressed address may be used to address the address lookup table.
Using, for example, the 5 least significant bits of the 32-bit compressed address to address the address lookup table works well once the address lookup table has been generated. This method, however, can cause problems when generating the address lookup table. Specifically, the address lookup table is typically generated during use as data packets are received. When a data packet is received, the 48-bit destination address is extracted, the 32-bit compressed address generated, the 5 least significant bits of the 32-bit compressed address selected, and then the memory location pointed to by the 5 least significant bits is checked to see if it already holds the 48-bit destination address and corresponding port information. If the memory location is unoccupied, the 48-bit destination address is stored therein. If the memory location is already occupied and the contents match the 48-bit destination address, then there is no need to stored the 48-bit destination address because it is already included in the address lookup table. In this manner, the address lookup table is slowly generated.
Problems occur when the memory location pointed to by the 5 least significant bits is already occupied but the contents do not match the 48-bit destination address. This situation can occur because the same 5 least significant bits of the 32-bit compressed address can be generated by two or more different 48-bit destination addresses. In other words, when less than the entire 48-bits of the destination addresses are used to address the address lookup table, two or more different 48-bit destination addresses can end up pointing to the same memory location in the address lookup table. When this occurs a different scheme must be used to address the address lookup table because each 48-bit destination address will not end up pointing to its own memory location within the address lookup table.
Thus, there is a need for a method and apparatus for generating an address lookup table which can adapt and accommodate the scenario where two or more different destination addresses end up pointing to the same memory location in the address lookup table.
BRIEF SUMMARY OF THE INVENTION
The present invention provides a method of generating a lookup table. The method includes receiving an input address; generating a compressed address from the input address, the compressed address having fewer bits than the input address; selecting a first set of bits from the compressed address; determining whether a memory location pointed to by the first set of bits in an address lookup table includes an unoccupied memory slot; determining whether the input address matches any address stored in the memory location pointed to by the first set of bits in the address lookup table; and selecting a second set of bits from the compressed address in response to there not being an unoccupied me
Allied Telesyn International Corporation
Cooley & Godward LLP
Moazzami Nasser
Yoo Do Hyun
LandOfFree
Method and apparatus for adaptive address lookup table... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for adaptive address lookup table..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for adaptive address lookup table... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2512406