diff options
Diffstat (limited to 'doc/rfc/rfc626.txt')
| -rw-r--r-- | doc/rfc/rfc626.txt | 334 |
1 files changed, 334 insertions, 0 deletions
diff --git a/doc/rfc/rfc626.txt b/doc/rfc/rfc626.txt new file mode 100644 index 0000000..7f5b6ea --- /dev/null +++ b/doc/rfc/rfc626.txt @@ -0,0 +1,334 @@ + + + +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 the + IMP Subnet Due to Message Sequencing" + + +Lockup or deadlock conditions are one of the most serious system malfunctions +that can occur in a computer system or network. Communication protocols have +to be designed very carefully to avoid the occurrence of these lockups. Their +common characteristic is that they occur only under unusual circumstances which +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 evaluate +such likelihoods quantitatively.) + +The best known lockup that has occurred in the ARPANET is the reassembly +lockup [1]. The store-and-forward lockup, also described in Reference 1, has +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 light +by collecting snapshot measurement messages from all sites simultaneously. +The Christmas lockup happened when snapshot messages arrived at ther UCLA IMP +which had allocated reassembly storage for them and no reassembly blocks were +free. (A reassembly block is a piece of storage used in the actual process +of reassembling packets back into messages) [2]. + +Deadlock conditions have not only been observed in the subnet but also in +higher level protocols. The original design of the ICP, for example, had a +flaw that was discovered only after a few months of use [3,4]. More recently +BBN reported a deadlock problem involving the exchange of HOST status +information by the RSEXEC server (RSSER) programs [5]. + +As long as it is not possible to design practical communication protocols +which guarantee deadlock-free operation it is vital to continually check those +protocols that are currently in use for any such failures - even if they appear +"very unlikely" to occur. In this RFC we comment on a possible deadlock +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. This +possible lockup condition is due to the sequencing of messages in the subset. + +To avoid the occurrence of reassembly lockup, the flow control mechanism in +the subnet was modified in some significant ways. Currently there is a limit +of four messages that can simultaneously be in transmission between any pair of +source and destination IMPs. As a result of removing the link-handling from +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 source +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 deadlock +conditions. The reason for this is that any message, say message (n+1), which +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 delivered +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 very +careful not to allocate too many resources (e.g., buffers) to messages that +are out of order. + +To avoid lockup conditions the current IMPSYS takes the following two +precautions: + + 1. Requests for buffer allocation are always services in order + of message number; i.e., no 'ALLOCATE' is returned for + message (n+1) if message (n) (or a request for buffer + allocation for message (n)) has not yet been received and + serviced. + + 2. Single packet messages (regular and priority) that arrive + at the destination IMP out of order are not accepted unless + they were retransmitted in response to a previous buffer + allocation. These messages are treated rather as a request + for the allocation of one buffer (according to 1 above) and + then discarded. + +With these two precautions a deadlock condition appears to be impossible to +occur. However, there is a second buffer allocation mechanism that is not +tried to the message sequencing, namely the 'ALLOCATE' that is piggy-backed +on the RFNM for a multiple-packet message. The piggy-backed ALLOCATE +represents a buffer allocation for the next multiple-packet message, and NOT +for the next message in sequence. Thus, if the next message in sequence is +a single-packet message, the piggy-backed ALLOCATE in effect allocates +buffers to a message that is out of order. + +Let us see how this situation can lead to a deadlock condition. Assume there +is a maximum number of 24 reassembly buffers in each IMP. + + + -2- + + +Network Working Group +Request for Comments: 626 + + + +Let IMPs A, B, and C continually transmit 8-packet messages to the same +destination IMP D such that all 24 reassembly buffers in IMP D are used up by +this transmission of multiple packet messages. If now, in the stream of +8-packet messages, IMP A sends a single-packet message it will generally not +be accepted by destination IMP D since there is no reassembly buffer space +available. (There may be a free reassembly buffer if the single-packet message +happens to arrive during the time one of the three 8-packet messages is being +transmitted to its HOST). The single-packet message will therefore be treated +as a request for buffer allocation. This request will not be serviced before +the RFNM of the previous multiple-packet message is sent. At this time, +however, all the free reassembly buffers have already been allocated to the +next multiple-packet message via the piggy-backed ALLOCATE mechanism. The +only chance for the single-packet message to get its allocation request +satisfied is to grab a reassembly buffer from one of the other two 8-packet +messages. This attempt may be unsuccessful because it depends on the timing +of events in the IMP. A deadlock condition can occur if IMP B and IMP C +also send a single-packet message in their stream of 8-packet measures which +cannot be serviced for the same reason. In this case, the three 8-packet +messages that will arrive later at IMP D cannot be delivered to their +destination HOST(s) because they are out of order. The three single-packet +messages that should be delivered next, however, will never reach the +destination IMP since there is no reassembly space available. + +A possible sequence of event that leads to a deadlock condition can be +described as follows: + + Examples for Notation: + + event: A8 arrives -> all 8 packets of the 8-packet message + from IMP A have arrived at IMP D + + event: C1 arrives -> a single packet message from IMP C has + arrived at IMP D (and is treated as a + request for buffer allocation) + + event: B8 complete -> the last packet of the 8-packet + message from IMP B has been received + by its destination HOST + + event: A8 RFNM/ALL -> a RFNM with the piggy-backed ALLOCATE + is sent to IMP A + + + + + -3- + + +Network Working Group +Request for Comments: 626 + + + + + # of Allocated # of Reassembly # of Free + Reassembly Buffers Reassembly + Buffers in Use Buffers + + 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 can +only be returned to source IMP A, B, and C, respectively, after the RFNM +(with its piggy-backed ALLOCATE) for the previous 8-packet message has been +sent. If these RFNMs are sent in sequence, i.e., without an ALLOCATE for +one of the single-packet messages in between, the temporarily freed reassembly +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-packet +messages. The next 8-packet messages are, however, out of order and +cannot be delivered to their destination HOST(s). + +Right now it looks as if such a lockup can only occur if the number of +reassembly buffers is a multiple of eight. Indeed, the probability of a +lockup in this latter case is much higher. However, deadlocks can also occur +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 of +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-packet +message. When the second packet of the 2-packet message arrives at IMP D the +IMP realizes that only 2 of the allocated 8 buffers will be needed. Therefore + + + + -4- + + +Network Working Group +Request for Comments: 626 + + + +6 buffers are returned to the pool of free reassembly buffers. If there were +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 another +piggy-backed ALLOCATE. The single-packet message will therefore find the pool +of free reassembly buffers empty although the total number of reassembly +buffers is not a multiple of eight. The 2-packet message cannot be delivered +to its destination HOST because it is out of order. Therefore the deadlock +condition we described before may occur again. + +We agree that the above mentioned sequence of events is unlikely to occur +(otherwise one would have observed it already). This is particularly true +since the current maximum number of reassembly buffers (58) is much larger +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 the +long run. Also, the probability of this deadlock condition increases with +increasing traffic in the net. Therefore, it is certainly worthwhile to +modify the IMPSYS in such a way that this deadlock cannot occur. It turns out +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 single +reassembly buffer (or one for each destination HOST) that can be used only by +single-packet messages this lockup condition due to message sequencing cannot +occur. + +Another solution to this problem is, of course, to more the message sequencing +from the IMP to the HOST level. This does not mean that similar lockup +problems cannot occur on the HOST level. Also, it is currently much easier +to resolve this problem by a slight modification of the IMPSYS rather than +having to coordinate all the various HOSTs. Another alternative is to +discontinue the use of multiple-packet messages. However, this also involves +much more drastic changes which require careful consideration. + + + + + + + + + + + + + + + + + -5- + + +Network Working Group +Request for Comments: 626 + + + + + REFERENCES + + + +1. Kahn, R. E. and W. R. Crowther, "Flow Control in a Resource-Sharing + Computer Network," IEEE Transactions on Communication, Volume COM-20,3 + June 1972. + +2. BBN Report No. 2717, "Interface Message Processors for the ARPA Computer + Network," Quarterly Technical Report No. 4, January 1974. + +3. Naylor, W., J. Wong, C. Kline, and J. Postel, "Regarding Proffered + Official ICP," RFC 143, NIC 6728. + +4. Postel, J. B. "A Graph Model Analysis of Computer Communications + Protocols," PhD dissertation, University of California, Los Angeles. + +5. BBN Report No. 2670. "Natural Communication with Computers IV," Quarterly + Progress Report No. 12, October 1973. + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + -6- |