RFC970 日本語訳

Network Working Group                                         John Nagle
Request for Comments: 970                                 FACC Palo Alto
                                                           December 1985

コメントを求めるワーキンググループジョンネーグルRequestをネットワークでつないでください: 970 FACCパロアルト1985年12月

                On Packet Switches With Infinite Storage

無限の格納があるパケット交換機に関して

Status of this Memo

このMemoの状態

   The purpose of this RFC is to focus discussion on particular problems
   in the ARPA-Internet and possible methods of solution.  No proposed
   solutions in this document are intended as standards for the
   ARPA-Internet at this time.  Rather, it is hoped that a general
   consensus will emerge as to the appropriate solution to such
   problems, leading eventually to the adoption of standards.
   Distribution of this memo is unlimited.

このRFCの目的はARPA-インターネットの特定の問題と解決策の可能な方法に議論の焦点を合わせることです。 提案された解決策は全くこのとき、ARPA-インターネットの規格として本書では意図しません。 むしろ、全体的な合意がそのような問題の適切な解決に関して現れることが望まれています、結局規格の採用に通じて。 このメモの分配は無制限です。

Abstract

要約

   Most prior work on congestion in datagram systems focuses on buffer
   management.  We find it illuminating to consider the case of a packet
   switch with infinite storage.  Such a packet switch can never run out
   of buffers. It can, however, still become congested.  The meaning of
   congestion in an infinite-storage system is explored.  We demonstrate
   the unexpected result that a datagram network with infinite storage,
   first-in-first-out queuing, at least two packet switches, and a
   finite packet lifetime will, under overload, drop all packets.  By
   attacking the problem of congestion for the infinite-storage case, we
   discover new solutions applicable to switches with finite storage.

データグラムシステムにおける混雑に対するほとんどの先の仕事がバッファ管理に焦点を合わせます。 私たちは、無限の格納があるパケット交換機に関するケースを考えるのが啓発的であることがわかりました。 そのようなパケット交換機はバッファを決して使い果たすことができません。 しかしながら、それはまだ混雑するようになることができます。 無限の格納システムにおける混雑の意味は探られます。 私たちは無限の格納があるデータグラム・ネットワーク、ファーストインファーストアウトの列を作り、少なくとも2個のパケット交換機、および有限パケット生存期間がオーバーロードの下ですべてのパケットを落とすという予期していなかった結果を示します。 無限の格納ケースのための混雑の問題を攻撃することによって、私たちは有限格納があるスイッチに適切な新しい解決策を発見します。

Introduction

序論

   Packet switching was first introduced in an era when computer data
   storage was several orders of magnitude more expensive than it is
   today.  Strenuous efforts were made in the early days to build packet
   switches with the absolute minimum of storage required for operation.
   The problem of congestion control was generally considered to be one
   of avoiding buffer exhaustion in the packet switches.  We take a
   different view here.  We choose to begin our analysis by assuming the
   availablity of infinite memory. This forces us to look at congestion
   from a fresh perspective.  We no longer worry about when to block or
   which packets to discard; instead, we must think about how we want
   the system to perform.

最初に、コンピュータデータ保存が今日のそれより数桁高価であった時代でパケット交換を導入しました。 初期で格納の絶対最小値が操作に必要である状態でパケット交換機を組立てるのを多大な努力をしました。 一般に、輻輳制御の問題はパケット交換機でバッファ疲労困憊を避けるものであると考えられました。 私たちはここに違った見解を抱きます。 私たちは、無限のメモリのavailablityを仮定することによって私たちの分析を始めるのを選びます。 これによって、私たちは新鮮な見解から混雑をやむを得ず見ます。 私たちはもうブロックへのいつかそれともどのパケットを捨てたらよいかを心配しません。 代わりに、システムが働いて欲しいとどう思うかについて私たちは考えなければなりません。

   Pure datagram systems are especially prone to congestion problems.
   The blocking mechanisms provided by virtual circuit systems are
   absent.  No fully effective solutions to congestion in pure datagram
   systems are known.  Most existing datagram systems behave badly under
   overload.  We will show that substantial progress can be made on the

純粋なデータグラムシステムは特に混雑問題の傾向があります。仮想の循環方式によって提供されたブロッキングメカニズムは欠けています。 純粋なデータグラムシステムにおける混雑のどんな完全に効果的な解決策も知られていません。 ほとんどの既存のデータグラムシステムがオーバーロードの下でひどく反応します。 私たちは、具体的進展をオンにすることができるのを示すつもりです。

Nagle                                                           [Page 1]

ネーグル[1ページ]

RFC 970                                                    December 1985
On Packet Switches With Infinite Storage

無限の格納があるパケット交換機の上のRFC970 1985年12月

   congestion control problem even for pure datagram systems when the
   problem is defined as determining the order of packet transmission,
   rather than the allocation of buffer space.

問題であるときに、純粋なデータグラムシステムさえのための混雑制御の問題はバッファ領域の配分よりむしろパケット伝送の順番を決定すると定義されます。

A Packet Switch with Infinite Storage

無限の格納があるパケット交換機

   Let us begin by describing a simple packet switch with infinite
   storage.  A switch has incoming and outgoing links.  Each link has a
   fixed data transfer rate.  Not all links need have the same data
   rate. Packets arrive on incoming links and are immediately assigned
   an outgoing link by some routing mechanism not examined here.  Each
   outgoing link has a queue.  Packets are removed from that queue and
   sent on its outgoing link at the data rate for that link.  Initially,
   we will assume that queues are managed in a first in, first out
   manner.

無限の格納がある簡単なパケット交換機について説明することによって、始まりましょう。 スイッチには、送受信のリンクがあります。 各リンクには、固定データ転送速度があります。 リンクが必要とするというわけではないすべてが同じデータ信号速度を持っています。 パケットは入って来るリンクの上に到着して、すぐに、ここで調べられなかった何らかのルーティングメカニズムによって出発しているリンクを割り当てられます。 それぞれの出発しているリンクには、待ち行列があります。 そのリンクのためにデータ信号速度でパケットをその待ち行列から移して、出発しているリンクに送ります。 初めは、私たちは、待ち行列が最初に、方法から最初のコネで管理されると思うつもりです。

   We assume that packets have a finite lifetime.  In the DoD IP
   protocol, packets have a time-to-live field, which is the number of
   seconds remaining until the packet must be discarded as
   uninteresting. As the packet travels through the network, this field
   is decremented; if it becomes zero, the packet must be discarded.
   The initial value for this field is fixed; in the DoD IP protocol,
   this value is by default 15.

私たちは、パケットには有限寿命があると思います。 DoD IPプロトコルでは、パケットは生きる時間分野を持っています。(それは、おもしろくないとしてパケットを捨てなければならないまで残っている秒数です)。 パケットがネットワークを通って移動するのに従って、この分野は減少します。 ゼロになるなら、パケットを捨てなければなりません。 この分野への初期の値は固定されています。 DoD IPには、15は、デフォルトで議定書を作って、ありますこれが、評価する。

   The time-to-live mechanism prevents queues from growing without
   bound; when the queues become sufficiently long, packets will time
   out before being sent.  This places an upper bound on the total size
   of all queues; this bound is determined by the total data rate for
   all incoming links and the upper limit on the time-to-live.

生きる時間メカニズムは、待ち行列がバウンドなしで成長するのを防ぎます。 待ち行列が十分長くなると、パケットは送る前のタイムアウトがなるでしょう。 これはすべての待ち行列の総サイズに上限を置きます。 このバウンドは生きる時にすべての入って来るリンクと上限のために総データ信号速度で決定します。

   However, this does not eliminate congestion.  Let us see why.

しかしながら、これは混雑を排除しません。 理由を見ましょう。

   Consider a simple node, with one incoming link and one outgoing link.
   Assume that the packet arrival rate at a node exceeds the departure
   rate.  The queue length for the outgoing link will then grow until
   the transit time through the queue exceeds the time-to-live of the
   incoming packets.  At this point, as the process serving the outgoing
   link removes packets from the queue, it will sometimes find a packet
   whose time-to-live field has been decremented to zero.  In such a
   case, it will discard that packet and will try again with the next
   packet on the queue.  Packets with nonzero time-to-live fields will
   be transmitted on the outgoing link.

1個の入って来るリンクと1個の出発しているリンクがある簡単なノードを考えてください。 ノードにおけるパケット到着率が出発率を超えていると仮定してください。 そして、待ち行列によるトランジット時間が入って来るパケットについて生きる時間を超えるまで、出発しているリンクへの待ち行列の長さは成長するでしょう。 ここに、出発しているリンクに役立つ過程が待ち行列からパケットを取り除くとき、それは時々生きる時間分野がゼロまで減少したパケットを見つけるでしょう。 このような場合には、それは、そのパケットを捨てて、待ち行列の次のパケットで再試行するでしょう。 非零生きる時間分野があるパケットは出発しているリンクの上に伝えられるでしょう。

   The packets that do get transmitted have nonzero time-to- live
   values. But once the steady state under overload has been reached,
   these values will be small, since the packet will have been on the
   queue for slightly less than the maximum time-to-live.  In fact, if

伝えられるパケットは非零時間からライブ値を持っています。 しかし、オーバーロードの下における定常状態にいったん達すると、これらの値は小さくなるでしょう、生きる最大よりわずかに少ない時間の待ち行列にパケットがあってしまうだろうので。 事実上

Nagle                                                           [Page 2]

ネーグル[2ページ]

RFC 970                                                    December 1985
On Packet Switches With Infinite Storage

無限の格納があるパケット交換機の上のRFC970 1985年12月

   the departure rate is greater than one per time-to-live unit, the
   time-to-live of any forwarded packet will be exactly one.  This
   follows from the observation that if more than one packet is sent per
   time-to-live unit, consecutive packets on the queue will have
   time-to-live values that differ by no more than 1.  Thus, as the
   component of the packet switch that removes packets from the queue
   and either sends them or discards them as expired operates, it will
   either find packets with negative or zero time to live values (which
   it will discard) or packets with values of 1, which it will send.

出発率が生きる時間単位あたり1つ以上である、いずれも生きるために調節された進められたパケットはちょうど1になるでしょう。 これは生きる時間単位単位で1つ以上のパケットを送ると、待ち行列の連続したパケットには1時までに異なる生きる時間値があるという観測から続きます。 したがって、待ち行列からパケットを取り除いて、それらを送るか、または吐き出されるようにそれらを捨てるパケット交換機の部品が作動するとき、それは、ライブ値(それが捨てる)かそれが送る1の値があるパケットに否定的でパケットを見つけるか、または時間のゼロを合わせるでしょう。

   So, clearly enough, at the next node of the packet switching system,
   the arriving packets will all have time-to-live values of 1.  Since
   we always decrement the time-to-live value by at least 1 in each
   node, to guarantee that the time-to-live value decreases as the
   packet travels through the network, we will in this case decrement it
   to zero for each incoming packet and will then discard that packet.

それで、十分明確に、パケット交換システムの次のノードでは、到着パケットはすべて、1の生きる時間値を持つでしょう。 私たちが生きる時間をいつも減少させるとき、次に、各入って来るパケットと意志がそのパケットを捨てるので、各ノードを少なくとも1つのコネ評価して、パケットがネットワークを通って移動するのに従って生きる時間値が減少して、私たちがこの場合それをゼロまで減少させるつもりであるのを保証してください。

   We have thus shown that a datagram network with infinite storage,
   first-in-first-out queuing, and a finite packet lifetime will, under
   overload, drop all packets.  This is a rather unexpected result.  But
   it is quite real.  It is not an artifact of the infinite-buffer
   assumption.  The problem still occurs in networks with finite
   storage, but the effects are less clearly seen.  Datagram networks
   are known to behave badly under overload, but analysis of this
   behavior has been lacking.  In the infinite-buffer case, the analysis
   is quite simple, as we have shown, and we obtain considerable insight
   into the problem.

その結果、私たちは、無限の格納があるデータグラム・ネットワーク、ファーストインファーストアウトの列を作り、および有限パケット生存期間がオーバーロードの下ですべてのパケットを落とすのを示しました。 これはかなり予期していなかった結果です。 しかし、それはかなり本当です。 それは無限のバッファ仮定の人工物ではありません。 問題は有限格納でネットワークでまだ起こっていますが、効果はそれほど明確にない見られません。 データグラム・ネットワークがオーバーロードの下でひどく振る舞うのが知られていますが、この振舞いの分析は欠けています。 無限のバッファ場合では、分析はかなり簡単です、私たちが目立って、問題に関するかなりの洞察を得るとき。

   One would expect this phenomenon to have been discovered previously.
   But previous work on congestion control in packet switching systems
   almost invariably focuses on buffer management.  Analysis of the
   infinite buffer case is apparently unique with this writer.

人は、以前にこの現象を発見してあると予想するでしょう。 しかし、パケット交換システムにおける輻輳制御に対する前の仕事はほぼ不変的にバッファ管理に焦点を合わせます。 無限のバッファケースの分析は明らかにこの作家にユニークです。

   This result is directly applicable to networks with finite resources.
   The storage required to implement a switch that can never run out of
   buffers turns out to be quite reasonable.  Let us consider a pure
   datagram switch for an ARPANET-like network.  For the case of a
   packet switch with four 56Kb links, and an upper bound on the
   time-to-live of 15 seconds, the maximum buffer space that could ever
   be required is 420K bytes <1>.  A switch provided with this rather
   modest amount of memory need never drop a packet due to buffer
   exhaustion.

この結果は有限な資源で直接ネットワークに適切です。 バッファを決して使い果たすことができないスイッチを実行するのに必要である格納はかなり妥当であると判明します。 アルパネットのようなネットワークのために純粋なデータグラムスイッチを考えましょう。 56KBの4個のリンクがあるパケット交換機に関するケース、および15秒、かつて必要であるのが、420Kのバイト<であるということであるかもしれない最大のバッファ領域が生きるために調節された1>の上の上限のために。 このかなり穏やかなメモリー容量が提供されたスイッチはバッファ疲労困憊のためパケットを決して落としてはいけません。

   This problem is not just theoretical.  We have demonstrated it
   experimentally on our own network, using a supermini with several
   megabytes of memory as a switch.  We now have experimental evidence
   that the phenomenon described above occurs in practice.  Our first

この問題はただ理論上ではありません。 スイッチとして数個のメガバイトのメモリがあるスーパーミニコンピュータを使用して、私たちは私たち自身のネットワークに実験的にそれを示しました。 私たちには、現在、上で説明された現象が実際には起こるという実験上の証拠があります。 私たちの1番目

Nagle                                                           [Page 3]

ネーグル[3ページ]

RFC 970                                                    December 1985
On Packet Switches With Infinite Storage

無限の格納があるパケット交換機の上のRFC970 1985年12月

   experiment, using an Ethernet on one side of the switch and a 9600
   baud line on the other, resulted in 916 IP datagrams queued in the
   switch at peak.  However, we were applying the load over a TCP
   transport connection, and the transport connection timed out due to
   excessive round trip time before the queue reached the time to live
   limit, so we did not actually reach the stable state with the queue
   at the maximum length as predicted by our analysis above.  It is
   interesting that we can force this condition from the position of a
   user application atop the transport layer (TCP), and this deserves
   further analysis.

実験はピークのスイッチに列に並ばせられた916個のIPデータグラムをもたらして、もう片方のスイッチと9600年のボー線の半面の上でイーサネットを使用しました。 しかしながら、私たちがTCP輸送接続の上に荷重を適用していて、待ち行列がライブ限界に時間に達する前に輸送接続が過度の周遊旅行時間による外で調節したので、私たちの分析で予測される最大の長さでの待ち行列が上にある状態で、私たちは実際に安定状態に達しませんでした。 私たちが(TCP)トランスポート層の上でユーザアプリケーションの位置からこの状態を強制できるのが、おもしろく、これはさらなる分析に値します。

Interaction with Transport Protocols

トランスポート・プロトコルとの相互作用

   We have thus far assumed packet sources that emit packets at a fixed
   rate.  This is a valid model for certain sources such as packet voice
   systems.  Systems that use transport protocols of the ISO TP4 or DoD
   TCP class, however, ought to be better behaved.  The key point is
   that transport protocols used in datagram systems should behave in
   such a way as to not overload the network, even where the network has
   no means of keeping them from doing so.  This is quite possible.  In
   a previous paper by this writer [1], the behavior of the TCP
   transport protocol over a congested network is explored.  We have
   shown that a badly behaved transport protocol implementation can
   cause serious harm to a datagram network, and discussed how such an
   implementation ought to behave.  In that paper we offered some
   specific guidance on how to implement a well-behaved TCP, and
   demonstrated that proper behavior could in some cases reduce network
   load by an order of magnitude.  In summary, the conclusions of that
   paper are that a transport protocol, to be well behaved, should not
   have a retransmit time shorter than the current round trip time
   between the hosts involved, and that when informed by the network of
   congestion, the transport protocol should take steps to reduce the
   number of packets outstanding on the connection.

私たちはこれまでのところ、定率でパケットを放つパケットソースを思っていました。 これはパケット音声システムなどの確信している源への有効なモデルです。しかしながら、ISO TP4かDoD TCPのクラスのトランスポート・プロトコルを使用するシステムは反応するべきであるほうがよいです。 要所はデータグラムシステムで使用されるトランスポート・プロトコルがネットワークを積みすぎないほどそのような方法で振る舞うべきであるということです、ネットワークにはそれらがそうするのを妨げる手段が全くしさえしないところで。 これはかなり可能です。 この作家[1]による前の論文では、混雑しているネットワークの上のTCPトランスポート・プロトコルの振舞いは調査されます。 私たちは、ひどく振る舞っているトランスポート・プロトコル実現が重大な害をデータグラム・ネットワークに引き起こす場合があるのを示して、そのような実現がどう振る舞うべきであるかについて議論しました。 その紙では、私たちは、どう品行方正のTCPを実行するかにおける何らかの特定の指導を申し出て、いくつかの場合、適切な振舞いがネットワーク負荷を1桁減少させることができるのを示しました。 概要では、その紙の結末はよく振る舞うためにはそのaトランスポート・プロトコルです、そして、aにホストの間の時間がかかわった現在の周遊旅行より短い間を再送させるべきでなくて、混雑についてネットワークによって知らされると、トランスポート・プロトコルが取るべきであるのは、接続の未払いのパケットの数を減少させるために踏まれます。

   We reference our earlier work here to show that the network load
   imposed by a transport protocol is not necessarily fixed by the
   protocol specification.  Some existing implementations of transport
   protocols are well-behaved.  Others are not. We have observed a wide
   variability among existing TCP implementations.  We have reason to
   suspect that ISO TP4 implementations will be more uniform, given the
   greater rigidity of the specification, but we see enough open space
   in the TP4 standard to allow for considerable variability.  We
   suspect that there will be marginal TP4 implementations, from a
   network viewpoint, just as there are marginal TCP implementations
   today. These implementations will typically work quite well until
   asked to operate over a heavily loaded network with significant
   delays.  Then we find out which ones are well-behaved.

私たちは、トランスポート・プロトコルによって課されたネットワーク負荷が必ずプロトコル仕様で修理されるというわけではないのを示すためにここで以前の仕事に参照をつけます。 トランスポート・プロトコルのいくつかの既存の実現が品行方正です。 他のものはそうではありません。 私たちは既存のTCP実現の中で広い可変性を観測しました。 私たちには、仕様の、より大きい剛性を考えて、ISO TP4実現が、より一定になりますが、私たちが、TP4の空き地がかなりの可変性を考慮するために標準であることを十分見ると疑う理由があります。 私たちは、マージンのTP4実現があると疑います、ネットワーク観点から、ちょうど今日、マージンのTCP実現があるとき。 通常、大いにロードされたネットワークの上で重要な遅れで作動するように頼まれるまで、これらの実現はかなりうまくいくでしょう。 そして、私たちは、どれが品行方正であるかを見つけます。

Nagle                                                           [Page 4]

ネーグル[4ページ]

RFC 970                                                    December 1985
On Packet Switches With Infinite Storage

無限の格納があるパケット交換機の上のRFC970 1985年12月

   Even if all hosts are moderately well-behaved, there is potential for
   trouble.  Each host can normally obtain more network bandwidth by
   transmitting more packets per unit time, since the first in, first
   out strategy gives the most resources to the sender of the most
   packets. But collectively, as the hosts overload the network, total
   throughput drops.  As shown above, throughput may drop to zero.
   Thus, the optimal strategy for each host is strongly suboptimal for
   the network as a whole.

すべてのホストが適度に品行方正であっても、問題の可能性があります。 通常、各ホストは、より多くのユニット時間あたりのパケットを伝えることによって、より多くのネットワーク回線容量を得ることができます、最初のコネ以来最初に、出ている戦略は最も多くのパケットの送付者に最も多くのリソースを与えます。 しかし、ホストがネットワークを積みすぎるのに従って、総スループットはまとめて、低下します。 上に示されるように、スループットはゼロまで下がるかもしれません。 したがって、全体でネットワークにおいて、各ホストのための最適戦略は強く準最適です。

Game Theoretic Aspects of Network Congestion

ネットワークの混雑のゲームの理論的な局面

   This game-theory view of datagram networks leads us to a digression
   on the stability of multi-player games.  Systems in which the optimal
   strategy for each player is suboptimal for all players are known to
   tend towards the suboptimal state.  The well-known prisoner's dilemma
   problem in game theory is an example of a system with this property.
   But a closer analogue is the tragedy of the commons problem in
   economics.  Where each individual can improve their own position by
   using more of a free resource, but the total amount of the resource
   degrades as the number of users increases, self-interest leads to
   overload of the resource and collapse.  Historically this analysis
   was applied to the use of common grazing lands; it also applies to
   such diverse resources as air quality and time-sharing systems.  In
   general, experience indicates that many-player systems with this type
   of instability tend to get into serious trouble.

データグラム・ネットワークのこのゲーム理論視点はマルチプレーヤーゲームの安定性で私たちを脱線に導きます。 すべてのプレーヤーにとって、各プレーヤーのための最適戦略が準最適であるシステムは準最適の状態の傾向があるのが知られています。 ゲーム理論の周知の囚人のジレンマ問題はこの特性があるシステムに関する例です。 しかし、経済学は、より近いアナログがコモン問題の悲劇です。 各個人が一層の無料のリソースを使用して、合計を使用することによってそれら自身の位置を改良できるところに、リソースの量はユーザの数として増加を下がらせて、私利はリソースと崩壊のオーバーロードにつながります。 歴史的に、この分析は一般的な放牧地の使用に適用されました。 また、それは大気質と時分割システムのようなさまざまのリソースに申し込まれます。一般に、経験は、このタイプの不安定性がある多くのプレーヤーシステムが、重大な問題に入る傾向があるのを示します。

   Solutions to the tragedy of the commons problem fall into three
   classes: cooperative, authoritarian, and market solutions.
   Cooperative solutions, where everyone agrees to be well-behaved, are
   adequate for small numbers of players, but tend to break down as the
   number of players increases.  Authoritarian solutions are effective
   when behavior can be easily monitored, but tend to fail if the
   definition of good behavior is subtle.  A market solution is possible
   only if the rules of the game can be changed so that the optimal
   strategy for players results in a situation that is optimal for all.
   Where this is possible, market solutions can be quite effective.

コモン問題の悲劇のソリューションは3つのクラスになります: 協同組合、権威主義者、および市場解決策。 少ない数のプレーヤーにとって、共同解決は皆が品行方正であるのに同意するところで適切ですが、プレイ人数が増加するのに従って故障する傾向があってください。 容易に振舞いをモニターできるとき、権威主義的な解決策は有効ですが、良い振舞いの定義が微妙であるなら、失敗する傾向があってください。 ゲームの規則を変えることができる場合にだけ市場解決策が可能であるので、プレーヤーのための最適戦略はすべてに、最適の状況をもたらします。 これが可能であるところでは、市場解決策はかなり効果的である場合があります。

   The above analysis is generally valid for human players.  In the
   network case, we have the interesting situation that the player is a
   computer executing a preprogrammed strategy.  But this alone does not
   insure good behavior; the strategy in the computer may be programmed
   to optimize performance for that computer, regardless of network
   considerations.  A similar situation exists with automatic redialing
   devices in telephony, where the user's equipment attempts to improve
   performance over an overloaded network by rapidly redialing failed
   calls.  Since call-setup facilities are scarce resources in telephone
   systems, this can seriously impact the network; there are countries

一般に、人間のプレーヤーにとって、上の分析は有効です。 プレーヤーはおもしろい状況ですが、ネットワーク場合では、私たちはそうしました。前プログラムされた戦略を実行するコンピュータ。 しかし、これだけが良い振舞いを保障しません。 コンピュータの戦略がネットワーク問題にかかわらずそのコンピュータのために性能を最適化するようにプログラムされるかもしれません。 同様の状況は電話に自動再ダイヤルする装置で存在しています。そこでは、ユーザの設備が積みすぎられたネットワークの上の急速に失敗した呼び出しに再ダイヤルするのによる性能を向上させるのを試みます。 呼び出しセットアップ施設が電話の希少資源であるので、これは真剣にネットワークに影響を与えることができます。 国があります。

Nagle                                                           [Page 5]

ネーグル[5ページ]

RFC 970                                                    December 1985
On Packet Switches With Infinite Storage

無限の格納があるパケット交換機の上のRFC970 1985年12月

   that have been forced to prohibit such devices.  (Brazil, for one).
   This solution by administrative fiat is sometimes effective and
   sometimes not, depending on the relative power of the administrative
   authority and the users.

それはやむを得ずそのようなデバイスを禁止しました。 (個人的にはブラジル。) 管理法令によるこのソリューションは、時々有効で時々そうしていません、職務権限とユーザの相対的なパワーによって。

   As transport protocols become more commercialized and competing
   systems are available, we should expect to see attempts to tune the
   protocols in ways that may be optimal from the point of view of a
   single host but suboptimal from the point of view of the entire
   network.  We already see signs of this in the transport protocol
   implementation of one popular workstation manufacturer.

トランスポート・プロトコルがさらに商業化されるようになって、競争しているシステムが利用可能であるので、私たちは、独身のホストの観点から最適の、しかし、全体のネットワークの観点から準最適であるかもしれない方法でプロトコルを調整する試みを見ると予想するべきです。 私たちは1つのポピュラーなワークステーションメーカーのトランスポート・プロトコル実装で既にこのサインを見ます。

   So, to return to our analysis of a pure datagram internetwork, an
   authoritarian solution would order all hosts to be "well-behaved" by
   fiat; this might be difficult since the definition of a well-behaved
   host in terms of its externally observed behavior is subtle.  A
   cooperative solution faces the same problem, along with the difficult
   additional problem of applying the requisite social pressures in a
   distributed system.  A market solution requires that we make it pay
   to be well-behaved.  To do this, we will have to change the rules of
   the game.

それで、私たちの純粋なデータグラムインターネットワークの分析に戻るために、権威主義的なソリューションは、「品行方正である」ようすべてのホストに法令で命令するでしょう。 外部的に観測された振舞いによる品行方正のホストの定義が微妙であるので、これは難しいかもしれません。 共同解決は同じ問題に直面しています、分散システムにおける必要な社会的圧力を適用するという難しい追加問題と共に。 市場ソリューションは、品行方正であるのが私たちが得にならせるのを必要とします。 これをするために、私たちは発想を変えなければならないでしょう。

Fairness in Packet Switching Systems

パケット交換システムの公正

   We would like to protect the network from hosts that are not
   well-behaved.  More specifically, we would like, in the presence of
   both well-behaved and badly-behaved hosts, to insure that
   well-behaved hosts receive better service than badly-behaved hosts.
   We have devised a means of achieving this.

品行方正でないホストからネットワークを保護したいと思います。 より明確に、品行方正のものと同様にひどく振る舞っているホストの面前で品行方正のホストがひどく振る舞っているホストより良いサービスを受けるのを保障したいと思います。 私たちはこれを達成する手段を工夫しました。

   Let us consider a network that consists of high-bandwidth
   pure-datagram local area networks without flow control (Ethernet and
   most IEEE 802.x datagram systems are of this class, whether based on
   carrier sensing or token passing), hosts connected to these local
   area networks, and an interconnected wide area network composed of
   packet switches and long-haul links.  The wide area network may have
   internal flow control, but has no way of imposing mandatory flow
   control on the source hosts.  The DoD Internet, Xerox Network Systems
   internetworks, and the networks derived from them fit this model.

フロー制御(イーサネットとほとんどのIEEE 802.xデータグラムシステムがこのクラスのものです、キャリヤーの感じかトークンパッシングに基づいているか否かに関係なく)なしで高帯域純粋なデータグラムローカル・エリア・ネットワークから成るネットワーク、これらのローカル・エリア・ネットワークに接続されたホスト、およびパケット交換機と長期リンクで構成されたインタコネクトされた広域ネットワークを考えましょう。 広域ネットワークには、内部のフロー制御を持っているかもしれませんが、義務的なフロー制御を送信元ホストに課す方法は全くありません。 DoDインターネット、ゼロックスNetwork Systemsインターネットワーク、およびそれらから得られたネットワークはこのモデルに合います。

   If any host on a local area network generates packets routed to the
   wide area network at a rate greater than the wide area network can
   absorb them, congestion will result in the packet switch connecting
   the local and wide area networks.  If the packet switches queue on a
   strictly first in, first out basis, the badly behaved host will
   interfere with the transmission of data by other, better-behaved
   hosts.

ローカル・エリア・ネットワークのどれかホストが広域ネットワークがそれらを吸収できるより大きいレートで広域ネットワークに発送されたパケットを生成すると、混雑は地方と広域ネットワークを接続するパケット交換機をもたらすでしょう。 パケット交換機が最初に、最初に、基礎からのひどく振る舞っているホストにaに厳密に列を作るなら、他の、そして、よりよく振る舞っているホストによるデータの伝達を妨げるために望んでください。

Nagle                                                           [Page 6]

ネーグル[6ページ]

RFC 970                                                    December 1985
On Packet Switches With Infinite Storage

無限のストレージがあるパケット交換機の上のRFC970 1985年12月

   We introduce the concept of fairness.  We would like to make our
   packet switches fair; in other words, each source host should be able
   to obtain an equal fraction of the resources of each packet switch.
   We can do this by replacing the single first in, first out queue
   associated with each outgoing link with multiple queues, one for each
   source host in the entire network. We service these queues in a
   round- robin fashion, taking one packet from each non-empty queue in
   turn and transmitting the packets with positive time to live values
   on the associated outgoing link, while dropping the expired packets.
   Empty queues are skipped over and lose their turn.

私たちは公正の概念を紹介します。 私たちのパケット交換機を公正にしたいと思います。 言い換えれば、それぞれの送信元ホストはそれぞれのパケット交換機に関するリソースの等しい部分を得ることができるべきです。 私たちはただ一つの最初のコネを取り替えることによって、これができます、複数の待ち行列とのそれぞれの出発しているリンクに関連している最初の出ている待ち行列、全体のネットワークの各送信元ホストあたり1つ。 私たちは丸いコマドリファッションでこれらの待ち行列を修理します、それぞれの非空の待ち行列から1つのパケットを順番に取って、関連出発しているリンクの上に上向きの時間でライブ値にパケットを伝えて満期のパケットを下げていて。 空の待ち行列は、飛ばされて、彼らの回転を失います。

   This mechanism is fair; outgoing link bandwidth is parcelled out
   equally amongst source hosts.  Each source host with packets queued
   in the switch for the specified outgoing link gets exactly one packet
   sent on the outgoing link each time the round robin algorithm cycles.
   So we have implemented a form of load-balancing.

このメカニズムは公正です。 送信元ホストの中で等しく外向的なリンク帯域幅を分配します。 連続アルゴリズムが循環するたびにパケットがスイッチに指定された出発しているリンクへ列に並ばせられている各送信元ホストはちょうど1つのパケットを出発しているリンクに送らせます。 それで、私たちはロードバランシングのフォームを実装しました。

   We have also improved the system from a game theory point of view.
   The optimal strategy for a given host is no longer to send as many
   packets as possible.  The optimal strategy is now to send packets at
   a rate that keeps exactly one packet waiting to be sent in each
   packet switch, since in this way the host will be serviced each time
   the round-robin algorithm cycles, and the host's packets will
   experience the minimum transit delay.  This strategy is quite
   acceptable from the network's point of view, since the length of each
   queue will in general be between 1 and 2.

また、私たちはゲーム理論観点からシステムを改良しました。 与えられたホストのための最適戦略がもうできるだけ多くのパケットを送るのがありません。 最適戦略は現在、ちょうど1つのパケットを各パケット交換機で送られるのを待たせておくレートでパケットを送ることです、ホストがその都度サービスを提供されるこのように、連続アルゴリズムが循環して、ホストのパケットが最小のトランジット遅れを経験するので。 この戦略はネットワークの観点からかなり許容できます、それぞれの待ち行列の長さが一般に1〜2になるので。

   The hosts need advisory information from the network to optimize
   their strategies.  The existing Source Quench mechanism in DoD IP,
   while minimal, is sufficient to provide this.  The packet switches
   should send a Source Quench message to a source host whenever the
   number of packets in the queue for that source host exceeds some
   small value, probably 2.  If the hosts act to keep their traffic just
   below the point at which Source Quench messages are received, the
   network should run with mean queue lengths below 2 for each host.

ホストは、彼らの戦略を最適化するためにネットワークからの顧問情報を必要とします。 最小量ですが、DoD IPの既存のSource Quenchメカニズムは、これを提供するために十分です。 その送信元ホストのための待ち行列における、パケットの数が何らかの小さい値、たぶん2を超えているときはいつも、パケット交換機はSource Quenchメッセージを送信元ホストに送るはずです。 ホストがまさしくSource Quenchメッセージが受信されているポイントより下で彼らのトラフィックを保つために行動するなら、ネットワークを各ホストのために2未満の平均である待ち行列の長さと共に経営しているべきです。

   Badly-behaved hosts can send all the datagrams they want, but will
   not thereby increase their share of the network resources.  All that
   will happen is that packets from such hosts will experience long
   transit times through the network.  A sufficiently badly-behaved host
   can send enough datagrams to push its own transit times up to the
   time to live limit, in which case none of its datagrams will get
   through.  This effect will happen sooner with fair queuing than with
   first in, first out queuing, because the badly- behaved host will
   only obtain a share of the bandwidth inversely proportional to the
   number of hosts using the packet switch at the moment.  This is much

ひどく振る舞っているホストは、彼らが欲しいすべてのデータグラムを送ることができますが、その結果、それらのネットワーク資源のシェアを増強しないでしょう。 起こるすべてはそのようなホストからのパケットがネットワークを通して長いトランジット時間を経験するということです。 十分ひどく振る舞っているホストは時間までのそれ自身のトランジット時代をライブ限界に押すことができるくらいのデータグラムを送ることができます、その場合、データグラムのいずれも通らないでしょう。 この効果は公正な列を作りで最初のコネより早く起こるでしょう、最初に外に列を作って、ひどく振る舞っているホストが現在パケット交換機を使用することで逆にホストの数に変化する帯域幅のシェアを得るだけであるので。 これは多いです。

Nagle                                                           [Page 7]

ネーグル[7ページ]

RFC 970                                                    December 1985
On Packet Switches With Infinite Storage

無限のストレージがあるパケット交換機の上のRFC970 1985年12月

   less than the share it would have under the old system, where more
   verbose hosts obtained more bandwidth.  This provides a strong
   incentive for badly-behaved hosts to improve their behavior.

それが、より冗長なホストが、より多くの帯域幅を得た古いシステムの下で持っているシェアよりそれほど。 これはひどく振る舞っているホストが彼らの振舞いを改良する強い動機を提供します。

   It is worth noting that malicious, as opposed to merely
   badly-behaved, hosts, can overload the network by using many
   different source addresses in their datagrams, thereby impersonating
   a large number of different hosts and obtaining a larger share of the
   network bandwidth. This is an attack on the network; it is not likely
   to happen by accident. It is thus a network security problem, and
   will not be discussed further here.

単にひどく振る舞いと対照的にそんなに悪意がある価値の注意(ホスト)はそれらのデータグラムで多くの異なったソースアドレスを使用することによって、ネットワークを積みすぎることができます、その結果、多くの異なったホストをまねて、ネットワーク回線容量の、より大きいシェアを得てことです。 これはネットワークに対する攻撃です。 それは偶然に起こりそうにはありません。 それについて、その結果、ネットワーク警備上の問題であり、ここでさらに議論しないでしょう。

   Although we have made the packet switches fair, we have not thereby
   made the network as a whole fair.  This is a weakness of our
   approach. The strategy outlined here is most applicable to a packet
   switch at a choke point in a network, such as an entry node of a wide
   area network or an internetwork gateway.  As a strategy applicable to
   an intermediate node of a large packet switching network, where the
   packets from many hosts at different locations pass through the
   switch, it is less applicable.  The writer does not claim that the
   approach described here is a complete solution to the problem of
   congestion in datagram networks.  However, it presents a solution to
   a serious problem and a direction for future work on the general
   case.

パケット交換機を公正にしましたが、私たちはその結果、全体でネットワークを公正にしていません。 これは私たちのアプローチの弱点です。 ここに概説された中で戦略はネットワークで難所のパケット交換機に最も適切です、広域ネットワークのエントリーノードやインターネットワークゲートウェイのように。 別の場所の多くのホストからのパケットがスイッチを通り抜ける大きいパケット交換網の中間的ノードに適切な戦略として、それはそれほど適切ではありません。 作家は、ここで説明されたアプローチがデータグラム・ネットワークにおける混雑の問題の完全解であると主張しません。 しかしながら、それは一般的なケースへの今後の活動のための深刻な問題と方向にソリューションを提示します。

Implementation

実装

   The problem of maintaining a separate queue for each source host for
   each outgoing link in each packet switch seems at first to add
   considerably to the complexity of the queuing mechanism in the packet
   switches.  There is some complexity involved, but the manipulations
   are simpler than those required with, say, balanced binary trees.
   One simple implementation involves providing space for pointers as
   part of the header of each datagram buffer.  The queue for each
   source host need only be singly linked, and the queue heads (which
   are the first buffer of each queue) need to be doubly linked so that
   we can delete an entire queue when it is empty.  Thus, we need three
   pointers in each buffer.  More elaborate strategies can be devised to
   speed up the process when the queues are long.  But the additional
   complexity is probably not justified in practice.

各パケット交換機のそれぞれの出発しているリンクに各送信元ホストのための別々の待ち行列を維持するという問題は初めに、パケット交換機の列を作りメカニズムの複雑さにかなり加えるように思えます。 かかわった何らかの複雑さがありますが、操作はそれらがたとえば、バランスのとれている2進の木で必要であるというよりも簡単です。 1つの簡単な実装が、それぞれのデータグラムバッファのヘッダーの一部としてスペースを指針に提供することを伴います。 各送信元ホストのための待ち行列は単独でリンクされるだけでよいです、そして、待ち行列ヘッド(それぞれの待ち行列の最初のバッファである)はそれが空であるときに、私たちが全体の待ち行列を削除できるように二倍リンクされる必要があります。 したがって、私たちは各バッファのスリー・ポイント・シュートを必要とします。 待ち行列が長いときに、プロセスを加速するために、より入念な戦略を工夫できます。 しかし、追加複雑さはたぶん実際には正当化されません。

   Given a finite buffer supply, we may someday be faced with buffer
   exhaustion.  In such a case, we should drop the packet at the end of
   the longest queue, since it is the one that would be transmitted
   last. This, of course, is unfavorable to the host with the most
   datagrams in the network, which is in keeping with our goal of
   fairness.

有限バッファ供給を考えて、私たちはいつか、バッファ疲労困憊に直面するかもしれません。 このような場合には、私たちは最も長い待ち行列の終わりにパケットを下げるべきです、それが最後に伝えられるものであるので。 ホストには、これはネットワークは最も多くのデータグラムによってもちろん好ましくありません。(ネットワークは私たちの公正の目標に従っています)。

Nagle                                                           [Page 8]

ネーグル[8ページ]

RFC 970                                                    December 1985
On Packet Switches With Infinite Storage

無限のストレージがあるパケット交換機の上のRFC970 1985年12月

Conclusion

結論

   By breaking away from packet switching's historical fixation on
   buffer management, we have achieved some new insights into congestion
   control in datagram systems and developed solutions for some known
   problems in real systems. We hope that others, given this new
   insight, will go on to make some real progress on the general
   datagram congestion problem.

バッファ管理に対するパケット交換の歴史的な執着から逃げることによって、私たちは、データグラムシステムでいくつかの新しい洞察を輻輳制御に達成して、いくつかの既知の問題によって実システムで解決策を見いだしました。この新しい洞察を考えて、他のものが、一般的なデータグラム混雑問題におけるいくらかの真の進歩を作り続けることを願っています。

References

参照

   [1]  Nagle, J. "Congestion Control in IP/TCP Internetworks", ACM
        Computer Communications Review, October 1984.

[1] ACMコンピュータコミュニケーションは、1984年10月にJ. ネーグル、「IP/TCPインターネットワークにおける輻輳制御」と見直します。

Editor's Notes

編集者注

   <1>  The buffer space required for just one 10Mb Ethernet with an
        upper bound on the time-to-live of 255 is 318 million bytes.

バッファ領域が10Mbのちょうど1つのイーサネットのために生きる時の上限で必要とした255の<1>は3億1800万バイトです。

Nagle                                                           [Page 9]

ネーグル[9ページ]