Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-10-05
2004-01-13
Olms, Douglas (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S401000, C370S471000
Reexamination Certificate
active
06678269
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to networks, such as telephone and computer networks, and, more particularly, relates to routing information through such networks.
BACKGROUND OF THE INVENTION
A network allows two or more parties to communicate with each other. In their simplest form, networks generally include transmission lines and switching devices (e.g., routers, switching routers, switches, etc.). The transmission lines carry signals (e.g., electrical, optical, etc.), while the switching devices are intermediate stations that establish temporary connections between transmission lines. In telephone networks, for example, a caller's line goes to a switching device where the actual connection is made to the called party. In computer networks, devices such as routers receive messages on the network and forward the messages to their correct destinations. Computer networks can be as small as a local area network (LAN) consisting of a few computers, printers, and other devices, or it can consist of many computers distributed over a vast geographical area (e.g., the Internet).
An example computer network
10
is shown in FIG.
1
A. The network includes two local segments
12
and
14
, and connection to a remote network
16
. Nodes, labeled as A-J, represent computers connected to the local segments. A switching device
20
includes three ports
22
-
24
and switches network traffic between segments
12
,
14
, and the remote network
16
. Network
16
may also include switching devices, such as switching device
21
, which then connects other segments (not shown) to the network. Switching device
20
allows the nodes on one segment to communicate with nodes on other segments and to other switching devices. The nodes communicate with each other through a protocol (e.g., HTTP, TCP/IP, SMB, etc.) which allows the nodes to transmit and receive network frames (a network frame includes a destination address, a source address, and a data field). When switching device
20
receives a frame from a node, it analyzes the destination address by searching a lookup table
26
, shown in FIG.
1
B. Lookup table
26
includes table entries having a network address field and a port field. When the destination address is matched to a network address in the lookup table, switching device
20
determines which port to forward the frame to by obtaining the port number corresponding to the matched network address. For example, if node A on segment
12
sends a message to node H on segment
14
, switching device
20
receives the message from node A and in response searches the entries in the network address field of lookup table
26
. Table entry
28
contains the network address for H. A corresponding port field
30
for network address H indicates that the frame should be forwarded over port
2
. Additional background information on switches can be found in a number of references, such as Fast Ethernet (1997) by L. Quinn et al.,
Computer Networks
(3
rd
Ed. 1996 by A. Tannenbaum, and
High-Speed Networking with LAN Switches
(1997) by G. Held, all of which are incorporated herein by reference.
The switching device can obtain the network addresses for the lookup table in different ways, depending on the particular implementation of the switching device. For example, the switching device may snoop network traffic so that when a frame is received on a port, the switching device determines if the frame's source address is in the table and, if it is not, adds an entry containing the source address and the inbound port to the table. Thus, the switching device is said to “learn ” addresses and port numbers from any frame that is transmitted by a node. Another technique some switching devices, such as routers, use to obtain the lookup table is from other switching devices through a special protocol. Thus, routers supply network addresses to each other to supplement their lookup tables.
Some switching devices need to be able to forward network frames having different data frame formats. For example, a switching device may forward network frames containing MAC addresses (48 bit address), IP addresses (32 bit addresses), IPX addresses (
32
), IPV
6
addresses (128 bits), etc.
FIG. 2
shows a prior art switching device
32
that forwards frames of different formats. A packet analysis circuit
34
receives a network frame and analyzes its format. Based on the analysis, the packet analysis circuit forwards address information from the network frame onto either a MAC search engine
36
, an IP search engine
38
, or an IPX search engine
40
. Each search engine
36
,
38
, and
40
has access to its own independent memory
42
,
44
, and
46
, respectively, which store forwarding information in the appropriate format for its search engine. When one of these search engines receives the address information, they perform a search on their memory and pass forwarding information obtained from the search onto other forwarding logic in the switch.
Using such a prior art switch has several drawbacks. First, the switch requires a separate search engine and separate memory for each different database format, which is costly and inefficient. Second, the memories must be sufficiently sized so that there is adequate memory space for each database format, even though a particular user may only require a few entries having one format. For example, a user may only require a few MAC database entries, while requiring excessive IP entries. In such a case, the memory containing MAC entries has wasted memory locations, while the memory storing IP entries is overloaded. Also, currently there is no way to reallocate some of the extra IP entries into the spare memory locations in the MAC database.
An objective of the present invention, therefore, is to provide a highspeed network switching device that can quickly and efficiently search through an address lookup table and that supports multiple database formats.
SUMMARY OF INVENTION
The present invention provides a switching device (e.g., router, switch, switching router, etc.) that forwards network traffic to a desired destination on a network, such as a telephone or computer network. The switching device includes multiple ports and uses a lookup table to determine which port to forward network traffic over. The network traffic is typically in the form of network frames that include source and destination addresses.
In one aspect of the invention, a single lookup table can store multiple database formats for supporting different network protocols (e.g., MAC, IP, IPX, IPV
6
, Appletalk, etc.). The different database formats require addresses and forwarding information of different lengths. Additionally, a single search engine may be used to search the lookup table in order to obtain the forwarding information.
In another aspect of the invention, the different database formats are grouped into separate sections of memory, rather than intermingled, by prepending format identification bits to the most significant bit position of the keys stored in the lookup table. As a result, the search engine can perform the same search regardless of the database format.
Thus, the invention allows for a multi-database, single memory system wherein the size of the database formats can be customized and changed dynamically for a particular user. Additionally, memory space is not a fixed size for each database format, but, instead, can be changed to allow the databases to differ in size and for the size to dynamically change (i.e., the database sizes change while the switch is operational). Additionally, the search engine algorithm is simplified since it views the entire memory as a single database without regard to the disparate database formats contained therein.
REFERENCES:
patent: 4201890 (1980-05-01), Lawrence et al.
patent: 5214639 (1993-05-01), Herion
patent: 5386413 (1995-01-01), McAuley et al.
patent: 5414704 (1995-05-01), Spinney
patent: 5459724 (1995-10-01), Jeffrey et al.
patent: 5566170 (1996-10-01), Bakke et al.
patent: 5608726 (1997-03-01), Virgile
patent:
Cathey James E.
Ganesh Jayasenan Sundara
Helbling Michael Dale
Michels Timothy Scott
Alcatel
Brooks PC Michael Blaine
Cordeir David A.
Naglestad Andrew
Nguyen Brian
LandOfFree
Network switching device with disparate database formats does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Network switching device with disparate database formats, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network switching device with disparate database formats will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3256951