1. Field of the Invention
The present invention relates to a search mechanism and associated implementations for locating quickly and efficiently items of data associated with a given identifier. It is particularly useful in communication hubs such as bridges which are used in computer communication networks.
2. Description of Related Art
Computer networks are typically made up of a number of devices, eg user stations, data storage devices, output devices, etc, which are arranged to be able to communicate with each other. This is achieved by interconnecting the devices by way of communication hubs. The simplest form of such a hub is a repeater. A hub in general terms has a plurality of ports, to each of which a network device or another hub may be connected. A repeater functions to output each communication received on any port to each of the other ports. This ensures that any communication sent by any device reaches all other devices connected to the repeater, and thus reaches its intended destination, although a considerable number of unnecessary communications appear on the network.
This is not a problem when the volume of communications traffic on the network is relatively low but problems can occur in high volume situations when communication between network devices can be noticeably slowed.
Another type of known network communication hub, the bridge or switch, attempts to reduce this problem. In particular a bridge, when it receives a communication on a particular port outputs it only to that port or those ports necessary for the communication to reach its intended destination(s). To enable a bridge to function in this manner it is necessary for the bridge to maintain a database which relates intended destinations of communications packets to the ports of the bridge. On receipt of a communication the bridge must read from the data base the port associated with the intended destination of the packet and output it accordingly.
In the Ethernet network standard all network devices are identified by a Media Access Control (MAC) address. These addresses are made up of 48 bits (6 bytes) enabling a very large number of devices (2.8.times.10.sup.4) to be uniquely identified. It is recognised however that a given bridge need only store details of a limited number of MAC addresses. This is because only a limited number of devices will communicate via any given bridge, and also it is known that it is not necessary to maintain details of a MAC address for longer than a predetermined time after its last use. The "timing out" of MAC addresses may occur for instance 15 minutes after the last use.
Thus it has been proposed that a bridge should store details of 8000 MAC addresses. These details would include, as mentioned above, the port of the bridge with which that MAC address is associated. Other information, such as the time of last use, may also be stored related to each MAC address.
In operation it is therefore necessary on reception of a packet, to search on the basis of the destination MAC address to find which port or ports of the bridge the packet should be sent to. Given that within the fast Ethernet standard communications may occur at speeds up to 100 Megabits per second (100 Mbps), in order for the bridge to keep up with the communications, it is necessary to perform the look-up in 6 .mu.s.
USPTO Backgrounds
USPTO Backgrounds