アドレス指定方法、アドレス指定装置、ファブリックマネージャ、スイッチ、およびデータルーティング方法
【課題】 本発明は、データセンターネットワーク用のアドレス指定方法、アドレス指定装置、ファブリックマネージャ、スイッチ、およびデータルーティング方法を提供する。
【解決手段】 本発明によるアドレス指定装置は、複数のツリーを取得するために、ネットワークトポロジ発見機能を使用して、各スイッチを順にルートとして、全ホストを含むツリーを作成するツリー作成手段と、ツリー作成手段によって作成された複数のツリーから最低高さを有するツリーを選択するツリー選択手段と、ツリー選択手段によって選択された最低高さを有する各ツリーに関し、ネットワーク内の各スイッチおよび各ホストにアドレスを割り当てるアドレス割り当て手段とを備える。
【解決手段】 本発明によるアドレス指定装置は、複数のツリーを取得するために、ネットワークトポロジ発見機能を使用して、各スイッチを順にルートとして、全ホストを含むツリーを作成するツリー作成手段と、ツリー作成手段によって作成された複数のツリーから最低高さを有するツリーを選択するツリー選択手段と、ツリー選択手段によって選択された最低高さを有する各ツリーに関し、ネットワーク内の各スイッチおよび各ホストにアドレスを割り当てるアドレス割り当て手段とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データセンターネットワークに関し、特に、データセンターで採用される様々なトポロジに適応可能な、データセンターネットワーク用のアドレス指定方法、アドレス指定装置、ファブリックマネージャ、スイッチ、およびデータルーティング方法に関する。本発明は、転送テーブルの短縮を目的としたロケータアドレスの集約と、ネットワークのロードバランスとを実現することができる。
【背景技術】
【０００２】
クラウドサービスの普及により、数万〜数十万台のサーバを備えるデータセンターの創設が加速している。また、データセンターは複数の異なるアプリケーションを同時にサポートしており、それには、データセンター内のサーバ間における帯域集約型の全対全通信を必要とするものも含まれる。こうしたアプリケーションの大規模化と発達により、データセンターのネットワークファブリックに様々な課題が生じている。
【０００３】
データセンターネットワークの目的を達成するためには、多数のデータセンターサーバを相互接続し、効率的で耐故障性を有するルーティングおよび転送サービスを高レベルのアプリケーションに提供する必要がある。データセンターネットワークファブリックの主な選択肢としては、レイヤ２ネットワークとレイヤ３ネットワークの２つが挙げられる。
・レイヤ２ネットワークにおいては、データセンターは単一のＥｔｈｅｒｎｅｔとみなされる。Ｅｔｈｅｒｎｅｔでは、ネットワーク管理は容易であるが（プラグアンドプレイ、シームレスな仮想マシンマイグレーション等）、数万台のサーバを含むネットワークへの拡張は不可能である。
・レイヤ３方式では、拡張性の問題は克服できるが、Ｅｔｈｅｒｎｅｔの単純性が犠牲にされているため、管理負担が大きい。
【０００４】
Ｅｔｈｅｒｎｅｔの拡張性の問題を解決して、「プラグアンドプレイ」と大規模データセンターネットワークの両方をサポートすることを目指して、研究者によって新しい方法およびシステムが提案されている。
【０００５】
Ｅｔｈｅｒｎｅｔは、現在広く使用されているコモンＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）技術である。Ｅｔｈｅｒｎｅｔはネットワーク内のノードをＭＡＣアドレスで識別する。ＩＰアドレスの階層構造とは異なり、ＭＡＣアドレスはフラット構造であり、全世界において一意である。宛先ＭＡＣアドレスから送信ポートへのマッピングレコードは、スイッチ内の転送テーブルで保持される。
【０００６】
図１は、スイッチが自己学習方式で転送テーブルを作成する場合を示す概略図である。データフレームがスイッチに着信すると、スイッチはデータフレームの送信元ＭＡＣアドレスをチェックし、送信元ＭＡＣアドレスとデータフレームが入力されるポート間のマッピングを転送テーブルに格納する。自己学習メカニズムとＭＡＣアドレスの使用により、ネットワーク管理は容易になり、スイッチは「プラグアンドプレイ」の機能を獲得する。
【０００７】
しかし、以下の理由により、Ｅｔｈｅｒｎｅｔは依然として数万台のサーバを備えるネットワークに拡張することはできない。第１に、ＭＡＣアドレスは階層的ではないので、複数のＭＡＣアドレスを１つに集約することができない。宛先ＭＡＣアドレスと送信ポート間のマッピングレコードはスイッチの転送テーブルに格納されるため、ネットワーク全体の全ホストのＭＡＣアドレスが、各スイッチの転送テーブルに格納されなければならない。ネットワーク内のホスト数は、スイッチのバッファサイズによって制限される。第２に、図２に示すように、未知の宛先ＭＡＣアドレスを有するデータフレームについては（宛先ＭＡＣアドレスは転送テーブルに格納されない）、スイッチはそれをデータフレームが着信したポートを除くすべてのポートへ送信（ブロードキャスト）する。加えて、一部の基本的なネットワークサービス（アドレス解決プロトコル、動的ホスト構成プロトコル等）はブロードキャストによって実行される。Ｅｔｈｅｒｎｅｔは、このブロードキャストメカニズムによっても、大規模ネットワークへの拡張を制限される。最後に、Ｅｔｈｅｒｎｅｔはスパニングツリープロトコル（ＳＴＰ）を使用してループを回避するが、単一のツリーに沿って転送するためルーティングが非効率的であり、リンクの負荷バランスも悪化する。
【０００８】
そのため、データセンターネットワークを大規模ＬＡＮとして構築することはできない。１つの解決法は、レイヤ２構成とレイヤ３構成を混在させることである。これは、データセンターを、ＩＰルートによって接続された複数のＬＡＮとして構築することを意味する。各ＬＡＮは数十〜数百のマシンから成り、１つのＩＰサブネットを形成する。レイヤ２構成とレイヤ３構成を混在させることで、拡張性の問題は克服できるが、Ｅｔｈｅｒｎｅｔの単純性が犠牲にされるため、管理負担は依然として重い。本発明の目的は、Ｅｔｈｅｒｎｅｔの拡張性の問題を解決して、「プラグアンドプレイ」と大規模データセンターネットワークの両方をサポートすることである。
【０００９】
非特許文献１は、データセンターネットワークのためのレイヤ２アドレス指定プロトコル、ルーティングプロトコル、および転送プロトコルをセットにした、ＰｏｒｔＬａｎｄプロトコルを提案している。このプロトコルでは、疑似ＭＡＣ（ＰＭＡＣ）アドレスをネットワーク内のすべてのホストに割り当てることにより、トポロジ内のホストの位置が符号化される。ＰＭＡＣアドレスを使用すると、少ないスイッチステートで効率的に転送することができる。以下では、ＰｏｒｔＬａｎｄシステムについて詳細に説明する。
【００１０】
図３に、ＰｏｒｔＬａｎｄシステムのアーキテクチャの概略図を示す。
【００１１】
ＰｏｒｔＬａｎｄシステムにおいては、各エンドホストに、ＰＭＡＣが割り当てられ（図３の例では、ＭＡＣアドレスが「００．１９．Ｂ９．ＦＡ．８８．Ｅ２」、ＩＰアドレスが「１０．５．１．２」のエンドホストにＰＭＡＣ「００．００．０１．０２．００．０１」が割り当てられている）、これによりトポロジ内のエンドホストの位置が符号化されている。データパケットを転送するための転送テーブルには、実際のＭＡＣアドレスではなく、ＰＭＡＣアドレスが格納される。ＰＭＡＣアドレスは階層的なので、スイッチが保持する転送テーブルを小規模に維持することができる。加えて、ＰｏｒｔＬａｎｄシステムは、ネットワークの構成情報と状態を保持する、集中型のファブリックマネージャ（ＦＭ）３００を備えている。ＦＭ３００は、従来のＥｔｈｅｒｎｅｔの純粋なブロードキャストメカニズムとは異なり、ＡＲＰの解決を容易にし、耐故障性能を向上させる。
【００１２】
ＰｏｒｔＬａｎｄプロトコルは、ファットツリートポロジに基づく、アドレス指定プロトコル、ルーティングプロトコル、および転送プロトコルのセットである（非特許文献３参照）。ファットツリートポロジでは、スイッチはエッジ層、集約層、コア層という３つの層に分割される。各層のすべてのスイッチは同一であり、それぞれｋ個のポートを備える。図３のファットツリートポロジでは、ｋ＝４である。このファットツリーは、ｋ個の個別ポッドに分割されている。図３の点線の枠で示すエッジ層と集約層には、ｋ個のスイッチから成るポッドが１つの枠で囲まれている。一般に、ファットツリーは、ｋ個のポートを備える５ｋ２／４個のスイッチを使用して、ｋ３／４個のホストの間でノンブロッキング通信をサポートすることができる。
【００１３】
エッジスイッチは、各４８ビットＰＭＡＣアドレスを、直接接続されたすべてのホストにそれぞれ割り当てる。ＰＭＡＣアドレスは階層的であり、トポロジ内のホストの位置を符号化する。ＰＭＡＣアドレスは、以下の形式である。
ポッド．位置．ポート．仮想マシンＩＤ
【００１４】
ここで、
「ポッド」は１６ビットの長さで、エッジスイッチのポッド番号を表す。
「位置」は８ビットの長さで、ポッド内のエッジスイッチの位置を示す。
「ポート」は８ビットの長さで、ホストが接続されるエッジスイッチのポート番号を表す。
「仮想マシンＩＤ」は１６ビットの長さで、物理マシン上の仮想マシンの番号を示す（同じ物理マシン上に複数の仮想マシンが存在できる）。
【００１５】
図３の例において、左から３番目のホストのＰＭＡＣアドレスは「００．００．０１．０２．００．０１」であり、ここで、
ポッド「００．００」はポッド０を示す。
位置「０１」はポッド０内の位置０１を表す。
ポート「０２」は、エンドホストはエッジスイッチのポート０２に接続されていることを示す。
仮想マシンＩＤ「００．０１」は、エンドホスト内の仮想マシンの番号は１であることを示す。
【００１６】
図３に示すように、データパケットを転送するための転送テーブルには、実際のＭＡＣアドレスではなくＰＭＡＣアドレスが格納される（図３の右側のテーブル参照）。ＭＡＣアドレスのフラット構造とは異なり、ＰＭＡＣアドレスは階層的なので、スイッチに保持する転送テーブルは小さくてもよい。各層のスイッチの転送テーブルは、以下のとおりである。
・コアスイッチ：ポッド．＊⇔送信ポート
この例では、図３の右端にあるコアスイッチのポート０および１は、それぞれポッド０および１に接続されている。したがって、宛先ＭＡＣアドレスが「００．００．＊」のすべてのデータパケットはポート０に送られる。これは、ポッド０を宛先とするすべてのデータパケットはポート０に送信されることを意味する。同様に、ポッド１を宛先とするすべてのデータパケットはポート１に送信されることを意味する。
・集約スイッチ：ポッド．位置．＊⇔送信ポート
例えば、図３の右端にある集約スイッチは、ポッド３、すなわち００．１１に属する。したがって、宛先ＭＡＣアドレスが「００．１１．＊」のすべてのデータパケットはこのポッド３に送られ（すなわち、宛先ＭＡＣアドレスが「００．１１．００．＊」のすべてのデータパケットは位置「０」（ポート０）のエッジスイッチに送られ）、宛先ＭＡＣアドレスが「００．１１．０１．＊」のすべてのデータパケットは位置「１」（すなわち、ポート１）のエッジスイッチに送られる。他の宛先ＭＡＣアドレスを有するデータパケットは、ポート２またはポート３を介して、アップリンクデータパケットとして他のポッドに送られる。
・エッジスイッチ：ポッド．位置．ポート．＊⇔送信ポート
この例では、図３の右端にあるエッジスイッチは、ポッド３、位置１，すなわち００．１１．０１に属する。このスイッチには２つのホストが直接接続されており、宛先ＭＡＣアドレスが「００．１１．０１．００．＊」のすべてのデータパケットはポート０に送られ、宛先ＭＡＣアドレスが「００．１１．０１．０１．＊」のすべてのデータパケットはポート１に送られる。他の宛先ＭＡＣアドレスを有するデータパケットは、ポート２またはポート３を介して、アップリンクデータパケットとして他のホストに送られる。
【００１７】
ＰｏｒｔＬａｎｄプロトコルは、データセンターネットワークのためのレイヤ２アドレス指定プロトコル、ルーティングプロトコル、および転送プロトコルのセットで構成される。ただし、ＰｏｒｔＬａｎｄプロトコルはこのファットツリートポロジに限定され、他のトポロジには適用できない。例えば、ＰｏｒｔＬａｎｄプロトコルによって使用されるＰＭＡＣの形式「ポッド．位置．ポート．仮想マシンＩＤ」は、非特許文献２で提案されるＣｌｏｓトポロジに直接適用することはできない。
【００１８】
図４に、Ｃｌｏｓトポロジの概略図を示す。Ｃｌｏｓトポロジもやはり３つの層に分割され、Ｔｏｐ ｏｆ Ｒａｃｋ（ＴｏＲ）スイッチは、エンドホストに直接接続されるファットツリートポロジのエッジスイッチと類似している。ファットツリートポロジのすべてのスイッチは同一である。ただし、Ｃｌｏｓトポロジでは、コアスイッチと集約スイッチは１０Ｇポートを有するスイッチである。ＴｏＲスイッチは１０Ｇのアップリンクポートを介して集約スイッチに接続されるが、ホストへは１Ｇのダウンリンクポートを介して接続される。
【００１９】
Ｃｌｏｓトポロジにポッドの概念はないので、ＰＭＡＣの形式（ポッド．位置．ポート．仮想マシンＩＤ）を直接利用することはできない。集約スイッチがポッドに対応する場合（例えば、集約スイッチＳ３およびＳ４がそれぞれポッド０およびポッド１に対応する場合）、ＴｏＲスイッチをアドレス指定することはできない。各ＴｏＲスイッチは２つの集約スイッチに接続されている（例：ＴｏＲスイッチＳ７が集約スイッチＳ３およびＳ４に接続されている）ので、ＴｏＲスイッチＳ７のポッド番号は０または１の可能性があるからである。その結果、非特許文献１で提案されるＰｏｒｔＬａｎｄプロトコルは、非特許文献２で提案されるＣｌｏｓトポロジに直接適用することはできない。
【先行技術文献】
【非特許文献】
【００２０】
【非特許文献１】“ＰｏｒｔＬａｎｄ：Ａ Ｓｃａｌａｂｌｅ Ｆａｕｌｔ Ｔｏｌｅｒａｎｔ ｌａｙｅｒ−２ Ｄａｔａ Ｃｅｎｔｅｒ Ｎｅｔｗｏｒｋ Ｆａｂｒｉｃ（ＰｏｒｔＬａｎｄ：スケーラブル故障耐性レイヤ２データセンターネットワークファブリック）”，Ｒａｄｈｉｋａ Ｎｉｒａｎｊａｎ Ｍｙｓｏｒｅ ｅｔｃ．，ｉｎ Ｓｉｇｃｏｍｍ ２００９
【非特許文献２】“ＶＬ２：Ａ Ｓｃａｌａｂｌｅ ａｎｄ Ｆｌｅｘｉｂｌｅ Ｄａｔａ Ｃｅｎｔｅｒ Ｎｅｔｗｏｒｋ（ＶＬ２：スケーラブルでフレキシブルなデータセンターネットワーク）”，Ａｌｂｅｒｔ Ｇｒｅｅｎｂｅｒｇ ｅｔｃ．，ｉｎ Ｓｉｇｃｏｍｍ ２００９
【非特許文献３】“Ａ Ｓｃａｌａｂｌｅ，Ｃｏｍｍｏｄｉｔｙ Ｄａｔａ Ｃｅｎｔｅｒ Ｎｅｔｗｏｒｋ Ａｒｃｈｉｔｅｃｔｕｒｅ（スケーラブルなコモディティデータセンターネットワークアーキテクチャ”，Ｍ．Ａｌ−Ｆａｒｅｓ ｅｔｃ．，ｉｎ Ｓｉｇｃｏｍｍ ２００８
【発明の概要】
【発明が解決しようとする課題】
【００２１】
関連技術における上記の欠点を鑑みて、本発明の目的は、データセンターで採用される様々なトポロジに適応可能な、データセンターネットワーク用のアドレス指定方法、アドレス指定装置、ファブリックマネージャ、スイッチ、およびデータルーティング方法を提供することにある。本発明は、転送テーブルの短縮を目的としたロケータアドレスの集約と、ネットワークのロードバランスとを実現することができる。
【００２２】
本発明は、データセンターネットワーク用のアドレス指定方法、アドレス指定装置、ファブリックマネージャ、スイッチ、およびデータルーティング方法を提供する。ネットワーク内のホストとスイッチは、１つ以上のロケータアドレスに割り当てられる。ロケータアドレスは階層的であり、トポロジ内のホストおよびスイッチの位置を符号化する。トポロジ内に冗長パスが設けられている場合、スイッチおよびホストは複数のロケータアドレスに割り当てられる。データパケットを転送するためのスイッチの転送テーブルには、ＭＡＣアドレスではなく、ロケータアドレスが格納される。複数のロケータアドレスは複数のパスがあることを示す。複数のパスからロードバランスを実現できるいくつかの適切なパスを選択することが可能となる。
【００２３】
本発明の第１の態様によれば、アドレス指定装置であって、複数のツリーを取得するために、ネットワークトポロジ発見機能を使用して、各スイッチを順にルートとして、全ホストを含むツリーを作成するツリー作成手段と、ツリー作成手段によって作成された複数のツリーから最低高さを有するツリーを選択するツリー選択手段と、ツリー選択手段によって選択された最低高さを有する各ツリーに関し、ネットワーク内の各スイッチおよび各ホストにアドレスを割り当てるアドレス割り当て手段とを備えるアドレス指定装置を提供する。
【００２４】
好ましくは、１つのスイッチをルートとして、全ホストを含む複数のツリーが作成された場合、ツリー作成手段は、当該スイッチをルートとする複数のツリーのうち最低高さを有するツリーの１つを、作成されたツリーとして選択する。
【００２５】
好ましくは、１つのスイッチをルートとして、全ホストを含む複数のツリーが作成された場合、ツリー作成手段は、当該複数のツリーのすべてを、作成されたツリーとして記録する。
【００２６】
好ましくは、当該複数のツリーのうち最低高さを有するツリーが複数個ある場合、ツリー選択手段は、最低高さを有する当該複数個のツリーのすべてを選択する。
【００２７】
好ましくは、アドレス割り当て手段は、ツリー選択手段によって選択された最低高さＨを有する各ツリーについて、ルートスイッチロケータアドレスを、ツリーのルートに位置するルートスイッチ（「第０層スイッチ」とも称する）に割り当て、ルートスイッチに直接接続された第１層スイッチから開始して、第（ｉ−１）層スイッチに直接接続された第ｉ層スイッチの各々について、ルートスイッチから第ｉ層スイッチまでのすべてのパスを検出し、各パスについて、「ルートスイッチロケータアドレス．第１層スイッチアドレス．・・・．第ｉ層スイッチアドレス」（ここで１≦ｉ≦Ｈ−２）の形式で、第ｉ層スイッチロケータアドレスを第ｉ層スイッチに割り当て、かつ、「エッジスイッチロケータアドレス．ホストアドレス」（ここで、エッジスイッチはホストに直接接続された第ｋ層スイッチであり、０≦ｋ≦Ｈ−２）の形式で、ホストロケータアドレスを各ホストに割り当てる。
【００２８】
好ましくは、第ｉ層スイッチアドレスは、第（ｉ−１）層スイッチの各第ｉ層スイッチに接続された個々のポートのポート番号である。
【００２９】
好ましくは、ホストアドレスは、エッジスイッチの各ホストに接続された個々のポートのポート番号である。
【００３０】
本発明の第２の態様によれば、アドレス指定方法であって、複数のツリーを取得するために、ネットワークトポロジ発見機能を使用して、各スイッチを順にルートとして、全ホストを含むツリーを作成するステップと、作成された複数のツリーから最低高さを有するツリーを選択するステップと、選択された最低高さを有する各ツリーに関し、ネットワーク内の各スイッチおよび各ホストにアドレスを割り当てるステップとを備えるアドレス指定方法を提供する。
【００３１】
好ましくは、１つのスイッチをルートとして、全ホストを含む複数のツリーが作成された場合、当該スイッチをルートとする複数のツリーのうち最低高さを有するツリーの１つが、作成されたツリーとして選択される。
【００３２】
好ましくは、１つのスイッチをルートとして、全ホストを含む複数のツリーが作成された場合、当該複数のツリーのすべてが、作成されたツリーとして記録される。
【００３３】
好ましくは、当該複数のツリーのうち最低高さを有するツリーが複数個ある場合には、最低高さを有する当該複数個のツリーのすべてが選択される。
【００３４】
好ましくは、最低高さＨを有する各選択されたツリーについて、ルートスイッチロケータアドレスが、ツリーのルートに位置するルートスイッチ（「第０層スイッチ」とも称する）に割り当てられ、ルートスイッチに直接接続された第１層スイッチから開始して、第（ｉ−１）層スイッチに直接接続された第ｉ層スイッチの各々について、ルートスイッチから第ｉ層スイッチまでのすべてのパスが検出され、各パスについて、「ルートスイッチロケータアドレス．第１層スイッチアドレス．・・・．第ｉ層スイッチアドレス」（ここで１≦ｉ≦Ｈ−２）の形式で、第ｉ層スイッチロケータアドレスが第ｉ層スイッチに割り当てられ、かつ、「エッジスイッチロケータアドレス．ホストアドレス」（ここで、エッジスイッチはホストに直接接続された第ｋ層スイッチであり、０≦ｋ≦Ｈ−２）の形式で、ホストロケータアドレスが各ホストに割り当てられる。
【００３５】
好ましくは、第ｉ層スイッチアドレスは、第（ｉ−１）層スイッチの各第ｉ層スイッチに接続された個々のポートのポート番号である。
【００３６】
好ましくは、ホストアドレスは、エッジスイッチの各ホストに接続された個々のポートのポート番号である。
【００３７】
本発明の第３の態様によれば、ファブリックマネージャであって、本発明によるアドレス指定装置と、各ホストのインターネットプロトコル（ＩＰ）アドレスおよびそのホストのすべてのホストロケータアドレス間のマッピングを保持するグローバルロケータアドレステーブルを格納するための記憶装置とを備えるファブリックマネージャを提供する。
【００３８】
好ましくは、ファブリックマネージャは、アドレス解決プロトコル（ＡＲＰ）要求を受信すると、宛先ホストのＩＰアドレスを索引としてグローバルロケータアドレステーブルを検索し、スケジューリングアルゴリズムに基づいて、宛先ホストのＩＰアドレスに対応する検索された１つ以上のホストロケータアドレスから１つのホストロケータアドレスを選択し、選択された１つのホストロケータアドレスを送信元ホストに返してＡＲＰアドレス解決を完了する、スケジューリング手段をさらに備える。
【００３９】
好ましくは、スケジューリング手段は、グローバルロケータアドレステーブルから宛先ホストのＩＰアドレスに対応するホストロケータアドレスが検索されなかった場合、ネットワークブロードキャストを実行して宛先ホストの１つ以上のホストロケータアドレスを取得し、スケジューリングアルゴリズムに基づいて、宛先ホストのＩＰアドレスに対応する取得された１つ以上のホストロケータアドレスから１つのホストロケータアドレスを選択し、選択された１つのホストロケータアドレスを送信元ホストに返してＡＲＰアドレス解決を完了する。
【００４０】
好ましくは、ファブリックマネージャは、スイッチが隣接スイッチの故障またはリンクの故障を検出した場合には、グローバルロケータアドレステーブル内の関連のホストロケータアドレスを無効化する障害処理手段をさらに備え、スケジューリング手段は宛先ホストのＩＰアドレスに対応するホストロケータアドレスを選択する際に、無効化されたホストロケータアドレスを選択しない。
【００４１】
本発明の第４の態様によれば、本発明によるアドレス指定装置を備えるスイッチを提供する。
【００４２】
本発明の第５の態様によれば、本発明によるアドレス指定方法によってアドレス指定されたスイッチアドレスとホストアドレスが適応される、データルーティング方法を提供する。当該データルーティング方法は、ルートスイッチ／第０層スイッチが、宛先ホストのホストロケータアドレスとして、「ルートスイッチロケータアドレス．第１層スイッチアドレス／ホストアドレス．＊」を含むデータパケットを「第１層スイッチアドレス／ホストアドレス」として付番されたポートへ送信するステップと、第ｉ層スイッチが、宛先ホストのホストロケータアドレスとして、「第ｉ層スイッチロケータアドレス．第（ｉ＋１）層スイッチアドレス／ホストアドレス．＊」を含むデータパケットを、「（ｉ＋１）層スイッチアドレス／ホストアドレス」として付番されたポート（ここで、１≦ｉ≦Ｈ−２）へ送信するステップと、第ｉ層スイッチが、宛先ホストのホストロケータアドレスとして、「ルートスイッチロケータアドレス．＊」を含むデータパケットを、「ルートスイッチロケータアドレス」のルートスイッチロケータアドレスを有するルートスイッチをルートとする第（ｉ−１）層スイッチ（ここで、１≦ｉ≦Ｈ−２）に接続されたポートに送信するステップとを備える。
【００４３】
本発明は、ファットツリートポロジ、Ｃｌｏｓトポロジ等の、データセンターによって採用される様々なトポロジに適応可能な新しいアドレス指定解決法を提供する。データパケットを転送するためのスイッチの転送テーブルには、ＭＡＣアドレスではなく、ロケータアドレスが格納される。ロケータアドレスは階層的なので、スイッチが保持する転送テーブルを小規模に維持することができる。トポロジ内に冗長パスが設けられている場合、スイッチおよびホストは複数のロケータアドレスに割り当てられる。複数のロケータアドレスは、それぞれ複数のパスがあることを示す。複数のパスからロードバランスを実現できるいくつかの適切なパスを選択することが可能となる。
【図面の簡単な説明】
【００４４】
本発明の上記および他の目的、特徴、利点は、本発明の実施例に関する以下の説明と添付図面とを参照することにより、明らかになるであろう。
【００４５】
【図１】スイッチが自己学習方式で転送テーブルを作成する場合を示す概略図である。
【図２】スイッチが、未知の宛先ＭＡＣアドレスを有するデータフレームを転送（ブロードキャスト）する場合を示す概略図である。
【図３】ＰｏｒｔＬａｎｄシステムのアーキテクチャの概略図である。
【図４】Ｃｌｏｓトポロジの概略図である。
【図５】本発明によるアドレス指定装置５００のブロック図である。
【図６】本発明によるアドレス指定装置６００のフローチャートである。
【図７】非特許文献３で提案されるファットツリートポロジを示す概略図である。
【図８】ネットワークトポロジ発見機能がファットツリートポロジに基づいて作成するツリーの例を示す。
【図９】ネットワークトポロジ発見機能がファットツリートポロジに基づいて作成するツリーの他の例を示す。
【図１０】ネットワークトポロジ発見機能がファットツリートポロジに基づいて作成するツリーの他の例を示す。
【図１１】ファットツリートポロジに基づくアドレス指定結果の一部を示す。
【図１２】Ｃｌｏｓトポロジに基づくアドレス指定結果の一部を示す。
【図１３】ファットツリートポロジにおけるデータパケットの転送を示す概略図である。
【図１４】本発明によるアドレス指定装置５００を備えるファブリックマネージャ１４００の一例のブロック図である。
【図１５】複数のパスのそれぞれに対応する複数のロケータアドレスを示す概略図である。
【００４６】
これらの図面においては、同一もしくは類似の要素またはステップは、同一もしくは類似の参照記号で識別されている。
【発明を実施するための形態】
【００４７】
以下では、図面を参照して本発明の実施例について詳述する。これにより、当業者には本発明の原理および実装は明らかとなるであろう。ただし、本発明はここで説明する特定の実施例に限定されない。さらに、明快で簡素な内容とするため、本発明に関連する一般的な要素の説明は省略している。
【００４８】
図５は、本発明によるアドレス指定装置５００のブロック図である。本発明によるアドレス指定装置５００は、図３に示すファブリックマネージャ３００や他の任意のスイッチに配置することができる。図５に示すように、本発明によるアドレス指定装置５００は、ツリー作成手段５１０と、ツリー選択手段５２０と、アドレス割り当て手段５３０とを備える。
【００４９】
ツリー作成手段５１０は、ネットワークトポロジ発見機能によって、各スイッチを順にルートとして全ホストを含むツリーを作成し、複数のツリーを取得する。トポロジは冗長パスを設けることができるので、各ツリーにスイッチのすべてを含める必要はない。また、１つのスイッチをルートとして、全ホストを含む複数のツリーが作成されることもある。この場合、ツリー作成手段５１０は、ツリー選択手段５２０の動作の前に、当該スイッチをルートとする複数のツリーから最低高さを有する任意の１つのツリーを、作成されたツリーとして選択することができる。あるいは、ツリー作成手段５１０がすべてのツリーを作成して記録しておき、ツリー選択手段５２０が選択を行うようにしてもよい。
【００５０】
ツリー選択手段５２０は、ツリー作成手段５１０によって作成された複数のツリーから最低高さを有するツリーを選択する。当該複数のツリーのうち最低高さを有するツリーが複数個ある場合には、ツリー選択手段５２０は、最低高さを有する複数個のツリーのすべてを選択する。ツリー選択手段５２０の動作によれば、同じ最低高さを有するツリーが複数個存在する場合には、トポロジは複数ルートのツリーとして構築される。
【００５１】
アドレス割り当て手段５３０は、ネットワーク内の各スイッチおよび各ホストにアドレスを割り当てる。
【００５２】
以下では、便宜上、ネットワーク内のスイッチの階層構造についてまず説明する。
【００５３】
各ツリーのルートノードにあるスイッチを「ルートスイッチ」と称する（「第０層スイッチ」とも称する）。第（ｉ−１）層スイッチに直接接続されたスイッチを「第ｉ層スイッチ」（１≦ｉ≦Ｈ−２、Ｈはツリーの高さ）と称する。ホストに直接接続されたスイッチを「エッジスイッチ」と称する（第ｋ層スイッチとも称し、０≦ｋ≦Ｈ−２である）。
【００５４】
最初に、各選択された最低高さを有するツリーについて、ツリーのルートにあるルートスイッチにルートスイッチロケータアドレスが割り当てられる。このルートスイッチは「第０層スイッチ」と称する。
【００５５】
続いて、ルートスイッチ（第０層スイッチ）に直接接続された第１層スイッチから開始して、各第ｉ層スイッチについて、ルートスイッチから第ｉ層スイッチまでのすべてのパスが検出され、各パスについて、「ルートスイッチロケータアドレス．第１層スイッチアドレス．・・・．第ｉ層スイッチアドレス」の形式で、第ｉ層スイッチロケータアドレスが第ｉ層スイッチに割り当てられる。ここで、第ｉ層スイッチアドレスは、第（ｉ−１）層スイッチの第ｉ層スイッチに接続された各ポートのポート番号である。
【００５６】
最後に、「エッジスイッチロケータアドレス．ホストアドレス」の形式で、ホストロケータアドレスが各ホストに割り当てられる。ここで、ホストアドレスは、エッジスイッチの各ホストに接続された各ポートのポート番号である。
【００５７】
図６は、本発明によるアドレス指定方法６００のフローチャートである。
【００５８】
ステップＳ６１０において、ツリー作成手段５１０は、ネットワークトポロジ発見機能によって、各スイッチを順にルートとして全ホストを含むツリーを作成し、複数のツリーを取得する。トポロジは冗長パスを設けることができるので、各ツリーにスイッチのすべてを含める必要はない。また、１つのスイッチをルートとして、全ホストを含む複数のツリーが作成されることもある。この場合、ツリー作成手段５１０は、ツリー選択手段５２０の動作の前に、当該スイッチをルートとする複数のツリーから最低高さを有する任意の１つのツリーを、作成されたツリーとして選択することができる。あるいは、ツリー作成手段５１０がすべてのツリーを作成して記録しておき、ツリー選択手段５２０が選択を行うようにしてもよい。
【００５９】
ステップＳ６２０において、ツリー選択手段５２０は、ツリー作成手段５１０によって作成された複数のツリーから最低高さを有するツリーを選択する。当該複数のツリーのうち最低高さを有するツリーが複数個ある場合には、ツリー選択手段５２０は、最低高さを有する複数個のツリーのすべてを選択する。ツリー選択手段５２０の動作によれば、同じ最低高さを有する（Ｒ）ツリーが複数個存在する場合には、トポロジは複数ルートのツリーとして構築される。複数ルートのツリーの高さはＨである。各ツリーのルートノードにあるスイッチを「ルートスイッチ」と称する（「第０層スイッチ」とも称する）。第（ｉ−１）層スイッチに直接接続されたスイッチを「第ｉ層スイッチ」（１≦ｉ≦Ｈ−２）と称する。ホストに直接接続されたスイッチを「エッジスイッチ」と称する（第ｋ層スイッチとも称し、０≦ｋ≦Ｈ−２である）。
【００６０】
ステップＳ６３０において、アドレス割り当て手段５３０は、各選択された最低高さＨを有するツリーについて、ツリーのルートにあるルートスイッチにルートスイッチロケータアドレスを割り当てる。このルートスイッチは「第０層スイッチ」とも称する。ツリーのルートノードには、例えばルートスイッチロケータアドレス「０」、「１」、・・・、「Ｒ−１」を順に割り当てることができる。
【００６１】
ステップＳ６４０において、アドレス割り当て手段５３０は、ルートスイッチ（第０層スイッチ）に直接接続された第１層スイッチから開始して、各第ｉ層スイッチについて、ルートスイッチから第ｉ層スイッチまでのすべてのパスを検出し、各パスについて、「ルートスイッチロケータアドレス．第１層スイッチアドレス．・・・．第ｉ層スイッチアドレス」の形式で、第ｉ層スイッチロケータアドレスを第ｉ層スイッチに割り当てる。ここで、第ｉ層スイッチアドレスは、第（ｉ−１）層スイッチの第ｉ層スイッチに接続された各ポートのポート番号である。
【００６２】
ステップＳ６５０において、アドレス割り当て手段５３０は、「エッジスイッチロケータアドレス．ホストアドレス」の形式で、ホストロケータアドレスを各ホストに割り当てる。ここで、ホストアドレスは、エッジスイッチの各ホストに接続された各ポートのポート番号である。
【００６３】
ロケータアドレス「ルートスイッチロケータアドレス．第１層スイッチアドレス．・・・．第ｉ層スイッチアドレス．・・・．エッジスイッチロケータアドレス．ホストアドレス」については、ロケータアドレスの各層は８ビットで示すことができる。そのため、トポロジ発見機能によって取得された複数ルートのツリーの高さＨが６未満の場合には、ロケータアドレスの長さが４８ビットのＭＡＣアドレス領域を超えることはない。
【００６４】
ロケータアドレスが全６層（４８ビット）に達しなかった場合、（アドレス割り当て手段５３０によって）無効なアドレスビットが「１」で示される。例えば、「０．１．２．３．２５５．２５５」は、ホストのロケータアドレスの形式は「ルートスイッチロケータアドレス．第１層アドレス．第２層アドレス．ホストアドレス」であり、その固有値は「０．１．２．３」であることを示す。煩雑化を避けるため、記述においては無効なアドレスビットは通常省略される。よって、「０．１．２．３」は「０．１．２．３．２５５．２５５」を表す。
【００６５】
「ルートスイッチロケータアドレス」のアドレス領域のサイズは、ルートスイッチ数によって決まる。８ビットは、最大２５５個のルートスイッチを表すことができる。通常、コア層のスイッチは１０Ｇポートを備えるスイッチである。ここで、コア層には、各々１２８ポートを有する２５５個のスイッチがあると想定する。したがって、この構成では、２５５＊１２８＊１０＝３２６，４００のホストにおいて１Ｇ通信をサポートすることが可能である。この数は大規模なデータセンターの要件を十分に満たすことができる。
【００６６】
「ルートスイッチロケータアドレス」だけでなく、「第１層アドレス」、「第２層アドレス」、・・・、「第ｎ層アドレス」、または「ホストアドレス」のアドレス領域のサイズも、スイッチのポート数によって異なる。８ビットは最大２５５ポートを表現できるので、既存のスイッチの要件を満たすには十分である。
【００６７】
一方、トポロジ発見機能によって取得された複数ルートのツリーの高さＨが６より大きい場合、ロケータアドレス「ルートスイッチロケータアドレス．第１層スイッチアドレス．・・・．第ｉ層スイッチアドレス．・・・．エッジスイッチロケータアドレス．ホストアドレス」を圧縮する必要がある。ある特定層の最大アドレス領域≦２Ｎ−１とすると、この層のビット数はＮビットに圧縮される（アドレス割り当て手段５３０によって実行される）。この場合、各層はもはや固定ビット長（８ビット）で示されないため、ファブリックマネージャ３００（図３）はトポロジ発見の完了後に、すべてのスイッチに各層のビット長を通知する。
【００６８】
本発明で提案されるアドレス指定の解決法は、データセンターによって採用される様々なトポロジに適応可能である。以下に、典型的なトポロジにおけるアドレス指定の例を示す。
【００６９】
図７は、非特許文献３で提案されるファットツリートポロジを示す概略図である。詳細については図３を参照すると分かるので、ここでは煩雑化を避けるため省略する。
【００７０】
図８に、ネットワークトポロジ発見機能がファットツリートポロジに基づいて作成するツリーの例を示す。
【００７１】
図８に示すように、ツリー作成手段５１０は、ネットワークトポロジ発見機能を使用し、スイッチＳ１をルートとして、全ホストを含むツリーを作成する（ステップＳ６１０）。ツリーの高さＨは４である。
【００７２】
図９に、ネットワークトポロジ発見機能がファットツリートポロジに基づいて作成するツリーの他の例を示す。
【００７３】
図９に示すように、ツリー作成手段５１０は、ネットワークトポロジ発見機能を使用し、スイッチＳ５をルートとして、全ホストを含む他のツリーを作成する（ステップＳ６１０）。ツリーの高さＨは５である。
【００７４】
図１０に、ネットワークトポロジ発見機能がファットツリートポロジに基づいて作成するツリーの他の例を示す。
【００７５】
図１０に示すように、ツリー作成手段５１０は、ネットワークトポロジ発見機能を使用し、スイッチＳ１３をルートとして、全ホストを含む他のツリーを作成する（ステップＳ６１０）。ツリーの高さＨは６である。
【００７６】
上記の動作によれば、ツリー作成手段５１０は、図７に示すファットツリートポロジに対し少なくとも２０個のツリーを作成することができる。
【００７７】
図１１に、ファットツリートポロジに基づくアドレス指定結果の一部を示す。
【００７８】
ツリー選択手段５２０は、ツリー作成手段５１０によって作成された少なくとも２０個のツリーから、最低高さ（Ｈ＝４）を有するツリーを選択する。最低高さＨ＝４のツリーは４個あり、それぞれスイッチＳ１、Ｓ２、Ｓ３、Ｓ４をルートとする（ステップＳ６２０）。
【００７９】
そのため、アドレス割り当て手段５３０は、ルートスイッチである４個のスイッチＳ１、Ｓ２、Ｓ３、Ｓ４にロケータアドレス「０」、「１」、「２」、「３」を割り当てる（ステップＳ６３０）。
【００８０】
スイッチＳ５〜Ｓ１２はルートスイッチに直接接続されているため、第１層スイッチである。第１層スイッチの各々について、ルートスイッチから第１層スイッチまでのパスは２つある。したがって、第１層スイッチの各々に２つのロケータアドレスが割り当てられる。例えば、スイッチＳ５の場合、１つのパスはＳ１→Ｓ５である。スイッチＳ５がルートスイッチＳ１のポート０に接続されているとすると、スイッチＳ５によってこのパスのために取得されるスイッチロケータアドレスは「０．０」である。ルートスイッチからスイッチＳ５までのもう一方のパスは、Ｓ２→Ｓ５である。スイッチＳ５がルートスイッチＳ２のポート０に接続されているとすると、スイッチＳ５によってこのパスのために取得されるスイッチロケータアドレスは「１．０」である。スイッチＳ１３〜Ｓ２０は第１層スイッチに直接接続されているので、第２層スイッチである。第２層スイッチの各々について、ルートスイッチから第２層スイッチまでのパスは４つある。そのため、第２層スイッチの各々には４個のロケータアドレスが割り当てられる。例えば、、スイッチＳ１３の４個のパスはＳ１→Ｓ５→Ｓ１３、Ｓ２→Ｓ５→Ｓ１３、Ｓ３→Ｓ６→Ｓ１３、Ｓ４→Ｓ６→Ｓ１３であり、対応する４個のスイッチロケータアドレスは「０．０．０」、「１．０．０」、「２．０．０」、「３．０．０」である（ステップＳ６３０）。
【００８１】
ホストはエッジスイッチ（第２層スイッチ）に直接接続される。エッジスイッチの各スイッチロケータアドレスに対応して、１つのホストロケータアドレスが各ホストに割り当てられる。そのため、図１１に示す各ホストは４個のホストロケータアドレスを有する。例えば、ホストＨ１はＳ１３のポート０に接続される。したがって、スイッチＳ１３の４個のスイッチロケータアドレス「０．０．０」、「１．０．０」、「２．０．０」、「３．０．０」に対応するホストＨ１のホストロケータアドレスは、「０．０．０．０」、「１．０．０．０」、「２．０．０．０」、「３．０．０．０」である（ステップＳ６４０）。
【００８２】
図１２に、Ｃｌｏｓトポロジに基づくアドレス指定結果の一部を示す。
【００８３】
図１２に示すＣｌｏｓトポロジの場合、ツリー作成手段５１０は少なくとも１０個のツリーを作成する可能性がある。
【００８４】
ツリー選択手段５２０は、ツリー作成手段５１０によって作成された少なくとも１０個のツリーから、最低高さ（Ｈ＝４）を有するツリーを選択する。最低高さＨ＝４のツリーは２個あり、それぞれスイッチＳ１、Ｓ２をルートとする（ステップＳ６２０）。
【００８５】
そのため、アドレス割り当て手段５３０は、ルートスイッチである２個のスイッチＳ１、Ｓ２にロケータアドレス「０」、「１」を割り当てる（ステップＳ６３０）。
【００８６】
スイッチＳ３〜Ｓ６はルートスイッチに直接接続されているので、第１層スイッチである。第１層スイッチの各々について、ルートスイッチから第１層スイッチまでのパスは２つある。したがって、第１層スイッチの各々に２つのロケータアドレスが割り当てられる。例えば、スイッチＳ３の場合、１つのパスはＳ１→Ｓ３である。スイッチＳ３がルートスイッチＳ１のポート０に接続されているとすると、スイッチＳ３によってこのパスのために取得されるスイッチロケータアドレスは「０．０」である。ルートスイッチからスイッチＳ３までのもう一方のパスは、Ｓ２→Ｓ３である。スイッチＳ３がルートスイッチＳ２のポート０に接続されているとすると、スイッチＳ３によってこのパスのために取得されるスイッチロケータアドレスは「１．０」である。スイッチＳ７〜Ｓ１０は第１層スイッチに直接接続されているので、第２層スイッチである。第２層スイッチの各々について、ルートスイッチから第２層スイッチまでのパスは４つある。そのため、第２層スイッチの各々には４個のロケータアドレスが割り当てられる。例えば、スイッチＳ７の４個のパスはＳ１→Ｓ３→Ｓ７、Ｓ２→Ｓ３→Ｓ７、Ｓ１→Ｓ４→Ｓ７、Ｓ２→Ｓ４→Ｓ７であり、４個のスイッチロケータアドレスは「０．０．０」、「１．０．０」、「０．１．０」、「１．１．０」である（ステップＳ６３０）。
【００８７】
ホストはエッジスイッチ（第２層スイッチ）に直接接続されている。エッジスイッチの各スイッチロケータアドレスに対応して、１つのホストロケータアドレスが各ホストに割り当てられる。そのため、図１２に示す各ホストは４個のホストロケータアドレスを有する。例えば、ホストＨ１はＳ７のポート０に接続される。したがって、スイッチＳ７の４個のスイッチロケータアドレス「０．０．０」、「１．０．０」、「０．１．０」、「１．１．０」に対応するホストＨ１のホストロケータアドレスは、「０．０．０．０」、「１．０．０．０」、「０．１．０．０」、「１．１．０．０」である（ステップＳ６４０）。
【００８８】
データパケットを転送するためのスイッチの転送テーブルには、ＭＡＣアドレスではなく、ロケータアドレスが格納される。図１３は、ファットツリートポロジにおけるデータパケットの転送を示す概略図である。各層のスイッチの転送テーブルは、以下のとおりである。
・ルートスイッチ：
セルフロケータ．ポート．＊⇔ポート「ポート」
ここで、「セルフロケータ」はルートスイッチ自体のルートスイッチロケータアドレスを表し、「ポート」はルートスイッチロケータアドレスの後に位置する次のアドレスフィールドを表す。
例えば、ルートスイッチＳ１の「セルフロケータ」は「０」である。そのポート０はＳ５に接続されており、Ｓ５に割り当てられている第１層アドレスも「０」である。そのため、宛先ロケータアドレス「０．０．＊」を有するデータパケットはポート０に送信される。同様に、宛先ロケータアドレス「０．１．＊」を有するデータパケットはポート１に送信される。
・第ｉ層スイッチ：
セルフロケータ．ポート．＊⇔ポート「ポート」
親のルート．＊⇔第（ｉ−１）層スイッチに接続されたポート
ここで、「セルフロケータ」は第ｉ層スイッチ自体の第ｉ層スイッチロケータアドレスを表し、「ポート」は第ｉ層スイッチロケータアドレスの後に位置する次のアドレスフィールドを表し、「親のルート」は第ｉ層スイッチに接続される第（ｉ−１）層スイッチのルートスイッチのルートスイッチロケータアドレスを表す。
例えば、スイッチＳ５の「セルフロケータ」は「０．０」および「１．０」である。そのポート０はＳ１３に接続されており、Ｓ１３に割り当てられている第２層アドレスも「０」である。そのため、宛先ロケータアドレス「セルフロケータ．０．＊」を有するデータパケットはポート０に送信される（すなわち、“０．０．０．＊” ⇔ポート０、“１．０．０．＊” ⇔ポート０）。同様に、宛先ロケータアドレス「セルフロケータ１．＊」を有するデータパケットはポート１に送信される（すなわち、“０．０．１．＊” ⇔ポート１、“１．０．１．＊” ⇔ポート１）。スイッチＳ５のポート２および３はアップリンクポートであり、第（ｉ−１）層スイッチに接続されている。スイッチＳ５のポート２および３に接続されている第（ｉ−１）層スイッチを、スイッチＳ５の親スイッチと称する。したがって、スイッチＳ５は２個の親スイッチＳ１およびＳ２を有する。スイッチＳ２はスイッチＳ５のポート２に接続されているとすると、スイッチＳ２のルートノードはＳ２自体（ルートスイッチロケータアドレスは「１」（親のルート））である。したがって、対応する転送テーブル項目は「１．＊」⇔ポート２である。同様に、スイッチＳ１はスイッチＳ５のポート３に接続されているとすると、スイッチＳ１のルートノードはＳ１自体（ルートスイッチロケータアドレスは「０」（親のルート））である。したがって、対応する転送テーブル項目は「０．＊」⇔ポート３である。
別の例を挙げると、スイッチＳ１３の「セルフロケータ」は「０．０．０」、「１．０．０」、「２．０．０」、「３．０．０」である。そのポート０はホストＨ１に接続されており、Ｈ１に割り当てられているホストロケータアドレスも「０」である。そのため、宛先ロケータアドレス「セルフロケータ．０．＊」を有するデータパケットはポート０に送信される（すなわち、「０．０．０．０．＊」⇔ポート０、「１．０．０．０．＊」⇔ポート０、「２．０．０．０．＊」⇔ポート０、「３．０．０．０．＊」⇔ポート０）。同様に、宛先ロケータアドレス「セルフロケータ１．＊」を有するデータパケットはポート１に送信される（すなわち、「０．０．０．１．＊」⇔ポート１、「１．０．０．１．＊」⇔ポート１、「２．０．０．１．＊」⇔ポート１、「３．０．０．１．＊」⇔ポート１）。スイッチＳ１３のポート２および３はアップリンクポートであり、第（ｉ−１）層スイッチに接続されている。スイッチＳ１３のポート２および３に接続されている第（ｉ−１）層スイッチを、スイッチＳ１３の親スイッチと称する。したがって、スイッチＳ１３は２個の親スイッチＳ５およびＳ６を有する。スイッチＳ６はスイッチＳ１３のポート２に接続されているとすると、スイッチＳ６のルートノードはルートスイッチＳ３（ルートスイッチロケータアドレスは「２」（親のルート））またはルートスイッチＳ４（ルートスイッチロケータアドレスは「３」（親のルート））である。したがって、対応する転送テーブル項目は「２．＊」⇔ポート２と「３．＊」⇔ポート２である。同様に、スイッチＳ５はスイッチＳ１３のポート３に接続されているとすると、スイッチＳ５のルートノードはルートスイッチＳ１（ルートスイッチロケータアドレスは「０」（親のルート））またはルートスイッチＳ２（ルートスイッチロケータアドレスは「１」（親のルート））である。したがって、対応する転送テーブル項目は「０．＊」⇔ポート３と「１．＊」⇔ポート３である。
【００８９】
トポロジ内に冗長パスが設けられている場合、スイッチおよびホストは複数のロケータアドレスに割り当てられる。複数のロケータアドレスは、それぞれ複数のパスがあることを示す。ロードバランスのために、複数のパスからいくつかの適切なパスが選択されることがある。
【００９０】
図１４は、本発明によるアドレス指定装置５００を備えるファブリックマネージャ１４００の一例のブロック図である。図１５は、複数のパスのそれぞれに対応する複数のロケータアドレスを示す概略図である。
【００９１】
図１４に示すように、本発明によるアドレス指定装置５００を備えるファブリックマネージャ１４００は、記憶装置１４１０と、スケジューリング手段１４２０と、障害処理手段１４３０とをさらに備える。
【００９２】
記憶装置１４１０は、各ホストのインターネットプロトコル（ＩＰ）アドレスと、アドレス指定装置５００によって作成された当該ホストのすべてのホストロケータアドレスとの間のマッピングを保持するグローバルロケータアドレステーブルを格納する。
【００９３】
スケジューリング手段１４２０は、アドレス解決プロトコル（ＡＲＰ）要求が受信されると、宛先ホストのＩＰアドレスを索引としてグローバルロケータアドレステーブルを検索し、スケジューリングアルゴリズムに基づいて、宛先ホストのＩＰアドレスに対応する検索された１つ以上のホストロケータアドレスから１つのホストロケータアドレスを選択し、選択された１つのホストロケータアドレスを送信元ホストに返してＡＲＰアドレス解決を完了する。グローバルロケータアドレステーブルから宛先ホストのＩＰアドレスに対応するホストロケータアドレスが検索されなかった場合には、スケジューリング手段１４２０は、ネットワークブロードキャストを実行して宛先ホストの１つ以上のホストロケータアドレスを取得し（宛先ホストの１つ以上のホストロケータアドレスとＩＰアドレスとのマッピングは、グローバルロケータテーブルに格納してもよい）、スケジューリングアルゴリズムに基づいて、宛先ホストのＩＰアドレスに対応する取得された１つ以上のホストロケータアドレスから１つのホストロケータアドレスを選択し、選択された１つのホストロケータアドレスを送信元ホストに返してＡＲＰアドレス解決を完了する。
【００９４】
スイッチが隣接スイッチの故障またはリンクの故障を検出した場合には、障害処理手段１４３０が、グローバルロケータアドレス（＊テーブル？）内の関連のホストロケータアドレスを無効化する。スケジューリング手段１４２０は、宛先ホストのＩＰアドレスに対応するホストロケータアドレスを選択する際に、無効化されたホストロケータアドレスを選択しない。
【００９５】
図１５に示すように、ホストＨ１は送信元ホストであり、ホストＨ５は宛先ホストである。ホストＨ５には４個のロケータアドレスが付与されている。したがって、やはり図１５に示されるように、ホストＨ１からホストＨ５までのパスは４つある。グローバルロケータアドレステーブル（記憶装置１４１０に格納されている）には、全ホストのすべてのホストロケータアドレスが保持されている。ファブリックマネージャがアドレス解決プロトコル（ＡＲＰ）要求を受信すると、スケジューリング手段１４２０は、ホストロケータアドレスから１個のホストロケータアドレスを選択することで、それに応答することがある。ホストロケータアドレスを選択することは、複数のパスから１つのパスを選択することに相当する。ロードバランスのために、複数のパスからいくつかの適切なパスが選択されることがある。この選択方法としては、ランダム、ラウンドロビン等のスケジューリングアルゴリズムを使用できる。ファブリックマネージャは、ＡＲＰアドレス解決のために、グローバルロケータアドレステーブルを格納する。ファブリックマネージャはＡＲＰ要求が受信されると、グローバルロケータアドレステーブルを検索して、宛先ホストのＩＰアドレスに対応するホストロケータアドレスを見つける。宛先ホストのＩＰアドレスに対応する１つ以上のホストロケータアドレスが見つかった場合には、スケジューリングアルゴリズムに基づいて、検索された１つ以上のホストロケータアドレスから１つのホストロケータアドレスが選択され、選択された１つのホストロケータアドレスが送信元ホストに返されて、ＡＲＰアドレス解決が完了する。グローバルロケータアドレステーブルから宛先ホストのＩＰアドレスに対応するホストロケータアドレスが検索されなかった場合には、ファブリックマネージャは、ネットワークブロードキャストを実行して宛先ホストの１つ以上のホストロケータアドレスを取得し、スケジューリングアルゴリズムに基づいて、取得された１つ以上のホストロケータアドレスから１つのホストロケータアドレスを選択し、選択された１つのホストロケータアドレスを送信元ホストに返してＡＲＰアドレス解決を完了する。ほとんどの場合、ファブリックマネージャが関与するときには、ネットワーク全体に対するブロードキャストは不要である。
【００９６】
加えて、データセンターは数万台のサーバとスイッチを備えており、複数の異なるアプリケーションを同時にサポートしているため、データセンターネットワークの耐故障性に対する要件は厳しい。本発明は、耐故障性の容易な実現方法として、１つのスイッチに対して１つ以上のスイッチロケータアドレスを使用している。隣接スイッチの動作状態を検出するため、スイッチ間でキープアライブメッセージが定期的に交換されている（これは、スイッチ内の障害検出手段によって行うことができる）。スイッチまたはリンクに障害が発生した場合には、隣接スイッチ内の障害検出手段がこの障害を検出し、ファブリックマネージャに報告する。その後、障害処理手段１４３０が、グローバルロケータアドレステーブル内の関連のホストロケータアドレスを無効化する。スケジューリング手段１４２０は、以降のＡＲＰ要求を処理する際に無効なホストロケータアドレスを避け、有効なホストロケータアドレスを選択してＡＲＰアドレス解決を完了する。
【００９７】
本発明の他の構成としては、方法実施例のステップおよび動作を実行するソフトウェアプログラムが挙げられる。以下ではまずその概要を述べ、次に詳細に説明する。具体的には、１つの実施例は、符号化されたコンピュータプログラム論理を格納するコンピュータ可読媒体で構成されるコンピュータプログラム製品である。コンピュータプログラム論理は、コンピュータ装置上で実行されると、上記の３Ｄ位置決め解決法を提供するために必要な動作を提供する。コンピュータプログラム論理は、それがコンピューティングシステムの少なくとも１つのプロセッサ上で実行されたときに、当該少なくとも１つのプロセッサが本発明の実施例の動作（方法）を実行することを可能にする。本発明のこうした構成は、典型的には、光媒体（例：ＣＤ−ＲＯＭ）、ソフトディスク、ハードディスク等のコンピュータ可読媒体、１つ以上のＲＯＭ、ＲＡＭ、もしくはＰＲＯＭチップに格納されたファームウェアもしくはマイクロコード等のその他の媒体、特定用途向け集積回路（ＡＳＩＣ）、または単一もしくは複数モジュール上のダウンロード可能なソフトウェアイメージおよび共有データベース等において提供または符号化されるソフトウェア、コード、その他のデータ構造として提供される。ソフトウェア、ハードウェア等の構成は、コンピューティング装置上にインストールされることにより、コンピューティング装置内の１つ以上のプロセッサを介して、本発明の実施例による技法を実行することができる。また、本発明のノードおよびホストは、ソフトウェアプロセスを、例えば他のエンティティ内の一連のデータ通信装置やコンピューティング装置と共に稼働させることによっても実現することができる。本発明のノードおよびホストはさらに、複数のデータ通信装置の複数のソフトウェアプロセス間に分散させたり、一連の小型専用コンピュータ上で稼働するすべてのソフトウェアプロセス、あるいは単一のコンピュータ上で稼働するすべてのソフトウェアプロセスに分散させることも可能である。
【００９８】
本発明の実施例は、厳密には、ソフトウェアプログラム、１台のデータ処理装置上のソフトウェアおよびハードウェア、独立したソフトウェア、または独立した回路として実装できることに留意されたい。
【００９９】
以上、実施例に関連して本発明を説明してきたが、本発明はその精神と範囲から逸脱することなく様々な変更、置換、追加を行うことが当業者によって可能なことは理解されるであろう。したがって、本発明の範囲は上記の特定の実施例に限定されず、以下の請求項によって限定される。
【０１００】
さらに、上記実施形態の一部又は全部は、以下の付記のようにも記載されうるが、これに限定されない。
【０１０１】
（付記１）
複数のツリーを取得するために、ネットワークトポロジ発見機能を使用して、各スイッチを順にルートとして、全ホストを含むツリーを作成するツリー作成手段と、
前記ツリー作成手段によって作成された複数のツリーから最低高さを有するツリーを選択するツリー選択手段と、
前記ツリー選択手段によって選択された最低高さを有する各ツリーに関し、ネットワーク内の各スイッチおよび各ホストにアドレスを割り当てるアドレス割り当て手段と
を備えることを特徴とするアドレス指定装置。
【０１０２】
（付記２）
１つのスイッチをルートとして、全ホストを含む複数のツリーが作成された場合、前記ツリー作成手段は、当該スイッチをルートとする複数のツリーのうち最低高さを有するツリーの１つを、作成されたツリーとして選択することを特徴とする付記１に記載のアドレス指定装置。
【０１０３】
（付記３）
１つのスイッチをルートとして、全ホストを含む複数のツリーが作成された場合、前記ツリー作成手段は、当該複数のツリーのすべてを、作成されたツリーとして記録することを特徴とする付記１に記載のアドレス指定装置。
【０１０４】
（付記４）
前記複数のツリーのうち最低高さを有するツリーが複数個ある場合、前記ツリー選択手段は、最低高さを有する当該複数個のツリーのすべてを選択することを特徴とする付記１から付記３の何れかに記載のアドレス指定装置。
【０１０５】
（付記５）
前記ツリー選択手段によって選択された最低高さＨを有する各ツリーについて、前記アドレス割り当て手段は、
ルートスイッチロケータアドレスを、ツリーのルートに位置するルートスイッチ（第０層スイッチ）に割り当て、
前記ルートスイッチに直接接続された第１層スイッチから開始して、第（ｉ−１）層スイッチに直接接続された第ｉ層スイッチの各々について、ルートスイッチから第ｉ層スイッチまでのすべてのパスを検出し、各パスについて、「ルートスイッチロケータアドレス．第１層スイッチアドレス．・・・．第ｉ層スイッチアドレス」（ここで、１≦ｉ≦Ｈ−２）の形式で、第ｉ層スイッチロケータアドレスを第ｉ層スイッチに割り当て、
「エッジスイッチロケータアドレス．ホストアドレス」（ここで、エッジスイッチはホストに直接接続された第ｋ層スイッチであり、０≦ｋ≦Ｈ−２）の形式で、ホストロケータアドレスを各ホストに割り当てる
ことを特徴とする付記１から付記４の何れかに記載のアドレス指定装置。
【０１０６】
（付記６）
前記第ｉ層スイッチアドレスは、第（ｉ−１）層スイッチの各第ｉ層スイッチに接続された個々のポートのポート番号であることを特徴とする付記５に記載のアドレス指定装置。
【０１０７】
（付記７）
前記ホストアドレスは、エッジスイッチの各ホストに接続された個々のポートのポート番号であることを特徴とする付記５又は付記６に記載のアドレス指定装置。
【０１０８】
（付記８）
複数のツリーを取得するために、ネットワークトポロジ発見機能を使用して、各スイッチを順にルートとして、全ホストを含むツリーを作成するステップと、
作成された複数のツリーから最低高さを有するツリーを選択するステップと、
選択された最低高さを有する各ツリーに関し、ネットワーク内の各スイッチおよび各ホストにアドレスを割り当てるステップと
を備えることを特徴とするアドレス指定方法。
【０１０９】
（付記９）
１つのスイッチをルートとして、全ホストを含む複数のツリーが作成された場合、当該スイッチをルートとする複数のツリーのうち最低高さを有するツリーの１つが、作成されたツリーとして選択されることを特徴とする付記８に記載のアドレス指定方法。
【０１１０】
（付記１０）
１つのスイッチをルートとして、全ホストを含む複数のツリーが作成された場合、当該複数のツリーのすべてが、作成されたツリーとして記録されることを特徴とする付記８に記載のアドレス指定方法。
【０１１１】
（付記１１）
当該複数のツリーのうち最低高さを有するツリーが複数個ある場合、最低高さを有する当該複数個のツリーのすべてが選択されることを特徴とする付記８から付記１０の何れか１項に記載のアドレス指定方法。
【０１１２】
（付記１２）
最低高さＨを有する各選択されたツリーについて、
ルートスイッチロケータアドレスが、ツリーのルートに位置するルートスイッチ（「第０層スイッチ」とも称する）に割り当てられ、
ルートスイッチに直接接続された第１層スイッチから開始して、第（ｉ−１）層スイッチに直接接続された第ｉ層スイッチの各々について、ルートスイッチから第ｉ層スイッチまでのすべてのパスが検出され、各パスについて、「ルートスイッチロケータアドレス．第１層スイッチアドレス．・・・．第ｉ層スイッチアドレス」（ここで１≦ｉ≦Ｈ−２）の形式で、第ｉ層スイッチロケータアドレスが第ｉ層スイッチに割り当てられ、
「エッジスイッチロケータアドレス．ホストアドレス」（ここで、エッジスイッチはホストに直接接続された第ｋ層スイッチであり、０≦ｋ≦Ｈ−２）の形式で、ホストロケータアドレスが各ホストに割り当てられる
ことを特徴とする付記８から付記１１の何れか１項に記載のアドレス指定方法。
【０１１３】
（付記１３）
前記第ｉ層スイッチアドレスは、第（ｉ−１）層スイッチの各第ｉ層スイッチに接続された個々のポートのポート番号であることを特徴とする付記１２に記載のアドレス指定方法。
【０１１４】
（付記１４）
前記ホストアドレスは、エッジスイッチの各ホストに接続された個々のポートのポート番号であることを特徴とする付記１２又は付記１３に記載のアドレス指定方法。
【０１１５】
（付記１５）
付記１から付記７の何れかに記載のアドレス指定装置と、
各ホストのインターネットプロトコル（ＩＰ）アドレスおよびそのホストのすべてのホストロケータアドレス間のマッピングを保持するグローバルロケータアドレステーブルを格納するための記憶装置と
を備えることを特徴とするファブリックマネージャ。
【０１１６】
（付記１６）
アドレス解決プロトコル（ＡＲＰ）要求を受信すると、宛先ホストのＩＰアドレスを索引としてグローバルロケータアドレステーブルを検索し、スケジューリングアルゴリズムに基づいて、宛先ホストのＩＰアドレスに対応する検索された１つ以上のホストロケータアドレスから１つのホストロケータアドレスを選択し、選択された１つのホストロケータアドレスを送信元ホストに返してＡＲＰアドレス解決を完了する、スケジューリング手段を
さらに備えることを特徴とする付記１５に記載のファブリックマネージャ。
【０１１７】
（付記１７）
前記スケジューリング手段は、グローバルロケータアドレステーブルから宛先ホストのＩＰアドレスに対応するホストロケータアドレスが検索されなかった場合には、ネットワークブロードキャストを実行して宛先ホストの１つ以上のホストロケータアドレスを取得し、スケジューリングアルゴリズムに基づいて、宛先ホストのＩＰアドレスに対応する取得された１つ以上のホストロケータアドレスから１つのホストロケータアドレスを選択し、選択された１つのホストロケータアドレスを送信元ホストに返してＡＲＰアドレス解決を完了することを特徴とする付記１６に記載のファブリックマネージャ。
【０１１８】
（付記１８）
スイッチが隣接スイッチの故障またはリンクの故障を検出した場合、グローバルロケータアドレステーブル内の関連のホストロケータアドレスを無効化する障害処理手段をさらに備え、
前記スケジューリング手段は、宛先ホストのＩＰアドレスに対応するホストロケータアドレスを選択する際に、前記無効化されたホストロケータアドレスを選択しないことを特徴とする付記１６又は付記１７に記載のファブリックマネージャ。
【０１１９】
（付記１９）
付記１から付記７の何れかに記載のアドレス指定装置を備えることを特徴とするスイッチ。
【０１２０】
（付記２０）
付記１４に記載のアドレス指定方法によってアドレス指定されたスイッチアドレスとホストアドレスが適応される、データルーティング方法であって、
ルートスイッチ／第０層スイッチが、宛先ホストのホストロケータアドレスとして、「ルートスイッチロケータアドレス．第１層スイッチアドレス／ホストアドレス．＊」を含むデータパケットを「第１層スイッチアドレス／ホストアドレス」として付番されたポートへ送信するステップと、
第ｉ層スイッチが、宛先ホストのホストロケータアドレスとして、「第ｉ層スイッチロケータアドレス．第（ｉ＋１）層スイッチアドレス／ホストアドレス．＊」を含むデータパケットを、「（ｉ＋１）層スイッチアドレス／ホストアドレス」として付番されたポート（ここで、１≦ｉ≦Ｈ−２）へ送信するステップと、
第ｉ層スイッチが、宛先ホストのホストロケータアドレスとして、「ルートスイッチロケータアドレス．＊」を含むデータパケットを、「ルートスイッチロケータアドレス」のルートスイッチロケータアドレスを有するルートスイッチをルートとする第（ｉ−１）層スイッチ（ここで、１≦ｉ≦Ｈ−２）に接続されたポートに送信するステップと
を備えることを特徴とするデータルーティング方法。
【符号の説明】
【０１２１】
５００：アドレス指定装置
５１０：ツリー作成手段
５２０：ツリー選択手段
５３０：アドレス割り当て手段
６００：アドレス指定方法
１４００：ファブリックマネージャ
１４１０：記憶装置
１４２０：スケジューリング手段
１４３０：障害処理手段
【技術分野】
【０００１】
本発明は、データセンターネットワークに関し、特に、データセンターで採用される様々なトポロジに適応可能な、データセンターネットワーク用のアドレス指定方法、アドレス指定装置、ファブリックマネージャ、スイッチ、およびデータルーティング方法に関する。本発明は、転送テーブルの短縮を目的としたロケータアドレスの集約と、ネットワークのロードバランスとを実現することができる。
【背景技術】
【０００２】
クラウドサービスの普及により、数万〜数十万台のサーバを備えるデータセンターの創設が加速している。また、データセンターは複数の異なるアプリケーションを同時にサポートしており、それには、データセンター内のサーバ間における帯域集約型の全対全通信を必要とするものも含まれる。こうしたアプリケーションの大規模化と発達により、データセンターのネットワークファブリックに様々な課題が生じている。
【０００３】
データセンターネットワークの目的を達成するためには、多数のデータセンターサーバを相互接続し、効率的で耐故障性を有するルーティングおよび転送サービスを高レベルのアプリケーションに提供する必要がある。データセンターネットワークファブリックの主な選択肢としては、レイヤ２ネットワークとレイヤ３ネットワークの２つが挙げられる。
・レイヤ２ネットワークにおいては、データセンターは単一のＥｔｈｅｒｎｅｔとみなされる。Ｅｔｈｅｒｎｅｔでは、ネットワーク管理は容易であるが（プラグアンドプレイ、シームレスな仮想マシンマイグレーション等）、数万台のサーバを含むネットワークへの拡張は不可能である。
・レイヤ３方式では、拡張性の問題は克服できるが、Ｅｔｈｅｒｎｅｔの単純性が犠牲にされているため、管理負担が大きい。
【０００４】
Ｅｔｈｅｒｎｅｔの拡張性の問題を解決して、「プラグアンドプレイ」と大規模データセンターネットワークの両方をサポートすることを目指して、研究者によって新しい方法およびシステムが提案されている。
【０００５】
Ｅｔｈｅｒｎｅｔは、現在広く使用されているコモンＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）技術である。Ｅｔｈｅｒｎｅｔはネットワーク内のノードをＭＡＣアドレスで識別する。ＩＰアドレスの階層構造とは異なり、ＭＡＣアドレスはフラット構造であり、全世界において一意である。宛先ＭＡＣアドレスから送信ポートへのマッピングレコードは、スイッチ内の転送テーブルで保持される。
【０００６】
図１は、スイッチが自己学習方式で転送テーブルを作成する場合を示す概略図である。データフレームがスイッチに着信すると、スイッチはデータフレームの送信元ＭＡＣアドレスをチェックし、送信元ＭＡＣアドレスとデータフレームが入力されるポート間のマッピングを転送テーブルに格納する。自己学習メカニズムとＭＡＣアドレスの使用により、ネットワーク管理は容易になり、スイッチは「プラグアンドプレイ」の機能を獲得する。
【０００７】
しかし、以下の理由により、Ｅｔｈｅｒｎｅｔは依然として数万台のサーバを備えるネットワークに拡張することはできない。第１に、ＭＡＣアドレスは階層的ではないので、複数のＭＡＣアドレスを１つに集約することができない。宛先ＭＡＣアドレスと送信ポート間のマッピングレコードはスイッチの転送テーブルに格納されるため、ネットワーク全体の全ホストのＭＡＣアドレスが、各スイッチの転送テーブルに格納されなければならない。ネットワーク内のホスト数は、スイッチのバッファサイズによって制限される。第２に、図２に示すように、未知の宛先ＭＡＣアドレスを有するデータフレームについては（宛先ＭＡＣアドレスは転送テーブルに格納されない）、スイッチはそれをデータフレームが着信したポートを除くすべてのポートへ送信（ブロードキャスト）する。加えて、一部の基本的なネットワークサービス（アドレス解決プロトコル、動的ホスト構成プロトコル等）はブロードキャストによって実行される。Ｅｔｈｅｒｎｅｔは、このブロードキャストメカニズムによっても、大規模ネットワークへの拡張を制限される。最後に、Ｅｔｈｅｒｎｅｔはスパニングツリープロトコル（ＳＴＰ）を使用してループを回避するが、単一のツリーに沿って転送するためルーティングが非効率的であり、リンクの負荷バランスも悪化する。
【０００８】
そのため、データセンターネットワークを大規模ＬＡＮとして構築することはできない。１つの解決法は、レイヤ２構成とレイヤ３構成を混在させることである。これは、データセンターを、ＩＰルートによって接続された複数のＬＡＮとして構築することを意味する。各ＬＡＮは数十〜数百のマシンから成り、１つのＩＰサブネットを形成する。レイヤ２構成とレイヤ３構成を混在させることで、拡張性の問題は克服できるが、Ｅｔｈｅｒｎｅｔの単純性が犠牲にされるため、管理負担は依然として重い。本発明の目的は、Ｅｔｈｅｒｎｅｔの拡張性の問題を解決して、「プラグアンドプレイ」と大規模データセンターネットワークの両方をサポートすることである。
【０００９】
非特許文献１は、データセンターネットワークのためのレイヤ２アドレス指定プロトコル、ルーティングプロトコル、および転送プロトコルをセットにした、ＰｏｒｔＬａｎｄプロトコルを提案している。このプロトコルでは、疑似ＭＡＣ（ＰＭＡＣ）アドレスをネットワーク内のすべてのホストに割り当てることにより、トポロジ内のホストの位置が符号化される。ＰＭＡＣアドレスを使用すると、少ないスイッチステートで効率的に転送することができる。以下では、ＰｏｒｔＬａｎｄシステムについて詳細に説明する。
【００１０】
図３に、ＰｏｒｔＬａｎｄシステムのアーキテクチャの概略図を示す。
【００１１】
ＰｏｒｔＬａｎｄシステムにおいては、各エンドホストに、ＰＭＡＣが割り当てられ（図３の例では、ＭＡＣアドレスが「００．１９．Ｂ９．ＦＡ．８８．Ｅ２」、ＩＰアドレスが「１０．５．１．２」のエンドホストにＰＭＡＣ「００．００．０１．０２．００．０１」が割り当てられている）、これによりトポロジ内のエンドホストの位置が符号化されている。データパケットを転送するための転送テーブルには、実際のＭＡＣアドレスではなく、ＰＭＡＣアドレスが格納される。ＰＭＡＣアドレスは階層的なので、スイッチが保持する転送テーブルを小規模に維持することができる。加えて、ＰｏｒｔＬａｎｄシステムは、ネットワークの構成情報と状態を保持する、集中型のファブリックマネージャ（ＦＭ）３００を備えている。ＦＭ３００は、従来のＥｔｈｅｒｎｅｔの純粋なブロードキャストメカニズムとは異なり、ＡＲＰの解決を容易にし、耐故障性能を向上させる。
【００１２】
ＰｏｒｔＬａｎｄプロトコルは、ファットツリートポロジに基づく、アドレス指定プロトコル、ルーティングプロトコル、および転送プロトコルのセットである（非特許文献３参照）。ファットツリートポロジでは、スイッチはエッジ層、集約層、コア層という３つの層に分割される。各層のすべてのスイッチは同一であり、それぞれｋ個のポートを備える。図３のファットツリートポロジでは、ｋ＝４である。このファットツリーは、ｋ個の個別ポッドに分割されている。図３の点線の枠で示すエッジ層と集約層には、ｋ個のスイッチから成るポッドが１つの枠で囲まれている。一般に、ファットツリーは、ｋ個のポートを備える５ｋ２／４個のスイッチを使用して、ｋ３／４個のホストの間でノンブロッキング通信をサポートすることができる。
【００１３】
エッジスイッチは、各４８ビットＰＭＡＣアドレスを、直接接続されたすべてのホストにそれぞれ割り当てる。ＰＭＡＣアドレスは階層的であり、トポロジ内のホストの位置を符号化する。ＰＭＡＣアドレスは、以下の形式である。
ポッド．位置．ポート．仮想マシンＩＤ
【００１４】
ここで、
「ポッド」は１６ビットの長さで、エッジスイッチのポッド番号を表す。
「位置」は８ビットの長さで、ポッド内のエッジスイッチの位置を示す。
「ポート」は８ビットの長さで、ホストが接続されるエッジスイッチのポート番号を表す。
「仮想マシンＩＤ」は１６ビットの長さで、物理マシン上の仮想マシンの番号を示す（同じ物理マシン上に複数の仮想マシンが存在できる）。
【００１５】
図３の例において、左から３番目のホストのＰＭＡＣアドレスは「００．００．０１．０２．００．０１」であり、ここで、
ポッド「００．００」はポッド０を示す。
位置「０１」はポッド０内の位置０１を表す。
ポート「０２」は、エンドホストはエッジスイッチのポート０２に接続されていることを示す。
仮想マシンＩＤ「００．０１」は、エンドホスト内の仮想マシンの番号は１であることを示す。
【００１６】
図３に示すように、データパケットを転送するための転送テーブルには、実際のＭＡＣアドレスではなくＰＭＡＣアドレスが格納される（図３の右側のテーブル参照）。ＭＡＣアドレスのフラット構造とは異なり、ＰＭＡＣアドレスは階層的なので、スイッチに保持する転送テーブルは小さくてもよい。各層のスイッチの転送テーブルは、以下のとおりである。
・コアスイッチ：ポッド．＊⇔送信ポート
この例では、図３の右端にあるコアスイッチのポート０および１は、それぞれポッド０および１に接続されている。したがって、宛先ＭＡＣアドレスが「００．００．＊」のすべてのデータパケットはポート０に送られる。これは、ポッド０を宛先とするすべてのデータパケットはポート０に送信されることを意味する。同様に、ポッド１を宛先とするすべてのデータパケットはポート１に送信されることを意味する。
・集約スイッチ：ポッド．位置．＊⇔送信ポート
例えば、図３の右端にある集約スイッチは、ポッド３、すなわち００．１１に属する。したがって、宛先ＭＡＣアドレスが「００．１１．＊」のすべてのデータパケットはこのポッド３に送られ（すなわち、宛先ＭＡＣアドレスが「００．１１．００．＊」のすべてのデータパケットは位置「０」（ポート０）のエッジスイッチに送られ）、宛先ＭＡＣアドレスが「００．１１．０１．＊」のすべてのデータパケットは位置「１」（すなわち、ポート１）のエッジスイッチに送られる。他の宛先ＭＡＣアドレスを有するデータパケットは、ポート２またはポート３を介して、アップリンクデータパケットとして他のポッドに送られる。
・エッジスイッチ：ポッド．位置．ポート．＊⇔送信ポート
この例では、図３の右端にあるエッジスイッチは、ポッド３、位置１，すなわち００．１１．０１に属する。このスイッチには２つのホストが直接接続されており、宛先ＭＡＣアドレスが「００．１１．０１．００．＊」のすべてのデータパケットはポート０に送られ、宛先ＭＡＣアドレスが「００．１１．０１．０１．＊」のすべてのデータパケットはポート１に送られる。他の宛先ＭＡＣアドレスを有するデータパケットは、ポート２またはポート３を介して、アップリンクデータパケットとして他のホストに送られる。
【００１７】
ＰｏｒｔＬａｎｄプロトコルは、データセンターネットワークのためのレイヤ２アドレス指定プロトコル、ルーティングプロトコル、および転送プロトコルのセットで構成される。ただし、ＰｏｒｔＬａｎｄプロトコルはこのファットツリートポロジに限定され、他のトポロジには適用できない。例えば、ＰｏｒｔＬａｎｄプロトコルによって使用されるＰＭＡＣの形式「ポッド．位置．ポート．仮想マシンＩＤ」は、非特許文献２で提案されるＣｌｏｓトポロジに直接適用することはできない。
【００１８】
図４に、Ｃｌｏｓトポロジの概略図を示す。Ｃｌｏｓトポロジもやはり３つの層に分割され、Ｔｏｐ ｏｆ Ｒａｃｋ（ＴｏＲ）スイッチは、エンドホストに直接接続されるファットツリートポロジのエッジスイッチと類似している。ファットツリートポロジのすべてのスイッチは同一である。ただし、Ｃｌｏｓトポロジでは、コアスイッチと集約スイッチは１０Ｇポートを有するスイッチである。ＴｏＲスイッチは１０Ｇのアップリンクポートを介して集約スイッチに接続されるが、ホストへは１Ｇのダウンリンクポートを介して接続される。
【００１９】
Ｃｌｏｓトポロジにポッドの概念はないので、ＰＭＡＣの形式（ポッド．位置．ポート．仮想マシンＩＤ）を直接利用することはできない。集約スイッチがポッドに対応する場合（例えば、集約スイッチＳ３およびＳ４がそれぞれポッド０およびポッド１に対応する場合）、ＴｏＲスイッチをアドレス指定することはできない。各ＴｏＲスイッチは２つの集約スイッチに接続されている（例：ＴｏＲスイッチＳ７が集約スイッチＳ３およびＳ４に接続されている）ので、ＴｏＲスイッチＳ７のポッド番号は０または１の可能性があるからである。その結果、非特許文献１で提案されるＰｏｒｔＬａｎｄプロトコルは、非特許文献２で提案されるＣｌｏｓトポロジに直接適用することはできない。
【先行技術文献】
【非特許文献】
【００２０】
【非特許文献１】“ＰｏｒｔＬａｎｄ：Ａ Ｓｃａｌａｂｌｅ Ｆａｕｌｔ Ｔｏｌｅｒａｎｔ ｌａｙｅｒ−２ Ｄａｔａ Ｃｅｎｔｅｒ Ｎｅｔｗｏｒｋ Ｆａｂｒｉｃ（ＰｏｒｔＬａｎｄ：スケーラブル故障耐性レイヤ２データセンターネットワークファブリック）”，Ｒａｄｈｉｋａ Ｎｉｒａｎｊａｎ Ｍｙｓｏｒｅ ｅｔｃ．，ｉｎ Ｓｉｇｃｏｍｍ ２００９
【非特許文献２】“ＶＬ２：Ａ Ｓｃａｌａｂｌｅ ａｎｄ Ｆｌｅｘｉｂｌｅ Ｄａｔａ Ｃｅｎｔｅｒ Ｎｅｔｗｏｒｋ（ＶＬ２：スケーラブルでフレキシブルなデータセンターネットワーク）”，Ａｌｂｅｒｔ Ｇｒｅｅｎｂｅｒｇ ｅｔｃ．，ｉｎ Ｓｉｇｃｏｍｍ ２００９
【非特許文献３】“Ａ Ｓｃａｌａｂｌｅ，Ｃｏｍｍｏｄｉｔｙ Ｄａｔａ Ｃｅｎｔｅｒ Ｎｅｔｗｏｒｋ Ａｒｃｈｉｔｅｃｔｕｒｅ（スケーラブルなコモディティデータセンターネットワークアーキテクチャ”，Ｍ．Ａｌ−Ｆａｒｅｓ ｅｔｃ．，ｉｎ Ｓｉｇｃｏｍｍ ２００８
【発明の概要】
【発明が解決しようとする課題】
【００２１】
関連技術における上記の欠点を鑑みて、本発明の目的は、データセンターで採用される様々なトポロジに適応可能な、データセンターネットワーク用のアドレス指定方法、アドレス指定装置、ファブリックマネージャ、スイッチ、およびデータルーティング方法を提供することにある。本発明は、転送テーブルの短縮を目的としたロケータアドレスの集約と、ネットワークのロードバランスとを実現することができる。
【００２２】
本発明は、データセンターネットワーク用のアドレス指定方法、アドレス指定装置、ファブリックマネージャ、スイッチ、およびデータルーティング方法を提供する。ネットワーク内のホストとスイッチは、１つ以上のロケータアドレスに割り当てられる。ロケータアドレスは階層的であり、トポロジ内のホストおよびスイッチの位置を符号化する。トポロジ内に冗長パスが設けられている場合、スイッチおよびホストは複数のロケータアドレスに割り当てられる。データパケットを転送するためのスイッチの転送テーブルには、ＭＡＣアドレスではなく、ロケータアドレスが格納される。複数のロケータアドレスは複数のパスがあることを示す。複数のパスからロードバランスを実現できるいくつかの適切なパスを選択することが可能となる。
【００２３】
本発明の第１の態様によれば、アドレス指定装置であって、複数のツリーを取得するために、ネットワークトポロジ発見機能を使用して、各スイッチを順にルートとして、全ホストを含むツリーを作成するツリー作成手段と、ツリー作成手段によって作成された複数のツリーから最低高さを有するツリーを選択するツリー選択手段と、ツリー選択手段によって選択された最低高さを有する各ツリーに関し、ネットワーク内の各スイッチおよび各ホストにアドレスを割り当てるアドレス割り当て手段とを備えるアドレス指定装置を提供する。
【００２４】
好ましくは、１つのスイッチをルートとして、全ホストを含む複数のツリーが作成された場合、ツリー作成手段は、当該スイッチをルートとする複数のツリーのうち最低高さを有するツリーの１つを、作成されたツリーとして選択する。
【００２５】
好ましくは、１つのスイッチをルートとして、全ホストを含む複数のツリーが作成された場合、ツリー作成手段は、当該複数のツリーのすべてを、作成されたツリーとして記録する。
【００２６】
好ましくは、当該複数のツリーのうち最低高さを有するツリーが複数個ある場合、ツリー選択手段は、最低高さを有する当該複数個のツリーのすべてを選択する。
【００２７】
好ましくは、アドレス割り当て手段は、ツリー選択手段によって選択された最低高さＨを有する各ツリーについて、ルートスイッチロケータアドレスを、ツリーのルートに位置するルートスイッチ（「第０層スイッチ」とも称する）に割り当て、ルートスイッチに直接接続された第１層スイッチから開始して、第（ｉ−１）層スイッチに直接接続された第ｉ層スイッチの各々について、ルートスイッチから第ｉ層スイッチまでのすべてのパスを検出し、各パスについて、「ルートスイッチロケータアドレス．第１層スイッチアドレス．・・・．第ｉ層スイッチアドレス」（ここで１≦ｉ≦Ｈ−２）の形式で、第ｉ層スイッチロケータアドレスを第ｉ層スイッチに割り当て、かつ、「エッジスイッチロケータアドレス．ホストアドレス」（ここで、エッジスイッチはホストに直接接続された第ｋ層スイッチであり、０≦ｋ≦Ｈ−２）の形式で、ホストロケータアドレスを各ホストに割り当てる。
【００２８】
好ましくは、第ｉ層スイッチアドレスは、第（ｉ−１）層スイッチの各第ｉ層スイッチに接続された個々のポートのポート番号である。
【００２９】
好ましくは、ホストアドレスは、エッジスイッチの各ホストに接続された個々のポートのポート番号である。
【００３０】
本発明の第２の態様によれば、アドレス指定方法であって、複数のツリーを取得するために、ネットワークトポロジ発見機能を使用して、各スイッチを順にルートとして、全ホストを含むツリーを作成するステップと、作成された複数のツリーから最低高さを有するツリーを選択するステップと、選択された最低高さを有する各ツリーに関し、ネットワーク内の各スイッチおよび各ホストにアドレスを割り当てるステップとを備えるアドレス指定方法を提供する。
【００３１】
好ましくは、１つのスイッチをルートとして、全ホストを含む複数のツリーが作成された場合、当該スイッチをルートとする複数のツリーのうち最低高さを有するツリーの１つが、作成されたツリーとして選択される。
【００３２】
好ましくは、１つのスイッチをルートとして、全ホストを含む複数のツリーが作成された場合、当該複数のツリーのすべてが、作成されたツリーとして記録される。
【００３３】
好ましくは、当該複数のツリーのうち最低高さを有するツリーが複数個ある場合には、最低高さを有する当該複数個のツリーのすべてが選択される。
【００３４】
好ましくは、最低高さＨを有する各選択されたツリーについて、ルートスイッチロケータアドレスが、ツリーのルートに位置するルートスイッチ（「第０層スイッチ」とも称する）に割り当てられ、ルートスイッチに直接接続された第１層スイッチから開始して、第（ｉ−１）層スイッチに直接接続された第ｉ層スイッチの各々について、ルートスイッチから第ｉ層スイッチまでのすべてのパスが検出され、各パスについて、「ルートスイッチロケータアドレス．第１層スイッチアドレス．・・・．第ｉ層スイッチアドレス」（ここで１≦ｉ≦Ｈ−２）の形式で、第ｉ層スイッチロケータアドレスが第ｉ層スイッチに割り当てられ、かつ、「エッジスイッチロケータアドレス．ホストアドレス」（ここで、エッジスイッチはホストに直接接続された第ｋ層スイッチであり、０≦ｋ≦Ｈ−２）の形式で、ホストロケータアドレスが各ホストに割り当てられる。
【００３５】
好ましくは、第ｉ層スイッチアドレスは、第（ｉ−１）層スイッチの各第ｉ層スイッチに接続された個々のポートのポート番号である。
【００３６】
好ましくは、ホストアドレスは、エッジスイッチの各ホストに接続された個々のポートのポート番号である。
【００３７】
本発明の第３の態様によれば、ファブリックマネージャであって、本発明によるアドレス指定装置と、各ホストのインターネットプロトコル（ＩＰ）アドレスおよびそのホストのすべてのホストロケータアドレス間のマッピングを保持するグローバルロケータアドレステーブルを格納するための記憶装置とを備えるファブリックマネージャを提供する。
【００３８】
好ましくは、ファブリックマネージャは、アドレス解決プロトコル（ＡＲＰ）要求を受信すると、宛先ホストのＩＰアドレスを索引としてグローバルロケータアドレステーブルを検索し、スケジューリングアルゴリズムに基づいて、宛先ホストのＩＰアドレスに対応する検索された１つ以上のホストロケータアドレスから１つのホストロケータアドレスを選択し、選択された１つのホストロケータアドレスを送信元ホストに返してＡＲＰアドレス解決を完了する、スケジューリング手段をさらに備える。
【００３９】
好ましくは、スケジューリング手段は、グローバルロケータアドレステーブルから宛先ホストのＩＰアドレスに対応するホストロケータアドレスが検索されなかった場合、ネットワークブロードキャストを実行して宛先ホストの１つ以上のホストロケータアドレスを取得し、スケジューリングアルゴリズムに基づいて、宛先ホストのＩＰアドレスに対応する取得された１つ以上のホストロケータアドレスから１つのホストロケータアドレスを選択し、選択された１つのホストロケータアドレスを送信元ホストに返してＡＲＰアドレス解決を完了する。
【００４０】
好ましくは、ファブリックマネージャは、スイッチが隣接スイッチの故障またはリンクの故障を検出した場合には、グローバルロケータアドレステーブル内の関連のホストロケータアドレスを無効化する障害処理手段をさらに備え、スケジューリング手段は宛先ホストのＩＰアドレスに対応するホストロケータアドレスを選択する際に、無効化されたホストロケータアドレスを選択しない。
【００４１】
本発明の第４の態様によれば、本発明によるアドレス指定装置を備えるスイッチを提供する。
【００４２】
本発明の第５の態様によれば、本発明によるアドレス指定方法によってアドレス指定されたスイッチアドレスとホストアドレスが適応される、データルーティング方法を提供する。当該データルーティング方法は、ルートスイッチ／第０層スイッチが、宛先ホストのホストロケータアドレスとして、「ルートスイッチロケータアドレス．第１層スイッチアドレス／ホストアドレス．＊」を含むデータパケットを「第１層スイッチアドレス／ホストアドレス」として付番されたポートへ送信するステップと、第ｉ層スイッチが、宛先ホストのホストロケータアドレスとして、「第ｉ層スイッチロケータアドレス．第（ｉ＋１）層スイッチアドレス／ホストアドレス．＊」を含むデータパケットを、「（ｉ＋１）層スイッチアドレス／ホストアドレス」として付番されたポート（ここで、１≦ｉ≦Ｈ−２）へ送信するステップと、第ｉ層スイッチが、宛先ホストのホストロケータアドレスとして、「ルートスイッチロケータアドレス．＊」を含むデータパケットを、「ルートスイッチロケータアドレス」のルートスイッチロケータアドレスを有するルートスイッチをルートとする第（ｉ−１）層スイッチ（ここで、１≦ｉ≦Ｈ−２）に接続されたポートに送信するステップとを備える。
【００４３】
本発明は、ファットツリートポロジ、Ｃｌｏｓトポロジ等の、データセンターによって採用される様々なトポロジに適応可能な新しいアドレス指定解決法を提供する。データパケットを転送するためのスイッチの転送テーブルには、ＭＡＣアドレスではなく、ロケータアドレスが格納される。ロケータアドレスは階層的なので、スイッチが保持する転送テーブルを小規模に維持することができる。トポロジ内に冗長パスが設けられている場合、スイッチおよびホストは複数のロケータアドレスに割り当てられる。複数のロケータアドレスは、それぞれ複数のパスがあることを示す。複数のパスからロードバランスを実現できるいくつかの適切なパスを選択することが可能となる。
【図面の簡単な説明】
【００４４】
本発明の上記および他の目的、特徴、利点は、本発明の実施例に関する以下の説明と添付図面とを参照することにより、明らかになるであろう。
【００４５】
【図１】スイッチが自己学習方式で転送テーブルを作成する場合を示す概略図である。
【図２】スイッチが、未知の宛先ＭＡＣアドレスを有するデータフレームを転送（ブロードキャスト）する場合を示す概略図である。
【図３】ＰｏｒｔＬａｎｄシステムのアーキテクチャの概略図である。
【図４】Ｃｌｏｓトポロジの概略図である。
【図５】本発明によるアドレス指定装置５００のブロック図である。
【図６】本発明によるアドレス指定装置６００のフローチャートである。
【図７】非特許文献３で提案されるファットツリートポロジを示す概略図である。
【図８】ネットワークトポロジ発見機能がファットツリートポロジに基づいて作成するツリーの例を示す。
【図９】ネットワークトポロジ発見機能がファットツリートポロジに基づいて作成するツリーの他の例を示す。
【図１０】ネットワークトポロジ発見機能がファットツリートポロジに基づいて作成するツリーの他の例を示す。
【図１１】ファットツリートポロジに基づくアドレス指定結果の一部を示す。
【図１２】Ｃｌｏｓトポロジに基づくアドレス指定結果の一部を示す。
【図１３】ファットツリートポロジにおけるデータパケットの転送を示す概略図である。
【図１４】本発明によるアドレス指定装置５００を備えるファブリックマネージャ１４００の一例のブロック図である。
【図１５】複数のパスのそれぞれに対応する複数のロケータアドレスを示す概略図である。
【００４６】
これらの図面においては、同一もしくは類似の要素またはステップは、同一もしくは類似の参照記号で識別されている。
【発明を実施するための形態】
【００４７】
以下では、図面を参照して本発明の実施例について詳述する。これにより、当業者には本発明の原理および実装は明らかとなるであろう。ただし、本発明はここで説明する特定の実施例に限定されない。さらに、明快で簡素な内容とするため、本発明に関連する一般的な要素の説明は省略している。
【００４８】
図５は、本発明によるアドレス指定装置５００のブロック図である。本発明によるアドレス指定装置５００は、図３に示すファブリックマネージャ３００や他の任意のスイッチに配置することができる。図５に示すように、本発明によるアドレス指定装置５００は、ツリー作成手段５１０と、ツリー選択手段５２０と、アドレス割り当て手段５３０とを備える。
【００４９】
ツリー作成手段５１０は、ネットワークトポロジ発見機能によって、各スイッチを順にルートとして全ホストを含むツリーを作成し、複数のツリーを取得する。トポロジは冗長パスを設けることができるので、各ツリーにスイッチのすべてを含める必要はない。また、１つのスイッチをルートとして、全ホストを含む複数のツリーが作成されることもある。この場合、ツリー作成手段５１０は、ツリー選択手段５２０の動作の前に、当該スイッチをルートとする複数のツリーから最低高さを有する任意の１つのツリーを、作成されたツリーとして選択することができる。あるいは、ツリー作成手段５１０がすべてのツリーを作成して記録しておき、ツリー選択手段５２０が選択を行うようにしてもよい。
【００５０】
ツリー選択手段５２０は、ツリー作成手段５１０によって作成された複数のツリーから最低高さを有するツリーを選択する。当該複数のツリーのうち最低高さを有するツリーが複数個ある場合には、ツリー選択手段５２０は、最低高さを有する複数個のツリーのすべてを選択する。ツリー選択手段５２０の動作によれば、同じ最低高さを有するツリーが複数個存在する場合には、トポロジは複数ルートのツリーとして構築される。
【００５１】
アドレス割り当て手段５３０は、ネットワーク内の各スイッチおよび各ホストにアドレスを割り当てる。
【００５２】
以下では、便宜上、ネットワーク内のスイッチの階層構造についてまず説明する。
【００５３】
各ツリーのルートノードにあるスイッチを「ルートスイッチ」と称する（「第０層スイッチ」とも称する）。第（ｉ−１）層スイッチに直接接続されたスイッチを「第ｉ層スイッチ」（１≦ｉ≦Ｈ−２、Ｈはツリーの高さ）と称する。ホストに直接接続されたスイッチを「エッジスイッチ」と称する（第ｋ層スイッチとも称し、０≦ｋ≦Ｈ−２である）。
【００５４】
最初に、各選択された最低高さを有するツリーについて、ツリーのルートにあるルートスイッチにルートスイッチロケータアドレスが割り当てられる。このルートスイッチは「第０層スイッチ」と称する。
【００５５】
続いて、ルートスイッチ（第０層スイッチ）に直接接続された第１層スイッチから開始して、各第ｉ層スイッチについて、ルートスイッチから第ｉ層スイッチまでのすべてのパスが検出され、各パスについて、「ルートスイッチロケータアドレス．第１層スイッチアドレス．・・・．第ｉ層スイッチアドレス」の形式で、第ｉ層スイッチロケータアドレスが第ｉ層スイッチに割り当てられる。ここで、第ｉ層スイッチアドレスは、第（ｉ−１）層スイッチの第ｉ層スイッチに接続された各ポートのポート番号である。
【００５６】
最後に、「エッジスイッチロケータアドレス．ホストアドレス」の形式で、ホストロケータアドレスが各ホストに割り当てられる。ここで、ホストアドレスは、エッジスイッチの各ホストに接続された各ポートのポート番号である。
【００５７】
図６は、本発明によるアドレス指定方法６００のフローチャートである。
【００５８】
ステップＳ６１０において、ツリー作成手段５１０は、ネットワークトポロジ発見機能によって、各スイッチを順にルートとして全ホストを含むツリーを作成し、複数のツリーを取得する。トポロジは冗長パスを設けることができるので、各ツリーにスイッチのすべてを含める必要はない。また、１つのスイッチをルートとして、全ホストを含む複数のツリーが作成されることもある。この場合、ツリー作成手段５１０は、ツリー選択手段５２０の動作の前に、当該スイッチをルートとする複数のツリーから最低高さを有する任意の１つのツリーを、作成されたツリーとして選択することができる。あるいは、ツリー作成手段５１０がすべてのツリーを作成して記録しておき、ツリー選択手段５２０が選択を行うようにしてもよい。
【００５９】
ステップＳ６２０において、ツリー選択手段５２０は、ツリー作成手段５１０によって作成された複数のツリーから最低高さを有するツリーを選択する。当該複数のツリーのうち最低高さを有するツリーが複数個ある場合には、ツリー選択手段５２０は、最低高さを有する複数個のツリーのすべてを選択する。ツリー選択手段５２０の動作によれば、同じ最低高さを有する（Ｒ）ツリーが複数個存在する場合には、トポロジは複数ルートのツリーとして構築される。複数ルートのツリーの高さはＨである。各ツリーのルートノードにあるスイッチを「ルートスイッチ」と称する（「第０層スイッチ」とも称する）。第（ｉ−１）層スイッチに直接接続されたスイッチを「第ｉ層スイッチ」（１≦ｉ≦Ｈ−２）と称する。ホストに直接接続されたスイッチを「エッジスイッチ」と称する（第ｋ層スイッチとも称し、０≦ｋ≦Ｈ−２である）。
【００６０】
ステップＳ６３０において、アドレス割り当て手段５３０は、各選択された最低高さＨを有するツリーについて、ツリーのルートにあるルートスイッチにルートスイッチロケータアドレスを割り当てる。このルートスイッチは「第０層スイッチ」とも称する。ツリーのルートノードには、例えばルートスイッチロケータアドレス「０」、「１」、・・・、「Ｒ−１」を順に割り当てることができる。
【００６１】
ステップＳ６４０において、アドレス割り当て手段５３０は、ルートスイッチ（第０層スイッチ）に直接接続された第１層スイッチから開始して、各第ｉ層スイッチについて、ルートスイッチから第ｉ層スイッチまでのすべてのパスを検出し、各パスについて、「ルートスイッチロケータアドレス．第１層スイッチアドレス．・・・．第ｉ層スイッチアドレス」の形式で、第ｉ層スイッチロケータアドレスを第ｉ層スイッチに割り当てる。ここで、第ｉ層スイッチアドレスは、第（ｉ−１）層スイッチの第ｉ層スイッチに接続された各ポートのポート番号である。
【００６２】
ステップＳ６５０において、アドレス割り当て手段５３０は、「エッジスイッチロケータアドレス．ホストアドレス」の形式で、ホストロケータアドレスを各ホストに割り当てる。ここで、ホストアドレスは、エッジスイッチの各ホストに接続された各ポートのポート番号である。
【００６３】
ロケータアドレス「ルートスイッチロケータアドレス．第１層スイッチアドレス．・・・．第ｉ層スイッチアドレス．・・・．エッジスイッチロケータアドレス．ホストアドレス」については、ロケータアドレスの各層は８ビットで示すことができる。そのため、トポロジ発見機能によって取得された複数ルートのツリーの高さＨが６未満の場合には、ロケータアドレスの長さが４８ビットのＭＡＣアドレス領域を超えることはない。
【００６４】
ロケータアドレスが全６層（４８ビット）に達しなかった場合、（アドレス割り当て手段５３０によって）無効なアドレスビットが「１」で示される。例えば、「０．１．２．３．２５５．２５５」は、ホストのロケータアドレスの形式は「ルートスイッチロケータアドレス．第１層アドレス．第２層アドレス．ホストアドレス」であり、その固有値は「０．１．２．３」であることを示す。煩雑化を避けるため、記述においては無効なアドレスビットは通常省略される。よって、「０．１．２．３」は「０．１．２．３．２５５．２５５」を表す。
【００６５】
「ルートスイッチロケータアドレス」のアドレス領域のサイズは、ルートスイッチ数によって決まる。８ビットは、最大２５５個のルートスイッチを表すことができる。通常、コア層のスイッチは１０Ｇポートを備えるスイッチである。ここで、コア層には、各々１２８ポートを有する２５５個のスイッチがあると想定する。したがって、この構成では、２５５＊１２８＊１０＝３２６，４００のホストにおいて１Ｇ通信をサポートすることが可能である。この数は大規模なデータセンターの要件を十分に満たすことができる。
【００６６】
「ルートスイッチロケータアドレス」だけでなく、「第１層アドレス」、「第２層アドレス」、・・・、「第ｎ層アドレス」、または「ホストアドレス」のアドレス領域のサイズも、スイッチのポート数によって異なる。８ビットは最大２５５ポートを表現できるので、既存のスイッチの要件を満たすには十分である。
【００６７】
一方、トポロジ発見機能によって取得された複数ルートのツリーの高さＨが６より大きい場合、ロケータアドレス「ルートスイッチロケータアドレス．第１層スイッチアドレス．・・・．第ｉ層スイッチアドレス．・・・．エッジスイッチロケータアドレス．ホストアドレス」を圧縮する必要がある。ある特定層の最大アドレス領域≦２Ｎ−１とすると、この層のビット数はＮビットに圧縮される（アドレス割り当て手段５３０によって実行される）。この場合、各層はもはや固定ビット長（８ビット）で示されないため、ファブリックマネージャ３００（図３）はトポロジ発見の完了後に、すべてのスイッチに各層のビット長を通知する。
【００６８】
本発明で提案されるアドレス指定の解決法は、データセンターによって採用される様々なトポロジに適応可能である。以下に、典型的なトポロジにおけるアドレス指定の例を示す。
【００６９】
図７は、非特許文献３で提案されるファットツリートポロジを示す概略図である。詳細については図３を参照すると分かるので、ここでは煩雑化を避けるため省略する。
【００７０】
図８に、ネットワークトポロジ発見機能がファットツリートポロジに基づいて作成するツリーの例を示す。
【００７１】
図８に示すように、ツリー作成手段５１０は、ネットワークトポロジ発見機能を使用し、スイッチＳ１をルートとして、全ホストを含むツリーを作成する（ステップＳ６１０）。ツリーの高さＨは４である。
【００７２】
図９に、ネットワークトポロジ発見機能がファットツリートポロジに基づいて作成するツリーの他の例を示す。
【００７３】
図９に示すように、ツリー作成手段５１０は、ネットワークトポロジ発見機能を使用し、スイッチＳ５をルートとして、全ホストを含む他のツリーを作成する（ステップＳ６１０）。ツリーの高さＨは５である。
【００７４】
図１０に、ネットワークトポロジ発見機能がファットツリートポロジに基づいて作成するツリーの他の例を示す。
【００７５】
図１０に示すように、ツリー作成手段５１０は、ネットワークトポロジ発見機能を使用し、スイッチＳ１３をルートとして、全ホストを含む他のツリーを作成する（ステップＳ６１０）。ツリーの高さＨは６である。
【００７６】
上記の動作によれば、ツリー作成手段５１０は、図７に示すファットツリートポロジに対し少なくとも２０個のツリーを作成することができる。
【００７７】
図１１に、ファットツリートポロジに基づくアドレス指定結果の一部を示す。
【００７８】
ツリー選択手段５２０は、ツリー作成手段５１０によって作成された少なくとも２０個のツリーから、最低高さ（Ｈ＝４）を有するツリーを選択する。最低高さＨ＝４のツリーは４個あり、それぞれスイッチＳ１、Ｓ２、Ｓ３、Ｓ４をルートとする（ステップＳ６２０）。
【００７９】
そのため、アドレス割り当て手段５３０は、ルートスイッチである４個のスイッチＳ１、Ｓ２、Ｓ３、Ｓ４にロケータアドレス「０」、「１」、「２」、「３」を割り当てる（ステップＳ６３０）。
【００８０】
スイッチＳ５〜Ｓ１２はルートスイッチに直接接続されているため、第１層スイッチである。第１層スイッチの各々について、ルートスイッチから第１層スイッチまでのパスは２つある。したがって、第１層スイッチの各々に２つのロケータアドレスが割り当てられる。例えば、スイッチＳ５の場合、１つのパスはＳ１→Ｓ５である。スイッチＳ５がルートスイッチＳ１のポート０に接続されているとすると、スイッチＳ５によってこのパスのために取得されるスイッチロケータアドレスは「０．０」である。ルートスイッチからスイッチＳ５までのもう一方のパスは、Ｓ２→Ｓ５である。スイッチＳ５がルートスイッチＳ２のポート０に接続されているとすると、スイッチＳ５によってこのパスのために取得されるスイッチロケータアドレスは「１．０」である。スイッチＳ１３〜Ｓ２０は第１層スイッチに直接接続されているので、第２層スイッチである。第２層スイッチの各々について、ルートスイッチから第２層スイッチまでのパスは４つある。そのため、第２層スイッチの各々には４個のロケータアドレスが割り当てられる。例えば、、スイッチＳ１３の４個のパスはＳ１→Ｓ５→Ｓ１３、Ｓ２→Ｓ５→Ｓ１３、Ｓ３→Ｓ６→Ｓ１３、Ｓ４→Ｓ６→Ｓ１３であり、対応する４個のスイッチロケータアドレスは「０．０．０」、「１．０．０」、「２．０．０」、「３．０．０」である（ステップＳ６３０）。
【００８１】
ホストはエッジスイッチ（第２層スイッチ）に直接接続される。エッジスイッチの各スイッチロケータアドレスに対応して、１つのホストロケータアドレスが各ホストに割り当てられる。そのため、図１１に示す各ホストは４個のホストロケータアドレスを有する。例えば、ホストＨ１はＳ１３のポート０に接続される。したがって、スイッチＳ１３の４個のスイッチロケータアドレス「０．０．０」、「１．０．０」、「２．０．０」、「３．０．０」に対応するホストＨ１のホストロケータアドレスは、「０．０．０．０」、「１．０．０．０」、「２．０．０．０」、「３．０．０．０」である（ステップＳ６４０）。
【００８２】
図１２に、Ｃｌｏｓトポロジに基づくアドレス指定結果の一部を示す。
【００８３】
図１２に示すＣｌｏｓトポロジの場合、ツリー作成手段５１０は少なくとも１０個のツリーを作成する可能性がある。
【００８４】
ツリー選択手段５２０は、ツリー作成手段５１０によって作成された少なくとも１０個のツリーから、最低高さ（Ｈ＝４）を有するツリーを選択する。最低高さＨ＝４のツリーは２個あり、それぞれスイッチＳ１、Ｓ２をルートとする（ステップＳ６２０）。
【００８５】
そのため、アドレス割り当て手段５３０は、ルートスイッチである２個のスイッチＳ１、Ｓ２にロケータアドレス「０」、「１」を割り当てる（ステップＳ６３０）。
【００８６】
スイッチＳ３〜Ｓ６はルートスイッチに直接接続されているので、第１層スイッチである。第１層スイッチの各々について、ルートスイッチから第１層スイッチまでのパスは２つある。したがって、第１層スイッチの各々に２つのロケータアドレスが割り当てられる。例えば、スイッチＳ３の場合、１つのパスはＳ１→Ｓ３である。スイッチＳ３がルートスイッチＳ１のポート０に接続されているとすると、スイッチＳ３によってこのパスのために取得されるスイッチロケータアドレスは「０．０」である。ルートスイッチからスイッチＳ３までのもう一方のパスは、Ｓ２→Ｓ３である。スイッチＳ３がルートスイッチＳ２のポート０に接続されているとすると、スイッチＳ３によってこのパスのために取得されるスイッチロケータアドレスは「１．０」である。スイッチＳ７〜Ｓ１０は第１層スイッチに直接接続されているので、第２層スイッチである。第２層スイッチの各々について、ルートスイッチから第２層スイッチまでのパスは４つある。そのため、第２層スイッチの各々には４個のロケータアドレスが割り当てられる。例えば、スイッチＳ７の４個のパスはＳ１→Ｓ３→Ｓ７、Ｓ２→Ｓ３→Ｓ７、Ｓ１→Ｓ４→Ｓ７、Ｓ２→Ｓ４→Ｓ７であり、４個のスイッチロケータアドレスは「０．０．０」、「１．０．０」、「０．１．０」、「１．１．０」である（ステップＳ６３０）。
【００８７】
ホストはエッジスイッチ（第２層スイッチ）に直接接続されている。エッジスイッチの各スイッチロケータアドレスに対応して、１つのホストロケータアドレスが各ホストに割り当てられる。そのため、図１２に示す各ホストは４個のホストロケータアドレスを有する。例えば、ホストＨ１はＳ７のポート０に接続される。したがって、スイッチＳ７の４個のスイッチロケータアドレス「０．０．０」、「１．０．０」、「０．１．０」、「１．１．０」に対応するホストＨ１のホストロケータアドレスは、「０．０．０．０」、「１．０．０．０」、「０．１．０．０」、「１．１．０．０」である（ステップＳ６４０）。
【００８８】
データパケットを転送するためのスイッチの転送テーブルには、ＭＡＣアドレスではなく、ロケータアドレスが格納される。図１３は、ファットツリートポロジにおけるデータパケットの転送を示す概略図である。各層のスイッチの転送テーブルは、以下のとおりである。
・ルートスイッチ：
セルフロケータ．ポート．＊⇔ポート「ポート」
ここで、「セルフロケータ」はルートスイッチ自体のルートスイッチロケータアドレスを表し、「ポート」はルートスイッチロケータアドレスの後に位置する次のアドレスフィールドを表す。
例えば、ルートスイッチＳ１の「セルフロケータ」は「０」である。そのポート０はＳ５に接続されており、Ｓ５に割り当てられている第１層アドレスも「０」である。そのため、宛先ロケータアドレス「０．０．＊」を有するデータパケットはポート０に送信される。同様に、宛先ロケータアドレス「０．１．＊」を有するデータパケットはポート１に送信される。
・第ｉ層スイッチ：
セルフロケータ．ポート．＊⇔ポート「ポート」
親のルート．＊⇔第（ｉ−１）層スイッチに接続されたポート
ここで、「セルフロケータ」は第ｉ層スイッチ自体の第ｉ層スイッチロケータアドレスを表し、「ポート」は第ｉ層スイッチロケータアドレスの後に位置する次のアドレスフィールドを表し、「親のルート」は第ｉ層スイッチに接続される第（ｉ−１）層スイッチのルートスイッチのルートスイッチロケータアドレスを表す。
例えば、スイッチＳ５の「セルフロケータ」は「０．０」および「１．０」である。そのポート０はＳ１３に接続されており、Ｓ１３に割り当てられている第２層アドレスも「０」である。そのため、宛先ロケータアドレス「セルフロケータ．０．＊」を有するデータパケットはポート０に送信される（すなわち、“０．０．０．＊” ⇔ポート０、“１．０．０．＊” ⇔ポート０）。同様に、宛先ロケータアドレス「セルフロケータ１．＊」を有するデータパケットはポート１に送信される（すなわち、“０．０．１．＊” ⇔ポート１、“１．０．１．＊” ⇔ポート１）。スイッチＳ５のポート２および３はアップリンクポートであり、第（ｉ−１）層スイッチに接続されている。スイッチＳ５のポート２および３に接続されている第（ｉ−１）層スイッチを、スイッチＳ５の親スイッチと称する。したがって、スイッチＳ５は２個の親スイッチＳ１およびＳ２を有する。スイッチＳ２はスイッチＳ５のポート２に接続されているとすると、スイッチＳ２のルートノードはＳ２自体（ルートスイッチロケータアドレスは「１」（親のルート））である。したがって、対応する転送テーブル項目は「１．＊」⇔ポート２である。同様に、スイッチＳ１はスイッチＳ５のポート３に接続されているとすると、スイッチＳ１のルートノードはＳ１自体（ルートスイッチロケータアドレスは「０」（親のルート））である。したがって、対応する転送テーブル項目は「０．＊」⇔ポート３である。
別の例を挙げると、スイッチＳ１３の「セルフロケータ」は「０．０．０」、「１．０．０」、「２．０．０」、「３．０．０」である。そのポート０はホストＨ１に接続されており、Ｈ１に割り当てられているホストロケータアドレスも「０」である。そのため、宛先ロケータアドレス「セルフロケータ．０．＊」を有するデータパケットはポート０に送信される（すなわち、「０．０．０．０．＊」⇔ポート０、「１．０．０．０．＊」⇔ポート０、「２．０．０．０．＊」⇔ポート０、「３．０．０．０．＊」⇔ポート０）。同様に、宛先ロケータアドレス「セルフロケータ１．＊」を有するデータパケットはポート１に送信される（すなわち、「０．０．０．１．＊」⇔ポート１、「１．０．０．１．＊」⇔ポート１、「２．０．０．１．＊」⇔ポート１、「３．０．０．１．＊」⇔ポート１）。スイッチＳ１３のポート２および３はアップリンクポートであり、第（ｉ−１）層スイッチに接続されている。スイッチＳ１３のポート２および３に接続されている第（ｉ−１）層スイッチを、スイッチＳ１３の親スイッチと称する。したがって、スイッチＳ１３は２個の親スイッチＳ５およびＳ６を有する。スイッチＳ６はスイッチＳ１３のポート２に接続されているとすると、スイッチＳ６のルートノードはルートスイッチＳ３（ルートスイッチロケータアドレスは「２」（親のルート））またはルートスイッチＳ４（ルートスイッチロケータアドレスは「３」（親のルート））である。したがって、対応する転送テーブル項目は「２．＊」⇔ポート２と「３．＊」⇔ポート２である。同様に、スイッチＳ５はスイッチＳ１３のポート３に接続されているとすると、スイッチＳ５のルートノードはルートスイッチＳ１（ルートスイッチロケータアドレスは「０」（親のルート））またはルートスイッチＳ２（ルートスイッチロケータアドレスは「１」（親のルート））である。したがって、対応する転送テーブル項目は「０．＊」⇔ポート３と「１．＊」⇔ポート３である。
【００８９】
トポロジ内に冗長パスが設けられている場合、スイッチおよびホストは複数のロケータアドレスに割り当てられる。複数のロケータアドレスは、それぞれ複数のパスがあることを示す。ロードバランスのために、複数のパスからいくつかの適切なパスが選択されることがある。
【００９０】
図１４は、本発明によるアドレス指定装置５００を備えるファブリックマネージャ１４００の一例のブロック図である。図１５は、複数のパスのそれぞれに対応する複数のロケータアドレスを示す概略図である。
【００９１】
図１４に示すように、本発明によるアドレス指定装置５００を備えるファブリックマネージャ１４００は、記憶装置１４１０と、スケジューリング手段１４２０と、障害処理手段１４３０とをさらに備える。
【００９２】
記憶装置１４１０は、各ホストのインターネットプロトコル（ＩＰ）アドレスと、アドレス指定装置５００によって作成された当該ホストのすべてのホストロケータアドレスとの間のマッピングを保持するグローバルロケータアドレステーブルを格納する。
【００９３】
スケジューリング手段１４２０は、アドレス解決プロトコル（ＡＲＰ）要求が受信されると、宛先ホストのＩＰアドレスを索引としてグローバルロケータアドレステーブルを検索し、スケジューリングアルゴリズムに基づいて、宛先ホストのＩＰアドレスに対応する検索された１つ以上のホストロケータアドレスから１つのホストロケータアドレスを選択し、選択された１つのホストロケータアドレスを送信元ホストに返してＡＲＰアドレス解決を完了する。グローバルロケータアドレステーブルから宛先ホストのＩＰアドレスに対応するホストロケータアドレスが検索されなかった場合には、スケジューリング手段１４２０は、ネットワークブロードキャストを実行して宛先ホストの１つ以上のホストロケータアドレスを取得し（宛先ホストの１つ以上のホストロケータアドレスとＩＰアドレスとのマッピングは、グローバルロケータテーブルに格納してもよい）、スケジューリングアルゴリズムに基づいて、宛先ホストのＩＰアドレスに対応する取得された１つ以上のホストロケータアドレスから１つのホストロケータアドレスを選択し、選択された１つのホストロケータアドレスを送信元ホストに返してＡＲＰアドレス解決を完了する。
【００９４】
スイッチが隣接スイッチの故障またはリンクの故障を検出した場合には、障害処理手段１４３０が、グローバルロケータアドレス（＊テーブル？）内の関連のホストロケータアドレスを無効化する。スケジューリング手段１４２０は、宛先ホストのＩＰアドレスに対応するホストロケータアドレスを選択する際に、無効化されたホストロケータアドレスを選択しない。
【００９５】
図１５に示すように、ホストＨ１は送信元ホストであり、ホストＨ５は宛先ホストである。ホストＨ５には４個のロケータアドレスが付与されている。したがって、やはり図１５に示されるように、ホストＨ１からホストＨ５までのパスは４つある。グローバルロケータアドレステーブル（記憶装置１４１０に格納されている）には、全ホストのすべてのホストロケータアドレスが保持されている。ファブリックマネージャがアドレス解決プロトコル（ＡＲＰ）要求を受信すると、スケジューリング手段１４２０は、ホストロケータアドレスから１個のホストロケータアドレスを選択することで、それに応答することがある。ホストロケータアドレスを選択することは、複数のパスから１つのパスを選択することに相当する。ロードバランスのために、複数のパスからいくつかの適切なパスが選択されることがある。この選択方法としては、ランダム、ラウンドロビン等のスケジューリングアルゴリズムを使用できる。ファブリックマネージャは、ＡＲＰアドレス解決のために、グローバルロケータアドレステーブルを格納する。ファブリックマネージャはＡＲＰ要求が受信されると、グローバルロケータアドレステーブルを検索して、宛先ホストのＩＰアドレスに対応するホストロケータアドレスを見つける。宛先ホストのＩＰアドレスに対応する１つ以上のホストロケータアドレスが見つかった場合には、スケジューリングアルゴリズムに基づいて、検索された１つ以上のホストロケータアドレスから１つのホストロケータアドレスが選択され、選択された１つのホストロケータアドレスが送信元ホストに返されて、ＡＲＰアドレス解決が完了する。グローバルロケータアドレステーブルから宛先ホストのＩＰアドレスに対応するホストロケータアドレスが検索されなかった場合には、ファブリックマネージャは、ネットワークブロードキャストを実行して宛先ホストの１つ以上のホストロケータアドレスを取得し、スケジューリングアルゴリズムに基づいて、取得された１つ以上のホストロケータアドレスから１つのホストロケータアドレスを選択し、選択された１つのホストロケータアドレスを送信元ホストに返してＡＲＰアドレス解決を完了する。ほとんどの場合、ファブリックマネージャが関与するときには、ネットワーク全体に対するブロードキャストは不要である。
【００９６】
加えて、データセンターは数万台のサーバとスイッチを備えており、複数の異なるアプリケーションを同時にサポートしているため、データセンターネットワークの耐故障性に対する要件は厳しい。本発明は、耐故障性の容易な実現方法として、１つのスイッチに対して１つ以上のスイッチロケータアドレスを使用している。隣接スイッチの動作状態を検出するため、スイッチ間でキープアライブメッセージが定期的に交換されている（これは、スイッチ内の障害検出手段によって行うことができる）。スイッチまたはリンクに障害が発生した場合には、隣接スイッチ内の障害検出手段がこの障害を検出し、ファブリックマネージャに報告する。その後、障害処理手段１４３０が、グローバルロケータアドレステーブル内の関連のホストロケータアドレスを無効化する。スケジューリング手段１４２０は、以降のＡＲＰ要求を処理する際に無効なホストロケータアドレスを避け、有効なホストロケータアドレスを選択してＡＲＰアドレス解決を完了する。
【００９７】
本発明の他の構成としては、方法実施例のステップおよび動作を実行するソフトウェアプログラムが挙げられる。以下ではまずその概要を述べ、次に詳細に説明する。具体的には、１つの実施例は、符号化されたコンピュータプログラム論理を格納するコンピュータ可読媒体で構成されるコンピュータプログラム製品である。コンピュータプログラム論理は、コンピュータ装置上で実行されると、上記の３Ｄ位置決め解決法を提供するために必要な動作を提供する。コンピュータプログラム論理は、それがコンピューティングシステムの少なくとも１つのプロセッサ上で実行されたときに、当該少なくとも１つのプロセッサが本発明の実施例の動作（方法）を実行することを可能にする。本発明のこうした構成は、典型的には、光媒体（例：ＣＤ−ＲＯＭ）、ソフトディスク、ハードディスク等のコンピュータ可読媒体、１つ以上のＲＯＭ、ＲＡＭ、もしくはＰＲＯＭチップに格納されたファームウェアもしくはマイクロコード等のその他の媒体、特定用途向け集積回路（ＡＳＩＣ）、または単一もしくは複数モジュール上のダウンロード可能なソフトウェアイメージおよび共有データベース等において提供または符号化されるソフトウェア、コード、その他のデータ構造として提供される。ソフトウェア、ハードウェア等の構成は、コンピューティング装置上にインストールされることにより、コンピューティング装置内の１つ以上のプロセッサを介して、本発明の実施例による技法を実行することができる。また、本発明のノードおよびホストは、ソフトウェアプロセスを、例えば他のエンティティ内の一連のデータ通信装置やコンピューティング装置と共に稼働させることによっても実現することができる。本発明のノードおよびホストはさらに、複数のデータ通信装置の複数のソフトウェアプロセス間に分散させたり、一連の小型専用コンピュータ上で稼働するすべてのソフトウェアプロセス、あるいは単一のコンピュータ上で稼働するすべてのソフトウェアプロセスに分散させることも可能である。
【００９８】
本発明の実施例は、厳密には、ソフトウェアプログラム、１台のデータ処理装置上のソフトウェアおよびハードウェア、独立したソフトウェア、または独立した回路として実装できることに留意されたい。
【００９９】
以上、実施例に関連して本発明を説明してきたが、本発明はその精神と範囲から逸脱することなく様々な変更、置換、追加を行うことが当業者によって可能なことは理解されるであろう。したがって、本発明の範囲は上記の特定の実施例に限定されず、以下の請求項によって限定される。
【０１００】
さらに、上記実施形態の一部又は全部は、以下の付記のようにも記載されうるが、これに限定されない。
【０１０１】
（付記１）
複数のツリーを取得するために、ネットワークトポロジ発見機能を使用して、各スイッチを順にルートとして、全ホストを含むツリーを作成するツリー作成手段と、
前記ツリー作成手段によって作成された複数のツリーから最低高さを有するツリーを選択するツリー選択手段と、
前記ツリー選択手段によって選択された最低高さを有する各ツリーに関し、ネットワーク内の各スイッチおよび各ホストにアドレスを割り当てるアドレス割り当て手段と
を備えることを特徴とするアドレス指定装置。
【０１０２】
（付記２）
１つのスイッチをルートとして、全ホストを含む複数のツリーが作成された場合、前記ツリー作成手段は、当該スイッチをルートとする複数のツリーのうち最低高さを有するツリーの１つを、作成されたツリーとして選択することを特徴とする付記１に記載のアドレス指定装置。
【０１０３】
（付記３）
１つのスイッチをルートとして、全ホストを含む複数のツリーが作成された場合、前記ツリー作成手段は、当該複数のツリーのすべてを、作成されたツリーとして記録することを特徴とする付記１に記載のアドレス指定装置。
【０１０４】
（付記４）
前記複数のツリーのうち最低高さを有するツリーが複数個ある場合、前記ツリー選択手段は、最低高さを有する当該複数個のツリーのすべてを選択することを特徴とする付記１から付記３の何れかに記載のアドレス指定装置。
【０１０５】
（付記５）
前記ツリー選択手段によって選択された最低高さＨを有する各ツリーについて、前記アドレス割り当て手段は、
ルートスイッチロケータアドレスを、ツリーのルートに位置するルートスイッチ（第０層スイッチ）に割り当て、
前記ルートスイッチに直接接続された第１層スイッチから開始して、第（ｉ−１）層スイッチに直接接続された第ｉ層スイッチの各々について、ルートスイッチから第ｉ層スイッチまでのすべてのパスを検出し、各パスについて、「ルートスイッチロケータアドレス．第１層スイッチアドレス．・・・．第ｉ層スイッチアドレス」（ここで、１≦ｉ≦Ｈ−２）の形式で、第ｉ層スイッチロケータアドレスを第ｉ層スイッチに割り当て、
「エッジスイッチロケータアドレス．ホストアドレス」（ここで、エッジスイッチはホストに直接接続された第ｋ層スイッチであり、０≦ｋ≦Ｈ−２）の形式で、ホストロケータアドレスを各ホストに割り当てる
ことを特徴とする付記１から付記４の何れかに記載のアドレス指定装置。
【０１０６】
（付記６）
前記第ｉ層スイッチアドレスは、第（ｉ−１）層スイッチの各第ｉ層スイッチに接続された個々のポートのポート番号であることを特徴とする付記５に記載のアドレス指定装置。
【０１０７】
（付記７）
前記ホストアドレスは、エッジスイッチの各ホストに接続された個々のポートのポート番号であることを特徴とする付記５又は付記６に記載のアドレス指定装置。
【０１０８】
（付記８）
複数のツリーを取得するために、ネットワークトポロジ発見機能を使用して、各スイッチを順にルートとして、全ホストを含むツリーを作成するステップと、
作成された複数のツリーから最低高さを有するツリーを選択するステップと、
選択された最低高さを有する各ツリーに関し、ネットワーク内の各スイッチおよび各ホストにアドレスを割り当てるステップと
を備えることを特徴とするアドレス指定方法。
【０１０９】
（付記９）
１つのスイッチをルートとして、全ホストを含む複数のツリーが作成された場合、当該スイッチをルートとする複数のツリーのうち最低高さを有するツリーの１つが、作成されたツリーとして選択されることを特徴とする付記８に記載のアドレス指定方法。
【０１１０】
（付記１０）
１つのスイッチをルートとして、全ホストを含む複数のツリーが作成された場合、当該複数のツリーのすべてが、作成されたツリーとして記録されることを特徴とする付記８に記載のアドレス指定方法。
【０１１１】
（付記１１）
当該複数のツリーのうち最低高さを有するツリーが複数個ある場合、最低高さを有する当該複数個のツリーのすべてが選択されることを特徴とする付記８から付記１０の何れか１項に記載のアドレス指定方法。
【０１１２】
（付記１２）
最低高さＨを有する各選択されたツリーについて、
ルートスイッチロケータアドレスが、ツリーのルートに位置するルートスイッチ（「第０層スイッチ」とも称する）に割り当てられ、
ルートスイッチに直接接続された第１層スイッチから開始して、第（ｉ−１）層スイッチに直接接続された第ｉ層スイッチの各々について、ルートスイッチから第ｉ層スイッチまでのすべてのパスが検出され、各パスについて、「ルートスイッチロケータアドレス．第１層スイッチアドレス．・・・．第ｉ層スイッチアドレス」（ここで１≦ｉ≦Ｈ−２）の形式で、第ｉ層スイッチロケータアドレスが第ｉ層スイッチに割り当てられ、
「エッジスイッチロケータアドレス．ホストアドレス」（ここで、エッジスイッチはホストに直接接続された第ｋ層スイッチであり、０≦ｋ≦Ｈ−２）の形式で、ホストロケータアドレスが各ホストに割り当てられる
ことを特徴とする付記８から付記１１の何れか１項に記載のアドレス指定方法。
【０１１３】
（付記１３）
前記第ｉ層スイッチアドレスは、第（ｉ−１）層スイッチの各第ｉ層スイッチに接続された個々のポートのポート番号であることを特徴とする付記１２に記載のアドレス指定方法。
【０１１４】
（付記１４）
前記ホストアドレスは、エッジスイッチの各ホストに接続された個々のポートのポート番号であることを特徴とする付記１２又は付記１３に記載のアドレス指定方法。
【０１１５】
（付記１５）
付記１から付記７の何れかに記載のアドレス指定装置と、
各ホストのインターネットプロトコル（ＩＰ）アドレスおよびそのホストのすべてのホストロケータアドレス間のマッピングを保持するグローバルロケータアドレステーブルを格納するための記憶装置と
を備えることを特徴とするファブリックマネージャ。
【０１１６】
（付記１６）
アドレス解決プロトコル（ＡＲＰ）要求を受信すると、宛先ホストのＩＰアドレスを索引としてグローバルロケータアドレステーブルを検索し、スケジューリングアルゴリズムに基づいて、宛先ホストのＩＰアドレスに対応する検索された１つ以上のホストロケータアドレスから１つのホストロケータアドレスを選択し、選択された１つのホストロケータアドレスを送信元ホストに返してＡＲＰアドレス解決を完了する、スケジューリング手段を
さらに備えることを特徴とする付記１５に記載のファブリックマネージャ。
【０１１７】
（付記１７）
前記スケジューリング手段は、グローバルロケータアドレステーブルから宛先ホストのＩＰアドレスに対応するホストロケータアドレスが検索されなかった場合には、ネットワークブロードキャストを実行して宛先ホストの１つ以上のホストロケータアドレスを取得し、スケジューリングアルゴリズムに基づいて、宛先ホストのＩＰアドレスに対応する取得された１つ以上のホストロケータアドレスから１つのホストロケータアドレスを選択し、選択された１つのホストロケータアドレスを送信元ホストに返してＡＲＰアドレス解決を完了することを特徴とする付記１６に記載のファブリックマネージャ。
【０１１８】
（付記１８）
スイッチが隣接スイッチの故障またはリンクの故障を検出した場合、グローバルロケータアドレステーブル内の関連のホストロケータアドレスを無効化する障害処理手段をさらに備え、
前記スケジューリング手段は、宛先ホストのＩＰアドレスに対応するホストロケータアドレスを選択する際に、前記無効化されたホストロケータアドレスを選択しないことを特徴とする付記１６又は付記１７に記載のファブリックマネージャ。
【０１１９】
（付記１９）
付記１から付記７の何れかに記載のアドレス指定装置を備えることを特徴とするスイッチ。
【０１２０】
（付記２０）
付記１４に記載のアドレス指定方法によってアドレス指定されたスイッチアドレスとホストアドレスが適応される、データルーティング方法であって、
ルートスイッチ／第０層スイッチが、宛先ホストのホストロケータアドレスとして、「ルートスイッチロケータアドレス．第１層スイッチアドレス／ホストアドレス．＊」を含むデータパケットを「第１層スイッチアドレス／ホストアドレス」として付番されたポートへ送信するステップと、
第ｉ層スイッチが、宛先ホストのホストロケータアドレスとして、「第ｉ層スイッチロケータアドレス．第（ｉ＋１）層スイッチアドレス／ホストアドレス．＊」を含むデータパケットを、「（ｉ＋１）層スイッチアドレス／ホストアドレス」として付番されたポート（ここで、１≦ｉ≦Ｈ−２）へ送信するステップと、
第ｉ層スイッチが、宛先ホストのホストロケータアドレスとして、「ルートスイッチロケータアドレス．＊」を含むデータパケットを、「ルートスイッチロケータアドレス」のルートスイッチロケータアドレスを有するルートスイッチをルートとする第（ｉ−１）層スイッチ（ここで、１≦ｉ≦Ｈ−２）に接続されたポートに送信するステップと
を備えることを特徴とするデータルーティング方法。
【符号の説明】
【０１２１】
５００：アドレス指定装置
５１０：ツリー作成手段
５２０：ツリー選択手段
５３０：アドレス割り当て手段
６００：アドレス指定方法
１４００：ファブリックマネージャ
１４１０：記憶装置
１４２０：スケジューリング手段
１４３０：障害処理手段
【特許請求の範囲】
【請求項１】
複数のツリーを取得するために、ネットワークトポロジ発見機能を使用して、各スイッチを順にルートとして、全ホストを含むツリーを作成するツリー作成手段と、
前記ツリー作成手段によって作成された複数のツリーから最低高さを有するツリーを選択するツリー選択手段と、
前記ツリー選択手段によって選択された最低高さを有する各ツリーに関し、ネットワーク内の各スイッチおよび各ホストにアドレスを割り当てるアドレス割り当て手段と
を備えることを特徴とするアドレス指定装置。
【請求項２】
１つのスイッチをルートとして、全ホストを含む複数のツリーが作成された場合、前記ツリー作成手段は、当該スイッチをルートとする複数のツリーのうち最低高さを有するツリーの１つを、作成されたツリーとして選択することを特徴とする請求項１に記載のアドレス指定装置。
【請求項３】
１つのスイッチをルートとして、全ホストを含む複数のツリーが作成された場合、前記ツリー作成手段は、当該複数のツリーのすべてを、作成されたツリーとして記録することを特徴とする請求項１に記載のアドレス指定装置。
【請求項４】
前記複数のツリーのうち最低高さを有するツリーが複数個ある場合、前記ツリー選択手段は、最低高さを有する当該複数個のツリーのすべてを選択することを特徴とする請求項１から請求項３の何れかに記載のアドレス指定装置。
【請求項５】
前記ツリー選択手段によって選択された最低高さＨを有する各ツリーについて、前記アドレス割り当て手段は、
ルートスイッチロケータアドレスを、ツリーのルートに位置するルートスイッチ（第０層スイッチ）に割り当て、
前記ルートスイッチに直接接続された第１層スイッチから開始して、第（ｉ−１）層スイッチに直接接続された第ｉ層スイッチの各々について、ルートスイッチから第ｉ層スイッチまでのすべてのパスを検出し、各パスについて、「ルートスイッチロケータアドレス．第１層スイッチアドレス．・・・．第ｉ層スイッチアドレス」（ここで、１≦ｉ≦Ｈ−２）の形式で、第ｉ層スイッチロケータアドレスを第ｉ層スイッチに割り当て、
「エッジスイッチロケータアドレス．ホストアドレス」（ここで、エッジスイッチはホストに直接接続された第ｋ層スイッチであり、０≦ｋ≦Ｈ−２）の形式で、ホストロケータアドレスを各ホストに割り当てる
ことを特徴とする請求項１から請求項４の何れかに記載のアドレス指定装置。
【請求項６】
前記第ｉ層スイッチアドレスは、第（ｉ−１）層スイッチの各第ｉ層スイッチに接続された個々のポートのポート番号であることを特徴とする請求項５に記載のアドレス指定装置。
【請求項７】
前記ホストアドレスは、エッジスイッチの各ホストに接続された個々のポートのポート番号であることを特徴とする請求項５又は請求項６に記載のアドレス指定装置。
【請求項８】
複数のツリーを取得するために、ネットワークトポロジ発見機能を使用して、各スイッチを順にルートとして、全ホストを含むツリーを作成するステップと、
作成された複数のツリーから最低高さを有するツリーを選択するステップと、
選択された最低高さを有する各ツリーに関し、ネットワーク内の各スイッチおよび各ホストにアドレスを割り当てるステップと
を備えることを特徴とするアドレス指定方法。
【請求項９】
請求項１から請求項７の何れかに記載のアドレス指定装置と、
各ホストのインターネットプロトコル（ＩＰ）アドレスおよびそのホストのすべてのホストロケータアドレス間のマッピングを保持するグローバルロケータアドレステーブルを格納するための記憶装置と
を備えることを特徴とするファブリックマネージャ。
【請求項１０】
請求項１から請求項７の何れかに記載のアドレス指定装置を備えることを特徴とするスイッチ。
【請求項１】
複数のツリーを取得するために、ネットワークトポロジ発見機能を使用して、各スイッチを順にルートとして、全ホストを含むツリーを作成するツリー作成手段と、
前記ツリー作成手段によって作成された複数のツリーから最低高さを有するツリーを選択するツリー選択手段と、
前記ツリー選択手段によって選択された最低高さを有する各ツリーに関し、ネットワーク内の各スイッチおよび各ホストにアドレスを割り当てるアドレス割り当て手段と
を備えることを特徴とするアドレス指定装置。
【請求項２】
１つのスイッチをルートとして、全ホストを含む複数のツリーが作成された場合、前記ツリー作成手段は、当該スイッチをルートとする複数のツリーのうち最低高さを有するツリーの１つを、作成されたツリーとして選択することを特徴とする請求項１に記載のアドレス指定装置。
【請求項３】
１つのスイッチをルートとして、全ホストを含む複数のツリーが作成された場合、前記ツリー作成手段は、当該複数のツリーのすべてを、作成されたツリーとして記録することを特徴とする請求項１に記載のアドレス指定装置。
【請求項４】
前記複数のツリーのうち最低高さを有するツリーが複数個ある場合、前記ツリー選択手段は、最低高さを有する当該複数個のツリーのすべてを選択することを特徴とする請求項１から請求項３の何れかに記載のアドレス指定装置。
【請求項５】
前記ツリー選択手段によって選択された最低高さＨを有する各ツリーについて、前記アドレス割り当て手段は、
ルートスイッチロケータアドレスを、ツリーのルートに位置するルートスイッチ（第０層スイッチ）に割り当て、
前記ルートスイッチに直接接続された第１層スイッチから開始して、第（ｉ−１）層スイッチに直接接続された第ｉ層スイッチの各々について、ルートスイッチから第ｉ層スイッチまでのすべてのパスを検出し、各パスについて、「ルートスイッチロケータアドレス．第１層スイッチアドレス．・・・．第ｉ層スイッチアドレス」（ここで、１≦ｉ≦Ｈ−２）の形式で、第ｉ層スイッチロケータアドレスを第ｉ層スイッチに割り当て、
「エッジスイッチロケータアドレス．ホストアドレス」（ここで、エッジスイッチはホストに直接接続された第ｋ層スイッチであり、０≦ｋ≦Ｈ−２）の形式で、ホストロケータアドレスを各ホストに割り当てる
ことを特徴とする請求項１から請求項４の何れかに記載のアドレス指定装置。
【請求項６】
前記第ｉ層スイッチアドレスは、第（ｉ−１）層スイッチの各第ｉ層スイッチに接続された個々のポートのポート番号であることを特徴とする請求項５に記載のアドレス指定装置。
【請求項７】
前記ホストアドレスは、エッジスイッチの各ホストに接続された個々のポートのポート番号であることを特徴とする請求項５又は請求項６に記載のアドレス指定装置。
【請求項８】
複数のツリーを取得するために、ネットワークトポロジ発見機能を使用して、各スイッチを順にルートとして、全ホストを含むツリーを作成するステップと、
作成された複数のツリーから最低高さを有するツリーを選択するステップと、
選択された最低高さを有する各ツリーに関し、ネットワーク内の各スイッチおよび各ホストにアドレスを割り当てるステップと
を備えることを特徴とするアドレス指定方法。
【請求項９】
請求項１から請求項７の何れかに記載のアドレス指定装置と、
各ホストのインターネットプロトコル（ＩＰ）アドレスおよびそのホストのすべてのホストロケータアドレス間のマッピングを保持するグローバルロケータアドレステーブルを格納するための記憶装置と
を備えることを特徴とするファブリックマネージャ。
【請求項１０】
請求項１から請求項７の何れかに記載のアドレス指定装置を備えることを特徴とするスイッチ。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【公開番号】特開２０１２−２０５３００（Ｐ２０１２−２０５３００Ａ）
【公開日】平成２４年１０月２２日（２０１２．１０．２２）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１１−２４１１５５（Ｐ２０１１−２４１１５５）
【出願日】平成２３年１１月２日（２０１１．１１．２）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＥＴＨＥＲＮＥＴ
【出願人】（５０５４１８８７０）エヌイーシー（チャイナ）カンパニー， リミテッド (108)
【氏名又は名称原語表記】ＮＥＣ（Ｃｈｉｎａ）Ｃｏ．，Ｌｔｄ．
【Ｆターム（参考）】
【公開日】平成２４年１０月２２日（２０１２．１０．２２）
【国際特許分類】
【出願番号】特願２０１１−２４１１５５（Ｐ２０１１−２４１１５５）
【出願日】平成２３年１１月２日（２０１１．１１．２）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＥＴＨＥＲＮＥＴ
【出願人】（５０５４１８８７０）エヌイーシー（チャイナ）カンパニー， リミテッド (108)
【氏名又は名称原語表記】ＮＥＣ（Ｃｈｉｎａ）Ｃｏ．，Ｌｔｄ．
【Ｆターム（参考）】
[ Back to top ]