Systems and methods for routing messages sent between computer systems

• US 6,781,961 B1
• Filed: 11/17/2000
• Issued: 08/24/2004
• Est. Priority Date: 11/17/2000
• Status: Expired due to Term

• Current Assignee: Panasonic Electric Works Company Limited (Panasonic Holdings Corporation)
• Original Assignee: emWare, Inc. (Panasonic Holdings Corporation)
• Inventors: Gunsay, Metin
• Primary Examiner(s): NGUYEN, BRIAN D
• Application Number:
  US09/715,408
• Time in Patent Office: 1,376 Days
• Field of Search: 370/255, 370/256, 370/254, 370/351, 370/352, 370/389, 370/392, 370/400, 370/401, 370/408, 370/475, 370/488, 370/230, 370/252, 709/223, 709/224, 709/225, 709/220, 709/228, 709/232, 709/238, 709/245, 709/252
• US Class Current: 370/255
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00

Abstract

A method for routing electronic messages for communications between computer systems may include the steps of examining a plurality of interest data sets, each having a interest value that indicates specific data that is of interest, creating a filter tree from the plurality of interest data sets where each filter of the filter tree accurately describes child filters in such a way that messages may be properly passed to any terminal filters of the tree which have an interest value that describes the messages, examining the messages, comparing the messages to the root filter of the filter tree to determine if the messages should pass the root filter, and, as long as the messages passes a current filter, comparing the messages with the child filters of the current filter in order to effectively pass the messages to any terminal filters of the tree having an interest value that describes the messages.

Claims

1. A method for routing messages comprising:

examining a plurality of interest data sets, wherein each interest data set comprises a value, and wherein each value indicates data that is of interest;

creating a filter tree from the plurality of interest data sets wherein each node of the filter tree accurately describes child nodes such that the messages are properly passed to any terminal nodes of the tree having a value that describes the messages;

examining the messages; and

comparing the messages to the root node of the filter tree to determine if the messages should pass the root node, and, as long as a message passes a current node, then comparing the message with the child nodes of the current node in order to effectively pass the message to any terminal nodes of the tree having a value that describes the message.

2. The method as defined in claim 1 wherein the messages comprise electronic messages sent by computer systems in electronic communication with a computer implementing the method for filtering.

3. The method as defined in claim 1 wherein the messages that are passed to a terminal node having a value descriptive of the messages are sent electronically to one or more receiving computer systems.

4. The method as defined in claim 1 wherein the interest data sets further comprise a mask.

5. In a system for computers, where electronic messages are sent by sending computers and are received by receiving computers, a method for routing the electronic messages comprising the steps of:

acquiring a plurality of interest data sets, wherein each interest data set comprises a value and a mask;

creating a filter tree from the plurality of interest data sets wherein each parent node of the filter tree accurately describes child nodes such that an input electronic message is properly passed to any terminal nodes of the tree having a value that describes the input electronic message;

receiving the input electronic message sent by a sending computer;

comparing the input electronic message to traversed nodes of the filter tree in succession in order to effectively pass the input electronic message to any terminal nodes of the tree having a value that identifies the electronic message; and

sending the input electronic message to a receiving computer if the input electronic message passed through the filter tree without being blocked.

6. The method of claim 5 wherein the mask specifies message content that is relevant, and where the value indicates a specified value that is to be present in the specified content such that the input electronic message is sent to one or more receiving computers.

7. The method of claim 6 wherein the creating step further comprises:

dividing the interest data sets into groups of two or more nodes;

using the mask and the value of the nodes in each group to create a parent mask and a parent value range for a parent node in the adjacent level of the tree such that the parent mask and the parent value range of the created patent node accurately describe the mask and the value of each node in the group used to create the parent node; and

repeating the dividing step and the using step until only one parent node exists in one level of the tree.

8. The method of claim 7 wherein the mask and interest value are in binary form.

9. The method of claim 8 wherein the using step further comprises the steps of:

logically ANDing the masks of the nodes in each group to produce the parent mask;

logically ORing the values of the nodes in each group to produce an upper-bound value for the parent value range; and

logically ANDing the interest values of the nodes in each group to produce a lower-bound value for the parent value range.

10. The method of claim 8 wherein the using step further comprises the steps of:

logically ORing the masks of the nodes in each group to produce the parent mask;

selecting the highest value of the values of each group to be an upper-bound value for the parent value range; and

selecting the lowest value of the values of each group to be a lower-bound value for the parent value range.

11. The method of claim 8 wherein the comparing step further comprises the steps of:

logically ANDing the electronic message with the mask of the node to produce a masked result;

determining whether the masked result exists within the parent value range of the node;

allowing the electronic message to pass the node if the masked result exists within the parent value range; and

repeating the logically ANDing, the determining and the allowing steps until the electronic message can no longer be passed by a parent node or the electronic message is passed by one or more terminal filter nodes.

12. A system for filtering electronic messages, wherein the electronic messages are sent by sending computers in electronic communication with the system, the system comprising:

a terminal node level, residing at level N, wherein each terminal node comprises a mask and value, the mask specifying the relevant portions of the messages, and the value indicating a particular data value that is of interest;

a root node level, residing at level one, wherein the root node comprises a mask and a range, the mask specifying the relevant portions of the messages, and the range indicating a range of values for desirable messages; and

one or more intermediate levels, residing at levels two to (N−

1), wherein each intermediate level comprises one or more nodes, and wherein each intermediate node comprises a mask and a range; and

wherein the levels are interconnected in a tree structure such that messages may be propagated down one or more branches of the tree structure to arrive at any terminal nodes of the tree having a value that describes the messages.

13. The system of claim 12 wherein a parent node is created by a method comprised of the steps of:

logically ANDing the masks of child nodes to produce a parent mask;

logically ORing the values of the child nodes to produce an upper-bound value for a parent range; and

logically ANDing the values of the child nodes to produce a lower-bound value for the parent range.

14. The system of claim 13 wherein an input electronic message is filtered by the system through a method comprises of the steps of, beginning with the root node:

logically ANDing the electronic message with the mask of the node to produce a masked result;

determining whether the masked result exists within the parent range of the node;

allowing the electronic message to pass the node if the masked result exists within the parent range; and

repeating the logically ANDing, the determining and the allowing steps until the electronic message can no longer be passed by a parent node or the electronic message is passed by one or more terminal filter nodes.

15. The system of claim 12 wherein a parent node is created by a method comprised of the steps of:

logically ORing the masks of child nodes to produce a parent mask;

selecting the highest value of the values of the child nodes to be an upper-bound value for a parent range; and

selecting the lowest value of the values of the child nodes to be a lower-bound value for the parent range.

16. The system of claim 15 wherein an input electronic message is filtered by the system through a method comprises of the steps of, beginning with the root node:

logically ANDing the electronic message with the mask of the node to produce a masked result;

determining whether the masked result exists within the parent range of the node;

allowing the electronic message to pass the node if the masked result exists within the parent range; and

repeating the logically ANDing, the determining and the allowing steps until the electronic message can no longer be passed by a parent node or the electronic message is passed by one or more terminal filter nodes.