RFC632 日本語訳
0632 Throughput degradations for single packet messages. H. Opderbeck. May 1974. (Format: TXT=14563 bytes) (Status: UNKNOWN)
プログラムでの自動翻訳です。
英語原文
Network Working Group H. Opderbeck Request for Comments: #632 UCLA-NMC NIC # 30239 20 May 1974
Opderbeckがコメントのために要求するワーキンググループH.をネットワークでつないでください: #632 UCLA-NMC NIC#30239 1974年5月20日
Throughput Degradations for Single Packet Messages
ただ一つのパケットメッセージのためのスループット転落
The transmission of digitized speech over the ARPANET represents a new dimension in the use of packet switching systems. The throughput and delay requirements for this newly emerging application area are quite different from the throughput and delay requirements for interactive use or file transfers. In particular, we need to achieve a high throughput for small messages since long messages result in long source delays to fill the large buffers. Therefore we are currently studying the throughput limits for single-packet messages. We realize that up to now little attempt was made to optimize throughput for low delay traffic. It was nevertheless surprising for us to find out that the observed throughput for single-packet messages is in many cases only about one fourth of what one would expect. In what follows we are going to explain why this happens and what could be done to correct this situation.
アルパネットの上のデジタル化しているスピーチの送信はパケット交換システムの使用における新しい寸法を表します。この新たに現れているアプリケーション部のためのスループットと遅れ要件は対話的な使用かファイル転送のためのスループットと遅れ要件と全く異なっています。 特に、私たちは、大きいバッファをいっぱいにするのに長いメッセージが長いソース遅れをもたらすので小さいメッセージのための高生産性を達成する必要があります。 したがって、私たちは現在、単一のパケットメッセージのためのスループット限界を研究しています。 私たちは、これまで低い遅れ交通のためのスループットを最適化するのを試みをほとんどしなかったとわかります。 それにもかかわらず、私たちが、多くの場合、単一のパケットメッセージのための観測されたスループットがものが予想することのおよそ1/4にすぎないことを見つけるのは、驚くべきものでした。 私たちは、続くことでこれがなぜ起こるかを説明するつもりです、そして、何が、この状況を修正するために終わることができますか?
On April 1, 1974, we sent, using the IMP message generator, single- packet messages at the highest possible rate ("RFNM-driven") from the MOFFET-IMP to the SRI-IMP. There are two three-hop paths from MOFFET to SRI, one of them involving two 230.4 kbs circuits. Since there was hardly any interfering traffic we expected an average round-trip delay of not more than 100 msec. Assuming that there are, on an average, 3 messages in transmission between MOFFET and SRI and assuming a message length of about 1000 bits this should result in a throughout of more than 30 kbs. The observed through was, however, less than 8 kbs. A repetition of the experiment showed the same result. A more detailed analysis of the collected data revealed that an average number of 3.5 messages were simultaneously in transmission between MOFFET and SRI. The throughput degradation could therefore not have been due to interfering traffic between these two sites. Also the channel utilization for all channels that were involved in the transmission was less than 40 percent. The observed mean round-trip times between MOFFET and SRI, however, were about 500 msec. Since these large round-trip times were obviously not due to physical limitations, we studied the flow control mechanism for single-packet messages and were able to come up with an explanation for this undesirable behavior.
1974年4月1日に、私たちは発信しました、IMPメッセージジェネレータ(可能な限り高いMOFFET-IMPからSRI-IMPまでのレート(「RFNM駆動」の)におけるただ一つのパケットメッセージ)を使用して MOFFETからそれらの1つが意味ありげであるSRIまで2つの3ホップの経路がある、2、230.4個のkbsサーキット ほとんど少しの干渉交通もなかったので、私たちは100以上msecでない平均した往復の遅れを予想しました。 MOFFETとSRIの間には、平均に3つのメッセージがトランスミッションにあると仮定して、ビットがこれであると1000年頃のメッセージ長に仮定するのがあらゆる点での30以上kbsのaをもたらすべきです。 しかしながら、観測されて、突き抜けるのは、8未満kbsでした。 実験の反復は同じ結果を示しました。 集まっているデータの、より詳細な分析は、3.5のメッセージの平均した数が同時にトランスミッションMOFFETとSRIの間で中であったのを明らかにしました。 したがって、スループット退行はこれらの2つのサイトの間の交通に干渉するためであるはずがありませんでした。 また、トランスミッションにかかわったオール・チャンネルのためのチャンネル利用は40パーセント未満でした。 しかしながら、MOFFETとSRIの間の観測された意地悪な往復の回はおよそ500msecでした。 これらの大きい往復の回が明らかに当然でなかったので、私たちは、物理的な制限に、単一のパケットメッセージのためにフロー制御メカニズムを研究して、この好ましくない行動のための説明を思いつくことができました。
When a single-packet message arrives at the destination IMP out of order (i.e., the logically preceding message has not yet arrived there) it is not accepted by the destination IMP. It is rather treated as a request for the allocation of one reassembly buffer. The corresponding ALLOCATE
単一のパケットメッセージが目的地IMPに故障していた状態で到着するとき(すなわち、論理的に前のメッセージはまだそこに到着していません)、それは目的地IMPによって受け入れられません。 それはむしろ1つの再アセンブリバッファの配分を求める要求として扱われます。 対応するALLOCATE
Opderbeck [Page 1] RFC 632 Throughput Degradations for Single Packet Messages May 1974
単一のパケットメッセージ1974年5月のためのOpderbeck[1ページ]RFC632スループット転落
is then sent back to the source IMP only after the RFNM for the previous message has been processed. We therefore may have the following sequence of events:
そして、前のメッセージのためのRFNMが処理された後にだけソースIMPに送り返されます。 したがって、私たちには、出来事の以下の系列があるかもしれません:
1 MSG(i) sent from SOURCE-IMP (message i is sent from the source IMP to the destination IMP).
1 MSG(i)はSOURCE-IMPから発信しました(ソースIMPから目的地IMPにメッセージiを送ります)。
2 MSG(i+1) sent from SOURCE-IMP.
2 MSG(i+1)はSOURCE-IMPから発信しました。
3 MSG(i+1) arrives at DEST-IMP (due to an alternate path or a line error, message (i+1) arrives at the destination IMP out of order; it is treated as a request for one reassembly buffer allocation and then discarded).
3 MSG(i+1)はDEST-IMPに到着します(代替パスか線誤りのため、メッセージ(i+1)は目的地IMPに故障していた状態で到着します; それは、1つの再アセンブリバッファ配分を求める要求として扱われて、次に、捨てられます)。
4 MSG(i) arrives at DEST-IMP (message i arrives at the destination IMP; it is put on the proper HOST output queue).
4 MSG(i)はDEST-IMPに到着します(メッセージiは目的地IMPに到着します; それは適切なHOST出力キューに置かれます)。
5 RFNM(i) sent from DEST-IMP (after message i has been accepted by the destination HOST the RFNM is sent to the source IMP).
5 RFNM(i)はDEST-IMPから発信しました(目的地HOSTがメッセージiを受け入れた後にソースIMPにRFNMを送ります)。
6 ALL(i+1) sent from DEST-IMP (only after the RFNM for message i has been processed can the ALLOCATE for message i + 1 be sent).
すべて(i+1)がDEST-IMPから送った6、(メッセージiのためのRFNMを処理した後にだけメッセージi+1のためのALLOCATEを送ることができる、)
7 RFNM(i) arrives at SOURCE-IMP.
7 RFNM(i)はSOURCE-IMPに到着します。
8 ALL(i+1) arrives at SOURCE-IMP.
8 すべて、(i+1)はSOURCE-IMPに到着します。
9 MSG(i+1) arrives at DEST-IMP (now message i+1 is put on the proper HOST output queue.)
9 MSG(i+1)はDEST-IMPに到着します。(現在、メッセージi+1は適切なHOST出力キューに置かれます。)
10 RFNM(i+1) sent form DEST-IMP.
10 RFNM(i+1)はフォームDEST-IMPを送りました。
11 RFNM(i+1) arrives at SOURCE-IMP.
11 RFNM(i+1)はSOURCE-IMPに到着します。
Note that the round-trip time for message i+1 is the time interval between event 2 and event 11. Therefore the round-trip time for message i+1 is more than twice as large as it would have been if it had arrived in order, other conditions being unchanged. Therefore a line error will in many cases not only delay the message in error but also the next single-packet message if this message follows the preceding message within 125 msec, the error retransmission timeout interval. Also, a faster, alternate path to the destination IMP can actually slow down the transmission since it causes messages to arrive there out of order.
メッセージi+1のための往復の時間が出来事2と出来事11の時間間隔であることに注意してください。 したがって、メッセージi+1のための往復の時間は変わりがない整然とした状態で到着したかどうかということであっただろう2倍以上大きくて、他の状態です。 したがって、このメッセージが125msec(誤り再送タイムアウト間隔)の中で前のメッセージに従うと、多くの場合、線誤りは間違いメッセージだけではなく、次の単一のパケットメッセージも遅らせるでしょう。 また、そこに故障していた状態で到着するメッセージを引き起こすので、目的地IMPへの、より速くて、交互の経路は実際にトランスミッションを減速させることができます。
Opderbeck [Page 2] RFC 632 Throughput Degradations for Single Packet Messages May 1974
単一のパケットメッセージ1974年5月のためのOpderbeck[2ページ]RFC632スループット転落
This situation becomes even worse when we consider RFNM-driven single- packet message traffic. Table 1 shows a possible sequence of events. We again assume that message i+1 reaches the destination IMP before message i.
私たちがRFNM駆動のただ一つのパケットメッセージ交通を考えるとき、この状況はさらに悪くなります。 テーブル1は出来事の可能な系列を示しています。 私たちは、メッセージ私+1がメッセージiの前に目的地IMPに達すると再び思います。
SOURCE IMP DESTINATION IMP
ソース悪童目的地悪童
MSG(i) sent MSG(i+1) sent MSG(i+2) sent MSG(i+1) arr MSG(i+3) sent MSG(i) arr RFNM(i) sent ALL(i+1) sent MSG(i+2) arr MSG(i+3) arr RFNM(i) arr MSG(i+4) sent ALL(i+1) arr MSG(i+4) arr MSG(i+1) sent MSG(i+1) arr RFNM(i+1) sent RFNM(i+1) arr ALL(i+2) sent MSG(i+5) sent ALL(i+2) arr MSG(i+5) arr MSG(i+2) sent MSG(i+2) arr RFNM(i+2) sent RFNM(i+2) arr ALL(i+3) sent MSG(i+6) sent ALL(i+3) arr MSG(i+6) arr MSG(i+3) sent MSG(i+3) arr RFNM(i+3) sent RFNM(i+3) arr ALL(i+4) ent MSG(i+7) sent ALL(i+4) arr MSG(i+7) arr MSG(i+4) sent MSG(i+4) arr RFNM(i+4) sent RFNM(i+4) arr ALL(i+5) MSG(i+8) sent ALL(i+5) arr MSG(i+5) sent
送る..送る..送る..送る..送る..送る..送る..送る..送る..送る..送る..送る; 送る..送る..送る..送る..送る..送る..送る..送る..送る..送る
Table 1.
1を見送ってください。
Retransmission Pattern for the Current Flow Control Scheme
Retransmissionは現在のフロー制御計画のために型に基づいて作ります。
(Since the traffic is RFNM-driven, the arrival of RFNM i, i+1, ... is followed by the sending of message i+4, i+5, ...)
以来、交通はそうです。(RFNM iの到着、i+1、RFNMが駆動であり、メッセージi+4の発信は…のあとに続いています、i+5…、)
Opderbeck [Page 3] RFC 632 Throughput Degradations for Single Packet Messages May 1974
単一のパケットメッセージ1974年5月のためのOpderbeck[3ページ]RFC632スループット転落
The most interesting fact about this sequence of events is that the arrival of message i+1 before message i at the destination IMP causes not only messages i+1 but all future messages to be retransmitted-- though we do not assume that any of the future messages arrive out of order. The table also shows that the round-trip times for message i+4 and all future messages is more than four times as large as it would be without these undesirable retransmissions. It is also noteworthy that, once this retransmission pattern has established itself, there is almost no way the system can recover from this condition other than interrupting the input stream at the source IMP. A single arrival out of order of any of the later user or control messages, for instance, will not change this retransmission pattern. The normal flow of single-packet messages will only reestablish itself if, for example, message i+4, i+5, and i+6 are simultaneously delayed for several hundred milliseconds such that messages i+1, i+2, and i+3 can be retransmitted in the meantime. The probability of occurrence of such an event is, however, extremely small. Therefore one can consider the system as being trapped in this undesirable retransmission condition. The "normal" flow of messages, on the other hand, represents only the transient behavior of the system since there is always a finite probability that two message arrive out of order due to transmission errors.
出来事のこの系列に関する最もおもしろい事実は私たちが、将来のメッセージのどれかが故障していた状態で到着すると思いませんが、目的地IMPのメッセージiの前のメッセージi+1の到着がメッセージi+1だけではなく、すべての再送されるべき将来のメッセージも引き起こすということです。 また、テーブルは、メッセージi+4とすべての将来のメッセージのための往復の回がそれがこれらの望ましくない「再-トランスミッション」なしであるだろうより4倍以上大きいのを示します。 また、この「再-トランスミッション」パターンがいったん定着するとシステムがソースIMPで入力ストリームを中断するのを除いたこの状態から回収されることができる方法が全くほとんどないのも、注目に値します。 例えば、後のユーザかコントロールメッセージのいずれでも不適切なただ一つの到着はこの「再-トランスミッション」パターンを変えないでしょう。 例えば、メッセージi+4、i+5、およびi+6が同時に差し当たりメッセージi+1、i+2、およびi+3を再送できるように数100ミリセカンドと同じくらい遅らせられる場合にだけ、単一のパケットメッセージの正常な流れはそれ自体を復職させるでしょう。 しかしながら、そのような出来事の発生可能性は非常にわずかです。 したがって、人は、システムがこの望ましくない「再-トランスミッション」状態で捕らえることにされるのであるとみなすことができます。 2メッセージが伝送エラーで故障していた状態で到着するという有限確率がいつもあるので、他方では、メッセージの「正常な」流れはシステムの遷移挙動だけを表します。
As mentioned before, the system can only recover from this throughput (and delay) degradation if the input stream of single-packet messages is interrupted. In case of speech transmission, however, this might not occur for a long time. Therefore speech transmission systems would in many cases have to work with only one fourth of the expected single- packet bandwidth. Since this is clearly an unacceptable condition we looked for a modification of the current flow control scheme which corrects this situation. In what follows we describe two methods that could be used to avoid the undesirable retransmission of messages.
以前言及されるように、単一のパケットメッセージに関する入力ストリームが中断される場合にだけ、システムはこのスループット(延着する)退行から回収されることができます。 しかしながら、スピーチ送信の場合には、これは長い間、起こらないかもしれません。 したがって、多くの場合、スピーチ伝動装置は1/4だけで予想された単一のパケット帯域幅を働かせなければならないでしょう。 これが明確に容認できない状態であるので、私たちはこの状況を修正する現在のフロー制御計画の変更を探しました。 続くことでは、私たちはメッセージの望ましくない「再-トランスミッション」を避けるのに使用できた2つの方法を説明しますか?
Recall that a single-packet message is rejected at destination IMP and later retransmitted if the RFNM for the preceding message has not yet been sent to the source IMP. This is mainly done to prevent the occurrence of reassembly lockup conditions [1]. Therefore the problem cannot be solved by simply accepting all single-packet messages without additional measures to prevent deadlocks. This could lead to a reassembly lockup if a large number of single-packet messages from several source IMPs arrives at their common destination IMP out of order. In this case the destination IMP might not be able to accept those messages that are in order because of the lack of reassembly buffers. As a result the system is deadlocked. Any solution of the throughput degradation problem must guarantee that all messages that arrive in order can be accepted by the destination IMP.
前のメッセージのためのRFNMがまだソースIMPに送られないなら、単一のパケットメッセージが目的地IMPで拒絶されて、後で再送されたと思い出してください。 再アセンブリ留置所状態[1]の発生を防ぐために主にこれをします。 したがって、行き詰まりを防ぐ追加措置なしですべての単一のパケットメッセージを単に受け入れることによって、問題を解決できません。 数個のソースIMPsからの多くの単一のパケットメッセージが彼らの一般的な目的地IMPに故障していた状態で到着するなら、これは再アセンブリ留置所に通じるかもしれません。 この場合、目的地IMPはそれらの再アセンブリバッファの不足のために整然としているメッセージを受け入れることができないかもしれません。 システムがあるという結果が行き詰まったので。 スループット退行問題のどんな解決も、目的地IMPが整然とした状態で到着するすべてのメッセージを受け入れることができるのを保証しなければなりません。
Opderbeck [Page 4] RFC 632 Throughput Degradations for Single Packet Messages May 1974
単一のパケットメッセージ1974年5月のためのOpderbeck[4ページ]RFC632スループット転落
One way to achieve this goal is to reject single-packet messages that arrive out of order only if the buffer requirement(s) of the preceding messages(s) is not known. In the previous examples we have seen that the destination IMP continuously rejected messages although it knew the buffer requirements for the messages that had to be delivered first. As the buffer requirements become known, the necessary number of buffers can be set aside and future single-packet messages can be accepted without the danger of deadlock. Therefore the undesirable retransmission pattern cannot establish itself. Table 2 shows the sequence of events for this policy if message i+1 arrives before message i at the destination IMP.
この目標を達成する1つの方法は前のメッセージのバッファ要件が知られていない場合にだけ故障していた状態で到着する単一のパケットメッセージを拒絶することです。 前の例では、私たちは、最初に送られなければならなかったメッセージのためのバッファ要件を知っていましたが、目的地IMPが絶え間なくメッセージを拒絶したのを見ました。 バッファ要件が知られるようになるとき、バッファの必要な数をかたわらに置くことができます、そして、行き詰まりという危険なしで将来の単一のパケットメッセージを受け入れることができます。 したがって、望ましくない「再-トランスミッション」パターンは定着できません。 メッセージi+1がメッセージiの前に目的地IMPに到着するなら、テーブル2はこの方針のために出来事の系列を示しています。
SOURCE IMP DESTINATION IMP
ソース悪童目的地悪童
MSG (i) sent MSG(i+1) sent MSG(i+2) sent MSG(i+1) arr. (rejected) MSG(i+3) sent MSG(i) arr. (HOST output) RFNM(i) sent ALL (i+1) sent MSG(i+2) arr (stored) MSG(i+3) arr (stored) RFNM(i) arr MSG(i+4) sent ALL(i+1) arr MSG(i+4) arr (stored) MSG(i+1) sent MSG(i+1) arr (HOST output) RFNM(i+1) sent RFNM(i+1) arr RFNM(i+2) sent MSG(i+5) sent RFNM(i+3) sent RFNM(i+4) sent
MSG(i)はMSG(i+1)の送られたMSG(i+2)の送られたMSG(i+1)arrを送りました。 (拒絶されます) MSG(i+3)はMSG(i) arrを送りました。 (HOST出力) 送る..送る..格納..格納..送る..格納..送る..出力..送る..送る..送る..送る..送る
Table 2.
2を見送ってください。
Sequence of Events for Modified Flow Control Scheme
規制流量コントロール計画のための出来事の系列
Note that in this modified scheme only one message, message i+1, is retransmitted. In view of the fact that the IMPs have plenty of reassembly buffer space it is, however, desirable to avoid this one retransmission, too. This is particularly important for the transmission of speech which depends on a steady flow of data and will be disrupted by a sudden large delay. Therefore we suggest a second method to solve the throughput degradation problem which, in most cases, will not require any retransmissions.
この変更された計画だけでは、1つのメッセージ(メッセージi+1)が再送されることに注意してください。 しかしながら、また、IMPsには多くの再アセンブリバッファ領域があるという事実から見て、この1個の「再-トランスミッション」を避けるのは望ましいです。 これは、データの定流によるスピーチの送信には特に重要であり、突然の大きい遅れによって混乱させられるでしょう。 したがって、私たちは多くの場合、少しの「再-トランスミッション」も必要としないスループット退行問題を解決する2番目の方法を勧めます。
Opderbeck [Page 5] RFC 632 Throughput Degradations for Single Packet Messages May 1974
単一のパケットメッセージ1974年5月のためのOpderbeck[5ページ]RFC632スループット転落
Suppose all single-packet messages are initially accepted (or stored). Currently single-packet messages that arrive out of order are rejected because of the possibility of a deadlock. But let us take a closer look at the situation where all single-packet messages are accepted (or stored) such that there is no reassembly buffer available for messages that have to be delivered to their HOST(s) next. This is not really a lockup condition because the source IMPs keep a copy of all single- packet messages for which a RFNM has not yet been received. Therefore any single-packet message, which arrived out of order but was accepted by the destination IMP nevertheless, can be deleted later without the message being lost. The destination IMP only has to send an ALLOCATE for each deleted single-packet message to the corresponding source IMP when reassembly buffer space is available. This can also be considered as deferred rejection. But now a retransmission is only necessary if the destination IMP is really running out of reassembly buffers. In this case, the physical limitations of the system are reached and we cannot hope to gain large throughput increases by means of protocol changes.
すべての単一のパケットメッセージが初めは受け入れられる(または、格納される)と仮定してください。 現在の、故障していた状態で到着する単一のパケットメッセージは行き詰まりの可能性で拒絶されます。 しかし、どんな再アセンブリそれらのHOST(s)に渡されなければならないメッセージに利用可能な次でないバッファもすべての単一のパケットメッセージを受け入れるので(または、格納されます)あるところで状況への、より近い一見を取りましょう。 ソースIMPsがRFNMがまだ受け取られていないすべてのただ一つのパケットメッセージの写しを取っておくので、これは本当に留置所状態ではありません。 したがって、後で失われているメッセージなしでどんな単一のパケットメッセージ(故障していた状態で到着しましたがそれにもかかわらず、目的地IMPが受け入れられた)も削除できます。 再アセンブリバッファ領域が利用可能であるときに、目的地IMPだけがそれぞれの削除された単一のパケットメッセージのために対応するソースIMPにALLOCATEを送らなければなりません。 また、延期された拒絶であるとこれをみなすことができます。 しかし、目的地IMPが本当に再アセンブリバッファを使い果たす場合にだけ、現在、「再-トランスミッション」が必要です。 この場合、システムの物理的な限界に達しています、そして、私たちはプロトコル変化によって大きいスループット増加を獲得することを望むことができません。
It is our intention to pursue this issue with the IMP development group at BBN in the future. They agree that the two solutions we suggest would improve the situation. However, they can think of alternative solutions.
それは将来BBNのIMP開発グループのこの問題を追求するという私たちの意志です。 彼らは、私たちが勧める2つの解決策が状況を改善するのに同意します。 しかしながら、彼らは代替の解決策を考えることができます。
I acknowledge the help of Bill Naylor and Joe Katz in performing the experiments which led to the discovery of the throughput degradation.
私はスループット退行の発見につながった実験を行う際にビル・ネーラーとジョー・キャッツの助けを承諾します。
References:
参照:
[1] Kleinrock, L. and H. Opderbeck. "On a Possible Lockup condition in the IMP Subnet Due to Message Sequencing", RFC #626.
[1] クラインロック、L.、およびH.Opderbeck。 「Message SequencingへのIMP Subnet DueのPossible Lockup条件」、RFC#626。
[ This RFC was put into machine readable form for entry ] [ into the online RFC archives by Alex McKenzie with ] [ support from GTE, formerly BBN Corp. 11/99 ]
[このRFCはエントリーのためのマシンに入れられた読み込み可能なフォームでした]、[アレックス・マッケンジーによるオンラインRFCアーカイブ、][GTEからのサポート、以前BBN社11/99]
Opderbeck [Page 6]
Opderbeck[6ページ]
一覧
スポンサーリンク