Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-03-30
2004-04-27
Amsbury, Wayne (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C725S034000, C725S035000
Reexamination Certificate
active
06728715
ABSTRACT:
TECHNICAL FIELD
This invention relates, in general, to event computing systems and, more particularly, to a content-based multicast routing technique which delivers events to consumers of an event computing system interested in a particular set of events.
BACKGROUND ART
A common practice for integrating autonomous components within a computing system has been to utilize events. Events are, for example, data generated by a provider and delivered through a communication medium, such as a computer network, hard disk, or random access memory, to a set of interested consumers. The providers and consumers need not know one another's identity, since delivery is provided through intermediary software. This independence between provider and consumer is known as decoupling.
One example of an event computing system is a database event system. Modern database systems include support for event triggers. Event triggers associate a filter, which is a predicate that selects a subset of events and excludes the rest, with an action to take in response to events on the database. An event on a database is any change to the state of the database.
In database event systems, gating tests have been used to determine which consumers of a system are interested in a particular event. That is, gating tests have been used to match filters in event triggers to events. As described in “A Predicate Matching Algorithm for Database Rule Systems,” by Hanson et al., Proceedings of SIGMOD (1991), pp. 271-280, gating tests identify a single predicate for each filter as primary, and tests are organized in a data structure based on this primary predicate. Additionally, the data needs to be organized based on the primary predicate.
Another example of an event computing system is a distributed event system, also known as a publish/subscribe system. A publish/subscribe system is a mechanism where subscribers express interest in future information by some selection criterion, publishers provide information, and the mechanism delivers the information to all interested subscribers. Current publish/subscribe systems organize information around groups (also called channels, subjects or streams). Providers or publishers publish events to groups and consumers or subscribers subscribe to all data from a particular group.
One example of a publish/subscribe system is described in detail in U.S. Pat. No. 5,557,798, issued to Skeen et al. on Sep. 17, 1996, and entitled “Apparatus And Method For Providing Decoupling Of Data Exchange Details For Providing High Performance Communication Between Software Processes”, which is hereby incorporated herein by reference in its entirety. In U.S. Pat. No. 5,557,798, the publisher of an event annotes each message with a group identifier called a subject and a subscriber subscribes to a particular subject. Thus, if a subscriber is interested in just a portion of the events having a given subject, it would have to receive the entire subject and then discard the unwanted information.
Based on the foregoing, a need exists for a matching capability that does not require the partitioning of data into subjects. A further need exists for a matching capability that enables a consumer to use any filtering criterion expressible with the available predicates. Additionally, a need exists for a mechanism that allows a consumer to receive only the information that it desires, such that the filtering is done independent of the consumer.
SUMMARY OF THE INVENTION
One approach to addressing the above-noted needs is described in the above-incorporated, co-pending U.S. patent application Ser. No. 08/975,280, entitled “Method and System for Matching Consumers to Events.” In this approach, referred to herein as a content-based event computing system, the matching facility includes a search data structure (e.g., a search tree or search graph), which is used to determine the consumers interest in a particular event. Content-based subscription is the ability of subscribers to specify interest in events based on operations limited only by the structure of the events and the operation supported by the pattern language.
Applicants have identified a problem arising with content-based subscription which arises when using internet protocol (IP) multicasting of an event. In a practical content-based subscription system, there will typically be too many groups of clients or consumers to use a multicast facility.
As one example, the environment of this invention may include content-based, publish/subscribe systems deployed over IP networks such as the Internet. Clients are either publishers or subscribers, and are attached to machines referred to herein as brokers. The publisher's broker receives a published message (also referred to herein as an “event”) and delivers it to subscriber brokers at least one of whose attached clients has a subscription matched by the message. These subscriber brokers then forward the message to the at least one attached client. Content-based systems are more flexible and provide more selectivity than subject-based systems. However, the multicast problem for content-based message delivery middleware is more complex than for subject-based delivery once the number of destinations for messages becomes large. It may no longer be straightforward or efficient to use IP multicast groups to distribute messages of a content-based system over a network because the number of such groups required grows rapidly with the number of subscriptions. This number eventually becomes so large that either the supported range of multicast addresses is exceeded or the overhead of setting up and listening to such a large number of multicast addresses becomes excessive.
The goal of the present invention is to replace a potentially large set of IP multicast addresses with a much smaller set, which will be a conservative approximation. That is, every broker which might require a message will receive it, but certain brokers may possibly receive messages they do not actually need. These extra messages cause wasted bandwidth in the network and wasted processing time in the receiving broker, which can be quantified by a penalty function. Thus, the present invention collapses a large number of groups to a smaller number of groups, while approximately minimizing the expected penalty. The invention disclosed herein uses dynamic information about the existing set of subscriptions and the expected probabilities of different events in order to perform this collapse.
To summarize, the shortcomings of the prior art are overcome and additional advantages are provided through the provision of a method for distributing events to consumers in a content-based publish/subscribe system. The method includes: deriving a set of g approximate multicast groups from a larger set of G possible multicast groups in the publish-subscribe system, the deriving including exploiting knowledge of subscription predicates of at least some consumers of the publish-subscribe system; and using the set of g approximate multicast groups to forward an event to at least one consumer withing the publish-subscribe system.
In another aspect, the present invention provides at least one program storage device readable by a machine, tangibly embodying at least one program of instructions executable by the machine to perform a method for distributing events to consumers in a content-based publish-subscribe system, wherein the consumers each have at least one subscription. The method includes: deriving a set of g approximate multicast groups from a larger set of G possible multicast groups in the publish-subscribe system. The deriving including exploiting knowledge of subscription predicates of at least some consumers of the publish-subscribe system; and using the set of g approximate multicast groups to forward an event to at least one consumer within the publish-subscribe system.
In a further aspect, an article of manufacture is provided herein which includes at least one computer usable medium having computer readable program code means embodied therein for causi
Astley Mark
Strom Robert E.
Sturman Daniel C.
Amsbury Wayne
Cameron Esq. Douglas W.
Nguyen Cam-Linh T.
LandOfFree
Method and system for matching consumers to events employing... 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 system for matching consumers to events employing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for matching consumers to events employing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3254041