(57)【要約】【課題】アクセスネットワークとコアネットワークという２つの階層で構成されたネットワークで、ユーザ間遅延分散を削減する転送経路を設定する。【解決手段】本発明は、エッジノードはアクセスネットワーク内での遅延値に関する集約情報を保持し、マルチキャスト経路計算を行うノードに遅延値を配送し、コアネットワーク内のノードは、通過する情報が被る遅延を計測した情報をマルチキャスト転送経路を計算するノードに通知し、当該ノードは２つの遅延情報を保持し、計算された転送経路は、保持した遅延情報で送信者と受信者の間で被る遅延の受信者同士の差を削減するマルチキャスト転送経路を計算する。【選択図】　　　図１
2004072534.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークが階層的に構成された場合におけるマルチキャスト通信における、端末を収容するアクセスネットワークとアクセスネットワーク間を接続するコアネットワークにおけるマルチキャスト転送経路計算方法において、
階層化されたコンピュータネットワークに存在するノードにおいて、情報を配送するマルチキャスト通信による配送の際に使用する転送経路を計算するとき、
前記アクセスネットワークと前記コアネットワークとを接続するエッジノードにおいて、自身に接続する該アクセスネットワークに存在する受信者の端末に配送するときに情報が経由する経路で被る遅延を該受信者の端末毎に測定し、
測定された遅延値から、前記アクセスネットワーク内で被る遅延値を計算し、
計算された遅延値に関する集約情報として保持し、
マルチキャスト経路計算を行うノードに計算された前記遅延値を配送し、
前記コアネットワーク内のノードにおいて、自身を通過する情報が被る遅延を計測し、
計測された情報を、マルチキャスト転送経路を計算する機能を有するノードに通知し、
前記マルチキャスト転送経路を計算する機能を有するノードにおいて、前記エッジノードと前記コアネットワーク内のノードから配布された２つの遅延情報を保持し、
計算された転送経路は、保持した前記遅延情報に基づいて、送信者の端末と前記受信者の端末の間で被る遅延の、受信者の端末同士の差を削減するマルチキャスト転送経路を計算することを特徴とするマルチキャスト転送経路計算方法。
【請求項２】
前記アクセスネットワークと前記コアネットワークとを接続する前記エッジノードにおいて、
前記エッジノード自身に接続する前記アクセスネットワークに存在する受信者の端末に配送するときに、情報が経由する経路で被る遅延を該受信者の端末毎に測定し、
測定された遅延値の最大値に関する集約情報として保持する請求項１記載のマルチキャスト転送経路計算方法。
【請求項３】
前記アクセスネットワークと前記コアネットワークとを接続する前記エッジノードにおいて、
前記エッジノード自身に接続する前記アクセスネットワークに存在する受信者の端末に配送するときに情報が経由する経路で被る遅延を該受信者の端末毎に測定し、
測定された遅延値の平均値を遅延に関する集約情報として保持する請求項１記載のマルチキャスト転送経路計算方法。
【請求項４】
前記マルチキャスト転送経路を計算するノードにおいて、
マルチキャストグループの受信者の端末が存在するアクセスネットワークへの出口となる出口エッジノードから該マルチキャストグループにデータを送信する送信者の端末が存在するアクセスネットワークからの入口となる入口エッジノードまで被る遅延の最小値を該出口エッジノード毎に計算し、
各前記出口エッジノードが配布した、自ノードと接続するアクセスネットワークにおける遅延の集約情報と計測された前記遅延の最小値とを足し合わせ、その最小値を探索し、
探索された最小値を設定するマルチキャスト転送経路が実現すべき遅延と決定する請求項１乃至３記載のいずれか１項記載のマルチキャスト転送経路計算方法。
【請求項５】
前記マルチキャスト転送経路が送信者の端末と前記出口エッジノードを結ぶ転送経路を出口エッジノード毎に計算し、
計算された前記マルチキャスト転送経路が実現すべき遅延値から前記出口エッジノードに接続するアクセスネットワークにおけるマルチキャストグループに関する遅延の集約情報を引いた値に、許容する受信者の端末間の遅延の差異を加えたものを上限に、引いたものを下限とし、その間に入る遅延値を実現する経路を転送経路の候補として保持し、
保持した候補の中から、選考して時点で転送経路として採択されている経路と重なるリンク数が最も多い候補と転送経路として採択する請求項４記載のマルチキャスト転送経路計算方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、マルチキャスト転送経路計算方法に係り、特に、ネットワークが階層的に構成された場合におけるマルチキャスト通信において、端末を収容するアクセスネットワークとアクセスネットワーク間を結ぶコアネットワークにおけるマルチキャスト転送経路計算方法に関する。
【０００２】
【従来の技術】
コンピュータネットワーク上で、動画や音声を特定多数のユーザに配送するマルチキャスト通信が注目を集めている。この通信方式は、送信者と各受信者を結ぶ経路のうち、経路が分かれる部分において情報をコピーし、各受信者へと情報を配信する。特定多数の受信者へ送信者と１対１で通信を行うユニキャスト通信を用いて情報を配送した場合、受信者の数だけ送信者は情報を用意する必要がある。よって、マルチキャスト通信を用いることにより、ネットワーク内の情報量は減少する。マルチキャスト通信では、特定多数の受信者をマルチキャストグループと呼ばれる管理単位で管理を行い、マルチキャストグループに対して１つの転送経路が設定される。この転送経路は、送信者からマルチキャストグループに属するすべての受信者を接続するように設定される。また、あるマルチキャストグループへと転送される情報を取得したいユーザは、マルチキャストグループに参加することで情報を取得する。このため、ユーザの参加状況に応じて転送経路は変化する。
【０００３】
マルチキャスト通信を用いるアプリケーションとして、テレビ会議やオンラインゲーム、映画やテレビ等の動画配送があげられる。テレビ会議やオンラインゲームは複数のユーザがデータの受信者となり、同時に受信したデータに対し、応答を返すため送信者ともなる。このようなアプリケーションでは、あるユーザが送信したデータに対し、各ユーザが応答する時間を同程度とすることで、各ユーザの発言機会を均等にする技術が注目を集めている。
【０００４】
応答時間の均等化を実現する手段としては、送信者から各受信者までの情報の転送経路を全受信者とも同等の遅延を被るように設計するものがある。ここで、情報が各受信者まで到達する時に、転送経路上で被る情報の転送遅延の差異をユーザ間遅延分散と呼ぶ。現在この問題を扱う論文としては、１）「Ｇ．Ｒｏｕｓｋａｓ，他“Ｍｕｌｔｉｃａｓｔ　Ｒｏｕｔｉｎｇ　ｗｉｔｈ　Ｅｎｄ−ｔｏ−Ｅｎｄ　Ｄｅｌａｙ　ａｎｄ　Ｄｅｌａｙ　Ｖａｒｉａｔｉｏｎ　Ｃｏｎｓｔｒａｉｎｔｓ，”　ＩＥＥＥ　Ｊｏｕｒｎａｌ　ｏｎ　Ｓｅｌｅｃｔｅｄ　Ａｒｅａｓ　ｉｎ　Ｃｏｍｍｕｎｉｃａｔｉｏｎ，　Ｖｏｌ　１５，　Ｎｏ．３，　Ａｐｒ．　１９９７」や、２）「Ｐｉ−Ｒｏｎｇ　Ｓｈｅｕ他、“Ａ　Ｆａｓｔ　ａｎｄ　Ｅｆｆｉｃｉｅｎｔ　Ｈｅｕｒｉｓｔｉｃ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｈｅ　Ｄｅｌａｙ−ａｎｄ　Ｅｆｆｉｃｉｅｎｔ　Ｈｅｕｒｉｓｔｉｃ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｈｅ　Ｄｅｌａｙ−ａｎｄ　Ｄｅｌａｙ　Ｖａｒｉａｔｉｏｎ　Ｂｏｕｎｄ　Ｍｕｌｔｉｃａｓｔ　Ｔｒｅｅ　Ｐｒｏｂｌｅｍ，　”ＩＥＥＥ　ＩＣＣ，　２００１」が発表されている。
上記の１）の論文は、この問題を転送経路の選択という観点で解決した最初の論文であり、２）の論文は、１）の論文で提案された方式より計算量の少ない方式を提案し、経路の計算時間を短縮している。
【０００５】
これらの論文では、前記ユーザ間遅延分散が最小となる状況下で計算目標であるマルチキャスト転送経路は、経路を構成するリンクに付与されたコストの総和を可能な限り小さくすることを目的としている。前述の論文で提案されているアルゴリズムでは、マルチキャスト情報を転送する経路を計算するノードガ受信者までの全ネットワーク構成を理解している状況下で動作する。現在提供されているコンピュータネットワークは、ユーザを収容するアクセスネットワークとアクセスネットワーク間を繋ぐコアネットワークという大別して２階層の階層構成をとる。コアネットワークとアクセスネットワークの間は、エッジノードと呼ばれるノードで接続され、あるアクセスネットワークＡから別のアクセスネットワークＢへ情報を転送するとき、情報はアクセスネットワークＡとコアネットワークを接続するエッジノードを経由し、コアネットワークを介してアクセスネットワークＢとコアネットワーク間に存在するエッジノードを経由して転送される。
【０００６】
エッジノードは、他のエッジノード間で形成される転送経路の一部となる場合、前述の転送経路上を流れる情報を中継する機能も有する。
【０００７】
コアネットワークは、エッジノードとデータの中継のみを行う中継ノードから構成される。
【０００８】
【発明が解決しようとする課題】
しかしながら、上記の従来の技術では、以下のような問題がある。
【０００９】
以下、コアネットワークにおけるノードは、エッジノードと中継ノードを含むものとする。各アクセスネットワークに存在する転送経路計算を行うノードは、自身が属するネットワークの構成情報のみを保持している。コアネットワークに存在するノードは、各ネットワークの構成情報を集約した情報を保持しており、詳細なネットワーク構成情報を保持しない。これは、コンピュータネットワーク全体を構成するノード、並びにリンクの数が大きいため、各ノードが全ノード、並びにリンクの情報を保持することが困難であるためである。このため、転送経路を計算するノードはすべてネットワーク構成を知ることは実現上困難である。本発明は、上記の点に鑑みなされたもので、アクセスネットワークとコアネットワークという２つの階層で構成されたネットワークで、各アクセスネットワークにおける転送遅延に関する集約情報が利用できる状況下でアクセスネットワークから提供された集約情報を元に、コアネットワークにおいて、ユーザ間遅延分散を削減する転送経路を設定することが可能なマルチキャスト転送経路計算方法を提供することを目的とする。
【００１０】
また、本発明の目的は、計算された経路が送信者から全受信者に送信するために必要な最小遅延を実現することが可能なマルチキャスト転送経路計算方法を提供することである。
【００１１】
また、更なる本発明の目的は、計算目標であるマルチキャスト転送経路を構成するノードやリンクに付与されたコストの総和が可能な限り小さくなるような転送経路を計算することが可能なマルチキャスト転送経路計算方法を提供することである。
【００１２】
【課題を解決するための手段】
本発明は、ネットワークが階層的に構成された場合におけるマルチキャスト通信における、端末を収容するアクセスネットワークとアクセスネットワーク間を接続するコアネットワークにおけるマルチキャスト転送経路計算方法において、階層化されたコンピュータネットワークに存在するノードにおいて、情報を配送するマルチキャスト通信による配送の際に使用する転送経路を計算するとき、アクセスネットワークとコアネットワークとを接続するエッジノードにおいて、自身に接続する該アクセスネットワークに存在する受信者の端末に配送するときに情報が経由する経路で被る遅延を該受信者の端末毎に測定し、
測定された遅延値から、アクセスネットワーク内で被る遅延値を計算し、
計算された遅延値に関する集約情報として保持し、
マルチキャスト経路計算を行うノードに計算された遅延値を配送し、
コアネットワーク内のノードにおいて、自身を通過する情報が被る遅延を計測し、
計測された情報を、マルチキャスト転送経路を計算する機能を有するノードに通知し、
マルチキャスト転送経路を計算する機能を有するノードにおいて、エッジノードとコアネットワーク内のノードから配布された２つの遅延情報を保持し、
計算された転送経路は、保持した遅延情報に基づいて、送信者の端末と受信者の端末の間で被る遅延の、受信者の端末同士の差を削減するマルチキャスト転送経路を計算する。
【００１３】
また、本発明は、アクセスネットワークとコアネットワークとを接続するエッジノードにおいて、
エッジノード自身に接続するアクセスネットワークに存在する受信者の端末に配送するときに、情報が経由する経路で被る遅延を該受信者の端末毎に測定し、
測定された遅延値の最大値に関する集約情報として保持する。
【００１４】
また、本発明は、アクセスネットワークとコアネットワークとを接続するエッジノードにおいて、
エッジノード自身に接続するアクセスネットワークに存在する受信者の端末に配送するときに情報が経由する経路で被る遅延を該受信者の端末毎に測定し、
測定された遅延値の平均値を遅延に関する集約情報として保持する。
【００１５】
また、本発明は、マルチキャスト転送経路を計算するノードにおいて、
マルチキャストグループの受信者の端末が存在するアクセスネットワークへの出口となる出口エッジノードから該マルチキャストグループにデータを送信する送信者の端末が存在するアクセスネットワークからの入口となる入口エッジノードまで被る遅延の最小値を該出口エッジノード毎に計算し、
各出口エッジノードが配布した、自ノードと接続するアクセスネットワークにおける遅延の集約情報と計測された遅延の最小値とを足し合わせ、その最小値を探索し、
探索された最小値を設定するマルチキャスト転送経路が実現すべき遅延と決定する。
【００１６】
また、本発明は、マルチキャスト転送経路が送信者の端末と出口エッジノードを結ぶ転送経路を出口エッジノード毎に計算し、
計算されたマルチキャスト転送経路が実現すべき遅延値から出口エッジノードに接続するアクセスネットワークにおけるマルチキャストグループに関する遅延の集約情報を引いた値に、許容する受信者の端末間の遅延の差異を加えたものを上限に、引いたものを下限とし、その間に入る遅延値を実現する経路を転送経路の候補として保持し、
保持した候補の中から、選考した時点で転送経路として採択されている経路と重なるリンク数が最も多い候補と転送経路として採択する。
【００１７】
上記のように、本発明のマルチキャスト転送経路設定手法は、階層構成をとるネットワークにおいて、ユーザ間遅延分散の削減を実現するためのものであり、本発明により計算された経路は、アクセスネットワーク内で計算された、当該ネットワークのエッジノードと当該ネットワーク内に存在する計算対象となるマルチキャストグループの受信者までの遅延最大値と、コアネットワーク内のノードで記録された、自身で情報が被る遅延値からユーザ間転送遅延を削減するために計算されることが第１の特徴である。
【００１８】
また、送信者が存在するアクセスネットワークに接続するエッジノードからマルチキャストグループに参加する受信者のうち最もエッジノードから遠い受信者までの転送遅延を、該当マルチキャストグループ宛に送られる情報が達成すべき目標遅延値とすることが第２の特徴である。
【００１９】
さらに、発見された経路のうち、最も経由するリンク数が少ないものを採択することが第３の特徴である。
【００２０】
本発明は、前述の従来の技術とは、対象とするネットワークが単一ネットワークから階層化されたネットワークとなることが大きく異なる。このため、ユーザ間分散遅延の削減のために従来技術で知る必要のあったコンピュータネットワーク全体のノードの位置や、リンクの接続関係等を保持しなくても、ユーザ間遅延分散を削減する転送経路を構築できるところが大きく異なる。
【００２１】
【発明の実施の形態】
以下、図面と共に本発明の実施の形態を説明する。
【００２２】
図１は、メッシュ形態のネットワーク構成図である。
【００２３】
本発明は、テレビ会議、オンラインゲーム、株式情報等、通常の対話のように相互に応答しあうような対話型アプリケーションを対象としている。このようなアプリケーションを実現する際に、転送経路は、１送信者の端末に対し特定多数の受信者の端末へと向かって設定される。
【００２４】
この転送経路の形状は、ｐｏｉｎｔ−ｔｏ−ｍｕｌｔｉｐｏｉｎｔと呼ばれる。このような転送経路が各アプリケーションユーザに対し設定されることで、これらのアプリケーションが実現される。ここでは、この形態をメッシュ形態と呼ぶ。
【００２５】
図２は、経路共有形態のネットワーク構成図である。
【００２６】
同図に示すネットワークでは、各ユーザから情報を収集し、これらの情報を管理するサーバから同図に示すような転送経路を設定し、各ユーザに配送することで実現される。この場合、マルチキャスト転送経路は、情報管理サーバから各受信者の端末に向けて設定される。ここでは、この形態を経路共有形態と呼ぶ。
【００２７】
このようなアプリケーションは、コンピュータネットワーク上で実現される。コンピュータネットワークは、ユーザを収容するアクセスネットワークとアクセスネットワークを接続するコアネットワークから構成される。このようなネットワーク形態を図３に示す。
【００２８】
各受信者の端末に配送される情報は、送信者の端末から当該送信者の端末が属するアクセスネットワーク１０Ａとコアネットワーク２０を接続するエッジノード３０Ａとコアネットワーク２０、さらに、コアネットワーク２０と受信者の端末が属するアクセスネットワーク１０Ｂ，１０Ｃ，１０Ｄを接続するエッジノード３０Ｂ，３０Ｃ、３０Ｄを経由し、受信者の端末まで配送される。ここで示したエッジノード３０うち、前者（エッジノード３０Ａ）を入口エッジノード、後者（エッジノード３０Ｂ，３０Ｃ，３０Ｄ）を出口エッジノードと呼ぶ。
【００２９】
マルチキャストでは受信者の端末は複数存在するため、その転送経路は、木構造をとる。このような木構造の分岐点において、配送情報はコピーされ、各受信者の端末に配送される。
【００３０】
このような転送形態に対し、ユーザ間転送遅延分散を削減する方法として、計算対象であるマルチキャストグループの転送経路で被る遅延を各受信者の端末とも同程度にする方法がある。これらの転送経路は、コアネットワークを構成するノード、特に、当該マルチキャストグループに対する入口エッジノードや、コアネットワーク、もしくはアクセスネットワーク中に用意される経路計算専用のノードで計算される。計算結果は、転送経路を設定するノードに通知される。転送経路が設定されるノードとしては、入口エッジノードや出口エッジノード、もしくは、コアネットワーク、もしくは、アクセスネットワーク中に存在するノード設定の指示を行う専用のノードがあげられる。経路計算を行うノードや経路設定を行うノードは、ネットワーク管理者の管理方針に依存して決定される。
【００３１】
ユーザ間遅延分散を削減するためには、経路計算を行うノードが送信者の端末から各受信者の端末までの転送遅延を把握する必要がある。転送遅延は、送信者の端末から入口エッジノードまでの遅延、入口エッジノードから各受信者の端末が属するアクセスネットワークへの出口エッジノードまでの遅延並びに、出口エッジノードから各受信者の端末までの遅延、並びに、出口エッジノードから各受信者の端末までの遅延で構成される。このうち、各受信者の端末間で生じる遅延差に関係する遅延は、入口エッジノードから各受信者の端末が属するアクセスネットワークへの出口エッジノードまでの遅延と出口エッジノードから各受信者の端末までの遅延である。本発明では、この２つの遅延を考慮して経路の計算を行う。
【００３２】
まず、各受信者の端末が属するアクセスネットワークへの出口エッジノードまでの遅延について考える。
【００３３】
アクセスネットワークの地理的規模、並びにユーザ密度は、各アクセスネットワーク共に異なる。また、同一アクセスネットワークに属する受信者の端末は、存在する位置が受信者の端末毎に異なる。このため、出口エッジルータから各受信者の端末まで情報を送信するために必要な遅延は、受信者の端末毎に異なる。
本発明では、これらの異なる遅延情報をある１つの情報に集約し、コアネットワークにおける経路を計算するノードに通知する。
【００３４】
図４は、本発明の一実施の形態における集約情報を説明するための図である。
この集約情報としては、
ケース１）　出口エッジノードから最も大きい遅延を被る受信者の端末までの遅延；
集約遅延ｄ（ｋ）＝Ｍａｘ｛ｄ（Ｒｉ）｝
ケース２）　出口エッジノードから各受信者の端末に向けて送信される情報が被る遅延値の平均値；
があげられる。
【００３５】
但し、Ｒｉはアクセスネットワークａに属する計算対象（マルチキャストグループの参加者）であり、ｄ（Ｒｉ）は、出口エッジノードから受信者の端末Ｒｉまでの遅延を示す。
【００３６】
図５は、本発明の一実施の形態における情報収集機構を説明するための図である。同図において、Ｒｉは、アクセスネットワークに属する計算対象（マルチキャストグループの参加者）であり、Ｄ（Ｒｉ）は、出口エッジノードから受信者の端末Ｒｉまでの遅延であり、ｍｉは、受信者の端末Ｒｉに情報が到着した時刻を示す。
【００３７】
出口エッジノードは、自身と接続するアクセスネットワークに関するこれらの情報を管理する。情報を収集する機構としては、
１）　既存の経路計算用プロトコル（ルーチングプロトコル）；
２）　ネットワーク管理者が独自に用意した情報収集機構；
等があげられる。
【００３８】
上記の２）の例としては、配送される情報にタイムスタンプを設け、出口エッジノードを通過した時刻をタイムスタンプに記録し、各受信者の端末で出口エッジノードからの転送遅延を計測し、出口エッジノードに直接計測情報を送信するといった方法があげられる。
【００３９】
収集された集約情報は、出口エッジノードがコアネットワーク内に存在する経路計算を行うノードに通知する。このような情報を通知する方法としては、
１）　既存の経路計算用プロトコル（ルーングプロトル）；
２）　ネットワーク管理者が独自に用意した情報通機構；
等があげられる。
【００４０】
次に、入口エッジノードから出口エッジノードまでの遅延について考える。
【００４１】
送信者の端末から送信対象のマルチキャストグループに参加する受信者の端末までの転送遅延を均等にするためには、アクセスネットワークで収集された遅延に関する集約情報に応じて、入口エッジノードから出口エッジノードまでの設定目標遅延は、出口エッジノード毎に設定する必要がある。この設定遅延を計算するアルゴリズムを以下に述べる。
【００４２】
まず、経路計算を行うノードは、計算対象のマルチキャストグループに対する入口エッジノードから各出口エッジノードｋまで情報を配送するのに必要な遅延の最小値Ｉ（ｋ）を調査する。この調査に必要な情報として、各ノードで情報が被る遅延に関する情報があげられる。現在存在する、このようなノードは、この遅延を計測する能力を有する。このため、各出口エッジノードまでの遅延の最小値に対する調査の方法としては、
１）　経路計算を行うノードが独自にコアネットワーク内に存在するノードから各ノードで情報が被る遅延に関する情報を収集する；
２）　情報収集用のノードがこれらの情報を収集し、計算を行うノードに通知する；
があげられる。
【００４３】
図６は、本発明の一実施の形態における遅延値の算出方法を説明するための図である。計算された各出口エッジノードｋに対する最小遅延Ｉ（ｋ）と当該エッジノードが保持する、自身配下のアクセスネットワークにおける当該マルチキャストグループに関する転送遅延の集約情報を足し合わせた値を算出する。この算出値のうち、最小のものが、全受信者の端末に送信するときに必要な遅延値の最小値となる。よって、この値をマルチキャスト転送経路が実現すべき遅延値Δとして設定する。即ち、
Δ＝ｍｉｎ｛ｄ（ｋ）＋Ｉ（ｋ）｝
となる。
【００４４】
マルチキャスト転送経路の達成目標となる遅延値Δが設定されたことで、入口エッジノードから各出口エッジノードまで情報を転送するのに被る目標遅延値δ（ｋ）が計算される。即ち、
δ（ｋ）＝Δ−ｄ（ｋ）
となる。経路計算を行うノードは、入口エッジノードから出口エッジノードまで転送遅延がδ（ｋ）である経路を探索する。但し、転送遅延がδ（ｋ）に等しい経路を探すのは困難であるため、転送経路が満たすべき遅延値が
δ（ｋ）−α≦ΣＤ（ｉ）≦δ（ｋ）＋α
を満たすような経路を探索する。ここでは、αは、アプリケーションで許容するユーザ分散遅延の値である。また、ΣＤ（ｉ）は、配送情報が検索対象となる経路を通ることで被る遅延である。
【００４５】
経路検索法の例としては、考えられる経路を全て検索して、前述の遅延条件を満たす経路を候補として確保する方法である。複数経路が候補として保持された場合、すでに転送経路として採択されている経路と共通するリンクが多い経路を、転送経路として採択する。この例を図７に示す。この例では、ノードＡ，Ｂを経由する経路ＸとノードＣを経由する経路Ｙが候補として検索されている。この場合、経路Ｘに対するΣＤ（ｉ）は、
ΣＤ（ｉ）＝Ｄ（Ａ）＋Ｄ（Ｂ）
であり、経路Ｙに対するΣＤ（ｉ）は、Ｄ（Ｃ）となる。両者が通る経路とすでに転送経路として採択されている検索経路の共通するリンク数を数えると、経路Ｘは、２つ、経路Ｙは０である。よって、採択される経路はＸとなる。この動作をすべて出口エッジノードに対して行う。これらの動作を行った結果作成される転送経路が、階層化されたネットワークにおいてユーザ間遅延を削減するコアネットワーク中で設定される転送経路となる。
【００４６】
最後に、上記のシステムにおける一連の動作を説明する。
【００４７】
図８は、本発明の一実施の形態における一連の動作を説明するための図である。同図における記号や動作の番号と以下の説明は対応するものとする。
【００４８】
まず、各エッジノードは、自身が接続するアクセスネットワーク内に存在する経路計算対象のマルチキャスト通信の受信者の端末までの転送遅延に関する情報を収集する（動作１）。同図の例では、アクセスネットワーク１０Ａ，１０Ｂ，１０Ｃ，１０Ｄのうち、１０Ａには送信者の端末、１０Ｂ，１０Ｃ，１０Ｄには受信者の端末が存在する状況を想定している。よって、入口エッジノードは、３０Ａ、出口エッジノードは、３０Ｂ，３０Ｃ，３０Ｄとなる。出口エッジノード３０Ｂ，３０Ｃ，３０Ｄがそれぞれ、アクセスネットワーク１０Ｂ，１０Ｃ，１０Ｄに存在する受信者の端末の遅延情報を収集する。この動作は各エッジノードで独立に行われる。
【００４９】
収集した情報から、各エッジノードはアクセスネットワーク内で被る遅延の集約情報を計算する（動作２）。これらの情報の収集方法、ならびに計算方法は前述の方法に基づく。集約情報の更新は、アクセスネットワークにおける遅延状況などの変更に伴い、遅延情報の収集機構からもたらされた情報に変化が生じたときに適宜行われる。
【００５０】
各エッジノードは、コアネットワーク内の経路計算を行うノードに向けて、自身が計算した、アクセスネットワークにおける遅延の集約情報を送信する、もしくは、コアネットワーク内で動作する情報収集機構により集約情報が収集される（動作３）。この動作は、各エッジノードが遅延の集約情報を更新したときに適宜行われる。これにより、経路計算を行うノードは新しい遅延情報を保持する。経路計算を行うノードは、保持する各エッジノードからの遅延集約情報を基に本発明の目的である、受信者の端末間の遅延分散の削減を実現する経路を計算する（動作４）。
【００５１】
経路計算を行うノードが計算対象のマルチキャスト通信の入口エッジノードと同じ場合、入口エッジノードは計算結果を用いて情報転送用の経路を設定する。異なる場合は経路計算を行うノードは、該当マルチキャストグループにおける入口エッジノードに計算結果を通知する（動作５）。
【００５２】
結果を受け取った入口エッジノードは結果をもとに経路を設定する（動作６）。
【００５３】
以上の動作を遅延情報に変更が生じるときに行ことにより、情報配送中に常に要求条件を満たすような経路を提供することが可能になる。
【００５４】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【００５５】
【発明の効果】
上述のように、本発明によれば、階層化されたネットワークにおいて、ユーザ間遅延の削減を達成できる。このため、テレビ会議やオンラインゲームなど、各ユーザのあるデータに対する応答時間を同一時刻にすることで、ユーザの発言機会の公平性を要求するアプリケーションに対し、その要求条件を達成することが可能となる。
【００５６】
また、本発明によれば、コンピュータネットワーク全体の情報を保持することなく、上記の要求条件を達成することができる。よって、従来の方式で必要であった経路計算ノードが保持する情報量の削減も可能にする。このため、本発明を実現する際に要求されるコンピュータの性能はネットワークの規模に依存せず、大規模なネットワークでもアプリケーションの提供を可能にする。
【図面の簡単な説明】
【図１】メッシュ形態のネットワーク構成図である。
【図２】経路共有形態のネットワーク構成図である。
【図３】本発明の一実施の形態におけるネットワーク構成図である。
【図４】本発明の一実施の形態における集約情報を説明するための図である。
【図５】本発明の一実施の形態における情報収集機能を説明するための図である。
【図６】本発明の一実施の形態における遅延値の算出方法を説明するための図である。
【図７】本発明の一実施の形態における転送経路の採択方法を説明するための図である。
【図８】本発明の一実施の形態における一連の動作を説明するための図である。
【符号の説明】
１０　アクセスネットワーク
２０　コアネットワーク
３０　エッジノード
【図１】
2004072534.tif 000003
【図２】
2004072534.tif 000004
【図３】
2004072534.tif 000005
【図４】
2004072534.tif 000006
【図５】
2004072534.tif 000007
【図６】
2004072534.tif 000008
【図７】
2004072534.tif 000009
【図８】
2004072534.tif 000010