(57)【要約】      （修正有）【課題】マルチプロセス環境において最適化されたスケジューリングを提供する。【解決手段】第１および第２の２進木を用いてスケジュールされたリーフおよびスケジュールされていないリーフを記憶する。各リーフは、送信すべきデータを有する論理リンクを表す。第１の２進木は、送信すべきであって次送信サイクル内でスケジュールされていないデータを有する論路リンクを表すリーフを含み、第２の２進木は、送信すべきであって次送信サイクル内でスケジュールされているデータを有する論路リンクを表すリーフを含む。方法は、第１および第２の２進木の各リーフを更新するステップおよび再順序付けするステップと、第１および第２の２進木にリーフを追加するステップ／リーフを除去するステップと、第２の２進木からのリーフを第１の２進木と交換するステップと、その逆とを含む。【選択図】図４
2013211848.tif 000002
【特許請求の範囲】
【請求項１】
パケットベースのネットワークにおいて送信タイムスロットを割り当てる方法であって、
前記ネットワークにおいて、時間がスケジューリングサイクルに分割され、各スケジューリングサイクルは複数のタイムスロット（ＴＱ）に分割され、
前記ネットワークは、端末によって管理される複数の論理リンク（ＬＬｉ）を備え、
前記端末は、各論理リンクに、いくつかの授与されたタイムスロット（ＧｒＴＱ，ｉ）と、いくつかの要求されるタイムスロット（ＲｅｑＴＱ，ｉ）と、理論的送信時刻（ＴＴＴｉ）とを関連付け、
前記いくつかの授与されたタイムスロット（ＧｒＴＱ，ｉ）は、次スケジューリングサイクル（ｋ＋１）内でパケットを送信するためにその論理リンクが使うことを許可された資源を表し、
前記いくつかの要求されるタイムスロット（ＲｅｑＴＱ，ｉ）は、スケジュールされていないパケットを送信するためにその論理リンクが要求する資源を表す
方法において、
アクティブな論理リンクは、少なくとも１つの要求されるタイムスロット（ＲｅｑＴＱ，ｉ）を有し、非アクティブな論理リンクは、要求されるタイムスロットを有さず、
スケジュールされた論理リンクは、少なくとも１つの授与されたタイムスロット（ＧｒＴＱ，ｉ）を有し、スケジュールされていない論理リンクは、授与されたタイムスロット（ＧｒＴＱ，ｉ）を有さず、
前記方法は、所定の最大サイズの第１の２進木および所定の最大サイズの第２の２進木を使用し、
前記第１の２進木は、スケジュールされていないアクティブな論理リンクを表すリーフを含み、
前記第２の２進木は、スケジュールされたアクティブな論理リンクを表すリーフを含み、前記第２の２進木に含まれる前記リーフは、ヌルでない要求されるタイムスロット（ＲｅｑＴＱ，ｉ）を持つ、アクティブな論理リンクを表すものであり、
前記方法は、
論理リンクに関連するＲＥＰＯＲＴメッセージの受信の際に、
その論理リンクが非アクティブである場合、その論理リンクの理論的送信時刻（ＴＴＴｉ）を更新し、その論理リンクに関連付けられた新たなリーフを生成し、その論理リンクがスケジュールされていないか又は前記第２の２進木が満杯である場合には前記第１の２進木に前記新たなリーフを追加し、その論理リンクがスケジュールされておりかつ前記第２の２進木が満杯でない場合には前記第２の２進木に前記新たなリーフを追加するステップと、
その論理リンクについて前記要求されるタイムスロット値（ＲｅｑＴＱ，ｉ）を更新するステップと、
各表される論理リンクに関連付けられた理論的送信時刻の値（ＴＴＴｉ）に従って前記第１の２進木および前記第２の２進木をソートするステップと、
各スケジューリングサイクル（ｋ）について、
すべての授与されたタイムスロット値（ＧｒＴＱ，ｉ）をゼロに初期化するステップと、
前記第２の２進木が空でなくかつ前記第１の２進木が空である場合に、または、是木第２の２進木が空でなくかつ前記第２の２進木のルートリーフの理論的送信時刻（ＴＴＴｉ）が前記第１の２進木のルートリーフの理論的送信時刻（ＴＴＴｉ）よりも小さい場合に、次スケジューリングサイクル（ｋ＋１）内でいくつかのタイムスロットを前記第２の２進木のルートリーフに関連付けられた論理リンクに授与するとともに、前記第２の２進木のルートリーフに関連付けられた論理リンクの、前記理論的送信時刻（ＴＴＴｉ）、前記授与されたタイムスロット値（ＧｒＴＱ，ｉ）および前記要求されるタイムスロット値（ＲｅｑＴＱ，ｉ）を更新するステップと、
前記第２の２進木が空でありかつ前記第１の２進木が空でない場合、
前記第１の２進木のルートリーフを除去するとともに関連付けられた論理リンクが依然としてアクティブであればこれを前記第２の２進木に加える前に、
次スケジューリングサイクル（ｋ＋１）内でいくつかのタイムスロットを前記第１の２進木のルートリーフに関連付けられた論理リンクに授与するとともに、前記第１の２進木のルートリーフに関連付けられた論理リンクの前記理論的送信時刻（ＴＴＴｉ）、前記授与されたタイムスロット値（ＧｒＴＱ，ｉ）および前記要求されるタイムスロット値（ＲｅｑＴＱ，ｉ）を更新するステップと、
各表される論理リンクに関連付けられた理論的送信時刻の値（ＴＴＴｉ）に従って前記第１の２進木および前記第２の２進木をソートするステップと、
前記授与するステップ、前記更新するステップおよび前記ソートするステップを、次スケジューリングサイクル（ｋ＋１）内のすべてのタイムスロットが授与されるか、または、もはやアクティブな論理リンクが存在しなくなるまで、繰り返すステップと、
前記第２の２進木に残っているすべてのリーフを前記第１の２進木に転送するステップと
を備える、方法。
【請求項２】
前記要求されるタイムスロット値（ＲｅｑＴＱ、ｉ）が、固定された最大値（ＳＧ）よりも大きい場合、いくつかのタイムスロットを授与する前記ステップは、現在授与されているタイムスロット値（ＧｒＴＱ，ｉ）を前記固定された最大値だけインクリメントすることを含み、前記理論的送信時刻（ＴＴＴｉ）を更新する前記ステップは、前記理論的送信時刻（ＴＴＴｉ）を前記固定された最大値と論理リンクに関連付けられた重み（Ｗｉ）の逆数との積と等価な値だけインクリメントすることを含み、前記要求されるタイムスロット値（ＲｅｑＴＱ，ｉ）を更新する前記ステップは、前記要求されるタイムスロット値（ＲｅｑＴＱ，ｉ）を前記固定された最大値だけデクリメントすることを含み、
前記要求されるタイムスロット値（ＲｅｑＴＱ，ｉ）が固定された最大値（ＳＧ）よりも大きくない場合、いくつかのタイムスロットを授与する前記ステップは、現在授与されているタイムスロット値（ＧｒＴＱ，ｉ）を前記要求されるタイムスロット値（ＲｅｑＴＱ，ｉ）だけインクリメントすることを含み、前記理論的送信時刻（ＴＴＴｉ）を更新する前記ステップは、前記理論的送信時刻（ＴＴＴｉ）を前記要求されるタイムスロット値（ＲｅｑＴＱ，ｉ）と論理リンクに関連付けられた重み（Ｗｉ）の逆数との積と等価な値だけインクリメントすることを含み、前記要求されるタイムスロット値（ＲｅｑＴＱ，ｉ）を更新する前記ステップは、前記要求されるタイムスロット値（ＲｅｑＴＱ，ｉ）をゼロにセットすることを含む、請求項１に記載の方法。
【請求項３】
各論理リンク（ＬＬｉ）に、独立に固定された最大値（ＳＧｉ）が関連付けられる、請求項２に記載の方法。
【請求項４】
次スケジューリングサイクル（ｋ＋１）内でいくつかのタイムスロットを前記第２の２進木のルートリーフに関連付けられた論理リンクに授与する前記ステップは、次サイクル内でスケジュールされた異なる論理リンクの数（ｎＬＬＩＤ）が異なる論理リンクの目標最大数（ＮＬＬＩＤ）未満である場合にのみ実行され、
前記方法は、前記第１の２進木および前記第２の２進木をソートする前記ステップより前に、
論理リンクがスケジュールされていない場合に、次サイクル内でスケジュールされた異なる論理リンクの数（ｎＬＬＩＤ）を１だけインクリメントするステップ
をさらに備える、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
前記第２の２進木が空であり、次サイクル内でスケジュールされた異なる論理リンクの数（ｎＬＬＩＤ）が異なる論理リンクの目標最大数（ＮＬＬＩＤ）に達している場合、異なる論理リンクの目標最大数（ＮＬＬＩＤ）は、所与のサイクル内の異なる論理リンクの所定の初期最大数（Ｎ）を、ある比率で乗算した値だけインクリメントされ、
前記比率は、次スケジューリングラウンド（ｋ＋１）内のタイムスロット（ＴＱ）の総数に対する、次スケジューリングラウンド（ｋ＋１）内でスケジュールされていない残りのタイムスロットの数の比率である、請求項４に記載の方法。
【請求項６】
前記ＲＥＰＯＲＴメッセージの受信に際し、前記非アクティブな論理リンクの理論的送信時刻（ＴＴＴｉ）を更新する前記ステップは、
他にアクティブな論理リンクが存在する場合、前記非アクティブな論理リンクの理論的送信時刻（ＴＴＴｉ）を、その論理リンクの現在の理論的送信時刻（ＴＴＴｉ）の値と、すべてのアクティブな論理リンクのうち最小の理論的送信時刻（ＴＴＴｉ）とのうちの最大値にセットすることと、
他にアクティブな論理リンクが存在しない場合、前記非アクティブな論理リンクの理論的送信時刻（ＴＴＴｉ）を、その論理リンクの現在の理論的送信時刻（ＴＴＴｉ）の値と、すべての論理リンクのうち直近の送信時刻とのうちの最大値にセットすることと
をさらに備える、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
前記授与するステップ、前記更新するステップおよび前記ソートするステップの各繰り返しは、スケジューリングサイクルの間、インターバルによって分離される、請求項１〜６のいずれか一項に記載の方法。
【請求項８】
各繰り返し間の前記インターバルは、直前の前記授与されたタイムスロット値（ＧｒＴＱ，ｉ）を更新する前記ステップの間に、前記授与されたタイムスロット値（ＧｒＴＱ，ｉ）に加えられた数のタイムスロットを送信するのに要する時間に等しい、請求項７に記載の方法。
【請求項９】
前記授与するステップ、前記更新するステップおよび前記ソートするステップの各前記繰り返しは、スケジューリングサイクルの終了時点で割り込みなく実行される、請求項１〜６のいずれか一項に記載の方法。
【請求項１０】
各論理リンクはメモリコンテキストを備え、
前記メモリコンテキストは、関連付けられた論理リンクＩＤ（ＬＬＩＤ）と、関連付けられた要求されるタイムスロット値（ＲｅｑＴＱ，ｉ）と、関連付けられた授与されたタイムスロット値（ＧｒＴＱ，ｉ）と、関連付けられた理論的送信時刻（ＴＴＴｉ）値とを含む、請求項１〜９のいずれか一項に記載の方法。
【請求項１１】
前記理論的送信時刻（ＴＴＴｉ）は、前記第１の２進木および前記第２の２進木のリーフの、最上位ビット（複数）に符号化される、請求項１〜１０のいずれか一項に記載の方法。
【請求項１２】
前記第１の２進木および前記第２の２進木をソートする前記ステップは、理論的送信時刻（ＴＴＴｉ）値の符号付き比較を用いて実行される、請求項１〜１１のいずれか一項に記載の方法。
【請求項１３】
前記方法は、すべての非アクティブな論理リンクの理論的送信時刻（ＴＴＴｉ）を、定期的に、最小の理論的送信時刻（ＴＴＴｉ）値を持つアクティブな論理リンクの理論的送信時刻（ＴＴＴｉ）値にセットするステップをさらに備える、請求項１２に記載の方法。
【請求項１４】
請求項１〜１３のいずれか一項に記載の方法の各ステップを実行するよう構成された、イーサネット受動光ネットワーク（ＥＰＯＮ）光回線終端装置（ＯＬＴ）。
【請求項１５】
データ処理装置のためのコンピュータプログラム製品であって、
前記コンピュータプログラム製品は命令の組を備え、
前記命令の組は、前記データ処理装置にロードされたときに、前記装置に請求項１〜１３のいずれか一項に記載の方法の各ステップを実行させる、コンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、広くアクセスネットワークに関し、より正確には、光回線終端装置と、複数の光ネットワークユニットとの間のポイントツーマルチポイント通信のための受動光ネットワーク（ＰＯＮ）に関する。
【０００２】
ＰＯＮは、単一の共有される光ファイバであり、中央局（Central Office）（ＣＯ）からの単一のファイバを、個々の加入者に供給を行う個別のストランドに分割するために、廉価な光スプリッタを用いる。このようなネットワークでは、情報はレーザーバーストによって搬送される。アクセスネットワーク内には、加入者エンドポイントおよびＣＯを除いて能動的な電子機器が存在しないので、ＰＯＮは「受動」と呼ばれる。この単一の光ファイバは受動スプリッタによって分割される。
【０００３】
非同期転送モード（ＡＴＭ）標準規格に基づく他のＰＯＮ技術とは異なり、イーサネット（登録商標）受動光ネットワーク（ＥＰＯＮ）はイーサネット標準規格（ＩＥＥＥ８０２．３）に基づいている。ＥＰＯＮはイーサネットの規模の経済を利用し、加入者エンドポイントおよびＣＯの双方において、イーサネットベースのＩＰ（インターネットプロトコル）機器に、簡素で管理しやすい接続性を提供する。
【０００４】
このようなネットワークでは、層間においてパケット単位で情報が交換される。ある層において受信された各パケットは、その層に固有の符号化パラメータセットを用いて符号化される。これらのパラメータは、ネットワーク管理手段を介して与えられる。データリンク層は、加入者エンドポイントとＣＯとの間の物理的資源を共有する役割を果たす。データリンク層は、２つのサブ層、すなわち論理リンク（ＬＬ）層および媒体アクセス制御（ＭＡＣ）層からなる。物理層は、データリンク層からの論理通信要求を、電子的信号の送受信に影響を及ぼすハードウェア固有の動作に変換する。
【０００５】
ＩＥＥＥ８０２．３ａｈ  ＥＰＯＮ仕様書は、ギガビットＥＰＯＮ（ＧＥＰＯＮ）とも呼ばれ、１ギガビットＥＰＯＮについて、マルチポイント制御プロトコル（ＭＰＣＰ）、ポイントツーポイントエミュレーション（Ｐ２ＰＥ）および物理層を定義する。ＩＥＥＥ８０２．３ａｖ仕様書は、１０ギガビットＥＰＯＮについての拡張（主に物理層に関するもの）を定義する。とりわけ、イーサネット受動光ネットワークにおけるサービス相互運用性のための標準規格（the Standard for Service Interoperability in Ethernet（登録商標） Passive Optical Networks）（ＳＩＥＰＯＮ）グループ（Ｐ１９０４．１とも呼ばれる）は、ＥＰＯＮ機器のサービスレベルマルチベンダー相互運用性を確保するのに必要なシステムレベル要件を記述している。これらの仕様書は、物理層およびデータリンク層における相互運用性を確保する既存のＩＥＥＥ標準規格８０２．３およびＩＥＥＥ標準規格８０２．１を補完する。
【０００６】
ＥＰＯＮネットワークは、通常、光回線終端装置（「ＯＬＴ」。ＣＯに含めることができるもの）と、１つ以上の光ネットワークユニット（「ＯＮＵ」。ＥＰＯＮの１人以上の加入者を受け持つもの）とを含む。各ＯＬＴによって管理されるＯＮＵの数は、現在の配備では典型的には４〜６４であるが、将来の配備では１０２４まで拡張可能である。
【０００７】
ポイントツーマルチポイント（Ｐ２ＭＰ）ファイバネットワークを制御するために、ＥＰＯＮはＭＰＣＰを用いる。ＭＰＣＰは、帯域幅割当て、帯域幅ポーリング、自動発見及び測距を実行する。ＭＰＣＰはＭＡＣ層内に実装され、２種類の６４バイトイーサネット制御メッセージを導入する。帯域幅の割り当ておよび要求にＧＡＴＥメッセージおよびＲＥＰＯＲＴメッセージが用いられ、自動発見処理を制御するためにＲＥＧＩＳＴＥＲメッセージが用いられる。
【０００８】
ＭＡＣ層は、送信調停（transmission arbitration）の役割を果たす。送信調停により、あるＯＮＵが所定時間区間（送信窓またはタイムスロットとも呼ばれる）だけそのピアから送信できるようになる。各ＯＮＵに専用の送信窓の始点および長さは、各ＯＬＴに備わる動的帯域幅割当て（ＤＢＡ）スケジューラによって定義される。
【０００９】
ＧＡＴＥメッセージはＯＬＴから１つのＯＮＵに送信され、そのＯＮＵに１つまたはいくつかの送信窓を割り当てるために用いられる。一方、ＲＥＰＯＲＴメッセージは、ＯＮＵによって、そのＯＮＵのバッファ占有率（すなわち、そのＯＮＵからＯＬＴに対して送信すべき待機中のデータパケットのキューの長さ）を示すために用いられるフィードバック機構であり、これによってＤＢＡスケジューラはそのＯＮＵのバッファ占有率に適合した送信窓を定義できる。
【００１０】
送信窓の始点および長さ（すなわち割り当てられる資源の量）およびＲＥＰＯＲＴメッセージ中のキューの長さは、時量子（Time Quantum）（ＴＱ）で表される。時量子（ＴＱ）はたとえば１６ｎｓ（ナノ秒）の時間区間として定義される。すなわち、１ギガビット毎秒のスピードにおいて２バイトを送信するのに要する時間である。
【００１１】
ＩＥＥＥ８０２アーキテクチャに準拠するため、ＰＯＮに接続される装置は、論理トポロジエミュレーション（ＬＴＥ）機能を実装する。この機能は共有媒体またはポイントツーポイント媒体をエミュレートすることができる。後者の方式では、ＯＮＵとＯＬＴとの間に能動的なスプリッタが用いられるスイッチ式ローカルエリアネットワーク（ＬＡＮ）と同じ物理的接続性を達成することが目的である。このＯＬＴ（レガシーＯＬＴとも呼ばれる）は、ある数Ｎ個のＭＡＣポート（またはインタフェース）を、各ＯＮＵについて１つずつ持つことができる。各ポートは、登録手順の間に各ＯＮＵに割り当てられる論理リンク識別子（ＬＬＩＤ）を用いて識別される。
【００１２】
下り方向（すなわちＯＬＴからＯＮＵへ）では、ＯＬＴが送信したイーサネットパケットは１＊Ｎ受動スプリッタを通過して各ＯＮＵに到達する。各イーサネットパケットは、そのパケットが宛てられたポートのＬＬＩＤを格納するフレームプリアンブルを備える。このような機能は、共有媒体ネットワークに類似している（イーサネットはＥＰＯＮアーキテクチャと完全に互換し、イーサネットは性質上ブロードキャストする）。このようにして、イーサネットパケットはＯＬＴによってブロードキャストされ、イーサネットフレームプリアンブルに挿入されたＬＬＩＤを用いてＯＮＵによって選択的に抽出される。ＯＬＴにおける下り処理は、主に、入来パケットを正しいＬＬＩＤでタグ付けすることと、それらを対応する論理リンクに転送することとからなるので、非常に単純である。
【００１３】
上り方向では、ＯＮＵは、専用のＧＡＴＥメッセージにおいて示された送信窓の間だけ送信可能となるよう許可される。この機構によりデータ衝突が回避され、ＯＮＵ間でチャネル容量が公平に(fairly)共有される。上りイーサネットフレームは、イーサネットフレームプリアンブルにおいてＯＮＵに割り当てられたＬＬＩＤを用いてタグ付けされる。このＥＰＯＮ多重化方式は、ＬＬＩＤの数が増加すると重要となり得る上りオーバヘッドを生じる。実際に、ＥＰＯＮ上りオーバヘッドは、主に制御メッセージオーバヘッドおよびガード帯オーバヘッドによるものである。制御メッセージオーバヘッドの主な原因は、ＯＮＵによってバッファ占有率を示すために送信されるＲＥＰＯＲＴメッセージである。ガード帯は、レーザのＯＮ／ＯＦＦを切り替え、必要なキャリブレーションを行うために、２つの上りバーストの間で空白のままにされる時間である。オーバヘッドの他の原因（たとえば発見オーバヘッドやフレーム描画）は無視できると考えられる。
下の表１は、１ｍｓＤＢＡサイクルの１ＧビットＥＰＯＮ（各ＯＮＵは各サイクルでＯＬＴにデータを送信する機会を持つ）における、様々な数のＯＮＵに対する上りオーバヘッドのまとめである。
【００１４】
【表１】
2013211848.tif 000003
【００１５】
表１に含まれる結果を見ると、ＤＢＡサイクルあたり３２ＯＮＵを超える数を管理するのは妥当でない。実際に、ＤＢＡサイクルあたり３２ＯＮＵを超えると、オーバヘッドが１０％を超え、また、バイト数で表した送信ウィンドウの長さが２０００バイトより小さくなるので、送信ウィンドウは１５００バイトのフレームをただ１つ送信できるのみとなる。
【００１６】
この問題を解決するために、２０１１年２月９日に出願された欧州特許出願第１１３０５１３１号明細書では、各ＤＢＡサイクル（一般的に１ｍｓ）においてスケジュールされる論理リンク（ＬＬ）の数を低減することにより、ＤＢＡサイクルあたりの上りバーストの数を制限する方法が提案されている。以下、この方法を概説する。この方法は、ＥＰＯＮがサポートするＬＬの合計数を制限することなく、レガシーの制的割り当ての代わりにＬＬ送信機会の動的割り当てを含む。それはたとえばイーサネット受動光ネットワーク（Ｇ．  Ｋｒａｍｍｅｒ、２００５年、ＩＳＢＮ  ０−０７−１４４５６２−５）において提案されるようなものである。
【００１７】
このような解決策は、オーバヘッドの低減にはつながるが、一方で、ＯＮＵが送信機会を得るまでに数サイクル待つ場合があるので、上り送信時間の増加をもたらす。このスケジューリングアルゴリズムは、バースト数制限をサポートするよう変更された自己クロック型公平キューイング（Self-Clocked Fair Queuing）（ＳＣＦＱ）アルゴリズムに基づく。
【００１８】
上述の方法の効率的な実装に関し、いくつかの技術的問題が存在する。これらの問題は、いくつかのプロセッサ間で資源を共有するプロセッサ上のネットワーキング機器の信頼性と複合する。
【００１９】
本発明は、下記の方法を提供することによって、これらの問題に対する解決策を提供する。この方法は、
パケットベースのネットワークにおいて送信タイムスロットを割り当てる方法であって、
前記ネットワークにおいて、時間がスケジューリングサイクルに分割され、各スケジューリングサイクルは複数のタイムスロットに分割され、
前記ネットワークは、端末によって管理される複数の論理リンクを備え、
前記端末は、各論理リンクに、いくつかの授与されたタイムスロットと、いくつかの要求されるタイムスロットと、理論的送信時刻とを関連付け、
前記いくつかの授与されたタイムスロットは、次スケジューリングサイクル内でパケットを送信するためにその論理リンクが使うことを許可された資源を表し、
前記いくつかの要求されるタイムスロットは、スケジュールされていないパケットを送信するためにその論理リンクが要求する資源を表す
方法において、
アクティブな論理リンクは、少なくとも１つの要求されるタイムスロットを有し、非アクティブな論理リンクは、要求されるタイムスロットを有さず、
スケジュールされた論理リンクは、少なくとも１つの授与されたタイムスロットを有し、スケジュールされていない論理リンクは、授与されたタイムスロットを有さず、
前記方法は、所定の最大サイズの第１の２進木および所定の最大サイズの第２の２進木を使用し、
前記第１の２進木は、スケジュールされていないアクティブな論理リンクを表すリーフを含み、
前記第２の２進木は、スケジュールされたアクティブな論理リンク（ただし、ヌルでない要求されるタイムスロット（ＲｅｑＴＱ，ｉ）を持つもの）を表すリーフを含み、
前記方法は、
論理リンクに関連するＲＥＰＯＲＴメッセージの受信の際に、
その論理リンクが非アクティブである場合、その論理リンクの理論的送信時刻を更新し、その論理リンクに関連付けられた新たなリーフを生成し、その論理リンクがスケジュールされていないか又は前記第２の２進木が満杯である場合には前記第１の２進木に前記新たなリーフを追加し、その論理リンクがスケジュールされておりかつ前記第２の２進木が満杯でない場合には前記第２の２進木に前記新たなリーフを追加するステップと、
その論理リンクについて前記要求されるタイムスロット値を更新するステップと、
各表される論理リンクに関連付けられた理論的送信時刻の値に従って前記第１の２進木および前記第２の２進木をソートするステップと、
各スケジューリングサイクルについて、
すべての授与されたタイムスロット値をゼロに初期化するステップと、
前記第２の２進木が空でなくかつ前記第１の２進木が空である場合に、または、是木第２の２進木が空でなくかつ前記第２の２進木のルートリーフの理論的送信時刻が前記第１の２進木のルートリーフの理論的送信時刻よりも小さい場合に、次スケジューリングサイクル内でいくつかのタイムスロットを前記第２の２進木のルートリーフに関連付けられた論理リンクに授与するとともに、前記第２の２進木のルートリーフに関連付けられた論理リンクの、前記理論的送信時刻、前記授与されたタイムスロット値および前記要求されるタイムスロット値を更新するステップと、
前記第２の２進木が空でありかつ前記第１の２進木が空でない場合、
前記第１の２進木のルートリーフを除去するとともに関連付けられた論理リンクが依然としてアクティブであればこれを前記第２の２進木に加える前に、
次スケジューリングサイクル内でいくつかのタイムスロットを前記第１の２進木のルートリーフに関連付けられた論理リンクに授与するとともに、前記第１の２進木のルートリーフに関連付けられた論理リンクの前記理論的送信時刻、前記授与されたタイムスロット値および前記要求されるタイムスロット値を更新するステップと、
各表される論理リンクに関連付けられた理論的送信時刻の値に従って前記第１の２進木および前記第２の２進木をソートするステップと、
前記授与するステップ、前記更新するステップおよび前記ソートするステップを、次スケジューリングサイクル内のすべてのタイムスロットが授与されるか、または、もはやアクティブな論理リンクが存在しなくなるまで、繰り返すステップと、
前記第２の２進木に残っているすべてのリーフを前記第１の２進木に転送するステップと
を備える。
【００２０】
好ましくは、
前記要求されるタイムスロット値が、固定された最大値よりも大きい場合、いくつかのタイムスロットを授与する前記ステップは、現在授与されているタイムスロット値を前記固定された最大値だけインクリメントすることを含み、前記理論的送信時刻を更新する前記ステップは、前記理論的送信時刻を前記固定された最大値と論理リンクに関連付けられた重みの逆数との積と等価な値だけインクリメントすることを含み、前記要求されるタイムスロット値を更新する前記ステップは、前記要求されるタイムスロット値を前記固定された最大値だけデクリメントすることを含み、
前記要求されるタイムスロット値が固定された最大値よりも大きくない場合、いくつかのタイムスロットを授与する前記ステップは、現在授与されているタイムスロット値を前記要求されるタイムスロット値だけインクリメントすることを含み、前記理論的送信時刻を更新する前記ステップは、前記理論的送信時刻を前記要求されるタイムスロット値と論理リンクに関連付けられた重みの逆数との積と等価な値だけインクリメントすることを含み、前記要求されるタイムスロット値を更新する前記ステップは、前記要求されるタイムスロット値をゼロにセットすることを含む。
【００２１】
好ましくは、各論理リンクに、独立に固定された最大値が関連付けられる。
【００２２】
好ましくは、次スケジューリングサイクル内でいくつかのタイムスロットを前記第２の２進木のルートリーフに関連付けられた論理リンクに授与する前記ステップは、次サイクル内でスケジュールされた異なる論理リンクの数が、所与のサイクル内の異なる論理リンクの目標最大数未満である場合にのみ実行され、
前記方法は、前記第１の２進木および前記第２の２進木をソートする前記ステップより前に、
論理リンクがスケジュールされていない場合に、次サイクル内でスケジュールされた異なる論理リンクの数を１だけインクリメントするステップ
をさらに備える。
【００２３】
好ましくは、前記第２の２進木が空であり、次サイクル内でスケジュールされた異なる論理リンクの数が異なる論理リンクの目標最大数に達している場合、異なる論理リンクの目標最大数は、所与のサイクル内の異なる論理リンクの所定の初期最大数を、ある比率で乗算した値だけインクリメントされ、
前記比率は、次スケジューリングラウンド内のタイムスロットの総数に対する、次スケジューリングラウンド内でスケジュールされていない残りのタイムスロットの数の比率である。
【００２４】
好ましくは、前記ＲＥＰＯＲＴメッセージの受信に際し、前記非アクティブな論理リンクの理論的送信時刻を更新する前記ステップは、
他にアクティブな論理リンクが存在する場合、前記非アクティブな論理リンクの理論的送信時刻を、その論理リンクの現在の理論的送信時刻の値と、すべてのアクティブな論理リンクのうち最小の理論的送信時刻とのうちの最大値にセットすることと、
他にアクティブな論理リンクが存在しない場合、前記非アクティブな論理リンクの理論的送信時刻を、その論理リンクの現在の理論的送信時刻の値と、すべての論理リンクのうち直近の送信時刻とのうちの最大値にセットすることと
をさらに備える。
【００２５】
一実施形態では、前記授与するステップ、前記更新するステップおよび前記ソートするステップの各繰り返しは、スケジューリングサイクルの間、インターバルによって分離される。
【００２６】
好ましくは、各繰り返し間の前記インターバルは、直前の前記授与されたタイムスロット値を更新する前記ステップの間に、前記授与されたタイムスロット値に加えられた数のタイムスロットを送信するのに要する時間に等しい。
【００２７】
別の実施形態では、前記授与するステップ、前記更新するステップおよび前記ソートするステップの各前記繰り返しは、スケジューリングサイクルの終了時点で割り込みなく実行される。
【００２８】
好ましくは、各論理リンクはメモリコンテキストを備え、
前記メモリコンテキストは、関連付けられた論理リンクＩＤと、関連付けられた要求されるタイムスロット値と、関連付けられた授与されたタイムスロット値と、関連付けられた理論的送信時刻値とを含む。
【００２９】
好ましくは、前記理論的送信時刻（ＴＴＴｉ）は、前記第１の２進木および前記第２の２進木のリーフの、最上位ビット（複数）に符号化される。
【００３０】
好ましくは、前記第１の２進木および前記第２の２進木をソートする前記ステップは、理論的送信時刻値の符号付き比較を用いて実行される。
【００３１】
好ましくは、前記方法は、すべての非アクティブな論理リンクの理論的送信時刻を、定期的に、最小の理論的送信時刻値を持つアクティブな論理リンクの理論的送信時刻値にセットするステップをさらに備える。
【００３２】
また、本発明は、上述の方法を実行するために構成されたイーサネット受動光ネットワーク（ＥＰＯＮ）光回線終端装置（ＯＬＴ）を提供する。
【００３３】
また、本発明は、データ処理装置のためのコンピュータプログラム製品を提供する。このコンピュータプログラム製品は、データ処理装置にロードされたときに、装置に上記方法の各ステップを実行させる命令の組を含む。
【００３４】
当業者には理解されるように、本発明は従来技術に対していくつかの利益を提供する。たとえば、本発明は、いくつかの処理間で資源が共有されるプロセッサ上の進歩したスケジューリングアルゴリズムを効率的に実装する方法を提供する。本発明の第１の態様では、上りリンク上でサイクルが開始される前に各サイクルのスケジューリングが終了しなければならないので、スケジューリング処理はリアルタイムで実行される。このために、各動作は時間的に拘束され、進行中に（on the fly）実行される。要求される動作を効率的に実行するために、２つの２進木に基づくよく適合されたメモリ構造が用いられる。この構造は、エンベッドされたプラットフォームとともに用いられるときに有利である（メモリ使用量を低減するからである）。
【００３５】
本発明の第２の態様によれば、スケジューリング処理自体を実行可能とするために２つの異なる実施形態が提案される。第１のものでは、スケジューリング処理は、他のタスクが割り込み可能なバックグラウンドタスクとして実行可能である。第２の実施形態では、スケジューリング処理は、各サイクルの終了直前に全体が実行される。この場合、他の処理の割り込みは不可である。
【００３６】
マルチプロセッサ環境では、スケジューリング処理専用のプロセッサ資源は変動し得る。したがって、本発明の第３の態様では、提案される方法は、サービス品質や、上り論理リンクに対する全利用可能帯域幅に影響を与えることなく、資源利用可能性の変動に方法自体を適合させることができる。
【００３７】
本発明は任意のＯＬＴに実装することができ、既存のＩＥＥＥ標準規格にいかなる修正も要しない。これは、様々なＱｏＳ制約を持つサービスの共存を許容することにより、上りリンク上でユーザが経験するＱｏＳを改善するのに役立つ。利用可能なＣＰＵ資源に動的に適合する能力は、装置のコストを低減するために特に有利である。実際に、それは、他のタスク（制御、管理）と共有されるハードウェア上に実装することができ、専用ハードウェアに実装する必要がない。このため、超高速ネットワーク（１０Ｇ−ＥＰＯＮ標準規格等）にとくによく適合する。
【００３８】
本発明の他の利益および恩恵は、以下の記載および添付の図面を考慮することで明白となる。
【図面の簡単な説明】
【００３９】
【図１】本発明の一実施形態によって用いることができるシステムを表すブロック図である。
【図２】本発明の一実施形態によるキュー更新方法を表すフローチャートである。
【図３】本発明の一実施形態によるキューサービスサブルーチンを表すフローチャートである。
【図４】本発明の一実施形態によるキューサービス方法を表すフローチャートである。
【図５】図１のシステム上で実行される、いくつかのキューサービスラウンドの結果を示す図である。
【図６】本発明の一実施形態によるＴＴＴｉメンテナンスアルゴリズムの比較結果を表す図である。
【図７】本発明の一実施形態によるＴＴＴｉメンテナンスアルゴリズムの比較結果を表す図である。
【図８】本発明の一実施形態によるスケジューリングのランタイムを示す図である。
【図９】本発明の別の実施形態によるスケジューリングのランタイムを示す図である。
【発明を実施するための形態】
【００４０】
図１は、本発明の一実施形態によって用いられるシステムを表す機能ブロック図である。システムは、本発明による方法を実装するよう適合したＯＬＴ１を備える。ＯＬＴ１は複数のＯＮＵ２．１、２．２および２．３に接続され、各ＯＮＵはそれぞれのユーザ４．１、４．２および４．３に関連付けられる。理解されるように、１つのＯＮＵが複数のユーザのサービスを担当することができる。
【００４１】
ＯＬＴ１は、受動スプリッタ５を備えるＥＰＯＮを介してＯＮＵ２．１、２．２および２．３に接続される。受動スプリッタ５はＯＬＴ１からの光ファイバを複数の光ファイバに分割するためのものである。この複数の光ファイバのそれぞれは、論理リンク３．１１、３．１２、３．２１および３．３１に関連付けられる。たとえば、各論理リンクはあるサービスに関連付けることができる。本実施形態では、ＯＮＵ２．１が論理リンク３．１１および３．１２の両方を管理し、ＯＮＵ２．２が論理リンク３．２１を管理し、ＯＮＵ２．３が論理リンク３．３１を管理する。ＯＮＵは、論理リンクを介してタイムスロット内でデータパケットを送信するよう適合している。タイムスロットは、後述の方法で、ＯＬＴ１によってＧＡＴＥメッセージを介して定義される。ＯＮＵは、それぞれの送信タイムスロットの間にＯＬＴ１にＲＥＰＯＲＴメッセージを送信することができる。
【００４２】
この目的のために、ＯＬＴ１は、スケジューラ６と、サイクルビルダ７と、ネットワークインタフェース８とを備える。スケジューラ６およびサイクルビルダ７は、ＯＬＴからＲＥＰＯＲＴメッセージを受信している間、サイクルを構築するために前述のアルゴリズムを実行するよう適合している。サイクルにおいて、異なる論理リンク３．１１、３．１２、３．２１および３．３１内のデータパケットの送信のために、ＯＮＵ２．１、２．２および２．３に対してタイムスロットが公平な(fair)方法で割り当てられる。インタフェース８は、ＧＡＴＥメッセージのヘッドに論理リンクの識別子を含めるためにＧＡＴＥメッセージを構築し、またＯＮＵからＲＥＰＯＲＴメッセージを受信するよう適合している。
【００４３】
ＲＥＰＯＲＴメッセージおよびガード帯に起因するオーバヘッドを低減するための解決策は、各ＤＢＡサイクル内でスケジュールされまたはサーブされる論理リンクＬＬｉの数を低減することである。ＥＰＯＮ内でサポートされる論理リンクＬＬｉの総数を制限することなく、本方法は、従来技術の静的割り当て方法の代わりに、論理リンク送信機会の動的割り当て（または所与のＤＢＡサイクル内でのタイムスロット割り当て）を含む。このような解決策がオーバヘッドの全体的な低減をもたらす。
【００４４】
不公平なキュー方式を得ることを避けるために、この解決策では上り送信時間を増加させ、ＯＮＵがタイムスロットを割り当てられる前に数サイクル待つという前提のもとで、本発明は、各論理リンクＬＬｉに次時刻発信値（next time emission value）を導入する。次時刻発信値は、異なる論理リンクＬＬｉの間で公平さを保証する。
【００４５】
本発明の動作は、３つの基本的メモリ構造に依存する。第１の２進木（または主木）、第２の２進木（または副木）、および論理リンクコンテキスト（ＬＬＩＤコンテキスト）である。２進木は、高速なＴＴＴｉ順序付けに用いられるデータ構造であり、複数のリーフ（葉）（またはノード）を持ち、各「親」リーフは２個またはそれ以下の「子」リーフに接続される。「ルート」リーフは、子リーフではない親リーフである。上記の構造の組合せを用いることの主な利点のひとつは、大量のキャッシュメモリを要求することなく、広範な高速計算機能を許容することである。
【００４６】
２進木によって要求されるメモリの他に、管理されるＬＬＩＤそれぞれについてＬＬＩＤコンテキストが要求される。ＬＬＩＤコンテキストは、いくつかのフィールドを含むメモリのセクションである。各ＬＬＩＤコンテキストは、要求されるＴＱの数すなわちＲｅｑＴＱ，ｉ（すなわちＲＥＰＯＲＴメッセージの受信に際してセット可能であるもの）の数と、次のＤＢＡサイクルについてそのＬＬｉに現在割り当てられているＴＱの数（すなわちＧｒＴＱ，ｉの数）と、そのＬＬｉに対するＴＴＴｉの現在の値と、割り当てられた重みＷｉから導出される時間区間Ｔｉ（すなわち１／Ｗｉ）とを含む。Ｗｉは、論理リンクＬＬｉに授与される最小ビットレートｂｉを反映しており、時間区間ＴｉはＴＴＴｉをインクリメントするために用いられる。Ｗｉ（したがってＴｉ）は、管理者によって、論理リンク登録の際に静的にセットされるということに留意すべきである。このように、管理されるＬＬｉのそれぞれは、少なくとも上記のフィールドを含むＬＬＩＤメモリコンテキストを含む。他の実施形態では、他のフィールドが追加されてもよい。
【００４７】
第１の２進木の各リーフは、アクティブＬＬＩＤ（すなわちバックログされるＬＬ）と、それが関連付けられた次のＴＴＴｉとを表す。理解されるように、第１の２進木に対する基本的操作は、木の初期化、ルートリーフ（すなわち最小のＴＴＴｉを持つリーフ）の取得、木からのルートリーフの削除（これに木の再順序付けが続く）、木への新たなリーフの挿入（これにも木の再順序付けが続く）、あるリーフの他のリーフによる置換（これはＴＴＴｉ更新に有利に用いられ、これにも木の再順序付けが続く）である。２進木に対するこれらの操作の実行は、当業者により明確に理解される。
【００４８】
本実施形態によれば、第１の木の各リーフは、３２ビット符号なし整数によって表され、最下位１０ビットがＬＬＩＤを符号化し（これによって１０２４個のＬＬＩＤをサポートし）、残る２２ビットがＬＬＩＤのＴＴＴｉを符号化する。この符号化方式の結果、２進木アルゴリズムは、リーフの各部をマスクすることなく、直接的にリーフに対して作用することができる。また、２つのＬＬが同一のＴＴＴｉを持つ場合、本アルゴリズムはより小さいＬＬＩＤを持つＬＬを優先する。理解されるように、リーフを符号化する他の方法を用いてもよい。
【００４９】
ＲＥＰＯＲＴメッセージが受信されるたびに、本発明は、ＬＬＩＤコンテキストおよび第１の２進木の双方において、ＴＴＴｉおよびＲｅｑＴＱ，ｉの値を更新し、これに従って木を再順序付けする。
【００５０】
所与のＤＢＡサイクル内でスケジュールされるＬＬＩＤの数を制限するために、第２の２進木は、現在スケジュールされているＬＬＩＤを記憶する必要がある。第２の２進木の各リーフのメモリ構成は、上述の第１の２進木のものと同様である。第２の２進木の許容可能なサイズは、１つのＤＢＡフレームにおいてスケジュールされるＬＬＩＤの最大目標数に等しい。
【００５１】
スケジューリング処理は、主に、完全に独立かつ非同期の２つのステップに分割される。第１のステップは「キュー更新」と呼ばれ、ＲＥＰＯＲＴメッセージの到着の際に発生するものであり、ＯＬＴにおける上りＬＬＩＤキューの状態を更新することを担当する。第２のものは「キューサービス」と呼ばれ、次のサイクルの構成を決定する（すなわち、選択されたＬＬＩＤごとに授与される資源の量を決定する）責任を負う。
【００５２】
図２は、本発明の一実施形態による方法のキュー更新ステップのフローチャートを表す。
【００５３】
ステップＳ２０１において、ＯＬＴが管理するＯＮＵのひとつからそのＯＬＴがＲＥＰＯＲＴメッセージを受信した場合（このＲＥＰＯＲＴメッセージは論理リンクＬＬｉに関するものである）、スケジューラが次のアルゴリズムを実行する。ＲＥＰＯＲＴメッセージは更新されたキュー長さを含むことができ、これは論理リンクＬＬｉ上のデータパケットの送信のために必要なＴＱの数Ｍｉに対応してもよい。ＯＬＴは、所与の論理リンクＬＬｉにおいて送信すべきデータパケットに対応する各キューのイメージを記憶する。イメージキュー長はＲｅｑＴＱ，ｉと表記され、ＴＱで表される。
【００５４】
次に、スケジューラは、下記表２の動作を実行する。
【００５５】
【表２】
2013211848.tif 000004
【００５６】
ただし、ＴＴＴ−１は、ＥＰＯＮ内の論理リンクの１つによって直近のデータパケットが送信された時刻であり、ＭｉはＲＥＰＯＲＴメッセージにおいてＬＬｉが要求しているＴＱの数であり、ＧｒＴＱ，ｉは、次サイクルｋ＋１の間のデータパケットの送信のために、論理リンクＬＬｉに対して現サイクルｋの間に授与されたＴＱの数に対応する。サイクルｋ＋１の開始時に、ＧｒＴＱ，ｉはゼロに初期化される。
【００５７】
キュー更新の動作は図２に見ることができる。ステップＳ２０１において、ＲＥＰＯＲＴメッセージが、Ｍｉ（そのＲＥＰＯＲＴメッセージにおいてＬＬｉが要求しているＴＱの数）を含んで受信される。ステップＳ２０２において、ＬＬｉがアクティブである場合（すなわちＲｅｑＴＱ，ｉ≠０である場合）、ステップＳ２０６が実行され、ＲｅｑＴＱ，ｉが、Ｍｉの値からＧｒＴＱ，ｉ（次サイクルｋ＋１の間のデータパケットの送信ために論理リンクＬＬｉに対して現サイクルｋの間に授与されたＴＱの数）を減算することによって更新される。
【００５８】
一方、ＬＬｉが非アクティブである場合（すなわちＲｅｑＴＱ，ｉ＝０である場合）、ステップＳ２０３において新たなリーフが作成される。その後、ステップＳ２０４において、ＧｒＴＱ，ｉがヌルであるか否か、および、副木が満杯である(full)か否かについての判定が行われる。副木が満杯であるか、または、ＧｒＴＱ，ｉがヌルである場合、ステップＳ２０５においてそのリーフは主２進木に注入される。一方、ＧｒＴＱ，ｉがヌルではなく、副木に存在しているリーフの数がその木の最大サイズから１を減じた値を超えない場合には、ステップＳ２０６においてそのリーフは副２進木に注入される。
【００５９】
ステップＳ２０７において、そのＬＬｉが非アクティブであり、かつ少なくとも１つの他のＬＬｉがアクティブである場合、ステップＳ２０８が実行され、ＴＴＴｉは、現ＬＬｉの現ＴＴＴｉと、残るアクティブＬＬｉのＴＴＴｉの最小値とのうちの最大値に更新される。一方、ステップＳ２０７において他のＬＬｉがいずれもアクティブでないと判明した場合、ステップＳ２０９が実行され、現ＬＬｉのＴＴＴｉ値は、現ＬＬｉの現ＴＴＴｉ値と、すべてのＬＬｉのうち直近の送信時刻（すなわちＴＴＴ−１）とのうちの最大値にセットされる。
【００６０】
その後、別のアクティブなＬＬｉが存在するか否かに関わらず、ステップＳ２１０において、ＲｅｑＴＱ，ｉが、Ｍｉの値からＧｒＴＱ，ｉ（次サイクルｋ＋１の間のデータパケットの送信ために論理リンクＬＬｉに対して現サイクルｋの間に授与されたＴＱの数）を減算することによって更新される。
【００６１】
したがって、イメージキュー長ＲｅｑＴＱ，ｉは、データパケットをＭｉ個のＴＱだけ送信できるように、論理リンクＬＬｉに割り当てるべき残りのタイムスロットの数を表す。いくつかの実施形態では、ＴＴＴｉは絶対値であり、たとえば各論理リンクＬＬｉに対してゼロに初期化される。または、いくつかの実施形態では、論理リンクＬＬｉに対するＴＴＴｉはＴｉに初期化される。
【００６２】
理解されるように、上述のアルゴリズムは、ＲＥＰＯＲＴメッセージの受信前に非アクティブであり、かつデータパケットの送信にＭｉ個のＴＱを要求する論理リンクＬＬｉに対するＴＱの割り当てを優先する。実際に、ＥＰＯＮの少なくとも１つの論理リンクＬＬｉがアクティブである場合、その論理リンクＬＬｉに割り当てられるＴＴＴｉは、それに割り当てられた最後のＴＴＴｉと、残るアクティブな論理リンクＬＬｉのうち最小のＴＴＴｉ値とのうちの最大値に等しい。実際に、キューイング方式の公平さを尊重するため、非アクティブな論理リンクがデータを長時間転送しておらず、ＴＱが非常に高速にそれらに割り当てられるということが可能である。そうでない場合、その論理リンクＬＬｉに割り当てられるＴＴＴｉは、それに割り当てられた最後のＴＴＴｉと、ＥＰＯＮ内の論理リンクの１つによって直近のデータパケットが送信された時刻（すなわちＴＴＴ−１）とのうちの最大値に等しい。
【００６３】
ＲＥＰＯＲＴメッセージを送信している論理リンクＬＬｉがすでにアクティブである場合、イメージキュー長ＲｅｑＴＱ，ｉは、単純に、論理リンクＬＬｉによって要求されているＴＱの数Ｍｉから、現在スケジュールされているサイクルｋについて授与された資源の数ＧｒＴＱ，ｉを減算したものに等しい。論理リンクＬＬｉが非アクティブである場合、ＧｒＴＱ，ｉはゼロであり、ＲｅｑＴＱ，ｉ＝Ｍｉである。スケジューラは、イメージキュー長ＲｅｑＴＱ，ｉを更新した後、サイクルｋの間に受信される新たなＲＥＰＯＲＴメッセージを待つ（これはサイクルｋ−１の間にタイムスロット割り当てがスケジュールされたものである）。
【００６４】
提案する方法によれば、１つのＤＢＡフレーム内でスケジュールされるＬＬｉの数が制限されるので、１つのＤＢＡサイクル内で発生するキュー更新の数もまた限定され、したがってシステム性能の観点においてクリティカルなものとはならない。
【００６５】
本発明によれば、上述のアルゴリズムは、第１の２進木を、高速ＴＴＴｉ順序付けおよびＬＬＩＤコンテキストに関して更新することによって実施される。
【００６６】
本発明によって実施される第２の処理は、キューサービス動作であり、次サイクルの構成を準備するために、ＤＢＡサイクルの間に、継続的に実行され得る処理である。したがって、図３、４および５に示すように、１つのＤＢＡサイクルのスケジューリングが、１ＤＢＡサイクル先行して準備される。１つのＤＢＡサイクルの終了時点で、次のＤＢＡのスケジューリングが終了する。各キューサービスは独立したラウンドであり、ラウンドは、１つのＬＬＩＤを選択すること、要求されるＴＱの数（すなわちＲｅｑＴＱ，ｉ）と、割り当てられまたは授与されたＴＱの数（すなわちＧｒＴＱ，ｉ）とを更新すること、ＴＴＴｉを更新すること、ならびに、これらに従って第１の２進木および第２の２進木の値およびＬＬＩＤコンテキストを更新すること、からなる。
【００６７】
本発明の一実施形態によれば、各キューサービスラウンドはバックグラウンド処理として実装され、各ラウンドの実行に要する時間の長さが、そのラウンドの間に授与された数のＴＱを発信するのに要する時間に整合するように、各ラウンドの間に遅延が導入される。
【００６８】
１つのＤＢＡサイクル内のキューサービスラウンドの数は、サービス細分性値(service granularity value)に依存する。サービス細分性値は、各キューサービスラウンドで選択されたＬＬＩＤに対して授与されるバイト数の最大値である。１つのラウンドの間に授与されるＴＱの最大数をＳＧと表す。いくつかの実施形態では、各ＬＬｉが個別のＳＧの値（ＳＧｉと表す）を持つことができる（図示しない）。１つのＤＢＡサイクル内のスケジューリングキューサービスラウンドの数は、[リンク速度*TDBA/8]/SGにほぼ等しくすることができる。ただしＴＤＢＡはＤＢＡサイクル長である。理解されるように、ＤＢＡサイクル内のいくつかのＬＬｉについてＲｅｑＴＱ，ｉ＜ＳＧである場合には、より多くのキューサービスラウンドが可能である。
【００６９】
資源（すなわちＴＱ）の数は各ＤＢＡサイクルにおいて固定されているので、現サービスラウンド内で授与されたＴＱを発信するのに要する時間の後に次のキューサービスラウンドが発生するよう、スケジュールすることができる。本実施形態では、次のキューサービスラウンドの時間（ＴＱで表される）は、次のように計算可能である。
tk+1 = t0 + tk + min(SG,ReqTQi)
ただし、ｔ０は、そのＤＢＡサイクルの開始時点（したがって、現ＤＢＡサイクルに対する最初のキューサービスラウンドの時）として定義される。
【００７０】
各キューサービスラウンドについて、選択されたＬＬＩＤに授与されるバイト数を決定するために、次のサブルーチン（図３に示す）が適用される。このサブルーチンは、ＴＴＴｉ、ＧｒＴＱ，ｉおよびＲｅｑＴＱ，ｉの値を更新するためにも用いられる。
【００７１】
【表３】
2013211848.tif 000005
【００７２】
図３のアルゴリズムはステップＳ３０１で開始され、そこでは、要求される資源の量（すなわち要求されるＴＱの数、またはＲｅｑＴＱ，ｉ）が１ラウンドで授与され得るＴＱの最大数（すなわちＳＧ）より大きいか否かに関する判定が行われる。ＲｅｑＴＱ，ｉがＳＧよりも大きいと判定された場合、本方法はステップＳ３０３に進む。ステップＳ３０３では、そのＬＬｉのＴＴＴｉが、
‐ＴＴＴｉの現在の値、および
‐そのＬＬｉのＴｉ値と、１ラウンド内で授与され得るＴＱの最大数（すなわちＳＧ）との積
の和にセットされる。その後、ＤＢＡサイクルｋ＋１に対して授与されたＴＱの数（すなわちＧｒＴＱ，ｉ）が、現在授与されているＴＱの数（すなわちＧｒＴＱ，ｉ）と、１ラウンド内で授与され得るＴＱの最大数（すなわちＳＧ）との和に更新される。最後に、１ラウンド内で授与され得るＴＱの最大数（すなわちＳＧ）が、現在要求されているＴＱの量（すなわちＲｅｑＴＱ，ｉ）から除去される。
【００７３】
ステップＳ３０１において、ＲｅｑＴＱ，ｉがＳＧ以下であると判明した場合、本方法はステップＳ３０２に進む。ステップＳ３０２において、そのＬＬｉのＴＴＴｉは、
‐ＴＴＴｉの現在の値、および
‐そのＬＬｉのＴｉ値と、現在要求されているＴＱの量（すなわちＲｅｑＴＱ，ｉ）との積
の和にセットされる。その後、ＤＢＡサイクルｋ＋１に対して授与されたＴＱの数（すなわちＧｒＴＱ，ｉ）が、現在授与されているＴＱの数（すなわちＧｒＴＱ，ｉ）と、現在要求されているＴＱの数（すなわちＲｅｑＴＱ，ｉ）との和に更新される。最後に、ＲｅｑＴＱ，ｉがゼロにセットされる。ステップＳ３０２またはＳ３０３が完了した後、サブルーチンは終了する。
【００７４】
図３のアルゴリズムの結果は、図５に見ることができる。図５では、ＤＢＡサイクルｋにおいて入来するＲＥＰＯＲＴメッセージの内容に照らして、ＤＢＡサイクルｋ＋１を構築するために８つのキューサービスサイクルが実行される。キュー更新情報は図の上部にあり、キューサ−ビス情報は図の下部にある。
【００７５】
見られるように、ＤＢＡサイクルｋでは、３つのＬＬＩＤが資源を授与される。各送信の終了時点で、上述の方法に従ってキュー更新処理が実行される。この例では、ＬＬＩＤ＃１はＭｉ＝０を含むレポートメッセージを送信する。したがって、これにはＤＢＡラウンドｋ＋１においていかなる資源も割り当てられない。しかしながら、ＬＬＩＤ＃２は８０００ＴＱを要求し、ＬＬＩＤ＃３０００は３０００ＴＱを要求する。新たなレポートメッセージを受信するたびに、当該ＬＬＩＤに対するＴＴＴｉ値およびＲｅｑＴＱ，ｉ値が、図３の方法に従って更新される。たとえば、図５に見られるように、ＬＬＩＤ＃２に対して実行される第２のキューサービスラウンド（すなわちＲ２２）の結果として、ＬＬＩＤ＃２は５００ＴＱを授与され（ＧｒＴＱ，２＝１５００＋５００＝２０００）、要求されるＴＱの数は５００から０に減少する。しかしながら、その後、８０００ＴＱを要求するＬＬＩＤ＃２の送信の後にＲＥＰＯＲＴメッセージが到着したときには、要求されるＴＱの数は、上述のキュー更新アルゴリズムを用いて６０００にセットされる。実際に、ＲＥＰＯＲＴの到着時点でＧｒＴＱ，２は２０００に等しいので、キュー更新アルゴリズムを適用することにより、ＲｅｑＴＱ２は（８０００−２０００）に等しくなる。このＲｅｑＴＱ，ｉの増加は、キューサービスラウンドＲ３２の開始時点におけるＲｅｑＴＱ，ｉの初期値によって裏付けられる(evidenced)。この時点で、ＲｅｑＴＱ，ｉは６０００ＴＱから４５００ＴＱに変化する。理解されるように、図５の例ではＳＧの値は１５００ＴＱである。
【００７６】
従来技術による自己クロック型公平キューイング（Self-Clocked Fair Queuing）（ＳＣＦＱ）アルゴリズムに記載されるように、スケジュールされたＬＬＩＤはＴＴＴｉの値に従って選択される。従来技術によれば、最小のＴＴＴｉを持つバックログされるＬＬＩＤが選択される。
【００７７】
本発明によるＤＢＡサイクルごとのＬＬＩＤ制限を適用するために、現在スケジュールされているＬＬＩＤのＴＴＴｉを記憶および順序付けするために、副木が用いられる。スケジュールされたＬＬＩＤを選択して木を更新するための動作は、図４を参照して以下に記述される。ＴＴＴｉを順序付けするために２進木を用い、ルートリーフは最小のＴＴＴｉを持つＬＬＩＤを含む。キューサービスが実行されると、キューサービスの後に、木が新たに計算されたＴＴＴｉで更新されるか（リーフ置換）、または、ＬＬＩＤがバックログされなくなる（すなわち非アクティブになる）場合にルートリーフが除去される。
【００７８】
下記に説明されるとともに図４に示されるアルゴリズムを参照して、変数ｎＬＬＩＤは、次ＤＢＡサイクル内でスケジュールされた異なるＬＬＩＤの数を表し、ＮＬＬＩＤはＤＢＡサイクルあたりの目標最大ＬＬＩＤ数を表す。各ＤＢＡサイクルの開始時点でＮＬＬＩＤはＮの値にセットされる。ＮはＤＢＡサイクルに対する初期目標ＮＬＬＩＤを表し、システム管理者により固定される。
【００７９】
【表４】
2013211848.tif 000006
【００８０】
この処理は、ステップＳ４０１において、副２進木が空であるか否かに関する判定をもって開始される。第２の２進木が空でない場合、処理はステップＳ４０２、Ｓ４０３およびＳ４０４へと継続される。これらのステップでは、主２進木が空であるか否か（Ｓ４０２）、ＤＢＡサイクルｋ＋１内の異なるＬＬＩＤの数（ｎＬＬＩＤ）が、１ＤＢＡラウンド内で許容される異なるＬＬＩＤの最大数以上であるか否か（Ｓ４０３）、および、副２進木のルートリーフが主２進木のルートリーフより小さいか否か（Ｓ４０４）に関する判定が行われる。Ｓ４０２、Ｓ４０３およびＳ４０４のいずれかが肯定的に回答された場合、処理はステップＳ４０５へと継続し、操作のために副木のルートリーフが選択される。
【００８１】
その後、ステップＳ４０６において、ＧｒＴＱ，ｉがゼロより大きいか否か（すなわち、ＬＬｉがＤＢＡサイクルｋ＋１内ですでに割り当てられている資源を有するか否か）に関する判定が行われる。ＬＬｉが次サイクル内で割り当てられた資源（すなわちＴＱ）を有しない場合、それはサイクルｋ＋１内の新たなＬＬｉを表し、ステップＳ４０７においてｎＬＬＩＤが１だけインクリメントされ、その後ステップＳ４０８に進む。一方、ＬＬｉが次ＤＢＡラウンド内ですでに割り当てられている資源を有する場合には、ｎＬＬＩＤをインクリメントすることなく、処理は単にＳ４０８に進む。Ｓ４０８では、副木のルートリーフが図３のサブルーチンを実行するための基礎として用いられる（すなわち、そのＬＬｉについて、ＴＴＴｉ、ＧｒＴＱ，ｉおよびＲｅｑＴＱ，Ｉの値を更新する）。
【００８２】
サブルーチンが完了すると、ステップＳ４０９において、要求されるＴＱの現在の量（すなわちＲｅｑＴＱ，ｉ）がゼロより大きいか否か（言い換えると、ＬＬｉが、サブルーチン内である量の資源を授与された後に、さらに資源を要求しているか否か）に関する判定が行われる。さらなる資源が要求されている場合（すなわちＲｅｑＴＱ，Ｉ＞０である場合）、ステップＳ４１１において、副木のルートリーフが新たなＴＴＴｉで置換され、その後処理が終了する。一方、さらなるＴＱが要求されていない場合、副木のルートリーフはもはやアクティブではないので、ステップＳ４２０において単に除去され、その後処理が終了する。
【００８３】
ステップＳ４０１に戻る。副２進木が空である場合、処理はＳ４１２において継続する。同様に、ステップＳ４０２、Ｓ４０３およびＳ４０４のすべてにおいて回答が否定的である場合、処理はステップＳ４１２へと継続し、主木が空であるか否かに関する判定が行われる。主木が空である場合には、ステップＳ４０１において副木も空であると判定されているので、アクティブなリンクが存在しないという点において処理は終了する。
【００８４】
一方、主木が空でない場合、ステップＳ４１３において、将来の操作のために主木のルートリーフが選択される。その後、ステップＳ４１４において、ＧｒＴＱ，ｉがゼロより大きいか否か（すなわちＬＬｉがＤＢＡサイクルｋ＋１内ですでに割り当てられた資源を有しているか）に関する判定が行われる。ＬＬｉが次サイクル内で割り当てられた資源（すなわちＴＱ）を有していない場合、それはサイクルｋ＋１内の新たなＬＬｉを表し、ステップＳ４１５においてｎＬＬＩＤが１だけインクリメントされ、その後ステップＳ４１６に進む。一方、ＬＬｉが次ＤＢＡラウンド内ですでに割り当てられている資源を有する場合には、ｎＬＬＩＤをインクリメントすることなく、処理は単にＳ４１６に進む。Ｓ４１６では、主木のルートリーフが図３のサブルーチンを実行するための基礎として用いられる（すなわち、そのＬＬｉについて、ＴＴＴｉ、ＧｒＴＱ，ｉおよびＲｅｑＴＱ，Ｉの値を更新する）。
【００８５】
サブルーチンが完了すると、処理はステップＳ４１７において継続し、主木のルートリーフが除去される。その後、ステップＳ４１８において、ＬＬｉが将来のさらなるＴＱを要求している（すなわちＲｅｑＴＱ，ｉ＞０である）という判定が行われ、その後、ステップＳ４１９においてそのＬＬＩＤは副木に挿入される。言い換えると、ステップＳ４１７で主木のルートリーフが除去されたとき、それがさらなる資源を要求している場合には副木に挿入され、そうでなければ単に破棄される。
【００８６】
共有すべき資源がもはやなくなったとき（すなわち次サイクルが満杯である場合）、または、すべてのＬＬＩＤキューが空である場合（すなわちすべてのＬＬＩＤ要求に対する授与がなされた場合）には、スケジューリングは終点に到達する。前者のケースでは、その後、副木に残るすべてのリーフを主木に注入する必要がある。その後、システムは、満杯でないＧｒＴＱ，ｉを持つすべてのＬＬＩＤに対して、その値に基づいていくつかのＧＡＴＥメッセージを生成する。その後、すべてのＬＬＩＤに対するＧｒＴＱ，ｉ値がリセットされる。
【００８７】
副木の最大深さはｌｏｇ２（ＮＬＬＩＤ）に等しく、これは、ｌｏｇ２（ＬＬＩＤ最大値）に等しい主木の深さよりも小さい。結果として、副木に対する操作は、主木に対するものよりも高速である。このふるまいにより、単一２進木策に比べてスケジューリングサービス処理が加速される。ただし、資源要求をほとんど持たないＬＬＩＤが多数ある場合を除く。実際に、そのような場合には、各ＬＬＩＤは１つのスケジューリングサービスによりサービスされ、副木に入らない。
【００８８】
このアルゴリズムは、１つのＤＢＡフレーム内でスケジュールされるＬＬＩＤの最終的な数がＮＬＬＩＤより小さくなることを保証しない。しかしながら、このアルゴリズムは、ＮＬＬＩＤと、ＤＢＡサイクルの充填率（利用可能な資源をすべて使おうとする）と、ＬＬＩＤ間の公平性（スケジュールされるＬＬＩＤの数がＮＬＬＩＤよりも小さい間は、より小さいＴＴＴｉを持つＬＬＩＤが常に優先される）との間のトレードオフを実行する。上述のように、変数ｎＬＬＩＤは次ＤＢＡサイクル内でスケジュールされた異なるＬＬＩＤの数を表し、ＮＬＬＩＤはＤＢＡサイクルあたりの目標最大ＬＬＩＤ数を表す。各ＤＢＡサイクルの開始時点でＮＬＬＩＤはＮの値にセットされる。ＮはＤＢＡサイクルに対する初期目標ＮＬＬＩＤであり、システム管理者により固定される。
【００８９】
あるＤＢＡサイクルの間にｎＬＬＩＤが目標値（ＮＬＬＩＤ）に達し、副木が空である場合、ＮＬＬＩＤが次式を用いて増加される。
NLLID = NLLID + シーリング[N*(RemainingResource)/(ResourcePerDBACycle)]
ただし、RemainingResourceの値はＤＢＡラウンド（ｋ＋１）内でスケジュールされていないＴＱの数に等しく、ResourcePerDBACycleは１ＤＢＡサイクル内のＴＱの合計数である。
【００９０】
正当なリーフ値比較を保証するため、本発明の有利な一実施形態による２進木アルゴリズムは、ラップアップコヒーレンシー（wrap-up coherency）を確保するために、符号付き比較(signed comparison)を用いる。図６および図７は特定の値Ａに対する比較結果を示す。符号付き比較を用いることにより、陰付きでない半円内に位置するすべての値はＡより小さく、一方で、陰付きの半円内に位置するすべての値はより大きい。
【００９１】
Ａが、ｍｉｎＮＢ（ＴＴＴｉ）に、すなわちバックログされないＬＬに対するＴＴＴｉの最小値に等しい場合には、それらのバッグログされないＬＬはすべて陰付きの半円に含まれなければならない。アクティブなＬＬＩＤは定期的に選択され、それらのＴＴＴｉはｍｉｎ（ＴＴＴｉ）から開始して増加するので、アクティブなＬＬＩＤについてはこの想定は常に正しい。逆に、非アクティブなＬＬＩＤは更新されず、それらのＴＴＴｉが陰付きでない半円に該当し、長期の非アクティブ状態の後に、陰付きの半円に位置する場合がある。これは、符号付き比較が誤った結果を与えるので正当ではない。
【００９２】
これが、非アクティブなＬＬＩＤのＴＴＴｉを定期的にチェックし、アクティブなＬＬＩＤの最小ＴＴＴｉ値に更新するためにバックグラウンド処理が要求される理由である。実際に、非アクティブなＬＬＩＤがアクティブになるときには、少なくともｍｉｎＮＢ（ＴＴＴｉ）に等しいＴＴＴｉをもって木に挿入される。したがって、このＴＴＴｉの変更は、本発明によるＳＣＦＱアルゴリズムに影響を及ぼさず、実装は非常に効率的である。主な制約は、バックグラウンド処理によりすべての非アクティブ接続がスキャンされるスキャニング期間ＴＳｃａｎを定義することである。
【００９３】
重み付き公平キューイングアルゴリズム（Weighted Fair Queuing algorithms）において、ＴＴＴｉおよびＴｉは、ＥＰＯＮ時量子（Time Quantum）（ＴＱ）単位（１ＴＱ＝２バイト）で表現可能な、または、Ｎｕ個（複数）のＴＱとして表現可能な時間値である。この定義を用いて、あるＬＬＩＤにｋバイトが授与されるたびに、それに関連付けられたＴＴＴｉは次式を用いて更新されなければならない：
TTTi = TTTi + シーリング[k/2Nu] * Ti
ＴＳｃａｎ期間にわたって、ｍｉｎ（ＴＴＴｉ）の最大増加は [TScan.リンク速度/8]/2Nu に等しい（ＴＳｃａｎ期間の間、ただ１つのＬＬＩＤのみがアクティブである場合）。
【００９４】
ＮｂがＴＴＴｉを符号化するために用いられるビット数である場合、ＴＳｃａｎ期間にわたってすべての非アクティブなＬＬＩＤがチェックされる（２Ｎｂ−１バイトが授与されるまで）。そして、Nu ≧ [TScan.リンク速度/8]/ 2Nb である。
【００９５】
実装を便利にするため（除算をビットシフトで置き換える）、Ｎｕは２の累乗として選択することができる。たとえば、ＴＳｃａｎが５１２ｍｓにセットされている場合（１ｍｓごとに１ＬＬＩＤがポーリングされる）、１０ギガビットＥＰＯＮに対してはＮｕ＝２５６である。大きいＮｕ値を用いると、公平キューイング割り当てアルゴリズムにいくらかのジッタが生じる。しかしながら、このジッタは、ＤＢＡフレームあたりのＬＬＩＤの制限によって生じるジッタと比較して無視できると考えられる。
【００９６】
図８に示すように、本発明の第１の実施形態では、スケジューリングキューサービス処理は、前章で開示したように、ｔｋ法計算を用いてサイクル全体に定間隔で分散するバックグラウンド処理として実行される。この場合、各スケジューリングラウンドは原子的(atomic）かつ短い動作であり、ＣＰＵによって実行される他のタスクと容易にインタレース可能である。このような実施形態の主な利点は、他の処理を実行するために誘起されるジッタが１つのスケジューリングラウンドを実行するのに要する最大時間に限定されることである。たとえば、ある処理がシステムの他の部分からなんらかのデータを受信するとき（たとえばＲＥＰＯＲＴメッセージ）、そのような小さい遅延は、ＦＩＦＯ長を低減するためにリアルタイムオペレーティングシステムにとって非常に重要となる可能性がある。しかしながら、スケジューリングラウンドが発生するたびに実行コンテキストがリロードされ、これがオーバヘッドにつながる（キャッシュリローディング等）。
【００９７】
図９に示す第２の実施形態では、スケジューリングキューサービス処理はワンバーストで実行される。すなわち、すべてのスケジューリングサービスラウンドが、他のタスクによって割り込まれることなくＣＰＵによって実行される。この場合、スケジューリングサービスタスク全体を実行するのに要する時間ははるかに長くなり、他の処理を開始するためにより長いジッタを生じる。
【００９８】
しかしながら、タスクコンテキストのリローディングは必要ではなく、コードがＣＰＵの一次キャッシュに留まるので、より高速に実行される。さらに、ＲＥＰＯＲＴメッセージの受信に際しキュー更新が実行されるとき、いくつかの最適化を行うことができる。実際に、ＣＰＵによってＲＥＰＯＲＴメッセージが処理されるとき、スケジューリングサービス処理はいまだ開始されておらず、要求者ＬＬＩＤに対してなんらかの資源を直接割り当てることがより単純である。
【００９９】
１ＤＢＡサイクルの間に実行可能なスケジューリングラウンドの最大数は、利用可能なプロセッサ資源と、各ラウンドを実行するのに要する時間とに依存する。ｔSchRound,kをｋ番目のスケジューリングサービスラウンドを実行するのに要する時間とし、ｃSchRound,kを対応するＣＰＵサイクルの数とする（ｃSchRound,k = ｔSchRound,k * CPUSpeed）。ｃSchRound,kはｍａｘ（ｃSchRound,k）によって抑制する(bound)ことができ、その平均値はｍｅａｎ（ｃSchRound,k）と表すことができる。ＲSchRoundを、スケジューリングサービス処理専用のＣＰＵ資源の割合（たとえば５０％）とする。そうすると、持続時間ＴＤＢＡのＤＢＡサイクル１つ内の最大スケジューリングラウンド数は、TDBA * CPUSpeed * RSchRound/max(cSchRound,k) に等しい。上述のように、これは[リンク速度*TDBA/8]/SGで近似することができる。そうすると、スケジューリングサービス細分性値を、次式で求めることができる。
【０１００】
【数１】
2013211848.tif 000007
【０１０１】
ここで、細分性は、ＲSchRoundによって表される利用可能なプロセッサ資源に動的に適合させることができる。これはＲSchRoundに反比例するので、適合はリアルタイムで容易に実行可能である。細分性の変動は、光リンク上でより長いデータバーストを作成するので、ジッタを増加させる。しかしながら、これは他のＱｏＳパラメータ（平均遅延、帯域幅）には影響しない。さらに、これは大域スケジューリングを変更しない（すなわち、利用可能な帯域の全体が、バックログされる論理リンク間で共有され続ける）。
【０１０２】
理解されるように、本発明はコンピュータプログラム製品に埋め込むことも可能である。このコンピュータプログラム製品は、本明細書に記載される方法の実装を可能にするすべての機能を備えており、情報処理システムにロードされると、その情報処理システムを動作させる。本明細書のコンテキストにおけるコンピュータプログラム手段またはコンピュータプログラムとは、情報処理能力を有するシステムに対し、（直接的に、または他の言語に変換された後に）特定の機能を実行させることを意図する命令の組の、いかなる表現（いかなる言語、コードまたは表記法におけるものも）をも意味する。
【０１０３】
このようなコンピュータプログラムは、コンピュータ可読媒体または機械可読媒体（それらの媒体から読み出されるべきデータ、命令、メッセージまたはメッセージパケットおよび他の機械可読情報を許容するもの）上に記憶することができる。このコンピュータ可読媒体または機械可読媒体は、不揮発性メモリ（ＲＯＭ、フラッシュメモリ、ディスクドライブメモリ、ＣＤ−ＲＯＭおよび他の恒久的記憶装置等）を含むことができる。さらに、コンピュータ可読媒体または機械可読媒体は、たとえば揮発性記憶装置（ＲＡＭ、バッファ、キャッシュメモリおよびネットワーク回路）を含むことができる。さらに、このコンピュータ可読媒体または機械可読媒体は、一時的状態媒体（ネットワークリンクおよび／またはネットワークインタフェース（デバイスがそのようなコンピュータまたは機械可読情報を読み出すことを許容する有線ネットワークまたは無線ネットワークを含む））内のコンピュータまたは機械可読情報を含んでもよい。
【０１０４】
図面に示す要素の機能は、専用ハードウェアおよび／またはソフトウェアを用いて提供することができる。「処理」「処理手段」および「処理モジュール」という表現は、いかなるデジタル信号プロセッサ（ＤＳＰ）ハードウェア、ネットワークプロセッサ、アプリケーション専用集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、ソフトウェアを記憶する読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）および不揮発性記憶装置をも含むことができるが、これらに限定されない。
【図１】
2013211848.tif 000008
【図２】
2013211848.tif 000009
【図３】
2013211848.tif 000010
【図４】
2013211848.tif 000011
【図５】
2013211848.tif 000012
【図６】
2013211848.tif 000013
【図７】
2013211848.tif 000014
【図８】
2013211848.tif 000015
【図９】
2013211848.tif 000016
【外国語明細書】
2013211848.tif 000017
2013211848.tif 000018
2013211848.tif 000019
2013211848.tif 000020
2013211848.tif 000021
2013211848.tif 000022
2013211848.tif 000023
2013211848.tif 000024
2013211848.tif 000025
2013211848.tif 000026
2013211848.tif 000027
2013211848.tif 000028
2013211848.tif 000029
2013211848.tif 000030
2013211848.tif 000031
2013211848.tif 000032
2013211848.tif 000033
2013211848.tif 000034
2013211848.tif 000035
2013211848.tif 000036
2013211848.tif 000037
2013211848.tif 000038
2013211848.tif 000039
2013211848.tif 000040
2013211848.tif 000041
2013211848.tif 000042
2013211848.tif 000043
2013211848.tif 000044
2013211848.tif 000045
2013211848.tif 000046
2013211848.tif 000047
2013211848.tif 000048
2013211848.tif 000049
2013211848.tif 000050
2013211848.tif 000051
2013211848.tif 000052
2013211848.tif 000053
2013211848.tif 000054