(57)【特許請求の範囲】
【請求項１】
可変長パケットのルーティングを行なうパケット転送装置のパケット転送レート監視制御装置において、
受信パケットからその受信パケットが属する上位レイヤのフローを識別するとともに、その受信パケットの転送間隔と受信パケット長からパケット転送レートを測定し、その測定したパケット転送レートと予めフロー毎に設定されたレート情報とを比較して各受信パケットを転送する優先順位を決定することにより、
パケット転送レートが最低保証レート未満であるフローに関して受信したパケットをパケット転送レートが最低保証レート以上であるフローに関して受信したパケットよりも優先して転送し、
かつ、
パケット転送レートが最大制限レート未満であるフローに関して受信したパケットをパケット転送レートが最大制限レート以上であるフローに関して受信したパケットよりも優先して転送するようにした、
ことを特徴とするパケット転送レート監視制御装置。
【請求項２】
受信パケットのヘッダ情報から受信パケットが属する上位レイヤのフローを識別する上位レイヤフロー識別手段と、
前記上位レイヤフロー識別手段によって識別したフロー毎に受信パケットの転送間隔と受信パケット長からパケット転送レートを測定するパケット転送レート測定手段と、
前記パケット転送レート測定手段によって測定したパケット転送レートと予めフロー毎に設定された最低保証レート情報および最大制限レート情報とを比較する比較手段と、
前記比較手段によって比較した結果に基いて、受信パケットに対応するフローを、パケット転送レートが前記最低保証レート未満であるフローが属するグループ１と、パケット転送レートが前記最低保証レート以上であり、かつ前記最大制限レート未満であるフローが属するグループ２と、パケット転送レートが前記最大制限レートを超過したフローが属するグループ３とに分類する分類手段とを備え、
前記グループ１が属するフローに関して受信したパケットを前記グループ２に属するフローに関して受信したパケットに優先して転送し、かつ前記グループ２が属するフローに関して受信したパケットを前記グループ３に属するフローに関して受信したパケットに優先して転送するようにした、
ことを特徴とする請求項１記載のパケット転送レート監視制御装置。
【請求項３】
前記受信パケットを上位レイヤフロー識別手段によって識別したフロー毎に到着順にキューイングすることを特徴とする請求項２記載のパケット転送レート監視制御装置。
【請求項４】
前記グループ１に属するフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝について予め設定された最低保証レートを｛Ｋ１、Ｋ２、……、Ｋｉ｝、その合計をＫｓｕｍ  とし、前記グループ１に属するフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝に対する重み付け係数｛Ｗ１、Ｗ２、……、Ｗｉ｝をＷ１＝Ｋ１／Ｋｓｕｍ  、Ｗ２＝Ｋ２／Ｋｓｕｍ  、……、Ｗｉ＝Ｋｉ／Ｋｓｕｍ  のように定義し、
前記グループ２に属するフロー｛Ｇ１、Ｇ２、……、Ｇｊ｝について予め設定された最低保証レートを｛Ｌ１、Ｌ２、……、Ｌｊ｝、その合計をＬｓｕｍ  とし、前記グループ２に属するフロー｛Ｇ１、Ｇ２、……、Ｇｊ｝に対する重み付け係数｛Ｖ１、Ｖ２、……、Ｖｊ｝をＶ１＝Ｌ１／Ｌｓｕｍ  、Ｖ２＝Ｌ２／Ｌｓｕｍ  、……、Ｖｊ＝Ｌｊ／Ｌｓｕｍ  のように定義し、
パケットの出力インタフェース速度をＣとした場合、前記グループ１のフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝をパケット転送レートが｛Ｃ×Ｗ１、Ｃ×Ｗ２、……、Ｃ×Ｗｉ｝未満のグループ１Ａと、パケット転送レートが｛Ｃ×Ｗ１、Ｃ×Ｗ２、……、Ｃ×Ｗｉ｝以上のグループ１Ｂとに分類し、
前記グループ２のフロー｛Ｇ１、Ｇ２、……、Ｇｊ｝をパケット転送レートが｛（Ｃ−Ｋｓｕｍ  ）×Ｖ１、（Ｃ−Ｋｓｕｍ  ）×Ｖ２、……、（Ｃ−Ｋｓｕｍ  ）×Ｖｊ｝未満のグループ２Ａと、パケット転送レートが｛（Ｃ−Ｋｓｕｍ  ）×Ｖ１、（Ｃ−Ｋｓｕｍ  ）×Ｖ２、……、（Ｃ−Ｋｓｕｍ  ）×Ｖｊ｝以上のグループ２Ｂとに分類し、
前記グループ１Ａに属するフローに関して受信したパケットを前記グループ１Ｂに属するフローに関して受信したパケットに優先して転送し、前記グループ２Ａに属するフローに関して受信したパケットを前記グループ２Ｂに属するフローに関して受信したパケットに優先して転送することを特徴とする請求項２または３記載のパケット転送レート監視制御装置。
【請求項５】
前記グループ１に属するフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝について予め設定された最大制限レートを｛Ｍ１、Ｍ２、……、Ｍｉ｝、その合計をＭｓｕｍ  とし、前記グループ１に属するフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝に対する重み付け係数｛Ｗ１、Ｗ２、……、Ｗｉ｝をＷ１＝Ｍ１／Ｍｓｕｍ  、Ｗ２＝Ｍ２／Ｍｓｕｍ  、……、Ｗｉ＝Ｍｉ／Ｍｓｕｍ  のように定義し、
前記グループ２に属するフロー｛Ｇ１、Ｇ２、……、Ｇｊ｝について予め設定された最大制限レートを｛Ｎ１、Ｎ２、……、Ｎｊ｝、その合計をＮｓｕｍ  とし、前記グループ２に属するフロー｛Ｇ１、Ｇ２、……、Ｇｊ｝に対する重み付け係数｛Ｖ１、Ｖ２、……、Ｖｊ｝をＶ１＝Ｎ１／Ｎｓｕｍ  、Ｖ２＝Ｎ２／Ｎｓｕｍ  、……、Ｖｊ＝Ｎｊ／Ｎｓｕｍ  のように定義し、
パケットの出力インタフェース速度をＣとした場合、前記グループ１のフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝をパケット転送レートが｛Ｃ×Ｗ１、Ｃ×Ｗ２、……、Ｃ×Ｗｉ｝未満のグループ１Ａと、パケット転送レートが｛Ｃ×Ｗ１、Ｃ×Ｗ２、……、Ｃ×Ｗｉ｝以上のグループ１Ｂとに分類し、
前記グループ２のフロー｛Ｇ１、Ｇ２、……、Ｇｊ｝をパケット転送レートが｛（Ｃ−Ｍｓｕｍ  ）×Ｖ１、（Ｃ−Ｍｓｕｍ  ）×Ｖ２、……、（Ｃ−Ｍｓｕｍ  ）×Ｖｊ｝未満のグループ２Ａと、パケット転送レートが｛（Ｃ−Ｍｓｕｍ  ）×Ｖ１、（Ｃ−Ｍｓｕｍ  ）×Ｖ２、……、（Ｃ−Ｍｓｕｍ  ）×Ｖｊ｝以上のグループ２Ｂとに分類し、
前記グループ１Ａに属するフローに関して受信したパケットを前記グループ１Ｂに属するフローに関して受信したパケットに優先して転送し、前記グループ２Ａに属するフローに関して受信したパケットを前記グループ２Ｂに属するフローに関して受信したパケットに優先して転送することを特徴とする請求項２または３記載のパケット転送レート監視制御装置。
【請求項６】
前記グループ１に属するフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝について予め設定された最低保証レートを｛Ｋ１、Ｋ２、……、Ｋｉ｝、その合計をＫｓｕｍ  とし、前記グループ１に属するフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝に対する重み付け係数｛Ｗ１、Ｗ２、……、Ｗｉ｝をＷ１＝Ｋ１／Ｋｓｕｍ  、Ｗ２＝Ｋ２／Ｋｓｕｍ  、……、Ｗｉ＝Ｋｉ／Ｋｓｕｍ  のように定義し、
前記グループ２に属するフロー｛Ｇ１、Ｇ２、……、Ｇｊ｝について予め設定された最低保証レートを｛Ｌ１、Ｌ２、……、Ｌｊ｝、その合計をＬｓｕｍ  とし、前記グループ２に属するフロー｛Ｇ１、Ｇ２、……、Ｇｊ｝に対する重み付け係数｛Ｖ１、Ｖ２、……、Ｖｊ｝をＶ１＝Ｌ１／Ｌｓｕｍ  、Ｖ２＝Ｌ２／Ｌｓｕｍ  、……、Ｖｊ＝Ｌｊ／Ｌｓｕｍ  のように定義し、
かつ、前記グループ１に属するフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝について予め設定された最大制限レートを｛Ｍ１、Ｍ２、……、Ｍｉ｝、その合計をＭｓｕｍ  とし、前記グループ１に属するフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝に対する重み付け係数｛Ｗ１、Ｗ２、……、Ｗｉ｝をＷ１＝Ｍ１／Ｍｓｕｍ  、Ｗ２＝Ｍ２／Ｍｓｕｍ  、……、Ｗｉ＝Ｍｉ／Ｍｓｕｍ  のように定義し、
前記グループ２に属するフロー｛Ｇ１、Ｇ２、……、Ｇｊ｝について予め設定された最大制限レートを｛Ｎ１、Ｎ２、……、Ｎｊ｝、その合計をＮｓｕｍ  とし、前記グループ２に属するフロー｛Ｇ１、Ｇ２、……、Ｇｊ｝に対する重み付け係数｛Ｖ１、Ｖ２、……、Ｖｊ｝をＶ１＝Ｎ１／Ｎｓｕｍ  、Ｖ２＝Ｎ２／Ｎｓｕｍ  、……、Ｖｊ＝Ｎｊ／Ｎｓｕｍ  のように定義し、
さらに０から１までの値をとるパラメータαを用いることにより、前記グループ１に属するフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝に対する重み付け係数｛Ｗ１、Ｗ２、……、Ｗｉ｝をＷ１＝α×Ｋ１／Ｋｓｕｍ  ＋（１−α）×Ｍ１／Ｍｓｕｍ  、Ｗ２＝α×Ｋ２／Ｋｓｕｍ  ＋（１−α）×Ｍ２／Ｍｓｕｍ  、……、Ｗｉ＝α×Ｋｉ／Ｋｓｕｍ  ＋（１−α）×Ｍｉ／Ｍｓｕｍ  のように定義し、
前記グループ２に属するフロー｛Ｇ１、Ｇ２、……、Ｇｊ｝に対する重み付け係数｛Ｖ１、Ｖ２、……、Ｖｊ｝をＶ１＝α×Ｌ１／Ｌｓｕｍ  ＋（１−α）×Ｎ１／Ｎｓｕｍ  、Ｖ２＝α×Ｌ２／Ｌｓｕｍ  ＋（１−α）×Ｎ２／Ｎｓｕｍ  、……、Ｖｊ＝α×Ｌｊ／Ｌｓｕｍ  ＋（１−α）×Ｎｊ／Ｎｓｕｍ  のように定義し、
前記パラメータαを外部から設定可能であることを特徴とする請求項４または５記載のパケット転送レート監視制御装置。
【請求項７】
受信パケットのヘッダ情報からトランスポート層のプロトコル種別を識別するプロトコル種別識別手段を備え、パケット転送レートが前記最大制限レートを超過した場合、前記プロトコル種別識別手段によって識別したトランスポート層のプロトコルに応じて、受信したパケットを廃棄するか、あるいは受信したパケットの転送をパケット転送レートが前記最大制限レート以下になるまで遅延させてシェーピングを行なうかを選択することを特徴とする請求項２または３記載のパケット転送レート監視制御装置。
【請求項８】
受信パケットのヘッダ情報からトランスポート層のプロトコル種別を識別するプロトコル種別識別手段を備え、前記プロトコル種別識別手段によって識別したトランスポート層プロトコルがＴＣＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  ＣｏｎｔｒｏｌＰｒｏｔｏｃｏｌ  ）であり、かつパケット転送レートが前記最大制限レートを超過した場合には、転送するパケットのヘッダにＲＦＣ２４８１で定義されるＣＥ（Ｃｏｎｇｅｓｔｉｏｎ  Ｅｘｐｅｒｉｅｎｃｅｄ）ビットを付加することにより、送信側ノードに対して送信レートの抑制を通知することを特徴とする請求項２または３記載のパケット転送レート監視制御装置。
【請求項９】
受信パケットのヘッダ情報からトランスポート層のプロトコル種別を識別するプロトコル種別識別手段を備え、前記プロトコル種別識別手段によって識別したトランスポート層プロトコルがＴＣＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  ＣｏｎｔｒｏｌＰｒｏｔｏｃｏｌ  ）であり、かつパケット転送レートが前記最大制限レートを超過した場合には、以後、受信側ノードから送信側ノードに向けて転送する確認応答パケットのＴＣＰヘッダにおける受信ウィンドウサイズを０に上書きし、送信側ノードに対して送信レートの抑制を通知することを特徴とする請求項２または３記載のパケット転送レート監視制御装置。
【請求項１０】
可変長パケットのルーティングを行なうパケット転送装置のパケット転送レート監視制御方法において、
受信パケットからその受信パケットが属する上位レイヤのフローを識別するとともに、その受信パケットの転送間隔と受信パケット長からパケット転送レートを測定し、その測定したパケット転送レートと予めフロー毎に設定されたレート情報とを比較して各受信パケットを転送する優先順位を決定することにより、
パケット転送レートが最低保証レート未満であるフローに関して受信したパケットをパケット転送レートが最低保証レート以上であるフローに関して受信したパケットよりも優先して転送し、
かつ、
パケット転送レートが最大制限レート未満であるフローに関して受信したパケットをパケット転送レートが最大制限レート以上であるフローに関して受信したパケットよりも優先して転送するようにした、
ことを特徴とするパケット転送レート監視制御方法。
【請求項１１】
受信パケットのヘッダ情報から受信パケットが属する上位レイヤのフローを識別する上位レイヤフロー識別手順と、
前記上位レイヤフロー識別手順によって識別したフロー毎に受信パケットの転送間隔と受信パケット長からパケット転送レートを測定するパケット転送レート測定手順と、
前記パケット転送レート測定手順によって測定したパケット転送レートと予めフロー毎に設定された最低保証レート情報および最大制限レート情報とを比較する比較手順と、
前記比較手順によって比較した結果に基いて、受信パケットに対応するフローを、パケット転送レートが前記最低保証レート未満であるフローが属するグループ１と、パケット転送レートが前記最低保証レート以上であり、かつ前記最大制限レート未満であるフローが属するグループ２と、パケット転送レートが前記最大制限レートを超過したフローが属するグループ３とに分類する分類手順と、
前記グループ１が属するフローに関して受信したパケットを前記グループ２に属するフローに関して受信したパケットに優先して転送し、かつ前記グループ２が属するフローに関して受信したパケットを前記グループ３に属するフローに関して受信したパケットに優先して転送する転送制御手順と、
を有することを特徴とする請求項１０記載のパケット転送レート監視制御方法。
【請求項１２】
可変長パケットのルーティングを行なうパケット転送装置を制御するコンピュータの動作を制御するプログラムにおいて、
受信パケットのヘッダ情報から受信パケットが属する上位レイヤのフローを識別する上位レイヤフロー識別手順と、
前記上位レイヤフロー識別手順によって識別したフロー毎に受信パケットの転送間隔と受信パケット長からパケット転送レートを測定するパケット転送レート測定手順と、
前記パケット転送レート測定手順によって測定したパケット転送レートと予めフロー毎に設定された最低保証レート情報および最大制限レート情報とを比較する比較手順と、
前記比較手順によって比較した結果に基いて、受信パケットに対応するフローを、パケット転送レートが前記最低保証レート未満であるフローが属するグループ１と、パケット転送レートが前記最低保証レート以上であり、かつ前記最大制限レート未満であるフローが属するグループ２と、パケット転送レートが前記最大制限レートを超過したフローが属するグループ３とに分類する分類手順と、
前記グループ１が属するフローに関して受信したパケットを前記グループ２に属するフローに関して受信したパケットに優先して転送し、かつ前記グループ２が属するフローに関して受信したパケットを前記グループ３に属するフローに関して受信したパケットに優先して転送する転送制御手順と、
をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、加入者やサービス毎にパケット転送の最低保証レートまたは最大制限レートを契約するパケット通信網において、パケット転送装置に組み込むパケット転送レート監視制御装置、方法、及びプログラムに関する。
【０００２】
【従来の技術】
例えば双方向ＣＡＴＶやＡＤＳＬ（Ａｓｙｍｍｅｔｒｉｃ  Ｄｉｇｉｔａｌ  Ｓｕｂｓｃｒｉｂｅｒ  Ｌｏｏｐ）等の高速アクセス網を利用したパケット通信では、一般に加入者と網運用事業者との間でパケット転送の最低保証レートと最大制限レートのいずれか一方、または両方を契約し、その契約値に応じて接続料金が決められる。
この契約は加入者あたり１種類の場合もあれば、加入者が利用するデータ、音声、映像等のサービスに応じて複数の契約を結ぶ場合もある。特に網運用事業者がサービス毎に異なる課金体系を適用する場合には、後者のように加入者が利用するサービス毎にパケット転送の最低保証レートと最大制限レートを契約することになる。
また、サービスによっては、パケット転送の最低保証レートと最大制限レートに加えて、バースト性の許容度や、最大転送遅延時間等も契約対象になる。
【０００３】
したがって、これらの加入者との契約内容を守るために、パケット通信網の網運用事業者が保有するパケット転送装置には、パケット転送レートの監視制御装置が必要となる。
このパケット転送レート監視制御装置は、転送するパケットのヘッダ情報から上位レイヤのフローを識別し、フロー毎にパケットの転送レートと予め加入者が契約した最低保証レートや最大制限レートとの比較を行ない、この比較の結果やフローが属するサービスに応じて、トラフィックの優先制御、ポリシング、シェーピング等を行なう。
そして、従来のパケット転送レート監視制御装置としては、ＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ  Ｔｒａｎｓｆｅｒ  Ｍｏｄｅ）交換網におけるＵＰＣ（Ｕｓａｇｅ  ＰａｒａｍｅｔｅｒＣｏｎｔｒｏｌ）装置が知られており、例えば米国特許５，３１１，５１３  号や米国特許６，０６４，６５１  号、あるいは特開平９−４６３４４  号や特開平９−１４９０４６号等に記載されたものが知られている。
【０００４】
【発明が解決しようとする課題】
しかしながら、従来のパケット転送レート監視制御装置では、最大制限レートに関する契約値を数種類のパラメータで定義し、これに違反した場合はパケットを廃棄したり、パケットのヘッダに契約違反を示すタグを付加して転送の優先度を下げることにより、全てのフローについて最大制限レートの契約値を超えないようにするのみであった。
この場合、最大制限レートと最低保証レートとが等しければこれでも良いが、これらの値が異なり、かつ各フローに対する最大制限レートの合計がパケット転送装置のインタフェース速度を上回るように設定した場合、一時的にトラフィックが増加すると、各々のフローは最大制限レートを超過していないにもかかわらず、一部のフローの最低保証レートが守られなくなるという問題があった。
【０００５】
そこで、本発明は、加入者が利用するサービス毎にパケット転送の最低保証レートと最大制限レートを契約するパケット通信網において、トラフィック増加時にも最低保証レート以上のパケット転送速度を保証しつつ、契約した最低保証レートや最大制限レートに応じて余剰帯域の再配分を簡易かつ公平に行なうことを目的とする。
【０００６】
【課題を解決するための手段】
本発明（第１の発明）は前記目的を達成するため、可変長パケットのルーティングを行なうパケット転送装置のパケット転送レート監視制御装置において、受信パケットからその受信パケットが属する上位レイヤのフローを識別するとともに、その受信パケットの転送間隔と受信パケット長からパケット転送レートを測定し、その測定したパケット転送レートと予めフロー毎に設定されたレート情報とを比較して各受信パケットを転送する優先順位を決定することにより、パケット転送レートが最低保証レート未満であるフローに関して受信したパケットをパケット転送レートが最低保証レート以上であるフローに関して受信したパケットよりも優先して転送し、かつ、パケット転送レートが最大制限レート未満であるフローに関して受信したパケットをパケット転送レートが最大制限レート以上であるフローに関して受信したパケットよりも優先して転送するようにしたことを特徴とする。
したがって第１の発明によれば、加入者が利用するサービス毎にパケット転送の最低保証レートと最大制限レートを契約するパケット通信網において、トラフィック増加時にも最低保証レート以上のパケット転送速度を保証することが可能となる。
【０００７】
また、さらに具体的な構成としては、第２の発明によるパケット転送レート監視制御装置では、受信パケットのヘッダ情報から受信パケットが属する上位レイヤのフローを識別する上位レイヤフロー識別手段と、前記上位レイヤフロー識別手段によって識別したフロー毎に受信パケットの転送間隔と受信パケット長からパケット転送レートを測定するパケット転送レート測定手段と、前記パケット転送レート測定手段によって測定したパケット転送レートと予めフロー毎に設定された最低保証レート情報および最大制限レート情報とを比較する比較手段と、前記比較手段によって比較した結果に基いて、受信パケットに対応するフローを、パケット転送レートが前記最低保証レート未満であるフローが属するグループ１と、パケット転送レートが前記最低保証レート以上であり、かつ前記最大制限レート未満であるフローが属するグループ２と、パケット転送レートが前記最大制限レートを超過したフローが属するグループ３とに分類する分類手段とを備え、前記グループ１が属するフローに関して受信したパケットを前記グループ２に属するフローに関して受信したパケットに優先して転送し、かつ前記グループ２が属するフローに関して受信したパケットを前記グループ３に属するフローに関して受信したパケットに優先して転送するようにしたことを特徴とする。
【０００８】
このように、パケット転送レートに応じてフローを３段階のグループに分類することにより、常に最低保証レート未満のフローに対するパケット転送を優先させることができるため、一時的にトラフィックが増加した場合にも全てのフローの最低保証レートを守ることができる。
なお、フローが属するグループは固定的ではなく、パケット転送レートに応じて時間とともに変動する。
従って、グループ１に属するフローに対する受信パケットを優先的に転送したためにグループ２に属するフローに対する受信パケットの転送がしばらく行なわれなかった場合は、グループ２に属するフローのパケット転送レートが低下し、これが最低保証レートを下回るとフローがグループ１に属するようになる。このようにして、最低保証レートを一時的に超過したフローに対しても、最低保証レートの契約値以上のパケット転送を行なうことができる。
【０００９】
さらに第３の発明によるパケット転送レート監視制御装置では、受信パケットを上位レイヤフロー識別手段によって識別したフロー毎に到着順にキューイングすることを特徴とする。
これにより、パケットのキューイングをフロー毎に行なうことで、最大制限レートを超過したフローに属するパケットに対し、パケットの廃棄やタギングを行なうだけでなく、トラフィック特性が最大制限レートに準拠するようにシェーピングを容易に行なうことができる。
【００１０】
また、第４の発明のパケット転送レート監視制御装置では、前記グループ１に属するフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝について予め設定された最低保証レートを｛Ｋ１、Ｋ２、……、Ｋｉ｝、その合計をＫｓｕｍ  とし、前記グループ１に属するフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝に対する重み付け係数｛Ｗ１、Ｗ２、……、Ｗｉ｝をＷ１＝Ｋ１／Ｋｓｕｍ  、Ｗ２＝Ｋ２／Ｋｓｕｍ  、……、Ｗｉ＝Ｋｉ／Ｋｓｕｍ  のように定義し、前記グループ２に属するフロー｛Ｇ１、Ｇ２、……、Ｇｊ｝について予め設定された最低保証レートを｛Ｌ１、Ｌ２、……、Ｌｊ｝、その合計をＬｓｕｍ  とし、前記グループ２に属するフロー｛Ｇ１、Ｇ２、……、Ｇｊ｝に対する重み付け係数｛Ｖ１、Ｖ２、……、Ｖｊ｝をＶ１＝Ｌ１／Ｌｓｕｍ  、Ｖ２＝Ｌ２／Ｌｓｕｍ  、……、Ｖｊ＝Ｌｊ／Ｌｓｕｍ  のように定義し、パケットの出力インタフェース速度をＣとした場合、前記グループ１のフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝をパケット転送レートが｛Ｃ×Ｗ１、Ｃ×Ｗ２、……、Ｃ×Ｗｉ｝未満のグループ１Ａと、パケット転送レートが｛Ｃ×Ｗ１、Ｃ×Ｗ２、……、Ｃ×Ｗｉ｝以上のグループ１Ｂとに分類し、前記グループ２のフロー｛Ｇ１、Ｇ２、……、Ｇｊ｝をパケット転送レートが｛（Ｃ−Ｋｓｕｍ  ）×Ｖ１、（Ｃ−Ｋｓｕｍ  ）×Ｖ２、……、（Ｃ−Ｋｓｕｍ  ）×Ｖｊ｝未満のグループ２Ａと、パケット転送レートが｛（Ｃ−Ｋｓｕｍ  ）×Ｖ１、（Ｃ−Ｋｓｕｍ  ）×Ｖ２、……、（Ｃ−Ｋｓｕｍ  ）×Ｖｊ｝以上のグループ２Ｂとに分類し、前記グループ１Ａに属するフローに関して受信したパケットを前記グループ１Ｂに属するフローに関して受信したパケットに優先して転送し、前記グループ２Ａに属するフローに関して受信したパケットを前記グループ２Ｂに属するフローに関して受信したパケットに優先して転送することを特徴とする。
【００１１】
また、第５の発明のパケット転送レート監視制御装置では、前記グループ１に属するフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝について予め設定された最大制限レートを｛Ｍ１、Ｍ２、……、Ｍｉ｝、その合計をＭｓｕｍ  とし、前記グループ１に属するフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝に対する重み付け係数｛Ｗ１、Ｗ２、……、Ｗｉ｝をＷ１＝Ｍ１／Ｍｓｕｍ  、Ｗ２＝Ｍ２／Ｍｓｕｍ  、……、Ｗｉ＝Ｍｉ／Ｍｓｕｍ  のように定義し、前記グループ２に属するフロー｛Ｇ１、Ｇ２、……、Ｇｊ｝について予め設定された最大制限レートを｛Ｎ１、Ｎ２、……、Ｎｊ｝、その合計をＮｓｕｍ  とし、前記グループ２に属するフロー｛Ｇ１、Ｇ２、……、Ｇｊ｝に対する重み付け係数｛Ｖ１、Ｖ２、……、Ｖｊ｝をＶ１＝Ｎ１／Ｎｓｕｍ  、Ｖ２＝Ｎ２／Ｎｓｕｍ  、……、Ｖｊ＝Ｎｊ／Ｎｓｕｍ  のように定義し、パケットの出力インタフェース速度をＣとした場合、前記グループ１のフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝をパケット転送レートが｛Ｃ×Ｗ１、Ｃ×Ｗ２、……、Ｃ×Ｗｉ｝未満のグループ１Ａと、パケット転送レートが｛Ｃ×Ｗ１、Ｃ×Ｗ２、……、Ｃ×Ｗｉ｝以上のグループ１Ｂとに分類し、前記グループ２のフロー｛Ｇ１、Ｇ２、……、Ｇｊ｝をパケット転送レートが｛（Ｃ−Ｍｓｕｍ  ）×Ｖ１、（Ｃ−Ｍｓｕｍ  ）×Ｖ２、……、（Ｃ−Ｍｓｕｍ  ）×Ｖｊ｝未満のグループ２Ａと、パケット転送レートが｛（Ｃ−Ｍｓｕｍ  ）×Ｖ１、（Ｃ−Ｍｓｕｍ  ）×Ｖ２、……、（Ｃ−Ｍｓｕｍ  ）×Ｖｊ｝以上のグループ２Ｂとに分類し、前記グループ１Ａに属するフローに関して受信したパケットを前記グループ１Ｂに属するフローに関して受信したパケットに優先して転送し、前記グループ２Ａに属するフローに関して受信したパケットを前記グループ２Ｂに属するフローに関して受信したパケットに優先して転送することを特徴とする。
【００１２】
また、第６の発明のパケット転送レート監視制御装置では、さらに０から１までの値をとるパラメータαを用いることにより、前記グループ１に属するフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝に対する重み付け係数｛Ｗ１、Ｗ２、……、Ｗｉ｝をＷ１＝α×Ｋ１／Ｋｓｕｍ  ＋（１−α）×Ｍ１／Ｍｓｕｍ  、Ｗ２＝α×Ｋ２／Ｋｓｕｍ  ＋（１−α）×Ｍ２／Ｍｓｕｍ  、……、Ｗｉ＝α×Ｋｉ／Ｋｓｕｍ  ＋（１−α）×Ｍｉ／Ｍｓｕｍ  のように定義し、前記グループ２に属するフロー｛Ｇ１、Ｇ２、……、Ｇｊ｝に対する重み付け係数｛Ｖ１、Ｖ２、……、Ｖｊ｝をＶ１＝α×Ｌ１／Ｌｓｕｍ  ＋（１−α）×Ｎ１／Ｎｓｕｍ  、Ｖ２＝α×Ｌ２／Ｌｓｕｍ  ＋（１−α）×Ｎ２／Ｎｓｕｍ  、……、Ｖｊ＝α×Ｌｊ／Ｌｓｕｍ  ＋（１−α）×Ｎｊ／Ｎｓｕｍ  のように定義し、前記パラメータαを外部から設定可能であることを特徴とする。
【００１３】
そして、まず第４の発明において、パケットの出力インタフェース速度をＣとし、グループ１に属するフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝について測定した転送レートを｛Ｒ１、Ｒ２、……Ｒｉ｝、その合計をＲｓｕｍ  とし、グループ２に属するフロー｛Ｇ１、Ｇ２、……Ｇｊ｝について測定した転送レートを｛Ｔ１、Ｔ２、……Ｔｊ｝、その合計をＴｓｕｍ  とする。
そして、この場合、条件Ｃ＞（Ｒｓｕｍ  ＋Ｔｓｕｍ  ）が成立すれば、最大制限レート以下で、パケットを転送中の全てのフローに対して十分な帯域があるため、グループ１、グループ２に属するフローに関して受信したパケットは即時に転送する。
【００１４】
次に、条件Ｒｓｕｍ  ≦Ｃ≦（Ｒｓｕｍ  ＋Ｔｓｕｍ  ）が成立する場合は、まずグループ１に属するフローに関しては十分な帯域があるため、受信したパケットは即時に転送する。
また、グループ２に属するフローに関しては、割り当てることのできる余剰帯域（Ｃ−Ｋｓｕｍ  ）を各フローの最低保証レートを基に算出した重み付け係数｛Ｗ１、Ｗ２、……、Ｗｊ｝に比例する形で再配分し、グループ２のフローをパケット転送レートが｛（Ｃ−Ｋｓｕｍ  ）×Ｖ１、（Ｃ−Ｋｓｕｍ  ）×Ｖ２、……、（Ｃ−Ｋｓｕｍ  ）×Ｖｊ｝未満のグループ２Ａと、パケット転送レートが｛（Ｃ−Ｋｓｕｍ  ）×Ｖ１、（Ｃ−Ｋｓｕｍ  ）×Ｖ２、……、（Ｃ−Ｋｓｕｍ  ）×Ｖｊ｝以上のグループ２Ｂとに分類し、グループ２Ａに属するフローに関して受信したパケットをグループ２Ｂに属するフローに関して受信したパケットに優先して転送する。
このように余剰帯域の再配分を行なうことにより、パケットの転送レートが最低保証レート以上、最大制限レート未満のフローについても、余剰帯域を各フローの最低保証レートに応じて公平に割り当てることができる。
【００１５】
また、条件Ｃ＜Ｒｓｕｍ  が成立する場合は、グループ１に属するフローに関しても十分な帯域が確保できないため、最低保証レートを守ることができないことになる。
本来は、このような事態が生じないように、新規フローの受け付け制御を行なうべきであるが、一時的なトラフィックの急増によって、Ｃ＜Ｒｓｕｍ  になった場合は、全帯域を各フローの最低保証レートに応じて再配分する。
この再配分の方法は、グループ１のフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝をパケット転送レートが｛Ｃ×Ｗ１、Ｃ×Ｗ２、……、Ｃ×Ｗｉ｝未満のグループ１Ａと、パケット転送レートが｛Ｃ×Ｗ１、Ｃ×Ｗ２、……、Ｃ×Ｗｉ｝以上のグループ１Ｂとに分類し、グループ１Ａに属するフローに関して受信したパケットをグループ１Ｂに属するフローに関して受信したパケットに優先して転送することによって行なう。
以上のように、この第４の発明によれば、最低保証レートの契約値に基き、各フローに対して余剰帯域の再配分を行なうことが可能となる。
この第４の発明は、網運用事業者が加入者に対して提供するサービスのコストが最低保証レートに応じたものになっている場合に適する。
【００１６】
また、第５の発明のパケット転送レート監視制御装置では、グループ１に属するフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝に対する重み付け係数｛Ｗ１、Ｗ２、……、Ｗｊ｝、およびグループ２に属するフロー｛Ｇ１、Ｇ２、……、Ｇｊ｝に対する重み付け係数｛Ｖ１、Ｖ２、……Ｖｊ｝を、第４の発明のように各フローの最低保証レートではなく、各フローの最大制限レートを基に決めるものである。
従って、最大制限レートの契約値に基き、各フローに対して余剰帯域の再配分を行なうことが可能となる。
この第５の発明は、網運用事業者が加入者に対して提供するサービスのコストが最大制限レートに応じたものになっている場合に適する。
【００１７】
また、第６の発明のパケット転送レート監視制御装置では、０から１までの値をとるパラメータαを用いて上述した第４の発明や第５の発明の重み付け係数を定義する。
このパラメータαは、網運用事業者の課金体系や運用方針等に基づき、パケット転送レート監視制御装置の外部から設定可能とする。この第６の発明によれば、網運用事業者が最低保証レートの契約値と最大制限レートの契約値の両方に基づいて余剰帯域の再配分を行なうことが可能である。
【００１８】
また、第７の発明のパケット転送レート監視制御装置は、受信パケットのヘッダ情報からトランスポート層のプロトコル種別を識別するプロトコル種別識別手段を備え、パケット転送レートが前記最大制限レートを超過した場合、前記プロトコル種別識別手段によって識別したトランスポート層のプロトコルに応じて、受信したパケットを廃棄するか、あるいは受信したパケットの転送をパケット転送レートが前記最大制限レート以下になるまで遅延させてシェーピングを行なうかを選択することを特徴とする。
例えばトランスポート層のプロトコル種別がＴＣＰの場合、最大制限レートを超過したフローのパケットを連続的に廃棄してしまうと、Ｗ．  Ｒｉｃｈａｒｄ  Ｓｔｅｖｅｎｓによる「ＴＣＰ／ＩＰ  Ｉｌｌｕｓｔｒａｔｅｄ  ｖｏｌ．１」（Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ）の第２０章６節に記載されているように、エンドシステムがパケットの送信を再開した後、徐々に転送レートをあげるスロースタートを行なうため、実際のパケット転送レートが常に最大制限レートを大きく下回るような問題が発生する場合がある。
この問題は、最大制限レート超過時にパケットを廃棄せず、シェーピングを行なうことによって回避可能であるが、全てのトランスポート層プロトコルがこのようなスロースタートを行なうわけではないので、常にシェーピングを行なうとシェーピング用のバッファを無駄に消費することになる。
そこで、この第７の発明のように、トランスポート層プロトコルに応じてパケット廃棄とシェーピングを切り替えるようにすれば、最大制限レートの制約を正確に行なうだけでなく、シェーピング用のバッファを節約することができる。
【００１９】
また、第８の発明のパケット転送レート監視制御装置では、受信パケットのヘッダ情報からトランスポート層のプロトコル種別を識別するプロトコル種別識別手段を備え、前記プロトコル種別識別手段によって識別したトランスポート層プロトコルがＴＣＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ  ）であり、かつパケット転送レートが前記最大制限レートを超過した場合には、転送するパケットのヘッダにＲＦＣ２４８１で定義されるＣＥ（Ｃｏｎｇｅｓｔｉｏｎ  Ｅｘｐｅｒｉｅｎｃｅｄ）ビットを付加することにより、送信側ノードに対して送信レートの抑制を通知することを特徴とする。
ＲＦＣ２４８１に記載されているように、ヘッダ情報にＣＥビットが付加されたパケットを受信側ノードが受信すると、送信側ノードに対する確認応答（ＡＣＫ）パケットのヘッダ情報にＥＣＮーｅｃｈｏフラグをセットして送信する。
送信側ノードでは、このＥＣＮーｅｃｈｏフラグがヘッダ情報にセットされたパケットを受信して送信レートを下げるため、パケット転送装置は例えば第７の発明におけるパケット廃棄やシェーピングを行なわずとも、パケット転送レートを最大制限レートで制約することができる。
但し、この第８の発明を適用するためには、送信ノード、受信ノードのＴＣＰが共にＲＦＣ２４８１をサポートしている必要がある。
【００２０】
また、第９の発明のパケット転送レート監視制御装置では、受信パケットのヘッダ情報からトランスポート層のプロトコル種別を識別するプロトコル種別識別手段を備え、前記プロトコル種別識別手段によって識別したトランスポート層プロトコルがＴＣＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ  ）であり、かつパケット転送レートが前記最大制限レートを超過した場合には、以後、受信側ノードから送信側ノードに向けて転送する確認応答パケットのＴＣＰヘッダにおける受信ウィンドウサイズを０に上書きし、送信側ノードに対して送信レートの抑制を通知することを特徴とする。
これにより、送信側ノードがＴＣＰの確認応答パケットを受信した場合、その受信ウィンドウサイズが０であった場合には、受信側ノードのバッファが枯渇したものとみなし、送信を一時停止する。
以後、Ｗ．  Ｒｉｃｈａｒｄ  Ｓｔｅｖｅｎｓによる「ＴＣＰ／ＩＰ  Ｉｌｌｕｓｔｒａｔｅｄ  ｖｏｌ．１」（Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ）の第２２章に記載されているように、送信側ノードはＴＣＰのＰｅｒｓｉｓｔ  タイマを起動し、周期的に受信側ノードの受信ウィンドウサイズをプローブして、受信ウィンドウサイズが十分大きくなると送信を再開する。
パケット転送装置は、パケット転送レートが最大制限レート未満になると、確認応答パケットにおける受信ウィンドウサイズの上書きを停止するので、パケット転送レートを最大制限レートで制約することができる。
【００２１】
また、第１０の発明は、可変長パケットのルーティングを行なうパケット転送装置のパケット転送レート監視制御方法において、受信パケットからその受信パケットが属する上位レイヤのフローを識別するとともに、その受信パケットの転送間隔と受信パケット長からパケット転送レートを測定し、その測定したパケット転送レートと予めフロー毎に設定されたレート情報とを比較して各受信パケットを転送する優先順位を決定することにより、パケット転送レートが最低保証レート以上であるフローに関して受信したパケットより優先して転送し、かつ、パケット転送レートが最大制限レート未満であるフローに関して受信したパケットをパケット転送レートが最大制限レート以上であるフローに関して受信したパケットよりも優先して転送するようにしたことを特徴とする。
したがって第１０の発明によれば、加入者が利用するサービス毎にパケット転送の最低保証レートと最大制限レートを契約するパケット通信網において、トラフィック増加時にも最低保証レート以上のパケット転送速度を保証することが可能となる。
【００２２】
また、第１１の発明は、第１０の発明をさらに具体化し、受信パケットのヘッダ情報から受信パケットが属する上位レイヤのフローを識別する上位レイヤフロー識別手順と、前記上位レイヤフロー識別手順によって識別したフロー毎に受信パケットの転送間隔と受信パケット長からパケット転送レートを測定するパケット転送レート測定手順と、前記パケット転送レート測定手順によって測定したパケット転送レートと予めフロー毎に設定された最低保証レート情報および最大制限レート情報とを比較する比較手順と、前記比較手順によって比較した結果に基いて、受信パケットに対応するフローを、パケット転送レートが前記最低保証レート未満であるフローが属するグループ１と、パケット転送レートが前記最低保証レート以上であり、かつ前記最大制限レート未満であるフローが属するグループ２と、パケット転送レートが前記最大制限レートを超過したフローが属するグループ３とに分類する分類手順と、前記グループ１が属するフローに関して受信したパケットを前記グループ２に属するフローに関して受信したパケットに優先して転送し、かつ前記グループ２が属するフローに関して受信したパケットを前記グループ３に属するフローに関して受信したパケットに優先して転送する転送制御手順とを有することを特徴とする。
【００２３】
このように、パケット転送レートに応じてフローを３段階のグループに分類することにより、常に最低保証レート未満のフローに対するパケット転送を優先させることができるため、一時的にトラフィックが増加した場合にも全てのフローの最低保証レートを守ることができる。
なお、フローが属するグループは固定的ではなく、パケット転送レートに応じて時間とともに変動する。
従って、グループ１に属するフローに対する受信パケットを優先的に転送したためにグループ２に属するフローに対する受信パケットの転送がしばらく行なわれなかった場合は、グループ２に属するフローのパケット転送レートが低下し、これが最低保証レートを下回るとフローがグループ１に属するようになる。このようにして、最低保証レートを一時的に超過したフローに対しても、最低保証レートの契約値以上のパケット転送を行なうことができる。
【００２４】
また、第１２の発明は、可変長パケットのルーティングを行なうパケット転送装置を制御するコンピュータの動作を制御するプログラムにおいて、受信パケットのヘッダ情報から受信パケットが属する上位レイヤのフローを識別する上位レイヤフロー識別手順と、前記上位レイヤフロー識別手順によって識別したフロー毎に受信パケットの転送間隔と受信パケット長からパケット転送レートを測定するパケット転送レート測定手順と、前記パケット転送レート測定手順によって測定したパケット転送レートと予めフロー毎に設定された最低保証レート情報および最大制限レート情報とを比較する比較手順と、前記比較手順によって比較した結果に基いて、受信パケットに対応するフローを、パケット転送レートが前記最低保証レート未満であるフローが属するグループ１と、パケット転送レートが前記最低保証レート以上であり、かつ前記最大制限レート未満であるフローが属するグループ２と、パケット転送レートが前記最大制限レートを超過したフローが属するグループ３とに分類する分類手順と、前記グループ１が属するフローに関して受信したパケットを前記グループ２に属するフローに関して受信したパケットに優先して転送し、かつ前記グループ２が属するフローに関して受信したパケットを前記グループ３に属するフローに関して受信したパケットに優先して転送する転送制御手順とをコンピュータに実行させることを特徴とする。
【００２５】
このようなプログラムによってパケット転送装置を制御するコンピュータを動作させることで、パケット転送レートに応じてフローを３段階のグループに分類することにより、常に最低保証レート未満のフローに対するパケット転送を優先させることができるため、一時的にトラフィックが増加した場合にも全てのフローの最低保証レートを守ることができる。
なお、フローが属するグループは固定的ではなく、パケット転送レートに応じて時間とともに変動する。
従って、グループ１に属するフローに対する受信パケットを優先的に転送したためにグループ２に属するフローに対する受信パケットの転送がしばらく行なわれなかった場合は、グループ２に属するフローのパケット転送レートが低下し、これが最低保証レートを下回るとフローがグループ１に属するようになる。このようにして、最低保証レートを一時的に超過したフローに対しても、最低保証レートの契約値以上のパケット転送を行なうことができる。
【００２６】
【発明の実施の形態】
以下、本発明によるパケット転送レート監視制御装置、方法、及びプログラムの実施の形態について説明する。
なお、以下に説明する実施の形態は、本発明の好適な具体例であり、技術的に好ましい種々の限定が付されているが、本発明の範囲は、以下の説明において、特に本発明を限定する旨の記載がない限り、これらの態様に限定されないものとする。
【００２７】
図１は、本発明の第１の実施の形態を適用したパケット転送装置を含むパケット通信網の一例を示すブロック図である。
以下、このパケット通信網の概要について説明する。
まず、パケット転送装置１０はインタフェース６０、７０を介して、それぞれパケット通信網４０、パケット通信網５０に接続されている。
また、送信ノード２０は、インタフェース８０を介してパケット通信網４０に接続され、受信ノード３０は、インタフェース９０を介してパケット通信網５０に接続される。そして、送信ノード２０は受信ノード３０に向けてデータパケット１００を出力し、パケット転送装置１０はインタフェース６０からこのデータパケット１００を受信する。
パケット転送装置１０は、入力されたデータパケット１００に対し、パケットのヘッダ情報に基きルーティング処理を行ない、必要に応じてパケットのヘッダ情報を書き換えた後、インタフェース７０からデータパケット１０１を出力する。受信ノード３０は、このデータパケット１０１を受信すると、確認応答（ＡＣＫ）パケット２００を送信ノード２０に向けて返送する。
確認応答パケット２００は、パケット転送装置１０において中継され、送信ノード１０は確認応答パケット２０１を受信する。
【００２８】
図２は、本発明の第１の実施の形態におけるパケット転送装置１０の構成を詳細に示すブロック図である。
パケット転送装置１０は、インタフェース６０からデータパケット１００を受信すると、パケットルーティング手段３００に出力する。
パケットルーティング手段３００は、入力されたデータパケット１０２のヘッダ情報を基にルーティングデータベース３０１を検索し、出力インタフェース７０を決定すると共に、必要に応じてデータパケットのヘッダ情報を書き換え、フロー識別手段３０２に出力する。
フロー識別手段３０２は、データパケット１０３のヘッダ情報を基にフロー識別データベース３０３を検索し、受信データパケットに対応する上位レイヤのフローを識別する。
【００２９】
パケット転送レート測定手段３０４は、識別したフロー毎に測定したパケット転送レートの測定値を記憶し、最低保証レート記憶手段３０５及び最大制限レート記憶手段３０６に問い合わせを行ない、パケット転送レートが最低保証レート未満か、最低保証レート以上、最大制限レート未満か、または最大制限レート以上であるかを判定する。
フロー識別手段３０２は、識別したフロー毎に用意されたキューに、パケットを到着順に挿入（キューイング）する。
このフロー毎のキューは、パケット転送レートが最低保証レート未満のキュー｛Ｑ１１、Ｑ１２、……、Ｑ１ｉ｝からなるキューグループ（グループ１）４０１と、最低保証レート以上かつ最大制限レート未満のキュー｛Ｑ２１、Ｑ２２、……、Ｑ２ｉ｝からなるキューグループ（グループ２）４０２と、最大制限レート以上のキュー｛Ｑ３１、Ｑ３２、……、Ｑ３ｈ｝からなるキューグループ（グループ３）４０３に分類する。
【００３０】
そして、キューから転送するパケットを取り出す際は、まずこのキューグループ単位で、取り出すキューを選択する。
この場合、キュー選択手段３０７、３０８、３０９は、それぞれキューグループ４０１、４０２、４０３に属するフロー毎のキューを選択する。
このキュー選択手段３０７、３０８、３０９におけるキュー選択方法は、単純なラウンドロビン式で行なっても良いし、フロー毎の最低保証レート、最大制限レート、パケット転送レート測定値を基に転送予定時刻を管理し、転送予定時刻の最も小さなフローのキューからパケットを取り出すようにしても良い。
【００３１】
また、キューグループ選択手段３１０は、キュー選択手段３０７、３０８、３０９によって選択された３つのキューの内、いずれかを選択する。
このキューグループ選択手段３１０におけるキューの選択は、キュー選択手段３０７によって選択されたキューをキュー選択手段３０８によって選択されたキューに対して優先し、キュー選択手段３０８によって選択されたキューをキュー選択手段３０９によって選択されたキューに対して優先する。
従って、パケット転送レートが最低保証レート以下のフロー毎のキューは、パケット転送レートが最低保証レート以上で最大制限レート未満のフロー毎のキューに対して優先して選択される。
また、パケット転送レートが最低保証レート以上で最大制限レート未満のフロー毎のキューは、パケット転送レートが最大制限レート以上のキューに対して優先して選択される。
【００３２】
次に、キューグループ選択手段３１０は、このようにして選択されたフロー毎のキューの先頭からデータパケット１０４を取り出し、フロー毎のパケット転送レートを測定してパケット転送レート測定手段３０４に格納された情報を更新する。取り出したデータパケット１０４はインタフェース７０から出力する。
なお、各々のフローが属するキューグループは随時パケット転送レートを行なう毎に変動し、同一フローに対して連続してパケット転送を行なった結果、パケット転送レートが上昇した場合は、フロー毎のキューをキューグループ４０１から４０２へ、あるいはキューグループ４０２から４０３へと移動させる。逆に同一フローに対してしばらくパケットが転送できなかった結果、パケット転送レートが低下した場合は、フロー毎のキューをキューグループ４０２から４０１へ、あるいはキューグループ４０３から４０２へと移動させる。
このように本実施の形態によれば、パケットの転送レートに応じてフローを３種類のグループに分類することにより、最低保証レート未満で送信するフローに対する受信パケットを常に優先して転送できるので、一時的にトラフィックが増えた場合にも最低保証レートでの転送が保証可能になる。
【００３３】
図３は、本発明の第１の実施の形態におけるフロー識別データベース３０３、パケット転送レート測定手段３０４、最低保証レート記憶手段３０５、最大制限レート記憶手段３０６のデータ構造を示す説明図である。
フロー識別データベース３０３は、送信元ＩＰアドレス５４０、宛先ＩＰアドレス５４１、トランスポート層プロトコル５４２、送信元ポート番号５４３、宛先ポート番号５４４等のパケットヘッダに関する情報を保持し、対応するフロー識別子５０３へのマッピングを行なう。
また、パケット転送レート測定手段３０４は、識別したフロー毎にフロー識別子５０２、測定したパケット転送レート５３０、フローが属するキューグループ５３１、そのフローに関して最後にパケットを転送した最終転送時刻５３２、キューイング中のパケット数５３３からなる情報を保持し、パケットの転送時にこれらの情報を更新する。
最低保証レート記憶手段３０５、最大制限レート記憶手段３０６は、それぞれフロー識別子５００、５０１に対応する最低保証レート５１０、最大制限レート５２０を保持する。
このようなデータ構造を用いて上述したパケット転送動作を制御することが可能である。
【００３４】
次に本発明の他の実施の形態について説明する。
図４は、本発明の第２の実施の形態におけるパケット転送装置１１の構成を示すブロック図である。
この第２の実施の形態では、パケット転送レートが最低保証レート未満のキューのグループを４０１ａと４０１ｂに分類し、パケット転送レートが最低保証レート以上最大制限レート以下のキューのグループを４０２ａと４０２ｂに分類する。この分類は以下の様にして行なう。
【００３５】
まず、パケット転送レート測定手段３１１は、パケット転送レートが最低保証レート未満のフロー｛Ｆ１、Ｆ２、……、Ｆｉ｝に対して測定したパケット転送レート｛Ｒ１、Ｒ２、……、Ｒｉ｝の合計値Ｒｓｕｍ  と、パケット転送レートが最低保証レート以上最大制限レート未満のフロー｛Ｇ１、Ｇ２、……、Ｇｉ｝に対して測定したパケット転送レート｛Ｔ１、Ｔ２、……、Ｔｉ｝の合計値Ｔｓｕｍ  とを保持する。
また、最低保証レート記憶手段３１２は、フロー｛Ｆ１、Ｆ２、……、Ｆｉ｝に対して予め設定された最低保証レート｛Ｋ１、Ｋ２、……、Ｋｉ｝の合計値Ｋｓｕｍ  と、フロー｛Ｇ１、Ｇ２、……、Ｇｊ｝に対して予め設定された最低保証レート｛Ｌ１、Ｌ２、……、Ｌｉ｝の合計値Ｌｓｕｍ  を保持し、フロー｛Ｆ１、Ｆ２、……、Ｆｉ｝に対する重み付け係数｛Ｗ１、Ｗ２、……、Ｗｊ｝をＷ１＝Ｋ１／Ｋｓｕｍ  、Ｗ２＝Ｋ２／Ｋｓｕｍ  、……、Ｗｊ＝Ｋｊ／Ｋｓｕｍ  のように計算し、フロー｛Ｇ１、Ｇ２、……、Ｇｊ｝に対する重み付け係数｛Ｖ１、Ｖ２、……、Ｖｊ｝をＶ１＝Ｌ１／Ｌｓｕｍ  、Ｖ２＝Ｌ２／Ｌｓｕｍ  、……、Ｖｊ＝Ｌｊ／Ｌｓｕｍ  のように計算して保持する。
【００３６】
次に、フロー｛Ｆ１、Ｆ２、……、Ｆｉ｝に対するキュー｛Ｑ１１、Ｑ１２、……、Ｑ１ｉ｝は、パケットの出力インタフェース７０のインタフェース速度をＣとした場合、パケット転送レートが｛Ｃ×Ｗ１、Ｃ×Ｗ２、……、Ｃ×Ｗｉ｝未満のキューグループ４０１ａと、パケット転送レートが｛Ｃ×Ｗ１、Ｃ×Ｗ２、……、Ｃ×Ｗｉ｝以上のキューグループ４０１ｂとに分類し、フロー｛Ｇ１、Ｇ２、……、Ｇｊ｝に対するキュー｛Ｑ２１、Ｑ２２、……、Ｑ２ｊ｝は、パケット転送レートが｛（Ｃ−Ｋｓｕｍ  ）×Ｖ１、（Ｃ−Ｋｓｕｍ  ）×Ｖ２、……、（Ｃ−Ｋｓｕｍ  ）×Ｖｊ｝未満のキューグループ４０２ａと、パケット転送レートが｛（Ｃ−Ｋｓｕｍ  ）×Ｖ１、（Ｃ−Ｋｓｕｍ  ）×Ｖ２、……、（Ｃ−Ｋｓｕｍ  ）×Ｖｊ｝以上のキューグループ４０２ｂとに分類する。
【００３７】
ここで、キューグループ選択手段３１０はキューグループ４０１ａに属するキューをキューグループ４０１ｂに属するキューに優先して選択し、キューグループ４０２ａに属するキューをキューグループ４０２ｂに属するキューに優先して選択する。このように出力キューの選択を行なった場合、受信パケットの転送は入力されるトラフィックの量に応じて次のようになる。
（１）条件Ｃ＜（Ｒｓｕｍ  ＋Ｔｓｕｍ  ）が成立する場合
この場合、最大制限レート以下でパケットを転送中のすべてのフローに対して十分な帯域があるため、キューグループ４０１ａ、４０１ｂ、４０２ａ、４０２ｂに属するフローに関して受信したパケットは即時に転送される。
【００３８】
（２）条件Ｒｓｕｍ  ≦Ｃ≦（Ｒｓｕｍ  ＋Ｔｓｕｍ  ）が成立する場合
この場合、キューグループ４０１ａ、４０１ｂに属するフローに関しては十分な帯域があるため、受信したパケットは即時に転送される。
キューグループ４０２ａに属するフローに関して受信したパケットは、キューグループ４０２ｂに属するフローに関して受信したパケットに優先して転送される。
なお、第１の実施の形態と同様に、同一のフローに対して連続してパケット転送を行なった結果、パケット転送レートが上昇した場合には、フロー毎のキューをキューグループ４０２ａから４０２ｂ、４０３へと移動させる。
逆に同一フローに対してしばらくパケットが転送できなかった結果、パケット転送レートが低下した場合は、フロー毎のキューをキューグループ４０３から４０２ｂへ、あるいは４０２ｂから４０２ａへと移動させる。
このようにパケット転送レートが最低保証レート以上最大制限レート未満のフローに関するパケットキューをパケット転送レートに応じて２つのグループに分類することにより、各フローの最低保証帯域に応じて余剰帯域を公平に分配することができる。
【００３９】
（３）条件Ｃ＜Ｒｓｕｍ  が成立する場合
この場合、キューグループ４０１ａ、４０１ｂに属するフローに関しても十分な帯域が確保できないため、最低保証レートを守ることができない。
各フローに対して予約する最低保証帯域の合計が回線レートを上回ることを認めた場合、一時的に入力トラフィック量が増大すると、このような状況が発生する。
キューグループ４０１ａに属するフローに関して受信したパケットは、キューグループ４０１ｂに属するフローに関して受信したパケットに優先して転送される。従って、パケット転送レートが最低保証レート未満のフローに対し、各フローの最低保証帯域に応じて出力回線の全帯域（Ｃ）を公平に分配することができる。
以上のように、本発明の第２の実施の形態によれば、各フローの最低保証レートの契約値に基き、各フローに対して余剰帯域の再配分を行なうことが可能となる。
本実施の形態は、網運用事業者が加入者に対して提供するサービスのコストが最低保証レートに応じたものになっている場合に適している。
【００４０】
次に、本発明の第３の実施の形態について説明する。
この第３の実施の形態におけるパケット転送装置の構成は、上述した第２の実施の形態におけるパケット転送装置１１の構成と同様である。
また、この第３の実施の形態における最大制限レート記憶手段３１３は、フロー｛Ｆ１、Ｆ２、……、Ｆｉ｝に対して予め設定された最大制限レート｛Ｍ１、Ｍ２、……、Ｍｉ｝の合計値Ｍｓｕｍ  と、フロー｛Ｇ１、Ｇ２、……、Ｇｊ｝に対して予め設定された最大制限レート｛Ｎ１、Ｎ２、……、Ｎｉ｝の合計値Ｎｓｕｍ  を保持し、フロー｛Ｆ１、Ｆ２、……、Ｆｉ｝に対する重み付け係数｛Ｗ１、Ｗ２、……、Ｗｊ｝をＷ１＝Ｍ１／Ｍｓｕｍ  、Ｗ２＝Ｍ２／Ｍｓｕｍ  、……、Ｗｊ＝Ｍｊ／Ｍｓｕｍ  のように計算し、フロー｛Ｇ１、Ｇ２、……、Ｇｊ｝に対する重み付け係数｛Ｖ１、Ｖ２、……、Ｖｊ｝をＶ１＝Ｎ１／Ｎｓｕｍ  、Ｖ２＝Ｎ２／Ｎｓｕｍ  、……、Ｖｊ＝Ｎｊ／Ｎｓｕｍ  のように計算して保持する。
【００４１】
キュー｛Ｑ１１、Ｑ１２、……、Ｑ１ｉ｝は、上述のように最大制限レートを基にして決めた重み付け係数｛Ｗ１、Ｗ２、……、Ｗｉ｝を基にキューグループ４０１ａと４０１ｂに分類し、キュー｛Ｑ２１、Ｑ２２、……、Ｑ２ｊ｝は上記のように最大制限レートを基にして決めた重み付け係数｛Ｖ１、Ｖ２、……、Ｖｊ｝を基にキューグループ４０２ａと４０２ｂに分類する。
以後、第２の実施の形態と同様に、キューグループ選択手段３１０はキューグループ４０１ａに属するキューを、キューグループ４０１ｂに属するキューに優先して選択し、また、キューグループ４０２ａに属するキューを、キューグループ４０２ｂに属するキューに優先して選択する。
このように出力キューの選択を行なうことにより、各フローの最大制限レートの契約値に基き、各フローに対して余剰帯域の再配分を行なうことが可能となる。
本実施の形態は、網運用事業者が加入者に対して提供するサービスのコストが最大制限レートに応じたものになっている場合に適している。
【００４２】
なお、本発明の第２の実施の形態および第３の実施の形態において、余剰帯域の分配に用いる重み付け係数｛Ｗ１、Ｗ２、……、Ｗｉ｝、｛Ｖ１、Ｖ２、……、Ｖｊ｝の計算方法は必ずしも上述した方法の限りではない。
例えば、網運用者がサービスの最低保証レートと最大制限レートの契約値の双方に基づき、余剰帯域の分配方針を決めようとする場合には、パケット転送装置の外部より、０から１までの範囲でパラメータαを与え、このパラメータαを用いて、
Ｗ１＝α×Ｋ１／Ｋｓｕｍ  ＋（１−α）×Ｍ１／Ｍｓｕｍ  、Ｗ２＝α×Ｋ２／Ｋｓｕｍ  ＋（１−α）×Ｍ２／Ｍｓｕｍ  、……、Ｗｉ＝α×Ｋｉ／Ｋｓｕｍ  ＋（１−α）×Ｍｉ／Ｍｓｕｍ  、
および、
Ｖ１＝α×Ｌ１／Ｌｓｕｍ  ＋（１−α）×Ｎ１／Ｎｓｕｍ  、Ｖ２＝α×Ｌ２／Ｌｓｕｍ  ＋（１−α）×Ｎ２／Ｎｓｕｍ  、……、Ｖｊ＝α×Ｌｊ／Ｌｓｕｍ  ＋（１−α）×Ｎｊ／Ｎｓｕｍ
のように計算する方法が挙げられる。
【００４３】
次に、本発明の第４の実施の形態について説明する。
図５は、この第４の実施の形態におけるパケット転送レート測定手段３１４のデータ構造を示す説明図である。
上述した第１の実施の形態と同様に、フロー毎にパケット転送レート５３４、キューグループ５３５、最終転送時刻５３６、キューイング中パケット数５３７を保持し、加えてフロー毎に最大制限レート超過時の処理方法５３８を保存している。
最大制限レート超過時の処理方法としては、トラフィックのシェーピング（Ｓｈａｐｅ）  、受信したパケットの廃棄（Ｄｒｏｐ）、パケットの確率的な廃棄（Ｒａｎｄｏｍ−Ｄｒｏｐ）  等がある。
さらに、トランスポート層プロトコルがＴＣＰの場合、上記の処理方法に加えて、パケットヘッダへのＣｏｎｇｅｓｔｉｏｎ  Ｅｘｐｅｒｉｅｎｄビットの付加（ＥＣＮ）  、確認応答パケットの受信ウィンドウサイズの０上書き（Ｚｅｒｏ−Ｗｉｎｄｏｗ）  を指定することもできる。
【００４４】
この最大制限レート超過時の処理方法５３８は、フロー識別データベース３０３に格納されたフロー識別条件における、トランスポート層プロトコル５４２に基いて決める。
例えば、トランスポート層プロトコルがＵＤＰの場合は最大制限レート超過時処理方法を（Ｄｒｏｐ）とし、トランスポート層プロトコルがＴＣＰの場合は、Ｓｈａｐｅ  、（Ｓｈａｐｅ、ＥＣＮ）  、またはＲａｎｄｏｍ−Ｄｒｏｐ  のようにする。
トランスポート層プロトコルがＴＣＰで最大制限レート超過時にＣｏｎｇｅｓｔｉｏｎ  Ｅｘｐｅｒｉｅｎｄビットの付加を行なった場合、受信ノードは送信ノードに対して返送する確認応答パケットにおいて、パケット転送の経路中で輻輳が発生したことを送信ノードに通知するため、送信ノードは最大制限レート以下になるまで送信レートを自動的に低減する。
【００４５】
また、トランスポート層プロトコルがＴＣＰの場合、最大制限レート超過時に受信ノードから返送される確認応答パケットにおける受信ウィンドウサイズを０に上書きすると、送信ノードは以後のパケット送信を一時的に停止する。
以後、送信ノードはＴＣＰのＰｅｒｓｉｓｔ  タイマを起動し、受信ウィンドウサイズが十分大きくなるまで周期的に受信ノードの受信ウィンドウサイズをプローブする。
パケット転送装置は、パケット転送レートが最大制限レート未満になると、確認応答パケットにおける受信ウィンドウサイズの上書きを停止するため、パケット転送レートを最大制限レートに抑えることができる。このように、最大制限レート超過時の処理方法を、フロー識別条件のトランスポート層プロトコルに基き選択することにより、シェーピングに必要なバッファを削減し、またシェーピングに必要な処理負荷を軽減することができる。
【００４６】
なお、本発明は以上のような各構成のパケット転送装置に含まれるパケット転送レート監視制御装置とともに、上述した各手順より構成されるパケット転送レート監視制御方法、及びパケット転送装置を制御するＣＰＵ等の各コンピュータに上述した各手順を実行させるためのプログラムを含むものである。
【００４７】
【発明の効果】
以上説明したように本発明のパケット転送レート監視制御装置によれば、加入者が利用するサービス毎にパケット転送の最低保証レートと最大制限レートを契約するパケット通信網において、トラフィック増加時にも最低保証レート以上のパケット転送速度を保証することができ、さらに、最低保証レート以上のパケット転送速度を保証しつつ、契約した最低保証レートや最大制限レートに応じて余剰帯域の再配分を簡易かつ公平に行なうことも可能となる。
【００４８】
また、本発明のパケット転送レート監視制御方法おいても同様に、加入者が利用するサービス毎にパケット転送の最低保証レートと最大制限レートを契約するパケット通信網において、トラフィック増加時にも最低保証レート以上のパケット転送速度を保証することができ、さらに、最低保証レート以上のパケット転送速度を保証しつつ、契約した最低保証レートや最大制限レートに応じて余剰帯域の再配分を簡易かつ公平に行なうことも可能となる。
【００４９】
さらに、本発明のプログラムによってパケット転送装置のコンピュータを動作させることにより、加入者が利用するサービス毎にパケット転送の最低保証レートと最大制限レートを契約するパケット通信網において、トラフィック増加時にも最低保証レート以上のパケット転送速度を保証しつつ、契約した最低保証レートや最大制限レートに応じて余剰帯域の再配分を簡易かつ公平に行なうことも可能となる。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態を適用したパケット転送装置を含むパケット通信網の一例を示すブロック図である。
【図２】本発明の第１の実施の形態におけるパケット転送装置の構成を詳細に示すブロック図である。
【図３】本発明の第１の実施の形態におけるフロー識別データベース、パケット転送レート測定手段、最低保証レート記憶手段、最大制限レート記憶手段のデータ構造を示す説明図である。
【図４】本発明の第２の実施の形態におけるパケット転送装置の構成を示すブロック図である。
【図５】本発明の第４の実施の形態におけるパケット転送レート測定手段のデータ構造を示す説明図である。
【符号の説明】
１０、１１……パケット転送装置、２０……送信ノード、３０……受信ノード、４０、５０……パケット通信網、６０、７０……インタフェース、８０、９０……インタフェース、３００……パケットルーティング手段、３０１……ルーティングデータベース、３０２……フロー識別手段、３０３……フロー識別データベース、３０４……パケット転送レート測定手段、３０５……最低保証レート記憶手段、３０６……最大制限レート記憶手段、３０７、３０８、３０９……キュー選択手段、３１０……キューグループ選択手段。
【図１】
0003558044.tif 000002
【図２】
0003558044.tif 000003
【図３】
0003558044.tif 000004
【図４】
0003558044.tif 000005
【図５】
0003558044.tif 000006