Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-03-23
2003-07-29
Kizou, Hassan (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S412000, C709S240000
Reexamination Certificate
active
06600744
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to data communications and more particularly to packet classification in data communication systems.
BACKGROUND OF THE INVENTION
Data in data communication systems are often transported in packet form. Packets include data and headers that direct the packet through the data communications network to its final destination. Routing information and other properties, such as billing information and priority, is often extracted from the packet by examining the headers at various points in the network. This type of packet classification by switches and other entities within the data communications network can require a great deal of processing bandwidth and also introduce latency in the system if it cannot be accomplished in a timely manner.
The header information of the data communications packet typically includes a source address that indicates the source of the data communications packet, a destination address that indicates the intended receiver of the packet, the particular protocol that is being used to transport the data, and other relevant information used to determine how the data packet should be treated throughout the data communication system. In order to classify the data packet and determine how it should be dealt with, the header information is examined. In a firewall application, the header information may be utilized to determine whether or not data can be passed through a particular link in the data communications system. If the packet is passed, it must be prioritized relative to other packets destined for the same link, which may be based on the class of service. In other applications, the header information may be used to determine billing information such as the cost of sending the data packet and which party is to be billed.
Data communication protocols are often structured using a number of different layers, where each layer may include a number of parameters associated with a particular data packet. Typically, these parameters are included in the header of the data packet. Thus, the parameters contained in the header of the data packet can be significant. These parameters must be efficiently assessed and processed in order to properly utilize them for routing and other data classification purposes.
Prior art solutions to the problem of filtering or classifying packets using the large amount of information contained in the packet headers include mathematically elegant solutions that are able to sort through the data in the packet header. However, these prior art solutions typically encounter problems with memory usage. In many cases the large amount of memory required to store the classification parameters required to properly analyze incoming packets renders these solutions impractical for most applications. Although the use of cache memories can help alleviate some of the obstacles created by large memory requirements, the bandwidth required to update the contents of the cache render these solutions impractical.
Similarly, in systems that have more reasonable memory requirements, the algorithms required to perform the packet classification are time consuming to the point where the delay introduced is detrimental to the system performance. In addition to this, the parameters used for classification in these systems are often stored in such a way that it is difficult to modify the classification parameters, or rules. Because the parameters used to classify the packets are often dynamic, the ability to easily modify the parameters is important in most applications.
Therefore, a need exists for a method and apparatus for packet classification that requires a limited amount of memory, is able to perform the classification in a timely manner, and allows for easy modification of the rules, or classification parameters.
REFERENCES:
patent: 6104696 (2000-08-01), Kadambi et al.
patent: 6157955 (2000-12-01), Narad et al.
patent: 6167047 (2000-12-01), Welfeld
patent: 6167445 (2000-12-01), Gai et al.
patent: 6341130 (2002-01-01), Lakshman et al.
patent: 6430184 (2002-08-01), Robins et al.
“High-Speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching,” Laskhman, et al; Comput. Commun. Rev.; vol. 28, No. 4, pp. 203-214, Oct. 1998.
“Fast and Scalable Layer Four Switching,” Srinivasan, et al; Comput. Commun. Rev.; vol. 28, No. 4, pp. 191-202, Oct. 1998.
Carr David W.
Nadj Paul
Alcatel Canada Inc.
Kizou Hassan
Pezzlo John
LandOfFree
Method and apparatus for packet classification in a data... 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 packet classification in a data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for packet classification in a data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3046325