Possible Deadlock in ICP (RFC0202)

Network Working Group Steve Wolfe Request for Comments: #202 UCLA-CCN NIC #7155 Jon Postel Categories: D UCLA-NMC References: Document #2 26 July 1971 Obsoletes: None

We have noticed a possible deadlock situation which may arise using the Initial Connection Protocol (ICP) specified in Document #2 (NIC #7101 in the Current Network Protocols Notebook NIC #7104).

If on both sides one RFC is issued and a "wait for match" is required before the second RFC is issued, it is possible that the first RFC’s will not match. In particular a deadlock will occur if both sides open their send or both sides open their receive sockets first.

Briefly the ICP is: <where the original uses a script lowercase letter with a single digit subscript we use the lower case letter followed by {digit} so that script-m-subscript-2 is printed m{2}>

Server User ------ ----

S1: Listen on socket L. U1: RTS(U, L, l{1})

S2: Wait for a match. U2: Wait for match.

S3: STR(L, U, s{1})

S4: Wait for allocation. U3: All(l{1}, m{1}, b{1})

S5: Send data S in s{1} bit U4: Receive data S in s{1} bytes as allowed by bit bytes. allocation m{1}, b{1}.

S6: CLS(L, U) U5: CLS(U, L)

S7: RTS(S, U+3, l{2}) U6: STR(U+3, S, s{2})

S8: STR(S+1, U+2, s{3}) U7: RTS(U+2, S+1, l{3})

"The labels here imply no ordering except that ordering required by the Host-Host Protocol. Note that steps S7 and S8 can be reversed as can U6 and U7. Also, notice that at any time after S2 the server could initiate steps S7 and S8 in parallel with steps S3 th...