(57)【特許請求の範囲】
【請求項１】
最も厳しいＱｏＳ制約を有するクラスに専用の１つの超仮想ネットワーク（２）と、少なくとも１つの他の仮想ネットワーク（３）とを備える、それぞれが少なくとも１つの特定のＱｏＳクラスに専用であるカスタマイズされた仮想ネットワーク（２、３）を備えるように仮想化されたデータ通信ネットワーク（１）内で、入ってくるトラフィックフローに関する先験的な知識なしにアドミッションを制御し、入ってくるトラフィックフローにリソースを割り当てるための方法であって、
入口ノード（７）と出口ノード（８）の間で運ばれるように意図されたフロー（６）の到着時、前記超仮想ネットワーク（２）を介した前記入口ノード（７）から前記出口ノード（８）への第１の経路（９）を決定するステップと、
前記フロー（６）の最初のＮ個のパケット（１１）を解析することによって前記フロー（６）のＱｏＳクラスを決定するステップと、
前記超仮想ネットワーク（２）を横断して前記第１の経路（９）を介して前記フロー（６）の前記最初のＮ個のパケット（１１）を送信するステップと、
前記フロー（６）の前記決定されたＱｏＳクラスに専用の仮想ネットワーク（３）を決定するステップと、
前記決定された仮想ネットワーク（３）が超仮想ネットワーク（２）と異なる場合は、前記決定された仮想ネットワーク（３）を介して前記入口ノード（７）から前記出口ノード（８）への第２の経路（１０）を決定するステップ、または、
前記決定された仮想ネットワーク（３）が超仮想ネットワーク（２）と等しい場合は、第１の経路（９）に等しい第２の経路（１０）を決定ステップと、
前記第２の経路（１０）を介して前記フロー（６）のパケット（１２）をＮ＋１番のパケットから送信するステップとを備えることを特徴とする、方法。
【請求項２】
第１の経路（９）を決定するステップが、最初のＮ個のパケット（１１）を送信するために前記第１の経路（９）の使用可能性をチェックするステップを備える、請求項１に記載の方法。
【請求項３】
使用可能性がチェックされない場合は、第１の経路（９）を決定するステップの後の諸ステップが、前記フロー（６）を拒否するステップで置き換えられる、請求項２に記載の方法。
【請求項４】
第２の経路（１０）を決定するステップが、前記フロー（６）のパケット（１２）をＮ＋１番目のパケットから送信するために前記第２の経路（１０）の使用可能性をチェックするステップを備える、請求項１から３のいずれか一項に記載の方法。
【請求項５】
使用可能性がチェックされない場合は、第２の経路（１０）を決定するステップの後の諸ステップが、前記フロー（６）を拒否するステップで置き換えられる、請求項４に記載の方法。
【請求項６】
第２の経路（１０）を決定するステップで使用可能性がチェックされない場合は、別の仮想ネットワークを介した第２の経路（１０）を決定するステップで前記ステップを置き換える、請求項４に記載の方法。
【請求項７】
前記別の仮想ネットワークが、あまり厳しくないＱｏＳ制約を有するクラスに専用の仮想ネットワークである、請求項６に記載の方法。
【請求項８】
使用可能性のチェックが正確または確率的である、請求項２から７のいずれか一項に記載の方法。
【請求項９】
前記第１の経路を介した送信ステップの後の諸ステップが、フロー（６）が終了するときに停止され、または取り消される、請求項１から８のいずれか一項に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の技術領域は、通信網、特に自律的な自己管理型の仮想化されたネットワークの領域である。本発明は、ネットワークのエッジノードまたは境界ノードのトラフィック制御に関し、パケットレベルではなくフロー粒度レベルで定義されたネットワーク操作に取り組む。フローは、サービス品質、ＱｏＳ、すなわち遅延制約または帯域幅／スループット制約に関して同じ特性により関連しているパケットのシーケンスである。フローは、送信元アドレス、宛先アドレス、送信元ポート、宛先ポート、プロトコルおよび時間相関によって特徴付けられる。所与のときに、これらのパラメータのすべてを共有するパケットは、同じフローに関係する。次いで、これらのパラメータに基づいて、フローを分離することが可能である。
【背景技術】
【０００２】
通信網は自律的な、自己管理型の仮想化された基盤へと進化している。データ通信網のこうした「次世代」は、いくつかのネットワーク機能性について再考することを必要とし、このネットワーク機能性の中には、ユーザ−ネットワークインターフェース上のトラフィック制御がある。フローがパケットに置き換わり、次世代ネットワークの基本単位になるので、トラフィック制御などのネットワーク操作が有利には、フロー粒度で定義されるということは注目に値する。
【０００３】
自律的な自己管理型のデータ通信システム内では、入ってくるトラフィックフローに関する先験的な知識を利用することができない。すなわち、こうしたシステムは、明示的なユーザ−ネットワークシグナリングなしに働く。
【０００４】
仮想化されたネットワーク環境では、リンクリソースおよびノードリソースは、特定のＱｏＳ制約によって特徴付けられたアプリケーションのクラスにカスタマイズされた仮想ネットワーク、ＶＮを作成するように仮想化される。
【０００５】
こうした状況では、トラフィック制御は、サービスクラスごとに、すなわち同等に仮想ネットワークごとに行われなければならない。
【０００６】
知られていない、または宣言されていないトラフィックフロー、すなわちその先験的な情報が知られていないフローを制御することは、フローの性質に関する先験的な情報（たとえばアプリケーションの特性、タイプ）がないので、アドミッション制御およびリソース割当てにとって極め難しいことである。
【０００７】
「オンザフライ」のトラフィック識別および分類手順が知られており、入ってくるフローを特徴付けるために、ユーザ−ネットワークインターフェース上で、すなわちネットワークの境界ノード上で展開される。高速トラフィック分類手法は典型的に、Ｎをおよそ４個から１０個のパケットと等しいものとして、フローからの最初のＮ個のパケットを解析することを必要とする。トラフィック分類の可能な１つの原理は、フローを分離した後に、たとえばフローの最初のパケットのサイズを測定することである。前記最初のパケットがフローに関するプロトコル情報を含むので、パケットのサイズは、フローのアプリケーションを示し、アプリケーションはクラスを示す。たとえば、Ｌ．Ｂｅｒｎａｉｌｌｅ、Ｒ．Ｔｅｘｅｉｒａ、Ｋ．Ｓａｌａｍａｔｉａｎ、「Ｅａｒｌｙ  ａｐｐｌｉｃａｔｉｏｎ  ｉｄｅｎｔｉｆｉｃａｔｉｏｎ」、Ｐｒｏｃ．ｏｆ  ＡＣＭ  ＣｏＮｅｘｔ  ２００６を参照されたい。
【０００８】
仮想化されたリソースを備えたデータ通信システム内の宣言されていないトラフィックフローのフロー制御の問題は、２レベルに分割され得る問題を引き起こす。
【０００９】
アドミッション制御レベル：アドミッション制御は、フローを受け付けるべきか、それとも拒否するべきか決定する役割を担う。第１の問題は、前記フローがまだ識別されず分類されていない場合にフローからの最初のＮ個のパケットのアドミッション制御を行うために生じる。第２の問題は、フローの分類が決定されている場合の前記フローのＮ＋１番目および後続のパケットのアドミッション制御のために生じる。
【００１０】
リソース割当てレベル：リソース割当ては、受け付けられたフローの送信用のリソースを割り当てる役割を担う。入ってくる新しいフローへのリソース割当てが、前記フローの特性を知る前に行われなければならないということにより、問題が生じる。
【００１１】
最適なフロー制御に関していくつかの従来技術の文献が存在する。たとえば、下記を参照されたい：
−  Ｐ．Ｋｅｙ、Ｌ．Ｍａｓｓｏｕｌｉｅ、「Ｃｏｎｔｒｏｌ  ｏｆ  ｃｏｍｍｕｎｉｃａｔｉｏｎ  ｎｅｔｗｏｒｋｓ：ｗｅｌｆａｒｅ  ｍａｘｉｍｉｚａｔｉｏｎ  ａｎｄ  ｍｕｌｔｉｐａｔｈ  ｔｒａｎｓｆｅｒｓ」、Ｐｈｉｌｏｓｏｐｈｉｃａｌ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｆ  ｔｈｅ  Ｒｏｙａｌ  Ｓｏｃｉｅｔｙ、３６６（１８７２）、２００８年
−  Ｐ．Ｋｅｙ、Ｌ．Ｍａｓｓｏｕｌｉｅ、Ｄ．Ｔｏｗｓｌｅｙ、「Ｐａｔｈ  Ｓｅｌｅｃｔｉｏｎ  ａｎｄ  Ｍｕｌｔｉｐａｔｈ  Ｃｏｎｇｅｓｔｉｏｎ  Ｃｏｎｔｒｏｌ」、Ｐｒｏｃ．ｏｆ  ＩＭＦＯＣＯＭ  ２００７、または
−  Ｍ．Ｃｈｉａｎｇ、Ｓ．Ｈ．Ｌｏｗ、Ａ．Ｒ．Ｃａｌｄｅｒｂａｎｋ、Ｊ．Ｃ．Ｄｏｙｌｅ，「Ｌａｙｅｒｉｎｇ  ａｓ  ｏｐｔｉｍｉｚａｔｉｏｎ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ：Ａ  ｍａｔｈｅｍａｔｉｃａｌ  ｔｈｅｏｒｙ  ｏｆ  ｎｅｔｗｏｒｋ  ａｒｃｈｉｔｅｃｔｕｒｅｓ」、Ｐｒｏｃ．ｏｆ  ＩＥＥＥ、９５巻、１号、２５５−３１２頁、２００７年１月。
【００１２】
いくつかの従来技術文献は、さらにネットワーク仮想化のためのものである。たとえば、下記を参照されたい：
−ｈｔｔｐ：／／ｗｗｗ．ｃｓ．ｐｒｉｎｃｅｔｏｎ．ｅｄｕ／〜ｊｒｅｘ／ｐａｐｅｒｓ／ＶＮｅｍｂｅｄ．ｐｄｆで入手可能なＭ．Ｙｕ、Ｙ．Ｙｉ、Ｊ．ＲｅｘｆｏｒｄおよびＭ．Ｃｈｉａｎｇ、「Ｒｅｔｈｉｎｋｉｎｇ  ｖｉｒｔｕａｌ  ｎｅｔｗｏｒｋ  ｅｍｂｅｄｄｉｎｇ：Ｓｕｂｓｔｒａｔｅ  ｓｕｐｐｏｒｔ  ｆｏｒ  ｐａｔｈ  ｓｐｌｉｔｔｉｎｇ  ａｎｄ  ｍｉｇｒａｔｉｏｎ」、Ｐｒｏｃ．ｏｆ  ＡＣＭ  ＳＩＧＣＯＭＭ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｒｅｖｉｅｗ、２００８年４月、
−  Ｙ．Ｚｈｕ、Ｍ．Ａｍｍａｒ、「Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ａｓｓｉｇｎｉｎｇ  ｓｕｂｓｔｒａｔｅ  ｎｅｔｗｏｒｋ  ｒｅｓｏｕｒｃｅｓ  ｔｏ  ｖｉｒｔｕａｌ  ｎｅｔｗｏｒｋ  ｃｏｍｐｏｎｅｎｔｓ」、Ｐｒｏｃ．ｏｆ  ＩＮＦＯＣＯＭ  ２００６
【００１３】
しかし、これらの研究はすべて、フローの明示的な特性化、したがってフロークラスについての先験的な知識に基づく（ｌｉｅ  ｏｎ）。したがって、それらの文献は、宣言されていないフローのオンライン分類を対処するようになされないことがある。
【００１４】
フローのオンライン分類を用いたアドミッション制御およびリソース割当てを実現する既存の１つの解決策は、分類手順が終了するまで、すなわちＮ個の最初のパケットが受信されるまで、フローからの最初のＮ個のパケットを格納することにある。しかし、この解決策は、誤判定に対してネットワークを「保護する」よいやり方であるが、解決策を実際の実装に適さないものにするいくつかの問題を提示する。最も重要な問題の一部は、フローからの最初のＮ個のパケットを、それらのパケットをネットワーク内に解放する前に格納することにより、以下のようになるということである：
−  特に一定のビットレートおよび低いビットレートのフローに追加の遅延および遅延変化が加わる。この問題は、低いビットレートのフローを生成するＶｏＩＰなどの遅延に敏感なアプリケーションにとって極めて重要なことであり得る。
−  システムが作業量を節約できなくなり（ｎｏｎ−ｗｏｒｋ  ｃｏｎｓｅｒｖｉｎｇ）、したがってリソースが浪費されることがある。
−  トラフィックプロファイルが変更される：こうした方法は、トラフィックのバースト性を高め、さらに悪いことには、トラフィックをバースト的なものにする。これによって、ネットワークのコアに輻輳が生じることがある。この説明は、非常に単純で直覚的である：コアルータを介して相互接続された２、３個の境界ルータを想像されたい。境界ルータ上の２つのアドミッション制御は、Ｎ個のパケットのバーストを同時にコアルータに解放するという意味で「同期」され得る。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】Ｌ．Ｂｅｒｎａｉｌｌｅ、Ｒ．Ｔｅｘｅｉｒａ、Ｋ．Ｓａｌａｍａｔｉａｎ、「Ｅａｒｌｙ  ａｐｐｌｉｃａｔｉｏｎ  ｉｄｅｎｔｉｆｉｃａｔｉｏｎ」、Ｐｒｏｃ．ｏｆ  ＡＣＭ  ＣｏＮｅｘｔ  ２００６
【非特許文献２】Ｐ．Ｋｅｙ、Ｌ．Ｍａｓｓｏｕｌｉｅ、「Ｃｏｎｔｒｏｌ  ｏｆ  ｃｏｍｍｕｎｉｃａｔｉｏｎ  ｎｅｔｗｏｒｋｓ：ｗｅｌｆａｒｅ  ｍａｘｉｍｉｚａｔｉｏｎ  ａｎｄ  ｍｕｌｔｉｐａｔｈ  ｔｒａｎｓｆｅｒｓ」、Ｐｈｉｌｏｓｏｐｈｉｃａｌ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｆ  ｔｈｅ  Ｒｏｙａｌ  Ｓｏｃｉｅｔｙ、３６６（１８７２）、２００８年
【非特許文献３】Ｐ．Ｋｅｙ、Ｌ．Ｍａｓｓｏｕｌｉｅ、Ｄ．Ｔｏｗｓｌｅｙ、「Ｐａｔｈ  Ｓｅｌｅｃｔｉｏｎ  ａｎｄ  Ｍｕｌｔｉｐａｔｈ  Ｃｏｎｇｅｓｔｉｏｎ  Ｃｏｎｔｒｏｌ」、Ｐｒｏｃ．ｏｆ  ＩＭＦＯＣＯＭ  ２００７
【非特許文献４】Ｍ．Ｃｈｉａｎｇ、Ｓ．Ｈ．Ｌｏｗ、Ａ．Ｒ．Ｃａｌｄｅｒｂａｎｋ、Ｊ．Ｃ．Ｄｏｙｌｅ，「Ｌａｙｅｒｉｎｇ  ａｓ  ｏｐｔｉｍｉｚａｔｉｏｎ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ：Ａ  ｍａｔｈｅｍａｔｉｃａｌ  ｔｈｅｏｒｙ  ｏｆ  ｎｅｔｗｏｒｋ  ａｒｃｈｉｔｅｃｔｕｒｅｓ」、Ｐｒｏｃ．ｏｆ  ＩＥＥＥ、９５巻、１号、２５５−３１２頁、２００７年１月。
【非特許文献５】Ｍ．Ｙｕ、Ｙ．Ｙｉ、Ｊ．ＲｅｘｆｏｒｄおよびＭ．Ｃｈｉａｎｇ、「Ｒｅｔｈｉｎｋｉｎｇ  ｖｉｒｔｕａｌ  ｎｅｔｗｏｒｋ  ｅｍｂｅｄｄｉｎｇ：Ｓｕｂｓｔｒａｔｅ  ｓｕｐｐｏｒｔ  ｆｏｒ  ｐａｔｈ  ｓｐｌｉｔｔｉｎｇ  ａｎｄ  ｍｉｇｒａｔｉｏｎ」、Ｐｒｏｃ．ｏｆ  ＡＣＭ  ＳＩＧＣＯＭＭ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｒｅｖｉｅｗ、２００８年４月
【非特許文献６】ｈｔｔｐ：／／ｗｗｗ．ｃｓ．ｐｒｉｎｃｅｔｏｎ．ｅｄｕ／〜ｊｒｅｘ／ｐａｐｅｒｓ／ＶＮｅｍｂｅｄ．ｐｄｆ
【非特許文献７】Ｙ．Ｚｈｕ、Ｍ．Ａｍｍａｒ、「Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ａｓｓｉｇｎｉｎｇ  ｓｕｂｓｔｒａｔｅ  ｎｅｔｗｏｒｋ  ｒｅｓｏｕｒｃｅｓ  ｔｏ  ｖｉｒｔｕａｌ  ｎｅｔｗｏｒｋ  ｃｏｍｐｏｎｅｎｔｓ」、Ｐｒｏｃ．ｏｆ  ＩＮＦＯＣＯＭ  ２００６
【非特許文献８】Ｊｉａｙｕｅ  ＨｅおよびＪｅｎｎｉｆｅｒ  Ｒｅｘｆｏｒｄ、「Ｔｏｗａｒｄｓ  Ｉｎｔｅｒｎｅｔ−ｗｉｄｅ  ｍｕｌｔｉｐａｔｈ  ｒｏｕｔｉｎｇ」、ＩＥＥＥ  Ｎｅｔｗｏｒｋ  Ｍａｇａｚｉｎｅ、２００８年３月
【発明の概要】
【発明が解決しようとする課題】
【００１６】
オンライン分類は、自律ネットワークへの重要な問題である。したがって、オンライン分類を含み、またそれに適応されたフロー制御は、入ってくる、宣言されていないフローに自己適応させる自律ネットワークにおいて解決すべき重要な問題である。
【００１７】
ここで解決されるべき技術的問題は、仮想化されたリソースおよび複数のサービスクラスを備えた自己管理型のデータ通信システム内のフロー制御手順を設計することであり、このシステムでは、ユーザ−ネットワークインターフェースは、入ってくる新しいトラフィックフローの特性について先験的な知識をもたない。
【００１８】
本発明は、この問題に取り組み、それを解決する。
【課題を解決するための手段】
【００１９】
本発明の目的は、最も厳しいＱｏＳ制約を有するクラスに専用の１つの超仮想ネットワークと、少なくとも１つの他の仮想ネットワークとを備える、それぞれが少なくとも１つの特定のＱｏＳクラスに専用であるカスタマイズされた仮想ネットワークを備えるように仮想化されたデータ通信ネットワーク内で、入ってくるトラフィックフローに関する先験的な知識なしにアドミッションを制御し、入ってくるトラフィックフローにリソースを割り当てるための方法であって、
−  入口ノードと出口ノードの間で運ばれるように意図されたフローの到着時、前記超仮想ネットワークを介した前記入口ノードから前記出口ノードへの第１の経路を決定するステップと、
−  前記フローの最初のＮ個のパケットを解析することによって前記フローのＱｏＳクラスを決定するステップと、
−  前記超仮想ネットワークを横断して前記第１の経路を介して前記フローの前記最初のＮ個のパケットを送信するステップと、
−  前記フローの前記決定されたＱｏＳクラスに専用の仮想ネットワークを決定するステップと、
−  前記決定された仮想ネットワークが超仮想ネットワークと異なる場合は、前記決定された仮想ネットワークを介した前記入口ノードから前記出口ノードへの第２の経路を決定するステップ、または、
−  前記決定された仮想ネットワークが超仮想ネットワークと等しい場合は、第１の経路に等しい第２の経路を決定ステップと、
−  前記第２の経路を介して前記フローのパケットをＮ＋１番のパケットから送信するステップとを備える。
【００２０】
本発明の別の特徴によれば、第１の経路を決定するステップは、
最初のＮ個のパケットを送信するために前記第１の経路の使用可能性をチェックするステップを備える。
【００２１】
本発明の別の特徴によれば、第１の経路を決定するステップの後の諸ステップは、使用可能性がチェックされない場合は、前記フローを拒否するステップで置き換えられる。本発明の別の特徴によれば、第２の経路を決定するステップは、前記フローのパケットをＮ＋１番目のパケットから送信するために前記第２の経路の使用可能性をチェックするステップを備える。
【００２２】
本発明の別の特徴によれば、第２の経路を決定するステップの後の諸ステップは、使用可能性がチェックされない場合は、前記フローを拒否するステップで置き換えられる。
【００２３】
本発明の別の特徴によれば、第２の経路を決定するステップで使用可能性がチェックされない場合は、別の仮想ネットワークを介した第２の経路を決定するステップで前記ステップを置き換える。
【００２４】
本発明の別の特徴によれば、前記別の仮想ネットワークは、あまり厳しくないＱｏＳ制約を有するクラスに専用の仮想ネットワークである。
【００２５】
本発明の別の特徴によれば、使用可能性のチェックは、正確または確率的である。
【００２６】
本発明の別の特徴によれば、前記第１の経路を介した送信ステップの後の諸ステップは、フローが終了するときに停止され、または取り消される。
【００２７】
本発明の他の特徴、詳細および利点は、図面に関して下記に示された詳細な例示的説明からより明らかになろう。
【図面の簡単な説明】
【００２８】
【図１】宣言されていないフローを送信しながら、２つの仮想ネットワークを備える仮想化されたネットワークの概略図である。
【発明を実施するための形態】
【００２９】
図１によれば、物理的なネットワーク１が表されている。前記ネットワーク１は例示的に、６つのノードＡ−Ｆを備える。前記物理的なネットワーク１上に、物理ノードおよび物理リンクを部分的または全体的に使用した少なくとも２つの仮想ネットワーク２、３が展開されている。この図では、たとえば２つの仮想ネットワーク２、３が示されている。第１の仮想ネットワーク２、ＶＮ１は、それぞれが物理ノードＡ、Ｃ、Ｄ、ＥおよびＦ上に実装された仮想ノードＡ”、Ｃ”、Ｄ”、Ｅ”およびＦ”を備える。第２の仮想ネットワーク３、ＶＮ２は、それぞれ物理ノードＡ、Ｂ、ＤおよびＥ上に実装された仮想ノードＡ’、Ｃ’、Ｄ’、Ｅ’を備える。仮想リンクは、複数の物理リンクに渡って実装されている。いくつかの仮想リンクが、１つの物理リンクを共有することがある。たとえば、図の最下部にズームされた詳細で示されたように、物理リンクＡ−Ｅは、仮想リンクＡ”−Ｅ”、４と、仮想リンクＡ’−Ｅ’、５の間で共有されている。
【００３０】
次いで、それぞれの仮想ネットワーク２、３は、少なくとも１つの特定のＱｏＳクラスに専用とされてよい。複数の仮想ネットワークは、最も厳しいＱｏＳ制約を有するクラスに専用の１つの超仮想ネットワーク２を備える。前記超ＶＮに加えて、他のいくつかの仮想ネットワーク３が見られ得る。
【００３１】
本発明について例示するために、ＶＮ１、２が超仮想ネットワークであり、ＶＮ２、３が、別のＱｏＳクラスに専用の１つの他の仮想ネットワーク３であると考える。たとえば、超仮想ネットワーク２は、遅延に敏感なアプリケーションに最適化されてよく、他の仮想ネットワーク３は、スループットに敏感なアプリケーション最適化されてよい。リソース仮想化のこのやり方は単に、トポロジおよび仮想リンクへの帯域幅割当てが、効用関数としてＶＮ１については遅延を、ＶＮ２については帯域幅使用、すなわちスループットを使用してネットワークのマルチパスルーティング最適化を行う結果であることを意味する。遅延に敏感なアプリケーションおよびスループットに敏感なアプリケーションがそれぞれ異なるＱｏＳクラスに属するということは注目に値する。また、明らかに３つ以上の仮想ネットワークがあってもよい。
【００３２】
本発明による方法は、アドミッション制御、および入ってくるトラフィックフロー６へのリソース割当ての問題に関する。ほとんどの従来技術アドミッションコントローラおよび／またはリソース割当て器（ａｓｓｉｇｎｅｒ）は、フロー６に関する先験的な情報に基づく。一般に、フロー６に関する情報は、フロー６のユーザ／送信者によって提供される。これによって、前記情報をネットワーク管理システムに取り入れることが必要になり、とりわけそれは、前記ユーザと、アドミッション制御および／またはリソース割当ての役割を担うノード、すなわちフロー６がそれを通って前記ネットワークに入るネットワークの境界ノード７との間のシグナリングを必要とする。本発明の１つの重要な特徴は、自律的な自己管理型のネットワーク管理型システムを提供するためにシグナリングが回避され、その代わりに、境界ノード７への到着時にフローを「オンザフライ」で解析することから、入ってくるフロー６に関する情報が自動的に得られるということである。したがって、どんな先験的な知識もが、オンラインで自動的に収集された情報で置き換えられる。
【００３３】
本発明の主な考えは、入ってくるフロー６を、それを分類する前に一時的に受け付けるということである。分類は、入ってくるフロー６の最初のＮ個のパケット１１を解析する必要がある。フロー６のクラスが知られていない間、すなわちＮ番目のパケットの到着まで、フロー６は初期設定により、最優先クラスに関係すると見なされなければならない。したがって、フロー６は、初めは、最優先のものと見なされ、最優先クラスに専用の仮想ネットワーク、すなわち超仮想ネットワーク２を介して最優先のものとして送信される。フロー６のクラスが決定された後は、フローをその実際のクラスに従って扱うために再ルーティングが行われてよい。
【００３４】
前記考えを実現するために、この方法は、下記のステップを備える。
【００３５】
入口ノード７と出口ノード８の間で運ばれるように意図されたフロー６が到着するとき、フロー６にまず最高優先度が割り当てられる。次いで、前記入口ノード７から前記出口ノード８への第１の経路９が決定される。優先度がその最高レベルであるので、前記第１の経路９は、最高優先度に専用の前記超仮想ネットワーク２上で決定される。
【００３６】
前記フロー６の第１のパケット１１が到着するときに、そのアプリケーション、したがって前記フロー６の対応するＱｏＳクラスを決定するために、前記第１のパケット１１が解析される。前記ＱｏＳクラスを決定するには、所与の数、Ｎ個のパケットが必要である。Ｎは典型的には、最良のプロセスでは、４と１０の間にある。
【００３７】
それと並行して、クラスが決定されるまで、すなわちｎ番目のパケットが到着するまで、優先度は、最も厳しいＱｏＳ制約に対応する最高優先度と依然として見なされる。したがって、前記フロー６の最初のＮ個のパケット１１は、前記超仮想ネットワーク２を横断して、前記以前に決定された第１の経路９を介して送信される。
【００３８】
好ましい一実施形態では、フロー６のプロファイルを修正し得るパケットの送信を遅延させないために、前の両方のステップがインタリーブされる。換言すると、それぞれパケットが到着し、解析され、または解析のためにコピーされ、連続して送信される。そうすると、処理時間は、各パケットについて同じである。
【００３９】
しかし、処理全体に関しては、解析時間は無視されてよい。
【００４０】
前記フロー６の決定されたＱｏＳクラスに基づいて、前記フロー６の前記決定されたＱｏＳクラスに専用の仮想ネットワーク３が決定されてよい。
【００４１】
次いで、２つのケースが生じることがある。第１に、仮想ネットワーク３は、超仮想ネットワーク２と異なる。次いで、前記決定された仮想ネットワーク３を介した前記入口ノード７から前記出口ノード８への第２の経路１０が決定されてよい。次いで、超仮想ネットワークを緩和するために、再リルーティングが適用されてよい。
【００４２】
第２に、仮想ネットワーク３は、超仮想ネットワーク２と同じであると決定される。すなわち、フロー６はこと上、最も厳しいＱｏＳ制約に対応するＱｏＳクラスに関係する。その場合、送信は、前記超仮想ネットワーク２を介して続行してよい。次いで、第２の経路１０は、第１の経路９と等しいと見なされてよい。
【００４３】
次いで、Ｎ＋１番のパケットからの、前記フロー６のパケット１２の残りは、前記第２の経路１０を介して送信されてよい。
【００４４】
アドミッション制御およびリソース割当てが２つの連続したステップで行われるので、使用可能性チェックもまた、それぞれ第１の経路９および第２の経路の決定時、２つのステップで適用されてよい。
【００４５】
第１の経路９を決定する間、使用可能性チェックが適用されてよく、したがって、前記第１の経路９は、少なくとも最初のＮ個のパケット１１を送信できるほど十分なリソースを有する。
【００４６】
前記第１の使用可能性がチェックされ得ない場合、すなわち、前記超仮想ネットワーク２を介してフロー６の最初のＮ個のパケット１１を送信できる経路を入口ノード７と出口ノード８の間で見つけることができない場合、この方法は、入ってくるフロー６を拒否するステップで終了する。換言すると、最後のステップ、すなわち第１の経路９の決定ステップの後の諸ステップは、拒否ステップで置き換えられる。
【００４７】
第２の経路１０を決定する間、使用可能性チェックが適用されてよく、したがって、前記第２の経路１０は、新しく決定された仮想ネットワーク３を介して、Ｎ＋１番から開始する残りのパケット１２を送信できるほど十分なリソースを有する。
【００４８】
前記第２の使用可能性がチェックされ得ない場合、すなわちフロー６のＮ＋１番から開始する残りのパケット１２を前記新しく決定された仮想ネットワーク３を介して送信できる経路を入口ノード７と出口ノード８の間で見つけることができない場合は、この方法は、入ってくるフロー６を拒否するステップで終了する。換言すると、最後のステップ、すなわち第２の経路１０を決定するステップの後の諸ステップは、拒否ステップで置き換えられる。
【００４９】
あるいは、第２の経路１０を決定するステップで使用可能性がチェックされない場合は、別の仮想ネットワークを介して新しい試みが行われてよい。換言すると、この方法は、使用可能性を提供する第２の経路１０を決定するために、いくつかの仮想ネットワークに渡って繰り返される。
【００５０】
好ましくは、前記新しい試みは、あまり厳しくないＱｏＳ制約を有するクラスに専用の仮想ネットワーク上で適用される。次いで、この方法は、１つの仮想ネットワークが使用可能となるまで、ＱｏＳ制約の厳しさの降順で順序付けられた仮想ネットワークのリストに渡って繰り返されてよい。そうではなく、どの仮想ネットワークも使用可能な経路を提供できない場合は、フロー６は、最終的に拒否されてよい。
【００５１】
上記の実施形態で使用されるいくつかの使用可能性チェックはそれぞれ、正確に行われてよい。すなわち、使用可能性は、フロー６を収容するのに必要な正確なリソースが、必要なときに必要なところで使用可能である場合にだけチェックされる。
【００５２】
上記の実施形態で使用されるいくつかの使用可能性チェックはそれぞれ、確率論的なやり方で行うこともできる。すなわち、使用可能性は、フロー６を収容するのに必要なリソースが、所与の受付け確率より大きい、必要時に使用可能である確率を示す場合にチェックされる。
【００５３】
前記第１の経路を介した送信ステップの後の諸ステップは、フロー６の終了時に停止され、または取り消されることが当業者には明らかである。
【００５４】
最初のＮ個のパケット１１の処理の後、この方法は、フローに対してその行為を終了することも明らかである。これは、この方法の利点である。
【００５５】
フロー６がＮ個より少ないパケットを含む場合、この方法も短縮される。
【００５６】
マイス（ｍｉｃｅ）とも呼ばれる前記短いフローでは、下記の２つのケースが生じ得ることに留意されたい：
−  フロー６は、最高クラスのトラフィックに属する：この方法は、フロー６がそのクラスの一部と正確に見なされ送信されているので正しい。
−  フロー６は、最高クラスのトラフィックに属さない：この場合、短いフローは、この方法によって、そうでない場合でも「キング」として扱われている。
【００５７】
しかし、最近のトラフィック調査は、小さいトラフィックフロー、すなわちマイス（たとえば、わずか数十パケット）が、たとえばインターネットなどのネットワーク内で循環するトラフィックフローの大部分に相当することを示している。しかし、それらは、インターネットトラフィックの全体量より著しく小さい帯域幅のパーセントを消費する。これは、大きいフロー、すなわちエレファントが、総帯域幅の大部分を消費し、さらに少数のトラフィックフロー表すことを意味している。
【００５８】
この状況では、短いフローを「キング」として扱うことは、他のタイプのトラフィックフローのＱｏＳ保証に小さい影響を及ぼす。さらに、小さいフローは通常、低遅延でその宛先に送り届けなければならない制御メッセージを表すことが当業者には理解されよう。
【００５９】
本発明による方法の別の利点は、そのスケーラビリティである。前記スケーラビリティは、ネットワークのエッジの境界ルータだけがアドミッション制御機構を有するということから推論することができ、前記機構は、フロー６からの最初のＮ個のパケット１１に対してだけ作用する。フロー６が識別され分類されると、アドミッション制御は、受け付けられたフローに関する状態情報を保持する必要はなく、到着する新しいフローだけに焦点を当てる。
【００６０】
超仮想ネットワーク２から別の仮想ネットワーク３へのフロー６の再ルーティングは、フロー６内のパケットシーケンスに干渉しないことも明らかである。フロー６が分割され、または複数の経路間でルーティング／再ルーティングされるとき、フローのパケットシーケンスを保証するいくつかのトラフィック分割手法が存在することが、トラフィック分割の当業者には理解されよう。
【００６１】
この主題に関しては、たとえば文献：Ｊｉａｙｕｅ  ＨｅおよびＪｅｎｎｉｆｅｒ  Ｒｅｘｆｏｒｄ、「Ｔｏｗａｒｄｓ  Ｉｎｔｅｒｎｅｔ−ｗｉｄｅ  ｍｕｌｔｉｐａｔｈ  ｒｏｕｔｉｎｇ」、ＩＥＥＥ  Ｎｅｔｗｏｒｋ  Ｍａｇａｚｉｎｅ、２００８年３月を参照することができる。
【図１】
0005245007.tif 000002