(57)【要約】ＶＰＮ間のトラヒック干渉を制御するパケットスケジューリング方式を提供する。パケットスケジューリング方式は、入力されたデータパケットを振り分けるキューイング先判定部５と、複数の特定のグループごとに、キューイング先判定部５によって振り分けられたデータパケットを品質クラス毎に蓄積する複数のキューイング部７−１〜７−ｎと、読み出すデータパケットを制御する読み出し制御部８を有する第１段目のスケジューリング部６−１〜６−ｍと、上記第１段目のスケジューリング部６−１〜６−ｍを複数の特定のグループごとに複数有し、上記複数の特定グループごとの第１段目のスケジューリング部から読み出すデータパケットを制御する読み出し制御部１１を有する第２段目のスケジューリング部とを有する。
2003098883.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも一つの入力インタフェースから入力するデータパケットを少なくとも一つの出力インタフェースに振り分けるパケットスケジューリング方式において、
上記入力インタフェースからデータパケットを入力し、入力したデータパケットを振り分けるキューイング先判定部と、
上記キューイング先判定部から振り分けられたデータパケットを入力し、入力したデータパケットを蓄積し、蓄積したデータパケットの読み出しを制御する複数の第１のスケジューリング部と、
上記複数の第１のスケジューリング部が読み出した複数のデータパケットを入力し、入力した複数のデータパケットから一つのデータパケットを選択し、選択したデータパケットを上記出力インタフェースへ出力する第２のスケジューリング部と
を備えることを特徴とするパケットスケジューリング方式。
【請求項２】
上記複数の第１のスケジューリング部は、ネットワークを構成する複数のグループに対応づけられて備えられ、
上記キューイング先判定部は、上記複数のグループに関して上記データパケットを判定し、判定した結果に基づいて、複数の第１のスケジューリング部から一つの第１のスケジューリング部を選択し、選択した一つの第１のスケジューリング部へ上記データパケットを振り分けることを特徴とする請求項１記載のパケットスケジューリング方式。
【請求項３】
上記複数の第１のスケジューリング部の各第１のスケジューリング部は、データパケットを蓄積する複数のキューイング部を、データパケットの品質の数に対応させて備え、
上記キューイング先判定部は、上記品質に関して上記データパケットを判定し、判定した結果に基づいて、複数のキューイング部から一つのキューイング部を選択し、選択した一つのキューイング部へ上記データパケットを振り分けることを特徴とする請求項１記載のパケットスケジューリング方式。
【請求項４】
上記複数の第１のスケジューリング部それぞれは、
複数のキューイング部から一つのキューイング部を選択し、選択したキューイング部に蓄積したデータパケットを読み出す指示を出力する第１の読み出し制御部と、
上記第１の読み出し制御部から指示を入力し、入力した指示に基づいて、上記一つのキューイング部に蓄積したデータパケットを選択し、選択したデータパケットを上記第２のスケジューリング部へ読み出す選択部と
を備えることを特徴とする請求項３記載のパケットスケジューリング方式。
【請求項５】
上記第１の読み出し制御部は、複数のキューイング部を順番に選択する制御と、複数のキューイング部それぞれに重みを設定し、設定した重みに基づいて一つのキューイング部を選択する制御と、上記複数のキューイング部それぞれの蓄積状況に基づいて一つのキューイング部を選択する制御とのうち、少なくともいずれか一つの制御を用いて、一つのキューイング部を選択することを特徴とする請求項４記載のパケットスケジューリング方式。
【請求項６】
上記複数の第１のスケジューリング部それぞれは、さらに、上記複数のキューイング部から一つのキューイング部を選択する場合に、上記複数のキューイング部毎に割り当てる帯域を定める帯域割当情報を生成する第１のシェーピング部を備え、
上記第１の読み出し制御部は、上記第１のシェーピング部が生成した帯域割当情報に従って、上記一つのキューイング部を選択することを特徴とする請求項４記載のパケットスケジューリング方式。
【請求項７】
上記複数の第１のスケジューリング部は、ネットワークを構成する複数のグループに対応させて備えられ、
上記複数の第１のスケジューリング部それぞれは、データパケットを蓄積する複数のキューイング部を、データパケットの品質の数に対応させて備え、
上記キューイング先判定部は、上記複数のグループと上記品質とに関して、上記データパケットを判定し、判定した結果に基づいて、複数の第１のスケジューリング部から一つの第１のスケジューリング部を選択し、選択した一つの第１のスケジューリング部へ上記データパケットを振り分けることを特徴とする請求項１記載のパケットスケジューリング方式。
【請求項８】
少なくとも一つの入力インタフェースから入力するデータパケットを少なくとも一つの出力インタフェースに振り分けるパケットスケジューリング方式において、
上記入力インタフェースからデータパケットを入力し、入力したデータパケットを振り分けるキューイング先判定部と、
上記キューイング先判定部から振り分けられたデータパケットを入力し、入力したデータパケットを蓄積し、蓄積したデータパケットの読み出しを制御する複数の第１のスケジューリング部と、
上記複数の第１のスケジューリング部から読み出された複数のデータパケットを入力し、入力した複数のデータパケットの出力を制御する複数の第２のスケジューリング部と、
上記複数の第２のスケジューリング部それぞれから一つずつ出力された複数のデータパケットを入力し、入力した複数のデータパケットから一つのデータパケットを選択し、選択したデータパケットを上記出力インタフェースへ出力する競合制御部と
を備えることを特徴とするパケットスケジューリング方式。
【請求項９】
上記複数の第１のスケジューリング部それぞれは、データパケットを蓄積する複数のキューイング部を、データパケットの品質の数に対応させて備え、
上記キューイング先判定部は、上記品質に関して上記データパケットを判定し、判定した結果に基づいて、複数のキューイング部から一つのキューイング部を選択し、選択した一つのキューイング部へ上記データパケットを振り分けることを特徴とする請求項８記載のパケットスケジューリング方式。
【請求項１０】
上記出力インタフェースは、複数のポートを有し、
上記複数の第１のスケジューリング部は、ネットワークを構成する複数のグループに対応させて備えられ、
上記複数の第２のスケジューリング部は、上記複数のポートに対応させて備えられるとともに、上記第１のスケジューリング部と関連づけられ、
上記キューイング先判定部は、上記データパケットを上記複数のグループと上記複数のポートとに基づいて判定し、判定した結果に基づいて、複数の第１のスケジューリング部から一つの第１のスケジューリング部を選択し、選択した一つの第１のスケジューリング部へ上記データパケットを振り分けることを特徴とする請求項８記載のパケットスケジューリング方式。
【請求項１１】
上記複数の第２のスケジューリング部それぞれは、
上記複数の第１のスケジューリング部から一つの第１のスケジューリング部を選択する場合に、上記複数の第１のスケジューリング部毎に割り当てる帯域を定める帯域割当情報を生成する第２のシェーピング部と、
上記第２のシェーピング部が生成した帯域割当情報に従って、上記複数の第１のスケジューリング部から一つの第１のスケジューリング部を選択し、選択した第１のスケジューリング部から入力したデータパケットを出力することを指示する第２の読み出し制御部と、
上記第２の読み出し制御部から指示を入力し、入力した指示に基づいて、選択した第１のスケジューリング部から入力したデータパケットを上記競合制御部へ出力する選択部と
を備えることを特徴とする請求項８記載のパケットスケジューリング方式。
【請求項１２】
上記出力インタフェースは、複数のポートを有し、
上記複数の第１のスケジューリング部は、ネットワークを構成する複数のグループに対応させて備えられるとともに、上記複数の第１のスケジューリング部それぞれは、データパケットを蓄積する複数のキューイング部を、データパケットの複数の品質の数に対応させて有し、
上記複数の第２のスケジューリング部は、上記複数のポートに対応させて備えられるとともに、上記第１のスケジューリング部と関連づけられ、
上記キューイング先判定部は、上記データパケットを、上記複数の品質と上記複数のグループと上記複数のポートとに関して判定し、判定した結果に基づいて、複数の第１のスケジューリング部から一つの第１のスケジューリング部を選択し、選択した一つの第１のスケジューリング部へ上記データパケットを振り分けることを特徴とする請求項８記載のパケットスケジューリング方式。
【請求項１３】
データパケットの品質に基づいてスケジューリングする複数の第１のスケジューリング部と、ネットワークを構成する複数のグループに基づいてスケジューリングする第２のスケジューリング部とを介して、少なくとも一つの入力インタフェースから入力するデータパケットを、少なくとも一つの出力インタフェースに振り分けるパケットスケジューリング方法において、
上記入力インタフェースからデータパケットを入力し、
入力したデータパケットを上記データパケットの品質とグループとに基づいて判別し、
判別した結果に基づいて、上記データパケットを上記複数の第１のスケジューリング部のいずれかへ振り分け、
振り分けられたデータパケットを上記複数の第１のスケジューリング部へ蓄積し、
蓄積したデータパケットの読み出しを品質に基づいて判別し、
判別した結果に基づいて上記複数の第１のスケジューリング部から上記第２のスケジューリング部へ上記データパケットを読み出し、
上記第２のスケジューリング部へ入力した複数のデータパケットを上記複数のグループに関して判別し、
判別した結果に基づいて上記複数のデータパケットから一つのデータパケットを選択し、
選択したデータパケットを上記出力インタフェースへ出力することを特徴とするパケットスケジューリング方法。
【発明の詳細な説明】
技術分野
本発明は、パケット交換装置に関し、本パケット交換装置によって提供される各種サービスに対応した所望のトラヒック特性を実現するための技術に関する。
特に、ＶＰＮ（Ｖｉｒｔｕａｌ  Ｐｒｉｖａｔｅ  Ｎｅｔｗｏｒｋ）サービスのように特定のグループに対するサービスにおいて、ＶＰＮのように特定のグループ間でのトラヒックの干渉をなくし、かつ、複数の異なった品質クラスのトラヒックを効果的に扱うことによって、その品質を向上させるためのパケットスケジューリング技術に関するものである。
背景技術
図７は、例えば、従来のパケットスケジューリング方式の構成図の一例である。
図７のパケットスケジューリング方式は、キューイング先判定部１、キューイング部２−１〜２−ｎ、読み出し制御部３、選択部（ＳＥＬ）４とを備える。
キューイング先判定部１は、データパケットの品質クラスを振り分ける。
キューイング部２−１〜２−ｎは、キューイング先判定部１によって振り分けられたデータパケットをｎ個の品質クラス毎に蓄積する。
読み出し制御部３は、ｎ個のキューイング部２−１〜２−ｎからデータパケットを各品質クラスの優先度に従って読み出す。
選択部４は、読み出し制御部３の制御に従ったｎ個のキューイング部２−１〜２−ｎのいずれかから出力するデータパケットを選択する。
品質クラスは、ｎ個（ｎは任意の整数）あることを前提とする。
次に、動作について説明する。
キューイング先判定部１は、データパケットを入力し、入力したデータパケットの品質クラスを識別し、ｎ個の品質クラス毎に用意されたキューイング部２−１〜２−ｎに振り分ける。
ｎ個の品質クラス毎に用意されたキューイング部２−１〜２−ｎは、キューイング先判定部１によって振り分けられたデータパケットを蓄積する。
読み出し制御部３は、ｎ個の品質クラス毎に用意されたキューイング部２−１〜２−ｎにおけるデータパケットの蓄積状況と、各品質クラスの優先度とに従って、ｎ個の品質クラス毎に用意された複数のキューイング部２−１〜２−ｎから読み出しを行う一つのキューイング部を判定し、蓄積されたデータパケットの読み出し指示をキューイング部へ行う。同時に、読み出し制御部３は、選択部４へ選択指示を行い、データパケットを出力する。
このように、キューイング先判定部１で、その品質クラスを振り分け、ｎ個の品質クラス毎に用意された複数のキューイング部２−１〜２−ｎで蓄積し、読み出し制御部３で、その蓄積状況と各品質クラスの優先度に従って読み出し、選択部４で選択することによって、入力した複数のデータパケットに対して、各品質クラスの優先度に従ったデータパケットを出力することが可能となる。
従来のパケットスケジューリング方式は、上記のように構成されており、ネットワークがＶＰＮサービスを行う場合、同一インタフェースに複数のＶＰＮを収容すると、各ＶＰＮのトラヒックを分けずに、インタフェース単位に各品質クラスに従ったスケジューリングを行っていた。このため、各品質クラスに従ったパケット転送は可能になるが、ＶＰＮ間のトラヒック干渉を制御する手段がなく、ＶＰＮ間でトラヒックの干渉が発生してしまう問題点があった。
そこで、この発明は、複数のグループに対するサービス（例えば、ＶＰＮサービス）において、パケットスケジューリング方式及び方法の品質を向上させることを目的とする。
特に、特定の複数のグループ間（例えば、複数のＶＰＮ間）でのトラヒックの干渉をなくし、各グループ内で複数の異なった品質クラスのトラヒックを効果的に扱うことによって、パケットスケジューリング方式及び方法の品質を向上させることを目的とする。
発明の開示
この発明に係るパケットスケジューリング方式は、少なくとも一つの入力インタフェースから入力するデータパケットを少なくとも一つの出力インタフェースに振り分けるパケットスケジューリング方式において、
上記入力インタフェースからデータパケットを入力し、入力したデータパケットを振り分けるキューイング先判定部と、
上記キューイング先判定部から振り分けられたデータパケットを入力し、入力したデータパケットを蓄積し、蓄積したデータパケットの読み出しを制御する複数の第１のスケジューリング部と、
上記複数の第１のスケジューリング部が読み出した複数のデータパケットを入力し、入力した複数のデータパケットから一つのデータパケットを選択し、選択したデータパケットを上記出力インタフェースへ出力する第２のスケジューリング部と
を備えることを特徴とする。
上記複数の第１のスケジューリング部は、ネットワークを構成する複数のグループに対応づけられて備えられ、
上記キューイング先判定部は、上記複数のグループに関して上記データパケットを判定し、判定した結果に基づいて、複数の第１のスケジューリング部から一つの第１のスケジューリング部を選択し、選択した一つの第１のスケジューリング部へ上記データパケットを振り分けることを特徴とする。
上記複数の第１のスケジューリング部の各第１のスケジューリング部は、データパケットを蓄積する複数のキューイング部を、データパケットの品質の数に対応させて備え、
上記キューイング先判定部は、上記品質に関して上記データパケットを判定し、判定した結果に基づいて、複数のキューイング部から一つのキューイング部を選択し、選択した一つのキューイング部へ上記データパケットを振り分けることを特徴とする。
上記複数の第１のスケジューリング部それぞれは、
複数のキューイング部から一つのキューイング部を選択し、選択したキューイング部に蓄積したデータパケットを読み出す指示を出力する第１の読み出し制御部と、
上記第１の読み出し制御部から指示を入力し、入力した指示に基づいて、上記一つのキューイング部に蓄積したデータパケットを選択し、選択したデータパケットを上記第２のスケジューリング部へ読み出す選択部と
を備えることを特徴とする。
上記第１の読み出し制御部は、複数のキューイング部を順番に選択する制御と、複数のキューイング部それぞれに重みを設定し、設定した重みに基づいて一つのキューイング部を選択する制御と、上記複数のキューイング部それぞれの蓄積状況に基づいて一つのキューイング部を選択する制御とのうち、少なくともいずれか一つの制御を用いて、一つのキューイング部を選択することを特徴とする。
上記複数の第１のスケジューリング部それぞれは、さらに、上記複数のキューイング部から一つのキューイング部を選択する場合に、上記複数のキューイング部毎に割り当てる帯域を定める帯域割当情報を生成する第１のシェーピング部を備え、
上記第１の読み出し制御部は、上記第１のシェーピング部が生成した帯域割当情報に従って、上記一つのキューイング部を選択することを特徴とする。
上記複数の第１のスケジューリング部は、ネットワークを構成する複数のグループに対応させて備えられ、
上記複数の第１のスケジューリング部それぞれは、データパケットを蓄積する複数のキューイング部を、データパケットの品質の数に対応させて備え、
上記キューイング先判定部は、上記複数のグループと上記品質とに関して、上記データパケットを判定し、判定した結果に基づいて、複数の第１のスケジューリング部から一つの第１のスケジューリング部を選択し、選択した一つの第１のスケジューリング部へ上記データパケットを振り分けることを特徴とする。
この発明に係るパケットスケジューリング方式は、少なくとも一つの入力インタフェースから入力するデータパケットを少なくとも一つの出力インタフェースに振り分けるパケットスケジューリング方式において、
上記入力インタフェースからデータパケットを入力し、入力したデータパケットを振り分けるキューイング先判定部と、
上記キューイング先判定部から振り分けられたデータパケットを入力し、入力したデータパケットを蓄積し、蓄積したデータパケットの読み出しを制御する複数の第１のスケジューリング部と、
上記複数の第１のスケジューリング部から読み出された複数のデータパケットを入力し、入力した複数のデータパケットの出力を制御する複数の第２のスケジューリング部と、
上記複数の第２のスケジューリング部それぞれから一つずつ出力された複数のデータパケットを入力し、入力した複数のデータパケットから一つのデータパケットを選択し、選択したデータパケットを上記出力インタフェースへ出力する競合制御部と
を備えることを特徴とする。
上記複数の第１のスケジューリング部それぞれは、データパケットを蓄積する複数のキューイング部を、データパケットの品質の数に対応させて備え、
上記キューイング先判定部は、上記品質に関して上記データパケットを判定し、判定した結果に基づいて、複数のキューイング部から一つのキューイング部を選択し、選択した一つのキューイング部へ上記データパケットを振り分けることを特徴とする。
上記出力インタフェースは、複数のポートを有し、
上記複数の第１のスケジューリング部は、ネットワークを構成する複数のグループに対応させて備えられ、
上記複数の第２のスケジューリング部は、上記複数のポートに対応させて備えられるとともに、上記第１のスケジューリング部と関連づけられ、
上記キューイング先判定部は、上記データパケットを上記複数のグループと上記複数のポートとに基づいて判定し、判定した結果に基づいて、複数の第１のスケジューリング部から一つの第１のスケジューリング部を選択し、選択した一つの第１のスケジューリング部へ上記データパケットを振り分けることを特徴とする。
上記複数の第２のスケジューリング部それぞれは、
上記複数の第１のスケジューリング部から一つの第１のスケジューリング部を選択する場合に、上記複数の第１のスケジューリング部毎に割り当てる帯域を定める帯域割当情報を生成する第２のシェーピング部と、
上記第２のシェーピング部が生成した帯域割当情報に従って、上記複数の第１のスケジューリング部から一つの第１のスケジューリング部を選択し、選択した第１のスケジューリング部から入力したデータパケットを出力することを指示する第２の読み出し制御部と、
上記第２の読み出し制御部から指示を入力し、入力した指示に基づいて、選択した第１のスケジューリング部から入力したデータパケットを上記競合制御部へ出力する選択部と
を備えることを特徴とする。
上記出力インタフェースは、複数のポートを有し、
上記複数の第１のスケジューリング部は、ネットワークを構成する複数のグループに対応させて備えられるとともに、上記複数の第１のスケジューリング部それぞれは、データパケットを蓄積する複数のキューイング部を、データパケットの複数の品質の数に対応させて有し、
上記複数の第２のスケジューリング部は、上記複数のポートに対応させて備えられるとともに、上記第１のスケジューリング部と関連づけられ、
上記キューイング先判定部は、上記データパケットを、上記複数の品質と上記複数のグループと上記複数のポートとに関して判定し、判定した結果に基づいて、複数の第１のスケジューリング部から一つの第１のスケジューリング部を選択し、選択した一つの第１のスケジューリング部へ上記データパケットを振り分けることを特徴とする。
この発明に係るパケットスケジューリング方法は、データパケットの品質に基づいてスケジューリングする複数の第１のスケジューリング部と、ネットワークを構成する複数のグループに基づいてスケジューリングする第２のスケジューリング部とを介して、少なくとも一つの入力インタフェースから入力するデータパケットを、少なくとも一つの出力インタフェースに振り分けるパケットスケジューリング方法において、
上記入力インタフェースからデータパケットを入力し、
入力したデータパケットを上記データパケットの品質とグループとに基づいて判別し、
判別した結果に基づいて、上記データパケットを上記複数の第１のスケジューリング部のいずれかへ振り分け、
振り分けられたデータパケットを上記複数の第１のスケジューリング部へ蓄積し、
蓄積したデータパケットの読み出しを品質に基づいて判別し、
判別した結果に基づいて上記複数の第１のスケジューリング部から上記第２のスケジューリング部へ上記データパケットを読み出し、
上記第２のスケジューリング部へ入力した複数のデータパケットを上記複数のグループに関して判別し、
判別した結果に基づいて上記複数のデータパケットから一つのデータパケットを選択し、
選択したデータパケットを上記出力インタフェースへ出力することを特徴とする。
発明を実施するための最良の形態
実施の形態１．
以下、この発明の実施の形態１を図を用いて説明する。
図１は、実施の形態１のパケットスケジューリング方式の一例を示す図である。
図１のパケットスケジューリング方式は、キューイング先判定部５、第１段目のスケジューリング部６−１〜６−ｍ、キューイング部７−１〜７−ｎ、読み出し制御部８、選択部９、第２段目のスケジューリング部１０、読み出し制御部１１、選択部１２とを備える。上記パケットスケジューリング方式は、パケット交換装置に適用される方式である。
第１段目のスケジューリング部は、第１のスケジューリング部ともいう。
第２段目のスケジューリング部は、第２のスケジューリング部ともいう。
読み出し制御部８は、第１の読み出し制御部ともいう。
また、読み出し制御部１１は、第２の読み出し制御部ともいう。
なお、図１には示していないが、データパケットは、一つ又は複数の入力インタフェース（入力インタフェース部）から入力する。また、入力したデータパケットは、一つ又は複数の出力インタフェース（出力インタフェース部）に振り分けられる。以下の説明では、複数の出力インタフェースのうち、任意の一つの出力インタフェースに、データパケットをスケジューリングする場合を説明する。
入力インタフェースは、キューイング先制御部５へデータパケットを入力するインタフェースである。出力インタフェースは、このスケジューリング方式（実施の形態１では、選択部９）からデータパケットを出力するインタフェースである。一例としては、ネットワークとスケジューリング方式とを接続する交換器のインタフェース部分である。
また、入力するデータパケットは、特定の複数のグループ（例えば、ＶＮＰ（仮想閉域網、仮想私設網）に設定されるグループ）間でスケジューリングされる。特定の複数のグループは、所定の利用者が利用するネットワークを構成するグループである。
また、上記データパケットは、各グループ内で品質クラス毎にスケジューリングされる。「品質クラス」は、単に、「品質」ということも有る。品質クラスは、品質のクラス（レベル）を示す。例えば、サービスごとに要求される遅延や廃棄率等の品質のクラスがある。
以下、複数のグループの数をｍ、品質クラスの数をｎとして説明する。ｍ、ｎは、任意の整数である。
キューイング先判定部５は、データパケットを振り分ける。
第１段目のスケジューリング部６−１〜６−ｍは、ｍ個の特定のグループごとに備えられ、ｎ個の品質クラスに関するスケジューリングを行う。
キューイング部７−１〜７−ｎは、第１段目のスケジューリング部６−１〜６−ｍにおいて、キューイング先判定部５によって振り分けられたデータパケットをｎ個の品質クラス毎に蓄積する。
読み出し制御部８は、第１段目のスケジューリング部６−１〜６−ｍにおいて、品質クラス毎のｎ個のキューイング部７−１〜７−ｎからデータパケットを各品質クラスの優先度に従った読み出しを行う。
選択部９は、第１段目のスケジューリング部６−１〜６−ｍそれぞれにおいて、読み出し制御部８の制御に従ってｎ個のキューイング部７−１〜７−ｎから出力するデータパケットを選択し、各第１段目のスケジューリング部６−１〜６−ｍから出力するデータパケットとする。
第２段目のスケジューリング部１０は、第１段目のスケジューリング部６−１〜６−ｍの出力に対して、ｍ個の特定のグループに関するスケジューリングを行い、データパケットを出力する。
読み出し制御部１１は、第２段目のスケジューリング部１０において、ｍ個の第１段目のスケジューリング部６−１〜６−ｍの出力を、ｍ個の特定のグループごとの帯域割り当てに従った読み出しを行う。
選択部１２は、第２段目のスケジューリング部１０において、読み出し制御部１１の制御に従ってｍ個の第１段目のスケジューリング部６−１〜６−ｍから出力されるデータパケットのうちの一つを選択し、選択したデータパケットを出力する。
次に、動作を図２を用いて説明する。
図２は、実施の形態１のパケットスケジューリング方式（方法）の動作の一例を示すフローチャート図である。
キューイング先判定部５は、データパケットを入力する（Ｓ１１）。入力したデータパケットについて、ｍ個のグループのいずれに属するか、及び、ｎ個の品質クラスのいずれに属するかとを識別（判別）する（Ｓ１２）。
キューイング先判定部５は、識別した結果に基づいて、ｍ個の第１段目のスケジューリング部６−１〜６−ｍのいずれかを選択し（Ｓ１３）、更に、選択した第１段目のスケジューリング部において、入力したデータパケットをｎ個の品質クラス毎に用意されたキューイング部７−１〜７−ｎへ振り分ける（Ｓ１４）。第１段目のスケジューリング部６−１〜６−ｍにおいて、ｎ個の品質クラス毎に用意されたキューイング部７−１〜７−ｎは、キューイング先判定部１によって振り分けられたデータパケットを蓄積する（Ｓ１５）。
読み出し制御部８は、ｎ個の品質クラス毎に用意されたキューイング部７−１〜７−ｎそれぞれにおけるデータパケットの蓄積状況と各品質クラスの優先度に従って、ｎ個の品質クラス毎に用意されたキューイング部７−１〜７−ｎのなかから読み出しを行うキューイング部を選択（判定）する。次に、読み出し制御部８は、キューイング部７−１〜７−ｎの中から選択したキューイング部７へ、蓄積されたデータパケットの読み出し指示を行う。同時に、読み出し制御部８は、選択部９へ、上記選択したキューイング部を選択する選択指示を行い、ｍ個のグループごとにデータパケットを出力する（Ｓ１６）。
なお、キューイング部への読み出し指示は、選択指示を入力した選択部９が行ってもよい。
次に、第２段目のスケジューリング部１０において、以下の読み出し制御を行なう。第２段目のスケジューリング部１０に配置された読み出し制御部１１は、ｍ個の第１段目のスケジューリング部６−１〜６−ｍの読み出し制御部８とリンクし、ｍ個のグループごとの帯域割り当てに従った読み出し制御を行う。同時に、読み出し制御部１１は、選択部１２へ、ｍ個の第１段目のスケジューリング部６−１〜６−ｍから選択した一つの第１段目のスケジューリング部のデータパケットを選択する選択指示を行う（Ｓ１７）。予め、第１段目のスケジュール部６−１〜６−ｍは、帯域を、ｍ個のグループごとに定義（設定）して帯域制御情報として保持する。このようにして、ｍ個の第１段目のスケジューリング部６−１〜６−ｍからデータパケットを出力する一つの第１段目のスケジューリング部を選択し、データパケットを出力する（Ｓ１８）。
この実施の形態によれば、ＶＰＮサービスのように複数のグループに対するパケットスケジューリングにおいて、グループ単位にスケジュールを行うスケジューリング部（第１段目のスケジューリング部）を有し、更に、出力インタフェースに対し、複数のグループ間のスケジューリングを行うスケジューリング部（第２段目のスケジューリング部）を有する。これによって、一つの出力インタフェースを用いて複数のグループを収容した場合においても、グループごとの帯域割り当てに従った読み出しが可能となる。また、グループごとの帯域保証が可能となる。
また、グループ単位のスケジューリングを行うスケジューリング部は、品質クラスに対応したスケジューリングを行うことにより、グループ毎にアプリケーションに対応した優先転送や帯域確保が可能となる。
このように、この実施の形態によれば、複数のグループ間でのトラヒックの干渉をなくし、かつ、各グループ内で複数の異なった品質クラスのトラヒックを効果的に扱いことができる。従って、品質向上を簡易に得られる効果がある。
以上のように、実施の形態１のパケットスケジューリング方式及び方法は、一つ又は複数の入力インタフェースから入力されたデータパケットを、一つ又は複数の出力インタフェースに振り分けるパケット交換装置に適用され、下記の（１）〜（３）を有する。
（１）上記複数の入力インタフェースから入力されたデータパケットを振り分けるキューイング先判定部。
（２）複数の特定のグループごとに、キューイング先判定部によって振り分けられたデータパケットを蓄積する複数のキューイング部と、複数のキューイング部から一つのデータパケットを読み出す読み出し制御部とを有する第１段目のスケジューリング部。
（３）上記第１段目のスケジューリング部を複数の特定のグループごとに複数有し、上記複数の特定グループごとの第１段目のスケジューリング部からデータパケットを読み出す読み出し制御部を有する第２段目のスケジューリング部。
また、以下を特徴とする。
複数の特定のグループは、ＶＰＮサービスに代表される企業グループや、ユーザのグループや、ネットワークのサービスグループ等に対応させる。
上記第１段目のスケジューリング部のキューイング部は、あらかじめデータパケットに付与された優先クラスや、アプリケーションや、ユーザや、企業及びその組み合わせ等に対応して備えられる。
上記第１段目のスケジューリング部の読み出し制御部は、優先制御や、単純にキューを順番に読み出すＲＲ（Ｒｏｕｎｄ  Ｒｏｂｉｎ）制御や、キューに重みをつけその比率に従って読み出すＷＲＲ（Ｗｅｉｇｈｔｅｄ  Ｒｏｕｎｄ  Ｒｏｂｉｎ）制御や、ＷＦＱ（Ｗｅｉｇｈｔｅｄ  Ｆａｉｒ  Ｑｕｅｉｎｇ）制御や、その組み合わせ等によって読み出しを制御する。
上記第２段目のスケジューリング部の読み出し制御部は、上記第１段目のスケジューリング部の読み出し制御部と同様に、優先制御や、単純にキューを順番に読み出すＲＲ制御や、キューに重みをつけその比率に従って読み出すＷＲＲ制御や、ＷＦＱ制御や、その組み合わせ等に対応させ、あらかじめデータパケットに付与された優先クラスや、アプリケーションや、ユーザや、企業及びその組み合わせ等に対応して備えられる。
上記キューイング先判定部は、上記グループとグループごとのキューイング部の組み合わせに対応してデータパケットを振り分ける。
実施の形態２．
以下、この発明の実施の形態２を図を用いて説明する。
図３は、実施の形態２のパケットスケジューリング方式の一例を示す図である。
図３のパケットスケジューリング方式は、図１のパケットスケジューリング方式にシェーピング部１３を加えた構成である。
図３において、図１と同じ符号を付けた構成要素は、実施の形態１と同様であるため、説明を省略する。
シェーピング部１３は、第１段目のスケジューリング部６−１〜６−ｍ内に配置され、読み出し制御部８とリンクして、データパケットの読み出し帯域に制限を加える。予め、シェーピング部１３は、帯域を、ｍ個のグループごとに定義（設定）して帯域制御情報として保持する。
次に、動作について図４を用いて説明する。
図４は、実施の形態２のパケットスケジューリング方式（方法）の動作の一例を示すフローチャート図である。図２と同じステップ番号（Ｓｘｘ）を付した動作は、実施の形態１で説明した動作と同様である。
キューイング先判定部５は、データパケットを入力する（Ｓ１１）。入力したデータパケットについて、ｍ個のグループ、及び、品質クラスとを識別（判別）する（Ｓ１２）。
キューイング先判定部５は、識別した結果に基づいて、ｍ個の第１段目のスケジューリング部６−１〜６−ｍのいずれかを選択し（Ｓ１３）、更に、選択した第１段目のスケジューリング部において、入力したデータパケットをｎ個の品質クラス毎に用意されたキューイング部７−１〜７−ｎへ振り分ける（Ｓ１４）。第１段目のスケジューリング部６−１〜６−ｍにおいて、ｎ個の品質クラス毎に用意されたキューイング部７−１〜７−ｎは、キューイング先判定部１によって振り分けられたデータパケットを蓄積する（Ｓ１５）。
シェーピング部１３は、グループ毎の読み出し帯域割当に関する帯域割当情報（読み出し帯域割当情報）を読み出し制御部８へ通知する（Ｓ２１）。帯域割当情報は、帯域を制限することから、帯域制限情報ともいう。
読み出し制御部８は、ｎ個の品質クラス毎に用意されたキューイング部７−１〜７−ｎそれぞれにおけるデータパケットの蓄積状況と、各品質クラスの優先度と、上記シェーピング部１３から通知された帯域割当情報とに従って、ｎ個の品質クラス毎に用意されたキューイング部７−１〜７−ｎのなかから読み出しを行うキューイング部を選択（判定）する。次に、読み出し制御部８は、キューイング部７−１〜７−ｎの中から選択したキューイング部７へ、蓄積されたデータパケットの読み出し指示を行う。同時に、読み出し制御部８は、選択部９へ、上記選択したキューイング部を選択する選択指示を行い、ｍ個のグループごとにデータパケットを出力する（Ｓ１６）。
次に、第２段目のスケジューリング部１０において、以下の読み出し制御を行なう。第２段目のスケジューリング部１０に配置された読み出し制御部１１は、ｍ個の第１段目のスケジューリング部６−１〜６−ｍの読み出し制御部８とリンクし、ｍ個のグループごとの帯域割り当てに従った読み出し制御を行う。同時に、読み出し制御部１１は、選択部１２へ、ｍ個の第１段目のスケジューリング部６−１〜６−ｍから選択した一つの第１段目のスケジューリング部のデータパケットを選択する選択指示を行う（Ｓ１７）。このようにして、ｍ個の第１段目のスケジューリング部６−１〜６−ｍからデータパケットを出力する一つの第１段目のスケジューリング部を選択し、データパケットを出力する（Ｓ１８）。
この実施の形態によれば、ＶＰＮサービスのように複数のグループに対するパケットスケジューリングにおいて、グループ単位にスケジュールを行うスケジューリング部（第１段目のスケジューリング部）を有し、更に、出力インタフェースに対し、複数のグループ間のスケジューリングを行うスケジューリング部（第２段目のスケジューリング部）を有する。これによって、一つの出力インタフェースを用いて複数のグループを収容した場合においても、グループごとの帯域割り当てに従った読み出しが可能となる。また、グループごとの帯域保証が可能となる。
また、グループ単位のスケジューリングを行うスケジューリング部は、品質クラスに対応したスケジューリングを行うことにより、グループ毎にアプリケーションに対応した優先転送や帯域確保が可能となる。
さらに、グループ単位のスケジューリングを行うスケジューリング部にシェーピング機能を備えることによって、グループごとの出力帯域に制限を加えたり、データパケットのバースト性を平準化することが可能となる。
このように、この実施の形態によれば、複数のグループ間でのトラヒックの干渉をなくし、かつ、各グループ内で複数の異なった品質クラスのトラヒックを効果的に扱うことができる。従って、品質向上を簡易に得られる効果がある。
以上のように、実施の形態２のパケットスケジューリング方式は、一つ又は複数の入力インタフェースから入力されたデータパケットを、一つ又は複数の出力インタフェースに振り分けるパケット交換装置に適用され、下記の（１）〜（３）を有する。
（１）上記複数の入力インタフェースから入力されたデータパケットを振り分けるキューイング先判定部。
（２）複数の特定のグループごとに、キューイング先判定部によって振り分けられたデータパケットを蓄積する複数のキューイング部と、複数のキューイング部から一つのデータパケットを読み出す読み出し制御部と、読み出し制御部とリンクして、データパケットの読み出し帯域に制限を加えるシェーピング部とを有する第１段目のスケジューリング部。
（３）上記第１段目のスケジューリング部を複数の特定のグループごとに複数有し、上記複数の特定のグループごとの第１段目のスケジューリング部からデータパケットを読み出す読み出し制御部を有する第２段目のスケジューリング部。
実施の形態３．
以下、この発明の実施の形態３を図５を用いて説明する。
図５は、一つの出力インタフェースにｘ個のポートを有する場合のスケジューリング方式の一例を示した図である。
キューイング先判定部１６は、データパケットを入力し、入力したデータパケットを振り分ける。実施の形態１のキューイング先判定部５と異なる点は、ｍ個のグループと、ｎ個の品質クラスとに加え、ｘ個のポートを識別して、データパケットを振り分ける点である。
第１段目のスケジューリング部６−１−１〜６−ｘ−ｍは、ｘ個のポートそれぞれに含まれるｍ個のグループ毎に備えられ、品質クラスに関してグループごとにスケジューリングを行う。第１段目のスケジューリング部６−１−１〜６−ｘ−ｍは、実施の形態１の第１段目のスケジューリング部６−１〜６−ｍと同様の構成であり、ｘ個のポート毎に設置される点が異なる。図５では、第１段目のスケジューリング部６−１−１〜６−ｘ−ｍ内の構成は省略して示している。第１段目のスケジューリング部６−１−１〜６−ｘ−ｍは、ｍ×ｘ個備えられることになる。
第２段目のスケジューリング部１０−１〜１０−ｘは、ｘ個のポート毎に備えられ、第１段目のスケジューリング部６−ｘ−１〜６−ｘ−ｍの出力に対するスケジューリングを行う。
競合制御部１５は、ｘ個のポート毎に備えられた第２段目のスケジューリング部１０−１〜１０−ｘから出力されるデータパケットに対して、競合制御を行い、出力するデータパケットを選択し、選択したデータパケットを出力する。
ｘ個のポート毎に備えられた第２段目のスケジューリング部１０−１〜１０−ｘは、読み出し制御部１１、シェーピング部１４、選択部１２とを備える。
読み出し制御部１１は、ｍ個の第１段目のスケジューリング部６−１−１〜６−ｘ−ｍの出力を、ｍ個のグループごとの帯域割り当てに従った読み出しを行う。
シェーピング部１４は、読み出し制御部１１とリンクして、データパケットの読み出し帯域に制限を加える。
選択部１２は、読み出し制御部１１の制御に従ってｍ個の第１段目のスケジューリング部６−１−１〜６−ｘ−ｍから出力されるデータパケットのうちの一つを選択する。
次に、動作について図６を用いて説明する。
図６は、実施の形態３のパケットスケジューリング方式（方法）の動作の一例を示すフローチャート図である。図２と同じステップ番号（Ｓｘｘ）を付した動作は、実施の形態１で説明した動作と同様である。
キューイング先判定部１６は、データパケットを入力する（Ｓ１１）。入力したデータパケットについて、一つの出力インタフェースにおけるｘ個の出力ポートのいずれに属するか、ｍ個のグループのいずれに属するか、及び、ｎ個の品質クラスのいずれに属するかを識別する（Ｓ１２）。
キューイング先判定部１６は、識別した結果に基づいて、ｍ×ｘ個の第１段目のスケジューリング部６−１−１〜６−ｘ−ｍのいずれかを選択し（Ｓ１３）、入力したデータパケットを選択した第１段目のスケジューリング部へ振り分ける（Ｓ３１）。
また、実施の形態１と同様に、キューイング先判定部１６は、選択した第１段目のスケジューリング部へ振り分けたデータパケットを、更に、上記第１段目のスケジューリング部内のｎ個の品質クラス毎に用意されたキューイング部（図５では省略している）へ振り分ける（図２のＳ１４）。
キューイング部は、振り分けられたデータパケットを蓄積する（Ｓ１５）。
ｘ×ｍ個の第１段目のスケジューリング部６−１−１〜６−ｘ−ｍは、実施の形態１及び実施の形態２における第１段目のスケジューリング部６−１〜６−ｍと同じように動作し、ｍ個のグループ毎に品質クラスに従ってデータパケットを出力する（Ｓ１６）。
次に、一つの出力インタフェースにおけるｘ個の出力ポートそれぞれに対応している第２段目のスケジューリング部１０−１〜１０−ｘにおいて、まず、第１番目の出力ポート（ｘ＝１）に対応している第２段目のスケジューリング部１０−１の動作について説明する。
シェーピング部１４は、グループ毎の読み出し帯域割当に関する読み出し帯域割当情報（帯域割当情報）を第２段目のスケジューリング部１０−１の読み出し制限部１１へ通知する（Ｓ３２）。
読み出し制御部１１は、ｍ個の第１段目のスケジューリング部６−１−１〜６−１−ｍにおけるデータパケットの蓄積状況と、上記シェーピング部１４から通知された帯域割当情報とに従って、ｍ個の第１段目のスケジューリング部６−１−１〜６−１−ｍの中から読み出しを行なう第１段目のスケジューリング部を選択（判定）する。選択した第１番目のスケジューリング部からデータパケットを出力する。
すなわち、第１番目の出力ポート（ｘ＝１）に対応している第２段目のスケジューリング部１０−１の読み出し制御部１１は、シェーピング部１４から通知された帯域割当情報に従って、読み出し帯域に制限をかけるともに、ｍ個の第１段目のスケジューリング部６−１−１〜６−１−ｍの読み出し制御部とリンクし、ｍ個のグループごとの帯域割り当てに従った読み出し制御を行う。同時に、読み出し制御部１１は、選択部１２への選択指示を行い、ｍ個の第１段目のスケジューリング部６−１−１〜６−１−ｍからの出力を選択し、データパケットを出力する。
他のｘ個の出力ポートそれぞれに対応している第２段目のスケジューリング部１０−１〜１０−ｘも、上記における第１番目の出力ポート対応の第２段目のスケジューリング部１０−１の動作と同様である。
競合制御部１５は、ｘ個のポート毎の第２段目のスケジューリング部１０−１〜１０−ｘからのデータパケット出力に対して、競合制御を行い（Ｓ３３）、出力インタフェースの出力帯域に従ったデータパケットを出力する（Ｓ１８）。
この実施の形態によれば、ＶＰＮサービスのように複数のグループに対するパケットスケジューリングにおいて、グループ単位にスケジュールを行うスケジューリング部（第１段目のスケジューリング部）を有し、更に、出力インタフェースに対し、複数のグループ間のスケジューリングを行うスケジューリング部（第２段目のスケジューリング部）を有する。これによって、一つの出力インタフェースを用いて複数のグループを収容した場合においても、グループごとの帯域割り当てに従った読み出しが可能となる。また、グループごとの帯域保証が可能となる。
また、グループ単位のスケジューリングを行うスケジューリング部は、品質クラスに対応したスケジューリングを行うことにより、グループ毎にアプリケーションに対応した優先転送や帯域確保が可能となる。
更に、グループ単位のスケジューリングを行うスケジューリング部にシェーピング機能を備えることによって、グループごとの出力帯域に制限を加えたり、データパケットのバースト性を平準化することが可能となる。
このように、同一出力インタフェースに複数ポートを有するような場合においても、ＶＰＮのように複数のグループ間でのトラヒックの干渉をなくし、かつ、各グループ内で複数の異なった品質クラスのトラヒックを効果的に扱うことができる。従って、品質向上を簡易に得られる効果がある。
以上のように、実施の形態３のパケットスケジューリング方式は、複数の入力インタフェースから入力されたデータパケットを、複数の出力インタフェースに振り分けるパケット交換装置に適用される。実施の形態１、実施の形態２のパケットスケジューリング方式において、出力インタフェースに複数のポートを有するようなパケット交換装置に対応し、ポートごとに上記第１段目のスケジューリング部と第２段目のスケジューリング部とを有する。更に、第２段目のスケジューリング部に、読み出し制御部とリンクして、データパケットの読み出し帯域に制限を加えるシェーピング部を有する。第２段目のスケジューリング部は、ポートの出力帯域にシェーピングして出力するデータパケットを選択する。競合制御部は、ｍ個の第１段目のスケジューリング部が選択したｍ個の出力するデータパケットを競合制御して出力する。
実施の形態４．
上記実施の形態１から３においては、データパケットを出力するキューイング部を選択する場合に、読み出し制御部８は、データパケットの蓄積状況と品質クラスの優先度とに基づいて判定する場合を説明したが、これに限られるわけではない。読み出し制御部８は、品質クラスについて重み付けを行ない、重み付けを用いて判定してもよい。また、品質クラスの優先度と重み付けとを組み合わせて用いてもよい。その他の手段であってもかまわない。
また、読み出し制御部は、複数のキューイング部を順番に選択する制御（ＲＲ制御）や、複数のキューイング部それぞれに重みを設定し、設定した重みに基づいて一つのキューイング部を選択する制御（ＷＲＲ制御）や、ＷＦＱ制御等、あるいはこれらの組合せの制御を利用することも可能である。
実施の形態５．
上記実施の形態１から３では、品質クラスと、ＶＮＰに代表される複数のグループ間のトラヒックの干渉を防止することとに基づいてパケットをスケジューリングする場合を説明したが、これらに限られるわけではない。上記以外の要素に基づいて、パケットをスケジューリングする場合にも、図１、図３、図５に一例として示したパケットスケジューリング方式を適用することが可能である。
実施の形態６．
上記実施の形態１から実施の形態３では、複数の入力インタフェースからデータパケットを入力し、一つの出力インタフェースへデータパケットを出力する場合を一例として説明した。しかしながら、この発明のスケジューリング方式は、一つの入力インタフェースから一つの出力インタフェース、複数の入力インタフェースから複数の出力インタフェースへとデータパケットを中継する場合にも有効である。例えば、一つの入力インタフェースから一つの出力インタフェースへ中継する場合を考える。入力インタフェースのデータ転送容量が出力インタフェースのデータ転送容量より大きい場合は、データパケットをスケジューリングする必要があり、本スケジューリング方式を適用することは有効である。
産業上の利用可能性
この発明の好適な実施の形態によれば、品質クラスとデータ蓄積状況とによって、データパケットをスケジューリングすることができる。
また、複数のグループ毎に帯域を割当てて、データパケットをスケジューリングすることができる。
更に、パケットをスケジューリングする場合に発生するトラヒックの干渉を防止することができる。
また、グループ単位に品質クラス毎のキューを持ち、グループ単位のスケジューリングを行い、更に出力インタフェースに対し、ＶＰＮ間のスケジューリング（２段階のスケジューリング）を行うことにより、同一の出力インタフェースで複数のグループを収容し、ＶＰＮ毎の帯域保証及びＶＰＮ内でアプリケーションに対応した優先転送や帯域確保を行うことにより、パケットスケジューリング方式及び方法の品質を向上させることができる。
【図面の簡単な説明】
図１は、この発明の実施の形態１のパケットスケジューリング方式の一例を示す構成図である。
図２は、実施の形態１のパケットスケジューリング方式の動作の一例を示すフローチャート図である。
図３は、この発明の実施の形態２のパケットスケジューリング方式の一例を示す構成図である。
図４は、実施の形態２のパケットスケジューリング方式の動作の一例を示すフローチャート図である。
図５は、この発明の実施の形態３のパケットスケジューリング方式の一例を示す構成図である。
図６は、実施の形態３のパケットスケジューリング方式の動作の一例を示すフローチャート図である。
図７は、従来のパケットスケジューリング方式の一例を示す構成図である。
【図１】
2003098883.tif 000003
【図２】
2003098883.tif 000004
【図３】
2003098883.tif 000005
【図４】
2003098883.tif 000006
【図５】
2003098883.tif 000007
【図６】
2003098883.tif 000008
【図７】
2003098883.tif 000009
【国際調査報告】
2003098883.tif 000010
2003098883.tif 000011
2003098883.tif 000012
2003098883.tif 000013