JP2004201304A - 高速パケット網のためのパケットスケジューリングシステム及び方法 - Google Patents

Abstract

【課題】 高速パケット網のためのパケットスケジューリングシステム及び方法を提供すること。
【解決手段】 ＡＴＭまたはインターネットのような高速パケット交換網でのノードの入力インターフェース及び出力インターフェースにおいて、トラフィック分類器と、中央管理部と、仮想終了時間計算部と、パケットキューと、パケット伝送部とを備えることにより、同じ出力リンクへの伝送を要求する幾つかのセション間の公正なリンク資源の配分を行える。
【選択図】 図２

Description

本発明はパケットスケジューリングシステム及び方法に係り、特に、非同期伝送モード（Ａｓｙｎｃｈｒｏｎｏｕｓ Ｔｒａｎｓｆｅｒ Ｍｏｄｅ：ＡＴＭ）またはインターネットのような高速パケット交換網でのノード、すなわちＡＴＭ交換機またはラウターのような入力インターフェース及び出力インターフェースで同じ出力リンクへの伝送を要求する幾つかのセション間の公正なリンク資源配分を行えるパケットスケジューリングシステム及び方法に関する。

一般的に、パケットスケジューリングアルゴリズムは、サーバーの動作モードによって大きく２つの方式に区分できる。

その第１の方式は、キュー内にサービスを待機するパケットが存在するかぎりサーバーが継続的にサービスを提供する作業保存方式である。

その第２の方式は、キュー内にサービスを受けるために待機するパケットが存在しても一定基準に符合されなければ、サーバーがサービスを提供せずに待機状態を維持する非作業保存方式である。

後者の非作業保存方式は、待機するパケットがあることにも拘わらず、サーバーがサービスを提供しないので、サーバーの利用効率が相対的に低い一方、事前に約束された遅延バウンドまたは遅延ジッタ限界のような性能要求事項が正確に保障されうる特徴を有する。

一方、前者の作業保存方式は、サーバーの利用効率は高いが、セション別最小性能を他のセションの動作と関係なく保障しなければならず、サーバーの遊休資源を使用しようという複数の要請に対してセション別契約速度を公正に分配できるメカニズムが考慮されなければならない。

以下、作業保存方式のスケジューリングアルゴリズムについて説明する。
スケジューリングアルゴリズムの基になる理論としては、第１の例として、非特許文献１に開示されているＧＰＳ（Ｇｅｎｅｒａｌｉｚｅｄ Ｐｒｏｃｅｓｓｏｒ Ｓｈａｒｉｎｇ）アルゴリズムがある。

前記論文では、全ての入力トラフィックを流体の流れにモデリングし、サーバーがサービスを要請する全ての連結に対して同時にサービスを提供するスケジューリングシステムとして使われ、理想的な公正性及び最適な遅延バウンド値を提供するという仮説的な理論を提示している。

しかし、このＧＰＳアルゴリズムは、実際パケット網環境ではトラフィックの最小単位がパケットであり、特定瞬間にサーバーは一つのパケットだけを伝送できるため、前記論文で提示しているシステムを実際的に具現することは不可能である。ただし、全ての工程スケジューリングアルゴリズムが指向する概念的な性能基準だけを提供する。

第２の例として、前記ＧＰＳアルゴリズムの概念を最も近接に実際網環境で具現したアルゴリズムには、引入トラフィックの基本単位をパケットに仮定したＷＦＱ（Ｗｅｉｇｈｔｅｄ Ｆａｉｒ Ｑｕｅｕｅｉｎｇ）アルゴリズムがある。ＷＦＱアルゴリズムでは流体の流れでモデリングされたトラフィックがあたかも同時にサービスされるようにＧＰＳサーバーの動作を摸倣しなければならないため、ＧＰＳサーバーの動作状態を表示するために仮想時間という概念を導入する。システム仮想時間は、ＧＰＳシステム上で発生する新しいパケットの到着、またはサービス中であるパケットのサービス終了イベントごとにＧＰＳサーバーで行なわれた仕事の量に更新され、更新された仮想終了時間をパケットのタイムスタンプとして使用する。

このＷＦＱアルゴリズムは、ＧＰＳアルゴリズムに近接な性能を提供できるが、最悪の場合、一つのパケットが伝送される間に全ての連結から新しいパケットが到着することがあるので、連結の数だけ仮想時間の計算及び更新が反復されうる。したがって、パケットに対して高速の伝送順序の決定が要求される高速網環境では事実上具現し難いと言える。

第３の例として、このようなＷＦＱアルゴリズムが有している具現上の複雑性を改善するために提案されたスケジューリングアルゴリズムとして、ＳＣＦＱ（Ｓｅｌｆ Ｃｌｏｃｋｅｄ Ｆａｉｒ Ｑｕｅｕｉｎｇ）アルゴリズムがある。

このＳＣＦＱアルゴリズムは、ＷＦＱアルゴリズムと違って、連続的なＧＰＳシミュレーションを経由せず、新しいパケット到着時、サービス中であるパケットのタイムスタンプを仮想時間と見なす。その結果、一つの伝送中に到着したパケットは、全て同じ仮想時間を共有して、仮想時間の計算による複雑性を大幅減らせる。

しかし、最悪の場合、任意のパケット到着時、全てのセションがサービス中であるタイムスタンプと同じ時間を有しうるため、新しく到着したパケットはトラフィック約束遵守の可否と関係なく全てのセションのパケットが伝送されるまで待機しなければならない。この場合、待機時間は、連結されたセションの数に比例する。このように、ＳＣＦＱアルゴリズムは仮想時間計算による複雑性は改善されたが、保障可能な遅延バウンドはＷＦＱアルゴリズムより劣化する短所がある。

第４の例として、そのようなＳＣＦＱアルゴリズムの短所を改善するための方案として、ＳＰＦＱ（Ｓｔａｒｔｉｎｇ Ｐｏｔｅｎｔｉａｌ Ｆａｉｒ Ｑｕｅｕｅｉｎｇ）アルゴリズムがある。

このＳＰＦＱアルゴリズムは、毎パケットの伝送が終わる度に各キューのヘッドにあるパケットの仮想開始時間値のうち最小値を仮想時間に再設定するアルゴリズムであって、優秀な性能を維持する長所があるが、仮想開始時間に対する整列過程が付加的必要な短所がある。

第５の例として、ＳＣＦＱアルゴリズムと類似な観点で、ＷＦＱアルゴリズムの計算複雑性を改善するための方案として、ＭＤ−ＳＣＦＱ（Ｍｉｎｉｍｕｍ Ｄｅｌａｙ−ＳＣＦＱ）アルゴリズムがある。

このＭＤ−ＳＣＦＱアルゴリズムは、ＳＣＦＱアルゴリズムのようにＧＰＳを別途にシミュレーションせずキューで待機中である先頭パケットに関する情報を利用してシステム仮想時間を計算することによって、ＷＦＱアルゴリズムに比べて計算の複雑性を減らし、ＳＣＦＱアルゴリズムに比べて遅延特性を改善しようとするアルゴリズムである。

しかし、このＭＤ−ＳＣＦＱアルゴリズムは、システム仮想時間を計算する瞬間、キューで待機するパケットの情報を持続的に収集して管理しなければならないオーバーヘッドが伴われる短所がある。

Ａｂｈａｙ Ｋ．ＰａｒｅｋｈとＲｏｂｅｒｔ Ｇ．ＧａｌｌａｇｅｒによってＩＥＥＥ／ＡＣＭ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｎｅｔｗｏｒｋｉｎｇ，ｖｏｌ.１，ｐｐ.３４４−３５７，"Ａ ｇｅｎｅｒａｌｉｚｅｄ ｐｒｏｃｅｓｓｏｒ ｓｈａｒｉｎｇ ａｐｐｒｏａｃｈ ｔｏ ｆｌｏｗ ｃｏｎｔｒｏｌ ｉｎ ｉｎｔｅｇｒａｔｅｄ ｓｅｒｖｉｃｅｓ ｎｅｔｗｏｒｋｓ：Ｔｈｅ ｓｉｎｇｌｅ ｎｏｄｅ ｃａｓｅ"（１９９３年６月）

以上説明したような第１の例〜第５の例のような作業保存方式のスケジューリングアルゴリズムにおいては、各システム別仮想時間の関数及びタイムスタンプを計算して維持する方式に差がある。

高速網環境を対象とするスケジューリングシステムにおいて、最も重要な性能パラメータは、高速の伝送順序の決定と関連したシステムの単純性という点を考慮するとき、このような単純性を維持しつつ作業保存スケジューリングシステムの基本的な要求条件である公正性及び遅延特性をＧＰＳと最も近接に維持できるシステムであるほど優秀であるといえる。

従って、高速パケット交換網で交換機またはラウターに対してＷＦＱレベルの遅延バウンド及び公正性指数を保障しつつ、システム仮想時間計算の複雑性は０（１）の複雑度を維持できる新しいパケットスケジューリングシステム及び方法が要求されている。

そこで、本発明の目的は、高速パケット交換網上の交換機またはラウターでＷＦＱレベルの遅延バウンド及び公正性指数を保障するが、システム仮想時間計算の複雑性は０（１）の複雑度を維持できる、パケットスケジューリングシステム及び方法を提供することにある。

本発明の他の目的は、パケットの伝送順序の決定時、公正で最適の遅延バウンドを提供できる、パケットスケジューリングシステム及び方法を提供することにある。

本発明の他の目的は、パケットスケジューリング方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取れる記録媒体を提供することにある。

本発明は、複数の入力リンクから入力されたトラフィックを各セション別に分類するトラフィック分類器と、前記各セションに対する協約速度及びシステムの仮想時間を管理する中央管理部と、前記協約速度及び前記システム仮想時間に応答して前記トラフィックに対してパケット別仮想終了時間を計算し、計算された前記仮想終了時間を前記パケットのヘッダにタイムスタンプとして付け加える仮想終了時間計算部と、前記仮想終了時間計算部から伝えられる前記パケットをセション別に保存するパケットキューと、前記パケットキューに保存された前記パケットのうち前記仮想終了時間が最短であるパケットを選択して出力するパケット伝送部とを具えることによって、パケットスケジューリングシステムを構成する。

前記仮想終了時間計算部は、前記パケットが属するセションの以前到着パケットの仮想終了時間及び現在時点のシステム仮想時間のうち大きい値をシステム仮想開始時間に決定するシステム仮想開始時間計算機と、前記仮想開始時間計算機によって計算された前記システム仮想開始時間、前記パケットが属するセションの速度、及び前記パケットの長さに応答してシステム仮想終了時間を計算するシステム仮想終了時間計算機とを含んでもよい。

前記システム仮想時間は、現在伝送されているパケットの伝送完了時、以前パケットの伝送が完了した時点のシステム仮想時間に現在パケットを出力リンク速度に実際伝送するのにかかる時間を加算することによって計算してもよい。

の値を有してもよい。

前記パケット伝送部は、前記パケット別仮想終了時間に基づいて前記パケットキューに保存されているパケットリストを管理するパケットリスト管理器と、前記パケットリストのうち前記パケット別仮想終了時間が最短であるパケットを選択して出力リンクに伝送し、前記中央管理部にシステム仮想時間アップデートインターラプトを発生するパケット伝送器とを含んでもよい。

前記システム仮想時間は、前記仮想時間アップデートインターラプトに応答して、

の値に再調整してもよい。

前記トラフィック分類器と、前記中央管理部と、前記仮想終了時間計算部と、前記パケットキューと、前記パケット伝送部とを、ＡＴＭ交換機及びラウターを含む高速パケット交換網ノードの入力インターフェース及び出力インターフェースのうちいずれか１つに具えてもよい。

本発明は、（ａ）複数の入力リンクから入力されたトラフィックを各セション別に分類する分類工程と、（ｂ）中央管理部から提供される各セション別協約速度及びシステムの仮想時間に応答して前記トラフィックに対してパケット別仮想終了時間を計算し、計算された前記仮想終了時間を前記パケットのヘッダにタイムスタンプとして付け加える付加工程と、（ｃ）前記仮想終了時間が付け加えた前記パケットをパケットキューにセション別に保存する保存工程と、（ｄ）前記パケットキューに保存された前記パケットのうち前記仮想終了時間が最短であるパケットを選択して出力する出力工程とを具えることによって、パケットスケジューリング方法を提供する。

本発明は、上記パケットスケジューリング方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取れる記録媒体を提供する。

本発明によるパケットスケジューリングシステム及び方法によれば、高速パケット交換網上にある交換機またはラウターでＷＦＱレベルの遅延バウンド及び公正性指数を保障しつつ、システム仮想時間計算の複雑性は０（１）の複雑度を維持できる。したがって、パケットの伝送順序の決定時、公正で最適の遅延バウンドを提供できる。

以下、添付された図面を参照して本発明の望ましい実施例を詳細に説明する。

図１は、本発明によるパケットスケジューリングシステムが備わった高速パケット交換ノードの基本構造を示すブロック図である。図１には本発明が適用されるＡＴＭまたはインターネットのような高速パケット交換網で、多数の入力リンクから任意の速度に引込まれるパケットをスケジューリングし、スケジューリングされたパケットを順次に多重化して伝送する高速パケット交換ノード（例えば、ＡＴＭ交換機、ラウターシステムなど）の基本的な構成が示されている。本発明によるパケットスケジューリングシステムは、高速パケット交換ノードの入力インターフェース部１０及び／または出力インターフェース部３０に備わる。

図１を参照すれば、高速パケット交換ノードは、大きく入力インターフェース部１０、スイッチファブリック２０、及び出力インターフェース部３０で構成される。入力インターフェース部１０は、ｍ個の入力インターフェース１０ａ〜１０ｍを含み、出力インターフェース部３０はｎ個の出力インターフェース３０ａ〜３０ｎを各々含む。出力インターフェース３０ａ〜３０ｎの各部の構成は、入力インターフェース１０ａ〜１０ｍの各部と同一構成とすることができる。

入力インターフェース部１０に備わったそれぞれの入力インターフェース１０ａ〜１０ｍは、複数の入力リンクから入力される複数のトラフィックに対して本発明によるパケットスケジューリングを行い、スケジューリング結果をスイッチファブリック２０の入力ポート１７を通じてスイッチファブリック２０に伝達する。スイッチファブリック２０は、入力インターフェース部１０から提供される入力トラフィックをスイッチングした後、これをスイッチファブリック２０の出力ポート２７を通じて出力インターフェース部３０に伝達する。出力インターフェース部３０に備わったそれぞれの出力インターフェース３０ａ〜３０ｎは、スイッチファブリック２０を通じて提供されるトラフィックを受け入れて本発明によるパケットスケジューリングを行い、その結果を出力リンクに出力する。

図２は、図１に示された入力インターフェース１０ａ内に構成される、本発明によるパケットスケジューリングシステム１００の詳細構成を示すブロック図である。

図２を参照すれば、本発明によるパケットスケジューリングシステム１００は、トラフィック分類器１１とトラフィックスケジューラ１２とを含む。そして、トラフィックスケジューラ１２は、仮想終了時間計算部１４、中央管理部１５、パケットキュー１６、及びパケット伝送部１７を含む。

トラフィック分類器１１は、複数の入力リンク１０１から入力されたトラフィックに対する多重フィールド基盤のトラフィック分類を行う。トラフィックスケジューラ１２の仮想終了時間計算部１４は、分類されたトラフィックに対して各パケット別仮想終了時間を計算し、計算された仮想終了時間を各パケットのヘッダにタイムスタンプとして付け加える。パケットキュー１６はパケットの各ヘッダに仮想終了時間が付け加えられた前記パケットを各セション別に保存する。パケット伝送部１７は、パケットに対する実際的な伝送を担当する。そして、中央管理部１５は、仮想終了時間計算部１４、パケットキュー１６及びパケット伝送部１７に連結されて、各セションに対する協約速度及びシステムの仮想時間を管理する。

入力リンク１０１から入力されたトラフィックは、トラフィック分類器１１によって各セションを区分する。トラフィック分類に使われるパケットのフィールドがインターネットプロトコルのような３階層プロトコルである場合、ＩＰのソース住所、目的地住所、プロトコルフィールド、ポート番号のような多重フィールドに基づいてセションを区分する。そして、ＡＴＭの場合、ＶＰＩ（Ｖｉｒｔｕａｌ Ｐａｔｈ Ｉｄｅｎｔｉｆｉｅｒ）及びＶＣＩ（Ｖｉｒｔｕａｌ Ｃｈａｎｎｅｌ Ｉｄｅｎｔｉｆｉｅｒ）値に基づいてセションを区分し、ＭＰＬＳ（Ｍｕｌｔｉ Ｐｒｏｔｏｃｏｌ Ｌａｂｅｌ Ｓｗｉｔｃｈｉｎｇ）の場合は、ＭＰＬＳヘッダのレーブル値に基づいてセションを区分する。

各セションに区分されたトラフィックは、仮想終了時間計算部１４に入力されるが、仮想終了時間計算部１４は中央管理部１５によって管理されるシステム仮想時間と当該セションの以前パケットの仮想終了時間に基づいて各パケット別仮想終了時間を計算し、計算された結果を当該セションに当るパケットキュー１６に保存する。パケット伝送部１７は、パケットキュー１６に保存されたパケットのうち各セションの仮想終了時間が最短であるパケットを優先的に選択して出力リンクに伝送する。

各入力リンクから入力されたトラフィックがトラフィック分類器１１を通過して各セション別に区分された後、仮想終了時間計算部１４及びパケット伝送部１７で行われる詳細動作は、次の通りである。

図３は、図２に示された仮想終了時間計算部１４の詳細ブロック図である。

図３を参照すれば、仮想終了時間計算部１４は、システム仮想開始時間計算機１４２とシステム仮想終了時間計算機１４４で構成される。

システム仮想開始時間計算機１４２は、中央管理部１５からセションに対する協約速度及びシステム仮想時間を持ってきて、パケットが属するセションの以前到着パケットの仮想終了時間及び現在時点のシステム仮想時間のうち大きい値をシステム仮想開始時間に決定する。システム仮想終了時間計算機１４４は、仮想開始時間計算機１４２によって計算された仮想開始時間と、パケットが属するセションの速度及びパケットの長さによってシステム仮想終了時間とを計算する。

図４は、新しいパケットが到着する時、図３に示された仮想終了時間計算部１４で行われるシステム仮想開始時間及びシステム仮想終了時間計算過程を示すフローチャートである。

前述したように、現在伝送中であるパケットが伝送完了する場合、パケット伝送部１７はパケットの伝送が完了する時点で次に伝送するパケットを選択して出力し、システム仮想時間を再調整する動作を行う。これに関する詳細構成及び動作は、次の通りである。

図６は、図２に示したパケット伝送部１７の詳細ブロック図である。
図６を参照すれば、パケット伝送部１７はパケットリスト管理器１７２と、パケット伝送器１７４で構成される。

パケットリスト管理器１７２は、仮想終了時間計算部１４によって計算されたパケットの仮想終了時間に基づいて、パケットキュー１６に保存されているパケットリストを管理する。パケット伝送器１７４は、パケットリスト管理器１７２によって管理されるパケットリストのうち仮想終了時間が最短であるパケットを選択して出力リンクに伝送し、中央管理部１５にシステム仮想時間アップデートインターラプトを発生してシステム仮想時間を再調整させる。

図７は、図６に示したパケット伝送部１７で行われるパケット伝送過程を示すフローチャートである。

前述したように、本発明によるパケットスケジューリング方法によれば、一つのパケット伝送のうち新しく到着するパケットは、全て同じ基準によってタイムスタンプを計算するので、システム仮想時間計算による複雑性が０（１）値に改善される。これは、ＷＦＱパケットスケジューリングシステムでシステム仮想時間（すなわち、仮想時間）の更新がセションの数Ｎに依存して０（Ｎ）に表示されるものと比較する時、Ｎ倍改善されたものと言える。

しかし、既存のＳＣＦＱパケットスケジューリングシステムも、一つのパケット処理のうち到着した全てのパケットがサービス中であるパケットのタイムスタンプ（すなわち、システム仮想時間）に基づいて自身のタイムスタンプを計算するため、０（１）の複雑性を有する。しかし、ＳＣＦＱパケットスケジューリングシステムでは複雑性は改善されたが、任意のパケットが到着して伝送されるまでの遅延の最大値がセションの数に依存する特性を有するので、多くの引込トラフィックが存在するノードに適用し難い短所がある。そして、ＳＰＦＱパケットスケジューリングシステムは、仮想開始時間によって整列された順序を維持する短所があり、それにより仮想時間の計算の複雑度が０（ｌｏｇ Ｎ）となる。

そして、ＭＤ−ＳＣＦＱパケットスケジューリングシステムは、仮想時間計算の複雑度を０（１）に減らし、遅延及び公正性指数の性能を改善したが、相変らず仮想時間の計算のための付加的な複雑度が存在する問題点を有している。
従って、本発明によるパケットスケジューリングシステム及び方法は、前記のような既存のパケットスケジューリングシステムが有している問題点を改善し、複雑性は０（１）に維持しつつ最大遅延限度をＷＦＱパケットスケジューリングシステムのレベルに保障でき、ＷＦＱパケットスケジューリングシステムの公正性指数に相応する公正性指数の値を有する。

これにより、本発明によるパケットスケジューリングシステム及び方法は、高速パケット交換ノードに適用可能な長所を有し、インターネット網のように可変的なパケットだけでなく、ＡＴＭのように固定サイズのパケットにも適用されうる長所を有している。

本発明は、コンピュータで読取れる記録媒体にコンピュータが読取れるコードとして具現できる。コンピュータが読取れる記録媒体は、コンピュータシステムによって読取られるデータが保存される全ての種類の記録装置を含む。コンピュータが読取れる記録媒体の例としては、ＲＯＭ、ＲＡＭ、ＣＤ−ＲＯＭ、磁気テープ、フロッピー（登録商標）ディスク、光データ保存装置があり、またキャリヤウェーブ（例えば、インターネットを通じた伝送）状に具現されるものも含む。また、コンピュータが読取れる記録媒体は、ネットワークに連結されたコンピュータシステムに分散されて、分散方式でコンピュータが読取れるコードとして保存され、かつ実行されうる。

本発明によるパケットスケジューリングシステム及び方法は、ＡＴＭまたはインターネットのような高速パケット交換網でのノードの入力インターフェース及び出力インターフェースで同じ出力リンクへの伝送を要求する幾つかのセション間の公正なリンク資源の配分を行うためにＡＴＭ交換機またはラウターに適用される。

本発明によるパケットスケジューリングシステムが備わった高速パケット交換ノードの基本構造を示すブロック図である。 図１に示す入力インターフェース内に構成される、本発明によるパケットスケジューリングシステムの詳細構成を示すブロック図である。 図２に示す仮想終了時間計算部の詳細ブロック図である。 新しいパケットが到着するとき、図３に示す仮想終了時間計算部で行われるシステム仮想開始時間及びシステム仮想終了時間計算過程を示すフローチャートである。 図４に示す１４５０段階で行われる仮想開始時間及び仮想終了時間計算に対する詳細フローチャートである。 図２に示すパケット伝送部の詳細ブロック図である。 図６に示すパケット伝送部で行われるパケット伝送過程を示すフローチャートである。

符号の説明

１１ トラフィック分類器
１２ トラフィックスケジューラ
１４ 仮想終了時間計算部
１５ 中央管理部
１６ パケットキュー
１７ パケット伝送部
１００ パケットスケジューリングシステム
１０１ 入力リンク

Claims (14)

1. 複数の入力リンクから入力されたトラフィックを各セション別に分類するトラフィック分類器と、
   前記各セションに対する協約速度及びシステムの仮想時間を管理する中央管理部と、
   前記協約速度及び前記システム仮想時間に応答して前記トラフィックに対してパケット別仮想終了時間を計算し、計算された前記仮想終了時間を前記パケットのヘッダにタイムスタンプとして付け加える仮想終了時間計算部と、
   前記仮想終了時間計算部から伝えられる前記パケットをセション別に保存するパケットキューと、
   前記パケットキューに保存された前記パケットのうち前記仮想終了時間が最短であるパケットを選択して出力するパケット伝送部と
   を具えたことを特徴とするパケットスケジューリングシステム。
2. 前記仮想終了時間計算部は、
   前記パケットが属するセションの以前到着パケットの仮想終了時間及び現在時点のシステム仮想時間のうち大きい値をシステム仮想開始時間に決定するシステム仮想開始時間計算機と、
   前記仮想開始時間計算機によって計算された前記システム仮想開始時間、前記パケットが属するセションの速度、及び前記パケットの長さに応答してシステム仮想終了時間を計算するシステム仮想終了時間計算機と
   を含むことを特徴とする請求項１記載のパケットスケジューリングシステム。
3. 前記システム仮想時間は、現在伝送されているパケットの伝送完了時、以前パケットの伝送が完了した時点のシステム仮想時間に現在パケットを出力リンク速度に実際伝送するのにかかる時間を加算することによって計算されることを特徴とする請求項１記載のパケットスケジューリングシステム。
4. 

   

   の値を有することを特徴とする請求項２記載のパケットスケジューリングシステム。
5. 前記パケット伝送部は、
   前記パケット別仮想終了時間に基づいて前記パケットキューに保存されているパケットリストを管理するパケットリスト管理器と、
   前記パケットリストのうち前記パケット別仮想終了時間が最短であるパケットを選択して出力リンクに伝送し、前記中央管理部にシステム仮想時間アップデートインターラプトを発生するパケット伝送器と
   を含むことを特徴とする請求項１記載のパケットスケジューリングシステム。
6. 

   前記システム仮想時間は、前記仮想時間アップデートインターラプトに応答して、
   

   

   の値に再調整されることを特徴とする請求項５記載のパケットスケジューリングシステム。
7. 前記トラフィック分類器と、前記中央管理部と、前記仮想終了時間計算部と、前記パケットキューと、前記パケット伝送部とを、ＡＴＭ交換機及びラウターを含む高速パケット交換網ノードの入力インターフェース及び出力インターフェースのうちいずれか１つに具えたことを特徴とする請求項１記載のパケットスケジューリングシステム。
8. （ａ）複数の入力リンクから入力されたトラフィックを各セション別に分類する分類工程と、
   （ｂ）中央管理部から提供される各セション別協約速度及びシステムの仮想時間に応答して前記トラフィックに対してパケット別仮想終了時間を計算し、計算された前記仮想終了時間を前記パケットのヘッダにタイムスタンプとして付け加える付加工程と、
   （ｃ）前記仮想終了時間が付け加えた前記パケットをパケットキューにセション別に保存する保存工程と、
   （ｄ）前記パケットキューに保存された前記パケットのうち前記仮想終了時間が最短であるパケットを選択して出力する出力工程と
   を具えたことを特徴とするパケットスケジューリング方法。
9. 前記（ｂ）付加工程は、
   （ｂ−１）前記パケットが属するセションの以前到着パケットの仮想終了時間及び現在時点のシステム仮想時間のうち大きい値をシステム仮想開始時間に決定する工程と、
   （ｂ−２）前記システム仮想開始時間、前記パケットが属するセションの速度、及び前記パケットの長さに応答してシステム仮想終了時間を計算する工程と
   を含むことを特徴とする請求項８記載のパケットスケジューリング方法。
10. 前記システム仮想時間は、現在伝送されているパケットの伝送完了時、以前パケットの伝送が完了した時点のシステム仮想時間に現在パケットを出力リンク速度に実際伝送するのにかかる時間を加算することによって計算されることを特徴とする請求項８記載のパケットスケジューリング方法。
11. 

    

    の値を有することを特徴とする請求項９記載のパケットスケジューリング方法。
12. 前記（ｄ）出力工程は、
    （ｄ−１）前記パケット別仮想終了時間に基づいて前記パケットキューに保存されているパケットリストを管理する工程と、
    （ｄ−２）前記パケットリストのうち前記パケット別仮想終了時間が最短であるパケットを選択して出力リンクに伝送し、前記システム仮想時間を再調整する工程と
    を含むことを特徴とする請求項８記載のパケットスケジューリング方法。
13. 

    前記システム仮想時間は、前記仮想時間アップデートインターラプトに応答して
    

    

    の値に再調整されることを特徴とする請求項１２記載のパケットスケジューリング方法。
14. 請求項８記載の方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取れる記録媒体。
    

Images