Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
1999-12-31
2004-08-17
Burgess, Glenton B. (Department: 2153)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
C709S243000, C709S207000, C370S319000, C370S401000, C370S432000
Reexamination Certificate
active
06779038
ABSTRACT:
TECHNICAL FIELD
The invention relates generally to communication networks and, more particularly, to a system and method for extending virtual synchrony to wide area networks.
BACKGROUND
A distributed system utilizing a protocol referred to as virtual synchrony (i.e., operating in a virtual synchrony environment) comprises a plurality of process groups, each of which process groups comprises a plurality of processes. Processes are typically distributed among two or more computers so that if one computer fails, the entire process group does not fail. Processes and process groups are configured for managing and executing application programs, and for transmitting messages between the process groups and processes.
Virtual synchrony ensures that a message transmitted to a plurality of destination processes is received by either all or none of the destination processes. Virtual synchrony, furthermore, ensures that messages delivered to a set of destination processes are delivered in a specified order to all destinations. In a system using virtual synchrony, the message order is maintained even though subsequent messages destined for other processes are interspersed with each other. Several message orders may be specified, generally FIFO (First-In-First-Out), causal, and total order.
FIFO order means that the messages will be delivered in the order they were transmitted but without any specified ordering between messages from different sources. So, if message source A transmits messages A
1
and A
2
in that order, and message source B transmits message B
1
and B
2
in that order, each destination may deliver A
1
, A
2
, B
1
, and B
2
to applications on the respective destinations in any order, so long as A
1
is delivered before A
2
and B
1
is delivered before B
2
, such as A
1
, A
2
, B
1
, B
2
; or B
1
, A
1
, B
2
, A
2
; etc.
Causal order means that a message may not be delivered before any cause of the message is delivered. For example, a process A may transmit a message A
1
to both a process B and a process C. Message A
1
causes process B to transmit message B
1
to process C. If messages are delivered in causal order, then message A
1
must be delivered before message B
1
because B
1
was caused by A
1
. These type of problems may happen in distributed systems due to transmission delays, loss of messages in the network causing retransmission, scheduling delays on processors, or many other network problems.
Total order means that each destination process may deliver all its messages in exactly the same order as any other process delivering the same set or any shared subset of messages. Suppose we have processes A, B, and C and message X
1
comes to A and B, X
2
comes to B and C, and X
3
comes to all the processes. Any order may be selected as long as A and B deliver X
1
and X
3
in the same order and B and C deliver X
2
and X
3
in the same order.
Theoretically, these message orders can be applied in a mutually exclusive manner. In practice, though, they are generally inclusive (causal implies FIFO, total implies causal and FIFO).
Virtual synchrony with total order has been demonstrated to work very well within local area networks (LANs) using systems such as Totem. Such networks can be extended to wide area networks (WANs), using U.S. patent application Ser. No. 09/213,682, filed Dec. 17, 1998, entitled “Method and Apparatus to Extend the Fault-Tolerant Abilities of a Node into a Network,” issued Apr. 9, 2002 in the name of Law, Jr., as U.S. Pat. No. 6,370,654, which is hereby incorporated in its entirety by reference herein. Local Totem networks can be made fault tolerant using redundant communication fabrics as discussed in greater detail in U.S. patent application Ser. No. 09/477,784, filed Dec. 31, 1999, and entitled “Redundant Communication Fabrics for Enhancing Fault Tolerance in Totem Networks”, issued Apr. 22, 2003, in the name of Minyard, as U.S. Pat. No. 6,553,508, which is hereby incorporated in its entirety by reference herein. However, the system of U.S. Pat. No. 6,370,654 is not tolerant of the failure of a router or point-to-point communication link.
Accordingly, there is a need for a system and a method which will enable virtual synchrony to be extended to wide area networks while maintaining fault-tolerant properties.
SUMMARY
The present invention, accordingly, provides a system and a method which will enable virtual synchrony to be extended to wide area networks without a single point of failure in the system. In a preferred embodiment of the present invention, a virtual synchrony wide area network has a first local area network (LAN) and a second LAN. A first router and a second router are connected to the first LAN, and a third router and a fourth router are connected to the second LAN. Both LANs are virtual synchrony networks maintaining total order for all messages. A point-to-point link is connected between the first and third routers, between the first and fourth routers, and between the second and third routers, and between the second and fourth routers. Each router is provided with computer program code for controlling the flow of messages through the routers.
REFERENCES:
patent: 5737526 (1998-04-01), Periasamy et al.
patent: 5835696 (1998-11-01), Hess
patent: 6324161 (2001-11-01), Kirch
patent: 6331983 (2001-12-01), Haggerty et al.
patent: 6442594 (2002-08-01), Ouchi
patent: 6473425 (2002-10-01), Bellaton et al.
Extended Virtual Synchrony (1994) L. E. Moser, Y. Amir, P. M. Melliar-Smith and D. A. Agarwal Department of . . . The 14th IEEE International Conference on Distributed Computing Systems (ICDCS).*
Structured virtual synchrony: exploring the bounds of virtual synchronous group communication Katherine Guo, Werner Vogels, Robbert van Renesse. ACM Press New York, NY, USA pp.: 213-217 Year of Publication 1996.*
U.S. patent application Ser. No. 08/940,412, Koch, filed Sep. 30, 1997.
Sape Mullender,Distributed Systems, 2nd, ACM Press, NY, NY (1993), pp. 255, 329-352-413-417.
David Powell, “Group Communications,”Communications of the ACM, NY, NY, vol. 39, No. 4 (Apr. 1996), pp. 50-53.
L. E. Moser, Milliar-Smith, Agarwal, Budhia and Lingley-Papadopoulous, “Totem: A Fault-Tolerant Multicast Group Communication System,”Communications of the ACM, pp. 54-63, vol. 39, No. 4 (Apr. 1996), pp. 54-63.
Deborah A. Agarwal, “Totem: A Reliable Ordered Delivery Protocol for Interconnected Local-Area Networks” (dissertation submitted in partial satisfaction of the requirements of the Degree of Doctor of Philosophy in Electrical and Computer Engineering), University of California, Santa Barbara (Aug., 1994).
Burgess Glenton B.
Carr LLP
Choudhary Anita
LandOfFree
System and method for extending virtual synchrony to wide... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for extending virtual synchrony to wide..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for extending virtual synchrony to wide... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3323343