Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-05-01
2004-02-17
Vanderpuye, Kenneth (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S389000
Reexamination Certificate
active
06693908
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to layer
2
(and above) switching of data packets in a non-blocking network switch configured for switching data packets between subnetworks and more particularly to the efficient evaluation of equations at a network switch port.
2. Background Art
Local area networks use a network cable or other media to link stations on the network. Each local area network architecture uses a media access control (MAC) enabling network interface devices at each network node to access the network medium.
The Ethernet protocol IEEE 802.3 has evolved to specify a half-duplex media access mechanism and a full-duplex media access mechanism for transmission of data packets. The full-duplex media access mechanism provides a two-way, point-to-point communication link between two network elements, for example between a network node and a switched hub.
Switched local area networks are encountering increasing demands for higher speed connectivity, more flexible switching performance, and the ability to accommodate more complex network architectures. For example, commonly-assigned U.S. Pat. No. 5,953,335 discloses a network switch configured for switching layer
2
type Ethernet (IEEE 802.3) data packets between different network nodes; a received data packet may include a VLAN (virtual LAN) tagged frame according to IEEE 802.1q protocol that specifies another subnetwork (via a router) or a prescribed group of stations. Since the switching occurs at the layer
2
level, a router is typically necessary to transfer the data packet between subnetworks.
Efforts to enhance the switching performance of a network switch to include layer
3
(e.g., Internet protocol) processing may suffer serious drawbacks, as current layer
2
switches preferably are configured for operating in a non-blocking mode, where data packets can be output from the switch at the same rate that the data packets are received. Newer designs are needed to ensure that higher speed switches can provide both layer
2
and above switching capabilities for faster speed networks such as 100 Mbps or gigabit networks.
However, such design requirements risk loss of the non-blocking features of the network switch, as it becomes increasingly difficult for the switching fabric of a network switch to be able to perform layer 3 processing at the wire rates (i.e., the network data rate).
Commonly assigned U.S. patent application Ser. No. 09/430,753, filed Oct. 29, 1999 and entitled “Apparatus And Method For Identifying Data Packet Types In Real Time On A Network Port Switch” discloses one arrangement that enables a network switch port to provide layer
2
and above switching capabilities. In these disclosed arrangement, equations are evaluated in a network switch port based on min term comparisons to generate a tag which identifies the incoming data packet, as well as the action that needs to be performed by the network switch port. For example, assume the following equation is evaluated:
EQ1
=
M1
*
M2
*
M3
*
M4
+
M1
*
M5
*
M6
*
M7
Where
M1
=
IPv4
frame
//
byte
(
0
)
==
8
′
hx4
M2
=
protocol
field
is
TCP
M3…
In conventional arrangements, the equation EQ1 is evaluated by comparing each of the min terms M
1
, M
2
, M
3
. . . If the comparison for each min term is a true condition, then the end condition is matched in EQ1 causing a tag to be generated which corresponds to the condition specific for EQ1. Although this equation evaluation technique is effective, conventional implementation techniques may cause unnecessary computations to be performed on the equation. For example, in EQ1, if the incoming frame is not a IPv4 frame, this equation is deemed false after evaluation of the min term M
1
with the first byte. Thus, the continued evaluation of min terms M
2
, M
3
. . . M
7
wastes resources, reducing the computing efficiency in the network switch port.
SUMMARY OF THE INVENTION
There is a need for an arrangement that enables a network switch to provide layer
2
switching and layer 3 switching capabilities for 100 Mbps and gigabit links without blocking of the data packets.
There is also a need for an arrangement that improves the evaluation of equations so that once the result of the equation is know, no further computations are performed on the equation.
These and other needs are attained by the present invention, where a network switch includes network switch port filter configured for evaluating an incoming data packet. The filter includes a min term memory configured for storing min term values. Each min term value is stored based on a location of a corresponding selected byte of the incoming data packet for comparison, an expression portion specifying a corresponding comparison operation, and a template identifier field that specifies templates that use the corresponding min term. The template identifier field includes an equation identifier and an obsolete equation identifier. A header memory is configured for storing an effect min term and a plurality of equation identifiers. The effect min term specifies which min terms are necessary for comparison. A min term generator is configured for simultaneously comparing a received byte of the incoming data packet with the necessary min terms that correspond to the received byte and generates respective min term comparison results. An equation core is configured for evaluating equations and for generating a frame tag identifying the incoming data packet based on the min term comparison results relative to the templates. The equation core is configured to identify equations which are no longer relevant. A content addressable memory (CAM) is configured to store the equations which are no longer relevant. A min term controller is configured to update the effect min term based on a comparison between the contents of the CAM and the equation identifiers of the header memory.
One aspect of the present invention provides a method, in a network switch, of evaluating an incoming data packet at a network switch port. The method includes storing a plurality of templates for equations configured for identifying respective data formats, each template having at least one min term configured for comparing a corresponding prescribed value to a corresponding selected byte of the incoming data packet. Header information associated with the min terms is also stored. The header information includes effect min term fields and a plurality of equation identifiers. Each effect min term field specifies which mm terms are necessary for comparison with the corresponding selected byte. The effect min term is read to specify which of the min terms are necessary for comparison. The method includes simultaneously comparing, to the selected byte, the necessary min terms that correspond to the selected byte as the selected byte is received by the network switch port. An obsolete equation is identified which needs no further evaluation based on a comparison of the necessary min terms with the selected byte. The obsolete equation is stored in a content addressable memory (CAM). The effect min term fields are updated based on the obsolete equation specified in the CAM.
Thus, the apparatus and method if the invention advantageously reduces the processing of equations by not evaluating equations which are determined to be obsolete.
Additional advantages and novel features of the invention will be set forth in part in the description which follows and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The advantages of the present invention may be realized and attained by means of instrumentalities and combinations particularly pointed in the appended claims.
REFERENCES:
patent: 5953335 (1999-09-01), Erimli et al.
Chow Peter Ka-Fai
Tzeng Shr-jie
Advanced Micro Devices , Inc.
Kading Joshua
Manelli Denison & Selter PLLC
Stemberger Edward J.
Turkevich Leon R.
LandOfFree
Apparatus and method for efficient evaluation of equations... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for efficient evaluation of equations..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for efficient evaluation of equations... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3340115