故障復旧システム、ノード、故障復旧方法およびプログラム
【課題】パケット交換網における多重故障復旧時に、転送ループの発生する確率を低下させる、故障復旧システム、ノード、故障復旧方法およびプログラムを提供する。
【解決手段】故障復旧システムの各ノード1は、1番目の故障リンクをプロテクトするために選ばれた予備トポロジに基づき、2番目の故障リンク検出時に備え、2番目に検出した故障リンクをプロテクトしつつ、1番目の故障リンクもプロテクトできるような予備トポロジを、類似性判定法または故障箇所推定法により求め、FIB-ID探索テーブル300を作成しておく。そして、ノード1は、2番目の故障リンクを検出した場合に、FIB-ID探索テーブル300を参照して、2番目の故障リンクをプロテクトしつつ、1番目の故障リンクも回避する予備トポロジを抽出して、パケットを転送する。
【解決手段】故障復旧システムの各ノード1は、1番目の故障リンクをプロテクトするために選ばれた予備トポロジに基づき、2番目の故障リンク検出時に備え、2番目に検出した故障リンクをプロテクトしつつ、1番目の故障リンクもプロテクトできるような予備トポロジを、類似性判定法または故障箇所推定法により求め、FIB-ID探索テーブル300を作成しておく。そして、ノード1は、2番目の故障リンクを検出した場合に、FIB-ID探索テーブル300を参照して、2番目の故障リンクをプロテクトしつつ、1番目の故障リンクも回避する予備トポロジを抽出して、パケットを転送する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、IP(Internet Protocol)ネットワーク等のパケット交換網における、故障復旧時の転送経路再設定技術に関する。
【背景技術】
【0002】
ネットワークにおいては、予期しない故障の発生に対して迅速に転送経路を切り替えることで故障復旧を行い、転送品質の維持を行うことが重要である。IPネットワークにおける故障復旧方式として、OSPF(Open Shortest Path First)等のルーチングプロトコルを用いた動的な復旧方式がある(非特許文献1参照)。
【0003】
OSPFでは、故障を検知したノードは、全ノードに故障情報を通知(フラッディング)する。故障情報を受け取ったノードは、新規に作成される故障箇所を除いた網トポロジ情報をもとに迂回経路を計算することで、自動的に転送経路を切り替えることが可能となる。しかし、OSPFでは故障発生後に迂回経路を計算するため、故障の復旧に秒単位の時間を必要とする問題がある。また、故障情報の通知や迂回経路の計算は、IPネットワークの規模に依存して増加する。
【0004】
このような問題を解決する方法として、事前に迂回経路を計算しておくことで高速な故障復旧を実現するIP−FRR(IP Fast Reroute)方式が提案されている(非特許文献2参照)。IP−FRR方式は、事前に予備トポロジを作成し、故障発生時には該当故障箇所をプロテクトする(迂回する)予備トポロジに従った転送経路に切り替えることで故障復旧を行う。
【0005】
IP−FRR方式における予備トポロジを用いた故障復旧方法の具体例を、図1を参照して説明する。図1(a)は、通常のトポロジの一例を示し、図1(b)は、予備トポロジの一例を示す。
【0006】
まず、各ノードは、リンク断絶(故障)に備えた予備トポロジを予め作成しておく。例えば、リンク1−2(ノード番号「1」のノードと、ノード番号「2」のノードとの間のリンク)が断絶した場合に備え、このリンク1−2をプロテクトする予備トポロジを事前に作成する。ここで、予備トポロジにおけるプロテクトリンクのリンクコストは、このプロテクトリングが経路として選択されないようにするため、設定可能な最大値を付与する。これにより、予備トポロジ上でリンクコストの総和が最小となる最小コストルーティングにより経路を計算すると、プロテクトリンクを使用しない経路が算出される。この予備トポロジは全てのノードに記憶され、各ノードは予備トポロジに従った経路を事前に(トラヒック転送前に)計算しておく。
【0007】
ここで、ノード番号「1」のノードをsrc(source:送信元)とし、ノード番号「5」のノードをdst(destination:宛先)とする経路上において、リンク1−2の故障を検出した場合を考える。例えば、図1(a)に示す通常のトポロジ上で、(1)リンク1−2の故障を検出すると、故障検出ノード(ノード番号「1」のノード)は、故障リンクをプロテクトする予備トポロジAに従ってパケットをノード番号「4」のノードに転送する(図1(b)参照)。このとき、故障検出ノード(ノード番号「1」のノード)は、リンク1−2が故障ノードしたことを知っているので、予備トポロジAを使用すれば故障箇所を迂回できることを知っている。
【0008】
しかし、他のノード(例えば、ノード番号「4」のノード)は、故障箇所を把握できていない。そこで、故障検出ノード(ノード番号「1」のノード)は、(2)使用する予備トポロジAを選択し、この予備トポロジAのID(Identification)をノード番号「4」のノードに転送するパケットのヘッダに記述しておく。そして、迂回経路上に存在する他のノード(ここでは、ノード番号「4」のノード)はパケットを受信すると、(3)このパケットのヘッダを参照し、使用すべき予備トポロジAを選択し、その選択した予備トポロジAに従って、パケットをノード番号「5」のノードに転送する。このように、故障検出ノードは、使用する予備トポロジのIDをパケットに付与することで、データ転送と同時に故障箇所を間接的に伝搬する。
【0009】
図2は、任意の単一リンクの故障をプロテクトする予備トポロジの設計例を示す。図2(a)は、通常のトポロジであり、図2(b)〜(d)は、図2(a)の通常のトポロジの予備トポロジを示す。予備トポロジは、全体の予備トポロジの数を削減するため、単一のトポロジで複数のリンクをプロテクトするように設計される。
【0010】
また、これまでに、予備トポロジ数を最小化したり(非特許文献3参照)、迂回後の負荷を平滑化したり(非特許文献4参照)する予備トポロジ設計アルゴリズムが提案されている。
【先行技術文献】
【非特許文献】
【0011】
【非特許文献1】“OSPF Version 2”,[online], April 1998, IETF RFC2328, [平成23年8月31日検索],インターネット<URL:http://www.ietf.org/rfc/rfc2328.txt>
【非特許文献2】A.Kvalbein, A.F.Hansen, et al.,“Fast IP Network Recovery using Multiple Routing Configurations,” in Proceedings of INFOCOM, Apr.2006.
【非特許文献3】S.Kamamura, T.Miyamura, et al.,“Scalable Backup Configurations Creation for IP Fast Reroute,”IEICE Trans. Commun Vol.E94-B No.1 pp.109-117, 2011.1.
【非特許文献4】R.Takahashi, S.Tembo, et al.,“Dispersing Hotspot Traffic in Backup Topology for IP Fast Reroute,”submitted to IEEE ICC, 2011.6.
【発明の概要】
【発明が解決しようとする課題】
【0012】
しかしながら、既存の方式は、単一のリンクやノードの故障に対しては安定的に動作するが、多重故障の発生によって転送ループが発生する問題がある。なお、パケット交換網上の転送ループは、該当パケットがロスするだけでなく、ループするパケットによる帯域消費が、他のパケット通信に悪影響を与える可能性があるため、極力避ける必要がある。
【0013】
転送ループ発生の具体例を、図3を参照して説明する。ノード「i」からノード「dst」に向けてパケットを転送する際に、図3(a)に示すリンク故障x,yが発生する場合を考える。故障xを検出したノード「i」は、予備トポロジ#2を選択し、予備トポロジ#2に従った予備経路「1」−「2」−「3」−「8」−「7」−「6」に沿った転送を試みる(図3(b)参照)。一方で、予備経路上には2つ目の故障である故障yが存在するため、故障yを検出したノード「j」は、故障yをプロテクトする予備トポロジ#1を選択する(図3(c)参照)。ここで、予備トポロジ#1に従った予備経路「2」−「1」−「6」は、再度リンク故障xを含む経路となる。結果として、この例ではノード「i」とノード「j」との間で、転送ループが発生する。
【0014】
この問題は、既存技術では、故障検出ノード以外のノードには、予備トポロジのIDのみが伝搬されるため、故障箇所の特定ができないことに起因する。例えば、二重故障の場合、2番目の故障を検出したノードは、2番目の故障を回避する予備トポロジを選択することは可能であるが、1番目の故障の故障箇所が既知ではないため、再度1番目の故障を含む予備トポロジを選択する可能性があり、このような場合には、転送ループが発生する。
【0015】
このような背景に鑑みて本発明がなされたのであり、本発明は、パケット交換網における多重故障復旧時に、転送ループの発生する確率を低下させることができる、故障復旧システム、ノード、故障復旧方法およびプログラムを提供することを課題とする。
【課題を解決するための手段】
【0016】
前記した課題を解決するため、請求項1に記載の発明は、複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムであって、前記故障復旧システムの各ノードが、パケットを送受信する通信部と、前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部と、前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すdst-IDと、出力ポートとを対応付けた経路テーブル(FIB)を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル(FIB)の識別子であるFIB-IDに対応付けて作成する経路テーブル(FIB)作成部と、1番目の前記故障リンクをプロテクトする前記予備トポロジを示す第1の予備トポロジの現FIB−IDと、前記パケットの送信元アドレスを示すsrc-IDと、前記dst-IDとを、2番目の前記故障リンクをプロテクトする前記予備トポロジを示す第2の予備トポロジの前記FIB-IDであり、前記第1の予備トポロジに基づき選択された次FIB-IDに対応付けたFIB-ID探索テーブルを作成するFIB-ID探索テーブル作成部と、前記FIB-ID、前記src-IDおよび前記dst-IDが付された前記パケットを、前記通信部を介して受信し、前記FIB-IDをキーとして、前記経路テーブル(FIB)を探索し、前記出力ポートを取得するテーブル探索部と、前記出力ポートが起動しているか否かを判定し、前記起動していると判定した場合には、当該出力ポートから前記パケットを送信し、前記起動してないと判定した場合には、前記パケットをFIB-ID更新部に引き渡す出力ポート確認部と、前記パケットに付された前記FIB-ID、前記src-IDおよび前記dst-IDに基づき、前記パケットに付された前記FIB-IDを前記現FIB-IDとして、前記FIB-ID探索テーブルを探索し、前記次FIB-IDを取得し、当該次FIB-IDを付した前記パケットを、前記テーブル探索部に引き渡す前記FIB-ID更新部と、を備え、前記テーブル探索部が、前記次FIB-IDが付されたパケットを受信すると、前記次FIB-IDをキーとして前記経路テーブル(FIB)を探索し、前記出力ポートを取得して、前記出力ポート確認部に引き渡すことを特徴とする故障復旧システムとした。
【0017】
また、請求項4に記載の発明は、複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムの前記ノードであって、パケットを送受信する通信部と、前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部と、前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すdst-IDと、出力ポートとを対応付けた経路テーブル(FIB)を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル(FIB)の識別子であるFIB-IDに対応付けて作成する経路テーブル(FIB)作成部と、1番目の前記故障リンクをプロテクトする前記予備トポロジを示す第1の予備トポロジの現FIB−IDと、前記パケットの送信元アドレスを示すsrc-IDと、前記dst-IDとを、2番目の前記故障リンクをプロテクトする前記予備トポロジを示す第2の予備トポロジの前記FIB-IDであり、前記第1の予備トポロジに基づき選択された次FIB-IDに対応付けたFIB-ID探索テーブルを作成するFIB-ID探索テーブル作成部と、前記FIB-ID、前記src-IDおよび前記dst-IDが付された前記パケットを、前記通信部を介して受信し、前記FIB-IDをキーとして、前記経路テーブル(FIB)を探索し、前記出力ポートを取得するテーブル探索部と、前記出力ポートが起動しているか否かを判定し、前記起動していると判定した場合には、当該出力ポートから前記パケットを送信し、前記起動してないと判定した場合には、前記パケットをFIB-ID更新部に引き渡す出力ポート確認部と、前記パケットに付された前記FIB-ID、前記src-IDおよび前記dst-IDに基づき、前記パケットに付された前記FIB-IDを前記現FIB-IDとして、前記FIB-ID探索テーブルを探索し、前記次FIB-IDを取得し、当該次FIB-IDを付した前記パケットを、前記テーブル探索部に引き渡す前記FIB-ID更新部と、を備え、前記テーブル探索部が、前記次FIB-IDが付されたパケットを受信すると、前記次FIB-IDをキーとして前記経路テーブル(FIB)を探索し、前記出力ポートを取得して、前記出力ポート確認部に引き渡すことを特徴とするノードとした。
【0018】
また、請求項5に記載の発明は、 複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムの故障復旧方法であって、前記故障復旧システムのノードが、前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部を備えており、前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すdst-IDと、出力ポートとを対応付けた経路テーブル(FIB)を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル(FIB)の識別子であるFIB-IDに対応付けて作成するステップと、1番目の前記故障リンクをプロテクトする前記予備トポロジを示す第1の予備トポロジの現FIB−IDと、前記パケットの送信元アドレスを示すsrc-IDと、前記dst-IDとを、2番目の前記故障リンクをプロテクトする前記予備トポロジを示す第2の予備トポロジの前記FIB-IDであり、前記第1の予備トポロジに基づき選択された次FIB-IDに対応付けたFIB-ID探索テーブルを作成するステップと、前記FIB-ID、前記src-IDおよび前記dst-IDが付された前記パケットを受信し、前記FIB-IDをキーとして、前記経路テーブル(FIB)を探索し、前記出力ポートを取得するステップと、前記出力ポートが起動しているか否かを判定し、前記出力ポートが起動していると判定した場合に、当該出力ポートから前記パケットを送信するステップと、前記出力ポートが起動してないと判定した場合に、前記パケットに付された前記FIB-ID、前記src-IDおよび前記dst-IDに基づき、前記パケットに付された前記FIB-IDを前記現FIB-IDとして、前記FIB-ID探索テーブルを探索し、前記次FIB-IDを取得するステップと、前記次FIB-IDを付した前記パケットを受信し、当該次FIB-IDをキーとして前記経路テーブル(FIB)を探索し、前記出力ポートを取得して、当該取得した出力ポートが起動しているか否かを判定して、前記パケットの送信するステップ、または、前記次FIB-IDを取得するステップを実行することを特徴とする故障復旧方法とした。
【0019】
このようにすることで、2番目のリンク故障が発生した場合であっても、1番目のリンク故障をプロテクトするために選択された第1の予備トポロジに基づき、2番目のリンク故障をプロテクトしつつ、1番目の故障リンクを回避するように第2の予備トポロジを選択し、パケットを転送することができる。これにより、転送ループの発生する確率を低下させることができる。
【0020】
請求項2に記載の発明は、前記FIB-ID探索テーブル作成部が、前記FIB-ID探索テーブルの作成の際に行う、前記第1の予備トポロジに基づく前記次FIB-IDの選択において、前記2番目の故障リンクをプロテクトする前記予備トポロジとして抽出される1つ以上の前記第2の予備トポロジについて、全プロテクトリンク数に対し、前記第1の予備トポロジがプロテクトしているリンクと同一のリンクをプロテクトしている数の割合を示す類似性を計算し、前記第2の予備トポロジのうち、前記類似性の最も高い前記第2の予備トポロジを抽出し、そのFIB-IDを次FIB-IDとして選択することを特徴とする請求項1に記載の故障復旧システムとした。
【0021】
このようにすることで、FIB-ID探索テーブル作成部は、第1の予備トポロジと第2の予備トポロジの類似性を計算し、最も類似性の高い第2の予備トポロジを抽出して、そのFIB-IDを次FIB-IDとし、FIB-ID探索テーブルを作成することができる。これにより、1番目の故障リンクを回避するような第2の予備トポロジが選択され、転送ループの発生する確率を低下させることができる。
【0022】
請求項3に記載の発明は、前記FIB-ID探索テーブル作成部は、前記FIB-ID探索テーブルの作成の際に行う、前記第1の予備トポロジに基づく前記次FIB-IDの選択において、前記パケットに付された前記src-IDおよび前記dst-IDに基づき、故障発生前の最短経路を計算し、その最短経路上のリンクを抽出し、前記1番目の前記故障リンクをプロテクトする前記第1の予備トポロジのプロテクトリンクを抽出し、前記最短経路上のリンクと前記第1の予備トポロジのプロテクトリンクとに重複するリンクを、推定故障リンクとして抽出し、前記抽出した推定故障リンクと、前記2番目の故障リンクをプロテクトする前記予備トポロジとして抽出される1つ以上の前記第2の予備トポロジについて、転送ループが発生するか否かを判定し、前記第2の予備トポロジのうち、前記転送ループの発生が最も少ない前記第2の予備トポロジを抽出し、そのFIB-IDを次FIB-IDとして選択することを特徴とする請求項1に記載の故障復旧システムとした。
【0023】
このようにすることで、FIB-ID探索テーブル作成部は、1番目のリンク故障の発生箇所を推定し、推定故障リンクで故障が発生するとした場合に、2番目の故障リンクをプロテクトする第2の予備トポロジにおいて、転送ループが発生するか否かを判定し、転送ループの発生が最も少ない第2の予備トポロジを抽出して、そのFIB-IDを次FIB-IDとし、FIB-ID探索テーブルを作成することができる。これにより、1番目の故障リンクを回避するような第2の予備トポロジが選択され、転送ループの発生する確率を低下させることができる。
【0024】
請求項6に記載の発明は、請求項5に記載の故障復旧方法を、コンピュータである前記ノードに実行させるためのプログラムとした。
【0025】
このようなプログラムによれば、請求項5に記載の故障復旧方法を、一般的なコンピュータであるノードで実現することができる。
【発明の効果】
【0026】
本発明によれば、パケット交換網における多重故障復旧時に、転送ループの発生する確率を低下させることができる、故障復旧システム、ノード、故障復旧方法およびプログラムを提供することができる。
【図面の簡単な説明】
【0027】
【図1】IP−FRR方式における予備トポロジを用いた故障復旧方法を説明するための図である。
【図2】予備トポロジの設計例を示す図である。
【図3】多重故障による転送ループの発生を説明するための図である。
【図4】本実施形態に係る故障復旧システムの概要を説明するための図である。
【図5】本実施形態に係る通信ネットワーク(故障復旧システム)の構成例を示す図である。
【図6】本実施形態に係るノードの構成例を示す機能ブロック図である。
【図7】本実施形態に係る記憶部に記憶される情報のデータ構成を説明するための図である。
【図8】本実施形態に係る類似判定法によるFIB-ID探索テーブルの作成処理を示すフローチャートである。
【図9】本実施形態に係る故障箇所推定法によるFIB-ID探索テーブルの作成処理を示すフローチャートである。
【図10】本実施形態に係る故障箇所推定法の概要を説明するための図である。
【図11】本実施形態に係る故障復旧方法の全体の処理の流れを示すフローチャートである。
【図12】本実施形態に係る通信ネットワーク(故障復旧システム)の変形例の構成を示す図である。
【発明を実施するための形態】
【0028】
次に、本発明を実施するための形態(以下、「本実施形態」という)における故障復旧システム等について説明する。
【0029】
≪概要≫
まず、本実施形態に係る故障復旧システムの概要について説明する。
図4は、本実施形態に係る故障復旧システムの概要を説明するための図である。
【0030】
図4(a)に示すように、従来の故障復旧の方式では、1番目の故障である故障xのみを考慮して予備経路を決定するため、2番目の故障である故障yが発生すると、1番目の故障である故障xを再び選び、転送ループが発生する問題があった。
【0031】
本実施形態に係る故障復旧システムでは、1番目の故障を回避するために選択された予備トポロジの情報に基づいて、2番目の故障に対して、適切な予備トポロジを選択することで、検出した故障x,yの両方を迂回し、転送ループの発生する確率を低下させる。図4(b)に示す例においては、2番目の故障である故障yをプロテクトする際に、予備トポロジ#1(図2(b)参照)を選択すると転送ループが発生するが、予備トポロジ#3(図2(d)参照)を選択した場合には、転送ループは発生しない。このように、2番目の故障に対して、適切な予備トポロジを選択することで、転送ループの発生する確率を低下させる。
【0032】
この2番目の予備トポロジの選択方法として、本実施形態に係る故障復旧システムでは、(1)予備トポロジ間の類似性に基づく選択方法(類似性判定法)、または、(2)1番目の故障位置の推定結果に基づく選択方法(故障箇所推定法)という本発明に特有な処理を実行することにより、検出した故障を回避しつつ転送ループの発生しにくい予備トポロジを選択することが可能となる。この類似性判定法および故障箇所推定法については、後記し詳細に説明する。
【0033】
≪故障復旧システム構成≫
次に、本実施形態に係る故障復旧システムとしての通信ネットワーク1000の構成について説明する。
図5は、本実施形態に係る通信ネットワーク1000の構成例を示す図である。
【0034】
故障復旧システムとしての通信ネットワーク1000は、複数のノード1と、各ノード1間を接続することにより通信経路を提供するリンクとで構成される。このノード1間には、トラヒックが発生しており、トラヒックは、IPパケット単位でノード1に到着するものとする。
また、この通信ネットワーク1000を構成する各ノード1それぞれには、後記するノード1の制御部により実現される故障回復機能が備わっている。
【0035】
≪ノードの構成≫
続いて、本実施形態に係るノード1について説明する。
図6は、本実施形態に係るノード1の構成例を示す機能ブロック図である。
【0036】
ノード1は、IPパケット(以下単に「パケット」と呼ぶ)を転送する中継装置であり、例えば、ルータである。このノード1は、不図示の制御部と、通信部と、記憶部とを備える。
【0037】
通信部は、入力インタフェース(I/F)31と出力インタフェース(I/F)32とを含んで構成され、それぞれのインタフェースには、接続先のノード1別のリンクが各ポートを介して接続され、パケットの受信および送信を実行する。
【0038】
制御部は、通信ネットワーク1000におけるパケットの転送処理や、パケット交換における故障復旧処理の全般を制御し、経路テーブル(FIB:Forwarding Information Base)作成部11と、FIB-ID探索テーブル作成部12と、テーブル探索部13と、出力ポート確認部14と、FIB-ID更新部15とを含んで構成される。
【0039】
経路テーブル(FIB)作成部11は、後記するトポロジ情報100に基づき転送経路の計算を行い、経路テーブル(FIB)200を作成する。具体的には、経路テーブル(FIB)作成部11は、トポロジ情報100に記憶される、通常のトポロジと、複数の予備トポロジに基づき、通常の経路テーブル(Primary FIB)210、および複数の予備経路テーブル(Backup FIB)220の作成を行う。
この経路テーブル(FIB)200としての通常の経路テーブル(Primary FIB)210および予備経路テーブル(Backup FIB)220には、本故障復旧システムに固有な番号であるFIB-IDが付されている。そして、各経路テーブル(FIB)200には、パケットの宛先アドレスを示すdst-IDと、出力インタフェース32である出力ポートとの対応関係を示す情報が格納される。
また、この経路テーブル(FIB)作成部11が行う処理は、既存の予備トポロジ設計アルゴリズムにより行われる。
【0040】
FIB-ID探索テーブル作成部12は、FIB-ID探索テーブル300を、最短経路探索法や、類似性判定法、故障箇所推定法を用いて作成する。
図7に示すように、FIB-ID探索テーブル300には、現時点でのパケットに付与されている経路テーブル(FIB)200のIDを示す「現FIB-ID」、送信元アドレスを示す「src-ID」、および、宛先アドレスを示す「dst-ID」が、次に選択すべき経路テーブル(FIB)200のIDを示す「次FIB-ID」に対応付けられて記憶される。
このFIB-ID探索テーブル作成部12による、FIB-ID探索テーブル300の作成法については、後記し詳細に説明する。
【0041】
図6に戻り、テーブル探索部13は、入力インタフェース(I/F)31を介してパケットを受信し、そのパケットのヘッダに付与されたFIB−IDおよび宛先アドレスを示すdst-IDを取得する。そして、テーブル探索部13は、FIB-IDを用いて、通常の経路テーブル210および予備経路テーブル220を探索し、該当するFIB−IDの経路テーブル(FIB)200を抽出し、dst-IDをキーとして、出力ポートを決定する。テーブル探索部13は、決定した出力ポートの情報を出力ポート確認部14に引き渡す。
また、テーブル探索部13は、FIB-ID更新部15から、次FIB-IDが付されたパケットを受信すると、その次FIB-IDとdst-IDとを用いて、予備経路テーブル220を探索し、出力ポートを決定する。そして、テーブル探索部13は、決定した出力ポートの情報を出力ポート確認部14に引き渡す。
【0042】
出力ポート確認部14は、テーブル探索部13から受信した出力ポートが起動しているかを確認する。つまり、そのリンクを介して正常に他のノード1に送信可能か否かを確認する。
出力ポート確認部14は、出力ポートが起動している場合には、その出力ポートへパケットを引き渡し、出力インタフェース(I/F)32を介してパケットを送信する。一方、出力ポート確認部14は、出力ポートが起動していない場合には、そのパケットをFIB-ID更新部15に引き渡す。
【0043】
FIB-ID更新部15は、出力ポート確認部14から、パケットを受信すると、そのパケットのヘッダから、現FIB-ID、src-ID、dst-IDを取得し、これらをキーとして、FIB-ID探索テーブル300を探索し、更新後のFIB-IDである次FIB-IDを取得する。
そして、FIB-ID更新部15は、取得した次FIB-IDを付したパケットを、テーブル探索部13に引き渡す。
【0044】
また、記憶部には、トポロジ情報100と、経路テーブル(FIB)200と、FIB-ID探索テーブル300とを含む情報が記憶される。図7は、記憶部に記憶される各情報についての、データ構成(情報要素)と、その取得・生成方法を示している。
ここで、トポロジ情報100は、通信ネットワーク1000内の各ノード1間のリンクによる接続関係を示し、経路テーブル(FIB)作成部11が、OSPF等のルーチングプロトコルを用いて取得する。また、このトポロジ情報100には、経路テーブル(FIB)作成部11が、既存の予備トポロジ設計アルゴリズムにより生成した予備トポロジが記憶される。なお、経路テーブル(FIB)200およびFIB-ID探索テーブル300については、既に説明を行っているので、ここでは説明を省略する。
【0045】
そして、この記憶部は、RAM(Random Access Memory)や、HDD(Hard Dick Drive)、フラッシュメモリ等の記憶媒体から構成される。ノード1をプログラム実行処理により実現する場合、記憶部には、ノード1の制御部の機能を実現するためのプログラムが格納される。そして、制御部は、記憶部に記憶されたプログラムを、不図示のCPU(Central Processing Unit)が、RAM等に展開し実行することで実現される。
【0046】
≪FIB-ID探索テーブルの作成方法≫
次に、本実施形態に係る故障復旧システムの各ノード1が、パケット転送の処理前に事前に行っておく、FIB-ID探索テーブル300の作成処理について説明する。
FIB-ID探索テーブル300は、前記したように、現時点でのパケットに付与されている経路テーブル(FIB)200のIDを示す「現FIB-ID」、送信元アドレスを示す「src-ID」、および、宛先アドレスを示す「dst-ID」が、次に選択すべき経路テーブル(FIB)200のIDを示す「次FIB-ID」に対応付けられて記憶される情報である。
各ノード1のFIB-ID探索テーブル作成部12は、FIB-ID探索テーブル300を、最短経路探索法、類似性判定法、故障箇所推定法を用いて作成する。
【0047】
(最短経路探索法)
まず、1番目の故障リンクの検出時の予備トポロジを決定し、FIB-ID探索テーブル300を作成するために用いる、最短経路探索法について説明する。
【0048】
最短経路探索法(Shortest Method)は、検出した故障リンクをプロテクトしつつ、予備経路の経路長が最短となる予備トポロジを選択する方法である。予備経路の経路長は、パケットのヘッダに付与された宛先ノードの情報をもとに、各予備トポロジにおいて、故障検出ノードから宛先ノードまでの経路を計算することにより算出される。
【0049】
まず、FIB-ID探索テーブル作成部12は、1番目の故障リンクをプロテクトする予備経路を、故障検出ノードから宛先ノードまでの経路長が最短となる予備トポロジを探索することにより決定し、その予備トポロジにより作成された予備経路テーブル(Backup FIB)220のFIB-IDを取得する。
そして、FIB-ID探索テーブル作成部12は、FIB-ID探索テーブル300の「現FIB-ID」に、通常の経路テーブル(Primary FIB)210のFIB-IDを格納し、「次FIB-ID」に、経路長が最短となる予備経路テーブル(Backup FIB)220のFIB-IDを格納して、src-ID、dst-IDを含めた、FIB-ID探索テーブル300を作成する。
【0050】
次に、FIB-ID探索テーブル作成部12は、2番目の故障リンクの検出時に備えたFIB-ID探索テーブル300を、類似性判定法、または、故障箇所推定法を用いて作成する。なお、2番目の故障検出時に備えたFIB-ID探索テーブル300の作成を、最短経路探索法を用いて行ってもよいが、以下に説明する、類似性判定法、故障箇所推定法に比べると、転送ループの発生する確率を低下させる効果は低いものとなる。
【0051】
(類似性判定法)
類似性判定法(Similarity Method)は、2番目に検出した故障リンクをプロテクトしつつ、1番目に選択した予備トポロジとの類似性が最大となる予備トポロジを、2番目の故障検出時に備えた予備トポロジとして選択する。ここで、類似性とは、全プロテクトリンク数に対し、同一のリンクをプロテクトしている数の割合として定義される。この類似性判定法の基本的な考え方は、類似性の高い2つの予備トポロジは、提供する経路に関しても類似性が高いと考えられるため、1番目の故障リンクをプロテクトするために選ばれた予備トポロジに類似する予備トポロジは、同様に1番目の故障リンクをプロテクトしている確率が高いとの考えに基づく。
【0052】
この類似性判定法に基づく、2番目の故障検出時に備えたFIB-ID探索テーブル300の作成法を、図8を参照して説明する。図8は、本実施形態に係る類似判定法によるFIB-ID探索テーブル300の作成処理を示すフローチャートである。
【0053】
まず、FIB-ID探索テーブル作成部12は、1番目の故障検出時に備えて作成されたFIB-ID探索テーブル300内の「次FIB-ID」を抽出する(ステップS101)。
【0054】
次に、FIB-ID探索テーブル作成部12は、トポロジ情報100に記憶されている予備トポロジ全体の中から、2番目の故障リンクをプロテクトする予備トポロジ(「第2の予備トポロジ」と呼ぶ)を抽出する(ステップS102)。
【0055】
そして、FIB-ID探索テーブル作成部12は、ステップS101において「次FIB-ID」として抽出されたFIB-IDの予備トポロジ(「第1の予備トポロジ」と呼ぶ)と、ステップS102で抽出された第2の予備トポロジとの類似性を判定し、第2の予備トポロジのうち最も類似性が高い、つまり、全プロテクトリンク数に対し、同一のリンクをプロテクトしている数の割合が最も高い第2の予備トポロジを選択する(ステップS103)。
【0056】
続いて、FIB-ID探索テーブル作成部12は、FIB-ID探索テーブル300の「現FIB-ID」に、第1の予備トポロジのFIB-IDを格納し、「次FIB-ID」に、最も類似性の高い第2の予備トポロジのFIB-IDを格納して、src-ID、dst-IDを含めた、FIB-ID探索テーブル300を作成する(ステップS104)。
【0057】
このようにして、FIB-ID探索テーブル作成部12は、パケットの転送処理を実行する前に、FIB-ID探索テーブル300を、類似性判定法に基づき作成することができる。
【0058】
(故障箇所推定法)
故障箇所推定法(Estimation Method)は、2番目に検出した故障リンクをプロテクトしつつ、1番目の故障リンク位置を推定することで、転送ループが最も発生しにくい予備トポロジを選択する方法である。
【0059】
この故障箇所推定法に基づく、2番目の故障検出時に備えたFIB-ID探索テーブル300の作成法を、図9および図10を参照して説明する。図9は、本実施形態に係る故障箇所推定法によるFIB-ID探索テーブル300の作成処理を示すフローチャートである。図10は、本実施形態に係る故障箇所推定法の概要を説明するための図である。なお、図10においては、図3および図4で示したリンク故障x,yの例とは、別の例として説明する。
【0060】
図9に示すように、まず、FIB-ID探索テーブル作成部12は、パケットのヘッダに付与される、送信元アドレスを示す「src-ID」と、宛先アドレスを示す「dst-ID」から、故障が発生する前の最短経路を計算する。そして、その最短経路を構成するリンクの集合を「E1」として抽出する(ステップS201)。
図10(a)に示す例では、最短経路「1」−「4」−「7」が計算され、そのリンク集合「E1」として、リンク1−4,4−7が抽出される。
【0061】
次に、FIB-ID探索テーブル作成部12は、1番目の故障検出時に備えて作成されたFIB-ID探索テーブル300内の「次FIB-ID」を抽出し、「次FIB-ID」として抽出されたFIB-IDの予備トポロジ(第1の予備トポロジ)上のプロテクトリンクの集合を「E2」として抽出する(ステップS202)。
図10(b)に示す例では、予備トポロジ#1のプロテクトリンクの集合「E2」として、リンク1−2,1−6,2−3,2−4,3−8,4−7,7−8が抽出される。
【0062】
続いて、FIB-ID探索テーブル作成部12は、「E1」と「E2」の論理積をとった積集合を「E3」として抽出する(ステップS203)。この「E3」が推定故障リンクの集合となる。
図10に示す例では、「E1」と「E2」の積集合はリンク4−7となり、故障箇所が推定される。なお、図10の例では、故障箇所が1つ推定されるが、複数推定される場合もある。
【0063】
そして、FIB-ID探索テーブル作成部12は、トポロジ情報100に記憶されている予備トポロジ全体の中から、2番目の故障リンクをプロテクトする予備トポロジ(第2の予備トポロジ)を抽出する(ステップS204)。
【0064】
続いて、FIB-ID探索テーブル作成部12は、ステップS203の推定故障リンクで故障が発生したと想定し、ステップS204で抽出した第2の予備トポロジの1つを選択した場合に、転送ループが発生するか否かを評価する(ステップS205)。
ここでは、FIB-ID探索テーブル作成部12は、抽出した第2の予備トポロジ毎に、転送ループが発生しない場合の評価値を「0」、転送ループが1箇所発生する場合の評価値を「1」、転送ループが2箇所発生する場合の評価値を「2」等のようにし、結果として、最も転送ループの発生に関する評価値の値が小さい第2の予備トポロジを選択する。なお、ステップS203において、推定故障リンクが複数抽出される場合があるため、転送ループが複数の箇所で発生するとの評価される場合がある。
【0065】
次に、FIB-ID探索テーブル作成部12は、評価値の値が最も小さい第2の予備トポロジを選択する(ステップS206)。
【0066】
そして、FIB-ID探索テーブル300の「現FIB-ID」に、第1の予備トポロジのFIB-IDを格納し、「次FIB-ID」に、最も評価値の値が小さい第2の予備トポロジのFIB-IDを格納して、src-ID、dst-IDを含めた、FIB-ID探索テーブル300を作成する(ステップS207)。
【0067】
このようにして、FIB-ID探索テーブル作成部12は、パケットの転送処理を実行する前に、FIB-ID探索テーブル300を、故障箇所推定法に基づき作成することができる。
【0068】
≪故障箇所復旧方法の全体の処理≫
次に、本実施形態に係る故障復旧システムにおける、故障復旧方法の全体の処理の流れを説明する(適宜図6参照)。
図11は、本実施形態に係る故障復旧方法の全体の処理の流れを示すフローチャートである。
【0069】
まず、経路テーブル(FIB)作成部11は、トポロジ情報100に基づき転送経路の計算を行い、通常の経路テーブル(Primary FIB)210、および予備経路テーブル(Backup FIB)220の作成を行う(ステップS301)。
【0070】
次に、FIB-ID探索テーブル作成部12は、最短経路探索法と、類似性判定法、故障箇所推定法のいずれかを用いて、FIB-ID探索テーブル300を作成する(ステップS302)。
FIB-ID探索テーブル作成部12が、FIB-ID探索テーブル300の作成の際に、類似性判定法、故障箇所推定法のいずれを用いるかは、ネットワーク管理者等により任意に設定されるが、類似性判定法の方が、故障箇所推定法に比べ処理負荷が少ないが、故障箇所推定法の方が、類似性判定法に比べ、転送ループの発生する確率をより低下させることができるという特徴がある。
【0071】
このステップS301とステップS302の処理は、パケット転送処理の前に各ノード1が予め計算しておく処理である。つまり、パケット転送時にリアルタイムで実行される計算ではないため、処理負荷の影響を考慮する必要はない。
【0072】
そして、ノード1のテーブル探索部13は、入力インタフェース(I/F)31を介して、パケットを受信すると、パケットのヘッダに付されたFIB-IDおよびdst-ID(宛先アドレス)をキーとして、通常の経路テーブル(Primary FIB)210、および予備経路テーブル(Backup FIB)220を探索し、出力ポートを取得する(ステップ303)。
【0073】
次に、出力ポート確認部14は、出力ポートが起動しているか否かを確認する(ステップS304)。出力ポート確認部14は、出力ポートが起動している場合には(ステップS304→Yes)、その出力ポートへパケットを引き渡し、出力インタフェース(I/F)32を介して、パケットを送信して(ステップS305)、処理を終える。
【0074】
一方、出力ポート確認部14は、出力ポートが起動していない場合には(ステップS304→No)、次のステップS306に進む。
【0075】
ステップS306において、出力ポート確認部14は、そのパケットをFIB-ID更新部15に引き渡す。
【0076】
続いて、FIB-ID更新部15は、出力ポート確認部14から、パケットを受信すると、そのパケットのヘッダ情報から、現FIB-ID、src-ID、dst-IDを取得し、これらをキーとして、FIB-ID探索テーブル300を探索し、更新後のFIB-IDである次FIB-IDを取得する(ステップS307)。そして、FIB-ID更新部15は、取得した次FIB-IDを付したパケットを、テーブル探索部13に引き渡し、ステップS303に戻る。
【0077】
そして、テーブル探索部13が、FIB-ID更新部15から次FIB-IDが付されたパケットを受信すると、その次FIB-IDとdst-IDとを用いて、予備経路テーブル220を探索し、出力ポートを決定する。そして、テーブル探索部13は、決定した出力ポートの情報を出力ポート確認部14に引き渡し、ステップS304以降の処理を続ける。
【0078】
以上説明したように、本実施形態に係る故障復旧システム、ノード、故障復旧方法およびプログラムによれば、パケット交換網の多重故障復旧時に発生していた転送ループについて、類似性判定法や、故障箇所推定法を用いたFIB-ID探索テーブル300を予め作成しておき、2番目の故障に対して適切な予備トポロジを、FIB-ID探索テーブル300を参照して選択することで、転送ループの発生する確率を低下させることができる。
【0079】
≪変形例≫
本実施形態に係る故障復旧システムとしての通信ネットワーク1000は、図5に示したように、通信ネットワーク1000内のノードそれぞれが、故障回復機能を備える構成とした。しかし、本発明はこれに限定されず、例えば、図12に示すように、故障復旧サーバ1100を、ネットワーク情報取得装置1200を介して通信ネットワーク1000に接続する構成にすることもできる。
【0080】
この場合、故障復旧サーバ1100が、経路テーブル(FIB)作成部11とFIB-ID探索テーブル作成部12とを備え、ネットワーク情報取得装置1200を介して、各ノード間のトポロジ情報100を取得する。そして、故障復旧サーバ1100が、経路テーブル(FIB)200およびFIB-ID探索テーブル300を作成し、各ノード1aに対して、パケット転送処理の開始前に配信するようにしてもよい。
【符号の説明】
【0081】
1 ノード
11 経路テーブル(FIB)作成部
12 FIB-ID探索テーブル作成部
13 テーブル探索部
14 出力ポート確認部
15 FIB-ID更新部
31 入力インタフェース(I/F)
32 出力インタフェース(I/F)
100 トポロジ情報
200 経路テーブル(FIB)
210 通常の経路テーブル(Primary FIB)
220 予備経路テーブル(Backup FIB)
300 FIB-ID探索テーブル
1000 通信ネットワーク
1100 故障復旧サーバ
1200 ネットワーク情報取得装置
【技術分野】
【0001】
本発明は、IP(Internet Protocol)ネットワーク等のパケット交換網における、故障復旧時の転送経路再設定技術に関する。
【背景技術】
【0002】
ネットワークにおいては、予期しない故障の発生に対して迅速に転送経路を切り替えることで故障復旧を行い、転送品質の維持を行うことが重要である。IPネットワークにおける故障復旧方式として、OSPF(Open Shortest Path First)等のルーチングプロトコルを用いた動的な復旧方式がある(非特許文献1参照)。
【0003】
OSPFでは、故障を検知したノードは、全ノードに故障情報を通知(フラッディング)する。故障情報を受け取ったノードは、新規に作成される故障箇所を除いた網トポロジ情報をもとに迂回経路を計算することで、自動的に転送経路を切り替えることが可能となる。しかし、OSPFでは故障発生後に迂回経路を計算するため、故障の復旧に秒単位の時間を必要とする問題がある。また、故障情報の通知や迂回経路の計算は、IPネットワークの規模に依存して増加する。
【0004】
このような問題を解決する方法として、事前に迂回経路を計算しておくことで高速な故障復旧を実現するIP−FRR(IP Fast Reroute)方式が提案されている(非特許文献2参照)。IP−FRR方式は、事前に予備トポロジを作成し、故障発生時には該当故障箇所をプロテクトする(迂回する)予備トポロジに従った転送経路に切り替えることで故障復旧を行う。
【0005】
IP−FRR方式における予備トポロジを用いた故障復旧方法の具体例を、図1を参照して説明する。図1(a)は、通常のトポロジの一例を示し、図1(b)は、予備トポロジの一例を示す。
【0006】
まず、各ノードは、リンク断絶(故障)に備えた予備トポロジを予め作成しておく。例えば、リンク1−2(ノード番号「1」のノードと、ノード番号「2」のノードとの間のリンク)が断絶した場合に備え、このリンク1−2をプロテクトする予備トポロジを事前に作成する。ここで、予備トポロジにおけるプロテクトリンクのリンクコストは、このプロテクトリングが経路として選択されないようにするため、設定可能な最大値を付与する。これにより、予備トポロジ上でリンクコストの総和が最小となる最小コストルーティングにより経路を計算すると、プロテクトリンクを使用しない経路が算出される。この予備トポロジは全てのノードに記憶され、各ノードは予備トポロジに従った経路を事前に(トラヒック転送前に)計算しておく。
【0007】
ここで、ノード番号「1」のノードをsrc(source:送信元)とし、ノード番号「5」のノードをdst(destination:宛先)とする経路上において、リンク1−2の故障を検出した場合を考える。例えば、図1(a)に示す通常のトポロジ上で、(1)リンク1−2の故障を検出すると、故障検出ノード(ノード番号「1」のノード)は、故障リンクをプロテクトする予備トポロジAに従ってパケットをノード番号「4」のノードに転送する(図1(b)参照)。このとき、故障検出ノード(ノード番号「1」のノード)は、リンク1−2が故障ノードしたことを知っているので、予備トポロジAを使用すれば故障箇所を迂回できることを知っている。
【0008】
しかし、他のノード(例えば、ノード番号「4」のノード)は、故障箇所を把握できていない。そこで、故障検出ノード(ノード番号「1」のノード)は、(2)使用する予備トポロジAを選択し、この予備トポロジAのID(Identification)をノード番号「4」のノードに転送するパケットのヘッダに記述しておく。そして、迂回経路上に存在する他のノード(ここでは、ノード番号「4」のノード)はパケットを受信すると、(3)このパケットのヘッダを参照し、使用すべき予備トポロジAを選択し、その選択した予備トポロジAに従って、パケットをノード番号「5」のノードに転送する。このように、故障検出ノードは、使用する予備トポロジのIDをパケットに付与することで、データ転送と同時に故障箇所を間接的に伝搬する。
【0009】
図2は、任意の単一リンクの故障をプロテクトする予備トポロジの設計例を示す。図2(a)は、通常のトポロジであり、図2(b)〜(d)は、図2(a)の通常のトポロジの予備トポロジを示す。予備トポロジは、全体の予備トポロジの数を削減するため、単一のトポロジで複数のリンクをプロテクトするように設計される。
【0010】
また、これまでに、予備トポロジ数を最小化したり(非特許文献3参照)、迂回後の負荷を平滑化したり(非特許文献4参照)する予備トポロジ設計アルゴリズムが提案されている。
【先行技術文献】
【非特許文献】
【0011】
【非特許文献1】“OSPF Version 2”,[online], April 1998, IETF RFC2328, [平成23年8月31日検索],インターネット<URL:http://www.ietf.org/rfc/rfc2328.txt>
【非特許文献2】A.Kvalbein, A.F.Hansen, et al.,“Fast IP Network Recovery using Multiple Routing Configurations,” in Proceedings of INFOCOM, Apr.2006.
【非特許文献3】S.Kamamura, T.Miyamura, et al.,“Scalable Backup Configurations Creation for IP Fast Reroute,”IEICE Trans. Commun Vol.E94-B No.1 pp.109-117, 2011.1.
【非特許文献4】R.Takahashi, S.Tembo, et al.,“Dispersing Hotspot Traffic in Backup Topology for IP Fast Reroute,”submitted to IEEE ICC, 2011.6.
【発明の概要】
【発明が解決しようとする課題】
【0012】
しかしながら、既存の方式は、単一のリンクやノードの故障に対しては安定的に動作するが、多重故障の発生によって転送ループが発生する問題がある。なお、パケット交換網上の転送ループは、該当パケットがロスするだけでなく、ループするパケットによる帯域消費が、他のパケット通信に悪影響を与える可能性があるため、極力避ける必要がある。
【0013】
転送ループ発生の具体例を、図3を参照して説明する。ノード「i」からノード「dst」に向けてパケットを転送する際に、図3(a)に示すリンク故障x,yが発生する場合を考える。故障xを検出したノード「i」は、予備トポロジ#2を選択し、予備トポロジ#2に従った予備経路「1」−「2」−「3」−「8」−「7」−「6」に沿った転送を試みる(図3(b)参照)。一方で、予備経路上には2つ目の故障である故障yが存在するため、故障yを検出したノード「j」は、故障yをプロテクトする予備トポロジ#1を選択する(図3(c)参照)。ここで、予備トポロジ#1に従った予備経路「2」−「1」−「6」は、再度リンク故障xを含む経路となる。結果として、この例ではノード「i」とノード「j」との間で、転送ループが発生する。
【0014】
この問題は、既存技術では、故障検出ノード以外のノードには、予備トポロジのIDのみが伝搬されるため、故障箇所の特定ができないことに起因する。例えば、二重故障の場合、2番目の故障を検出したノードは、2番目の故障を回避する予備トポロジを選択することは可能であるが、1番目の故障の故障箇所が既知ではないため、再度1番目の故障を含む予備トポロジを選択する可能性があり、このような場合には、転送ループが発生する。
【0015】
このような背景に鑑みて本発明がなされたのであり、本発明は、パケット交換網における多重故障復旧時に、転送ループの発生する確率を低下させることができる、故障復旧システム、ノード、故障復旧方法およびプログラムを提供することを課題とする。
【課題を解決するための手段】
【0016】
前記した課題を解決するため、請求項1に記載の発明は、複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムであって、前記故障復旧システムの各ノードが、パケットを送受信する通信部と、前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部と、前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すdst-IDと、出力ポートとを対応付けた経路テーブル(FIB)を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル(FIB)の識別子であるFIB-IDに対応付けて作成する経路テーブル(FIB)作成部と、1番目の前記故障リンクをプロテクトする前記予備トポロジを示す第1の予備トポロジの現FIB−IDと、前記パケットの送信元アドレスを示すsrc-IDと、前記dst-IDとを、2番目の前記故障リンクをプロテクトする前記予備トポロジを示す第2の予備トポロジの前記FIB-IDであり、前記第1の予備トポロジに基づき選択された次FIB-IDに対応付けたFIB-ID探索テーブルを作成するFIB-ID探索テーブル作成部と、前記FIB-ID、前記src-IDおよび前記dst-IDが付された前記パケットを、前記通信部を介して受信し、前記FIB-IDをキーとして、前記経路テーブル(FIB)を探索し、前記出力ポートを取得するテーブル探索部と、前記出力ポートが起動しているか否かを判定し、前記起動していると判定した場合には、当該出力ポートから前記パケットを送信し、前記起動してないと判定した場合には、前記パケットをFIB-ID更新部に引き渡す出力ポート確認部と、前記パケットに付された前記FIB-ID、前記src-IDおよび前記dst-IDに基づき、前記パケットに付された前記FIB-IDを前記現FIB-IDとして、前記FIB-ID探索テーブルを探索し、前記次FIB-IDを取得し、当該次FIB-IDを付した前記パケットを、前記テーブル探索部に引き渡す前記FIB-ID更新部と、を備え、前記テーブル探索部が、前記次FIB-IDが付されたパケットを受信すると、前記次FIB-IDをキーとして前記経路テーブル(FIB)を探索し、前記出力ポートを取得して、前記出力ポート確認部に引き渡すことを特徴とする故障復旧システムとした。
【0017】
また、請求項4に記載の発明は、複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムの前記ノードであって、パケットを送受信する通信部と、前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部と、前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すdst-IDと、出力ポートとを対応付けた経路テーブル(FIB)を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル(FIB)の識別子であるFIB-IDに対応付けて作成する経路テーブル(FIB)作成部と、1番目の前記故障リンクをプロテクトする前記予備トポロジを示す第1の予備トポロジの現FIB−IDと、前記パケットの送信元アドレスを示すsrc-IDと、前記dst-IDとを、2番目の前記故障リンクをプロテクトする前記予備トポロジを示す第2の予備トポロジの前記FIB-IDであり、前記第1の予備トポロジに基づき選択された次FIB-IDに対応付けたFIB-ID探索テーブルを作成するFIB-ID探索テーブル作成部と、前記FIB-ID、前記src-IDおよび前記dst-IDが付された前記パケットを、前記通信部を介して受信し、前記FIB-IDをキーとして、前記経路テーブル(FIB)を探索し、前記出力ポートを取得するテーブル探索部と、前記出力ポートが起動しているか否かを判定し、前記起動していると判定した場合には、当該出力ポートから前記パケットを送信し、前記起動してないと判定した場合には、前記パケットをFIB-ID更新部に引き渡す出力ポート確認部と、前記パケットに付された前記FIB-ID、前記src-IDおよび前記dst-IDに基づき、前記パケットに付された前記FIB-IDを前記現FIB-IDとして、前記FIB-ID探索テーブルを探索し、前記次FIB-IDを取得し、当該次FIB-IDを付した前記パケットを、前記テーブル探索部に引き渡す前記FIB-ID更新部と、を備え、前記テーブル探索部が、前記次FIB-IDが付されたパケットを受信すると、前記次FIB-IDをキーとして前記経路テーブル(FIB)を探索し、前記出力ポートを取得して、前記出力ポート確認部に引き渡すことを特徴とするノードとした。
【0018】
また、請求項5に記載の発明は、 複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムの故障復旧方法であって、前記故障復旧システムのノードが、前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部を備えており、前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すdst-IDと、出力ポートとを対応付けた経路テーブル(FIB)を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル(FIB)の識別子であるFIB-IDに対応付けて作成するステップと、1番目の前記故障リンクをプロテクトする前記予備トポロジを示す第1の予備トポロジの現FIB−IDと、前記パケットの送信元アドレスを示すsrc-IDと、前記dst-IDとを、2番目の前記故障リンクをプロテクトする前記予備トポロジを示す第2の予備トポロジの前記FIB-IDであり、前記第1の予備トポロジに基づき選択された次FIB-IDに対応付けたFIB-ID探索テーブルを作成するステップと、前記FIB-ID、前記src-IDおよび前記dst-IDが付された前記パケットを受信し、前記FIB-IDをキーとして、前記経路テーブル(FIB)を探索し、前記出力ポートを取得するステップと、前記出力ポートが起動しているか否かを判定し、前記出力ポートが起動していると判定した場合に、当該出力ポートから前記パケットを送信するステップと、前記出力ポートが起動してないと判定した場合に、前記パケットに付された前記FIB-ID、前記src-IDおよび前記dst-IDに基づき、前記パケットに付された前記FIB-IDを前記現FIB-IDとして、前記FIB-ID探索テーブルを探索し、前記次FIB-IDを取得するステップと、前記次FIB-IDを付した前記パケットを受信し、当該次FIB-IDをキーとして前記経路テーブル(FIB)を探索し、前記出力ポートを取得して、当該取得した出力ポートが起動しているか否かを判定して、前記パケットの送信するステップ、または、前記次FIB-IDを取得するステップを実行することを特徴とする故障復旧方法とした。
【0019】
このようにすることで、2番目のリンク故障が発生した場合であっても、1番目のリンク故障をプロテクトするために選択された第1の予備トポロジに基づき、2番目のリンク故障をプロテクトしつつ、1番目の故障リンクを回避するように第2の予備トポロジを選択し、パケットを転送することができる。これにより、転送ループの発生する確率を低下させることができる。
【0020】
請求項2に記載の発明は、前記FIB-ID探索テーブル作成部が、前記FIB-ID探索テーブルの作成の際に行う、前記第1の予備トポロジに基づく前記次FIB-IDの選択において、前記2番目の故障リンクをプロテクトする前記予備トポロジとして抽出される1つ以上の前記第2の予備トポロジについて、全プロテクトリンク数に対し、前記第1の予備トポロジがプロテクトしているリンクと同一のリンクをプロテクトしている数の割合を示す類似性を計算し、前記第2の予備トポロジのうち、前記類似性の最も高い前記第2の予備トポロジを抽出し、そのFIB-IDを次FIB-IDとして選択することを特徴とする請求項1に記載の故障復旧システムとした。
【0021】
このようにすることで、FIB-ID探索テーブル作成部は、第1の予備トポロジと第2の予備トポロジの類似性を計算し、最も類似性の高い第2の予備トポロジを抽出して、そのFIB-IDを次FIB-IDとし、FIB-ID探索テーブルを作成することができる。これにより、1番目の故障リンクを回避するような第2の予備トポロジが選択され、転送ループの発生する確率を低下させることができる。
【0022】
請求項3に記載の発明は、前記FIB-ID探索テーブル作成部は、前記FIB-ID探索テーブルの作成の際に行う、前記第1の予備トポロジに基づく前記次FIB-IDの選択において、前記パケットに付された前記src-IDおよび前記dst-IDに基づき、故障発生前の最短経路を計算し、その最短経路上のリンクを抽出し、前記1番目の前記故障リンクをプロテクトする前記第1の予備トポロジのプロテクトリンクを抽出し、前記最短経路上のリンクと前記第1の予備トポロジのプロテクトリンクとに重複するリンクを、推定故障リンクとして抽出し、前記抽出した推定故障リンクと、前記2番目の故障リンクをプロテクトする前記予備トポロジとして抽出される1つ以上の前記第2の予備トポロジについて、転送ループが発生するか否かを判定し、前記第2の予備トポロジのうち、前記転送ループの発生が最も少ない前記第2の予備トポロジを抽出し、そのFIB-IDを次FIB-IDとして選択することを特徴とする請求項1に記載の故障復旧システムとした。
【0023】
このようにすることで、FIB-ID探索テーブル作成部は、1番目のリンク故障の発生箇所を推定し、推定故障リンクで故障が発生するとした場合に、2番目の故障リンクをプロテクトする第2の予備トポロジにおいて、転送ループが発生するか否かを判定し、転送ループの発生が最も少ない第2の予備トポロジを抽出して、そのFIB-IDを次FIB-IDとし、FIB-ID探索テーブルを作成することができる。これにより、1番目の故障リンクを回避するような第2の予備トポロジが選択され、転送ループの発生する確率を低下させることができる。
【0024】
請求項6に記載の発明は、請求項5に記載の故障復旧方法を、コンピュータである前記ノードに実行させるためのプログラムとした。
【0025】
このようなプログラムによれば、請求項5に記載の故障復旧方法を、一般的なコンピュータであるノードで実現することができる。
【発明の効果】
【0026】
本発明によれば、パケット交換網における多重故障復旧時に、転送ループの発生する確率を低下させることができる、故障復旧システム、ノード、故障復旧方法およびプログラムを提供することができる。
【図面の簡単な説明】
【0027】
【図1】IP−FRR方式における予備トポロジを用いた故障復旧方法を説明するための図である。
【図2】予備トポロジの設計例を示す図である。
【図3】多重故障による転送ループの発生を説明するための図である。
【図4】本実施形態に係る故障復旧システムの概要を説明するための図である。
【図5】本実施形態に係る通信ネットワーク(故障復旧システム)の構成例を示す図である。
【図6】本実施形態に係るノードの構成例を示す機能ブロック図である。
【図7】本実施形態に係る記憶部に記憶される情報のデータ構成を説明するための図である。
【図8】本実施形態に係る類似判定法によるFIB-ID探索テーブルの作成処理を示すフローチャートである。
【図9】本実施形態に係る故障箇所推定法によるFIB-ID探索テーブルの作成処理を示すフローチャートである。
【図10】本実施形態に係る故障箇所推定法の概要を説明するための図である。
【図11】本実施形態に係る故障復旧方法の全体の処理の流れを示すフローチャートである。
【図12】本実施形態に係る通信ネットワーク(故障復旧システム)の変形例の構成を示す図である。
【発明を実施するための形態】
【0028】
次に、本発明を実施するための形態(以下、「本実施形態」という)における故障復旧システム等について説明する。
【0029】
≪概要≫
まず、本実施形態に係る故障復旧システムの概要について説明する。
図4は、本実施形態に係る故障復旧システムの概要を説明するための図である。
【0030】
図4(a)に示すように、従来の故障復旧の方式では、1番目の故障である故障xのみを考慮して予備経路を決定するため、2番目の故障である故障yが発生すると、1番目の故障である故障xを再び選び、転送ループが発生する問題があった。
【0031】
本実施形態に係る故障復旧システムでは、1番目の故障を回避するために選択された予備トポロジの情報に基づいて、2番目の故障に対して、適切な予備トポロジを選択することで、検出した故障x,yの両方を迂回し、転送ループの発生する確率を低下させる。図4(b)に示す例においては、2番目の故障である故障yをプロテクトする際に、予備トポロジ#1(図2(b)参照)を選択すると転送ループが発生するが、予備トポロジ#3(図2(d)参照)を選択した場合には、転送ループは発生しない。このように、2番目の故障に対して、適切な予備トポロジを選択することで、転送ループの発生する確率を低下させる。
【0032】
この2番目の予備トポロジの選択方法として、本実施形態に係る故障復旧システムでは、(1)予備トポロジ間の類似性に基づく選択方法(類似性判定法)、または、(2)1番目の故障位置の推定結果に基づく選択方法(故障箇所推定法)という本発明に特有な処理を実行することにより、検出した故障を回避しつつ転送ループの発生しにくい予備トポロジを選択することが可能となる。この類似性判定法および故障箇所推定法については、後記し詳細に説明する。
【0033】
≪故障復旧システム構成≫
次に、本実施形態に係る故障復旧システムとしての通信ネットワーク1000の構成について説明する。
図5は、本実施形態に係る通信ネットワーク1000の構成例を示す図である。
【0034】
故障復旧システムとしての通信ネットワーク1000は、複数のノード1と、各ノード1間を接続することにより通信経路を提供するリンクとで構成される。このノード1間には、トラヒックが発生しており、トラヒックは、IPパケット単位でノード1に到着するものとする。
また、この通信ネットワーク1000を構成する各ノード1それぞれには、後記するノード1の制御部により実現される故障回復機能が備わっている。
【0035】
≪ノードの構成≫
続いて、本実施形態に係るノード1について説明する。
図6は、本実施形態に係るノード1の構成例を示す機能ブロック図である。
【0036】
ノード1は、IPパケット(以下単に「パケット」と呼ぶ)を転送する中継装置であり、例えば、ルータである。このノード1は、不図示の制御部と、通信部と、記憶部とを備える。
【0037】
通信部は、入力インタフェース(I/F)31と出力インタフェース(I/F)32とを含んで構成され、それぞれのインタフェースには、接続先のノード1別のリンクが各ポートを介して接続され、パケットの受信および送信を実行する。
【0038】
制御部は、通信ネットワーク1000におけるパケットの転送処理や、パケット交換における故障復旧処理の全般を制御し、経路テーブル(FIB:Forwarding Information Base)作成部11と、FIB-ID探索テーブル作成部12と、テーブル探索部13と、出力ポート確認部14と、FIB-ID更新部15とを含んで構成される。
【0039】
経路テーブル(FIB)作成部11は、後記するトポロジ情報100に基づき転送経路の計算を行い、経路テーブル(FIB)200を作成する。具体的には、経路テーブル(FIB)作成部11は、トポロジ情報100に記憶される、通常のトポロジと、複数の予備トポロジに基づき、通常の経路テーブル(Primary FIB)210、および複数の予備経路テーブル(Backup FIB)220の作成を行う。
この経路テーブル(FIB)200としての通常の経路テーブル(Primary FIB)210および予備経路テーブル(Backup FIB)220には、本故障復旧システムに固有な番号であるFIB-IDが付されている。そして、各経路テーブル(FIB)200には、パケットの宛先アドレスを示すdst-IDと、出力インタフェース32である出力ポートとの対応関係を示す情報が格納される。
また、この経路テーブル(FIB)作成部11が行う処理は、既存の予備トポロジ設計アルゴリズムにより行われる。
【0040】
FIB-ID探索テーブル作成部12は、FIB-ID探索テーブル300を、最短経路探索法や、類似性判定法、故障箇所推定法を用いて作成する。
図7に示すように、FIB-ID探索テーブル300には、現時点でのパケットに付与されている経路テーブル(FIB)200のIDを示す「現FIB-ID」、送信元アドレスを示す「src-ID」、および、宛先アドレスを示す「dst-ID」が、次に選択すべき経路テーブル(FIB)200のIDを示す「次FIB-ID」に対応付けられて記憶される。
このFIB-ID探索テーブル作成部12による、FIB-ID探索テーブル300の作成法については、後記し詳細に説明する。
【0041】
図6に戻り、テーブル探索部13は、入力インタフェース(I/F)31を介してパケットを受信し、そのパケットのヘッダに付与されたFIB−IDおよび宛先アドレスを示すdst-IDを取得する。そして、テーブル探索部13は、FIB-IDを用いて、通常の経路テーブル210および予備経路テーブル220を探索し、該当するFIB−IDの経路テーブル(FIB)200を抽出し、dst-IDをキーとして、出力ポートを決定する。テーブル探索部13は、決定した出力ポートの情報を出力ポート確認部14に引き渡す。
また、テーブル探索部13は、FIB-ID更新部15から、次FIB-IDが付されたパケットを受信すると、その次FIB-IDとdst-IDとを用いて、予備経路テーブル220を探索し、出力ポートを決定する。そして、テーブル探索部13は、決定した出力ポートの情報を出力ポート確認部14に引き渡す。
【0042】
出力ポート確認部14は、テーブル探索部13から受信した出力ポートが起動しているかを確認する。つまり、そのリンクを介して正常に他のノード1に送信可能か否かを確認する。
出力ポート確認部14は、出力ポートが起動している場合には、その出力ポートへパケットを引き渡し、出力インタフェース(I/F)32を介してパケットを送信する。一方、出力ポート確認部14は、出力ポートが起動していない場合には、そのパケットをFIB-ID更新部15に引き渡す。
【0043】
FIB-ID更新部15は、出力ポート確認部14から、パケットを受信すると、そのパケットのヘッダから、現FIB-ID、src-ID、dst-IDを取得し、これらをキーとして、FIB-ID探索テーブル300を探索し、更新後のFIB-IDである次FIB-IDを取得する。
そして、FIB-ID更新部15は、取得した次FIB-IDを付したパケットを、テーブル探索部13に引き渡す。
【0044】
また、記憶部には、トポロジ情報100と、経路テーブル(FIB)200と、FIB-ID探索テーブル300とを含む情報が記憶される。図7は、記憶部に記憶される各情報についての、データ構成(情報要素)と、その取得・生成方法を示している。
ここで、トポロジ情報100は、通信ネットワーク1000内の各ノード1間のリンクによる接続関係を示し、経路テーブル(FIB)作成部11が、OSPF等のルーチングプロトコルを用いて取得する。また、このトポロジ情報100には、経路テーブル(FIB)作成部11が、既存の予備トポロジ設計アルゴリズムにより生成した予備トポロジが記憶される。なお、経路テーブル(FIB)200およびFIB-ID探索テーブル300については、既に説明を行っているので、ここでは説明を省略する。
【0045】
そして、この記憶部は、RAM(Random Access Memory)や、HDD(Hard Dick Drive)、フラッシュメモリ等の記憶媒体から構成される。ノード1をプログラム実行処理により実現する場合、記憶部には、ノード1の制御部の機能を実現するためのプログラムが格納される。そして、制御部は、記憶部に記憶されたプログラムを、不図示のCPU(Central Processing Unit)が、RAM等に展開し実行することで実現される。
【0046】
≪FIB-ID探索テーブルの作成方法≫
次に、本実施形態に係る故障復旧システムの各ノード1が、パケット転送の処理前に事前に行っておく、FIB-ID探索テーブル300の作成処理について説明する。
FIB-ID探索テーブル300は、前記したように、現時点でのパケットに付与されている経路テーブル(FIB)200のIDを示す「現FIB-ID」、送信元アドレスを示す「src-ID」、および、宛先アドレスを示す「dst-ID」が、次に選択すべき経路テーブル(FIB)200のIDを示す「次FIB-ID」に対応付けられて記憶される情報である。
各ノード1のFIB-ID探索テーブル作成部12は、FIB-ID探索テーブル300を、最短経路探索法、類似性判定法、故障箇所推定法を用いて作成する。
【0047】
(最短経路探索法)
まず、1番目の故障リンクの検出時の予備トポロジを決定し、FIB-ID探索テーブル300を作成するために用いる、最短経路探索法について説明する。
【0048】
最短経路探索法(Shortest Method)は、検出した故障リンクをプロテクトしつつ、予備経路の経路長が最短となる予備トポロジを選択する方法である。予備経路の経路長は、パケットのヘッダに付与された宛先ノードの情報をもとに、各予備トポロジにおいて、故障検出ノードから宛先ノードまでの経路を計算することにより算出される。
【0049】
まず、FIB-ID探索テーブル作成部12は、1番目の故障リンクをプロテクトする予備経路を、故障検出ノードから宛先ノードまでの経路長が最短となる予備トポロジを探索することにより決定し、その予備トポロジにより作成された予備経路テーブル(Backup FIB)220のFIB-IDを取得する。
そして、FIB-ID探索テーブル作成部12は、FIB-ID探索テーブル300の「現FIB-ID」に、通常の経路テーブル(Primary FIB)210のFIB-IDを格納し、「次FIB-ID」に、経路長が最短となる予備経路テーブル(Backup FIB)220のFIB-IDを格納して、src-ID、dst-IDを含めた、FIB-ID探索テーブル300を作成する。
【0050】
次に、FIB-ID探索テーブル作成部12は、2番目の故障リンクの検出時に備えたFIB-ID探索テーブル300を、類似性判定法、または、故障箇所推定法を用いて作成する。なお、2番目の故障検出時に備えたFIB-ID探索テーブル300の作成を、最短経路探索法を用いて行ってもよいが、以下に説明する、類似性判定法、故障箇所推定法に比べると、転送ループの発生する確率を低下させる効果は低いものとなる。
【0051】
(類似性判定法)
類似性判定法(Similarity Method)は、2番目に検出した故障リンクをプロテクトしつつ、1番目に選択した予備トポロジとの類似性が最大となる予備トポロジを、2番目の故障検出時に備えた予備トポロジとして選択する。ここで、類似性とは、全プロテクトリンク数に対し、同一のリンクをプロテクトしている数の割合として定義される。この類似性判定法の基本的な考え方は、類似性の高い2つの予備トポロジは、提供する経路に関しても類似性が高いと考えられるため、1番目の故障リンクをプロテクトするために選ばれた予備トポロジに類似する予備トポロジは、同様に1番目の故障リンクをプロテクトしている確率が高いとの考えに基づく。
【0052】
この類似性判定法に基づく、2番目の故障検出時に備えたFIB-ID探索テーブル300の作成法を、図8を参照して説明する。図8は、本実施形態に係る類似判定法によるFIB-ID探索テーブル300の作成処理を示すフローチャートである。
【0053】
まず、FIB-ID探索テーブル作成部12は、1番目の故障検出時に備えて作成されたFIB-ID探索テーブル300内の「次FIB-ID」を抽出する(ステップS101)。
【0054】
次に、FIB-ID探索テーブル作成部12は、トポロジ情報100に記憶されている予備トポロジ全体の中から、2番目の故障リンクをプロテクトする予備トポロジ(「第2の予備トポロジ」と呼ぶ)を抽出する(ステップS102)。
【0055】
そして、FIB-ID探索テーブル作成部12は、ステップS101において「次FIB-ID」として抽出されたFIB-IDの予備トポロジ(「第1の予備トポロジ」と呼ぶ)と、ステップS102で抽出された第2の予備トポロジとの類似性を判定し、第2の予備トポロジのうち最も類似性が高い、つまり、全プロテクトリンク数に対し、同一のリンクをプロテクトしている数の割合が最も高い第2の予備トポロジを選択する(ステップS103)。
【0056】
続いて、FIB-ID探索テーブル作成部12は、FIB-ID探索テーブル300の「現FIB-ID」に、第1の予備トポロジのFIB-IDを格納し、「次FIB-ID」に、最も類似性の高い第2の予備トポロジのFIB-IDを格納して、src-ID、dst-IDを含めた、FIB-ID探索テーブル300を作成する(ステップS104)。
【0057】
このようにして、FIB-ID探索テーブル作成部12は、パケットの転送処理を実行する前に、FIB-ID探索テーブル300を、類似性判定法に基づき作成することができる。
【0058】
(故障箇所推定法)
故障箇所推定法(Estimation Method)は、2番目に検出した故障リンクをプロテクトしつつ、1番目の故障リンク位置を推定することで、転送ループが最も発生しにくい予備トポロジを選択する方法である。
【0059】
この故障箇所推定法に基づく、2番目の故障検出時に備えたFIB-ID探索テーブル300の作成法を、図9および図10を参照して説明する。図9は、本実施形態に係る故障箇所推定法によるFIB-ID探索テーブル300の作成処理を示すフローチャートである。図10は、本実施形態に係る故障箇所推定法の概要を説明するための図である。なお、図10においては、図3および図4で示したリンク故障x,yの例とは、別の例として説明する。
【0060】
図9に示すように、まず、FIB-ID探索テーブル作成部12は、パケットのヘッダに付与される、送信元アドレスを示す「src-ID」と、宛先アドレスを示す「dst-ID」から、故障が発生する前の最短経路を計算する。そして、その最短経路を構成するリンクの集合を「E1」として抽出する(ステップS201)。
図10(a)に示す例では、最短経路「1」−「4」−「7」が計算され、そのリンク集合「E1」として、リンク1−4,4−7が抽出される。
【0061】
次に、FIB-ID探索テーブル作成部12は、1番目の故障検出時に備えて作成されたFIB-ID探索テーブル300内の「次FIB-ID」を抽出し、「次FIB-ID」として抽出されたFIB-IDの予備トポロジ(第1の予備トポロジ)上のプロテクトリンクの集合を「E2」として抽出する(ステップS202)。
図10(b)に示す例では、予備トポロジ#1のプロテクトリンクの集合「E2」として、リンク1−2,1−6,2−3,2−4,3−8,4−7,7−8が抽出される。
【0062】
続いて、FIB-ID探索テーブル作成部12は、「E1」と「E2」の論理積をとった積集合を「E3」として抽出する(ステップS203)。この「E3」が推定故障リンクの集合となる。
図10に示す例では、「E1」と「E2」の積集合はリンク4−7となり、故障箇所が推定される。なお、図10の例では、故障箇所が1つ推定されるが、複数推定される場合もある。
【0063】
そして、FIB-ID探索テーブル作成部12は、トポロジ情報100に記憶されている予備トポロジ全体の中から、2番目の故障リンクをプロテクトする予備トポロジ(第2の予備トポロジ)を抽出する(ステップS204)。
【0064】
続いて、FIB-ID探索テーブル作成部12は、ステップS203の推定故障リンクで故障が発生したと想定し、ステップS204で抽出した第2の予備トポロジの1つを選択した場合に、転送ループが発生するか否かを評価する(ステップS205)。
ここでは、FIB-ID探索テーブル作成部12は、抽出した第2の予備トポロジ毎に、転送ループが発生しない場合の評価値を「0」、転送ループが1箇所発生する場合の評価値を「1」、転送ループが2箇所発生する場合の評価値を「2」等のようにし、結果として、最も転送ループの発生に関する評価値の値が小さい第2の予備トポロジを選択する。なお、ステップS203において、推定故障リンクが複数抽出される場合があるため、転送ループが複数の箇所で発生するとの評価される場合がある。
【0065】
次に、FIB-ID探索テーブル作成部12は、評価値の値が最も小さい第2の予備トポロジを選択する(ステップS206)。
【0066】
そして、FIB-ID探索テーブル300の「現FIB-ID」に、第1の予備トポロジのFIB-IDを格納し、「次FIB-ID」に、最も評価値の値が小さい第2の予備トポロジのFIB-IDを格納して、src-ID、dst-IDを含めた、FIB-ID探索テーブル300を作成する(ステップS207)。
【0067】
このようにして、FIB-ID探索テーブル作成部12は、パケットの転送処理を実行する前に、FIB-ID探索テーブル300を、故障箇所推定法に基づき作成することができる。
【0068】
≪故障箇所復旧方法の全体の処理≫
次に、本実施形態に係る故障復旧システムにおける、故障復旧方法の全体の処理の流れを説明する(適宜図6参照)。
図11は、本実施形態に係る故障復旧方法の全体の処理の流れを示すフローチャートである。
【0069】
まず、経路テーブル(FIB)作成部11は、トポロジ情報100に基づき転送経路の計算を行い、通常の経路テーブル(Primary FIB)210、および予備経路テーブル(Backup FIB)220の作成を行う(ステップS301)。
【0070】
次に、FIB-ID探索テーブル作成部12は、最短経路探索法と、類似性判定法、故障箇所推定法のいずれかを用いて、FIB-ID探索テーブル300を作成する(ステップS302)。
FIB-ID探索テーブル作成部12が、FIB-ID探索テーブル300の作成の際に、類似性判定法、故障箇所推定法のいずれを用いるかは、ネットワーク管理者等により任意に設定されるが、類似性判定法の方が、故障箇所推定法に比べ処理負荷が少ないが、故障箇所推定法の方が、類似性判定法に比べ、転送ループの発生する確率をより低下させることができるという特徴がある。
【0071】
このステップS301とステップS302の処理は、パケット転送処理の前に各ノード1が予め計算しておく処理である。つまり、パケット転送時にリアルタイムで実行される計算ではないため、処理負荷の影響を考慮する必要はない。
【0072】
そして、ノード1のテーブル探索部13は、入力インタフェース(I/F)31を介して、パケットを受信すると、パケットのヘッダに付されたFIB-IDおよびdst-ID(宛先アドレス)をキーとして、通常の経路テーブル(Primary FIB)210、および予備経路テーブル(Backup FIB)220を探索し、出力ポートを取得する(ステップ303)。
【0073】
次に、出力ポート確認部14は、出力ポートが起動しているか否かを確認する(ステップS304)。出力ポート確認部14は、出力ポートが起動している場合には(ステップS304→Yes)、その出力ポートへパケットを引き渡し、出力インタフェース(I/F)32を介して、パケットを送信して(ステップS305)、処理を終える。
【0074】
一方、出力ポート確認部14は、出力ポートが起動していない場合には(ステップS304→No)、次のステップS306に進む。
【0075】
ステップS306において、出力ポート確認部14は、そのパケットをFIB-ID更新部15に引き渡す。
【0076】
続いて、FIB-ID更新部15は、出力ポート確認部14から、パケットを受信すると、そのパケットのヘッダ情報から、現FIB-ID、src-ID、dst-IDを取得し、これらをキーとして、FIB-ID探索テーブル300を探索し、更新後のFIB-IDである次FIB-IDを取得する(ステップS307)。そして、FIB-ID更新部15は、取得した次FIB-IDを付したパケットを、テーブル探索部13に引き渡し、ステップS303に戻る。
【0077】
そして、テーブル探索部13が、FIB-ID更新部15から次FIB-IDが付されたパケットを受信すると、その次FIB-IDとdst-IDとを用いて、予備経路テーブル220を探索し、出力ポートを決定する。そして、テーブル探索部13は、決定した出力ポートの情報を出力ポート確認部14に引き渡し、ステップS304以降の処理を続ける。
【0078】
以上説明したように、本実施形態に係る故障復旧システム、ノード、故障復旧方法およびプログラムによれば、パケット交換網の多重故障復旧時に発生していた転送ループについて、類似性判定法や、故障箇所推定法を用いたFIB-ID探索テーブル300を予め作成しておき、2番目の故障に対して適切な予備トポロジを、FIB-ID探索テーブル300を参照して選択することで、転送ループの発生する確率を低下させることができる。
【0079】
≪変形例≫
本実施形態に係る故障復旧システムとしての通信ネットワーク1000は、図5に示したように、通信ネットワーク1000内のノードそれぞれが、故障回復機能を備える構成とした。しかし、本発明はこれに限定されず、例えば、図12に示すように、故障復旧サーバ1100を、ネットワーク情報取得装置1200を介して通信ネットワーク1000に接続する構成にすることもできる。
【0080】
この場合、故障復旧サーバ1100が、経路テーブル(FIB)作成部11とFIB-ID探索テーブル作成部12とを備え、ネットワーク情報取得装置1200を介して、各ノード間のトポロジ情報100を取得する。そして、故障復旧サーバ1100が、経路テーブル(FIB)200およびFIB-ID探索テーブル300を作成し、各ノード1aに対して、パケット転送処理の開始前に配信するようにしてもよい。
【符号の説明】
【0081】
1 ノード
11 経路テーブル(FIB)作成部
12 FIB-ID探索テーブル作成部
13 テーブル探索部
14 出力ポート確認部
15 FIB-ID更新部
31 入力インタフェース(I/F)
32 出力インタフェース(I/F)
100 トポロジ情報
200 経路テーブル(FIB)
210 通常の経路テーブル(Primary FIB)
220 予備経路テーブル(Backup FIB)
300 FIB-ID探索テーブル
1000 通信ネットワーク
1100 故障復旧サーバ
1200 ネットワーク情報取得装置
【特許請求の範囲】
【請求項1】
複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムであって、
前記故障復旧システムの各ノードは、
パケットを送受信する通信部と、
前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部と、
前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すdst-IDと、出力ポートとを対応付けた経路テーブル(FIB)を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル(FIB)の識別子であるFIB-IDに対応付けて作成する経路テーブル(FIB)作成部と、
1番目の前記故障リンクをプロテクトする前記予備トポロジを示す第1の予備トポロジの現FIB−IDと、前記パケットの送信元アドレスを示すsrc-IDと、前記dst-IDとを、2番目の前記故障リンクをプロテクトする前記予備トポロジを示す第2の予備トポロジの前記FIB-IDであり、前記第1の予備トポロジに基づき選択された次FIB-IDに対応付けたFIB-ID探索テーブルを作成するFIB-ID探索テーブル作成部と、
前記FIB-ID、前記src-IDおよび前記dst-IDが付された前記パケットを、前記通信部を介して受信し、前記FIB-IDをキーとして、前記経路テーブル(FIB)を探索し、前記出力ポートを取得するテーブル探索部と、
前記出力ポートが起動しているか否かを判定し、前記起動していると判定した場合には、当該出力ポートから前記パケットを送信し、前記起動してないと判定した場合には、前記パケットをFIB-ID更新部に引き渡す出力ポート確認部と、
前記パケットに付された前記FIB-ID、前記src-IDおよび前記dst-IDに基づき、前記パケットに付された前記FIB-IDを前記現FIB-IDとして、前記FIB-ID探索テーブルを探索し、前記次FIB-IDを取得し、当該次FIB-IDを付した前記パケットを、前記テーブル探索部に引き渡す前記FIB-ID更新部と、を備え、
前記テーブル探索部は、
前記次FIB-IDが付されたパケットを受信すると、前記次FIB-IDをキーとして前記経路テーブル(FIB)を探索し、前記出力ポートを取得して、前記出力ポート確認部に引き渡すこと
を特徴とする故障復旧システム。
【請求項2】
前記FIB-ID探索テーブル作成部は、前記FIB-ID探索テーブルの作成の際に行う、前記第1の予備トポロジに基づく前記次FIB-IDの選択において、
前記2番目の故障リンクをプロテクトする前記予備トポロジとして抽出される1つ以上の前記第2の予備トポロジについて、全プロテクトリンク数に対し、前記第1の予備トポロジがプロテクトしているリンクと同一のリンクをプロテクトしている数の割合を示す類似性を計算し、前記第2の予備トポロジのうち、前記類似性の最も高い前記第2の予備トポロジを抽出し、そのFIB-IDを次FIB-IDとして選択すること
を特徴とする請求項1に記載の故障復旧システム。
【請求項3】
前記FIB-ID探索テーブル作成部は、前記FIB-ID探索テーブルの作成の際に行う、前記第1の予備トポロジに基づく前記次FIB-IDの選択において、
前記パケットに付された前記src-IDおよび前記dst-IDに基づき、故障発生前の最短経路を計算し、その最短経路上のリンクを抽出し、
前記1番目の前記故障リンクをプロテクトする前記第1の予備トポロジのプロテクトリンクを抽出し、
前記最短経路上のリンクと前記第1の予備トポロジのプロテクトリンクとに重複するリンクを、推定故障リンクとして抽出し、
前記抽出した推定故障リンクと、前記2番目の故障リンクをプロテクトする前記予備トポロジとして抽出される1つ以上の前記第2の予備トポロジについて、転送ループが発生するか否かを判定し、前記第2の予備トポロジのうち、前記転送ループの発生が最も少ない前記第2の予備トポロジを抽出し、そのFIB-IDを次FIB-IDとして選択すること
を特徴とする請求項1に記載の故障復旧システム。
【請求項4】
複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムの前記ノードであって、
パケットを送受信する通信部と、
前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部と、
前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すdst-IDと、出力ポートとを対応付けた経路テーブル(FIB)を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル(FIB)の識別子であるFIB-IDに対応付けて作成する経路テーブル(FIB)作成部と、
1番目の前記故障リンクをプロテクトする前記予備トポロジを示す第1の予備トポロジの現FIB−IDと、前記パケットの送信元アドレスを示すsrc-IDと、前記dst-IDとを、2番目の前記故障リンクをプロテクトする前記予備トポロジを示す第2の予備トポロジの前記FIB-IDであり、前記第1の予備トポロジに基づき選択された次FIB-IDに対応付けたFIB-ID探索テーブルを作成するFIB-ID探索テーブル作成部と、
前記FIB-ID、前記src-IDおよび前記dst-IDが付された前記パケットを、前記通信部を介して受信し、前記FIB-IDをキーとして、前記経路テーブル(FIB)を探索し、前記出力ポートを取得するテーブル探索部と、
前記出力ポートが起動しているか否かを判定し、前記起動していると判定した場合には、当該出力ポートから前記パケットを送信し、前記起動してないと判定した場合には、前記パケットをFIB-ID更新部に引き渡す出力ポート確認部と、
前記パケットに付された前記FIB-ID、前記src-IDおよび前記dst-IDに基づき、前記パケットに付された前記FIB-IDを前記現FIB-IDとして、前記FIB-ID探索テーブルを探索し、前記次FIB-IDを取得し、当該次FIB-IDを付した前記パケットを、前記テーブル探索部に引き渡す前記FIB-ID更新部と、を備え、
前記テーブル探索部は、
前記次FIB-IDが付されたパケットを受信すると、前記次FIB-IDをキーとして前記経路テーブル(FIB)を探索し、前記出力ポートを取得して、前記出力ポート確認部に引き渡すこと
を特徴とするノード。
【請求項5】
複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムの故障復旧方法であって、
前記故障復旧システムのノードは、
前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部を備えており、
前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すdst-IDと、出力ポートとを対応付けた経路テーブル(FIB)を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル(FIB)の識別子であるFIB-IDに対応付けて作成するステップと、
1番目の前記故障リンクをプロテクトする前記予備トポロジを示す第1の予備トポロジの現FIB−IDと、前記パケットの送信元アドレスを示すsrc-IDと、前記dst-IDとを、2番目の前記故障リンクをプロテクトする前記予備トポロジを示す第2の予備トポロジの前記FIB-IDであり、前記第1の予備トポロジに基づき選択された次FIB-IDに対応付けたFIB-ID探索テーブルを作成するステップと、
前記FIB-ID、前記src-IDおよび前記dst-IDが付された前記パケットを受信し、前記FIB-IDをキーとして、前記経路テーブル(FIB)を探索し、前記出力ポートを取得するステップと、
前記出力ポートが起動しているか否かを判定し、前記出力ポートが起動していると判定した場合に、当該出力ポートから前記パケットを送信するステップと、
前記出力ポートが起動してないと判定した場合に、前記パケットに付された前記FIB-ID、前記src-IDおよび前記dst-IDに基づき、前記パケットに付された前記FIB-IDを前記現FIB-IDとして、前記FIB-ID探索テーブルを探索し、前記次FIB-IDを取得するステップと、
前記次FIB-IDを付した前記パケットを受信し、当該次FIB-IDをキーとして前記経路テーブル(FIB)を探索し、前記出力ポートを取得して、当該取得した出力ポートが起動しているか否かを判定して、前記パケットの送信するステップ、または、前記次FIB-IDを取得するステップを実行すること
を特徴とする故障復旧方法。
【請求項6】
請求項5に記載の故障復旧方法を、コンピュータである前記ノードに実行させるためのプログラム。
【請求項1】
複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムであって、
前記故障復旧システムの各ノードは、
パケットを送受信する通信部と、
前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部と、
前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すdst-IDと、出力ポートとを対応付けた経路テーブル(FIB)を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル(FIB)の識別子であるFIB-IDに対応付けて作成する経路テーブル(FIB)作成部と、
1番目の前記故障リンクをプロテクトする前記予備トポロジを示す第1の予備トポロジの現FIB−IDと、前記パケットの送信元アドレスを示すsrc-IDと、前記dst-IDとを、2番目の前記故障リンクをプロテクトする前記予備トポロジを示す第2の予備トポロジの前記FIB-IDであり、前記第1の予備トポロジに基づき選択された次FIB-IDに対応付けたFIB-ID探索テーブルを作成するFIB-ID探索テーブル作成部と、
前記FIB-ID、前記src-IDおよび前記dst-IDが付された前記パケットを、前記通信部を介して受信し、前記FIB-IDをキーとして、前記経路テーブル(FIB)を探索し、前記出力ポートを取得するテーブル探索部と、
前記出力ポートが起動しているか否かを判定し、前記起動していると判定した場合には、当該出力ポートから前記パケットを送信し、前記起動してないと判定した場合には、前記パケットをFIB-ID更新部に引き渡す出力ポート確認部と、
前記パケットに付された前記FIB-ID、前記src-IDおよび前記dst-IDに基づき、前記パケットに付された前記FIB-IDを前記現FIB-IDとして、前記FIB-ID探索テーブルを探索し、前記次FIB-IDを取得し、当該次FIB-IDを付した前記パケットを、前記テーブル探索部に引き渡す前記FIB-ID更新部と、を備え、
前記テーブル探索部は、
前記次FIB-IDが付されたパケットを受信すると、前記次FIB-IDをキーとして前記経路テーブル(FIB)を探索し、前記出力ポートを取得して、前記出力ポート確認部に引き渡すこと
を特徴とする故障復旧システム。
【請求項2】
前記FIB-ID探索テーブル作成部は、前記FIB-ID探索テーブルの作成の際に行う、前記第1の予備トポロジに基づく前記次FIB-IDの選択において、
前記2番目の故障リンクをプロテクトする前記予備トポロジとして抽出される1つ以上の前記第2の予備トポロジについて、全プロテクトリンク数に対し、前記第1の予備トポロジがプロテクトしているリンクと同一のリンクをプロテクトしている数の割合を示す類似性を計算し、前記第2の予備トポロジのうち、前記類似性の最も高い前記第2の予備トポロジを抽出し、そのFIB-IDを次FIB-IDとして選択すること
を特徴とする請求項1に記載の故障復旧システム。
【請求項3】
前記FIB-ID探索テーブル作成部は、前記FIB-ID探索テーブルの作成の際に行う、前記第1の予備トポロジに基づく前記次FIB-IDの選択において、
前記パケットに付された前記src-IDおよび前記dst-IDに基づき、故障発生前の最短経路を計算し、その最短経路上のリンクを抽出し、
前記1番目の前記故障リンクをプロテクトする前記第1の予備トポロジのプロテクトリンクを抽出し、
前記最短経路上のリンクと前記第1の予備トポロジのプロテクトリンクとに重複するリンクを、推定故障リンクとして抽出し、
前記抽出した推定故障リンクと、前記2番目の故障リンクをプロテクトする前記予備トポロジとして抽出される1つ以上の前記第2の予備トポロジについて、転送ループが発生するか否かを判定し、前記第2の予備トポロジのうち、前記転送ループの発生が最も少ない前記第2の予備トポロジを抽出し、そのFIB-IDを次FIB-IDとして選択すること
を特徴とする請求項1に記載の故障復旧システム。
【請求項4】
複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムの前記ノードであって、
パケットを送受信する通信部と、
前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部と、
前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すdst-IDと、出力ポートとを対応付けた経路テーブル(FIB)を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル(FIB)の識別子であるFIB-IDに対応付けて作成する経路テーブル(FIB)作成部と、
1番目の前記故障リンクをプロテクトする前記予備トポロジを示す第1の予備トポロジの現FIB−IDと、前記パケットの送信元アドレスを示すsrc-IDと、前記dst-IDとを、2番目の前記故障リンクをプロテクトする前記予備トポロジを示す第2の予備トポロジの前記FIB-IDであり、前記第1の予備トポロジに基づき選択された次FIB-IDに対応付けたFIB-ID探索テーブルを作成するFIB-ID探索テーブル作成部と、
前記FIB-ID、前記src-IDおよび前記dst-IDが付された前記パケットを、前記通信部を介して受信し、前記FIB-IDをキーとして、前記経路テーブル(FIB)を探索し、前記出力ポートを取得するテーブル探索部と、
前記出力ポートが起動しているか否かを判定し、前記起動していると判定した場合には、当該出力ポートから前記パケットを送信し、前記起動してないと判定した場合には、前記パケットをFIB-ID更新部に引き渡す出力ポート確認部と、
前記パケットに付された前記FIB-ID、前記src-IDおよび前記dst-IDに基づき、前記パケットに付された前記FIB-IDを前記現FIB-IDとして、前記FIB-ID探索テーブルを探索し、前記次FIB-IDを取得し、当該次FIB-IDを付した前記パケットを、前記テーブル探索部に引き渡す前記FIB-ID更新部と、を備え、
前記テーブル探索部は、
前記次FIB-IDが付されたパケットを受信すると、前記次FIB-IDをキーとして前記経路テーブル(FIB)を探索し、前記出力ポートを取得して、前記出力ポート確認部に引き渡すこと
を特徴とするノード。
【請求項5】
複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムの故障復旧方法であって、
前記故障復旧システムのノードは、
前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部を備えており、
前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すdst-IDと、出力ポートとを対応付けた経路テーブル(FIB)を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル(FIB)の識別子であるFIB-IDに対応付けて作成するステップと、
1番目の前記故障リンクをプロテクトする前記予備トポロジを示す第1の予備トポロジの現FIB−IDと、前記パケットの送信元アドレスを示すsrc-IDと、前記dst-IDとを、2番目の前記故障リンクをプロテクトする前記予備トポロジを示す第2の予備トポロジの前記FIB-IDであり、前記第1の予備トポロジに基づき選択された次FIB-IDに対応付けたFIB-ID探索テーブルを作成するステップと、
前記FIB-ID、前記src-IDおよび前記dst-IDが付された前記パケットを受信し、前記FIB-IDをキーとして、前記経路テーブル(FIB)を探索し、前記出力ポートを取得するステップと、
前記出力ポートが起動しているか否かを判定し、前記出力ポートが起動していると判定した場合に、当該出力ポートから前記パケットを送信するステップと、
前記出力ポートが起動してないと判定した場合に、前記パケットに付された前記FIB-ID、前記src-IDおよび前記dst-IDに基づき、前記パケットに付された前記FIB-IDを前記現FIB-IDとして、前記FIB-ID探索テーブルを探索し、前記次FIB-IDを取得するステップと、
前記次FIB-IDを付した前記パケットを受信し、当該次FIB-IDをキーとして前記経路テーブル(FIB)を探索し、前記出力ポートを取得して、当該取得した出力ポートが起動しているか否かを判定して、前記パケットの送信するステップ、または、前記次FIB-IDを取得するステップを実行すること
を特徴とする故障復旧方法。
【請求項6】
請求項5に記載の故障復旧方法を、コンピュータである前記ノードに実行させるためのプログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【公開番号】特開2013−74448(P2013−74448A)
【公開日】平成25年4月22日(2013.4.22)
【国際特許分類】
【出願番号】特願2011−211781(P2011−211781)
【出願日】平成23年9月28日(2011.9.28)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【出願人】(899000068)学校法人早稲田大学 (602)
【Fターム(参考)】
【公開日】平成25年4月22日(2013.4.22)
【国際特許分類】
【出願日】平成23年9月28日(2011.9.28)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【出願人】(899000068)学校法人早稲田大学 (602)
【Fターム(参考)】
[ Back to top ]