Method and apparatus for forwarding network traffic

Details Method and apparatus for forwarding network traffic Method and apparatus for forwarding network traffic

1998-10-05

2003-04-22

Hsu, Alpus H. (Department: 2662)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C370S389000, C370S401000, C370S428000, C709S238000, C709S241000

Reexamination Certificate

active

06553000

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
.
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.
The lookup tables may be kept in sorted or random order. Typically, the lookup table contains hundreds of thousands of different network addresses and each address the switching device receives is added to the lookup table indiscriminately. The larger the lookup table, the slower the switching device can search the table, thereby reducing its overall performance. Generally, each address in the lookup table is the same length (e.g., 32 bits for Internet Protocol addresses). If addresses of different lengths are maintained by the switching device, such addresses require separate searches and separate lookup tables, which also reduces the performance and increases the cost of the switching device. Additionally, if the switching device does not find an exact match in the lookup table, it either does not forward the network frame or transmits the network frame on all ports, depending on the particular switching device.
An objective of the present invention, therefore, is to provide a high-speed network switching device that can quickly and efficiently search through address lookup tables and that overcomes the limitations of the prior art.
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, the lookup table includes network addresses that are maintained in sorted order (e.g., ascending or descending order). By ordering the network addresses, a search engine can efficiently search the lookup table to find a network address in the table that matches a destination address in the network frame.
In another aspect, the lookup table includes both network addresses and collapsed network addresses. A collapsed network address represents a group of network addresses. Collapsed addresses are useful when a switching device does not know an exact address, but knows that the address is a member within a group. The sorted ordering also allows for efficient searching of collapsed network addresses and network addresses when an exact match is not found. For example, when an exact match fails, the switching device searches the collapsed addresses and network address by using a comparison field that the search engine applies to the destination address in the network frame. The comparison field can include mask bits that mask a portion of the destination address or a length value that indicates the bits that should be compared. In the case of mask bits, the masked destination address is compared to the network address of the current table entry. If there is a match, then port information is obtained from the current table entry and the network frame is forwarded to that port. For example, when the table is in ascending order, the search engine starts from a point where the search failed and analyzes each table entry in descending order. The mask bits are applied to the destination address and compared to the table entry. If the masked destination address matches the table entry, then the search is complete. If not, the next table entry in descending order is analyzed. This process continues until a match is found or the end of the table is reached. A similar technique may be used for a length value instead of the mask bits. Alternatively, a combination of mask bits and a length value may be used. Additionally, the length value and/or mask bits may be applied to the lookup table entry.
In yet another aspect of the invention, the lookup table includes network addresses that differ in length. The addresses can be virtually any desired length of bits. Additionally, only one search is performed on the lookup table, despite the differing address lengths. The ability to store and search multiple address lengths in the lookup table allows the switching device to work efficiently with different types of networks having different data frames formats.
In still yet another aspect, fictitious network addresses are added to the lookup table to expedite searches performed by the search engine. The search engine inserts a fictitious network address at the point where the search failed. The ficti

Affiliated with

Also associated with

Rating

Method and apparatus for forwarding network traffic 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 forwarding network traffic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for forwarding network traffic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3023640