Multiplex communications – Pathfinding or routing – Store and forward
Reexamination Certificate
2000-07-10
2003-04-01
Nguyen, Chau (Department: 2663)
Multiplex communications
Pathfinding or routing
Store and forward
Reexamination Certificate
active
06542513
ABSTRACT:
TECHNICAL FIELD
This Application relates to message processing systems. More particularly, this Application relates to methods and systems, including protocols and buffering, for facilitating the transmission of messages from a source node to a destination node in a message processing system.
BACKGROUND OF THE INVENTION
Message processing systems, for example, the multiprocessor data processing system
10
depicted in
FIG. 1
, require reliable message communication paths between respective ones of the processors
12
1
. . .
12
j
. The exemplary system
10
of
FIG. 1
employs an exemplary communication medium or switch network
20
commonly coupled to the processors
12
. The processors may require respective communication adapters
14
1
. . .
14
j
to control communications between each processor
12
and the medium
20
via respective connections
16
1
. . .
16
j
. Communication between, for example, software application(s) executing on the processors
12
of system
10
can thus be provided via medium
20
. Storage medium
22
may be employed in the system to hold the applications, associated data, etc.
Because respective processors may be supporting different, asynchronous application software partitions, asynchronous messaging becomes a useful form of communication between the processors. For example, messages may require transmission from a “source” node (e.g., processor
12
1
) to a “destination” node (e.g., processor
12
j
).
Random delays may be experienced in medium
20
by individual messages sent from a source node to a destination node, therefore, the destination node may be required to receive messages in an order different from the order in which they were transmitted from the source node. The destination node, to accommodate this requirement, may provide buffers to hold incoming, unordered messages. The messages can then be retrieved from the buffers and processed in their proper order. This is illustrated in
FIG. 2
, which is a hybrid hardware/software diagram of a message processing system like that of FIG.
1
and which depicts a message source node
18
, and a message destination node
18
j
. (The term “node” is used broadly herein to connote any identifiable combination of hardware and/or software to or from which messages are passed.) Source node
18
1
has allocated therein send message buffers
30
within which are placed messages M(
1
), M(
2
) and M(
3
) which, for application reasons, are required to be sent through send message processing
32
, across medium
20
, to destination node
18
j
.
As discussed above, random delays in medium
20
may cause messages M(
1
), M(
2
) and M(
3
) to arrive at destination node
18
j
out of order. To accommodate out of order receipt of messages, destination node
18
j
, in anticipation of the arrival of messages from various sources in the system, can allocate or post receive buffers
40
. In the example of
FIG. 2
, buffer B
1
holds the first arriving message M(
2
), buffer B
2
holds the second arriving message M(
1
) and buffer B
3
holds the third arriving message M(
3
). In this example, message M(
2
) has arrived before message M(
1
). However, to properly order the messages, receive message processing
42
can simply remove message M(
1
) from its buffer first (thereby reordering the messages) and can then pass the messages in their proper order to receive processing
44
(e.g., the application software executing at the destination node).
Those skilled in the art will understand that message ordering in a system can be imposed by using a particular protocol, e.g., messages sent from a particular source to a particular destination may be sequentially numbered and the sequential numbers can be transmitted with the messages so that the destination node can properly reorder the messages.
The process of allocating or posting receive buffers
40
in destination node
18
j
is often a dynamic one, and if more messages are arriving than there are buffers posted, buffer overrun can occur. To avoid buffer overrun at the destination node, it is common to 1) adopt a convention wherein the destination node automatically discards packets assuming that the source node will retransmit them after a timeout, or 2) adopt a rendezvous protocol when the message lengths are larger than some threshold. A rendezvous protocol, as discussed further below, involves the transmission from the source node of a control information packet relating to a message to be sent from the source node to the destination node. The control information often includes an indication of the length of the entire data portion of the message to be sent. When a buffer of adequate length is allocated or posted at the destination node, an acknowledgement packet transmission (e.g., “READY TO RECEIVE”) is sent from the destination node to the source node, and the source node can thereafter reliably send the entire message to the destination node. In conventional rendezvous protocols, this initial exchange of the control information and acknowledgement packets results in a loss of performance for messages longer than the threshold because two packets are now required to be exchanged between the source and destination nodes before any actual message data can be exchanged.
What is required, therefore, is a method, system, and associated program code and data structures, which prevent the performance degradation associated with packet retransmission after timeouts, or with standard rendezvous protocols in which an exchange of packets between source and destination nodes occurs before any actual message data is exchanged.
SUMMARY OF THE INVENTION
The shortcomings of the prior approaches are overcome by the present invention, which relates to methods, systems, protocols and buffering for facilitating the efficient transmission of messages from a source node to a destination node in a message processing system. An optimistic, eager rendezvous transmission mode is disclosed wherein first data portions of messages are transmitted from a source node to a destination node along with the initial control information packets. By employing early arrival buffering at the destination node, the source node can reliably send the first data portions of the messages to the destination node along with the control information, knowing that the first data portions will be reliably stored in either early arrival buffering or posted receive buffering.
In one particular aspect, the present invention is a method for transmitting at least one message from a source node to a destination node, the message including a first data portion and a second data portion. The method includes providing, at the destination node, first, early arrival buffering to reliably store the first data portion of the message. The first data portion of the message is transmitted, along with control information relating to the first message, from the source node to the destination node. The destination node stores the first data portion of the message in the provided early arrival buffering, and the source node thereafter waits for an acknowledgement pertaining to the first message from the destination node before transmitting any remaining data portions of the first message.
The destination node determines whether it can receive the remaining data portions of the first message, e.g., whether adequate receive buffering is posted, in response to receiving the control information relating to the first message. In response to an eventual determination that the destination node can receive the remaining data portions of the first message, the destination node transmits the acknowledgement pertaining to the first message to the source node, and the source node transmits the second data portion of the first message in response to receiving the acknowledgement.
In another aspect, the present invention provides a combined rendezvous mode message transmission method for a message processing system, including alternating between rendezvous transmission modes as a function of the amount of free space in the early arr
Franke Hubertus
Govindaraju Rama K.
Pattnaik Pratap C.
Raghunath Mandayam T.
Straub Robert M.
Cutter, Esq. Lawrence D.
Heslin Rothenberg Farley & & Mesiti P.C.
Kwoh Jasper
Nguyen Chau
LandOfFree
Optimistic, eager rendezvous transmission mode and combined... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimistic, eager rendezvous transmission mode and combined..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimistic, eager rendezvous transmission mode and combined... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3088285