(57)【要約】【課題】  ＣＳＷ等のスイッチでマルチキャスト中継動作になるパケットの高輻輳時にパケットを落としながらも最大の性能を実現し、帯域が溢れつつも可能な限り最大の転送性能を実現すること。【解決手段】  ＣＳＷの入力側のキューに積まれていてＣＳＷマルチキャスト中継動作になる全パケットの出力方路毎のパケット長の合計値を記憶する仮想キュー長カウンタ３０１０〜３０１４を設ける。マルチキャスト中継動作になるパケットをＣＳＷ入力側のキュー３０１５に積むときに、加算すべき仮想キュー長カウンタ値が閾値を超えていたら、ＣＳＷの入力側のキューの廃棄クラスを下げるか、或いは、ＣＳＷの入力側のキューに積まずに廃棄させる。これによりＣＳＷからの出力トラフィック量が多い方路に出力するマルチキャスト程、廃棄されるようになり、ＣＳＷ全体として帯域を有効に使用できる。【選択図】  図１
2013131973.tif 000002
【特許請求の範囲】
【請求項１】
各出力方路に対応する複数のキューを有するスイッチと、
パケットの転送動作を行う転送エンジンと、
パケットの転送先の検索動作を行う検索エンジンと
を備えた中継装置におけるパケット廃棄制御方法であって、
前記転送エンジンは、
キューへのパケットの積み込み、キューにパケットを積み込む際の廃棄制御、及び、キューからのパケットの引き抜きの制御を行うキュー制御部を備え、
前記キュー制御部は、
入力されたマルチキャストパケットを格納し、該マルチキャストパケットを前記スイッチへ出力するためのマルチキャストキューと、
前記スイッチの前記複数のキュー毎に設けられた複数の仮想キュー長カウンタと
を備え、
前記検索エンジンは、各パケットの出力方路を表すビットマップを作成及び出力し、
前記転送エンジンは、前記検索エンジンから入力した前記ビットマップを前記マルチキャストパケットに付与して前記マルチキャストキューに格納し、前記ビットマップが表す出力方路に対応するひとつ又は複数の前記仮想キュー長カウンタを加算し、
前記転送エンジンは、前記マルチキャストパケットを前記マルチキャストキューに格納するときに、前記マルチキャストパケットを出力する方路に対応するいずれかの前記仮想キュー長カウンタの値が予め決められた閾値を超えていた場合、該マルチキャストパケットを前記マルチキャストキューに格納せずに廃棄し、前記仮想キュー長カウンタへの加算を抑止し、
前記転送エンジンは、前記マルチキャストパケットを前記マルチキャストキューから出力するとき、前記ビットマップも取り出し、前記ビットマップが表す出力方路に対応するひとつ又は複数の前記仮想キュー長カウンタを減算する、
パケット廃棄制御方法。
【請求項２】
請求項１に記載のパケット廃棄制御方法であって、
前記仮想キュー長カウンタに加算又は減算する値は、パケット長、又は、前記スイッチがパケットを固定長のセルに分割して中継動作を行う場合はセル数、であることを特徴とするパケット廃棄制御方法。
【請求項３】
請求項１又は２に記載のパケット廃棄制御方法であって、
前記転送エンジンは、さらに、複数の前記仮想キュー長カウンタの値の合計値をカウントするトータル仮想キュー長カウンタを備え、
前記仮想キュー長カウンタの値を比較するための前記予め定められた閾値は、少なくとも第１レベル及び第１のレベルより高いレベルの第２レベルを含み、
前記転送エンジンは、前記マルチキャストパケットを前記マルチキャストキューに格納するときに、
（ｉ）前記トータル仮想キュー長カウンタの値が予め決められたトータル閾値を超えていた場合、前記マルチキャストパケットを出力する方路のうち、いずれかの方路の前記仮想キュー長カウンタの値が前記第１のレベルを超えていたら、該マルチキャストパケットを前記マルチキャストキューに格納せずに廃棄し、
一方、
（ｉｉ）前記トータル仮想キュー長カウンタの値が前記トータル閾値を超えていなかった場合、前記マルチキャストパケットを出力する方路のうち、いずれかの方路の前記仮想キュー長カウンタの値が前記第２のレベルを超えていたら、該マルチキャストパケットを前記マルチキャストキューに格納せずに廃棄する
ことを特徴とするパケット廃棄制御方法。
【請求項４】
請求項１又は２に記載のパケット廃棄制御方法であって、
前記転送エンジンは、さらに、複数の前記仮想キュー長カウンタの値の合計値をカウントするトータル仮想キュー長カウンタを備え、
前記転送エンジンは、前記マルチキャストパケットを前記マルチキャストキューに格納するときに、前記マルチキャストパケットを出力する方路のうち、いずれかの方路の前記仮想キュー長カウンタの値が前記予め定められた閾値を超えている場合、又は、前記トータル仮想キュー長カウンタの値が予め決められたトータル閾値を超えている場合、前記マルチキャストパケットを前記マルチキャストキューに格納せずに廃棄する
ことを特徴とするパケット廃棄制御方法。
【請求項５】
請求項１乃至４のいずれかに記載のパケット廃棄制御方法であって、
前記マルチキャストパケットは、パケットの属性として廃棄クラスを含み、
各廃棄クラス順に格納するキューの長さを変化させるように前記予め定められた閾値を複数設定し、
前記マルチキャストパケットを出力する方路に対応するいずれかの前記仮想キュー長カウンタの値が予め決められた閾値を超えていた場合、前記廃棄クラスを、格納するキューの長さが短くなる方向に変更し、前記マルチキャストキューの長さが、前記変更後の廃棄クラスに対応する閾値を超えていた場合、前記マルチキャストキューに前記マルチキャストパケットを格納せずに廃棄し、
前記マルチキャストパケットを出力する方路に対応するいずれかの前記仮想キュー長カウンタの値が予め決められた閾値を超えていなかった場合、前記廃棄クラスを変更せず、前記マルチキャストキューの長さが、前記廃棄クラスに対応する閾値を超えていた場合、前記マルチキャストキューに前記マルチキャストパケットを格納せずに廃棄する
ことを特徴とするパケット廃棄制御方法。
【請求項６】
請求項１乃至５のいずれかに記載のパケット廃棄制御方法であって、
前記マルチキャストパケットは、パケットの属性として出力クラスを含み、
前記転送エンジン内の前記キュー制御部が、出力クラス毎に複数設けられ、
前記マルチキャストパケットを、出力クラスにより複数の前記キュー制御部のいずれかに振り分ける振り分け部と、
複数の前記キュー制御部のいずれかから前記マルチキャストパケットを選択及び出力するスケジューラと、
をさらに備え、
各前記キュー制御部が、前記マルチキャストパケットの廃棄制御を各出力クラス毎に独立して行うことを特徴とするパケット廃棄制御方法。
【請求項７】
請求項１乃至６のいずれかに記載のパケット廃棄制御方法であって、
前記転送エンジンは、さらに、
前記スイッチの複数の出力方路に対応して設けられた、ユニキャストパケット用の複数の仮想出力キューと、
ユニキャストパケットを複数の前記仮想出力キューのいずれかに振り分け、マルチキャストパケットを前記マルチキャストキューへ振り分ける振り分け部と、
複数の前記仮想出力キュー及び前記マルチキャストキューのいずれかからパケットを引き抜き、前記スイッチに出力するスケジューラと、
を備え、
前記振り分け部は、ユニキャストパケットが入力された場合、前記ユニキャストパケットを前記仮想出力キューに振り分け、
（ｉ）前記転送エンジンは、前記仮想出力キューの長さと予め定められたユニキャスト用廃棄閾値とを比較することにより、前記仮想出力キューに対する前記ユニキャストパケットの廃棄制御を行うこと、又は、
（ｉｉ）前記転送エンジンは、前記仮想出力キューの長さ、及び、該ユニキャストパケットの出力方路に対応するマルチキャストパケット用の前記仮想キュー長カウンタの値の加算値と、予め定められた合計廃棄閾値とを比較することにより、廃棄制御を行うこと
を特徴とするパケット廃棄制御方法。
【請求項８】
請求項１乃至７のいずれかに記載のパケット廃棄制御方法であって、
前記転送エンジンは、さらに、
前記スイッチの複数の出力方路に対応して設けられた、ユニキャストパケット用の複数の仮想出力キューと、
ユニキャストパケットを複数の前記仮想出力キューのいずれかに振り分け、マルチキャストパケットを前記マルチキャストキューへ振り分ける振り分け部と、
複数の前記仮想出力キュー及び前記マルチキャストキューのいずれかからパケットを引き抜き、前記スイッチに出力するスケジューラと、
を備え、
前記振り分け部は、マルチキャストパケットが入力された場合、前記マルチキャストパケットを前記マルチキャストキューに振り分け、
（ｉ）前記転送エンジンは、前記マルチキャストパケットを出力する全方路に対応する前記仮想キュー長カウンタの値と予め定められたマルチキャスト用廃棄閾値とを比較することにより、廃棄制御を行うこと、又は、
（ｉｉ）前記転送エンジンは、前記マルチキャストパケットを出力する全方路に対応するユニキャストパケット用の前記仮想出力キューの長さ、及び、該マルチキャストパケットを出力する全方路に対応するマルチキャストパケット用の前記仮想キュー長カウンタの値の、各出力方路毎の加算値と、予め定められた合計廃棄閾値とを各出力方路毎に比較することにより、廃棄制御を行うこと
を特徴とするパケット廃棄制御方法。
【請求項９】
各出力方路に対応する複数のキューを有するスイッチと、
パケットの転送動作を行う転送エンジンと、
パケットの転送先の検索動作を行う検索エンジンと
を備えた中継装置であって、
前記転送エンジンは、
入力されたマルチキャストパケットを格納し、該マルチキャストパケットを前記スイッチへ出力するためのマルチキャストキューと、
前記スイッチの前記複数のキュー毎に設けられた複数の仮想キュー長カウンタと
を備え、
前記検索エンジンは、各パケットの出力方路を表すビットマップを作成及び出力し、
前記転送エンジンは、前記検索エンジンから入力した前記ビットマップを前記マルチキャストパケットに付与して前記マルチキャストキューに格納し、前記ビットマップが表す出力方路に対応するひとつ又は複数の前記仮想キュー長カウンタを加算し、
前記転送エンジンは、前記マルチキャストパケットを前記マルチキャストキューに格納するときに、前記マルチキャストパケットを出力する方路に対応するいずれかの前記仮想キュー長カウンタの値が予め決められた閾値を超えていた場合、該マルチキャストパケットを前記マルチキャストキューに格納せずに廃棄し、前記仮想キュー長カウンタへの加算を抑止し、
前記転送エンジンは、前記マルチキャストパケットを前記マルチキャストキューから出力するとき、前記ビットマップも取り出し、前記ビットマップが表す出力方路に対応するひとつ又は複数の前記仮想キュー長カウンタを減算する、
パケット廃棄制御のための中継装置。
【請求項１０】
各出力方路に対応する複数のキューを有するスイッチを備えた中継装置におけるパケット廃棄制御のためのパケット処理装置であって、
パケットの転送動作を行う転送エンジンと、
パケットの転送先の検索動作を行う検索エンジンと
を備え、
前記転送エンジンは、
入力されたマルチキャストパケットを格納し、該マルチキャストパケットを前記スイッチへ出力するためのマルチキャストキューと、
前記スイッチの前記複数のキュー毎に設けられた複数の仮想キュー長カウンタと
を備え、
前記検索エンジンは、各パケットの出力方路を表すビットマップを作成及び出力し、
前記転送エンジンは、前記検索エンジンから入力した前記ビットマップを前記マルチキャストパケットに付与して前記マルチキャストキューに格納し、前記ビットマップが表す出力方路に対応するひとつ又は複数の前記仮想キュー長カウンタを加算し、
前記転送エンジンは、前記マルチキャストパケットを前記マルチキャストキューに格納するときに、前記マルチキャストパケットを出力する方路に対応するいずれかの前記仮想キュー長カウンタの値が予め決められた閾値を超えていた場合、該マルチキャストパケットを前記マルチキャストキューに格納せずに廃棄し、前記仮想キュー長カウンタへの加算を抑止し、
前記転送エンジンは、前記マルチキャストパケットを前記マルチキャストキューから出力するとき、前記ビットマップも取り出し、前記ビットマップが表す出力方路に対応するひとつ又は複数の前記仮想キュー長カウンタを減算する、
パケット処理装置。
【請求項１１】
請求項９に記載の中継装置、又は、請求項１０に記載のパケット処理装置であって、
前記転送エンジンは、
前記マルチキャストキューと前記複数の仮想キュー長カウンタを有し、キューへのパケットの積み込み、キューにパケットを積み込む際の廃棄制御、及び、キューからのパケットの引き抜きの制御を行うキュー制御部を備えたことを特徴とする、出力装置又はパケット処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット廃棄制御方法、中継装置、パケット処理装置に係り、特に、ネットワーク内の中継装置内のクロスバースイッチ等のスイッチでマルチキャスト中継を行うパケットの廃棄制御に関するものである。
【背景技術】
【０００２】
従来、ユニキャスト中継動作では、クロスバースイッチの入力側に、出力方路毎のキュー（ＶＯＱ：Ｖｉｒｔｕａｌ  Ｏｕｔｐｕｔ  Ｑｕｅｕｅ）を持つことにより、輻輳していない出力方路行きのパケットが、輻輳している出力方路行きのパケットにより待たされないようにできた。これに対しマルチキャスト中継動作では、一つのパケットを同時に複数の方路に出力する為、出力方路毎にキューを分けるＶＯＱの手法が使えず、従来、出力方路に関係なく、一つの共通のキューに積んでいた。この為、輻輳していない出力方路行きのパケットが、輻輳している出力方路行きのパケットにより待たされるという場合（ＨＯＬ）があった。
【０００３】
従来技術として、特許文献１には、「マルチキャストパケットに許容される入力レートを低下させることなく、処理の負担を軽減することができるパケットスイッチ」（要約）が記載されている。特許文献２には、「マルチキャスト通信中継方式に関し、ブロッキングの発生による中継性能の劣化の影響を軽減する」（要約）マルチキャスト通信中継方式が記載されている。また、特許文献３には、「ネットワークの各ステージで個々の交換装置に追加のインテリジェント特徴を提供することによって、マルチステージスイッチングネットワークの性能及び接続能力を高めるための方法及び装置」（段落００１６）が記載されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００２−２０８９３８号公報
【特許文献２】特開２００２−１５２１９９号公報
【特許文献３】特開平０６−１９７１２５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来は、ネットワーク内の中継装置内のスイッチ（以下、クロスバースイッチ（ＣＳＷ：Ｃｒｏｓｓｂａｒ  Ｓｗｉｔｃｈ）を例に説明する。）でのマルチキャスト中継動作において、輻輳していない出力方路行きのパケットが待たされるという課題（ＨＯＬ：Ｈｅａｄ  ｏｆ  Ｌｉｎｅ）があった。
この改善策として、本発明は、例えば、ＣＳＷの入力方路毎のキューに積まれているパケットの出力方路毎のカウント値から輻輳している方路を推定し、輻輳している出力方路に出力されるマルチキャストを選択的に廃棄するものである。
【０００６】
図５は、クロスバースイッチでのマルチキャストの輻輳を示す説明図である。以下、従来の課題である、ＣＳＷのＨＯＬブロッキング回避のために、ユニキャスト中継動作ではＶＯＱが使えたが、マルチキャスト中継動作ではＶＯＱの手法が使えず、ＨＯＬブロッキングが発生する場合について、図５を使用し説明する。
ＣＳＷ（２）内で、受信側のパケット処理機構ＰＰＵ０（３０Ｒ）から送信側のパケット処理機構ＰＰＵ１（３１Ｔ）行きの出力方路（２１１）行きのキュー（２１０）が輻輳しているとき、ＣＳＷ（２）は、パケットＡ，Ｂを出力できない。そして、転送エンジン（３０１）のキュー（３０１５）において、パケットＡ，Ｂの後ろにパケットＣが積まれていた場合、ＣＳＷ（２）は、パケットＣの全出力方路（２３１、２４１）行きのキュー（２３０、２４０）は輻輳していないにも関わらず、パケットＣを転送することができない。
ＣＳＷ（２）でマルチキャストの中継動作が大量に発生する場合として、例えば、動画配信のように複数の端末に同時にパケットを届けるためにアプリケーションレベルでマルチキャスト動作になる場合と、アプリケーションレベルでは一つの端末にのみパケットを届ける必要があるユニキャストだが網変化時のみ出力先が判らなくなる結果としてマルチキャスト動作になる所謂レイヤ２フラッディング動作がある。アプリケーションレベルでマルチキャスト動作になる場合は、一般的に再送が難しく、積極的に廃棄させる制御方式は必ずしも有効ではない場合も想定されるが、レイヤ２フラッディングの場合には、廃棄させながらも最大限中継させた方がネットワーク全体としての中継性能向上に効果がある。
【０００７】
本発明は、以上の点に鑑み、ＣＳＷ等のスイッチでマルチキャスト中継動作になるパケットの高輻輳時にパケットを落としながらも最大の性能を実現し、レイヤ２フラッディング時など、帯域が溢れつつも可能な限り最大の転送性能を実現することを、ひとつの目的とする。
また、本発明は、出力トラフィックが多いマルチキャストを、より廃棄され易くし、公平性を保つことを、他の目的とする。
更に本発明は、廃棄制御機能を設けたパケット転送機構と設けていないパケット転送機構を装置内で混在可能とし、装置を稼動させたまま装置内のパケット転送機構を、本発明による廃棄制御機能を設けたパケット転送機構に順次置き換えていくことを可能とすることを、他の目的とする。
【課題を解決するための手段】
【０００８】
本発明のひとつの態様によると、ＣＳＷ行きのキューに積まれていてＣＳＷでマルチキャスト中継動作になる全パケットの出力方路毎のパケット長の合計値を記憶する仮想キュー長カウンタを設ける。或いは、ＣＳＷでパケットを固定長のセルに分割して中継する方式を採用している場合には、パケット長の代わりにセル数を用い、セル数の合計値を記憶しても良い。
仮想キュー長カウンタには、マルチキャスト中継動作になるパケットをＣＳＷ行きのキューに積むときに、マルチキャストの各出力方路に対応する各仮想キュー長カウンタにパケット長、或いはセル数を加算する。
【０００９】
マルチキャスト中継動作になるパケットをＣＳＷ行きのキューから引き抜くときには、マルチキャストの各出力方路に対応する各仮想キュー長カウンタからパケット長、或いはセル数を減算する。
マルチキャスト中継動作になるパケットをＣＳＷ行きのキューに積むときに、加算すべき仮想キュー長カウンタ値が閾値を超えていたら、ＣＳＷ行きのキューの廃棄クラスを下げるか、或いは、ＣＳＷ行きのキューに積まずに廃棄させる。
これによりＣＳＷからの出力トラフィック量が多い方路に出力するマルチキャスト程、廃棄されるようになり、輻輳していない方路行きのマルチキャストが、より多く転送されるようになり、出力方路によりトラフィック量が異なる場合にも、ＣＳＷ全体として帯域を有効に使用できる。
【００１０】
更に、本発明の他の態様によると、出力方路毎の仮想キュー長カウンタの値に加え、全仮想キュー長カウンタの値の合計であるトータル仮想キュー長カウンタの値を用いて廃棄閾値判定を行い、出力方路毎の仮想キュー長カウンタの値の判定に用いる閾値を２以上のレベルとし、トータル仮想キュー長カウンタの値が予め決められた閾値を超えていたら、出力方路毎のカウンタ値の閾値として低い方の閾値を用い、トータル仮想キュー長カウンタの値が予め決められた閾値を超えていなかったら、出力方路毎の仮想キュー長カウンタの値の閾値として高い方の閾値を用いるようにする。或いは、出力方路毎の仮想キュー長カウンタの値の判定は、トータル仮想キュー長カウンタを用いない場合と同様に行い、更にトータル仮想キュー長カウンタの値が予め決められた閾値を超えていた場合には、マルチキャストの出力方路に関わり無く当該パケットを廃棄するようにする。
これにより、ＣＳＷの帯域を多く使用するＰＰＵ程、パケットが廃棄され易くなり、複数のＰＰＵの間での公平性を確保することが可能となる。
【００１１】
本発明の第１の解決手段によると、
各出力方路に対応する複数のキューを有するスイッチと、
パケットの転送動作を行う転送エンジンと、
パケットの転送先の検索動作を行う検索エンジンと
を備えた中継装置におけるパケット廃棄制御方法であって、
前記転送エンジンは、
前記マルチキャストキューと前記複数の仮想キュー長カウンタを有し、キューへのパケットの積み込み、キューにパケットを積み込む際の廃棄制御、及び、キューからのパケットの引き抜きの制御を行うキュー制御部を備え、
前記キュー制御部は、
入力されたマルチキャストパケットを格納し、該マルチキャストパケットを前記スイッチへ出力するためのマルチキャストキューと、
前記スイッチの前記複数のキュー毎に設けられた複数の仮想キュー長カウンタと
を備え、
前記検索エンジンは、各パケットの出力方路を表すビットマップを作成及び出力し、
前記転送エンジンは、前記検索エンジンから入力した前記ビットマップを前記マルチキャストパケットに付与して前記マルチキャストキューに格納し、前記ビットマップが表す出力方路に対応するひとつ又は複数の前記仮想キュー長カウンタを加算し、
前記転送エンジンは、前記マルチキャストパケットを前記マルチキャストキューに格納するときに、前記マルチキャストパケットを出力する方路に対応するいずれかの前記仮想キュー長カウンタの値が予め決められた閾値を超えていた場合、該マルチキャストパケットを前記マルチキャストキューに格納せずに廃棄し、前記仮想キュー長カウンタへの加算を抑止し、
前記転送エンジンは、前記マルチキャストパケットを前記マルチキャストキューから出力するとき、前記ビットマップも取り出し、前記ビットマップが表す出力方路に対応するひとつ又は複数の前記仮想キュー長カウンタを減算する、
パケット廃棄制御方法が提供される。
【００１２】
本発明の第２の解決手段によると、
各出力方路に対応する複数のキューを有するスイッチと、
パケットの転送動作を行う転送エンジンと、
パケットの転送先の検索動作を行う検索エンジンと
を備えた中継装置であって、
前記転送エンジンは、
入力されたマルチキャストパケットを格納し、該マルチキャストパケットを前記スイッチへ出力するためのマルチキャストキューと、
前記スイッチの前記複数のキュー毎に設けられた複数の仮想キュー長カウンタと
を備え、
前記検索エンジンは、各パケットの出力方路を表すビットマップを作成及び出力し、
前記転送エンジンは、前記検索エンジンから入力した前記ビットマップを前記マルチキャストパケットに付与して前記マルチキャストキューに格納し、前記ビットマップが表す出力方路に対応するひとつ又は複数の前記仮想キュー長カウンタを加算し、
前記転送エンジンは、前記マルチキャストパケットを前記マルチキャストキューに格納するときに、前記マルチキャストパケットを出力する方路に対応するいずれかの前記仮想キュー長カウンタの値が予め決められた閾値を超えていた場合、該マルチキャストパケットを前記マルチキャストキューに格納せずに廃棄し、前記仮想キュー長カウンタへの加算を抑止し、
前記転送エンジンは、前記マルチキャストパケットを前記マルチキャストキューから出力するとき、前記ビットマップも取り出し、前記ビットマップが表す出力方路に対応するひとつ又は複数の前記仮想キュー長カウンタを減算する、
パケット廃棄制御のための中継装置が提供される。
【００１３】
本発明の第３の解決手段によると、
各出力方路に対応する複数のキューを有するスイッチを備えた中継装置におけるパケット廃棄制御のためのパケット処理装置であって、
パケットの転送動作を行う転送エンジンと、
パケットの転送先の検索動作を行う検索エンジンと
を備え、
前記転送エンジンは、
入力されたマルチキャストパケットを格納し、該マルチキャストパケットを前記スイッチへ出力するためのマルチキャストキューと、
前記スイッチの前記複数のキュー毎に設けられた複数の仮想キュー長カウンタと
を備え、
前記検索エンジンは、各パケットの出力方路を表すビットマップを作成及び出力し、
前記転送エンジンは、前記検索エンジンから入力した前記ビットマップを前記マルチキャストパケットに付与して前記マルチキャストキューに格納し、前記ビットマップが表す出力方路に対応するひとつ又は複数の前記仮想キュー長カウンタを加算し、
前記転送エンジンは、前記マルチキャストパケットを前記マルチキャストキューに格納するときに、前記マルチキャストパケットを出力する方路に対応するいずれかの前記仮想キュー長カウンタの値が予め決められた閾値を超えていた場合、該マルチキャストパケットを前記マルチキャストキューに格納せずに廃棄し、前記仮想キュー長カウンタへの加算を抑止し、
前記転送エンジンは、前記マルチキャストパケットを前記マルチキャストキューから出力するとき、前記ビットマップも取り出し、前記ビットマップが表す出力方路に対応するひとつ又は複数の前記仮想キュー長カウンタを減算する、
パケット処理装置が提供される。
【発明の効果】
【００１４】
本発明は、ＣＳＷ等のスイッチでマルチキャスト中継動作になるパケットの高輻輳時にパケットを落としながらも最大の性能を実現でき、レイヤ２フラッディング時など、帯域が溢れつつも可能な限り最大の転送性能を実現したい場合に有効である。
また、本発明では出力トラフィックが多いマルチキャストが、より廃棄され易くなり、公平性が保たれる。
更に本発明は、ＣＳＷ等のスイッチの入力側のパケット中継機構だけで実現可能であり、ＣＳＷには特別な機構は不要であることから、本発明による廃棄制御機能を設けたパケット転送機構と設けていないパケット転送機構を装置内で混在可能であり、装置を稼動させたまま装置内のパケット転送機構を、本発明による廃棄制御機能を設けたパケット転送機構に順次置き換えていくことが可能である。
【図面の簡単な説明】
【００１５】
【図１】クロスバースイッチでの輻輳を回避するための機構を示す図である。
【図２】図１の閾値判定部の判定結果に対する動作の代替案を示す図である。
【図３】図２で廃棄クラスを下げる場合と下げない場合の動作を示す図である。
【図４】ネットワーク内の中継装置の構成図である。
【図５】クロスバースイッチでのマルチキャストの輻輳を示す説明図である。
【図６】クロスバースイッチでの輻輳を回避するための機構にトータル仮想キュー長カウンタを組み合わせた場合の実現方法を示す図である。
【図７】クロスバースイッチでの輻輳を回避するための機構に出力優先度を組み合わせた場合の実現方法を示す図である。
【図８】ユニキャスト中継動作になるパケットとマルチキャスト中継動作になるパケットの間の廃棄制御方法を示す図である。
【発明を実施するための形態】
【００１６】
Ａ．中継装置
図４に、本実施の形態のネットワーク内の中継装置の構成図を示す。中継装置（１）は、ＣＳＷ（２）と、ネットワークとのパケットの送受信を行うネットワークインタフェース機構ＮＩＦ０（４０Ｒ、４０Ｔ）、ＮＩＦ１（４１Ｒ、４１Ｔ）、ＮＩＦ２（４２Ｒ、４２Ｔ）、ＮＩＦ３（４３Ｒ、４３Ｔ）、ＮＩＦ４（４４Ｒ、４４Ｔ）、ＣＳＷ（２）とＮＩＦ０、ＮＩＦ１、ＮＩＦ２、ＮＩＦ３、ＮＩＦ４の間でパケットの転送を行うパケット転送機構ＰＰＵ０（３０Ｒ、３０Ｔ）、ＰＰＵ１（３１Ｒ、３１Ｔ）、ＰＰＵ２（３２Ｒ、３２Ｔ）、ＰＰＵ３（３３Ｒ、３３Ｔ）、ＰＰＵ４（３４Ｒ、３４Ｔ）を備える。なお、実施の形態では、クロスバースイッチ（ＣＳＷ：Ｃｒｏｓｓｂａｒ  Ｓｗｉｔｃｈ）を例に説明するが、適宜のスイッチを用いることができる。
【００１７】
各ＰＰＵは、構成要素としてパケットの転送動作を行う転送エンジン（３０１）とパケットの検索動作を行う検索エンジン（３０２）を含む。
ＮＩＦ０、ＮＩＦ１、ＮＩＦ２、ＮＩＦ３、ＮＩＦ４、及びＰＰＵ０、ＰＰＵ１、ＰＰＵ２、ＰＰＵ３、ＰＰＵ４は、図４では受信側と送信側に分けて示しており、それぞれ番号にＲとＴを付けて記述しているが、実際には受信側と送信側を合わせて一つの部位とすることができる。
【００１８】
Ｂ．パケット転送機構及びクロスバースイッチ
１．第１の実施の形態
図１は、クロスバースイッチでの輻輳を回避するための機構を示す図である。以下に、図１を用いて、装置内クロスバースイッチＣＳＷ（２）のマルチキャストのＨＯＬの回避策を説明する。本実施の形態では、パケット転送機構ＰＰＵ０（３０Ｒ）内の転送エンジン（３０１）内に、キューへのパケットの積み込み、キューにパケットを積む際の廃棄制御、及びキューからのパケットの引き抜きなどのキューの制御を行うキュー制御部（３０２０）を設け、キュー制御部（３０２０）内に、ＣＳＷ（２）行きのマルチキャストキュー（３０１５）に入っている、ＣＳＷ（２）でマルチキャスト転送動作になるパケットの、キュー（２００、２１０、２２０、２３０、２４０）毎の仮想キュー長カウンタ（３０１０、３０１１、３０１２、３０１３、３０１４）を設ける。キュー（２００、２１０、２２０、２３０、２４０）は、ＰＰＵ０（３０Ｔ）、ＰＰＵ１（３１Ｔ）、ＰＰＵ２（３２Ｔ）、ＰＰＵ３（３３Ｔ）、ＰＰＵ４（３４Ｔ）行きの出力方路（２０１、２１１、２２１、２３１、２４１）に対応する。
【００１９】
ＣＳＷ（２）でマルチキャスト転送動作になるパケットを、ネットワークから受信後、ＣＳＷ（２）行きのマルチキャストキュー（３０１５）に入力する（積む）ときに、マルチキャストの各出力方路（２０１、２１１、２２１、２３１、２４１）に対応する各仮想キュー長カウンタ（３０１０、３０１１、３０１２、３０１３、３０１４）にパケット長を加算する。具体的には各パケットをどの方路（２０１、２１１、２２１、２３１、２４１）に出力するかは、各パケットをＣＳＷ（２）行きのマルチキャストキュー（３０１５）に積む前に検索エンジン（３０２）により検索され、どの方路（２０１、２１１、２２１、２３１、２４１）に出力するかのビットマップ（ＣＳＷ  ｂｉｔｍａｐ）としてパケットに付与され、ＣＳＷ（２）行きのマルチキャストキュー（３０１５）に積むときに、ＣＳＷ  ｂｉｔｍａｐ（３０１７）中の１が立っている方路（２０１、２１１、２２１、２３１、２４１）に対応する仮想キュー長カウンタ（３０１０、３０１１、３０１２、３０１３、３０１４）を加算するようにする。
ここで、ＣＳＷ  ｂｉｔｍａｐ（３０１７）中の全ｂｉｔが０だった場合には、当該パケットはＣＳＷ（２）から、どの方路へも出力しないので、マルチキャストキュー（３０１５）に積まずに廃棄するようにしても良い。
【００２０】
ＣＳＷ（２）でマルチキャスト転送動作になるパケットを、ＣＳＷ（２）に送る為にＣＳＷ（２）行きのマルチキャストキュー（３０１５）から出力する（引き抜く）ときには、マルチキャストの各出力方路（２０１、２１１、２２１、２３１、２４１）に対応する各仮想キュー長カウンタ（３０１０、３０１１、３０１２、３０１３、３０１４）からパケット長を減算する。具体的にはパケットをマルチキャストキュー（３０１５）に積むときにパケットそのものと共にＣＳＷ  ｂｉｔｍａｐも格納し、ＣＳＷ（２）行きのマルチキャストキュー（３０１５）から引き抜くときに、ＣＳＷ  ｂｉｔｍａｐも同時に引き抜き、ＣＳＷ  Ｂｉｔｍａｐ（３０１８）中の１が立っている方路（２０１、２１１、２２１、２３１、２４１）に対応する仮想キュー長カウンタ（３０１０、３０１１、３０１２、３０１３、３０１４）を減算するようにする。
【００２１】
図１にはＰＰＵ１（３１Ｔ）とＰＰＵ２（３２Ｔ）に出力するパケットＢをキュー（３０１５）に積むときに、出力方路（２１１、２２１）に対応する仮想キュー長カウンタ（３０１１、３０１２）を加算し、キュー（３０１５）から引き抜くときに、出力方路（２１１、２２１）に対応する仮想キュー長カウンタ（３０１１、３０１２）を減算する場合の例を示している。このとき、ｂｉｔｍａｐは、仮想キュー長カウンタ（３０１１及び３０１２）に対応するビットに１が立っている。
転送エンジン（３０１）は、パケットＢをマルチキャストキュー（３０１５）に入力するときに、このｂｉｔｍａｐも含めて格納し（積み）、仮想キュー長カウンタ（３０１１及び３０１２）を加算する。一方、パケットＢをマルチキャストキュー（３０１５）から出力する（引き抜く）とき、転送エンジン（３０１）は、このｂｉｔｍａｐに基づき仮想キュー長カウンタ（３０１１及び３０１２）を減算する。
【００２２】
転送エンジン（３０１）内のキュー制御部（３０２０）は、閾値判定部（３０１６）により、ネットワークから受信したパケットをＣＳＷ（２）行きのマルチキャストキュー（３０１５）に積むときに加算しようとした仮想キュー長カウンタ（３０１０、３０１１、３０１２、３０１３、３０１４）の値が予め決められた閾値を超えているかを閾値判定部（３０１６）で判定し、超えていたら、ＣＳＷ（２）行きのマルチキャストキュー（３０１５）に積まずに廃棄させると共に、ＣＳＷ（２）行きのマルチキャストキュー（３０１５）に積まずに廃棄させたパケットに対するバイト数は加算抑止機構（３０１１０）を用いて仮想キュー長カウンタ（３０１０、３０１１、３０１２、３０１３、３０１４）への加算を抑止するようにする。
【００２３】
これによりＣＳＷ（２）の出力トラフィック量が多い方路（２０１、２１１、２２１、２３１、２４１）に出力するマルチキャスト程、廃棄され易くなり、輻輳していない方路（２０１、２１１、２２１、２３１、２４１）行きのマルチキャストが、より多く転送されるようになり、出力方路（２０１、２１１、２２１、２３１、２４１）によりトラフィック量が異なる場合にも、ＣＳＷ（２）全体として帯域を有効に使用できるようになる。
他の実施の形態として、パケットを固定長のセルに分割しＣＳＷ（２）の転送を行う方式を採用している場合には、仮想キュー長カウンタ（３０１０、３０１１、３０１２、３０１３、３０１４）に加減算する値として、パケット長の代わりにセル数を用いることもできる。
【００２４】
２．第２の実施の形態
図６は、クロスバースイッチでの輻輳を回避するための機構にトータル仮想キュー長カウンタを組み合わせた場合の実現方法を示す図である。更に第２の実施の形態として、出力方路毎の仮想キュー長カウンタ（３０１０、３０１１、３０１２、３０１３、３０１４）の値に加え、全仮想キュー長カウンタ（３０１０、３０１１、３０１２、３０１３、３０１４）の値の合計であるトータル仮想キュー長カウンタ（３０１９）の値を用いて廃棄閾値判定を行う方式も考えられる。トータル仮想キュー長カウンタ（３０１９）の値は、ＰＰＵ（３０Ｒ、３１Ｒ、３２Ｒ、３３Ｒ、３４Ｒ）のうちの一つに滞留していて今後ＣＳＷ（２）の全出力方路（２０１、２１１、２２１、２３１、２４１）に流れるトータルデータ量であり、トータル仮想キュー長カウンタ（３０１９）の値を用いて廃棄閾値判定を行うことにより、今後ＣＳＷ（２）の帯域を多く使用するＰＰＵ程、パケットが廃棄され易くなり、複数のＰＰＵ（３０Ｒ、３１Ｒ、３２Ｒ、３３Ｒ、３４Ｒ）の間での公平性を確保することが可能となる。
トータル仮想キュー長カウンタ（３０１９）の値を、全仮想キュー長カウンタ（３０１０、３０１１、３０１２、３０１３、３０１４）の合計値になるようにする為に、各仮想キュー長カウンタにパケット長を加算するタイミングで、パケット長にＣＳＷ  ｂｉｔｍａｐの１の数を掛けた値をトータル仮想キュー長カウンタ（３０１９）に加算するようにする。
加算抑止機構（３０１１０）により、各仮想キュー長カウンタへの加算を抑止する場合には、同時に、トータル仮想キュー長カウンタ（３０１９）への加算も抑止する。
また、各仮想キュー長カウンタからパケット長を減算するタイミングで、パケット長にＣＳＷ  ｂｉｔｍａｐの１の数を掛けた値をトータル仮想キュー長カウンタ（３０１９）から減算するようにする。
他の機構は第１の実施の形態と同様である。
【００２５】
この拡張方式の実現方法の一番目の例を図６を用いて説明する。出力方路（２０１、２１１、２２１、２３１、２４１）毎の仮想キュー長カウンタ（３０１０、３０１１、３０１２、３０１３、３０１４）の値の判定に用いる閾値を２レベルとし、トータル仮想キュー長カウンタ（３０１９）の値が予め決められた閾値を超えていたら、出力方路（２０１、２１１、２２１、２３１、２４１）毎のカウンタ値の閾値として低い方の閾値を用い、トータル仮想キュー長カウンタ（３０１９）の値が予め決められた閾値を超えていなかったら、出力方路（２０１、２１１、２２１、２３１、２４１）毎の仮想キュー長カウンタ（３０１０、３０１１、３０１２、３０１３、３０１４）の値の閾値として高い方の閾値を用いるようにする。
【００２６】
この拡張方式の実現方法の二番目の例として、出力方路（２０１、２１１、２２１、２３１、２４１）毎の仮想キュー長カウンタ（３０１０、３０１１、３０１２、３０１３、３０１４）の値の判定は、トータル仮想キュー長カウンタ（３０１９）を用いない場合と同様に行い、更にトータル仮想キュー長カウンタ（３０１９）の値が予め決められた閾値を超えていた場合には、マルチキャストの出力方路に関わり無く当該パケットを廃棄するようにする。
【００２７】
３．第３の実施の形態
図２は、図１の閾値判定部の判定結果に対する動作の代替案を示す図である。また、図３は、図２で廃棄クラスを下げる場合と下げない場合の動作を示す図である。
更に、第１又は第２の実施の形態と廃棄クラスを組み合わせることもできる。第１又は第２の実施の形態と廃棄クラスを組み合わせ方について図２及び図３を用いて説明する。廃棄クラスとはパケットの属性であり、廃棄クラスが低いパケットをキュー（３０１５）に積むときには、最大のキュー長まで積まずに、キュー長が予め決められた値を超えていたら積まずに廃棄させるようにするものである。廃棄クラスはＣＳＷ（２）行きのマルチキャストキュー（３０１５）に積む前に、例えば前述した検索エンジン（３０２）で検索することにより得ることができる。廃棄クラスは通常は複数設け、最高の廃棄クラスのパケットは最大のキュー長まで積み、廃棄クラスが下がるにつれ、予め決められた、より低い閾値で廃棄させるようにするものである。例えば廃棄クラスを４クラス設けた場合、最高クラス（廃棄クラス３）は最大のキュー長まで積み、廃棄クラス２は８５％まで、廃棄クラス１は６０％まで、廃棄クラス０は３５％までキュー長が伸びていたら積まずに廃棄させるようにするものである。第１又は第２の実施の形態と廃棄クラスを組み合わせる場合、閾値判定部（３０１６）は、ネットワークから受信したパケットをＣＳＷ（２）行きのマルチキャストキュー（３０１５）に積むときに加算しようとした仮想キュー長カウンタ（３０１０、３０１１、３０１２、３０１３、３０１４）の値が閾値を超えていたら、廃棄クラスを下げるという処理を行う（図２の３０１６）。最低の廃棄クラスのパケットに対しては、これ以上廃棄クラスを下げられない為、廃棄クラスを変えないか、或いはキューに積まずに廃棄させるようにしても良い（図３）。
【００２８】
例えば、マルチキャストパケットを出力する方路に対応するいずれかの仮想キュー長カウンタの値が予め決められた閾値を超えていた場合、廃棄クラスを、格納するキューの長さが短くなる方向に変更し、マルチキャストキューの長さが、変更後の廃棄クラスに対応する閾値を超えていた場合、マルチキャストキューにマルチキャストパケットを格納せずに廃棄するように構成することができる。また、マルチキャストパケットを出力する方路に対応するいずれかの仮想キュー長カウンタの値が予め決められた閾値を超えていなかった場合、廃棄クラスを変更せず、マルチキャストキューの長さが、廃棄クラスに対応する閾値を超えていた場合、マルチキャストキューにマルチキャストパケットを格納せずに廃棄するように構成することができる。
【００２９】
４．第４の実施の形態
更に、第１〜第３の実施の形態と出力クラスを組み合わせることもできる。
図７は、クロスバースイッチでの輻輳を回避するための機構に出力優先度を組み合わせた場合の実現方法を示す図である。一例として、第１の実施の形態と出力クラスの組み合わせ方につき図７を用いて説明する。出力クラスとはパケットの属性であり、パケットを一つの出力方路に出力するときに、出力クラスが高いパケットから優先して出力するようにするものである。出力クラスも、パケットをＣＳＷ（２）行きのマルチキャストキュー（３０１５）に積む前に、例えば前述した検索エンジン（３０２）で検索することにより得ることができる。第１〜第３の実施の形態と出力クラスを組み合わせる場合、図１、図６に示したキュー制御部（３０２０）を、出力クラス毎に設け、出力クラスによる振り分け部（３０２５）を用いて、出力クラスごとにパケットを各出力クラスのキュー制御部（３０２００、３０２０１、３０２０２、３０２０３）の一つに振り分け、各出力クラスのキュー制御部（３０２００、３０２０１、３０２０２、３０２０３）からは、パケットを出力クラスのスケジューラ（３０２４）により順番に引き抜くようにする。各出力クラスのパケットを引き抜く際の出力クラス間のスケジューリング方法としては例えば、完全優先、重み付きフェアキューイングなどが知られている。
【００３０】
Ｃ．ユニキャストとマルチキャストの中継動作
次にＣＳＷ（２）でユニキャスト中継動作になるパケットとマルチキャスト中継動作になるパケットの間の廃棄制御方法につき図８を用いて説明する。一般にネットワーク内の中継装置では、中継動作としてユニキャスト中継動作を行うべきパケットと、マルチキャスト中継動作を行うべきパケットを混在して受信し、各々のパケットを受信する毎にユニキャスト中継動作とマルチキャスト中継動作を各々行う。ユニキャスト中継動作とマルチキャスト中継動作のどちらを行うかは、例えば検索エンジン（３０２）で検索することにより得ることができ、検索結果としてユニキャスト／マルチキャストの種別と、ユニキャストの場合は宛先ＰＰＵ番号、マルチキャストの場合はＣＳＷ  ｂｉｔｍａｐが得られる。
ユニキャスト中継動作を行うパケットは、ＰＰＵ（３０Ｒ、３１Ｒ、３２Ｒ、３３Ｒ、３４Ｒ）内の転送エンジン（３０１）内のキュー制御部（３０２０）内にＣＳＷ（２）行きの仮想出力キュー（３０１２０、３０１２１、３０１２２、３０１２３、３０１２４）を、ＣＳＷ（２）の出力方路（図４の２０１、２１１、２２１、２３１、２４１）毎に独立して設ける。これらは実際に存在するキューであるが出力毎に仮想的に設けることから仮想出力キュー（ＶＯＱ）と呼ばれ、ＣＳＷ（２）でのユニキャストパケットの調停方式として知られた技術である。ＣＳＷ（２）の各出力方路が輻輳したら、輻輳しているＣＳＷ（２）の出力方路に対応する仮想出力キュー（３０１２０、３０１２１、３０１２２、３０１２３、３０１２４）からはパケットを引き抜かないようにする。
【００３１】
一方、ＣＳＷ（２）でマルチキャスト中継動作になるパケットは、ＰＰＵ（３０Ｒ、３１Ｒ、３２Ｒ、３３Ｒ、３４Ｒ）内の転送エンジン（３０１）内のキュー制御部（３０２０）内にＣＳＷ（２）行きのマルチキャストキュー（３０１５）を、例えば、一つだけ設け、図１に示した方法と同じ方法により出力方路（２０１、２１１、２２１、２３１、２４１）毎に仮想キュー長カウンタ（３０１０、３０１１、３０１２、３０１３、３０１４）を設ける。
なお、仮想出力キュー（３０１２０、３０１２１、３０１２２、３０１２３、３０１２４）と、仮想キュー長カウンタ（３０１０、３０１１、３０１２、３０１３，３０１４）とは、それぞれ同一の出力方路に対応する。
各仮想出力キュー（３０１２０、３０１２１、３０１２２、３０１２３、３０１２４）とマルチキャストキュー（３０１５）へのパケットの振り分けは、種別／宛先による振り分け部（３０２７）を用いて行う。各パケットの各仮想出力キュー（３０１２０、３０１２１、３０１２２、３０１２３、３０１２４）とマルチキャストキュー（３０１５）からの引き抜きは、種別／宛先のスケジューラ（３０２６）を用いて行う。各キューからパケットを引き抜く際のスケジューリング方法としては例えば、ユニキャストとマルチキャスト間、及び、ユニキャストの各仮想出力キューの間で重み付きフェアキューイングなどを用いることができる。
【００３２】
次に、ユニキャスト動作となるパケットとマルチキャスト動作となるパケットの間の廃棄制御方法を示す。まず考え方の整理として、ＣＳＷ（２）の出力方路（２０１、２１１、２２１、２３１、２４１）には、ユニキャスト中継動作になるパケットとマルチキャスト中継動作になるパケットが調停されて流れるので、
（数１）
ＰＰＵ内に滞留していて今後ＣＳＷ（２）の各出力方路毎に流れるトータルデータ量
＝  ユニキャストの仮想出力キュー長  ＋
マルチキャストの仮想キュー長カウンタ値
となる。
ここで、「ユニキャストの仮想出力キュー長」と「マルチキャストの仮想出力キュー長カウンタ」とは、同一の出力方路に対応するものである（以下同様）。
ＰＰＵ（３０Ｒ、３１Ｒ、３２Ｒ、３３Ｒ、３４Ｒ）内に滞留していて今後ＣＳＷ（２）の出力方路（２０１、２１１、２２１、２３１、２４１）毎に流れるトータルデータ量は、今後のＣＳＷ（２）の出力の輻輳予測量と考えることができる。
【００３３】
本実施の形態では、ユニキャストの仮想キュー（３０１２０、３０１２１、３０１２２、３０１２３、３０１２４）の各キュー長と、マルチキャストの仮想キュー長カウンタ（３０１０、３０１１、３０１２、３０１３、３０１４）の各値を閾値判定部（図１の３０１６）に送り、ユニキャストとマルチキャストの廃棄制御を行う。
閾値判定部（図１の３０１６）で行うユニキャストとマルチキャストの閾値判定方式として以下のような例が考えられる。
【００３４】
１．例１
例１は、ユニキャストとマルチキャストを公平に扱う制御方式であり、ユニキャストとマルチキャストを、それぞれでも、合計でも同様に廃棄させる。具体的には以下のようにする。ここで、ユニキャストの廃棄閾値、マルチキャストの廃棄閾値、合計の廃棄閾値は予め決めた値とする。また、以下、数３内の「マルチキャストをキューに積むときの廃棄閾値を下げる条件」とは、図２及び図３に示した閾値判定部（３０１６）により廃棄クラスを下げる条件のことを示す。
（数２）
各出力方路毎に、ユニキャストを仮想出力キューに積むときに積まずに廃棄させる条件
＝（ユニキャストの仮想出力キュー長  ＞  ユニキャストの廃棄閾値）ｏｒ
（ユニキャストの仮想出力キュー長  ＋
マルチキャストの仮想キュー長カウンタ値
＞  合計の廃棄閾値）
（数３）
マルチキャストをキューに積むときに積まずに廃棄させる条件、或いは、
マルチキャストをキューに積むときの廃棄閾値を下げる条件
＝ＣＳＷ  ｂｉｔｍａｐの１が立っている出力方路のうち、いずれかで
（マルチキャストの仮想キュー長カウンタ値  ＞  マルチキャストの廃棄閾値）
ｏｒ
（ユニキャストの仮想出力キュー長  ＋
マルチキャストの仮想キュー長カウンタ値
＞    合計の廃棄閾値）
【００３５】
ここで、「or」以降の上式について補足すると、転送エンジンは、マルチキャストパケットを出力する全方路に対応する各出力方路毎のユニキャストパケット用の仮想出力キューの長さ、及び、マルチキャストパケットを出力する全方路に対応するマルチキャストパケット用の仮想キュー長カウンタの値の、各出力方路毎の加算値と、予め定められた合計廃棄閾値とを各出力方路毎に比較することにより、廃棄制御を行う。例えば、いずれかひとつ又は予め定められた数の出力方路について、加算値が合計廃棄閾値以上のとき、パケットを廃棄するように構成することもできる。
【００３６】
２．例２
例２もユニキャストとマルチキャストを公平に扱う制御方式であるが、それぞれ、ユニキャストパケットを仮想出力キューに積むときには仮想出力キュー長のみを見て、マルチキャストパケットをマルチキャストキューに積むときにはマルチキャストの仮想キュー長カウンタ値のみを見る方式である。具体的には以下のようにする。
（数４）
ユニキャストを仮想出力キューに積むときに積まずに廃棄させる条件
＝（ユニキャストの仮想出力キュー長  ＞  ユニキャストの廃棄閾値）
（数５）
マルチキャストをキューに積むときに積まずに廃棄させる条件、或いは、
マルチキャストをキューに積むときの廃棄閾値を下げる条件
＝ＣＳＷ  ｂｉｔｍａｐの１が立っている出力方路のうち、いずれかで
（マルチキャストの仮想キュー長カウンタ値  ＞  マルチキャストの廃棄閾値）
【００３７】
３．例３
例３は、ユニキャストとマルチキャストの競合時、ユニキャストは守り、マルチキャストを優先して廃棄させる方式である。この方式は、マルチキャストとして想定しているパケットがレイヤ２フラッディングパケットであり、転送できる範囲で最大の性能を出すことを目指しているのに対し、ユニキャストとして想定しているパケットには、廃棄させてはいけないパケットが含まれる場合を想定している。具体的には以下のようにする。
（数６）
ユニキャストの廃棄条件
＝（ユニキャストの仮想出力キュー長  ＞  ユニキャストの廃棄閾値）
（数７）
マルチキャストをキューに積むときに積まずに廃棄させる条件、或いは、
マルチキャストをキューに積むときの廃棄閾値を下げる条件
＝ＣＳＷ  ｂｉｔｍａｐの１が立っている出力方路のうち、いずれかで
（マルチキャストの仮想キュー長カウンタ値  ＞  マルチキャストの廃棄閾値）
ｏｒ
（ユニキャストの仮想出力キュー長  ＋
マルチキャストの仮想キュー長カウンタ値
＞    合計の廃棄閾値）
【産業上の利用可能性】
【００３８】
以上の説明では、クロスバースイッチを用いる例を説明したが、本発明は、適宜のスイッチを用いることができる。
【符号の説明】
【００３９】
１  本実施の形態を実施する中継装置
２  クロスバースイッチＣＳＷ
２００、２１０、２２０、２３０、２４０  ＣＳＷの出力方路行きのキュー
２０１、２１１、２２１、２３１、２４１  ＣＳＷの出力方路
３０Ｒ、３１Ｒ、３２Ｒ、３３Ｒ、３４Ｒ  パケット処理機構の受信側
３０Ｔ、３１Ｔ、３２Ｔ、３３Ｔ、３４Ｔ  パケット処理機構の送信側
３０１  転送エンジン
３０１０、３０１１、３０１２、３０１３、３０１４  仮想キュー長カウンタ
３０１５  転送エンジン内ＣＳＷ行きマルチキャストキュー
３０１６  仮想キュー長カウンタの閾値判定部
３０１７  キューに積むＣＳＷ  ｂｉｔｍａｐ
３０１８  キューから引き抜いたＣＳＷ  ｂｉｔｍａｐ
３０１９  トータル仮想キュー長カウンタ
３０１１０  加算抑止機構
３０１２０、３０１２１、３０１２２、３０１２３、３０１２４  転送エンジン内仮想出力キュー
３０２  検索エンジン
３０２０  キュー制御部
３０２００、３０２０１、３０２０２、３０２０３  出力クラス毎のキュー制御部
３０２４  出力クラスのスケジューラ
３０２５  出力クラスによる振り分け部
３０２６  種別／宛先のスケジューラ
３０２７  種別／宛先による振り分け部
４０Ｒ、４１Ｒ、４２Ｒ、４３Ｒ、４４Ｒ  ネットワークインタフェース機構の受信側
４０Ｔ、４１Ｔ、４２Ｔ、４３Ｔ、４４Ｔ  ネットワークインタフェース機構の送信側
【図１】
2013131973.tif 000003
【図２】
2013131973.tif 000004
【図３】
2013131973.tif 000005
【図４】
2013131973.tif 000006
【図５】
2013131973.tif 000007
【図６】
2013131973.tif 000008
【図７】
2013131973.tif 000009
【図８】
2013131973.tif 000010