データセンター向けの拡張可能なマルチキャスト転送方法および装置
【課題】データセンター向けのマルチキャスト転送装置および方法を提供する。
【解決手段】データセンター内のサーバーのマルチキャストアドレスは一連の連続マルチキャストアドレス内のアドレスであり、着信マルチキャストデータパケットを受信し、当該着信マルチキャストデータパケットのヘッダから宛先ＭＡＣアドレスが抽出し、抽出された宛先ＭＡＣアドレスと所定のマスク項目との間で論理ＡＮＤ演算を実行し、索引値を取得するルーティングクエリー実行エンジン１２０と、取得された索引値を使用して出力ポート系列を決定する転送エンジン１３０とにより、スイッチングファブリックユニット１４０が、決定された出力ポート系列に示されるポートから当該着信マルチキャストデータパケットを出力するようにラインカード１１０をスケジューリングする。
【解決手段】データセンター内のサーバーのマルチキャストアドレスは一連の連続マルチキャストアドレス内のアドレスであり、着信マルチキャストデータパケットを受信し、当該着信マルチキャストデータパケットのヘッダから宛先ＭＡＣアドレスが抽出し、抽出された宛先ＭＡＣアドレスと所定のマスク項目との間で論理ＡＮＤ演算を実行し、索引値を取得するルーティングクエリー実行エンジン１２０と、取得された索引値を使用して出力ポート系列を決定する転送エンジン１３０とにより、スイッチングファブリックユニット１４０が、決定された出力ポート系列に示されるポートから当該着信マルチキャストデータパケットを出力するようにラインカード１１０をスケジューリングする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータセンターに関し、特に、データセンター向けの拡張可能なマルチキャスト転送方式に関する。
【背景技術】
【０００２】
インターネットやクラウドコンピューティングサービスのようなアプリケーションの発達に伴い、データセンターはますます大規模化し、データセンターに設置されるマシンの数も増加の一途を辿っている（数万台規模）。データセンターにおける内部サーバー間のデータ通信は、インターネットを高密度に集中化した、規則性を有するネットワーク層トポロジーを形成する。そのため、データセンターのネットワークインフラストラクチャは、現在注目される研究テーマの一つとなっている。
【０００３】
マルチキャスト機能を適用できるアプリケーションはますます拡大しており（例：オンラインビデオ）、データのバックアップを始めとするデータセンター独自のニーズにも対応可能になっている。１対１のユニキャストルーティングとは対照的に、マルチキャストルーティングは主に１対多のサービスで利用される。つまり、１つのマルチキャストソースがサービスを提供する場合には、そのマルチキャストグループに参加しているすべてのメンバーがこのソースによって提供されるサービス（例：ビデオ、ファイルコピー）を利用することができるのである。データセンターは多数のサーバーを相互接続し、上位層のアプリケーションに効率的で耐障害性のあるルーティング転送サービスを提供する。そのため、マルチキャスト転送メカニズムに対する要求はますます厳しくなっている。しかし、現在のデータセンターで行われているマルチキャスト転送は未だにインターネットアプリケーションを対象としているため、転送テーブルが大きすぎる、スイッチのコスト効率が低い、拡張性に乏しい、といったいくつかの固有な問題を避けて通ることができない。これらの問題を鑑みると、転送テーブルの格納効率を向上させると同時に新たなルーティング検索機能が使用でき、データセンターが抱えるマルチキャスト転送の拡張性の問題を解消することのできる、新たな方法が必要とされている。
【０００４】
インターネット上ではマルチキャストよりもユニキャストの方が広く利用されている。そのため、ルーティングモジュールを設計する際には、ネットワーク機器ベンダーが提供するネットワーク機器はユニキャストルーティング向けに集中しており、マルチキャストルーティング機能は付随的にしか扱われていない。ユニキャストルーティングで使用されるＩＰｖ４アドレスの集約特性により、ルータで実行されるルーティングテーブル検索には最長一致法が採られている。例えば、宛先アドレスが「１．２．３．４」のデータパケットに対して、現在のルーティングテーブルに存在する「１．０．０．０／８」「１．２．０．０／１６」「１．２．３．０／２４」という３項目が一致したとすると、最長一致となる「１．２．３．０／２４」がヒット項目とみなされる。この最長一致の要件があるために、ルーティングテーブル検索はデータパケット転送プロセスの中で最も時間のかかる処理となっている。
【０００５】
ルーティングテーブル検索で時間計算量が高くなる最大の原因は、ルーティングテーブルの格納方法にある。表１は、不規則アドレスを格納したルーティングテーブルを示している。テーブルの各項目には１つのイーサネットアドレス（ＭＡＣアドレス）が索引付けされており、そのコンテンツとして、転送ポートを示すビットマップ（インタフェースビットマップ）が格納されている。ヒットした項目は、格納されたインタフェースビットマップに対応するポート（ビット１に対応するポート）に送信される。表１の索引は不規則なので、データパケットの宛先アドレスに基づいてクエリーを実行する際には、転送テーブル全体をトラバースする必要がある。この場合、時間計算量はＯ（Ｎ）である。
【表１】
【０００６】
表２は、ＭＡＣアドレスがソートされた、順序付けルーティングテーブルである。そのため、索引を検索する際には、２進探索法を使用することができる。したがって時間計算量はＯ（ｌｏｇ２Ｎ）である。
【表２】
【０００７】
ただし、時間計算量の点においては、これら２種類の格納方法と、ツリー構造格納方式を用いたルーティング検索とを用いたのでは、インターネットや大規模データセンターで要求される、ほぼＯ（１）というルーティングテーブル検索の要件に対応することはできない。
【０００８】
現在、ほとんどのネットワーク機器ベンダーは、ＴＣＡＭ（Ｔｅｒｎａｒｙ Ｃｏｎｔｅｎｔ Ａｄｄｒｅｓｓａｂｌｅ Ｍｅｍｏｒｙ：３値連想記憶装置）を適用してルーティング検索プロセスを実行している。ＴＣＡＭは、ルーティングテーブル並行検索方法のハードウェア実装であり、その時間計算量はＯ（１）になる。この場合、検索結果は、ルーティングテーブルを１度読み込んで最長一致を実行することにより得られる。これはＣＡＭをベースに開発される。ＣＡＭ記憶装置では各ビットが「０」と「１」という２つの状態しか持たないのが一般的であるのに対し、ＴＣＡＭでは各ビットは「０」と「１」に加えて「ＤＯＮ’Ｔ ＣＡＲＥ」（どちらでもよい）という３つ目の状態を持ち（それ故に「ｔｅｒｎａｒｙ」（３値）と呼ばれる）、マスクによって実装することができる。ＴＣＡＭの３つ目の状態を使うと、完全一致検索とあいまい検索の両方を実行することが可能になる。しかし、ＴＣＡＭはコスト効率が低く、拡張性にも劣る。下記の表３に示すように、ＴＣＡＭの価格と電力消費量はＳＲＡＭのそれよりも遙かに高い。
【表３】
【０００９】
そのため、「ＴＣＡＭをＤＲＡＭまたはＳＲＡＭに代えて、ルーティングテーブル検索においてＯ（１）に近い時間計算量を達成するにはどうしたらよいか」ということが、現在のネットワーク機器ベンダーにとっての主な研究テーマとなりつつある。ＤＲＡＭのアクセス速度（１０〜２０ｎｓ）はＳＲＡＭ（〜２ｎｓ）に比較して遅すぎる。電力消費量の面では、ＤＲＡＭとＳＲＡＭの間に大きな差はない。したがって、本研究ではＴＣＡＭをＳＲＡＭで代替することに焦点を当てる。
【００１０】
最長一致の問題はマルチキャストアドレスでは発生せず、データセンターネットワークはアドレスフィールドが一箇所に集中しているという特徴を有する。ＩＰｖ４アドレスは合計約４３億（２３２）個あり、マルチキャストアドレスは合計２億（１６×２２４）個ある。これらのアドレスは２２４．０．０．０〜２３９．２５５．２５５．２５５の範囲にある。したがって、インターネット上のマルチキャストルーティングおよび転送メカニズムで処理されるアドレスは２億個であり、アドレスの連続性は制御不能である。データセンターネットワークは、マルチキャストアドレスの個数はデータセンターネットワーク内のサーバー数に依存するという点で、インターネットとは異なる。現在の大規模データセンターが保有するサーバー数は１万〜１０万台の範囲にわたり、その多くは５万台前後に集中している。そのため、現在のデータセンターにおけるマルチキャスト需要に対応するには、１つの連続するマルチキャストアドレスフィールド（例えば、２３９．０．＊．＊／１６の場合、合計６５，５３６個のアドレスがある）で十分である。こうした少数アドレスと集中制御の特徴を鑑みれば、インターネットアプリケーション向けに設計されたＴＣＡＭの採用はコスト効率が低く拡張性も低いという問題につながるのは必至なので、データセンターネットワークにとっては、単純ゲート回路とＳＲＡＭとの組み合わせをもってＴＣＡＭを代替することが、マルチキャスト用ルーティングテーブル検索を効率的に実装するための方法となる。したがって、大規模データセンターネットワークにおけるマルチキャストルーティングテーブルのクエリーと転送に係るオーバーヘッドを削減し、コストパフォーマンスを低下させずに高度な拡張性を提供できる技術的解決法が必要とされている。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明は、データセンター向けの拡張可能なマルチキャスト転送方式を提案する。この方法では、Ｏ（１）の時間計算量を確保しながら、ＴＣＡＭに代えて単純ゲート回路が、ルーティングテーブルのクエリーを完了するための手段として採用される。このクエリー方法では、ルーティングテーブルを格納する必要はなく、マスクを用いた「ＡＮＤ」演算に基づいて転送テーブルの索引値を直接取得することができる。この回路のマスク部分は、データセンターネットワーク内のサーバー数によって変動する。
【００１２】
加えて本発明は、転送テーブル格納部分に、転送テーブル圧縮方法も備えている。この圧縮方法では、既存の転送テーブル内の同じテーブル項目の間で１つのコピーのみが保持され、同じテーブル項目のない転送テーブルを読み込む前に、別の索引配列を使用して１回のリダイレクトを実行することができる。
【課題を解決するための手段】
【００１３】
本発明の第１の態様によれば、データセンター向けのマルチキャスト転送装置であって、データセンター内のサーバーのマルチキャストアドレスが一連の連続マルチキャストアドレス内のアドレスであり、着信マルチキャストデータパケットを受信して、当該着信マルチキャストデータパケットのヘッダから宛先ＭＡＣアドレスを抽出するように構成されたラインカードと、ラインカードによって抽出された宛先ＭＡＣアドレスと所定のマスク項目との間で論理ＡＮＤ演算を実行して索引値を取得するように構成されたルーティングクエリーユニットと、ルーティングクエリーユニットによって取得された索引値を使用して出力ポート系列を決定するように構成された転送ユニットと、着信マルチキャストデータパケットを転送ユニットによって決定された出力ポート系列内に示されるポートから出力することである着信マルチキャストデータパケットのマルチキャスト転送を完了するためにラインカードをスケジューリングするように構成されたスイッチングファブリックユニットとを含む。
【００１４】
好ましい態様では、転送ユニットが、ルーティングクエリーユニットによって取得された索引値を転送テーブルの索引値として使用して、当該転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定し、あるいは、転送ユニットが、索引配列と転送テーブルとを含み、最初に、ルーティングクエリーユニットによって取得された索引値を当該索引配列の索引値として使用して、当該索引配列内の対応するテーブル項目に直接ヒットさせることにより当該転送テーブルの索引値を取得し、次に、当該索引配列がヒットした当該転送テーブルの索引値を使用して、転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定する。
【００１５】
好ましい態様では、所定のマスク項目は、データセンター内のサーバー総数に基づいて設定される。
【００１６】
好ましい態様では、データセンター内のサーバー総数が２１６以下の場合、一連の連続マルチキャストアドレスは下位１６ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘｆｆｆｆとして設定され、データセンター内のサーバー総数が２１７以下の場合、一連の連続マルチキャストアドレスは下位１７ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ１ｆｆｆｆとして設定され、データセンター内のサーバー総数が２１８以下の場合、一連の連続マルチキャストアドレスは下位１８ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ３ｆｆｆｆとして設定され、データセンター内のサーバー総数が２１９以下の場合、一連の連続マルチキャストアドレスは下位１９ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ７ｆｆｆｆとして設定され、データセンター内のサーバー総数が２２０以下の場合、一連の連続マルチキャストアドレスは下位２０ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘｆｆｆｆｆとして設定される。
【００１７】
転送ユニットは、ＳＲＡＭ上に転送テーブルを格納するか、またはＳＲＡＭ上に索引配列と転送テーブルとを格納するのが望ましい。
【００１８】
本発明の第２の態様によれば、データセンター向けのマルチキャスト転送方法であって、データセンター内のサーバーのマルチキャストアドレスが一連の連続マルチキャストアドレスにおけるアドレスであり、着信マルチキャストデータパケットを受信するステップと、着信マルチキャストデータパケットのヘッダから宛先ＭＡＣアドレスを抽出するステップと、抽出された宛先ＭＡＣアドレスと所定のマスク項目との間で論理ＡＮＤ演算を実行して索引値を取得するステップと、取得された索引値を使用して出力ポート系列を決定するステップと、決定された出力ポート系列内に示されるポートから着信マルチキャストデータパケットを出力するステップとを含む
【００１９】
好ましい態様では、取得された索引値を使用して出力ポート系列を決定するステップにおいて、取得された索引値を転送テーブルの索引値として使用して、当該転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定し、あるいは、最初に、取得された索引値を索引配列の索引値として使用して、当該索引配列内の対応するテーブル項目に直接ヒットさせることにより転送テーブルの索引値を取得し、次に、当該索引配列がヒットした当該転送テーブルの索引値を使用して、転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定する。
【００２０】
所定のマスク項目は、データセンター内のサーバー総数に基づいて設定されるのが望ましい。
【００２１】
データセンター内のサーバー総数が２１６以下の場合、一連の連続マルチキャストアドレスは下位１６ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘｆｆｆｆとして設定され、データセンター内のサーバー総数が２１７以下の場合、一連の連続マルチキャストアドレスは下位１７ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ１ｆｆｆｆとして設定され、データセンター内のサーバー総数が２１８以下の場合、一連の連続マルチキャストアドレスは下位１８ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ３ｆｆｆｆとして設定され、データセンター内のサーバー総数が２１９以下の場合、一連の連続マルチキャストアドレスは下位１９ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ７ｆｆｆｆとして設定され、データセンター内のサーバー総数が２２０以下の場合、一連の連続マルチキャストアドレスは下位２０ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘｆｆｆｆｆとして設定される。
【００２２】
ＳＲＡＭ上に転送テーブルを格納するか、またはＳＲＡＭ上に索引配列と転送テーブルとを格納するのが望ましい。
【００２３】
本発明の第３の態様によれば、ＯｐｅｎＦｌｏｗスイッチが提案される。このＯｐｅｎＦｌｏｗスイッチは、本発明の第１の態様によるマルチキャスト転送装置を含む。
【００２４】
本発明の第４の態様によれば、イーサネットスイッチが提案される。このイーサネットスイッチは、本発明の第１の態様によるマルチキャスト転送装置を含む。
【発明の効果】
【００２５】
本発明で提案されるデータセンター向けの拡張可能なマルチキャスト転送方式においては、複雑なＴＣＡＭに代えて単純ゲート回路を使用してマスク演算が実現される。第一に、このような実装では最長一致を実行する必要はなく、ルーティングテーブルを格納することも不要なため、コストとリソースのオーバーヘッド（電力消費量、回路複雑度等）はＴＣＡＭよりも遙かに低い。第二に、これはマスクの単純なＡＮＤ演算なので、データセンターネットワークを構成するサーバー数の変動に応じてマスク内のビット数を変えることができるため、拡張性が実現される。加えて、単純な設計であるため、本発明のクエリー演算に費やされる時間量はＳＲＡＭ上でのワンタイムアクセスの時間量（〜２ｎｓ）程度に留まり、ＴＣＡＭ（３〜５ｎｓ）上でのそれよりも少ない。加えて、本発明の転送テーブル圧縮方式では、リダイレクトの使用によりメモリー空間（最初のメモリー空間の１／２〜１／４）を節減することが可能となっている。これは、本発明は、同じ記憶領域であれば最初の記憶方式よりも多くのアドレス領域（２〜４倍）を確保できるため、データセンターネットワークの拡張性が大幅に高くなることを意味する。
【図面の簡単な説明】
【００２６】
上記およびその他の目的、特徴、並びに利点は、図面を参照しながら実施例について述べた以下の説明を読むことにより、さらに明らかになるであろう。
【００２７】
【図１】本発明によるデータセンター向けの拡張可能なマルチキャスト転送装置１０００の概略ブロック図である。
【図２】転送テーブル１３２の概略図である。
【図３】本発明によるデータセンター向けの拡張可能なマルチキャスト転送方法３０００の概略フローチャートである。
【図４】本発明によるデータセンター向けの拡張可能なマルチキャスト転送装置４０００の概略図である。
【図５】転送テーブルのリダイレクトにより記憶容量の圧縮を実現する方法を説明する概略図である。
【図６】ＯｐｅｎＦｌｏｗを使用して本発明を実現する場合の概略図である。
【図７】既存のイーサネット環境に本発明を実装する場合の概略図である。
【００２８】
本発明の図面においては、同一または類似の構造とステップは同一または類似の参照番号によって示されている。
【発明を実施するための形態】
【００２９】
以下では、上記の図面を参照して、本発明の好適な実施例を説明する。以下の説明においては、本発明に対する理解が曖昧になるのを回避するため、本発明に必須ではない詳細および機能を省略する。
【００３０】
上述したとおり、データセンターネットワークとインターネットの最大の相違点は、前者においてマルチキャストアドレスの個数はデータセンターネットワーク内のサーバー数に依存することである。現在の大規模データセンターが保有するサーバー数は１万〜１０万台の範囲にわたり、その多くは５万台前後に集中している。そのため、現在のデータセンターネットワークにおけるマルチキャスト需要に対応するには、１つの連続するマルチキャストアドレスフィールド（例えば、２３９．０．＊．＊／１６の場合、合計６５，５３６個のアドレスがある）で十分である。こうした特徴に着目して、本発明は、連続ＩＰアドレスフィールド内のＩＰアドレスを使用して、データセンターにおけるサーバーのマルチキャストアドレスを示すことを提案する。本発明では例えば、２３９．０．＊．＊／１６や１９２．１．＊．＊／１６の範囲内のアドレスを使用することができる。
【００３１】
ＩＰアドレスの選択（つまり、連続ＩＰアドレスフィールド内のＩＰアドレスを選択すること）という観点から見ると、同様に、マルチキャストＭＡＣアドレスは、対応してマルチキャストＩＰアドレスと同じ特徴を有すると考えられる。イーサネットにおいては、アドレスフィールド２３９．０．＊．＊／１６の範囲内のアドレスを使用でき、０１：００：５Ｅ：００：００：００〜０１：００：５Ｅ：ＦＦ：ＦＦ：ＦＦはマルチキャスト専用のＭＡＣアドレスフィールドである。上位２５ビットは固定（０１：００：５Ｅ）であり、下位２３ビットは対応するＩＰアドレスと等しい。マルチキャストアドレスのマッピングにおいては、ＩＰアドレスの下位２３ビットをＭＡＣアドレスの下位２３ビットに直接マップすることができる。これはつまり、マルチキャストアドレスの下位２３ビットは、上位層のＩＰマルチキャストアドレスの下位２３ビットと同じであることを意味する。インターネット環境においては、ＩＰアドレスのクラスＤでは、ＩＰアドレスの上位４ビットは固定（１１１０）である。そのため中間の５ビットはＭＡＣアドレスにマップされないが、これは、１個のマルチキャストＭＡＣアドレスが２５＝３２個の異なるＩＰアドレスに対応する可能性を生じさせる原因となる。この場合、マルチキャストアドレスの一意性を確立するには、ＭＡＣアドレスを使用することを除くと、マルチキャストＩＰアドレスを使用するしか方法はない。ただし、上述したように、データセンターネットワークのサーバー数は限られており（１０万台未満）、アドレスの連続性も制御可能なので、各マルチキャストアドレスは下位２３ビットによって区別することが可能である。その理由は、データセンター内のサーバー数は１０万台未満（＜２２３）なので、２３ビットでサーバーのマルチキャストアドレスを一意に識別できるためである（ほとんどの仕様において、データセンター内に存在するサーバー数は６５，５３６台以下なので、下位１６ビットのみが使用される。拡張することとなった場合には、２３ビットの使用が可能なので、２２３台のサーバーにアドレス指定を行うことができる）。最後に、このアドレスマッピングは、単一のインスタンスで記述することが可能である（マルチキャストアドレス２２４．１９３．１６．２はＭＡＣ層アドレス０１：００：５Ｅ：４１：１０：０２にマップされる）。ＭＡＣアドレスの上位２５ビットは固定（０１：００：５Ｅ）である。１９３の２進表現は１１０００００１であり、最上位ビットを除去すると１０００００１（すなわち０ｘ４１）になる。１６の１６進表現は０ｘ１０である。２の１６進表現は０ｘ０２である。このようにして、下位２３ビットを決定することができる。最後のＭＡＣアドレス（０１：００：５Ｅ：４１：１０：０２）が取得される。
【００３２】
図１は、本発明によるデータセンター向けの拡張可能なマルチキャスト転送装置１０００の概略図である。
【００３３】
図１に示すように、本発明によるデータセンター向けの拡張可能なマルチキャスト転送装置１０００は、ラインカード１１０と、ルーティングクエリー実行エンジン１２０と、転送エンジン１３０と、スイッチングファブリックユニット(switch fabric)１４０とを含む。
【００３４】
ラインカード１１０は、データパケットをルータ／スイッチから入出力するためのポータルであり、入出力待ち行列１１２とデータパケットプロセッサ１１４を主な構成要素とする複数のネットワークカード（図示せず）を含む。
・入出力待ち行列１１２：データパケットがネットワークカードを通って着信すると、まず入力待ち行列にキャッシュされ、処理を待機する。入力待ち行列が満杯になると、新たに着信するデータパケットはそのまま破棄される。データパケットの処理順序は、異なるサービス品質（ＱｏＳ：ｑｕａｌｉｔｙ ｏｆ ｓｅｒｖｉｃｅ）の要件に基づくデータパケット優先順位によって決まる。デフォルトでは、処理ルールはＦＩＦＯ（先入れ先出し）である。出力待ち行列も、これと同様である。
・データパケットプロセッサ１１４：これは主に、データパケットのヘッダから、データリンク層の宛先アドレス（すなわち、宛先ＭＡＣアドレス）とルーティング層の宛先アドレス（すなわち、宛先ＩＰアドレス）を抽出するために使用される。これら２個のアドレスは、それぞれデータリンク層エンジンとルーティング層エンジンの索引項目として使用される。
【００３５】
データセンターではサーバーのマルチキャストアドレスは連続ＩＰ／ＭＡＣアドレスフィールド内のアドレスを使用して示される可能性があるとの発明者の認識から、本発明ではルーティングクエリー実行エンジン１２０を単純な構造とし、十分な拡張性を持たせている。例えば、データセンターネットワーク内のサーバー数が６５，５３６（すなわち、２１６）台以下の場合には、マルチキャストアドレスは、プレフィックス長が１６の連続アドレスフィールドを使用して示すことができる。ルーティングクエリー実行エンジン１２０は、対応して設定されたマスク項目１２４との論理ＡＮＤ演算を実行する単純なＡＮＤゲート回路１２２によって、クエリー演算を実装することが可能である。
・ＡＮＤゲート回路１２２：ＡＮＤゲート回路１２２は、ラインカード１１２のデータパケットプロセッサ１１４からデータパケットの宛先アドレスを取得した後、宛先ＭＡＣアドレスとマスク項目内に格納されたマスクとの間でＡＮＤ演算を実行する（マルチキャストアドレス数は２１６以下なので、マスク内には１６個の有効ビットが存在する）。その結果得られる転送テーブルの索引値は、転送エンジン１３０に出力される。データセンターネットワーク内のアドレスは連続しているため、第２層の転送は主に、ネットワークトポロジーが判明した後に実行される。そのため、第２層のＭＡＣアドレスがＡＮＤゲート回路１２２によって処理される。
・マスク項目１２４：ここには、論理ＡＮＤ演算で使用されるマスク値が格納される。データセンターネットワーク内のサーバー数は２１６以下なので、１６ビットのマスク値を使用するので十分である。ここで、最も単純な方法は、１６ビットのマスクを０ｘｆｆｆｆで示すことである。こうすれば、ＡＮＤ演算により宛先アドレスそのものが得られる。データセンター内のアドレスは集中化され制御可能なため、各サーバーにより使用されるＭＡＣアドレスの下位１６ビットが互いに異なることを確保することができる。
【００３６】
マスク値は、既存のデータセンターネットワーク内のサーバー数の変動によって変化する可能性があることに注意する必要がある。ただし、最も単純なマスクを例にとると、マスク値は以下のようになる。すなわち、６５，５３６（２１６）個のマルチキャストアドレスが存在する場合には、マスクはそれに対応して０ｘｆｆｆｆに設定され、１３１，０７２（２１７）個のマルチキャストアドレスが存在する場合には、マスクはそれに対応して０ｘ１ｆｆｆｆに設定され、１，０４８，５７６（２２０）個のマルチキャストアドレスが存在する場合には、マスクはそれに対応して０ｘｆｆｆｆｆに設定される。そのためマスク値は、マスク項目１２４においてハードウェア実装に関して１回のリライト操作を実行するたけで、容易に調整することが可能である。ＴＣＡＭと比較して、この方法は実装が容易なだけではなく、コストとエネルギー消費量も遙かに少なくて済む。さらに、この方法によりデータセンターネットワークに十分な拡張性がもたらされる。
【００３７】
転送エンジン１３０は、ルーティングクエリ実行エンジン１２０によって出力された転送テーブルの索引値を、転送テーブル１３２内の対応するテーブル項目に直接ヒットさせて、出力ポート系列を取得することができる。
【００３８】
図２は、転送テーブル１３２（Ｇ２Ｉ）の概略図である。データセンターネットワークの第２層転送テーブルは、ビットマップを使用して実装される。テーブル項目番号のＧは、マルチキャストグループ数に等しい。すなわち、このシナリオにおいては、６５，５３６個のマルチキャストアドレス（１個のアドレスが１つのマルチキャストグループを表す）が存在するので、６５，５３６個のテーブル項目が存在する。各テーブル項目は、現在のスイッチに含まれるポート数Ｉのビットマップに対応する。現在のデータセンターネットワークでは主に６４ポートのスイッチが使用されているため、このビットマップは合計６４ビットを有する（各ビットは１つのポート番号を表す）。例えば、１０１１０１０１０１１０００００００００００００００００００００００００００００００００００００００００００００００００００００は、ポート１、３、４、６、８、１０および１１からの転送を表す。本発明においては、転送テーブルはＳＲＡＭを使用して格納できるので、高いコスト効率が達成される。マルチキャストアドレスは６５，５３６（６４Ｋ、１Ｋ＝１０２４）個存在し、スイッチは６４ポートを有するとして計算すると、各転送テーブルのサイズは６４Ｋ＊６４ｂｉｔｓ／８＝５１２ＫＢになる。表３に示すように、現在のスイッチの単一チップセット内にあるＳＲＡＭは平均して約４ＭＢのサイズを有するため、５１２ＫＢのＳＲＡＭであれば過剰なオーバーヘッドが発生することはない。また逆に、４ＭＢのＳＲＡＭを使用して転送テーブルを格納する場合には、スイッチにまだ６４ポートが残っているとすると、４ＭＢ／５１２ＫＢ＊６４Ｋ＝５１２Ｋ個のマルチキャストアドレスをサポートすることが可能である。つまり、データセンターネットワーク内のサーバー数が最大５１２Ｋまで増加した場合でも、本発明の転送エンジンはＯ（１）のクエリー速度を達成することができるのである。これにより、データセンターネットワークに十分な拡張性がもたらされる。
【００３９】
スイッチングファブリックユニット１４０は、データパケットの出力パスをスケジューリングするために使用される。同じラインカード１１０内の複数ネットワークカード間で行われるデータパケットの転送は、ラインカード１１０内のデータパケットプロセッサ１１４によってスケジューリングされる。一方、異なるラインカード間で行われるデータパケットの転送は、スイッチングファブリックユニット１４０によってスケジューリングされ、そのスケジューリングはネットワーク機器の他のリソースを共有することで実現される。
【００４０】
図３は、本発明によるデータセンター向けの拡張可能なマルチキャスト転送方法３０００の概略フローチャートである。
【００４１】
図３に示すように、ステップＳ３０１０において、ラインカード１１０が着信マルチキャストデータパケットを受信し、入出力待ち行列１１２の入力待ち行列にそれを登録する。その後、ステップＳ３０２０において、ラインカード１１００内のデータパケットプロセッサ１１４が着信マルチキャストデータパケットを処理し、着信マルチキャストデータパケットのヘッダから宛先ＭＡＣアドレスを抽出し、抽出された宛先ＭＡＣアドレスをルーティングクエリー実行エンジン１２０に送信する。ステップＳ３０３０において、ルーティングクエリー実行エンジン１２０が、受信された宛先ＭＡＣアドレスとマスク項目との間で論理ＡＮＤ演算を実行して、転送エンジン１３０の索引値を取得する。ステップＳ３０４０において、転送エンジン１３０は、ルーティングクエリー実行エンジン１２０によって出力された索引値を直接、転送テーブルの索引値として使用して、転送テーブル１３２内の対応する項目に直接ヒットさせ、出力ポート系列を取得する。ステップＳ３０５０において、スイッチングファブリックユニット１４０が、転送エンジン１３０によって決定された出力ポート系列に基づいて、着信マルチキャストデータパケットのマルチキャスト転送（すなわち、当該着信マルチキャストデータパケットを、出力ポート系列内に示されるポートから出力すること）を完了するためにラインカード１１０をスケジューリングする。
【００４２】
（前述の実施例の改良）
図２に示す転送テーブル１３２の読み取りは容易であるが（索引値に基づいてコンテンツを直接読み取ることができる）、データセンターのネットワークトポロジーは規則性を有するので、同じテーブル項目が多数存在する。多くの中間層スイッチ（ツリー構造内の葉ノードではないスイッチ）では、異なる宛先アドレスに対して同じ転送ポート系列が使用される。そのため、本発明はさらに、リダイレクト方式（ビットマップ共有）を使用して、転送テーブル上で圧縮格納を実行することを提案する。
【００４３】
図４は、本発明によるデータセンター向けの拡張可能なマルチキャスト転送装置４０００の概略ブロック図である。図１からの改良は転送エンジン１３０でのみ行われており、これは転送エンジン４３０として識別される。他の処理手段は図１と同じである。これらの同じ処理手段の詳細な説明は、不必要な反復を避けるため省略する。
【００４４】
転送エンジン４３０において階層的索引付けを実現するため、索引配列４３４が追加され、それに対応して転送テーブル１３２を修正して転送テーブル４３２とする。
【００４５】
演算において（図３のステップＳ３０４０に対応）、転送エンジン４３０は、ルーティングクエリー実行エンジン１２０によって出力された索引値を索引配列４３４の索引値として使用して（転送テーブルの索引値は、索引配列４３４内の各テーブル項目を使用して格納される）、索引配列４３４内の対応するテーブル項目に直接ヒットさせ、転送テーブルの索引値を取得する。その後、転送エンジン４３０は、索引配列４３４がヒットした転送テーブルの索引値を再使用して、転送テーブル４３０内の対応するテーブル項目に直接ヒットさせ、出力ポート系列を取得する。このような２段階の索引付けにより、出力ポート系列がヒットされ、同時に記憶容量の圧縮が実現される。
【００４６】
図５は、転送テーブルのリダイレクトにより記憶容量の圧縮を実現する方法を説明する概略図である。
【００４７】
図５において、Ｇ２Ｍは索引配列４３４であり、Ｍ２Ｉは転送テーブル４３２である。Ｇ２Ｍの系列長はマルチキャストグループ数に等しい。このシナリオには６５，５３６個の素子が存在し、各々がＭ２Ｉの索引値を保持している。したがって、転送テーブルにヒットさせるためには２段階の索引付けが必要とされる（第１の索引付けはＧ２Ｍで、第２の索引付けはＭ２Ｉ）。最初の転送テーブルには多数の同じテーブル項目が存在するため（図２）、記憶領域の圧縮を実行する目的で索引配列４３４が導入されている。圧縮された転送テーブル４３２（すなわち、Ｍ２Ｉ）において、最初の転送テーブルと同様に各テーブル項目は１つのビットマップを一意に表現するので、ビットマップ数はスイッチ内のポート数に等しい。図５の矢印は、リダイレクトプロセスを表す。すなわち、ルーティングクエリー実行エンジン１２０が２つの異なるデータパケットのＭＡＣアドレスをクエリーすると、マスクのＡＮＤ演算によって２つの異なる索引項目が取得される。これら２つの異なる索引項目は、それぞれマルチキャストグループ１とマルチキャストグループ２である。次に、これら２つの索引項目に基づいて対応する２つの素子値が索引配列４３４から読み取られるので、転送テーブルに対して複数の同じ索引値が取得される可能性がある。これは、記憶領域の圧縮前には、２つのマルチキャストグループに対応する転送テーブル１３２のテーブル項目が、同じコンテンツを保持している可能性があることを意味する。
【００４８】
ＣＰＵによる１回の読み取り操作を円滑化するため、索引配列Ｇ２Ｍはその素子の幅を位置合わせルール（Ｌは２バイトまたは４バイトのいずれか）に基づいて調整する。３２ビットＣＰＵの場合、１回の読み取り操作で４バイトが消費される。この場合、Ｌが２バイトであれば２個の素子を読み取ることができ、Ｌが４バイトであれば１個の素子を読み取ることができる。これによりアクセス効率が向上する（Ｌが３バイトの場合は、各読み取りの位置合わせは不可能である）。加えて、図５から分かるように、転送テーブル４３２の項目番号Ｎの最大値は、Ｌの幅（すなわち、Ｍ＝２Ｌ）に関係している。Ｌが２バイトの場合、転送テーブル４３２は最大Ｍ＝２１６＝６４Ｋの項目を保持することができる。Ｌが４バイトの場合、転送テーブル４３２は最大Ｍ＝２３２＝４Ｇの項目を保持することができる。すなわち、Ｌが２バイトと４バイトのときは、データセンター内でそれぞれ６４Ｋと４Ｇのサーバーをサポートすることが可能である。したがって、本発明による索引配列の位置合わせルールは、ＣＰＵアクセス操作を円滑化するだけでなく、十分な拡張性も同時にもたらすのである。
【００４９】
２段階の索引付け操作では、リダイレクトが実行されるため、最初の直接索引付け転送テーブルよりもアクセス操作が１回多くなる。ここでは格納のためにＳＲＡＭが採用されているので、１．５〜２ｎｓの時間が余分に必要となる。しかし、こうした余分の時間を費やしてもなお、ＴＣＡＭよりも所要時間は短い。加えて、本発明により転送テーブルの記憶領域が節減される。
【００５０】
図２において、最初の圧縮されていない転送テーブル１３２のテーブル項目数Ｇは、マルチキャストグループ数（例えば、６４Ｋ）に等しい。転送テーブル１３２のこれらの項目の各々は、スイッチ内のポート数（例：６４ポート）に等しい幅を有するビットマップである。図５に示す圧縮して格納された索引配列４３４の場合、索引配列４３４のテーブル項目数Ｇはマルチキャストグループ数（例えば、６４Ｋ）に等しく、各素子は幅Ｌを有する（例えば、ＣＰＵ位置合わせルールによれば、Ｌは２バイトである（２１６＝６４Ｋ））。図５の転送テーブル４３２においては、圧縮された転送テーブル４３２のテーブル項目数はＮである。これらのテーブル項目の各々はビットマップであり、スイッチ内のポート数（例：６４ポート）に等しい幅Ｉを有する。したがって、圧縮領域のオーバーヘッドと最初の領域のオーバーヘッドの比は、式（１）によって計算できる。
【数１】
【００５１】
本発明の典型的な適用例（Ｌ＝２ＢおよびＩ＝６４ビット＝８Ｂ）では、Ｌ ／ Ｉ＝１／４となる。圧縮率Ｎ／Ｇは、転送テーブル１３２での同じテーブル項目の出現頻度によって決まる（平均して２つおきのテーブル項目が同じであれば同じテーブル項目の出現頻度は２であり、４つおきのテーブル項目が同じであれば同じテーブル項目の出現頻度は４である）。データセンターネットワークの実際のトポロジーのツリー構造においては、同じテーブル項目の出現頻度は平均して４〜８の範囲なので、圧縮率Ｎ／Ｇは１／８〜１／４の範囲であり、式（１）は［１／４，１／２］の値をとることができる。そのため、最初の転送テーブル１３２と比較して、本発明による圧縮された索引配列４３４と転送テーブル４３２は、最初の所要領域の１／４〜１／２しか必要としない。したがって、同じ記憶領域の場合であれば、この改良版は前述の実施例の２〜４倍のマルチキャストアドレス領域をサポートできるので、データセンターネットワークの拡張性が大幅に向上する。
【００５２】
最後に、本発明の実装における２つの具体例について説明する。一方の具体例は広く普及したＯｐｅｎＦｌｏｗ技術を使用して実装することができ、もう一方の具体例は既存のイーサネット環境内に展開することができる。
【００５３】
（１）ＯｐｅｎＦｌｏｗは、研究者が実際の要件に応じて新しいネットワークプロトコルやネットワーク実験を実装および展開することを可能にするオープンソース技術である。ネットワーク機器ベンダーによって提供されるネットワーク機器はすべて「ブラックボックス」なので、ユーザーが行えるのはＩＰアドレスやＶＬＡＮを設定するといった構成作業に限られ、実験的にプログラミングを実行することはできない。そのため、ネットワーク機器のプログラミングインタフェースをオープンにすることは、主要な研究者にとって火急の課題となっていた。ＯｐｅｎＦＬｏｗはまさにそれを実現する技術である。これはスタンフォード大学によって開発されたオープンソース製品であり、ソフトウェアによってルーティングと転送の機能を実現することが可能である。ＯｐｅｎＦｌｏｗは、マルチカードＰＣがスイッチとして扱われるＬｉｎｕｘホストに直接展開できるだけでなく、ＮＥＣやＪＵＮＩＰＥＲ製製品のような市販のスイッチにもロードされている。ユーザーは研究要件に従ってＯｐｅｎＦｌｏｗ上でプログラミングできるので、研究者によるネットワーク実験の実施が容易になった。
【００５４】
図６は、ＯｐｅｎＦｌｏｗを使用して本発明を実現する場合の概略図である。
【００５５】
ＯｐｅｎＦｌｏｗスイッチ６１０内の転送ルールと転送テーブルは、リモートコントローラ６２０によって展開できる。新しいルーティングプロトコル等はすべて、コントローラ６２０上のプログラミングにより実装される。コントロールプレーンの情報交換は、ＯｐｅｎＦｌｏｗスイッチ６１０とコントローラ６２０間で、暗号化されたＳＳＬセキュリティプロトコルを介して実行できる。ＯｐｅｎＦｌｏｗスイッチ６１０自体は、データパケットの転送のみを担当する。図６に示すように、送信機６３０は宛先アドレス２３９．０．０．６を使用してマルチキャストデータパケットを送信する。マルチキャストアドレス指定ルールによれば、対応する宛先ＭＡＣアドレスは０１：００：５ Ｅ：００：００：０６なので、ＡＲＰテーブルは図６に示すような内容となる。データパケットを受信した後、ＯｐｅｎＦｌｏｗスイッチ６１０はＯｐｅｎＦｌｏｗの特性に従って、ＭＡＣアドレスの下位１６ビットが直接、転送テーブルの索引値として使用されるように、転送ルールをプログラムミングする。これは、マスク値０ｘｆｆｆｆと宛先ＭＡＣアドレスの下位１６ビットとをＡＮＤ演算したのと同じ結果となる。ここで、宛先ＭＡＣアドレスの下位１６ビット（図６の丸で囲んだ部分）は０ｘ０００６なので、索引値は６である。したがって、転送は転送テーブルの６番目の項目に示されるポートから直接実行される。図６のＯｐｅｎＦｌｏｗスイッチ６１０、コントローラ６２０、および送信機（ＰＣ）６３０は、それぞれ以下の機能を実装することができる。
【００５６】
ＯｐｅｎＦｌｏｗスイッチ６１０
・ＯｐｅｎＦｌｏｗスイッチ６１０は、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ）を適用することにより、ルーティングクエリー実行エンジンの機能を実装することができる。ＯｐｅｎＦｌｏｗはハードウェアＦＰＧＡ上でのプログラミングをサポートしているため、転送テーブルの直接読み取り、転送テーブルのリダイレクトと読み取り、ビットマップで示されるポートからの直接転送といったデータプレーンの機能はすべて、高水準言語（例：Ｃ言語）を使用してプログラミングし、ハードウェア内に実装することが可能である。
・転送テーブルはＯｐｅｎＦｌｏｗスイッチ６１０内に格納されるが、ＳＳＬプロトコルを介してコントローラ６２０から制御することができる。
【００５７】
コントローラ６２０：
・コントローラ６２０は、ＯｐｅｎＦｌｏｗスイッチ６１０内に格納される転送テーブルに対して、追加、削除、修正、検索の各操作を実行する。
・コントローラ６２０は、アドレスの衝突が発生しないように、データセンターネットワーク内のサーバーにマルチキャストアドレスを割り当てる。これにより各サーバーのマルチキャストアドレスの一意性が確保され、その結果、スイッチの転送ルール内で複数一致が発生しないようになる（例えば、各宛先ＭＡＣアドレスの下位１６ビットは一意である）。
【００５８】
ＰＣ６３０：
・ＰＣ６３０はまず、中間スイッチノード６１０に転送テーブルの項目を確立させるために、通信前にマルチキャスト要求メッセージを送信する。
・ユーザーはサーバー側のサービス開発を修正する必要はなく、最初のマルチキャストソケットに従ってプログラムを実行する。
ｓｅｔｓｏｃｋｏｐｔ（ｓｏｃｋｅｔ，ＩＰＰＲＯＴＯ＿ＩＰ，ＩＰ＿ＡＤＤ＿ＭＥＭＢＥＲＳＨＩＰ，．．．）．
【００５９】
（２）図７は、既存のイーサネット環境に本発明を実装する場合の概略図である。ホスト７３０−１〜７３０−ｎは、アドレス衝突を回避するために、未使用のマルチキャストアドレスを検出する役割を担う。アドレスの割り当てと転送テーブルの制御を行うＯｐｅｎＦｌｏｗコントローラ６１０のような機器はないので、主にスイッチ７１０−１〜７１０−ｍとＰＣ７３０−１〜７３０−ｎがマルチキャスト転送プロセスを実装するために使用される。
【００６０】
スイッチ７１０−１〜７１０−ｍ：
・ＯｐｅｎＦｌｏｗと同様に、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ）を適用することにより、ルーティングクエリー実行エンジンの機能を実装することができる。市販のスイッチとＦＰＧＡを使用しているので、転送テーブルの直接読み取り、転送テーブルのリダイレクトと読み取り、ビットマップで示されるポートからの直接転送といったデータプレーンの機能を実行するために、専用ハードウェアプログラミング言語（例：ＶｅｒｉｌｏｇやＶＨＤＬ）を採用することができる。
【００６１】
ＰＣ７３０−１〜７３０−ｎ：
・アドレス割り当て用のコントローラはないので、ホスト７３０−１〜７３０−ｎが自機においてマルチキャストアドレスを検出し、自機のマルチキャストアドレスが使用されないことを確保する必要がある。
・ユーザーはサーバー側のサービス開発を修正する必要はなく、最初のマルチキャストソケットに従ってプログラムを実行する。
ｓｅｔｓｏｃｋｏｐｔ（ｓｏｃｋｅｔ，ＩＰＰＲＯＴＯ＿ＩＰ，ＩＰ＿ＡＤＤ＿ＭＥＭＢＥＲＳＨＩＰ，．．．）．
【００６２】
本開示の他の構成としては、方法実施例のステップおよび動作を実行するソフトウェアプログラムが挙げられる。以下ではまずその概要を述べ、次に詳細に説明する。具体的には、１つの実施例は、符号化されたコンピュータプログラム論理を格納するコンピュータ可読媒体を含むコンピュータプログラム製品である。コンピュータプログラム論理は、コンピューティング装置上で実行されると、上記の拡張可能なマルチキャスト転送方式を提供するための操作を提供する。コンピュータプログラム論理は、それがコンピューティングシステムの少なくとも１つのプロセッサ上で実行されたときに、当該少なくとも１つのプロセッサが本発明の実施例の動作（方法）を実行することを可能にする。本発明のこうした構成は、典型的には、光媒体（例：ＣＤ−ＲＯＭ）、ソフトディスク、ハードディスク等のコンピュータ可読媒体上で提供または符号化されたソフトウェア、コードもしくはデータ構造体、１つ以上のＲＯＭ、ＲＡＭもしくはＰＲＯＭチップに格納されたファームウェアもしくはマイクロコード等のその他の媒体、特定用途向け集積回路（ＡＳＩＣ）、または単一もしくは複数モジュール上のダウンロード可能なソフトウェアイメージおよび共有データベース等として提供される。ソフトウェア、ハードウェア等の構成は、コンピューティング装置上にインストールされることにより、コンピューティング装置内の１つ以上のプロセッサを介して、本発明の実施例による技法を実行することができる。また、本発明のノードおよびホストは、ソフトウェアプロセスを、例えば他のエンティティ内の一連のデータ通信装置やコンピューティング装置と共に稼働させることによっても提供することができる。本発明のノードおよびホストはさらに、複数のデータ通信装置の複数のソフトウェアプロセスに分散させたり、一連の小型専用コンピュータ上で稼働するすべてのソフトウェアプロセスに分散させたり、あるいは単一のコンピュータ上で稼働するすべてのソフトウェアプロセスに分散させることができる。
【００６３】
本発明の実施例は、ソフトウェアプログラム、１台のデータ処理装置上のソフトウェアおよびハードウェア、独立したソフトウェア、または独立した回路として実装できることは理解されるであろう。
【００６４】
上記では、本発明を好適な実施例を使用して説明してきたが、本発明の適用範囲には、本発明の精神および原則に則ったあらゆる変更、置換、改良等も内包されることは理解されるであろう。したがって、本発明の範囲は上記の具体的な実施例に限定されず、付記した請求項によってのみ限定される。
【００６５】
さらに、上記実施形態の一部又は全部は、以下の付記のようにも記載されうるが、これに限定されない。
【００６６】
（付記１）
データセンター向けのマルチキャスト転送装置であって、
データセンター内のサーバーのマルチキャストアドレスが一連の連続マルチキャストアドレス内のアドレスであり、
着信マルチキャストデータパケットを受信して、当該着信マルチキャストデータパケットのヘッダから宛先ＭＡＣアドレスを抽出するように構成されたラインカードと、
前記ラインカードによって抽出された宛先ＭＡＣアドレスと所定のマスク項目との間で論理ＡＮＤ演算を実行して索引値を取得するように構成されたルーティングクエリーユニットと、
前記ルーティングクエリーユニットによって取得された索引値を使用して出力ポート系列を決定するように構成された転送ユニットと、
前記着信マルチキャストデータパケットを転送ユニットによって決定された出力ポート系列内に示されるポートから出力することである前記着信マルチキャストデータパケットのマルチキャスト転送を完了するために前記ラインカードをスケジューリングするように構成されたスイッチングファブリックユニットと
を備えることを特徴とするマルチキャスト転送装置。
【００６７】
（付記２）
前記転送ユニットが、前記ルーティングクエリーユニットによって取得された索引値を転送テーブルの索引値として使用して、当該転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定し、
あるいは、前記転送ユニットが、索引配列と転送テーブルとを含み、最初に、前記ルーティングクエリーユニットによって取得された索引値を当該索引配列の索引値として使用して、当該索引配列内の対応するテーブル項目に直接ヒットさせることにより当該転送テーブルの索引値を取得し、次に、当該索引配列がヒットした当該転送テーブルの索引値を使用して、転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定する
ことを特徴とする付記１に記載のマルチキャスト転送装置。
【００６８】
（付記３）
所定のマスク項目は、前記データセンター内のサーバー総数に基づいて設定されることを特徴とする付記１又は付記２に記載のマルチキャスト転送装置。
【００６９】
（付記４）
前記データセンター内のサーバー総数が２１６以下の場合、一連の連続マルチキャストアドレスは下位１６ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２１７以下の場合、一連の連続マルチキャストアドレスは下位１７ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ１ｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２１８以下の場合、一連の連続マルチキャストアドレスは下位１８ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ３ｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２１９以下の場合、一連の連続マルチキャストアドレスは下位１９ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ７ｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２２０以下の場合、一連の連続マルチキャストアドレスは下位２０ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘｆｆｆｆｆとして設定される
ことを特徴とする付記３に記載のマルチキャスト転送装置。
【００７０】
（付記５）
前記転送ユニットは、ＳＲＡＭ上に前記転送テーブルを格納するか、またはＳＲＡＭ上に前記索引配列と前記転送テーブルとを格納することを特徴とする付記１から付記４の何れかに記載のマルチキャスト転送装置。
【００７１】
（付記６）
データセンター向けのマルチキャスト転送方法であって、
前記データセンター内のサーバーのマルチキャストアドレスが一連の連続マルチキャストアドレスにおけるアドレスであり、
着信マルチキャストデータパケットを受信するステップと、
前記着信マルチキャストデータパケットのヘッダから宛先ＭＡＣアドレスを抽出するステップと、
抽出された宛先ＭＡＣアドレスと所定のマスク項目との間で論理ＡＮＤ演算を実行して索引値を取得するステップと、
取得された索引値を使用して出力ポート系列を決定するステップと、
決定された出力ポート系列内に示されるポートから前記着信マルチキャストデータパケットを出力するステップと
を含むことを特徴とするマルチキャスト転送方法。
【００７２】
（付記７）
取得された索引値を使用して出力ポート系列を決定するステップにおいて、
取得された索引値を転送テーブルの索引値として使用して、当該転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定し、
あるいは、最初に、取得された索引値を索引配列の索引値として使用して、当該索引配列内の対応するテーブル項目に直接ヒットさせることにより転送テーブルの索引値を取得し、次に、当該索引配列がヒットした当該転送テーブルの索引値を使用して、転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定する
ことを特徴とする付記６に記載のマルチキャスト転送方法。
【００７３】
（付記８）
所定のマスク項目は、前記データセンター内のサーバー総数に基づいて設定されることを特徴とする付記６又は付記７に記載のマルチキャスト転送方法。
【００７４】
（付記９）
前記データセンター内のサーバー総数が２１６以下の場合、一連の連続マルチキャストアドレスは下位１６ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２１７以下の場合、一連の連続マルチキャストアドレスは下位１７ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ１ｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２１８以下の場合、一連の連続マルチキャストアドレスは下位１８ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ３ｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２１９以下の場合、一連の連続マルチキャストアドレスは下位１９ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ７ｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２２０以下の場合、一連の連続マルチキャストアドレスは下位２０ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘｆｆｆｆｆとして設定される
ことを特徴とする付記８に記載のマルチキャスト転送方法。
【００７５】
（付記１０）
ＳＲＡＭ上に前記転送テーブルを格納するか、またはＳＲＡＭ上に前記索引配列と前記転送テーブルとを格納することを特徴とする付記６から付記９の何れかに記載のマルチキャスト転送方法。
【００７６】
（付記１１）
付記１から付記５の何れかに記載のマルチキャスト転送装置を含むことを特徴とするＯｐｅｎＦｌｏｗスイッチ。
【００７７】
（付記１２）
付記１から付記５の何れかに記載のマルチキャスト転送装置を含むことを特徴とするイーサネットスイッチ。
【符号の説明】
【００７８】
１１０：ラインカード
１１２：入出力待ち行列
１１４：データパケットプロセッサ
１２０：ルーティングクエリー実行エンジン
１２２：ＡＮＤゲート回路
１２４：マスク項目
１３０：転送エンジン
１３２：転送テーブル
１４０：スイッチングファブリックユニット
１０００：マルチキャスト転送装置
４３０：転送エンジン
４３２：転送テーブル
４３４：索引配列
４０００：マルチキャスト転送装置
６１０：ＯｐｅｎＦｌｏｗスイッチ
６２０：コントローラ
６３０：送信機
７１０−１：スイッチ
【技術分野】
【０００１】
本発明はデータセンターに関し、特に、データセンター向けの拡張可能なマルチキャスト転送方式に関する。
【背景技術】
【０００２】
インターネットやクラウドコンピューティングサービスのようなアプリケーションの発達に伴い、データセンターはますます大規模化し、データセンターに設置されるマシンの数も増加の一途を辿っている（数万台規模）。データセンターにおける内部サーバー間のデータ通信は、インターネットを高密度に集中化した、規則性を有するネットワーク層トポロジーを形成する。そのため、データセンターのネットワークインフラストラクチャは、現在注目される研究テーマの一つとなっている。
【０００３】
マルチキャスト機能を適用できるアプリケーションはますます拡大しており（例：オンラインビデオ）、データのバックアップを始めとするデータセンター独自のニーズにも対応可能になっている。１対１のユニキャストルーティングとは対照的に、マルチキャストルーティングは主に１対多のサービスで利用される。つまり、１つのマルチキャストソースがサービスを提供する場合には、そのマルチキャストグループに参加しているすべてのメンバーがこのソースによって提供されるサービス（例：ビデオ、ファイルコピー）を利用することができるのである。データセンターは多数のサーバーを相互接続し、上位層のアプリケーションに効率的で耐障害性のあるルーティング転送サービスを提供する。そのため、マルチキャスト転送メカニズムに対する要求はますます厳しくなっている。しかし、現在のデータセンターで行われているマルチキャスト転送は未だにインターネットアプリケーションを対象としているため、転送テーブルが大きすぎる、スイッチのコスト効率が低い、拡張性に乏しい、といったいくつかの固有な問題を避けて通ることができない。これらの問題を鑑みると、転送テーブルの格納効率を向上させると同時に新たなルーティング検索機能が使用でき、データセンターが抱えるマルチキャスト転送の拡張性の問題を解消することのできる、新たな方法が必要とされている。
【０００４】
インターネット上ではマルチキャストよりもユニキャストの方が広く利用されている。そのため、ルーティングモジュールを設計する際には、ネットワーク機器ベンダーが提供するネットワーク機器はユニキャストルーティング向けに集中しており、マルチキャストルーティング機能は付随的にしか扱われていない。ユニキャストルーティングで使用されるＩＰｖ４アドレスの集約特性により、ルータで実行されるルーティングテーブル検索には最長一致法が採られている。例えば、宛先アドレスが「１．２．３．４」のデータパケットに対して、現在のルーティングテーブルに存在する「１．０．０．０／８」「１．２．０．０／１６」「１．２．３．０／２４」という３項目が一致したとすると、最長一致となる「１．２．３．０／２４」がヒット項目とみなされる。この最長一致の要件があるために、ルーティングテーブル検索はデータパケット転送プロセスの中で最も時間のかかる処理となっている。
【０００５】
ルーティングテーブル検索で時間計算量が高くなる最大の原因は、ルーティングテーブルの格納方法にある。表１は、不規則アドレスを格納したルーティングテーブルを示している。テーブルの各項目には１つのイーサネットアドレス（ＭＡＣアドレス）が索引付けされており、そのコンテンツとして、転送ポートを示すビットマップ（インタフェースビットマップ）が格納されている。ヒットした項目は、格納されたインタフェースビットマップに対応するポート（ビット１に対応するポート）に送信される。表１の索引は不規則なので、データパケットの宛先アドレスに基づいてクエリーを実行する際には、転送テーブル全体をトラバースする必要がある。この場合、時間計算量はＯ（Ｎ）である。
【表１】
【０００６】
表２は、ＭＡＣアドレスがソートされた、順序付けルーティングテーブルである。そのため、索引を検索する際には、２進探索法を使用することができる。したがって時間計算量はＯ（ｌｏｇ２Ｎ）である。
【表２】
【０００７】
ただし、時間計算量の点においては、これら２種類の格納方法と、ツリー構造格納方式を用いたルーティング検索とを用いたのでは、インターネットや大規模データセンターで要求される、ほぼＯ（１）というルーティングテーブル検索の要件に対応することはできない。
【０００８】
現在、ほとんどのネットワーク機器ベンダーは、ＴＣＡＭ（Ｔｅｒｎａｒｙ Ｃｏｎｔｅｎｔ Ａｄｄｒｅｓｓａｂｌｅ Ｍｅｍｏｒｙ：３値連想記憶装置）を適用してルーティング検索プロセスを実行している。ＴＣＡＭは、ルーティングテーブル並行検索方法のハードウェア実装であり、その時間計算量はＯ（１）になる。この場合、検索結果は、ルーティングテーブルを１度読み込んで最長一致を実行することにより得られる。これはＣＡＭをベースに開発される。ＣＡＭ記憶装置では各ビットが「０」と「１」という２つの状態しか持たないのが一般的であるのに対し、ＴＣＡＭでは各ビットは「０」と「１」に加えて「ＤＯＮ’Ｔ ＣＡＲＥ」（どちらでもよい）という３つ目の状態を持ち（それ故に「ｔｅｒｎａｒｙ」（３値）と呼ばれる）、マスクによって実装することができる。ＴＣＡＭの３つ目の状態を使うと、完全一致検索とあいまい検索の両方を実行することが可能になる。しかし、ＴＣＡＭはコスト効率が低く、拡張性にも劣る。下記の表３に示すように、ＴＣＡＭの価格と電力消費量はＳＲＡＭのそれよりも遙かに高い。
【表３】
【０００９】
そのため、「ＴＣＡＭをＤＲＡＭまたはＳＲＡＭに代えて、ルーティングテーブル検索においてＯ（１）に近い時間計算量を達成するにはどうしたらよいか」ということが、現在のネットワーク機器ベンダーにとっての主な研究テーマとなりつつある。ＤＲＡＭのアクセス速度（１０〜２０ｎｓ）はＳＲＡＭ（〜２ｎｓ）に比較して遅すぎる。電力消費量の面では、ＤＲＡＭとＳＲＡＭの間に大きな差はない。したがって、本研究ではＴＣＡＭをＳＲＡＭで代替することに焦点を当てる。
【００１０】
最長一致の問題はマルチキャストアドレスでは発生せず、データセンターネットワークはアドレスフィールドが一箇所に集中しているという特徴を有する。ＩＰｖ４アドレスは合計約４３億（２３２）個あり、マルチキャストアドレスは合計２億（１６×２２４）個ある。これらのアドレスは２２４．０．０．０〜２３９．２５５．２５５．２５５の範囲にある。したがって、インターネット上のマルチキャストルーティングおよび転送メカニズムで処理されるアドレスは２億個であり、アドレスの連続性は制御不能である。データセンターネットワークは、マルチキャストアドレスの個数はデータセンターネットワーク内のサーバー数に依存するという点で、インターネットとは異なる。現在の大規模データセンターが保有するサーバー数は１万〜１０万台の範囲にわたり、その多くは５万台前後に集中している。そのため、現在のデータセンターにおけるマルチキャスト需要に対応するには、１つの連続するマルチキャストアドレスフィールド（例えば、２３９．０．＊．＊／１６の場合、合計６５，５３６個のアドレスがある）で十分である。こうした少数アドレスと集中制御の特徴を鑑みれば、インターネットアプリケーション向けに設計されたＴＣＡＭの採用はコスト効率が低く拡張性も低いという問題につながるのは必至なので、データセンターネットワークにとっては、単純ゲート回路とＳＲＡＭとの組み合わせをもってＴＣＡＭを代替することが、マルチキャスト用ルーティングテーブル検索を効率的に実装するための方法となる。したがって、大規模データセンターネットワークにおけるマルチキャストルーティングテーブルのクエリーと転送に係るオーバーヘッドを削減し、コストパフォーマンスを低下させずに高度な拡張性を提供できる技術的解決法が必要とされている。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明は、データセンター向けの拡張可能なマルチキャスト転送方式を提案する。この方法では、Ｏ（１）の時間計算量を確保しながら、ＴＣＡＭに代えて単純ゲート回路が、ルーティングテーブルのクエリーを完了するための手段として採用される。このクエリー方法では、ルーティングテーブルを格納する必要はなく、マスクを用いた「ＡＮＤ」演算に基づいて転送テーブルの索引値を直接取得することができる。この回路のマスク部分は、データセンターネットワーク内のサーバー数によって変動する。
【００１２】
加えて本発明は、転送テーブル格納部分に、転送テーブル圧縮方法も備えている。この圧縮方法では、既存の転送テーブル内の同じテーブル項目の間で１つのコピーのみが保持され、同じテーブル項目のない転送テーブルを読み込む前に、別の索引配列を使用して１回のリダイレクトを実行することができる。
【課題を解決するための手段】
【００１３】
本発明の第１の態様によれば、データセンター向けのマルチキャスト転送装置であって、データセンター内のサーバーのマルチキャストアドレスが一連の連続マルチキャストアドレス内のアドレスであり、着信マルチキャストデータパケットを受信して、当該着信マルチキャストデータパケットのヘッダから宛先ＭＡＣアドレスを抽出するように構成されたラインカードと、ラインカードによって抽出された宛先ＭＡＣアドレスと所定のマスク項目との間で論理ＡＮＤ演算を実行して索引値を取得するように構成されたルーティングクエリーユニットと、ルーティングクエリーユニットによって取得された索引値を使用して出力ポート系列を決定するように構成された転送ユニットと、着信マルチキャストデータパケットを転送ユニットによって決定された出力ポート系列内に示されるポートから出力することである着信マルチキャストデータパケットのマルチキャスト転送を完了するためにラインカードをスケジューリングするように構成されたスイッチングファブリックユニットとを含む。
【００１４】
好ましい態様では、転送ユニットが、ルーティングクエリーユニットによって取得された索引値を転送テーブルの索引値として使用して、当該転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定し、あるいは、転送ユニットが、索引配列と転送テーブルとを含み、最初に、ルーティングクエリーユニットによって取得された索引値を当該索引配列の索引値として使用して、当該索引配列内の対応するテーブル項目に直接ヒットさせることにより当該転送テーブルの索引値を取得し、次に、当該索引配列がヒットした当該転送テーブルの索引値を使用して、転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定する。
【００１５】
好ましい態様では、所定のマスク項目は、データセンター内のサーバー総数に基づいて設定される。
【００１６】
好ましい態様では、データセンター内のサーバー総数が２１６以下の場合、一連の連続マルチキャストアドレスは下位１６ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘｆｆｆｆとして設定され、データセンター内のサーバー総数が２１７以下の場合、一連の連続マルチキャストアドレスは下位１７ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ１ｆｆｆｆとして設定され、データセンター内のサーバー総数が２１８以下の場合、一連の連続マルチキャストアドレスは下位１８ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ３ｆｆｆｆとして設定され、データセンター内のサーバー総数が２１９以下の場合、一連の連続マルチキャストアドレスは下位１９ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ７ｆｆｆｆとして設定され、データセンター内のサーバー総数が２２０以下の場合、一連の連続マルチキャストアドレスは下位２０ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘｆｆｆｆｆとして設定される。
【００１７】
転送ユニットは、ＳＲＡＭ上に転送テーブルを格納するか、またはＳＲＡＭ上に索引配列と転送テーブルとを格納するのが望ましい。
【００１８】
本発明の第２の態様によれば、データセンター向けのマルチキャスト転送方法であって、データセンター内のサーバーのマルチキャストアドレスが一連の連続マルチキャストアドレスにおけるアドレスであり、着信マルチキャストデータパケットを受信するステップと、着信マルチキャストデータパケットのヘッダから宛先ＭＡＣアドレスを抽出するステップと、抽出された宛先ＭＡＣアドレスと所定のマスク項目との間で論理ＡＮＤ演算を実行して索引値を取得するステップと、取得された索引値を使用して出力ポート系列を決定するステップと、決定された出力ポート系列内に示されるポートから着信マルチキャストデータパケットを出力するステップとを含む
【００１９】
好ましい態様では、取得された索引値を使用して出力ポート系列を決定するステップにおいて、取得された索引値を転送テーブルの索引値として使用して、当該転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定し、あるいは、最初に、取得された索引値を索引配列の索引値として使用して、当該索引配列内の対応するテーブル項目に直接ヒットさせることにより転送テーブルの索引値を取得し、次に、当該索引配列がヒットした当該転送テーブルの索引値を使用して、転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定する。
【００２０】
所定のマスク項目は、データセンター内のサーバー総数に基づいて設定されるのが望ましい。
【００２１】
データセンター内のサーバー総数が２１６以下の場合、一連の連続マルチキャストアドレスは下位１６ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘｆｆｆｆとして設定され、データセンター内のサーバー総数が２１７以下の場合、一連の連続マルチキャストアドレスは下位１７ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ１ｆｆｆｆとして設定され、データセンター内のサーバー総数が２１８以下の場合、一連の連続マルチキャストアドレスは下位１８ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ３ｆｆｆｆとして設定され、データセンター内のサーバー総数が２１９以下の場合、一連の連続マルチキャストアドレスは下位１９ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ７ｆｆｆｆとして設定され、データセンター内のサーバー総数が２２０以下の場合、一連の連続マルチキャストアドレスは下位２０ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘｆｆｆｆｆとして設定される。
【００２２】
ＳＲＡＭ上に転送テーブルを格納するか、またはＳＲＡＭ上に索引配列と転送テーブルとを格納するのが望ましい。
【００２３】
本発明の第３の態様によれば、ＯｐｅｎＦｌｏｗスイッチが提案される。このＯｐｅｎＦｌｏｗスイッチは、本発明の第１の態様によるマルチキャスト転送装置を含む。
【００２４】
本発明の第４の態様によれば、イーサネットスイッチが提案される。このイーサネットスイッチは、本発明の第１の態様によるマルチキャスト転送装置を含む。
【発明の効果】
【００２５】
本発明で提案されるデータセンター向けの拡張可能なマルチキャスト転送方式においては、複雑なＴＣＡＭに代えて単純ゲート回路を使用してマスク演算が実現される。第一に、このような実装では最長一致を実行する必要はなく、ルーティングテーブルを格納することも不要なため、コストとリソースのオーバーヘッド（電力消費量、回路複雑度等）はＴＣＡＭよりも遙かに低い。第二に、これはマスクの単純なＡＮＤ演算なので、データセンターネットワークを構成するサーバー数の変動に応じてマスク内のビット数を変えることができるため、拡張性が実現される。加えて、単純な設計であるため、本発明のクエリー演算に費やされる時間量はＳＲＡＭ上でのワンタイムアクセスの時間量（〜２ｎｓ）程度に留まり、ＴＣＡＭ（３〜５ｎｓ）上でのそれよりも少ない。加えて、本発明の転送テーブル圧縮方式では、リダイレクトの使用によりメモリー空間（最初のメモリー空間の１／２〜１／４）を節減することが可能となっている。これは、本発明は、同じ記憶領域であれば最初の記憶方式よりも多くのアドレス領域（２〜４倍）を確保できるため、データセンターネットワークの拡張性が大幅に高くなることを意味する。
【図面の簡単な説明】
【００２６】
上記およびその他の目的、特徴、並びに利点は、図面を参照しながら実施例について述べた以下の説明を読むことにより、さらに明らかになるであろう。
【００２７】
【図１】本発明によるデータセンター向けの拡張可能なマルチキャスト転送装置１０００の概略ブロック図である。
【図２】転送テーブル１３２の概略図である。
【図３】本発明によるデータセンター向けの拡張可能なマルチキャスト転送方法３０００の概略フローチャートである。
【図４】本発明によるデータセンター向けの拡張可能なマルチキャスト転送装置４０００の概略図である。
【図５】転送テーブルのリダイレクトにより記憶容量の圧縮を実現する方法を説明する概略図である。
【図６】ＯｐｅｎＦｌｏｗを使用して本発明を実現する場合の概略図である。
【図７】既存のイーサネット環境に本発明を実装する場合の概略図である。
【００２８】
本発明の図面においては、同一または類似の構造とステップは同一または類似の参照番号によって示されている。
【発明を実施するための形態】
【００２９】
以下では、上記の図面を参照して、本発明の好適な実施例を説明する。以下の説明においては、本発明に対する理解が曖昧になるのを回避するため、本発明に必須ではない詳細および機能を省略する。
【００３０】
上述したとおり、データセンターネットワークとインターネットの最大の相違点は、前者においてマルチキャストアドレスの個数はデータセンターネットワーク内のサーバー数に依存することである。現在の大規模データセンターが保有するサーバー数は１万〜１０万台の範囲にわたり、その多くは５万台前後に集中している。そのため、現在のデータセンターネットワークにおけるマルチキャスト需要に対応するには、１つの連続するマルチキャストアドレスフィールド（例えば、２３９．０．＊．＊／１６の場合、合計６５，５３６個のアドレスがある）で十分である。こうした特徴に着目して、本発明は、連続ＩＰアドレスフィールド内のＩＰアドレスを使用して、データセンターにおけるサーバーのマルチキャストアドレスを示すことを提案する。本発明では例えば、２３９．０．＊．＊／１６や１９２．１．＊．＊／１６の範囲内のアドレスを使用することができる。
【００３１】
ＩＰアドレスの選択（つまり、連続ＩＰアドレスフィールド内のＩＰアドレスを選択すること）という観点から見ると、同様に、マルチキャストＭＡＣアドレスは、対応してマルチキャストＩＰアドレスと同じ特徴を有すると考えられる。イーサネットにおいては、アドレスフィールド２３９．０．＊．＊／１６の範囲内のアドレスを使用でき、０１：００：５Ｅ：００：００：００〜０１：００：５Ｅ：ＦＦ：ＦＦ：ＦＦはマルチキャスト専用のＭＡＣアドレスフィールドである。上位２５ビットは固定（０１：００：５Ｅ）であり、下位２３ビットは対応するＩＰアドレスと等しい。マルチキャストアドレスのマッピングにおいては、ＩＰアドレスの下位２３ビットをＭＡＣアドレスの下位２３ビットに直接マップすることができる。これはつまり、マルチキャストアドレスの下位２３ビットは、上位層のＩＰマルチキャストアドレスの下位２３ビットと同じであることを意味する。インターネット環境においては、ＩＰアドレスのクラスＤでは、ＩＰアドレスの上位４ビットは固定（１１１０）である。そのため中間の５ビットはＭＡＣアドレスにマップされないが、これは、１個のマルチキャストＭＡＣアドレスが２５＝３２個の異なるＩＰアドレスに対応する可能性を生じさせる原因となる。この場合、マルチキャストアドレスの一意性を確立するには、ＭＡＣアドレスを使用することを除くと、マルチキャストＩＰアドレスを使用するしか方法はない。ただし、上述したように、データセンターネットワークのサーバー数は限られており（１０万台未満）、アドレスの連続性も制御可能なので、各マルチキャストアドレスは下位２３ビットによって区別することが可能である。その理由は、データセンター内のサーバー数は１０万台未満（＜２２３）なので、２３ビットでサーバーのマルチキャストアドレスを一意に識別できるためである（ほとんどの仕様において、データセンター内に存在するサーバー数は６５，５３６台以下なので、下位１６ビットのみが使用される。拡張することとなった場合には、２３ビットの使用が可能なので、２２３台のサーバーにアドレス指定を行うことができる）。最後に、このアドレスマッピングは、単一のインスタンスで記述することが可能である（マルチキャストアドレス２２４．１９３．１６．２はＭＡＣ層アドレス０１：００：５Ｅ：４１：１０：０２にマップされる）。ＭＡＣアドレスの上位２５ビットは固定（０１：００：５Ｅ）である。１９３の２進表現は１１０００００１であり、最上位ビットを除去すると１０００００１（すなわち０ｘ４１）になる。１６の１６進表現は０ｘ１０である。２の１６進表現は０ｘ０２である。このようにして、下位２３ビットを決定することができる。最後のＭＡＣアドレス（０１：００：５Ｅ：４１：１０：０２）が取得される。
【００３２】
図１は、本発明によるデータセンター向けの拡張可能なマルチキャスト転送装置１０００の概略図である。
【００３３】
図１に示すように、本発明によるデータセンター向けの拡張可能なマルチキャスト転送装置１０００は、ラインカード１１０と、ルーティングクエリー実行エンジン１２０と、転送エンジン１３０と、スイッチングファブリックユニット(switch fabric)１４０とを含む。
【００３４】
ラインカード１１０は、データパケットをルータ／スイッチから入出力するためのポータルであり、入出力待ち行列１１２とデータパケットプロセッサ１１４を主な構成要素とする複数のネットワークカード（図示せず）を含む。
・入出力待ち行列１１２：データパケットがネットワークカードを通って着信すると、まず入力待ち行列にキャッシュされ、処理を待機する。入力待ち行列が満杯になると、新たに着信するデータパケットはそのまま破棄される。データパケットの処理順序は、異なるサービス品質（ＱｏＳ：ｑｕａｌｉｔｙ ｏｆ ｓｅｒｖｉｃｅ）の要件に基づくデータパケット優先順位によって決まる。デフォルトでは、処理ルールはＦＩＦＯ（先入れ先出し）である。出力待ち行列も、これと同様である。
・データパケットプロセッサ１１４：これは主に、データパケットのヘッダから、データリンク層の宛先アドレス（すなわち、宛先ＭＡＣアドレス）とルーティング層の宛先アドレス（すなわち、宛先ＩＰアドレス）を抽出するために使用される。これら２個のアドレスは、それぞれデータリンク層エンジンとルーティング層エンジンの索引項目として使用される。
【００３５】
データセンターではサーバーのマルチキャストアドレスは連続ＩＰ／ＭＡＣアドレスフィールド内のアドレスを使用して示される可能性があるとの発明者の認識から、本発明ではルーティングクエリー実行エンジン１２０を単純な構造とし、十分な拡張性を持たせている。例えば、データセンターネットワーク内のサーバー数が６５，５３６（すなわち、２１６）台以下の場合には、マルチキャストアドレスは、プレフィックス長が１６の連続アドレスフィールドを使用して示すことができる。ルーティングクエリー実行エンジン１２０は、対応して設定されたマスク項目１２４との論理ＡＮＤ演算を実行する単純なＡＮＤゲート回路１２２によって、クエリー演算を実装することが可能である。
・ＡＮＤゲート回路１２２：ＡＮＤゲート回路１２２は、ラインカード１１２のデータパケットプロセッサ１１４からデータパケットの宛先アドレスを取得した後、宛先ＭＡＣアドレスとマスク項目内に格納されたマスクとの間でＡＮＤ演算を実行する（マルチキャストアドレス数は２１６以下なので、マスク内には１６個の有効ビットが存在する）。その結果得られる転送テーブルの索引値は、転送エンジン１３０に出力される。データセンターネットワーク内のアドレスは連続しているため、第２層の転送は主に、ネットワークトポロジーが判明した後に実行される。そのため、第２層のＭＡＣアドレスがＡＮＤゲート回路１２２によって処理される。
・マスク項目１２４：ここには、論理ＡＮＤ演算で使用されるマスク値が格納される。データセンターネットワーク内のサーバー数は２１６以下なので、１６ビットのマスク値を使用するので十分である。ここで、最も単純な方法は、１６ビットのマスクを０ｘｆｆｆｆで示すことである。こうすれば、ＡＮＤ演算により宛先アドレスそのものが得られる。データセンター内のアドレスは集中化され制御可能なため、各サーバーにより使用されるＭＡＣアドレスの下位１６ビットが互いに異なることを確保することができる。
【００３６】
マスク値は、既存のデータセンターネットワーク内のサーバー数の変動によって変化する可能性があることに注意する必要がある。ただし、最も単純なマスクを例にとると、マスク値は以下のようになる。すなわち、６５，５３６（２１６）個のマルチキャストアドレスが存在する場合には、マスクはそれに対応して０ｘｆｆｆｆに設定され、１３１，０７２（２１７）個のマルチキャストアドレスが存在する場合には、マスクはそれに対応して０ｘ１ｆｆｆｆに設定され、１，０４８，５７６（２２０）個のマルチキャストアドレスが存在する場合には、マスクはそれに対応して０ｘｆｆｆｆｆに設定される。そのためマスク値は、マスク項目１２４においてハードウェア実装に関して１回のリライト操作を実行するたけで、容易に調整することが可能である。ＴＣＡＭと比較して、この方法は実装が容易なだけではなく、コストとエネルギー消費量も遙かに少なくて済む。さらに、この方法によりデータセンターネットワークに十分な拡張性がもたらされる。
【００３７】
転送エンジン１３０は、ルーティングクエリ実行エンジン１２０によって出力された転送テーブルの索引値を、転送テーブル１３２内の対応するテーブル項目に直接ヒットさせて、出力ポート系列を取得することができる。
【００３８】
図２は、転送テーブル１３２（Ｇ２Ｉ）の概略図である。データセンターネットワークの第２層転送テーブルは、ビットマップを使用して実装される。テーブル項目番号のＧは、マルチキャストグループ数に等しい。すなわち、このシナリオにおいては、６５，５３６個のマルチキャストアドレス（１個のアドレスが１つのマルチキャストグループを表す）が存在するので、６５，５３６個のテーブル項目が存在する。各テーブル項目は、現在のスイッチに含まれるポート数Ｉのビットマップに対応する。現在のデータセンターネットワークでは主に６４ポートのスイッチが使用されているため、このビットマップは合計６４ビットを有する（各ビットは１つのポート番号を表す）。例えば、１０１１０１０１０１１０００００００００００００００００００００００００００００００００００００００００００００００００００００は、ポート１、３、４、６、８、１０および１１からの転送を表す。本発明においては、転送テーブルはＳＲＡＭを使用して格納できるので、高いコスト効率が達成される。マルチキャストアドレスは６５，５３６（６４Ｋ、１Ｋ＝１０２４）個存在し、スイッチは６４ポートを有するとして計算すると、各転送テーブルのサイズは６４Ｋ＊６４ｂｉｔｓ／８＝５１２ＫＢになる。表３に示すように、現在のスイッチの単一チップセット内にあるＳＲＡＭは平均して約４ＭＢのサイズを有するため、５１２ＫＢのＳＲＡＭであれば過剰なオーバーヘッドが発生することはない。また逆に、４ＭＢのＳＲＡＭを使用して転送テーブルを格納する場合には、スイッチにまだ６４ポートが残っているとすると、４ＭＢ／５１２ＫＢ＊６４Ｋ＝５１２Ｋ個のマルチキャストアドレスをサポートすることが可能である。つまり、データセンターネットワーク内のサーバー数が最大５１２Ｋまで増加した場合でも、本発明の転送エンジンはＯ（１）のクエリー速度を達成することができるのである。これにより、データセンターネットワークに十分な拡張性がもたらされる。
【００３９】
スイッチングファブリックユニット１４０は、データパケットの出力パスをスケジューリングするために使用される。同じラインカード１１０内の複数ネットワークカード間で行われるデータパケットの転送は、ラインカード１１０内のデータパケットプロセッサ１１４によってスケジューリングされる。一方、異なるラインカード間で行われるデータパケットの転送は、スイッチングファブリックユニット１４０によってスケジューリングされ、そのスケジューリングはネットワーク機器の他のリソースを共有することで実現される。
【００４０】
図３は、本発明によるデータセンター向けの拡張可能なマルチキャスト転送方法３０００の概略フローチャートである。
【００４１】
図３に示すように、ステップＳ３０１０において、ラインカード１１０が着信マルチキャストデータパケットを受信し、入出力待ち行列１１２の入力待ち行列にそれを登録する。その後、ステップＳ３０２０において、ラインカード１１００内のデータパケットプロセッサ１１４が着信マルチキャストデータパケットを処理し、着信マルチキャストデータパケットのヘッダから宛先ＭＡＣアドレスを抽出し、抽出された宛先ＭＡＣアドレスをルーティングクエリー実行エンジン１２０に送信する。ステップＳ３０３０において、ルーティングクエリー実行エンジン１２０が、受信された宛先ＭＡＣアドレスとマスク項目との間で論理ＡＮＤ演算を実行して、転送エンジン１３０の索引値を取得する。ステップＳ３０４０において、転送エンジン１３０は、ルーティングクエリー実行エンジン１２０によって出力された索引値を直接、転送テーブルの索引値として使用して、転送テーブル１３２内の対応する項目に直接ヒットさせ、出力ポート系列を取得する。ステップＳ３０５０において、スイッチングファブリックユニット１４０が、転送エンジン１３０によって決定された出力ポート系列に基づいて、着信マルチキャストデータパケットのマルチキャスト転送（すなわち、当該着信マルチキャストデータパケットを、出力ポート系列内に示されるポートから出力すること）を完了するためにラインカード１１０をスケジューリングする。
【００４２】
（前述の実施例の改良）
図２に示す転送テーブル１３２の読み取りは容易であるが（索引値に基づいてコンテンツを直接読み取ることができる）、データセンターのネットワークトポロジーは規則性を有するので、同じテーブル項目が多数存在する。多くの中間層スイッチ（ツリー構造内の葉ノードではないスイッチ）では、異なる宛先アドレスに対して同じ転送ポート系列が使用される。そのため、本発明はさらに、リダイレクト方式（ビットマップ共有）を使用して、転送テーブル上で圧縮格納を実行することを提案する。
【００４３】
図４は、本発明によるデータセンター向けの拡張可能なマルチキャスト転送装置４０００の概略ブロック図である。図１からの改良は転送エンジン１３０でのみ行われており、これは転送エンジン４３０として識別される。他の処理手段は図１と同じである。これらの同じ処理手段の詳細な説明は、不必要な反復を避けるため省略する。
【００４４】
転送エンジン４３０において階層的索引付けを実現するため、索引配列４３４が追加され、それに対応して転送テーブル１３２を修正して転送テーブル４３２とする。
【００４５】
演算において（図３のステップＳ３０４０に対応）、転送エンジン４３０は、ルーティングクエリー実行エンジン１２０によって出力された索引値を索引配列４３４の索引値として使用して（転送テーブルの索引値は、索引配列４３４内の各テーブル項目を使用して格納される）、索引配列４３４内の対応するテーブル項目に直接ヒットさせ、転送テーブルの索引値を取得する。その後、転送エンジン４３０は、索引配列４３４がヒットした転送テーブルの索引値を再使用して、転送テーブル４３０内の対応するテーブル項目に直接ヒットさせ、出力ポート系列を取得する。このような２段階の索引付けにより、出力ポート系列がヒットされ、同時に記憶容量の圧縮が実現される。
【００４６】
図５は、転送テーブルのリダイレクトにより記憶容量の圧縮を実現する方法を説明する概略図である。
【００４７】
図５において、Ｇ２Ｍは索引配列４３４であり、Ｍ２Ｉは転送テーブル４３２である。Ｇ２Ｍの系列長はマルチキャストグループ数に等しい。このシナリオには６５，５３６個の素子が存在し、各々がＭ２Ｉの索引値を保持している。したがって、転送テーブルにヒットさせるためには２段階の索引付けが必要とされる（第１の索引付けはＧ２Ｍで、第２の索引付けはＭ２Ｉ）。最初の転送テーブルには多数の同じテーブル項目が存在するため（図２）、記憶領域の圧縮を実行する目的で索引配列４３４が導入されている。圧縮された転送テーブル４３２（すなわち、Ｍ２Ｉ）において、最初の転送テーブルと同様に各テーブル項目は１つのビットマップを一意に表現するので、ビットマップ数はスイッチ内のポート数に等しい。図５の矢印は、リダイレクトプロセスを表す。すなわち、ルーティングクエリー実行エンジン１２０が２つの異なるデータパケットのＭＡＣアドレスをクエリーすると、マスクのＡＮＤ演算によって２つの異なる索引項目が取得される。これら２つの異なる索引項目は、それぞれマルチキャストグループ１とマルチキャストグループ２である。次に、これら２つの索引項目に基づいて対応する２つの素子値が索引配列４３４から読み取られるので、転送テーブルに対して複数の同じ索引値が取得される可能性がある。これは、記憶領域の圧縮前には、２つのマルチキャストグループに対応する転送テーブル１３２のテーブル項目が、同じコンテンツを保持している可能性があることを意味する。
【００４８】
ＣＰＵによる１回の読み取り操作を円滑化するため、索引配列Ｇ２Ｍはその素子の幅を位置合わせルール（Ｌは２バイトまたは４バイトのいずれか）に基づいて調整する。３２ビットＣＰＵの場合、１回の読み取り操作で４バイトが消費される。この場合、Ｌが２バイトであれば２個の素子を読み取ることができ、Ｌが４バイトであれば１個の素子を読み取ることができる。これによりアクセス効率が向上する（Ｌが３バイトの場合は、各読み取りの位置合わせは不可能である）。加えて、図５から分かるように、転送テーブル４３２の項目番号Ｎの最大値は、Ｌの幅（すなわち、Ｍ＝２Ｌ）に関係している。Ｌが２バイトの場合、転送テーブル４３２は最大Ｍ＝２１６＝６４Ｋの項目を保持することができる。Ｌが４バイトの場合、転送テーブル４３２は最大Ｍ＝２３２＝４Ｇの項目を保持することができる。すなわち、Ｌが２バイトと４バイトのときは、データセンター内でそれぞれ６４Ｋと４Ｇのサーバーをサポートすることが可能である。したがって、本発明による索引配列の位置合わせルールは、ＣＰＵアクセス操作を円滑化するだけでなく、十分な拡張性も同時にもたらすのである。
【００４９】
２段階の索引付け操作では、リダイレクトが実行されるため、最初の直接索引付け転送テーブルよりもアクセス操作が１回多くなる。ここでは格納のためにＳＲＡＭが採用されているので、１．５〜２ｎｓの時間が余分に必要となる。しかし、こうした余分の時間を費やしてもなお、ＴＣＡＭよりも所要時間は短い。加えて、本発明により転送テーブルの記憶領域が節減される。
【００５０】
図２において、最初の圧縮されていない転送テーブル１３２のテーブル項目数Ｇは、マルチキャストグループ数（例えば、６４Ｋ）に等しい。転送テーブル１３２のこれらの項目の各々は、スイッチ内のポート数（例：６４ポート）に等しい幅を有するビットマップである。図５に示す圧縮して格納された索引配列４３４の場合、索引配列４３４のテーブル項目数Ｇはマルチキャストグループ数（例えば、６４Ｋ）に等しく、各素子は幅Ｌを有する（例えば、ＣＰＵ位置合わせルールによれば、Ｌは２バイトである（２１６＝６４Ｋ））。図５の転送テーブル４３２においては、圧縮された転送テーブル４３２のテーブル項目数はＮである。これらのテーブル項目の各々はビットマップであり、スイッチ内のポート数（例：６４ポート）に等しい幅Ｉを有する。したがって、圧縮領域のオーバーヘッドと最初の領域のオーバーヘッドの比は、式（１）によって計算できる。
【数１】
【００５１】
本発明の典型的な適用例（Ｌ＝２ＢおよびＩ＝６４ビット＝８Ｂ）では、Ｌ ／ Ｉ＝１／４となる。圧縮率Ｎ／Ｇは、転送テーブル１３２での同じテーブル項目の出現頻度によって決まる（平均して２つおきのテーブル項目が同じであれば同じテーブル項目の出現頻度は２であり、４つおきのテーブル項目が同じであれば同じテーブル項目の出現頻度は４である）。データセンターネットワークの実際のトポロジーのツリー構造においては、同じテーブル項目の出現頻度は平均して４〜８の範囲なので、圧縮率Ｎ／Ｇは１／８〜１／４の範囲であり、式（１）は［１／４，１／２］の値をとることができる。そのため、最初の転送テーブル１３２と比較して、本発明による圧縮された索引配列４３４と転送テーブル４３２は、最初の所要領域の１／４〜１／２しか必要としない。したがって、同じ記憶領域の場合であれば、この改良版は前述の実施例の２〜４倍のマルチキャストアドレス領域をサポートできるので、データセンターネットワークの拡張性が大幅に向上する。
【００５２】
最後に、本発明の実装における２つの具体例について説明する。一方の具体例は広く普及したＯｐｅｎＦｌｏｗ技術を使用して実装することができ、もう一方の具体例は既存のイーサネット環境内に展開することができる。
【００５３】
（１）ＯｐｅｎＦｌｏｗは、研究者が実際の要件に応じて新しいネットワークプロトコルやネットワーク実験を実装および展開することを可能にするオープンソース技術である。ネットワーク機器ベンダーによって提供されるネットワーク機器はすべて「ブラックボックス」なので、ユーザーが行えるのはＩＰアドレスやＶＬＡＮを設定するといった構成作業に限られ、実験的にプログラミングを実行することはできない。そのため、ネットワーク機器のプログラミングインタフェースをオープンにすることは、主要な研究者にとって火急の課題となっていた。ＯｐｅｎＦＬｏｗはまさにそれを実現する技術である。これはスタンフォード大学によって開発されたオープンソース製品であり、ソフトウェアによってルーティングと転送の機能を実現することが可能である。ＯｐｅｎＦｌｏｗは、マルチカードＰＣがスイッチとして扱われるＬｉｎｕｘホストに直接展開できるだけでなく、ＮＥＣやＪＵＮＩＰＥＲ製製品のような市販のスイッチにもロードされている。ユーザーは研究要件に従ってＯｐｅｎＦｌｏｗ上でプログラミングできるので、研究者によるネットワーク実験の実施が容易になった。
【００５４】
図６は、ＯｐｅｎＦｌｏｗを使用して本発明を実現する場合の概略図である。
【００５５】
ＯｐｅｎＦｌｏｗスイッチ６１０内の転送ルールと転送テーブルは、リモートコントローラ６２０によって展開できる。新しいルーティングプロトコル等はすべて、コントローラ６２０上のプログラミングにより実装される。コントロールプレーンの情報交換は、ＯｐｅｎＦｌｏｗスイッチ６１０とコントローラ６２０間で、暗号化されたＳＳＬセキュリティプロトコルを介して実行できる。ＯｐｅｎＦｌｏｗスイッチ６１０自体は、データパケットの転送のみを担当する。図６に示すように、送信機６３０は宛先アドレス２３９．０．０．６を使用してマルチキャストデータパケットを送信する。マルチキャストアドレス指定ルールによれば、対応する宛先ＭＡＣアドレスは０１：００：５ Ｅ：００：００：０６なので、ＡＲＰテーブルは図６に示すような内容となる。データパケットを受信した後、ＯｐｅｎＦｌｏｗスイッチ６１０はＯｐｅｎＦｌｏｗの特性に従って、ＭＡＣアドレスの下位１６ビットが直接、転送テーブルの索引値として使用されるように、転送ルールをプログラムミングする。これは、マスク値０ｘｆｆｆｆと宛先ＭＡＣアドレスの下位１６ビットとをＡＮＤ演算したのと同じ結果となる。ここで、宛先ＭＡＣアドレスの下位１６ビット（図６の丸で囲んだ部分）は０ｘ０００６なので、索引値は６である。したがって、転送は転送テーブルの６番目の項目に示されるポートから直接実行される。図６のＯｐｅｎＦｌｏｗスイッチ６１０、コントローラ６２０、および送信機（ＰＣ）６３０は、それぞれ以下の機能を実装することができる。
【００５６】
ＯｐｅｎＦｌｏｗスイッチ６１０
・ＯｐｅｎＦｌｏｗスイッチ６１０は、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ）を適用することにより、ルーティングクエリー実行エンジンの機能を実装することができる。ＯｐｅｎＦｌｏｗはハードウェアＦＰＧＡ上でのプログラミングをサポートしているため、転送テーブルの直接読み取り、転送テーブルのリダイレクトと読み取り、ビットマップで示されるポートからの直接転送といったデータプレーンの機能はすべて、高水準言語（例：Ｃ言語）を使用してプログラミングし、ハードウェア内に実装することが可能である。
・転送テーブルはＯｐｅｎＦｌｏｗスイッチ６１０内に格納されるが、ＳＳＬプロトコルを介してコントローラ６２０から制御することができる。
【００５７】
コントローラ６２０：
・コントローラ６２０は、ＯｐｅｎＦｌｏｗスイッチ６１０内に格納される転送テーブルに対して、追加、削除、修正、検索の各操作を実行する。
・コントローラ６２０は、アドレスの衝突が発生しないように、データセンターネットワーク内のサーバーにマルチキャストアドレスを割り当てる。これにより各サーバーのマルチキャストアドレスの一意性が確保され、その結果、スイッチの転送ルール内で複数一致が発生しないようになる（例えば、各宛先ＭＡＣアドレスの下位１６ビットは一意である）。
【００５８】
ＰＣ６３０：
・ＰＣ６３０はまず、中間スイッチノード６１０に転送テーブルの項目を確立させるために、通信前にマルチキャスト要求メッセージを送信する。
・ユーザーはサーバー側のサービス開発を修正する必要はなく、最初のマルチキャストソケットに従ってプログラムを実行する。
ｓｅｔｓｏｃｋｏｐｔ（ｓｏｃｋｅｔ，ＩＰＰＲＯＴＯ＿ＩＰ，ＩＰ＿ＡＤＤ＿ＭＥＭＢＥＲＳＨＩＰ，．．．）．
【００５９】
（２）図７は、既存のイーサネット環境に本発明を実装する場合の概略図である。ホスト７３０−１〜７３０−ｎは、アドレス衝突を回避するために、未使用のマルチキャストアドレスを検出する役割を担う。アドレスの割り当てと転送テーブルの制御を行うＯｐｅｎＦｌｏｗコントローラ６１０のような機器はないので、主にスイッチ７１０−１〜７１０−ｍとＰＣ７３０−１〜７３０−ｎがマルチキャスト転送プロセスを実装するために使用される。
【００６０】
スイッチ７１０−１〜７１０−ｍ：
・ＯｐｅｎＦｌｏｗと同様に、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ）を適用することにより、ルーティングクエリー実行エンジンの機能を実装することができる。市販のスイッチとＦＰＧＡを使用しているので、転送テーブルの直接読み取り、転送テーブルのリダイレクトと読み取り、ビットマップで示されるポートからの直接転送といったデータプレーンの機能を実行するために、専用ハードウェアプログラミング言語（例：ＶｅｒｉｌｏｇやＶＨＤＬ）を採用することができる。
【００６１】
ＰＣ７３０−１〜７３０−ｎ：
・アドレス割り当て用のコントローラはないので、ホスト７３０−１〜７３０−ｎが自機においてマルチキャストアドレスを検出し、自機のマルチキャストアドレスが使用されないことを確保する必要がある。
・ユーザーはサーバー側のサービス開発を修正する必要はなく、最初のマルチキャストソケットに従ってプログラムを実行する。
ｓｅｔｓｏｃｋｏｐｔ（ｓｏｃｋｅｔ，ＩＰＰＲＯＴＯ＿ＩＰ，ＩＰ＿ＡＤＤ＿ＭＥＭＢＥＲＳＨＩＰ，．．．）．
【００６２】
本開示の他の構成としては、方法実施例のステップおよび動作を実行するソフトウェアプログラムが挙げられる。以下ではまずその概要を述べ、次に詳細に説明する。具体的には、１つの実施例は、符号化されたコンピュータプログラム論理を格納するコンピュータ可読媒体を含むコンピュータプログラム製品である。コンピュータプログラム論理は、コンピューティング装置上で実行されると、上記の拡張可能なマルチキャスト転送方式を提供するための操作を提供する。コンピュータプログラム論理は、それがコンピューティングシステムの少なくとも１つのプロセッサ上で実行されたときに、当該少なくとも１つのプロセッサが本発明の実施例の動作（方法）を実行することを可能にする。本発明のこうした構成は、典型的には、光媒体（例：ＣＤ−ＲＯＭ）、ソフトディスク、ハードディスク等のコンピュータ可読媒体上で提供または符号化されたソフトウェア、コードもしくはデータ構造体、１つ以上のＲＯＭ、ＲＡＭもしくはＰＲＯＭチップに格納されたファームウェアもしくはマイクロコード等のその他の媒体、特定用途向け集積回路（ＡＳＩＣ）、または単一もしくは複数モジュール上のダウンロード可能なソフトウェアイメージおよび共有データベース等として提供される。ソフトウェア、ハードウェア等の構成は、コンピューティング装置上にインストールされることにより、コンピューティング装置内の１つ以上のプロセッサを介して、本発明の実施例による技法を実行することができる。また、本発明のノードおよびホストは、ソフトウェアプロセスを、例えば他のエンティティ内の一連のデータ通信装置やコンピューティング装置と共に稼働させることによっても提供することができる。本発明のノードおよびホストはさらに、複数のデータ通信装置の複数のソフトウェアプロセスに分散させたり、一連の小型専用コンピュータ上で稼働するすべてのソフトウェアプロセスに分散させたり、あるいは単一のコンピュータ上で稼働するすべてのソフトウェアプロセスに分散させることができる。
【００６３】
本発明の実施例は、ソフトウェアプログラム、１台のデータ処理装置上のソフトウェアおよびハードウェア、独立したソフトウェア、または独立した回路として実装できることは理解されるであろう。
【００６４】
上記では、本発明を好適な実施例を使用して説明してきたが、本発明の適用範囲には、本発明の精神および原則に則ったあらゆる変更、置換、改良等も内包されることは理解されるであろう。したがって、本発明の範囲は上記の具体的な実施例に限定されず、付記した請求項によってのみ限定される。
【００６５】
さらに、上記実施形態の一部又は全部は、以下の付記のようにも記載されうるが、これに限定されない。
【００６６】
（付記１）
データセンター向けのマルチキャスト転送装置であって、
データセンター内のサーバーのマルチキャストアドレスが一連の連続マルチキャストアドレス内のアドレスであり、
着信マルチキャストデータパケットを受信して、当該着信マルチキャストデータパケットのヘッダから宛先ＭＡＣアドレスを抽出するように構成されたラインカードと、
前記ラインカードによって抽出された宛先ＭＡＣアドレスと所定のマスク項目との間で論理ＡＮＤ演算を実行して索引値を取得するように構成されたルーティングクエリーユニットと、
前記ルーティングクエリーユニットによって取得された索引値を使用して出力ポート系列を決定するように構成された転送ユニットと、
前記着信マルチキャストデータパケットを転送ユニットによって決定された出力ポート系列内に示されるポートから出力することである前記着信マルチキャストデータパケットのマルチキャスト転送を完了するために前記ラインカードをスケジューリングするように構成されたスイッチングファブリックユニットと
を備えることを特徴とするマルチキャスト転送装置。
【００６７】
（付記２）
前記転送ユニットが、前記ルーティングクエリーユニットによって取得された索引値を転送テーブルの索引値として使用して、当該転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定し、
あるいは、前記転送ユニットが、索引配列と転送テーブルとを含み、最初に、前記ルーティングクエリーユニットによって取得された索引値を当該索引配列の索引値として使用して、当該索引配列内の対応するテーブル項目に直接ヒットさせることにより当該転送テーブルの索引値を取得し、次に、当該索引配列がヒットした当該転送テーブルの索引値を使用して、転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定する
ことを特徴とする付記１に記載のマルチキャスト転送装置。
【００６８】
（付記３）
所定のマスク項目は、前記データセンター内のサーバー総数に基づいて設定されることを特徴とする付記１又は付記２に記載のマルチキャスト転送装置。
【００６９】
（付記４）
前記データセンター内のサーバー総数が２１６以下の場合、一連の連続マルチキャストアドレスは下位１６ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２１７以下の場合、一連の連続マルチキャストアドレスは下位１７ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ１ｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２１８以下の場合、一連の連続マルチキャストアドレスは下位１８ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ３ｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２１９以下の場合、一連の連続マルチキャストアドレスは下位１９ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ７ｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２２０以下の場合、一連の連続マルチキャストアドレスは下位２０ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘｆｆｆｆｆとして設定される
ことを特徴とする付記３に記載のマルチキャスト転送装置。
【００７０】
（付記５）
前記転送ユニットは、ＳＲＡＭ上に前記転送テーブルを格納するか、またはＳＲＡＭ上に前記索引配列と前記転送テーブルとを格納することを特徴とする付記１から付記４の何れかに記載のマルチキャスト転送装置。
【００７１】
（付記６）
データセンター向けのマルチキャスト転送方法であって、
前記データセンター内のサーバーのマルチキャストアドレスが一連の連続マルチキャストアドレスにおけるアドレスであり、
着信マルチキャストデータパケットを受信するステップと、
前記着信マルチキャストデータパケットのヘッダから宛先ＭＡＣアドレスを抽出するステップと、
抽出された宛先ＭＡＣアドレスと所定のマスク項目との間で論理ＡＮＤ演算を実行して索引値を取得するステップと、
取得された索引値を使用して出力ポート系列を決定するステップと、
決定された出力ポート系列内に示されるポートから前記着信マルチキャストデータパケットを出力するステップと
を含むことを特徴とするマルチキャスト転送方法。
【００７２】
（付記７）
取得された索引値を使用して出力ポート系列を決定するステップにおいて、
取得された索引値を転送テーブルの索引値として使用して、当該転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定し、
あるいは、最初に、取得された索引値を索引配列の索引値として使用して、当該索引配列内の対応するテーブル項目に直接ヒットさせることにより転送テーブルの索引値を取得し、次に、当該索引配列がヒットした当該転送テーブルの索引値を使用して、転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定する
ことを特徴とする付記６に記載のマルチキャスト転送方法。
【００７３】
（付記８）
所定のマスク項目は、前記データセンター内のサーバー総数に基づいて設定されることを特徴とする付記６又は付記７に記載のマルチキャスト転送方法。
【００７４】
（付記９）
前記データセンター内のサーバー総数が２１６以下の場合、一連の連続マルチキャストアドレスは下位１６ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２１７以下の場合、一連の連続マルチキャストアドレスは下位１７ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ１ｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２１８以下の場合、一連の連続マルチキャストアドレスは下位１８ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ３ｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２１９以下の場合、一連の連続マルチキャストアドレスは下位１９ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ７ｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２２０以下の場合、一連の連続マルチキャストアドレスは下位２０ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘｆｆｆｆｆとして設定される
ことを特徴とする付記８に記載のマルチキャスト転送方法。
【００７５】
（付記１０）
ＳＲＡＭ上に前記転送テーブルを格納するか、またはＳＲＡＭ上に前記索引配列と前記転送テーブルとを格納することを特徴とする付記６から付記９の何れかに記載のマルチキャスト転送方法。
【００７６】
（付記１１）
付記１から付記５の何れかに記載のマルチキャスト転送装置を含むことを特徴とするＯｐｅｎＦｌｏｗスイッチ。
【００７７】
（付記１２）
付記１から付記５の何れかに記載のマルチキャスト転送装置を含むことを特徴とするイーサネットスイッチ。
【符号の説明】
【００７８】
１１０：ラインカード
１１２：入出力待ち行列
１１４：データパケットプロセッサ
１２０：ルーティングクエリー実行エンジン
１２２：ＡＮＤゲート回路
１２４：マスク項目
１３０：転送エンジン
１３２：転送テーブル
１４０：スイッチングファブリックユニット
１０００：マルチキャスト転送装置
４３０：転送エンジン
４３２：転送テーブル
４３４：索引配列
４０００：マルチキャスト転送装置
６１０：ＯｐｅｎＦｌｏｗスイッチ
６２０：コントローラ
６３０：送信機
７１０−１：スイッチ
【特許請求の範囲】
【請求項１】
データセンター向けのマルチキャスト転送装置であって、
データセンター内のサーバーのマルチキャストアドレスが一連の連続マルチキャストアドレス内のアドレスであり、
着信マルチキャストデータパケットを受信して、当該着信マルチキャストデータパケットのヘッダから宛先ＭＡＣアドレスを抽出するように構成されたラインカードと、
前記ラインカードによって抽出された宛先ＭＡＣアドレスと所定のマスク項目との間で論理ＡＮＤ演算を実行して索引値を取得するように構成されたルーティングクエリーユニットと、
前記ルーティングクエリーユニットによって取得された索引値を使用して出力ポート系列を決定するように構成された転送ユニットと、
前記着信マルチキャストデータパケットを転送ユニットによって決定された出力ポート系列内に示されるポートから出力することである前記着信マルチキャストデータパケットのマルチキャスト転送を完了するために前記ラインカードをスケジューリングするように構成されたスイッチングファブリックユニットと
を備えることを特徴とするマルチキャスト転送装置。
【請求項２】
前記転送ユニットが、前記ルーティングクエリーユニットによって取得された索引値を転送テーブルの索引値として使用して、当該転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定し、
あるいは、前記転送ユニットが、索引配列と転送テーブルとを含み、最初に、前記ルーティングクエリーユニットによって取得された索引値を当該索引配列の索引値として使用して、当該索引配列内の対応するテーブル項目に直接ヒットさせることにより当該転送テーブルの索引値を取得し、次に、当該索引配列がヒットした当該転送テーブルの索引値を使用して、転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定する
ことを特徴とする請求項１に記載のマルチキャスト転送装置。
【請求項３】
所定のマスク項目は、前記データセンター内のサーバー総数に基づいて設定されることを特徴とする請求項１又は請求項２に記載のマルチキャスト転送装置。
【請求項４】
前記データセンター内のサーバー総数が２１６以下の場合、一連の連続マルチキャストアドレスは下位１６ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２１７以下の場合、一連の連続マルチキャストアドレスは下位１７ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ１ｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２１８以下の場合、一連の連続マルチキャストアドレスは下位１８ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ３ｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２１９以下の場合、一連の連続マルチキャストアドレスは下位１９ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ７ｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２２０以下の場合、一連の連続マルチキャストアドレスは下位２０ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘｆｆｆｆｆとして設定される
ことを特徴とする請求項３に記載のマルチキャスト転送装置。
【請求項５】
前記転送ユニットは、ＳＲＡＭ上に前記転送テーブルを格納するか、またはＳＲＡＭ上に前記索引配列と前記転送テーブルとを格納することを特徴とする請求項１から請求項４の何れかに記載のマルチキャスト転送装置。
【請求項６】
データセンター向けのマルチキャスト転送方法であって、
前記データセンター内のサーバーのマルチキャストアドレスが一連の連続マルチキャストアドレスにおけるアドレスであり、
着信マルチキャストデータパケットを受信するステップと、
前記着信マルチキャストデータパケットのヘッダから宛先ＭＡＣアドレスを抽出するステップと、
抽出された宛先ＭＡＣアドレスと所定のマスク項目との間で論理ＡＮＤ演算を実行して索引値を取得するステップと、
取得された索引値を使用して出力ポート系列を決定するステップと、
決定された出力ポート系列内に示されるポートから前記着信マルチキャストデータパケットを出力するステップと
を含むことを特徴とするマルチキャスト転送方法。
【請求項７】
取得された索引値を使用して出力ポート系列を決定するステップにおいて、
取得された索引値を転送テーブルの索引値として使用して、当該転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定し、
あるいは、最初に、取得された索引値を索引配列の索引値として使用して、当該索引配列内の対応するテーブル項目に直接ヒットさせることにより転送テーブルの索引値を取得し、次に、当該索引配列がヒットした当該転送テーブルの索引値を使用して、転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定する
ことを特徴とする請求項６に記載のマルチキャスト転送方法。
【請求項８】
所定のマスク項目は、前記データセンター内のサーバー総数に基づいて設定されることを特徴とする請求項６又は請求項７に記載のマルチキャスト転送方法。
【請求項９】
請求項１から請求項５の何れかに記載のマルチキャスト転送装置を含むことを特徴とするＯｐｅｎＦｌｏｗスイッチ。
【請求項１０】
請求項１から請求項５の何れかに記載のマルチキャスト転送装置を含むことを特徴とするイーサネットスイッチ。
【請求項１】
データセンター向けのマルチキャスト転送装置であって、
データセンター内のサーバーのマルチキャストアドレスが一連の連続マルチキャストアドレス内のアドレスであり、
着信マルチキャストデータパケットを受信して、当該着信マルチキャストデータパケットのヘッダから宛先ＭＡＣアドレスを抽出するように構成されたラインカードと、
前記ラインカードによって抽出された宛先ＭＡＣアドレスと所定のマスク項目との間で論理ＡＮＤ演算を実行して索引値を取得するように構成されたルーティングクエリーユニットと、
前記ルーティングクエリーユニットによって取得された索引値を使用して出力ポート系列を決定するように構成された転送ユニットと、
前記着信マルチキャストデータパケットを転送ユニットによって決定された出力ポート系列内に示されるポートから出力することである前記着信マルチキャストデータパケットのマルチキャスト転送を完了するために前記ラインカードをスケジューリングするように構成されたスイッチングファブリックユニットと
を備えることを特徴とするマルチキャスト転送装置。
【請求項２】
前記転送ユニットが、前記ルーティングクエリーユニットによって取得された索引値を転送テーブルの索引値として使用して、当該転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定し、
あるいは、前記転送ユニットが、索引配列と転送テーブルとを含み、最初に、前記ルーティングクエリーユニットによって取得された索引値を当該索引配列の索引値として使用して、当該索引配列内の対応するテーブル項目に直接ヒットさせることにより当該転送テーブルの索引値を取得し、次に、当該索引配列がヒットした当該転送テーブルの索引値を使用して、転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定する
ことを特徴とする請求項１に記載のマルチキャスト転送装置。
【請求項３】
所定のマスク項目は、前記データセンター内のサーバー総数に基づいて設定されることを特徴とする請求項１又は請求項２に記載のマルチキャスト転送装置。
【請求項４】
前記データセンター内のサーバー総数が２１６以下の場合、一連の連続マルチキャストアドレスは下位１６ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２１７以下の場合、一連の連続マルチキャストアドレスは下位１７ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ１ｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２１８以下の場合、一連の連続マルチキャストアドレスは下位１８ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ３ｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２１９以下の場合、一連の連続マルチキャストアドレスは下位１９ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘ７ｆｆｆｆとして設定され、
前記データセンター内のサーバー総数が２２０以下の場合、一連の連続マルチキャストアドレスは下位２０ビットのみが異なる一連の連続ＩＰアドレスであり、所定のマスク項目は０ｘｆｆｆｆｆとして設定される
ことを特徴とする請求項３に記載のマルチキャスト転送装置。
【請求項５】
前記転送ユニットは、ＳＲＡＭ上に前記転送テーブルを格納するか、またはＳＲＡＭ上に前記索引配列と前記転送テーブルとを格納することを特徴とする請求項１から請求項４の何れかに記載のマルチキャスト転送装置。
【請求項６】
データセンター向けのマルチキャスト転送方法であって、
前記データセンター内のサーバーのマルチキャストアドレスが一連の連続マルチキャストアドレスにおけるアドレスであり、
着信マルチキャストデータパケットを受信するステップと、
前記着信マルチキャストデータパケットのヘッダから宛先ＭＡＣアドレスを抽出するステップと、
抽出された宛先ＭＡＣアドレスと所定のマスク項目との間で論理ＡＮＤ演算を実行して索引値を取得するステップと、
取得された索引値を使用して出力ポート系列を決定するステップと、
決定された出力ポート系列内に示されるポートから前記着信マルチキャストデータパケットを出力するステップと
を含むことを特徴とするマルチキャスト転送方法。
【請求項７】
取得された索引値を使用して出力ポート系列を決定するステップにおいて、
取得された索引値を転送テーブルの索引値として使用して、当該転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定し、
あるいは、最初に、取得された索引値を索引配列の索引値として使用して、当該索引配列内の対応するテーブル項目に直接ヒットさせることにより転送テーブルの索引値を取得し、次に、当該索引配列がヒットした当該転送テーブルの索引値を使用して、転送テーブル内の対応するテーブル項目に直接ヒットさせることにより、出力ポート系列を決定する
ことを特徴とする請求項６に記載のマルチキャスト転送方法。
【請求項８】
所定のマスク項目は、前記データセンター内のサーバー総数に基づいて設定されることを特徴とする請求項６又は請求項７に記載のマルチキャスト転送方法。
【請求項９】
請求項１から請求項５の何れかに記載のマルチキャスト転送装置を含むことを特徴とするＯｐｅｎＦｌｏｗスイッチ。
【請求項１０】
請求項１から請求項５の何れかに記載のマルチキャスト転送装置を含むことを特徴とするイーサネットスイッチ。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１３−５５６４２（Ｐ２０１３−５５６４２Ａ）
【公開日】平成２５年３月２１日（２０１３．３．２１）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１２−１５２２３９（Ｐ２０１２−１５２２３９）
【出願日】平成２４年７月６日（２０１２．７．６）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．イーサネット
２．Ｌｉｎｕｘ
【出願人】（５０５４１８８７０）エヌイーシー（チャイナ）カンパニー， リミテッド (108)
【氏名又は名称原語表記】ＮＥＣ（Ｃｈｉｎａ）Ｃｏ．，Ｌｔｄ．
【Ｆターム（参考）】
【公開日】平成２５年３月２１日（２０１３．３．２１）
【国際特許分類】
【出願番号】特願２０１２−１５２２３９（Ｐ２０１２−１５２２３９）
【出願日】平成２４年７月６日（２０１２．７．６）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．イーサネット
２．Ｌｉｎｕｘ
【出願人】（５０５４１８８７０）エヌイーシー（チャイナ）カンパニー， リミテッド (108)
【氏名又は名称原語表記】ＮＥＣ（Ｃｈｉｎａ）Ｃｏ．，Ｌｔｄ．
【Ｆターム（参考）】
[ Back to top ]