Reduction and optimization of information processing systems

Details Reduction and optimization of information processing systems Reduction and optimization of information processing systems

1999-05-28

2004-01-20

Thompson, Marc D. (Department: 2142)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C709S217000, C709S203000, C708S400000, C708S005000

Reexamination Certificate

active

06681220

ABSTRACT:

TECHNICAL FILED
The present invention relates to information processing systems, and in particular relates to techniques for optimizing information processing paths within these systems.
BACKGROUND OF THE INVENTION
Messaging middleware, by supporting general messaging and message transformation between network nodes, facilitates the integration of distributed components of a processing application. Middleware collects messages from information producers (“publishers”), filters and transforms the messages as necessary, and disseminates applicable messages to interested information consumers (“subscribers”). This type of system is known as a publish/subscribe system. Publish/subscribe middleware systems are therefore important to the inter-connection of heterogeneous and distributed components of large information networks, which rely on message communication, in domains such as finance, process automation, and transportation.
A exemplary publish/subscribe system may be represented by an Information Flow Graph (“IFG”) as a set of information publishing nodes which emit event messages, a set of information subscribing nodes which read event messages, a set of intermediate nodes where messages coming from streams along different input arcs are interleaved into an outgoing stream of messages, i.e., a replica of the stream is sent along each outgoing arc. The nodes may be connected by arcs of at least two kinds:
Selection arcs, which “filter” messages flowing from one node to another by only passing along messages which satisfy a predicate; and
Transformation arcs, which “transform” messages flowing from one node to another by adding, dropping, and/or recomputing the fields of each message.
A publish/subscribe system may include a large network or “graph” of nodes and arcs, with many possible paths from each publishing node to each subscribing node, each path comprised of possibly many selection and transformation arcs, resulting in a particular sequence of operations between each publisher/subscriber node pair.
Using subject-based publish/subscribe systems as a starting point, recent advances include:
1. Content-based publish/subscribe. Rather than treating events as un-interpreted data with a single “subject” field, schemas are associated with event streams, and express subscriptions as predicates over all fields in the event.
2. Stateless event transformnations. To support scenarios where events from multiple publishers are similar but not identical, events may be subject to transform operations. These operations are stateless in the sense that they do not depend upon prior events.
3. Event stream interpretation. To support subscribers who are interested not only in published events but also in events such as summaries, trends, and alarms, derived from a sequence of related events, “stateful” operations are supported (operations whose results depend on the event history). State can also be used to express the “meaning” of an event stream, and by implication, the equivalence of two event streams.
Designers of such systems are often faced with the challenges of reducing abstract descriptions (e.g., Information Flow Graphs) of select and transform sequences between nodes into a system design which utilizes resources efficiently, and redesigning existing systems with the same goals. One particular problem involves the consolidation of transform operations at the periphery of the network, and select operations at the interior, so that existing techniques for efficient content-based subscription can be used as the basis for an optimized implementation of middleware.
SUMMARY OF INVENTION
The present invention provides techniques (methods, systems and computer program products) for reducing and optimizing publish/subscribe systems, wherein any operation sequence from one node to another may be replaced by an equivalent sequence comprised of a single select followed by a single transform operation. The optimization rules disclosed herein can be automatically applied during system design or redesign, similar to the way computer programs can be automatically optimized by state-of-art compilers.
Using a set of design rules disclosed herein, any system flow diagram (e.g., Information Flow Graph) may be converted or “rewritten” so that select operations are combined and “pushed” toward the sources (publishers), and transform operations are combined and “pushed” toward the subscribers. (Because transforms may destroy information, they cannot, in general be “pushed” ahead of selects.)
This rewriting can be done by an automated system having as its input a sequence of selects and transforms representing the flow and processing of messages. The system produces an optimized model which avoids transform functions for messages that would be eliminated by (later) select operations; and which “pushes” all selects in the information flow toward a single node so that all event distribution (selection) can be accomplished by a single content-based publish/subscribe system.
The present invention therefore advances the technology of messaging middleware and extends its range of application by providing optimizations which allow stateless messaging systems to be converted to a form which can exploit efficient multitask technology developed for content-based publish/subscribe systems.


REFERENCES:
patent: 5175843 (1992-12-01), Casavant et al.
patent: 5412804 (1995-05-01), Krishna
patent: 5701456 (1997-12-01), Jacopi et al.
patent: 5857097 (1999-01-01), Henzinger et al.
patent: 6032144 (2000-02-01), Srivastava et al.
Reflection in the Gryphon Message Brokering System, Sturman, D.; Banavar, G.; Strom, R.; In Reflection Workshop of 13thACM Conference on Object Oriented Programming Systems, Languages and Applications, Oct. 1998, 12 pages.*
Site and scheduling policies in multicomputer database systems, Freider, O.; Baru, C.K., Knowledge and Data Engineering, IEEE Transactions , vol. 6, Aug. 1994, ISSN: 1041-4347, pp. 609-619.*
A data-flow graphical user interface for querying a scientific database, Tjan, B.S.; Breslow, L.; Dogru, S.; Rajan, V.; Rieck, K.; Slagle, J.R.; Poliac, M.O., Visual Languages, Proceedings IEEE Symposium, Aug. 1993, ISBN: 0-8186-3970-9, pp. 49-54.*
Query processing for knowledge bases using join indices, Shrufi, A.; Topaloglou, T., Conference on Information and Knowledg Management, Proceedings 4th International Conf. on Information and Knowledge Management, 1995, ISBN: 0-89791-812-6, pp. 158-166.*
Combinatorial algorithm for the generalized circulation problem, Golberg, A.V.; Plotkin, A. S.; Tardos, E., this paper appears in: Foundation of Computer Science, 1988., 29thAnnual Symposium on Oct. 24-26, 1988, pp. 432-443.*
High performance DSP software using data-flow graph transformations, Zivojnovic, V. ; Ritz, S.; Meyr, H.; this paper appear in: Signals, Systems and Computers, 1994. Conference Record on the 28th Conference on Oct. 31-Nov. 2, 1994, pp. 492-496.

Affiliated with

Also associated with

Rating

Reduction and optimization of information processing systems does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Reduction and optimization of information processing systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reduction and optimization of information processing systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3235970