(57)【特許請求の範囲】
【請求項１】
複数の進入手段（３１２、３１４、３１６）と複数の進出手段（３２２、３２４、３２６）の間に接続された交換装置においてマルチキャスト・トラフィックのための帯域幅を割り当てる方法であって、
ａ１）各進入手段（３１２、３１４、３１６）につき進入マルチキャスト待ち行列（３４２、３４４、３４６）の占有率を決定し、
ｂ１）最後の帯域幅割り当て期間に進出手段が進入手段から受信したマルチキャスト・セル（３５２、３５４、３５６）の数を求め、
ｃ）各進入／進出手段ペアにつき進出マルチキャスト待ち行列の実効占有率を決定し、
ｄ）各進入／進出手段ペアにつきマルチキャスト・トラフィックのために使用可能な進出帯域幅を決定し、
ａ２）各進出手段につき進出マルチキャスト待ち行列の占有率を決定し、
ｂ２）最後の帯域幅割り当て期間に進入手段が進出手段に送信したマルチキャスト・セル（３５２、３５４、３５６）の数を求め、
ｅ）各進入／進出手段ペアにつき進入マルチキャスト待ち行列の実効占有率を決定し、
ｆ）各進入／進出手段ペアにつきマルチキャスト・トラフィックのために使用可能な進入帯域幅を決定し、
ｇ）ステップｆ）において決定されたマルチキャスト・トラフィックのために使用可能な進入帯域幅（i）と、ステップｄ）において決定されたマルチキャスト・トラフィックのために使用可能な進出帯域幅（ii）のどちらが最小かを決定し、前記いずれかの最小の帯域幅（iまたはii）をマルチキャスト・トラフィックのための帯域幅に割り当て、
ｈ）前記ステップａ１）〜ｇ）の方法において得られた値に従って次の帯域幅割り当て期間の帯域幅割り当てを計算する（２４０）
ステップより成る方法。
【発明の詳細な説明】
本発明は、交換装置の改良に関し、さらに詳細には、かかる装置における帯域幅調整方法に関する。
【０００１】
インターネットによるトラフィックの量は指数関数的増加を示しており、３乃至６ヶ月毎に倍増する勢いである。インターネットプロトコル（ＩＰ）ルータの現在の容量はこの需要を満たすには不充分であるため、１０ギガビットから数テラビットビットの極端に大きい総帯域幅でＩＰトラフィックをルーティングできる製品が必要とされている。かかるルータは、「スーパールータ」と呼ばれる。
【０００２】
さらに、インターネットまたは他の任意のＩＰ系ネットワーク内でマルチキャスト（１つの端末から多数の端末へ、または多数の端末から多数の端末へ）通信をサポートする必要性が増大しつつある。かかるサービスをサポートするために、ＩＰルータは、パケットを複写し、それらをパケット毎に多数の出力へ送る能力を具備しなければならない。サービス品質基準をサポートするために帯域幅の割り当てを厳格に制御するルータでは、コアとなる交換装置に亘ってどれほどの帯域幅をマルチキャスト・トラフィックに割り当てるかを決定する必要がある。
【０００３】
従って、本発明の目的は、上記問題を解消する方法を提供することにある。
【０００４】
本発明の１つの局面によると、複数の進入手段と複数の進出手段の間に接続された交換装置においてマルチキャスト・トラフィックのための帯域幅を割り当てる方法であって、（ａ）各進入手段につき進入マルチキャスト待ち行列の占有率をチェックし、（ｂ）最後の帯域幅割り当て期間に進出手段が進入手段から受信したマルチキャスト・セルの数を求め、（ｃ）各進入手段及び各進出手段において帯域幅を決定し、（ｄ）ステップ（ａ）、（ｂ）及び（ｃ）において得られた値に従って次の帯域幅割り当て期間の帯域幅割り当てを計算するステップより成る方法が提供される。
【０００５】
本発明をよく理解するために、実施例を示す添付図面を参照されたい。
【０００６】
本発明は、「スーパールータ」のノードを形成するために幾つかのＩＰパケット転送機能を連結する非同期転送モード（ＡＴＭ）スイッチまたはクロスバーのような交換機に亘って、マルチキャスト・トラフィックに割り当てる帯域幅を動的に調整する方法に関する。
【０００７】
列の先頭がブロックされるのを阻止するため、ユニキャスト・トラフィックは、別個の論理スケジューリング手段（スケジューラ・ブロックと呼ぶ）の待ち行列に入れられ、何れの進出転送手段かにより宛先が決められる。スケジューラ・ブロックは、リアルタイムＩＰトラフィックのクラスが最小帯域幅を保証されている場合、任意所望の機構（例えば、厳格な優先順位または重み付けしたフェアな待ち行列方式）により、１組の待ち行列（クラス毎または接続毎に）を提供する。
【０００８】
しかしながら、マルチキャスト・トラフィックでは、進出手段の宛先の特異な組合せに応じてトラフィックを待ち行列に待機させるのは実際的でない。その理由は、必要とされる待ち行列の数が、比較的少数の進出ポートでも取り扱い不能な大きさになるからである。従って、図１に示すように、各進出転送手段に、１つのリアルタイム・マルチキャスト待ち行列と、１またはそれ以上の非リアルタイムのマルチキャスト待ち行列を含む別個のマルチキャスト・スケジューラ・ブロックを用いる。
【０００９】
図１は、ユニキャスト・トラフィックのスケジューリングを行うユニキャスト・スケジューラ・ブロック１１０と、マルチキャスト・トラフィックのスケジューリングを行うマルチキャスト・スケジューラ・ブロック１３０とを有する進入転送手段１００を示す。ただ１個のユニキャスト・スケジューラ・ブロック１１０と、１個のマルチキャスト・スケジューラ・ブロック１３０を示すが、特定の用途に応じて任意の数のかかるスケジューラ・ブロックを任意の組合せで用いてもよいことがわかるであろう。
【００１０】
ユニキャスト・スケジューラ・ブロック１１０は、複数の待ち行列１１２、１１４、１１６がスケジューラ１１８に接続され、そのスケジューラの出力１２０が特定の進出転送手段（図示せず）、例えば、進出転送手段１に接続されたものである。ただ３個の待ち行列１１２、１１４、１１６を示すが、特定の用途に応じて任意の数の待ち行列を設けてもよいことが容易にわかるであろう。
【００１１】
スケジューラ１１８は、ユニキャスト帯域幅割り当てにより決まるスケジューリングレートを有し、それぞれの待ち行列１１２、１１４、１１６の先頭セル１２２、１２４、１２６を、矢印１２８で示す優先順位に従って、出力１２０へ送信するように動作する。ユニキャスト帯域幅割り当ては、本願の一部として引用する係属中の英国特許出願第９９０７３１３．２号（事件番号Ｆ２１５５８／９８Ｐ４８６３号）に記載されている。
【００１２】
マルチキャスト・スケジューラ・ブロック１３０は、待ち行列１３２及び１３４、即ち、リアルタイム待ち行列１３２と、非リアルタイム待ち行列１３４より成る。これらの待ち行列１３２、１３４は共にスケジューラ１３６に接続され、このスケジューラを全てのマルチキャスト・トラフィックが通過する。スケジューラ１３６は、出力１３８を有する。
【００１３】
ただ１個のリアルタイム待ち行列と、１個の非リアルタイム待ち行列を示したが、特定の用途に応じて任意の数のかかる待ち行列を使用すればよいことが容易にわかるであろう。
【００１４】
待ち行列１３２、１３４のそれぞれの先頭セル１４２、１４４は、矢印１４６で示す優先順位に従って選択され、スケジューラ１３６から出力１３８へ送られる。
【００１５】
ラインからの入来ＩＰトラフィックは、スケジューラ・ブロックの待ち行列に入れられる。スケジューラブロックの選択は、宛先の進出転送手段と、マルチキャスト・トラフィックかユニキャスト・トラフィックの何れかにより決まる。サービスの等級が、使用する特定の待ち行列を決定する。
【００１６】
図２は、集中型帯域幅割り当て装置２００の全体図である。この装置２００は、複数の進入転送手段２１０と、複数の進出転送手段２２０と、交換ネットワーク２３０と、帯域幅割り当てコントローラ２４０とより成る。各進入転送手段２１２、２１４、２１６、２１８は、帯域幅割り当てコントローラ２４０の制御下で、交換ネットワーク２３０を介して、必要とされる１またはそれ以上の進出転送手段２２２、２２４、２２６、２２８に接続することが可能である。
【００１７】
ただ４個の進入転送手段２１２、２１４、２１６、２１８と、４個の進出転送手段２２２、２２４、２２６、２２８を示したが、特定の用途に応じて任意の数の進入及び進出転送手段を設けてもよいことがわかるであろう。
【００１８】
図２に示すように、各進入転送手段２１２、２１４、２１６、２１８は、リンク２４２、２４４を介して帯域幅割り当てコントローラ２４０とインターフェイスしており、わかりやすくするために、進入転送手段２１２へのリンク２４２、２４４だけを示した。リンク２４２は、各進入転送手段２１２、２１４、２１６、２１８につき、バッファ占有率、セルのパケットの到達レート等に関する情報を、帯域幅割り当てコントローラ２４０へ提供する。リンク２４４は、各進入転送手段２１２、２１４、２１６、２１８へ、帯域幅割り当てコントローラ２４０によるスケジューリングの決定を与える。
【００１９】
同様に、各進出転送手段２２２、２２４、２２６、２２８は、リンク２４６を介して帯域幅割り当てコントローラ２４０とインターフェイスし、帯域幅割り当てコントローラ２４０へ、送信されるマルチキャスト・セルに関する情報を提供する。再び、わかりやすくするために、進出転送手段２２０のリンク２４６だけを示した。
【００２０】
固定された期間、即ち、帯域幅割り当て期間（ＢＡＰ）毎に、各進入転送手段２１２、２１４、２１６、２１８は、バッファ占有率（そして、恐らく他の情報も）をリンク２４２を介して中央の帯域幅割り当てコントローラ２４０へ送る。さらに、各進出転送手段２２２、２２４、２２６、２２８は、最後のＢＡＰに各進入転送手段２１２、２１４、２１６、２１８からいくつのマルチキャスト・セルが受信されたかの情報を、リンク２４６を介して送信する。帯域幅割り当てコントローラ２４０は、次のＢＡＰの間に全ての進入／進出転送手段の対の間で帯域幅の割り当てを行い、これに基づくスケジューリング情報を、リンク２４４を介して、進入転送手段２１２、２１４、２１６、２１８へ与え、それらに次のセル期間に何れのセル／パケットを送信すべきかを指示する。
【００２１】
しかしながら、帯域幅割り当てプロセスにマルチキャスト機能を含めるためには、上記英国特許出願第９９０７３１３．２号に記載されたユニキャストのアルゴリズムに幾つかの付加を行うことが必要である。ユニキャスト帯域幅割り当てアルゴリズムでは、本質的に、進入及び進出手段において利用可能な帯域幅が、進入待ち行列の長さを重み付け係数として用いることにより、競合する転送手段の間に分割される。宛先が進出転送手段ｊである進入転送手段ｉ上のトラフィックのユニキャスト・スケジューラ・ブロックの待ち行列の長さを、ｑijで示す。従って、例えば、進入転送手段ｉから進出転送手段ｊへのユニキャスト・トラフィックに割り当てられる帯域幅の大きさｂｅijを、下記の式で示す。
0004618942.tif 000002
【００２２】
ＡＢＷＥjは、進出転送手段ｊにおいてリアルタイムの予約を考慮した後の利用可能な帯域幅であり、Σｑikは各進入転送手段における宛先が進出転送手段ｊであるデータのバッファ占有率の総和である。項ｑikは、宛先が進出転送手段ｊである進入転送手段ｉにおけるスケジューラ・ブロックのバッファ占有率を表わす。
【００２３】
リアルタイムのマルチキャストの流れについては、ファンアウト及び帯域幅の保証が前もって知られており、全ての進入及び進出条件の総和を、リアルタイムのユニキャスト・トラフィックの流れと同様に、利用可能な帯域幅から差し引くことができる。
【００２４】
非リアルタイムのマルチキャストの流れに必要とされる進出帯域幅の大きさは知られていないため（リアルタイムのマルチキャスト場合と比較すれば）、システムによりその大きさを求める必要がある。必要とされる進出帯域幅の大きさを求める１つの方法は、進出転送手段において、最後のＢＡＰに各進入転送手段から受信したマルチキャスト・セルの数の統計を集計することである。その後、これらの統計を、進入転送手段から中央のスケジューラへＢＡＰ毎に送られる待ち行列統計メッセージに含めることができる。
【００２５】
図１及び２を進入及び進出転送手段に関連して説明したが、進入及び進出装置はかかる装置に限定されず、交換ネットワークの一方の側からもう一方の側へのデータパケットの転送を可能にする任意適当な装置により構成できることがわかる。
【００２６】
図３は、非リアルタイム・マルチキャスト帯域幅割り当ての計算システム３００を示す。このシステム３００は、複数の進入転送手段またはライン・インターフェイス・カード（ＬＩＣカード）３１０と、複数の進出進入転送手段またはライン・インターフェイス・カード（ＬＩＣカード）３２０と、交換ネットワーク３３０とより成る。各進入ＬＩＣ３１２、３１４、３１６は、図示のように、少なくとも１つの待ち行列３４２、３４４、３４６を有する。各進出ＬＩＣ３２２、３２４、３２６は、図示のように、交換ネットワーク３３０を介して１またはそれ以上の進入ＬＩＣ３１２、３１４、３１６からデータを受信する。わかりやすくするため、各進入ＬＩＣ３１２、３１４、３１６においてただ１つの待ち行列３４２、３４４、３４６を示した。
【００２７】
進入転送手段のマルチキャスト待ち行列占有率は、進入転送手段ｉにつきｍｃｑiで示す。最後のＢＡＰに進入転送手段ｉから進出転送手段ｊへ受信したマルチキャスト・セルの数を、ｍｃｑijで示す。進入転送手段ｉから進出転送手段ｊへの非リアルタイムのマルチキャストの流れに割り当てられる帯域幅を、ｍｃｂijで示す。
【００２８】
集中型ユニキャスト帯域幅割り当てアルゴリズムにおけるｑijと同様に、進入帯域幅のフェアな割り当て分に値ｍｃｑiを使用する。
【００２９】
値ｍｃｑijは、進入マルチキャスト待ち行列占有率のスケーリングを行う比率を与えることにより、進出手段のフェアな割り当て分に関与する。これは、進入手段の非リアルタイム（ｎｒｔ）のマルチキャスト待ち行列の占有率（ｍｃｑi）が進出転送手段ｊに対して有する実効重み（ｅｍｃｑijと呼ぶ）が、最後のＢＡＰ期間に進出転送手段ｊが受信する全てのセルに対する進出転送手段ｊが受信するｎｒｔセルの比率により決まることを意味する。従って、それは下記の式により決まる。
0004618942.tif 000003
【００３０】
ｅｍｃｑijの値は、ユニキャストの等価量ｑijと並んで進出帯域幅割り当て機能に用いられる。
【００３１】
従って、マルチキャストトラフィックを含む時の式（１）の等化量は、式（３）で与えられる。
0004618942.tif 000004
【００３２】
上式において、ｂｍｅijは、進入転送手段ｉと、進出転送手段ｊの間に割り当てられる非リアルタイム・マルチキャスト帯域幅であり、ＡＢＷＥj、ｅｍｃｑij及びｑikは前と同じである。
【００３３】
同じ原理を進入手段における帯域幅割り当てに利用可能であり、残った帯域幅は必要とされる任意のフェアな機構により、ユニキャストとマルチキャストの割り当ての間で配分できる。
【００３４】
非リアルタイム・マルチキャスト帯域幅の進入側の式は、下記のようになる。
0004618942.tif 000005
【００３５】
ＡＢＷＩiは、リアルタイム・トラフィックの予約を考慮した後の進入転送手段ｉにおける利用可能な帯域幅である。項ｉｍｃｑijは、ｅｍｃｑijの進入側の等価量であり、進入マルチキャスト待ち行列の占有率をスケーリングする実効重みである。それは、式（５）から計算される。
0004618942.tif 000006
【００３６】
進入転送手段ｉと進出転送手段ｊの間に割り当てられる実際のマルチキャスト帯域幅は、式（６）により決まる、進入及び進出帯域幅割り当ての最小値である。
0004618942.tif 000007
【００３７】
このプロセスが実行された後割り当てから洩れた残りの帯域幅は、任意のフェアな方式でユニキャストとマルチキャストの割り当ての間で配分することが可能である。
【００３８】
上述した方式の利点には、
ａ）帯域幅が１００％の効率で配分される。
【００３９】
ｂ）進入待ち行列の占有率に応じて非リアルタイム帯域幅がフェアに配分される。
【００４０】
ｃ）進入及び進出ポートにおいてクロスバーに割り当てられる帯域幅の全体量を制限することにより、クロスバーのオーバーロードが防止される。
【図面の簡単な説明】
【図１】図１は、進入転送手段のスケジューリング機能を示す。
【図２】図２は、本発明による集中帯域幅割り当てを示す。
【図３】図３は、非実時間マルチキャスト帯域幅割り当てのための実行待ち行列の長さを示す。
【図１】
0004618942.tif 000008
【図２】
0004618942.tif 000009
【図３】
0004618942.tif 000010