(57)【要約】【課題】利用する仮想ポートＩＤの数を低減させることができるノード装置を提供する。【解決手段】マルチキャスト通信を行うノード装置であって、前記ノード装置が持つ物理ポートを記憶する物理ポート記憶部と、前記物理ポート記憶部から物理ポートの集合を読み出し、読み出した物理ポートの集合を複数の集合に分割し、分割されたそれぞれの集合における物理ポートの全ての組合せの数を算出し、この組合せに基づいて、パケットヘッダに書き込む範囲内の数である仮想ポートＩＤを求め、仮想ポートＩＤを割り当てる組合せ計算部を有する。【選択図】図１
2011166614.tif 000002
【特許請求の範囲】
【請求項１】
マルチキャスト通信を行うノード装置であって、
前記ノード装置が持つ物理ポートを記憶する物理ポート記憶部と、
前記物理ポート記憶部から物理ポートの集合を読み出し、読み出した物理ポートの集合を複数の集合に分割し、分割されたそれぞれの集合における物理ポートの全ての組合せの数を算出し、この組合せに基づいて、パケットヘッダに書き込む範囲内の数である仮想ポートＩＤを求め、仮想ポートＩＤを割り当てる組合せ計算部
を有することを特徴とするノード装置。
【請求項２】
前記組合せ計算部は、物理ポートの集合を複数の集合に分割する際に、物理ポートの集合を等分に分割することを特徴とする請求項１記載のノード装置。
【請求項３】
マルチキャスト通信を行うノード装置のコンピュータを用いて、
前記コンピュータの組合せ計算部が、
前記コンピュータの物理ポート記憶部から物理ポートの集合を読み出し、読み出した物理ポートの集合を複数の集合に分割し、分割されたそれぞれの集合における物理ポートの全ての組合せの数を算出し、この組合せに基づいて、パケットヘッダに書き込む範囲内の数である仮想ポートＩＤを求め、仮想ポートＩＤを割り当てるステップ
を実行するノード装置の仮想ポートＩＤ割り当て方法。
【請求項４】
マルチキャスト通信を行うノード装置のコンピュータに、
前記コンピュータの物理ポート記憶部から物理ポートの集合を読み出し、読み出した物理ポートの集合を複数の集合に分割し、分割されたそれぞれの集合における物理ポートの全ての組合せの数を算出し、この組合せに基づいて、パケットヘッダに書き込む範囲内の数である仮想ポートＩＤを求め、仮想ポートＩＤを割り当てる手段
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチキャスト配信を行うノード装置、ノード装置の仮想ポートＩＤ割り当て方法、プログラム処理に関する。
【背景技術】
【０００２】
マルチキャスト配信とは、パケット通信ネットワークにおいて、複数ホストにパケットを効率的に送信する技術である。ノード装置（ルータ）は必要に応じてパケットを複製し、複数の物理ポートに出力する。この動作を繰り返しながらパケットを転送することで、複数ホストに効率的にパケットを送信できる。
【０００３】
非特許文献１記載のＩＰ  ｍｕｌｔｉｃａｓｔでは、ノード装置は、マルチキャストのための転送表を管理し、グループに対応する物理ポートを転送表から検索し、出力先の物理ポートを決定していた。図４にこの方式によって配信されている状況の一部を示す。しかしながら、ホストからの要求によってノード装置の状態が頻繁に更新されるという課題がある。
【０００４】
一方、非特許文献４記載のＦｒｅｅ  Ｒｉｄｉｎｇ  Ｍｕｌｔｉｃａｓｔは、パケットヘッダに物理ポート一覧をエンコードすることによって、上記（非特許文献１）の課題を解決している。図５にこの方式によって配信されている状況の一部を示す。この方式では、全てのノード装置の物理ポート（文献中ではリンクと記載）に一意のＩＤ（以下、ＰＰＩＤ）を与える。そして、ツリー上の配信経路（配信木）を構成する物理ポートのＩＤを、非特許文献３記載のＢｌｏｏｍ  ｆｉｌｔｅｒという方法によってパケットヘッダにエンコードする。ノード装置は、パケットヘッダに自分の物理ポートＩＤが含まれていれば、その物理ポートにパケットを出力する。Ｂｌｏｏｍ  ｆｉｌｔｅｒにエンコードできるＩＤの数には上限があるため、配信木を構成する物理ポートの数はＢｌｏｏｍ  ｆｉｌｔｅｒにエンコードできるＩＤの数が上限となる。
【０００５】
この点に関して、非特許文献２に記載のＬＩＰＳＩＮは、一つ以上のノード装置に含まれる複数の物理ポートに一つの仮想ポートＩＤ（以下、ＶＰＩＤ）を割り当てることで、配信可能な物理ポートの数を増やすことを提案している。図６にこの方式によって５つのＰＰＩＤを２つのＶＰＩＤで表現できる例を示す。この方式では、パケットヘッダに自分が管理する仮想ポートＩＤが含まれていれば、ノード装置はその仮想ポートＩＤに対応する物理ポートにパケットを出力する。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Stephen Deering、 “Host extensions for IP multicasting、“ IETF Request for Comments 1112、 August 1989. http://www.ietf.org/rfc/rfc1112.txt
【非特許文献２】Petri Jokela、 Andras Zahemszky、 Christian Esteve Rothenberg、 Somaya Arianfar and Pekka Nikander、 “LIPSIN: line speed publish/subscribe inter-networking、” Proc. of SIGCOMM、 2009. http://portal.acm.org/citation.cfm?id=1592568.1592592
【非特許文献３】Michael Mitzenmacher and Eli Upfal、 “確率と計算 -乱択アルコ゛リス゛ムと確率的解析-、” 共立出版、 pp.150-154、 2009.
【非特許文献４】S. Ratnasamy、 A. Ermolinskiy、 and S. Shenker、 “Revisiting IP multicast、” Proc. of SIGCOMM、 2006. http://conferences.sigcomm.org/sigcomm/2006/discussion/getpaper.php?paper_id=2
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述した非特許文献に記載されたＬＩＰＳＩＮには、仮想ポートを構成する物理ポートの組の決定方法について述べられてないという問題がある。例えば、単純に一つのノード装置が持つ全ての物理ポートから取りうる全ての組み合わせについて仮想ポートＩＤを設定する場合、仮想ポートＩＤの総数が多すぎて管理しきれない可能性がある。以下に、さらに具体的に説明する。
【０００８】
以下、簡単のためにある１台のノード装置の物理ポートだけからなる物理ポートの組を仮想ポートとして扱う（図６のＶＰＩＤ１のように複数ノード装置に渡る仮想ポートではなく、ＶＰＩＤ２のように単一ノード装置の物理ポートのみによって構成される仮想ポートのみを考えるということ）。また、単にポートといった場合には物理ポートと仮想ポートの両方を表わすことにする。
例えば、３２個の物理ポートを持つノード装置の場合、すべての物理ポートの組み合わせに対して仮想ポートＩＤを割り当てるためには、Σｉ∈｛１，…，３２｝３２Ｃｉ＝２３２−１個のポートＩＤが必要になる。実際のノード装置（ルータ）のメモリサイズを参考に、一つのノード装置が管理できるポートＩＤの上限数を２１７＝１３１０７２個と仮定し、可能な限りの仮想ポートＩＤのみを用いるとすると、４個以下の組み合わせしか管理できないことになる。これは、図７に示すように３２個の物理ポートから５個以下の組み合わせの総数は２１７個を超えるためである。つまり、物理ポート１、２、３、４の組み合わせからなる仮想ポートは使えるが、物理ポート１、２、３、４、５のように５つ以上の物理ポートを組み合わせる仮想ポートは使えない。この結果、たとえば入力されたパケットをすべての物理ポートから出力するためには、図８に示すように８（＝３２／４）個の仮想ポートＩＤをパケットヘッダに書き込む必要がある。
【０００９】
本発明は、このような事情に鑑みてなされたもので、その目的は、利用する仮想ポートＩＤの数を低減させることができるノード装置、ノード装置の仮想ポートＩＤ割り当て方法、プログラムを提供することにある。
【課題を解決するための手段】
【００１０】
上述した課題を解決するために、本発明は、マルチキャスト通信を行うノード装置であって、前記ノード装置が持つ物理ポートを記憶する物理ポート記憶部と、前記物理ポート記憶部から物理ポートの集合を読み出し、読み出した物理ポートの集合を複数の集合に分割し、分割されたそれぞれの集合における物理ポートの全ての組合せの数を算出し、この組合せに基づいて、パケットヘッダに書き込む範囲内の数である仮想ポートＩＤを求め、仮想ポートＩＤを割り当てる組合せ計算部を有することを特徴とする。
【００１１】
また、本発明は、上述のノード装置において、前記組合せ計算部は、物理ポートの集合を複数の集合に分割する際に、物理ポートの集合を等分に分割することを特徴とする。
【００１２】
また、本発明は、マルチキャスト通信を行うノード装置のコンピュータを用いて、前記コンピュータの組合せ計算部が、前記コンピュータの物理ポート記憶部から物理ポートの集合を読み出し、読み出した物理ポートの集合を複数の集合に分割し、分割されたそれぞれの集合における物理ポートの全ての組合せの数を算出し、この組合せに基づいて、パケットヘッダに書き込む範囲内の数である仮想ポートＩＤを求め、仮想ポートＩＤを割り当てるステップを実行するノード装置の仮想ポートＩＤ割り当て方法である。
【００１３】
また、本発明は、マルチキャスト通信を行うノード装置のコンピュータに、前記コンピュータの物理ポート記憶部から物理ポートの集合を読み出し、読み出した物理ポートの集合を複数の集合に分割し、分割されたそれぞれの集合における物理ポートの全ての組合せの数を算出し、この組合せに基づいて、パケットヘッダに書き込む範囲内の数である仮想ポートＩＤを求め、仮想ポートＩＤを割り当てる手段として機能させるためのプログラムである。
【発明の効果】
【００１４】
以上説明したように、この発明によれば、全ての物理ポートからパケットを出力するために必要な仮想ポートＩＤの数を減らすことができ、パケットヘッダにエンコードするＩＤの数を減らすことができる。
【図面の簡単な説明】
【００１５】
【図１】この発明の一実施形態によるノード装置の構成を示す概略ブロック図である。
【図２】本実施形態における物理ポートの一例を説明する図である。
【図３】組合せ計算部２０が行う計算の一例を説明する図である。
【図４】マルチキャスト通信方式によって配信される一例を説明する図である。
【図５】マルチキャスト通信方式によって配信される一例を説明する図である。
【図６】５つのＰＰＩＤを２つのＶＰＩＤで表現できる場合を説明する図である。
【図７】ノード装置が管理できる組合せについて説明する図である。
【図８】仮想ポートが８個である場合を説明する図である。
【発明を実施するための形態】
【００１６】
以下、本発明の一実施形態による仮想ポートの管理について図面を参照して説明する。
図１は、この発明の一実施形態によるノード装置の構成を示す概略ブロック図である。この仮想ポート管理は、マルチキャスト通信を行う各ノード装置に設けられる。
このノード装置１において、
物理ポート記憶部１０は、ノード装置１が持つ物理ポートを記憶する記憶装置である。
組合せ計算部２０は、物理ポート記憶部１０から物理ポートの集合を読み出し、読み出した物理ポートの集合を複数の集合に分割し、分割された集合における、物理ポートの全ての組合せの数を計算し、仮想ポートＩＤの計算を行う。
ポートＩＤ記憶部３０は、組合せ計算部２０が行った計算結果を記憶する記憶装置である。
通信部４０は、外部に接続される各ポートと通信を行う。
ポートＩＤ送信部５０は、Ｂｌｏｏｍ  ｆｉｌｔｅｒを生成する装置（例えば、送信サーバ）にポートＩＤを通信部４０によって送信する。
出力ポート決定部６０は、送信源（送信サーバのこと）から送信されたデータパケットを通信部４０によって受信すると、そのデータパケットのヘッダに書き込まれたＢｌｏｏｍ  ｆｉｌｔｅｒに含まれるポートを決定する。
パケット複製部７０は、出力ポート決定部６０が通信部４０によって受信したデータパケットを複製し、通信部４０によってデータパケットを出力する。
【００１７】
図２は、本実施形態における物理ポートの一例を説明する図である。この実施形態においては、図２に示すように、３２個の物理ポートを持つノード装置を一例として説明する。このような３２個の物理ポートがある場合における、組合せ計算部２０が行う仮想ポートＩＤの計算方法について以下、説明する。
【００１８】
組合せ計算部２０は、３２個の物理ポートを持つノード装置の場合、物理ポートを１６個ずつ二つの集合に分割し、分割された各集合において、取りうる全ての組み合わせを計算する。ここでは、図３に示すように、それぞれ２１６−１個のポートＩＤが必要になる（ノード装置全体では２×（２１６−１）＝２１７−２個のポートＩＤが必要になる）。
【００１９】
ここで、本発明の効果を簡単に評価する。実際のノード装置（ルータ）のメモリサイズを参考に、一つのノード装置が管理できるポートＩＤの上限数を２１７個と仮定すると、上述したような、物理ポートが３２個の場合においては、全てのポートＩＤが管理可能である。入力されたパケットを全ての物理ポートから出力するためには、図２に示すように２個の仮想ポートＩＤ（ＶＰＩＤ１、ＶＰＩＤ２）をパケットヘッダに書き込むことになる。この例では、本発明の方法は単純な方法に比べて全ての物理ポートからパケットを出力するために必要な仮想ポートＩＤの数を８個から２個に減らすことができている。その結果、パケットヘッダの  Ｂｌｏｏｍ  ｆｉｌｔｅｒにエンコードするＩＤの数を減らせるため、配信可能な物理ポートＩＤの数を増やすことができる。
【００２０】
また、ここでは、仮想ポートＩＤの数を得ることができたら、組合せ計算部２０は、その仮想ポートＩＤの数に応じた仮想ポートＩＤ（例えば、ＶＰＩＤ１、ＶＰＩＤ２）を割り当てる。
【００２１】
次に、ノード装置１の動作を説明する。このノード装置１が設けられたネットワークにおいて、全てのノード装置の組合せ計算部２０は、予め仮想ポートＩＤを計算し、計算結果をポートＩＤ記憶部３０に記憶する。そして、ポートＩＤ送信部５０は、Ｂｌｏｏｍ  ｆｉｌｔｅｒを生成する装置にポートＩＤを通信部４０によって送信する。
【００２２】
送信源から送信されたデータパケットを通信部４０によって受信すると、出力ポート決定部６０は、そのパケットのヘッダに書き込まれたＢｌｏｏｍ  ｆｉｌｔｅｒに含まれるポートを決定し、パケット複製部７０によってデータパケットを複製し、通信部４０によってパケットを出力する。
【００２３】
各受信ホストが送信源に配信を要求すると、送信源は全受信ホストまでの最短経路を基に配信木を生成する。送信源は、配信木を構成するポートを含むＢｌｏｏｍ  ｆｉｌｔｅｒを作成し、パケットヘッダに書き込み、送信する。このパケットヘッダを含むパケットを受信したノード装置は、Ｂｌｏｏｍ  ｆｉｌｔｅｒに含まれるポートに従い、パケットを転送していく。このようにして、マルチキャスト通信が行われる。
【００２４】
なお、上述の実施形態において、組合せ計算部２０は、物理ポートの集合を分割する際、等分するようにした。これにより、転送表のエントリ数を最小にすることができる。ここでは、組合せ計算部２０は、物理ポートの集合を分割する場合、等分割する場合について説明したが、この分割は等分割でなくともよい。
【００２５】
また、上述した実施形態は、仮想ポートの生成方法に関するものであり、そのエンコード方法は、Ｂｌｏｏｍ  ｆｉｌｔｅｒに限定されるものではない。例えば、出力ポートＩＤを木構造のまま表現し、パケットヘッダに搭載するようなマルチキャスト方法も考えられる。このような方法においても、本実施形態によってエンコードするポートＩＤ数を削減することにより、同様の効果を得ることができる。
【００２６】
また、以上説明した実施形態において、組合せ計算部２０は、組み合わせを行う物理ポートの集合全体から組み合わせを求めるのではなく、物理ポートの集合を複数に分割し、分割されたそれぞれの集合に対して取り得る全ての組み合わせを求めるようにした。特に、３２個の物理ポートを２等分して２つの集合を得て、この得られた２つの集合のそれぞれについて、取り得る全ての組合せを求めるようにした。
【００２７】
ここでは、組合せ計算部２０は、２つに分割する以外に、３つ以上に分割するようにしてもよい。また、２つに分割し、取り得る全ての組合せの数が、所定の数以下であるか否かを比較し、所定の数以下で無い場合には、この集合のそれぞれを、さらに分割し、分割されたそれぞれの集合において、取り得る全ての組合せ数を求めるようにしてもよい。この所定の数とは、例えば、実際のノード装置（ルータ）のメモリサイズを参考に、一つのノード装置が管理できるポートＩＤの上限数であり、これを組合せ計算部２０の所定のメモリ領域に記憶しておき、これと比較して判断するようにしてもよい。これにより、仮想ポートＩＤの総和を抑えつつ、パケットヘッダにエンコードするポートＩＤ数を削減でき、配信可能な物理ポートの数を増やすことができる。
【００２８】
本発明のノード装置は、コンピュータとプログラムによっても実現することができ、プログラムを記憶媒体に記録することも、ネットワークを通じて提供することも可能である。
【００２９】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００３０】
１  ノード装置
１０  物理ポート記憶部
２０  組合せ計算部
３０  ポートＩＤ記憶部
４０  通信部
５０  ポートＩＤ送信部
６０  出力ポート決定部
７０  パケット複製部
【図１】
2011166614.tif 000003
【図２】
2011166614.tif 000004
【図３】
2011166614.tif 000005
【図４】
2011166614.tif 000006
【図５】
2011166614.tif 000007
【図６】
2011166614.tif 000008
【図７】
2011166614.tif 000009
【図８】
2011166614.tif 000010