(57)【要約】【課題】局所的なリソース超過の発生を抑圧できるようにし、ネットワークの利用の効率化を図ったルーティング方法および伝送システムを提供すること。【解決手段】ポリシーベースの検索により唯一のパスルートだけでなく、複数の候補ルートをまず抽出する。そしてこれらのルートに対して、「通過するリンクごとのリソース占有数の最大値の少ない候補ルートほど、その順位を高くする（ルール１）」、「通過するリンクごとのリソース占有数の合計値の少ない候補ルートほど、その順位を高くする（ルール２）」、「通過するリンクごとのリソース占有数のばらつきの少ない候補ルートほど、その順位を高くする（ルール３）」、および、「通過するノードの持つリンク数の合計値の多い候補ルートほど、順位を高くする（ルール４）」というルールを適用し、最も順位の高い候補ルートにパスを設定するようにした。【選択図】      図２
2006025014.tif 000002
【特許請求の範囲】
【請求項１】
リンクを介して接続される複数のノードを備える伝送システムに、前記リンクの少なくとも一部のリソースを占有する通信パスを設定するためのルートを選定するルーティング方法において、
設定すべき通信パスの終端ノードを両端とする複数の候補ルートを抽出する抽出ステップと、
前記伝送システムにおける現時点でのパス設定状態に前記候補ルートを経由する通信パスを追加した状態における前記リソースの占有状態に基づいて、前記複数の候補ルートごとに優位順序を算出する算出ステップと、
前記優位順序の高い候補ルートをパス設定用ルートとして選定する選定ステップとを具備し、
前記算出ステップは、
前記候補ルートのそれぞれに、当該候補ルートに通信パスを設定した状態で各リンクごとのリソース占有数の最大値が少ないほど高い順位を与えるという第１ルールと、
前記候補ルートのそれぞれに、当該候補ルートに通信パスを設定した状態で各リンクごとのリソース占有数の合計値が少ないほど高い順位を与えるという第２ルールと、
前記候補ルートのそれぞれに、当該候補ルートに通信パスを設定した状態で各リンクごとのリソース占有数のばらつきが小さいほど高い順位を与えるという第３ルールと、
前記候補ルートのそれぞれに、当該候補ルートの通過点となるノードがそれぞれ有するリンク数の合計値が多いほど高い順位を与えるという第４ルールとに基づいて、前記複数の候補ルートごとに優位順序を算出するステップであることを特徴とするルーティング方法。
【請求項２】
前記抽出ステップは、
ルーティングメトリックを最適化するというポリシーに基づいて前記複数の候補ルートを検索する検索ステップを含むことを特徴とする請求項１に記載のルーティング方法。
【請求項３】
前記抽出ステップは、前記検索ステップにおいて検索されたルートのうち前記ポリシーに適合する既定の順位までのルートを前記複数の候補ルートに含むことを特徴とする請求項２に記載のルーティング方法。
【請求項４】
前記算出ステップは、前記第１ルールに代えて、
前記候補ルートのそれぞれに、通信パスを設定した状態で各リンクごとのリソース占有率の最大値が少ないほど高い順位を与えるという第５ルールを適用することを特徴とする請求項１に記載のルーティング方法。
【請求項５】
前記算出ステップにおいて同値１位の優位順序を持つ複数の候補ルートが算出された場合に、
さらに、この複数の候補ルートからルーティングメトリックを最適化するというポリシーに基づいて一つの候補ルートを検索する検索ステップを具備し、
前記選定ステップは、前記検索ステップにおいて検索された一つの候補ルートをパス設定用ルートとして選定することを特徴とする請求項１に記載のルーティング方法。
【請求項６】
前記算出ステップにおいて同値１位の優位順序を持つ複数の候補ルートが算出された場合に、
さらに、この複数の候補ルートのそれぞれの伝送品質を評価する評価ステップを具備し、
前記選定ステップは、前記評価ステップにおいて評価された伝送品質の高い候補ルートをパス設定用ルートとして選定することを特徴とする請求項１に記載のルーティング方法。
【請求項７】
さらに、前記伝送システムのトポロジの変化を検出する検出ステップと、
この検出ステップにおいて前記トポロジの変化が検出された場合に、変化後のトポロジのもとで前記抽出ステップと、前記算出ステップと、前記選定ステップとを実施する再起動ステップとを具備することを特徴とする請求項１に記載のルーティング方法。
【請求項８】
リンクを介して接続される複数のノードを備える伝送システムにおいて、
前記リンクの少なくとも一部のリソースを占有する通信パスを設定するパス設定手段と、
設定すべき通信パスの終端ノードを両端とする複数の候補ルートを抽出する抽出手段と、
現時点でのパス設定状態に前記候補ルートを経由する通信パスを追加した状態における前記リソースの占有状態に基づいて、前記複数の候補ルートごとに優位順序を算出する算出手段と、
前記優位順序の高い候補ルートをパス設定用ルートとして選定する選定手段とを具備し、
前記算出手段は、
前記候補ルートのそれぞれに、当該候補ルートに通信パスを設定した状態で各リンクごとのリソース占有数の最大値が少ないほど高い順位を与えるという第１ルールと、
前記候補ルートのそれぞれに、当該候補ルートに通信パスを設定した状態で各リンクごとのリソース占有数の合計値が少ないほど高い順位を与えるという第２ルールと、
前記候補ルートのそれぞれに、当該候補ルートに通信パスを設定した状態で各リンクごとのリソース占有数のばらつきが小さいほど高い順位を与えるという第３ルールと、
前記候補ルートのそれぞれに、当該候補ルートの通過点となるノードがそれぞれ有するリンク数の合計値が多いほど高い順位を与えるという第４ルールとに基づいて、前記複数の候補ルートごとに優位順序を算出することを特徴とする伝送システム。
【請求項９】
前記抽出手段は、ルーティングメトリックを最適化するというポリシーに基づいて前記複数の候補ルートを検索することを特徴とする請求項８に記載の伝送システム。
【請求項１０】
前記抽出手段は、前記検索されたルートのうち前記ポリシーに適合する既定の順位までのルートを前記複数の候補ルートに含むことを特徴とする請求項９に記載の伝送システム。
【請求項１１】
前記算出手段は、前記第１ルールに代えて、
前記候補ルートのそれぞれに、通信パスを設定した状態で各リンクごとのリソース占有率の最大値が少ないほど高い順位を与えるという第５ルールを適用することを特徴とする請求項８に記載の伝送システム。
【請求項１２】
さらに、前記算出手段により同値１位の優位順序を持つ複数の候補ルートが算出された場合に、この複数の候補ルートからルーティングメトリックを最適化するというポリシーに基づいて一つの候補ルートを検索する検索手段を具備し、
前記選定手段は、前記検索手段により検索された一つの候補ルートをパス設定用ルートとして選定することを特徴とする請求項８に記載の伝送システム。
【請求項１３】
さらに、前記算出手段により同値１位の優位順序を持つ複数の候補ルートが算出された場合に、この複数の候補ルートのそれぞれの伝送品質を評価する評価手段を具備し、
前記選定手段は、前記評価手段において評価された伝送品質の高い候補ルートをパス設定用ルートとして選定することを特徴とする請求項８に記載の伝送システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は基幹網などに適用される情報伝送システムと、この種のシステムにおいて有限のリソース上に複数の通信パスを設定するために用いられるルーティング方法に関する。
【背景技術】
【０００２】
近年の情報伝送システムでは複数のノードをリンクを介してメッシュ状に接続し、メッシュネットワークを形成することが多い。メッシュネットワークの伝送リソースを複数の通信パスに割り付けるには、ルーティングアルゴリズムによる最適ルート検索の手法が従来から適用されている。
【０００３】
ルーティングアルゴリズムは、例えば帯域幅（通信処理能力）、ノードホップ数（距離）、信頼性（稼働時間率）、伝送遅延などにより指定されるルーティングメトリックを最適化するというポリシーのもとで、最適ルートを検索する。この種のアルゴリズムには、比較的大規模なネットワークに用いられるＯＳＰＦ（Open Shortest Path First）のようなルーティングプロトコルが知られている。下記特許文献１および２に、この種のプロトコルを用いてネットワーク内に通信経路を設定する技術が開示されている。
【特許文献１】特開２００３−２５８８５５号公報
【特許文献２】特開２０００−２５３０４９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ところで、上記のような最適ルート検索アルゴリズムでは、特定のルートにパス割り付けが集中することが頻繁に生じる。そうなれば局所的なリソース超過がネットワーク内に発生し、伝送リソースの満遍ない使用が妨げられることになる。このことは、ネットワーク全体から見れば局所的なボトルネックのために効率的な運用を妨げられることを意味し、よって何らかの対処が望まれる。  
本発明は上記事情によりなされたもので、その目的は、局所的なリソース超過の発生を抑圧できるようにし、これによりネットワークの利用の効率化を図ったルーティング方法および伝送システムを提供することにある。
【課題を解決するための手段】
【０００５】
上記目的を達成するために本発明の一態様によれば、リンクを介して接続される複数のノードを備える伝送システムに、前記リンクの少なくとも一部のリソースを占有する通信パスを設定するためのルートを選定するルーティング方法において、設定すべき通信パスの終端ノードを両端とする複数の候補ルートを抽出する抽出ステップと、前記伝送システムにおける現時点でのパス設定状態に前記候補ルートを経由する通信パスを追加した状態における前記リソースの占有状態に基づいて、前記複数の候補ルートごとに優位順序を算出する算出ステップと、前記優位順序の高い候補ルートをパス設定用ルートとして選定する選定ステップとを具備し、前記算出ステップは、前記候補ルートのそれぞれに、当該候補ルートに通信パスを設定した状態で各リンクごとのリソース占有数の最大値が少ないほど高い順位を与えるという第１ルールと、前記候補ルートのそれぞれに、当該候補ルートに通信パスを設定した状態で各リンクごとのリソース占有数の合計値が少ないほど高い順位を与えるという第２ルールと、前記候補ルートのそれぞれに、当該候補ルートに通信パスを設定した状態で各リンクごとのリソース占有数のばらつきが小さいほど高い順位を与えるという第３ルールと、前記候補ルートのそれぞれに、当該候補ルートの通過点となるノードがそれぞれ有するリンク数の合計値が多いほど高い順位を与えるという第４ルールとに基づいて、前記複数の候補ルートごとに優位順序を算出するステップであることを特徴とするルーティング方法が提供される。
【０００６】
このような手段を講じることにより、既存の手法のようにポリシーベースで最適ルートだけが検索されるのではなく、候補ルートとして複数のルートが抽出される。これらの各候補パスと既存パスとの組み合わせの中から、上記４つのルール（選定基準（クライテリア））のもとで最適なパスルートが選定される。ルール１および２によれば、各リンクにおける伝送リソース占有数の合計値がより少なくなり、リソース占有最大数が低減される。ルール３によれば、各リンクの間での伝送リソース占有数のばらつきがより少なくなり、各リンクにおける伝送リソースの占有数が平均化される。よってリソースの占有効率が向上し、占有最大数が低減される。ルール４によっても、各リンクにおける伝送リソースの占有数が平均化され、従ってリソース占有の効率が向上して占有最大数が低減される。
【０００７】
従って、特定のルートへのパスの集中を避けることができ、ロードバランシング（Load Balancing）を実現してリソースを高効率に、すなわち満遍なく使用することができるようになる。
【発明の効果】
【０００８】
本発明によれば、局所的なリソース超過の発生を抑圧できるようになり、これによりネットワークの利用の効率化を図ったルーティング方法および伝送システムを提供することができる。
【発明を実施するための最良の形態】
【０００９】
図１は、本発明に係わる情報伝送システムの実施の形態を示すシステム図である。このシステムは、光ファイバ１００を介してメッシュ状に接続される複数のノードＡ〜Ｅを備える。光ファイバ１００は例えばシングルモード光ファイバであり、複数の波長光を多重した波長多重光を伝送する。各ノードは光クロスコネクトを備え、各波長光を波長変換すること無くルーティングする。
【００１０】
この種のシステムはいわゆる全光ネットワークと称され、ＩＰ（Internet Protocol）パケットを伝送するパケット通信網などにオーバレイされることが多い。すなわち全光ネットワークは、パケット通信網に収容しきれないトラフィックを収容するために運用されることが多い。パケット通信網のトラフィックが逼迫してくると、クライアントアプリケーションなどにより「パス設定要求」が生成される。全光ネットワークはこのパス設定要求に応じて光パスを生成し、この光パスにＩＰトラフィックを迂回させるための処理を実施する。  
なお図１の全光ネットワークにおいて、システム全体を統括する監視制御装置ＭＥを設ける場合もある。監視制御装置ＭＥは一つのノード（図１ではノードＡ）に接続しても良いし、全てのノードＡ〜Ｅに一つずつ個別に接続しても良い。
【００１１】
図２は、図１のノードＡの実施の形態を示す機能ブロック図である。ノードＢ〜Ｅも同様の構成である。図２においてノードＡは、現用系高速インタフェース部（ＨＳ Ｉ／Ｆ（SRV））１と、予備系高速インタフェース部（ＨＳ Ｉ／Ｆ（PRT））２と、低速インタフェース部（ＬＳ Ｉ／Ｆ）３と、光クロスコネクト４と、記憶部５と、制御部６と、パターン発生器７と、エラー検出器８と、２×２光スイッチ９と、セレクタ１０とを備える。
【００１２】
現用系高速インタフェース部１は、サービスファイバＳＦを介して導入された波長多重光を個々の波長光に分離して光クロスコネクト４に入力し、また、光クロスコネクト４から与えられる各波長光を波長多重してサービスファイバＳＦに送出する。予備系高速インタフェース部２は、プロテクションファイバＰＦを介して導入された波長多重光を個々の波長光に分離して光クロスコネクト４に入力し、また、光クロスコネクト４から与えられる各波長光を波長多重してプロテクションファイバＰＦに送出する。低速インタフェース部（ＬＳ Ｉ／Ｆ）３は、低速回線２００を介してクライアントインタフェースを収容する。
【００１３】
光クロスコネクト４は、現用系高速インタフェース部１、予備系高速インタフェース部２、および低速インタフェース部３から与えられる波長光の経路を任意に設定し、ネットワーク内に波長パスを形成する。記憶部５は、制御部６の動作に必要となる種々のプログラムやデータなどを記憶する。制御部６は、記憶部５に記憶されたデータをもとに種々の制御機能を実行する。
【００１４】
ところで制御部６は、抽出処理部６ａと、算出処理部６ｂと、選定処理部６ｃと、パス設定処理部６ｄと、検索処理部６ｅと、評価処理部６ｆとを備える。抽出処理部６ａは、設定すべき通信パスの終端ノードを両端とする複数の候補ルートを抽出する。特に抽出処理部６ａは、ルーティングメトリックを最適化するというポリシーに基づいて複数の候補ルートを検索する。算出処理部６ｂは、現時点でのパス設定状態に候補ルートを経由する通信パスを追加した状態におけるリソースの占有状態に基づいて、各候補ルートごとに優位順序を算出する。優位順序の算出にあたっては一定のルールが適用される。
【００１５】
選定処理部６ｃは、優位順序の高い候補ルートをパス設定用ルートとして選定する。パス設定処理部６ｄは、このパス設定用ルートに通信パスを設定する。通信パスを設定することによりリンクの少なくとも一部のリソースが占有されることになる。検索処理部６ｅは、算出処理部６ｂにより同値１位の優位順序を持つ複数の候補ルートが算出された場合に、この複数の候補ルートからルーティングメトリックを最適化するというポリシーに基づいて一つの候補ルートを検索する。
【００１６】
評価処理部６ｆは、算出処理部６ｂにより同値１位の優位順序を持つ複数の候補ルートが算出された場合に、この複数の候補ルートのそれぞれの伝送品質を、例えばビットエラー率などを尺度として評価する。この場合、選定処理部６ｃは、評価処理部６ｆにおいて評価された伝送品質の高い候補ルートをパス設定用ルートとして選定する。なお、これらの各処理部はソフトウェアによる機能オブジェクトとして実現される。
【００１７】
図３は、図１のシステムに備わる伝送リソースの一例を示す模式図である。図３に示すように、隣接するノード間を接続するリンクＡＢ〜ＤＥは、それぞれ４つの伝送リソースλ１〜λ４を持つ。本実施形態では、各リソースを異なる波長とする。これに代えて、時分割多重された複数のタイムスロットのそれぞれを伝送リソースとすることもできる。
【００１８】
図３のトポロジにおいては、ノードＡ−Ｂ間、Ｂ−Ｃ間、Ｃ−Ｄ間、Ｄ−Ａ間、Ｂ−Ｅ間、Ｃ−Ｅ間、Ｄ−Ｅ間、Ａ−Ｃ間、Ｂ−Ｄ間、および、Ｅ−Ａ間を結ぶ、計１０通りのルート上にパスを設定することが可能である。これは、５つのノードから２つの両端ノードを選択する組み合わせの数に相当する。  
図４は、図３のシステムにおけるパス設定状態の一例を示す図である。図４においては全てのリンクに一つずつパスを設定した状態が示される。各パスはそれぞれ波長リソースλ１を占有している。
【００１９】
図５は、本発明に係わるルーティング方法の実施の形態を示すフローチャートである。以下、図４に示す状態を初期状態として種々のパスを設定する手順につき、図５を参照して説明する。なお、図４のパス設定状態も図５のフローチャートに沿って実現されることは勿論である。
【００２０】
図５において、各ノードＡ〜Ｅは既存のリンク状態型ルーティングプロトコル（ＯＳＰＦなど）を利用して、互いにリンク状態情報を交換し合う（ステップＳ１）。その結果を参照して、各ノードＡ〜Ｅはネットワークトポロジ、および、既存パスの状況などを含むネットワーク状態を認識する（ステップＳ２）。各ノードＡ〜Ｅはパス設定要求の到来を待ち受け、パス設定要求が来なければステップＳ１，Ｓ２を繰り返す（ステップＳ３）。これらの情報は図２の記憶部５に記憶され（ネットワークトポロジ５ａ、パス設定状態５ｂ）、時間の経過とともに更新される。
【００２１】
パス設定要求が到来すると（ステップＳ３でＹｅｓ）、この要求を受け取ったノードはパス設定要求情報を含む「パス設定開始通知メッセージ」をシステム全域にブロードキャストする（ステップＳ４）。これによりネットワーク全体が”パス設定中状態”に遷移し、パス設定処理が開始される。
【００２２】
次にシステムは、設定を要求されたパスに対して複数の候補ルートを抽出する（ステップＳ５）。ステップＳ５では、まず設定すべきパスの両端のノードが認識され（ステップＳ５ａ）、この両端のノードをその両端とする複数のルートが選択される。例えば、ノードＡとノードＣとの間にパスを設定する場合、ノードＡからノードＣに到達するには、他の経由ノード（Ｂ，Ｄ，Ｅ）を通るＡ−Ｂ−Ｃ，Ａ−Ｄ−Ｃ，Ａ−Ｂ−Ｅ−Ｃ，Ａ−Ｄ−Ｅ−Ｃの４つのルートがある。なお、ルート検索のアルゴリズムには、既存のルーティングアルゴリズムを利用することができる。
【００２３】
次に、ルーティングメトリックを最適化するというポリシーに従って、これらのルートをさらに幾つかのルートに絞り込む（ステップＳ５ｂ）。この実施形態では「ノードホップ数を最小化する」というポリシーを採択し、このポリシーに適合する上位Ｘ位までのルートを検索するようにする（ステップＳ５ｃ）。
【００２４】
「ホップ数の最小化」に基づいてＸ＝１位までのルートを検索すると、ノードＡと各経由ノードとの間には、ルートＡ−Ｂ，Ａ−Ｄ，Ａ−Ｂ−Ｅ，Ａ−Ｄ−Ｅが選択される。また各経由ノードとノードＣとの間には、ルートＢ−Ｃ，Ｄ−Ｃ，Ｅ−Ｃが選択される。ノードＡ，Ｃ間を結ぶ経路においては、このうちルートＡ−Ｂ−Ｃ，Ａ−Ｄ−Ｃの２つを候補ルートとして見立てることができる。このようにして、ステップＳ５において複数の候補ルートが抽出される。
【００２５】
次に、抽出された候補ルートごとに、一定のルールに従って優位順序が算出される（ステップＳ６）。この実施形態では、各候補ルートに対して次の４つのルールを順次適用し、その結果に基づいてそれぞれの候補ルートを順位付けする。  
（ルール１）  通過するリンクごとのリソース占有数の最大値の少ない候補ルートほど、その順位を高くする。  
（ルール２）  通過するリンクごとのリソース占有数の合計値の少ない候補ルートほど、その順位を高くする。  
（ルール３）  通過するリンクごとのリソース占有数のばらつきの少ない候補ルートほど、その順位を高くする。  
（ルール４）  通過するノードの持つリンク数の合計値の多い候補ルートほど、順位を高くする。
【００２６】
なおルール３の判定基準に用いるばらつきは、例えば標準偏差により計算できる。図４のパスが存在する状態からルートＡ−Ｂ−ＣまたはルートＡ−Ｄ−Ｃにパスを追加した場合の、各リソースの占有状態を表１に示す。  
【表１】
2006025014.tif 000003
【００２７】
表１において、候補ルートＡ−Ｂ−Ｃは、リンクＡＢとＢＣとを通過する。よってこれらのリンクにおけるリソース占有数は、既存パスのリソースと合わせてそれぞれ２となる。他のリンクの占有数は１のままである。ルール１に対応する最大値は、リンクＡＢおよびＢＣにおける占有数の２である。ルール２の合計値は、表の上から順に２，２，１，１，１，１，１の各数値の合計であり、９となる。ルール３のばらつきは各数値の標準偏差を演算し、０．４５となる。さらに、候補ルートＡ−Ｂ−Ｃは、ノードＡ，ノードＢ，ノードＣを通過する。これらの通過ノードは図３のトポロジを参照すると分かるように、それぞれ２個、３個、３個のリンクを持つ。よってこれらの合計は７となる。候補ルートＡ−Ｄ−Ｃに対しても同様の数値を求める。これらの数値を、表１に太線の囲みで示す。
【００２８】
次に図５において、表１の結果から、優先順位の最も高い候補ルートが選定される（ステップＳ７）。表１を参照すると、結果として候補ルートＡ−Ｂ−Ｃと候補ルートＡ−Ｄ−Ｃとに優位順序の差が無いことが分かる。これは図１のネットワークがノードＡ、Ｅ、Ｃを軸として線対称のトポロジを持つことによる。よってステップＳ７で複数の候補ルートが選定され、この段階ではパスを設定すべきルートが確定しない（ステップＳ８でＹｅｓ）。
【００２９】
そこで、新たな判断指標を導入する。この実施形態では各ルートのＢＥＲ（Bit Error Rate）を比較し、伝送品質（ＱｏＳ）の制御に対応可能とする。ここでは、例えば１リンクあたりのエラー損失量をＰ／Ｅ（ＰはリンクのＢＥＲ、Ｅは規格化値：例えば１０-6）と定義したポリシーを導入する。このようなポリシーに基づき各候補ルートのＢＥＲを比較し（ステップＳ１１）、その結果に基づいてＢＥＲが最小となるルートが選定される（ステップＳ１２）。ここではルートＡ−Ｂ−Ｃが選定されたとする。そして、例えばＭＰＬＳ（Multi Protocol Label Switching）などの既知のプロトコルを利用して、選定されたルートにパスが設定される（ステップＳ９）。こののち新規のパスを含むパス設定状態メッセージがシステム全域にブロードキャストされる（ステップＳ１０）。これによりネットワークはパス設定中状態から通常状態に戻り、パス設定処理が終了する。
【００３０】
図６は、図４の状態からルートＡ−Ｂ−Ｃを経由するパスが新規に設定された状態を示す図である。この新規パスはリソースλ２を占有している。図６において、リソースλ２を点線で示す。  
次に、図６の状態から、ノードＢ−Ｄを結ぶパス設定要求が生じたとする。ノードＢ−Ｄ間には、ノードＢから経由ノード（Ａ，Ｅ，Ｃ）を通過してノードＤに至る、ルートＢ−Ａ−Ｄ，Ｂ−Ｅ−Ｄ，Ｂ−Ｃ−Ｄがある。これらの３つのルートのいずれも候補パスとして見立てることができる。図７に、図６からルートＢ−Ａ−Ｄを経由するパスを設定した状態を示す。図８に、図６からルートＢ−Ｅ−Ｄを経由するパスを設定した状態を示す。図１０に、図６からルートＢ−Ｃ−Ｄを経由するパスを設定した状態を示す。図７、図８、図１０につき、各リソースの占有状態を表２に示す。  
【表２】
2006025014.tif 000004
【００３１】
表２の比較結果から、ルートＢ−Ｅ−Ｄ（図８）が最も優位であることが分かる。よってルートＢ−Ｅ−Ｄが選択され、このルートにパスが設定される。
【００３２】
なお本実施形態では、同じパスが複数のリンクを通過する場合、同じパス内でλのサブスクリプト（リソース番号）をできるだけ変えないことを意識した処理を行うようにする。これは、光伝送においては伝送途中で波長変換を行わないことに相当し、電気伝送においては伝送途中でタイムスロットインターチェンジを行わないことに相当する。よってルートＢ−Ｅ−Ｄにリソースλ３を割り当てる（図８の状態）よりは、図９に示すように、ルートＢ−Ｅ−Ｄにリソースλ２を割り当てるのが好ましい。つまり、空きリソースのサブスクリプトを順次詰めていくように、リソース割り当てを最適化すると良い。
【００３３】
さらに、図９の状態から、ノードＥ−Ａを結ぶパス設定要求が生じたとする。ノードＥ−Ａ間には、ノードＥから経由ノード（Ｂ，Ｃ，Ｄ）を通過してノードＡに至る、ルートＥ−Ｂ−Ａ，Ｅ−Ｃ−Ｂ−Ａ，Ｅ−Ｃ−Ｄ−Ａ，Ｅ−Ｄ−Ａがある。このうちルートＥ−Ｂ−Ａ，Ｅ−Ｄ−Ａを、候補パスとして見立てることができる。図１１に、図９からルートＥ−Ｂ−Ａを経由するパスを設定した状態を示す。図１２に、図９からルートＥ−Ｄ−Ａを経由するパスを設定した状態を示す。図１１および図１２について各リソースの占有状態を表３に示す。  
【表３】
2006025014.tif 000005
【００３４】
表３の比較結果から、ルートＥ−Ｄ−Ａ（図１２）が最も優位であることが分かる。よってルートＥ−Ｄ−Ａが選択され、このルートにパスが設定される。以上のような手順を経ることにより、ネットワークリソースを万遍なく使用したパスルートを設定することが可能になる。
【００３５】
なお、図１２に示すパス割り付け状態の優位性は、Ｅ−Ａ間でのパス設定処理だけでなく、その前のルートＡ−Ｃ、またはルートＢ−Ｄに如何に有利な状態を実現するかによっても変わってくる。以下にこのことを説明する。  
表２から分かるように、図７の状態は図９に比べて有利ではない。仮に図７のルートにパスが設定されてしまった状態でノードＥ−Ａを結ぶパス設定要求が生じたとすると、図１３および図１４の状態が考えられる。各図につき各リソースの占有状態を、表３の＜有利度低い＞の欄に示す。表３から分かるように、例えば全てのリソースが消費されてしまうリンク（リンクＡＢ）が生じる。このように、図１３および図１４のどちらも図１１の状態の優位性には及ばない。一つずつパスを設定する処理の一連の流れの中で、最も優位となるルートを逐次選択することで、ネットワーク全体としてのパスの割り付け状態を、最終的に最も優位な状態に導くことができる。
【００３６】
以上説明したように本実施形態では、ポリシーベースの検索により唯一のパスルートだけでなく、複数の候補ルートをまず抽出する。そしてこれらのルートに対して、「通過するリンクごとのリソース占有数の最大値の少ない候補ルートほど、その順位を高くする（ルール１）」、「通過するリンクごとのリソース占有数の合計値の少ない候補ルートほど、その順位を高くする（ルール２）」、「通過するリンクごとのリソース占有数のばらつきの少ない候補ルートほど、その順位を高くする（ルール３）」、および、「通過するノードの持つリンク数の合計値の多い候補ルートほど、順位を高くする（ルール４）」というルールを適用し、最も順位の高い候補ルートにパスを設定するようにしている。
【００３７】
このようにしたので、リンクごとに万遍なくパスを設定でき、ネットワーク全体におけるリソースの占有最大数を低減してリソースを高効率で使用することが可能になる。従って局所的なリソース超過の発生を抑圧できるようになり、ネットワークの利用の効率化を図ることが可能になる。
【００３８】
なお、本発明は上記実施の形態に限定されるものではない。例えば本実施形態では全光ネットワークを例として説明した。本発明はこれに代えて、時分割多重された伝送信号をカッパーリンクを介して伝送する伝送ネットワークにも適用できる。要するに本発明は、波長リソースおよびタイムスロットリソースのいずれに対するパス割り付け処理に対しても適用できる。
【００３９】
また図５の手順は、ネットワーク上に１本ずつパスを張り足していく場合だけでなく、全てのパスを一時に張る場合にも適用できる。後者の場合には、各パスを連続的に設定するようにすれば良い。またルール１において、各リンクごとのリソース占有数の最大値が少ないルートに高い順位を与えるようにしたが、リソース占有率の最大値を比較しても良い。またリンク障害などによりネットワークトポロジが変化した場合には、これを検出した時点においてパス設定処理を再起動し、既に設定されていた各パスを再度、１本ずつ設定し直すことで、高効率なリソースの使用状態を保持することができる。
【００４０】
さらに、ポリシーベースでの適合性の上位Ｘ位指定及び許容範囲閾値指定、各候補パスと既存パスの組み合わせに対して伝送リソースの占有数もしくは占有率を用いて判定することの指定、各候補パスと既存パスの同値１位の組み合わせに対して優位判定を行うためのルーティングのポリシーもしくは別メトリック導入の指定、の組み合わせを、設定対象パスごとに設定できるようにしても良い。
【００４１】
さらに本発明は、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。
【図面の簡単な説明】
【００４２】
【図１】本発明に係わる情報伝送システムの実施の形態を示すシステム図。
【図２】図１のノードＡ〜Ｅの実施の形態を示す機能ブロック図。
【図３】図１のシステムに備わる伝送リソースの一例を示す模式図。
【図４】図３のシステムにおけるパス設定状態の一例を示す図。
【図５】本発明に係わるルーティング方法の実施の形態を示すフローチャート。
【図６】図４の状態からルートＡ−Ｂ−Ｃを経由するパスが新規に設定された状態を示す図。
【図７】図６の状態からルートＢ−Ａ−Ｄを経由するパスを設定した状態を示す図。
【図８】図６の状態からルートＢ−Ｅ−Ｄを経由するパスを設定した状態を示す図。
【図９】図８に相当するパス設定状態の、より好ましい状態を示す図。
【図１０】図６の状態からルートＢ−Ｃ−Ｄを経由するパスを設定した状態を示す図。
【図１１】図９の状態からルートＥ−Ｂ−Ａを経由するパスを設定した状態を示す図。
【図１２】図９の状態からルートＥ−Ｄ−Ａを経由するパスを設定した状態を示す図。
【図１３】図７の状態からルートＥ−Ｂ−Ａを経由するパスを設定した状態を示す図。
【図１４】図７の状態からルートＥ−Ｄ−Ａを経由するパスを設定した状態を示す図。
【符号の説明】
【００４３】
Ａ〜Ｅ…ノード、ＭＥ…監視制御装置、ＳＦ…サービスファイバ、ＰＦ…プロテクションファイバ、ＡＢ〜ＤＥ…リンク、λ１〜λ４…伝送リソース、１…現用系高速インタフェース部、２…予備系高速インタフェース部、３…低速インタフェース部、４…光クロスコネクト、５…記憶部、６…制御部、６ａ…抽出処理部、６ｂ…算出処理部、６ｃ…選定処理部、６ｄ…パス設定処理部、６ｅ…検索処理部、６ｆ…評価処理部、７…パターン発生器、８…エラー検出器、９…光スイッチ、１０…セレクタ、１００…光ファイバ、２００…低速回線
【図１】
2006025014.tif 000006
【図２】
2006025014.tif 000007
【図３】
2006025014.tif 000008
【図４】
2006025014.tif 000009
【図５】
2006025014.tif 000010
【図６】
2006025014.tif 000011
【図７】
2006025014.tif 000012
【図８】
2006025014.tif 000013
【図９】
2006025014.tif 000014
【図１０】
2006025014.tif 000015
【図１１】
2006025014.tif 000016
【図１２】
2006025014.tif 000017
【図１３】
2006025014.tif 000018
【図１４】
2006025014.tif 000019