JPH11298523A - パケット・スケジューリング方法 - Google Patents

Abstract

(57)【要約】 【課題】 ＷＦＱよりも実施を容易とし、ＷＲＲと比較
して遅延ジッタ性能を向上する。 【解決手段】 優先インデックスを用いたアルゴリズム
を基本とし、優先インデックステーブルを用いた構成に
対して、優先ソートリスト１３を設けて、実際のパケッ
ト転送シーケンス（ラウンド）ごとに、全フローあるい
は所定フローを優先インデックスの大きい順（降順）に
格納し、この優先ソートリスト１３内の先頭の各フロー
から順にパケットを転送し、その後、優先ソートリスト
外の各フローからパケットを転送する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、パケット・スケジ
ューリング方法に関し、特に超高速ネットワークを構成
する中継ノードにおいて、各フローに対し中継ノードの
パケット転送処理能力の割り当てを行うパケット・スケ
ジューリングの制御方法に関するものである。

【０００２】

【従来の技術】現在、パケット交換ネットワークは、リ
アルタイムでのマルチメディア通信など、増加の一途を
たどる新世代のアプリケーションへの対応を迫られてい
る。これらのアプリケーションを効果的にサポートする
には、同時に複数の高品質のサービスを提供する必要が
ある。例えば、インターネットは、そのサービス範囲を
ますます広げるべく進化し、変容しつつある。

【０００３】複数のサービスをサポートするパケット交
換ネットワークで用いられる機構の１つに、中継ノード
におけるパケット・スケジューリングがある。パケット
・スケジューラの機能は、次に送出するパケットを決定
することだけである。これは、巨視的な観点から見れ
ば、異なるクラスに属する複数のアプリケーション間で
ネットワーク・リソースをスケジューリングする方法で
ある。

【０００４】従来、ネットワーク・ノードでパケット・
スケジューリングを行う場合、１つのＦＩＦＯ（Ｆｉｒ
ｓｔ−Ｉｎ Ｆｉｒｓｔ−Ｏｕｔ）待ち行列だけを使用
していた。しかし、前述のように、各アプリケーション
が用いるどのフローのどのパケットもサービスの対象に
なり得るにもかかわらず、ＦＩＦＯでは個々のパケット
・フローを区別していないため、複数の高品質サービス
を提供するという観点が抜けていた。

【０００５】すなわち、パケット・サービス（スケジュ
ーリング）方式を採用するということは、それ自体が大
きな設計上の課題である。理想的なスケジューリング・
アルゴリズムは、簡単なコンピュータ処理で高速ネット
ワーク内で実現できる必要があるだけでなく、それぞれ
のフローを公平にサポートしながら切り分けるという、
一般的には矛盾する要件を満たすものでなくてはならな
い。

【０００６】従来のパケット・スケジューリングのアル
ゴリズムとして、タイムスタンピング・アルゴリズム
と、タイムフレームベース・アルゴリズムとが提案され
ている。タイムスタンピング・アルゴリズムとしては、
いわゆるジェネラライズド・プロセッサ・シェアリング
（以下、ＧＰＳという）を、パケット転送処理能力の割
り当て方法として適応させた重みづけフェア・キューイ
ング（ＷＦＱ）がある。また、タイムフレームベース・
アルゴリズムとしては、重みづけラウンドロビン（ＷＲ
Ｒ）がある。

【０００７】

【発明が解決しようとする課題】しかしながら、このよ
うな従来のパケット・スケジューリング方法は、以下の
ような問題点があった。まず、ＷＦＱ（重み付き公平待
ち行列化）などのタイムスタンプ・アルゴリズムでは、
ルータに到着するそれぞれのパケットについて、あまり
にも多くの変数を用いて計算を行うため、タイムスタン
ピング・アルゴリズムを超高速ネットワークで使用する
のは困難であった。

【０００８】また、ＷＲＲ（重み付きラウンド・ロビ
ン）などのフレーム単位でのアルゴリズムは、バースト
性が高いトラフィックに極めて弱いため、遅延ジッタが
大きいという問題点があった。本発明はこのような課題
を解決するためのものであり、ＷＦＱよりも実施が容易
であるとともに、ＷＲＲと比較して遅延ジッタ性能を向
上できるパケット・スケジューリング方法を提供するこ
とを目的としている。

【０００９】

【課題を解決するための手段】このような目的を達成す
るために、請求項１の発明は、パケット・スケジューリ
ング方法において、各フローが要求するサービス転送速
度に対応する時間量を示す重みと、各フローの待ち行列
長とに基づいて、各フローのパケットを転送する優先順
位を示す優先インデックスを算出し、これら優先インデ
ックスの大きい順に各フローを並び替えて優先ソートリ
ストに格納し、この優先ソートリストの先頭フローから
順にパケットを転送することにより、各フローに対して
パケット転送能力を割り当てるようにしたものである。
したがって、各フローの重みと待ち行列長という極めて
比較的少ない数の変数に基づいて優先インデックスが算
出されて、パケット転送能力が割り当てられるととも
に、各フローのトラフィック変化を反映した優先ソート
リストに応じて迅速な優先処理が実行される。

【００１０】より詳細には、請求項２記載のように、時
間軸上に各フローの重みの和に対応する長さのフレーム
を連続して設けるとともに、各フレーム内に１つ以上の
フローから単位数ずつパケットを転送するのに必要な長
さのラウンドを連続して設ける。そして、各フローから
は、各フレームの先頭ラウンドからそのフローの重みに
対応する数の連続する各ラウンドごとに単位数ずつパケ
ットを転送し、各ラウンド内では優先ソートリストの先
頭フローから順にパケットを転送する。したがって、各
フローが要求するサービス転送速度が各フレームごとに
保証されるとともに、各フローのトラフィック変化に応
じた順序で各ラウンドごとにパケット転送能力が割り当
てられる。

【００１１】なお、請求項３の発明のように、それぞれ
のフローの優先インデックスがそのフローに設定された
所定しきい値以上の場合のみ、そのフローを優先ソート
リストに追加し、優先ソートリスト内の先頭のフローか
ら順にパケットを転送した後に、優先ソートリスト外の
各フローから順次パケットを転送するようにしてもよ
く、これにより、パケット転送能力の割当順を優先した
場合に効果のあるフローのみが選択されて優先ソートリ
ストへ追加される。また、請求項４の発明のように、中
継ノードで処理する全フロー数がその中継ノードに設定
された基準フロー数以上の場合にのみ、優先ソートリス
トへフローを追加するようにしてもよく、これにより、
全フロー数が所定しきい値以上の場合のみ優先ソートリ
ストが利用される。

【００１２】

【発明の実施の形態】次に、本発明について図面を参照
して説明する。図１は本発明の一実施の形態であるパケ
ット・スケジューリング方法を示す説明図である。本発
明のアルゴリズムの基本的な機構は、特願平９−２３０
８０５号で提案した優先インデックスの概念を拡張した
ものである。

【００１３】以下、本発明の基本となる優先インデック
スを用いたアルゴリズムについて説明する。この考え方
によれば、時間軸上に同じ長さのフレームを設け、各フ
レーム内においてその接続処理時に予め固定的に重みｗ
_i という時間量を各フローＦ_i に割り当てることによ
り、各フローが要求するサービス転送速度を各フレーム
ごとに保証するものとなっている。

【００１４】さらに、待ち行列へ着信するフローの優先
順位を示す値、すなわち優先インデックスが格納されて
いる優先インデックス・テーブルを使用して、前述した
ＷＲＲなどの静的なスケジューラとは異なり、それぞれ
のフローの瞬間的な「サービス需要」に対応した処理が
可能となる。

【００１５】図１において、Ｎ本（Ｎは２以上の整数）
の各フローＦ₁ 〜Ｆ_N には、それぞれのフロー接続処理
時に、重みｗ₁ 〜ｗ_N が所定の方法により割当てられ
る。各フローから到着したパケットは、各フローごとに
設けられたキュー・バッファ（待ち行列）Ｑ₁ 〜Ｑ_N に
格納される。

【００１６】優先インデックス・テーブル１１には、各
フローごとに優先インデックスｕ₁〜ｕ_N が格納されて
いる。これら優先インデックスは、パケット転送シーケ
ンス（ラウンド）の開始の直前タイミング（時刻ｔ）
に、次の式に基づいて更新される。 ｕ_i（ｔ）＝ｑ_i（ｔ）／ｗ_i ただし、ｉ＝１‥Ｎ、ｑ_i（ｔ）は時刻ｔにおけるフロ
ーＦ_i のキュー・バッファＱ_i の長さ、ｗ_i はフローＦ
_i に予め割り当てられた重みを示す。

【００１７】このようにして、各フローＦ₁ 〜Ｆ_N の優
先インデックスｕ₁ 〜ｕ_N を更新した後、これら優先イ
ンデックスを大きさの順に並び替え（ソート）する。続
いて、優先インデックスが大きい順に各フローを順に選
択し（ラウンド）、選択されたフローの重みｗが残って
いる場合（ｗ＞０の場合）に限り、対応するフローのキ
ュー・バッファＱからパケットを読み出して送出する。

【００１８】そして、各フローの選択が一巡し終わった
時点（ラウンド終了時点）で、各フローの新たな待ち行
列の長さとパケット読み出しに応じて減算された重みと
に基づいて、各優先インデックスｕ₁ 〜ｕ_N が再計算さ
れ、次のパケット転送シーケンスが開始される。これに
より、当初割り当てられた重みだけではなく、トラフィ
ックにより変化する待ち行列の長さに応じてもパケット
転送能力が各フローに割り当てられるものとなり、バー
スト的なトラフィックに対応できる。

【００１９】本発明は、このような優先インデックスを
用いたアルゴリズムを基本とし、図１に示すように、前
述した優先インデックステーブルを用いた構成に対し
て、優先ソートリスト１３を設けて、実際のパケット転
送シーケンス（ラウンド）ごとに、全フローの優先イン
デックスの大きい順（降順）に格納するとともに、この
優先ソートリスト１３に基づいて各フローからパケット
を転送するようにしたものである。

【００２０】これにより、従来のＷＦＱ方式と比較し
て、極めて少ない変数に基づいてスケジューリングを行
うことができ、中継ノードにおいて容易に実施でき、か
つ処理負担を軽減できる。また、任意のフローでバース
ト的なトラフィック変動が発生した場合でも、これに応
じてそのフローを直ちに高優先で処理でき、従来のＷＲ
Ｒのアルゴリズムに比較して、遅延ジッタを大幅に低減
できる。

【００２１】また、各フローごとに設定された所定のし
きい値ｅ_i （しきい値テーブル１２）と、各フローの優
先インデックスｕ_I とを比較し、その比較結果に応じて
優先ソートリスト１３への追加要否を判断して、優先ソ
ートリスト１３へ追加するフローを制限するようにして
もよく、より効果的にフロー選択処理の所要時間を短縮
できる。

【００２２】以下、所定のしきい値ｅ_i を用いて、優先
ソートリスト１３への追加要否を判断する場合について
詳細に説明する。図３はパケット・スケジューリング処
理動作を示すフローチャート、図４はフロー転送処理動
作を示すフローチャート、図５はパケット転送処理動作
を示すフローチャートである。

【００２３】中継ノードでは、図３に示すように、パケ
ット・スケジューリング処理として、まず、各フローＦ
₁ 〜Ｆ_N のキュー・バッファＱ₁ 〜Ｑ_N を検査すること
により未転送パケットの有無を確認し（ステップ３
０）、未転送パケットがない場合は（ステップ３０：Ｎ
Ｏ）、任意のフローから新たなパケットが到着するまで
待機する。

【００２４】一方、未転送パケットがある場合は（ステ
ップ３０：ＹＥＳ）、各フローＦ₁〜Ｆ_N に予め設定さ
れている重みｗ₁ 〜ｗ_N を合計することにより１フレー
ムの長さ（フレーム長）Ｌを算出する（ステップ３
１）。次に、ラウンドごとの処理として、まず、優先ソ
ートリスト１３（図１参照）を初期化し（ステップ３
２）、前述と同様にして、最新の待ち行列の長さに基づ
いて各フローの優先インデックスｕ₁ 〜ｕ_N を算出し、
優先インデックステーブル１１に格納する（ステップ３
３）。

【００２５】続いて、任意のフローＦ_i の優先インデッ
クスｕ_i とそのフローＦ_i に対して予めしきい値テーブ
ル１２に設定されているしきい値ｅ_i とを比較する（ス
テップ３４）。このしきい値ｅ_i は、フローＦ_i を優先
リストテーブル１３へ追加するか否かを判断するための
値であり、各フローの重みｗ_i と同様に呼設定時に算出
され、しきい値テーブル１２に格納される。

【００２６】通常、例えばトラフィック急増などによ
り、フローＦ_i が緊急性を要する場合、その優先インデ
ックスｕ_i も大きくなり、優先インデックスｕ_i の大き
いものから順に優先的に選択されて処理される。この場
合、全フローの数すなわちコネクション数が大きくなれ
ば、優先インデックスｕ_i の大きさに基づくフロー選択
処理も大きくなり、中継ノードにおける処理負担が増加
し、パケット転送の遅延が生じる場合がある。

【００２７】一方、トラフィックがあまり増加していな
い各フローでは、優先インデックスｕ_i に応じた順で選
択した場合でも、処理負担の小さい適当な順序、例えば
呼設定順や各フローに割り当てられた番号順に選択した
場合でも、そのフローに対する順序的優先による輻輳回
避効果はあまり変わらないと考えられる。

【００２８】このことから、これら優先インデックスが
小さく、優先度が低いフローについては、優先インデッ
クスに基づくフロー選択を実行せず、処理負担の小さい
適当な順序によりフロー選択を行うことにより、中継ノ
ードでの処理負担が軽減され、パケット転送の遅延発生
が回避される。

【００２９】したがって、このしきい値ｅ_i には、各フ
ローの優先インデックス値のうち、優先インデックスに
基づくフロー選択処理による効果と、これにより増加す
る処理負担との平衡点を示す値が設定される。実際に
は、このしきい値ｅ_i は、中継ノードが使用されるネッ
トワークのタイプ（バックボーンなど）、ネットワーク
に挿入されるトラフィックのタイプ、中継ノードを利用
する予想ユーザ数などによって異なる。

【００３０】例えば、呼設定時にアプリケーションから
要求された転送レート、バッファサイズ、さらにはＩＥ
ＴＦ（Internet Engineering Task Force ）で提唱され
ているトークン・バケット・モデルにおけるトークン・
バケットサイズなど、フローＦ_i の性質を示す各種パラ
メータを用いて算出するようにしてもよい。

【００３１】このようにして、ステップ３４でしきい値
ｅ_i と優先インデックスｕ_i とが比較され、ｕ_i ≧ｅ_i
の場合にのみ（ステップ３４：ＹＥＳ）、フローＦ_i が
その優先インデックスｕ_i の大きい順（降順）に、優先
ソートリスト１３に追加される（ステップ３５）。そし
て、各フローのｕ_i のチェックが、同様にして繰り返し
実施される（ステップ３６：ＮＯ）。

【００３２】すべてのフローのチェックが終了した後
（ステップ３６：ＹＥＳ）、図４（ａ）に示すように、
優先ソートリスト内に追加されたフローに対する転送処
理が実行される（ステップ３７）。ここでは、まず、優
先ソートリスト１３（図１参照）のうち、先頭から順に
フローＦ_i が選択され（ステップ４０）、そのフローＦ
_i に対するパケット転送処理が実行される（ステップ４
１）。

【００３３】なお、任意のフローＦ_i に対するパケット
転送処理は、図５に示すように、その重みｗ_i が０より
大きい場合は（ステップ５０：ＹＥＳ）、フローＦ_i へ
のネットワーク資源割当量を使い切っておらず、パケッ
ト転送可能と判断して、フローＦ_i のキュー・バッファ
Ｑ_i から１パケット（単位パケット数）を読み出して転
送し、その重みｗ_i とフレーム長とをそれぞれ１パケッ
ト（単位パケット数）分減算する（ステップ５１）。

【００３４】また、重みｗ_i が０より大きくない場合は
（ステップ５０：ＮＯ）、フローＦ_i へのネットワーク
資源割当量を使い切っており、パケット転送不可と判断
して、現フレーム内でのフローＦ_i からのパケット転送
を禁止する（ステップ５２）。

【００３５】このようにして、図４（ａ）のステップ４
１で、選択されたフローＦ_i から１パケット（単位パケ
ット数）転送された後、優先ソートリスト１３内の他の
フローが、リストの先頭から順（優先インデックスの降
順）に選択され（ステップ４２：ＮＯ）、転送処理が実
行される。そして、優先ソートリスト１３内のすべての
フローについて転送処理が行われた後（ステップ４２：
ＹＥＳ）、処理が終了する。

【００３６】このようにして、図３のステップ３７で、
優先ソートリスト１３内のフローに関する転送処理が実
行された後、図４（ｂ）に示すような、優先ソートリス
ト１３に追加されなかったフローの転送処理が実行され
る（ステップ３８）。

【００３７】まず、優先ソートリスト１３外のフローを
所定の順序で選択する（ステップ４５）。ここでは、公
知の一般的なラウンド・ロビン方式によるフロー選択、
例えば呼設定順や各フローに割り当てられた番号順によ
りフローが順に選択され、優先インデックスに基づく順
序での選択時より処理負担が軽減される。

【００３８】そして、前述の図４（ａ）と同様に、選択
されたフローのパケット転送処理が行われ（ステップ４
６）、選択されたフローＦ_i から１パケット（単位パケ
ット数）転送された後、優先ソートリスト１３外の他の
フローが、所定の順に選択され（ステップ４７：Ｎ
Ｏ）、転送処理が実行される。そして、優先ソートリス
ト１３外のすべてのフローについて転送処理が行われた
後（ステップ４７：ＹＥＳ）、処理が終了する。

【００３９】このようにして、図３のステップ３８で、
優先ソートリスト１３外のフローに関する転送処理が実
行された後、残りのフレーム長Ｌにより、１フレーム内
でのパケット転送処理の継続可否が判断される（ステッ
プ３９）。ここで、Ｌ＞０の場合は（ステップ３９：Ｙ
ＥＳ）、前述したステップ３２に戻って、新たなラウン
ドにおける転送処理を継続する。

【００４０】また、フレーム長Ｌ＞０以外の場合は（ス
テップ３９：ＮＯ）、残りのフレーム長Ｌがなく、１フ
レーム内でのパケット転送処理を継続不可と判断して、
前述したステップ３０に戻り、次の新たなフレームにお
けるパケット転送処理を開始する。

【００４１】したがって、１フレーム内では、図２に示
すような順序で各フレームのパケットが転送される。図
２はパケット転送出力例を示す説明図である。各フロー
Ｆ₁ 〜Ｆ_N の重みｗ₁ 〜ｗ_N の総和を長さとして持つフ
レームが、時間軸上に設けられている。

【００４２】フレーム内には、各ラウンドが設けられて
おり、ラウンド内において、自己の重みｗ_i を使い切っ
ていない各フローＦ_i から１パケット（単位パケット
数）ずつ読み出されて転送される。この場合、１ラウン
ド内では、前述の図３で説明したように、まず、各フロ
ーの優先インデックスｕ₁ 〜ｕ_N が新たに算出され、し
きい値ｅ₁ 〜ｅ_N との比較結果により優先ソートリスト
が更新される（時刻２１）。

【００４３】続いて、優先ソートリスト１３に追加され
ている順、すなわち各フローの優先インデックスｕ_i の
大きいものから順に、フローＦ（ｕ_max ）〜Ｆ（ｕ
_min ）が選択され、１パケット（単位パケット数）ずつ
転送される。優先ソートリスト内の各フロー選択が終了
した後、優先ソートリスト外の各フローが所定の順序で
選択され、１パケット（単位パケット数）ずつ転送され
る。

【００４４】自己の重みｗ_i を使い切っていないすべて
のフローから１パケット（単位パケット数）ずつ転送さ
れた時点で、１ラウンドが終了し、新たなラウンドが開
始される（時刻２２，２３）。このようにして、フレー
ム長Ｌに残りがなくなるまで、ラウンドが繰り返され、
フレーム長がなくなった時点で、新たなフレームが繰り
返し開始される（時刻２４）。

【００４５】このように、各フローＦ_i について、その
優先インデックスｕ_i としきい値ｅ_i との比較結果に応
じて、優先ソートリストへの追加要否を判断するように
したので、より効果のあるフローのみを選択して優先ソ
ートリストへ追加でき、追加フロー数を低減させた分だ
け、中継ノードの処理負担を軽減できる。

【００４６】なお、以上説明したパケット・スケジュー
リング方法において、さらに、中継ノードで処理する全
フローの数に応じて、優先ソートリストを用いるか否か
を判断する処理を追加してもよい。具体的には、全フロ
ーの数が所定の基準フロー数ｎ以上の場合にのみ、優先
ソートリストへの追加を許可する判断処理となる。

【００４７】これは、中継ノードで処理する全フローの
数が、極端に小さい場合、例えば中継ノードの最大処理
フロー数が数千で、実際のフロー数が数十の場合は、従
来の一般的なフロー選択アルゴリズムであっても、あま
り処理時間を必要とせず、本発明とほとんど差がない。
したがって、このような場合は、優先ソートリストへの
追加を禁止することにより、中継ノードにおいて、優先
ソートリストを生成するための処理負担を軽減でき、中
継ノードの処理能力をより効果的に利用できる。

【００４８】なお、各フレームごとに、そのフレーム開
始時点での全フロー数に基づいて、優先ソートリストへ
の追加可否を行うようにしもよい。例えば、各フローＦ
₁ 〜Ｆ_N の優先インデックスｕ₁ 〜ｕ_N を算出するステ
ップ３３（図３参照）の直前に挿入することにより、優
先ソートリストに関する処理、例えばステップ３３〜３
６までの処理を省略できる。

【００４９】また、各ラウンドごとに、そのラウンド開
始時点における全フロー数に基づいて、優先ソートリス
トへの追加可否を行うようにしもよい。例えば、各フロ
ーＦ₁ 〜Ｆ_N の優先インデックスｕ₁ 〜ｕ_N としきい値
ｅ₁ 〜ｅ_N との比較結果により優先ソートリストへの追
加要否判断を行うステップ３４と論理積となる処理位置
に挿入することにより、各ラウンドごとに変化しうる最
新のフロー数に基づく判断が可能となる。

【００５０】

【発明の効果】以上説明したように、本発明は、各フロ
ーの重みと待ち行列長とから算出された優先インデック
スの大きい順に各フローを並び替えて優先ソートリスト
に格納し、この優先ソートリストの先頭フローから順に
パケットを転送することにより、各フローに対してパケ
ット転送能力を割り当てるようにしたものである。した
がって、従来のＷＦＱ方式と比較して、極めて少ない数
の変数に基づいてスケジューリングを行うことができ、
中継ノードにおいて容易に実施でき、かつ処理負担を軽
減できる。また、任意のフローでバースト的なトラフィ
ック変動が発生した場合でも、これに応じてそのフロー
を直ちに高優先で処理でき、従来のＷＲＲのアルゴリズ
ムに比較して、遅延ジッタを大幅に低減できる。

【００５１】また、それぞれのフローの優先インデック
スがそのフローに設定された所定しきい値以上の場合の
み、そのフローを優先ソートリストに追加し、優先ソー
トリスト内の先頭のフローから順にパケットを転送した
後に、優先ソートリスト外の各フローから順次パケット
を転送するようにしたので、このしきい値として各フロ
ーに適切な値を設定することにより、パケット転送能力
の割当順を優先した場合に効果のあるフローのみを選択
して優先ソートリストへ追加でき、中継ノードが有する
処理能力を有効利用できる。また、中継ノードで処理す
る全フロー数がその中継ノードに設定された基準フロー
数以上の場合にのみ、優先ソートリストへフローを追加
するようにしたので、この基準フロー数として中継ノー
ドに適切な値を設定することにより、中継ノードの処理
能力をより効果的に利用できる。

【図面の簡単な説明】

【図１】 本発明の一実施の形態によるパケット・スケ
ジューリング方法を示す説明図である。

【図２】 パケット転送出力例を示す説明図である。

【図３】 パケット・スケジューリング処理動作を示す
フローチャートである。

【図４】 フロー転送処理動作を示すフローチャートで
ある。

【図５】 パケット転送処理動作を示すフローチャート
である。

【符号の説明】

Ｆ₁ 〜Ｆ_N …フロー、Ｑ₁ 〜Ｑ_N …キュー・バッファ
（待ち行列）、ｑ₁ 〜ｑ_N …待ち行列長、ｗ₁ 〜ｗ_N …
重み、ｕ₁ 〜ｕ_N …優先インデックス、ｅ₁ 〜ｅ_N …し
きい値、１１…優先インデックステーブル、１２…しき
い値テーブル、１３…優先ソートリスト。

Claims (4)

【特許請求の範囲】
1. 【請求項１】 超高速ネットワークを構成する中継ノー
   ドで、個々のパケット流を示す各フローに対し、中継ノ
   ードのパケット転送処理能力の割り当てを行う場合のパ
   ケット・スケジューリング方法において、 各フローが要求するサービス転送速度に対応する時間量
   を示す重みと、各フローの待ち行列長とに基づいて、各
   フローのパケットを転送する優先順位を示す優先インデ
   ックスを算出し、 これら優先インデックスの大きい順に各フローを並び替
   えて優先ソートリストに格納し、 この優先ソートリストの先頭フローから順にパケットを
   転送することにより、各フローに対してパケット転送能
   力を割り当てることを特徴とするパケット・スケジュー
   リング方法。
2. 【請求項２】 請求項１記載のパケット・スケジューリ
   ング方法において、 時間軸上に各フローの重みの和に対応する長さのフレー
   ムを連続して設けるとともに、各フレーム内に１つ以上
   のフローから単位数ずつパケットを転送するのに必要な
   長さのラウンドを連続して設け、 各フローからは、各フレームの先頭ラウンドからそのフ
   ローの重みに対応する数の連続する各ラウンドごとに単
   位数ずつパケットを転送し、 各ラウンド内では優先ソートリストの先頭フローから順
   にパケットを転送することを特徴とするパケット・スケ
   ジューリング方法。
3. 【請求項３】 請求項１または２記載のパケット・スケ
   ジューリング方法において、 それぞれのフローの優先インデックスがそのフローに設
   定された所定しきい値以上の場合のみ、そのフローを優
   先ソートリストに追加し、 優先ソートリスト内の先頭のフローから順にパケットを
   転送した後に、優先ソートリスト外の各フローから順次
   パケットを転送することを特徴とするパケット・スケジ
   ューリング方法。
4. 【請求項４】 請求項１〜３記載のパケット・スケジュ
   ーリング方法において、 中継ノードで処理する全フロー数がその中継ノードに設
   定された基準フロー数以上の場合にのみ、優先ソートリ
   ストへフローを追加することを特徴とするパケット・ス
   ケジューリング方法。