Electrical computers and digital processing systems: multicomput – Computer-to-computer protocol implementing – Computer-to-computer handshaking
Reexamination Certificate
1998-09-08
2001-06-12
Rinehart, Mark H. (Department: 2152)
Electrical computers and digital processing systems: multicomput
Computer-to-computer protocol implementing
Computer-to-computer handshaking
C709S238000, C709S248000, C370S390000, C370S469000, C714S018000, C714S048000
Reexamination Certificate
active
06247059
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to a computing system using clustering principles, and more particularly to transmission of multicast (i.e., broadcast) messages to members of the system.
Many segments of today's financial and business communities (e.g., stock exchanges, banks, telecommunications companies) require computing environments that are fault tolerant and provide high availability. Downtime in these environments can be extremely costly and are not lightly tolerated. There exists a number of different approaches to providing fault tolerance and high availability. However, one enjoying increasing popularity is the employment of distributed operating systems in connection with a collection of independent processing environments, referred to as nodes, to be connected via some form of a communication interconnect to form a “cluster” which can operate as a single system or as a collection of independent processing resources. High availability and improved fault tolerance are achieved by the distributed nature of the operating system. High availability is achieved by distributing the system services and providing for their failover. With this approach, the system as a whole can still function even with the loss of one or more of the nodes that make up the system.
Regardless of how such processing system clusters are used, it is often advantageous to keep each of the processing elements of such systems up-to-date as, for example, to the system's configuration (e.g., what elements are located where, etc.). This, in turn, often will require that each node possess the capability of transmitting (i.e., broadcasting) messages to the other nodes of the cluster system. Often, such “multicast” transmissions are sent point-to-point, that is, from a sender node to a first node, then to a second node, and so on until all target nodes have been addressed. This multicast transmission procedure can require considerable processing time, increase the messaging traffic on the communicating medium of the cluster (particularly when the message is intended for every node in the cluster), and impose unacceptable restraints and limitations on system performance. Some procedures will require continuing retransmission of the message when not acknowledged by the intended receiver node. The constant retransmission of the message to all non-responding nodes further increases traffic on the network thereby degrading the overall network performance as well as occupying processor time and other cluster resources.
More importantly, however, is the need to identify the failure to receive a message, i.e., for the intended receiver to determine in some way that a message was sent, but not received. For example, if a sender node and multiple receiver nodes are interconnected by a routing network, it is not unexpected that messages can get lost and not arrive at one or more of the intended receivers (in the case of multicast transmissions). Thus, if the sender node transmits a multicast message that is received by some, but not all, of the intended receivers, those receivers that did not receive the message may well be missing needed information that can inhibit or impede system operation or proper operation of other nodes of the system.
It can be seen, therefore, that there is a need for a more efficient method of multicast transmission in a multiple processor or cluster system that also checks for and supplies possible missing multicast messages.
SUMMARY OF THE INVENTION
The present invention provides a prompt and efficient method of transmitting a multicast message in a multiple processor cluster. In addition, the method provides a technique for sequenced once only delivery of messages supplemented by the ability to supply missing earlier-sent messages to multiple receivers.
The invention finds particular advantage in a multiple processor system is arranged as a cluster of nodes. Each node comprises one or more processor units, although those skilled in this art will readily see that the invention will also find effective use in other multiple processor arrangements. According to the invention, a sender node will initiate a multicast message transmission by inserting, in a destination address field of the message, an address indicative of the message being a multicast transmission. The multicast message is also structured to include a sequence number and a “date of birth” (DOB) marker (a monotonically incrementing value that is indicative of when a node is brought on-line, i.e., comes to life). All nodes communicatively connected to the sender node will, therefore, receive the multicast message, and acknowledge that receipt with a responsive acknowledgement (ACK) message addressed to the sender node (as identified in the multicast message). A failure by the sender node to receive an ACK message from any of the nodes for whom the multicast message was intended within an allotted time period will prompt the sender to assume that the non-responding receiver node(s) did not, for whatever reason, receive the multicast message, and to begin sending point-to-point messages to such nodes. Point-to-point messages will continue to be sent until a responsive ACK is received, or the non-responsive node is declared by the system to be inoperative.
When a multicast message is received, the receiver node will check the sequence number contained in the message. If the sequence number is out of sequence, the receiver node will queue the message in an ordered queue and then check the queue for the missing least sequence number message, and send a negative acknowledgement for the multicast message corresponding to such missing least sequence number. On the other hand, if the sequence number or the DOB marker contained in the multicast message do not match the sequence number or marker expected by the receiver node, a resynchronization request message will be returned by the receiver node to the sender node. The resynchronization request will cause the sender node to respond with its new marker, and the sequence number of the last multicast message unacknowledged by the receiving node. In this way, lost multicast messages can be accounted for and delivered.
In a further embodiment of the invention, if a receiver node repeatedly fails to respond to multicast messages, but does respond to point-to-point messages, the sender node will make note of that fact, and all future multicast messages will be accompanied by a point-to-point message to that particular receiver node—until it finally responds to a multicast message.
The invention is disclosed in connection with use of the User Data Protocol (UDP) of the TCP/IP protocol suite to transfer information (messages) between the nodes of the system, including the multicast messages. A multicast message will typically consist of a number of UDP datagrams. Each datagram is provided a sequence number that identifies the location of the datagram in the sequence. Further, subsequent messages as well as prior messages have sequence numbers that identify not only the datagrams with a sequence of a message, but also relative to the other sequences. When a receiving node receives a datagram
A further understanding of the nature and advantages of the inventions herein may be realized by reference to the remaining portions of the specification and the attached drawings.
REFERENCES:
patent: 4617657 (1986-10-01), Drynan et al.
patent: 5459725 (1995-10-01), Bodner et al.
patent: 5602839 (1997-02-01), Annapareddy et al.
patent: 5604487 (1997-02-01), Frymier
patent: 5905871 (1999-05-01), Buskens et al.
patent: 6092220 (2000-07-01), Palmer et al.
Braudes et al., Requirements for Multicasts Protocols, RFC 1458, May 1993, sections 3.4, 4.2.2.-3.*
Patent Cooperation Treaty (PCT) International Search Report.
The Data Link Layer, Chapter 3, p. 202 (XP-002108581).
Routing Algorithm Issues, Chapter 9, p. 205 (XP-002108582).
Johnson Charles S.
Shafiq Muhammad
Boyce Justin
Compaq Computer Company
Kang Paul
Oppenheimer Wolff & Donnelly LLP
Rinehart Mark H.
LandOfFree
Transaction state broadcast method using a two-stage... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Transaction state broadcast method using a two-stage..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Transaction state broadcast method using a two-stage... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2478749