(57)【特許請求の範囲】
【請求項１】
パケットスイッチを行なうノード、端末およびリンクを構成要素とするネットワーク中のある構成要素Aから別のある構成要素Bへ転送されるトラヒックに対して帯域を割り当てる帯域制御方法において、前記構成要素Aを入力側とし、前記構成要素Bを出力側とし、前記入力側は前記出力側に制御パケットを送信する際、前記制御パケットの送信時刻と、前記送信時刻までに入力側から出力側に送信したデータパケットの累積量とに関する情報を前記制御パケットに書き込み、前記出力側は前記入力側より前記制御パケットを受信したら、これに前記制御パケットの受信時刻と、前記受信時刻までに受信したデータパケットの累積量とに関する情報を書き加えて前記入力側に返送し、前記入力側は、前記出力側より、今回新たに受信した制御パケットと前回受信した制御パケットとにそれぞれ含まれる情報に基づいて、前記出力側に送信すべきデータパケットの送信許容レートを決定することを特徴とする帯域制御方法。
【請求項２】
入力側は出力側より新たに制御パケットを受信すると、今回新たに受信した前記制御パケットと前回受信した制御パケットとにそれぞれ含まれる制御パケットの送信時刻と前記送信時刻までに入力側が送信したデータパケットの累積量とから送信レートを算出すると共に、次に今回新たに受信した制御パケットと前回受信した制御パケットとにそれぞれ含まれる制御パケットの受信時刻と前記受信時刻までに出力側が受信したデータパケットの累積量とから受信レートを算出し、今回算出した前記送信レートおよび前記受信レートと、前回制御パケットを受信した際に算出しておいた送信レートおよび受信レートとから送信レートの変化分および受信レートの変化分をそれぞれ算出し、前記受信レートの変化分が、前記送信レートの変化分とある一定値との積より大きい場合は、入力側の送信許容レートを増加し、そうでない場合は前記送信許容レートを削減することを特徴とする請求項１記載の帯域制御方法。
【請求項３】
帯域制御の入力側および出力側がそれぞれノードであることを特徴とする請求項１または２記載の帯域制御方法。
【請求項４】
帯域制御の入力側および出力側がそれぞれ端末であることを特徴とする請求項１または２記載の帯域制御方法。
【請求項５】
帯域制御の入力側がノードであり、出力側がリンクまたは端末であることを特徴とする請求項１または２記載の帯域制御方法。
【請求項６】
帯域制御の入力側が端末であり、出力側がリンクまたはノードであることを特徴とする請求項１または２記載の帯域制御方法。
【請求項７】
帯域制御の入力側がリンクであり、出力側がリンクまたはノードまたは端末であることを特徴とする請求項１または２記載の帯域制御方法。
【請求項８】
帯域制御の対象として入力側から出力側に流れるトラヒックは、ノードもしくはリンクもしくは端末のみならず、さらに加えてトランスポートレイヤのプロトコルもしくはアプリケーションレイヤのプロトコルに基づいて特定されることを特徴とする請求項１乃至７の何れか１項に記載の帯域制御方法。
【請求項９】
前記ネットワークにおけるある構成要素Cが終端するリンクDの輻輳状態を検出し、それに対する帯域制御要求を前記構成要素Cとは別の一つもしくは複数の構成要素に通知することを帯域制御の開始の契機とし、前記構成要素Cとは別の一つもしくは複数の前記構成要素のおのおのを前記帯域制御の入力側とし、前記構成要素Cを前記帯域制御の出力側とし、前記入力側から前記リンクD上に転送されるトラヒックに対して請求項１または請求項２に記載の帯域制御方法を実施することで前記リンクDに検出された輻輳状態の回復を図ることを特徴とする輻輳制御方法。
【請求項１０】
帯域制御の解除は少なくとも前記入力側での輻輳状況に基づいて決定されることを特徴とする請求項９記載の輻輳制御方法。
【請求項１１】
帯域制御の入力側および出力側がそれぞれノードであることを特徴とする請求項９または１０記載の輻輳制御方法。
【請求項１２】
帯域制御の入力側および出力側がそれぞれ端末であることを特徴とする請求項９または１０記載の輻輳制御方法。
【請求項１３】
出力側である端末が制御パケットに書き込むデータパケットの累積量は、端末が受信したデータ量ではなく端末が処理したデータ量に基づいて決定することを特徴とする請求項１２記載の輻輳制御方法。
【請求項１４】
帯域制御の対象として入力側から出力側に流れるトラヒックは、ノードもしくはリンクもしくは端末のみならずトランスポートレイヤのプロトコルもしくはアプリケーションレイヤのプロトコルに基づいて特定されることを特徴とする請求項９乃至１３の何れか１項に記載の輻輳制御方法。
【請求項１５】
データパケットを送信する毎にそれまでの送信データ累積量を更新する手段と、一定時間毎に送信時刻と前記送信データ累積量とに関する情報を含む制御パケットを帯域制御の出力側に送信する手段と、前記制御パケットを受信した前記出力側が前記制御パケットの受信時刻とそれまでの受信データ累積量とに関する情報を前記制御パケットに書き加えて返送してきたときに前記制御パケットを受信する手段と、前記受信した制御パケットと前回受信した制御パケットとにそれぞれ含まれる情報に基づいて、前記出力側に送信すべきデータパケットの送信許容レートを決定する手段とを備えることを特徴とするネットワーク構成装置。
【請求項１６】
前記送信許容レートを決定する手段は、今回新たに受信した前記制御パケットと前回受信した制御パケットとにそれぞれ含まれる制御パケットの送信時刻と前記送信時刻までに入力側が送信したデータパケットの累積量とから送信レートを算出する手段と、今回新たに受信した制御パケットと前回受信した制御パケットとにそれぞれ含まれる制御パケットの受信時刻と前記受信時刻までに出力側が受信したデータパケットの累積量とから受信レートを算出する手段と、今回算出した前記送信レートおよび前記受信レートと、前回制御パケットを受信した際に算出しておいた送信レートおよび受信レートとから送信レートの変化分および受信レートの変化分をそれぞれ算出する手段と、前記受信レートの変化分が、前記送信レートの変化分とある一定値との積より大きい場合は、入力側の送信許容レートを増加し、そうでない場合は前記送信許容レートを削減する手段とを備えることを特徴とする請求項１５に記載のネットワーク構成装置。
【請求項１７】
データパケットを受信する毎にそれまでの受信データ累積量を更新する手段と、帯域制御の入力側から送信時刻とそれまでの送信データ累積量とに関する情報を含む制御パケットを受信する手段と、受信した前記制御パケットに前記制御パケットの受信時刻と前記受信データ累積量とに関する情報を書き加えて前記入力側に返送する手段とを備えることを特徴とするネットワーク構成装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、通信ネットワークにおける帯域制御方法および輻輳制御方法に関し、特にインターネットにおける１組のノードもしくは１組の端末もしくはノードと端末の間などで実行される帯域制御方法および輻輳制御方法に関する。
【０００２】
【従来の技術】
インターネットにおいては、ネットワーク資源に対して加えられるトラヒック量がネットワークの容量をこえる過負荷が継続するという状態が発生しうる。これを輻輳状態と呼ぶ。ここでネットワーク資源とはノードにおけるバッファの蓄積容量やノードが終端するリンクの伝送容量である。こうした輻輳を防止もしくは回復するための制御を一般に輻輳制御と呼ぶが、ここでは以下、輻輳の発生を回避するための制御を特に輻輳防止制御と呼び、また発生した輻輳を回復するための制御を輻輳回復制御と呼んで区別する。
【０００３】
インターネットにおいては、従来こうした輻輳防止制御は、端末に実装されているTCPにおけるウインドサイズの動的な変更によって実現されている。ここで端末はノードとは異なり、トランスポートレイヤおよびアプリケーションレイヤのプロトコルが実装されている。また、TCPとはInternetworking with TCP/IP volume 1 Douglas E. Comer著 Prentice Hall刊でも解説されているように、１組の端末間で信頼性の高い通信を行なうためのプロトコルでトランスポートレイヤに位置する。またウインドサイズとは、送信側の端末が、パケットの正常な受信に対して受信側の端末が送信側の端末に返送する確認応答を待つことなく、送信側の端末が連続して送信できるデータ量をさす。そして、輻輳防止のためのウインドサイズの動的な変更では、送信側の端末が確認応答を受信する毎にウインドサイズを一定量増やし、データパケットの廃棄を検出した場合は、ウインドサイズを半分に減らす。
【０００４】
これに対し、David Harrison, Shivkumar Kalyanaraman, "Edge-To-Edge Traffic Control for the Internet," RPI ECSE Networks Laboratory Technical Report, ECSE-NET-2000-1. March 2000では、ネットワーク内の１組のエッジノード間に転送されるトラヒックに対して帯域を適応的に割り当てる帯域制御方法が提案されている。ここでエッジノードとは端末を収容するノードをさす。この帯域制御方法によれば、ネットワーク内の輻輳は各エッジノードに分散されるので、ノード内バッファでのパケットの平均的蓄積量を削減したり、また各TCPのコネクションが得られるスループットの公平性を向上させたりという効果がもたらされる。
【０００５】
また、もともと輻輳防止機構を組み込んでいないトランスポートプロトコル（例えばUDP）もしくはアプリケーションプロトコルに基づくトラヒックがネットワーク内に大量流入して発生する深刻な輻輳状態を回避する輻輳防止制御をネットワーク側で実行できる。ここでUDPとはInternetworking with TCP/IP volume 1 Douglas E. Comer著 Prentice Hall刊にも解説されているように、データの信頼性の高い転送は保証しないものの、データが発生したら直ちに転送できるためのプロトコルで、トランスポートレイヤに相当する。TCPのトラヒックのみが存在するネットワークに大量のUDPのトラヒックが流入して輻輳状態になると、TCPのトラヒックはそこに組み込まれている輻輳防止機構により流入量を自ら削減してしまう追出しという問題も、この帯域制御方法によれば発生しない。
【０００６】
ここで、上記の従来の帯域制御方法について具体的に説明する。以下、帯域制御をその間で実行する１組のノードにおいて、データパケットを送信するノードを入力側と呼び、データパケットを受信するノードを出力側と呼ぶ。帯域制御は入力側から出力側へ転送されるトラヒックに対して帯域を適応的に割り当てることになる。また、入力側と出力側との間で帯域制御を行なうための情報をやりとりするためのパケットを特に制御パケットと呼んでデータパケットと区別する。さらに、入力側が出力側に送信する制御パケットを特に順方向制御パケット、出力側が入力側に送信する制御パケットを逆方向制御パケットと呼ぶ。
【０００７】
入力側は出力側へのパケット（データパケットと順方向制御パケットとを含む）の送信許容レートｒを算出するが、これによりパケットの送出を制御する方法としてはトークンバケットシェイパーがある。図９はこのメカニズムを説明する図である。送信許容レートｒに対して、一定のサイズSをもつトークンを一定レートr/Sで発生させ、最大サイズσを持つトークンバケットに蓄積する。到着したパケットは、そのサイズ分だけトークンの総量がある場合は転送され、その時トークンバケット内の蓄積量は転送されたパケットサイズ分だけ減算される。もし、到着したパケットのサイズにトークンの総量が達しない場合は、レートr/Sでトークンを生成することでトークン蓄積量が到着したパケットのサイズに達するまでそのパケットはバッファで待たされる。
【０００８】
以下、パケットの送信許容レートｒの算出方法について説明する。入力側は一定時間T毎に順方向制御パケットを発生させ、送信中のデータパケットを妨げない範囲でなるべく速やかに送信する。その際、順方向制御パケットには、順方向制御パケットの実際の送信時刻と入力レートλとを書き込んでおく。ここでλは、２つの連続して送信した順方向制御パケットの送信時間間隔τの間に送信したデータパケットのデータ総量をτで割ったものである。
【０００９】
出力側では、順方向制御パケットを受信するたび、前回受信した時刻との時間間隔ηの間に受信したデータパケットのデータ総量をηで割って出力レートνを計算する。これより、出力側は、蓄積量の移動平均値ｑをｑ←ｑ＋（λ‐ν）×τで更新する。ここで蓄積量とは、帯域制御における入力側と出力側との間の経路上の各ノードが、この帯域制御の対象となるトラヒックに関して蓄積していると考えられるパケットの総量である。そして、出力側では、現在が輻輳期間でない場合は、このｑがトークンバケットシェイパーのバケットサイズσ以上の場合は輻輳期間に入ったと判定し、νを含む逆方向制御パケットを入力側に戻す。そして、出力側は輻輳期間である限りは、順方向制御パケットを受信するごとに、入力側にνを含む逆方向制御パケットを返す。輻輳期間を出ているときは逆方向制御パケットは返さない。
【００１０】
入力側では、この逆方向制御パケットを受け取ると、送信許容レートｒをｒ←β×νに設定する。ここでβは１未満の定数である。またこのパケットを受け取らない間は、T時間ごとに送信許容レートｒを一定値αだけ加算して、ｒ←ｒ＋αと更新する。よって逆方向制御パケットは負のフィードバックになっている。
【００１１】
出力側での輻輳期間を解除する判断は次のようにしておこなう。すなわち、順方向制御パケットに挿入された順方向制御パケットの送信時刻と、出力側がそのパケットを受信した時刻との差分を一方向転送遅延の測定値とし、これと現在までに測定した一方向転送遅延の最小値との差が一定値以下の場合に輻輳期間は解除されたと判断する。
【００１２】
ところで、ネットワーク内の特定個所へのトラヒック集中によって発生した輻輳を回復するための輻輳回復制御方法として、従来、John Ioannidis and Steven M. Bellovin, "Implementing Pushback: Router-Based Defense Against DDoS Attacks", Network and Distributed System Security Symposium, February 2002に次のような方法が提案されている。ここでは、終端する特定のリンクへトラヒックが集中することによってパケットの廃棄が比較的長時間継続すると、そのリンクを終端するノードは輻輳状態が発生したと判断し、そのノードはその原因となるトラヒックを特定して、それらに対してレート制限をかける。ここでレート制限の対象となるトラヒックは、宛先IPアドレスもしくは宛先IPアドレス接頭辞に基づいて特定する。レート制限は前述のトークンバケットシェイパーにおいて、バッファのサイズを０としたものである。すなわち到着したパケットはその場でパケットサイズ分のトークン量を得られない場合は直ちに廃棄される。
【００１３】
輻輳状態を最初に検出したノードが実施するレート制限においてパケットの廃棄が継続する場合は、レート制限の対象となるトラヒックを上流からそのノードへ転送してくる各隣接ノードに対してPushbackと呼ばれるレート制限を要求するための制御パケットを転送する。その際、Pushbackを転送するノードは、隣接する各上流ノードが用いる送信許容レートの上限を決定して書き込んでおく。Pushbackを受け取った上流の各隣接ノードは、指定されたトラヒックに対して指定された送信許容レートにそったレート制限をかける。こうした動作はさらに上流のノードに向かって繰り返される。
【００１４】
このレート制限は一定時間ｔが過ぎると解除されるいわゆるソフトステートの機構を採用している。すなわち、輻輳状態を検出したノードEは、輻輳回復制御を継続したい場合は、ｔよりも短い一定時間ごとにPushbackメッセージを上流に転送して、レート制限要求のリフレッシュを行なう。このために、別途、上流ノードから、レート制限の対象となるトラヒックの経路上で隣接する下流ノードに状態通知メッセージが送信され、これは最終的に最下流に位置するノードEまで転送される。このメッセージの中には、状態通知メッセージを生成して転送するノードにその上流の隣接ノードから、レート制限の対象となるトラヒックが到着するレートの総和が書かれている。よって、状態通知メッセージが最下流のノードEに到着するときは、レート制限の対象となるトラヒックの到着レートの網内における総和が書かれている。ノードEはその総和が必要以上に下がったと判断すると、Pushbackメッセージを上流に転送しなくなり、ｔ時間以上送信しないと上流の各ノードにおけるレート制限は行なわれなくなる。
【００１５】
【発明が解決しようとする課題】
１番目の課題は、従来の帯域制御方法では制御パケットが紛失すると帯域制御が適切に動作しないことである。その理由は以下による。すなわち、入力側から送信した順方向制御パケットが廃棄された場合、出力側では蓄積量を更新することが出来なくなり、輻輳期間に入ったことを判断できず、ネットワーク内に輻輳が発生した場合でも入力側の送信許容レートｒを削減させることができない。また、出力側から送信した逆方向制御パケットが紛失しても、同じくｒを削減させることができない。そして、さらに悪いことには、入力側は負のフィードバックを意味する逆方向制御パケットを受信できないと、ネットワークが輻輳状態にあるにもかかわらず送信許容レートｒを増加させることになってしまうからである。
【００１６】
２番目の課題は、従来の帯域制御方法において、ダイナミックルーチングプロトコル等により、現在の経路が伝搬遅延のより大きな経路に切り替わった場合、輻輳期間が依然として継続していると誤った判断を下し、輻輳期間の解除を行なうことができなくなってしまう。こうなると輻輳期間に入っていないのにもかかわらず、送信許容レートを増加させることはできなくなってしまう。その理由は、出力側での輻輳期間の解除は、一方向転送遅延を測定してこれが最小遅延との差が一定値以下の場合に判断するからである。
【００１７】
３番目の課題は、従来のトラヒック集中に対する輻輳回復制御方法は、輻輳防止機構が組み込まれていないプロトコルによるトラヒックが引き起こす輻輳を防止することは出来ないということである。その理由は輻輳状態を検出してからレート規制を実行するからである。
【００１８】
よって、この輻輳防止制御も同じネットワーク内で行なう場合は、コストがその分増えるという問題がでてくる。その理由は、輻輳防止制御のためには、輻輳回復制御とは別の、例えば従来の帯域制御方法のようなものを実施する必要があるからである。
【００１９】
本発明の目的は，制御パケットの廃棄にも、経路の変更にも耐性のある帯域制御方法を提供することにある。また、輻輳防止機構がないプロトコルによるトラヒックの流入で発生する輻輳の回避に対しても、特定個所にトラヒックが集中することで発生した輻輳の回復に対しても、共通の帯域制御方法に基づいてコスト効率良く対処できる輻輳制御方法を提供することである。
【００２０】
【課題を解決するための手段】
本発明の帯域制御方法は、パケットスイッチを行なうノード、端末およびリンクを構成要素とするネットワーク中の任意のある構成要素Aから別の任意のある構成要素Bへ転送されるトラヒックに対して帯域を割り当てる帯域制御方法において、前記構成要素Aを入力側とし、前記構成要素Bを出力側とし、前記入力側は前記出力側に制御パケットを送信する際、前記制御パケットの送信時刻と、前記送信時刻までに入力側から出力側に送信したデータパケットの累積量とに関する情報を前記制御パケットに書き込み、前記出力側は前記入力側より前記制御パケットを受信したら、これに前記制御パケットの受信時刻と、前記受信時刻までに受信したデータパケットの累積量とに関する情報を書き加えて前記入力側に返送し、前記入力側は、前記出力側より、今回新たに受信した制御パケットと前回受信した制御パケットとにそれぞれ含まれる情報に基づいて、前記出力側に送信すべきデータパケットの送信許容レートを決定することを特徴とする。
【００２１】
本発明の帯域制御方法においては、入力側は出力側より新たに制御パケットを受信すると、今回新たに受信した前記制御パケットと前回受信した制御パケットとにそれぞれ含まれる制御パケットの送信時刻と前記送信時刻までに入力側が送信したデータパケットの累積量とから送信レートを算出すると共に、次に今回新たに受信した制御パケットと前回受信した制御パケットとにそれぞれ含まれる制御パケットの受信時刻と前記受信時刻までに出力側が受信したデータパケットの累積量とから受信レートを算出し、今回算出した前記送信レートおよび前記受信レートと、前回制御パケットを受信した際に算出しておいた送信レートおよび受信レートとから送信レートの変化分および受信レートの変化分をそれぞれ算出し、前記受信レートの変化分が、前記送信レートの変化分とある一定値との積より大きい場合は、入力側の送信許容レートを増加し、そうでない場合は前記送信許容レートを削減するようにしてよい。
【００２２】
本発明の帯域制御方法においては、帯域制御の入力側および出力側はネットワークの任意の構成要素としてよい。すなわち、入力側および出力側がそれぞれノードであっても、端末であっても、リンクであってもよいし、入力側がノードで出力側がリンクまたは端末、入力側が端末で出力側がリンクまたはノード、入力側がリンクで出力側がノードまたは端末であってもよい。
【００２３】
また本発明の輻輳制御方法は、前記ネットワークにおけるある構成要素Cが終端するリンクDの輻輳状態を検出し、それに対する帯域制御要求を前記構成要素Cとは別の一つもしくは複数の構成要素に通知することを帯域制御の開始の契機とし、前記構成要素Cとは別の一つもしくは複数の前記構成要素のおのおのを前記帯域制御の入力側とし、前記構成要素Cを前記帯域制御の出力側とし、前記入力側から前記リンクD上に転送されるトラヒックに対して上述した帯域制御方法を実施することで前記リンクDに検出された輻輳状態の回復を図ることを特徴とする。
【００２４】
本発明の輻輳制御方法においては、帯域制御の解除は少なくとも前記入力側での輻輳状況に基づいて決定されるようにしてよい。
【００２５】
本発明の輻輳制御方法においては、帯域制御の入力側および出力側はネットワークの任意の構成要素としてよい。すなわち、入力側および出力側がそれぞれノードであっても、端末であっても、リンクであってもよいし、入力側がノードで出力側がリンクまたは端末、入力側が端末で出力側がリンクまたはノード、入力側がリンクで出力側がノードまたは端末であってもよい。
【００２６】
また本発明の帯域制御方法および輻輳制御方法においては、帯域制御の対象として入力側から出力側に流れるトラヒックは、ノードもしくはリンクもしくは端末のみならず、さらに加えてトランスポートレイヤのプロトコルもしくはアプリケーションレイヤのプロトコルに基づいて特定されるものであってよい。
【００２７】
本発明のネットワーク構成装置は、データパケットを送信する毎にそれまでの送信データ累積量を更新する手段と、一定時間毎に送信時刻と前記送信データ累積量とに関する情報を含む制御パケットを帯域制御の出力側に送信する手段と、前記制御パケットを受信した前記出力側が前記制御パケットの受信時刻とそれまでの受信データ累積量とに関する情報を前記制御パケットに書き加えて返送してきたときに前記制御パケットを受信する手段と、前記受信した制御パケットと前回受信した制御パケットとにそれぞれ含まれる情報に基づいて、前記出力側に送信すべきデータパケットの送信許容レートを決定する手段とを備えたノード装置または端末装置であって、前記出力側と協調して当該ネットワーク構成装置から前記出力側へ転送されるトラフィックに対して帯域を割り当てる帯域制御を実行する。
【００２８】
本発明の上記ネットワーク構成装置において、前記送信許容レートを決定する手段は、今回新たに受信した前記制御パケットと前回受信した制御パケットとにそれぞれ含まれる制御パケットの送信時刻と前記送信時刻までに入力側が送信したデータパケットの累積量とから送信レートを算出する手段と、今回新たに受信した制御パケットと前回受信した制御パケットとにそれぞれ含まれる制御パケットの受信時刻と前記受信時刻までに出力側が受信したデータパケットの累積量とから受信レートを算出する手段と、今回算出した前記送信レートおよび前記受信レートと、前回制御パケットを受信した際に算出しておいた送信レートおよび受信レートとから送信レートの変化分および受信レートの変化分をそれぞれ算出する手段と、前記受信レートの変化分が、前記送信レートの変化分とある一定値との積より大きい場合は、入力側の送信許容レートを増加し、そうでない場合は前記送信許容レートを削減する手段とを備えるようにしてよい。
【００２９】
また本発明のネットワーク構成装置は、データパケットを受信する毎にそれまでの受信データ累積量を更新する手段と、帯域制御の入力側から送信時刻とそれまでの送信データ累積量とに関する情報を含む制御パケットを受信する手段と、受信した前記制御パケットに前記制御パケットの受信時刻と前記受信データ累積量とに関する情報を書き加えて前記入力側に返送する手段とを備えたノード装置または端末装置であって、前記入力側と協調して当該ネットワーク構成装置へ前記出力側から転送されてくるトラフィックに対して帯域を割り当てる帯域制御を実行する。
【００３０】
【作用】
図７は入力側と出力側でのパケットのやりとりを示したものである。入力側が出力側に送信した制御パケットを出力側が受信した場合は、出力側はそれを必ず入力側に返信する。そして、入力側では制御パケットを受信したときにのみ、それに含まれる情報に基づいて送信許容レートを決定する。よって、制御パケットが入力側から出力側へ転送時に、もしくは出力側から入力側に返送時にそれぞれ廃棄されても悪影響を及ぼすような特定の動作を起すことがない。
【００３１】
図８は一般のネットワークにおける入力レートに対する出力レートの変化を例示したものである。入力レートの増加にともなって出力レートも増加するが、入力レートが十分大きくなると、パケットの遅延や廃棄により出力レートは飽和し一定になる。これが輻輳状態である。よって、入力レートの変化に対する出力レートの変化の割合、すなわち微分値に相当するものが計算できれば、その値が一定値以上である場合は送信許容レートを増やし、０に近づいたらそれを減らすというような制御を行なえば、送信量を出力レートが飽和し始める値一杯に近づけることが可能となる。よって、この帯域制御は、出力レートが飽和している輻輳状態から開始すれば輻輳回復制御となり、出力レートが飽和していない非輻輳状態から開始すれば輻輳防止制御となる。
【００３２】
【発明の実施の形態】
本発明の第１の実施の形態について図面を参照して詳細に説明する。図２は帯域制御が実施されるネットワークの物理構成を示したものである。ノード１０１〜１０６、リンク２、および端末３から構成される。端末３を収容するノードを特にエッジノード呼び、ノード１０１〜１０４がこれに相当する。エッジノードのみを接続するノードを特にコアノードと呼び、ノード１０５と１０６がこれに相当する。以下、ノードを特に限定しない場合、参照符号１を付けてノード１と称する。
【００３３】
図３はその物理構成において、帯域制御の対象となるトラヒックの流れを示したものである。ここでは、帯域制御が、任意の１組のエッジノード間で両方向に流れるトラヒックに対して実施される。これにより、図２で示すネットワーク内の任意のリンク２において発生する輻輳を回避することができる。
【００３４】
次に、帯域制御の詳しい動作について説明する。まず、概要について述べる。作用で説明したように、送信許容レートを決定するためには、入力レートの変化値および出力レートの変化値を計算する必要がある。そのために、入力側が出力側に入力レートを算出するための情報を含む制御パケットを送信すると、それに対して、出力側は入力側に出力レートを算出するための情報をさらに加えた制御パケットを返信する。そして入力側は制御パケットを受信するごとに入力レートと出力レートを算出し、またそれからそれぞれの変化分を計算して、これに基づいて送信許容レートを更新する。
【００３５】
以下、より具体的にこれを説明する。入力側は一定時間T毎に制御パケットを発生させ、現在送信中のデータパケットがあればそれを妨げない範囲でなるべく早く出力側に送信する。その際、制御パケットには、その送信時刻STと、それまでの送信したデータパケットのサイズの累積量SBとを書き込んでおく。
【００３６】
出力側では、この制御パケットを受信すると、さらにその受信時刻DTと、それまでに受信したデータパケットのサイズの累積量DBを書き加えて入力側に返送する。よって、入力側に戻ってきた制御パケットには、SB、ST、DB、DTの４つの値が書き込まれている。これにもとづき、入力側では以下のようにして入力レートλおよび出力レートνを計算する。
【００３７】
すなわち、SB、ST、DB、DT、λ、νの値は変数にいれて保持し、制御パケットを受信するごとに更新する。この変数は、前回制御パケットを受信したときの値を保持する変数は下付文字oldで、今回受信したときの値を保持する変数は下付文字newでそれぞれ区別する。今回制御パケットを受信したらその中の情報をそれぞれSBnew、SＴnew 、DBnew、DＴnewに保持する。次に、これらと前回受信したときに保持した情報SBold、SＴold 、DBold、DＴoldとから、下記の式で今回の入力レートλnew、および出力レートνnewを次式で算出して保持する。
λnew←(SBnew-SBold)/(STnew-STold)，νnew←(DBnew-DBold)/(DTnew-DTold)…（１）
【００３８】
すなわち、２つの連続して送信もしくは受信した制御パケットの間に送信もしくは受信したデータパケットのサイズの総和を送信間隔もしくは受信間隔でそれぞれ割って、送信レートおよび受信レートを算出する。次に、入力側が今回制御パケットを受信した時の入力レートの変化値Δλ, および出力レートの変化値Δνを、前回制御パケットを受信したときに算出して保持しておいた入力レートλoldおよび出力レートνoldを用いて次のように計算する。
Δλ=λnew-λold , Δν=νnew-νold     …（２） 
【００３９】
入力側はこれらのレートの変化分を用いて、以下のようにして送信許容レートｒを更新する。すなわち入力レートの変化分に対する出力レートの変化分の割合が一定値γ以上なら、ｒを一定値αだけ増やす。さもなければｒを一定値αだけ減らす。すなわち
Δν＞γ×Δλ ならば ｒ←ｒ+α、さもなければ、ｒ←ｒ-α     …（３）
ここで、レート変化分の割合であるΔν／Δλを計算しないのは、Δλ＝０となる場合に計算不能となるからである。
【００４０】
最後に、次回制御パケットを受信したときの算出に備えるために変数をつぎの様に更新しておく。
SBold←SBnew、STold←STnew、DBold←DBnew、DTold←DTnew、λold←λnew 、νold←νnew     …（４）
【００４１】
ここで、帯域制御を実行するノードは、送受信する制御パケットが関与する、帯域制御の対象となるトラヒックを識別できる必要がある。このため本実施の形態では、入力トラヒック識別子および出力パケット情報識別子と呼ばれるものを用いる。よって、制御パケットは少なくとも次に示す情報の組み合わせを含む。（入力トラヒック識別子、出力トラヒック識別子、送信時刻、送信データ累積量、受信時刻、受信データ累積量）
【００４２】
これらの情報を含む制御パケットはIPパケットに乗せて運ばれる。その際、この制御パケットを識別するためにあらかじめ割り当てられた特定のプロトコル番号が用いられる。また、制御パケットを運ぶIPパケット内のIPアドレスは、入力側および出力側のノードにそれぞれ割り振られたIPアドレスを用いる。
【００４３】
なお、本実施の形態では、図３に示すように、各エッジノード間に流れるトラヒックの全体に対して帯域制御を行なうので、入力／出力トラヒック識別子はそれらのエッジノードを特定するもの、たとえばそのノードに割り振られたIPアドレスを用いればよい。
【００４４】
ここで、データ累積量を制御パケット内で表現できる量には一般に制限量Mがあり、これを超えた場合はMを引いてM未満になった値を書き込む。よって、制御パケットに書き込まれた今回のデータ累積量が前回のデータ累積量より小さい場合は、（今回のデータ累積量）-（前回のデータ蓄積量）+Mを、２つの連続した制御パケットを受信した間に入力もしくは出力したデータパケットのサイズの総量とする。よって制限量Mは、制御パケットの発生時間間隔T内に最大送信可能なデータパケットのサイズの総量よりも十分大きな値にする必要がある。
【００４５】
同じくして、送信時刻もしくは受信時刻を制御パケット内で表現できる量にも制限量Qがあるので、データ累積量と同じくして、今回の時刻が前回の時刻よりも小さい場合は、（今回の時刻）-（前回の時刻）+Qを、隣接する２つの制御パケットの送信もしくは受信間隔とする。よって、制限量Qは、制御パケットの発生時間間隔Tに制御パケットが送信もしくは返信時に連続して廃棄される個数の平均値aをかけたもの(T*a)よりも十分大きな値にする必要がある。
【００４６】
次に、以上に基づいて、入力側および出力側における動作をフローチャートにまとめると図１のようになる。
【００４７】
図１（A）は入力側における動作を示すフローチャートである。データパケットを送信したら（ステップA1）、保持している送信データ累積量にそのパケットのバイト長を加えて新たな送信データ累積量とする（ステップA2）。
【００４８】
T時間経過したら（ステップB1）、送信時刻と送信データ累積量とに関する情報を含む制御パケットを出力側に送信する（ステップB2）。
【００４９】
出力側から制御パケットを受信したら（ステップC1）、その中の情報を保持する（ステップC2）。次に、今回制御パケットを受信して保持した制御パケット内の情報と前回制御パケット受信時に保持した制御パケット内の情報とから、式（１）より今回の入力レートと出力レートを計算して保持する（ステップC3）。次にこれらと、前回制御パケット受信時に算出して保持していた入力レートと出力レートから式（２）を用いて各レートの変化分を計算し（ステップC4）、次にこれにもとづいて送信許容レートを式（３）を用いて算出し(ステップC5)、最後に式（４）に示すように新しい値を古い値を表す変数に代入して次回の計算に備える(ステップC6)。
【００５０】
図１（B）は出力側の動作を示すフローチャートである。データパケットを受信したら（ステップD1）、保持している受信データ累積量にそのパケットのサイズを加えて新たな受信データ累積量とする（ステップD2）。制御パケットを受信したら（ステップE1）、制御パケットの返信時刻（受信時刻）と、受信データ累積量を書き込んで入力側に返送する(ステップE2)。
【００５１】
第1の実施の形態の変形例として、送信許容レートｒに最低保証値ｍ、および最大許容値Mがある場合を考える。特に最低保証値を設定するのは、帯域を保証するトラヒックを収容する場合である。また、最大許容値を設定するのは、入力側のリンクの最大速度に物理的な限界があることを考慮する場合である。rがｍとMの間の範囲で変更されるようにするために、式（３）は以下のように変更する。すなわち、
Δμ＞γ×Δλ ならば ｒ←min{ｒ+α, M}、さもなければ ｒ←max{ｒ‐α, m}…（５）
【００５２】
第１の実施の形態のもう一つの変形例として、入力／出力トラヒック識別子には、ノードを特定するものに加えて、トランスポートレイヤのプロトコルもしくはアプリケーションレイヤのプロトコルを識別するものを加える。Internetworking with TCP/IP volume 1 Douglas E. Comer著 Prentice Hall刊にも解説されているように、トランスポートレイヤのプロトコルはIPパケットのヘッダーに含まれるプロトコル番号により識別でき、また、アプリケーションレイヤのプロトコルは、TCPもしくはUDPパケットのヘッダーに含まれるポート番号により識別できる。 よって、入力／出力トラヒック識別子は例えば、（入力／出力側ノードのIPアドレス、プロトコル番号）、もしくは（入力／出力側ノードのIPアドレス、ポート番号）の組み合わせで与える。これにより、ある1組のノード間で特定のプロトコルを用いたトラヒックに対して帯域制御を実施することができる。例えば、輻輳防止機構のないUDPのトラヒックに対してネットワーク側で輻輳防止制御を行なう場合を考える。エッジノード１０１からエッジノード１０４へのUDPのトラヒックを識別するための入力／出力トラヒック識別子は（ノード１０１のIPアドレス／ノード１０４のIPアドレス、UDPに関するポート番号）で与える。
【００５３】
本発明の第２の実施の形態は、第１の実施の形態で述べた帯域制御の入力側も出力側も、いずれもノード１ではなく端末３となるものである。そして、帯域制御の対象となるトラヒックを、入力側および出力側の端末のみならず、輻輳制御機構のないストリーミングプロトコルによって限定する。図４は端末３０４から、端末３０１〜３０３にそれぞれ転送されるストリーミングプロトコルのトラヒックに対して帯域制御をかける場合を示している。ここで、端末３０４はストリーミングコンテンツのサーバーであり、端末３０１から３０３はそのクライアントに相当する。例えば端末３０４から３０１に転送されるストリーミングトラヒックに実施される帯域制御における入力トラヒック識別子は（端末３０４のIPアドレス、ストリーミングプロトコルのサーバー側に関するポート番号）の組み合わせで、出力トラヒック識別子は（端末３０１のIPアドレス、ストリーミングプロトコルのクライアント側に関するポート番号）の組み合わせでそれぞれ与える。
【００５４】
本発明における第３の実施の形態について図面を用いて詳細に説明する。図２の物理構成をもつネットワークにおいて、特にエッジノード１０４につながる特定の端末３にトラヒックが集中して輻輳が起こっている場合、帯域制御によってこれを回復することを考える。よって、帯域制御の対象となるトラヒックは、図５に示すように、各エッジノード１０１〜１０３のそれぞれから、端末３０１を接続するリンク２１０に流れることになる。よって例えばノード１０１からリンク２１０に転送されるトラヒックに対して実施される帯域制御における入力トラヒック識別子はノード１０１に割り振られたIPアドレスで、また出力トラヒック識別子はリンク２１０に割り振られたIPアドレスであたえる。つまり、本実施の形態では出力側はリンクである。
【００５５】
エッジノード１０４は、それが終端するリンク２１０で輻輳を検知すると、それの識別子を書き込んだ帯域制御要求パケットを他のエッジノード１０１〜１０３に送信する。するとこれを契機に他の各エッジノード１０１〜１０３のそれぞれからリンク２１０に流れるトラヒックに対して帯域制御が開始される。なお、各帯域制御における出力データ累積量は、エッジノード１０４がリンク２１０上で端末３０１に向かって転送できたデータパケットのデータ蓄積量で測る。
【００５６】
次に帯域制御の解除は、入力側となるエッジノード１０１〜１０３のそれぞれにおいて図９に示すトラヒックシェイパーでのバッファにおけるパケット廃棄が少なくなったときに行なう。こうして入力側で帯域制御の解除を判断できる理由は、帯域制御を行なうと、輻輳状態がリンク２１０から、入力側である各エッジノード１０１〜１０３のそれぞれに移行するからである。
【００５７】
なお、各帯域制御における入力側および出力側での動作は、第１の実施の形態と同じなのでここでは説明を省略する。
【００５８】
第３の実施の形態の変形例として、入力／出力トラヒック識別子には、ノードもしくはリンクを特定するものに加えて、トランスポートレイヤのプロトコルもしくはアプリケーションレイヤのプロトコルを識別するものを加える。これにより特定のプロトコルによるトラヒックが特定のリンクに集中して発生している輻輳状態を回復することが出来る。以下の説明は第１の実施の形態における第２の変形例と同じなので省略する。
【００５９】
本発明の第４の実施の形態は、第３の実施の形態において出力側がノード１ではなく端末３である場合である。このとき、各ノード１を経由して端末３に到着する大量のトラヒックを端末３が検出した場合、端末３側でノード１に制御パケットを用いて適切なフィードバックをかけることで、そうした大量のトラヒックの到着を制限することが出来る。図６では、ノード１０１〜１０３のそれぞれから端末３０４に転送されるトラヒックの流れを示しており、それぞれの流れに対して帯域制御をかける。その際、端末３０４において返送する制御パケットに書き込む出力データ累積量は、端末３０４が受信したデータ量ではなく実際に端末で処理もしくは蓄積可能なデータ量で測る。また、例えばノード１０１から端末３０４に転送されるトラヒックに実施される帯域制御における入力トラヒック識別子はノード１０１のIPアドレスで、出力トラヒック識別子は端末３０１のIPアドレスでそれぞれ与える。
【００６０】
以上の実施の形態では、帯域制御の入力側および出力側の組として、ノードとノード（第１の実施の形態）、端末と端末（第２の実施の形態）、ノードとリンク（第３の実施の形態）、ノードと端末（第４の実施の形態）について例示したが、本発明は入力側および出力側はネットワークの任意の構成要素とすることができる。すなわち、入力側および出力側がそれぞれノードであっても、端末であっても、リンクであってもよいし、入力側がノードで出力側がリンクまたは端末、入力側が端末で出力側がリンクまたはノード、入力側がリンクで出力側がノードまたは端末であってもよい。
【００６１】
【発明の効果】
第１の効果は、制御パケットが廃棄されても制御に悪影響を及ぼさないことである。その理由は、帯域制御の入力側が出力側に送信し、それに対して出力側が入力側に返信して、入力側で確実に受信できた制御パケットに含まれる情報に基づいてのみ、入力側で帯域制御を行なうからである。
【００６２】
第２の効果は、帯域制御を行っている入力側と出力側の間に流れるトラヒックの現在の経路がより伝搬遅延の大きな経路に変更されても制御に支障がでないことである。また入力側もしくは出力側で制御パケットを送信もしくは受信した時刻をはかる時計がずれていたとしても全く問題がないことである。その理由は、輻輳の検出もしくは輻輳緩和の検出に入力側と出力側の間で測ったパケット転送遅延を用いないからである。
【００６３】
第３の効果は、輻輳防止機構のないトランスポートプロトコルもしくはアプリケーションプロトコルに基づくトラヒックに対して、それらのプロトコルを輻輳制御対応に変更することなく、端末側で輻輳防止制御を行なうことが可能となる。その理由は、帯域制御の入力側および出力側を端末とし、帯域制御の対象となるトラヒックを端末だけではなく、さらにトランスポートレイヤプロトコルもしくはアプリケーションレイヤプロトコルによって限定するからである。
【００６４】
第４の効果は、特定個所にトラヒックが集中することで発生する輻輳の回復に対しても、輻輳制御機構がないプロトコルによるトラヒックによりネットワークに発生するかもしれない輻輳の防止と共通の帯域制御方法をもちいて対処でき、輻輳防止と輻輳回復とに別々の制御方法をとることでさらに余分に発生するコストをおさえることができることである。その理由は、作用でも説明したように、本発明による帯域制御は、輻輳状態から開始すれば輻輳回復制御となり、非輻輳状態から開始すれば輻輳防止制御となるという性質を有しているからである。
【００６５】
第５の効果は、端末側がそのトラヒックの発信源である端末を特定することなく、輻輳回復制御を実行することができることである。その理由は帯域制御の入力側をノード、出力側を端末とすることで、端末がノードに処理したデータ量に関する情報を制御パケットにのせて通知するからである。
【００６６】
第６の効果は、端末がネットワーク内の輻輳に反応して転送量を削減させないトラヒックが大量にネットワーク内に流入して引き起こされる輻輳を回避するための輻輳防止制御をネットワーク側で行なうことが可能となる。またこれにより、TCPトラヒックのように輻輳に反応するトラヒックがネットワークから締め出されることを網側で防ぐことができることである。その理由は、帯域制御の入力側および出力側をノードとし、帯域制御の対象となるトラヒックを、ノード間もしくはリンクだけではなく、さらに加えてトランスポートレイヤプロトコルもしくはアプリケーションレイヤプロトコルによって限定するからである。
【００６７】
第７の効果は、特定のプロトコルによるトラヒックが特定のリンクに集中して発生している輻輳状態を回復することが出来ることである。その理由は帯域制御の入力側をノード、出力側を輻輳状態にあるリンクとし、帯域制御の対象となるトラヒックをノード間もしくはリンクだけではなく、さらに加えてトランスポートレイヤプロトコルもしくはアプリケーションレイヤプロトコルによって限定するからである。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態における入力側での動作を示すフローチャート（図１(A)）および本発明の第１の実施の形態における出力側での動作を示すフローチャート（図１(B)）である。
【図２】本発明の第１および第２の実施の形態の前提となるネットワークの物理構成を示す図である。
【図３】本発明の第１の実施の形態において帯域制御の対象となるトラヒックの流れを示す図である。
【図４】本発明の第２の実施の形態において帯域制御の対象となるトラヒックの流れを示す図である。
【図５】本発明の第３の実施の形態において帯域制御の対象となるトラヒックの流れを示す図である。
【図６】本発明の第４の実施の形態において帯域制御の対象となるトラヒックの流れを示す図である。
【図７】本発明における入力側と出力側でのパケットのやり取りを示すための図である。
【図８】入力レートに対する出力レートの関係を示す図である。
【図９】トークンバケットシェイパーのメカニズムを説明するためのブロック図である。
【符号の説明】
１ ノード
２ リンク
３ 端末
【図１】
0003862003.tif 000002
【図２】
0003862003.tif 000003
【図３】
0003862003.tif 000004
【図４】
0003862003.tif 000005
【図５】
0003862003.tif 000006
【図６】
0003862003.tif 000007
【図７】
0003862003.tif 000008
【図８】
0003862003.tif 000009
【図９】
0003862003.tif 000010