JP3394478B2 - Ｒｅｄによる輻輳回避装置及びその方法 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、ＲＥＤによる輻輳
回避装置及びその方法に関し、特に、ＡＡＬ５を適用し
たＩＰオーバＡＴＭ方式によるネットワークにおいて、
ＲＥＤによる輻輳回避の実現方式を改良することにより
処理量を減少させたＲＥＤによる輻輳回避装置及びその
方法に関する。

【０００２】

【従来の技術】現在、個人レベル、企業レベルを問わ
ず、コンピュータ通信による情報の伝達が主流である。

【０００３】しかしながら、コンピュータ通信では、各
端末からのトラフィックが強いバースト性を持ち、又、
このトラフィックパターンを予め推定することが困難で
あるという問題が生じる。

【０００４】そのため、ネットワーク上の各中継交換ノ
ードにおいて輻輳状態が発生し、ネットワーク全体の通
信速度に遅延が生じる。

【０００５】そこで、ＡＴＭ網において上記のような弊
害を効率よく回避するために、従来のＣＢＲサービス、
ＶＢＲサービスのように予め帯域を割り当てる方法に替
わって、ＵＢＲサービス、ＡＢＲサービスのように予め
帯域を割り当てない方法により網内の輻輳度に応じて制
御を行うことで効率よく情報を伝送するベストエフォー
トサービスに関する議題がＡＴＭフォーラム等で論議さ
れている。

【０００６】この中でも、特にＵＢＲサービスにおいて
は、ＡＴＭレイヤで通信における品質保証を何ら行わ
ず、その代行手段として、輻輳回避を上位のレイヤの機
能、例えば、ＴＣＰである場合、ウィンドウフローコン
トロールによって行うため、低料金でコンピュータ通信
が行えるというメリットがあるため、今後の発展が大き
く望まれている。

【０００７】しかしながら、上記ＵＢＲサービスでは、
同一バッファサイズのパケットスイッチを用いた場合で
比較して、他のサービスよりパケットスループットが劣
化するといった問題が生じてしまう。

【０００８】この主な原因としては、ＡＴＭ方式による
通信では、輻輳状態を解消するために、パケット単位で
なくセル単位で廃棄が起こることが挙げられる。即ち、
廃棄されたセルを含むパケット（以下、不完全パケット
という）が到着した後に受信側において廃棄する制御を
行うため、送信側において再送制御が必要となることか
ら、不完全パケットを構成するセルが伝送路の容量を無
駄に消費するためである。

【０００９】また、ＡＴＭ方式では、一般的にセル廃棄
を実行した場合、廃棄されたセルが別々のパケットに分
布するため、多数の不完全パケットを生じるという問題
をも有してしまう。

【００１０】上記のような問題を解決する方法として、
インタネットプロトコル（以下、ＩＰという）の中継交
換ノードにおいて、輻輳の兆候が出始めた時点で通過す
るパケットの中から少ない廃棄率でランダムに選んで廃
棄するか、又は、パケットのヘッダ内の輻輳通知ビット
を立てることにより、一部のホストのアプリケーション
またはトランスポートプロトコルに輻輳の発生を通知
し、そのホストからの送出量の削減を誘導する方法であ
るRandom Early Detection（ＲＥＤ）方式による輻輳回
避がある。

【００１１】このＲＥＤによる輻輳回避は、従来技術文
献１とするSally Floyd, Van Jacobson による“Random
Early Detection Gateways for Congestion Avoidanc
e”,(IEEE/ACM Transaction on Networking, Vol.1 No.
4 August,1993.)により開示されている技術である。

【００１２】また、上記従来技術文献１には、廃棄する
パケットを決定するための方法として、廃棄するパケッ
トと次に廃棄するパケットとの間隔をランダムに決定す
ることにより破棄するパケットを特定する方法がさらに
開示されている。

【００１３】上記従来文献１により開示されたＲＥＤに
よる輻輳回避をここに説明すると、先ず、ＡＡＬ５では
セルレベルでパケットを認識するため、パケットを構成
する最後のセル、即ち、End Of Packet （ＥＯＰ）セル
（最終セルと同意）のＡＵＵパラメータを１、その他の
セルのＡＵＵパラメータを０とすることで、ＥＯＰを他
のセルと区別している。

【００１４】よって、ＡＡＬ５では、中継交換ノードに
おいて、１つのＡＴＭバーチャルサーキット（以下、Ｖ
Ｃという）に着目し、受信されたＥＯＰセルの次のセル
から観察して次に最初に受信するＥＯＰセルまでを同一
パケットを構成するセルと見なすことができる。

【００１５】しかしながら、上記のようなＥＯＰセルを
用いることによりセルレベルでパケットを認識する技術
に基づいたＲＥＤによる輻輳回避は、パケットのＥＯＰ
セルが廃棄された場合、次のパケットを構成するセルが
受信側に全て到達しても、直前のパケットと区別するこ
とが不可能となり、このため、ＣＲＣ符号等による誤り
検出が生じてしまい、全てのセルを受信したパケット
（完全パケット）まで廃棄してしまうといった問題が生
じる。

【００１６】又、上記従来技術１に対して、ＡＡＬ５を
使用したＩＰオーバＡＴＭ方式によるパケット廃棄方式
が、従来技術文献２とする鍋島正義による「End Of Pac
ketセル廃棄を防止する選択的セル廃棄方式に関する検
討」（SSE98-88,IN96-72,CS96-96）に開示されている。

【００１７】この従来技術文献２が開示するパケット廃
棄方式として、Early Packet Discard（ＥＰＤ）方式
と、Partial Packet Discard（ＰＰＤ）で使用される方
式と、ＥＰＤの改良方式とがある。

【００１８】ここで、ＡＡＬ５上のＩＰオーバＡＴＭ方
式では、１つのＩＰパケットは、複数のＡＴＭデータセ
ルに分割されて転送される。従って、ＡＡＬ５では、Ａ
ＴＭセルヘッダ部分に最終を示すビット（以下、最終ビ
ットという）が定義されている。

【００１９】従って、ＥＰＤ方式による輻輳回避は、中
継交換ノードにおいて輻輳が発生した場合、処理しきれ
ないパケットを廃棄することで輻輳状態を解消するため
の方式である。

【００２０】また、ＰＰＤで使用される方式では、先頭
セルが中継交換ノードに到着したとき、この中継交換ノ
ードにおいて輻輳状態である、即ち、中継交換ノードの
バッファに記憶されたキュー長が、予め設定された閾値
を超えている状態であれば、その先頭セル及び当該セル
から同一パケットを構成するセルを強制廃棄し、また、
輻輳状態でなければ、その先頭セルから同一パケットを
構成する最終セルまでを受信し、自身のバッファに入力
する。更に、バッファにセルを入力する過程において、
当該バッファに空き容量が無くなると、その時点から到
達した同一パケットを構成するセルの内、最終セル以外
を強制廃棄することにより、輻輳状態の緩和を図ってい
た。

【００２１】つまり、ＰＰＤで使用される方式では、分
割されたパケットの先頭セルを限定するか否かに関わら
ず、廃棄が必要と判断した時点から最終セルの一つ前の
セルまでを強制廃棄する処理を行っていた。

【００２２】また、このＥＰＤの改良方式では、パケッ
トを廃棄する場合、１つのＶＣに着目し、最終ビットが
オンであるセルの次のセル（以下、先頭セルという）か
らのセルの廃棄を始め、次の最終ビットがオンであるセ
ル（以下、最終セルという）までを廃棄している。

【００２３】更に、このＥＰＤの改良方式では、最終セ
ルを識別することにより、最終セルを破棄しない改良方
式が２種類提案されている。

【００２４】先ず、第１のＥＰＤの改良方式では、パケ
ットを構成する先頭セルが中継交換ノードに到着したと
きに直前のセルが最終セルでなければ、輻輳状態である
か否かに関わらず、次の最終セルの一つ前までのセルを
全て強制廃棄する。また、パケットを構成する先頭セル
が中継交換ノードに到着した時に直前のセルが最終セル
であり、且つ、輻輳状態である場合、次の最終セルの一
つ前までのセルを全て強制廃棄する。また、パケットを
構成する先頭セルが中継交換ノードに到着したときに直
前のセルが最終セルであり、且つ、輻輳状態でない場
合、次の最終セルまでの全てのセルを自身のバッファに
入力する。更に、バッファにセルを入力する過程におい
て、当該バッファに空き容量がなくなると、その時点か
ら到達した同一パケットを構成するセルの内、最終セル
以外を強制廃棄する。

【００２５】更に、第２のＥＰＤの改良方式では、輻輳
状態検知のための閾値に高閾値と低閾値との２種類を設
けることにより、バッファにセルを入力する過程におけ
るバッファの空き容量の不足によるセルの廃棄を防止す
る方法が取られている。

【００２６】

【発明が解決しようとする課題】しかしながら、ＲＥＤ
を上記したＥＰＤ方式又はＰＰＤ方式によるパケット廃
棄機能を使用して実現した場合、以下に挙げるような問
題が生じる。

【００２７】第１の問題点は、ＥＰＤ方式あるいはＰＰ
Ｄ方式では、分解して転送された一つのパケットをＡＴ
Ｍセル単位で廃棄することによりパケット全体を廃棄す
る方法（以下、パケットレベル廃棄方法という）を取る
ため、特定のＶＣを監視して、一つのパケットを分解す
ることにより作成されたＡＴＭセルを全て特定して廃棄
する必要が生じ、処理量が増加する。

【００２８】その理由としては、パケットレベル廃棄方
法を実現するためには、最終セルの検出、及び、次の最
終セルまでの一つのパケットを構成するセルを全て廃棄
するという、複数のセルに対する種類の異なる処理を実
行する必要があるからである。

【００２９】又、第１及び第２のＥＰＤの改良方式で
は、最終セルを捨てないための改良はなされているが、
ＶＣ単位にパケットを捨てる処理は残っており、逆に処
理量が増加するといった問題を生じる。

【００３０】その理由としては、ＲＥＤが、複数のコネ
クションを集約した全体を対象としているため、ＲＥＤ
をＩＰオーバＡＴＭに適用するためには、次に廃棄する
パケットを決定するフロー全体のＶＣを対象とした処理
と、廃棄対象のパケットが送られる特定のＶＣを処理対
象とするパケットレベル廃棄処理を組み合わせて行う必
要があるためである。

【００３１】さらに、上記ＥＰＤ及びＰＰＤ方式による
輻輳回避は、中継交換ノードにおいて輻輳が発生したこ
とが検出された場合に、輻輳状態が回復することを早め
るための手段である。それに対して、ＲＥＤによる輻輳
回避は、ＴＣＰの特性を利用することで、常時少ない確
率でパケットを廃棄し、ＴＣＰの送出量（送出レート）
が大きくならないようにするものである。

【００３２】従って、上記ＥＰＤ及びＰＰＤ方式と、Ｒ
ＥＤとは目的や構成・手段が異なるため、ＲＥＤをＥＰ
Ｄ及びＰＰＤ方式に適用すると、処理量が増加する等と
いう問題が生じる。

【００３３】従って、本発明は、上記問題に鑑みなされ
たもので、最終セル以外のセルをランダムに廃棄するこ
とにより、少ない処理でパケットの廃棄を可能とし、も
って、輻輳の抑制・制御を可能とするＲＥＤによる輻輳
回避装置及びその方法を提供することを目的とする。

【００３４】

【課題を解決するための手段】係る目的を達成するため
に、請求項１記載の発明は、プロトコルとしてＡＡＬ５
を適用したネットワークにおけるＲＥＤ(Random Early
Detection）による輻輳回避装置であって、最終セル以
外のセルを所定の確率により算出されたセル間隔を基に
特定し、特定されたセルを廃棄するセル廃棄手段を有
し、所定の確率は、１つのパケットが分割される平均の
セル数と、輻輳状態のレベルに対応したパケットの廃棄
率とを基に算出され、セル間隔は、所定の確率が近似す
ることができる２の巾乗分の１の値を求め、２の巾乗の
値を基に、０から２の巾乗の２倍の値までの範囲で等確
率の擬似乱数を作成し、擬似乱数を基に特定し、セル廃
棄手段は、セル間隔により特定されたセルが最終セルで
ない場合、特定されたセルを廃棄することを特徴とす
る。

【００３５】また、請求項２記載の発明は、プロトコル
としてＡＡＬ５を適用したネットワークにおけるＲＥＤ
による輻輳回避装置であって、回線より受信したセルを
一時保持するバッファリング手段と、バッファリング手
段が保持するセルのキュー長を算出するキュー長監視手
段と、キュー長監視手段により算出されたキュー長を基
に、輻輳状態の発生を判定する輻輳状態判定手段と、輻
輳状態判定手段により輻輳状態の発生が判定された場
合、到着したセルが最終セルであるか否かを判定する最
終セル判定手段と、最終セル判定手段により、到着した
セルが最終セルでないことが判定された場合、所定の確
率により算出されたセル間隔を基に特定し、特定された
セルを廃棄するセル廃棄手段とを有し、所定の確率は、
１つのパケットが分割される平均のセル数と、輻輳状態
のレベルに対応したパケットの廃棄率とを基に算出さ
れ、セル間隔は、所定の確率が近似することができる２
の巾乗分の１の値を求め、２の巾乗の値を基に、０から
２の巾乗の２倍の値までの範囲で等確率の擬似乱数を作
成し、擬似乱数を基に特定し、セル廃棄手段は、セル間
隔により特定されたセルが最終セルでない場合、特定さ
れたセルを廃棄することを特徴とする。

【００３６】また、請求項３記載の発明によれば、請求
項２記載のＲＥＤによる輻輳回避装置において、キュー
長監視手段は、所定の時間間隔毎に、バッファリング手
段におけるキュー長を検知し、検知したキュー長を基
に、最新のキュー長を含む平均のキュー長を算出するこ
とで、バッファリング手段が保持するセルのキュー長を
算出することを特徴とする。

【００３７】また、請求項４記載の発明によれば、請求
項２または３記載のＲＥＤによる輻輳回避装置におい
て、セルは、セルを構成するヘッダ部に、セルが同一パ
ケットを構成するセルの内、最終セルであるか否かを示
す最終ビットを有し、最終セル判定手段は、セルのヘッ
ダ部に含まれる最終ビットを基に、セルが最終セルであ
るか否かを判定することを特徴とする。

【００３８】また、請求項５記載の発明によれば、請求
項２から４のいずれかに記載のＲＥＤによる輻輳回避装
置において、閾値として所定のキュー長を記憶するキュ
ー長記憶手段をさらに有し、輻輳状態判定手段は、キュ
ー長監視手段により算出されたキュー長と、キュー長記
憶手段に記憶された所定のキュー長とを比較することに
より、輻輳の発生を判定することを特徴とする。

【００３９】また、請求項６記載の発明によれば、請求
項２から４のいずれかに記載のＲＥＤによる輻輳回避装
置において、閾値として所定のキュー長を、異なる値で
複数記憶し、複数の所定のキュー長に対応する輻輳状態
のレベルをさらに記憶するキュー長輻輳レベル記憶手段
をさらに有し、輻輳判定手段は、キュー長監視手段によ
り算出されたキュー長と、キュー長輻輳レベル記憶手段
に記憶された複数の所定のキュー長とをそれぞれ比較
し、比較の結果、キュー長監視手段により算出されたキ
ュー長が超えた所定のキュー長の内、最も大きな値であ
る所定のキュー長に対応する輻輳レベルを特定し、段階
的に輻輳の発生を判定することを特徴とする。

【００４０】また、請求項７記載の発明によれば、請求
項１から６のいずれかに記載のＲＥＤによる輻輳回避装
置において、プロトコルとしてＡＡＬ５を適用したネッ
トワークは、ＩＰオーバＡＴＭ方式を採用したネットワ
ークであることを特徴とする。

【００４１】また、請求項８記載の発明によれば、プロ
トコルとしてＡＡＬ５を適用したネットワークにおける
ＲＥＤによる輻輳回避方法であって、最終セル以外のセ
ルを所定の確率により算出されたセル間隔を基に特定
し、特定されたセルを廃棄するセル廃棄工程を有し、所
定の確率は、１つのパケットが分割される平均のセル数
と、輻輳状態のレベルに対応したパケットの廃棄率とを
基に算出され、セル間隔は、所定の確率が近似すること
ができる２の巾乗分の１の値を求め、２の巾乗の値を基
に、０から２の巾乗の２倍の値までの範囲で等確率の擬
似乱数を作成し、擬似乱数を基に特定し、セル廃棄工程
は、セル間隔により特定されたセルが最終セルでない場
合、特定されたセルを廃棄することを特徴とする。

【００４２】また、請求項９記載の発明によれば、プロ
トコルとしてＡＡＬ５を適用したネットワークにおける
ＲＥＤによる輻輳回避方法であって、回線より受信した
セルを一時保持するバッファリング工程と、バッファリ
ング工程において保持されたセルのキュー長を算出する
キュー長監視工程と、キュー長監視工程において算出さ
れたキュー長を基に、輻輳状態の発生を判定する輻輳状
態判定工程と、輻輳状態判定工程において輻輳状態の発
生が判定された場合、到着したセルが最終セルであるか
否かを判定する最終セル判定工程と、最終セル判定工程
において到着したセルが最終セルでないことが判定され
た場合、所定の確率により算出されたセル間隔を基に特
定し、特定されたセルを廃棄するセル廃棄工程とを有
し、所定の確率は、１つのパケットが分割される平均の
セル数と、輻輳状態のレベルに対応したパケットの廃棄
率とを基に算出され、セル間隔は、所定の確率が近似す
ることができる２の巾乗分の１の値を求め、２の巾乗の
値を基に、０から２の巾乗の２倍の値までの範囲で等確
率の擬似乱数を作成し、擬似乱数を基に特定し、セル廃
棄工程は、セル間隔により特定されたセルが最終セルで
ない場合、特定されたセルを廃棄することを特徴とす
る。

【００４３】また、請求項１０記載の発明によれば、請
求項９記載のＲＥＤによる輻輳回避方法において、キュ
ー長監視工程は、所定の時間間隔毎に、バッファリング
工程におけるキュー長を検知し、検知したキュー長を基
に、最新のキュー長を含む平均のキュー長を算出するこ
とで、バッファリング工程が保持するセルのキュー長を
算出することを特徴とする。

【００４４】また、請求項１１記載の発明によれば、請
求項９または１０載のＲＥＤによる輻輳回避方法におい
て、セルは、セルを構成するヘッダ部に、セルが同一パ
ケットを構成するセルの内、最終セルであるか否かを示
す最終ビットを有し、最終セル判定工程は、セルのヘッ
ダ部に含まれる最終ビットを基に、セルが最終セルであ
るか否かを判定することを特徴とする。

【００４５】また、請求項１２記載の発明によれば、請
求項９から１１のいずれかに記載のＲＥＤによる輻輳回
避方法において、閾値として所定のキュー長を記憶する
キュー長記憶工程をさらに有し、輻輳状態判定工程は、
キュー長監視工程において算出されたキュー長と、キュ
ー長記憶工程において記憶された所定のキュー長とを比
較することにより、輻輳の発生を判定することを特徴と
する。

【００４６】また、請求項１３記載の発明によれば、請
求項９から１１のいずれかに記載のＲＥＤによる輻輳回
避方法において、輻輳判定工程は、キュー長監視工程に
おいて算出されたキュー長と、複数の輻輳状態のレベル
がそれぞれ対応するように記憶された複数のキュー長と
をそれぞれ比較し、比較の結果、キュー長監視工程によ
り算出されたキュー長が超えた所定のキュー長の内、最
も大きな値である所定のキュー長に対応する輻輳レベル
を特定し、段階的に輻輳の発生を判定することを特徴と
する。

【００４７】また、請求項１４記載の発明によれば、請
求項８から１３のいずれかに記載のＲＥＤによる輻輳回
避方法において、プロトコルとしてＡＡＬ５を適用した
ネットワークは、ＩＰオーバＡＴＭ方式を採用したネッ
トワークであることを特徴とする。

【００４８】

【発明の実施の形態】以下、本発明によるＲＥＤによる
輻輳制御装置及びその方法を図面を用いて詳細に説明す
る。

【００４９】（ＲＥＤに関する概要） ここで、本発明の実施形態におけるＲＥＤは、ＩＰオー
バＡＴＭ方式を用い、その上位プロトコルとしてＴＣＰ
を前提としている。

【００５０】このＴＣＰは、エンド・エンドでフロー制
御を行うため、送信ウィンドウサイズは受信側の受信ウ
ィンドウサイズ（上限値）に達するまで徐々に大きくす
るよう制御される。従って、ＴＣＰが送信ウィンドウサ
イズを小さくして送出量を減らす場合は、パケット廃棄
を検出した時のみに限られる。

【００５１】そのため、中継交換ノードでキュー長の時
間平均値を監視し、この時間平均値がある程度大きくな
った場合、微小の確率でパケットの廃棄を行う。これ
は、上記従来の技術で述べられたＥＰＤ方式及びＰＰＤ
方式とは、根本的に目的・構成・手段が異なるものであ
る。

【００５２】また、ＴＣＰでは送信ウィンドウサイズを
パケット廃棄検出まで増加させるため、パケット廃棄が
前提となる。従って、このＴＣＰによるパケット廃棄を
ネットワークにおいて輻輳回避の目的で使用すること
は、何ら弊害を生じるものではない。

【００５３】また、ＲＥＤでは、使用帯域を平等化する
ため、廃棄するパケットはランダムに選択される。この
ため、各ＴＣＰコネクションでは、使用している帯域に
比例して廃棄されるパケット数が増加する。

【００５４】更に、ＲＥＤでは、パケットをランダムに
廃棄するため、結果として廃棄するパケットの間隔をラ
ンダムに選択することとなる。

【００５５】（ＩＰオーバＡＴＭに関する概要） また、本発明によるＲＥＤによる輻輳制御装置及びその
方法では、その通信形態をＩＰオーバＡＴＭ方式として
いる。このＩＰオーバＡＴＭ方式には、コンピュータ通
信を主な用途に想定したプロトコルとしてＡＡＬ５が有
る。これは、ＡＴＭセル損失補償や遅延ゆらぎ補償等の
高度な付加機能を極力省略し、簡易にＡＴＭ通信を実現
することを目的としたものである。

【００５６】ここで、ＡＡＬ５の特徴としては、通信に
おいて送信側・受信側（エンド・エンド）でパケットの
組み立てを行っているため、エンドノードでは、一つの
パケットを構成する複数のセルの内、最終セルと最終セ
ル以外のセルとを容易に判定することができることであ
る。

【００５７】また、ＡＴＭ通信における中継交換ノード
（中継ＡＴＭノード）では、１つのＶＣを流れるＡＴＭ
セルを継続監視することにより、あるＡＴＭセルが分解
したパケットを構成する複数のセルを、先頭セル、最終
セル、中間セル（先頭セル及び最終セルでないセル）と
して詳細に区別することができる。

【００５８】ここで、ＩＰオーバＡＴＭ方式によるパケ
ット廃棄では、ＥＰＤ方式とＰＰＤ方式とがあり、この
両者は共に、輻輳発生時に処理できないセルを廃棄する
時に、一つのパケットを構成する全ＡＴＭセルの廃棄を
行うことを目的としている。従って、パケットを構成す
るセルを選択的に廃棄する時に、全くランダムにセルを
廃棄することにより、多くのパケットが捨てられる結果
となり、上位レイヤ（ＴＣＰ）からの再送パケットが大
量に発生することに起因する輻輳の状態の悪化を回避す
るためのものである。

【００５９】従って、ＲＥＤを単純にＩＰオーバＡＴＭ
に適用してパケットをランダムに廃棄しようとした場
合、処理量が増加するといった問題が生じる。これは、
ＲＥＤは使用率が低いときから動作するものであるた
め、常時動作していると考えられるからである。従っ
て、処理量が大きい場合、オーバヘッドが増加してしま
う。これは、超高速回線を収容するＡＴＭ交換機では、
更に顕著に現れてくる問題である。

【００６０】上記のように処理量が増加する理由は、次
に挙げるような２つのレベルの異なる処理を行っている
ためである。

【００６１】先ず、１つ目の処理としては、中継ＡＴＭ
ノードを通過する全てのセルを監視して次の廃棄パケッ
トを決定する処理であり、又、２つ目の処理としては、
パケットを廃棄するＶＣ単位の処理である。この２つ目
の処理は、１つ目の処理で決定したＶＣの次のパケット
を構成する全ＡＴＭセルを廃棄する処理であり、処理量
が増加する原因としてこの処理が占める割合が大きい。

【００６２】（本発明の特徴） 従って、本発明は、パケット全体の廃棄はエンドである
ＡＡＬ５に委任することにより、中継ＡＴＭノード（Ａ
ＴＭスイッチ）の処理量を減らすことである。

【００６３】即ち、ＡＴＭスイッチは、最終でないＡＴ
Ｍセルを１つ廃棄した場合、このＡＴＭセルを含むパケ
ットの廃棄をエンドのＡＡＬ５に委任する。また、ＡＴ
Ｍセルを廃棄する確率は、（平均セル数／パケット）と
パケット廃棄率から求める。更に、この廃棄する確率に
従って、ランダムなセル間隔で、最終セル以外のセルを
廃棄することとする。

【００６４】これにより、本発明によるＲＥＤによる輻
輳回避装置及びその方法では、ＲＥＤが輻輳発生時に動
作するのではなく、平均のリソース使用率がある程度高
くなったときに低い廃棄率でパケットを廃棄するよう動
作させるため、１パケットを構成する全セルを廃棄する
従来の方法に比べて、回線上に無駄なセルが流れるとい
ったことが生じるが、これによる影響は小さく、効率よ
く輻輳の発生を防止することを可能とする。

【００６５】従って、本発明によるＲＥＤによる輻輳回
避装置及びその方法は、一つのパケットを構成する全て
のＡＴＭセルを廃棄するのではなく、ランダムなセル間
隔で一つのパケットを分解した複数のＡＴＭセルの内、
最終セルでないＡＴＭセル（以下、中間セルと略記す
る）を廃棄することを特徴としている。

【００６６】このため処理の開始の段階において、先
ず、廃棄するセルと次に廃棄するセルとの間隔（セル間
隔）を求め、次に、この求めたセル間隔を隔てた後に最
初に到着する中間セルを廃棄する。

【００６７】廃棄するセルと次に廃棄するセルとのセル
間隔は、最小値０と、１パケットを転送するのに必要な
平均セル数と輻輳レベルに応じたパケット廃棄率とから
計算によって求められる最大値とのセル間隔の中からラ
ンダムに選択することによって決定する。このセル間隔
の算出方法は、以下において詳細に説明することとす
る。

【００６８】また、中間セルを廃棄することにより、エ
ンド（パケット受信側）では、バッファに入力したＡＴ
Ｍセルからパケットを組み立てる過程において、この１
パケットを構成するセルの数が不足しているか否かを検
出し、不足している場合、そのパケットを廃棄する処理
が行われるといったＡＡＬ５による制御を活用してい
る。

【００６９】従って、中間セルを廃棄するだけで、一つ
のパケットを破棄することと同等の輻輳回避効果を得る
ことが可能となる。

【００７０】また、従来技術において問題とされた最終
セルを廃棄した場合に関しては、従来技術では、受信側
において、第１のパケットの最終セルを除いた部分と第
２のパケットを分解したセルとをあわせた全体を一つの
パケットとして組み立てられることとなり、１パケット
を構成するセル数の過多が検出され、廃棄の目的となる
第１のパケットの他に完全に受信した第２のパケットも
廃棄されるという問題を有していたが、これに対し、本
発明によるＲＥＤによる輻輳回避装置及びその方法で
は、最終セルでなく、中間セルを選択的に廃棄するた
め、このような問題を解消することが可能となる。

【００７１】さらに、本発明によるＲＥＤによる輻輳回
避装置及びその方法では、輻輳の兆候を発見した時点で
パケット廃棄（または、輻輳表示の設定）を始めるた
め、中間セル以外のＡＴＭセルを廃棄することなく、通
常の制御を行うことにより、完全に受信したパケットの
再度の送信を回避することを可能としている。そのた
め、ネットワークの輻輳をさらに悪化させることを防止
することが可能となる。

【００７２】（第１の実施形態） 以下に、本発明によるＲＥＤによる輻輳回避装置及びそ
の方法の第１の実施形態について、図面と共に詳細に説
明する。

【００７３】図１は、ＡＴＭスイッチ（中継交換ノー
ド）の構成を示すブロック図である。本図１において、
ＡＴＭスイッチは、その主要構成として回線対応部３．
１から回線対応部３．ＮまでのＮ個の回線対応部と、ス
イッチ部２とから構成されている。

【００７４】図１において、回線より受信したＡＴＭセ
ルは、スイッチ部２を経由して送出する回線に対応する
回線対応部に送られる。

【００７５】図２は、図１に示された回線対応部３の構
成を示すブロック図である。本図２において、回線対応
部３は、その主要構成として回線制御部２１と受信部２
２と送信部２３とから構成されている。

【００７６】図２において、回線から受信したＡＴＭセ
ルは回線制御部２１と受信部２２とを経由してスイッチ
部２へと送られる。また、スイッチ部２から受信したＡ
ＴＭセルは、送信部２３と回線制御部２１とを経由して
スイッチ部へと送られる。

【００７７】ここで、本発明は、上記図１及び図２に示
された回線対応部３内の送信部２３の機能に関する発明
である。

【００７８】図３を参照すると、図３は図２に示された
送信部２３の構成を示すブロック図であり、本発明の
（第１の実施形態）の説明に必要な機能及びデータを有
して構成されている。本図３では、本発明の第１の実施
形態を説明するために必要な構成のみを記している。

【００７９】図３において、スイッチ部２から受信した
ＡＴＭセルは、セル廃棄判定部４３において、廃棄する
か、若しくは送信待ちキュー３１に接続するかが判定さ
れる。ここで、送信待ちキュー３１は、セルが回線制御
部２１を経由して送出されることが可能になるまでの待
ちキューである。

【００８０】また、図３における平均キュー長監視部４
１は、送信待ちキュー３１における基準時間毎の平均キ
ュー長を監視する機能を有している。

【００８１】さらに、輻輳状態判定部４２は、平均キュ
ー長監視部４１の出力を基に、自身のＡＴＭスイッチ１
において輻輳が発生しているか否か、または輻輳状態が
解消されたか否かを判定する機能を有する。

【００８２】この時の輻輳状態の判定方法としては、平
均キュー長監視部４１により検知されたキュー長の長さ
に対して閾値を設け、この閾値を、検知した平均キュー
長が超えたか否かにより、輻輳の発生を判定する。

【００８３】更に、上記輻輳状態判定部４２が、上記の
ような閾値を複数段階有することで、段階的に輻輳状態
のレベルを判定することも可能である。

【００８４】また、図３に示されたデータ類は、セル廃
棄判定部４３が受信したセルを廃棄するか否かを判定す
るために使用するデータ類である。

【００８５】また、擬似乱数テーブル５１は、２のＫ乗
個のデータにより構成されるテーブルであり、０から
（２のＫ乗）−１までの２のＫ乗個の値がランダムに格
納されている。

【００８６】さらに、擬似乱数テーブルインデックス５
２は、擬似乱数テーブル５１を索引するためのインデッ
クスを格納したデータであり、この値を参照する毎に１
を加えるサイクリックカウンタである。

【００８７】また、シフトビット数データ５３は、輻輳
状態判定部４２がＡＴＭスイッチ１が輻輳状態であるこ
とを判定したときに設定されるデータである。また、一
つのＡＴＭセルを廃棄した後、次に廃棄するＡＴＭセル
までの廃棄しないセル数の最大数が｛（２のＬ乗）−
１｝と設定されたとき、輻輳判定部４２により（Ｌ−
Ｋ）の値が設定される。

【００８８】よって、得られた擬似乱数値をこのシフト
ビット数データ５３の値だけ右シフト（２の巾乗で除
算）することにより、次の廃棄セルまでのセル間隔を得
ることができる。

【００８９】更に詳細に、セル間隔を決定する処理につ
いて述べると、先ず、輻輳状態判定部により判定された
輻輳状態のレベルに対応したパケット廃棄率と、１パケ
ットが分割される平均のセル数とによりセル廃棄率を求
め、このセル廃棄率に対して最も近似の１／（２のｎ
乗）の値を特定する。この特定された２のｎ乗の値を基
に、０から（２の（ｎ＋１）乗）の範囲で等確率の擬似
乱数を作成する。従って、この擬似乱数テーブルを参照
することにより、次に廃棄するセルまでの間隔を特定す
る。

【００９０】上記のようにして得られた廃棄セル間隔
は、廃棄セルカウンタ５４に一時格納される。そこで、
セル廃棄判定部４３はＡＴＭセルを受信する毎に廃棄セ
ルカウンタ５４の値を参照することにより、受信したＡ
ＴＭセルを廃棄するか否かを決定する。

【００９１】また、輻輳状態データ５５は輻輳状態判定
部４２が輻輳の開始および終了を検出したとき、輻輳状
態を数的に表現するのに対応する値を設定するためのデ
ータである。この数的な表現は、送信待ちのキュー長毎
に輻輳状態のレベルを設定することにより、輻輳状態の
程度を表すものである。

【００９２】従って、このレベルに応じてセルを廃棄す
る確率を変動することにより、輻輳状態に応じた輻輳回
避が可能になる。また、同様に、輻輳状態に応じて各送
信ノードに輻輳状態の通知をすることも可能となる。

【００９３】以上、詳細に本第１の実施形態における構
成を述べたが、図３に示された平均キュー長監視部４１
および輻輳状態判定部４２は、本発明とは直接関係しな
いので、その詳細な処理は省略する。

【００９４】次に、セル廃棄判定部４３の輻輳状態にお
ける動作を図４を用いて詳細に説明する。

【００９５】図４において、セル廃棄判定部４３にＡＴ
Ｍセルが到着すると、ステップＳ６１においてセル受信
の判定が行われる。セルが受信された場合、ステップＳ
６２において廃棄セルカウンタ５４の値を判定する処理
を実行する。

【００９６】廃棄セルカンウンタ５４の値が０でない場
合は、ステップＳ６６において廃棄セルカウンタ５４の
値を１減算し、つぎにステップＳ６７において受信ＡＴ
Ｍセルを送信待ちキュー３１に登録する処理を実行し、
その後、ステップＳ６１に帰還する。

【００９７】また、廃棄セルカウンタ５４の値が０であ
る場合は、ステップＳ６３において受信セルのＡＴＭヘ
ッダの値を参照し、ＡＡＬ５で定義された最終ビットの
値が０、即ち、オフであるか否かにより、この受信した
セルが最終セルであるか否かを判定する。

【００９８】また、受信したセルのＡＴＭヘッダの値が
オフでない場合は、ステップＳ６７において受信ＡＴＭ
セルを送信待ちキューに登録する処理を実行し、その
後、ステップＳ６１に帰還する。

【００９９】さらに、受信したセルのＡＴＭヘッダの値
がオフである場合は、ステップＳ６４において受信した
ＡＴＭセルを廃棄し、ステップＳ６５において廃棄セル
カウンタ更新処理を実行して、ステップＳ６１に帰還す
る。

【０１００】次に、図４のステップＳ６５で示された廃
棄セルカウンタ更新処理を図５を用いて詳細に説明す
る。

【０１０１】先ず、ステップＳ７１において擬似乱数テ
ーブルインデックス５２の値に１を加えて格納する。

【０１０２】つぎにステップＳ７２において擬似乱数テ
ーブル５１をこの擬似乱数テーブルインデックス５２の
値で索引することにより擬似乱数の値を取得する。さら
に、この擬似乱数の値をシフトビット数データ５３の値
だけ右シフトした値を廃棄セルカウンタ５４に格納して
処理を終了する。

【０１０３】このように、本第１の実施形態において
は、中継交換ノードが受信したセルが、中間セルか否か
を判定することにより廃棄してよいセルか否かを判断し
ているため、処理量が極めて少ない。

【０１０４】更には、本第１の実施形態においては、１
つの回線上を流れる受信セル全体をまとめて廃棄セルを
決定しているため、ＥＰＤ方式によるパケット廃棄処理
のようにパケット全体を廃棄するために、全てのＶＣに
着目してそれぞれ別々にＡＴＭセルヘッダを監視する必
要がない。

【０１０５】従って、ＶＣ毎の処理と集約されたＶＣ全
体の処理とを共同して行うことも回避することが可能と
なる。

【０１０６】なお、上記第１の実施形態においては、全
てのコネクションがＩＰオーバーＡＴＭ方式であるとし
て取り扱ってたが、しかしながら、ＶＣ毎のサービスク
ラスの判定処理を追加することにより、ＩＰオーバーＡ
ＴＭ方式においてはＵＢＲを使用し、他のＡＴＭ通信に
おいてはＵＢＲ以外を使用することが可能となるため、
ＩＰオーバーＡＴＭによる通信と他の種類での通信とを
混在させて使用する形態にも適用することが可能とな
る。

【０１０７】（他の実施形態） また、上記第１の実施形態においては、ＡＴＭスイッチ
を適用した一実施形態を示したが、ホストのＡＴＭ用ネ
ットワークインタフェースカードなど、他のＡＡＬ５の
ＩＰオーバーＡＴＭトラフィックを処理する部分にも、
本発明によるＲＥＤによる輻輳回避装置及びその方法を
適用することが可能である。

【０１０８】

【発明の効果】以上説明したように、本発明によるＲＥ
Ｄによる輻輳回避装置及びその方法によれば、以下に挙
げるような本発明独自の効果を奏することが可能であ
る。

【０１０９】先ず、第１の効果としては、１つの中間セ
ルのみを選択して廃棄の対象としているため、ＥＰＤ方
式によるパケット廃棄方式に比べ、少ない処理でアプリ
ケーションにパケット廃棄を通知することが可能とな
る。

【０１１０】その理由としては、ＥＰＤ方式による廃棄
処理における１パケットを構成する全てのセルを廃棄す
るために必要な多くの処理を削減することが可能となる
ためである。

【０１１１】また、第２の効果としては、集約されたフ
ロー全体の中から１つの中間セルの廃棄のみを行ってい
るため、ＥＰＤ方式によるパケット廃棄方式を使用した
方式に比べ、少ない処理でＲＥＤを実現することも可能
となることである。

【０１１２】その理由としては、ＥＰＤ方式によるパケ
ット廃棄方式におけるＶＣ毎の１パケットを構成する全
てのセルを廃棄するための処理を削減することが可能と
なるためである。

【０１１３】更に、ＲＥＤによる輻輳回避が輻輳発生時
に動作するのではなく、平均のリソース使用率がある程
度高くなったときに低い廃棄率でパケットを廃棄するの
で、１パケットを構成する全セルを廃棄する従来の方法
に比べて回線上に無駄なセルが流れるが、このことによ
る影響は小さく、効率よく輻輳の発生を回避することが
可能となる。

【図面の簡単な説明】

【図１】ＡＴＭスイッチ（中継交換ノード）の構成を示
すブロック図である。

【図２】図１に示された回線対応部３の構成を示すブロ
ック図である。

【図３】図２に示された送信部２３の構成を示すブロッ
ク図であり、本発明の第１の実施形態の説明に必要な機
能及びデータを有して構成されている。

【図４】セル廃棄判定部４３の輻輳状態における動作示
すフローチャートである。

【図５】図４のステップＳ６５で示された廃棄セルカウ
ンタ更新処理を示すフローチャートである。

【符号の説明】

１ ＡＴＭスイッチ ２ スイッチ部 ３. １〜３. ｎ 回線対応部 ２１ 回線制御部 ２２ 受信部 ２３ 送信部 ３１ 送信待ちキュー ４１ 平均キュー長監視部 ４２ 輻輳判断部 ４３ セル廃棄判定部 ５１ 擬似乱数テーブル ５２ 擬似乱数テーブルインデックス ５３ シフトビット数データ ５４ 廃棄セルカウンタ ５５ 輻輳状態データ

Claims (14)

(57)【特許請求の範囲】
1. 【請求項１】 プロトコルとしてＡＡＬ５を適用したネ
   ットワークにおけるＲＥＤ(Random Early Detection)に
   よる輻輳回避装置であって、 最終セル以外のセルを所定の確率により算出されたセル
   間隔を基に特定し、特定されたセルを廃棄するセル廃棄
   手段を有し、前記所定の確率は、１つのパケットが分割される平均の
   セル数と、輻輳状態のレベルに対応したパケットの廃棄
   率とを基に算出され、 前記セル間隔は、前記所定の確率が近似することができ
   る２の巾乗分の１の値を求め、該２の巾乗の値を基に、
   ０から前記２の巾乗の２倍の値までの範囲で等確率の擬
   似乱数を作成し、該擬似乱数を基に特定し、 前記セル廃棄手段は、前記セル間隔により特定されたセ
   ルが最終セルでない場合、前記特定されたセルを廃棄す
   ることを特徴とするＲＥＤによる輻輳回避装置。
2. 【請求項２】 プロトコルとしてＡＡＬ５を適用したネ
   ットワークにおけるＲＥＤによる輻輳回避装置であっ
   て、 回線より受信したセルを一時保持するバッファリング手
   段と、 該バッファリング手段が保持するセルのキュー長を算出
   するキュー長監視手段と、 該キュー長監視手段により算出されたキュー長を基に、
   輻輳状態の発生を判定する輻輳状態判定手段と、 該輻輳状態判定手段により輻輳状態の発生が判定された
   場合、到着したセルが最終セルであるか否かを判定する
   最終セル判定手段と、 該最終セル判定手段により、前記到着したセルが最終セ
   ルでないことが判定された場合、所定の確率により算出
   されたセル間隔を基に特定し、特定されたセルを廃棄す
   るセル廃棄手段とを有し、前記所定の確率は、１つのパケットが分割される平均の
   セル数と、輻輳状態のレベルに対応したパケットの廃棄
   率とを基に算出され、 前記セル間隔は、前記所定の確率が近似することができ
   る２の巾乗分の１の値を求め、該２の巾乗の値を基に、
   ０から前記２の巾乗の２倍の値までの範囲で等確率の擬
   似乱数を作成し、該擬似乱数を基に特定し、 前記セル廃棄手段は、前記セル間隔により特定されたセ
   ルが最終セルでない場合、前記特定されたセルを廃棄す
   ることを特徴とするＲＥＤによる輻輳回避装置。
3. 【請求項３】 前記キュー長監視手段は、 所定の時間間隔毎に、前記バッファリング手段における
   キュー長を検知し、該検知したキュー長を基に、最新の
   キュー長を含む平均のキュー長を算出することで、前記
   バッファリング手段が保持するセルのキュー長を算出す
   ることを特徴とする請求項２記載のＲＥＤによる輻輳回
   避装置。
4. 【請求項４】 前記セルは、 該セルを構成するヘッダ部に、該セルが同一パケットを
   構成するセルの内、最終セルであるか否かを示す最終ビ
   ットを有し、 前記最終セル判定手段は、 前記セルのヘッダ部に含まれる前記最終ビットを基に、
   該セルが最終セルであるか否かを判定することを特徴と
   する請求項２または３記載のＲＥＤによる輻輳回避装
   置。
5. 【請求項５】 閾値として所定のキュー長を記憶するキ
   ュー長記憶手段をさらに有し、 前記輻輳状態判定手段は、 前記キュー長監視手段により算出された前記キュー長
   と、前記キュー長記憶手段に記憶された前記所定のキュ
   ー長とを比較することにより、輻輳の発生を判定するこ
   とを特徴とする請求項２から４のいずれかに記載のＲＥ
   Ｄによる輻輳回避装置。
6. 【請求項６】 閾値として所定のキュー長を、異なる値
   で複数記憶し、該複数の前記所定のキュー長に対応する
   輻輳状態のレベルをさらに記憶するキュー長輻輳レベル
   記憶手段をさらに有し、 前記輻輳判定手段は、 前記キュー長監視手段により算出された前記キュー長
   と、前記キュー長輻輳レベル記憶手段に記憶された複数
   の前記所定のキュー長とをそれぞれ比較し、該比較の結
   果、前記キュー長監視手段により算出された前記キュー
   長が超えた前記所定のキュー長の内、最も大きな値であ
   る前記所定のキュー長に対応する前記輻輳レベルを特定
   し、段階的に輻輳の発生を判定することを特徴とする請
   求項２から４のいずれかに記載のＲＥＤによる輻輳回避
   装置。
7. 【請求項７】 前記プロトコルとしてＡＡＬ５を適用し
   たネットワークは、ＩＰオーバＡＴＭ方式を採用したネ
   ットワークであることを特徴とする請求項１から６のい
   ずれかに記載のＲＥＤによる輻輳回避装置。
8. 【請求項８】 プロトコルとしてＡＡＬ５を適用したネ
   ットワークにおけるＲＥＤによる輻輳回避方法であっ
   て、 最終セル以外のセルを所定の確率により算出されたセル
   間隔を基に特定し、特定されたセルを廃棄するセル廃棄
   工程を有し、前記所定の確率は、１つのパケットが分割される平均の
   セル数と、輻輳状態のレベルに対応したパケットの廃棄
   率とを基に算出され、 前記セル間隔は、前記所定の確率が近似することができ
   る２の巾乗分の１の値を求め、該２の巾乗の値を基に、
   ０から前記２の巾乗の２倍の値までの範囲で等確率の擬
   似乱数を作成し、該擬似乱数を基に特定し、 前記セル廃棄工程は、前記セル間隔により特定されたセ
   ルが最終セルでない場合、前記特定されたセルを廃棄す
   ることを特徴とするＲＥＤによる輻輳回避方法。
9. 【請求項９】 プロトコルとしてＡＡＬ５を適用したネ
   ットワークにおけるＲＥＤによる輻輳回避方法であっ
   て、 回線より受信したセルを一時保持するバッファリング工
   程と、 該バッファリング工程において保持されたセルのキュー
   長を算出するキュー長監視工程と、 該キュー長監視工程において算出されたキュー長を基
   に、輻輳状態の発生を判定する輻輳状態判定工程と、 該輻輳状態判定工程において輻輳状態の発生が判定され
   た場合、到着したセルが最終セルであるか否かを判定す
   る最終セル判定工程と、 該最終セル判定工程において前記到着したセルが最終セ
   ルでないことが判定された場合、所定の確率により算出
   されたセル間隔を基に特定し、特定されたセルを廃棄す
   るセル廃棄工程とを有し、前記所定の確率は、１つのパケットが分割される平均の
   セル数と、輻輳状態のレベルに対応したパケットの廃棄
   率とを基に算出され、 前記セル間隔は、前記所定の確率が近似することができ
   る２の巾乗分の１の値を求め、該２の巾乗の値を基に、
   ０から前記２の巾乗の２倍の値までの範囲で等確率の擬
   似乱数を作成し、該擬似乱数を基に特定し、 前記セル廃棄工程は、前記セル間隔により特定されたセ
   ルが最終セルでない場合、前記特定されたセルを廃棄す
   ることを特徴とするＲＥＤによる輻輳回避方法。
10. 【請求項１０】 前記キュー長監視工程は、 所定の時間間隔毎に、前記バッファリング工程における
    キュー長を検知し、該検知したキュー長を基に、最新の
    キュー長を含む平均のキュー長を算出することで、前記
    バッファリング工程が保持するセルのキュー長を算出す
    ることを特徴とする請求項９記載のＲＥＤによる輻輳回
    避方法。
11. 【請求項１１】 前記セルは、 該セルを構成するヘッダ部に、該セルが同一パケットを
    構成するセルの内、最終セルであるか否かを示す最終ビ
    ットを有し、 前記最終セル判定工程は、 前記セルのヘッダ部に含まれる前記最終ビットを基に、
    該セルが最終セルであるか否かを判定することを特徴と
    する請求項９または１０記載のＲＥＤによる輻輳回避方
    法。
12. 【請求項１２】 閾値として所定のキュー長を記憶する
    キュー長記憶工程をさらに有し、 前記輻輳状態判定工程は、 前記キュー長監視工程において算出された前記キュー長
    と、前記キュー長記憶工程において記憶された前記所定
    のキュー長とを比較することにより、輻輳の発生を判定
    することを特徴とする請求項９から１１のいずれかに記
    載のＲＥＤによる輻輳回避方法。
13. 【請求項１３】 前記輻輳判定工程は、 前記キュー長監視工程において算出された前記キュー長
    と、複数の輻輳状態のレベルがそれぞれ対応するように
    記憶された複数のキュー長とをそれぞれ比較し、該比較
    の結果、前記キュー長監視工程により算出された前記キ
    ュー長が超えた前記所定のキュー長の内、最も大きな値
    である前記所定のキュー長に対応する前記輻輳レベルを
    特定し、段階的に輻輳の発生を判定することを特徴とす
    る請求項９から１１のいずれかに記載のＲＥＤによる輻
    輳回避方法。
14. 【請求項１４】 前記プロトコルとしてＡＡＬ５を適用
    したネットワークは、ＩＰオーバＡＴＭ方式を採用した
    ネットワークであることを特徴とする請求項８から１３
    のいずれかに記載のＲＥＤによる輻輳回避方法。