Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
1999-01-29
2001-10-23
Coulter, Kenneth R. (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
C370S351000
Reexamination Certificate
active
06308220
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to computer networks, and more particularly to searching a routing table to configure a network switch.
BACKGROUND OF THE INVENTION
Computer networks such as local-area networks (LANs) and larger wide-area networks (WANs) route data packets from one station to another often through intermediate nodes. Recently network switches making switching decisions based on multiple OSI Layers have become favored for connecting different stations on a LAN or different LANs on a corporate backbone network. These network switches have a higher throughput than earlier hubs or repeaters since multiple connections may be dynamically made and broken between different pairs of network nodes as needed, and they significantly reduce network congestion experienced in the shared media.
FIG. 1
is a diagram of a prior-art system that configures a network switch based on a search of a routing table using a microprocessor. Routing table
20
contains entries for different network addresses. These entries may be for lower-level media-access-controller (MAC) addresses on a LAN or higher-level Internet-Protocol (IP) addresses for a WAN. Each entry contains a MAC or IP address and a port number. Incoming packets to network switch
22
contain a destination address, such as a MAC and/or IP address. For some switches capable of performing multi-layered switching, the IP address may only be searched if the MAC address matches. The traditional routers are networked devices, and they only do IP-address searches. This destination address from the incoming packet is compared to the addresses in the entries in routing table
20
until a match is found. Then the port number for the matching entry is used to configure network switch
22
, so that the data from the incoming port is forwarded to the output port identified by the port number from the matching entry in routing table
22
.
Central processing unit (CPU)
10
monitors the input ports of network switch
22
for incoming packets. When an incoming packet is detected, CPU
10
reads the destination address of the new packet. Then CPU
10
executes a search routine to look for a matching entry in routing table
20
. Once a matching entry is found, CPU
10
sends instructions to network switch
22
over bus
16
to establish a connection between the input port receiving the new input packet and the output port identified by the port number from the matching entry in routing table
20
.
When CPU
10
is a general-purpose processor, CPU instructions are read from memory
12
over bus
16
before CPU
10
executes each instruction. The search routine is a series of such instructions contained in code block
18
in memory
12
. For each entry in routing table
20
, several instructions are fetched from code block
18
, and the entry itself is read from routing table
20
in memory
12
. Thus several accesses of memory
12
over bus
16
are required. Caching of instructions in CPU
10
can reduced traffic on bus
16
, but usually caches are not large enough to contain routing table
20
.
For each entry in routing table
20
, the entry must be read from routine table
20
and compared to the destination address, which is stored in a register in CPU
10
. Within CPU
10
, arithmetic-logic-unit (ALU)
14
compares the destination address to the address in the entry read from routing table
20
. This compare is repeated for each entry read from routing table
20
until a match is found.
Thus many accesses of memory
12
by CPU
10
are required to search routing table
20
. Other incoming packets for other input ports may be detected before the search is complete. The search for these other incoming packets may need to be delayed until the first search is completed. Thus the delay or latency for these subsequent packets is increased. System throughput may be decreased, or a faster, more expensive CPU is needed to reduce delay and latency. However, the search must still be performed serially resulting in ports waiting in long queues while waiting for the CPU to finish the on-going search.
Some hardware-assisted search chips (integrated circuits) are being developed. For example, a dedicated search engine may be used rather than ALU
14
in CPU
10
. This dedicated search engine can be directly coupled to the memory containing routing table
20
. While this hardware improves the efficiency of the search engine compared to using the CPU, it does not solve the problem of serial search. Furthermore, the speed of the search is limited by the bandwidth (number of pins allocated to the table memory).
Embedded-DRAM Graphics Display Systems
The assignee has recognized the problem of bottlenecks to external dynamic-random-access memory (DRAM) in graphics display systems, and has pioneered embedded DRAM for graphics controllers. See for example: Puar et al., “Graphics Controller Integrated Circuit Without Memory Interface”, U.S. Pat. Nos. 5,650,955 and 5,703,806. These embedded-DRAM graphics controllers have been used predominantly for portable PC's such as laptop and notebook PCs.
Although graphics controllers are in a different technical field hand network switches, the inventor has realized that such embedded DRAM technology could solve performance and cost problems for network switches. While many view embedded DRAM technology as useful only for portable systems, the inventor realizes that computer-network routers could benefit from the performance and cost improvement of embedded DRAM.
What is desired is a search engine for a network switch. It is desired to have a dedicated search engine search a network routing table for an entry with a matching MAC or IP address. It is further desired to use an embedded DRAM containing the routing table. It is desired to locate the search engine and the embedded DRAM on the same integrated circuit chip, allowing a very wide data path between the search engine and the routing table. It is further desired to increase the speed of the search engine by using an ultra-wide data path to the routing table. A parallel architecture for the search engine is also desired to allow searches for different input ports to occur at the same time, increasing throughput and decreasing latency. It is desired to provide a same low latency for all input ports even when other searches are in progress. A highly-parallel multiple-port search engine is desired.
SUMMARY OF THE INVENTION
A parallel-search integrated circuit has a free-running sequencer that repeatedly outputs a sequence of addresses in a loop. A table stores a plurality of entries. The table outputs an entry in response to an address from the free-running sequencer.
A plurality of search engines are included. Each search engine receives the entry from the table. A first search engine compares at least a portion of the entry to a first input and generates a first match signal when the first input matches the at least a portion of the entry. A second search engine compares the at least a portion of the entry to a second input and generates a second match signal when the second input matches the at least a portion of the entry. A third search engine compares the at least a portion of the entry to a third input and generates a third match signal when the third input matches the at least a portion of the entry.
The free-running sequencer repeats the sequence of addresses once all entries have been read from the table. The first search engine begins a search once the first input is received, beginning the search at any address in the sequence of addresses and continuing until all entries have been compared by the first search engine or until the first match signal is generated. The second search engine begins a search once the second input is received, beginning the search at any address in the sequence of addresses and continuing until all entries have been compared by the second search engine or until the second match signal is generated. Likewise, the third search engine begins a search once the third input is received, beginning the search at any addre
Auvinen Stuart T.
Coulter Kenneth R.
NeoMagic Corp.
LandOfFree
Circulating parallel-search engine with random inputs for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Circulating parallel-search engine with random inputs for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circulating parallel-search engine with random inputs for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2610190