Patent Publication Number: US-6336119-B1

Title: Method and system for applying cluster-based group multicast to content-based publish-subscribe system

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is a division of U.S. application Ser. No. 08/975,280, filed Nov. 20, 1997 which is a division of U.S. application Ser. No. 08/975,303, filed Nov. 20, 1997. 
     This application contains subject matter which is related to the subject matter of the following applications, each of which is assigned to the same assignee as this application. Each of the below listed applications is hereby incorporated herein by reference in its entirety: 
     “Method And System For Matching Consumers To Events,” Astley et al., Ser. No. 08/975,280, filed Nov. 20, 1997, now U.S. Pat. No. 6,216,132; 
     “Routing Messages Within A Network Using The Data Content Of The Message,” Chandra et al., Ser. No. 08/975,303, filed Nov. 20, 1997, now U.S. Pat. No. 6,091,724; and 
     “Method And System For Matching Consumers To Events Employing Content-Based Multicast Routing Using Approximate Groups,” Astley et al., Ser. No. 09/538,471, co-filed herewith, now pending. 
    
    
     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&#39;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 subjects (also called channels 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 an 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 group based multicast such as 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&#39;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 present invention addresses this problem. 
     To summarize, provided herein is of a method for implementing a content-based publish-subscribe system using a group-based multicast. The method includes: mapping possible groups of the publish-subscribe system to a smaller number of multicast groups, wherein the smaller number of multicast groups includes brokers, and the brokers have consumers; and using the smaller number of multicast groups to forward an event to consumers within the content-based publish-subscribe system. 
     In another aspect, the present invention includes 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 of implementing a content-based publish-subscribe system using a group-based multicast. The method includes: mapping possible groups of the publish-subscribe system to a smaller number of multicast groups, wherein the smaller number of multicast groups comprise brokers, the brokers having consumers; and using the smaller number of multicast groups to forward an event to consumers within the content-based publish-subscribe system. 
     In a further aspect, a system for implementing a content-based publish-subscribe system using a group-based multicast is provided. The system includes means for mapping possible groups of the publish-subscribe system to a smaller number of multicast groups, wherein the smaller number of multicast groups comprise brokers, and the brokers have consumers. The system further includes means for using the smaller number of multicast groups to forward an event to consumers within the content-based publish-subscribe system. 
     To restate, the present invention applies clustering to group multicast-based implementations of a content-based publish-subscribe system. Furthermore, as an enhancement, the invention employs thresholding to further reduce the number of groups required. These processes, referred to herein as cluster group multicast (CGM), provide multiple advantages over existing art. For example, under conditions of high match rate (i.e., very few subscribers are interested in any given event) and high regionalism (i.e., subscribers interested in an event are geographically co-located), CGM is superior to flooding (described herein below). In addition, when the cost of fringe-links (i.e., links connecting brokers to the network) is highest, CGM is superior to other group multicast techniques. Advantageously, group assignments in CGM are static and can be created independent of the subscriptions. Furthermore, it is possible to apply CGM to reasonably sized broker networks in Internet protocol (IP) version  4  and version  6 . 
     Additional features and advantages are realized through the techniques of the present invention. Other embodiments and aspects of the invention are described in detail herein and are considered part of the claimed invention. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The above-described objects, advantages and features of the present invention, as well as others, will be more readily understood from the following detailed description of certain preferred embodiments of the invention, when considered in conjunction with the accompanying drawings in which: 
     FIG. 1 depicts a sample environment for deployment of one embodiment of a cluster group multicast (CGM) facility in accordance with the present invention; 
     FIG. 2 is a flowchart of one embodiment of a clustering process for a CGM facility in accordance with the present invention; 
     FIG. 3A is a flowchart of one process embodiment for configuring brokers for cluster group multicast in accordance with the principles of the present invention; 
     FIG. 3B is a flowchart of an alternate embodiment for configuring brokers for cluster group multicast in accordance with the principles of the present invention, wherein a threshold number is employed to signal use of a special cluster broadcast address; 
     FIG. 4A depicts a publisher matching data structure for use in event matching using cluster group multicast in accordance with the present invention; 
     FIG. 4B is a subscriber matching data structure for use in event matching using cluster group multicast in accordance with the present invention; 
     FIG. 5 is a flowchart of one embodiment of a subscription propagation process in accordance with the principles of the present invention; 
     FIG. 6A is a flowchart of one embodiment for matching an event to a subscribing client using cluster group matching (CGM) in accordance with the principles of the present invention; and 
     FIG. 6B is a flowchart of one embodiment for matching an event to a subscribing client using threshold cluster group matching (TCGM) in accordance with the principles of the present invention. 
    
    
     BEST MODE FOR CARRYING OUT THE INVENTION 
     As briefly noted above, a content-based publish-subscribe system disseminates information in the form of “events” from those producing information (publishers), to interested parties (subscribers). The advantage of a content-based publish-subscribe system is that subscribers receive only those events for which they have expressed an interest. One way of expressing information is by specifying a predicate over an event schema. 
     As shown in FIG. 1, a scalable publish-subscribe system, generally denoted  100 , is commonly realized on networks of “broker” nodes, connected by “router” nodes  110 . Subscribing clients connect to subscribing brokers  120  and register their interest in particular types of events. Likewise, publishers connect to publishing broker nodes  130 , and publish events. The brokers are responsible for tracking subscriptions and for routing events from publishers to the appropriate set of subscribers. 
     Implementations of publish-subscribe systems on today&#39;s network infrastructure are typically based on either matching near the subscriber or matching near the publisher. 
     Matching near the subscriber is called “flooding”. In the flooding approach, every event is broadcast to all brokers, which in turn match the event and deliver it to their subscribers. This approach is inefficient since brokers that may not eventually need the message still receive the event and thus consume valuable network bandwidth. The situation is particularly bad when subscriptions are regional in nature. 
     When an event is matched near the publisher, it can be routed to the right set of subscribing brokers by using (1) point-to-point broker connections, (2) destination lists, or (3) group multicast between brokers. Point-to-point routing is inefficient because it fails to take advantage of the common paths between brokers. Routing via destination lists is not scalable since message headers, and thus the message itself can grow quickly. Moreover, routing via destination lists is not directly supported by routers in current day network infrastructure. 
     That leaves the approach of routing via group multicast, to which the present invention is directed. Straightforward implementations using group multicast-based routing, such as an internet protocol (IP) multicast, produce systems that are not scalable in the number of groups required. For example, a system with N endpoints requires 2 N  groups. Using the currently deployed version of IP, this means that systems may not have more than 24 endpoints, since the number of groups supported in the best case is 2 24 . 
     Thus, this invention is concerned with the problem of efficiently matching an event against a set of subscriptions and routing it from its publisher to subscribers within a network of publish-subscribe brokers. Furthermore, this invention is concerned with solving the problem within the context of existing internet infrastructure and under expected distributions of subscriptions. One such expected subscriber distribution is called a “regional distribution” in which subscribers with similar interest are located in the same geographical region of the network, and furthermore, publishers that produce events of interest may lay within the same region as well. 
     Clustering is an existing technique for reducing the number of groups required for message distribution. This invention applies the clustering technique to group multicast based implementations of a content-based publish-subscribe system. Furthermore, this invention applies the technique of thresholding (described later) to further reduce the number of groups required. 
     The CGM process described herein is based on the use of clusters: mutually exclusive subsets of brokers where each subset has its own set of multicast groups. We observe that if we divide N endpoints into 2 clusters, we reduce the number of groups in each cluster to 2 N/2  groups, and the total number of groups to two times that. The cost of this approach, however, is that it may be necessary to multicast an event twice: once to a group in each cluster. In general, if we divide N into C clusters, the total number of groups needed is given by g=C(2 N/C ). So, for example, if we have 2 13  multicast groups available, we can support  80  broker endpoints by dividing them into 8 clusters of 10 brokers each. Since the groups within a cluster enumerate all possible combinations of brokers, each broker must join half these groups (those that include the broker) at system configuration time. 
     Each broker contains an instance of the subscription matching engine with entries for all client subscriptions, and sorts the resulting list of brokers by cluster. It then looks up the group in each cluster that contains, for example, exactly those brokers destined to receive the event. The publisher&#39;s broker then performs up to C multicasts, where C is the number of clusters. Some clusters may have no matching brokers and are therefore skipped. 
     The choice of cluster assignment has a significant impact on performance. For example, brokers that match a single subscription, but that are spread over multiple clusters will require multiple multicasts. One approach to clustering is to build clusters by grouping brokers with similar subscription sets. Another approach is to use geographic (or network) location data to group brokers into clusters. This latter approach performs well in the case when subscribers that are geographically co-located also have similar subscriptions, i.e., there is “regionalism” of subscriptions. 
     The number of groups required by the CGM process may be reduced further by reducing the precision of the algorithm. One approach to reducing the precision is to flood a cluster when more than a threshold number of brokers within that cluster need to receive an event. That is, the process behaves like CGM unless the number of destinations in a cluster exceeds a threshold, at which point the event is multicast to the entire cluster. This algorithm is referred to herein as threshold CGM (or TCGM). 
     For each cluster, we pick a threshold T, with T&lt;K, where K is the size of the cluster. If an event matches more than T endpoints, the event is sent to all brokers in the cluster. Otherwise, the event is sent only to the brokers subscribed to the event (as in CGM). This process requires multicast groups for all subsets of brokers in a cluster of size T or smaller, plus one additional multicast group for an “all brokers” multicast in the cluster. The group requirement for TCGM can be many orders of magnitude smaller than in the case of CGM. 
     As noted, in accordance with the present invention a broker network, for example, network  100  of FIG. 1, needs to be divided into a number of clusters, C. FIG. 2 depicts one embodiment of a clustering process for achieving this. In this process, the variable Nc is defined as the total number of brokers divided by the desired number of clusters  200 . Once Nc is defined, the process begins by choosing a random unassigned broker in the network  210 . An unassigned broker that is nearest to broker B in terms of latency is selected for inclusion in the current cluster  220 . This process continues until the number of brokers in the current cluster equals Nc  230 . As the process proceeds, each visited broker is marked as assigned and the process continues until all C clusters are defined and all brokers are assigned to a cluster  240 . Note that the process of FIG. 2 for creating clusters is provided by way of example only, i.e., several alternative processes are also possible. 
     Before the publish-subscribe system can begin accepting subscriptions and published events, the system must be configured. Note that this configuration occurs once and is static, i.e., unless the network itself changes. For the clustered group multicast (CGM) process presented herein, this configuration can be performed using the process of FIG.  3 A. Initially, each broker  300  is assumed to be associated with a cluster Ci, and assigned a broker number Bi within the cluster Ci. The cluster number for the broker is expressed in binary, while Bi is the broker number for the broker within Ci  310 . Multicast addresses are normally represented as binary strings. The group multicast addresses that a broker must join have the cluster number Ci (in binary) as their high order bits and a “1” in the position corresponding to the broker number Bi  320 . Essentially, this process determines each individual subset or group of the total number of brokers in the cluster, represents each broker as a single bit, and makes each broker join all of the groups which have addresses with “1” in the position of that broker number within the cluster. 
     As an alternate embodiment, FIG. 3B depicts a process for configuring brokers when a threshold cluster group multicast (TCGM) is to be employed. Again, each broker  350  is assumed to be associated with a cluster Ci, and is assigned a broker number Bi within the cluster Ci  360 . For this process, the multicast addresses to join are determined by selecting all addresses that have a “1” in the position Bi, the broker number, and further, by selecting only those addresses that have no more 1s than a threshold number. Each broker in a cluster also joins a special group address, referred to herein as the “all brokers” or “cluster broadcast” address  370 . 
     The subscription propagation and event matching and routing processes in accordance with this invention are written based on the data structures that are maintained by each broker. Exemplary embodiments of these data structures are depicted in FIGS. 4A &amp; 4B, wherein a publisher matching tree and a subscriber matching tree are shown, respectively. Each publishing broker maintains a matching tree of all subscriptions in which each leaf is annotated with a bit vector as shown in FIG.  4 A. The bit vector annotation has C rows and a number of columns K equal to the number of brokers in each cluster. The “*” shown in these figures comprises a “don&#39;t care” meaning that the path is traversed irrespective of the attribute value. Don&#39;t cares are described in greater detail in the initially incorporated United States Patent application entitled “Method and System for Matching Consumers to Events.” The trees are traversed by comparing attribute values with values of the published event. As shown in FIG. 4B, the subscribing brokers contain a matching data structure used to match events to those subscriptions that are applicable to the clients of that broker. As shown, leaf nodes in this tree are annotated with identifiers of all the clients that match a particular subscription. 
     FIG. 5 depicts one embodiment for propagating new subscriptions throughout the system. Once a new subscription is made  500 , the subscription itself is broadcast by the receiving broker, along with a cluster id of the subscribing broker and the broker id of the subscribing broker within the cluster  510 . At each publishing broker, the broker finds the subscription Si in the publisher matching data structure (FIG.  4 A), and in the Si&#39;s annotation, the publishing broker turns on the corresponding bit in the cluster id row, broker id column  520 . 
     FIG. 6A depicts one embodiment of cluster group multicast (CGM) in accordance with the principles of the present invention. Once an event is published  600 , then at the publishing broker, a 2D bit-vector “mask” of all zeros is created, where the number of rows is the same as the number of clusters, and the number of columns equals the number of brokers within a cluster  605 . The publisher matching tree (FIG. 4A) is then traversed  610 , and for each leaf node visited, an OR operation is performed between the mask and the annotation of the leaf node  615 . At the end of this traversal, the event is multicast once to each cluster containing at least one interested subscriber  620 . The multicast addresses are determined by appending each nonzero row in the result mask to the corresponding cluster id (in binary). The group multicast infrastructure that exists within the routers will then deliver the event to the subscribing brokers in the clusters. At each subscribing broker, the subscriber matching tree (FIG. 4B) is traversed and the event is sent to each subscribing client  625 . 
     FIG. 6B depicts an alternate cluster group matching process, herein referred to as the threshold cluster group multicast (TCGM) process which employs the above-discussed thresholding technique. An event is again published  650  and the publisher matching tree is traversed  655  as described above in connection with the CGM process of FIG.  6 A. At the end of this traversal, the event is multicast once to each cluster, where the multicast addresses are determined as follows  660 : for each cluster id Ci, if the corresponding row in the result mask has a nonzero number of “1s”, but no more than a “threshold”, the multicast address is Ci appended with the row&#39;s value  665 . For cluster id Ci, if the corresponding row in the result mask has more than the threshold of 1s, the multicast address is Ci&#39;s special “cluster broadcast” address  670 . At the subscribing broker, the subscriber matching tree is again traversed and the event is sent to each subscribing client  675 . If there are no subscribing clients, then the event is discarded. 
     Note that the present invention can be included, for example, in an article of manufacture (e.g., one or more computer program products) having, for instance, computer usable media. This media has embodied therein, for instance, computer readable program code means for providing and facilitating the capabilities of the present invention. The articles of manufacture can be included as part of the computer system or sold separately. 
     Additionally, at least one program storage device readable by machine, tangibly embodying at least one program of instructions executable by the machine, to perform the capabilities of the present invention, can be provided. 
     The flow diagrams depicted herein are provided by way of example. There may be variations to these diagrams or the steps (or operations) described herein without departing from the spirit of the invention. For instance, in certain cases, the steps may be performed in differing order, or steps may be added, deleted or modified. All of these variations are considered to comprise part of the present invention as recited in the appended claims. 
     While the invention has been described in detail herein in accordance with certain preferred embodiments thereof, many modifications and changes therein may be effected by those skilled in the art. Accordingly, it is intended by the appended claims to cover all such modifications and changes as fall within the true spirit and scope of the invention.