(57)【要約】【課題】特定ルータでの輻輳発生の確率を減少させ、より安定したマルチキャストを提供する。【解決手段】CBT基盤オーバーレイマルチキャストのためのCBT構成方法において、加入しようとする終端ノードがコアノードに既に加入済みの子ノード情報を要請するステップと、コアノードから子ノード情報を受信した終端ノードが自身と情報を受信した各子ノードとの方向性を計算し、最小の結果値を有する子ノードの情報を加入要求メッセージとともにコアノードに伝送するステップと、コアノードがその加入要求メッセージ及び子ノードの情報を受信して、該当子ノードと終端ノードの方向性計算結果値を、加入済み子ノード間の方向性計算結果値と比較し、その比較結果によって終端ノードを該当子ノードの親又は子ノードとして加入させてCBTを構成するステップと、を含む方向性基盤としたことを特徴とする。【選択図】  図８
2004304799.tif 000002
【特許請求の範囲】
【請求項１】
CBT基盤オーバーレイマルチキャストのためのCBT構成方法において、
CBTに加入しようとする任意の終端ノードがコアノードに既に加入されている子ノード情報を要請して受信するステップと、
前記コアノードから任意の子ノード情報を受信した前記終端ノードが自身と前記情報を受信した各子ノードとの方向性を計算し、最小の結果値を有する前記コアノードの子ノードに対する情報を加入要求メッセージとともに前記コアノードに伝送するステップと、
前記コアノードが前記終端ノードから伝送された前記加入要求メッセージ及び前記子ノードに対する情報を受信して、該当子ノードと前記終端ノードの方向性計算結果値を、既に加入されている子ノード間の方向性計算結果値と比較し、その比較結果によって前記終端ノードを該当子ノードの親ノードまたは子ノードとして加入させてCBTを構成するステップと、を含む方向性基盤としたことを特徴とするCBT構成方法。
【請求項２】
コアノード及び終端ノードが親ノード、子ノード、兄弟ノードと周期的にハローパケットを送受信して該当ノードの状態を確認し、その状態値によって、構成済みのCBTを再構成するステップをさらに含む、請求項１記載のCBT構成方法。
【請求項３】
方向性は、コアノードに隣接する任意の二つのノード間の距離を辺とする三角形で、この三角形の内外角と高さとを用いて計算される請求項１記載のCBT構成方法。
【請求項４】
方向性は、direction=(α+β)×y（式中、C0：コアノード、a1，a2：任意のノード、α：C0−a2を底辺とした三角形a1−C0−a2で辺C0−a1と辺C0−a2がなす内角、β：同じく三角形a1−C0−a2で辺C0−a1と辺a1−a2がなす外角、y：三角形の高さ、direction:方向性）により計算される請求項３記載のCBT構成方法。
【請求項５】
終端ノードと最小値を有する子ノードとは、コアノードから受信するパケットの進行方向が同一であると判断し、前記終端ノードが該当子ノードの親ノードまたは子ノードのいずれかと判断する請求項１記載のCBT構成方法。
【請求項６】
CBTを構成するステップは、
コアノードで方向性計算結果値を比較した結果、該当子ノードと終端ノードの方向性計算結果値が既に加入されている子ノード間の方向性計算結果値より小さい場合、前記終端ノードを自身の子ノードに加入させ、既に加入されている該当子ノードを該終端ノードの子ノードとして再加入するようにメッセージを伝送するステップと、
前記既に加入されている該当子ノードが前記メッセージによって前記コアノードから脱退し、前記終端ノードの子ノードに加入するステップと、を行う請求項１記載のCBT構成方法。
【請求項７】
CBTに加入しようとする任意の終端ノードがコアノードに既に加入されている子ノード情報を要請して受信するステップと、
前記コアノードから任意の子ノード情報を受信した前記終端ノードが自身と前記情報を受信した各子ノードとの方向性を計算し、最小の結果値を有する前記コアノードの子ノードに対する情報を加入要求メッセージとともに前記コアノードに伝送するステップと、
前記コアノードが前記終端ノードから伝送された前記加入要求メッセージ及び前記子ノードに対する情報を受信して、該当子ノードと前記終端ノードの方向性計算結果値を、既に加入されている子ノード間の方向性計算結果値と比較し、その比較結果によって前記終端ノードを該当子ノードの親ノードまたは子ノードとして加入させてCBTを構成するステップと、を含むことを特徴とするCBT基盤オーバーレイマルチキャストのための方向性基盤CBT構成方法を、デジタル処理装置に実行させるプログラムを記録したデジタル処理装置で読み取り可能な記録媒体。
【請求項８】
コアノード及び終端ノードが親ノード、子ノード、兄弟ノードと周期的にハローパケットを送受信して該当ノードの状態を確認し、その状態値によって、構成済みのCBTを再構成するステップをさらに含むプログラムを記録した請求項７記載の記録媒体。
【請求項９】
方向性は、コアノードに隣接する任意の二つのノード間の距離を辺とする三角形で、この三角形の内外角と高さを用いて計算されるプログラムを記録した請求項７記載の記録媒体。
【請求項１０】
方向性は、direction=(α+β)×y（式中、C0：コアノード、a1，a2：任意のノード、α：C0−a2を底辺とした三角形a1−C0−a2で辺C0−a1と辺C0−a2がなす内角、β：同じく三角形a1−C0−a2で辺C0−a1と辺a1−a2がなす外角、y：三角形の高さ、direction:方向性）により計算されるプログラムを記録した請求項９記載の記録媒体。
【請求項１１】
終端ノードと最小値を有する子ノードとは、コアノードから受信するパケットの進行方向が同一であると判断し、前記終端ノードが該当子ノードの親ノードまたは子ノードのいずれかと判断するプログラムを記録した請求項７記載の記録媒体。
【請求項１２】
CBTを構成するステップで、
コアノードで方向性計算結果値を比較した結果、該当子ノードと終端ノードの方向性計算結果値が既に加入されている子ノード間の方向性計算結果値より小さな場合、前記終端ノードを自身の子ノードに加入させ、既に加入されている該当子ノードを該終端ノードの子ノードとして再加入するようにメッセージを伝送するステップと、
前記既に加入されている該当子ノードが前記メッセージによって前記コアノードから脱退し、前記終端ノードの子ノードに加入するステップと、を行うプログラムを記録した請求項７記載の記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、CBT(Core Based Tree)基盤オーバーレイマルチキャストのための方向性基盤CBT構成方法に関する。
【背景技術】
【０００２】
同じ情報を様々な受信者に送信しようとする場合は、一対一通信であるユニキャスト(unicast)よりマルチキャスト(multicast)を介して該当マルチキャストグループに参加した受信者にデータを伝送する一対多通信が送信者の伝送オーバーヘッド、ネットワークの資源、受信者側での遅延(latency)を減らせて効率的である。
【０００３】
しかし、ネットワークで行われるIPマルチキャストは、マルチキャストルーティングアルゴリズムによってデータを中継するマルチキャストルータでネットワークを構成しなければならない。これに伴い、既存のユニキャストルータをマルチキャストルータに交替しなければならない新規投資費用が所要される問題が発生する。
【０００４】
一方、ISP（インターネットサービスプロバイダ）の立場ではマルチキャストサービス収益モデル不在による投資対比収益性の理由で、また技術的な側面でもSIP(Session Initiation Protocols)間マルチキャストトラフィック通過に対するネゴシエーションとポリシー、既存ユニキャストトラフィックとの平等性(Fairness)、そして相変らず不透明なInter-Domailマルチキャスト技術等で特にISPバックボーン網でマルチキャスト導入が遅れている。
【０００５】
反面、インターネットを用いた社内放送、キャンパス放送等私的で地域的なマルチキャスト要求は急速に増加している。これに伴い現在のユニキャスト網を基盤とするマルチキャスト伝送の必要性が台頭してきている。
【０００６】
ユニキャスト網基盤のマルチキャスト伝送の一方法として、終端ノードでデータを中継(relay)するオーバーレイ(overlay)マルチキャストがある。終端ノードは最近、データ処理速度の急激な向上、メモリーの増加及びVDSL普及等によるデータ伝送速度の急速な向上で、他の終端ノードでデータを中継することが可能となり、効率的なオーバーレイマルチキャストを期待できるようになった。
【０００７】
図１Ａは、マルチキャストルータを用いたIPマルチキャストを行うネットワークを示し、図１Ｂは、ユニキャストルータを用いたオーバーレイマルチキャストを行うネットワークを示す。
【０００８】
オーバーレイマルチキャストの基本概念は、図１Ａに示すように複数のマルチキャストルータ(Multicast Router)(MR1〜MR4)で構成されたネットワークでマルチキャストを行う代わりに、図１Ｂに示すように複数のユニキャストルータ(Unicast Router)(R1〜R4)で構成されたネットワークでノードBのように終端ノード(ホスト)でパケットを中継(コピー後に伝送)する方法でユニキャスト基盤のマルチキャストを行うものである。すなわち、終端ノードでマルチキャストルータの役割を行うのである。
【０００９】
図１Ｂのネットワークでオーバーレイマルチキャストを行う場合、図１Ａのネットワークでマルチキャストを行う場合より遅延時間やパケット数が増加するが、マルチキャストルータを必要としないので、既存のユニキャスト網基盤で比較的効率的なマルチキャスト通信を提供できる。
【００１０】
オーバーレイマルチキャストプロトコル関連研究としては、DVMRP(Distance Vector Multicast Routing Protocol)、マルチキャストルーティングプロトコルを適用したNarada、ネットワーク上にscattercast proxyを設置してproxy間のユニキャスト通信を用いたscattercast、そして、CBT(Core Based Tree)基盤の研究等が進行中にある。このようなオーバーレイマルチキャストの核心は、同じマルチキャストグループに属した終端ノードで効率的なパケット伝送のためのオーバーレイツリーを構成して維持するものである。
【００１１】
これらのうち、DVMRPマルチキャストルーティングプロトコルを適用した場合よりも、共有ツリーであるCBTを適用する場合のほうが、拡張性と制御メッセージのオーバーヘッド(OVERHEAD)、そして性能面で効率的である。すなわち、CBTは、コアノードにトラフィックが集中するという短所があるが、マルチキャストメンバーの変動に対し相対的に少ない制御メッセージを発生すればよく、各終端ノードで管理しなければならない情報量が少ないので、拡張性に優れた長所があって具現が易しい。また終端ノードの処理速度向上とデータ伝送能力向上に比例して中継可能な子ノード(child node)数を増加させることによってマルチキャストの全体性能を向上させることができる長所により、CBTでオーバーレイツリーを構成することがより効率的である。
【００１２】
CBT基盤オーバーレイマルチキャストは、基本的にノード間の距離(distance)が近いノードを親(parent)または子ノードに選択してCBTを構成する。距離をメトリック(Metric)で構成するCBTでは、CBT上のノード全体において、パケットを中継する過程で特定リンクやルータを重複して経由することによって、該当リンクやルータにトラフィックが集中して輻輳(Congestion)が発生し得る。
【００１３】
一般的にマルチキャストは、TCPとは異なって輻輳制御メカニズムを有していないUDPを基盤に動作するので、ネットワークに輻輳が発生する場合でもトラフィック量を減少することはなく、引続きパケットをネットワークに伝送する。その結果、パケットの損失によるマルチキャストの性能だけでなく、ネットワークの性能を悪化させてネットワーク上の他のTCP接続との公平性問題(Unfair problem)を起こす問題点があった。
【００１４】
図２は、同じマルチキャストグループに属したノードからなるネットワークトポロジーの一例を示し、各ノードの加入順序は、a、b、h、h1の順になっている。
【００１５】
図２を参照すれば、コアノードC0にリンク(Link)#1を介してルータ1(R1)が連結し、ノードaは、ルータ1(R1)にリンク#2を介して連結する。ルータ1(R1)にリンク#3を介してルータ3(R3)が連結し、ノードbがリンク#32を介してルータ3(R3)に連結する。ノードhは、リンク#31を介してルータ3(R3)に連結し、ノードh1は、リンク#33を介してルータ3(R3)に連結している。
【００１６】
図３Ａ〜Ｄは、図２のネットワークトポロジーでコアノードがC0である距離メトリック基盤CBTに基づき、ノードa、b、hの順序で加入する場合を説明するための図面である。
【００１７】
図３Ａは、図２のネットワークでコアノードがC0である距離メトリック基盤CBTにノードa、b、hの順序で加入する場合に各ノード間の距離を示す。コアノードC0とノードaの距離は3で、コアノードC0とノードbの距離は9で、ノードaとノードhの距離は4で、ノードhとノードbとの距離は8で、ノードaとノードbの距離は10である。
【００１８】
すなわち、コアノードC0とノードaは、リンク#1を介してルータ1(R1)からリンク#2を経由し連結するため、リンク#1の距離1とリンク#2の距離2を足せば全体的な距離は3となる。
【００１９】
コアノードC0とノードbは、リンク#1を介してルータ1(R1)を経由し、そしてリンク#3を介してルータ3(R3)からリンク#32を経由し連結するため、リンク#1の距離1と、リンク#3の距離1と、リンク32の距離7を足せば全体的な距離は9となる。
【００２０】
ノードaとノードhは、リンク#2を介してルータ1(R1)を経由し、そしてリンク#3を介してルータ3(R3)からリンク#31を経由し連結するため、リンク#2の距離2と、リンク#3の距離1と、リンク#31の距離1を足せば全体的な距離は4となる。
【００２１】
ノードhとノードbは、リンク#32を介してルータ3(R3)からリンク#31を経由し連結するので、リンク#32の距離7とリンク#31の距離1を足せば全体的な距離は8となる。
【００２２】
ノードaとノードbは、リンク#2を介してルータ1(R1)を経由し、そしてリンク#3を介してルータ3(R3)からリンク#32を経由し連結するので、リンク#2の距離2と、リンク#3の距離1と、リンク#32の距離7を足せば全体的な距離は10となる。
【００２３】
ここで、二つのノード間距離は、照会(query)と応答(response)の交換に対する終端間遅延時間(end-to-end-latency)を用いた。
【００２４】
コアC0の収容(中継)可能な子ノード数が2である場合、図２と図３Ａを参照すれば、図３Ｂに示すように、まず、aとbノードが加入した状態で、hノードは、aノードとは距離が4で、bノードとは8であるから、aノードを親ノードに選択して加入し、図３ＣのCBTを構成する。
【００２５】
図３Ｄは、コアノードから一つのマルチキャストパケットがCBT全体に中継される過程で各リンク及びルータで処理するパケットの数を示す。すなわち、図２のネットワークトポロジーで図３Ａのような距離を有することによって、図３Ｂ及び図３Ｃのような手順を踏む距離基盤CBTを構成すれば、各リンク及びルータで処理するパケット数は次の通りである。
【００２６】
コアノードC0から各ノードa、ノードb、ノードhにパケットを伝達するためには、コアノードからノードaとノードbにパケットを伝送し、ノードaからパケットを中継してノードhに送ることができる。
【００２７】
すなわち、図２を参照してコアノードC0からノードaまでのパケット伝送経路を見てみると、コアノードC0からリンク#1を介してルータ1(R1)を経由し、そしてリンク#2を介してノードaまでの経路が描かれる(リンク#1、R1、リンク#2)。また、コアノードC0からノードbまでのパケット伝送経路を見てみると、コアノードC0からリンク#1を介してルータ1(R1)を経由し、そしてリンク#3を介してルータ3(R3)を経由し、さらにリンク#32を介してノードbまでの経路が描かれる(リンク#1、R1、リンク#3、R3、リンク#32)。また、ノードaからパケットを中継してノードhに送る経路を見てみると、ノードaからリンク#2を介してルータ1(R1)を経由し、そしてリンク#3を介してルータ3(R3)を経由し、さらにリンク#31を介してノードhまでの経路が描かれる(リンク#2、R1、リンク#3、R3、リンク#31)。
【００２８】
したがって、各リンク別、ルータ別にパケットが通過する回数を計算してみれば、リンク#1は２回、ルータ1(R1)は３回、リンク#2は２回、リンク#3は２回、ルータ3(R3)は２回、リンク#31は１回、リンク#32は１回となる。すなわち、N個のマルチキャストパケットをCBT全体に伝送するために、ルータ1(R1)で3×N個のパケットを処理する。
【００２９】
このように他のリンクやルータよりもルータR1にパケットが集中することは、図４に示すように、パケットを１番目階層であるC0からR1を経由してノードaとノードbに中継する経路(実線矢印)に対して、２番目階層ノードaからノードhにパケットを中継する経路(点線矢印)がR1に戻って経由されるためである。すなわち、実線矢印で示すように、コアノードC0からノードaとノードbに中継する時、各々一回ずつR1を経由するうえに、点線矢印で示すように、ノードaからノードhにパケットを中継する時もR1及びR3を経由するようになるため、R1を全体で３回経由することになる。
【００３０】
図５Ａは、図２に示されたネットワークトポロジーでC0、a、b、h、h1のノードから構成された距離メトリック基盤のCBTを示すもので、ノードh1はノードaを親ノードに選択して加入する。図５Ｂは、図５Ａのネットワークにおいて各リンク及びルータで処理するパケットの数を示す。図５Ｂを参照すれば、各々、リンク#1は２個、ルータ1(R1)は４個、リンク#2は３個、リンク#3は３個、ルータ3(R3)は３個、リンク#31は１個、リンク#32は１個、リンク#33は１個のパケットを処理する。
【００３１】
すなわち、図２のネットワークトポロジーで図３Ａのような距離を有し、図５Ａに示されたような距離基盤CBTを構成すれば、各リンク及びルータで処理するパケット数は次の通りである。
【００３２】
コアノードC0から各ノードa、ノードb、ノードh、ノードh1にパケットを伝達するためにはコアノードからノードaとノードbにパケットを伝送し、ノードaからパケットを中継してノードhとノードh1に送ることができる。
【００３３】
すなわち、図２を参照してコアノードC0からノードaまでのパケット伝送経路を見てみると、コアノードC0からリンク#1を介してルータ1(R1)からリンク#2を経由しノードaまでの経路が描かれる(リンク#1、R1、リンク#2)。コアノードC0からノードbまでのパケット伝送経路を見てみると、コアノードC0からリンク#1を介してルータ1(R1)を経由し、そしてリンク#3を介してルータ3(R3)からリンク#32を経由しノードbまでの経路が描かれる(リンク#1、R1、リンク#3、R3、リンク#32)。また、ノードaからパケットを中継してノードhに送る経路を見てみると、ノードaからリンク#2を介してルータ1(R1)を経由し、そしてリンク#3を介してルータ3(R3)からリンク#31を経由しノードhまでの経路が描かれる(リンク#2、R1、リンク#3、R3、リンク#31)。ノードaからパケットを中継してノードh1に送る経路を見てみると、ノードaからリンク#2を介してルータ1(R1)を経由し、そしてリンク#3を介してルータ3(R3)からリンク#33を経由しノードh1までの経路が描かれる(リンク#2、R1、リンク#3、R3、リンク#33)。
【００３４】
したがって、各リンク別、ルータ別にパケットが通過する回数を計算してみれば、リンク#1は２回、ルータ1(R1)は４回、リンク#2は３回、リンク#3は３回、ルータ3(R3)は３回、リンク#31は１回、リンク#32は１回、リンク#33は１回となる。
【００３５】
図５Ａ及び図５Ｂに示すように、新しいノードの加入でR1を経由して戻る回数が増加すれば、ルータ1(R1)では輻輳の問題が発生し得る。
【００３６】
このように、距離メトリック基盤のCBTでは、加入順序により輻輳が発生する問題点がある。特に、ルータR1のようにコアノードと連結したルータやリンクで輻輳が発生する場合、CBT全体に影響を及ぼす深刻な問題点となり得る。
【発明の開示】
【発明が解決しようとする課題】
【００３７】
上述のような従来の距離メトリック基盤CBTの問題点は、ツリーで下位(子)ノードに伝送されるマルチキャストパケットの中継経路を考慮せずに、単純にノード間の距離だけで親または子ノードを選択し、CBTを構成することに起因する。
【００３８】
本発明は、このような問題点を解決するために案出されたもので、特定ルータとリンクにトラフィックが集中する問題を解決するためのCBT基盤オーバーレイマルチキャストのための方向性基盤CBT構成方法を提供することにその目的がある。
【課題を解決するための手段】
【００３９】
前記目的を達成するため本発明の一態様によれば、CBT基盤オーバーレイマルチキャストのためのCBT構成方法において、CBTに加入しようとする任意の終端ノードがコアノードに既に加入されている子ノード情報を要請して受信するステップと、コアノードから任意の子ノード情報を受信した終端ノードが自身と情報を受信した各子ノードとの方向性を計算し、最小の結果値を有するコアノードの子ノードに対する情報を加入要求メッセージとともにコアノードに伝送するステップと、コアノードが終端ノードから伝送された加入要求メッセージ及び子ノードに対する情報を受信して、該当子ノードと終端ノードの方向性計算結果値を、既に加入されている子ノード間の方向性計算結果値と比較し、その比較結果によって終端ノードを該当子ノードの親ノードまたは子ノードとして加入させてCBTを構成するステップと、を含む方向性基盤としたことを特徴とする。
【００４０】
この方法では、コアノード及び終端ノードが親ノード、子ノード、兄弟ノードと周期的にハローパケットを送受信して該当ノードの状態を確認し、その状態値によって、構成済みのCBTを再構成するステップをさらに含むことができる。また、方向性は、コアノードに隣接する任意の二つのノード間の距離を辺とする三角形で、この三角形の内外角と高さとを用いて計算するものとし、特に、direction=(α+β)×y（式中、C0：コアノード、a1，a2：任意のノード、α：C0−a2を底辺とした三角形a1−C0−a2で辺C0−a1と辺C0−a2がなす内角、β：同じく三角形a1−C0−a2で辺C0−a1と辺a1−a2がなす外角、y：三角形の高さ、direction:方向性）により計算するようにする。
【００４１】
さらに、終端ノードと最小値を有する子ノードとは、コアノードから受信するパケットの進行方向が同一であると判断し、該終端ノードが該当子ノードの親ノードまたは子ノードのいずれかと判断することができる。また、CBTを構成するステップは、コアノードで方向性計算結果値を比較した結果、該当子ノードと終端ノードの方向性計算結果値が既に加入されている子ノード間の方向性計算結果値より小さい場合、終端ノードを自身の子ノードに加入させ、既に加入されている該当子ノードを終端ノードの子ノードとして再加入するようにメッセージを伝送するステップと、既に加入されている該当子ノードがそのメッセージによってコアノードから脱退し、終端ノードの子ノードに加入するステップと、を行うものとすることができる。
【００４２】
本発明の別の態様によれば、CBTに加入しようとする任意の終端ノードがコアノードに既に加入されている子ノード情報を要請して受信するステップと、コアノードから任意の子ノード情報を受信した終端ノードが自身と情報を受信した各子ノードとの方向性を計算し、最小の結果値を有するコアノードの子ノードに対する情報を加入要求メッセージとともにコアノードに伝送するステップと、コアノードが終端ノードから伝送された加入要求メッセージ及び子ノードに対する情報を受信して、該当子ノードと終端ノードの方向性計算結果値を、既に加入されている子ノード間の方向性計算結果値と比較し、その比較結果によって終端ノードを該当子ノードの親ノードまたは子ノードとして加入させてCBTを構成するステップと、を含むことを特徴としたCBT基盤オーバーレイマルチキャストのための方向性基盤CBT構成方法を、デジタル処理装置（ノードのホストコンピュータ等）に実行させるプログラム、そして、該プログラムを記録したデジタル処理装置で読み取り可能な記録媒体を提供する。
【００４３】
この場合も、コアノード及び終端ノードが親ノード、子ノード、兄弟ノードと周期的にハローパケットを送受信して該当ノードの状態を確認し、その状態値によって、構成済みのCBTを再構成するステップをさらに含むものとすることができる。また、方向性は、コアノードに隣接する任意の二つのノード間の距離を辺とする三角形で、この三角形の内外角と高さを用いて計算されるものとし、特に、direction=(α+β)×y（式中、C0：コアノード、a1，a2：任意のノード、α：C0−a2を底辺とした三角形a1−C0−a2で辺C0−a1と辺C0−a2がなす内角、β：同じく三角形a1−C0−a2で辺C0−a1と辺a1−a2がなす外角、y：三角形の高さ、direction:方向性）により計算されるものとする。
【００４４】
さらにまた、終端ノードと最小値を有する子ノードとは、コアノードから受信するパケットの進行方向が同一であると判断し、終端ノードが該当子ノードの親ノードまたは子ノードのいずれかと判断するものとすることができる。また、CBTを構成するステップで、コアノードで方向性計算結果値を比較した結果、該当子ノードと終端ノードの方向性計算結果値が既に加入されている子ノード間の方向性計算結果値より小さな場合、終端ノードを自身の子ノードに加入させ、既に加入されている該当子ノードを終端ノードの子ノードとして再加入するようにメッセージを伝送するステップと、既に加入されている該当子ノードがそのメッセージによってコアノードから脱退し、終端ノードの子ノードに加入するステップと、を行うものとすることができる。
【発明の効果】
【００４５】
本発明に係る方向性メトリック基盤のCBTを用いたオーバーレイマルチキャストによれば、パケットの中継進行方向を考慮したCBTを生成することによって、従来の距離メトリック基盤CBTにあった特定ルータにパケットが集中する問題点を解決できる。そして、このような効果によって、特定ルータでの輻輳発生の可能性を減少させられ、より安定したマルチキャストを提供できる。
【発明を実施するための最良の形態】
【００４６】
本発明では、コアノードから各ノードに伝送されるパケットの伝送進行方向を分析し、進行方向が同じノードをCBTでの親または子ノードに選択することによって、距離メトリック基盤CBTの輻輳問題を解決できる。
【００４７】
まず、本発明による方向性メトリック基盤CBTの属性(attribute)を定義するようにする。表1は、本発明に係る方向性メトリック基盤CBTの定義された属性(attribute)である。
【００４８】
【表１】
2004304799.tif 000003
【００４９】
表1を参照すれば、C(x)は、ノードxの子(child)集合、num(C(x))は、ノードxの子数、max(C(x))は、ノードxが最大収容(中継)可能な子数、Pi(x)は、ノードxのi番目先祖ノード(i>0)である。また、dist(x、y)は、ノードxとy間の距離、C0は、コアノード、hは、CBTに加入を望む新しいノード、Nx、Nyは、CBTに既に加入しているノードを示す。さらに、p(x、y)は、ノードxとyのうちでコアノードとの距離が近いノードを示すもので、例えば、コアノードとノードxとの距離(dist(C0、x))がコアノードとノードyとの距離(dist(C0、y))より小さければ、p(x、y)はxとなる。一方、c(x、y)は、ノードxとyのうちでコアノードとの距離が遠いノードを示すもので、例えばコアノードとノードxとの距離(dist(C0、x))がコアノードとノードyとの距離(dist(C0、y))より小さければ、c(x、y)はyとなる。atan()は、アークタンジェント値をラジアン値で計算することを示し、sqr()は、自乗根返還、PIは、パイ(π)値(≒3.1415926)、WhoisChild(x)は、ノードxにxの子情報を要請することを示し、direction(x、y)は、ノードxとy間の方向性値を計算することを示す。
【００５０】
図６Ａ〜Ｄは、本発明に係る方向性基盤CBT構成方法を説明するための図面で、コアノードを基準にして隣接する二つのノード間の位置関係を示す。図６Ａは、コアC0、ノードa1、ノードa2の順に連結していて、図６Ｂは、ノードa1、コアC0、ノードa2の順に連結している。図６Ｃ及び図６Ｄのようにコアノードに隣接する二つのノード間の距離を辺とする三角形も考えられる。この三角形の内外角と高さを用いてノード間中継されるパケットの進行方向性を求める。
【００５１】
本発明による方向性計算アルゴリズムは、次の通り示すことができる。
【００５２】
Procedure:direction(a1、a2)
hc ← dist(C0、c(a1、a2))
ac ← dist(C0、p(a1、a2))
ha ← dist(a1、a2)
if(hc+ac≧ha)
retun ∞
else if(ac+ha≦hc)
retun 0
end if
x ← ((hc*hc)+(ac*ac)-(ha*ha)/(2*hc)
y ← sqrt(ac*ac-x*x)                    //高さ計算
if(x>0)
α ← atan(y/x)*(180/PI)
else
α ← 180-atan(y/-x)*(180/PI)//ラジアン値を角度に変換
end if
γ ← atan(y/(hc-x))*(180/PI)
β ← α+γ
return(α+β)*y      //direction(a1、a2)の結果値
【００５３】
すなわち、ノードa1とノードa2のうち、コアC0から遠いノードとC0の距離をhcとし、ノードa1とノードa2のうち、コアC0に近いノードとC0の距離をacとし、ノードa1とノードa2の距離をhaとする。
【００５４】
まず、図６Ａのようにac+ha≦hcである場合には、リターン値で0を出力し、図６Ｂのようにhc+ac≧haである場合には、リターン値で∞を出力する。
【００５５】
一方、図６Ｃまたは図６Ｄの場合には((hc*hc)+(ac*ac)-(ha*ha))/(2*hc)をxにし、sqrt(ac*ac-x*x)をyにして高さ(y)を計算する。この際、図６Ｃのように、x>0である場合にはatan(y/x)*(180/PI)をαにし、図６Ｄのようにx<0である場合には、180-atan(y/-x)*(180/PI)をαにしてラジアン値を角度に変換する。次に、atan(y/(hc-x))*(180/PI)をγにし、α+γをβにして(α+β)*y値をdirection(a1、a2)の結果値にリターンする。
【００５６】
上記のように、本発明では方向性計算アルゴリズムで計算された方向性値を距離の代わりに新しいメトリックに用いてCBTを構成する。すなわち、ノード間の方向性値が最も小さい値を有する二つのノードは、コアノードから受信するパケットの進行する方向が同一であると判断してどちらかを親、どちらかを子ノードと判断する。これを通じてルータ1で戻る回数を減らすことができる。
【００５７】
コアノード選出に関する方法は、手動的な方法を使用する。Bootstrap Mechanismなどの方法もあるが、実現の利便のためにコアノードを指定し、グループに参加するすべてのノードは設定を通じてコアノードを知っていたり、コアノードを知っているノードに対する情報を有すると仮定する。
【００５８】
図７Ａ〜Ｃと図８及び図９Ａ〜Ｂは、本発明に係る方向性基盤CBTを説明するための図面で、従来の距離基盤CBT構成と比較するために、図２に示されたネットワークトポロジーでa、b、h、h1ノードの順序でCBTに加入する場合を考察する。したがって、各図面に示された各ノード間の距離は、図２に示されたネットワークトポロジーと図３Ａに示された各ノード間の距離を示すものである。各ノード間の距離は、図３Ａで説明した。
【００５９】
図７Ａは、h加入前のCBTを示し、図７Ｂは、h加入後のCBTを示し、図７Ｃのグラフは、一つのマルチキャストパケットに対して各リンク及びルータで処理するパケットの数を示す。
【００６０】
加入を望むノードhは、中継可能な最大子数が２であるコアノードC0から、C0の子であるa、bノード情報を得た後、a、bノードと前述した方向性値direction(h、a)[≒214.09]とdirection(h、b)[≒41.37]を計算する。
【００６１】
hノードは、小さい方向性値を示すbノードとの情報をもつCBT加入要求メッセージを伝送し、１番目の階層の親であるコアノードC0に加入を要求する。コアノードC0は、受信したCBT加入要求メッセージのdirection(h、b)値と、周期的なハロー(hello)メッセージを介して受信した既存の子ノード間direction(a、b)[≒71.57]値とを比較する。この結果、[direction(h、b)<direction(a、b)]は、hノードからbノードにパケットを中継する経路が、前述した戻る現象を避ける効率的な経路であることを意味する。
【００６２】
これに伴い、コアノードC0は、hノードを新しい子ノードとして加入させ、既存の子だったbノードを新しくhノードを親として再加入することをフラッシュ(Flush)メッセージの伝送で要請する。この要請によってbノードは、２番目階層の親hノードに加入して７ＢのようなCBTを構成する。
【００６３】
図７Ｃは、各リンク及びルータが処理するパケットの個数である。図面で実線は、本発明に係る方向性基盤CBT構成に対する結果で、点線は、従来の距離基盤CBT構成に対する結果である。図７Ｃを参照して本発明の結果を見れば、図中実線で示すように、各々リンク#1は２個、ルータ1(R1)は２個、リンク#2は１個、リンク#3は１個、ルータ3(R3)は２個、リンク#31は２個、リンク#32は１個のパケットを処理する。
【００６４】
すなわち、図２と図７Ｂを参照して、コアノードC0からノードaまでのパケット伝送経路を見てみると、コアノードC0からリンク#1を介してルータ1(R1)からリンク#2を経由しノードaまでの経路が描かれる(リンク#1、R1、リンク#2)。コアノードC0からノードhまでのパケット伝送経路を見てみると、コアノードC0からリンク#1を介してルータ1(R1)を経由し、そしてリンク#3を介してルータ3(R3)からリンク#31を経由しノードhまでの経路が描かれる(リンク#1、R1、リンク#3、R3、リンク#31)。また、ノードhからパケットを中継してノードbに送る経路を見てみると、ノードhからリンク#31を介してルータ3(R3)からリンク#32を経由しノードbまでの経路が描かれる(R3、リンク#31、リンク#32)。
【００６５】
したがって、各リンク別、ルータ別にパケットが通過する回数を計算してみれば、リンク#1は２回、ルータ1(R1)は２回、リンク#2は１回、リンク#3は１回、ルータ3(R3)は２回、リンク#31は２回、リンク#32は１回となって、これは、図７Ｃで実線で示されている。これに対し、従来の距離基盤CBTによる結果は、図７Ｃに点線で対比して示すように、各リンク別、ルータ別にパケットが通過する回数が、リンク#1は２回、ルータ1(R1)は３回、リンク#2は２回、リンク#3は２回、ルータ3(R3)は２回、リンク#31は１回、リンク#32は１回で対比される。従来の距離基盤CBTによる結果は、既に図３Ｄで示めしたとおりである。
【００６６】
図８は、図２に示されたネットワークトポロジーで、本発明に係る方向性基盤CBTによるマルチキャストパケットの中継経路を示すもので、実線は、C0からa、hへの中継経路を示し、点線は、hからbへの中継経路を示す。これは、図４に示された従来の距離基盤CBTによるマルチキャストパケットの中継経路と対比される。
【００６７】
すなわち、N個のマルチキャストパケットに対して、従来の距離メトリック基盤のCBTでのような戻る現象が発生しないので、ルータR1で3×N個ではなく2×N個のパケットだけ処理すれば済む。たとえリンク#31で処理するパケットの数が増加するとしても、距離メトリック基盤のCBTでの問題点であるコアノードが連結したルータなど特定のルータやリンクのパケット集中現象を緩和させる結果を得ることができる。
【００６８】
図９Ａは、図２に示されたネットワークトポロジーで、本発明に係るC0、a、b、h、h1のノードで構成された方向性メトリック基盤のCBTを示し、図９Ｂは、図９Ａのネットワークにおいて各リンク及びルータで処理するパケットの数を示す。図９Ｂを参照すれば、各々リンク#1は2個、ルータ1(R1)は2個、リンク#2は1個、リンク#3は1個、ルータ3(R3)は3個、リンク#31は3個、リンク#32は1個、リンク#33は1個のパケットを処理する。
【００６９】
すなわち、図２と図９Ａを参照して、コアノードC0からノードaまでのパケット伝送経路を見てみると、コアノードC0からリンク#1を介してルータ1(R1)からリンク#2を経由しノードaまでの経路が描かれる(リンク#1、R1、リンク#2)。コアノードC0からノードhまでのパケット伝送経路を見てみると、コアノードC0からリンク#1を介してルータ1(R1)を経由し、そしてリンク#3を介してルータ3(R3)からリンク#31を経由しノードhまでの経路が描かれる(リンク#1、R1、リンク#3、R3、リンク#31)。また、ノードhからパケットを中継してノードbに送る経路を見てみると、ノードhからリンク#31を介してルータ3(R3)からリンク#32を経由しノードbまでの経路が描かれる(R3、リンク#31、リンク#32)。ノードhからパケットを中継してノードh1に送る経路を見てみると、ノードhからリンク#31を介してルータ3(R3)からリンク#33を経由しノードh1までの経路が描かれる(R3、リンク#31、リンク#33)。
【００７０】
したがって、各リンク別、ルータ別にパケットが通過する回数を計算してみれば、リンク#1は2回、ルータ1(R1)は2回、リンク#2は1回、リンク#3は1回、ルータ3(R3)は3回、リンク#31は3回、リンク#32は1回、リンク#33は1回となって、これは、図９Ｂに実線で表示されている。これに対し、従来の距離基盤CBTによる結果は、図９Ｂに点線で対比して示すように、各リンク別、ルータ別にパケットが通過する回数がリンク#1は2回、ルータ1(R1)は4回、リンク#2は3回、リンク#3は3回、ルータ3(R3)は3回、リンク#31は1回、リンク#32は1回、リンク#33は1回で対比される。これは、既に図５Ｂでも示したとおりである。
【００７１】
このような本発明に係る方向性メトリック基盤CBT加入アルゴリズムは、次のように示すことができる。
【００７２】
Procedure:JoinCBT(h)
Pi(h) ← C0
C(Pi(h)) ← WhoisChild(Pi(h))
while(num(C(Pi(h)))≧max(C(Pi(h)))
Find Ny s.t、direction(h、Ny)<direction(h、Nx)、Nx、Ny∈C(Pi(h))
Find Nx、Nz s.t、direction(Nx、Ny)<direction(Nw Nx)、
Nv、Nw、Nx、Ny∈C(Pi(h))
if(direction(h、Ny)>direction(Nx、Nz))
h Join C(Pi(h))
c(Nx、Nz) Quit C(Pi(h))
c(Nx、Nz) Join C(p(Nx、Nz))
return
else
if(p(h、Ny)==h)
h Join C(Pi(h))
Ny Quit C(Pi(h))
Ny Join C(h)
return
else
Increment i、Pi(h) ← Ny
C(Pi(h)) ← WhoisChild(Pi(h))
end if
end if
end while
h Join C(Pi(h))
【００７３】
このアルゴリズムをもう少し詳細に説明すれば、次の通りである。
【００７４】
Pi(h) ← C0
C(Pi(h)) ← WhoisChild(Pi(h))//
Pi(h) ← C0:任意のノードhがCBTに加入しようとする時、0番目親ノードをコアノードC0にする。
C(Pi(h)) ← WhoisChild(Pi(h)):ノードhは、コアノードC0にコアノードC0の子ノード情報を要請して受信された子ノードの情報をコアノードC0の子ノードに入力する。
while(num(C(Pi(h)))≧max(C(Pi(h))):この際、コアノードC0の子ノード個数が最大収容可能な子数以上である場合には、次の手順を行う。
Find Ny s.t、direction(h、Ny)<direction(h、Nx)、Nx、Ny∈C(Pi(h)):ノードhと任意のノード(ノードNy、ノードNx)間の方向性を計算してノードhと最も近接したノード(Ny)を捜し出す。
Find Nx、Nz s.t、direction(Nx、Ny)<direction(Nw、Nx):コアノードの子ノード中から互いの方向性が最も遠いノードを捜し出す。
if(direction(h、Ny)>direction(Nx、Nz)):加入しようとするノードhと、そのノードhと最も近接したノードNyの方向性がコアノードの子ノード中から最も遠く離れているノードとの方向性より大きいか否かを判断する。
h Join C(Pi(h)):大きい場合には互いに連関性が無いことにより、ノードhを子ノードに加入させる。
c(Nx、Nz) Quit C(Pi(h)):コアノードの子ノードであるNxとNzノードのうち、コアノードから遠く離れたノードをコアノードから脱退させる。
c(Nx、Nz) Join C(p(Nx、Nz)):その脱退させたノードを、NxとNzノードのうち、コアノードに近接したノードの子ノードに加入させる。
else
if(p(h、Ny)==h):ノードhとノードNyの中からコアノードに近接したノードがノードhであれば、
h Join C(Pi(h)):ノードhをコアノードの子ノードに加入させ、
Ny Quit C(Pi(h)):ノードyをコアノードの子ノードから脱退させ、
Ny Join C(h):ノードyをコアノードの子ノードに加入させる。
Increment i、Pi(h) ← Ny
C(Pi(h)) ← WhoisChild(Pi(h)):階層を増加させ、またノードyに対する加入過程を進行する。
【００７５】
次に、CBTを再構成するのを察し見る。
【００７６】
任意のノードがCBTに加入した後には、周期的に兄弟ノード、親ノードとハローパケットを送受信することによって、親ノードと子ノード、そして兄弟ノードの状態を確認できる。一定時間ハローパケットを受けられなければ、相手ノードに障害が発生したことと見なす。
【００７７】
兄弟ノードとのハローパケット送受信では、最近受信したマルチキャストパケットの送信番号情報等を有したハローパケットを兄弟ノードと周期的に交換、分析して兄弟ノードとの方向性値計算と親ノードとの通信異常有無を確認する。確認した結果、親ノードとの通信に一時的な異常が発見されれば、最も方向性値が小さい兄弟ノードからパケットの中継を受けることができる。このように兄弟ノードとの周期的な通信でCBTに兄弟ノード間のメッシュ(Mesh)構造を作ることができる。
【００７８】
親ノードとのハローパケット送受信では、最近受信したマルチキャストパケットの送信番号、兄弟ノードとの方向性情報と子ノードが存在する場合、子ノードとの方向性情報などを周期的に親ノードに送信する。合わせて、兄弟ノードの情報と叔父(uncle)ノードの情報を親ノードから受信する。
【００７９】
この際、親ノードより小さい方向性値を示す叔父ノードを発見すれば、叔父ノードに再加入した後、以前の親ノードから脱退する。一方、兄弟ノードとのハローパケット交換で受信したマルチキャストパケットの送信番号を比較して兄弟ノードより小さな送信番号を持っていれば、親ノードとのリンクに障害が発生したことと判断し、兄弟ノードにパケット中継を要請して中継を受ける。一定時間親ノードからハローパケットを受けられなかったり、親ノードとのリンク障害が持続すれば、祖父ノード(図面で、Pi(h)、i=i-1)に再加入する。
【００８０】
また、子ノードから一定時間ハローパケットを受けられなければ、子ノードに障害が発生したことと判断し、孫ノードが再加入できるように一定時間待つ。収容可能な子ノードの数より現在の子数が少ない場合は、自身ノードで受信した子ノードと孫ノードとの方向性を比較し、もっとも大きい方向性値を示す孫ノードを子ノードに再加入させることによって、CBTの階層を減らし、中継遅延時間を減らす。
【００８１】
次に、本発明に係る方向性メトリック基盤のCBTオーバーレイマルチキャストと従来の距離メトリック基盤のCBTオーバーレイマルチキャストを行って、コアノードから一つのマルチキャストパケットをCBT全体に中継する過程で該当ルータにパケットが集中する情報を比較して性能を評価する。
【００８２】
大きく２種類に分けて、CBT全体の性能に影響を及ぼすコアノードが連結したルータの処理パケット数と、コアノード他の最も多いパケットを処理するルータの処理パケット数を算出して性能を評価する。
【００８３】
表２〜表５は、CBTに加入する実験での加入ノードと加入順序を示す表である。
【００８４】
【表２】
2004304799.tif 000004
【００８５】
【表３】
2004304799.tif 000005
【００８６】
【表４】
2004304799.tif 000006
【００８７】
【表５】
2004304799.tif 000007
【００８８】
実験過程は、次の各ネットワークでマルチキャストグループ会員ノードの数を増加させながら実験する。グループ会員ノードは、rand()関数を用いて表２〜表５のように任意に選択し、また任意の順序でCBTに加入する。各会員ノード数に対して5回の実験を繰り返して反復実験したオーバーレイマルチキャスト結果に対する平均を求めて、実験結果値に使用する。
【００８９】
実験１：リングトポロジーネットワーク上での比較
【００９０】
図１０は、リングトポロジーネットワークを示す。図１０のような41個のルータと終端ノードから構成されたリングトポロジーネットワークで、表２〜表５における順序で10個、15個、20個、25個の終端ノードがCBTに加入する場合を各々実験した。
【００９１】
図１１Ａは、表２中の実験１について、距離メトリック基盤で構成されたCBTを示し、図１１Ｂは、本発明に係る方向性メトリック基盤で構成されたCBTの例を示す。図１１Ａ及び図１１Ｂを参照すれば、従来の距離CBTより本発明の方向性CBTのほうが、階層が一つ小さいことが分かる。これに伴いパケットをコピーして伝送する中継過程が短縮され、それだけ速い伝送が可能となる。
【００９２】
図１２は、図１１Ａ及び図１１Ｂで終端ノードと連結した各ルータで処理するパケット数を比較したグラフである。図面で点線は、距離基盤CBTを示し、実線は、方向性基盤CBTを示す。図１２を参照すれば、距離CBTではコアノードとノード1が連結したルータにパケットが集中することが分かる。これに比べて方向性CBTは、比較的緩慢な処理パケット数を示す。これは、図１１Ａの距離CBTで実際には各ノードの位置とCBT上のノード位置が一致しないことによって、ノード1でノード32と37に中継されたパケットが、以前のコアノードからノード1にパケットを伝送した経路に戻るためである。
【００９３】
図１３Ａ及び図１３Ｂは、実験１で各ノードがCBTに加入する場合を実験した結果の平均処理パケット数を示すグラフである。図１３Ａは、コアノードと連結したルータで加入ノード数別平均処理パケット数を示し、図１３Ｂは、最大パケットを処理するルータのノード数別平均処理パケット数を示す。図１３Ａ及び図１３Ｂのグラフで、コアノードが連結したルータで処理するパケットの数が距離CBTより方向性CBTで約38%減少し、最大パケットを処理するルータの処理パケット数も約10%減少することが分かる。特に、CBTマルチキャスト性能全体に影響を及ぼすコアノードが連結したルータの処理パケット数の減少により、より安定したマルチキャスト通信を期待できる。
【００９４】
実験２：線形トポロジーネットワーク上での比較
【００９５】
図１４は、線形トポロジーネットワークを示す。図１４のような41個のルータと終端ノードで構成された線形トポロジーネットワークで実験１の実験と同じ方法で実験した。
【００９６】
図１５Ａ及び図１５Ｂは、実験２で各ノード別CBT加入実験結果の平均処理パケット数を示すグラフである。図１５Ａは、コアノードと連結したルータで加入ノード数別平均処理パケット数を示し、図１５Ｂは、最大パケットを処理するルータのノード数別平均処理パケット数を示す。図１５Ａ及び図１５Ｂを参照すれば、実験１と同様に、コアノードが連結したルータで処理するパケット数が距離CBTより方向性CBTで平均約42%減少し、最大パケットを処理するルータの処理パケット数も平均約10%減少する結果が分かる 。
【００９７】
実験３：星形トポロジーネットワーク上での比較
【００９８】
図１６は、星形トポロジーネットワークを示す。図１６のように41個のルータと終端ノードで構成される星形トポロジーネットワークで、実験１と同じ方法で実験した。図１７Ａ及び図１７Ｂは、実験３で各ノード別CBT加入実験結果の平均処理パケット数を示すグラフである。図１７Ａは、コアノードと連結したルータで加入ノード数別平均処理パケット数を示し、図１７Ｂは、最大パケットを処理するルータのノード数別平均処理パケット数を示す。図１７Ａ及び図１７Ｂを参照すれば、コアノードが連結したルータで処理するパケット数が距離CBTより方向性CBTで平均約34%減少し、最大パケットを処理するルータの処理パケット数も平均約25%減少する結果とともに、CBTの階層が減る効果を得ることができる。
【図面の簡単な説明】
【００９９】
【図１Ａ】マルチキャストルータを用いたIPマルチキャストを行うネットワークの形状図。
【図１Ｂ】ユニキャストルータを用いたオーバーレイマルチキャストを行うネットワークの形状図。
【図２】同じマルチキャストグループに属したノードからなるネットワークトポロジー。
【図３Ａ】図２のネットワークトポロジーでコアノードがC0である距離メトリック基盤CBTに基づき、ノードa、b、hの順序で加入する場合を説明するための図。
【図３Ｂ】図２のネットワークトポロジーでコアノードがC0である距離メトリック基盤CBTに基づき、ノードa、b、hの順序で加入する場合を説明するための図。
【図３Ｃ】図２のネットワークトポロジーでコアノードがC0である距離メトリック基盤CBTに基づき、ノードa、b、hの順序で加入する場合を説明するための図。
【図３Ｄ】図２のネットワークトポロジーでコアノードがC0である距離メトリック基盤CBTに基づき、ノードa、b、hの順序で加入する場合を説明するための図。
【図４】図３ＣのCBTにおけるマルチキャストパケットの中継経路図。
【図５Ａ】C0、a、b、h、h1のノードで構成された距離メトリック基盤のCBT構成図。
【図５Ｂ】図５Ａのネットワークにおいて各リンク及びルータで処理するパケットの数を示すグラフ。
【図６Ａ】コアノードを基準に隣接する二つのノード間の位置関係を示す図。
【図６Ｂ】コアノードを基準に隣接する二つのノード間の位置関係を示す図。
【図６Ｃ】コアノードを基準に隣接する二つのノード間の位置関係を示す図。
【図６Ｄ】コアノードを基準に隣接する二つのノード間の位置関係を示す図。
【図７Ａ】本発明に係るコアノードがC0である方向性メトリック基盤CBTに基づき、ノードa、b、hの順序で加入する場合を説明するための図。
【図７Ｂ】本発明に係るコアノードがC0である方向性メトリック基盤CBTに基づき、ノードa、b、hの順序で加入する場合を説明するための図。
【図７Ｃ】本発明に係るコアノードがC0である方向性メトリック基盤CBTに基づき、ノードa、b、hの順序で加入する場合を説明するための図。
【図８】本発明に係る方向性メトリック基盤CBTでのマルチキャストパケットの中継経路図。
【図９Ａ】本発明に係るコアノードがC0である方向性メトリック基盤CBTに基づき、ノードa、b、h、h1の順序で加入する場合を説明するための図。
【図９Ｂ】本発明に係るコアノードがC0である方向性メトリック基盤CBTに基づき、ノードa、b、h、h1の順序で加入する場合を説明するための図。
【図１０】リングトポロジーネットワーク構成図。
【図１１Ａ】表２で実験１に対する距離メトリック基盤CBT構成図。
【図１１Ｂ】表２で実験１に対する本発明に係る方向性メトリック基盤CBT構成図。
【図１２】図１１Ａ及び図１１Ｂで終端ノードと連結した各ルータで処理するパケット数を比較したグラフ。
【図１３Ａ】実験１で各ノードがCBTに加入する場合を実験した結果の平均処理パケット数を示すグラフ。
【図１３Ｂ】実験１で各ノードがCBTに加入する場合を実験した結果の平均処理パケット数を示すグラフ。
【図１４】線形トポロジーネットワークの構成図。
【図１５Ａ】実験２で各ノード別CBT加入実験結果の平均処理パケット数を示すグラフ。
【図１５Ｂ】実験２で各ノード別CBT加入実験結果の平均処理パケット数を示すグラフ。
【図１６】星形トポロジーネットワークの構成図。
【図１７Ａ】実験３で各ノードがCBTに加入する場合を実験した結果の平均処理パケット数を示すグラフ。
【図１７Ｂ】実験３で各ノードがCBTに加入する場合を実験した結果の平均処理パケット数を示すグラフ。
【図１Ａ】
2004304799.tif 000008
【図１Ｂ】
2004304799.tif 000009
【図２】
2004304799.tif 000010
【図３Ａ】
2004304799.tif 000011
【図３Ｂ】
2004304799.tif 000012
【図３Ｃ】
2004304799.tif 000013
【図３Ｄ】
2004304799.tif 000014
【図４】
2004304799.tif 000015
【図５Ａ】
2004304799.tif 000016
【図５Ｂ】
2004304799.tif 000017
【図６Ａ】
2004304799.tif 000018
【図６Ｂ】
2004304799.tif 000019
【図６Ｃ】
2004304799.tif 000020
【図６Ｄ】
2004304799.tif 000021
【図７Ａ】
2004304799.tif 000022
【図７Ｂ】
2004304799.tif 000023
【図７Ｃ】
2004304799.tif 000024
【図８】
2004304799.tif 000025
【図９Ａ】
2004304799.tif 000026
【図９Ｂ】
2004304799.tif 000027
【図１０】
2004304799.tif 000028
【図１１Ａ】
2004304799.tif 000029
【図１１Ｂ】
2004304799.tif 000030
【図１２】
2004304799.tif 000031
【図１３Ａ】
2004304799.tif 000032
【図１３Ｂ】
2004304799.tif 000033
【図１４】
2004304799.tif 000034
【図１５Ａ】
2004304799.tif 000035
【図１５Ｂ】
2004304799.tif 000036
【図１６】
2004304799.tif 000037
【図１７Ａ】
2004304799.tif 000038
【図１７Ｂ】
2004304799.tif 000039