(57)【特許請求の範囲】
【請求項１】
ＩＰネットワークを構成するルータのインターフェースで、到着したＩＰパケットのＩＰヘッダーを参照し、ＩＰトラヒックを、ギャランティーサービスクラス、最低帯域保証クラス及びベストエフォートサービスクラスへのクラス分けを行い、クラス毎のレギュレータを用いてＩＰトラヒックをクラス毎に設定されたキューに振り分け、ギャランティーサービス用キューはＰＱ方式の最優先キューとして設定し、最低帯域保証用キューはＷＦＱ方式によって読出しＷＦＱフローの全レートを制限してＰＱ方式のいずれかの優先キューに入力し、ベストエフォートサービス用キューはＰＱ方式の非優先キューに設定しＰＱ方式により出力リンクへ送ることを特徴とするトラヒック制御方法。
【請求項２】
ＷＦＱの実装には、アクティブなキューではその時点でのビット毎のラウンドロビンがサービスを終了するラウンド数をタグ付けし、アクティブでないキューではそのキューにおける直前のパケットのサービス終了時刻をタグ付けするＳＦＱを用い、ＷＦＱ全体の読出しレートを自由に設定することを可能にした上で、ＰＱ方式のいずれかの優先キューに入れて出力リンクから読出すことを特徴とする請求項１に記載のトラヒック制御方法。
【請求項３】
クラス分けの際にＢＥクラスに設定したトラヒックは、ＰＱにおいて非優先クラスに設定し、ＰＱの各優先クラスに対応するレギュレータのパラメータの全リンクレートをＰＱ全体の出力の帯域より小さく設定し、残りの帯域に対しても優先度別に読出すことを特徴とする請求項１に記載のトラヒック制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＩＰネットワークを構成するルータのインターフェースで実施されるＤｉｆｆｓｅｒｖ（Ｄｉｆｆｅｒｅｎｔｉａｔｅｄ  Ｓｅｒｖｉｃｅ）型のサービスにおいて、クラス別の品質保証を行うためのトラヒック制御方法に関するものである。
【０００２】
【従来の技術】
通信業者がＩＰネットワークにおいてシンプルに付加価値サービスを提供する手段としてＤｉｆｆｓｅｒｖが提案されている。Ｄｉｆｆｓｅｒｖは、ＩＰヘッダーに埋め込まれた情報によって各ルータが優先制御を行ってＩＰ品質保証サービスを提供する方法である。その品質保証サービス要求を保証する重要なメカニズムの一つとしてスケジューリング法が挙げられる。スケジューリング法は、大きくギャランティー型及びベストエフォート型に分けられる。ギャランティー型は、帯域保証、低遅延及び低ジッターを利点とし、ベストエフォート型は、公平性及び帯域利用率を利点としている。これらの利点は相反する特性を実現しようとするものであるため、一方の利点を強調すると他方にとっては欠点となるという性質を持つ。
【０００３】
従来のルータにおいては、サービス品質を保証するようなスケジューリング法が実装されているルータでも、一つのルータに対して一つのスケジューリング法又はインターフェース毎に一つのスケジューリング法を目的に合わせて選択することになっている。代表的なスケジューリング法はＷＦＱ（Ｗｅｉｇｈｔｅｄ  Ｆａｉｒ  Ｑｕｅｕｉｎｇ）  であり、これは、公平性及び帯域利用率に関して非常に優れており、同時に低遅延を実現するスケジューリング法として、現在多くの高性能ルータに実装されている。
【０００４】
このＷＦＱは、到着したＩＰパケットに対してビット毎のラウンドロビンによってサービスを終了するまでの時間をタグ付けし、そのタグの最小のパケットから読出しを行う。しかしながら、保証される遅延及びジッターは設定する帯域によってのみ指定され、また、ギャランティー型トラヒックもベストエフォート型トラヒックと同様の計算によってタグ付けされるためベストエフォート型トラヒックからの影響を避けられない。従って、従来のルータのように、一つのスケジューリング法によってＤｉｆｆｓｅｒｖ型サービスを全て提供することは困難であるという問題がある。
【０００５】
Ｄｉｆｆｓｅｒｖでは、契約帯域を保証し仮想専用線を実現するＥＦ（Ｅｘｐｅｄｉｔｅｄ  Ｆｏｒｗａｒｄｉｎｇ）サービス、及び最低帯域保証付きベストエフォートサービスを行うＡＦ（Ａｓｓｕｒｅｄ  Ｆｏｒｗａｒｄｉｎｇ）サービスの二つのサービスが規定されている。しかしながら、スケジューリング法等に関しては規定されておらず、これらのサービスを実現する方法が課題となっている。以下に、このＤｉｆｆｓｅｒｖ型サービスを、現在多くの高性能ルータに実装されているＷＦＱによって行う場合について説明する。
【０００６】
ＷＦＱは、それぞれのキューから無限小のデータを公平に読出すＧＰＳ（Ｇｅｎｅｒａｌｉｚｅｄ  Ｐｒｏｃｅｓｓｏｒ  Ｓｈａｒｉｎｇ）  サーバをビット毎に実行するようにモデル化し、到着したパケットはそのＧＰＳによるサービス終了時刻によってソートされ、読出される。また、キューにパケットが存在する際には常に読出しを行うので、公平性及び帯域利用率に関して非常に優れている。また、ＷＦＱは、コネクション毎の帯域を保証しており、複数段のＷＦＱスケジューラを介してエンド間を接続した場合の遅延は以下のように示される（Ａ．Ｋ．Ｐｅｒｅｋｈ，  Ｒ．Ｇ．Ｇａｌｌａｇｅｒ，  ”Ａ  Ｇｅｎｅｒａｌｉｚｅｄ  Ｐｒｏｃｅｓｓｏｒ  Ｓｈａｒｉｎｇ  Ａｐｐｒｏａｃｈ  ｔｏ  Ｆｌｏｗ  Ｃｏｎｔｒｏｌ  ｉｎ  Ｉｎｔｅｇｒａｔｅｄ  Ｓｅｒｖｉｃｅ  Ｎｅｔｗｏｒｋｓ−Ｔｈｅ  Ｍｕｌｔｉｐｌｅ  Ｎｏｄｅ  Ｃａｓｅ”，  ＩＥＥＥ／ＡＣＭ  ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｎｅｔｗｏｒｋｉｎｇ，  ｐｐ．１３７−１５０，Ａｐｒ．１９９４  参照）。
【０００７】
いま、ｋ番目のスケジューラがリンクレートｒ（ｋ）  のリンクで接続されている場合、φを重み付けとすると、リーキーバケットパラメータ（σ，ρ）で制限されたソースｉがそのスケジューラで受けるサービスレートｇ（ｉ，ｋ）  は、次式で表される。
【数１】
0003623420.tif 000002
【０００８】
ここでは、最小のサービスレートｇ（ｉ）  はρより大きいとする。また、コネクションの中で最大のパケット長をＰｍａｘ（ｉ）とし、他のコネクションの影響はないとすると、エンド間での遅延Ｄ（ｉ）  は次式で制限される。
【数２】
0003623420.tif 000003
従って、エンド間での遅延は適切なｇ（ｉ）  を割当てることによって制限することができ、ギャランティー型としても用いることができる。
【０００９】
ＡＦのみのサービスをＷＦＱで行うには、それぞれのサービスクラスに対応する最低帯域分の重み付けを行えばよく、クラス間の公平性又は帯域利用率を考えても適用できると考えられる。しかしながら、同時にギャランティークラスであるＥＦクラスのサービスを行う場合は、ＥＦクラスの品質を保つことが難しい。ＷＦＱでも式２に示したように到着するトラヒックをリーキーバケット等で制限すれば、エンド間での最大遅延を抑え、ジッターを抑えることができる。しかし、式２から、その最大遅延は配分するレートによって左右され、低遅延及び低ジッターを実現するにはより多くの帯域を必要とし、ネットワーク設計上問題がある。また、他のトラヒックの影響も全くないことはなく、空き帯域をアクティブなコネクションで共用するため、コネクション数によって式１のレートの変化率が影響を受ける。即ち、ＡＦトラヒックの混み具合によってＥＦトラヒックに影響が出るという問題がある。
【００１０】
これらの上述の問題は他のスケジューリング法を用いる場合でも同様に生起する問題であり、ギャランティー型（ＥＦ型）サービスとベストエフォート型（ＡＦ型）サービスとを同時に実現することは難しい。
【００１１】
【発明が解決しようとする課題】
本発明の目的は、Ｄｉｆｆｓｅｒｖ型サービスを実現する場合の上述の問題を解決し、簡易な構成でギャランティー型サービスとベストエフォート型サービスとを同時に実現することができるトラヒック制御方法を提供することにある。
【００１２】
【課題を解決するための手段】
本発明のトラヒック制御方法は、上記の目的を達成するため、ＩＰネットワークを構成するルータのインターフェースで、到着したＩＰパケットのＩＰヘッダーを参照し、ＩＰパケットを、ギャランティーサービスクラス、最低帯域保証クラス及びベストエフォートサービスクラスへのクラス分けを行い、クラス毎のレギュレータを用いてＩＰトラヒックをクラス毎に設定されたキューに振り分け、ギャランティーサービス用キューはＰＱ方式の最優先キューとして設定し、最低帯域保証用キューはＷＦＱ方式によって読出しＷＦＱフローの全レートを制限してＰＱ方式のいずれかの優先キューに入力し、ベストエフォートサービス用キューはＰＱ方式の非優先キューに設定しＰＱ方式により出力リンクへ送ることを特徴とする。
【００１３】
本発明のトラヒック制御方法においては、ＷＦＱの実装に、アクティブなキューではその時点でのビット毎のラウンドロビンがサービスを終了するラウンド数をタグ付けし、アクティブでないキューではそのキューにおける直前のパケットのサービス終了時刻をタグ付けするＳＦＱ（Ｓｔａｒｔ−Ｔｉｍｅ  Ｆａｉｒ  ｑｕｅｕｉｎｇ）（Ｐ．Ｇｏｙａｌ，Ｈ．Ｖｉｎ，Ｈ．Ｃｈｅｎ，  ”Ｓｔａｒｔ−Ｔｉｍｅ  Ｆａｉｒ  Ｑｕｅｕｉｎｇ  ：  Ａ  Ｓｃｈｅｄｕｌｉｎｇ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｉｎｔｅｇｒａｔｅｄ  Ｓｅｒｖｉｃｅｓ  Ｐａｃｋｅｔ  Ｓｗｉｔｃｈｉｎｇ  Ｎｅｔｗｏｒｋｓ”，  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＡＣＭ  ＳＩＧＣＯＭＭ  ’９６，Ａｕｇ．１９９６  参照）  を用い、ＷＦＱ全体の読出しレートを自由に設定することを可能にした上で、ＰＱ方式のいずれかの優先キューに入れて出力リンクから読出すようにしてもよい。
【００１４】
また、クラス分けの際にＢＥクラスに設定したトラヒックは、ＰＱにおいて非優先クラスに設定し、ＰＱの各優先クラスに対応するレギュレータのパラメータの全リンクレートをＰＱ全体の出力の帯域より小さく設定し、残りの帯域に対しても優先度別に読出すようにしてもよい。
【００１５】
このような本発明によれば、ＰＱ方式は最優先キューのパケットを到着し次第読出すので、到着レート以上に読出しレートを設定することにより低遅延及び低ジッターを実現することができる。スケジューリング全体としては、ＡＦクラスのＷＦＱ方式とＥＦクラスのＰＱ方式とを完全に独立させることにより、ＥＦクラスに対するＡＦクラスの影響を防ぐ。これらのスケジューリングの前段には、クラス分け機構、及びそれぞれのサービスクラスのプロファイルに基づくトークンバケットレギュレータを設けており、トークンバケットパラメータ（トークンレート、バケットサイズ、リンクレート）により特徴付けられたトラヒックがスケジューラに送られるため、ＥＦクラス及びＡＦクラスそれぞれにおいて品質を保証することができ、Ｄｉｆｆｓｅｒｖ型サービスを全て実現することができる。
【００１６】
【発明の実施の形態】
次に図面を用いて本発明の実施例を説明する。本発明の方法を実施する場合、既知のルータ構成を用いて実施することができる。図１はこのようなルータの例の機能ブロック図である（Ｙ．Ｂｅｒｎｅｔ  ｅｔ  ａｌ．，  ”Ａ  Ｃｏｎｃｅｐｔｕａｌ  Ｍｏｄｅｌ  ｆｏｒ  Ｄｉｆｆｓｅｒｖ  Ｒｏｕｔｅｒ”，  Ｄｒａｆｔ−ｉｅｔｆ−ｄｉｆｆｓｅｒｖ−ｍｏｄｅｌ−００．ｔｘｔ，Ｊｕｎｅ  １９９９参照）  。このルータは二つのインターフェースＡ及びＢを有するルータであり、エッジルータとして用いる場合は、入力側モジュールにおいて契約に応じてシェーピングを行う。また、コアルータとして用いる場合は、入力側モジュールを省略することができる。本発明によりＤｉｆｆｓｅｒｖ型サービスを実現するためには、出力側モジュールで図２に示すトラヒック制御を行う。
【００１７】
図２は、本発明によるトラヒック制御方法を説明するための図である。到着したＩＰパケットに対して、クラス分け機構１１が、ＩＰヘッダーのＤｉｆｆｓｅｒｖコードポイント、ソース／デスティネーションアドレス、ソース／デスティネーションポート、ＩＰプロトコル番号等を識別し、フロー毎に識別子を決定し、ＥＦクラスＡ、ＡＦクラスＢ〜Ｅ、ＢＥクラスＦ及び不適合パケットＸにクラス分けし、それぞれのプロファイルに従ってクラスＡ〜Ｆについて設定されたトークンバケットレギュレータ１２ａ〜１２ｎにＩＰパケットを送る。非適合であるクラスＸのパケットは直ちに破棄される。
【００１８】
トークンバケットレギュレータ１２ａ〜１２ｎは、例えばバケットサイズ、トークンレート及びリンクレートの三つのパラメータでトラヒックを制限する。図３に示すように、到着したパケットは、トークンがある場合はそのトークンサイズだけ送出され、トークンがない場合は破棄される。バケットの中のトークンはトークンレートで溜まり、最大値はバケットサイズで制限されている。例えばＬバイトのフローが到着した時は、バケットの中にＬ個のトークンがある場合に送出が許可される。即ち、トークンレートに相当する平均レートを超えてバケットサイズまでのバーストが許可され、リンクレートによって、その大きさが制限される。
【００１９】
図２の場合、ＥＦクラスのパケットＡはＰＱ方式の最優先キュー１４ａに送られ、ＡＦクラスのパケットＢ〜ＥはＷＦＱのキュー１３ａ〜１３ｎに送られ、ＢＥクラスのパケットＦはＰＱ方式の非優先キュー１５に送られる。
【００２０】
ＷＦＱは、アクティブなキューに対してそれぞれのキューのデータを無限に細かく分割して理想的に公平なスケジューリングを行うＧＰＳサーバを、パケット単位でのスケジューリングに近似したものである。ＷＦＱは、ＧＰＳサーバをビット毎のラウンドロビンでモデル化し、そのラウンドロビンでのサービス時間を基にしてサービス終了時刻を決定し、それにより、パケットをソートし順次読出す。
【００２１】
即ち、或る時刻ｔにおいて、コネクションｉに到着したｋ番目のパケットのパケットサイズをＰ（ｉ，ｋ，ｔ）  、ラウンドナンバーをＲ（ｔ）  、サービスを終了する時刻であるフィニッシュナンバーをＦ（ｉ，ｋ，ｔ）  、ｉ番目のコネクションに対する重み付けをφ（ｉ）  とすると、ＷＦＱサーバは、次式によりＦ（ｉ，ｋ，ｔ）  を決定し、Ｆ（ｉ，ｋ，ｔ）  の小さいパケットからサービスを行う。
【数３】
0003623420.tif 000004
【００２２】
このようなアクティブなコネクションのみの計算を行うため、帯域を公平に配分でき、なお且つ利用可能な帯域を最大限活用することができる。しかしながら、Ｒ（ｔ）  の計算はパケットの到着及び送出毎に計算しなければならず、その実装は非常に困難であるため、この実施例では、このＲ（ｔ）  の計算にＳＦＱの方法を用いる。即ち、パケットがアクティブではないキューに到着した際には、その時点でのラウンドナンバーをスタートナンバー（Ｓ（ｉ，ｋ，ｔ））とし、パケットがアクティブなキューに到着した際には、その直前のパケットのフィニッシュナンバーをスタートナンバーとし、次式によりフィニッシュナンバーＦ（ｉ，ｋ，ｔ）  を決定する。
【数４】
0003623420.tif 000005
【００２３】
このようにすることにより、ＷＦＱの問題点とされるコネクションの繰り返し削除を防ぐことができる。パケットはこのフィニッシュナンバーＦ（ｉ，ｋ，ｔ）  によりソートされ、それぞれのキューに送られる。ＷＦＱ全体のフローは、スタティックに全体のフローのレートに制限を与えて、ＰＱのいずれかの優先キューに送る。
【００２４】
ＰＱはそれぞれのコネクションがサービスする優先順位に相当し、例えばｎ個の優先レベルがある場合、或る番号の優先レベルに対してそれより高い優先度の番号の優先レベルに属するパケットは常に優先的に送出される。即ち、優先レベルｋのパケットは、ｋ＋１，ｋ＋２，．．．，ｎの番号の優先レベルにサービス待ちのパケットがない場合のみサービスされる。優先キュー１４（図２）は、ＥＦフロー及びＡＦフロー即ちＷＦＱフローを集合し、優先レベルに従って読出す。
【００２５】
このような構成を有するトラヒック制御方法を用いるモジュールをルータのインターフェースに装備することにより、Ｄｉｆｆｓｅｒｖ型サービスを全て実現することができる。以下に、ＥＦクラス、ＡＦクラス及びＢＥクラスについて具体的に説明する。
【００２６】
ＥＦクラスのトラヒックは、上述のように、低遅延及び低ジッターを実現するものであり、本発明では、トークンバケットレギュレータ及びＰＱによって実現される。クラス分け機構でＥＦクラスに識別されるフローのトークンバケットパラメータは、バケットサイズ＝０、トークンレート＝リンクレートである。契約帯域をリンクレートに設定することにより契約違反トラヒックを排除することができる。このＥＦクラスのトラヒックはＷＦＱのフィニッシュナンバーの計算を行わず、処理のオーバーヘッドを減らすことができる。ＥＦクラスのトラヒックは直接ＰＱの最優先キュー１４ａに送られ、このＰＱでは、入力レートを常に出力レートより小さく設計することにより、キューイング遅延及びジッターを最小にすることができる。また、このように完全にキューを分けることにより、このＥＦクラスのキューサイズを削減することができる。
【００２７】
ＡＦクラス即ち最低帯域保証クラスのトラヒックは、限られた帯域を有効に活用し且つ帯域を保証されるものであり、本発明では、トークンバケット及びＷＦＱによって実現される。クラス分け機構１１で四つのＡＦクラスＢ〜Ｅに識別されたフローは、それぞれのクラスのプロファイルに応じてトークンバケットパラメータを設定される。ＷＦＱの重み付けはトークンレートによる重み付けであり、フィニッシュナンバーの計算を行うことによりクラス間での公平性を確保し、且つＡＦクラスに与えられた帯域を有効に利用する。このＷＦＱ全体の読出しレートを制限し、ＰＱのいずれかの優先キュー１４に入力することにより、出力帯域をＰＱ及びＷＦＱ双方で共用すると共に、ＥＦクラスのトラヒックに対するＡＦクラスのトラヒックの影響を防ぐことができる。
【００２８】
クラス分け機構１１でＢＥクラスに設定したトラヒックは、ＰＱにおいて優先キュー１４以外の非優先レベル１５に設定する。ＰＱでは、低優先のトラヒックは高優先のトラヒックの影響を受け、その優先レベルに応じて遅延及びジッターを受ける。本発明では、ＥＦクラス及びＡＦクラスのトークンバケットパラメータのリンクレートをＰＱの全出力の帯域より小さく設定するため、残りの帯域に対して、ＢＥクラス内においてもＰＱの優先レベルによる差別化サービスを提供することができる。
【００２９】
【発明の効果】
以上説明したように、本発明によれば、Ｄｉｆｆｓｅｒｖ型サービスの契約帯域を保証し低遅延及び低ジッターを実現するクラスであるＥＦクラスと、最低帯域保証付きのベストエフォートクラスであるＡＦクラスとのサービスを同時に実現することができる。即ち、ＥＦクラスサービスにはＰＱを行うことにより低遅延及び低ジッターを実現し、ＡＦクラスサービスにはＷＦＱを用いることによりＥＦクラスに対する影響を防ぎ、また、ＡＦクラス間での公平性及び帯域利用率を高め、配分された帯域を最大限活用することができる。ＢＥクラスでは帯域保証なしの優先度別サービスを実現することができる。本発明はＷＦＱをベースとした簡易な構成であり、実装を容易なものとしているため、現在多くの高性能ルータに実装されているＷＦＱを本発明の実行に適するように改良することにより、簡単にＤｉｆｆｓｅｒｖ型サービスの全てを提供できるようにすることができる。
【図面の簡単な説明】
【図１】Ｄｉｆｆｓｅｒｖルータの例の機能ブロック図である。
【図２】本発明によるトラヒック制御方法を説明するための図である。
【図３】トークンバケットレギュレータの動作を説明するための図である。
【符号の説明】
１１  クラス分け機構
１２  トークンバケットレギュレータ
１３  キュー
１４  優先キュー
１４ａ  最優先キュー
１５  非優先キュー
【図１】
0003623420.tif 000006
【図２】
0003623420.tif 000007
【図３】
0003623420.tif 000008