(57)【特許請求の範囲】
【請求項１】
ホストにマルチキャストのフローを配信する複数台の配信ルータと１台以上の前記ホストとが共有セグメントに接続され、その共有セグメントに送信されるパケットは、前記共有セグメントに接続される前記配信ルータおよび前記ホストがそれぞれ受信可能であるマルチキャスト配信システムに用いられる前記配信ルータであって、
前記共有セグメントに接続される前記配信ルータのインタフェースごとに、そのインタフェースの識別情報を引数として所定のハッシュ空間へと射影する第１ハッシュ関数を計算することで、ＩＦハッシュ値を計算するＩＦ状態管理部と、
前記共有セグメントを介して前記配信ルータによる配信されるフローごとに、そのフローの識別情報を引数として前記所定のハッシュ空間へと射影する第２ハッシュ関数を計算することで、フローハッシュ値を計算し、
計算した各前記ＩＦハッシュ値によって区切られるハッシュ空間内の所定領域を、所定の前記ＩＦハッシュ値の担当領域とし、その担当領域に含まれる前記フローハッシュ値に該当するフローを、所定の前記ＩＦハッシュ値に該当する前記配信ルータのインタフェースが配信を担当するように制御し、
前記所定のハッシュ空間に対して新たに前記ＩＦハッシュ値を追加するときには、追加する前記ＩＦハッシュ値の担当領域を、前記ＩＦハッシュ値の担当領域の１つを分割した領域とし、
前記所定のハッシュ空間から前記ＩＦハッシュ値を削除するときには、削除する前記ＩＦハッシュ値の担当領域を、他の１つの前記ＩＦハッシュ値の担当領域へ統合するフロー割当処理部とを有することを特徴とする
配信ルータ。
【請求項２】
前記ＩＦ状態管理部は、前記共有セグメントに流れる前記配信ルータからのマルチキャストのクエリメッセージを受信し、そのクエリメッセージに含まれる送信元ＩＰアドレスを前記ＩＦハッシュ値を計算するための前記インタフェースの識別情報として用いることを特徴とする
請求項１に記載の配信ルータ。
【請求項３】
前記フロー割当処理部は、前記共有セグメントに流れる前記ホストからのマルチキャストのレポートメッセージを受信し、そのレポートメッセージに含まれる配信フローの送信元ＩＰアドレス、および、配信フローの宛先ＩＰアドレスのうちの少なくとも１つのＩＰアドレスを、前記フローハッシュ値を計算するための前記フローの識別情報として用いることを特徴とする
請求項１に記載の配信ルータ。
【請求項４】
前記フロー割当処理部は、
前記計算したＩＦハッシュ値が互いに同じ値となる前記配信ルータのインタフェース群について、前記インタフェース群のうちの１つのインタフェースには、前記同じ値として計算したＩＦハッシュ値を対応づけて前記所定のハッシュ空間に割り当て、
前記インタフェース群のうちの他のインタフェースには、前記同じ値として計算したＩＦハッシュ値を起点として所定分だけ移動したＩＦハッシュ値を対応づけて前記所定のハッシュ空間に割り当て、
前記所定のハッシュ空間から前記１つのインタフェースのＩＦハッシュ値が削除されるときには、前記他のインタフェースに対応づけられていたＩＦハッシュ値を、前記所定のハッシュ空間において移動前のＩＦハッシュ値へと戻すことを特徴とする
請求項１ないし請求項３のいずれか１項に記載の配信ルータ。
【請求項５】
ホストにマルチキャストのフローを配信する複数台の配信ルータと１台以上の前記ホストとが共有セグメントに接続され、その共有セグメントに送信されるパケットは、前記共有セグメントに接続される前記配信ルータおよび前記ホストがそれぞれ受信可能であるマルチキャスト配信システムであって、
前記マルチキャスト配信システムに用いられる前記各配信ルータは、
前記共有セグメントに接続される前記配信ルータのインタフェースごとに、そのインタフェースの識別情報を引数として所定のハッシュ空間へと射影する第１ハッシュ関数を計算することで、ＩＦハッシュ値を計算するＩＦ状態管理部と、
前記共有セグメントを介して前記配信ルータによる配信されるフローごとに、そのフローの識別情報を引数として前記所定のハッシュ空間へと射影する第２ハッシュ関数を計算することで、フローハッシュ値を計算し、
計算した各前記ＩＦハッシュ値によって区切られるハッシュ空間内の所定領域を、所定の前記ＩＦハッシュ値の担当領域とし、その担当領域に含まれる前記フローハッシュ値に該当するフローを、所定の前記ＩＦハッシュ値に該当する前記配信ルータのインタフェースが配信を担当するように制御し、
前記所定のハッシュ空間に対して新たに前記ＩＦハッシュ値を追加するときには、追加する前記ＩＦハッシュ値の担当領域を、前記ＩＦハッシュ値の担当領域の１つを分割した領域とし、
前記所定のハッシュ空間から前記ＩＦハッシュ値を削除するときには、削除する前記ＩＦハッシュ値の担当領域を、他の１つの前記ＩＦハッシュ値の担当領域へ統合するフロー割当処理部とを有することを特徴とする
マルチキャスト配信システム。
【請求項６】
ホストにマルチキャストのフローを配信する複数台の配信ルータと１台以上の前記ホストとが共有セグメントに接続され、その共有セグメントに送信されるパケットは、前記共有セグメントに接続される前記配信ルータおよび前記ホストがそれぞれ受信可能であるマルチキャスト配信システムが実行するマルチキャスト配信方法であって、
前記マルチキャスト配信システムに用いられる前記各配信ルータは、ＩＦ状態管理部と、フロー割当処理部とを有しており、
前記ＩＦ状態管理部は、前記共有セグメントに接続される前記配信ルータのインタフェースごとに、そのインタフェースの識別情報を引数として所定のハッシュ空間へと射影する第１ハッシュ関数を計算することで、ＩＦハッシュ値を計算し、
前記フロー割当処理部は、
前記共有セグメントを介して前記配信ルータによる配信されるフローごとに、そのフローの識別情報を引数として前記所定のハッシュ空間へと射影する第２ハッシュ関数を計算することで、フローハッシュ値を計算し、
計算した各前記ＩＦハッシュ値によって区切られるハッシュ空間内の所定領域を、所定の前記ＩＦハッシュ値の担当領域とし、その担当領域に含まれる前記フローハッシュ値に該当するフローを、所定の前記ＩＦハッシュ値に該当する前記配信ルータのインタフェースが配信を担当するように制御し、
前記所定のハッシュ空間に対して新たに前記ＩＦハッシュ値を追加するときには、追加する前記ＩＦハッシュ値の担当領域を、前記ＩＦハッシュ値の担当領域の１つを分割した領域とし、
前記所定のハッシュ空間から前記ＩＦハッシュ値を削除するときには、削除する前記ＩＦハッシュ値の担当領域を、他の１つの前記ＩＦハッシュ値の担当領域へ統合することを特徴とする
マルチキャスト配信方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、配信ルータ、マルチキャスト配信システム、および、マルチキャスト配信方法に関する。
【背景技術】
【０００２】
ＩＰ（Internet Protocol）ルータとＩＰホスト区間のＩＰマルチキャストの配信制御を行うプロトコルとして、ＩＧＭＰ（Internet Group Management Protocol）／ＭＬＤ（Multicast Listener Discovery）が存在する。また、その中でも、配信フローの送信元ＩＰアドレス（以下、Ｓアドレス：Sourceアドレス）と、宛先ＩＰアドレス（以下、Ｇアドレス：Groupアドレス）との両方（以下、（Ｓ，Ｇ））をフローＩＤとして指定して制御を行うＳＳＭ（Source-Specific Multicast）方式に対応したプロトコルとして、非特許文献１に記載のＩＧＭＰｖ３（ＩＰｖ４）や、非特許文献２に記載のＭＬＤｖ２（ＩＰｖ６）が存在する。
ＩＧＭＰｖ３／ＭＬＤｖ２では、ルータは、ホストからレポートを受信したことを契機に、当該フローの配信を開始／停止する。なお、レポートには、フローの（Ｓ，Ｇ）アドレスと、配信状態（配信中を示すＪｏｉｎ／未配信を示すＬｅａｖｅ）とが含まれている。
【０００３】
ＩＰルータがＩＧＭＰ／ＭＬＤを用いてＩＰマルチキャストの配信制御を行うときに、複数のＩＰルータのインタフェース（以下、ＩＦ（Interface）と略す）を、単一の共有セグメントに冗長接続する構成もある。以下、同じ共有セグメントに接続される複数のルータのＩＦをＩＦ集合とする。なお、共有セグメントは、例えば、イーサネット（登録商標）のＶＬＡＮ（Virtual Local Area Network）などで構成される。
【０００４】
ここで、共有セグメントに複数のルータが接続される場合、全てのルータがレポートを受信して配信を開始すると、同一フローが重複配信される状況に陥る。この場合、セグメントの帯域利用効率が低下するため、同時配信可能な最大フロー数が減少したりや、同一パケットを重複受信するホストに悪影響を及ぼしたりする可能性がある。
【０００５】
そこで、ＩＧＭＰｖ３／ＭＬＤｖ２には、クエリアの選択メカニズムが備わっている。すなわち、ＩＦ集合の中の１つのＩＦ（以下、クエリア）のみ配信制御を行う。一方、非クエリアは、共有セグメントへのフローの配信を停止する。そして、クエリアの選択メカニズムでは、ＩＦ集合におけるクエリアと非クエリアとの交代処理は、以下の契機に実行される。
（契機１）クエリアは、他ルータからクエリ（ＧＱ（General Query）またはＳＱ（Group-Specific Query））を受信すると、その送信元ＩＰアドレスと自ＩＦのＩＰアドレスとを大小比較し、送信元アドレスの方が小さい場合は、自身を非クエリアへと降格させる。
（契機２）非クエリアは、クエリアからタイマ上限値（ＯＱＰＴ（Other Querier Present Interval）とも呼ばれる）を超過するまでにＧＱを受信しないとき、クエリアに障害が発生したとみなして、クエリアを代行するために自身をクエリアへと昇格させる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】ＩＥＴＦ、“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）
【発明の概要】
【発明が解決しようとする課題】
【０００７】
前記した従来のクエリアの選択メカニズムは、（契機１）および（契機２）という単純な処理により、クエリアと非クエリアとの交代処理を実現しているので、実装はしやすいものの、ＩＦ集合の構成変更に伴って、フローの配信処理が不安定になる。
不安定とは、具体的には、ＩＦ集合のうちのクエリアが０台となってしまい、フローがホストに配信されない「配信断」や、ＩＦ集合のうちのクエリアが２台以上となってしまい、同じフローがホストに対して別々に配信されてしまう「重複配信」である。
つまり、クエリアの選択メカニズムは、精密に時刻同期／順序同期して実行されるわけではなく、他ＩＦから送信されるクエリおよびホストから送信されるレポートの受信を契機にそれぞれ独立したタイミングで実行されるため、クエリアと非クエリアとの交代処理を実行する過程において、フローの配信処理が不安定になる。
【０００８】
以下、ＩＦ集合の構成変更の例を（変更１）〜（変更４）として、それぞれ説明する。
（変更１）新しいＩＦをＩＦ集合に増設する場合、増設先のＩＦ集合にクエリアがすでに存在しているにもかかわらず、増設したＩＦはクエリアとして一旦起動する。よって、すでに存在しているクエリアと、増設したＩＦのクエリアとが同じＩＦ集合に重複して存在するため、増設したＩＦとすでに存在しているクエリアとで、新たなクエリアを１つ選出する（契機１）が実行されるまでの期間において、重複配信が発生してしまう。
【０００９】
（変更２）所定のＩＦをＩＦ集合から減設する場合、その減設対象がクエリアであるときには、クエリアが減設されたときから、非クエリア間で新たなクエリアを選出するまでの期間において、クエリアが０台となってしまい、配信断が発生してしまう。
【００１０】
（変更３）クエリアに障害が発生する場合、その障害発生クエリアを非クエリアが検出するには、クエリアからＧＱパケットを受信しない時間が標準規定上で定められたタイマ上限値（例えば、２５６秒程度）を超過するまで、ＧＱパケットを待たなければならない。よって、非クエリアが障害発生クエリアを代行するまでの期間において、クエリアが０台となってしまい、配信断が発生してしまう。
なお、タイマ上限値を短くすると、その分のＧＱパケットの送信頻度が上がってしまうため、ＩＦ集合のクエリアや他ＩＦの負荷が上昇してしまう副作用が発生する。
【００１１】
（変更４）クエリアが（変更３）の障害から復旧した場合、復旧したクエリアと、（変更３）でクエリアを代行していたクエリアは、それぞれフローを配信するので、クエリアを１つに集約するまでは、重複配信が発生してしまう。
【００１２】
そこで、本発明は、共有セグメントに複数のマルチキャスト配信ルータのインタフェースが接続される構成において、それらのインタフェース集合に構成変更が発生してもフローの配信処理が不安定となる範囲を限定することを、主な目的とする。
【課題を解決するための手段】
【００１３】
前記課題を解決するために、本発明は、ホストにマルチキャストのフローを配信する複数台の配信ルータと１台以上の前記ホストとが共有セグメントに接続され、その共有セグメントに送信されるパケットが、前記共有セグメントに接続される前記配信ルータおよび前記ホストがそれぞれ受信可能であるマルチキャスト配信システムに用いられる前記配信ルータであって、
前記共有セグメントに接続される前記配信ルータのインタフェースごとに、そのインタフェースの識別情報を引数として所定のハッシュ空間へと射影する第１ハッシュ関数を計算することで、ＩＦハッシュ値を計算するＩＦ状態管理部と、
前記共有セグメントを介して前記配信ルータによる配信されるフローごとに、そのフローの識別情報を引数として前記所定のハッシュ空間へと射影する第２ハッシュ関数を計算することで、フローハッシュ値を計算し、
計算した各前記ＩＦハッシュ値によって区切られるハッシュ空間内の所定領域を、所定の前記ＩＦハッシュ値の担当領域とし、その担当領域に含まれる前記フローハッシュ値に該当するフローを、所定の前記ＩＦハッシュ値に該当する前記配信ルータのインタフェースが配信を担当するように制御し、
前記所定のハッシュ空間に対して新たに前記ＩＦハッシュ値を追加するときには、追加する前記ＩＦハッシュ値の担当領域を、前記ＩＦハッシュ値の担当領域の１つを分割した領域とし、
前記所定のハッシュ空間から前記ＩＦハッシュ値を削除するときには、削除する前記ＩＦハッシュ値の担当領域を、他の１つの前記ＩＦハッシュ値の担当領域へ統合するフロー割当処理部とを有することを特徴とする。
【００１４】
これにより、構成変更が発生したＩＦハッシュ値に近接するフローを収容変更するだけで済むので、フローの配信処理の不安定の影響を局所的にすることができる。よって、共有セグメントに複数のマルチキャスト配信ルータのインタフェースが接続される構成において、それらのインタフェース集合に構成変更が発生してもフローの配信処理が不安定となる範囲を限定することができる。
【００１５】
本発明は、前記ＩＦ状態管理部が、前記共有セグメントに流れる前記配信ルータからのマルチキャストのクエリメッセージを受信し、そのクエリメッセージに含まれる送信元ＩＰアドレスを前記ＩＦハッシュ値を計算するための前記インタフェースの識別情報として用いることを特徴とする。
【００１６】
これにより、既存のプロトコルのパケットフォーマット（クエリ）をそのまま活用できる。
【００１７】
本発明は、前記フロー割当処理部が、前記共有セグメントに流れる前記ホストからのマルチキャストのレポートメッセージを受信し、そのレポートメッセージに含まれる配信フローの送信元ＩＰアドレス、および、配信フローの宛先ＩＰアドレスのうちの少なくとも１つのＩＰアドレスを、前記フローハッシュ値を計算するための前記フローの識別情報として用いることを特徴とする。
【００１８】
これにより、既存のプロトコルのパケットフォーマット（レポート）をそのまま活用できる。
【発明の効果】
【００１９】
本発明によれば、共有セグメントに複数のマルチキャスト配信ルータのインタフェースが接続される構成において、それらのインタフェース集合に構成変更が発生してもフローの配信処理が不安定となる範囲を限定することができる。
【図面の簡単な説明】
【００２０】
【図１】本発明の一実施形態に関するマルチキャスト配信システムを示す構成図である。
【図２】本発明の一実施形態に関する配信ルータを示す構成図である。
【図３】本発明の一実施形態に関するリング状のハッシュ空間を示す説明図である。
【図４】本発明の一実施形態に関する配信処理およびその前準備処理を示すフローチャートである。
【図５】本発明の一実施形態に関するリング状のハッシュ空間に両ハッシュ値を配置した旨を示す説明図である。
【図６】本発明の一実施形態に関するＩＦ集合の構成変更処理を示すフローチャートである。
【図７】本発明の一実施形態に関するリング状のハッシュ空間においてＩＦ集合の構成変更例を示す説明図である。
【図８】本発明の一実施形態に関するフロー割当処理部の処理を示すフローチャートである。
【発明を実施するための形態】
【００２１】
以下、本発明の一実施形態について、図面を参照して詳細に説明する。
【００２２】
図１は、マルチキャスト配信システムを示す構成図である。
マルチキャストフローは、配信サーバ１（Ｓ１，Ｓ２，…）から送信され、マルチキャスト配信網２、リンク３、配信ルータ４（Ｒ１，Ｒ２，Ｒ３，…）、共有セグメント５を経由し、ホスト６（Ｈ１，Ｈ２，Ｈ３，Ｈ４，…）に配信される。共有セグメント５は、例えば、イーサネットのセグメント（マルチキャストＶＬＡＮ）として構成される。
これらのマルチキャスト配信システムの各装置は、ＣＰＵ（Central Processing Unit）とメモリとハードディスク（記憶手段）とネットワークインタフェースを有するコンピュータとして構成され、このコンピュータは、ＣＰＵが、メモリ上に読み込んだプログラムを実行することにより、各処理部を動作させる。
【００２３】
配信ルータ４とホスト６と間のパケットは、共有セグメント５を介して送受信される。この送受信されるパケットは、配信ルータ４から送信されるクエリと、ホスト６から送信されるレポート（配信中を示すＪｏｉｎ／未配信を示すＬｅａｖｅ）とがある。ＲＦＣ（Request for Comments）３８１０に記載されているように、レポートのＩＣＭＰｖ６ヘッダ内の「Record Type」を5（ALLOW_NEW_SOURCES）に設定すると指定した（Ｓ，Ｇ）に対するＪｏｉｎとなり、「Record Type」を6（BLOCK_OLD_SOURCES）に設定すると指定した（Ｓ，Ｇ）に対するＬｅａｖｅとなる。
【００２４】
図２は、配信ルータ４を示す構成図である。
配信ルータ４は、マルチキャスト配信網２と接続するＭＣ配信網接続インタフェース４１、マルチキャスト配信網２とフレーム送受信を行うＭＣ配信網フレーム転送部４２、共有セグメント５とフレーム送受信を行う共有セグメントフレーム転送部４４、共有セグメント５と接続する共有セグメント接続インタフェース４５、フローの配信を制御する転送制御回路４３から構成される。
【００２５】
ＭＣ配信網接続インタフェース４１と共有セグメント接続インタフェース４５は、一般的な物理レイヤを司り、イーサネットの場合はＰＨＹレイヤに相当する。
ＭＣ配信網接続インタフェース４１は、受信ＩＦ部４１１と送信ＩＦ部４１２とから構成される。
共有セグメント接続インタフェース４５は、送信ＩＦ部４５１と受信ＩＦ部４５２とから構成される。
【００２６】
ＭＣ配信網フレーム転送部４２と共有セグメントフレーム転送部４４は、一般的なデータリンク層を司り、イーサネットの場合はＭＡＣ（Media Access Control）レイヤに相当する。
ＭＣ配信網フレーム転送部４２は、フレーム受信部４２１とフレーム送信部４２２とから構成される。共有セグメントフレーム転送部４４は、フレーム送信部４４１とフレーム受信部４４２とから構成される。
【００２７】
転送制御回路４３は、配信状態管理部４３１、ＭＣ配信網連携部４３２、ＩＦ状態管理部４３３、ＩＦ管理テーブル４３４、フロー割当処理部４３５、フロー配信テーブル４３６、配信フィルタ部４３７から構成される。
レポートは、ホスト６から受信すると、共有セグメント接続インタフェース４５、共有セグメントフレーム転送部４４、配信状態管理部４３１を介して、フロー割当処理部４３５に通知される。
配信状態管理部４３１は、従来のＩＧＭＰ／ＭＬＤルータなどに相当し、ＩＰマルチキャストフローのアクセス配信状態の管理を行う。ここで、配信状態管理部４３１は、ホスト６から受信したレポートの内容と現在のフロー配信状態に応じて、ＭＣ配信網連携部４３２を介して、配信に関する連携処理を行う。
ＭＣ配信網連携部４３２は、従来のＰＩＭルータなどに相当する。マルチキャスト配信網２と連携してＩＰマルチキャストルーティングの制御を行う。
配信フィルタ部４３７は、フロー割当処理部４３５からの指示を受けて、フロー単位の配信フィルタを開閉する。フィルタが開放されたフローは、ＭＣ配信網フレーム転送部４２から受信したフローパケットを共有セグメントフレーム転送部４４へ転送する。逆に、フィルタ閉鎖されたフローは転送せずに廃棄する。
【００２８】
ＩＦ状態管理部４３３は、共有セグメントに接続される全てのＩＦの情報を管理する。共有セグメント接続インタフェース４５、共有セグメントフレーム転送部４４、配信状態管理部４３１を介して受信する他ＩＦからのクエリの送信元ＩＰアドレスや受信時刻を検査し、ＩＦの識別情報からＩＦハッシュ値を計算し（詳細は、後記する表１で説明）、他ＩＦを死活監視する。
ＩＦ管理テーブル４３４は、ＩＦ状態管理部４３３において検査されたＩＦ情報が登録および管理されるデータベースである。
ＩＦ状態管理部４３３は、フロー割当処理部４３５の指示に従い、ＩＦ管理テーブル４３４に登録したインタフェース情報を読み出して、フロー割当処理部４３５に引き渡す。
【００２９】
フロー割当処理部４３５は、フローに対するＩＦの割当情報をフロー配信テーブル４３６に管理する。フロー割当処理部４３５は、レポートから読み取ったフローの識別情報をもとに、フローハッシュ値を計算する（詳細は、後記する表２で説明）。フロー割当処理部４３５は、ＩＦ状態管理部４３３から全てのＩＦハッシュ値を取得し、当該フローハッシュ値と全てのＩＦハッシュ値の方向距離を計算して当該フローに対する配信ＩＦの割当てを決定して配信状態の制御を行う。ここで、これらの処理情報をフロー配信テーブル４３６に登録する。
フロー配信テーブル４３６は、フロー割当処理部４３５において処理されたフローごとのインタフェースに対する割当情報および配信状態が登録および管理されるデータベースである。
【００３０】
図３は、両テーブル（ＩＦ管理テーブル４３４、フロー配信テーブル４３６）が使用するリング状のハッシュ空間を示す説明図である。
図３（ａ）は、ハッシュ空間の大きさであるハッシュ値の上限を決める定数ｎとしたときのハッシュ空間を示す。定数ｎとはハッシュ値の最大値＋１である。ハッシュ空間は、右回り（時計回り）にハッシュ値が大きくなるように構成され、１２時の方向（真上）がハッシュ値「０」とハッシュ値「ｎ」、６時の方向（真下）がハッシュ値「ｎ／２」を示す。
図３（ｂ）は、図３（ａ）のハッシュ空間として、ｎ＝１０００としたときの一例を示す。
【００３１】
【表１】
0005613142.tif 000002
【００３２】
表１は、共有セグメント５ごとに生成されるＩＦ管理テーブル４３４を示す。ＩＦ管理テーブル４３４は、ＩＦの識別情報であるＩＦＩＤと、ＩＦのＩＰアドレスと、そのＩＦのＩＦハッシュ値（Hash）と、そのＩＦが自身のものか否かを示すＩＦフラグと、ＩＦが活動しているか否かを監視するためのクエリア死活監視タイマとを対応づけて格納する。
例えば、ＩＦＩＤ「R1」は、自身が収容するＩＦである。
ＩＦＩＤ「R2,R3」は、他装置が収容するＩＦであり、クエリを受信してから経過した時間（クエリア死活監視タイマの時間）が所定時間以下なので、活動している。
ＩＦＩＤ「R4」は、他装置が収容するＩＦであり、クエリを受信してから経過した時間が所定時間を超えたため（タイムアウトしたため）、活動していない。
【００３３】
ＩＦ管理テーブル４３４のＩＦハッシュ値は、ＩＦのＩＰアドレスを定数ｎで剰余算（ｍｏｄ）した結果である。なお、各ＩＦのＩＰアドレスは、クエリのＩＰｖ６ヘッダに記載されている送信元ＩＰアドレス（ＩＰｖ６のリンクローカルアドレス）を読み取れば取得できる。
なお、以下では、ハッシュ関数の引数として、ＩＦのＩＰアドレスを用いたが、他のＩＦの識別情報（送信元ＩＰアドレスの一部や、所定ルールで設定したＩＦのＩＤや、共有セグメント５におけるＩＦのクエリア順位（共有セグメント５の中で何番目に小さいＩＰアドレスか）など）を代わりに引数として用いてもよい。
【００３４】
以下、ハッシュ空間の大きさを「n」とし、ハッシュ引数であるＩＦのＩＰアドレスを「IP」とし、ハッシュ関数を「H()」とし、ハッシュ引数の変換関数を「f()」とし、１６進数表現を「()h」と表記する。
H(IP,n)= mod[f(IP),n]
例えば、n=1000、IP=R1の「fe80::1122::3344::5566::789a」の場合
H(IP,n)
=mod[(fe80+1122+3344+5566+789a)h,1000]
=mod[(65152+4386+13124+21862+30874),1000]
=mod[135398,1000]=398
【００３５】
【表２】
0005613142.tif 000003
【００３６】
表２は、共有セグメント５ごとに生成されるフロー配信テーブル４３６を示す。フロー配信テーブル４３６は、フローＩＤと、フローのＳアドレスと、フローのＧアドレスと、フローハッシュ値（Hash）と、フローの配信担当であるＩＦと、フローの配信状態とを対応づけて格納する。フローの配信状態は、配信中（Join）か、未配信（Leave）か、いずれかの値をとる。
例えば、フローＩＤ「F1」のフローは、ＩＦ「R3」から配信され、他のＩＦからは配信されない。
【００３７】
フロー配信テーブル４３６のフローハッシュ値は、フローの（Ｓ，Ｇ）アドレス情報を定数ｎで剰余算（ｍｏｄ）した結果である。Ｓアドレスは、レポート内のＩＣＭＰｖ６ヘッダの「Multicast Address」から読み取ることができ、Ｇアドレスは、レポート内のＩＣＭＰｖ６ヘッダの「Source Address[1]〜[N]」から読み取ることができる。
なお、以下では、ハッシュ関数の引数として、フローの（Ｓ，Ｇ）アドレス情報を用いたが、他のフローの識別情報（Ｓアドレスを単体で用いる、Ｇアドレスを単体で用いる、など）を代わりに引数として用いてもよい。
【００３８】
以下、ハッシュ空間の大きさを「n」とし、ハッシュ引数であるフローの（Ｓ，Ｇ）アドレス情報を「S,G」とし、ハッシュ関数を「H()」とし、ハッシュ引数の変換関数を「f()」とし、１６進数表現を「()h」と表記する。
H(S,G,n)= mod[f(S,G),n]
例えば、n=1000、S=F1の「2001::1000::2000::3000::4000」、G=F1の「ff3e::0001::0002::0003::0004」の場合
H(S,G,n)
=mod[(2001+1000+2000+3000+4000)h+(ff3e+0001+0002+0003+0004)h,1000]
=mod[(8193+4096+8192+12288+16384)+(65342+1+2+3+4),1000]
=mod[(49153+65352),1000]=114
【００３９】
以上説明したＩＦハッシュ値およびフローハッシュ値それぞれについて、ネットワーク管理者がハッシュキーやハッシュ値を手動で設定してもよい。
なお、ハッシュ関数は、必ずしも剰余算である必要はなく、一般的に用いられるその他のハッシュ関数を用いてもよい。ただし、同じ共有セグメント５内で配信制御の一貫性を保つため、ハッシュ値の計算方法は、同じ共有セグメント５に接続される配信ルータ４間で共通の方法とするほうがよい。
【００４０】
なお、フローハッシュ値の計算において、互いに異なる２つのＩＦ（２つの引数）であっても、ハッシュ関数により射影されるハッシュ空間内のハッシュ値が偶然一致してしまうハッシュ衝突が発生することもある。ハッシュ衝突が発生したときには、ＳＮＭＰ（Simple Network Management Protocol）コマンドなどで、ネットワーク管理者に衝突発生を警告する。
【００４１】
または、フロー割当処理部４３５は、ハッシュ衝突が発生したときには、以下の（１）〜（４）に示すハッシュ衝突の回避処理を実行してもよい。
（１）互いに衝突しない全てのＩＦハッシュ値を、そのままハッシュ空間に配置する。
（２）衝突する複数のＩＦハッシュ値のうち、そのＩＦハッシュ値の計算に使用されるＩＰアドレスが最小のＩＦハッシュ値を、そのままハッシュ空間に配置する。なお、この（２）の衝突判定は、ＩＦ集合の構成変更（ＩＦの増設やＩＦの障害回復）のたびに実行される。
（３）前記（２）で衝突する複数のＩＦハッシュ値のうち、（２）でハッシュ空間に配置されなかったＩＦハッシュ値については、そのＩＦハッシュ値とは別の場所（例えば、ＩＦハッシュ値を起点として右回りにｎ／８分ずつ順に移動した場所）に補正して、ハッシュ空間に配置する。
（４）ＩＦ集合の構成変更（ＩＦの減設やＩＦの障害発生）により、すでにハッシュ空間に配置されたＩＦハッシュ値を削除するときには、その削除したＩＦハッシュ値が（２）でハッシュ空間に配置されたＩＦハッシュ値なら、（３）で補正して配置されたＩＦハッシュ値を、補正前のＩＦハッシュ値へと戻す。この（４）を実現するために、衝突する複数のＩＦハッシュ値を管理するデータ構造（例えば、リスト構造）を用意する。
【００４２】
図４は、配信処理およびその前準備処理を示すフローチャートである。
Ｓ１０１として、各配信ルータ４は、自身への電源投入などを契機に、両テーブル（ＩＦ状態管理部４３３が生成するＩＦ管理テーブル４３４、フロー割当処理部４３５が生成するフロー配信テーブル４３６）を初期化する。なお、Ｓ１０１で初期化された両テーブルは、例えば配信ルータ４のシャットダウン時などに削除される。
ＩＦ状態管理部４３３は、自ＩＦのエントリをＩＦ管理テーブル４３４に新規追加する。エントリ内容は、自ＩＦのＩＰアドレス、そのＩＰアドレスのＩＦハッシュ値、自ＩＦであることを示す「自ＩＦ」のＩＦフラグ、クエリアタイマ（ＧＱ受信死活監視）の無効化である。
【００４３】
Ｓ１０２として、配信ルータ４（Ｒ１）は、共有セグメント５にクエリを送信するとともに、他ＩＦからのクエリを受信する。
Ｓ１０３として、配信ルータ４（Ｒ２）のＩＦ状態管理部４３３は、Ｓ１０２で受信したクエリに記載されたＩＦを、自身のハッシュ空間に登録する。
具体的には、ＩＦ状態管理部４３３は、受信パケットのＩＰヘッダから読み込んだ送信元ＩＰアドレスを検索キーとして、ＩＦ管理テーブル４３４からその検索キーのエントリ（以下、クエリエントリとする）が存在するか否かを検索する。
クエリエントリが存在するときには、そのクエリエントリのクエリア死活監視タイマ＝０とする。
クエリエントリが存在しないときには、ＩＦ管理テーブル４３４に対してクエリエントリを新規追加する。エントリ内容は、クエリの送信元ＩＰアドレス、その送信元ＩＰアドレスのＩＦハッシュ値、他ＩＦであることを示す「他ＩＦ」のＩＦフラグ、クエリア死活監視タイマ＝０である。
【００４４】
図５は、図３（ｂ）で示したリング状のハッシュ空間に、両ハッシュ値（ＩＦハッシュ値、フローハッシュ値）を配置した旨を示す説明図である。図５（ａ）は、ハッシュ空間に３つのＩＦハッシュ値を配置した図である。
Ｓ１０３のハッシュ空間の登録処理の一例として、配信ルータ４「Ｒ３」のＩＦハッシュ値「１３６」と、配信ルータ４「Ｒ１」のＩＦハッシュ値「３９８」と、配信ルータ４「Ｒ２」のＩＦハッシュ値「７６７」とが、それぞれ配置されている。
そして、ハッシュ空間での方向距離に基づいて、フローを割り当てる。例えば、配信ルータ４「Ｒ１」の配信担当となるハッシュ空間は、自身より１つ前（左回り）に位置する配信ルータ４「Ｒ３」のＩＦハッシュ値「１３６」＋１を起点として、右回りに自身のＩＦハッシュ値「３９８」までの範囲である。
【００４５】
図４に戻り、Ｓ１１１として、ホスト６は、クエリに対するレポートを返信する。ここでは、そのレポートにフローＦ１〜Ｆ４に対する配信要求を示すＪｏｉｎが含まれているとする。
Ｓ１１２として、各配信ルータ４のフロー割当処理部４３５は、Ｓ１１１のレポートを参照して、各自のハッシュ空間にＦ１〜Ｆ４を登録する（詳細は図８参照）。その結果、配信ルータ４（Ｒ１）はフローＦ２，Ｆ３の配信を担当し、配信ルータ４（Ｒ２）はフローの配信を担当しないものとする。
【００４６】
図５（ｂ）は、図５（ａ）のハッシュ空間に対して、フローハッシュ値を配置した例を示す。例えば、フローＦ１のフローハッシュ値「１１４」が、配信ルータ４「Ｒ３」のＩＦハッシュ値「１３６」の近傍に配置されている。
フロー割当処理部４３５は、ＩＦハッシュ値とフローハッシュ値との方向距離をもとに、各フローを担当するＩＦを決定する。例えば、図５（ａ）で示したように、配信ルータ４「Ｒ１」の配信担当となるハッシュ空間は、配信ルータ４「Ｒ３」のＩＦハッシュ値「１３６」＋１を起点として、右回りに自身のＩＦハッシュ値「３９８」までの範囲であるので、この範囲に含まれるフローハッシュ値「１７７」のフローＦ５は、配信ルータ４「Ｒ１」の配信担当となる。
【００４７】
以下、ＩＦハッシュ値「R」およびフローハッシュ値「F」が計算されたハッシュ空間から、フローハッシュ値ごとに担当するＩＦハッシュ値を決定する方法を示す。
ハッシュ距離  D(R,F)=R-Fとし、各Fについて、もし、D(R,F)≧０が１つ以上存在するときには、D(R,F)≧０のうちの最小値となるRをFの配信担当として割り当てる。一方、D(R,F)≧０が存在しないときには、D(R,F)が最小値となるRをFの配信担当として割り当てる。
【００４８】
図４に戻り、Ｓ１１３として、配信サーバ１は、Ｓ１１１のＪｏｉｎで指定されたフローＦ２のデータを共有セグメント５に配信する。このデータは、共有セグメント５に接続されているすべての配信ルータ４が受信可能であるが、今回はＳ１１２でフローＦ２の配信担当である配信ルータ４（Ｒ１）がホスト６に対してフローＦ２を配信する。
【００４９】
Ｓ１２１として、ホスト６は、Ｓ１１１と同様にクエリに対するレポートを返信する。ここでは、そのレポートにフローＦ５に対する配信要求を示すＪｏｉｎが含まれているとする。
Ｓ１２２として、各配信ルータ４のフロー割当処理部４３５は、Ｓ１１２と同様に、Ｓ１２１のレポートを参照して、各自のハッシュ空間にフローＦ５を登録する（詳細は図８参照）。その結果、配信ルータ４（Ｒ２）はフローＦ５の配信を担当する。
Ｓ１２３として、Ｓ１１３と同様に、配信ルータ４（Ｒ２）は、自身の配信担当であるフローＦ５をデータ配信する。
【００５０】
Ｓ１３１として、ホスト６は、クエリに対するレポートを返信する。ここでは、そのレポートにフローＦ５に対する離脱要求を示すＬｅａｖｅが含まれているとする。
Ｓ１３２として、各配信ルータ４のフロー割当処理部４３５は、今回Ｌｅａｖｅを受信したホスト６とは別のホスト６（引き続きフローＦ５の配信を要求するホスト６）が共有セグメント５内に存在しないときには、フロー配信テーブル４３６のハッシュ空間からフローＦ５を削除する。
なお、フロー配信テーブル４３６内のエントリを削除する代わりに、そのエントリを休止中（Leave）の状態に移行するとともに、後にそのエントリに対するＪｏｉｎを受信したときには、休止中（Leave）から活動中（Join）へと状態遷移してもよい。
このように、フロー配信テーブル４３６内に休止中のエントリを記憶し続けることで、フロー配信テーブル４３６のサイズは大きくなってしまうものの、休止中のエントリの再登録をせずに状態遷移するだけで済むので、配信制御を早期再開することができる。
【００５１】
図６は、ＩＦ集合の構成変更処理を示すフローチャートである。
Ｓ２０１として、フロー割当処理部４３５は、図４のＳ１１２，Ｓ１２２，Ｓ１３２などで説明したように、Ｊｏｉｎされた各フローを担当する配信ルータ４のＩＦを計算する。ここでは、配信ルータ４（Ｒ１）がフローＦ５を担当し、配信ルータ４（Ｒ２）がフローＦ２，３を担当し、配信ルータ４（Ｒ３）がフローＦ１，４を担当するものとする。
【００５２】
Ｓ２１１として、ネットワーク管理者が、共有セグメント５に配信ルータ４（Ｒ４）を増設（または障害回復）したとする。
Ｓ２１２として、配信ルータ４（Ｒ４）は、自身のＩＦを示すＩＰアドレスを含めたクエリを共有セグメント５に送信することで、他の配信ルータ４（Ｒ１〜Ｒ３）に自身の増設を通知する。
Ｓ２１３として、他の配信ルータ４（Ｒ１〜Ｒ３）のＩＦ状態管理部４３３は、Ｓ２１２で通知された配信ルータ４（Ｒ４）のＩＦをハッシュ空間に登録する（Ｓ１０３と同様の処理）。
【００５３】
Ｓ２１４として、各配信ルータ４のフロー割当処理部４３５は、ＩＰ集合の構成変更に伴い、更新されたハッシュ空間でのフロー担当を計算する。その結果、Ｓ２０１からの変更分として、フローＦ４の担当がＲ３からＲ４へと変更されるものの、他のフローＦ１〜Ｆ３の担当は変更されない。
このように、フローの担当変更が少ない理由として、図５（ｂ）で示したようなリング上のハッシュ空間にＩＦハッシュ値を配置していくため、ＩＦハッシュ値の増減の影響が局所的で済むことが、挙げられる。
【００５４】
図７は、リング状のハッシュ空間においてＩＦ集合の構成変更例を示す説明図である。図７（ａ）は、図５（ｂ）の状態から、さらに配信ルータ４（Ｒ４）のＩＦ（ＩＦハッシュ値＝９６５）が増設（または障害回復）されたときのハッシュ空間を示す。
前回の配信ルータ４（Ｒ３）のＩＦの担当範囲（Ｒ２→Ｒ３）が、今回の配信ルータ４（Ｒ４）のＩＦの担当範囲（Ｒ２→Ｒ４）と、今回の配信ルータ４（Ｒ３）のＩＦの担当範囲（Ｒ４→Ｒ３）とに分割されている。
【００５５】
図６に戻って、Ｓ２２１として、配信ルータ４（Ｒ４）に障害が発生し（または減設され）、配信ルータ４（Ｒ４）からのクエリが送信不可になったとする。
Ｓ２２２として、他の配信ルータ４（Ｒ１〜Ｒ３）のＩＦ状態管理部４３３は、配信ルータ４（Ｒ４）からのクエリ受信のタイムアウトを検出し、ハッシュ空間から配信ルータ４（Ｒ４）のＩＦを削除する。
具体的には、ＩＦ状態管理部４３３は、ＩＦ管理テーブル４３４に登録されたルータインタフェースの各エントリに対し、予め設定したクエリア死活監視用タイマの上限値に達しても当該インタフェースからのクエリを受信しないことを、タイムアウトとして検出判定する。そして、タイマ上限値を超過したエントリを削除する。
ここで、ＩＦ状態管理部４３３は、タイマ上限値を超過したＩＦ管理テーブル４３４のエントリを削除する代わりに、そのエントリを休止状態へ移行することとしてもよい（Ｓ１３２と同様の状態遷移処理）。
Ｓ２２３として、フロー割当処理部４３５は、Ｓ２２２のＩＰ集合の構成変更（ＩＦ削除）に伴い、更新されたハッシュ空間でのフロー担当を計算する。その結果、フローＦ４の担当がＲ４からＲ３へと戻ることで、Ｓ２０１の配信担当の状態へと戻る。
【００５６】
図７（ｂ）は、図７（ａ）の状態から、ＩＦ「Ｒ４」に障害が発生したとき（または減設されたとき）のハッシュ空間を示す。配信ルータ４（Ｒ４）のＩＦハッシュ値（９６５）を削除することで、前回の配信ルータ４（Ｒ４）のＩＦの担当範囲（Ｒ２→Ｒ４）と、前回の配信ルータ４（Ｒ３）のＩＦの担当範囲（Ｒ４→Ｒ３）とが、今回の配信ルータ４（Ｒ３）のＩＦの担当範囲（Ｒ２→Ｒ３）へと統合されている。
【００５７】
図８は、フロー割当処理部４３５が実行するフローの割当処理（図４のＳ１１２，Ｓ１２２）を示すフローチャートである。本フローチャートの動作主体はフロー割当処理部４３５であるので、各処理ステップでの説明において、その動作主体の記載を省略する。
【００５８】
Ｓ３０１として、ホスト６から受信したＪｏｉｎが示すフロー（Ｓ，Ｇ）に対する既存エントリがフロー配信テーブル４３６内に存在するか否かを検索する。Ｓ３０１でＹｅｓならＳ３０３へ進み、ＮｏならＳ３０２へ進む。
Ｓ３０２として、フロー配信テーブル４３６にフロー（Ｓ，Ｇ）を新規のエントリとして登録する。エントリ内容は、フロー（Ｓ，Ｇ）のアドレス、その（Ｓ，Ｇ）アドレスから計算したフローハッシュ値、フローハッシュ値に対応するハッシュ空間内の配信担当ＩＦである。
【００５９】
Ｓ３０３として、フロー配信テーブル４３６内のフロー（Ｓ，Ｇ）の配信状態が「Ｌｅａｖｅ」であるか否かを参照し、フローが未配信の状態か否かを判定する。Ｓ３０３でＹｅｓならＳ３０４へ進み、Ｎｏなら図８の処理を終了する。
Ｓ３０４として、フロー配信テーブル４３６内のフロー（Ｓ，Ｇ）ののＩＦ列を自身が収容しているか否かを参照し、自身が配信担当か否かを判定する。Ｓ３０４でＹｅｓならＳ３０５へ進み、Ｎｏなら図８の処理を終了する。
Ｓ３０５として、フロー（Ｓ，Ｇ）の配信を開始する。具体的には、フロー配信テーブル４３６内の配信状態を「Ｊｏｉｎ」としてから、配信フィルタ部４３７に対してフィルタの開放を指示し、ＭＣ配信網連携部４３２を介して配信サーバ１に配信要求（ＰＩＭ−Ｊｏｉｎ）を送信する。
【００６０】
以上説明した本実施形態では、図１で示したように、複数台の配信ルータ４を単一の共有セグメント５へと接続し、その複数台の配信ルータ４間でフロー単位に配信担当を割り当てることで、マルチキャスト配信処理におけるアクセス分散を実現する。つまり、系全体としての冗長構成による障害リスク分散だけでなく、障害が発生していないときでも配信ルータ４間でそれぞれ自身の配信担当のフローを配信するので、アクセス収容効率が向上する。
【００６１】
一方、フロー単位に配信担当を割り当てないと、パケットコピー処理などに必要な配信ルータ４の計算資源や、パケット配信処理に必要な共有セグメント５上の配信パス（帯域）の通信資源は有限であるため、特定の資源に負荷が集中する。
それにより、システム全体の資源利用効率が低下し、輻輳によるパケット損失や遅延（ゆらぎ）の増加などのサービス品質の劣化がユーザの利便性を低下させる。ここで、負荷集中をシステム増強で安易に緩和するだけでは、過剰コストが発生してしまう。
【００６２】
各配信ルータ４は、図５で示したようなリング型のハッシュ空間を定義して、そのハッシュ空間に収まるようにＩＦハッシュ値とフローハッシュ値の両方を計算する。そして、ＩＦハッシュ値とフローハッシュ値の方向距離に基づき、フローごとの配信担当を特定する。
そのため、配信ルータ４の増減設／障害切替／回復切戻などの各イベントにより、共有セグメント５へと接続された配信ルータ４の構成変更が発生しても、リング型に閉じたハッシュ空間での方向距離に基づいたフロー割当を再計算するため、構成変更が発生したＩＦハッシュ値に近接するフローを収容変更するだけで済むので、フローの配信処理の不安定の影響を局所的にすることができる。よって、配信の品質および信頼性を保ちつつ設備需要の変動に柔軟に対応可能なＩＰマルチキャスト配信サービスが提供可能となる。
【００６３】
なお、ハッシュ値を計算するための引数として、ＩＦの識別情報（ＩＰアドレスなど）や、フローの識別情報（（Ｓ，Ｇ）アドレス情報など）を用いることで、ハッシュ計算の引数にはＩＦ数を含めなくてもよい。つまり、配信ルータ４の構成変更が発生しても、構成変更されていない多くの配信ルータ４のＩＦハッシュ値が変わらないので、フローの配信処理の不安定の影響を局所的に限定することができる。
【００６４】
さらに、ハッシュ計算の引数となる識別情報は、接続される全てのＩＦおよびホスト間で交換される制御パケット（マルチキャスト／ブロードキャスト）を検出監視することで、容易に取得することができる。よって、既存のプロトコルのパケットフォーマット（クエリやレポート）をそのまま活用できるので、ルータ／ホスト間で特別な制御情報を交換することなく、スケーラブルで簡素な方法で、各ルータが自律分散的にフローごとの配信担当を特定することができる。
【００６５】
以上説明したように、単一の共有セグメント５へと接続された複数台の配信ルータ４が、それぞれの配信担当のフローを配信ルータ４の構成変更に対しても柔軟に対応するため、配信品質および信頼性を維持しつつトラヒック需要の変動に強いマルチキャスト配信制御が可能となり、地上デジタル放送／ＢＳデジタル放送のＩＰ再送信サービスなどのような、高品質かつ高信頼性なＩＰマルチキャスト配信サービスが実現可能となる。
【符号の説明】
【００６６】
１      配信サーバ
２      マルチキャスト配信網
３      リンク
４      配信ルータ
５      共有セグメント
６      ホスト
４１    ＭＣ配信網接続インタフェース
４２    ＭＣ配信網フレーム転送部
４３    転送制御回路
４４    共有セグメントフレーム転送部
４５    共有セグメント接続インタフェース
４１１  受信ＩＦ部
４１２  送信ＩＦ部
４２１  フレーム受信部
４２２  フレーム送信部
４３１  配信状態管理部
４３２  ＭＣ配信網連携部
４３３  ＩＦ状態管理部
４３４  ＩＦ管理テーブル
４３５  フロー割当処理部
４３６  フロー配信テーブル
４３７  配信フィルタ部
４４１  フレーム送信部
４４２  フレーム受信部
４５１  送信ＩＦ部
４５２  受信ＩＦ部
【図１】
0005613142.tif 000004
【図２】
0005613142.tif 000005
【図３】
0005613142.tif 000006
【図４】
0005613142.tif 000007
【図５】
0005613142.tif 000008
【図６】
0005613142.tif 000009
【図７】
0005613142.tif 000010
【図８】
0005613142.tif 000011