JP3575381B2 - リンクステートルーティング用通信装置及びリンクステートルーティング用通信方法 - Google Patents
リンクステートルーティング用通信装置及びリンクステートルーティング用通信方法 Download PDFInfo
- Publication number
- JP3575381B2 JP3575381B2 JP2000083558A JP2000083558A JP3575381B2 JP 3575381 B2 JP3575381 B2 JP 3575381B2 JP 2000083558 A JP2000083558 A JP 2000083558A JP 2000083558 A JP2000083558 A JP 2000083558A JP 3575381 B2 JP3575381 B2 JP 3575381B2
- Authority
- JP
- Japan
- Prior art keywords
- link
- route
- resource information
- calculated
- communication device
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/302—Route determination based on requested QoS
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5619—Network Node Interface, e.g. tandem connections, transit switching
- H04L2012/562—Routing
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は、単階層ネットワークまたは階層化ネットワークにおいて、各階層内のノード間、あるいは、階層をまたがったノード間において、リンクまたはノードのトポロジー情報、および、コネクション品質（クオリティオブサービス（Ｑｕａｌｉｔｙ ｏｆ Ｓｅｒｖｉｃｅ：ＱｏＳ）情報を経路情報として相互に交換することにより、ネットワーク全体のトポロジー情報およびＱｏＳ情報を認識し、経路選択を行うリンクステートルーティング用通信装置に関する。
【０００２】
【従来の技術】
従来、この種のリンクステートルーティング用通信装置は、処理を高速化するために、コネクション設定要求を受け付ける前に、事前経路計算を行い、この事前計算経路を記憶しておき、実際にコネクション設定要求があったときに、記憶していた事前計算経路が、呼が要求するサービス品質を満足する場合には、その事前計算経路を使用し、満足しない場合には、経路を計算し直す、という処理を行っていた。
【０００３】
従来のリンクステートルーティング用通信装置の一例が次の文献に記載されている。
【０００４】
発行日：１９９６年８月
学会誌名：ＩＥＩＣＥ ＴＲＡＳＡＣＴＩＯＮＳ ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｖｏｌ．Ｅ７９−Ｂ，Ｎｏ．８
掲載論文の題名：「ＡＴＭ Ｒｏｕｔｉｎｇ Ａｌｇｏｒｉｔｈｍｓ ｗｉｔｈ Ｍｕｌｔｉｐｌｅ ＱｏＳ Ｒｅｑｕｉｒｅｍｅｎｔｓ ｆｏｒ Ｍｕｌｔｉｍｅｄｉａ Ｉｎｔｅｒｎｅｔｗｏｒｋｉｎｇ」
掲載ページ：９９９−１００７ページ
図１９は上記の文献に記載されているリンクステートルーティング用通信装置のブロック図である。
【０００５】
図１９に示すように、この従来のリンクステートルーティング用通信装置は、他の通信装置からリンクリソース情報を受信するリンクリソース情報受信手段１と、プログラム制御により動作するデータ処理装置２と、情報を記憶する記憶装置３と、コネクションの目的地およびそのコネクション品質に対する要求を受信するコネクション要求受信手段４と、目的地へのコネクションを設定するコネクション設定手段５と、からなっている。
【０００６】
記憶装置３は、リンクリソース情報記憶部３１と、事前計算経路記憶部３２と、を備えている。
【０００７】
リンクリソース情報記憶部３１は、他の通信装置から受信したリンクリソース情報を記憶している。リンクリソース情報の例としては、リンク上の利用可能帯域や遅延時間等がある。
【０００８】
事前計算経路記憶部３２は、事前計算経路トポロジー記憶部３２１と、事前計算経路リソース情報記憶部３２２と、を備えている。
【０００９】
事前計算経路トポロジー記憶部３２１は、事前計算経路が目的地に到達するまでに経由する一連の通信装置またはリンクの集合を経路トポロジーとして記憶している。
【００１０】
事前計算経路リソース情報記憶部３２２は、事前計算経路トポロジー記憶部３２１に記憶された経路トポロジーに対応する経路リソース情報を記憶している。経路リソース情報の例としては、経路上の利用可能帯域や遅延時間等がある。
【００１１】
経路リソース情報は、経路に含まれるリンクのリンクリソース情報によって計算される。例えば、経路リソース情報の一例である経路上の利用可能帯域は、その経路に含まれるリンクのもつ利用可能帯域の最小値で与えられる。
【００１２】
事前計算経路リソース情報記憶部３２２が記憶している経路リソース情報の更新は、リンクリソース情報記憶部３１の内容が更新されたときに、もしくは、リンクリソース情報記憶部３１の内容の更新とは独立に定期的に行われる。
【００１３】
データ処理装置２は、リンクリソース情報更新手段２１と、事前経路計算手段２２と、経路抽出手段２３と、を備えている。
【００１４】
リンクリソース情報更新手段２１は、リンクリソース情報受信手段１から与えられたリンクリソース情報とリンクリソース情報記憶部３１に記憶されたリンクリソース情報とを比較し、リンクリソース情報に変更のあったリンクを抽出した後、リンクリソース情報記憶部３１に記憶されたリンクリソース情報のうち、該当するリンクリソース情報を更新する。
【００１５】
事前経路計算手段２２は、コネクション設定要求を受け付ける前に、リンクリソース情報記憶部３１に記憶されたリンクリソース情報を用いて、目的地毎に一つの経路を事前に計算する。計算より得られた事前計算経路のうち、経路トポロジーに関する情報を事前計算経路トポロジー記憶部３２１に、経路リソースに関する情報を事前計算経路リソース情報記憶部３２２にそれぞれ登録する。
【００１６】
経路抽出手段２３は、事前計算経路抽出手段２３１と、オンデマンド経路抽出手段２３２と、を備えている。
【００１７】
事前計算経路抽出手段２３１は、コネクション要求受信手段４から与えられたコネクションを設定する目的地およびコネクション品質に対する要求をキーとして、事前計算経路リソース情報記憶部３２２に記憶されている経路リソース情報を探索し、要求を満たしている事前計算経路の候補を検索する。
【００１８】
オンデマンド経路抽出手段２３２は、リンクリソース情報記憶部３１に記憶されているリンクリソース情報に基づき、コネクション品質要求を満たす経路を計算する。
【００１９】
次に、図１９、図２０および図２１を参照して、以上のような構成を有する従来のリンクステートルーティング用通信装置の動作を、コネクション要求が発生した場合と、リンクリソース情報を他の通信装置から受信した場合とに分けて説明する。
【００２０】
先ず、コネクション要求が発生した場合のリンクステートルーティング用通信装置の動作は以下の通りである。
【００２１】
コネクション要求が発生すると、コネクション要求受信手段４へその旨が通知される。コネクション要求受信手段４に与えられたコネクション要求は、事前計算経路抽出手段２３１へ供給される（図２０のステップＡ１）。
【００２２】
事前計算経路抽出手段２３１は、まず、コネクションを設定する目的地までの事前計算経路を事前計算経路トポロジー記憶部３２１から検索する。次に、コネクション品質に対する要求および該当する事前計算経路をキーとして、事前計算経路リソース情報記憶部３２２に記憶されている経路リソース情報を探索し、要求を満たしている事前計算経路の候補を検索する（ステップＡ２）。
【００２３】
コネクション要求を満たす事前計算経路の候補が存在する場合には（ステップＡ３のＹＥＳ）、その事前計算経路はコネクション設定手段５へ供給され、コネクション設定が行われる（ステップＡ４）。
【００２４】
図２０のステップＡ３において、事前計算経路リソース情報記憶部３２２に記憶されている経路リソース情報を参照した結果、コネクション要求を満たす事前計算経路が事前計算経路記憶部３２に記憶されていない場合（ステップＡ３のＮＯ）、コネクション要求はオンデマンド経路抽出手段２３２に供給される。オンデマンド経路抽出手段２３２はリンクリソース情報記憶部３１に記憶されているリンクリソース情報に基づき、コネクション品質要求を満たす経路を計算する（ステップＡ５）。
【００２５】
計算の結果、コネクション品質要求を満たす経路が存在する場合には（ステップＡ６のＹＥＳ）、その経路はコネクション設定手段５へ供給され、コネクション設定が行われる（ステップＡ４）。
【００２６】
一方、コネクション品質要求を満たす経路が存在しない場合には（ステップＡ６のＮＯ）、そのコネクションは拒否される（ステップＡ７）。
【００２７】
次に、リンクリソース情報を他の通信装置から受信した場合のリンクステートルーティング用通信装置の動作は以下の通りである。
【００２８】
リンクリソース情報を他の通信装置から受信した場合（図２１のステップＢ０）、受信したリンクリソース情報は、リンクリソース情報受信手段１からリンクリソース情報更新手段２１へ供給される。リンクリソース情報更新手段２１は、リンクリソース情報受信手段１から与えられたリンクリソース情報とリンクリソース情報記憶部３１に記憶されたリンクリソース情報とを比較し、リンクリソース情報に変更のあったリンクを抽出する（ステップＢ１）。
【００２９】
そして、リンクリソース情報記憶部３１に記憶されたリンクリソース情報のうち、該当するリンクリソース情報を更新する（ステップＢ２）。
【００３０】
図１９に示した従来のリンクステートルーティング用通信装置は、単階層ネットワークにおける使用を前提として構成されている。
【００３１】
大規模な階層化ネットワークにおいては、各階層間で要約したリンクリソース情報を交換するための境界通信装置が必要となる。ここに、境界通信装置とは、ある階層に含まれ、他の階層へ接続する通信装置のことである。
【００３２】
従来のリンクステートルーティング用境界通信装置の一例が次の文献に記載されている。
【００３３】
発行日：１９９９年６月
発表された国際会議名：ＩＥＥＥ／ＩＦＩＰ ＩＷＱｏＳ‘９９
掲載論文の題名：「Ｓｏｕｒｃｅ−Ｏｒｉｅｎｔｅｄ Ｔｏｐｏｌｏｇｙ Ａｇｇｒｅｇａｔｉｏｎ ｗｉｔｈ Ｍｕｌｔｉｐｌｅ ＱｏＳ」、予稿集の掲載ページ１３７−１４６ページ
図４は、上記の文献に記載されているリンクステートルーティング用境界通信装置のブロック図である。
【００３４】
図４に示すように、この従来のリンクステートルーティング用境界通信装置は、他の通信装置からリンクリソース情報を受信するリンクリソース情報受信手段１と、プログラム制御により動作するデータ処理装置６と、情報を記憶する記憶装置７と、要約した情報を他の階層の境界通信装置へ送信する要約情報送信手段８と、からなっている。
【００３５】
記憶装置７はリンクリソース情報記憶部３１を備えている。
【００３６】
リンクリソース情報記憶部３１は、図１に示した従来のリンクステートルーティング用通信装置におけるリンクリソース情報記憶部３１と同様の構造及び作用を有するものである。
【００３７】
データ処理装置６は、リンクリソース情報更新手段２１と、要約情報計算手段６１と、を備えている。
【００３８】
リンクリソース情報更新手段２１は、リンクリソース情報受信手段１からリンクリソース情報を受け取ると、先ず、リンクリソース情報記憶部３１が記憶しているリンクリソース情報を更新する。リンクリソース情報更新手段２１は、次いで、要約情報計算手段６１に、リンクリソース情報記憶部３１の記憶内容が更新されたことを通知する。
【００３９】
要約情報計算手段６１は、リンクリソース情報更新手段２１から、リンクリソース情報記憶部３１の記憶内容が更新されたことを告げられると、リンクリソース情報記憶部３１の記憶内容を参照しながら、他階層に対して、自階層から先のネットワーク状態を要約した情報を計算し、新しい要約情報を要約情報送信手段８へ供給する。
【００４０】
要約情報送信手段８は、計算された新しい要約情報を別階層の境界通信装置へ伝達する。
【００４１】
図１に示したリンクステートルーティング用通信装置及び図４に示したリンクステートルーティング用境界通信装置の他にも同様の種々の通信装置がこれまでに提案されている。
【００４２】
例えば、特許第２７２３０９７号（特開平９−１６２８７０号公報）は、コネクション設定時に要求された全てのＱｏＳを同時に満足できる経路を選択するＱｏＳルーティング装置を開示している。
【００４３】
特開平１１−２５２１０６号公報は、コネクション確立後において、経路上避けたいノードを回避してコネクションを再確立することができるコネクション経路変更装置を提案している。
【００４４】
特開平１０−１６４０７４号公報は、ネットワーク内におけるルーティング処理の際に通信品質要求値を満たすコネクション経路を探索するとともに、コネクション設定の負荷軽減をも可能にするＡＴＭネットワークシステムを提案している。
【００４５】
特開平１０−１３５９８０号公報は、既に設定されているコネクションの品質が劣化したときに、その品質劣化を回避することができ、かつ、コネクションの復旧を迅速に行うことができるコネクション設定装置を提案している。
【００４６】
特開平１０−１５４９７９号公報は、広帯域通信網におけるポイントツーマルチポイント呼の呼設定を経済的な接続経路を選択して行うポイントツーマルチポイント接続方法を提案している。
【００４７】
【発明が解決しようとする課題】
しかしながら、上に掲げた従来のリンクステートルーティング用境界通信装置は以下のような問題点を有していた。
【００４８】
第１の問題点は、従来の事前計算経路と動的経路検索との組み合わせ方式においては、事前計算経路候補の数が少ないために、要求されたコネクション品質を満足する事前計算経路が存在しない場合が多く、結果として経路を動的に計算し直す回数が増え、処理負荷を増大させてしまうことである。
【００４９】
その理由は、一つの宛先に対しては、一つの事前計算経路しか用いないことにある。
【００５０】
第２の問題点は、従来の事前計算経路と動的経路検索との組み合わせ方式においては、事前計算経路によるコネクション設定は失敗する確率が大きいことである。
【００５１】
その理由は、記憶された事前計算経路の情報が最新の情報を反映していないためである。
【００５２】
第３の問題点は、従来の境界通信装置においては、境界通信装置における要約情報の計算に高い処理能力が必要となることである。
【００５３】
その理由は、要約情報計算のためには、自階層内ネットワーク全体について探索することが必要であり、かつ、高い頻度で再計算を繰り返さなければならないので処理負荷が大きいためである。
【００５４】
第４の問題点は、従来の境界通信装置においては、要約情報のパケット量が増えてしまうことである。
【００５５】
その理由は、自階層内ネットワークの状態の変更が通知されるたびに、要約情報を送信しているためである。
【００５６】
本発明は以上のような従来のリンクステートルーティング用通信装置及びリンクステートルーティング用境界通信装置における問題点に鑑みてなされたものであり、コネクション品質要求を満たし、かつ、ブロック率の低い事前計算経路を用いることができる単階層ネットワークのリンクステートルーティング用通信装置を提供すること、および、要約情報を高速・低負荷で計算でき、かつ、ネットワーク中に伝播される要約情報の量を低減させることができるリンクステートルーティング用境界通信装置を提供することを目的とする。
【００６２】
【課題を解決するための手段】
この目的を達成するため、本発明は、請求項１において、他の通信装置から送られたリンクリソース情報を受信するリンクリソース情報受信手段と、リンクリソース情報を記憶するリンクリソース情報記憶部と、前記リンクリソース情報を更新するリンクリソース情報更新手段と、コネクション要求発生前に、一つの目的地に対して候補となる複数の経路を計算する複数事前経路計算手段と、前記複数事前経路計算手段によって計算された事前計算経路情報を記憶する事前計算経路記憶部と、前記事前計算経路記憶部から候補経路を抽出する事前計算経路抽出手段と、各リンクがどの事前計算経路に含まれているかを記憶したリンク−経路対応表を記憶するリンク−経路対応表記憶部と、前記リンクリソース情報更新手段から供給された更新リンクの情報をキーにして、該更新リンクと対応する事前計算経路を前記リンク−経路対応表の中から検索し、前記事前計算経路記憶部に記憶された事前計算経路情報のうち、前記更新リンクと対応する情報を更新する事前計算経路リソース情報抽出手段と、を備えたことを特徴とするリンクステートルーティング用通信装置を提供する。
【００６３】
複数事前経路計算手段は、例えば、請求項２に記載されているように、リンクリソース情報に依存せず、リンク固定のパラメータに基づいて、複数事前経路の計算を行うものとして構成することができる。
【００６５】
あるいは、複数事前経路計算手段は、請求項３に記載されているように、複数のパラメータを統合した統合化パラメータに基づいて、複数事前経路の計算を行うものとして構成することもできる。
【００６６】
請求項４に記載されているように、前記事前計算経路抽出手段は、統合化パラメータに基づいて事前計算経路を整列させ、整列した事前計算経路を先頭から順番に探索し、候補となる事前計算経路を抽出するものとして構成することができる。
【００６７】
あるいは、請求項５に記載されているように、前記事前計算経路抽出手段は、統合化パラメータを重みとする重みつきラウンドロビンによって、候補となる事前計算経路を抽出するものとして構成することもできる。
【００６８】
あるいは、請求項６に記載されているように、前記事前計算経路抽出手段は、階層化重みつきラウンドロビンによって、候補となる事前計算経路を抽出するものとして構成することもできる。
【００７６】
請求項７に記載されているように、本リンクステートルーティング用通信装置は、前記リンクリソース情報記憶部に記憶されているリンクリソース情報に基づいて、コネクション品質要求を満たす経路を計算するオンデマンド経路抽出手段をさらに備えていることが好ましい。
【００８７】
請求項８は、他の通信装置からリンクリソース情報を受信する第一の過程と、前記第一の過程において受信したリンクリソース情報と、予め記憶されているリンクリソース情報とを比較し、リソース情報に変更のあったリンクを抽出する第二の過程と、事前に計算された経路のうち、変更のあったリンクを含む経路を抽出する第三の過程と、前記第三の過程において抽出された経路の経路リソース情報を抽出し、その内容を更新する第四の過程と、を備えるリンクステートルーティング用通信方法を提供する。
【００８８】
本方法によれば、請求項１に係るリンクステートルーティング用通信装置と同様の効果を得ることができる。
【００８９】
請求項９に記載されているように、請求項８に記載の方法は、事前に計算された全ての経路の経路リソース情報を更新するまで、前記第四の過程を繰り返す第五の過程をさらに備えることが好ましい。
【０１００】
【発明の実施の形態】
以下、本発明の実施の形態について図面を参照して説明する。
【０１０１】
［第一の実施形態］
図１は、本発明の第一の実施形態に係るリンクステートルーティング用通信装置のブロック図である。
【０１０２】
本実施形態に係るリンクステートルーティング用通信装置は、以下に示す点においてのみ、図１９に示した従来のリンクステートルーティング用通信装置と異なり、それ以外の構成は同様である。従って、以下、相違点のみを説明し、同様の構成に関しては説明を省略する。
【０１０３】
第一の相違点は、本実施形態に係るリンクステートルーティング用通信装置においては、データ処理装置９が、図１９に示された従来のリンクステートルーティング用通信装置のデータ処理装置２に含まれる事前経路計算手段２２の代わりに複数事前経路計算手段２４を備えている点である。
【０１０４】
第二の相違点は、図１９に示された従来のリンクステートルーティング用通信装置のデータ処理装置２を構成している経路抽出手段２３が事前計算経路抽出手段２３１と、オンデマンド経路抽出手段２３２とからなるものであるのに対して、本実施形態に係るリンクステートルーティング用通信装置のデータ処理装置９を構成している経路抽出手段２５は、事前計算経路抽出手段２３１とオンデマンド経路抽出手段２３２とに加えて、実行可能性チェック手段２３３を備えている点である。
【０１０５】
複数事前経路計算手段２４は、コネクション要求を受け付ける前に、目的地の通信装置までの経路を複数計算し、得られた複数個の事前計算経路の経路トポロジー情報を事前計算経路トポロジー記憶部３２１に、経路上のリソース情報を事前計算経路リソース情報記憶部３２２に登録する。
【０１０６】
これにより、目的地に対して１つの事前計算経路しか存在しない従来のリンクステートルーティング用通信装置と比べ、事前計算経路が要求を満たさない場合を低減させ、結果として、動的に経路を計算し直す回数を減らすことができる。
【０１０７】
実行可能性チェック手段２３３は、事前計算経路抽出手段２３１で検索された事前計算経路に含まれる各リンクが、要求されたコネクション品質を満たしているかどうかを、リンクリソース情報記憶部３１に記憶されているリンクリソース情報と比較することにより判定する。
【０１０８】
事前計算経路記憶部３２に記憶された事前計算経路は、最新のリンクリソース情報を反映していないため、その事前計算経路を用いてコネクション設定を行うと、ブロック率が高くなる。実行可能性チェック手段２３３を用いることにより、事前計算経路抽出手段２３１によって得られた事前計算経路がコネクション品質を満たしているかどうかを判定できるため、事前計算経路を用いたコネクションのブロック率を低減させることができる。
【０１０９】
図２は、本実施形態に係るリンクステートルーティング用通信装置の動作を示すフローチャートである。以下、図２を参照して、本実施形態に係るリンクステートルーティング用通信装置の動作を説明する。
【０１１０】
図２のステップＡ１−Ａ７は、図１に示される本実施形態に係るリンクステートルーティング用通信装置におけるコネクション要求受信手段４、事前計算経路抽出手段２３１、オンデマンド経路抽出手段２３２およびコネクション設定手段５の動作を表している。これら各手段の動作は、図１９、図２０および図２１が示す従来のリンクステートルーティング用通信装置の各手段４、２３１、２３２および５の動作と同一のため、説明は省略する。
【０１１１】
図２のステップＡ３において、事前計算経路抽出手段２３１がコネクション要求を満たす事前計算経路の候補を抽出すると（ステップＡ３のＹＥＳ）、事前計算経路抽出手段２３１はその事前計算経路を実行可能性チェック手段２３３へ供給する。
【０１１２】
次に、実行可能性チェック手段２３３は供給された事前計算経路上の各リンクが、要求されたコネクション品質を満たしているかどうかを、リンクリソース情報記憶部３１に記憶されているリンクリソース情報を参照することによってチェックする（ステップＣ１）。
【０１１３】
各リンクが要求されたコネクション品質が満たしている場合は（ステップＣ１のＹＥＳ）、その事前計算経路はコネクション設定手段５へ供給され、コネクション設定が行われる（ステップＡ４）。
【０１１４】
図６のステップＣ１において、事前計算経路抽出手段２３１から実行可能性チェック手段２３３に供給された事前計算経路が、要求されたコネクション品質を満たしていない場合（ステップＣ１のＮＯ）、別の事前計算経路候補が抽出される（ステップＡ２）。
【０１１５】
次に、本実施の形態の実施例を、図面を参照して説明する。
【０１１６】
図３は、リンクリソース情報記憶部３１および事前計算経路記憶部３２の内容の例を示す。
【０１１７】
図３は、通信装置５０１、５０２、５０３、５０４および５０５から構成されるネットワークにおいて、特に通信装置５０１内のリンクリソース情報記憶部に記憶されているリンクリソース情報５１１、および、通信装置５０１から通信装置５０３への４本の事前計算経路５２１、５２２、５２３および５２４に関する事前計算経路情報５３１を示している。ここで、リンクリソース情報５１１および事前計算経路情報５３１はそれぞれ遅延情報および使用可能帯域情報からなっている。
【０１１８】
複数事前経路計算手段２４は定期的にリンクリソース情報５１１を参照しながら、事前計算経路情報５３１を更新する。
【０１１９】
ここで、通信装置５０１のコネクション要求受信手段４に対して、「通信装置５０３へ遅延８ｍｓｅｃ以下、使用帯域５０Ｍｂｐｓのコネクションを設定せよ」という要求が到着したとする。
【０１２０】
この要求に対して、事前計算経路抽出手段２３１は、事前計算経路情報５３１の事前計算経路リソース情報を参照し、要求を満たす事前計算経路として、事前計算経路５２１を抽出する。
【０１２１】
事前計算経路情報５３１の内容は、定期的に再計算されるため、古くなっている可能性がある。そこで、事前計算経路情報５３１の事前計算経路リソース情報を用いてコネクション設定を行う前に、実行可能性チェック手段２３３が、コネクション品質要求を満たしているかどうかをチェックする。
【０１２２】
事前計算経路５２１は、二つのリンク（ａ、ｂ）および（ｂ、ｃ）を含んでいる。そこで、これらのリンクに対応するリンクリソース情報５１１を参照すると、リンク（ａ、ｂ）の使用可能帯域が３０Ｍｂｐｓとなっており、要求されたコネクション品質を満たしていないことがわかる。そこで、実行可能性チェック手段２３３は、事前計算経路抽出手段２３１に通知を行い、次の候補を抽出させる。
【０１２３】
この通知を受けた事前計算経路抽出手段２３１は、事前計算経路情報５３１の事前計算経路リソース情報を参照し、要求を満たす事前計算経路として、事前計算経路５２２を抽出し、実行可能性チェック手段２３１は、事前計算経路抽出手段２３１によって抽出された事前計算経路５２２がコネクション品質要求を満たしているかどうかをチェックする。
【０１２４】
事前計算経路５２２は、リンク（ａ、ｃ）を含んでいる。リンク（ａ、ｃ）に対応するリンクリソース情報５１１を参照すると、リンク（ａ、ｃ）は使用可能帯域が６０Ｍｂｐｓ、遅延３ｍｓｅｃであり、事前計算経路５２２はコネクション品質要求を満たしていることがわかる。よって、実行可能性チェック手段２３３は、事前経路５２２をコネクションとして設定可能であると判断し、コネクション設定手段５に事前経路５２２を用いたコネクションを設定させる。
【０１２５】
次に、本実施形態によって得られる効果について説明する。
【０１２６】
本実施形態によれば、次の２つの効果を得ることができる。
【０１２７】
第１の効果は、要求されたコネクション品質を満たす経路を複数の事前計算経路の中から探索するため、コネクション品質要求を満たす事前計算経路を見つけることができる確率が増え、結果として、計算処理負荷の高いオンデマンド経路計算を行う回数を減らすことができる。よって、通信機器の計算処理負荷を低減することができる。
【０１２８】
第２の効果は、事前計算経路を抽出した後に、その事前計算経路がコネクション品質要求を満たしているかどうかを最新のリンクリソース情報を参照することにより判別しているので、事前計算経路を用いたコネクション設定の成功確率が高くなり、ブロック率を低減することができる。
【０１２９】
［第二の実施形態］
図４は、本発明の第二の実施形態に係るリンクステートルーティング用通信装置である。
【０１３０】
本実施形態に係るリンクステートルーティング用通信装置は、以下に示す点においてのみ、図１９に示した従来のリンクステートルーティング用通信装置と異なり、それ以外の構成は同様である。従って、以下、相違点のみを説明し、同様の構成に関しては説明を省略する。
【０１３１】
第一の相違点は、本実施形態に係るリンクステートルーティング用通信装置においては、データ処理装置１０が、図１９に示された従来のリンクステートルーティング用通信装置のデータ処理装置２に含まれる事前経路計算手段２２の代わりに複数事前経路計算手段２４を備えている点である。
【０１３２】
第二の相違点は、データ処理装置１０が、図１９に示された従来のリンクステートルーティング用通信装置のデータ処理装置２には含まれていない事前計算経路リソース情報抽出手段２６を備えている点である。
【０１３３】
第三の相違点は、図１９に示された従来のリンクステートルーティング用通信装置の記憶装置３の事前計算経路記憶部３２が事前計算経路トポロジー記憶部３２１と事前計算経路リソース情報記憶部３２２とからなるものであるのに対して、本実施形態に係るリンクステートルーティング用通信装置の記憶装置１１を構成している事前計算経路記憶部３３は、事前計算経路トポロジー記憶部３２１と、事前計算経路リソース情報記憶部３２２と、リンク−経路対応表記憶部３２３と、からなるものである点である。
【０１３４】
複数事前経路計算手段２４及び実行可能性チェック手段２３３は第一の実施形態におけるものと同一である。
【０１３５】
リンク−経路対応表記憶部３２３は、各リンクがどの事前計算経路に含まれているかを記憶している。
【０１３６】
事前計算経路リソース情報抽出手段２６は、リンクリソース情報更新手段２１から供給された更新リンクの情報をキーにして、リンク−経路対応表記億部３２３を検索し、対応する事前計算経路を探索する。次いで、リンクリソース情報記憶部３１もしくは事前計算経路リソース情報記憶部３２２を参照しながら、当該事前計算経路の経路リソース情報を抽出し、事前計算経路リソース情報記憶部３２２に記憶された経路リソース情報を更新する。
【０１３７】
従来のリンクステートルーティング用通信装置においては、全ての経路リソース情報を更新する必要があったのに対して、本実施形態に係るリンクステートルーティング用通信装置によれば、リンクリソース情報更新と同時に、対応する経路リソース情報のみを更新することができるようになる。
【０１３８】
図５は、本実施形態に係るリンクステートルーティング用通信装置の動作を示すフローチャートである。以下、図５を参照して、本実施形態に係るリンクステートルーティング用通信装置の動作を説明する。
【０１３９】
図５のステップＢ０乃至Ｂ２におけるリンクリソース情報受信手段１およびリンクリソース情報更新手段２１の動作は、図２１に示す従来のリンクステートルーティング用通信装置におけるリンクリソース情報受信手段１およびリンクリソース情報更新手段２１のステップＢ０乃至Ｂ２動作と同一のため、説明は省略する。
【０１４０】
リンクリソース情報に変更のあったリンクを抽出した後（ステップＢ１）、事前計算経路リソース情報抽出手段２６は、リンクリソース情報更新手段２１から供給された更新リンクをキーにして、リンク−経路対応表記億部３２３を検索し、該当リンクを含んでいる事前計算経路を探索する（ステップＦ１）。そして、リンクリソース情報記憶部３１に記憶されているリンクリソース情報を参照することにより、探索された事前計算経路の経路リソース情報を抽出し、事前計算経路リソース情報記憶部３２２の内容を更新する（ステップＦ２）。
【０１４１】
事前計算経路リソース情報記憶部３２２の内容の更新は、更新リンクを含む全ての事前計算経路の経路リソース情報を更新するまで繰り返される（ステップＦ３）。
【０１４２】
次に、本実施形態の実施例を、図面を参照して説明する。
【０１４３】
図６の表５４１は、リンク（ａ、ｃ）を含む事前計算経路の情報を表している。
【０１４４】
ここで、リンク（ａ、ｃ）のリソース情報が表５５１に示される内容に更新されたことをリンクリソース情報更新手段２１が検知したとする。
【０１４５】
表５５１の更新内容を見ると、遅延時間が２ｍｓｅｃ増加し、使用可能帯域が２０Ｍｂｐｓ減少している。
【０１４６】
表５５１の更新の結果、事前計算経路リソース情報抽出手段２６は、表５４１の内容を表５４２のように変更する。
【０１４７】
この変更は、事前計算経路に含まれる全てのリンクのリンクリソース情報を参照することにより行われるが、差分だけを更新することも可能である。
【０１４８】
図６に示した例においては、変更前に比べて遅延時間が２ｍｓｅｃ増加しているので、表５４２に示されている各事前計算経路リソース情報の遅延時間が何れも２ｍｓｅｃ増加している。
【０１４９】
また、変更前に比べて使用可能帯域は２０Ｍｂｐｓ減少し、６０Ｍｂｐｓから４０Ｍｂｐｓになっているので、表５４１に示されている各事前計算経路リソース情報の使用可能帯域のうち、４０Ｍｂｐｓよりも大きな値をもつものは一律に４０Ｍｂｐｓへと減少させる。
【０１５０】
この例で示すとおり、コネクション品質パラメータによって、差分を用いて経路リソース情報を計算する方法は異なってくる。
【０１５１】
遅延時間や遅延ばらつき（ジッタ）などの加算性（Ａｄｄｉｔｉｖｅ）パラメータを用いる場合には、差分をそのまま加算する。帯域は非加算性（Ｎｏｎ−Ａｄｄｉｔｉｖｅ）のパラメータであるため、帯域が減少し、Ｂという値（例えば、上の例における４０Ｍｂｐｓ）になった場合には、Ｂを越えない値へと変更する。帯域が増加した場合には、経路に含まれるリンクのリンクリソース情報を参照して、経路リソース情報を再計算する必要がある。
【０１５２】
次に、本実施形態により得られる効果について説明する。
【０１５３】
本実施形態においては、リンクリソース情報受信手段１がリンクリソース情報の更新を検知すると同時に、処理負荷のかかる複数事前経路計算手段２４を用いることなく、事前計算経路リソース情報記憶部３２２の更新のみを行う。これにより、事前計算経路抽出手段２３１は、第１の実施形態で用いた実行可能性チェック手段２３３を用いることなく、最新の経路リソース情報に基づいて事前計算経路の抽出を行えるようになる。その結果、通信装置の処理負荷を抑えながら、事前計算経路を用いたコネクションのブロック率を低減させることが可能となる。
【０１５４】
［第三の実施形態］
次に、本発明の第三の実施形態について説明する。
【０１５５】
複数事前経路計算手段２４が、使用可能帯域や遅延などのリンクリソース情報に依存したパラメータに基づいて、事前経路計算を行うと、リンクリソース情報の変更があるたびに事前経路を再計算することが必要となり、計算負荷が高くなってしまう。
【０１５６】
そこで、Ａｄｍｉｎｉｓｔｒａｔｉｖｅ Ｗｅｉｇｈｔや伝播遅延といった、リンクリソース情報に依存しない、リンク固有のパラメータに基づいた事前経路計算を行うことも可能である。
【０１５７】
本実施形態によれば、事前経路の再計算の頻度を抑え、計算負荷を低減することができる。
【０１５８】
［第四の実施形態］
次に、本発明の第四の実施の形態について説明する。
【０１５９】
複数事前経路計算手段２４においては、ある１つのパラメータに基づいた事前経路計算を複数回行うことにより、複数事前計算経路を計算することも可能である。
【０１６０】
例えば、ある目的地に対して、ホップ数の最も小さな経路、使用可能帯域の最も大きい経路および遅延時間の最も小さな経路の３つを、事前計算経路として計算し、記憶しておくことができる。
【０１６１】
本実施形態によれば、従来の通信装置の開発時に設計された事前経路計算手段を流用することが可能となり、設計時間を短縮することができる。
【０１６２】
［第五の実施形態］
次に、本発明の第五の実施の形態について説明する。
【０１６３】
複数事前経路計算手段２４は、使用可能帯域や遅延などの複数のパラメータをある割合で統合することにより得られる統合化パラメータに基づいて、事前経路計算を行うことも可能である。
【０１６４】
統合化パラメータの例としては、１０００／（遅延時間［ｍｓｅｃ］）＋（使用可能帯域［Ｍｂｐｓ］）がある。
【０１６５】
本実施形態によれば、事前経路計算を一度だけ行うことにより、複数のパラメータを反映した事前計算経路を得ることができるため、計算負荷を低減することができる。
【０１６６】
［第六の実施形態］
次に、本発明の第六の実施の形態について説明する。
【０１６７】
コネクション設定に用いられる経路の選択方法は、ネットワーク全体の資源を有効に活用できるかどうかに影響を与える。例えば、同一のコネクション品質要求を満たす経路の中でも、ホップ数の小さな経路を用いることにより、リンクリソースの消費を抑えることができるので、ネットワーク全体の資源を有効に活用することができる。
【０１６８】
本発明の第一および第二の実施形態においては、事前計算経路抽出手段２３１における事前計算経路の抽出順序を変更することにより、コネクション設定に用いられる経路の選択方法を制御することが可能である。
【０１６９】
このため、事前計算経路抽出手段２３１において、ある１つの統合化パラメータに基づいて事前計算経路を整列しておき、コネクション要求が発生したときに、整列した事前計算経路を頭から順番に探索することにより、候補となる事前計算経路を探索し、抽出することが可能である。
【０１７０】
図３に示した第一の実施形態の実施例において、統合化パラメータとして使用可能帯域の値を用いれば、事前計算経路５２１、５２２、５２４、５２３の順で探索が行われる。
【０１７１】
また、統合化パラメータとして、１０００／（遅延時間［ｍｓｅｃ］）＋（使用可能帯域［Ｍｂｐｓ］）を用いると、各事前計算経路５２１、５２２、５２３、５２４の統合化パラメータはそれぞれ、２２２、３９３、５３０、２１６となる。統合化パラメータの大きい順に整列すると、事前計算経路５２３、５２２、５２１、５２４の順で候補となる事前計算経路の探索が行われることになる。
【０１７２】
本実施形態によれば、統合化パラメータを変更することにより、コネクション設定に用いられる経路の選択方法を制御することが可能となり、ネットワーク全体の資源の利用状況を調節することが可能となる。
【０１７３】
［第七の実施形態］
次に、本発明の第七の実施形態について説明する。
【０１７４】
本発明の第六の実施形態においては、統合化パラメータによって整列した順番通りにのみ従って、候補となる経路抽出が行われ、それ以外の順番に従って経路抽出が行われることはない。よって、常に先頭に存在する事前計算経路が使用される確率ばかりが高くなり、使用頻度に偏りが出てしまう。
【０１７５】
このため、使用頻度における偏りを防止するため、統合化パラメータを重みとして用いる重みつきラウンドロビンによって、候補となる事前計算経路を抽出することが可能である。
【０１７６】
この実施の形態によれば、整列した順序によらず、同じ統合化パラメータを用いた事前計算経路間で負荷分散を行うことが可能となる。
【０１７７】
［第八の実施形態］
次に、本発明の第八の実施形態について説明する。
【０１７８】
事前計算経路抽出手段２３１における事前計算経路の抽出順序を変更することによりコネクション設定に用いられる経路の選択方法を制御する際に、階層化重みつきラウンドロビンによって、候補となる事前計算経路を抽出することが可能である。
【０１７９】
以下、本実施形態を図７を参照して説明する。
【０１８０】
図７に示す表５６１は、ある目的地に対する事前計算経路のうち、コネクション品質要求を満たす９本の事前計算経路ａ、ｂ、ｃ、ｄ、ｅ、ｆ、ｇ、ｈ、ｉについて示している。ここで、階層化ラウンドロビンにおける第１の重みはホップ数、第２の重みは使用可能帯域を用いている。
【０１８１】
まず、第１の重みであるホップ数を用いたラウンドロビンが行われる。このラウンドロビンにおいては、３：４：５の割合に従って事前計算経路ａ、ｂ、ｃのグループ、ｄ、ｅ、ｆのグループ、ｇ、ｈ、ｉのグループが選択される。
【０１８２】
次に、第２の重みである使用可能帯域を用いたラウンドロビンが行われる。例えば、ホップ数３の事前計算経路グループが選択されると、事前計算経路ａ、ｂ、ｃが使用可能帯域に基づいてラウンドロビンが行われるので、１００：５０：１０の割合で事前計算経路ａ、ｂ、ｃが選択される。
【０１８３】
本実施の形態においては、ある重みに対してはラウンドロビンを行わないように指定することも可能である。例えば、第１の重みとしてホップ数を用いたラウンドロビンを行わず、単に事前計算経路を整列するためにのみホップ数を用いることも可能である。このようにすることにより、常にホップ数の小さな事前計算経路を選択することが可能になる。
【０１８４】
本実施形態によれば、階層化重みを変更することにより、コネクション設定に用いられる経路の選択方法を制御することが可能となり、ネットワーク全体の資源の利用状況を調節することが可能となる。
【０１８５】
また、事前計算経路間で負荷分散を行うことが可能となる。
【０１８６】
［第九の実施形態］
図８は、本発明の第九の実施形態に係るリンクステートルーティング用通信装置のブロック図である。
【０１８７】
本実施形態に係るリンクステートルーティング用通信装置は、以下に示す点においてのみ、図１に示した第一の実施形態に係るリンクステートルーティング用通信装置と異なり、それ以外の構成は同様である。従って、以下、相違点のみを説明し、同様の構成に関しては説明を省略する。
【０１８８】
第一の相違点は、本実施形態に係るリンクステートルーティング用通信装置におけるデータ処理装置１２は、第一の実施形態におけるデータ処理装置９の構成に加え、ブロック率抽出手段２７を有している点である。
【０１８９】
第二の相違点は、本実施形態に係るリンクステートルーティング用通信装置における記憶装置１３は、第一の実施形態におけるデータ処理装置３の構成に加え、ブロック率記憶部３４を有している点である。
【０１９０】
ブロック率記憶部３４は、ブロック率閾値記憶部３４１と、ブロック回数記憶部３４２と、コネクション試行回数記憶部３４３と、を備える。
【０１９１】
本実施形態におけるブロック率記憶部３４は、リンクブロック率及びパスブロック率の何れか一方またはその両方を計測可能である。
【０１９２】
リンク（パス）ブロック率は、そのリンクがコネクションの候補として計算された回数をα、そのリンクがコネクション品質要求を満たさなかった回数をβとすると、β／αで定義される。
【０１９３】
コネクション試行回数記憶部３４３は、リンク（パス）に対して、実行可能性チェック手段２３３もしくはコネクション設定手段５が実施された回数を記憶する。
【０１９４】
ブロック回数記憶部３４２は、リンク（パス）がブロックを起こした回数を記憶する。
【０１９５】
ブロック率閾値記憶部３４１は、性能劣化の限界を表すリンク（パス）ブロック率閾値を記憶する。
【０１９６】
ブロック率抽出手段２７は、ブロック回数記憶部３４２に記憶されたリンク（パス）ブロック回数を、コネクション試行回数記憶部３４３に記憶されたコネクション試行回数で除算することにより、リンク（パス）ブロック率を計算する。ブロック率抽出手段２７は、このようにして得られたブロック率と、ブロック率閾値記憶部３４１に記憶されたブロック率閾値とを比較し、ブロック率がブロック率閾値よりも大きければ、そのリンク（パス）を用いた通信の性能が劣化したと判断し、複数事前経路計算手段２４を用いて、そのリンク（パス）を除いた事前経路経路を再計算する。
【０１９７】
実行可能性チェック手段２３３およびコネクション設定手段５は、それぞれが実施された回数をリンクブロック率記憶部３４のコネクション試行回数記憶部３４３に記憶する。
【０１９８】
図９は、本実施形態に係るリンクステートルーティング用通信装置の動作を示すフローチャートである。以下、図９を参照して、本実施形態に係るリンクステートルーティング用通信装置の動作を説明する。
【０１９９】
図９のステップＡ１乃至Ａ３およびＡ５乃至Ａ７におけるコネクション要求受信手段４、事前計算経路抽出手段２３１およびオンデマンド経路抽出手段２３２の動作は、図２に示す第一の実施形態に係るリンクステートルーティング用通信装置におけるコネクション要求受信手段４、事前計算経路抽出手段２３１およびオンデマンド経路抽出手段２３２の動作と同一のため、説明は省略する。
【０２００】
本実施形態においては、実行可能性チェック手段２３３またはコネクション設定手段５におけるリンク（パス）ブロック率を計算し、そのブロック率が、予め設定された閾値よりも大きくなった場合に、そのリンクを除いた状態で事前計算経路を再計算する。
【０２０１】
事前計算経路抽出手段２３１がコネクション要求を満たす経路の候補を抽出した場合（ステップＡ３のＹＥＳ）、実行可能性チェック手段２３３は、コネクション試行回数記憶部３４３が記憶する実行可能性チェック実施回数を１増やされる（ステップＤ１）。
【０２０２】
その後、実行可能性チェック手段２３３により、事前計算経路に含まれる各リンクが、要求されたコネクション品質を満たしているかどうかが判定される（ステップＣ１）。
【０２０３】
事前経路計算手段２３１から実行可能性チェック手段２３３に与えられた事前計算経路に含まれるリンクが、要求されたコネクション品質を満たさない場合（ステップＣ１のＮＯ）、ブロック回数記憶部３４２に記憶されている、該当リンク（パス）のブロック回数を１増やす（ステップＤ２）。
【０２０４】
次いで、ブロック率抽出手段２７によって該当リンク（パス）の実行可能性チェック時におけるブロック率を計算し、このブロック率がブロック率閾値記憶部３４１に記憶されているブロック率閾値よりも大きい場合、複数事前経路計算手段２４を用いて、該当リンク（パス）を用いない事前経路を再計算し、事前計算経路記憶部３２に記憶された事前計算経路の情報を更新する（ステップＤ３）。
【０２０５】
一方、事前経路計算手段２３１から実行可能性チェック手段２３３に与えられた事前計算経路に含まれる全てのリンクが、要求されたコネクション品質を満たす場合（ステップＣ１のＹＥＳ）、コネクション試行回数記憶部３４３が記憶する、コネクション設定手段５の実施回数を１増やし（ステップＤ４）、コネクション設定手段５にその事前計算経路を供給する。
【０２０６】
コネクション設定手段５では、与えられた事前計算経路に基づいてコネクション設定の試行を行うが（ステップＤ５）、コネクション設定の段階において、あるリンクが要求されたコネクション品質を満たさない場合（ステップＤ５のＮＯ）、ブロック回数記憶部３４２に記憶されている、該当リンク（パス）のブロック回数を１増やす（ステップＤ２）。
【０２０７】
次いで、ブロック率抽出手段２７によって、コネクション設定時における該当リンク（パス）のブロック率を計算し、このブロック率がブロック率閾値記憶部３４１に記憶されているブロック率閾値よりも大きい場合、複数事前経路計算手段２４を用いて、該当リンク（パス）を用いない事前経路を再計算し、事前計算経路記憶部３２に記憶された事前計算経路の情報を更新する。
【０２０８】
ステップＤ３において、事前経路の再計算を行う閾値として、実行可能性チェック時のブロック率Ｒとコネクション設定時におけるブロック率Ｓを線形補間した値Ｔを用いることもできる。Ｔは次式により定義される。
【０２０９】
Ｔ＝Ｙ×Ｒ＋（１−Ｙ）×Ｓ
また、ステップＤ３において、事前経路再計算を行う閾値として、時間を定義域にする関数を用いることも可能である。時間が経過するに従って、閾値が増加するような関数を用いることにより、事前経路再計算の間隔を長くすることができ、頻繁に事前経路再計算が行われることを防ぐことができる。
【０２１０】
次に、本実施形態により得られる効果について説明する。
【０２１１】
本実施形態によれば、各リンクのリンクブロック率を算出することにより、事前計算経路記憶部３２に記憶された事前計算経路の性能の性能劣化を検知し、劣化部分の特定をすることが可能となる。そして、劣化部分を取り除いた状態で事前計算経路を再計算するため、常に低いブロック率を実現する事前計算経路を使用することが可能となる。
［第十の実施形態］
図１０は、本発明の第十の実施形態に係るリンクステートルーティング用通信装置のブロック図である。
【０２１２】
本実施形態に係るリンクステートルーティング用通信装置は、以下に示す点においてのみ、図１に示した第一の実施形態に係るリンクステートルーティング用通信装置と異なり、それ以外の構成は同様である。従って、以下、相違点のみを説明し、同様の構成に関しては説明を省略する。
【０２１３】
第一の相違点は、本実施形態に係るリンクステートルーティング用通信装置におけるデータ処理装置１４は、第一の実施形態におけるデータ処理装置９の構成に加えて、リンク品質判定手段２８を有している点である。
【０２１４】
第二の相違点は、本実施形態に係るリンクステートルーティング用通信装置における記憶装置１５は、第一の実施形態におけるデータ処理装置３の構成に加え、リンク品質閾値記憶部３５を有している点である。
【０２１５】
リンク品質閾値記憶部３５は、使用可能な最低品質を表すリンク品質閾値を記憶している。
【０２１６】
リンク品質判定手段２８は、リンクリソース情報更新手段２１から供給された、更新リンクのリンクリソース情報と、リンク品質閾値記憶部３５に記憶されたリンク品質閾値とを比較することにより、変更のあったリンクの品質が許容できる最低品質を満たしているかどうかを判定する。リンク品質閾値よりも品質の悪いリンクが存在する場合、複数事前経路計算手段２４を用いて該当リンクを除いた事前経路を再計算し、事前計算経路記憶部３２に記憶された事前計算経路の情報を更新する。
【０２１７】
図１１は、本実施形態に係るリンクステートルーティング用通信装置の動作を示すフローチャートである。以下、図１１を参照して、本実施形態に係るリンクステートルーティング用通信装置の動作を説明する。
【０２１８】
図１１のステップＢ０乃至Ｂ２におけるリンクリソース情報受信手段１およびリンクリソース情報更新手段２１の動作は、図２１に示す従来のリンクステートルーティング用通信装置におけるリンクリソース情報受信手段１およびリンクリソース情報更新手段２１のステップＢ０乃至Ｂ２動作と同一のため、説明は省略する。
【０２１９】
リンクリソース情報更新手段２１は、リンクリソース情報受信手段１から与えられたリンクリソース情報とリンクリソース情報記憶部３１に記憶されたリンクリソース情報とを比較し、更新リンクの情報を抽出し、抽出した情報をリンク品質判定手段２８に供給する（ステップＢ１）。
【０２２０】
リンク品質判定手段２８は、供給された更新リンクのリソース情報と、リンク品質閾値記憶部３５に記憶されているリンク品質閾値とを比較する（ステップＥ１）。
【０２２１】
その結果、更新リンクのリソース情報がリンク品質閾値に比べて品質劣化していることが判明すると（ステップＥ１のＮＯ）、複数事前経路計算手段２４を用いて、更新リンクを除いた事前計算経路を再計算し、事前計算経路記憶部３２に記憶された事前計算経路を更新する（ステップＥ２）。
【０２２２】
次に、本実施形態により得られる効果について説明する。
【０２２３】
本実施形態によれば、リンクリソース情報受信手段１より得られるリンクリソース情報に基づいて、品質劣化したリンクを検知することが可能となる。そして、品質劣化を検知すると同時に、品質劣化部分を取り除いた事前計算経路を再計算することにより、ブロック率を低減する事前計算経路を常時使用することが可能となる。
［第十一の実施形態］
図１２は、本発明の第十の実施形態に係るリンクステートルーティング用通信装置のブロック図である。
【０２２４】
本実施形態に係るリンクステートルーティング用通信装置は、以下に示す点においてのみ、図２２に示した従来のリンクステートルーティング用境界通信装置と異なり、それ以外の構成は同様である。従って、以下、相違点のみを説明し、同様の構成に関しては説明を省略する。
【０２２５】
第一の相違点は、本実施形態に係るリンクステートルーティング用通信装置におけるデータ処理装置１６は、図２２に示した従来のリンクステートルーティング用境界通信装置におけるデータ処理装置６に含まれる要約情報計算手段６１の代わりに、高速要約情報計算手段６２を備えている点である。
【０２２６】
第二の相違点は、本実施形態に係るリンクステートルーティング用通信装置におけるデータ処理装置１６は、図１に示した第一の実施形態に係るデータ処理装置９に含まれる複数事前経路計算手段２４を備えている点である。
【０２２７】
第三の相違点は、本実施形態に係るリンクステートルーティング用通信装置における記憶装置１７は、図２２に示した従来のリンクステートルーティング用境界通信装置における記憶装置７の構成に加え、図１に示した第一の実施形態における事前計算経路記憶部３２を含んでいる点である。
【０２２８】
高速要約情報計算手段６２は、経路リソース情報による要約情報計算手段６２１と、図４に示した第二の実施形態における事前計算経路リソース情報抽出手段２６と、を備える。
【０２２９】
経路リソース情報による要約情報計算手段６２１は、事前計算経路トポロジー情報記憶部３２１およびリンクリソース情報記憶部３１を参照し、経路リソース情報を抽出し、要約情報を計算し、計算結果を要約情報送信手段８へ供給する。このように、高速要約情報計算手段６２は、事前計算経路情報に基づいて要約情報を計算できるため、処理の高速化を実現することができる。
【０２３０】
次に、本実施形態の実施例について図１３を参照して説明する。
【０２３１】
図１３（Ａ）は、階層６０１、６０２、６０３および６０４から構成される階層化ネットワークの情報を階層６０１のために要約した結果の一例を示している。
【０２３２】
階層６０２は、通信装置５０１、５０２、５０３、５０４および５０５から構成されているネットワークである。このとき、通信装置５０１、５０３および５０５は他階層に接続しているため、境界通信装置となる。
【０２３３】
ここで、階層６０２のリンクリソース情報を、階層６０１へ送信するものとする。
【０２３４】
仮に、階層６０１のために階層６０２の情報を要約しないのであれば、全部で７本のリンクに関するリンクリソース情報を境界通信装置５０１から階層６０１へ送信することになる。
【０２３５】
一方、階層６０２の情報を要約した場合、階層６０１へは、要約情報７０２が伝達される。要約情報７０２においては、階層６０２の情報が、他階層６０３、６０４へ接続している境界通信装置５０３および５０５に直接接続するネットワークへと要約されている。よって、要約情報７０２を用いれば、図１３（Ｂ）に示すように、全部で２本のリンクに関するリンクステート情報を境界通信装置５０１から階層６０１へ送信するだけでよい。
【０２３６】
以下に、経路リソース情報による要約情報計算手段６２１が要約情報７０２の要約リンクリソース情報を計算する場合の一例を図１４および図１５を使って説明する。
【０２３７】
図１４の表５１１は階層６０２のリンクリソース情報を表し、表５３１は通信装置５０１から通信装置５０３への事前計算経路情報を表す。図１５の表５９１は表５３１を用いて計算された、境界通信装置７０２１と境界通信装置７０２３（図１３（Ｂ））とを結ぶ要約リンク情報を表している。
【０２３８】
事前計算経路リソース情報抽出手段２６は、表５３１に示されるリンクリソース情報に基づいて、境界通信装置５０３への事前計算経路５２１、５２２、５２３および５２４に関する事前計算経路リソース情報（表５３１）を計算する。
【０２３９】
要約情報計算手段６２１は、計算された事前計算経路リソース情報（表５３１）から、境界通信装置５０１と５０３との間の要約リンクリソース情報として適切なものを選択する。例えば、それぞれの経路リソース情報の中から最良値を選択する場合、要約リンクリソース情報として、遅延２ｍｓｅｃ、使用可能帯域８０Ｍｂｐｓが与えられる（図１５の表５９１におけるポリシー最良値）。
【０２４０】
また、それぞれの経路リソース情報の中から最悪値を選択する場合、要約リンクリソース情報として、遅延７ｍｓｅｃ、使用可能帯域３０Ｍｂｐｓが与えられる（図１５の表５９１におけるポリシー最悪値）。
【０２４１】
また、最良値と最悪値との線形補間の値を与える場合、遅延及び使用可能帯域は次の二式により定義される。
【０２４２】
遅延：２Ｘ＋７（１−Ｘ）＝７−５Ｘ ［ｍｓｅｃ］
使用可能帯域：８０Ｘ＋３０（１−Ｘ）＝３０＋５０Ｘ ［Ｍｂｐｓ］
ここで、Ｘは０から１の間の実数として与えることができる（図１５の表５９１におけるポリシー線形補間）。
【０２４３】
要約情報計算手段６２１は、他の要約リンクステート情報（ここでは、境界通信装置５０１と５０５との間の要約リンクステート情報）も同様にして決定する。
【０２４４】
次に、本実施形態により得られる効果について説明する。
【０２４５】
本実施形態によれば、事前計算経路を用いて要約情報を計算することにより、処理の高速化を実現することができる。
【０２４６】
［第十二の実施形態］
次に、本発明の第十二の実施形態について説明する。
【０２４７】
上述した第十一の実施形態においては、リンクリソース情報が更新されると、全ての事前計算経路リソース情報が再計算される。しかし、全ての事前計算経路リソース情報を再計算することは必ずしも必要ではなく、更新のあったリンクを含んでいる事前計算経路の経路リソース情報だけを再計算することにより、計算の回数を減らすことができる。
【０２４８】
これを実現するためには、本発明の第二の実施形態と同じく、事前計算経路記憶部３２の代わりに、リンク−経路対応表記憶部３２３を含む前記事前計算経路記憶部３３（図４参照）を採用すればよい。
【０２４９】
事前計算経路リソース情報抽出手段２６は、リンク−経路対応表記憶部３２３を参照することにより、変更のあったリンクを含んでいる事前計算経路の経路リソース情報だけを再計算できるようになる。
【０２５０】
本実施形態によれば、更新のあったリンクを含んでいる事前計算経路の経路リソース情報だけを再計算できるので、計算負荷を低減することができる。
［第十三の実施形態］
図１６は、本発明の第十三の実施形態に係るリンクステートルーティング用通信装置のブロック図である。
【０２５１】
本実施形態に係るリンクステートルーティング用通信装置は、以下に示す点においてのみ、図２２に示した従来のリンクステートルーティング用境界通信装置と異なり、それ以外の構成は同様である。従って、以下、相違点のみを説明し、同様の構成に関しては説明を省略する。
【０２５２】
第一の相違点は、本実施形態に係るリンクステートルーティング用通信装置におけるデータ処理装置１８は、図２２に示した従来のリンクステートルーティング用境界通信装置におけるデータ処理装置６の構成に加え、変化率抽出手段６３および変化率比較手段６４を備えている点である。
【０２５３】
第二の相違点は、本実施形態に係るリンクステートルーティング用通信装置における記憶装置１９は、図２２に示した従来のリンクステートルーティング用境界通信装置における記憶装置７の構成に加え、要約情報記憶部３６および変化率閾値記憶部３７を備えている点である。
【０２５４】
要約情報記憶部３６は、前回他階層へ送信した要約情報を記憶している。
【０２５５】
変化率閾値記憶部３７は、要約情報を他階層へ送信するかどうかを判断するときに用いる変化率閾値を記憶する。
【０２５６】
変化率抽出手段６３は、要約情報計算手段６１から供給された新しい要約情報と、要約情報記憶部３６が記憶する前回送信済みの古い要約情報とを比較することにより、変化率を抽出し、新しい要約情報およびその変化率を変化率比較手段６４に供給する。
【０２５７】
変化率比較手段６４は、変化率抽出手段６３から供給された変化率と、変化率閾値記憶部３７が記憶する変化率閾値とを比較し、変化率が変化率閾値よりも大きかった場合には、要約情報記憶部３６に記憶された古い要約情報を、今回計算された新しい要約情報に更新し、その新しい要約情報を要約情報送信手段８へ供給する。
【０２５８】
図１７は、本実施形態に係るリンクステートルーティング用境界通信装置の動作を示すフローチャートである。以下、図１７を参照して、本実施形態に係るリンクステートルーティング用境界通信装置の動作を説明する。
【０２５９】
リンクリソース情報更新手段２１がリンクリソース情報を受信すると（ステップＧ０）、要約情報計算手段６１は、リンクステート情報記憶部３１の内容を参照しながら、他階層に対して、自階層から先のネットワークの状態を要約した情報を計算し（ステップＧ１）、計算した要約情報を変化率抽出手段６３へ供給する。
【０２６０】
変化率抽出手段６３は、要約情報計算手段６１から供給された新しい要約情報と、要約情報記憶部３６に記憶された前回送信した古い要約情報とを比較し、変化率を抽出する（ステップＧ２）。
【０２６１】
抽出された変化率は変化率比較手段６４に供給される。
【０２６２】
変化率比較手段６４は、変化率抽出手段６３から供給された変化率と、変化率閾値記憶部３７が記憶する変化率閾値とを比較する（ステップＧ３）。
【０２６３】
変化率が変化率閾値よりも大きかった場合には（ステップＧ３のＹＥＳ）、大きな変化が発生したと判断し、要約情報記憶部３６に記憶された古い要約情報を新しい要約情報に更新し（ステップＧ４）、その新しい要約情報を要約情報送信手段８へ供給する（ステップＧ５）。
【０２６４】
変化率抽出手段６３から供給された変化率が変化率閾値より小さかった場合には（ステップＧ３のＮＯ）、変化が小さかったと判断し、計算された要約情報は送信されずに処理を終了する。
【０２６５】
次に、本実施形態の実施例について説明する。
【０２６６】
図１８に示す表５８１は、図１３に示される階層６０２内のリンク（ａ、ｅ）のリンクリソース情報を表す。図１８の表５８２は、階層６０２の要約情報を作るために用いられる事前計算経路（境界通信装置５０１から境界通信装置５０３への事前計算経路および境界通信装置５０１から境界通信装置５０５への事前計算経路）の情報を表す。表５８３は、表５８２から計算された階層６０２の要約情報を表す。
【０２６７】
表５８１に示されるように、リンク（ａ、ｅ）の遅延時間が１ｍｓｅｃから３ｍｓｅｃへ、使用可能帯域が５０Ｍｂｐｓから２０Ｍｂｐｓへ変更されたものとする。
【０２６８】
要約情報計算手段６１は、まず、事前計算経路リソース情報を更新する（表５８２）。
【０２６９】
次に、更新された事前計算経路リソース情報に基づいて、要約情報を変更する（表５８３）。
【０２７０】
変化率抽出手段６３は要約情報の変化率を計算する。ここでは、変化率として、 ｜Ｒｏｒｇ−Ｒｌａｓｔ｜／Ｒｌａｓｔ を用いている。Ｒｏｒｇは変更前のリソース情報の値、Ｒｌａｓｔは変更後のリソース情報の値を表す。
【０２７１】
要約情報全体の変化率は、例えば、要約リンクの変化率の和として求めることができる。
【０２７２】
また、要約リンクの変化率は、例えば、各リンクリソース情報における変化率の和として求めることができる。
【０２７３】
要約情報計算のポリシーとして最良値を取る場合、要約リンク（ａ、ｃ）においては、遅延時間の変化率３３％、使用可能帯域の変化率０％であるので、要約リンク（ａ、ｃ）における変化率の合計は ３３＋０＝３３％ となる。
【０２７４】
同様に、要約リンク（ａ、ｄ）においては、遅延時間の変化率２０％、使用可能帯域の変化率０％であるので、要約リンク（ａ、ｄ）における変化率の合計は ２０＋０＝２０％ となる。
【０２７５】
よって、要約情報全体の変化率は、要約リンクの変化率を合計して、５３％になる。
【０２７６】
要約情報計算のポリシーとして最悪値を取る場合、要約リンク（ａ、ｃ）においては、遅延時間の変化率１３％、使用可能帯域の変化率５０％であるので、要約リンク（ａ、ｃ）における変化率の合計は １３＋５０＝６３％ となる。
【０２７７】
同様に、要約リンク（ａ、ｄ）においては、遅延時間の変化率０％、使用可能帯域の変化率５０％であるので、要約リンク（ａ、ｄ）における変化率の合計は ０＋５０＝５０％ となる。
【０２７８】
よって、要約情報全体の変化率は、要約リンクの変化率を合計して、１１３％になる。
【０２７９】
次に、本実施形態により得られる効果について説明する。
【０２８０】
本実施形態によれば、計算した要約情報が、前回他階層の境界通信装置に通知した要約情報と比較して、どれだけ変化したのかを測定し、大きな変化が発生したときのみ、要約情報を送信することを可能とする。このように、大きな変化が発生したときのみ要約情報が送信されるため、ネットワーク中に伝播される要約情報の量を削減することができる。
【０２８１】
【発明の効果】
以上のように、本発明によれば、次のような効果を得ることができる。
【０２８２】
第１の効果は、要求に適した経路を、予め記憶した複数の事前計算経路の中から選び出すことができるので、コネクション要求時に経路を再計算する手間が減り、高速なコネクション設定を行うことが可能になることである。
【０２８３】
その理由は、１つの目的地に対して複数の事前計算経路を計算し、その中から要求に適した候補経路を抽出しているからである。
【０２８４】
第２の効果は、事前計算経路を用いたコネクションのブロック率が低減されることである。
【０２８５】
その理由は、実行可能性チェック手段もしくは事前計算経路更新手段の作用により、最新のリンクリソース情報を事前計算経路に反映させることができるためである。
【０２８６】
第３の効果は、高速な要約情報計算が可能となり、境界通信装置における処理負荷を低減できることである。
【０２８７】
その理由は、事前計算経路を用いた要約情報計算を行うためである。
【０２８８】
第４の効果は、ネットワーク中に伝播する要約情報の量を低減し、他の境界通信装置における要約情報受信による一連の処理を省くことができることである。
【０２８９】
その理由は、要約情報の変化率に応じて、要約情報の計算もしくは送信を制御することができるからである。
【図面の簡単な説明】
【図１】本発明の第一の実施形態に係るリンクステートルーティング用境界通信装置の構成を示すブロック図である。
【図２】本発明の第一の実施形態に係るリンクステートルーティング用境界通信装置の動作を示すフローチャートである。
【図３】本発明の第一の実施形態に係るリンクステートルーティング用境界通信装置の実施例を示す概略図である。
【図４】本発明の第二の実施形態に係るリンクステートルーティング用境界通信装置の構成を示すブロック図である。
【図５】本発明の第二の実施形態に係るリンクステートルーティング用境界通信装置の動作を示すフローチャートである。
【図６】本発明の第二の実施形態に係るリンクステートルーティング用境界通信装置の実施例における事前計算経路リソース情報を表す表である。
【図７】本発明の第八の実施形態に係るリンクステートルーティング用境界通信装置の実施例における事前計算経路リソース情報を表す表である。
【図８】本発明の第九の実施形態に係るリンクステートルーティング用境界通信装置の構成を示すブロック図である。
【図９】本発明の第九の実施形態に係るリンクステートルーティング用境界通信装置の動作を示すフローチャートである。
【図１０】本発明の第十の実施形態に係るリンクステートルーティング用境界通信装置の構成を示すブロック図である。
【図１１】本発明の第十の実施形態に係るリンクステートルーティング用境界通信装置の動作を示すフローチャートである。
【図１２】本発明の第十一の実施形態に係るリンクステートルーティング用境界通信装置の構成を示すブロック図である。
【図１３】本発明の第十一の実施形態に係るリンクステートルーティング用境界通信装置の第一の実施例を示す概略図である。
【図１４】本発明の第十一の実施形態に係るリンクステートルーティング用境界通信装置の第二の実施例を示す概略図である。
【図１５】本発明の第十一の実施形態に係るリンクステートルーティング用境界通信装置の第三の実施例における事前計算経路リソース情報を表す表である。
【図１６】本発明の第十三の実施形態に係るリンクステートルーティング用境界通信装置の構成を示すブロック図である。
【図１７】本発明の第十三の実施形態に係るリンクステートルーティング用境界通信装置の動作を示すフローチャートである。
【図１８】本発明の第十三の実施形態に係るリンクステートルーティング用境界通信装置の実施例における事前計算経路リソース情報を表す表である。
【図１９】従来のリンクステートルーティング用通信装置の構成を示すブロック図である。
【図２０】図１９に示した従来のリンクステートルーティング用通信装置のコネクション要求受信時の動作を示すフローチャートである。
【図２１】図１９に示した従来のリンクステートルーティング用通信装置のリンクリソース情報受信時の動作を示すフローチャートである。
【図２２】従来のリンクステートルーティング用境界通信装置の構成を示すブロック図である。
【符号の説明】
１ リンクリソース情報受信手段
２１ リンクリソース情報更新手段
２２ 事前経路計算手段
２３１ 事前計算経路抽出手段
２３２ オンデマンド経路抽出手段
２３３ 実行可能性チェック手段
２４ 複数事前経路計算手段
２５ 経路抽出手段
２６ 事前計算経路リソース情報抽出手段
２７ ブロック率抽出手段
２８ リンク品質判定手段
３ 記憶装置
３１ リンクリソース情報記憶部
３２ 事前計算経路記憶部
３２１ 事前計算経路トポロジー記憶部
３２２ 事前計算経路リソース情報記憶部
３２３ リンク−経路対応表記憶部
３３ 事前計算経路記憶部
３４ ブロック率記憶部
３４１ ブロック率閾値記憶部
３４２ ブロック回数記憶部
３４３ コネクション試行回数記憶部
３５ リンク品質閾値記憶部
３６ 要約情報記憶部
３７ 変化率閾値記憶部
４ コネクション要求受信手段
５ コネクション設定手段
６ データ処理装置
６１ 要約情報計算手段
６２ 高速要約情報計算手段
６２１ 経路リソース情報による要約情報計算手段
６３ 変化率抽出手段
６４ 変化率比較手段
７ 記憶装置
８ 要約情報送信手段
９、１０、１２、１４、１６ データ処理装置
１１、１３、１５、１７ 記憶装置
５０１、５０２、５０３、５０４、５０５ リンクステートルーティング用通信装置
５１１ リンクリソース情報
５２１、５２２、５２３、５２４ 事前計算経路
５３１ 事前計算経路情報
５４１ リンク（ａ、ｃ）を含む事前計算経路情報
５４２ リンク（ａ、ｃ）を含む事前計算経路情報
５５１ リンク（ａ、ｃ）のリソース情報の変化
５６１ ある目的地に対する事前計算経路のうちコネクション品質要求を満たすもの
５８１ リンク（ａ、ｅ）のリソース情報の変化
５８２ 事前計算経路のリソース情報の変化
５８３ 要約リンクのリソース情報の変化
５９１ 要約リンク情報
６０１、６０２、６０３、６０４ 階層化ネットワークにおける各階層
７０２ 階層６０２の要約リンク表現
７０２１、７０２２、７０２３ 階層６０２の境界通信装置
【発明の属する技術分野】
本発明は、単階層ネットワークまたは階層化ネットワークにおいて、各階層内のノード間、あるいは、階層をまたがったノード間において、リンクまたはノードのトポロジー情報、および、コネクション品質（クオリティオブサービス（Ｑｕａｌｉｔｙ ｏｆ Ｓｅｒｖｉｃｅ：ＱｏＳ）情報を経路情報として相互に交換することにより、ネットワーク全体のトポロジー情報およびＱｏＳ情報を認識し、経路選択を行うリンクステートルーティング用通信装置に関する。
【０００２】
【従来の技術】
従来、この種のリンクステートルーティング用通信装置は、処理を高速化するために、コネクション設定要求を受け付ける前に、事前経路計算を行い、この事前計算経路を記憶しておき、実際にコネクション設定要求があったときに、記憶していた事前計算経路が、呼が要求するサービス品質を満足する場合には、その事前計算経路を使用し、満足しない場合には、経路を計算し直す、という処理を行っていた。
【０００３】
従来のリンクステートルーティング用通信装置の一例が次の文献に記載されている。
【０００４】
発行日：１９９６年８月
学会誌名：ＩＥＩＣＥ ＴＲＡＳＡＣＴＩＯＮＳ ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｖｏｌ．Ｅ７９−Ｂ，Ｎｏ．８
掲載論文の題名：「ＡＴＭ Ｒｏｕｔｉｎｇ Ａｌｇｏｒｉｔｈｍｓ ｗｉｔｈ Ｍｕｌｔｉｐｌｅ ＱｏＳ Ｒｅｑｕｉｒｅｍｅｎｔｓ ｆｏｒ Ｍｕｌｔｉｍｅｄｉａ Ｉｎｔｅｒｎｅｔｗｏｒｋｉｎｇ」
掲載ページ：９９９−１００７ページ
図１９は上記の文献に記載されているリンクステートルーティング用通信装置のブロック図である。
【０００５】
図１９に示すように、この従来のリンクステートルーティング用通信装置は、他の通信装置からリンクリソース情報を受信するリンクリソース情報受信手段１と、プログラム制御により動作するデータ処理装置２と、情報を記憶する記憶装置３と、コネクションの目的地およびそのコネクション品質に対する要求を受信するコネクション要求受信手段４と、目的地へのコネクションを設定するコネクション設定手段５と、からなっている。
【０００６】
記憶装置３は、リンクリソース情報記憶部３１と、事前計算経路記憶部３２と、を備えている。
【０００７】
リンクリソース情報記憶部３１は、他の通信装置から受信したリンクリソース情報を記憶している。リンクリソース情報の例としては、リンク上の利用可能帯域や遅延時間等がある。
【０００８】
事前計算経路記憶部３２は、事前計算経路トポロジー記憶部３２１と、事前計算経路リソース情報記憶部３２２と、を備えている。
【０００９】
事前計算経路トポロジー記憶部３２１は、事前計算経路が目的地に到達するまでに経由する一連の通信装置またはリンクの集合を経路トポロジーとして記憶している。
【００１０】
事前計算経路リソース情報記憶部３２２は、事前計算経路トポロジー記憶部３２１に記憶された経路トポロジーに対応する経路リソース情報を記憶している。経路リソース情報の例としては、経路上の利用可能帯域や遅延時間等がある。
【００１１】
経路リソース情報は、経路に含まれるリンクのリンクリソース情報によって計算される。例えば、経路リソース情報の一例である経路上の利用可能帯域は、その経路に含まれるリンクのもつ利用可能帯域の最小値で与えられる。
【００１２】
事前計算経路リソース情報記憶部３２２が記憶している経路リソース情報の更新は、リンクリソース情報記憶部３１の内容が更新されたときに、もしくは、リンクリソース情報記憶部３１の内容の更新とは独立に定期的に行われる。
【００１３】
データ処理装置２は、リンクリソース情報更新手段２１と、事前経路計算手段２２と、経路抽出手段２３と、を備えている。
【００１４】
リンクリソース情報更新手段２１は、リンクリソース情報受信手段１から与えられたリンクリソース情報とリンクリソース情報記憶部３１に記憶されたリンクリソース情報とを比較し、リンクリソース情報に変更のあったリンクを抽出した後、リンクリソース情報記憶部３１に記憶されたリンクリソース情報のうち、該当するリンクリソース情報を更新する。
【００１５】
事前経路計算手段２２は、コネクション設定要求を受け付ける前に、リンクリソース情報記憶部３１に記憶されたリンクリソース情報を用いて、目的地毎に一つの経路を事前に計算する。計算より得られた事前計算経路のうち、経路トポロジーに関する情報を事前計算経路トポロジー記憶部３２１に、経路リソースに関する情報を事前計算経路リソース情報記憶部３２２にそれぞれ登録する。
【００１６】
経路抽出手段２３は、事前計算経路抽出手段２３１と、オンデマンド経路抽出手段２３２と、を備えている。
【００１７】
事前計算経路抽出手段２３１は、コネクション要求受信手段４から与えられたコネクションを設定する目的地およびコネクション品質に対する要求をキーとして、事前計算経路リソース情報記憶部３２２に記憶されている経路リソース情報を探索し、要求を満たしている事前計算経路の候補を検索する。
【００１８】
オンデマンド経路抽出手段２３２は、リンクリソース情報記憶部３１に記憶されているリンクリソース情報に基づき、コネクション品質要求を満たす経路を計算する。
【００１９】
次に、図１９、図２０および図２１を参照して、以上のような構成を有する従来のリンクステートルーティング用通信装置の動作を、コネクション要求が発生した場合と、リンクリソース情報を他の通信装置から受信した場合とに分けて説明する。
【００２０】
先ず、コネクション要求が発生した場合のリンクステートルーティング用通信装置の動作は以下の通りである。
【００２１】
コネクション要求が発生すると、コネクション要求受信手段４へその旨が通知される。コネクション要求受信手段４に与えられたコネクション要求は、事前計算経路抽出手段２３１へ供給される（図２０のステップＡ１）。
【００２２】
事前計算経路抽出手段２３１は、まず、コネクションを設定する目的地までの事前計算経路を事前計算経路トポロジー記憶部３２１から検索する。次に、コネクション品質に対する要求および該当する事前計算経路をキーとして、事前計算経路リソース情報記憶部３２２に記憶されている経路リソース情報を探索し、要求を満たしている事前計算経路の候補を検索する（ステップＡ２）。
【００２３】
コネクション要求を満たす事前計算経路の候補が存在する場合には（ステップＡ３のＹＥＳ）、その事前計算経路はコネクション設定手段５へ供給され、コネクション設定が行われる（ステップＡ４）。
【００２４】
図２０のステップＡ３において、事前計算経路リソース情報記憶部３２２に記憶されている経路リソース情報を参照した結果、コネクション要求を満たす事前計算経路が事前計算経路記憶部３２に記憶されていない場合（ステップＡ３のＮＯ）、コネクション要求はオンデマンド経路抽出手段２３２に供給される。オンデマンド経路抽出手段２３２はリンクリソース情報記憶部３１に記憶されているリンクリソース情報に基づき、コネクション品質要求を満たす経路を計算する（ステップＡ５）。
【００２５】
計算の結果、コネクション品質要求を満たす経路が存在する場合には（ステップＡ６のＹＥＳ）、その経路はコネクション設定手段５へ供給され、コネクション設定が行われる（ステップＡ４）。
【００２６】
一方、コネクション品質要求を満たす経路が存在しない場合には（ステップＡ６のＮＯ）、そのコネクションは拒否される（ステップＡ７）。
【００２７】
次に、リンクリソース情報を他の通信装置から受信した場合のリンクステートルーティング用通信装置の動作は以下の通りである。
【００２８】
リンクリソース情報を他の通信装置から受信した場合（図２１のステップＢ０）、受信したリンクリソース情報は、リンクリソース情報受信手段１からリンクリソース情報更新手段２１へ供給される。リンクリソース情報更新手段２１は、リンクリソース情報受信手段１から与えられたリンクリソース情報とリンクリソース情報記憶部３１に記憶されたリンクリソース情報とを比較し、リンクリソース情報に変更のあったリンクを抽出する（ステップＢ１）。
【００２９】
そして、リンクリソース情報記憶部３１に記憶されたリンクリソース情報のうち、該当するリンクリソース情報を更新する（ステップＢ２）。
【００３０】
図１９に示した従来のリンクステートルーティング用通信装置は、単階層ネットワークにおける使用を前提として構成されている。
【００３１】
大規模な階層化ネットワークにおいては、各階層間で要約したリンクリソース情報を交換するための境界通信装置が必要となる。ここに、境界通信装置とは、ある階層に含まれ、他の階層へ接続する通信装置のことである。
【００３２】
従来のリンクステートルーティング用境界通信装置の一例が次の文献に記載されている。
【００３３】
発行日：１９９９年６月
発表された国際会議名：ＩＥＥＥ／ＩＦＩＰ ＩＷＱｏＳ‘９９
掲載論文の題名：「Ｓｏｕｒｃｅ−Ｏｒｉｅｎｔｅｄ Ｔｏｐｏｌｏｇｙ Ａｇｇｒｅｇａｔｉｏｎ ｗｉｔｈ Ｍｕｌｔｉｐｌｅ ＱｏＳ」、予稿集の掲載ページ１３７−１４６ページ
図４は、上記の文献に記載されているリンクステートルーティング用境界通信装置のブロック図である。
【００３４】
図４に示すように、この従来のリンクステートルーティング用境界通信装置は、他の通信装置からリンクリソース情報を受信するリンクリソース情報受信手段１と、プログラム制御により動作するデータ処理装置６と、情報を記憶する記憶装置７と、要約した情報を他の階層の境界通信装置へ送信する要約情報送信手段８と、からなっている。
【００３５】
記憶装置７はリンクリソース情報記憶部３１を備えている。
【００３６】
リンクリソース情報記憶部３１は、図１に示した従来のリンクステートルーティング用通信装置におけるリンクリソース情報記憶部３１と同様の構造及び作用を有するものである。
【００３７】
データ処理装置６は、リンクリソース情報更新手段２１と、要約情報計算手段６１と、を備えている。
【００３８】
リンクリソース情報更新手段２１は、リンクリソース情報受信手段１からリンクリソース情報を受け取ると、先ず、リンクリソース情報記憶部３１が記憶しているリンクリソース情報を更新する。リンクリソース情報更新手段２１は、次いで、要約情報計算手段６１に、リンクリソース情報記憶部３１の記憶内容が更新されたことを通知する。
【００３９】
要約情報計算手段６１は、リンクリソース情報更新手段２１から、リンクリソース情報記憶部３１の記憶内容が更新されたことを告げられると、リンクリソース情報記憶部３１の記憶内容を参照しながら、他階層に対して、自階層から先のネットワーク状態を要約した情報を計算し、新しい要約情報を要約情報送信手段８へ供給する。
【００４０】
要約情報送信手段８は、計算された新しい要約情報を別階層の境界通信装置へ伝達する。
【００４１】
図１に示したリンクステートルーティング用通信装置及び図４に示したリンクステートルーティング用境界通信装置の他にも同様の種々の通信装置がこれまでに提案されている。
【００４２】
例えば、特許第２７２３０９７号（特開平９−１６２８７０号公報）は、コネクション設定時に要求された全てのＱｏＳを同時に満足できる経路を選択するＱｏＳルーティング装置を開示している。
【００４３】
特開平１１−２５２１０６号公報は、コネクション確立後において、経路上避けたいノードを回避してコネクションを再確立することができるコネクション経路変更装置を提案している。
【００４４】
特開平１０−１６４０７４号公報は、ネットワーク内におけるルーティング処理の際に通信品質要求値を満たすコネクション経路を探索するとともに、コネクション設定の負荷軽減をも可能にするＡＴＭネットワークシステムを提案している。
【００４５】
特開平１０−１３５９８０号公報は、既に設定されているコネクションの品質が劣化したときに、その品質劣化を回避することができ、かつ、コネクションの復旧を迅速に行うことができるコネクション設定装置を提案している。
【００４６】
特開平１０−１５４９７９号公報は、広帯域通信網におけるポイントツーマルチポイント呼の呼設定を経済的な接続経路を選択して行うポイントツーマルチポイント接続方法を提案している。
【００４７】
【発明が解決しようとする課題】
しかしながら、上に掲げた従来のリンクステートルーティング用境界通信装置は以下のような問題点を有していた。
【００４８】
第１の問題点は、従来の事前計算経路と動的経路検索との組み合わせ方式においては、事前計算経路候補の数が少ないために、要求されたコネクション品質を満足する事前計算経路が存在しない場合が多く、結果として経路を動的に計算し直す回数が増え、処理負荷を増大させてしまうことである。
【００４９】
その理由は、一つの宛先に対しては、一つの事前計算経路しか用いないことにある。
【００５０】
第２の問題点は、従来の事前計算経路と動的経路検索との組み合わせ方式においては、事前計算経路によるコネクション設定は失敗する確率が大きいことである。
【００５１】
その理由は、記憶された事前計算経路の情報が最新の情報を反映していないためである。
【００５２】
第３の問題点は、従来の境界通信装置においては、境界通信装置における要約情報の計算に高い処理能力が必要となることである。
【００５３】
その理由は、要約情報計算のためには、自階層内ネットワーク全体について探索することが必要であり、かつ、高い頻度で再計算を繰り返さなければならないので処理負荷が大きいためである。
【００５４】
第４の問題点は、従来の境界通信装置においては、要約情報のパケット量が増えてしまうことである。
【００５５】
その理由は、自階層内ネットワークの状態の変更が通知されるたびに、要約情報を送信しているためである。
【００５６】
本発明は以上のような従来のリンクステートルーティング用通信装置及びリンクステートルーティング用境界通信装置における問題点に鑑みてなされたものであり、コネクション品質要求を満たし、かつ、ブロック率の低い事前計算経路を用いることができる単階層ネットワークのリンクステートルーティング用通信装置を提供すること、および、要約情報を高速・低負荷で計算でき、かつ、ネットワーク中に伝播される要約情報の量を低減させることができるリンクステートルーティング用境界通信装置を提供することを目的とする。
【００６２】
【課題を解決するための手段】
この目的を達成するため、本発明は、請求項１において、他の通信装置から送られたリンクリソース情報を受信するリンクリソース情報受信手段と、リンクリソース情報を記憶するリンクリソース情報記憶部と、前記リンクリソース情報を更新するリンクリソース情報更新手段と、コネクション要求発生前に、一つの目的地に対して候補となる複数の経路を計算する複数事前経路計算手段と、前記複数事前経路計算手段によって計算された事前計算経路情報を記憶する事前計算経路記憶部と、前記事前計算経路記憶部から候補経路を抽出する事前計算経路抽出手段と、各リンクがどの事前計算経路に含まれているかを記憶したリンク−経路対応表を記憶するリンク−経路対応表記憶部と、前記リンクリソース情報更新手段から供給された更新リンクの情報をキーにして、該更新リンクと対応する事前計算経路を前記リンク−経路対応表の中から検索し、前記事前計算経路記憶部に記憶された事前計算経路情報のうち、前記更新リンクと対応する情報を更新する事前計算経路リソース情報抽出手段と、を備えたことを特徴とするリンクステートルーティング用通信装置を提供する。
【００６３】
複数事前経路計算手段は、例えば、請求項２に記載されているように、リンクリソース情報に依存せず、リンク固定のパラメータに基づいて、複数事前経路の計算を行うものとして構成することができる。
【００６５】
あるいは、複数事前経路計算手段は、請求項３に記載されているように、複数のパラメータを統合した統合化パラメータに基づいて、複数事前経路の計算を行うものとして構成することもできる。
【００６６】
請求項４に記載されているように、前記事前計算経路抽出手段は、統合化パラメータに基づいて事前計算経路を整列させ、整列した事前計算経路を先頭から順番に探索し、候補となる事前計算経路を抽出するものとして構成することができる。
【００６７】
あるいは、請求項５に記載されているように、前記事前計算経路抽出手段は、統合化パラメータを重みとする重みつきラウンドロビンによって、候補となる事前計算経路を抽出するものとして構成することもできる。
【００６８】
あるいは、請求項６に記載されているように、前記事前計算経路抽出手段は、階層化重みつきラウンドロビンによって、候補となる事前計算経路を抽出するものとして構成することもできる。
【００７６】
請求項７に記載されているように、本リンクステートルーティング用通信装置は、前記リンクリソース情報記憶部に記憶されているリンクリソース情報に基づいて、コネクション品質要求を満たす経路を計算するオンデマンド経路抽出手段をさらに備えていることが好ましい。
【００８７】
請求項８は、他の通信装置からリンクリソース情報を受信する第一の過程と、前記第一の過程において受信したリンクリソース情報と、予め記憶されているリンクリソース情報とを比較し、リソース情報に変更のあったリンクを抽出する第二の過程と、事前に計算された経路のうち、変更のあったリンクを含む経路を抽出する第三の過程と、前記第三の過程において抽出された経路の経路リソース情報を抽出し、その内容を更新する第四の過程と、を備えるリンクステートルーティング用通信方法を提供する。
【００８８】
本方法によれば、請求項１に係るリンクステートルーティング用通信装置と同様の効果を得ることができる。
【００８９】
請求項９に記載されているように、請求項８に記載の方法は、事前に計算された全ての経路の経路リソース情報を更新するまで、前記第四の過程を繰り返す第五の過程をさらに備えることが好ましい。
【０１００】
【発明の実施の形態】
以下、本発明の実施の形態について図面を参照して説明する。
【０１０１】
［第一の実施形態］
図１は、本発明の第一の実施形態に係るリンクステートルーティング用通信装置のブロック図である。
【０１０２】
本実施形態に係るリンクステートルーティング用通信装置は、以下に示す点においてのみ、図１９に示した従来のリンクステートルーティング用通信装置と異なり、それ以外の構成は同様である。従って、以下、相違点のみを説明し、同様の構成に関しては説明を省略する。
【０１０３】
第一の相違点は、本実施形態に係るリンクステートルーティング用通信装置においては、データ処理装置９が、図１９に示された従来のリンクステートルーティング用通信装置のデータ処理装置２に含まれる事前経路計算手段２２の代わりに複数事前経路計算手段２４を備えている点である。
【０１０４】
第二の相違点は、図１９に示された従来のリンクステートルーティング用通信装置のデータ処理装置２を構成している経路抽出手段２３が事前計算経路抽出手段２３１と、オンデマンド経路抽出手段２３２とからなるものであるのに対して、本実施形態に係るリンクステートルーティング用通信装置のデータ処理装置９を構成している経路抽出手段２５は、事前計算経路抽出手段２３１とオンデマンド経路抽出手段２３２とに加えて、実行可能性チェック手段２３３を備えている点である。
【０１０５】
複数事前経路計算手段２４は、コネクション要求を受け付ける前に、目的地の通信装置までの経路を複数計算し、得られた複数個の事前計算経路の経路トポロジー情報を事前計算経路トポロジー記憶部３２１に、経路上のリソース情報を事前計算経路リソース情報記憶部３２２に登録する。
【０１０６】
これにより、目的地に対して１つの事前計算経路しか存在しない従来のリンクステートルーティング用通信装置と比べ、事前計算経路が要求を満たさない場合を低減させ、結果として、動的に経路を計算し直す回数を減らすことができる。
【０１０７】
実行可能性チェック手段２３３は、事前計算経路抽出手段２３１で検索された事前計算経路に含まれる各リンクが、要求されたコネクション品質を満たしているかどうかを、リンクリソース情報記憶部３１に記憶されているリンクリソース情報と比較することにより判定する。
【０１０８】
事前計算経路記憶部３２に記憶された事前計算経路は、最新のリンクリソース情報を反映していないため、その事前計算経路を用いてコネクション設定を行うと、ブロック率が高くなる。実行可能性チェック手段２３３を用いることにより、事前計算経路抽出手段２３１によって得られた事前計算経路がコネクション品質を満たしているかどうかを判定できるため、事前計算経路を用いたコネクションのブロック率を低減させることができる。
【０１０９】
図２は、本実施形態に係るリンクステートルーティング用通信装置の動作を示すフローチャートである。以下、図２を参照して、本実施形態に係るリンクステートルーティング用通信装置の動作を説明する。
【０１１０】
図２のステップＡ１−Ａ７は、図１に示される本実施形態に係るリンクステートルーティング用通信装置におけるコネクション要求受信手段４、事前計算経路抽出手段２３１、オンデマンド経路抽出手段２３２およびコネクション設定手段５の動作を表している。これら各手段の動作は、図１９、図２０および図２１が示す従来のリンクステートルーティング用通信装置の各手段４、２３１、２３２および５の動作と同一のため、説明は省略する。
【０１１１】
図２のステップＡ３において、事前計算経路抽出手段２３１がコネクション要求を満たす事前計算経路の候補を抽出すると（ステップＡ３のＹＥＳ）、事前計算経路抽出手段２３１はその事前計算経路を実行可能性チェック手段２３３へ供給する。
【０１１２】
次に、実行可能性チェック手段２３３は供給された事前計算経路上の各リンクが、要求されたコネクション品質を満たしているかどうかを、リンクリソース情報記憶部３１に記憶されているリンクリソース情報を参照することによってチェックする（ステップＣ１）。
【０１１３】
各リンクが要求されたコネクション品質が満たしている場合は（ステップＣ１のＹＥＳ）、その事前計算経路はコネクション設定手段５へ供給され、コネクション設定が行われる（ステップＡ４）。
【０１１４】
図６のステップＣ１において、事前計算経路抽出手段２３１から実行可能性チェック手段２３３に供給された事前計算経路が、要求されたコネクション品質を満たしていない場合（ステップＣ１のＮＯ）、別の事前計算経路候補が抽出される（ステップＡ２）。
【０１１５】
次に、本実施の形態の実施例を、図面を参照して説明する。
【０１１６】
図３は、リンクリソース情報記憶部３１および事前計算経路記憶部３２の内容の例を示す。
【０１１７】
図３は、通信装置５０１、５０２、５０３、５０４および５０５から構成されるネットワークにおいて、特に通信装置５０１内のリンクリソース情報記憶部に記憶されているリンクリソース情報５１１、および、通信装置５０１から通信装置５０３への４本の事前計算経路５２１、５２２、５２３および５２４に関する事前計算経路情報５３１を示している。ここで、リンクリソース情報５１１および事前計算経路情報５３１はそれぞれ遅延情報および使用可能帯域情報からなっている。
【０１１８】
複数事前経路計算手段２４は定期的にリンクリソース情報５１１を参照しながら、事前計算経路情報５３１を更新する。
【０１１９】
ここで、通信装置５０１のコネクション要求受信手段４に対して、「通信装置５０３へ遅延８ｍｓｅｃ以下、使用帯域５０Ｍｂｐｓのコネクションを設定せよ」という要求が到着したとする。
【０１２０】
この要求に対して、事前計算経路抽出手段２３１は、事前計算経路情報５３１の事前計算経路リソース情報を参照し、要求を満たす事前計算経路として、事前計算経路５２１を抽出する。
【０１２１】
事前計算経路情報５３１の内容は、定期的に再計算されるため、古くなっている可能性がある。そこで、事前計算経路情報５３１の事前計算経路リソース情報を用いてコネクション設定を行う前に、実行可能性チェック手段２３３が、コネクション品質要求を満たしているかどうかをチェックする。
【０１２２】
事前計算経路５２１は、二つのリンク（ａ、ｂ）および（ｂ、ｃ）を含んでいる。そこで、これらのリンクに対応するリンクリソース情報５１１を参照すると、リンク（ａ、ｂ）の使用可能帯域が３０Ｍｂｐｓとなっており、要求されたコネクション品質を満たしていないことがわかる。そこで、実行可能性チェック手段２３３は、事前計算経路抽出手段２３１に通知を行い、次の候補を抽出させる。
【０１２３】
この通知を受けた事前計算経路抽出手段２３１は、事前計算経路情報５３１の事前計算経路リソース情報を参照し、要求を満たす事前計算経路として、事前計算経路５２２を抽出し、実行可能性チェック手段２３１は、事前計算経路抽出手段２３１によって抽出された事前計算経路５２２がコネクション品質要求を満たしているかどうかをチェックする。
【０１２４】
事前計算経路５２２は、リンク（ａ、ｃ）を含んでいる。リンク（ａ、ｃ）に対応するリンクリソース情報５１１を参照すると、リンク（ａ、ｃ）は使用可能帯域が６０Ｍｂｐｓ、遅延３ｍｓｅｃであり、事前計算経路５２２はコネクション品質要求を満たしていることがわかる。よって、実行可能性チェック手段２３３は、事前経路５２２をコネクションとして設定可能であると判断し、コネクション設定手段５に事前経路５２２を用いたコネクションを設定させる。
【０１２５】
次に、本実施形態によって得られる効果について説明する。
【０１２６】
本実施形態によれば、次の２つの効果を得ることができる。
【０１２７】
第１の効果は、要求されたコネクション品質を満たす経路を複数の事前計算経路の中から探索するため、コネクション品質要求を満たす事前計算経路を見つけることができる確率が増え、結果として、計算処理負荷の高いオンデマンド経路計算を行う回数を減らすことができる。よって、通信機器の計算処理負荷を低減することができる。
【０１２８】
第２の効果は、事前計算経路を抽出した後に、その事前計算経路がコネクション品質要求を満たしているかどうかを最新のリンクリソース情報を参照することにより判別しているので、事前計算経路を用いたコネクション設定の成功確率が高くなり、ブロック率を低減することができる。
【０１２９】
［第二の実施形態］
図４は、本発明の第二の実施形態に係るリンクステートルーティング用通信装置である。
【０１３０】
本実施形態に係るリンクステートルーティング用通信装置は、以下に示す点においてのみ、図１９に示した従来のリンクステートルーティング用通信装置と異なり、それ以外の構成は同様である。従って、以下、相違点のみを説明し、同様の構成に関しては説明を省略する。
【０１３１】
第一の相違点は、本実施形態に係るリンクステートルーティング用通信装置においては、データ処理装置１０が、図１９に示された従来のリンクステートルーティング用通信装置のデータ処理装置２に含まれる事前経路計算手段２２の代わりに複数事前経路計算手段２４を備えている点である。
【０１３２】
第二の相違点は、データ処理装置１０が、図１９に示された従来のリンクステートルーティング用通信装置のデータ処理装置２には含まれていない事前計算経路リソース情報抽出手段２６を備えている点である。
【０１３３】
第三の相違点は、図１９に示された従来のリンクステートルーティング用通信装置の記憶装置３の事前計算経路記憶部３２が事前計算経路トポロジー記憶部３２１と事前計算経路リソース情報記憶部３２２とからなるものであるのに対して、本実施形態に係るリンクステートルーティング用通信装置の記憶装置１１を構成している事前計算経路記憶部３３は、事前計算経路トポロジー記憶部３２１と、事前計算経路リソース情報記憶部３２２と、リンク−経路対応表記憶部３２３と、からなるものである点である。
【０１３４】
複数事前経路計算手段２４及び実行可能性チェック手段２３３は第一の実施形態におけるものと同一である。
【０１３５】
リンク−経路対応表記憶部３２３は、各リンクがどの事前計算経路に含まれているかを記憶している。
【０１３６】
事前計算経路リソース情報抽出手段２６は、リンクリソース情報更新手段２１から供給された更新リンクの情報をキーにして、リンク−経路対応表記億部３２３を検索し、対応する事前計算経路を探索する。次いで、リンクリソース情報記憶部３１もしくは事前計算経路リソース情報記憶部３２２を参照しながら、当該事前計算経路の経路リソース情報を抽出し、事前計算経路リソース情報記憶部３２２に記憶された経路リソース情報を更新する。
【０１３７】
従来のリンクステートルーティング用通信装置においては、全ての経路リソース情報を更新する必要があったのに対して、本実施形態に係るリンクステートルーティング用通信装置によれば、リンクリソース情報更新と同時に、対応する経路リソース情報のみを更新することができるようになる。
【０１３８】
図５は、本実施形態に係るリンクステートルーティング用通信装置の動作を示すフローチャートである。以下、図５を参照して、本実施形態に係るリンクステートルーティング用通信装置の動作を説明する。
【０１３９】
図５のステップＢ０乃至Ｂ２におけるリンクリソース情報受信手段１およびリンクリソース情報更新手段２１の動作は、図２１に示す従来のリンクステートルーティング用通信装置におけるリンクリソース情報受信手段１およびリンクリソース情報更新手段２１のステップＢ０乃至Ｂ２動作と同一のため、説明は省略する。
【０１４０】
リンクリソース情報に変更のあったリンクを抽出した後（ステップＢ１）、事前計算経路リソース情報抽出手段２６は、リンクリソース情報更新手段２１から供給された更新リンクをキーにして、リンク−経路対応表記億部３２３を検索し、該当リンクを含んでいる事前計算経路を探索する（ステップＦ１）。そして、リンクリソース情報記憶部３１に記憶されているリンクリソース情報を参照することにより、探索された事前計算経路の経路リソース情報を抽出し、事前計算経路リソース情報記憶部３２２の内容を更新する（ステップＦ２）。
【０１４１】
事前計算経路リソース情報記憶部３２２の内容の更新は、更新リンクを含む全ての事前計算経路の経路リソース情報を更新するまで繰り返される（ステップＦ３）。
【０１４２】
次に、本実施形態の実施例を、図面を参照して説明する。
【０１４３】
図６の表５４１は、リンク（ａ、ｃ）を含む事前計算経路の情報を表している。
【０１４４】
ここで、リンク（ａ、ｃ）のリソース情報が表５５１に示される内容に更新されたことをリンクリソース情報更新手段２１が検知したとする。
【０１４５】
表５５１の更新内容を見ると、遅延時間が２ｍｓｅｃ増加し、使用可能帯域が２０Ｍｂｐｓ減少している。
【０１４６】
表５５１の更新の結果、事前計算経路リソース情報抽出手段２６は、表５４１の内容を表５４２のように変更する。
【０１４７】
この変更は、事前計算経路に含まれる全てのリンクのリンクリソース情報を参照することにより行われるが、差分だけを更新することも可能である。
【０１４８】
図６に示した例においては、変更前に比べて遅延時間が２ｍｓｅｃ増加しているので、表５４２に示されている各事前計算経路リソース情報の遅延時間が何れも２ｍｓｅｃ増加している。
【０１４９】
また、変更前に比べて使用可能帯域は２０Ｍｂｐｓ減少し、６０Ｍｂｐｓから４０Ｍｂｐｓになっているので、表５４１に示されている各事前計算経路リソース情報の使用可能帯域のうち、４０Ｍｂｐｓよりも大きな値をもつものは一律に４０Ｍｂｐｓへと減少させる。
【０１５０】
この例で示すとおり、コネクション品質パラメータによって、差分を用いて経路リソース情報を計算する方法は異なってくる。
【０１５１】
遅延時間や遅延ばらつき（ジッタ）などの加算性（Ａｄｄｉｔｉｖｅ）パラメータを用いる場合には、差分をそのまま加算する。帯域は非加算性（Ｎｏｎ−Ａｄｄｉｔｉｖｅ）のパラメータであるため、帯域が減少し、Ｂという値（例えば、上の例における４０Ｍｂｐｓ）になった場合には、Ｂを越えない値へと変更する。帯域が増加した場合には、経路に含まれるリンクのリンクリソース情報を参照して、経路リソース情報を再計算する必要がある。
【０１５２】
次に、本実施形態により得られる効果について説明する。
【０１５３】
本実施形態においては、リンクリソース情報受信手段１がリンクリソース情報の更新を検知すると同時に、処理負荷のかかる複数事前経路計算手段２４を用いることなく、事前計算経路リソース情報記憶部３２２の更新のみを行う。これにより、事前計算経路抽出手段２３１は、第１の実施形態で用いた実行可能性チェック手段２３３を用いることなく、最新の経路リソース情報に基づいて事前計算経路の抽出を行えるようになる。その結果、通信装置の処理負荷を抑えながら、事前計算経路を用いたコネクションのブロック率を低減させることが可能となる。
【０１５４】
［第三の実施形態］
次に、本発明の第三の実施形態について説明する。
【０１５５】
複数事前経路計算手段２４が、使用可能帯域や遅延などのリンクリソース情報に依存したパラメータに基づいて、事前経路計算を行うと、リンクリソース情報の変更があるたびに事前経路を再計算することが必要となり、計算負荷が高くなってしまう。
【０１５６】
そこで、Ａｄｍｉｎｉｓｔｒａｔｉｖｅ Ｗｅｉｇｈｔや伝播遅延といった、リンクリソース情報に依存しない、リンク固有のパラメータに基づいた事前経路計算を行うことも可能である。
【０１５７】
本実施形態によれば、事前経路の再計算の頻度を抑え、計算負荷を低減することができる。
【０１５８】
［第四の実施形態］
次に、本発明の第四の実施の形態について説明する。
【０１５９】
複数事前経路計算手段２４においては、ある１つのパラメータに基づいた事前経路計算を複数回行うことにより、複数事前計算経路を計算することも可能である。
【０１６０】
例えば、ある目的地に対して、ホップ数の最も小さな経路、使用可能帯域の最も大きい経路および遅延時間の最も小さな経路の３つを、事前計算経路として計算し、記憶しておくことができる。
【０１６１】
本実施形態によれば、従来の通信装置の開発時に設計された事前経路計算手段を流用することが可能となり、設計時間を短縮することができる。
【０１６２】
［第五の実施形態］
次に、本発明の第五の実施の形態について説明する。
【０１６３】
複数事前経路計算手段２４は、使用可能帯域や遅延などの複数のパラメータをある割合で統合することにより得られる統合化パラメータに基づいて、事前経路計算を行うことも可能である。
【０１６４】
統合化パラメータの例としては、１０００／（遅延時間［ｍｓｅｃ］）＋（使用可能帯域［Ｍｂｐｓ］）がある。
【０１６５】
本実施形態によれば、事前経路計算を一度だけ行うことにより、複数のパラメータを反映した事前計算経路を得ることができるため、計算負荷を低減することができる。
【０１６６】
［第六の実施形態］
次に、本発明の第六の実施の形態について説明する。
【０１６７】
コネクション設定に用いられる経路の選択方法は、ネットワーク全体の資源を有効に活用できるかどうかに影響を与える。例えば、同一のコネクション品質要求を満たす経路の中でも、ホップ数の小さな経路を用いることにより、リンクリソースの消費を抑えることができるので、ネットワーク全体の資源を有効に活用することができる。
【０１６８】
本発明の第一および第二の実施形態においては、事前計算経路抽出手段２３１における事前計算経路の抽出順序を変更することにより、コネクション設定に用いられる経路の選択方法を制御することが可能である。
【０１６９】
このため、事前計算経路抽出手段２３１において、ある１つの統合化パラメータに基づいて事前計算経路を整列しておき、コネクション要求が発生したときに、整列した事前計算経路を頭から順番に探索することにより、候補となる事前計算経路を探索し、抽出することが可能である。
【０１７０】
図３に示した第一の実施形態の実施例において、統合化パラメータとして使用可能帯域の値を用いれば、事前計算経路５２１、５２２、５２４、５２３の順で探索が行われる。
【０１７１】
また、統合化パラメータとして、１０００／（遅延時間［ｍｓｅｃ］）＋（使用可能帯域［Ｍｂｐｓ］）を用いると、各事前計算経路５２１、５２２、５２３、５２４の統合化パラメータはそれぞれ、２２２、３９３、５３０、２１６となる。統合化パラメータの大きい順に整列すると、事前計算経路５２３、５２２、５２１、５２４の順で候補となる事前計算経路の探索が行われることになる。
【０１７２】
本実施形態によれば、統合化パラメータを変更することにより、コネクション設定に用いられる経路の選択方法を制御することが可能となり、ネットワーク全体の資源の利用状況を調節することが可能となる。
【０１７３】
［第七の実施形態］
次に、本発明の第七の実施形態について説明する。
【０１７４】
本発明の第六の実施形態においては、統合化パラメータによって整列した順番通りにのみ従って、候補となる経路抽出が行われ、それ以外の順番に従って経路抽出が行われることはない。よって、常に先頭に存在する事前計算経路が使用される確率ばかりが高くなり、使用頻度に偏りが出てしまう。
【０１７５】
このため、使用頻度における偏りを防止するため、統合化パラメータを重みとして用いる重みつきラウンドロビンによって、候補となる事前計算経路を抽出することが可能である。
【０１７６】
この実施の形態によれば、整列した順序によらず、同じ統合化パラメータを用いた事前計算経路間で負荷分散を行うことが可能となる。
【０１７７】
［第八の実施形態］
次に、本発明の第八の実施形態について説明する。
【０１７８】
事前計算経路抽出手段２３１における事前計算経路の抽出順序を変更することによりコネクション設定に用いられる経路の選択方法を制御する際に、階層化重みつきラウンドロビンによって、候補となる事前計算経路を抽出することが可能である。
【０１７９】
以下、本実施形態を図７を参照して説明する。
【０１８０】
図７に示す表５６１は、ある目的地に対する事前計算経路のうち、コネクション品質要求を満たす９本の事前計算経路ａ、ｂ、ｃ、ｄ、ｅ、ｆ、ｇ、ｈ、ｉについて示している。ここで、階層化ラウンドロビンにおける第１の重みはホップ数、第２の重みは使用可能帯域を用いている。
【０１８１】
まず、第１の重みであるホップ数を用いたラウンドロビンが行われる。このラウンドロビンにおいては、３：４：５の割合に従って事前計算経路ａ、ｂ、ｃのグループ、ｄ、ｅ、ｆのグループ、ｇ、ｈ、ｉのグループが選択される。
【０１８２】
次に、第２の重みである使用可能帯域を用いたラウンドロビンが行われる。例えば、ホップ数３の事前計算経路グループが選択されると、事前計算経路ａ、ｂ、ｃが使用可能帯域に基づいてラウンドロビンが行われるので、１００：５０：１０の割合で事前計算経路ａ、ｂ、ｃが選択される。
【０１８３】
本実施の形態においては、ある重みに対してはラウンドロビンを行わないように指定することも可能である。例えば、第１の重みとしてホップ数を用いたラウンドロビンを行わず、単に事前計算経路を整列するためにのみホップ数を用いることも可能である。このようにすることにより、常にホップ数の小さな事前計算経路を選択することが可能になる。
【０１８４】
本実施形態によれば、階層化重みを変更することにより、コネクション設定に用いられる経路の選択方法を制御することが可能となり、ネットワーク全体の資源の利用状況を調節することが可能となる。
【０１８５】
また、事前計算経路間で負荷分散を行うことが可能となる。
【０１８６】
［第九の実施形態］
図８は、本発明の第九の実施形態に係るリンクステートルーティング用通信装置のブロック図である。
【０１８７】
本実施形態に係るリンクステートルーティング用通信装置は、以下に示す点においてのみ、図１に示した第一の実施形態に係るリンクステートルーティング用通信装置と異なり、それ以外の構成は同様である。従って、以下、相違点のみを説明し、同様の構成に関しては説明を省略する。
【０１８８】
第一の相違点は、本実施形態に係るリンクステートルーティング用通信装置におけるデータ処理装置１２は、第一の実施形態におけるデータ処理装置９の構成に加え、ブロック率抽出手段２７を有している点である。
【０１８９】
第二の相違点は、本実施形態に係るリンクステートルーティング用通信装置における記憶装置１３は、第一の実施形態におけるデータ処理装置３の構成に加え、ブロック率記憶部３４を有している点である。
【０１９０】
ブロック率記憶部３４は、ブロック率閾値記憶部３４１と、ブロック回数記憶部３４２と、コネクション試行回数記憶部３４３と、を備える。
【０１９１】
本実施形態におけるブロック率記憶部３４は、リンクブロック率及びパスブロック率の何れか一方またはその両方を計測可能である。
【０１９２】
リンク（パス）ブロック率は、そのリンクがコネクションの候補として計算された回数をα、そのリンクがコネクション品質要求を満たさなかった回数をβとすると、β／αで定義される。
【０１９３】
コネクション試行回数記憶部３４３は、リンク（パス）に対して、実行可能性チェック手段２３３もしくはコネクション設定手段５が実施された回数を記憶する。
【０１９４】
ブロック回数記憶部３４２は、リンク（パス）がブロックを起こした回数を記憶する。
【０１９５】
ブロック率閾値記憶部３４１は、性能劣化の限界を表すリンク（パス）ブロック率閾値を記憶する。
【０１９６】
ブロック率抽出手段２７は、ブロック回数記憶部３４２に記憶されたリンク（パス）ブロック回数を、コネクション試行回数記憶部３４３に記憶されたコネクション試行回数で除算することにより、リンク（パス）ブロック率を計算する。ブロック率抽出手段２７は、このようにして得られたブロック率と、ブロック率閾値記憶部３４１に記憶されたブロック率閾値とを比較し、ブロック率がブロック率閾値よりも大きければ、そのリンク（パス）を用いた通信の性能が劣化したと判断し、複数事前経路計算手段２４を用いて、そのリンク（パス）を除いた事前経路経路を再計算する。
【０１９７】
実行可能性チェック手段２３３およびコネクション設定手段５は、それぞれが実施された回数をリンクブロック率記憶部３４のコネクション試行回数記憶部３４３に記憶する。
【０１９８】
図９は、本実施形態に係るリンクステートルーティング用通信装置の動作を示すフローチャートである。以下、図９を参照して、本実施形態に係るリンクステートルーティング用通信装置の動作を説明する。
【０１９９】
図９のステップＡ１乃至Ａ３およびＡ５乃至Ａ７におけるコネクション要求受信手段４、事前計算経路抽出手段２３１およびオンデマンド経路抽出手段２３２の動作は、図２に示す第一の実施形態に係るリンクステートルーティング用通信装置におけるコネクション要求受信手段４、事前計算経路抽出手段２３１およびオンデマンド経路抽出手段２３２の動作と同一のため、説明は省略する。
【０２００】
本実施形態においては、実行可能性チェック手段２３３またはコネクション設定手段５におけるリンク（パス）ブロック率を計算し、そのブロック率が、予め設定された閾値よりも大きくなった場合に、そのリンクを除いた状態で事前計算経路を再計算する。
【０２０１】
事前計算経路抽出手段２３１がコネクション要求を満たす経路の候補を抽出した場合（ステップＡ３のＹＥＳ）、実行可能性チェック手段２３３は、コネクション試行回数記憶部３４３が記憶する実行可能性チェック実施回数を１増やされる（ステップＤ１）。
【０２０２】
その後、実行可能性チェック手段２３３により、事前計算経路に含まれる各リンクが、要求されたコネクション品質を満たしているかどうかが判定される（ステップＣ１）。
【０２０３】
事前経路計算手段２３１から実行可能性チェック手段２３３に与えられた事前計算経路に含まれるリンクが、要求されたコネクション品質を満たさない場合（ステップＣ１のＮＯ）、ブロック回数記憶部３４２に記憶されている、該当リンク（パス）のブロック回数を１増やす（ステップＤ２）。
【０２０４】
次いで、ブロック率抽出手段２７によって該当リンク（パス）の実行可能性チェック時におけるブロック率を計算し、このブロック率がブロック率閾値記憶部３４１に記憶されているブロック率閾値よりも大きい場合、複数事前経路計算手段２４を用いて、該当リンク（パス）を用いない事前経路を再計算し、事前計算経路記憶部３２に記憶された事前計算経路の情報を更新する（ステップＤ３）。
【０２０５】
一方、事前経路計算手段２３１から実行可能性チェック手段２３３に与えられた事前計算経路に含まれる全てのリンクが、要求されたコネクション品質を満たす場合（ステップＣ１のＹＥＳ）、コネクション試行回数記憶部３４３が記憶する、コネクション設定手段５の実施回数を１増やし（ステップＤ４）、コネクション設定手段５にその事前計算経路を供給する。
【０２０６】
コネクション設定手段５では、与えられた事前計算経路に基づいてコネクション設定の試行を行うが（ステップＤ５）、コネクション設定の段階において、あるリンクが要求されたコネクション品質を満たさない場合（ステップＤ５のＮＯ）、ブロック回数記憶部３４２に記憶されている、該当リンク（パス）のブロック回数を１増やす（ステップＤ２）。
【０２０７】
次いで、ブロック率抽出手段２７によって、コネクション設定時における該当リンク（パス）のブロック率を計算し、このブロック率がブロック率閾値記憶部３４１に記憶されているブロック率閾値よりも大きい場合、複数事前経路計算手段２４を用いて、該当リンク（パス）を用いない事前経路を再計算し、事前計算経路記憶部３２に記憶された事前計算経路の情報を更新する。
【０２０８】
ステップＤ３において、事前経路の再計算を行う閾値として、実行可能性チェック時のブロック率Ｒとコネクション設定時におけるブロック率Ｓを線形補間した値Ｔを用いることもできる。Ｔは次式により定義される。
【０２０９】
Ｔ＝Ｙ×Ｒ＋（１−Ｙ）×Ｓ
また、ステップＤ３において、事前経路再計算を行う閾値として、時間を定義域にする関数を用いることも可能である。時間が経過するに従って、閾値が増加するような関数を用いることにより、事前経路再計算の間隔を長くすることができ、頻繁に事前経路再計算が行われることを防ぐことができる。
【０２１０】
次に、本実施形態により得られる効果について説明する。
【０２１１】
本実施形態によれば、各リンクのリンクブロック率を算出することにより、事前計算経路記憶部３２に記憶された事前計算経路の性能の性能劣化を検知し、劣化部分の特定をすることが可能となる。そして、劣化部分を取り除いた状態で事前計算経路を再計算するため、常に低いブロック率を実現する事前計算経路を使用することが可能となる。
［第十の実施形態］
図１０は、本発明の第十の実施形態に係るリンクステートルーティング用通信装置のブロック図である。
【０２１２】
本実施形態に係るリンクステートルーティング用通信装置は、以下に示す点においてのみ、図１に示した第一の実施形態に係るリンクステートルーティング用通信装置と異なり、それ以外の構成は同様である。従って、以下、相違点のみを説明し、同様の構成に関しては説明を省略する。
【０２１３】
第一の相違点は、本実施形態に係るリンクステートルーティング用通信装置におけるデータ処理装置１４は、第一の実施形態におけるデータ処理装置９の構成に加えて、リンク品質判定手段２８を有している点である。
【０２１４】
第二の相違点は、本実施形態に係るリンクステートルーティング用通信装置における記憶装置１５は、第一の実施形態におけるデータ処理装置３の構成に加え、リンク品質閾値記憶部３５を有している点である。
【０２１５】
リンク品質閾値記憶部３５は、使用可能な最低品質を表すリンク品質閾値を記憶している。
【０２１６】
リンク品質判定手段２８は、リンクリソース情報更新手段２１から供給された、更新リンクのリンクリソース情報と、リンク品質閾値記憶部３５に記憶されたリンク品質閾値とを比較することにより、変更のあったリンクの品質が許容できる最低品質を満たしているかどうかを判定する。リンク品質閾値よりも品質の悪いリンクが存在する場合、複数事前経路計算手段２４を用いて該当リンクを除いた事前経路を再計算し、事前計算経路記憶部３２に記憶された事前計算経路の情報を更新する。
【０２１７】
図１１は、本実施形態に係るリンクステートルーティング用通信装置の動作を示すフローチャートである。以下、図１１を参照して、本実施形態に係るリンクステートルーティング用通信装置の動作を説明する。
【０２１８】
図１１のステップＢ０乃至Ｂ２におけるリンクリソース情報受信手段１およびリンクリソース情報更新手段２１の動作は、図２１に示す従来のリンクステートルーティング用通信装置におけるリンクリソース情報受信手段１およびリンクリソース情報更新手段２１のステップＢ０乃至Ｂ２動作と同一のため、説明は省略する。
【０２１９】
リンクリソース情報更新手段２１は、リンクリソース情報受信手段１から与えられたリンクリソース情報とリンクリソース情報記憶部３１に記憶されたリンクリソース情報とを比較し、更新リンクの情報を抽出し、抽出した情報をリンク品質判定手段２８に供給する（ステップＢ１）。
【０２２０】
リンク品質判定手段２８は、供給された更新リンクのリソース情報と、リンク品質閾値記憶部３５に記憶されているリンク品質閾値とを比較する（ステップＥ１）。
【０２２１】
その結果、更新リンクのリソース情報がリンク品質閾値に比べて品質劣化していることが判明すると（ステップＥ１のＮＯ）、複数事前経路計算手段２４を用いて、更新リンクを除いた事前計算経路を再計算し、事前計算経路記憶部３２に記憶された事前計算経路を更新する（ステップＥ２）。
【０２２２】
次に、本実施形態により得られる効果について説明する。
【０２２３】
本実施形態によれば、リンクリソース情報受信手段１より得られるリンクリソース情報に基づいて、品質劣化したリンクを検知することが可能となる。そして、品質劣化を検知すると同時に、品質劣化部分を取り除いた事前計算経路を再計算することにより、ブロック率を低減する事前計算経路を常時使用することが可能となる。
［第十一の実施形態］
図１２は、本発明の第十の実施形態に係るリンクステートルーティング用通信装置のブロック図である。
【０２２４】
本実施形態に係るリンクステートルーティング用通信装置は、以下に示す点においてのみ、図２２に示した従来のリンクステートルーティング用境界通信装置と異なり、それ以外の構成は同様である。従って、以下、相違点のみを説明し、同様の構成に関しては説明を省略する。
【０２２５】
第一の相違点は、本実施形態に係るリンクステートルーティング用通信装置におけるデータ処理装置１６は、図２２に示した従来のリンクステートルーティング用境界通信装置におけるデータ処理装置６に含まれる要約情報計算手段６１の代わりに、高速要約情報計算手段６２を備えている点である。
【０２２６】
第二の相違点は、本実施形態に係るリンクステートルーティング用通信装置におけるデータ処理装置１６は、図１に示した第一の実施形態に係るデータ処理装置９に含まれる複数事前経路計算手段２４を備えている点である。
【０２２７】
第三の相違点は、本実施形態に係るリンクステートルーティング用通信装置における記憶装置１７は、図２２に示した従来のリンクステートルーティング用境界通信装置における記憶装置７の構成に加え、図１に示した第一の実施形態における事前計算経路記憶部３２を含んでいる点である。
【０２２８】
高速要約情報計算手段６２は、経路リソース情報による要約情報計算手段６２１と、図４に示した第二の実施形態における事前計算経路リソース情報抽出手段２６と、を備える。
【０２２９】
経路リソース情報による要約情報計算手段６２１は、事前計算経路トポロジー情報記憶部３２１およびリンクリソース情報記憶部３１を参照し、経路リソース情報を抽出し、要約情報を計算し、計算結果を要約情報送信手段８へ供給する。このように、高速要約情報計算手段６２は、事前計算経路情報に基づいて要約情報を計算できるため、処理の高速化を実現することができる。
【０２３０】
次に、本実施形態の実施例について図１３を参照して説明する。
【０２３１】
図１３（Ａ）は、階層６０１、６０２、６０３および６０４から構成される階層化ネットワークの情報を階層６０１のために要約した結果の一例を示している。
【０２３２】
階層６０２は、通信装置５０１、５０２、５０３、５０４および５０５から構成されているネットワークである。このとき、通信装置５０１、５０３および５０５は他階層に接続しているため、境界通信装置となる。
【０２３３】
ここで、階層６０２のリンクリソース情報を、階層６０１へ送信するものとする。
【０２３４】
仮に、階層６０１のために階層６０２の情報を要約しないのであれば、全部で７本のリンクに関するリンクリソース情報を境界通信装置５０１から階層６０１へ送信することになる。
【０２３５】
一方、階層６０２の情報を要約した場合、階層６０１へは、要約情報７０２が伝達される。要約情報７０２においては、階層６０２の情報が、他階層６０３、６０４へ接続している境界通信装置５０３および５０５に直接接続するネットワークへと要約されている。よって、要約情報７０２を用いれば、図１３（Ｂ）に示すように、全部で２本のリンクに関するリンクステート情報を境界通信装置５０１から階層６０１へ送信するだけでよい。
【０２３６】
以下に、経路リソース情報による要約情報計算手段６２１が要約情報７０２の要約リンクリソース情報を計算する場合の一例を図１４および図１５を使って説明する。
【０２３７】
図１４の表５１１は階層６０２のリンクリソース情報を表し、表５３１は通信装置５０１から通信装置５０３への事前計算経路情報を表す。図１５の表５９１は表５３１を用いて計算された、境界通信装置７０２１と境界通信装置７０２３（図１３（Ｂ））とを結ぶ要約リンク情報を表している。
【０２３８】
事前計算経路リソース情報抽出手段２６は、表５３１に示されるリンクリソース情報に基づいて、境界通信装置５０３への事前計算経路５２１、５２２、５２３および５２４に関する事前計算経路リソース情報（表５３１）を計算する。
【０２３９】
要約情報計算手段６２１は、計算された事前計算経路リソース情報（表５３１）から、境界通信装置５０１と５０３との間の要約リンクリソース情報として適切なものを選択する。例えば、それぞれの経路リソース情報の中から最良値を選択する場合、要約リンクリソース情報として、遅延２ｍｓｅｃ、使用可能帯域８０Ｍｂｐｓが与えられる（図１５の表５９１におけるポリシー最良値）。
【０２４０】
また、それぞれの経路リソース情報の中から最悪値を選択する場合、要約リンクリソース情報として、遅延７ｍｓｅｃ、使用可能帯域３０Ｍｂｐｓが与えられる（図１５の表５９１におけるポリシー最悪値）。
【０２４１】
また、最良値と最悪値との線形補間の値を与える場合、遅延及び使用可能帯域は次の二式により定義される。
【０２４２】
遅延：２Ｘ＋７（１−Ｘ）＝７−５Ｘ ［ｍｓｅｃ］
使用可能帯域：８０Ｘ＋３０（１−Ｘ）＝３０＋５０Ｘ ［Ｍｂｐｓ］
ここで、Ｘは０から１の間の実数として与えることができる（図１５の表５９１におけるポリシー線形補間）。
【０２４３】
要約情報計算手段６２１は、他の要約リンクステート情報（ここでは、境界通信装置５０１と５０５との間の要約リンクステート情報）も同様にして決定する。
【０２４４】
次に、本実施形態により得られる効果について説明する。
【０２４５】
本実施形態によれば、事前計算経路を用いて要約情報を計算することにより、処理の高速化を実現することができる。
【０２４６】
［第十二の実施形態］
次に、本発明の第十二の実施形態について説明する。
【０２４７】
上述した第十一の実施形態においては、リンクリソース情報が更新されると、全ての事前計算経路リソース情報が再計算される。しかし、全ての事前計算経路リソース情報を再計算することは必ずしも必要ではなく、更新のあったリンクを含んでいる事前計算経路の経路リソース情報だけを再計算することにより、計算の回数を減らすことができる。
【０２４８】
これを実現するためには、本発明の第二の実施形態と同じく、事前計算経路記憶部３２の代わりに、リンク−経路対応表記憶部３２３を含む前記事前計算経路記憶部３３（図４参照）を採用すればよい。
【０２４９】
事前計算経路リソース情報抽出手段２６は、リンク−経路対応表記憶部３２３を参照することにより、変更のあったリンクを含んでいる事前計算経路の経路リソース情報だけを再計算できるようになる。
【０２５０】
本実施形態によれば、更新のあったリンクを含んでいる事前計算経路の経路リソース情報だけを再計算できるので、計算負荷を低減することができる。
［第十三の実施形態］
図１６は、本発明の第十三の実施形態に係るリンクステートルーティング用通信装置のブロック図である。
【０２５１】
本実施形態に係るリンクステートルーティング用通信装置は、以下に示す点においてのみ、図２２に示した従来のリンクステートルーティング用境界通信装置と異なり、それ以外の構成は同様である。従って、以下、相違点のみを説明し、同様の構成に関しては説明を省略する。
【０２５２】
第一の相違点は、本実施形態に係るリンクステートルーティング用通信装置におけるデータ処理装置１８は、図２２に示した従来のリンクステートルーティング用境界通信装置におけるデータ処理装置６の構成に加え、変化率抽出手段６３および変化率比較手段６４を備えている点である。
【０２５３】
第二の相違点は、本実施形態に係るリンクステートルーティング用通信装置における記憶装置１９は、図２２に示した従来のリンクステートルーティング用境界通信装置における記憶装置７の構成に加え、要約情報記憶部３６および変化率閾値記憶部３７を備えている点である。
【０２５４】
要約情報記憶部３６は、前回他階層へ送信した要約情報を記憶している。
【０２５５】
変化率閾値記憶部３７は、要約情報を他階層へ送信するかどうかを判断するときに用いる変化率閾値を記憶する。
【０２５６】
変化率抽出手段６３は、要約情報計算手段６１から供給された新しい要約情報と、要約情報記憶部３６が記憶する前回送信済みの古い要約情報とを比較することにより、変化率を抽出し、新しい要約情報およびその変化率を変化率比較手段６４に供給する。
【０２５７】
変化率比較手段６４は、変化率抽出手段６３から供給された変化率と、変化率閾値記憶部３７が記憶する変化率閾値とを比較し、変化率が変化率閾値よりも大きかった場合には、要約情報記憶部３６に記憶された古い要約情報を、今回計算された新しい要約情報に更新し、その新しい要約情報を要約情報送信手段８へ供給する。
【０２５８】
図１７は、本実施形態に係るリンクステートルーティング用境界通信装置の動作を示すフローチャートである。以下、図１７を参照して、本実施形態に係るリンクステートルーティング用境界通信装置の動作を説明する。
【０２５９】
リンクリソース情報更新手段２１がリンクリソース情報を受信すると（ステップＧ０）、要約情報計算手段６１は、リンクステート情報記憶部３１の内容を参照しながら、他階層に対して、自階層から先のネットワークの状態を要約した情報を計算し（ステップＧ１）、計算した要約情報を変化率抽出手段６３へ供給する。
【０２６０】
変化率抽出手段６３は、要約情報計算手段６１から供給された新しい要約情報と、要約情報記憶部３６に記憶された前回送信した古い要約情報とを比較し、変化率を抽出する（ステップＧ２）。
【０２６１】
抽出された変化率は変化率比較手段６４に供給される。
【０２６２】
変化率比較手段６４は、変化率抽出手段６３から供給された変化率と、変化率閾値記憶部３７が記憶する変化率閾値とを比較する（ステップＧ３）。
【０２６３】
変化率が変化率閾値よりも大きかった場合には（ステップＧ３のＹＥＳ）、大きな変化が発生したと判断し、要約情報記憶部３６に記憶された古い要約情報を新しい要約情報に更新し（ステップＧ４）、その新しい要約情報を要約情報送信手段８へ供給する（ステップＧ５）。
【０２６４】
変化率抽出手段６３から供給された変化率が変化率閾値より小さかった場合には（ステップＧ３のＮＯ）、変化が小さかったと判断し、計算された要約情報は送信されずに処理を終了する。
【０２６５】
次に、本実施形態の実施例について説明する。
【０２６６】
図１８に示す表５８１は、図１３に示される階層６０２内のリンク（ａ、ｅ）のリンクリソース情報を表す。図１８の表５８２は、階層６０２の要約情報を作るために用いられる事前計算経路（境界通信装置５０１から境界通信装置５０３への事前計算経路および境界通信装置５０１から境界通信装置５０５への事前計算経路）の情報を表す。表５８３は、表５８２から計算された階層６０２の要約情報を表す。
【０２６７】
表５８１に示されるように、リンク（ａ、ｅ）の遅延時間が１ｍｓｅｃから３ｍｓｅｃへ、使用可能帯域が５０Ｍｂｐｓから２０Ｍｂｐｓへ変更されたものとする。
【０２６８】
要約情報計算手段６１は、まず、事前計算経路リソース情報を更新する（表５８２）。
【０２６９】
次に、更新された事前計算経路リソース情報に基づいて、要約情報を変更する（表５８３）。
【０２７０】
変化率抽出手段６３は要約情報の変化率を計算する。ここでは、変化率として、 ｜Ｒｏｒｇ−Ｒｌａｓｔ｜／Ｒｌａｓｔ を用いている。Ｒｏｒｇは変更前のリソース情報の値、Ｒｌａｓｔは変更後のリソース情報の値を表す。
【０２７１】
要約情報全体の変化率は、例えば、要約リンクの変化率の和として求めることができる。
【０２７２】
また、要約リンクの変化率は、例えば、各リンクリソース情報における変化率の和として求めることができる。
【０２７３】
要約情報計算のポリシーとして最良値を取る場合、要約リンク（ａ、ｃ）においては、遅延時間の変化率３３％、使用可能帯域の変化率０％であるので、要約リンク（ａ、ｃ）における変化率の合計は ３３＋０＝３３％ となる。
【０２７４】
同様に、要約リンク（ａ、ｄ）においては、遅延時間の変化率２０％、使用可能帯域の変化率０％であるので、要約リンク（ａ、ｄ）における変化率の合計は ２０＋０＝２０％ となる。
【０２７５】
よって、要約情報全体の変化率は、要約リンクの変化率を合計して、５３％になる。
【０２７６】
要約情報計算のポリシーとして最悪値を取る場合、要約リンク（ａ、ｃ）においては、遅延時間の変化率１３％、使用可能帯域の変化率５０％であるので、要約リンク（ａ、ｃ）における変化率の合計は １３＋５０＝６３％ となる。
【０２７７】
同様に、要約リンク（ａ、ｄ）においては、遅延時間の変化率０％、使用可能帯域の変化率５０％であるので、要約リンク（ａ、ｄ）における変化率の合計は ０＋５０＝５０％ となる。
【０２７８】
よって、要約情報全体の変化率は、要約リンクの変化率を合計して、１１３％になる。
【０２７９】
次に、本実施形態により得られる効果について説明する。
【０２８０】
本実施形態によれば、計算した要約情報が、前回他階層の境界通信装置に通知した要約情報と比較して、どれだけ変化したのかを測定し、大きな変化が発生したときのみ、要約情報を送信することを可能とする。このように、大きな変化が発生したときのみ要約情報が送信されるため、ネットワーク中に伝播される要約情報の量を削減することができる。
【０２８１】
【発明の効果】
以上のように、本発明によれば、次のような効果を得ることができる。
【０２８２】
第１の効果は、要求に適した経路を、予め記憶した複数の事前計算経路の中から選び出すことができるので、コネクション要求時に経路を再計算する手間が減り、高速なコネクション設定を行うことが可能になることである。
【０２８３】
その理由は、１つの目的地に対して複数の事前計算経路を計算し、その中から要求に適した候補経路を抽出しているからである。
【０２８４】
第２の効果は、事前計算経路を用いたコネクションのブロック率が低減されることである。
【０２８５】
その理由は、実行可能性チェック手段もしくは事前計算経路更新手段の作用により、最新のリンクリソース情報を事前計算経路に反映させることができるためである。
【０２８６】
第３の効果は、高速な要約情報計算が可能となり、境界通信装置における処理負荷を低減できることである。
【０２８７】
その理由は、事前計算経路を用いた要約情報計算を行うためである。
【０２８８】
第４の効果は、ネットワーク中に伝播する要約情報の量を低減し、他の境界通信装置における要約情報受信による一連の処理を省くことができることである。
【０２８９】
その理由は、要約情報の変化率に応じて、要約情報の計算もしくは送信を制御することができるからである。
【図面の簡単な説明】
【図１】本発明の第一の実施形態に係るリンクステートルーティング用境界通信装置の構成を示すブロック図である。
【図２】本発明の第一の実施形態に係るリンクステートルーティング用境界通信装置の動作を示すフローチャートである。
【図３】本発明の第一の実施形態に係るリンクステートルーティング用境界通信装置の実施例を示す概略図である。
【図４】本発明の第二の実施形態に係るリンクステートルーティング用境界通信装置の構成を示すブロック図である。
【図５】本発明の第二の実施形態に係るリンクステートルーティング用境界通信装置の動作を示すフローチャートである。
【図６】本発明の第二の実施形態に係るリンクステートルーティング用境界通信装置の実施例における事前計算経路リソース情報を表す表である。
【図７】本発明の第八の実施形態に係るリンクステートルーティング用境界通信装置の実施例における事前計算経路リソース情報を表す表である。
【図８】本発明の第九の実施形態に係るリンクステートルーティング用境界通信装置の構成を示すブロック図である。
【図９】本発明の第九の実施形態に係るリンクステートルーティング用境界通信装置の動作を示すフローチャートである。
【図１０】本発明の第十の実施形態に係るリンクステートルーティング用境界通信装置の構成を示すブロック図である。
【図１１】本発明の第十の実施形態に係るリンクステートルーティング用境界通信装置の動作を示すフローチャートである。
【図１２】本発明の第十一の実施形態に係るリンクステートルーティング用境界通信装置の構成を示すブロック図である。
【図１３】本発明の第十一の実施形態に係るリンクステートルーティング用境界通信装置の第一の実施例を示す概略図である。
【図１４】本発明の第十一の実施形態に係るリンクステートルーティング用境界通信装置の第二の実施例を示す概略図である。
【図１５】本発明の第十一の実施形態に係るリンクステートルーティング用境界通信装置の第三の実施例における事前計算経路リソース情報を表す表である。
【図１６】本発明の第十三の実施形態に係るリンクステートルーティング用境界通信装置の構成を示すブロック図である。
【図１７】本発明の第十三の実施形態に係るリンクステートルーティング用境界通信装置の動作を示すフローチャートである。
【図１８】本発明の第十三の実施形態に係るリンクステートルーティング用境界通信装置の実施例における事前計算経路リソース情報を表す表である。
【図１９】従来のリンクステートルーティング用通信装置の構成を示すブロック図である。
【図２０】図１９に示した従来のリンクステートルーティング用通信装置のコネクション要求受信時の動作を示すフローチャートである。
【図２１】図１９に示した従来のリンクステートルーティング用通信装置のリンクリソース情報受信時の動作を示すフローチャートである。
【図２２】従来のリンクステートルーティング用境界通信装置の構成を示すブロック図である。
【符号の説明】
１ リンクリソース情報受信手段
２１ リンクリソース情報更新手段
２２ 事前経路計算手段
２３１ 事前計算経路抽出手段
２３２ オンデマンド経路抽出手段
２３３ 実行可能性チェック手段
２４ 複数事前経路計算手段
２５ 経路抽出手段
２６ 事前計算経路リソース情報抽出手段
２７ ブロック率抽出手段
２８ リンク品質判定手段
３ 記憶装置
３１ リンクリソース情報記憶部
３２ 事前計算経路記憶部
３２１ 事前計算経路トポロジー記憶部
３２２ 事前計算経路リソース情報記憶部
３２３ リンク−経路対応表記憶部
３３ 事前計算経路記憶部
３４ ブロック率記憶部
３４１ ブロック率閾値記憶部
３４２ ブロック回数記憶部
３４３ コネクション試行回数記憶部
３５ リンク品質閾値記憶部
３６ 要約情報記憶部
３７ 変化率閾値記憶部
４ コネクション要求受信手段
５ コネクション設定手段
６ データ処理装置
６１ 要約情報計算手段
６２ 高速要約情報計算手段
６２１ 経路リソース情報による要約情報計算手段
６３ 変化率抽出手段
６４ 変化率比較手段
７ 記憶装置
８ 要約情報送信手段
９、１０、１２、１４、１６ データ処理装置
１１、１３、１５、１７ 記憶装置
５０１、５０２、５０３、５０４、５０５ リンクステートルーティング用通信装置
５１１ リンクリソース情報
５２１、５２２、５２３、５２４ 事前計算経路
５３１ 事前計算経路情報
５４１ リンク（ａ、ｃ）を含む事前計算経路情報
５４２ リンク（ａ、ｃ）を含む事前計算経路情報
５５１ リンク（ａ、ｃ）のリソース情報の変化
５６１ ある目的地に対する事前計算経路のうちコネクション品質要求を満たすもの
５８１ リンク（ａ、ｅ）のリソース情報の変化
５８２ 事前計算経路のリソース情報の変化
５８３ 要約リンクのリソース情報の変化
５９１ 要約リンク情報
６０１、６０２、６０３、６０４ 階層化ネットワークにおける各階層
７０２ 階層６０２の要約リンク表現
７０２１、７０２２、７０２３ 階層６０２の境界通信装置
Claims (9)
- 他の通信装置から送られたリンクリソース情報を受信するリンクリソース情報受信手段と、
リンクリソース情報を記憶するリンクリソース情報記憶部と、
前記リンクリソース情報を更新するリンクリソース情報更新手段と、
コネクション要求発生前に、一つの目的地に対して候補となる複数の経路を計算する複数事前経路計算手段と、
前記複数事前経路計算手段によって計算された事前計算経路情報を記憶する事前計算経路記憶部と、
前記事前計算経路記憶部から候補経路を抽出する事前計算経路抽出手段と、
各リンクがどの事前計算経路に含まれているかを記憶したリンク−経路対応表を記憶するリンク−経路対応表記憶部と、
前記リンクリソース情報更新手段から供給された更新リンクの情報をキーにして、該更新リンクと対応する事前計算経路を前記リンク−経路対応表の中から検索し、前記事前計算経路記憶部に記憶された事前計算経路情報のうち、前記更新リンクと対応する情報を更新する事前計算経路リソース情報抽出手段と、
を備えたことを特徴とするリンクステートルーティング用通信装置。 - 前記複数事前経路計算手段は、リンクリソース情報に依存せず、リンク固定のパラメータに基づいて、複数事前経路の計算を行うものであることを特徴とする請求項１に記載のリンクステートルーティング用通信装置。
- 前記複数事前経路計算手段は、複数のパラメータを統合した統合化パラメータに基づいて、複数事前経路の計算を行うものであることを特徴とする請求項１に記載のリンクステートルーティング用通信装置。
- 前記事前計算経路抽出手段は、統合化パラメータに基づいて事前計算経路を整列させ、整列した事前計算経路を先頭から順番に探索し、候補となる事前計算経路を抽出するものであることを特徴とする請求項１に記載のリンクステートルーティング用通信装置。
- 前記事前計算経路抽出手段は、統合化パラメータを重みとする重みつきラウンドロビンによって、候補となる事前計算経路を抽出するものであることを特徴とする請求項４に記載のリンクステートルーティング用通信装置。
- 前記事前計算経路抽出手段は、階層化重みつきラウンドロビンによって、候補となる事前計算経路を抽出するものであることを特徴とする請求項１に記載のリンクステートルーティング用通信装置。
- 前記リンクリソース情報記憶部に記憶されているリンクリソース情報に基づいて、コネクション品質要求を満たす経路を計算するオンデマンド経路抽出手段をさらに備えていることを特徴とする請求項１乃至６のいずれか一項に記載のリンクステートルーティング用通信装置。
- 他の通信装置からリンクリソース情報を受信する第一の過程と、
前記第一の過程において受信したリンクリソース情報と、予め記憶されているリンクリソース情報とを比較し、リソース情報に変更のあったリンクを抽出する第二の過程と、
事前に計算された経路のうち、変更のあったリンクを含む経路を抽出する第三の過程と、
前記第三の過程において抽出された経路の経路リソース情報を抽出し、その内容を更新する第四の過程と、
を備えるリンクステートルーティング用通信方法。 - 事前に計算された全ての経路の経路リソース情報を更新するまで、前記第四の過程を繰り返す第五の過程をさらに備えることを特徴とする請求項８に記載のリンクステートルーティング用通信方法。
Priority Applications (5)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2000083558A JP3575381B2 (ja) | 2000-03-24 | 2000-03-24 | リンクステートルーティング用通信装置及びリンクステートルーティング用通信方法 |
| CA002342097A CA2342097A1 (en) | 2000-03-24 | 2001-03-23 | Link state routing techniques |
| US09/814,854 US7047316B2 (en) | 2000-03-24 | 2001-03-23 | Link state routing techniques |
| EP20010107411 EP1137228A3 (en) | 2000-03-24 | 2001-03-26 | Link state routing techniques |
| US11/300,414 US7765321B2 (en) | 2000-03-24 | 2005-12-15 | Link state routing techniques |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2000083558A JP3575381B2 (ja) | 2000-03-24 | 2000-03-24 | リンクステートルーティング用通信装置及びリンクステートルーティング用通信方法 |
Related Child Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2004151496A Division JP2004266863A (ja) | 2004-05-21 | 2004-05-21 | リンクステートルーティング用通信装置及びリンクステートルーティング用通信方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2001274826A JP2001274826A (ja) | 2001-10-05 |
| JP3575381B2 true JP3575381B2 (ja) | 2004-10-13 |
Family
ID=18600175
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2000083558A Expired - Fee Related JP3575381B2 (ja) | 2000-03-24 | 2000-03-24 | リンクステートルーティング用通信装置及びリンクステートルーティング用通信方法 |
Country Status (4)
| Country | Link |
|---|---|
| US (2) | US7047316B2 (ja) |
| EP (1) | EP1137228A3 (ja) |
| JP (1) | JP3575381B2 (ja) |
| CA (1) | CA2342097A1 (ja) |
Families Citing this family (66)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB2386032B (en) * | 2002-03-01 | 2005-08-24 | Parc Technologies Ltd | Method of estimating traffic data |
| US7764617B2 (en) * | 2002-04-29 | 2010-07-27 | Harris Corporation | Mobile ad-hoc network and methods for performing functions therein based upon weighted quality of service metrics |
| US7471680B1 (en) * | 2002-06-24 | 2008-12-30 | Cisco Technology, Inc. | Method to enhance routing control in PNNI networks |
| US7263069B2 (en) * | 2002-07-03 | 2007-08-28 | Verizon Business Global Llc | Arrangement for evaluating network capacity, network utilization, and network efficiency in a communications network |
| CN1685742A (zh) * | 2002-07-26 | 2005-10-19 | 西门子公司 | 在通信系统中提供网络单元 |
| US7894354B2 (en) * | 2002-10-04 | 2011-02-22 | Jds Uniphase Corporation | System and method to monitor RTP streams using RTCP SR/RR packet information |
| CN100459534C (zh) | 2002-10-07 | 2009-02-04 | 日本电信电话株式会社 | 分层网络节点及通过该节点构成的网络、节点和分层网络 |
| US7652998B2 (en) * | 2002-12-11 | 2010-01-26 | Nippon Telegraph And Telephone Corporation | Multicast communication path calculation method and multicast communication path calculation apparatus |
| US7382731B1 (en) * | 2003-03-05 | 2008-06-03 | Cisco Technology, Inc. | Method and apparatus for updating probabilistic network routing information |
| WO2004084562A2 (en) * | 2003-03-13 | 2004-09-30 | Interdigital Technology Corporation | Wireless communication method and system for assigning multi-paths to rake receiver fingers |
| US7921447B1 (en) * | 2003-03-14 | 2011-04-05 | Thomson Licensing | Enhanced television metadata processor for efficient broadcast operations |
| US7403939B1 (en) * | 2003-05-30 | 2008-07-22 | Aol Llc | Resolving queries based on automatic determination of requestor geographic location |
| US20050008014A1 (en) * | 2003-07-07 | 2005-01-13 | Debasis Mitra | Techniques for network traffic engineering |
| US7336617B1 (en) * | 2003-08-01 | 2008-02-26 | Verizon Laboratories Inc. | Bit-field-encoded resource record for determining a transmission path in a communications network |
| US8018953B1 (en) | 2003-08-20 | 2011-09-13 | Cisco Technology, Inc. | Adaptive, deterministic ant routing approach for updating network routing information |
| AU2003304680A1 (en) * | 2003-11-24 | 2005-06-08 | Zte Corporation | A method device and system of realizing qos (quality of service) guarantee in mpls network |
| WO2005067227A1 (ja) * | 2004-01-09 | 2005-07-21 | Nec Corporation | 負荷分散方法、ノード及び制御プログラム |
| US7804789B2 (en) * | 2004-03-18 | 2010-09-28 | Tekelec | Methods, systems, and computer program products for organizing, managing, and selectively distributing routing information in a signaling message routing node |
| US7583593B2 (en) * | 2004-12-01 | 2009-09-01 | Cisco Technology, Inc. | System and methods for detecting network failure |
| JP4726498B2 (ja) * | 2005-01-14 | 2011-07-20 | 富士通株式会社 | 情報処理方法及びルータ |
| US7990888B2 (en) * | 2005-03-04 | 2011-08-02 | Cisco Technology, Inc. | System and methods for network reachability detection |
| US20060215577A1 (en) * | 2005-03-22 | 2006-09-28 | Guichard James N | System and methods for identifying network path performance |
| JP2007013684A (ja) * | 2005-06-30 | 2007-01-18 | Toshiba Corp | 通信システム、サーバ装置及びデータ端末装置 |
| JP4550705B2 (ja) * | 2005-09-22 | 2010-09-22 | 株式会社東芝 | サーバ装置 |
| US7983174B1 (en) | 2005-12-19 | 2011-07-19 | Cisco Technology, Inc. | Method and apparatus for diagnosing a fault in a network path |
| US7912934B1 (en) | 2006-01-09 | 2011-03-22 | Cisco Technology, Inc. | Methods and apparatus for scheduling network probes |
| US8218445B2 (en) * | 2006-06-02 | 2012-07-10 | Ciena Corporation | Smart ethernet edge networking system |
| CN101841883B (zh) * | 2006-05-10 | 2011-11-09 | 华为技术有限公司 | 控制网状网络节点发射功率的方法及装置 |
| CN101043236B (zh) * | 2006-05-10 | 2010-05-12 | 华为技术有限公司 | 控制网状网络节点发射功率的方法及网状网络节点 |
| US7826349B2 (en) * | 2006-05-30 | 2010-11-02 | Intel Corporation | Connection management mechanism |
| US8223655B2 (en) * | 2006-08-22 | 2012-07-17 | Embarq Holdings Company, Llc | System and method for provisioning resources of a packet network based on collected network performance information |
| US20100011244A1 (en) * | 2006-08-30 | 2010-01-14 | France Telecom | Method of routing data in a network comprising nodes organized into clusters |
| US20080256270A1 (en) * | 2007-03-02 | 2008-10-16 | Hubbs Robert A | Quality of service based preemptive routing |
| US9392504B2 (en) * | 2007-06-19 | 2016-07-12 | Qualcomm Incorporated | Delivery of handover command |
| US7827306B2 (en) * | 2007-06-28 | 2010-11-02 | Verizon Patent And Licensing Inc. | Methods and computer program products for route determination |
| US8111627B2 (en) * | 2007-06-29 | 2012-02-07 | Cisco Technology, Inc. | Discovering configured tunnels between nodes on a path in a data communications network |
| US9043451B2 (en) | 2007-07-31 | 2015-05-26 | Tekelec, Inc. | Methods, systems, and computer readable media for managing the flow of signaling traffic entering a signaling system 7 (SS7) based network |
| JP4840334B2 (ja) * | 2007-11-14 | 2011-12-21 | ブラザー工業株式会社 | 端末装置、通信システム、プログラム及び方法 |
| DE602007012565D1 (de) * | 2007-12-14 | 2011-03-31 | Sony Corp | Strahlensteueralgorithmus für NLOS-Drahtlossysteme mit vordefinierten Parametern |
| US8411584B1 (en) * | 2008-03-31 | 2013-04-02 | Olympus Corporation | Wireless resource allocation system and method |
| US8355344B1 (en) * | 2008-07-23 | 2013-01-15 | Sprint Communications Company L.P. | Storage area network edge-core interswitch link optimization |
| CN101646229B (zh) * | 2008-08-04 | 2012-02-29 | 中兴通讯股份有限公司 | 传输功率控制命令获取方法及获取预处理方法、移动终端 |
| JP4649516B2 (ja) * | 2009-01-30 | 2011-03-09 | 株式会社東芝 | 電話交換装置及びこの電話交換装置で使用されるホスト名情報割り当て方法 |
| US8346079B2 (en) * | 2009-02-27 | 2013-01-01 | Futurewei Technologies, Inc. | Path computation element protocol (PCEP) operations to support wavelength switched optical network routing, wavelength assignment, and impairment validation |
| US8374502B2 (en) | 2009-02-27 | 2013-02-12 | Futurewei Technologies, Inc. | Open shortest path first extensions in support of wavelength switched optical networks |
| EP2425584B1 (en) * | 2009-04-30 | 2013-02-13 | Telefonaktiebolaget LM Ericsson (publ) | Core network node selection in a mobile communication network |
| CN101583161B (zh) * | 2009-05-26 | 2013-02-13 | 北京邮电大学 | 协作节点单元选择方法及装置 |
| US8315519B2 (en) * | 2009-06-03 | 2012-11-20 | Nec Laboratories America, Inc. | Systems and methods for transmitting signals in communication networks |
| CN101645847A (zh) * | 2009-08-25 | 2010-02-10 | 中兴通讯股份有限公司 | 一种在传送网络中提高业务恢复速度的方法及系统 |
| US8537677B2 (en) * | 2009-10-13 | 2013-09-17 | Hewlett-Packard Development Company, L.P. | Incremental adaptive packet routing in a multi-dimensional network |
| WO2011071127A1 (ja) * | 2009-12-11 | 2011-06-16 | 日本電気株式会社 | 利用可能帯域計測方法、利用可能帯域計測システム、端末装置及びコンピュータ読み取り可能な記録媒体 |
| IN2012CN07525A (ja) | 2010-02-12 | 2015-05-29 | Tekelec Inc | |
| US8516152B2 (en) * | 2010-11-12 | 2013-08-20 | Alcatel Lucent | Lookahead computation of routing information |
| JP5716587B2 (ja) * | 2011-07-19 | 2015-05-13 | 富士通株式会社 | 経路決定装置，経路決定方法，管理プログラム及び管理装置 |
| US8805382B2 (en) * | 2012-07-23 | 2014-08-12 | At&T Intellectual Property I, L.P. | System and method for quality of service in a wireless network environment |
| US9306840B2 (en) | 2012-09-26 | 2016-04-05 | Alcatel Lucent | Securing software defined networks via flow deflection |
| JP5929682B2 (ja) * | 2012-10-09 | 2016-06-08 | 富士通株式会社 | ネットワーク設計装置、ネットワーク設計方法、ネットワーク設計プログラム |
| US9906439B2 (en) * | 2013-11-01 | 2018-02-27 | Futurewei Technologies, Inc. | Ad-hoc on-demand routing through central control |
| CN104811392B (zh) * | 2014-01-26 | 2018-04-17 | 国际商业机器公司 | 用于处理网络中的资源访问请求的方法和系统 |
| WO2015120912A1 (en) * | 2014-02-17 | 2015-08-20 | Telefonaktiebolaget L M Ericsson (Publ) | A method and apparatus for allocating physical resources to a summarized resource |
| US9436391B1 (en) * | 2014-03-28 | 2016-09-06 | Formation Data Systems, Inc. | Efficient scalable I/O scheduling |
| JP6148641B2 (ja) * | 2014-05-30 | 2017-06-14 | 日本電信電話株式会社 | 端末収容ルーティング装置、端末収容ルーティング装置の動作方法および通信システム |
| WO2020067403A1 (ja) * | 2018-09-28 | 2020-04-02 | 日本電気株式会社 | 通信装置、通信方法及びプログラム |
| US11546413B2 (en) * | 2019-12-31 | 2023-01-03 | Oracle International Corporation | System and method for identifying capabilities and limitations of an orchestration based application integration |
| US11570084B2 (en) * | 2021-05-30 | 2023-01-31 | Fujitsu Limited | Path routing with delay constraints |
| CN118170326B (zh) * | 2024-05-13 | 2024-08-09 | 中移(苏州)软件技术有限公司 | 存储路由确定方法、装置、电子设备、存储介质及产品 |
Family Cites Families (15)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH05130144A (ja) | 1991-10-31 | 1993-05-25 | Fujitsu Ltd | 動的ルーテイング方式 |
| JP3132996B2 (ja) | 1995-03-02 | 2001-02-05 | 三菱電機株式会社 | ネットワークの経路設定方法及びネットワークの経路設定装置 |
| JP2723084B2 (ja) | 1995-07-19 | 1998-03-09 | 日本電気株式会社 | リンクステートルーティング装置 |
| JP2723097B2 (ja) * | 1995-12-04 | 1998-03-09 | 日本電気株式会社 | Ｑｏｓルーティング装置 |
| US5845091A (en) * | 1996-02-15 | 1998-12-01 | Bay Networks, Inc. | Forwarding of internetwork packets to a destination network via a selected one of a plurality of paths |
| JP2964957B2 (ja) | 1996-08-15 | 1999-10-18 | 日本電気株式会社 | 高速ルーティング制御方式 |
| JP2993444B2 (ja) | 1996-10-25 | 1999-12-20 | 日本電気株式会社 | Ａｔｍ網におけるコネクション設定および復旧方式 |
| JPH10154979A (ja) | 1996-11-21 | 1998-06-09 | Nippon Telegr & Teleph Corp <Ntt> | ポイントツーマルチポイント接続方法および広帯域通信装置 |
| JPH10164074A (ja) | 1996-11-27 | 1998-06-19 | Toshiba Corp | Ａｔｍスイッチおよびａｔｍネットワークシステム |
| JP3063721B2 (ja) * | 1997-04-30 | 2000-07-12 | 日本電気株式会社 | トポロジー情報交換装置及びプログラムを記録した機械読み取り可能な記録媒体 |
| JP3665460B2 (ja) * | 1997-12-05 | 2005-06-29 | 富士通株式会社 | 分散自律協調型の応答時間チューニングによる経路選択システム、方法、及び記録媒体 |
| JP3120770B2 (ja) | 1998-03-04 | 2000-12-25 | 日本電気株式会社 | コネクション経路変更装置とその変更方法及びノードとコネクション経路変更システム |
| US6633544B1 (en) * | 1998-06-24 | 2003-10-14 | At&T Corp. | Efficient precomputation of quality-of-service routes |
| US6687229B1 (en) * | 1998-11-06 | 2004-02-03 | Lucent Technologies Inc | Quality of service based path selection for connection-oriented networks |
| JP2000174755A (ja) | 1998-12-02 | 2000-06-23 | Fujitsu Ltd | 経路選択方式 |
-
2000
- 2000-03-24 JP JP2000083558A patent/JP3575381B2/ja not_active Expired - Fee Related
-
2001
- 2001-03-23 CA CA002342097A patent/CA2342097A1/en not_active Abandoned
- 2001-03-23 US US09/814,854 patent/US7047316B2/en not_active Expired - Fee Related
- 2001-03-26 EP EP20010107411 patent/EP1137228A3/en not_active Withdrawn
-
2005
- 2005-12-15 US US11/300,414 patent/US7765321B2/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| CA2342097A1 (en) | 2001-09-24 |
| US7765321B2 (en) | 2010-07-27 |
| US20060155873A1 (en) | 2006-07-13 |
| EP1137228A2 (en) | 2001-09-26 |
| US7047316B2 (en) | 2006-05-16 |
| EP1137228A3 (en) | 2004-10-27 |
| JP2001274826A (ja) | 2001-10-05 |
| US20010029543A1 (en) | 2001-10-11 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3575381B2 (ja) | リンクステートルーティング用通信装置及びリンクステートルーティング用通信方法 | |
| Bahk et al. | Dynamic multi-path routing and how it compares with other dynamic routing algorithms for high speed wide area network | |
| US6804199B1 (en) | Communications network system and method for routing based on disjoint pairs of paths | |
| EP1510044B1 (en) | Dynamic routing in packet-switching multi-layer communications networks | |
| US7187652B2 (en) | Multi-constraint routing system and method | |
| US6377551B1 (en) | QoS based route determination method for communications networks | |
| US7406032B2 (en) | Bandwidth management for MPLS fast rerouting | |
| EP2058986B2 (en) | A method for determining a routing path and a routing path determination unit | |
| US6163525A (en) | Network restoration | |
| JP2648579B2 (ja) | 最適経路を決定するための方法及びネットワーク・ノード | |
| JPH1070571A (ja) | 最適パス決定方法 | |
| US20020097680A1 (en) | Apparatus and method for spare capacity allocation | |
| JPH0983546A (ja) | 経路選択方法および経路選択装置および通信網設計方法および通信網設計装置 | |
| JP2004266863A (ja) | リンクステートルーティング用通信装置及びリンクステートルーティング用通信方法 | |
| Alabbad et al. | Localised credit based QoS routing | |
| Beaubrun et al. | A routing algorithm for distributed communication networks | |
| Felstaine et al. | Crankback prediction in hierarchical ATM networks | |
| Bahk et al. | Congestion control based dynamic routing in ATM networks | |
| Attar | A Distributed Adaptive Multi-Path Routing-Consistent and Conflicting Decision Making. | |
| Bahk et al. | Preventive congestion control based routing in ATM networks | |
| Yuen et al. | Efficient path selection for QoS routing in load balancing | |
| Garcia et al. | Optimal lsp placement with qos constraints in diffserv/mpls networks | |
| Bahk et al. | A dynamic multi-path routing algorithm for ATM networks | |
| Pathak | Distributed Quality-of-Service Routing of Best Constrained Shortest Paths. | |
| Tham et al. | A QoS-based routing algorithm for PNNI ATM networks |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20040322 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20040521 |
|
| A911 | Transfer to examiner for re-examination before appeal (zenchi) |
Free format text: JAPANESE INTERMEDIATE CODE: A911 Effective date: 20040528 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20040615 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20040628 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20070716 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080716 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090716 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100716 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110716 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110716 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120716 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120716 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130716 Year of fee payment: 9 |
|
| LAPS | Cancellation because of no payment of annual fees |