Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1997-12-29
2002-01-08
Luu, Le Hien (Department: 2152)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S235000, C370S278000, C370S300000, C709S231000, C709S232000, C709S236000
Reexamination Certificate
active
06337852
ABSTRACT:
TECHNICAL FIELD
This Application relates to message processing systems. More particularly, this Application relates to a method 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, but related application software partitions, messaging must be used as a 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
).
The asynchronous nature of the application software partitions on the source and destination nodes often results in a condition where the number of messages sent from a source node exceed the destination node's ability to handle them. Normally, the destination node is expected to post buffers to hold incoming messages. The messages can then be retrieved from the buffers and appropriately processed by the application software. 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
1
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
.
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(
1
), buffer B
2
holds the second arriving message M(
2
) and buffer B
3
holds the third arriving message M(
3
). Received message processing
42
then removes messages from their buffers and can then pass the messages to receive processing
44
(e.g., the application software partition 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 identified and the sequential indicia can be transmitted as control information along with the data portions of 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. Traditional solutions to avoid buffer overrun at the destination node include 1) data buffering with a pre-reservation protocol or, 2) adopting a convention wherein the destination node automatically discards packets assuming that the source node will retransmit them after a time-out. The first solution assumes a destination node that is frequently unprepared to accommodate data, and the second solution assumes a destination that is rarely unprepared to accommodate data.
A problem with the first solution occurs when message size is practically unbounded, or if the number of message sources is large. Large messages can be decomposed into smaller pieces and flow controlled into the buffers, if the overhead to do so is manageable. However, many sources present problems with buffer fragmentation or starvation. Distributed fairness protocols can be introduced to solve these problems, but at a price in complexity and additional overhead.
A problem with the time-out/retransmit solution is that should the destination be unable to accommodate the data for an extended period of time, many needless retransmits will occur, occupying otherwise useful bandwidth on the medium.
A third conventional solution to this problem is a rendezvous protocol. A rendezvous protocol 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 may include an indication of the length of the entire data portion of the message to be sent, as well as indicia which identifies the message and/or its sequence. When a buffer of adequate length is allocated or posted at the destination node, an acknowledgment packet transmission 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. This technique also makes conservative assumptions about the preparedness of the destination node to accommodate the data portion of the message. In conventional rendezvous protocols, the initial exchange of the control information and acknowledgment packets results in a loss of performance 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 time-outs, 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 a method for facilitating the efficient transmission and flow control of messages from a source node to a destination node in a message processing system.
The present invention seeks to strike a balance between the ultra-conservatism of pure buffering and rendezvous, and the ultra-optimism of time-out/retransmit. The present invention assumes that the destination is generally able to accommodate data portions of messages, but if it is not, the time that it may take to become prepared may be very long. Such conditions often arise in multi-tasking systems where context swaps between processes are long and a process may be suspended for an unbounded period of time. To accommodate this type of environment, the present invention involves optimistically sending the data portion of a message along with control information, in an initial transmission from the source to the destination. However, it is not appropriate for the destination to discard the entire content of this transmission if it is unable to accommodate the data since there may be many time-out periods before the destination is subsequently able to accommodate the data. Therefore, the destination retains enough control information to identify the message to the source, but discards the data portion of the message (i.e., “runts” the message). The source does not time-out/retransmit, rather, it waits for the destination to notify it that it is prepared. At that time, the source retransmits the message, knowing the destination will be able to accommodate it. The number of retransmissions from the source node to the destination node is therefore bounded to one.
In that regard, in one aspect, the present invention relates to a flow control method for transmitting a plurality of messages from
Benner Alan F.
Desnoyers Christine M.
Joseph Douglas J.
Kampf Francis A.
Cutter, Esq. Lawrence D.
Gonzales, Esq. Floyd A.
Heslin Rothenberg Farley & & Mesiti P.C.
Luu Le Hien
Prieto Beatriz
LandOfFree
Flow control system using control information of a message... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Flow control system using control information of a message..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Flow control system using control information of a message... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2825260