(57)【特許請求の範囲】
【請求項１】
１以上のインターネットサービスプロバイダを介して相互に接続されたインターネットサービスカスタマ間でＩＰパケットの送受信を行う手段を備えた通信網において、
前記インターネットサービスプロバイダ内のルータに設けられ、通過するパケットにあらかじめ設定されたサービスクラスにしたがって当該パケットを該当するキューにそれぞれ蓄積する手段と、
前記ルータ内においてパケットを処理する順番を決めるスケジューリングを決めるために使用するトラヒックモデルとしての参照システムを生成する手段と、
この参照システムにしたがって前記サービスクラス毎に望ましいキュー長を算出する手段と、
この算出する手段の算出結果にしたがって前記蓄積する手段のキュー長が前記望ましいキュー長に近づくようにパケットを取り出すべきキューを選択する方法およびそのときのパケット送出速度を設定する手段と
を備えたことを特徴とする通信網。
【請求項２】
前記算出する手段は、ｄｉをｉ番目のキューにおけるパケットの数とし、このｉ番目のキューヘのデータパケットの到着は平均到着率λｉの一般分布に従い、パケット長も一般分布に従うとし、前記参照システムに対して最大配信時間の目標値ｔｉを与え、キューｉの系内時間の密度関数のラプラス変換形（ＬＳＴ）Ｄ＊ｉ（ｓ）、および平均キュー長［外３］を
【数２】
0003607522.tif 000009
として求める手段を含み、前記設定する手段は、前記参照システムから得られた平均キュー長［外３］を参照値として用いて実際のキュー長ｄｉと参照値［外３］との差が最小になるように送出すべきパケットを含むキューを選択する順序を決める方法およびそのときのパケット送出速度を設定する手段を含む請求項１記載の通信網。
【外３】
0003607522.tif 000010
【発明の詳細な説明】
【０００１】
【発明が属する技術分野】
本発明はインターネットサービスに利用する。特に、複数のインターネットサービスプロバイダ（以下、ＩＳＰという）に対する課金処理技術および複数のＩＳＰにおけるパケット転送処理のスケジューリング技術に関する。
【０００２】
【従来の技術】
インターネットサービスにおける通信網の構成を図１に示す。図１はインターネットサービスカスタマ（以下、ＩＳＣという）間に複数のＩＳＰが接続された通信網の構成を示す図である。図１に示すような通信網におけるインターネットサービスでは、従来は、パケットの転送遅延、廃棄率その他の品質保証を行う方法はいくつか提案されてはいるもののまだ実現されるには至っていない。また、エンド−エンドでの課金をどのような考え方で行うべきかということについての提案はない。さらに、パケット処理のスケジューリング方法に関しては、複数の並列待ち行列システム（以下、キューという）において１つのサーバが、各キューからどのような順番に呼（パケット）を取り出して、何個連続して処理すればよいかという一般的なスケジューリング法が述べられているだけである。
【０００３】
例えば、サーバが順番にキューを巡回してサービスするラウンドロビン方式には、各待ち行列の待ち呼をすべて処理する全処理式、ｋ個まで処理するｋ−制限式、到着時点までに並んでいる呼のみを処理するゲート式などがある。また、上記ラウンドロビン型にある重み付けをしたＷＲＲ（Ｗｅｉｇｈｔｅｄ  Ｒｏｕｎｄ  Ｒｏｂｉｎ）方式、先着順に処理するＦＩＦＯ（Ｆｉｒｓｔ  Ｉｎ  Ｆｉｒｓｔ  Ｏｕｔ）方式、各待ち行列に対してその待ち行列のサービスレートに関係するある値の実数を割り当て、処理状況に従ってその値の再配分計算を行うＷＦＱ（Ｗｅｉｇｈｔｅｄ  Ｆａｉｒ  Ｑｕｅｕｅ）方式などがあるが、これらの方式はいかなる到着に対してもマルチレベルの品質を保証するという観点からの処理方式ではない。
【０００４】
【発明が解決しようとする課題】
上記従来例では、複数のＩＳＰ網が接続されている通信網において、ＩＳＣがエンド−エンドの品質保証サービスを受ける場合に、各ＩＳＰ毎に課金処理をどのようにしたらよいか、またその実現のためには、各ＩＳＰ網内の各ルータにおいてどのようなキュー選択スケジューリングアルゴリズムでパケットを処理（送出）したらよいかという課題についての提案はない。
【０００５】
本発明は、このような背景に行われたものであって、一つの網内の複数のＩＳＰに対する正当な課金処理を行うことができる通信網を提供することを目的とする。本発明は、一つの網内の複数のＩＳＰにおけるパケットのサービスクラス毎の品質を保証することができる通信網を提供することを目的とする。
【０００６】
【課題を解決するための手段】
本発明は、複数のＩＳＰ網がネットワーク上で接続されている形態において、ユーザがエンド−エンドでインターネットサービスを受ける場合には、その課金について各ＩＳＰ毎に測定した情報をもとに積み上げ式に算出する。そのときに品質（遅延時間など）をある一定値以下に抑えながら、すなわち品質を保証しながら各パケットをそれぞれ遅延目標値より小さい値にするよう処理することを特徴とする。
【０００７】
本発明の課金処理とパケット転送スケジューリングアルゴリズムを説明する前に、まず次のような技術的背景について説明する。
【０００８】
・品質配分
パケットが横断できるＩＳＰの数はある値に制限されており、エンド−エンド品質の目標値は各ＩＳＰに均等に配分されているようなＩＳＰ網間接続形態を仮定する。
【０００９】
・品質クラス
品質クラスは、一つまたは複数の品質パラメータ（例えば、遅延、遅延の分散、損失確率など）を用いて定義される。各品質クラスは、各パラメータに対して明確にエンド−エンドの目標値をもっている。これらのパラメータに対して加法則が成り立つことを仮定して、エンド−エンド品質の目標値の１／ｎが各ＩＳＰに割り当てられるとする。
【００１０】
・帯域契約
ＩＳＰとＩＳＣ間、またはＩＳＰ間の論理的なインタフェースを「コネクションポイント（ＣＰ）」と呼ぶ。ＩＳＣは一つまたは複数のホスト（ＩＳＣシステム）を有する自分自身の網をもつ。ＩＳＰ網とＩＳＣシステムは各ＣＰを通してデータパケットを転送するボーダルータ（ｂｏｒｄｅｒ  ｒｏｕｔｅｒ）をもつ。各ＣＰにおいては、各方向のデータパケットトラヒック（以下、単に帯域という）が、ある時間区間に対して両方の団体（ＩＳＰまたはＩＳＣ）の契約として各品質クラス毎に詳細に定められる。ここで、各ＣＰにおいて各方向のデータトラヒック毎に詳細に決められる帯域は、アプリケーションのフロー毎ではなく、行き先ＣＰにかかわらないすべてのフローを束ねたものである。
【００１１】
ここで、契約に基づくＣＰ−ＣＰ間の帯域の算出は各ＩＳＰがおこない、このＩＳＰは、入り口ボーダルータ（ＩＢＲ）から入ってくるデータパケットトラヒックを各品質クラスに対して要求される隣接団体（ＩＳＰまたはＩＳＣ）へ配送する責任を負う。
【００１２】
ここで２種類の契約が考えられる。一つは「実帯域保証」であり、もう一つは「最低帯域保証」である。後者では、もしネットワークが未使用の帯域を持っているときには、ＩＳＰは契約帯域を超えて付加的なデータパケット転送容量を供給することができる。
【００１３】
・データパケット転送法
あるＩＳＰのＩＢＲにおいて、次に転送される（下流の）団体（ＩＳＰまたはＩＳＣ）の出口ボーダルータ（ＥＢＲ）のＩＰアドレスが、流入してくるデータパケット毎に与えられる。流入してくる各データパケットは「転送パケット（ＴＤ）」と呼ばれる新しいパケットにカプセル化されるが、それらはソースＩＰアドレスとして現在のＩＳＰのＩＢＲのＩＰアドレスと行き先ＩＰアドレスとして次に転送される団体のＥＢＲのＩＰアドレスをＩＰヘッダ内にもっている。そのＴＤは現在のＩＢＲからＥＢＲに配信される。同じ品質クラスの同じＥＢＲが行き先である複数のデータパケットは一つのＴＤ内にカプセル化され得る。
【００１４】
そのＴＤは、ＩＳＰ内の各中継ルータの通常のデータパケット送出機能を用いてＥＢＲへ配信される。そのＥＢＲにおいては、そのＴＤはカプセルから取り外されもとのパケットとして収納される。この転送法を用いることにより、各ルータは、各ＴＤの送出元と行き先のルータ（ＩＢＲとＥＢＲ）を特定することができ、各品質クラス毎に配分された目標値を満たすようにスケジューリングすることができる。
【００１５】
・トラヒックシェーピングとポリシング
各ＣＰにおいては、上流団体（ＩＳＰまたはＩＳＣ）は各品質クラス毎の契約帯域に合うように流出していくデータパケットに対して（ＥＢＲにおいて）トラヒックシェーピングを実行する。最低帯域保証の場合には、トラヒックシェーピングは要求されない。下流のＩＳＰは流入してくるデータパケットに対して、ＩＢＲにおいてポリシングを行う。契約帯域に違反するデータパケットについては、実帯域保証の場合にはＩＢＲで廃棄され、最低帯域保証の場合にはこのＩＳＰ網内では低い優先度で処理されるように印を付けられる。
【００１６】
以上の前提の基に、本発明では、次のように課金処理とスケジューリングアルゴリズムを定める。
【００１７】
すなわち、本発明は、１以上のＩＳＰを介して相互に接続されたＩＳＣ間でＩＰパケットの送受信を行う手段を備えた通信網である。
【００１８】
ここで、本発明の特徴とするところは、前記ＩＳＣと前記ＩＳＰとの間または前記ＩＳＰ相互間に設けられ、通過するＩＰパケットのヘッダ情報に含まれる課金情報にしたがって自己に接続された前記ＩＳＣまたは前記ＩＳＰに関する課金処理を実行する手段を備えたところにある。
【００１９】
前記課金処理を実行する手段は、Ｗｉｊｃをパケット転送経路の上流にあるＩＳＰまたはＩＳＣ（Ｐｉ）から下流にあるＩＳＰまたはＩＳＣ（Ｐｊ）へのある品質クラスのデータトラヒックに対する契約帯域とし、Ｐｉによって支払われる部分をＷｉｊ、Ｐｊによって支払われる部分を［外４］とし、ｆｉｊおよび［外５］をＰｉおよびＰｊの契約によって決定される料金係数とするとき、ＩＳＰｋに着目し、このＩＳＰｋに隣接するＩＳＰまたはＩＳＣのセットをＳｋ、このＩＳＰｋに隣接するＩＳＣのセットをＵｋとし、データパケットの配信料金は契約帯域に比例するとき、前記ＩＳＰｋの収入と支出の差Ｄｋは、
【００２０】
【数３】
0003607522.tif 000002
として処理する手段を含むことが望ましい。
【００２１】
【外４】
0003607522.tif 000003
【００２２】
【外５】
0003607522.tif 000004
【００２３】
【外６】
0003607522.tif 000005
【００２４】
また、前記ＩＳＰ内のルータに設けられ、通過するパケットにあらかじめ設定されたサービスクラスにしたがって当該パケットを該当するキューにそれぞれ蓄積する手段と、前記ルータ内においてパケットを処理する順番を決めるスケジューリングを決めるために使用するトラヒックモデルとしての参照システムを生成する手段と、この参照システムにしたがって前記サービスクラス毎に望ましいキュー長を算出する手段と、この算出する手段の算出結果にしたがって前記蓄積する手段のキュー長が前記望ましいキュー長に近づくように前記蓄積する手段からのパケットを取り出すべきキューを選択する方法およびそのときのパケット送出速度を設定する手段とを備えることが望ましい。
【００２５】
前記算出する手段は、ｄｉをｉ番目のキューにおけるパケットの数とし、このｉ番目のキューヘのデータパケットの到着は平均到着率λｉの一般分布に従い、パケット長も一般分布に従うとし、前記参照システムに対して最大配信時間の目標値ｔｉを与え、キューｉの系内時間の密度関数のラプラス変換形（ＬＳＴ）Ｄ＊ｉ（ｓ）、および平均キュー長［外６］を
【００２６】
【数４】
0003607522.tif 000006
として求める手段を含み、前記設定する手段は、前記参照システムから得られた平均キュー長［外６］を参照値として用いて実際のキュー長ｄｉと参照値［外６］との差が最小になるように前記蓄積する手段からの送出すべきパケットを含むキューを選択する方法およびそのときのパケット送出速度を設定する手段を含むことが望ましい。
【００２７】
【発明の実施の形態】
本発明実施例を図１ないし図３を参照して説明する。図２は品質クラス毎に分かれたキューのオリジナルシステムおよびその参照システムを示す図である。図３は本発明実施例のスケジューリングアルゴリズムを示す図である。
【００２８】
本発明は、図１に示すように、１以上のＩＳＰを介して相互に接続されたＩＳＣ間でＩＰパケットの送受信を行う通信網である。
【００２９】
ここで、本発明の特徴とするところは、ＩＳＣとＩＳＰとの間またはＩＳＰ相互間に設けられ、通過するＩＰパケットのヘッダ情報に含まれる課金情報にしたがって自己に接続されたＩＳＣまたはＩＳＰに関する課金処理を実行する手段としての課金処理部１を備えたところにある。
【００３０】
また、図２に示すように、ＩＳＰ内のルータには、通過するパケットにあらかじめ設定されたサービスクラスにしたがって当該パケットを該当するキューにそれぞれ蓄積し、前記ルータ内においてパケットを処理する順番を決めるスケジューリングを決めるために使用するトラヒックモデルとしての参照システムを生成し、この参照システムにしたがって前記サービスクラス毎に望ましいキュー長を算出し、この算出結果にしたがってキュー長が前記望ましいキュー長に近づくようにパケットを取り出すべきキューを選択する方法およびそのときのパケット送出速度を設定することを特徴とする。
【００３１】
（課金処理の実施例）
図１に示すＩＳＰは提供したサービスに対して課金するが、本発明実施例では、エンド−エンドの課金ではなく、代りに各ＣＰにおいてＩＳＣ−ＩＳＰ間、またはＩＳＰ間で契約帯域に基づく課金を考える。
【００３２】
課金は各ＩＳＰ網内に設けられる課金処理部１において契約帯域に基づいて行われるので、それはＣＰの上流のＩＳＰと下流のＩＳＰに分配される。この課金の分配に対しては測定データを使用する。Ｗｉｊｃを上流団体（ＩＳＰかＩＳＣ）Ｐｉから下流団体Ｐｊへのある品質クラスのデータトラヒックに対する契約帯域とする。また、使用される帯域は、次の２つの部分に分割される。一つはＰｉによって支払われる部分（Ｗｉｊ）であり、もう一つはＰｊによって支払われる部分［外４］である。この分割はＩＰヘッダの中の課金インジケータに基づいて行われる。ｆｉｊと［外５］をＰｉとＰｊの契約によって決定される料金係数とする。
【００３３】
ＩＳＰｋに注目したときに、Ｓｋを隣接する団体（ＩＳＰまたはＩＳＣ）のセット、Ｕｋを隣接するＩＳＣのセットとする。簡単のため、データパケットの配信料金は契約帯域に比例すると仮定する。ＩＳＰｋの収入と支出の差は次式で与えられる。
［数３］
ここで、ＩＳＰｋが正味の収入を得るためには、Ｄｋは０より大きくなければならない。
【００３４】
（スケジューリングアルゴリズムの実施例）
本発明実施例のスケジューリングアルゴリズムを図２および図３を参照して説明する。一つの品質パラメータ、エンド−エンドデータパケット配信時間に着目する。配信時間に関しては、ｋ個の品質クラスがあると仮定し、クラスｋに対する最大エンド−エンド配信時間の目標値をＴｋ（ｋ＝１、・・・、Ｋ）とする。ここで、ｉ＜ｊに対してはＴｉ＜Ｔｊである。最大エンド−エンド配信時間は、その時間以内にデータパケットの９５％が配信される時間であると定義する。まず、最大エンド−エンド配信時間の目標値を各ＩＳＰに均等に割り当てる。どのデータパケットに対しても、配信に携わることのできるＩＳＰの最大数はｎであり、したがって、クラスｋに対するＩＳＰ当りの最大配信時間の目標値はＴｋ／ｎとなる。
【００３５】
次に、ＩＳＰ当りの最大配信時間の目標値をそのＩＳＰ内の各ルータに均等に割り当てる。もし、あるＩＳＰのＩＢＲｉから次に向かう（その下流の）ＩＳＰのＩＢＲに配信されるクラスｋのデータパケットが、途中でＭｉｊｋ個のルータを経由すると仮定すると、ルータ当りの最大配信時間の目標値は、
Ｔｋ／ｎ（Ｍｉｊｋ＋１）
となる。
【００３６】
あるルータ内の各クラスに対して最大配信時間を制御するアルゴリズムは次のようなものである。あるＩＳＰ内の各ルータは、各出チャネルに対して、各フロー及び各クラス毎に一つのキューをもっているものとする。ここである出チャネルに対するキューの数をＮとする。もしそのＩＳＰの隣接団体（ＩＳＰかＩＳＣ）の総数をＭと仮定すると、フローの総数はＭ（Ｍ−１）である。したがって、あるルータ内での出チャネル毎のキューの最大数は、Ｍ（Ｍ−１）Ｋとなる。したがって、Ｎ≦Ｍ（Ｍ−１）Ｋである。各キューは、上で述べたように対応する最大配信時間の目標値をもっている。それを以後ｔｉ（ｉ＝１、…、Ｎ）と定義する。流入してくるデータパケットはそのフローとクラスに対してふさわしいキューに置かれる。
【００３７】
ここで、あるルータにおいてデータパケット配信時間を決定づける主要な要因は、待ち時間とパケットを出チャネルヘ転送する時間であると仮定する。このようにしてシングルサーバと複数の待ち行列をもつ待ち行列システムを用いてシステムをモデル化する。ここで、ｄｉをｉ番目のキューにおけるパケットの数とする（サービス中のパケットを含まない）。システム設計パラメータとして、ｉ番目のキューヘのデータパケットの到着は平均到着率λｉの一般分布に従い、パケット長も一般分布に従うとする。
【００３８】
ここで、それぞれがオリジナルシステムの一つのキューに対応しているＭ／Ｇ／１待ち行列システムの一つのセットを導入する（以後これを参照システムと呼ぶ）（図２）。参照システムに対して最大配信時間の目標値ｔｉを与える。このとき、キューｉの系内時間の密度関数のラプラス変換形（ＬＳＴ）Ｄ＊ｉ（ｓ）、および平均キュー長ｄｉは、Ｐｏｌｌａｃｚｅｋ−Ｋｈｉｎｔｃｈｉｎｅの式より次式で定まる。［数４］
【００３９】
ここで、参照システムから得られた平均キュー長［外６］を参照値として用い、実際のキュー長ｄｉと参照値［外６］との差をできるだけ最小にするようにオリジナルシステムのキューを選択し、その中のパケットをサービスする。
【００４０】
より詳しく述べると、
【数５】
0003607522.tif 000007
の値が最大であるキューｉを選択し、このキューの中の一つのパケットがサービスされる。ここで、パラメータ１／σｉは、データパケット数を待ち時間に変換するために必要な重みづけファクタである（σｉはキュー長の標準偏差であり、平均と２次モーメントから計算可能である）。もし、同じ最大値をもつキューが複数存在する場合には、それらのキューの中で最後にサービスされたキューを選ぶ。これは、そのキューが他のキューより高い到着率をもつからであり、したがってもしサービスされなければ今後も［数５］の値が大きいであろうと思われるからである。
【００４１】
上記の発見的なスケジューリングアルゴリズムの効果を、図２（Ａ）のオリジナルシステムにおいて、Ｎ＝１０、データパケット長が指数分布（平均２０００ビット）に従う場合についてシミュレーション結果により示す。ここでθ＝１は、すべてのトラヒックの和Σλｉ（ｉ＝１、…、１０）が一つのキューに到着し先着順にサービスされるシングルキューシステム（Ｍ／Ｇ／１）において、最も厳しい系内時間の目標値を満たすのに必要な伝送容量を意味する。シミュレーション条件は、一つのキュー（キュー番号１）のみが目標値が厳しく到着率が低く、その他のキュー（キュー番号２〜１０）は平均してその１０倍の到着率があり、目標値はその５０倍も緩い場合を想定する。なお、シミュレーション条件は表１に示すとおりである。
【００４２】
【表１】
0003607522.tif 000008
【００４３】
図４は、最大配信時間の目標値ｔｉとシミュレーションから得られたｉ番目のキューの実際の配信時間ｔｉ’（ｉ＝１、…、１０）を比較したものであり、横軸にキュー番号をとり、縦軸に最大配信時間をとる。図４より提案されたスケジューリングアルゴリズムは、ｔｉ’≦ｔｉ（ｉ＝１、…、１０）を十分に満たすように最大配信時間を良く制御していることがわかる。
【００４４】
図５は、各キュー群の最大配信時間の最大値をθの各値に対して示したものであり、横軸にθをとり、縦軸に最大配信時間をとる。必要な伝送容量は、最大配信時間の目標値と実際の最大配信時間が交差する最も右側の点におけるθの値である。必要な伝送容量（θ＝０．８６１）が上限値（θ＝１）より小さい値となっていることから、提案したスケジューリングアルゴリズムはキュー間の最大配信時間の差を有効に利用して（容量に関して）ゲインを得ているということができる。
【００４５】
【発明の効果】
以上説明したように、本発明によれば、一つの網内の複数のＩＳＰに対する課金処理を行うことができる。また、一つの網内の複数のＩＳＰにおけるパケットのサービスクラス毎の品質を保証することができる。
【図面の簡単な説明】
【図１】ＩＳＣ間に複数のＩＳＰが接続された通信網の構成を示す図。
【図２】品質クラス毎に分かれたキューのオリジナルシステムおよびその参照システムを示す図。
【図３】本発明実施例のキュー選択スケジューリングアルゴリズムを示す図。
【図４】最大配信時間の目標値ｔｉとシミュレーションから得られたｉ番目のキューの実際の配信時間ｔｉ’（ｉ＝１、…、１０）を比較した図。
【図５】各キュー群の最大配信時間の最大値をθの各値に対して示した図。
【符号の説明】
１  課金処理部
Ａ  オリジナルシステム
Ｂ  参照システム
【図１】
0003607522.tif 000011
【図２】
0003607522.tif 000012
【図３】
0003607522.tif 000013
【図４】
0003607522.tif 000014
【図５】
0003607522.tif 000015