RFC626 日本語訳

Network Working Group                                  L. Kleinrock  (UCLA-NMC)
Request for Comments:  626                             H. Opderbeck  (UCLA-NMC)
NIC #22161                                                             Mar 1974

クラインロック(UCLA-NMC)がコメントのために要求するワーキンググループL.をネットワークでつないでください: 626時間Opderbeck(UCLA-NMC)NIC#22161 1974年3月

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

留置所か行き詰まり状態がコンピュータ・システムかネットワークで起こることができる最も重大なシステム異常の1つです。 通信プロトコルは、これらの留置所の発生を避けるように非常に入念に設計されなければなりません。 それらの共通する特徴は単に見通されなかったか、またはプロトコルデザイナーで起こり過ぎそうにないのは考えられなかった珍しい状況で起こるということです。 (しかしながら、これらのデザイナーはしばしば量的にそのような見込みを評価する立場のものであるというわけではありません。)

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

アルパネットで現れた最もよく知られている留置所は再アセンブリ留置所[1]です。 また、Reference1で説明された店とフォワード留置所は、新しいIMPSYSで注意深くカーンの発見的教授法[1]を観測することによって、避けられました。 「私たちが知っているサブネットにおける最後の留置所が1973年12月21日に現れた、(クリスマスの留置所、」、) 状態が同時にすべてのサイトからスナップ測定メッセージを集めることによって火が付くのにもたらされたこの眠っている留置所。 スナップメッセージがそれらのために再アセンブリ格納を割り当てたther UCLA IMPに到着したとき、クリスマスの留置所は起こりました、そして、どんな再アセンブリブロックも無料ではありませんでした。 (再アセンブリブロックはメッセージへの1片のパケットを組み立て直し返す実際の過程で使用される格納です) [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].

行き詰まり状態はサブネットで観測されるだけではなく、より高い平らなプロトコルで観測もされました。 ICPの当初の設計には、例えば、数カ月の使用[3、4]の後にだけ発見された欠点がありました。 より最近、BBNはRSEXECサーバ(RSSER)プログラム[5]によるHOST状態情報の交換にかかわることにおける行き詰まり問題を報告しました。

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.

無行き詰まりの操作を保証する実用的な通信プロトコルを設計するのが可能でない限り、絶えずそれらのどんなそのような失敗にも、起こるのにおいて「非常にありそうもなく」見えても現在使用中のプロトコルをチェックするのは重大です。 私たちが私たちが知っている限り、まだ起こっていないIMPサブネットにおける可能な行き詰まり条件に関してコメントするこのRFCでは、どちらも、それは特定されていません。 私たちは、この問題が実際に起こるのを一度も見たことがありませんが、注意しないなら、それは将来、起こるかもしれません。 この可能な留置所状態は部分集合における、メッセージの配列のためです。

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.

再アセンブリ留置所の発生を避けるために、サブネットにおけるフロー制御メカニズムはいくつかの重要な方法で変更されました。 現在、同時にトランスミッションどんな組のソースと目的地IMPsの間で中であることができる4つのメッセージの限界があります。 古いIMPSYSからリンク取り扱いを取り除くことの結果、メッセージ配列メカニズムを紹介するのは必要になりました。

                                   -1-

-1-

Network Working Group				
Request for Comments:  626

コメントを求めるワーキンググループ要求をネットワークでつないでください: 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).

ソースIMPに入ったので、メッセージは同次で目的地をIMPに出ます。 (HOSTからホストへの基礎ではなく、IMPからIMPへのベースで配列することに注意してください。 同じ目的地IMPに取り付けられた2HOSTsが同じソース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.

一般に、メッセージの配列には、行き詰まり状態を導入する可能性があります。 この理由はたとえば、どんなメッセージ、(n+1)(故障しています(そして、したがって、目的地HOSTに渡すことができない))がリソースを使いきるかもしれないというメッセージも次に送らなければならないメッセージ(n)が必要であるということです。 したがって、メッセージ(n)は渡される順番に他のメッセージ(n+1)など) それを防ぐIMPがそれらの目的地HOST(s)に故障している目的地に達することができません。 この理由で、1つは、あまりに多くのリソース(例えば、バッファ)を不適切なメッセージに割り当てないように非常に慎重でなければなりません。

To avoid lockup conditions the current IMPSYS takes the following two
precautions:

留置所状態を避けるために、現在のIMPSYSは2つの注意を以下に払います:

	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.

1. いつもバッファ配分を求める要求はメッセージ番号の順にサービスです。 メッセージ(n)であるならメッセージ(n+1)のためにすなわち、'ALLOCATE'を全く返しません。(または、(n))がまだ受け取られて、修理されていないというメッセージのためのバッファ配分を求める要求。

	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.

2. それらが前のバッファ配分に対応して再送されなかったなら、目的地IMPに故障していた状態で到着するただ一つのパケットメッセージ(レギュラーと優先権)は受け入れられません。 これらのメッセージは、むしろ1つのバッファ(上の1に従って)の配分を求める要求として扱われて、次に、捨てられます。

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.

これらの2つの注意で、行き詰まり状態は起こるのが不可能であるように見えます。 しかしながら、すなわち、メッセージ配列に試みられない2番目のバッファ配分メカニズム、複数のパケットメッセージのためにRFNMで背負われる'ALLOCATE'があります。 便乗しているALLOCATEは連続して次のメッセージではなく、次の複数のパケットメッセージのためのバッファ配分を表します。 したがって、次のメッセージが連続して単一のパケットメッセージであるなら、事実上、便乗しているALLOCATEは不適切なメッセージにバッファを割り当てます。

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.

この状況がどう行き詰まり状態につながることができるかを見ましょう。 24の再アセンブリバッファの最大数が各IMPにあると仮定してください。

                                   -2-

-2-

Network Working Group
Request for Comments:  626

コメントを求めるワーキンググループ要求をネットワークでつないでください: 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.

IMPs A、B、およびCにIMP Dのすべての24の再アセンブリバッファが複数のパケットメッセージのこの伝達で使いきられるように、同じ目的地IMP Dに8パケットのメッセージを絶えず送らせてください。 現在なら、8パケットのメッセージのストリームでは、IMP Aは利用可能などんな再アセンブリバッファ領域もないので一般に、それが目的地IMP Dによって受け入れられないという単一のパケットメッセージを送ります。 (単一のパケットメッセージが3つの8パケットのメッセージの1つがHOSTに伝えられる予定である時たまたま到着するなら、無料の再アセンブリバッファがあるかもしれません。) したがって、単一のパケットメッセージはバッファ配分を求める要求として扱われるでしょう。 前の複数のパケットメッセージのRFNMを送る前にこの要求を修理しないでしょう。 しかしながら、このとき、便乗しているALLOCATEメカニズムですべての無料の再アセンブリバッファを既に次の複数のパケットメッセージに割り当てました。 配分要求を満たさせている単一のパケットメッセージのための唯一の機会は他の2つの8パケットのメッセージの1つから再アセンブリバッファをつかむことです。 この試みは、IMPの出来事のタイミングによるので、失敗しているかもしれません。 また、IMP BとIMP Cが彼らの同じ理由から調整できない8パケットの測定のストリームで単一のパケットメッセージを送るなら、行き詰まり状態は現れることができます。 それらが故障しているので、この場合、後でIMP Dに到着する3つの8パケットのメッセージはそれらの目的地HOST(s)に渡すことができません。 利用可能などんな再アセンブリスペースもないので、しかしながら、次に送られるべきである3つの単一のパケットメッセージは目的地IMPに決して達しないでしょう。

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

出来事: A8が到着する、IMP Aからの8パケットのメッセージのすべての8つのパケットが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)

出来事: C1が到着する、IMP Cからのただ一つのパケットメッセージがIMP Dに到着するようにする->。(そして、バッファ配分を求める要求として扱われます)

	event:  B8 complete ->		the last packet of the 8-packet
					message from IMP B has been received
					by its destination HOST

出来事: B8の完全な->はIMPからのBが目的地HOSTによって受け取られたという8パケットのメッセージの最後のパケットです。

	event:  A8 RFNM/ALL ->		a RFNM with the piggy-backed ALLOCATE
					is sent to IMP A

出来事: 便乗しているALLOCATEとすべての->a RFNMがIMP Aに送られるA8 RFNM/

                                   -3-

-3-

Network Working Group
Request for Comments:  626

コメントを求めるワーキンググループ要求をネットワークでつないでください: 626

		    # of Allocated	# of Reassembly		# of Free
		     Reassembly		   Buffers		Reassembly
		      Buffers              in Use		 Buffers

# 割り当てられることでは、自由なReassemblyバッファReassemblyのReassembly#の#、は使用中でありバッファをバッファリングします。

     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 -

初めは、24 0 0 1。 A8は到着します。16 8 0 2。 B8は到着します。8 16 0 3。 C8は到着します。0 24 0 4。 アルは到着します。0 24 0 5。 B1は到着します。0 24 0 6。 C1は到着します。0 24 0 7。 A8は0を完成します。16 8 8。 B8は0 8を完成します。16 9。 C8完全な0 0 24 10。 A8 RFNM/、すべての8 0、16 11 B8 RFNM/、すべての16、0 8、12 C8 RFNM/、すべての24、0 0、13 A8が到着する、16、8 0、14 B8は到着します。8 16 0 15。 C8は到着します。0 24 0 16。 - 行き詰まり、-

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

IMP A、Bの出典を明示するために単一のパケットメッセージのA1、B1、およびC1の1つのALLOCATEを返すことができるだけであるというメモとC、それぞれ、後に、前の8パケットのメッセージのためのRFNM(便乗しているALLOCATEと)を送りました。 それとなく次の複数のパケットメッセージに出来事(7)から(9)を割り当てます。すなわち、連続してこれらのRFNMsを送る間の単一のパケットメッセージの1つ、一時無料であることの再アセンブリ格納へのALLOCATE、((. 次の8パケットのメッセージはしかしながら、故障していて、それらの目的地HOST(s)に渡すことができないという単一のパケットメッセージのどれかではなく、(12)を通した出来事(10)。

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.

たった今、まるでそのような留置所が再アセンブリバッファの数が8の倍数である場合にだけ現れることができるかのように見えます。 本当に、この後者の場合における、留置所の確率ははるかに高いです。 しかしながら、また、行き詰まりは再アセンブリバッファの数が8の倍数でないなら起こることができます。

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

26が24の再アセンブリバッファの代わりにあると仮定しましょう。 また、2パケットのメッセージの2番目のパケットが同じソースIMP A.からの単一のパケットメッセージの前に代替パス、線の故障、または「再-トランスミッション」のためIMP Dに到着すると仮定してください。単一のパケットメッセージをよりわずかな一連番号を持って、したがって、2パケットのメッセージの前の目的地HOSTに渡さなければなりません。 2パケットのメッセージの2番目のパケットがIMP Dに到着するとき、IMPは、8つの割り当てられたバッファのうち2だけが必要であるとわかります。 したがって

                                   -4-

-4-

Network Working Group
Request for Comments:  626

コメントを求めるワーキンググループ要求をネットワークでつないでください: 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.

無料の再アセンブリバッファのプールに6つのバッファを返します。 プールの中に2つの26-3×8=バッファがあったなら、以前、プール・サイズは6〜8つのバッファによって増加させられます。 しかしながら、これらの8つのバッファが、別の便乗しているALLOCATEを出すためにただ十分です。 単一のパケットメッセージによって、再アセンブリバッファの総数は8の倍数ではありませんが、したがって、無料の再アセンブリバッファのプールが空であることがわかるでしょう。 それが故障しているので、2パケットのメッセージを目的地HOSTに渡すことができません。 したがって、私たちが以前説明した行き詰まり状態は再び現れるかもしれません。

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.

私たちは、出来事の上記の系列が起こりそうにないのに同意します(さもなければ、1つは既にそれを観測したでしょう)。 現在の最大数の再アセンブリバッファ(58)が24よりはるかに大きいので、これは特に本当です。 しかしながら、コンピュータ・システムとネットワークの過去の経験から判断すると、私たちは、非常にありそうもない出来事でさえ結局起こる傾向があるのを知っています。 また、この行き詰まり状態の確率は交通を増やすのにネットを増加させます。 したがって、確かに、この行き詰まりが起こることができないような方法でIMPSYSを変更する価値があります。 小さい方の変更が既に期待される効果を発揮すると判明します。 単一の、そして、複数のパケットのメッセージが再アセンブリバッファの同じプールを使用するのでその説明された行き詰まりが起こっただけであるはずであると思い出してください。 私たちが単一のパケットメッセージだけで使用できるただ一つの再アセンブリバッファ(または、各目的地HOSTあたり1つ)をかたわらに置くなら、メッセージ配列によるこの留置所状態は現れることができません。

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.

IMPからHOSTまでのメッセージ配列が平らにする以上にはこの問題の他の解決法がもちろんあります。 これは、同様の留置所問題がHOSTレベルに起こることができないことを意味しません。 また、IMPSYSのわずかな変更でこの問題をむしろ解決するのも現在、すべての様々なHOSTsを調整しなければならないよりはるかに簡単です。 別の代替手段は複数のパケットメッセージの使用を中止することです。 しかしながら、また、これは注意深い考慮を要するずっと多くの飛躍的な変化にかかわります。

                                   -5-

-5-

Network Working Group
Request for Comments:  626

コメントを求めるワーキンググループ要求をネットワークでつないでください: 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.

1. カーンとR.E.とW.R.クラウザー、「資源分割形計算機ネットワークにおけるフロー制御」、コミュニケーションにおけるIEEE取引、ボリュームCOM-20(1972年6月3日)。

2.  BBN Report No. 2717, "Interface Message Processors for the ARPA Computer
    Network," Quarterly Technical Report No. 4, January 1974.

2. BBNは1974年1月にNo.2717、「アルパコンピュータネットワークのためのインタフェース・メッセージ・プロセッサ」、四半期の技術報告書No.4を報告します。

3.  Naylor, W., J. Wong, C. Kline, and J. Postel, "Regarding Proffered
    Official ICP," RFC 143, NIC 6728.

3. ネーラーとW.とJ.ウォン、C.クラインとJ.ポステル、「提供された公式のICP」RFC143、NIC6728。

4.  Postel, J. B. "A Graph Model Analysis of Computer Communications
    Protocols," PhD dissertation, University of California, Los Angeles.

4. J. ポステル、B. 「コンピュータ通信規約のグラフモデル分析」、博士号論文、カリフォルニア大学ロサンゼルス校。

5.  BBN Report No. 2670.  "Natural Communication with Computers IV,"  Quarterly
    Progress Report No. 12, October 1973.

5. BBNはNo.2670を報告します。 「コンピュータIVとの自然なコミュニケーション」、四半期の経過報告書No.12、1973年10月。

                                   -6-

-6-