(57)【特許請求の範囲】
【請求項１】
ネットワークに流入したパケットに対し、該パケットの送信元の契約帯域に違反していないかどうか監視し、該パケットが契約帯域内であれば当該パケットを優先的に送信し、違反した場合は当該パケットを非優先パケットとして送信する帯域監視方法であって、
前記帯域監視を前記パケットの属するフローに対して行ない、
前記帯域監視を複数のフローから構成されるフローグループに対して行ない、
第一のフローに属する流入パケットが前記フロー毎に行なった帯域監視に違反していない場合、前記フローグループ毎に行なった帯域監視に違反する場合であっても、前記パケットを優先パケットとして送信し、
さらに、前記フローグループの契約帯域を超過した前記第一のフローに属するパケット分の超過帯域を記憶し、
第二のフローに属するパケットが該パケットの属するフロー毎契約帯域に違反している場合には、前記記憶された超過帯域を前記フローグループ毎契約帯域から差し引いて前記フローグループ毎の帯域監視を行なうことを特徴とする帯域監視方法。
【請求項２】
請求項１に記載の帯域監視方法において、前記フロー毎契約帯域として前記フロー毎に保証された最低帯域を使用し、前記フローグループ毎契約帯域として前記フローグループに属するフローに保証された最低帯域の総和以上の値を使用することを特徴とする帯域監視方法。
【請求項３】
請求項１に記載の帯域監視方法において、前記フロー毎契約帯域として前記フロー毎に保証された最低帯域を使用し、前記フローグループ毎契約帯域として前記フローグループとして制限された最大帯域を使用することを特徴とする帯域監視方法。
【請求項４】
請求項３に記載の帯域監視方法において、前記流入パケットが、前記フロー毎帯域監視に違反し、かつ前記フローグループ帯域監視に違反する場合には、当該流入パケットを廃棄することを特徴とする帯域監視方法。
【請求項５】
請求項１に記載の帯域監視方法において、帯域監視のアルゴリズムとしてリーキーバケットアルゴリズムを用いることを特徴とする帯域監視方法。
【請求項６】
請求項５に記載の帯域監視方法において、前記フロー毎に行なう帯域監視においてフロー毎契約帯域に違反していないと判定されたパケットに対しては、フローグループ毎帯域監視におけるリーキーバケットアルゴリズムのバケツの深さに関わらず、フローグループ毎契約帯域に違反していないと判定してこれをバケツに蓄積して、ここでバケツに蓄積された水量が前記超過帯域情報であることを特徴とする帯域監視方法。
【請求項７】
複数の入力回線を収容する複数のパケット受信回路と、複数の出力回線を収容する複数のパケット送信回路と、前記パケット受信回路で受信したパケットを前記複数の出力回線のいずれへ転送するか決定するルーティング処理部と、該ルーティング処理部と前記複数のパケット送信回路の各々とのパケット転送経路上に設けられる複数の帯域監視部と、廃棄制御部と、前記ルーティング処理部を通過したパケットを前記複数の帯域監視部のいずれかへスイッチングするパケット中継処理手段とを有し、
前記帯域監視部は、
受信したパケットの属するフローを検出するフロー検出部と、
該検出したフローの属するフローグループを検出するフローグループ検出部と、
前記検出したフロー毎に契約帯域を監視するためのフロー毎帯域監視部と、
前記検出したフローグループ毎に契約帯域を監視するためのフローグループ毎帯域監視部と、
前記フロー毎帯域監視部とフローグループ帯域監視部との監視結果を基に、前記受信パケットを優先パケットか非優先パケットに弁別する監視結果総合判定部とを備え、
該監視結果総合判定部は、第一のフローに属する受信パケットが前記フロー毎に行なった帯域監視に違反していない場合、前記フローグループ毎に行なった帯域監視に違反する場合であっても、前記パケットを優先パケットとして前記パケット送信回路へ転送し、
さらに、前記フローグループの契約帯域を超過した前記第一のフローに属するパケット分の超過帯域を記憶し、
第二のフローに属するパケットが該パケットの属するフロー毎契約帯域に違反している場合には、前記記憶された超過帯域を前記フローグループ毎契約帯域から差し引いて前記フローグループ毎の帯域監視を行なうことを特徴とするパケット転送装置。
【請求項８】
請求項７に記載の帯域監視装置において、
前記フロー毎帯域監視手段は、フロー帯域監視テーブルと、入力パケットの属するフローに対応するフロー毎帯域監視エントリをフロー毎帯域監視テーブルから読み出すフロー毎帯域監視テーブル制御手段と、フロー毎帯域監視のための制御情報と現時刻を表すタイマーの値とに基づいて入力パケットのフロー毎契約帯域遵守・違反の判定を行なうフロー毎監視結果判定手段とを備え、
前記フローグループ毎帯域監視手段は、フローグループ毎帯域監視テーブルと、入力パケットの属するフローグループに対応するフローグループ毎帯域監視エントリを前記フローグループ毎帯域監視テーブルから読み出すフローグループ毎帯域監視テーブル制御手段と、フローグループ毎帯域監視のための制御情報と現時刻を表すタイマーとの値に基づいて入力パケットのフローグループ毎契約帯域遵守・違反の判定を行なうフローグループ毎監視結果判定手段とを備え、
前記フロー帯域監視テーブルは、
フロー毎契約帯域、フロー毎のバケツの深さ及びフロー毎のバケツの水量と前回のフロー毎帯域監視時刻を含むフロー毎帯域監視制御情報と、フロー毎契約帯域に違反しているパケットに与える制裁として廃棄またはネットワーク優先度書き換えまたは制裁無しを指示するフロー毎制裁情報とを含むフロー毎帯域監視エントリを備え、
前記フローグループ毎帯域監視テーブルは、
フローグループ毎契約帯域、フローグループ毎のバケツの深さ、フローグループ毎のバケツの水量と前回のフローグループ毎帯域監視時刻とを含むフローグループ毎帯域監視制御情報と、フローグループ毎契約帯域に違反しているパケットに与える制裁として廃棄またはネットワーク優先度書き換えまたは制裁無しを指示するフローグループ毎制裁情報とから構成されるフローグループ毎帯域監視エントリとを備えることを特徴とするパケット転送装置。
【請求項９】
請求項８に記載の帯域監視装置において、
前記フロー毎契約帯域に違反していないパケットに対しては制裁を与えず、フロー毎契約帯域に違反していてフローグループ毎契約帯域に違反していないパケットに対してはフロー毎制裁情報で指定された制裁を与え、フロー毎契約帯域とフローグループ毎契約帯域共に違反しているパケットに対してはフロー毎制裁情報で指定された制裁またはフローグループ毎制裁情報で指定された制裁を与えることを特徴とするパケット転送装置。
【請求項１０】
請求項７から９のいずれか１項に記載のパケット転送装置において、パケットを蓄積するパケット蓄積FIFOと、前記パケット蓄積FIFOに蓄積しているパケット数をカウントするカウンタと、前記パケット蓄積FIFOへのパケットの蓄積・廃棄を判定する廃棄制御部とを備え、
複数のフローグループのパケットが同一のパケット蓄積FIFOに蓄積されることを特徴とする帯域監視装置。
【請求項１１】
請求項１０に記載のパケット転送装置において、
前記フロー毎制裁情報または前記フローグループ毎制裁情報は、各々パケット蓄積FIFOに対するキューイング優先度書き換えを含み、
前記廃棄制御部は、前記パケット蓄積FIFOへのパケットの蓄積・廃棄を判定する際に参照する閾値をキューイング優先度毎に保持することを特徴とするパケット転送装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケットの制御方法及び転送装置、特にネットワークに流入するパケットの帯域を監視する帯域監視方法および帯域監視装置に関する。
【０００２】
【従来の技術】
インターネットをはじめとするIP(Internet Protocol)ネットワークで用いられるパケット型通信方式では、多数のユーザが回線を共用できるので従来の専用回線よりも通信コストの低減が可能となる。この低コスト性を活かして、従来は専用回線を流れていた音声データ、企業のミッションクリティカルデータ等をIPネットワークに適用する要求がでてきた。このため、Best Effort型サービスが主流であった従来のIPネットワークにおいて、専用回線のもつ低遅延、低廃棄率等の通信品質を実現する必要性が増している。
【０００３】
通信品質を実現するサービスの一つに、ATM(Asynchronous Transfer Mode)網のATC(ATM Transfer Capability)として規定されるGFR(Guaranteed Frame Rate)がある。GFRでは、契約された最低帯域を保証すると共に、余剰帯域があれば最低帯域を超過する通信も許すことにより帯域を有効活用できる。
【０００４】
帯域制御の必要性について、図３を用いて説明する。なお、図３はネットワークの構造を示すための一例であって、従来技術であっても本願発明であっても適用が可能であることは言うまでもない。図３において、エッジノードC1の出力回線はISP(Internet Service Provider)サイトA、ISPサイトB両方からのフローにより共有されている。従って、通信回線に輻輳が生じた際には通信品質の劣化点となり易い。よって、エッジノードC1では、送信パケットに対する帯域制御が必要となる。
【０００５】
帯域制御のためには、まず、各ユーザ毎に契約された最低帯域を監視してこれを保証することが必要である。ISPサイトAの収容ユーザA1~A3の通信品質を保証するためである。同時に、輻輳を防止してキャリアバックボーンネットワーク内の帯域資源を守るため、ユーザA1〜A3を束ねたグループであるユーザグループAとしての最大帯域を監視して制限をかける必要もある。なお、各ユーザA1〜A3は、各々保証された最低帯域を使い切った場合にも、ユーザグループAとして最大帯域を超過しない限り余剰帯域を用いてパケットの送受信が可能である。また、ユーザグループ当たりの収容コスト低減のため、エッジノードC1には複数のユーザグループが収容され、ユーザグループ毎に帯域監視が実行される。
【０００６】
特開2001-326688号公報（以下、従来技術1）には、ユーザ毎に最低帯域を保証するシェーピング装置が開示されている。従来技術1では、ATMにおける固定長パケットであるセルの帯域監視アルゴリズムであるcontinuous Leaky Bucket Algorithm（以下、リーキーバケットアルゴリズムと称す。）を、IPの可変長パケットに拡張した帯域監視アルゴリズムを用いている。リーキーバケットアルゴリズムはある深さを持った穴の空いた漏れバケツのモデルで、バケツに水が入っている間は監視帯域で水は漏れ続け、パケット入力時にはこのパケットのバイト長分の水が注ぎ込まれる。パケットの到着揺らぎを許容するためにバケツはある程度の深さを持ち、バケツが溢れるまでは入力パケットは遵守パケットと、溢れると違反パケットと判定される。
【０００７】
従来技術1より引用したシェーピング装置の概念図を図１に示す。図１に示したシェーピング装置は、受信パケットの内部転送処理を行なうパケット中継処理手段と、処理の終わったパケットを送信するパケット送信回路の間に設けられたものとする。
シェーパ部100にパケットが到着すると、廃棄制御部110は到着パケットの「蓄積」「廃棄」を判定する。パケット蓄積FIFO120は「蓄積」と判定したパケットを蓄積し、各ユーザ毎に契約された最低帯域の総和以上の帯域で送信する。帯域監視部130は、ユーザ毎に帯域をチェックして、最低帯域以内のパケットを優先パケットと、それ以外を非優先パケットと判定する。優先パケットに対するFIFO閾値を非優先パケットに対するFIFO閾値よりも深く設定することにより、優先パケットを優先的に「転送」と判定して優先パケットを保護し、各ユーザ毎に最低帯域を保証する。ここで、FIFOとはパケットを蓄積するメモリの一種であって、データを格納したり、格納したデータを取り出して使用する場合に，格納した順番どおりに、先に格納したデータが取り出せる構成のメモリ，またはそのような記憶方法をいう。なお、FIFOとは、First In First Outの略である。
【０００８】
従来技術1のシェーピング装置を図３のエッジノードC1に適用すれば、上述の帯域制御が可能である。帯域監視部130により、受信パケットユーザ毎にパケットの帯域監視を実行し、優先パケット/非優先パケットの弁別が実行される。最低帯域内に収まっているパケットは、優先パケットとして処理される。すなわち、パケット蓄積FIFO120に対するキューイング優先度が高優先に設定される。一方、ユーザ毎の最低帯域を超過するパケットは非優先パケットとして処理される。すなわち、パケット蓄積FIFO120に対するキューイング優先度を低優先に設定される。これにより、ユーザ毎の最低帯域保証を実現できる。
また、パケットユーザグループの最大帯域制限は、パケット蓄積FIFO120からのパケット送信帯域を任意の値に設定することで実現可能である。なお、パケット蓄積FIFO120に蓄積するパケットは、特定のユーザグループ、例えばユーザグループAのパケットに限定されている。すなわち、当該シェーパ100は、ユーザグループの数に応じて設けられている。
【０００９】
Internet SocietyのRFC2698には、最低帯域と最大帯域の二つの帯域監視結果から、パケットの弁別を行なう際の弁別法として2Rate 3Color Marker（以下、従来技術2）が開示されている。図２には、従来技術2の処理の流れをフローチャートで示す。従来技術2では、まずユーザ毎の使用帯域が最大帯域を超過していないか判定し、超過している場合は廃棄パケットと判定してパケットを廃棄する。超過していない場合は、次にユーザ毎の使用帯域が最低帯域を超過していないか判定する。最低帯域を超過している場合はこのパケットを非優先パケットと判定し、制裁として例えばキューイング優先度を低優先として輻輳時に優先的に廃棄されるパケットとする。超過していない場合はこのパケットを優先パケットと判定して、輻輳時にも廃棄され難くなるようキューイング優先度を高優先とする。
【００１０】
【発明が解決しようとする課題】
従来技術1に開示されたシェーピング装置に複数のユーザグループを収容しようとする場合、ユーザグループ毎に最大帯域を制限するためには、ユーザグループ毎にパケット蓄積FIFOを設けて、パケット蓄積FIFOからの送信帯域を最大帯域以下に制限する必要がある。従って、収容ユーザグループ数が増加すると、所持すべきパケット蓄積FIFOの本数も増加する。パケットを送信すべきパケット蓄積FIFOを判定する時間は、パケット蓄積FIFOの数と共に増加するので、多数のユーザグループを収容する場合、パケット蓄積FIFOの判定に要する判定処理時間は、収容するユーザグループ数に応じて増加する。よって、多数のユーザグループを収容する場合、高速に帯域制御できないという課題がある。更に、多数のユーザグループを収容する場合、多数のパケット蓄積FIFOが必要となるので、パケット蓄積FIFOを所持するためのコストが収容ユーザグループ数に比例して増加するという課題もある。
FIFOの替りに汎用の大型メモリを用いて、種類の異なるユーザグループに属するパケットをバッファリングすれば、原理的にはユーザグループに応じてパケット蓄積FIFOを設ける必要はなくなるが、どのユーザグループに属するパケットを引き出すかという処理が必要になる。従って、処理が複雑化する上、メモリの読み出し速度も早くないので、結局高速な帯域制御はできない。
【００１１】
また、従来技術2に記載された技術は、帯域監視結果を利用して、受信パケットを優先パケット/非優先パケット/廃棄パケットに弁別するための技術なので、従来技術1に記載のリーキーバケットアルゴリズムと組み合わせても課題の解決にはならない。
【００１２】
本発明の第一の目的は、従来技術1の課題を解決して、ユーザ毎に帯域監視すると共に、複数ユーザから構成されるユーザグループを多数収容してユーザグループ毎にも帯域監視することのできる高速な帯域監視装置を提供することにある。更に、この帯域監視装置を用いて多数のユーザグループを収容することにより、ユーザグループ当たりの収容コスト
を低減する効果を得ることにある。
【００１３】
【課題を解決するための手段】
本発明の帯域監視装置は、パケットの属するユーザ毎の契約帯域を帯域監視するユーザ毎帯域監視手段と、複数のユーザから構成されるユーザグループ毎の契約帯域を帯域監視するユーザグループ毎帯域監視手段とを備え、複数のユーザのみならず複数のユーザグループのパケットが同一のパケット蓄積FIFOに蓄積されることを特徴とする。本発明の帯域監視装置によれば、収容するユーザグループ数が増加しても常に一つのパケット蓄積FIFOからパケットを出力するので、複数のパケット蓄積FIFOからパケットを出力するパケット蓄積FIFOを選択する必要がないので、収容するユーザグループ数が増加しても高速に帯域監視することができる。
【００１４】
なお、契約帯域は必ずしもユーザ毎またはユーザグループ毎である必要はなく、一般的には入力パケットのアドレス情報、用途を識別する情報またはネットワーク内の優先度を識別する情報であるネットワーク優先度のうち、少なくとも一つの情報から識別されるフロー毎、または複数のフローから構成されるフローグループ毎とすることができる。この場合、本発明の帯域監視装置はパケットの属するフローを検出するフロー検出手段と、検出したフローの属するフローグループを検出するフローグループ検出手段とを備え、フロー検出手段で検出したフロー毎に契約帯域を監視するためのフロー毎帯域監視手段と、フローグループ検出手段で検出したフローグループ毎に契約帯域を監視するためのフローグループ毎帯域監視手段を備え、複数のフローグループのパケットが同一のパケット蓄積FIFOに蓄積されることを特徴とする。
【００１５】
【発明の実施の形態】
従来技術2に記載されたパケットの弁別基準を従来技術1のシェーパに適用して上記の帯域制御を行うと新たに別の課題が発生する。帯域監視部130にてユーザ毎の最低帯域を監視して最低帯域以内のパケットを優先パケットとしてパケット蓄積FIFO120に対するキューイング優先度を高優先とし、ユーザ毎の最低帯域を超過するパケットは非優先パケットとしてキューイング優先度を低優先とする。更に、帯域監視部130にてユーザグループ毎の最大帯域を監視して最大帯域を超過するパケットを廃棄する。
このときの課題を、図４（A）を用いて説明する。まず、図４（A）の左図のようにユーザA1〜A3のうちユーザA1だけが通信している状態を考え、ユーザA1はユーザ毎に契約された最低帯域を使い切った上で、更にユーザグループAに属する他のユーザが未使用の余剰帯域を利用してユーザグループAの最大帯域まで占有して通信しているものとする。このときユーザA2のパケットが入力し始めると、図４（A）の右図のようにユーザグループAのバケツ閾値を超過してしまう。従来技術2では、まず最大帯域監視の判定から行うので、ユーザA2のパケットはユーザ毎の最低帯域を使いきっていないにも関わらず、ユーザグループ毎の最大帯域を超過と判定されるので廃棄されてしまう。このように、従来技術2で複数ユーザをまとめる最大帯域監視を論理的に先判定すると、ユーザ毎の最低帯域を必ずしも保証できないという課題がある。
【００１６】
本発明のパケット転送装置は、フローグループ毎契約帯域の全てが使用されている場合にネットワークに流入したパケットに対して、該パケットが該パケットの属するフロー毎契約帯域に違反していない場合には、フローグループ毎契約帯域に違反していないと判定することによりフロー毎契約帯域を保証すると共に、フローグループ毎契約帯域を超過した該パケット分の超過帯域を超過帯域情報として記憶しておく一方、該パケットが該パケットの属するフロー毎契約帯域に違反している場合には、前記の超過帯域情報として記憶している超過帯域をフローグループ毎契約帯域から差し引いてフローグループ毎帯域監視を行なうことにより、フロー毎契約帯域に違反しているパケットと違反していないパケットを合わせた使用帯域としてフローグループ毎契約帯域を超過する帯域が割り当てられないことを特徴とする。
これにより、従来技術2の課題が解決される理由は、次の通りである。例として、帯域監視のアルゴリズムがリーキーバケットアルゴリズムである場合を説明する。まず、図４-2の左図のようにユーザA1はユーザ毎の最低帯域を使い切った上で、更に余剰帯域を利用してユーザグループAの最大帯域まで占有して通信しているものとする。このときユーザA2のパケットが入力し始めると、図４-2の右図のようにユーザグループAのバケツ閾値を超過する。従来技術2では、まず最大帯域の判定から論理的に先に行うので、ユーザA2のパケットは最大帯域超過と判定されて廃棄となってしまい、ユーザA2の最低帯域は必ずしも保証できない。
しかし、本発明によれば、図５のユーザグループ毎の契約帯域が最大帯域の場合は上図、ユーザグループ毎の契約帯域が最低帯域の場合は下図のように、まずユーザ毎の契約帯域である最低帯域の判定から論理的に先に行なう。すると、ユーザA2のパケットが入力し始めたとき、このパケットはユーザA2の契約帯域に違反していないのでユーザグループAの契約帯域にも違反していないと判定され、ユーザA2のバケツにはこのパケットに相当する水量が蓄積されるのみならず、これと同じ水量がユーザグループAのバケツには閾値を溢れて蓄積される。従って、ユーザA2の契約帯域は必ず保証される。
【００１７】
一方、この状態でユーザA1のパケットが入力すると、このパケットはユーザA1の契約帯域に違反しており、更にユーザグループAの契約帯域にも違反しているものとみなされるので、ユーザグループAの最大帯域制限を受けて廃棄される。このように、ユーザ毎契約帯域に違反していないユーザのパケットとユーザ毎契約帯域に違反しているパケットとが競合する場合、ユーザ毎契約帯域に違反していないパケットはユーザグループ毎契約帯域を違反していないと判定されてユーザグループ毎のバケツに蓄積される一方、ユーザ毎契約帯域に違反しているパケットはユーザグループ毎契約帯域に違反していると判定されるので、ユーザグループ毎のバケツに蓄積されない。従って、ユーザ毎契約帯域に違反していないパケットはユーザグループ毎契約帯域にも違反せず必ず最低帯域を保証できるのに対し、ユーザ毎契約帯域に違反しているパケットはユーザグループ契約帯域に違反した場合優先的に廃棄されることで、ユーザ毎契約帯域を使い切ったユーザと使い切っていないユーザとの間で使用帯域が調整されることとなる。
尚、本発明ではユーザグループ毎契約帯域をユーザ毎契約帯域の総和以上とする必要がある。その理由は、ユーザグループ毎契約帯域がユーザ毎契約帯域の総和未満である場合、全てのユーザがユーザ毎契約帯域を全て使用してパケットを送信し続けると、ユーザグループの帯域を監視するバケツが溢れ続けてしまい、ユーザグループ毎契約帯域を超過する状態が恒常的に続いてしまうからである。ユーザグループ毎契約帯域がユーザ毎契約帯域の総和以上である場合は、ユーザ毎契約帯域に違反していないパケットが過剰にユーザグループ毎のバケツに蓄積された場合にも、ユーザ毎契約帯域以上の帯域でユーザグループ毎のバケツからは水が漏れ続けている。更に、ユーザ毎契約帯域に違反しているパケットのユーザグループ毎帯域監視において、ユーザグループ毎契約帯域から前記の過剰にユーザグループ毎のバケツに蓄積された分の超過帯域は差し引かれる。従って、ユーザ毎契約帯域に違反しているパケットに対しては、ユーザ毎契約帯域に違反していないパケットが超過した分の帯域が使用帯域として割り当てられないので、フロー毎契約帯域に違反しているパケットと違反していないパケットを合わせた使用帯域としてユーザグループ毎契約帯域を超過する帯域は割り当てられない。
【００１８】
ユーザ毎契約帯域とユーザグループ毎契約帯域の例として、例えばユーザ毎に保証された最低帯域をユーザ毎契約帯域とし、ユーザグループ毎契約帯域はユーザグループに属するユーザ毎に保証された最低帯域の総和とすることができる。この場合、ユーザ毎最低帯域を必ず保証すると共に、ユーザグループ毎契約帯域に余剰帯域のある場合はこれを有効活用できるように帯域監視することができる。
【００１９】
また、ユーザ毎に保証された最低帯域をユーザ毎契約帯域とし、ユーザグループ毎契約帯域はユーザグループとして制限したい最大帯域とすることができる。この場合、ユーザ毎最低帯域を必ず保証すると共に、ユーザグループとしての最大帯域を制限しながら余剰帯域のある場合にはこれを有効活用できるように帯域監視することができる。
この場合も、契約帯域は必ずしもユーザ毎またはユーザグループ毎である必要はなく、一般的には入力パケットのアドレス情報、用途を識別する情報またはネットワーク内の優先度を識別する情報であるネットワーク優先度のうち少なくとも一つの情報から識別されるフロー毎または複数のフローから構成されるフローグループ毎とすることができる。
【００２０】
まず、本発明を適用したパケット転送装置の構成概要を、図６を用いて説明する。パケット転送装置600は、パケットが入力するN個の入力回線610-i(i=1〜N)と、パケットの受信処理を行うパケット受信回路620-iと、ルーティング処理部630と、パケットをスイッチングするパケット中継処理手段640と、出力回線毎の帯域監視部650-j(j=1〜M)と、廃棄制御部660-jと、送信処理を行うパケット送信回路670-jと、パケットが出力されるN個の出力回線680-jから構成される。
【００２１】
図７は、本発明が想定する図３に示したIPネットワークにおけるパケットのフォーマットの一例を示す。パケットはヘッダ部710とデータ部720から構成される。ヘッダ部710は送信元IPアドレス(Source IP address：以下「SIP」と称する。)711と、宛先IPアドレス(Destination IP address：以下「DIP」と称する。)712と、サービス識別子(Type of Service：以下「TOS」と称する。)713から構成される。また、データ部720はユーザデータ721から構成される。ヘッダ部710には、前記情報以外にも生存時間(TTL：Time to Live)等の情報も格納されているが、前記情報と同様に後述の処理を実行できる。
【００２２】
図８は、本発明を適用したパケット転送装置600内部におけるパケットのフォーマットの一例を示す。パケット転送装置600内部のパケットのフォーマットには、IPネットワークのパケットのフォーマットに内部ヘッダ810が加わる。内部ヘッダ810はパケットが入力した回線の識別子である入力回線番号811と、パケットが出力される回線の識別子である出力回線番号812と、パケットのバイト長を表すパケット長813と、帯域監視の結果指示された廃棄制御部660-jにおけるパケット蓄積FIFO665-ｊに対する蓄積・廃棄を指示する蓄積廃棄指示814と、パケット蓄積FIFO665-ｊに対するキューイング優先度815とから構成される。
【００２３】
次に、本発明を適用したパケット転送装置の動作概要を、図６を用いて説明する。パケット転送装置600の入力回線610-iからパケットが入力すると、パケット受信回路620-iは内部ヘッダ810を付加し、パケットのバイト長を計算した上でパケット長813(単位はByte)に書き込む。更に、パケットが入力した入力回線610-iを入力回線番号811に書き込み、ルーティング処理部630へパケットを送信する。尚、この時点では出力回線番号812は無意味な値となっている。ルーティング処理部630は、パケットを受信するとDIP712に基づいてパケットを出力する回線680-jを判定し、出力回線680-jの回線番号jを出力回線番号812に書き込みパケット中継処理手段640に送信する。パケット中継処理手段640は出力回線番号812に従ってパケットをスイッチングし、出力回線毎の帯域監視部650-jに送信する。
【００２４】
帯域監視部650-jは、SIP711に基づいてパケットの属するユーザと、パケットの属するユーザグループとを検出し、各ユーザ毎の帯域監視と各ユーザグループ毎の帯域監視を行ない、ユーザ毎に契約された最低帯域を必ず保証すると共に、更にユーザグループ毎の使用帯域に余剰帯域のある場合はこれを有効活用できるよう帯域監視を行なう。この帯域監視部650-ｊの詳細動作については後述する。帯域監視されたパケットに対して、帯域監視の結果指示された廃棄制御部660-jにおけるパケット蓄積FIFO665-jに対する蓄積・廃棄の指示を蓄積廃棄指示814に、パケット蓄積FIFO665-jに対するキューイング優先度をキューイング優先度815に書き込み、廃棄制御部660-jに送信する。
【００２５】
廃棄制御部660-jに送信されたパケットは、一旦一時蓄積バッファ662-jに蓄積される。帯域監視部650-jから送信されたパケットの蓄積廃棄指示814に基づき、「廃棄」と指示された場合には、一時蓄積バッファ662-jからパケット蓄積FIFO665-jにパケットを送信しない。そして、「廃棄」と判定されたパケットの次に廃棄制御部660-jに到着したパケットの情報を上書きする。「蓄積」と指示された場合には、キューイング優先度毎閾値蓄積手段661-jからキューイング優先度815に対するパケット蓄積FIFO665-jの閾値を参照して、この閾値とFIFOカウンタ664-jの値を比較する。この閾値がFIFOカウンタ664-jより大きい場合には、「蓄積」と判定してパケットをパケット蓄積FIFO665-jに送信すると共に、FIFOカウンタ664-jの値に1加算する。閾値がFIFOカウンタ664-j以下の場合には、「廃棄」と判定してパケットをパケット蓄積FIFO665-jに送信せず、FIFOカウンタ664-jの値に加算しない。そして、「廃棄」と判定されたパケットの次に廃棄制御部660-jに到着したパケットの情報を上書きする。
【００２６】
パケット出力制御部666-jはパケット蓄積FIFO665-jに蓄積した順番に回線帯域でパケットを送信するようにパケット送信起動信号667-jを送信し、この信号を受信したパケット蓄積FIFO665-jはパケット送信回路670-jへパケットを送信する。また、FIFOカウンタ665-jは前記パケット送信起動信号667-jを受信するとFIFOカウンタ665-jから1減算する。本発明では、パケット出力制御部666-jは回線帯域でパケットを送信するようにパケット送信起動信号667-jを送信するが、ネットワーク運用者によって設定された回線帯域以下の帯域(例えば、回線帯域の半分)で送信しても良い。パケット送信回路670-jへ送信されたパケットは、内部ヘッダ810を外されて出力回線680-ｊへ送信される。
【００２７】
本発明の帯域監視部650-ｊでは、ユーザ毎帯域監視とユーザグループ毎帯域監視を行なってユーザグループ毎の契約帯域を超過するパケットに対する廃棄、またはサービス識別子713またはキューイング優先度815の書き換え指示がなされている。従って、廃棄制御部660-ｊでは廃棄指示、またはキューイング優先度815に従って廃棄制御を行なうことにより、ユーザ毎およびユーザグループ毎の帯域制御が可能となる。ユーザグループ毎にパケット蓄積FIFO665-ｊを所持する必要がなく一つのパケット蓄積FIFO665-ｊからパケットを送信するので、複数のFIFOから送信するFIFOを選択する必要がなく、高速に帯域制御できる。
【００２８】
本実施例で想定するネットワークの構成は図３に示した通りである。ISPサイトAとISPサイトBからの通信データが輻輳するエッジノードC1の出力側に帯域監視部を持ち、ユーザA1〜A3の各ユーザ毎の帯域を監視して、各ユーザ毎契約帯域MA1〜MA3を最低帯域として保証する。また、ユーザA1~A3から構成されるユーザグループAの帯域を監視して、ユーザ毎帯域を未使用のユーザがある場合はその他のユーザに未使用のユーザ毎契約帯域を保証帯域として提供できる。例えば、ユーザA2、A3が通信していない場合、ユーザA1はユーザグループAの契約帯域MA=MA1+MA2+MA3までの保証帯域を使用できる。
【００２９】
ユーザグループAの契約帯域MAは、ユーザグループとして保証される最低帯域、またはユーザグループとして制限される最大帯域のいずれかを選択できる。MAを最低帯域とする場合、ユーザ毎契約帯域を違反しているパケットに対する制裁はなく、ユーザグループ毎契約帯域に違反しているパケットに対する制裁としてサービス識別子713またはキューイング優先度815の書き換えを行なう。MAを最大帯域とする場合、ユーザ毎契約帯域を違反しているパケットに対する制裁はなし、またはサービス識別子713またはキューイング優先度815の書き換えとなり、ユーザグループ毎契約帯域に違反しているパケットに対する制裁は廃棄となる。ISPサイトBのユーザB1~B3から構成されるユーザグループBに対しても、同様の帯域監視を行なうものとする。
【００３０】
次に、帯域監視部650-ｊの詳細動作について説明する。帯域監視アルゴリズムとしてリーキーバケットアルゴリズムを、IPの可変長パケットに拡張した帯域監視アルゴリズムを使用する。リーキーバケットアルゴリズムはある深さを持った穴の空いた漏れバケツのモデルで、バケツに水が入っている間は監視帯域で水は漏れ続け、パケット入力時にはこのパケットのバイト長分の水が注ぎ込まれる。パケットの到着揺らぎを許容するためにバケツに深さを持ち、バケツが溢れないうちは入力パケットは遵守と、溢れると違反と判定される。
【００３１】
図１０に帯域監視部650-ｊのブロック図を示す。帯域監視部650-ｊは、フロー検出部と、フロー毎帯域監視テーブル制御部と、フロー毎バケツ蓄積量判定部と、フロー毎帯域監視結果判定部と、フローグループ検出部と、フローグループ毎帯域監視テーブル制御部と、フローグループ毎バケツ蓄積量判定部と、フローグループ毎帯域監視結果判定部と、監視結果総合判定部とから構成される。フロー毎帯域監視テーブルのフォーマットを図１１に、フローグループ毎帯域監視テーブルのフォーマットを図１２に示す。11-1〜11-6は各々、ユーザA1からユーザB3に対応するフロー毎帯域監視エントリ、12-1はユーザグループA、12-2はユーザグループBのフローグループ毎帯域監視エントリである。THRはバケツの深さ、POLRは監視帯域、TSは前回パケット到着時刻、CNTはバケツに蓄積されている水量を示すバケツ蓄積量、TOSCは遵守時のサービス識別子、TOSNは違反時のサービス識別子、QCは遵守時のキューイング優先度、QNは違反時のキューイング優先度、DROPは違反時の「廃棄」または「蓄積」の指示を示す。フロー検出部はフロー毎帯域監視をするためにパケットヘッダ内の情報のうちSIP711によりフロー識別子を判定する。フロー毎帯域監視テーブル制御部は、前記フロー識別子に対応するフロー毎帯域監視エントリを参照し、帯域監視に必要なTHR、POLR、TS、CNT、TOSC、TOSN、QC、QN、DROPのパラメタを読み出して、各々THR蓄積手段、POLR蓄積手段、TS蓄積手段、CNT蓄積手段、TOSC蓄積手段、TOSN蓄積手段、QC蓄積手段、QN蓄積手段、DROP蓄積手段に蓄積する。以下では、フローがユーザA1に属し、フローグループがユーザグループAに属する場合を説明する。
【００３２】
フロー毎バケツ蓄積量判定部では、パケット入力直前のバケツの水量を判定する。まず、バケツ蓄積量判定回路は現時刻をカウントするタイマーの値とTS蓄積手段のTS-A1との差分を計算し、バケツに水が前回蓄積されてから経過した経過時間を計算する。次に経過時間にPOLR蓄積手段内のPOLR-A1を乗じて、バケツに水が前回蓄積されてから漏れた水の量を計算する。更に、CNT蓄積手段内のCNT-A1からバケツ内水量減少量を減算して、パケットが入力する直前の水量であるバケツ蓄積量を判定する。前記バケツ蓄積量の正負を判定し、判定結果が負の場合にはバケツ蓄積量を0に修正する。
【００３３】
フロー毎監視結果判定部の監視結果判定回路は、入力パケットのパケット長に相当する水がバケツに入るか否かを判定する。まず、前記のバケツ蓄積量にパケット長を加算して、これをTHR蓄積手段内のTHR-A1と大小比較する。バケツ蓄積量+パケット長がTHR-A1よりも大なるときは、パケット長に相当する水を入力した場合にバケツが溢れてしまうので、入力パケットを違反パケットと判定して、この判定結果を監視結果総合判定部に送信する。バケツ蓄積量+パケット長がTHR-A1以下のときは入力パケットを遵守パケットと判定し、この判定結果を監視結果総合判定部に送信する。
【００３４】
フローグループ毎バケツ蓄積量判定部でも、フローグループ毎帯域監視テーブルから同様にして読み出したパラメタに対し同様の処理を繰り返し、判定結果を監視結果総合判定部に送信する。
【００３５】
監視結果総合判定部では、フロー毎の判定結果とフローグループ毎の判定結果に基づいて、このパケットに対する蓄積廃棄指示814、キューイング優先度815、サービス識別子713を判定して、これらを廃棄制御部660-jに送信する。ここでは、フローグループ毎契約帯域が最低帯域であって、フロー毎帯域監視違反時の制裁無し（遵守時と同じ判定）、フローグループ毎帯域監視違反時の制裁はサービス識別子とキューイング優先度の書き換えである場合を説明する。フロー毎の判定結果が「遵守」のパケットに対しては、蓄積指示となりTOSC-A1、QC-A1を廃棄制御部660-jに送信する。フロー毎の判定結果が「違反」かつフローグループ毎の判定結果が「遵守」のパケットに対しても、フロー毎帯域監視違反時の制裁無しであるから、蓄積指示となりTOSC-A1、QC-A1を廃棄制御部660-jに送信する。フロー毎の判定結果が「違反」かつフローグループ毎の判定結果が「違反」のパケットに対しては、蓄積指示となりTOSC-A、QC-Aを廃棄制御部660-jに送信する。これにより、フロー毎最低帯域MAi(i=1〜3)を必ず保証すると共に、フロー毎最低帯域を超過したユーザに対してもユーザグループAの最低帯域MAに余剰帯域のある場合はこれを有効活用できる。また、ユーザグループAの最低帯域MAを超過したパケットは、サービス識別子またはキューイング優先度を書き換えることにより自パケット転送装置内またはネットワーク内の他のパケット転送装置内において非優先パケットとして扱われる。
【００３６】
更に、フロー毎帯域監視の判定結果が「遵守」であった場合、バケツ蓄積量+パケット長を新たなバケツ蓄積量CNT-A1として、現時刻のタイマーの値を新たなTS-A1としてフロー毎帯域監視テーブル制御部に送信し、次の入力パケットに対してフロー毎帯域監視テーブルを読み出す前にユーザA1のフロー毎帯域監視エントリに書き込む。同様に、フローグループ毎帯域監視の判定結果が「遵守」であった場合にも新たなCNT-A、TS-Aをフローグループ毎帯域監視テーブルに書き込む。更に、本発明に固有の処理として、フローグループ毎帯域監視の判定結果が「違反」であった場合にも、フロー毎帯域監視結果が「遵守」であれば、新たなCNT-A、TS-Aを超過帯域分を示す超過帯域情報としてフローグループ毎帯域監視テーブルに書き込む。
【００３７】
図１３に帯域監視アルゴリズムのフローチャートを示す。13の処理、即ちフロー毎帯域監視判定結果が「遵守」であった場合に、新たなCNT-A、TS-Aを超過帯域分を示す超過帯域情報としてフローグループ毎帯域監視テーブルに書き込む処理が、本発明に固有の処理である。
【００３８】
【発明の効果】
本発明によれば、ユーザ毎に帯域監視すると共に、複数ユーザから構成されるユーザグループを多数収容してユーザグループ毎にも帯域監視することのできる高速な帯域監視装置を提供できる。更に、この帯域監視装置を用いて多数のユーザグループを収容することにより、ユーザグループ当たりの収容コストを低減できる。
【００３９】
また、本発明の帯域監視方法によれば、ユーザ毎に契約された最低帯域を必ず保証すると共に、更にユーザグループ毎の使用帯域に余剰帯域のある場合はこれを有効活用できる。
【図面の簡単な説明】
【図１】従来技術1のシェーピング装置の構成を示すブロック図。
【図２】従来技術2の帯域監視方法のフローチャート。
【図３】本発明で想定するネットワークの構成例を示す図。
【図４】（A）従来技術2とリーキーバケットアルゴリズムとを組み合わせた場合の課題を示す図。（B）本発明により、従来技術2の課題を解決することをリーキーバケットアルゴリズムのバケツ水量により示す図。
【図５】本発明により、従来技術2の課題を解決することをリーキーバケットアルゴリズムのバケツ水量により示す図。
【図６】本発明を適用するパケット転送装置のブロック図。
【図７】図３のネットワーク上のパケットのヘッダおよびデータ構成を示す図。
【図８】図６のパケット転送装置内のパケットの構成を示す図。
【図９】図６のパケット転送装置内の廃棄制御部のブロック図。
【図１０】本発明の帯域監視部のブロック図。
【図１１】フロー毎帯域監視テーブルのフォーマット。
【図１２】フローグループ毎帯域監視テーブルのフォーマット。
【図１３】本発明の帯域監視方法のフローチャート。
【符号の説明】
600…パケット転送装置、610…入力回線、640…パケット中継処理手段、680…出力回線、11…フロー毎帯域監視エントリ、12…フローグループ毎帯域監視エントリ、13…フロー毎帯域監視判定結果が「遵守」であった場合に、新たなCNT-A、TS-Aを超過帯域分を示す超過帯域情報としてフローグループ毎帯域監視テーブルに書き込む処理。
【図１】
0004069818.tif 000002
【図２】
0004069818.tif 000003
【図３】
0004069818.tif 000004
【図４】
0004069818.tif 000005
【図５】
0004069818.tif 000006
【図６】
0004069818.tif 000007
【図７】
0004069818.tif 000008
【図８】
0004069818.tif 000009
【図９】
0004069818.tif 000010
【図１０】
0004069818.tif 000011
【図１１】
0004069818.tif 000012
【図１２】
0004069818.tif 000013
【図１３】
0004069818.tif 000014