(57)【特許請求の範囲】
【請求項１】
受信したパケットをバッファに格納した後所定の順番で送出するパケット交換機の送信キュー管理システムであって、
受信したパケットのヘッダ情報を識別するヘッダ情報識別手段と、このヘッダ情報識別手段における識別結果に応じて他のパケットの伝送制御に用いられかつ廃棄されることにより輻輳制御が期待されるパケットを選択的に廃棄するための廃棄優先情報を前記パケットに付与する廃棄優先情報付与手段と、前記廃棄優先情報が付与されたパケットが格納されるバッファ手段と、前記バッファ手段に格納されたパケット数がしきい値に達した場合に同一順位の前記廃棄優先情報が付与されたパケットを一括廃棄する廃棄処理手段とを含むことを特徴とするパケット交換機の送信キュー管理システム。
【請求項２】
前記ヘッダ情報識別手段は廃棄優先情報付与の基となる情報が保持された廃棄優先情報保持部と、前記廃棄優先情報保持部に保持された情報と前記パケットのヘッダ情報とを比較して前記ヘッダ情報を識別するヘッダ識別部とからなることを特徴とする請求項１記載のパケット交換機の送信キュー管理システム。
【請求項３】
前記廃棄優先情報保持部に保持される情報としてパケットヘッダパタンと、前記パケットヘッダパタンに対応した廃棄優先情報とを含むことを特徴とする請求項２記載のパケット交換機の送信キュー管理システム。
【請求項４】
前記ヘッダ識別部は前記パケットヘッダパタンと前記パケットのヘッダ情報とを比較し、一致する場合にそのパケットヘッダパタンに対応した廃棄優先情報を出力することを特徴とする請求項３記載のパケット交換機の送信キュー管理システム。
【請求項５】
受信したパケットをバッファに格納した後、所定の順番で送出するパケット交換機の送信キュー管理システムであって、
受信したパケットのヘッダ情報を識別するヘッダ情報識別手段と、このヘッダ情報識別手段における識別結果に応じて前記パケットに所定順位の廃棄優先情報を付与する廃棄優先情報付与手段と、前記廃棄優先情報が付与されたパケットが格納されるバッファ手段と、前記バッファ手段に格納されたパケット数がしきい値に達した場合に同一順位の前記廃棄優先情報が付与されたパケットを一括廃棄する廃棄処理手段とを含み、
前記ヘッダ情報識別手段は、廃棄優先情報付与の基となる情報が保持された廃棄優先情報保持部と、前記廃棄優先情報保持部に保持された情報と前記パケットのヘッダ情報とを比較して前記ヘッダ情報を識別するヘッダ識別部とからなり、
前記廃棄優先情報保持部に保持される情報としてパケットヘッダパタンと、前記パケットヘッダパタンに対応した廃棄優先情報と、各エントリ毎の使用統計値とを含むことを特徴とするパケット交換機の送信キュー管理システム。
【請求項６】
前記ヘッダ識別部は前記パケットヘッダパタンと前記パケットのヘッダ情報とを比較し、一致する場合にそのパケットヘッダパタンに対応した廃棄優先情報及び前記使用統計値を出力することを特徴とする請求項５記載のパケット交換機の送信キュー管理システム。
【請求項７】
前記廃棄優先情報付与手段は前記ヘッダ識別部から出力された廃棄優先情報及び前記使用統計値を集約して得た新たな廃棄優先情報を前記パケットに付与することを特徴とする請求項６記載のパケット交換機の送信キュー管理システム。
【請求項８】
前記廃棄優先情報保持部に保持される情報としてコネクションの種別を示すコネクションテーブルと、前記コネクションテーブルに対応した廃棄優先情報とを含むことを特徴とする請求項２記載のパケット交換機の送信キュー管理システム。
【請求項９】
前記ヘッダ識別部は前記コネクションテーブルと前記パケットのヘッダ情報とを比較し、一致する場合にそのコネクションテーブルに対応した廃棄優先情報を出力することを特徴とする請求項８記載のパケット交換機の送信キュー管理システム。
【請求項１０】
前記廃棄優先情報付与手段は前記ヘッダ識別部から出力された廃棄優先情報と同一の廃棄優先情報を前記パケットに付与することを特徴とする請求項４又は９記載のパケット交換機の送信キュー管理システム。
【請求項１１】
前記しきい値は２種以上設定され、かつ前記廃棄優先の順位は３種以上設定されることを特徴とする請求項１乃至１０いずれかに記載のパケット交換機の送信キュー管理システム。
【請求項１２】
前記廃棄処理手段は廃棄優先順位が高いパケットから順に廃棄することを特徴とする請求項１乃至１１いずれかに記載のパケット交換機の送信キュー管理システム。
【請求項１３】
受信したパケットをバッファに格納した後所定の順番で送出するパケット交換機の送信キュー管理方法であって、
受信したパケットのヘッダ情報を識別するヘッダ情報識別ステップと、このヘッダ情報識別ステップにおける識別結果に応じて他のパケットの伝送制御に用いられかつ廃棄されることにより輻輳制御が期待されるパケットを選択的に廃棄するための廃棄優先情報を前記パケットに付与する廃棄優先情報付与ステップと、前記廃棄優先情報が付与されたパケットを格納部に格納するパケット格納ステップと、前記パケット格納ステップにて格納されたパケット数がしきい値に達した場合に同一順位の前記廃棄優先情報が付与されたパケットを一括廃棄する廃棄処理ステップとを含むことを特徴とするパケット交換機の送信キュー管理方法。
【請求項１４】
前記ヘッダ情報識別ステップは廃棄優先情報付与の基となる情報が保持された廃棄優先情報保持部を参照する参照ステップと、前記廃棄優先情報保持部に保持された情報と前記パケットのヘッダ情報とを比較して前記ヘッダ情報を識別するヘッダ識別ステップとからなることを特徴とする請求項１３記載のパケット交換機の送信キュー管理方法。
【請求項１５】
前記廃棄優先情報保持部に保持される情報としてパケットヘッダパタンと、前記パケットヘッダパタンに対応した廃棄優先情報とを含むことを特徴とする請求項１４記載のパケット交換機の送信キュー管理方法。
【請求項１６】
前記ヘッダ識別ステップは前記パケットヘッダパタンと前記パケットのヘッダ情報とを比較し、一致する場合にそのパケットヘッダパタンに対応した廃棄優先情報を出力することを特徴とする請求項１５記載のパケット交換機の送信キュー管理方法。
【請求項１７】
受信したパケットをバッファに格納した後、所定の順番で送出するパケット交換機の送信キュー管理方法であって、
受信したパケットのヘッダ情報を識別するヘッダ情報識別ステップと、このヘッダ情報識別ステップにおける識別結果に応じて前記パケットに所定順位の廃棄優先情報を付与する廃棄優先情報付与ステップと、前記廃棄優先情報が付与されたパケットを格納部に格納するパケット格納ステップと、前記パケット格納ステップにて格納されたパケット数がしきい値に達した場合に同一順位の前記廃棄優先情報が付与されたパケットを一括廃棄する廃棄処理ステップとを含み、
前記ヘッダ情報識別ステップは、廃棄優先情報付与の基となる情報が保持された廃棄優先情報保持部を参照する参照ステップと、前記廃棄優先情報保持部に保持された情報と前記パケットのヘッダ情報とを比較して前記ヘッダ情報を識別するヘッダ識別ステップとからなり、
前記廃棄優先情報保持部に保持される情報としてパケットヘッダパタンと、前記パケットヘッダパタンに対応した廃棄優先情報と、各エントリ毎の使用統計値とを含むことを特徴とするパケット交換機の送信キュー管理方法。
【請求項１８】
前記ヘッダ識別ステップは前記パケットヘッダパタンと前記パケットのヘッダ情報とを比較し、一致する場合にそのパケットヘッダパタンに対応した廃棄優先情報及び前記使用統計値を出力することを特徴とする請求項１７記載のパケット交換機の送信キュー管理方法。
【請求項１９】
前記廃棄優先情報付与ステップは前記ヘッダ識別ステップにて出力された廃棄優先情報及び前記使用統計値を集約して得た新たな廃棄優先情報を前記パケットに付与することを特徴とする請求項１８記載のパケット交換機の送信キュー管理方法。
【請求項２０】
前記廃棄優先情報保持部に保持される情報としてコネクションの種別を示すコネクションテーブルと、前記コネクションテーブルに対応した廃棄優先情報とを含むことを特徴とする請求項１４記載のパケット交換機の送信キュー管理方法。
【請求項２１】
前記ヘッダ識別ステップは前記コネクションテーブルと前記パケットのヘッダ情報とを比較し、一致する場合にそのコネクションテーブルに対応した廃棄優先情報を出力することを特徴とする請求項２０記載のパケット交換機の送信キュー管理方法。
【請求項２２】
前記廃棄優先情報付与ステップは前記ヘッダ識別ステップにて出力された廃棄優先情報と同一の廃棄優先情報を前記パケットに付与することを特徴とする請求項１６又は２１記載のパケット交換機の送信キュー管理方法。
【請求項２３】
前記しきい値は２種以上設定され、かつ前記廃棄優先の順位は３種以上設定されることを特徴とする請求項１３乃至２２いずれかに記載のパケット交換機の送信キュー管理方法。
【請求項２４】
前記廃棄処理ステップは廃棄優先順位が高いパケットから順に廃棄することを特徴とする請求項１３乃至２３いずれかに記載のパケット交換機の送信キュー管理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はパケット交換機の送信キュー管理システム及び管理方法に関し、特に出力バッファ方式パケット交換機の送信キュー管理システム及び管理方法に関する。
【０００２】
【従来の技術】
従来の出力バッファ方式パケット交換機のキュー管理システムには、Ｔａｉｌ−Ｄｒｏｐ方式、Ｒａｎｄｏｍ  Ｄｒｏｐ  Ｏｎ  Ｆｕｌｌ方式やＲａｎｄｏｍ
Ｅａｒｌｙ  Ｄｅｔｅｃｔｉｏｎ（ＲＥＤ）方式などがある。
【０００３】
Ｔａｉｌ−Ｄｒｏｐ方式は、送信キュー内のパケット蓄積数がキュー長に達してその送信キューが一杯になった場合、後続の溢れたパケットを単純に廃棄していく方式である。Ｒａｎｄｏｍ  Ｄｒｏｐ  Ｏｎ  Ｆｕｌｌ方式は、同様に送信キューが一杯になった場合、送信キュー内に蓄積されているパケットをランダムに廃棄する方式である。ＲＥＤ方式は、送信キュー内のパケット蓄積数が一定のしきい値を超過した場合、そのキューに蓄積される後続のパケットを統計的に廃棄する方式である。ここでは、後続のパケットが廃棄される確率は、キュー内のパケット蓄積数に比例して増加する。
【０００４】
又、この種のキュー管理システムの他の例が特開平１１−６８８３５号公報（以下、文献１という）、特許第２８８６９７６号公報（以下、文献２という）、特表平１１−５１００１４号公報（以下、文献３という）及び特開平１０−１３４２７号公報（以下、文献４という）に開示されている。
【０００５】
文献１開示の技術は、通常送信待ちキュ−と廃棄優先送信待ちキュ−の２つを用意しておき、フレームが廃棄優先フレームであれば廃棄優先送信待ちキュ−へキュ−イングし、そうでなければ通常送信待ちキュ−へキュ−イングする。そして、輻輳発生時には廃棄優先送信待ちキュ−内のフレームを一括廃棄する、というものである。
【０００６】
文献２開示の技術は、セルに廃棄特性のクラスを付与し、そのクラスに対応したバッファメモリを設けておく。そして、バッファメモリの使用量がしきい値を超えるとそのバッファメモリ内のセルを廃棄する、というものである。
【０００７】
文献３開示の技術は、ヘッダ部にセル損優先度標識が付与されており、バッファ内のセル数がしきい値を超えれば、又一連のセル内のセルのためのセル損優先度標識が第１の状態にセットされれば、第１のセルと第２のセルとの間に受信された一連のセルは廃棄される、というものである。
【０００８】
文献４開示の技術は、コネクション識別子とセル廃棄優先度を対応させて記憶しておき、コネクション毎のノード内セル蓄積数とセル優先度とに応じてセルを廃棄する、というものである。
【０００９】
【発明が解決しようとする課題】
しかしながら、従来の送信キュー管理システムは、送信キュー管理における輻輳制御を各パケットヘッダーの内容に基づいて行う仕組みを持たない為、送信キューが輻輳した場合輻輳の原因となるトラヒックを抑制する効果を持たないパケットも含めて、キューに蓄積された順番通りに、もしくはランダムに廃棄処理が行われ、効率の良い輻輳制御ができないという課題がある。上記文献１乃至４にもこの課題を解決する手段は開示されていない。
【００１０】
そこで本発明の目的は、効率の良い輻輳制御が可能なパケット交換機の送信キュー管理システム及び管理方法を提供することにある。
【００１１】
【課題を解決するための手段】
前記課題を解決するために本発明のパケット交換機の送信キュー管理システムは、受信したパケットをバッファに格納した後所定の順番で送出するパケット交換機の送信キュー管理システムであって、
受信したパケットのヘッダ情報を識別するヘッダ情報識別手段と、このヘッダ情報識別手段における識別結果に応じて他のパケットの伝送制御に用いられかつ廃棄されることにより輻輳制御が期待されるパケットを選択的に廃棄するための廃棄優先情報を前記パケットに付与する廃棄優先情報付与手段と、前記廃棄優先情報が付与されたパケットが格納されるバッファ手段と、前記バッファ手段に格納されたパケット数がしきい値に達した場合に同一順位の前記廃棄優先情報が付与されたパケットを一括廃棄する廃棄処理手段とを含むことを特徴とする。
【００１２】
又、本発明のパケット交換機の送信キュー管理方法は、受信したパケットをバッファに格納した後所定の順番で送出するパケット交換機の送信キュー管理方法であって、
受信したパケットのヘッダ情報を識別するヘッダ情報識別ステップと、このヘッダ情報識別ステップにおける識別結果に応じて他のパケットの伝送制御に用いられかつ廃棄されることにより輻輳制御が期待されるパケットを選択的に廃棄するための廃棄優先情報を前記パケットに付与する廃棄優先情報付与ステップと、前記廃棄優先情報が付与されたパケットを格納部に格納するパケット格納ステップと、前記パケット格納ステップにて格納されたパケット数がしきい値に達した場合に同一順位の前記廃棄優先情報が付与されたパケットを一括廃棄する廃棄処理ステップとを含むことを特徴とする。
【００１３】
本発明のパケット交換機の送信キュー管理システム及び本発明のパケット交換機の送信キュー管理方法によれば、送信キューに蓄積されるパケット各々に、パケット・ヘッダ識別部を用いて、明示的な廃棄優先情報を付与し、この送信キューのパケット蓄積数が一定のしきい値を超過した場合、廃棄優先度の高いパケットを一括廃棄する構成であるため、効率の良い輻輳制御が可能となる。
【００１４】
【発明の実施の形態】
まず、本発明の特徴について説明する。本発明は、データ・パケットネットワークを構成する出力バッファ方式パケット交換機の送信キュー管理において、送信キューに蓄積されるパケット各々に、パケット・ヘッダ識別部を用いて、明示的な廃棄優先情報を付与し、この送信キューのパケット蓄積数が一定のしきい値を超過した場合、廃棄優先度の高いパケットを一括廃棄するため、効率の良い輻輳制御が可能となる。
【００１５】
以下、本発明の実施の形態について添付図面を参照しながら説明する。図１は本発明に係るパケット交換機の送信キュー管理システムの最良の実施の形態の構成図である。同図を参照すると、パケット交換機の送信キュー管理システム２０は、パケットヘッダ識別部１と、廃棄優先情報付与部２と、送信キュー選択部３と、パケット蓄積数管理部４と、一括廃棄処理部５と、送信キューＡ７と、送信キューＢ８と、廃棄優先情報保持部１０と、しきい値保持部１１とを含んで構成される。又、送信キューＡ７と送信キューＢ８とによりキュー保持記憶部６が構成され、廃棄優先情報保持部１０と、しきい値保持部１１とにより設定記憶部９が構成される。
【００１６】
次に、この送信キュー管理システム２０の動作について説明する。図１において、パケットヘッダ識別部１は受信したパケットのヘッダ部を識別し、設定記憶部９にて実現される廃棄優先情報保持部１０に含まれるルックアップ・テーブル（ｌｏｏｋ−ｕｐ  ｔａｂｌｅ）のヘッダパタンと比較することにより、廃棄優先情報保持部１０に含まれるルックアップ・テーブル内のエントリ（ｅｎｔｒｙ）において前述パケットヘッダと前述ヘッダパタンの一致するものを特定する。
【００１７】
パケットヘッダ識別部１は、一致したエントリに含まれる廃棄優先情報を受信したパケットと共に廃棄優先情報付与部２に通知し、又、同エントリに含まれる送信キューＩＤ（ｉｄｅｎｔｉｔｙ）を送信キュー選択部３に通知する。
【００１８】
廃棄優先情報付与部２は、パケットヘッダ識別部１から通知を受けた廃棄優先情報をパケットヘッダ識別部１より同時に受けたパケットの特定ビット箇所にｓｅｔ（１）もしくはｒｅｓｅｔ（０）のどちらかの値を設定し、送信キュー選択部３に受け渡す。
【００１９】
送信キュー選択部３は、パケットヘッダ識別部１より通知を受けた送信キューＩＤに基づき、廃棄優先情報付与部２より受けたパケットをキュー保持記憶部６に実現される送信キューＡ７もしくは送信キューＢ８に蓄積する。
【００２０】
キュー保持記憶部６に実現される送信キューＡ７と送信キューＢ８はＦＩＦＯ（ｆｉｒｓｔ  ｉｎ  ｆｉｒｓｔ  ｏｕｔ）型キューであり、これらの送信キューに蓄積されたパケットは、順次キューに蓄積された順番に従ってそれぞれのキューより送出される。
【００２１】
パケット蓄積数管理部４は、定期的に各送信キューに蓄積されるパケット数を記録しており、そのパケット数が設定記憶部９に実現される、しきい値保持部１１に含まれるしきい値を超過しているか否かを監視する。パケット蓄積数管理部４が、ある特定の送信キューにおいてパケット蓄積数が前述のしきい値を超過したと判断した場合は、その送信キューに対して一括廃棄処理を一括廃棄処理部５に促す。
【００２２】
一括廃棄処理部５は、パケット蓄積数管理部４より指定された送信キューに蓄積される全パケットの廃棄優先情報を持つ特定ビット箇所を確認して、廃棄優先情報がｓｅｔ（１）されているならばそのパケットを廃棄する一括廃棄処理を行う。
【００２３】
このようにして、本願発明では、送信キューに蓄積されるパケット各々に、パケット・ヘッダ識別部１を用いて、明示的な廃棄優先度情報を付与しているので、例えばＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）通信においてはＴＣＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  ｐｒｔｏｃｏｌ）パケット等が廃棄されることにより輻輳制御を期待できるパケットを選択的に廃棄するなど制御粒度が細かい輻輳制御を実現できる。
【００２４】
又、この送信キューのパケット蓄積数が一定のしきい値を超過した場合、廃棄優先度の高いパケットを一括廃棄する方式により、送信キュー内のパケット蓄積数に関わらず効果が発揮されるまでの遅延が少ない、効果の即効性の高い輻輳制御を実現できる。
【００２５】
【実施例】
次に、本発明の実施例について説明する。まず、第１実施例について説明する。第１実施例の構成は図１と同様であるので、引続き図１を参照する。図２はパケットの一例の形式図である。図２に示すように、パケット１５はヘッダ１６とデータ１７とからなり、ヘッダ１６は後述する特定ビット１８を含んでいる。
【００２６】
図１において、パケットヘッダ識別部１は受信したパケット１５のヘッダ１６を識別し、設定記憶部９にて実現される廃棄優先情報保持部１０に含まれるルックアップ・テーブルのヘッダパタンと比較することにより、廃棄優先情報保持部１０に含まれるルックアップ・テーブル内のエントリにおいて前述パケットヘッダ１６と前述ヘッダパタンの一致するものを特定する。
【００２７】
例えば、前述パケットヘッダパタンとしてＴＣＰパケットを特定するパタンを持つエントリが１個のみ存在し、又、パケットヘッダ識別部１が受信パケット１５はＴＣＰパケットであると識別した場合、これらのパケットヘッダ１６とパケットヘッダパタンは一致したと言える。この場合、パケットヘッダ識別部１は、一致したエントリに含まれる廃棄優先情報を受信したパケット１５と共に廃棄優先情報付与部２に通知し、又、同エントリに含まれる送信キューＩＤを送信キュー選択部３に通知する。
【００２８】
廃棄優先情報付与部２は、パケットヘッダ識別部１から通知を受けた廃棄優先情報をパケットヘッダ識別部１より同時に受けたパケット１５の特定ビット箇所１８にｓｅｔ（１）もしくはｒｅｓｅｔ（０）のどちらかの値を設定し、送信キュー選択部３に受け渡す。
【００２９】
送信キュー選択部３は、パケットヘッダ識別部１より通知を受けた送信キューＩＤに基づき、廃棄優先情報付与部２より受けたパケットをキュー保持記憶部６に実現される送信キューＡ７もしくは送信キューＢ８に蓄積する。
【００３０】
前例において、ＴＣＰパケットを特定するパケットヘッダ・パタンを持つエントリに含まれる廃棄優先情報がｓｅｔ（１）であり、また、送信キューＩＤが送信キューＡ７を指定している場合、この出力バッファ方式パケット交換機の送信キュー管理システム２０が受けたＴＣＰパケットのみが、廃棄優先情報としてｓｅｔ（１）の値が設定され、又、これらのＴＣＰパケットは全て送信キューＡ７に蓄積されることになる。
【００３１】
キュー保持記憶部６に実現される送信キューＡ７と送信キューＢ８はＦＩＦＯ型キューであり、これらの送信キューに蓄積されたパケットは、順次キューに蓄積された順番に従ってそれぞれのキューより送出される。
【００３２】
パケット蓄積数管理部４は、定期的に各送信キューに蓄積されるパケット数を記録しており、そのパケット数が設定記憶部９に実現される、しきい値保持部１１に含まれるしきい値を超過しているか否かを監視する。パケット蓄積数管理部４が、ある特定の送信キューにおいてパケット蓄積数が前述のしきい値を超過したと判断した場合は、その送信キューに対して一括廃棄処理を一括廃棄処理部５に促す。
【００３３】
一括廃棄処理部５は、パケット蓄積数管理部４より指定された送信キューに蓄積される全パケット１５の廃棄優先情報を持つ特定ビット箇所１８を確認して、廃棄優先情報がｓｅｔ（１）に設定されているならばそのパケットを廃棄する一括廃棄処理を行う。
【００３４】
再び、前例において、しきい値保持部１１に含まれるしきい値が一例として１０パケットと設定されており、かつ、送信キューＡ７のパケット蓄積数が１０パケットを超えた場合、パケット蓄積数管理部４は一括廃棄処理部５に対して送信キューＡ７の一括廃棄処理を指示し、その結果一括廃棄処理部５は、その時点で送信キューＡ７に蓄積され廃棄優先情報を持つ特定ビット箇所１８がｓｅｔ（１）を示しているパケット１５、即ち送信キューＡ７内の全てのＴＣＰパケットを一括廃棄する。
【００３５】
図３は廃棄優先情報保持部１０のデータ構造図である。同図を参照すると、同図には図１に示す廃棄優先情報保持部１０の詳細な構成が示されている。番号１９は廃棄優先情報保持部１０を構成するテーブルの行番号を指定する。番号１９はユニークな数値でありＮ（Ｎは正の整数）行のエントリを持つテーブルにおいては、１からＮまでの連続した整数値を持つ。
【００３６】
パケットヘッダ・パタン２１には、パケットヘッダの全て、もしくは一部のデータパタンが入力されており、このパケットヘッダ・パタン２１を自在に設定することにより、特定アドレス宛のパケットの指定、特定プロトコルのパケットの指定や、ＴＣＰやＵＤＰ（Ｕｓｅｒ  Ｄａｔａｇｒａｍ  Ｐｒｏｔｏｃｏｌ）など特定トランスポート・プロトコルのパケットの指定などが可能である。
【００３７】
送信キューＩＤ２２には、特定の送信キューを指定するＩＤ情報が必ず格納される。図１に示される実施例の場合には、送信キューＡ７もしくは送信キューＢ８どちらかを特定するＩＤ情報が格納される。
【００３８】
廃棄優先情報２３には、ｓｅｔ（１）もしくはｒｅｓｅｔ（０）のどちらかの値が格納され、含まれるエントリー固有な廃棄優先情報を示す。ｓｅｔ（１）の値を持つパケットは、ｒｅｓｅｔ（０）の値を持つパケットに比較してより優先的に廃棄されることを示す。
【００３９】
以上詳細に第１実施例の構成を述べたが、図１の送信キューＡ７と送信キューＢ８を実現する手段は、当業者にとってよく知られており、又本発明とは直接関係しないので、その詳細な構成は省略する。
【００４０】
次に図１の出力バッファ方式パケット交換機の送信キュー管理システム２０のパケットヘッダ識別部１、廃棄優先情報付与部２及び送信キュー選択部３における処理動作を図４を参照しながら説明する。図４はパケットヘッダ識別、廃棄優先情報付与及び送信キュー選択処理動作を示すフローチャートである。
【００４１】
まず、受信したパケット１５のヘッダ１６が前述のパケットヘッダ識別部１により識別され、そのパケット固有の廃棄優先情報が取得可能か否かが判定される（図４のＳ１）。ヘッダ１６の内容と廃棄優先情報保持部１０に含まれるルックアップ・テーブル内のパケットヘッダ・パタン２１の内容とが一致すればそのパケット固有の廃棄優先情報が取得可能と判定され、不一致であれば取得できないと判定される。
【００４２】
その廃棄優先情報が取得可能である場合（Ｓ１にてＹＥＳの場合）は、取得した情報（ルックアップ・テーブル内の廃棄優先情報２３）に基づいて、そのパケット固有の廃棄優先情報をｓｅｔ（１）、ｒｅｓｅｔ（０）の何れかに設定する（図２のＳ２）。即ち、廃棄優先情報２３の内容がｓｅｔ（１）であればｓｅｔ（１）に、ｒｅｓｅｔ（０）であればｒｅｓｅｔ（０）に夫々設定する。一方、廃棄優先情報２３が取得できない場合（Ｓ１にてＮＯの場合）には、自動的にｒｅｓｅｔ（０）を廃棄優先情報としてそのパケットに設定する（図２のＳ３）。
【００４３】
そして、廃棄優先情報の付与されたパケット１５は、パケットヘッダー識別部１で取得された送信キューＩＤ情報２２に基づいて送信キューが選択され、その選択された送信キューにパケット１５は蓄積される（図２のＳ４）。即ち、パケットヘッダー識別部１で取得された送信キューＩＤ２２が送信キューＡ７であれば、その廃棄優先情報の付与されたパケット１５は送信キューＡ７に蓄積され、送信キューＢ８であれば、送信キューＢ８に蓄積される。
【００４４】
次に、図１の出力バッファ方式パケット交換機の送信キュー管理システム２０におけるパケット蓄積数管理部４の処理動作を図５を参照しながら説明する。図５はパケット蓄積数管理部４の処理動作を示すフローチャートである。
【００４５】
同図において、各送信キューに蓄積されたパケット数がパケット蓄積数として各送信キュー毎に取得され一時的な変数Ｎに代入される（図５のＳ１１）。次にこの値、Ｎは、予め設定されたしきい値と比較される（図５のＳ１２）。そして、この値Ｎがしきい値を超過しない場合（Ｓ１２にてＮＯの場合）は、一時的なタイマーＷＡＩＴを通して処理の最初に戻される（図５のＳ１３）。一方、この値、Ｎがしきい値を超過する場合（Ｓ１２にてＹＥＳの場合）は、該当する送信キューに対して一括廃棄処理が完了したのち（図５のＳ１４）、一時的なタイマーＷＡＩＴを通して（図５のＳ１３）、処理の最初に戻される（図５のＳ１１）。
【００４６】
次に図１の出力バッファ方式パケット交換機の送信キュー管理システムにおける一括廃棄処理部５の処理動作を図６を参照しながら説明する。図６は一括廃棄処理部５の処理動作を示すフローチャートである。
【００４７】
同図において、一括廃棄処理の対象となった送信キューに蓄積されたパケット数がパケット蓄積数として取得され一時的な変数Ｎに代入される。同時にもう一つの一時的な変数、Ｋ（Ｋは正の整数）に初期値として整数１が設定される（図６のＳ２１）。次に、変数Ｎと変数Ｋは大きさの比較がなされ、又同時に該当送信キューが空であるか否かが確認される（図６のＳ２２）。
【００４８】
変数Ｋが変数Ｎの値を超えた場合、もしくは該当送信キューが空であった場合には（Ｓ２２にてＮＯの場合）、一括廃棄処理は完了する（図６のＳ２３）。一方、変数Ｋが変数Ｎの値を超えておらず、かつ該当送信キューが空でない場合には（Ｓ２２にてＹＥＳの場合）、該当送信キューに蓄積されたＫ番目のパケットの廃棄優先情報を取得しその内容を判定する処理がなされる（図６のＳ２４）。
【００４９】
そして、Ｋ番目のパケットの廃棄優先情報がｓｅｔ（１）を示す場合には（Ｓ２４にてｓｅｔ（１）の場合）、そのパケットは廃棄される（図６のＳ２５）。一方、Ｋ番目のパケットの廃棄優先情報がｒｅｓｅｔ（０）を示す場合には（Ｓ２４にてｒｅｓｅｔ（０）の場合）、そのパケットは廃棄されずに次の処理に移る。最後に、変数Ｋはインクリメントされ（図６のＳ２７）、２２まで処理は戻される。
【００５０】
次に、第２実施例について説明する。図７は第２実施例の構成図である。なお、同図において第１実施例（図１参照）と同様の構成部分については同一番号を付し、その説明を省略する。第２実施例の基本的構成は上記第１実施例と同様であるが、第２実施例ではパケットヘッダ識別部１における廃棄優先情報付与のスケジューリング処理についてさらに工夫している。又、この実施例が持つ廃棄優先情報保持部４０を図８に示す。図８は廃棄優先情報保持部４０のデータ構造図である。第２実施例は第１実施例の構成に廃棄スケジューラ部３０と、スケジューラデータベース３２とを追加したものである。又、図８は図３に使用統計値３１を追加したものである。
【００５１】
ここでは、図８の廃棄優先情報保持部４０に各エントリ毎の使用統計値３１を設け、ある特定のエントリーがどの位の頻度で使用されたかを計算できる仕組みを持つ。本実施例においては、パケットヘッダ識別部１は、１つのパケットのパケットヘッダ識別処理として、廃棄優先情報保持部４０に含まれるルックアップ・テーブルのヘッダパタンと比較することにより、図８に示す廃棄優先情報保持部４０に含まれるルックアップ・テーブル内のエントリにおいて前述パケットヘッダ１６と前述ヘッダパタンの一致するものを特定するが、この時、パケットヘッダ識別部１は、一致したエントリに含まれる廃棄優先情報２３を受信したパケットと共に廃棄優先情報付与部２に通知し、同エントリに含まれる送信キューＩＤ２２を送信キュー選択部３に通知すると同時に、廃棄スケジューラ部３０に使用統計値３１を通知する。
【００５２】
廃棄スケジューラ部３０は、パケットヘッダ識別部１より受けた使用統計値３１を基にある特定のエントリがどの位の頻度で使用されたかを計算し、その値をスケジューラデータベース３２に参照することにより、統計的にそのパケットを廃棄優先させるか否かを決定して、その結果を廃棄優先情報付与部２に通知する。スケジューラデータベース３２には、廃棄スケジューラ部３０が統計的に該当パケットを廃棄優先させるか否かを判断するための比較情報が保持されている。
【００５３】
廃棄優先情報付与部２は、パケットヘッダ識別部１から通知を受けた廃棄優先情報２３と廃棄スケジューラ部３０から通知を受けた結果を集約して、パケットヘッダ識別部１より同時に受けたパケットの特定ビット箇所にｓｅｔ（１）もしくはｒｅｓｅｔ（０）のどちらかの値を設定し、送信キュー選択部３に受け渡す。その他の構成や動作は本願発明の実施例と同一である。
【００５４】
このように、第２実施例では、廃棄優先情報保持部４０に各エントリ毎の使用統計値３１を設け、ある特定のエントリがどの位の頻度で使用されたかを計算できる仕組みを持ち、廃棄スケジューラ部３０がその計算結果を基に廃棄優先情報を付与するか付与しないかのスケジューリングを追加で行うようにしているので、ＵＤＰプロトコルの様に輻輳制御機構を持たないトランスポート・プロトコルを用いた通信においても、スケジューラを用いて定量的に廃棄優先度の高い情報をパケットに付与することにより、これらのパケットの送信レート制御を行うことが可能となる効果が得られる。
【００５５】
次に、第３実施例について説明する。図９はこの実施例が持つ廃棄優先情報保持部のデータ構造図である。第３実施例の基本的構成は上記第１実施例と同様であるが、第３実施例ではパケットヘッダ識別部１におけるＩＰ通信コネクション認識処理についてさらに工夫している。図９は図３のパケットヘッダ・パタン２１を拡張したデータ構造を示している。図９において、コネクションテーブル３３は、パケットヘッダ・パタンを保持する代わりに、ＩＰ通信コネクションを示すコネクション情報を保持する。このように、第３実施例では、パケットヘッダ識別部１の実装にパケットヘッダ・パタン２１を持つ代わりにＩＰ通信コネクションを示すコネクションテーブル３３を持つようにしており、送信キュー内の個々のＩＰ通信コネクションを認識して選択的に廃棄優先情報を付与することを可能としているので、送信キューを一つのコネクションが占有し、他のコネクションに対する通信の公平性を侵害することを防ぐことができる効果が得られる。
【００５６】
次に、第４実施例について説明する。第４実施例の基本的構成は上記第１実施例と同様であるが、第４実施例ではしきい値と廃棄優先情報の持ち方についてさらに工夫している。図１に示すしきい値保持部１１のしきい値を各送信キューに対して複数持つ様に変更し、又、図３に示す廃棄優先情報２３を２レベルではなく複数レベル持つように変更する。
【００５７】
第４実施例によれば、しきい値と廃棄優先情報の持ち方を多層化することにより、一括廃棄処理を複数の段階において行うことを可能としているので、粒度のより細かい制御を実現できる効果が得られる。
【００５８】
【発明の効果】
本発明によれば、受信したパケットをバッファに格納した後所定の順番で送出するパケット交換機の送信キュー管理システムであって、受信したパケットのヘッダ情報を識別するヘッダ情報識別手段と、このヘッダ情報識別手段における識別結果に応じて前記パケットに所定順位の廃棄優先情報を付与する廃棄優先情報付与手段と、前記廃棄優先情報が付与されたパケットが格納されるバッファ手段と、前記バッファ手段に格納されたパケット数がしきい値に達した場合に同一順位の前記廃棄優先情報が付与されたパケットを一括廃棄する廃棄処理手段とを含むため、効率の良い輻輳制御が可能となる。
【００５９】
より具体的には、第１の効果は、送信キューに蓄積されるパケット各々に、パケットヘッダ識別手段を用いて、明示的な廃棄優先度情報を付与しているので、例えばＩＰ通信においてはＴＣＰパケット等廃棄されることにより輻輳制御を期待できるパケットを選択的に廃棄するなど制御粒度が細かく、かつ効果的な輻輳制御を実現できることである。
【００６０】
第２の効果は、この送信キューのパケット蓄積数が一定のしきい値を超過した場合、廃棄優先度の高いパケットを一括廃棄しているので、送信キュー内のパケット蓄積数に関わらず効果が発揮されるまでの遅延が少ない、効果の即効性の高い輻輳制御を実現できることである。
【００６１】
第３の効果は、一括廃棄処理を行うトリガーイベントを送信キューが溢れた時ではなく、設定されたしきい値を超過した時としているので、送信キュー溢れによる廃棄優先度の低いパケットの不必要な廃棄行為を未然に防ぐことができることである。
【００６２】
第４の効果は、一括廃棄処理を行うトリガーイベントを送信キューが溢れた時ではなく、任意に設定できるしきい値を超過した時としているので、輻輳制御の制御粒度を向上できることである。
【００６３】
第５の効果は、送信キューに蓄積されるパケット各々に、パケットヘッダ識別手段を用いて、パケット毎に廃棄優先度情報を付与しているので、同一ＩＰ通信コネクションに属する複数のパケット列において、パケット送信順位の入れ替わりを発生させずにパケット毎の優先制御を実現できることである。
【００６４】
又、本発明による他の発明によれば、受信したパケットをバッファに格納した後所定の順番で送出するパケット交換機の送信キュー管理方法であって、受信したパケットのヘッダ情報を識別するヘッダ情報識別ステップと、このヘッダ情報識別ステップにおける識別結果に応じて前記パケットに所定順位の廃棄優先情報を付与する廃棄優先情報付与ステップと、前記廃棄優先情報が付与されたパケットを格納部に格納するパケット格納ステップと、前記パケット格納ステップにて格納されたパケット数がしきい値に達した場合に同一順位の前記廃棄優先情報が付与されたパケットを一括廃棄する廃棄処理ステップとを含むため、前述の本発明と同様の効果を奏する。
【図面の簡単な説明】
【図１】本発明に係るパケット交換機の送信キュー管理システムの最良の実施の形態の構成図である。
【図２】パケットの一例の形式図である。
【図３】廃棄優先情報保持部１０のデータ構造図である。
【図４】パケットヘッダ識別、廃棄優先情報付与及び送信キュー選択処理動作を示すフローチャートである。
【図５】パケット蓄積数管理部４の処理動作を示すフローチャートである。
【図６】一括廃棄処理部５の処理動作を示すフローチャートである。
【図７】第２実施例の構成図である。
【図８】廃棄優先情報保持部４０のデータ構造図である。
【図９】第３実施例が持つ廃棄優先情報保持部のデータ構造図である。
【符号の説明】
１  パケットヘッダ識別部
２  廃棄優先情報付与部
３  送信キュー選択部
４  パケット蓄積数管理部
５  一括廃棄処理部
６  キュー保持記憶部
７  送信キューＡ
８  送信キューＢ
９  設定記憶部
１０，４０  廃棄優先情報保持部
１１  しきい値保持部
３０  廃棄スケジューラ部
３２  スケジューラデータベース
【図１】
0003687501.tif 000002
【図２】
0003687501.tif 000003
【図３】
0003687501.tif 000004
【図４】
0003687501.tif 000005
【図５】
0003687501.tif 000006
【図６】
0003687501.tif 000007
【図７】
0003687501.tif 000008
【図８】
0003687501.tif 000009
【図９】
0003687501.tif 000010