図面 (/)

技術 物理経路割当装置、物理経路割当方法、及びプログラム

出願人 日本電信電話株式会社
発明者 本多泰理土屋利明松村龍太郎塩本公平
出願日 2015年6月22日 (6年0ヶ月経過) 出願番号 2015-124414
公開日 2017年1月12日 (4年6ヶ月経過) 公開番号 2017-011465
状態 特許登録済
技術分野 広域データ交換
主要キーワード 性能評価指標 経路割当 ナップザック エッジ集合 収容状況 双対問題 ナップザック問題 仮想ノード間
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2017年1月12日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (10)

課題

物理ネットワークに対してより効率的に多くの仮想ネットワークを収容可能とすること。

解決手段

物理経路割当装置は、サービスに利用される仮想ネットワークに対する、物理ネットワーク上の物理経路の割当要求に応じ、当該仮想ネットワークのトラヒック量と、当該物理ネットワークにおける他の仮想ネットワークの収容状況とに基づいて、当仮想ネットワークに対する物理経路の割り当ての可否を判定する判定部と、前記物理経路の割り当てが可能であると判定された場合に、数理計画問題を計算して、前記割当要求に係る仮想ネットワークに対する物理経路を選出する第1の選出部とを有し、前記判定部は、前記仮想ネットワークのトラヒック量が第1の所定値以下である場合には、当該トラヒック量が前記第1の所定値を超える場合には課せられない制約を課して、前記物理経路の割り当ての可否を判定する。

概要

背景

仮想化技術進展に伴い、ストレージサーバのみならず、ネットワークにおいてUプレーンとCプレーンとを分離するネットワーク仮想化技術が進展している。当該技術を用いた世界においては、従来の様なネットワークサービス設備との固定的な関係は解消し、より柔軟なつながりが実現されていく。すなわち、ネットワークを運営するネットワーク事業者が提供する物理的なネットワーク(以下「物理ネットワーク」という)上でサービス展開する各事業者は、それぞれ独立なタイミング及び順番で当該サービスの提供を開始し、また、一般には、所定時間経過後にサービスを終了する。

物理ネットワークを運用管理するネットワーク事業者は、上記の様に一般には独立な到着時刻順で提供の開始を所望する各サービスに対し、当該物理ネットワークのリソースネットワーク帯域)を割り当て、仮想的なネットワークとして構成することで、ネットワーク上の各サービスを実現していく。従って、可能な限り多くのサービスを物理ネットワーク上に収容し、実現することが、ネットワーク事業者としても、サービス事業者としても望ましい。そのためには、高効率で各サービスへの物理リソースの割り当てを行い、サービスを実現することが肝要である。また、ネットワーク事業者としては、仮想ネットワークの構成に要するオペレーションの量、すなわち、リソースの再配置実行頻度を抑制することも重要である。

したがって、このようなネットワーク仮想化技術を用いたネットワークサービスの提供形態において、提供の開始を所望する各サービスに対して物理ネットワークのリソースの割り当てを適切に実現することで、高効率で多くのサービスを収容することが求められている。

上記サービスへの物理リソースの割り当ては、Virtual Network Embedding(以下「VNE」という。)と呼ばれる問題として定式化され、近年多くの研究が報告されている。これは、所与の物理ネットワーク及び時系列到着するサービスを重み付き無向グラフとしてモデル化し、各サービスに対して、物理ネットワークのリソースを割り当てていく問題である。一般には、ノードリンクとも物理的配置箇所は自由であり、多くの場合、受付成功率要求トラヒック量の総和(受付ネットワークの価値の総和)を目的関数とする数理計画問題として定式化される。

非特許文献1においては、時系列で到着する仮想ネットワークに対して、ネットワークの各指標案することで、ノードへの物理リソース(CPU処理能力)及びネットワーク設備量を最適化することが検討されている。また、非特許文献2では、ノードの配置場所に若干の制約を設けた場合の問題が考察されている。

非特許文献3では、オンライン仮想経路を割り当てていく問題において、各サービス要求に異なる要求トラヒック量の総和が付与されている場合において、要求トラヒック量の総和を最大化するために必要に応じて受け付け拒否する方式が提案されている。当該問題では、線型計画問題の0−1整数計画問題においてその双対問題を考えることで、目的関数である要求トラヒック量の総和の累積値の向上を実現している。

この他、組み合わせ問題としてよく知られるナップザック問題オンライン版として、時系列で到着する荷物をオンラインでナップザックに収容し、適切に収容の是非を判定することで、所定時間経過後におけるナップザック内の荷物の価値を最大化する問題も、オンラインナップザック問題として、近年、最適化アルゴリズムの研究が進められている(非特許文献4)。

概要

物理ネットワークに対してより効率的に多くの仮想ネットワークを収容可能とすること。物理経路割当装置は、サービスに利用される仮想ネットワークに対する、物理ネットワーク上の物理経路の割当要求に応じ、当該仮想ネットワークのトラヒック量と、当該物理ネットワークにおける他の仮想ネットワークの収容状況とに基づいて、当仮想ネットワークに対する物理経路の割り当ての可否を判定する判定部と、前記物理経路の割り当てが可能であると判定された場合に、数理計画問題を計算して、前記割当要求に係る仮想ネットワークに対する物理経路を選出する第1の選出部とを有し、前記判定部は、前記仮想ネットワークのトラヒック量が第1の所定値以下である場合には、当該トラヒック量が前記第1の所定値を超える場合には課せられない制約を課して、前記物理経路の割り当ての可否を判定する。

目的

本発明は、上記の点に鑑みてなされたものであって、物理ネットワークに対してより効率的に多くの仮想ネットワークを収容可能とすることを目的とする

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

サービスに利用される仮想ネットワークに対する、物理ネットワーク上の物理経路割当要求に応じ、当該仮想ネットワークのトラヒック量と、当該物理ネットワークにおける他の仮想ネットワークの収容状況とに基づいて、当仮想ネットワークに対する物理経路の割り当ての可否を判定する判定部と、前記物理経路の割り当てが可能であると判定された場合に、数理計画問題を計算して、前記割当要求に係る仮想ネットワークに対する物理経路を選出する第1の選出部とを有し、前記判定部は、前記仮想ネットワークのトラヒック量が第1の所定値以下である場合には、当該トラヒック量が前記第1の所定値を超える場合には課せられない制約を課して、前記物理経路の割り当ての可否を判定する、ことを特徴とする物理経路割当装置

請求項2

前記判定部は、前記物理ネットワークを構成する各リンク残余帯域を重みとする無向グラフにおいて、前記割当要求に係る仮想ネットワークのトラヒック量に基づいて、当該仮想ネットワークに対する物理経路について、1以上の候補を抽出し、前記第1の選出部は、前記無向グラフについて、局所辺連結度になるノード対の数を目的関数に設定し、前記目的関数に基づいて、前記1以上の候補の中から1つの物理経路を選出する、ことを特徴とする請求項1記載の物理経路割当装置。

請求項3

前記判定部は、前記割当要求に係る仮想ネットワークのトラヒック量が前記第1の所定値以下である場合には、局所辺連結度が零になるノード対の数を第2の所定値以下にするという制約を課して、前記物理経路の割り当ての可否を判定する、ことを特徴とする請求項2記載の物理経路割当装置。

請求項4

前記判定部は、更に、過去の仮想ネットワークの平均滞在時間と、前記過去の仮想ネットワークのトラヒック量とが所定の条件を満たす場合に、前記制約を課して、前記物理経路の割り当ての可否を判定する、ことを特徴とする請求項3記載の物理経路割当装置。

請求項5

前記判定部によって、前記物理経路の割り当てが不可能であると判定された場合に、前記物理ネットワークに収容されている他の仮想ネットワークの中から任意の仮想ネットワークを取り出し、取り出された仮想ネットワークと、前記割当要求に係る仮想ネットワークとに基づいて新たな仮想ネットワークを生成し、当該新たな仮想ネットワークについて、数理計画問題を計算して物理経路を選出する第2の選出部、を有することを特徴とする請求項1乃至4いずれか一項記載の物理経路割当装置。

請求項6

コンピュータが、サービスに利用される仮想ネットワークに対する、物理ネットワーク上の物理経路の割当要求に応じ、当該仮想ネットワークのトラヒック量と、当該物理ネットワークにおける他の仮想ネットワークの収容状況とに基づいて、当仮想ネットワークに対する物理経路の割り当ての可否を判定する判定手順と、前記物理経路の割り当てが可能であると判定された場合に、数理計画問題を計算して、前記割当要求に係る仮想ネットワークに対する物理経路を選出する選出手順とを実行し、前記判定手順は、前記仮想ネットワークのトラヒック量が第1の所定値以下である場合には、当該トラヒック量が前記第1の所定値を超える場合には課せられない制約を課して、前記物理経路の割り当ての可否を判定する、ことを特徴とする物理経路割当方法

請求項7

コンピュータに、サービスに利用される仮想ネットワークに対する、物理ネットワーク上の物理経路の割当要求に応じ、当該仮想ネットワークのトラヒック量と、当該物理ネットワークにおける他の仮想ネットワークの収容状況とに基づいて、当仮想ネットワークに対する物理経路の割り当ての可否を判定する判定手順と、前記物理経路の割り当てが可能であると判定された場合に、数理計画問題を計算して、前記割当要求に係る仮想ネットワークに対する物理経路を選出する選出手順とを実行させ、前記判定手順は、前記仮想ネットワークのトラヒック量が第1の所定値以下である場合には、当該トラヒック量が前記第1の所定値を超える場合には課せられない制約を課して、前記物理経路の割り当ての可否を判定する、ことを特徴とするプログラム

技術分野

0001

本発明は、物理経路割当装置、物理経路割当方法、及びプログラムに関する。

背景技術

0002

仮想化技術進展に伴い、ストレージサーバのみならず、ネットワークにおいてUプレーンとCプレーンとを分離するネットワーク仮想化技術が進展している。当該技術を用いた世界においては、従来の様なネットワークサービス設備との固定的な関係は解消し、より柔軟なつながりが実現されていく。すなわち、ネットワークを運営するネットワーク事業者が提供する物理的なネットワーク(以下「物理ネットワーク」という)上でサービス展開する各事業者は、それぞれ独立なタイミング及び順番で当該サービスの提供を開始し、また、一般には、所定時間経過後にサービスを終了する。

0003

物理ネットワークを運用管理するネットワーク事業者は、上記の様に一般には独立な到着時刻順で提供の開始を所望する各サービスに対し、当該物理ネットワークのリソースネットワーク帯域)を割り当て、仮想的なネットワークとして構成することで、ネットワーク上の各サービスを実現していく。従って、可能な限り多くのサービスを物理ネットワーク上に収容し、実現することが、ネットワーク事業者としても、サービス事業者としても望ましい。そのためには、高効率で各サービスへの物理リソースの割り当てを行い、サービスを実現することが肝要である。また、ネットワーク事業者としては、仮想ネットワークの構成に要するオペレーションの量、すなわち、リソースの再配置実行頻度を抑制することも重要である。

0004

したがって、このようなネットワーク仮想化技術を用いたネットワークサービスの提供形態において、提供の開始を所望する各サービスに対して物理ネットワークのリソースの割り当てを適切に実現することで、高効率で多くのサービスを収容することが求められている。

0005

上記サービスへの物理リソースの割り当ては、Virtual Network Embedding(以下「VNE」という。)と呼ばれる問題として定式化され、近年多くの研究が報告されている。これは、所与の物理ネットワーク及び時系列到着するサービスを重み付き無向グラフとしてモデル化し、各サービスに対して、物理ネットワークのリソースを割り当てていく問題である。一般には、ノードリンクとも物理的配置箇所は自由であり、多くの場合、受付成功率要求トラヒック量の総和(受付ネットワークの価値の総和)を目的関数とする数理計画問題として定式化される。

0006

非特許文献1においては、時系列で到着する仮想ネットワークに対して、ネットワークの各指標案することで、ノードへの物理リソース(CPU処理能力)及びネットワーク設備量を最適化することが検討されている。また、非特許文献2では、ノードの配置場所に若干の制約を設けた場合の問題が考察されている。

0007

非特許文献3では、オンライン仮想経路を割り当てていく問題において、各サービス要求に異なる要求トラヒック量の総和が付与されている場合において、要求トラヒック量の総和を最大化するために必要に応じて受け付け拒否する方式が提案されている。当該問題では、線型計画問題の0−1整数計画問題においてその双対問題を考えることで、目的関数である要求トラヒック量の総和の累積値の向上を実現している。

0008

この他、組み合わせ問題としてよく知られるナップザック問題オンライン版として、時系列で到着する荷物をオンラインでナップザックに収容し、適切に収容の是非を判定することで、所定時間経過後におけるナップザック内の荷物の価値を最大化する問題も、オンラインナップザック問題として、近年、最適化アルゴリズムの研究が進められている(非特許文献4)。

先行技術

0009

Johannes Infuhr, Gunther R. Raidl, "Introducing the Virtual Network MappingProblem with Delay, Routing and Location Constraints" Network Optimization Lecture Notes in Computer Science6701( 2011), 105-117.
Chowdhury, N.M.M.K. Cheriton, Rahman, M.R. ; Boutaba, R., "Virtual Network Embedding with Coordinated Node and Link Mapping,"Proc.INFOCOM2009.
G.Even, et. al., "Competitive and deterministic embeddings of virtual networks", Theory of Computer Science 496 (2013), 184--194.
D. Chakrabarty, et.al.., "Online Knapsack Problems", [online], [平成27年6月1日検索],インターネット(URL:http://research.microsoft.com/en-us/um/people/dechakr/pubs/czk-full.pdf)

発明が解決しようとする課題

0010

しかしながら、上記非特許文献に示される技術においては、目的関数として現在までの収容数のみを採用していることから、将来的な収容数を向上する問題としては定式化されていない。

0011

また非特許文献1、2等に示される従来技術においては、データセンタにおける適用を主な目的としており、ノードのリソース割り当てが中心であった。また、最適化される対象の性能指標としてオペレーションの実行回数などを勘案したものも報告されていない。また、従来のVNE検討においては、リンクの埋め込みは帯域を勘案せず、k-shortest path first方式により設備量を最小化するものが殆どであった。

0012

本発明は、上記の点に鑑みてなされたものであって、物理ネットワークに対してより効率的に多くの仮想ネットワークを収容可能とすることを目的とする。

課題を解決するための手段

0013

そこで上記課題を解決するため、物理経路割当装置は、サービスに利用される仮想ネットワークに対する、物理ネットワーク上の物理経路の割当要求に応じ、当該仮想ネットワークのトラヒック量と、当該物理ネットワークにおける他の仮想ネットワークの収容状況とに基づいて、当仮想ネットワークに対する物理経路の割り当ての可否を判定する判定部と、前記物理経路の割り当てが可能であると判定された場合に、数理計画問題を計算して、前記割当要求に係る仮想ネットワークに対する物理経路を選出する第1の選出部とを有し、前記判定部は、前記仮想ネットワークのトラヒック量が第1の所定値以下である場合には、当該トラヒック量が前記第1の所定値を超える場合には課せられない制約を課して、前記物理経路の割り当ての可否を判定する。

発明の効果

0014

物理ネットワークに対してより効率的に多くの仮想ネットワークを収容可能とすることができる。

図面の簡単な説明

0015

本発明の実施の形態におけるネットワークリソース割当装置のハードウェア構成例を示す図である。
本発明の実施の形態におけるネットワークリソース割当装置の機能構成例を示す図である。
本発明の実施の形態におけるネットワークリソース割当装置が実行する処理手順概要を説明するための図である。
サービス要求到着時の最適経路決定処理を説明するための図である。
再配置処理を説明するための図である。
シミュレーションに利用された物理ネットワークを示す無向グラフの構成例を示す図である。
定常状態における既存方式提案方式との比較結果を示す図である。
定常状態の時刻t=250における収容中の仮想ネットワークの要求トラヒック量の度数分布示す図である。
100サンプルのサービス要求パターンに関する既存方式と提案方式との比較結果を示す図である。

実施例

0016

以下、図面に基づいて本発明の実施の形態を説明する。本発明の実施の形態では、物理ネットワーク上での仮想ネットワークの展開を求める各種サービス(仮想ネットワークサービス)の要求がそれぞれ独立に到着し、ネットワーク事業者が、各サービスに対して物理ネットワークのリソース(物理的な経路。以下「物理経路」という。)を割り当てて、物理ネットワーク上でサービスを実現することを想定する。各サービスは所定時間経過後に終了し、割り当てられた物理経路を開放して退去する。また、通信事業者は、サービスの提供時間(サービスが提供されるタイミング)を知り得ないものとする。各サービスは仮想ネットワークとして物理ネットワーク上で展開されるが、仮想ネットワークは、1以上の仮想経路によって構成される。仮想ネットワークは、当該仮想ネットワークを構成する仮想経路ごとの仮想ノード対(送信元ノード、あて先ノード)、当該仮想経路ごとの仮想ノード対で仮想ノード間に流れるトラヒック量(要求トラヒック量)、並びに各仮想経路に共通の到着時刻及び退去時刻の組として定式化される。なお、各仮想経路は、仮想ネットワークに流れる各フローに対応する。

0017

あるサービス要求が到着した時に、物理ネットワークの帯域リソースが当該サービスに係る仮想ネットワークの収容に不足している場合には、既に収容されている仮想ネットワークの配置変更を行うことで、既存の仮想ネットワーク及び新たに到着したサービスに係る仮想ネットワークを収容可能であるかを模索する。以下、当該プロセスを「再配置」と呼ぶ。本実施の形態では、適切な性能評価指標を採用することで、当該指標の意味においてネットワークリソースの割り当てを最適に行うプロセスと、それを実現するためのアルゴリズムとを記載する。

0018

想定する物理リソース割当方式は、(i)サービス要求到着時の経路割当方式に関する部分と、(ii)再配置実行時の再配置実行方式に関する部分とに大別される。

0019

(i)の経路割当方式は、サービス要求到着時に、当該サービス要求の要求トラヒック量の総和(仮想経路ごとの要求トラヒック量の総和)が所定値以下の場合においては、物理経路選択のための制約を新規に課し、物理ネットワークにおいて、別途指定される所定のリンクの残余使用率が所定値以下の場合には、当該サービス要求を受付不可と判断するものである。

0020

(ii)の再配置実行方式は、到着したサービス要求の要求トラヒック量の総和に依存して、再配置における入れ替え経路数や実行回数の上限を課す方式である。

0021

図1は、本発明の実施の形態におけるネットワークリソース割当装置のハードウェア構成例を示す図である。図1のネットワークリソース割当装置10は、それぞれバスBで相互に接続されているドライブ装置100、補助記憶装置102、メモリ装置103、CPU104、及びインタフェース装置105等を有する。

0022

ネットワークリソース割当装置10での処理を実現するプログラムは、CD−ROM等の記録媒体101によって提供される。プログラムを記憶した記録媒体101がドライブ装置100にセットされると、プログラムが記録媒体101からドライブ装置100を介して補助記憶装置102にインストールされる。但し、プログラムのインストールは必ずしも記録媒体101より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置102は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。

0023

メモリ装置103は、プログラムの起動指示があった場合に、補助記憶装置102からプログラムを読み出して格納する。CPU104は、メモリ装置103に格納されたプログラムに従ってネットワークリソース割当装置10に係る機能を実行する。インタフェース装置105は、ネットワークに接続するためのインタフェースとして用いられる。

0024

図2は、本発明の実施の形態におけるネットワークリソース割当装置の機能構成例を示す図である。ネットワークリソース割当装置10は、例えば、以下の(1)〜(3)の性能評価指標のいずれか1以上、又はそれらの加重和を向上させるために、図2に示されるような機能構成を有する。
(1)時間無限大における受付成功率;
(2)時間無限大における、サービス要求あたり再配置実行回数;
(3)時間無限大における、サービス要求あたり要求トラヒック量の総和
但し、これらの性能評価指標を最大化又は最小化する問題は、一般にはNP困難な整数計画問題であり、実時間における確定的な理論解の算出は困難である。そこで、本実施の形態では、物理経路の選出過程において、所定のコスト関数を定め、それを最小化するヒューリスティックアプローチを採用することにより、実時間での実現を図る。

0025

図2において、ネットワークリソース割当装置10は、物理ネットワーク情報入力部11、サービス要求入力部12、受付可否判定部13、要求トラヒック量総和算出部14、最適経路決定部15、及び再配置実行部16を有する。これら各部は、ネットワークリソース割当装置10にインストールされる1以上のプログラムが、CPU104に実行させる処理により実現される。ネットワークリソース割当装置10は、また、選出経路対記憶部17を利用する。選出経路対記憶部17は、例えば、補助記憶装置102、又はネットワークリソース割当装置10にネットワークを介して接続可能な記憶装置等を用いて実現可能である。

0026

物理ネットワーク情報入力部11は、物理ネットワーク¥情報を入力する。物理ネットワーク情報は、物理ネットワークのトポロジや、物理ネットワークを構成する各リンクの帯域等を示す情報である。物理ネットワーク情報の入力は、予め行われる。サービス要求が到着するたびに、他の各部は、図3に示される手順で、各部の機能を実行する。

0027

図3は、本発明の実施の形態におけるネットワークリソース割当装置が実行する処理手順の概要を説明するための図である。

0028

サービス要求が到着すると、サービス要求入力部12は、当該サービス要求を入力する(ステップS1)。サービス要求は、仮想ネットワークを利用したサービスの提供要求であり、当該仮想ネットワークを構成する各仮想経路の仮想ノード対(送信元ノード、あて先ノード)、当該仮想経路ごとの仮想ノード対で仮想ノード間に流れるトラヒック量(要求トラヒック量)、並びに各仮想経路に共通の到着時刻及び退去時刻等を含む。なお、サービス要求は、仮想ネットワークに対する物理経路の割当要求であるともいえる。

0029

続いて、受付可否判定部13は、サービス要求入力部12によって入力されたサービス要求について、当該サービス要求に係る仮想ネットワークに対する物理経路の割り当ての可否及び再配置の要否を判定する(ステップS2)。なお、当該判定において、受付可否判定部13は、要求トラヒック量総和算出部14を利用して、サービス要求の要求トラヒック量の総和を算出し、当該算出結果と、物理ネットワークにおける他の仮想ネットワークの収容状況とに基づいて、物理経路の割り当ての可否及び再配置の要否を判定する。要求トラヒック量の総和は、通信事業者としてのメリットを定量的に表す指標としての意味を有する。

0030

受付可否判定部13によって、物理経路の割り当てが可能であり、かつ、再配置が不要であると判定された場合、最適経路対決定部5は、当該サービス要求に係る仮想ネットワークに最適な物理経路(最適経路)を選出する(ステップS3)。最適経路は、仮想ネットワークを構成する仮想経路ごとに選出される。

0031

一方、受付可否判定部13によって、物理経路の割り当てが不可能であり、再配置処理が必要であると判定された場合、再配置実行部16が、既に収容されている仮想ネットワークについて、再配置を実行する(ステップS4)。

0032

なお、選出経路対記憶部17は、選出経路対の情報を記憶する。選出経路対とは、仮想経路ごとに選出された最適経路の対(集合)を示す情報いう。

0033

続いて、以下の説明において用いられる記号の用法及び前提事項を、以下にまとめて説明する。

0034

続いて、図3のステップS2及びS3の詳細について説明する。

0035

番目のサービス要求が到着すると、受付可否判定部13は、k-shortest path firstアルゴリズムにより、物理ネットワーク情報が示す物理ネットワーク上において、サービス要求に係る仮想ネットワークVNj含まれる仮想経路ごとに、当該仮想経路の送信元ノード及びあて先ノード間について、k本の物理経路を抽出する。ここでkの値は、計算時間に対する要件のもとで可能な限り大きい値が望ましい。なお、抽出されたk本の物理経路を、以下「候補経路集合」という。

0036

続いて、受付可否判定部13は、仮想ネットワークVNjを構成する仮想経路ごとに、当該仮想経路に関して抽出された候補経路集合に含まれる各物理経路について、容量制約の確認を行う。具体的には、仮想経路ごとに、当該仮想経路に関して抽出された候補経路集合に含まれる各物理経路について、当該物理経路を構成する物理リンク最小残余帯域が、当該仮想経路の要求トラヒック量以上であることを確認する。受付可否判定部13は、或る仮想経路について、最小残余帯域が要求トラヒック量を下回る物理経路が有る場合、当該物理経路を、当該仮想経路の候補経路集合から除外する。

0037

容量制約の確認の結果、k本の物理経路の全ての割り当てが不可能である仮想経路が1以上有る場合、受付可否判定部13は、再配置が必要であると判定する。

0038

容量制約の確認においては再配置が必要でないと判定された場合、要求トラヒック量総和算出部14は、仮想ネットワークVNjの仮想経路ごとの要求トラヒック量の総和rjを、以下により計算する。

0039

rj≦ε1である場合、受付可否判定部13は、以下の条件付き制約を課して、物理経路の割り当ての可否を判定する。なお、ε1は、任意に設定可能なパラメータである。

0040

なお、数3のIF文が、「条件」付き「制約」における「条件」に該当し、IF文の条件が満たされた場合に実行される{}内が、「条件」付き「制約」における「制約」に該当する。また、IF文において、c2と比較されている値は、j番目のサービス要求の到着時刻において収容されている仮想ネットワークVNのトラヒック量の総和の上位α%の値である(数1の(15)参照)。また、c3と比較されている値は、j番目のサービス要求の到着時刻において退去し終わった仮想ネットワークVN(過去の仮想ネットワークVN)のうち、トラヒック量の総和がs以下である仮想ネットワークVNの平均滞在時間である(数1の(12)参照)。また、c4と比較されている値は、j番目のサービス要求の到着時刻において退去し終わった仮想ネットワークVNのうち、トラヒック量の総和がS以上である仮想ネットワークVNの平均滞在時間である(数1の(14)参照)。なお、c2、c3、c4、α、s、Sは、任意に設定可能なパラメータである。c2には、小さな値が設定されることが想定されている。c3には、大きな値が設定されることが想定されている。c4には、小さな値が設定されることが想定されている。したがって、IF文が示す条件は、「j番目のサービス要求の到着時において収容されている仮想ネットワークVNの多くは、要求トラヒック量の総和が比較的小さく、かつ、要求トラヒック量の総和が比較的小さい仮想ネットワークVNの滞在時間が長い傾向にある」ことを示す。

0041

また、当該条件が付与される制約(IF文の{}内)において、任意に設定可能なパラメータc5と比較される値は、j番目のサービス要求に係る仮想ネットワークVNjを収容した後の無向グラフの局所辺連結度になってしまうノード対の数である。ここで、局所辺連結度が零になってしまうノード対とは、当該ノード対の間の辺の残余帯域が零になってしまうノード対を意味する。また、c5には、小さい値が設定されることが想定されている。したがって、当該制約は、残余帯域が零になってしまうノード対の数がし所定値より少なくなること(c5以下になること)である。

0042

rj≦ε1である場合において、受付可否判定部13が、上記の条件付き制約を勘案した上で、各仮想経路について、当該仮想経路に対する候補経路集合に含まれる物理経路のうちのいずれの物理経路の割り当てが可能であると判定した場合には、最適経路決定部15は、各仮想経路について、当該仮想経路に対する候補経路集合から、以下に述べる数理計画問題を計算して、1つの最適経路を選出する。一方、rj>ε1である場合、上記の制約は勘案されずに、最適経路決定部15は、各仮想経路について、当該仮想経路に対する候補経路集合から、以下に述べる数理計画問題を計算して最適経路を選出する。ここで、数理計画問題の計算とは、例えば、以下の目的関数を解くことをいう。

0043

また、#は、#に続く()内の集合の要素数を意味する。そして、Ec(v1,v2;G(V,E,ue))は、ノード集合V、エッジ集合E、重みベクトルueの重み付き無向グラフにおける、ノードv1、v2間の局所辺連結度を示す(数1の(6)参照)。したがって、#に続く()内は、局所辺連結度が零になるノード対の集合を示す。すなわち、当該目的関数は、仮想ネットワークVNjに物理経路を割当てた場合において、接続性を失う(残余帯域が零になってしまう)ノード対の数量を最小化することを目的としている。

0044

このようにすることで、要求トラヒック量の総和が小さいにも係らず、主要なリンクを占有するサービス要求を排除し、より高効率に要求トラヒック量の総和が大きい仮想ネットワークの収容を可能にしていくことができる。なお、上記制約により、j番目のサービス要求に係る仮想ネットワークVNjに対する物理経路の割り当てが不可能である場合には、受付可否判定部13は、再配置が必要であると判定する。以上の判断フローは、サービス要求到着時に以下の様な最適化問題を解くことに相当する。

0045

なお、図4に、ステップS2及びS3の処理手順を詳細化した図を示す。

0046

なお、上記目的関数の他に、仮想ネットワークVNjの各仮想経路のホップ数の総和を最小化することを目的とする目的関数を解くことで、各仮想経路の最適経路が選出されてもよい。

0047

続いて、図3のステップS4の詳細について説明する。

0048

受付可否判定部13によって、再配置が必要であると判定されると、再配置実行部16は、所定のプロセスに基づき、既存の仮想ネットワークVNへの物理経路の割り当てを見直し、到着サービス要求に係る仮想ネットワークVNjと併せて収容の可否を模索する。

0049

仮想ネットワークVNjに係るサービス要求が、時刻tj(0)に到着したとし、その時点で収容されている仮想ネットワークVNの数を、N(tj(0))とする。この時、再配置実行部16は、収容されている仮想ネットワークVNの中からランダムに、

0050

個の仮想ネットワークVNを抽出し、メモリ上で一時的にリソース解放を行う。メモリ上でのリソース解放とは、実際に物理ネットワークから仮想ネットワークVNを退去させるわけではないことを意味する。ここで、M2は、任意に設定可能なパラメータである。また、「∧」は、「∧」の両側の値のうち小さいほうの値が選択されることを示す。したがって、時刻tj(0)において収容されている仮想ネットワークVNの数がM2以下であれば、時刻tj(0)において収容されている全ての仮想ネットワークVNが抽出され、時刻tj(0)において収容されている仮想ネットワークVNの数がM2を超える場合には、時刻tj(0)において収容されている仮想ネットワークVNの中から、M2個の仮想ネットワークVNが、ランダムに抽出される。

0051

続いて、再配置実行部16は、到着サービス要求に係る仮想ネットワークVNjと、一時的にリソース解放が行われた仮想ネットワークVNとを併せて、新たな仮想ネットワーク

0052

を生成する。これは、一時的にリソース解放が行われた各仮想ネットワークVNの仮想経路ごとの要求トラヒック量、送信元ノード及びあて先ノードと、仮想ネットワークVNjの各仮想経路の要求トラヒック量、送信元ノード及びあて先ノードとを合成又は統合することで、新たな仮想ネットワークが生成されることを示す。

0053

この時、一時的なリソース解放後の残余帯域を表すベクトルC'e(tj(0))は、

0054

と表すことができる。これを用いて、当該時点におけるグラフGは、

0055

と表せる。また以下では、

0056

ただし、

0057

とする。

0058

この時、再配置実行部16は、新たな仮想ネットワークを、以下のオフライン最適化問題を解くことにより、グラフG(V、E、C'e(tj(0))に埋め込むことを試みる

0059

新たな仮想ネットワークを埋め込めた場合(新たな仮想ネットワークの各仮想経路に物理経路を割り当てることができた場合)、当該各仮想経路の最適経路対は決定される。

0060

一方、新たな仮想ネットワークを埋め込めなかった場合、再配置実行部16は、収容されている仮想ネットワークVNの中からのランダムな仮想ネットワークVNの抽出以降を繰り返す。N∞回繰り返しても、新たな仮想ネットワークを埋め込めなかった場合、到着サービス要求は、受け付け不可であると判定される。

0061

なお、図5に、ステップS4の処理手順を詳細化した図を示す。

0062

次に、本実施の形態のネットワークリソース割当装置10に関する数値実験について述べる。ここでは、時間は無次元実数で表すこととする。数値実験による評価に際しては、サービス要求の到着パターンについて複数のパターンを用意し、同一の物理ネットワーク上でそれぞれのサービス要求に対する仮想ネットワークの収容の模様をシミュレーションした結果に基づき比較を行う。

0063

図6は、シミュレーションに利用された物理ネットワークを示す無向グラフの構成例を示す図である。図6に示される無向グラフは、ノードV1〜V15の15個のノードから構成される、接続率が0.1のランダムグラフの一標本である。接続率が0.1であるとは、各ノードからの接続確率が0.1であることをいう。

0064

サービス要求に係る仮想ネットワークは、それぞれM本の仮想経路から構成される。ただし、Mは確率変数で、
M=max{1、x}, x∈N(3、2)
である。max{1、x}は、1とxとのうちの大きい方が選択されることを示す。x∈N(3、2)は、xが、平均3、標準偏差2の正規分布に従うことを示す。

0065

また、サービス要求の到着パターンは、平均λ=1のPoisson到着、平均滞在時間μ=20の指数分布に従うとする。すなわち、各サービス要求は到着後、所定時間経過後に退去する。各仮想経路の送信元ノード及びあて先ノードは、いずれも物理ノードの集合Vからランダムに非復元抽出され、300個のサービス要求が到着するまでシミュレーションが実行される。

0066

比較するアルゴリズムは、最短経路方式(以下、「既存方式」という。)と本実施の形態における方式(以下、「提案方式」という。)とする。既存方式は、サービス要求到着時に、リンク容量の制約のもとに各仮想経路に対して割り当てられる物理経路の経路長の総和をコストとする方式である。提案方式では、前記各パラメータ値を以下の通り設定して評価を行う。

0067

ここで、パラメータM2の値は、時刻tj(0)において収容されている仮想ネットワークから2本の仮想ネットワークを抽出する場合の組み合わせの数を示す。

0068

図7は、定常状態における既存方式と提案方式との比較結果を示す図である。定常状態とは、シミュレーションが開始されてから、サービス要求の到着と、仮想ネットワークの退去とが安定している状態をいう。

0069

図7には、上述した3つの性能評価指標について、既存方式と提案方式との比較結果が示されている。なお、受付成功率は、便宜上、図7において、収容サービス数(収容できたサービス要求の数)に置き換えられている。受付成功率=収容サービス数/サービス要求の到着であり、サービス要求の到着数は、既存方式と提案方式とで共通である。したがって、収容サービス数の比較は、実質的に、受付成功率の比較に相当する。

0070

図7によれば、提案方式の方が、既存方式よりも累積要求トラヒック量の総和が大きく、かつ再配置実行回数が少量であることが分かる。

0071

また、図8は、定常状態の時刻t=250における収容中の仮想ネットワークの要求トラヒック量の度数分布示す図である。図8によれば、提案方式において、要求トラヒック量が高い仮想ネットワークが、既存方式に比べて高い割合で収容されていることが確認できる。

0072

同様の試験を、サービス要求パターンをランダムに100サンプル生成して実施した結果を図9に示す。図9より、統計的に見ても、再配置実施回数と要求トラヒック量との観点で、提案方式が既存方式よりも優れていることが確認できる。

0073

上述したように、本実施の形態によれば、ネットワーク仮想化の技術を生かして、より少量のオペレーション稼動で、より要求トラヒック量の総和大きいサービスを収容することができる。かつ、ネットワーク内を流れるトラヒック量(carried traffic)については、既存方式と同程度の量を実現することができる。すなわち、本実施の形態によれば、物理ネットワークに対してより効率的に多くの仮想ネットワークを収容可能とすることができる。

0074

なお、本実施の形態において、ネットワークリソース割当装置10は、物理経路割当装置の一例である。受付可否判定部13は、判定部の一例である。最適経路対決定部5は、第1の選出部の一例である。再配置実行部16は、第2の選出部の一例である。ε1は、第1の所定値の一例である。c5は、第2の所定値の一例である。

0075

以上、本発明の実施例について詳述したが、本発明は斯かる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。

0076

10ネットワークリソース割当装置
11物理ネットワーク情報入力部
12サービス要求入力部
13 受付可否判定部
14要求トラヒック量総和算出部
15最適経路決定部
16再配置実行部
17選出経路対記憶部
100ドライブ装置
101記録媒体
102補助記憶装置
103メモリ装置
104 CPU
105インタフェース装置
B バス

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • 日本電信電話株式会社の「 検知装置および検知プログラム」が 公開されました。( 2021/04/30)

    【課題・解決手段】正規化部(11)が、複数のWebサーバへのアクセスログのURIを、複数のURI間で類似する表記を統一して正規化済URIに変更する。算出部(12)が、送信元が同一のアクセスログのうち、... 詳細

  • 株式会社NTTドコモの「 転送制御システム、網側装置及び位置管理装置」が 公開されました。( 2021/04/30)

    【課題】移動体通信網においてパケットの移動距離を短くした上で確実にパケットを移動通信端末に届かせる転送制御システム、網側装置及び位置管理装置を提供する。【解決手段】転送制御システム1は、移動体通信網N... 詳細

  • 上田日本無線株式会社の「 中継装置および通信システム」が 公開されました。( 2021/04/30)

    【課題】本発明は、パケットの中継を制限するために実行される処理を単純化することを目的とする。【解決手段】無線端末20は中継装置18−1に接続要求パケットを送信する(S1)。通信状態が予め定められた条件... 詳細

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ