Browse Prior Art Database

On a possible lockup condition in IMP subnet due to message sequencing (RFC0626)

IP.com Disclosure Number: IPCOM000003699D
Original Publication Date: 1974-Mar-14
Included in the Prior Art Database: 2000-Sep-13
Document File: 5 page(s) / 13K

Publishing Venue

Internet Society Requests For Comment (RFCs)

Related People

L. Kleinrock: AUTHOR [+2]

Abstract

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.)

This text was extracted from a ASCII Text document.
This is the abbreviated version, containing approximately 23% of the total text.

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 ...