Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-11-08
2004-08-17
Pham, Chi (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
Reexamination Certificate
active
06778530
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to data communications, and more particularly to systems and methods for processing network data according to rules requiring multiple field matches.
BACKGROUND OF THE INVENTION
With the explosion in growth of data communication networks, a need has arisen for faster table lookup operations for handling the transmission of network data. Within a network structure, data is typically transferred between a source station and a destination station in the form of a packet. A network device, such as bridge or router or similar system, will receive a data packet and forward it on toward its final destination. The forwarding operation of such network devices involves a basic forwarding lookup operation that is performed within the device. In a forwarding lookup operation, the initial portion (“header”) of a packet is examined, and using a particular destination address field within the header, a table of known destinations is searched. The result of that search allows the packet to forwarded to an output port, and onward toward its destination. The operation is referred to as a “basic” forwarding lookup operation, as it involves a lookup on only one field (destination address) from the packet header.
Within a high speed network device, this lookup function may be performed by a portion of the device referred to as a lookup engine. A basic lookup engine manages forwarding (routing) table that can include a potentially large number of rules. Each rule tells the router how to process a certain class of packet, those packets whose headers match the rule. The routing table thus includes a number of database entries that are indexed by header field information. Such a lookup engine receives a data field extracted from a packet, and uses the data field to retrieve routing instructions from the routing table.
The use of the term “basic” to describe single field lookup operations is not intended to imply that such operations are easily accomplished. Some types of single field lookup operations can require sophisticated lookup operations. In particular, many types of network protocols can require “longest prefix matching” lookup operations. Such operations include rules that provide different routing instructions according to variable length portions (prefixes) within a given data field. As just one example, two routing rules are set forth below.
192.9/16→Nexthop “
A”
192.9.4/24→Nexthop “
B.”
The addresses are written by separating “octets” (8-bit sections) by periods. Thus, the address 192.9.0.0 is equal to binary 11000000 00001001 00000000 00000000. The first rule requires that the first 16-bits of the 32-bit address be examined, and if they are equal to 192.9 (11000000 00001001), the packet will be forwarded to a location identified as nexthop A. The second rule requires that the first 24-bits of the address be examined. If the first 24-bits is equal to 192.9.4 (11000000 00001001 00000100), the packet will be forwarded to a location nexthop B.
It is noted that the two described rules “overlap.” That is, an address of 192.9.4.X (where X is a binary octet of any value) will match both rules. Such rule overlap situations are typically resolved by giving the longest prefix precedence. Thus, the example address 192.9.4.X would be forwarded to nexthop B according to longest prefix matching.
The lookup operation on a prefix may be accomplished with a prefix matching engine. Such engines may be formed within an integrated circuit, or be implemented as an algorithm executed by a general purpose or special purpose programmable processor. A novel prefix matching engine is set forth in commonly owned, co-pending U.S. patent application Ser. No. 09/401,475 entitled “METHOD AND APPARATUS FOR HIGH SPEED LONGEST PREFIX AND MASKED PREFIX TABLE SEARCHES” by the present inventor. This application will be referred to hereinafter as “LONGEST PREFIX MATCHING METHOD AND APPARATUS.” The contents of this application are incorporated by reference herein.
While the longest prefix matching problem raises considerable challenges in the implementation of network devices, there is an increasing need to address even more complex functions. One such function is “multiple field matching.” Multiple field matching looks “deeper” into packet information in order to determine routing information. For example, many networking systems can include features that extend beyond a simple forwarding function. Such features include access control lists, policy-based routing, flow classification, traffic accounting, quality of service (QOS), and class of service (COS). As a result, rather than forward data packets to the same location based on destination information alone, such systems must discriminate among packets going to the same destination based on various additional criteria within the packet header.
As just one example, flow classification rules may include fields that specify an IP destination address range, a destination port range, an IP source address range, a source port range, and a protocol. A number of such rules make up a classification table. For each incoming packet, the classification table is searched to determine which rule, if any, applies to the packet; a rule is said to apply to a packet only if the packet's header values in all five fields (destination address, destination port, source address, source port, and protocol) satisfy the corresponding ranges specified in the rule. When more than one rule applies to a packet, then a relative priority among rules determines which one is returned from the table search process. Because there can be thousands of such rules, the standard approach for multiple field classification table searching, which is to scan sequentially through the rules in the table testing the packet header against each rule, can take considerable time to execute.
An example of a particular multiple field key is shown in FIG.
1
.
Due to the complexity involved in multiple field matching, such processing can present a considerable bottleneck in a network system. To accomplish multiple field matching at high speed is generally regarded as more difficult than longest prefix matching at comparable speed.
It would be desirable to provide a system that can accomplish multiple field matching operations, but not require costly, or overly complex memory devices to implement.
It would also be desirable to provide a multiple field matching system that is relatively compact when implemented in hardware.
SUMMARY OF THE INVENTION
According to disclosed embodiments, a system provides multiple-field matching capabilities for table searching. The matching is based on multiple key fields where each rule has a specification (such as a range or prefix) or a wild card in each field. A rule match occurs when all fields of the search satisfy the corresponding fields of the rule. The system includes a number of single field lookup engines that are connected together in a pipelined fashion. In one embodiment, the pipelined arrangement allows the system to provide one multiple field lookup result per memory clock cycle. In another embodiment, a smaller number of lookup engines can be employed to provide one multiple field lookup result for every two memory clock cycles.
According to one aspect of the embodiments, a first field lookup can compress ranges of input key field values into “equivalence class” values. Equivalence class values can then be combined with other fields and/or equivalence class values to generate an index value to associated data.
According to another aspect of the embodiments, a lookup operation can compress ranges of more than one field into equivalence class values.
According to one aspect of a preferred embodiment, a system provides multiple field lookups that include longest prefix matching, and an arbitrary number of additional fields.
According to another aspect of a preferred embodiment, a system includes a memory system for storing a classification rule data structure, and performs multiple field lookups in a pipelined fa
Ferris Derrick W
Harrity & Snyder LLP
Juniper Networks, Inc.
LandOfFree
Method and apparatus for multiple field matching in network... 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 multiple field matching in network..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for multiple field matching in network... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3326408