(57)【要約】  マルチセグメント（２５）を含む通信ネットワーク（２０）を通る接続を確立するための方法であって、当該方法は、該ネットワーク中の複数の接続同士の間での帯域幅の分配を定義する分配定義を与えることを含む。該ネットワークを通って確立される新たな接続のための２つ以上の候補経路（４０、４４、５２、５６）が特定される。該２つ以上の候補経路のそれぞれについて、分配定義に対応して、候補経路に沿ったセグメント内の新たな接続に割り当てられる累積的な追加の帯域幅予約が計算される。該２つ以上の候補経路の中から、累積的な追加の帯域幅予約の最小値を有する好ましい経路が選択される。該好ましい経路を使用して新たな接続が確立される。【選択図】図１
2009524970.tif 000002
【特許請求の範囲】
【請求項１】
マルチセグメントを含んだ通信ネットワークを通る接続を確立するための方法であって、当該方法は、
該ネットワーク中の複数の接続同士の間での帯域幅の分配を定義する分配定義を、与えることを有し、
該ネットワークを通って確立される新たな接続のための２つ以上の候補経路を特定することを有し、
該２つ以上の候補経路のそれぞれについて、前記分配定義に対応して、候補経路に沿ったセグメント内の新たな接続に割り当てられる累積的な追加の帯域幅予約を計算することを有し、
該２つ以上の候補経路の中から、累積的な追加の帯域幅予約の最小値を有する好ましい経路を選択することを有し、かつ、
該好ましい経路を使用して、新たな接続を確立することを有する、
前記方法。
【請求項２】
少なくともいくつかのセグメントがリング構成をなすように配置されており、かつ、
２つ以上の候補経路を特定することが、該リング構成のそれぞれの第１および第２のリングレットを渡って行く第１および第２の経路を特定することを有する、請求項１記載の方法。
【請求項３】
新たな接続を確立することが、ネットワークを通るトンネルを、トンネルベースの通信プロトコルに従って確立することを有する、請求項１記載の方法。
【請求項４】
分配定義が、
新たな接続が、好ましい経路に沿った少なくとも一つの共通のセグメントを渡る既存の接続と共に、帯域幅を分配し得る、
ということを記述しており、かつ、
新たな接続を確立することが、新たな接続と既存の接続との間の少なくとも一つの共通のセグメント内で、帯域幅割り当てを分配することを有する、請求項１〜３のいずれかに記載の方法。
【請求項５】
新たな接続および既存の接続が、ネットワークセグメントおよびネットワークノードの少なくとも一つにおける故障に対して、お互いを保護するように確立されている、請求項４記載の方法。
【請求項６】
分配定義を与えることが、予約プロトコルを使用して、ネットワークのノードに分配定義を割り振ることを有する、請求項１〜３のいずれかに記載の方法。
【請求項７】
好ましい経路を選択することが、計算された累積的な追加の帯域幅予約が該２つ以上の候補経路の全てについて等しい場合に、より低い優先順位の経路を選択する方法に立ち戻ることを有する、請求項１〜３のいずれかに記載の方法。
【請求項８】
ネットワークノードであって、当該ネットワークノードは、
ネットワークインターフェースを有し、該ネットワークインターフェースは、マルチセグメントを含む通信ネットワーク上で、他のネットワークノードと通信するように設定されており、かつ、
プロセッサーを有し、該プロセッサーは、該ネットワーク中の複数の接続同士の間での帯域幅の分配を定義する分配定義を受け入れるように設定されており、該プロセッサーは、該ネットワークを通って確立される新たな接続のための２つ以上の候補経路を特定するように設定されており、該プロセッサーは、該２つ以上の候補経路のそれぞれについて、分配定義に対応して、候補経路に沿ったセグメント内の新たな接続に割り当てられる累積的な追加の帯域幅予約を計算するように設定されており、該プロセッサーは、該２つ以上の候補経路の中から、累積的な追加の帯域幅予約の最小値を有する好ましい経路を選択するように設定されており、かつ、該プロセッサーは、その好ましい経路を使用して新たな接続を確立するように設定されている、
前記ネットワークノード。
【請求項９】
少なくともいくつかのセグメントが、ノードと連結されて、リング構成をなすように配置されており、かつ、
該プロセッサーが、リングレベルのコネクション・アドミッション・コントロール（ＣＡＣ）モジュールを有し、該モジュールが、リング構成の第１および第２のリングレットをそれぞれ渡る第１および第２の候補経路を特定するように設定されており、かつ、第１および第２のリングレットの一つを渡る好ましい経路を選択するように設定されている、
請求項８記載のノード。
【請求項１０】
新たな接続が、トンネルベースの通信プロトコルに従って、ネットワークを通して確立されたトンネルを有する、請求項８記載のノード。
【請求項１１】
新たな接続が、好ましい経路に沿った少なくとも一つの共通のセグメントを渡る既存の接続とで、帯域幅を分配し得るということを、分配定義が記述しており、かつ、
プロセッサーが、新たな接続と既存の接続との間に、少なくとも一つの共通のセグメント内の帯域幅割り当てを分配するように設定されている、請求項８〜１０のいずれかに記載のノード。
【請求項１２】
新たな接続および既存の接続が、ネットワークセグメントおよびネットワークノードの少なくとも一つにおける故障に対して、お互いを保護するように確立されている、請求項１１記載のノード。
【請求項１３】
プロセッサーが、予約プロトコルを使用した分配定義に応じるように設定されている、請求項８〜１０のいずれかに記載のノード。
【請求項１４】
計算された累積的な追加の帯域幅予約が、２つ以上の候補経路の全てについて等しい場合に、より低い優先順位の経路を選択する方法に立ち戻るように、プロセッサーが設定されている、請求項８〜１０のいずれかに記載のノード。
【請求項１５】
通信ネットワークであって、当該通信ネットワークは、
複数のネットワークセグメントを有し、
ネットワークノードを有し、
該ネットワークノードは、ネットワークインターフェースを有し、該ネットワークインターフェースは、ネットワーク内の他のノードと通信するように設定されており、かつ、
該ネットワークノードは、プロセッサーを有し、
該プロセッサーは、
ネットワーク内の接続同士の間での帯域幅の分配を定義する分配定義を受け入れ、該ネットワークを通って確立される新たな接続のための２つ以上の候補経路を特定し、その２つ以上の候補経路のそれぞれについて、分配定義に対応して、候補経路に沿ったセグメント内の新たな接続に割り当てられる累積的な追加の帯域幅予約を計算し、その２つ以上の候補経路の中から、累積的な追加の帯域幅予約の最小値を有する好ましい経路を選択し、かつ、その好ましい経路を使用して新たな接続を確立するように、設定されている、
前記通信ネットワーク。
【請求項１６】
少なくともいくつかのセグメントが、ネットワークノードと連結されて、リング構成をなすように配置されており、かつ、
該プロセッサーが、リングレベルのコネクション・アドミッション・コントロール（ＣＡＣ）モジュールを有し、該モジュールが、リング構成の第１および第２のリングレットをそれぞれ渡る第１および第２の候補経路を特定するように設定されており、かつ、第１および第２のリングレットの一つを渡る好ましい経路を選択するように設定されている、
請求項１５記載のネットワーク。
【請求項１７】
マルチセグメントを含む通信ネットワーク中のネットワークノードに使用されるコンピュータソフトウェア製品であって、
当該製品は、コンピュータ読取り可能な媒体を有し、該媒体にはプログラム命令が記憶されており、該命令は、コンピュータに読み込まれた時に、該コンピュータに、
該ネットワーク中の複数の接続同士の間での帯域幅の分配を定義する分配定義を受け入れさせ、該ネットワークを通って確立される新たな接続のための２つ以上の候補経路を特定させ、その２つ以上の候補経路のそれぞれについて、分配定義に対応して、候補経路に沿ったセグメント内の新たな接続に割り当てられる累積的な追加の帯域幅予約を計算させ、その２つ以上の候補経路の中から、累積的な追加の帯域幅予約の最小値を有する好ましい経路を選択させ、かつ、該好ましい経路を使用して新たな接続を確立させるものである、
前記コンピュータソフトウェア製品。
【請求項１８】
少なくともいくつかのセグメントが、ノードと連結されて、リング構成をなすように配置されており、かつ、
該命令が、コンピュータに、リング構成の第１および第２のリングレットをそれぞれ渡る第１および第２の候補経路を特定させ、かつ、第１および第２のリングレットの一つを渡る好ましい経路を選択させるものである、
請求項１７記載の製品。
【請求項１９】
新たな接続が、トンネルベースの通信プロトコルに従って、ネットワークを通して確立されたトンネルを有する、請求項１７記載の製品。
【請求項２０】
分配定義が、
新たな接続が、好ましい経路に沿った少なくとも一つの共通のセグメントを渡る既存の接続と共に、帯域幅を分配し得る、
ということを記述しており、かつ、
該命令が、コンピュータに、新たな接続と既存の接続との間の少なくとも一つの共通のセグメント内で、帯域幅割り当てを分配させるものである、請求項１７記載の製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概しては、通信ネットワークに関し、とりわけ、リング構成における帯域幅割り当てを分配(share)する通信接続のための経路(routes)を選択する方法およびシステムに関する。
【背景技術】
【０００２】
通信ネットワークは、時にリング構成(リング・コンフィギュレーション）を有する。例えば、一部のネットワークは、ＩＥＥＥ ８０２．１７ワーキンググループによって定義されているように、レジリエント・パケット・リング(Resilient Packet Ring (ＲＰＲ))構成を有する。ＲＰＲネットワークの構成に関する適用規格および更なる詳細は、www.ieee802.org/17 で入手できる。
【０００３】
接続（コネクション）は、時として、マルチプロトコル・ラベル・スイッチング (Multiprotocol Label Switching (ＭＰＬＳ))プロトコルなどのトンネルプロトコルを用いてリング上に確立される。ＭＰＬＳは、Rosen らによって、「Multiprotocol Label Switching Architecture」というタイトルで、 Request for Comments（ＲＦＣ） 3031 of the Internet Engineering Task Force（ＩＥＴＦ）（２００１年１月）に詳細に記載されている（これは、参照したことによって、本明細書に組み込まれる）。このＲＦＣ、および以下で言及するその他のＩＥＴＦ  ＲＦＣは、 www.ietf.org/rfc で入手できる。ＭＰＬＳは、また、Anderssonらにより、「Label Distribution Protocol Specification」というタイトルで、ＩＥＴＦ  ＲＦＣ  3036（２００１年１月）に記載されている（これは、参照したことによって、本明細書に組み込まれる）。
【０００４】
ＭＰＬＳは、ラベル・ディストリビューション・プロトコル（ＬＤＰ）を定義しており、該ラベル・ディストリビューション・プロトコルによって、あるＬＳＲは、他のＬＳＲにラベルの意味を知らせ、該ラベルは、それらの間でおよびそれらを通して、トラフィックを送るために使用される。制約ベースのラベル・スイッチド・パス（ＣＲ−ＬＳＰ）をセットアップするためのＬＤＰの拡張は、ＣＲ−ＬＤＰと呼ばれており、Jamoussi らにより、「Constraint-Based LSP Setup using LDP」というタイトルで、ＩＥＴＦ  ＲＦＣ  3212（２００２年１月）において定義されている（これは、参照したことによって、本明細書に組み込まれる）。ＣＲ−ＬＤＰは、ルーティングをされたネットワーク上のトラフィックの該制約ベースのルーティングのためのサポートを与える。ＬＳＰは、明示的なルート制約、クオリティ・オブ・サービス（ＱｏＳ）の制約、および、その他の制約に基づいてセットアップすることが出来る。
【０００５】
ＭＰＬＳトンネルをセットアップするために使用される別のプロトコルは、ＲＳＶＰ−ＴＥであり、それは、Awduche らにより「RSVP-TE: Extensions to RSVP for LSP Tunnels」というタイトルで、ＩＥＴＦ  ＲＦＣ  3209（２００１年１２月）に記載されている（これは、参照したことによって、本明細書に組み込まれる）。ＲＳＶＰ−ＴＥは、良く知られたリソース・リザベーション・プロトコル（ＲＳＶＰ）を拡張しており、該ＲＳＶＰをシグナリングプロトコルとして使用することで明示的にルーティングされたＬＳＰの確立を可能にしている。ＲＳＶＰ自体は、Braden らにより「Resource ReSerVation Protocol（ＲＳＶＰ）−Version 1 Functional Specification」というタイトルで、ＩＥＴＦ  ＲＦＣ  2205（１９９７年９月）に記載されている（これは、参照したことによって、本明細書に組み込まれる）。
【０００６】
一部の用途では、ネットワーク要素 (network elements) は、それらが提供するサービスに帯域幅などのリソースを割り当てる。例えば、ＩＥＴＦは、様々なサービスに様々なレベルのクオリティ・オブ・サービス（ＱｏＳ）を割り当てるためのフレームワークとして、インテグレーテッド・サービス（IntServ）のプロトコル・アーキテクチャを提示している。IntServは、Braden らにより「Integrated Services in the Internet Architecture: an Overview」というタイトルで、ＩＥＴＦ  ＲＦＣ  1633（１９９４年６月）に記載されている（これは、参照したことによって、本明細書に組み込まれる）。
【発明の開示】
【０００７】
発明の概要
通信ネットワークを渡る(traversing)通信接続は、時に、共通のネットワークセグメントにおける帯域幅割り当てを分配することを許容される。例えば、帯域幅分配(bandwidth-sharing)接続は、ネットワークノードまたはセグメントの故障に対してお互いを保護するためにセットアップされた接続を有し得る。
【０００８】
オープン・ショーテスト・パス・ファースト（ＯＳＰＦ）プロトコル、または、中間システム−中間システム（Intermediate System to Intermediate System;ＩＳ-ＩＳ）プロトコルなどのいくつかの既知のルーティングプロトコル、および、上述のＲＳＶＰ−ＴＥおよびＬＤＰなどのいくつかの既知のトンネル作成および予約プロトコルは、異なる接続同士の間で帯域幅割り当てを分配する機能を取り入れていない。その結果、そのようなプロトコルによって行われる経路選択は、帯域幅分配が許可されている場合にはしばしば最適ではない。
【０００９】
本発明の実施形態は、通信ネットワークを通る接続（コネクション）を確立するための改善された方法およびシステムを提供し、当該方法およびシステムは、新たな接続と既存の接続との間で帯域幅を分配する機能を取り入れている。分配定義(sharing definition)は、帯域幅割り当てを分配し得る接続を定義する。新たな接続を確立するために、ネットワークを通る２つ以上の候補経路が特定される。開示する方法およびシステムは、候補経路のそれぞれについて追加の帯域幅予約を計算し、該追加の帯域幅予約が対象となる候補経路に沿ったネットワークセグメントにわたって累積され、それが、新たな接続がこの経路を通って確立されるならば、新たな接続に割り当てられる。
【００１０】
累積的な追加の帯域幅予約は、帯域幅分配(bandwidth sharing)に起因して特定の経路に蓄えられ得る帯域幅の量の尺度と見なすことが出来る。累積的な追加の帯域幅予約の最小値を有する候補経路は、新たな接続を確立するための好ましい経路として選択される。以下に説明する方法およびシステムを使用することで、より大きなネットワーク容量およびより高いＱｏＳを達成することが出来る。
【００１１】
いくつかの実施形態では、開示される方法およびシステムは、時計回り（ＣＷ）リングレットおよび反時計回り（ＣＣＷ）リングレットとしばしば表される２つのリングレットを有するリング構成を通る通信接続を確立するために使用される。これらの実施形態では、該リングに付随するリングレベルのコネクション・アドミッション・コントロール（ＣＡＣ）モジュールが、２つのリングレットのそれぞれについて累積的な追加の帯域幅予約を計算する。次いでリングレベルのＣＡＣモジュールは、累積的な追加の帯域幅予約の最小値を有するリングレットを、新たな接続を確立するための好ましいリングレットとして選択する。
【００１２】
従って、本発明の一つの実施形態によれば、マルチセグメント(multiple segments)を含んだ通信ネットワークを通る接続を確立するための方法が提供され、当該方法は、
該ネットワーク中の複数の接続同士の間での帯域幅の分配を定義する分配定義を、与えることを含み、
該ネットワークを通って確立される新たな接続のための２つ以上の候補経路を特定することを含み、
該２つ以上の候補経路のそれぞれについて、前記分配定義に対応して、候補経路に沿ったセグメント内の新たな接続に割り当てられる累積的な追加の帯域幅予約を計算することを含み、
該２つ以上の候補経路の中から、累積的な追加の帯域幅予約の最小値を有する好ましい経路を選択することを含み、かつ、
該好ましい経路を使用して、新たな接続を確立することを含む。
【００１３】
ある実施形態では、少なくともいくつかのセグメントがリング構成をなすように配置されて、かつ、２つ以上の候補経路を特定することが、該リング構成のそれぞれの第１および第２のリングレットを渡って行く第１および第２の経路を特定することを含む。
【００１４】
別の実施形態では、新たな接続を確立することが、ネットワークを通るトンネルを、トンネルベースの通信プロトコルに従って確立することを含む。
【００１５】
また別の実施形態では、分配定義(sharing definition)が、
新たな接続が、好ましい経路に沿った少なくとも一つの共通のセグメントを横断する既存の接続と共に、帯域幅を分配し得る
ということを記述しており、かつ、
新たな接続を確立することが、新たな接続と既存の接続との間の少なくとも一つの共通のセグメント内で、帯域幅割り当てを分配することを含んでいる。
【００１６】
付加的または代替的には、新たな接続および既存の接続は、ネットワークセグメントおよびネットワークノードの少なくとも一つにおける故障(failure)に対して、お互いを保護するように確立される。
【００１７】
ある実施形態では、分配定義を与えることが、予約プロトコルを使用して、ネットワークのノードに分配定義を割り振ることを含む。
【００１８】
別の実施形態では、好ましい経路を選択することが、計算された累積的な追加の帯域幅予約が該２つ以上の候補経路の全てについて等しい場合に、より低い優先順位の経路を選択する方法に立ち戻ることを含む。
【００１９】
本発明の一つの実施形態によれば、ネットワークノードが更に提供され、当該ネットワークノードは、
ネットワークインターフェースを含み、該ネットワークインターフェースは、マルチセグメントを含む通信ネットワーク上で、他のネットワークノードと通信するように設定されており、かつ、
プロセッサーを含み、該プロセッサーは、該ネットワーク中の複数の接続同士の間での帯域幅の分配を定義する分配定義を受け入れるように設定されており、該プロセッサーは、該ネットワークを通って確立される新たな接続のための２つ以上の候補経路を特定するように設定されており、該プロセッサーは、該２つ以上の候補経路のそれぞれについて、分配定義に対応して、候補経路に沿ったセグメント内の新たな接続に割り当てられる累積的な追加の帯域幅予約を計算するように設定されており、該プロセッサーは、該２つ以上の候補経路の中から、累積的な追加の帯域幅予約の最小値を有する好ましい経路を選択するように設定されており、かつ、該プロセッサーは、その好ましい経路を使用して新たな接続を確立するように設定されている。
【００２０】
本発明の一つの実施形態によれば、通信ネットワークも提供され、当該通信ネットワークは、
複数のネットワークセグメントを含み、
ネットワークノードを含み、
該ネットワークノードは、ネットワークインターフェースを含み、該ネットワークインターフェースは、ネットワーク内の他のノードと通信するように設定されており、かつ、
該ネットワークノードは、プロセッサーを含み、
該プロセッサーは、
ネットワーク内の接続同士の間での帯域幅の分配を定義する分配定義を受け入れ、該ネットワークを通って確立される新たな接続のための２つ以上の候補経路を特定し、その２つ以上の候補経路のそれぞれについて、分配定義に対応して、候補経路に沿ったセグメント内の新たな接続に割り当てられる累積的な追加の帯域幅予約を計算し、その２つ以上の候補経路の中から、累積的な追加の帯域幅予約の最小値を有する好ましい経路を選択し、かつ、その好ましい経路を使用して新たな接続を確立するように、設定されている。
【００２１】
本発明の一つの実施形態によれば、マルチセグメントを含む通信ネットワーク中のネットワークノードに使用されるコンピュータソフトウェア製品（コンピュータソフトウェアプロダクト）が更に提供され、当該製品（プロダクト）は、コンピュータ読取り可能な媒体を有し、該媒体にはプログラム命令が記憶されており、該命令は、コンピュータに読み込まれた時に、該コンピュータに、該ネットワーク中の複数の接続同士の間での帯域幅の分配を定義する分配定義を受け入れさせ、該ネットワークを通って確立される新たな接続のための２つ以上の候補経路を特定させ、その２つ以上の候補経路のそれぞれについて、分配定義に対応して、候補経路に沿ったセグメント内の新たな接続に割り当てられる累積的な追加の帯域幅予約を計算させ、その２つ以上の候補経路の中から、累積的な追加の帯域幅予約の最小値を有する好ましい経路を選択させ、かつ、該好ましい経路を使用して新たな接続を確立させるものである。
【００２２】
本発明は、図面とあわせて解釈される、以下の本発明の実施形態の詳細な説明からより完全に理解されるであろう。
【発明を実施するための最良の形態】
【００２３】
図１は、本発明の一つの実施形態による通信ネットワーク２０を図式的に示すブロック図である。該ネットワーク２０は、マルチ(multiple)ネットワークノード２４を有する。ネットワークノード（ネットワーク結節点）は、例えば、レイヤ２スイッチ(layer 2 switches)、レイヤ３ルータ(layer 3 routers)、ブリッジ、コンセントレータ(concentrators)、アグリゲータ(aggregators)、および、アド／ドロップ多重化装置（add/drop multiplexers（ＡＤＭ））を有し得る。ノード２４は、セグメント２５として参照されるネットワークリンク(network links)によって接続され、該ネットワークリンクは、光ファイバーリンクまたは任意の他の好適な通信媒体を有し得る。
【００２４】
図１の例示的な構成では、Ａ、Ｂ、Ｃ、および、Ｄで示した４つのネットワークノードが、上記で言及したＩＥＥＥ  ８０２．１７規格で定義されるレジリエント・パケット・リング（ＲＰＲ）構成といったリング構成２６に設定されている。リング２６は、２つのリングレット(ringlet)、即ち、時計回り（ＣＷ）リングレット２８と、反時計回り（ＣＣＷ）リングレット３２とを有する。リング２６に属するセグメント２５を、リングセグメントと呼称する。
【００２５】
接続（コネクション）３６は、ネットワーク２０を通じて、特にリング２６を通じて、前以て定義されている。この例においては、接続３６は、１００Ｍｂｐｓの接続を有する（即ち、その経路(route)に沿ったセグメント内において、１００Ｍｂｐｓの帯域幅割り当てを必要としている）。接続３６の経路は、ノードＡにおいてリング２６に入り、時計回りリングレット２８を通ってノードＢまで行く。該経路は、ノードＢにおいてリングを去り、リング２６の外側に位置するノードＥにおいて終わる。
【００２６】
ネットワーク２０を通って確立される新たな５０Ｍｂｐｓの接続について次に考える。新たな接続は、ノードＡにおいてリング２６に入り、ノードＣにおいてリングを離れ、そしてノードＥにおいて終わるよう要求されていると仮定する。リング２６の２つのリングレットに対応して、そのような接続のための選び得る２つの経路が存在する。第１の候補経路４０は、ノードＡにおいてリング２６に入り、時計回りリングレット２８をたどって、ノードＢおよびＣを渡って行く。候補経路４０は、ノードＣにおいてリングを離れ、ノードＥにおいて終わる。第２の候補経路４４は、ノードＡにおいてリング２６に入り、反時計回りリングレット３２をたどって、ノードＤおよびＣを渡って行く。候補経路４４は、ノードＣにおいてリング２６を離れ、ノードＥにおいて終わる。
【００２７】
接続３６だけでなく、新たな接続、および、以下に説明する他の接続は、上述で言及したＭＰＬＳトンネル作成プロトコル(MPLS tunnel creation protocols)による、ＭＰＬＳラベル・スイッチド・パス（ＬＳＰ）、または、ＭＰＬＳトンネルを有し得る。代替的には、該接続は、ＡＴＭトンネル作成プロトコルなどの任意の他の好適な通信プロトコルを使用して定義され得る。
【００２８】
あるケースでは、新たな接続がその帯域幅割り当てを既存の接続３６と分け合う（シェアする）ことを許容されてもよい。例えば、新たな接続は、ノードのまたは経路に沿ったセグメントの故障(failure)に対して既存の接続を保護するようにセットアップされ得る。別の場合には、帯域幅は、ある程度のオーバーサブスクリプション(oversubscription)を伴う接続に割り当てられ得る。つまり、現実には全ての接続が割り当てられた全ての帯域幅を同時に使用するわけではないことを仮定して、分配される帯域幅は２つ以上の接続に同時に割り当てられても良い。代替的または付加的には、接続は、任意の他の理由または目的のために帯域幅割り当てを分け合うのを許容されているとして定義され得る。図１の例示的な構成では、新たな接続が、その経路に沿ったセグメント内において、５０Ｍｂｐｓの帯域幅割り当てを、既存の接続３６の１００Ｍｂｐｓの帯域幅割り当てと分け合い得ると仮定されている。
【００２９】
オープン・ショーテスト・パス・ファースト−トラフィック・エンジニアリング（ＯＳＰＦ−ＴＥ）または中間システム・ツー・中間システム−トラフィック・エンジニアリング（ＩＳ−ＩＳ−ＴＥ）プロトコルなどの、一部の既知のルーティングプロトコルは、通常、最小遅延、セグメントの最小数（ｈｏｐ）、最小コスト、および、平均または最大の利用可能帯域幅といった基準に基づいて、接続のための経路を選択する。これらの既知のプロトコルは、一般に、新たに確立される接続と、既に在る接続との間の依存関係（該接続間の帯域幅割り当てを分配する機能など）を取り入れていない。また、上記で言及したＲＳＶＰ−ＴＥおよびＬＤＰなどの一部の既知の予約プロトコルは、異なる接続の間の帯域幅割り当てを分配することを可能としない。
【００３０】
以下に説明する方法およびシステムは、リング２６における帯域幅割り当てを最適化するようにして、新たな接続を確立するための２つの候補経路の一つを選択する。上述した既知のルーティングプロトコルとは異なり、これらの方法およびシステムは、リング２６を渡る新たな接続と既存の接続との間で帯域幅を分配する機能を取り入れている。ある実施形態では、これらの方法およびシステムは、帯域幅分配を考慮して、最小の帯域幅割り当てを達成する好ましい経路を選択する。従って、図１に示した例では、経路４０が選択されることになる。一方、当該技術分野で知られているアルゴリズムおよびプロトコルは、分配を考慮することに注意せずに経路４４を選択する可能性があるが、これは、この経路のセグメントにおいてより多くの帯域幅が利用可能であるためである。帯域幅分配に基づく経路選択のプロセスの詳細を、図４を参照して以下で説明する。帯域幅分配の結果として、リング２６の容量は著しく向上し、与えられたＱｏＳにおいて、より多くの帯域幅を付与すること、または、与えられた容量において、より高いＱｏＳを付与することが可能となる。
【００３１】
概しては、リング２６を通る帯域幅分配接続は、同様のまたは異なる帯域幅を持ち得る。該接続は、リング２６の内部または外側のいずれかにおいて、同一のノードまたは異なるノードで始まり得、また、終わり得る。
【００３２】
本特許出願の文脈および特許請求の範囲において、用語「帯域幅(bandwidth)」は、任意の割り当てスキームによるネットワーク容量の割り当てを意味するために使用される。従って、割り当てられた帯域幅は、例えば、保証(guaranteed)帯域幅（認定情報速度、または、ＣＩＲとも呼ばれる）、平均帯域幅、および／または、ピーク帯域幅（ピーク情報速度またはＰＩＲとも呼ばれる）を有し得、これらは、ハード保証(hard guarantee)なしで利用可能である場合にのみ提供される。
【００３３】
図２は、本発明の別の実施形態による通信ネットワーク２０を図式的に示すブロックダイアグラムである。図２の例示的な構成では、リング２６は、Ａ、Ｂ、Ｃ、Ｄ、ＥおよびＦにて示した６つのノード２４を有する。接続４８は、ネットワークにおいて前以て定義されている。この例においては、接続４８は、１Ｇｂｐｓの接続を有する（即ち、その経路に沿ったセグメント内において、１Ｇｂｐｓの帯域幅割り当てを必要としている）。接続４８の経路は、ノードＡにおいてリング２６に入り、反時計回りリングレット３２をたどってノードＦ、ＥおよびＤを通り、ノードＣにおいてリング２６を去る。
【００３４】
ネットワーク２０を通って確立される別の１Ｇｂｐｓの接続について考える。新たな接続は、ノードＡにおいてリング２６に入り、ノードＣにおいて離れる必要があり、且つ、その帯域幅割り当てを既存の接続４８と分け合い得ると仮定する。新たな接続を確立するための選択可能な２つの経路が存在する。第１の候補経路５２は、反時計回りリングレット３２を通って接続４８の経路と同じ経路をたどり、ノードＡ、Ｆ、Ｅ、Ｄ、および、Ｃを渡っていく。第２の候補経路５６は、時計回りリングレット２８をたどり、ノードＡ、Ｂ、および、Ｃを渡って行く。以下に示すように、開示する方法およびシステムは、典型的には、帯域幅分配に基づいて、リング２６のノード２４において帯域幅割り当てを最適化するよう、経路５２を選択する。
【００３５】
上記図１および図２のネットワーク構成は、例示的な構成であり、単に概念的に明確にするために示している。本明細書に記載する方法およびシステムは、例えば、シンクロナス・オプティカル・ネットワーク（Synchronous Optical Network（ＳＯＮＥＴ））バイディレクショナル・ライン・スイッチ・リング（Bidirectional Line Switch Ring（ＢＬＳＲ））構成などの他のリング構成において使用することが出来る。一般に、本明細書に記載する実施形態は、主にリング上の帯域幅分配を扱っているとはいえ、開示する方法およびシステムは、決してリング構成に限定されず、マルチ(multiple)なネットワークノードおよびセグメントを含む他の任意の好適なネットワーク構成において接続を確立するために使用することが出来る。
【００３６】
図３は、本発明の一つの実施形態によるネットワークノード２４の詳細を図式的に示すブロック図である。ノード２４は、プロセッサー６０を有し、該プロセッサーは、ノードの様々な処理機能を実行し、また、ノード２４は、ネットワークインターフェース６２を有し、該ネットワークインターフェースは、ネットワーク２０内の他のノード２４と通信する。
【００３７】
ある実施形態では、２つ以上のノード２４がリング構成において設定されている場合に（上述の図１および図２におけるリング２６など）、これらのノードのうちの１つのプロセッサー６０が、リングレベルのコネクション・アドミッション・コントロール（connection admission control（ＣＡＣ））モジュール６４（セントラライズドＣＡＣ（ＣＣＡＣ）モジュールとも呼ぶ）を有する。ＣＣＡＣモジュールは、リング２６のリングセグメントのためにリングレベルのリソース割り当て機能を実行するのに関与する。
【００３８】
リングレベルのＣＡＣ機能には、例えば、所望のサービス品質で新たな接続を支えるのに充分な帯域幅がリングセグメントにおいて利用可能であることを確認すること、および、該リングに属するノードおよびセグメントにおいてそのような接続のための帯域幅予約(bandwidth reservations)を実行することなどが含まれる。明確にするために、後に続く説明においては、リング２６に属するノードおよびセグメントのためにＣＡＣ機能を実行するのに関与するＣＣＡＣモジュールを、リング２６のＣＣＡＣモジュールと呼ぶ。
【００３９】
典型的には、プロセッサー６０は、汎用コンピュータを有し、該汎用コンピュータは、本明細書に記載する機能を実行するためのソフトウェアでプログラムされている。該ソフトウェアは、例えば、ネットワーク上で電子的形態でコンピュータにダウンロードされても良く、または、別の方法としては、ＣＤ−ＲＯＭなどの有形の媒体でコンピュータに供給されても良い。更に別の方法としては、プロセッサー６０は、ハードウェアエレメントとソフトウェアエレメントとの組み合わせを使用して実装されても良い。
【００４０】
図４は、本発明の一つの実施形態による、接続を確立するための方法を図式的に示すフローチャートである。当該方法は、典型的には、リング２６のＣＣＡＣモジュール６４によって実行される。当該方法は、接続開始ステップ７０において、ＣＣＡＣモジュール６４が新たな接続の確立を開始することで始まる。
【００４１】
該ＣＣＡＣモジュールは、分配チェック(sharing checking)ステップ７２において、新たな接続が、リング２６を渡る既存の接続のいずれかとその分配割り当てを分け合い得るかどうかをチェックする。ある実施形態では、ＣＣＡＣモジュール６４は、帯域幅割り当てを分け合い得るリング２６を渡る接続を定義するアプリオリ(a-priori)な分配定義を受け入れる。代替的には、新たな接続のセットアッププロシージャが、他の接続を記述する分配定義を有していても良い（他の接続と共に、新たな接続が、その帯域幅割り当てを分け合い得る）。
【００４２】
ある実施形態では、分配定義は、上記で言及したＲＳＶＰ−ＴＥおよびＬＤＰなどのシグナリングまたは予約プロトコルを使用して、ノード２４に割り振られる。分配定義は、通常、ネットワーク設計の部分として、ネットワーク管理者などのオペレータによって定義される。ネットワークリソースの分配を定義しネットワークノードに分配定義を割り振る例示的な方法は、２００５年１２月１５日に出願された "Resource Sharing among Network Tunnels" というタイトルの米国特許出願シリアル番号１１／３０５，４８６に記載されており、それは本特許出願の出願人に帰属しており、その開示は参照したことにより本明細書に組み込まれる。
【００４３】
分配定義が、新たな接続がその帯域幅割り当てを少なくとも一つの既存の接続と分け合い得ると、記述している場合、ＣＣＡＣモジュール６４は、２つの候補経路（即ち、リング２６の時計回りリングレット２８を渡る経路、または、リング２６の反時計回りリングレット３２を渡る経路）のどちらが新たな接続のために使用されるべきかを決定する。予約計算ステップ７４において、ＣＣＡＣモジュール６４は、２つのリングレットのそれぞれについて、リング２６のリングセグメントにおいて新たな接続に割り当てられることになる累積的な追加の帯域幅予約を計算する。ある実施形態では、ステップ７４を実行する前に、ＣＣＡＣモジュール６４が、（両方のリングレットが新たな接続をサポートするのに充分な利用可能帯域幅を持っていること）を確認する。一つのリングレットのみが充分な帯域幅を持つ場合、このリングレットがデフォルトで選択される。
【００４４】
ある実施形態では、累積的な付加的な帯域幅予約は、次式によって与えられる。：
2009524970.tif 000003
ここで、ΔＢＷCW およびΔＢＷCCW は、それぞれ、時計回りのリングレットおよび反時計回りのリングレットでの、累積的な付加的な帯域幅を示す。
【００４５】
和(summation)が、対象となるリングレットの全てのリングセグメントＳ（このリングレットを渡る候補経路に属するもの）にわたって実行される。
2009524970.tif 000004
は、全ての接続に対してリングセグメントＳ内で割り当てられる帯域幅を示しており、前記全ての接続は新たな接続を含み、新たな接続が対象のリングレットを通じてセットアップされたならば、帯域幅分配を考慮する。
2009524970.tif 000005
は、全ての既にある接続（新たな接続を除く）に対してリングセグメントＳ内で割り当てられる帯域幅を示している。従って、
2009524970.tif 000006
なる項は、リングセグメントＳについての付加的な帯域幅予約(bandwidth reservation)を与える。
【００４６】
ΔＢＷCW およびΔＢＷCCW を計算する場合、ＣＣＡＣモジュール６４は、新たな接続と帯域幅を分け合う接続のみを考慮する。各リングセグメントにおいては、ＣＣＡＣモジュールは、新たな接続を伴う接続と、伴わない接続とに割り当てられる帯域幅の差を計算する。パラメータΔＢＷCWは、新たな接続が時計回りリングレット２８を通じて確立されることになる場合に、このリングレットのリングセグメントにおいて新たな接続に割り当てられることになる追加(extra)の帯域幅を累積(accumulate)する。同様に、ΔＢＷCCWは、反時計回りリングレット３２のリングセグメントにおいて、新たな接続に割り当てられることになる追加の帯域幅を累積する。特に、ΔＢＷCW およびΔＢＷCCWは、新たな接続がその帯域幅を、リング２６を通る少なくとも一つの既存の接続と分け合い得ることを考慮に入れている。
【００４７】
ＣＣＡＣモジュール６４は、リングレット比較ステップ７６において、２つのリングレットの累積的な追加の帯域幅予約の値を比較する。２つの値が異なる場合、ＣＣＡＣモジュール６４は、リングレット選択ステップ７８において、より小さいΔＢＷ値を有するリングレットを渡る候補経路を、新たな接続を確立するための好ましい経路として選択する。例えば、ΔＢＷCW ＜ΔＢＷCCW は、新たな接続に起因して割り当てられることになる総計の追加の帯域幅が、ＣＣＷリングレット３２においてよりも、ＣＷリングレット２８においての方がより少ないことを意味しており、逆もまた同様である。つまり、帯域幅分配を考慮して、より少ない帯域幅が費やされるリングレットが、より小さいΔＢＷ値を有することになる。
【００４８】
上記リングレット比較ステップ７６の結果が、ΔＢＷCW ＝ΔＢＷCCW である場合、当該方法は、次の優先順位(priority)選択ステップ８０において、より低い優先順位の選択方法(lower priority selection method)に立ち戻る。新たな接続がその帯域幅を他のいずれの接続とも分け合うことができない場合にも、当該方法は、上記分配チェックステップ７２からステップ８０に立ち戻る。
【００４９】
より低い優先順位の選択方法は、リング２６を通る新たな接続のための好ましい経路がＣＷリングレット２８を渡るか、または、ＣＣＷリングレット３２を渡るかを選択する任意の好適な方法を有し得る。例えば、より低い優先順位の選択方法は、新たな接続のソース・ノードとデスティネーション・ノードとの間で利用可能な平均の帯域幅を最大化しうる。より低い優先順位の選択方法は、接続間の帯域幅分配を取り入れていても良く、または、取り入れていなくても良い。ある実施形態では、２つ以上の、より低い優先順位の選択方法を使用することが出来、その場合、当該方法は、好ましい経路が選択されるまで、ステップ７６とステップ８０とをループする。
【００５０】
上記図１の例示的なネットワーク構成に戻って、図４の方法の適用は、次の結果を与えることになり：
2009524970.tif 000007
ここで、
2009524970.tif 000008
は、ノードＸをノードＹへ接続するセグメントにおいて、帯域幅を既存の接続とで分け合う能力を考慮しての、新たな接続に割り当てられるべき追加の帯域幅を示す。
【００５１】
従って、ＣＷリングレット２８を渡る候補経路４０が、費やされる帯域幅を最小化する、新たな接続のための好ましい経路として選択されることになる。これとは反対に、帯域幅分配を考慮せずにＣＷリングレットおよびＣＣＷリングレットの帯域幅の使用を均衡させようとする方法であれば、代わりに候補経路４４を選択して、より多くの帯域幅が割り当てられることを招いたであろう。
【００５２】
上記図２の例示的なネットワーク構成においては、図４の方法の適用は、次の結果を与えることになる：
2009524970.tif 000009
【００５３】
従って、この場合、ＣＣＷリングレット３２を渡る候補経路５２が、費やされる帯域幅を最小化する、新たな接続のための好ましい経路として選択されることになる。これとは反対に、帯域幅分配を考慮せずに、利用可能な帯域幅を最大化しようとするか、または、セグメントの数を最小化しようとする方法であれば、代わりに候補経路５６を選択して、より多くの帯域幅が割り当てられることを招いたであろう。
【００５４】
本明細書に記載した実施形態は、帯域幅分配に基づく経路選択を主に扱っているが、本発明の原理は、接続を支え、処理するために使用される他のネットワークリソースの分配を考慮することによる経路選択のために使用することが出来る。例えば、分配されるリソースは、メモリ空間およびポートなどのネットワークノードのリソースを含み得る。リング構成を扱うのに加えてまたはその代わりに、本明細書に記載した方法およびシステムは、任意の好適なネットワーク構造において経路を選択するために使用することが出来る。
【００５５】
更にそれに加えて、または、その代わりに、本明細書に記載した方法は、普通では帯域幅分配を考慮に入れない既知のルーティングプロトコルと組み合わせて使用することが出来る。例えば、あるネットワーク構成において、ネットワークノードは、ＯＳＰＦ−ＴＥまたはＩＳ−ＩＳ−ＴＥなどの既知のレイヤ３プロトコルを使用し、ネットワークセグメントにおいて利用可能な帯域幅を通知する。次いで通知された帯域幅がルーティングを決定するために使用される。ある実施形態では、ネットワークノードは、以下に記載する方法を使用して、複数の接続同士の間での帯域幅分配を考慮に入れて、利用可能な帯域幅を計算し通知することが出来る。それゆえ、その結果としてのルーティングの決定は、非明示的に帯域幅分配に依存し、ネットワークリソースの、より良い使用を可能とすることになる。同様に、本明細書に記載した方法およびシステムは、複数の接続同士の間での帯域幅分配を考慮することによって、帯域幅に関連する他のルーティングプロトコルを強化するために使用することが出来る。
【００５６】
このように、上記した実施形態は、例示のために言及されており、本発明は、上に特に示して説明したものに限定されないことが理解されよう。むしろ、本発明の範囲は、上に記載した様々な特徴の組み合わせおよび部分的組み合わせの両方、並びに、上の説明を読んでいる当業者に思い付くであろう、先行技術において開示されていない、その変形および改良を含む。
【図面の簡単な説明】
【００５７】
【図１】図１は、本発明の一つの実施形態による通信ネットワークを図式的に示すブロック図である。
【図２】図２は、本発明の別の実施形態による通信ネットワークを図式的に示すブロック図である。
【図３】図３は、本発明の一つの実施形態によるネットワークノードの詳細を図式的に示すブロック図である。
【図４】図４は、本発明の一つの実施形態による、接続を確立するための方法を図式的に示すフローチャートである。
【図１】
2009524970.tif 000010
【図２】
2009524970.tif 000011
【図３】
2009524970.tif 000012
【図４】
2009524970.tif 000013
【国際調査報告】
2009524970.tif 000014