(57)【特許請求の範囲】
【請求項１】
複数のソースに関して記憶された情報に基づいて、複数のソースから複数の宛先に向かってデータ通信システム内を通過する情報単位を処理する時間ベース・カレンダと、
複数のソースに関して記憶された情報に基づいて、複数のソースから複数の宛先に向かってデータ通信システム内を通過するその他の情報単位を処理する時間に依存しないカレンダと、
前記カレンダの一方から出力宛先に向かって単一情報単位を移動させる信号を定期的に生成するタイマであって、記憶している規則に基づいてその単一情報単位が選択されているタイマとを含む装置。
【請求項２】
前記時間に依存しないカレンダが情報単位のフローを処理し、各フローをキューに入れ、そのフローを処理した後でキュー内の他の場所にそのフローを移動させ、フローが時間ベース・カレンダ内に場所を有していたかどうかを判定し、切断および再接続の結果として、時間ベース・カレンダ内にこのような場所を有していたフローが時間ベース・カレンダ内のより恵まれた場所を達成しないようにするメカニズムをさらに含む、請求項１に記載の装置。
【請求項３】
前記時間に依存しないカレンダが情報単位のフローを処理し、各フローをキューに入れ、移動を待っている一連のフレームと、各フレームの重み係数およびサイズと、時間に依存しないカレンダによって１つのフレームを移動した後でそのフレームの重み係数およびサイズに基づいてそれぞれのフローの新しい位置を計算するメカニズムとを提供する、請求項１に記載の装置。
【請求項４】
情報単位が複数のソースから複数の宛先に向かってデータ通信システム内を通過するにつれて、サービス用のキューにデータ・フローを順番に入れるステップと、
データ・フローがキュー内に前の位置を有していたかどうかを判定するステップと、
データ・フローがキュー内に前の位置を有していた場合に、割り当てられると思われる新しい位置が前の位置より有利であるかどうかを判定するステップと、
割り当てられると思われる新しい位置がより有利である場合に、前の位置を使用してフローを処理するステップと、
前の位置が割り当てられると思われる新しい位置より有利ではない場合に、新しい位置を使用してフローを処理するステップとを含む方法。
【請求項５】
情報単位が複数のソースから複数の宛先に向かってデータ通信システム内を通過するにつれて、サービス用のキューにデータ・フローを順番に入れるステップと、
処理の準備ができている情報単位のそれぞれに関する優先順位情報を受け取るステップと、
各情報単位に関連する優先順位情報に基づいて、処理の準備ができている各情報単位を複数の優先順位付きキューの１つに入れるステップであって、１つのキューが時間ベースであり、もう１つが時間に依存しないステップと、
記憶している１組の規則に基づいて処理するために、一連のクロック・サイクルのそれぞれについて、キューの１つを選択するステップと、
一連のクロック・サイクルのそれぞれについて、選択したキューから１つの情報単位を選択するステップと、
選択した情報単位を宛先に向かって前方へ通過させるステップとを含み、
前記一連のクロック・サイクルのそれぞれについて、選択したキューから１つの情報単位を選択するステップが、加重公平キューから選択すること、および、情報単位のサイズと選択した単位の重み係数に基づいて加重公平キュー内の新しい位置を計算することを含む方法。
【請求項６】
情報単位が複数のソースから複数の宛先に向かってデータ通信システム内を通過するにつれて、サービス用のキューにデータ・フローを順番に入れるステップと、
記憶している規則に基づいて、データ・フローによるピーク・バースト伝送を可能にすべきかどうかを判定するステップとを含む方法であって、前記規則が、
データ・フロー用の初期クレジットを計算すること、
時間の経過とともに、また、データのフロー・レートがそのデータ・フロー用に設定したしきい値以下のままになったときに、そのクレジットに加えること、
時間の経過とともに、また、データのフロー・レートがそのしきい値を超えたときに、そのクレジットから差し引くこと、および、
クレジット値を使用して、所与の時期にピーク・バースト伝送が許されるかどうかを判定することを含む方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、様々なタイプおよび機能の情報処理システムまたはコンピュータを互いにリンクするために使用するような通信ネットワーク装置に関し、また、このような装置におけるデータ処理のための構成要素および方法に関する。本発明は、複数のネットワーク処理ユニットに結合されたフロー制御システムからＭＡＣを介してデータ伝送ネットワークに向かう情報単位の配布をスケジューリングするための改良されたシステムおよび方法を含む。より詳細には、本発明は、可変サイズの情報パケットまたはフレームを処理している複数のユーザを扱うことが可能なスケジューリングを含み、複数の異なる優先順位を異なるユーザに与えられるようにしながら、フロー制御システムからデータ伝送ネットワークに向かって供給されるフレームに秩序を提供する。
【０００２】
【従来の技術】
以下に示す本発明の説明は、読者がネットワーク・データ通信およびこのようなネットワーク通信で有用なルータおよびスイッチに関する基礎知識を有するという前提に基づくものである。特に、この説明では、ネットワーク・オペレーションを複数のレイヤーに分割する国際標準化機構（「ＩＳＯ」）モデルのネットワーク・アーキテクチャに精通していることを前提とする。このＩＳＯモデルに基づく典型的なアーキテクチャは、物理経路または媒体であるレイヤー１（「Ｌ１」と呼ぶこともある）から延び、それを介して信号はレイヤー２（または「Ｌ２」）、レイヤー３（または「Ｌ３」）などを通って、ネットワークにリンクされたコンピュータ・システムに常駐するアプリケーション・プログラミングのレイヤーであるレイヤー７まで上に向かって渡される。本明細書全体を通して、そのようなレイヤーをＬ１、Ｌ２、Ｌ３と称する場合は、ネットワーク・アーキテクチャの対応するレイヤーを指し示すものとする。また、この説明は、パケットおよびフレームとして知られ、ネットワーク通信で使用されるビット・ストリングに関する基本的理解に基づくものである。
【０００３】
今日のネットワーク・オペレーションに鑑みて、帯域幅に関する考慮事項（またはシステムが単位時間に処理できるデータの量）は重要なものになっている。ネットワーク上のトラフィックは、純然たるボリュームとトラフィックの多様性の両面で増加し続けている。主に、電話網上の音声やデータ伝送ネットワーク上のディジタル・データなど、所与のタイプの通信トラフィックのために一度にいくつかのネットワークが使用されていた。当然のことながら、電話網はまた、音声信号に加えて限られた量の「データ」（経路指定および請求のための発呼側番号および着呼側番号など）を搬送することになるが、いくつかのネットワークの主な用途は、ある時点では、実質的に均質なパケットであった。
【０００４】
インターネット（ワールドワイド・ウェブまたは「ｗｗｗ」と呼ばれることもある、緩くリンクした複数のコンピュータからなる公衆ネットワーク）や、専用データ伝送ネットワークで見られるその内部類似物（イントラネットと呼ぶこともある）の普及率が高まった結果、トラフィックが大幅に増加した。インターネットおよびイントラネットは、情報および新興アプリケーションへのリモート・アクセスの増大し続ける必要性を満たすために、リモート・ロケーション間で大量の情報の伝送を必要とする。インターネットは、地理的に分散している多数のユーザに、爆発的に増加するリモート情報を開放し、ｅコマースなどの様々な新しいアプリケーションを可能にし、それにより、ネットワークにかかる負荷が非常に増加した。ｅメール、ファイル転送、データベース・アクセスなどのその他のアプリケーションは、ネットワークに対してさらに負荷を追加するものであり、そのうちの一部は高レベルのネットワーク・トラフィックによりすでに重圧を受けている。
【０００５】
音声およびデータ・トラフィックも現在、ネットワーク上に集中している。データは現在、インターネット上で（インターネット・プロトコルまたはＩＰにより）無料で伝送されており、音声トラフィックは通常、最低コストの経路をたどる。ボイス・オーバーＩＰ（ＶｏＩＰ）やボイス・オーバー非同期転送モードまたはＡＴＭ（ＶｏＡＴＭ）またはボイス・オーバー・フレーム・リレー（ＶｏＦＲ）は、現在の環境で音声トラフィックを伝送するための費用効果の高い代替策である。このようなサービスが広がるにつれて、業界は、コスト構造の変化などの問題ならびにプロセッサ間の情報伝送におけるサービス・コストとサービス品質の兼ね合いに関する懸念に対処することになる。
【０００６】
サービス品質の諸側面としては、容量または帯域幅（ある時間枠でどのくらいの情報に対処できるか）、応答時間（１つのフレームを処理するのにどのくらいの時間を要するか）、その処理がどの程度フレキシブルか（各種カプセル化またはフレーム・ヘッダ方法などの各種プロトコルおよびフレーム構成に対応するか）を含む。ある資源を使用するものは、提示された状況に応じた兼ね合いにより、サービス品質ならびにサービス・コストを考慮することになる。あるユーザにとって様々な各種優先順位またはスケジューリング・アルゴリズムが可能になることは望ましいことであり、ユーザは自分が保証帯域幅、ベスト・エフォート、ピークに関するベスト・エフォート付き保証帯域幅のいずれを望んでいるのか（また、そのいずれに関連する料金を支払うつもりなのか）を決定する。さらに、帯域幅を割り振るためのシステムが、ユーザが選択し支払ったものを超過するユーザ容量を否定することにより、ユーザによって選択された優先順位および帯域幅を実施するためのシステムを有することは望ましいことである。
【０００７】
いくつかの従来技術のシステムは、様々な方法で処理システムからの発信情報単位を処理する。１つの提案は、１組のキューの間で公平なラウンドロビン・スケジューラを使用することである。もう１つの提案では、数通りのレベルの優先順位と、それぞれについて１つのキューとを使用する。このようなシステムには絶対優先順位があり、最高優先順位の作業が最初に処理され、最低優先順位の作業は決して処理されない可能性がある。出力をスケジューリングする、さらにもう１つの方法は、複数の優先順位付きリストを含む。階レイヤーパケット・スケジューリング・システムを使用することも知られている。各種スケジューリング技法の組合せを使用し、データ伝送ネットワークに向かって情報単位を送出する順序を決定する際に、数通りのスケジューリング方法を使用するシステムすら存在する。
【０００８】
他のシステムではラウンドロビンの形で実現された加重優先順位技法を使用しているが、これは、サービスのレベルを定義するアルゴリズムに基づいて、すべてのキューを処理するものであり、一部のキューは他のキューより頻繁に処理される。このような加重優先順位システムでは、それに割り当てられたサービス・レベルを継続的に上回るユーザにサービスを提供することになり、たとえあまり多くなくても、割り当てられたサービス・レベルを超える場合でさえ処理し続け、システムがあるレベルのサービス方針を実施することが困難になるだろう。
【０００９】
どの顧客を処理すべきかを決定する際にパケットまたはフレームのサイズを考慮すると、公平さの尺度がサービス・システムに追加されるが、これは、大型フレームを処理しているユーザがシステム容量以上を占めており、したがって、小型フレームを備えたユーザより低い頻度でサービスを受けることになるからである。従来技術のシステムの一部では資源を割り振る際に伝送サイズを考慮するが、他のシステムではそれを考慮しない。一部の通信システムでは均一の固定サイズのパケットを使用しており、パケット・サイズの考慮が不要になるが、他のシステムでは資源を割り振る際にパケットのサイズを考慮しない。
【００１０】
他の従来技術のシステムは、いわゆる非同期転送モード（またはＡＴＭ）システムのように、共通サイズになっている情報単位の処理を対象とするので、現行の情報単位または今後の情報単位の優先順位を決定する際に情報単位のサイズは考慮されない。重み主導のスケジューラを備えたＡＴＭシステムは、ＡＴＭシステムからの出力をスケジューリングするために従来技術で知られている解決策の１つである。
【００１１】
【発明が解決しようとする課題】
このようなシステムでは、フレーム・サイズにかかわらず所与の保証帯域幅を顧客に割り振るようなシステム上の制約に対処するとともに、保証帯域幅を超えるピーク入力に対処し、一方、システム・パラメータの大きく持続的な超過に関する保護を可能にしながら効率よくかつ公正にネットワーク・プロセッサの能力を使用してデータ伝送ネットワークに出力を提供するという、追加の特徴を実現するためのメカニズムを提供することは望ましいことだろう。
【００１２】
望むように各種タイプおよびレベルのサービスを可能にするのに最大のフレキシビリティを備えたシステムを用意することは望ましいことだろう。たとえば、一部のユーザは最小帯域幅を希望し、他のユーザは最小帯域幅を希望するもののバーストを見込んでいる可能性があり、さらに他のユーザは最小帯域幅の有無にかかわらず「ベスト・エフォート」サービスを可能にするエコノミー・サービスに関心を有している可能性があり、帯域幅またはバースト・サイズに関する制限はスケジューリング・システムによって実施可能なものでなければならない。可変パケット長に対処し、未使用帯域幅を割り振る加重公平キュー化システムを可能にする単純かつ効率のよいシステムにおいて、スケジューリング・システムがこのような特徴の一部または全部を備えることができれば望ましいことだろうが、残念ながら、このようなシステムは従来技術には存在しない。
【００１３】
また、フロー・キューが切断し再接続したとき、それが切断し再接続していなければ有していたであろうよりも良好な優先順位またはキュー内の配置を達成しないことが望ましい。
【００１４】
さらに、スケジュールを計算する際に、それが処理された後で所与のフローについてスケジュール内の新しい場所を求める複雑な計算に関連するハードウェア・コストを回避するように、単純かつ効率のよいシステムが実現されることが望ましい。
【００１５】
したがって、ネットワークへの伝送のためにデータ・パケットを処理するための従来技術のシステムは望ましくない欠点および制限を有し、その欠点および制限はシステムの多様性またはシステムが動作可能な速度のいずれかに影響する。
【００１６】
【課題を解決するための手段】
本発明は、処理システムから出る情報単位またはフレームを処理し、データ伝送ネットワークへのディスパッチのためにフレームを出力ポートに向けるための単純であるが効果的な方法を提供することにより、従来技術のシステムの欠点および制限を克服するものである。本発明は、複数のユーザからの可変長のパケットが処理され、少なくとも一部のユーザに対し、あるレベルのサービス・コミットメントが行われているシステムに特に応用可能である。
【００１７】
本発明により、システムの各種ユーザに対してなされる複数タイプのサービス・レベル契約またはコミットメントの使用が可能になる。すなわち、他のユーザが共用帯域幅を享受している間に、あるユーザに対して最小保証帯域幅を提供可能であり、ピーク帯域幅は限られた持続期間の間、許可可能であり、あるユーザに対して最大バースト・レベル・サービスを提供可能であり、いずれもプログラミング通りであり、他のユーザに提供されるサービスに干渉しない。
【００１８】
本発明は、帯域幅資源の効率のよい使用が可能になり、残りの帯域幅を効率よく公正に使用できるようにしながらサービス・レベル・コミットメントを果たすことができるという利点を有する。
【００１９】
また、本発明は、バーストに対処しながら資源割振りを実施するという利点も有する。すなわち、ユーザは、限られた時間枠の間、自分の定義帯域幅を超えるバースト・レートで何らかの量のトラフィックを伝送することができるが、そのユーザが長期間の間、それを行う場合、そのユーザは、過度の使用を補償してしまうまで自分の通常帯域幅を超過する伝送が禁じられる。これは、それぞれのユーザが自分の帯域幅全体を使用していなかった間に蓄積した、そのユーザのフロー・キュー用の「クレジット」のシステムにより実施される。
【００２０】
本発明により、処理したフローのためにキュー内の新しい位置の計算をサポートするために、除算を実行しない単純な計算が可能になる。
【００２１】
また、本発明は、切断および再接続時に、所与のフローがその切断によって改善された位置に達しないという利点も有する。
【００２２】
本発明は、スロット距離を使用してフレームのサイズおよびキューの重みに合わせて調整し、次の位置を迅速かつ容易に計算することができるようにする。
【００２３】
また、本発明は、バーストの使用のランニング・スコアを維持し、使用可能な「クレジット」を計算して維持し、無理ない範囲のバーストを可能にするが、使用法に関するシステム制約を実施する。
【００２４】
また、本システムは、所与のタイム・スロットまたはサイクルについてスケジューリングされたサービスを求める最新要求に対し優先順位が与えられる、後入れ先出しスタックを提供するという利点も有する。これは、より遅くスケジューリングされるユーザの方がより高い優先順位を有していなければならず、そのユーザを処理する際の遅延は、より低い優先順位のユーザを処理する際の同様の遅延よりパーセンテージの大きい遅延になるという想定に基づくものである。スロット要求を果たすためにこの後入れ先出し（ＬＩＦＯ）システムを使用することにより、システムは、システムが過負荷になったとき、すなわち、スケジューリングした時期に処理可能な作業より多くの作業を有するときに、連続するサービス間の通常間隔のパーセンテージとして認識されたサービス遅延を最小限にすることができる。
【００２５】
【発明の実施の形態】
好ましい実施形態の以下の説明では、本発明者にとって現在既知であり、本発明を実施する最良の実施例について、ある程度詳細に説明する。しかし、この説明は、特定の実施形態において本発明の概念を大ざっぱかつ一般的に教示するものであるが、特に、当業者であれば、添付図面に関連して図示し説明する特定の構造および動作に対する多くの変形および変更を理解できるので、本実施形態に示すものに本発明を制限するためのものではない。
【００２６】
図１は、基板１０と、その基板上に集積された複数のサブアセンブリとを含む、インタフェース装置チップのブロック図を示している。このサブアセンブリは上側構成と下側構成に配置され、「上側」構成（「入」と呼ぶこともある）はデータ伝送ネットワークからチップに（チップまでまたはチップ内に）到着するデータに関連する構成要素を指し、「下側」（「出」と呼ぶこともある）はその機能がチップからデータ伝送ネットワークに向かってアウトバウンド方式で（チップから外へまたはネットワーク内に）データを送信することである構成要素を指す。データ・フローは上側構成と下側構成のそれぞれの配置をたどり、したがって、図１のシステムには上側データ・フローと下側データ・フローが存在する。上側または入構成エレメントとしては、エンキュー・デキュー・スケジューリングＵＰ（ＥＤＳ−ＵＰ）論理回路１６と、複数の多重化ＭＡＣ−ＵＰ（ＰＭＭ−ＵＰ）１４と、スイッチ・データ・ムーバ−ＵＰ（ＳＤＭ−ＵＰ）１８と、スイッチ・インタフェース（ＳＩＦ）２０と、データ位置合せシリアル・リンクＡ（ＤＡＳＬ−Ａ）２２と、データ位置合せシリアル・リンクＢ（ＤＡＳＬ−Ｂ）２４とを含む。本発明の好ましい実施形態はデータ・リンクを使用するが、本発明は好ましい実施形態で使用するデータ・リンクなどの特定の補助装置に限定されないので、他のシステム、特に、比較的高いデータ・フローおよびシステム要件をサポートするものを使用して本発明により利益を得ることができることを理解されたい。
【００２７】
システムの下側（または出）に示す構成要素としては、データ・リンクＤＡＳＬ−Ａ２６およびＤＡＳＬ−Ｂ２８と、スイッチ・インタフェースＳＩＦ３０と、スイッチ・データ・ムーバＳＤＭ−ＤＮ３２と、エンキュー・デキュー・スケジューラＥＤＳ−ＤＮ３４と、出ＰＭＭ−ＤＮ用の複数の多重化ＭＡＣ３６とを含む。また、基板１０は、複数の内部スタティック・ランダム・アクセス・メモリ構成要素（Ｓ−ＲＡＭ）と、トラフィック管理スケジューラ（トラフィックＭＧＴスケジューラ、出スケジューラとも呼ぶ）４０と、組込みプロセッサ複合体１２も含む。インタフェース装置３８は、それぞれのＤＭＵバスによってＰＭＭ１４、３６に結合されている。インタフェース装置３８は、イーサネット（Ｒ）物理（ＥＮＥＴ  ＰＨＹ）装置または非同期転送モード・フレーミング機器（ＡＴＭフレーマ）など、Ｌ１回路に接続するための任意の適当なハードウェア装置にすることができ、そのいずれも、この業界で周知であり、一般にこの目的のために使用可能な装置の例である。インタフェース装置のタイプおよびサイズは、少なくとも部分的に、本チップおよびそのシステムが取り付けられたネットワーク・メディアによって決定される。このチップが使用するために、複数の外部ダイナミック・ランダム・アクセス・メモリ・デバイス（Ｄ−ＲＡＭ）および１つのＳ−ＲＡＭが用意されている。
【００２８】
ここでは、関連のスイッチングおよび経路指定装置の外部の一般的なデータ・フローがビル内に取り付けられたワイヤおよびケーブルなどの導電体を通って渡されるネットワークに関して詳細に開示されているが、本発明は、ネットワーク・スイッチおよびその構成要素がワイヤレス環境でも使用可能であることを企図するものである。たとえば、ここに開示されているメディア・アクセス制御（ＭＡＣ）エレメントは、シリコン・ゲルマニウム技術により作られるものなどの適当な無線周波装置で置き換えることができ、その結果、開示されている装置がワイヤレス・ネットワークに直接接続されることになるだろう。このような技術を適切に使用すれば、当業者により本明細書に開示されているＶＬＳＩ構造に無線周波エレメントを集積することができる。あるいは、ワイヤレス・ネットワーク装置とともに有用なスイッチ装置を達成するために、本明細書に開示されている他のエレメントとともに、赤外線（ＩＲ）応答装置などの無線周波その他のワイヤレス応答装置をブレード上に取り付けることができる。
【００２９】
矢印は、図１に示すインタフェース・システム内の一般的なデータ・フローを示している。ＥＮＥＴ  ＰＨＹブロック３８を出てＤＭＵバスを介してイーサネット（Ｒ）ＭＡＣ１４から受け取ったデータまたはメッセージのフレーム（パケットまたは情報単位と呼ぶこともある）は、ＥＤＳ−ＵＰ装置１６により内部データ・ストア・バッファ１６ａに入れられる。このフレームは通常フレームまたは誘導フレームのいずれかとして識別することができ、それは複数のプロセッサ内の後続処理の方法および位置に関連する。組込みプロセッサ複合体内の複数のプロセッサの１つによって入力単位またはフレームが処理された後、完了した情報単位はスイッチに送られ、ネットワーク・プロセッサの入側に送達される。ネットワーク・プロセッサの入側で情報単位が受け取られると、その情報単位は組込みプロセッサ複合体内の複数のプロセッサの１つによって処理され、出処理が完了すると、その情報単位は処理ユニット１０からのスケジューラ４０によってスケジューリングされ、ＰＭＭ−ＤＮ多重化ＭＡＣ３６および物理レイヤー３８によりデータ伝送ネットワーク上に送られる。
【００３０】
図２は、本発明を使用して利益を得ることができる処理システム１００のブロック図である。この図２では、複数の処理ユニット１１０がディスパッチャ・ユニット１１２と完了ユニット１１４との間に位置する。各出フレームＦ（本データ処理システムに取り付けられたスイッチ（図示せず）からのもの）は受け取られてＤＯＷＮデータ・ストア（またはＤＮ  ＤＳ）１１６内に記憶され、次に、ディスパッチャ１１２によって順次取り除かれ、そのフレームを処理するためにその処理ユニットが使用可能であるというディスパッチャ１１２による判定に基づいて、複数の処理ユニット１１０の１つに割り当てられる。ディスパッチャ１１２と複数の処理ユニット１１０との間には、ハードウェア分類器アシスト機構１１８が挿入されている。複数のネットワーク・プロセッサ１１０によって処理されたフレームは完了ユニット１２０に入り、そのユニットはフロー制御システムによりＤＮエンキュー３４に結合されている。ＤＮエンキュー３４はＰＭＭ  ＤＮ  ＭＡＣ３６を介し、次にＤＭＵデータ・バスにより物理レイヤー３８（データ伝送ネットワークそのもの）に結合されている。
【００３１】
図３のスケジューラ４０は、単一統一スケジューラ・システムにおいて最小帯域幅アルゴリズム、ピーク帯域幅アルゴリズム、加重公平キュー化技法、および最大バースト・サイズ・スケジューリングによりネットワーク処理ユニットからデータ伝送ネットワークへのフレーム伝送をスケジューリングする機能を可能にする構造および動作方法を提供する。
【００３２】
最小帯域幅およびベスト・エフォート・ピーク・レート要件を備えたパケットをスケジューリングするために、時間ベース・カレンダを使用する。図３に示すように、このために３つの時間ベース・カレンダを使用するが、２つは最小帯域幅用であり、第３のカレンダはフロー・キューを最大ベスト・エフォート・ピーク・レート（ピーク帯域幅成形）に制限するために使用する。最小帯域幅用に用意された２つのカレンダ（ＬＬＳおよびＮＬＳ）により、最小帯域幅ＱｏＳクラス内の各種クラスのサービス（すなわち、低待ち時間および通常待ち時間）のサポートが可能になる。
【００３３】
前述のカレンダでは、ポインタを使用してそのカレンダ内でのフロー・キューの位置を表す。さらに、システム内の複数のカレンダには、単一フロー・キューを指すこのようなポインタが何もない場合もあれば、１つまたは２つ存在する場合もある。通常、カレンダ内のポインタは、初期設定していないフロー・キューまたは空のフロー・キューを表すことはない。システム内のカレンダにフロー・キューを指すポインタがある場合、そのフロー・キューはカレンダ「内」にあると言うことができる。
【００３４】
時間枠はscheduler_tickと定義する。各scheculer_tickの間、１単位分の帯域幅に対応することができる。好ましい実施形態では、この単位を「ステップ」と定義し、バイトあたりの時間単位（すなわち、１／帯域幅）を有する。
【００３５】
ある通信システムでは、各フロー・キューの最小帯域幅指定の範囲は複数桁にわたることになる。すなわち、一部のユーザ（または実際にはそのユーザ用の関連キュー）は高い帯域幅を有することになる。というのは、そのユーザは、大量のデータを伝送しており、その帯域幅の代金を支払っているが、他のユーザはいつでもより少ない量の情報（帯域幅）を送信するための経済的な提供品を選んでいるからである。この目的専用のハードウェアの量を最小限にするために、好ましい実施形態では、通信システムおよびサービス・レベル契約（ＳＬＡ）が要求する範囲および正確さを維持しながら、より少ないハードウェアの使用を可能にするスケーリング技法を使用する。
【００３６】
図４に示すように、好ましい一実施形態の各タイマ・ベース・カレンダは４つの「エポック」から構成される。各エポックは５１２個のスロットから構成される。各スロットはフロー・キューを指すポインタのＬＩＦＯスタックを含む。任意の２つのスロット間の距離は帯域幅の測定値であり、その値はエポックに依存する。図４に示す好ましい実施形態では、各エポック間に１６という倍率が存在する。好ましい実施形態では、１５０ｎｓのscheduler_tick期間が選択されており、したがって、エポック０では１スロット分の距離は１５０ｎｓの間に移動した５１２バイトの帯域幅または約２７Ｇｂ／ｓを表し、エポック３では１スロット分の距離は０．６１４ｍｓの間に移動した５１２バイトの帯域幅または約６．６７Ｍｂ／ｓを表す。
【００３７】
一実施形態で使用するエポックあたりのスロット数とエポック数は、ハードウェア・コストと設計の複雑さとの兼ね合いであり、本発明の範囲を制限するためのものではない。当業者にとって明らかになるように、エポックと、エポック間の倍率と、エポックあたりのスロット数との様々な組合せは、本発明の精神を逸脱せずに変更することができる。
【００３８】
現在時は現行のスケジューラ・システム時間の値を維持するレジスタである。このレジスタはscheduler_tickあたり１回増分される。好ましい実施形態の現在時レジスタの範囲は、タイマ・ベース・スケジューラの範囲の４倍になるように選択されている。このため、フロー・キュー制御ブロックで見つかるタイム・スタンプ・フィールドの１つ（すなわち、NextRedTimeまたはNextGreenTime）と現在時とを比較したときに現在時ラップを決定することができる。
【００３９】
動作
図５は、本発明のスケジューラの動作を流れ図形式で示している。現行ポインタは、各エポック内のサービス・ロケーションを示すために使用する。各scheduler_tickの間に、現行ポインタが示すスロットを検査する。そのスロットが空であると分かった場合、現行ポインタは次の非空スロットまたは現在時に対応するスロットに進むことができる。ただし、スロット間の距離はエポック間で様々なので、現行ポインタは、現在時に「追随」しながら各種レートで各エポックを進んでいくことに留意されたい。そのスロットが非空であると分かった場合、フロー・キューエポック候補が検出される。各エポックは独立して、フロー・キューエポック候補が見つかったかどうかを判定する。図４に示すように、フロー・キューカレンダ候補は絶対優先順位選択の使用により複数のエポック候補の中から選択されるが、最小番号のエポックが最初に選択される。図４に示すように、選択順序は以下の通りである。
１．エポック０
２．エポック１
３．エポック２
４．エポック３
【００４０】
フロー・キュー・エポック候補が選択されると、フロー・キュー・ポインタはＬＩＦＯスタックからデキューされる。このデキュー・アクション後に現行ポインタが示すスロットが非空であると分かった場合、現行ポインタは未変更のままになる。このデキュー・アクション後に現行ポインタが示すスロットが空であると分かった場合、現行ポインタは、次の非空スロットまたは現在時に対応するスロットまたはそのスロットからデキューされたフロー・キューがフロー・キュー・サービス・アクションによって移動されたスロットに進むことができる。現行ポインタは、このような可能な距離のうち最短の距離を移動する。
【００４１】
図３に示すスケジューラ・システムは、複数のフロー２１０と、時間ベース・カレンダ２２０、２３０、２５０と、加重公平キュー化（ＷＦＱ）カレンダ２４０と、ターゲット・ポート・キュー２６０から構成される。
【００４２】
フロー２１０は、割当て、すなわち、関連ユーザが選択し支払を行っているサービス・レベルに基づく共通システム特性を共用する複数フレームの順序付きリストを維持するために使用する制御構造である。このような特性としては、最小帯域幅、ピーク帯域幅、ベスト・エフォート帯域幅、最大バースト・サイズ・サービス品質（ＱｏＳ）要件を含む。好ましい実施形態では、通信システム用のＱｏＳをサポートするためにセットアップされたフロー・キューに加え、フレーム（すなわち、フィルタ処理されたトラフィック）を廃棄し、ネットワーク・プロセッサ・システムの出から入へフレーム・データをラップするために定義されたフロー・キューを必要とする。
【００４３】
時間ベース・カレンダ２２０、２３０、２５０は、最小帯域幅およびベスト・エフォート・ピーク・レート要件を備えたパケットをスケジューリングするために使用する。図３に示すように、このために３つの時間ベース・カレンダを使用するが、２つのカレンダ２２０、２３０は最小帯域幅用であり、第３のカレンダ２５０はフロー・キューを最大ベスト・エフォート・ピーク・レート（ピーク帯域幅成形）に制限するために使用する。２つの時間ベース・カレンダ２２０、２３０（一方のカレンダ２２０は低待ち時間サービスまたはＬＬＳとして識別され、もう一方のカレンダ２３０は通常待ち時間サービスまたはＮＬＳとして識別される）は最小帯域幅に備えるものであり、最小帯域幅ＱｏＳクラス内の各種クラスのサービス（すなわち、低待ち時間および通常待ち時間）のサポートを可能にするものである。
【００４４】
加重公平キュー化（ＷＦＱ）カレンダ２４０は、（時間ベース・カレンダ２２０、２３０の一方と組み合わせて使用した場合）ベスト・エフォート・サービスおよびベスト・エフォート・ピーク・サービスに使用する。さらに、ＷＦＱカレンダ２４０は、ベスト・エフォート・サービスＱｏＳクラス内の各種サービス・クラスのサポートを可能にするキュー重みをサポートする。好ましい実施形態には、サポートしているメディア・ポート（出力ポート）の数に対応する４０個のこのようなＷＦＱカレンダが存在する。４０個のこのようなポートの選択は、ハードウェア・コストと設計の複雑さとの兼ね合いであり、本発明の範囲を制限するためのものではない。
【００４５】
前述のカレンダのそれぞれでは、そのカレンダ内のフロー・キューの位置を表すためにポインタ（フローＩＤ）を使用する。したがって、図３の矢印が示すように、フロー０はカレンダ２２０内にそのフローＩＤ２２１を有し、フロー１はカレンダ２３０内のフローＩＤ２３２とＷＦＱ２４０内のフローＩＤ２４１を有し、フロー２０４７はカレンダ２３０内のフローＩＤ２３１とカレンダ２５０内のフローＩＤ２５１を有する。さらに、システム内の複数のカレンダには、単一フロー・キューを指すこのようなポインタが何もない場合もあれば、１つまたは２つ存在する場合もある。通常、カレンダ内のポインタは、初期設定していないフロー・キューまたは空のフロー・キューを表すことはない。システム内の特定のカレンダにフロー・キュー（またはフローＩＤ）を指すポインタがある場合、そのフロー・キューはその特定のカレンダ「内」にあると言うことができる。
【００４６】
ターゲット・ポート・キューは、共通ポート宛先および優先順位を共用する複数フレームの順序付きリストを維持するために使用する制御構造である。好ましい実施形態では、各種サービス・クラスのサポートを可能にするために、メディア・ポート（または出力ポート）あたり２通りの優先順位、すなわち、いわゆる高優先順位ターゲット・ポート・キューといわゆる低優先順位ターゲット・ポート・キューが用意されている。２通りの優先順位の選択は、ハードウェア・コストと設計の複雑さとの兼ね合いであり、本発明の範囲を制限するためのものではない。さらに、好ましい実施形態は、個別のラップキュー２７２と廃棄ポート・キュー２７０とを含む。
【００４７】
時間ベース・カレンダ２２０、２３０、２５０のそれぞれは複数のエポックから構成され、オーバラップする矩形で表すように図３のそれぞれについて４つのエポックが示されている。図４は、そのエポック用の典型的なタイミング構成とともに４つのエポック３０２、３０４、３０６、３０８を示しており、第１のエポック３０２（エポック０と示す）はスケジューラ目盛りのステップを有し（この場合、１５０ｎｓｅｃごとに５１２バイトが可能である）、第２のエポック３０４は第１のエポック３０２のステップの１６倍のステップを有し、第３のエポック３０６は第２のエポック３０４と同じ比率を有し、第４のエポック３０８は第３のエポックと同じ比率を有する。このため、第１のエポック３０２は高優先順位を有し（第２のエポック３０４の１６倍の頻度でサービスのスケジューリングが行われる）、関連するコスト増を有することになるサービス優先順位の階レイヤーを作成する。現行ポインタ（たとえば、エポック３０２の場合の３１２）は、キュー内でその処理が現在位置する場所に関するポインタを提供するために各エポックに関連づけられている。エポックによる処理の本システムでは現行ポインタを増分することになっているので、処理の方向はそのエポック内で低い方から高い方に向かう。また、この図４には、現在時３２０と、クロック３２０を駆動すると同時に各エポック内のステップを駆動するスケジューラ目盛り３３０も示されている。
【００４８】
この優先順位選択は絶対優先順位選択であり、任意の間隔中に１つしか処理できないので、最高優先順位のものを処理することを意味する。各エポックの現行ポインタが１つのデータ・フローを指す場合、最低のもの（エポック０）を処理することになる。エポック０がいかなるサービスも必要としない場合、エポック１を処理し、次にエポック２などを処理する。
【００４９】
図６は、図４の各エポックごとのビットの時間分解能を示している。すなわち、本書で後述するように、現在時ストア（２３ビット・カウンタ）内のどのビットが各エポックに関連づけられているかを示している。
【００５０】
図７は、あるユーザからの通信のパラメータを示している。使用する帯域幅はＹ軸上に示し、時間はＸ軸上に示す。ユーザは、矢印３５０でマークが付けられた持続帯域幅が割り当てられている可能性があり、バーストの幅３７０が示す持続期間の間、矢印３６０でマークが付けられたピーク・バースト帯域幅を有することが許される可能性がある。時間３８０中に帯域幅がないことが示す遅延または静止時間は、ピーク・バースト帯域幅を使用するための代価として賦課される可能性があり、本書で詳しく後述するようにＭＢＳとして知られるクレジットの使用により実施される可能性がある。
【００５１】
キューが空になると、そのキューは切断という形でカレンダから除去される。どのカレンダにも入っていないキューがフレームを送信し始めると、それは接続（または以前フレームを送信していたキューの復帰の場合は再接続）と呼ばれるプロセスで新しいキューとして扱われる。切断し、その後、再接続するプロセスは、そのキューがラインの先頭、それぞれの処理後に計算された優先順位で引き続いていればあったであろうところより前に進むという望ましくない結果をもたらす可能性がある。
【００５２】
現在時から時間ベース・カレンダ位置への変換
現在時と、エポック間の倍率と、各エポックに使用するスロット数を検査することにより、現在時をタイマ・ベース・カレンダ内の位置に変換する。好ましい実施形態では、倍率は１６であり、各エポックに５１２個のスロットがあるので、そのエポック内の位置を識別するには各エポックごとに９ビットが必要である。図６に示すように、ビット８〜０はエポック０内の位置を定義するために使用し、ビット１２〜４はエポック１に使用し、ビット１６〜８はエポック２に使用し、ビット２０〜１２はエポック３に使用する。
【００５３】
フロー・キューを追加する際のＷＦＱカレンダ内の位置の決定
本発明は、重みまたは優先順位とフレームの長さに基づいてキュー内の次のサービスの順序を決定する式により、共用するユーザとともに、最小帯域幅顧客に不要な帯域幅をベスト・エフォート・ベースで使用できる、加重公平キューの使用を企図するものである。
【００５４】
フロー・キューにパケットをエンキューし、そのフロー・キューをＷＦＱに追加すると、図３のＷＦＱカレンダ２４０内の位置は以下のいずれかの方法で決定される。
１．ＷＦＱカレンダの現行ポインタが示す位置に追加する。
２．ＷＦＱカレンダの現行ポインタが示す位置の直前の位置に追加する。
３．フロー・キューの重みＱＤを使用して、現行ポインタが示す位置からの距離を決定する。
【００５５】
好ましい実施形態では、フロー・キューの重みを使用して、フロー・キューが位置することになり、現行ポインタが示す位置からの距離を決定する。この距離計算は以下の形式を有する。
スロット距離＝Ｍｉｎ（（ＱＤ＊Ｓ），１）
式中、Ｓは、任意の正の整数値を帯びることができる倍率である。好ましい実施形態の倍率Ｓは１６である。
【００５６】
現在時からNextGreenTimeへの変換
NextGreenTimeは、（ピーク帯域幅成形カレンダと組み合わせて）ピーク帯域幅成形を可能にするためにＷＦＱカレンダ２４０が使用するタイム・スタンプ・フィールドである。現在時をNextGreenTime（好ましい実施形態ではNxtGT.V、NxtGT.E）に変換するには、フロー・キュー制御ブロックのピーク・サービス・レート・フィールドの検査が必要である。
【００５７】
好ましい実施形態では、PSD.Eの値を使用し、以下に示すようにNxtGT.Vフィールドのために現在時から使用するビットを決定する。
PSD.E              現在時ビット
０                  ８〜０
１                  １２〜４
２                  １６〜８
３                  ２０〜１２
NxtGT.Eは、PSD.Eの値に等しくなるように設定される。
【００５８】
NextRedTimeまたはNextGreenTimeと現在時との比較（テスト以降）
好ましい実施形態では、以下のステップは、フロー・キュー制御ブロックからのタイム・スタンプと現在時との比較を可能にする方法を構成する。
１．比較を実行するために現在時からのビットを選択する。この設定には、比較すべきタイム・スタンプ（NextRedTimeまたはNextGreenTime）からの「ドットＥ」フィールドの検査が必要である。
ドットＥ            現在時ビット
０                  ８〜０
１                  １２〜４
２                  １６〜８
３                  ２０〜１２
２．「Ａ」が「Ｂ」より後であるかどうかを判定するために、まずＢの２の補数を形成し、次にその結果をＡに加え、その演算からのいかなる繰上がりも無視する。その結果が非ゼロであって、その結果の最上位ビット０である場合、ＡはＢより後になり、そうではない場合、ＢはＡより後になる。
【００５９】
NextRedTimeまたはNextGreenTimeから時間ベース・カレンダ内の位置への変換
フロー・キュー制御ブロック内のタイム・スタンプ・フィールドは、フロー・キューがそのサービス・パラメータに違反するのを防止する方法の一部として機能する。好ましい実施形態の「ドットＥ」フィールドはエポックを示し、「ドットＶ」フィールドはそのエポック内の位置０からの距離を示す。
【００６０】
フローがピーク・レートに違反しているときのNextGreenTimeの計算（ベースとしてNextGreenTimeを使用）
好ましい実施形態では、フローがそのピーク・レートに違反しているときのNextGreenTimeの計算はＢＣＩを検査することによって決定され、これはバイト単位のパケット長と、ピーク・サービス・レートと、NextGreenTimeの現行値とを決定するものである。図８のＦＬは、ＢＣＩから決定したフレームのバイト長を表している。このプロセス・ブロックについては以下に説明する。
【００６１】
プロセス２は、NextGreenTimeとピーク・サービス・レートの両方について倍率（ドットＥ）が同じである場合のスロット距離計算（Temp）である。
【００６２】
プロセス４は、ピーク・サービス・レートの倍率がNextGreenTimeの倍率より大きい場合のスロット距離計算（Temp）である。
【００６３】
プロセス５は、ピーク・サービス・レートの倍率がNextGreenTimeの倍率より小さい場合のスロット距離計算（Temp）である。
【００６４】
プロセス７は、スロット距離（Temp）が現行倍率の容量より大きい場合のNxtGT.V値とNxtGT.E値の計算である（好ましい実施形態の場合、ドットＶの値は５１１を超えることができない）。
【００６５】
プロセス１０は、スロット距離（Temp）により現行倍率の低減が可能になる場合のNxtGT.V値とNxtGT.E値の計算である。倍率が小さいほど時間ベースがより正確になるので、これは望ましいものである。
【００６６】
プロセス１１は、スロット距離（Temp）が現行倍率の変更を必要としないかまたはスロット距離（Temp）により現行倍率の変更が可能にならない場合のNxtGT.V値の計算である。NxtGT.Eの値は未変更のままになる。
【００６７】
フローがピーク・レートに違反していないときのNextGreenTimeの計算（ベースとして現在時を使用）
好ましい実施形態では、フローがそのピーク・レートに違反していないときのNextGreenTimeの計算はＢＣＩを検査することによって決定され、これはバイト単位のパケット長と、ピーク・サービス・レートと、現在時とを決定するものであり、図９に示す。このプロセス・ブロックについては以下に説明する。図９のＦＬは、ＢＣＩから決定したフレームのバイト長を表している。
【００６８】
プロセス２１はスロット距離計算（Temp）である。プロセス・ブロック２３、２５、２７、２９では、ピーク・サービス・レートに使用する倍率に基づいて、現在時レジスタ内のビットからベース時間（BaseT）の値を割り当てる。NextGreenTimeは、スロット距離、倍率、ベース時間から決定することになる。
【００６９】
プロセス３１は、スロット距離（Temp）が現行倍率の容量より大きい場合のNxtGT.V値とNxtGT.E値の計算である（好ましい実施形態の場合、ドットＶの値は５１１を超えることができない）。
【００７０】
プロセス３４は、スロット距離（Temp）により現行倍率の低減が可能になる場合のNxtGT.V値とNxtGT.E値の計算である。倍率が小さいほど時間ベースがより正確になるので、これは望ましいものである。
【００７１】
プロセス３５は、スロット距離（Temp）が現行倍率の変更を必要としないかまたはスロット距離（Temp）により現行倍率の変更が可能にならない場合のNxtGT.V値とNxtGT.E値の計算である。
【００７２】
ＭＢＳ獲得クレジットの計算
好ましい実施形態では、非ゼロの最大バースト・フィールドとともに使用中のフロー・キュー（QinUse＝１）は、そのフロー・キューが空であるときにトークンを獲得する。MBSCreditフィールドは、その空のフロー・キューにパケットがエンキューされたときに更新される。獲得したトークンの数を決定するため、NextRedTimeおよび現在時を検査し、それを図１０に示す。
【００７３】
NextRedTimeが使用する倍率に基づいて、プロセス・ブロック３０２、３０３、３０５、３０７で現在時からのビットを選択し、フロー・キューが空であった長さを決定するために使用するスケーリング済み時間（TimeA）を作成する。
【００７４】
判断ブロック３０８では、TimeAがNextRedTimeタイム・スタンプ・フィールドが示す時間より後であるかどうかを判定する。NextRedTimeをこの目的に使用するには、フロー・キューが次に可能なスケジューリング時間後も空のままになっている必要がある。TimeAがNextRedTimeより後ではない場合、それ以上のアクションは一切行われない。
【００７５】
判断ブロック３０９では、タイマ・ラップ・ケースを取り扱い、プロセス・ブロック３１１および３１０においてフロー・キューがトークンを蓄積する期間（TimeT）の計算が可能になる。
【００７６】
プロセス・ブロック３１３、３１５、３１６はMBSCredit.Vに関する最終計算である。判断ブロック３１２および３１４では、ＭＢＳフィールドを定義するために使用する倍率による調整がTimeTに必要であるかどうかを判定する。
【００７７】
使用するＭＢＳクレジットの計算
MBSCreditの新しい値は、MBSCreditの現行値と、フレーム長を決定するためのＢＣＩと、持続サービス・レートから決定される。持続レートの使用は、ＭＢＳ値を計算する際に使用する方法による（式から複雑な除算を取り除いたもの）。好ましい実施形態のMBSCreditは、負の値を帯びることができる。このプロセス・ブロックについては以下に説明する。図１１のＦＬは、ＢＣＩから決定したフレームのバイト長を表している。
【００７８】
プロセス・ブロック４０２、４０４、４０５は、長さＦＬのフレームに使用するトークンの数を決定するものである。判断ブロック４０１および４０３は、MBSCreditフィールドを定義するために使用する倍率による調整がTempに必要であるかどうかを判定するために使用する。
【００７９】
プロセス・ブロック４０６は、使用するトークンの数だけ、MBSCredit.Vの値を調整する。
【００８０】
フロー・キュー制御ブロックの経時
フロー・キュー制御ブロックで倍率を使用すると、タイム・スタンプ・フィールドの維持に必要なハードウェアが削減される。タイム・スタンプが古すぎて適切ではない時期を正確に判定するために、タイム・スタンプ・フィールドと残りのフィールドが有効ではないことを示す方法が必要になる。図１２および図１３は、そのタイム・スタンプがもはや有効ではないフロー・キュー制御ブロックにマークを付ける方法を示している。
【００８１】
スケジューラ・システムには、現在使用中の（QinUse＝１）すべてのフロー・キュー制御ブロックのリストが追加される。当業者には、このようなリストを維持する方法が多数あることが分かっている。
【００８２】
好ましい実施形態では、タイム・スタンプ・フィールドのドットＶフィールドは２ビットだけ拡張されている。この追加ビットは、タイム・スタンプ・フィールドが更新されたときに現在時ポインタから取られる。現在時ポインタから使用するビットは、図６に示すようにドットＥフィールドの値によって決まり、以下に示す通りである。
ドットＥ            使用する現在時ビット
０                  １０〜９
１                  １４〜１３
２                  １８〜１７
３                  ２２〜２１
【００８３】
フロー・キュー制御ブロックをチェックするプロセスが行われる時期を決定するために、タイマを使用する。図１２を参照すると、この方法は、「経時サービス目盛り」のチェックから始まる。これが真である場合、プロセスは引き続き、５０２で経時リストからフロー・キュー制御ブロック（ＱＣＢ）を選択する。プロセスは引き続き、５０３で、選択したフロー・キュー制御ブロックのQinUseフィールドをチェックする。
【００８４】
フロー・キュー制御ブロックが使用中ではない場合、プロセスは５０１に戻って次のサービス目盛りを待ち、そうではない場合、プロセスは引き続き、５０４で持続サービス・レート・フィールドを検査し、５０５でQinRedフィールドを検査する。フロー・キューが持続サービスの指定を備えており、フロー・キューがＬＬＳまたはＮＬＳのいずれのカレンダにもない（QinRed＝０）場合、５０６で経時の決定が行われる。「TestAge」のために行われるアクションについては以下に説明する。
【００８５】
フロー・キューが持続サービス・レートの指定を備えていない場合、５０７でピーク・サービス・レート・フィールドが検査される。ピーク・サービス・レートが一切指定されていない場合、プロセスは５０１に留まって次のサービス目盛りを待つ。ピーク・サービス・レートが指定されている場合、フロー・キュー制御ブロックを検査し、５０８でフロー・キューがＷＦＱカレンダにあるかまたは５０９でピーク帯域幅成形カレンダにあるかを判定する。フロー・キューがいずれか一方にある場合、プロセスは５０１に戻り、そうではない場合、５１０で経時の決定が行われる。「TestAge」のために行われるアクションについては以下に説明する。
【００８６】
図１３に示すTestAgeは、フロー・キュー制御ブロックのタイム・スタンプ・フィールドの１つと現在時を入力として使用する。これは、QinUseフィールドの状態に対する更新をプロセスに返す。流れ図５では、この結果を５１２および５１３で使用して、フロー・キュー制御ブロックを更新し、経時リストからフロー・キュー制御ブロックを除去する。
【００８７】
図１３に戻ると、TestAgeプロセスは倍率Ｅを使用し、タイム・スタンプ・フィールドが古すぎてその有用性を保持できなくなっているかどうかを判定するために現在時のどのビットを使用するかを決定する。ブロック６００〜６０６によりこのタスクが実施される。
【００８８】
引き続き６０６および６０７では、ドットＶフィールドの上位ビット（上記で定義し、図３に示すＭＭビット）と現在時から選択したビットとの比較を行う。６０７および６０８のテストでは、タイム・スタンプに関連するエポックが最後の更新以降に複数回ラップしたかどうかを判定する。複数回のラップが行われた場合、そのタイム・スタンプはもはや使用不能であり、QinUseビットをゼロにセットするアクションによってタイム・スタンプ・フィールドに無効のマークが付けられ、そうではない場合、QinUseビットは未変更のままになる（ブロック６０９、６１０）。
【００８９】
加重公平キュー化（ＷＦＱ）カレンダはいわゆる「ベスト・エフォート」サービスに使用し、時間ベース・カレンダと組み合わせて使用する場合はいわゆる「ベスト・エフォート・ピーク」サービスに使用する。すなわち、ベスト・エフォート・サービスはいかなる保証帯域幅（すべての単位時間についてｘビット分の帯域幅が提供される）も取得しないが、保証帯域幅顧客に対応した後に残っている帯域幅について他のユーザと競合する。これは、保証帯域幅より低レベルのサービスであり、通常はかなり安価である。いわゆる「ベスト・エフォート・ピーク」サービスは、ユーザが加入している保証サービス・レベルを上回る要件のために、資源上の過剰帯域幅を競合共用できるようにする。したがって、ユーザは、合計ピーク・サービスが１５Ｍビットのサービスになるように、毎秒１０Ｍビットのサービスとともに、追加５Ｍビットのピーク用のベスト・エフォートを購入することができるだろう（最後の５Ｍビットのサービスは、それが使用可能であり、加重公平キュー化の他のユーザとの公平な共用によってそれが可能になる場合に限り、提供されるものである）。
【００９０】
さらに、ＷＦＱカレンダは、ベスト・エフォート・サービスＱｏＳクラス内の各種サービス・クラスのサポートを可能にする、キュー重みをサポートしている。ここで使用するキュー重みは、所与のユーザのサービス・レベルに基づいてそのユーザに割り当てられる相対優先順位である。このキュー重みは、このシステムに関連して説明した加重公平キュー化システムにおけるサービス間の遅延の量に関連する。図３に示す好ましい実施形態には、サポートしているメディア・ポートの数に対応する４０個のこのようなＷＦＱカレンダが存在する。４０個のこのようなポートの選択は、ハードウェア・コストと設計の複雑さとの兼ね合いを伴う自由裁量による設計選択であり、本発明の範囲を制限するためのものではない。
【００９１】
周期（またはクロック間隔）はscheduler_tickとして定義され、これは、アクセス中のハードウェアの応答時間に応じて１５０ナノ秒または１６５ナノ秒のいずれかに達するが、設計パラメータおよびハードウェア機能に応じてより長いかまたは短い周期にもなりうる。scheduler_tickの間、サービスのためにフロー・キューを選択する。記載した選択アルゴリズムの結果として、最小帯域幅指定（持続サービス・レート）を備えたすべてのフロー・キューがサービスを必要としない（すなわち、スケジューラによって管理される、残りの帯域幅がＷＦＱカレンダによる使用のために用意されている）ときにＷＦＱカレンダが選択される。他の方法では、時間ベースキュー２２０、２３０がスケジューリングされ、送信すべき情報を有する場合、各クロック間隔中にその時間ベースキューが処理され、そうではない場合、クロック間隔中にＷＦＱキュー２４０が処理される。ネットワーク・プロセッサの全最小帯域幅を管理可能なタイマ・ベース・スケジューラとは対照的に、各ＷＦＱカレンダは１つのターゲット・ポート用のベスト・エフォート帯域幅を管理する。ＷＦＱカレンダまたはキュー２４０の目的は、競合するフロー・キュー間でこのベスト・エフォート帯域幅を公平に共用することである。これは、サービス用に選択したフロー・キューによって送信されるバイト数を調節し、送信バイト数に基づいてその現在の位置からある距離だけカレンダ内のフロー・キューを移動させることによって実施される。すなわち、フローがscheduler_tickの間に送信するバイト数が増えるほど、次のサービスまでにカレンダの上の方に移動する（さらに介在するフローが増加し、周期が長くなる）。
【００９２】
図１４に示す好ましい一実施形態では、ＷＦＱカレンダ２４０ａは５１２個のスロットから構成される。各スロットはフロー・キューを指すポインタのＬＩＦＯスタックを含む。一実施形態で使用するスロット数は、ハードウェア・コストと設計の複雑さとの兼ね合いであり、本発明の範囲を制限するためのものではない。
【００９３】
さらに図１４を参照すると、現在時は現行のスケジューラ・システム時間の値を維持するレジスタである。このレジスタはscheduler_tickあたり１回増分される。好ましい実施形態の現在時レジスタの範囲は、タイマ・ベース・スケジューラの範囲の４倍になるように選択されている。このため、フロー・キュー制御ブロックで見つかるタイム・スタンプ・フィールドの１つ（すなわち、NextGreenTime）と現在時とを比較したときに現在時ラップを決定することができる。
【００９４】
現行ポインタを使用して、ＷＦＱカレンダ内のサービス・ロケーションを示す。タイマ・ベース・カレンダとは対照的に、現行ポインタはスケジューラ・システム時間とは無関係である。
【００９５】
動作
図１５の流れ図に示すように、各scheduler_tickの間に、まず各ターゲット・ポート・キューの状態を検査する。ＷＦＱカレンダのそれぞれは１対のポートに関連づけられ、したがって、ＷＦＱポート０は高優先順位ポート０と低優先順位ポート０に関連づけられている。ライン２６２上でターゲット・ポート・キューのしきい値を超えている場合、scheduler_tickの間、そのＷＦＱカレンダによりそれ以上のアクションは一切行われない。（このシステムは、出力を制限するための一種の背圧を提供し、システムが処理できないフレームが送出されないようにする。）ターゲット・ポート・キューのしきい値を超えていない場合、現行ポインタが示すスロットが検査される。そのスロットが空であると分かった場合、現行ポインタは次の非空スロットに進んでフロー・キューＷＦＱ候補を見つけることができる。すべてのスロットが空であると分かった場合、現行ポインタは未変更であり、いかなる候補も検出されない。そのスロットがこの１つのカレンダ内で非空であると分かった場合、スロットに記憶されているフロー・キュー／アドレスはこのポート用のＷＦＱ候補である。同様に、４０個のＷＦＱカレンダのそれぞれは、それに関連するターゲット・ポート・キュー用の候補を見つけることができるだろう。
【００９６】
ターゲット・ポートしきい値の検査の目的は、ＷＦＱカレンダからターゲット・ポート・キューにパケットが割り当てられるレートを制御することである。ターゲット・ポート・キューは接続されたメディアが指定するレートで排出されることになるので、しきい値を超えるターゲット・ポートの状況を検査すると、そのメディアの帯域幅を超えるレートでパケットがターゲット・ポート・キューに割り当てられないことを保証するメカニズムが得られる。好ましい実施形態では、このしきい値はバイト単位の測定値として定義され、このしきい値は、少なくとも、適切な動作を保証するためにそのメディア用に定義された最大伝送ユニット（ＭＴＵ）に設定しなければならない。
【００９７】
本発明の目的は、最小帯域幅と組み合わせてベスト・エフォート帯域幅をスケジューリングする方法を提供することにあり、その場合、単一フロー・キューが時間ベース・カレンダとＷＦＱカレンダの両方にあるので、適切な機能のために上記のメカニズムが必要である。
【００９８】
すべてのカレンダ（時間ベース・カレンダとＷＦＱカレンダの両方）間で最終フロー・キュー選択が行われる。フロー・キューＷＦＱ候補が選択されると、フロー・キューポインタがＬＩＦＯスタックからデキューされる。このデキュー・アクション後に現行ポインタが示すスロットが非空である（すなわち、少なくとももう１つの項目がその中に存在する）と分かった場合、現行ポインタはそれ以上変更されない。このデキュー・アクション後に現行ポインタが示すスロットが空であると分かった場合、現行ポインタは次の非空スロットに進むことになる。すべてのスロットが空であると分かった場合、現行ポインタは未変更である。
【００９９】
当業者であれば分かるように、ＷＦＱカレンダは、それに割り当てられたすべてのフロー・キュー間で使用可能な帯域幅を共用する。さらに、フロー・キューに重みを割り当てることにより、各フロー・キューに割り振られた帯域幅の相対比率を変更することができる。これは、非空対応フロー・キューが置かれている位置の計算によって実施される。低重み係数は、所与のフレーム長の場合により頻度の高いサービスを可能にし、関連フローが同じ長さのフレームの場合に高重み係数より短い距離だけ次のサービス用の「はしご」を上っていくことを意味する。同様に、より長いフレームを提供するフローは、同じ重み係数を有するより短いフレームを提供するフローより大きい距離だけ、はしごを上ることになり、同じ優先順位または重み係数の場合、より短いフレームを有する方がより頻度の高いサービスを受け取ることを意味する。
【０１００】
ＷＦＱ距離計算
距離計算は、それがデキューされた位置からカレンダ内でフロー・キューが移動するスロットの数として定義する。好ましい実施形態では、ＷＦＱカレンダ用の距離計算は以下の形式を有する。
【０１０１】
スロット距離＝Ｍａｘ（Ｍｉｎ（（（フレーム長）＊ＱＤ＊Ｋ），max_distance），１）
式中、スロット距離は整数であり、フレーム長はバイト単位で測定され、ＱＤはフロー・キュー制御ブロックに指定されているキュー重みであり、max_distanceはカレンダ内のスロット数から１を引いたものとして定義され、Ｋはターゲット・ポートに割り当てられた倍率である。Ｋの指定は、ターゲット・ポートのＭＴＵと、ＷＦＱカレンダ内のスロット数と、所望のＱＤの範囲から決定される。好ましい実施形態の場合、以下に示す値のＫを推奨する。
ＭＴＵ（バイト数）        Ｋ
２０４８                  １／６４
９２１６                  １／２５６
１６３８４                １／１０２４
【０１０２】
本発明の精神を逸脱せずに他の値のＫを選択することができる。
【０１０３】
添付図面とともに好ましい実施形態の上記の説明を考慮すると、本発明の多くの変更態様は当業者にとって明らかなものになるだろう。たとえば、フレーム・サイズおよび記憶している重み係数に基づく重み付けは、他の式で置き換えることができる。１つのカレンダ内のスロット数とポートあたりのカレンダ数は、このシステムのアーキテクチャに対処できるように変更することができる。それぞれのステップのエポック数と距離、現在時レジスタのサイズ、scheduler_tickレートは本発明の精神を逸脱せずに変更できるだろう。そのうえ、本発明の精神を逸脱せずに、システムの実施例および優先順位の体系に対して多くの変更を行うことができ、優先順位を決定するために様々なアルゴリズムを使用することができる。さらに、本発明の特徴の一部は、その他の特徴を対応して使用せずに使用することができる。したがって、好ましい実施形態の上記の説明は、単に本発明の原理を例示するものであり、それを制限するものではないと見なすべきである。
【図面の簡単な説明】
【図１】  組込みプロセッサ複合体を含むインタフェース装置のブロック図であり、本発明を実施する際に有用なＤＮエンキュー・システムおよびスケジューラを示す図である。
【図２】  図１に示すタイプの組込みプロセッサ複合体のブロック図であり、本発明を理解する際に有用なＤＮエンキュー（およびそれに含まれるスケジューラ）を伴う図である。
【図３】  本発明の好ましい実施形態により、図２のスケジューラにおいて可変長パケットをスケジューリングするためのシステムを示す図である。
【図４】  本発明の好ましい実施形態により、図３のスケジューリング・システムで使用するタイマ・ベース・カレンダを示す図である。
【図５】  図３ないし４のスケジューラに関連して使用するスケジューリング操作の流れ図である。
【図６】  図４の各種エポックが色々な時間分解能を有する様子を示す図である。
【図７】  本発明で使用する最大バースト指定を示す図である。
【図８】  本スケジューラの様々な構成要素の流れ図であり、次の緑色時間の計算を対象とする図である。
【図９】  本スケジューラの様々な構成要素の流れ図であり、次の緑色時間の計算を対象とする図である。
【図１０】  本スケジューラの様々な構成要素の流れ図であり、バースト・サイズ・クレジットの計算および更新を対象とする図である。
【図１１】  本スケジューラの様々な構成要素の流れ図であり、バースト・サイズ・クレジットの計算および更新を対象とする図である。
【図１２】  本スケジューラの様々な構成要素の流れ図であり、切断および再接続による恩恵を回避するためのキュー制御ブロックの経時を示す図である。
【図１３】  本スケジューラの様々な構成要素の流れ図であり、切断および再接続による恩恵を回避するためのキュー制御ブロックの経時を示す図である。
【図１４】  本発明の好ましい一実施形態により、本発明のスケジューラで有用なＷＦＱカレンダを示す図である。
【図１５】  図３ないし４のスケジューラに関連して使用するスケジューリング操作の論理の流れ図である。
【図１】
0003784049.tif 000002
【図２】
0003784049.tif 000003
【図３】
0003784049.tif 000004
【図４】
0003784049.tif 000005
【図５】
0003784049.tif 000006
【図６】
0003784049.tif 000007
【図７】
0003784049.tif 000008
【図８】
0003784049.tif 000009
【図９】
0003784049.tif 000010
【図１０】
0003784049.tif 000011
【図１１】
0003784049.tif 000012
【図１２】
0003784049.tif 000013
【図１３】
0003784049.tif 000014
【図１４】
0003784049.tif 000015
【図１５】
0003784049.tif 000016