(57)【要約】【課題】多段階スイッチネットワークの容量の制約を考慮する方法および装置を提供する。【解決手段】多段階スイッチネットワークを通るトラフィックを評価するシステムを実現する装置が提供される。装置はトラフィックのタイプに応じて1つ以上の入力ポートから1つ以上の出力ポートへトラフィックをルーティングするように構成された多段階スイッチネットワークを通してルーティングされるトラフィックの指示を受信することができる。装置は入力ポートと、出力ポートと、トラフィックのタイプとに基づき、トラフィックのネットワークリソース要求を計算することができる。ここで、ネットワークリソース要求は、トラフィックのタイプに特有であるが、多段階スイッチネットワークを通るトラフィックの特定のルートに一般化されるアルゴリズムによって計算される。また装置は、多段階スイッチネットワークの容量と、トラフィックのネットワークリソース要求との比較に基づいてトラフィックを評価することができる。【選択図】図１
2019195216.tif 000002
【特許請求の範囲】
【請求項１】
多段階スイッチネットワークを通るトラフィックを評価するシステムを実現する装置であって、前記装置はプロセッサと、実行可能な命令を記憶するメモリとを備え、前記命令が前記プロセッサによって実行されるのに応じて前記装置は少なくとも、
トラフィックのタイプに応じて1つ以上の入力ポートから1つ以上の出力ポートへ前記トラフィックをルーティングするように構成された多段階スイッチネットワークを通してルーティングされるトラフィックの指示を受信し、
前記1つ以上の入力ポートと、前記1つ以上の出力ポートと、前記トラフィックのタイプとに基づき、前記トラフィックのネットワークリソース要求を計算し、前記ネットワークリソース要求は、前記トラフィックのタイプに特有であるが、前記多段階スイッチネットワークを通る前記トラフィックの特定のルートに一般化されるアルゴリズムによって計算され、
前記多段階スイッチネットワークの容量と、前記トラフィックの前記ネットワークリソース要求との比較に基づいて前記トラフィックを評価する、装置。
【請求項２】
前記多段階スイッチネットワークが複数の入口スイッチと、複数の中間スイッチと、複数の出口スイッチとを含み、
前記トラフィックが前記1つ以上の入力ポートで前記複数の入口スイッチのうちのそれぞれ1つ以上の入口スイッチに入力され、前記1つ以上の出力ポートで前記複数の出口スイッチのうちのそれぞれ1つ以上の出口スイッチから出力され、
前記中間スイッチの数により前記多段階スイッチネットワークの容量が決まる、請求項1に記載の装置。
【請求項３】
前記ネットワークリソース要求を計算する装置が、前記それぞれ1つ以上の入口スイッチの各入口スイッチと、前記それぞれ1つ以上の出口スイッチの各出口スイッチのアルゴリズムによってリソース要求値を計算することを含み、
前記トラフィックを評価する前記装置が、前記多段階スイッチネットワークの容量と、各入口スイッチと各出口スイッチの前記リソース要求値との比較に基づいて前記トラフィックを評価することを含む、請求項2に記載の装置。
【請求項４】
前記トラフィックのタイプが、前記1つ以上の入力ポートのうちの1つの入力ポートからのトラフィックが前記1つ以上の出力ポートのうちの複数の出力ポートにルーティングされる一対多または多対多であり、
前記アルゴリズムが、前記入口スイッチにおけるネットワークリソース利用を多少偏重して、前記多段階スイッチネットワークを通して前記トラフィックをルーティングするように選択された性能パラメータを含む、請求項2または3に記載の装置。
【請求項５】
前記トラフィックのタイプが、前記1つ以上の入力ポートのうちの複数の入力ポートからのトラフィックが前記1つ以上の出力ポートのうちの1つの出力ポートにルーティングされる多対一または多対多であり、
前記アルゴリズムが、前記中間スイッチにおけるネットワークリソース利用を多少偏重して、前記多段階スイッチネットワークを通して前記トラフィックをルーティングするように選択された性能パラメータを含む、請求項2から4のいずれか一項に記載の装置。
【請求項６】
前記ネットワークリソース要求を計算する前記装置が、前記トラフィックと、前記多段階スイッチネットワークの他の既存のトラフィックの前記ネットワークリソース要求を計算することを含み、
前記トラフィックを評価する前記装置が、前記多段階スイッチネットワークの容量と、前記トラフィックと既存のトラフィックの前記ネットワークリソース要求との比較に基づ
いて前記トラフィックを評価することを含む、請求項1から5のいずれか一項に記載の装置。
【請求項７】
多段階スイッチネットワークを通るトラフィックを評価する方法であって、
トラフィックのタイプに応じて1つ以上の入力ポートから1つ以上の出力ポートへ前記トラフィックをルーティングするように構成された多段階スイッチネットワークを通してルーティングされるトラフィックの指示を受信するステップと、
前記1つ以上の入力ポートと、前記1つ以上の出力ポートと、前記トラフィックのタイプとに基づき、前記トラフィックのネットワークリソース要求を計算するステップであって、前記ネットワークリソース要求は、前記トラフィックのタイプに特有であるが、前記多段階スイッチネットワークを通る前記トラフィックの特定のルートに一般化されるアルゴリズムによって計算されるステップと、
前記多段階スイッチネットワークの容量と、前記トラフィックの前記ネットワークリソース要求との比較に基づいて前記トラフィックを評価するステップとを備える方法。
【請求項８】
前記多段階スイッチネットワークが複数の入口スイッチと、複数の中間スイッチと、複数の出口スイッチとを含み、
前記トラフィックが前記1つ以上の入力ポートで前記複数の入口スイッチのうちのそれぞれ1つ以上の入口スイッチに入力され、前記1つ以上の出力ポートで前記複数の出口スイッチのうちのそれぞれ1つ以上の出口スイッチから出力され、
前記中間スイッチの数により前記多段階スイッチネットワークの容量が決まる、請求項7に記載の方法。
【請求項９】
前記ネットワークリソース要求を計算するステップが、前記それぞれ1つ以上の入口スイッチの各入口スイッチと、前記それぞれ1つ以上の出口スイッチの各出口スイッチのアルゴリズムによってリソース要求値を計算することを含み、
前記トラフィックを評価するステップが、前記多段階スイッチネットワークの容量と、各入口スイッチと各出口スイッチの前記リソース要求値との比較に基づいて前記トラフィックを評価することを含む、請求項8に記載の方法。
【請求項１０】
前記トラフィックのタイプが、前記1つ以上の入力ポートのうちの1つの入力ポートからのトラフィックが前記1つ以上の出力ポートのうちの複数の出力ポートにルーティングされる一対多または多対多であり、
前記アルゴリズムが、前記入口スイッチにおけるネットワークリソース利用を多少偏重して、前記多段階スイッチネットワークを通して前記トラフィックをルーティングするように選択された性能パラメータを含む、請求項8または9に記載の方法。
【請求項１１】
前記トラフィックのタイプが、前記1つ以上の入力ポートのうちの複数の入力ポートからのトラフィックが前記1つ以上の出力ポートのうちの1つの出力ポートにルーティングされる多対一または多対多であり、
前記アルゴリズムが、前記中間スイッチにおけるネットワークリソース利用を多少偏重して、前記多段階スイッチネットワークを通して前記トラフィックをルーティングするように選択された性能パラメータを含む、請求項8から10のいずれか一項に記載の方法。
【請求項１２】
前記ネットワークリソース要求を計算するステップが、前記トラフィックと、前記多段階スイッチネットワークの他の既存のトラフィックの前記ネットワークリソース要求を計算することを含み、
前記トラフィックを評価するステップが、前記多段階スイッチネットワークの容量と、前記トラフィックと既存のトラフィックの前記ネットワークリソース要求との比較に基づいて前記トラフィックを評価することを含む、請求項7から11のいずれか一項に記載の方
法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に多段階スイッチネットワークに関し、特に、トラフィックのネットワークリソース要求に基づいて、Closスイッチネットワークなどの多段階スイッチネットワークを通るトラフィックを評価することに関する。
【背景技術】
【０００２】
ネットワーク管理者は、メッセージトラフィックを送信者から受信者により速くより安く移送する方法を求める。かかる管理者は、既設のスイッチングハードウェアやソフトウェアをより効率的に利用しようと努力する。より効率的に利用することで、さらに投資をする必要なく生産性を向上できる。ネットワークロードを現在利用可能なスイッチングリソースにより効率的に分散することによって、設備投資を増加することなく生産性を上げる目標を達成することができる。
【０００３】
スイッチと他のハードウェアとのロードバランシングが不適正であったり、不足していたりすることで、ネットワークが混雑したり、そうでなければ過剰なメッセージ量や、他の処理問題を負担することになる場合がある。過大な負荷がかかったハードウェアがある一方、近接するハードウェアは十分に活用されていないことがある。既存のネットワークが最適に構成されていないのに、情報技術管理者が新しいハードウェアやソフトウェアに不必要に投資することがある。
Closネットワークなどの多段階スイッチネットワークが、上記問題のいくつかに対処するために開発されている。しかし、これらのスイッチネットワークはトラフィックを移送する能力を高めるものの、スイッチネットワークを通るトラフィックが実行可能であるかどうか判定する際に考慮しなければならないリソースや容量の制約がある。したがって、多段階スイッチネットワークの容量の制約や、他のあり得る問題をさらに考慮する方法および装置を設けることは有益である。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許出願第13／922670号明細書
【特許文献２】特開平０４−３２６８３７号公報
【非特許文献】
【０００５】
【非特許文献１】Anujan VARMA and Suresu CHALASANI，AN INCREMENTAL ALGORITHM FOR TDM SWITHCING ASSIGNMENTS IN SATELLITE AND TERRESTRIAL NETWORKS，IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS，IEEE，１９９２年  ２月  １日，vol. 10, no. 2，pages 364-377
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の実施形態は一般に多段階スイッチネットワークに関し、特に、トラフィックのネットワークリソース要求に基づいて、Closスイッチネットワークなどの多段階スイッチネットワークを通るトラフィックを評価することに関する。実施形態によると、ネットワークリソース要求は、トラフィックのタイプに基づいて計算される。この点に関して、ネットワークリソース要求は、トラフィックのタイプに特有のアルゴリズムによって計算される。しかし、トラフィックのタイプに特有ではあるが、当該アルゴリズムは多段階スイッチネットワークを通るトラフィックの特定のルートに一般化される可能性がある。
【課題を解決するための手段】
【０００７】
本発明の実施形態の一態様によると、多段階スイッチネットワークを通るトラフィックを評価するシステムを実現する装置が提供される。当該装置はプロセッサと、実行可能な命令を記憶するメモリとを含み、当該命令が当該プロセッサによって実行されるのに応じて当該装置は少なくとも複数の動作を実行する。この点に関して、当該装置はトラフィックのタイプに応じて1つ以上の入力ポートから1つ以上の出力ポートへ当該トラフィックを
ルーティングするように構成された多段階スイッチネットワークを通してルーティングされるトラフィックの指示を受信することができる。当該装置は、当該入力ポートと、当該出力ポートと、当該トラフィックのタイプとに基づき、当該トラフィックのネットワークリソース要求を計算することができる。ここで、当該ネットワークリソース要求は、当該トラフィックのタイプに特有であるが、当該多段階スイッチネットワークを通る当該トラフィックの特定のルートに一般化されるアルゴリズムによって計算される。また当該装置は、当該多段階スイッチネットワークの容量と、当該トラフィックの当該ネットワークリソース要求との比較に基づいて当該トラフィックを評価することができる。
【０００８】
幾つかの例において、当該多段階スイッチネットワークが複数の入口スイッチと、複数の中間スイッチと、複数の出口スイッチとを含む。これらの例において、当該トラフィックが当該入力ポートで各入口スイッチに入力され、当該出力ポートで各出口スイッチから出力され、当該中間スイッチの数により当該多段階スイッチネットワークの容量が決まる。
【０００９】
幾つかの例において、当該装置は、各入口スイッチと、各出口スイッチのアルゴリズムによってリソース要求値を計算することができる。これらの例において、当該装置は、当該多段階スイッチネットワークの容量と、各入口スイッチと各出口スイッチの当該リソース要求値との比較に基づいて当該トラフィックを評価することができる。幾つかのさらなる例において、各入口スイッチについて、当該装置は、当該入口スイッチに入力される1つ以上の異なるタイプのトラフィックのトラフィックタイプ要求値の合計を計算することができる。同様に、各出口スイッチについて、当該装置は、当該出口スイッチから出力される1つ以上の異なるタイプのトラフィックのトラフィックタイプ要求値の合計を計算することができる。
【００１０】
幾つかの例において、当該トラフィックのタイプは、1つの入力ポートからのトラフィックが各出力ポートにルーティングされる一対一のトラフィックであってもよい。
【００１１】
幾つかの例において、トラフィックのタイプは、当該入力ポートのうちの1つの入力ポートからのトラフィックが当該出力ポートの複数の出力ポートにルーティングされる一対多または多対多であってもよい。これらの例において、当該アルゴリズムは、当該入口スイッチにおけるネットワークリソース利用を多少偏重して、当該多段階スイッチネットワークを通して当該トラフィックをルーティングするように選択された性能パラメータを含むことができる。
【００１２】
幾つかの例において、当該トラフィックのタイプは、当該入力ポートのうちの複数の入力ポートからのトラフィックが当該出力ポートのうちの1つの出力ポートにルーティングされる多対一または多対多であってもよい。これらの例において、当該アルゴリズムは、当該中間スイッチにおけるネットワークリソース利用を多少偏重して、当該多段階スイッチネットワークを通して当該トラフィックをルーティングするように選択された性能パラメータを含むことができる。
【００１３】
幾つかの例において、当該装置が、当該トラフィックと、当該多段階スイッチネットワークの他の既存のトラフィックの当該ネットワークリソース要求を計算することができる。これらの例において、当該装置が、当該多段階スイッチネットワークの容量と、当該トラフィックと既存のトラフィックの当該ネットワークリソース要求との比較に基づいて当該トラフィックを評価することができる。
【００１４】
実施形態の他の態様において、多段階スイッチネットワークを通るトラフィックを評価する方法とコンピュータ可読記憶媒体とが提供される。
【００１５】
本発明の別の態様によると、多段階スイッチネットワークを通るトラフィックを評価する方法が提供され、当該方法は、トラフィックのタイプに応じて1つ以上の入力ポートから1つ以上の出力ポートへ当該トラフィックをルーティングするように構成された多段階スイッチネットワークを通してルーティングされるトラフィックの指示を受信するステップと、当該1つ以上の入力ポートと、当該1つ以上の出力ポートと、当該トラフィックのタイプとに基づき、当該トラフィックのネットワークリソース要求を計算するステップであって、当該ネットワークリソース要求は、当該トラフィックのタイプに特有であるが、当該多段階スイッチネットワークを通る当該トラフィックの特定のルートに一般化されるアルゴリズムによって計算されるステップと、当該多段階スイッチネットワークの容量と、当該トラフィックの当該ネットワークリソース要求との比較に基づいて当該トラフィックを評価するステップとを備える。
【００１６】
当該方法において、当該多段階スイッチネットワークが複数の入口スイッチと、複数の中間スイッチと、複数の出口スイッチとを含み、当該トラフィックが当該1つ以上の入力ポートで当該複数の入口スイッチのうちのそれぞれ1つ以上の入口スイッチに入力され、当該1つ以上の出力ポートで当該複数の出口スイッチのうちのそれぞれ1つ以上の出口スイッチから出力され、当該中間スイッチの数により当該多段階スイッチネットワークの容量が決まる。
【００１７】
当該方法において、当該ネットワークリソース要求を計算するステップが、当該それぞれ1つ以上の入口スイッチの各入口スイッチと、当該それぞれ1つ以上の出口スイッチの各出口スイッチのアルゴリズムによってリソース要求値を計算することを含み、当該トラフィックを評価するステップが、当該多段階スイッチネットワークの容量と、各入口スイッチと各出口スイッチの当該リソース要求値との比較に基づいて当該トラフィックを評価することを含む。
【００１８】
当該方法において、各入口スイッチの当該リソース要求値を計算するステップが、当該入口スイッチに入力される1つ以上の異なるタイプの当該トラフィックのトラフィックタイプ要求値の合計を計算することを含み、各出口スイッチの当該リソース要求値を計算するステップが、当該出口スイッチから出力される1つ以上の異なるタイプの当該トラフィックのトラフィックタイプ要求値の合計を計算することを含む。
【００１９】
当該方法において、当該トラフィックのタイプが、当該1つ以上の入力ポートのうちの1つの入力ポートからのトラフィックが当該1つ以上の出力ポートのうちの複数の出力ポートにルーティングされる一対多または多対多であり、当該アルゴリズムが、当該入口スイッチにおけるネットワークリソース利用を多少偏重して、当該多段階スイッチネットワークを通して当該トラフィックをルーティングするように選択された性能パラメータを含む。
【００２０】
当該方法において、当該トラフィックのタイプが、当該1つ以上の入力ポートのうちの複数の入力ポートからのトラフィックが当該1つ以上の出力ポートのうちの1つの出力ポートにルーティングされる多対一または多対多であり、当該アルゴリズムが、当該中間スイッチにおけるネットワークリソース利用を多少偏重して、当該多段階スイッチネットワークを通して当該トラフィックをルーティングするように選択された性能パラメータを含む。
【００２１】
当該方法において、当該ネットワークリソース要求を計算するステップが、当該トラフィックと、当該多段階スイッチネットワークの他の既存のトラフィックの当該ネットワークリソース要求を計算することを含み、当該トラフィックを評価するステップが、当該多
段階スイッチネットワークの容量と、当該トラフィックと既存のトラフィックの当該ネットワークリソース要求との比較に基づいて当該トラフィックを評価することを含む。
【００２２】
本発明のさらに別の態様によると、多段階スイッチネットワークを通るトラフィックを評価するためのコンピュータ可読記憶媒体が提供され、当該コンピュータ可読記憶媒体は非一時的であり、内部にコンピュータ可読プログラムコード部が記憶されており、当該コンピュータ可読プログラムコード部がプロセッサによって実行されるのに応じて装置が少なくとも、トラフィックのタイプに応じて1つ以上の入力ポートから1つ以上の出力ポートへ当該トラフィックをルーティングするように構成された多段階スイッチネットワークを通してルーティングされるトラフィックの指示を受信し、当該1つ以上の入力ポートと、当該1つ以上の出力ポートと、当該トラフィックのタイプとに基づき、当該トラフィックのネットワークリソース要求を計算し、当該ネットワークリソース要求は、当該トラフィックのタイプに特有であるが、当該多段階スイッチネットワークを通る当該トラフィックの特定のルートに一般化されるアルゴリズムによって計算され、当該多段階スイッチネットワークの容量と、当該トラフィックの当該ネットワークリソース要求との比較に基づいて当該トラフィックを評価する。
【００２３】
当該コンピュータ可読記憶媒体において、当該多段階スイッチネットワークが複数の入口スイッチと、複数の中間スイッチと、複数の出口スイッチとを含み、当該トラフィックが当該1つ以上の入力ポートで当該複数の入口スイッチのうちのそれぞれ1つ以上の入口スイッチに入力され、当該1つ以上の出力ポートで当該複数の出口スイッチのうちのそれぞれ1つ以上の出口スイッチから出力され、当該中間スイッチの数により当該多段階スイッチネットワークの容量が決まる。
【００２４】
当該コンピュータ可読記憶媒体において、当該ネットワークリソース要求を計算する当該装置が、当該それぞれ1つ以上の入口スイッチの各入口スイッチと、当該それぞれ1つ以上の出口スイッチの各出口スイッチのアルゴリズムによってリソース要求値を計算することを含み、当該トラフィックを評価する当該装置が、当該多段階スイッチネットワークの容量と、各入口スイッチと各出口スイッチの当該リソース要求値との比較に基づいて当該トラフィックを評価することを含む。
【００２５】
当該コンピュータ可読記憶媒体において、各入口スイッチの当該リソース要求値を計算する当該装置が、当該入口スイッチに入力される1つ以上の異なるタイプの当該トラフィックのトラフィックタイプ要求値の合計を計算することを含み、各出口スイッチの当該リソース要求値を計算する当該装置が、当該出口スイッチから出力される1つ以上の異なるタイプの当該トラフィックのトラフィックタイプ要求値の合計を計算することを含む。
【００２６】
当該コンピュータ可読記憶媒体において、当該トラフィックのタイプが、当該1つ以上の入力ポートのうちの1つの入力ポートからのトラフィックが当該1つ以上の出力ポートのうちの複数の出力ポートにルーティングされる一対多または多対多であり、当該アルゴリズムが、当該入口スイッチにおけるネットワークリソース利用を多少偏重して、当該多段階スイッチネットワークを通して当該トラフィックをルーティングするように選択された性能パラメータを含む。
【００２７】
当該コンピュータ可読記憶媒体において、当該トラフィックのタイプが、当該1つ以上の入力ポートのうちの複数の入力ポートからのトラフィックが当該1つ以上の出力ポートのうちの1つの出力ポートにルーティングされる多対一または多対多であり、当該アルゴリズムが、当該中間スイッチにおけるネットワークリソース利用を多少偏重して、当該多段階スイッチネットワークを通して当該トラフィックをルーティングするように選択された性能パラメータを含む。
【００２８】
当該コンピュータ可読記憶媒体において、当該ネットワークリソース要求を計算する装置が、当該トラフィックと、当該多段階スイッチネットワークの他の既存のトラフィックの当該ネットワークリソース要求を計算することを含み、当該トラフィックを評価する装置が、当該多段階スイッチネットワークの容量と、当該トラフィックと既存のトラフィックの当該ネットワークリソース要求との比較に基づいて当該トラフィックを評価することを含む。
【００２９】
本明細書に記載の特徴、機能、および利点は、種々の実施形態において個別に得ることもできるし、さらに他の実施形態において組み合わせることもでき、そのさらなる詳細は以下の説明と図面を参照して明らかとなるであろう。
【００３０】
以上で、本発明の実施形態について一般的に説明した。次に、添付図面について説明する。添付図面は必ずしも正しい縮尺では描かれていない。
【図面の簡単な説明】
【００３１】
【図１】本発明の幾つかの実施形態に従うスイッチ分析システムを示す図である。
【図２】実施形態に従う多段階スイッチネットワークのブロック図である。
【図３】幾つかの実施形態に従う、図2の多段階スイッチネットワークを流れるトラフィックの一例を示す図である。
【図４】幾つかの実施形態に従う、多段階スイッチネットワークを通してルーティングされる異なるタイプのトラフィックを示す図である。
【図５】実施形態に従う、多段階スイッチネットワークと、それを通してルーティングされる異なるタイプのトラフィックの例を示す図である。
【図６】実施形態に従う、図5の多段階スイッチネットワークを通してルーティングされる1つ以上の異なるタイプのトラフィック入力のトラフィックタイプ要求値を計算するアルゴリズムの適用を示す図である。
【図７】実施形態に従う、図5の多段階スイッチネットワークを通してルーティングされる1つ以上の異なるタイプのトラフィック入力のトラフィックタイプ要求値を計算するアルゴリズムの適用を示す図である。
【図８】実施形態に従う、図5の多段階スイッチネットワークを通してルーティングされる1つ以上の異なるタイプのトラフィック入力のトラフィックタイプ要求値を計算するアルゴリズムの適用を示す図である。
【図９】実施形態に従う、図5の多段階スイッチネットワークを通してルーティングされる1つ以上の異なるタイプのトラフィック入力のトラフィックタイプ要求値を計算するアルゴリズムの適用を示す図である。
【図１０】実施形態に従う、図5の多段階スイッチネットワークを通してルーティングされる1つ以上の異なるタイプのトラフィック入力のトラフィックタイプ要求値を計算するアルゴリズムの適用を示す図である。
【図１１】実施形態に従う、トラフィック評価システムのブロック図である。
【図１２】本発明の実施形態に従う方法における種々の動作を含むフローチャートを示す図である。
【図１３】本発明の幾つかの実施形態に従う、トラフィック評価システムを実現する装置を示す図である。
【発明を実施するための形態】
【００３２】
本発明の幾つかの実施態様を、添付図面を参照して以下でより十分に説明する。これらは本発明の幾つかの実施態様であって、全ての実施態様を示すものではない。実際、本発明の様々な実施態様は、多くの異なる形式で実現でき、本明細書に記載の実施態様に限定されるとみなすべきではない。これらの実施態様は、本開示が詳細で十分なものになり、
本発明の範囲を当業者に完全に伝えるように提供されている。明細書全体にわたって、同じ符号は同じ要素を指す。背景となる例は、特許文献１に開示されている。
【００３３】
図1は本発明の幾つかの実施形態に従うスイッチ分析システム100を示す。このスイッチ分析システムは、1つ以上の機能または動作を行うために互いに連結された、それぞれ複数である複数の異なるサブシステムのいずれかを含むことができる（それぞれ個別のシステム）。図1に示すように、例えば、スイッチ分析システムは、多段階スイッチネットワーク102と、多段階スイッチネットワークを通るトラフィックを評価する（トラフィック評価）システム104とを含むことができる。一緒に示してはいるが、多段階スイッチネットワークとトラフィック評価システムのいずれかまたは両方が、他方に対して別個のシステムとして機能または動作できることを同じく理解されたい。幾つかの例における多段階スイッチネットワークは通信衛星に搭載して、例えばかかる通信衛星のトランスポンダー内で動作することができる。また、スイッチ分析システムは、1つ以上の付加的な、または図1に示すものに替わるサブシステムを含むことができることを理解されたい。かかるサブシステムの一例が、上記に参照して組み込んだ特許文献１にさらに記載されている。
【００３４】
多段階スイッチネットワーク102は、時分割多重アクセス（TDMA）多段Closスイッチネットワークなど、複数段に配置された複数のグループのスイッチを含むことができる。TDMAクロスバースイッチは、デジタル対称マトリクス（DSM）と呼ぶことがある。物理的回路スイッチングにおいて、最大の実現可能な単一クロスバースイッチを超える容量が必要な場合、Closスイッチネットワークが適切である場合がある。複数のクロスポイントであり得るクロスバーを実現するのに伴う複雑度は、入力／出力の数の二乗に比例する場合があり、一方Closネットワークの複雑度は線形である場合がある。（Closスイッチネットワークの各クロスバースイッチを構成する）クロスポイントの必要数は、多段階スイッチネットワーク全体が単一の大きいクロスバースイッチで実現される場合よりも少ない場合がある。
【００３５】
図示したように、多段階スイッチネットワーク102は、入口段と、中間段と、出口段とを含むことができ、入口段と出口段を時々「入力段」と「出力段」と呼ぶ。各段は、それぞれ複数のスイッチ、すなわち複数の入口スイッチ106（時々「入口段スイッチ」と呼ぶ）と、複数の中間スイッチ108（時々「中間段スイッチ」と呼ぶ」）と、複数の出口スイッチ110（時々「出口段スイッチ」と呼ぶ）とを含む。中間スイッチは各相互接続112、114を介して入口スイッチと出口スイッチに連結され、幾つかの例では、中間スイッチの数により多段階スイッチネットワークの容量が決まる。幾つかの例において、各段のスイッチは、同数の入力と出力を備えるクロスバースイッチであってもよい。この点に関して、多段階スイッチネットワークは一般に、各入口スイッチと、中間スイッチと、出口スイッチの入力と出力の切り替えをサポートすることができる。
【００３６】
入口スイッチ106に入ったトラフィック（例えば、メッセージ、データ、コール）は相互接続112を介して、利用可能ないずれかの中間スイッチ108にルーティングすることができる。その後トラフィックは、利用可能な中間スイッチを通って相互接続114をわたり、適切な出口スイッチ110に移動できる。この点に関して、中間スイッチは、入口スイッチを中間スイッチに接続するリンクと、中間スイッチを出口スイッチに接続するリンクの両方が利用可能であれば、特定の新しいトラフィックのために利用可能であるとみなすことができる。
【００３７】
入口スイッチ106と、中間スイッチ108と、出口スイッチ110のそれぞれは、ある瞬間に、該スイッチの出力容量とは異なる入力または受信容量を有することがある。幾つかの例において、各種段スイッチのそれぞれが、出力用の複数のチャネルと、入力用の複数のチャネルとを含むことができる。そしてこれらのチャネルのそれぞれは、複数のサブチャネ
ルを含むことができる。
【００３８】
実施形態によると、何らかのスイッチルーティングアルゴリズムに従って、トラフィックが多段階スイッチネットワーク102を通してルーティングされる。当該アルゴリズムは、多段階スイッチネットワークの負荷を軽減しスイッチリソースをより効率的に利用可能にし高いトラフィック負荷をサポートできる所定のスイッチの入力チャネルと出力チャネルの組み合わせを求める。多段階スイッチネットワーク内のトラフィックの移送には、相互接続112、114を介して、1つのスイッチの出力側または出力端から他のスイッチの入力側への伝送を含めることができる。一例において、図2および図3に関連して説明するように、ある段の第1スイッチの所定の出力サブチャネルを出たトラフィックを、相互接続を介して他の段の第2スイッチの所定の入力サブチャネルに伝送することができる。
【００３９】
図2は多段階スイッチネットワーク200のブロック図であり、幾つかの例において、図1の多段階スイッチネットワーク102に対応することができる。図示したように、多段階スイッチネットワークは、入口スイッチ206と、中間スイッチ208と、出口スイッチ210とを含み、それらは入口スイッチ106と、中間スイッチ108と、出口スイッチ110にそれぞれ対応する。各相互接続212、214を介して中間スイッチを入口スイッチと出口スイッチに連結することができ、幾つかの例において、これらの相互接続は相互接続112、114に対応する。
【００４０】
説明のために、図2では入口スイッチ206と、中間スイッチ208と、出口スイッチ210とをそれぞれの入力および出力機能に分割し、それらを別個に示しているが、入口スイッチと、中間スイッチと、出口スイッチを単一の物理装置として実現することができる。この点に関して、入口スイッチはそれぞれスイッチ入力206aとスイッチ出力206bとを含むことができる。中間スイッチはそれぞれスイッチ入力208aとスイッチ出力208bとを含むことができる。また出口スイッチはそれぞれスイッチ入力210aとスイッチ出力210bとを含むことができる。
【００４１】
さらに、説明のために、多段階スイッチネットワーク200の構成要素を、ユーザー入力216と、アルゴリズム領域218と、ユーザー出力220とに分割して示す。図示したように、入口スイッチ入力206aは、これらの構成要素はユーザートラフィックの受信ポイントであるため、ユーザー入力として示す。入口スイッチ出力206bと、中間スイッチ入力および出力208a、208bと、出口段入力210aはアルゴリズム領域として示しているが、スイッチルーティングアルゴリズムが動作できるのはこれらの構成要素上であるからである。そして、出口スイッチ出力210bはユーザー出力として示しているが、これらの構成要素はユーザートラフィックの伝送または出口ポイントであるからである。
【００４２】
図2はまた、トラフィックが、相互接続212、214を介して、入口スイッチ出力206bから中間スイッチ入力208aへ移動し、中間スイッチ出力208bから出口スイッチ入力210aに移動する選択肢を表す複数の一方向接続を示している。幾つかの例において、構成要素間のサポート伝送は短期間であってもよいし、伝送が完了すると存続しなくてもよい。
【００４３】
入口スイッチ206と、中間スイッチ208と、出口スイッチ210とはそれぞれ、出力222用の複数のチャネルと、入力224用の複数のチャネルを含み（図2においてそれぞれのうち1つが具体的に表記されている）、これらのチャネルはそれぞれ、複数のサブチャネル226を含むことができる（図2において1つが具体的に表記されている）。図2に示すように、例えば、各入口スイッチ入力206a（すなわち、各入口スイッチのスイッチ入力）は入力用に3つのチャネルを提供し（垂直に列で示す）、これら3つのチャネルはそれぞれ4つのサブチャネルを含む（水平に列で示す）。同様に、例えば、各入口スイッチ出力206bは出力用に3つのチャネルを提供し、これらのチャネルはそれぞれ4つのサブチャネルを含む。各中
間スイッチ入力208aおよび出力208bと、各出口スイッチ入力210aおよび出力210bは同様に入力および出力用にそれぞれ3つのチャネルを提供し、各チャネルは4つのサブチャネルを含む。各種段のスイッチの3つのチャネルは、上部チャネル、中間チャネル、下部チャネルと呼ぶことがある。
【００４４】
スイッチルーティングアルゴリズムにより、送信するスイッチの所定チャネルからのトラフィックが、受信するスイッチの所定チャネルに送られることを決定することができ、幾つかの例において、この決定は、現在のスイッチ利用および／または1つ以上の他の要因に基づくことができる。図2の例において、一番上に示す入口スイッチ出力206bの中間チャネル222を出たトラフィックは、相互接続212を介して中間に示す中間スイッチ入力208aの上部チャネル224に向かう。中間に示す入口スイッチ出力の上部チャネルからのトラフィックは一番上に示す中間スイッチ入力の中間チャネルに送られる。一番下に示す入口スイッチ出力の下部チャネルからのトラフィックは、一番下に示す中間スイッチ入力の下部チャネルに送られる。上記は、入口スイッチ206のスイッチ出力から相互接続を介して中間スイッチ208のスイッチ入力へと示された全部で9つの伝送のうちの3つの例である。図2は同様に、中間スイッチ208のスイッチ出力208bから他の相互接続を介して出口スイッチ210のスイッチ入力210aへの9つの伝送を示している。相互接続のいずれか一方または両方をわたる伝送に関して他のバリエーションも可能であり、したがってこの例に限定されるとみなすべきではない。
【００４５】
図3は、本発明の幾つかの実施形態に従う、図2の多段階スイッチネットワーク200を流れるトラフィックの一例を示す。図3は一番上に示す入口スイッチ入力206aの上部チャネルで多段階スイッチネットワークに入る、A1およびA2と示される2つのデータを示している。データA1は一番上に示す入口スイッチ出力206bの上部チャネルにおいて出る。一番上に示す入口スイッチ出力の上部チャネルにおいて出たデータA1は、サブチャネルインデックス00の入力／チャネル0からサブチャネルインデックス01の出力／チャネル0へのA1の2次元マッピングであってもよい。データA2は一番上に示す入口スイッチ出力の下部チャネルにおいて出る。相互接続212を介して入口スイッチ206から中間スイッチ208への伝送は上述のように行うことができる。その後、データA1は一番上に示す中間スイッチ入力208aの上部チャネルに向けられ、データA2は一番下に示す中間スイッチ入力の上部チャネルに向けられる。
【００４６】
データA1およびA2はそれぞれ、ロードや他の理由でそこから中間スイッチに入った異なるサブチャネルにおいて、一番上および一番下に示す中間スイッチ208を出る。例えば、データA1は上部チャネルで一番上に示す中間スイッチ入力208aに入り、一番上に示す中間スイッチ出力208bの中間チャネルにおいて出る。図3はデータA1とA2が、一番上に示す入口スイッチ入力206aにおけるそれぞれの起点から中間部に示す出口スイッチ出力210bにおけるそれぞれの出口ポイントまで別個の経路を取って多段階スイッチネットワーク200をわたることを示している。幾つかの例において、スイッチルーティングアルゴリズムによって、受信するスイッチの容量を最適に利用することができ、ロードバランシングを促進し、より高いトラフィック負荷をサポートできるように、データA1とA2を送ることができる、相互接続212、214をわたる経路を決定することができる。多段階スイッチネットワークを通してトラフィックをルーティングすることができるスイッチルーティングアルゴリズムに関するさらなる情報については、上記に引用して組み込んだ特許文献１を参照されたい。
【００４７】
図4は、種々の実施形態に従う、多段階スイッチネットワーク102（幾つかの例ではスイッチネットワーク200）を通してルーティングされる、「一対一」、「一対多」、「多対一」、および「多対多」を含む、異なるタイプのトラフィックを示す。図4において、多段階スイッチネットワークの内外に通じる複数の小さい矩形が示されている。多段階スイ
ッチネットワーク内に通じる小さい矩形は入口スイッチ106への入力ポート402を示し、中の文字はそれらの入力ポートにおける多段階スイッチネットワークへの別個のトラフィック入力を示す。またスイッチネットワークの外へ通じる小さい矩形は出口スイッチ110からの出力ポート404を示し、中の文字は、それらの出力ポートにおける多段階スイッチネットワークからの別個のトラフィック出力を示す。
【００４８】
その種々のタイプに従って、トラフィックは入力ポート402で各入口スイッチ106に入力され、各出口スイッチ110から出力ポート404で出力される。一対一のトラフィック（時々「ユニキャスト」トラフィックと呼ぶ）は、1つの入力ポートからのトラフィックが各出力ポートにルーティングされるトラフィックのタイプであることがある。一対多トラフィック（時々「マルチキャスト」または「ファンアウト」トラフィックと呼ぶ）は、1つの入力ポートからのトラフィックが複数の出力ポートにルーティングされるトラフィックのタイプであることがある。逆に、多対一トラフィック（時々、「結合」または「ファンイン」トラフィックと呼ぶ）は、複数の入力ポートからのトラフィックが1つの出力ポートにルーティングされるトラフィックのタイプであることがある。多対多トラフィック（時々、「ファンインおよびファンアウト」トラフィックと呼ぶ）は、一対多と多対一の特徴を含むトラフィックのタイプであることがある。
【００４９】
図4に示すように、一対一のトラフィックは、各入力ポート402で多段階スイッチネットワーク102に入力され、多段階スイッチネットワークを通してルーティングされ各出力ポート404で出力される3つの別個のトラフィック（A、B、C）として示すことができる。一対多トラフィックは、単一の入力ポートで多段階スイッチネットワークに入力され、多段階スイッチネットワークを通してルーティングされ複数の出力ポートで出力される1つの別個のトラフィック（A）として示すことができる。多対一トラフィックは、各入力ポートで多段階スイッチネットワークに入力され、多段階スイッチネットワークを通してルーティングされ単一の出力ポートで出力される3つの別個のトラフィック（A＋B＋C）として示すことができる。多対多トラフィックは、各入力ポートで多段階スイッチネットワークに入力され、多段階スイッチネットワークを通してルーティングされ1つ以上の出力ポートで出力される3つの別個のトラフィック（A＋B＋C）として示すことができる。多対多において、別個のトラフィックのうちの1つを複数の出力ポートで出力してもよいし、別個のトラフィックの複数を単一の出力ポートで出力してもよい。
【００５０】
図5は、幾つかの実施形態に従う、図2（および図3）と図4の概念を組み合わせた、多段階スイッチネットワーク500と、それを通してルーティングされる異なるタイプのトラフィックの例を示す。幾つかの例において、図5の多段階スイッチネットワーク500は図2の多段階スイッチネットワーク200（そしてまた、図1のネットワーク102）に対応していてもよい。図示したように、多段階スイッチネットワークは入口スイッチ506と、中間スイッチ508（ひとまとめに示す）と、出口スイッチ510とを含み、それぞれ入口スイッチ206、中間スイッチ208、出口スイッチ210に対応していてもよい。
【００５１】
図5の例において、多段階スイッチネットワーク500は3つの入口スイッチ506（I0、I1、I2と示す）と、3つの出口スイッチ510（E0、E1、E2と示す）とを含む。入口スイッチと出口スイッチはそれぞれ、入力／出力用に3つのチャネルを含み、これらのチャネルはそれぞれ5つのサブチャネルを含む。上述のように、トラフィックを各入口スイッチに向けて入力ポートで入力し、各出口スイッチから出口ポートで出力することができ、幾つかの例において、これらの入力ポートおよび出力ポートは入力ポート402、出力ポート404に対応することができる。幾つかの例において、これらの入力ポートおよび出力ポートは、入口スイッチおよび出口スイッチのチャネルおよびサブチャネルのそれぞれに対応するチャネルおよびサブチャネルを含むことができる。
【００５２】
入力ポート／入口スイッチ506のサブチャネルは、3つの入口スイッチをわたるチャネルおよびサブチャネルによって示すことができる。したがって、例えば、入力ポート／入口スイッチI0は、サブチャネル00、01、02、03、04を備えるチャネル0と、サブチャネル10、11、12、13、14を備えるチャネル1とを含むことができる。入力ポート／入口スイッチI1は、サブチャネル20、21、22、23、24を備えるチャネル2と、サブチャネル30、31、32、33、34を備えるチャネル3とを含むことができる。また入力ポート／入口スイッチI2は、サブチャネル40、41、42、43、44を備えるチャネル4と、サブチャネル50、51、52、53、54を備えるチャネル5とを含むことができる。出力ポート／出口スイッチ510はそれぞれ同様に表示することができる。
【００５３】
図5はまた、幾つかの実施形態に従う、1つ以上の入力ポート／入口スイッチ506から1つ以上の出力ポート／出口スイッチ510へ多段階スイッチネットワーク500を通してルーティングされる異なるタイプのトラフィックの例を示す。4つの異なるタイプのトラフィックはそれぞれ、1つ以上の入口スイッチ（I）のセットから1つ以上の出口スイッチ（E）のセットへルーティングされる1つ以上の別個のトラフィックを含むトラフィック（T）のセットに関して図示され、以下に説明される。
【００５４】
図5に示すように、例えば、一対一のトラフィックが、入力ポート／入口スイッチI0のサブチャネルインデックス04においてチャネル0から、出力ポート／出口スイッチE0のサブチャネルへルーティングされる。別の例では、一対多トラフィックが、入力ポート／入口スイッチI1のサブチャネルインデックス34においてチャネル3から、出力ポート／出口スイッチE1、E2のサブチャネルへルーティングされる。さらなる例では、多対一トラフィックが、入力ポート／入口スイッチI1のサブチャネルインデックス30においてチャネル3から、また入力ポート／入口スイッチI2のサブチャネルインデックス50においてチャネル5から、出力ポート／出口スイッチE2のサブチャネルへルーティングされる。またさらに別の例では、多対多トラフィックが、入力ポート／入口スイッチI0のサブチャネルインデックス14においてチャネル1から、また入力ポート／入口スイッチI1のサブチャネルインデックス24においてチャネル2から、出力ポート／出口スイッチE0、E1のサブチャネルへルーティングされる。
【００５５】
図1に戻り、さらに図4を参照すると、トラフィック評価システム104は一般に、トラフィックのネットワークリソース要求に基づいて、多段階スイッチネットワーク102を通るトラフィックを評価するように構成される。この点に関して、トラフィック評価システムは、トラフィックのタイプ（例えば、一対一、一対多、多対一、多対多）に応じて、1つ以上の入力ポート402から1つ以上の出力ポート404へ多段階スイッチネットワークを通してルーティングされるトラフィックの指示を受信するように構成される。トラフィックには、複数の異なるタイプのいずれかの1つ以上の別個のトラフィックを含むことができ、時々トラフィックルーティングプランを示してもよいし、その中に含まれてもよい。トラフィックは、多段階スイッチネットワークを通してルーティングされるトラフィックや、多段階スイッチネットワークの既存のトラフィックや、ルーティングされるトラフィックと多段階スイッチネットワークに既存のトラフィックの組み合わせでもよい。
【００５６】
トラフィック評価システム104は、入力ポート402と、出力ポート404と、トラフィックのタイプに基づいて、トラフィックのネットワークリソース要求を計算することができる。以下により詳細に説明するように、トラフィックのタイプに特有であるが、多段階スイッチネットワーク102を通るトラフィックの特定のルートに一般化できるアルゴリズムによって、このネットワークリソース要求を計算できる。トラフィック評価システムはその後、多段階スイッチネットワークの容量と、トラフィックのネットワークリソース要求との比較に基づいて、トラフィックを評価することができる。
【００５７】
幾つかの例において、ネットワークリソース要求はリソース要求値から計算することができ、リソース要求値は、トラフィックを入力できる各入口スイッチの各入口スイッチ106と、トラフィックを出力できる各出口スイッチの各出口スイッチ110のアルゴリズムに従って計算することができる。これらの例において、トラフィック評価システム104は、多段階スイッチネットワーク102の容量と、各入口スイッチと出口スイッチのリソース要求値との比較に基づいてトラフィックを評価することができる。幾つかのさらに特定的な例おいて、トラフィック評価システム104は、各入口スイッチのリソース要求値を、入口スイッチへの1つ以上の異なるタイプのトラフィック入力のトラフィックタイプ要求値の合計として計算することができる。同様に、トラフィック評価システムは各出口スイッチのリソース要求値を、出口スイッチからの1つ以上の異なるタイプのトラフィック出力のトラフィックタイプ要求値の合計値として計算することができる。
【００５８】
図6から図10は、図5の多段階スイッチネットワーク500の例を拡張しており、さらに、トラフィック評価とアルゴリズムとを示しており、それにしたがってトラフィック評価システム104は、図1の多段階スイッチネットワーク102を通してルーティングされるトラフィックのネットワークリソース要求を計算することができる。図6に示すように、トラフィック評価システムは、多段階スイッチネットワークの入口スイッチ506を、各入口スイッチ（I0、I1、I2）の列を含む入口マトリクス602（I‐マトリクス）に割り当てることができる。同様に、トラフィック評価システムは、出口スイッチ510を、各出口スイッチ（E0、E1、E2）の列を含む出口マトリクス604（E‐マトリクス）に割り当てることができる。
【００５９】
I‐マトリクスの各列に対し入口スイッチ506が割り当てられているために、トラフィック評価システム104は、入口スイッチへの異なるタイプのトラフィック入力にアルゴリズムを適用して、それぞれ異なるタイプのトラフィックに関しトラフィックタイプ要求を計算することができる。これらのトラフィックタイプ要求は、I‐マトリクスの列で累積（合計）することができ、その合計は入口スイッチのリソース要求値を示す。トラフィック評価システムは同じ処理を、E‐マトリクスの各列の出口スイッチに対し行うことができ、これらのトラフィックタイプ要求の合計は出口スイッチのリソース要求値を示す。
【００６０】
トラフィック評価システム104は列I‐マトリクスとE‐マトリクスの入口スイッチと出口スイッチのリソース要求値を、多段階スイッチネットワーク500の容量と比較することができる。図6に示すように、多段階スイッチネットワークの容量は、多段階スイッチネットワークの中間スイッチ508の少なくとも1つの部分集合の数（SR）と、この部分集合の中間スイッチ1つ当たりのサブチャネルの数（f）の積で示すことができる。ここで、部分集合には全ての中間スイッチを含めてもよいし、中間スイッチのいくつかが重複や他のエラー訂正や緩和目的などの他の目的に割り当てられる場合においてなど、それより少ない数の中間スイッチを含めてもよい。多段階スイッチネットワークの容量は時々、I‐マトリクスとE‐マトリクスの列に対する列合計限界で示される。
【００６１】
I‐マトリクスとE‐マトリクスがこの列合計限界を満たす場合、トラフィックは実行可能であるとみなすことができ、そうでなければ、トラフィックはネットワーク容量を超えており、実行不可能であるとみなすことができる。実行可能なトラフィックは多段階スイッチネットワーク500を通してルーティングすることができる。しかしながら、実行不可能なトラフィック（または実行不可能なトラフィックを含むトラフィックルーティングプラン）は、トラフィックを入力する入口スイッチ506、トラフィックを出力する出口スイッチ510、および／またはトラフィックのタイプに対してなど、修正を要求することができる。修正されたトラフィック／トラフィックルーティングプランはその後評価され、その実行可能性を判定されるが、これはトラフィック／トラフィックルーティングプランが実行可能になるまで繰り返される。
【００６２】
上記のように、トラフィック評価システム104がそれによりトラフィックのネットワークリソース要求を計算することができるアルゴリズムは、トラフィックのタイプに特有であるが、多段階スイッチネットワーク102を通るトラフィックの特定のルートに一般化することができる。図7から図10は、一対一、一対多、多対一、および多対多トラフィックのアルゴリズムを示し、引き続き例となる多段階スイッチネットワーク500に関する。
【００６３】
図7は一対一のトラフィックのアルゴリズムの一例を示し、ここでもまた、1つの入力ポート／入口スイッチ506からのトラフィックがそれぞれの出力ポート／出口スイッチ510にルーティングされている。一対一のトラフィックがルーティングされる各入力ポート／入口スイッチについて、アルゴリズムはトラフィックタイプ要求値1を、I‐マトリクスの各列に加算することができる。また、一対一のトラフィックがルーティングされる各出力ポート／出口スイッチについて、アルゴリズムはトラフィックタイプ要求値1を、E‐マトリクスの各列に加算することができる。
【００６４】
図8は一対多トラフィックのアルゴリズムの例を示し、ここでもまた、1つの入力ポート／入口スイッチ506からのトラフィックが複数の出力ポート／出口スイッチ510にルーティングされている。前と同様に、一対多トラフィックがルーティングされる各出力ポート／出口スイッチについて、アルゴリズムはトラフィックタイプ要求値1をE‐マトリクスの各列に加算することができる。他方、一対多トラフィックがルーティングされる各入力ポート／入口スイッチについて、アルゴリズムはトラフィックタイプ要求値RFOを計算して、I‐マトリクスの各列に加算することができる。
【００６５】
値RFOは複数の異なる方法で計算することができ、幾つかの例では、RFOは入口スイッチ506でのネットワークリソース利用を多少偏重して、多段階スイッチネットワーク500を通してトラフィックをルーティングするように選択された（調整可能な）性能パラメータを含むことができる。RFOを計算する適切な方法の一例は以下の通りである。
【００６６】
【数１】
2019195216.tif 000003
【００６７】
上記数式において、αは性能パラメータを示し、
【００６８】
【数２】
2019195216.tif 000004
【００６９】
は天井関数を示し、|E|は、一対多トラフィックがルーティングされる出口スイッチ（E）のセットにおけるエレメントの数（すなわち、Eの濃度）を示す。幾つかの例において、性能パラメータαは0から1におよび（すなわち、α∈（0，1））、1の値は入口スイッチにおける最大ネットワーク利用を示し、0の値は入口スイッチにおける最小ネットワーク利用を示す。1つの特定の例において、α＝1を選択してもよい。
【００７０】
図9は多対一トラフィックのアルゴリズムの一例を示し、ここでもまた、複数の入力ポート／入口スイッチ506からのトラフィックが1つの出力ポート／出口スイッチ510へルーティングされている。ここで、アルゴリズムは、入力ポート／入口スイッチによって多対一トラフィック（T）のセットを分割でき（TiはスイッチIiのトラフィック）、iは入口スイッチのインデックスを示す（例えば、i＝1，2，3）。多対一トラフィックがルーティングされる各入力ポート／入口スイッチIiについて、その後アルゴリズムはトラフィックタイプ要求値
【００７１】
【数３】
2019195216.tif 000005
【００７２】
を計算し、I‐マトリクスの各列に加算することができる。この数式において、Pは単一のサブチャネルで結合することができるトラフィックのサブチャネルの数を限定するスイッチのハードウェア制約を示す（例えば、P＝4）。この点に関して、多段階スイッチネットワーク500の各段は、デジタル対称マトリクス（2次元クロスバー）として考えることができ、その出力サブチャネルはそれぞれP入力を備えた加算器として考えることができる。
【００７３】
多対一トラフィックがルーティングされる各出力ポート／出口スイッチ510について、アルゴリズムはトラフィックタイプ要求値RFIを計算し、E−マトリクスの各列に加算することができる。値RFIは複数の異なる方法で計算することができ、幾つかの例において、RFIは、中間スイッチ508におけるネットワークリソース利用を多少偏重して、多段階スイッチネットワーク500を通してトラフィックをルーティングするように選択した（調整可能な）性能パラメータを含むことができる。RFIを計算するのに適した方法の一例は以下の通りである。
【００７４】
【数４】
2019195216.tif 000006
【００７５】
上記の数式において、βは性能パラメータを示し、｜Tk|はr個の入力ポート／入口スイッチ506のいずれかからルーティングされた一対多トラフィック（T）のセットにおけるエレメント数（すなわち、Tkの濃度）を示す。幾つかの例において、性能パラメータβは、0から1におよび（すなわち、β∈（0，1））、1の値は中間スイッチ508における最小のネットワーク利用を示し、0の値は中間スイッチにおける最大ネットワーク利用を示す。1つの特定の例において、β＝0.75を選択することができる。
【００７６】
図10は多対多トラフィックのアルゴリズムの一例を示し、ここでもまた、複数の入力ポート／入口スイッチ506からのトラフィックが複数の出力ポート／出口スイッチ510にルーティングされる。上記と同様に、アルゴリズムは、入力ポート／入口スイッチによって多対一トラフィック（T）のセットを分割することができる（TiはIiにおけるトラフィック）。多対多トラフィックがルーティングされる各入力ポート／入口スイッチIiについて、その後、アルゴリズムはトラフィックタイプ要求値
【００７７】
【数５】
2019195216.tif 000007
【００７８】
を計算し、I‐マトリクスの各列に加算することができる。そして、多対一トラフィックについての上記と同じように、多対多トラフィックがルーティングされる各出力ポート／
出口スイッチについて、アルゴリズムはトラフィックタイプ要求値RFIを計算し、E‐マトリクスの各列に加算することができる。
【００７９】
上記のように、トラフィック評価システム104は、一対一、一対多、多対一、および／または多対多などの、複数の異なるタイプのいずれか1つ以上の別個のトラフィックを含むトラフィックを評価することができる。トラフィックは、多段階スイッチネットワーク102を通してルーティングされるトラフィックでもよいし、多段階スイッチネットワークの既存のトラフィックでもよいし、多段階スイッチネットワークを通してルーティングされるトラフィックと多段階スイッチネットワークの既存のトラフィックの組み合わせでもよい。
【００８０】
図11はトラフィック評価システム1100の一例を示し、幾つかの例において、図1のトラフィック評価システム104に対応するものでもよい。図示される例において、トラフィック評価システムは、図5の多段階スイッチネットワーク500などの多段階スイッチネットワークを通してルーティングされるトラフィックを評価するように構成することができる。図示したように、トラフィック評価システムは、多段階スイッチネットワーク102などの多段階スイッチネットワークを通してルーティングされる新しいトラフィック1102の指示を受信するように構成することができる。ここで、この指示は、複数の入力ポート／入口スイッチ506から1つの出力ポート／出口スイッチ510にルーティングされる特定のタイプの別個のトラフィックによって提供される。
【００８１】
トラフィック評価システム1100はまた、多段階スイッチネットワーク500の既存のトラフィックの指示を受信することができる。幾つかの例において、既存のトラフィックの指示は、新しいトラフィックの指示と同様に提供される。さらに、またはその代わりに、全部ではなくても少なくとも幾つかの既存のトラフィックの指示を、既存のトラフィックのトラフィックタイプ要求値が累積されたI‐マトリクスおよびE‐マトリクス1104によって提供することができる。
【００８２】
幾つかの例において、多段階スイッチネットワーク500を通してルーティングされる新しいトラフィック1102を評価するのが望ましい場合があるが、さらに、またはその代わりに、多段階スイッチネットワークから取り除くことができる既存のトラフィック（古いトラフィック1106）のいずれかを評価するのが望ましい場合がある。これらの場合、トラフィック評価システム1100は新しいトラフィックの指示に加えて、またはそれに代わって、この古いトラフィックの指示を受信することができ、古いトラフィックの指示は新しいトラフィックの指示と同様に提供される。
【００８３】
トラフィック評価システム1100は、新しいトラフィック1102を加え、および／または古いトラフィック1106を取り除いた後、上述のアルゴリズムを実行して、トラフィックタイプ要求値と、したがってネットワークのトラフィックのネットワークリソース要求とを計算することができ、途中でI‐マトリクスとE‐マトリクス1104を更新することができる。トラフィックの少なくとも幾つかのタイプについて、アルゴリズムは（調整可能な）性能パラメータ（例えば、α、β）を含むことができる。トラフィック評価システムは、これらの性能パラメータの値で事前構成することができ、または幾つかの例では、トラフィック評価システムは性能パラメータ1108の値を備えることができる。
【００８４】
上記と同様の方法で、トラフィック評価システム1100は入口スイッチ506と出口スイッチ510のリソース要求値を、多段階スイッチネットワークの容量と比較することができる。再び、この容量は、I‐マトリクスとE‐マトリクスの列の列合計限界によって示すことができる。I‐マトリクスとE‐マトリクスがこの列合計限界を満たす場合、トラフィック評価システムはトラフィックまたはそのトラフィックルーティングプランを実行可能とみ
なすことができ、そうでなければ、トラフィック評価システムは、トラフィック／トラフィックルーティングプランを、ネットワーク容量を超えているので実行不可能であるとみなすことができる。トラフィック評価システムはその後、トラフィック／トラフィックルーティングプランの実行可能性の指示を出力することができる。この指示は一般に、トラフィック／トラフィックルーティングプランの実行可能性（または実行不可能性）、または多段階スイッチネットワーク500の容量に近づいている多分実行可能なトラフィック／トラフィックルーティングプランを示すことができる。幾つかの例において、この指示は、入口スイッチ506と出口スイッチ510のリソース要求値などの追加情報を提供することができ、多段階スイッチネットワークにおける過負荷状態のスイッチやボトルネックを示すことができる。この追加情報は、実行不可能なトラフィック／トラフィックルーティングプランの場合や、それが容量に近づいている場合に、その修正のための基礎として用いることができる。
【００８５】
図12は本発明の幾つかの実施形態に従う、多段階スイッチネットワークを通るトラフィックを評価する方法1200の各種動作を示す。ブロック1202に示すように、また図1および図4を参照して、この方法には、トラフィックのタイプに応じて、1つ以上の入力ポート402から1つ以上の出力ポート404にトラフィックをルーティングするように構成した多段階スイッチネットワーク102を通してルーティングされるトラフィックの指示を受信することが含まれる。この方法には、ブロック1204に示すように、入力ポートと、出力ポートと、トラフィックタイプと、さらに、幾つかの例においては、既存のトラフィックリソースに基づいて、トラフィックのネットワークリソース要求を計算することが含まれる。ここで、ネットワークリソース要求は、トラフィックのタイプに特有であるが、多段階スイッチネットワークを通るトラフィックの特定のルートに一般化されるアルゴリズムによって計算することができる。またこの方法には、ブロック1206に示すように、多段階スイッチネットワークの容量と、トラフィックのネットワークリソース要求との比較に基づいて、トラフィックを評価することが含まれる。
【００８６】
本発明の実施形態によると、トラフィック評価システム104、1100は種々の手段によって実現することができ、ハードウェア単独や、またはハードウェアがコンピュータ可読記憶媒体からの1つ以上のコンピュータプログラムの指示に従うことが含まれる。幾つかの例において、ここに図示し記載した評価システムとして機能するか、該評価システムを実現するように構成された1つ以上の装置を設けることができる。1つ以上の装置を含む例において、各装置は、有線または無線ネットワークなどを介して直接にまたは間接的になど、複数の異なる方法で互いに接続されるかまたは通信することができる。
【００８７】
一般に、本発明の実施形態の装置は、1つ以上の固定されたまたは携帯用の電子機器を備えるか、含むか、実現することができる。適した電子機器の例には、スマートフォン、タブレットコンピュータ、ラップトップコンピュータ、デスクトップコンピュータ、ワークステーションコンピュータ、サーバーコンピュータなどが含まれる。図13は本発明の幾つかの実施形態に従うトラフィック評価システム104、1100を実現するための装置1300を示す。この装置は、例えば、メモリ1304に接続するプロセッサ1302などの複数の構成要素のそれぞれを1つ以上含むことができる。
【００８８】
プロセッサ1302は一般に、例えば、データ、コンピュータプログラム、および／または他の適切な電子情報などの情報を処理することができる任意のコンピュータハードウェアである。プロセッサは電子回路の集合からなり、それらのいくつかは集積回路または複数の相互接続された集積回路としてパッケージ化することができる（時に「チップ」と称するのがより一般的な集積回路）。プロセッサはコンピュータプログラムを実行するように構成することができ、該プログラムはプロセッサに搭載して記憶するか、（同じ装置または別の装置の）メモリ1304に記憶することができる。
【００８９】
プロセッサ1302は、特定の実施態様によって、複数のプロセッサであったり、マルチプロセッサコアであったり、その他の種類のプロセッサであったりする。さらに、プロセッサは、単一のチップに主プロセッサが1つ以上の二次プロセッサと共に存在する、複数の異種プロセッサシステムを用いて実現することができる。別の実施形態として、プロセッサは、同じ種類の複数のプロセッサを含む対称マルチプロセッサシステムであってもよい。さらに別の例では、プロセッサは、1つ以上の特定用途向け集積回路（ASIC）や、フィールド・プログラマブル・ゲートアレイ（FPGA）などとして実現されるか、またはそれらを含むことができる。このように、プロセッサは、コンピュータプログラムを実行して1つ以上の機能を果たすことができるが、種々の実施形態のプロセッサは、コンピュータプログラムを用いずに1つ以上の機能を果たすことができる。
【００９０】
メモリ1304は一般に、例えば、データ、コンピュータプログラム、および／またはその他の適切な情報などの情報を、一時的におよび／または永久的に記憶することができる任意のコンピュータハードウェアである。メモリは揮発性および／または不揮発性メモリを含むことができ、固定してもよいし取り外し可能でもよい。適したメモリの例には、ランダムアクセスメモリ（RAM）、読み出し専用メモリ（ROM）、ハードドライブ、フラッシュメモリ、サムドライブ、取り外し可能コンピュータディスケット、光ディスク、磁気テープ、または上記の何らかの組み合わせが含まれる。光ディスクには、コンパクトディスク−読み出し専用メモリ（CD‐ROM）、コンパクトディスク−読み取り／書き込み（CD‐R／W）、DVDなどが含まれる。種々の例において、メモリはコンピュータ可読記憶媒体と呼ぶことがあり、情報を記憶することができる非一時的な装置として、ある場所から別の場所へ情報を送ることができる電子一時的信号などのコンピュータ可読伝送媒体と区別できる。ここで説明するようなコンピュータ可読媒体は一般に、コンピュータ可読記憶媒体やコンピュータ可読伝送媒体を指す。
【００９１】
メモリ1304に加えて、プロセッサ1302は1つ以上のインターフェースにも接続されて、情報を表示、送信、および／または受信できる。インターフェースは少なくとも1つの通信インターフェース1306および／または1つ以上のユーザーインターフェースを含むことができる。通信インターフェースは、他の装置やネットワークなどとの間などで、情報を送信および／または受信するように構成することができる。通信インターフェースは、物理的（有線）および／または無線通信リンクによって情報を送信および／または受信するように構成することができる。適切な通信インターフェースの例には、ネットワークインターフェースコントローラー（NIC）や無線NIC（WNIC）などが含まれる。
【００９２】
ユーザーインターフェースは、ディスプレイ1308および／または1つ以上のユーザー入力インターフェース1310を含むことができる。ディスプレイはユーザーに情報を提示または表示するように構成することができ、その適した例には、液晶ディスプレイ（LCD）、発光ダイオードディスプレイ（LED）、プラズマ・ディスプレイ・パネル（PDP）などが含まれる。ユーザーインターフェースは有線でも無線でもよく、ユーザーからの情報を装置1300に受信するよう構成して、処理、記憶、および／または表示などすることができる。ユーザー入力インターフェースの適切な例には、マイク、画像または音声取り込み装置、キーボードまたはキーパッド、ジョイスティック、（タッチスクリーンとは別個の、またはタッチスクリーンに組み込まれた）タッチセンシティブ面、バイオメトリックセンサなどが含まれる。ユーザーインターフェースはさらに、プリンタやスキャナなどの周辺装置と通信するための1つ以上のインターフェースを含むことができる。
【００９３】
上記のように、プログラムコード命令をメモリに記憶し、プロセッサで実行することで、本明細書に記載のシステムとサブシステムとそれらの各要素の機能を実現することができる。当然のことながら、任意の適切なプログラムコード命令を、コンピュータ可読記憶
媒体からコンピュータや他のプログラム可能な装置にロードして特定のマシンを作ることができ、その結果該特定のマシンは本明細書に記載の機能を実行する手段となる。これらのプログラムコード命令はまたコンピュータ可読記憶媒体に記憶することができ、コンピュータやプロセッサや他のプログラム可能な装置に、特定の方法で機能するように指示することによって、特定のマシンまたは特定の製品を生み出すことができる。コンピュータ可読記憶媒体に記憶された命令により製品を作ることができ、この製品は本明細書に記載の機能を実行する手段となる。プログラムコード命令をコンピュータ可読記憶媒体から取得してコンピュータやプロセッサや他のプログラム可能な装置にロードして、コンピュータやプロセッサや他のプログラム可能な装置を構成し、コンピュータやプロセッサや他のプログラム可能な装置においてまたはそれによって行われる動作を実行することができる。
【００９４】
プログラムコード命令の取得、ロード、および実行は、1つの命令が一度に取得、ロード、実行されるように、逐次行うことができる。幾つかの実施形態において、取得、ロード、および／または実行を、複数の命令が一緒に取得、ロード、および／または実行されるように、並行して行うことができる。プログラムコード命令の実行により、コンピュータやプロセッサや他のプログラム可能な装置によって実行される命令により、本明細書に記載の機能を実現するための動作が提供されるように、コンピュータ実現プロセスを生成することができる。
【００９５】
プロセッサにより命令を実行し、コンピュータ可読記憶媒体に命令を記憶することで、特定の機能を実行するための動作の組み合わせがサポートされる。また当然のことながら、1つ以上の機能や、機能の組み合わせは、特定の機能を実行する特定目的ハードウェアによるコンピュータシステムおよび／またはプロセッサ、または特定目的ハードウェアとプログラムコード命令の組み合わせによって実現できる。
【００９６】
本明細書に記載の本発明の様々な変更や他の実施態様は、当該説明と関連図面で提示した教示を利用できる、本発明が関連する分野の当業者であれば思い浮かぶであろう。したがって、本発明は開示した特定の実施態様に限定されるものではなく、変更や他の実施態様が添付の請求項の範囲に含まれるものであることを理解されたい。さらに、当該説明と関連図面では、要素および／または機能の特定の組み合わせ例との関連で実施形態について説明しているが、要素および／または機能の異なる組み合わせが、添付の請求項の範囲から逸脱することなく他の実施態様によって提供されることを理解すべきである。この点に関して、例えば、上記に明確に説明したものとは異なる要素および／または機能の異なる組み合わせもまた、添付の請求項のいずれかに記載されているものと考えられる。本明細書において特定の用語を使用しているが、総称的説明的意味で用いており、限定するためではない。
【符号の説明】
【００９７】
100  スイッチ分析システム
102、200、500  多段階スイッチネットワーク
104、1100  トラフィック評価システム
106、206、506  入口スイッチ
108、208、508  中間スイッチ
110、210、510  出口スイッチ
112、114、212、214  相互接続
206a、208a、210a  スイッチ入力
206b、208b、210b  スイッチ出力
216  ユーザー入力
218  アルゴリズム領域
220  ユーザー出力
222  出力
224  入力
226  複数のサブチャネル
402  入力ポート
404  出力ポート
602  入口マトリクス
604  出口マトリクス
1102  新しいトラフィック
1104  I‐マトリクスおよびE‐マトリクス
1106  古いトラフィック
1108  性能パラメータ
1200  方法
1202、1204、1206  ブロック
1300  装置
1302  プロセッサ
1304  メモリ
1306  通信インターフェース
1308  ディスプレイ
1310  ユーザー入力インターフェース
A1、A2  データ
E0、E1、E2  出力ポート／出口スイッチ
I0、I1、I2  入口ポート／入口スイッチ
【図１】
2019195216.tif 000008
【図２】
2019195216.tif 000009
【図３】
2019195216.tif 000010
【図４】
2019195216.tif 000011
【図５】
2019195216.tif 000012
【図６】
2019195216.tif 000013
【図７】
2019195216.tif 000014
【図８】
2019195216.tif 000015
【図９】
2019195216.tif 000016
【図１０】
2019195216.tif 000017
【図１１】
2019195216.tif 000018
【図１２】
2019195216.tif 000019
【図１３】
2019195216.tif 000020
【外国語明細書】
2019195216000001.pdf