JP3783628B2

JP3783628B2 - 通信システムにおけるノード装置及びその動作制御方法

Info

Publication number: JP3783628B2
Application number: JP2002020840A
Authority: JP
Inventors: 英之下西
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 2002-01-30
Filing date: 2002-01-30
Publication date: 2006-06-07
Anticipated expiration: 2022-01-30
Also published as: JP2003224597A

Description

【０００１】
【発明の属する技術分野】
本発明は通信システムにおけるノード装置及びその動作制御方法に関し、特に広帯域網において、複数のフローあるいはコネクションをその属性に基づいて適切な品質クラスへと分類し、各クラス毎に定義されたサービス規律に従ってパケットを出力するルータあるいはスイッチ等のノード装置、特にＩＥＴＦによって定義されたDifferenciated Serviceに適合するルータに関する。
【０００２】
なお、以下本明細書においては、簡単化のために、”ルータあるいはスイッチ”を単に”ノード装置”と示し、”フローあるいはコネクション”を単に”フロー”と示し、”パケット及びセル”を単に”パケット”と示すものとする。
【０００３】
【従来の技術】
ノード装置において、クラス間の差別化、クラスの内での公平性制御及びフロー毎の帯域保証を実現するパケット出力の制御方式としては、一般的に、各フロー毎に制御を行う第一の方式と、各フローが属するクラス毎に制御を行う第二の方式とがある。
【０００４】
第一の方式では、個々のフローに対して品質制御を行うことにより、個々のフローに対して帯域保証を行うことが可能であり、また余剰帯域をフロー間で公平に分配することも可能である。本方式の一例としては、各フローに対して独立なキューを用意し、それぞれに最低保証帯域の相当する帯域資源を割り当て、M. Katavenis他, "Weighted round-robin cell multiplexing an a general-purpose ATM switch chip", IEEE Journals on Salectec Areas in Communication, Col.9, No.8, 1991やM. Shreedher他, "Efficient fair queueing using deficit round-robin", IEEE/ACM Transactions on Networking, vol.4, no.3, pp.375-385, 1996 等のwork-conserving なスケジューリングアルゴリズムを用いてパケット出力を行う方式があり、最低帯域の保証と余剰帯域の公平な分配が可能である。
【０００５】
また、別の一例としては、特開平１１−２１５１４２号公報において、各ＡＴＭコネクションに対して独立なキューを用意し、それぞれに最低帯域を保証した上で、任意の比率で余剰帯域を割り当てることが可能なスケジューリング方式が示されている。
【０００６】
第二の方式は、ノード装置において各フローが属するクラス毎に制御を行う方式であり、フロー毎の制御を行わないため多くのフローを収容する大規模なノード装置にも適用可能である。本方式では、網の入り口において各フローに対する保証帯域での流入制限を行い、ノード装置では各クラス内の全フローの保証帯域の合計に相当する資源を各クラスに割り当てることで、各フローに対する帯域保証が可能である。本方式の一例としては、各クラス毎にキューを用意し、それぞれのクラスに対して保証帯域の合計に相当する帯域資源を割り当て、前出のWeighted Round-Robinスケジューリングを用いてパケット出力を行う方式がある。
【０００７】
また別の一例としては、特開平１０−６５７０９号公報において、上位クラスのパケットを優先して出力し、順に下位クラスへと移行し、上位クラスのセル送出スケジュールに余裕があればそのセル間に下位クラスのセルを挿入するスケジューラを用いる方式が示されている。
【０００８】
第三の方式は、第二の方式の拡張であり、網の入り口で各パケットに対して廃棄優先度を設定し、各ノード装置においてクラス毎のキューに入力するときにパケットの廃棄優先度とその時点のキュー長からパケットの廃棄を決定する方式である。本方式では、網の入り口において保証帯域に相当する割合のパケットは低廃棄優先と設定し、それ以上のパケットは高廃棄優先と設定することにより、各フローに対して帯域を保証すると同時に、網の状態によっては保証帯域以上のパケットを送信することが可能である。本方式の一例としては、IETF (Internet Engineering Task Force)によって定義されたDifferenciated Services(文献IETF
RFC-2475)がある。
【０００９】
第四の方式は、各ノード装置において、各クラス毎に収容しているフロー数を計測し、計測されたフロー数の比に従って動的に各クラスに帯域を割り当てる方式である。特開平9-149035に示されている方式では、各サービスクラス毎に現在送信中のコネクションの本数を計測し、各バッファからのサービス比率を前記本数に比例させることで、それぞれのサービスクラス内の各コネクションを平等にサービスする。
【００１０】
【発明が解決しようとする課題】
第一の問題点は、前記第一の方式が広帯域網において大規模なルータへの適用が難しい点である。この第一の方式においては収容するフロー数に比例した数の状態を管理する必要があるが、高速動作が要求されるノード装置においては多数の状態を管理することはできない。
【００１１】
第二の問題点は、前記第二の方式では余剰帯域の分配が不可能であり、帯域を有効に利用できない点である。すなわち、各フローは保証帯域で流入制限が行われているため、網内の帯域資源に余裕がある場合でも保証帯域以上での送信ができない。
【００１２】
第三の問題点は、前記第三の方式において、各フローに与えられる品質が網の状態に動的に追従できないことである。すなわち、常に固定数のフローが固定した帯域で通信を行っているのではなく、網の状態が動的に変化している場合、本方式において固定的に各クラスに帯域を割り当てれば、特定のクラスにおいて一時的に入力パケットが少ない場合、このクラスのフローはより上位クラスのフローよりも高い品質を得ることが可能となる。特に、網の状態が予測が困難である場合、各クラス間に有意な品質差を設ける事ができるようにノード装置において帯域割り当てを行うことは非常に困難である。
【００１３】
第四の問題点は、前記第三の方式において、余剰帯域を公平に分配できないことである。第一の方式では余剰帯域は保証帯域比で分配されるが、本方式ではより多くのパケットを送信しているフローがより多くの余剰帯域を得る。
【００１４】
第五の問題点は、前記第四の方式において、各クラス毎に収容フロー数の計測を行う必要があり、そのためには各フロー毎に状態を管理する必要がある点である。そのため、本方式は多数のフローを収容する大規模なノード装置への適用が難しい。
【００１５】
第六の問題点は、前記第四の方式において、フロー毎の帯域保証が出来ない点である。本方式では、各フローへの保証帯域に係わり無くフロー数のみで帯域割り当てを行うため、平均的な帯域よりも大きな保証帯域が必要なフローにおいては、保証帯域を満足させることが不可能である。
【００１６】
本発明は以上の問題点を鑑み発案されたものであり、その目的とするところは、大規模なルータに適用可能なクラス毎の制御方式でありながら、クラス間の差別化、クラスの内での公平性制御及びフロー毎の帯域保証が可能なノード装置及びその動作制御方法を提供することにある。
【００１７】
【課題を解決するための手段】
本発明によるノード装置は、入力パケットをその属性情報に基づいて複数のキューのいずれかに格納し、各キュー内の各フローの送信状況から各キューに割り当てる帯域を動的に変更し、前記キューから割り当てられた帯域に従ってパケットを出力回線に出力するノード装置であって、前記各キューが、扱っているフローのうち一部のフローについてその送信帯域等の情報を記憶する手段と、該キューへの入力パケットに対してその所属フローが前記記憶手段で管理されている場合には前記記憶手段の内容を更新する手段と、前記記憶手段の内容から該キューで現在送信中のフロー数を推定する手段とを、それぞれ有し、前記各キュー毎に推定したフロー数に従って、各キューに割り当てる帯域を決定する手段とを含むことを特徴とする。
【００１８】
本発明による他のノード装置は、入力パケットをその属性情報に基づいて複数のキューのいずれかに格納し、各キュー内の各フローの送信状況から各キューに割り当てる帯域を動的に変更し、割り当てられた帯域に従って前記キューからのパケットの廃棄制御を行うノード装置であって、前記各キューが、扱っているフローのうち一部のフローについてその送信帯域等の情報を記憶する手段と、該キューへの入力パケットに対してその所属フローが前記記憶手段で管理されている場合には前記記憶手段の内容を更新する手段と、前記記憶手段の内容から該キューで現在送信中のフロー数を推定する手段とを、それぞれ有し、前記各キュー毎に推定したフロー数に従って、各キューに割り当てる帯域を決定する手段とを含むことを特徴とする。
【００１９】
本発明による更に他のノード装置は、入力パケットをその属性情報に基づいて複数のキューのいずれかに格納し、前記キューからスケジューラを用いてパケットを出力回線に出力するノード装置であって、前記入力パケットが属するサービスクラスによって格納するキューを決定するパケット振り分け部と、各サービスクラス毎に各フローの送信状況から帯域を割り当てるべきフローの本数を推定するフロー数推定部と、各サービスクラス毎のキューと、各サービスクラス内の推定フロー数とに基づいて、各サービスクラスに割り当てる帯域を動的に変更する帯域割り当て制御部と、各サービスクラスに割り当てられた帯域をもとに各キューからのパケット出力を制御するスケジューラとを含み、前記フロー数推定部が、該キューにて扱っているフローのうち一部のフローについてその送信帯域等の情報を記憶する手段と、該キューへの入力パケットに対してその所属フローが前記記憶手段で管理されている場合には前記記憶手段の内容を更新する手段と、前記記憶手段で管理されているフローを適宜入れ替える手段と、前記記憶手段で管理されているキューの送信帯域等の情報から前記記憶手段で管理されていないフローを含む前記キューで扱っている全てのフローの数を推定する手段とを有することを特徴とする。
【００２０】
本発明による別のノード装置は、入力パケットをその属性情報に基づいて複数のキューのいずれかに格納し、前記キューからスケジューラを用いてパケットを出力回線に出力するノード装置であって、前記入力パケットが属するサービスクラスによって格納するキューを決定するパケット振り分け部と、各サービスクラス毎に各フローの送信状況から帯域を割り当てるべきフローの本数を推定するフロー数推定部と、各サービスクラス毎のキューと、各サービスクラス内の推定フロー数とに基づいて、各サービスクラスに割り当てる帯域を動的に変更する帯域割り当て制御部と、各サービスクラスに割り当てられた帯域に従って各キューに入力するパケットの廃棄制御を行うシェイパと、各キューからのパケット出力を制御するスケジューラとを有し、前記フロー数推定部が、該キューにて扱っているフローのうち一部のフローについてその送信帯域等の情報を記憶する手段と、該キューへの入力パケットに対してその所属フローが前記記憶手段で管理されている場合には前記記憶手段の内容を更新する手段と、前記記憶手段で管理されているフローを適宜入れ替える手段と、前記記憶手段で管理されているキューの送信帯域等の情報から前記記憶手段で管理されていないフローを含む前記キューで扱っている全てのフローの数を推定する手段とを有することを特徴とする。
【００２１】
本発明によるノード装置の動作制御方法は、入力パケットをその属性情報に基づいて複数のキューのいずれかに格納し、各キュー内の各フローの送信状況から各キューに割り当てる帯域を動的に変更し、前記キューから割り当てられた帯域に従ってパケットを出力回線に出力するノード装置の動作制御方法であって、前記各キュー毎に扱っているフローのうち一部のフローについてその送信帯域等の情報を記憶手段へ記憶するステップと、該キューへの入力パケットに対してその所属フローが前記記憶手段で管理されている場合には前記記憶手段の内容を更新するステップと、前記記憶手段の内容から該キューで現在送信中のフロー数を推定するステップとを含むことを特徴とする。
【００２２】
本発明による他のノード装置の動作制御方法は、入力パケットをその属性情報に基づいて複数のキューのいずれかに格納し、各キュー内の各フローの送信状況から各キューに割り当てる帯域を動的に変更し、割り当てられた帯域に従って前記キューからのパケットの廃棄制御を行うノード装置の動作制御方法であって、各キュー内の一部のフローの状態を記憶手段に記憶するステップと、各キュー毎に扱っているフローのうち一部のフローについてその送信帯域等の情報を前記記憶手段に記憶するステップと、該キューへの入力パケットに対してその所属フローが前記記憶手段で管理されている場合には前記記憶手段の内容を更新するステップと、前記記憶手段の内容から該キューで現在送信中のフロー数を推定するステップとを含むことを特徴とする。
【００２３】
本発明による更に他のノード装置の動作制御方法は、入力パケットをその属性情報に基づいて複数のキューのいずれかに格納し、前記キューからスケジューラを用いてパケットを出力回線に出力するノード装置の動作制御方法であって、前記入力パケットが属するサービスクラスによって格納するキューを決定するパケット振り分けステップと、各サービスクラス毎に各フローの送信状況から帯域を割り当てるべきフローの本数を推定するフロー数推定ステップと、各サービスクラス毎のキューと、各サービスクラス内の推定フロー数とに基づいて、各サービスクラスに割り当てる帯域を動的に変更する帯域割り当て制御ステップと、各サービスクラスに割り当てられた帯域をもとに各キューからのパケット出力を制御するステップとを含み、前記フロー数推定ステップが、該キューにて扱っているフローのうち一部のフローについてその送信帯域等の情報を記憶手段に記憶するステップと、該キューへの入力パケットに対してその所属フローが前記記憶手段で管理されている場合には前記記憶手段の内容を更新するステップと、前記記憶手段で管理されているフローを適宜入れ替えるステップと、前記記憶手段で管理されているキューの送信帯域等の情報から前記記憶手段で管理されていないフローを含む前記キューで扱っている全てのフローの数を推定するステップとを有することを特徴とする。
【００２４】
本発明による更に他のノード装置の動作制御方法は、入力パケットをその属性情報に基づいて複数のキューのいずれかに格納し、前記キューからスケジューラを用いてパケットを出力回線に出力するノード装置の動作制御方法であって、前記入力パケットが属するサービスクラスによって格納するキューを決定するパケット振り分けステップと、各サービスクラス毎に各フローの送信状況から帯域を割り当てるべきフローの本数を推定するフロー数推定ステップと、各サービスクラス毎のキューと、各サービスクラス内の推定フロー数とに基づいて、各サービスクラスに割り当てる帯域を動的に変更する帯域割り当て制御ステップと、各サービスクラスに割り当てられた帯域に従って各キューに入力するパケットの廃棄制御を行うステップと、各キューからのパケット出力を制御するステップとを有し、前記フロー数推定ステップが、該キューにて扱っているフローのうち一部のフローについてその送信帯域等の情報を記憶手段に記憶するステップと、該キューへの入力パケットに対してその所属フローが前記記憶手段で管理されている場合には前記記憶手段の内容を更新するステップと、前記記憶手段で管理されているフローを適宜入れ替えるステップと、前記記憶手段で管理されているキューの送信帯域等の情報から前記記憶手段で管理されていないフローを含む前記キューで扱っている全てのフローの数を推定するステップとを有することを特徴とする。
【００２５】
更に述べれば、第一の問題点及び第五の問題点を解決するため、本発明によるノード装置では、フロー毎の制御は行わず、フローを集約した単位、すなわちクラス単位での制御を行う。クラス内のフロー数を計測する際も、、各クラス内の正確なフロー数を計測するのではなく、特願２００１−１４６０２８号明細書に開示された方式を用いて各クラス内のフロー数を簡易に推定する。
【００２６】
第二の問題点を解決するため、本発明によるノード装置では、第三の方式と同様に網の入り口で各パケットに対して廃棄優先度を設定し、前記廃棄優先度に基づいてノード装置におけるパケットの廃棄制御を行う。そのため、保証帯域以上のパケットを低優先に設定することにより、同クラス内の他のフローの帯域保証に影響を与えることなく、保証帯域以上のパケットを送出可能である。
【００２７】
第三の問題点を解決するため、本発明によるノード装置では、各クラスに入力されるトラヒックを観測し、各クラス内で現に送信を行っているフローに対してのみ帯域が割り当てられるように動的に各クラスの割り当て帯域を変更する。本発明では低廃棄優先度に設定されているパケットを計測し、前記パケット数を元に現に送信を行っているフローの保証帯域の合計を算出する。従って、保証帯域以下で送信しているフローに関しては、いかなるクラスにおいても保証帯域が満たされるように各クラスに対して帯域割り当てがなさせる。そして前記帯域割り当て後に余剰帯域がある場合には、各クラス内で現に送信を行っているフロー数を推定し、前記推定フロー数及び各クラスの優先度に従って余剰帯域を各クラスに割り当てる。そのため、本発明においては、各クラスにおいて送信を行っているフロー数が動的に変化する状況においても、常にクラス間の品質差別化が可能であり、上下のクラス間での品質の逆転が発生しない。
【００２８】
第四の問題点を解決するため、本発明によるノード装置では、各クラスに入力されるトラヒックを観測し、同一クラス内で他のフローよりも多く余剰帯域を使用しているフローを識別して、該フローからは高い確率でパケット廃棄を行う。すなわち、保証帯域以上で送信されている高廃棄優先のパケットの個数をフロー毎に比較し、他のフローよりも多く高廃棄優先のパケットを送信しているフローに対しては、高廃棄優先のパケットをさらに高い廃棄優先度へと変更する。そのため、同一クラス内で多く余剰帯域を使用しているフローからは多くパケットが廃棄され、同一クラス内のフロー間の公平性が向上する。
【００２９】
第六の問題点を解決するため、本発明によるノード装置では、各クラス内のフロー数のみで帯域を割り当てるのではなく、前記の通り、まず各クラスに対して保証帯域の合計に相当する帯域を割り当て、余剰帯域が生じた場合のみ余剰帯域を各クラス内のフロー数及び各クラスの優先度を元に帯域割り当てを行う。
【００３０】
【発明の実施の形態】
以下に図面を参照しつつ本発明の実施例につき詳述する。図１は本発明によるノード装置の第一の実施例の構成を示すブロック図である。本実施例において、ノード装置１００は、到着したパケットが属するサービスクラスを判定するパケット振り分け部１０１と、クラス毎に現に送信を行っている全フローの保証帯域の合計を計測するｎ個の保証帯域計測部１０２と、クラス毎に現に送信を行っているフロー数を推定するｎ個のフロー数推定部１０３と、各クラス毎にパケットを格納するｎ個のクラスキュー１０４と、帯域割り当て制御部１０６の情報をもとに各クラスのキューからのパケット出力を制御するスケジューラ１０５と、各クラスの保証帯域合計及び推定フロー数を元に各クラスに割り当てる帯域を計算する帯域割り当て制御部１０６とにより構成される。
【００３１】
パケット振り分け部１０１は入力パケットが属する品質クラスを調べ、パケットを格納すべきキューを選択する。ルータやイーサスイッチを例に説明すると、送信元ＭＡＣ（Media Access Control）アドレス、送信先ＭＡＣアドレス、IEEE 802.1p 優先度、ＶＬＡＮ−ＩＤ、送信元ＩＰ（Internet Protocol ）アドレス、送信先ＩＰアドレス、第四層プロトコル番号、送信元ポート番号、送信先ポート番号、ＴＯＳ（Type of service)情報等を用いて品質クラスを決定する。
【００３２】
保証帯域計測部１０２は対応するクラスにおいて現に送信を行っているフローの保証帯域の合計を計測する。保証帯域計測部１０２では到着したパケットの廃棄優先度を調べ、低廃棄優先で送信されているパケットを保証帯域内のパケットであると判断し、低廃棄優先度のパケットの到着率を保証帯域の合計とする。
【００３３】
フロー数推定部１０３は対応するクラスにおいて現に送信を行っているフローの数を推定する。また、フロー数推定部１０３では、到着パケットが高廃棄優先であり、到着パケットが属するフローが同一クラス内の他のフローよりも余剰帯域を多く使用している場合、到着パケットをさらに高い廃棄優先度とする。
【００３４】
図２は本実施例におけるフロー数推定部１０３の構成を示すブロック図である。フロー数推定部１０３は、フロー識別子と到着パケット数と高廃棄優先パケット数をエントリとして持つ到着フロー履歴１０７と、到着パケットが属するフローが該履歴に存在する確率を導出する一致確率導出部１０８と、到着パケットが属するクラスの全フローの平均帯域を導出する推定平均帯域導出部１０９と、推定フロー数を計算するフロー数計算部１１０と、該クラスへのパケット到着率を計測する入力トラヒック計測部１１１と、入力パケットの廃棄優先度を変更する優先度変更部１１２とにより構成される。
【００３５】
フロー識別子は到着パケットが属するフローを一意に識別するための識別子であり、”ＩＰｖｅｒｓｉｏｎ４”を例に説明すると、フローの識別子とは送信元ＩＰアドレス、送信先ＩＰアドレス、第四層プロトコル番号、送信元ポート番号、送信先ボート番号から生成される識別子である。到着パケット数は該エントリに新たなフローが登録されてからの該フローの入力パケット数の合計であり、高廃棄優先パケット数は前記到着パケット数のうち高廃棄優先に設定されているパケット数である。
【００３６】
到着フロー履歴１０７は、該クラスに属する全てのフローに対するエントリを持つのではなく一部のフローについてのみエントリを持ち、該履歴に登録されるフローは該履歴に登録されていないフローからのパケット入力を契機として適宜入れ替えられる。すなわち、フロー数推定部１０３では、全フローの状態を用いてフロー数を推定するのではなく、遠くない過去にパケットが到着した１または複数のフローの状態を用いてフロー数の推定を行う。図３はフロー数推定部の動作を示すフローチャートである。
【００３７】
クラスキュー１０４は各クラス毎に設けられたキューであり、現在のキュー長と到着パケットの廃棄優先度を元に、到着パケットを廃棄する機能も持つ。スケジューラ１０５は割り当て帯域制御部１０６で計算された各クラスへの割り当て帯域に従って、各クラスキューからパケットの出力を行う。スケジューラ１０５は、出力回線に余剰帯域がある場合にはこの余剰帯域を各キューに対して公平に分配する機構を備えている必要があり、このようなスケジューリングアルゴリズムとしては、前記のＷＲＲやＤＲＲ等が挙げられる。
【００３８】
割り当て帯域制御部１０６は保証帯域計測部１０２及びフロー数推定部１０３で計測された保証帯域及びフロー数から各クラスへの割り当て帯域を計算する。図４は割り当て帯域制御部の動作を示すフローチャートである。
【００３９】
次に、図１から図４を参照して本実施例の動作を説明する。まず最初に、パケット入力時の動作を説明する。本実施例によるノード装置にパケットが到着すると、まず入力パケットが属するクラスを判定する。そして、該クラスに対応する保証帯域計測部において、該クラスに到着する全フローの保証帯域合計、すなわち該クラスへの低廃棄優先パケットの到着率を求める。これは、例えば単位時間あたりの低廃棄優先パケットの到着数を求めれば良い。
【００４０】
次に、該クラスに対応するフロー数推定部において、該クラス内で現に送信を行っているフロー数を以下の様に推定する。フロー数推定部では到着フロー履歴を参照し、入力パケットと同じフロー識別子を持つエントリを探す（ステップＳ１）。一致確率導出部は前記参照において一致するエントリが存在する確率の時間平均を保持しており、前記参照の結果から一致確率を更新する（ステップＳ３，４）。そして、もし前記参照において一致するエントリが見つかれば（ステップＳ２でＹ）、該エントリの到着パケット数に１を加え（ステップＳ５）、もし到着パケットの廃棄優先度が高廃棄優先であれば（ステップＳ６でＹ）、高廃棄優先パケット数に１を加える（ステップＳ７）。
【００４１】
ステップＳ２の参照において一致するエントリが発見されなければ（ステップＳ２でＮ）、到着フロー履歴からランダムに１つのエントリを選択し（ステップＳ８）、任意の確率ｑによって該エントリを置き換える。エントリの置き換えの際には、到着パケット数及び高廃棄優先パケット数を１に初期化する（ステップＳ１５）。
【００４２】
優先度変更部では、ステップＳ２の参照において一致するエントリが見つかり（ステップＳ２でＹ）、到着パケットが高廃棄優先であり（ステップＳ６でＹ）、かつ前記高廃棄優先パケット数が同一クラス内の全てのフローの高廃棄優先パケット数の平均よりも大きければ（ステップＳ１０でＹ）、到着パケットを最高廃棄優先度に変更する（ステップＳ１１）。
【００４３】
推定平均帯域導出部では、エントリ置き換えの直前に、置き換えられる前のフローに関してその推定帯域を計算し、これに基づいて同一クラス内の全てのフローの推定帯域の平均を求める。推定帯域は、例えば「推定帯域＝（１−一致確率）＊ｑ／エントリ数＊到着パケット数」の様な式で計算できる。そして、得られた推定帯域から、該クラスへ到着する全フローの帯域の平均を求める。ここでは、帯域の低いフローでは他のフローに比べて帯域推定の回数が少ないため重み付けを行い、「推定平均帯域＝（１−α＊到着パケット数／推定帯域）＊前回の推定平均帯域＋α＊到着パケット数／帯域＊推定帯域」のように推定平均帯域を計算する（ステップＳ１２，１３）。
【００４４】
フロー数計算部では、推定平均帯域導出部で求めた推定平均帯域と、入力トラヒック計測部で求めた該クラスへのパケット到着率から、該クラス内で現に送信を行っているフロー数を推定する。ここで推定フロー数は、パケット到着率を推定平均帯域で割ったものである（ステップＳ１４）。以上の式の由来は、牧一進他、「高速バックボーンネットワークにおける公平性を考慮した階層化パケットスケジューリング方式」、電子情報通信学会技術研究報告、ＮＳ０１−０６，２００１に示されている。
【００４５】
該クラスで現に送信を行っているフロー数が到着フロー履歴のエントリ数よりも少ない場合、到着フロー履歴のエントリ置き換えが発生せず、一致確率が１となる。この場合、上記の方式では推定帯域が計算できない。そこで一致確率がある１に近い定数β（β＜１）を超えた場合には（ステップＳ１６でＹ）、「推定帯域＝該エントリの到着パケット数／該クラスの全エントリの到着パケット数合計」として推定帯域を求める（ステップＳ１７，１８）。そして、ステップＳ１４と同様に推定フロー数を求める（ステップＳ１９）。
【００４６】
フロー数推定が終了すると、次に、到着パケットを該クラスに対応するキューへと格納する。この際、該キューのキュー長及び到着パケットの廃棄優先度より、到着パケットの廃棄判断を行い、廃棄と決定した場合には到着パケットを該キューに格納せずに廃棄する。各キューに設定された各廃棄優先度毎の廃棄閾値は、前記保証帯域及び推定フロー数に従って動的に変更する。例えば廃棄閾値を保証帯域にある定数を乗じた値と、推定フロー数に別の定数を乗じた値の合計に設定する。
【００４７】
各キューに格納されたパケットは、各クラスに設定された帯域に従ってスケジューラによって読み出され、出力回線に出力される。
【００４８】
次に、割り当て帯域制御部での各クラスに対する割り当て帯域の計算動作を説明する。まず全クラスの保証帯域の合計（保証帯域合計）及び推定フロー数の合計（全推定フロー数）を求める（ステップＳ２１，２２）。各クラスの推定フロー数に関しては、該クラスに与えられたウエイトに従ってある定数を乗じる。これは上位クラスに対して多くの余剰帯域を割り当てるため、上位クラスでは実際のフロー数よりも多くのフローが存在することとして余剰帯域を多く配分するためである。
【００４９】
そして、回線容量から全保証帯域を引いたものを余剰帯域とし、これを全推定フロー数で割って、フローあたりの単位余剰帯域を求める（ステップＳ２３）。最後に、各クラスに対してそれぞれの保証帯域を割り当て、さらに単位余剰帯域と推定フロー数と該クラスに対するウエイトと定数γの積を割り当てる（ステップＳ２４）。定数γは、０≦γ＜≦１であり、γ=０の場合は余剰帯域はフロー数に関係なくスケジューラの動作によって保証帯域の比率での割り当てとなり、γ＝１の場合は余剰帯域は保証帯域に関係無く各フロー均等な割り当てとなり、０＜γ＜１の場合はこれらの中間的な割り当てとなる。
【００５０】
図５は本発明によるノード装置の第二の実施例の構成を示すブロック図である。本実施例において、ノード装置２００は、第一の実施例の構成に加えて、ｎ個のフロー数推定部２０３の後段にｎ個のシェイパ２０７を有する構成である。シェイパ２０７は割り当て帯域計算部２０６によって計算された各クラスへの割り当て帯域に従って、本シェイパを通過するパケットの廃棄制御を行う。本シェイパでは各クラスへの割り当て帯域以内のパケットはクラスキュー２０４に格納し、割り当て帯域を越えるパケットは廃棄する。本シェイパでは、廃棄優先度の高いパケットが多く廃棄されるように廃棄制御を行う。
【００５１】
本実施例においては、スケジューラ２０６では割り当て帯域によるスケジューリングは行わず、高いクラスのパケットは常に優先して出力するスケジューリング動作を行う。
【００５２】
次に、図５を参照して本実施例の動作を説明する。本実施例においても、パケットが到着してからフロー数推定までの動作は、第一の実施例と同様である。フロー数の推定後、シェイパによって廃棄制御を行う。シェイパでは、前到着パケットの仮想的な出力終了時刻が「現在時刻＋閾値」を越えていれば、到着パケットを廃棄する。ここで、廃棄優先度の高いパケットに対しては小さな閾値を用いることにより、廃棄優先度の高いパケットが多く廃棄されるように制御することが可能である。
【００５３】
パケットの廃棄が行わなければ、到着パケットをクラスキューに格納し、「出力終了時刻＝ｍａｘ（現在時刻、前回計算の出力終了時刻）＋到着パケット長／割り当て帯域」として、到着パケットの仮想的な出力終了時刻を更新する。そして、各キューに格納されたパケットは、高い優先度のクラスから順番にスケジューラによって読み出され、出力回線に出力される。本実施例における割り当て帯域の計算方式は、第一の実施例と同様である。
【００５４】
図６は本発明によるノード装置の第三の実施例の構成を示すブロック図である。本実施例においてノード装置３００は、第一の実施例の構成と基本的な構成は同様であり、ｍ個（ｍは２以上の整数）の保証帯域計測部３０２、ｍ個のフロー数推定部３０３、ｍ個のキュー３０４をクラス毎に１つ持つのではなく、クラス毎に複数持つことが異なる。
【００５５】
また、本実施例においては、パケット振り分け部３０１はクラスよりも細かな粒度でパケットの振り分けを行い、帯域割り当て制御部３０６ではクラス単位でなくキュー単位で割り当て帯域を計算する。
【００５６】
次に、図６を参照して本実施例の動作を説明する。本実施例によるノード装置にパケットが到着すると、まず入力パケットが属するクラスを判定した後、クラス内のいずれのキューに格納するかを決定する必要がある。ここでは、同一フローに属するパケットが同一キューに格納されればよく、例えば、フロー識別子から生成される一意なハッシュ値を用いてキューを決定すれば良い。
【００５７】
パケットを格納して以降の処理に関しては、本実施例の動作は第一の実施例の動作と同様であり、クラス毎に処理を行うのではなく、キュー毎に処理を行う点が異なるのみである。そのため以降の処理の説明は省略する。
【００５８】
本実施例においては、１つのキューに収容するフロー数が第一の実施例に比べて少なくなるため、フロー数推定の精度が向上し、また多くの余剰帯域を使用しているフローを発見できる確率も高くなると期待できる。
【００５９】
図７は本発明によるノード装置の第四の実施例の構成を示すブロック図である。本実施例においてノード装置４００は、到着したパケットが属するクラスを判定するパケット振り分け部４０１と、クラス毎に現に送信を行っているフロー数を推定するｎ個のフロー数推定部４０３と、各クラス毎にパケットを格納するｎ個のクラスキュー４０４と、帯域割り当て制御部４０６の情報をもとに各クラスのキューからのパケット出力を制御するスケジューラ４０５と、各クラスの推定フロー数を元に各クラスに割り当てる帯域を計算する帯域割り当て制御部４０６とにより構成される。これは第一の実施例におけるノード装置１００から保証帯域計測部１０２を除いた構成である。
【００６０】
フロー数推定部４０３は対応するクラスにおいて現に送信を行っているフローの数を推定する。また、フロー数推定部４０３では、到着パケットが属するフローが同一クラス内の他のフローよりも帯域を多く使用している場合、到着パケットを高い廃棄優先度とする。
【００６１】
図８は本実施例におけるフロー数推定部４０３の構成を示すブロック図である。フロー数推定部４０３は、フロー識別子と到着パケット数をエントリとして持つ到着フロー履歴４０７と、到着パケットが属するフローが該履歴に存在する確率を導出する一致確率導出部４０８と、到着パケットが属するクラスの全フローの平均帯域を導出する推定平均帯域導出部４０９と、推定フロー数を計算するフロー数計算部４１０と、該クラスへのパケット到着率を計測する入力トラヒック計測部４１１と、入力パケットの廃棄優先度を変更する優先度変更部４１２とにより構成される。図９はフロー数推定部の動作を示すフローチャートであり、図３のステップと同等ステップは同一符号にて示している。
【００６２】
割り当て帯域制御部４０６はフロー数推定部４０３で計測されたフロー数から各クラスへの割り当て帯域を計算する。図１０は割り当て帯域制御部の動作を示すフローチャートである。パケット振り分け部４０１及びクラスキュー４０４、スケジューラ４０５の構成及び動作は第一の実施例と同様である。
【００６３】
次に、図７から図１０を参照して本実施例の動作を説明する。まず最初に、パケット入力時の動作を説明する。本実施例によるノード装置にパケットが到着すると、まず入力パケットが属するクラスを判定する。そして、該クラスに対応するフロー数推定部において、該クラス内で現に送信を行っているフロー数を図９の様に推定する。本動作は、高廃棄優先パケットのみを対象に廃棄優先度の変更処理を行うのではなく（図３のステップＳ６，Ｓ７，Ｓ１０の処理をなくして）、全ての到着パケットを対象として廃棄優先度の変更処理を行う点（ステップＳ３１）を除いて、第一の実施例におけるフロー数推定動作と同様である。
【００６４】
フロー数推定が終了すると、次に、到着パケットを該クラスに対応するキューへと格納する。この際、該キューのキュー長及び到着パケットの廃棄優先度より、到着パケットの廃棄判断を行い、廃棄と決定した場合には到着パケットを該キューに格納せずに廃棄する。そして、各キューに格納されたパケットは、各クラスに設定された帯域に従ってスケジューラによって読み出され、出力回線に出力される。
【００６５】
次に、割り当て帯域制御部での各クラスに対する割り当て帯域の計算動作を説明する。まず全クラスの推定フロー数の合計（全推定フロー数）を求める（ステップＳ４１）。各クラスの推定フロー数に関しては、該クラスに与えられたウエイトに従ってある定数を乗じる。これは上位クラスに対して多くの余剰帯域を割り当てるため、上位クラスでは実際のフロー数よりも多くのフローが存在することとして余剰帯域を多く配分するためである。そして、回線容量を全推定フロー数で割って、フローあたりの単位割り当て帯域を求める（ステップＳ４２）。最後に、各クラスに対して単位割り当て帯域と推定フロー数と該クラスに対するウエイトの積を割り当てる（ステップＳ４３）。
【００６６】
図１１は本発明によるノード装置の第五の実施例の構成を示すブロック図である。本実施例においてノード装置５００は、第四の実施例におけるノード装置４００の構成に加えて、保証帯域保存部５０７を持つ。本実施例の動作は、帯域割り当て動作を除いて、第四の実施例と同様である。
【００６７】
本実施例における帯域割り当て制御部５０７の動作を図１２に示す。本実施例における帯域割り当て制御部の動作は、第一の実施例における帯域割り当て制御部の動作（図４のフロー）と同様であるが、保証帯域を動的に計測するのではなく、保証帯域保存部５０７に静的に設定された保証帯域の値を用いる点が異なる。
【００６８】
【発明の効果】
本発明の第一の効果は、クラス間の差別化、クラスの内での公平性制御、及びフロー毎の帯域保証を実現するノード装置において、フロー毎の制御を行うことなくパケットの出力制御を行うことができ、高速なノード装置に対して適用可能としたことである。
【００６９】
本発明の第二の効果は、前記ノード装置において、同クラス内の他のフローの帯域保証に影響を与えることなく、網の状況に応じて保証帯域以上の通信を可能としたことができることである。
【００７０】
本発明の第三の効果は、前記ノード装置において、各クラスで現に送信を行っているフロー数が動的に変化する状況においても、常にクラス間の品質差別化が可能であり、上下のクラス間で品質の逆転が発生しないことである。
【００７１】
本発明の第四の効果は、前記ノード装置において、同一クラス内で多く余剰帯域を使用しているフローからは多くパケットを廃棄し、同一クラス内のフロー間での公平性が向上することである。
【００７２】
本発明の第五の効果は、前記ノード装置において、各フロー毎の帯域保証と、余剰帯域の公平な分配の両立を実現できることである。
【図面の簡単な説明】
【図１】第一の実施例の構成を示すブロック図である。
【図２】第一の実施例におけるフロー数推定部の構成を示すブロック図である。
【図３】第一の実施例におけるフロー数推定部の動作を示すフローチャートである。
【図４】第一の実施例における帯域割り当て制御部の動作を示すフローチャートである。
【図５】第二の実施例の構成を示すブロック図である。
【図６】第三の実施例の構成を示すブロック図である。
【図７】第四の実施例の構成を示すブロック図である。
【図８】第四の実施例におけるフロー数推定部の構成を示すブロック図である。
【図９】第四の実施例におけるフロー数推定部の動作を示すフローチャートである。
【図１０】第四の実施例における帯域割り当て制御部の動作を示すフローチャートである。
【図１１】第五の実施例の構成を示すブロック図である。
【図１２】第五の実施例における帯域割り当て制御部の動作を示すフローチャートである。
【符号の説明】
１００，２００，３００，４００，５００ノード装置
１０１，２０１，３０１，４０１，５０１パケット振り分け部
１０２，２０２，３０２，４０２，３０２保証帯域計測部
１０３，２０３，３０３，４０３，５０３フロー数推定部
１０４，２０４，３０４，４０４，５０４キュー
１０５，２０５，３０５，４０５，５０５スケジューラ
１０６〜５０６，２０６，３０６，４０６帯域割り当て制御部
５０７保証帯域保存部
１０７，４０７到着フロー履歴
１０８，４０８一致確率導出部
１０９，４０９推定平均帯域導出部
１１０，４１０フロー数計算部
１１１，４１１入力トラヒック計測部
１１２，４１２優先度変更部

Claims

入力パケットをその属性情報に基づいて複数のキューのいずれかに格納し、各キュー内の各フローの送信状況から各キューに割り当てる帯域を動的に変更し、前記キューから割り当てられた帯域に従ってパケットを出力回線に出力するノード装置であって、
前記各キューが、
扱っているフローのうち一部のフローについてその送信帯域等の情報を記憶する手段と、該キューへの入力パケットに対してその所属フローが前記記憶手段で管理されている場合には前記記憶手段の内容を更新する手段と、前記記憶手段の内容から該キューで現在送信中のフロー数を推定する手段とを、それぞれ有し、
前記各キュー毎に推定したフロー数に従って、各キューに割り当てる帯域を決定する手段とを含むことを特徴とするノード装置。
入力パケットをその属性情報に基づいて複数のキューのいずれかに格納し、各キュー内の各フローの送信状況から各キューに割り当てる帯域を動的に変更し、割り当てられた帯域に従って前記キューからのパケットの廃棄制御を行うノード装置であって、
前記各キューが、扱っているフローのうち一部のフローについてその送信帯域等の情報を記憶する手段と、該キューへの入力パケットに対してその所属フローが前記記憶手段で管理されている場合には前記記憶手段の内容を更新する手段と、前記記憶手段の内容から該キューで現在送信中のフロー数を推定する手段とを、それぞれ有し、
前記各キュー毎に推定したフロー数に従って、各キューに割り当てる帯域を決定する手段とを含むことを特徴とするノード装置。
入力パケットをその属性情報に基づいて複数のキューのいずれかに格納し、前記キューからスケジューラを用いてパケットを出力回線に出力するノード装置であって、
前記入力パケットが属するサービスクラスによって格納するキューを決定するパケット振り分け部と、
各サービスクラス毎に各フローの送信状況から帯域を割り当てるべきフローの本数を推定するフロー数推定部と、
各サービスクラス毎のキューと、各サービスクラス内の推定フロー数とに基づいて、各サービスクラスに割り当てる帯域を動的に変更する帯域割り当て制御部と、
各サービスクラスに割り当てられた帯域をもとに各キューからのパケット出力を制御するスケジューラとを含み、
前記フロー数推定部が、該キューにて扱っているフローのうち一部のフローについてその送信帯域等の情報を記憶する手段と、該キューへの入力パケットに対してその所属フローが前記記憶手段で管理されている場合には前記記憶手段の内容を更新する手段と、前記記憶手段で管理されているフローを適宜入れ替える手段と、前記記憶手段で管理されているキューの送信帯域等の情報から前記記憶手段で管理されていないフローを含む前記キューで扱っている全てのフローの数を推定する手段とを有することを特徴とするノード装置。
入力パケットをその属性情報に基づいて複数のキューのいずれかに格納し、前記キューからスケジューラを用いてパケットを出力回線に出力するノード装置であって、
前記入力パケットが属するサービスクラスによって格納するキューを決定するパケット振り分け部と、
各サービスクラス毎に各フローの送信状況から帯域を割り当てるべきフローの本数を推定するフロー数推定部と、
各サービスクラス毎のキューと、各サービスクラス内の推定フロー数とに基づいて、各サービスクラスに割り当てる帯域を動的に変更する帯域割り当て制御部と、
各サービスクラスに割り当てられた帯域に従って各キューに入力するパケットの廃棄制御を行うシェイパと、
各キューからのパケット出力を制御するスケジューラとを有し、
前記フロー数推定部が、該キューにて扱っているフローのうち一部のフローについてその送信帯域等の情報を記憶する手段と、該キューへの入力パケットに対してその所属フローが前記記憶手段で管理されている場合には前記記憶手段の内容を更新する手段と、前記記憶手段で管理されているフローを適宜入れ替える手段と、前記記憶手段で管理されているキューの送信帯域等の情報から前記記憶手段で管理されていないフローを含む前記キューで扱っている全てのフローの数を推定する手段とを有することを特徴とするノード装置。
一部のフローに関してパケット到着率を推定し、これをもとに全フローのパケット到着率の平均を推定し、この平均到着率をもとにフロー数を推定することを特徴とする請求項１〜４いずれか記載のノード装置。
各サービスクラスに対して予め設定された保証帯域に相当する帯域を固定的に割り当て、残りの帯域を各サービスクラスに対して保証帯域及び推定フロー数に基づいて動的に割り当てることを特徴とする請求項１〜５いずれか記載のノード装置。
各サービスクラス毎に現に送信を行っているフローの保証帯域の合計を計測する保証帯域計測部を有し、各サービスクラスに対して前記保証帯域に相当する帯域を動的に割り当て、残りの帯域を各サービスクラスに対して保証帯域及び推定フロー数に基づいて動的に割り当てることを特徴とする請求項１〜５いずれか記載のノード装置。
廃棄優先度の低い到着パケットを計測することにより、各フローに設定された保証帯域を推定することを特徴とする請求項７記載のノード装置。
パケットを廃棄する際、各フロー内の保証帯域以内に相当するパケットよりも、保証帯域以上に送信されたパケットを優先して廃棄すること特徴とする請求項６〜８いずれか記載のノード装置。
各サービスクラスにおいて、対応するキューが管理しているフローの送信帯域等の情報を参照することで他のフローよりも大きな帯域を使用しているフロー、もしくは保証帯域以上の帯域を他のフローより多く使用しているフローを検出する手段を有し、該フローに属するパケットについてはその廃棄優先度を高く変更する、もしくは優先して廃棄する手段を有することを特徴とする請求項１〜９いずれか記載のノード装置。
各キューの容量もしくは各キューに設定された廃棄閾値を、推定されたフロー数に従って動的に変化させることを特徴とする請求項１〜１０いずれか記載のノード装置。
各サービスクラス毎に１つのキューを持つ代わりに、各サービスクラス毎に複数のキューを持ち、各サービスクラス毎ではなく各キュー毎に帯域割り当て制御を行うことを特徴とする請求項１〜１１記載のノード装置。
入力パケットをその属性情報に基づいて複数のキューのいずれかに格納し、各キュー内の各フローの送信状況から各キューに割り当てる帯域を動的に変更し、前記キューから割り当てられた帯域に従ってパケットを出力回線に出力するノード装置の動作制御方法であって、
前記各キュー毎に扱っているフローのうち一部のフローについてその送信帯域等の情報を記憶手段へ記憶するステップと、
該キューへの入力パケットに対してその所属フローが前記記憶手段で管理されている場合には前記記憶手段の内容を更新するステップと、
前記記憶手段の内容から該キューで現在送信中のフロー数を推定するステップとを含むことを特徴とする動作制御方法。
入力パケットをその属性情報に基づいて複数のキューのいずれかに格納し、各キュー内の各フローの送信状況から各キューに割り当てる帯域を動的に変更し、割り当てられた帯域に従って前記キューからのパケットの廃棄制御を行うノード装置の動作制御方法であって、
各キュー内の一部のフローの状態を記憶手段に記憶するステップと、
各キュー毎に扱っているフローのうち一部のフローについてその送信帯域等の情報を前記記憶手段に記憶するステップと、
該キューへの入力パケットに対してその所属フローが前記記憶手段で管理されている場合には前記記憶手段の内容を更新するステップと、
前記記憶手段の内容から該キューで現在送信中のフロー数を推定するステップとを含むことを特徴とする動作制御方法。
入力パケットをその属性情報に基づいて複数のキューのいずれかに格納し、前記キューからスケジューラを用いてパケットを出力回線に出力するノード装置の動作制御方法であって、
前記入力パケットが属するサービスクラスによって格納するキューを決定するパケット振り分けステップと、
各サービスクラス毎に各フローの送信状況から帯域を割り当てるべきフローの本数を推定するフロー数推定ステップと、
各サービスクラス毎のキューと、各サービスクラス内の推定フロー数とに基づいて、各サービスクラスに割り当てる帯域を動的に変更する帯域割り当て制御ステップと、
各サービスクラスに割り当てられた帯域をもとに各キューからのパケット出力を制御するステップとを含み、
前記フロー数推定ステップが、該キューにて扱っているフローのうち一部のフローについてその送信帯域等の情報を記憶手段に記憶するステップと、該キューへの入力パケットに対してその所属フローが前記記憶手段で管理されている場合には前記記憶手段の内容を更新するステップと、前記記憶手段で管理されているフローを適宜入れ替えるステップと、前記記憶手段で管理されているキューの送信帯域等の情報から前記記憶手段で管理されていないフローを含む前記キューで扱っている全てのフローの数を推定するステップとを有することを特徴とする動作制御方法。
入力パケットをその属性情報に基づいて複数のキューのいずれかに格納し、前記キューからスケジューラを用いてパケットを出力回線に出力するノード装置の動作制御方法であって、
前記入力パケットが属するサービスクラスによって格納するキューを決定するパケット振り分けステップと、
各サービスクラス毎に各フローの送信状況から帯域を割り当てるべきフローの本数を推定するフロー数推定ステップと、
各サービスクラス毎のキューと、各サービスクラス内の推定フロー数とに基づいて、各サービスクラスに割り当てる帯域を動的に変更する帯域割り当て制御ステップと、
各サービスクラスに割り当てられた帯域に従って各キューに入力するパケットの廃棄制御を行うステップと、
各キューからのパケット出力を制御するステップとを有し、
前記フロー数推定ステップが、該キューにて扱っているフローのうち一部のフローについてその送信帯域等の情報を記憶手段に記憶するステップと、該キューへの入力パケットに対してその所属フローが前記記憶手段で管理されている場合には前記記憶手段の内容を更新するステップと、前記記憶手段で管理されているフローを適宜入れ替えるステップと、前記記憶手段で管理されているキューの送信帯域等の情報から前記記憶手段で管理されていないフローを含む前記キューで扱っている全てのフローの数を推定するステップとを有することを特徴とする動作制御方法。