ノードおよび経路計算方法
【課題】マルチエリアネットワークの管理を容易にする。
【解決手段】経路算出部1aは、例えば、始点のノード1から終点のノード5に至る経路を算出する。記憶部1bは、経路算出部1aの算出する経路が通過するマルチエリアネットワークのエリアA〜Dを示す通過エリアリストを記憶する。経路算出部1aは、始点のノード1から終点のノード5に至る経路を算出する際、記憶部1bの通過エリアリストを参照し、同じエリアを複数回通過する経路を経路算出対象から除外する。
【解決手段】経路算出部1aは、例えば、始点のノード1から終点のノード5に至る経路を算出する。記憶部1bは、経路算出部1aの算出する経路が通過するマルチエリアネットワークのエリアA〜Dを示す通過エリアリストを記憶する。経路算出部1aは、始点のノード1から終点のノード5に至る経路を算出する際、記憶部1bの通過エリアリストを参照し、同じエリアを複数回通過する経路を経路算出対象から除外する。
【発明の詳細な説明】
【技術分野】
【0001】
本件は、マルチエリアネットワークに設けられるノードおよび経路計算方法に関する。
【背景技術】
【0002】
複数のエリアに分割されたネットワークでは、エリア間ルーティングプロトコルが用いられる。例えば、エリア間ルーティングプロトコルに参加するノードは、エリア内で交換されているエリア内ルーティングプロトコルの情報を、エリア間ルーティングプロトコルのルーティングドメインに通知する。これにより、各エリアのノードは、他のエリアのネットワーク状態を把握することが可能になり、複数のエリアを跨る経路の算出が可能になる。
【0003】
図20は、エリア内ルーティングを説明する図である。図20には、マルチエリアネットワークが示してある。マルチエリアネットワークは、エリアA〜エリアDを有している。エリアAはノードN31〜N36を有し、エリアBはノードN10,N11を有し、エリアCはノードN21を有し、エリアDはノードN40,N41を有している。各ノード間に示す数字は、リンクコストを示している。
【0004】
マルチエリアネットワークでは、エリア毎にエリア内ルーティングプロトコルが動作する。エリア内ルーティングプロトコルが動作する全てのノードは、各ノードのリンク情報をエリア内全てのノードへ通知する。これによって、エリア内の全てのノードは、エリア内のトポロジーを把握することができる。
【0005】
図21は、エリア間ルーティングを説明する図である。図21において、図20と同じものには同じ符号を付し、その説明を省略する。
図21の例では、エリア境界ノードのノードN11,N21,N31〜N33,N41がエリア間ルーティングに参加しているものとする。また、図20に示したように、各リンクのリンクコストを1とする。
【0006】
エリア間ルーティングに参加するノードでは、エリア間ルーティングプロトコルが動作する。エリア間ルーティングに参加するノードは、例えば、エリア内のトポロジー情報を要約した仮想リンクの情報をエリア間ルーティングに参加する全てのノードに通知する。また、エリア間ルーティングに参加するノードは、エリア間リンクの情報をエリア間ルーティングに参加する全てのノードに通知する。
【0007】
例えば、ノードN31は、エリアA内のトポロジー情報を基に、エリア境界ノードのノードN32,N33までの到達経路を、リンクコスト5およびリンクコスト4の仮想リンク情報として、エリア間ルーティングに参加する全ノードに通知する。また、ノードN31は、ノードN31−N11,N31−N21のエリア間リンク情報をエリア間ルーティングに参加する全ノードに通知する。他のエリア間ルーティングに参加するノードも同様に、仮想リンク情報およびエリア間リンク情報を通知する。これによって、図21に示すエリア間のトポロジーの情報がエリア間ルーティングに参加するノードで交換され、エリア間ルーティングに参加するノードはエリア間トポロジー情報を保持することができる。
【0008】
図22は、各ノードに保持されるエリア間トポロジー情報を示した図である。エリア間ルーティングに参加するノードは上述したように、例えば、図21に示すエリア間トポロジーの情報をエリア間ルーティングプロトコルで交換し、図22に示すようなエリア間トポロジー情報を保持する。例えば、エリア間ルーティングに参加した各エリア境界ノードは、エリア境界ノード間のリンク情報と、そのエリア境界ノード間のリンクコストを保持している。
【0009】
ネットワーク制御アプリケーション等が複数エリアに跨る経路を計算する場合、各ノードが保持するエリア間トポロジー情報を基に経路を計算する。例えば、図21において、ノードN21からノードN41までの経路を計算するとする。ノードN21からノードN41に至る経路は複数あるが、一般的にダイクストラアルゴリズムによって、リンクコストが最も小さくなる最短経路が選択される。例えば、ノードN21,N32,N33,N41が選択される。
【0010】
なお、1つのネットワークを複数のエリアに分割して経路制御プロトコルを運用しているネットワーク内において、パスの起点となる発側ノードから終点となる着側ノードの間に異なる経路を通る複数のパスを設定し、設定された複数のパスを、トラヒック負荷分散やパスプロテクションに利用可能な経路計算方法が提案されている(例えば、特許文献1参照)。
【先行技術文献】
【特許文献】
【0011】
【特許文献1】特開2005−252368号公報
【発明の概要】
【発明が解決しようとする課題】
【0012】
しかし、従来の経路計算では、リンクコストを基準に経路が選択されるため、1度通過したエリアを再び通過する場合があり、このような経路はマルチエリアネットワークの管理が困難になるという問題点があった。
【0013】
例えば、図21において、ノードN11からノードN41までの経路を計算するとする。従来の経路計算では、例えば、ダイクストラ法に基づき最短経路(リンクコストの最も小さい経路)が選択されるため、ノードN11,N31,N21,N32,N33,N41の経路が算出される。この経路計算では、総コストが最も小さいという利点があるものの、より多くのエリアを通過するため、管理の手間がかかる。例えば、図21の例の場合、エリアAを通過した経路がエリアCを経由して再びエリアAを通過しており、エリアAの管理者は、例えば、他の管理者の元にあるエリアCの状況等を把握しなければならない。
【0014】
本件はこのような点に鑑みてなされたものであり、マルチエリアネットワークの管理を容易にすることができるノードおよび経路計算方法を提供することを目的とする。
【課題を解決するための手段】
【0015】
上記課題を解決するために、マルチエリアネットワークに設けられるノードが提供される。このノードは、始点ノードから終点ノードに至る経路を算出する経路算出部と、前記経路算出部の算出する経路が通過する前記マルチエリアネットワークのエリアを示す通過エリアリストを記憶する記憶部と、を備え、前記経路算出部は、前記始点ノードから前記終点ノードに至る経路を算出する際、前記記憶部の通過エリアリストを参照し同じエリアを複数回通過する経路を経路算出対象から除外する。
【0016】
また、上記課題を解決するために、マルチエリアネットワークに設けられるノードが提供される。このノードは、始点ノードから終点ノードに至る経路を算出する経路算出部と、前記経路算出部の算出する経路が通過する前記マルチエリアネットワークのエリアを示す通過エリアリストを記憶する記憶部と、を備え、前記経路算出部は、前記始点ノードから前記終点ノードに至る経路を算出した後、前記記憶部の通過エリアリストを参照して同じエリアを許容回数以下で通過する経路を抽出し、抽出した経路の中からリンクコストの最も小さい経路を選択する。
【発明の効果】
【0017】
開示のノードおよび経路計算方法によれば、マルチエリアネットワークの管理が容易になる。
【図面の簡単な説明】
【0018】
【図1】第1の実施の形態に係るノードを示した図である。
【図2】第2の実施の形態に係るエリア内ルーティングを説明する図である。
【図3】エリア間ルーティングを説明する図である。
【図4】各ノードに保持されるエリア間トポロジー情報を示した図である。
【図5】各ノードに保持されるエリア情報を示した図である。
【図6】ノードのブロック図である。
【図7】エリア間経路計算処理部のブロック図である。
【図8】マルチエリアネットワークの経路計算を説明する図である。
【図9】経路算出部のフローチャートである。
【図10】到達距離の小さい経路を算出することができない場合のマルチエリアネットワークの例を示した図である。
【図11】第3の実施の形態に係るマルチエリアネットワークの経路計算を説明する図である。
【図12】経路算出部のフローチャートである。
【図13】第4の実施の形態に係る経路計算で経路を求めることができないマルチエリアネットワークの例を示した図である。
【図14】経路算出部のフローチャートである。
【図15】第5の実施の形態に係るマルチエリアネットワークを説明する図である。
【図16】エリア間ルーティングで交換されるトポロジー情報を説明する図である。
【図17】第6の実施の形態に係るマルチエリアネットワークの経路計算を説明する図である。
【図18】経路算出部のフローチャートである。
【図19】経路算出部のフローチャートである。
【図20】エリア内ルーティングを説明する図である。
【図21】エリア間ルーティングを説明する図である。
【図22】各ノードに保持されるエリア間トポロジー情報を示した図である。
【発明を実施するための形態】
【0019】
以下、第1の実施の形態を、図面を参照して詳細に説明する。
図1は、第1の実施の形態に係るノードを示した図である。図1には、マルチエリアネットワークが示してある。マルチエリアネットワークは、エリアA〜エリアDを有している。エリアAはノード1を有し、エリアBはノード2を有し、エリアCはノード3,4を有し、エリアDはノード5を有している。
【0020】
ノード1は、経路算出部1aおよび記憶部1bを有している。経路算出部1aは、始点ノードから終点ノードに至る経路を算出する。例えば、経路算出部1aは、ダイクストラ法などに基づいて自分(ノード1)からノード5までの経路を算出する。
【0021】
記憶部1bは、経路算出部1aの算出する経路が通過するエリアA〜Dを示す通過エリアリストを記憶する。
経路算出部1aは、始点ノードから終点ノードに至る経路を算出する際、記憶部1bの通過エリアリストを参照し、同じエリアを複数回通過する経路を経路算出対象から除外する。
【0022】
例えば、経路算出部1aは、ノード1,3,2までの経路を算出し、記憶部1bには、経路算出部1aの算出した経路が通過するエリアA,C,Bを示す通過エリアリスト‘A,C,B’が記憶されているとする。
【0023】
経路算出部1aは、次の経路候補としてノード4を抽出したとする。ノード4は、エリアCに属しており、経路算出部1aは、記憶部1bの通過エリアリスト‘A,C,B’に基づき、ノード4の経路はエリアCを2回通過することになると認識する。そこで、経路算出部1aは、ノード4の経路を経路算出対象から除外する。これにより、経路算出部1aは、例えば、同一エリアを複数回通過しないノード1,3,4,5の経路を算出することが可能となる。
【0024】
このように、ノード1は、経路を算出する際、経路が通過するエリアを示した通過エリアリストを記憶する。そして、ノードは、通過エリアリストに基づいて1度通過したエリアを再び通過することになる経路を経路算出対象から除外する。これにより、マルチエリアネットワークの管理を容易にすることができる。
【0025】
次に、第2の実施の形態を、図面を参照して詳細に説明する。
図2は、第2の実施の形態に係るエリア内ルーティングを説明する図である。図2には、マルチエリアネットワークが示してある。マルチエリアネットワークは、エリアA〜エリアDを有している。エリアAはノードN31〜N36を有し、エリアBはノードN10,N11を有し、エリアCはノードN21を有し、エリアDはノードN40,N41を有している。各ノード間に示す数字は、リンクコストを示している。ノードは、例えば、ルータやスイッチなどの通信装置である。
【0026】
マルチエリアネットワークでは、エリア毎にエリア内ルーティングプロトコルが動作する。エリア内ルーティングプロトコルが動作する全てのノードは、各ノードのリンク情報をエリア内全てのノードへ通知する。これによって、エリア内の全てのノードは、エリア内のトポロジーを把握することができる。
【0027】
図3は、エリア間ルーティングを説明する図である。図3において、図2と同じものには同じ符号を付し、その説明を省略する。
図3の例では、エリア境界ノードのノードN11,N21,N31〜N33,N41がエリア間ルーティングに参加しているものとする。また、図2に示したように、各リンクのリンクコストを1とする。
【0028】
エリア間ルーティングに参加するノードでは、エリア間ルーティングプロトコルが動作する。エリア間ルーティングに参加するノードは、例えば、エリア内のトポロジー情報を要約した仮想リンクの情報をエリア間ルーティングに参加する全てのノードに通知する。また、エリア間ルーティングに参加するノードは、エリア間リンクの情報をエリア間ルーティングに参加する全てのノードに通知する。また、エリア間ルーティングプロトコルに参加するノードは、自分の属しているエリアのエリアIDをエリア情報としてエリア間ルーティングに参加する全てのノードに通知する。
【0029】
例えば、ノードN31は、エリアB内のトポロジー情報を基に、エリア境界ノードのノードN32,N33までの到達経路を、リンクコスト5およびリンクコスト4の仮想リンク情報として、エリア間ルーティングに参加する全ノードに通知する。また、ノードN31は、ノードN31−N11,N31−N21のエリア間リンク情報をエリア間ルーティングに参加する全ノードに通知する。また、ノードN31は、自分の属するエリアID‘A’のエリア情報をエリア間ルーティングに参加する全ノードに通知する。他のエリア間ルーティングに参加するノードも同様に、仮想リンク情報、エリア間リンク情報、およびエリア情報を通知する。これにより、図3に示すエリア間のトポロジーの情報がエリア間ルーティングに参加するノードの間で交換され、エリア間ルーティングに参加するノードはエリア間トポロジー情報とエリア情報とを保持することができる。
【0030】
図4は、各ノードに保持されるエリア間トポロジー情報を示した図である。エリア間ルーティングに参加するノードは上述したように、例えば、図3に示すエリア間トポロジーの情報をエリア間ルーティングプロトコルで交換し、図4に示すようなエリア間トポロジー情報を保持する。例えば、エリア間ルーティングに参加するノードは、エリア間ルーティングに参加するノードのリンク情報と、そのリンク情報のリンク間のリンクコストとを保持している。
【0031】
図5は、各ノードに保持されるエリア情報を示した図である。エリア間ルーティングに参加するノードは上述したように、例えば、図3に示すエリア間トポロジーの情報をエリア間ルーティングプロトコルで交換し、図5に示すようなエリア情報を保持する。例えば、エリア間ルーティングに参加するノードは、ノード情報と、そのノード情報のノードの属するエリアのエリアIDとを保持している。
【0032】
なお、エリア境界ノード以外のノードがエリア間ルーティングに参加してもよい。例えば、図2に示すノードN10,N40もエリア間ルーティングに参加できる。この場合、ノードN10,N40のトポロジー情報も図4に示したエリア間トポロジー情報に含まれる。また、ノードN10,N40のエリア情報も図5に示したエリア情報に含まれる。
【0033】
図6は、ノードのブロック図である。図6に示すようにノードは、データ受信部11、データ種別判定部12、データ送信部13、エリア内RT(RT:RouTing)処理部20、およびエリア間RT処理部30を有している。エリア内RT処理部20は、エリア内RT制御パケット受信部21、エリア内RT制御パケット処理部22、エリア内RT情報生成部23、エリア内RT制御パケット送信部24、およびエリア内情報DB(DB:Data Base)25を有している。エリア間RT処理部30は、エリア間RT制御パケット受信部31、エリア間RT制御パケット処理部32、エリア間RT情報生成部33、エリア間RT制御パケット送信部34、エリア間経路計算処理部35、およびエリア間情報DB36を有している。
【0034】
データ受信部11は、ネットワークからデータを受信する。
データ種別判定部12は、データ受信部11によって受信されたデータを解析し、エリア内ルーティングプロトコルの制御パケットであるか、エリア間ルーティングプロトコルの制御パケットであるか、またはユーザデータのパケットであるかを判定する。データ種別判定部12は、エリア内ルーティングプロトコルの制御パケットが受信された場合、エリア内RT制御パケット受信部21へ出力する。データ種別判定部12は、エリア間ルーティングプロトコルの制御パケットが受信された場合、エリア間RT制御パケット受信部31へ出力する。データ種別判定部12は、ユーザデータのパケットが受信された場合、図示していないユーザRT処理部へ出力する。
【0035】
エリア内RT処理部20のエリア内RT制御パケット受信部21は、受信された制御パケットのヘッダを解析し、正常な制御パケットである場合には、エリア内RT制御パケット処理部22へ出力する。
【0036】
エリア内RT制御パケット処理部22は、受信した制御パケットに含まれているエリア内のトポロジー情報およびエリア内RT情報生成部23で生成されたトポロジー情報をエリア内情報DB25に記憶する。エリア内RT制御パケット処理部22は、生成されたトポロジー情報をエリア内情報DB25に記憶した後、受信ポート以外の全てのポートへ転送するため、エリア内RT制御パケット送信部24へ制御パケットを出力する。
【0037】
エリア内RT情報生成部23は、隣接しているノードの情報やそのノードを接続しているリンクのリンクコストを有するトポロジー情報を生成し、エリア内RT制御パケット処理部22へ出力する。
【0038】
エリア内RT制御パケット送信部24は、エリア内RT制御パケット処理部22から出力される制御パケットの適切なヘッダを生成し、データ送信部13に出力する。
エリア内情報DB25には、エリア内のトポロジー情報が格納される。
【0039】
エリア間RT処理部30のエリア間RT制御パケット受信部31は、受信された制御パケットのヘッダを解析し、正常な制御パケットである場合には、エリア間RT制御パケット処理部32へ出力する。
【0040】
エリア間RT制御パケット処理部32は、受信した制御パケットに含まれているエリア間のトポロジー情報およびエリア間RT情報生成部33で生成されたトポロジー情報とエリア情報とをエリア間情報DB36に記憶する。また、エリア間RT制御パケット処理部32は、受信した制御パケットに含まれている、制御パケットを送信したノードの属しているエリア情報をエリア間情報DB36に記憶する。エリア間RT制御パケット処理部32は、生成されたトポロジー情報とエリア情報とをエリア間情報DB36に記憶した後、受信ポート以外の全てのポートへ転送するため、エリア間RT制御パケット送信部34へ制御パケットを出力する。
【0041】
エリア間RT情報生成部33は、隣接しているノードの情報やそのノードを接続しているリンクのリンクコストを有するトポロジー情報を生成し、エリア間RT制御パケット処理部32へ出力する。エリア間RT情報生成部33は、エリア内情報DB25のエリア内トポロジー情報を基に、仮想リンク等のエリア間トポロジー情報を生成し、エリア間RT制御パケット処理部32へ出力する。また、エリア間RT情報生成部33は、自ノードが属するエリアのエリア情報を生成し、エリア間RT制御パケット処理部32へ出力する。
【0042】
エリア間RT制御パケット送信部34は、エリア間RT制御パケット処理部32から出力される制御パケットの適切なヘッダを生成し、データ送信部13に出力する。
エリア間経路計算処理部35は、エリア間情報DB36に記憶されているエリア間のトポロジー情報とエリア情報に基づいて、指定された始点のノードから終点(宛先)のノードまでの経路を算出する。エリア間経路計算処理部35は、一度通過したエリアを再度通過することがなく、例えば、ダイクストラ法等を用いてリンクコストが小さくなる経路を算出する。
【0043】
エリア間情報DB36には、エリア間のトポロジー情報とエリア情報が格納される。例えば、図4に示したエリア間トポロジー情報と図5に示したエリア情報とが格納される。
図7は、エリア間経路計算処理部のブロック図である。図7に示すようにエリア間経路計算処理部35は、経路算出部41および記憶部42を有している。
【0044】
経路算出部41は、経路計算処理中に得られた経路候補群の中から次に計算すべき経路を抽出する。また、経路算出部41は、抽出した経路が同一エリアを複数回通過しているか否かを、記憶部42に記憶されている、経路が通過したエリアを示す通過エリアリストを基に判定する。また、経路算出部41は、抽出した経路とすでに得られている他の経路とのリンクコストを比較する。また、経路算出部41は、記憶部42の通過エリアリストに経路が通過したエリアを記憶する。また、経路算出部41は、経路が通過するリンクのリンクコストを記憶部42に記憶する。
【0045】
記憶部42は、経路算出部41によって算出される経路の通過するエリアを示す通過エリアリストや、経路の通過するリンクのリンクコストの情報を記憶する。
図8は、マルチエリアネットワークの経路計算を説明する図である。図8には、経路算出部41が経路計算するマルチエリアネットワークの例が示してある。図8のマルチエリアネットワークは、エリアX,A,B,Yを有している。エリアXはノードN11を有し、エリアAはノードN13,N14を有し、エリアBはノードN12,N16,N17を有し、エリアYはノードN15を有している。各ノード間に示す数字は、リンクコストを示している。ノードN11〜N17は、エリア境界ノードであり、エリア間ルーティングに参加しているものとする。
【0046】
ノードN11の経路算出部41は、自分(ノードN11)からノードN15までの経路を算出するとする。ノードN11の経路算出部41は、例えば、ネットワーク管理者からのコマンドに基づいて、目的のノードN15までの経路を算出する。または、エリアXに属する他のノードがネットワーク管理者からのコマンドに基づいて、ノードN11からノードN15までの経路を算出してもよい。この場合、経路を算出したノードは、ノードN11に算出結果を通知する。
【0047】
なお、経路算出部41は、エリア間情報DB36に記憶されているトポロジー情報に基づき、図8に示すマルチエリアネットワークのトポロジーを認識することができる。
経路算出部41は、ダイクストラ法に基づき目標とする経路を算出していく。このとき、経路算出部41は、算出した経路(ノード)までの到達距離(リンクコストの合計)と、算出した経路が通過したエリアのエリアIDを記憶部42の通過エリアリストに記憶していく。
【0048】
例えば、経路算出部41は、ノードN11,N12,N13までの経路を確定した場合、図8のノードN11の下部に示すように、リンクコスト‘0’、通過エリアリスト‘X’を記憶部42に記憶している。また、図8のノードN12の下部に示すように、ノードN11からノードN12までのリンクコスト‘1’と、ノードN11からノードN12までの経路が通過したエリアの通過エリアリスト‘X,B’を記憶部42に記憶している。また、図8のノードN13の上部に示すように、ノードN11からノードN13までのリンクコスト‘2’と、ノードN11からノードN13までの経路が通過したエリアの通過エリアリスト‘X,B,A’を記憶部42に記憶している。また、図8のノードN17の下部に示すように、ノードN11からノードN17までのリンクコスト‘6’と、ノードN11からノードN17までの経路が通過したエリアの通過エリアリスト‘X,B’を記憶部42に記憶している。また、図8のノードN14の上部に示すように、ノードN11からノードN14までのリンクコスト‘3’と、ノードN11からノードN14までの経路が通過したエリアの通過エリアリスト‘X,B,A’を記憶部42に記憶している。
【0049】
なお、経路算出部41は、エリア間情報DB36に記憶されているエリア情報に基づいて通過エリアリストを生成し、記憶部42に記憶することができる。
経路算出部41は、ダイクストラ法により、最短経路が未確定であるノード群から、リンクコストの最も小さいノードを抽出する。例えば、経路算出部41は、ノードN13を最後に確定ノードとした場合、次にノードN14を抽出することになる。
【0050】
経路算出部41は、抽出したノードN14の有するリンクの端点となる隣接ノード(図8の場合、ノードN15,N16)を選択する。ここでは、ノードN16を選択したとする。経路算出部41は、抽出したノードN14の通過エリアリストの最後以外に、選択したノードN16のエリアIDが含まれているか判断する。経路算出部41は、抽出したノードN14の通過エリアリストの最後以外に、選択したノードN16のエリアIDが含まれている場合、選択したノードN16の経路を経路算出候補から除く。
【0051】
ここで、抽出したノードN14の通過エリアリストは‘X,B,A’である。この通過エリアリストの最後‘A’以外には、選択したノードN16のエリアID‘B’が含まれている。従って、経路算出部41は、抽出したノードN14の通過エリアリストの最後以外に、選択したノードN16のエリアIDが含まれているので、選択したノードN16の経路を経路算出候補から除く。
【0052】
すなわち、経路算出部41は、ノードN12で一旦エリアBに入り、その後エリアAを経由して再びエリアBに入る経路を経路算出候補から除外する。そして、経路算出部41は、ノードN14からノードN16の経路を除外して、別の経路をダイクストラ法により算出する。
【0053】
つまり、経路算出部41は、ダイクストラ法によって経路算出を行うとともに算出した経路の通過エリアリストを記憶する。そして、経路算出部41は、通過エリアリストに基づいて、一度通過したエリアを再び通過することになるか否かを判断し、一度通過したエリアを再び通過することになると判断した場合、その経路を除外してダイクストラ法の処理を進めていく。
【0054】
なお、図8の例の場合、ノードN11,N12,N17,N16,N15の経路が算出される。
図9は、経路算出部のフローチャートである。
【0055】
[ステップS1]経路算出部41は、全ノードにおける、始点ノードからの到達距離を無限大に設定し、始点ノードの到達距離を0に設定する。さらに、経路算出部41は、全ノードを最短経路未確定ノードとしてマークする(記憶部42に記憶する)。
【0056】
[ステップS2]経路算出部41は、最短経路が未確定であるとマークされたノード群の中から、始点ノードからの到達距離が最短となるノードを抽出する。
[ステップS3]経路算出部41は、ノードを抽出できなかった場合、終点ノードへの到達距離が存在しないことになるので処理を終了する。経路算出部41は、ノードを抽出できた場合、ステップS4へ進む。
【0057】
[ステップS4]経路算出部41は、抽出されたノードが終点ノードであるか否かを判断する。経路算出部41は、抽出したノードが終点ノードであった場合、最短経路が算出されたことになるので処理を終了する。経路算出部41は、抽出したノードが終点ノードでなかった場合、ステップS5へ進む。
【0058】
[ステップS5]経路算出部41は、抽出ノードを最短経路確定ノードとしてマークする。
[ステップS6]経路算出部41は、抽出ノードの有するリンク数分、ステップS13までの処理を繰り返す。なお、ステップS6からステップS13までの処理の対象となっているリンクを対象リンクと呼ぶ。
【0059】
[ステップS7]経路算出部41は、抽出ノードの有する通過エリアリストのエリアIDのうち、最後のエリアID以外で、対象リンクの端点となる隣接ノードのエリアIDと同一のものが含まれているか判断する。
【0060】
[ステップS8]経路算出部41は、同一のエリアIDが含まれていない場合には、ステップS9の処理へ進む。経路算出部41は、同一のエリアIDが含まれている場合には、次のリンク処理へ移るためステップS6へ進む。すなわち、経路算出部41は、一度通過したことのあるエリアに再び戻る経路を経路計算から除外する。
【0061】
[ステップS9]経路算出部41は、対象リンクの隣接ノードにおける新しい到達距離を算出する。隣接ノードにおける始点ノードからの到達距離は、抽出ノードまでの到達距離と対象リンクのリンクコストの和として求められる。
【0062】
[ステップS10]経路算出部41は、算出した隣接ノードの新しい到達距離と、すでに得られている隣接ノードの到達距離とを比較する。経路算出部41は、新しい到達距離がすでに得られている到達距離に対し小さい場合は、ステップS11へ進む。経路算出部41は、新しい到達距離がすでに得られている到達距離に対し小さくない場合は、次のリンク処理へ移るためステップS6へ進む。
【0063】
[ステップS11]経路算出部41は、隣接ノードの到達距離をステップS9で算出された新しい値に更新する。
[ステップS12]経路算出部41は、抽出ノードの通過エリアリストに記載されている最後のエリアIDと、隣接ノードのエリアIDとを比較する。経路算出部41は、通過エリアリストに記載されている最後のエリアIDと、隣接ノードのエリアIDとが異なる場合には、抽出ノードの通過エリアリストの最後に隣接ノードのエリアIDを追加して隣接ノードの通過エリアリストとして記憶する。経路算出部41は、通過エリアリストに記載されている最後のエリアIDと、隣接ノードのエリアIDとが同じである場合には、抽出ノードの通過エリアリストをそのまま隣接ノードの通過エリアリストとして記憶する。
【0064】
[ステップS13]経路算出部41は、対象リンクが残っている場合には、ステップS6へ進む。経路算出部41は、対象リンクが残っていない場合には、ステップS2へ進む。
【0065】
このように、経路算出部41は、ダイクストラ法により経路を算出するとともに、算出した経路の通過エリアを記憶する。これにより、経路算出部41は、到達距離が小さく、かつ、同一エリアを通過しないように経路を算出することができ、マルチエリアネットワークの管理を容易にすることができる。
【0066】
次に、第3の実施の形態を、図面を参照して詳細に説明する。第2の実施の形態では、各ノードへ到達する経路を1経路だけ保持しながら計算を進める。そのため、第2の実施の形態では、到達距離の小さい経路を算出するようにしているが、マルチエリアネットワークのトポロジーによっては、より到達距離の小さい経路を算出できない場合が存在する。第3の実施の形態では、各ノードへ到達する複数の経路と、それらの経路が通過する通過エリアリストを保持することによって、適切な経路を算出することができるようにする。
【0067】
図10は、到達距離の小さい経路を算出することができない場合のマルチエリアネットワークの例を示した図である。図10のマルチエリアネットワークは、エリアA〜Eを有している。エリアAはノードN10を有し、エリアBはノードN21,N22を有し、エリアCはノードN31を有し、エリアDはノードN41を有し、エリアEはノードN51を有している。各ノード間に示す数字はリンクコストを示している。ノードN10を始点ノード、ノードN22を終点ノードとする。
【0068】
ノードN10からノードN22までの経路は、例えば、ノードN10,N31,N41,N51,N22の経路R1と、ノードN10,N21,N41,N51,N22の経路R2と、ノードN10,N21,N22の経路R3とが考えられる。それぞれの経路R1〜R3のリンクコストは、8、4、11となる。
【0069】
ここで、経路R2は、リンクコストが最も小さいがエリアBを一度通過しており望ましい経路でない。また、経路R3は、経路R1よりリンクコストが大きいため望ましい経路でない。従って、経路R1が望ましい経路となる。
【0070】
第2の実施の形態では、ダイクストラ法により、最短の到達距離を有するノードを選択し、最短経路確定ノードの領域を広げていく。そのため、図10の例では、ノードN31を経由した経路が算出されない。すなわち、経路R1を算出したいが、第2の実施の形態では経路R3が算出される。
【0071】
なお、第3の実施の形態においてもノードは、図6、図7と同様のブロックを有する。ただし、経路算出部41の機能が異なる。
図11は、第3の実施の形態に係るマルチエリアネットワークの経路計算を説明する図である。図11のマルチエリアネットワークは、エリアA〜Cを有している。エリアAはノードN11を有し、エリアBはノードN12〜N15を有し、エリアCはノードN16,N17を有している。
【0072】
各ノードは、図11に示すように、リンクL1〜L8によって接続されている。各ノード間に示す数字はリンクコストを示している。ノードN11を始点ノード、ノードN15を終点ノードとする。
【0073】
ノードN11の経路算出部41は、始点である自分(ノードN11)に接続されている全てのリンクL1,L4を記憶部42の計算候補リストに登録する。経路算出部41は、リンクL1,L4の到達距離を記憶部42に記憶し、始点のノードN11のエリアID‘A’をリンクL1,L4の通過エリアリストとして記憶部42に記憶する。これにより、例えば、図11のノードN12の上部に示すように‘1’,‘A’の情報と、ノードN16の下部に示すように‘5’,‘A’の情報が記憶部42に記憶される。
【0074】
経路算出部41は、計算候補リストのうち、最短の到達距離を有するリンクを抽出する。上記例の場合、リンクL1を抽出する。経路算出部41は、抽出したリンクL1を計算候補リストから削除する。
【0075】
経路算出部41は、抽出したリンクL1の終端点のノードN12の有するリンクL2,L8を抽出する。以下、抽出したリンクL1と、その終端点のノードN12から伸びるリンクL2,L8を区別するため、リンクL2,L8を新規リンクと呼ぶ。
【0076】
経路算出部41は、抽出したリンクL1の通過エリアリスト‘A’の最後以外のエリアIDと、新規リンクL2,L8の終端点のノードN14,N13のエリアIDとが同じか判断する。
【0077】
経路算出部41は、エリアIDが同じであれば、新規リンクによる経路の算出を除外する。すなわち、経路算出部41は、一度通過したエリアを再び通過することになる経路を経路計算から除外する。
【0078】
一方、経路算出部41は、エリアIDが異なれば、新規リンクを計算候補リストに登録する。また、経路算出部41は、新規リンクまでの到達距離を記憶部42に記憶する。そして、経路算出部41は、抽出したリンクの始端点ノードと終端点ノードのエリアが異なる場合、抽出したリンクの通過エリアリストの最後に、新規リンクの始端点ノードの属するエリアIDを追加して、新規リンクの通過エリアリストとする。経路算出部41は、抽出したリンクの始端点ノードと終端点ノードのエリアが同じ場合、抽出したリンクの通過エリアリストを新規リンクの通過エリアリストとする。
【0079】
上記例の場合、抽出したリンクL1の通過エリアリスト‘A’の最後以外のエリアID(この場合はなし)と、新規リンクL2,L8の終端点のノードN14,N13のエリアIDが異なるので、経路算出部41は、新規リンクL2,L8を計算候補リストに登録する。また、経路算出部41は、新規リンクL2,L8までの到達距離‘2’,‘21’を記憶部42に記憶する。そして、経路算出部41は、抽出したリンクL1の始端点ノードと終端点ノードのエリアが異なるので、抽出したリンクL1の通過エリアリスト‘A’の最後に、新規リンクL2,L8の始点のノードN12の属するエリアID‘B’を追加して、新規リンクL2,L8の通過エリアリストとする。
【0080】
これにより、例えば、図11のノードN13の上部に示すように‘21’,‘AB’の情報が記憶部42に記憶される。また、ノードN14の上部に示すように‘2’,‘AB’の情報が記憶部42に記憶される。
【0081】
なお、上記例の場合、リンクL1は計算候補リストから削除され、新規リンクL2,L8は計算候補リストに登録されているので、現在の計算候補リストには、リンクL2,L4,L8が登録されていることになる。それぞれの到達距離は、2,5,21である。
【0082】
経路算出部41は、計算候補リストの中から、到達距離の最も小さいリンクを抽出する。上記例の場合、経路算出部41は、リンクL2を抽出する。経路算出部41は、抽出したリンクL2を計算候補リストから削除する。
【0083】
経路算出部41は、上記と同様に、抽出したリンクL2から伸びるリンクL3,L7を新規リンクとし、上記と同様の処理を行う。
経路算出部41は、新規リンクの終端点のノードが一度通過したエリアに属している場合にはその新規リンクの経路を経路算出対象から除く。一方、経路算出部41は、新規リンクの終端点ノードが一度通過したエリアに属していない場合には、その新規リンクの到達距離を記憶し、通過エリアリストを記憶する。これにより、例えば、図11のノードN16の下部に示すように到達距離‘7’と通過エリアリスト‘AB’の情報が記憶部42に記憶される。また、ノードN15の上部に示すように到達距離‘12’と通過エリアリスト‘AB’の情報が記憶部42に記憶される。なお、計算候補リストは、リンクL2が削除され、L3,L4,L7,L8となる。
【0084】
すなわち、経路算出部41は、計算候補リストから最短の到達距離を有するリンクを抽出し、そのリンクの終端点のノードから新規リンクを伸ばし、伸ばした新規リンクが一度通過したエリアに戻っていなければ、新規リンクを計算候補リストに追加していく。
【0085】
これにより、同じノードに到達する、異なる経路のリンクが複数計算候補リストに登録される場合がある。例えば、図11の例の場合、ノードN16に到達するリンクとしてリンクL4とリンクL3が計算候補リストに登録される。つまり、経路算出部41は、各ノードへ到達する複数の経路を記憶することによって、適切な経路を算出することができる。
【0086】
図12は、経路算出部のフローチャートである。
[ステップS21]経路算出部41は、始点ノードに接続されている全リンクを計算候補リストに登録する。そして、経路算出部41は、始点ノードからリンクの終端点へ至る経路情報として、始点ノードからリンクの終端点へ至る到達距離と、始点ノードからリンクの終端点へ至る経路が通過するエリアを通過エリアリストとして記憶部42に記憶する。すなわち、経路算出部41は、始点ノードから伸びる各リンクのリンクコストを到達距離として記憶し、始点ノードの属するエリアのエリアIDを通過エリアリストとして記憶部42に記憶する。
【0087】
[ステップS22]経路算出部41は、計算候補リストの中から到達距離の最も小さいリンクを抽出する。
[ステップS23]経路算出部41は、リンクを抽出できなかった場合、終点ノードへの到達経路が存在しないことになるので、処理を終了する。経路算出部41は、リンクを抽出できた場合、ステップS24へ進む。
【0088】
[ステップS24]経路算出部41は、抽出したリンクの終端点のノードが終点ノードであるか否かを判断する。経路算出部41は、終点ノードであると判断した場合、最短経路が算出されたことになるので処理を終了する。経路算出部41は、終点ノードでなかった場合には、ステップS25へ進む。
【0089】
[ステップS25]経路算出部41は、抽出リンクを計算候補リストから削除する。
[ステップS26]経路算出部41は、抽出リンクの終端点のノードが有している全てのリンクに対して、順にステップS32までの処理を行う。以下では、抽出リンクの終端点のノードから伸びている処理対象となっているリンクを新規リンクと呼ぶ。
【0090】
[ステップS27]経路算出部41は、抽出リンクの通過エリアリストに記憶されているエリアIDのうち、最後のエリアID以外のエリアIDで、新規リンクの終端点のノードの属するエリアIDと同一のものがあるか否かを判断する。
【0091】
[ステップS28]経路算出部41は、同一のエリアIDが含まれていない場合には、ステップS29の処理へ進む。経路算出部41は、同一のエリアIDが含まれている場合には、次の新規リンクの処理へ移るためステップS26へ進む。すなわち、経路算出部41は、一度通過したことのあるエリアに再び戻る経路を経路計算対象から除外する。
【0092】
[ステップS29]経路算出部41は、新規リンクの新しい到達距離(抽出リンクの到達距離+新規リストのリンクコスト)を記憶部42に記憶する。また、経路算出部41は、新規リンクへの経路として、抽出リンクの経路に抽出リンクの始端点のノードを追加した通過ノードリストを記憶部42に記憶する。
【0093】
[ステップS30]経路算出部41は、抽出リンクの始端点のノードと終端点のノードでエリアIDが異なる場合には、抽出リンクの通過エリアリストの最後に新規リンクの始端点のノードのエリアIDを追加し、新規リンクの通過エリアリストとして記憶部42に記憶する。また、経路算出部41は、抽出リンクの始端点のノードと終端点のノードでエリアIDが同じである場合には、抽出リンクの通過エリアリストを新規リンクの通過エリアリストとして記憶部42に記憶する。
【0094】
[ステップS31]経路算出部41は、新規リンクを計算候補リストに追加する。このとき、同じノードに到達する異なるリンクが計算候補リストに登録される場合もある。つまり、経路算出部41は、あるノードに到達するリンクが複数存在する場合、異なる経路距離を持つリンクとして、多重に計算候補リストに登録する。このように、経路算出部41は、複数の経路を記憶することによって、同一エリアを通過しない到達距離の短い経路を算出することが可能となる。
【0095】
[ステップS32]経路算出部41は、新規リンクが残っている場合には、ステップS26へ進む。経路算出部41は、新規リンクが残っていない場合には、ステップS22へ進む。
【0096】
このように、経路算出部41は、複数の経路を記憶しながら、かつ、同一エリアに戻る経路を除外して経路計算を進めていく。これにより、最短経路を算出することが可能となる。
【0097】
次に、第4の実施の形態を、図面を参照して詳細に説明する。第2の実施の形態では、各ノードにおいて経路が通過する全てのエリアIDを通過エリアリストに追加しながら経路計算を進める。第3の実施の形態では、各ノードに到達可能な複数の経路において、その経路が通過する全てのエリアIDを通過エリアリストに追加しながら、経路計算を進める。そのため、ノードは、多くの情報を記憶するための記憶領域が必要になるとともに、記憶した情報をチェックする量も増加し、経路計算負荷が高くなる。第4の実施の形態では、ノードの記憶容量および計算負荷の低減を図る。
【0098】
図13は、第4の実施の形態に係る経路計算で経路を求めることができないマルチエリアネットワークの例を示した図である。図13のマルチエリアネットワークは、エリアA〜Eを有している。エリアAはノードN11を有し、エリアBはノードN21〜N24を有し、エリアCはノードN31,N32を有し、エリアDはノードN41,N42を有し、エリアEはノードN51を有している。ノードN11を始点ノード、ノードN51を終点ノードとする。
【0099】
第4の実施の形態では、ダイクストラ法によって経路を算出するとともに、経路が1つ前に通過したエリアのエリアIDを記憶部に記憶する。すなわち、第4の実施の形態では、経路が通過してきた全てのエリアを記憶部に記憶しない。従って、複数の異なるエリアを跨って再び同一エリアに戻るマルチエリアネットワークのトポロジーでは、同一エリアを通過する経路計算を許可してしまう。
【0100】
例えば、図13においてノードN42では、1つ前に通過したエリアCのエリアIDしか記憶部に記憶していない。従って、第4の実施の形態では、同一のエリアBを再び通過するノードN23の経路を経路計算対象から除外せずに計算してしまう。
【0101】
一方、図2に示したようなマルチエリアネットワークのトポロジーでは、第4の実施の形態に係る経路計算によっても同一エリアを再び通過する経路を除外することができる。すなわち、第4の実施の形態では、スター型のトポロジーを有するマルチエリアネットワークにおいて適用することができる。
【0102】
なお、第4の実施の形態においてもノードは、図6、図7と同様のブロックを有する。ただし、経路算出部41の機能が異なる。また、図8に示したマルチエリアネットワークを第4の実施の形態に係る経路算出部41で経路計算した場合、図8に示すノードN11,N12,N13,N14,N16,N17の通過エリアリストは、それぞれX,X,B,B,X,Xとなる。すなわち、第4の実施の形態では、各ノードの通過エリアリストは、1つのエリアIDを記憶すればよい。以下では、第4の実施の形態に係る通過エリアリストを通過エリア情報と呼ぶ。
【0103】
図14は、経路算出部のフローチャートである。
ステップS41からステップS46までの処理は、図9のフローチャートのステップS1からステップS6までの処理と同じであり、その説明を省略する。
【0104】
[ステップS47]経路算出部41は、抽出ノードの有する通過エリア情報が示しているエリアIDと、対象リンクの端点となる隣接ノードのエリアIDが同じであるか否か判断する。
【0105】
[ステップS48]経路算出部41は、抽出ノードの有する通過エリア情報のエリアIDと、対象リンクの端点となる隣接ノードのエリアIDが同じである場合、ステップS46に進む。経路算出部41は、同じでない場合、ステップS49へ進む。
【0106】
[ステップS49]経路算出部41は、対象リンクの隣接ノードにおける新しい到達距離を算出する。隣接ノードにおける始点ノードからの到達距離は、抽出ノードまでの到達距離と対象リンクのリンクコストの和として求められる。
【0107】
[ステップS50]経路算出部41は、算出した隣接ノードの新しい到達距離と、すでに得られている隣接ノードの到達距離とを比較する。経路算出部41は、新しい到達距離がすでに得られている到達距離に対し小さい場合は、ステップS51へ進む。経路算出部41は、新しい到達距離がすでに得られている到達距離に対し小さくない場合は、次のリンク処理へ移るためステップS46へ進む。
【0108】
[ステップS51]経路算出部41は、隣接ノードの到達距離をステップS49で算出された新しい値に更新する。
[ステップS52]経路算出部41は、抽出ノードと隣接ノードのエリアIDを比較する。経路算出部41は、エリアIDが異なる場合には、抽出ノードのエリアIDを隣接ノードの通過エリア情報として記憶部42に記憶する。経路算出部41は、エリアIDが同じである場合には、抽出ノードの通過エリア情報を隣接ノードの通過エリア情報として記憶部42に記憶する。
【0109】
[ステップS53]経路算出部41は、対象リンクが残っている場合には、ステップS46へ進む。経路算出部41は、対象リンクが残っていない場合には、ステップS42へ進む。
【0110】
このように、経路算出部41は、ダイクストラ法により経路を算出するとともに、算出した経路の1つ前に通過したエリアを記憶する。これにより、経路算出部41は、記憶部42に記憶する情報量を低減でき、また、経路計算の処理負荷を低減することができる。
【0111】
次に、第5の実施の形態を、図面を参照して詳細に説明する。第5の実施の形態では、あるエリア内で障害が発生した場合の経路計算について説明する。
図15は、第5の実施の形態に係るマルチエリアネットワークを説明する図である。図15のマルチエリアネットワークは、図2のマルチエリアネットワークと同様であり、その説明を省略する。
【0112】
図15に示すように、エリアAのノードN35に障害が発生したとする。この場合、エリア間ルーティングプロトコルでは、ノードN31−N33間の仮想リンク、ノードN31−N32間の仮想リンクのリンク情報が通知されないか、あるいは障害リンクとして通知される。
【0113】
図16は、エリア間ルーティングで交換されるトポロジー情報を説明する図である。図15のノードN35で障害が発生した場合、図16に示すように、ノードN31−N33間の仮想リンク、ノードN31−N32間の仮想リンクで障害が発生したことになり、ノードN31−N33間の仮想リンク、ノードN31−N32間の仮想リンクのリンク情報が通知されないか、あるいは障害リンクとして通知される。
【0114】
このような場合に、上述した実施の形態の経路算出部41によってノードN11からノードN41までの経路を計算した場合には、同一エリアを複数回通過しない経路が存在しないため、経路が算出されない。そこで、第5の実施の形態では、経路算出部41によって経路計算できない場合は、ダイクストラ法に切り替えて経路の再計算を行う。
【0115】
図16の場合、経路算出部41は、ダイクストラ法によって再計算を行うことにより、ノードN11,N31,N21,N32,N33,N41のエリアAを2回通過する経路を算出することができる。
【0116】
このように、経路算出部41は、障害発生により、経路を算出することができないときはダイクストラ法によって経路を再計算する。これにより、経路算出部41は、障害が発生したときでも経路を算出することができる。
【0117】
次に、第6の実施の形態を、図面を参照して詳細に説明する。経路計算において、同一エリアの通過を許可しない場合、場合によってはリンクコストが非常に大きくなる場合もある。第6の実施の形態では、同一エリアを通過する経路の許容回数を指定し、より小さいリンクコストの経路を選択するようにする。
【0118】
図17は、第6の実施の形態に係るマルチエリアネットワークの経路計算を説明する図である。図17のマルチエリアネットワークは、エリアA〜Dを有している。エリアAはノードN11〜N14を有し、エリアBはノードN21を有し、エリアCはノードN31を有し、エリアDはノードN41を有している。各ノード間に示す数字は、リンクコストを示している。なお、ノードN11−N12間、ノードN12−N13間、ノードN13−N14間は、仮想リンクのリンクコストを示している。ノードN11を始点ノード、ノードN14を終点ノードとする。
【0119】
ノードN11からノードN14までに至る同一エリアを複数回通過しない経路は、ノードN11,N12,N13,N14を通過する経路になる。この経路は、総リンクコストが30となり、非常にリンクコストが大きい経路となる。
【0120】
しかし、他のエリアB〜Dに出て行くことを許すと、エリアAを4回通過することになるが、最短リンクコスト6のノードN11,N21,N12,N31,N13,N41,N14の経路を得ることができる。一般的には、管理者は、同一エリアを通過する回数とリンクコストのバランスを考慮して経路を選択することになる。
【0121】
第6の実施の形態では、同一エリアを通過する許容回数を指定することにより、より小さいコストの経路を選択することを可能とする。許容回数は、例えば、ネットワークの管理者によって指定される。
【0122】
例えば、図17に示すようなマルチエリアネットワークにおいて、エリアAの通過を許容できる許容回数を2回とした場合には、ノードN11,N12,N13,N41,N14の総リンクコスト‘17’の経路を算出できる。あるいは、許容回数を3回とした場合には、ノードN11,N12,N31,N13,N41,N14の総リンクコスト‘9’の経路を算出できる。
【0123】
なお、第6の実施の形態においてもノードは、図6、図7と同様のブロックを有する。ただし、経路算出部41の機能が異なる。経路算出部41は、第3の実施の形態と同様の機能を有する。ただし、第3の実施の形態の経路算出部41では、同一エリアを通過することになる新規リンクは経路計算から除外したが、第6の実施の形態に係る経路算出部41では、除外しない。すなわち、第6の実施の形態に係る経路算出部41は、始点ノードから終点ノードに至る経路を複数計算する。そして、各経路の通過エリアリストを参照して同じエリアを許容回数以下で通過する経路を抽出し、抽出した経路の中からリンクコストの最も小さい経路を選択する。
【0124】
図18、図19は、経路算出部のフローチャートである。
[ステップS61]経路算出部41は、始点ノードに接続されている全リンクを計算候補リストに登録する。そして、経路算出部41は、始点ノードからリンクの終端点へ至る経路情報として、始点ノードからリンクの終端点へ至る到達距離と、始点ノードからリンクの終端点へ至る経路が通過するエリアを通過エリアリストとして記憶部42に記憶する。すなわち、経路算出部41は、始点ノードから伸びる各リンクのリンクコストを到達距離として記憶し、始点ノードの属するエリアのエリアIDを通過エリアリストとして記憶部42に記憶する。
【0125】
[ステップS62]経路算出部41は、計算候補リストの中から到達距離の最も小さいリンクを抽出する。
[ステップS63]経路算出部41は、リンクを抽出できなかった場合、ステップS71へ進む。経路算出部41は、リンクを抽出できた場合、ステップS64へ進む。
【0126】
[ステップS64]経路算出部41は、抽出したリンクの終端点のノードが終点ノードであるか否かを判断する。経路算出部41は、終点ノードであると判断した場合、最短経路が算出されたことになる。経路算出部41は、繰り返し計算により選ばれた複数経路の中から最適経路を選択するため、ステップS72へ進む。経路算出部41は、終点ノードでなかった場合には、ステップS65へ進む。
【0127】
[ステップS65]経路算出部41は、抽出リンクを計算候補リストから削除する。
[ステップS66]経路算出部41は、抽出リンクの終端点のノードが有している全てのリンクに対して、順にステップS70までの処理を行う。以下では、抽出リンクの終端点のノードから伸びている処理対象となっているリンクを新規リンクと呼ぶ。
【0128】
[ステップS67]経路算出部41は、新規リンクの新しい到達距離(抽出リンクの到達距離+新規リストのリンクコスト)を記憶部42に記憶する。また、経路算出部41は、新規リンクへの経路として、抽出リンクの経路に抽出リンクの始端点のノードを追加した経路候補リストを記憶部42に記憶する。
【0129】
[ステップS68]経路算出部41は、抽出リンクの始端点のノードと終端点のノードでエリアIDが異なる場合には、抽出リンクの通過エリアリストの最後に新規リンクの始端点のノードのエリアIDを追加し、同一である場合には、抽出リンクの通過エリアリストを新規リンクの通過エリアリストとして記憶部42に記憶する。
【0130】
[ステップS69]経路算出部41は、新規リンクを計算候補リストに追加する。
[ステップS70]経路算出部41は、新規リンクが残っている場合には、ステップS66へ進む。経路算出部41は、新規リンクが残っていない場合には、ステップS62へ進む。
【0131】
[ステップS71]経路算出部41は、経路候補リストに経路が存在しない場合、宛先までの経路が存在しないと判断し処理を終了する。経路算出部41は、経路候補リストに経路が存在する場合、経路候補リストに格納されている全ての経路に対して通過エリアリストを参照し、許容回数以下で同一エリアを通過している経路を抽出する。経路算出部41は、経路を抽出できた場合には、その中から最短リンクコストの経路を選択する。経路算出部41は、経路を抽出できなかった場合には、終点ノードまでの所望の経路は存在しないと判断し処理を終了する。
【0132】
[ステップS72]抽出リンクの終端点が終点ノードであることは、終点までの経路が得られたことを意味する。従って、経路算出部41は、得られた経路が選択すべき最適な経路であるかを判断する。
【0133】
経路算出部41は、抽出リンクの通過エリアリストに基づいて、同一エリアを通過したことのある経路であるか判断する。すなわち、経路算出部41は、不連続に並んだ同じエリアIDが存在するか判断する。
【0134】
[ステップS73]経路算出部41は、抽出リンクの通過エリアリストに不連続に並んだ同じエリアIDが存在する場合、すなわち、抽出リンクの経路が同一エリアを一度通過した経路である場合、ステップS74へ進む。経路算出部41は、抽出リンクの通過エリアリストに不連続に並んだ同じエリアIDが存在しない場合、ステップS75へ進む。
【0135】
[ステップS74]経路算出部41は、抽出リンクの経路を経路候補リストに格納する。経路算出部41は、他の到達距離の小さい経路を探索すべく、ステップS62へ進む。
[ステップS75]経路算出部41は、経路候補リストに経路が存在しない場合、宛先までの経路が存在しないと判断し処理を終了する。経路算出部41は、経路候補リストに経路が存在する場合、経路候補リストに格納されている全ての経路に対して、通過エリアリストを参照し、許容回数以下で同一経路を通過している経路を抽出する。そして、経路算出部41は、抽出した経路の中から最短の到達距離の経路を選択し処理を終了する。経路算出部41は、許容回数以下で経路を抽出できなかった場合には、所望の経路は存在しないとして処理を終了する。
【0136】
このように、経路算出部41は、複数の経路を記憶しながら、かつ、同一エリアに戻る経路を除外しないで経路計算を進めていく。そして、経路算出部41は、同一エリアを許容回数以下で通過する経路を抽出し、より小さいリンクコストの経路を選択して、最適な経路を算出する。
【符号の説明】
【0137】
1〜5 ノード
1a 経路算出部
1b 記憶部
【技術分野】
【0001】
本件は、マルチエリアネットワークに設けられるノードおよび経路計算方法に関する。
【背景技術】
【0002】
複数のエリアに分割されたネットワークでは、エリア間ルーティングプロトコルが用いられる。例えば、エリア間ルーティングプロトコルに参加するノードは、エリア内で交換されているエリア内ルーティングプロトコルの情報を、エリア間ルーティングプロトコルのルーティングドメインに通知する。これにより、各エリアのノードは、他のエリアのネットワーク状態を把握することが可能になり、複数のエリアを跨る経路の算出が可能になる。
【0003】
図20は、エリア内ルーティングを説明する図である。図20には、マルチエリアネットワークが示してある。マルチエリアネットワークは、エリアA〜エリアDを有している。エリアAはノードN31〜N36を有し、エリアBはノードN10,N11を有し、エリアCはノードN21を有し、エリアDはノードN40,N41を有している。各ノード間に示す数字は、リンクコストを示している。
【0004】
マルチエリアネットワークでは、エリア毎にエリア内ルーティングプロトコルが動作する。エリア内ルーティングプロトコルが動作する全てのノードは、各ノードのリンク情報をエリア内全てのノードへ通知する。これによって、エリア内の全てのノードは、エリア内のトポロジーを把握することができる。
【0005】
図21は、エリア間ルーティングを説明する図である。図21において、図20と同じものには同じ符号を付し、その説明を省略する。
図21の例では、エリア境界ノードのノードN11,N21,N31〜N33,N41がエリア間ルーティングに参加しているものとする。また、図20に示したように、各リンクのリンクコストを1とする。
【0006】
エリア間ルーティングに参加するノードでは、エリア間ルーティングプロトコルが動作する。エリア間ルーティングに参加するノードは、例えば、エリア内のトポロジー情報を要約した仮想リンクの情報をエリア間ルーティングに参加する全てのノードに通知する。また、エリア間ルーティングに参加するノードは、エリア間リンクの情報をエリア間ルーティングに参加する全てのノードに通知する。
【0007】
例えば、ノードN31は、エリアA内のトポロジー情報を基に、エリア境界ノードのノードN32,N33までの到達経路を、リンクコスト5およびリンクコスト4の仮想リンク情報として、エリア間ルーティングに参加する全ノードに通知する。また、ノードN31は、ノードN31−N11,N31−N21のエリア間リンク情報をエリア間ルーティングに参加する全ノードに通知する。他のエリア間ルーティングに参加するノードも同様に、仮想リンク情報およびエリア間リンク情報を通知する。これによって、図21に示すエリア間のトポロジーの情報がエリア間ルーティングに参加するノードで交換され、エリア間ルーティングに参加するノードはエリア間トポロジー情報を保持することができる。
【0008】
図22は、各ノードに保持されるエリア間トポロジー情報を示した図である。エリア間ルーティングに参加するノードは上述したように、例えば、図21に示すエリア間トポロジーの情報をエリア間ルーティングプロトコルで交換し、図22に示すようなエリア間トポロジー情報を保持する。例えば、エリア間ルーティングに参加した各エリア境界ノードは、エリア境界ノード間のリンク情報と、そのエリア境界ノード間のリンクコストを保持している。
【0009】
ネットワーク制御アプリケーション等が複数エリアに跨る経路を計算する場合、各ノードが保持するエリア間トポロジー情報を基に経路を計算する。例えば、図21において、ノードN21からノードN41までの経路を計算するとする。ノードN21からノードN41に至る経路は複数あるが、一般的にダイクストラアルゴリズムによって、リンクコストが最も小さくなる最短経路が選択される。例えば、ノードN21,N32,N33,N41が選択される。
【0010】
なお、1つのネットワークを複数のエリアに分割して経路制御プロトコルを運用しているネットワーク内において、パスの起点となる発側ノードから終点となる着側ノードの間に異なる経路を通る複数のパスを設定し、設定された複数のパスを、トラヒック負荷分散やパスプロテクションに利用可能な経路計算方法が提案されている(例えば、特許文献1参照)。
【先行技術文献】
【特許文献】
【0011】
【特許文献1】特開2005−252368号公報
【発明の概要】
【発明が解決しようとする課題】
【0012】
しかし、従来の経路計算では、リンクコストを基準に経路が選択されるため、1度通過したエリアを再び通過する場合があり、このような経路はマルチエリアネットワークの管理が困難になるという問題点があった。
【0013】
例えば、図21において、ノードN11からノードN41までの経路を計算するとする。従来の経路計算では、例えば、ダイクストラ法に基づき最短経路(リンクコストの最も小さい経路)が選択されるため、ノードN11,N31,N21,N32,N33,N41の経路が算出される。この経路計算では、総コストが最も小さいという利点があるものの、より多くのエリアを通過するため、管理の手間がかかる。例えば、図21の例の場合、エリアAを通過した経路がエリアCを経由して再びエリアAを通過しており、エリアAの管理者は、例えば、他の管理者の元にあるエリアCの状況等を把握しなければならない。
【0014】
本件はこのような点に鑑みてなされたものであり、マルチエリアネットワークの管理を容易にすることができるノードおよび経路計算方法を提供することを目的とする。
【課題を解決するための手段】
【0015】
上記課題を解決するために、マルチエリアネットワークに設けられるノードが提供される。このノードは、始点ノードから終点ノードに至る経路を算出する経路算出部と、前記経路算出部の算出する経路が通過する前記マルチエリアネットワークのエリアを示す通過エリアリストを記憶する記憶部と、を備え、前記経路算出部は、前記始点ノードから前記終点ノードに至る経路を算出する際、前記記憶部の通過エリアリストを参照し同じエリアを複数回通過する経路を経路算出対象から除外する。
【0016】
また、上記課題を解決するために、マルチエリアネットワークに設けられるノードが提供される。このノードは、始点ノードから終点ノードに至る経路を算出する経路算出部と、前記経路算出部の算出する経路が通過する前記マルチエリアネットワークのエリアを示す通過エリアリストを記憶する記憶部と、を備え、前記経路算出部は、前記始点ノードから前記終点ノードに至る経路を算出した後、前記記憶部の通過エリアリストを参照して同じエリアを許容回数以下で通過する経路を抽出し、抽出した経路の中からリンクコストの最も小さい経路を選択する。
【発明の効果】
【0017】
開示のノードおよび経路計算方法によれば、マルチエリアネットワークの管理が容易になる。
【図面の簡単な説明】
【0018】
【図1】第1の実施の形態に係るノードを示した図である。
【図2】第2の実施の形態に係るエリア内ルーティングを説明する図である。
【図3】エリア間ルーティングを説明する図である。
【図4】各ノードに保持されるエリア間トポロジー情報を示した図である。
【図5】各ノードに保持されるエリア情報を示した図である。
【図6】ノードのブロック図である。
【図7】エリア間経路計算処理部のブロック図である。
【図8】マルチエリアネットワークの経路計算を説明する図である。
【図9】経路算出部のフローチャートである。
【図10】到達距離の小さい経路を算出することができない場合のマルチエリアネットワークの例を示した図である。
【図11】第3の実施の形態に係るマルチエリアネットワークの経路計算を説明する図である。
【図12】経路算出部のフローチャートである。
【図13】第4の実施の形態に係る経路計算で経路を求めることができないマルチエリアネットワークの例を示した図である。
【図14】経路算出部のフローチャートである。
【図15】第5の実施の形態に係るマルチエリアネットワークを説明する図である。
【図16】エリア間ルーティングで交換されるトポロジー情報を説明する図である。
【図17】第6の実施の形態に係るマルチエリアネットワークの経路計算を説明する図である。
【図18】経路算出部のフローチャートである。
【図19】経路算出部のフローチャートである。
【図20】エリア内ルーティングを説明する図である。
【図21】エリア間ルーティングを説明する図である。
【図22】各ノードに保持されるエリア間トポロジー情報を示した図である。
【発明を実施するための形態】
【0019】
以下、第1の実施の形態を、図面を参照して詳細に説明する。
図1は、第1の実施の形態に係るノードを示した図である。図1には、マルチエリアネットワークが示してある。マルチエリアネットワークは、エリアA〜エリアDを有している。エリアAはノード1を有し、エリアBはノード2を有し、エリアCはノード3,4を有し、エリアDはノード5を有している。
【0020】
ノード1は、経路算出部1aおよび記憶部1bを有している。経路算出部1aは、始点ノードから終点ノードに至る経路を算出する。例えば、経路算出部1aは、ダイクストラ法などに基づいて自分(ノード1)からノード5までの経路を算出する。
【0021】
記憶部1bは、経路算出部1aの算出する経路が通過するエリアA〜Dを示す通過エリアリストを記憶する。
経路算出部1aは、始点ノードから終点ノードに至る経路を算出する際、記憶部1bの通過エリアリストを参照し、同じエリアを複数回通過する経路を経路算出対象から除外する。
【0022】
例えば、経路算出部1aは、ノード1,3,2までの経路を算出し、記憶部1bには、経路算出部1aの算出した経路が通過するエリアA,C,Bを示す通過エリアリスト‘A,C,B’が記憶されているとする。
【0023】
経路算出部1aは、次の経路候補としてノード4を抽出したとする。ノード4は、エリアCに属しており、経路算出部1aは、記憶部1bの通過エリアリスト‘A,C,B’に基づき、ノード4の経路はエリアCを2回通過することになると認識する。そこで、経路算出部1aは、ノード4の経路を経路算出対象から除外する。これにより、経路算出部1aは、例えば、同一エリアを複数回通過しないノード1,3,4,5の経路を算出することが可能となる。
【0024】
このように、ノード1は、経路を算出する際、経路が通過するエリアを示した通過エリアリストを記憶する。そして、ノードは、通過エリアリストに基づいて1度通過したエリアを再び通過することになる経路を経路算出対象から除外する。これにより、マルチエリアネットワークの管理を容易にすることができる。
【0025】
次に、第2の実施の形態を、図面を参照して詳細に説明する。
図2は、第2の実施の形態に係るエリア内ルーティングを説明する図である。図2には、マルチエリアネットワークが示してある。マルチエリアネットワークは、エリアA〜エリアDを有している。エリアAはノードN31〜N36を有し、エリアBはノードN10,N11を有し、エリアCはノードN21を有し、エリアDはノードN40,N41を有している。各ノード間に示す数字は、リンクコストを示している。ノードは、例えば、ルータやスイッチなどの通信装置である。
【0026】
マルチエリアネットワークでは、エリア毎にエリア内ルーティングプロトコルが動作する。エリア内ルーティングプロトコルが動作する全てのノードは、各ノードのリンク情報をエリア内全てのノードへ通知する。これによって、エリア内の全てのノードは、エリア内のトポロジーを把握することができる。
【0027】
図3は、エリア間ルーティングを説明する図である。図3において、図2と同じものには同じ符号を付し、その説明を省略する。
図3の例では、エリア境界ノードのノードN11,N21,N31〜N33,N41がエリア間ルーティングに参加しているものとする。また、図2に示したように、各リンクのリンクコストを1とする。
【0028】
エリア間ルーティングに参加するノードでは、エリア間ルーティングプロトコルが動作する。エリア間ルーティングに参加するノードは、例えば、エリア内のトポロジー情報を要約した仮想リンクの情報をエリア間ルーティングに参加する全てのノードに通知する。また、エリア間ルーティングに参加するノードは、エリア間リンクの情報をエリア間ルーティングに参加する全てのノードに通知する。また、エリア間ルーティングプロトコルに参加するノードは、自分の属しているエリアのエリアIDをエリア情報としてエリア間ルーティングに参加する全てのノードに通知する。
【0029】
例えば、ノードN31は、エリアB内のトポロジー情報を基に、エリア境界ノードのノードN32,N33までの到達経路を、リンクコスト5およびリンクコスト4の仮想リンク情報として、エリア間ルーティングに参加する全ノードに通知する。また、ノードN31は、ノードN31−N11,N31−N21のエリア間リンク情報をエリア間ルーティングに参加する全ノードに通知する。また、ノードN31は、自分の属するエリアID‘A’のエリア情報をエリア間ルーティングに参加する全ノードに通知する。他のエリア間ルーティングに参加するノードも同様に、仮想リンク情報、エリア間リンク情報、およびエリア情報を通知する。これにより、図3に示すエリア間のトポロジーの情報がエリア間ルーティングに参加するノードの間で交換され、エリア間ルーティングに参加するノードはエリア間トポロジー情報とエリア情報とを保持することができる。
【0030】
図4は、各ノードに保持されるエリア間トポロジー情報を示した図である。エリア間ルーティングに参加するノードは上述したように、例えば、図3に示すエリア間トポロジーの情報をエリア間ルーティングプロトコルで交換し、図4に示すようなエリア間トポロジー情報を保持する。例えば、エリア間ルーティングに参加するノードは、エリア間ルーティングに参加するノードのリンク情報と、そのリンク情報のリンク間のリンクコストとを保持している。
【0031】
図5は、各ノードに保持されるエリア情報を示した図である。エリア間ルーティングに参加するノードは上述したように、例えば、図3に示すエリア間トポロジーの情報をエリア間ルーティングプロトコルで交換し、図5に示すようなエリア情報を保持する。例えば、エリア間ルーティングに参加するノードは、ノード情報と、そのノード情報のノードの属するエリアのエリアIDとを保持している。
【0032】
なお、エリア境界ノード以外のノードがエリア間ルーティングに参加してもよい。例えば、図2に示すノードN10,N40もエリア間ルーティングに参加できる。この場合、ノードN10,N40のトポロジー情報も図4に示したエリア間トポロジー情報に含まれる。また、ノードN10,N40のエリア情報も図5に示したエリア情報に含まれる。
【0033】
図6は、ノードのブロック図である。図6に示すようにノードは、データ受信部11、データ種別判定部12、データ送信部13、エリア内RT(RT:RouTing)処理部20、およびエリア間RT処理部30を有している。エリア内RT処理部20は、エリア内RT制御パケット受信部21、エリア内RT制御パケット処理部22、エリア内RT情報生成部23、エリア内RT制御パケット送信部24、およびエリア内情報DB(DB:Data Base)25を有している。エリア間RT処理部30は、エリア間RT制御パケット受信部31、エリア間RT制御パケット処理部32、エリア間RT情報生成部33、エリア間RT制御パケット送信部34、エリア間経路計算処理部35、およびエリア間情報DB36を有している。
【0034】
データ受信部11は、ネットワークからデータを受信する。
データ種別判定部12は、データ受信部11によって受信されたデータを解析し、エリア内ルーティングプロトコルの制御パケットであるか、エリア間ルーティングプロトコルの制御パケットであるか、またはユーザデータのパケットであるかを判定する。データ種別判定部12は、エリア内ルーティングプロトコルの制御パケットが受信された場合、エリア内RT制御パケット受信部21へ出力する。データ種別判定部12は、エリア間ルーティングプロトコルの制御パケットが受信された場合、エリア間RT制御パケット受信部31へ出力する。データ種別判定部12は、ユーザデータのパケットが受信された場合、図示していないユーザRT処理部へ出力する。
【0035】
エリア内RT処理部20のエリア内RT制御パケット受信部21は、受信された制御パケットのヘッダを解析し、正常な制御パケットである場合には、エリア内RT制御パケット処理部22へ出力する。
【0036】
エリア内RT制御パケット処理部22は、受信した制御パケットに含まれているエリア内のトポロジー情報およびエリア内RT情報生成部23で生成されたトポロジー情報をエリア内情報DB25に記憶する。エリア内RT制御パケット処理部22は、生成されたトポロジー情報をエリア内情報DB25に記憶した後、受信ポート以外の全てのポートへ転送するため、エリア内RT制御パケット送信部24へ制御パケットを出力する。
【0037】
エリア内RT情報生成部23は、隣接しているノードの情報やそのノードを接続しているリンクのリンクコストを有するトポロジー情報を生成し、エリア内RT制御パケット処理部22へ出力する。
【0038】
エリア内RT制御パケット送信部24は、エリア内RT制御パケット処理部22から出力される制御パケットの適切なヘッダを生成し、データ送信部13に出力する。
エリア内情報DB25には、エリア内のトポロジー情報が格納される。
【0039】
エリア間RT処理部30のエリア間RT制御パケット受信部31は、受信された制御パケットのヘッダを解析し、正常な制御パケットである場合には、エリア間RT制御パケット処理部32へ出力する。
【0040】
エリア間RT制御パケット処理部32は、受信した制御パケットに含まれているエリア間のトポロジー情報およびエリア間RT情報生成部33で生成されたトポロジー情報とエリア情報とをエリア間情報DB36に記憶する。また、エリア間RT制御パケット処理部32は、受信した制御パケットに含まれている、制御パケットを送信したノードの属しているエリア情報をエリア間情報DB36に記憶する。エリア間RT制御パケット処理部32は、生成されたトポロジー情報とエリア情報とをエリア間情報DB36に記憶した後、受信ポート以外の全てのポートへ転送するため、エリア間RT制御パケット送信部34へ制御パケットを出力する。
【0041】
エリア間RT情報生成部33は、隣接しているノードの情報やそのノードを接続しているリンクのリンクコストを有するトポロジー情報を生成し、エリア間RT制御パケット処理部32へ出力する。エリア間RT情報生成部33は、エリア内情報DB25のエリア内トポロジー情報を基に、仮想リンク等のエリア間トポロジー情報を生成し、エリア間RT制御パケット処理部32へ出力する。また、エリア間RT情報生成部33は、自ノードが属するエリアのエリア情報を生成し、エリア間RT制御パケット処理部32へ出力する。
【0042】
エリア間RT制御パケット送信部34は、エリア間RT制御パケット処理部32から出力される制御パケットの適切なヘッダを生成し、データ送信部13に出力する。
エリア間経路計算処理部35は、エリア間情報DB36に記憶されているエリア間のトポロジー情報とエリア情報に基づいて、指定された始点のノードから終点(宛先)のノードまでの経路を算出する。エリア間経路計算処理部35は、一度通過したエリアを再度通過することがなく、例えば、ダイクストラ法等を用いてリンクコストが小さくなる経路を算出する。
【0043】
エリア間情報DB36には、エリア間のトポロジー情報とエリア情報が格納される。例えば、図4に示したエリア間トポロジー情報と図5に示したエリア情報とが格納される。
図7は、エリア間経路計算処理部のブロック図である。図7に示すようにエリア間経路計算処理部35は、経路算出部41および記憶部42を有している。
【0044】
経路算出部41は、経路計算処理中に得られた経路候補群の中から次に計算すべき経路を抽出する。また、経路算出部41は、抽出した経路が同一エリアを複数回通過しているか否かを、記憶部42に記憶されている、経路が通過したエリアを示す通過エリアリストを基に判定する。また、経路算出部41は、抽出した経路とすでに得られている他の経路とのリンクコストを比較する。また、経路算出部41は、記憶部42の通過エリアリストに経路が通過したエリアを記憶する。また、経路算出部41は、経路が通過するリンクのリンクコストを記憶部42に記憶する。
【0045】
記憶部42は、経路算出部41によって算出される経路の通過するエリアを示す通過エリアリストや、経路の通過するリンクのリンクコストの情報を記憶する。
図8は、マルチエリアネットワークの経路計算を説明する図である。図8には、経路算出部41が経路計算するマルチエリアネットワークの例が示してある。図8のマルチエリアネットワークは、エリアX,A,B,Yを有している。エリアXはノードN11を有し、エリアAはノードN13,N14を有し、エリアBはノードN12,N16,N17を有し、エリアYはノードN15を有している。各ノード間に示す数字は、リンクコストを示している。ノードN11〜N17は、エリア境界ノードであり、エリア間ルーティングに参加しているものとする。
【0046】
ノードN11の経路算出部41は、自分(ノードN11)からノードN15までの経路を算出するとする。ノードN11の経路算出部41は、例えば、ネットワーク管理者からのコマンドに基づいて、目的のノードN15までの経路を算出する。または、エリアXに属する他のノードがネットワーク管理者からのコマンドに基づいて、ノードN11からノードN15までの経路を算出してもよい。この場合、経路を算出したノードは、ノードN11に算出結果を通知する。
【0047】
なお、経路算出部41は、エリア間情報DB36に記憶されているトポロジー情報に基づき、図8に示すマルチエリアネットワークのトポロジーを認識することができる。
経路算出部41は、ダイクストラ法に基づき目標とする経路を算出していく。このとき、経路算出部41は、算出した経路(ノード)までの到達距離(リンクコストの合計)と、算出した経路が通過したエリアのエリアIDを記憶部42の通過エリアリストに記憶していく。
【0048】
例えば、経路算出部41は、ノードN11,N12,N13までの経路を確定した場合、図8のノードN11の下部に示すように、リンクコスト‘0’、通過エリアリスト‘X’を記憶部42に記憶している。また、図8のノードN12の下部に示すように、ノードN11からノードN12までのリンクコスト‘1’と、ノードN11からノードN12までの経路が通過したエリアの通過エリアリスト‘X,B’を記憶部42に記憶している。また、図8のノードN13の上部に示すように、ノードN11からノードN13までのリンクコスト‘2’と、ノードN11からノードN13までの経路が通過したエリアの通過エリアリスト‘X,B,A’を記憶部42に記憶している。また、図8のノードN17の下部に示すように、ノードN11からノードN17までのリンクコスト‘6’と、ノードN11からノードN17までの経路が通過したエリアの通過エリアリスト‘X,B’を記憶部42に記憶している。また、図8のノードN14の上部に示すように、ノードN11からノードN14までのリンクコスト‘3’と、ノードN11からノードN14までの経路が通過したエリアの通過エリアリスト‘X,B,A’を記憶部42に記憶している。
【0049】
なお、経路算出部41は、エリア間情報DB36に記憶されているエリア情報に基づいて通過エリアリストを生成し、記憶部42に記憶することができる。
経路算出部41は、ダイクストラ法により、最短経路が未確定であるノード群から、リンクコストの最も小さいノードを抽出する。例えば、経路算出部41は、ノードN13を最後に確定ノードとした場合、次にノードN14を抽出することになる。
【0050】
経路算出部41は、抽出したノードN14の有するリンクの端点となる隣接ノード(図8の場合、ノードN15,N16)を選択する。ここでは、ノードN16を選択したとする。経路算出部41は、抽出したノードN14の通過エリアリストの最後以外に、選択したノードN16のエリアIDが含まれているか判断する。経路算出部41は、抽出したノードN14の通過エリアリストの最後以外に、選択したノードN16のエリアIDが含まれている場合、選択したノードN16の経路を経路算出候補から除く。
【0051】
ここで、抽出したノードN14の通過エリアリストは‘X,B,A’である。この通過エリアリストの最後‘A’以外には、選択したノードN16のエリアID‘B’が含まれている。従って、経路算出部41は、抽出したノードN14の通過エリアリストの最後以外に、選択したノードN16のエリアIDが含まれているので、選択したノードN16の経路を経路算出候補から除く。
【0052】
すなわち、経路算出部41は、ノードN12で一旦エリアBに入り、その後エリアAを経由して再びエリアBに入る経路を経路算出候補から除外する。そして、経路算出部41は、ノードN14からノードN16の経路を除外して、別の経路をダイクストラ法により算出する。
【0053】
つまり、経路算出部41は、ダイクストラ法によって経路算出を行うとともに算出した経路の通過エリアリストを記憶する。そして、経路算出部41は、通過エリアリストに基づいて、一度通過したエリアを再び通過することになるか否かを判断し、一度通過したエリアを再び通過することになると判断した場合、その経路を除外してダイクストラ法の処理を進めていく。
【0054】
なお、図8の例の場合、ノードN11,N12,N17,N16,N15の経路が算出される。
図9は、経路算出部のフローチャートである。
【0055】
[ステップS1]経路算出部41は、全ノードにおける、始点ノードからの到達距離を無限大に設定し、始点ノードの到達距離を0に設定する。さらに、経路算出部41は、全ノードを最短経路未確定ノードとしてマークする(記憶部42に記憶する)。
【0056】
[ステップS2]経路算出部41は、最短経路が未確定であるとマークされたノード群の中から、始点ノードからの到達距離が最短となるノードを抽出する。
[ステップS3]経路算出部41は、ノードを抽出できなかった場合、終点ノードへの到達距離が存在しないことになるので処理を終了する。経路算出部41は、ノードを抽出できた場合、ステップS4へ進む。
【0057】
[ステップS4]経路算出部41は、抽出されたノードが終点ノードであるか否かを判断する。経路算出部41は、抽出したノードが終点ノードであった場合、最短経路が算出されたことになるので処理を終了する。経路算出部41は、抽出したノードが終点ノードでなかった場合、ステップS5へ進む。
【0058】
[ステップS5]経路算出部41は、抽出ノードを最短経路確定ノードとしてマークする。
[ステップS6]経路算出部41は、抽出ノードの有するリンク数分、ステップS13までの処理を繰り返す。なお、ステップS6からステップS13までの処理の対象となっているリンクを対象リンクと呼ぶ。
【0059】
[ステップS7]経路算出部41は、抽出ノードの有する通過エリアリストのエリアIDのうち、最後のエリアID以外で、対象リンクの端点となる隣接ノードのエリアIDと同一のものが含まれているか判断する。
【0060】
[ステップS8]経路算出部41は、同一のエリアIDが含まれていない場合には、ステップS9の処理へ進む。経路算出部41は、同一のエリアIDが含まれている場合には、次のリンク処理へ移るためステップS6へ進む。すなわち、経路算出部41は、一度通過したことのあるエリアに再び戻る経路を経路計算から除外する。
【0061】
[ステップS9]経路算出部41は、対象リンクの隣接ノードにおける新しい到達距離を算出する。隣接ノードにおける始点ノードからの到達距離は、抽出ノードまでの到達距離と対象リンクのリンクコストの和として求められる。
【0062】
[ステップS10]経路算出部41は、算出した隣接ノードの新しい到達距離と、すでに得られている隣接ノードの到達距離とを比較する。経路算出部41は、新しい到達距離がすでに得られている到達距離に対し小さい場合は、ステップS11へ進む。経路算出部41は、新しい到達距離がすでに得られている到達距離に対し小さくない場合は、次のリンク処理へ移るためステップS6へ進む。
【0063】
[ステップS11]経路算出部41は、隣接ノードの到達距離をステップS9で算出された新しい値に更新する。
[ステップS12]経路算出部41は、抽出ノードの通過エリアリストに記載されている最後のエリアIDと、隣接ノードのエリアIDとを比較する。経路算出部41は、通過エリアリストに記載されている最後のエリアIDと、隣接ノードのエリアIDとが異なる場合には、抽出ノードの通過エリアリストの最後に隣接ノードのエリアIDを追加して隣接ノードの通過エリアリストとして記憶する。経路算出部41は、通過エリアリストに記載されている最後のエリアIDと、隣接ノードのエリアIDとが同じである場合には、抽出ノードの通過エリアリストをそのまま隣接ノードの通過エリアリストとして記憶する。
【0064】
[ステップS13]経路算出部41は、対象リンクが残っている場合には、ステップS6へ進む。経路算出部41は、対象リンクが残っていない場合には、ステップS2へ進む。
【0065】
このように、経路算出部41は、ダイクストラ法により経路を算出するとともに、算出した経路の通過エリアを記憶する。これにより、経路算出部41は、到達距離が小さく、かつ、同一エリアを通過しないように経路を算出することができ、マルチエリアネットワークの管理を容易にすることができる。
【0066】
次に、第3の実施の形態を、図面を参照して詳細に説明する。第2の実施の形態では、各ノードへ到達する経路を1経路だけ保持しながら計算を進める。そのため、第2の実施の形態では、到達距離の小さい経路を算出するようにしているが、マルチエリアネットワークのトポロジーによっては、より到達距離の小さい経路を算出できない場合が存在する。第3の実施の形態では、各ノードへ到達する複数の経路と、それらの経路が通過する通過エリアリストを保持することによって、適切な経路を算出することができるようにする。
【0067】
図10は、到達距離の小さい経路を算出することができない場合のマルチエリアネットワークの例を示した図である。図10のマルチエリアネットワークは、エリアA〜Eを有している。エリアAはノードN10を有し、エリアBはノードN21,N22を有し、エリアCはノードN31を有し、エリアDはノードN41を有し、エリアEはノードN51を有している。各ノード間に示す数字はリンクコストを示している。ノードN10を始点ノード、ノードN22を終点ノードとする。
【0068】
ノードN10からノードN22までの経路は、例えば、ノードN10,N31,N41,N51,N22の経路R1と、ノードN10,N21,N41,N51,N22の経路R2と、ノードN10,N21,N22の経路R3とが考えられる。それぞれの経路R1〜R3のリンクコストは、8、4、11となる。
【0069】
ここで、経路R2は、リンクコストが最も小さいがエリアBを一度通過しており望ましい経路でない。また、経路R3は、経路R1よりリンクコストが大きいため望ましい経路でない。従って、経路R1が望ましい経路となる。
【0070】
第2の実施の形態では、ダイクストラ法により、最短の到達距離を有するノードを選択し、最短経路確定ノードの領域を広げていく。そのため、図10の例では、ノードN31を経由した経路が算出されない。すなわち、経路R1を算出したいが、第2の実施の形態では経路R3が算出される。
【0071】
なお、第3の実施の形態においてもノードは、図6、図7と同様のブロックを有する。ただし、経路算出部41の機能が異なる。
図11は、第3の実施の形態に係るマルチエリアネットワークの経路計算を説明する図である。図11のマルチエリアネットワークは、エリアA〜Cを有している。エリアAはノードN11を有し、エリアBはノードN12〜N15を有し、エリアCはノードN16,N17を有している。
【0072】
各ノードは、図11に示すように、リンクL1〜L8によって接続されている。各ノード間に示す数字はリンクコストを示している。ノードN11を始点ノード、ノードN15を終点ノードとする。
【0073】
ノードN11の経路算出部41は、始点である自分(ノードN11)に接続されている全てのリンクL1,L4を記憶部42の計算候補リストに登録する。経路算出部41は、リンクL1,L4の到達距離を記憶部42に記憶し、始点のノードN11のエリアID‘A’をリンクL1,L4の通過エリアリストとして記憶部42に記憶する。これにより、例えば、図11のノードN12の上部に示すように‘1’,‘A’の情報と、ノードN16の下部に示すように‘5’,‘A’の情報が記憶部42に記憶される。
【0074】
経路算出部41は、計算候補リストのうち、最短の到達距離を有するリンクを抽出する。上記例の場合、リンクL1を抽出する。経路算出部41は、抽出したリンクL1を計算候補リストから削除する。
【0075】
経路算出部41は、抽出したリンクL1の終端点のノードN12の有するリンクL2,L8を抽出する。以下、抽出したリンクL1と、その終端点のノードN12から伸びるリンクL2,L8を区別するため、リンクL2,L8を新規リンクと呼ぶ。
【0076】
経路算出部41は、抽出したリンクL1の通過エリアリスト‘A’の最後以外のエリアIDと、新規リンクL2,L8の終端点のノードN14,N13のエリアIDとが同じか判断する。
【0077】
経路算出部41は、エリアIDが同じであれば、新規リンクによる経路の算出を除外する。すなわち、経路算出部41は、一度通過したエリアを再び通過することになる経路を経路計算から除外する。
【0078】
一方、経路算出部41は、エリアIDが異なれば、新規リンクを計算候補リストに登録する。また、経路算出部41は、新規リンクまでの到達距離を記憶部42に記憶する。そして、経路算出部41は、抽出したリンクの始端点ノードと終端点ノードのエリアが異なる場合、抽出したリンクの通過エリアリストの最後に、新規リンクの始端点ノードの属するエリアIDを追加して、新規リンクの通過エリアリストとする。経路算出部41は、抽出したリンクの始端点ノードと終端点ノードのエリアが同じ場合、抽出したリンクの通過エリアリストを新規リンクの通過エリアリストとする。
【0079】
上記例の場合、抽出したリンクL1の通過エリアリスト‘A’の最後以外のエリアID(この場合はなし)と、新規リンクL2,L8の終端点のノードN14,N13のエリアIDが異なるので、経路算出部41は、新規リンクL2,L8を計算候補リストに登録する。また、経路算出部41は、新規リンクL2,L8までの到達距離‘2’,‘21’を記憶部42に記憶する。そして、経路算出部41は、抽出したリンクL1の始端点ノードと終端点ノードのエリアが異なるので、抽出したリンクL1の通過エリアリスト‘A’の最後に、新規リンクL2,L8の始点のノードN12の属するエリアID‘B’を追加して、新規リンクL2,L8の通過エリアリストとする。
【0080】
これにより、例えば、図11のノードN13の上部に示すように‘21’,‘AB’の情報が記憶部42に記憶される。また、ノードN14の上部に示すように‘2’,‘AB’の情報が記憶部42に記憶される。
【0081】
なお、上記例の場合、リンクL1は計算候補リストから削除され、新規リンクL2,L8は計算候補リストに登録されているので、現在の計算候補リストには、リンクL2,L4,L8が登録されていることになる。それぞれの到達距離は、2,5,21である。
【0082】
経路算出部41は、計算候補リストの中から、到達距離の最も小さいリンクを抽出する。上記例の場合、経路算出部41は、リンクL2を抽出する。経路算出部41は、抽出したリンクL2を計算候補リストから削除する。
【0083】
経路算出部41は、上記と同様に、抽出したリンクL2から伸びるリンクL3,L7を新規リンクとし、上記と同様の処理を行う。
経路算出部41は、新規リンクの終端点のノードが一度通過したエリアに属している場合にはその新規リンクの経路を経路算出対象から除く。一方、経路算出部41は、新規リンクの終端点ノードが一度通過したエリアに属していない場合には、その新規リンクの到達距離を記憶し、通過エリアリストを記憶する。これにより、例えば、図11のノードN16の下部に示すように到達距離‘7’と通過エリアリスト‘AB’の情報が記憶部42に記憶される。また、ノードN15の上部に示すように到達距離‘12’と通過エリアリスト‘AB’の情報が記憶部42に記憶される。なお、計算候補リストは、リンクL2が削除され、L3,L4,L7,L8となる。
【0084】
すなわち、経路算出部41は、計算候補リストから最短の到達距離を有するリンクを抽出し、そのリンクの終端点のノードから新規リンクを伸ばし、伸ばした新規リンクが一度通過したエリアに戻っていなければ、新規リンクを計算候補リストに追加していく。
【0085】
これにより、同じノードに到達する、異なる経路のリンクが複数計算候補リストに登録される場合がある。例えば、図11の例の場合、ノードN16に到達するリンクとしてリンクL4とリンクL3が計算候補リストに登録される。つまり、経路算出部41は、各ノードへ到達する複数の経路を記憶することによって、適切な経路を算出することができる。
【0086】
図12は、経路算出部のフローチャートである。
[ステップS21]経路算出部41は、始点ノードに接続されている全リンクを計算候補リストに登録する。そして、経路算出部41は、始点ノードからリンクの終端点へ至る経路情報として、始点ノードからリンクの終端点へ至る到達距離と、始点ノードからリンクの終端点へ至る経路が通過するエリアを通過エリアリストとして記憶部42に記憶する。すなわち、経路算出部41は、始点ノードから伸びる各リンクのリンクコストを到達距離として記憶し、始点ノードの属するエリアのエリアIDを通過エリアリストとして記憶部42に記憶する。
【0087】
[ステップS22]経路算出部41は、計算候補リストの中から到達距離の最も小さいリンクを抽出する。
[ステップS23]経路算出部41は、リンクを抽出できなかった場合、終点ノードへの到達経路が存在しないことになるので、処理を終了する。経路算出部41は、リンクを抽出できた場合、ステップS24へ進む。
【0088】
[ステップS24]経路算出部41は、抽出したリンクの終端点のノードが終点ノードであるか否かを判断する。経路算出部41は、終点ノードであると判断した場合、最短経路が算出されたことになるので処理を終了する。経路算出部41は、終点ノードでなかった場合には、ステップS25へ進む。
【0089】
[ステップS25]経路算出部41は、抽出リンクを計算候補リストから削除する。
[ステップS26]経路算出部41は、抽出リンクの終端点のノードが有している全てのリンクに対して、順にステップS32までの処理を行う。以下では、抽出リンクの終端点のノードから伸びている処理対象となっているリンクを新規リンクと呼ぶ。
【0090】
[ステップS27]経路算出部41は、抽出リンクの通過エリアリストに記憶されているエリアIDのうち、最後のエリアID以外のエリアIDで、新規リンクの終端点のノードの属するエリアIDと同一のものがあるか否かを判断する。
【0091】
[ステップS28]経路算出部41は、同一のエリアIDが含まれていない場合には、ステップS29の処理へ進む。経路算出部41は、同一のエリアIDが含まれている場合には、次の新規リンクの処理へ移るためステップS26へ進む。すなわち、経路算出部41は、一度通過したことのあるエリアに再び戻る経路を経路計算対象から除外する。
【0092】
[ステップS29]経路算出部41は、新規リンクの新しい到達距離(抽出リンクの到達距離+新規リストのリンクコスト)を記憶部42に記憶する。また、経路算出部41は、新規リンクへの経路として、抽出リンクの経路に抽出リンクの始端点のノードを追加した通過ノードリストを記憶部42に記憶する。
【0093】
[ステップS30]経路算出部41は、抽出リンクの始端点のノードと終端点のノードでエリアIDが異なる場合には、抽出リンクの通過エリアリストの最後に新規リンクの始端点のノードのエリアIDを追加し、新規リンクの通過エリアリストとして記憶部42に記憶する。また、経路算出部41は、抽出リンクの始端点のノードと終端点のノードでエリアIDが同じである場合には、抽出リンクの通過エリアリストを新規リンクの通過エリアリストとして記憶部42に記憶する。
【0094】
[ステップS31]経路算出部41は、新規リンクを計算候補リストに追加する。このとき、同じノードに到達する異なるリンクが計算候補リストに登録される場合もある。つまり、経路算出部41は、あるノードに到達するリンクが複数存在する場合、異なる経路距離を持つリンクとして、多重に計算候補リストに登録する。このように、経路算出部41は、複数の経路を記憶することによって、同一エリアを通過しない到達距離の短い経路を算出することが可能となる。
【0095】
[ステップS32]経路算出部41は、新規リンクが残っている場合には、ステップS26へ進む。経路算出部41は、新規リンクが残っていない場合には、ステップS22へ進む。
【0096】
このように、経路算出部41は、複数の経路を記憶しながら、かつ、同一エリアに戻る経路を除外して経路計算を進めていく。これにより、最短経路を算出することが可能となる。
【0097】
次に、第4の実施の形態を、図面を参照して詳細に説明する。第2の実施の形態では、各ノードにおいて経路が通過する全てのエリアIDを通過エリアリストに追加しながら経路計算を進める。第3の実施の形態では、各ノードに到達可能な複数の経路において、その経路が通過する全てのエリアIDを通過エリアリストに追加しながら、経路計算を進める。そのため、ノードは、多くの情報を記憶するための記憶領域が必要になるとともに、記憶した情報をチェックする量も増加し、経路計算負荷が高くなる。第4の実施の形態では、ノードの記憶容量および計算負荷の低減を図る。
【0098】
図13は、第4の実施の形態に係る経路計算で経路を求めることができないマルチエリアネットワークの例を示した図である。図13のマルチエリアネットワークは、エリアA〜Eを有している。エリアAはノードN11を有し、エリアBはノードN21〜N24を有し、エリアCはノードN31,N32を有し、エリアDはノードN41,N42を有し、エリアEはノードN51を有している。ノードN11を始点ノード、ノードN51を終点ノードとする。
【0099】
第4の実施の形態では、ダイクストラ法によって経路を算出するとともに、経路が1つ前に通過したエリアのエリアIDを記憶部に記憶する。すなわち、第4の実施の形態では、経路が通過してきた全てのエリアを記憶部に記憶しない。従って、複数の異なるエリアを跨って再び同一エリアに戻るマルチエリアネットワークのトポロジーでは、同一エリアを通過する経路計算を許可してしまう。
【0100】
例えば、図13においてノードN42では、1つ前に通過したエリアCのエリアIDしか記憶部に記憶していない。従って、第4の実施の形態では、同一のエリアBを再び通過するノードN23の経路を経路計算対象から除外せずに計算してしまう。
【0101】
一方、図2に示したようなマルチエリアネットワークのトポロジーでは、第4の実施の形態に係る経路計算によっても同一エリアを再び通過する経路を除外することができる。すなわち、第4の実施の形態では、スター型のトポロジーを有するマルチエリアネットワークにおいて適用することができる。
【0102】
なお、第4の実施の形態においてもノードは、図6、図7と同様のブロックを有する。ただし、経路算出部41の機能が異なる。また、図8に示したマルチエリアネットワークを第4の実施の形態に係る経路算出部41で経路計算した場合、図8に示すノードN11,N12,N13,N14,N16,N17の通過エリアリストは、それぞれX,X,B,B,X,Xとなる。すなわち、第4の実施の形態では、各ノードの通過エリアリストは、1つのエリアIDを記憶すればよい。以下では、第4の実施の形態に係る通過エリアリストを通過エリア情報と呼ぶ。
【0103】
図14は、経路算出部のフローチャートである。
ステップS41からステップS46までの処理は、図9のフローチャートのステップS1からステップS6までの処理と同じであり、その説明を省略する。
【0104】
[ステップS47]経路算出部41は、抽出ノードの有する通過エリア情報が示しているエリアIDと、対象リンクの端点となる隣接ノードのエリアIDが同じであるか否か判断する。
【0105】
[ステップS48]経路算出部41は、抽出ノードの有する通過エリア情報のエリアIDと、対象リンクの端点となる隣接ノードのエリアIDが同じである場合、ステップS46に進む。経路算出部41は、同じでない場合、ステップS49へ進む。
【0106】
[ステップS49]経路算出部41は、対象リンクの隣接ノードにおける新しい到達距離を算出する。隣接ノードにおける始点ノードからの到達距離は、抽出ノードまでの到達距離と対象リンクのリンクコストの和として求められる。
【0107】
[ステップS50]経路算出部41は、算出した隣接ノードの新しい到達距離と、すでに得られている隣接ノードの到達距離とを比較する。経路算出部41は、新しい到達距離がすでに得られている到達距離に対し小さい場合は、ステップS51へ進む。経路算出部41は、新しい到達距離がすでに得られている到達距離に対し小さくない場合は、次のリンク処理へ移るためステップS46へ進む。
【0108】
[ステップS51]経路算出部41は、隣接ノードの到達距離をステップS49で算出された新しい値に更新する。
[ステップS52]経路算出部41は、抽出ノードと隣接ノードのエリアIDを比較する。経路算出部41は、エリアIDが異なる場合には、抽出ノードのエリアIDを隣接ノードの通過エリア情報として記憶部42に記憶する。経路算出部41は、エリアIDが同じである場合には、抽出ノードの通過エリア情報を隣接ノードの通過エリア情報として記憶部42に記憶する。
【0109】
[ステップS53]経路算出部41は、対象リンクが残っている場合には、ステップS46へ進む。経路算出部41は、対象リンクが残っていない場合には、ステップS42へ進む。
【0110】
このように、経路算出部41は、ダイクストラ法により経路を算出するとともに、算出した経路の1つ前に通過したエリアを記憶する。これにより、経路算出部41は、記憶部42に記憶する情報量を低減でき、また、経路計算の処理負荷を低減することができる。
【0111】
次に、第5の実施の形態を、図面を参照して詳細に説明する。第5の実施の形態では、あるエリア内で障害が発生した場合の経路計算について説明する。
図15は、第5の実施の形態に係るマルチエリアネットワークを説明する図である。図15のマルチエリアネットワークは、図2のマルチエリアネットワークと同様であり、その説明を省略する。
【0112】
図15に示すように、エリアAのノードN35に障害が発生したとする。この場合、エリア間ルーティングプロトコルでは、ノードN31−N33間の仮想リンク、ノードN31−N32間の仮想リンクのリンク情報が通知されないか、あるいは障害リンクとして通知される。
【0113】
図16は、エリア間ルーティングで交換されるトポロジー情報を説明する図である。図15のノードN35で障害が発生した場合、図16に示すように、ノードN31−N33間の仮想リンク、ノードN31−N32間の仮想リンクで障害が発生したことになり、ノードN31−N33間の仮想リンク、ノードN31−N32間の仮想リンクのリンク情報が通知されないか、あるいは障害リンクとして通知される。
【0114】
このような場合に、上述した実施の形態の経路算出部41によってノードN11からノードN41までの経路を計算した場合には、同一エリアを複数回通過しない経路が存在しないため、経路が算出されない。そこで、第5の実施の形態では、経路算出部41によって経路計算できない場合は、ダイクストラ法に切り替えて経路の再計算を行う。
【0115】
図16の場合、経路算出部41は、ダイクストラ法によって再計算を行うことにより、ノードN11,N31,N21,N32,N33,N41のエリアAを2回通過する経路を算出することができる。
【0116】
このように、経路算出部41は、障害発生により、経路を算出することができないときはダイクストラ法によって経路を再計算する。これにより、経路算出部41は、障害が発生したときでも経路を算出することができる。
【0117】
次に、第6の実施の形態を、図面を参照して詳細に説明する。経路計算において、同一エリアの通過を許可しない場合、場合によってはリンクコストが非常に大きくなる場合もある。第6の実施の形態では、同一エリアを通過する経路の許容回数を指定し、より小さいリンクコストの経路を選択するようにする。
【0118】
図17は、第6の実施の形態に係るマルチエリアネットワークの経路計算を説明する図である。図17のマルチエリアネットワークは、エリアA〜Dを有している。エリアAはノードN11〜N14を有し、エリアBはノードN21を有し、エリアCはノードN31を有し、エリアDはノードN41を有している。各ノード間に示す数字は、リンクコストを示している。なお、ノードN11−N12間、ノードN12−N13間、ノードN13−N14間は、仮想リンクのリンクコストを示している。ノードN11を始点ノード、ノードN14を終点ノードとする。
【0119】
ノードN11からノードN14までに至る同一エリアを複数回通過しない経路は、ノードN11,N12,N13,N14を通過する経路になる。この経路は、総リンクコストが30となり、非常にリンクコストが大きい経路となる。
【0120】
しかし、他のエリアB〜Dに出て行くことを許すと、エリアAを4回通過することになるが、最短リンクコスト6のノードN11,N21,N12,N31,N13,N41,N14の経路を得ることができる。一般的には、管理者は、同一エリアを通過する回数とリンクコストのバランスを考慮して経路を選択することになる。
【0121】
第6の実施の形態では、同一エリアを通過する許容回数を指定することにより、より小さいコストの経路を選択することを可能とする。許容回数は、例えば、ネットワークの管理者によって指定される。
【0122】
例えば、図17に示すようなマルチエリアネットワークにおいて、エリアAの通過を許容できる許容回数を2回とした場合には、ノードN11,N12,N13,N41,N14の総リンクコスト‘17’の経路を算出できる。あるいは、許容回数を3回とした場合には、ノードN11,N12,N31,N13,N41,N14の総リンクコスト‘9’の経路を算出できる。
【0123】
なお、第6の実施の形態においてもノードは、図6、図7と同様のブロックを有する。ただし、経路算出部41の機能が異なる。経路算出部41は、第3の実施の形態と同様の機能を有する。ただし、第3の実施の形態の経路算出部41では、同一エリアを通過することになる新規リンクは経路計算から除外したが、第6の実施の形態に係る経路算出部41では、除外しない。すなわち、第6の実施の形態に係る経路算出部41は、始点ノードから終点ノードに至る経路を複数計算する。そして、各経路の通過エリアリストを参照して同じエリアを許容回数以下で通過する経路を抽出し、抽出した経路の中からリンクコストの最も小さい経路を選択する。
【0124】
図18、図19は、経路算出部のフローチャートである。
[ステップS61]経路算出部41は、始点ノードに接続されている全リンクを計算候補リストに登録する。そして、経路算出部41は、始点ノードからリンクの終端点へ至る経路情報として、始点ノードからリンクの終端点へ至る到達距離と、始点ノードからリンクの終端点へ至る経路が通過するエリアを通過エリアリストとして記憶部42に記憶する。すなわち、経路算出部41は、始点ノードから伸びる各リンクのリンクコストを到達距離として記憶し、始点ノードの属するエリアのエリアIDを通過エリアリストとして記憶部42に記憶する。
【0125】
[ステップS62]経路算出部41は、計算候補リストの中から到達距離の最も小さいリンクを抽出する。
[ステップS63]経路算出部41は、リンクを抽出できなかった場合、ステップS71へ進む。経路算出部41は、リンクを抽出できた場合、ステップS64へ進む。
【0126】
[ステップS64]経路算出部41は、抽出したリンクの終端点のノードが終点ノードであるか否かを判断する。経路算出部41は、終点ノードであると判断した場合、最短経路が算出されたことになる。経路算出部41は、繰り返し計算により選ばれた複数経路の中から最適経路を選択するため、ステップS72へ進む。経路算出部41は、終点ノードでなかった場合には、ステップS65へ進む。
【0127】
[ステップS65]経路算出部41は、抽出リンクを計算候補リストから削除する。
[ステップS66]経路算出部41は、抽出リンクの終端点のノードが有している全てのリンクに対して、順にステップS70までの処理を行う。以下では、抽出リンクの終端点のノードから伸びている処理対象となっているリンクを新規リンクと呼ぶ。
【0128】
[ステップS67]経路算出部41は、新規リンクの新しい到達距離(抽出リンクの到達距離+新規リストのリンクコスト)を記憶部42に記憶する。また、経路算出部41は、新規リンクへの経路として、抽出リンクの経路に抽出リンクの始端点のノードを追加した経路候補リストを記憶部42に記憶する。
【0129】
[ステップS68]経路算出部41は、抽出リンクの始端点のノードと終端点のノードでエリアIDが異なる場合には、抽出リンクの通過エリアリストの最後に新規リンクの始端点のノードのエリアIDを追加し、同一である場合には、抽出リンクの通過エリアリストを新規リンクの通過エリアリストとして記憶部42に記憶する。
【0130】
[ステップS69]経路算出部41は、新規リンクを計算候補リストに追加する。
[ステップS70]経路算出部41は、新規リンクが残っている場合には、ステップS66へ進む。経路算出部41は、新規リンクが残っていない場合には、ステップS62へ進む。
【0131】
[ステップS71]経路算出部41は、経路候補リストに経路が存在しない場合、宛先までの経路が存在しないと判断し処理を終了する。経路算出部41は、経路候補リストに経路が存在する場合、経路候補リストに格納されている全ての経路に対して通過エリアリストを参照し、許容回数以下で同一エリアを通過している経路を抽出する。経路算出部41は、経路を抽出できた場合には、その中から最短リンクコストの経路を選択する。経路算出部41は、経路を抽出できなかった場合には、終点ノードまでの所望の経路は存在しないと判断し処理を終了する。
【0132】
[ステップS72]抽出リンクの終端点が終点ノードであることは、終点までの経路が得られたことを意味する。従って、経路算出部41は、得られた経路が選択すべき最適な経路であるかを判断する。
【0133】
経路算出部41は、抽出リンクの通過エリアリストに基づいて、同一エリアを通過したことのある経路であるか判断する。すなわち、経路算出部41は、不連続に並んだ同じエリアIDが存在するか判断する。
【0134】
[ステップS73]経路算出部41は、抽出リンクの通過エリアリストに不連続に並んだ同じエリアIDが存在する場合、すなわち、抽出リンクの経路が同一エリアを一度通過した経路である場合、ステップS74へ進む。経路算出部41は、抽出リンクの通過エリアリストに不連続に並んだ同じエリアIDが存在しない場合、ステップS75へ進む。
【0135】
[ステップS74]経路算出部41は、抽出リンクの経路を経路候補リストに格納する。経路算出部41は、他の到達距離の小さい経路を探索すべく、ステップS62へ進む。
[ステップS75]経路算出部41は、経路候補リストに経路が存在しない場合、宛先までの経路が存在しないと判断し処理を終了する。経路算出部41は、経路候補リストに経路が存在する場合、経路候補リストに格納されている全ての経路に対して、通過エリアリストを参照し、許容回数以下で同一経路を通過している経路を抽出する。そして、経路算出部41は、抽出した経路の中から最短の到達距離の経路を選択し処理を終了する。経路算出部41は、許容回数以下で経路を抽出できなかった場合には、所望の経路は存在しないとして処理を終了する。
【0136】
このように、経路算出部41は、複数の経路を記憶しながら、かつ、同一エリアに戻る経路を除外しないで経路計算を進めていく。そして、経路算出部41は、同一エリアを許容回数以下で通過する経路を抽出し、より小さいリンクコストの経路を選択して、最適な経路を算出する。
【符号の説明】
【0137】
1〜5 ノード
1a 経路算出部
1b 記憶部
【特許請求の範囲】
【請求項1】
マルチエリアネットワークに設けられるノードにおいて、
始点ノードから終点ノードに至る経路を算出する経路算出部と、
前記経路算出部の算出する経路が通過する前記マルチエリアネットワークのエリアを示す通過エリアリストを記憶する記憶部と、
を備え、
前記経路算出部は、前記始点ノードから前記終点ノードに至る経路を算出する際、前記記憶部の通過エリアリストを参照し同じエリアを複数回通過する経路を経路算出対象から除外する、
ことを特徴とするノード。
【請求項2】
前記経路算出部は、
経路が未確定のノード群の中からリンクコストの最も小さいノードを抽出し、
抽出した前記ノードを経路が確定したノードとして登録し、
抽出した前記ノードの通過エリアリストの最後以外に、抽出した前記ノードの隣接ノードのエリアが含まれているか否かに基づいて前記隣接ノードを経路算出対象から除外し、
前記隣接ノードを経路算出対象から除外しなかった場合、抽出した前記ノードの通過エリアリストの最後と前記隣接ノードのエリアとの比較結果に基づいて、抽出した前記ノードの通過エリアリストに前記隣接ノードのエリアを追加して前記隣接ノードの通過エリアリストとし、または、抽出した前記ノードの通過エリアリストを前記隣接ノードの通過エリアリストとする、
ことを特徴とする請求項1記載のノード。
【請求項3】
前記経路算出部は、
経路計算の候補となる計算候補リストの中からリンクコストの最も小さいリンクを抽出し、
抽出した前記リンクの終端点ノードに隣接する隣接ノードに至る新規リンクを抽出し、
抽出した前記リンクの通過エリアリストの最後以外に、前記新規リンクの終端点ノードのエリアが含まれているか否かに基づいて前記新規リンクを経路算出対象から除外し、
前記新規リンクを経路算出対象から除外しなかった場合、前記新規リンクまでのリンクコストをリンクコスト記憶部に記憶するとともに前記新規リンクを前記計算候補リストに含め、抽出した前記リンクの始端点ノードと終端点ノードの比較結果に基づいて、抽出した前記リンクの通過エリアリストに前記新規リンクの始端点ノードのエリアを追加して前記新規リンクの通過エリアリストとし、または、抽出した前記リンクの通過エリアリストを前記新規リンクの通過エリアリストとする、
ことを特徴とする請求項1記載のノード。
【請求項4】
前記経路算出部は、
経路が未確定のノード群の中からリンクコストの最も小さいノードを抽出し、
抽出した前記ノードを経路が確定したノードとして登録し、
抽出した前記ノードの通過エリアリストに、抽出した前記ノードの隣接ノードのエリアが含まれているか否かに基づいて前記隣接ノードを経路算出対象から除外し、
前記隣接ノードを経路算出対象から除外しなかった場合、抽出した前記ノードのエリアと前記隣接ノードのエリアとの比較結果に基づいて、抽出した前記ノードのエリアを前記隣接ノードの通過エリアリストとし、または、抽出した前記ノードの通過エリアリストを前記隣接ノードの通過エリアリストとする、
ことを特徴とする請求項1記載のノード。
【請求項5】
前記経路算出部は、前記始点ノードから前記終点ノードに至る経路を算出することができなかった場合、ダイクストラ法によって経路を算出することを特徴とする請求項1記載のノード。
【請求項6】
マルチエリアネットワークに設けられるノードにおいて、
始点ノードから終点ノードに至る経路を算出する経路算出部と、
前記経路算出部の算出する経路が通過する前記マルチエリアネットワークのエリアを示す通過エリアリストを記憶する記憶部と、
を備え、
前記経路算出部は、前記始点ノードから前記終点ノードに至る経路を算出した後、前記記憶部の通過エリアリストを参照して同じエリアを許容回数以下で通過する経路を抽出し、抽出した経路の中からリンクコストの最も小さい経路を選択する、
ことを特徴とするノード。
【請求項7】
前記経路算出部は、
経路計算の候補となる計算候補リストの中からリンクコストの最も小さいリンクを抽出し、
抽出した前記リンクの終端点ノードに隣接する隣接ノードに至る新規リンクを抽出し、
前記新規リンクまでのリンクコストをリンクコスト記憶部に記憶するとともに前記新規リンクを前記計算候補リストに含め、抽出した前記リンクの始端点ノードと終端点ノードのエリアの比較結果に基づいて、抽出した前記リンクの通過エリアリストに前記新規リンクの始端点ノードのエリアを追加して前記新規リンクの通過エリアリストとし、または、抽出した前記リンクの通過エリアリストを前記新規リンクの通過エリアリストとする、
ことを特徴とする請求項1記載のノード。
【請求項8】
マルチエリアネットワークに設けられるノードの経路計算方法において、
始点ノードから終点ノードに至る経路を算出する工程と、
前記経路を算出する工程において算出される経路が通過する前記マルチエリアネットワークのエリアを示した通過エリアリストを記憶部に記憶する工程と、
を有し、
前記経路を算出する工程において前記始点ノードから前記終点ノードに至る経路を算出する際、前記記憶部の通過エリアリストを参照し同じエリアを複数回通過する経路を経路算出対象から除外する、
ことを特徴とする経路計算方法。
【請求項9】
マルチエリアネットワークに設けられるノードの経路計算方法において、
始点ノードから終点ノードに至る経路を算出する工程と、
前記経路を算出する工程において算出される経路が通過する前記マルチエリアネットワークのエリアを示した通過エリアリストを記憶部に記憶する工程と、
を有し、
前記経路を算出する工程において前記始点ノードから前記終点ノードに至る経路を算出した後、前記記憶部の通過エリアリストを参照して同じエリアを許容回数以下で通過する経路を抽出し、抽出した経路の中からリンクコストの最も小さい経路を選択する、
ことを特徴とする経路計算方法。
【請求項1】
マルチエリアネットワークに設けられるノードにおいて、
始点ノードから終点ノードに至る経路を算出する経路算出部と、
前記経路算出部の算出する経路が通過する前記マルチエリアネットワークのエリアを示す通過エリアリストを記憶する記憶部と、
を備え、
前記経路算出部は、前記始点ノードから前記終点ノードに至る経路を算出する際、前記記憶部の通過エリアリストを参照し同じエリアを複数回通過する経路を経路算出対象から除外する、
ことを特徴とするノード。
【請求項2】
前記経路算出部は、
経路が未確定のノード群の中からリンクコストの最も小さいノードを抽出し、
抽出した前記ノードを経路が確定したノードとして登録し、
抽出した前記ノードの通過エリアリストの最後以外に、抽出した前記ノードの隣接ノードのエリアが含まれているか否かに基づいて前記隣接ノードを経路算出対象から除外し、
前記隣接ノードを経路算出対象から除外しなかった場合、抽出した前記ノードの通過エリアリストの最後と前記隣接ノードのエリアとの比較結果に基づいて、抽出した前記ノードの通過エリアリストに前記隣接ノードのエリアを追加して前記隣接ノードの通過エリアリストとし、または、抽出した前記ノードの通過エリアリストを前記隣接ノードの通過エリアリストとする、
ことを特徴とする請求項1記載のノード。
【請求項3】
前記経路算出部は、
経路計算の候補となる計算候補リストの中からリンクコストの最も小さいリンクを抽出し、
抽出した前記リンクの終端点ノードに隣接する隣接ノードに至る新規リンクを抽出し、
抽出した前記リンクの通過エリアリストの最後以外に、前記新規リンクの終端点ノードのエリアが含まれているか否かに基づいて前記新規リンクを経路算出対象から除外し、
前記新規リンクを経路算出対象から除外しなかった場合、前記新規リンクまでのリンクコストをリンクコスト記憶部に記憶するとともに前記新規リンクを前記計算候補リストに含め、抽出した前記リンクの始端点ノードと終端点ノードの比較結果に基づいて、抽出した前記リンクの通過エリアリストに前記新規リンクの始端点ノードのエリアを追加して前記新規リンクの通過エリアリストとし、または、抽出した前記リンクの通過エリアリストを前記新規リンクの通過エリアリストとする、
ことを特徴とする請求項1記載のノード。
【請求項4】
前記経路算出部は、
経路が未確定のノード群の中からリンクコストの最も小さいノードを抽出し、
抽出した前記ノードを経路が確定したノードとして登録し、
抽出した前記ノードの通過エリアリストに、抽出した前記ノードの隣接ノードのエリアが含まれているか否かに基づいて前記隣接ノードを経路算出対象から除外し、
前記隣接ノードを経路算出対象から除外しなかった場合、抽出した前記ノードのエリアと前記隣接ノードのエリアとの比較結果に基づいて、抽出した前記ノードのエリアを前記隣接ノードの通過エリアリストとし、または、抽出した前記ノードの通過エリアリストを前記隣接ノードの通過エリアリストとする、
ことを特徴とする請求項1記載のノード。
【請求項5】
前記経路算出部は、前記始点ノードから前記終点ノードに至る経路を算出することができなかった場合、ダイクストラ法によって経路を算出することを特徴とする請求項1記載のノード。
【請求項6】
マルチエリアネットワークに設けられるノードにおいて、
始点ノードから終点ノードに至る経路を算出する経路算出部と、
前記経路算出部の算出する経路が通過する前記マルチエリアネットワークのエリアを示す通過エリアリストを記憶する記憶部と、
を備え、
前記経路算出部は、前記始点ノードから前記終点ノードに至る経路を算出した後、前記記憶部の通過エリアリストを参照して同じエリアを許容回数以下で通過する経路を抽出し、抽出した経路の中からリンクコストの最も小さい経路を選択する、
ことを特徴とするノード。
【請求項7】
前記経路算出部は、
経路計算の候補となる計算候補リストの中からリンクコストの最も小さいリンクを抽出し、
抽出した前記リンクの終端点ノードに隣接する隣接ノードに至る新規リンクを抽出し、
前記新規リンクまでのリンクコストをリンクコスト記憶部に記憶するとともに前記新規リンクを前記計算候補リストに含め、抽出した前記リンクの始端点ノードと終端点ノードのエリアの比較結果に基づいて、抽出した前記リンクの通過エリアリストに前記新規リンクの始端点ノードのエリアを追加して前記新規リンクの通過エリアリストとし、または、抽出した前記リンクの通過エリアリストを前記新規リンクの通過エリアリストとする、
ことを特徴とする請求項1記載のノード。
【請求項8】
マルチエリアネットワークに設けられるノードの経路計算方法において、
始点ノードから終点ノードに至る経路を算出する工程と、
前記経路を算出する工程において算出される経路が通過する前記マルチエリアネットワークのエリアを示した通過エリアリストを記憶部に記憶する工程と、
を有し、
前記経路を算出する工程において前記始点ノードから前記終点ノードに至る経路を算出する際、前記記憶部の通過エリアリストを参照し同じエリアを複数回通過する経路を経路算出対象から除外する、
ことを特徴とする経路計算方法。
【請求項9】
マルチエリアネットワークに設けられるノードの経路計算方法において、
始点ノードから終点ノードに至る経路を算出する工程と、
前記経路を算出する工程において算出される経路が通過する前記マルチエリアネットワークのエリアを示した通過エリアリストを記憶部に記憶する工程と、
を有し、
前記経路を算出する工程において前記始点ノードから前記終点ノードに至る経路を算出した後、前記記憶部の通過エリアリストを参照して同じエリアを許容回数以下で通過する経路を抽出し、抽出した経路の中からリンクコストの最も小さい経路を選択する、
ことを特徴とする経路計算方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【公開番号】特開2011−109426(P2011−109426A)
【公開日】平成23年6月2日(2011.6.2)
【国際特許分類】
【出願番号】特願2009−262487(P2009−262487)
【出願日】平成21年11月18日(2009.11.18)
【出願人】(000005223)富士通株式会社 (25,993)
【Fターム(参考)】
【公開日】平成23年6月2日(2011.6.2)
【国際特許分類】
【出願日】平成21年11月18日(2009.11.18)
【出願人】(000005223)富士通株式会社 (25,993)
【Fターム(参考)】
[ Back to top ]