(57)【要約】  システムおよび方法は、ネットワーク環境において別個のサブネット間のトラフィックをルーティングすることができる。InfiniBand（ＩＢ）サブネットなどの別個のサブネットを接続するルータは、当該ルータが担う１つ以上のパケットのルーティング先であるデスティネーションのリストを受信することができる。さらに、ルータは、１つ以上のパケットをルーティングするためにルータのいずれの下流側出力ポートを使用することができるかについての情報を、少なくとも１つのサブネットにおける１つ以上のスイッチから取得し、取得された情報に基づいてルーティングテーブルを構築することができる。
2015520995.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク環境において別個のサブネット間のトラフィックをルーティングするための方法であって、
ルータにおいて、前記ルータが担う１つ以上のパケットのルーティング先であるデスティネーションのリストを受信することを含み、前記ルータは、前記ネットワーク環境において少なくとも１つのサブネットに接続しており、さらに、
前記１つ以上のパケットをルーティングするために前記ルータのいずれの下流側出力ポートを使用することができるかについての情報を、前記少なくとも１つのサブネットにおける１つ以上のスイッチから取得することと、
前記取得された情報に基づいてルーティングテーブルを構築することとを含む、方法。
【請求項２】
前記少なくとも１つのサブネットに接続されるすべての利用可能なルータ間でラウンドロビンパス分散を行なうことをさらに含む、請求項１に記載の方法。
【請求項３】
各ルータに接続されているスイッチに照会して、いずれのスイッチが特定のデスティネーションへの主要なパスとして作用することができるかについて学習することをさらに含む、請求項１または２に記載の方法。
【請求項４】
前記取得された情報に基づいて、最大性能のために前記ルータのいずれの下流側出力ポートを使用することができるかを判定することをさらに含む、先行する請求項のいずれか１項に係る方法。
【請求項５】
１つ以上のデスティネーショングローバル識別子（ＧＩＤ）と１つ以上のルータポートとの間のポートマッピングをサブネットマネージャから受信することをさらに含む、先行する請求項のいずれか１項に係る方法。
【請求項６】
１つ以上の付加的なルータを用いて、ネットワーク環境における１つ以上の近隣のサブネットに前記少なくとも１つのサブネットを接続することをさらに含む、先行する請求項のいずれか１項に係る方法。
【請求項７】
接続されるサブネットが異なるトポロジーであることを可能にすることをさらに含む、先行する請求項のいずれか１項に係る方法。
【請求項８】
接続される各サブネットが多段ファットツリーにおけるブランチであることを可能にすることをさらに含む、先行する請求項のいずれか１項に係る方法。
【請求項９】
前記少なくとも１つのサブネットがファットツリートポロジーで構成されることを可能にすることをさらに含む、先行する請求項のいずれか１項に係る方法。
【請求項１０】
前記少なくとも１つのサブネットをルーティングするためにファットツリールーティングアルゴリズムを使用することをさらに含む、先行する請求項のいずれか１項に係る方法。
【請求項１１】
１つ以上のマイクロプロセッサ上で動作し、先行する請求項のいずれか１項に係る方法のステップをすべて行なうためのプログラム命令を備えるコンピュータプログラム。
【請求項１２】
機械読取可能な媒体上に設けられる、請求項１１に記載のコンピュータプログラムを備えるコンピュータプログラム。
【請求項１３】
ネットワーク環境において別個のサブネット間のトラフィックをルーティングするためのシステムであって、
１つ以上のマイクロプロセッサと、
前記１つ以上のマイクロプロセッサ上で実行するルータとを備え、前記ルータは、
前記ルータが担う１つ以上のパケットのルーティング先であるデスティネーションのリストを受信するように動作し、前記ルータは、前記ネットワーク環境において少なくとも１つのサブネットに接続しており、さらに、
前記１つ以上のパケットをルーティングするために前記ルータのいずれの下流側出力ポートを使用することができるかについての情報を、前記少なくとも１つのサブネットにおける１つ以上のスイッチから取得ように動作し、
前記取得された情報に基づいてルーティングテーブルを構築するように動作する、システム。
【請求項１４】
ラウンドロビンパス分散は、前記少なくとも１つのサブネットに接続されたすべての利用可能なルータ間で行なわれる、請求項１３に記載のシステム。
【請求項１５】
前記ルータは、前記ルータに接続されているスイッチに照会して、いずれのスイッチが特定のデスティネーションへの主要なパスとして作用することができるかについて学習するように動作する、請求項１３または１４に記載のシステム。
【請求項１６】
前記ルータは、前記取得された情報に基づいて、最大性能のために前記ルータのいずれの下流側出力ポートを使用することができるかを判定するように動作する、請求項１３から１５のいずれか１項に記載のシステム。
【請求項１７】
前記ルータは、前記ルータによって接続されたサブネットを異なるネットワークトポロジーで構成することを可能にするように動作する、請求項１３から１６のいずれか１項に記載のシステム。
【請求項１８】
前記少なくとも１つのサブネットは、１つ以上の付加的なルータを用いてネットワーク環境における１つ以上の近隣のサブネットに接続される、請求項１３から１７のいずれか１項に記載のシステム。
【請求項１９】
接続されるサブネットは、異なるトポロジーであることができる、請求項１３から１８のいずれか１項に記載のシステム。
【請求項２０】
接続される各サブネットは、多段ファットツリーにおけるブランチである、請求項１３から１９のいずれか１項に記載のシステム。
【請求項２１】
前記少なくとも１つのサブネットをファットツリートポロジーで構成させることができ、前記少なくとも１つのサブネットをルーティングするためにファットツリールーティングアルゴリズムを使用することができる、請求項１１に記載のシステム。
【請求項２２】
実行されると以下のステップをシステムに行なわせる命令がその上に格納されている非一時的な機械読取可能な記録媒体であって、以下のステップは、
前記ルータが担う１つ以上のパケットのルーティング先であるデスティネーションのリストを受信することを含み、前記ルータは、前記ネットワーク環境において少なくとも１つのサブネットに接続しており、さらに、
前記１つ以上のパケットをルーティングするために前記ルータのいずれの下流側出力ポートを使用することができるかについての情報を、前記少なくとも１つのサブネットにおける１つ以上のスイッチから取得することと、
前記取得された情報に基づいてルーティングテーブルを構築することとを含む、非一時的な機械読取可能な記録媒体。
【請求項２３】
請求項１から１０のいずれか１項に記載の方法をコンピュータに実行させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
著作権表示
この特許文献の開示の一部は著作権保護の対象となる内容を含む。著作権者は、特許商標庁の特許ファイルまたは記録に現れた際には特許文献または特許開示のいずれによるファクシミリ再現に対しても異議を申立てないが、それ以外のすべてのいかなる著作権も留保する。
【０００２】
発明の分野
本発明は概してコンピュータシステムに関し、特にミドルウェアマシン環境に関する。
【背景技術】
【０００３】
背景
より大きなクラウドコンピューティングアーキテクチャが導入されるにつれ、従来のネットワークおよび記憶装置に関連付けられる性能および管理上の障害が重要な問題となっている。InfiniBand（ＩＢ）技術は、クラウドコンピューティングファブリックの基盤としてますます展開されている。これは、発明の実施形態が対処するように意図される概略的な分野である。
【発明の概要】
【課題を解決するための手段】
【０００４】
概要
別個のInfiniBand（ＩＢ）サブネット間のトラフィックをルーティングすることができるシステムおよび方法をここに記載する。InfiniBand（ＩＢ）サブネットなどの別個のサブネットを接続するルータは、当該ルータが担う１つ以上のパケットのルーティング先であるデスティネーションのリストを受信することができる。さらに、ルータは、１つ以上のパケットをルーティングするためにルータのいずれの下流側出力ポートを使用することができるかについての情報を、少なくとも１つのサブネットにおける１つ以上のスイッチから取得し、取得された情報に基づいてルーティングテーブルを構築することができる。
【０００５】
ネットワーク環境において別個のサブネット間のトラフィックをルーティングするためのシステムもここに説明される。システムは、ルータにおいて、当該ルータが担う１つ以上のパケットのルーティング先であるデスティネーションのリストを受信するための手段を備え、ルータは、ネットワーク環境において少なくとも１つのサブネットに接続している。システムは、１つ以上のパケットをルーティングするためにルータのいずれの下流側出力ポートを使用することができるかについての情報を、少なくとも１つのサブネットにおける１つ以上のスイッチから取得するための手段をさらに備える。システムは、取得された情報に基づいてルーティングテーブルを構築するための手段をさらに備える。
【０００６】
さらに、ネットワーク環境において別個のサブネット間のトラフィックをルーティングするためのシステムがここに説明される。システムは、自身が担う１つ以上のパケットのルーティング先であるデスティネーションのリストを受信するように構成されたルータを備え、ルータは、ネットワーク環境において少なくとも１つのサブネットに接続している。システムは、１つ以上のパケットをルーティングするためにルータのいずれの下流側出力ポートを使用することができるかについての情報を、少なくとも１つのサブネットにおける１つ以上のスイッチから取得し、取得された情報に基づいてルーティングテーブルを構築するようにも構成される。
【図面の簡単な説明】
【０００７】
【図１】発明の実施形態に従う、ネットワーク環境において別個のInfiniBand（ＩＢ）サブネット間のトラフィックをルーティングする例示を示す図である。
【図２】発明の実施形態に従う、ネットワーク環境においてルータ上のパケット転送をサポートする例示を示す図である。
【図３】発明の実施形態に従う、ネットワーク環境において異なるデスティネーションのための入口ルータポートを選択する例示を示す図である。
【図４】発明の実施形態に従う、ネットワーク環境におけるルータにおいて受信パケットのための出口ルータポートを選択する例示を示す図である。
【図５】発明の実施形態に従う、ネットワーク環境におけるルータにおいてサブネット間ソースルーティング（ＩＳＳＲ）アルゴリズムをサポートするための典型的なフローチャートを例示する図である。
【図６】発明の実施形態に従う、ネットワーク環境におけるルータにおいてサブネット間ファットツリールーティング（ＩＳＦＲ）アルゴリズムをサポートする例示を示す図である。
【図７】発明の実施形態に従う、異なるトポロジーを有するネットワーク環境におけるルーティングを例示する図である。
【図８】発明の実施形態に従う、異なるトポロジーを有するネットワーク環境におけるルーティングを例示する図である。
【図９】発明の実施形態に従う、異なるトポロジーを有するネットワーク環境におけるルーティングを例示する図である。
【図１０】発明の実施形態に従う、ネットワーク環境におけるルータにおいてサブネット間ファットツリールーティング（ＩＳＦＲ）アルゴリズムをサポートするための典型的なフローチャートを例示する図である。
【図１１】発明の実施形態に従う特徴を示す機能ブロック図を例示する図である。
【発明を実施するための形態】
【０００８】
詳細な説明
発明は、限定の目的ではなく一例として添付の図面の図に図示され、図中同じ参照番号は同様の要素を示す。この開示での「ある」または「１つの」または「いくつかの」実施形態の参照は必ずしも同じ実施形態に対するものではなく、そのような参照は少なくとも１つを意味することに留意すべきである。
【０００９】
以下のような発明の説明は、InfiniBand（ＩＢ）ネットワークを高性能ネットワークの例として用いる。当業者には、他の種類の高性能ネットワークを限定なく用いることができることが明らかであろう。また、以下のような発明の説明は、ファットツリーをネットワークトポロジーモデルの例として用いる。当業者には、他の種類のネットワークトポロジーモデルを限定なく用いることができることが明らかであろう。
【００１０】
別個のネットワーク間でのトラフィックのルーティングをサポートすることができるシステムおよび方法をここに説明する。
【００１１】
InfiniBand（ＩＢ）アーキテクチャ
ＩＢアーキテクチャは、直列の二地点間全二重技術である。ＩＢクラスタのサイズおよび複雑性が増大するにつれて、サブネットと称することができる扱いやすいセクションにネットワークをセグメント化することができる。ＩＢサブネットは、スイッチおよび二地点間リンクを用いて相互接続された１組のホストを含むことができる。ＩＢサブネットは、少なくとも１つのサブネットマネージャ（ＳＭ）を含むこともでき、サブネットマネージャは、サブネットにおけるすべてのスイッチ、ルータおよびホストチャネルアダプタ（ＨＣＡ）の構成を含む、ネットワークの初期化および立上げを担う。
【００１２】
ＩＢは、リモートダイレクトメモリアクセス（ＲＤＭＡ）および従来の送信／受信セマンティクスの両方を提供するために、多数の伝送サービスの組をサポートする。使用される伝送サービスとは別個に、ＩＢ  ＨＣＡはキューペア（ＱＰ）を用いて通信する。ＱＰは通信セットアップ中に作成され、提供されるＱＰ番号、ＨＣＡポート、デスティネーションＬＩＤ、キューサイズ、および伝送サービスなどの１組の初期属性を有することができる。ＨＣＡは多くのＱＰを処理することができ、各ＱＰは、送信キュー（ＳＱ）および受信キュー（ＲＱ）などの１組のキューで構成され、通信に参加する各エンドノードにおいて、１つのそのようなペアが存在する。送信キューは、リモートノードに転送される作業要求を保持し、一方受信キューは、リモートノードから受信したデータで何を行うべきかについての情報を保持する。ＱＰに加えて、各ＨＣＡは１組の送信キューおよび受信キューと関連付けられた１つ以上の完了キュー（ＣＱ）を有する。ＣＱは、送信および受信キューに書込まれた作業要求についての完了通知を保持する。通信の複雑性がユーザーに非公開であっても、ＱＰ状態情報がＨＣＡに保持される。
【００１３】
別個のInfiniBand（ＩＢ）サブネット間のトラフィックのルーティング
図１は、発明の実施形態に従う、ネットワーク環境において別個のInfiniBand（ＩＢ）サブネット間のトラフィックをルーティングする実例を示す。図１に示されるように、ネットワーク環境１００は、InfiniBandアーキテクチャ（ＩＢＡ）に基づくことができ、２層トポロジー分割をサポートする。
【００１４】
ＩＢネットワークの下位レイヤ、すなわちＩＢファブリック１００は、サブネット、たとえばサブネット１０１−１０４と称することができ、サブネットの各々は、スイッチおよび二地点間リンクを用いて相互接続された１組のホストを含む。より高いレベルでは、ＩＢファブリック１００中の１つ以上のサブネット１０１−１０４をルータ、たとえばルータ１０５−１０６を用いて相互接続することができる。さらに、各サブネット１０１−１０４は、ポートのみを構成するそれ自身のサブネットマネージャ（ＳＭ）をローカルサブネット上で実行することができ、ルータ１０５−１０６は、サブネットマネージャ（ＳＭ）に対して不透明である。
【００１５】
サブネット１０１−１０４の各々中のホストおよびスイッチは、指定されたローカル識別子（ＬＩＤ）を用いてアドレス指定することができる。大きな設備のサイズは、利用可能なローカル識別子（ＬＩＤ）の数によって限定され得る。たとえば、一つのサブネットは４９１５１のユニキャストＬＩＤに限定され得る。ＩＢアドレス空間を拡張する１つの手法は、ＬＩＤアドレス指定空間を３２ビットに拡張することであり、この手法がより古いハードウェアとの後方互換性がない場合があるため、その有用性は限定される可能性がある。
【００１６】
発明の実施形態によれば、ＩＢルータ１０５−１０６は、ＩＢファブリック１００中のアドレス空間スケーラビリティを提供することができる。図１に示されるように、より多くのエンドポートが望ましい場合、１つ以上のＩＢルータ１０５−１０６を用いて複数のサブネット１０１−１０４を互いに組合せることができる。サブネット１０１−１０４の各々は、ローカル識別子（ＬＩＤ）アドレス空間１１１−１１４を使用することができる。ＬＩＤアドレスは各ＬＩＤアドレス空間１１１−１１４内にローカルな可視性を有することから、ルータ１０５−１０６によって接続されている異なるサブネット１０１−１０４においてＬＩＤアドレスを再使用することができる。したがって、アドレス空間スケーラビリティをＩＢファブリック１００に提供することができ、この手法は、無限のアドレス指定空間を理論的にもたらすことができる。
【００１７】
さらに、大きく複雑なネットワーク１００を複数のサブネット１０１−１０４にセグメント化することにより、システムはファブリック管理コンテナを提供することができる。ファブリック管理コンテナは、１）フォールト分離、２）より高いセキュリティ、および３）サブネット内ルーティングフレキシビリティを提供する際に有益となり得る。
【００１８】
まず、大きなネットワーク１００をいくつかのより小さなサブネット１０１−１０４に分割することにより、フォールトまたはトポロジーの変化を一つのサブネットに含めることができ、サブネットリコンフィギュレーションは、ルータ１０５−１０６を介して他のサブネットに通過しない場合がある。これにより、リコンフィギュレーション時間が短くなり、フォールトのインパクトが限定される。
【００１９】
第２に、セキュリティの観点から、ルータ１０５−１０６を用いて大きなファブリック１００をサブネット１０１−１０４にセグメント化することにより、大部分の攻撃の範囲を攻撃されたサブネットに限定する。
【００２０】
第３に、ルーティングの観点から、ファブリック管理格納は、よりフレキシブルなルーティングスキームをサポートする際に有益となることができ、２つ以上の規則的なトポロジーを含むハイブリッドファブリックの場合には特に有利となることができる。
【００２１】
たとえば、ハイブリッドファブリック１００は、メッシュで相互接続されたファットツリー部またはトーラス部（またはいずれかの他の規則的なトポロジー）を含んでもよい。サブネット内ルーティング（intra-subnet routing）アルゴリズムはサブネットスコープのみを有するため、ハイブリッドファブリック１００の異なる部分を別々にルーティングする簡単な方法がない場合がある。また、ハイブリッドトポロジーに最適な性能を提供することができるＩＢのための汎用アグノスティックルーティングトポロジーはない。
【００２２】
発明の実施形態によれば、ハイブリッドトポロジーを、より小さな規則的なサブネット１０１−１０４に分割することができ、その各々を、特定のサブネットに最適化される異なるルーティングアルゴリズムを用いてルーティングすることができる。たとえば、ファットツリールーティングアルゴリズムはファットツリー部をルーティングすることができ、次元順ルーティングは、トポロジーのメッシュ部をルーティングすることができる。
【００２３】
さらに、スーパーサブネットマネージャを用いてローカルサブネットマネージャ間の調整を行なうことができ、最終デスティネーションが別のサブネットの後ろに位置するより不規則なネットワークの場合（たとえば、少なくとも２つのルータホップが必要とされる）、トランジットサブネットを通るパスを確立することができる。
【００２４】
したがって、ＩＢサブネット間のルーティングを用いることによって、システムは、ＩＢネットワークにおけるアドレス空間スケーラビリティおよびファブリック管理コンテナをもたらすことができる。
【００２５】
ネイティブなInfiniBand（ＩＢ）ルータ
図２は、発明の実施形態に従う、ネットワーク環境においてルータ上のパケット転送をサポートする例示を示す。図２に示されるように、ネットワーク環境２００は、ルータ２１０を用いて相互接続される複数のサブネット、たとえばＩＢサブネットＡ−Ｂ  ２０１−２０２を含むことができる。さらに、ＩＢサブネットＡ  ２０１は、ホストチャネルアダプタ（ＨＣＡ）２１３に関連付けられるエンドノードＸ  ２０３に接続し、ＩＢサブネットＢ  ２０２は、ホストチャネルアダプタ（ＨＣＡ）２１４に関連付けられるエンドノードＹ  ２０４に接続する。
【００２６】
発明の実施形態によれば、ＩＢルータ２１０は、ＩＢアドレス指定ヒエラルキーのレイヤ３で動作することができる。さらに、ＬＩＤに加えて、各ＩＢ装置は、ＧＩＤ、ＩＢレイヤ３アドレスを形成するために使用することができる６４ビットのグローバルユニーク識別子（ＧＵＩＤ）も有し得る。たとえば、６４ビットサブネットＩＤを６４ビットＧＵＩＤと連結してＩＰｖ６のような１２８ビットのアドレスを形成することによってＧＩＤを作成することができる。また、ＧＵＩＤという用語は、ポートＧＵＩＤ、つまりＩＢファブリック中のあらゆるポートに割当てられたＧＵＩＤを指すのに使用してもよく、ＧＵＩＤは、不揮発性メモリに焼きつけることができる。
【００２７】
図２に示されるように、エンドノード、たとえばエンドノードＸ  ２０３は、ルータ２１０を介して、別のエンドノード、たとえばエンドノードＹ  ２０４にパケットを送信することができる。アドレス解決メカニズムは、ローカルルータ２１０をエンドノードＸ−Ｙ  ２０３−２０４に対して可視化することができる。
【００２８】
たとえば、ルータ２１０で受信されたパケットは、ローカルルーティングヘッダ（ＬＲＨ）２２３およびグローバルルーティングヘッダ（ＧＲＨ）２２５を含む入来ルーティングヘッダ２２１を含むことができる。パケットを転送する前に、ルータ２１０は、ＬＲＨ  ２２４およびＧＲＨ  ２２６を含む送出ルーティングヘッダ２２２に入来ルーティングヘッダ２２１を修正することができる。
【００２９】
図２に示されるように、エンドノードＸ  ２０３は、ローカルＨＣＡのＬＩＤアドレス、たとえばＸをソースＬＩＤであるｓｒｃＬＩＤとして配置することができ、ローカルルータのＬＩＤアドレス、たとえばＡをＬＲＨ  ２２３中のデスティネーションＬＩＤであるｄｓｔＬＩＤとして配置することができる。さらに、エンドノードＸ  ２０３は、そのレイヤ３アドレス（ＧＩＤ）、たとえば１２３４をソースＧＩＤであるｓｒｃＧＩＤとして配置することができ、最終デスティネーションアドレス（ＧＩＤ）、たとえば５６７８をＧＲＨ  ２２５中のデスティネーションＧＩＤであるｄｓｔＧＩＤとして配置することができる。
【００３０】
パケットがルータ２１０に到達すると、パケット転送メカニズム２２０はパケットフィールドを更新し置換することができる。たとえばシステムは、ローカルルーティングヘッダ（ＬＲＨ）２２４中のソースＬＩＤであるｓｒｃＬＩＤを、ルータの出口ポートのＬＩＤ、たとえばＢに置換することができる。さらにシステムは、デスティネーションＬＩＤであるｄｓｔＬＩＤを、デスティネーションのＬＩＤアドレス、たとえばＹに置換することができる。
【００３１】
代替的に、システムは、パケットが別のルータから転送されてくる場合、前のホップルータの出口ポートのＬＩＤをソースＬＩＤであるｓｒｃＬＩＤとして使用することができる。また、さらなるパケット転送が必要な場合、システムは、デスティネーションＬＩＤであるｄｓｔＬＩＤを次のホップポートのＬＩＤに置換することができる。それぞれの場合、システムは次のホップにパケットを転送する前に巡回冗長検査（ＣＲＣ）を再計算することができる。
【００３２】
発明の実施形態によれば、別個のInfiniBand（ＩＢ）サブネット間のトラフィックをルーティングするために異なる方法を使用することができる。これらの方法は、特定のデスティネーションについてどのルータを選択すべきか（第１のルーティング段階）、および当該デスティネーションに到達するにはどのパスをルータによって選択すべきか（第２のルーティング段階）などの、サブネット間ルーティングに関するさまざまな問題に対処するために使用することができる。
【００３３】
たとえば、これらの方法は、単純な古典的ルーティング法、さまざまなトポロジーに良好な性能を提供するソースルーティング法、およびファットツリーベースのトポロジーのために特殊化され、最適な性能を提供する最適化ルーティング法を含むことができる。ソースルーティング法および最適化ルーティング法は両方とも、場合によっては古典的ルーティング法よりも良好な性能を与えることができる。さらに、最適化ルーティング法は、基礎をなすファットツリートポロジーについて最適な性能を取得することを可能にする。加えて、両方の方法は、任意のマルチポートルータの使用をサポートするが、古典的ルーティングは、利用可能なポートの数を制限しない場合でもすべてのポートを効果的に利用しない場合がある。
【００３４】
したがって、これらの方法を用いて、ネイティブなＩＢルータは、性能を著しく低下させることなくサブネットを互いに接続することによって、より複雑なＩＢファブリックを構築することを可能にする。
【００３５】
サブネット間ソースルーティング（Inter-Subnet Source Routing：ＩＳＳＲ）
発明の実施形態によれば、サブネット間ソースルーティング（ＩＳＳＲ）ルーティングアルゴリズムなどの汎用ルーティングアルゴリズムを、ハイブリッドサブネットを有する複雑なネットワークをルーティングするために使用することができる。ＩＳＳＲルーティングアルゴリズムは、２つの段階、特定のデスティネーションのための入口ルータポートを選択するための第１段階と、出口ルータポートを選択するための第２段階とを含むことができる。
【００３６】
図３は、発明の実施形態に従う、ネットワーク環境において異なるデスティネーションのための入口ルータポートを選択する例示を示す。図３に示されるように、ネットワーク環境３００は、１つ以上のルータ、たとえばルータＡ  ３０１およびルータＢ  ３０２に接続されたサブネット３１０を含むことができる。
【００３７】
サブネットマネージャ（ＳＭ）、たとえばサブネット３１０中のＳＭ  ３０３は、異なるデスティネーションのための入口ルータポートを選択するのに使用することができるマッピングファイル３０４を含むことができる。さらに、入口ルータポートの選択は、ローカルサブネットに接続されるすべての利用可能なルータ間のラウンドロビンパス分散に基づくことができる。たとえば、ＩＳＳＲアルゴリズムについてローカルルータポートを選択するｆｉｎｄ＿ｒｏｕｔｅｒ（）機能は、ＯｐｅｎＳＭルーティングアルゴリズムと同様の方法で実装することができる。
【００３８】
以下は、マッピングファイル３０４のハイレベルの例である。
【００３９】
【表１】
2015520995.tif 000003
【００４０】
サブネット全体を一つのルータポートにマッチングさせることしかできないＯｐｅｎＳＭルーティングとは異なり、システムは、デスティネーションエンドポートを異なるルータポートにマッピングすることができる。さらに、マッピングファイルのセットアップを、ＯｐｅｎＳＭに設けられたマッピングファイルとは異ならせることができる。上記の表１に示されるように、マッピングファイル３０４は、ＯｐｅｎＳＭサブネット間ルーティングに関するサブネットプレフィックスのみでなく、完全修飾ポートＧＩＤを含み、入口ルータポートを選択する際に、システムが十分な粒度を提供することを可能にする。
【００４１】
さらに、図３に示されるように、等しい（または同様の）数のデスティネーションを、たとえばラウンドロビン式に多くのポートにマッピングすることができる。たとえば、デスティネーションＡ  ３１１（ｄｓｔ＿ｇｉｄ１）およびデスティネーションＣ  ３１３（ｄｓｔ＿ｇｉｄ３）は、ルータＡ  ３０１上のポート１およびポート２を介してルーティングすることができ、デスティネーションＢ  ３１２（ｄｓｔ＿ｇｉｄ２）およびデスティネーションＤ  ３１４（ｄｓｔ＿ｇｉｄ４）は、ルータＢ  ３０２上のポート１およびポート２を介してルーティングすることができる。加えて、マッピングファイル３０４はバックアップおよびデフォルトルートを特定することができる。
【００４２】
発明の実施形態によれば、出口ルータポートを選択することは、ルータファームウェアにおけるモジュロベースのハッシュを用いて実施することができる。ハッシュは、ソースおよびデスティネーションＬＩＤ（またはルータ上の入口ポート番号などのいずれかの他の有用なパラメータ）を用いて生成された乱数をとることができる。ハッシュを使用すると、出力ルータポートのうちの１つを選択することができる。さらに、ＩＳＳＲルーティングアルゴリズムは、同じペアのノードには同じパスを常に使用する決定的オブリビアス（deterministic oblivious）ルーティングアルゴリズムである。
【００４３】
さらに、ルータは３つ以上のサブネットに取付けられ得ることから、ツーステップポート確認方法を用いて、出口ルータポートを選択することができる。まず、システムは、デスティネーションが位置するサブネットに（またはサブネットの方向に）取付けられている１組の可能なポートを選択することができる。次いで、システムは、モジュロ機能に基づく単純なハッシュを用いて、出口ポートを選択することができる。
【００４４】
図４は、発明の実施形態に従う、ネットワーク環境におけるルータにおいて受信パケットのための出口ルータポートを選択する例示を示す。図４に示されるように、ネットワーク環境４００は、異なるサブネット中の様々なデスティネーションに１つ以上のパケットをルーティングすることができるルータ、たとえばルータＡ  ４０１を含むことができる。
【００４５】
たとえば、ルータＡ  ４０１は、サブネット４０３中のデスティネーションＸ  ４２１宛てのソースＡ  ４１１からのパケットを、ポート１において受信することができる。加えて、ルータＡ  ４０１は、サブネット４０２中のデスティネーションＹ  ４２２宛てのソースＣ  ４１３からの別のパケットを、ポート２において受信することができる。
【００４６】
以下のアルゴリズム１は、出口ルータポートを選択するためのＳＭおよびルータファームウェアの両方において実装することができる。
【００４７】
【表２】
2015520995.tif 000004
【００４８】
ルーティング決定は、ソースＬＩＤおよびデスティネーションＬＩＤの両方に基づくことができる。ソースＬＩＤは、オリジナルソースまたはトランジットサブネットシナリオにおける前のホップルータの出口ポートのいずれかとすることができ、デスティネーションＬＩＤは、最終デスティネーションＬＩＤまたは次のホップ入口ルータポートのＬＩＤのいずれかとすることができる。
【００４９】
サブネットが取付けられているのを見ることができることから、ルータＡ  ４０１は、ソースＬＩＤおよびデスティネーションＬＩＤの両方についての値を識別する。デスティネーションＬＩＤを得るためには、アルゴリズム１中のｇｅｔ＿ｎｅｘｔ＿ＬＩＤ（）（２行目）などのマッピング機能を用いて、デスティネーションＧＩＤをデスティネーションＬＩＤにマッピングすることができるか、またはＧＩＤ内に位置するサブネットプレフィックスに基づいて次のホップＬＩＤを戻すことが必要とされる。マッピング機能は、連想メモリルックアップ、最終デスティネーションのローカル識別子（ＬＩＤ）をグローバルルーティングヘッダ（ＧＲＨ）フィールドからデコードすること、次のホップのローカル識別子をグローバルルーティングヘッダ（ＧＲＨ）フィールドからデコードすることのうち、１つ以上を行なうことができる。
【００５０】
発明の実施形態によれば、出口ルータポートを選択するアルゴリズムは、ソースおよびデスティネーションＬＩＤに基づく乱数を算出することができる。この乱数を用いて、１組の可能なポートから一つの出口ポートを選択することができる。乱数の生成は、所定のソース−デスティネーションのペアが同じ数を常に生成することができるような決定的な手法で行なうことができる。したがってシステムは、出口ポートを選択するためのラウンドロビン法とは異なり、サブネット間でルーティングする際のアウトオブオーダー配信を防ぐことができ、各ソース−デスティネーションのペアがネットワークを通る同じパスを常に使用することを確実にする。
【００５１】
図５は、発明の実施形態に従う、ネットワーク環境におけるルータにおいてサブネット間ソースルーティング（ＩＳＳＲ）アルゴリズムをサポートするための典型的なフローチャートを例示する。図５に示されるように、ステップ５０１において、ルータは、当該ルータが担う１つ以上のパケットのルーティング先であるデスティネーションのリストを受信することができ、ルータは、ネットワーク環境において少なくとも１つのサブネットに接続している。次いで、ステップ５０２において、ルータは、１つ以上のパケットに関連付けられたソースローカル識別子（ＬＩＤ）およびデスティネーションＬＩＤに基づいて乱数を生成することができる。さらに、ステップ５０３において、ルータは、モジュロベースのハッシュを用いて、ルータの出力ルータポートのうち１つのポートを選択することができる。
【００５２】
サブネット間ファットツリールーティング（Inter-Subnet Fat-Tree Routing：ＩＳＦＲ）
発明の実施形態によれば、サブネット間ファットツリールーティング（ＩＳＦＲ）ルーティングアルゴリズムなどの最適化ルーティング法は、ファットツリートポロジーを有するサブネット間でルーティングするために使用されることができる。
【００５３】
最適化ルーティング法は、ローカルサブネットに接続されるすべての利用可能なルータ間のラウンドロビンパス分散の第１段階、各ルータに接続された下流側へのスイッチを照会し、どのスイッチが特定のデスティネーションへの主要なパスとして作用するかを学習する第２段階、および第１段階と第２段階とから得られる情報を用いてルーティングテーブルを構築する第３段階などの３つの段階を含むことができる。
【００５４】
図６は、発明の実施形態に従う、ネットワーク環境６００におけるルータにおいてサブネット間ファットツリールーティング（ＩＳＦＲ）アルゴリズムをサポートする例示を示す。図６に示されるように、ルータ６０１は、１つ以上のエンドノード６２１−６２４に接続するサブネット６１０にパケット６５０をルーティングすることを担う。サブネット６１０は、ファットツリートポロジー中のＳＷ６１１−６１６などの１つ以上のスイッチを含むことができる。
【００５５】
ルータ６０１は、特定のデスティネーションへのパケットを、関連付けられたＧＩＤに相応してルーティングするためにはそのポートのうちどれを使用することができるかを学習することができる。たとえば、ルータ６０１は、サブネット６１０中のサブネットマネージャ（ＳＭ）６２０からポートマッピング６３０を受信することができる。ポートマッピング６３０は、ルータ６０１が担うサブネット６１０から生じるパケットのルーティング先であるデスティネーションのリストを含むことができる。
【００５６】
さらに、ルータ６０１は、パケット６５０をルーティングする際に最大性能を実現するためにはいずれの下流側出力ポートを使用するべきであるかをスイッチ６１１−６１２から学習することができる。たとえば、ルータ６０１は、サブネット６１０における宛先ノードへの主要なパスについて、サブネット６１０におけるスイッチ６１１−６１２に照会することができる。それらのスイッチのうちの１つのみが所望のデスティネーションへの専用の主要なパスを有し得ることから、照会によって、パケット６５０についての主要なパス（スイッチ６１１またはスイッチ６１２のいずれか）をルータが選択することが可能となる。
【００５７】
次いでルータ６０１は、上で得られた情報を用いてルーティングテーブル６４０を構築することができる。たとえば、ローカルＯｐｅｎＳＭルーティングは、スイッチ６１１またはスイッチ６１２のいずれかのルーティングテーブルに宛先ノードへの主要なパスをマークすることができる。
【００５８】
以下のアルゴリズム２は、ルータ上の出口ポートを選択するためのルータファームウェアに実装することができる。
【００５９】
【表３】
2015520995.tif 000005
【００６０】
上記のＩＳＦＲアルゴリズムは、表１のＧＩＤ‐ルータポートマッピングを含む、あらかじめ定義されたファイル形式を使用することができる。ＩＳＳＲアルゴリズムのように、ＩＳＦＲアルゴリズムはルータ装置において実装することができる。さらに、ＩＳＦＲアルゴリズムは、ファットツリー上で、かつファットツリールーティングがあらゆるサブネットにおいてローカルに実行している状態でのみ機能し得る。また、必要であれば、ＩＳＦＲアルゴリズムはＩＳＳＲに戻ることができる。
【００６１】
図６に示されるように、ルータ６０１は、適切なファットツリートポロジーの上に位置するものとして表わすことができる。したがって、照会が行なわれた後、ルータ６０１は、特定のサブネットに位置する各デスティネーションについて下流側への方向にポートごとに１つのパスを有することができる。オーバーサブスクライブファットツリーの場合、パスの数はオーバーサブスクリプション比率と同等することができる。
【００６２】
加えて、サブネット６１０に接続された２つ以上のルータがある場合がある。ＩＳＦＲルーティングのプロパティは、すべてのスパイン（トップ）ルータがスイッチに置換された場合、（ルータによる）ＩＳＦＲルーティングのための、および（スイッチによる）ローカルルーティングのためのルーティングテーブルが同じとなるようなものである。
【００６３】
発明の実施形態によれば、ＩＳＦＲルーティングアルゴリズムは、不透明なルータによって接続される異なるサブネット中のサブネットマネージャ（ＳＭ）間で確立された通信に基づいて実装することができる。たとえば、ＳＭがそれを介して通信することができるルータにインターフェイスを設けることができ、付近のサブネットに位置する２つのＳＭ間でハンドシェーキングを実施することができる。
【００６４】
図７〜図９は、発明の実施形態に従う、異なるトポロジーによるネットワーク環境におけるルーティングを例示する。トポロジーの各々は、多段ファットツリー、たとえばルータが上に置かれた３段ファットツリーとして表わすことができる。たとえば、３段ファットツリーは、３つのルーティング／スイッチ段階および１つのノード段階を有することができ、各サブネット（２段ファットツリー）はブランチとして出現する。さらに、ＩＳＦＲルーティングアルゴリズムに基づいて、より大きなトポロジーをサポートすることもできる。
【００６５】
発明の実施形態によれば、各サブネットが、いずれのトランジットサブネットも介在しない状態で他のサブネットに直接取付けることができるファットツリートポロジーであるように、ネットワーク環境を構成することができる。
【００６６】
たとえば、図７において、システム７００は、６つのルータ７１０を用いて、２つのファットツリーサブネット、たとえばサブネットＡ−Ｂ  ７０１−７０２を接続することができる。図８において、システム８００は、６つのルータ８１０を用いて、３つのファットツリーサブネット、たとえばサブネットＡ−Ｃ  ８０１−８０３を接続することができる。図９では、システム９００は１８個のルータ９１０を用いて６４８ポートの３段ファットツリーを作成して、６つのファットツリーサブネット９０１−９０６を接続することができる。
【００６７】
図１０は、発明の実施形態に従う、ネットワーク環境におけるルータにおいてサブネット間ファットツリールーティング（ＩＳＦＲ）アルゴリズムをサポートするための典型的なフローチャートを例示する。図１０に示されるように、ステップ１００１において、ルータは、当該ルータが担う１つ以上のパケットのルーティング先であるデスティネーションのリストを受信することができ、ルータは、ネットワーク環境において少なくとも１つのサブネットに接続している。次いで、ステップ１００２において、ルータは、１つ以上のパケットをルーティングするためにルータのいずれの下流側出力ポートを使用することができるかについての情報を、少なくとも１つのサブネットにおける１つ以上のスイッチから取得することができる。さらに、ステップ１００３において、ルータは、取得された情報に基づいてルーティングテーブルを構築することができる。
【００６８】
図１１は、発明の実施形態の特徴を示すための機能ブロック図を例示する。本特徴は、ネットワーク環境において別個のサブネット間のトラフィックをルーティングするためのシステム１１００として実装され得る。システム１１００は、１つ以上のマイクロプロセッサ、および１つ以上のマイクロプロセッサ上で動くルータ１１１０を含む。ルータ１１１０は、当該ルータが担う１つ以上のパケットのルーティング先であるデスティネーションのリストを受信ユニット１１２０から受信し、１つ以上のパケットをルーティングするためにルータのいずれの下流側出力ポートを使用することができるかについての、少なくとも１つのサブネットにおける１つ以上のスイッチからの情報を取得ユニット１１３０から取得し、取得された情報に基づいてルーティングテーブルを構築ユニット１１４０上に構築するように動作する。
【００６９】
一実施形態によれば、１つ以上のマイクロプロセッサ上のネットワーク環境においてディストリクトサブネット間のトラフィックをルーティングするためのシステムが開示される。システムは、ルータにおいて、当該ルータが担う１つ以上のパケットのルーティング先であるデスティネーションのリストを受信するための手段を備え、ルータは、ネットワーク環境において少なくとも１つのサブネットに接続している。システムは、１つ以上のパケットをルーティングするためにルータのいずれの下流側出力ポートを使用することができるかについての情報を、少なくとも１つのサブネットにおける１つ以上のスイッチから取得するための手段を備える。システムは、取得された情報に基づいてルーティングテーブルを構築するための手段を備える。
【００７０】
好ましくは、システムは、少なくとも１つのサブネットに接続されるすべての利用可能なルータ間でラウンドロビンパス分散を行なうための手段を備える。
【００７１】
好ましくは、システムは、各ルータに接続されているスイッチに照会して、いずれのスイッチが特定のデスティネーションへの主要なパスとして作用するかについて学習するための手段を備える。
【００７２】
好ましくは、システムは、最大性能のためにルータのいずれの下流側出力ポートを使用することができるかを取得された情報に基づいて判定するための手段を備える。
【００７３】
好ましくは、システムは、ルータによって接続されたサブネットを異なるネットワークトポロジーで構成することを可能にするための手段を備える。
【００７４】
好ましくは、システムは、１つ以上の付加的なルータを用いて、ネットワーク環境における１つ以上の近隣のサブネットに少なくとも１つのサブネットを接続するための手段を備える。
【００７５】
好ましくは、システムは、接続されるサブネットが異なるトポロジーであることを可能にするための手段を備える。
【００７６】
好ましくは、システムは、接続される各サブネットが多段ファットツリーにおけるブランチであることを可能にするための手段を備える。
【００７７】
好ましくは、システムは、少なくとも１つのサブネットがファットツリートポロジーで構成されることを可能にするための手段を備える。
【００７８】
好ましくは、システムは、少なくとも１つのサブネットをルーティングするためにファットツリールーティングアルゴリズムを使用するための手段を備える。
【００７９】
一実施形態によれば、ネットワーク環境において別個のサブネット間のトラフィックをルーティングするためのシステムが開示される。システムはルータを含み、上記ルータは、当該ルータが担う１つ以上のパケットのルーティング先であるデスティネーションのリストを受信するように構成され、ルータは、ネットワーク環境において少なくとも１つのサブネットに接続している。ルータは、１つ以上のパケットをルーティングするためにルータのいずれの下流側出力ポートを使用することができるかについての情報を、少なくとも１つのサブネットにおける１つ以上のスイッチから取得するように構成され、かつ取得された情報に基づいてルーティングテーブルを構築するようにも構成される。
【００８０】
好ましくは、システムは、少なくとも１つのサブネットに接続されるすべての利用可能なルータ間でラウンドロビンパス分散を行なうことができる。
【００８１】
好ましくは、システムは、上記ルータに接続されているスイッチに照会して、いずれのスイッチが特定のデスティネーションへの主要なパスとして作用することができるかについて学習するように上記ルータを動作させることができる。
【００８２】
好ましくは、システムは、取得された情報に基づいて、最大性能のためにルータのいずれの下流側出力ポートを使用することができるかを判定するように上記ルータを動作させることができる。
【００８３】
好ましくは、システムは、１つ以上のデスティネーショングローバル識別子（ＧＩＤ）と１つ以上のルータポートとの間のポートマッピングをサブネットマネージャから受信するように上記ルータを動作させることができる。
【００８４】
好ましくは、システムは、１つ以上の付加的なルータを用いて、ネットワーク環境における１つ以上の近隣のサブネットに少なくとも１つのサブネットを接続させることができる。
【００８５】
好ましくは、システムは、接続されるサブネットを異なるトポロジーにさせることができる。
【００８６】
好ましくは、システムは、接続される各サブネットを多段ファットツリーにおけるブランチにすることができる。
【００８７】
好ましくは、システムは、少なくとも１つのサブネットをファットツリートポロジーで構成させ、少なくとも１つのサブネットをルーティングするためにファットツリールーティングアルゴリズムを使用させることができる。
【００８８】
本発明は、本開示の教示に従ってプログラミングされる１つ以上のプロセッサ、メモリ、および／またはコンピュータ読取可能な記録媒体を含む、１つ以上の従来の汎用もしくは特化デジタルコンピュータ、コンピューティングデバイス、マシン、またはマイクロプロセッサを用いて好都合に実現されてもよい。適切なソフトウェアコーディングは、ソフトウェア技術の当業者には明らかであるように、本開示の教示に基づいて、熟練したプログラマーによって容易に作成されることができる。
【００８９】
いくつかの実施形態では、本発明は、本発明のプロセスのうち任意のものを行なうようにコンピュータをプログラミングするのに用いることができる命令をその上に／その中に記憶した記録媒体またはコンピュータ読取可能な媒体であるコンピュータプログラム製品を含む。記録媒体は、フロッピー（登録商標）ディスク、光学ディスク、ＤＶＤ、ＣＤ−ＲＯＭ、マイクロドライブ、および磁気光学ディスクを含む任意の種類のディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、ＤＲＡＭ、ＶＲＡＭ、フラッシュメモリデバイス、磁気もしくは光学カード、（分子メモリＩＣを含む）ナノシステム、または命令および／もしくはデータを記憶するのに好適な任意の種類の媒体もしくはデバイスを含むことができるが、これらに限定されない。
【００９０】
本発明の以上の説明は、例示および説明の目的のために与えられた。網羅的であることまたは開示される正確な形態に発明を限定することを意図するものではない。当業者には多数の修正例および変形例が明らかである。発明の原則およびその実際的な適用例を最も良く説明し、これによりさまざまな実施形態について、企図される特定の用途に適するさまざまな修正例とともに当業者が発明を理解できるようにするために、実施形態を選択し、説明した。発明の範囲は、以下の請求項およびそれらの均等物によって規定されることが意図される。
【図１】
2015520995.tif 000006
【図２】
2015520995.tif 000007
【図５】
2015520995.tif 000008
【図６】
2015520995.tif 000009
【図７】
2015520995.tif 000010
【図８】
2015520995.tif 000011
【図９】
2015520995.tif 000012
【図１０】
2015520995.tif 000013
【図１１】
2015520995.tif 000014
【図３】
2015520995.tif 000015
【図４】
2015520995.tif 000016
【国際調査報告】
2015520995.tif 000017
2015520995.tif 000018
2015520995.tif 000019