(57)【特許請求の範囲】
【請求項１】
少なくとも１台のルータを回線で接続し、各ルータにはノードが接続され、パケットの送受信を行なうシステムにおいて、
転送されるパケットヘッダに複数の宛先アドレスリストとその未配送ビットマップを持つパケットを、ユニキャスト経路に従って中継する手段をルータ又はノードに具備すると共に、
同一パケットを複数の宛先に配送する際に、宛先アドレスのリストと未配送ビットマップをパケットヘッダに格納して送信するトランスミッタを具備し、
前記ルータは、トランスミッタが分岐正則印を添えて送信したパケットを中継する際に、未配送ビットマップで未配送となっている列の両端の２ノード分について経路表検索を行ない、分岐不要の場合には、他のアドレスに関する経路探索を省略し、分岐が必要な場合にのみ全宛先の経路表検索を行なうことを特徴とするパケットのマルチキャスト配送システム。
【請求項２】
パケットを分岐させる際に、配送済みとなったアドレスについてはアドレスとして意味のない値に変更してから配送することを特徴とする請求項１記載のマルチキャスト配送システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は分散パケット交換網におけるマルチキャスト配送システムに関する。
インターネットを代表とする分散パケット交換網においては、パケット配送形式を宛先指定方法によって幾つかに分類している。現在のインターネットで使用されているＩＰｖ４や次世代インターネットの標準であるＩＰｖ６では、以下のパケット配送が用いられている。
▲１▼宛先が唯一のインターフェィスを表わすアドレスであるユニキャスト
▲２▼宛先が複数のインターフェィスのグループを表し、その全てへパケットのコピーを配送するマルチキャスト
▲３▼宛先が複数のインターフェィスのグループを表し、その中のいずれか一つにパケットを配送するエニーキャスト
本発明は前記▲２▼のマルチキャストに関するものである。マルチキャストは、同一の発信内容を複数のノードに効率よく配送できるので、マルチメディアデータの放送や、多地点音声動画会議等への応用が試みられている。
【０００２】
【従来の技術】
ＩＰｖ４におけるマルチキャスト実現を例に従来技術を説明する。現在標準化が提案されているＩＰｖ６においても実現方法はほぼ同様である。実際にマルチキャストを実行するためには、以下の３つの手順を踏むことになる。
▲１▼マルチキャストのアドレスの割り当て
▲２▼経路設定の依頼
▲３▼パケットの配送
これらの手順について、以下に説明する。
【０００３】
▲１▼マルチキャストのアドレスの割り当て
ＩＰｖ４では、４オクテットのＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）アドレス空間のうち、１６分の１をクラスＤと呼ばれるマルチキャストのためのアドレスに割り当てている。クラスＤのアドレスは、上位４ビットが１１１０で始まるように決められている。パケットのマルチキャストを行なう送信者は、マルチキャストするための宛先ノードのグループ毎に一つずつＩＡＮＡ（Ｉｎｔｅｒｎｅｔ  Ａｓｓｉｇｎｅｄ  Ｎｕｍｂｅｒ  Ａｕｔｈｏｒｉｔｙ）、ＩＣＡＮＮ（Ｉｎｔｅｒｎｅｔ  Ｃｏｒｐｏｒａｔｉｏｎ  ｆｏｒ  Ａｓｓｉｇｎｅｄ  Ｎａｍｅｓ  ａｎｄ  Ｎｕｍｂｅｒｓ）より、マルチキャストアドレスの割り当てを受ける。
【０００４】
▲２▼経路設定の依頼
発信者は受信者の一つ一つと連携をとりながら、予め、マルチキャストパケットが配送される経路上の全てのルータに▲３▼の実際のパケット配送で使用される経路設定を依頼する必要がある。
【０００５】
▲３▼パケットの配送
ＩＰｖ６パケットは、ユニキャスト・マルチキャストとも図２０に示すヘッダフォーマットを持つ。図のｖｅｒｓｉｏｎは、版数であり、ｃｌａｓｓはビデオ、オーディオ、データの何れであるかを知らせるためのものであり、Ｆｌｏｗ  Ｌａｂｅｌは、フローに対して何番のフローをつけてやるかを決定するものである。
【０００６】
Ｐａｙｌｏａｄ  Ｌｅｎｇｔｈはデータの長さを示し、Ｎｅｘｔ  Ｈｅａｄｅｒは何のプロトコルであるかを予め知らせるためのものである。Ｈｏｐ  Ｌｉｍｉｔは、ネットワーク内でパケットが堂々巡りしないようにパケットの中継回数の上限を示すものである。
【０００７】
Ｓｏｕｒｃｅ  Ａｄｄｒｅｓｓは、発信元アドレス、ＤｅｓｔｉｎａｔｉｏｎＡｄｄｒｅｓｓは、宛先アドレスである。最後に上位プロトコルデータがくる。
【０００８】
送信ノードはこのうち、宛先アドレスに割り当てられたマルチキャストアドレスを格納して送信する。途中のルータは、パケットを正しい方向に中継するために予め用意された経路表を検索する。経路表は、概略図２１のようになっている。図中、ネットワーク列には、インターネット上で、このルータから到達可能なネットワークを列挙してある。
【０００９】
ネットワークは、ネットワークプリフィクスとマスクで表現する。例えば、プリフィクスが３ＦＦＥ：５０１：１０００：：でマスクが４０（ＦＦＦＦ：ＦＦＦＦ：ＦＦ００：：）ならば、３ＦＦＥ：５０１：１０００：０：０：０：０：〜３ＦＦＥ：５０１：１０ＦＦ：ＦＦＦＦ：ＦＦＦＦ：ＦＦＦＦ：ＦＦＦＦ：ＦＦＦＦを範囲とするネットワークを表わす。
【００１０】
ディスティネーション列には、そのネットワーク宛のパケットを配送するために、このルータ自身が次に配送を依頼するべきルータのアドレスｎｅｉｇｈｂｏｒと、そのためにパケットを送出するインターフェィスを表している。経路表検索は、先ず検索対象となるアドレスとｎｅｔｍａｓｋの論理積（ＡＮＤ）を計算し、結果がネットワークプリフィクスと等しくなる項目を探す、検索した項目のディスティネーションｎｅｉｇｈｂｏｒに対してパケットをインターフェィスから配送する（この経路表検索には種々の高速化技法があり、特許も多数申請されている。）。
【００１１】
ユニキャストアドレスを中継する際には、宛先（ディスティネーション）は必ず一つだけ設定されており、指定されたインターフェィスから指定された次のルータへパケットを渡すことになる。発信者から受信者までの全てのルータで必ず１つずつの次のルータが設定されているので、結果としてパケットは１本の経路上を配送されることになる。
【００１２】
一方、マルチキャストに関しては、ルータにより宛先（ディスティネーション）が１つの場合と、２つ以上存在する場合を許す。１つの場合にはユニキャストと同じ動作を行なうが、２つ以上の場合は、それぞれにパケットをコピーして配送する。これにより発信時に１つだったパケットがネットワーク上で枝分かれしながら複数の受信者へ到達することができる。
【００１３】
【発明が解決しようとする課題】
既存のマルチキャスト方式には以下の問題がある。
▲１▼アドレス割り当て
マルチキャストを行なう場合、配送するグループ毎に一つずつマルチキャストアドレスを割り付ける必要がある。現行のテレビ・ラジオの代替としての放送型マルチキャストの場合は、恒常的にアドレスを割り付けることができるが、多地点テレビ会議中継等の動的にチャネルが増える通信の場合にはその都度動的にマルチキャストアドレスの払い出しを行なう必要がある。これは、インターネットで一意になるように行なう必要があり、その整合性をとるために、ある程度の複雑度を持った仕組みが必要になる。
【００１４】
▲２▼ルータ設定
マルチキャストアドレスの割り当て後、発信者から宛先クライアント一つ一つに至る経路の途中にある全てのルータの経路表にマルチキャストアドレスの項目の設定を行なう必要がある。インターネットの基幹となるルータでは、この経路表が膨大な数になる。更に、マルチキャストアドレスに対応する宛先ノードグループはメンバが頻繁に入れ替わる。そのたびに経路を再計算し経路表の更新を行なう必要がある。この処理量も膨大な量となる。
【００１５】
本発明はこのような課題に鑑みてなされたものであって、アドレス設定とルータ設定を容易にしたマルチキャスト配送システムを提供することを目的としている。
【００１６】
【課題を解決するための手段】
（１）図１は本発明の原理ブロック図である。図に示すシステムは、ルータ１同士が専用線２を介して接続されている。各ルータ１には、ノード４が接続されている。３は専用線上を転送されるパケットである。
【００１７】
図では、転送されるパケットヘッダに複数のアドレスリストとその未配送ビットマップを持つパケットをユニキャスト経路に従って、中継するようになっている。この中継手段は、ルータ１又はノード４内に設けられる。なお、ノード４は、以下に説明するトランスミッタ又はクライアントとして機能する。
また、同一パケットを複数の宛先に配送する際に、宛先アドレスのリストと未配送ビットマップをパケットヘッダに格納して送信するトランスミッタを具備し、前記ルータは、トランスミッタが分岐正則印を添えて送信したパケットを中継する際に、未配送ビットマップで未配送となっている列の両端の２ノード分について経路表検索を行ない、分岐不要の場合には、他のアドレスに関する経路探索を省略し、分岐が必要な場合にのみ全宛先の経路表検索を行なう。
【００１８】
このように構成すれば、マルチキャスト経路情報を持たずに、ユニキャスト経路情報だけでマルチキャスト配送が可能となる。また、マルチキャストパケット配送を行なう際に、検索すべきユニキャストアドレスの数が少なく、パケット配送処理が小さくなる。
【００２０】
（２）請求項２では、パケットを分岐させる際に、配送済みとなったアドレスについてはアドレスとして意味のない値に変更してから配送することを特徴とする。
【００２１】
このように構成すれば、マルチキャストに参加している他のクライアントに対して、自身が参加していることを秘匿できる。
また、同一パケットを複数の宛先に配送する際に、宛先アドレスのリストと未配送ビットマップをパケットヘッダに格納して送信するトランスミッタを具備するように構成すれば、中継ルータ群に対して、マルチキャスト経路情報設定依頼を行なうことなく、マルチキャストパケットの発信が可能となる。
【００２２】
また、リストにおけるアドレス出現順位を、パケット配送経路上の任意のパスにおいて、未配送ビットマップの未配送部分が常に連続するように、予め整列され、配送済みであることを示す印を添えて送信するトランスミッタを具備するように構成すれば、分岐正則ルータ（後述）が、効率的にマルチキャストパケット配送を行なうことが可能となる。
【００２３】
また、前記トランスミッタが分岐正則印を添えて送信したパケットを中継する際に、未配送ビットマップで未配送となっている列の両端の２ノード分についてのみ経路表検索を行ない、分岐不要の場合には他のアドレスに関する経路探索を省略し、分岐が必要な場合にのみ全宛先の経路表検索を行なうルータを具備するように構成すれば、マルチキャストパケット配送を行なう際に、請求項１のルータに比べて検索すべきユニキャストアドレスの数が少なく、パケット配送処理が小さくなる。
【００２４】
また、アドレスリストを持つ分岐探索パケットを送信し、得られた探査結果を元に分岐正則リストを作成するトランスミッタを具備するように構成すれば、分岐正則リストの自動的な作成が可能になる。また、管理者等が予め正則なリストを作成する必要がなくなる。
【００２５】
また、トランスミッタが送信した経路探査パケットについて、経路表検索を行ない、分岐を行なう際には、自ルータまでの未配送経路リストの最後尾に、未配送ビットマップを追加して探査パケットを中継し、分岐しない場合にはそのまま探査パケットを中継するルータを具備するように構成すれば、分岐正則リストの自動的な作成が可能になる。また、管理者等が予め正則なリストを作成する必要がなくなる。
【００２６】
また、前記探査パケットが中継された宛先ノードで、探査パケットの未配送経路リストをそのままトランスミッタに返送するクライアントを具備するように構成すれば、分岐正則リストの自動的な作成が可能となる。また、管理者等が予め正則なリストを作成する必要がなくなる。
【００２７】
また、経路表検索の結果、同じルータへ中継する宛先が１つ若しくは２つとなる経路がある場合、２つになる経路を１つまでか、１つになる経路を２つまで経路探索パケットの中継を省略するルータを具備するように構成すれば、経路探索のためのパケット数が少なくなり、トランスミッタでの判断の処理が少なくなる。また、ネットワーク流量を節約できる。更に、ルータ／クライアントの中継処理、折り返し処理が節約できる。
【００２８】
また、前記ルータによって、経路探査パケットが省略されていることを前提に、分岐木を解析してアドレスリストを分岐正則に整列させるルータを具備するように構成すれば、経路探索のためのパケット数が少なくなり、トランスミッタでの判断の処理が少なくなる。また、ネットワーク流量を節約できる。更に、ルータ／クライアントの中継処理、折り返し処理が節約できる。
【００２９】
また、一連のパケット送信の途中で、宛先アドレスの追加／削除ができるトランスミッタを具備するように構成すれば、マルチキャスト配送中のチャネルに、途中から参加／脱退が可能になる。
【００３０】
また、追加したアドレスに関する経路探索を行ない、アドレスを分岐正則に保つトランスミッタを具備するように構成すれば、マルチキャスト配送中のチャネルに、途中から参加／脱退しても分岐正則による配送の効率化が継続する。
【００３１】
また、定期的にアドレスリストが分岐正則かをチェックする正則検査パケットを送信し、非正則通知がくると正則化をやり直すトランスミッタを具備するように構成すれば、マルチキャスト中継中に途中経路の変更があっても、一定時間で検出し、適応することが可能になる。
【００３２】
また、前記トランスミッタが出す正則検査パケットのアドレスリストを経路表検索し、正則性が崩れていた場合に非正則通知を返送し、それ以外は検査パケットを中継するルータを具備するように構成すれば、マルチキャスト中継中に途中経路の変更があっても、一定時間で検出し、適応することが可能になる。
【００３３】
また、前記トランスミッタ及びルータで、パケットの元の宛先アドレスとして、未配送アドレスリストのノードのうち一つを格納するように構成すれば、マルチキャスト配送経路の途中に本発明による配送を介さないルータが存在しても、マルチキャスト中継が可能になる。
【００３４】
また、自己が送信し、自己のインタフェースに到着したパケットを検査し、自ノードが宛先リストに含まれている時に、これを受理するノードを具備するように構成すれば、マルチキャスト経路情報を持たず、ユニキャスト経路情報だけでマルチキャスト配送が可能となる。
【００３５】
【発明の実施の形態】
本発明では、上記の問題を、従来のパケットに宛先が一つしか指定できなかったのを改め、複数の宛先アドレスのリストとリスト中で未配送なものを示すビットマップをパケットの拡張ヘッダとして添付することで解決するものである。
【００３６】
以下、図面を参照して本発明の実施の形態例を詳細に説明する。
マルチキャストでデータを送信するサーバは、図２に示す形式のパケットを作成する。ＩＰヘッダと異なる項目それぞれの意味は以下のようになる。
【００３７】
（ａ）Ｄｅｓｔｉｎａｔｉｏｎ  Ａｄｄｒｅｓｓ（ＭＳＣ  ａｄｄｒｅｓｓ）このパケットがＭＳＣ（Ｍｕｌｔｉｃａｓｔ  ｆｏｒ  Ｓｍａｌｌ  Ｃｏｍｍｕｎｉｔｙ）であることを示す特殊なＩＰアドレス。途中のルータが本発明のマルチキャスト方式でこのパケットを処理すべきであることを判別できるようにする。
【００３８】
（ｂ）ＭＳＣ  ｏｐｔｉｏｎｓ
以降の処理バリエーションを確保する際にこの項目にオプションを指定する。
（ｃ）＃  ｏｆ  ｄｅｓｔ
本パケットに含まれるアドレスのリストの長さ
（ｄ）Ｄｓｔｉｎａｔｉｏｎ  Ａｄｄｒｅｓｓ  ＃ｎ
マルチキャストアドレスを配送するべきｎ個めの宛先アドレス
（ｅ）ｄｅｓｔｉｎａｔｉｏｎ  ｂｉｔｍａｐ
上記アドレスのリストのうち、本パケットがこれから到達すべき宛先のｎ番目を“１”、本パケットからは到達させる必要がないものは“０”で表わすビットマップ。最初の発進時は全て“１”とする。
【００３９】
宛先アドレスが３２を超えた場合には、３２個目のアドレスの次に３３個目から６５個目までのアドレスのビットマップを挟んでアドレスのリストを続けて添付する。
【００４０】
本実施の形態例のルータは、リストのアドレスのうちビットマップが“１”になっているものについて、ユニキャストのための経路表を検索する。検索した結果、次のルータ一つ一つについてパケットを転送する。この際、検索結果の次のルータが同じものについては、パケットを一つで済ますので、マルチキャストになる。中継パケットが更に中継されるべき宛先アドレスの位置を示すビットマップを“１”とし、他は“０”とする。
【００４１】
このように構成すれば、マルチキャスト経路情報を持たずに、ユニキャスト経路情報だけでマルチキャスト配送が可能となる。
以上の中継によって、パケットは最終目的ノードまで到達し、このノードによって、リストが検査され、自己宛のアドレスがある場合は、これを受理し、より上位のプロトコルスタック（例：ＴＣＰ）処理を行なう。この実施の形態例によれば、自己が送信し、自己のインターフェィスに到着したパケットを検査し、自ノードが宛先リストに含まれている時に、これを受理するノードを具備することにより、マルチキャスト経路情報を持たず、ユニキャスト経路情報だけでマルチキャスト配送が可能となる。
【００４２】
以降における分岐正則とは、ルータにおける経路表検索を簡略化するための、前処理が施されているアドレスリストの性質である。分岐正則なアドレスリストとは、マルチキャスト経路の全てのルータにおいて、ビットマップが“１”となるノードが必ず連続することが保証されているような順番に整列しているものである。例えば、図３（一実施の形態例を示すブロック図）に示すように分岐するマルチキャストで、［ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ］というアドレスリストを考える。図１と同一のものは、同一の符号を付して示す。
【００４３】
分岐深さは、ａ，ｆ，ｇが２、ｂ，ｃ，ｄ，ｅが３であるものとする。発信者からｄまでの経路でルータでの分岐を３回通る。その間にビットマップは図４に示すように変化し、経路のどの点でもビットマップ１は連続している。これが全ての終点で成り立つので、［ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ］は分岐正則である。
【００４４】
一方、リスト［ａ，ｇ，ｆ，ｂ，ｃ，ｄ，ｅ］は、ａに向かう最初の分岐で、ビットマップが［１，０，０，１，１，１，１］となり“１”が離れてしまう。従って、分岐正則ではない。
【００４５】
分岐正則であることを保証されている場合には、ビットマップで“１”となっている部分の両端にあるアドレスのみをまず経路表検索し、それが同じルータへ中継することになっていれば、その間にある宛先へも同じルータを経由して配送することが保証できるので、それについては経路表を検索することなしで次の中継先を決定することができる。
【００４６】
本実施の形態例は、同一パケットを複数の宛先に配送する際に、宛先アドレスのリストと未配送ビットマップをパケットヘッダに格納して送信するトランスミッタを具備することにより、中継ルータ群に対して、マルチキャスト経路情報設定依頼を行なうことなく、マルチキャストパケットの発信が可能となる。
【００４７】
このような形式でパケットを発信するトランスミッタと、これにより経路表検索を効率的に行なうルータを記述することができる。この方法を採用してマルチキャストを行なうために、トランスミッタはアドレスリストが分岐正則であることを示すビットをＭＳＣオプションに設定し、ルータはこのビットが立っているかを検査して、経路表検索方法を切り替える。
【００４８】
この実施の形態例によれば、リストにおけるアドレス出現順位を、パケット配送経路上の任意のパスにおいて、未配送ビットマップの未配送部分が常に連続するように、予め整列され、配送済みであることを示す印を添えて送信するトランスミッタを具備することにより、分岐正則ルータが効率的にマルチキャストパケット配送を行なうことが可能となる。
【００４９】
また、前記トランスミッタが分岐正則印を添えて送信したパケットを中継する際に、未配送ビットマップで未配送となっている列の両端の２ノード分についてのみ経路表検索を行ない、分岐不要の場合には他のアドレスに関する経路検索を省略し、分岐が必要な場合にのみ全宛先の経路表検索を行なうルータを具備することにより、マルチキャスト配送を行なう際に、請求項１のルータに比べて検索すべきユニキャストアドレスの数が少なく、パケット配送処理が小さくなる。
【００５０】
上記の分岐正則にリストを整列させるための仕組みについて説明する。トランスミッタは分岐正則としたいアドレスのリストを上位プロトコルデータが空のパケットに添付し、ＭＳＣオプションに経路探索依頼である印を添付して発信する。ルータは、請求項１の動作をしてパケットをマルチキャストすると同時に、若しパケットを分岐するならば、上位プロトコルデータ部分の最後尾に、どのように分岐を行なったかをビットマップとして追加記録する。
【００５１】
パケットが宛先クライアントに到達すると、トランスミッタからどのように分岐してきたかの履歴が記録されてきたことになる。これをトランスミッタにそのまま返信する。トランスミッタに全てのクライアントから分岐履歴が帰ってきたところで、分岐木を解析しリストを分岐正則に整列させる。
【００５２】
この実施の形態例によれば、アドレスリストを持つ分岐探索パケットを送信し、得られた調査結果を元に分岐正則リストを作成するトランスミッタを具備することにより、分岐正則リストの自動的な作成が可能となる。また、管理者等が予め正則なリストを作成する必要がなくなる。
【００５３】
また、トランスミッタが送信した経路探索パケットについて、経路表検索を行ない、分岐を行なう際には、自ルータまでの未配送経路リストの最後尾に未配送ビットマップを追加して探査パケットを中継し、分岐しない場合にはそのまま探査パケットを中継するルータを具備することにより、分岐正則リストの自動的な作成が可能になる。また、管理者等が予め正則なリストを作成する必要がなくなる。
【００５４】
また、前記探査パケットが中継された宛先ノードで、探査パケットの未配送経路リストをそのままトランスミッタに返送するクライアントを具備することにより、分岐正則リストの自動的な作成が可能となる。また、管理者等が予め正則なリストを作成する必要がなくなる。
【００５５】
また、分岐正則探査において、正則が自明となる部分分岐木についてはその先の探査をおこなわなくても分岐正則なリストが作成できることを利用して、探査処理を効率化する発明を記述することができる。
【００５６】
探索を行わなくてもよい理由は、以下のアドレスの個数に関する数学的帰納法で示すことができる。
先ず、アドレスが１個及び２個の場合には、自明に分岐正則である。
【００５７】
次に、ｎ−１個以下リストについて分岐正則なリストが作れるものとする。アドレスが３個以上（仮にｎ個とする）である場合を考える。あるルータがｎ個の宛先が未配送である探査パケットを受け取ったものとする。これを分岐させると、最小で２グループ、最大ｎグループに枝分かれする。それぞれ未配送宛先は、最小で１個、最大でｎ−１個含む。ここで、グループが含む宛先が１個のものと２個のものの個数で分類すると、図５に示すようなものとなる。
【００５８】
（あ）は、宛先が１個及び２個のグループがなく、３以上のグループへしか分岐していないことになる。但し、分岐はしているので、各グループは、ｎ−１個以下になる。この場合は、履歴を追加更新し、全てのグループに探査パケットを中継することで、中継先から帰ってくるパケットで、分岐先の部分リストを分岐正則にすることができる。これを全てのグループについて連結すればよい。
【００５９】
（い）は宛先１個のグループが１つあるが、宛先２個のグループがない場合である。宛先１個のグループは、それ自身が分岐正則であることは自明なので、中継しない。他のグループについて中継する。その結果、他のグループについて履歴が帰る。省略した１個のグループには履歴は帰らないが、他のグループの履歴を集めると、分岐は１つあったことがわかるので、これを他のグループの分岐正則と連結すればよい。
【００６０】
（う）は同様であるが、省略したのが宛先が１つのグループ１つか、宛先が２個のグループ１つのどちらかであるが、どちらにしろ足りない２つの宛先を連結すれば分岐正則なので、これを他のグループの分岐正則リストに接続する。
【００６１】
この実施の形態例によれば、経路表検索の結果、同じルータへ中継する宛先が１つ若しくは２つとなる経路がある場合、２つになる経路を１つまでか、１つになる経路を２つまで経路探査パケットの中継を省略するルータを具備することで、経路探索のためのパケット数が少なくなり、トランスミッタでの判断の処理が少なくなる。また、ネットワーク流量を節約できる。更に、ルータ／クライアントの中継処理、折り返し処理が節約できる。
【００６２】
また、ルータによって経路探査パケットが省略されていることを前提に、分岐木を解析してアドレスリストを分岐正則に整列させるルータを具備することにより、経路探索のためのパケット数が少なくなり、トランスミッタでの判断の処理が少なくなる。また、ネットワーク流量を節約できる。更に、ルータ／クライアントの中継処理、折り返し処理が節約できる。
【００６３】
また、宛先を変更してアドレスを追加／削除することができるトランスミッタを実現することができる。これによれば、一連のパケット送信の途中で宛先アドレスの追加／削除ができるトランスミッタを具備することにより、マルチキャスト配送中のチャネルに途中から参加／脱退が可能になる。
【００６４】
また、分岐正則を利用して効率化している状況で、前記トランスミッタ動作をを行なう際に分岐正則化を全てに対してもう一度やり直すトランスミッタである。この実施の形態例によれば、追加したアドレスに関する経路探索を行ない、アドレスを分岐正則に保つトランスミッタを具備することにより、マルチキャスト配送中のチャネルに、途中から参加／脱退しても分岐正則による配送の効率化が継続する。
【００６５】
また、ルータがパケットを分岐する際に、ビットマップを“０”にしたアドレスについては内容をクリアし、途中経路や終点等のホストが他にどこにマルチキャストしたかを隠蔽することができる。この発明によれば、マルチキャストに参加している他のクライアントに対して、自身が参加していることを秘匿できる。
【００６６】
また、一度構築した正則リストの有効性を検査し、ルーチング環境が変わった際でも適応可能にする仕組みを実現することができる。トランスミッタが、要検査をオプションに設定にすると、経路の各ルータは正則性をチェックする。崩れていなければ履歴と共に発信元に送り返す。トランスミッタはこれを受けて、必要な部分リストについては改めて正則化を行なう。
【００６７】
この実施の形態例によれば、定期的にアドレスリストが分岐正則かをチェックする正則検査パケットを送信し、非正則通知がくると正則化をやり直すトランスミッタを具備することにより、マルチキャスト中継中に途中経路の変更があっても、一定時間で検出し、適応することが可能になる。
【００６８】
また、前記トランスミッタが出す正則検査パケットのアドレスリストを経路表検索し、正則性が崩れていた場合に非正則通知を返送し、それ以外は検査パケットを中継するルータを具備することにより、マルチキャスト中継中に途中経路の変更があっても、一定時間で検出し、適応することが可能になる。
【００６９】
また、中継途中にＭＳＣに対応しないルータがあった場合にもＭＳＣが通るようにＩＰｖ６ヘッダの宛先をＭＳＣを表わすアドレスを入れないで、ＭＳＣリストのうち、未配送のアドレスの一つを入れておくことができる。非ＭＳＣルータは、これを通常のユニキャストと同様に中継するが、途中か終点でＭＳＣを解釈するルータがこれを分岐できる。
【００７０】
この実施の形態例によれば、トランスミッタ及びルータで、パケットの元の宛先アドレスとして、未配送アドレスリストのノードのうち一つを格納することにより、マルチキャスト配送経路の途中に本発明による配送を介さないルータが存在しても、マルチキャスト中継が可能になる。
【００７１】
図６は本発明の他の実施の形態例を示すブロック図である。この図では、ルータ１同志が専用線６を介して接続され、各ルータには、ノードａ〜ｈが接続されている。以下、このネットワークを用いて実施の形態例を説明する。このネットワークでは、ホスト８台（ａ〜ｈ）、４本のイーサネット（Ｗ〜Ｚ）、１本の専用線６、ルータＲ１、Ｒ２の２台からなる。
【００７２】
ホストのＩＰアドレスは、それぞれａ〜ｈとし、ルータのインターフェィス各々のＩＰアドレスは、専用線がｒ１、ｒ２、イーサネット側がｗ、ｘ、ｙ、ｚとする。この時、ａ、ｂは図７に示すような経路表を持つ。
【００７３】
同様に、ｃ、ｄはＷ、ｗをそれぞれＸ、ｘに、ｅ、ｆはＹ、ｙに、ｇ、ｈはＺ、ｚに変えた経路表となる。
一方、ルータＲ１、Ｒ２の経路表は図８に示すようなものとなる。
【００７４】
（基本動作の実施の形態例）
先ず、実施の形態例を示す。マルチキャストパケットの発信者をａとし、受信者をｂ、ｃ、ｄ、ｅ、ｆ、ｇ、ｈとする。ａ上のプロセスは、socketインターフェィスを経由してメッセージ送信を依頼する。
【００７５】
sendto（socket，msg，length，flag，dest，destlen）
destは本発明のために新たに定義する宛先アドレス指定構造体（struct sock addr msc）で以下のように宛先リストを格納する。
【００７６】
struct sock addr msc｛
short               smsc family；          ／* AF MSC *／
unsign int           smsc list desc；        ／* regular list desc *／
char                 smsc nnodes；          ／* # of sest nodes *／
struct inet addr v6 smsc addrs［MAX ADDR LIST］／* dest address list *
／
｝
ここで、smsc familyはmscのために定義するアドレスファミリの定数値である。
【００７７】
smsc list descは、以降の分岐正則で使用するリスト指示子である。
smsc nnodesは、このリストに含まれる宛先ノードの数である。
smcs addrs はＩＰｖ６アドレスの配列である。
【００７８】
ノードａは、これに対して以下の属性を持つパケットを発信する。
IPv6  src     =a
IPv6  dst     =MSC
IPv6  opt     =MSC followed
MSC option     =None
RoutType       =MSC
# of dest      =7
bitmap         =[1,1,1,1,1,1,1]
dest addr      =[b,c,d,e,f,g,h]
パケットは、具体的には図９に示すようなものとなる。
【００７９】
ａは自身の経路表を使用して［ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈ］を検索し、次の結果を得る。
ｂ：      自分の所属するイーサネットｗを通じて直接配送
c,d,e,f,g,h：  ｗを経由して中継
ｂ宛に直接パケットを送る際、ｂｉｔｍａｐ（ビットマップ）を以下のように変更する。
【００８０】
bitmap        =[1,0,0,0,0,0,0]
dest addr     =[b,c,d,e,f,g,h]
ｗ宛には以下のパケットを送付する。
【００８１】
bitmap        =[0,1,1,1,1,1,1]
dest addr     =[b,c,d,e,f,g,h]
ｂはこのパケットを見て、先ずＩＰｖ６ヘッダがＭＳＣを表わすことを検査し、ｏｐｔヘッダを見て、ｎｏ  ｏｐｔｉｏｎであることを確認し、ｒｏｕｔｉｎｇヘッダのビットマップを検査する。“１”が立っているアドレスが自分のアドレスなので、これを受理し、上位プロトコルに渡す。
【００８２】
ルータＲ１はこのパケットを見て、先ずＩＰｖ６ヘッダがＭＳＣを表わすことを検査し、ｏｐｔヘッダを見てｎｏオプションであることを確認する。次に、ｒｏｕｔｉｎｇヘッダのビットマップを検査する。“１”が立っているアドレスそれぞれについて、自分のアドレスでないことを確認した後、経路表を検査して以下の結果を得る。
【００８３】
c,d,g,h:ｒ２を経由して配送
e ,f:イーサネットＹ経由で直接配送
これにより、ｃ，ｄ，ｇ，ｈ用にｒ２に対して
bitmap        =[0,1,1,0,0,1,1]
dest addr     =[b,c,d,e,f,g,h]
ｅには、
bitmap        =[0,0,0,1,0,0,0]
dest addr     =[b,c,d,e,f,g,h]
fには、
bitmap        =[0,0,0,0,1,0,0]
dest addr     =[b,c,d,e,f,g,h]
を送付する。
【００８４】
（分岐正則時の中継動作例）
次に、分岐正則に関する動作として、一実施の形態例を示す。ノードａから宛先［ｃ，ｄ，ｇ，ｈ］へ送信する場合を考える。請求項１の場合では、ルータＲ１は次のパケットを中継する。
【００８５】
bitmap        =[1,1,1,1]
dest addr     =[c,d,g,h]
このため、４つの宛先が全て同じ中継先ｒ２に行くにも拘らずｃ，ｄ，ｇ，ｈの全てを経路表検索する必要があった。ここでは、ｃ，ｈのみの検索ですむようにする。
【００８６】
先ず、アドレス出現順位を実装したトランスミッタは、宛先アドレスを具備したトランスミッタと同様にパケットを組み立てるが、ＭＳＣ  ｏｐｔｉｏｎに、定数ＭＳＣ  ＲＥＧＵＬＡＲＥＤを記す。
【００８７】
分岐が必要な場合のみ全宛先の経路表検索を行なう処理を実装したルータＲ１は、ＩＰｖ６宛先アドレスがＭＳＣであることを確認した後、ＭＳＣオプションにＭＳＣ  ＲＥＧＵＬＡＲＥＤが記されているのを確認する。この場合は、ビットマップの両端ｃ，ｈのみを経路検索する。両方共にｒ２経由であるので、ｄ，ｇに関しては検索せず、ｒ２へ中継する。
【００８８】
一方、分岐が必要な場合のみ全宛先の経路表検索を行なう処理を実装したルータＲ２は、同様にｃ，ｈを検索する。すると、今度はｃはＸ、ｈはＺのインターフェィスへ中継する必要があることがわかる。従って、ｄ，ｇも検索を行ない、ｄはＸ、ｈはＺに中継する。
【００８９】
（分岐正則探査の実施の形態例）
上記の分岐正則リストを作成するための例を説明する。全体の流れは以下の通りである。
【００９０】
プログラム：      宛先リストを分岐正則にするように依頼。
トランスミッタ：  宛先リストを含む探査パケットを発信する。
ルータ：          探査パケットを中継しながら分岐履歴を記録する。
【００９１】
クライアント：    到着した探査パケットを分岐履歴毎にトランスミッタに送り返す。
トランスミッタ：  分岐履歴から分岐正則リストを作成する。分岐正則リストに対する識別子を返還。
【００９２】
プログラム：      識別子を宛先につけてパケット送信。
トランスミッタは、以下の情報を持つ探査パケットを作成し、本発明に係る方法で発信する。
【００９３】
IPv6 src    =a
IPv6 dst    =MSC
IPv6 opt    =MSC followed
MSC option  =MSC branch inquiry
RoutingHdr NextHdr=ICMP
Route Type  =MSC
# of dest   =7
bitmap        =[1,1,1,1,1,1,1]
dest addr     =[b,c,d,e,f,g,h]
ICMP Type     =MSC Branch Inquiry
ICMP Code     =None
ICMP bitmap len=0
ICMP Identifier=MSC inquiryをする毎に一意になるＩＤ
この時のパケットは、図１０に示すようなものとなる。
ルータは、請求項１と同様な中継動作をしつつ、中継すべきインターフェィスが２つ以上あった場合、即ち分岐が発生する場合には、ＩＣＭＰヘッダを以下のように更新する。
【００９４】
#of bitmapを１加算
新しいｂｉｔｍａｐをＩＣＭＰヘッダ末尾に追加
ルータＲ１でｅ，ｆに対して中継する際は、ＩＣＭＰヘッダが図１１に示すように変化する。
【００９５】
ｅはこれを受けとり、ａに対してＲｏｕｔｉｎｇヘッダ以下のコピーを以下のように返送する。
IPv6 src    =ｅ
IPv6 dst    =ａ
IPv6 opt    =None
IPv6 NextHdr=ICMP
ICMP Type   =MSC Branch record
ICMP Code   =None
以下、Routingヘッダ以降のコピー
この時のパケットは具体的には、図１２に示すようなものとなる。
この場合、同様のパケットが全てのクライアントから帰ってくる。前述のトランスミッタは、Ｉｄｅｎｔｉｆｉｅｒが同一であるパケットを集める。今回の例では、以下の履歴が返信されてくる。
【００９６】
0003792940.tif 000002
0003792940.tif 000003
これから次の手順で、分岐正則リストを作成する。
【００９７】
struct regular list*make regular list()[／*レギュラーリストを作るには、*／
struct tree tree;
tree  =make tree();      ／*分岐木を作成して *／
return make list(tree)   ／*分岐木をリストにする。*／
／*分岐木は図１３に示すような形をしている。図において、○は分岐するルータを表わす。ルータの横に（ｅ，ｆ）等とつくのは、そこで分岐していることはわかるが、その下の分岐構造が未決定のノードのリストである。
*／
make tree()[／* 分岐木を作成する。  *／
分岐木のルートになるルータを作り、
未決定ノードリストに全てのノードを入れる。
【００９８】
／*o(b,c,d,e,f,g,h)  *／
for(i=0;i<# of node;i++)[／* 全てのノードについて*／
node iから帰ってきた履歴を見る。
【００９９】
depth=node iの分岐深さ。／*bだと１、ｈだと４／*
for(j=node iがついているルートの深さ。  depth;j>0;j++)
node iがいるルータからルータを一つ作成して伸ばす。
【０１００】
新しく作ったルータにnode iを移動。
]
今、node iがいるルータにｅをぶら下げる。
【０１０１】
for(j=# of bitmap ;j>0;j--)／* 全ての履歴について*／
foreach(j番目とj-1番目の履歴で変化したノード)
if(ノードは未決定)
node iまでのルータ系列で深さｊ−１のルータに未決定ノードとして登録。]
make regular list(tree)[
treeを深さ優先に探索し、ノードを列挙。
]
上記手続きを例に当てはめると、図１４に示すように分岐木が生成できる。
（効率的分岐正則探査の実施の形態例）
分岐探査で、クライアントの全てから、履歴が帰ってくる必要はない。例えば図１５に示す分岐木の解析途中の経路木（ｈ）はｈの履歴を待たずにｇの横に置くことができるのは自明である。そこで、このような場合にｈへの探査パケット中継を抑制することで探査を効率化する。
【０１０２】
次に、他の実施の形態例を以下に説明する。
先ず、トランスミッタは、探査パケットを用意するが、ＭＳＣオプションとしてｅｆｆｅｃｔ  ｂｒａｎｃｈ  ｉｎｑｕｉｒｙを指定する。
【０１０３】
また、ルータは、この探査パケットを中継する際には、分岐しない場合にそのまま探査パケットを中継するルータと同様な動作をするが、中継先インターフェィス毎のグループをカウントして図１６に示すような場合分けをする。
【０１０４】
（あ）の場合には全ての中継を行なう。
（い）の場合で、省略することで中継先がなくならないならば、宛先１個の１グループについては中継を省略する。
【０１０５】
（う）の場合には、省略することで中継先がなくならないならば、宛先１個の２つのグループ、若しくは、宛先２個のグループを１つ選択して中継を省略する。
【０１０６】
前記トランスミッタでは、経路解析手段が以下のように変わる。
make tree()[／*   分岐木を作成する。 *／
分岐木のルートになるルータを作り
未決定ノードリストに全てのノードを入れる。
【０１０７】
／* o(b,c,d,e,f,g,h)*／
for(i=0;i<# of node;i++) [／*全てのノードについて*／
node iから帰ってきた履歴を見る。
【０１０８】
depth=node iの分岐深さ。／*bだと1、hだと4*／
for(j=node iがついているルートの深さ、depth;j>0;j++)
node iがいるルータからルータをルータ１つ作って伸ばす。
【０１０９】
新しく作ったルータにnode iを移動。
]
今、node iがいるルータにｅをぶら下げる。
【０１１０】
for(j=# of bitmap;j>0;j--)／* 全ての履歴について  *／
foreach(ｊ番目とj-1番目の履歴で変化したノード)
if(ノードは未決定）
node iまでのルータ系列で深さj-1のルータに未決定ノードとして登録。
foreach(全てのルータについて)／* 前記処理で増えたところ*／
if（未決定ノードが２以下なら）
未決定ノードをルータに直接ぶら下げる。
]
[b,c,d,e,f,g,h]ではｈ,c,e,bへの中継が省略できる（図１７参照）。
（宛先変更）
分岐正則をプログラムが指示し、正則化が終わると、識別子が帰る。連続してマルチキャストパケットを流す時には、前の正則リストを流用することで、再度正規化を行なわないことにする。しかしながら、クライアントが受信を中断したり、新しいクライアントが加わると、正則化をやり直す必要がある。
【０１１１】
また、この際に始めから正規化をやり直すトランスミッタを設けることができる。正規化処理自体は、前述のものと全く同じである。
（分岐先隠蔽）
中継ルータで分岐先ノード以外をクリアし、他のクライアントに自分ノードへの通信先を隠蔽するルータである。請求項１のルータと動作はほぼ同じであるが、ｂ宛に直接パケットを送る際、ビットマップを変更する際にアドレスもクリアする。
【０１１２】
bitmap     =[1,0,0,0,0,0,0]
dest addr   =[b,0,0,0,0,0,0]
ｗ宛には以下のパケットを送付する。
【０１１３】
bitmap     =[0,1,1,1,1,1,1]
dest addr   =[0,c,d,e,f,g,h]
（正則検査）
ネットワークのトポロジ変化や障害に対応するために正則性を定期的に検査を行なえるようにする。次に、他のトランスミッタの実施の形態例を以下に説明する。
【０１１４】
IPv6 src   =a
IPv  dst   =MSC
IPv  opt   =MSC followed
MSC option  =MSC check regular
RoutingHdr Nexthdr=ICMP
RoutType    =MSC
# of dest   =7
bitmap      =[1,1,1,1,1,1,1]
dest addr   =[b,c,d,e,f,g,h]
ICMP Type  =MSC check regular
ICMP Code  =None
ICMP bitmap len=0
ICMP Identifier=MSC inquiryをする毎に一意になるＩＤ
パケットは具体的には、図１８に示すようなものになる。
【０１１５】
一方、これを中継するルータは、ＭＳＣオプションがｃｈｅｃｋ  ｒｅｇｕｌａｒであるので、ビットマップが“１”のノードを全て経路検索する。ここで、全てが同じ経路であるか、若しくは両端のノードが異なる中継先になるなら、通常のＭＳＣ中継を行なう。若し、両端が同じ中継先になるにも拘らず、その間に異なる中継先のノードがあれば、以下のパケットを送信先に返信する。
【０１１６】
IPv6 src    =router addr
IPv6 dsc    =ａ
IPv6 NextHdr=ICMP
ICMP Type   =MSC not regular
ICMP Code   =None
ICMP Identifier=MSC  inquiryをする毎に一意になるＩＤ
これに異常が起こったビットマップで異常なノードが“０”になるように設定して送り返す。パケットは、具体的には図１９に示すようなものとなる。トランスミッタは、これを受けて、正規化を再度行なう。
（非ＭＳＣルーチング）
ＩＰｖ６パケットのｄｅｓｔにＭＳＣルーチングヘッダリストの中でビットマップが“１”である最初のアドレスを入れる。このようにすると、途中にＭＳＣ非対応ルータがあっても、宛先ノードのうちの一つに向かって中継が継続される。途中にＭＳＣ対応ルータがあるか、宛先ノードがＭＳＣ対応ならばここで、更に別の宛先に改めて中継が起こる。
【０１１７】
以上、説明したように、本実施の形態例によれば、以下の利点を得ることができる。
▲１▼小規模のグループ内での同報通信を、インターネット上のルータにマルチキャストのための特別な経路管理の負担なく行なうことができる。
▲２▼送信者が経路トポロジを探査し、ルータでの経路検索コストを低くするように宛先情報を整列できる。
▲３▼クライアントのマルチキャストグループへの加入／脱退がルータの関与なしに可能になる。その際も▲２▼の利点を失わない。
▲４▼経路途中に本発明の機構を実現しないルータが存在しても、上記の利点を享受することができる。
【０１１８】
【発明の効果】
以上、説明したように、本発明によれば、以下のような効果が得られる。
（１）請求項１の発明によれば、転送されるパケットヘッダに複数の宛先アドレスリストとその未配送ビットマップを持つパケットを、ユニキャスト経路に従って中継する手段を有することにより、マルチキャスト経路情報を持たずに、ユニキャスト経路情報だけでマルチキャスト配送が可能となる。
また、未配送ビットマップで未配送となっている列の両端の２ノード分について経路表検索を行ない、分岐不要の場合には、他のアドレスに関する経路探索を省略し、分岐が必要な場合にのみ全宛先の経路表検索を行なうことにより、マルチキャストパケット配送を行なう際に、検索すべきユニキャストアドレスの数が少なく、パケット配送処理が小さくなる。
（２）請求項２の発明によれば、パケットを分岐させる際に、配送済みとなったアドレスについてはアドレスとして意味のない値に変更してから配送することにより、マルチキャストに参加している他のクライアントに対して、自身が参加していることを秘匿できる。
【０１１９】
このように、本発明によれば、アドレス設定とルータ設定を容易にしたマルチキャスト配送システムを提供することができる。
【図面の簡単な説明】
【図１】本発明の原理ブロック図である。
【図２】パケットの構成例を示す図である。
【図３】本発明の一実施の形態例を示すブロック図である。
【図４】ビットマップの推移を示す図である。
【図５】グループ分岐の説明図である。
【図６】本発明の他の実施の形態例を示すブロック図である。
【図７】ａ，ｂの経路を示す図である。
【図８】Ｒ１，Ｒ２の経路を示す図である。
【図９】パケットの構成例を示す図である。
【図１０】パケットの構成例を示す図である。
【図１１】ＩＣＭＰの構成例を示す図である。
【図１２】パケットの構成例を示す図である。
【図１３】分岐木の構成例を示す図である。
【図１４】分岐木の生成を示す図である。
【図１５】解析途中の経路木を示す図である。
【図１６】中継先インターフェィスごとのグループの場合分けを示す図である。
【図１７】ｈ，ｃ，ｅ，ｂへの中継省略の説明図である。
【図１８】パケットの構成例を示す図である。
【図１９】パケットの構成例を示す図である。
【図２０】ＩＰｖ６のヘッダフォーマットの構成図である。
【図２１】検索表の構成を示す図である。
【符号の説明】
１  ルータ
２  専用線
３  パケット
４  ノード
【図１】
0003792940.tif 000004
【図２】
0003792940.tif 000005
【図３】
0003792940.tif 000006
【図４】
0003792940.tif 000007
【図５】
0003792940.tif 000008
【図６】
0003792940.tif 000009
【図７】
0003792940.tif 000010
【図８】
0003792940.tif 000011
【図９】
0003792940.tif 000012
【図１０】
0003792940.tif 000013
【図１１】
0003792940.tif 000014
【図１２】
0003792940.tif 000015
【図１３】
0003792940.tif 000016
【図１４】
0003792940.tif 000017
【図１５】
0003792940.tif 000018
【図１６】
0003792940.tif 000019
【図１７】
0003792940.tif 000020
【図１８】
0003792940.tif 000021
【図１９】
0003792940.tif 000022
【図２０】
0003792940.tif 000023
【図２１】
0003792940.tif 000024