(57)【要約】【課題】多数のユーザグループを収容するシェーパにおいて、ユーザグループ毎の帯域監視を高速に実行する。また、ユーザグループ毎の使用帯域に余剰帯域のある場合にこれを有効活用しながら、ユーザ毎に契約された最低帯域を必ず保証する。【解決手段】帯域監視を受けた複数のユーザグループのパケットを、同一のパケット蓄積ＦＩＦＯに蓄積する。また、ユーザ毎契約帯域に違反していないパケットに対しては、ユーザグループ毎契約帯域に違反していないと判定することによりユーザ毎契約帯域を保証する。【効果】ユーザグループ毎の帯域監視を高速に実行できる。また、ユーザ毎に契約された最低帯域を必ず保証する。更にユーザグループ毎の使用帯域に生じた余剰帯域を有効活用する。【選択図】  図１０
2005039390.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークに流入したパケットに対し、該パケットの送信元の契約帯域に違反していないかどうか監視し、該パケットが契約帯域内であれば当該パケットを優先的に送信し、違反した場合は当該パケットを非優先パケットとして送信する帯域監視方法であって、
前記帯域監視を前記パケットの属するフローに対して行ない、
前記帯域監視を複数のフローから構成されるフローグループに対して行ない、
前記流入パケットが前記フロー毎に行なった帯域監視に違反していない場合、前記フローグループ毎に行なった帯域監視に違反する場合であっても、前記パケットを優先パケットとして送信することを特徴とする帯域監視方法。
【請求項２】
請求項１に記載の帯域監視方法において、前記フロー毎契約帯域として前記フロー毎に保証された最低帯域を使用し、前記フローグループ毎契約帯域として前記フローグループに属するフローに保証された最低帯域の総和以上の値を使用することを特徴とする帯域監視方法。
【請求項３】
請求項１に記載の帯域監視方法において、前記フロー毎契約帯域として前記フロー毎に保証された最低帯域を使用し、前記フローグループ毎契約帯域として前記フローグループとして制限された最大帯域を使用することを特徴とする帯域監視方法。
【請求項４】
請求項３に記載の帯域監視方法において、前記流入パケットが、前記フロー毎帯域監視に違反し、かつ前記フローグループ帯域監視に違反する場合には、当該流入パケットを廃棄することを特徴とする帯域監視方法。
【請求項５】
請求項１に記載の帯域監視方法において、前記前記フローグループの契約帯域を超過したパケット分の超過帯域に関する情報を超過帯域情報として記憶し、
前記パケットが該パケットの属するフロー毎契約帯域に違反している場合には、前記記憶された超過帯域を前記フローグループ毎契約帯域から差し引いて前記フローグループ毎帯域監視を行なうことを特徴とする帯域監視方法。
【請求項６】
請求項１から５のいずれか１項に記載の帯域監視方法において、帯域監視のアルゴリズムとしてリーキーバケットアルゴリズムを用いることを特徴とする帯域監視方法。
【請求項７】
請求項６に記載の帯域監視方法において、前記フロー毎に行なう帯域監視においてフロー毎契約帯域に違反していないと判定されたパケットに対しては、フローグループ毎帯域監視におけるリーキーバケットアルゴリズムのバケツの深さに関わらず、フローグループ毎契約帯域に違反していないと判定してこれをバケツに蓄積して、ここでバケツに蓄積された水量が前記超過帯域情報であることを特徴とする帯域監視方法。
【請求項８】
複数の入力回線を収容する複数のパケット受信回路と、複数の出力回線を収容する複数のパケット送信回路と、前記パケット受信回路で受信したパケットを前記複数の出力回線のいずれへ転送するか決定するルーティング処理部と、該ルーティング処理部と前記複数のパケット送信回路の各々とのパケット転送経路上に設けられる複数の帯域監視部と、廃棄制御部と、前記ルーティング処理部を通過したパケットを前記複数の帯域監視部のいずれかへスイッチングするパケット中継処理手段とを有し、
前記帯域監視部は、
受信したパケットの属するフローを検出するフロー検出部と、
該検出したフローの属するフローグループを検出するフローグループ検出部と、
前記検出したフロー毎に契約帯域を監視するためのフロー毎帯域監視部と、
前記検出したフローグループ毎に契約帯域を監視するためのフローグループ毎帯域監視部と、
前記フロー毎帯域監視部とフローグループ帯域監視部との監視結果を基に、前記受信パケットを優先パケットか非優先パケットに弁別する監視結果総合判定部とを備え、
該監視結果総合判定部は、前記受信パケットが前記フロー毎に行なった帯域監視に違反していない場合、前記フローグループ毎に行なった帯域監視に違反する場合であっても、前記パケットを優先パケットとして前記パケット送信回路へ転送することを特徴とするパケット転送装置。
【請求項９】
請求項７に記載の帯域監視装置において、
前記フロー毎帯域監視手段は、フロー帯域監視テーブルと、入力パケットの属するフローに対応するフロー毎帯域監視エントリをフロー毎帯域監視テーブルから読み出すフロー毎帯域監視テーブル制御手段と、フロー毎帯域監視のための制御情報と現時刻を表すタイマーの値とに基づいて入力パケットのフロー毎契約帯域遵守・違反の判定を行なうフロー毎監視結果判定手段とを備え、
前記フローグループ毎帯域監視手段は、フローグループ毎帯域監視テーブルと、入力パケットの属するフローグループに対応するフローグループ毎帯域監視エントリを前記フローグループ毎帯域監視テーブルから読み出すフローグループ毎帯域監視テーブル制御手段と、フローグループ毎帯域監視のための制御情報と現時刻を表すタイマーとの値に基づいて入力パケットのフローグループ毎契約帯域遵守・違反の判定を行なうフローグループ毎監視結果判定手段とを備え、
前記フロー帯域監視テーブルは、
フロー毎契約帯域、フロー毎のバケツの深さ及びフロー毎のバケツの水量と前回のフロー毎帯域監視時刻を含むフロー毎帯域監視制御情報と、フロー毎契約帯域に違反しているパケットに与える制裁として廃棄またはネットワーク優先度書き換えまたは制裁無しを指示するフロー毎制裁情報とを含むフロー毎帯域監視エントリを備え、
前記フローグループ毎帯域監視テーブルは、
フローグループ毎契約帯域、フローグループ毎のバケツの深さ、フローグループ毎のバケツの水量と前回のフローグループ毎帯域監視時刻とを含むフローグループ毎帯域監視制御情報と、フローグループ毎契約帯域に違反しているパケットに与える制裁として廃棄またはネットワーク優先度書き換えまたは制裁無しを指示するフローグループ毎制裁情報とから構成されるフローグループ毎帯域監視エントリとを備えることを特徴とするパケット転送装置。
【請求項１０】
請求項９に記載の帯域監視装置において、
前記フロー毎契約帯域に違反していないパケットに対しては制裁を与えず、フロー毎契約帯域に違反していてフローグループ毎契約帯域に違反していないパケットに対してはフロー毎制裁情報で指定された制裁を与え、フロー毎契約帯域とフローグループ毎契約帯域共に違反しているパケットに対してはフロー毎制裁情報で指定された制裁またはフローグループ毎制裁情報で指定された制裁を与えることを特徴とするパケット転送装置。
【請求項１１】
請求項８から１０のいずれか１項に記載のパケット転送装置において、パケットを蓄積するパケット蓄積ＦＩＦＯと、前記パケット蓄積ＦＩＦＯに蓄積しているパケット数をカウントするカウンタと、前記パケット蓄積ＦＩＦＯへのパケットの蓄積・廃棄を判定する廃棄制御部とを備え、
複数のフローグループのパケットが同一のパケット蓄積ＦＩＦＯに蓄積されることを特徴とする帯域監視装置。
【請求項１２】
請求項１１に記載のパケット転送装置において、
前記フロー毎制裁情報または前記フローグループ毎制裁情報は、各々パケット蓄積ＦＩＦＯに対するキューイング優先度書き換えを含み、
前記廃棄制御部は、前記パケット蓄積ＦＩＦＯへのパケットの蓄積・廃棄を判定する際に参照する閾値をキューイング優先度毎に保持することを特徴とするパケット転送装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケットの制御方法及び転送装置、特にネットワークに流入するパケットの帯域を監視する帯域監視方法および帯域監視装置に関する。
【０００２】
【従来の技術】
インターネットをはじめとするＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）ネットワークで用いられるパケット型通信方式では、多数のユーザが回線を共用できるので従来の専用回線よりも通信コストの低減が可能となる。この低コスト性を活かして、従来は専用回線を流れていた音声データ、企業のミッションクリティカルデータ等をＩＰネットワークに適用する要求がでてきた。このため、Ｂｅｓｔ  Ｅｆｆｏｒｔ型サービスが主流であった従来のＩＰネットワークにおいて、専用回線のもつ低遅延、低廃棄率等の通信品質を実現する必要性が増している。
【０００３】
通信品質を実現するサービスの一つに、ＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ  Ｔｒａｎｓｆｅｒ  Ｍｏｄｅ）網のＡＴＣ（ＡＴＭ  Ｔｒａｎｓｆｅｒ  Ｃａｐａｂｉｌｉｔｙ）として規定されるＧＦＲ（Ｇｕａｒａｎｔｅｅｄ  Ｆｒａｍｅ  Ｒａｔｅ）がある。ＧＦＲでは、契約された最低帯域を保証すると共に、余剰帯域があれば最低帯域を超過する通信も許すことにより帯域を有効活用できる。
【０００４】
帯域制御の必要性について、図３を用いて説明する。なお、図３はネットワークの構造を示すための一例であって、従来技術であっても本願発明であっても適用が可能であることは言うまでもない。図３において、エッジノードＣ１の出力回線はＩＳＰ（Ｉｎｔｅｒｎｅｔ  Ｓｅｒｖｉｃｅ  Ｐｒｏｖｉｄｅｒ）サイトＡ、ＩＳＰサイトＢ両方からのフローにより共有されている。従って、通信回線に輻輳が生じた際には通信品質の劣化点となり易い。よって、エッジノードＣ１では、送信パケットに対する帯域制御が必要となる。
【０００５】
帯域制御のためには、まず、各ユーザ毎に契約された最低帯域を監視してこれを保証することが必要である。ＩＳＰサイトＡの収容ユーザＡ１￣Ａ３の通信品質を保証するためである。同時に、輻輳を防止してキャリアバックボーンネットワーク内の帯域資源を守るため、ユーザＡ１〜Ａ３を束ねたグループであるユーザグループＡとしての最大帯域を監視して制限をかける必要もある。なお、各ユーザＡ１〜Ａ３は、各々保証された最低帯域を使い切った場合にも、ユーザグループＡとして最大帯域を超過しない限り余剰帯域を用いてパケットの送受信が可能である。また、ユーザグループ当たりの収容コスト低減のため、エッジノードＣ１には複数のユーザグループが収容され、ユーザグループ毎に帯域監視が実行される。
【０００６】
特開２００１−３２６６８８号公報（以下、従来技術１）には、ユーザ毎に最低帯域を保証するシェーピング装置が開示されている。従来技術１では、ＡＴＭにおける固定長パケットであるセルの帯域監視アルゴリズムであるｃｏｎｔｉｎｕｏｕｓ  Ｌｅａｋｙ  Ｂｕｃｋｅｔ  Ａｌｇｏｒｉｔｈｍ（以下、リーキーバケットアルゴリズムと称す。）を、ＩＰの可変長パケットに拡張した帯域監視アルゴリズムを用いている。リーキーバケットアルゴリズムはある深さを持った穴の空いた漏れバケツのモデルで、バケツに水が入っている間は監視帯域で水は漏れ続け、パケット入力時にはこのパケットのバイト長分の水が注ぎ込まれる。パケットの到着揺らぎを許容するためにバケツはある程度の深さを持ち、バケツが溢れるまでは入力パケットは遵守パケットと、溢れると違反パケットと判定される。
【０００７】
従来技術１より引用したシェーピング装置の概念図を図１に示す。図１に示したシェーピング装置は、受信パケットの内部転送処理を行なうパケット中継処理手段と、処理の終わったパケットを送信するパケット送信回路の間に設けられたものとする。
シェーパ部１００にパケットが到着すると、廃棄制御部１１０は到着パケットの「蓄積」「廃棄」を判定する。パケット蓄積ＦＩＦＯ１２０は「蓄積」と判定したパケットを蓄積し、各ユーザ毎に契約された最低帯域の総和以上の帯域で送信する。帯域監視部１３０は、ユーザ毎に帯域をチェックして、最低帯域以内のパケットを優先パケットと、それ以外を非優先パケットと判定する。優先パケットに対するＦＩＦＯ閾値を非優先パケットに対するＦＩＦＯ閾値よりも深く設定することにより、優先パケットを優先的に「転送」と判定して優先パケットを保護し、各ユーザ毎に最低帯域を保証する。ここで、ＦＩＦＯとはパケットを蓄積するメモリの一種であって、データを格納したり、格納したデータを取り出して使用する場合に，格納した順番どおりに、先に格納したデータが取り出せる構成のメモリ，またはそのような記憶方法をいう。なお、ＦＩＦＯとは、Ｆｉｒｓｔ  Ｉｎ  Ｆｉｒｓｔ  Ｏｕｔの略である。
【０００８】
従来技術１のシェーピング装置を図３のエッジノードＣ１に適用すれば、上述の帯域制御が可能である。帯域監視部１３０により、受信パケットユーザ毎にパケットの帯域監視を実行し、優先パケット／非優先パケットの弁別が実行される。最低帯域内に収まっているパケットは、優先パケットとして処理される。すなわち、パケット蓄積ＦＩＦＯ１２０に対するキューイング優先度が高優先に設定される。一方、ユーザ毎の最低帯域を超過するパケットは非優先パケットとして処理される。すなわち、パケット蓄積ＦＩＦＯ１２０に対するキューイング優先度を低優先に設定される。これにより、ユーザ毎の最低帯域保証を実現できる。
また、パケットユーザグループの最大帯域制限は、パケット蓄積ＦＩＦＯ１２０からのパケット送信帯域を任意の値に設定することで実現可能である。なお、パケット蓄積ＦＩＦＯ１２０に蓄積するパケットは、特定のユーザグループ、例えばユーザグループＡのパケットに限定されている。すなわち、当該シェーパ１００は、ユーザグループの数に応じて設けられている。
【０００９】
Ｉｎｔｅｒｎｅｔ  ＳｏｃｉｅｔｙのＲＦＣ２６９８には、最低帯域と最大帯域の二つの帯域監視結果から、パケットの弁別を行なう際の弁別法として２Ｒａｔｅ  ３Ｃｏｌｏｒ  Ｍａｒｋｅｒ（以下、従来技術２）が開示されている。図２には、従来技術２の処理の流れをフローチャートで示す。従来技術２では、まずユーザ毎の使用帯域が最大帯域を超過していないか判定し、超過している場合は廃棄パケットと判定してパケットを廃棄する。超過していない場合は、次にユーザ毎の使用帯域が最低帯域を超過していないか判定する。最低帯域を超過している場合はこのパケットを非優先パケットと判定し、制裁として例えばキューイング優先度を低優先として輻輳時に優先的に廃棄されるパケットとする。超過していない場合はこのパケットを優先パケットと判定して、輻輳時にも廃棄され難くなるようキューイング優先度を高優先とする。
【００１０】
【発明が解決しようとする課題】
従来技術１に開示されたシェーピング装置に複数のユーザグループを収容しようとする場合、ユーザグループ毎に最大帯域を制限するためには、ユーザグループ毎にパケット蓄積ＦＩＦＯを設けて、パケット蓄積ＦＩＦＯからの送信帯域を最大帯域以下に制限する必要がある。従って、収容ユーザグループ数が増加すると、所持すべきパケット蓄積ＦＩＦＯの本数も増加する。パケットを送信すべきパケット蓄積ＦＩＦＯを判定する時間は、パケット蓄積ＦＩＦＯの数と共に増加するので、多数のユーザグループを収容する場合、パケット蓄積ＦＩＦＯの判定に要する判定処理時間は、収容するユーザグループ数に応じて増加する。よって、多数のユーザグループを収容する場合、高速に帯域制御できないという課題がある。更に、多数のユーザグループを収容する場合、多数のパケット蓄積ＦＩＦＯが必要となるので、パケット蓄積ＦＩＦＯを所持するためのコストが収容ユーザグループ数に比例して増加するという課題もある。
ＦＩＦＯの替りに汎用の大型メモリを用いて、種類の異なるユーザグループに属するパケットをバッファリングすれば、原理的にはユーザグループに応じてパケット蓄積ＦＩＦＯを設ける必要はなくなるが、どのユーザグループに属するパケットを引き出すかという処理が必要になる。従って、処理が複雑化する上、メモリの読み出し速度も早くないので、結局高速な帯域制御はできない。
【００１１】
また、従来技術２に記載された技術は、帯域監視結果を利用して、受信パケットを優先パケット／非優先パケット／廃棄パケットに弁別するための技術なので、従来技術１に記載のリーキーバケットアルゴリズムと組み合わせても課題の解決にはならない。
【００１２】
本発明の第一の目的は、従来技術１の課題を解決して、ユーザ毎に帯域監視すると共に、複数ユーザから構成されるユーザグループを多数収容してユーザグループ毎にも帯域監視することのできる高速な帯域監視装置を提供することにある。更に、この帯域監視装置を用いて多数のユーザグループを収容することにより、ユーザグループ当たりの収容コスト
を低減する効果を得ることにある。
【００１３】
【課題を解決するための手段】
本発明の帯域監視装置は、パケットの属するユーザ毎の契約帯域を帯域監視するユーザ毎帯域監視手段と、複数のユーザから構成されるユーザグループ毎の契約帯域を帯域監視するユーザグループ毎帯域監視手段とを備え、複数のユーザのみならず複数のユーザグループのパケットが同一のパケット蓄積ＦＩＦＯに蓄積されることを特徴とする。本発明の帯域監視装置によれば、収容するユーザグループ数が増加しても常に一つのパケット蓄積ＦＩＦＯからパケットを出力するので、複数のパケット蓄積ＦＩＦＯからパケットを出力するパケット蓄積ＦＩＦＯを選択する必要がないので、収容するユーザグループ数が増加しても高速に帯域監視することができる。
【００１４】
なお、契約帯域は必ずしもユーザ毎またはユーザグループ毎である必要はなく、一般的には入力パケットのアドレス情報、用途を識別する情報またはネットワーク内の優先度を識別する情報であるネットワーク優先度のうち、少なくとも一つの情報から識別されるフロー毎、または複数のフローから構成されるフローグループ毎とすることができる。この場合、本発明の帯域監視装置はパケットの属するフローを検出するフロー検出手段と、検出したフローの属するフローグループを検出するフローグループ検出手段とを備え、フロー検出手段で検出したフロー毎に契約帯域を監視するためのフロー毎帯域監視手段と、フローグループ検出手段で検出したフローグループ毎に契約帯域を監視するためのフローグループ毎帯域監視手段を備え、複数のフローグループのパケットが同一のパケット蓄積ＦＩＦＯに蓄積されることを特徴とする。
【００１５】
【発明の実施の形態】
従来技術２に記載されたパケットの弁別基準を従来技術１のシェーパに適用して上記の帯域制御を行うと新たに別の課題が発生する。帯域監視部１３０にてユーザ毎の最低帯域を監視して最低帯域以内のパケットを優先パケットとしてパケット蓄積ＦＩＦＯ１２０に対するキューイング優先度を高優先とし、ユーザ毎の最低帯域を超過するパケットは非優先パケットとしてキューイング優先度を低優先とする。更に、帯域監視部１３０にてユーザグループ毎の最大帯域を監視して最大帯域を超過するパケットを廃棄する。
このときの課題を、図４（Ａ）を用いて説明する。まず、図４（Ａ）の左図のようにユーザＡ１〜Ａ３のうちユーザＡ１だけが通信している状態を考え、ユーザＡ１はユーザ毎に契約された最低帯域を使い切った上で、更にユーザグループＡに属する他のユーザが未使用の余剰帯域を利用してユーザグループＡの最大帯域まで占有して通信しているものとする。このときユーザＡ２のパケットが入力し始めると、図４（Ａ）の右図のようにユーザグループＡのバケツ閾値を超過してしまう。従来技術２では、まず最大帯域監視の判定から行うので、ユーザＡ２のパケットはユーザ毎の最低帯域を使いきっていないにも関わらず、ユーザグループ毎の最大帯域を超過と判定されるので廃棄されてしまう。このように、従来技術２で複数ユーザをまとめる最大帯域監視を論理的に先判定すると、ユーザ毎の最低帯域を必ずしも保証できないという課題がある。
【００１６】
本発明のパケット転送装置は、フローグループ毎契約帯域の全てが使用されている場合にネットワークに流入したパケットに対して、該パケットが該パケットの属するフロー毎契約帯域に違反していない場合には、フローグループ毎契約帯域に違反していないと判定することによりフロー毎契約帯域を保証すると共に、フローグループ毎契約帯域を超過した該パケット分の超過帯域を超過帯域情報として記憶しておく一方、該パケットが該パケットの属するフロー毎契約帯域に違反している場合には、前記の超過帯域情報として記憶している超過帯域をフローグループ毎契約帯域から差し引いてフローグループ毎帯域監視を行なうことにより、フロー毎契約帯域に違反しているパケットと違反していないパケットを合わせた使用帯域としてフローグループ毎契約帯域を超過する帯域が割り当てられないことを特徴とする。
これにより、従来技術２の課題が解決される理由は、次の通りである。例として、帯域監視のアルゴリズムがリーキーバケットアルゴリズムである場合を説明する。まず、図４−２の左図のようにユーザＡ１はユーザ毎の最低帯域を使い切った上で、更に余剰帯域を利用してユーザグループＡの最大帯域まで占有して通信しているものとする。このときユーザＡ２のパケットが入力し始めると、図４−２の右図のようにユーザグループＡのバケツ閾値を超過する。従来技術２では、まず最大帯域の判定から論理的に先に行うので、ユーザＡ２のパケットは最大帯域超過と判定されて廃棄となってしまい、ユーザＡ２の最低帯域は必ずしも保証できない。
しかし、本発明によれば、図５のユーザグループ毎の契約帯域が最大帯域の場合は上図、ユーザグループ毎の契約帯域が最低帯域の場合は下図のように、まずユーザ毎の契約帯域である最低帯域の判定から論理的に先に行なう。すると、ユーザＡ２のパケットが入力し始めたとき、このパケットはユーザＡ２の契約帯域に違反していないのでユーザグループＡの契約帯域にも違反していないと判定され、ユーザＡ２のバケツにはこのパケットに相当する水量が蓄積されるのみならず、これと同じ水量がユーザグループＡのバケツには閾値を溢れて蓄積される。従って、ユーザＡ２の契約帯域は必ず保証される。
【００１７】
一方、この状態でユーザＡ１のパケットが入力すると、このパケットはユーザＡ１の契約帯域に違反しており、更にユーザグループＡの契約帯域にも違反しているものとみなされるので、ユーザグループＡの最大帯域制限を受けて廃棄される。このように、ユーザ毎契約帯域に違反していないユーザのパケットとユーザ毎契約帯域に違反しているパケットとが競合する場合、ユーザ毎契約帯域に違反していないパケットはユーザグループ毎契約帯域を違反していないと判定されてユーザグループ毎のバケツに蓄積される一方、ユーザ毎契約帯域に違反しているパケットはユーザグループ毎契約帯域に違反していると判定されるので、ユーザグループ毎のバケツに蓄積されない。従って、ユーザ毎契約帯域に違反していないパケットはユーザグループ毎契約帯域にも違反せず必ず最低帯域を保証できるのに対し、ユーザ毎契約帯域に違反しているパケットはユーザグループ契約帯域に違反した場合優先的に廃棄されることで、ユーザ毎契約帯域を使い切ったユーザと使い切っていないユーザとの間で使用帯域が調整されることとなる。
尚、本発明ではユーザグループ毎契約帯域をユーザ毎契約帯域の総和以上とする必要がある。その理由は、ユーザグループ毎契約帯域がユーザ毎契約帯域の総和未満である場合、全てのユーザがユーザ毎契約帯域を全て使用してパケットを送信し続けると、ユーザグループの帯域を監視するバケツが溢れ続けてしまい、ユーザグループ毎契約帯域を超過する状態が恒常的に続いてしまうからである。ユーザグループ毎契約帯域がユーザ毎契約帯域の総和以上である場合は、ユーザ毎契約帯域に違反していないパケットが過剰にユーザグループ毎のバケツに蓄積された場合にも、ユーザ毎契約帯域以上の帯域でユーザグループ毎のバケツからは水が漏れ続けている。更に、ユーザ毎契約帯域に違反しているパケットのユーザグループ毎帯域監視において、ユーザグループ毎契約帯域から前記の過剰にユーザグループ毎のバケツに蓄積された分の超過帯域は差し引かれる。従って、ユーザ毎契約帯域に違反しているパケットに対しては、ユーザ毎契約帯域に違反していないパケットが超過した分の帯域が使用帯域として割り当てられないので、フロー毎契約帯域に違反しているパケットと違反していないパケットを合わせた使用帯域としてユーザグループ毎契約帯域を超過する帯域は割り当てられない。
【００１８】
ユーザ毎契約帯域とユーザグループ毎契約帯域の例として、例えばユーザ毎に保証された最低帯域をユーザ毎契約帯域とし、ユーザグループ毎契約帯域はユーザグループに属するユーザ毎に保証された最低帯域の総和とすることができる。この場合、ユーザ毎最低帯域を必ず保証すると共に、ユーザグループ毎契約帯域に余剰帯域のある場合はこれを有効活用できるように帯域監視することができる。
【００１９】
また、ユーザ毎に保証された最低帯域をユーザ毎契約帯域とし、ユーザグループ毎契約帯域はユーザグループとして制限したい最大帯域とすることができる。この場合、ユーザ毎最低帯域を必ず保証すると共に、ユーザグループとしての最大帯域を制限しながら余剰帯域のある場合にはこれを有効活用できるように帯域監視することができる。
この場合も、契約帯域は必ずしもユーザ毎またはユーザグループ毎である必要はなく、一般的には入力パケットのアドレス情報、用途を識別する情報またはネットワーク内の優先度を識別する情報であるネットワーク優先度のうち少なくとも一つの情報から識別されるフロー毎または複数のフローから構成されるフローグループ毎とすることができる。
【００２０】
まず、本発明を適用したパケット転送装置の構成概要を、図６を用いて説明する。パケット転送装置６００は、パケットが入力するＮ個の入力回線６１０−ｉ（ｉ＝１〜Ｎ）と、パケットの受信処理を行うパケット受信回路６２０−ｉと、ルーティング処理部６３０と、パケットをスイッチングするパケット中継処理手段６４０と、出力回線毎の帯域監視部６５０−ｊ（ｊ＝１〜Ｍ）と、廃棄制御部６６０−ｊと、送信処理を行うパケット送信回路６７０−ｊと、パケットが出力されるＮ個の出力回線６８０−ｊから構成される。
【００２１】
図７は、本発明が想定する図３に示したＩＰネットワークにおけるパケットのフォーマットの一例を示す。パケットはヘッダ部７１０とデータ部７２０から構成される。ヘッダ部７１０は送信元ＩＰアドレス（Ｓｏｕｒｃｅ  ＩＰ  ａｄｄｒｅｓｓ：以下「ＳＩＰ」と称する。）７１１と、宛先ＩＰアドレス（Ｄｅｓｔｉｎａｔｉｏｎ  ＩＰ  ａｄｄｒｅｓｓ：以下「ＤＩＰ」と称する。）７１２と、サービス識別子（Ｔｙｐｅ  ｏｆ  Ｓｅｒｖｉｃｅ：以下「ＴＯＳ」と称する。）７１３から構成される。また、データ部７２０はユーザデータ７２１から構成される。ヘッダ部７１０には、前記情報以外にも生存時間（ＴＴＬ：Ｔｉｍｅ  ｔｏ  Ｌｉｖｅ）等の情報も格納されているが、前記情報と同様に後述の処理を実行できる。
【００２２】
図８は、本発明を適用したパケット転送装置６００内部におけるパケットのフォーマットの一例を示す。パケット転送装置６００内部のパケットのフォーマットには、ＩＰネットワークのパケットのフォーマットに内部ヘッダ８１０が加わる。内部ヘッダ８１０はパケットが入力した回線の識別子である入力回線番号８１１と、パケットが出力される回線の識別子である出力回線番号８１２と、パケットのバイト長を表すパケット長８１３と、帯域監視の結果指示された廃棄制御部６６０−ｊにおけるパケット蓄積ＦＩＦＯ６６５−ｊに対する蓄積・廃棄を指示する蓄積廃棄指示８１４と、パケット蓄積ＦＩＦＯ６６５−ｊに対するキューイング優先度８１５とから構成される。
【００２３】
次に、本発明を適用したパケット転送装置の動作概要を、図６を用いて説明する。パケット転送装置６００の入力回線６１０−ｉからパケットが入力すると、パケット受信回路６２０−ｉは内部ヘッダ８１０を付加し、パケットのバイト長を計算した上でパケット長８１３（単位はＢｙｔｅ）に書き込む。更に、パケットが入力した入力回線６１０−ｉを入力回線番号８１１に書き込み、ルーティング処理部６３０へパケットを送信する。尚、この時点では出力回線番号８１２は無意味な値となっている。ルーティング処理部６３０は、パケットを受信するとＤＩＰ７１２に基づいてパケットを出力する回線６８０−ｊを判定し、出力回線６８０−ｊの回線番号ｊを出力回線番号８１２に書き込みパケット中継処理手段６４０に送信する。パケット中継処理手段６４０は出力回線番号８１２に従ってパケットをスイッチングし、出力回線毎の帯域監視部６５０−ｊに送信する。
【００２４】
帯域監視部６５０−ｊは、ＳＩＰ７１１に基づいてパケットの属するユーザと、パケットの属するユーザグループとを検出し、各ユーザ毎の帯域監視と各ユーザグループ毎の帯域監視を行ない、ユーザ毎に契約された最低帯域を必ず保証すると共に、更にユーザグループ毎の使用帯域に余剰帯域のある場合はこれを有効活用できるよう帯域監視を行なう。この帯域監視部６５０−ｊの詳細動作については後述する。帯域監視されたパケットに対して、帯域監視の結果指示された廃棄制御部６６０−ｊにおけるパケット蓄積ＦＩＦＯ６６５−ｊに対する蓄積・廃棄の指示を蓄積廃棄指示８１４に、パケット蓄積ＦＩＦＯ６６５−ｊに対するキューイング優先度をキューイング優先度８１５に書き込み、廃棄制御部６６０−ｊに送信する。
【００２５】
廃棄制御部６６０−ｊに送信されたパケットは、一旦一時蓄積バッファ６６２−ｊに蓄積される。帯域監視部６５０−ｊから送信されたパケットの蓄積廃棄指示８１４に基づき、「廃棄」と指示された場合には、一時蓄積バッファ６６２−ｊからパケット蓄積ＦＩＦＯ６６５−ｊにパケットを送信しない。そして、「廃棄」と判定されたパケットの次に廃棄制御部６６０−ｊに到着したパケットの情報を上書きする。「蓄積」と指示された場合には、キューイング優先度毎閾値蓄積手段６６１−ｊからキューイング優先度８１５に対するパケット蓄積ＦＩＦＯ６６５−ｊの閾値を参照して、この閾値とＦＩＦＯカウンタ６６４−ｊの値を比較する。この閾値がＦＩＦＯカウンタ６６４−ｊより大きい場合には、「蓄積」と判定してパケットをパケット蓄積ＦＩＦＯ６６５−ｊに送信すると共に、ＦＩＦＯカウンタ６６４−ｊの値に１加算する。閾値がＦＩＦＯカウンタ６６４−ｊ以下の場合には、「廃棄」と判定してパケットをパケット蓄積ＦＩＦＯ６６５−ｊに送信せず、ＦＩＦＯカウンタ６６４−ｊの値に加算しない。そして、「廃棄」と判定されたパケットの次に廃棄制御部６６０−ｊに到着したパケットの情報を上書きする。
【００２６】
パケット出力制御部６６６−ｊはパケット蓄積ＦＩＦＯ６６５−ｊに蓄積した順番に回線帯域でパケットを送信するようにパケット送信起動信号６６７−ｊを送信し、この信号を受信したパケット蓄積ＦＩＦＯ６６５−ｊはパケット送信回路６７０−ｊへパケットを送信する。また、ＦＩＦＯカウンタ６６５−ｊは前記パケット送信起動信号６６７−ｊを受信するとＦＩＦＯカウンタ６６５−ｊから１減算する。本発明では、パケット出力制御部６６６−ｊは回線帯域でパケットを送信するようにパケット送信起動信号６６７−ｊを送信するが、ネットワーク運用者によって設定された回線帯域以下の帯域（例えば、回線帯域の半分）で送信しても良い。パケット送信回路６７０−ｊへ送信されたパケットは、内部ヘッダ８１０を外されて出力回線６８０−ｊへ送信される。
【００２７】
本発明の帯域監視部６５０−ｊでは、ユーザ毎帯域監視とユーザグループ毎帯域監視を行なってユーザグループ毎の契約帯域を超過するパケットに対する廃棄、またはサービス識別子７１３またはキューイング優先度８１５の書き換え指示がなされている。従って、廃棄制御部６６０−ｊでは廃棄指示、またはキューイング優先度８１５に従って廃棄制御を行なうことにより、ユーザ毎およびユーザグループ毎の帯域制御が可能となる。ユーザグループ毎にパケット蓄積ＦＩＦＯ６６５−ｊを所持する必要がなく一つのパケット蓄積ＦＩＦＯ６６５−ｊからパケットを送信するので、複数のＦＩＦＯから送信するＦＩＦＯを選択する必要がなく、高速に帯域制御できる。
【００２８】
本実施例で想定するネットワークの構成は図３に示した通りである。ＩＳＰサイトＡとＩＳＰサイトＢからの通信データが輻輳するエッジノードＣ１の出力側に帯域監視部を持ち、ユーザＡ１〜Ａ３の各ユーザ毎の帯域を監視して、各ユーザ毎契約帯域ＭＡ１〜ＭＡ３を最低帯域として保証する。また、ユーザＡ１￣Ａ３から構成されるユーザグループＡの帯域を監視して、ユーザ毎帯域を未使用のユーザがある場合はその他のユーザに未使用のユーザ毎契約帯域を保証帯域として提供できる。例えば、ユーザＡ２、Ａ３が通信していない場合、ユーザＡ１はユーザグループＡの契約帯域ＭＡ＝ＭＡ１＋ＭＡ２＋ＭＡ３までの保証帯域を使用できる。
【００２９】
ユーザグループＡの契約帯域ＭＡは、ユーザグループとして保証される最低帯域、またはユーザグループとして制限される最大帯域のいずれかを選択できる。ＭＡを最低帯域とする場合、ユーザ毎契約帯域を違反しているパケットに対する制裁はなく、ユーザグループ毎契約帯域に違反しているパケットに対する制裁としてサービス識別子７１３またはキューイング優先度８１５の書き換えを行なう。ＭＡを最大帯域とする場合、ユーザ毎契約帯域を違反しているパケットに対する制裁はなし、またはサービス識別子７１３またはキューイング優先度８１５の書き換えとなり、ユーザグループ毎契約帯域に違反しているパケットに対する制裁は廃棄となる。ＩＳＰサイトＢのユーザＢ１￣Ｂ３から構成されるユーザグループＢに対しても、同様の帯域監視を行なうものとする。
【００３０】
次に、帯域監視部６５０−ｊの詳細動作について説明する。帯域監視アルゴリズムとしてリーキーバケットアルゴリズムを、ＩＰの可変長パケットに拡張した帯域監視アルゴリズムを使用する。リーキーバケットアルゴリズムはある深さを持った穴の空いた漏れバケツのモデルで、バケツに水が入っている間は監視帯域で水は漏れ続け、パケット入力時にはこのパケットのバイト長分の水が注ぎ込まれる。パケットの到着揺らぎを許容するためにバケツに深さを持ち、バケツが溢れないうちは入力パケットは遵守と、溢れると違反と判定される。
【００３１】
図１０に帯域監視部６５０−ｊのブロック図を示す。帯域監視部６５０−ｊは、フロー検出部と、フロー毎帯域監視テーブル制御部と、フロー毎バケツ蓄積量判定部と、フロー毎帯域監視結果判定部と、フローグループ検出部と、フローグループ毎帯域監視テーブル制御部と、フローグループ毎バケツ蓄積量判定部と、フローグループ毎帯域監視結果判定部と、監視結果総合判定部とから構成される。フロー毎帯域監視テーブルのフォーマットを図１１に、フローグループ毎帯域監視テーブルのフォーマットを図１２に示す。１１−１〜１１−６は各々、ユーザＡ１からユーザＢ３に対応するフロー毎帯域監視エントリ、１２−１はユーザグループＡ、１２−２はユーザグループＢのフローグループ毎帯域監視エントリである。ＴＨＲはバケツの深さ、ＰＯＬＲは監視帯域、ＴＳは前回パケット到着時刻、ＣＮＴはバケツに蓄積されている水量を示すバケツ蓄積量、ＴＯＳＣは遵守時のサービス識別子、ＴＯＳＮは違反時のサービス識別子、ＱＣは遵守時のキューイング優先度、ＱＮは違反時のキューイング優先度、ＤＲＯＰは違反時の「廃棄」または「蓄積」の指示を示す。フロー検出部はフロー毎帯域監視をするためにパケットヘッダ内の情報のうちＳＩＰ７１１によりフロー識別子を判定する。フロー毎帯域監視テーブル制御部は、前記フロー識別子に対応するフロー毎帯域監視エントリを参照し、帯域監視に必要なＴＨＲ、ＰＯＬＲ、ＴＳ、ＣＮＴ、ＴＯＳＣ、ＴＯＳＮ、ＱＣ、ＱＮ、ＤＲＯＰのパラメタを読み出して、各々ＴＨＲ蓄積手段、ＰＯＬＲ蓄積手段、ＴＳ蓄積手段、ＣＮＴ蓄積手段、ＴＯＳＣ蓄積手段、ＴＯＳＮ蓄積手段、ＱＣ蓄積手段、ＱＮ蓄積手段、ＤＲＯＰ蓄積手段に蓄積する。以下では、フローがユーザＡ１に属し、フローグループがユーザグループＡに属する場合を説明する。
【００３２】
フロー毎バケツ蓄積量判定部では、パケット入力直前のバケツの水量を判定する。まず、バケツ蓄積量判定回路は現時刻をカウントするタイマーの値とＴＳ蓄積手段のＴＳ−Ａ１との差分を計算し、バケツに水が前回蓄積されてから経過した経過時間を計算する。次に経過時間にＰＯＬＲ蓄積手段内のＰＯＬＲ−Ａ１を乗じて、バケツに水が前回蓄積されてから漏れた水の量を計算する。更に、ＣＮＴ蓄積手段内のＣＮＴ−Ａ１からバケツ内水量減少量を減算して、パケットが入力する直前の水量であるバケツ蓄積量を判定する。前記バケツ蓄積量の正負を判定し、判定結果が負の場合にはバケツ蓄積量を０に修正する。
【００３３】
フロー毎監視結果判定部の監視結果判定回路は、入力パケットのパケット長に相当する水がバケツに入るか否かを判定する。まず、前記のバケツ蓄積量にパケット長を加算して、これをＴＨＲ蓄積手段内のＴＨＲ−Ａ１と大小比較する。バケツ蓄積量＋パケット長がＴＨＲ−Ａ１よりも大なるときは、パケット長に相当する水を入力した場合にバケツが溢れてしまうので、入力パケットを違反パケットと判定して、この判定結果を監視結果総合判定部に送信する。バケツ蓄積量＋パケット長がＴＨＲ−Ａ１以下のときは入力パケットを遵守パケットと判定し、この判定結果を監視結果総合判定部に送信する。
【００３４】
フローグループ毎バケツ蓄積量判定部でも、フローグループ毎帯域監視テーブルから同様にして読み出したパラメタに対し同様の処理を繰り返し、判定結果を監視結果総合判定部に送信する。
【００３５】
監視結果総合判定部では、フロー毎の判定結果とフローグループ毎の判定結果に基づいて、このパケットに対する蓄積廃棄指示８１４、キューイング優先度８１５、サービス識別子７１３を判定して、これらを廃棄制御部６６０−ｊに送信する。ここでは、フローグループ毎契約帯域が最低帯域であって、フロー毎帯域監視違反時の制裁無し（遵守時と同じ判定）、フローグループ毎帯域監視違反時の制裁はサービス識別子とキューイング優先度の書き換えである場合を説明する。フロー毎の判定結果が「遵守」のパケットに対しては、蓄積指示となりＴＯＳＣ−Ａ１、ＱＣ−Ａ１を廃棄制御部６６０−ｊに送信する。フロー毎の判定結果が「違反」かつフローグループ毎の判定結果が「遵守」のパケットに対しても、フロー毎帯域監視違反時の制裁無しであるから、蓄積指示となりＴＯＳＣ−Ａ１、ＱＣ−Ａ１を廃棄制御部６６０−ｊに送信する。フロー毎の判定結果が「違反」かつフローグループ毎の判定結果が「違反」のパケットに対しては、蓄積指示となりＴＯＳＣ−Ａ、ＱＣ−Ａを廃棄制御部６６０−ｊに送信する。これにより、フロー毎最低帯域ＭＡｉ（ｉ＝１〜３）を必ず保証すると共に、フロー毎最低帯域を超過したユーザに対してもユーザグループＡの最低帯域ＭＡに余剰帯域のある場合はこれを有効活用できる。また、ユーザグループＡの最低帯域ＭＡを超過したパケットは、サービス識別子またはキューイング優先度を書き換えることにより自パケット転送装置内またはネットワーク内の他のパケット転送装置内において非優先パケットとして扱われる。
【００３６】
更に、フロー毎帯域監視の判定結果が「遵守」であった場合、バケツ蓄積量＋パケット長を新たなバケツ蓄積量ＣＮＴ−Ａ１として、現時刻のタイマーの値を新たなＴＳ−Ａ１としてフロー毎帯域監視テーブル制御部に送信し、次の入力パケットに対してフロー毎帯域監視テーブルを読み出す前にユーザＡ１のフロー毎帯域監視エントリに書き込む。同様に、フローグループ毎帯域監視の判定結果が「遵守」であった場合にも新たなＣＮＴ−Ａ、ＴＳ−Ａをフローグループ毎帯域監視テーブルに書き込む。更に、本発明に固有の処理として、フローグループ毎帯域監視の判定結果が「違反」であった場合にも、フロー毎帯域監視結果が「遵守」であれば、新たなＣＮＴ−Ａ、ＴＳ−Ａを超過帯域分を示す超過帯域情報としてフローグループ毎帯域監視テーブルに書き込む。
【００３７】
図１３に帯域監視アルゴリズムのフローチャートを示す。１３の処理、即ちフロー毎帯域監視判定結果が「遵守」であった場合に、新たなＣＮＴ−Ａ、ＴＳ−Ａを超過帯域分を示す超過帯域情報としてフローグループ毎帯域監視テーブルに書き込む処理が、本発明に固有の処理である。
【００３８】
【発明の効果】
本発明によれば、ユーザ毎に帯域監視すると共に、複数ユーザから構成されるユーザグループを多数収容してユーザグループ毎にも帯域監視することのできる高速な帯域監視装置を提供できる。更に、この帯域監視装置を用いて多数のユーザグループを収容することにより、ユーザグループ当たりの収容コストを低減できる。
【００３９】
また、本発明の帯域監視方法によれば、ユーザ毎に契約された最低帯域を必ず保証すると共に、更にユーザグループ毎の使用帯域に余剰帯域のある場合はこれを有効活用できる。
【図面の簡単な説明】
【図１】従来技術１のシェーピング装置の構成を示すブロック図。
【図２】従来技術２の帯域監視方法のフローチャート。
【図３】本発明で想定するネットワークの構成例を示す図。
【図４】（Ａ）従来技術２とリーキーバケットアルゴリズムとを組み合わせた場合の課題を示す図。（Ｂ）本発明により、従来技術２の課題を解決することをリーキーバケットアルゴリズムのバケツ水量により示す図。
【図５】本発明により、従来技術２の課題を解決することをリーキーバケットアルゴリズムのバケツ水量により示す図。
【図６】本発明を適用するパケット転送装置のブロック図。
【図７】図３のネットワーク上のパケットのヘッダおよびデータ構成を示す図。
【図８】図６のパケット転送装置内のパケットの構成を示す図。
【図９】図６のパケット転送装置内の廃棄制御部のブロック図。
【図１０】本発明の帯域監視部のブロック図。
【図１１】フロー毎帯域監視テーブルのフォーマット。
【図１２】フローグループ毎帯域監視テーブルのフォーマット。
【図１３】本発明の帯域監視方法のフローチャート。
【符号の説明】
６００…パケット転送装置、６１０…入力回線、６４０…パケット中継処理手段、６８０…出力回線、１１…フロー毎帯域監視エントリ、１２…フローグループ毎帯域監視エントリ、１３…フロー毎帯域監視判定結果が「遵守」であった場合に、新たなＣＮＴ−Ａ、ＴＳ−Ａを超過帯域分を示す超過帯域情報としてフローグループ毎帯域監視テーブルに書き込む処理。
【図１】
2005039390.tif 000003
【図２】
2005039390.tif 000004
【図３】
2005039390.tif 000005
【図４】
2005039390.tif 000006
【図５】
2005039390.tif 000007
【図６】
2005039390.tif 000008
【図７】
2005039390.tif 000009
【図８】
2005039390.tif 000010
【図９】
2005039390.tif 000011
【図１０】
2005039390.tif 000012
【図１１】
2005039390.tif 000013
【図１２】
2005039390.tif 000014
【図１３】
2005039390.tif 000015