As per Relevance of the word messages, we have this rfc below:
Network Working Group L. Kleinrock (UCLA-NMC
Request for Comments: 626 H. Opderbeck (UCLA-NMC
NIC #22161 Mar 1974
"On a Possible Lockup Condition in
IMP Subnet Due to Message Sequencing
Lockup or deadlock conditions are one of the most serious system
that can occur in a computer system or network. Communication protocols have
to be designed very carefully to avoid the occurrence of these lockups.
common characteristic is that they occur only under unusual circumstances
were not foreseen or deemed too unlikely to occur by the protocol designers.
(However, these designers often are not the ones in a position to
such likelihoods quantitatively.)
The best known lockup that has occurred in the ARPANET is the
lockup [1]. The store-and-forward lockup, also described in Reference 1,
been avoided in the new IMPSYS by carefully observing Kahn's heuristics [1].
The last lockup in the subnet we know of occurred on December 21, 1973
(Christmas lockup"). This dormant lockup conditions was brought to
by collecting snapshot measurement messages from all sites simultaneously
The Christmas lockup happened when snapshot messages arrived at ther UCLA
which had allocated reassembly storage for them and no reassembly blocks
free. (A reassembly block is a piece of storage used in the actual
of reassembling packets back into messages) [2].
Deadlock conditions have not only been observed in the subnet but also
higher level protocols. The original design of the ICP, for example, had
flaw that was discovered only after a few months of use [3,4]. More
BBN reported a deadlock problem involving the exchange of HOST
information by the RSEXEC server (RSSER) programs [5].
As long as it is not possible to design practical communication
which guarantee deadlock-free operation it is vital to continually check
protocols that are currently in use for any such failures - even if they
"very unlikely" to occur. In this RFC we comment on a possible
condition in the IMP subnet which, to our knowledge, has not yet occurred
neither has it been identified. Though we have never seen this problem
actually happen it may occur in the future if no precautions are taken.
possible lockup condition is due to the sequencing of messages in the subset
To avoid the occurrence of reassembly lockup, the flow control mechanism
the subnet was modified in some significant ways. Currently there is a
of four messages that can simultaneously be in transmission between any pair
source and destination IMPs. As a result of removing the link-handling
the old IMPSYS, it became necessary to introduce a message sequencing
mechanism
-1-
Network Working Group
Request for Comments: 626
Messages leave the destination IMP in the same order as they entered the
IMP. (Note that the sequencing is done on an IMP-to-IMP basis, not a HOST-to
Host basis. This may introduce undesirable "sequencing delay" if two HOSTs
attached to the same destination IMP receive messages from the same source
IMP).
Sequencing of messages has, in general, the potential of introducing
conditions. The reason for this is that any message, say message (n+1),
is out of order (and therefore cannot be delivered to its destination HOST
may use up resources that are required by message (n) which must be
next. Therefore, message (n) cannot reach its destination IMP which, in turn
prevents the other messages (n+1), etc) that are out of order from being
delivered to their destination HOST(s). For this reason one has to be
careful not to allocate too many resources (e.g., buffers) to messages
are out of order
To avoid lockup conditions the current IMPSYS takes the following
precautions
1. Requests for buffer allocation are always services in
of message number; i.e., no 'ALLOCATE' is returned for
message (n+1) if message (n) (or a request for
allocation for message (n)) has not yet been received
serviced
2. Single packet messages (regular and priority) that
at the destination IMP out of order are not accepted
they were retransmitted in response to a previous
allocation. These messages are treated rather as a request
for the allocation of one buffer (according to 1 above)
then discarded
With these two precautions a deadlock condition appears to be impossible
occur. However, there is a second buffer allocation mechanism that is
tried to the message sequencing, namely the 'ALLOCATE' that is piggy-
on the RFNM for a multiple-packet message. The piggy-backed
represents a buffer allocation for the next multiple-packet message, and
for the next message in sequence. Thus, if the next message in sequence
a single-packet message, the piggy-backed ALLOCATE in effect
buffers to a message that is out of order
Let us see how this situation can lead to a deadlock condition. Assume
is a maximum number of 24 reassembly buffers in each IMP
-2-
Network Working
Request for Comments: 626
Let IMPs A, B, and C continually transmit 8-packet messages to the
destination IMP D such that all 24 reassembly buffers in IMP D are used up
this transmission of multiple packet messages. If now, in the stream
8-packet messages, IMP A sends a single-packet message it will generally
be accepted by destination IMP D since there is no reassembly buffer
available. (There may be a free reassembly buffer if the single-packet
happens to arrive during the time one of the three 8-packet messages is
transmitted to its HOST). The single-packet message will therefore be
as a request for buffer allocation. This request will not be serviced
the RFNM of the previous multiple-packet message is sent. At this time,
however, all the free reassembly buffers have already been allocated to
next multiple-packet message via the piggy-backed ALLOCATE mechanism.
only chance for the single-packet message to get its allocation
satisfied is to grab a reassembly buffer from one of the other two 8-
messages. This attempt may be unsuccessful because it depends on the
of events in the IMP. A deadlock condition can occur if IMP B and IMP
also send a single-packet message in their stream of 8-packet measures
cannot be serviced for the same reason. In this case, the three 8-
messages that will arrive later at IMP D cannot be delivered to
destination HOST(s) because they are out of order. The three single-packet
messages that should be delivered next, however, will never reach
destination IMP since there is no reassembly space available
A possible sequence of event that leads to a deadlock condition can
described as follows
Examples for Notation
event: A8 arrives -> all 8 packets of the 8-packet
from IMP A have arrived at IMP
event: C1 arrives -> a single packet message from IMP C
arrived at IMP D (and is treated as
request for buffer allocation
event: B8 complete -> the last packet of the 8-
message from IMP B has been
by its destination
event: A8 RFNM/ALL -> a RFNM with the piggy-backed
is sent to IMP
-3-
Network Working
Request for Comments: 626
# of Allocated # of Reassembly # of
Reassembly Buffers
Buffers in Use
Initially 24 0 0
1. A8 arrives 16 8 0
2. B8 arrives 8 16 0
3. C8 arrives 0 24 0
4. Al arrives 0 24 0
5. B1 arrives 0 24 0
6. C1 arrives 0 24 0
7. A8 complete 0 16 8
8. B8 complete 0 8 16
9. C8 complete 0 0 24
10. A8 RFNM/ALL 8 0 16
11. B8 RFNM/ALL 16 0 8
12. C8 RFNM/ALL 24 0 0
13. A8 arrives 16 8 0
14. B8 arrives 8 16 0
15. C8 arrives 0 24 0
16. - deadlock -
Note that an ALLOCATE for one of the single-packet messages A1, B1 and C1
only be returned to source IMP A, B, and C, respectively, after the
(with its piggy-backed ALLOCATE) for the previous 8-packet message has
sent. If these RFNMs are sent in sequence, i.e., without an ALLOCATE
one of the single-packet messages in between, the temporarily freed
storage (events (7) through (9) is implicitly allocated to the next multiple
packet messages (events (10) through (12) and not to any of the single-
messages. The next 8-packet messages are, however, out of order
cannot be delivered to their destination HOST(s).
Right now it looks as if such a lockup can only occur if the number
reassembly buffers is a multiple of eight. Indeed, the probability of a
lockup in this latter case is much higher. However, deadlocks can also
if the number of reassembly buffers is not a multiple of eight
Let us assume there are 26 instead of 24 reassembly buffers. Assume also that
due to alternate paths, line failure, or retransmission, the second packet
a 2-packet message arrives at IMP D before a single-packet message from the
same source IMP A. The single-packet message has a smaller sequence number
and must therefore be delivered to its destination HOST before the 2-
message. When the second packet of the 2-packet message arrives at IMP D
IMP realizes that only 2 of the allocated 8 buffers will be needed.
-4-
Network Working
Request for Comments: 626
6 buffers are returned to the pool of free reassembly buffers. If there
26-3x8=2 buffers in the pool before, the pool size is increased by 6 to 8
buffers. These 8 buffers, however, are just enough to send out
piggy-backed ALLOCATE. The single-packet message will therefore find the
of free reassembly buffers empty although the total number of
buffers is not a multiple of eight. The 2-packet message cannot be
to its destination HOST because it is out of order. Therefore the
condition we described before may occur again
We agree that the above mentioned sequence of events is unlikely to
(otherwise one would have observed it already). This is particularly
since the current maximum number of reassembly buffers (58) is much
than 24. Judging from past experience with computer systems and networks
however, we know that even very unlikely events have a tendency to occur in
long run. Also, the probability of this deadlock condition increases with
increasing traffic in the net. Therefore, it is certainly worthwhile
modify the IMPSYS in such a way that this deadlock cannot occur. It turns
that a minor modification already achieves the desired effect. Recall that
that described deadlock can only occur because single- and multiple-packet
messages use the same pool of reassembly buffers. If we set aside a
reassembly buffer (or one for each destination HOST) that can be used only by
single-packet messages this lockup condition due to message sequencing
occur
Another solution to this problem is, of course, to more the message
from the IMP to the HOST level. This does not mean that similar
problems cannot occur on the HOST level. Also, it is currently much
to resolve this problem by a slight modification of the IMPSYS rather
having to coordinate all the various HOSTs. Another alternative is
discontinue the use of multiple-packet messages. However, this also
much more drastic changes which require careful consideration
-5-
Network Working
Request for Comments: 626
1. Kahn, R. E. and W. R. Crowther, "Flow Control in a Resource-
Computer Network," IEEE Transactions on Communication, Volume COM-20,3
June 1972.
2. BBN Report No. 2717, "Interface Message Processors for the ARPA
Network," Quarterly Technical Report No. 4, January 1974.
3. Naylor, W., J. Wong, C. Kline, and J. Postel, "Regarding
Official ICP," RFC 143, NIC 6728.
4. Postel, J. B. "A Graph Model Analysis of Computer
Protocols," PhD dissertation, University of California, Los Angeles
5. BBN Report No. 2670. "Natural Communication with Computers IV,"
Progress Report No. 12, October 1973.
-6-
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
RFC documents can be found at I.E.T.F.
Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX
