(57)【特許請求の範囲】
【請求項１】
ネットワークを構成する装置間の接続関係を報告し合うことによって自律分散的にルーティングテーブルを作成するルーティング処理手段を含むパケット転送経路制御装置であって、
前記装置間を接続する個別リンクを介して隣接装置との接続情報を学習するためのハローメッセージを交換して前記隣接装置を特定する隣接装置識別子及び前記隣接装置に接続するための隣接個別リンクを特定する隣接個別リンク識別子を学習する個別リンク管理手段と、同一の隣接装置識別子を持つ複数の個別リンクを１つの集約リンクとして管理して前記ルーティング処理手段に通知する集約リンク管理手段とを有し、
前記ルーティング処理手段は、前記集約リンク単位で処理を行い、
前記集約リンク管理手段は、前記同一の隣接装置識別子を持つ複数の個別リンクのうちの各個別リンク毎に予め設定された設定情報が同一の個別リンクを１つの集約リンクとして管理するようにし、
前記設定情報が少なくとも管理上のグループを示すグループ識別子及び各個別リンク毎の優先度を示す優先度情報のいずれかを含むことを特徴とするパケット転送経路制御装置。
【請求項２】
前記個別リンクの帯域幅を示す情報を前記設定情報として設定するようにしたことを特徴とする請求項１記載のパケット転送経路制御装置。
【請求項３】
前記個別リンク管理手段は、前記集約リンク毎に設定されたインタフェースＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）アドレスを前記個別リンクを介して交換するよう構成したことを特徴とする請求項１または請求項２記載のパケット転送経路制御装置。
【請求項４】
前記インタフェースＩＰアドレスは、前記隣接装置識別子で規定されることを特徴とする請求項３記載のパケット転送経路制御装置。
【請求項５】
前記隣接装置は、ルータからなり、前記ルータと前記インタフェースＩＰアドレスを交換するようにしたことを特徴とする請求項３または請求項４記載のパケット転送経路制御装置。
【請求項６】
前記隣接装置は、ＯＸＣ（Ｏｐｔｉｃａｌ  Ｃｒｏｓｓ  Ｃｏｎｎｅｃｔ）からなり、前記ＯＸＣと前記インタフェースＩＰアドレスを交換するようにしたことを特徴とする請求項３または請求項４記載のパケット転送経路制御装置。
【請求項７】
前記個別リンク各々に送信側と受信側とで同一の値となる共通リンク識別子を設定し、その共通リンク識別子を、波長パスの設定要求を行うためのシグナリンクメッセージに挿入するようにしたことを特徴とする請求項６記載のパケット転送経路制御装置。
【請求項８】
前記集約リンクを構成する個別リンクの合計帯域を示す情報を個別リンク数に関係なく一定とするために、その情報に固定値を設定するようにしたことを特徴とする請求項６または請求項７記載の記載のパケット転送経路制御装置。
【請求項９】
前記集約リンクと当該集約リンクを構成する個別リンクのリストとを対応付けて格納するリンクマッピングテーブルを含み、
パケット受信時に前記リンクマッピングテーブルから前記集約リンクを構成する個別リンクの１つを選択してパケット転送を行い、
前記リンクマッピングテーブルにおいて、前記集約リンクに対応する当該集約リンクを構成する個別リンクのリストに記載された個別リンクのそれぞれに設定された分散係数にしたがって負荷分割パケット転送を行うようにしたことを特徴とする請求項１から請求項８のいずれか記載のパケット転送経路制御装置。
【請求項１０】
前記分散係数の設定は、前記個別リンク毎の帯域比及び前記個別リンク毎の前記分散係数のパラメータのいずれかを設定するようにしたことを特徴とする請求項９記載のパケット転送経路制御装置。
【請求項１１】
前記個別リンク管理手段は、前記ハローメッセージに前記個別リンクのインタフェース識別子を格納することで互いのインタフェース識別子を学習し合うようにしたことを特徴とする請求項１から請求項１０のいずれか記載のパケット転送経路制御装置。
【請求項１２】
請求項１１記載のパケット転送経路制御装置を具備し、各個別リンク毎にスイッチングを行うクロスコネクト装置において、前記個別リンク管理手段は、前記個別リンクが使用中であるかどうかを管理し、シグナリング要求メッセージを受信した際に転送先の集約リンクを特定し、当該集約リンクを構成する個別リンクの中で使用中でない個別リンクを選択するようにしたことを特徴とするパケット転送経路制御装置。
【請求項１３】
前記シグナリング要求メッセージを受信した際に、当該シグナリング要求メッセージ内の送信個別リンク識別子を参照し、その送信個別リンク識別子及び受信した集約リンクの前記インタフェース識別子を基に自装置に蓄積する隣接装置個別リンク識別子に一致する個別リンクを探索することで、どのリンクに対するシグナリング要求であるかを認識するようにしたことを特徴とする請求項１２記載のパケット転送経路制御装置。
【請求項１４】
前記送信個別リンク識別子に対応する隣接ルータリンク識別子を予め個別リンク管理テーブルから検索し、当該隣接ルータリンク識別子を宛先個別リンク識別子として前記シグナリング要求メッセージに挿入するようにしたことを特徴とする請求項１２記載のパケット転送経路制御装置。
【請求項１５】
前記個別リンク各々に送信側と受信側とで同一の値となる共通リンク識別子を設定し、その共通リンク識別子を前記シグナリンク要求メッセージに挿入するようにしたことを特徴とする請求項１２記載のパケット転送経路制御装置。
【請求項１６】
前記共通リンク識別子は、前記送信側及び前記受信側各々の個別リンク識別子のうちの大きい方の値を使用するようにしたことを特徴とする請求項１５記載のパケット転送経路制御装置。
【請求項１７】
転送先として選択した個別リンクの隣接個別リンク識別子を読出して前記シグナリング要求メッセージによって前記隣接装置に通知するようにしたことを特徴とする請求項１２記載のパケット転送経路制御装置。
【請求項１８】
前記ルーティングテーブルは、リンクステート型のルーティングプロトコルに用いられるリンクステートルーティングテーブルであることを特徴とする請求項１から請求項１７のいずれか記載のパケット転送経路制御装置。
【請求項１９】
ネットワークを構成する装置間の接続関係を報告し合うことによって自律分散的にルーティングテーブルを作成するルーティング処理手段を含むパケット転送経路制御装置のパケット転送経路制御方法であって、
前記装置間を接続する個別リンクを介して隣接装置との接続情報を学習するためのハローメッセージを交換して前記隣接装置を特定する隣接装置識別子及び前記隣接装置に接続するための隣接個別リンクを特定する隣接個別リンク識別子を学習し、同一の隣接装置識別子を持つ複数の個別リンクを１つの集約リンクとして管理して前記ルーティング処理手段に通知するとともに、前記ルーティング処理手段は前記集約リンク単位で処理を行い、
前記集約リンクとして管理する際に、前記同一の隣接装置識別子を持つ複数の個別リンクのうちの各個別リンク毎に予め設定された設定情報が同一の個別リンクを１つの集約リンクとして管理するようにし、
前記設定情報が少なくとも管理上のグループを示すグループ識別子及び各個別リンク毎の優先度を示す優先度情報のいずれかを含むことを特徴とするパケット転送経路制御方法。
【請求項２０】
前記個別リンクの帯域幅を示す情報を前記設定情報として設定するようにしたことを特徴とする請求項１９記載のパケット転送経路制御方法。
【請求項２１】
前記隣接装置識別子及び前記隣接個別リンク識別子を学習する際に、前記集約リンク毎に設定されたインタフェースＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）アドレスを前記個別リンクを介して交換するようにしたことを特徴とする請求項１９から請求項２０のいずれか記載のパケット転送経路制御方法。
【請求項２２】
前記インタフェースＩＰアドレスは、前記隣接装置識別子で規定されることを特徴とする請求項２１記載のパケット転送経路制御方法。
【請求項２３】
前記隣接装置は、ルータからなり、前記ルータと前記インタフェースＩＰアドレスを交換するようにしたことを特徴とする請求項２１または請求項２２記載のパケット転送経路制御方法。
【請求項２４】
前記隣接装置は、ＯＸＣ（Ｏｐｔｉｃａｌ  Ｃｒｏｓｓ  Ｃｏｎｎｅｃｔ）からなり、前記ＯＸＣと前記インタフェースＩＰアドレスを交換するようにしたことを特徴とする請求項２１または請求項２２記載のパケット転送経路制御方法。
【請求項２５】
前記個別リンク各々に送信側と受信側とで同一の値となる共通リンク識別子を設定し、その共通リンク識別子を、波長パスの設定要求を行うためのシグナリンクメッセージに挿入するようにしたことを特徴とする請求項２４記載のパケット転送経路制御方法。
【請求項２６】
前記集約リンクを構成する個別リンクの合計帯域を示す情報を個別リンク数に関係なく一定とするために、その情報に固定値を設定するようにしたことを特徴とする請求項２４または請求項２５記載の記載のパケット転送経路制御方法。
【請求項２７】
前記集約リンクと当該集約リンクを構成する個別リンクのリストとを対応付けてリンクマッピングテーブルに格納し、パケット受信時に前記リンクマッピングテーブルから前記集約リンクを構成する個別リンクの１つを選択してパケット転送を行うようにし、
前記リンクマッピングテーブルにおいて、前記集約リンクに対応する当該集約リンクを構成する個別リンクのリストに記載された個別リンクのそれぞれに設定された分散係数にしたがつて負荷分割パケット転送を行うようにしたことを特徴とする請求項１９から請求項２６のいずれか記載のパケット転送経路制御方法。
【請求項２８】
前記分散係数の設定は、前記個別リンク毎の帯域比及び前記個別リンク毎の前記分散係数のパラメータのいずれかを設定するようにしたことを特徴とする請求項２７記載のパケット転送経路制御方法。
【請求項２９】
前記隣接装置識別子及び前記隣接個別リンク識別子を学習する際に、前記ハローメッセージに前記個別リンクのインタフェース識別子を格納することで互いのインタフェース識別子を学習し合うようにしたことを特徴とする請求項１９から請求項２８のいずれか記載のパケット転送経路制御方法。
【請求項３０】
請求項２９記載のパケット転送経路制御方法を用い、各個別リンク毎にスイッチングを行うクロスコネクト装置において、前記個別リンクが使用中であるかどうかを管理し、シグナリング要求メッセージを受信した際に転送先の集約リンクを特定し、当該集約リンクを構成する個別リンクの中で使用中でない個別リンクを選択するようにしたことを特徴とするパケット転送経路制御方法。
【請求項３１】
前記シグナリング要求メッセージを受信した際に、当該シグナリング要求メッセージ内の送信個別リンク識別子を参照し、その送信個別リンク識別子及び受信した集約リンクの前記インタフェース識別子を基に自装置に蓄積する隣接装置個別リンク識別子に一致する個別リンクを探索することで、どのリンクに対するシグナリング要求であるかを認識するようにしたことを特徴とする請求項３０記載のパケット転送経路制御方法。
【請求項３２】
前記送信個別リンク識別子に対応する隣接ルータリンク識別子を予め個別リンク管理テーブルから検索し、当該隣接ルータリンク識別子を宛先個別リンク識別子として前記シグナリング要求メッセージに挿入するようにしたことを特徴とする請求項３０記載のパケット転送経路制御方法。
【請求項３３】
前記個別リンク各々に送信側と受信側とで同一の値となる共通リンク識別子を設定し、その共通リンク識別子を前記シグナリンク要求メッセージに挿入するようにしたことを特徴とする請求項３０記載のパケット転送経路制御方法。
【請求項３４】
前記共通リンク識別子は、前記送信側及び前記受信側各々の個別リンク識別子のうちの大きい方の値を使用するようにしたことを特徴とする請求項３３記載のパケット転送経路制御方法。
【請求項３５】
転送先として選択した個別リンクの隣接個別リンク識別子を読出して前記シグナリング要求メッセージによって前記隣接装置に通知するようにしたことを特徴とする請求項３０記載のパケット転送経路制御方法。
【請求項３６】
前記ルーティングテーブルは、リンクステート型のルーティングプロトコルに用いられるリンクステートルーティングテーブルであることを特徴とする請求項１９から請求項３５のいずれか記載のパケット転送経路制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はパケット転送経路制御装置及びそれに用いるパケット転送経路制御方法に関し、特に装置間に複数のリンクが接続されている環境（インタネット網）でのパケット転送経路制御方法に関する。
【０００２】
【従来の技術】
ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）トラフィックは４ヶ月から８ヶ月で倍になるといわれており、このＩＰトラフィックを収容するため、北米インタネットバックボーンに設置されるルータは年々大容量化、高速化が進んでいる。既に、回線インタフェース速度はＯＣ−１９２（１０Ｇｂｐｓ）に到達しようとしており、これ以上の高速化は困難な状況になりつつある。
【０００３】
しかしながら、ＷＤＭ（Ｗａｖｅｌｅｎｇｔｈ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅｘｉｎｇ）技術の進展によって、１本のファイバ内に複数のデータチャネルを収容可能となったことで、今後、急増するトラフィックを収容するために、ＷＤＭ装置の導入が加速し、ルータ間の並列リンク数が増加していくことはほぼ必然と考えられる。
【０００４】
また、インタネットではルーティングプロトコルがネットワーク内ルータの接続関係を報告し合うことによって、自律分散的にルーティングテーブルを作成している。上記のルーティングプロトコルとしてはリンクステート型とディスタントベクタ型とがあり、特にＩＳＰ（Ｉｎｔｅｒｎｅｔ  Ｓｅｒｖｉｃｅ  Ｐｒｏｖｉｄｏｒ）のバックボーンではリンクステート型が使われている。
【０００５】
代表的なリンクステートルーティングプロトコルとしては、インタネットエンジニアリングタスクフォース（Ｉｎｔｅｒｎｅｔ  Ｅｎｇｉｎｎｅｒｉｎｇ  Ｔａｓｋ  Ｆｏｒｃｅ（ＩＥＴＦ））において１９９１年６月に承認されたリクエストフォーコメンツ（Ｒｅｑｕｅｓｔ  Ｆｏｒ  Ｃｏｍｍｅｃｎｔｓ（ＲＦＣ））１２４７の標準プロトコル案“オーエスピーエフ  バージョン２（ＯＳＰＦ  Ｖｅｒｓｉｏｎ２）”や、国際標準化機構（Ｉｎｔｅｒｎａｔｉａｌ  Ｏｒｇａｎｉｚａｔｉｏｎｓ  ｏｆ  Ｓｔａｎｄａｒｄｉｚａｔｉｏｎ（ＩＳＯ））において、１９９２年６月に承認されたＩＳＯ  １０５８９の勧告ＩＳ−ＩＳ（Ｉｎｔｅｒｍｉｄｉａｔｅ  Ｓｙｓｔｅｍ  ｔｏ  Ｉｎｔｅｒｍｉｄｉａｔｅ  Ｓｙｓｔｅｍ）等がある。
【０００６】
リンクステートルーティングプロトコルはハロー（Ｈｅｌｌｏ）メッセージによる隣接ルータの識別、ＬＳＡ（Ｌｉｎｋ  Ｓｔａｔｅ  Ａｄｖｅｒｔｉｓｅｍｅｎｔ）交換による接続情報の学習、ＳＰＦ（Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔ）ツリーによるルーティングテーブルの計算という３つの機能要素から構成されている。
【０００７】
まず、リンクステートルーティングプロトコルはルータの全てのインタフェースにおいて、ハローメッセージを交換することによって隣接ルータを識別する。隣接ルータを識別すると、ルータの接続する隣接ルータの全ての情報を含んだＬＳＡを作成し、ルータの接続する全てのインターフェスを通して送信することによって隣接ルータに対してＬＳＡを通知する。また、他の隣接ルータから受信したＬＳＡに関しても、受信したインタフェース以外の全てのインタフェースに対して送信する。この全てのインタフェースに対するＬＳＡの送信処理をフラッディングと呼ぶ。
【０００８】
上記のフラッディング処理を繰り返すことによって、ルータはエリア内の全てのルータが送信したＬＳＡを受信し、ルータ間の接続関係を全て学習する。隣接関係を学習すると、リンクステートルーティングプロトコルはＳＰＦツリーを作成し、ルーティングテーブルを作成する。ＳＰＦツリーは、自分自身をルートとして、各ルータに対する経路が最短となるようなリンクのみで構成されるツリーである。
【０００９】
リンクステートルーティングプロトコルではＳＰＦツリーを計算するために、Ｄｉｊｋｓｔｒａのアルゴリズムを使用する。このＤｉｊｓｔｒａのアルゴリズムによって、ＳＰＦツリーの計算オーダはエリア内の全ルータ数をＮ、エリア内の全リンク数をＬとした場合、Ｏ（（ｎ＋Ｌ）×ｌｏｇ（ｎ））となることが知られている。但し、ＩＳ−ＩＳではＨａｓｈ  Ｔａｂｌｅを利用することによって、ＳＰＦツリーの計算オーダはＯ（Ｌ）となる。上記のＤｉｊｓｔｒａのアルゴリズムについては、“Ｒｏｕｔｉｎｇ  ｉｎ  ＣｏｍｍｕｎｉｃａｔｉｏｎｓＮｅｔｗｏｒｋｓ”［Ｍ．Ｓｔｅｅｎｓｔｒｕｐ，Ｐｒｅｎｔｉｃｅ  Ｈａｌｌ，ｐｐ１４３−１５２（１９９５）］に記載されている。
【００１０】
【発明が解決しようとする課題】
上述した従来のパケット転送経路制御方法では、リンクステートルーティングプロトコルを使用する場合、ルータ間の並列リンク数が増大することによって、ルータの作成するＬＳＡがルータの有する全リンクの接続情報によって構成されるので、並列リンクの増大に比例してリンクステート情報量が増大するという問題がある。
【００１１】
また、並列リンクの増大に比例した情報量のリンクステートパケットを、並列リンクの全てに送出するため、並列リンクの２乗に比例してルーティング制御トラフィックが増大するという問題がある。
【００１２】
さらに、ＳＰＦツリーの計算量がネットワーク内の全リンク数に比例して増大するので、並列リンク数に比例してＳＰＦツリーの計算量が増大するという問題がある。
【００１３】
さらにまた、リンクのメトリック値をリンク帯域の逆数に比例して設定している場合に、適切な経路が選択されないという問題がある。例えば、ルータＡ−Ｂ間に１００Ｍｂｐｓの２０本のリンクが存在し、ルータＡ−Ｃ間に６００Ｍｂｐｓの１本のリンクが存在する場合、ルータＡ−Ｂ間の方が合計の帯域が大きいにも関わらず、ルータＡ−Ｃ間のリンクのメトリック値の方が小さく設定されるため、ＳＰＦツリーの作成時にルータＡ−Ｃ間のリンクが優先的に選択されることになる。
【００１４】
この問題はルータＡ−Ｂ間の各リンクのメトリック値を１００Ｍｂｐｓ×２０＝２Ｇｂｐｓ分の合計帯域に設定することによって解決可能である。但し、リンクの障害が発生して合計帯域が変化した場合には、合計帯域と異なるメトリック値を設定してしまうことになる。以上のように、リンクのメトリック値をルータ間の並列リンクの合計帯域に対して設定することが難しいという問題がある。
【００１５】
そこで、本発明の目的は上記の問題点を解消し、現状のリンクステートルーティング処理部に手を加えずに、ルータ間並列リンクにおけるルーティング処理のスケーラビリティ及び安定性を確保することができるパケット転送経路制御装置及びそれに用いるパケット転送経路制御方法を提供することにある。
【００１６】
【課題を解決するための手段】
本発明によるパケット転送経路制御装置は、ネットワークを構成する装置間の接続関係を報告し合うことによって自律分散的にルーティングテーブルを作成するルーティング処理手段を含むパケット転送経路制御装置であって、
前記装置間を接続する個別リンクを介して隣接装置との接続情報を学習するためのハローメッセージを交換して前記隣接装置を特定する隣接装置識別子及び前記隣接装置に接続するための隣接個別リンクを特定する隣接個別リンク識別子を学習する個別リンク管理手段と、同一の隣接装置識別子を持つ複数の個別リンクを１つの集約リンクとして管理して前記ルーティング処理手段に通知する集約リンク管理手段とを備え、
前記ルーティング処理手段は、前記集約リンク単位で処理を行い、
前記集約リンク管理手段は、前記同一の隣接装置識別子を持つ複数の個別リンクのうちの各個別リンク毎に予め設定された設定情報が同一の個別リンクを１つの集約リンクとして管理するようにし、
前記設定情報が少なくとも管理上のグループを示すグループ識別子及び各個別リンク毎の優先度を示す優先度情報のいずれかを具備している。
【００１７】
本発明によるパケット転送経路制御方法は、ネットワークを構成する装置間の接続関係を報告し合うことによって自律分散的にルーティングテーブルを作成するルーティング処理手段を含むパケット転送経路制御装置のパケット転送経路制御方法であって、
前記装置間を接続する個別リンクを介して隣接装置との接続情報を学習するためのハローメッセージを交換して前記隣接装置を特定する隣接装置識別子及び前記隣接装置に接続するための隣接個別リンクを特定する隣接個別リンク識別子を学習し、同一の隣接装置識別子を持つ複数の個別リンクを１つの集約リンクとして管理して前記ルーティング処理手段に通知するとともに、前記ルーティング処理手段は前記集約リンク単位で処理を行い、
前記集約リンクとして管理する際に、前記同一の隣接装置識別子を持つ複数の個別リンクのうちの各個別リンク毎に予め設定された設定情報が同一の個別リンクを１つの集約リンクとして管理するようにし、
前記設定情報が少なくとも管理上のグループを示すグループ識別子及び各個別リンク毎の優先度を示す優先度情報のいずれかを具備している。
【００１８】
すなわち、本発明のパケット転送経路制御装置は、従来のリンクステートルーティング制御手段と当該リンクステートルーティング制御手段の作成するリンクステートルーティングテーブルとに加えて、個別リンク間でハローメッセージを交換することによって隣接装置識別子及び隣接個別リンク識別子を学習する個別リンク管理手段と、同一の隣接装置識別子を有する個別リンクを１つの集約リンクとして管理してリンクステートルーティング制御手段に通知する集約リンク管理手段とを有している。
【００１９】
これによって、並列リンク管理部で集約された集約リンク単位でリンクステートルーティング処理部におけるルーティング処理が行われるので、ルータ間の個別リンク数に関係なく、スケーラブルなルーティング処理を実現することが可能となる。
【００２０】
【発明の実施の形態】
次に、本発明の実施例について図面を参照して説明する。図１は本発明の第１の実施例によるルータの構成を示すブロック図である。図１において、ルータ１はパケット転送経路制御装置２と、スイッチ部３と、インタフェース部４ａ〜４ｈとから構成されている。
【００２１】
パケット転送経路制御装置２は隣接するルータと制御パケットの交換を行う。制御パケットの交換はスイッチ部３を介して隣接ルータと接続するインタフェース部４ａ〜４ｈからパケットを送受信することによって実現する。また、パケット転送経路制御装置２は他のルータに配備されたパケット転送経路制御装置２と交換したリンクステート情報及び集約リンク情報にしたがってパケットを転送するためのテーブルを作成し、各インタフェース部４ａ〜４ｈにダウンロードする。
【００２２】
図２は図１のパケット転送経路制御装置２の構成を示すブロック図である。図２において、パケット転送経路制御装置２は並列リンク管理部２０と、リンクステートルーティング処理部２６と、個別リンクインタフェースドライバ部２７と、リンクステートルーティングテーブル２８と、個別リンクマッピングテーブル２９とから構成されている。
【００２３】
並列リンク管理部２０は個別リンク管理部２１と、集約リンク管理部２２と、インタフェース変換部２３と、個別リンク管理テーブル２４と、集約リンク管理テーブル２５とから構成されている。
【００２４】
個別リンクインタフェースドライバ部２７は各個別リンクと制御パケットを送受信する。並列リンク管理部２０は個別リンクインタフェースドライバ部２７を介して各個別リンク間でハローメッセージを交換することによって、同一隣接ルータ間と接続している個別リンクを集約化して集約リンクを生成し、リンクステートルーティング処理部２６へ通知する。
【００２５】
リンクステートルーティング処理部２６は並列リンク管理部２０から通知された集約リンクにしたがってルーティング処理を行うモジュールであり、従来のリンクステートルーティング処理部と同様のものである。
【００２６】
リンクステートルーティング処理部２６はパケットの宛先アドレスから転送するルータの集約リンクを決定するリンクステートルーティングテーブル２８を管理し、並列リンク管理部２０は集約リンクから個別リンクへマッピングするための個別リンクマッピングテーブル２９を管理する。
【００２７】
図３は図２の個別リンク管理テーブル２４の構成例を示す図であり、図４は図２の集約リンク管理テーブル２５の構成例を示す図であり、図５は図２の個別リンクマッピングテーブル２９の構成例を示す図であり、図６は図２の個別リンク管理部２１の動作を示すフローチャートであり、図７は図２の集約リンク管理部２２の動作を示すフローチャートである。これら図２〜図７を参照して並列リンク管理部２０の構成及び動作について説明する。
【００２８】
個別リンク管理部２１は個別リンク毎にハローメッセージを交換することによって、隣接ルータとの接続情報を学習する。ハローメッセージは送信ルータ識別子（ＳＲＩＤ）、送信インタフェース識別子（ＳＩＩＤ）、隣接ルータ識別子（ＮＲＩＤ）、ハローメッセージ有効時間（ＨＨＴ）から構成されており、従来と同様に、隣接ルータを識別するためのものである。
【００２９】
送信ルータ識別子（ＳＲＩＤ）はハローメッセージを送信するルータのルータ識別子である。送信インタフェース識別子（ＳＩＩＤ）はハローメッセージを送信するインタフェースを識別するものであり、インタフェースのＩＰアドレスが設定される。インタフェースにＩＰアドレスが設定されていない場合には、インタフェースを一意に識別するための識別番号であるＩｆＩｎｄｅｘを使用する。
【００３０】
隣接ルータ識別子（ＮＲＩＤ）はハローメッセージを送信するインタフェースに接続する隣接ルータを一意に識別するためのＩＰアドレスであり、隣接ルータのルータ識別子を設定する。ハロー有効時間（ＨＨＴ）はハローメッセージの有効時間であり、設定された有効時間以内に次のハローパケットを受信しなければ、隣接ルータとの接続関係が破棄される。
【００３１】
個別リンク管理部２１は各個別リンクを管理するための個別リンク管理テーブル２４を有する。個別リンク管理テーブル２４の構成例を図３に示す。個別リンク管理テーブル２４は個別リンク識別子（ＣＬＩＤ）、個別リンク状態（ＣＬＳＴ）、隣接ルータ識別子（ＮＲＩＤ）、隣接ルータリンク識別子（ＮＣＬＩＤ）、個別リンク帯域（ＣＬＢＷ）から構成されている。
【００３２】
個別リンク管理部２１は自身の有する個別リンクに関して、個別リンクがアップ状態になったことを下位レイヤから通知されると、個別リンク管理テーブル２４のリンク状態を「ＵＰ」に設定し、個別リンク管理テーブル２４から送信インタフェース識別子（ＳＩＩＤ）及び隣接ルータ識別子（ＮＲＩＤ）を読出してハローメッセージを作成した後、これを送信する。隣接ルータ識別子（ＮＲＩＤ）は学習していない状態では空欄とする。
【００３３】
個別リンク管理部２１は隣接ルータからハローメッセージを受信すると、送信ルータ識別子（ＳＲＩＤ）から受信インタフェースの隣接ルータ識別子（ＮＲＩＤ）を学習して個別リンク管理テーブル２４に登録し、ハローメッセージ内の隣接ルータ識別子（ＮＲＩＤ）を更新し、そのハローメッセージを送信する。
【００３４】
個別リンク状態（ＣＬＳＴ）は「ＤＯＷＮ」、「ＵＰ」、「ＥＳＴＡＢＬＩＳＨ」の三種類の状態を有する。「ＤＯＷＮ」は下位レイヤにおいて個別リンクが使用できないと通知されている状態である。「ＵＰ」は下位レイヤから個別リンクが使用可能であると通知されているが、隣接ルータの個別リンク管理部との接続関係が確立されていない状態である。「ＥＳＴＡＢＬＩＳＨ」は隣接ルータの個別リンク管理部との接続関係が確立された状態である。
【００３５】
個別リンク管理部２１は隣接ルータからハローメッセージを受信すると、隣接ルータ識別子（ＮＲＩＤ）をチェックする。隣接ルータ識別子（ＮＲＩＤ）が自身のルータ識別子と一致する場合には隣接関係が確立されたと判断し、個別リンク管理テーブル２４の個別リンク状態（ＣＬＳＴ）を「ＥＳＴＡＢＬＩＳＨ」に設定し（図６ステップＳ１１，Ｓ１２）、個別リンクのリンクアップを、隣接ルータ識別子及びリンク帯域とともに集約リンク管理部２２に通知する（図６ステップＳ１３）。
【００３６】
個別リンク管理部２１は個別リンク状態（ＣＬＳＴ）が「ＥＳＴＡＢＬＩＳＨ」においてハローメッセージを受信すると、ハローメッセージ有効時間経過後にタイムアウトする個別リンク毎のハロー保持タイマ（図示せず）を設定する。
【００３７】
個別リンク管理部２１はタイマアウト発生前にハローメッセージを受信した場合、ハロー保持タイマを再設定する。ハローメッセージ有効時間以内にハローメッセージを受信しない場合にはタイムアウトが発生し、該当する個別リンクの個別リンク状態（ＣＬＳＴ）は「ＵＰ」に設定され、個別リンクのリンクダウンを集約リンク管理部２２に通知する。
【００３８】
個別リンク管理部２１は下位レイヤから個別リンクのリンクダウンが通知されると、個別リンク状態（ＣＬＳＴ）を「ＤＯＷＮ」に設定し、隣接ルータ識別子（ＮＲＩＤ）、隣接ルータリンク識別子（ＮＣＬＩＤ）をクリアする。その際、リンク状態が「ＥＳＴＡＢＬＩＳＨ」から「ＤＯＷＮ」に変更した場合には（図６ステップＳ１１，Ｓ１４）、集約リンク管理部２２に該当個別リンクのリンクダウンを、隣接ルータ識別子及びリンク帯域とともに通知する（図６ステップＳ１５）。
【００３９】
集約リンク管理部２２は集約リンク管理テーブル２５によって集約リンク毎の情報を管理する。集約リンク管理テーブル２５の構成例を図４に示す。集約リンク管理テーブル２５は集約リンク識別子（ＢＬＩＤ）、隣接ルータ識別子（ＮＲＩＤ）、合計帯域（ＴＢＷ）、集約リンク状態（ＢＳＴ）、個別リンク数（ＣＬＮ）、インタフェースＩＰアドレス、隣接インタフェースＩＰアドレスから構成されている。
【００４０】
集約リンク識別子（ＢＬＩＤ）は集約リンクを一意に識別する識別番号である。隣接ルータ識別子（ＮＲＩＤ）は集約リンクの接続する隣接ルータのルータ識別子である。合計帯域（ＴＢＷ）は集約リンクを構成する各個別リンクの帯域の和である。
【００４１】
集約リンク状態（ＢＳＴ）は集約リンクの状態を示しており、「ＤＯＷＮ」と「ＵＰ」との二種類が存在する。個別リンク数（ＣＬＮ）は集約リンクを構成する個別リンクの数である。インタフェースＩＰアドレスは集約リンクにつけられたインタフェースＩＰアドレスである。隣接インタフェースＩＰアドレスは集約リンクにつけられた隣接ルータのインタフェースＩＰアドレスである。
【００４２】
集約リンク管理部２２は個別リンク管理部２１から集約リンクを構成する個別リンクのリンクアップ、リンクダウンの通知を受けると、集約リンク状態と個別リンク数と合計帯域とを変更する。
【００４３】
集約リンク管理部２２は個別リンクのリンクアップの通知を受けると（図７ステップＳ２１，Ｓ２２）、隣接ルータ識別子より集約リンクを特定し（図７ステップＳ２３）、該当する集約リンクの個別リンク数を１大きい値に変更する（図７ステップＳ２４）。
【００４４】
また、集約リンク管理部２２は個別リンクのリンクダウンの通知を受けると（図７ステップＳ２１，Ｓ２２）、隣接ルータ識別子より集約リンクを特定し（図７ステップＳ２６）、該当する集約リンクの個別リンク数を１小さい値に変更する（図７ステップＳ２７）。集約リンク状態は個別リンク数によって決定し、個別リンク数が０の場合には（図７ステップＳ３０）、「ＤＯＷＮ」状態となり（図７ステップＳ３１）、個別リンク数が１以上の場合には（図７ステップＳ３０）、「ＵＰ」状態となる（図７ステップＳ３４）。
【００４５】
集約リンク管理部２２はリンクアップ時に個別リンクの帯域を合計帯域に追加し（図７ステップＳ２５）、リンクダウン時に個別リンクの帯域を合計帯域から減少する（図７ステップＳ２８）。集約リンクのメトリック値は合計帯域（ＴＢＷ）の逆数として計算される（図７ステップＳ２９）。
【００４６】
この計算方法は個別リンクにおいて管理している情報が帯域ではなく、メトリックである場合にも、帯域をメトリックの逆数として考えることによって同様に適用可能である。
【００４７】
集約リンク管理部２２は集約リンク状態が変化した場合やメトリックが変更された場合（図７ステップＳ３６）、リンクステートルーティング処理部２６に該当集約リンクの集約リンク状態とメトリックとを通知する（図７ステップＳ３７）。
【００４８】
集約リンク管理部２２は個別リンク管理部２１から集約リンクを構成する個別リンクのリンクアップ、リンクダウンの通知を受けると、個別リンクマッピングテーブル２９の更新を行う。個別リンクマッピングテーブル２９は、図５に示すように、集約リンクに対する個別リンクのリスト及びその負荷分割転送比（分散比）が格納される。
【００４９】
集約リンク管理部２２は個別リンク管理部２１から個別リンクのリンクアップ通知を受けた場合、該当する集約リンクに当該個別リンクのエントリを追加し（図７ステップＳ３５）、分割転送比を設定する。分割転送比は帯域に比例した値を設定するものとするが、個別リンク管理テーブル２４に個別リンク毎の分散転送比のパラメータを設定可能として、その値を利用しても良い。
【００５０】
集約リンク管理部２２は個別リンク管理部２１から個別リンクのリンクダウン通知を受けた場合、該当する集約リンクから当該個別リンクのエントリを削除し（図７ステップＳ３２）、リンクステートルーティング処理部２６にリンクダウンとメトリックとを通知する（図７ステップＳ３３）。
【００５１】
インタフェース変換部２３はリンクステートルーティング処理部２６からリンクステートルーティングパケットの送信要求を受付けると、集約リンクの中の１つの個別リンクを選択してパケットを転送する。また、インタフェース変換部２３はある個別リンクで隣接ルータからンクステートルーティングパケットを受信した場合、当該個別リンクを構成する集約リンクからパケットを受信したものとして、リンクステートルーティング処理部２６に受信パケットを受け渡す。
【００５２】
但し、ＯＳＰＦ（Ｏｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔ）等のように、受信インタフェースの識別を受信パケット内のインタフェースＩＰアドレスによって識別しているようなリンクステートルーティング処理部２６の場合には、インタフェース変換部２３で変換しなくても、リンクステートルーティング処理部２６は集約リンクにおいて受信したものと認識するため、変換を必要とはしない。
【００５３】
図８は図１のインタフェース部４ａ〜４ｈにおける転送リンク決定処理の動作を示す図である。図８においてはインタフェース部４ａ〜４ｈをインタフェース部４として示している。
【００５４】
まず、インタフェース部４にパケットが入力されると、集約リンク選択処理部４１はパケットの宛先アドレスからリンクステートルーティングテーブル２８を参照し、集約リンクを解決する。
【００５５】
次に、個別リンク選択処理部４２は個別リンクマッピングテーブル２９から集約リンクに対応する個別リンクのリストを解決し、個別リンクのリストの中の１つの個別リンクを選択してパケットの転送を行う。
【００５６】
図９は本発明の第１の実施例によるネットワークの構成を示すブロック図である。図９においてはパケット転送経路制御装置２を有するルータによって構成されるＩＰネットワークの構成を表したものである。このＩＰネットワークは第１〜第６の６台のルータ５１〜５６で構成されており、各ルータ５１〜５６間は一本もしくは複数のリンク１０１〜１０４で接続されている。
【００５７】
上記のパケット転送経路制御装置２を備えたルータ５１〜５６は各々有するリンク上でハローパケットを交換することによって、隣接するルータの装置識別子を取得する。装置識別子は装置を一意に識別するものであり、ルータ５１〜５６の場合にはルータ識別子（Ｒｏｕｔｅｒ  ＩＤ）と呼ばれる各ルータ５１〜５６にユニークなＩＰアドレスを利用する。
【００５８】
上述した集約リンクは隣接するルータのルータ識別子が同一であるリンクを集約して一本のリンクへと仮想リンク化したものである。また、上述した個別リンクは仮想化されていないリンクを集約リンクと区別するためのものである。個別リンクは物理的に異なる媒体を通るリンクの場合もあれば、ＡＴＭ（Ａｓｙｃｈｒｏｎｏｕｓ  Ｔｒａｎｓｆｅｒ  Ｍｏｄｅ）のＶＣ（Ｖｉｒｔｕａｌ  Ｃｏｎｎｅｃｔｉｏｎ）のような論理的に生成されたリンクの場合もある。
【００５９】
パケット転送経路制御装置２内のリンクステートルーティング処理部２６はこの集約リンク単位でルーティング処理を行う。
【００６０】
図１０は本発明の第１の実施例によるリンクステートルーティングモジュールの認識するネットワークの構成を示す図である。図１０において、全てのルータ５１〜５６は１本の集約リンク２０１〜２０８によって接続されているため、各ルータ５１〜５６間の個別リンク数に関係なく、スケーラブルなルーティング処理が実現可能となる。
【００６１】
図１１は本発明の第１の実施例におけるハローメッセージによる隣接関係の確立例を示すシーケンスチャートである。これら図１〜図１１を参照して隣接ルータ間の個別リンク管理部２１においてハローメッセージを交換することによる個別リンクの隣接関係確立手順について説明する。尚、交換する情報としては送信ルータ識別子（ＳＲＩＤ）と隣接ルータ識別子（ＮＲＩＤ）とのみを示し、他の情報は省略する。
【００６２】
まず、第１のルータ５１の個別リンク管理部２１は個別リンクのリンク状態が「ＤＯＷＮ」状態から「ＵＰ」状態に変化すると、送信ルータ識別子（ＳＲＩＤ）を「第１のルータのルータ識別子」、隣接ルータ識別子（ＮＲＩＤ）を「なし」に設定してハローメッセージを送信する（図１１のＳ１）。
【００６３】
第１のルータ５１からハローメッセージを受信した第２のルータ５２の個別リンク管理部２１は、第１のルータ５１と同じタイミングで、個別リンクのリンク状態が「ＤＯＷＮ」状態から「ＵＰ」状態に変化すると、ハローメッセージ内の隣接ルータ識別子（ＮＲＩＤ）が「なし」であるため、リンク状態を「ＵＰ」のまま変更しない。
【００６４】
次に、第２のルータ５２の個別リンク管理部２１は送信ルータ識別子（ＳＲＩＤ）＝「第２のルータのルータ識別子」、隣接ルータ識別子（ＮＲＩＤ）＝「第１のルータのルータ識別子」に設定して、ハローメッセージを送信する（図１１のＳ２）。
【００６５】
第２のルータ５２からハローメッセージを受信した第１のルータ５１の個別リンク管理部２１はハローメッセージ内の隣接ルータ識別子（ＮＲＩＤ）が「第１のルータのルータ識別子」であり、自分のルータ識別子と一致することからリンク状態を「ＥＳＴＡＢＬＩＳＨ］に変更する。
【００６６】
次に、第１のルータ５１の個別リンク管理部２１は送信ルータ識別子（ＳＲＩＤ）＝「第１のルータのルータ識別子」、隣接ルータ識別子（ＮＲＩＤ）＝「第２のルータのルータ識別子」に設定して、ハローメッセージを送信する（図１１のＳ３）。
【００６７】
第１のルータ５１からハローメッセージを受信した第２のルータ５２の個別リンク管理部２１はハローメッセージ内の隣接ルータ識別子（ＮＲＩＤ）が「第２のルータのルータ識別子」であり、自分のルータ識別子と一致することから、リンク状態を「ＥＳＴＡＢＬＩＳＨ］に変更する。
【００６８】
以上の処理動作によって、第１のルータ５１、第２のルータ５２の両方において、双方向での通信が可能であることが確認される。
【００６９】
次に、第１のルータ５１と第２のルータ５２との間の個別リンク１０１に障害が発生した場合の動作について図１〜図１１を用いて説明する。
【００７０】
個別リンク管理部２１は個別リンク１０１に障害が発生した場合、例えば下位レイヤにおける信号断通知等によって個別リンク１０１が通信不能であることを認識すると、個別リンク管理テーブル２４の個別リンク１０１に関して、個別リンク状態（ＣＬＳＴ）を「ＤＯＷＮ」に設定し、集約リンク管理部２２に個別リンク１０１がダウンしたことを通知する。集約リンク管理部２２は個別リンク１０１によって構成されている集約リンク２０１に関して、集約リンク管理テーブル２５を更新するとともに、個別リンクマッピングテーブル２９の集約リンク２０１のエントリから個別リンク１０１を削除する。
【００７１】
個別リンク１０１を個別リンクマッピングテーブル２９から削除することによって、ルータ５１におけるパケット転送は集約リンク２０１を構成する個別リンク１０１〜１０４において、障害の発生した個別リンク１０１を除く他の個別リンク１０２〜１０４に対して負荷分割パケット転送が行われる。
【００７２】
パケット転送経路制御装置２における個別リンクに障害が発生した場合のパケット転送テーブルの更新処理は、個別リンクマッピングテーブル２９の更新によって実現され、個別リンクマッピングテーブル２９の更新はリンクステートルーティング処理部２６におけるリンクステートルーティングテーブル２８の再計算処理を行うことなく更新されるため、従来のリンクステートルーティング処理部による転送テーブル更新に比べ、非常に高速に転送テーブルの更新を実施することが可能である。
【００７３】
上述した本発明の第１の実施例では同一の隣接ルータ識別子（ＮＲＩＤ）を有する個別リンク毎に集約リンクを作成しているが、同一の隣接ルータ識別子（ＮＲＩＤ）を有し、同一の帯域幅の個別リンク毎に集約リンクを設定することも可能である。
【００７４】
本発明の第２の実施例は同一の隣接ルータ識別子（ＮＲＩＤ）を有し、上述したように、同一の帯域幅の個別リンク毎に集約リンクを設定するものである。尚、本発明の第２の実施例は本発明の第１の実施例と同様の構成となっている。
【００７５】
図１２は本発明の第２の実施例による集約リンク管理テーブル２５の構成例を示す図であり、図１３は本発明の第２の実施例による個別リンク管理部２１の動作を示すフローチャートであり、図１４は本発明の第２の実施例による集約リンク管理部２２の動作を示すフローチャートである。これら図１〜図３と図５と図８〜図１４とを参照して本発明の第２の実施例について説明する。
【００７６】
尚、本発明の第２の実施例は同一の帯域幅の個別リンク毎に集約リンクを設定しているので、図１２に示す集約リンク管理テーブル２５は、合計帯域（ＴＢＷ）の項目の代わりにリンク帯域（ＣＬＢＷ）の項目を設けた以外は図４に示す集約リンク管理テーブル２５と同様の構成となっている。
【００７７】
また、図１３に示す本発明の第２の実施例による個別リンク管理部２１のステップＳ４１〜Ｓ４５の処理動作においては、ステップＳ４３の処理で集約リンク管理部２２に隣接インタフェースＩＰアドレスも通知するようにした以外は図６に示す本発明の第１の実施例による個別リンク管理部２１のステップＳ１１〜Ｓ１５の処理動作と同様であるので、その詳細な動作の説明は省略する。
【００７８】
さらに、図１４に示す本発明の第２の実施例による集約リンク管理部２２のステップＳ５１〜Ｓ６８の処理動作においては、ステップＳ５６の処理で隣接インタフェースＩＰアドレスを設定するようにし、ステップＳ６７の処理で隣接インタフェースＩＰアドレスの変化をチェックするようにした以外は図７に示す本発明の第１の実施例による集約リンク管理部２２のステップＳ２１〜Ｓ３７の処理動作と同様であるので、その詳細な動作の説明は省略する。
【００７９】
集約リンク管理部２２は個別リンクのリンクアップもしくはリンクダウンが通知された場合、当該個別リンクの隣接ルータ識別子（ＮＲＩＤ）と帯域に一致する集約リンク識別子（ＢＬＩＤ）とにマッピングする。
【００８０】
本発明の第２の実施例のリンクマッピングテーブルでは、集約リンクを構成する個別リンクの帯域が同一であるため、個別リンク毎の分散比を削除し、同一比で負荷分割パケット転送を行う。
【００８１】
また、本発明の第２の実施例においては隣接ルータ識別子（ＮＲＩＤ）と帯域が同一である個別リンク毎に集約リンクを作成しているが、帯域以外の情報、例えば帯域以外の１つまたは複数の他の情報を利用して集約リンクを作成しても良い。他の情報とは、例えば管理上のグループを表すグループ識別子やリンク毎に設定された優先度等である。また、リンクがＷＤＭによって多重されている波長の１つの場合には、同一ファイバを利用するリンク等が考えられる。
【００８２】
本発明の第３の実施例は集約リンク毎に設定されたインタフェースＩＰアドレスを隣接ルータに通知しあうことによって、隣接ルータのインタフェースＩＰアドレスを学習するものである。尚、本発明の第３の実施例は本発明の第１の実施例と同様の構成となっている。
【００８３】
図１５は本発明の第３の実施例による集約リンク管理テーブル２５の構成変化の一例を示す図であり、図１６は本発明の第３の実施例による個別リンク管理部２１の動作を示すフローチャートであり、図１７は本発明の第３の実施例による集約リンク管理部２２の動作を示すフローチャートである。これら図１〜図３と図５と図８〜図１１と図１５〜図１７とを参照して本発明の第３の実施例について説明する。
【００８４】
尚、図１６に示す本発明の第３の実施例による個別リンク管理部２１のステップＳ７１〜Ｓ７５の処理動作においては、ステップＳ７３の処理で集約リンク管理部２２に隣接インタフェースＩＰアドレスも通知するようにした以外は図６に示す本発明の第１の実施例による個別リンク管理部２１のステップＳ１１〜Ｓ１５の処理動作と同様であるので、その詳細な動作の説明は省略する。
【００８５】
また、図１７に示す本発明の第３の実施例による集約リンク管理部２２のステップＳ８１〜Ｓ９８の処理動作においては、ステップＳ８６の処理で隣接インタフェースＩＰアドレスを設定するようにし、ステップＳ９７の処理で隣接インタフェースＩＰアドレスの変化をチェックするようにした以外は図７に示す本発明の第１の実施例による集約リンク管理部２２のステップＳ２１〜Ｓ３７の処理動作と同様であるので、その詳細な動作の説明は省略する。
【００８６】
本発明の第３の実施例によるパケット転送経路制御装置２は集約リンク毎に設定されたインタフェースＩＰアドレスを隣接ルータに通知しあうことによって、隣接ルータのインタフェースＩＰアドレスを学習するため、予め隣接ルータインタフェースＩＰアドレスを設定しなくても良い。
【００８７】
本発明の第３の実施例による個別リンク管理部２１はハローメッセージに交換する情報として、送信ルータ識別子（ＳＲＩＤ）、送信インタフェース識別子（ＳＩＩＤ）、隣接ルータ識別子（ＮＲＩＤ）、ハローメッセージ有効時間以外に、集約リンクインタフェースＩＰアドレスを交換する。
【００８８】
次に、第１のルータ５１と第２のルータ５２との間の個別リンクを例に説明する。第１のルータ５１の個別リンク管理部２１はある個別リンクが「ＤＯＷＮ」状態から「ＵＰ」状態となると、集約リンクインタフェースＩＰアドレスを「なし」にして、ハローメッセージを送信する。
【００８９】
第１のルータ５１から当該個別リンクにおいてハローメッセージを受信した第２のルータ５２の個別リンク管理部２１は、第１のルータ５１と同じタイミングで、個別リンクが「ＤＯＷＮ」状態から「ＵＰ」状態となると、ハローメッセージの送信ルータ識別子（ＳＲＩＤ）から隣接ルータ識別子（ＮＲＩＤ）を得る。その後、集約リンク管理テーブル２５から当該隣接ルータ識別子（ＮＲＩＤ）で規定される集約リンクのインタフェースＩＰアドレスを読出し、ハローメッセージの集約リンクインタフェースＩＰアドレスとして設定した後、ハローメッセージを当該個別リンクに対して送出する。
【００９０】
第１のルータ５１の個別リンク管理部２１は第２のルータ５２からハローメッセージを受信した結果、インタフェースＩＰアドレスフィールドに集約リンクインタフェースＩＰアドレスが設定され、かつ隣接ルータ識別子（ＮＲＩＤ）に自身のルータ識別が設定されていることを認識する。
【００９１】
第１のルータ５１の個別リンク管理部２１は当該個別リンクのリンクアップを集約リンクインタフェースＩＰアドレス、隣接ルータ識別子（ＮＲＩＤ）とともに集約リンク管理部２２へ通知する。
【００９２】
集約リンク管理部２２は隣接ルータ識別子（ＮＲＩＤ）から集約リンクを特定し、集約リンクインタフェースＩＰアドレスを隣接ルータインタフェースＩＰアドレスとして登録する（図１５参照）。
【００９３】
図１８は本発明の第４の実施例によるネットワークの構成を示すブロック図である。図１８においては上記のパケット転送経路制御装置２を備えたＯＸＣ（Ｏｐｔｉｃａｌ  Ｃｒｏｓｓ  Ｃｏｎｎｅｃｔ）６１〜６４とルータ５１〜５４とによって構成するネットワークの例を示している。ＯＸＣ６１〜６４とはファイバ内に多重される波長セグメントを各ノードで交換し、ルータ間にリンクを設定するものである。
【００９４】
ルータ５１〜５４とＯＸＣ６１〜６４との間は複数のリンクによって接続されている。ＯＸＣ６１〜６４間はＷＤＭ多重分離装置７１を介して１本もしくは複数本のファイバ３０１によって接続されている。ＷＤＭ多重分離装置７１においては波長の異なるチャネルが多重されているため、論理的にはＯＸＣ６１〜６４間には複数のリンクが接続される。
【００９５】
これらＯＸＣ６１〜６４内のパケット転送経路制御装置２はルータ５１〜５４と同様に、リンクステートプロトコルによって物理トポロジ情報を交換するものとする。
【００９６】
各ＯＸＣ６１〜６４は個々の波長リンクに関して、ハローメッセージを交換することによって、波長リンク間に双方向通信が可能であることを認識するとともに、互いの波長リンクのリンク識別子を学習する。また、ＯＸＣ６１〜６４はルータ５１〜５４と同様に、ルータ識別子を有するものとし、同一隣接ルータ識別子（ＮＲＩＤ）の波長リンクを集約リンク化する。
【００９７】
図１９は図１８のＯＸＣ６１における集約リンク管理テーブル６１ａの構成例を示す図である。図１９において、集約リンク管理テーブル６１ａは、合計帯域（ＴＢＷ）の項目の代わりに空きリンク数（ＥＬＮ）の項目を設けた以外は図４に示す集約リンク管理テーブル２５と同様の構成となっている。
【００９８】
図２０は図１８に示すネットワークにおいてリンクステートルーティング処理部２６によって認識されるネットワークの構成を示す図である。図２０においてはリンクステートルーティング処理部２６からみたルータ５１〜５４間の接続関係を示している。
【００９９】
リンクステートルーティング処理部２６ではルータ５１〜５４とＯＸＣ６１〜６４との間、及びＯＸＣ６１〜６４間が１本のリンク２０１〜２０８によって接続されているように認識されるため、スケーラブルなルーティング処理を実現することが可能である。
【０１００】
図２１は図１８に示すネットワークにおける波長パスの設定例を示す図である。図２１においては第１のルータ５１と第４のルータ５４との間に接続される波長パスの例を示している。
【０１０１】
ＯＸＣ６１〜６４を中継してルータ５１〜５４間でパケットを転送するためには、ルータ５１〜５４間に波長パスを設定する必要がある。波長パスを設定するためには各ＯＸＣ６１〜６４において、入力側のどのリンク出力側のどのリンクを接続するかのマトリックスを設定する必要がある。
【０１０２】
マトリックスの設定方法としては、ユーザがＮＭＳ等を利用して、個々のＯＸＣ６１〜６４に対して個別に設定する場合と、波長パスの始点となるルータ５１もしくは終点となるルータ５４が波長パスのシグナリングによって設定要求を行うことで設定される場合とがある。ここでは、始点のルータ５１が波長パスの設定要求を行う場合について説明する。
【０１０３】
波長パスの設定要求を行うためのシグナリングメッセージは転送経路リストと送信個別リンク識別子とを含む。転送経路リストは経由するＯＸＣ６１〜６４またはルータ５１〜５４の装置識別子、もしくは集約リンクインタフェースアドレスのリストによって構成される。送信個別リンク識別子はシグナリングメッセージを送信するＯＸＣ６１〜６４またはルータ５１〜５４の個別リンク識別子である。
【０１０４】
また、本発明の第４の実施例における個別リンク管理テーブル２４は、各個別リンク毎に使用状態かどうかを示すフラグを設定する。個別リンクがシグナリングパスによって既に設定されている場合には「使用中」となり、設定されていない場合には「未使用」となる。
【０１０５】
図２２は図１８のＯＸＣ６１〜６４におけるシグナリングメッセージの処理手順を示すフローチャートである。これら図１８〜図２２を参照してＯＸＣ６１〜６４におけるシグナリングメッセージの処理手順について説明する。
【０１０６】
ＯＸＣ６１〜６４はシグナリングメッセージを受信したかどうかをチェックし（図２２ステップＳ１０１）、シグナリングメッセージを受信しなければ繰返しチェックを行う。
【０１０７】
また、ＯＸＣ６１〜６４はシグナリングメッセージを受信すると、シグナリングメッセージ内の転送リストの先頭をチェックし、ＯＸＣ６１〜６４のルータ識別子もしくは集約リンクインタフェースアドレスのどれかであるかをチェックする（図２２ステップＳ１０２）。
【０１０８】
ＯＸＣ６１〜６４自身のルータ識別子もしくは集約リンクインタフェースアドレスであった場合には、転送リストから最初のエントリを削除する（図２２ステップＳ１０３）。
【０１０９】
次に、ＯＸＣ６１〜６４は送信個別リンク識別子から個別リンク管理テーブル２４内の受信集約リンクのエントリに関して、隣接個別リンク識別子に一致する個別リンクを受信個別リンクとして特定する（図２２ステップＳ１０４）。
【０１１０】
この後に、ＯＸＣ６１〜６４は転送リストの先頭からリンクステートルーティングテーブル２８を検索し、シグナリングメッセージを送信する集約リンクを決定する（図２２ステップＳ１０５）。
【０１１１】
ＯＸＣ６１〜６４は当該集約リンクを構成する個別リンクの中で使用状態が「未使用」の個別リンクを送信個別リンクとして検索する（図２２ステップＳ１０６）。ＯＸＣ６１〜６４は送信個別リンクを検索できなければ（図２２ステップＳ１０７）、送信拒否メッセージを送信元に対して送り返す（図２２ステップＳ１１０）。
【０１１２】
ＯＸＣ６１〜６４は送信個別リンクが検索できると（図２２ステップＳ１０７）、受信個別リンクと送信個別リンクとを接続するようにＯＸＣ６１〜６４のスイッチマトリックスの設定を予約する（図２２ステップＳ１０８）。
【０１１３】
その後、ＯＸＣ６１〜６４は送信ＩＰメッセージを次の送信先である集約リンクの送信インタフェースＩＰアドレスに設定し、シグナリングメッセージを送信する（図２２ステップＳ１０９）。
【０１１４】
図２３は図１８のＯＸＣ６１〜６４でのシグナリングメッセージの処理例を示す図である。図２３（ａ）は集約リンクの接続関係を示し、図２３（ｂ）は個別リンクの接続関係を示している。この図２３を参照して具体的なシグナリングメッセージの処理例について説明する。
【０１１５】
始点ルータである第１のルータ５１はシグナリングメッセージの転送経路リストを、第１のＯＸＣ６１、第２のＯＸＣ６２、第４のＯＸＣ６４、第４のルータ５４と設定する。
【０１１６】
次に、第１のルータ５１は第１のＯＸＣ６１と接続する集約リンク内の個別リンクから、「未使用」状態の個別リンクを選択する。第１のルータ５１はこの選択した個別リンクを送信個別リンク識別子に設定し、送信ＩＰアドレスを「１３３．２０６．４０．２」に設定して第１のＯＸＣ６１に出力する。ここでは、送信個別リンク識別子として「５」が設定される。
【０１１７】
シグナリングメッセージを受信した第１のＯＸＣ６１は転送経路リストの先頭が第１のＯＸＣ６１であることを認識すると、第１のＯＸＣ６１の部分を削除し、転送経路リストを第２のＯＸＣ６２、第４のＯＸＣ６４、第４のルータ５４と設定する。
【０１１８】
また、第１のＯＸＣ６１は送信個別リンク識別子が「５」であり、受信した集約リンクのインタフェースＩＰアドレスが「１３３．２０６．４０．２」であることから、個別リンク管理テーブル２４を検索し、個別リンク識別子が「３」の個別リンクが受信個別リンクであることを認識する。
【０１１９】
続いて、第１のＯＸＣ６１は転送経路リストの先頭が第２のＯＸＣ６２となっていることから、送信する集約リンクを特定し、当該集約リンクを構成する「未使用」の個別リンクの中で個別リンク識別子が「５」の個別リンクを送信個別リンクとして選択する。
【０１２０】
第１のＯＸＣ６１は受信個別リンクから送信個別リンクへ接続するようにスイッチマトリックスの設定予約を行う。最後に、第１のＯＸＣ６１は送信ＩＰアドレスを集約リンクの隣接インターフェースアドレスである「１３３．２０６．３０．３」に設定し、第２のＯＸＣ６２に対してシグナリングメッセージを送信する。
【０１２１】
尚、本発明の第４の実施例では、シグナリンクメッセージを送信するＯＸＣがシグナリングメッセージに送信個別リンク識別子を挿入し、シグナリングメッセージを受信したＯＸＣが個別リンク管理テーブルから送信個別リンク識別子に対応する個別リンク識別子を検索することによって使用リンクを特定している。
【０１２２】
しかしながら、シグナリングメッセージを送信するＯＸＣが予め送信個別リンク識別子に対応する隣接ルータリンク識別子を個別リンク管理テーブルから検索し、当該隣接ルータリンク識別子を宛先個別リンク識別子として、シグナリングメッセージに挿入することによって、シグナリングメッセージを受信したＯＸＣが個別リンク管理テーブルを参照することなく、リンク識別子が宛先個別リンク識別子と一致するリンクを使用することを認識するようにしても良い。
【０１２３】
また、各個別リンクに送信側と受信側とで同一の値となる共通リンク識別子を設定し、シグナリンクメッセージに当該共通リンクメッセージを挿入することによって、特に個別リンク管理テーブルを探索しなくても、使用する個別リンクを特定することができるようにする方法も考えられる。共通リンク識別子の設定方法の一例としては、両側のリンク識別子の値のうち、大きい方の値を使用する等の方法が考えられる。
【０１２４】
上記の集約リンク管理部２２においては、管理される集約リンクのメトリック値を個別リンク数（ＣＬＮ）に関係なく一定とするために、固定的なメトリック値を設定することも可能である。本発明の第５の実施例は上述した本発明の第１〜第４の実施例の集約リンク管理テーブル２５の集約リンク毎に固定的なメトリック値を設定するものである。集約リンク管理テーブル２５の集約リンク毎に固定的なメトリック値を設定した場合には、集約リンク管理部２２において管理される集約リンクのメトリック値が個別リンク数（ＣＬＮ）に関係なく、一定となる。
【０１２５】
上記によって、ある集約リンクの個別リンク数の変更が生じた場合にも、集約リンクのメトリック値が変化しないため、リンクステートルーティング処理部２６ではネットワークトポロジの変更が通知されず、トラフィックの流出が発生しないため、安定したルーティング処理を維持することが可能となる。
【０１２６】
このように、同一隣接ルータと接続する個別リンクを集約リンクとして扱うため、リンクステートルーティング処理部２６がルータ間に一本の集約リンクのみが接続されているものと判断し、リンクステート情報を生成するので、ルータ間の並列リンク数が増加した場合にも、ルータ間の生成するリンクステート情報量の増加を防止することができる。
【０１２７】
上記のように、リンクステート自体の情報量の増加が防止されるのと同時に、リンクステートトラフィックをフラッディングする個別リンクを集約リンクに対してただ一つだけ割当てているため、無駄にトラフィックが送受信されることがなくなり、ルータ間の並列リンク数が増加した場合にも、ルータ間の生成するリンクステートトラフィック量の増加を防止することができる。
【０１２８】
同一隣接ルータと接続する個別リンクは集約リンクとして扱われるため、リンクステートルーティング処理部２６がルータ間に一本の集約リンクのみが接続されているものと判断してリンクステートルーティングテーブル２８の算出処理を行うので、ルータ間の並列リンク数が増加した場合にもリンクステートルーティング処理部２６において計算するリンクステートルーティングテーブル２８の計算時間の増加を防止することができる。
【０１２９】
本発明の第５の実施例によれば、集約リンクに対して固定的なメトリックがつけられている場合、個別リンクの増減が発生しても、リンクステートルーティング処理部２６に通知する集約リンクのパラメータが変化しないため、個別リンクの変化をリンクステートルーティング処理部２６に隠蔽することが可能となるので、集約リンクに対して固定的なメトリックがつけられている場合、集約リンクを構成する個別リンクの数が変化した際にも、リンクステートトラフィックのフラッディング及びリンクステートルーティングテーブル２８の再計算が発生しないようにすることができる。
【０１３０】
パケット転送テーブルをリンクステートルーティングテーブル２８と個別リンクマッピングテーブル２９とに分離したことによって、個別リンクの状態が変化した際にルーティングプロトコル処理による低速なパケット転送テーブル更新を行う必要がなくなり、並列リンク管理部２０のみでパケット転送テーブルの更新を行うことが可能となるので、個別リンクに障害が発生したり、個別リンクの障害が復旧した場合のパケット転送テーブルを高速に更新することができる。
【０１３１】
本発明の第３の実施例によれば、個別リンク間のハローメッセージにおいて集約リンクのＩＰインタフェースアドレスの交換を行うので、集約リンクで接続される隣接ルータのＩＰインタフェースアドレスを予め設定しておく必要がなくなる。
【０１３２】
個別リンク間のハローメッセージにおいては個別リンクのインタフェース識別子の交換を行っているので、シグナリングで波長パスを設定するために個別リンクで接続される隣接ルータのインタフェース識別子を予め設定しておく必要がなくなる。
【０１３３】
したがって、現状のリンクステートプロトコル処理部に手を加えることなく、ルータ間の並列リンク数が増大した際にも、メモリ量、ＣＰＵ処理量、制御トラフィック量の増大を抑えてスケーラブルなルーティング処理を提供することができる。
【０１３４】
【発明の効果】
以上説明したように本発明によれば、ネットワークを構成する装置間の接続関係を報告し合うことによって自律分散的にリンクステートルーティングテーブルを作成するリンクステートルーティング処理手段を含むパケット転送経路制御装置において、装置間を接続する個別リンクを介して隣接装置との接続情報を学習するためのハローメッセージを交換して隣接装置を特定する隣接装置識別子及び前記隣接装置に接続するための隣接個別リンクを特定する隣接個別リンク識別子を学習し、同一の隣接装置識別子を持つ複数の個別リンクを１つの集約リンクとして管理してリンクステートルーティングテーブルに通知するとともに、リンクステートルーティング処理手段が集約リンク単位で処理を行うことによって、現状のリンクステートルーティング処理部に手を加えずに、ルータ間並列リンクにおけるルーティング処理のスケーラビリティ及び安定性を確保することができるという効果がある。
【図面の簡単な説明】
【図１】本発明の第１の実施例によるルータの構成を示すブロック図である。
【図２】図１のパケット転送経路制御装置の構成を示すブロック図である。
【図３】図２の個別リンク管理テーブルの構成例を示す図である。
【図４】図２の集約リンク管理テーブルの構成例を示す図である。
【図５】図２の個別リンクマッピングテーブルの構成例を示す図である。
【図６】図２の個別リンク管理部の動作を示すフローチャートである。
【図７】図２の集約リンク管理部の動作を示すフローチャートである。
【図８】図１のインタフェース部における転送リンク決定処理の動作を示す図である。
【図９】本発明の第１の実施例によるネットワークの構成を示すブロック図である。
【図１０】本発明の第１の実施例によるリンクステートルーティングモジュールの認識するネットワークの構成を示す図である。
【図１１】本発明の第１の実施例におけるハローメッセージによる隣接関係の確立例を示すシーケンスチャートである。
【図１２】本発明の第２の実施例による集約リンク管理テーブルの構成例を示す図である。
【図１３】本発明の第２の実施例による個別リンク管理部の動作を示すフローチャートである。
【図１４】本発明の第２の実施例による集約リンク管理部の動作を示すフローチャートである。
【図１５】本発明の第３の実施例による集約リンク管理テーブルの構成変化の一例を示す図である。
【図１６】本発明の第３の実施例による個別リンク管理部の動作を示すフローチャートである。
【図１７】本発明の第３の実施例による集約リンク管理部の動作を示すフローチャートである。
【図１８】本発明の第４の実施例によるネットワークの構成を示すブロック図である。
【図１９】図１８のＯＸＣにおける集約リンク管理テーブルの構成例を示す図である。
【図２０】図１８に示すネットワークにおいてリンクステートルーティング処理部によって認識されるネットワークの構成を示す図である。
【図２１】図１８に示すネットワークにおける波長パスの設定例を示す図である。
【図２２】図１８のＯＸＣにおけるシグナリングメッセージの処理手順を示すフローチャートである。
【図２３】（ａ）は図１８のＯＸＣにおける集約リンクの接続関係を示す図、（ｂ）は図１８のＯＸＣにおける個別リンクの接続関係を示す図である。
【符号の説明】
１，５１〜５６  ルータ
２  パケット転送経路制御装置
３  スイッチ部
４，４ａ〜４ｈ  インタフェース部
２０  並列リンク管理部
２１  個別リンク管理部
２２  集約リンク管理部
２３  インタフェース変換部
２４  個別リンク管理テーブル
２５，６１ａ  集約リンク管理テーブル
２６  リンクステートルーティング処理部
２７  個別リンクインタフェースドライバ部
２８  リンクステートルーティングテーブル
２９  個別リンクマッピングテーブル
４１  集約リンク選択処理部
４２  個別リンク選択処理部
６１〜６４  ＯＸＣ
７１  ＷＤＭ多重分離装置
１０１〜１０４  個別リンク
２０１〜２０８  集約リンク
３０１  ファイバ
【図１】
0003654158.tif 000002
【図２】
0003654158.tif 000003
【図３】
0003654158.tif 000004
【図４】
0003654158.tif 000005
【図５】
0003654158.tif 000006
【図６】
0003654158.tif 000007
【図７】
0003654158.tif 000008
【図８】
0003654158.tif 000009
【図９】
0003654158.tif 000010
【図１０】
0003654158.tif 000011
【図１１】
0003654158.tif 000012
【図１２】
0003654158.tif 000013
【図１３】
0003654158.tif 000014
【図１４】
0003654158.tif 000015
【図１５】
0003654158.tif 000016
【図１６】
0003654158.tif 000017
【図１７】
0003654158.tif 000018
【図１８】
0003654158.tif 000019
【図１９】
0003654158.tif 000020
【図２０】
0003654158.tif 000021
【図２１】
0003654158.tif 000022
【図２２】
0003654158.tif 000023
【図２３】
0003654158.tif 000024