(57)【特許請求の範囲】
【請求項１】
パケット転送装置であって、
複数の物理回線を束ねて論理回線として扱う送受信部と、
前記送受信部が出力するパケットを迂回させる予備の送受信部と、
出力ラベルと、前記論理回線の識別子とを対応付けて記憶する第１の記憶部と、
前記論理回線の識別子と、前記論理回線が含む前記物理回線の識別子を対応付けて記憶する第２の記憶部と、
前記第１の記憶部を参照し、前記第１の送受信部で受信したパケットのヘッダ情報に基づいて前記出力ラベルと前記論理回線を検索する出力ラベル検索部と、
前記第２の記憶部を参照し、前記ラベル検索部で検索された前記論理回線が含む前記物理回線を検索する物理回線検索部と、
前記送受信部で受信した第１の受信パケットのヘッダを基に検索された第１の物理回線が障害が発生していた場合、前記論理回線の中の前記第１の物理回線の送受信を停止させ、前記第１のパケットを前記予備の送受信部から送出する宛先判定部とを有することを特徴とするパケット転送装置。
【請求項２】
請求項１記載のパケット転送装置であって、
前記物理回線の障害を検出する障害検出部を有し、
前記障害検出部は、前記物理回線で障害を検知すると、前記第２の記憶部の前記物理回線の識別子を障害発生を示す値に更新することを特徴とするパケット転送装置。
【請求項３】
請求項２記載のパケット転送装置であって、
前記論理回線は、複数の物理回線のリンクアグリゲーションで構成されていることを特徴とするパケット転送装置。
【請求項４】
請求項３記載のパケット転送装置であって、
前記ラベルは、ＭＰＬＳのラベルであることを特徴とするパケット転送装置。
【請求項５】
パケット転送装置であって、
複数の物理回線を束ねて論理回線として扱う送受信部と、
前記送受信部が出力するパケットを迂回させる予備の送受信部と、
出力ラベルと、前記論理回線の識別子と、閾値を対応付けて記憶する第１の記憶部と、
前記論理回線の識別子と、前記論理回線が含む前記物理回線の識別子を対応付けて記憶する第２の記憶部と、
前記第１の記憶部を参照し、前記第１の送受信部で受信したパケットのヘッダ情報に基づいて前記出力ラベルと前記論理回線を検索する出力ラベル検索部と、
前記第２の記憶部を参照し、前記ラベル検索部で検索された前記論理回線が含む前記物理回線を検索する物理回線検索部と、
前記送受信部で受信した第１の受信パケットのヘッダを基に検索された前記論理回線が含む前記物理回線の数が閾値を下回った場合、前記第１のパケットを前記予備の送受信部から送出する宛先判定部とを有することを特徴とするパケット転送装置。
【請求項６】
請求項５記載のパケット転送装置であって、
前記物理回線の障害を検出する障害検出部を有し、
前記障害検出部は、前記物理回線で障害を検知すると、前記第２の記憶部の前記物理回線の識別子を障害発生を示す値に更新することを特徴とするパケット転送装置。
【請求項７】
請求項６記載のパケット転送装置であって、
前記論理回線は、複数の物理回線のリンクアグリゲーションで構成されていることを特徴とするパケット転送装置。
【請求項８】
請求項７記載のパケット転送装置であって、
前記ラベルは、ＭＰＬＳのラベルであることを特徴とするパケット転送装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット転送網におけるトラフィック保護機能を備えるパケット転送装置に関する。
【背景技術】
【０００２】
ネットワークを構成するノードやその物理回線の障害時に、通信の継続を実現する高可用化技術が開発されている。本技術の一例として、例えば、MPLS(Multi Protocol Label Switching)ネットワークの通信遮断を防止するファストリルート技術がある。非特許文献１には、パスであるLSP(Label Switching Path)（保護対象LSPと呼ぶ）を流れるトラフィックの保護方式として１対１バックアップ(one-to-one backup)方式とファシリティバックアップ(facility backup)方式が記載されている。１対１バックアップ方式では、保護対象LSPに１つの予備LSPが設定され、ファシリティバックアップ方式では、複数の保護対象LSPに１つの予備LSPが設定される。保護対象LSPが経由するノードや物理回線に障害が発生した時には、本LSPを流れるトラフィックは予備LSPへと迂回され、障害発生時の通信継続が実現される。
【０００３】
高可用化技術の別の例としては、例えば、非特許文献２記載のリンクアグリゲーション技術がある。本技術では、複数の物理回線を論理的な一つの回線（論理回線と呼ぶ）として扱い、複数の物理回線にフレームを振り分けて通信する。論理回線の一つの物理回線が故障しても少なくとも一つの物理回線は正常であるため、論理回線で接続されているスイッチ間の通信が途切れることはない。そのため、スイッチ間をリンクアグリゲーションの論理回線で接続することで、一物理回線が故障した時の通信継続が実現される。
【０００４】
【非特許文献１】IETF Internet Draft draft-ietf-mpls-rsvp-lsp-fastreroute-07.txt   “Fast Reroute Extensions to RSVP-TE for LSP Tunnels”
【非特許文献２】IEEE802.3ad
【発明の開示】
【発明が解決しようとする課題】
【０００５】
非特許文献２を適用したネットワークにおいては、論理回線の一部の物理回線に障害が発生した際には通信の継続は可能であるが、ノードに障害が発生すると通信が継続されないという問題がある。
【０００６】
一方、非特許文献1を適用したネットワークにおいては、ノード障害が発生した場合、予備LSPが障害ノードを経由しないのであれば、予備LSPを用いて通信は継続される。しかし、両LSP設定時には、個々のトラフィックに必要な通信品質(通信遅延など)を満たす経路が、保護対象LSP用の経路以外には存在しない場合も考えられる。この場合、ノードや物理回線に障害が発生すると、通信は継続されるが、予備LSPに迂回されたトラフィックの通信遅延が大きくなる場合や、トラフィックの一部が廃棄される場合がある。
【０００７】
そこで、ノード障害時の通信継続を実現しつつ、迂回するトラフィックを最小限に抑えて該トラフィックの通信品質劣化を最小限に抑えるパケット転送装置を提供することを一つの目的とする。
【課題を解決するための手段】
【０００８】
上記課題を解決するために、例えば、複数の入力回線と複数の出力回線と、該入力回線より入力するパケットのヘッダ内の情報から、少なくとも一つの出力回線から構成される第一の論理回線と第一の論理回線を構成する第一の出力回線を判定する宛先判定部を備え、前記第一の出力回線に該パケットを送信するパケット転送装置であって、前記宛先判定部が第一の論理回線の出力回線に障害が発生すると、前記第一の出力回線を第二の論理回線を構成する第二の出力回線に変更することを特徴とするパケット転送装置を提供する。
【０００９】
上記以外の本願が解決しようとする課題、その解決手段は、本願の「発明を実施するための最良の形態」の欄および図面で明らかにされる。
【発明の効果】
【００１０】
論理回線を構成する一部の物理回線に障害が発生すると、障害回線の帯域分のトラヒックを迂回すれば良く、論理回線の総帯域分のトラヒックを迂回する必要が無い。そのため、迂回するトラフィックを最小限に抑えて該トラフィックの通信品質劣化を最小限に抑えることができる。また、ノード障害が発生すると、論理回線を流れるトラヒックを全て迂回することで、通信継続も実現できる。
【発明を実施するための最良の形態】
【００１１】
以下、図１から図１０を用いて本発明に好適な実施形態の例を説明する。ただし、本発明は本実施形態に限定されるものではない。
【００１２】
（１）ネットワークの概要
図１０は、本実施例における網構成の一例を示す。図１０中のIP網AからIP網Eはそれぞれ異なるIP網である。LER1からLER4はラベルエッジルータ（Label Edge Router :LER）であり、IP網から送られてきたIPパケットに、宛先IPアドレスや宛先ポート番号などの情報を集約したラベルを付加し、MPLSパケットとしてMPLS網内に送信する機能を備えている。ラベルはMPLS網内でトラフィックの明示的な経路（LSP）を識別する情報である。また、MPLS網内から送られてきたMPLSパケットからラベルを削除し、IPパケットとしてIP網に送信する機能を備えている。R1からR5はMPLSコアルータ（MPLS Core Router）であり、MPLSパケットをラベルの値に基づき転送（ラベルスイッチ）する機能を備えている。R-AからR-EはIPルータであり、IPパケットを転送する機能を備えている。R1とR2は1Gbpsの物理回線3本で接続されており、この3本の物理回線を集約（例えば、リンクアグリゲーションによるグループ化）し、3Gbpsの帯域幅を持つ1本の論理回線Aとして扱かっている。その他のルータ間は、それぞれ10Gbpsの回線で接続されている。R1において、論理回線Aを構成する物理回線番号は1番から3番であり、R4と接続する物理回線番号は4番である。
【００１３】
LSP１、LSP2、LSP3は、LER1、R1、R2，R3、LER2を通るLSPであり、それぞれのLSPには1Gbpsの帯域が予約されている。IP網B内のホストとIP網E内のホストが通信を行うためのパスとして、LER2、R4、R5、LER4を経路とするLSP_Aが設定されており、最大8Gbpsの帯域が予約されている。また、R1、R2を接続する回線の回線障害および、R3の障害に備え、保護対象LSP1、LSP2、LSP3の予備LSPとしてLSP_backup が設定されている。それぞれのLSP_backupはR1、R4、R5、R3を通るパスである。LSP_backupには3Gbpsの帯域が予約されている。
【００１４】
IP網A内のホストとIP網B、IP網C、IP網E内のホストが通信を行うため、R-AはLER1と、R-C、R-D、R-EはLER3と接続されている。IP網A内から発信されるIP網C、IP網D、IP網E宛のIPトラフィックは、LER1で宛先ごとに異なるラベルを付加され、それぞれ、該ラベルに対応したLSP１、LSP2、LSP3に沿って転送される。
【００１５】
LSP１、LSP2、LSP3は、IP網AからIP網Ｃ、IP網Ｄ、IP網Eへ流れるトラフィックの特性を考慮した最適パスである。また、LSP_backup とLSP_Aは、R4とR5を接続する回線において帯域を共有している。R4とR5を接続する回線帯域10Gbpsに対し、LSP_backupの予約帯域とLSP_Aの予約帯域は11Gbpsであり、オーバーサブスクライブ（利用可能な帯域幅を越えた帯域予約）となっている。このため、LSP_backupの予約帯域分のトラフィックとLSP_Aの予約帯域分のトラフィックが同時に、R4とR5を接続する回線帯域に流れ込むと、帯域幅を超えて遅延、輻輳が発生する可能性がある。
【００１６】
R1は、論理回線Aを構成する物理回線に障害が起きた場合、LSP1、LSP2又はLSP3に流れるトラフィックをLSP_backupに迂回する。論理回線Aを構成する物理回線に障害が発生し、R１がLSP1に流れるトラフィックをLSP_backupに迂回する場合を例に挙げる。論理回線Aを構成する物理回線全てがリンクアップしている場合、LSP1、LSP2、LSP3のトラフィックはそれぞれ、物理回線番号1、物理回線番号2、物理回線番号3が出力物理回線として選択される。R1は、物理回線番号1の回線に障害が起きたとき、LSP1に流れるトラフィックのみをLSP_backupに迂回する。
【００１７】
仮に、R1とR2が10Gbpsの物理回線1本で接続されている場合、該物理回線が障害を起こすと、LSP1、LSP2、LSP3 を流れる全てのトラフィックは、LSP_backupに迂回する。R4とR5を接続する回線にLSP_Aを通る8Gbpsのトラフィックが流れていた場合、遅延、輻輳が生じてしまう。また、R2に障害が発生したときは、論理回線Aを構成するすべての物理回線で通信不能になるので、LSP１、LSP2、LS3に流れるトラフィックすべてがLSP_backupに迂回する。これに対し本実施例では、回線障害に応じてトラフィックをLSP_backupに迂回するので、論理回線Aを構成する物理回線全てに障害発生、又はR2に障害発生しない限りR4とR5を接続する回線における輻輳は発生しない。また、LSP2、LSP3を流れるトラフィックには変化がなく、引き続き最適なパスがトラフィックの転送路として選択される。
【００１８】
また、R1はLSP毎に迂回優先度を蓄積して、該迂回優先度に基づきトラフィックを迂回する手段を備えている。例えば、LSP1にはVoIPトラフィック、LSP2にはメールトラフィック、LSP3にはファイル転送トラフィックが流れているとする。LSP2のメールトラフィックは遅延や輻輳に対して敏感ではないので、R1の管理者はLSP2の迂回優先度を最大値に設定する。LSP1を流れるVoIPトラフィックは遅延に弱いので、R1の管理者はLSP1の迂回優先度を最小値に設定する。LSP3の迂回優先度はLSP1とLSP3の迂回優先度の中間に設定する。R1は、論理回線Aを構成する物理回線に障害が発生したとき、健全な物理回線数と迂回優先度を比較し、不等式、(物理回線数)＜(LSPの迂回優先度)が成り立つLSPに流れるトラフィックから迂回を開始する。上記例では、R１は遅延の影響が少ないメールトラフィックから迂回を開始し、遅延に弱いVoIPトラフィックは継続して最適パスで転送を続ける。
【００１９】
このように、R1は、論理回線Aを構成する物理回線に障害が発生したとき、該物理回線が出力回線として選択されるトラフィックを予備LSPに迂回する。該トラフィック以外の前記論理回線に流れるトラフィックに変化は生じないため、最適でないパスを通るトラフィックを最小限に抑えることが出来る。また、障害発生した回線を流れるトラフィックのみを予備LSPに迂回するため、迂回先での輻輳発生（パケット廃棄）を抑えることが出来る。
（２）ルータの概要
図２は、R1として適用されるルータ200の構成例を示すブロック図である。ルータ200はNの回線部210-i (i=1からN)と、各回線部210が収容する2Nの物理回線201-ij (i=1からN, j=1 or 2)、回線部210-iを結合する一つのパケット中継処理部250と、一つのプロセッサ280から構成される。回線部210-iは、パケットの送受信処理を行うパケット送受信回路230と、回線障害を検出する回線障害検出部240と、本発明固有の宛先判定部100と、ARPテーブル検索部220とから構成される。以下、図８と図５も用いつつルータ200の動作の概要を説明する。
【００２０】
図８上部は、物理回線201から入出力されるパケットのフォーマットの一例を示す。本フォーマットは、ヘッダ部810とデータ部820から構成される。データ部820はユーザデータ821より構成される。ヘッダ部810は、データリンク層の送信元アドレスである送信先MACアドレス811（Destination MAC Address：以下「DMAC」という）と、送信元アドレスである送信元MACアドレス812（Source MAC Address：以下「SMAC」という）と、MPLS網内でパケットの転送先を示すラベル813と、送信元IPアドレス(Source IP address)を示すSIP814と、送信先IPアドレス(Destination IP address)DIP815とから構成される。
【００２１】
また、図８下部にルータ200の内部パケットフォーマットの一例を示す。本フォーマットは図８上部で前述のパケットフォーマットに内部ヘッダ部830が追加される。この内部ヘッダ部830は、パケットを出力する物理回線の番号である出力回線番号831と、該パケットを出力する際パケットに書き込む出力ラベル832と、ラベル813に対するラベル操作833と、該パケットを受信する次のルータ又は端末のIPアドレスである次ホップIPアドレス834（Next Hop IP Address：以下「NHIP」という）とから構成される。ここでラベル操作とは、ラベルを一つスタックするプッシュ(PUSH)、ラベルを一つ外すポップ(POP)、ラベル813と出力ラベル832を交換するスワップ(SWAP)の3種類である。
【００２２】
図５は、図２のパケット送受信回路230の構成例を示すブロック図である。物理回線201よりパケットを入力すると、内部ヘッダ付加回路510が内部ヘッダ部830を付加し、本パケットをパケットバッファ520に書き込む。パケットヘッダ送信部540Aは、パケットバッファ520内のパケットヘッダ部810をパケットヘッダ情報21として、図２の宛先判定処部100に送信する。このとき、内部ヘッダの各フィールドは意味の無い値となっており、後にヘッダ書き込み回路550Aにより意味のある値が書き込まれる。
【００２３】
パケット送受信回路230よりパケットヘッダ情報21を受信した宛先判定部100は、パケットヘッダ情報21内のパケットヘッダ810の少なくとも一つの情報に基づき宛先判定処理を行い、パケット送受信回路230内のヘッダ書き込み回路550Aにパケット出力回線情報22を送信する。パケットヘッダ810内の情報のとして、MPLSコアルータの場合はラベル813であり、入り口エッジルータの場合は送信先IPアドレス(Destination IP address)DIP815や(Destination MAC address)DMAC811などがある。本実施例では、R1をMPLSコアルータとして、パケットヘッダ810内のラベル813に基づく宛先判定処理について説明をする。
【００２４】
パケット出力回線情報22は、出力ラベル、ラベル操作、物理回線201に割り振られた回線番号、ネクストホップIPアドレスの少なくとも一部を含む。出力回線が複数の物理回線を集約した論理回線である場合、該物理回線のうち1回線を出力回線として選択する。例えば図１０の場合、LER１からラベル20が付加されたパケットを受信すると、次ホップIPアドレスはR2の論理回線Aに割り振られた192.168.0.2、出力ラベル200、出力回線番号は論理回線Aを構成する物理回線に割り振られた番号の中から選択される。出力物理回線番号の選択方法の例として、1から3のいずれかの値を出力するハッシュ関数を用いる方法がある。
【００２５】
また宛先判定部100は、論理回線を構成する物理回線に障害が発生した場合、保護対象ラベル（保護対象LSPに沿って転送されるパケットに付加されるラベル）が付加されたパケットに予備ラベル（予備LSPに沿って転送されるパケットに付加されるラベル）を付加し、予備LSPに迂回する機能を備えている。
【００２６】
回線障害検出部240は、各回線の状態を常時監視している。回線障害検出部240は回線障害を発見すると、障害が発生した回線の物理回線番号を障害発生回線番号情報25として回線部210-1から210-N内の宛先判定部100に送信する。図２中では省略してあるが、回線部210-2から210-Nから全ての回線部210に対し、障害発生回線番号情報25が結線されている。
【００２７】
宛先判定部100は障害発生回線番号情報25を受信すると、障害発生回線番号情報25が論理回線を構成している物理回線番号であった場合、論理回線を縮退（論理回線を構成する物理回線を減らし、残帯域を減少）させる。宛先判定部100は、入力パケットの出力回線が上記論理回線であり、かつ、上記処理で回線障害と認識した回線が出力回線として選ばれた場合、該パケットに予備ラベルを付加し、予備ラベルに対応する出力回線から出力する。また、宛先判定部100は、保護対象ラベル毎に設定された迂回閾値に基づき、パケット迂回を実行するモードも備える。該モードの詳細については後に説明する。
【００２８】
パケット送受信回路230のヘッダ書き込み回路550Aはパケット出力回線情報22を受信すると、パケット出力回線情報22内の出力回線番号、出力ラベル、ラベル操作、次ホップIPアドレスをそれぞれ出力回線番号831と出力ラベル832とラベル操作834とNHIP 835の各フィールドに書き込む。パケット読み出し回路560は、パケットバッファ520から蓄積されているパケットを読み出して、パケット中継処理部250へ送信する。
【００２９】
パケットを受信したパケット中継処理部250は出力回線番号831に対応する回線部210のパケット送受信回路230に該パケットを送信する。パケット送受信回路230は本パケットをパケットバッファ530に蓄積する。パケットヘッダ送信部540Bは、本パケットの内部ヘッダ部830のNHIP834を次ホップIPアドレス情報23としてARPテーブル検索部220に送信する。
【００３０】
ARPテーブル検索部220は次ホップIPアドレス情報23に対応する次ホップルータのMACアドレスを備え、次ホップIPアドレス情報23を受信すると対応するMACアドレスを次ホップMACアドレス情報24としてヘッダ書き込み回路550Bに送信する。ヘッダ書き込み回路550Bは本情報24内のMACアドレス、出力回線番号831に対応する物理回線に割り当てられたMACアドレスをそれぞれ、パケットバッファ530内のパケットのDMAC811、SMAC812に書き込む。該出力物理回線が論理回線の一部である場合、該論理回線に割り振られたSMACがSMAC812に書き込まれる。
【００３１】
続いて、ラベル操作833に従いラベル813の書換えを行う。ラベル操作833がSWAPを示す場合には、ラベル813を出力ラベル833で上書きをする。PUSHの場合はSMAC812とラベル813の間に出力ラベル832を挿入する。POPの場合は、単にラベル813を削除し、SMAC812の直後にデータ821を移動させる。最後に、パケット読み出し回路560は、内部ヘッダ部830を削除し、蓄積したパケットを出力回線番号831に対応する入出力回線201に送信する。
【００３２】
以上に示したように、宛先判定部100は、論理回線を構成する物理回線に障害が発生したとき、該論理回線を縮退させる。入力パケットの出力回線に、上記障害発生した回線が選ばれた場合、該パケットに予備ラベルを付加し、予備ラベルに対応する物理回線又は論理回線から出力することで、出力先を予備ラベルに対応する宛先へ変更することが出来る。複数の保護対象ラベルの出力先が論理回線に設定されているとき、予備LSPへ迂回するトラフィックを障害発生した回線に応じて分割できる。このため、最適でないパスを流れるトラフィックを最小限に抑えることができる。
【００３３】
（３）トラフィック一部迂回方式
図１は、図２の宛先判定部100の構成例を示すブロック図である。宛先判定部100は、出力ラベル検索部101、出力物理回線番号検索部102、入力ラベル蓄積部103、出力ラベル検索起動部104、迂回判定部105から構成される。
【００３４】
図３は、図１の出力ラベル検索部の構成例を示すブロック図である。出力ラベル検索部101は、保護対象LSPに対応する出力ラベルテーブル300A、予備LSPに対応する出力ラベルテーブル300B、これらのテーブルの検索制御を行う出力ラベルテーブル制御部310より構成される。出力ラベルテーブル300A、Bの一例を図６に示す。出力ラベルテーブル300Aは、入力ラベルに対応する出力ラベル、ラベル操作、NHIP、出力回線番号、迂回閾値、論理回線ビットより構成される。迂回閾値はLSPごとの迂回閾値を表す。迂回閾値の使用法については後に説明する。論理回線ビットは、出力回線が複数の物理回線を束ねた論理回線であることを示す。論理回線ビットが‘1’のとき、出力回線番号は論理回線番号になる。論理回線ビットが‘0’のとき、出力回線番号は入出力物理回線に割り振られた番号になる。出力ラベルテーブル300Bは、出力ラベルテーブル300Aの構成要素より論理回線ビットの列を除いたものに等しい。
【００３５】
宛先判定部100は、パケットヘッダ情報21を受信すると、入力ラベル813の情報を入力ラベル蓄積部103に蓄積する。次に、出力ラベル検索起動部104が出力ラベル検索部101に検索指示し、入力ラベル蓄積部内103の入力ラベル813を検索キーとして送信する。
【００３６】
出力ラベル検索部101の出力ラベルテーブル制御部310は、出力ラベル検索起動部104からの出力ラベルテーブル検索指示と入力ラベル813を受信すると、入力ラベル813の値を出力ラベルテーブル300A、出力ラベルテーブル300Bのエントリのアドレスとして扱い、該アドレスのエントリを読み出す。このとき、出力ラベルテーブル300A、出力ラベルテーブル300Bの両エントリ情報を読み出す。例えば、入力ラベルの値が20であった場合、出力ラベルテーブル300A、出力ラベルテーブル300Bのアドレス20のエントリを読み出す。出力ラベルテーブル300A、出力ラベルテーブル300Bから読み出したエントリ情報、有効ビット、出力ラベル、ラベル操作、NHIP、出力回線番号、迂回閾値、論理回線ビットを迂回判定部105に送信する。
【００３７】
迂回判定部105は、出力ラベル検索部101から受信したラベルテーブル300A、出力ラベルテーブル300Bのエントリ情報の有効ビットを確認する。有効ビットが‘0’を示す場合、エントリ情報は無効であることを示す。両テーブルのエントリ情報が無効である場合、出力先無しとして、入力パケットは最終的に廃棄される。出力ラベルテーブル300Bのエントリ情報が無効であった場合、入力パケットに対する予備ラベルは存在しないため、迂回パスも存在しないことになる。出力ラベルテーブル300Aのエントリ情報が無効で出力ラベルテーブル300Bのエントリ情報が有効の場合、入力パケットの出力先は出力ラベルテーブル300Bのエントリ情報に従う。つなり迂回パスへ出力するよう判定する。
【００３８】
出力ラベルテーブル300A又はBのエントリ情報が有効である場合、迂回判定部105は、該エントリ情報の論理回線ビットが‘1’であるか確認する。出力ラベルテーブル300A又はBのエントリ情報の論理回線ビットが‘1’を示している場合、出力回線番号は論理回線であることを示している。迂回判定部105は、出力回線番号が示す論理回線を構成する物理回線の中から出力回線を決定するため、出力回線検索部102に検索指示と出力ラベルテーブル300のエントリ情報の出力回線番号を送信する。迂回判定部105は出力回線検索部105に検索指示を出すとともに、物理回線を選択する情報として、例えば、入力パケットのヘッダ部810を送信する。以上の出力回線検索部105への検索指示は、出力ラベルテーブル300A及びBのどちらか一方、又は、両方のエントリ情報の論理回線ビットが‘1’であった場合に行う。本実施例では、出力ラベルテーブル300Aの検索結果の出力回線が、論理回線の場合について説明を行う。
【００３９】
次に、図１の出力回線検索部102の構成例を図４に示す。出力物理回線番号検索部102は、物理回線テーブル410と物理回線テーブル制御部400とより構成される。
【００４０】
図４の物理回線テーブル410の一例を図７に示す。物理回線テーブル410は、論理回線を構成する物理回線を管理しているテーブルである。物理回線テーブル410は、エントリの有効ビット、論理回線番号、論理回線を構成する物理回線の数を示す物理回線数、論理回線を構成する物理回線の番号が記録されている物理回線番号フィールドより構成される。物理回線番号フィールドの各フィールドには物理回線番号が蓄積されている。物理回線番号フィールドに蓄積されている物理回線番号が‘0’である場合、物理回線に割り振られる番号は1から2Nなので、該出力回線は障害により通信不能であることを示す。
【００４１】
物理回線テーブル制御部400は、検索指示と入力パケットのヘッダ部810を受信すると、テーブルエントリをアドレスが小さい順に読み出す。読出したエントリの論理回線番号と迂回判定部105から受信した出力回線番号を比較し、最初に一致したエントリを検索結果として採用する。次に該エントリの物理回線番号フィールドの中から、一つの物理回線回線番号を判定する。物理回線回線番号を判定する方法としては、例えば、ハッシュ関数Hn(x)を用いた方式が考えられる。Hn(x)は引数xに対してハッシュ値として1からnの中から一つの整数を出力する。出力回線テーブル制御部400は、物理回線テーブル410の検索により得られた有効な出力回線数である‘n’と対応したハッシュ関数Hn(x)を選択する。例えば、出力回線数‘3’の場合にはハッシュ関数H3(x)を選択する。
【００４２】
本実施例ではHn(x)の引数として、迂回判定部105から受信したパケットヘッダ部810内のラベル813を使用する。出力回線テーブル制御部400は、Hn(x)結果が指す前記処理で読み出した物理回線番号フィールドに格納されている物理回線番号を出力回線番号として選択する。出力回線テーブル制御部400は、出力回線番号が決定すると、迂回判定部105に前記処理で読み出した出力回線テーブル410のエントリの物理回線数と、物理回線番号を送信する。
【００４３】
迂回判定部105は、物理回線テーブル制御部400から出力回線番号と出力回線数を受信すると、該出力回線番号が‘0’であるか判定する。該出力回線番号が‘0’であった場合、該出力回線番号に該当する物理回線は障害により通信不能であるものとして、パケット出力回線情報22にラベルテーブル300Bの検索結果を採用する。該出力回線番号が‘0’以外の値であった場合、出力ラベル検索部101から受信したラベルテーブル300Aのエントリ情報をパケット出力回線情報22に採用する。迂回判定部105は、上記処理で採用したラベルテーブル300A、又はBの検索結果である出力ラベル、ラベル操作、NHIP、出力回線判定部105から受信した出力回線番号を、パケット出力回線情報22としてパケット送受信回路230に送信する。
【００４４】
以上に宛先判定部100におけるトラフィック迂回方法を説明した。次に、宛先判定部100における物理回線障害発生時の処理について説明を行う。
【００４５】
宛先判定部100内の出力回線テーブル制御部400は、障害回線番号情報25を受信すると、該障害回線番号情報25をキーに出力回線テーブル410の検索を行う。出力回線テーブル410の出力回線番号フィールド内に該回線番号を発見すると、該出力回線番号フィールドに蓄積されている出力回線番号を‘0’に書き換える。上記処理は、迂回判定部105での迂回判定処理において、前記障害回線番号情報25に相当する物理回線が、障害により通信不能であると判定するための処理である。例えば、物理回線番号‘1’が通信不能になったとき、図７に示す物理回線テーブル410のエントリ410-1の物理回線番号フィールド‘1’に蓄積されている値を‘0’にする。
【００４６】
以上に示したように宛先判定部100は、保護対象LSPに相当する出力ラベルテーブル300Aと、予備LSPに相当する出力ラベルテーブル300Bを備える。読み出した出力ラベルテーブル300Aのエントリ情報の出力回線が論理回線のとき、論理回線を構成する物理回線の一つを出力回線として選択する。該物理回線に障害が発生していた場合、出力ラベルテーブル300Bのエントリ情報を入力パケットの宛先とし、パケットの迂回を実現する。このためルータ200は、論理回線Aを構成する物理回線に障害が発生したとき、該物理回線が出力回線として選択されるパケットを、予備ラベルに対応する健全な回線から出力することができる。該パケット以外の前記論理回線に流れるパケットに変化は生じないため、最適でないパスを通るトラフィックを最小限に抑えることができる。また、障害発生により通信不能となった回線を流れるトラフィックのみを予備LSPに迂回するため、迂回先での輻輳発生（パケット廃棄）を抑えることが出来る。また、ネクストホップのノード障害時は、該ネクストホップノードに接続されている全ての物理回線の物理回線番号が、物理回線テーブル410において‘0'になるため、該論理回線を流れるすべてのトラフィックは予備LSPに迂回する。
【００４７】
ルータ200の管理者は、ルータ200外部の管理端末10から出力ラベルテーブル300の設定を行う。出力ラベルテーブル300A、Bに設定する際に、管理端末10に入力されるコマンドの一例を図９に示す。図９のコマンド901は、入力ラベル20に対するコンフィグを開始することをルータ200の宛先判定部100に伝える。コマンド910は入力ラベル20に対する宛先を設定する。字句911は入力ラベル20に対し出力ラベル200をSWAPすることを宣言している。字句912は入力ラベル20のネクストホップIPアドレスは192.168.0.2であることを宣言している。字句913は出力回線の設定で、論理回線la1が出力回線であることを宣言している。コマンド910を制御端末10から入力すると、プロセッサ280を介してコマンドを受け取った、出力ラベルテーブル310は出力ラベルテーブル300Aの出力ラベルに200、ラベル操作にSWAP、NHIPに192.168.0.2、出力回線番号に‘1’、論理回線ビットに‘1’、有効ビットに‘1’を書き込む。次にコマンド920は、入力ラベル20に対する予備LSPを設定する。字句921は予備LSPを設定開始の字句である。字句922は出力ラベル2000であることを宣言している。字句923は入力ラベル20のネクストホップは192.168.5.2であることを宣言している。字句924は出力回線番号が‘4’であることを宣言している。コマンド920を制御端末10から入力すると、プロセッサ280を介してコマンドを受け取った、出力ラベルテーブル310は出力ラベルテーブル300Bの出力ラベルに2000、ラベル操作にSWAP、NHIPに192.168.5.2、出力回線番号に‘4’、論理回線ビットに‘0’、有効ビットを‘1’を書き込む。
【００４８】
（４）優先度付き一部迂回方式
次に、宛先判定部100における出力ラベルテーブル300Aの各エントリに蓄積する迂回閾値に基づくトラフィック迂回判定の実施例について説明する。該トラフィック迂回法は、論理回線を構成する物理回線に障害が発生したとき、トラフィックの特性に応じてトラフィック迂回の順序を変更できる。例えば、遅延に強いトラフィックから迂回を開始し、遅延に弱いフィックは継続して最適パスで転送を続けることができる。宛先判定部100は、迂回に関するモード蓄積部106を備える。宛先判定部100は、迂回に関する2値のモード情報が蓄積されているモード蓄積部106を備える。該モード情報は、出力回線テーブル制御部400の動作モードを表現している。出力回線テーブル制御部400はモード蓄積部106に蓄積されたモード情報を参照する。出力物理回線番号検索部102と出力回線テーブル制御部400は、モード蓄積部106に蓄積されたモード情報に基づきトラフィック一部迂回方式、または、優先度付き一部迂回方式で動作するかを判断する。
【００４９】
まず、物理線検索部102における回線障害発生時の処理を説明する。出力物理回線番号検索部102内の出力回線テーブル制御部400は、障害回線番号情報25を受信すると、該回線番号を検索キーに物理回線テーブル410の検索する。物理回線テーブル410のアドレスの小さい順に各エントリを読み出し、該エントリの物理回線番号フィールドに蓄積している出力回線番号と障害回線番号情報25を比較する。障害回線番号情報25と、物理回線番号フィールドに蓄積している物理回線番号が一致した場合次の処理を行う。アドレスNの出力物理回線番号フィールドMに障害回線番号情報25と一致する物理回線番号が蓄積されていたとする。アドレスNのエントリの物理回線番号数が指す物理回線番号フィールド、つまり、最後の物理回線番号フィールドの物理回線番号を読み出す。続いて、物理回線番号フィールドの最後の値をアドレスNの出力回線番号フィールドMに書きこみ、出力回線番号フィールドの最後の値に‘0’を書き込む。アドレスNの出力回線番号数から‘１’を引く。上記処理を行うことで、論理回線を構成する物理回線を減らし、迂回判定部105において、迂回閾値に基づいたトラフィック迂回処理を行うことができる。
【００５０】
次に、迂回判定部105におけるトラフィック迂回判定処理について説明する。迂回判定部105は、物理回線テーブル制御部400から物理回線番号と物理回線数を受信すると、該物理回線数と、出力ラベルテーブル制御部310から受信した、出力ラベルテーブル300Aのエントリ情報の迂回閾値との比較を行う。該物理回線数が該迂回閾値を下回っていた(出力回線数＜迂回閾値)場合、出力ラベルテーブル300Bのエントリ情報をパケット出力回線情報22としてパケット送受信回路230に送信する。該出力回線数が該迂回閾値と同等以上(出力回線数≧迂回閾値)の場合、出力ラベルテーブル300Aの検索結果をパケット出力回線情報22としてパケット送受信回路230に送信する。物理回線数テーブル制御部400から受信した物理回線数は、論理回線の残帯域又は残物理回線本数を表現している。出力ラベルテーブル300Aに設定した迂回閾値と、該物理回線数を比較することで、パケット出力回線情報22に、出力ラベルテーブル300A又はBの検索結果を採用するか決定する。例えば、図6の出力ラベルテーブル300の状態のとき、ラベル20が付加されたパケットを受信した場合、迂回閾値は3になる。図7の物理回線テーブル410では物理回線数が3なので(出力回線数≧迂回閾値)の条件が成立し、出力物理回線は`1'、`2'、`3'のどれかになる。また、同条件でラベル21のパケットを受信したときは(出力回線数＜迂回閾値)が成立するので、出力回線は出力ラベルテーブル300Bのアドレス21エントリの出力回線番号`4'が採用される。
【００５１】
なお、選んだ物理回線の有効ビットを逐次見る方法（一部迂回方式）と、有効な物理回線の数と迂回優先度とを比較する方法（優先度付き一部迂回方式）とは、本実施例ではモードを切り替えることとし同時に実現していないが、例えば物理回線テーブル410のエントリ毎にモードビットを持たせれば同時に実現できる。ただし、この場合、モードが論理回線に括り付けになり、トラフィック（フロー）毎のモードの変更はできない。
（5）ユーザーインターフェース  また、迂回閾値をルータ200に設定する際の、管理端末10に入力されるコマンドの一例を図９に示す。図９のコマンド931は、入力ラベル20に対するコンフィグを開始することをルータ200の宛先判定部100に伝える。コマンド940は入力ラベル20に対する宛先を設定する。字句941は入力ラベル20に対し出力ラベル200をSWAPすることを宣言している。字句942は入力ラベル20のネクストホップIPアドレスは192.168.0.2であることを宣言している。字句943は出力回線の設定で、論理回線論理回線1が出力回線であることを宣言している。字句944は迂回閾値が‘10’であることを宣言している。コマンド940を制御端末10から入力すると、プロセッサ280を介してコマンドを受け取った、出力ラベルテーブル310は出力ラベルテーブル300Aの出力ラベルに200、ラベル操作にSWAP、NHIPに192.168.0.2、出力回線に論理回線番号‘1’、迂回閾値に‘3’、論理回線ビットに‘1’、有効ビットに‘1’を書き込む。次にコマンド950は、入力ラベル20に対する予備LSPを設定する。字句951は予備LSPを設定開始することを宣言している。字句952は出力ラベル2000であることを宣言している。字句953は入力ラベル20のネクストホップは192.168.5.2であることを宣言している。字句954は出力回線番号が物理回線番号4番であることを宣言している。コマンド920を制御端末10から入力すると、プロセッサ280を介してコマンドを受け取った、出力ラベルテーブル310は出力ラベルテーブル300Bの出力ラベルに2000、ラベル操作にSWAP、NHIPに192.168.5.2、出力回線番号に‘4’、論理回線ビットに‘0’、有効ビットを‘1’を書き込む。
【図面の簡単な説明】
【００５２】
【図１】図２の宛先判定部100の構成例を示すブロック図。
【図２】図１０のR1に相当するルータ200の構成例を示すブロック図。
【図３】図１の出力ラベル検索部101の構成例を示すブロック図。
【図４】図１の出力物理回線番号検索部102の構成例を示すブロック図。
【図５】図１のパケット送受信回路230の構成例を示すブロック図。
【図６】図３の出力ラベルテーブル300A、Bの一例を示すテーブル図。
【図７】図４の物理回線テーブル410の一例を示すテーブル図。
【図８】ルータ200が送受信するパケット、及び、ルータ200内部のパケットフォーマットの一例。
【図９】出力ラベルテーブル300A、Bを設定するための入力コマンドの一例。
【図１０】MPLS網の一例。
【符号の説明】
【００５３】
100…宛先判定部
101…出力ラベル検索部
102…物理回線検索部
200…ルータ
230…パケット受信回路
240…回線障害検出部
300…出力ラベルテーブル300
410…物理回線テーブル
21…パケットヘッダ情報
22…パケット出力回線情報
23…次ホップIPアドレス情報
24…MACアドレス情報
25…障害回線番号情報25
【図１】
0004491397.tif 000002
【図２】
0004491397.tif 000003
【図３】
0004491397.tif 000004
【図４】
0004491397.tif 000005
【図５】
0004491397.tif 000006
【図６】
0004491397.tif 000007
【図７】
0004491397.tif 000008
【図８】
0004491397.tif 000009
【図９】
0004491397.tif 000010
【図１０】
0004491397.tif 000011