Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-03-30
2004-07-06
Chin, Wellington (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S411000, C370S394000
Reexamination Certificate
active
06760340
ABSTRACT:
TECHNICAL FIELD
This invention relates in general to multicasting messages within a network and, in particular, to sequencing messages within a routing network to facilitate ordered delivery thereof to one or more clients.
BACKGROUND OF THE INVENTION
Many network environments enable messages to be forwarded from one site within the network to one or more other sites using a multicast protocol. Typical multicast protocols send messages from one site to one or more other sites based on information stored within a message header. That is, each message has two components: the message header, which includes the routing information, including destination addresses or a predefined group name that is associated with a fixed list of destinations; and a data content, which is the data of the message. The routing information is read from the message header and is used to send the data content of the message to the specified destinations.
One example of a system that conventionally includes such a network environment is a publish/subscribe system. In publish/subscribe systems, publishers post messages and subscribers independently specify categories of events in which they are interested. The system takes the posted messages and includes in each message header the destination information of those subscribers indicating interest in the particular message. The system then uses the destination information in the message to forward the message through the network to the appropriate subscribers.
In large systems, there may be many subscribers interested in a particular message. Thus, a large list of destinations needs to be added to the message header and used in forwarding the message. The use of the list, which can be even longer than the message itself, can degrade system performance. Other approaches have included the use of multicast groups, in which destinations are bound to a group name, and then that name is included in the message header. The message is then sent to all those destinations bound to the name. This technique has the disadvantage of requiring publishers to send to and subscribers to receive from a static set of groups, which restricts flexibility in many publish/subscribe systems.
DISCLOSURE OF THE INVENTION
A publish/subscribe system consists of a network of message routers (or simply routers) connected via links in an arbitrary graph topology. A number of clients connect to the periphery of this router network and either publish or subscribe to messages. A message consists of a number of attributes, which are name-value pairs. A subscription specifies a predicate on the attributes of messages.
The router network is responsible for routing messages from publishers to interested subscribers based on matching events to subscription predicates. One embodiment of this routing protocol, referred to as content-based routing, is described in the above-incorporated co-pending patent application entitled “Routing Messages Within A Network Using The Data Content Of The Message.” Content-based routing proceeds as follows. From each router node at which a publisher is present, the system computes and stores a spanning tree to reach every other node in the network. All published messages from a particular publisher then follow the paths in the corresponding spanning tree, with each router node performing enough matching to determine which of its child routers should receive the published message.
Briefly summarized, the present invention is directed in one aspect to providing a mechanism for sequencing messages for multicasting through content-based subscriptions in a manner which is resilient to failures in the network or routers. Ordering resiliency is achieved by assigning sequencing numbers to messages within the network, and then using the sequencing numbers to order delivery of the messages.
More particularly, provided herein is a method for routing messages within a network. The method includes: receiving a message; sequencing the message at a node of the routing network with other messages received by the routing network to produce an ordering of messages within the routing network for delivery; and delivering the message to one or more clients of the routing network while maintaining the ordering of the message delivery.
In another aspect, a system for routing messages within a routing network is provided which includes means for receiving a message and means for sequencing the message at a node of the routing network with other messages received by the routing network to produce an ordering of message delivery within the routing network. The system also includes means for delivering the message to one or more clients of the routing network while maintaining the ordering of message delivery.
In still another aspect, a system of routing messages within a network is provided. The system includes a routing network adapted to receive a message, and a sequencer node disposed within the network for sequencing the message with other messages received by the routing network to produce an ordering of message delivery within the routing network. The routing network includes one or more routers for delivering the message to one or more clients of the network. The sequencing of the message occurs prior to delivery of the message to the one or more clients of the network and allows the message to be delivered to the one or more clients while maintaining the ordering of message delivery.
In a further aspect, an article of manufacture is provided which includes at least one computer usable medium having computer readable program code means embodied therein for effecting routing of messages within the network. The computer readable program code means in the article of manufacture includes: computer readable program code means for causing a computer to effect receiving a message; computer readable program code means for causing a computer to effect sequencing the message at a node of the routing network with other messages received by the routing network to produce an ordering of message delivery within the routing network; and computer readable program code means for causing a computer to effect delivering the message to one or more clients of the network while maintaining the ordering of message delivery.
To restate, provided herein is a technique for sequencing messages within a routing network itself to ensure reliable multicasting of messages across the network in a totally ordered manner. Although principally described herein in connection with data-content routing of messages, the sequencing technique can be applied to other routing systems, e.g., subject-based routing. A system implementing the sequencing technique of the present invention allows senders and receivers to connect anywhere in the network regardless of the location of the sequencer. Again, sequencing of messages occurs within the network itself between the sender and the one or more clients to which the message is directed. The sequencing technique described herein allows a sender or receivers to choose whether ordering of messages is required by either the sender or the receivers. This choice allows a tradeoff of system resources versus quality of service.
REFERENCES:
patent: 5257369 (1993-10-01), Skeen et al.
patent: 5325362 (1994-06-01), Aziz
patent: 5517562 (1996-05-01), McConnell
patent: 5522046 (1996-05-01), McMillen et al.
patent: 5555244 (1996-09-01), Gupta et al.
patent: 5557798 (1996-09-01), Skeen et al.
patent: 5570366 (1996-10-01), Baker et al.
patent: 5581764 (1996-12-01), Fitzgerald et al.
patent: 5604837 (1997-02-01), Tanaka
Hanson et al., “A Predicate Matching Algorithm for Database Rule Systems”, Published at Proceedings of SIGMOID, pp. 271-280 (1991).
Mishra et al., “Consul: A Communication Substrate for Fault-Tolerant Distributed Programs”, TR91-32, Department of Computer Science, The University of Arizona, pp. 1-33 (Nov. 1991).
Smirnov, M.I., “Object-Oriented Framework for a Scalable Multicast Call Modelling”, Teleservices and Multimedia Communications Second International COST 237 Workshop, Proce
Banavar Guruduth Somasekhara
Chandra Tushar Deepak
Miller Kevan Lee
Strom Robert Evan
Sturman Daniel Charles
Cameron Esq. Douglas W.
Chin Wellington
Heslin Rothenberg Farley & & Mesiti P.C.
Pham Brenda
Radigan, Esq. Kevin P.
LandOfFree
Message sequencing for ordered multicasting of a message... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Message sequencing for ordered multicasting of a message..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Message sequencing for ordered multicasting of a message... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3204100