(57)【要約】【課題】サポートするキューの数が増大した場合でも、高速動作が可能となる重み付きラウンドロビン規則に基づくパケットスケジューリング装置を提供する。【解決手段】パケット送信部が、各キューに格納されたパケットが当該キューの先頭に達した際に、パケットが送信された最新のキューの識別子と当該キューの識別子を比較して、当該キューのサービス順序が前記最新のキューのサービス順序より遅い場合に、当該キューに対する次のサービス回数の値を前記最新のキューのサービス回数の値とし、当該キューのサービス順序が前記最新のキューのサービス順序以前の場合に、当該キューに対する次のサービス回数の値を（前記最新のキューのサービス回数の値＋１）とし、当該キューに対する次のサービス回数の値、及び記憶部から読み込んだ重みの値に基づいて、当該パケットが送信可能となるサービス回数の値を決定するスケジューリング手段を有する。【選択図】　　　　図３
2004064159.tif 000002
【特許請求の範囲】
【請求項１】
パケットを到着順に先頭から格納する複数のキューであって、前記各キューが一連の識別子で識別され、前記各キュー間のサービス順序が識別子順であり、かつ前記各キューに対する一連のサービスが繰り返されるラウンドロビン規則に基づく複数のキューと、
前記各キュー毎に設定された重みの値を記憶する記憶部と、
前記各キューに設定された重みの値、及び前記各キューに対するサービス回数の値に基づいて、前記各キューに格納されたパケットが送信可能となる送信可能条件が予め定められ、サービス順序に達したキューにパケットが格納されていて、かつ当該キューの送信可能条件が成立している場合、当該キューに格納された先頭のパケットを送信するパケット送信部とから構成されるパケットスケジューリング装置であって、
前記パケット送信部は、前記各キューに格納されたパケットが当該キューの先頭に達した際に、パケットが送信された最新のキューの識別子と当該キューの識別子を比較して、当該キューのサービス順序が前記パケットが送信された最新のキューのサービス順序より遅い場合に、当該キューに対する次のサービス回数の値を前記パケットが送信された最新のキューのサービス回数の値とし、当該キューのサービス順序が前記パケットが送信された最新のキューのサービス順序以前の場合に、当該キューに対する次のサービス回数の値を（パケットが送信された最新のキューのサービス回数の値＋１）とし、当該キューに対する次のサービス回数の値、及び前記記憶部から読み込んだ当該キューに対応した重みの値に基づいて、当該キューの先頭に達したパケットが送信可能となるサービス回数の値を決定するスケジューリング手段と、
前記スケジューリング手段が決定した前記パケットが送信可能となるサービス回数の値及びキューの識別子を記憶し、記憶されたパケットが送信可能となるサービス回数の値及びキューの識別子から、サービス回数が最も早く、かつサービス順序が最も早いキューの識別子を特定し、前記特定されたキューの識別子で識別されるキューの先頭のパケットを送信し、特定されたパケットが送信可能となるサービス回数の値及びキューの識別子の記憶を消去する送信パケット決定手段を備えたことを特徴とするパケットスケジューリング装置。
【請求項２】
キューに対応した重みの値をＷｑ、キューに対する次のサービス回数の値をＳｑ、キューに設定可能な重みの値の最大値をＷｍａｘ、剰余演算子を％、小数点以下を切り捨てた整数値を商とする除算演算子を／とするとき、前記スケジューリング手段は、前記キューの先頭のパケットが送信可能となるサービス回数を決定する際に、Ｗｑ＞（Ｓｑ−１）％Ｗｍａｘの関係が成立する場合は、当該パケットが送信可能となるサービス回数の値をＳｑとし、Ｗｑ≦（Ｓｑ−１）％Ｗｍａｘの関係が成立する場合は、当該パケットが送信可能となるサービス回数の値を［｛（Ｓｑ−１）／Ｗｍａｘ｝＋１］＊Ｗｍａｘ＋１とすることを特徴とする請求項１に記載のパケットスケジューリング装置。
【請求項３】
パケットスケジューリング装置が動作を開始する際、もしくは、前記送信パケット決定手段がキューの先頭のパケットを送信し、パケットが送信可能となるサービス回数の値及びキューの識別子を消去した際に、全てのキューに格納されたパケットの送信が全て完了した場合、パケットを送信した最新のキューの識別子を、最もサービス順序の遅いキューの識別子とし、パケットを送信した最新のキューのサービス回数の値を０とすることを特徴とする請求項１または請求項２に記載のパケットスケジューリング装置。
【請求項４】
前記送信パケット決定手段として、ヒープによる優先キューを備えたことを特徴とする請求項１ないし請求項３のいずれか１項に記載のパケットスケジューリング装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＡＴＭセル等の固定長パケットや、ＦＲフレーム、イーサネットフレーム、ＨＤＬＣフレーム、ＩＰパケット等の可変長パケットに対するパケットスケジューリング装置に係わり、特に、重み付きラウンドロビン規則（ＷＲＲ規則）に基づくパケットスケジューリング装置に関わる。
【０００２】
【従来の技術】
重み付きラウンドロビン規則とは、ラウンドロビン規則に重みの概念を加えたサービス規則である。
図１（ａ）に示す様に、ラウンドロビン規則では、ａからｆに対して順次サービスが行なわれる。従って、ラウンドロビン規則では、サービス対象に対して等しい頻度でサービスが行なわれる。
これに対して、重み付きラウンドロビン規則は、このサービス頻度に対して重みづけを加えるものである。
図１（ｂ）に、ａ、ｂ、ｄ、ｆの重みを２、ｃ、ｅの重みを１とした例を示す。
図１（ｂ）に示す様に、１回目のサービスでａ−ｆに対して、２回目のサービスでａ、ｂ、ｄ、ｆに対してサービスが行なわれ、これらのサービスが順次繰り返えされる。
重み付きラウンドロビン規則に基づくパケットスケジューリング装置では、パケットを格納する複数のキューに対して重みづけに応じた頻度でサービスが行なわれる。
このため、パケットが固定長の場合は、各キューに対して、回線の帯域を各キューの重みづけに応じて分割した、最低帯域を割り当てる事が出来る。
【０００３】
従来の、重み付きラウンドロビン規則に基づくパケットスケジューリング装置の実現例を下記文献（イ）に基づいて示す。
（イ）Ｍ．Ｋａｔｅｖｅｎｉｓ，Ｓ．Ｓｉｄｉｒｏｐｏｕ−ｌｏｓ，ａｎｄ　Ｃ．Ｃｏｕｒｃｏｕｂｅｔｉｓ，“Ｗｅｉｇｈｔｅｄ　Ｒｏｕｎｄ−Ｒｏｂｉｎ　Ｃｅｌｌ　Ｍｕｌｔｉｐｌｅｘｉｎｇ　ｉｎ　ａ　Ｇｅｎｅｒａｌ−Ｐｕｒｐｏｓｅ　ＡＴＭ　Ｓｗｉｔｃｈ　Ｃｈｉｐ，”ＩＥＥＥ　Ｊ．　ｏｎ　Ｓｅｌｅｃｔｅｄ　Ａｒｅａｓ　ｉｎ　Ｃｏｍｍｕｎ．，　ＶｏＬ　９，　Ｎｏ．　８，　ｐｐ．１２６５−１２７９，　Ｏｃｔｏｂｅｒ　１９９１．図２は、前述の文献（イ）に開示されたパケットスケジューリング装置を示すブロック図である。
同図において、２０１は重みの値を記憶する記憶部、２０２はパケット送信部、２０３，２０４はキューである。
この図２に示す実現例において、従来の重み付きラウンドロビン規則に基づくパケットスケジューリング装置の動作例を説明する。
図２に示す様に、２０３，２０４のキューは、先頭から到着順にパケットを格納するもので、一連の識別子で識別される。
【０００４】
パケットスケジューリング装置に到着したパケットは、パケットに含まれるアドレス識別子、上位プロトコル識別子、及びサービス識別子等に基づくセッション情報、パケットに含まれるリンク識別子、パケットや上位プロトコルの優先度情報、及びパケットが到着した入力回線の識別子、等の情報の一部あるいは全部に基づいて分類され、それぞれのキューに格納される。
記憶部２０１は、キューの識別子の値でアドレッシングされる配列で構成され、キュー毎に設定された重みの値を記憶する。
パケット送信部２０２は、パケットが送信された最新のキューの次のサービス順序のキューから、キューの識別子順にキューを検索して、パケットが格納されていて、かつキューに設定された重みの値及びキューに対するサービス回数の値に基づいた送信可能条件が成立しているキューの先頭のパケットを送信する。
ここで、キューを検索する際に、サービス順序の最後の識別子のキューの次のキューはサービス順序が最初の識別子のキューとなる。
また、ラウンドロビン規則におけるサービスは、ここではキューに対する検索に相当するため、サービス回数はキューに対する検索回数となる。
【０００５】
尚、キューに対応した重みの値をＷｑ、キューに対するサービス回数の値をＳｑ、キューに設定可能な重みの値の最大値をＷｍａｘ、剰余演算子を％、小数点以下を切り捨てた整数値を商とする除算演算子を／とすると、前述の文献（イ）では、［｛（Ｓｑ−１）％Ｗｍａｘ｝＋１］の値をサイクルと、［｛（Ｓｑ−１）／Ｗｍａｘ｝＋１］の値をラウンドとしているが、これらは、キューに対するサービス回数の値と、キューに設定可能な重みの最大値と論理的に同じである。キューに設定された重みの値Ｗｑ、及びキューに対するサービス回数Ｓｑの値に基づいたパケットの送信可能条件の判定方法には幾つかの方法がある。
重み付きラウンドロビン規則に基づくパケットスケジューリング装置の簡易な実装では、キューにおけるサイクルの値が１からＷｑの間は送信可能とし、これ以外の場合は送信不可とする方法が用いられている場合がある。
即ち、Ｗｑ＞｛（Ｓｑ−１）％Ｗｍａｘ｝の関係が成立する場合は送信可能となる。
また、前述の文献（イ）には、これと異なる判定方法として、重みの値毎に、送信可能となるサイクルの値を１ラウンドの間に可能な限り分散する様に予め定めておく方法が開示されている。
【０００６】
以上の、重み付きラウンドロビン規則に基づくパケットスケジューリング装置を実装する際には、幾つかの状態変数が必要となる。
先ず、サービス順序に達したキューにパケットが格納されている事を判断するために、キュー毎にパケットの格納の有無を示す状態変数が必要となる。
前述の文献（イ）では、この様な状態変数を記憶部２０１が記憶する方法が開示されている。
しかし、この様な状態変数はキュー（２０３，２０４）が保持している実装や、装置全体で状態変数を共有する実装も考えられる。また、キュー（２０３，２０４）が格納しているパケット数を状態変数としても同等な処理が可能である。次に、キューの検索を実行する際に、パケットが送信された最新のキューの次のキューを示す状態変数が必要となる。
前述の文献（イ）では、この様な状態変数を記憶部２０１にキューが検索された事を示すフラグを設ける事によって記憶する方法が開示されている。
しかし、この様な状態変数は、パケット送信部２０２がキューの識別子情報として保持している実装や、装置全体で状態変数を共有する実装も考えられる。
また、パケットが送信された最新のキューのサービス回数、若しくはサイクルの値、または、各キューのサービス回数の値を記憶する必要がある事も自明である。
【０００７】
何れにせよ、重み付きラウンドロビン規則に基づくパケットスケジューリング装置を実装する際には、この様な状態変数を管理している事は技術的に自明であり、それがどの様な形態で、装置の何処の部分に記憶されているかは実現上の本質的な部分ではない。
尚、重み付きラウンドロビン規則に基づくパケットスケジューリング装置の実現例中には、キューの先頭のパケットを送信した際に、全てのキューがパケットの送信が完了している場合には、前記パケットが送信された最新のキューの次のキューを示す状態変数や、パケットが送信された最新のキューのサービス回数等の状態変数を初期値に戻すものもある。
以上の説明から明らかな通り、従来の重み付きラウンドロビン規則に基づくパケットスケジューリング装置の実現例には、種々の実装例があるが、いづれの場合も、パケットが送信された最新のキューの次のサービス順序のキューから、パケットが格納されていて、かつ送信可能条件が成立しているキューを検索する必要がある。
このため、パケットスケジューリング装置がサポートするキューの数をＮとすると、キューを逐次検索した場合は最大Ｎ回の比較判定処理が必要となり、キューを並列処理で検索した場合は最大（Ｎの２乗）／２個の比較判定装置が必要となり、Ｎが増大した場合、動作時間が増大して高速な動作が困難となったり、必要なハードウエアが増大して装置コストが増大する問題点がある。
【０００８】
【発明が解決しようとする課題】
従来のラウンドロビン規則に基づくパケットスケジューリング装置の実現例における、前記と類似の問題点に対する解決方法が特開２０００−３４１３０１号公報（以下、文献（ロ）という）に開示されている。
文献（ロ）の請求項及び段落番号［００４１］の記載から明らかな通り、この文献（ロ）に記載された解決方法は二進木探索を用いる方法であり、キューのパケットの格納の有無を示す状態変数（文献（ロ）の明細書では「レディビット」）、キューが検索された事を示すフラグ（文献（ロ）の明細書では「トークン」）、及びキューの識別子（文献（ロ）の明細書では「出力ポート番号」）を探索の対象となる要素とし、各要素は各キューの状態を保持し、二進木探索を用いてこれらの要素を比較して、次にパケットを送信するキューの識別子を含む要素を特定する。
従って、必要となる比較判定装置は最大Ｎ個となり、ラウンドロビン規則に基づくパケットスケジューリング装置においては、前記と類似の問題点を解決する事が出来る。
文献（ロ）の明細書の請求項には、この解決方法がラウンドロビン規則に基づくパケットスケジューリング装置のみならず、重み付きラウンドロビン規則に基づくパケットスケジューリング装置にも適用出来るとの主張が述べられている。
【０００９】
しかし、文献（ロ）の明細書の段落番号［００５４］の記載から明らかな通り、文献（ロ）の明細書の特許請求の範囲、及び実施の形態には、重み付きラウンドロビン規則に基づくパケットスケジューリング装置における実現方法は何ら記載されておらず、この方法において重みの値がどの様に実現され処理されるかは不明である。
従って、文献（ロ）に記載された解決方法には、重み付きラウンドロビン規則に基づくパケットスケジューリング装置における従来技術と比較して、文献（ロ）の明細書の段落番号［０００６］に記載された従来技術の問題点が解決されるとする根拠は存在しない。
本発明は、前記従来技術の問題点を解決するためになされたものであり、本発明の目的は、重み付きラウンドロビン規則に基づくパケットスケジューリング装置において、次にパケットを送信するキューを決定する際に検索が必要となるため、パケットスケジューリング装置がサポートするキューの数が増大した場合、動作時間が増大して高速な動作が困難となったり、必要なハードウエアが増大して装置コストが増大する問題点を解決することが可能となる技術を提供することにある。
本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述及び添付図面によって明らかにする。
【００１０】
【課題を解決するための手段】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、下記の通りである。
本発明は、前述の目的を達成するために、重み付きラウンドロビン規則に基づくパケットスケジューリング装置のパケット送信部において、キューに格納されたパケットがキューの先頭に達した際に、パケットが送信された最新のキューの識別子とキューの識別子を比較して、キューのサービス順序がパケットが送信された最新のキューのサービス順序より遅い場合、キューに対するサービス回数の値をパケットが送信された最新のキューのサービス回数の値とし、キューのサービス順序がパケットが送信された最新のキューのサービス順序以前の場合、キューに対するサービス回数の値を（パケットが送信された最新のキューのサービス回数の値＋１）とし、キューに対するサービス回数の値、及び記憶部から読み込んだキューに対応した重みの値に基づいて、パケットが送信可能となるサービス回数の値を決定するスケジューリング手段と、スケジューリング手段が決定したパケットが送信可能となるサービス回数の値及びキューの識別子を記憶し、記憶されたパケットが送信可能となるサービス回数の値及びキューの識別子から、サービス回数が最も早く、かつサービス順序が最も早いキューの識別子を特定し、特定されたキューの識別子で識別されるキューの先頭のパケットを送信し、特定されたパケットが送信可能となるサービス回数の値及びキューの識別子の記憶を消去する送信パケット決定手段を備えた事を最も主要な特徴とする。
【００１１】
従来の重み付きラウンドロビン規則に基づくパケットスケジューリング装置の実現例から明らかな通り、キューに対するサービス回数の値は単調に増加し、かつ、サービス回数の値はキューの間ではサービス順序で増加する。
従って、各キューのサービス回数の値は、パケットが送信された最新のキューのサービス回数の値から求める事が可能であり、各キューのサービス回数を個々に計数して記憶する必要は無い。
即ち、あるキューのサービス順序がパケットが送信された最新のキューのサービス順序より遅い場合は、このキューの次のサービス回数は、パケットが送信された最新のキューのサービス回数となり、サービス順序がパケットが送信された最新のキューのサービス順序以前の場合は、このキューの次のサービス回数は、（パケットが送信された最新のキューのサービス回数＋１）となる。
従って、キューに格納されたパケットがキューの先頭に達した場合、このキューの次のサービス回数は上記に基づいて算出できる。
一方、重み付きラウンドロビン規則に基づくパケットスケジューリング装置では、キューがサービス順序に達した際にキューにパケットが格納されていて、かつキューの送信可能条件が成立している場合、キューの先頭のパケットを送信する。
【００１２】
ここで、キューの送信可能条件は、キューの重みの値及びキューのサービス回数に基づいて予め定められているため、キューの次のサービス回数以降において、送信可能条件を満たすサービス回数の値を算出する事は可能である。
キューに対応した重みの値をＷｑ、キューに対する次のサービス回数の値をＳｑ、キューに設定可能な重みの値の最大値をＷｍａｘ、剰余演算子を％、小数点以下を切り捨てた整数値を商とする除算演算子を／とすると、例えば、送信可能条件が、キューにおけるサイクルの値が１からＷｑの間は送信可能とし、これ以外の値では送信不可とする条件の場合、キューの次のサービス回数をＳｑとすると、Ｗｑ＞（Ｓｑ−１）％Ｗｍａｘの関係が成立する場合は、送信可能条件を満たすサービス回数の値はＳｑ、即ち、次のサービス回数で送信可能となり、これ以外の場合は、次のラウンドのサイクル、即ち、［｛（Ｓｑ−１）／Ｗｍａｘ｝＋１］＊Ｗｍａｘ＋１が送信可能条件を満たすサービス回数の値となる。
従って、パケットがキューの先頭に達した際に、このキューの重みの値、及び次のサービス回数の値に基づいて、送信可能条件を満たすサービス回数の値を算出し、サービス回数が算出されたキューの中から、サービス回数が最も早く、かつサービス順序が最も早いキューの先頭のパケットを送信する動作を繰り返せば、次にパケットを送信するキューを決定する際に個々のキューを検索する事なく、重み付きラウンドロビンに基づくパケットスケジューリング装置を構成する事が出来る。
【００１３】
以上の説明から明らかな通り、従来の重み付きラウンドロビンに基づくパケットスケジューリング装置では、パケットが送信された最新のキューの次のサービス順序のキューから順に、パケットが格納されていて、かつ送信可能条件が成立しているキューを線形探索（逐次検索）する方法が用いられていた。
また、従来のラウンドロビンに基づくパケットスケジューリング装置では、キューを二進木探索を用いてパケットを送信するキューを決定する方法も用いられている。
これに対して、本発明は、パケットがキューの先頭に達した際に、このキューの重みの値、及び次のサービス回数の値に基づいて、送信可能条件を満たすサービス回数の値を算出し、サービス回数が算出されたキューの中から、サービス回数が最も早く、かつサービス順序が最も早いキューの先頭のパケットを送信する事を最も主要な特徴とし、従来の方法と比較してキューの検索や探索を行なわない点が最も異なる。
【００１４】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
なお、実施の形態を説明するための全図において、同一機能を有するものは同一符号を付け、その繰り返しの説明は省略する。
図３は、本発明のパケットスケジューリング装置の概略構成を示すブロック図である。
同図において、３０１は重みの値を記憶する記憶部、３０２はパケット送信部、３０３，３０４はキュー、３０５はスケジューリング手段、３０６は送信パケット決定手段である。
以下、本実施の形態の重み付きラウンドロビン規則に基づくパケットスケジューリング装置の動作例を説明する。
図３に示す様に、キュー（３０３，３０４）は、先頭から到着順にパケットを格納するもので、一連の識別子で識別される。
パケットスケジューリング装置に到着したパケットは、パケットに含まれるアドレス識別子、上位プロトコル識別子、及びサービス識別子等に基づくセッション情報、パケットに含まれるリンク識別子、パケットや上位プロトコルの優先度情報、及びパケットが到着した入力回線の識別子等の情報の一部あるいは全部に基づいて分類され、キューに格納される。
【００１５】
記憶部３０１は、キューの識別子の値でアドレッシングされる配列で構成され、キュー毎に設定された重みの値を記憶する。
キュー（３０３，３０４）に格納されたパケットが、キューの先頭に達した際のパケット送信部３０２のスケジューリング手段３０５の動作例を図４に示す。スケジューリング手段３０５は、このキューのサービス順序がパケットが送信された最新のキューのサービス順序より遅い場合、このキューに対する次のサービス回数の値Ｓｑを、パケットが送信された最新のキューのサービス回数の値とする（ステップ４０１、ステップ４０２のＹ）。
キュー間のサービス順序は識別子順であるので、パケットが送信された最新のキューと、このキューのサービス順序の前後関係は、識別子を比較する事によって判定する事が出来る。
また、このキューのサービス順序がパケットが送信された最新のキューのサービス順序以前の場合、このキューに対する次のサービス回数の値Ｓｑを、（パケットが送信された最新のキューのサービス回数の値＋１）とする（ステップ４０１、ステップ４０２のＮ、ステップ４０３）。
そして、スケジューリング手段３０５は、このキューに対応した重みの値Ｗｑを記憶部３０１から読み込み、算出したＳｑとＷｑの値に基づいてパケットが送信可能となるサービス回数の値を算出する（ステップ４０４）。
【００１６】
前述のステップ４０４における、Ｓｑ及びＷｑに基づいた、パケットが送信可能となるサービス回数の値の算出方法には幾つもの方法がある。
パケットが送信可能となる送信可能条件の例として、キューにおけるサイクルの値が１からＷｑの間は送信可能とし、これ以外の値では送信不可とする条件の場合において、前述のステップ４０４におけるパケットが送信可能となるサービス回数の値を算出する際の動作例の詳細を図５に示す。
なお、図５では、キューに対応した重みの値をＷｑ、該キューに対する次のサービス回数の値をＳｑ、キューに設定可能な重みの値の最大値をＷｍａｘ、剰余演算子を％、小数点以下を切り捨てた整数値を商とする除算演算子を／としている。
キューに設定可能な重みの値の最大値Ｗｍａｘは、パケットスケジューリング装置の構造に基づく定数である。
Ｗｑ＞（Ｓｑ−１）％Ｗｍａｘの関係が成立する場合は、該パケットが送信可能となるサービス回数の値をＳｑとする（ステップ５０１、ステップ５０２）。
Ｗｑ≦（Ｓｑ−１）％Ｗｍａｘの関係が成立する場合は、該パケットが送信可能となるサービス回数の値を［｛（Ｓｑ−１）／Ｗｍａｘ｝＋１］＊Ｗｍａｘ＋１とする（ステップ５０１、ステップ５０３）。
【００１７】
パケット送信部３０２の送信パケット決定手段３０６は、スケジューリング手段３０５が決定したパケットが送信可能となるサービス回数の値及びキューの識別子を記憶し、記憶されたパケットが送信可能となるサービス回数の値及びキューの識別子から、サービス回数が最も早く、かつサービス順序が最も早いキューの識別子を特定し、特定されたキューの識別子で識別されるキューの先頭のパケットを送信し、特定されたパケットが送信可能となるサービス回数の値及びキューの識別子の記憶を消去する。
送信パケット決定手段３０６は、一般には、｛パケットが送信可能となるサービス回数の値＊（パケットスケジューリング装置が備えるキューの数＋１）＋サービス順序の値｝を比較要素とする優先キューやソータで実現する事が出来る。
【００１８】
また、送信パケット決定手段３０６は、ヒープによる優先キューで実現されても良い。
ヒープによる優先キューの動作を、下記文献（ハ）に基づいて説明する。
（ハ）Ａｌ−ｆｒｅｄ　Ａｈｏ，他著，大野訳，“データ構造とアルゴリズム，”倍風館，１９８７の１２５−１２６ページ。
ヒープとは配列による半順序のついた木のデータ構造の事であり、優先キューの実装やソータの実装に用いられる。
ヒープの例を図６に示す。
図６において、丸は要素を示し、リンクは要素間の上下関係を示す。ある要素の上の要素を「親」、下の要素を「子」と呼ぶ。
図７に示す様に、一つの要素は最大２つの要素を「子」とする事ができる。
ヒープの要素はアドレスで識別される。
ヒープの一番上の要素のアドレスを１とし、以下のアドレスは図８に示す様に順次割り当てられる。
図８において、ある要素のアドレスをＩとすると、その要素に子が存在する場合、そのアドレスは２Ｉ、２Ｉ＋１となる。また、親が存在する場合、そのアドレスはＩ／２の整数部となる。
図８において、アドレス１の要素を一番左の要素、アドレス１２の要素を一番右の要素と呼ぶ事がある。
【００１９】
図８に示す様に、ヒープの要素は左詰めで配置される。
優先キューとは、優先度が割り当てられられた要素から、優先度の最も高い要素を特定するデータ構造の事である。
優先キューは、要素を記憶するデータ構造と、データ構造から最も優先度の高い要素を削除するアルゴリズムと、データ構造に要素を挿入するアルゴリズムから構成される。
優先キューは、優先度が最も高い要素を特定出来るが、ソータと異なり、その他の要素を優先度順に整列するものでは無い事に注意せよ。
ヒープによる優先キューのデータ構造を図９に示す。
図９における要素の値は優先度を表し、値が少ないほど優先度が高いものとする。
図９における要素の配置は、「要素が子を有する場合、その要素の優先度は子の優先度以上となる」規則に基づいている。このため、ヒープの一番上の要素は最も高い優先度を持つことになる。
図９において、ある要素が２つの子を持つ場合、子の間には特に優先度の大小関係が規定されない事に注意せよ。また、同じ優先度の要素が必ずしも同じ高さに位置する訳では無い事に注意せよ。
【００２０】
ヒープヘの要素の挿入アルゴリズムは、ヒープにおける要素の適切な挿入アドレス（位置）を探索する事によって実現される。
基本的なアルゴリズムを以下に示す。
（ａ）最初の挿入位置を、ヒープの最も右の要素の右隣とする。
（ｂ）挿入する要素の優先度が、挿入位置の親の要素の優先度以下の場合、もしくは、挿入位置の親の要素が存在しない場合（＝挿入位置が一番上の要素となる場合）、挿入する要素の適切な挿入位置が探索されたため、挿入する要素を挿入位置に移動して、停止する。
（ｃ）挿入する要素の優先度が、挿入位置の親の要素の優先度より高い場合、この位置は適切な挿入位置ではないため、挿入位置の親の要素を挿入位置へ移動し、次の挿入位置を移動前の親の位置とする。
（ｄ）上記（ｂ）と（ｃ）の動作を、アルゴリズムが停止するまで繰り返す。
このアルゴリズムの例として、図９のヒープに優先度７の要素を挿入する例を図１０に示す。
このアルゴリズムによって、図１１に示した様にヒープの一番上の要素によって最も高い優先度の要素が特定される。
【００２１】
ヒープから最も優先度の高い要素を削除するアルゴリズムは、最も上の要素を削除し、最も右の要素の適切な挿入アドレス（位置）を探索する事によって実現される。
基本的なアルゴリズムを以下に示す。
（ａ）ヒープの最も上の要素が最も優先度が高いため、これを削除する。
（ｂ）ヒープの要素数が０となった場合、停止する。
（ｃ）最も右の要素を削除し、挿入する要素とする。
（ｄ）最初の挿入位置を、ヒープの最も上の要素とする。
（ｅ）挿入位置の要素が子を持たない場合、もしくは、挿入する要素の優先度が、挿入位置の全ての子の優先度以上となる場合、挿入する要素の適切な挿入位置が探索されたため、挿入する要素を挿入位置に移動して、停止する。
（ｆ）挿入する要素の優先度が、何れか一方の子あるいは両方の子の優先度より低い場合、（子が一つしかない場合は子の優先度より低い場合）、この位置は適切な挿入位置ではないため、優先度の高い方の子を挿入位置へ移動し、次の挿入位置を移動前の子の位置とする。
（ｇ）上記（ｅ）と（ｆ）の動作を、アルゴリズムが停止するまで繰り返す。
【００２２】
このアルゴリズムの例として、図９のヒープから最も優先度の高い要素を削除する例を図１２に示す。
このアルゴリズムによって、図１３に示した様にヒープの一番上の要素によって最も高い優先度の要素が特定される。
よって、ヒープによる優先キューにおける要素数をＮとすると、要素の挿入や削除の際の要素の比較や移動の回数はｌｏｇ２Ｎに比例し、かつ要素の格納用のメモリ容量はＮのオーダとなる。
以上の説明から明らかな通り、パケット送信部３０２の送信パケット決定手段３０６は、キュー（３０３，３０４）に格納されたパケットがキューの先頭に達した際に、スケジューリング手段３０５が決定したパケットが送信可能となるサービス回数の値及びキューの識別子を比較要素としてヒープによる優先キューに挿入し、サービス回数が最も早く、かつサービス順序が最も早いキューの識別子を特定し、特定されたキューの識別子で識別されるキューの先頭のパケットを送信し、特定されたパケットが送信可能となるサービス回数の値及びキューの識別子の要素を削除する事によって実現できる。
【００２３】
前述した本実施の形態の、重み付きラウンドロビン規則に基づくパケットスケジューリング装置では、パケットが送信された最新のキューの識別子を示す状態変数、及びパケットが送信された最新のキューのサービス回数の値を示す状態変数が必要となる。
これらの状態変数は、パケット送信部３０２や記憶部３０１やキュー（３０３，３０４）が保持しても良いし、装置全体で共有しても良く、これは実現上の本質的な部分では無い。
尚、パケットスケジューリング装置が動作を開始する際と、キューの先頭のパケットを送信した際に、全てのキューがパケットの送信が完了している場合には、パケットを送信した最新のキューの識別子を示す状態変数を最もサービス順序の遅いキューの識別子とし、パケットを送信した最新のキューのサービス回数の値を示す状態変数を０として初期値に戻しても良い。
キューの先頭のパケットを送信した際に、全てのキューがパケットの送信が完了している事は、ヒープによる優先キューに基づく送信パケット決定手段ではヒープに記憶された要素数が０となった事によって検出する事が出来る。
以上、本発明者によってなされた発明を、前記実施の形態に基づき具体的に説明したが、本発明は、前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【００２４】
【発明の効果】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば、下記の通りである。
本発明によれば、パケットがキューの先頭に達した際に、このキューの重みの値、及び次のサービス回数の値に基づいて、送信可能条件を満たすサービス回数の値を算出し、サービス回数が算出されたキューの中から、サービス回数が最も早く、かつサービス順序が最も早いキューの先頭のパケットを送信する。
このため、パケットを送信するキューを決定する際の検索動作が必要なく、送信パケット決定手段にヒープによる優先キューを用いた場合、パケットスケジューリング装置がサポートするキューの数をＮとすると、要素の挿入や削除の際の要素の比較や移動の回数はｌｏｇ２Ｎに比例し、かつ要素の格納用のメモリ容量はＮのオーダとなり、装置がサポートするキューの数が増大した場合であっても、動作時間が増大する割合や必要なハードウエア量が増大する割合が既存の方法と比較して低いため、高速な動作が可能となり、また装置コストが増大しない利点がある。
【図面の簡単な説明】
【図１】ラウンドロビン規則と重み付きラウンドロビン規則を説明するための図である。
【図２】従来の重み付きラウンドロビン規則に基づくパケットスケジューリング装置の実現例を示すブロック図である。
【図３】本発明の実施の形態における、重み付きラウンドロビン規則に基づくパケットスケジューリング装置の概略構成を示すブロック図である。
【図４】図３に示すスケジューリング手段の動作例を説明するためのフローチャートである。
【図５】図３に示すスケジューリング手段において、サービス回数を算出する際の動作例を説明するためのフローチャートである。
【図６】ヒープの一例を示す図である。
【図７】ヒープの親と子の関係を説明するための図である。
【図８】ヒープのアドレスを説明するための図である。
【図９】ヒープによる優先キューのデータ構造を説明するための図である。
【図１０】図９のヒープに優先度７の要素を挿入する例を説明するための図である。
【図１１】図１０の挿入結果を示す図である。
【図１２】図９のヒープから最も優先度の高い要素を削除する例を説明するための図である。
【図１３】図１２の削除結果を示す図である。
【符号の説明】
２０１，３０１…記憶部、２０３，２０４，３０３，３０４…キュー、２０２，３０２…パケット送信部、３０５…スケジューリング手段、３０６…送信パケット決定手段。
【図１】
2004064159.tif 000003
【図２】
2004064159.tif 000004
【図３】
2004064159.tif 000005
【図４】
2004064159.tif 000006
【図５】
2004064159.tif 000007
【図６】
2004064159.tif 000008
【図７】
2004064159.tif 000009
【図８】
2004064159.tif 000010
【図９】
2004064159.tif 000011
【図１０】
2004064159.tif 000012
【図１１】
2004064159.tif 000013
【図１２】
2004064159.tif 000014
【図１３】
2004064159.tif 000015