(57)【特許請求の範囲】
【請求項１】
ラベル・スイッチ・ネットワークで多数のリンクを管理するシステムにおいて、
複数の入力仮想リンクと複数の出力仮想リンクとを含み、入力又は出力仮想リンク各々が複数の個別のリンクを有する複数の仮想リンクと、
各々のイングレス・ノードがパケットを受信して付属のラベルを前記パケットにラベル付けするように構成された複数のイングレス・ノードと、
各々のラベル・スイッチング・ノードが１つまたはそれ以上の入力仮想リンク経由で各々に関連したラベルを有する前記ラベル付けされたパケットを受信して前記受信したラベル付けされたパケットを１つまたはそれ以上の出力仮想リンク経由で各々に関連するラベルに基づいて転送するように構成され、各ラベル・スイッチング・ノードはさらに前記関連ラベルに関するラベル情報を管理する制御コンポーネントと前記受信したラベル付けされたパケットを前記ラベル情報に基づいて転送するように構成された転送コンポーネントとを含む複数のラベル・スイッチング・ノードと、
各エグレス・ノードが前記複数のラベル・スイッチング・ノードの一つから転送された前記ラベルのついたパケットを受信するように構成される複数のエグレス・ノードとを含み、
１つまたはそれ以上のラベル・スイッチング・ノードがラベル・スイッチ経路に属し、仮想リンクを使用して前記ラベル・スイッチ経路に属する前記識別されたラベル・スイッチング・ノードを相互接続し、
さらに、前記ラベルのついたパケットの少なくとも一つは、初期シグナリング処理で設定される付属のラベルを変更することなしに、出力仮想リンク内の前記複数の個別リンクのいずれか一つへ転送されることが可能であることを特徴とすることを特徴とするシステム。
【請求項２】
出力仮想リンク内の前記個別のリンクのどれを使って前記受信したパケットを転送するかの詳細が前記制御コンポーネントから隠蔽されることを特徴とする請求項１に記載のシステム。
【請求項３】
ラベル・スイッチ・ネットワークにおいてラベル・スイッチ経路を設定するためのシステムであって、
複数のリンクと、
前記複数のリンク経由で互いに相互接続される複数のノードとを含み、
ラベル・スイッチ経路は前記ラベル・スイッチ・ネットワーク経由でパケットを送信するために識別され１つまたはそれ以上のノードを相互接続する１つまたはそれ以上のリンクから構成されることと、
前記ラベル・スイッチ経路内の前記１つまたはそれ以上のリンクは１つまたはそれ以上の仮想リンクを含むことと、
前記１つまたはそれ以上の仮想リンクの各々が１つまたはそれ以上の物理リンクから構成され、
さらに、前記ラベル・スイッチ経路の各ノードはこれに接続された１つまたはそれ以上のリンク経由で各々のラベルを有するパケットを受信して、これに接続された１つまたはそれ以上のリンクを経由して各々のラベルに基づいて前記受信したパケットを転送するように構成されることと、
前記ラベル・スイッチ経路の各ノードは前記ラベルに関するラベル情報を保持するように構成された制御コンポーネントと前記ラベル情報に基づいて前記受信したパケットの転送を実行するように構成された転送コンポーネントとを含むことと、
前記ラベル・スイッチ経路のノードについて、受信パケットを転送するために使用する前記リンクが仮想リンクであれば、前記受信パケットは初期シグナリング処理で設定されたラベルを変更することなく前記仮想リンク内の前記１つまたはそれ以上の物理リンクのいずれか一つへ転送されることが可能であることを特徴とするシステム。
【請求項４】
パケットに付属する前記ラベルは、固定長のビット列、ＴＤＭフレームの時間スロット位置、光キャリアの波長を含む実体又はその組み合わせのいずれか一つから構成されることを特徴とする請求項３に記載のシステム。
【請求項５】
マルチプロトコル・ラベル・スイッチ・ネットワークで使用するラベル・スイッチング・ルータであって、
複数の入力仮想リンクと複数の出力仮想リンクとを含み各々の入力又は出力仮想リンクは複数の個別リンクを有する複数の仮想リンクと、
１つまたはそれ以上の前記入力仮想リンク経由で受信したパケットによって運ばれるラベルに関するラベル情報を保持するように構成された制御コンポーネントと、
前記複数の出力仮想リンクの１つまたはそれ以上を経由して前記ラベル情報に基づいて前記受信したパケットの転送を実行するように構成された転送コンポーネントと、
複数のエントリを有し、各エントリは入力仮想ポート番号と、入力ラベルと、出力ラベルと、出力仮想ポート番号とを有する、前記ラベル情報を格納するための少なくとも１個のラベル転送テーブルとを含み、
前記ラベル・スイッチング・ルータはパケットをルーティングするためのラベル・スイッチ経路の一部として認識され、
さらに、前記パケットの少なくとも一つは初期のシグナリング処理で設定される付属ラベルを変更することなく出力仮想リンク内の前記複数の個別リンクのいずれか一つに転送されることが可能であることを特徴とするラベル・スイッチング・ルータ。
【請求項６】
前記制御コンポーネントは前記受信したパケットを転送するために使用しようとする前記出力仮想リンク内の前記個別リンクがどれかについて関与しないことを特徴とする請求項５に記載のラベル・スイッチング・ルータ。
【請求項７】
受信パケットは付属の入力ラベルを有し、前記付属する入力ラベルは転送等価クラスと付属出力ラベルに対応することと、
前記ラベル・スイッチング・ルータは前記付属の入力ラベルと前記受信パケットに付属する入力仮想ポート番号とをキーとして使用して、前記付属の出力ラベルと、前記受信パケットを転送しようとする出力仮想リンクに対応する出力仮想ポート番号とを前記少なくとも一つのラベル転送テーブル内で検索することと、
第１のハッシュ関数を使用して前記付属の出力ラベルについて演算してハッシュ値を取得し、前記ハッシュ値が前記受信パケットを転送しようとする前記出力仮想リンク内の前記複数の個別リンクの一つに対応する出力実用ポート番号を表わすことを特徴とする請求項５に記載のラベル・スイッチング・ルータ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は一般にネットワーク内の２台の装置間の通信スパン内の複数リンクに関する。さらに詳しく説明すると、本発明はラベル・スイッチ・ネットワーク内の次ホップ装置用に複数リンク間で負荷バランスを採るための方法および装置に関する。
【０００２】
【従来の技術】
複数リンク技術はネットワーク内の２台の通信装置またはノード間でバンド幅を拡大する簡単な方法として広く使用されている。たとえば、波長分割多重化ネットワークでのパラレル・リンクは互いに隔離された多数の波長を用いて設定される。複数リンクを物理的に別の媒体、たとえば数本のファイバーおよび／または光ファイバ内の数種類の波長、またはＳＯＮＥＴ（同期光ネットワーク）／ＳＤＨ（同期デジタル階層）上のＳＴＭ（同期転送モード）におけるＶＣ（仮想コンテナ）など、なんらかの多重化技術を応用した共有媒体内のいくつかのスロットに設定できる。
【０００３】
リンク・コスト・チューニングと呼ばれる初期のいくつかの方法は複数リンク間で負荷バランシングを提供するために使用され、負荷によりリンクのコストを変更し、リンク・コストを用いて送信元と宛先の各対についてもっとも短いリンクまたは経路を見つけるルーティング・アルゴリズムにおいて使用されていた。これらの方法は一部に調節の粒状性が粗いため、またフィードバック処理における遅延に起因する固有の不安定性によるトラフィック発振のため、不十分であることがわかった。
【０００４】
「等コスト・マルチパス」法（ＥＣＭＰ）は多重リンク間で負荷バランシングを実現するために使用されていたもう一つの方法である。ＥＣＭＰ法では負荷に基づいたＯＳＰＦコストの動的調節を行なおうとはしないので、ＥＣＭＰ法を信頼性のあるものにすることができる。等コストの経路が存在するようなトポロジーであれば、経路間でトラフィックを等分割するように試みる。トラフィック分割の次のような方法が使用されてきた。
【０００５】
「パケットごとラウンドロビン・フォワーディング」法は経路上の遅延がほとんど等しい場合にのみ適用できる。遅延差はパケット・シリアル化時間に比べて十分に小さくなければならない。パケット・シリアル化時間の３倍以上の遅延差ではひどいＴＣＰパフォーマンスの劣化が起こるが、これは順序が正しくないパケットの到着でＴＣＰの高速再送を誘発し、ＴＣＰを小さな時間枠に制限し、長い遅延路ではパフォーマンスを非常に低くしている。
【０００６】
「発信元／宛先ハッシュ」法はＩＢＭ社製ＲＴ−ＰＣベースのルータでＴ１−ＮＳＦＮＥＴと同程度のハッシュ関数たとえばＣＲＣ−１６を発信元アドレスと宛先アドレスに対して適用する。閾値を設定するかモジュロ演算を実行するかのいずれかによって、ハッシュ空間を利用できる経路の間で均等に分割する。任意の発信元と宛先の間のトラフィックは同一経路上にとどまる。
【０００７】
【発明が解決しようとする課題】
ここで説明したこれらの方法はＩＰパケット転送メカニズムに基づいたものである。よって各パケットが転送される経路に沿って資源を確保するためのなんらかのシグナリング・メカニズムはサポートしていない。またトラフィック・エンジニアリングを実現するための明示的ルーティングもサポートしていない。そのため、なんらかのＩＰパケット転送メカニズムを使用することなしに負荷バランシングを実行することが可能な方法および装置を提供することが望まれる。
【０００８】
さらに、多重リンクを使用することは一つまたはそれ以上の潜在的短所を発生させかねない。たとえば、リンク利用における効率の劣化は負荷バランシングなしのバランスのとれていないトラフィックで発生することがある。図１はこの状況を図示したものである。他のリンクたとえばリンク＃２やリンク＃３を使用していないとしても、過負荷状態の物理リンク＃１では重大なパケット損失が発生しうる。負荷バランシングなしでは、多重リンク内のパケット損失を減少するためオーバーエンジニアリングが行なわれる。図２は従来の負荷バランシングを行なっている状態を示している。図２に図示してあるように、同じクラスに所属するパケットは多重リンクの内の特定の一つに転送されて、多重リンク全体にわたるトラフィックの均等な分配またはバランスを行なえるようにする。あるパケットが一つの物理リンクから別のリンクへ分配されるとき、これに付随するラベルも変更される。たとえば、物理リンク＃１でラベルＡのパケットが物理リンク＃２へ再ルーティングされる場合、パケットは物理リンク＃２で新しいラベルＡ‘が付与される。
【０００９】
多重リンクにわたる負荷バランシングにより、ある種のネットワークたとえばマルチプロトコル・ラベル・スイッチ（ＭＰＬＳ）ネットワークでは相当量の処理オーバヘッドが発生する。従来のＭＰＬＳネットワークでは、各パケットにラベルを付与しパケットの転送はラベルに依存する。同じラベルを有するパケットは同一の方法で処理される、たとえばあらかじめセットアップしてあるラベル・スイッチ経路またはリンクに沿って全部が転送される。この種のネットワークでは、一つのリンクから別のリンクへ、たとえば渋滞のためパケットを再転送する場合、再転送されるパケットには新しいリンクに沿って伝送するための新しいラベルを付与する必要がある。これには新しいラベルの作成が必要であり、大量の処理オーバヘッドが発生する。たとえば、新しいラベル・スイッチ経路をセットアップする必要があり、新しいラベル転送情報を新しいラベルスイッチ経路に沿ったすべてのノードに配布する必要が生じる。大量のパラレル多重リンクがあるＭＰＬＳネットワークでは、負荷バランシングは問題を生じやすい。したがって、ネットワークたとえばＭＰＬＳネットワークにおける多重リンクにわたって負荷バランシングを実行しつつ処理オーバヘッドを満足できる水準に維持できるような方法および装置を提供することが望まれる。
【００１０】
さらに、ＭＰＬＳネットワークにおいて、到着パケットをラベル・スイッチ・ルータで受信する場合、到着パケットに付随するラベルを新しいラベルに変更するかマッピングし直してから次のラベル・スイッチ・ルータへ供給する。このラベル・マッピング処理は付随ラベル転送テーブルの関連ラベル転送情報を参照することで行なう。付随ラベル転送テーブルは多重リンク全部を経由してラベル・スイッチ・ルータへ転送されるエントリを全部含むのが普通である。全部の多重リンクについてのエントリ数は極めて大きくなることがある。その結果、関連のあるラベル転送情報をそれぞれのラベル・スイッチ・ルータで検索する時間が実質的に大きくなり、これによりラベル・マッピング処理に遅延が生じることで、パケットの転送レイテンシに影響を与えるようになる。したがって、ネットワーク、たとえばＭＰＬＳネットワークでの転送レイテンシを改善することができるような方法および装置を提供することが望まれる。
【００１１】
【課題を解決するための手段】
本発明の代表的な一例によれば、ラベル・スイッチ・ネットワーク内の２台の装置間の一組のリンクから構成される仮想リンクがラベル・スイッチング・ルータの制御コンポーネントにより一つの実体として扱われる。仮想リンクへ伝送しようとする各パケットはこれに割り当てられるクラスに基づいてラベルが付与される。各パケットに付与されるラベルは、短く、固定長で、ローカルに有意な識別子であって特定のクラスを識別するために使用される。特定のラベルが対応するクラスに結合される。特定のラベルは同一クラスに属するパケットについて使用され、このようなパケットが仮想リンク内のリンクのいずれか一つへ転送することができる。仮想リンク内で一つのリンクから別のリンクへパケットを再ルーティングする場合、そのパケットに付属するラベルは変更されない。ラベル配布プロトコルを使用してイングレス・ノードからエグレス・ノードへ各クラスについての経路（またはラベル・スイッチ経路）を決定する。
【００１２】
さらに、本発明の別の代表的な一例によれば、各クラスは出力ラベルを変更することなく出発仮想リンク内のリンクの一つにマッピングすることができる。このマッピングは選択したハッシュ関数を使用して行なわれる。選択したハッシュ関数を使用してラベルを整数にマッピングし、仮想リンク内の少数のリンクの組に分配するようにする。
【００１３】
さらに、本発明のさらに代表的な一例によれば、別のラベルを有するパケットは仮想リンク内のリンクの間で配分される。同一ラベルを有するパケット（つまり同一クラスのパケット）は仮想リンク内で同じリンクへ転送される。仮想リンク内の各種リンクについて負荷バランスをとるためには、選択した時間に別の選択したハッシュ関数を使用して負荷条件によりパケットを配分することができる。
【００１４】
最後に、本発明のさらに別の代表的な一例によれば、送出側と受信側ラベル・スイッチ・ルータで使用されるそれぞれのハッシュ関数が同期される。ハッシュ関数を同期することで、負荷転送テーブル内のエントリ数を減少し、これによって検索時間とメモリ記憶条件を減少する。
【００１５】
本発明の代表的な実施例は多数のノードを有するラベル・スイッチ・ネットワークである。各ノードは、多数の入力仮想リンクと多数の出力仮想リンクとを含み各入力または出力仮想リンクが多数の独立したリンクを有する多数の仮想リンクと、入力仮想リンクの一つまたはそれ以上を経由してそれぞれのラベルを有するパケットを受信しまた出力仮想リンクの一つまたはそれ以上を経由してそれぞれのラベルに基づいて受信パケットを転送するように構成され、ラベルに関連したラベル情報を保持するように構成された制御コンポーネントとラベル情報に基づいて受信パケットの転送を実行するように構成された転送コンポーネントとをさらに含むラベル・スイッチング・ルータとを含む。
【００１６】
ラベル・スイッチング・ルータはルーティング・パケットのラベル・スイッチ経路の一部として認識される。ラベル・スイッチ経路に関して、入力仮想リンクそれぞれの中の個別のリンクと出力仮想リンクそれぞれの中の個別のリンクがそれぞれ制御コンポーネントによって一つの実体として扱われる。
【００１７】
受信パケットを転送するのに出力仮想リンク内の個別のリンクの内のどれを使用することになるかについての詳細は制御コンポーネントから隠蔽される。言い換えれば、制御コンポーネントはパケットのそれぞれのラベルをつけ変えることなく、出力仮想リンク内の個別リンクのどれにでもパケットを転送する。
【００１８】
パケットに付随するラベルは、固定長のビット列、ＴＤＭフレーム内の時間スロット位置、光キャリアの波長を含む実体のいずれか一つまたはその組み合わせから構成される。さらに、各ラベルは多数の転送等価クラスの一つに割り当てられ、ラベルをラベル・スイッチング・ルータで使用して出力仮想リンクの個別リンクの一つへ対応するクラスに属するパケットを転送する。
【００１９】
各ノードはさらにハッシュ関数を使って出力仮想リンク経由で転送しようとするパケットのラベルを計算してハッシュ値を得るように構成された制御論理を含み、ハッシュ値はパケット転送に使用される出力仮想リンク内の個別リンクの一つを表わす。ハッシュ関数を使用してパケットのラベルを計算することで、ラベルを変更せずに出力仮想リンク内の個別のリンクの一つへパケットを転送することができるようになる。
【００２０】
制御論理はまた出力仮想リンク経由で転送しようとするパケットのそれぞれのラベルについて演算するのに使用しようとする多数のハッシュ関数のうちの一つを選択して対応するハッシュ値を得るようにも構成される。それぞれのラベルは一つまたはそれ以上の対応するクラスに対応する。対応するハッシュ値はパケットを転送するために使用しようとする出力仮想リンク内の個別のリンクの一つまたはそれ以上を表わす。それぞれのラベルについて演算するハッシュ関数の一つを選択することによりそれぞれのラベルを付与したパケットが出力仮想リンク内の個別のリンクの中から配分される。それぞれのラベルについて演算するために使用するハッシュ関数は負荷バランシング条件の一つまたはそれ以上に基づいて選択される。
【００２１】
各ノードはさらに多数のラベル転送テーブルを含み、各ラベル転送テーブルは多数のエントリを有し、各エントリは入力仮想ポート番号、入力ラベル、出力ラベル、出力仮想ポート番号を含む。入力仮想ポート番号は入力仮想リンクに関する識別情報を表わす。入力ラベルは受信パケットに関するラベル情報を表わす。出力ラベルは出力パケットに関するラベル情報を表わし、出力仮想ポート番号は出力仮想リンクに関する識別情報を表わす。
【００２２】
それぞれのラベル転送テーブルには入力仮想リンク内の個別リンクの一つが関連する。第１のラベル転送テーブルでは、そのエントリについての入力ラベルのハッシュ値が第１のラベル転送テーブルに付随する入力仮想リンク内の個別リンクに対応する入力実用ポート番号に等しければエントリがタグされる。第１のラベル転送テーブルを変更して、タグのついたエントリだけを含めるようにする。第１のラベル転送テーブルに付随する入力仮想リンク内の個別リンク経由でパケットを受信した場合、受信パケットに対応するエントリについて第１のラベル転送テーブル内のタグつきエントリだけを検索する。
【００２３】
本発明により多数の利点および／または利益が実現できる。たとえば、ラベル配布プロトコルを使用することにより、ラベル・スイッチ経路の決定は、最短経路を見つけるためのＩＰルーティング処理で使用されるＩＰパケット転送メカニズムやリンク・コストのどれからも独立して行なわれるので、これによりＩＰパケット転送メカニズムに付随する固有の不安定性やトラフィック発振を回避できる。ラベル配布プロトコルはトラフィック・エンジニアリングで使用する明示的ルーティングもサポートしているので、ネットワーク設計やトラフィック・フローの最適化が実現可能である。
【００２４】
さらに、仮想リンクは一つの実体として扱われるので、ラベル・スイッチ経路を設定・保持するために必要とされるシグナリングおよびメッセージングの総量を減少し、これにより大量のパラレル多重リンクから構成されるスケーラブル・ネットワークのサポートが容易になる。
【００２５】
さらに、本発明によればラベル転送テーブルにおける受信パケットのラベル検索が容易になるので結果としてそれぞれのラベル・スイッチング・ルータで多重リンクへのラベルのマッピングし直しに必要な時間が短縮される。これによりフィードバック処理の遅延や発振の危険性を減少しデータバーストにたいして応答が高速の多重リンクの利用を向上する。
【００２６】
図面や請求項を含む明細書の残りの部分を参照することで、本発明のその他の特徴や利点が明らかになろう。本発明の更なる特徴や利点ならびに本発明の各種実施例の構造と動作は、添付の図面を参照して以下で詳細に説明し、図面において同じ参照番号は同一または機能的に類似した要素を表わすものとする。
【００２７】
【発明の実施の形態】
一つまたはそれ以上の代表的実施例の形で本発明を説明する。本発明の代表的実施例によれば、制御の観点から、負荷バランシングを実現する特定の物理リンクの識別および選択は対象ではない。言い換えれば、多重リンクは負荷バランシング制御の観点から、集合的に仮想リンクとして（すなわち、擬似的な１本の太いパイプとして）扱われる。したがって、あるパケットについて初期のシグナリング処理で設定されるラベル情報は、一つの物理リンクから別のリンクへパケットが分配される場合に変更を受けない。図３は本発明の代表的実施例の動作を示す。図３に図示したように、物理リンク＃１から物理リンク＃２へラベルＡをつけたパケットを再ルーティングする場合、パケットは同じラベル、ラベルＡのままである。
【００２８】
代表的実施例において、本発明は多重プロトコル・ラベル・スイッチ（ＭＰＬＳ）ネットワークへ適用される。しかし、本明細書で提供される開示に基づいて本発明をその他の同様な種類のネットワークへ適用できることは当業者には明らかであろう。図４はＭＰＬＳネットワーク３０を示す略模式図である。図４に図示したように、ＭＰＬＳネットワーク３０は多数のラベル・エッジ・ルータ（ＬＥＲ）３２、３４と多数のラベル・スイッチング・ルータ（ＬＳＲ）３６を含む。ＬＥＲはさらに２種類に分類される、すなわちイングレスＬＥＲ３２ａ、３２ｂとエグレスＬＥＲ３４ａ、３４ｂである。ＬＥＲ３２、３４は後述する同様の機能をそれぞれ実行する他のノードにより置換可能であり、ＬＳＲ３６はＬ３スイッチ、光クロスコネクトなどを含む他の種類のラベル・スイッチング・ノードで置き換えうることが理解されるべきである。
【００２９】
イングレスＬＥＲ３２ａはたとえば送信元（図示していない）から指定された宛先アドレスＡ１をもつＩＰパケットを受信する。送信元はＩＰパケットを送信することができるなんらかの装置、たとえばクライアント端末やネットワークのノードなどである。ＩＰパケットをイングレスＬＥＲ３２ａで受信した場合、イングレスＬＥＲ３２ａはＩＰパケットを転送等価クラス（ＦＥＣ）たとえばＦＥＣＡ１に分類する。転送等価クラスは伝送について同じ条件を共有するパケットのグループを表現したものである、すなわち同じ転送等価クラス内の全部のパケットはＭＰＬＳネットワーク３０を通る同じ経路をたどり各ＬＳＲ３６で同じ処理を受ける。ＩＰパケットに適当なＦＥＣを付与したあと、イングレスＬＥＲ３２ａはＩＰパケットに出力ラベル、たとえばα１をつけ、これはこの場合ＦＥＣＡ１である所定のＦＥＣに対応するものである。ＩＰパケットに関連するラベルは以下の実体のいずれか一つまたはその組み合わせから構成され、これにはたとえば固定長ビット列、ＴＤＭフレームの時間スロット位置および光キャリアの波長を含む。イングレスＬＥＲ３２ａは新しくラベルをつけたＩＰパケットをＬＳＲ３６ａへ転送する。同様に、イングレスＬＥＲ３２ｂは指定された宛先アドレスＢ１を有するＩＰパケットに対して同じ機能を実行する。
【００３０】
ラベルのついたＩＰパケットを受信すると、ＬＳＲ３６ａはラベル転送テーブルを使用してＩＰパケットのラベルをα１からα２へ切り換える。ラベルα２は同様にＩＰパケットに割り当てられたＦＥＣであるＦＥＣＡ１に対応する、すなわちＦＥＣＡ１に属するすべてのパケットにはラベルα２が付与される。ＬＳＲ３６ａで実行されるこのラベルスイッチ機能はＭＰＬＳネットワーク３０の特徴である。各ＬＳＲ３６はそれ自身のラベル転送テーブルと特定ＦＥＣについてそれ自身のラベルを保持する。ラベル転送テーブルは入力および出力のラベリングとＦＥＣ情報とを内包する。この情報を用いて到着ＩＰパケットからの入力ラベルを、同じＦＥＣに所属する出力ラベルへマッピングする。出力ラベルのついたＩＰパケットはここでＬＳＲにより別のＬＳＲへ転送される。したがって、各ＩＰパケットをカプセル化するために使用されるラベルはリンク内部の送出側ＬＳＲから受信側ＬＳＲへ同一のまま維持される。しかし、リンクごとにラベルを変更できることは注意すべきである。ラベルは、ＩＰパケットを受信し受信側ＬＳＲで検証した場合、受信側ＬＳＲの観点からの入力ラベルとして特徴づけられ、またラベルは、ＩＰパケットが送出側ＬＳＲから次ホップＬＳＲへ送出された場合、送出側ＬＳＲの観点からの出力ラベルとして特徴づけられる。本実施例では、ＬＳＲ３６ａはそのラベル転送テーブルを使用することにより、ＬＥＲ３２から（特定の入力ポート経由で）受信したＩＰパケットのラベルα１がＦＥＣＡ１に対応することを判定し結果としてＩＰパケットのラベルをα２に切り換えるが、このラベルもＦＥＣＡ１に対応するものである。新しいラベルα２のついたＩＰパケットはＬＳＲ３６ａにより次のＬＳＲ３６ｂへ送信される。よって、各ＬＳＲ３６で、ＩＰパケットのラベルは関連するローカル・ラベル転送テーブルにより切り換えられるが、ＩＰパケットのＦＥＣはＭＰＬＳネットワーク３０内の伝送を通じて同じまま保持される。
【００３１】
エグレスＬＥＲ３４ａがＩＰパケットを受信した場合、ラベルα４（これはＬＳＲ３６ｃによって割り当てられる）が除去され、ＩＰパケットについて従来のレイヤー３（ネットワーク層）参照を行なう。参照の結果に基づき、ＩＰパケットは宛先アドレスＡ１へ転送される。
【００３２】
ラベル・スイッチド・パス（ＬＳＰ）としても公知で、同じＦＥＣに所属するＩＰパケットがＭＰＬＳネットワーク３０内部で転送される経路は、初期のラベル結合手順でユニークに決定される。つまり、ＬＳＰはデータパケット伝送の開始より前に設定される。初期ラベル結合手順はラベルにＦＥＣをマッピングまたは結合するために行ない、ラベル結合情報はあるプロトコル、たとえば、インターネット・エンジニアリング・タスクフォース（ＩＥＴＦ）で策定されるラベル配布プロトコル（ＬＤＰ）などを用いてＬＳＲ３６へ分配される。
【００３３】
図４に図示してあるリンクのどれか、たとえばイングレスＬＥＲ３２ａとＬＳＲ３６ａの間のリンク＃１  ３８とＬＳＲ３６ａとＬＳＲ３６ｄの間のリンク＃５  ４０は、多数のリンクから構成されることがある。代表的実施例において、ＬＳＲ３６の入力リンク（群）（すなわち、パケット受信用のリンク）と出力リンク（群）（すなわち、パケット転送用のリンク）はそれぞれ多数のリンクから構成される。しかし、各ＬＳＲ３６で、入力リンク（群）と出力リンク（群）がどちらも多数のリンクから構成されなくとも良いことには注意すべきである。たとえば、別の実施例において、入力リンクまたは出力リンクのどちらかが多重リンクで構成される。図４ａから図４ｄは多重リンクの各種代表的実施例を示す。２台の装置間の通信スパン内部の多重リンクは本明細書において集合的に「仮想リンク」と呼ぶ。図５ａを参照すると、たとえば、仮想リンクはイーサ・フレーマを使用してパケットを送信する多数のファイバで構成されるように図示してあり、図５ｂでは仮想リンクはＳＯＮＥＴ／ＳＤＨフレーマを使用してパケットを送信する多数のファイバから構成されるように図示してある。多数のフレーマを使用すると波長分割多重化技術を用いてファイバーのうちの１本にパケットを送信することができる。図５ｃにおいて、仮想リンクはイーサ・リンクとＳＯＮＥＴ／ＳＤＨリンクの組み合わせから構成されるように図示してある。また図５ｄでは仮想リンクはＳＯＮＥＴ／ＳＤＨリンクのタイムスロットにより提供される多数の論理リンクから構成されるように図示してある。
【００３４】
図６は本発明を実施するために使用できるＬＳＲ３６のアーキテクチャを図示している。図６を参照すると、アーキテクチャには２つの独立したコンポーネントが含まれており、すなわち転送コンポーネント（データプレーンとも呼ばれる）５０と制御コンポーネント（制御プレーンとも呼ばれる）５２である。転送コンポーネント５０は多数の到着仮想リンクからデータ・パケットを受信して当該パケットを多数の出発仮想リンクへ転送する。各仮想リンクは（到着側と出発側）多数の個別リンクまたは多重リンクを含む。一つの実装において、到着仮想リンク内部の各リンクは入力実用ポートに接続され、これがさらにネットワーク・カード（図示していない）へ接続される。同様に、出発仮想リンク内部の各リンクは出力実用ポートへ接続される。各入力実用ポートで、転送コンポーネント５０はラベル転送テーブルまたはデータベースを使用してデータパケットが保持しているラベルに基づきその入力実用ポート経由で受信したデータパケットの転送を実行する。ラベル転送テーブルに関する詳細については以下で提供する。
【００３５】
制御コンポーネント５２はＭＰＬＳネットワーク３０内部のＬＳＰに沿って相互接続されているＬＳＲのグループ間でラベル転送情報（バインディング（結合）とも呼ばれる）を作成、保持、分配する役割がある。ラベル転送情報はラベルが作成された時点で生成され制御コンポーネント５２によって保持されるラベル転送テーブル内に格納される。各ＬＳＲ３６は自分のラベル転送情報をＭＰＬＳネットワーク３０内の他のＬＳＲ３６へ配布する。このラベル配布処理はまたラベル・バインディング交換とも呼ばれることがある。制御コンポーネント５２はＩＰルーティング・テーブルも使用してラベル・バインディング交換を行ない、ここで隣接するＭＰＬＳノードがＩＰルーティングテーブル内に含まれている個別の発信元−宛先ペアについてのラベルを交換する。一つの例では、宛先ユニキャスト・ルーティングのラベル・バインディング交換はＩＥＴＦ策定ＬＤＰを使用して行なわれる。明示的なルーティングをサポートしトラフィック・エンジニアリングを実現するため、基本ＬＤＰへの拡張も策定されている。その他のプロトコル、たとえばＭＰＬＳ−ＲＳＶＰ（資源予約プロトコル）やＣＲ−ＬＤＰ（制限ベースのラベル配布プロトコル）もラベル・バインディング交換を実行するために使用できる。
【００３６】
図７は従来の方法で図６に図示したＬＳＲ３６のアーキテクチャ内部でどのように多重リンクが処理されるかを示す。図７を参照すると、多重リンクの中の各リンクは別個の実体として扱われている。たとえば、３本のリンク６０、６２、６４と各々のＬＳＰは別個の独立した実体として扱われている。各々のＬＳＰについて、ラベル配布処理やＬＳＰを維持するためのその他の処理が必要である。
【００３７】
本発明の代表的実施例によれば、制御コンポーネント５２は多重リンク（すなわち仮想リンク）を単一の実体として扱う。言い換えれば、仮想リンクを構成する多くの物理および／または論理リンクの詳細は制御コンポーネント５２から隠蔽される。図８は本発明の代表的実施例によりどのように多重リンクを扱うかを示す。図８に図示してあるように、多重リンクは単一の仮想リンク７０として扱われる。多重リンクを単一の仮想リンクとして扱うことにより、仮想リンクを構成する物理および／または論理リンクの各々の詳細が必要ではなくなり単一のＬＳＰが多重リンクの組全体について仮想的に設定されるため、シグナリングとメッセージングの総量が効果的に減少する。言い換えれば、制御コンポーネント５２の観点から、仮想リンク７０内の多重リンクは単一のＬＳＰとして見なされる、すなわちパケットを転送するために使用される仮想リンク７０内の多重リンクのどれを用いるかが制御コンポーネント５２から隠蔽され、またこれらの多重リンクは単一のＬＳＰを設定するために使用されるのと等しい量のシグナリングおよびメッセージングの量で集合的に設定される。代表的実施例によれば、ラベル配布処理はＦＥＣに属するパケットの共通のラベルを結合し、ここで共通のラベルは同じＦＥＣに属するパケットを出発仮想リンク内の個別のリンクのいずれか一つへ転送するために使用できる。
【００３８】
図９と図１０は本発明によるＬＳＲ３６の転送コンポーネント５０の代表的動作を示す。図９と図１０を参照すると、転送コンポーネント５０は多数の入力・出力仮想ポートと、多数の入力・出力実用ポートと、多数のフロントエンドおよびバックエンド・ラベル転送モジュールおよびバックプレーン・スイッチを含む。仮想ポートは制御コンポーネント５２により単一の実体と見なされる一組の実用ポートであると見なされる。仮想ポート内の実用ポートは各々が一つの実用ポートを他のポートから識別するために使用するユニークなポート番号を有する。
【００３９】
到着仮想リンクは各々の入力仮想ポート（およびこれを構成する入力実用ポート）へ接続される。入力実用ポートはさらにフロントエンド・ラベル転送モジュールへ接続される。代表的には、各々の入力実用ポートはネットワーク・カード（図示していない）へ接続され、これに対応するフロントエンド・ラベル転送モジュールを含む。フロントエンド・ラベル転送モジュールはバックプレーン・スイッチへ接続される。バックプレーン・スイッチはバックエンド・ラベル転送モジュールへ接続され、これがさらに出力実用ポート（および出力仮想ポート）へ接続される。最後に、出力仮想ポートは各々の出発仮想リンクへ接続される。
【００４０】
転送コンポーネント５０は本発明による以下の代表的な方法で動作する。各々の入力仮想ポートを用いて対応する到着仮想リンクからパケットを受信する。つまり、到着仮想リンクたとえば仮想リンクＡからのパケットは、到着仮想リンク内の個別のリンクに対応する多数の入力実用ポート（これは同じ入力仮想ポートに属する）によって受信される。入力実用ポートはこれに対応する多数のフロントエンド・ラベル転送モジュールへ接続される。各フロントエンド・ラベル転送モジュールは到着パケットの転送に使用すべき出力仮想ポートおよび実用ポートがどれなのかを決定する責任がある。各フロントエンド・ラベル転送モジュールは関連するラベル転送テーブルの適切なエントリを参照してこの決定を行なう。たとえば、パケットに付けられたラベルと仮想ポート番号を参照のキーとして使用できる。到着パケットを受信する入力仮想ポート番号は分かっている。よって、到着パケットについて入力仮想ポートの仮想ポート番号は容易に取得できる。参照の結果として、パケットを転送するために使用すべき出力仮想ポートの仮想ポート番号と次ホップＬＳＲへの仮想リンクで使用すべき新しいラベルが取得される。前述したように、各々のフロントエンド・ラベル転送モジュール又は入力実用ポートはラベル転送テーブルに関連するが、ラベル転送テーブルは多数の方法で構成できることに注意すべきである。たとえば、各々のＬＳＲ３６は一つだけのラベル転送テーブルを含んでいたり、幾つかのフロントエンド・ラベル転送モジュール（これが仮想ポートを含む多数の入力実用ポートを処理する）が一つのラベル転送テーブルを共有することがある。本明細書に提供した開示に基づいて、ラベル転送テーブルを構成する他の方法が当業者には理解されよう。参照処理については以下でさらに詳しく説明する。出力仮想ポート内の出力実用ポート（とこれに対応する実用ポート番号）のどれを使うかを決定するメカニズムについては後述する。
【００４１】
参照から得られた情報を使って、フロントエンド・ラベル転送モジュールはバックプレーン・スイッチに利用可能な出力仮想ポートの一つへパケットをスイッチさせる。図９に図示してあるように、たとえばバックプレーン・スイッチは出力仮想ポートの各々の中の出力実用ポートの間でパケットをスイッチするために使用する。さらに詳しく説明すると、到着するα、β、γパケットは、入力仮想ポートＡ経由で仮想リンクＡから受信される。関連する参照情報がフロントエンド・ラベル転送モジュールによって得られてから、フロントエンド・ラベル転送モジュールはバックプレーン・スイッチにパケットを分割させて２個の別々の仮想リンクへこれらを配送させる。αおよびβパケット（新しいラベルα’とβ’がついている）は出力仮想ポートＫ経由で仮想リンクＫへ配送され、γパケット（新しいラベルγ’がついている）は出力仮想ポートＸ経由で仮想リンクＸへ配送される。
【００４２】
さらに、バックエンド・ラベル転送モジュールもパケットのトラフィックをバランスさせるスイッチング機能を実行する。たとえば、図１０に図示してあるように、バックエンド・ラベル転送モジュールは出力仮想ポート内の出力実用ポートの間でパケットを割り当てて出力仮想リンクへ配送すべきトラフィックをバランスさせるようにスイッチング動作する。詳細には後述するように、ハッシュ関数をパケットの出力ラベルとの関連で使用して仮想リンク内の各種リンクの間にパケットを割り当ててパケット・トラフィックをバランスさせる。
【００４３】
図１１は本発明によりパケットを転送するＬＳＲ３６の各フロントエンド・ラベル転送モジュールで使用するラベル転送テーブルの好適実施例を示す。前述のように、好適実施例において、各々のフロントエンド・ラベル転送モジュールはそれ自身のラベル転送テーブルを保持する。図１１に図示してあるように、ラベル転送テーブルは入力仮想ポート番号９０のフィールド、入力ラベル９２、出力ラベル９４、出力仮想ポート番号９６を含む。これらのフィールドにある情報は初期にたとえばラベルとＬＳＰを作成する時点でＬＤＰを使用して伝搬する。前述のように、ラベル転送テーブルはＬＳＲ３６の制御コンポーネント５２によって維持される。
【００４４】
前述の参照処理をさらに以下で説明する。もう一度図９を参照すると、たとえば、βとラベルのついたパケットを入力仮想ポートＡで仮想リンクＡから受信する。図１１に図示したラベル転送テーブルを使用して、ラベル転送テーブルからＡとβをキーとして参照を行なうと出力仮想ポート番号“Ｋ”と出力ラベル“β”を次ホップＬＳＲへの出発仮想リンクで使用すべきことが分かる。出力仮想ポート番号はパケット転送に使用すべき出力仮想ポート（とそれに対応する出発仮想リンク）を識別する。
【００４５】
次に、識別された出力仮想ポート内でパケット転送に使用すべき出力実用ポートを決定する。あらかじめ選択しておいたハッシュ関数を使って出力ラベルを整数（又はハッシュ値）にマッピングして識別した出力仮想ポートで少ないリンクの組に対して配布を行なう。別のハッシュ関数を使えば別のトラフィック・パターンでの変動に対する負荷バランシングに対応することができる。出力実用ポート番号は出力ラベルのハッシュ値を取ることにより得られる。図１１に図示してあるように、たとえば、ｆ（Ｘ）がラベルＸのハッシュ値を表わすものとすると、出力実用ポート番号がｆ（β’）の出力実用ポートへパケットを転送する。
【００４６】
ＬＳＲ３６の制御コンポーネント５２は仮想リンク内のＦＥＣ各々にユニークなラベルを割り当てるので、同じ出力ラベルが同じＦＥＣに属するパケットに割り当てられる。したがって、出力ラベルのハッシュ値として定義された出力実用ポート番号も又同じＦＥＣに属する全てのパケットでユニークである。つまり、同じＦＥＣに属する全部のパケットは各々の出力仮想ポート内の同じ出力実用ポートを使用することになり、パケット順序が保存される。
【００４７】
図１２は本発明による到着パケット受信時のＬＳＲ３６のフロントエンド・ラベル転送モジュール各々で使用するラベル転送テーブルの別の好適実施例を示す。後述するように、代表的なラベル転送テーブルはもっと少ない数のエントリを含み、これによって検索時間とメモリ要求の量を減少する。
【００４８】
本発明の代表的実施例によれば、受信側ＬＳＲによって使用されるハッシュ関数は送出側ＬＳＲで使用されるハッシュ関数と同期される。前述のように、ハッシュ関数は出力ラベルに演算を行なって対応する出力実用ポート番号を得るために使用される。送信側ＬＳＲから受信側ＬＳＲへ送出されたパケットについて、送信側ＬＳＲで付与した出力ラベルは受信側ＬＳＲで受信される入力ラベルと同一である。したがって、送信側と受信側のＬＳＲでの各々のハッシュ関数を同期することにより、入力実用ポート番号が入力ラベルのハッシュ値として計算できるため、受信側ＬＳＲは入力実用ポートのどれを使用してパケットを受信するか通知を受けることができる。これは入力実用ポートに接続された各々のフロントエンド・ラベル転送モジュールに付随するラベル転送テーブルにおけるエントリ数を減少するために使用できる。
【００４９】
ラベル転送テーブルのエントリ数は以下のようにすると減少できる。図１２を参照すると、入力仮想ポート番号９０、入力ラベル９２、出力ラベル９４、出力仮想ポート番号９６といったフィールドの情報に加えて、フィールドの他の情報すなわち入力ラベルのハッシュ値９８と入力実用ポート番号１００も利用できる。入力ラベルのハッシュ値は入力ラベルについてハッシュ関数を演算することで得ることができ、入力実用ポート番号についてはフロントエンド・ラベル転送モジュールはこれに付属する入力実用ポートの認識に関する情報を有している。「タグ」フィールドの情報は以下の決定に基づいて伝播する：各エントリについて、入力ラベルのハッシュ値が入力実用ポート番号に等しい場合には、特定のエントリをマークする又はタグつけする。たとえば、図１２に図示したように、実用ポートが実用ポート番号［ｎ］を有しこの実用ポートが仮想ポート番号「Ａ」を有する仮想ポート内にあると仮定する。入力ラベルβ’のハッシュ値ｆ（β’）が入力実用ポート番号「ｎ」に等しい場合、入力ラベルβ’のエントリがタグされる。言い換えれば、入力実用ポート番号「ｎ」に対応するハッシュ値を有するエントリだけがタグされる。前述の方法で配布したラベル転送テーブルは入力実用ポート番号「ｎ」を有する入力実用ポート経由でパケットを受信するフロントエンド・ラベル転送モジュールとの関連で使用される。タグのついたエントリを用いることでより高速な参照が実現できる。このラベル転送テーブルを使用して参照又は検索を行ない関連するラベル転送情報を取得する場合、タグのついたエントリだけを検索することにより検索時間の総量を減少できる。他のエントリについての検索は、送信側ＬＳＲが番号を出力ラベルのハッシュ値であると決定した一つの出力実用ポートへ各パケットを転送するため、不要である。
【００５０】
別の代表的実施例において、ラベル転送テーブルはタグのついたエントリだけを含む。タグのついたエントリだけを格納することにより、ラベル転送テーブルのサイズを小さくしておくことができ、ラベル転送テーブルを格納するのに必要なメモリ・ストレージ量も対応して減少する。ＭＰＬＳネットワーク内には多数のラベル転送テーブルが存在しており、各フロントエンド・ラベル転送モジュールについて潜在的に一つのラベル転送テーブルがあるので、メモリ・ストレージについて有意な節約が本発明により実現できる。
【００５１】
代表的実施例において、本発明はモジュール型又は内蔵型のいずれかの方法で制御論理の形でソフトウェアを使用して実現される。しかし、本発明はハードウェアを使用して又はハードウェアとソフトウェアの組み合わせを使用して実現することもできることは当業者には明らかなはずである。
【００５２】
本明細書で説明した例および実施例は本発明の説明を目的としたものであってこれに鑑みた各種の変更又は変化が当業者には示唆されまた本出願の趣旨と範囲内又添付の請求項の範囲内に含まれるべきであることが理解されよう。本明細書で引用した全ての刊行物、特許、特許出願はその全体として全ての目的で参照に含まれる。
【図面の簡単な説明】
【図１】図１は負荷バランシングなしのバランスしていないトラフィック下でのリンク使用における効率の劣化を示す略模式図である。
【図２】図２は負荷バランシングありの多重リンクに対する分散トラフィックを示す略模式図である。
【図３】図３は本発明の代表的実施例の動作を示す略模式図である。
【図４】図４はマルチプロトコル・ラベル・スイッチ・ネットワークを示す略模式図である。
【図５】図５（ａ）から図５（ｄ）は多重リンクの各種代表的実施例を示す略模式図である。
【図６】図６は本発明の実施に使用することができるラベル・スイッチング・ルータのアーキテクチャを示す略模式図である。
【図７】図７は図５（ａ）〜（ｄ）に図示したラベル・スイッチング・ルータの従来のアーキテクチャ内でどのように多重リンクが扱われるかを示す略模式図である。
【図８】図８は本発明の代表的実施例により多重リンクがどのように処理されるかを示す略模式図である。
【図９】図９は本発明によるラベル・スイッチング・ルータの転送コンポーネントの代表的実施例を示す略模式図である。
【図１０】図１０は本発明によるラベル・スイッチング・ルータの転送コンポーネントの別の代表的実施例を示す略模式図である。
【図１１】図１１は本発明によるラベル・スイッチング・ルータによりパケットを転送するために使用されるラベル転送テーブルの代表的実施例を示す略図である。
【図１２】図１２は本発明による到着パケット受信時にラベル・スイッチング・ルータにより使用されるラベル転送テーブルの別の代表的実施例を示す略図である。
【符号の説明】
４０：リンク５、Ｃ１，Ｃ２，Ｃ３，Ｃ４：ラベル・スイッチング・ルータ（ＣＯＲＥ）、Ｅ１，Ｅ２，Ｅ３，Ｅ４：ラベル・スイッチング・ルータ（エッジ）、Ａ１，Ｂ１：ＩＰ宛先アドレス、α１，α２，α３，α４，β１，β２，β３，β４：ラベル、９０：入力仮想ポート＃、９２：入力ラベル、９４：出力ラベル、９６：出力仮想ポート＃。
【図１】
0004205931.tif 000002
【図２】
0004205931.tif 000003
【図３】
0004205931.tif 000004
【図４】
0004205931.tif 000005
【図５】
0004205931.tif 000006
【図６】
0004205931.tif 000007
【図７】
0004205931.tif 000008
【図８】
0004205931.tif 000009
【図９】
0004205931.tif 000010
【図１０】
0004205931.tif 000011
【図１１】
0004205931.tif 000012
【図１２】
0004205931.tif 000013