Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-12-13
2002-10-08
Olms, Douglas (Department: 2732)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395310, C370S356000
Reexamination Certificate
active
06463067
ABSTRACT:
CROSS REFERENCE TO RELATED APPLICATIONS
None
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not Applicable
BACKGROUND OF THE INVENTION
The present invention is related to the field of data communication networks.
In data communication networks, network devices such as switches are used to route packets through the network. Each switch typically has a number of line interfaces, each connected to a different network segment. When a packet is received at a given line interface, forwarding logic determines which line interface the packet should be transmitted from, and the packet is transferred to the appropriate outgoing line interface to be sent toward its destination in the network.
It is known to employ specialized forwarding logic in conjunction with a microprocessor on the line interface. The microprocessor is responsible for overall packet processing and forwarding. The forwarding logic stores one or more forwarding tables in high-speed memory. The forwarding tables contain information indicating how packets should be forwarded, typically based on a destination address contained within the packet. The forwarding tables are maintained by a background process executing in the switch. When a packet is received at a line interface, the microprocessor generates a lookup request containing selected information from the packet, and issues the lookup request to the forwarding logic. The forwarding logic carries out a specialized search of one or more forwarding tables, and returns a lookup result to the microprocessor. The lookup result contains an indication of whether forwarding information has been found, and if so then it contains the forwarding information itself. The microprocessor uses the forwarding information to forward the packet. This architecture is used to achieve packet forwarding rates greater than what is achievable using a microprocessor alone.
It is also known to perform packet filtering in network devices such as switches. Packet filtering can be used to achieve various network management goals, such as traffic monitoring and security goals. Filtering criteria are established by network administrators, and provided to the switches or other devices that carry out the filtering operation. Packets received by the switches are examined to determine whether their characteristics match the criteria for any of the established filters. For packets that satisfy the criteria for one or more filters, predetermined actions associated with those filters are carried out. For example, under certain circumstances it may be desirable that packets originating from a given network node be discarded rather than being forwarded in the network. A filter can be defined in which the criterion is that a packet source address exactly match a specific value, which is the address of the node whose packets are to be discarded. The action associated with the filter is the discarding of the packet. When a packet is received whose source address satisfies this criterion, it is discarded rather than being forwarded in the normal fashion.
There are a number of different kinds of criteria that may be used to filter packets. These criteria include exact matches as well as range checking, i.e., checking whether a value in a packet falls in some range of values. Numerous packet parameters can be used as criteria, such as source address, destination address, port identifiers, type of service, and others. To be useful, packet filtering processes must allow filters to be flexibly defined using different combinations of these and other criteria.
Because of this complexity inherent in packet filtering, it has traditionally been performed largely or exclusively in software within switches or other network devices supporting packet filtering. Software-based filtering, however, presents a bottleneck when high packet forwarding performance is required. Network administrators have had to make undesirable tradeoffs between network responsiveness and network security, for example, because previous systems have not been capable of robust packet filtering at line rates.
BRIEF SUMMARY OF THE INVENTION
In accordance with the present invention, packet processing logic in a network device is disclosed that provides high-speed forwarding searching along with packet classification for packet filtering purposes. A novel request and response architecture is used between a packet-processing microprocessor and dedicated searching and classification logic to avoid communications bottlenecks that might otherwise reduce forwarding performance.
The packet processing logic includes a request queue for receiving lookup requests from a packet processor, where each request includes various information elements from a received packet, and each request indicates that both a route lookup and a packet classification are to be performed based on the information elements contained in the request. A route lookup engine (RLE) has an input coupled to the request queue for receiving selected information elements from the requests. Similarly, a packet classification engine (PCE) has an input coupled to the request queue. Based on the information elements in each request, the RLE searches for forwarding information indicating how the packet corresponding to the request should be forwarded, and the PCE performs a classification process and generates classification information about the packet corresponding to the request. For each request, the forwarding information from the RLE and the classification information from the PCE are combined into a single result stored in a result queue. Each result is provided to the packet processor in a single communication transaction therewith.
This shared request and result architecture enhances the efficiency and speed of communication between the packet processor and the PCE and RLE, allowing for high-speed packet forwarding and classification.
Other aspects, features, and advantages of the present invention are disclosed in the detailed description that follows.
REFERENCES:
patent: 5905723 (1999-05-01), Varghese et al.
patent: 5918074 (1999-06-01), Wright et al.
patent: 6069895 (2000-05-01), Ayandeh
patent: 6081522 (2000-06-01), Hendel et al.
patent: 6160811 (2000-12-01), Partridge et al.
patent: 6192051 (2001-02-01), Lipman et al.
patent: 6259699 (2001-07-01), Opalka et al.
patent: 6266706 (2001-07-01), Brodnik et al.
patent: 6285679 (2001-09-01), Dally et al.
Cherian Sanjay G.
Hebb Andrew T.
Ascend Communications, Inc.
Olms Douglas
Sam Phirin
Troutman Sanders LLP
LandOfFree
Submission and response architecture for route lookup and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Submission and response architecture for route lookup and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Submission and response architecture for route lookup and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2990944