Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-12-10
2004-11-30
Patel, Ajit (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S400000, C370S432000
Reexamination Certificate
active
06826182
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of computer networking, and more specifically to an AND-OR multi-cast message routing method for high performance fault-tolerant message replication.
2. Related Art
In many high availability distributed service environments, it is required to maintain multiple synchronized databases with nodes spread over multiple local area network (LAN) sites connected to a Wide Area Network (WAN). High performance requirements mandate that these databases synchronize in real-time continually with new update messages originating at any node in the configuration.
Some terms are defined hereunder along with
FIGS. 1-4
for a better understanding of the invention.
FIG. 1
illustrates a typical multi-site nodal architecture. In this example, LANs
11
,
12
,
13
, are connected to a WAN
16
. Each LAN
11
,
12
,
13
, is housing Service Control Points (SCPs) and corresponding databases (DB). The SCPs receive updates from an SS7 network
17
and are further required to replicate their share of SS7 Network Side Updates (NSUs), and propagate the updates to all their peer nodes for commitment to their respective databases for an automatic synchronization.
In the configuration of
FIG. 1
, all the SCPs have access to their own copies of service databases for query processing and updating. Each SCP communicates the received updates to other SCPs so that they may commit the updates to the respective databases. The databases thus get up-to-date, as well as synchronized on the service information.
The message replication process implies that each message is copied and transmitted to all other destinations. It can be implemented using—synchronous or asynchronous algorithms. The goal of the synchronous class of algorithms is message-by-message synchronization, whereby a message is transmitted only after the previously propagated message is confirmed to have been successfully committed at all the destinations. In addition, a message has to be committed either everywhere or nowhere, and if the message cannot be committed at one SCP, the transaction is rolled back and all the databases are restored to the previous state. Obviously the synchronous algorithms are limited by the speed of the slowest SCP.
Another disadvantage of this class of algorithms is that, occasionally, an SCP may fail and may hold up the entire replication process until it is revived. In order to guarantee that the updates are carried out atomically, i.e. done everywhere or nowhere, exchange of a large number of protocol messages among SCPs is required and this adversely impacts the network bandwidth utilization.
FIG. 2
illustrates an example of asynchronous message replication viewed as a process of identical message streams
26
,
27
,
28
, propagating from a source to different destinations
21
,
22
,
23
, at different paces, depending upon the individual destination. The messages are propagated continuously to the peer-SCPs which in turn commit these messages to their respective databases for eventual synchronization of the databases.
Asynchronous algorithms on the other hand, do not guarantee dynamic convergence of the databases, but offer speed and effective network bandwidth utilization, with eventual convergence of the databases. Further, since the time order of origination of the NSUs coming from different sources need not to match the order of their receipt at the destination ends, asynchronous algorithms have to implement a database updating strategy which ensures database synchronization despite the differences in the order in which updates from different streams arrive at individual destination nodes. This update strategy should also involve a method of detecting conflicting updates originating at the same time, or almost at the same time at different SCPs, assuming the clocks of all SCPs are synchronized using a Global Positioning System. Such strategies are available and hence it is possible to implement an asynchronous replication algorithm and take advantage of the high performance it provides. However, it is possible to improve this performance with respect to network bandwidth utilization by effective propagation of message streams.
A solution to the message replication problem is to replicate all the messages received by a SCP and to send them to all the SCPs in the network. The messages generated at any source node are placed into a number of message streams equal to the number of destinations and propagated to their destinations. This implies that the WAN traffic increases five times for the topology with five nodes per LAN site presented in
FIG. 1
, since a message generated at one node at a LAN site
11
flows five times on each WAN connection. This is definitely a colossal wastage of WAN bandwidth because the same message has to be propagated over a WAN
16
a number of times equal to the number of the other SCPs at all the other LAN sites
12
,
13
.
Some of the problems associated with such a distribution are listed below. In the usual configuration where a number of SCPs are housed on a few LAN sites interconnected by a WAN, known multi-cast routing methods generate WAN peak traffic proportionate to the number of the SCPs in the network. This could lead to network congestion during traffic periods, because of the relatively low bandwidth of the WANs (compared to the LANs).
To build a fault tolerant process upon the above described framework it would be extremely difficult because if a SCP fails, the replication process stops. Moreover, the complexity of the protocols needed to assess the best SCP to be contacted by a failed node at the time of recovery provides for extensive delay.
Finally, the presently known commercial products use synchronous replication methods like the 2-phase or the 3-phase protocols and this implies extensive protocol message traffic and propagation latency.
Therefore, there is a need for an improved asynchronous replication process for a multi-cast messaging framework.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide an asynchronous multi-casting method which alleviates totally or in part the drawbacks of the prior art methods.
Another objective of the present invention is to minimize WAN traffic by allowing a message to flow across a WAN connection at most once during normal, failure-free operation mode.
According to one aspect of the present invention, a multi-cast routing method for asynchronous propagation for messages from any source location to its pre-configured replication nodes in an advanced intelligent network (AIN), is provided. The method comprises the steps of establishing connections between a primary replication node located at a first LAN site and all its peer nodes at same LAN site, creating a transit node located at a second LAN site, and establishing a connection between the primary replication node and the transit node (AND-routing). The transit node becomes a secondary source of replication at the second LAN site. Finally, connections are established between the transit node and all its peer nodes located at the second LAN site.
According to another aspect of the invention, a fault tolerant replication method without any degradation of the WAN bandwidth efficiency, is provided. A surrogate node is created for each replication node so as to form complementary replication nodes at each LAN site. Using an OR-routing, the messages from an active replicator can be directed either to the replication node, or to its surrogate node, whichever is live.
The message streams between replication nodes are established by implementing identical multi-cast queues for each replication node. A multi-cast queue may have a plurality of source sublocations configured at the input end, and a plurality of destination sublocations configured at the output end for routing messages between the replication nodes and the destination nodes that receive the message. The destination nodes contain identical databases as the replication nodes, and use the update messag
Nortel Networks Limited
Patel Ajit
Shah Chirag
LandOfFree
And-or multi-cast message routing method for high... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with And-or multi-cast message routing method for high..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and And-or multi-cast message routing method for high... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3320269