JPH0657017B2 - 輻湊制御型パケット交換方法及びその装置 - Google Patents

Description

【発明の詳細な説明】 （発明の背景） ［発明の属する技術分野］ 本発明は、利用者が過度のレートで情報を伝送すること
によって生じる交換節点とリンクでの輻湊を制御するパ
ケット交換方法およびその装置に関する。

［従来技術の説明］ パケット通信は、交換ネットワークの送信端末で情報を
分離したデータバーストすなわちパケットに分解する技
術と、ネットワークの受信端末でデータパケットから同
一の情報を再び組立てる技術を含む。この技術に基づく
通信は、共通搬送波あるいは、時間分割交換システムに
特に有用である。これは、パケットの伝送に必要とする
通信路あるいは回路が各パケットがネットワークを通し
て転送される際だけ必要とされて、それ以外の期間は他
のユーザも利用できるからである。

パケット交換は、別の魅力のある特徴をもつ。それは、
多くの応用、例えば、対話的データ、バルクデータ、シ
グナリング、パケット化された音声、画像など、に対し
て総合情報伝送サービスを提供するという柔軟性であ
る。特殊の利用形態を最適化する特殊なネットワークを
設計する代わりに、多くのサービスはネットワークへの
同一の接続を介して同時に行われる。各種のユーザ情報
は、パケットに変換されて、ネットワークはこれらのパ
ケットをユーザの間で伝送する。エンドユーザは、固定
レートの接続に束縛されない。その代わり、ネットワー
クの接続はエンドユーザの個々の要求に順応する。ま
た、広範囲のサービスに適応する一様なユーザ−ネット
ワークインタフェースを作ることも可能である。種々の
応用によって、程度の異なるサービスを要求しうること
は注意すべきである。例えば、パケット化された音声の
伝送は対話中の関連するパケットの配達に対して、非常
にきびしい遅延条件を有する。

ネットワークの資源の有効利用は、複数ユーザのパケッ
ト化された伝送を時間分割に基いて、同一の接続手段に
おくことによって達成できる。従ってあるユーザのパケ
ットは他のユーザのパケットの間に入り込み、一緒に散
在している。

このようなパケット網で共有しうる資源または設備の諸
元は、伝送リンク帯域幅（バイト／秒を単位として定義
され、リンク容量の度合を表す）、プロセッサの実時間
（すなわちパケットを処理するためのすぐ利用できる時
間）、ポート（リンク）およびデータ（パケット）バッ
ファを含む。多節点の大ネットワークでは、各節点また
はパケットスイッチは、多くのこのようなポートあるい
はリンクを調節し、これらはユーザの端末装置あるいは
他の節点まで広がっている伝送路を終端する。各節点は
そこを通過するパケットの経路指定と処理を制御するた
めに、プロセッサを有する。通常、節点に多くのバッフ
ァが装備され、このバッファが経路指定の前または出力
リンクを待つ間、パケットを蓄積する。節点間あるいは
ユーザの間まで広がる各回線は異なる端末装置の間に同
時発生した複数の呼を取扱う。ネットワークを通過する
各パケットは各節点である程度のプロセッサ実時間を消
費し、ある程度のリンク容量（パケットの大きさに比例
する）を取去る。また、処理される間、バッファも使用
する。単位時間当たりネットワークが取り扱えるパケッ
トには最大の数がある。この“容量”という概念はネッ
トワーク内に用意されている前記のすべての資源および
ユーザによって生じる特別のトラヒック混合に依存す
る。

多数のユーザが同時にネットワークを利用しようとする
時、一つの問題がパケット交換システムに起こる。これ
はパケットの経路指定のために多数の伝送路または回線
が形成され、通信設備が輻湊するという問題である。設
備の輻湊とは発生するワーク数が設備の一定の時間内に
処理できるワーク数より多いという現象である。輻湊が
制御されなければ、ネットワーク内に広がっていくこと
が知られている。従って、フロー／輻湊制御機構が、各
々のサービスタイプ（例えば音声）に対して期待される
性能レベルを他のサービスタイプにより生じた予測でき
ないトラヒックの過負荷から保護することが望まれる。
過負荷からの保護は重要な資源の配分によって得られ
る。重要な資源がトラヒックによって過負荷になる場合
では、システムの総合性能はできるだけ徐々に下がるこ
とが望ましい。重要な資源の利用の制御は、過負荷状態
と正常負荷状態とでは違うものを要求しても良い。

パケットに輻湊が発生する主な領域は、各節点のバッフ
ァ（すなわち待ち行列）であり、特にバッファが入力パ
ケットを蓄積できなくなる場所においてである。バッフ
ァの要求はプロセッサの実時間およびリンクの利用と密
接に関連する。プロセッサの実時間が使い尽される場
合、または、リンク帯域幅がパケットトラヒックを処理
するのに十分でない場合は、交換節点での待ち行列は長
い遅延を招く。最後にパケットバッファは使い尽され
て、結局パケットのドロップとなってしまう。いくつか
のフロー制御処理、例えばエンドツーエンドウィンドウ
方式は、輻湊制御のために開発されて商品化されてい
る。

フロー制御用として知られているエンドツーエンドウィ
ンドウ方式はネットワークの動作を厳密にネットワーク
の周囲から観察するとき有利である。各装置は、それ自
身と種々の他の装置との間に設定されている多数の論理
通信路を同時にもつことができる。これらの各論理通信
路に対して特定の装置はネットワーク内に存在している
Ｗ個の未応答パケットをもっても良い。例えば、装置は
最初にＷ個のパケットを所望の速さでネットワークに伝
送できるが、少なくともそれらの未決のパケットのうち
の１つに対して着局装置から受領応答を受取るまで待た
なければならず、その後、初めて他のパケットを伝送で
きる。

この方式はいくつかの非常に望ましい特性を有する。フ
ロー制御機構によって生じるむだなリンク帯域幅はほと
んどない。これは、受領応答のビット数をそれと関係す
るＷ個のパケット内のビット数よりかなり少なくするこ
とができるからである。また、反復の遅延が増加する
と、受領応答、従ってトラヒック源を遅くするため、重
負荷状態では、伝送の自動抑制機能を有する。

エンドツーエンドウィンドウフロー制御には欠点もあ
る。ウィンドウ機構それ自身は充分強固ではない。この
機構は合意した窓の寸法に忠実である端末ユーザに依存
する。悪意のユーザは、窓の寸法を一方的に増加して、
自分に有利な性能が得られるが同時に他のユーザに対し
ては性能を下げてしまう。すべてのユーザが規定された
エンドツーエンドウィンドウの寸法に従っても、種々の
負荷条件に対して適切な寸法を決めることは非常に困難
である。一般的に、ウィンドウの寸法Ｗはネットワーク
が軽負荷のとき、連続伝送ができるように充分大きく運
ぶが、過負荷の場合では、パケットスイッチ内に許容で
きない程大量のバッファ記憶容量を要求する。エンドユ
ーザは、ネットワークの輻湊状況に基づいてウィンドウ
の寸法を適度に調節できるが、これだけでは、必ずしも
良い輻湊制御を与えない。

エンドツーエンドウィンドウ式機構の他の欠点はすべて
の合意したユーザがウィンドウに基づくエンドツーエン
ド制御に従属するわけではないことである。例えば、あ
るウィンドウに基づくプロトコルの番号のついていない
情報（Unnumbered Information）の伝送、例えばＬＡＰ
Ｄ、はエンドユーザがウィンドウの制限なしに、パケッ
トを送出することを許す。他の例として、パケット化さ
れた音声またはパケット化された音声帯域データの応用
例であり、そこにはエンドツーエンドウィンドウ方式は
適用できない。

総合的な音声／データパケットネットワークにおけるフ
ロー／輻湊制御の適切な方法が提案されている。それ
は、帯域を接続に割当てることと、必要とされる帯域幅
が利用できるときだけ新しい接続を作ることである。

これはネットワークがユーザに、帯域幅の要求を選択
し、ユーザの伝送のバースティネス（集中発生の度あ
い）を表示する機構を提供しなければならないことを意
味する。従って、ネットワークはそれらのパラメータを
それぞれのユーザに対して押しつけなければならない。

帯域配分の重要な部分は、必要な帯域幅を選択し、特定
する機構およびユーザを自分の選択に制限する機構であ
る。最も簡単なアプローチはいわゆる“漏れやすいバケ
ツ”法である。接続に伝送している各ユーザ端末と関連
する度数計の数はユーザがパケットを送出するたびに増
加し、それ以外は周期的に減少する。ユーザは度数計の
減少レート（これは平均帯域幅を決める）としきい値
（バースティネスを表す数）を選択する。度数計にある
数値がしきい値を越えるとネットワークはそのパケット
をドロップする。

この“漏れやすいバケツ”帯域配分の提案には問題があ
る。主な問題は制御が本質的にオープンループであるこ
とである。ユーザのパケットは、一旦しきい値を超える
と、ネットワークがこのパケットを処理できても、ドロ
ップされてしまう。貴重なネットワーク資源は浪費され
る。そのユーザのデータに対する不必要な抑制は情報伝
送に対して長期間続く。これは後のネットワークの輻湊
の原因となる。他の問題は制限となるネットワークの資
源がリンク帯域幅よりプロセッサの実時間である可能性
が高いことである。

（発明の概要） これらの問題および他の問題はパケット交換ネットワー
クにおける輻湊を制御するための新しい方法と装置によ
って解決できる。この方法はパケットドロッピングアル
ゴリズムを用いてネットワークを通して伝送されている
マークされたパケットをいくつドロップするかを決め
る。マークされたパケットはデータパケットを伝送する
伝送路に沿ってネットワークのどこか１ケ所が輻湊すれ
ばドロップされる。パケットを監視し、マークするのに
用いられる方法は本願と同一の出願人による同日の出願
（特願昭６２−３３０３９１号）の明細書に記載されて
いる。

（実施例の説明） 第１図を参照すれば、端末装置間の仮想回線接続を設立
するために用意されたパケット交換ネットワーク２０が
示されている。端末２１と２２はデータパケットを顧客
の接続回線２５と２６を通してパケットマルチプレクサ
２８に伝送する。ドロップ列で表される他の端末（図示
せず）は、データパケットをマルチプレクサ２８に伝送
できる。端末２１と２２は、計算機端末として図示され
ているが、ディジタル音声、ビテオまたは、他のデータ
端末であっても良い。互いに多重化されているパケット
の出力ストリームは入力回線２９を通してマルチプレク
サ２８からパケット交換ネットワーク２０内の入力節点
３０へ伝送される。別の入力回線３３およびドット列で
表示される他の入力回線もデータストリームを入力節点
３０に伝送する。これらの入力回線のあるものはマルチ
プレクサから始まり、他の入力回線は高速端末装置から
始まる。

一般にパケット交換ネットワークは交換節点とリンクと
からなる非常に複雑なネットワークであるが、本発明の
配置を説明するために、５つの交換節点３０、４０、５
０、６０および７０だけを第１図に示す。第１図では節
点３０だけが顧客の端末装置からパケットを受け取る入
力接点として配置されている。他の節点はいずれもオペ
レーティングシステムの入力節点となっても良い。ネッ
トワーク２０に入力接点と図示されていないのは図面を
簡潔化するためだけである。節点６０は第１図に出力節
点として示される。他の接点も出力節点であってもかま
わないが、図面を簡潔化するために第１図に図示しな
い。出力節点６０からパケットストリームは出力回線６
１と６２およびドット列で表されている他の回線を通し
てディマルチプレクサまたはユーザの装置に伝送され
る。第１図を簡潔化するために一つのディマルチプレク
サ６３だけが示されている。出力回線６１を通して伝送
されるデータパケットのストリームはディマルチプレク
サ６３でユーザの識別子により分離される。従ってユー
ザの特定のパケットはそれぞれユーザ接続回線６５、６
６を通してユーザ端末６７と６８に伝送される。パケッ
トストリームはディマルチプレクサ６３から他のユーザ
回線と端末にも供給される。それらの他の回線と端末は
第１図にドット列で表される。

データ交換ネットワーク２０の動作を示すために、典型
的な仮想接続は太く描いた伝送路で示される。それは端
末装置２１と端末装置６７をつなぐ伝送路である。この
ような仮想接続における典型的な伝送は、双方向である
が、第１図に端末装置２１からネットワーク２０を介し
て端末装置６７への一方向の伝送だけを示す。この仮想
回線接続はマルチプレクサ２８と入力回線２９から入力
節点３０、交換節点４０および５０、回線７２、７４お
よび７６、出力節点６０および出力回線６１を通してデ
ィマルチプレクサ６３に設置されている。

ネットワーク２０は輻湊制御が出来るように構成されて
いる。回線とスイッチはすべてのパケットに対して限界
まで妨げられず、伝送できるように多数用意されてい
る。ネットワーク２０内のどこでも十分発生しうる輻湊
は長期間続くならば、パケット数の増加するのを妨げ
る。従って、輻湊はネットワーク内に広がってしまっ
て、ネットワークを有効に動作できないようにしてしま
う。

本実施例に示される有利な輻湊制御方式は、選択された
顧客のデータパケットを監視し、マークして、輻湊状態
になったら、いつ、どこかを問わずにネットワークを介
してマークされたデータパケットを以降の伝送から除
去、すなわちドロップする。この制御方式は連続的なパ
ケットストリームが仮想接続を通して進行するとき、ネ
ットワーク内の多くの時刻と場所で個々のデータパケッ
トに作用するアルゴリズムによって実施される。各々の
顧客または端末ユーザはネットワークの異なる顧客に多
重仮想接続しても良い。監視およびマーク方式は仮想回
線ごと、仮想回線群ごと、または、顧客ごとで実施でき
る。

以後の説明を簡単化するために、一人の顧客につき一つ
の仮想回線しかないと仮定する。従って以後では、顧客
と仮想回線という用語は同意語となる。

第１のアルゴリズムは、顧客の帯域幅を監視してそれが
予約された帯域幅を超えると同顧客のパケットをマーク
するものである。この状況において、帯域幅は、回線帯
域幅または、プロセッサ実時間が制限付き資源であるか
否かということを区別するために、二次元の量として定
義されても良い（単位バイト／秒、パケット／秒）。予
約された帯域幅は平均レート（寸法一定のパケットをも
つユーザが獲得できると保障されているバイト／秒単位
でのスループット）とバースティネス因子（バースティ
ネスの程度は、例えば、伝送レートのピークと平均との
比率およびピーク伝送の持続時間である）によって記述
される。この第１のアルゴリズムは入力節点３０の受信
側でも用いられる。入力回線２９から受け取った各パケ
ットはヘッダに、パケットが属する仮想回線接続を識別
する情報を含む。従って、種々のパケットはレジスタに
蓄積されて、特定の仮想回線と同一視される。

端末装置２１から送出されて、入力節点３０によって受
け取られたパケットヘッダからの情報は第１図の帯域幅
を監視し、およびパケットをマークする回路８０に入力
される。

第２図を参照すれば、提案した帯域幅を監視し、および
パケットをマークする機能を顧客ごとの基準で実行する
回路８０のブロック図が示されている。第１図の端末２
１からの発信と識別されて端末６７へ繋がる太く描かれ
た線路を通して伝送されるパケットからの情報は、アル
ゴリズムによって監視される。回路８０は他の仮想接続
に対して同一機能を実行するように時間的に分割されて
いるが、すべての監視およびマークは個々の仮想接続に
対して独立に行なわれる。

監視は、端末２１の顧客が端末６７まで延長されている
仮想接続を通して過度のレート（予約レートより高いレ
ート）で伝送しているかどうかを決めるアルゴリズムに
よって行なわれる。

図示された仮想接続が設置される際、顧客の端末装置２
１とネットワーク２０は仮想接続と関連する望ましい帯
域幅の割当てを協定する。帯域幅の割当ては選択すなわ
ち予約された伝送レートと呼ばれる。この予約された伝
送レートを超える情報の伝達は過度レートと呼ばれる。

アルゴリズム３０にあるプロセッサは予約された伝送レ
ートの割当てを長期しきい値Ｍ、短期しきい値Ｓと減少
定数Ｃに変換する。長期しきい値Ｍは、予約された伝送
レートが許容する最大のバースト寸法を調節するように
選択され、短期しきい値Ｓは許容される最大瞬時レート
によって決められる。減少定数Ｃはマークされていない
パケットの確保される平均スループットに関連する。こ
れらは、第２図に示されるように、間隔の終りにＣＯＵ
ＮＴとＴＨＲＥＳＨの値を更新するために仮想接続が設
置される際論理回路８１に入力される初期化パラメータ
である。これらは次に帯域幅を監視するおよびパケット
をマークする回路８０に使用される。アキュームレータ
８２のＣＯＵＮＴ値も最初にゼロとセットされ、アクテ
ィブしきい値Ｔも初めにＳと等しいようにレジスタ８３
にセットされる。また更に、初期化では、間隔つきのパ
ケット数と関連する重み因子を表すパラメータｋは論理
回路８４に入力される。この論理回路８４は過度伝送レ
ートで伝送されているパケットをマークするための信号
を発生する。各間隔の期間中に、第２図と第５図に図示
されるように、各々の到達しているパケットに含まれる
バイト数はリード８５を介して論理回路８４に供給され
るＢＹＴＥＳを蓄積するレジスタに入力される。回路８
４はこの特定のパケットを過度伝送レートで伝送されて
いるとマークすべきかどうかを決める。このパケットが
マークされるならば、マーク信号はリード８５に発生さ
れる。これはパケットを過度伝送レートで伝送されてい
るパケットであると識別するためにパケットのヘッダに
挿入される。パケットの伝送レートが予約された伝送レ
ートの範囲内にあるならば、マーク信号は発生されず、
またパケットヘッダに挿入されない。

本実施例では、パケットをマークするための３つのアル
ゴリズムが実例により記述される。他のアルゴリズムも
利用できる。

アルゴリズム（Ａ）と（Ｂ）に用いられるパラメータ Ｉ−アキュームレータのＣＯＵＮＴ値までの連続的な減
少量間の間隔。これは監視されている各仮想回線に対し
て一定の間隔であるが、仮想回路によって違うこともあ
る。Ｉの代表的な数値は１０〜５００ミリ秒の範囲にあ
る。

ｋ−アキュームレータのＣＯＵＮＴ値は顧客の端末から
送出された各パケットに対して、このパラメータおよび
パケットのＢＹＴＥＳ値で増加させる。パラメータｋは
確保されているスループットにある１パケットあたりの
バイトペナルティを表す。この確保されているスループ
ットは過度の極小パケットからのネットワークに対する
保護を提供する。保護がなければ、実時間資源を圧迫す
る。パラメータｋの典型的な値は０から１０００の間で
ある。ゼロに等しいパラメータｋの値は、プロセッサ実
時間が問題にならない場合に用いられる。

Ｃ−顧客が選択した間隔ごとのスループットに関連する
減少定数。各間隔にアキュームレータのＣＯＵＮＴ値は
この値を引く。すべての伝送されるパケットがマークさ
れないような、間隔毎の顧客のバイト数である。

Ｓ−各間隔のスループットに関する短期あるいはドロッ
プしきい値。これを超えるとパケットはマークされる。

Ｍ−許容できる“バースト”寸法に関連する長期帯域幅
しきい値。

ＢＹＴＥＳ−入力節点が顧客の端末から受取ったパケッ
トのバイト数。

ＣＯＵＮＴ−アキュームレータの値 ＴＨＲＥＳＨ−可変しきい値 帯域幅を監視し、パケットをマークするアルゴリズム
（Ａ） それらのアルゴリズムの一つであるアルゴリズム（Ａ）
は第３図に示され、それの図形例は第５図に示される。

アルゴリズム（Ａ）の初期化 １．アキュームレータ変数Ｃを０とセットする。

２．しきい値変数ＴをＳとセットする。

アルゴリズム（Ａ）のステップ １．各間隔中に、顧客の端末（第３図）から各パケット
を受取ったならば ａ．バイト数変数ＢＹＴＥＳをパケットのバイト数にセ
ットする。

ｂ．ＣＯＵＮＴの値をＴＨＲＥＳＨの値と比較して、以
下の動作を行う。

ＣＯＵＮＴ＜ＴＨＲＥＳＨならば、パケットをマークせ
ずに通過させて、ＣＯＵＮＴの値をＣＯＵＮＴ＋ＢＹＴ
ＥＳ＋ｋで置換える。

ＣＯＵＮＴ≧ＴＨＲＥＳＨならば、パケットをマークし
て通過させて、同一のＣＯＵＮＴ値を保つ。

２．各間隔の終りに（第４図） ａ．ＣＯＵＮＴの値をＣＯＵＮＴ−ＣかまたはＯのいず
れか大きいものに置換える。

ｂ．ＴＨＲＥＳＨをＣＯＵＮＴ＋ＳかまたはＭのいずれ
か小さいものに置換える。

第５図は縦軸はバイト単位のパラメータｋの値、現在の
パケットのＢＹＴＥＳ値、短期しきい値Ｓの値および長
期しきい値Ｍの値、しきい値変数ＴＨＲＥＳＨの値と減
少定数Ｃを表示する。水平軸は等間隔Ｉで時間分割され
ている。間隔Ｉは二つの時刻、例えば時刻t₀とt₁、の間
の持続時間である。水平軸に沿って数字列があるが、そ
れの各々は特定の到達するパケットを識別する。

パケットｋは第５図に実矢じりを有する上向きの矢印で
示される。これは仮想接続のすべてのパケットに対して
一定の値であり、典型値は０〜１０００の範囲内にあ
る。このアルゴリズムに従ってパケットが到達するたび
にＣＯＵＮＴはパラメータｋの値だけ増加される。

ＢＹＴＥＳ値は第５図に空の矢じりを有する上向きの矢
印で表わされる。これは、いくつかの到達するパケット
に対して種々の値を持つ。このアルゴリズムにより、Ｃ
ＯＵＮＴはパケットが到達するたびにＢＹＴＥＳ分だけ
増加される。但し、パケットがマークされる場合は、例
外である。

ＣＯＵＮＴの累算される値は第５図に水平の太線セグメ
ントで示される。

ＴＨＲＥＳＨの値は第５図に点線で表示される。

パケットが到達すると、ＣＯＵＮＴはＴＨＲＥＳＨと比
較される。ＣＯＵＮＴがＴＨＲＥＳＨより小さいなら
ば、パケットはマークされず、ＣＯＵＮＴは増加され
る。ＣＯＵＮＴがＴＨＲＥＳＨに等しいか、または、そ
れより大きいならば、パケットは、マークされて、ＣＯ
ＵＮＴは増加されない。

星印はマークすべきパケットの線（パラメータｋとＢＹ
ＴＥＳを表示する）の上にある。それらのパケットは過
度伝送レートで伝送されていると判定されたものであ
る。

減少定数Ｃは第５図に空の矢じりを有する下向きの矢印
で示される。これは、一定の値であり、ＣＯＵＮＴがゼ
ロ以下に減少されない限り各間隔Ｉの終りに現われる。

また第４図のアルゴリズムでは、ＣＯＵＮＴとＳの値と
の和はＭの値と比較される。その和がＭより大きいなら
ば、ＴＨＲＥＳＨはＭとセットされる。その和がＭより
小さい、またはＭと等しいならば、ＴＨＲＥＳＨはＣＯ
ＵＮＴとＳの値との和でセットされる。

一旦パケットをマークするかどうかが決定されて、それ
に対応してパケットのヘッダがマークされれば、パケッ
トは第１図の入力節点２０を通過して出力回線と関連す
る出力バッファに入れられる前に、出力制御装置に入
る。なお、パケットは出力回線を通じて伝送される。そ
の際、マーク信号のために確保されたヘッダフィールド
にある情報は、第１図の節点３０と連結されているパケ
ットドロッピング論理回路５３に転送される。パケット
ドロッピング論理回路５３のより詳細なブロック図は第
６図に示される。

第６図と第７図に現在のパケットをドロップするかどう
かを決定するロジックのブロック図とアルゴリズムが示
されている。上記のパケットは第１図の入力節点３０の
出力バッファまたは第１図の交換節点４０、５０、６０
および７０のどれかの出力バッファに入力される。

トラヒックは仮想接続沿線の節点３０、４０と６０では
軽ないし中程度であると仮定する。

しかし、交換節点５０でのトラヒックは十分激しく輻湊
状態をひき起こしている。

まず、パケットドロッピング論理回路５３と５４は第７
図のアルゴリズムを実行する。それらは軽く負荷されて
いる節点３０、４０と連結されており、第６図の論理回
路５５と同様である。これらの節点では輻湊がないた
め、およびテストされるとき、出力バッファが一杯でな
いため、現在のパケットはマークされたかどうかと関係
せずに、仮想接続に沿って関連する節点の出力バッファ
に回されて伝送を待つ。

次にパケットは輻湊している節点５０を通る。パケット
はリード９１を通ってパケットドロッピング論理回路５
５のドロッピング回路９０に入力される。パケットがリ
ード９３を通って、それの識別されるパケット出力バッ
ファ９２に配置される前、そのバッファは一杯であるか
どうかチェックされる。バッファ９２が一杯であれば、
信号はリード９４を通ってドロッピング回路９０に転送
される。パケットがマークされたかどうかに関係せず、
出力バッファ９２が一杯であれば、パケットはドロップ
される。出力バッファが一杯であるかどうかと関係せ
ず、輻湊の測定がなされる。パケット出力バッファ９２
のパケット数はリード９５を通って輻湊測定回路９６に
入力される。同時にプロセッサ実時間の有効性を表す信
号はリード９７を通って輻湊測定回路９６に入力され
る。

リード９５と９７上の信号に応じて、回路９６はリード
９８に信号を発生し、第１図の節点５０での輻湊量を表
示する。リード９８上の輻湊信号とリード９９を通って
入力されるしきい値は、ドロッピング回路９０がマーク
されたパケットをドロップするかどうかを決める。パケ
ットをドロップすべきという信号はリード１００を通っ
て交換節点５０に送出される。パケットをドロップする
信号が現われたら関連したパケットはドロップされるか
（マークされたパケットの場合）または第１図の回線７
６による次の伝送のために出力バッファ９２に配置され
る（マークされていないパケットの場合）。

上述の処置はマークされたパケットを出力バッファに入
れる前にドロップする。この処置はパケットのドロップ
がバッファへの入力で行われるため、“入力ドロッピン
グ”と呼ばれる。あるいは、出力バッファにスペースが
あれば、全てのパケットをそこに入れてマークされたパ
ケットに対して“出力ドロッピング”を実施しても良
い。すなわち、出力バッファにあるマークされたパケッ
トは、最終的に待ち行列の先頭まで移動して出力の準備
ができたとき、しきい値はチェックされる。その結果に
応じて、パケットはドロップされるかまたは伝送され
る。

輻湊度はマークされていないパケットを通過させるため
に必要とするある程度の資源が節点に用意されていると
保証するように選ばれたしきい値である。出力バッファ
９２に入っているパケット数とプロセッサの利用できる
実時間の量との重みをつけた和は輻湊度を測定するに用
いられる。実時間の量はパラメータｋと関連している。
パラメータｋがゼロに等しいならば、実時間は問題にな
らない。その際、出力バッファにあるパケット数は輻湊
度の唯一の表示となる。

節点が輻湊しており、かつパケットがマークされたもの
である場合、パケットがドロップされるため、輻湊はあ
る程度軽減できる。ドロップされるパケットは前に入力
節点３０で過度伝送レートで伝送されていたとマークさ
れたパケットである。出力バッファが一杯ではない程度
の輻湊状態はマークされたパケットだけをドロップする
ことによって軽減できる。この状態では、マークされて
いないパケットは通過して目的地に送出される。

従って、輻湊は顧客の協定したあるいは割当てた伝送レ
ートを超えるレートで送信する顧客のパケットをドロッ
プすることによって、だいぶ軽減される。ネットワーク
は、従って、予約された伝送レート以下で送信するすべ
ての加入者に十分サービスできる。

帯域幅を監視するおよびパケットをマークする他の方
法、アルゴリズム（Ｂ） 第８図と第９図を参照すれば、そこにはマークすべきパ
ケットを決める他のアルゴリズムおよびそのアルゴリズ
ムが受取ったパケット列に対してどのように動作するか
図示されている。一番目のステップ（マークするステッ
プ）だけが前述の第３図と第４図に関して説明したアル
ゴリズムと異なる。初期化およびパラメータは同一また
は類似の意味をもつが、ＣＯＵＮＴの新しい値がＣＯＵ
ＮＴ値とＴＨＲＥＳＨ値と比較する前に決められる点が
異なる。ＢＹＴＥＳ値とパラメータｋとの和は比較する
前にＣＯＵＮＴに加えられる。次にＣＯＵＮＴの値がＴ
ＨＲＥＳＨの値より小さいと判定される時、パケットは
マークされずに通過する。

ＣＯＵＮＴの現在値は保持される。ＣＯＵＮＴがＴＨＲ
ＥＳＨに等しいかまたはそれより大きいならば、パケッ
トはマークされてから通過される。その時、ＣＯＵＮＴ
の値からＢＹＴＥＳとパラメータｋとの和が減算され
る。前述のパケットをマークするアルゴリズム（Ａ）と
同様にマークされたパケットは過度伝送レートで伝送さ
れているものと見なされる。

アルゴリズム（Ｂ）の初期化 １．度数計変数ＣＯＵＮＴを０とセットする。

２．しきい値変数ＴＨＲＥＳＨをＳとセットする。

アルゴリズム（Ｂ）のステップ １．顧客の端末から各パケットを受取る各間隔に（第８
図） ａ．バイト計数変数ＢＹＴＥＳをパケットにあるバイト
数にセットする。

ｂ．ＣＯＵＮＴの値をＣＯＵＮＴ＋ＢＹＴＥＳ＋ｋに置
換える。

ｃ．ＣＯＵＮＴの値をＴＨＲＥＳＨの値と比較して以下
の動作を行う。

ＣＯＵＮＴ＜ＴＨＲＥＳＨならばパケットをマークせず
に通過させる。あるいは、ＣＯＵＮＴ≧ＴＨＲＥＳＨな
らば、パケットをマークして通過させて、ＣＯＵＮＴ値
をＣＯＵＮＴ−ＢＹＴＥＳ−ｋに置換える。

２．各間隔Ｉの終りに（第４図） ａ．ＣＯＵＮＴの値をＣＯＵＮＴ−Ｃかまたは０のいず
れか大きいものに置換える。

ｂ．ＴＨＲＥＳＨをＣＯＵＮＴ＋ＳかまたはＭの小さい
ものに置換える。

第９図は第８図のアルゴリズムにより監視されるパケッ
ト列の結果を示す図である。パラメータｋとパケットの
ＢＹＴＥＳを表す。直線の上にある星印は過度レートパ
ケットとしてマークされるパケットを表示する。

特殊サービスパケットマーク 一種の新しいサービスは顧客に提供できる。この新しい
サービスの提供は以下の事実にもとづく。マークされた
パケットが輻湊状態あるいはフルバッファ状態に出会っ
たら、ネットワークはそれの場所と時間を問わずにマー
クされたパケットをドロップするように構成されてい
る。

この新しいサービスは低価格、いいかえれば、経済的な
レートのサービスである。この経済的なレートのサービ
スを予約すなわち選択すると、顧客は伝送したメッセー
ジが輻湊に出会ったら、目的地に配達されないという恐
れがある。操作装置（顧客の端末かまたは入力節点にあ
る）は、経済的なレートサービスを利用する顧客が送出
した各パケットをマークするようになっている。

従ってマークされたパケットはパケット交換ネットワー
クを通過する際、他のマークされたパケット同様に扱わ
れる。これらのマークされた経済的なレートサービスの
パケットは輻湊点を通るならば、すなわち、ネットワー
クのフルバッファに到着するならぱ、ドロップされる。
すべての経済的なレートのパケットがマークされるた
め、メッセージが繁忙のトラヒック状態では配達されな
い確率が高い。

軽トラヒックの時間帯では、輻湊もフルバッファもない
確率は高い。このような時間帯では、メッセージは第１
回目の試みで無事にネットワークを通過する。

この経済的なレートサービスは通信会社にも顧客にも有
利である。顧客は低レート料金により利益を受ける。通
信会社はこのサービスを利用する顧客がすいているトラ
ヒック時間帯に経済的なレートサービスのメッセージを
伝送しようとするために利益を受ける。このすいている
トラヒック時間帯に大部分の会社の装置はあいており、
多くの使われていない容量を利用できる。

輻湊制御 本発明に採用されたアプローチはパケット交換ネットワ
ークにおける輻湊制御に関する従来の技術に比べて、以
下の利点を有する。まずこのアプローチは顧客に情報ス
ループットの確保されるレベルおよびネットワークに依
存しうる余分の容量（ネットワークの輻湊の瞬時レベル
による）を利用して確保されるレベルを超えるような情
報スループットを実現する機会を与える。これは顧客に
確保し且つ期待されるスループットレベル、ネットワー
クを介して伝送する情報の完全性および異なるサービス
程度に対してネットワークの提供者に払う対応する料金
などのトレードオフの関係を有する要素に対して柔軟性
を与える。

次に、このアプローチはネットワークの提供者に顧客の
需要をかなえるように重要なネットワークの資源を提供
する面においてより大きな柔軟性を与える。ネットワー
クの資源は統計的に予測されたすべての顧客のピークト
ータル需要により、すべての顧客の確保される平均スル
ープットによるトータル需要（高いレベルの確実性をも
つ）をかなえるように提供できる。これはネットワーク
の資源を提供する際に要求される保守性を減らし、より
高い平均レベルのネットワークの資源の利用を与える。

最後に第１〜第９図に図示された輻湊制御は分散制御で
あり、これは入力節点でパケットを監視、マークする方
法および輻湊しているすべての節点でマークされたパケ
ットをドロップする方法を用いる。制御は、端末装置で
顧客に採用される操作から除去される。ネットワーク中
の制御の分散はネットワークの節点間の超低遅延信号機
構に対する要求をなくする。過度レートのパケットが入
力節点でドロップされるならば、この要求は必要とな
る。端末操作による制御を除去することによって他の制
御方式にある制御方式の完全な端末操作に依存しなくて
よい。制御の分散は制御に強さを与え、過度レートでパ
ケットをみだりに送出する顧客から、ネットワークおよ
び正しく使用する顧客を確実に保護する。

以上、過度レートで伝送されている、または、特殊の顧
客から伝送されているパケットを入力節点で受取ったと
き、マークする装置と方法および輻湊状態の時、マーク
されたパケットをネットワークのどの節点においてでも
ドロップする装置と方法を説明した。本明細書に記載さ
れる装置と方法および他の明らかにされた考えられる装
置と方法は特許請求の範囲にあると見なされる。

【図面の簡単な説明】

第１図は音声／データ／ビデオ端末の相互接続とネット
ワーク内の輻湊制御のためのパケット交換ネットワーク
を示す図、 第２図は顧客の伝送レートを監視するためのおよび顧客
のパケットをマークするための回路構成のブロック図、 第３図は伝送レートが過度となる場合、顧客の伝送レー
トを監視するおよび顧客のパケットをマークするアルゴ
リズムの流れ図、 第４図は、顧客の伝送レートを監視する度数計を周期的
に調節するためおよび顧客が選択した伝送レートと関連
する動的なしきい値を決定するためのアルゴリズムの流
れ図、 第５図は顧客からのパケットの順番に対する第３図と第
４図に示されたアルゴリズムの動作を示す図、 第６図は、ネットワーク内のマークされたパケットをド
ロップする回路構成のブロック図、 第７図は、ネットワークが輻湊する場合、マークされた
パケットをドロップするアルゴリズムの流れ図、 第８図は伝送レートが過度となる場合、顧客の伝送レー
トを監視するためのおよび顧客のパケットをマークする
ための他のアルゴリズムの流れ図、 第９図は顧客からのパケットの順番に対する第４図と第
８図に示されたアルゴリズムの動作を示す図である。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 デイヴィッド マイケル ルーカントニ アメリカ合衆国 07724 ニュージャージ ィ，イートンタウン，レッドウッド ドラ イブ 35 (72)発明者 タイバー ジョセフ ションフェルド アメリカ合衆国，07039 ニュージャージ ィ，リヴィングストン，タングルウッド ドライブ 45 (56)参考文献 特開 昭60−500935（ＪＰ，Ａ) デイビット・Ｃ・フリント著（松下 温 訳）ローカルエリアネットワーク入門 昭和59年12月15日 近代科学社 Ｐ．207 −221 ディジタルデータ交換網 第１部 交換 局編 概要（その３）パケット交換 中央 電気通信学園編 昭和54年２月16日 Ｐ. 296−298

Claims (11)

【特許請求の範囲】
1. 【請求項１】データのパケットの送信を準備するステッ
   プと、 パケットが送信される出力における交換節点の輻湊を評
   価するステップと、 輻湊が所定値以上であるか否かを判定するステップと、 パケットが、所定のドロップ可能型パケットとしてマー
   クされているか否かを判定するステップと、 パケットが所定のドロップ可能型パケットとしてマーク
   されており、かつ、輻湊が所定値以上である場合、その
   パケットを送信前にドロップするステップとからなるこ
   とを特徴とする、パケットがマークされたパケットであ
   る場合にパケット交換網内の交換節点から送信される予
   定のパケットをドロップする方法。
2. 【請求項２】輻湊が所定値未満の場合、ドロップされな
   かったパケットを出力に送るステップと、 所定のドロップ可能型のパケットとしてマークされてい
   ないパケットを出力に送るステップと、 送られたパケットを他のパケットと多重化するステップ
   と、 この多重化したパケットをリンクまたは端末線を通して
   送信するステップとをさらに有することを特徴とする請
   求項１の方法。
3. 【請求項３】所定のドロップ可能型パケットが、単一の
   所定のマーキングビットが１であるパケットであること
   を特徴とする請求項１または２の方法。
4. 【請求項４】所定のドロップ可能型パケットが、特殊サ
   ービスパケットであることを特徴とする請求項１または
   ２の方法。
5. 【請求項５】所定のドロップ可能型パケットが、少なく
   とも１人の所定の顧客の分割されたパケットであること
   を特徴とする請求項１または２の方法。
6. 【請求項６】所定のドロップ可能型パケットが、過大レ
   ートで送信されたパケットであることを特徴とする請求
   項１または２の方法。
7. 【請求項７】所定のドロップ可能型パケットが、任意の
   マークされたパケットであることを特徴とする請求項１
   または２の方法。
8. 【請求項８】パケットのマークが、前記交換節点とは異
   なる交換節点で実行されることを特徴とする請求項１ま
   たは２の方法。
9. 【請求項９】パケットのマークが、前記交換節点と同一
   の交換節点で実行されることを特徴とする請求項１また
   は２の方法。
10. 【請求項１０】前記準備するステップが、 パケットを出力バッファに入れるステップと、 パケットが出力バッファから送信される準備ができるま
    で待機するステップとをさらに有することを特徴とする
    請求項１、２、３、４、５、６、７、８または９の方
    法。
11. 【請求項１１】複数の受信ポートを有し、 相異なる受信ポートに接続され、イネーブルにすること
    が可能なマークビットを含むデータのパケットを連続し
    て送信する複数のチャネルと、 パケット交換節点の輻湊の測定に応答して、パケット交
    換節点における輻湊量を示す信号（９８）を発生する手
    段（９６）と、 発生された輻湊信号およびあるしきい値に応答して、イ
    ネーブルにされたマークビット（９０）を含むパケット
    をドロップする手段とからなることを特徴とするパケッ
    ト交換節点装置（３０、４０、５０、６０）。