図面 (/)

技術 リソース割当計算装置、リソース割当計算方法、及びプログラム

出願人 日本電信電話株式会社
発明者 鈴木晃人高橋洋介辻野雅之石橋圭介塩本公平
出願日 2016年2月15日 (5年4ヶ月経過) 出願番号 2016-026397
公開日 2017年8月24日 (3年10ヶ月経過) 公開番号 2017-147517
状態 特許登録済
技術分野 広域データ交換
主要キーワード 要求時間帯 利用タイミング 設定コスト 許容時間帯 経路集合 数理計画問題 最適化モデル 許容帯域
関連する未来課題
重要な関連分野

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

図面 (8)

課題

一定の幅を許容するあいまいなトラヒック需要に対しても、最適なリソース割当を実現する割当計算装置、方法及びプログラムを提供する。

解決手段

ユーザ需要を満たすように、リソース割当を計算するリソース割当計算装置100において、割当要求リソースに対する許容範囲が指定されたユーザ需要を入力する入力手段101と、前記ユーザ需要に対して実際に割り当てる割当リソースを前記許容範囲内に収めるという制約条件の下、前記割当リソースと前記割当要求リソースとの間の差分が大きくなるほど大きくなるユーザ需要ペナルティを有するペナルティを最小にするように、数理最適化問題解くことにより前記割当リソースを計算する計算手段102と、前記計算手段により計算された前記割当リソースをユーザの端末通知する出力手段104とを備える。

概要

背景

通信事業者の提供するネットワーク接続サービスベストエフォート型ギャランティ型に大別される。ベストエフォート型サービスは、通信品質ネットワーク利用帯域の確保を行わないサービスである。通信リソースを複数のユーザで共用することで、低コストで実現できる。主にコンシューマ向けに低価格で提供される。

一方、専用線サービス等に代表されるギャランティ型サービスは、通信リソースを分離することで、通信品質やネットワーク利用帯域を確実に確保するサービスである。通信リソースを契約ユーザ専有させるため、高いコストがかかり、主に事業者向けに高価格で提供される。

しかし、インターネット上のサービスの多様化に伴い、ユーザがネットワークに求める要件も変化しつつある。例えば、利用タイミングに応じて、短期間だけギャランティ型サービスを安く利用したい、といったニーズが増加している。このようなサービスを本明細書では、オンデマンド・ギャランティ型サービスと呼ぶ。

オンデマンド・ギャランティ型サービスを低コストで実現するためには、ネットワークのリソース割当ダイナミックに変更する技術と最適なリソース割当を求めるためのネットワーク最適化技術が必要となる。

前者の技術に関しては、近年、SDN(Software-Defined Network)やNFV(Network Functions Virtualization)に代表されるネットワーク仮想化技術進展しており、当該技術を利用することで、ネットワークのリソース割当をダイナミックに変更することが可能となりつつある。後者の技術に関しては、ネットワーク最適化を実現するための数理計画問題がいくつか提案されている(非特許文献1〜3)。

ネットワーク最適化を実現するための数理計画問題の例として、多品種フロー問題による数理最適化モデルが挙げられる。この数理最適化モデルを解くことで、トラヒック需要に対して効率的にネットワークリソースを確保することができる。ここで、従来の数理最適化モデルにおけるトラヒック需要は所与確定的な入力パラメータとして扱われる。つまり、確保する帯域、確保する時間帯が明確に定まっており、指定されたトラヒック需要を完全に満たす解を導出する。ネットワークの混雑等で指定されたトラヒック需要が一部しか満たせない場合には、解を出力できない。すなわち、従来のネットワーク最適化技術では、事業者のリソースのみを制御最適化対象としており、ユーザのトラヒック需要を制御最適化対象としていない。

概要

一定の幅を許容するあいまいなトラヒック需要に対しても、最適なリソース割当を実現する割当計算装置、方法及びプログラムを提供する。ユーザ需要を満たすように、リソース割当を計算するリソース割当計算装置100において、割当要求リソースに対する許容範囲が指定されたユーザ需要を入力する入力手段101と、前記ユーザ需要に対して実際に割り当てる割当リソースを前記許容範囲内に収めるという制約条件の下、前記割当リソースと前記割当要求リソースとの間の差分が大きくなるほど大きくなるユーザ需要ペナルティを有するペナルティを最小にするように、数理最適化問題を解くことにより前記割当リソースを計算する計算手段102と、前記計算手段により計算された前記割当リソースをユーザの端末通知する出力手段104とを備える。

目的

本発明は上記の点に鑑みてなされたものであり、一定の幅を許容するあいまいなトラヒック需要に対しても、最適なリソース割当を実現することを可能とする技術を提供する

効果

実績

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

この技術が所属する分野

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

請求項1

ユーザ需要を満たすように、リソース割当を計算するリソース割当計算装置であって、割当要求リソースに対する許容範囲が指定されたユーザ需要を入力する入力手段と、前記ユーザ需要に対して実際に割り当てる割当リソースを前記許容範囲内に収めるという制約条件の下、前記割当リソースと前記割当要求リソースとの間の差分が大きくなるほど大きくなるユーザ需要ペナルティを有するペナルティを最小にするように、数理最適化問題解くことにより前記割当リソースを計算する計算手段と、前記計算手段により計算された前記割当リソースをユーザの端末通知する出力手段とを備えることを特徴とするリソース割当計算装置。

請求項2

前記リソース割当は通信ネットワークに対するリソース割当であり、前記ペナルティは、前記ユーザ需要ペナルティと、前記ユーザ需要の割り当てに起因して経路が変更されるトラヒック量が大きいほど大きくなる経路変更ペナルティとを有することを特徴とする請求項1に記載のリソース割当計算装置。

請求項3

前記リソース割当は通信ネットワークに対するリソース割当であり、前記ペナルティは、前記ユーザ需要ペナルティと、リンク混雑の程度が大きいほど大きくなるリンク混雑ペナルティとを有することを特徴とする請求項1に記載のリソース割当計算装置。

請求項4

記入力手段が、前記割当リソースの予約を前記端末から受け付けた場合に、前記出力手段は、前記割当リソースの情報を、前記通信ネットワークにおいて転送装置の設定を行う制御設定装置に出力することを特徴とする請求項2又は3に記載のリソース割当計算装置。

請求項5

前記割当要求リソースは、割当要求帯域又は割当要求時刻であることを特徴とする請求項1ないし4のうちいずれか1項に記載のリソース割当計算装置。

請求項6

ユーザ需要を満たすように、リソース割当を計算するリソース割当計算装置が実行するリソース割当計算方法であって、割当要求リソースに対する許容範囲が指定されたユーザ需要を入力する入力ステップと、前記ユーザ需要に対して実際に割り当てる割当リソースを前記許容範囲内に収めるという制約条件の下、前記割当リソースと前記割当要求リソースとの間の差分が大きくなるほど大きくなるユーザ需要ペナルティを有するペナルティを最小にするように、数理最適化問題を解くことにより前記割当リソースを計算する計算ステップと、前記計算ステップにより計算された前記割当リソースをユーザの端末に通知する出力ステップとを備えることを特徴とするリソース割当計算方法。

請求項7

前記リソース割当は通信ネットワークに対するリソース割当であり、前記ペナルティは、前記ユーザ需要ペナルティと、前記ユーザ需要の割り当てに起因して経路が変更されるトラヒック量が大きいほど大きくなる経路変更ペナルティとを有することを特徴とする請求項6に記載のリソース割当計算方法。

請求項8

前記リソース割当は通信ネットワークに対するリソース割当であり、前記ペナルティは、前記ユーザ需要ペナルティと、リンク混雑の程度が大きいほど大きくなるリンク混雑ペナルティとを有することを特徴とする請求項6に記載のリソース割当計算方法。

請求項9

前記リソース割当計算装置が、前記割当リソースの予約を前記端末から受け付けた場合に、前記リソース割当計算装置は、前記割当リソースの情報を、前記通信ネットワークにおいて転送装置の設定を行う制御設定装置に出力することを特徴とする請求項7又は8に記載のリソース割当計算方法。

請求項10

コンピュータを、請求項1ないし5のうちいずれか1項に記載のリソース割当計算装置における各手段として機能させるためのプログラム

技術分野

0001

本発明は、ユーザの需要に基づき、通信ネットワークリソースを制御する技術に関連するものである。

背景技術

0002

通信事業者の提供するネットワーク接続サービスベストエフォート型ギャランティ型に大別される。ベストエフォート型サービスは、通信品質ネットワーク利用帯域の確保を行わないサービスである。通信リソースを複数のユーザで共用することで、低コストで実現できる。主にコンシューマ向けに低価格で提供される。

0003

一方、専用線サービス等に代表されるギャランティ型サービスは、通信リソースを分離することで、通信品質やネットワーク利用帯域を確実に確保するサービスである。通信リソースを契約ユーザ専有させるため、高いコストがかかり、主に事業者向けに高価格で提供される。

0004

しかし、インターネット上のサービスの多様化に伴い、ユーザがネットワークに求める要件も変化しつつある。例えば、利用タイミングに応じて、短期間だけギャランティ型サービスを安く利用したい、といったニーズが増加している。このようなサービスを本明細書では、オンデマンド・ギャランティ型サービスと呼ぶ。

0005

オンデマンド・ギャランティ型サービスを低コストで実現するためには、ネットワークのリソース割当ダイナミックに変更する技術と最適なリソース割当を求めるためのネットワーク最適化技術が必要となる。

0006

前者の技術に関しては、近年、SDN(Software-Defined Network)やNFV(Network Functions Virtualization)に代表されるネットワーク仮想化技術進展しており、当該技術を利用することで、ネットワークのリソース割当をダイナミックに変更することが可能となりつつある。後者の技術に関しては、ネットワーク最適化を実現するための数理計画問題がいくつか提案されている(非特許文献1〜3)。

0007

ネットワーク最適化を実現するための数理計画問題の例として、多品種フロー問題による数理最適化モデルが挙げられる。この数理最適化モデルを解くことで、トラヒック需要に対して効率的にネットワークリソースを確保することができる。ここで、従来の数理最適化モデルにおけるトラヒック需要は所与確定的な入力パラメータとして扱われる。つまり、確保する帯域、確保する時間帯が明確に定まっており、指定されたトラヒック需要を完全に満たす解を導出する。ネットワークの混雑等で指定されたトラヒック需要が一部しか満たせない場合には、解を出力できない。すなわち、従来のネットワーク最適化技術では、事業者のリソースのみを制御最適化対象としており、ユーザのトラヒック需要を制御最適化対象としていない。

先行技術

0008

林理恵,清水香里, 井上一郎, 塩本公平,帯域予約型サービスにおける帯域割当て方式とTraffic Engineering技術, 信学技報IEICE Technical Report NS2008-170(2008-03).
A. N. Patel and J. P. Jue, Routing and Scheduling for Variable Bandwidth Advance Reservation., J. Opt. Co,,un. Netw., Vol. 12, No. 12, Dec. 2011.
P. Dharam, C. Q. Wu and Y. Wang, Advance bandwidth reservation with deadline constraint in high-performance networks., InComputing, Networking and Communications (ICNC), 2014 International Conference on (pp. 1041-1045).

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

0009

しかし、実際にはそれらの確定的なトラヒック需要を持つユーザだけでなく、「あいまいなトラヒック需要」しかもたないユーザも存在すると考えられる。つまり、確保する帯域、確保する時間帯が確定的でなく、一定の変化を許容するような需要である。

0010

上記の「あいまいなトラヒック需要」として、例えば、「帯域については少なくとも 30Mbps以上、出来れば100Mbps 欲しい」といったタイプの需要や、「時間帯については、8時から10時までの間で1時間だけ帯域を確保してほしい」といったタイプの需要が想定される。

0011

上記のように、ユーザがトラヒック需要に幅を持たせた場合には、通常の多品種フロー問題よりも制約条件緩和でき、より効率的なネットワークリソースの割当を実現できる可能性が高くなる。

0012

しかし、前述したとおり、従来のネットワーク最適化技術では、事業者のリソースのみを制御最適化対象としており、ユーザの需要を制御最適化対象としていないことから、確保する帯域、確保する時間帯が明確に定まっており、指定されたトラヒック需要を完全に満たす「確定的なトラヒック需要」の解のみしか導出できない、という課題がある。

0013

本発明は上記の点に鑑みてなされたものであり、一定の幅を許容するあいまいなトラヒック需要に対しても、最適なリソース割当を実現することを可能とする技術を提供することを目的とする。

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

0014

本発明の実施の形態によれば、ユーザ需要を満たすように、リソース割当を計算するリソース割当計算装置であって、
割当要求リソースに対する許容範囲が指定されたユーザ需要を入力する入力手段と、
前記ユーザ需要に対して実際に割り当てる割当リソースを前記許容範囲内に収めるという制約条件の下、前記割当リソースと前記割当要求リソースとの間の差分が大きくなるほど大きくなるユーザ需要ペナルティを有するペナルティを最小にするように、数理最適化問題を解くことにより前記割当リソースを計算する計算手段と、
前記計算手段により計算された前記割当リソースをユーザの端末通知する出力手段と
を備えることを特徴とするリソース割当計算装置が提供される。

0015

また、本発明の実施の形態によれば、ユーザ需要を満たすように、リソース割当を計算するリソース割当計算装置が実行するリソース割当計算方法であって、
割当要求リソースに対する許容範囲が指定されたユーザ需要を入力する入力ステップと、
前記ユーザ需要に対して実際に割り当てる割当リソースを前記許容範囲内に収めるという制約条件の下、前記割当リソースと前記割当要求リソースとの間の差分が大きくなるほど大きくなるユーザ需要ペナルティを有するペナルティを最小にするように、数理最適化問題を解くことにより前記割当リソースを計算する計算ステップと、
前記計算ステップにより計算された前記割当リソースをユーザの端末に通知する出力ステップと
を備えることを特徴とするリソース割当計算方法が提供される。

発明の効果

0016

本発明の実施の形態によれば、一定の幅を許容するあいまいなトラヒック需要に対しても、最適なリソース割当を実現することを可能とする技術が提供される。

図面の簡単な説明

0017

あいまいなトラヒック需要のタイプを説明するための図である。
本発明の実施の形態における通信ステムの全体構成図である。
通信ネットワーク内の構成を詳細に示した通信システムの図である。
経路計算装置100の構成図である。
経路計算装置100の全体の処理を示すフローチャートである。
タイプ1におけるペナルティ関数を説明するための図である。
タイプ2におけるペナルティ関数を説明するための図である。

実施例

0018

以下、図面を参照して本発明の実施の形態を説明する。なお、以下で説明する実施の形態は一例に過ぎず、本発明が適用される実施の形態は、以下の実施の形態に限られるわけではない。

0019

(あいまいなトラヒック需要について)
本実施の形態では、後述する経路計算装置が、ユーザからの需要の申告に基づいて、通信ネットワークに割り当てるリソースの算出を行う。まず、本実施の形態においてユーザが申告する需要について説明する。

0020

本実施の形態では、ユーザは、確保する帯域、時間帯等について、一定の幅で変更を許容する「あいまいなトラヒック需要」を申告することが可能である。本実施の形態では、「あいまいなトラヒック需要」を3つのタイプに大別している。ただし、これらのタイプはモデル化にあたっての一例に過ぎず、本発明の適用範囲はこれらのタイプに限定されるわけではない。

0021

以下、本実施の形態の各タイプについて、図1を参照して説明する。図1(a)は、各タイプについて、ユーザが申告する「需要」を規定するパラメータの種類を示している。図1(b)は、各パラメータの値の一例を示している。

0022

<タイプ1>
タイプ1は、ユーザが帯域の変更を許容するタイプの需要である。タイプ1では、ユーザは「開始時刻」、「終了時刻」、「要求帯域」、「最低帯域」を含む需要を申告する。図1(a)に示すように、この申告は、「開始時刻」から「終了時刻」まで、少なくとも「最低帯域」以上、可能であれば「要求帯域」を要求することを意味する。「最低帯域」と「要求帯域」との間であれば、割当帯域が変更されても構わない。ただし、「開始時刻」と「終了時刻」の変更は許容されない。

0023

図1(b)には、具体例として、20:00から22:00まで、少なくとも30Mbps以上、可能であれば100Mbpsを要求する需要が示されている。

0024

<タイプ2>
タイプ2は、ユーザが時間帯の変更を許容するタイプの需要である。タイプ2では、ユーザは「開始時刻」、「終了時刻」、「要求帯域」、「要求時間」を含む需要を申告する。図1(a)に示すように、この申告は、「開始時刻」から「終了時刻」までの間で、「要求時間」だけ「要求帯域」の確保を要求することを意味する。「要求帯域」の提供を開始した時刻を「要求開始時刻」、提供を終了した時刻を「要求終了時刻」と呼ぶ。

0025

図1(b)には、具体例として、現在から22:00までの間で、2時間だけ、50Mbpsの確保を要求する需要が示されている。タイプ2では、要求帯域と割当帯域が異なることを許容しないが、割当時間帯については、「要求時間」だけ確保されているならば、「開始時刻」から「終了時刻」までの間で任意である。

0026

<タイプ3>
タイプ3は、要求トラヒック量を時間内に転送するタイプの需要である。ユーザは「開始時刻」、「終了時刻」、「要求トラヒック量」を含む需要を申告する。図1(a)に示すように、この需要は、「開始時刻」から「終了時刻」までに「要求トラヒック量」の通信を行いたいという需要を意味する。図1(b)には、具体例として、現在から22:00までに10GBの通信を行いたいという需要が示されている。ここでは、各時刻の帯域は任意の値とし、「要求トラヒック量」の転送終了時刻は「終了時刻」までなら許容する。

0027

システム構成
図2に、本発明の実施の形態における通信システムの全体構成図を示す。図2に示すように、本実施の形態の通信システムは、通信ネットワーク200に、複数の端末300と、経路計算装置100が接続された構成を有する。

0028

端末300は、トラヒックを発生させる装置であり、経路計算装置100にユーザ需要(上述した申告)を送信する機能を有する。経路計算装置100は、端末300との関係では、端末300から通信ネットワーク200を介してユーザ需要を受信し、ユーザ需要等に基づき後述するリソース割当の計算を行って、端末300に通信ネットワーク200を介してユーザ需要に対する制御結果(割当可否、割当時刻、割当帯域等)を送信する。

0029

図3は、図2に示す通信システムにおける通信ネットワーク200の部分をより詳細に示した図である。図3に示すように、通信ネットワーク200は、複数の転送装置ノード)220、及び制御設定装置(コントローラ)210を有する。

0030

転送装置220は、通信ネットワーク200におけるトラヒックを転送する装置であり、経路情報に従ってパケットを処理する機能を含む。また、転送装置220は、自身が転送するトラヒック量計測し、トラヒック観測情報として、制御設定装置210に送信する機能、及び、制御設定装置210から受信する経路情報設定命令に従って、経路情報を設定する機能を有する。

0031

制御設定装置210は、ネットワーク内の全ての転送装置220に経路情報を設定する機能、転送装置220から送信されたトラヒック観測情報を経路計算装置100に送信する機能等を有する。

0032

経路計算装置100についてより詳細に説明する。経路計算装置100は、ネットワーク構成情報、トラヒック観測情報、及びユーザ需要を収集し、ユーザ需要を満たすトラヒックの最適経路を計算する装置である。また、経路計算装置100は、制御設定装置100に、計算した経路情報を送信する機能、通信ネットワーク200を経由して、端末300にユーザ需要制御結果を送信する機能等を有する。

0033

経路計算装置100に入力されるネットワーク構成情報は、ノードやリンク等のネットワークのトポロジ情報である。ネットワーク構成情報は、ネットワーク管理者等が経路計算装置100に与えることとしてもよいし、図3に示すいずれかの装置から経路計算装置100に与えることとしてもよい。

0034

より具体的には、例えば、ネットワークトポロジ時間変化しない場合、ネットワーク管理者等が経路計算装置100に一度だけ入力として与える。また、ネットワークトポロジが時間変化する場合、転送装置220もしくは制御設定装置210から経路計算装置100へ定期的にネットワーク構成情報を送信してもらい、それを入力とする。

0035

経路計算装置100に入力されるトラヒック観測情報は、ノード間を時刻tに流れる背景トラヒック量の予測値を指す。なお、背景トラヒックとは、ユーザが申告した需要に係るトラヒック以外のトラヒックである。

0036

経路計算装置100に入力されるユーザ需要は、図1を参照して説明したとおり、タイプ毎に以下の情報を含む。

0037

タイプ1:開始時刻、終了時刻、要求帯域、最低帯域
タイプ2:開始時刻、終了時刻、要求帯域、要求時間
タイプ3:開始時刻、終了時刻、要求トラヒック量
経路計算装置100から出力されるユーザ需要制御結果は、経路計算装置100が計算したユーザ需要の収容判定の結果と時刻・帯域に関する情報である。具体的には、タイプ毎に以下の情報を含む。

0038

タイプ1:開始時刻、終了時刻、割当帯域
タイプ2:要求開始時刻、要求終了時刻、割当帯域
タイプ3:開始時刻、終了時刻
経路計算装置100から出力される経路情報は、ある時刻、ある経路で流すトラヒック量を示す。なお、トラヒック量を「帯域」と言い換えてもよい。

0039

(経路計算装置100の構成)
図4に、経路計算装置100の構成図を示す。図4に示すように、入力部101、数理最適化問題計算部102、リソース制御部103、出力部104を有する。各部の動作については、後述する動作説明の中で説明する。なお、経路計算装置100は、ユーザ需要を満たすように、通信ネットワークのリソース割当を計算する装置であるから、これをリソース割当計算装置と呼んでもよい。

0040

本実施の形態に係る経路計算装置100は、例えば、コンピュータに、本実施の形態で説明する処理内容記述したプログラムを実行させることにより実現可能である。すなわち、経路計算装置100が有する機能は、当該コンピュータに内蔵されるCPUやメモリなどのハードウェア資源を用いて、経路計算装置100で実施される処理に対応するプログラムを実行することによって実現することが可能である。上記プログラムは、コンピュータが読み取り可能な記録媒体可搬メモリ等)に記録して、保存したり、配布したりすることが可能である。また、上記プログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。

0041

より具体的には、経路計算装置100に入力されたネットワーク構成情報、トラヒック観測情報、及びユーザ需要は、メモリ等の記憶部に格納される。そして、CPUが、後述する数理最適化問題を解くプログラムを実行し、当該プログラムに従って、メモリから情報を読み出し演算を行い、解を計算する。
(経路計算装置100の処理手順
次に、図5のフローチャートに沿って、経路計算装置100の処理手順について説明する。

0042

ステップS1において、入力部101から経路計算装置100に、ネットワーク構成情報、トラヒック観測情報、ユーザ需要が入力される。

0043

具体的には、ネットワーク構成情報は、例えば、ネットワーク管理者から入力される。また、ユーザが、端末300から通信ネットワーク200を介してユーザ需要(申告情報)を送信することで、経路計算装置100にユーザ需要が入力される。トラヒック観測情報は、転送装置220から制御設定装置210により取得され、制御設定装置210から経路計算装置100に入力される。

0044

ユーザ需要に関して、例えば、端末300においてユーザがWebブラウザ画面等から需要のタイプを選択し、タイプの選択後、タイプ毎の必要事項を入力する。入力情報Webサーバに送信され、当該Webサーバから経路計算装置100に入力される。なお、経路計算装置100が当該Webサーバの機能を含むこととしてもよい。

0045

ステップS2において、入力部101から入力された情報に基づいて、数理最適化問題計算部102が、数理最適化問題を計算する。問題の定式化等の詳細については後述する。

0046

ステップS3において、数理最適化問題計算部102は、数理最適化問題の解があるか否かを判定する。ステップS3で解がある場合はステップS4に進む。

0047

ステップS4では、出力部104が、ユーザ需要制御結果を、ユーザ需要の送信元の端末300に送信する。ユーザ需要制御結果は許容帯域許容時間帯等であり、具体的には、タイプ毎に前述したとおりである。

0048

また、ステップS4において、ユーザが帯域予約を望む場合、端末300から経路計算装置100に帯域予約を申請する。つまり、ユーザ需要制御結果の許容帯域、許容時間帯での帯域予約を経路計算装置100に申請する。

0049

ユーザが帯域予約の申請を行うと、経路計算装置100の入力部101が当該申請を入力し、リソース制御部103は、当該ユーザに関するリソース制御結果を制御設定装置210に送信し、制御設定装置210がリソース制御結果を各転送装置220に送信する。リソース制御結果は、経路情報(ある時刻、ある経路で流すトラヒック量を表す情報)である。なお、ユーザ需要に対する数理最適化問題の解によっては、経路情報が、「(時刻1、経路1、トラヒック量1)、(時刻2、経路2、トラヒック量2)、...」のように、時刻毎に異なる経路、異なるトラヒック量を含む情報となる場合がある。

0050

上記の処理により、当該ユーザに割り当てられるリソースが通信ネットワークで確保され、予約した時間が来たら、ユーザにリソースが割り当てられ、トラヒックの送信が行われる。なお、残余帯域がユーザへの割当帯域よりも少ない場合、割り当てられた時間帯の背景トラヒックは経路を変更される。また、背景トラヒックの経路を変更しなくても、ユーザ需要を収容できる場合、背景トラヒックは変化しない。

0051

ユーザが帯域予約の申請を行わず、キャンセルする場合、上記の処理は行われず、ユーザ需要は棄却される。

0052

ステップS3において、ユーザ需要を満たす数理最適化問題の解がない場合、ステップS5に進む。この場合、ユーザ需要の受付は不可能であるため、経路計算装置100はユーザ需要を棄却し、その旨を示すユーザ需要制御結果を端末300に送信する。

0053

最適化問題計算部102の処理の概要
次に、経路計算装置100の最適化問題計算部102が実行する数理最適化問題の計算について説明する。一般に、数理最適化問題では、目的関数と制約条件が設定され、当該制約条件の下、目的関数を満たす最適解(目的関数の値)を求める。このような計算を最適化問題計算部102が実行する。

0054

本実施の形態における数理最適化問題では、ペナルティを最小化するような目的関数を設定する。当該目的関数は、ユーザ需要に関するペナルティ関数と経路変更に関するペナルティ関数とリンクの混雑に関するペナルティ関数を含む。

0055

ユーザ需要のペナルティ関数は、ユーザの要求と数理最適化問題の解が乖離するほど、ペナルティが増加するように定める。具体的には、タイプ1については、実際の帯域が「要求帯域」から減少するにつれ、ペナルティが増加するように定める。タイプ2については、「要求開始時刻」が「開始時刻」から外れるにつれ、ペナルティが増加するように定める。タイプ3については、ペナルティを定めていない。なお、これらのペナルティは一例である。また、タイプ3についても、例えばタイプ2と同様のペナルティを設けることとしてもよい。

0056

経路変更のペナルティ関数については、経路が変更されたトラヒック量に比例するペナルティを定める。つまり、経路変更はユーザの体感品質下げ要因となるため、多くのトラヒックが経路を変更されるほど、経路変更のペナルティを増加させる。なお、経路変更は、ユーザ需要に対するリソースの割当に起因して、生じるものである。また、経路変更が体感品質を下げる要因とならないようなネットワークの場合等においては、経路変更のペナルティを用いることは必須ではない。

0057

リンク混雑のペナルティ関数については、ネットワークを構成するリンクの混雑に応じたペナルティを定める。つまり、リンクの混雑はパケットロス転送遅延等によりユーザの体感品質を下げる要因となったり、受付制御を行っている場合ではユーザからの接続要求拒絶する要因となったりするため、リンクの混雑度に応じてペナルティを増加させる。通常、このリンク混雑は、全期間に渡り最も高いリンクのトラヒック利用率や各期間における最も高いリンクのトラヒック利用率の合計値等により定められる。なお、リンクの混雑が生じないことがわかっている場合等においては、リンク混雑のペナルティ関数を用いないこととしてもよい。

0058

ここで、本実施の形態の数理最適化問題計算部102は、単位時間毎の数理最適化問題を解くこととしている。例えば、単位時間を5分とし、24時間先まで予約を受け付けるとすると、単位時間の数は288 (=24*60/5)となる。

0059

数理最適化問題計算部102は、前の単位時間中に受け付けたユーザ需要を記録しておき、次の単位時間には、ユーザ需要毎に数理最適化問題を解き、収容判定を行う。例えば、前のステップ中に5個のユーザ需要があった場合、次の単位時間に収容判定が5回行われる。

0060

(最適化問題計算部102の処理の詳細)
以下、数理最適化問題計算部102が実行する数理最適化計算について、より詳細に説明する。

0061

数理最適化問題計算を実施するときに新規に受け付けたユーザ需要を「新規需要」と呼び、既に受け付けていたユーザ需要を「既存需要」と呼び、「既存需要」と「新規需要」を含めて「全需要」とする。ユーザが申告した需要以外のトラヒックを「背景トラヒック」と呼ぶ。例えば、ある単位時間1で5個のユーザ需要があった場合、次の単位時間2で数理最適化問題計算の対象となる5個のユーザ需要が「新規需要」である。仮に、この単位時間2で、新たにユーザ需要を受けた場合、この新たなユーザ需要にとって、上記5個のユーザ需要は「既存需要」となる。

0062

集合変数の定義>
数理最適化問題の定式化にあたって使用する集合、変数を以下に示す。

0063

各集合を、経路集合:R、リンク集合:L、新規需要:i∈D、全需要:j∈F、タイプ1の需要の集合:D1⊂D、タイプ2の需要の集合:D2⊂D、と表す。最適化で扱う全期間(前述した単位時間の全期間における集合)をT とし、その要素をt∈Tとする。

0064

<数理最適化問題の定式化:目的関数>
目的関数を下記の式1とする。

0065

ユーザ需要に関するペナルティ関数Pを下記の式2とする。

0066

式2において、p1i,tは、時刻tにおいてタイプ1の需要iが受けるペナルティであり、p2i,tは、時刻tにおいてタイプ2の需要iが受けるペナルティである。

0067

経路変更に関するペナルティ関数Qを下記の式3とする。

0068

リンク混雑に関するペナルティ関数Rを下記の式4とする。

0069

式4において、ul,tはリンクlの期間tにおけるリンク利用率である。式4に示すとおり、リンク混雑のペナルティは、リンク混雑の程度が大きいほど大きくなるペナルティである。

0070

上記のα、β、γは、各ペナルティの重みを決めるパラメータである。タイプ1のペナルティは下記の式5とする。

0071

但し、zは割当帯域であり、fi,t(z)は、図6に示すように、割当帯域zが要求帯域から減少するほど増加するペナルティ関数とする。タイプ2のペナルティは下記の式6とする。

0072

但し、yは要求開始時刻であり、gi,t(y)は、図7に示すように、要求開始時刻yが開始時刻から離れるほど増加するペナルティ関数とする。需要の経路変更ペナルティは下記の式7とする。

0073

但し、xrj,tは、新規需要jについて時刻tに経路r(Rjは、需要jの端点間経路の集合)で流れるトラヒック量である。

0074

<数理最適化問題の定式化:制約条件>
タイプ1の需要の制約条件は、「開始時刻」から「終了時刻」まで、最低帯域以上、要求帯域以下の固定帯域が割り当てられるように定式化したものである。

0075

タイプ2の需要の制約条件は、「開始時刻」から「終了時刻」までの間で、「要求時間」だけ「要求帯域」が割り当てられるように定式化したものである。

0076

タイプ3の需要の制約条件は、「開始時刻」から「終了時刻」までの総トラヒック量が、「要求トラヒック量」と等しくなるように定式化したものである。

0077

なお、制約条件として、更なる制約条件を加えることとしてもよい。

0078

数理最適化問題計算部102は、上述した制約条件の下、P+Q+Rを最少とする解を計算する。数理最適化問題の計算自体は既存技術で行うことができ、例えば市販の数理最適化問題ソフトウェア等により行うことができる。

0079

(実施の形態のまとめ)
本実施の形態では、事業者のリソース制御とユーザの需要制御を同時に行うことを可能にしている。また、あいまいなトラヒック需要をモデル化する際に、最低限確保すべき部分を制約条件とし、追加的に確保する部分については目的関数のなかで評価している。これにより、ユーザの最低確保リソースを担保しつつ、ネットワークの余剰リソースに応じて、追加的にリソースを確保することが可能となっている。

0080

以上、説明したように、本実施の形態により、ユーザ需要を満たすように、リソース割当を計算するリソース割当計算装置であって、割当要求リソースに対する許容範囲が指定されたユーザ需要を入力する入力手段と、前記ユーザ需要に対して実際に割り当てる割当リソースを前記許容範囲内に収めるという制約条件の下、前記割当リソースと前記割当要求リソースとの間の差分が大きくなるほど大きくなるユーザ需要ペナルティを有するペナルティを最小にするように、数理最適化問題を解くことにより前記割当リソースを計算する計算手段と、前記計算手段により計算された前記割当リソースをユーザの端末に通知する出力手段とを備えるリソース割当計算装置が提供される。

0081

実施の形態で説明した経路計算装置100、入力部101、数理最適化問題計算部102、出力部104はそれぞれ、リソース割当計算装置、入力手段、計算手段、出力手段の例である。また、実施の形態で説明した、タイプ1の最低帯域や、タイプ2の開始時刻/終了時刻等は、割当要求リソース(例:要求帯域、要求時間等)に対する許容範囲の例である。

0082

前記リソース割当は例えば通信ネットワークに対するリソース割当であり、前記ペナルティは、前記ユーザ需要ペナルティと、前記ユーザ需要の割り当てに起因して経路が変更されるトラヒック量が大きいほど大きくなる経路変更ペナルティとを有することとしてもよい。

0083

また、前記リソース割当は通信ネットワークに対するリソース割当であり、前記ペナルティは、前記ユーザ需要ペナルティと、リンク混雑の程度が大きいほど大きくなるリンク混雑ペナルティとを有することとしてもよい。

0084

記入力手段が、前記割当リソースの予約を前記端末から受け付けた場合に、前記出力手段は、前記割当リソースの情報を、前記通信ネットワークにおいて転送装置の設定を行う制御設定装置に出力することとしてもよい。前記割当要求リソースは、例えば割当要求帯域又は割当要求時刻である。

0085

以上、本実施の形態について詳述したが、本発明は特定の実施形態に限定したものではない。

0086

例えば、本実施の形態では、事業者のネットワーク制御を例にとったが、サーバ制御コンテンツ制御などの他のリソース制御に関しても同等のモデル化が可能である。

0087

また、既存需要の再割当を行う場合でも同様の制御が可能である。ここで、既存需要の再割当とは、新規需要の帯域割当量を計算する際に、既存需要の帯域等の条件を変更することを指す。例えば、実際の背景トラヒック量が予測した背景トラヒック量よりも少ないとき、既存需要の割当帯域を増加させることなどである。

0088

また、リソース利用効率を目的関数に含む場合でも同等のモデル化が可能である。

0089

また、ユーザ需要制御時において、ネットワークの余剰リソースの一部を残しておく機能を用いることも可能である。これにより、将来発生し得るユーザ需要を受け付けられる可能性を高めることができる。これは、リソース利用効率をペナルティとして表現し、目的関数に含むモデル化、または、リソース利用効率を制約条件に含むパラメータとしてモデル化することが可能である。

0090

(実施の形態の効果等)
本実施の形態における技術により、あいまいなトラヒック需要に対しても、最適なリソース割当を実現することができ、より多くの需要を受け付けることが可能になると同時に、ネットワークのリソース利用率を増加させることが可能になる。

0091

また、要求帯域の変更を許容する需要や要求時間帯の変更を許容する需要など、変更を許容する項目が異なる複数種類の需要を単一のモデルで扱うことができるため、全ての需要に対する経路計算を一度で実施することができ、モデル化にかかるコスト、経路計算にかかるコスト、ネットワーク機器への設定コストなどを抑えることができる。

0092

本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。

0093

100経路計算装置
101 入力部
102数理最適化問題計算部
103リソース制御部
104 出力部

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

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

関連する公募課題

ページトップへ

おススメ サービス

おススメ 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 データ