(57)【要約】【課題】ネットワークサービス処理システムを実現するための方法及びシステムを提供すること。【解決手段】本システムは、複数のネットワークドメインに対応する複数のネットワークコントローラにおける分散グラフ処理を利用する。各ネットワークコントローラは各自のネットワークドメインのネットワークグラフを管理及び維持する。各ネットワークコントローラは、各自のネットワークドメインでノード(又はバーテックス)と通信する一方、ネットワークコントローラ同士がパス発見及び演算の目的で互いに通信する。【選択図】図1
2017076971.tif 000002
【特許請求の範囲】
【請求項１】
ソースバーテックス及び宛先バーテックスを指定するネットワークリクエストを第1ネットワークコントローラで受信する工程であって、前記ソースバーテックスは前記第1ネットワークコントローラにより管理される第1ネットワークドメインに位置し、前記宛先バーテックスは前記第2ネットワークコントローラにより管理される第2ネットワークドメインに位置する、工程；及び
複数のネットワークドメインに対応する、前記第1ネットワークコントローラ及び前記第2ネットワークコントローラを含む複数のネットワークコントローラにおいて、分散グラフ処理を実行し、前記ソースバーテックス及び前記宛先バーテックスの間のネットワークパスを決定する工程；
を含む方法であって、前記分散グラフ処理は：
各々のネットワークドメインの中で、ネットワークドメインにおける各バーテックスと前記ソースバーテックスとの間の最小パス距離を識別する工程；
前記複数のネットワークコントローラの間でコントローラメッセージを送信する工程であって、前記コントローラメッセージの各々は、送信バーテックス識別子と、ターゲットバーテックス識別子と、前記ソースバーテックスから前記ターゲットバーテックス識別子に対応するターゲットバーテックスまでの最小パス距離とを指定し、前記送信バーテックス識別子に対応する送信バーテックスは、前記コントローラメッセージを送信するネットワークコントローラのネットワークドメインに含まれ、前記ターゲットバーテックスは前記コントローラメッセージを受信するネットワークコントローラのネットワークドメインに含まれる、工程；及び
前記ネットワークコントローラに対応する前記ネットワークドメイン内の各バーテックスについて、各ネットワークコントローラがパス情報を記録する工程であって、前記パス情報は、前記ソースバーテックスからバーテックスまでの最小パス距離と、前記ソースバーテックスまでの最小パス距離をもたらすバーテックスのうちの親バーテックスの親バーテックス識別子とを含む、工程；
を有する方法。
【請求項２】
前記分散グラフ処理は、前記第1ネットワークドメインにおける前記第1ネットワークコントローラにより始まる、請求項1に記載の方法。
【請求項３】
前記分散グラフ処理は、前記第2ネットワークドメインにおける前記第2ネットワークコントローラにより始まる、請求項1に記載の方法。
【請求項４】
前記コントローラメッセージを送信することは、前記ソースバーテックスと前記宛先バーテックスとの間の全てのネットワークパスが記録されるまで、前記コントローラメッセージの送信を反復することを含み、前記パス情報は、前記複数のネットワークドメインの間の所与のネットワークトポロジによっては変動しない、請求項1に記載の方法。
【請求項５】
前記最小パス距離に対応する前記パス情報を収集する工程；及び
収集された前記パス情報に基づいて、前記ソースバーテックスと前記宛先バーテックスとの間を最小距離で結ぶ出力パスを算出する工程；
を更に有する請求項1に記載の方法。
【請求項６】
前記パス情報を収集することが、各ネットワークドメインの境界バーテックスのみに関するパス情報を収集することを更に含む、請求項5に記載の方法。
【請求項７】
前記パス情報を収集することは、前記第1ネットワークコントローラ及び前記第2ネットワークコントローラのうちの何れかによって実行され、
当該方法は、前記第1ネットワークコントローラが、前記出力パスとともに前記ネットワークリクエストに応答する工程を更に有する請求項5に記載の方法。
【請求項８】
前記複数のネットワークコントローラは、ソフトウェア構築ネットワークコントローラである、請求項1に記載の方法。
【請求項９】
バーテックスに関して前記パス情報が記録された後に、前記バーテックスについて新たなパス情報を受信する工程；及び
前記新たなパス情報が、前記パス情報に記録されている最小パス距離より大きな最小パス距離の新たな値を示す場合、前記新たなパス情報を破棄する工程；
を更に有する請求項1に記載の方法。
【請求項１０】
第1ネットワークコントローラ及び第2ネットワークコントローラを含む複数のネットワークドメインの各々に関連する複数のネットワークコントローラを有するネットワークシステムであって、前記複数のネットワークコントローラの各々は：
メモリ；
前記メモリに結合されたプロセッサ；及び
前記メモリに保存されたプロセッサ実行可能な命令；
を有し、前記複数のネットワークコントローラは、
ソースバーテックス及び宛先バーテックスを指定するネットワークリクエストを第1ネットワークコントローラで受信する工程であって、前記ソースバーテックスは前記第1ネットワークコントローラにより管理される第1ネットワークドメインに位置し、前記宛先バーテックスは前記第2ネットワークコントローラにより管理される第2ネットワークドメインに位置する、工程；及び
複数のネットワークコントローラにおいて、分散グラフ処理を実行し、前記ソースバーテックス及び前記宛先バーテックスの間のネットワークパスを決定する工程；
を行うための命令を実行するように動作することが可能であり、前記分散グラフ処理は：
各々のネットワークドメインの中で、ネットワークドメインにおける各バーテックスと前記ソースバーテックスとの間の最小パス距離を識別する工程；
前記複数のネットワークコントローラの間でコントローラメッセージを送信する工程であって、前記コントローラメッセージの各々は、送信バーテックス識別子と、ターゲットバーテックス識別子と、前記ソースバーテックスから前記ターゲットバーテックス識別子に対応するターゲットバーテックスまでの最小パス距離とを指定し、前記送信バーテックス識別子に対応する送信バーテックスは、前記コントローラメッセージを送信するネットワークコントローラのネットワークドメインに含まれ、前記ターゲットバーテックスは前記コントローラメッセージを受信するネットワークコントローラのネットワークドメインに含まれる、工程；及び
前記ネットワークコントローラに対応する前記ネットワークドメイン内の各バーテックスについて、各ネットワークコントローラがパス情報を記録する工程であって、前記パス情報は、前記ソースバーテックスからバーテックスまでの最小パス距離と、前記ソースバーテックスまでの最小パス距離をもたらすバーテックスのうちの親バーテックスの親バーテックス識別子とを含む、工程；
を含むことを特徴とするネットワークシステム。
【請求項１１】
前記分散グラフ処理は、前記第1ネットワークドメインにおける前記第1ネットワークコントローラにより始まる、請求項10に記載のネットワークシステム。
【請求項１２】
前記分散グラフ処理は、前記第2ネットワークドメインにおける前記第2ネットワークコントローラにより始まる、請求項10に記載のネットワークシステム。
【請求項１３】
前記コントローラメッセージを送信するための命令は、前記ソースバーテックスと前記宛先バーテックスとの間の全てのネットワークパスが記録されるまで、前記コントローラメッセージの送信を反復するための命令を含み、前記パス情報は、前記複数のネットワークドメインの間の所与のネットワークトポロジによっては変動しない、請求項10に記載のネットワークシステム。
【請求項１４】
前記最小パス距離に対応する前記パス情報を収集する工程；及び
収集された前記パス情報に基づいて、前記ソースバーテックスと前記宛先バーテックスとの間を最小距離で結ぶ出力パスを算出する工程；
を行うための命令を更に有する請求項10に記載のネットワークシステム。
【請求項１５】
前記パス情報を収集するための命令が、各ネットワークドメインの境界バーテックスのみに関するパス情報を収集するための命令を更に含む、請求項14に記載のネットワークシステム。
【請求項１６】
前記パス情報を収集するための命令は、前記第1ネットワークコントローラ及び前記第2ネットワークコントローラのうちの何れかによって実行され、
前記命令は、前記第1ネットワークコントローラが、前記出力パスとともに前記ネットワークリクエストに応答する工程を行うための命令を更に有する請求項14に記載のネットワークシステム。
【請求項１７】
前記複数のネットワークコントローラは、ソフトウェア構築ネットワークコントローラである、請求項10に記載のネットワークシステム。
【請求項１８】
バーテックスに関して前記パス情報が記録された後に、前記バーテックスについて新たなパス情報を受信する工程；及び
前記新たなパス情報が、前記パス情報に記録されている最小パス距離より大きな最小パス距離の新たな値を示す場合、前記新たなパス情報を破棄する工程；
を行うための命令を更に有する請求項10に記載のネットワークシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は一般にデータセンターネットワークに関連し、特にネットワークサービス処理システム等に関連する。
【背景技術】
【０００２】
ソフトウェア構築ネットワーク(software  defined-network：SDN)の出現とともに、所定のネットワークドメインの管理のために、分散されたSDNコントローラが使用されている。更に、ネットワークトポロジの維持及び管理は、SDNの中心的な機能である。SDN、モノのインターネット(IoT)及び高帯域幅ワイヤレスシステムの大規模な展開により、多種多様な接続されるネットワークリソースの大規模な処理が、エンドトゥエンドのネットワークサービスを提供する上で不可欠となっている。
【０００３】
一般に、様々なネットワークドメインが様々なSDNコントローラにより管理される場合、各々のSDNコントローラは、グローバルな経路の演算及び提供を可能にするために、ローカルメモリにグローバルマップを保持することになる。同様な構成は、マルチレイヤマルチドメイン分散経路演算エンジン(path  computation  engines  ：PCE)により使用されるかもしれない。各ネットワークコントローラでグローバルネットワークマップの様々なコピーを更新し続けることは、グローバルな同期のための演算負担の大きなオーバーヘッド及び低いスケーラビリティに関連し、かつ、ネットワークトポロジを不必要に露呈してしまう。
【発明の概要】
【０００４】
一形態では、開示される方法は、ソースバーテックス及び宛先バーテックスを指定するネットワークリクエストを第1ネットワークコントローラで受信する工程を含む。本方法では、ソースバーテックスは第1ネットワークコントローラにより管理される第1ネットワークドメインに位置し、宛先バーテックスは第2ネットワークコントローラにより管理される第2ネットワークドメインに位置する。本方法は、複数のネットワークドメインに対応する、前記第1ネットワークコントローラ及び前記第2ネットワークコントローラを含む複数のネットワークコントローラにおいて、分散グラフ処理を実行し、前記ソースバーテックス及び前記宛先バーテックスの間のネットワークパスを決定する工程を含む。本方法では、分散グラフ処理は、各々のネットワークドメインの中で、ネットワークドメインにおける各バーテックスとソースバーテックスとの間の最小パス距離を識別する工程を含む。本方法において、分散グラフ処理は、複数のネットワークコントローラの間でコントローラメッセージを送信する工程であって、前記コントローラメッセージの各々は、送信バーテックス識別子と、ターゲットバーテックス識別子と、前記ソースバーテックスから前記ターゲットバーテックス識別子に対応するターゲットバーテックスまでの最小パス距離とを指定する。本方法において、送信バーテックス識別子に対応する送信バーテックスは、コントローラメッセージを送信するネットワークコントローラのネットワークドメインに含まれ、ターゲットバーテックスはコントローラメッセージを受信するネットワークコントローラのネットワークドメインに含まれる。本方法において、分散グラフ処理は、ネットワークコントローラに対応する前記ネットワークドメイン内の各バーテックスについて、各ネットワークコントローラがパス情報を記録する工程を含み、パス情報は、ソースバーテックスからバーテックスまでの最小パス距離と、ソースバーテックスまでの最小パス距離をもたらすバーテックスのうちの親バーテックスの親バーテックス識別子とを含む。
【０００５】
開示される任意の方法形態において、分散グラフ処理は、第1ネットワークドメインにおける第1ネットワークコントローラにより始まってもよい。開示される任意の方法形態において、分散グラフ処理は、第2ネットワークドメインにおける第2ネットワークコントローラにより始まってもよい。
【０００６】
開示される任意の方法形態において、コントローラメッセージを送信することは、ソースバーテックスと宛先バーテックスとの間の全てのネットワークパスが記録されるまで、コントローラメッセージの送信を反復することを含み、パス情報は、複数のネットワークドメインの間の所与のネットワークトポロジによっては変動しない。
【０００７】
開示される任意の方法形態において、本方法は、最小パス距離に対応する前記パス情報を収集する工程；及び、収集されたパス情報に基づいて、ソースバーテックスと宛先バーテックスとの間を最小距離で結ぶ出力パスを算出する工程；を更に含んでもよい。
【０００８】
開示される任意の方法形態において、パス情報を収集することが、各ネットワークドメインの境界バーテックスのみに関するパス情報を収集することを更に含んでもよい。開示される任意の方法形態において、パス情報を収集することは、第1ネットワークコントローラ及び第2ネットワークコントローラのうちの何れかによって実行され、本方法は、第1ネットワークコントローラが、出力パスとともにネットワークリクエストに応答する工程を更に有する。
【０００９】
開示される任意の方法形態において、複数のネットワークコントローラは、SDNコントローラであってもよい。
【００１０】
開示される任意の方法形態において、本方法は、バーテックスに関してパス情報が記録された後に、バーテックスについて新たなパス情報を受信する工程；及び、新たなパス情報が、パス情報に記録されている最小パス距離より大きな最小パス距離の新たな値を示す場合、新たなパス情報を破棄する工程；を更に有する。
【００１１】
分散グラフ処理を利用するネットワークサービス処理システムを実現するための更に開示される形態は、非一時的なコンピュータ読み取り可能な媒体を含む製品、及び、コンピュータ読み取り可能な媒体に保存されるコンピュータ実行可能な命令を含む。分散グラフ処理を利用するネットワークサービス処理システムを実現する別の形態は、複数のネットワークドメインそれぞれに関連する複数のネットワークコントローラを有するネットワークシステムを含む。分散グラフ処理を利用するネットワークサービス処理システムを実現する別の形態は、メモリ、メモリに結合されるプロセッサ、及び、メモリに保存される子ピュータ実行可能な命令を有するネットワークコントローラを含む。
【図面の簡単な説明】
【００１２】
本発明並びにその特徴及び利点についての十分な理解のため、添付図面とともに以下の記述が参照される。
【００１３】
【図１】一形態によるネットワークの選択された要素についてのブロック図。
【００１４】
【図２】一形態による分散ネットワークドメインの選択された要素についてのネットワーク図。
【００１５】
【図３】一形態によるネットワークグラフ処理の選択された要素についてのブロック図。
【００１６】
【図４Ａ】分散グラフ処理を利用するネットワークサービス処理システムを実現する方法形態のうちの選択された要素を示すフローチャート。
【００１７】
【図４Ｂ】分散グラフ処理を利用するネットワークサービス処理システムを実現する方法形態のうちの選択された要素を示すフローチャート。
【００１８】
【図５】一形態によるネットワークコントローラの選択された要素についてのブロック図。
【発明を実施するための形態】
【００１９】
以下の説明では、開示される対象事項の議論を促すために、詳細な事項が具体例により説明される。しかしながら、開示される形態は例示に過ぎず、可能な全ての形態の網羅ではないことが、当業者には明らかであろう。
【００２０】
本開示を通じて、ハイフンが付いた形式の参照番号は、あるエレメントのうちの特定のインスタンスを指し、ハイフンが付いてない形式の参照番号は、一般的又は集合的にエレメントを指している。例えば、(図示してはいないが)具体例として、ウィジェット(widget)「12-1」はウィジェットのクラスのうちのインスタンスを指し、ウィジェットのクラスはウィジェット「12」のように集合的に言及されてよく、そのうちの任意の何れもウィジェット「12」として一般的に言及されてよい。図面及び明細書において、同様な番号は同様な要素を表現するように意図されている。
【００２１】
本願で説明されるように、エンドトゥエンドのネットワークサービスを提供する適切なフレームワークを提供するネットワークサービス処理システムが開示され、そのサービスは様々なネットワークドメインにわたる経路処理リクエストに応じることを含む。本願で開示されるネットワークサービス処理システムは、クラウドアプリケーションの局所性(locality)を促し、様々なネットワークの問題に対処するように融通が利く。本願で開示されるネットワークサービス処理システムは、バーテックスセントリック分散グラフ処理を適用しており、その処理は、所与のネットワークトポロジに対する収束が達成されるまで、様々なバーテックスが、コントローラメッセージを反復的に利用して経路情報を交換することを可能にする。本願で開示されるネットワークサービス処理システムでは、各々のネットワークコントローラは全体的な(又はグローバルな)ネットワークトポロジを維持しておらず、そうではなく、そのネットワークコントローラにより管理されるネットワークドメイン内の頂点に対するネットワークリクエストに関連するトポロジ情報とともにネットワークグラフを生成する。従って、本願で開示されるネットワークサービス処理システムでは、バーテックス同士(vertices)は互いに経路情報を送信せず、そうではなく、ネットワークドメインを管理する各ネットワークコントローラが、ネットワークドメイン内の各バーテックスにメッセージを送信し、ネットワークコントローラがコントローラメッセージを互いに通信する。このようにして、ネットワークにおける演算処理及びグローバルなパスディスカバリに関して低遅延をもたらすスケーラブルなネットワークサービス処理システムが実現される。
【００２２】
図面を参照すると、図1は一実施例によるネットワークドメイン100を示し、ネットワークドメイン100は、個々のネットワーク要素(network  elements：NE)であるバーテックス(又はノード又は頂点)に基づいている。図1では、ソフトウェア構築ネットワーク(SDN)コントローラ108及び物理ネットワーク110を含むネットワークドメイン100が示されている。図1では、物理ネットワーク110により表現される基礎的な光ネットワークは、コネクションの帯域幅を調整するように構成される光転送ネットワーク(OTN)又はフレキシブル光データプレーン(例えば、フレキシブルトランシーバ)であってよい。
【００２３】
図1において、SDNコントローラ108は、ネットワーク要素112を有するように示されるネットワークドメイン100を管理する。ネットワーク要素112は、スイッチ、ルーター等のような様々なタイプのネットワーク機能を表現し、かつ、様々なタイプの物理インターフェースを相互接続するハードウェアを含んでよい。ネットワークドメイン100は、様々な距離を有するネットワーク要素間のコネクションとともに、ネットワーク要素NE_A112-1、ネットワーク要素NE_B112-2、ネットワーク要素NE_C112-3、ネットワーク要素NE_D112-4、ネットワーク要素NE_E112-5、及び、ネットワーク要素NE_F112-6を含む。すなわち、ネットワークドメイン100は、SDNコントローラ108により管理される単独のネットワークドメインのネットワークトポロジを表現する。より大きなネットワークが複数のネットワークドメインを含む場合、それぞれの個別的なネットワークドメインがそれぞれのSDNコントローラにより管理される。
【００２４】
様々なネットワークドメイン間の従来の経路処理を促すため、マルチレイヤマルチドメイン分散経路処理エンジン(a  multilayer  multidomain  distributed  path  computation  engine：PCE)が使用され、PCEにおいてはグローバルネットワークマップがそれぞれのSDNコントローラで維持され、これにより、各々のSDNコントローラが、グローバルネットワークに対するネットワーク要請リクエストに応じて経路処理を実行することを許容している。しかしながら、そのような分散SDNコントローラの分散経路処理アーキテクチャは、ある不都合な特性に関連付けられてしまう。例えば、各々のSDNコントローラでグローバルネットワークマップを保存することはかなりのメモリ量を消費し、及び、ネットワーク内の様々なドメイン全体を通じて物理ネットワーク110を露呈し、そのような露呈は望まれないかもしれない。ネットワークトポロジは常に変化するので、全てのグローバルネットワークマップの更新を維持するために、グローバルな同期が実行され、そのような更新の維持はかなりのネットワークオーバーヘッドを含む。更に、従来のルーティングプロトコルが使用される場合、ネットワークトポロジの発見及び経路計算は、ネットワーク要素112がメッセージを互いに送信してネットワーク経路及び到達範囲における何らかの変化を発見する一方、ネットワークトポロジの通信結果が各々のSDNコントローラ108で更新されることを当てにする。グローバルネットワークが膨大な数のドメイン及びネットワーク要素を含む場合、経路処理及び分散ネットワーク動作に含まれる結果的に次々と生じる通信は、非効率的で遅延したものになってしまう。
【００２５】
本願において更に詳細に開示されるように、ネットワークドメイン100はネットワークサービス処理システムに含まれ、そのシステムは、物理ネットワーク110等のような複数のネットワークドメインのそれぞれに関連するSDNコントローラ108のような複数のネットワークコントローラ同士の間でコントローラメッセージ及び分散グラフ処理を利用する。各々のネットワークコントローラは、本願で開示されるようなネットワークサービス処理エンジン(a  network  service  computation  engine：NSCE)を動作させ、ネットワークサービス処理システムを協働して実現する。
【００２６】
図2を参照すると、一形態による分散ネットワークドメイン200のうちの選択された要素がネットワーク図として示されている。分散ネットワークドメイン200は、本願で開示されるようにネットワークサービス処理システムを実現する複数のSDNコントローラ108それぞれにより管理されるマルチドメインネットワークの実施例を表現している。分散ネットワークドメイン200は特定のネットワークトポロジとして示されているが、ネットワークの多種多様なタイプ及びサイズ並びに様々な数のネットワークドメインが、本願で開示されるネットワークサービス処理システムとともに使用されてよいことが、理解されるであろう。分散ネットワークドメイン200は、概略的な例として示されているに過ぎず、寸法を描いているわけではない。
【００２７】
図2において、分散ネットワークドメイン200は、個々のバーテックスにより構成される複数のドメイン110を含む。バーテックスは、例えば、スイッチ、ルーター、ネットワークエレメント、データセンター、サブネットワーク、サブドメイン等のような様々なネットワークノードのうちの何れを表現してもよい。従って、各々のバーテックスは、他のバーテックスへのネットワーク接続を提供することに加えて、例えばネットワークサービスを提供することやネットワークアプリケーションをサポートすること等のような処理リソースを提供するように動作してもよい。図示されるように、コネクションリンクがバーテックス同士の間に提供され、図2では、コネクションリンクに関する相対的な経路距離を表現する整数値とともにラベル付けされている。コネクションリンクはイントラドメイン(ドメイン内)及びインタードメイン(ドメイン間)に形成されてよいことに留意を要する。
【００２８】
分散ネットワークドメイン200における(複数の)バーテックスは、バーテックスによる到達可能なネットワークを表現し、そのネットワークはソースバーテックス(又は起点)Sと宛先バーテックス(又は終点)Dとの間の潜在的な経路を提供する。具体的には、SDNコントローラ108-Aは、ソースバーテックスS並びにバーテックスA1、A2及びA3を含むドメイン110-Aを管理し；SDNコントローラ108-Bは、バーテックスB1、B2、B3、B4、B5、B6及びB7を含むドメイン110-Bを管理し；SDNコントローラ108-Cは、バーテックスC1、C2及びC3並びに宛先バーテックスDを含むドメイン110-Cを管理し；SDNコントローラ108-Dは、バーテックスD1、D2及びD3を含むドメイン110-Dを管理する。分散ネットワークドメイン200において、各々のSDNコントローラ108は各自自身のドメイン110内のバーテックスと通信するが、バーテックス同士が互いに通信することは控える。SDNコントローラ108も互いに通信し、リング、スター、バス等のような適切な任意のトポロジを利用して共にネットワーク化される(ただし、簡明化のため詳細に図示されてはいない)。一実施例では、SDNコントローラ108間の通信は、サイドバンドネットワークチャネル或いは管理目的の他のネットワークコネクションを利用してもよく、他のチャネルはバーテックス間のネットワークコネクションと干渉しないものであり、ネットワークコネクションは、サービスプロバイダによる顧客への通信サービスとして提供されるペイロードネットワークを表現する。
【００２９】
図3を参照すると、一形態による分散グラフ処理300のうちの選択された要素が示されている。分散グラフ処理は、順に実行されるスーパーステップ(superstep)SS01-SS09の反復を示す。各々のスーパーステップは、SDNコントローラ108でコントローラメッセージ又は情報を受信すること、個々のネットワークドメイン110でローカルな動作を実行すること、及び、他のSDNコントローラ108にコントローラメッセージを送出することを包含する。分散グラフ処理300は分散ネットワークドメイン200を利用する適切なネットワーク動作システムとともに使用されてよいことに留意を要する。各々のバーテックスを制御することに加えて、各々のSDNコントローラ108は、個々のネットワークドメイン110のネットワークトポロジを追跡し続ける。
【００３０】
分散グラフ処理300においては、経路情報を有する2つの値のボックスは、各ネットワークドメイン110内の各バーテックスに関し、ソースバーテックスからバーテックスまでの最小パス距離と、その最小パス距離を生じさせる親バーテックスのバーテックス識別子とを記録するように示される。親バーテックスは所定のパスに沿う次の(隣の又は1つ前の)バーテックスであり、この場合、所定のパスは最小パス距離に対応するパスである。最小パス距離に関してゼロ(0)の値は、ソースバーテックスSを示す。最小パス距離に関してINFの値は、未定値(undefined  value)を示す。バーテックスIDに関して-1の値は、バーテックスIDに関して値が無いこと(no  value)を示す。従って、ソースバーテックスSは、各スーパーステップに関し、分散グラフ処理300を通じて(0，-1)というパス情報値を有する。各々のSDNコントローラ108に関するバーテックスは、共にグループ化され、各SDNコントローラ108により保存されるパス情報を示す。
【００３１】
更に、分散グラフ処理300において、各スーパーステップが実行された後に、コントローラメッセージが送信される。コントローラメッセージは、異なるドメイン内の送信側バーテックス及びターゲット側バーテックスに関して送信されるドメイン間メッセージである。各々のコントローラメッセージは、送信バーテックス識別子；ターゲットバーテックス識別子；及びソースバーテックスSからターゲットバーテックスまでの最小距離を含んでよい。コントローラメッセージは、説明の簡明化のため図2では示されていないが、SS01-SS09に関して後述される。
【００３２】
図3では、分散グラフ処理は初期化としてSS01とともに始まり、ソースバーテックスSを除く全てのバーテックスが、(INF,-1)というパス情報又は単なる値を有し、(0,-1)という値を有するソースインデックスSを指定するネットワークリクエストが受信されていることを意味する。SS01の後、コントローラメッセージはドメイン110-Aの中以外では送信されず、ソースバーテックスSは自身の隣接バーテックスA2及びA3を発見し、それに応じてそれらの値を(4,S)及び(1,S)に更新する(更新は、図3において背景に影を付すことにより示されている)。SS02の後、コントローラメッセージ(A2,B2,5)がSDNコントローラ108-AからSDNコントローラ108-Bへ送信され、バーテックスB2はバーテックスA2を介するとソースバーテックスSから距離5であることを通知する。SS03において、ドメイン108-Aの中で、バーテックスA3は、隣接バーテックスA1は距離1だけ離れていることをSDNコントローラ108-Aに報告し、それに応じてSDNコントローラ108-AはバーテックスA1の値を(2,A3)に更新する。そして、バーテックスB1及びD1はバーテックスA1に隣接していることが判断される。SS03の後、コントローラメッセージ(A1,B1,3)、(A1,D1,4)及び(B2,A2,6)が上述の対応する方法で送信される。メッセージ(B2,A2,6)はバーテックスA2の経路情報の変化をもたらさず、その理由は、バーテックスA2はより少ない距離値を既に保存しているからである。SS04において、SDNコントローラ108-Bは、バーテックスB1の値を(3,A1)に更新し、バーテックスB4の値を(6,B2)に更新する一方、SDNコントローラ108-DはバーテックスD1の値を(4,A1)に更新する。SS04の後、コントローラメッセージ(B1,A1,4)及び(D1,A1,6)が送信され、これらはバーテックスA1のパス情報を変更しない。SS05において、SDNコントローラ108-Bは、バーテックスB3の値を(4,B1)に更新し、バーテックスB5の値を(9,B4)に更新し、バーテックスB7の値を(7,B4)に更新する一方、SDNコントローラ108-DはバーテックスD2の値を(5,D1)に更新する。SS05の後、コントローラメッセージ(B7,C2,8)が送信される。SS06において、SDNコントローラ108-BはバーテックスB5の値を(5,B3)に更新し及びバーテックスB6の値を(10,B5)に更新し、SDNコントローラ108-DはバーテックスD3の値を(6,D2)に更新し、SDNコントローラ108-CはバーテックスC2の値を(8,B7)に更新する。SS06の後、コントローラメッセージ(D3,C1,9)が、コントローラメッセージ(C2,B7,9)及び(B6,C1,7)とともに送信され、後者の2つは無視又は破棄される。SS07において、SDNコントローラ108-BはバーテックスB6の値を(6,B5)に更新し、SDNコントローラ108-CはバーテックスC5の値を(9,D3)に更新し及び宛先バーテックDの値を(9,C2)に更新する。SS07の後、コントローラメッセージ(B6,C1,7)が、コントローラメッセージ(C1,D3,12)及び(C1,B6,10)とともに送信され、後者の2つは無視又は破棄される。SS08において、SDNコントローラ108-CはバーテックスC1の値を(7,B6)に更新し及びバーテックスC3の値を(10,C1)に更新する。SS08の後、コントローラメッセージ(C1,B6,8)及び(C1,D3,10)が送信され、それらは無視又は破棄される。
そして、SS09において、分散グラフ処理300は収束し、更なる更新はされず、各SDNコントローラに保存されるパス情報値が「ホット(hot)」であること及び分散ネットワークドメイン200の実際のネットワークトポロジを表現していることを示すコントローラメッセージが送信される。
【００３３】
様々な形態において、異なる数のスーパーステップが分散グラフ処理300の収束をもたらしてよいことに留意を要する。分散グラフ処理300は分散ネットワークドメイン200に関して示されているが、上記の手順は、極めて多数のバーテックスを有する極めて多数のネットワークドメインを含むネットワークドメインの任意の集まりに適用されてよい。ソースバーテックスSから発しているが、類似する又は同等な結果を達成するために、分散グラフ処理300は、宛先ターゲットDから始まって逆順に実行されてよいことに留意を要する。更に、一実施例では、各々のSDNコントローラ108が、度面110のエッジにある境界バーテックスのみに関するコントローラメッセージを送信し、ドメイン110の内部トポロジが分散グラフ処理300の間に露呈しないようにしてもよい。
【００３４】
一実施例では、分散グラフ処理300が収束した後に、SDNコントローラ108-B、108-C、108-Dは各自のパス情報を全てSDNコントローラ108-Aに返送し、最短経路の演算を可能にしてもよい。例えば、SS09に基づいて、宛先バーテックスDの値(9,C2)は親バーテックスがC2であることを示し、バーテックスC2の値(8,B7)は親バーテックスがB7であることを示し、バーテックスB7の値(7,B4)は親バーテックスがB4であることを示し、バーテックスB4の値(6,B2)は親バーテックスがB2であることを示し、バーテックスB2の値(5,A2)は親バーテックスがA2であることを示し、バーテックスA2の値(4,S)はソースバーテックスに到達したことを示す。他の実施例では、パス情報は、宛先バーテックスDが属するSDNコントローラ108-Dにより収集及び処理されてもよい。そして、SDNコントローラ108-Aにおいて、算出された最小距離のパスがネットワークリクエストに応じて出力される。
【００３５】
図4Aを参照すると、本願で説明されるような分散グラフ処理を利用するネットワークサービス処理システムを実現する方法例400のうちの選択された要素がフローチャートで示されている。様々な形態において、分散グラフ処理300(図3参照)を実現するように、方法400は、複数のネットワークコントローラでそれぞれ実行されるネットワークサービス処理エンジン530(図5参照)を利用して実現される。方法400に示される所定の動作は望まれるならば並べ替えられてもよいし或いは省略されてもよいことに留意を要する。
【００３６】
方法400は、ステップ402において、ソースバーテックスを含む第1ネットワークドメインに対するネットワークリクエストを第1SDNコントローラが受信することによって始まり、ネットワークリクエストは、第2SDNコントローラにより管理される第2ネットワークドメインにおける宛先バーテックス及びソースバーテックスを指定する。ステップ404において、分散グラフ処理が、第1及び第2SDNコントローラを含む複数のSDNコントローラの各々で実行され、分散グラフ処理は、コントローラメッセージに基づいて各バーテックスのパス情報を記録することを含む。ステップ406において、ソースバーテックスと宛先バーテックスとの間の最小パス距離に対応するパス情報が集められる。ステップ408において、収集されたパス情報に基づいて、ソースバーテックスと宛先バーテックスとの間を最小距離で結ぶ出力パスが算出される。
【００３７】
図4Bを参照すると、本願で説明されるような分散グラフ処理を利用するネットワークサービス処理システムを実現する方法例404のうちの選択された要素がフローチャートで示されている。方法404は方法400(図4A参照)における動作404の少なくとも一部を表現する。様々な形態において、分散グラフ処理300(図3参照)を実現するように、方法404は、複数のネットワークコントローラでそれぞれ実行されるネットワークサービス処理エンジン530(図5参照)を利用して実現される。方法404に示される所定の動作は望まれるならば並べ替えられてもよいし或いは省略されてもよいことに留意を要する。
【００３８】
方法404は、ステップ402の後に、各々のネットワークドメインの中で、ステップ420において、ネットワークドメインのうちの各バーテックスとソースバーテックスとの間の最小パス距離を識別することによって始まる。ステップ422において、コントローラメッセージがSDNコントローラの間で送信され、その場合において、各々のコントローラメッセージは、送信しているバーテックスの識別子と、ターゲットのバーテックスの識別子と、ソースバーテックスからターゲットバーテックス識別子に対応するターゲットバーテックスまでの最小パス距離とを指定する。ステップ424において、各バーテックスの各SDNコントローラにより、パス情報は記録され、パス情報は、ソースバーテックスからそのバーテックスまでの最小パス距離と、ソースバーテックスまでの最小パス距離をもたらすバーテックスのうちの親バーテックスの親バーテックス識別子とを含む。ステップ424の後に、ステップ426において、何らかのコントローラメッセージが受信されているか否かの判断が為される。ステップ426の結果がYESであり、追加的なコントローラメッセージが受信されている場合、方法404はステップ420にループバックする。ステップ426の結果がNOである場合、方法404は終了し、方法400のステップ406に進む。
【００３９】
図5を参照すると、一形態のネットワークコントローラ500のうちの選択された要素についてのブロック図が示されている。図5においては、ネットワークコントローラ500が、本願で説明されるように、分散グラフ処理を利用するネットワークサービス処理システムを実現する物理的及び論理的なコンポーネントを含むコンピュータシステムとして表現されており、それに応じて、プロセッサ501、メモリ510及びネットワークインターフェース520を含む。プロセッサ501は、プログラム命令の実行、データの解釈、及び、メモリ510又は管理システム500により保存されるデータの処理を行ってよい。様々な形態において、ネットワークコントローラ500はSDNコントローラであってもよい。
【００４０】
図5において、メモリ510は、プロセッサ501に通信可能に結合され、及び、或る期間にわたってプログラム命令及びデータを維持するために適切なシステム、デバイス又は装置(例えば、コンピュータ読み取り可能な媒体)を有する。メモリ510は、様々なタイプのコンポーネント及びデバイスを含み、例えば、ランダムアクセスメモリ(RAM)、電気的に消去可能なプログラム可能なリードオンリメモリ(EEPROM)、PCMCIAカード、フラッシュメモリ、ソリッドステートディスク、ハードディスクドライブ、磁気テープライブラリ、光ディスクドライブ、磁気光ディスクドライブ、コンパクトディスクドライブ、コンパクトディスクアレイ、ディスクアレイコントローラ、及び、揮発性又は不揮発性メモリの適切な任意の選択又はアレイ等を含んでよい。不揮発性メモリは、電源が遮断された後でもデータを維持するメモリを指す。メモリ510は様々な形態において様々な数の物理ストレージデバイスを含んでよいことに留意を要する。
【００４１】
図5に示されるように、メモリ510はネットワークサービス処理エンジン(NSCE)530を含み、NSCE530は、ネットワークコントローラ500の他のインスタンスとの協働の下で、本願で説明される機能のうち、図4の方法400及び404を実行すること等のような分散グラフ処理を利用して、分散グラフ処理を利用するネットワークサービス処理システムを実現する。
【００４２】
本願で開示されるように、ネットワークサービス処理システムを実現するための方法及びシステムは、複数のネットワークドメインに対応する複数のネットワークコントローラにおいて分散グラフ処理を利用する。各々のネットワークコントローラは、各自のネットワークドメインのネットワークグラフを管理及び維持する。各ネットワークコントローラは、各自のネットワークドメイン内のノード(又はバーテックス)と通信する一方、ネットワークコントローラ同士はパスの発見及び演算のために互いに通信する。
【００４３】
本明細書の対象は1つ以上の実施例に関連して説明されているが、説明される特定の形態に、何れの請求項も限定するようには意図されていない。むしろ、本開示で意図される何れかの請求項は、本願の精神及び範囲に包含される代替例、修正例及び均等物をカバーするように意図されている。
【００４４】
以上の実施の形態に関し、更に以下の付記を開示する。
（付記1）
ソースバーテックス及び宛先バーテックスを指定するネットワークリクエストを第1ネットワークコントローラで受信する工程であって、前記ソースバーテックスは前記第1ネットワークコントローラにより管理される第1ネットワークドメインに位置し、前記宛先バーテックスは前記第2ネットワークコントローラにより管理される第2ネットワークドメインに位置する、工程；及び
複数のネットワークドメインに対応する、前記第1ネットワークコントローラ及び前記第2ネットワークコントローラを含む複数のネットワークコントローラにおいて、分散グラフ処理を実行し、前記ソースバーテックス及び前記宛先バーテックスの間のネットワークパスを決定する工程；
を含む方法であって、前記分散グラフ処理は：
各々のネットワークドメインの中で、ネットワークドメインにおける各バーテックスと前記ソースバーテックスとの間の最小パス距離を識別する工程；
前記複数のネットワークコントローラの間でコントローラメッセージを送信する工程であって、前記コントローラメッセージの各々は、送信バーテックス識別子と、ターゲットバーテックス識別子と、前記ソースバーテックスから前記ターゲットバーテックス識別子に対応するターゲットバーテックスまでの最小パス距離とを指定し、前記送信バーテックス識別子に対応する送信バーテックスは、前記コントローラメッセージを送信するネットワークコントローラのネットワークドメインに含まれ、前記ターゲットバーテックスは前記コントローラメッセージを受信するネットワークコントローラのネットワークドメインに含まれる、工程；及び
前記ネットワークコントローラに対応する前記ネットワークドメイン内の各バーテックスについて、各ネットワークコントローラがパス情報を記録する工程であって、前記パス情報は、前記ソースバーテックスからバーテックスまでの最小パス距離と、前記ソースバーテックスまでの最小パス距離をもたらすバーテックスのうちの親バーテックスの親バーテックス識別子とを含む、工程；
を有する方法。
（付記2）
前記分散グラフ処理は、前記第1ネットワークドメインにおける前記第1ネットワークコントローラにより始まる、付記1に記載の方法。
（付記3）
前記分散グラフ処理は、前記第2ネットワークドメインにおける前記第2ネットワークコントローラにより始まる、付記1に記載の方法。
（付記4）
前記コントローラメッセージを送信することは、前記ソースバーテックスと前記宛先バーテックスとの間の全てのネットワークパスが記録されるまで、前記コントローラメッセージの送信を反復することを含み、前記パス情報は、前記複数のネットワークドメインの間の所与のネットワークトポロジによっては変動しない、付記1に記載の方法。
（付記5）
前記最小パス距離に対応する前記パス情報を収集する工程；及び
収集された前記パス情報に基づいて、前記ソースバーテックスと前記宛先バーテックスとの間を最小距離で結ぶ出力パスを算出する工程；
を更に有する付記1に記載の方法。
（付記6）
前記パス情報を収集することが、各ネットワークドメインの境界バーテックスのみに関するパス情報を収集することを更に含む、付記5に記載の方法。
（付記7）
前記パス情報を収集することは、前記第1ネットワークコントローラ及び前記第2ネットワークコントローラのうちの何れかによって実行され、
当該方法は、前記第1ネットワークコントローラが、前記出力パスとともに前記ネットワークリクエストに応答する工程を更に有する付記5に記載の方法。
（付記8）
前記複数のネットワークコントローラは、ソフトウェア構築ネットワークコントローラである、付記1に記載の方法。
（付記9）
バーテックスに関して前記パス情報が記録された後に、前記バーテックスについて新たなパス情報を受信する工程；及び
前記新たなパス情報が、前記パス情報に記録されている最小パス距離より大きな最小パス距離の新たな値を示す場合、前記新たなパス情報を破棄する工程；
を更に有する付記1に記載の方法。
（付記10）
第1ネットワークコントローラ及び第2ネットワークコントローラを含む複数のネットワークドメインの各々に関連する複数のネットワークコントローラを有するネットワークシステムであって、前記複数のネットワークコントローラの各々は：
メモリ；
前記メモリに結合されたプロセッサ；及び
前記メモリに保存されたプロセッサ実行可能な命令；
を有し、前記複数のネットワークコントローラは、
ソースバーテックス及び宛先バーテックスを指定するネットワークリクエストを第1ネットワークコントローラで受信する工程であって、前記ソースバーテックスは前記第1ネットワークコントローラにより管理される第1ネットワークドメインに位置し、前記宛先バーテックスは前記第2ネットワークコントローラにより管理される第2ネットワークドメインに位置する、工程；及び
複数のネットワークコントローラにおいて、分散グラフ処理を実行し、前記ソースバーテックス及び前記宛先バーテックスの間のネットワークパスを決定する工程；
を行うための命令を実行するように動作することが可能であり、前記分散グラフ処理は：
各々のネットワークドメインの中で、ネットワークドメインにおける各バーテックスと前記ソースバーテックスとの間の最小パス距離を識別する工程；
前記複数のネットワークコントローラの間でコントローラメッセージを送信する工程であって、前記コントローラメッセージの各々は、送信バーテックス識別子と、ターゲットバーテックス識別子と、前記ソースバーテックスから前記ターゲットバーテックス識別子に対応するターゲットバーテックスまでの最小パス距離とを指定し、前記送信バーテックス識別子に対応する送信バーテックスは、前記コントローラメッセージを送信するネットワークコントローラのネットワークドメインに含まれ、前記ターゲットバーテックスは前記コントローラメッセージを受信するネットワークコントローラのネットワークドメインに含まれる、工程；及び
前記ネットワークコントローラに対応する前記ネットワークドメイン内の各バーテックスについて、各ネットワークコントローラがパス情報を記録する工程であって、前記パス情報は、前記ソースバーテックスからバーテックスまでの最小パス距離と、前記ソースバーテックスまでの最小パス距離をもたらすバーテックスのうちの親バーテックスの親バーテックス識別子とを含む、工程；
を含むことを特徴とするネットワークシステム。
（付記11）
前記分散グラフ処理は、前記第1ネットワークドメインにおける前記第1ネットワークコントローラにより始まる、付記10に記載のネットワークシステム。
（付記12）
前記分散グラフ処理は、前記第2ネットワークドメインにおける前記第2ネットワークコントローラにより始まる、付記10に記載のネットワークシステム。
（付記13）
前記コントローラメッセージを送信するための命令は、前記ソースバーテックスと前記宛先バーテックスとの間の全てのネットワークパスが記録されるまで、前記コントローラメッセージの送信を反復するための命令を含み、前記パス情報は、前記複数のネットワークドメインの間の所与のネットワークトポロジによっては変動しない、付記10に記載のネットワークシステム。
（付記14）
前記最小パス距離に対応する前記パス情報を収集する工程；及び
収集された前記パス情報に基づいて、前記ソースバーテックスと前記宛先バーテックスとの間を最小距離で結ぶ出力パスを算出する工程；
を行うための命令を更に有する付記10に記載のネットワークシステム。
（付記15）
前記パス情報を収集するための命令が、各ネットワークドメインの境界バーテックスのみに関するパス情報を収集するための命令を更に含む、付記14に記載のネットワークシステム。
（付記16）
前記パス情報を収集するための命令は、前記第1ネットワークコントローラ及び前記第2ネットワークコントローラのうちの何れかによって実行され、
前記命令は、前記第1ネットワークコントローラが、前記出力パスとともに前記ネットワークリクエストに応答する工程を行うための命令を更に有する付記14に記載のネットワークシステム。
（付記17）
前記複数のネットワークコントローラは、ソフトウェア構築ネットワークコントローラである、付記10に記載のネットワークシステム。
（付記18）
バーテックスに関して前記パス情報が記録された後に、前記バーテックスについて新たなパス情報を受信する工程；及び
前記新たなパス情報が、前記パス情報に記録されている最小パス距離より大きな最小パス距離の新たな値を示す場合、前記新たなパス情報を破棄する工程；
を行うための命令を更に有する付記10に記載のネットワークシステム。
【図１】
2017076971.tif 000003
【図２】
2017076971.tif 000004
【図３】
2017076971.tif 000005
【図４Ａ】
2017076971.tif 000006
【図４Ｂ】
2017076971.tif 000007
【図５】
2017076971.tif 000008