(57)【特許請求の範囲】
【請求項１】
共通リンク（Ｌ）を介して伝送される複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）間で、通信ネットワーク内の前記共通リンク（Ｌ）上の利用可能な帯域幅を共用する方法であって、前記方法が、プロセッサ（Ｐ）によって使用され、前記複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）間で前記利用可能な帯域幅に含まれる予約帯域幅を共用するステップと、前記複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）の各データフローに関連付けられるそれぞれの未予約データパケット割当に従って前記複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）間で、前記予約帯域幅を超えて前記利用可能な帯域幅に含まれる未予約帯域幅を共用するステップとを含み、前記未予約帯域幅を共用する前記ステップが、前記複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）の少なくとも１つのデータフロー（Ｃ２）に、運用業者の方針に従って決定されたそれぞれの調整可能な管理ウエイトを関連付けるステップと、前記それぞれの調整可能な管理ウエイトに応じて前記少なくとも１つのデータフロー（Ｃ２）に関連付けられる前記それぞれの未予約データパケット割当を決定するステップとを含むことを特徴とする方法。
【請求項２】
前記プロセッサ（Ｐ）に結合されたバッファ手段（ＢＵＦ）内に少なくとも１つのデータパケットを有する、前記複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）のアクティブなデータフロー（Ｃ２）として前記少なくとも１つのデータフロー（Ｃ２）を決定するステップを含むことを特徴とする請求項１に記載の利用可能な帯域幅を共用する方法。
【請求項３】
前記プロセッサ（Ｐ）が、受信したデータパケットを記憶するバッファ手段（ＢＵＦ）を制御し、予約帯域幅を共用する前記ステップが、各データフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、）ごとに事前定義されかつ前記利用可能な帯域幅に含まれる予約帯域幅の量（ＭＣＲ１、ＭＣＲ２、．．．、ＭＣＲ８、ＭＣＲ９、．．．、ＭＣＲ１６）まで、保証帯域幅を共用する第１の処理から構成され、未予約帯域幅を共用する前記ステップが、それぞれの非保証帯域幅割当に従って、前記複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）間で非保証帯域幅を共用する第２の処理から構成され、前記非保証帯域幅が、前記予約帯域幅を超えて前記利用可能な帯域幅に含まれる未予約帯域幅と前記予約帯域幅の実際には未使用の部分とを含み、前記非保証帯域幅を共用する前記第２の処理が、前記それぞれの調整可能な管理ウエイトを前記複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）の少なくとも１つのデータフロー（Ｃ２）に関連付ける処理を含み、前記それぞれの非保証帯域幅割当が、前記少なくとも１つのデータフロー（Ｃ２）に関連付けられた前記それぞれの調整可能な管理ウエイトに応じて決定されることを特徴とする請求項１に記載の利用可能な帯域幅を共用する方法。
【請求項４】
各サービス時間で、前記複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）の少なくとも１つのアクティブなデータフローが、前記予約帯域幅のそれぞれの利用権限の与えられた予約帯域幅割当に達したか否かを決定するステップと、少なくとも１つのアクティブなデータフロー（Ｃ２）がそれぞれの利用権限の与えられた予約帯域幅割当に達しない時に、利用権限の与えられた予約帯域幅割当に達しない前記複数のアクティブなデータフローの１つ（Ｃ２）を選択し、それによって前記サービス時間で保証帯域幅を認可するステップと、前記複数のアクティブなデータフローの各データフローがそれぞれの利用権限の与えられた予約帯域幅割当に達した時に、複数のアクティブなデータフローの１つ（Ｃ１）を選択し、それによって前記サービス時間で非保証帯域幅を認可するステップとをさらに含むことを特徴とする請求項３に記載の利用可能な帯域幅を共用する方法。
【請求項５】
前記複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）の各データフローにそれぞれのサービス認可カウンタ（ＣＴ１、ＣＴ２、．．．、ＣＴ８、ＣＴ９、．．．、ＣＴ１６）を関連付けるステップと、
事前定義された期間が開始するたびに、前記事前定義された期間の予約帯域幅の対応する利用権限の与えられたサービス認可数に等しい、前記予約帯域幅（ＭＣＲ２）から導出されたそれぞれの事前定義された初期クレジット値（ＥＧＳＧ２）に前記サービス認可カウンタ（ＣＴ２）を初期化するステップと、
前記それぞれのサービス認可カウンタ（ＣＴ２）がそれぞれの事前定義された最終値に達するまで、前記サービス時間に処理されるデータフロー（Ｃ２）に関連付けられているそれぞれのサービス認可カウンタ（ＣＴ２）を、各サービス時間毎に更新するステップと、
前記関連付けられたサービス認可カウンタが前記それぞれの事前定義された最終値に達した時に、データフローがそれぞれの利用権限の与えられた予約帯域幅割当に達したことを検出するステップとをさらに含むことを特徴とする請求項３に記載の利用可能な帯域幅を共用する方法。
【請求項６】
可変長の完全なパケットを連続的に処理する場合、前記それぞれのサービス認可カウンタ（ＣＴ２）を更新する前記ステップが、処理されたパケットの長さに比例したサービス認可数をカウントすることによって実行されることを特徴とする請求項５に記載の利用可能な帯域幅を共用する方法。
【請求項７】
前記事前定義された期間が、すべてのデータフローについて同じ継続期間を有することを特徴とする請求項５に記載の利用可能な帯域幅を共用する方法。
【請求項８】
前記同じ継続期間の事前定義された期間が、すべてのデータフローについて同期化され、その結果、事前定義された期間が開始するたびに、各データフロー（Ｃ２）の前記サービス認可カウンタ（ＣＴ２）を初期化するステップが、すべてのデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）のすべてのサービス認可カウンタ（ＣＴ１、ＣＴ２、．．．、ＣＴ８、ＣＴ９、．．．、ＣＴ１６）について同時に実行されることを特徴とする請求項７に記載の利用可能な帯域幅を共用する方法。
【請求項９】
前記同じ継続期間の事前定義された期間が、すべてのデータフローについて同期化されず、その結果、前記事前定義された期間が開始するたびに、各データフロー（Ｃ２）の前記サービス認可カウンタ（ＣＴ２）を初期化する前記ステップが、すべてのデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）のすべてのサービス認可カウンタ（ＣＴ１、ＣＴ２、．．．、ＣＴ８、ＣＴ９、．．．、ＣＴ１６）について同時に実行されないことを特徴とする請求項７に記載の利用可能な帯域幅を共用する方法。
【請求項１０】
前記事前定義された期間が、データフローごとに異なる場合がある特定の継続期間を有することを特徴とする請求項５に記載の利用可能な帯域幅を共用する方法。
【請求項１１】
少なくともそれぞれのアクティブなデータフローが前記予約帯域幅のそれぞれの利用権限の与えられた予約帯域幅割当に達したか否かを決定する前記ステップが、共通保証帯域幅割当データフローカウンタ（ＧＢＳＤＦＣ）を含み、前記共通保証帯域幅割当データフローカウンタが、
事前定義された期間中に前記予約帯域幅の前記それぞれの利用権限の与えられた予約帯域幅割当に達していない現在のアクティブなデータフローの数を記録するために使用され、
アクティブなデータフローが前記それぞれの利用権限の与えられた予約帯域幅割当に達するたびに、または前記それぞれの利用権限の与えられた予約帯域幅割当に達していなくてもアクティブなデータフローが非アクティブになるたびに、減分され、
データフローが以前アクティブでなくまだ前記それぞれの利用権限の与えられた予約帯域幅割当に達していない間にアクティブになるたびに、またはアクティブなデータフローが以前それぞれの利用権限の与えられた予約帯域幅割当に達したと考えられていたがまだ前記それぞれの利用権限の与えられた予約帯域幅割当に達していないことが新たに検出されるたびに、増分され、
それによって、前記各サービス時間で、前記共通カウンタが空でない時に利用権限の与えられた予約帯域幅割当に達していないアクティブなデータフローに保証帯域幅を認可するか、または前記共通カウンタが空の時にアクティブなデータフローに非保証帯域幅を認可するかを示すことを特徴とする請求項４または５に記載の利用可能な帯域幅を共用する方法。
【請求項１２】
各サービス時間で、処理すべき１つのデータフローを適切に選択するために、前記選択ステップが、
それぞれの利用権限の与えられた予約帯域幅割当に達していない少なくとも各アクティブなデータフローについて保証帯域幅スケジュールパラメータ（Ｒ）を決定し、それによって各データフローに前記保証帯域幅スケジュールパラメータを提供し、各保証帯域幅スケジュールパラメータ（Ｒ）が前記予約帯域幅（ＭＣＲ）に応じて決定されるステップと、
それぞれの利用権限の与えられた予約帯域幅割当に達した少なくとも各アクティブなデータフローについて非保証スケジュールパラメータ（Ｕ）を決定し、それによって各データフローに前記非保証スケジュールパラメータを提供し、各非保証スケジュールパラメータが前記それぞれの調整可能な管理ウエイト（Ｗ）に応じて決定されるステップと、
それぞれの利用権限の与えられた予約帯域幅割当に達していないアクティブなデータフローに保証帯域幅を認可する時に前記保証帯域幅スケジュールパラメータ（Ｒ）に基づいてスケジューリングを実行するステップと、
それぞれの利用権限の与えられた予約帯域幅割当に達したアクティブなデータフローに非保証帯域幅を認可する時に前記非保証スケジュールパラメータ（Ｕ）に基づいてスケジューリングを実行するステップと、
前記プロセッサ（Ｐ）が保証帯域幅認可信号または非保証帯域幅認可信号を受信すると、事前定義された規則と条件に従って、それぞれ、前記保証帯域幅スケジュールパラメータ（Ｒ２）の最小値を有するデータフローであることまたは非保証スケジュールパラメータ（Ｕ２）の最小値を有するデータフローであることが検出されたデータフロー（Ｃ２）を選択するステップをさらに含むことを特徴とする請求項４に記載の利用可能な帯域幅を共用する方法。
【請求項１３】
前記保証帯域幅スケジュールパラメータ（Ｒ）がそれぞれの利用権限の与えられた予約帯域幅割当に達していないデータフローにだけ使用され、前記非保証スケジュールパラメータ（Ｕ）がそれぞれの利用権限の与えられた予約帯域幅割当に達したデータフローにだけ使用され、各データフローが任意の時点で前記保証帯域幅スケジュールパラメータ（Ｒ）または非保証スケジュールパラメータ（Ｕ）のいずれかであるただ１つのスケジュールパラメータを専ら使用することによってスケジューリングされることを特徴とする請求項１２に記載の利用可能な帯域幅を共用する方法。
【請求項１４】
各サービス時間で、処理すべき１つのデータフローを適切に選択するために、前記選択ステップが、
それぞれの利用権限の与えられた予約帯域幅割当に達していないアクティブなデータフローの保証帯域幅データフロー巡回リストを維持するステップと、
それぞれの利用権限の与えられた予約帯域幅割当に達した少なくとも各アクティブなデータフローについて非保証スケジュールパラメータ（Ｕ）を決定し、それによって各データフローに前記非保証スケジュールパラメータを提供し、各非保証スケジュールパラメータ（Ｕ）が前記それぞれの調整可能な管理ウエイト（Ｗ）に応じて決定されるステップと、
それぞれの利用権限の与えられた予約帯域幅割当に達していないアクティブなデータフローに保証帯域幅を認可する時に前記保証帯域幅データフロー巡回リストに基づいてスケジューリングを実行するステップと、
それぞれの利用権限の与えられた予約帯域幅割当に達したアクティブなデータフローに非保証帯域幅を認可する時に前記非保証スケジュールパラメータ（Ｕ）に基づいてスケジューリングを実行するステップと、
前記プロセッサ（Ｐ）が保証帯域幅認可信号または非保証帯域幅認可信号を受信すると、事前定義された規則と条件に従って、それぞれ、前記保証帯域幅データフロー巡回リストの先頭のデータフローであることまたは前記非保証スケジュールパラメータ（Ｕ２）の最小値を有するデータフローであることが検出されたデータフロー（Ｃ２）を選択するステップをさらに含むことを特徴とする請求項４に記載の利用可能な帯域幅を共用する方法。
【請求項１５】
各サービス時間で、処理すべき１つのデータフローを適切に選択するために、前記選択ステップが、
それぞれの利用権限の与えられた予約帯域幅割当に達していない少なくとも各アクティブなデータフローについて保証帯域幅スケジュールパラメータ（Ｒ）を決定し、それによって各データフローに前記保証帯域幅スケジュールパラメータを提供し、各保証帯域幅スケジュールパラメータ（Ｒ）が前記予約帯域幅（ＭＣＲ）に応じて決定されるステップと、
前記複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）の各データフローにそれぞれの特別サービス認可カウンタ（ＥＣＴ１、ＥＣＴ２、．．．、ＥＣＴ８、ＥＣＴ９、．．．、ＥＣＴ１６）を関連付けるステップと、
それぞれの予約帯域幅割当に達した各データフローの前記特別サービス認可カウンタを、前記それぞれの調整可能な管理ウエイト（Ｗ）に比例するそれぞれの事前定義された初期特別サービス認可クレジット値（ＮＧＳＧ）に初期化し、この初期化動作が、すべての前記特別サービス認可カウンタがそれぞれの事前定義された最終値に達するたびに実行されるステップと、
各サービス時間で、前記サービス時間で処理されるデータフロー（Ｃ２）に関連付けられているそれぞれの特別サービス認可カウンタ（ＥＣＴ２）を、前記それぞれの特別サービス認可カウンタ（ＥＣＴ２）がそれぞれの事前定義された最終値に達するまで更新し、特別サービス認可カウンタの可能な更新数の合計が前記関連付けられたデータフローの前記それぞれの調整可能な管理ウエイト（Ｗ）に比例するステップと、
それぞれの利用権限の与えられた予約帯域幅割当に達したアクティブなデータフローの非保証帯域幅データフロー巡回リストを維持するステップと、
それぞれの利用権限の与えられた予約帯域幅割当に達していないアクティブなデータフローに保証帯域幅を認可する時に前記保証帯域幅スケジュールパラメータ（Ｒ）に基づいてスケジューリングを実行するステップと、
それぞれの利用権限の与えられた予約帯域幅割当に達したアクティブなデータフローに非保証帯域幅を認可する時に前記非保証帯域幅データフロー巡回リストに基づいてスケジューリングを実行するステップと、
前記プロセッサ（Ｐ）が保証帯域幅認可信号または非保証帯域幅認可信号を受信すると、事前定義された規則と条件に従って、それぞれ、前記保証帯域幅スケジュールパラメータ（Ｒ２）の最小値を有するデータフローであることまたは前記非保証帯域幅データフロー巡回リストの先頭のデータフローであることが検出されたデータフロー（Ｃ２）を選択するステップをさらに含むことを特徴とする請求項４に記載の利用可能な帯域幅を共用する方法。
【請求項１６】
各サービス時間で、処理すべき１つのデータフローを適切に選択するために、前記選択ステップが、
それぞれの利用権限の与えられた予約帯域幅割当に達していないアクティブなデータフローの保証帯域幅データフロー巡回リストを維持するステップと、
前記複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）の各データフローにそれぞれの特別サービス認可カウンタ（ＥＣＴ１、ＥＣＴ２、．．．、ＥＣＴ８、ＥＣＴ９、．．．、ＥＣＴ１６）を関連付けるステップと、
それぞれの予約帯域幅割当に達した各データフローの前記特別サービス認可カウンタを、前記それぞれの調整可能な管理ウエイト（Ｗ）に比例するそれぞれの事前定義された初期特別サービス認可クレジット値（ＮＧＳＧ）に初期化し、この初期化動作が、すべての前記特別サービス認可カウンタがそれぞれの事前定義された最終値に達するたびに実行されるステップと、
各サービス時間で、前記サービス時間で処理されるデータフロー（Ｃ２）に関連付けられたそれぞれの特別サービス認可カウンタ（ＥＣＴ２）を、前記特別サービス認可カウンタ（ＥＣＴ２）がそれぞれの事前定義された最終値に達するまで更新し、特別サービス認可カウンタの可能な更新数の合計が前記関連付けられたデータフローの前記それぞれの調整可能な管理ウエイト（Ｗ）に比例するステップと、
それぞれの利用権限の与えられた予約帯域幅割当に達したアクティブなデータフローの非保証帯域幅データフロー巡回リストを維持するステップと、
それぞれの利用権限の与えられた予約帯域幅割当に達していないアクティブなデータフローに保証帯域幅を認可する時に前記保証帯域幅データフロー巡回リストに基づいてスケジューリングを実行するステップと、
それぞれの利用権限の与えられた予約帯域幅割当に達したアクティブなデータフローに非保証帯域幅を認可する時に前記非保証帯域幅データフロー巡回リストに基づいてスケジューリングを実行するステップと、
前記プロセッサ（Ｐ）が保証帯域幅認可信号または非保証帯域幅認可信号を受信すると、事前定義された規則と条件に従って、それぞれ、前記保証帯域幅データフロー巡回リストの先頭のデータフローであることまたは前記非保証帯域幅データフロー巡回リストの先頭のデータフローであることが検出されたデータフロー（Ｃ２）を選択するステップをさらに含むことを特徴とする請求項４に記載の利用可能な帯域幅を共用する方法。
【請求項１７】
可変長の完全なパケットを連続的に処理する場合、前記それぞれの特別サービス認可カウンタ（ＥＣＴ２）を更新する前記ステップが、処理されたパケットの長さに応じてサービス認可数をカウントすることによって実行されることを特徴とする請求項１５または１６に記載の利用可能な帯域幅を共用する方法。
【請求項１８】
前記それぞれのサービス認可カウンタ（ＣＴ）がそれぞれの利用権限の与えられた予約帯域幅割当に達していないデータフローにだけ使用され、前記それぞれの特別サービス認可カウンタ（ＥＣＴ）がそれぞれの利用権限の与えられた予約帯域幅割当に達したデータフローにだけ使用され、それぞれの利用権限の与えられた予約帯域幅割当に達していないデータフローのための前記それぞれのサービス認可カウンタ（ＣＴ）の働きをするか、またはそれぞれの利用権限の与えられた予約帯域幅割当に達したデータフローのための前記それぞれの特別サービス認可カウンタ（ＥＣＴ）の働きをする各データフロー（Ｃ）に関連付けられたただ１つのカウンタ手段が使用されることを特徴とする請求項１５または１６に記載の利用可能な帯域幅を共用する方法。
【請求項１９】
共通リンク（Ｌ）を介して伝送される複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）間で、通信ネットワーク内の前記共通リンク（Ｌ）上の利用可能な帯域幅を共用するプロセッサ（Ｐ）であって、前記プロセッサ（Ｐ）が、前記複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）の各データフローに関連付けられているそれぞれの予約データパケット割当に従って、前記複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）間で前記利用可能な帯域幅に含まれる予約帯域幅を共用する第１の処理手段（Ｐ１）と、前記複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）の各データフローに関連付けられているそれぞれの未予約データパケット割当に従って、前記複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）間で、前記予約帯域幅を超えて前記利用可能な帯域幅に含まれる未予約帯域幅を共用する第２の処理手段（Ｐ２）とを含み、前記プロセッサ（Ｐ）が、前記複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）の少なくとも１つのデータフロー（Ｃ２）に、運用業者の方針に従って決定された調整可能な管理ウエイトを関連付ける関連付け手段（ＭＥＭ）を含み、前記第２の処理手段（Ｐ２）が、前記それぞれの調整可能な管理ウエイトに応じて前記少なくとも１つのデータフロー（Ｃ２）に関連付けられた前記それぞれの未予約データパケット割当を決定する第２の決定手段（ＤＥＴ２）を含み、前記プロセッサ（Ｐ）が、前記第１の処理手段（Ｐ１）と前記第２の処理手段（Ｐ２）とを制御し、前記それぞれの予約データパケット割当と前記それぞれの未予約データパケット割当の尺度である共用帯域幅信号を提供する制御手段（ＣＴＲＬ）をさらに含むことを特徴とするプロセッサ（Ｐ）。
【請求項２０】
前記プロセッサ（Ｐ）に結合されたバッファ手段（ＢＵＦ）内に少なくとも１つのデータパケットを有する、前記複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）のアクティブなデータフロー（Ｃ２）として前記少なくとも１つのデータフロー（Ｃ２）を決定する第３の決定手段（ＤＥＴ３）をさらに含むことを特徴とする請求項１９に記載の利用可能な帯域幅を共用するプロセッサ（Ｐ）。
【請求項２１】
前記第１の処理手段（Ｐ１）が、前記各データフローに関連付けられている最低データパケット速度に応じて前記それぞれの予約データパケット割当を決定し、前記各データフローごとに最低保証帯域幅を保証する第１の決定手段（ＤＥＴ１）を含み、前記最低保証帯域幅が前記第１の処理手段（Ｐ１）によって守られる場合に前記第２の処理手段（Ｐ２）を作動させるために前記制御手段（ＣＴＲＬ）がさらに含まれることを特徴とする請求項１９に記載の利用可能な帯域幅を共用するプロセッサ（Ｐ）。
【請求項２２】
前記プロセッサ（Ｐ）が非同期転送モード通信システムで保証フレーム速度サービスをサポートすることを特徴とする請求項１９に記載の利用可能な帯域幅を共用するプロセッサ（Ｐ）。
【請求項２３】
可変長パケット通信システムをサポートすることを特徴とする請求項１９に記載の利用可能な帯域幅を共用するプロセッサ（Ｐ）。
【請求項２４】
共通リンク（Ｌ）を介して伝送される複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）間で、通信ネットワーク内の前記共通リンク（Ｌ）上の利用可能な帯域幅を共用するスケジューラであって、前記スケジューラが、関連付けられたデータフローに従って前記スケジューラの少なくとも１つの入力に供給される前記複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）の着信データパケットを、バッファ手段（ＢＵＦ）に含まれ前記複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）の１つのデータフローにそれぞれ関連付けられた複数のバッファ待ち行列（Ｑ１、Ｑ２、．．．、Ｑ８、Ｑ９、．．．、Ｑ１６）にソートし、それによって複数のソートされたデータパケットを提供するためのバッファ手段（ＢＵＦ）と、１つのソートされたデータパケットを前記共通リンク（Ｌ）上で伝送するために前記複数のソートされたデータパケットの１つを選択するための選択手段（ＳＥＬ）を含み、前記スケジューラが請求項１９、２０、２１のいずれか一項に記載のプロセッサ（Ｐ）をさらに含み、前記共用帯域幅信号に従って前記選択を制御するために前記プロセッサ（Ｐ）が前記選択手段（ＳＥＬ）に結合されることを特徴とするスケジューラ。
【請求項２５】
共通リンク（Ｌ）を介して伝送される複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）間で、通信ネットワーク内の前記共通リンク（Ｌ）上の利用可能な帯域幅を共用するインテリジェントバッファであって、前記インテリジェントバッファが、前記インテリジェントバッファの少なくとも１つの入力に供給される前記複数のデータフロー（Ｃ１、Ｃ２、．．．、Ｃ８、Ｃ９、．．．、Ｃ１６）の１つのデータフローの着信データパケットを受け入れるか廃棄するかを決定し、それによって前記着信データパケットが受け入れられた場合に受け入れられたデータパケットを提供するための決定手段を含み、前記受け入れられたデータパケットを記憶し、前記受け入れられたデータパケットを前記共通リンク（Ｌ）上で伝送するためにバッファ手段が前記決定手段に結合され、前記インテリジェントバッファが請求項１９、２０、２１のいずれか一項に記載のプロセッサ（Ｐ）をさらに含み、前記共用帯域幅信号に従って前記決定を制御するために前記プロセッサ（Ｐ）が前記決定手段に結合されることを特徴とするインテリジェントバッファ。
【請求項２６】
請求項１９に記載の少なくとも１つのプロセッサ（Ｐ）を含むことを特徴とする通信システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、請求項１のプリアンブルに記載の利用可能な帯域幅を共用する方法、請求項１９のプリアンブルに記載のそのような方法を実現するプロセッサ、ならびにそれぞれ請求項２４、２５、および２６のプリアンブルに記載のスケジューラ、インテリジェントバッファ、および通信システムに関する。
【０００２】
【従来の技術】
利用可能な帯域幅を共用するそのような方法は、例えば１９９８年７月２０〜２２日のＩＦＩＰ  ＡＴＭ９８  ｗｏｒｋｓｈｏｐで発表されたＯ．Ｂｏｎａｖｅｎｔｕｒｅの論文「A flexible buffer acceptance algorithm to support a guaranteed frame rate service category in asynchronous transfer mode ATM switches」、７１／１〜７１／１０頁からすでに当技術分野で知られている。この論文には、非同期転送モード交換機内で保証フレーム速度ＧＦＲサービスカテゴリをサポートする柔軟なバッファ受け入れアルゴリズムが記載されている。ＧＦＲサービスは異なる種類のネットワークアプリケーション用に指定された複数のサービスカテゴリの１つである。サービスの種類ごとに、ネットワークに提示されるトラフィックおよびネットワークに要求されるサービス品質（ＱＯＳ）を記述するために１組のパラメータが与えられる。所望のＱＯＳ目的を満たすために、異なる種類のトラフィック制御機構が定義されている。
【０００３】
通信ネットワーク内の共通リンク上で、共通リンクを介して伝送される複数のデータフローの間で利用可能な帯域幅を共用する方法が、特に保証フレーム速度ＧＦＲサービスについて、この論文に記載されている。この論文には、保証フレーム速度ＧＦＲサービスカテゴリの目的がエンドシステムで使用しやすい最低保証帯域幅をサービスに与えることであると記載されている。エンドシステムが保証フレーム速度ＧＦＲサービスカテゴリの恩恵を受けるために厳密には変更は不要であるが、このサービスカテゴリをサポートするために交換機やルータなどの特定の機能ブロックを拡張する必要がある。
【０００４】
実際、上記の論文の第２節には、ＧＦＲサービスカテゴリを導入する主な動機は、無指定伝送速度サービスカテゴリＵＢＲの簡単さを保持しながら、そのような共通リンクを利用する（この出願ではデータフローと呼ばれる）各仮想コネクションに最低保証帯域を関連付けることを可能にすることによってより良いサービスを提供することであったと記載されている。そのようなＧＦＲサービスのトラフィック契約は各データフローの最低セル速度ＭＣＲの定義を含む。そのような最低セル速度ＭＣＲは、例えばセル／秒で表される最低保証帯域幅に対応する。最低保証帯域幅は、契約に従って確立された各データフローごとに任意の時点で保証され、かつデータフローの接続設定時に決定される最低帯域幅である。これは、保証帯域幅が確立された各データフローごとに共通リンク上で利用可能であり、この確立されたデータフローについてこの保証帯域幅が使用されるかまたは使用されないということを意味する。
【０００５】
したがって、共通リンク上で利用可能な帯域幅を共用する方法は、利用可能な帯域幅に含まれる予約帯域幅を複数のデータフロー間で共用するステップを含む。ＧＦＲサービスについての論文に記載されているように、利用可能な帯域幅を共用する可能な方法はその最低セル速度ＭＣＲの機能による。
【０００６】
またその論文に述べられているように、複数のデータフロー間でそれらのＭＣＲに比例して共用される利用可能な帯域幅は必ずしも一定の帯域幅である必要はないことに留意する必要がある。実際、ＧＦＲサービスカテゴリに加えて、例えばＡＴＭ交換機が他のサービスカテゴリをサポートできることもある。そのようなマルチサービス交換機では、ＧＦＲサービスのデータパケットストリームが利用することができる帯域幅はもはや一定ではなく、リアルタイムトラフィックなどのより優先度の高いトラフィックの量によって異なる。これは、共通リンク上の全帯域幅が、パケットの適時送達が重要であるリアルタイムサービスのような他の種類のサービスに、より大きく分散されることがあるということを意味する。コネクション受付制御（ＣＡＣ）アルゴリズムにより、すべてのＧＦＲデータフローの異なる最低セル速度の合計を超えるＧＦＲデータフローが事前定義された平均帯域幅を常に利用することが保証されているということを理解する必要がある。
【０００７】
また、この論文には、ＧＦＲサービスによって、そのようなデータフローに含まれるデータパケットを、そのデータフローに関連付けられた最低セル速度ＭＣＲより高速で伝送するという利点がエンドシステムに提供されることが記載されている。ただし、この論文の第７．１節、すなわち、２重ＥＰＤ機構に記載された利用可能な帯域幅を共用する方法は、未予約帯域幅と呼ばれる余剰帯域幅の割り振りが全く制御できないという欠点を有する。他方、この論文の第７．３節はこの未予約帯域幅を制御する次の２つのアルゴリズムについて述べている。一方の実施態様は未予約帯域幅の公平な割り振りを提供し、他方の実施態様はデータフローのＭＣＲに比例して未予約帯域幅を分配する。このようにして、共通リンク上で利用可能な帯域幅を共用する方法は、各データフローに関連付けられたそれぞれの未予約データパケット割当に応じて予約帯域幅を超えて未予約帯域幅を共用するステップを含む。
【０００８】
【発明が解決しようとする課題】
これらの従来技術のアルゴリズムの欠点は、それらのアルゴリズムが、それでもやはり全データフローに対する公平な割当または最低セル速度ＭＣＲに応じた割当などの特定の戦略に従って未予約帯域幅を共用するということである。これは、未予約データパケット割当が知られているアルゴリズムによって事前定義されるということを意味する。ネットワーク運用業者が余剰帯域幅を共用する独自の方針を定義できる融通性は存在しない。
【０００９】
本発明の一目的は、ネットワーク運用業者に、上記の知られているタイプであるが、未予約帯域幅を共用する独自の方針を定義する融通性を提供する利用可能な帯域幅を共用する方法を提供することである。
【００１０】
【課題を解決するための手段】
本発明によれば、この目的は請求項１に記載の利用可能な帯域幅を共用する方法、請求項１９に記載のその方法を実現するプロセッサ、ならびにそれぞれ請求項２４、２５、および２６に記載のスケジューラ、インテリジェントバッファ、およびそのようなプロセッサを含む通信システムに関する。
【００１１】
実際、未予約帯域幅を共用するステップが、データフローの１つに関連付けているそれぞれの調整可能な管理ウエイトと、それぞれの管理ウエイトに応じてこのデータフローのそれぞれの未予約データパケット割当を決定するステップとを含むということによって、ネットワーク運用業者は、予約帯域幅を共用することに加えて、データフローごとに管理ウエイトを提供する能力を有する。これらの管理ウエイトは未予約帯域幅を共用する運用業者の方針を反映している。
【００１２】
本発明の提案された方法の融通性によって、ネットワーク運用業者は従来技術の解決策の方針をサポートする、すなわち、公平な割り振りまたはデータフローの最低セル速度に従った未予約帯域幅の分配を提供するだけでなく、独自の方針を定義でき、例えば、運用業者はそれ自体のローカルネットワークトラフィックを他のネットワークからの中継トラフィックに優先させることができる。
【００１３】
未予約帯域幅割当を解釈するために異なる種類の実施態様が可能であることを説明する必要がある。実際、調整可能な管理ウエイトは未予約帯域幅の「ウエイト」、すなわち未予約帯域幅のパーセンテージ、例えば３０％に等しい調整可能な管理ウエイトによって実施できる。ただし、別の実施態様は「速度」、例えば相互に釣り合ったデータパケット速度によって解釈できる。これについては次のパラグラフでより明らかにする。
【００１４】
【発明の実施の形態】
ネットワーク運用業者は、未予約帯域幅の異なる一部分を異なるデータフローに与えるために、調整可能な管理ウエイトを使用できる。
【００１５】
第１の例は、ネットワーク運用業者が、すべてのデータフローに未予約帯域幅の同じ一部分を与える場合に与えられ、運用業者はすべてのデータフローについて同じ管理ウエイト、例えば１を入力する。
【００１６】
第２の例は、ネットワーク運用業者が最低保証帯域幅に比例して未予約帯域幅を分配する場合に与えられ、異なるデータフローの調整可能な管理ウエイトが、例えば最低データパケット速度に設定される必要がある。
【００１７】
第３の例は、ネットワーク運用業者が２つのタイプのデータフロー、例えば、ゴールドデータフローとノーマルデータフローとをサポートする場合に与えられる。ゴールドデータフローはノーマルデータフローの１０倍の未予約帯域幅の一部分を受け取るものとする。これは次の２つの異なる方法で実施できる。
【００１８】
ゴールドデータフローの各調整可能な管理ウエイトはノーマルデータフローの各管理ウエイトの値の１０倍の値である。このようにして、各ゴールドデータフローはノーマルデータフローの未予約帯域幅割当の１０倍の未予約帯域幅割当を受け取る。この実施態様はゴールドクラスのデータフローに含まれるデータフロー数に依存せず、通常クラスのデータフロー含まれるデータフロー数にも依存しない。また、
ゴールドデータフローの未予約帯域幅の合計のグローバル割当は、ノーマルデータフローの未予約帯域幅の合計の１０倍であり、それによってこのグローバルゴールド割当はゴールドデータフローの数に均等に分割され、グローバルノーマル割当はノーマルデータフローの数に均等に分割される。それに応じて調整可能な管理ウエイトが実施される。この実施態様はゴールドクラスデータフローに含まれるデータフロー数と、ノーマルクラスデータフローに含まれるデータフロー数とに依存する。
【００１９】
本発明の方法の利点が調整可能な管理ウエイトの次の可能な実施態様によって明らかになることに留意する必要がある。実際、調整可能な管理ウエイトが、例えば時間などの他のパラメータに依存して行われる時、ネットワーク運用業者は、後に運用業者の実際の介入なしに管理ウエイトがそのようなパラメータに応じて変化する、すなわち適応される、独自の方針を事前に実施する。これは次の例でより明らかになる。運用業者が１日の最繁時にすべてのデータフローに未予約帯域幅の同じ一部分を与え、１日の残りの時間帯に運用業者がゴールドデータフローとノーマルデータフローに関して前述した２つのクラスのデータフローをサポートする場合に、データフローは時間カウンタに応じた調整可能な管理ウエイトを受け取る。このようにして、運用業者は、例えば１日の事前定義された期間に、運用業者の実際の介入なしに調整可能な管理ウエイトが適応される独自の方針を実施し、それによって異なるデータフローの管理ウエイトがすべて同じ値を受け取る。後に第２の事前定義された時間に、管理ウエイトは再び適応され、それによって異なるデータフローの管理ウエイトがゴールドデータフローに従った値を受け取るかまたはノーマルデータフローに従った値を受け取るかする。さらに、調整可能な管理ウエイトは複数の変数に依存することもできる。実際、上記の例によれば、時間カウンタに加えて、各クラスのデータフローに関して変数を、例えば、ゴールドクラスデータフローの場合はＷＧを、ノーマルクラスデータフローの場合はＷＮを入力でき、それによってデータパケット速度の相対的な値がＷＧまたはＷＮに与えられる。例えば、ゴールドクラスデータフローがノーマルクラスデータフローの３倍の帯域幅を受け取る場合、ＷＧ変数は１に設定され、ＷＮ変数は１／３に設定される。ただし、運用業者が各クラスのデータフローの帯域幅割当を変更する場合には、変数ＷＧおよびＷＮの値だけが適応される、例えば、ＷＧを１に設定してＷＮを１／４に設定する必要がある。
【００２０】
利用可能な帯域幅をより有効に利用する方法は、アクティブなデータフロー、すなわち、少なくとも１つのデータパケットが本発明のプロセッサに結合されたバッファ手段に含まれているデータフローに未予約帯域幅を分配することである。実際、本発明の方法に従って未予約帯域幅を共用する可能な方法は、すべての確立されたデータフローに未予約帯域幅の一定の割当を分配することである。ただし、伝送されているデータフロー、例えばバースト伝送されていて現在バッファ内にデータパケットがないデータパケット割当を、他のデータフローが使用することによってこの方法が改善できる。本発明のこの特徴的な機能を請求項２および請求項２０に記載する。
【００２１】
本発明の方法は、最低帯域幅保証を受けるデータフローと最低帯域幅保証を受けないデータフローの共存を効率的にサポートし、このことが異なる種類のサービスカテゴリをサポートするための利点であることに留意する必要がある。最低帯域幅保証のサポートを請求項２１に記載する。同項には、本発明のプロセッサが、各データフローに関連付けられ且つ各データフローごとに最低保証帯域幅を保証する最低データパケット速度に応じて、それぞれの予約帯域幅を決定する第１の決定手段をさらに含むこと、および第１の処理手段によって最低保証帯域幅が守られる場合に第２の処理手段を作動させる制御手段がさらにプロセッサ内に含まれることが記載されている。このようにして、すべてのデータフローが、または上記の実施態様によればすべてのアクティブなデータフローが、予約帯域幅を共用するステップで最低保証帯域幅をすでに受け取っている場合に限って、未予約帯域幅が共用される。
【００２２】
最低帯域幅の保証をサポートする異なる種類のサービスカテゴリが知られているが、本発明の重要な適用例は、本発明のプロセッサが非同期転送モード通信システム内の保証フレーム速度サービスカテゴリをサポートするということである。これを請求項２２に記載する。本発明の方法が保証フレーム速度サービスカテゴリをサポートするために使用される場合、この方法は未予約帯域幅の共用の処理を最低帯域幅の保証を提供する処理から分離するということに留意する必要がある。
【００２３】
本発明による方法の利点は、従来技術の実施態様に従って、最低保証帯域幅を有するデータフローと共にベストエフォート型データフローをサポートするために、最低帯域幅が一般に暗黙的に定義され、データフローごとに予約されるということである。ただし、これは利用可能な帯域幅が本発明の方法に従って共用される場合には不要である。実際、ゼロに等しい事前定義された最低データパケット割当を有するデータフローは、ゼロ以外の調整可能な管理ウエイトを有することができ、例えばデータフローがアクティブになった時に調整可能な管理ウエイトに応じた未予約データパケット割当に従って未予約帯域幅割当を獲得する。
【００２４】
さらに、本発明のプロセッサは上記のようにＡＴＭセルなどの固定長データパケットで実施できるが、本発明に従ってインターネットパケットなどの可変長パケットをサポートするようにプロセッサの実施態様を拡張することも可能であるということに留意する必要がある。これを請求項６、請求項１７および請求項２３に記載する。このようにして、本発明のプロセッサは、例えばインターネットプロトコル通信システム内の負荷制御サービスをサポートする。
【００２５】
本発明による別の実施態様を請求項３の方法に記載する。同項には、プロセッサが受信データパケットを記憶するバッファ手段をさらに制御することが記載されている。さらに、予約帯域幅を共用するステップは、予約帯域幅の量まで保証帯域幅を共用する第１の処理から構成される。予約帯域幅はデータフローごとに事前定義され、利用可能な帯域幅に含まれる。未予約帯域幅を共用するステップは、それぞれの非保証帯域幅割当に従って複数のデータフロー間で非保証帯域幅を共用する第２の処理から構成される。非保証帯域幅は未予約帯域幅と予約帯域幅の実際には未使用の部分とを含む。未予約帯域幅は予約帯域幅を超えて利用可能な帯域幅に含まれる。非保証帯域幅を共用する第２の処理は、それぞれの調整可能な管理ウエイトをデータフローの少なくとも１つに関連付ける処理を含む。それぞれの非保証帯域幅割当は、これによりデータフローに関連付けられたそれぞれの調整可能な管理ウエイトに応じて決定される。
【００２６】
２つのプロセッサを有する実施態様の欠点は、第１のプロセッサが、リアルタイムクロックに応じて関連するスケジューリングパラメータを更新する動作を保存しない（ｎｏｎ  ｗｏｒｋ  ｃｏｎｓｅｒｖｉｎｇ）原理で動作するが、第２のプロセッサは仮想タイムクロックに応じて関連するスケジューリングパラメータを更新する動作を保存する（ｗｏｒｋ  ｃｏｎｓｅｒｖｉｎｇ）原理で動作するということである。これにより、それぞれのスケジューリングパラメータを扱う２つの別個のスケジューラ、すなわちリアルタイムクロックに対するスケジューリングパラメータを扱う第１のスケジューラと、仮想タイムクロックに対するスケジューリングパラメータを扱う第２のスケジューラが必要になる。
【００２７】
上記の欠点を回避する本発明の別の実施態様を請求項４の方法に記載する。実際、そのような方法は、各サービス時間に、
制御手段に含まれるモード決定手段によって、複数のデータフローの少なくとも１つのアクティブなデータフローについて、前記予約帯域幅に対してそれぞれ利用権限の与えられた予約帯域幅割当を決定するステップと、
少なくとも１つのデータフローがそれぞれ利用権限の与えられた利用権限の与えられた予約帯域幅割当に達しない時に、利用権限の与えられた予約帯域幅割当に達していない複数のアクティブなデータフローの１つを選択し、それによってサービス時間で保証帯域幅を認可するステップと、
複数のアクティブなデータフローの１つがそれぞれ利用権限の与えられた利用権限の与えられた予約帯域幅割当に達した時に、複数のアクティブなデータフローの１つを選択し、それによってサービス時間で非保証帯域幅を認可するステップとを実行する処理をさらに含む。
【００２８】
それに応じて、この実施態様は、各サービス時間に、ＧまたはＮＧのどちらのモードで帯域幅をデータフローに認可するか、すなわち、そのサービス時間に、モードＧで保証帯域幅を認可するか、モードＮＧで非保証帯域幅を認可するかを直ちに示すことができるモード決定手段を使用する。
【００２９】
そのような実施態様の第１の利点は、モード決定手段による上記の決定によって、保証または非保証帯域幅を認可するための後続のデータフロー選択処理を実行するのに実際に必要なのは１つのスケジューラだけであるということである。実際、共通のスケジューラはサービス時間に、モードＧまたはＮＧに従って、モードＧで、利用権限の与えられた予約帯域幅割当に達していない複数のアクティブなデータフローの１つのデータフローを選択するか、モードＮＧで、複数のアクティブなデータフローに１つを選択する。
【００３０】
このようにして、データフローごとに、保証帯域幅認可条件に達したことを、すなわち、それぞれの利用権限の与えられた予約帯域幅割当に達する時を、意味する利用権限の与えられた回数のセルサービス時間の発生が、これまでに認可されているかどうかが決定される。これによって、スケジューラは、少なくとも１つのアクティブなデータフローが保証帯域幅認可条件に達していないモードＧで動作するか、すべてのデータフローが保証帯域幅認可条件に達したか、保証帯域幅認可条件に達していないすべてのデータフローが非アクティブであるモードＮＧで動作する。
【００３１】
そのような実施態様の第２の利点は、モードＧは常にモードＮＧに優先して実行されるので、モードＧで保証帯域幅を共用する時にはスケジューラの動作はここでは動作を保存するタイプであるということである。
【００３２】
そのような実施態様による別の特徴的な機能を請求項５に記載する。同項には、この方法が、
複数のデータフローの各データフローにそれぞれのサービス認可カウンタを関連付けるステップと、
事前定義された期間が開始するたびに、事前定義された期間中の予約帯域幅の対応する利用権限の与えられたサービス認可数に等しい、予約帯域幅から導出されたそれぞれの事前定義された初期クレジット値にサービス認可カウンタを初期化するステップと、
それぞれのサービス認可カウンタがそれぞれの事前定義された最終値に達するまで、サービス時間に処理されるデータフローに関連付けられたそれぞれのサービス認可カウンタを、サービス時間ごとに更新するステップと、
関連付けられたサービス認可カウンタがそれぞれの事前定義された最終値に達した時にデータフローのそれぞれの利用権限の与えられた予約帯域幅割当に達したことを検出するステップとをさらに含むことが記載されている。
【００３３】
この原理は、所定の期間にわたる各データフローのスケジューリング動作が、新しい期間の前記データフローの予約帯域幅の対応する利用権限の与えられたサービス認可数を反映するクレジット値にセッションごとに初期化されるデータフロー単位のサービス認可カウンタによって制御される処理を含む。したがって、すべてのデータフローのそれぞれのサービス認可カウンタの現在の内容をモニタすることによって、スケジューラはそれぞれのサービス時間にモードＧまたはモードＮＧで動作する。
【００３４】
ここで、本発明は上記の実施態様、すなわち、事前定義された期間の初めに所定のクレジット量にそれぞれのサービス認可カウンタを初期化し、関連付けられたデータフローが処理されたたびにそれぞれのサービス認可カウンタを更新する実施態様に限定されないことに留意する必要がある。実際、本発明の代替実施態様はそれぞれのサービス認可カウンタがデータフローの予約帯域幅の利用権限の与えられたサービス認可の対応する数に比例して連続的に提供される場合に実現される。そのような実施態様はより良いパフォーマンスを提供し、事前定義された期間の初めの周期的な初期化を回避する。
【００３５】
別の特徴的な機能を請求項６に記載する。同項には、可変長の完全なパケットを連続的に処理する場合、それぞれのサービス認可カウンタを更新するステップが、処理されたパケットの長さに応じてサービス認可数をカウントすることによって実行されることが記載されている。実際、このようにしてスケジューラは固定長データパケットと同様に可変長データパケット、すなわち、完全なフレームを扱うことが可能になる。
【００３６】
さらに、サービス認可カウンタを初期化するための異なる構成の手法が可能であることに留意すべきである。
【００３７】
事前定義された期間がすべてのデータフローで同じ継続期間であることを述べる第１の解決策を請求項７に記載する。
【００３８】
別の解決策を請求項８に記載する。この解決策は、同じ継続期間の事前定義された期間がすべてのデータフローについて同期化されることを特徴とする。このようにして事前定義された期間が開始するたびに各データフローのサービス認可カウンタを初期化するステップは、すべてのデータフローのすべてのサービス認可カウンタについて同時に実行される。
【００３９】
別の代替解決策を請求項９に記載する。同項には、同じ継続期間の事前定義された期間がすべてのデータフローについて同期化されていないことが記載されている。事前定義された期間が開始するたびにそれぞれのデータフローのサービス認可カウンタを初期化するステップは、すべてのデータフローのすべてのサービス認可カウンタについて同時に実行されない。
【００４０】
事前定義された期間が、データフローごとに異なる場合がある特定の継続期間を有する時間間隔の別の実施態様を請求項１０に示す。実際、そのような代替解決策では、データフロースケジューリング時間間隔はデータフローごとに異なる継続期間を有し、その時間間隔は相互に非同期な位相となる。スケジューラの動作は第１の解決策とは異なりすべてのデータフローについて全く相関性がなく、または前述の解決策と比べて相関性が低い。
【００４１】
本発明を実施するための別の特徴的な機能を請求項１１に記載する。同項では、少なくともそれぞれのアクティブなデータフローが予約帯域幅のそれぞれの利用権限の与えられた予約帯域幅割当に達したか否かを決定するステップが、共通保証帯域幅割当データフローカウンタを使用するモード決定手段を含むことが記載されている。共通保証帯域幅割当データフローカウンタは予約帯域幅のそれぞれの利用権限の与えられた予約帯域幅割当にまだ達していない現在のアクティブなデータフローの数を記録する。
【００４２】
さらに、本発明を実施するために、異なるタイプのスケジューリング構成が可能であることを述べる必要がある。これらのスケジューリング構成を請求項１２、請求項１３、請求項１４、請求項１５、請求項１６、請求項１７および請求項１８に記載し、以下に詳述する。
【００４３】
本発明のプロセッサの３つの適用例を請求項２４、請求項２５および請求項２６に記載する。これを以下に詳述する
プロセッサの出力信号、すなわち、それぞれの予約データパケット割当とそれぞれの未予約データパケット割当の尺度である共用帯域幅信号がプロセッサの出力に提供される。この共用帯域幅信号は異なる方法で実施できることに留意する必要がある。
【００４４】
共用予約帯域幅と共用未予約帯域幅の結果を反映する可能な方法は、後続のデータパケットを共通リンク上で伝送できるデータフローの識別のシーケンスを生成することである。これは、共通リンク上で複数のデータフロー間で利用可能な帯域幅を共用するために通信ネットワーク内に含まれたスケジューラで実現できる。これを請求項２４に記載する。スケジューラはデータパケットが属するデータフローに従って複数のバッファ待ち行列に入力されるデータパケットをソートするためにバッファ手段を含む。バッファ手段に含まれる各バッファ待ち行列はデータフローに関連付けられている。このようにして、異なるバッファ待ち行列内の複数のソートされたデータパケットが提供される。スケジューラはまたソートされたデータパケットの１つを選択し、選択したデータパケットを共通リンク上で伝送するために選択手段を含む。スケジューラは選択手段に結合された本発明によるプロセッサをさらに含む。異なる待ち行列のソートされたデータパケットの選択を制御するために、プロセッサの共用帯域幅信号が選択手段に提供される。
【００４５】
バッファ手段のソート機能は異なる方法で、すなわち物理待ち行列化または論理待ち行列化で実施できることに留意する必要がある。実際、可能な実施態様はデータパケット全体の内容を異なる待ち行列に入れることであるが、別の実施態様では、データパケットが、例えば識別番号に関連付けられ、データパケットの内容が物理的には全くソートされずすべて１つのメモリに記憶される。特定の識別番号に関連付けられたデータパケットをバッファ手段から出力できるようになるまでの更なる処理がその識別番号で実行される。
【００４６】
共用予約帯域幅と共用未予約帯域幅の結果を反映する別の方法は、特定のデータフローの受信データパケットに従って受け入れコマンドまたは拒否コマンドを生成することである。これは、共通リンク上で、共通リンクを介して伝送される複数のデータフローの間で利用可能な帯域幅を共用するために通信ネットワークに含まれるインテリジェントバッファで実現できる。これを請求項２５に記載する。インテリジェントバッファは、データフローの１つの入力データパケットを受け入れるか廃棄するかを決定するために決定手段を含む。入力データパケットが受け入れられると、入力データパケットは、後で共通リンクで伝送されるためにファーストイン・ファーストアウトバッファなどのバッファ手段に記憶される。インテリジェントバッファは決定手段に結合された本発明によるプロセッサをさらに含む。共用帯域幅信号に従って決定を制御するために、プロセッサの共用帯域幅信号が決定手段に提供される。
【００４７】
本発明の第３の適用例は、本発明による少なくとも１つのプロセッサを含む通信システムである。これを請求項２６に記載する。
【００４８】
本発明の上記その他の目的および特徴は、添付の図面に関連する以下の実施形態についての説明を読めばより明らかになり、本発明自体も最もよく理解できるであろう。
【００４９】
まず、図示する機能ブロックの機能説明を行う。この説明に基づいて図の機能ブロックの実施態様は当業者には明らかになろう。さらに、本発明の方法の動作原理についても詳述する。
【００５０】
この特定の実施形態について、とりわけＡＴＭ通信システム内の保証フレーム速度サービスＧＦＲをサポートする非同期転送モード通信マルチサービス交換機に含まれるスケジューラについて説明することが好ましい。
【００５１】
図のスケジューラは各ＧＦＲデータフローに最低保証帯域幅を保証するためにＡＴＭ交換機に含まれる。ＧＦＲデータフローごとにこの最低保証帯域幅をサポートできるように、スケジューラは、すべてのＧＦＲデータフローの所定の利用可能な帯域幅をＡＴＭ交換機から受け取る。各ＧＦＲデータフローに少なくとも最低帯域幅を提供するために使用される利用可能な帯域幅の帯域幅部分は予約帯域幅と呼ばれる。ただし、この予約帯域幅を超えて利用可能な帯域幅は、運用業者がその独自の方針に従って共用できる未予約帯域幅を含む。図を参照すると、共通リンクＬ上で伝送する必要がある複数のデータフロー間で予約帯域幅および未予約帯域幅を共用するスケジューラが示されている。図示のこの共通リンクＬはスケジューラに結合される。
【００５２】
この特定の実施形態では、複数のデータフローが１６に等しいことが好ましい。これは、１６個のＧＦＲデータフローをサポートするためにスケジューラの大きさが決まっていることを意味する。
【００５３】
この実施形態のスケジューラはＡＴＭ交換機をサポートするので、各データフローが仮想識別子で識別されるＡＴＭ仮想コネクション／パスを表すことを理解する必要があることにさらに留意すべきである。
【００５４】
図を参照すると、スケジューラは本発明によるバッファＢＵＦ、セレクタＳＥＬ、およびプロセッサＰを含む。バッファＢＵＦはセレクタＳＥＬおよびプロセッサＰに結合される。セレクタＳＥＬはスケジューラの出力を介して共通リンクＬに結合される。またプロセッサＰはセレクタＳＥＬに結合される。
【００５５】
バッファＢＵＦは１つの入力と１６の出力を備える。図を分かりにくくしないように、５つの出力だけを示している。入力はバッファに向けられた矢印で示され、図示の各出力はバッファＢＵＦから外に向かう矢印で表される。
【００５６】
バッファＢＵＦはサポートするデータフローごとにバッファ待ち行列を含む。図には５つの示された出力に関連付けられた５つのバッファ待ち行列Ｑ１、Ｑ２、Ｑ８、Ｑ９およびＱ１６だけが示されている。各バッファ待ち行列、例えばＱ２は識別番号、例えばＣ２で識別される１つのデータフローに関連付けられる。バッファＢＵＦは、データパケットが属するデータフローの識別子に従ってバッファＢＵＦの入力からスケジューラに入力されてバッファ待ち行列に入れられる各データパケットをソートする。このようにして、複数のソートされたデータパケットが提供される。
【００５７】
この実施形態を説明するために、５つのデータフローＣ１、Ｃ２、Ｃ８、Ｃ９およびＣ１６が５つの図示されたバッファ待ち行列Ｑ１、Ｑ２、Ｑ８、Ｑ９およびＱ１６に従って確立されていると仮定する。ソートされたデータパケットは図中ではデータフロー識別子に従って各待ち行列に含まれる影付きのブロックによって示される。図が事前定義された時間の実際の状況を示すことを理解する必要がある。このようにして、いくつかのバッファ待ち行列が実際にデータパケット、例えばＱ１、Ｑ２およびＱ１６を含み、他のバッファ待ち行列はデータパケット、例えばＱ８およびＱ９を含まないということが図から分かる。各影付きのブロックは関連付けられたデータフローのいくつかのデータパケットを表す。
【００５８】
定期的な時間にバッファ待ち行列の１つを選択して、この選択されたバッファ待ち行列がその待ち行列内の第１のデータパケットをセレクタＳＥＬを介して共通リンクＬに送信できるようにこのバッファ待ち行列に制御信号を提供するために、セレクタＳＥＬがスケジューラ内に含まれる。セレクタＳＥＬは実際にバッファＢＵＦの各出力へのスイッチオン／オフとしての働きをすることに留意する必要がある。さらに、このセレクタＳＥＬとバッファＢＵＦの詳細な動作は当業者には知られており、本発明の範囲外であるためここでは詳述しないことに留意する必要がある。
【００５９】
セレクタＳＥＬの選択機能を制御するためにプロセッサＰがスケジューラ内に含まれる。この動作を実行するために、プロセッサＰはセレクタＳＥＬに制御信号、すなわち共用帯域幅信号ＢＷを提供する。
【００６０】
プロセッサＰは第１のプロセッサＰ１と、第２のプロセッサＰ２と、コントローラＣＴＲＬと、第３の決定装置ＤＥＴ３とメモリＭＥＭを含む。第１のプロセッサＰ１と、第２のプロセッサＰ２と、コントローラＣＴＲＬはメモリＭＥＭに結合される。第１のプロセッサＰ１と第２のプロセッサＰ２もコントローラＣＴＲＬに結合される。
【００６１】
第１のプロセッサＰ１は、それぞれの予約データパケット割当に従って５つの確立されたデータフローの間で利用可能な帯域幅に含まれる予約帯域幅を共用する。データフローは、必要な帯域幅が存在する場合、すなわち、接続が確立され、データパケットを伝送する場合に限って予約帯域幅を受け取るということを理解する必要がある。さらに、この特定の実施形態のデータフローの保証最低帯域幅によれば、それぞれの予約データパケット割当は、ＭＣＲと呼ばれる最低データパケット速度に応じて変化する。この最低データパケット速度はデータフローの接続の確立時にＧＦＲサービス契約内で合意される。このようにして、確立された接続ごとに次の最低データパケット速度が定義される。
【００６２】
データフローＣ１：ＭＣＲ１
データフローＣ２：ＭＣＲ２
データフローＣ８：ＭＣＲ８
データフローＣ９：ＭＣＲ９
データフローＣ１６：ＭＣＲ１６
データフローが確立される場合（例えばＣ２）、及びデータパケットが一定のデータパケット速度で伝送される場合、データフローはこの最低データパケット速度、例えばＭＣＲ２に従って少なくとも必要な帯域幅を受け取る。
【００６３】
第１のプロセッサＰ１は、最低データパケット速度に応じてそれぞれの予約データパケット割当を決定するために第１の決定装置ＤＥＴ１を含む。第１の決定装置ＤＥＴ１がこの最低データパケット速度に従って確立されたデータフローの間で予約帯域幅を共用する方法については後述する。
【００６４】
第１のプロセッサＰ１は必要な計算をするためにさらに計算機を含み、メモリＭＥＭおよびコントローラＣＴＲＬと対話するために読取り装置と書込み装置を含むが、前述したように、これらの機能ブロックは図示されておらず、ここでは詳述しない。
【００６５】
第２のプロセッサＰ２はそれぞれの未予約データパケット割当に従って予約帯域幅を超えて利用可能な帯域幅に含まれる未予約帯域幅を共用する。前述したように、未予約帯域幅は帯域幅の絶対的な一定の量ではない。スケジューラはＧＦＲサポートしているので、未予約帯域幅は未使用の予約帯域幅も含むことは明らかである。未予約帯域幅を共用する方法で運用業者の異なる種類の戦略を反映するために、調整可能な管理ウエイトＷがデータフローの接続の確立時に確立されたデータフローごとに定義される。このようにして、確立されたデータフローごとに次の調整可能な管理ウエイトが定義される。
【００６６】
データフローＣ１：Ｗ１
データフローＣ２：Ｗ２
データフローＣ８：Ｗ８
データフローＣ９：Ｗ９
データフローＣ１６：Ｗ１６
第２のプロセッサＰ２は、これらの調整可能な管理ウエイトに応じてそれぞれの未予約データパケット割当を決定するために第２の決定装置ＤＥＴ２を含む。この特定の実施形態では、未予約帯域幅がアクティブなデータフロー間、すなわち、バッファＢＵＦの関連付けられたバッファ待ち行列に少なくとも１つのデータパケットを有するデータフロー間で共用される。第２の決定装置ＤＥＴ２がアクティブなデータフロー間で未予約帯域幅を共用する方法については後述する。
【００６７】
第２のプロセッサＰ２はまた、必要な計算をするために計算機を含み、メモリＭＥＭおよびコントローラＣＴＲＬと対話するために読取り装置と書込み装置を含むが、前述したように、これらの機能ブロックは図示されておらず、ここでは詳述しない。
【００６８】
またプロセッサＰは、データフローの状態、すなわち、アクティブなデータフローかアクティブでないデータフローかを決定するために、第３の決定装置ＤＥＴ３を含む。この機能を実行するために、第３の決定装置ＤＥＴは、バッファＢＵＦの各バッファ待ち行列、例えばＱ２で、データパケットの最終的な存在を制御する。データ待ち行列内に少なくとも１つのデータパケットが存在する場合、関連付けられたデータフローの状態は「ｙｅｓ」であると確認される。データ待ち行列内にデータパケットが存在しない場合、関連付けられたデータフローの状態は「ｎｏ」であると確認される。各データフローの状態は第３の決定装置ＤＥＴ３によって後述するメモリＭＥＭに提供され、状態変数ＡＣＴと呼ばれる第３の変数によってデータフローごとにこのメモリＭＥＭ内に記憶される。
【００６９】
さらに、プロセッサはメモリＭＥＭを含む。このメモリＭＥＭはデータフローごとにデータフローの接続確立時に定義された情報、すなわちデータフローの識別子Ｃと、それに関連付けられたバッファ待ち行列Ｑと、定義された最低データパケット速度ＭＣＲと、定義された調整可能な管理ウエイトＷと、それと共に３つの変数、すなわち、やはり各データフローに関連付けられた第１の変数Ｒと第２の変数Ｕと、アクティブなデータフローかアクティブでないデータフローかに関するデータフローの状態を反映する状態変数ＡＣＴと呼ばれる第３の変数とを含む。
【００７０】
各データフローに調整可能な管理ウエイトを関連付けるための請求項に記載する関連付け手段は実際にはこのメモリＭＥＭの一部によって実現されるということに留意する必要がある。図を参照すると、前述の定義および関連付けがこのメモリＭＥＭを実施する可能な方法であるテーブルによって示されている。上述の関連付け手段はメモリテーブル内でデータフローのカラムと調整可能な管理ウエイトのカラムの関係によって実施される。
【００７１】
コントローラＣＴＲＬは第１のプロセッサＰ１と第２のプロセッサＰ２を制御する。第１のプロセッサＰ１と第２のプロセッサＰ２からそれぞれ提供された結果、すなわち、それぞれの予約データパケット割当とそれぞれの未予約データパケット割当に従って、コントローラＣＴＲＬは前述した共用帯域幅信号ＢＷを生成する。この共用帯域幅信号は共用予約帯域幅と共用未予約帯域幅のグローバルな結果を反映する。この実施形態では、共用帯域幅信号ＢＷは、実際の時間にセレクタＳＥＬが選択する必要があるバッファ待ち行列、例えばＱ２の識別子を含む。コントローラＣＴＲＬがそのような選択されたバッファ待ち行列の識別子（以下選択バッファ待ち行列と略す）を認識する方法が、後述するアルゴリズムによって実施される。
【００７２】
この好ましい実施形態によれば、本発明のプロセッサＰを実施するために、予約帯域幅の提供が第１のプロセッサＰ１によって実行される動作を保存しない原理によって実行される。第１のプロセッサＰ１が使用しない帯域幅は、第２のプロセッサＰ２によって実行される動作を保存する原理によってアクティブなデータフローに分配される。これらの２つのプロセッサの動作は結合され、第２のプロセッサＰ２は第１のプロセッサＰ１が空き状態の場合にだけ作動する。
【００７３】
動作を保存する原理は、プロセッサＰ２が機能を実行できる時は必ず機能を実行する仮想タイムクロックで実施できることが当業者に知られていることに留意する必要がある。動作を保存する原理の詳細な動作は、本発明の範囲外である。本発明の目的は、第２のプロセッサＰ２の動作原理を実施するために第２のプロセッサＰ２がリアルタイムクロックの代わりに仮想タイムクロックを使用することである。
【００７４】
各データフロー、すなわち各バッファ待ち行列に関連付けられた前述の２つの変数をこれ以降はタイムスタンプＵおよびタイムスタンプＲと呼ぶ（メモリＭＥＭのテーブルを参照）。例えば、データフローＣ２についてはタイムスタンプＵ２およびタイムスタンプＲ２が定義される。このアルゴリズムの動作中にＲタイムスタンプの実際の値とＵタイムスタンプの実際の値は後述する方法に従って増分される。さらに、Ｒタイムスタンプの値は、リアルタイムクロックの実際の値と比較すると、このデータフローについて定義された最低データパケット速度を守るために関連付けられたデータフローのデータパケットを伝送する必要性の尺度を実際に表している。これを理解するために、Ｒタイムスタンプの値は、適宜、最低データパケット速度ＭＣＲに応じて計算され構成されるということを説明する必要がある。実際の時間が左から右に流れる、左から右への時間軸を想定すると、この時間軸上にＲタイムスタンプの異なる値を印すことができる。実際の時間がすべてのＲタイムスタンプのうち最小の値より小さい場合、異なるデータフローの最低データパケット速度がまだ守られている。最低データパケット速度に従って実際のデータパケット速度を得るためにいずれかのデータフロー間で利用可能な帯域幅を共用する必要はない。残りの利用可能な帯域幅は運用業者の戦略に応じてデータフロー間で共用することができる。ただし、実際の時間がＲタイムスタンプの最小値の位置を過ぎると、すなわち、このデータフローのための時間が経過すると、最低データパケット速度を再び守るためにこのデータフローのデータパケットを伝送する時間が起動する。
【００７５】
空のバッファ待ち行列内にデータパケットが到着すると、ＲタイムスタンプとＵタイムスタンプはそれぞれ第１のプロセッサＰ１と第２のプロセッサＰ２によって作動する。データパケットが空の待ち行列、例えばバッファＱ２に到着する状況を仮定すると、タイムスタンプＲ２の値は、このタイムスタンプの以前の値Ｒ２＿ｐｒｅｖ、関連付けられた最低データパケット速度ＭＣＲ２の逆数および実際の時間Ｔを反映するリアルタイムクロック（図示せず）に応じて計算される。
【００７６】
Ｒ２タイムスタンプの初期値は次の公式で第１のプロセッサＰ１によって計算される。
【００７７】
Ｒ２＝Ｍａｘ｛（Ｒ２＿ｐｒｅｖ＋１／ＭＣＲ２）；Ｔ｝
すなわち、
関連付けられた最低データパケット速度ＭＣＲ２の逆数で増分されたタイムスタンプＲ２の以前の値と、
実際の時間
のいずれか大きい値。
【００７８】
同じ例で、タイムスタンプＵ２の値は、このタイムスタンプの以前の値Ｕ２＿ｐｒｅｖ、関連付けられた調整可能な管理ウエイトＷ２の逆数および仮想時間Ｔ＿ｖｉｒｔを反映する仮想タイムクロック（図示せず）に応じて計算される。第２のプロセッサＰ２の仮想時間の値Ｔ＿ｖｉｒｔは、第２のプロセッサＰ２によって最後に選択されたタイムスタンプの値Ｕ２＿ｌａｓｔに等しい。
【００７９】
Ｕ２タイムスタンプの初期値は次の公式で第２のプロセッサＰ２によって計算される。
【００８０】
Ｕ２＝Ｍａｘ｛（Ｕ２＿ｐｒｅｖ＋１／Ｗ２）；Ｔ＿ｖｉｒｔ｝
すなわち、
関連付けられた調整可能な管理ウエイトＷ２の逆数で増分されたタイムスタンプＵ２の以前の値と、
仮想時間Ｔ＿ｖｉｒｔ
のいずれか大きい値。
【００８１】
以降、プロセッサＰに含まれる異なる機能ブロック間での異なる制御信号の使用について説明するが、図を見やすくするために図示はしていない。
【００８２】
選択バッファ待ち行列を決定するために、コントローラＣＴＲＬは共通リンクＬ上の伝送速度に従って事前定義された定期的な時間に、第１のプロセッサＰ１に対し制御信号を提供する。第１の決定装置ＤＥＴ１はメモリＭＥＭ内のアクティブなデータフローに対応するＲタイムスタンプの実際の値のうち最小値の検索を開始する。最小値を有するＲタイムスタンプは最小Ｒタイムスタンプと呼ばれる。最小Ｒタイムスタンプの値はリアルタイムクロックの値と比較される。
【００８３】
リアルタイムクロックの値が最小Ｒタイムスタンプの値より大きい時、このデータフローの最低データパケット速度ＭＣＲを守るために、この最小Ｒタイムスタンプに関連付けられたデータフローのデータパケットを伝送する時間が起動する。第１のプロセッサＰ１は、この最小Ｒタイムスタンプに関連付けられたバッファ待ち行列の識別子、すなわち選択バッファ待ち行列をコントローラＣＴＲＬに提供する。選択バッファ待ち行列は、セレクタＳＥＬが、適合するバッファ待ち行列を選択し、この選択バッファ待ち行列の第１のデータパケットを共通リンクＬ上で伝送することを可能にする帯域幅信号ＢＷ内に、コントローラＣＴＲＬによって入れられる。また第１のプロセッサＰ１はそれに関連付けられたデータフローの最低データパケット速度に応じて最小Ｒタイムスタンプの値を更新する。例えば、最小ＲタイムスタンプがデータフローＣ２のタイムスタンプＲ２であると仮定する。Ｒ２タイムスタンプの新しい値は次の公式で計算される。
【００８４】
Ｒ２＝Ｒ２＿ｐｒｅｖｉｏｕｓ＋１／ＭＣＲ２
この値はメモリＭＥＭ内で第１のプロセッサＰ１によって更新される。
【００８５】
リアルタイムクロックの値が最小Ｒタイムスタンプの値より小さい時、必ずしもこの最小Ｒタイムスタンプに関連付けられていない別のデータフローのデータパケットを伝送する時間がまだ残されている、すなわち、アクティブなデータフロー間で共用するために利用可能な未予約帯域幅が残されている。第１のプロセッサＰ１は未予約制御信号と呼ばれるこの事実を含む制御信号をコントローラＣＴＲＬに提供する。コントローラＣＴＲＬは第１のプロセッサＰ１のそのような未予約制御信号を受信すると、今度は、第２のプロセッサＰ２を作動させるために開始制御信号を第２のプロセッサＰ２に提供する。第２のプロセッサＰ２の第２の決定装置ＤＥＴ２はメモリＭＥＭ内のアクティブなデータフローに対応するＵタイムスタンプの実際の値の最小値の検索を開始する。最小値を有するＵタイムスタンプは最小Ｕタイムスタンプと呼ばれる。第２のプロセッサＰ２は、この最小Ｕタイムスタンプに関連付けられたバッファ待ち行列の識別子、すなわち選択バッファ待ち行列をコントローラＣＴＲＬに提供する。選択バッファ待ち行列は、セレクタＳＥＬが、適合するバッファ待ち行列を選択し、この選択バッファ待ち行列の第１のデータパケットを共通リンクＬ上で伝送することを可能にする帯域幅信号ＢＷ内に、コントローラＣＴＲＬによって入れられる。また第２のプロセッサＰ２はそれに関連付けられたデータフローの調整可能な管理ウエイトに応じて最小Ｕタイムスタンプの値を更新する。例えば、最小ＵタイムスタンプがデータフローＣ２のタイムスタンプＵ２であると仮定する。Ｕ２タイムスタンプの新しい値は次の公式で計算される。
【００８６】
Ｕ２＝Ｕ２＿ｐｒｅｖｉｏｕｓ＋１／Ｗ２
この値はメモリＭＥＭ内で第２のプロセッサＰ２によって更新される。
【００８７】
このアルゴリズムが最終処理変数と呼ばれるもう１つの変数を扱う場合に、本発明のより正確な実施態様が提供されるということに留意する必要がある。この変数の値は、共用帯域幅信号ＢＷに最後に含まれていた選択バッファ待ち行列の識別子を提供したプロセッサである、第１のプロセッサＰ１の名前または第２のプロセッサＰ２の名前である。そのような特別変数の使用は、バッファ待ち行列識別子、例えばＱ１６が、例えばＰ２のプロセッサの結果によって帯域幅信号ＢＷに含まれ、それによって、実施されたアルゴリズムに従って、関連付けられたタイムスタンプＵ１６の値が増分される場合、この関連付けられたタイムスタンプＵ１６の値はこのバッファ待ち行列Ｑ１６が空の場合に最初のデータパケットがバッファ待ち行列Ｑ１６に到着する時に再度計算されないという制御を行う。予約帯域幅のより効率的な使用法を確立するためのそのような最終処理変数を組み込むように上記の実施形態を構成するために、当業者には明らかな多少の変更を上記の実施形態に加えることができる。
【００８８】
本発明の方法の動作原理について、アルゴリズムの実際の動作中の事前定義された期間を説明する例によって説明する。以下の状況とメモリＭＥＭの実際の値を仮定する。次のテーブルに５つの確立されたデータフローＣ１、Ｃ２、Ｃ８、Ｃ９、Ｃ１６とそれに関連付けられたバッファ待ち行列と、その最低データパケット速度と、それに関連付けられたＲタイムスタンプの実際の値と、その調整可能な管理ウエイトと、それに関連付けられたＵタイムスタンプの実際の値とを示す。
【００８９】
【表１】
0004394203.tif 000002
ただし、データフローＣ８とデータフローＣ９のバッファ待ち行列は空であると仮定する。このようにして、これらの２つのデータフローに実際の利用可能な帯域幅を提供する必要はなくなる。
【００９０】
アルゴリズムの動作中、コントローラＣＴＲＬは第１のプロセッサＰ１に次の開始信号を提供すると仮定する。第１のプロセッサＰ１の第１の決定装置ＤＥＴ１はメモリＭＥＭ内のアクティブなデータフローに対応するＲタイムスタンプの実際の値のうち最小値の検索を開始する。最小値を有するＲタイムスタンプはＲ１６＝１０である。Ｒ１６の値はリアルタイムクロックの値と比較される。このリアルタイムクロックはＴ＝１２に等しく、すなわち、リアルタイムクロックの値はＲ１６タイムスタンプの値より大きいと仮定する。このデータフローＣ１６の最低データパケット速度ＭＣＲ１６＝１／１０を守るためにこのデータフロー、すなわちこの最小ＲタイムスタンプＲ１６に関連付けられたＣ１６のデータパケットを伝送する時間が起動する。第１のプロセッサＰ１は、この最小ＲタイムスタンプＲ１６に関連付けられたバッファ待ち行列Ｑ１６の識別子、すなわち選択バッファ待ち行列をコントローラＣＴＲＬに提供する。選択バッファ待ち行列Ｑ１６は、セレクタＳＥＬが、選択バッファ待ち行列Ｑ１６を選択し、この選択バッファ待ち行列Ｑ１６の第１のデータパケットを共通リンクＬ上で伝送することを可能にする帯域幅信号ＢＷ内に、コントローラＣＴＲＬによって入れられる。また第１のプロセッサＰ１はそれに関連付けられたデータフローＣ１６の最低データパケット速度ＭＣＲ１６＝１／１０に応じて最小ＲタイムスタンプＲ１６の値を更新する。Ｒ１６タイムスタンプの新しい値は次の公式で計算される。
【００９１】
Ｒ１６＝Ｒ１６＿ｐｒｅｖｉｏｕｓ＋１／ＭＣＲ１６＝１０＋１０＝２０
この値はメモリＭＥＭ内で第１のプロセッサＰ１によって更新される。
【００９２】
【表２】
0004394203.tif 000003
アルゴリズムは続行し、それによって実際のタイムカウンタも適応されてＴ＝１３まで増分される。
【００９３】
コントローラＣＴＲＬは第１のプロセッサＰ１に次の開始信号を提供する。第１のプロセッサＰ１はメモリＭＥＭ内のＲタイムスタンプの実際の値のうち最小値の検索を開始する。最小値を有するＲタイムスタンプはＲ２＝１８である。最小タイムスタンプ値Ｒ２＝１８はリアルタイムクロックの値Ｔ＝１３と比較される。リアルタイムクロックの値は最小ＲタイムスタンプＲ２の値より大きくなく、必ずしもこの最小ＲタイムスタンプＲ２に関連付けられていない別のデータフローのデータパケットを伝送する時間がまだ残されている、すなわち、アクティブなデータフロー間で共用するために利用可能な未予約帯域幅が残されている。
【００９４】
第１のプロセッサＰ１は未予約制御信号をコントローラＣＴＲＬに提供する。コントローラＣＴＲＬは、第１のプロセッサＰ１のこの未予約制御信号を受信すると、今度は、第２のプロセッサＰ２を作動させるために開始制御信号を第２のプロセッサＰ２に提供する。第２のプロセッサＰ２の第２の決定装置ＤＥＴ２はメモリＭＥＭ内のアクティブなデータフローに対応するＵタイムスタンプの実際の値の最小値の検索を開始する。最小値を有するＵタイムスタンプは最小ＵタイムスタンプＵ２＝２である。第２のプロセッサＰ２は、この最小ＵタイムスタンプＵ２＝２に関連付けられたバッファ待ち行列Ｑ２の識別子、すなわち選択バッファ待ち行列Ｑ２をコントローラＣＴＲＬに提供する。選択バッファ待ち行列Ｑ２は、セレクタＳＥＬが、適合するバッファ待ち行列Ｑ２を選択し、この選択バッファ待ち行列の第１のデータパケットを共通リンクＬ上で伝送することを可能にする帯域幅信号ＢＷ内に、コントローラＣＴＲＬによって入れられる。また第２のプロセッサＰ２はそれに関連付けられたデータフローＣ２の調整可能な管理ウエイトに応じて最小ＵタイムスタンプＵ２の値を更新する。Ｕ２タイムスタンプの新しい値は次の公式で計算される。
【００９５】
Ｕ２＝Ｕ２＿ｐｒｅｖｉｏｕｓ＋１／Ｗ２＝２＋１＝３
第２のプロセッサＰ２はテーブル内で更新するためにこの値をメモリＭＥＭ内に提供する。
【００９６】
【表３】
0004394203.tif 000004
このようにして、利用可能な帯域幅を共用する方法はネットワーク運用業者に未予約帯域幅を共用する独自の方針を定義する融通性を提供する。実際、運用業者は調整可能な管理ウエイトに別の値を提供して、それによってアルゴリズムに別の戦略に従って未予約帯域幅を共用させることができる。
【００９７】
スケジューラに含まれるプロセッサの上記の実施形態は、とりわけ保証フレーム速度サービスＧＦＲカテゴリをサポートするＡＴＭ交換機内で説明されているが、本発明の適用はそのような交換機に限定されるものではない。実際、運用業者の戦略に従って予約帯域幅を超えて利用可能な帯域幅に含まれる未予約帯域幅を複数のデータフロー間で共用する必要がある他の種類の通信システム、例えば、インターネットプロトコルルータなどの可変長パケット通信システムで使用するように上記の実施形態を適応するために、当業者には明らかな多少の変更を上記の実施形態に加えることができる。
【００９８】
第２の実施形態では、さらにスケジューラを使用して、データフローあたり２つのスケジューリングパラメータ、すなわち、保証帯域幅の場合は予約帯域幅スケジューリングパラメータ、非保証帯域幅の場合は管理ウエイトスケジューリングパラメータに基づいて、保証帯域幅と非保証帯域幅の両方を共用できる。
【００９９】
この第２の実施形態の説明ではいくつかの態様に関して本発明の図を参照することを述べる必要がある。さらに、この第２の実施形態を説明する以下の各パラグラフでは、理解を容易にするためにいくつかの略語を使用する。ただし、これらの略語は本発明の図で使用する参照符号を指すものではない。
【０１００】
スケジューラは図示したものとほぼ同じであるが、プロセッサＰは２つの個別の処理手段Ｐ１およびＰ２を含まない。実際、予約帯域幅を共用するステップと非保証帯域幅を共用するステップの２つのステップは複数の（アクティブな）データフロー間の専ら２つの共用処理で構成される。その処理とは、
保証帯域幅を共用する（予約帯域幅の量まで）第１の処理と、
非保証帯域幅を共用する第２の処理である。
【０１０１】
非保証帯域幅は未予約帯域幅と予約帯域幅の実際には未使用の部分とを含む。未予約帯域幅は予約帯域幅を超えて利用可能な帯域幅に含まれる。
【０１０２】
それに応じて、前述の実施形態と比較した原理の違いについてだけ説明する。
【０１０３】
第２の実施形態では、各サービス時間に、予約帯域幅の動作を保存しないタイプのスケジューリングを実行する処理手段Ｐ１の動作の結果として保証帯域幅と非保証帯域幅のどちらの割当を認可するかを決定する代わりに、コントローラＣＴＲＬ内でモード決定手段（図示せず）が使用される。モード決定手段は、各サービス時間に、ＧまたはＮＧのどちらのモードで帯域幅をデータフローに認可するかを直ちに示すことができる。これは、モード決定手段が、そのサービス時間に、保証帯域幅を優先的に認可するか（モードＧで）、そうでなければ非保証帯域幅を認可するか（モードＮＧで）示すということを意味する。さらに、直ちに決定されるモードに従って、保証または非保証帯域幅をデータフローに認可する後続のデータフロー選択処理がスケジューラによって実行される。
【０１０４】
以下に説明するように、２重モードスケジューラのそのような実施態様の利点は次の２つの局面からなる。
【０１０５】
モード決定手段による上記の決定により、各サービス時間で、保証または非保証帯域幅を認可する後続のデータフロー選択処理を実行するためには１つの２重モードスケジューラだけが必要である。
【０１０６】
モードＧは常にモードＮＧに優先して実行されるので、モードＧで保証帯域幅を共用する時にはスケジューラの動作はここでは動作を保存するタイプである。
【０１０７】
モード決定手段を実施する好ましい解決策は、
各データフロー（Ｃ１、Ｃ２、．．．、Ｃ１６）に関連付けられたサービス認可カウンタ（ＣＴ１、ＣＴ２、．．．ＣＴ１６）と、
共通保証帯域幅割当データフローカウンタ（ＧＢＳＤＦＣ）とを含む。
【０１０８】
データフローＣ２に関連付けられたサービス認可カウンタＣＴ２は、保証帯域幅に対するサービス認可の現在のクレジット量を含む。このカウンタは、当該データフローの予約帯域幅ＭＣＲ２に比例する速度で適格の特別サービス認可を常に供給される。
【０１０９】
保証帯域幅割当がデータフローＣ２に供給されるたびに、そのカウンタＣＴ２は減分される。この動作はそのサービス認可量がなくなるまで可能である。データフローＣ２は、そのカウンタＣＴ２に、バッファＢＵＦ内のそれに関連付けられた待ち行列で待ち状態にある次のデータパケットについて保証帯域幅を認可するための十分なクレジットが残っている限り、その予約帯域幅割当に達していない、すなわち、適格のサービス認可クレジットを使い果たしていない。
【０１１０】
共通保証帯域幅割当データフローＧＢＳＤＦＣカウンタは、全予約帯域幅のそれぞれの利用権限の与えられた予約帯域幅割当にまだ達していない現在のアクティブなデータフローの数を記録するために使用される。それに応じて、ＧＢＳＤＦＣカウンタは、その内容が正の値の場合の保証帯域幅割当（モードＧ）またはゼロの場合の非保証帯域幅割当（モードＮＧ）割当割当どちらを実行するかを示す。
【０１１１】
以下、サービス認可カウンタＣＴについて説明する。
【０１１２】
サービス用に選択されたデータフローＣのカウンタＣＴの更新に関して、システムがスケジューリングするデータパケットのタイプによって２つの異なる状況が可能である。
【０１１３】
スケジューラが「セルモード」で動作すると定義される固定長データパケット、すなわちセルのスケジューリング、または
スケジューラが「フレームモード」で動作すると定義される可変長データパケット、すなわちフレームのスケジューリング。
【０１１４】
「セルモード」で動作しているスケジューラの場合、サービス認可カウンタＣＴは、例えば次のように簡単に扱うことができる。ＣＴカウンタにロードされた初期クレジット値は、例えば、１つの期間Ｔのそれぞれの利用権限の与えられた量のクレジットを付与されたセルとして表現されることが好都合である。この利用権限の与えられた量のクレジットを付与されたセルの値は、新しい期間Ｔの初めにＣＴカウンタが初期化された時点でＣＴカウンタ内にロードされる。それに関連付けられたＣＴカウンタの内容がゼロに達していない限り、保証帯域幅割当に対してアクティブなデータフローが選択される。これは、その現在のクレジットを付与されたセルの量が正の値であることを示し、これによって、データフローがその利用権限の与えられた予約帯域幅割当に達していないことを示す。保証帯域幅割当に対してデータフローが供給されるたびに、それに関連付けられたＣＴカウンタは現在の内容を１つだけ減分することによって更新される。
【０１１５】
他方、「フレームモード」で動作するスケジューラの場合、従来の方法は、可変長の各フレームをいくつかの連続する固定長のセグメントに分割することからなる。可変長フレームは事前定義された数であるＳ個の固定長セグメントを含み、同じＳ個の連続するサービス時間を有するスケジューラによって処理される。それに応じて、各サービス時間に、「フレームモード」で動作するスケジューラは、「セルモード」で動作するスケジューラが１つの固定長セルを処理するのと全く同様に、サービス時間あたり１つの固定長セグメントを処理するが、それらの基本的な相違点はスケジューリングの決定にある。実際、スケジューラが「フレームモード」でサービスに可変長フレームを選択する時、スケジューラはフレームのＳ個の連続する固定長セグメント、すなわち、現在のサービス時間から始めてＳ個の連続するサービス時間相当の帯域幅割当を認可することを決定する。これとは逆に、スケジューラが「セルモード」でサービスに固定長セルを選択する時、スケジューラは当該の固定長セル、すなわち、現在のサービス時間相当だけの帯域幅割当を認可することを決定する。このようにして、「フレームモード」で動作するスケジューラの場合、ＣＴカウンタは、例えば次のように扱われる。ＣＴカウンタにロードされた初期クレジット値は、１つの期間のそれぞれの利用権限の与えられた量のクレジットを付与されたセグメントとして表現されることが好都合である。このそれぞれの利用権限の与えられた量のクレジットを付与されたセルの値は、新しい期間の初めにＣＴカウンタが初期化された時点でＣＴカウンタ内にロードされる。それに関連付けられたＣＴカウンタの内容がゼロでないだけでなく、そのデータフローに供給される次のフレームのセグメント数Ｓに等しい限り、保証帯域幅割当に対してアクティブなデータフローが選択される。これは、その現在のクレジットを付与されたセグメントの量がなお正の値であることを示し、したがって、データフローがその利用権限の与えられた予約帯域幅割当に達していないことを示す。さらに、保証帯域幅がデータフローに供給されるたびに、それに関連付けられたカウンタは現在の内容をＳだけ、すなわち、次のフレームの固定長セグメントの数だけ減分することによって更新される。「セルモード」の場合のセルごとに１を減分する処理とは対照的に、各ＣＴカウンタは各フレームの可変長に対応する可変セグメント数Ｓで減分されるので、その内容値は正の値にならない時でも必ずしも正確にゼロにはならない。実際、この値はデータフローに供給される連続するフレームの長さによって変わる。したがって、各データフローごとに、有用なパラメータは、現在のクレジットの内容とそのデータフローに供給される次のフレームのセグメント数Ｓの差として定義されるＣＴカウンタのクレジット収支である。クレジット収支は正またはゼロの場合に、すなわち、現在のクレジットを付与されたセグメントの量がＳより大きいかそれと同じ時に、正のクレジット収支を示し、負の場合に、すなわち、現在のクレジットを付与されたセグメントの量がＳより小さい時に、正のクレジット収支を示す。それに応じて、正のクレジット収支は、スケジューラによるサービスについて次のフレームを適格にするために十分なクレジットが利用できるということを示す。
【０１１６】
各ＣＴカウンタへの利用権限の与えられたサービス認可の提供に関して、導入部で説明した第１の解決策は、事前定義された期間Ｔの初めに、データフローＣに関連付けられた各ＣＴカウンタに所与の量の利用権限の与えられた保証サービス認可ＥＧＳＧを提供することからなる。このクレジット量ＥＧＳＧは予約帯域幅ＭＣＲに比例し、それによってＥＧＳＧ＝ＭＣＲ／Ｔになる。
【０１１７】
ＣＴカウンタをそれぞれのＥＧＳＧクレジット量で定期的に初期化するための異なる手法が考えられる。異なる解決策は、事前定義された期間がすべてのデータフローについて同じであるか否か、また同じである場合には、そのＣＴカウンタがすべて同時に初期化されるか否かによって異なる。
【０１１８】
第１の手法では、すべてのデータフロースケジューリング時間間隔は同じ継続期間を有し、それに関連付けられたＣＴカウンタの初期化はグローバルサイクルＴで同期化されている。その場合、すべてのデータフローのサービス認可カウンタはそれぞれの初期クレジット値ＥＧＳＧによって同時に初期化される。そのような解決策では、スケジューラは通常次のシナリオを実行する。サイクルの初めは、いくつかのデータフローのサービス認可カウンタはゼロではない、したがって、それぞれの利用権限の与えられた予約帯域幅割当に達しておらず、スケジューラは連続する各時間にモードＧを実行する。ある時点では、いくつかのデータフローはまだ同じ状態であるが、それらはいずれも処理待ち状態のセルやセグメントを有していない。すなわちそれらのデータフローはすべて非アクティブである。次いでスケジューラはモードＮＧの実行を開始する。その後、それぞれの利用権限の与えられた予約帯域幅割当に達していないこれらのデータフローの１つまたはいくつかが、少なくとも１つの待ち状態のセルまたは１つの待ち状態のセグメントを有する可能性がある。こうして、それらのデータフローはアクティブになりつつある。次いで、スケジューラはモードＧを再開する。この状況は、すべてのデータフローが最終的にそれぞれの利用権限の与えられた予約帯域幅割当に達するまで継続する。この場合、スケジューラは、すべてのサービス認可カウンタＣＴが再び初期化されるサイクルＴの終わりまで、各連続サービス時間にモードＮＧを実行する。
【０１１９】
第２の手法では、すべてのデータフロースケジューリング時間間隔は同じ継続時間を有するが、それに関連付けられたＣＴカウンタの初期化はすべてのデータフローについて同期化されていない。このようにして、すべてのデータフロースケジューリング時間間隔は同じ継続期間Ｔを有しているが、それぞれの期間Ｔの配置は同じグローバルサイクルで同期化されておらず、多少時間的に分散している。スケジューラの動作は第１の解決策とは異なりもはやすべてのデータフローについて相関性がなく、または少なくともはるかに相関性が低い。そのような解決策では、さまざまなデータフローに関連付けられたサービス認可カウンタの初期化は異なる時間位相となる。そのようなデータフロースケジューリング期間の代替の分散構造は、本発明の原理のスケジューラ動作に完全に従うことが確認できる。実際、スケジューラは、各種ＣＴカウンタの状態にかかわらず、また以前のサービス時間に決定されたモードＧまたはＮＧとは無関係に、各サービス時間にモードＧとモードＮＧのどちらで動作するかを決定するので、各種ＣＴカウンタがいつ相互に初期化されたか、すなわち、同時に初期化されたかどうかは問題でない。データフロースケジューリング時間間隔を分散する主要な効果は、時間の経過と共に保証および非保証帯域幅の完全に混合したサービスタイプを生成することである。実際の適用では、すべてのデータフローは、例えば、ＴのＫ分の１に等しい継続期間によって分離された連続する時間で初期化できる事前定義された数のデータフローサブセットＫに分割できる。
【０１２０】
第３の手法では、事前定義された期間Ｔは各種データフローについて異なる場合がある特定の継続期間を有する。次いでその時間間隔は相互に非同期な位相となる。スケジューラの動作は第１の解決策とは異なりすべてのデータフローについて全く相関性がなく、または前述の解決策と比べて相関性が低い。この場合、各種データフローに関連付けられたサービス認可カウンタＣＴのそれぞれのクレジット値ＥＧＳＧによる初期化は全く異なる時間の位相となる。
【０１２１】
前述の代替解決策と同様、そのような第３の代替解決策では、データフロースケジューリング時間間隔の非同期構成が本発明の原理の２重スケジューラ動作にも完全に従うことが確認できる。データフロースケジューリング時間間隔をもはや相関させないことの主要な効果は、時間の経過と共に保証および非保証帯域幅の完全に混合したサービスタイプを生成することである。そのような第３の代替解決策を実現するために、各サービス認可カウンタの初期化のための異なるオプションが考えられる。これらの異なるオプションは、各データフローＣ２について、すべてのデータフローに同じクレジット値を使用し、異なる時間間隔値を使用する可能性を含む、それぞれの時間間隔値Ｔ２およびそれぞれのクレジット値ＥＧＳＧ２の融通性がある選択を提供する。
【０１２２】
各ＣＴカウンタへの利用権限の与えられたサービス認可の提供に関して、本発明は前述の実施態様、すなわち、事前定義された期間の初めに所定のクレジット量でそれぞれのサービス認可カウンタＣＴを初期化する実施態様に限定されないことに留意する必要がある。実際、本発明の代替実施態様は、セルまたはセグメントの１サービス時間にそれぞれ対応するサービス認可クレジット単位を、各データフローの予約帯域幅に比例して連続的にそれぞれのサービス認可カウンタに提供することによって実現できる。そのような代替実施態様では、Ｂビットのサイズのセルまたはセグメントの場合、予約帯域幅ＭＣＲを有するデータフローのＣＴカウンタはＲｃ＝ＭＣＲ／Ｂであるクレジット率Ｒｃで１サービス認可クレジット単位だけ連続的に増分される。そのような実施態様はより良いパフォーマンスを提供し、事前定義された期間の初めの周期的な初期化を回避する。
【０１２３】
共通保証帯域幅割当データフローカウンタＧＢＳＤＦＣについて以下に説明する。
【０１２４】
これまで予約帯域幅の合計の利用権限の与えられた予約帯域幅割当に達していないアクティブなデータフローの現在の数を正確に追跡するために、アクティブなデータフローがそれぞれの利用権限の与えられた予約帯域幅割当に達するたびに、またはそれぞれの利用権限の与えられた予約帯域幅割当に達していなくてもアクティブなデータフローが非アクティブになるたびに、共通ＧＢＳＤＦＣカウンタは減分される。
【０１２５】
さらに、データフローが以前アクティブであってまだそれぞれの利用権限の与えられた予約帯域幅割当に達していない間にアクティブになるたびに、またはデータフローが以前それぞれの利用権限の与えられた予約帯域幅割当に達したと考えられていたがまだそれぞれの利用権限の与えられた予約帯域幅割当に達していないことが新たに検出されるたびに、共通ＧＢＳＤＦＣカウンタは増分される。それによって、各サービス時間に、共通ＧＢＳＤＦＣカウンタが空でない時に利用権限の与えられた予約帯域幅割当に達していないアクティブなデータフローに保証帯域幅を認可するか、または共通ＧＢＳＤＦＣカウンタが空の時に非保証帯域幅をアクティブなデータフローに認可するかが示される。
【０１２６】
本発明の方法によれば、そのような共通保証帯域幅割当データフローカウンタを各フローに関連付けられたサービス認可カウンタと組み合わせて使用することによって、各サービス時間毎に、２重モードスケジューラによって保証帯域幅と非保証帯域幅のどちらを認可するかを弁別するモード決定手段を実施する効率的な解決策が可能であることが明らかになる。
【０１２７】
各サービス時間毎に、モードＧまたはＮＧで、最初に処理する１つの特定のデータフローを選択できるスケジューリング動作自体に関して、異なるタイプのスケジューリング構成が可能であることを説明する必要がある。
【０１２８】
各サービス時間毎に、スケジューラは、モードＧで保証帯域幅を認可する時は予約帯域幅スケジューリングパラメータに基づいて、または、モードＮＧで非保証帯域幅を認可する時は管理ウエイトスケジューリングパラメータに基づいて、専らスケジューリングを実行する。これはすべてのアクティブなデータフローのサービス認可カウンタの全体の状態をモニタするモード決定手段の結果としてプロセッサが実行するＧまたはＮＧによって変わる。モードＧは常にモードＮＧに優先して実行されるので、モードＧで保証帯域幅を共用する時にはスケジューラの動作はここでは動作を保存するタイプである。
【０１２９】
一般的に言えば、各モードＧまたはＮＧで、例えば、最小タイムスタンプのソータに基づいて、またはラウンドロビンスケジューリング技法と呼ばれる巡回リストに基づいて、異なるタイプの従来のスケジューリング技法を使用できる。組み合わせによって、次に示すように、通常、スケジューリング構成の４つの例が考えられる。
【０１３０】
モードＧとモードＮＧの両方で最小タイムスタンプのソータを使用する解決策１、
モードＧで最小タイムスタンプのソータを使用し、モードＮＧで巡回リストを使用する解決策２、
モードＧとモードＮＧの両方で巡回リストを使用する解決策３、
モードＧで巡回リストを使用し、モードＧで最小タイムスタンプのソータを使用する解決策４。
【０１３１】
これらの異なるタイプのスケジューラ技法についてモードＧとモードＮＧ別に説明する。
【０１３２】
Ａ）モードＧでのスケジューリング
モード決定手段によってモードＧが選択された場合、スケジューラはそのサービス認可カウンタに十分なクレジットが残っている現在アクティブなデータフロー、すなわち、それぞれの利用権限の与えられた予約帯域幅割当に達していないデータフロー間で保証帯域幅の重み付け公平割当分配を実行する。したがって、いずれにせよ、この動作は非アクティブでかつ／または利用権限の与えられた予約帯域幅割当に達したデータフローを除外する必要性を意味する。
【０１３３】
モードＧでの最小タイムスタンプのソータに基づくスケジューリング技法について以下に説明する。保証帯域幅の重み付け公平割当分配はメモリ内のデータフローごとの予約帯域幅スケジューリングパラメータに基づく従来の仮想スペーシングスケジューリングによって達成される。モードＧの各サービス時間毎において、選択されたデータフローは、それぞれの利用権限の与えられた予約帯域幅割当に達していないすべてのアクティブなデータフローの予約帯域幅スケジューリングパラメータのうち最小のタイムスタンプを有するデータフローである。予約帯域幅スケジューリングパラメータタイムスタンプの初期化および計算は第１の実施態様のそれらと類似していることに留意する必要がある。これは、スケジューリングパラメータタイムスタンプがそれに関連付けられた最低セル速度に応じて計算されることを意味する。ただし、ここではスケジューラは、動作を保存する方法でそれぞれの予約帯域幅スケジューリングパラメータタイムスタンプパラメータに基づいてデータフローを扱うことに留意されたい。データフローのスケジューリングパラメータは次のいずれかの場合にメモリから削除される。
【０１３４】
それぞれの利用権限の与えられた予約帯域幅割当に達していない以前アクティブであったデータフローが非アクティブになる場合。
【０１３５】
以前それぞれの利用権限の与えられた予約帯域幅割当に達していなかったアクティブなデータフローが処理され、サービス認可カウンタ内のクレジットを使い果たす場合。
【０１３６】
新しいデータフローの予約帯域幅スケジューリングパラメータは次のいずれかの場合にメモリに導入される。
【０１３７】
それぞれの利用権限の与えられた予約帯域幅割当に達していない以前非アクティブであったデータフローがアクティブになる場合。
【０１３８】
以前それぞれの利用権限の与えられた予約帯域幅割当に達したアクティブなデータフローがサービス認可カウンタ内に供給された新しいサービス認可クレジットを受け取る場合。
【０１３９】
モードＧでの巡回リストに基づくスケジューリング技法について説明する。保証帯域幅の重み付け公平割当分配は、利用権限の与えられたクレジット内容が各データフローのそれぞれの予約帯域幅に比例するそれぞれのサービス認可クレジットカウンタに関連付けられたアクティブな／クレジットを付与されたデータフローの、一般にラウンドロビンスケジューリング技法と呼ばれる１つの簡単な巡回リストによって代替方法として実行できる。アクティブな／クレジットを付与されたデータフローの巡回リストは、それぞれの利用権限の与えられた予約帯域幅割当に達していないすべてのアクティブなデータフローを識別する。
【０１４０】
モードＧの各サービス時間毎において、選択されたデータフローは巡回リストの先頭のデータフローで、その識別は巡回リストの末尾に移動していく。データフローの除外とは対応するエントリをアクティブな／クレジットを付与された巡回リストから削除することを意味する。この処理は、それぞれの利用権限の与えられた予約帯域幅割当に達していない以前アクティブであったデータフローがアクティブになるか、以前それぞれの利用権限の与えられた予約帯域幅割当に達していなかったアクティブなデータフローが処理され、サービス認可カウンタ内のクレジットを使い果たす場合に実行される。新しいデータフローエントリの導入とは、そのデータフローエントリをアクティブな／クレジットを付与された巡回リストに追加することを意味する。この処理は、それぞれの利用権限の与えられた予約帯域幅割当に達していない以前非アクティブであったデータフローがアクティブになるか、以前それぞれの利用権限の与えられた予約帯域幅割当に達したアクティブなデータフローがサービス認可カウンタ内に供給された新しいサービス認可クレジットを受け取る場合に実行される。それに応じて、少なくとも１つのデータフローエントリがこのアクティブな／クレジットを付与された巡回リスト内に存在する限り、モードＧが実行される。
【０１４１】
Ｂ）モードＮＧでのスケジューリング
モード決定手段によってモードＮＧが選択された場合、スケジューラは現在アクティブなすべてのデータフロー間で非保証帯域幅の重み付け公平割当分配を実行する。モードＮＧが実行される場合、すべてのアクティブなデータフローは常にそれぞれのクレジットを使い果たしている、すなわち、それぞれの利用権限の与えられた予約帯域幅割当に達していることに留意する必要がある。これはもしそうでなければモードＧが優先的に実行されるからである。いずれにせよ、この動作は非アクティブなデータフローを除外する必要性を意味する。
【０１４２】
モードＮＧでの最小タイムスタンプのソータに基づくスケジューリング技法について以下に説明する。非保証帯域幅の重み付け公平割当分配はメモリ内のデータフローごとの管理ウエイトスケジューリングパラメータに基づく従来の仮想スペーシングスケジューリングによって達成される。モードＮＧの各サービス時間毎において、選択されたデータフローは、すべてのアクティブなデータフローのうち最小の管理ウエイトスケジューリングパラメータタイムスタンプを有するデータフローである。
【０１４３】
管理ウエイトスケジューリングパラメータタイムスタンプの初期化および計算は第１の実施態様のそれらと類似していることに留意する必要がある。これは、管理ウエイトスケジューリングパラメータタイムスタンプがそれに関連付けられた管理ウエイトに応じて計算されることを意味する。データフローの管理ウエイトスケジューリングパラメータは、以前アクティブであったデータフローが非アクティブになるか、以前それぞれの利用権限の与えられた予約帯域幅割当に達したアクティブなデータフローがそのサービス認可カウンタの初期化によって新しいクレジットを受け取る場合にメモリから削除される。新しいデータフローの管理ウエイトスケジューリングパラメータは、以前非アクティブであったデータフローがアクティブになる場合にメモリに導入される。上記のデータフローの少なくとも１つのエントリがメモリ内に存在する限り、またはモードＧが再開されるまで、モードＮＧが実行される。
【０１４４】
モードＮＧでの巡回リストに基づくスケジューリング技法について説明する。非保証帯域幅のウエイト付け公平割当分配は、サービス認可カウンタＣＴに酷似しているがその内容がデータフローのそれぞれの管理ウエイトスケジューリングパラメータに比例するそれぞれの特別サービス認可カウンタＥＣＴの第２の組に関連付けられたアクティブな／クレジットを付与されたデータフローの、１つの簡単な巡回リストによって代替方法として実行できる。ただし、それぞれのサービス認可カウンタＣＴはそれぞれの利用権限の与えられた予約帯域幅割当に達していないデータフローにだけ使用されるが、それぞれの特別サービス認可カウンタＥＣＴは利用権限の与えられた予約帯域幅割当に達したデータフローにだけ使用されることが分かる。したがって、アクティブなデータフローが保証帯域幅分配のクレジットを使い果たすたびに、同じ関連付けられたカウンタ手段を基本的なクレジットアカウンティングと同様の方法で今度は非保証帯域幅認可クレジットアカウンティングに使用することが考えられる。そうすることによって、データフローがそれぞれの利用権限の与えられた予約帯域幅割当にまだ達していない場合はサービス認可カウンタＣＴとしての働きをし、データフローがそれぞれの利用権限の与えられた予約帯域幅割当に達した場合は特別サービス認可カウンタＥＣＴとしての働きをする、各データフローに関連付けられた１つのカウンタ手段を有利に使用することができる。
【０１４５】
モードＮＧでのスケジューリングに特別サービス認可カウンタを使用するために、管理ウエイトスケジューリングパラメータを、それぞれの事前定義された特別サービス認可クレジットＮＧＳＣ初期値の提供に関して、適した方法でサービス認可カウンタ内に収容する必要がある。これは、各データフローに保証帯域幅割当の新しいサービス認可が再び与えられるまで、非保証帯域幅の関連する分配をデータフローごとに継続して維持する必要があるためである。
【０１４６】
それに応じて、モードＮＧでのすべてのアクティブなデータフローへの非保証帯域幅のそのような継続的な重み付け公平割当分配を維持するために、
それぞれ関連付けられた管理ウエイトスケジューリングパラメータに基づいて、上記カウンタにそれぞれの初期の特別なサービス認可クレジットを再ロードすることによって同時に、
また、これらのすべてのアクティブなデータフローがそれぞれの初期の特別サービス認可クレジットＮＧＳＣを使い果たした場合にのみ、すべてのアクティブなデータフローの特別サービス認可カウンタＥＣＴを再初期化する必要がある。
【０１４７】
実際、そうでなければ、非保証帯域幅の分配はそれぞれの管理ウエイトに比例して実行されないであろう。
【０１４８】
実際の適用の一例では、すべてのアクティブなデータフローの初期特別サービス認可クレジットＮＧＳＣのそのような再初期化は、遅延することがあるサービス認可カウンタの内容を実際に同時に再ロードすることなしに、機能的には必要に応じて同時に達成できる。
【０１４９】
ＥＣＴカウンタ内の特別サービス認可クレジットのそのような遅延再ロードの要求を満たすために、それぞれの事前定義された初期特別サービス認可クレジット値を使い果たし、新しいクレジット値を受け取っていないアクティブなデータフローの追加の予備巡回リストが使用される。次いで、特別認可クレジットを同時に再初期化する必要がある場合、この追加予備リストへの切り替えが、空であることが分かった以前使用していたアクティブな／クレジットを付与された巡回リストを交換することによって実行される。予備巡回リストに切り替える場合、再初期化された特別サービス認可カウンタは実際にはそれぞれの非保証帯域幅認可クレジットをまだ再ロードされていない。ただし、新しいアクティブな／クレジットを付与されたこの追加巡回リストの中に前記カウンタがあるので、モードＮＧの実行時にスケジューラは少なくともそれを選択できる。それに応じて、特別サービス認可クレジットの最初期化の後で初めてデータフローが選択される場合、特別サービス認可カウンタがまだ再ロードされていない間にデータフローが選択されたということが検出される。実際、これは暗黙的な規則によって、特別サービス認可カウンタの再ロードが実際は保留状態であり、したがって、その時点で新しい特別サービス認可クレジットＮＧＳＣを再ロードする必要がある。
【０１５０】
データフローエントリは、次の場合に前記エントリをアクティブな／クレジットを付与された巡回リストから削除することによって除外される。
【０１５１】
アクティブなデータフローが特別サービス認可クレジットを使い果たした際、データフローが非アクティブになる場合、または
以前それぞれの利用権限の与えられた予約帯域幅割当に達したアクティブなデータフローがサービス認可カウンタ内に供給される新しいそれぞれのサービス認可クレジット値を受け取った場合である。さらに、この削除されたエントリは上記の追加の予備巡回リストに入れられるが、これはデータフローがまだアクティブで、特別サービス認可クレジットもそれぞれのサービスクレジット値も残っていない場合に限る。
【０１５２】
さらに、新しいデータフローエントリがアクティブになり、まだ特別サービス認可クレジットが残っている場合には、新しいデータフローエントリはアクティブな／クレジットを付与された巡回リストに導入される。少なくとも１つのデータフローエントリがアクティブな／クレジットを付与された巡回リストにある限り、すなわち、１つのデータフローがアクティブでモードＧが再開されない限り、モードＮＧが実行される。
【０１５３】
上記の第１の解決策、すなわち、タイムスタンプの１つのソータがモードＧとモードＮＧの両方に使用され、データフローごとに、任意のサービス時間に、１つのスケジューリングパラメータ、すなわち、予約帯域幅スケジューリングパラメータまたは管理ウエイトスケジューリングパラメータだけがメモリ内で専ら使用される解決策について説明する。そのような実施態様では、１組のタイムスタンプパラメータにはフィルタリング方法で十分である。実際、モードＧでは、フィルタリングによって使用可能にされるのは保証帯域幅スケジューリングパラメータを適当に有するデータフロー、すなわち、利用権限の与えられた予約帯域幅割当に達していないデータフローだけである。さらに、モードＮＧでは、すべてのアクティブなデータフローが利用権限の与えられた予約帯域幅割当に達しており、したがって、非保証帯域幅スケジューリングパラメータを適当に有しているので、原則的にフィルタリングは不要である。これは、そのような実施態様では、２重モードスケジューラが、保証帯域幅割当を認可されるデータフローの場合の予約帯域幅スケジューリングタイムスタンプパラメータと、非保証帯域幅割当を認可されるデータフローの場合の管理ウエイトスケジューリングタイムスタンプパラメータをメモリ内で専ら混合して扱う。
【０１５４】
以上、本発明の原理を特定の装置に関連して説明してきたが、この説明は例にすぎず、首記の請求の範囲に記載の本発明の範囲を限定するものでないことは明らかに理解できよう。
【図面の簡単な説明】
【図１】本発明によるプロセッサを含むスケジューラを示す図である。
【符号の説明】
Ｑ１、Ｑ２、Ｑ８、Ｑ９、Ｑ１６  バッファ待ち行列
ＢＵＦ  バッファ
ＳＥＬ  セレクタ
Ｌ  共通リンク
Ｐ  プロセッサ
ＢＷ  共用帯域幅信号
ＣＴＲＬ  コントローラ
ＤＥＴ１  第１の決定装置
ＤＥＴ２  第２の決定装置
ＤＥＴ３  第３の決定装置
ＭＥＭ  メモリ
Ｐ１  プロセッサ１
Ｐ２  プロセッサ２
Ｃ１、Ｃ２、Ｃ１６  データフロー
Ｑ１、Ｑ２、Ｑ１６  バッファ待ち行列
ＭＣＲ１、ＭＣＲ２、ＭＣＲ１６  予約帯域幅
Ｒ１、Ｒ２、Ｒ１４  Ｒタイムスタンプ
Ｗ１、Ｗ２、Ｗ１６  調整可能な管理ウエイト
Ｕ１、Ｕ２、Ｕ１６  タイムスタンプ
【図１】
0004394203.tif 000005