JP3734817B2 - 経路制御装置およびプログラム - Google Patents

Description

本発明は、パケットネットワークまたはＴＤＭ(Time Division
Multiplexing)ネットワークまたは波長パスネットワークに利用する。特に、経路制御技術に関する。

図７に、経路制御装置とネットワークとの関係を示す。ノード毎に経路制御装置を備えている。まず、ノードを、ＩＰルータとして、ＩＰネットワークにおける従来例を説明する。

ＩＰネットワークにおける経路制御、つまり、ＩＰルーチングは、ルーチングテーブルを作成するための技術であり、インターネットが自立分散的に動作し、大規模に発展するための重要な技術である。インターネットは大規模であり、宛先アドレスを一元的に管理してルーチングテーブルを作成するのは現実的でない。このことから自律分散的にルーチングテーブルを作るための仕組みとして、ルーチングプロトコルが開発されてきた。

ルーチングプロトコルは、ルータ同士が情報を交換しながらルーチングテーブルを作成し、このルーチングテーブルを元に、ＩＰパケットの転送に用いるフォワーディングテーブルを作成する。また、ルーチングテーブルは、ネットワークの状態の変化や運用ポリシーの変化に応じて動的に変更される。

ルーチングプロトコルは、動作原理の観点から幾つかのタイプに分類される。ディスタンスベクター型、パスベクター型、リンクステート型などである。図８に各タイプのルーチングプロトコルの分類と動作原理の概要を示す。

ディスタンスベクター型では、各ルータがディスタンスベクター（宛先アドレス、宛先アドレスまでの距離、および次ホップルータ）を交換し、隣接ルータから宛先アドレス毎のディスタンスベクターを元に自分のディスタンスベクター表を更新し、宛先アドレス毎の次ホップ情報を算出するものである。ディスタンスベクター型では、ルーチングテーブルの問題を解決するため、ネットワークの規模が制限される。

パスベクター型では、ディスタンスベクターの代わりにパスベクターを交換することで、ディスタンスベクター型で問題となるルーチングループの問題を解決し、ネットワーク規模に制限を加えないようにするものである。

リンクステート型はリンクステートをルータ間で交換することで、ネットワークのトポロジを全ルータ間で共有し、そのトポロジ上で各ルータがそれぞれ宛先アドレスまでの最短経路を計算するものである。

本発明は、ディスタンスベクター型の経路制御に関するものであるため、ディスタンスベクター型の経路制御について説明する。ディスタンスベクター型は、ディスタンスベクター表（宛先毎の距離と隣接ルータとを書いた表）を各ルータが隣接ルータとの間で交換することで、ルーチングテーブルを作成していくものである。図９にディスタンスベクター表を示す（ディスタンスベクター表には宛先毎の距離とそのときに用いる隣接ルータへのリンクの組とを記録する）。

ディスタンスベクター型は、Ｂｅｌｌｍａｎ−Ｆｏｒｄアルゴリズムに基づいて設計されている。はじめに各ルータは、隣接ルータとの間のリンクのコストを知っているものとして、プロトコルが動作する。つまり、ディスタンスベクターには、隣接ルータとそれへのリンクのコストのみを書いておく。

各ルータは、隣接ルータとディスタンスベクター表を交換し、ある宛先の組に関して、隣接ルータから得たディスタンスベクターが自分の持っているディスタンスベクターよりも短い距離で到達できるのであれば、それを用いて自分のディスタンスベクターを更新する。各ルータは、ディスタンスベクターを更新したら、再度隣接ルータへそれを伝える。各ルータが自律分散的に上記のディスタンスベクター表の更新を行い続けると、やがてディスタンスベクター表の内容が収束する。収束したディスタンスベクター表に従ったルートが最短経路となる。図１０にディスタンスベクター型の動作の概念図を示す。図１０では、ルータＸは、ルータＢからディスタスベクター表（宛先＝Ａ、次ホップ＝Ｂ、距離＝５０）をもらい、ルータＣ空は（宛先＝Ａ、次ホップ＝Ｃ、距離＝１００）をもらう。これにより、ルータＸは、ルータＡに行くには、隣接ルータＢを経由すると５２（＝５０＋２）のコストで、隣接ルータＣを経由すると、１０１（＝１００＋１）のコストで到達できることがわかる。従って、ルータＸは、隣接ルータＢをルータＡへ行くときの次ホップとして採用する。

Ｂｅｌｌｍａｎ−Ｆｏｒｄアルゴリズムでは、各ノードが以下に示すＢｅｌｌｍａｎの公式に基づいてディスタンスベクター表を更新する。隣接ノードｉとｊとの間のリンクコストをｄ（ｉ，ｊ）とし、時刻ｔでのノードｉから宛先ノードまでの最短距離をＤ（ｔ，ｉ）であるとすると、ノードｉがノードｊからディスタンスベクターを得たときに、次の瞬間の最短距離Ｄ（ｔ＋δ，ｉ）は、
Ｄ（ｔ＋δ，ｉ）＝ｍｉｎ（Ｄ（ｔ，ｉ），ｄ（ｉ，ｊ）＋Ｄ（ｔ，ｊ））…（１）
で与えられる。ディスタンスベクターを構成する宛先ノードへの次ホップ情報はｍｉｎ（ ）で選ばれた方のもので書き換えられる。図１１では、発ノードｉから宛先ノードへの最短経路を求めようとしている。時刻ｔにおける発ノードｉは、宛先ノードへの最短経路がＤ（ｔ，ｉ）のコストで到達できるとする。ここで隣接ノードｊが、宛先ノードへの最短経路について、コストＤ（ｔ，ｊ）で到達できることをノードｉへ伝えたとする。ノードｉとｊとは隣接しており、それらを接続するリンクのコストはｄ（ｉ，ｊ）とする。このとき、ノードｉはＤ（ｔ，ｊ）とｄ（ｉ，ｊ）＋Ｄ（ｔ，ｊ）の小さい方を選ぶ。

Ｂｅｌｌｍａｎ−Ｆｏｒｄアルゴリズムは初期値Ｄ（０，ｉ）および隣接リンクコストｄｉｊが任意の正の値であり、かつ、非同期でディスタンスベクター表を交換する場合でも最短経路に収束することが証明されている。非同期に各ルータが分散的にディスタンスベクター表を交換してディスタンスベクター表を更新してもよいので、この場合のアルゴリズムを特に非同期分散型Ｂｅｌｌｍａｎ−Ｆｏｒｄアルゴリズムと呼ぶ。

リンクが故障してトポロジが変化すると、そのリンクの両端のルータがディスタンスベクター表の変化を検出する。非同期分散型Ｂｅｌｌｍａｎ−Ｆｏｒｄアルゴリズムは、任意の初期値で最短経路に収まるので、トポロジの変化に対応した最短経路を見出すことができる。すなわち、ディスタンスベクター表が変化すると各ルータは上記の非同期分散型Ｂｅｌｌｍａｎ−Ｆｏｒｄアルゴリズムに従ってディスタンスベクター表を更新していき、やがて新しいトポロジに応じたディスタンスベクター表に収束する。ディスタンスベクター型の利点は、各ルータが非同期に自律分散的に動作することができ、ディスタンスベクター表以外には隣接ルータとの接続関係のみ認知すればよいので、各ルータが保持するデータ量が少なくて済むことである。

図１２に、従来のディスタンスベクターの選択方法を示した。従来のディスタンスベクターの選択方法のプロシジャは以下のとおりである。

Ｓｔｅｐ１：ノードＸが宛先ノードＡの新しいディスタンスベクターをノードＹから受信する。
Ｓｔｅｐ２：ノードＸが保持する宛先ノードＡのディスタンスベクターがあり、次ホップ情報がノードＹであるか？ＹＥＳならば、Ｓｔｅｐ５へ行く。ＮＯならば、Ｓｔｅｐ３へ行く。ＹＥＳの場合には、同じ宛先で同じ次ホップ情報のディスタンスベクターがある場合は、距離が更新されているとみなす。
Ｓｔｅｐ３：新しいディスタンスベクターの距離情報は、ノードＸが保持している宛先ノードＡのディスタンスベクターより、距離情報が短いか？ＹＥＳならば、Ｓｔｅｐ４へ行く。ＮＯならば、Ｓｔｅｐ５へ行く。
Ｓｔｅｐ４：宛先ノードＡのディスタンスベクターを更新する。
Ｓｔｅｐ５：宛先ノードＡのディスタンスベクターを更新しない。

図１３に従来の経路制御装置の構成を示した。経路制御装置は、隣接ノードから通知されるディスタンスベクター情報を受信するディスタンスベクター受信部１１と、受信したディスタンスベクター情報とディスタンスベクター表３の内容とを比較するディスタンスベクター比較部１２と、ディスタンスベクター情報が記録されるディスタンスベクター表１３と、受信したディスタンスベクター情報に基づきディスタンスベクター表１３を更新するディスタンスベクター更新部１５と、隣接ノードへディスタンスベクター情報を通知するためのディスタンスベクター送信部１４と、パス切替えを行うスイッチ部１６とから構成される。

これまでは、ノードをパケット毎に処理するＩＰルータと限定して説明したが、ノードを波長毎に処理する波長パススイッチとして考えることもできる。波長パスネットワークには、パスの概念がある。パスを設定するとは、リンク毎にパスに対応した波長が設定されることである。データがパス上を転送されるとは、波長がリンクバイリンクに設定され、波長をリレーしていくことである。

波長パスを設定する際に、上記に述べたディスタンスベクター型の経路制御を適用することを考える。発ノードは、宛先ノードへ向けて、シグナリングのＰＡＴＨメッセージを、次ホップへ送出する。ここでは、ＲＳＶＰ拡張シグナリングをベースに説明する。次ホップへＰＡＴＨメッセージを送出する際には、図９のディスタンスベクター表を用いる。次ホップノードにおいても、ディスタンスベクター表を用いて、さらに次ホップへ送出される。

この動作を繰り返して、ＰＡＴＨメッセージは、宛先ノードへ到着する。発ノードから宛先ノードへ送られたＰＡＴＨメッセージの経路が波長パスの経路になる。シグナリングメッセージが宛先ノードへ到着すると、宛先ノードは、ＲＥＳＶメッセージを、ＰＡＴＨメッセージの経路と同じ経路で、逆方向に送出して行く。中継ノードは、ＲＥＳＶメッセージを受信すると、波長パススイッチの入力ポートと出力ポートの接続を設定していく。どの波長を用いるかは、ＲＥＳＶメッセージにラベルを搭載する。

ラベルは、それぞれのファイバリンク毎に、割り当てられた値であり、ラベルと波長とが対応する。ラベルの値は、リンク毎に定義されている。あるリンクで赤色の波長がラベルの値１００が定義されていても、別のリンクでは、赤色の波長がラベルの値２００である。それぞれのリンク毎にラベルと波長とが対応しているからである。

中継ノードに波長変換機能がない場合は、設定する波長パスにおいて、波長が連続していなければならない。中継ノードは、ＲＥＳＶメッセージを転送するときに、波長パス上の両リンクで、連続した波長になるように、ラベルを選択する必要がある。波長連続性の制約のために、波長パスで使用できるラベルに制約がある。

また、中継ノードに波長変換機能を有していても、波長変換の制約がある場合には、設定する波長パスにおいて、波長変換の制約条件を満足していなければならない。中継ノードは、ＲＥＳＶメッセージを転送するときに、波長パス上の両リンクで、波長変換の制約条件を満足するように、ラベルを選択する必要がある。波長変換の制約のために、波長パスで使用できるラベルに制約がある。
ＮＴＴ Ｒ＆Ｄ Vol.52,No.3,182頁（2003年）「フォトニックネットワークトラヒック制御技術（岡本聡・山中直明）」

従来技術では、ディスタンスベクターには、次ホップ情報と距離情報とを有していた。ノードは、ディスタンスベクターを元に、隣接ノードへディスタンスベクターを伝播して、隣接ノードは、必要に応じて、ディスタンスベクターを更新していた。しかしながら、波長パスネットワークには、使用できる波長に制約がある。ディスタンスベクター表だけでは、次ホップまでのリンクで使用できる波長が、発ノードから着ノードまで、波長の制約条件を満足しているかわからない。そのため、ディスタンスベクター表に基づく経路は、波長制約の条件を満足していない問題が生じる。

本発明は、このような背景に行われたものであって、波長制約の条件を満足しながら、ディスタンスベクター表を作成して、自律分散的に、波長パスの経路を提供することができる経路制御装置を提供することを目的とする。

従来技術では、ディスタンスベクターには、次ホップ情報と距離情報とを有していた。宛先ノードへの次ホップの経路の決定には、波長変換の制約条件を考慮していない。

本発明では、ディスタンスベクターには、次ホップ情報、距離情報、およびラベルセット情報を有している。ラベルセット情報は、使用可能なラベルを搭載している。ディスタンスベクターを隣接ノードへ伝播する際には、波長に対応したラベルが、波長変換の制約条件を満足するように、ラベルセット情報を作成する。

ディスタンスベクターを受信したノードは、使用可能なラベル情報がディスタンスベクターにない場合は、距離情報が短くてもディスタンスベクターを更新しない。また、ディスタンスベクターを受信したノードは、使用可能なラベル情報数が閾値より小さければ、距離情報が短くても、ディスタンスベクターを更新しない。使用可能なラベル情報数が閾値を満足して、距離情報が短い場合に、ディスタンスベクターを更新する。ただし、宛先ノードに対応するディスタンスベクターがない場合は、使用可能なラベル情報数が１つ以上であれば、ディスタンスベクターを更新する。

すなわち、本発明の第一の観点は、複数のノードが相互に接続されて構成されたネットワークの前記ノードにそれぞれ設けられ、宛先に対応する次ホップ情報および当該次ホップまでの距離情報および当該次ホップまでのパスで使用可能なラベル情報が記録されたディスタンスベクター表を備え、自ノードに隣接するノードに対し、自ノードが当該隣接ノードからデータを受け取る際に当該隣接ノードが使用可能な宛先毎のラベルのセットをラベル変換の制約条件に基づき作成したラベルセット情報を含むディスタンスベクター情報を通知する手段と、自ノードが隣接ノードにデータを送信する際に自ノードが使用可能な宛先毎のラベルセット情報を含むディスタンスベクター情報の通知を当該隣接ノードから受け取る手段と、この受け取る手段により受け取ったディスタンスベクター情報に基づき自ノードの前記ディスタンスベクター表を更新する手段とを備えたことを特徴とする経路制御装置である（請求項１）。

また、前記通知する手段は、ラベル変換の制約条件を満足するラベルセット情報が作成不可の場合には、前記ディスタンスベクター情報に含まれる距離情報を無限大として通知する手段を備えることができる（請求項２）。

また、前記更新する手段は、前記受け取る手段により受け取ったディスタンスベクター情報にラベル情報が含まれていない場合には当該ディスタンスベクター情報による自ノードの前記ディスタンスベクター表の更新を禁止する手段を備えることができる（請求項３）。

また、前記更新する手段は、前記受け取る手段により受け取ったディスタンスベクター情報に１つ以上のラベル情報が含まれており、当該ディスタンスベクター情報に含まれる距離情報が自ノードの前記ディスタンスベクター表に記録された同一宛先に対する距離情報よりも短い場合には当該ディスタンスベクター情報により自ノードの前記ディスタンスベクター表を更新する手段を備えることができる（請求項４）。

あるいは、前記更新する手段は、前記受け取る手段により受け取ったディスタンスベクター情報に閾値以上の数のラベル情報が含まれていない場合には当該ディスタンスベクター情報による自ノードの前記ディスタンスベクター表の更新を禁止する手段を備えることができる（請求項５）。

あるいは、前記更新する手段は、前記受け取る手段により受け取ったディスタンスベクター情報に閾値以上の数のラベル情報が含まれており、当該ディスタンスベクター情報に含まれる距離情報が自ノードの前記ディスタンスベクター表に記録された同一宛先に対する距離情報よりも短い場合には当該ディスタンスベクター情報により自ノードの前記ディスタンスベクター表を更新する手段を備えることができる（請求項６）。

本発明の第二の観点は、情報処理装置にインストールすることにより、その情報処理装置に、複数のノードが相互に接続されて構成されたネットワークの前記ノードにそれぞれ設けられ、宛先に対応する次ホップ情報および当該次ホップまでの距離情報および当該次ホップまでのパスで使用可能なラベル情報が記録されたディスタンスベクター表に相応する機能と、自ノードに隣接するノードに対し、自ノードが当該隣接ノードからデータを受け取る際に当該隣接ノードが使用可能な宛先毎のラベルのセットをラベル変換の制約条件に基づき作成したラベルセット情報を含むディスタンスベクター情報を通知する機能と、自ノードが隣接ノードにデータを送信する際に自ノードが使用可能な宛先毎のラベルセット情報を含むディスタンスベクター情報の通知を当該隣接ノードから受け取る機能と、この受け取る機能により受け取ったディスタンスベクター情報に基づき自ノードの前記ディスタンスベクター表を更新する機能とを備えた経路制御装置に相応する機能を実現させることを特徴とするプログラムである（請求項７）。

また、前記通知する機能として、ラベル変換の制約条件を満足するラベルセット情報が作成不可の場合には、前記ディスタンスベクター情報に含まれる距離情報を無限大として通知する機能を実現させることができる（請求項８）。

また、前記更新する機能として、前記受け取る機能により受け取ったディスタンスベクター情報にラベル情報が含まれていない場合には当該ディスタンスベクター情報による自ノードの前記ディスタンスベクター表の更新を禁止する機能を実現させることができる（請求項９）。

また、前記更新する機能として、前記受け取る機能により受け取ったディスタンスベクター情報に１つ以上のラベル情報が含まれており、当該ディスタンスベクター情報に含まれる距離情報が自ノードの前記ディスタンスベクター表に記録された同一宛先に対する距離情報よりも短い場合には当該ディスタンスベクター情報により自ノードの前記ディスタンスベクター表を更新する機能を実現させることができる（請求項１０）。

あるいは、前記更新する機能として、前記受け取る機能により受け取ったディスタンスベクター情報に閾値以上の数のラベル情報が含まれていない場合には当該ディスタンスベクター情報による自ノードの前記ディスタンスベクター表の更新を禁止する機能を実現させることができる（請求項１１）。

あるいは、前記更新する機能として、前記受け取る機能により受け取ったディスタンスベクター情報に閾値以上の数のラベル情報が含まれており、当該ディスタンスベクター情報に含まれる距離情報が自ノードの前記ディスタンスベクター表に記録された同一宛先に対する距離情報よりも短い場合には当該ディスタンスベクター情報により自ノードの前記ディスタンスベクター表を更新する機能を実現させることができる（請求項１２）。

本発明の第三の観点は、本発明のプログラムが記録された前記情報処理装置読取可能な記録媒体である（請求項１３）。本発明のプログラムは本発明の記録媒体に記録されることにより、前記情報処理装置は、この記録媒体を用いて本発明のプログラムをインストールすることができる。あるいは、本発明のプログラムを保持するサーバからネットワークを介して直接前記情報処理装置に本発明のプログラムをインストールすることもできる。

これにより、汎用の情報処理装置を用いて、波長制約の条件を満足しながら、ディスタンスベクター表を作成して、自律分散的に、波長パスの経路を提供することができる経路制御装置を実現することができる。

本発明によれば、波長パスネットワーク、ＴＤＭネットワークには、使用できる波長またはタイムスロットに制約があり、波長またはタイムスロットに対応するラベル変換の制約条件を満足している場合のみ、ディスタンスベクター表に、ディスタンスベクターを更新するので、ディスタンスベクター表に基づく経路は、ラベル変換の制約条件を満足する。また、ラベル変換の制約条件を満足する波長が閾値より小さい場合は、当該経路を除外するので、ラベルリソースを有効的に利用できる。

本発明実施例の経路制御装置の構成を図１を参照して説明する。図１は本実施例の経路制御装置のブロック構成図である。

本実施例は、図７に示すように、複数のノードが相互に接続されて構成されたネットワークの前記ノードにそれぞれ設けられ、図１に示すように、宛先に対応する次ホップ情報および当該次ホップまでの距離情報および当該次ホップまでのパスで使用可能なラベル情報が記録されたディスタンスベクター表３を備え、自ノードに隣接するノードに対し、自ノードが当該隣接ノードからデータを受け取る際に当該隣接ノードが使用可能な宛先毎のラベルのセットをラベル管理部６により管理されている変換の制約条件に基づき作成したラベルセット情報を含むディスタンスベクター情報を通知するディスタンスベクター送信部４と、自ノードが隣接ノードにデータを送信する際に自ノードが使用可能な宛先毎のラベルセット情報を含むディスタンスベクター情報の通知を当該隣接ノードから受け取るディスタンスベクター受信部１と、このディスタンスベクター受信部１により受け取ったディスタンスベクター情報に基づき自ノードのディスタンスベクター表３を更新するディスタンスベクター更新部５とを備えたことを特徴とする経路制御装置である（請求項１）。

ディスタンスベクター送信部４は、ラベル変換の制約条件を満足するラベルセット情報が作成不可の場合には、前記ディスタンスベクター情報に含まれる距離情報を無限大として通知する手段を備える（請求項２）。

また、第一実施例では、ディスタンスベクター更新部５は、ディスタンスベクター受信部１により受け取ったディスタンスベクター情報にラベル情報が含まれていない場合には当該ディスタンスベクター情報による自ノードの前記ディスタンスベクター表の更新を禁止する手段を備える（請求項３）。

さらに、第一実施例では、ディスタンスベクター更新部５は、ディスタンスベクター受信部１により受け取ったディスタンスベクター情報に１つ以上のラベル情報が含まれており、当該ディスタンスベクター情報に含まれる距離情報が自ノードのディスタンスベクター表３に記録された同一宛先に対する距離情報よりも短い場合には当該ディスタンスベクター情報により自ノードのディスタンスベクター表３を更新する手段を備える（請求項４）。

また、第二実施例では、ディスタンスベクター更新部５は、ディスタンスベクター受信部１により受け取ったディスタンスベクター情報に閾値以上の数のラベル情報が含まれていない場合には当該ディスタンスベクター情報による自ノードのディスタンスベクター表３の更新を禁止する手段を備える（請求項５）。

また、第二実施例では、ディスタンスベクター更新部５は、ディスタンスベクター受信部１により受け取ったディスタンスベクター情報に閾値以上の数のラベル情報が含まれており、当該ディスタンスベクター情報に含まれる距離情報が自ノードのディスタンスベクター表３に記録された同一宛先に対する距離情報よりも短い場合には当該ディスタンスベクター情報により自ノードのディスタンスベクター表３を更新する手段を備える（請求項６）。

本発明は、汎用の情報処理装置にインストールすることにより、その情報処理装置に本発明の経路制御装置に相応する機能を実現させるプログラムとして実現することができる（請求項７〜１２）。このプログラムは、記録媒体に記録されて情報処理装置にインストールされ（請求項１３）、あるいは通信回線を介して情報処理装置にインストールされることにより当該情報処理装置に、ディスタンスベクター受信部１、ディスタンスベクター比較部２、ディスタンスベクター表３、ディスタンスベクター送信部４、ディスタンスベクター更新部５、ラベル管理部６にそれぞれ相応する機能を実現させることができる。

以下では、本実施例をさらに詳細に説明する。

（第一実施例）
図２に、第一実施例のディスタンスベクター表３を示す。従来の技術と比べて、ラベルセット情報が新たに追加されている。ラベルセット情報には、使用可能な波長に対応するラベルを搭載する。ラベルは、それぞれのファイバリンク毎に、割り当てられた値であり、ラベルと波長とが対応する。ラベルの値は、リンク毎に定義されている。

あるリンクで赤色の波長のラベルの値として１００が定義されていても、別のリンクでは、赤色の波長のラベルの値は２００である。それぞれのリンク毎にラベルと波長とが対応しているからである。図２の例では、１２９．６０．２２５．０／２４を宛先とする場合には、次ホップがノードＥであり、ノードＥまでに、使用できるラベルは、１００，１１０，１４０であることを意味している。また、１２９．６０．２２５．０／２４までの距離は、３であることを意味する。

図３に、第一実施例のディスタンスベクター型の動作の概念図を示す。ノードＢは、ノードＸに対して、宛先ノードＡのディスタンスベクターのラベルセット情報を作成する。ノードＢは、自ノードが発ノードとする宛先ノードＡのディスタンスベクターのラベルセットとリンクＢＸ間の使用可能なラベル値と波長の制約条件とを考慮すると、これらを満足するノードＸに対する宛先ノードＡのディスタンスベクターのラベルセット情報が見つからない。

そのため、波長制約条件を満足するノードＸからノードＢを経由してノードＡ宛ての経路がないことがわかる。したがって、ノードＢは、ノードＸに対して、宛先ノードＡのディスタンスベクターに、距離を無限大として、ラベル情報を搭載しないで伝播する。ここで、無限大とは、実際には、十分大きい値を定義しておき、この値を無限大とする。

一方、図４に示すように、ノードＣにおいて、宛先ノードＡのディスタンスベクターとして、次ホップ情報がノードＤ、距離情報が１００、ラベルセット情報のラベルが１０１，１２０，１５０として保持している。図４は、本実施例のラベルセット情報の伝播の状況を示す図である。ラベル１１５は、波長制約条件を満足していないために、ラベルセット情報から除外されている。ラベルと波長との関係は、図４のようになっている。ノードＣがノードＸに対してディスタンスベクターを伝播する際に、ノードＸに対するラベルセット情報を作成する。リンクＸＣの使用可能なラベルは２０１，２１５，２５０である。ここで、ノードＣは、波長変換機能がないと仮定している。ノードＣが保持している宛先ノードＡのラベルセット情報は｛１０１，１２０，１５０｝であり、ノードＣには、波長変換機能がないので、ノードＣがノードＸに対して、ディスタンスベクターを伝播するラベルセット情報は｛２０１，２５０｝のみとなる。ラベル２１５は、波長変換機能がないため、ラベルセットから除外される。したがって、ノードＣがノードＸに対して、宛先ノードＡのディスタンスベクターは、図３のようになる。

図３において、ノードＸは、宛先ノードＡのディスタンスベクターを、ノードＢとノードＣから受信している。この場合には、次ホップがノードＣのディスタンスベクターを選ぶことになる。その際に、当該ディスタンスベクターの距離は、距離１００とリンクＸＣの距離１との和を計算して１０１としている。

図５に、第一実施例のディスタンスベクターの選択方法を示した。第一実施例のディスタンスベクターの選択方法のプロシジャは以下のとおりである。

Ｓｔｅｐ１：ノードＸが宛先ノードＡの新しいディスタンスベクターをノードＹから受信する。
Ｓｔｅｐ２：ノードＸが保持する宛先ノードＡのディスタンスベクターがあり、次ホップ情報がノードＹであるか？ＹＥＳならば、Ｓｔｅｐ５へ行く。ＮＯならば、Ｓｔｅｐ３へ行く。ＹＥＳの場合には、同じ宛先で同じ次ホップ情報のディスタンスベクターがある場合は、距離情報が更新されているとみなす。
Ｓｔｅｐ３：ラベルセット情報にラベル情報が１つ以上あるか？ＹＥＳならば、Ｓｔｅｐ４へ行く。ＮＯならば、Ｓｔｅｐ６へ行く。
Ｓｔｅｐ４：新しいディスタンスベクターの距離情報は、ノードＸが保持している宛先ノードＡのディスタンスベクターより、距離情報が短いか？ＹＥＳならば、Ｓｔｅｐ５へ行く。ＮＯならば、Ｓｔｅｐ６へ行く。
Ｓｔｅｐ５：宛先ノードＡのディスタンスベクターを更新する。
Ｓｔｅｐ６：宛先ノードＡのディスタンスベクターを更新しない。

図１に第一実施例の経路制御装置の構成を示した。図１３との相違は、本発明では、ディスタンスベクターにラベルセット情報が含まれており、ディスタンスベクター受信部１、ディスタンスベクター比較部２、ディスタンスベクター表３、ディスタンスベクター更新部５、ディスタンスベクター送信部４は、上記に示したプロシジャにしたがって、ラベルセット情報を処理する機能を有することである。実際の波長とラベルとの対応および波長変換機能の制約条件の処理は、ラベルセット情報を作成する際に、ラベル管理部６で実施される。

このように、波長パスネットワークには、使用できる波長に制約があり、波長の制約条件を満足している場合のみ、ディスタンスベクター表３に、ディスタンスベクターを更新するので、ディスタンスベクター表３に基づく経路は、波長制約の条件を満足する。

（第二実施例）
図６に、第二実施例のディスタンスベクターの選択方法を示した。第二実施例のディスタンスベクターの選択方法のプロシジャは以下のとおりである。

Ｓｔｅｐ１：ノードＸが宛先ノードＡの新しいディスタンスベクターをノードＹから受信する。
Ｓｔｅｐ２：ノードＸが保持する宛先ノードＡのディスタンスベクターがあり、次ホップ情報がノードＹであるか？ＹＥＳならば、Ｓｔｅｐ６へ行く。ＮＯならば、Ｓｔｅｐ３へ行く。ＹＥＳの場合には、同じ宛先で同じ次ホップのディスタンスベクターがある場合は、距離が更新されているとみなす。
Ｓｔｅｐ３：ノードＸが保持している宛先ノードＡのディスタンスベクターが存在しない、かつ、ラベルセット情報にラベル情報が１つ以上あるか？ＹＥＳならば、Ｓｔｅｐ３へ行く。ＮＯならば、Ｓｔｅｐ４へ行く。
Ｓｔｅｐ４：新しいディスタンスベクターのラベルセット情報に含まれるラベル情報数は閾値以上か？ＹＥＳならば、Ｓｔｅｐ５へ行く。ＮＯならば、Ｓｔｅｐ７へ行く。

Ｓｔｅｐ５：新しいディスタンスベクターの距離情報は、ノードＸが保持している宛先ノードＡのディスタンスベクターより、距離情報が短いか？ＹＥＳならば、Ｓｔｅｐ６へ行く。ＮＯならば、Ｓｔｅｐ７へ行く。
Ｓｔｅｐ６：宛先ノードＡのディスタンスベクターを更新する。
Ｓｔｅｐ７：宛先ノードＡのディスタンスベクターを更新しない。

第二実施例では、新しいディスタンスベクターのラベルセット情報に含まれるラベル情報数に閾値を設けておき、閾値より小さいラベル情報数のラベルセットのディスタンスベクターは、距離情報に関係なく、ディスタンスベクターとして採用しない。これは、ラベル情報数が小さいとき、使用可能な波長が少ないことを意味しており、ラベル情報数が大きい別の候補のディスタンスベクターがあれば、距離情報が大きくてもそれを採用する。これにより、波長リソースを有効的に利用できる。

（第三実施例）
第一および第二実施例では、波長パスネットワークについて述べていた。第三実施例では、本発明は、ＴＤＭネットワークに適用することもできる。波長パスネットワークでは、ラベルは波長に対応していた。ＴＤＭネットワークでは、ラベルはタイムスロットに対応する。ノードが、タイムスロット毎に処理するＴＤＭスイッチの場合は、ＴＤＭネットワークである。

ＴＤＭネットワークの例として、ＳＤＨネットワークやＳＯＮＥＴネットワークがある。ＴＤＭネットワークには、パスの概念がある。パスを設定するとは、リンク毎にパスに対応したタイムスロットが設定されることである。データがパス上を転送されるとは、タイムスロットがリンクバイリンクに設定され、タイムスロットをリレーしていくことである。

第一および第二実施例で述べた波長変換の制約条件を、第三実施例では、タイムスロット変換の制約条件というように、波長をタイムスロットに置き換えて扱うことができる。このような制約条件を、より一般的に表現すると、ラベル変換の制約条件と表現することができる。

本発明によれば、波長制約の条件を満足しながら、ディスタンスベクター表を作成して、自律分散的に、波長パスの経路を提供することができるので、ネットワークの運用効率を向上させることができるため、ネットワーク事業者およびネットワークユーザにとって利便性の高いネットワークを構築することができる。

本実施例の経路制御装置のブロック構成図。 本実施例のディスタンスベクター表の例を示す図。 本実施例のディスタンスベクター型の動作の概念図。 本実施例のラベルセットの伝播の状況を示す図。 第一実施例のディスタンスベクターの選択手順を示すフローチャート。 第二実施例のディスタンスベクターの選択手順を示すフローチャート。 ネットワークの概念図。 ＩＰルーチングの分類と動作原理を示す図。 従来のディスタンスベクター表の例を示す図。 従来のディスタンスベクター型の動作の概念図。 Ｂｅｌｌｍａｎの公式を説明するための図。 従来のディスタンスベクターの選択手順を示すフローチャート。 従来の経路制御装置のブロック構成図。

符号の説明

１、１１ ディスタンスベクター受信部
２、１２ ディスタンスベクター比較部
２、１３ ディスタンスベクター表
４、１４ ディスタンスベクター送信部
５、１５ ディスタンスベクター更新部
６ ラベル管理部
７、１６ スイッチ部

Claims (13)

1. 複数のノードが相互に接続されて構成されたネットワークの前記ノードにそれぞれ設けられ、
   宛先に対応する次ホップ情報および当該次ホップまでの距離情報および当該次ホップまでのパスで使用可能なラベル情報が記録されたディスタンスベクター表を備え、
   自ノードに隣接するノードに対し、自ノードが当該隣接ノードからデータを受け取る際に当該隣接ノードが使用可能な宛先毎のラベルのセットをラベル変換の制約条件に基づき作成したラベルセット情報を含むディスタンスベクター情報を通知する手段と、
   自ノードが隣接ノードにデータを送信する際に自ノードが使用可能な宛先毎のラベルセット情報を含むディスタンスベクター情報の通知を当該隣接ノードから受け取る手段と、
   この受け取る手段により受け取ったディスタンスベクター情報に基づき自ノードの前記ディスタンスベクター表を更新する手段と
   を備えたことを特徴とする経路制御装置。
2. 前記通知する手段は、ラベル変換の制約条件を満足するラベルセット情報が作成不可の場合には、前記ディスタンスベクター情報に含まれる距離情報を無限大として通知する手段を備えた請求項１記載の経路制御装置。
3. 前記更新する手段は、前記受け取る手段により受け取ったディスタンスベクター情報にラベル情報が含まれていない場合には当該ディスタンスベクター情報による自ノードの前記ディスタンスベクター表の更新を禁止する手段を備えた請求項１記載の経路制御装置。
4. 前記更新する手段は、前記受け取る手段により受け取ったディスタンスベクター情報に１つ以上のラベル情報が含まれており、当該ディスタンスベクター情報に含まれる距離情報が自ノードの前記ディスタンスベクター表に記録された同一宛先に対する距離情報よりも短い場合には当該ディスタンスベクター情報により自ノードの前記ディスタンスベクター表を更新する手段を備えた請求項１記載の経路制御装置。
5. 前記更新する手段は、前記受け取る手段により受け取ったディスタンスベクター情報に閾値以上の数のラベル情報が含まれていない場合には当該ディスタンスベクター情報による自ノードの前記ディスタンスベクター表の更新を禁止する手段を備えた請求項１記載の経路制御装置。
6. 前記更新する手段は、前記受け取る手段により受け取ったディスタンスベクター情報に閾値以上の数のラベル情報が含まれており、当該ディスタンスベクター情報に含まれる距離情報が自ノードの前記ディスタンスベクター表に記録された同一宛先に対する距離情報よりも短い場合には当該ディスタンスベクター情報により自ノードの前記ディスタンスベクター表を更新する手段を備えた請求項１記載の経路制御装置。
7. 情報処理装置にインストールすることにより、その情報処理装置に、
   複数のノードが相互に接続されて構成されたネットワークの前記ノードにそれぞれ設けられ、
   宛先に対応する次ホップ情報および当該次ホップまでの距離情報および当該次ホップまでのパスで使用可能なラベル情報が記録されたディスタンスベクター表に相応する機能と、
   自ノードに隣接するノードに対し、自ノードが当該隣接ノードからデータを受け取る際に当該隣接ノードが使用可能な宛先毎のラベルのセットをラベル変換の制約条件に基づき作成したラベルセット情報を含むディスタンスベクター情報を通知する機能と、
   自ノードが隣接ノードにデータを送信する際に自ノードが使用可能な宛先毎のラベルセット情報を含むディスタンスベクター情報の通知を当該隣接ノードから受け取る機能と、
   この受け取る機能により受け取ったディスタンスベクター情報に基づき自ノードの前記ディスタンスベクター表を更新する機能と
   を備えた経路制御装置に相応する機能を実現させることを特徴とするプログラム。
8. 前記通知する機能として、ラベル変換の制約条件を満足するラベルセット情報が作成不可の場合には、前記ディスタンスベクター情報に含まれる距離情報を無限大として通知する機能を実現させる請求項７記載のプログラム。
9. 前記更新する機能として、前記受け取る機能により受け取ったディスタンスベクター情報にラベル情報が含まれていない場合には当該ディスタンスベクター情報による自ノードの前記ディスタンスベクター表の更新を禁止する機能を実現させる請求項７記載のプログラム。
10. 前記更新する機能として、前記受け取る機能により受け取ったディスタンスベクター情報に１つ以上のラベル情報が含まれており、当該ディスタンスベクター情報に含まれる距離情報が自ノードの前記ディスタンスベクター表に記録された同一宛先に対する距離情報よりも短い場合には当該ディスタンスベクター情報により自ノードの前記ディスタンスベクター表を更新する機能を実現させる請求項７記載のプログラム。
11. 前記更新する機能として、前記受け取る機能により受け取ったディスタンスベクター情報に閾値以上の数のラベル情報が含まれていない場合には当該ディスタンスベクター情報による自ノードの前記ディスタンスベクター表の更新を禁止する機能を実現させる請求項７記載のプログラム。
12. 前記更新する機能として、前記受け取る機能により受け取ったディスタンスベクター情報に閾値以上の数のラベル情報が含まれており、当該ディスタンスベクター情報に含まれる距離情報が自ノードの前記ディスタンスベクター表に記録された同一宛先に対する距離情報よりも短い場合には当該ディスタンスベクター情報により自ノードの前記ディスタンスベクター表を更新する機能を実現させる請求項７記載のプログラム。
13. 請求項７ないし１２のいずれかに記載のプログラムが記録された前記情報処理装置読み取り可能な記録媒体。

Images