System for segmenting data packets to form binary decision trees which determine filter masks combined to filter the packets for forwarding

• US 5,463,777 A
• Filed: 02/28/1995
• Issued: 10/31/1995
• Est. Priority Date: 07/02/1992
• Status: Expired due to Term

• Current Assignee: Rockstar Consortium US LP (Rockstar Consortium Inc.)
• Original Assignee: Wellfleet Communications Inc (Nortel Networks Corporation)
• Inventors: Bialkowski, Jan, Krawczyk, John
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/396,374
• Time in Patent Office: 245 Days
• Field of Search: 395/200, 395/600, 370/85.8
• US Class Current: 1/1
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A packet processing method and apparatus efficiently process a binary data packet based upon information contained in the header portion of the packet. The method and apparatus employ a binary tree search method for determining ranges of key elements of the packet and associating with each of the ranges a user supplied data and filter mask. The binary search process employs a unique binary tree storage structure which both conserves storage memory and enables efficient processing to reach a final node of the binary tree decision table. Nodes can be added or deleted from the table by the user as the data packet processing needs change.

Claims

1. A method for processing a data communications binary data packet for forwarding said packet to a next destination within a data communications network, said packet including a data portion and an information containing portion having keys, each key having a data value, comprising the steps of

segmenting said information containing portion into a plurality of information subset segments, each segment associated with at least one of said keys,

creating and storing a binary tree decision table associated with each of said segments, each of said binary tree decision tables having a plurality of non-final nodes, and a plurality of final nodes, each of the tables representing a binary decision tree structure,

processing each of said information subset segments using the associated binary tree decision tables to determine a filter mask for each segment,

combining the results of each filter mask to provide a final filter mask for determining data processing to be used for said packet for filtering and forwarding said packet to a next destination on the basis of the data values of the keys being within preselected ranges of data values, and

processing said packet in accordance with the processing results using said final filter mask.

2. The packet processing method of claim 1 wherein said table creating and storing step comprises the steps of

dividing a table storage into a numbered sequence of subarrays for each table,

ordering each of the binary decision tree structures in a dependency order of numbered nodes, and

storing a left and a right node child of a node "n", stored at subarray "n", at subarrays "2n" and "2n+1".

3. The packet processing method of claim 2 further comprising the step of

balancing each of the binary tree structures prior to said ordering step.

4. The packet processing method of claim 3 further comprising the steps of

adding nodes to an existing binary tree structure by modifying the associated binary tree decision table, and

deleting nodes from an existing binary tree structure by modifying the associated binary tree decision table.

5. The packet processing method of claim 2 further comprising the steps of

assigning a weight to each node equal to the sum of the weights of each of its child nodes plus one, and

balancing each of the binary tree structures whenever the weights associated with two child nodes of a common node differ by more than 1.

6. The packet processing method of claim 2 wherein each said subarray is associated with each of said non-final and final nodes, each subarray associated with a non-final node storing a bit offset value and a predetermined node threshold value, and each final subarray of said tree nodes, associated with a final node, is designated by passing through a sequence of non-final nodes.

7. The packet processing method of claim 6 wherein each final node has a predetermined node threshold value.

8. The packet processing method of claim 7 wherein said predetermined node threshold value is zero.

9. The packet processing method of claim 2 wherein each tree structure has at least one final subarray and each said final subarray contains said information data portion and said filter mask containing portion.

10. The packet processing method of claim 9 wherein said plurality of information subset segments are processed serially to determine a filter mask for each segment, and

said final filter mask is AND'"'"'ed with an initial filter mask.

11. The packet processing method of claim 1 wherein said segmenting step further comprises the step of

dividing each segment having a bit length greater than an operating word length into a plurality of subsegments, and

processing said subsegments through said binary tree structure.

12. The packet processing method of claim 1 wherein said first processing step comprises the steps of

deciding, for each non-final node, whether a data value of a selected key of said information containing portion is within a range of data values defined by a bit offset value referenced from a predetermined node associated threshold value associated with each non-final node, and

proceeding to one of a lower order right child node and a lower order left child node depending upon the relative values of said data value and said range of data values.

13. An apparatus for processing a data communications binary data packet for forwarding said packet to a next destination within a data communications network, said packet including an information containing portion having keys, each key having a data value, comprising:

means for segmenting said information containing portion into a plurality of information subset segments, each segment associated with at least one of said keys,

means for creating and storing a binary tree decision table associated with each of said segments, each of said binary tree decision tables having a plurality of non-final nodes, and a plurality of final nodes, each of the tables representing a binary decision tree structure,

means for processing each of said information subset segments using the associated binary tree decision tables to determine a filter mask for each segment,

means for combining the results of each filter mask to provide a final filter mask for determining the data processing to be used for said packet for filtering and forwarding said packet onto a next destination on the basis of the data values of the keys being within preselected ranges of data values, and

means for processing said packet in accordance with the processing results using said final filter mask.

14. The packet processing apparatus of claim 13 wherein said table creating and storing means comprises

means for dividing a table storage into a numbered sequence of subarrays for each table,

means for ordering each of the binary tree structures in a dependency order of numbered nodes, and

means for storing a left and a right node child of a node "n", stored at subarray "n", at subarrays "2n" and "2n+1".

15. The packet processing apparatus of claim 14 further comprising

means for balancing each of the binary tree structures prior to said ordering.

16. The packet processing apparatus of claim 15 further comprising

means for adding nodes to an existing binary tree structure by modifying the associated binary tree decision table, and

means for deleting nodes from an existing binary tree structure by modifying the associated binary tree decision table.

17. The packet processing apparatus of claim 14 further comprising

means for assigning a weight to each node equal to the sum of the weights of each of its child nodes plus one, and

means for balancing each of the binary tree structures whenever the weights associated with two child nodes of a parent node differ by more than 1.

18. The packet processing method of claim 14 wherein each said subarray is associated with each of said non-final and final nodes, each subarray associated with a non-final node storing a bit offset value and a predetermined node threshold value, and each final subarray of said tree nodes, associated with a final node, is designated by passing through a sequence of non-final nodes.

19. The packet processing apparatus of claim 18 wherein each said final node stores a predetermined node threshold value.

20. The packet processing apparatus of claim 19 wherein said predetermined node threshold value is zero.

21. The packet processing apparatus of claim 14 wherein each tree structure has at least one final subarray and each said final subarray contains said information data portion and said filter mask containing portion.

22. The packet processing apparatus of claim 21 wherein said information subset segments are processed serially to determine a filter mask for each segment, and

said means for combining the results of each filter mask comprises means for AND'"'"'ing the results of each filter mask with an initial filter mask.

23. The packet processing apparatus of claim 22 wherein said segmenting means further comprises

means for dividing each segment having a bit length greater than an operating word length into a plurality of subsegments, and

means for processing said subsegments through said binary tree structure.

24. The packet processing apparatus of claim 13 wherein said first processing means comprises

means for deciding, for each non-final node, whether a data value of a selected key of said information containing portion is within a range of data values defined by a bit offset value referenced from a predetermined node associated threshold value associated with each non-final node, and

means for proceeding to one of a lower order right child node and a lower order left child node depending upon the relative values of said data value and said range of data values.