(57)【特許請求の範囲】
【請求項１】
入力インターフェイス毎に設けられ、前記入力インターフェイスに対応する出力インターフェイスに出力される所定の品質が要求される保証データを格納する保証トラフィック用入力キューと、
前記入力インターフェイス毎に設けられ、入力インターフェイスに対応する出力インターフェイスに出力される前記保証データ以外のデータを格納するベストエフォートトラフィック用入力キューと、
前記ベストエフォートトラフィック用入力キューに格納された前記保証データ以外のデータの取り出しレートをそれぞれ制御するベストエフォートトラフィック用スケジューラと、
前記ベストエフォートトラフィック用スケジューラによって前記ベストエフォートトラフィック用入力キューから取り出された前記保証データ以外のデータと、前記保証トラフィック用入力キューに格納された保証データとの取り出しレートをそれぞれ制御する保証トラフィック用スケジューラと、
前記出力インターフェイス毎に設けられ、前記保証トラフィック用スケジューラによって取り出されたデータをそれぞれ格納する出力キューと、
前記出力インターフェイス毎に設けられ、前記出力キューに格納されたデータに基づいて、対応する出力インターフェイスの輻輳を検出するキューモニターとを具備し、
前記ベストエフォートトラフィック用スケジューラ及び前記保証トラフィック用スケジューラは、対応する前記キューモニターが輻輳を検出した場合に、取り出しレートを変更することを特徴とするネットワーク間中継装置。
【請求項２】
各入力インターフェイスから入力されるパケットデータを出力インターフェイス及び通信品質クラスに基づいて分類し、この分類に基づいて前記パケットデータを前記入力インターフェイス毎に設けられた前記保証トラフィック用入力キュー及び前記ベストエフォートトラフィック用入力キューに出力するパケットフォワーダをさらに具備することを特徴とする請求項１記載のネットワーク間中継装置。
【請求項３】
前記キューモニターによって対応する出力インターフェイスの輻輳が検出された場合における前記保証トラフィック用スケジューラの前記保証トラフィック用入力キューに格納された保証データの取り出しレートは、下記式に基づいて決定されることを特徴とする請求項１記載のネットワーク間中継装置。
（対応する入力インターフェイスのトラフィックが占める保証帯域）
／（対応する出力インターフェイスの採りうる最大帯域）
【請求項４】
前記キューモニターによって対応する出力インターフェイスの輻輳が検出された場合における前記保証トラフィック用スケジューラの前記ベストエフォートトラフィック用入力キューに格納された保証データ以外のデータの取り出しレートは、下記式に基づいて決定されることを特徴とする請求項１記載のネットワーク間中継装置。
｛（対応する出力インターフェイスのとり得る最大帯域）−（対応する出力インターフェイスの保証帯域）｝
／（対応する出力インターフェイスのとり得る最大帯域）
【請求項５】
前記キューモニターによって対応する出力インターフェイスの輻輳が検出された場合におけるベストエフォートトラフィック用スケジューラの前記ベストエフォートトラフィック用入力キューに格納された前記保証データ以外のデータの取り出しレートは、下記式に基づいて決定されることを特徴とする請求項１記載のネットワーク間中継装置。
｛（対応する入力インターフェイスの採りうる最大帯域）−（対応する入力インターフェイスの保証帯域）｝／
Σ｛（入力インターフェイスの採りうる最大帯域）−（入力インターフェイスの保証帯域）｝
【請求項６】
入力インターフェイス毎に設けられ、前記入力インターフェイスに対応する出力インターフェイスに出力される所定の品質が要求される保証データを格納する保証トラフィック用入力キューと、
前記入力インターフェイス毎に設けられ、入力インターフェイスに対応する出力インターフェイスに出力される前記保証データ以外のデータを格納するベストエフォートトラフィック用入力キューと、
前記ベストエフォートトラフィック用入力キューに格納された前記保証データ以外のデータの取り出しレートを個別に制御するベストエフォートトラフィック用スケジューラと、
前記ベストエフォートトラフィック用スケジューラによって前記ベストエフォートトラフィック用入力キューから取り出された前記保証データ以外のデータと、前記保証トラフィック用入力キューに格納された保証データとの取り出しレートをそれぞれ個別に制御する保証トラフィック用スケジューラと、
前記出力インターフェイス毎に設けられ、前記保証トラフィック用スケジューラによって取り出されたデータをそれぞれ格納する出力キューと、
前記出力インターフェイス毎に設けられ、前記出力キューに格納されたデータに基づいて、対応する出力インターフェイスの輻輳を検出するキューモニターとを具備し、
前記キューモニターが対応する出力インターフェイスの輻輳を検出した場合に、対応する前記保証トラフィック用スケジューラ及び前記ベストエフォートトラフィック用スケジューラに輻輳を通知し、
前記対応するキューモニターから輻輳を通知された場合に、前記ベストエフォートトラフィック用スケジューラは前記ベストエフォートトラフィック用入力キューに格納された前記保証データ以外のデータの取り出しレートを変更し、前記保証トラフィック用スケジューラは、前記ベストエフォートトラフィック用スケジューラによって前記ベストエフォートトラフィック用入力キューから取り出された前記保証データ以外のデータと、前記保証トラフィック用入力キューに格納された保証データとの取り出しレートを変更することを特徴とするネットワーク間中継方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複数のＬＡＮ（ローカルエリアネットワーク）およびＷＡＮ（広域ネットワーク）同士を相互に接続し、それらの間でデータを中継するネットワーク間中継装置に関するものである。
【０００２】
【従来の技術】
図５は、ネットワーク間中継装置であるルータの一般的な内部ブロック図である。
【０００３】
同図に示すように、ネットワーク間中継装置は、１ポート以上のＷＡＮまたはＬＡＮのラインインタフェース（Ｌｉｎｅ＃１〜Ｌｉｎｅ＃３）を持っており、各ポートは、ＰＭＤ（Ｐｈｙｓｉｃａｌ  Ｌａｙｅｒ  Ｍｅｄｉｕｍ  Ｄｅｐｅｎｄｅｎｔ）およびＰＨＹ（Ｐｈｙｓｉｃａｌ  Ｌａｙｅｒ）１１−１〜１１−３の各機能により構成される。
【０００４】
また、ラインインタフェース毎にデータリンク層に相当するデータリンクコントローラ１２−１〜１２−３が設けられており、ラインとのパケット送受信処理が行われる。図５においては、便宜的にラインインタフェースを３ポート設けている。
【０００５】
パケットフォワーダ１３は、データリンクコントローラ１２−１〜１２−３からパケットを受信すると、パケットのアドレス、例えばＩＰ（ＩｎｔｅｒｎｅｔＰｒｏｔｏｃｏｌ）アドレスに基づいて、転送すべきラインインタフェースを判断し、該当する送信ラインインタフェース宛のパケットとして中継処理し、キューイングマネージャ１５経由でパケットバッファメモリ１４に書き込む。
【０００６】
また、逆にデータリンクコントローラ１２−１〜１２−３に送信する場合も、キューイングマネージャ１５経由でパケットバッファメモリ１４から読み出されたパケットについて、同様に中継処理を行いデータリンクコントローラ１２−１〜１２−３に対して送信要求を発行する。
【０００７】
上記中継処理には、ＩＰルータが通常行うようなパケットヘッダのフィールドのチェックや追加／削除／書き換え等の処理が含まれる。但し、ラインインタフェースから受信した時とラインインタフェースへ送信する時とでは処理内容が異なる場合がある。
【０００８】
パケットバッファメモリ１４は、パケットフォワーダ１３からキューイングマネージャ１５経由で受信したパケットを一時的に保持するためのメモリである。
【０００９】
キューイングマネージャ１５は、中継されるパケットのキューを管理する機能を持ち、パケットバッファメモリ１４に格納されているパケットデータをパケットフォワーダ１３に対して送信する順序およびタイミングをパケット毎に調整する。
【００１０】
また、キューイングマネージャ１５はパケットフォワーダ１３が送受信パケットデータをパケットバッファメモリ１４との間でリード／ライトするためのＤＭＡコントローラ機能を持ち、キューイングマネージャ１５内のスケジューラとこのＤＭＡコントローラがパケットバッファメモリをアクセスする際のアクセス権の調停を行うアービタ機能を持つ。
【００１１】
図６は、従来のネットワーク間中継装置のパケット処理系を示す図である。なお、図５と同一部分には、同一符号を付して説明する。
【００１２】
また、同図において、ラインインタフェースのデータリンクコントローラから外側の部分については省略しており、便宜上ラインインタフェースの各ポートを送信ラインと受信ラインに明示的に分けて示している。
【００１３】
同図に示すように、入力インターフェイス（Ｌｉｎｅ＃１Ｒｘ〜Ｌｉｎｅ＃３Ｒｘ）毎にＦＩＦＯバッファ（ＦＩＦＯ−１〜ＦＩＦＯ−３）が設けられている。このＦＩＦＯバッファ（ＦＩＦＯ−１〜ＦＩＦＯ−３）には、対応する入力インターフェイスから入力されるパケットデータが順次格納される。
【００１４】
パケットフォワーダ１３は、ＦＩＦＯバッファ（ＦＩＦＯ−１〜ＦＩＦＯ−３）に格納されたパケットデータを解析して、パケットデータを、その宛先の出力インターフェイス（Ｌｉｎｅ＃１Ｔｘ〜Ｌｉｎｅ＃３Ｔｘ）毎に設けられたキュー（３−１１〜３−１３、３−２１〜３−２３、３−３１〜３−３３）にキューイングする。
【００１５】
なお、上記キュー（３−１１〜３−１３、３−２１〜３−２３、３−３１〜３−３３）は、パケットバッファメモリ１４に設けられている。
【００１６】
例えば、パケットフォワーダ１３は、入力インターフェイス（Ｌｉｎｅ＃１Ｒｘ）から入力され、ＦＩＦＯ−１に格納されたパケットデータの宛先が出力インターフェイス（Ｌｉｎｅ＃１Ｔｘ）である場合には、そのパケットデータをキュー３−１１にキューイングする。
【００１７】
また、入力インターフェイス（Ｌｉｎｅ＃１Ｒｘ）から入力され、ＦＩＦＯ−１に格納されたパケットデータの宛先が出力インターフェイス（Ｌｉｎｅ＃２Ｔｘ）である場合には、そのパケットデータをキュー３−２１にキューイングする。
【００１８】
出力インターフェイス毎に設けられたキュー（３−１１〜３−１３、３−２１〜３−２３、３−３１〜３−３３）にキューイングされたパケットデータは、対応するスケジューラ４−１〜４−３によってパケットが取り出され、パケットバッファメモリ１４に出力インターフェイス（Ｌｉｎｅ＃１Ｔｘ〜Ｌｉｎｅ＃３Ｔｘ）毎に設けられたキュー５−１〜５−３にキューイングされる。
【００１９】
図７は、スケジューラ４−１〜４−３の動作を説明するための状態遷移図である。
【００２０】
ここでは、入力インターフェイスＬｉｎｅ＃１Ｒｘに対応して設けられたスケジューラ４−１を例にとり説明する。
【００２１】
まず、スケジューラ４−１は、入力インターフェイスＬｉｎｅ＃１Ｒｘに対応するキュー３−１に格納されたパケットデータの取り出しを行なう（Ｓ１）。
【００２２】
そして、キュー３−１に格納された先頭のパケットデータを全て取り出し、すなわち、キュー３−１の先頭パケットデータを最後まで取り出し終わった場合に、Ｓ２の処理に移行する。
【００２３】
Ｓ２においては、スケジューラ４−１は、入力インターフェイスＬｉｎｅ＃２Ｒｘに対応するキュー３−２に格納されたパケットデータの取り出しを行なう（Ｓ１）。
【００２４】
そして、Ｓ１と同様に、キュー３−２の先頭パケットデータを最後まで取り出し終わった場合に、Ｓ３の処理に移行する。
【００２５】
Ｓ３においても同様に、スケジューラ４−１が、キュー３−１３に格納されたパケットデータの取り出しを行ない、キュー３−１３の先頭パケットデータを最後まで取り出し終わった場合に、Ｓ１の処理に戻る。
【００２６】
なお、ここでは、スケジューラ４−１について説明したが、スケジューラ４−２、４−３についても、対応するキューについて同様の処理が行なわれる。また、各状態で該当するキューにパケットデータが存在しない場合は、その状態での処理をスキップし、次の状態に遷移する。
【００２７】
【発明が解決しようとする課題】
しかしながら、上述の従来のネットワーク間中継装置には以下のような問題があった。すなわち、ネットワーク間において伝送されるデータには、重要度が高いデータ及び低いデータがあるが、従来のネットワーク間中継装置においては、これらデータの重要度（要求される通信品質）が考慮されていない。
【００２８】
したがって、ネットワークが輻輳状態になった場合に、重要度の低いデータ（要求通信品質の低いデータ）のみならず重要度の高いデータ（要求通信品質の高いデータ）の中継も困難になってしまうという問題があった。
【００２９】
なお、ネットワーク間中継装置の１つである可変長パケットスイッチとしては、ＩＥＥＥ８０２．１Ｐ準拠のイーサネットスイッチのようにパケットに付けられた優先度に基づいて優先度の高いパケットからネットワーク上に送出して特定トラフィックの通信品質を高める優先制御機能を持つものがある。
【００３０】
しかしながら、このような可変長パケットスイッチもパケットの送出の順番を優先度に基づいて変更しているのみで、重要度の高いデータ（要求通信品質の高いデータ）の通信品質を保証するものではない。
【００３１】
また、ネットワーク間中継装置の１つである固定長セルを交換するＡＴＭ  Ｃｅｌｌスイッチでは、最小帯域を保証するＧＦＲ（Ｇｕａｒａｎｔｅｅｄ  Ｆｒａｍｅ  Ｒａｔｅ）ＱＯＳクラスを実現しているものがある。
【００３２】
しかしながら、このＡＴＭ  Ｃｅｌｌスイッチは、固定長セルに関するものであり、可変長パケットを中継するネットワーク間中継装置に適用することはできない。
【００３３】
本発明は、上記実情に鑑みてなされたものであり、可変長パケットを中継するネットワーク間中継装置において、重要度の高いデータの最小帯域を保証することができるネットワーク間中継装置を提供することを目的とする。
【００３４】
【課題を解決するための手段】
したがって、まず、上記目的を達成するために、本発明の第１の発明は、入力インターフェイス毎に設けられ、前記入力インターフェイスに対応する出力インターフェイスに出力される所定の品質が要求される保証データを格納する保証トラフィック用入力キューと、前記入力インターフェイス毎に設けられ、入力インターフェイスに対応する出力インターフェイスに出力される前記保証データ以外のデータを格納するベストエフォートトラフィック用入力キューと、前記ベストエフォートトラフィック用入力キューに格納された前記保証データ以外のデータの取り出しレートをそれぞれ制御するベストエフォートトラフィック用スケジューラと、前記ベストエフォートトラフィック用スケジューラによって前記ベストエフォートトラフィック用入力キューから取り出された前記保証データ以外のデータと、前記保証トラフィック用入力キューに格納された保証データとの取り出しレートをそれぞれ制御する保証トラフィック用スケジューラと、前記出力インターフェイス毎に設けられ、前記保証トラフィック用スケジューラによって取り出されたデータをそれぞれ格納する出力キューと、前記出力インターフェイス毎に設けられ、前記出力キューに格納されたデータに基づいて、対応する出力インターフェイスの輻輳を検出するキューモニターとを具備し、前記ベストエフォートトラフィック用スケジューラ及び前記保証トラフィック用スケジューラは、対応する前記キューモニターが輻輳を検出した場合に、取り出しレートを変更することを特徴とするネットワーク間中継装置、である。
【００３５】
このような発明によれば、保証トラフィック用スケジューラ及びベストエフォートトラフィック用スケジューラがそれぞれ保証トラフィック用入力キュー及びベストエフォートトラフィック用入力キューに格納されたキューの取り出しレートを制御することができるので、インターフェイス毎に保証帯域が保証され、かつ保証帯域内において各入力インターフェイスからの保証データの取り出しレートを設定することができる。
【００３７】
このような発明によれば、キューモニターによって出力インターフェイスの輻輳が検出された場合に、保証トラフィック用スケジューラ及びベストエフォートトラフィック用スケジューラがそれぞれ保証トラフィック用入力キュー及びベストエフォートトラフィック用入力キューに格納されたキューの取り出しレートを制御する。これにより、ネットワークの輻輳が検出された場合に、保証データの通信品質を確保することができる。
【００３８】
さらに、本発明の第２の発明は、第１の発明において、各入力インターフェイスから入力されるパケットデータを出力インターフェイス及び通信品質クラスに基づいて分類し、この分類に基づいて前記パケットデータを前記入力インターフェイス毎に設けられた前記保証トラフィック用入力キュー及び前記ベストエフォートトラフィック用入力キューに出力するパケットフォワーダをさらに具備することを特徴とするネットワーク間中継装置である。
【００３９】
さらに、本発明の第３の発明は、第１の発明において、前記キューモニターによって対応する出力インターフェイスの輻輳が検出された場合における前記保証トラフィック用スケジューラの前記保証トラフィック用入力キューに格納された保証データの取り出しレートは、下記式に基づいて決定されることを特徴とする請求項１記載のネットワーク間中継装置ネットワーク間中継装置である。
【００４０】
（対応する入力インターフェイスのトラフィックが占める保証帯域）
／（対応する出力インターフェイスの採りうる最大帯域）
さらに、本発明の第４の発明は、第１の発明において、前記キューモニターによって対応する出力インターフェイスの輻輳が検出された場合における前記保証トラフィック用スケジューラの前記ベストエフォートトラフィック用入力キューに格納された保証データ以外のデータの取り出しレートは、下記式に基づいて決定されることを特徴とするネットワーク間中継装置である。
【００４１】
｛（対応する出力インターフェイスのとり得る最大帯域）−（対応する出力インターフェイスの保証帯域）｝
／（対応する出力インターフェイスのとり得る最大帯域）
さらに、本発明の第５の発明は、第１の発明において、前記キューモニターによって対応する出力インターフェイスの輻輳が検出された場合におけるベストエフォートトラフィック用スケジューラの前記ベストエフォートトラフィック用入力キューに格納された前記保証データ以外のデータの取り出しレートは、下記式に基づいて決定されることを特徴とするネットワーク間中継装置である。
【００４２】
｛（対応する入力インターフェイスの採りうる最大帯域）−（対応する入力インターフェイスの保証帯域）｝／
Σ｛（入力インターフェイスの採りうる最大帯域）−（入力インターフェイスの保証帯域）｝
【００４３】
さらに、本発明の第６の発明は、入力インターフェイス毎に設けられ、前記入力インターフェイスに対応する出力インターフェイスに出力される所定の品質が要求される保証データを格納する保証トラフィック用入力キューと、前記入力インターフェイス毎に設けられ、入力インターフェイスに対応する出力インターフェイスに出力される前記保証データ以外のデータを格納するベストエフォートトラフィック用入力キューと、前記ベストエフォートトラフィック用入力キューに格納された前記保証データ以外のデータの取り出しレートを個別に制御するベストエフォートトラフィック用スケジューラと、前記ベストエフォートトラフィック用スケジューラによって前記ベストエフォートトラフィック用入力キューから取り出された前記保証データ以外のデータと、前記保証トラフィック用入力キューに格納された保証データとの取り出しレートをそれぞれ個別に制御する保証トラフィック用スケジューラと、前記出力インターフェイス毎に設けられ、前記保証トラフィック用スケジューラによって取り出されたデータをそれぞれ格納する出力キューと、前記出力インターフェイス毎に設けられ、前記出力キューに格納されたデータに基づいて、対応する出力インターフェイスの輻輳を検出するキューモニターとを具備し、前記キューモニターが対応する出力インターフェイスの輻輳を検出した場合に、対応する前記保証トラフィック用スケジューラ及び前記ベストエフォートトラフィック用スケジューラに輻輳を通知し、前記対応するキューモニターから輻輳を通知された場合に、前記ベストエフォートトラフィック用スケジューラは前記ベストエフォートトラフィック用入力キューに格納された前記保証データ以外のデータの取り出しレートを変更し、前記保証トラフィック用スケジューラは、前記ベストエフォートトラフィック用スケジューラによって前記ベストエフォートトラフィック用入力キューから取り出された前記保証データ以外のデータと、前記保証トラフィック用入力キューに格納された保証データとの取り出しレートを変更することを特徴とするネットワーク間中継方法である。
【００５０】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態に係るネットワーク間中継装置について説明する。
【００５１】
ネットワーク間中継装置の内部ブロック図については、図５に示したものと同様であるのでここでは、省略する。ただし、本実施の形態においては、キューイングマネージャ、パケットフォワーダなどの機能が異なる。
【００５２】
図１は、本発明の実施の形態に係るネットワーク間中継装置のパケット処理系を示す図である。同図において、ラインインタフェースのデータリンクコントローラから外側の部分については省略しており、また便宜上ラインインタフェースの各ポートを送信ラインと受信ラインに明示的に分けて示している。
【００５３】
同図に示すように、入力インターフェイス（Ｌｉｎｅ＃１Ｒｘ〜Ｌｉｎｅ＃３Ｒｘ）毎にＦＩＦＯバッファ４１−１〜４１−３が設けられている。このＦＩＦＯバッファ４１−１〜４１−３には、対応する入力インターフェイスから入力されるパケットデータが順次格納される。
【００５４】
パケットフォワーダ３１は、ＦＩＦＯバッファ４１−１〜４１−３に格納されたパケットデータを解析して、パケットデータを、その宛先の出力インターフェイス（Ｌｉｎｅ＃１Ｔｘ〜Ｌｉｎｅ＃３Ｔｘ）毎に設けられたキュー（４２Ｇ−１１〜４２Ｇ−１３、４２Ｂ−１１〜４２Ｂ−１３、４２Ｇ−２１〜２３、４２Ｂ−２１〜４２Ｂ−２３、４２Ｇ−３１〜３３、４２Ｂ−３１〜３３）にキューイングする。
【００５５】
なお、上記キュー（４２Ｇ−１１〜４２Ｇ−１３、４２Ｂ−１１〜４２Ｂ−１３、４２Ｇ−２１〜２３、４２Ｂ−２１〜４２Ｂ−２３、４２Ｇ−３１〜３３、４２Ｂ−３１〜３３）は、パケットバッファメモリ３２に設けられている。
【００５６】
また、上記キューは、帯域保証クラス用のキュー（４２Ｇ−１１〜４２Ｇ−１３、４２Ｇ−２１〜２３、４２Ｇ−３１〜３３）及びベストエフォートクラス用のキュー（４２Ｂ−１１〜１３、４２Ｂ−２１〜２３、４２Ｂ−３１〜３３）にグループ分けされている。
【００５７】
例えば、パケットフォワーダ３１は、入力インターフェイス（Ｌｉｎｅ＃１Ｒｘ）から入力され、ＦＩＦＯ４１−１に格納されたパケットデータの宛先が出力インターフェイス（Ｌｉｎｅ＃１Ｔｘ）である場合であって、かつ帯域保証クラス用のパケットである場合には、そのパケットデータをキュー４２Ｇ−１１にキューイングする。
【００５８】
また、入力インターフェイス（Ｌｉｎｅ＃１Ｒｘ）から入力され、ＦＩＦＯ４１−１に格納されたパケットデータの宛先が出力インターフェイス（Ｌｉｎｅ＃２Ｔｘ）である場合であって、かつベストエフォートクラス用のパケットである場合には、そのパケットデータをキュー４２Ｂ−２１にキューイングする。
【００５９】
ベストエフォートクラス用のスケジューラ４４−１〜４４−３は、それぞれ出力インターフェイス（Ｌｉｎｅ＃１Ｔｘ〜Ｌｉｎｅ＃３Ｔｘ）毎に設けられ、対応するキュー（４２Ｂ−１１〜４２Ｂ−１３、４２Ｂ−２１〜２３、４２Ｂ−３１〜３３）からそれぞれパケットデータを取り出す。
【００６０】
また、対応するキューモニタ４８−１〜４８−３から出力インターフェイスの輻輳が通知された場合に、対応するキュー（４２Ｂ−１１〜４２Ｂ−１３、４２Ｂ−２１〜２３、４２Ｂ−３１〜３３）からのパケットデータの取り出しレートを変更する機能を有する。なお、各キューへのパケットデータのキューイングの制御はキューイングマネージャ３３が行なう。
【００６１】
帯域保証クラス用のスケジューラ４３−１〜４３−３は、それぞれ出力インターフェイス（Ｌｉｎｅ＃１Ｔｘ〜Ｌｉｎｅ＃３Ｔｘ）毎に設けられ、対応するキュー（４２Ｇ−１１〜１３、４２Ｇ−２１〜２３、４２Ｇ−３１〜３３）及びベストエフォートクラス用のスケジューラ４４−１〜４４−３から送出されるパケットデータを格納するＦＩＦＯメモリ４５−１〜４５−３からそれぞれパケットデータを取り出す。
【００６２】
これら帯域保証クラス用のスケジューラ４３−１〜４３−３によって取り出されたパケットデータは、パケットバッファメモリ３２に出力インターフェイス（Ｌｉｎｅ＃１Ｔｘ〜Ｌｉｎｅ＃３Ｔｘ）毎に設けられたキュー４６−１〜４６−３にキューイングされる。
【００６３】
ＦＩＦＯ４７−１〜４７−３は、出力インターフェイス（Ｌｉｎｅ＃１Ｔｘ〜Ｌｉｎｅ＃３Ｔｘ）毎に設けられ、対応するキュー４６−１〜４６−３から送出されるパケットデータをバッファリングし、順次対応する出力インターフェイス（Ｌｉｎｅ＃１Ｔｘ〜Ｌｉｎｅ＃３Ｔｘ）に出力する。
【００６４】
次に、本発明の実施の形態に係るネットワーク間中継装置の動作について説明する。
【００６５】
入力インターフェイス（Ｌｉｎｅ＃１Ｒｘ〜Ｌｉｎｅ＃３Ｒｘ）を介して受信され、パケットフォワーダ３１により中継処理が行なわれたパケットは、パケットフォワーダ３１内部のＦＩＦＯ４１−１〜４１−３経由で、出力インターフェイス（Ｌｉｎｅ＃１Ｔｘ〜Ｌｉｎｅ＃３Ｔｘ）及び通信品質クラス（帯域保証クラス、ベストエフォートクラス）毎に振り分けられて、対応するキュー（４２Ｇ−１１〜４２Ｇ−１３、４２Ｂ−１１〜４２Ｂ−１３、４２Ｇ−２１〜２３、４２Ｂ−２１〜４２Ｂ−２３、４２Ｇ−３１〜３３、４２Ｂ−３１〜３３）にキューイングされる。
【００６６】
ベストエフォートクラス用のスケジューラ（４４−１〜４４−３）では、パケットバッファメモリ３２上の入力インタフェース（Ｌｉｎｅ＃１Ｒｘ〜Ｌｉｎｅ＃３Ｒｘ）毎のキューから成るキューグループ（４２Ｂ−１１〜４２Ｂ−１３、４２Ｂ−２１〜２３、４２Ｂ−３１〜３３）において、どの順番でどのタイミングでパケットデータを読み出し、次段のＦＩＦＯメモリ４５−１〜４５−３に書き込むかのスケジューリング処理が行われる。
【００６７】
また、帯域保証クラス用のスケジューラ４３−１〜４３−３では、パケットバッファメモリ３２上の入力インタフェース（Ｌｉｎｅ＃１Ｒｘ〜Ｌｉｎｅ＃３Ｒｘ）毎のキュー（４２Ｇ−１１〜４２Ｇ−１３、４２Ｇ−２１〜２３、４２Ｇ−３１〜３３）と、ベストエフォートクラス用スケジューラ（４４−１〜４４−３）の次段ＦＩＦ０メモリ（４５−１〜４５−３）から成るキューグループにおいて、どの順番でどのタイミングでパケットデータを読み出し、次段のパケットバッファメモリ３２上のキュー４６−１〜４６−３に書き込むかのスケジューリング処理が行われる。
【００６８】
キューイングマネージャ３３は、帯域保証クラス用スケジューラ４３−１〜４３−３がパケットバッファメモリ３２上に送信パケットデータを書き込み、該当する出力インターフェイス用のバッファキュー（４６−１〜４６−３）につなぐと、パケットフォワーダ３１に対してパケットデータの送信処理要求を発行する。
【００６９】
その他、キューイングマネージャ３３は、出力インターフェイス用キュー（送信キュー）４６−１〜４６−３毎にキュー長を監視するキューモニタ４８−１〜４８−３を持っている。
【００７０】
キューモニタ４８−１〜４８−３と帯域保証クラス用スケジューラ４３−１〜４３−３とはそれぞれ輻輳信号線４９−１ａ〜４９−３ａで結ばれており、キューモニタ４８−１〜４８−３とベストエフォートクラス用スケジューラ４４−１〜４４−３との間は輻輳信号線４９−１ｂ〜４９−３ｂで結ばれている。
【００７１】
そして、送信キュー４６−１〜４６−３の長さがあらかじめ設定された閾値を超えると出力インタフェース（Ｌｉｎｅ＃１Ｔｘ〜Ｌｉｎｅ＃３Ｔｘ）側で輻輳が発生したと判断し、輻輳信号線（４９−１ａ〜４９−３ａ、４９−１ｂ〜４９−３ｂ）経由で帯域保証クラス用スケジューラ４３−１〜４３−３とベストエフォートクラス用スケジューラ４４−１〜４４−３に対してそれぞれ輻輳通知を行う。
【００７２】
また、キューの長さがあらかじめ設定された閾値（ヒステリシスを持たせるために、輻輳発生の判断に使用する閾値とは違う値を設定する場合がある）を下回ると、通知は解除される。
【００７３】
ベストエフォートクラス用スケジューラ４４−１〜４４−３と帯域保証クラス用スケジューラ４３−１〜４３−３は、自身に該当する出力インタフェース（Ｌｉｎｅ＃１Ｔｘ〜Ｌｉｎｅ＃３Ｔｘ）についての輻輳通知を受信すると、スケジューリングアルゴリズムを変更する。輻輳通知が解除されると、通常のスケジューリングアルゴリズムに戻る。なお、変更後のスケジューリングについては、図２及び図３を参照して後に説明する。
【００７４】
パケットフォワーダ３１は、入力インタフェース（Ｌｉｎｅ＃１Ｒｘ〜Ｌｉｎｅ＃３Ｒｘ）からパケットデータを受信すると、入力インタフェース番号とパケットの転送先である出力インタフェース番号、通信品質クラス（帯域保証クラス、ベストエフォートクラス）を判断し、パケットバッファメモリ３２にパケットデータを書き込んで、該当するキュー（４２Ｇ−１１〜４２Ｇ−１３、４２Ｂ−１１〜４２Ｂ−１３、４２Ｇ−２１〜２３、４２Ｂ−２１〜４２Ｂ−２３、４２Ｇ−３１〜３３、４２Ｂ−３１〜３３）につなぎ、キューイングマネージャ３３に対して受信通知を行う。
【００７５】
また、キューイングマネージャ３３からパケットの送信処理要求を受けると、パケットバッファメモリ３２上の送信キュー４６−１〜４６−３からパケットデータを読み出し、該当する出力インタフェース（Ｌｉｎｅ＃１Ｔｘ〜Ｌｉｎｅ＃３Ｔｘ）に対してパケットを出力する。
【００７６】
図２は、キューイングマネージャ３３内部の帯域保証クラス用スケジューラ４３−１〜４３−３の状態遷移図である。
【００７７】
Ｓ１０，Ｓ１１，Ｓ２１〜Ｓ２（ｋ＋１），Ｓ３１〜Ｓ３（ｋ＋１）は、各状態を識別するための記号である［図１の例では、ｋ＝３となる］。
【００７８】
通常はアイドル状態Ｓ１０にあり、スイッチインタフェースからのパケット受信通知を受けると、ステータスチェック状態Ｓ１１に遷移する。
【００７９】
処理対象とするキューグループの内いずれかのキューにパケットデータが存在し、かつキューモニタが輻輳無し状態を示していれば、受信ライン入力インターフェイスＬｉｎｅ＃１Ｒｘのキューからパケットデータを読み出す状態Ｓ２１に遷移する。
【００８０】
そこで、パケットデータを先頭からあるバイト数単位に順次読み出しては次段のＦＩＦＯメモリに書き込み、パケットの最後尾までを読み終わると、次の入力インターフェイスＬｉｎｅ＃２Ｒｘのキューからパケットデータを読み出す状態Ｓ２２に遷移し、以降同様に現在の状態に対応する受信ラインのキューからパケットデータを読み出しては次段ＦＩＦＯに書き込む。
【００８１】
全ての入力インタフェース数分遷移すると今度はベストエフォートクラス用スケジューラから出力される側のＦＩＦＯからパケットデータを読み出す状態Ｓ２（ｋ＋１）に遷移し、入力インタフェース用キューからの場合と同様にパケットデータを順次読み出しては次段のＦＩＦＯメモリに書き込み、パケットの最後尾までを読み終わると、Ｓ１１の状態に戻る。
【００８２】
この時点でまだキューグループの内いずれかのキューにパケットデータが存在すると、再度Ｓ２１に状態遷移する。また、各状態で該当するキューにパケットデータが存在しない場合は、その状態での処理をスキップし、次の状態に遷移する。
【００８３】
処理対象とするキューグループの内いずれかのキューにパケットデータが存在し、かつ輻輳信号線が輻輳状態を示していれば、入力インターフェイスＬｉｎｅ＃１Ｒｘのキューからパケットデータを読み出す状態Ｓ３１に遷移する。
【００８４】
Ｓ３１においては、パケットデータを先頭から順次読み出すための読み出しポインタ（パケットバッファメモリ上のアドレスを示す）をある単位例えばバイト単位で移動させる。もし、ポインタがパケットデータの最後尾まで達したならば、該当するパケットデータを全て読み出して次段のＦＩＦＯメモリに書き込む。
【００８５】
あらかじめ設定された回数ＶＡＬ＿Ｌ１回までポインタ移動を繰り返すか、またはポインタがパケットデータの最後尾まで達してパケットデータを全て次段のＦＩＦＯメモリに書き込むと、次の入力インターフェイスＬｉｎｅ＃２Ｒｘのキューからパケットデータを読み出す状態Ｓ３２に遷移し、以降同様に該当するキューからパケットデータを読み出して次段ＦＩＦＯに書き込むためのポインタ操作を行う。
【００８６】
全ての受信インタフェース数分遷移すると今度はベストエフォートクラス用スケジューラ出力ＦＩＦＯからパケットデータを読み出す状態Ｓ３（ｋ＋１）に遷移し、受信インタフェース用キューの場合と同様にパケットデータの読み出しポインタ（ＦＩＦＯメモリ上のアドレスを示す）をある単位で順次移動し、パケットデータの最後尾に達するとパケットデータ全体を読み出して次段のＦＩＦＯメモリに書き込み。
【００８７】
あらかじめ設定された回数ＶＡＬ＿ＢＥ回までポインタ操作を繰り返すか、またはポインタがパケットデータの最後尾に達してパケットデータ全体を次段ＦＩＦＯメモリに書き込むと、Ｓ１１の状態に戻る。
【００８８】
この時点でまだキューグループの内いずれかのキューにパケットデータが存在すると、再度Ｓ３１に状態遷移する。また、各状態で該当するキューにパケットデータが存在しない場合は、その状態での処理をスキップし、次の状態に遷移する。
【００８９】
ＶＡＬ＿Ｌ１〜ＶＡＬ＿ＬＫは、該当する各入力インタフェースから入力されるトラフィック（パケット列）が転送先ライン上に占める保証帯域の比率に基づいて決定される。また、ＶＡＬ＿ＢＥは、転送先の出力インターフェイスの取り得る最大帯域と合計保証帯域の差分に基づいて決定される。ＶＡＬ＿Ｌ１〜ＶＡＬ＿ＬＫ，ＶＡＬ＿ＢＥは以下の関係が成り立つ。
【００９０】
【数１】
0004439100.tif 000002
【００９１】
【数２】
0004439100.tif 000003
【００９２】
なお、上記式において、「出力インターフェイスの保証帯域」は、各入力インターフェイスにおいて転送される宛先が当該出力インターフェイスのトラフィックの保証帯域の合計と等しい。
【００９３】
また、状態Ｓ１１において、処理対象とするキューグループの内いずれかのキューにパケットデータが存在しない場合には、アイドル状態Ｓ１０に遷移する。
【００９４】
図３は、キューイングマネージャ３３内部のベストエフォートクラス用スケジューラ４４−１〜４４−３の状態遷移図である。図２に示す帯域保証クラス用スケジューラが取り得る状態から状態Ｓ２（ｋ＋１）および状態Ｓ３（ｋ＋１）を削除した内容となっている。また、出力インタフェース輻輳状態でのキュー読み出し回数が異なっている。
【００９５】
ＶＡＬ＿ＢＥ＿Ｌ１〜ＶＡＬ＿ＢＥ＿ＬＫは、該当する各入力インタフェースから入力されるトラフィック（パケット列）が入力インターフェイス上で占める保証帯域の比率に基づいて決定される。ＶＡＬ＿ＢＥ＿Ｌ１〜ＶＡＬ＿ＢＥ＿ＬＫは以下の関係が成り立つ。
【００９６】
【数３】
0004439100.tif 000004
【００９７】
なお、ベストエフォートクラス用のスケジューラ（４４−１〜４４−３）及び帯域保証クラス用のスケジューラ４３−１〜４３−３は、それぞれ対応するキュー（４２Ｇ−１１〜４２Ｇ−１３、４２Ｂ−１１〜４２Ｂ−１３、４２Ｇ−２１〜２３、４２Ｂ−２１〜４２Ｂ−２３、４２Ｇ−３１〜３３、４２Ｂ−３１〜３３）から上述の説明にしたがったアルゴリズムでパケットデータを読み出すが、読み取ったパケットデータがパケットの途中である場合には、次段のＦＩＦＯメモリ（４５−１〜４５−３）或いはキュー（４６−１〜４６−３）に読み取ったパケットデータを出力せず、完全にパケット全体を読み取った後に、次段のＦＩＦＯメモリ（４５−１〜４５−３）或いはキュー（４６−１〜４６−３）にパケットデータを出力する。
【００９８】
したがって、本実施の形態のネットワーク間中継装置によれば、出力インターフェイスの輻輳が検出された場合に、輻輳が検出された出力インターフェイスに対応する各スケジューラがパケットの取り出しレートを変更することができるので、入力インターフェイス毎に通信品質が要求されるデータの最小帯域を保証することができる。
【００９９】
図４は、パケットバッファメモリ上のパケットバッファキューの構造を示す。
【０１００】
キューはパケットデータが格納されるｊ個のバッファとその先頭ポインタ（メモリ上のアドレス）を示すキューディスクリプタから成る。
【０１０１】
キューディスククリプタには、各パケットバッファに対応したｊ個のエントリが存在し、各エントリはバッファ先頭ポインタを示すフィールドとバッファ内のパケットデータサイズを示すフィールドから成る。これらのエントリはサイクリックに使用される。
【０１０２】
そのほかキューディスクリプタはキューイングされたパケットデータの合計であるトータルデータサイズを示すフィールドを持ち、またキューイングマネージャ内のスケジューラとＤＭＡコントローラがキューを操作する際に両者の間でディスクリプタ・アクセスの排他を行うためのセマフォー・フィールドを持つ。
【０１０３】
キューイングマネージャ内には、キューディスクリプタの先頭ポインタと末尾ポインタを格納するレジスタが存在し、また実際のキューの先頭エントリと末尾エントリのそれぞれの先頭ポインタを格納するレジスタが存在する。
【０１０４】
このキューの先頭エントリと末尾エントリのそれぞれの先頭ポインタが示す位置の間に存在するエントリがキューに相当する。また、先頭エントリと末尾エントリのそれぞれの先頭ポインタ値が等しい場合には、キューイングマネージャはキューにパケットデータが存在しないと判断する。
【０１０５】
各種スケジューラがパケットデータを読み出す際や、パケットフォワーダへパケットデータを出力するためにＤＭＡコントローラがパケットデータを読み出す際には、先頭エントリのポインタ格納レジスタを参照してキューディスクリプタ上の先頭エントリの位置を割り出し、続いてエントリ内のバッファ先頭ポインタからキューの先頭パケットデータの位置を導き出す。
【０１０６】
パケットデータの読み出し終了後、先頭エントリのポインタ格納レジスタの値を次のエントリのポインタの値に置き換える。
【０１０７】
パケットフォワーダからパケットデータを入力するためにＤＭＡコントローラがパケットデータを書き込む際には、末尾エントリのポインタ格納レジスタを参照してキューディスクリプタ上の末尾エントリの位置を割り出す。キューの末尾に続く次のエントリがフリー・バッファの位置を示すため、そのバッファにパケットデータを書き込む。
【０１０８】
パケットデータの書き込み終了後、末尾エントリのポインタ格納レジスタの値を次のエントリのポインタの値に置き換える。
【０１０９】
また、キューディスクリプタ上のトータルデータサイズ・フィールドにパケットデータサイズ分を加算する。
【０１１０】
逆に、各種スケジューラがパケットデータを読み出す際や、パケットフォワーダへパケットデータを出力するためにＤＭＡコントローラがパケットデータを読み出す際には、トータルデータサイズ・フィールドにパケットデータサイズ分を減算する。
【０１１１】
このトータルデータサイズ・フィールドの値が０でなければ、当該キューにパケットデータが存在することになる。
【０１１２】
すなわち、本実施の形態においては、各スケジューラは、入力キューからのデータの読み出しの際に、パケットデータを読み出すポインタをある単位で移動させ、ポインタがパケットデータの最後尾に達するまではキューから出力しないで、１度に読み出す読み出し単位をの数を変えることで、読み出しレートを制御する。
【０１１３】
なお、本実施の形態においては、帯域保証クラス用のスケジューラ及びベストエフォートクラス用のスケジューラによってスケジューリングをする場合について説明したが、ベストエフォートクラス用のスケジューラによる取り出しレートの変更は必ずしも必須の構成要素ではない。
【０１１４】
すなわち、ベストエフォートクラス用キュー（４２Ｂ−１１〜４２Ｂ−１３、４２Ｂ−２１〜２３、４２Ｂ−３１〜３３）にパケットデータが格納されると、ベストエフォートクラス用のスケジューラによって取り出しレートの変更をすることなく、各キュー（４２Ｂ−１１〜４２Ｂ−１３、４２Ｂ−２１〜２３、４２Ｂ−３１〜３３）から順番にパケットデータが取り出されて、対応するＦＩＦＯ（４５−１〜４５−３）に格納される構成としてもよい。
【０１１５】
この場合、取り出しレートの変更は帯域保証クラス用のスケジューラのみで行なわれることになる。
【０１１６】
したがって、本実施の形態のネットワーク間中継装置によれば、出力インタフェースの輻輳時でも、入力インタフェース毎に設定された帯域を保証し、かつ当該出力インタフェースの残りの帯域を入力インタフェース毎のベストエフォートトラフィックの割合で割り当てることができる。
【０１１７】
結果的に、入力インタフェース毎に最小帯域の保証が可能となり、かつ入力インタフェースの限界帯域に応じた割合でパケット中継を行うことにより、公平さを保つことができる。
【０１１８】
また、可変長パケットを転送するネットワークにおいて、中継装置の入出力インタフェース間の最小帯域を保証することにより、その区間を経由する通信の最低限のスループットを予測することができるようになる。
【０１１９】
なお、本願発明は、上記各実施形態に限定されるものでなく、実施段階ではその要旨を逸脱しない範囲で種々に変形することが可能である。また、実施形態に示される全構成要件から幾つかの構成要件が省略されることで発明が抽出された場合には、その抽出された発明を実施する場合には省略部分が周知慣用技術で適宜補われるものである。
【０１２０】
また、実施形態に記載した手法は、計算機（コンピュータ）に実行させることができるプログラム（ソフトウエア手段）として、例えば磁気ディスク（フロッピーディスク、ハードディスク等）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤ、ＭＯ等）、半導体メモリ（ＲＯＭ、ＲＡＭ、フラッシュメモリ等）等の記録媒体に格納し、また通信媒体により伝送して頒布することもできる。なお、媒体側に格納されるプログラムには、計算機に実行させるソフトウエア手段（実行プログラムのみならずテーブルやデータ構造も含む）を計算機内に構成させる設定プログラムをも含む。なお、本明細書でいう記録媒体は、頒布用に限らず、計算機内部あるいはネットワークを介して接続される機器に設けられた磁気ディスクや半導体メモリ等の記憶媒体を含むものである。
【０１２１】
【発明の効果】
以上詳記したように、本発明によれば、可変長パケットを中継するネットワーク間中継装置において、重要度の高いデータの最小帯域を保証することができるネットワーク間中継装置を提供することができる。
【図面の簡単な説明】
【図１】本発明の実施の形態に係るネットワーク間中継装置のパケット処理系を示す図。
【図２】キューイングマネージャ３３内部の帯域保証クラス用スケジューラ４３−１〜４３−３の状態遷移図。
【図３】キューイングマネージャ３３内部のベストエフォートクラス用スケジューラ４４−１〜４４−３の状態遷移図。
【図４】パケットバッファメモリ上のパケットバッファキューの構造を示す図。
【図５】ネットワーク間中継装置であるルータの一般的な内部ブロック図。
【図６】従来のネットワーク間中継装置のパケット処理系を示す図。
【図７】スケジューラ４−１〜４−３の動作を説明するための状態遷移図。
【符号の説明】
３−１１〜３−１３、３−２１〜３−２３、３−３１〜３−３３…キュー、
４−１〜４−３…スケジューラ、
５−１〜５−３…キュー、
１１−１〜１１−３…ＰＭＤ／ＰＨＹ、
１２−１〜１２−３…データリンクコントローラ、
１３…パケットフォワーダ、
１４…パケットバッファメモリ、
１５…キューイングマネージャ、
３１…パケットフォワーダ、
３２…パケットバッファメモリ、
３３…キューイングマネージャ、
４１−１〜４１−３…ＦＩＦＯ、
４２Ｇ−１１〜１３、４２Ｇ−２１〜２３、４２Ｇ−３１〜３３…帯域保証クラス用のキュー、
４２Ｂ−１１〜１３、４２Ｂ−２１〜２３、４２Ｂ−３１〜３３…ベストエフォートクラス用のキュー、
４３−１〜４…帯域保証クラス用のスケジューラ、
４４−１〜４…ベストエフォートクラス用のスケジューラ、
４５−１〜３…ＦＩＦＯメモリ、
４６−１〜３…キュー、
４７−１〜３…ＦＩＦＯ，
４８−１〜３…キューモニター、
４９−１ａ，１ｂ、４９−２ａ、２ｂ，４９−３ａ，３ｂ…輻輳信号線。
【図１】
0004439100.tif 000005
【図２】
0004439100.tif 000006
【図３】
0004439100.tif 000007
【図４】
0004439100.tif 000008
【図５】
0004439100.tif 000009
【図６】
0004439100.tif 000010
【図７】
0004439100.tif 000011