Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-03-02
2001-09-25
Black, Thomas (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C002S004000, C002S010000, C002S102000, C002S103000, C002S200100, C002S205000
Reexamination Certificate
active
06295532
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to communication devices, and specifically, to an apparatus and method for classifying information received by communications devices.
2. Background Information
Small and medium businesses typically have networks comprised of local area networks (“LANs”), ranging between 10 Mega bits per second (“Mbps”) to 100 Mbps, that carry information between stations for a wide range of applications. The applications can include a mixture of voice, video, interactive, web browsing, file transfers, etc., each of which has different minimum requirements for latency, jitter, and data loss to ensure quality communication. The internal office LANs can either provide sufficient bandwidth or are economically upgradable to provide an order of magnitude increase in bandwidth.
The connection to a wide area network (“WAN”) is however another matter. The bandwidth is not easily upgradable due to the cost of WAN access circuits. Various queuing techniques have been employed in WAN access equipment in attempts to provide sharing of the limited circuit bandwidth among the different types of data. These queuing techniques typically have limited applications and undesirable characteristics. For example, in one queuing technique, queues are serviced in strict priority order, which tends to starve low priority data types. Another technique, called Weighted Fair Queuing, solves the starvation effects but it is computational intensive and does not provide guaranteed bandwidth, delay bound or jitter bound characteristics for data types that need these characteristics.
In implementing such queuing techniques, incoming data must first been identified and thereafter, classified for queuing allocation. Current routers, which provide some form of classification system, do so by combining search technologies previously used for routing table lookups. These technologies rely on algorithms such as the Patricia tree (as described by Don Morrison in “Practical Algorithm to Retrieve Information Coded In Alfanumeric,” Journal of the ACM, October 1968), or the Lulea tree (as described by Mikael Degermark of the Lulea University of Technology in “Small Forwarding Tables for Fast Routing Lookups,” Computer Communications Review, October 1998), search algorithms to perform lookup operations of various portions of the internet protocol (IP) header. The results from these searches are combined in some fashion (e.g., using Cross Product tables or arrays, as described by V. Srinivasan of Washington University in “Fast and Scalable Layer Four Switching,” Computer Communications Review, October 1998) and used to formulate a “class” for the incoming data.
Existing routing search algorithms are used to handling definitions of the form “Address A=route n”. To apply an existing routing search technique for searching and classifying data in ranges, “n” individual search steps have to be used. This results in excess data storage space requirements, and additional processing requirements when handling classification ranges.
Since the number of possible resulting combinations can be immense, the problem of translating the search results to a “class” is not trivial. Traditional approaches use either a simple array or something like a Cross Product table (as described by V. Srinivasan of Washington University in “Fast and Scalable Layer Four Switching,” Computer Communications Review, October 1998.
Simple arrays, although fast, require memory to hold every possible combination, so are impractical except for the simplest cases. The problem associated with using Cross Product tables to locate the final “class” results is that the most recently accessed results must be cached in the Cross Product table. Basically, the results from each individual search are combined by an expression similar to “finalResult=(((((((result
1
* maxResult
1
)+result
2
) * maxResult
2
)+result
3
) * maxResult
3
)+result
4
) * maxResult
4
)+result
5
”. The final “cross product” value is searched for in the “key” column of the Cross Product table, using a binary search. If the value is found, the correspond “result” column entry is returned as the “class” value. If not found, which is more likely to be the case due to the large range of possible values, a exhaustive search of the available classes must be done. The found “class” and the “cross product” value are both added to the “Cross Product” table. Although a Cross Product table does minimize the amount of memory required, processing requirements become nondeterministic.
Accordingly, there is a need in the technology for classifying incoming data received by a communications device that overcomes the aforementioned problems.
To classify incoming data, searches are typically performed to identify incoming data such as network frames or protocol data units. Traditional search methods either required each unique value to be explicitly stored in a search tree, or required an elaborate tree structure such as the use of a “grid of tries” to provide an efficient search. Since the search has to operate very quickly (typically less than one microsecond on the average), it is imperative to utilize the full capabilities of the processor in the communications device. For such traditional search techniques to operate efficiently, all data that has to be searched is typically stored in the processor's memory space. However, since the processor has only limited amounts of internal memory, the implementation of such traditional search techniques are not practicable.
Moreover, such in using such traditional search techniques, the average and worst case execution times do not remain deterministic beyond a small number of search values. These values are those that are located in the processor's memory space.
Accordingly, there is a need in the technology for an apparatus and method for identifying incoming data received by a communications device that overcomes the aforementioned problems.
SUMMARY OF THE INVENTION
The present invention involves a system and method for classifying information received by a communications device. A first parameter having a first parameter range and a second parameter range, and a second parameter having a third parameter range and a fourth parameter range, are defined. A first class having one of the first parameter and the second parameter ranges, and one of the third and the fourth parameter ranges, are also defined. A second class having another one of the first parameter and the second parameter ranges, and another one of the third and the fourth parameter ranges, is also defined. Information having a first parameter value and a second parameter value is received. The method determines if the first parameter value is within one of the first and second parameter ranges and if the second parameter value is within one of the third and fourth parameter ranges is made. If so, the information is classified into one of the first and second classes based on the first parameter value and the second parameter value, otherwise the information is classified as a default class. An output value representative of the classification is then generated.
REFERENCES:
patent: 5287498 (1994-02-01), Perelman et al.
patent: 5664172 (1997-09-01), Antoshenkov
patent: 5852822 (1998-12-01), Srinivasan et al.
patent: 6092115 (2000-07-01), Choudhury et al.
(IEEE publication) Efficient adaptive media scaling and streaming of layered multimedia in heterogeneous environment by Wei Zhao, Dept. of Computer Science, University of Maryland, College Park, MD. paper in Multimedia Computing and Systems, pp. 377-381, Jun. 1999.*
(IEEE publication) “Packet Classification using Hierarchical intelligent cuttings” by Gupta et al., Computer Systems Lab., Stanford University, Stanford, CA., pp. 34-41, Feb. 2000.*
Subhash Suri et al., Leap Forward Virtual Clock: A New Fair Queuing Scheme with Guaranteed Delays and Throughput Fairness, Washington University, Department of Computer Science, Oct. 27, 1997, 1-
Black Thomas
Irell & Manella LLP
Mizrahi Diane D.
NMS Communications Corporation
LandOfFree
Apparatus and method for classifying information received by... 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 classifying information received by..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for classifying information received by... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2514131