(57)【要約】【課題】共有セグメントに複数のマルチキャスト配信ルータのインタフェースが接続される構成において、それらのインタフェース集合で高い負荷分散を実現すること。【解決手段】配信ルータ４が、共有セグメント５を介して配信されるフローごとにフローハッシュ値を計算し、ハッシュ空間内に等間隔になるように配置される各仮想ＩＦの担当領域に対して、その担当領域に含まれるフローハッシュ値に該当する各フローを、仮想ＩＦに対応付ける第１対応付け処理と、配信ルータ４の実ＩＦに対して１つ以上の仮想ＩＦから構成される仮想ＩＦグループを対応付ける第２対応付け処理とを実行し、各フローが特定した各実ＩＦによって配信されるように制御する。【選択図】図１
2014036274.tif 000002
【特許請求の範囲】
【請求項１】
ホストにマルチキャストのフローを配信する複数台の配信ルータと１台以上の前記ホストとが共有セグメントに接続され、その共有セグメントに送信されるパケットは、前記共有セグメントに接続される前記配信ルータおよび前記ホストがそれぞれ受信可能であるマルチキャスト配信システムに用いられる前記配信ルータによるマルチキャスト配信制御方法であって、
前記配信ルータは、
前記共有セグメントを介して前記配信ルータによる配信されるフローごとに、そのフローの識別情報を引数として所定のハッシュ空間へと射影するハッシュ関数を計算することで、フローハッシュ値を計算し、
前記所定のハッシュ空間内に等間隔になるように配置される複数の仮想ＩＦハッシュ値によって区切られるハッシュ空間内の所定領域を、各仮想ＩＦの担当領域とし、その担当領域に含まれる前記フローハッシュ値に該当する各フローを、前記仮想ＩＦに対応付ける第１対応付け処理と、
前記共有セグメントに接続される前記配信ルータのインタフェースを実ＩＦとし、１つの実ＩＦに対して１つ以上の仮想ＩＦから構成される仮想ＩＦグループを対応付ける第２対応付け処理とを実行し、
前記フローハッシュ値から前記第１対応付け処理により対応付けられる前記仮想ＩＦを特定し、特定した前記仮想ＩＦから前記第２対応付け処理により対応付けられる前記実ＩＦを特定することで、各フローが特定した各実ＩＦによって配信されるように制御することを特徴とする
マルチキャスト配信制御方法。
【請求項２】
前記配信ルータは、前記第２対応付け処理において、前記各仮想ＩＦを静的ラウンドロビン方式で順番に前記実ＩＦの前記仮想ＩＦグループに対応付けることを特徴とする
請求項１に記載のマルチキャスト配信制御方法。
【請求項３】
前記配信ルータは、前記第２対応付け処理において、前記各実ＩＦの余剰リソースに応じた重み付けラウンドロビン方式で順番に前記実ＩＦの前記仮想ＩＦグループに対応付けることを特徴とする
請求項１に記載のマルチキャスト配信制御方法。
【請求項４】
前記各仮想ＩＦグループに属する仮想ＩＦの所属関係は、自身の仮想ＩＦグループと隣接する他の仮想ＩＦグループとを区切る仮想グループしきいにより決定されており、
前記配信ルータは、前記第２対応付け処理を再計算するときには、前記仮想グループしきいを仮想ＩＦの個数単位で１つ以上シフトすることで、前記互いに隣接する２つの仮想ＩＦグループに属する仮想ＩＦの所属関係をそれぞれ変更することを特徴とする
請求項１ないし請求項３のいずれか１項に記載のマルチキャスト配信制御方法。
【請求項５】
ホストにマルチキャストのフローを配信する複数台の配信ルータと１台以上の前記ホストとが共有セグメントに接続され、その共有セグメントに送信されるパケットは、前記共有セグメントに接続される前記配信ルータおよび前記ホストがそれぞれ受信可能であるマルチキャスト配信システムに用いられる前記配信ルータであって、
前記配信ルータは、
前記共有セグメントを介して前記配信ルータによる配信されるフローごとに、そのフローの識別情報を引数として所定のハッシュ空間へと射影するハッシュ関数を計算することで、フローハッシュ値を計算し、
前記所定のハッシュ空間内に等間隔になるように配置される複数の仮想ＩＦハッシュ値によって区切られるハッシュ空間内の所定領域を、各仮想ＩＦの担当領域とし、その担当領域に含まれる前記フローハッシュ値に該当する各フローを、前記仮想ＩＦに対応付ける第１対応付け処理と、
前記共有セグメントに接続される前記配信ルータのインタフェースを実ＩＦとし、１つの実ＩＦに対して１つ以上の仮想ＩＦから構成される仮想ＩＦグループを対応付ける第２対応付け処理とを実行し、
前記フローハッシュ値から前記第１対応付け処理により対応付けられる前記仮想ＩＦを特定し、特定した前記仮想ＩＦから前記第２対応付け処理により対応付けられる前記実ＩＦを特定することで、各フローが特定した各実ＩＦによって配信されるように制御するルータ状態管理部を有することを特徴とする
配信ルータ。
【請求項６】
前記配信ルータは、前記第２対応付け処理において、前記各仮想ＩＦを静的ラウンドロビン方式で順番に前記実ＩＦの前記仮想ＩＦグループに対応付けることを特徴とする
請求項５に記載の配信ルータ。
【請求項７】
前記配信ルータは、前記第２対応付け処理において、前記各実ＩＦの余剰リソースに応じた重み付けラウンドロビン方式で順番に前記実ＩＦの前記仮想ＩＦグループに対応付けることを特徴とする
請求項５に記載の配信ルータ。
【請求項８】
前記各仮想ＩＦグループに属する仮想ＩＦの所属関係は、自身の仮想ＩＦグループと隣接する他の仮想ＩＦグループとを区切る仮想グループしきいにより決定されており、
前記配信ルータは、前記第２対応付け処理を再計算するときには、前記仮想グループしきいを仮想ＩＦの個数単位で１つ以上シフトすることで、前記互いに隣接する２つの仮想ＩＦグループに属する仮想ＩＦの所属関係をそれぞれ変更することを特徴とする
請求項５ないし請求項７のいずれか１項に記載の配信ルータ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチキャスト配信制御方法、および、配信ルータに関する。
【背景技術】
【０００２】
ＩＰルータがＩＧＭＰ（Internet Group Management Protocol）／ＭＬＤ（Multicast Listener Discovery）プロトコルを用いてＩＰマルチキャストの配信制御を行う技術分野に属する。特に、単一の共有セグメント（イーサネット（登録商標）のＶＬＡＮなど）に複数のルータインタフェースが冗長接続される系において、複数のインタフェース間で配信アクセスを分散するための制御方法と装置システムおよび回路構成に関する。
【０００３】
ＩＰルータとＩＰホスト区間のＩＰマルチキャストの配信制御を行うプロトコルとして、ＩＰｖ４を利用する場合のＩＧＭＰ／ＩＰｖ６を利用する場合のＭＬＤが存在する。
また、その中でも、配信フローの送信元ＩＰアドレス（以下、Ｓ（Source）アドレス）の宛先ＩＰアドレス（以下、Ｇ（Group）アドレス）の両方（以下、（Ｓ、Ｇ））を指定して制御を行うＳＳＭ（Source-Specific Multicast）方式に対応したプロトコルとして、非特許文献１に記載のＩＧＭＰｖ３／非特許文献２に記載のＭＬＤｖ２が存在する。
【０００４】
ＩＧＭＰ／ＭＬＤでは、非特許文献３に記載のＰＩＭ−ＳＭ（Protocol-Independent Multicast Sparse Mode）などのＩＰマルチキャストルーティングプロトコルのような複雑な経路制御を行わないため、実装仕様が簡素で軽い利点がある。この点から、ＬＡＮ系のゲートウェイやアクセス系のエッジでＩＧＭＰ／ルータ、ＬＡＮ（Local Area Network）系のホストにＩＧＭＰ／ＭＬＤホストが一般的に適用されている。
【０００５】
ＩＧＭＰ／ＭＬＤルータは、各フローの視聴状態（ｊｏｉｎ／ｌｅａｖｅ）を示すレポートメッセージを受信すると、レポートを受信したインタフェースで当該フローの配信を開始／停止する。
ただし、同一セグメント（ＶＬＡＮ（Virtual LAN）など）に複数のルータが接続される場合、クエリア選択メカニズムが適用される。
【０００６】
図２１は、IGMP／MLDのクエリア選択メカニズムを示す説明図である。複数のルータインタフェースの中でＩＰアドレスが最小となるインタフェース（以下、クエリアと呼ぶ）のみｊｏｉｎ／ｌｅａｖｅの応答制御を行う。これにより、クエリアからはフローが配信され（符号２３０１）、非クエリアからはフローは未配信となる（符号２３０２）。
図２２は、重複配信の例を示す説明図である。図２１のようにクエリアを選択しないと、同一フローに対する３台のルータによる重複配信が行われてしまう（符号２４０１）。
【０００７】
以下、ＩＧＭＰ／ＭＬＤの課題を説明する。
【０００８】
図２３は、従来方式（IGMP／MLD）を示す説明図である。まず、第一の課題として、単一インタフェース（クエリアｘ１）で、全フローを配信するため（符号２５０１）、系全体として配信資源（パス帯域、ルータ処理能力など）の利用効率が悪い点が挙げられる。また、単純にＩＰアドレスの大小順位で選択するため、必ずしも最大性能を提供できるインタフェースを選択するとは限らない。
図２４は、負荷分散のイメージを示す説明図である。図２３とは異なり、フロー単位に配信インタフェースを分散させることで（符号２６０１）、リソース余剰がある複数のインタフェース間での負荷分散が実現される。
【０００９】
第二の課題として、系全体として障害リスク分散ができない点が挙げられる。すなわち、クエリアに障害が生じると、新たなクエリアが選出されて配信切替えが行われるものの、全ての配信中フローに対して一旦はサービス断が生じる。これらの２つの課題は、地上デジタル放送／ＢＳデジタル放送のＩＰ再送信サービスなどのような場合は特に重要な課題となる。
【００１０】
図２５は、ダイレクトハッシュ方式を示す説明図である。ここで、前記の第１の課題および第２の課題を解決するための方法として、特許文献１に記載のマルチキャスト配信システムが挙げられる。この配信システムは、フロー単位に配信インタフェースを分散する。そのとき、フローとインタフェースの対応付けを「ダイレクトハッシュ方式」で行う。
まず、ホストから受信するＩＧＭＰ／ＭＬＤレポートメッセージ（ｊｏｉｎ／ｌｅａｖｅ）内のＭＬＤヘッダ２７０１から、配信フロー単位の送信元ＩＰアドレス（以下、Ｓアドレス）と宛先グループＩＰアドレス（以下、Ｇアドレス）の情報を取得する（読み出し処理２７０２）。次に、インタフェースの総数Ｎから、剰余演算（mod）により、ハッシュ値を計算する（符号２７０３）。さらに、クエリア順位に一致するフローを直接ルータインタフェースにマッピングする（符号２７０４）。
【００１１】
図２６は、クエリア順位の計算方法を示す説明図である。各ルータＲ１〜Ｒ３は、起動時に自身のＲＭＴ（Router Management Table：「ルータ管理テーブル」）を作成する（符号２８０１）。そして、ルータＲ１は、作成したルータ管理テーブルに、自身のＩＦを登録する（符号２８０２）。
【００１２】
ルータＲ１は、クエリア選択メカニズムを拡張し、他のＩＧＭＰ／ＭＬＤルータのインタフェースから送信されるＳＱ（Startup Query）パケットやＧＱ（General Query）パケットを受信する都度、送信元ＩＰアドレス情報を取得・登録する（符号２８０３）。
ルータＲ１は、ルータ管理テーブルに登録されているＩＰアドレスの相対的な大小順位の関係により、インタフェースの総数Ｎおよび全てのインタフェースのクエリア順位を決定する（符号２８０４）。
ルータＲ１は、ＧＱの受信時には、ルータ管理テーブルに登録されているＧＱ受信タイマの設定と更新を行う（符号２８０５）。
【００１３】
そして、各フローに対するハッシュ値と各インタフェースのクエリア順位を比較して、一致したインタフェースに当該フローの配信権を付与することで、フロー毎に一つだけの配信インタフェースが選択される（符号２８０６）。
例えば、ＳアドレスとＧアドレスの和をインタフェース数Ｎで剰余算するハッシュ計算を行うと、Ｎ=３の場合は、剰余算の結果は０、１、２となり、ハッシュ値１をクエリア順位１、ハッシュ値２をクエリア順位２、ハッシュ値０をクエリア順位３に割り付ける。
【００１４】
ルータ管理テーブルへのエントリ追加処理（Ｓ２８１０）は、ＳＱ／ＧＱを受信し（Ｓ２８１１）、その受信内容が未登録か判定し（Ｓ２８１２）、未登録ならそのＩＰアドレスを登録し（Ｓ２８１３）、符号２８０４で述べたクエリア順位を計算し（Ｓ２８１４）、符号２８０５で述べたＧＱ受信タイマを設定する（Ｓ２８１５）各処理である。
ルータ管理テーブルへのエントリ削除処理（Ｓ２８２０）は、ＧＱ受信タイマのタイムアウトにより起動され（Ｓ２８２１）、エントリを削除し（Ｓ２８２２）、Ｓ２８１４と同様にクエリア順位を計算する（Ｓ２８２３）各処理である。
【００１５】
図２７は、ダイレクトハッシュによるフロー分散の例を示す説明図である。ここでは、３つのルータインタフェースで４つのフローを分散処理している。すなわち、ルータＲ１がフロー#２とフロー#３、ルータＲ２がフロー#１、ルータＲ３がフロー#４をそれぞれ配信する（符号２９０１）。
各ルータのフロー配信管理テーブルには、符号２９０２で示すように、各計算式で計算される各パラメータが格納される。
【００１６】
各ルータのフロー配信管理テーブルの更新処理および利用処理は、ＩＧＭＰ／ＭＬＤのｊｏｉｎ（Ｓ，Ｇ）を受信すると（Ｓ２９１０）、その（Ｓ，Ｇ）のエントリがフロー配信管理テーブルに存在するか否かを判定し（Ｓ２９１１）、存在しないときには、符号２９０２で示す計算式をｆ（Ｓ，Ｇ）として計算し、その結果をフロー配信管理テーブルに登録し（Ｓ２９１２）、パラメータｆの値が「１」か否かを判定し（Ｓ２９１３）、「１」なら（Ｓ，Ｇ）を配信し（Ｓ２９１４）、「１」でないなら、（Ｓ，Ｇ）を非配信とする（Ｓ２９１５）各処理である。
【００１７】
ダイレクトハッシュ方式には、インタフェースの増減時（障害／復旧、増減設）において、サービス中断の影響範囲が広範囲に及ぶ可能性がある。すなわち、インタフェースの数が変化することにより、クエリア順位とハッシュ値が変化するため、配信割当てが大きく変更され得る。これにより、切替え制御に伴うサービス断が発生する。
【００１８】
図２８は、ダイレクトハッシュ方式の課題を示す説明図である。ここでは、３つのインタフェースで６本のフローを分散配信している初期状態３００２から、４つ目のインタフェースが増設されて（符号３００１）、増設後状態３００３となる。
インタフェースの増設によって、各フローの配信割当て（フロー配信管理テーブルの内容）が再計算されている。すなわち、フロー#３はＩＦ#１からＩＦ#４、フロー#４はＩＦ#２からＩＦ#１、フロー#６はＩＦ#２からＩＦ#４へそれぞれ収容替えされる。
【先行技術文献】
【特許文献】
【００１９】
【特許文献１】特許願２０１０−１３１１０６号公報
【非特許文献】
【００２０】
【非特許文献１】ＩＥＴＦ、“Internet Group Management Protocol, Version 3”、［online］、［平成２４年６月２０日検索］、インターネット（ＵＲＬ：http://www.rfc-editor.org/rfc/rfc3376.txt）
【非特許文献２】ＩＥＴＦ、“Multicast Listener Discovery Version 2 (MLDv2) for IPv6”、［online］、［平成２４年６月２０日検索］、インターネット（ＵＲＬ：http://www.rfc-editor.org/rfc/rfc3810.txt）
【非特許文献３】ＩＥＴＦ、“Protocol Independent Multicast - Sparse Mode (PIM-SM)”、［online］、［平成２４年６月２０日検索］、インターネット（ＵＲＬ：http://www.rfc-editor.org/rfc/rfc4601.txt）
【発明の概要】
【発明が解決しようとする課題】
【００２１】
ダイレクトハッシュ方式の課題である、インタフェースの増減時において、サービス中断の影響範囲が広範囲に及ぶ点を検討する。インタフェースの変更前と変更後とで、収容されるインタフェースが変更されるフロー数が少ないほど、サービス中断の影響範囲をなるべく少なくすることができる。
【００２２】
図２９は、コンシステントハッシュ方式を示す説明図である。「コンシステントハッシュ方式」は、先のダイレクトハッシュ方式と異なり、フローだけではなくインタフェースに対してもハッシュ値を計算して、リング型のハッシュ空間３１０１上に計算値をプロットする。そして、フローとの方向距離が最近傍（例えば、右時計回りの最近傍）となるインタフェースに配信制御を割り当てる。
ここでは、｛ｉ１、ｉ２、ｉ３、ｉ４｝の４つのインタフェースにより、{ｆ１、ｆ２、ｆ３、ｆ４}の４本のフローを配信している。すなわち、フローｆ１はインタフェースｉ３、フローｆ２はインタフェースｉ２、フローｆ３はインタフェースｉ１、フローｆ４はインタフェースｉ４で配信する。
【００２３】
例えば、ハッシュ値の幅を０、１、２、３、…、Ｎ’−１（Ｎ’は自然数）とする。
ルータＩＦハッシュ値｛ｉ１、ｉ２、ｉ３、ｉ４｝は、インタフェースに割当てられたＩＰアドレスをＮ’で剰余算した結果である。
フローハッシュ値｛ｆ１、ｆ２、ｆ３、ｆ４｝はフローに割当てられたＳアドレスとＧアドレスの和をＮ’で剰余算した結果である。ここで、Ｎ’はダイレクトハッシュ方式と異なり、インタフェース総数Ｎではなく任意に選定可能な設定パラメータである。すなわち、何らかの最適化目標や条件に応じ、最適なパラメータ値に設定する。
【００２４】
また、インタフェースに増減（障害／復旧、増減設）が生じた場合は、フローとインタフェースの方向距離を計算し直して配信制御の割り当てを変更する。ただし、Ｎ’はインタフェースの数には依存しないため、増減したインタフェース近傍にプロットされるフロー群のみ配信割当が変更される。
【００２５】
まず、インタフェース障害が生じた場合は、当該インタフェースで配信されていた全てのフローが、別の同一なインタフェース（例えば、反時計周りに一つ隣りのインタフェース）へと収容変更される。一方、他のフローに関しては、配信割当ての変更がない。
例えば、障害が生じたインタフェースｉ４を削除した場合は（符号３１０３）、フローｆ４だけがインタフェースｉ１に収容変更される（切替え）。
一方、インタフェースｉ４を追加（増設や障害からの切戻し）した場合は（符号３１０２）、フローｆ４だけがインタフェースｉ４に収容変更される。
【００２６】
しかし、コンシステントハッシュ方式には、以下の課題がある。
図３０は、インタフェースハッシュ値の局所集中による分散性能の劣化を示す説明図である。
左側は理想的なインタフェースハッシュの分散配置（理想３２０１）、右側は現実のインタフェースハッシュの分散配置（現実配置３２０２）である。すなわち、理想配置３２０１の方は、インタフェースあたり２フローずつ均等に分散できている。一方、同じフロー分布に対し、現実配置３２０２の方は、特定のインタフェースに負荷が集中する。例では、インタフェース０に６本、インタフェース１に１本、インタフェース２に０本、インタフェース３に１本のフローが割り当てられる。
このような負荷集中が発生する要因としては、リング空間の特定区間にインタフェースのハッシュ値が密集する状況になることが挙げられる。ハッシュ空間の大きさが大きいほど、密集の度合いも大きくなる。
【００２７】
ルータＩＦハッシュ値が局所集中する要因を検討する。
同一セグメントに複数のインタフェースを接続する状況を前提しており、ＩＰサブネットを同一とするのが一般的である。また、ネットワーク系の管理者が、運用の簡易さという観点から、各インタフェースのＩＰアドレスの値を一つずつインクリメントして手動設定する状況や、これらを自動システム化する場合も、実装管理の容易さという観点から自動インクリメントする状況などもある。
よって、ＩＰアドレスの値からハッシュ関数（剰余算）によってルータＩＦハッシュ値を決める方式では、現実的にはハッシュ値が連続した値（例えば、０、１、２、…）のことが十分想定される。
一方、フローハッシュ値がリング空間内で一様に分布すると仮定すると、先頭のインタフェース（ルータＩＦハッシュ値）に負荷が集中する。すなわち、本来の目的に沿った良好な負荷分散の特性が得られない。
【００２８】
負荷分散の性能を向上させるためには、インタフェースハッシュ値の特定区間への集中を防止するための何らかの手段が必要となる。
【００２９】
そこで、本発明は、共有セグメントに複数のマルチキャスト配信ルータのインタフェースが接続される構成において、それらのインタフェース集合で高い負荷分散を実現することを、主な目的とする。
【課題を解決するための手段】
【００３０】
前記課題を解決するために、本発明は、ホストにマルチキャストのフローを配信する複数台の配信ルータと１台以上の前記ホストとが共有セグメントに接続され、その共有セグメントに送信されるパケットが、前記共有セグメントに接続される前記配信ルータおよび前記ホストがそれぞれ受信可能であるマルチキャスト配信システムに用いられる前記配信ルータによるマルチキャスト配信制御方法であって、
前記配信ルータが、
前記共有セグメントを介して前記配信ルータによる配信されるフローごとに、そのフローの識別情報を引数として所定のハッシュ空間へと射影するハッシュ関数を計算することで、フローハッシュ値を計算し、
前記所定のハッシュ空間内に等間隔になるように配置される複数の仮想ＩＦハッシュ値によって区切られるハッシュ空間内の所定領域を、各仮想ＩＦの担当領域とし、その担当領域に含まれる前記フローハッシュ値に該当する各フローを、前記仮想ＩＦに対応付ける第１対応付け処理と、
前記共有セグメントに接続される前記配信ルータのインタフェースを実ＩＦとし、１つの実ＩＦに対して１つ以上の仮想ＩＦから構成される仮想ＩＦグループを対応付ける第２対応付け処理とを実行し、
前記フローハッシュ値から前記第１対応付け処理により対応付けられる前記仮想ＩＦを特定し、特定した前記仮想ＩＦから前記第２対応付け処理により対応付けられる前記実ＩＦを特定することで、各フローが特定した各実ＩＦによって配信されるように制御することを特徴とする。
【００３１】
これにより、実ＩＦを直接に所定のハッシュ空間へと射影することで発生する実ＩＦの担当領域の局所集中を予防できるので、共有セグメントに複数のマルチキャスト配信ルータのインタフェースが接続される構成において、それらのインタフェース集合で高い負荷分散を実現することができる。
【００３２】
本発明は、前記配信ルータが、前記第２対応付け処理において、各仮想ＩＦグループの構成要素である仮想ＩＦの数が各仮想ＩＦグループ間で均等になるようにして形成された各仮想ＩＦグループを、各実ＩＦに対応付けることを特徴とする。
【００３３】
これにより、各実ＩＦの割り当て担当となる仮想ＩＦの数が均等化されるので、各実ＩＦ間でフロー配信の負荷分散が実現される。
【００３４】
本発明は、前記配信ルータが、前記第２対応付け処理において、各仮想ＩＦグループの構成要素である仮想ＩＦの数が、割り当てられる各実ＩＦの余剰資源に比例するようにして形成された各仮想ＩＦグループを、各実ＩＦに対応付けることを特徴とする。
【００３５】
これにより、各実ＩＦの余剰資源がばらついている環境下でも、割り当て担当となる仮想ＩＦの数が均等化されるので、各実ＩＦ間でフロー配信の負荷分散が実現される。
【００３６】
本発明は、前記各仮想ＩＦグループに属する仮想ＩＦの所属関係が、自身の仮想ＩＦグループと隣接する他の仮想ＩＦグループとを区切る仮想グループしきいにより決定されており、
前記配信ルータが、前記第２対応付け処理を再計算するときには、前記仮想グループしきいを仮想ＩＦの個数単位で１つ以上シフトすることで、前記互いに隣接する２つの仮想ＩＦグループに属する仮想ＩＦの所属関係をそれぞれ変更することを特徴とする。
【００３７】
これにより、仮想ＩＦグループに属する仮想ＩＦの構成が大きく変更されることはないので、実ＩＦの増減設に伴う配信断や重複配信によるサービス影響範囲を最小化することが可能となる。
【発明の効果】
【００３８】
本発明によれば、共有セグメントに複数のマルチキャスト配信ルータのインタフェースが接続される構成において、それらのインタフェース集合で高い負荷分散を実現することができる。
【図面の簡単な説明】
【００３９】
【図１】本発明の一実施形態に関する配信ネットワークの系構成を示す構成図である。
【図２】本発明の一実施形態に関する配信ルータの回路構成を示す構成図である。
【図３】本発明の一実施形態に関するルータ管理テーブルの初期生成シーケンスを示すフローチャートである。
【図４】本発明の一実施形態に関するルータ管理テーブルのエントリ追加／更新シーケンスを示すフローチャートである。
【図５】本発明の一実施形態に関するルータ管理テーブルのエントリ削除シーケンスを示すフローチャートである。
【図６】本発明の一実施形態に関するルータ管理テーブルの終了削除シーケンスを示すフローチャートである。
【図７】本発明の一実施形態に関する仮想ＩＦ（Interface）ハッシュ値の計算方法を示す説明図である。
【図８】本発明の一実施形態に関するルータ管理テーブルの実施例を示す説明図である。
【図９】本発明の一実施形態に関するフロー配信テーブルの初期生成シーケンスを示すフローチャートである。
【図１０】本発明の一実施形態に関するフロー配信テーブルのエントリ追加／更新シーケンスを示すフローチャートである。
【図１１】本発明の一実施形態に関するフロー配信テーブルのエントリ削除シーケンスを示すフローチャートである。
【図１２】本発明の一実施形態に関するフロー配信テーブルの終了削除シーケンスを示すフローチャートである。
【図１３】本発明の一実施形態に関するフローに対するハッシュ計算方法と仮想IFへの割当ての実施例（１／３）を示す説明図である。
【図１４】本発明の一実施形態に関するフローに対するハッシュ計算と仮想IFへの割当ての実施例（２／３）を示す説明図である。
【図１５】本発明の一実施形態に関するフローに対するハッシュ計算と仮想IFへの割当ての実施例（３／３）を示す説明図である。
【図１６】本発明の一実施形態に関するフロー配信テーブルの実施例を示す説明図である。
【図１７】本発明の一実施形態に関する仮想インタフェースと実インタフェースの対応づけ（可変）を示す説明図である。
【図１８】本発明の一実施形態に関する仮想インタフェースと実インタフェースの対応づけ（静的）を示す説明図である。
【図１９】本発明の一実施形態に関する仮想インタフェースと実インタフェースの対応づけ（初期化）を示すフローチャートである。
【図２０】本発明の一実施形態に関する仮想インタフェースと実インタフェースの対応づけ（変更）を示すフローチャートである。
【図２１】IGMP／MLDのクエリア選択メカニズムを示す説明図である。
【図２２】重複配信の例を示す説明図である。
【図２３】従来方式（IGMP／MLD）を示す説明図である。
【図２４】負荷分散のイメージを示す説明図である。
【図２５】ダイレクトハッシュ方式を示す説明図である。
【図２６】クエリア順位の計算方法を示す説明図である。
【図２７】ダイレクトハッシュによるフロー分散の例を示す説明図である。
【図２８】ダイレクトハッシュ方式の課題を示す説明図である。
【図２９】コンシステントハッシュ方式を示す説明図である。
【図３０】インタフェースハッシュ値の局所集中による分散性能の劣化を示す説明図である。
【図３１】インタフェースハッシュ値の衝突例を示す説明図である。
【発明を実施するための形態】
【００４０】
以下、本発明の一実施形態について、図面を参照して詳細に説明する。
【００４１】
図１は、配信ネットワークの系構成（配信システム）を示す構成図である。マルチキャストフローは、配信サーバ１（Ｓ１、Ｓ２、…）から送信され、マルチキャスト配信網２、リンク３、配信ルータ４（Ｒ１、Ｒ２、Ｒ３、…）、共有セグメント５を経由し、ホスト６（Ｈ１、Ｈ２、Ｈ３、Ｈ４、…）に配信される。
これらの配信システムの各装置は、ＣＰＵ（Central Processing Unit）とメモリとハードディスク（記憶手段）とネットワークインタフェースを有するコンピュータとして構成され、このコンピュータは、ＣＰＵが、メモリ上に読み込んだプログラムを実行することにより、各処理部を動作させる。
配信ルータ４とホスト６間の信号パケットは、共有セグメント５を介して送受信される。信号パケットは、配信ルータ４から送信されるクエリとホスト６から送信されるレポートがある。 
【００４２】
図２は、配信ルータの回路構成を示す構成図である。配信ルータ４は、マルチキャスト配信網２と接続するＭＣ配信網接続インタフェース４１、マルチキャスト配信網２とフレーム送受信を行うＭＣ配信網フレーム転送部４２、共有セグメント５とフレーム送受信を行う共有セグメントフレーム転送部４４、共有セグメント５と接続する共有セグメント接続インタフェース４５、本特許における特長的なフロー配信制御を司る転送制御回路４３から構成される。
【００４３】
ＭＣ配信網接続インタフェース４１と共有セグメント接続インタフェース４５は、一般的な物理レイヤを司り、イーサネットの場合はＰＨＹレイヤに相当する。
ＭＣ配信網接続インタフェース４１は、受信ＩＦ部４１１と送信ＩＦ部４１２から成る。
共有セグメント接続インタフェース４５は、送信ＩＦ部４５１と受信ＩＦ部４５２から成る。
ＭＣ配信網フレーム転送部４２と共有セグメントフレーム転送部４４は、一般的なデータリンク層を司り、イーサネットの場合はＭＡＣレイヤに相当する。
ＭＣ配信網フレーム転送部４２は、フレーム受信部４２１とフレーム送信部４２２から成る。共有セグメントフレーム転送部４４は、フレーム受信部４４２とフレーム送信部４４１から成る。
【００４４】
転送制御回路４３は、配信状態管理部４３１、ＭＣ配信網連携部４３２、ルータ状態管理部４３３、ルータ管理テーブル４３４、フロー割当処理部４３５、フロー配信テーブル４３６、配信フィルタ部４３７から構成される。
配信状態管理部４３１は、従来のＩＧＭＰ／ＭＬＤルータなどに相当し、ＩＰマルチキャストフローのアクセス配信状態の管理を行う。ここで、ホスト６からの受信レポートの内容に従い、Ｊｏｉｎ／Ｌｅａｖｅの要求と現在の配信状況に応じて、ＭＣ配信網連携部４３２との配信に関する連携処理を行う。
ＭＣ配信網連携部４３２は、従来のＰＩＭルータなどに相当する。マルチキャスト配信網２と連携してＩＰマルチキャストルーティングの制御を行う。
配信フィルタ部４３７は、フロー割当処理部４３５からの指示を受けて、フロー単位の配信フィルタを開閉する。フィルタ解放されたフローは、ＭＣ配信網フレーム転送部４２から受信したフローパケットを共有セグメントフレーム転送部４４へ転送する。逆に、フィルタ閉鎖されたフローは転送せずに廃棄する。
【００４５】
ルータ状態管理部４３３は、同一セグメントに接続される全てのルータインタフェースの情報を管理する。共有セグメント接続インタフェース４５、共有セグメントフレーム転送部４４、配信状態管理部４３１を介して受信する他インタフェースからのＳＱパケットもしくはＧＱパケットの送信元ＩＰアドレスや受信時刻を検査し、インタフェース単位の死活監視を行う。ここで、これら処理情報をルータ管理テーブル４３４に登録する。また、フロー割当処理部４３５の指示に従い、ルータ管理テーブル４３４に登録したインタフェース情報を読み出して、フロー割当処理部４３５に引き渡す。
【００４６】
ルータ管理テーブル４３４は、ルータ状態管理部４３３において検査されたインタフェース情報を登録管理する。また、ルータ状態管理部４３３の指示に従い登録情報を引き渡す。
【００４７】
フロー割当処理部４３５は、フローに対する配信インタフェースの割当情報を管理する。共有セグメント接続インタフェース４５、共有セグメントフレーム転送部４４、配信状態管理部４３１を介して、ホスト６から受信するレポートに格納される（Ｓ、Ｇ）毎のフロー配信状態（Ｊｏｉｎ／Ｌｅａｖｅ）を検査してフローハッシュ値を計算する。
【００４８】
ルータ状態管理部４３３は、同一セグメント内の全てのルータと連携し、仮想インタフェース群を定義する（図７参照）。そして、ルータ状態管理部４３３は、仮想インタフェース群に属する仮想インタフェースごとのハッシュ値（以下、仮想ＩＦハッシュ値）を計算し、仮想ＩＦハッシュ値とフローハッシュ値との方向距離を計算する（後記する図１０のＳ１００８や、図１５の符号１５０１を参照）。そして、計算した方向距離が近い両ハッシュ値を対応付ける（第１対応付け）。
また、ルータ状態管理部４３３は、仮想ＩＦハッシュ値と実インタフェースのハッシュ値（以下、実ＩＦハッシュ値）との対応関係（第２対応付け）を計算する。
これにより、ルータ状態管理部４３３は、フローハッシュ値→（第１対応付け）→仮想ＩＦハッシュ値→（第２対応付け）→実ＩＦハッシュ値とたどることで、各配信フローに対する実インタフェースの割当てを決定し、その決定に従って、配信状態の制御を行う。ここで、これらの処理情報をフロー配信テーブル４３６に登録する。なお、第１対応付けおよび第２対応付けの詳細は、後記する図１７、図１８で説明する。
フロー配信テーブル４３６は、フロー割当処理部４３５において処理されたフロー毎のインタフェースに対する割当情報および配信状態を登録管理する。また、フロー割当処理部４３５の指示に従い登録情報を引き渡す。
【００４９】
図３は、ルータ管理テーブルの初期生成シーケンスを示すフローチャートである。
テーブルを新規生成して初期化するステップ（Ｓ３００）と、自ルータインタフェースのＩＰアドレス検査するステップ（Ｓ３０１）、自インタフェースのＩＰアドレスをテーブルにエントリ登録するステップ（Ｓ３０２）、当該エントリが自インタフェースであることを示すＩＦフラグを登録するステップ（Ｓ３０３）、当該エントリが自インタフェースであるため、他インタフェースの死活監視用タイマを無効化登録するステップ（Ｓ３０４）から構成される。
なお、これらの処理ステップは、ルータ状態管理部４３３によって実行される。
【００５０】
図４は、図３の処理後に、ルータ管理テーブルのエントリ追加／更新シーケンスを示すフローチャートである。
他のインタフェースからＳＱパケットもしくはＧＱパケットを受信するステップ（Ｓ４００）と、受信パケットのＩＰヘッダから送信元ＩＰアドレス（例えば、IPv6（MLDv2）の場合は、送信元ルータＩＦのリンクローカルアドレスなど）を検査するステップ（Ｓ４０１）と、ルータ管理テーブル４３４を検索して受信パケットの送信元ＩＰアドレスに対する既存のエントリが存在するかを確認するステップ（Ｓ４０２、Ｓ４０３）、存在する場合は当該エントリに対するクエリア死活監視タイマをリセットするステップ（Ｓ４０４）、存在しない場合は送信元ＩＰアドレスと計算されたハッシュ値を組にしてルータ管理テーブル４３４にエントリ登録するステップ（Ｓ４０５）、当該エントリに対するクエリア死活監視用タイマを開始設定するステップ（Ｓ４０６）から構成される。
なお、これらの処理ステップは、ルータ状態管理部４３３によって実行される。
【００５１】
図５は、ルータ管理テーブルのエントリ削除シーケンスを示すフローチャートである。
ルータ管理テーブル４３４に登録されたルータインタフェースの各エントリに対し、予め設定したクエリア死活監視用タイマの上限値に達しても当該インタフェースからのＳＱ／ＧＱパケットを受信しないことを検出判定するステップ（Ｓ５００）と、タイマ上限値を超過した場合は当該エントリを削除するステップ（Ｓ５０１）から構成される。
なお、これらの処理ステップは、ルータ状態管理部４３３によって実行される。
【００５２】
図６は、ルータ管理テーブルの終了削除シーケンスを示すフローチャートである。
ＩＧＭＰ／ＭＬＤルータ終了後に、ルータ管理テーブル４３３を削除するステップ（Ｓ６００）から構成される。
なお、これらの処理ステップは、ルータ状態管理部４３３によって実行される。
【００５３】
図７は、仮想ＩＦハッシュ値の計算方法を示す説明図である。まず、リングのハッシュ空間７０１を定義する。ハッシュ値の最大値（＝Ｎ’−１）を設定する。次に、仮想インタフェース数Ｍ’（＝２ｎ、ｎは自然数）を設定する。更に、Ｍ個の仮想インタフェースをリング上に配置する。例えば、Ｎ’／Ｍ’×仮想ノード番号ｉ（ｉ＝１、２、３、…、Ｍ）を逐次計算し、計算値と一致するハッシュ値の上に、仮想ノード番号に対応する仮想ノードを配置する。なお、Ｍ個の仮想インタフェースが互いに等間隔になるように、ハッシュ空間７０１に配置されることが望ましい。
【００５４】
図３１は、図７のハッシュ空間７０１において、インタフェースハッシュ値の衝突例を示す説明図である。ハッシュ値の最大値Ｎ’の選び方によっては、インタフェース間でハッシュ値が衝突する可能性がある。すなわち、インタフェース数をＭとすると、Ｎ’＜Ｍとなる場合は、全てのインタフェースハッシュ値を計算していくと、明らかにリング空間を周回してしまうため、二周目からはハッシュ値が衝突する。これにより、フローとインタフェースが１対１の対応関係でなくなるため、一貫した配信制御が提供できない。このような衝突を回避する幾つか方法も考えられるが、システム系としての複雑性が増加する。
【００５５】
ここでは、ハッシュ値が１つずつ増加する１６個のインタフェースが存在する場合を想定している。図のように、１〜８番目のインタフェース（一周目）と、９〜１６番目のインタフェース（二週目）のハッシュ値が衝突する（符号３３０１）。
このような衝突を回避するためには、Ｎ’≫Ｍとなるように、Ｎ’を選定すればよい。演算子「≫」は、左辺が右辺よりも充分に大きいことを示す。
【００５６】
図８は、ルータ管理テーブルの実施例を示す説明図である。
ルータ管理テーブル４３４は、自ルータインタフェースが接続されるイーサセグメント（マルチキャストＶＬＡＮ）単位に管理する。各テーブルのエントリは、ルータＩＦ番号、ルータＩＦのＩＰアドレス、ルータＩＦフラグ、クエリア死活監視タイマの組で生成管理される。
例では、自ＩＦのｒ１、正常に動作している（alive）他ＩＦのｒ２とｒ３、ＳＱ／ＧＱを受信しなくなった（Not received）他ＩＦのｒ４を示している。
なお、「Not received」とは、まだタイムアウトにはなっていないが、ＳＱ／ＧＱを未受信のエントリを示し、タイムアウト後にエントリ削除する（図５のＳ５０１）旨を示す。
【００５７】
図９は、フロー配信テーブルの初期生成シーケンスを示すフローチャートである。
ＩＧＭＰ／ＭＬＤルータ起動後に、フロー配信テーブル４３６を新規生成して初期化するステップ（Ｓ９００）から構成される。
なお、これらの処理ステップは、フロー割当処理部４３５によって実行される。
【００５８】
図１０は、フロー配信テーブルのエントリ追加／更新シーケンスを示すフローチャートである。
ホスト６からフロー（Ｓ、Ｇ）に対するＪｏｉｎレポートを受信するステップ（Ｓ１０００）、当該（Ｓ、Ｇ）に対する既存エントリがフロー配信テーブル４３６内に存在するかを検査するステップ（Ｓ１００１、Ｓ１００２）、存在する場合は自割当かつ配信中ならば配信を継続し（Ｓ１００４でＹｅｓ）、自割当かつ配信中でないならば配信を開始するステップ（Ｓ１００３、Ｓ１００４でＮｏ、Ｓ１００５）、存在しない場合には当該（Ｓ、Ｇ）アドレスからハッシュ値を計算してフロー配信テーブル４３６に登録するステップ（Ｓ１００６、Ｓ１００７）、同一のセグメント（マルチキャストＶＬＡＮなど）内の全ての仮想インタフェースのハッシュ値との方向距離を計算して配信割当インタフェースをフロー配信テーブル４３６に登録するステップ（Ｓ１００８、Ｓ１０１０、Ｓ１０１１）、自割当フローならば当該フローの配信を開始／継続するステップ（Ｓ１００９、Ｓ１０１２）、当該（Ｓ、Ｇ）フローの配信状態を配信中としてフロー配信テーブル４３６に登録するステップ（Ｓ１０１３）から構成される。
なお、これらの処理ステップは、フロー割当処理部４３５によって実行される。
ここで、フローが自IFの配信割当てかを判断するステップ（Ｓ１００９）は、以下の処理ステップを指す。
処理ステップ（1）フローに対して割当てられる仮想IFハッシュを求めるステップ。図１３〜図１５の説明で後記する。
処理ステップ（2）上記(1)で求まる仮想IFに対応づけられた実IFを求めるステップ。図１７〜図２０の説明で後記する。
【００５９】
図１１は、フロー配信テーブルのエントリ削除シーケンスを示すフローチャートである。
ホスト６からフロー（Ｓ、Ｇ）に対するＬｅａｖｅレポートを受信するステップ（Ｓ１１００）と、当該（Ｓ、Ｇ）に対する既存エントリがフロー配信テーブル４３６内に存在するかを検索するステップ（Ｓ１１０１、Ｓ１１０２）、存在する場合は同一セグメント（マルチキャストＶＬＡＮ）内に他の受信ホスト６が存在するかを確認して存在しなければエントリを削除するステップ（Ｓ１１０３、Ｓ１１０４）から構成される。
なお、これらの処理ステップは、フロー割当処理部４３５によって実行される。
ここで、同一セグメント内に他の受信ホスト６が存在するか否かの判定方法（Ｓ１１０３）は、例えば、ＭＬＤｖ２の場合には、ルータＩＦからＭＡＳＳＱ（Multicast Address and Source Specific Query）を送信し、ホスト６からのｊｏｉｎ／ｌｅａｖｅレポートを受信して記憶することで、判定できる。
【００６０】
図１２は、フロー配信テーブルの終了削除シーケンスを示すフローチャートである。
フロー配信テーブル４３６を削除するステップ（Ｓ１２００）から構成される。
なお、これらの処理ステップは、フロー割当処理部４３５によって実行される。
【００６１】
図１３〜図１５は、フローに対するハッシュ計算方法と仮想IFへの割当ての実施例を示す。
図１３は、１つのフロー（Ｓ１，Ｇ１）に対する例を示している。まず、リング型のハッシュ空間７０１を定義する。ここで、ハッシュ値の上限を決める定数ｎを定めておく。Ｎ’は、ハッシュ空間７０１の大きさであり、ハッシュ値の最大値（定数ｎ）＋１である。
【００６２】
そして、符号１３０１に、ハッシュ値の計算式を示す。フローの（Ｓ、Ｇ）アドレス情報を定数ｎで剰余算（ｍｏｄ）した結果をインタフェースハッシュ値とする。ｎ＝１０００と設定した場合はハッシュ値が５０５となる。
なお、必ずしも剰余算である必要はなく、一般的に用いられるその他のハッシュ関数を用いても良い。また、ネットワーク管理者が手動で値を設定しても良い。ただし、同一イーサセグメント（マルチキャスト用ＶＬＡＮ）内で配信制御の一貫性を保つため、接続される全てのルータインタフェースが共通の方法でハッシュ値を計算／設定する必要がある。
【００６３】
図１４は、図１３の（Ｓ１，Ｇ１）に対して、更に４つのフロー（符号１４０１）を追加した場合の例を示している。符号１４０２に示すように、ルータＩＦハッシュ値は１２５、２５０、３７５、５００、６２５、７５０、８７５、１０００となる。符号１４０３に示すように、フローハッシュ値は５０５、６０１、６９７、８８９、１７７となる。これらの両ハッシュ値を、リング型のハッシュ空間７０１にそれぞれ分散配置する（符号１４０４）。
【００６４】
図１５は、図１４で示した仮想ＩＦハッシュ値とフローハッシュ値との方向距離（ハッシュ距離１５０１）を算出する例を示している。ここでは、方向としてハッシュ空間７０１内の右時計回りとしており、各フローについて右方向に進んで最も近いインタフェースへ配信割当を行うルールとしている。この場合、フローｆ１とｆ４はインタフェースｒ３、ｆ２とｆ３はｒ２、ｆ５はｒ１がそれぞれ配信する（符号１５０２）。
なお、符号１５０２で示すハッシュ空間７０１には、仮想ＩＦハッシュ値は記載されているが、ハードウェア構成としての配信ルータ４のインタフェースｒ３に関する情報は、記載されていない。そこで、配信ルータ４は、後記する図１７、図１８の対応付け処理により、仮想ＩＦハッシュ値とインタフェースとの対応付けを行うことにより、各フローと各インタフェースとを配信担当として特定する。
【００６５】
図１６は、フロー配信テーブルの実施例を示す説明図である。
フロー配信テーブル４３６は、自ルータインタフェースが接続されるイーサセグメント（マルチキャストＶＬＡＮ）単位に管理する。テーブルエントリは、フロー番号、フローＳアドレス、フローＧアドレス、フローハッシュ値、配信仮想ＩＦ、配信実ＩＦ、配信状態の組で生成管理される。
例では、自ＩＦのｒ１、正常に動作している（配信状態＝Ｊｏｉｎの）他ＩＦのｒ３とｒ４、ＳＱ／ＧＱを受信しなくなった（配信状態＝Ｌｅａｖｅの）他ＩＦのｒ２を示している。
【００６６】
図１７〜図２０は、フローハッシュ値と仮想ＩＦハッシュ値と実ＩＦハッシュ値との対応づけを示す。
【００６７】
図１７、図１８は、仮想インタフェース（仮想ＩＦハッシュ値で特定される仮想ノード）と、実インタフェース（実ＩＦハッシュ値で特定される実態ノード）との対応づけの一例を示す。
図１７、図１８の配信フローは、図１６のフロー配信テーブル４３６内の「フロー番号、フローＳアドレス、フローハッシュ値」に格納されているデータで示される。
図１７、図１８の仮想ノードは、図１６のフロー配信テーブル４３６内の「配信仮想ＩＦ」に格納されているデータで示される。
図１７、図１８の実態ノードは、図１６のフロー配信テーブル４３６内の「配信実ＩＦ」に格納されているデータで示される。
【００６８】
第１対応付けは、１つの配信フローを１つの仮想ノードへと対応付けることである。例えば、配信フロー「ｆ１」は、仮想ノード「ｖ１」に対応付けられる。この第１対応付けは、図１５の符号１５０２で説明した右回りの割り当て決定処理により実現される。ある配信フローにおける第１対応付けは、別の配信フローの構成変更（生成消滅）によっては変更されない、固定的な対応付けである。
【００６９】
第２対応付けは、０以上の仮想ノードから構成される仮想ノードグループを、１つの実態ノードへと対応付けることである。「仮想ノードグループ」とは、前記したように、１つの実態ノードに割り当てられる仮想ノードの集合である。例えば、図１７の３つの仮想ノード（ｖ２〜ｖ４）は、同じ実態ノード（ｒ２）に割り当てられるので、同じ仮想ノードグループに属する。
第２対応付けは、最適な負荷分散の特性が得られるよう、実態ノードの余剰配信リソース（接続パスの帯域、ノードのパケット処理性能など）を考慮した重み付け演算を行うことが、望ましい。そして、ネットワークリソースの利用効率の向上という観点からは、第２対応付けは、配信フローの構成変更（生成消滅）によるフロー分布状態の変化に追従し、ダイナミックに変更（再計算）してもよい。
【００７０】
図１９は、仮想インタフェースと実インタフェースの対応づけ（図１７、図１８の第２対応付け）を行う初期生成シーケンスを示す。この図１９の処理は、配信ルータ４が初期起動したときや、配信ルータ４の台数が変化（増減設）したときを契機として、実行される。
仮想インタフェースの登録情報（インタフェース数Ｍ’）を読み出すステップ（Ｓ１８００）と、実インタフェースの登録情報（インタフェース数Ｍ）を読出すステップ（Ｓ１８０１）と、実インタフェース毎の余剰配信リソース（接続パス帯域や、パケット転送容量）に応じた重み付けを加味した、実インタフェースへの仮想インタフェース群の配分比率を計算するステップ（Ｓ１８０２）と、Ｓ１８０２の計算結果をもとに、実インタフェースに対して仮想インタフェース群の配分割当を行うステップ（Ｓ１８０３）から構成される。
なお、これらの処理ステップは、フロー割当処理部４３５によって実行される。
【００７１】
配分比率を計算するステップ（Ｓ１８０２）は、例えば、以下のいずれかの計算方法により実現される。
（計算方法１）Ｍ’／Ｍ個ずつ均等配分する。例えば、ラウンドロビン形式で、実態ノードと仮想ノードを対応づける。図１８の場合、r1には仮想グループ｛v1,v5｝、r2には仮想グループ｛v2,v6｝、r3には仮想グループ｛v3,v7｝、r4には仮想グループ｛v4,v8｝というように、実態ノード数を４つずつ均等にスキップしながら割当てていけば、仮想ノードに割当てられた配信フロー数が均等であれば、実態ノードに割当てられる配信フロー数も均一化できる。
つまり、静的（固定的）にラウンドロビン方式で実態ノードと仮想ノードを対応づけることにより、配信断を生じずに、コンシステントハッシュ方式のように負荷分散性能を向上でき、サービス品質という観点で優れている。
【００７２】
（計算方法２）実IFの余剰資源（パス帯域、パケット処理性能等）に応じて重み付け（比例）配分する。前記した（計算方法１）の実インタフェースのハードウェア個数Ｍの代わりに、実インタフェースの余剰資源数を用いて、例えば、以下の式を実行すればよい。
（自身のIFの配分比率）＝Ｍ’×（自身のIFの余剰資源）／（全ての実IFの余剰資源の総和）
このように、ルータＩＦの余剰リソースに応じた重み付けラウンドロビン方式で、実態ノードと仮想ノードを対応づけることにより、各実ＩＦの余剰資源がばらついている環境下でも、各実ＩＦ間でフロー配信の負荷分散が実現される。
なお、重み付けラウンドロビンでは、例えば、r1の余剰資源を「rest_r1」と表現し、余剰資源比率「rest_r1：rest_r2：rest_r3：rest_r4＝４：３：１：０」の場合には、r1には仮想グループ｛v1,v2,v3,v4｝、r2には仮想グループ｛v5,v6,v7｝、r3には仮想グループ｛v8｝、r4には仮想グループ｛なし｝が割り当てられる。
【００７３】
図２０は、仮想インタフェースと実インタフェースの対応づけ（図１７、図１８の第２対応付け）を変更するシーケンスを示す。この図２０のシーケンスの起動契機は、例えば、周期時間タイマのタイムアウト時や、管理者によるオペレーション実行時などが挙げられる。
仮想インタフェース単位の配信フロー数ｋ’_ｖｉ（ｉ=１、２、…、Ｍ’）を計算するステップ（Ｓ１９００）と、現在の実インタフェースと仮想インタフェース群の配分割当から、実インタフェース毎の配信フロー数ｋ_ｒｊ（ｊ=１、２、…、Ｍ）を計算するステップ（Ｓ１９０１）と、実インタフェース毎の配信フロー数が、実インタフェース毎の余剰配信リソースを考慮して均等になるように、仮想インタフェース群の配分比率を再計算するステップ（Ｓ１９０２）と、これに応じ、実インタフェースに対する仮想インタフェース群の配分割当の変更を行うステップ（Ｓ１９０３）から構成される。
なお、これらの処理ステップは、フロー割当処理部４３５により実行される。
【００７４】
配分割当の変更処理（Ｓ１９０３）は、例えば、「仮想ノードしきい」をシフトする「しきいシフト演算」により実現される。「仮想ノードしきい」とは、隣接する２つの「仮想ノードグループ」を区切るしきいである。例えば、図１７では、以下の３つの仮想ノードしきい（記号「｜」）が存在する。
仮想グループ「ｖ１」｜仮想グループ「ｖ２〜ｖ４」｜仮想グループ「ｖ５，ｖ６」｜仮想グループ「ｖ７，ｖ８」
「しきいシフト演算」により、例えば、以下のように、仮想ノードしきいの位置が変更される。
仮想グループ「ｖ１，ｖ２」｜仮想グループ「ｖ３〜ｖ５」｜仮想グループ「ｖ６」｜仮想グループ「ｖ７，ｖ８」
【００７５】
以下、しきいシフト演算の詳細を説明する。
まず、仮想ノードiに対応づけられるフロー数M(i)（ここで、i=1,2,…,8）を管理します。次に、仮想ノードiと実態ノードjとの第２対応づけを管理するために、４つの仮想ノードグループと、３つの仮想ノードしきいを設定する。
仮想グループ１「ｖ１」｜仮想グループ２「ｖ２〜ｖ４」｜仮想グループ３「ｖ５，ｖ６」｜仮想グループ４「ｖ７，ｖ８」
【００７６】
各仮想グループjに含まれる仮想ノード数H(j)を導く。
H(1)=1  ({v1})
H(2)=3  ({v2,v3,v4})
H(3)=2  ({v5,v6})
H(4)=2  ({v7,v8})
【００７７】
M(i)から、各グループjに含まれる配信フロー数O(j)を計算する。
O(1)=M(1)=0
O(2)=M(2)+M(3)+M(4)=1+1+0=2
O(3)=M(5)+M(6)=2+1=3
O(4)=M(7)+M(8)=0+1=1
【００７８】
各グループに対して、仮想ノード単位の配信フロー数の平均O(j)/H(j)を計算する。
O(1)=M(1)=0
O(2)/H(2)=2/3=0.666666…
O(3)/H(3)=3/2=1.5
O(4)/H(4)=1/1=1
【００７９】
ここで、各仮想ノードしきいの変動幅Δ(k)を定義する。例えば、Δ(１)＝２とは、仮想グループ１「ｖ１」と、仮想グループ２「ｖ２〜ｖ４」とを区切る第１の仮想ノードしきいを右方向（正方向）に２つ分シフトすることを意味するので、「Δ(１)＝２」を適用後は、仮想グループ１「ｖ１〜ｖ３」と、仮想グループ２「ｖ４」との間に第１の仮想ノードしきいがシフトする。
【００８０】
前記の例では、３つの仮想ノードしきいがあるので、Δ(1)、Δ(2)、Δ(3)を定義する。しきいシフト後のグループjに含まれるフロー数をO’(j)を定義し、以下の境界条件（連立方程式）で、Δ(k)を算出する。
O’(1)/{H(1)+Δ(1)}
= O’(2)/{H(2)-Δ(1)+Δ(2)}
= O’(3)/{H(3)-Δ(2)+Δ(3)}
= O’(4)/{H(4)-Δ(3)}
【００８１】
その結果、連立方程式を解いて、仮にΔ(1)=1、Δ(2)=1、Δ(3)=0になったとすると、仮想ノードしきいが右方向（正方向）にシフトする。
H(1)=2  ({v1,v2})         第１の仮想ノードしきいを右に1シフト
H(2)=3  ({v3,v4,v5})    上記  ∧  第２の仮想ノードしきいを右に1シフト
H(3)=1  ({v6})          上記  ∧  第３の仮想ノードしきいは、シフトせず
H(4)=2  ({v7,v8})      上記第１〜第３の仮想ノードしきいは影響せず
すなわち、仮想ノードしきいの基本位置は、v2とv3の間、v5とv6の間、v6とv7の間に変更される。
【００８２】
ここで、解析解の導出が複雑で計算時間がかかるなどの要因で、近似の方程式を解くが、その解精度を向上させたい場合や、視聴状態の変化に追従する場合には、動的に閾値の位置を反復制御（再計算／再シフト）してもよい。
なお、反復計算による制御の安定性を向上させるために、しきいの位置をシフトしても、現状態より際立って高い負荷分散の精度が得られない場合には、しきいの位置をシフトしない補助的な制御を組み合せてもよい。このように、仮想ノードしきいのシフト制御を過敏にし過ぎないことで、制御系の安定性を確保してもよい。
【００８３】
また、仮想ノードしきいの改善アルゴリズムにおいて、前記したような連立方程式を解く方法の他に、各グループ内の負荷の分散値を評価関数として、その評価関数が最適（ここでは分散＝０）となるように、仮想ノードしきいをランダムに変化させてその都度評価するような手法を用いてもよい。
【００８４】
以上説明した本実施形態は、ＩＰルータがＩＧＭＰ／ＭＬＤプロトコルを用いてＩＰマルチキャストの配信制御を行う際に、単一の共有セグメント（イーサネットのＶＬＡＮなど）に複数のルータインタフェースが冗長接続される配信システムを示した。
この配信システムにおいて、複数のインタフェース間で配信アクセスを分散するための制御内容によって、インタフェース群に設定するＩＰアドレスの分布特性に依存せず、高い負荷分散の性能を実現することができる。換言すると、この配信システムにおいて、コンシステントハッシュ方式による負荷分散を適用する際、インタフェース増設の都度、高い負荷分散の性能を実現することができる。よって、系全体としてのアクセス収容効率の向上と障害リスク分散が達成可能となる。
【００８５】
そのための制御内容とは、主に図１７〜図２０で示したように、ＩＦハッシュ値を２種類用意し（仮想ＩＦハッシュ値、実ＩＦハッシュ値）、２段階の対応付けを活用することである。
ハッシュ空間７０１上に配置したフローハッシュ値と、ルータＩＦハッシュ値との対応付けにおいて、フローハッシュ値と仮想ＩＦハッシュ値との第１の対応付けと、仮想ＩＦハッシュ値と実ＩＦハッシュ値との第２の対応付けとをそれぞれ活用し、フローハッシュ値→仮想ＩＦハッシュ値→実ＩＦハッシュ値とたどることにより、フロー（フローハッシュ値）の配信を担当するインタフェース（実ＩＦハッシュ値）を決定する。
【００８６】
図１７、図１８の第１対応付けにおいて、ハッシュリング上に仮想ノードを均等間隔で配備し、仮想ノード群とフロー群の対応づけにコンシステントハッシュ方式を適用する。
図１７、図１８の第２対応付けにおいて、最適な負荷分散の特性が得られるよう、実態ノードの余剰配信リソース（接続パスの帯域、ノードのパケット処理性能など）を考慮した重み付けをした仮想ノード（仮想ＩＦハッシュ値）と実態ノード（実ＩＦハッシュ値）間の対応づけを行う。
さらに、フローの生成消滅によるフロー分布状態の変化に追従し、第１および第２の対応付けを再計算することで、対応関係をダイナミックに変更する。
【００８７】
また、リング状のハッシュ空間７０１を用いることで、インタフェースの増減設／障害切替／回復切戻において、収容変更の対象フロー群を限定することにより、増減設に伴う配信断や重複配信によるサービス影響範囲を最小化することが可能となる。よって、配信品質および信頼性を維持しつつトラヒック需要の変動に柔軟に対応可能なＩＰマルチキャスト配信サービスが実現可能となる。
【符号の説明】
【００８８】
１      配信サーバ
２      マルチキャスト配信網
３      リンク
４      配信ルータ
５      共有セグメント
６      ホスト
４１    ＭＣ配信網接続インタフェース
４２    ＭＣ配信網フレーム転送部
４３    転送制御回路
４４    共有セグメントフレーム転送部
４５    共有セグメント接続インタフェース
４１１  受信ＩＦ部
４１２  送信ＩＦ部
４２１  フレーム受信部
４２２  フレーム送信部
４３１  配信状態管理部
４３２  ＭＣ配信網連携部
４３３  ルータ状態管理部
４３４  ルータ管理テーブル
４３５  フロー割当処理部
４３６  フロー配信テーブル
４３７  配信フィルタ部
４４１  フレーム送信部
４４２  フレーム受信部
４５１  送信ＩＦ部
４５２  受信ＩＦ部
７０１  ハッシュ空間
【図３】
2014036274.tif 000003
【図４】
2014036274.tif 000004
【図５】
2014036274.tif 000005
【図６】
2014036274.tif 000006
【図９】
2014036274.tif 000007
【図１１】
2014036274.tif 000008
【図１２】
2014036274.tif 000009
【図１９】
2014036274.tif 000010
【図２０】
2014036274.tif 000011
【図１】
2014036274.tif 000012
【図２】
2014036274.tif 000013
【図７】
2014036274.tif 000014
【図８】
2014036274.tif 000015
【図１０】
2014036274.tif 000016
【図１３】
2014036274.tif 000017
【図１４】
2014036274.tif 000018
【図１５】
2014036274.tif 000019
【図１６】
2014036274.tif 000020
【図１７】
2014036274.tif 000021
【図１８】
2014036274.tif 000022
【図２１】
2014036274.tif 000023
【図２２】
2014036274.tif 000024
【図２３】
2014036274.tif 000025
【図２４】
2014036274.tif 000026
【図２５】
2014036274.tif 000027
【図２６】
2014036274.tif 000028
【図２７】
2014036274.tif 000029
【図２８】
2014036274.tif 000030
【図２９】
2014036274.tif 000031
【図３０】
2014036274.tif 000032
【図３１】
2014036274.tif 000033