Method of independent simultaneous queueing of message descriptors

• US 5,951,706 A
• Filed: 06/30/1997
• Issued: 09/14/1999
• Est. Priority Date: 06/30/1997
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Benner, Alan Frederic
• Primary Examiner(s): Grant, William
• Assistant Examiner(s): Marc, McDieunel, Marc, McDieunel
• Application Number:
  US08/884,974
• Time in Patent Office: 806 Days
• Field of Search: 371/33, 395/200.67, 395/200.49, 395/200.32, 395/200.57, 395/200.33, 395/200.51, 395/500, 395/569, 395/677, 395/683, 395/825, 395/846, 395/185.02 , 395/200.8, 703/8, 703/103, 379/88.07, 379/88.08, 379/88.1, 379/88.25, 379/211
• US Class Current: 714/749
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

Abstract

Two independent pointers within a message descriptor are used to link the message descriptor to various queues during transmission of a message from a sender node to a receiver node within a computer environment. In particular, one pointer is used to link the message descriptor on either a pending send queue or a send queue, while the other pointer is used to link the message descriptor on either an unacknowledged queue or an acknowledged queue. For example, when a message is sent, it is removed from the send queue using one pointer and placed on the unacknowledged queue using the other pointer. Further, if the message is resent, it is linked back onto the send queue using the send queue pointer without disturbing the order of the message on the unacknowledged queue. Thus, ordering of message transmission is preserved, even when a message is sent multiple times.

Claims

1. A method of sending messages within a computer environment, said method comprising:

sending a message from a sender of said computer environment to a receiver of said computer environment, said sending comprising;

removing a descriptor of said message from a first data structure using a first pointer of said descriptor; and

appending said descriptor to a second data structure using a second pointer of said descriptor, said first and second pointers being independent of one another.

2. The method of claim 1, wherein said appending comprises:

setting said second pointer of said descriptor to null indicating said descriptor is currently the last element of said second data structure; and

updating said second pointer of a previous descriptor appended to said second data structure, if said previous descriptor exists, to reflect that said descriptor being appended is the next linked element to said previous descriptor.

3. The method of claim 1, further comprising receiving, by said sender, an acknowledgement from said receiver indicating receipt of said message, said receiving comprising removing said descriptor from said second data structure and appending said descriptor to a third data structure using said second pointer.

4. The method of claim 3, wherein said first data structure comprises one or more descriptors capable of being received by said receiver, said second data structure comprises one or more descriptors that has been sent to said receiver, but not acknowledged by said receiver, and said third data structure comprises one or more descriptors that has been acknowledged by said receiver.

5. The method of claim 3, wherein said removing, said appending said descriptor to said second data structure, and said receiving are performed by one or more hardware elements of said computer environment.

6. The method of claim 1, further comprising resending said message from said sender to said receiver, said resending comprising appending said descriptor to said first data structure using said first pointer, wherein said descriptor also remains on said second data structure and ordering of said descriptor on said second data structure is maintained.

7. The method of claim 6, wherein said appending said descriptor to said first data structure comprises:

setting said first pointer of said descriptor to null indicating said descriptor is currently the last element of said first data structure; and

updating said first pointer of a previous descriptor appended to said first data structure, if said previous descriptor exists, to reflect that said descriptor being appended is the next linked element to said previous descriptor.

8. The method of claim 6, further comprising removing said descriptor from said first data structure, after said message is resent.

9. The method of claim 6, further comprising removing said descriptor from said second data structure when receipt of said message is acknowledged by said receiver.

10. The method of claim 9, further comprising appending said descriptor to a third data structure using said second pointer, after said descriptor is removed from said second data structure.

11. The method of claim 1, further comprising appending said descriptor, using said first pointer, to a pending send data structure prior to sending said message, when said receiver is incapable of receiving said message.

12. The method of claim 11, further comprising removing said descriptor, using said first pointer, from said pending send data structure and appending said descriptor to said first data structure, when said receiver is capable of receiving said message.

13. A method of queueing messages within a computer environment, said method comprising:

using a first pointer of a message descriptor to link said message descriptor to a first data structure; and

using a second pointer of said message descriptor to link said message descriptor to a second data structure, wherein said first and second pointers are independent of one another and wherein said message descriptor is appended to both said first data structure and said second data structure for a certain amount of time.

14. The method of claim 13, wherein appending of said message descriptor to said second data structure indicates receipt of a message corresponding to said message descriptor is to be acknowledged, and wherein appending of said message descriptor to said first data structure indicates retransmission of said message is required.

15. The method of claim 14, further comprising removing said message descriptor from said first data structure after retransmission of said message and removing said message descriptor from said second data structure after receipt of said message by said receiver is acknowledged.