(57)【要約】【課題】可変長フレームの所属フロー別に最低保証帯域を保証し、最大許容帯域の範囲内で空き帯域を有効利用可能にしたシェーピング装置の提供。【解決手段】フロー別に用意された複数のバッファメモリと、各バッファメモリに付随する帯域制御部と、読出し制御部とからなり、各帯域制御部が、最大許容帯域に基く第１のフレーム排出要求と、最低保証帯域に基く第２のフレーム排出要求と発行し、読出し制御部が、第２のフレーム排出要求を優先させて、フレーム排出要求を発行中の帯域制御部の中から排出許可すべき帯域制御部を選択するようにしたシェーピング装置。【選択図】  図３
2005333544.tif 000002
【特許請求の範囲】
【請求項１】
出力回線に接続された出力回線インタフェースと、
それぞれ特定のフローに属した可変長フレームを一時的に蓄積し、予め設定された最大許容帯域と最低保証帯域に従って蓄積フレームの出力タイミングを決定する複数のフロー制御部と、
上記複数のフロー制御部に接続された読出し制御部と、
上記出力回線に出力すべき可変長フレームの所属フローを識別し、所属フローと対応した上記何れかのフロー制御部に各可変長フレームを振り分けるフレーム振り分け部とからなり、
上記各フロー制御部が、
フロー毎に予め設定された最大許容帯域に基いて決定したフレーム排出タイミングで、上記読出し制御部に最大許容帯域フレーム排出要求を発行する第１の排出タイミング判定部と、
フロー毎に予め設定された最低保証帯域に基いてフレーム排出タイミングを決定し、上記第１の排出タイミング判定部から最大許容帯域フレーム排出要求が発行されていることを条件として、上記読出し制御部に最低保証帯域フレーム排出要求を発行する第２の排出タイミング判定部と、
上記読出し制御部から受信した排出許可に応答して、１つの可変長フレームを上記出力回線インタフェースに排出するフレーム排出制御部とからなり、
上記読出し制御部が、フレーム排出要求を発行中のフロー制御部の中から所定のアルゴリズムで選択した１つのフロー制御部に対して、上記排出許可を与えることを特徴とするシェーピング装置。
【請求項２】
前記各フロー制御部が、
可変長フレームを一時的に蓄積するためのバッファメモリと、
上記バッファメモリから排出された可変長フレームの長さを検出するフレーム長認識部とを有し、
前記第１の排出タイミング判定部が、フロー毎に予め設定された最大許容帯域と上記フレーム長認識部から通知された排出フレームの長さに基いて、次フレームの排出タイミングを決定し、
前記第２の排出タイミング判定部が、フロー毎に予め設定された最低保証帯域と上記フレーム長認識部から通知された排出フレームの長さに基いて、次フレームの排出タイミングを決定することを特徴とする請求項１に記載のシェーピング装置。
【請求項３】
前記第１の排出タイミング判定部が、フロー毎に予め設定された最大許容帯域に比例した漸減速度でレベルカウント値を減算し、前記フレーム排出制御部によるフレーム排出の都度、排出フレームの長さに応じてレベルカウント値を上昇させ、レベルカウント値を所定の閾値と比較して前記フレーム排出タイミングを決定するリーキーバケット型カウンタ構造を有し、
前記第２の排出タイミング判定部が、フロー毎に予め設定された最低保証帯域に比例した漸減速度でレベルカウント値を減算し、前記フレーム排出制御部によるフレーム排出の都度、排出フレームの長さに応じてレベルカウント値を上昇させ、レベルカウント値を所定閾値と比較して前記フレーム排出タイミングを決定するリーキーバケット型カウンタ構造を有することを特徴とする請求項１に記載のシェーピング装置。
【請求項４】
前記第１の排出タイミング判定部が、レベルカウント値の下限値を前記閾値に固定し、
前記第２の排出タイミング判定部が、前記閾値以下でのレベルカウント値の減算を許容することを特徴とする請求項３に記載のシェーピング装置
【請求項５】
前記読出し制御部が、
前記最低保証帯域フレーム排出要求を発行中の複数のフロー制御部からフレーム排出候補となる第１のフロー制御部を選択する第１の排出候補判定部と、
前記最大許容帯域フレーム排出要求を発行中の複数のフロー制御部からフレーム排出候補となる第２のフロー制御部を選択する第２の排出候補判定部と、
上記第１のフロー制御部を優先させて、フレーム排出候補となった上記第１、第２のフロー制御部のうちの１つにフレーム排出許可を与える排出許可発行部とからなることを特徴とする請求項１〜請求項４の何れかに記載のシェーピング装置。
【請求項６】
出力回線に接続された出力回線インタフェースと、
それぞれ特定のフローグループと対応する複数の初段シェーピング部と、
上記出力回線に出力すべき可変長フレームを上記初段フロー制御装置に選択的に振り分けるフレーム振り分け部と、
上記複数の初段シェーピング部と上記出力回線インタフェースとの間に接続された第２段シェーピング部とからなり、
初段の各シェーピング部が、
それぞれ同一グループ内の特定のフローに属した可変長フレームを一時的に蓄積し、予めフロー毎に設定された最大許容帯域と最低保証帯域に従って蓄積フレームの出力タイミングを決定する複数の第１フロー制御部と、
フレーム排出要求を発行中の第１フロー制御部の中から所定のアルゴリズムで選択した第１フロー制御部に対して、フレームの排出許可を与える第１読出し制御部とからなり、
上記第２段シェーピング部が、
それぞれ上記初段の各フロー制御装置から出力される特定グループの可変長フレームを一時的に蓄積し、予めフローグループ毎に設定された最大許容帯域と最低保証帯域に従って蓄積フレームの出力タイミングを決定する複数の第２フロー制御部と、
フレーム排出要求を発行中の第２フロー制御部の中から所定のアルゴリズムで選択したフロー制御部に対して、上記出力回線インタフェースへのフレームの排出許可を与える第２読出し制御部とからなり、
上記フレーム振り分け部が、上記出力回線に出力すべき可変長フレームの所属フローを識別し、該可変長フレームをその所属フローと対応した上記何れかの第１フロー制御部に振り分け、
上記第１、第２の各フロー制御部が、
可変長フレームを一時的に蓄積するためのバッファメモリと、
フロー毎に予め設定された最大許容帯域に基いて決定したフレーム排出タイミングで、上記読出し制御部に最大許容帯域フレーム排出要求を発行する第１の排出タイミング判定部と、
フロー毎に予め設定された最低保証帯域に基いてフレーム排出タイミングを決定し、上記第１の排出タイミング判定部から最大許容帯域フレーム排出要求が発行されていることを条件として、上記読出し制御部に最低保証帯域フレーム排出要求を発行する第２の排出タイミング判定部と、
上記第１または第２読出し制御部から受信した排出許可に応答して、上記バッファメモリに蓄積された１つの可変長フレームを排出するフレーム排出制御部とからなることを特徴とするシェーピング装置。
【請求項７】
複数の入出力回線に接続される通信ノード装置におけるフロー制御方法であって、
各入力回線から受信された可変長フレームを宛先情報で特定される何れかの出力ポートにスイッチングするステップと、
同一出力ポートにスイッチングされた可変長フレームを所属フロー別に一時的に蓄積するステップと、
フロー毎に予め設定された最大許容帯域に基いてフレーム排出タイミングを決定し、最大許容帯域のフレーム排出要求を発行するステップと、
フロー毎に予め設定された最低保証帯域に基いてフレーム排出タイミングを決定し、上記最大許容帯域フレーム排出要求が発行されていることを条件として、最低保証帯域のフレーム排出要求を発行するステップと、
最低保証帯域のフレーム排出要求を優先させて、発行中の複数のフレーム排出要求のうちの１つを選択し、該フレーム排出要求と対応するフローに属した最先の蓄積フレームを出力回線に送出するステップとからなるフロー制御方法。
【請求項８】
前記最大許容帯域のフレーム排出要求が、フロー毎に予め設定された最大許容帯域に比例した漸減速度でレベルカウント値を減算し、フレーム排出の都度、排出フレームの長さに応じて上記レベルカウント値を上昇させ、レベルカウント値を所定閾値と比較して前記フレーム排出タイミングを決定するリーキーバケット型カウンタによって生成され、
前記最低保証帯域フレーム排出要求が、フロー毎に予め設定された最低保証帯域に比例した漸減速度でレベルカウント値を減算し、前記フレーム排出制御部によるフレーム排出の都度、排出フレームの長さに応じて上記レベルカウント値を上昇させ、レベルカウント値を所定閾値と比較して前記フレーム排出タイミングを決定するリーキーバケット型カウンタによって生成されることを特徴とする請求項７に記載のフロー制御方法。
【請求項９】
複数の入出力ポートを有するスイッチ部と、
それぞれ上記スイッチ部の入力ポートに接続された複数の入力回線インタフェースと、
それぞれ上記スイッチ部の出力ポートに接続された複数のシェーピング部と、
それぞれ上記シェーピング部に接続された複数の出力回線インタフェースとからなる通信ノード装置において、
上記各シェーピング部が、
それぞれ特定のフローに属した可変長フレームを一時的に蓄積し、予め設定された最大許容帯域と最低保証帯域に従って蓄積フレームの出力タイミングを決定する複数のフロー制御部と、
上記複数のフロー制御部に接続された読出し制御部と、
上記スイッチ部の出力ポートから受信した同一出力回線に出力すべき可変長フレームの所属フローを識別し、所属フローと対応した上記何れかのフロー制御部に各可変長フレームを振り分けるフレーム振り分け部とからなり、
上記各フロー制御部が、
フロー毎に予め設定された最大許容帯域に基いて決定したフレーム排出タイミングで、上記読出し制御部に最大許容帯域フレーム排出要求を発行する第１の排出タイミング判定部と、
フロー毎に予め設定された最低保証帯域に基いてフレーム排出タイミングを決定し、上記第１の排出タイミング判定部から最大許容帯域フレーム排出要求が発行されていることを条件として、上記読出し制御部に最低保証帯域フレーム排出要求を発行する第２の排出タイミング判定部と、
上記読出し制御部から受信した排出許可に応答して、１つの可変長フレームを上記出力回線インタフェースに排出するフレーム排出制御部とからなり、
上記読出し制御部が、フレーム排出要求を発行中のフロー制御部の中から所定のアルゴリズムで選択した１つのフロー制御部に対して、上記出力回線インタフェースへのフレームの排出許可を与えることを特徴とする通信ノード装置。
【請求項１０】
前記各フロー制御部が、可変長フレームを一時的に蓄積するためのバッファメモリと、上記バッファメモリから排出された可変長フレームの長さを検出するフレーム長認識部とを有し、
前記第１の排出タイミング判定部が、フロー毎に予め設定された最大許容帯域と上記フレーム長認識部から通知された排出フレームの長さに基いて、次フレームの排出タイミングを決定し、
前記第２の排出タイミング判定部が、フロー毎に予め設定された最低保証帯域と上記フレーム長認識部から通知された排出フレームの長さに基いて、次フレームの排出タイミングを決定することを特徴とする請求項９に記載の通信ノード装置。
【請求項１１】
前記読出し制御部が、
前記最低保証帯域フレーム排出要求を発行中の複数のフロー制御部からフレーム排出候補となる第１のフロー制御部を選択する第１の排出候補判定部と、
前記最大許容帯域フレーム排出要求を発行中の複数のフロー制御部からフレーム排出候補となる第２のフロー制御部を選択する第２の排出候補判定部と、
上記第１のフロー制御部を優先させて、フレーム排出候補となった上記第１、第２のフロー制御部のうちの１つにフレーム排出許可を与える排出許可発行部とからなることを特徴とする請求項９または請求項１０に記載の通信ノード装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、可変長フレームを帯域制御して送出するためのトラフィックシェーピング装置、フロー制御方法および通信ノード装置に関する。
【背景技術】
【０００２】
近年、ブロードバンドサービス等、高速ネットワークへの需要が大きくなっている。高速ネットワークの１つの形態として、通信コストの安いイーサネット（登録商標名）ベースのネットワークが広く普及している。イーサネットベースのネットワークでは、回線の空き状況に応じて割当て帯域が決まるベストエフォート型の通信サービスが提供されており、ピーク速度の高いバースト的なパケット転送に向いている。しかしながら、ユーザ毎に安定した帯域の保証はなく、一時的に特定ユーザによる回線の占有が発生するため、安定した品質のサービスを保証できないという問題がある。
【０００３】
ネットワークユーザからは、最低帯域を保証した高品質の通信サービスへの要求が強まっており、各ユーザに対して契約で定めた最低保証帯域を安定的に割当て、空き帯域が発生した場合は、それを有効利用可能な通信サービスの提供が望まれている。また、空き帯域が発生した場合でも、ユーザ毎に予め設定された最大許容帯域を超えるようなパケット転送サービスを行うと、受信側端末でバッファあふれが発生し、受信データが廃棄される可能性があるため、各ユーザに対して適度な最大許容帯域を設定し、それを超えないように帯域を制御する必要がある。
【０００４】
イーサネットのような可変長フレームの転送においては、使用帯域がフレーム（パケット）数とフレーム長の双方に依存するため、ＡＴＭ網における固定長セル転送のように、フレーム数の制御だけでは、フロー毎の帯域制御を行うことができない。ここでフレーム（パケット）とは、通信網におけるデータ転送単位となるヘッダ、ペイロード、トレイラからなるデータブロックを指している。
【０００５】
フロー毎に最低保証帯域を保証し、且つ、空き帯域を有効利用して可変長データの転送する従来技術として、例えば、特開２００３−１９８６１１号公報（特許文献１）が示すように、或る深さをもつ穴開きバケツをモデルとしたリーキーバケット方式の帯域制御が知られている。リーキーバケット方式の帯域制御では、単位時間当たりにバケツから漏れる水量を目標帯域に比例させておき、バケツの水位が予め設定された閾値を下回った時、リーキーバケットと対応付けられたバッファメモリにフレーム送信権を与え、フレームの送出の都度、送出フレーム長に対応した量だけバケツの水位を上昇させることによって、転送されるデータ量が平均的に目標帯域の範囲内に収まるようにしている。
【０００６】
特許文献１に示された従来技術では、バッファメモリ（パケットキュー）毎に、リーキーバケットの水位に相当するレベルカウント値と、予め指定された最低保証帯域に対応する閾値との差分値を記憶しておき、差分値が小さいバッファメモリから順に蓄積パケット（フレーム）を出力するように、フレーム排出キューを選択している。
【０００７】
上記従来技術によれば、最低保証帯域に最も近いバッファメモリから順にパケットが排出されるため、最低保証帯域を遵守したパケット転送が可能となる。また、パケット送出に伴う上昇水位の算出に際して、リーキーバケットの現在水位を示すレベルカウント値の低下に伴って、パケット長に乗算される単位インクリメント値を段階的に増加させる可変インクリメント値を採用することによって、レベルカウント値が閾値を大きく下回った状態でパケットが送出された時、バケツ水位の上昇を加速し、短時間で閾値よりも高いレベルに復帰させるようにしている。
【０００８】
【特許文献１】特開２００３−１９８６１１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
上記従来技術では、レベルカウンタに最低保証帯域と最大許容帯域に対応する２つの閾値を設定し、それを超えないようにレベルカウント値を制御することできるため、通常の状態ではパケットの送出量が最大許容帯域を超えることはない、しかしながら、トラフィックが途絶えてレベルカウント値が閾値を大きく下回った場合、以下に説明するように、レベルカウント値が最低保証帯域の閾値以上に復帰する迄の期間に、パケットの送出量が一時的に最大許容帯域を超える可能性がある。
【００１０】
図９において、（Ａ）は、同一フローに所属したパケットの到着順序、（Ｂ）は、リーキーバケットのレベルカウント値、（Ｃ）は、パケット（フレーム）の出力タイミングを示している。
【００１１】
リーキーバケットのレベルカウント値は、（Ｂ）に示すように、時間経過とともに目標帯域に比例した速度で減少し、パケット排出の都度、排出パケット長に応じた値がレベルカウント値に加算される。レベルカウント値が閾値ＴＨを下回った時、もし、出力回線が空いていれば、パケットの排出が可能となる。通常状態では、レベルカウント値が閾値ＴＨに達した時点でパケット（Ｐ１、Ｐ２、Ｐ３）を送信することによって、目標帯域を遵守したトラフィックのシェーピングが可能となるが、例えば、パケットの到着が暫く途絶えて送出すべきパケットが無くなった場合や、他のフロー（コネクション）に属したパケットの送出によって出力回線の閉塞状態が継続した場合は、期間Ｔで示すように、レベルカウント値が閾値ＴＨを大きく下回ることになる。
【００１２】
このように、レベルカウント値が大きく減少すると、パケットを送出してレベルカウント値にパケット長を加算しても、レベルカウント値が閾値を超えないため、パケットの排出条件が連続的に満たされる。その結果、Ｐ４、Ｐ５、Ｐ６、Ｐ７で示すように、同一フローに属した複数のパケットがバースト的に送信され、レベルカウント値が閾値を大きく超える迄の間に、一時的に最大許容帯域を超えたパケット転送が起こり得る。
【００１３】
本発明の目的は、フロー毎に最低保証帯域を保証し、且つ、最大許容帯域の範囲内で出力回線の空き帯域を有効に利用できるトラフィックシェーピング装置、フロー制御方法および通信ノード装置を提供することにある。
本発明の他の目的は、同一出力回線で競合する他のトラフィック量が減少した場合でも、最大許容帯域を超えない範囲でパケットをバースト転送可能なシェーピング装置、フロー制御方法および通信ノード装置を提供することにある。
【課題を解決するための手段】
【００１４】
上記目的を達成するため、本発明のシェーピング装置および通信ノード装置は、それぞれ特定のフローに属した可変長フレーム（パケット）を一時的に蓄積し、予め設定された最大許容帯域と最低保証帯域に従って蓄積フレームの出力タイミングを決定する複数のフロー制御部と、上記複数のフロー制御部に接続された読出し制御部と、同一の出力回線に出力すべき可変長フレームの所属フローを識別し、所属フローと対応した上記何れかのフロー制御部に各可変長フレームを振り分けるフレーム振り分け部とを有し、
上記各フロー制御部が、フロー毎に予め設定された最大許容帯域に基いて決定したフレーム排出タイミングで、上記読出し制御部に最大許容帯域フレーム排出要求を発行する第１の排出タイミング判定部と、フロー毎に予め設定された最低保証帯域に基いてフレーム排出タイミングを決定し、上記第１の排出タイミング判定部から最大許容帯域フレーム排出要求が発行されていることを条件として、上記読出し制御部に最低保証帯域フレーム排出要求を発行する第２の排出タイミング判定部と、上記読出し制御部から受信した排出許可に応答して、１つの可変長フレームを上記出力回線インタフェースに排出するフレーム排出制御部とからなり、上記読出し制御部が、フレーム排出要求を発行中のフロー制御部の中から所定のアルゴリズムで選択したフロー制御部に対して、上記フレーム排出許可を与えることを特徴とする。
【００１５】
更に詳述すると、上記各フロー制御部は、可変長フレームを一時的に蓄積するためのバッファメモリと、上記バッファメモリから排出された可変長フレームの長さを検出するフレーム長認識部とを有し、上記第１の排出タイミング判定部は、フロー毎に予め設定された最大許容帯域と上記フレーム長認識部から通知された排出フレームの長さに基いて、次フレームの排出タイミングを決定し、上記第２の排出タイミング判定部は、フロー毎に予め設定された最低保証帯域と上記フレーム長認識部から通知された排出フレームの長さに基いて、次フレームの排出タイミングを決定する。
【００１６】
本発明の１実施例では、上記第１の排出タイミング判定部が、フロー毎に予め設定された最大許容帯域に比例した漸減速度でレベルカウント値を減算し、上記フレーム排出制御部によるフレーム排出の都度、排出フレームの長さに応じてレベルカウント値を上昇させ、レベルカウント値を所定の閾値と比較して前記フレーム排出タイミングを決定するリーキーバケット型カウンタ構造を有し、上記第２の排出タイミング判定部が、フロー毎に予め設定された最低保証帯域に比例した漸減速度でレベルカウント値を減算し、上記フレーム排出制御部によるフレーム排出の都度、排出フレームの長さに応じてレベルカウント値を上昇させ、レベルカウント値を所定閾値と比較して前記フレーム排出タイミングを決定するリーキーバケット型カウンタ構造を有する。
【００１７】
本発明の１つの特徴は、上記第１の排出タイミング判定部が、レベルカウント値の下限値を前記閾値に固定し、上記第２の排出タイミング判定部が、前記閾値以下でのレベルカウント値の減算を許容することにある。
本発明の他の特徴は、上記読出し制御部が、上記最低保証帯域フレーム排出要求を発行中の複数のフロー制御部からフレーム排出候補となる第１のフロー制御部を選択する第１の排出候補判定部と、上記最大許容帯域フレーム排出要求を発行中の複数のフロー制御部からフレーム排出候補となる第２のフロー制御部を選択する第２の排出候補判定部と、上記第１のフロー制御部を優先させて、フレーム排出候補となった上記第１、第２のフロー制御部のうちの１つにフレーム排出許可を与える排出許可発行部とを有する点にある。
【００１８】
本発明のフロー制御方法は、複数の入出力回線に接続される通信ノード装置において、（Ａ）各入力回線から受信された可変長フレームを宛先情報で特定される何れかの出力回線にスイッチングするステップと、（Ｂ）同一出力回線に送出される可変長フレームを所属フロー別に一時的に蓄積するステップと、（Ｃ）フロー毎に予め設定された最大許容帯域に基いてフレーム排出タイミングを決定し、最大許容帯域のフレーム排出要求を発行するステップと、（Ｄ）フロー毎に予め設定された最低保証帯域に基いてフレーム排出タイミングを決定し、上記最大許容帯域フレーム排出要求が発行されていることを条件として、最低保証帯域のフレーム排出要求を発行するステップと、（Ｅ）最低保証帯域のフレーム排出要求を優先させて、発行中の複数のフレーム排出要求のうちの１つを選択し、該フレーム排出要求と対応するフローに属した最先の蓄積フレームを出力回線に送出するステップとからなることを特徴とする。
【発明の効果】
【００１９】
本発明によれば、各フロー毎に、第１のフレーム排出タイミング判定部から最大許容帯域に基づく第１のフレーム排出要求を発行し、該第１のフレーム排出要求が発行中であることを条件として、第２のフレーム排出タイミング判定部から最低保証帯域に基づく第２のフレーム排出要求を発行し、読出し制御部が、最低保証帯域に基く第２のフレーム排出要求を優先させて、フレーム排出すべきフローを決定するようにしているため、各フローの最低保証帯域を保証し、且つ、出力回線の空き帯域を有効に利用したフロー制御を実現できる。
【００２０】
また、最大許容帯域に基くフレーム排出要求の発生タイミングを支配するレベルカウント値の下限を閾値に固定しておくことによって、例えば、同一フローの後続フレームの到着が暫く途絶えたり、他フローのフレーム送信による出力回線の閉塞状態が継続した場合でも、閾値以下でのレベルカウント値の減算に起因するフレーム排出要求の連続的な発行を抑制できるため、出力回線に空き帯域を利用した同一フローのバースト的フレーム転送における最大許容帯域の超過を防止することが可能となる。
【発明を実施するための最良の形態】
【００２１】
以下、本発明の実施例について図面を参照して説明する。
図１は、本発明によるシェーピング装置が適用されるパケットスイッチ１０の１例を示す。
【００２２】
パケットスイッチ１０は、複数の入力ポートＰＩ−１〜ＰＩ−ｎと出力ポートＰＯ−１〜ＰＯ−ｎを有するスイッチング部（フレーム中継処理部）３と、それぞれスイッチング部３の入力ポートＰＩ−ｉと入力回線ＩＮ−ｉとの間に接続された複数の入力回線インタフェース２−ｉ（ｉ＝１〜ｎ）と、それぞれスイッチング部３の出力ポートＰＯ−ｉに接続された複数のシェーピング装置（シェーパー）４−ｉ（ｉ＝１〜ｎ）と、それぞれシェーピング装置４−ｉと出力回線ＯＵＴ−ｉとの間に接続された複数の出力回線インタフェース５−ｉ（ｉ＝１〜ｎ）と、ノード制御部６とからなる。ノード制御６は、外部の管理端末（図示せず）と接続され、管理端末からの指示に従って、各シェーピング装置４が使用するフローテーブルへのデータ設定と帯域制御用の演算パラメータの設定を行う。
【００２３】
各入力回線インタフェース２−ｉは、入力回線ＩＮ−ｉから可変長フレーム（パケット）を受信すると、パケットヘッダが示す宛先アドレスに基いてルーティングテーブルから内部ルーティング情報を検索し、該内部ルーティング情報を含む内部ヘッダを付加した形で、受信フレームをスイッチング部３の入力ポートＰＩ−ｉに出力する。スイッチング部３は、各入力ポートＰＩ−ｉから受信した可変長フレームを内部ルーティング情報によって特定される何れかの出力ポートに転送する。
【００２４】
各シェーピング装置４−ｉは、スイッチング部３から出力ポートＰＯ−ｉに出力された可変長フレームを一時的に蓄積し、予め設定された最低保証帯域と最大許容帯域に基づいてフロー毎の帯域を制御して、出力回線インタフェース５−ｉに出力する。各出力回線インタフェース５−ｉは、シェーピング装置４−ｉの出力フレームから内部ヘッダを除去し、出力回線ＯＵＴ−ｉに送信する。
【００２５】
図２は、パケットスイッチ１０が適用されるネットワークの１例を示す。
ここでは、パケットスイッチ１０は、複数の端末１１１〜１１８と広域ネットワーク１００との間に配置されている。パケットスイッチ１０の入出力回線ＩＮ−ｉ、ＯＵＴ−ｉ（ｉ＝１〜ｎ）には、端末１１７、１１８のように、端末を個別に収容するものもあれば、端末１１１〜１１３のように、複数の端末を含む受動的なネットワーク１０１を収容するものや、端末１１４〜１１６のように、複数の端末にトラフィックを能動的に振り分ける多重化装置１０２を収容するものもある。このようなネットワーク構成において、端末毎に予め指定された帯域に基いてフロー制御を行おうとした場合、パケットスイッチ１０では、例えば、ネットワーク１０１または多重化装置１０２が接続された出力回線に向かうパケット列をフロー別にバッファリングし、パケットフロー毎に最低保証帯域と最大許容帯域を保証したフロー制御を行う必要がある。
【００２６】
図３は、スイッチング部３の出力ポートＰＯ−ｉに接続される本発明のシェーピング装置４−ｉの第１の実施例を示す。
シェーピング装置４−ｉは、スイッチング部３の出力ポートＰＯ−ｉに接続されたフレーム振り分け部４００と、フレーム振り分け部４００に接続された複数のフロー制御部４０（４０−１〜４０−ｍ）と、これらのフロー制御部４０に接続された読出し制御部４４およびセレクタ４５からなる。
【００２７】
各フロー制御部４０は、出力フレーム（出力パケット）を所属フロー別に一時的に蓄積するためのバッファメモリ４１（４１−１〜４１−ｍ）と、各バッファメモリに付随する帯域制御部４２（４２−１〜４２−ｍ）と、各バッファメモリから読み出されたフレーム長を認識し、帯域制御部４２に通知するフレーム長認識部４３（４３−１〜４３−ｍ）ととからなる。
【００２８】
スイッチング部３が出力ポートＰＯ−ｉに転送した出力フレームは、フレーム振り分け部４００によってフロー識別され、信号線Ｌ４０を介して、フローと対応した何れかのバッファメモリ４１−ｊに振り分けられる。各出力フレームの所属フローの識別とバッファメモリの特定は、フロー定義情報とバッファ番号との対応関係を示すフローテーブル４０５を参照して行われる。パケットフローは、例えば、各出力フレームのヘッダから抽出される宛先アドレス、タグ情報、優先度、フレーム長、サービスタイプ等のヘッダ（ラベル）情報の組み合せによって定義される。フレーム振り分け部４００は、可変長フレームをバッファメモリ４１−ｊに出力すると、信号線Ｌ４０を介して、バッファメモリ４１−ｊに付随した帯域制御部４２−ｊに、バッファメモリ４１−ｊにパケットが入力されたことを通知する。
【００２９】
帯域制御部４２−ｊは、フロー毎に予め設定された最低保証帯域と最大許容帯域に従って、バッファメモリ４１−ｊからのパケットの排出タイミングを決定し、信号線Ｌ４２を介して、読出し制御部４４にフレーム排出要求を発行する。尚、後述するように、本発明では、上記フレーム排出要求として、最低保証帯域に従ったフレーム排出要求と、最大許容帯域に従ったフレーム排出要求とが発行される。図３では、簡単化のために、帯域制御部４２−１〜４２−ｍと読出し制御部４４との間に設けられたフレーム排出要求信号線を1本の信号線Ｌ４２で示してある。
【００３０】
読出し制御部４４は、信号線Ｌ４２に出力される帯域制御部４２−１〜４２−ｍからのフレーム排出要求を監視して、フレーム排出を許可すべき帯域制御部を決定する。複数の排出要求が競合した場合は、予め用意された排出候補決定アルゴリズムに従って、優先的にフレーム排出すべき１つの帯域制御部４２−ｋを選択し、出力回線インタフェース５−ｉが新たなフレームの受け入れ可能状態となった時、信号線Ｌ４４を介して該帯域制御部４２−ｋに排出許可信号を出す。この時、読出し制御部４４は、上記帯域制御部４２−ｋと対応したフレーム長認識部４３−ｋからの出力フレームが出力回線インタフェース５−ｉに出力されるように、信号線Ｌ４５を介して、セレクタ４５に選択制御信号を与える。
【００３１】
帯域制御部４２−ｋは、読出し制御部４４からのフレーム排出許可信号に応答して、バッファメモリ４１−ｋに蓄積された出力フレームを排出し、フレーム長認識部４３−ｋから通知されたフレーム長に応じて、最低保証帯域と最大許容帯域に基づく次の排出タイミングを決定するためのリーキーバケットのレベル更新を行う。
【００３２】
図４は、図３のシェーピング装置４−ｉに適用される帯域制御部４２−ｊ（ｊ＝１〜ｍ）の１実施例を示す。
帯域制御部４２−ｊは、排出制御部４１０と、最低保証帯域に基づいた排出要求信号ＲＥＱ１を発生する最低保証帯域排出タイミング判定部４２０と、最大保証帯域に基づいた排出要求信号ＲＥＱ２を発生する最大許容帯域排出タイミング判定部４３０からなる。
【００３３】
排出制御部４１０は、バッファメモリ４１−ｊの蓄積パケット数をカウントするためのカウンタ４１１を有し、フレーム振り分け部４００から信号線Ｌ４００を介してパケットの入力通知を受けると、上記カウンタ４１１をインクリメントする。また、読出し制御部４４からフレーム排出許可信号を受信すると、バッファメモリ４１−ｊにフレーム排出命令を出力すると共に、カウンタ４１１をデクリメントし、最低保証帯域排出タイミング判定部４２０と最大許容帯域排出タイミング判定部４３０に対して、フレーム長加算命令を出力する。排出制御部４１０は、上記カウンタ４１１のカウント値が「１」以上の時、すなわち、バッファメモリ４１−ｊに蓄積フレームが存在している間は、最低保証帯域排出タイミング判定部４２０と最大許容帯域排出タイミング判定部４３０に与えるイネーブル信号ＥＮをオン状態にし、カウント値がゼロになった時、信号ＥＮをオフ状態にする。
【００３４】
最低保証帯域排出タイミング判定部４２０は、フレーム長加算処理部４２１と、フレーム長加算処理部４２１で更新されたレベルカウント値を保持するレベルカウント保持部４２２と、予め設定された演算パラメータを記憶する演算パラメータ保持部４２３と、レベルカウント保持部４２２が示すレベル値から、演算パラメータ保持部４２３に演算パラメータの１つとして記憶されている減算パラメータ値を周期的に減算する減算処理部４２４と、減算処理部４２４から出力されるレベルカウント値と演算パラメータ保持部４２３に演算パラメータの１つとして記憶されている閾値とを比較し、比較結果を出力する閾値判定部４２５と、閾値判定部４２５の出力から、レベルカウント値が閾値以下となったことを検知して、排出要求信号を発生する排出要求送出部４２６と、上記排出要求送出部４２６からの排出要求信号と最大許容帯排出タイミング判定部４３０から出力される排出要求信号との論理積を最低保証帯域フレーム排出要求信号ＲＥＱ１として出力する論理積（ＡＮＤ）回路４２７からなる。
【００３５】
排出要求送出部４２６は、イネーブル信号ＥＮがオフ状態の時は、排出要求信号を発生しない。また、閾値判定部４２５は、イネーブル信号ＥＮがオン状態からオフ状態に変わった場合、レベルカウント値が閾値に達した時点で、信号線Ｌ４２５を介して、減算処理部４２４に減算動作の停止を指示する。減算処理部４２４によるレベルカウント値の減算動作は、次のパケットがバッファメモリ４１−ｊに入力され、イネーブル信号ＥＮがオフ状態からオン状態に変わった時、再開される。
【００３６】
一方、最大許容帯域排出タイミング判定部４３０は、フレーム長加算処理部４３１と、レベルカウント保持部４３２と、予め設定された演算パラメータを記憶する演算パラメータ保持部４３３と、レベルカウント保持部４２２が示すレベル値から、演算パラメータ保持部４３３に演算パラメータの１つとして記憶されている減算パラメータ値を周期的に減算する減算処理部４３４と、減算処理部４３４から出力されるレベルカウント値と演算パラメータ保持部４３３に演算パラメータの１つとして記憶されている閾値とを比較し、比較結果を出力する閾値判定部４３５と、閾値判定部４３５の出力が閾値に達した時、フレーム排出要求信号ＲＥＱ２を発生する排出要求送出部４３６とからなる。減算処理部４３４は、レベルカウント値が閾値に達した時、実質的に減算動作を停止し、カウント値を閾値に保持し続ける。また、排出要求送出部４３６は、イネーブル信号ＥＮがオフ状態の時は、排出要求信号を発生しない。
【００３７】
最大許容帯域排出タイミング判定部４３０は、論理回路４２７が無いこと、減算処理部４３４のレベルカウント値の下限が閾値となっていること、および演算パラメータ保持部４３３に記憶されるパラメータ値が相違する点を除いて、構造的には最低保証帯域排出タイミング判定部４２０と類似しているため、ここでは、最低保証帯域排出タイミング判定部４２０について、その詳細動作を説明する。
【００３８】
フレーム長加算処理部４２１には、減算処理部４２４から出力される現在のレベルカウント値が入力してあり、排出制御部４１０からフレーム長加算命令を受信した時、現在のレベルカウント値にフレーム長認識４３−ｊから受信した排出フレーム長を加算する。フレーム加算命令がない場合は、排出フレーム長との加算処理は行われないため、減算処理部４２４から出力された現在のレベルカウント値が、そのままレベルカウント保持部４２２に入力される。
【００３９】
減算処理部４２４は、レベルカウント保持部４２２が示すレベルカウント値から、演算パラメータ保持部４２３が示す減算パラメータの値を周期的に減算し、演算結果を新たなレベルカウント値として、フレーム長加算処理部４２１と閾値判定部４２５に出力する。上記減算パラメータの値は、最低保証帯域排出タイミング判定部４２０の場合は最低限保証すべき帯域に相当し、最大許容帯域排出決定部４３０の場合は、許容できる最大の帯域に相当している。従って、最低保証帯域排出タイミング判定部４２０において、減算処理部４２４の出力は、最低保障帯域に比例した速度で漸減し、フレーム排出の都度、排出フレーム長に応じてレベル上昇するリーキーバケットの水位を示している。
【００４０】
閾値判定部４２５は、減算処理部４２４から出力されるレベルカウント値（リーキーバケット水位）と演算パラメータ保持部４２３が示す閾値との比較結果を出力しており、レベルカウント値が閾値を下回ったとき、排出要求送出部４２６からフレーム排出要求信号が発行される。
【００４１】
本実施例では、最低保証帯域排出タイミング判定部４２０は、最終段に論理積（ＡＮＤ）回路４２７を備え、上記排出要求送出部４２６の出力信号と最大許容帯域排出タイミング判定部４３０の排出要求送出部４３６から出力されるフレーム排出要求信号ＲＥＱ２との論理積を最低保証帯域のフレーム排出要求信号ＲＥＱ１としているため、最大許容帯域排出タイミング判定部４３０で排出要求が発生しない限り、最低保証帯域のフレーム排出要求は出力されない。
【００４２】
図５は、読出し制御部４４の１実施例を示す。
帯域制御部４２（４２−１〜４２−ｍ）は、上述したように、それぞれ最低保証帯域排出タイミング判定部４２０と最大許容帯域排出タイミング判定部４３０をもつため、読出し制御部４４には、各帯域制御部４２から、最低保証帯域に基づいたフレーム排出要求信号ＲＥＱ１と、最大許容帯域に基づいたフレーム排出要求信号ＲＥＱ２の２種類の要求が入力される。
【００４３】
読出し制御部４４は、フレーム排出要求信号ＲＥＱ１を処理する最低保証帯域排出候補選択部４４０と、フレーム排出要求信号ＲＥＱ２を処理する最大許容帯域排出候補選択部４５０と、排出許可発行部４６０と、排出候補決定アルゴリズムの記憶部４７０とからなる。
【００４４】
最低保証帯域排出候補選択部４４０は、フレーム排出要求信号ＲＥＱ１を発生中の帯域制御部の中から、記憶部４７０が示す排出公報決定アルゴリズムに従って、フレーム排出候補となる１つの帯域制御部を選択する。同様に、最大許容帯域排出候補選択部４５０は、フレーム排出要求信号ＲＥＱ２を発生中の帯域制御部の中から、上記排出候補決定アルゴリズムに従って、フレーム排出候補となる１つの帯域制御部を１つ選択する。但し、排出候補決定アルゴリズムは、最低保証帯域排出候補選択部４４０と最大許容帯域排出候補選択部４５０とで異なるアルゴリズムを適用してもよい。
【００４５】
排出許可発行部４６０は、最低保証帯域のフレーム排出候補を最大許容帯域のフレーム排出候補よりも優先させる。従って、最低保証帯域のフレーム排出要求ＲＥＱ１が発行中は、最低保証帯域のフレーム排出候補となった帯域制御部に排出許可が与えられる。最低保証帯域の排出候補がなかった場合に、最大許容帯域のフレーム排出候補となった帯域制御部に排出許可が与えられる。最低保証帯域と最大許容帯域の何れにもフレーム排出候補がない時は、現時点でフレーム排出すべきバッファメモリが存在しないことを意味しているため、フレーム排出許可は発行されない。
【００４６】
図６は、上述した本発明のシェーピング装置４において、帯域制御部４２−１によるバッファメモリ４２−１からの可変長フレーム（パケット）の排出動作を示す。
ここでは、図（Ａ）に示すように、バッファメモリ４１−１にフレームがＦＲ１、ＦＲ２、ＦＲ３の順で入力された場合を想定する。図（Ｂ）は、上記バッファメモリ４１−１に付随する最低保証帯域排出タイミング判定部４２０の演算処理部４２４から出力されるレベルカウント値、図（Ｃ）は、最低保証帯域排出タイミング判定部４２０の論理積回路４２７から発生する最低保証帯域のフレーム排出要求信号ＲＥＱ１、図（Ｄ）は、上記バッファメモリ４１−１に付随する最大許容帯域排出タイミング判定部４３０の演算処理部４３４から出力されるレベルカウント値、図（Ｅ）は、最大許容帯域排出タイミング判定部４３０の排出要求送出部４３６から発生する最大許容帯域のフレーム排出要求信号ＲＥＱ２、図（Ｆ）は、バッファメモリ４１−１からのフレームＦＲ１、ＦＲ２、ＦＲ３の排出タイミングを示している。
【００４７】
帯域制御部４２−１では、図（Ｆ）に示すように、時刻ｔ１で読出し制御部４４から排出許可を受信し、フレームＦＲ１の排出動作を開始すると、フレーム長加算処理部４２１、４３１が、最低保証帯域用のレベルカウント値と最大許容帯域用のレベルカウント値にフレームＦＲ１のフレーム長を加算するため、レベルカウント値は、図（Ｂ）、（Ｄ）のように増加する。ここで、レベルカウント値には同一のフレーム長が加算されるため、初期状態ｔ１において、上昇後のレベルカウント値は、最低保証帯域と最大許容帯域で同一の値となっている。レベルカウント値は、減算処理部４２４、４３４による減算動作によって、時間経過と共に漸減するが、最大許容帯域用の減算処理部４３４の方がデクリメント値が大きくなっているため、最低保証帯域のレベルカウント値より急激に減少する。
【００４８】
時刻ｔ２で最大許容帯域用のレベルカウント値が閾値（ゼロ）ＴＨに達すると、図（Ｅ）に示すように、最大許容帯域のフレーム排出要求信号ＲＥＱ２がオン状態となる。この時、減算処理部４３４は、実質的にレベルカウント値のデクリメント動作を休止し、レベルカウント値を閾値に保持する。上記フレーム排出要求信号ＲＥＱ２の発生によって、時刻ｔ２以降は、バッファメモリ４１−１が最大許容帯域のフレーム排出候補となり、読出し制御部４４から排出許可があれば、フレームを排出できる状態となる。
【００４９】
ここで、排出許可が得られないまま、時刻ｔ３で減算処理部４２４のレベルカウント値が閾値ＴＨに達すると、図（Ｃ）に示すように、最低保証帯域のフレーム排出要求ＲＥＱ１がオン状態となる。最低保証帯域用の減算処理部４２４は、カウント値が閾値以下となっても減算動作を継続する。バッファメモリ４１−１は、時刻ｔ３以降は、最低保証帯域のフレーム排出候補であり、且つ、最大許容帯域のフレーム排出候補にもなる。
【００５０】
時刻ｔ４で、読出し制御部４４から排出許可を受信すると、帯域制御部４２−１は、バッファメモリ４１−１からのフレームＦＲ２の排出を開始し、最低保証帯域のレベルカウント値と最大許容帯域のレベルカウント値にフレームＦＲ２のフレーム長を加算する。この加算によって、２つのレベルカウント値が閾値を上回り、フレーム排出要求ＲＥＱ１とＲＥＱ２が停止（オフ）状態となる。
【００５１】
減算処理部４２４、４３４は、更新されたレベルカウント値からデクリメント動作を再開し、減算処理部４３４のレベルカウント値が、時刻ｔ５で閾値（ゼロ）に達すると、図（Ｅ）に示すように、最大許容帯域のフレーム排出要求ＲＥＱ２が発生する。ここで、時刻ｔ５では他の帯域制御部からの排出要求が全く無かったと仮定すると、帯域制御部４２−１は、瞬時に次の排出許可を取得して、バッファメモリ４１−１からフレームＦＲ３を排出する。
【００５２】
フレームＦＲ３の排出に伴って、最低保証帯域用レベルカウント値と最大許容帯域用レベルカウント値にフレームＦＲ３のフレーム長が加算されるため、フレーム排出要求ＲＥＱ２が停止し、更新されたレベルカウント値からのデクリメント動作が繰り返される。尚、バッファメモリ４１−１が空になると、排出制御部４１０からのイネーブル信号ＥＮがオフ状態になるため、レベルカウント値が閾値に達しても、排出要求送出部４２６、４３６はフレーム排出要求を発生しない。
【００５３】
このように、本発明のシェーピング装置では、最低保証帯域のフレーム排出候補が不在の期間中は、読出し制御部４４が、最大許容帯域のフレーム排出候補となった帯域制御部にフレーム排出許可を与えるようになっているため、出力回線の空き帯域を有効に利用したフレーム（パケット）転送が可能となる。
【００５４】
次に、図７を参照して、本発明のシェーピング装置における２つのバッファメモリ４１−１、４１−２に着目して、フレームの排出動作を説明する。
ここでは、バッファメモリ４１−１には、図（Ａ）に示すように、フレームＦＲａ１〜ＦＲａ６が入力され、バッファメモリ４１−２には、図（Ｂ）に示すように、フレームＦＲｂ１、ＦＲｂ２が入力された場合を想定する。また、説明を簡単化するため、上記バッファメモリ４１−１、４１−２以外の他のバッファメモリ４１−３〜４１−ｍには蓄積フレームが存在しないものとし、読出し制御部４４には、排出要求発行中の帯域制御部に巡回的に排出許可を与えるラウンドロビン方式の排出候補決定アルゴリズムが適用された場合を想定する。
【００５５】
図（Ｃ）、（Ｄ）は、バッファメモリ４１−１に付随する帯域制御部４２−１における最低保証帯域排出タイミング判定部４２０のレベルカウント値と、最大許容帯域排出タイミング判定部４３０のレベルカウント値を示す。また、図（Ｅ）、（Ｆ）は、バッファメモリ４１−２に付随する帯域制御部４２−２における最低保証帯域排出タイミング判定部４２０のレベルカウント値と、最大許容帯域排出タイミング判定部４３０のレベルカウント値を示し、図（Ｇ）は、バッファメモリ４１−１、４１−２からのフレームの排出タイミングを示している。
【００５６】
読出し制御部４４が、時刻ｔ１で、帯域制御部４２−１に排出許可を与え、帯域制御部４２−１が、バッファメモリ４１−１からフレームＦＲａ１の排出を開始すると、図（Ｃ）、（Ｄ）に示すように、帯域制御部４２−１の最低保証帯域用のレベルカウント値と最大許容帯域用ののレベルカウント値にフレーム長が加算される。
【００５７】
時刻ｔ２で、フレームＦＲａ１の出力回線インタフェース５０−１への排出が完了すると、読出し制御部４４は、次にフレーム排出すべきバッファメモリを選択する。この時点では、帯域制御部４１−１は、最低保証帯域と最大許容帯域のレベルカウント値が何れも閾値を上回っているため、フレーム排出要求を発生していないが、帯域制御部４２−１は、図（Ｅ）、（Ｆ）に示すように、最低保証帯域のレベルカウント値が閾値を下回り、最大許容帯域のレベルカウント値が閾値に達しているため、フレーム排出要求ＲＥＱ１とＲＥＱ２の両方を発生している。従って、帯域制御部４２−１にフレーム排出許可を与えられ、時刻ｔ２でフレームＦＲｂ１の排出が開始される。
【００５８】
帯域制御部４２−１は、図（Ｃ）、（Ｄ）に示すように、最大許容帯域のレベルカウント値が閾値に達した時刻ｔ３でフレーム排出要求ＲＥＱ２を発生し、最低保証帯域のレベルカウント値が閾値に達した時刻ｔ４でフレーム排出要求ＲＥＱ１を発生する。しかしながら、時刻ｔ３、ｔ４では、帯域制御部４２−２がフレームＦＲｂ１を送出中で、出力回線が閉塞状態となっているため、帯域制御部４２−１へのフレーム排出許可は、フレームＦＲｂ１の排出が完了する時刻ｔ５まで保留される。
【００５９】
この待ち時間の間に、帯域制御部４２−１は、最低保証帯域のレベルカウント値の減算動作を繰り返し、レベルカウント値が閾値を大きく下回った状態となる。帯域制御部４２−１は、時刻ｔ５で排出許可を得て、バッファメモリ４１−１からフレームＦＲａ２の排出を開始する。フレームＦＲａ２の排出に伴うフレーム長の加算によって、帯域制御部４２−１のレベルカウント値は上昇するが、最低保証帯域のレベルカウント値は、図（Ｃ）に示すように、閾値を下回った状態にある。
【００６０】
従来方式の帯域制御によれば、このようにレベルカウント値が閾値を下回っていれば、最低保証帯域のフレーム排出要求が発生する。従って、フレームＦＲａ２の排出が完了した時、もし、他の帯域制御部からのフレーム排出要求が無ければ、帯域制御部４２−１に対して直ちに次のフレームの排出許可が与えられることになる。しかしながら、本発明の場合、帯域制御部４２−１は、最低保証帯域排出タイミング判定部４２０に論理積回路４２７を備えているため、最低保証帯域のフレーム排出要求ＲＥＱ１は、最大許容帯域のフレーム排出要求ＲＥＱ２が発生する迄、すなわち、最大許容帯域のレベルカウント値が閾値に達する時刻ｔ６まで、発行を抑制される。
【００６１】
帯域制御部４２−１は、時刻ｔ６で、最低保証帯域のフレーム排出要求ＲＥＱ１と、最大許容帯域のフレーム排出要求ＲＥＱ２を同時に発行する。ここに示した例では、図（Ｅ）、（Ｆ）に示すように、時刻ｔ６では、帯域制御部４２−２のレベルカウント値が、最低保証帯域、最大許容帯域ともに閾値に未達状態となっているため、読出し制御部４４は、帯域制御部４２−１に対してフレーム排出許可を与える。従って、帯域制御部４２−１は、時刻ｔ６でバッファメモリ４１−１からのフレームＦＲａ３の排出を開始する。一方、帯域制御部４２−２では、図（Ｆ）、（Ｇ）に示すように、フレームＦＲａ３が出力回線に送出中の時刻ｔ７において、最大許容帯域のレベルカウント値が閾値に達し、フレーム排出要求ＲＥＱ２を発行する。
【００６２】
フレームＦＲａ３の排出が完了した時点ｔ８では、排出要求としては、帯域制御部４２−２からの最大許容帯域のフレーム排出要求ＲＥＱ２のみが存在しているため、読出し制御部４４は、帯域制御部４２−２に排出許可を与える。これによって、時点ｔ８で、バッファメモリ４１−２からのフレームＦＲｂ２の排出が開始され、フレームＦＲｂ２の転送が完了した時刻ｔ９では、既にフレーム排出要求ＲＥＱ１、ＲＥＱ２を発生している帯域制御部４２−１に対して、排出許可が与えられる。
【００６３】
ここに示した例では、帯域制御部４２−２は、フレームＦＲｂ２を排出するとバッファメモリ４１−２が空になるため、最低保証帯域のレベルカウント値が閾値に達した時点で、減算処理部４２４によるレベルカウント動作を停止する。時刻ｔ９でフレームＦＲａ４の排出が完了した後は、図（Ｃ）、（Ｄ）、（Ｇ）に示すように、帯域制御部４２−１のみがフレームの排出と、フレーム排出に伴うレベルカウント値の更新と、最大許容帯域のレベルカウント値が閾値に達した時点でのフレーム排出要求ＲＥＱ２の発生を繰り返す。帯域制御部４２−１も、バッファメモリ４１−１が空になると、最低保証帯域のレベルカウント値が閾値に達した時点で、減算処理部４２４によるレベルカウント値の減算動作を停止する。
【００６４】
図（Ｇ）におけるフレームＦＲａ４、ＦＲａ５、ＦＲａ６の排出タイミングからも明らかなように、本発明によれば、特定フローに属したフレーム（パケット）がバースト的に排出される場合でも、フレームの排出を制御している帯域制御部に対して、予め設定された最大許容帯域を超えないようにフレーム排出許可を与えることができるため、仮に回線が空き状態になっても、特定のフローにおける一時的な帯域超過を防止したパケット転送制御が可能となる。
【００６５】
図８は、本発明によるシェーピング装置の第２の実施例を示す。
本実施例に示すシェーピング装置は、フローグループ別に用意された複数の初段シェーピング部４０１（４０１−１〜４０１−ｍ）と、これらの初段シェーピング部と出力回線インタフェースとの間に接続された第２段シェーピング部４０２とからなり、図３に示したフレーム振り分け部４００によって、スイッチング部３から出力ポートＰＯ−ｉに出力されたフレーム列を上記初段シェーピング部に選択的に振り分けるようにしている。
【００６６】
初段の各シェーピング部４０１は、それぞれ同一グループ内の特定のフローに属した可変長フレームを一時的に蓄積し、予めフロー毎に設定された最大許容帯域と最低保証帯域に従って蓄積フレームの出力タイミングを決定する複数の第１フロー制御部４１０（４１０−１〜４１０−ｋ）と、これらのフロー制御部に接続された第１読出し制御部４４０と、セレクタ４５０とからなる。第１読出し制御部４４０は、基本的には、図５に示した読出し制御部４４と同様の構成を有し、第１フロー制御部４１０は、第１実施例と同様、バッファメモリ４１１（４１１−１〜４１１−ｋ）と、帯域制御部４１２（４１２−１〜４１２−ｋ）と、フレーム長認識部４１３（４１３−１〜４１３−ｋ）とからなる。
【００６７】
一方、第２段シェーピング部４０２は、それぞれ初段シェーピング部４０１から出力される特定グループの可変長フレームを一時的に蓄積し、予めフローグループ毎に設定された最大許容帯域と最低保証帯域に従って蓄積フレームの出力タイミングを決定する複数の第２フロー制御部４０（４０−１〜４０−ｍ）と、フレーム排出要求を発行中の第２フロー制御部の中から所定のアルゴリズムで選択したフロー制御部４０−ｊに対して、フレームの排出許可を与える第２読出し制御部４４と、セレクタ４５とからなる。
【００６８】
第２読出し制御部４４は、図５に示した読出し制御部４４と同様の構成を有し、第２段シェーピング部の各フロー制御部４０は、初段シェーピング部４０１−１〜４０１−ｍの出力フレームを一時的に蓄積するバッファメモリ４１（４１−１〜４１−ｍ）と、バッファメモリ４１付随する帯域制御部４２（４２−１〜４２−ｍ）およびフレーム長認識４３（４３−１〜４４−ｍ）と、これらの帯域制御部４２−１〜４２−ｍに接続された第２読出し制御部４４と、フレーム長認識４３−１〜４４−ｍに接続されたセレクタ４５とからなる。
【００６９】
本実施例において、出力ポートＰＯ−ｉに接続されたフレーム振り分け部４００は、例えば、出力フレームのヘッダから抽出される宛先アドレス、タグ情報、優先度、フレーム長、サービスタイプ等のラベル情報によって、出力フレームの複数のグループに分ける。第１フローグループに属する出力フレームは、第１フローグループと対応する初段シェーピング部４０１−１のバッファメモリ４１１−１〜４１１−ｋに、フロー（コネクション）別に振り分けられる。同様に、第２〜第ｍフローグループの出力フレームは、これらのフローグループと対応する初段シェーピング部４０１−２〜４−１−ｍのバッファメモリ４１１−１〜４１１−ｋに、フロー別に振り分けられる。
【００７０】
初段の各シェーピング部４０１―ｊ（ｊ＝１〜ｍ）では、図３で説明したシェーピング装置４と同様の動作によって、各帯域制御部４１２（４１２−１〜４１２−ｋ）が、最大許容帯域のフレーム排出要求と最低保証帯域のフレーム排出要求を発行し、読出し制御部４４０からの排出許可信号に応答して、バッファメモリ４１１（４１１−１〜４１１−ｋ）に蓄積されたフロー別の可変長フレームをセレクタ４５０に出力する。この時、読出し制御部４４０は、図５に示した排出許可発行部４６０が、信号線Ｌ４２０を介して、第２段シェーピング部４０２の対応する帯域制御部４２に新たなフレーム（パケット）が入力されたことを通知する。
【００７１】
第２段のシェーピング部４０２では、図３で説明したシェーピング装置と同様、各帯域制御部４２（４２−１〜４２−ｍ）が、最大許容帯域のフレーム排出要求と最低保証帯域のフレーム排出要求を発行し、読出し制御部４４からの排出許可信号に応答して、バッファメモリ４１（４１−１〜４１−ｍ）に蓄積されたフローグループ別の可変長フレームをセレクタ４５を介して、出力回線インタフェースに送出する。
【００７２】
本実施例では、例えば、初段シェーピング部４０１−１の各バッファメモリ４１１−１〜４１１−ｋから排出されるパケットフローの最大許容帯域を１００Ｍｂｉｔ／ｓに設定し、これらの排出フレームの出力先となる第２段シェーピング部４０２のバッファメモリ４１−１のパケットフロー最大許容帯域を１００Ｍｂｉｔ／ｓに設定した場合、バッファメモリ４１０−１〜４１０−ｋから排出されるパケットフローは、個別フローもグループフローも最大許容帯域が１００Ｍｂｉｔ／ｓとなるように帯域制御されることになる。
【００７３】
従って、例えば、初段シェーピング部４０１−１の各バッファメモリ４１１（４１１−１〜４１１−ｋ）に同一ＶＬＡＮグループに属したｋ個のフローを割当て、これらをグループ化したＶＬＡＮグループのパケットフローをバッファメモリ４１−１に収容した場合、個々のフローで最大１００Ｍｂｉｔ／ｓの帯域を許容しつつ、ＶＬＡＮグループ全体としての最大許容帯域１００Ｍｂｉｔ／ｓに抑えたフロー制御が可能となる。本実施例によれば、バースト性の高いデータトラフィックについて、個々のユーザに高い許容帯域を与えつつ、これらのトラフィックが多重化される網ノードにおける最大帯域を指定値以下に抑えることが可能となる。
【図面の簡単な説明】
【００７４】
【図１】本発明が適用されるパケットスイッチ１０の構成例を示す図。
【図２】本発明のパケットスイッチ１０が適用されるネットワーク構成の１例を示す図。
【図３】パケットスイッチ１０に適用される本発明のシェーピング装置４−ｉの第１実施例を示す図。
【図４】本発明のシェーピング装置を構成する帯域制御部４２の１実施例を示す図。
【図５】本発明のシェーピング装置を構成する読出し制御部４４の１実施例を示す図。
【図６】本発明のシェーピング装置において、帯域制御部４２−１によるバッファメモリ４２−１からの可変長フレームの排出動作を説明するための図。
【図７】本発明のシェーピング装置において、２つのバッファメモリ４１−１、４１−２に着目した可変長フレームの排出動作を説明するための図。
【図８】本発明のシェーピング装置の第２実施例を示す図。
【図９】リーキーバケットを適用した従来の帯域制御の問題点を説明するための図。
【符号の説明】
【００７５】
１０：パケットスイッチ、２：入力回線インタフェース、３：スイッチング部、
４：シェーピング装置、５：出力回線インタフェース、６：ノード制御部、
４００：フレーム振り分け部、４１、４１１：バッファメモリ、
４２、４１２：帯域制御部、４３、４１３：フレーム長認識部、
４４、４４０：読出し制御部、４５、４５０：セレクタ、４１０：排出制御部、
４２０：最低保証帯域排出タイミング判定部、４３０：最大許容帯域排出タイミング判定部、４４０：最低保証帯域排出候補選択部、４５０：最大許容帯域排出候補選択部、
４６０：排出許可発行部、４７０：排出候補決定アルゴリズム記憶部。
【図１】
2005333544.tif 000003
【図２】
2005333544.tif 000004
【図３】
2005333544.tif 000005
【図４】
2005333544.tif 000006
【図５】
2005333544.tif 000007
【図６】
2005333544.tif 000008
【図７】
2005333544.tif 000009
【図８】
2005333544.tif 000010
【図９】
2005333544.tif 000011
【手続補正書】
【提出日】平成16年5月28日(2004.5.28)
【手続補正１】
【補正対象書類名】図面
【補正対象項目名】図８
【補正方法】変更
【補正の内容】
【図８】
2005333544.tif 000012