(57)【特許請求の範囲】
【請求項１】
入力パケットを分類する分類手段と、この分類手段によって分類されたパケットをそれぞれ蓄積する複数のキューと、該複数のキューに蓄積されたパケットの中からいずれかのパケットを選択して出力するスケジューラとを有するパケット処理装置において、
前記分類手段により分類されたパケットを第１のキューに挿入する際に、このパケットに対応する疑似パケットを作成して第２のキューに挿入する疑似パケット入力手段と、
前記疑似パケット入力手段により第２のキューに挿入された疑似パケットが前記スケジューラの処理対象とされた際に、当該疑似パケットに代えて前記第１のキューのパケットを第２のキューからの出力として処理する処理手段と、
を備えたことを特徴とするパケット処理装置。
【請求項２】
前記疑似パケット入力手段は、前記第１のキューに挿入するパケットと該パケットに対応する前記第２のキューに挿入する疑似パケットとを相互に関連づけることを特徴とする請求項１に記載のパケット処理装置。
【請求項３】
前記処理手段は、前記疑似パケットが該疑似パケットに対応する前記第１のキューに挿入されたパケットよりも先にスケジューラの処理対象とされた場合には、当該疑似パケットに対応する前記第１のキューのパケットを第２のキューからの出力として処理し、前記疑似パケットよりも該疑似パケットに対応する前記第１のキューに挿入されたパケットの方が先にスケジューラの処理対象とされた場合には、当該パケットを処理するとともに前記疑似パケットを無効化することを特徴とする請求項２に記載のパケット処理装置。
【請求項４】
前記第１のキューに挿入するパケットは、該パケットが実パケットであることを示す識別情報と、該疑似パケットへのリンク情報とを有し、前記第２のキューに挿入する疑似パケットは、疑似パケットであることを示す識別情報と、該疑似パケットに対応する実パケットへのリンク情報とを有することを特徴とする請求項２または３に記載のパケット処理装置。
【請求項５】
前記疑似パケット入力手段は、前記第２のキューに挿入する疑似パケットと前記第１のキューとを関連づけることを特徴とする請求項１に記載のパケット処理装置。
【請求項６】
前記処理手段は、第２のキューの前記疑似パケットがスケジューラの処理対象とされた際に、前記第１のキューにパケットが存在する場合には、前記第１のキューの先頭に所在するパケットを第２のキューからの出力として処理し、前記疑似パケットに対応する前記第１のキューにパケットが存在せず、かつ、前記第２のキューの次のパケットが存在する場合には、そのパケットをスケジューラの処理対象とし、前記疑似パケットに対応する前記第１のキューにパケットが存在せず、かつ、前記第２のキューの次のパケットが存在しない場合には、再スケジューリングをおこなうことを特徴とする請求項５に記載のパケット処理装置。
【請求項７】
前記第２のキューに挿入する疑似パケットは、疑似パケットであることを示す識別情報と、前記第１のキューへのリンク情報とを有することを特徴とする請求項５または６に記載のパケット処理装置。
【請求項８】
前記複数のキューは、出力バンド幅を予約した複数の予約キューおよびベストエフォートキューからなり、前記第１のキューは前記複数の予約キューのいずれかに対応し、前記第２のキューは前記ベストエフォートキューに対応することを特徴とする請求項１〜７のいずれか一つに記載のパケット処理装置。
【請求項９】
入力パケットを分類し、分類したパケットをそれぞれ複数のキューに蓄積し、該複数のキューに蓄積されたパケットの中からいずれかのパケットをスケジューラによって選択して出力するパケット処理方法において、
前記分類したパケットを第１のキューに挿入する際に、このパケットに対応する疑似パケットを作成して第２のキューに挿入する疑似パケット入力工程と、
前記疑似パケット入力工程において第２のキューに挿入された疑似パケットが前記スケジューラの処理対象とされた際に、当該疑似パケットに代えて前記第１のキューのパケットを第２のキューからの出力として処理する処理工程と、
を含むことを特徴とするパケット処理方法。
【請求項１０】
前記疑似パケット入力工程は、前記第１のキューに挿入するパケットと該パケットに対応する前記第２のキューに挿入する疑似パケットとを相互に関連づけることを特徴とする請求項９に記載のパケット処理方法。
【請求項１１】
前記処理工程は、前記疑似パケットが該疑似パケットに対応する前記第１のキューに挿入されたパケットよりも先にスケジューラの処理対象とされた場合には、当該疑似パケットに対応する前記第１のキューのパケットを第２のキューからの出力として処理し、前記疑似パケットよりも該疑似パケットに対応する前記第１のキューに挿入されたパケットの方が先にスケジューラの処理対象とされた場合には、当該パケットを処理するとともに前記疑似パケットを無効化することを特徴とする請求項１０に記載のパケット処理方法。
【請求項１２】
前記疑似パケット入力工程は、前記第２のキューに挿入する疑似パケットと前記第１のキューとを関連づけることを特徴とする請求項９に記載のパケット処理方法。
【請求項１３】
前記処理工程は、第２のキューの前記疑似パケットがスケジューラの処理対象とされた際に、前記第１のキューにパケットが存在する場合には、前記第１のキューの先頭に所在するパケットを第２のキューからの出力として処理し、前記疑似パケットに対応する前記第１のキューにパケットが存在せず、かつ、前記第２のキューの次のパケットが存在する場合には、そのパケットをスケジューラの処理対象とし、前記疑似パケットに対応する前記第１のキューにパケットが存在せず、かつ、前記第２のキューの次のパケットが存在しない場合には、再スケジューリングをおこなうことを特徴とする請求項１２に記載のパケット処理装置。
【請求項１４】
前記複数のキューは、出力バンド幅を予約した複数の予約キューおよびベストエフォートキューからなり、前記第１のキューは前記複数の予約キューのいずれかに対応し、前記第２のキューは前記ベストエフォートキューに対応することを特徴とする請求項９〜１３のいずれか一つに記載のパケット処理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、入力パケットを分類し、分類したパケットをそれぞれ複数のキューに蓄積し、該複数のキューに蓄積されたパケットの中からいずれかのパケットをスケジューラによって選択して出力するパケット処理装置およびパケット処理方法に関する。
【０００２】
近年、音声や動画などの実時間通信がＩＰ上で実現することが可能となり、また企業の基幹業務通信にもＩＰが利用されつつあるため、かかるＩＰを用いた場合の通信品質の保証が重要となってきた。このため、たとえばＲＳＶＰ（resorce ReSaVation Protcol）などの予約プロトコルを用いてエンドツーエンドで品質を予約するシグナリングや、ＷＦＱ（Weight Fair Queueing）などのバンド幅スケジューラを用いて通信パス上のノードで品質を保証するトラフィック制御がおこなわれている。
【０００３】
【従来の技術】
従来、ＴＣＰ／ＩＰ体系の中核となるインターネットプロトコル（ＩＰ）は、目的地までの配送に関して最善の努力を払う反面、その確実な配送は保証しないというベストエフォート型（以下「ＢＥＳ」という）の配送をその特徴とするため、利用可能なバンド幅などの品質については保証されない。
【０００４】
しかし、最近になって音声や動画などの実時間通信がＩＰ上で実現することが可能となり、また企業の基幹業務通信にもＩＰが利用されつつあるため、かかるＩＰを用いた場合の通信品質の保証が重要となっている。このため、ＲＳＶＰなどの予約プロトコルを用いてエンドツーエンドで品質を予約するシグナリングや、ＷＦＱなどのバンド幅スケジューラを用いて通信パス上のノードで品質を保証するトラフィック制御がおこなわれている。
【０００５】
具体的には、図１４に示すように、ルーティング処理部１４０でルーティング処理されたパケットをクラシファイア（classifier）１４１でストリームに分類し、パケット廃棄部１４２でパケットを廃棄するか否かを判断し、廃棄しないパケットをストリームごとのキューに入力し、スケジューラ１４３が適切な順序でパケットを選択出力することにより、通信品質が保証される。
【０００６】
なお、フィルタ１４１ａ〜１４１ｃは、入力パケットを予約キュー１４３ａ〜１４３ｃに加えるか否かのフィルタリングをおこない、いずれの予約キューにも属さないものは、ベストエフォートキュー（以下「ＢＥＳキュー」という）１４３ｄに加えられる。
【０００７】
【発明が解決しようとする課題】
しかしながら、図１４に示すネットワークノードを用いて品質を予約したとしても、品質を予約したために却って遅延時間やサービス品質が低下するという異常（以下「品質予約異常」という）が生ずる場合がある。
【０００８】
具体的には、図１５（ａ）に示すように、パケット廃棄部１４２がシステム全体としてパケットを廃棄する場合には、予約キュー１４１ａ以外のキュー１４１ｂ〜１４１ｄが混雑すると、レートＡでパケットが到着してもこの予約キュー１４３ａからは予約レートＲでしかパケットを出力できないため、結果的にこの予約キュー１４３ａに滞留するパケットが（Ａ−Ｒ）のレートで増加する。
【０００９】
そして、かかる予約キュー１４３ａに滞留するパケットが増加すると、その後にトラフィックのレートが低下したとしても、他のキュー１４３ｂ〜１４３ｄが混雑している間は、この予約キュー１４３ａのキュー長が短くはならないので、品質を予約したために却って遅延時間が大きくなるという品質予約異常が生ずることとなる。
【００１０】
また、図１５（ｂ）に示すように、キューごとに設けたキュー長制限に基づいてパケット廃棄部１４２がパケットをキューごとに廃棄する場合には、このキュー長制限をレートＲで除算した時間内に遅延時間を抑制できる反面、入出力レートの差分（Ａ−Ｒ）に相当する分のパケットが予約キュー１４３ａの入り口で廃棄される。すなわち、かかる場合には、品質を予約したために却って廃棄されるパケット量が増大し、結果的にサービス品質が低下するという品質予約異常が生ずることとなる。
【００１１】
さらに、図１５（ｃ）に示すように、予約時にトークンバケットにより示されるトラフィックの条件（Tspec ）を示し、到着するパケットがその条件を満たすか否かの条件チェック（以下「コンフォーマンスチェック」という）をおこない、条件を満たすコンフォーマントなパケットについては予約キュー１４３ａに投入し、条件を満たさないノンコンフォーマントなパケットについてはＢＥＳのＲＥＤ（Random Early Detection）にかけ、廃棄されないパケットを予約キュー１４３ａに投入することもできる。
【００１２】
しかしながら、この技術を用いたとしても、予約キュー１４３ａ中にノンコンフォーマントなパケットが溜まりすぎる場合があり得るので、品質を予約したために却って遅延時間が大きくなるという品質予約異常を回避することはできない。
【００１３】
具体的には、アプリケーションがトラフィック特性（Tspec ）を指定し、かつ、このアプリケーションがTspec に準拠する場合には、アプリケーションが適切なTspec を指定し、送信を正しく制御しさえしていれば、ノンコンフォーマントなパケットは発生しない。しかしながら、アプリケーションが制御できる時間精度は１０ｍｓ程度であることが多く、この場合には細かな誤差が避けられないため、一部のパケットがノンコンフォーマントになる。
【００１４】
また、アプリケーションがトラフィック特性（Tspec ）を指定するが、このアプリケーションが故意にTspec に準拠しないで出力する場合には、故意またはバグのいずれにしても、Tspec 以上に送信することとなるため、定常的にノンコンフォーマントなパケットが発生する。
【００１５】
さらに、アプリケーションがトラフィック特性（Tspec ）を指定するが、このアプリケーションがトラフィック特性を制御できない場合には、たとえばＯＳ内のＴＣＰ処理モジュールが予約値以上のパケットを勝手に送出してしまい、かなりの割合でノンコンフォーマントなパケットが発生する。
【００１６】
また、アプリケーションがトラフィック特性（Tspec ）を指定しない場合には、そのバンド幅を利用する多数のアプリケーションが同時かつ独立に動作し、それぞれのアプリケーションが予約バンド幅を意識せずに動作するため、ノンコンフォーマントなパケットが頻繁に発生する。
【００１７】
これらのことから、品質を予約したために却って遅延時間やサービス品質が低下する品質予約異常をいかに効率良く解決するかが極めて重要な課題となっている。
【００１８】
本発明は、上記に鑑みてなされたもので、品質を予約したために却って遅延時間やサービス品質が低下する品質予約異常に効率良く対処することができるパケット処理装置およびパケット処理方法を提供することを目的とする。
【００１９】
【課題を解決するための手段】
上記目的を達成するために、請求項１にかかるパケット処理装置は、入力パケットを分類する分類手段と、この分類手段によって分類されたパケットをそれぞれ蓄積する複数のキューと、該複数のキューに蓄積されたパケットの中からいずれかのパケットを選択して出力するスケジューラとを有するパケット処理装置において、前記分類手段により分類されたパケットを第１のキューに挿入する際に、このパケットに対応する疑似パケットを作成して第２のキューに挿入する疑似パケット入力手段（後述する実施の形態のパケット廃棄部２３ｂがおこなう処理に相当）と、前記疑似パケット入力手段により第２のキューに挿入された疑似パケットが前記スケジューラの処理対象とされた際に、当該疑似パケットに代えて前記第１のキューのパケットを第２のキューからの出力として処理する処理手段（後述する実施の形態のスケジューラ２３ｆがおこなう処理に相当）とを備えたことを特徴とする。
【００２０】
この請求項１にかかる発明では、分類されたパケットを第１のキューに挿入する際に、このパケットに対応する疑似パケットを作成して第２のキューに挿入し、この第２のキューに挿入した疑似パケットがスケジューラの処理対象とされた際に、当該疑似パケットに代えて第１のキューのパケットを第２のキューからの出力として処理することとしたので、少なくとも第２のキューの品質を第１のキューの品質として確保ことができる。
【００２１】
また、請求項２にかかるパケット処理装置は、前記疑似パケット入力手段は、前記第１のキューに挿入するパケットと該パケットに対応する前記第２のキューに挿入する疑似パケットとを相互に関連づけることを特徴とする。
【００２２】
この請求項２にかかる発明では、第１のキューに挿入するパケットと該パケットに対応する第２のキューに挿入する疑似パケットとを相互に関連づけることとしたので、パケットまたは疑似パケットのいずれかがスケジューリング対象とされた際に、他のキューに所在する当該パケットまたは疑似パケットに関連する疑似パケットまたはパケットを容易に特定することができる。
【００２３】
また、請求項３にかかるパケット処理装置は、前記処理手段は、前記疑似パケットが該疑似パケットに対応する前記第１のキューに挿入されたパケットよりも先にスケジューラの処理対象とされた場合には、当該疑似パケットに対応する前記第１のキューのパケットを第２のキューからの出力として処理し（後述する図７のステップＳ２０８〜Ｓ２１２に相当）、前記疑似パケットよりも該疑似パケットに対応する前記第１のキューに挿入されたパケットの方が先にスケジューラの処理対象とされた場合には、当該パケットを処理するとともに前記疑似パケットを無効化する（後述する図７のステップＳ２０２〜Ｓ２０７に相当）ことを特徴とする。
【００２４】
この請求項３にかかる発明では、疑似パケットが先にスケジューラの処理対象とされた場合には、この疑似パケットに対応する第１のキューのパケットを第２のキューからの出力として処理するので、少なくとも第２のキューの品質を第１のキューで保証できる。また、第１のキューに挿入されたパケットの方が先にスケジューラの処理対象とされた場合には、当該パケットを処理するとともに疑似パケットを無効化するので、不要な疑似パケットを処分することができる。
【００２５】
また、請求項４にかかるパケット処理装置は、前記第１のキューに挿入するパケットは、該パケットが実パケットであることを示す識別情報と、該疑似パケットへのリンク情報とを有し（後述する図４に示すパケットの構造に相当）、前記第２のキューに挿入する疑似パケットは、疑似パケットであることを示す識別情報と、該疑似パケットに対応する実パケットへのリンク情報とを有する（後述する図４に示すバブルの構造に相当）ことを特徴とする。
【００２６】
この請求項４にかかる発明では、第１のキューに挿入するパケットに、該パケットが実パケットであることを示す識別情報と、該疑似パケットへのリンク情報とを付加することとしたので、このパケットが先にスケジューリング対象とされた場合に対応する疑似パケットの廃棄を容易におこなうことができる。また、第２のキューに挿入する疑似パケットは、疑似パケットであることを示す識別情報と、該疑似パケットに対応するパケットへのリンク情報とを付加することとしたので、疑似パケットが先にスケジューリング対象とされた場合に、この疑似パケットに対応するパケットを迅速に取り出すことができる。
【００２７】
また、請求項５にかかるパケット処理装置は、前記疑似パケット入力手段は、前記第２のキューに挿入する疑似パケットと前記第１のキューとを関連づけることを特徴とする。
【００２８】
この請求項５にかかる発明では、パケットと該パケットに対応する疑似パケットとを関連づけるのではなく、疑似パケットと第１のキューとを関連づけることとしたので、パケットと疑似パケットの関連づけにかかわる処理負担を軽減することができる。
【００２９】
また、請求項６にかかるパケット処理装置は、前記処理手段は、前記疑似パケットがスケジューラの処理対象とされた場合に、前記第１のキューにパケットが存在すれば、その先頭のパケットを第２のキューからの出力として処理し（後述する図１３のステップＳ４０９〜Ｓ４１３に相当）、前記第１のキューにパケットが存在しない場合は、前記疑似パケットを廃棄し、その際第２のキューに次のパケットが存在すればそのパケットを処理対象とし、第２のキューに次のパケットが存在しなければ、スケジューリングをやり直すことを特徴とする。
【００３０】
この請求項６にかかる発明では、第１のキューに挿入されたパケットの方が先にスケジューラの処理対象とされた場合には、疑似パケットを無視して当該パケットの処理のみをおこなうこととしたので、疑似パケットにかかわる処理を軽減することができる。
【００３１】
また、請求項７にかかるパケット処理装置は、前記第２のキューに挿入する疑似パケットは、疑似パケットであることを示す識別情報と、前記第１のキューへのリンク情報とを有する（後述する図１０に示すバブルの構造に相当）ことを特徴とする。
【００３２】
この請求項７にかかる発明では、第２のキューに挿入する疑似パケットには、対応する第１のキューのパケットへのポインタではなく第１のキューへのリンク情報を付加し、また第１のキューに挿入するパケットには疑似パケットへのポインタを付加しないので、パケットと疑似パケットのリンクにかかわる処理負担を軽減することができる。
【００３３】
また、請求項８にかかるパケット処理装置は、前記複数のキューは、出力バンド幅を予約した複数の予約キューおよびベストエフォートキューからなり、前記第１のキューは前記複数の予約キューのいずれかに対応し、前記第２のキューは前記ベストエフォートキューに対応することを特徴とする。
【００３４】
この請求項８にかかる発明では、疑似パケットをベストエフォートキューに挿入することとしたので、各予約キューの品質として少なくともベストエフォートキューの品質を確保することができる。
【００３５】
また、請求項９にかかるパケット処理方法は、入力パケットを分類し、分類したパケットをそれぞれ複数のキューに蓄積し、該複数のキューに蓄積されたパケットの中からいずれかのパケットをスケジューラによって選択して出力するパケット処理方法において、前記分類したパケットを第１のキューに挿入する際に、このパケットに対応する疑似パケットを作成して第２のキューに挿入する疑似パケット入力工程（後述する図５および図６に示すステップＳ１０１〜Ｓ１１４に相当）と、前記疑似パケット入力工程において第２のキューに挿入された疑似パケットが前記スケジューラの処理対象とされた際に、当該疑似パケットに代えて前記第１のキューのパケットを第２のキューからの出力として処理する処理工程（後述する図７に示すステップＳ２０１〜Ｓ２１２に相当）とを含んだことを特徴とする。
【００３６】
この請求項９にかかる発明では、分類されたパケットを第１のキューに挿入する際に、このパケットに対応する疑似パケットを作成して第２のキューに挿入し、この第２のキューに挿入した疑似パケットがスケジューラの処理対象とされた際に、当該疑似パケットに代えて第１のキューのパケットを第２のキューからの出力として処理することとしたので、少なくとも第２のキューの品質を第１のキューの品質として確保ことができる。
【００３７】
また、請求項１０にかかるパケット処理方法は、前記疑似パケット入力工程は、前記第１のキューに挿入するパケットと該パケットに対応する前記第２のキューに挿入する疑似パケットとを相互に関連づけることを特徴とする。
【００３８】
この請求項１０にかかる発明では、第１のキューに挿入するパケットと該パケットに対応する第２のキューに挿入する疑似パケットとを相互に関連づけることとしたので、パケットまたは疑似パケットのいずれかがスケジューリング対象とされた際に、他のキューに所在する当該パケットまたは疑似パケットに関連する疑似パケットまたはパケットを容易に特定することができる。
【００３９】
また、請求項１１にかかるパケット処理方法は、前記処理工程は、前記疑似パケットが該疑似パケットに対応する前記第１のキューに挿入されたパケットよりも先にスケジューラの処理対象とされた場合には、当該疑似パケットに対応する前記第１のキューのパケットを第２のキューからの出力として処理（後述する図７のステップＳ２０８〜Ｓ２１２に相当）し、前記疑似パケットよりも該疑似パケットに対応する前記第１のキューに挿入されたパケットの方が先にスケジューラの処理対象とされた場合には、当該パケットを処理するとともに前記疑似パケットを無効化する（後述する図７のステップＳ２０２〜Ｓ２０７に相当）ことを特徴とする。
【００４０】
この請求項１１にかかる発明では、疑似パケットが先にスケジューラの処理対象とされた場合には、この疑似パケットに対応する第１のキューのパケットを第２のキューからの出力として処理するので、少なくとも第２のキューの品質を第１のキューで保証できる。また、第１のキューに挿入されたパケットの方が先にスケジューラの処理対象とされた場合には、当該パケットを処理するとともに疑似パケットを無効化するので、不要な疑似パケットを処分することができる。
【００４１】
また、請求項１２にかかるパケット処理方法は、前記疑似パケット入力工程は、前記第２のキューに挿入する疑似パケットと前記第１のキューとを関連づけることを特徴とする。
【００４２】
この請求項１２にかかる発明では、パケットと該パケットに対応する疑似パケットとを関連づけるのではなく、疑似パケットと第１のキューとを関連づけることとしたので、パケットと疑似パケットの関連づけにかかわる処理負担を軽減することができる。
【００４３】
また、請求項１３にかかるパケット処理方法は、前記処理手段は、前記疑似パケットがスケジューラの処理対象とされた場合に、前記第１のキューにパケットが存在すれば、その先頭のパケットを第２のキューからの出力として処理し（後述する図１３のステップＳ４０９〜Ｓ４１３に相当）、前記第１のキューにパケットが存在しない場合は、前記疑似パケットを廃棄し、その際第２のキューに次のパケットが存在すればそのパケットを処理対象とし、第２のキューに次のパケットが存在しなければ、スケジューリングをやり直すことを特徴とする。
【００４４】
この請求項１３にかかる発明では、第１のキューに挿入されたパケットの方が先にスケジューラの処理対象とされた場合には、疑似パケットを無視して当該パケットの処理のみをおこなうこととしたので、疑似パケットにかかわる処理を軽減することができる。
【００４５】
また、請求項１４にかかるパケット処理方法は、前記複数のキューは、出力バンド幅を予約した複数の予約キューおよびベストエフォートキューからなり、前記第１のキューは前記複数の予約キューのいずれかに対応し、前記第２のキューは前記ベストエフォートキューに対応することを特徴とする。
【００４６】
この請求項１４にかかる発明では、疑似パケットをベストエフォートキューに挿入することとしたので、各予約キューの品質として少なくともベストエフォートキューの品質を確保ことができる。
【００４７】
【発明の実施の形態】
以下に添付図面を参照して、この発明にかかるパケット処理装置およびパケット処理方法の好適な実施の形態を詳細に説明する。なお以下では、本発明をルータの出力インターフェース部に適用した場合を示すこととする。
【００４８】
（実施の形態１）
図２は、この実施の形態１で用いるルータおよび出力インターフェース部の構成を示す機能ブロック図である。図２（ａ）に示すルータ２０は、ＯＳＩ（Open System Interconnection ）基本参照モデルのネットワーク層プロトコルに相当するＩＰに基づいてＩＰパケットの中継をおこなうＩＰパケット中継装置であり、複数の入力インターフェース部２１と、ルーティング処理部２２と、複数の出力インターフェース部２３とからなる。
【００４９】
入力インターフェース部２１は、ルータ２０の外部から到来するパケットを受け付けてルーティング処理部２２に出力する処理部であり、ルーティング処理部２２は、入力インターフェース部２１から受け付けたパケットのヘッダに基づいて、このパケットをいずれかの出力インターフェース部２３に出力する処理部である。
【００５０】
出力インターフェース部２３は、本発明にかかわるパケット処理装置およびパケット処理方法を内在し、パケットの廃棄、キューイングおよび品質保証をおこなう処理部である。具体的には、予約キューにパケットを投入する際にこのパケットの疑似パケット（以下「バブル」という）を作成し、作成したバブルをＢＥＳキューに投入して、予約キューの品質がＢＥＳキューよりも低下しないことを保証するキューイング技術（以下「完全バブルキューイング」という）を採用する。
【００５１】
かかる完全バブルキューイングを採用した理由は、品質を予約したために却って遅延時間やサービス品質が低下する品質予約異常を解消し、予約キューにおいて少なくともＢＥＳキューの品質を保証するためである。
【００５２】
図２（ｂ）に示すように、この出力インターフェース部２３は、クラシファイア２３ａと、パケット廃棄部２３ｂと、出力キュー２３ｃと、リシェーパ２３ｄと、リミッタ２３ｅと、スケジューラ２３ｆとからなる。クラシファイア２３ａは、ルーティング処理部２２から受け付けた各パケットをフィルタリングして予約キューのストリームごとに分類し、パケット廃棄部２３ｂに出力する処理部である。
【００５３】
パケット廃棄部２３ｂは、クラシファイア２３ａから受け付けるパケット群のうち一定の条件に当てはまる一部のパケットを廃棄する処理部分である。この条件には、対応するキューにパケットを投入すると該キューの最大キュー長を越えてしまう場合や、輻輳回避のためのＲＥＤにより確率的に廃棄すべきと判断される場合を含む。具体的には、このパケット廃棄部２３ｂでは、ＢＥＳキューのストリームについてはＢＥＳのＲＥＤをおこない、また予約キューのストリームについてはコンフォーマンスチェックをおこなってノンコンフォーマントなパケットにＢＥＳのＲＥＤをおこなう。
【００５４】
なお、このＲＥＤ（Random Early Detection）１２とは、ＲＥＤの対象とするキューの平均キュー長をパラメータとして、前記キューに入るパケットの廃棄確率を変更するパケット廃棄方式で、その内容はＩＥＴＦ（Internet Engineering
Task Force ）のＲＦＣ２３０９に示されている。
【００５５】
出力キュー２３ｃは、複数の予約キューとＢＥＳキューとからなり、先入れ先出し方式で複数のパケットからなるストリームを保持する。リシェーパ２３ｄおよびリミッタ２３ｅは、ストリームの出力トラフィックをあらかじめ定められた形に整形するレギュレータを形成し、このリミッタ２３ｅでは、ストリームの出力トラフィックのピークレート制御をおこない、リシェーパ２３ｄは、その他の整形をおこなう。
【００５６】
スケジューラ２３ｆは、ストリーム単位でパケットのスケジューリングをおこなう処理部である。このスケジューラ２３ｆは、バンド幅保証、遅延保証および平等性（Fairness）を判断基準としてパケットのスケジューリングをおこなう。
【００５７】
つぎに、図２に示す出力インターフェース部２３がおこなう完全バブルキューイングの処理概念について説明する。なお、この完全バブルキューイングは、主として図２に示すパケット廃棄部２３ｂ、出力キュー２３ｃおよびスケジューラ２３ｆにかかわる処理である。
【００５８】
図１は、図２に示す出力インターフェース部２３がおこなう完全バブルキューイングの処理概念を示す図である。同図に示すように、この完全バブルキューイングでは、予約キュー１３に投入される実パケットのバブルをＢＥＳキュー１４に投入し、このＢＥＳキュー１４に投入したバブルを予約キュー１３に投入した実パケットとを対応づけることにより、予約キュー１３において少なくともＢＥＳキュー１４の品質を保証し、品質を予約したために却って遅延時間やサービス品質が低下する品質予約異常を解消している。
【００５９】
具体的には、ＢＥＳキュー１４のストリームは、従来と同様にＢＥＳのＲＥＤ１２によって廃棄すべきか否かが判断され、廃棄しないパケットのみがＢＥＳキュー１４に投入される。
【００６０】
これに対して、予約キュー１３のストリームは、予約時にトークンバケットにより示されるトラフィックの条件（Tspec ）を満たすか否かを判定するコンフォーマンスチェック１１をおこない、条件を満たすコンフォーマントなパケットを予約キュー１３に投入するとともに、このパケットに対応するマーカとしてのバブルをＢＥＳキュー１４に投入する。
【００６１】
また、このコンフォーマンスチェック１１の結果がノンコンフォーマントであるパケットについては、これをＢＥＳのＲＥＤ１２にかけてその一部を廃棄し、廃棄されないパケットを予約キュー１３に投入しつつ、このパケットのバブルをＢＥＳキュー１４に投入する。
【００６２】
なお、かかる予約キュー１３に投入したパケットとＢＥＳキュー１４に投入したバブルとはそれぞれ対応づけられており、スケジューラ２３ｆでは、複数のキューの中からつぎに出力するパケットを持つキューを選択する際に、このバブルについても通常のパケットと同様にスケジューリングの対象とする。
【００６３】
このように、かかる完全バブルキューイングでは、パケットをＢＥＳ扱いとした際にスケジューリングされる時期をバブルを用いて特定し、このパケットをＢＥＳ扱いした方が遅延時間が短くなって結果的に品質が向上する場合には、バブルがスケジューリングされる時期に該バブルに対応するパケットをスケジューリングする。
【００６４】
図３は、図１に示す予約キュー１３内の実パケットとＢＥＳキュー１４内のバブルとの対応関係を示す図である。同図（ａ）に示すように、スケジューラ２３ｆによって予約キュー１３内の実パケットの方が、ＢＥＳキュー１４内の対応するバブルのよりも早くスケジューリングされた場合には、通常通り予約キュー１３から実パケットを出力するとともに、ＢＥＳキュー１４中の当該実パケットに対応するバブルを廃棄するなどして無効化する。
【００６５】
これに対して、同図（ｂ）に示すように、スケジューラ２３ｆによって予約キュー１３内の実パケットよりも、ＢＥＳキュー１４内の対応するバブルの方が早くスケジューリングされた場合には、その時点で当該バブルに対応する実パケットを予約キュー１３から取り出し、この実パケットをバブルに代えてＢＥＳキュー１４から出力する。なお、この完全バブルキューイングの場合には、ＢＥＳキュー１４のバブルが先頭にきたときに、対応する実パケットが必ず予約キュー１３の先頭に位置することになる。
【００６６】
具体的には、かかる場合にはこの実パケットがＢＥＳキュー１４に割り当てられたバンド幅を消費するように出力される。ここで、一般のスケジューラは、パケットが到着した際に当該パケットに時刻タグを付け、その後この時刻タグに基づいて全パケットをソートするよう処理されることが多いが、全パケットをソートしなくともパケットの存在するキューでソートすることにより、同様の結果が得られる。
【００６７】
このため、このスケジューラ２３ｆでは、パケットではなくキュー自体に時刻タグを付け、パケットの到達時ではなく各キューの先頭のパケットが新しくなったときに時刻タグを計算することとし、実パケットをＢＥＳキュー１４から出力する場合には、このパケットが使用したバンド幅をＢＥＳキュー１４の時刻タグに反映させることとしている。なお、かかる処理をおこなう理由は、パケットに時刻タグを付与したのでは、実パケットをＢＥＳキュー１４から出力する際の処理が複雑化するためである。
【００６８】
つぎに、図１に示す予約キュー１３、ＢＥＳキュー１４、実パケットおよびバブルについてさらに具体的に説明する。図４は、図１に示す予約キュー１３内の実パケットおよびＢＥＳキュー１４内のバブルの具体的なデータ構造の一例を示す図である。
【００６９】
同図に示すように、ここでは複数の実パケットを双方向のリンクドリストで連結して予約キュー１３を形成するとともに、実パケットおよびバブルを双方向のリンクドリストで連結してＢＥＳキュー１４を形成している。
【００７０】
具体的には、実パケットは、次パケットへのポインタを格納する“ｎｅｘｔ”と、前パケットへのポインタを格納する“ｐｒｅｖ”と、実パケットまたはバブルのいずれであるかを示す“ｆｌａｇ”と、バブルへのポインタを格納する“ｂｕｂｂｌｅ”と、実パケットのサイズを格納する“パケットサイズ”と、実パケットの内容を格納する“パケット本体”とからなる。
【００７１】
また、バブルは、次パケットへのポインタを格納する“ｎｅｘｔ”と、前パケットへのポインタを格納する“ｐｒｅｖ”と、実パケットまたはバブルのいずれであるかを示す“ｆｌａｇ”と、実パケットへのポインタを格納する“ｒｅａｌ”とからなり、“パケットサイズ”および“パケット本体”は有しない。
【００７２】
なお、このパケットが実パケットである場合には“ｆｌａｇ＝０”となり、バブルである場合には“ｆｌａｇ＝１”となる。また、ＢＥＳキュー１４内に保持される実パケットについては、バブルへのポインタを格納しない。
【００７３】
そして、予約キュー１３では、“ｎｅｘｔ”および“ｐｒｅｖ”を用いてヘッド（ｈｅａｄ）のパケットからテール（ｔａｉｌ）のパケットに至る双方向のリンクが張られるとともに、各実パケットからＢＥＳキュー１４内の対応するバブルへリンクが張られる。
【００７４】
これに対して、ＢＥＳキュー１４では、“ｎｅｘｔ”および“ｐｒｅｖ”を用いてヘッド（ｈｅａｄ）のパケットからテール（ｔａｉｌ）のパケットに至る双方向のリンクが張られるとともに、各バブルから予約キュー１３内の対応する実パケットへリンクが張られる。
【００７５】
このように、ここでは、実パケットを双方向のリンクドリストで連結することにより予約キュー１３を形成し、実パケットおよびバブルを双方向のリンクドリストで連結してＢＥＳキュー１４を形成するとともに、実パケットおよびバブルの間をポインタで相互に対応づけることとしている。
【００７６】
つぎに、図１に示す完全バブルキューイングによるパケットキューイング時の処理手順について説明する。図５および図６は、図１に示す完全バブルキューイングによるパケットキューイング時の処理手順を示すフローチャートである。
【００７７】
図５および図６に示すように、この完全バブルキューイングでは、まず最初にストリームが瞬間最大キュー長の制限を越えているか否かが調べられ（ステップＳ１０１）、瞬間最大キュー長の制限を越えている場合には（ステップＳ１０１否定）、パケットが廃棄される。
【００７８】
一方、瞬間最大キュー長の制限を越えていない場合には（ステップＳ１０１肯定）、予約ストリームであるか否かが調べられ（ステップＳ１０２）、予約ストリームでない場合には（ステップＳ１０２否定）、ＢＥＳのＲＥＤを実行し（ステップＳ１１０）、当該パケットが廃棄すべきものである場合には（ステップＳ１１０肯定）そのままパケットを廃棄し、当該パケットが廃棄すべきものでない場合には（ステップＳ１１０否定）、このパケットをＢＥＳキュー１４に挿入する（ステップＳ１１１）。
【００７９】
これに対し、ステップＳ１０２において予約ストリームであると判断された場合には（ステップＳ１０２肯定）、予約条件のチェックがあるか否かを判断し（ステップＳ１０３）、予約条件のチェックがなく（ステップＳ１０３否定）、このストリームのＲＥＤがオンである場合には（ステップＳ１０４肯定）、全パケット群に対してＲＥＤを実行し（ステップＳ１０５）、廃棄対象となるパケットを廃棄する。
【００８０】
また、ステップＳ１０４においてストリームのＲＥＤがオンでない場合や（ステップＳ１０４否定）、ストリームのＲＥＤがオンであるが当該ＲＥＤを実行してもパケットが廃棄対象とはならない場合には（ステップＳ１０５否定）、実パケットに対応するバブルを作成して、作成したバブルをＢＥＳキュー１４に挿入し（ステップＳ１１３）、実パケットを当該ストリームの予約キュー１３に挿入する（ステップＳ１１４）。
【００８１】
なお、このバブルには、バブルであることを示す識別情報“ｆｌａｇ＝１”と、実パケットへのポインタを示す“ｒｅａｌ”とを付加する。また、実パケットには、バブルでないことを示す識別情報“ｆｌａｇ＝０”と、バブルへのポインタを示す“ｂｕｂｂｌｅ”とを付加する。
【００８２】
また、ステップＳ１０３において予約条件のチェックすなわちコンフォーマンスチェックがなされ（ステップＳ１０３肯定）、この予約条件が満たされているコンフォーマントな場合には（ステップＳ１０６肯定）、ステップＳ１１３に移行する。
【００８３】
これに対して、予約条件が満たされていないノンコンフォーマントな場合には（ステップＳ１０６否定）、ストリームのＲＥＤがオンであるか否かを調べ（ステップＳ１０７）、このＲＥＤがオンでなければ（ステップＳ１０７否定）、ＢＥＳのＲＥＤを実行する（ステップＳ１１２）。そして、このパケットが廃棄対象となる場合には（ステップＳ１１２肯定）当該パケットを廃棄し、廃棄対象にならない場合には（ステップＳ１１２否定）、ステップＳ１１３に移行する。
【００８４】
また、ＲＥＤがオンであれば、この予約キュー１３について違反パケット群に対するＲＥＤを実行し（ステップＳ１０８）、パケットが廃棄対象となる場合には（ステップＳ１０８肯定）このパケットを廃棄し、廃棄対象とならない場合には（ステップＳ１０８否定）、違反パケットであることを示す情報をパケットに付加した後に（ステップＳ１０９）、ステップ１１３に移行する。
【００８５】
上記一連の処理をおこなうことにより、実パケットを予約キュー１３に挿入するとともに、当該実パケットに対応するバブルを作成してＢＥＳキュー１４に挿入することができる。
【００８６】
つぎに、図１に示す完全バブルキューイングによるパケットの出力時の処理手順について説明する。図７は、図１に示す完全バブルキューイングによるパケットの出力時の処理手順を示すフローチャートである。完全バブルキューイングにおいては、いずれかのキューにパケットが存在するようになるまで待ち、スケジューラが出力処理対象となるキューを選択したならば、下記に示す処理をおこなう。
【００８７】
図７に示すように、まず最初に先頭パケットがバブルであるか否かを調べ（ステップＳ２０１）、このパケットがバブルでない場合には（ステップＳ２０１否定）、レギュレータがあるか否かを確認し（ステップＳ２０２）、レギュレータの制限を満たさない場合には（ステップＳ２０３否定）ウエイト処理へ移行する。
【００８８】
また、レギュレータがない場合や（ステップＳ２０２否定）、レギュレータがあるが制限を満たす場合には（ステップＳ２０３肯定）、当該キューのＲＥＤ用瞬間キュー長を減算し（ステップＳ２０５４、当該キューからパケットを取り出す（ステップＳ２０５）。なお、ステップＳ２０４において、予約キュー１３の場合には、違反マーク付きのパケットについてのみおこなう。
【００８９】
その後、このパケットに対応するバブルが存在するか否かを確認し（ステップＳ２０６）、対応するバブルが存在する場合には（ステップＳ２０６肯定）、このバブルをバブルが入っているＢＥＳキュー１４から取り出して廃棄する（ステップＳ２０７）。
【００９０】
これに対し、上記ステップＳ２０１において、パケットがバブルである場合には（ステップＳ２０１肯定）、レギュレータがあるか否かを確認し（ステップＳ２０８）、レギュレータの制限を満たさない場合には（ステップＳ２０９否定）ウエイト処理へ移行する。なお、ここではウエイト処理についての説明は省略する。
【００９１】
また、レギュレータがない場合や（ステップＳ２０８否定）、レギュレータがあるが制限を満たす場合には（ステップＳ２０９肯定）、ＢＥＳキュー１４のＲＥＤ用瞬間キュー長を減算し（ステップＳ２１０）、バブルをＢＥＳキュー１４から取り出して解放した後に（ステップＳ２１１）、予約キュー１３から当該バブルに対応する実パケットを取り出す（ステップＳ２１２）。
【００９２】
上記一連の処理をおこなうことにより、少なくともＢＥＳキュー１４と同程度の品質を予約キュー１３に保証して、品質を予約したために却って遅延時間やサービス品質が低下する品質予約異常を解消することができる。
【００９３】
上述してきたように、本実施の形態１にかかわる完全バブルキューイングでは、予約キュー１３に実パケットを挿入する際に、この実パケットに対応するバブルを作成してＢＥＳキュー１４に投入し、実パケットよりもバブルの方が先にスケジューリングされる場合には、この実パケットをバブルの代わりにＢＥＳキュー１４から出力するよう構成したので、少なくともＢＥＳキュー１４と同程度の品質を予約キュー１３に保証して、品質を予約したために却って遅延時間やサービス品質が低下する品質予約異常を解消することができる。
【００９４】
たとえば、ある予約ストリームについて、“Ｒ”のバンド幅を割り当て、実際には“Ｒ”よりも大きい“Ｓ”のバンド幅のトラフィックを流した場合に、予約範囲の“Ｒ”分のトラフィックについてはパケットを廃棄せずに予約ストリームの予約バンド幅を利用して出力し、予約範囲をオーバーした“Ｓ−Ｒ”分のトラフィックについては、あたかもＢＥＳストリームのパケットであるかのようにＢＥＳと同じ方法でパケット廃棄をおこない、廃棄されなかったパケットについてＢＥＳストリームに割り当てられたバンド幅を利用して出力する。このため結果的に、従来のバンド幅保証スケジューラと同様に“Ｒ”のバンド幅が保証されるとともに、予約しなかった場合のバンド幅も保証される。
【００９５】
もし仮に、上記の“Ｓ−Ｒ”分のパケットを単純にＢＥＳキュー１４に投入するような方法をとったとすると、それらのパケットと、予約キュー１３のパケットの順序関係が保たれず、受信側とは異なった順序でパケットを出力することになり、アプリケーションの動作に障害をきたしたり、通信の実行性能を低下させるなどの問題が生じる。バブルキューイング方式により、予約ストリームのパケットをＢＥＳストリームのバンド幅を利用して出力する場合は、予約キュー１３内の実パケットは受信順を保って管理され、その順序で出力されるため、予約ストリームのパケット順序が変動しない。したがって、パケット順の変動により、アプリケーションや通信の性能を低下させることがない。
【００９６】
なお、この完全バブルキューイングの実行コストを検討すると、ここでは予約キュー１３に投入するすべてのパケットに対応するバブルを作成し、このバブルをＢＥＳキュー１４に投入して実パケットとの対応関係を保持することとしたため、バブルにかかわる情報を記憶するメモリ容量が必要となる。
【００９７】
しかしながら、バブルにかかわる情報は、すでに説明したようにＢＥＳキュー１４内でのリンク、バブルであることを示すフラグおよび実パケットへのポインタのみであるから、これらの情報は２ワード程度に納めることができ、大きな問題とはならない。
【００９８】
また、かかる完全バブルキューイングを採用する場合には、バブルをＢＥＳキュー１４に投入したり、バブルであるか否かを判断したり、バブルと実パケットとの対応づけをおこなうＣＰＵコストが必要となるが、かかるＣＰＵ負担はバンド幅保証をおこなうコストと比較すると極めて小さいため、大きな問題とはならない。
【００９９】
（実施の形態２）
ところで、上記実施の形態１が採用する完全バブルキューイングでは、メモリ容量およびＣＰＵコストが特に問題にならないと考えたが、ハードウエア化を図る場合には、ＣＰＵの処理負担をできるだけ低減することが望ましい。このため、本実施の形態２では、パケットとバブルとを一対一で対応づける処理負担を軽減する技術（以下「部分バブルキューイング」という）について説明する。なお、この場合のルータおよび出力インターフェース部の構成は図２に示すものと同様のものになるので、ここではその説明を省略する。
【０１００】
図８は、実施の形態２にかかわる部分バブルキューイングの処理概念を示す図である。同図に示すように、この部分バブルキューイングでは、予約ストリームのうちノンコンフォーマントなパケットのみについてバブルを作成することとしたので、予約ストリームのすべてのパケットがコンフォーマントであるならば、バブルが発生しないために処理負担が軽減する。
【０１０１】
しかしながら、ノンコンフォーマントなパケットについてのみバブルを作成することとすると、完全バブルキューイングの場合と異なり、バブルがＢＥＳキュー１４の先頭にきたときに当該バブルに対応する実パケットが予約キュー１３の先頭にあるとは限らなくなる。
【０１０２】
このため、バブルに対応する実パケットを予約キュー１３から抜き出して送信したのでは、予約ストリーム中のパケットの順序が変動してしまうという問題がある。また、このバブルに対応する実パケットまでのすべてのパケットを連続送信することとすると、他のストリームに対するバンド幅を保証できなくなるという問題もある。加えて、外部で観察した場合には、ノードでどのパケットをノンコンフォーマントと解釈して出力したかをパケットごとに正確に判別できないという事実もある。
【０１０３】
そこで、この部分バブルキューイングでは、バブルと実パケットとの厳密な対応関係はとらず、バブルから予約キュー１３への対応関係のみを保持して、予約キュー１３中の実パケットのうちＢＥＳキュー１４のバンド幅を利用して予約キュー１３のパケットを出力すべきタイミングだけを管理するよう構成している。
【０１０４】
具体的には、ＢＥＳキュー１４のストリームは、従来と同様にＢＥＳのＲＥＤ１２によって破棄すべきか否かが判断され、破棄しないパケットのみをＢＥＳキュー１４に投入する。
【０１０５】
これに対して、予約キュー１３のストリームについては、コンフォーマンスチェック１１をおこない、条件を満たすコンフォーマントなパケットについてはバブルを作成することなく予約キュー１３に投入する。
【０１０６】
また、このコンフォーマンスチェック１１の結果がノンコンフォーマントであるパケットについては、これをＢＥＳのＲＥＤ１２にかけてその一部を廃棄し、廃棄されないパケットを予約キュー１３に投入しつつ、このパケットのバブルをＢＥＳキュー１４に投入する。
【０１０７】
なお、かかる予約キュー１３に投入したパケットとＢＥＳキュー１４に投入したバブルとは直接の対応関係はとらず、バブルから予約キュー１３への対応関係のみを保持する。
【０１０８】
このように、かかる部分バブルキューイングでは、完全バブルキューイングのように予約キュー１３に投入するすべての実パケットについてバブルを作成するのではなく、ＲＥＤで廃棄されないノンコンフォーマントなパケットについてのみバブルを作成してＢＥＳキュー１４に投入するとともに、バブルから予約キュー１３への対応関係のみを保持することとしている。
【０１０９】
図９は、図８に示す予約キュー１３内の実パケットとＢＥＳキュー１４内のバブルとの対応関係を示す図である。同図（ａ）に示すように、スケジューラ２３ｆによって予約キュー１３内の実パケットの方が、ＢＥＳキュー１４内の対応するバブルよりも早くスケジューリングされた場合には、通常通り予約キュー１３から実パケットを出力する。なお、この実パケットと当該実パケットに対応するＢＥＳキュー１４中のバブルとの対応関係は保持されていないので、ＢＥＳキュー１４中のバブルに関する処理はおこなわない。
【０１１０】
これに対して、同図（ｂ）に示すように、スケジューラ２３ｆによって、ＢＥＳキュー１４内の対応するバブルがスケジューリングされた場合には、その時点でたまたま予約キュー１３の先頭に存在する実パケットをＢＥＳキュー１４のバンド幅を使って出力する。ただし、予約キュー１３にパケットが存在しなければ、当該バブルを廃棄し、ＢＥＳキュー１４の次のパケットの処理をおこなう。また、ＢＥＳキュー１４にパケットがなければ、再スケジューリングする。
【０１１１】
このように、この部分バブルキューイングでは、ＢＥＳキュー１４中のバブル１個について予約キュー１３中の実パケットを最大１個出力して、パケット数の整合性のみを維持することとしている。
【０１１２】
つぎに、図８に示す予約キュー１３、ＢＥＳキュー１４、実パケットおよびバブルについてさらに具体的に説明する。図１０は、図８に示す予約キュー１３内の実パケットおよびＢＥＳキュー１４内のバブルの具体的なデータ構造の一例を示す図である。
【０１１３】
同図に示すように、この部分バブルキューイングにおいても、完全バブルキューイングと同様に、複数の実パケットを双方向のリンクドリストで連結して予約キュー１３を形成するとともに、実パケットおよびバブルを双方向のリンクドリストで連結してＢＥＳキュー１４を形成している。
【０１１４】
しかしながら、この部分バブルキューイングでは、バブルが実パケットへのポインタ“ｒｅａｌ”ではなく、予約キュー１３へのポインタ“ｑｕｅｕｅ”を持ち、また実パケットがバブルへのポインタを格納する“ｂｕｂｂｌｅ”を持たない点で完全バブルキューイングと異なる。
【０１１５】
このように、この部分バブルキューイングでは、予約キュー１３およびＢＥＳキュー１４をリンクドリストで形成する点では完全バブルキューイングと共通するものの、実パケットとバブルとの対応関係をとらない点が異なる。
【０１１６】
つぎに、図８に示す部分バブルキューイングによるパケットキューイング時の処理手順について説明する。図１１および図１２は、図８に示す部分バブルキューイングによるパケットキューイング時の処理手順を示すフローチャートである。
【０１１７】
図１１および図１２に示すように、この部分バブルキューイングでは、まず最初にストリームが瞬間最大キュー長の制限を越えているか否かを調べ（ステップＳ３０１）、瞬間最大キュー長の制限を越えている場合には（ステップＳ３０１否定）、パケットを廃棄する。
【０１１８】
一方、瞬間最大キュー長の制限を越えていない場合には（ステップＳ３０１肯定）、予約ストリームであるか否かを調べ（ステップＳ３０２）、予約ストリームでない場合には（ステップＳ３０２否定）、ＢＥＳのＲＥＤを実行し（ステップＳ３１１）、当該パケットが廃棄対象となる場合には（ステップＳ３１１肯定）そのままパケットを廃棄し、当該パケットが廃棄対象とならない場合には（ステップＳ３１１否定）このパケットをＢＥＳキュー１４に挿入する（ステップＳ３１２）。
【０１１９】
これに対し、上記ステップＳ３０２において予約ストリームであると判断された場合には（ステップＳ３０２肯定）、予約条件のチェックがあるか否かを判断し（ステップＳ３０３）、予約条件のチェックがなく（ステップＳ３０３否定）、このストリームのＲＥＤがオンである場合には（ステップＳ３０４肯定）、全パケット群に対してこのストリームのＲＥＤを実行し（ステップＳ３０５）、廃棄対象となるパケットを廃棄する。
【０１２０】
また、ステップＳ３０４においてストリームのＲＥＤがオンでない場合や（ステップＳ３０４否定）、ストリームのＲＥＤがオンであるが当該ＲＥＤを実行してもパケットが廃棄対象とならない場合には（ステップＳ３０５否定）、このパケットを当該ストリームのキューに挿入する（ステップＳ３１０）。この際、併せて瞬間キュー長の加算についてもおこなわれる。なお、完全バブルキューイングと異なり、この場合には実パケットに対応するバブルは作成されない。
【０１２１】
また、ステップＳ３０３において予約条件のチェックすなわちコンフォーマンスチェックがなされ（ステップＳ３０３肯定）、この予約条件が満たされているコンフォーマントな場合には（ステップＳ３０６肯定）、ステップＳ３１０に移行する。
【０１２２】
これに対して、予約条件が満たされていないノンコンフォーマントな場合には（ステップＳ３０６否定）、ストリームのＲＥＤがオンであるか否かを調べ（ステップＳ３０７）、このＲＥＤがオンでなければ（ステップＳ３０７否定）、ＢＥＳのＲＥＤを実行する（ステップＳ３１３）。
【０１２３】
その結果、パケットが廃棄対象となる場合には（ステップＳ３１３肯定）当該パケットを廃棄し、廃棄対象とならない場合には（ステップＳ３１３否定）、パケットを当該ストリームの予約キュー１３に挿入するとともに（ステップＳ３１４）、ストリーム用のバブルを生成してＢＥＳキュー１４に挿入する（ステップＳ３１５）。
【０１２４】
また、ＲＥＤがオンであれば、違反パケット群に対するＲＥＤを実行し（ステップＳ３０８）、パケットが廃棄対象となる場合には（ステップＳ３０８肯定）このパケットを廃棄し、廃棄対象とならない場合には（ステップＳ３０８否定）、違反パケットであることを示す情報をパケットに付加した後に（ステップＳ３０９）、ステップ３１０に移行する。
【０１２５】
上記一連の処理をおこなうことにより、パケットがノンコンフォーマントであり、かつ、ＢＥＳのＲＥＤで廃棄すべきものでない場合にのみ、バブルを作成してＢＥＳキュー１４に挿入することができる。
【０１２６】
つぎに、図８に示す部分バブルキューイングによるパケットの出力時の処理手順について説明する。図１３は、図８に示す部分バブルキューイングによるパケットの出力時の処理手順を示すフローチャートである。この部分バブルキューイングにおいても、いずれかのキューにパケットが存在するようになるまで待ち、スケジューラが出力処理対象となるキューを選択したならば、下記に示す処理をおこなう。
【０１２７】
図１３に示すように、まず最初に先頭パケットがバブルであるか否かを調べ（ステップＳ４０１）、このパケットがバブルではない場合には（ステップＳ４０１否定）、レギュレータがあるか否かを確認し（ステップＳ４０２）、レギュレータの制限を満たさない場合には（ステップＳ４０３否定）ウエイト処理へ移行する。
【０１２８】
また、レギュレータがない場合や（ステップＳ４０２否定）、レギュレータがあるが制限を満たす場合には（ステップＳ４０３肯定）、当該キューのＲＥＤ用瞬間キュー長を減算し（ステップＳ４０４）、当該キューからパケットを取り出す（ステップＳ４０５）。なお、ステップＳ４０４において、予約キュー１３の場合には、違反マーク付きのパケットについてのみおこなう。
【０１２９】
これに対して、このパケットがバブルである場合には（ステップＳ４０１肯定）、このバブルに対応づけられた予約キュー１３に実パケットがあるか否かを確認し（ステップＳ４０６）、実パケットが存在しない場合には（ステップＳ４０６否定）、ＢＥＳキュー１４のＲＥＤ用瞬間キュー長を減算し（ステップＳ４０７）、バブルをＢＥＳキュー１４から取り出して解放し（ステップＳ４０８）、ステップＳ４０１に移行する。
【０１３０】
また、ステップＳ４０６において、バブルに対応づけられた予約キュー１３に実パケットが存在する場合には（ステップＳ４０６肯定）、レギュレータがあるか否かを確認し（ステップＳ４０９）、レギュレータの制限を満たさない場合には（ステップＳ４１０否定）ウエイト処理へと移行する。
【０１３１】
また、レギュレータがない場合や（ステップＳ４０９否定）、レギュレータがあるが制限を満たす場合には（ステップＳ４１０肯定）、ＢＥＳキュー１４のＲＥＤ用瞬間キュー長を減算し（ステップＳ４１１）、バブルをＢＥＳキュー１４から取り出して解放した後に（ステップＳ４１２）、予約キュー１３から当該バブルに対応する実パケットを取り出す（ステップＳ４１３）。
【０１３２】
上記一連の処理をおこなうことにより、完全バブルキューイングの場合と異なり、ＢＥＳキュー１４中のバブル１個について予約キュー１３中の実パケットを最大１個出力して、パケット数の整合性を維持することができる。
【０１３３】
上述してきたように、本実施の形態２にかかわる部分バブルキューイングでは、完全バブルキューイングと異なり、ＲＥＤで廃棄されないノンコンフォーマントなパケットのみについてバブルを作成するとともに、このバブルと実パケットとの対応関係をとらず、ＢＥＳキュー１４中のバブル１個について予約キュー１３中の実パケットを最大１個出力して、パケット数の整合性を維持するよう構成したので、完全バブルキューイング処理をより単純化し、効率良くハードウエア化することが可能となる。
【０１３４】
なお、本実施の形態では、説明の便宜上予約キュー１３に挿入する実パケットのバブルをＢＥＳキュー１４に挿入する場合を示したが、本発明はこれに限定されるものではなく、かかるバブルを他の予約キュー１３に挿入する場合に適用することもできる。
【０１３５】
また、本実施の形態では、ＢＥＳキューのバブルがスケジューリングの対象となった場合において、対応する予約キューに実パケットが存在する場合には、必ず当該実パケットをＢＥＳキューのバンド幅を使って出力していた。しかし、一般には、対応する予約キューに実パケットが存在しても、ある条件を満たす場合のみバブルの処理を行い、条件を満たさない場合には対応する実パケットがあたかも存在しなかった時のように動作させる（つまり、バブルが無効であるとみなす）ような実施の形態もあり得る。前記条件としては、たとえば、予約キュー内のパケット数が２以上である、という条件などがある。これは、バブル処理時に、予約キューが空になった場合の特殊な処理が必要となる可能性をなくし、バブル処理を簡単化する場合などに有効である。
【０１３６】
【発明の効果】
上記に説明したとおり、請求項１または請求項９にかかる発明では、分類されたパケットを第１のキューに挿入する際に、このパケットに対応する疑似パケットを作成して第２のキューに挿入し、この第２のキューに挿入した疑似パケットがスケジューラの処理対象とされた際に、当該疑似パケットに代えて第１のキューのパケットを第２のキューからの出力として処理するよう構成したので、少なくとも第２のキューの品質を第１のキューの品質として確保もって品質を予約したために却って遅延時間やサービス品質が低下する品質予約異常に効率良く対処できるという効果を奏する。
【０１３７】
また、請求項２または請求項１０にかかる発明では、第１のキューに挿入するパケットと該パケットに対応する第２のキューに挿入する疑似パケットとを相互に関連づけるよう構成したので、パケットまたは疑似パケットのいずれかがスケジューリング対象とされた際に、他のキューに所在する当該パケットまたは疑似パケットに関連する疑似パケットまたはパケットを容易に特定し、もってパケットおよび疑似パケットのスケジューリングを容易にできるという効果を奏する。
【０１３８】
また、請求項３または請求項１１にかかる発明では、疑似パケットが先にスケジューラの処理対象とされた場合には、この疑似パケットに対応する第１のキューのパケットを第２のキューからの出力として処理し、第１のキューに挿入されたパケットの方が先にスケジューラの処理対象とされた場合には、当該パケットを処理するとともに疑似パケットを無効化するよう構成したので、少なくとも第２のキューの品質を第１のキューで保証しつつ、不要な疑似パケットを迅速に処分できるという効果を奏する。
【０１３９】
また、請求項４にかかる発明では、第１のキューに挿入するパケットに、該パケットが実パケットであることを示す識別情報と、該疑似パケットへのリンク情報とを付加するよう構成したので、このパケットが先にスケジューリング対象とされた場合に対応する疑似パケットの廃棄を容易におこなうことができ、また第２のキューに挿入する疑似パケットには、疑似パケットであることを示す識別情報と、該疑似パケットに対応する実パケットへのリンク情報とを付加するよう構成したので、疑似パケットが先にスケジューリング対象とされた場合に、この疑似パケットに対応するパケットを迅速に取り出すことができるという効果を奏する。
【０１４０】
また、請求項５または請求項１２にかかる発明では、パケットと該パケットに対応する疑似パケットとを関連づけるのではなく、疑似パケットと第１のキューとを関連づけることよう構成したので、パケットと疑似パケットの関連づけにかかわる処理負担を軽減し、比較的容易にハードウエア化することができるという効果を奏する。
【０１４１】
また、請求項６または請求項１３にかかる発明では、第１のキューに挿入されたパケットがスケジューラの処理対象とされた場合には、疑似パケットを無視して当該パケットの処理のみをおこなうよう構成したので、疑似パケットにかかわる処理を軽減することができるという効果を奏する。
【０１４２】
また、請求項７にかかる発明では、第２のキューに挿入する疑似パケットには、対応する第１のキューのパケットへのポインタではなく第１のキューへのリンク情報を付加し、また第１のキューに挿入するパケットには疑似パケットへのポインタを付加しないよう構成したので、パケットと疑似パケットのリンクにかかわる処理負担を軽減できるという効果を奏する。
【０１４３】
また、請求項８または請求項１４にかかる発明では、疑似パケットをベストエフォートキューに挿入するよう構成したので、各予約キューの品質として少なくともベストエフォートキューの品質を確保できるという効果を奏する。
【図面の簡単な説明】
【図１】実施の形態１にかかる完全バブルキューイングの処理概念を示す図である。
【図２】実施の形態１にかかるルータおよび出力インターフェース部の構成を示す機能ブロック図である。
【図３】図１に示した予約キュー内の実パケットとＢＥＳキュー内のバブルとの対応関係を示す図である。
【図４】図１に示した予約キュー内の実パケットおよびＢＥＳキュー内のバブルの具体的なデータ構造の一例を示す図である。
【図５】図１に示した完全バブルキューイングによるパケットキューイング時の処理手順を示すフローチャートである。
【図６】図１に示した完全バブルキューイングによるパケットキューイング時の処理手順を示すフローチャートである。
【図７】図１に示した完全バブルキューイングによるパケットの出力時の処理手順を示すフローチャートである。
【図８】実施の形態２にかかる部分バブルキューイングの処理概念を示す図である。
【図９】図８に示した予約キュー内の実パケットとＢＥＳキュー内のバブルとの対応関係を示す図である。
【図１０】図８に示した予約キュー内の実パケットおよびＢＥＳキュー内のバブルの具体的なデータ構造の一例を示す図である。
【図１１】図８に示した部分バブルキューイングによるパケットキューイング時の処理手順を示すフローチャートである。
【図１２】図８に示した部分バブルキューイングによるパケットキューイング時の処理手順を示すフローチャートである。
【図１３】図８に示した部分バブルキューイングによるパケットの出力時の処理手順を示すフローチャートである。
【図１４】従来におけるルータをモデル化した一例を示すブロック図である。
【図１５】従来におけるパケット廃棄技術を説明するための説明図である。
【符号の説明】
１１  コンフォーマンスチェック
１２  ＢＥＳ（ベストエフォート）のＲＥＤ
１３  予約キュー
１４  ＢＥＳキュー
２０  ルータ
２１  入力インターフェース部
２２  ルーティング処理部
２３  出力インターフェース部
２３ａ  クラシファイア
２３ｂ  パケット廃棄部
２３ｃ  出力キュー
２３ｄ  リシェーパ
２３ｅ  リミッタ
２３ｆ  スケジューラ
１４０  ルーティング処理部
１４１  クラシファイア
１４１ａ，１４１ｂ，１４１ｃ  フィルタ
１４２  パケット廃棄部
１４３ａ，１４３ｂ，１４３ｃ  予約キュー
１４３ｄ  ＢＥＳキュー
１４４  スケジューラ
【図１】
0003854745.tif 000002
【図２】
0003854745.tif 000003
【図３】
0003854745.tif 000004
【図４】
0003854745.tif 000005
【図５】
0003854745.tif 000006
【図６】
0003854745.tif 000007
【図７】
0003854745.tif 000008
【図８】
0003854745.tif 000009
【図９】
0003854745.tif 000010
【図１０】
0003854745.tif 000011
【図１１】
0003854745.tif 000012
【図１２】
0003854745.tif 000013
【図１３】
0003854745.tif 000014
【図１４】
0003854745.tif 000015
【図１５】
0003854745.tif 000016