JPH03174848A - コンピュータ回路網における遅延ベース混雑回避方法及び装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔発明の分野〕 本発明はデータ通信システムに関し、より特定的には直
列データ伝送を使用するパケットデータ通信回路網にお
ける混雑回避のための遅延ベース手順に関する。

〔発明の背景〕

伝統的な混雑制御方式は、回路網上の負荷が過大となり
パケットが失われ始めると回路網上の負荷を減少させる
ように働らく。これらの方式は回路網を混雑から回復可
能ならしめる。混雑回避メカニズムは、他方では回路網
を最適負荷で作動せしめ得る予防メカニズムでもある。

１９８８年４月２２日付Ｒ，Ｋ、　　ジェイン、Ｘ、　
Ｋ、　　ラマクリシュナン及びり、　Ｍ、　　チウ（デ
ィジタル・イクイップメント・コーポレーシヨン）の関
連出願、一連番号１８４．９４５号“コンピュータ回路
網における混雑回避”に記載のコンピュータ回路網のた
めの混雑回避方式においては回路網内の各ルータは、負
荷がそのルータの最適性能の領域内にあることを保証す
るために、そのルータが処理する合計トラフィック即ち
その負荷を条件付けることを探索する。この制御を達成
するために、ルータは複数のノードによって受信される
パケット内の複数のビットによってこれらのノードへの
フィードバンクを生成して過負荷状態を表示する。この
システムは混雑回避の機能には有効であるが、若干のフ
ィードバックピントをパケットに付加する必要があるた
めに、パケット書式が固定されていて新しいビットを付
加することができない回路網内のシステムとは相客れな
い。また、複数のノード及び多様な型のサーバを包含す
る異種混合回路網においては、これらのビットはある機
器に対して無意味となり得る。更に、この方法はルータ
またはサーバ機能にオーバヘッドを付加する。

他のコンピュータ回路網アーキテクチャは混雑制御のた
めの方策を有する。例えばディジタル・ネットワーク・
アーキテクチャ（ＤＮＡ）は１９８６年１０月のＩ　Ｅ
ＥＦ、ジャーナル・オン・セレクテンド・エリアズ・イ
ン・コミュニケーションズ、１１６２〜１１６７ページ
に所載のタイムアウトベース混雑制御及び１９７８年３
月のＩ　ＥＥＥ　）ランザクシラン・オン・コミュニケ
ーションズ、３２８〜３３７ページに所載の平方根バソ
ファリミティングを使用する。１９７９年の１８Ｍシス
テム・ジャーナル第１８巻２号の２９８〜３１４ページ
に記載されているように、ＩＢＭのシステム・ネットワ
ーキング・アーキテクチャ（ＳＮＡ）は“変更ウィンド
ウ標識”（ＣＷＩ）及び“リセットウィンドウ標識”（
ＲＷＩ）と呼ぶ混雑ビットを、源ノードを尋ねるために
逆方向に流れるパケット内に使用して混雑中の負荷を減
少させる。要約すれば、他の混雑対策は回路網から利用
者へのフィードバック信号（タイムアウト、ピントまた
は通報の形の）及び利用者によって訓練される負荷制御
メカニズム（低下したウィンドウレート）からなる。

これらの先行方式は全て混雑制御方式である。

またこれらは特定の回路網システム設計及びプロトコル
に専用であり、他の型の回路網アーキテクチャには適用
できない、異種混合副回路網からなる回路網においては
、１つの副回路網からの混雑フィードバックは通常は他
の副回路網上の源には意味を持たないであろう。

本発明の主目的は、異種混合回路網即ち、例えばＳＮＡ
、ＴＣＰ／ＩＰ、ｌ５Ｏ１０ＳＩ。

ＤＮＡ等の異なるアーキテクチャの副回路網が存在し得
る回路網において作動可能なコンピュータ回路網用混雑
回避手順を提供することである。別の目的は、回路網自
体に、即ちパケット転送用ルータまたはサーバにオーバ
ヘッドを付加しない混雑回避方式、及びフィードバック
のための付加的ビットの形でパケットにオーバヘッドを
付加しない混雑回避方式を提供することである。更なる
目的は、それ自体が回路網内に付加的なパケットを注入
せず、それによってトラフィック負荷を付加することが
ない混雑回避方式を提供することである。付加的な目的
は、最適ローディングの移動する目標に動的に適合する
ように回路網の構成及びトラフィックを変更させること
が可能な混雑回避方式を提供することである。

〔発明の概要〕

本発明の一実施例によれば、パケットデータ通信システ
ムは、各ノードがデータを宛先に送り肯定応答を受ける
時に発生する往復遅延を測定する混雑回避方法を使用す
る。この遅延は異なる負荷レベルに関して測定され、こ
れらの遅延の比較を使用して負荷レベルが増大したかま
たは低下したかを決定する。負荷レベルは、ウィンドウ
サイズ（回路網内へ送られるパケットの数）またはパケ
ットレート（単位時間当りのパケット）のような回路網
チューニングパラメタを調整することによって変更する
ことができる。目標は、処理能力対トラフィック曲線に
おいてデータ処理能力が高く往復遅延が低くなる膝折点
における動作である。

制御は、ルータまたはサーバによる介入なしに各ノード
において個々に達成されるので、システムオーバヘッド
は増大しない。

本発明の特徴と考えられる新規特色は特許請求の範囲に
記載されている。しかし本発明それ自体、並びに他の特
色及び長所は添付図面に基く以下の特定実施例の説明か
ら明白になるであろう。

〔実施例〕

第１図は本発明の特色を実現可能な一実施例によってデ
ータパケットを送信及び受信するためのパケット型デー
タ通信システムを示す。利用者即ちノード１０ａ−１０
ｎはリンク１２によってルータまたはサーバ１１に接続
されている。リンク１２は二地点間通信リンク、または
トークンリングまたはイーサネットＬＡＮのような共用
通信媒体であり得る。ノード１０ａ−１０ｎのそれぞれ
は通報パケットを生威し受信することができるＣＰＵま
たは類似のプロセッサ型装置である。ノード１０は、デ
ィスク制御装置、高速印刷機器、またはこの型の他の資
源、及び高性能データプロセッサであり得る。ルータ１
１はリンク１３によってルータまたはサーバ１４に結合
され、ルータまたはサーバ１４にはリンク１６によって
複数のノード１５ａ〜１５ｎが接続されている。同様に
、ルータ１４はリンク１７によってルータ１８に結合さ
れ、ルータ１８はリンク１９によって複数のノード２０
ａ〜２Ｏｎに接続されている。完全な回路網内にはより
多くのこれらのルータが存在していよう。各ルータ１１
．１４及び１８には多分複数ダースのノードが結合され
、また多くのルータが存在し得るので回路網は数千のノ
ードを含むことになろう、リンク１３及び１７は同一の
ビルディング内の、またはビルディング間のワイヤリン
クを含むことができ、または長距離光フアイバリンク並
びに衛星リンクを含むことができる。

回路網は、それぞれが異なるプロトコルに従う若干の副
回路網からなることができる。例えば、第１図に示す３
つのルータは、それぞれＤＮＡ、ＳＮＡ及びＴＣＰ／Ｉ
Ｐプロトコルに従う３つの異なる副回路網の部分であっ
てよい。

第１図のシステムのノードの１つは別のノードに送るべ
きかなり大きい、多分数メガバイトのデータのブロック
を有することが屡々であろうが、典型的な書式のパケッ
トを使用するとこのデータは多分５１２バイトずつの多
数のパケットに分割しなければならない。しかし１バー
スト内に数百または数千のパケットを送る代りに、ノー
ドは回路網のために確立されている優先権及び平等基準
に従わなければならない。

ルータはノードからパケットを受信して経路が自由にな
った時に宛先に向けて転送するためにそれらを保持する
バッファを含んでいる。これらのバッファは先入れ先出
しメモリとして働らく。しかしバッファが満杯である時
には、入パケットは単に破棄されるので送信者はそれを
再送しなければならないであろう。またバッファは受信
ノード（宛先）にも存在する。

流れ制御の一方法にれば、バッファの可用性に依存して
、宛先ノードは源ノードにウィンドウと呼ぶ複数のパケ
ットを送ることを許容する。もしこのウィンドウがルー
タ内のこれらのバッファの記憶及び転送容量を超えれば
、源はパケットが破棄されていても不必要にパケットを
送っていよう。

バッファあふれは、たとえそれが宛先において発生しな
くとも、ルータ内で発生し得る。

回路網上の負荷を制限するための別の変形はパケットレ
ートを介する。この方法においては宛先は源に単位時間
当り若干数のパケットのレートでパケットを送ることを
許容する。この“レートベース”方式においては、もし
宛先が許容したレートが中間ルータの容量を超えると、
過大なパケットがルータに待ち合わせるようになり、結
局はバッファが満杯となってパケットが失われるように
なる。

レートベース方式におけるリミティングレートは、単位
時間当りのパケットの代りに、ビット毎秒またはバイト
毎秒なる表現でも規定することができる。

ウィンドウサイズまたはパケットレートパラメタに加え
て回路網プロトコルは一般的に、回路網チューニングパ
ラメタと呼ばれる他のパラメタを有し、これらのパラメ
タは回路網の性能を最適化するように調整可能である。

一般に、これらのチューニングパラメタは回路網負荷に
も影響する。

第２ａ図乃至第２Ｃ図は、第１図に示す如き回路網の性
能を負荷の関数として示し、負荷はノードによって回路
網に入力される単位時間当りのパケット数を尺度として
いる。第２ａ図から負荷が低い場合には処理能力（何れ
かのノードによって送られ宛先ノードによって受けられ
るパケットの合計数）が負荷と共に線形に増加し、次で
負荷レベルが３５に到達すると曲線の“膝折点”が発生
し、この点以降は負荷が増加しても処理能力は重大に増
加せず、送られる付加的な通報は不要に待ち合わされ、
遅延の増加をもたらす。第２ｂ図はパケット当りの遅延
を負荷の関数としてプロットした図である。屈折点３５
以下においては遅延は本質的に一定であるが、膝折点以
上においては遅延は負荷の増加に伴って増加する。“圧
点”と呼ぶある負荷レベル３６において回路網の容量に
到達し、源ノードによって送られた付加的なパケットは
、何れのパケットも宛先に到着しないので第２ａ図及び
第２ｂ図に示すように処理能力は０に接近し、遅延は無
限大に接近する。回路網を圧点３６ではなく膝折点３５
において動作させることが望ましい。混雑制御方式は回
路網負荷をこの圧点の左に保つことを企図し、一方混雑
回避方式は負荷を最適膝折点レベル３５に維持すること
を試みる。膝折点を定義するために幾つかの方法が存在
する。１つの定義は、回路網処理能力と往復遅延との比
として定義される“回路網パワー”で表わされるもので
ある。時として指数αが使用され、パワーは以下のよう
に定義される。

膝折点は、第２Ｃ図に示すようにパワーが最大になる負
荷として定義される。パラメタαを１より大きく選択す
ることによって、回路網設計者は回路網を比較的大きい
遅延で動作させるように選択することができる。同様に
、αを１より小さく選択することによって、設計者は比
較的高い処理能力で動作するように選択することができ
る。

膝折点において動作させるための最適ウィンドウサイズ
を計算する方法の解析は、先ず他のノードは回路網にパ
ケットを送らず従って遅延または処理能力の限界の唯一
の源がトラフィックを処理するルータの容量であるとす
る仮定、即ち膝折点に到達するまでに如何に長い待ち合
せが累積し得るかを使用して行われよう。以下の解析に
は次の記号が使用される。

Ｗ＝ニラインドウニ路網内のパケットの数Ｔ＝単位時間
当りの処理能力 Ｄ＝往復遅延 Ｐ＝パワー＝Ｔ’／Ｄ α＝パワーを定義するのに使用される指数往復遅延り及
び処理能力Ｔは共にウィンドウＷの関数である： Ｄ＝ｆ、（ｗ） ’ｒ＝ｆ、（Ｗ） パワーは処理能力及び遅延の比として定義される：Ｔ′ − ここにαは回路網設計者によって選択されるパラメタで
ある。Ｐの定義から以下のように表わすことができる。

ｌｏｇ　（Ｐ）　＝　ｄｌｏｇ　（Ｔ）　−１！ｏｇ　
（Ｄ）最大パワーの点、即ち膝行点においては即ち ｄＴ　　　　　　ｄＤ α Ｔ　　　　　　　　Ｄ 従って、膝行点においては、遅延の相対（パーセンテー
ジ）増加は処理能力の相対増加のα倍である。もしα＝
１であれば膝行点における遅延のパーセンテージ増加は
処理能力のパーセンテージ増加に等しい。膝行点の前で
は ｄＤ　　　　　　ｄＴ 〈 Ｄ　　　　　　　　Ｔ となり、遅延の相対増加は処理能力の相対利得よりも小
さい。膝行点の後は Ｄ　　　　　　　　Ｔ となり、遅延の相対増加は処理能力の相対利得よりも大
きい。

膝行点においてより高い遅延の相対増加を得るためには
α〉ｌを与える。同様にα〈ｌであれば膝行点における
処理能力の相対増加はより高くなる。

ウィンドウ流れ制御回路網の場合、所与のノードにおけ
る処理能力Ｔは往復遅延当りのＷパケット、即ち Ｔ＝ であり、従って ｌｏｇＣＰ＞　　＝ｃｘｌｏｇ　（Ｗ）　−（１トα）
　　ｌｏｇ　（Ｄ）である。膝行点（即ちｄＰ＝ｏ）に
おいてはＰ　　　　　　　　Ｗ　　　　　　　　　　　
　　　　　Ｄこの条件をＷに関して解くことによって最
適ウィンドウサイズＷは として得られる。上記等式は、導関数ｄＤ／ｄＷ及び遅
延りがＷ＝Ｗにおいて測定された場合にのみ成立する。

Ｗが他の値であれば、上式はＷに対するＷの相対値を見
出すために、即ちＷがＷよりも少ない（または多い）こ
とを見出すために使用することができる。

以上に説明した解析は、回路網の内部成分の挙動、サー
ビス時間の決定論的または確率的分布、または遅延対ウ
ィンドウ曲線の線形または非線形挙動に関して何等の仮
定もなされていないから、全ての回路網または資源に対
して有効である。

もし回路網に他の利用者が存在しなければ、上記解析は
１つのノードに対して測定された遅延り及び遅延・ウィ
ンドウ曲線の勾配ｄＤ／ｄＷを使用して膝行点を決定す
る１つの方策を提供する。

上式を使用して計算されたＷの値は、ウィンドウ調整の
ための最適方向を与える。もし現ウィンドウがＷより小
さければウィンドウを増加させるべきである。同様にも
し現ウィンドウＷがＷより大きければ、ウィンドウサイ
ズを減少させるべきである。ＷとＷとの正確な差は意味
を持つかも知れないし、持たないかも知れない。例えば
、もし勾配ｄＤ／ｄＷが特定のＷにおいて０であればＷ
は無限であってＷを増加させるべきことを表わすが、こ
れは経路が無限の膝行点容量を有することを意味するも
のと解釈されるべきである。異なる値のウィンドウＷに
おいては、計算されたＷは異り得るがそれぞれの場合に
おいてそれは正しい方向を指し示す。換言すれば差（Ｗ
−Ｗ）の大きさではなく符号だけが意味を有する。

ウィンドウ調整の正確な方向を決定する一方策は正規化
された遅延勾配（ＮＤＧ）を使用することである。これ
は なる比として定義される。もし負荷が低ければＮＤＧは
低く、またはもし負荷が高ければＮＤＧは高い。膝行点
においてはＮＤＧは ｄＤ／ｄＷ　　　　　　　α Ｄ／Ｗ　　　　　　　１　＋α で与えられる。もしパラメタα＝１であれば、膝折点に
おけるＮＤＧは％である。従ってＮＤＧを計算すること
によってウィンドウサイズを増加させるのかまたは減少
させるのかの決定が明白になは最早無意味である。最適
の動作点は２つ存在し、一方は“社会的”であり、他方
は“利己的”である。

単一の経路を共用するｎ利用者（ノード）を与えると、
システム処理能力Ｔは全ｎ利用者のウィンドウの和の関
数である。

Ｔ＝ 但し、Ｗｉはｉ番目の利用者のウィンドウであり、Ｄは
ｎの各利用者によって経験される共通遅延である。シス
テムパワーはシステム処理能力に基いて定義される。

最大システムパワーの点は以下のようなｎ式の集合によ
って与えられる。

または または このようにして得られた最適動作点は社会的最適と呼ば
れる。

上式の遅延り及び偏導関数 ２　［）　／　ａ　Ｗ　ｉはＷｉ　＝Ｗｉにおいて評価
さるべきである。

個々の各使用者のパワーＰｉは使用者の処理能力Ｔｉを
基礎としており、 １ Ｔｉ＝ 及び で与えられる。

使用者のパワーは −１ αＷ。

首＝Ｏ または の時に最大となる。このようにして得られた動作点は利
己的最適と呼ばれる。Ｗｉに関する上式を調べることに
よって、利己的最適によって得られたＷｉが社会的最適
によって得られたＷｉとは異なることが分る。これらは
ノードがそのウィンドウサイズを同一方向に変化させる
べきことを指示していないかも知れない。

ｌ使用者だけが存在していれば、２つの値は等しくなり
、このような場合Ｗｉに関する何れの式もウィンドウ調
整の方向を決定するために使用することができる。

社会的考察は他の利用者が彼等のトラフィックを増加さ
せた時に良心的な利用者にウィンドウサイズを低下させ
るように導びき、一方利己的考察は他の利用者が彼等の
トラフィックを増加させた時に１人の利用者がそのウィ
ンドウサイズを増大させるように導びくであろう。この
挙動はＷｉに関する上記関係に従って数学的に真である
のみならず、直観的にも真である。ある資源が不足状態
を呈し始めれば人々はその資源を買いだめし、その資源
に対する彼等の見掛は上の需要が増加する理である。利
己的最適は各利用者が他の利用者のパワーを犠牲にして
も自己のパワーを最大限にしようと際限なくウィンドウ
を増大させ続けることを試みる競争状態を招来するので
、混雑回避は社会的最適を得ることを目指す。

社会的最適に関するＷｉに関する上式を調べると、所与
のノードにおいては、そのノードにおける社会的最適ウ
ィンドウを決定するために他の全ての利用者のウィンド
ウを知る必要があることが分る。各ノードが他の全ての
ノードにパケットを送る場合性の利用者にそのウィンド
ウサイズを通告することを要求する混雑回避方法は、付
加されるトラフィック内に過大なオーバベツドを受入れ
可能にさせる。幸運にも、社会的最適を達成するために
は他の利用者のウィンドウの知識を必要としない特別な
場合が存在する。この特別な場合は決定論的回路網を含
む。

決定論的コンピュータ回路網は、サーバまたはルータに
おけるパケットサービス時間（パケットを転送するため
の時間）が確率変数ではないような回路網である。異な
るサーバにおけるパケット当りのサービス時間は異なり
得るが、各サーバにおいて時間は固定されている。解析
的には、これらの回路網はｍ　Ｄ　／　Ｄ　／　１サー
バの閉じた待ち行列回路網によってモデル化することが
できる（但し、ｍはパケット及びそれらの肯定応答が回
路網を通して１往復する時に通過する待ち行列の数であ
る）。これらの回路網においては、遅延対ウィンドウ曲
線は膝折点において交わる２本の直線セグメントからな
る。膝折点の前においては遅延は一定であり である。ここにｔ８はｉ番目のサーバのサービス時間で
ある。膝折点の後においては遅延は線形に増加する。即
ち Ｄ　（Ｗ）＝Ｗｔ。

但しｔ、はボトルネックサーバのサービス時間、即ち １ｈ　＝１　　　（１ｍ） である。衛星リンクのような固定遅延サーバは最大値決
定に含まれないが、加算には含まれる。上述の遅延に関
する２つの式は１つにまとめることができる。

パワーは膝折点において最大となり、 または １に 最適ウィンドウサイズに関するこの式により、経路の膝
折点容量を計算することができる。即ちあるノードにお
いて実行される混雑回避手順は以下の３つの質問に返答
する必要がある。即ち、（１１ウインドウサイズを増加
させるのか、または減少させるのか？これは“決定関数
”である。

（２）ウィンドウサイズに如何に大きい変更をなすべき
か？これは“増加／：＄ｉ少”アルゴリズムである。

（３）ウィンドウサイズに如何に屡々変更をなすべきか
？これは“決定頻度”と呼ばれる。これらの３戒分はま
とまって、ユーザポリシーと呼ばれるものを形成する。

本発明による遅延ベース手順は、前記関連出願の方法の
ような他の混雑回避方法を同時に使用することも可能で
あるが、以下に説明するように回路網は混雑回避方法に
明快に関与しないので回路網ポリシーは有していない。

手順の決定関数はあるノードにおけるウィンドウ調整の
方向を決定する。正規化された遅延勾配ＮＤＧを決定関
数として使用することができる。

決定論的回路網の場合には、膝折点の左までＮＤＧはＯ
である。ウィンドウＷ及びＷｏｌｄにおける往復遅延を
それぞれＤ及びＤｏｌｄとすれば、決定関数は単にＮＤ
Ｇが０であるか否かを検査することからなる。このアル
ゴリズムを以下に述べる。

Ｄ　−Ｄｏｌｄ　　　　　　　　Ｗ　＋　ＷｏｌｄＩＦ
（ＮＤＧ＞δ　ｏｒ　　Ｗ＝Ｗ＠ＩＩＸ　）Ｔ　ＨＥ　
Ｎ　　Ｄｅｃｒｅａｓｅ　　（Ｗ）ＥＬＳＥ　　　ＩＦ
（ＮＤＧ≦δ　ｏｒ　　Ｗ　＝　Ｗｌｌ！ＩＩ　）Ｔ　
ＨＥ　Ｎ　　Ｉｎｃｒｅａｓｅ　　（Ｗ）　　；上記ア
ルゴリズムにおいて、δは回路網設計者によって選択さ
れるしきい値である。

等のしきい値を所望の動作点に依存して使用することが
できる。Ｗ、７及びＷ□８はウィンドウの下限及び上限
である。上限は受信ノードのローカルバッファ可用性考
察に基いて該ノードによって許容される流れ制御ウィン
ドウに等しくセットされる。下限は、ウィンドウをＯま
で減少させることができないので１より大きいかまたは
等しい。

Ｗ　ｍ　ｉ　ｎ≧１ Ｗ□８≧Ｗ　＋ａ　ｉ　ｎ Ｗ１１１＝Ｗ□８にセットすることによって、ウィンド
ウ調整を不能にすることができる。ウィンドウは決定点
毎に増加または減少させなければならないことに注意さ
れたい。ウィンドウを一定に留めることはできない（Ｗ
□７＝Ｗ□８にセットすることによって手順が不能化さ
れた場合を除く）回路！ｉｉ′！Ｌ荷は絶えず変動して
いるからこれが必要なのであり、またもしあれば勾配の
変化を可能な限り速やかに検出するようにすることが重
要である。また遅延の変化（Ｄ−Ｄｏｌｄ）がＯである
か否かを検査する代りに、比較はＮＤＧがＯであるか否
かであることに注目されたい。これら２つの条件は同等
であるが、ＮＤＧは無次元量でありその値は遅延がナノ
秒、ミリ秒、秒または他の何れの時間単位で測定されて
も同一に保たれるので、後者が好ましい。遅延の差は、
その単位を適切に操作することによって任意に小さく　
（または大きく）見えるようにすることができるが、Ｎ
ＤＧはこれらの操作の影響を受けない。

この手順は、任意のウィンドウ値で始動する複数の利用
者に公平さと収束をもたらす最も簡易な選択肢である加
法的増加及び乗法的減少アルゴリズムを使用する。即ち
、もしウィンドウを増加させるのであれば、それを加法
で行う。

Ｗ−Ｗ＋△Ｗ 減少の場合にはウィンドウに１より小さい係数を乗する
。

Ｗ＝　ｃ　Ｗ、　　ｃ　＜　１ パラメタ△Ｗ及びＣは、システム動作点が膝折点に接近
した時に振動の振巾及び周波数に影響する。これら２つ
のパラメタの推奨値は△Ｗ＝１及びｃ＝０．８７５であ
る。

加法的増加及び乗法的減少を選択したのは以下の理由か
らである。もし回路網が膝折点以下で動作中であれば全
ての利用者はそれらのウィンドウサイズを等しく増加さ
せるが、もし回路網が混雑していれば乗法的減少はより
大きいウィンドウを有する利用者からはより少ないウィ
ンドウを有する利用者より多く減少させ乙ので割当てを
より公平にする。０．８７５＝１−２−’であることに
注目されたい、即ち、乗算は浮動小数点ハードウェアな
しに、単なる論理シフト命令によって遂行できる。増加
／減少パラメタの前記推奨値は振動を小さくし、また実
現が容易である。計算は最も近い整数に丸めるべきであ
る。丸めの代りに切捨てると公平さにや・欠けるように
なる。

手順の“決定頻度”成分は、如何に屡々ウィンドウサイ
ズを変更するかの決定を援助する。余りにも屡々変更す
ると不要な振動がもたらされ、−方変更頻度が低いとシ
ステムが順応するのに長時間を要してしまう。汎用シス
テム制御理論によれば、最適制御頻度はフィードバック
遅延、即ち制御の適用（ウィンドウサイズの変更）とこ
の制御に対応する回路網からのフィードバックの入手と
の間の時間に依存する。第１図に示す如きコンピュータ
回路網においては、制御に影響する、即ち新ウィンドウ
が実現されるためには１往復を必要とし、またその結果
として回路網から変更を行ったノードヘフィードバンク
される変化を入手するまでに別の往復遅延を生ずる。混
雑回避システムの動作を第３図に示す。第３図はデータ
バケット及び肯定応答の流れを時間に対して示してある
。

第３図において、時刻１＝０より前はウィンドウサイズ
ＷはＷｅ　　（図ではＷｏ　”２パケツト）であり、ｔ
＝ＱにおいてウィンドウサイズはＷｌ（図ではＷ、＝３
パケット）に変更されている。１＝０から３パケツトが
送られ、ｔ＝Ｄ０からこれらの３パケツトに対する肯定
応答が源ノードに到着し始める。時刻ｔ＝Ｄ０＋Ｄ、に
は、時刻ｔ　＝　Ｄ　。

から送られた３パケツトに対する肯定応答が到着し始め
る。

あるパケットが経験する遅延は、そのパケットが送られ
る前に使用されたウィンドウサイズの関数である。遅延
Ｄ０はＷｏの関数であり、遅延Ｄ１はＷ、の関数である
。従ってこれから、ウィンドウは２往復遅延（２ウイン
ドウターン）毎に１回調整すべきであり、また最も新し
いサイクルに受けたフィードバック信号だけをウィンド
ウ調整に使用すべきであると結論付けられる。

以上に概説した手順においては、１つ置きの遅延測定は
破棄されている。これは情報を若干失うことになるが、
簡単な変更によって避けることができる。各パケットが
経験する遅延は、既に回路網内にあるパケットの数の関
数である。通常この数は、ウィンドウ変更点を除いて、
現ウィンドウに等しい。往復遅延測定のために送信時刻
が記録されているパケットに対して、もし送信時に未決
の（送られたが肯定応答されていない）パケットの数Ｗ
。ｕＬも記録すれば、遅延りと数Ｗ。ｕｔは１対ｌの一
致を有する。従って何れかの２つ（ｗｏｕｔ　、　　Ｄ
）の対を用いてＮＤＧを計算することができる。この変
更によりウィンドウを往復遅延毎に更新することができ
る。情報が多ければ回路網変更に速いレスポンスがもた
らされる。

初期化に関してこの手順は、ノードが新たに回路網に接
続される時に使用するウィンドウ値には何等の要求も設
定しない。この接続で任意ウィンドウサイズでの移送を
開始することができ、結局は手順が負荷を膝折点レベル
に持って行く。それにも拘わらず、最小ウィンドウ値か
ら始動することが推奨される。何故ならばこれは、既に
回路網を使用しているかも知れない他の利用者に最小の
影響しか与えないからである。

種々の遅延ベース混雑回避選択肢の性能を表わすシミニ
レ−ジョンモデルが使用された。これと同一のモデルは
、１９８６年１０月のＩＥＥＥジャーナル・オン・セレ
クテッド・エリャズ・イン・コミュニケーションズの１
１６２〜１１６７ページに所載のタイムアウトベース混
雑制御方法の評価に、及び前記関連出願（これは１９８
８年８月のカリフォルニア州スタンフォード。

Ｐｒｏｃ、　ＡＣＭ　　Ｓｉｇｃｏｍｍ　’　　８８に
も記載されている）の二元フィードバック混雑回避方法
の評価に既に使用されている。このモデルによれば若干
の地上及び衛星リンクを有し、任意の合理的な数の利用
者、中間システム、及びリンクを有する汎用コンピュー
タ回路網のシミュレーションが可能である。

第４図及び第５図を参照する。衛星リンク及び若干の地
上リンクを有する回路網形態がシミュレートされた。即
ちこの回路網は第１図の回路網に類似し、リンク１３．
１７等の１つ、衛星リンク及び他のワイヤまたは光フア
イバリンクを有している。現在使用されている最大の回
路網は一般に、衛星リンクを介して一緒に接続されてい
る若干の広域通信網（ＷＡＮ）及び構内通信網（ＬＡＮ
）からなり、まとまって“超大域通信網”即ちＶＬＡＮ
を形成している。シミュレートされた回路網の待ち行列
モデルは、２．５．３、及び４単位時間の決定論的サー
ビス時間を有する４サーバからなり、衛星リンクは６２
．５単位時間の固定された（ウィンドウには無関係の）
遅延によって表わされている。全てのサービス時間は源
サービス時間に対するものであり、従って源のサービス
時間は１である。この回路網の場合、ボトルネックサー
バのサービス時間ｔ、＝５であり、またΣｔ、＝７７．
５である。もしこの回路網内の合計パケット数がＷであ
れば、遅延りは Ｄ−最大（７，５，５Ｗ） で与えられる。第４図に示すように遅延曲線の膝折点は
Ｗ膝折点−７７，５／　５　＝　１５．５にある。

例示手順を使用したシミュレーションから得られた時間
の関数としてのウィンドウサイズのプロットを第５図の
実線曲線で示す。第５図では１６回以内のウィンドウ調
整によってウィンドウは最適値（破線で示す〉に到達し
、次で１２と１６との間との値の間で振動している。４
サイクル毎にウィンドウ曲線は値１３で（値１２ではな
く）上方に転じている。これは、送られたパケットの実
際の数が最寄りの整数であっても、ウィンドウ値は実数
として維持されるからである。

第６図に地上広域通信網である別の例を示す。

この構成は、衛星リンクが存在しないことを除けばＶＬ
ＡＮ回路網に類似する。この回路網は第１図に類似して
いる。即ち、パケットは源ノードと宛先ノードとの間の
複数のルータ１１．１４及び１８を通過し、肯定応答パ
ケットも同様にこれらのルータまたはサーバを通過する
。４つのサーバのサービス時間は２．５．４及び３時間
単位（源に対して〉である０回路網内を循還するＷパケ
ットに伴う遅延はＤ＝最大（１５，５Ｗ）であり、遅延
曲線の膝折点はＷ膝折点＝３にある。第６図はこの例示
手順を使用して得たウィンドウ曲線であり、この場合も
ウィンドウサイズは膝折点を中心として振動している。

第７図から、手順が回路網構成の変化に伴ってリンク速
度を変化させて応答していることが分る。

コンピュータ回路網はリンクがダウンまたはアップして
絶えず再構成される。混雑回避手順がこれらの動的状態
に応答するか否かの試験として入力バケソト流を３つの
部分に分割する。中央部分中、ボトルネックルータ速度
は３倍まで変化し、最適ウィンドウサイズは１５．５か
ら５．１７まで変化する。流れの第３の部分ではボトル
ネックサーバ速度は元に戻り、ウィンドウ曲線は再び最
適値の１５．７まで戻っている。第７図において、最適
ウィンドウは破線で示されており、また例示手順を使用
して得たウィンドウは実線で示してある。この手順が最
適値の変化に密接して追随していることが分る。

性能の別の尺度は公平さである。第８図は２利用者を有
するＶＬＡＮ回路網の性能を示す、この場合利用者当り
の最適ウィンドウは７．７５であり、図示のように両利
用者は６と８との間で振動するウィンドウを有している
０合計（両者の和〉ウィンドウは１２と１６との間で振
動している。

第９図から、ウィンドウサイズが始動時のウィンドには
関係なく膝折点容量に収束していることが分る。この手
順は回路！ｉ１ｍ戒の変化に応答して順応するから、利
用者が始動する場合の初期ウィンドウは無関係である。

第９図に示すように、たとえ極めて高いウィンドウから
始動しても、利用者は迅速に膝折点まで降下する。

この手順は激しい混雑の下で収束を呈する。第１０図の
ウィンドウ曲線は９利用者を有する高度に混雑した広域
通信網（ＷＡＮ）を示す。経路の膝折点容量は３にしか
過ぎない。前式を用いて計算された利用者当りの最適ウ
ィンドウは１／３である。最小ウィンドウサイズは１で
あるから、これらの利用者は１及び２のウィンドウサイ
ズの間で振動を保ち、合計ウィンドウは９と１８との間
で振動している。多くの他の決定関数は、この構成の場
合には発散をもたらすので適当ではない。

発散する場合には利用者はそれらのローカルパワーを最
適化する（単にＮＤＧが０であることを検査するのでは
なく〉ことを試みる。利用者はそれらのローカルパワー
を最適化するために、ウィンドウを少なくとも他の利用
者のウィンドウの和程度に大きくする必要があることを
見出す。これは、利用者の平均ウィンドウを際限なく増
加させ続けることになる。

以上に説明した本発明による手順は、少なくとも決定論
的回路網において、以下に列挙するような多くの長所を
有する混雑回避方法を提供する。

１、　回路網オーバベツドがＯ：サーバまたはルータの
ような中間システムにはオーバベツドは存在しない。中
間システムはそれらの負荷または待ち行列長を測定する
必要がないので、中間システム（ルータ、サーバ等）の
資源をノードへのフィードバットではなくパケット転送
に専用することができる。

２６　　新パケット不要：源クエンチ方式またはチョー
クパケット方式とは異なり、この遅延ベース方式は過負
荷または低負荷中に回路網内に如何なる新パケットをも
注入する必要がない、従って本混雑回避方式自体によっ
て付加的な負荷が付課されることはない。

３、パケットヘッダの変更不要：本発明の手順はパケッ
トヘッダを如何様にも変更する必要がない。全ての回路
網及びプロトコルはそれらの現存するパケット書式と共
に使用することができる。

４、分散制御Ｂ　：本手順は分散しており（制御はある
ノード自体のみにおいて付課され、中央制御装置からで
はない）、如何なる中央監視機器も用いずに働らく。

５、　ダイナミズム：回路網は絶えず変化している。

即ち回路構成及びトラフィックは絶えず変化し、ノード
及びリンクはアップまたはダウンし、利用者によって回
路網に配置される負荷は多様に変化する。従って最適動
作点は絶えず移動する目標である。本発明の手順は負荷
を最適動作点の若干下及び若干上に変化させることによ
って回路網を動的に監視し、フィードバックを観測する
ことによって現状態を確認する。

６、最小の振動：ウィンドウサイズの振動の振巾を最小
にするために、増加量に１、また減少係数に０．８７５
が選択されている。

７、収束：もし回路網構成及び作業負荷が安定に留まっ
ていれば、本手順は回路網を安定動作点に持って行く。

８、情報エントロピ：これはフィードバック情報の最適
使用に関する。目的は最小量のフィードバンクを用いて
最大量の情報を輸送することである。暗示フィードバッ
ク（何れにしても肯定応答パケットは送らなければなら
ず、その遅延は回路網または情報流に何物をも付加する
ことなく存在する）を使用することによって、本手順は
如何なる物理ビットをも付加することなく若干のビット
に情報の価値を与えることができる。

９、無次元パラメタ二次元（長さ、質量、時間）を有す
るパラメタは一般に回路網速度または構成の関数である
。無次元パラメタはより広い適用性を有する。ウィンド
ウ更新頻度、ウィンドウ増加量、及びウィンドウ減少係
数は全て無次元である。最小遅延または最大勾配のよう
なパラメタを必要とする選択肢は次元を有し、若干の帯
域中及び広がりの回路網にのみ有効であろう。

１０、構成の独立：ノードは回路網構成、ホップまたは
ブリッジの数、衛星リンクの存否等の予備知識を必要と
しない。

上述したように、本発明による手順はウィンドウベース
流れ制御メカニズムに集中している。しかし、上述した
混雑回避アルゴリズム及び概念は、回路網負荷に影響を
与える何等かの回路網チューニングパラメタを調整する
ことによって如何なる回路網にも適用可能であり、また
アルゴリズムは源が宛先によって規定された最大レート
（パケット／秒またはバイ１フ秒で表わされた）よりも
低いレートで送らなければならないレートベース流れ制
御のような他の形の流れ制御に容易に変更可能であるこ
とから、ウィンドウベース手順が必要条件ではない。ま
た説明した手順においては多分、パケットが明示的にま
たは暗示的に肯定応答された場合（肯定応答ビットによ
ってまたは送られたパケットによる要求に対する応答に
よって）にのみ往復遅延が推定できるものと仮定してい
る。しかし、全てのパケットが肯定応答される必要はな
く、送られた若干のパケットのみに対する肯定応答を受
信すれば充分である。殆んどのネットワーキングアーキ
テクチャは１つのタイマだけを使用して往復遅延を測定
するので多くのパケットは未解決となるがそれで充分で
ある。

説明した混雑回避のための遅延ベース手順は種々の選択
肢及び付加物に従って補うことができる。

例えば、ウィンドウサイズに関して別の決定関数を使用
することができる。第２に、決定を行う上で別の情報を
付加することができる。または、第３に、概念を確率的
回路網に拡張することができる、また別の最適性基準を
使用することができる。

以下にこれらに関してそれぞれ概述する。

決定関数としてＮＤＧのみを使用する代りに別の決定関
数を使用することができる。他の可能性は（１）切片、
（２）切片／勾配比及び最小ウィンドウにおける遅延で
ある。切片決定関数は、２つの異なるウィンドウ値を与
えると、（Ｄ＝ａＷ＋ｂ）の形の直線を適合させ得るこ
とに頼っている。但し、ａは勾配であり、ｂは線の切片
である。膝折点の前では切片は遅延りに接近し、一方膝
折点の後では切片は０に接近する。切片／勾配比決定関
数の使用は、比ｂ　／　ａが膝折点の前では大きいが、
膝折点の後では極めて小さいことに頼っている。最小ウ
ィンドウにおける遅延関数は、膝折点の前では遅延がＷ
＝１における遅延に接近しているが、膝折点の後ではＷ
＝１における遅延の数倍であることに基く、若干のＭ／
Ｍ／１サーバの閉じた待ち行列回路網としてモデル化で
きる回路網においては、膝折点における遅延は、何等の
待ち合せをしない場合の遅延の約２倍である。即ち、も
しＷ＝１における遅延を測定すれば、ウィンドウは遅延
がこの量の２倍になるまで増加させ続けることができる
。ＮＤＧ、切片、勾配及び最小遅延の他の若干の組合せ
も決定関数を定義するために使用できることは明白であ
る。

単なる往復遅延の代りに別の情報も使用することができ
る。前述した手順においては、あるパケットが回路網内
のどの経路を通ったのかに関する知識はないものとして
純ブラックボックス方法に従っていた。しかし、ある場
合には別の情報を使用することができ、決定手順への補
助として有用ならしめることができる。これらの情報の
例は、（１１ノードの数、及び（２）最小遅延である。

これらの各情報の効果を以下に検討する。

もし経路を共用するノードまたは利用者の数ｎが知れれ
ば、ローカルパワーを使用して社会的最適値の近くに到
達することができる。もし各利用者が利己的最適値によ
って予測されるウィンドウの１／（２ｎ−１）しか使用
していなければ、即ち であれば、何れかの初期状態から始まってウィンドウは
結局は公平な、社会的に最適値に収束するので ｎを静的に選択することが可能であり、或はそれを回路
網管理者によって設定される回路網パラメタとすること
もできる。この場合、実際の利用者の数がｎ以下である
場合の期間中は性能はやや亜最適であり、利用者の数が
ｎを超える期間中は本機構は発散し得る。この発散は限
界Ｗ１．８を設定することによって制御することができ
る。

もし最小遅延（何処においても待ち合せることなく経路
を通る際の遅延）が知れれば、回路網上の他の利用者の
現負荷は現遅延から推定することができ、これから社会
的最適条件を近似することができる。遅延・ウィンドウ
曲線の勾配は、もし０でなければ、ボトルネックサービ
ス時間に比例し、最小遅延は全てのサービス時間の和に
等しい。

これらの２つによって経路の膝折点容量を計算すること
ができる。Ｗｉ＝１における遅延と最小遅延との差は回
路網上に配置されている他の利用者による負荷に比例す
る。従って任意ノードにおいて、その利用者の負荷の割
当て分は社会的最適を達成するように計算することがで
きる。多くのネットワーキングアーキテクチャはそれら
の速度に基いてコストを回路網リンクに割当て、このコ
スト割当てを使用して最適経路を選択している。極めて
高速のリンクを有する回路網においては、経路の最適性
を決定するのはリンク速度ではなくスイッチングノード
のサービス時間である。従って、もし全てのサーバ（リ
ンク及びスイッチ）のパケットサービス時間に基いてそ
れらにコストが割当てられていれば、ある経路のコスト
が最小遅延の尺度であろう。

以上に決定論的回路網の例に基いて本発明の手順を説明
したが、本手順は各サーバにおけるパケット当りのサー
ビス時間が確率変数である確率的回路網に拡張できる。

もしサーバのサービス時間が確率分布を有する確率変数
であれば、往復遅延もまたランダムになる。従って遅延
に基いての決定はある確率で誤りををする。この状況を
解決するために若干の選択肢が７を在する。即ち、＋１
１信号浦波、（２）決定濾過、（３）順次試験、及び（
４）目標変更である。これらのそれぞれに関して以下に
説明する。

信号濾波は１つの選択肢である。ランダムサービス時間
の状態への遅延ベース手順の拡張は、任意のウィンドウ
における若干の遅延サンプルを取り、ＮＤＧの平均及び
確イ３間隔を推定することである。しかし直線濾液に関
して、遅延が確率変数ではなく、ランダム過程であるこ
とを理解しなければならない、確率変数は、時間と共に
変化しないパラメタを有する確率分布関数を特徴とする
。

ランダム過程はそのパラメタが時間と共に変化する確率
分布関数を特徴とする。これらの変化は回路網構成また
は負荷の変化によってもたらされる。

確率過程が定常でない限り、時間平均（異なる時点に取
られたサンプルの平均）は空間平均（同一時点に取られ
た若干のサンプルの平均）と同一ではない。何れの場合
にも全ての平均化は、最新のサンプルが古いサンプルよ
りもより大きい衝撃を意思決定に与えるようにすべきで
ある。従って同一のウィンドウのために取られた全サン
プルの直接加算に対して指数的に重みを付けた平均化が
好ましい。

決定濾過は別の選択肢である。ランダムさを処理するこ
の方法は、それぞれ単一のサンプルに基く若干の（例え
ば２に＋１）決定を行う。全ての決定は同一ではないで
あろう、ある決定は利用者に増加を求めるであろうし、
またある決定はウィンドウを減少させることを求めよう
、最終的に取られる動作は多数決によって指示されるこ
とになる。誤りの確率はｋを増加させることによって最
小にすることができる。ｐを、１つのサンプルに基く正
しい決定の確率としよう、従って２に＋１サンプルに基
く正しい決定の確率は となる。同様に正しくない決定の確率はである。この場
合も決定は“古きを排す”ことができ、最新の決定に対
してそれより前の決定より品い重みをり、えることがで
きる。

第３の選択肢は順次試験である。上記遅延ベース手順の
決定論的バージョンにおいては、ＮＤＧがＯであるか否
かの検査が行われる。確率的バージョンにおいては、こ
れは特定された確信レベルを用いた統計的仮定試験に変
更される。順次試験手順は、ｋサンプルの後に試験要求
がｊけ加、減少すること、または更に１つのサンプルを
採取することであるように提唱されている。

第４の選択肢は目標変更である。決定論的場合には膝折
点の左における遅延・ウィンドウ曲線のＮ１）Ｇは０で
ある。これは確率的場合には必ずしも真ではない。例え
ば、あるサイクル内にｈの同−Ｍ／Ｍ／１サーバの平衡
回路網の場合には、そのサイクル内に循還する ｉ＝１ である。但しｔ、は各サーバのサービス時間である。こ
の場合には遅延曲線は１本の直線であり、曲線上に膝折
点は見当らない。しかし数学的には膝折点は以下のよう
にして決定できる。システムパワーは である。

このパワーは の時に最大となる。

最適点においては、何処においても待ち合せがない回路
網の平均最小遅延をＤｏとしてＤ＝２ｈｔｂ＝２Ｄｅが
保たれる。従って、この遅延とＮＤＧではなく最小遅延
との比が、このような場合に関する膝行点のより良き標
識である。

上記解析において仮定したサービス時間の指数分布だけ
が解析に便宜を与える。殆んどの実際の回路網において
は、サービス時間は指数分布によって暗示されるよりも
晶かに小さい分散を有する。

従来のサービス時間の可変性をパケットのバイト毎の処
理に使用する１つの理由は、サービス時間がパケット長
に比例していたからである。回路網設計における現在の
傾向はこのような処理法から離れることであり、パケッ
トサービス時間は定数分布により近づき、指数分布から
離れている。

最適性を定義するために使用可能な別の基準が存在する
６例えばＰｒｏｃ、　ＩＥＥＥ　Ｉｎｆｏｃｏｓ＋　’
　８４の８７〜９４ページでＪ、　Ｍ、　　セルガが提
唱した新パワー関数は、遅延が最小遅延の倍数（例えば
２倍）である時にその最大値が得られる。これは経路の
最小遅延を知る必要があるが、もし最小遅延を知ること
ができれば前述した遅延ベース方式に拡張することが可
能である。

繰り返すが、回路網を通る往復遅延はその回路上の負荷
の暗示標識であり、これらの遅延を使用することによっ
て異種混合通信回路網における混雑回避のための手順が
提供される。たとえ異種混合回路網においても、この手
順は、明示混雑フィードバックを供給することができな
いアーキテクチャ層で動作しないブリッジのような資源
における混雑フィードバックの問題を解消する。またこ
の手順は回路網自体へのオーバベツドを０にする望まし
い特性をも有する。以上に説明した手順は、源が回路網
上のそれらのｆＬｒｉＩを制御するために使用できる唯
一のフィードバックとして往復遅延を使用する例示手順
である。始めに述べたように、本手順を決定論的回路網
即ちパケット当りのパケットサービス時間が一定である
回路網において説明中である。因みに、多くの異なる決
定論的構成及びシナリオは、本手順が回路網構成の変化
に対して集束、公平、最適及び順応することを示してい
る。本手順における重要な論点は利己的最適対社会的最
適である。利己的最適を達成し発散をもたらす競走状態
に至らしめる選択肢は回避される。

サービス時間がランダムであり、また利用者が共働する
のではなく競争するような回路網において本手順を実現
するには付加的な考察を必要とするが、それでも概念は
保持される。確率的回路網を含む実施例においては、ゲ
ーム理論概念の使用及び回路網に関する付加情報の使用
によって本発明の範囲内で変形手順が得られる。

第１１図において、一実施例における各ノード１０ａ−
１ｏｎ、または他のノード１５ａ＝１５ｎまたは２０ａ
〜２０ｎは、システムバス２３によって通イ３アダプタ
２２に結合されているＣＰＵ２１またはプロセッサ装置
からなる。バス２３は同一のアドレス／データバス及び
ＣＰＵが主メモリ及びこのような他のローカル資源にア
クセスするために使用する制御バスを含むことができる
。

アダプタ２２は通常、回路網プロトコルを取扱い、入バ
ケット友び出パケットを緩衝する。アダプタの構造は使
用する機器の型に依存して変化するが、通常はアダプタ
は送信／受信プロトコルを定義しパケットバッファメモ
リ２４ｂ内の入パケット及び出パケットを操作するため
に、ローカルメモリ２４ａからのコードを実行するロー
カルプロセッサ２４を含む。前述の遅延時間の測定は、
使用される特定のシステムに依存して、ＣＰＵ２１によ
ってまたはローカルプロセッサによって実行されるタイ
マアルゴリズムを使用することによって行われ、ウィン
ドウの最初のパケットが送られる時点が注目され、次で
最初の肯定応答の受信時点が注目され、その差が遅延時
間である。

以上に、あるノードによってｌバースト内に送られるパ
ケットの数を変化させることによって行われるウィンド
ウサイズの変更に暴くものとして制御を説明した。混雑
回避のこの概念は、ウインドウ当りのパケットではなく
パケットを送るレート（パケット／秒の形で）を変化さ
せるレートベース法にも適用できる。ウィンドウベース
方式で行うように（パケットを整数毎に）乗法的に減少
させ加法的に増加させる代りに、レートベース方式は乗
法的に、そして多分端数で増減させる。

第ｔｉ図のシステムにおいてリンク１２．１６または１
９上で送受信される通報パケットの典型的書式の１つの
型を第１２図に示す。パケット２５の正確な書式はリン
クで使用されるプロトコルに依存し、通常は同期部分２
６、ベツグ２７、情報フィールド２８、ＣＲＣフィール
ド２９及びトレーラ３０を含む。通常、同期部分及びト
レーラは通信アダプタ１１によって付加され、ベツグ２
７、情報フィールド２８及びＣＲＣはあるノードのため
のホストコンピュータまたはＣＰＵ２１によって生成さ
れる。フィールド２８は、数バイトからある実施例では
５１２バイトまで長さが可変の整数のバイトからなる。

パケットの各バイトは一般に、屡々マンチェスタコーデ
ィングまたは類似コードを使用して、リンク１２．１３
等にビット直列で伝送される。直列リンク上の伝送速度
は例えば、ローエンドイーサネットまたはツイストペア
線を使用するトークンリングシステムの場合は約１乃至
４Ｍビット／秒であり、光フアイバ結合を使用するＤＥ
Ｃ−Ｎｅｔ型のコンピュータ相互接続システムの場合は
７０Ｍビット／秒までまたはそれ以上である。同期部分
２６は複数の同期文字を含み、受信アダプタ２２に入通
報の始まりを認識可能ならしめ且つビット及び文字境界
で同期するクロ・どりを再生成するように機能する。

トレーラ３０は、源ノードによって生成され受信ノード
がヘッダ２７及び情報フィールド２８内の全ての機能を
計算して受信したデータの完全性を調べるために使用す
るＣＲＣを含む。トレーラ３０は、単に通報パケットの
終りを指定するように機能するだけの複数のトレーラ文
字で終る。

第１２図のパケット２５は使用される通信回路網の特定
の型に関して規定されているプロトコルに従って定義さ
れる。典型的実施例においては、パケット２５のへラダ
２７は、どの型の通報が伝送されるかを指定する型また
は指令フィールド３１、及びそれに続いて、バイト数で
表わされた通報の長さを指定する長さフィールド３２を
含む。

アドレスフィールド３３はＣＰＵｌ０（源ノードの）が
データを送ることを要求している宛先アドレスを指定す
る。源アドレス（データを送っているノードのアドレス
）はフィールド３４内に含まれる。アドレスフィールド
のサイズはある回路網において独特にアドレスできるノ
ードの数を決定する。これらのフィールド３１乃至３４
がパケットの“ヘッダを構成している。パケット２５内
のアドレスに続くのはデータフィールド２８であり、こ
れは０乃至５１２バイトの長さであることができる。肯
定応答パケットは第１２図のパケット２５と同じ書式で
あるが通常はデータフィールド２８の長さはＯであり、
肯定応答パケットの型フィールド３１は肯定応答のため
のあるコードを、また否定応答即ちＮＡＫのための別の
コードを有し得る。

第１図に示すような直列リンクに沿ってデータパケット
２５を輸送するために使用される媒体は、例えば同軸ラ
イン対であってよい。即ち、２本の同軸ケーブルが各ノ
ードを接続し、一方を送信用とし他方を受信用とする。

しかし、光ファイバまたはツイストペア線のような他の
媒体を代りに使用可能であることは理解されよう。また
、分離した受信ケーブル及び送信ケーブルを使用する代
りに、単一の送信／受信ケーブルまたはバスを使用でき
ることも理解されよう。同様に、前述したように、回路
網は通常他の回路網へのブリッジを含む。

本発明の特色を使用できるパケットデータ通信システム
の型の例は、合衆国特許４．７７７．５９５号、同４．
５６０，９８５号、同４，４９０，７８５、及び１９８
７年１０月１６日付関連出願、一連番号１０９，５０３
号、同１１０．００９号及び１１０．５１３号（何れも
ディジタル・エクィソプメント・コーポレーション）に
示されている。これらのコンピュータ相互接続システム
は、直列経路を使用してパケットデータ転送を行う型で
ある。これらの型のコンピュータ相互接続システムはＶ
ＡＸアーキテクチャのプロセッサ及び大容量記憶装置に
商業的に使用されており、高性能、高信頼性の汎用シス
テムを提供している。

他の商業的に使用可能な通信回路網には、メトカルフエ
らの合衆国特許４，０６３，２２０号に記載のいわゆる
イーサネットシステム、及びＩＥＥＥ８０２．５標準及
びＦＤＤＩ　　（ファイバ分布データインクフェース）
標準のようなトークンリングシステムが含まれる。これ
らの各通信システム、または構内通信網システムは、通
常は直列データで変調された搬送波を含む直列データ伝
送を使用する。勿論、以上に説明した概念は、それが直
列であろうとまたは並列であろうと、他の型のデータ転
送システムに等しく適用可能である。

以上に本発明を特定の実施例に基いて説明したが、この
説明は限定を目的としてなされたものではない。当業者
ならば説明した実施例の種々の夏更及び本発明の他の実
施例は明白であろう。従って、特許請求の範囲はこれら
の変更または実施例の何れをもカバーし、本発明の真の
範囲内に含まれることを企図しているのである。

【図面の簡単な説明】

第１図は本発明の特色を使用できるデータ通信システム
をブロックで示す回路図であり、第２ａ図乃至第２ｃ図
は第１図に示す如き回路網内の負荷（送られるパケット
数）の関数として処理能力、時間遅延及びパワーを表わ
す図であり、第３図は第１図のシステムにおけるパケッ
トデータ送信及び受信の事象対時間を示す空間・時間図
であり、 第４図は一実施例による回路網の遅延対ウィンドウサイ
ズのグラフであり、 第５図は本発明の手順を使用した時の一実施例における
ノードのウィンドウサイズ対時間のグラフであり、 第６図はノードが本発明の手順を使用した別の実施例に
おける第５図に類似のウィンドウサイズ対時間のグラフ
であり、 第７図乃至第１０図はノードが本発明の手順を使用した
他の実施例における第５図及び第６図に類似のウィンド
ウサイズ対時間のグラフであり、第１１図は第１図のコ
ンピュータ相互接続システムに使用されるアダプタ１１
の１つをブロックで示す回路図であり、 第１２図は第１図のコンピュータ相互接続システムに使
用できるパケット書式の一実施例の図である。 １０、　１５．２０・・・・・・ノード、１１、　１４
．　１ ８・・・・・・ルータまたはサーバ等の通信アダプタ、 １７．１９・・・・・・リンク、 ２、　１３．　１６゜ １・・・・・・ＣＰＵ。 ２・・・・・・通信アダプタ、 ３・・・・・・システムバス、 ４・・・・・・ローカルプロセッサ、 ４ａ・・・・・・ローカルメモリ、 ４ｂ・・・・・・パケットバッファメモリ、５・・・・
・・パケット、 ６・・・・・・同期部分、 ７・・・・・・ヘッダ、 ８・・・・・・情報（データ）フィールド、９・・・・
・・ＣＲＣフィールド、 Ｏ・・・・・・トレーラ、　　　３１・・・・・・指令
フィールド、２・・・・・・長さフィールド、 ３・・・・・・宛先アドレスフィールド、４・・・・・
・源アドレスフィールド、５・・・・・・膝折点、　　
　３６・・・・・・圧点。 釧 ＼ Ｌ　　　　　　　　　　　　　　　　　　　　Ｊウィン
ドウサイズ ウィンドウサイズ ウィンドウサイズ ウインドウサイズ ウィンドウサイズ ウィンドウサイズ 手 続 補 正 書 （方式） ％式％ １、事件の表示 平成２年特許願第２２９５３０号 ３、補正をする者 事件との関係 出 願人 ４、代 理 人 願書に最初に添付した明細書及び 図面の浄書（内容に変更なし）

Claims (1)

1. 【特許請求の範囲】 １、第１のノードを含む複数のノードを有し、前記第１
   のノードによるデータの伝送が回路網に付課されるロー
   ディングのレベルに影響を及ぼすチューニングパラメタ
   を特徴とするデータ通信回路網に使用される混雑回避方
   法であって、ａ）第１のノードから宛先ノードへ第１の
   データ群を送信し； ｂ）第１のデータ群の送信の直前に第１のノードによっ
   て送信されたデータによって回路網に付課されるローデ
   ィングを表わす第１のローディング値を決定し； ｃ）第１の群内の少なくとも若干のデータが宛先によっ
   て受信されたことの肯定応答を第１のノードにおいて受
   信し； ｄ）第１のデータ群の送信と、対応肯定応答の受信との
   間の時間遅延である第１の時間遅延を測定し； ｅ）チューニングパラメタを変更し； ｆ）第１のノードから宛先ノードへ第２のデータ群を送
   信し； ｇ）第２のデータ群の送信の直前に第１のノードによっ
   て送信されたデータによって付課されるローディングを
   表わす第２のローディング値を決定し； ｈ）第２の群内の少なくとも若干のデータが宛先によっ
   て受信されたことの肯定応答を第２のノードにおいて受
   信し； ｉ）第２の群の送信と対応肯定応答の受信との間の時間
   遅延である第１の時間遅延を測定し；ｊ）（１）第１の
   遅延時間と第２の遅延時間との相対差、及び（２）第１
   のローディング値と第２のローディング値との相対差の
   間の比を計算し；ｋ）もし前記比が所定値より小さけれ
   ば爾後に第１のノードによって送信されるデータによる
   ローディングを増加させるようにチューニングパラメタ
   を変更し、もし前記比が前記所定値より大きければロー
   ディングを減少させるようにチューニングパラメタを変
   更する 諸段階を具備する方法。 ２、チューニングパラメタは、第１のノードが一時に送
   信できるデータパケットの最大数に等しいウィンドウサ
   イズである請求項１記載の方法。 ３、チューニングパラメタは、第１のノードがデータを
   送信できる最大ビットレートである請求項１記載の方法
   。 ４、チューニングパラメタは、第１のノードがデータを
   送信できる最大パケットレートである請求項１記載の方
   法。 ５、第１及び第２のローディング値がそれぞれ、第１及
   び第２の群を送信する直前にデータを送信する時に第１
   のノードによって使用されるウィンドウサイズである請
   求項２記載の方法。 ６、第１及び第２のローディング値がそれぞれ、第１の
   ノードが、第１及び第２の群を送信する直前にデータを
   送信したビットレートである請求項３記載の方法。 ７、第１及び第２のローディング値がそれぞれ、第１の
   ノードが第１及び第２の群を送信する直前にデータを送
   信したパケットレートである請求項４記載の方法。 ８、コンピュータ回路網における混雑回避方法であって
   ： ａ）ある源からの第２のデータの送信とある宛先からの
   肯定応答の受信との間の遅延を測定し； ｂ）前記源による前記データのローディングを異ならせ
   た前記源からの第２のデータの送信と、前記宛先からの
   肯定応答の受信との間の遅延を測定し； ｃ）前記測定された遅延の差に応答して前記源によるロ
   ーディングをある最適値に変更する諸段階を具備する方
   法。 ９、ローディング変更段階が、源によって送信されるデ
   ータのパケットの数即ちウィンドウサイズか、または源
   によって送信されるパケットのレートの何れかを変更す
   ることを含む請求項８記載の方法。 １０、送信が、複数のデータのパケットを回路網の１つ
   のノードから回路網の別のノードへ伝送することを含む
   請求項８記載の方法。 １１、ローディング変更段階が、パケットの数またはレ
   ートを減少させるか、またはパケットの数またはレート
   を増加させることを含む請求項１０記載の方法。 １２、ローディング変更段階が、ウィンドウサイズ、ま
   たはビットレート、またはパケットレートの相対変化の
   関数としての測定された遅延の相対変化にも応答する請
   求項１１記載の方法。 １３、データ通信回路網においてノードを制御する方法
   であって： ａ）前記回路網の前記ノードから選択されたウィンドウ
   サイズまたはレートを使用してある宛先ノードへ第１の
   データを送信し； ｂ）前記ノードにおいて前記宛先ノードからの前記デー
   タの肯定応答を受信し； ｃ）第１のデータを送信する前記段階と第１のデータの
   肯定応答を受信する前記段階との間の遅延時間を測定し
   ； ｄ）前記回路網の前記源ノードから第１のデータを送信
   する時に使用したものとは異なるウィンドウサイズまた
   は異なるレートを使用して前記宛先ノードへ第２のデー
   タを送信し；ｅ）前記ノードにおいて前記宛先ノードか
   らの前記第２のデータの肯定応答を受信し； ｆ）第２のデータを送信する前記段階と第２のデータの
   肯定応答を受信する前記段階との間の遅延時間を測定し
   ； ｇ）前記第１及び第２の測定された遅延時間を比較し； ｈ）前記比較段階に応答してウィンドウサイズまたはレ
   ートを増加または減少させる 諸段階を具備する方法。 １４、データが複数の分離したパケットで送られる請求
   項１３記載の方法。 １５、ウィンドウサイズを増加または減少させる段階が
   、整数のパケット単位である請求項１４記載の方法。 １６、データ通信回路網が複数のノードを含み、諸段階
   が前記各ノードにおいて独立的に遂行される請求項１３
   記載の方法。 １７、ウィンドウサイズまたはレートを増加または減少
   させる段階が、最小の遅延時間で最大の処理能力を呈す
   る動作点を与えることである請求項１３記載の方法。 １８、ノードが直列リンクによってルータまたはサーバ
   に接続されている請求項１６記載の方法。 １９、複数のノードを有するパケットデータ通信回路網
   における混雑回避の方法であって： ａ）前記回路網内のある源ノードから選択されたウィン
   ドウサイズまたはレートを使用してある宛先ノードへ、
   複数のパケットを含むデータを送信し； ｂ）前記源ノードにおいて、前記宛先ノードからの前記
   データの肯定応答を受信し； ｃ）前記送信段階と前記受信段階との間の遅延時間を記
   録し； ｄ）前記回路網の前記源ノードから、前記選択されたウ
   ィンドウサイズまたはレートとは異なるウィンドウサイ
   ズまたはレートを使用して前記宛先ノードへ再びデータ
   を送信し； ｅ）前記源ノードにおいて、前記宛先ノードからの前記
   データの肯定応答を再び受信し； ｆ）前記記録した遅延時間と、前記再送信段階と前記再
   受信段階との間の遅延時間とを比較し； ｇ）前記比較段階に応答してウィンドウサイズまたはレ
   ートを増加または減少させて最小の遅延時間で最大の処
   理能力を呈する動作点を得る 諸段階を具備する方法。 ２０、データが複数の分離したパケットで送られる請求
   項１９記載の方法。 ２１、ウィンドウサイズを増加または減少させる段階が
   、整数のパケット単位である請求項２０記載の方法。 ２２、コンピュータ回路網において混雑回避を供する装
   置であって：ある源からのデータの送信とある宛先から
   の肯定応答の受信との間の遅延を測定し、前記源による
   前記データのローディングを異ならせて再度ある源から
   のデータ送信とある宛先からの肯定応答の受信との間の
   遅延を測定する手段；及び前記測定された遅延の差に応
   答して前記源によるローディングを最適値に変更する手
   段を具備する装置。 ２３、ローディング変更手段が、源によって送信される
   データのパケットの数を変更する請求項２２記載の装置
   。 ２４、送信手段が、回路網の１つのノードから少なくと
   も１つのルータを通して回路網の別のノードへ複数のデ
   ータパケットを伝送する請求項２２記載の装置。 ２５、データ通信回路網内のノードを制御する装置であ
   って：選択されたウィンドウサイズ及び前記選択された
   ウィンドウサイズとは異なるウィンドウサイズのデータ
   を前記回路網の前記ノードからある宛先ノードへ送信し
   、前記ノードにおいて前記宛先ノードから前記送信され
   たデータの肯定応答を受信する送信機／受信機手段；前
   記選択されたウィンドウサイズにおける前記送信と受信
   との間の遅延時間と、前記第２のウィンドウサイズにお
   ける前記送信と受信との間の遅延時間とを比較し、前記
   比較に応答して爾後のデータ送信のウィンドウサイズを
   増加または減少させる手段を具備する装置。 ２６、ウィンドウサイズが各々整数のデータパケットか
   らなる請求項２５記載の装置。 ２７、比較手段は、前記遅延比較の結果が遅延に差が存
   在しないことを示した時にはウィンドウサイズを増加せ
   しめる請求項２６記載の装置。