Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-12-20
2004-06-22
Rones, Charles (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06754662
ABSTRACT:
FIELD OF THE INVENTION
This invention generally relates to exchanging data over a data communications network and, more particularly, to a method and apparatus for classifying data packets in a network device.
BACKGROUND OF THE INVENTION
The introduction of new differentiated network services, such as Virtual Private Networks (VPN), firewalls, encryption, Network Address Translation (NAT), guaranteed Quality of Service. (QoS), traffic billing, etc., need an implementation of packet classification. In particular, for Diffserv edge routers in the newly-proposed DiffServ (Differentiated Services) architectures, the packet classification must be done at wire rate to guarantee the service agreed upon or purchased under a Service Level Agreement (SLA) i.e., the QoS.
Although the need for wire rate packet classification would seem to dictate a hardware approach, software-based fast packet classifiers offer low-cost implementation and high flexibility as compared to hardware-based approaches. However, software approaches suffer from the widening gap between CPU performance and memory-access latency. For example, most conventional CPUs operate at speeds in excess of 500 MHz, with each instruction cycle taking 2 nanoseconds. By comparison, the fastest widely available dynamic RAM (DRAM) runs at 60 nanoseconds, which means that a single memory fetch is approximately 30 times slower than a CPU instruction. Every indication suggests that CPU speed will continue to increase, while DRAM access speeds have remained stable for several years. Accordingly, an effective to software-based packet classification approach should consider memory latency issues.
As for existing packet classification schemes, most aim at accelerating the packet classification process. However, they are generally dependent on factors that are difficult to control. For example, packet classification schemes such as “Tuple Space Search” (TSS) and “Recursive Flow Classification” (RFC) aim at accelerating packet classification by performing some optimizations based on the sparse field-values distribution in the real-life filters set. Thus, the performance of those schemes will heavily depend on the actual field-values distribution for the real-life filters.
Other problems and issues are not adequately addressed by existing packet classification schemes. For example, it is noted that existing packet classification schemes do not take advantage of traffic information available from statistics of past performance. Moreover, although IP flows are not generally long-lived in most current applications, demand is growing for long-lived flows such as streamed multimedia data, Web cache server based traffic, persistent HTTP, Internet Telephony, FTP, etc. Finally, there are also no approaches that efficiently, accurately and consistently classify fragmented IP packets. It has been reported in some recent studies that the fragmentation ratio in today's Internet traffic is around 2% on the average. However, for some traffic flows, very high percentages up to 47% have been observed. To accurately and consistently classify the fragmented packets based on Layer-4 or Layer-7 information, per-flow tracking and management must be maintained due to the lack of the Layer4 and Layer-7 information-in the fragmented packet headers except the first one in each fragmentation family.
SUMMARY OF THE INVENTION
The present invention relates to a method and apparatus for classifying data packets.
A packet classification architecture according to the invention includes a cached hash table that stores a subset of classification identifiers (i.e. classIDs) for a plurality of data flows. A forwarding engine coupled to the cache receives packets and first attempts to classify the packet by generating a hash key based on header information from the packet and using the hash key to lookup a corresponding entry in the hash table. A hash caching policy according to the invention aims at maintaining high classification speeds by (1) employing a hash function that evenly distributes hash key indexes, thus reducing the likelihood of collisions and by (2) employing a hash removal scheme that uses Internet traffic statistics and characteristics to improve the likelihood that hash entries corresponding to statistically important flows will remain cached (i.e. those entries will have a higher probability of being accessed from the cache for incoming packets belonging to those flows).
In accordance with one aspect of the invention, a method of classifying a data packet includes generating a hash key based on flow information in the data packet, looking up, an entry among a plurality of entries in a hash table containing a classification identifier using the hash key, and maintaining the hash table in accordance with network traffic statistics.
In accordance with another aspect of the invention, an apparatus for classifying a data packet comprises a cache adapted to store a plurality of hash table entries, a forwarding engine coupled to the cache and having an input for receiving the data packet, the forwarding engine being adapted to retrieve a classification identifier from one of the hash table entries in the cache based on a hash key generated from flow information extracted from the received data packet, and a control engine coupled to the cache, the control engine being adapted to maintain the plurality of hash table entries in the cache in accordance with network traffic statistics.
REFERENCES:
patent: 5784539 (1998-07-01), Lenz
patent: 5832182 (1998-11-01), Zhang et al.
patent: 6212184 (2001-04-01), Venkatachary et al.
patent: 6434662 (2002-08-01), Greene et al.
Rones Charles
Steubing McGuinness & Manaras LLP
LandOfFree
Method and apparatus for fast and consistent packet... 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 fast and consistent packet..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for fast and consistent packet... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3337135