Methods and system for data packet filtering using tree-like hierarchy
First Claim
1. In a data packet transmission system, a method of filtering an incoming data packet comprising the steps of:
- creating a decision graph having a tree-like hierarchy for a set of filters such that the filters are subdivided and grouped along edges and stages of the tree-like hierarchy according to common filter values;
receiving a data packet at a point of ingress to the data packet transmission system;
comparing filters along edges of the tree-like hierarchy to portions of the data packet to determine where there are matches; and
if matches are made along an entire edge of the tree-like hierarchy, filtering the data packet stream according to number of condition values compared.
0 Assignments
0 Petitions
Accused Products
Abstract
A method of filtering an incoming data packet stream in a data packet transmission system. The method comprises a step of defining a tree-like hierarchy for a plurality of filter conditions such that the filter conditions are divided into groups of filters, each of the groups associated with one or more fields having pre-determined condition values. The groups are arranged in long edges of the tree-like hierarchy. Next, a data packet stream is received at a point of ingress to the data packet transmission system and condition values along the edges of the tree-like hierarchy are compared to specified portions of the data packet stream to determine where there are matches. If matches are made along an entire edge of the tree-like hierarchy, the data packet stream is filtered according to the number of condition values compared as opposed to the number of filters.
106 Citations
28 Claims
-
1. In a data packet transmission system, a method of filtering an incoming data packet comprising the steps of:
-
creating a decision graph having a tree-like hierarchy for a set of filters such that the filters are subdivided and grouped along edges and stages of the tree-like hierarchy according to common filter values;
receiving a data packet at a point of ingress to the data packet transmission system;
comparing filters along edges of the tree-like hierarchy to portions of the data packet to determine where there are matches; and
if matches are made along an entire edge of the tree-like hierarchy, filtering the data packet stream according to number of condition values compared. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. In connection with a router that receives incoming packets from a data network, a method of filtering the incoming packets at the interface of the router to provide differentiated services, the method comprising the steps of:
-
constructing a decision tree structure that stores a set of filters in a tree-like hierarchy, the tree-like hierarchy including edges and stages, the set of filters subdivided according to their values along the edges and stages of the tree-like hierarchy;
the interface of the router receiving at least one incoming data packet; and
comparing segments of the incoming data packet to values of the filters stored in the tree-like hierarchy such that the segments are compared along stages and not every edge of the tree-like hierarchy to allow the incoming data packet to be differentiated according to matches between the segments compared and specific filter values. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22)
-
-
23. A router for use in a data network and for allowing the implementation of differentiated services by filtering incoming data packets, the router comprising:
-
an interface to the data network;
a packet processing unit coupled to said interface and adapted for receiving incoming data packets via the interface from the data network;
memory means operably coupled to said packet processing unit and adapted for storing software instructions that cause said packet processing unit to filter incoming data packets; and
a data structure for storing a set of filters in a tree-like hierarchy, the tree-like hierarchy including edges organized into stages, the set of filters subdivided according to their values along the edges and stages of the tree-like hierarchy;
wherein said software instructions are further adapted to cause said packet processing unit to compare segments of incoming data packets to values of the filters stored in the tree-like hierarchy such that the segments are compared along stages and not every edge of the tree-like hierarchy to allow the incoming data packet to be differentiated according to matches between the segments compared and specific filter values. - View Dependent Claims (24, 25, 26, 27, 28)
-
Specification