(57)【要約】【課題】  高速パケット網のためのパケットスケジューリングシステム及び方法を提供すること。【解決手段】  ＡＴＭまたはインターネットのような高速パケット交換網でのノードの入力インターフェース及び出力インターフェースにおいて、トラフィック分類器と、中央管理部と、仮想終了時間計算部と、パケットキューと、パケット伝送部とを備えることにより、同じ出力リンクへの伝送を要求する幾つかのセション間の公正なリンク資源の配分を行える。【選択図】  図２
2004201304.tif 000002
【特許請求の範囲】
【請求項１】
複数の入力リンクから入力されたトラフィックを各セション別に分類するトラフィック分類器と、
前記各セションに対する協約速度及びシステムの仮想時間を管理する中央管理部と、
前記協約速度及び前記システム仮想時間に応答して前記トラフィックに対してパケット別仮想終了時間を計算し、計算された前記仮想終了時間を前記パケットのヘッダにタイムスタンプとして付け加える仮想終了時間計算部と、
前記仮想終了時間計算部から伝えられる前記パケットをセション別に保存するパケットキューと、
前記パケットキューに保存された前記パケットのうち前記仮想終了時間が最短であるパケットを選択して出力するパケット伝送部と
を具えたことを特徴とするパケットスケジューリングシステム。
【請求項２】
前記仮想終了時間計算部は、
前記パケットが属するセションの以前到着パケットの仮想終了時間及び現在時点のシステム仮想時間のうち大きい値をシステム仮想開始時間に決定するシステム仮想開始時間計算機と、
前記仮想開始時間計算機によって計算された前記システム仮想開始時間、前記パケットが属するセションの速度、及び前記パケットの長さに応答してシステム仮想終了時間を計算するシステム仮想終了時間計算機と
を含むことを特徴とする請求項１記載のパケットスケジューリングシステム。
【請求項３】
前記システム仮想時間は、現在伝送されているパケットの伝送完了時、以前パケットの伝送が完了した時点のシステム仮想時間に現在パケットを出力リンク速度に実際伝送するのにかかる時間を加算することによって計算されることを特徴とする請求項１記載のパケットスケジューリングシステム。
【請求項４】
2004201304.tif 000020
2004201304.tif 000021
の値を有することを特徴とする請求項２記載のパケットスケジューリングシステム。
【請求項５】
前記パケット伝送部は、
前記パケット別仮想終了時間に基づいて前記パケットキューに保存されているパケットリストを管理するパケットリスト管理器と、
前記パケットリストのうち前記パケット別仮想終了時間が最短であるパケットを選択して出力リンクに伝送し、前記中央管理部にシステム仮想時間アップデートインターラプトを発生するパケット伝送器と
を含むことを特徴とする請求項１記載のパケットスケジューリングシステム。
【請求項６】
2004201304.tif 000022
前記システム仮想時間は、前記仮想時間アップデートインターラプトに応答して、
2004201304.tif 000023
の値に再調整されることを特徴とする請求項５記載のパケットスケジューリングシステム。
【請求項７】
前記トラフィック分類器と、前記中央管理部と、前記仮想終了時間計算部と、前記パケットキューと、前記パケット伝送部とを、ＡＴＭ交換機及びラウターを含む高速パケット交換網ノードの入力インターフェース及び出力インターフェースのうちいずれか１つに具えたことを特徴とする請求項１記載のパケットスケジューリングシステム。
【請求項８】
（ａ）複数の入力リンクから入力されたトラフィックを各セション別に分類する分類工程と、
（ｂ）中央管理部から提供される各セション別協約速度及びシステムの仮想時間に応答して前記トラフィックに対してパケット別仮想終了時間を計算し、計算された前記仮想終了時間を前記パケットのヘッダにタイムスタンプとして付け加える付加工程と、
（ｃ）前記仮想終了時間が付け加えた前記パケットをパケットキューにセション別に保存する保存工程と、
（ｄ）前記パケットキューに保存された前記パケットのうち前記仮想終了時間が最短であるパケットを選択して出力する出力工程と
を具えたことを特徴とするパケットスケジューリング方法。
【請求項９】
前記（ｂ）付加工程は、
（ｂ−１）前記パケットが属するセションの以前到着パケットの仮想終了時間及び現在時点のシステム仮想時間のうち大きい値をシステム仮想開始時間に決定する工程と、
（ｂ−２）前記システム仮想開始時間、前記パケットが属するセションの速度、及び前記パケットの長さに応答してシステム仮想終了時間を計算する工程と
を含むことを特徴とする請求項８記載のパケットスケジューリング方法。
【請求項１０】
前記システム仮想時間は、現在伝送されているパケットの伝送完了時、以前パケットの伝送が完了した時点のシステム仮想時間に現在パケットを出力リンク速度に実際伝送するのにかかる時間を加算することによって計算されることを特徴とする請求項８記載のパケットスケジューリング方法。
【請求項１１】
2004201304.tif 000024
2004201304.tif 000025
の値を有することを特徴とする請求項９記載のパケットスケジューリング方法。
【請求項１２】
前記（ｄ）出力工程は、
（ｄ−１）前記パケット別仮想終了時間に基づいて前記パケットキューに保存されているパケットリストを管理する工程と、
（ｄ−２）前記パケットリストのうち前記パケット別仮想終了時間が最短であるパケットを選択して出力リンクに伝送し、前記システム仮想時間を再調整する工程と
を含むことを特徴とする請求項８記載のパケットスケジューリング方法。
【請求項１３】
2004201304.tif 000026
前記システム仮想時間は、前記仮想時間アップデートインターラプトに応答して
2004201304.tif 000027
の値に再調整されることを特徴とする請求項１２記載のパケットスケジューリング方法。
【請求項１４】
請求項８記載の方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取れる記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はパケットスケジューリングシステム及び方法に係り、特に、非同期伝送モード（Ａｓｙｎｃｈｒｏｎｏｕｓ Ｔｒａｎｓｆｅｒ Ｍｏｄｅ：ＡＴＭ）またはインターネットのような高速パケット交換網でのノード、すなわちＡＴＭ交換機またはラウターのような入力インターフェース及び出力インターフェースで同じ出力リンクへの伝送を要求する幾つかのセション間の公正なリンク資源配分を行えるパケットスケジューリングシステム及び方法に関する。
【背景技術】
【０００２】
一般的に、パケットスケジューリングアルゴリズムは、サーバーの動作モードによって大きく２つの方式に区分できる。
【０００３】
その第１の方式は、キュー内にサービスを待機するパケットが存在するかぎりサーバーが継続的にサービスを提供する作業保存方式である。
【０００４】
その第２の方式は、キュー内にサービスを受けるために待機するパケットが存在しても一定基準に符合されなければ、サーバーがサービスを提供せずに待機状態を維持する非作業保存方式である。
【０００５】
後者の非作業保存方式は、待機するパケットがあることにも拘わらず、サーバーがサービスを提供しないので、サーバーの利用効率が相対的に低い一方、事前に約束された遅延バウンドまたは遅延ジッタ限界のような性能要求事項が正確に保障されうる特徴を有する。
【０００６】
一方、前者の作業保存方式は、サーバーの利用効率は高いが、セション別最小性能を他のセションの動作と関係なく保障しなければならず、サーバーの遊休資源を使用しようという複数の要請に対してセション別契約速度を公正に分配できるメカニズムが考慮されなければならない。
【０００７】
以下、作業保存方式のスケジューリングアルゴリズムについて説明する。
スケジューリングアルゴリズムの基になる理論としては、第１の例として、非特許文献１に開示されているＧＰＳ（Ｇｅｎｅｒａｌｉｚｅｄ Ｐｒｏｃｅｓｓｏｒ Ｓｈａｒｉｎｇ）アルゴリズムがある。
【０００８】
前記論文では、全ての入力トラフィックを流体の流れにモデリングし、サーバーがサービスを要請する全ての連結に対して同時にサービスを提供するスケジューリングシステムとして使われ、理想的な公正性及び最適な遅延バウンド値を提供するという仮説的な理論を提示している。
【０００９】
しかし、このＧＰＳアルゴリズムは、実際パケット網環境ではトラフィックの最小単位がパケットであり、特定瞬間にサーバーは一つのパケットだけを伝送できるため、前記論文で提示しているシステムを実際的に具現することは不可能である。ただし、全ての工程スケジューリングアルゴリズムが指向する概念的な性能基準だけを提供する。
【００１０】
第２の例として、前記ＧＰＳアルゴリズムの概念を最も近接に実際網環境で具現したアルゴリズムには、引入トラフィックの基本単位をパケットに仮定したＷＦＱ（Ｗｅｉｇｈｔｅｄ Ｆａｉｒ Ｑｕｅｕｅｉｎｇ）アルゴリズムがある。ＷＦＱアルゴリズムでは流体の流れでモデリングされたトラフィックがあたかも同時にサービスされるようにＧＰＳサーバーの動作を摸倣しなければならないため、ＧＰＳサーバーの動作状態を表示するために仮想時間という概念を導入する。システム仮想時間は、ＧＰＳシステム上で発生する新しいパケットの到着、またはサービス中であるパケットのサービス終了イベントごとにＧＰＳサーバーで行なわれた仕事の量に更新され、更新された仮想終了時間をパケットのタイムスタンプとして使用する。
【００１１】
このＷＦＱアルゴリズムは、ＧＰＳアルゴリズムに近接な性能を提供できるが、最悪の場合、一つのパケットが伝送される間に全ての連結から新しいパケットが到着することがあるので、連結の数だけ仮想時間の計算及び更新が反復されうる。したがって、パケットに対して高速の伝送順序の決定が要求される高速網環境では事実上具現し難いと言える。
【００１２】
第３の例として、このようなＷＦＱアルゴリズムが有している具現上の複雑性を改善するために提案されたスケジューリングアルゴリズムとして、ＳＣＦＱ（Ｓｅｌｆ Ｃｌｏｃｋｅｄ Ｆａｉｒ Ｑｕｅｕｉｎｇ）アルゴリズムがある。
【００１３】
このＳＣＦＱアルゴリズムは、ＷＦＱアルゴリズムと違って、連続的なＧＰＳシミュレーションを経由せず、新しいパケット到着時、サービス中であるパケットのタイムスタンプを仮想時間と見なす。その結果、一つの伝送中に到着したパケットは、全て同じ仮想時間を共有して、仮想時間の計算による複雑性を大幅減らせる。
【００１４】
しかし、最悪の場合、任意のパケット到着時、全てのセションがサービス中であるタイムスタンプと同じ時間を有しうるため、新しく到着したパケットはトラフィック約束遵守の可否と関係なく全てのセションのパケットが伝送されるまで待機しなければならない。この場合、待機時間は、連結されたセションの数に比例する。このように、ＳＣＦＱアルゴリズムは仮想時間計算による複雑性は改善されたが、保障可能な遅延バウンドはＷＦＱアルゴリズムより劣化する短所がある。
【００１５】
第４の例として、そのようなＳＣＦＱアルゴリズムの短所を改善するための方案として、ＳＰＦＱ（Ｓｔａｒｔｉｎｇ Ｐｏｔｅｎｔｉａｌ Ｆａｉｒ Ｑｕｅｕｅｉｎｇ）アルゴリズムがある。
【００１６】
このＳＰＦＱアルゴリズムは、毎パケットの伝送が終わる度に各キューのヘッドにあるパケットの仮想開始時間値のうち最小値を仮想時間に再設定するアルゴリズムであって、優秀な性能を維持する長所があるが、仮想開始時間に対する整列過程が付加的必要な短所がある。
【００１７】
第５の例として、ＳＣＦＱアルゴリズムと類似な観点で、ＷＦＱアルゴリズムの計算複雑性を改善するための方案として、ＭＤ−ＳＣＦＱ（Ｍｉｎｉｍｕｍ Ｄｅｌａｙ−ＳＣＦＱ）アルゴリズムがある。
【００１８】
このＭＤ−ＳＣＦＱアルゴリズムは、ＳＣＦＱアルゴリズムのようにＧＰＳを別途にシミュレーションせずキューで待機中である先頭パケットに関する情報を利用してシステム仮想時間を計算することによって、ＷＦＱアルゴリズムに比べて計算の複雑性を減らし、ＳＣＦＱアルゴリズムに比べて遅延特性を改善しようとするアルゴリズムである。
【００１９】
しかし、このＭＤ−ＳＣＦＱアルゴリズムは、システム仮想時間を計算する瞬間、キューで待機するパケットの情報を持続的に収集して管理しなければならないオーバーヘッドが伴われる短所がある。
【００２０】
【非特許文献１】Ａｂｈａｙ Ｋ．ＰａｒｅｋｈとＲｏｂｅｒｔ Ｇ．ＧａｌｌａｇｅｒによってＩＥＥＥ／ＡＣＭ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｎｅｔｗｏｒｋｉｎｇ，ｖｏｌ.１，ｐｐ.３４４−３５７，“Ａ ｇｅｎｅｒａｌｉｚｅｄ ｐｒｏｃｅｓｓｏｒ ｓｈａｒｉｎｇ ａｐｐｒｏａｃｈ ｔｏ ｆｌｏｗ ｃｏｎｔｒｏｌ ｉｎ ｉｎｔｅｇｒａｔｅｄ ｓｅｒｖｉｃｅｓ ｎｅｔｗｏｒｋｓ：Ｔｈｅ ｓｉｎｇｌｅ ｎｏｄｅ ｃａｓｅ”（１９９３年６月）
【発明の開示】
【発明が解決しようとする課題】
【００２１】
以上説明したような第１の例〜第５の例のような作業保存方式のスケジューリングアルゴリズムにおいては、各システム別仮想時間の関数及びタイムスタンプを計算して維持する方式に差がある。
【００２２】
高速網環境を対象とするスケジューリングシステムにおいて、最も重要な性能パラメータは、高速の伝送順序の決定と関連したシステムの単純性という点を考慮するとき、このような単純性を維持しつつ作業保存スケジューリングシステムの基本的な要求条件である公正性及び遅延特性をＧＰＳと最も近接に維持できるシステムであるほど優秀であるといえる。
【００２３】
従って、高速パケット交換網で交換機またはラウターに対してＷＦＱレベルの遅延バウンド及び公正性指数を保障しつつ、システム仮想時間計算の複雑性は０（１）の複雑度を維持できる新しいパケットスケジューリングシステム及び方法が要求されている。
【００２４】
そこで、本発明の目的は、高速パケット交換網上の交換機またはラウターでＷＦＱレベルの遅延バウンド及び公正性指数を保障するが、システム仮想時間計算の複雑性は０（１）の複雑度を維持できる、パケットスケジューリングシステム及び方法を提供することにある。
【００２５】
本発明の他の目的は、パケットの伝送順序の決定時、公正で最適の遅延バウンドを提供できる、パケットスケジューリングシステム及び方法を提供することにある。
【００２６】
本発明の他の目的は、パケットスケジューリング方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取れる記録媒体を提供することにある。
【課題を解決するための手段】
【００２７】
本発明は、複数の入力リンクから入力されたトラフィックを各セション別に分類するトラフィック分類器と、前記各セションに対する協約速度及びシステムの仮想時間を管理する中央管理部と、前記協約速度及び前記システム仮想時間に応答して前記トラフィックに対してパケット別仮想終了時間を計算し、計算された前記仮想終了時間を前記パケットのヘッダにタイムスタンプとして付け加える仮想終了時間計算部と、前記仮想終了時間計算部から伝えられる前記パケットをセション別に保存するパケットキューと、前記パケットキューに保存された前記パケットのうち前記仮想終了時間が最短であるパケットを選択して出力するパケット伝送部とを具えることによって、パケットスケジューリングシステムを構成する。
【００２８】
前記仮想終了時間計算部は、前記パケットが属するセションの以前到着パケットの仮想終了時間及び現在時点のシステム仮想時間のうち大きい値をシステム仮想開始時間に決定するシステム仮想開始時間計算機と、前記仮想開始時間計算機によって計算された前記システム仮想開始時間、前記パケットが属するセションの速度、及び前記パケットの長さに応答してシステム仮想終了時間を計算するシステム仮想終了時間計算機とを含んでもよい。
【００２９】
前記システム仮想時間は、現在伝送されているパケットの伝送完了時、以前パケットの伝送が完了した時点のシステム仮想時間に現在パケットを出力リンク速度に実際伝送するのにかかる時間を加算することによって計算してもよい。
【００３０】
2004201304.tif 000003
【００３１】
【数１】
2004201304.tif 000004
【００３２】
の値を有してもよい。
【００３３】
前記パケット伝送部は、前記パケット別仮想終了時間に基づいて前記パケットキューに保存されているパケットリストを管理するパケットリスト管理器と、前記パケットリストのうち前記パケット別仮想終了時間が最短であるパケットを選択して出力リンクに伝送し、前記中央管理部にシステム仮想時間アップデートインターラプトを発生するパケット伝送器とを含んでもよい。
【００３４】
2004201304.tif 000005
【００３５】
前記システム仮想時間は、前記仮想時間アップデートインターラプトに応答して、
【００３６】
【数２】
2004201304.tif 000006
【００３７】
の値に再調整してもよい。
【００３８】
前記トラフィック分類器と、前記中央管理部と、前記仮想終了時間計算部と、前記パケットキューと、前記パケット伝送部とを、ＡＴＭ交換機及びラウターを含む高速パケット交換網ノードの入力インターフェース及び出力インターフェースのうちいずれか１つに具えてもよい。
【００３９】
本発明は、（ａ）複数の入力リンクから入力されたトラフィックを各セション別に分類する分類工程と、（ｂ）中央管理部から提供される各セション別協約速度及びシステムの仮想時間に応答して前記トラフィックに対してパケット別仮想終了時間を計算し、計算された前記仮想終了時間を前記パケットのヘッダにタイムスタンプとして付け加える付加工程と、（ｃ）前記仮想終了時間が付け加えた前記パケットをパケットキューにセション別に保存する保存工程と、（ｄ）前記パケットキューに保存された前記パケットのうち前記仮想終了時間が最短であるパケットを選択して出力する出力工程とを具えることによって、パケットスケジューリング方法を提供する。
【００４０】
本発明は、上記パケットスケジューリング方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取れる記録媒体を提供する。
【発明の効果】
【００４１】
本発明によるパケットスケジューリングシステム及び方法によれば、高速パケット交換網上にある交換機またはラウターでＷＦＱレベルの遅延バウンド及び公正性指数を保障しつつ、システム仮想時間計算の複雑性は０（１）の複雑度を維持できる。したがって、パケットの伝送順序の決定時、公正で最適の遅延バウンドを提供できる。
【発明を実施するための最良の形態】
【００４２】
以下、添付された図面を参照して本発明の望ましい実施例を詳細に説明する。
【００４３】
図１は、本発明によるパケットスケジューリングシステムが備わった高速パケット交換ノードの基本構造を示すブロック図である。図１には本発明が適用されるＡＴＭまたはインターネットのような高速パケット交換網で、多数の入力リンクから任意の速度に引込まれるパケットをスケジューリングし、スケジューリングされたパケットを順次に多重化して伝送する高速パケット交換ノード（例えば、ＡＴＭ交換機、ラウターシステムなど）の基本的な構成が示されている。本発明によるパケットスケジューリングシステムは、高速パケット交換ノードの入力インターフェース部１０及び／または出力インターフェース部３０に備わる。
【００４４】
図１を参照すれば、高速パケット交換ノードは、大きく入力インターフェース部１０、スイッチファブリック２０、及び出力インターフェース部３０で構成される。入力インターフェース部１０は、ｍ個の入力インターフェース１０ａ〜１０ｍを含み、出力インターフェース部３０はｎ個の出力インターフェース３０ａ〜３０ｎを各々含む。出力インターフェース３０ａ〜３０ｎの各部の構成は、入力インターフェース１０ａ〜１０ｍの各部と同一構成とすることができる。
【００４５】
入力インターフェース部１０に備わったそれぞれの入力インターフェース１０ａ〜１０ｍは、複数の入力リンクから入力される複数のトラフィックに対して本発明によるパケットスケジューリングを行い、スケジューリング結果をスイッチファブリック２０の入力ポート１７を通じてスイッチファブリック２０に伝達する。スイッチファブリック２０は、入力インターフェース部１０から提供される入力トラフィックをスイッチングした後、これをスイッチファブリック２０の出力ポート２７を通じて出力インターフェース部３０に伝達する。出力インターフェース部３０に備わったそれぞれの出力インターフェース３０ａ〜３０ｎは、スイッチファブリック２０を通じて提供されるトラフィックを受け入れて本発明によるパケットスケジューリングを行い、その結果を出力リンクに出力する。
【００４６】
図２は、図１に示された入力インターフェース１０ａ内に構成される、本発明によるパケットスケジューリングシステム１００の詳細構成を示すブロック図である。
【００４７】
図２を参照すれば、本発明によるパケットスケジューリングシステム１００は、トラフィック分類器１１とトラフィックスケジューラ１２とを含む。そして、トラフィックスケジューラ１２は、仮想終了時間計算部１４、中央管理部１５、パケットキュー１６、及びパケット伝送部１７を含む。
【００４８】
トラフィック分類器１１は、複数の入力リンク１０１から入力されたトラフィックに対する多重フィールド基盤のトラフィック分類を行う。トラフィックスケジューラ１２の仮想終了時間計算部１４は、分類されたトラフィックに対して各パケット別仮想終了時間を計算し、計算された仮想終了時間を各パケットのヘッダにタイムスタンプとして付け加える。パケットキュー１６はパケットの各ヘッダに仮想終了時間が付け加えられた前記パケットを各セション別に保存する。パケット伝送部１７は、パケットに対する実際的な伝送を担当する。そして、中央管理部１５は、仮想終了時間計算部１４、パケットキュー１６及びパケット伝送部１７に連結されて、各セションに対する協約速度及びシステムの仮想時間を管理する。
【００４９】
入力リンク１０１から入力されたトラフィックは、トラフィック分類器１１によって各セションを区分する。トラフィック分類に使われるパケットのフィールドがインターネットプロトコルのような３階層プロトコルである場合、ＩＰのソース住所、目的地住所、プロトコルフィールド、ポート番号のような多重フィールドに基づいてセションを区分する。そして、ＡＴＭの場合、ＶＰＩ（Ｖｉｒｔｕａｌ Ｐａｔｈ Ｉｄｅｎｔｉｆｉｅｒ）及びＶＣＩ（Ｖｉｒｔｕａｌ Ｃｈａｎｎｅｌ Ｉｄｅｎｔｉｆｉｅｒ）値に基づいてセションを区分し、ＭＰＬＳ（Ｍｕｌｔｉ Ｐｒｏｔｏｃｏｌ Ｌａｂｅｌ Ｓｗｉｔｃｈｉｎｇ）の場合は、ＭＰＬＳヘッダのレーブル値に基づいてセションを区分する。
【００５０】
各セションに区分されたトラフィックは、仮想終了時間計算部１４に入力されるが、仮想終了時間計算部１４は中央管理部１５によって管理されるシステム仮想時間と当該セションの以前パケットの仮想終了時間に基づいて各パケット別仮想終了時間を計算し、計算された結果を当該セションに当るパケットキュー１６に保存する。パケット伝送部１７は、パケットキュー１６に保存されたパケットのうち各セションの仮想終了時間が最短であるパケットを優先的に選択して出力リンクに伝送する。
【００５１】
各入力リンクから入力されたトラフィックがトラフィック分類器１１を通過して各セション別に区分された後、仮想終了時間計算部１４及びパケット伝送部１７で行われる詳細動作は、次の通りである。
【００５２】
図３は、図２に示された仮想終了時間計算部１４の詳細ブロック図である。
【００５３】
図３を参照すれば、仮想終了時間計算部１４は、システム仮想開始時間計算機１４２とシステム仮想終了時間計算機１４４で構成される。
【００５４】
システム仮想開始時間計算機１４２は、中央管理部１５からセションに対する協約速度及びシステム仮想時間を持ってきて、パケットが属するセションの以前到着パケットの仮想終了時間及び現在時点のシステム仮想時間のうち大きい値をシステム仮想開始時間に決定する。システム仮想終了時間計算機１４４は、仮想開始時間計算機１４２によって計算された仮想開始時間と、パケットが属するセションの速度及びパケットの長さによってシステム仮想終了時間とを計算する。
【００５５】
図４は、新しいパケットが到着する時、図３に示された仮想終了時間計算部１４で行われるシステム仮想開始時間及びシステム仮想終了時間計算過程を示すフローチャートである。
【００５６】
2004201304.tif 000007
【００５７】
2004201304.tif 000008
【００５８】
【数３】
2004201304.tif 000009
【００５９】
2004201304.tif 000010
【００６０】
【数４】
2004201304.tif 000011
【００６１】
2004201304.tif 000012
【００６２】
【数５】
2004201304.tif 000013
【００６３】
2004201304.tif 000014
【００６４】
前述したように、現在伝送中であるパケットが伝送完了する場合、パケット伝送部１７はパケットの伝送が完了する時点で次に伝送するパケットを選択して出力し、システム仮想時間を再調整する動作を行う。これに関する詳細構成及び動作は、次の通りである。
【００６５】
図６は、図２に示したパケット伝送部１７の詳細ブロック図である。  
図６を参照すれば、パケット伝送部１７はパケットリスト管理器１７２と、パケット伝送器１７４で構成される。
【００６６】
パケットリスト管理器１７２は、仮想終了時間計算部１４によって計算されたパケットの仮想終了時間に基づいて、パケットキュー１６に保存されているパケットリストを管理する。パケット伝送器１７４は、パケットリスト管理器１７２によって管理されるパケットリストのうち仮想終了時間が最短であるパケットを選択して出力リンクに伝送し、中央管理部１５にシステム仮想時間アップデートインターラプトを発生してシステム仮想時間を再調整させる。
【００６７】
図７は、図６に示したパケット伝送部１７で行われるパケット伝送過程を示すフローチャートである。
【００６８】
2004201304.tif 000015
【００６９】
【数６】
2004201304.tif 000016
【００７０】
2004201304.tif 000017
【００７１】
【数７】
2004201304.tif 000018
【００７２】
2004201304.tif 000019
【００７３】
前述したように、本発明によるパケットスケジューリング方法によれば、一つのパケット伝送のうち新しく到着するパケットは、全て同じ基準によってタイムスタンプを計算するので、システム仮想時間計算による複雑性が０（１）値に改善される。これは、ＷＦＱパケットスケジューリングシステムでシステム仮想時間（すなわち、仮想時間）の更新がセションの数Ｎに依存して０（Ｎ）に表示されるものと比較する時、Ｎ倍改善されたものと言える。
【００７４】
しかし、既存のＳＣＦＱパケットスケジューリングシステムも、一つのパケット処理のうち到着した全てのパケットがサービス中であるパケットのタイムスタンプ（すなわち、システム仮想時間）に基づいて自身のタイムスタンプを計算するため、０（１）の複雑性を有する。しかし、ＳＣＦＱパケットスケジューリングシステムでは複雑性は改善されたが、任意のパケットが到着して伝送されるまでの遅延の最大値がセションの数に依存する特性を有するので、多くの引込トラフィックが存在するノードに適用し難い短所がある。そして、ＳＰＦＱパケットスケジューリングシステムは、仮想開始時間によって整列された順序を維持する短所があり、それにより仮想時間の計算の複雑度が０（ｌｏｇ Ｎ）となる。
【００７５】
そして、ＭＤ−ＳＣＦＱパケットスケジューリングシステムは、仮想時間計算の複雑度を０（１）に減らし、遅延及び公正性指数の性能を改善したが、相変らず仮想時間の計算のための付加的な複雑度が存在する問題点を有している。
従って、本発明によるパケットスケジューリングシステム及び方法は、前記のような既存のパケットスケジューリングシステムが有している問題点を改善し、複雑性は０（１）に維持しつつ最大遅延限度をＷＦＱパケットスケジューリングシステムのレベルに保障でき、ＷＦＱパケットスケジューリングシステムの公正性指数に相応する公正性指数の値を有する。
【００７６】
これにより、本発明によるパケットスケジューリングシステム及び方法は、高速パケット交換ノードに適用可能な長所を有し、インターネット網のように可変的なパケットだけでなく、ＡＴＭのように固定サイズのパケットにも適用されうる長所を有している。
【００７７】
本発明は、コンピュータで読取れる記録媒体にコンピュータが読取れるコードとして具現できる。コンピュータが読取れる記録媒体は、コンピュータシステムによって読取られるデータが保存される全ての種類の記録装置を含む。コンピュータが読取れる記録媒体の例としては、ＲＯＭ、ＲＡＭ、ＣＤ−ＲＯＭ、磁気テープ、フロッピー（登録商標）ディスク、光データ保存装置があり、またキャリヤウェーブ（例えば、インターネットを通じた伝送）状に具現されるものも含む。また、コンピュータが読取れる記録媒体は、ネットワークに連結されたコンピュータシステムに分散されて、分散方式でコンピュータが読取れるコードとして保存され、かつ実行されうる。
【産業上の利用可能性】
【００７８】
本発明によるパケットスケジューリングシステム及び方法は、ＡＴＭまたはインターネットのような高速パケット交換網でのノードの入力インターフェース及び出力インターフェースで同じ出力リンクへの伝送を要求する幾つかのセション間の公正なリンク資源の配分を行うためにＡＴＭ交換機またはラウターに適用される。
【図面の簡単な説明】
【００７９】
【図１】本発明によるパケットスケジューリングシステムが備わった高速パケット交換ノードの基本構造を示すブロック図である。
【図２】図１に示す入力インターフェース内に構成される、本発明によるパケットスケジューリングシステムの詳細構成を示すブロック図である。
【図３】図２に示す仮想終了時間計算部の詳細ブロック図である。
【図４】新しいパケットが到着するとき、図３に示す仮想終了時間計算部で行われるシステム仮想開始時間及びシステム仮想終了時間計算過程を示すフローチャートである。
【図５】図４に示す１４５０段階で行われる仮想開始時間及び仮想終了時間計算に対する詳細フローチャートである。
【図６】図２に示すパケット伝送部の詳細ブロック図である。
【図７】図６に示すパケット伝送部で行われるパケット伝送過程を示すフローチャートである。
【符号の説明】
【００８０】
１１    トラフィック分類器
１２    トラフィックスケジューラ
１４    仮想終了時間計算部
１５    中央管理部
１６    パケットキュー
１７    パケット伝送部
１００    パケットスケジューリングシステム
１０１    入力リンク
【図１】
2004201304.tif 000028
【図２】
2004201304.tif 000029
【図３】
2004201304.tif 000030
【図４】
2004201304.tif 000031
【図５】
2004201304.tif 000032
【図６】
2004201304.tif 000033
【図７】
2004201304.tif 000034