(57)【要約】【課題】複数のノードと該ノード間を接続する複数の通信経路を備え、その少なくとも一部の通信経路上に仮想回線を設定可能な通信ネットワークにおいて通信経路上に要求された帯域幅をもった仮想回線を設定するための経路探索における通信経路上の帯域の予約方法を提案する。【解決手段】通信経路上に設定が要求された仮想回線のノードＡとノードＢ間の各リンクにおいて、（１）リンクの許容帯域幅から既に予約済みの帯域の帯域幅の総和を差引いた該リンクの余裕帯域幅が、設定を要求された上記仮想回線の要求帯域幅よりも大きい、という条件が満たされた場合は、ノードＡとノードＢ間の各リンクに対し、要求帯域幅を予約済み帯域幅として設定し、（２）上記の条件が満たされないリンクについては、該リンクを上記経路探索における探索対象から除外する、という操作を、各リンクについて行うことで、経路探索を実施する。【選択図】図３
2014045374.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードと該ノード間を接続する複数の通信経路を備え、該通信経路の少なくとも一部の通信経路上に仮想回線を設定することが可能な通信ネットワークにおいて、
あるノード間に帯域要求が生じた場合、
（１）既に該ノード間に仮想回線が設定され、かつ、該仮想回線の経路上の全てのリンクにおいて、リンクの許容帯域幅から既に予約済みの総帯域幅を差引いた該リンクの余裕帯域幅が、要求された要求帯域幅を超えているという条件を満たす場合、該帯域要求を受理し、該要求帯域幅を加えた帯域幅を予約済みの総帯域幅とし、
（２）上記の条件が満たされない場合、前記余裕帯域幅が要求された要求帯域幅を超えていないリンクを探索対象から除外し経路を探索し、経路が探索された場合、該経路上に、該要求帯域幅を該予約済みの総帯域幅として仮想回線を設定することを特徴とするネットワークの帯域予約方法。
【請求項２】
複数のノードと該ノード間を接続する複数の通信経路を備え、該通信経路の少なくとも一部の通信経路上に仮想回線を設定することが可能な通信ネットワークにおいて、
各ノードは、
（１）帯域要求を行う発信元ノードの場合に機能する、
前記仮想回線をリンクの許容帯域幅から既に予約済みの帯域の帯域幅の総和を差引いた該リンクの余裕帯域幅が設定を要求された上記仮想回線の要求帯域幅よりも大きい、という条件を満たすリンクに対し、要求の識別情報、宛先情報、要求帯域幅及び累積コスト値を含む帯域要求信号を同報する処理を行う帯域要求手段と、
（２）前記帯域要求信号を入力した場合に機能する、
前記帯域要求信号に含まれる識別情報に対応付けて、最小累積コスト値及び入力されたポート番号を管理する処理を行う帯域要求管理テーブルと、リンクに接続された出力ポート番号を対応づけて、許容帯域を管理する処理を行うリンク管理テーブルと、到着した帯域要求信号に応じて、予め定められた手順に従いコスト値を算出し、該帯域要求信号の累積コスト値に加算する処理を行うコスト値算出手段と、前記の到着した帯域要求信号の加算後の累積コスト値と、既に登録済の帯域要求信号の示す累積コスト値とを比較する処理を行う累積コスト値比較手段と、上記帯域要求信号が示す要求帯域幅とリンクの余裕帯域幅との比較を、出力リンクに接続された出力ポートについて行う処理を行う帯域幅比較手段と、該出力リンクに関わるリンク管理テーブルの余裕帯域幅を前記帯域要求信号に記載されている要求帯域幅の分だけ減少させ、該帯域要求信号を入力した隣接ノードは除いて、該出力リンクに接続された隣接ノードに対し、累積コスト値の加算後の前記帯域要求信号を同報し、該帯域要求信号に対応付けて、帯域要求管理テーブルの入力ポート番号と累積コスト値とを登録あるいは更新する処理を行う管理テーブル管理手段と、
（３）入力された前記帯域要求信号の宛先情報により該ノードが宛先ノードに指定された場合に機能する、
該前記帯域要求管理テーブルにより特定される累積コスト値が最小の入力リンクが接続する隣接ノードに接続された出力リンクに対し、要求信号の識別情報を含む帯域確保信号を送出する帯域確保信号送出手段と、
（４）前記帯域確保信号を入力した場合に機能する、
前記帯域管理テーブルを参照し前記識別情報に対応付けられ記録された入力ポート番号と、前記帯域確保信号を送出した隣接ノードへの出力リンクに接続された出力ポート番号とを、前記識別情報と対応付け、さらに帯域予約済み経路情報として管理する処理を行う第１管理手段と、
（５）前記の帯域要求信号を同報したノードにおいて、前記帯域要求信号と同じ識別情報を含む前記前記帯域確保信号を入力した場合に機能する、
前記帯域確保信号が入力された入力リンクに接続された入力ポート番号に対応付けられた出力ポート番号と、前記帯域確保信号が含む帯域要求信号の識別情報とを対応付け、さらに前記帯域要求に関わる帯域予約済みの出力ポートとして管理する第２管理手段と、を、
有するものであって、
帯域要求が生じたノードは、前記帯域要求手段により前記帯域要求信号を同報し、
前記帯域要求信号を受信したノードは、前記累積コスト値比較手段における比較結果が、新たに到着した帯域要求信号の累積コスト値よりも、既に帯域要求管理テーブルに登録済の帯域要求信号の示す累積コスト値の方が大きいという条件を満たし、かつ、前記帯域幅比較手段における比較結果が、帯域要求信号が示す要求帯域幅よりも余裕帯域幅が大きいという条件を満たす出力リンクが存在する場合、前記コスト値算出手段により累積コスト値が加算された帯域要求信号を該出力リンクに送出し、該出力リンクの存在が否定された場合、前記帯域要求信号の他のノードへの中継を停止し、
前記帯域要求信号の宛先情報により指定された宛先ノードは、帯域確保信号送出手段により前記帯域確保信号を送出し、
前記帯域確保信号を入力したノードは、前記第1管理手段を用いて仮想回線の帯域予約済み経路の管理を行い、
前記の帯域要求を行ない、前記帯域要求手段により前記帯域要求信号を同報したノードは、前記第2管理手段により該帯域要求を行った仮想回線の出力ポートの管理を行う
ことを特徴とするネットワークの帯域予約方法。
【請求項３】
請求項２記載のネットワークの帯域予約方法を用いて、前記の経路探索を行うことを特徴とする請求項１に記載のネットワークの帯域予約方法。
【請求項４】
複数のノードと該ノード間を接続する複数の通信経路を備え、該通信経路の少なくとも一部の通信経路上に仮想回線を設定することが可能な通信ネットワークにおいて上記通信経路上に要求された帯域幅をもった仮想回線を設定するための経路探索における通信経路上の帯域の予約方法であって、
上記通信経路上に設定することが要求された仮想回線の一端のノードと他端のノード間の上記仮想回線の候補となる各リンクにおいて、
複数の通信フローをアグリゲートする帯域可変のパスにより複数のノード間が接続されたネットワークにおいて、
ある送信元ノードからある宛先ノードに対し、経路の異なる複数の前記パスが設定可能であり、前記送信元ノードから前記宛先ノードに対し帯域予約要求が生じた時、
（１）既に設定済のパスが存在する場合、
（１−１）前記設定済のパスがたどる経路上のいずれのリンクにおいても、前記帯域予約要求が要求する要求帯域幅がリンクの許容帯域幅からパスの既に予約済みの帯域の帯域幅の総和を差引いた該リンクの余裕帯域幅を超えてないならば、前記設定済のパスがたどる経路上のいずれのリンクの前記パスの予約帯域幅を前記の要求帯域幅の分だけ増加させ、
（１−２）前記設定済のパスがたどる経路において、前記帯域予約要求が要求する要求帯域幅がいずれかのリンクの余裕帯域幅を超える場合は、該リンクを含み前記要求帯域幅がリンクの余裕帯域幅を超えなくなるまでリンクをすべて回避して、新たなパスを設定し、前記要求帯域幅を前記パスに割り当て、
（２）設定済のパスが存在しない場合、前記要求帯域幅が余裕帯域幅を超えなくなるまでリンクを回避して、新たなパスを設定し、前記要求帯域幅を前記パスに割り当てることを特徴とするネットワークの帯域予約方法。
【請求項５】
前記帯域予約要求が要求する帯域幅は、複数の通信フローのための帯域予約要求を満たすのに十分な値とすることを特徴とする請求項４記載のネットワークの帯域予約方法。
【請求項６】
パス内の予約済み帯域の総和と、パスの許容帯域からパス内の予約済み帯域の総和を減じて得られるパスの余裕帯域と、の差が定められた値より小さくなった場合、との差が定められた値より小さくなった場合、複数のフローの要求を満たすのに十分な帯域を要求することを特徴とする請求項５記載のネットワークの帯域予約方法。
【請求項７】
前記通信ネットワークにおいて、全てあるいは一部のノードがコンテンツをキャッシュする機能を有し、請求項１から請求項６のいずれか１つに記載のネットワークの帯域予約方法を用いて、送信元ノードから宛先ノード間への経路を決定し、該経路上のコンテンツをキャッシュする機能を有するノードは、送信元ノードから配信されるコンテンツをキャッシュしつつ前記経路にそって中継転送することを特徴とするネットワークの帯域予約方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のノード間をフローあるいはパスにより接続するパスネットワークにおける帯域予約方法に関する。
【背景技術】
【０００２】
ネットワークの帯域予約方法として、ＲＳＶＰ（Resource reSerVation Protocol）技術がある。これは、送信元ノードが、宛先ノードまでの設定された経路に対し帯域を予約するもので、テレビ会議やリアルタイムの動画像配信などに対し、保証された帯域を提供するためのものである。一方、ＭＰＬＳ（Multi-Protocol Label Switching）に代表されるパスネットワークは、送信元ノードと宛先ノードの間のパスを提供するものである。パスネットワークにおける経路制御は、一般的には、ＩＰ（Internet Protocol）ネットワークのルーティング制御に準拠し実施される。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特願２０１１−２８５８７０号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ＲＳＶＰによる帯域予約は、ルーティングプロトコルなどにより、送信元ノードと宛先ノードとの間に設定された一つの経路（最小コスト値経路）上で実施されるものであり、設定された経路において、オーバフロー（トラヒックの溢れ）が生じた場合、かかる帯域要求はブロックされ、他の経路に迂回する制御は実施されない。図1に示すネットワーク例において、ノード１１からノード１８への最短経路上のノード１４とノード１７の間のリンクで輻輳が生じる場合に、オーバフローした分を、他の経路、例えば、ノード１２、１３、１６を経由する経路に余裕があったとしても、この余裕のある経路に切り替えることはできない。
【０００５】
MPLS上でのRSVP制御も同じで、送信元ノードと宛先ノードとの間に設定されたパスにおいて、オーバフローが生じれば、かかる帯域要求はブロックされる。別の経路に迂回させないので、他のリンクに余裕があったとしても利用することができず、無駄が生じている。
【０００６】
MPLSにおいて、経路を動的に設定する場合、その処理負荷や設定のための処理時間がかかるという課題がある。また、通信フロー毎にパスを割り当てると、管理すべきパスの数が増大、ひいては、パスの設定回数が増大するという課題が生じる。
【課題を解決するための手段】
【０００７】
本発明の第１のネットワークの帯域予約方法は、複数のノードと該ノード間を接続する複数の通信経路を備え、該通信経路の少なくとも一部の通信経路上に仮想回線を設定することが可能な通信ネットワークにおいて、
あるノード間に帯域要求が生じた場合、
（１）既に該ノード間に仮想回線が設定され、かつ、該仮想回線の経路上の全てのリンクにおいて、リンクの許容帯域幅から既に予約済みの総帯域幅を差引いた該リンクの余裕帯域幅が、要求された要求帯域幅を超えているという条件を満たす場合、該帯域要求を受理し、該要求帯域幅を加えた帯域幅を予約済みの総帯域幅とし、
（２）上記の条件が満たされない場合、前記余裕帯域幅が要求された要求帯域幅を超えていないリンクを探索対象から除外し経路を探索し、経路が探索された場合、該経路上に、該要求帯域幅を該予約済みの総帯域幅として仮想回線を設定することを特徴とするとする。
【０００８】
また、本発明の第２のネットワークの帯域予約方法は、複数のノードと該ノード間を接続する複数の通信経路を備え、該通信経路の少なくとも一部の通信経路上に仮想回線を設定することが可能な通信ネットワークにおいて、
各ノードは、
（１）帯域要求を行う発信元ノードの場合に機能する、
前記仮想回線をリンクの許容帯域幅から既に予約済みの帯域の帯域幅の総和を差引いた該リンクの余裕帯域幅が設定を要求された上記仮想回線の要求帯域幅よりも大きい、という条件を満たすリンクに対し、要求の識別情報、宛先情報、要求帯域幅及び累積コスト値を含む帯域要求信号を同報する処理を行う帯域要求手段と、
（２）前記帯域要求信号を入力した場合に機能する、
前記帯域要求信号に含まれる識別情報に対応付けて、最小累積コスト値及び入力されたポート番号を管理する処理を行う帯域要求管理テーブルと、リンクに接続された出力ポート番号を対応づけて、許容帯域を管理する処理を行うリンク管理テーブルと、到着した帯域要求信号に応じて、予め定められた手順に従いコスト値を算出し、該帯域要求信号の累積コスト値に加算する処理を行うコスト値算出手段と、前記の到着した帯域要求信号の加算後の累積コスト値と、既に登録済の帯域要求信号の示す累積コスト値とを比較する処理を行う累積コスト値比較手段と、上記帯域要求信号が示す要求帯域幅とリンクの余裕帯域幅との比較を、出力リンクに接続された出力ポートについて行う処理を行う帯域幅比較手段と、該出力リンクに関わるリンク管理テーブルの余裕帯域幅を前記帯域要求信号に記載されている要求帯域幅の分だけ減少させ、該帯域要求信号を入力した隣接ノードは除いて、該出力リンクに接続された隣接ノードに対し、累積コスト値の加算後の前記帯域要求信号を同報し、該帯域要求信号に対応付けて、帯域要求管理テーブルの入力ポート番号と累積コスト値とを登録あるいは更新する処理を行う管理テーブル管理手段と、
（３）入力された前記帯域要求信号の宛先情報により該ノードが宛先ノードに指定された場合に機能する、
該前記帯域要求管理テーブルにより特定される累積コスト値が最小の入力リンクが接続する隣接ノードに接続された出力リンクに対し、要求信号の識別情報を含む帯域確保信号を送出する帯域確保信号送出手段と、
（４）前記帯域確保信号を入力した場合に機能する、
前記帯域管理テーブルを参照し前記識別情報に対応付けられ記録された入力ポート番号と、前記帯域確保信号を送出した隣接ノードへの出力リンクに接続された出力ポート番号とを、前記識別情報と対応付け、さらに帯域予約済み経路情報として管理する処理を行う第１管理手段と、
（５）前記の帯域要求信号を同報したノードにおいて、前記帯域要求信号と同じ識別情報を含む前記前記帯域確保信号を入力した場合に機能する、
前記帯域確保信号が入力された入力リンクに接続された入力ポート番号に対応付けられた出力ポート番号と、前記帯域確保信号が含む帯域要求信号の識別情報とを対応付け、さらに前記帯域要求に関わる帯域予約済みの出力ポートとして管理する第２管理手段と、を、
有するものであって、
帯域要求が生じたノードは、前記帯域要求手段により前記帯域要求信号を同報し、
前記帯域要求信号を受信したノードは、前記累積コスト値比較手段における比較結果が、新たに到着した帯域要求信号の累積コスト値よりも、既に帯域要求管理テーブルに登録済の帯域要求信号の示す累積コスト値の方が大きいという条件を満たし、かつ、前記帯域幅比較手段における比較結果が、帯域要求信号が示す要求帯域幅よりも余裕帯域幅が大きいという条件を満たす出力リンクが存在する場合、前記コスト値算出手段により累積コスト値が加算された帯域要求信号を該出力リンクに送出し、該出力リンクの存在が否定された場合、前記帯域要求信号の他のノードへの中継を停止し、
前記帯域要求信号の宛先情報により指定された宛先ノードは、帯域確保信号送出手段により前記帯域確保信号を送出し、
前記帯域確保信号を入力したノードは、前記第1管理手段を用いて仮想回線の帯域予約済み経路の管理を行い、
前記の帯域要求を行ない、前記帯域要求手段により前記帯域要求信号を同報したノードは、前記第2管理手段により該帯域要求を行った仮想回線の出力ポートの管理を行うことを特徴とする。
【０００９】
また、本発明は、上記第１のネットワークの帯域予約方法であって、上記第２のネットワークの帯域予約方法を用いて、経路探索を行うことを特徴とするものである。
【００１０】
また、本発明のネットワークの帯域予約方法は、複数のノードと該ノード間を接続する複数の通信経路を備え、該通信経路の少なくとも一部の通信経路上に仮想回線を設定することが可能な通信ネットワークにおいて上記通信経路上に要求された帯域幅をもった仮想回線を設定するための経路探索における通信経路上の帯域の予約方法であって、
上記通信経路上に設定することが要求された仮想回線の一端のノードと他端のノード間の上記仮想回線の候補となる各リンクにおいて、
複数の通信フローをアグリゲートする帯域可変のパスにより複数のノード間が接続されたネットワークにおいて、
ある送信元ノードからある宛先ノードに対し、経路の異なる複数の前記パスが設定可能であり、前記送信元ノードから前記宛先ノードに対し帯域予約要求が生じた時、
（１）既に設定済のパスが存在する場合、
（１−１）前記設定済のパスがたどる経路上のいずれのリンクにおいても、前記帯域予約要求が要求する要求帯域幅がリンクの許容帯域幅からパスの既に予約済みの帯域の帯域幅の総和を差引いた該リンクの余裕帯域幅を超えてないならば、前記設定済のパスがたどる経路上のいずれのリンクの前記パスの予約帯域幅を前記の要求帯域幅の分だけ増加させ、
（１−２）前記設定済のパスがたどる経路において、前記帯域予約要求が要求する要求帯域幅がいずれかのリンクの余裕帯域幅を超える場合は、該リンクを含み前記要求帯域幅がリンクの余裕帯域幅を超えなくなるまでリンクをすべて回避して、新たなパスを設定し、前記要求帯域幅を前記パスに割り当て、
（２）設定済のパスが存在しない場合、前記要求帯域幅が余裕帯域幅を超えなくなるまでリンクを回避して、新たなパスを設定し、前記要求帯域幅を前記パスに割り当てることを特徴とする。
【００１１】
また、本発明は、上記第４のネットワークの帯域予約方法であって、前記帯域予約要求が要求する帯域幅は、複数の通信フローのための帯域予約要求を満たすのに十分な値とすることを特徴とするものである。
【００１２】
また、本発明は、パス内の予約済み帯域の総和と、パスの許容帯域からパス内の予約済み帯域の総和を減じて得られるパスの余裕帯域と、の差が定められた値より小さくなった場合、との差が定められた値より小さくなった場合、複数のフローの要求を満たすのに十分な帯域を要求することを特徴とするものである。
【００１３】
また、本発明は、前記通信ネットワークにおいて、全てあるいは一部のノードがコンテンツをキャッシュする機能を有し、上記のネットワークの帯域予約方法を用いて、送信元ノードから宛先ノード間への経路を決定し、該経路上のコンテンツをキャッシュする機能を有するノードは、送信元ノードから配信されるコンテンツをキャッシュしつつ前記経路にそって中継転送することを特徴とするものである。
【発明の効果】
【００１４】
設定経路においてオーバフローが生じた場合、同じ宛先ノードに対し、別の経路を設定するので、ネットワークの利用効率が向上、ひいては、スループットが拡大する。
帯域要求の増大に対し、パスの帯域処理で対応するので、管理すべきパスの数を抑制することができる。
複数のフローに対しパスを設定するので、パスの設定頻度を少なくすることができる。
フローからの通信要求に先だって、事前に帯域を予約するので、予約処理に時間がかかったとして、フローの通信要求を速やかに処理することができる。
【図面の簡単な説明】
【００１５】
【図１】ネットワーク例を示す図である。
【図２】（ａ）フロー管理テーブル例と（ｂ）帯域管理テーブル例を示す図である。
【図３】新たなフローの経路設定のための中継ノードでの各種処理の処理手段を示す図である。
【図４】新たなフローの経路設定のための中継ノードでの処理フローを示す図である。
【図５】各リンクの既に予約済帯域幅が設定済の場合のネットワーク例を示す図である。
【図６】（ａ）パス管理テーブル例と（ｂ）帯域管理テーブル例を示す図である。
【図７】新たなパスの経路設定のための各中継ノードの処理フロー例を示す図である。
【図８】横軸右方向が時間の進行方向であり、縦軸上方向が確保した帯域幅の増大方向である。フローから帯域要求があった場合、パスに対しては、その要求より十分大きい帯域要求を実施する例を示す図である。
【図９】（ａ）５６ノード、双方向１００リンクで構成したシミュレーションのモデルネットワークを示す図、（ｂ）ネットワーク負荷に対するパスあるいはフローの帯域確保率を示す図であり、フローあるいはパスの帯域確保率が１００％となるネットワーク負荷（帯域）は、最短経路ベースでの既存のＲＳＶＰ方式を用いた場合の１３Ｇｂｐｓに対し、本発明を用いた場合は２３Ｇｂｐｓとなり、より高いスループットが得られることを示す。
【図１０】図１のノード１１と１８間の帯域要求信号と帯域確保信号の一連の処理を示す図である。
【図１１】本発明をネットワーク上に存在するコンテンツや処理機能を発見する場合に用いる場合の望ましいフレーム構成例を示す図である。
【発明を実施するための形態】
【００１６】
以下に、この発明の実施の形態を図面に基づいて詳細に説明する。以下の説明においては、同じ機能あるいは類似の機能をもった装置に、特別な理由がない場合には、同じ符号を用いるものとする。
【００１７】
まず、本発明によるネットワークの帯域予約方法は、複数のノードと該ノード間を接続する複数の通信経路を備え、該通信経路の少なくとも一部の通信経路上に仮想回線を設定することが可能な通信ネットワークにおいて、上記通信経路上に要求された帯域幅をもった仮想回線を設定するための経路探索における通信経路上の帯域の予約方法に関するものである。なお、この仮想回線とは、例えば、第1の実施例ではフローであり、第2の実施例では複数のフローをアグリゲートするパスのことである。
【００１８】
実施例の説明の前に、まずフローとパスについて説明する。
フローとは、ＩＰパケットあるいはＭＡＣ（Media Access Control）フレームのヘッダ情報等により識別・定義されるトラヒックの流れである。例えば、送信元ＩＰアドレスと宛先ＩＰアドレスまでの対が共通なフローをＩＰフロー、送信元ＴＣＰポート番号や宛先ＴＣＰポート番号の対が共通なフローをＴＣＰ（Transmission Control Protocol）フローと呼ぶことができる。ＩＰルーティングの場合、送信元ＩＰアドレスと宛先ＩＰアドレスの対が同じＩＰフローに対し、異なる経路設定することができないが、ＴＣＰフローベースで管理すれば、それが可能となる。なお、本発明はフローの定義方法を限定するものでない。
特許文献１（特願２０１１−２８５８７０号明細書）記載のラベルフロースイッチングネットワークにおいては、ラベルによりフローを定義しているが、このようなものも本発明におけるフローに該当する。
【００１９】
また、パスは、一般にパケットが伝送される道筋であり、代表的なものとして、ＯＳＩ参照モデルのレベルＬ１、Ｌ２、Ｌ３について、Ｌ３パスとしてＭＰＬＳ、Ｌ２パスとしてＶＬＡＮ（Virtual Local Area Network）、Ｌ１パスとしてはＳＤＨ（Synchronous Digital Hierarchy）パスなどがある。また、ラベルがつけられたパケットのパスとしてＭＰＬＳに用いられるＬＳＰ（Label Switched Path）も知られている。
【００２０】
なお、帯域要求信号の宛先情報としては、ＩＰアドレスのような情報だけでなく、コンテンツ名あるいはそれに関係付けられたアドレスのようなものでもよいし、前記特許出願明細書においてはラベルにコンテンツを特定するする方法が記載されているが、宛先情報として、該ラベル情報を用いることも含まれる。この場合、各ノードは、（１）宛先情報に対応するコンテンツを保有していない場合は、中継同報を実施し、（２）上記コンテンツを保有していれば、上記ノードが宛先ノードとなり、経路探索を終端し、帯域確保信号の送出を実施する。
【実施例１】
【００２１】
本実施例を図１、図２を用いて説明する。図１において、送信元であるノード１１は、経路が設定されていないフローの通信要求が生じると、全ての出力リンクに対し出力ポートを介し、宛先であるノード１８に向かって経路設定と帯域予約を行うための帯域要求信号を同報する。この帯域要求信号は、中継され、ノード１８に到着する。帯域要求信号は、フローを特定するフローＩＤ、宛先情報、要求帯域幅、累積コスト値を含むものである。また、各ノードは、図２に示すフロー管理テーブルと帯域管理テーブルとを有し、前者には、受信される帯域要求信号が関わるフローに対し、フローＩＤと入力ポート番号と要求帯域幅及びそのノードに至るまでの累積コスト値が記録され、後者には、出力ポートに接続された出力リンクの許容帯域幅と余裕帯域幅が、全ての出力ポートに対応付けられ記録される。ここで、上記余裕帯域幅はリンクの許容帯域幅から予約済み帯域幅の総和を差し引いた値である。
【００２２】
累積コスト値として、ホップ数を用いる場合を例にして説明する。発信元であるノード１１は、隣接するノード１２、１４に対し、あるフローの帯域要求信号を送出する。この時点の累積コスト値は、初期値として例えば０である。ノード１２，１４では、それぞれ、ノード１１からノード１２へのリンク１１→１２、リンク１１→１４のリンクコストを加算し（つまり、ホップ数をインクリメント）し、かつ、要求帯域幅よりも余裕帯域幅が大きいという条件を満たすリンクに対し該帯域要求信号を同報する。ただし、この同報においては、入力されたリンクを除く。ノード１５には、ノード１２経由の帯域要求信号（実線矢印）がノード１４経由の帯域要求信号（点線矢印）よりも先に到着したとすると、先に到着したノード１２経由の帯域要求信号は、フロー管理テーブルに記録されると共に、リンク１５→１４、リンク１５→１６及びリンク１５→１７に同報される。一方、ノード１４からの帯域要求信号は、累積コスト値（この場合はホップ数と同じ）が同じでも後に到着したので、フロー管理テーブルの更新は行われず、同報処理も実施されない。ノード１４では、リンク１４→１７においては、要求帯域幅は余裕帯域幅より大きい状態とする。この場合、この帯域要求を受理するとオーバフローが生じるので、このリンクを介した帯域要求信号の中継は行なわない。即ち、図中、Ｘ印で示すように、この帯域要求はブロックされる。これらの処理が行われた結果、フロー管理テーブルには、図２（ａ）に示す様に中継するフローのフローＩＤに対応した位置に並んで入力ポート番号及び最小累積コスト値が記録される。
【００２３】
最終的には、ノード１８にはノード１６及び１７から、それぞれ帯域要求信号が到着するが、最も累積コスト値が小さく、最も早く到着されたノード１１→１２→１５→１７→１８の経路に対応する帯域要求信号は、ノード１７より入力されたとする。この場合、ノード１８は、フローＩＤを含む帯域確保信号を送出する。各ノードは、帯域確保信号のフローＩＤに基づき、フロー管理テーブルを参照し、入力ポート番号に対応する出力ポートに対し、該帯域確保信号を転送する。この一連の制御により、帯域確保信号は、帯域予約された経路を逆走し、この場合、ノード１８→１７→１５→１２→１１のホップ数４の経路をたどって、発信元のノード１１までの経理の帯域が確保される。図１０に、一連の処理を示す。
【００２４】
従来技術であるＲＳＶＰでは、ホップ数３の最短経路（ノード１１→１４→１７）においてのみ、帯域予約処理が実施されるので、ノード１４→１７のリンクで要求帯域幅が余裕帯域幅より大きい状態となり、この予約要求はブロックされるのに対し、本発明では、次善の最短経路（ノード１１→１２→１５→１７→１８）が設定され、リンクの使用効率、ひいては、ネットワークの総スループットが拡大する。
【００２５】
上述の処理を実現する中継ノードでの処理フローを図４に示す。
Ｆ１：  帯域要求信号が到着した場合、Ｆ２へ。
Ｆ２：  入力されたリンクのコストを計算し、帯域要求信号の累積コスト値に加算し、Ｆ３へ。
Ｆ３：  到着帯域要求信号のフローＩＤと同じフローＩＤのフローがフロー管理テーブルに記録されているかどうかを確認し、記録されていればＦ４へ、記録されていなければ、Ｆ５へ。
Ｆ４：  到着した帯域要求信号の累積コスト値よりも、上記登録済のフローＩＤが同じフローの累積コスト値の方が大きいかどうかを確認し  （ステップＡ）、大きい場合はＦ５へ、大きくない場合はＦ８へ。
Ｆ５：  上記要求帯域よりも上記余裕帯域の方が大きいという条件を満たす出力ポートが存在するかどうかを確認し、存在する場合はＦ６へ、存在しない場合はＦ８へ。
Ｆ６：  上記ポートに対し帯域要求信号を同報  （ステップＢ）し、Ｆ７へ。
Ｆ７：  フロー管理テーブルを更新して、この処理を終了する。
Ｆ８：  フロー管理テーブルを更新しないで、この処理を終了する。
【００２６】
この処理フローにおいては、
Ａ）該中継ノードに至るまでの累積コスト値が最小となる経路の選択、
Ｂ）要求帯域＜余裕帯域の条件を満たす出力リンクに対する同報
の２つの処理を実施する手段をステップＡ，Ｂとして具備している点が特徴である。
【００２７】
上記のような処理フローを実現するためには、図３に示す各種手段を順に用いる。これらの各種手段は、ハードウェアで実現してもよく、また、共通のハードウェア上で動作するソフトウェアによって実現してもよい。ここで、
帯域要求手段は、リンクの許容帯域幅から既に予約済みの帯域の帯域幅の総和を差引いた該リンクの余裕帯域幅が設定を要求された上記仮想回線の要求帯域幅よりも大きい、という条件を満たすリンクに対し、帯域要求信号を同報する処理を行い、
コスト値算出手段は、前記各ノードは、到着した帯域要求信号に応じて、予め定められた手順に従いコスト値を算出し、該帯域要求信号の累積コスト値に加算する処理を行い、
累積コスト値比較手段は、前記の到着した帯域要求信号の加算後の累積コスト値と、既に登録済の帯域要求信号の示す累積コスト値とを比較する処理を行い、
帯域幅比較手段は、上記帯域要求信号が示す要求帯域幅とリンクの余裕帯域幅との比較を、出力リンクに接続された出力ポートについて行う処理を行い、
管理テーブル管理手段は、該出力リンクに関わるリンク管理テーブルの余裕帯域幅を前記帯域要求信号に記載されている要求帯域幅の分だけ減少させ、該帯域要求信号を入力した隣接ノードは除いて、該出力リンクに接続された隣接ノードに対し、累積コスト値の加算後の前記帯域要求信号を同報し、該帯域要求信号に対応付けて、帯域要求管理テーブルの入力ポート番号と累積コスト値とを登録あるいは更新する処理を行い、
第１管理手段は、前記識別情報を含む前記帯域確保信号を入力し上記仮想回線の候補となるノードは、前記帯域管理テーブルを参照し前記識別情報に対応付けられ記録された入力ポート番号と、前記帯域確保信号を送出した隣接ノードへの出力リンクに接続された出力ポート番号とを、前記識別情報と対応付け、さらに帯域予約済み経路情報として管理する処理を行い、
第２管理手段は、前記識別情報を含む前記帯域確保信号を入力した前記送信元ノードは、前記帯域確保信号を送出した隣接ノードへの出力リンクに接続された出力ポート番号を前記識別情報と対応付け帯域予約済み経路情報として管理する処理を行うものである。
ちなみに、上記帯域要求信号は、要求の識別情報、宛先情報、要求帯域幅及び累積コスト値を含む信号である。
また、前記各ノードは、入力される前記帯域要求信号に含まれる識別情報に対応付けられており、最小累積コスト値及び入力されたポート番号を管理する処理を行う帯域要求管理テーブルと、リンクに接続された出力ポート対応に、許容帯域を管理する処理を行うリンク管理テーブルと、を有する。
また、域要求信号の宛先情報により指定された宛先ノードにおいては、該前記帯域要求管理テーブルにより特定される累積コスト値が最小の入力リンクが接続する隣接ノードに接続された出力リンクに対し、要求信号の識別情報を含む帯域確保信号を送出する。
【００２８】
本実施例は、ネットワーク上に存在するコンテンツや処理機能を発見する場合にも用いることができる。この場合に用いるフレーム構成を図１１に示す。コンテンツ発見と帯域予約を行いたいノードをノード１１とし、要求されたコンテンツはノード１８が保有しているとする。図１１（ａ）に示す帯域要求信号を送出する。宛先アドレスとして同報アドレスを設定すると共に、要求コンテンツ名を含む。この要求コンテンツ名は、宛先情報とフローIDの両方の機能を有する。即ち、要求コンテンツを有するノードが宛先ノードとなり、この場合ノード１８が、帯域要求信号を受信すると、発信者ノードのアドレスとしてノード１８のアドレスを設定し、図１１（ｂ）に示すような帯域確保信号を送出する。また、この一連の処理は、図１０と同じ形態で実現される。
【００２９】
なお、本発明は、経路の帯域を予約・確保するための方法を提供するものであり、確保後、ノード内のルータやスイッチにどのようなデータを設定するかは制限していない。例えば、送受信アドレス対やコンテンツ名に関係付けられたフローIDが共通な帯域要求信号の入力ポート番号と帯域確保信号の入力ポート番号を対応付ければ、ルーティングテーブルを実現することができる。
【００３０】
なお、本実施例では、ノード分散の形態で説明を行ったが、このアルゴリズムを、センター装置で集中的に実施し、決定された経路及び予約帯域を各ノードに通知する実施様態を取ってもよい。
【実施例２】
【００３１】
図５から図７を用いて説明する。本実施例は、複数のフローをアグリゲートするパスに対する帯域予約に関するものである。第１の実施例と異なる点は、あるフローの発生によりノード間に帯域要求が生じた場合、既に帯域予約されたパスが存在する場合、パスの経路上の全てのリンクに対し、要求帯域幅よりも余裕帯域幅が大きいという条件を満たすかどうかをチェックし、この条件を満足している場合は、新たな経路を生成せずに、設定済のパスの予約帯域幅を増加させる処理を行う。これにより、フローレベルでの帯域要求の度に、経路探索を行う必要が無く、かつパスの数（例えばラベルパスにおいてはラベル数）の消費を抑制することができる。
【００３２】
図５、図６及び図７において、帯域要求信号は、パスを特定するパスＩＤ、宛先情報、要求帯域幅、累積コスト値を含むものである。また、各ノードは、図６（ａ）パス管理テーブルと図６（ｂ）帯域管理テーブルとを有し、前者図６（ａ）には、受信される帯域要求信号が関わるパスに対し、パスＩＤと入力ポート番号と要求帯域幅とそのノードに至るまでの累積コスト値とが記録され、後者図６（ｂ）には、出力ポートに接続された出力リンクの許容帯域幅と余裕帯域幅（これは、リンクの許容帯域幅から予約済み帯域幅の総和を減じた値に等しい）が、全ての出力ポートに対応付けられて記録される。
【００３３】
新たなパスの経路設定は、第１の実施例と同様の処理フローにより実現される。各中継ノードの処理フローを図７および以下に示す。
Ｇ１：  帯域要求信号が到着した場合、Ｇ２へ。
Ｇ２：  入力されたリンクのコストを計算し、帯域要求信号の累積コスト値に加算し、Ｇ３へ。
Ｇ３：  到着帯域要求信号のパスＩＤと同じパスＩＤのパスがパス管理テーブルに記録されているかどうかを確認し、記録されていればＧ４へ、記録されていなければ、Ｇ５へ。
Ｇ４：  到着した帯域要求信号の累積コスト値よりも上記登録済のパスＩＤが同じパスの累積コスト値の方が大きいかどうかを確認し（ステップＡ）、大きい場合はＧ５へ、大きくない場合はＧ８へ。
Ｇ５：  上記要求帯域よりも上記余裕帯域の方が大きいという条件を満たす出力ポートが存在するかどうかを確認し、存在する場合はＧ６へ、存在しない場合はＧ８へ。
Ｇ６：  上記ポートに対し帯域要求信号を同報（ステップＢ）し、Ｇ７へ。
Ｇ７：  パス管理テーブルを更新して、この処理を終了する。
Ｇ８：  パス管理テーブルを更新しないで、この処理を終了する。
【００３４】
図５のノード１１からノード１８への帯域が確保されたパスの経路として、例えばノード１１→１４→１７→１８の経路が設定済みであるとする。図５の四角欄に記載の数値は、各リンクの既に予約済帯域幅の総和を示す。なお、各リンクの許容帯域幅を、例えば１，０００Ｍｂｐｓとする。
【００３５】
この状態で、ノード１１からノード１８に対し、新たに２Ｍｂｐｓの送信要求が生じたとする。はじめに、ノード１１は、２Ｍｂｐｓ分の帯域増加要求信号を設定済のパスに対し送出する。このパス経路において、最も余裕帯域の小さいリンクは、ノード１４→１７であるが、２Ｍｂｐｓを加算しても、許容帯域以下なので、設定済の予約帯域を２Ｍｂpｓ分増加させる処理で対応できる。従って、ノード１１からノード１８へのパスが確保できる。
【００３６】
次に、宛先ノードであるノード１８は、２Ｍｂｐｓの帯域増加を指示する帯域確保信号を、設定済みのパスの経路を逆走させる。この場合は、同報処理を実施することなく、帯域を予約・確保することができる。この処理により、ノード１４→１７の予約済帯域幅は９９９Ｍｂｐｓとなる。
【００３７】
更に、ノード１１からノード１８への２Ｍｂｐｓの帯域要求が生じたとする。設定済みのパスは、ノード１４→１７のリンクにおいて要求帯域幅の方が余裕帯域幅より大きいという状態が生じ、帯域増加要求信号はブロックされる。なお、このブロック状態は、設定済みのパス経路を用いてノード１１に通知される。ノード１１は、設定済みのパス経路を用いた帯域幅増加の失敗を認識すると、帯域要求信号を新たに同報する。
【００３８】
この場合、リンク１２→１５のリンクでは、要求帯域幅が余裕帯域幅より大きいという状況が生じているので、このリンクの使用はブロックされ、このリンクの使用を回避する条件で、経路が設定される。本実施例では、同報処理を用いた経路設定に先だって、設定済み経路で帯域増加の要求に応えられるかをチェックするので、トラヒック及び処理負荷の増大をもたらす同報通信の頻度を抑制することができる。
【００３９】
なお、本実施例の変形として、帯域増加要求がブロックされた場合、送信元ノードに戻って経路探索を行うのではなく、ブロックが生じたノード、この場合、ノード１４が起点となって、経路探索を行っても良い。ノード１４は、新たなパスＩＤを記した帯域要求信号を、ノード１７へのリンクを除き同報する。この帯域要求信号により、全てのリンクで要求帯域＜余裕帯域となる累積コスト値が最小の経路が探索され、ノード１８は、その経路を用いて、ノード１４に帯域確保信号を送出する。ノード１１からノード１４への経路は要求帯域＜余裕帯域であることを認識しているので、この経路を用いて、新たなパスの設定を行う。これにより、ノード１１からノード１４までは、既設のパスと経路を共有し、ノード１４からノード１８への経路は、同報処理を用いて探索される。この変形方法によれば、同報処理の頻度を更に抑制することができる。
【００４０】
なお、同一宛先ノードに対する設定済みのパスが複数ある場合は、全ての該パスに対し、帯域増加が可能かどうかのチェックを行った後、新たなパスを用いた帯域予約処理を実施する。
【実施例３】
【００４１】
本実施例は、パスの設定頻度を少なくするためのもので、図８（ａ）を用いて説明する。図８（ａ）、（ｂ）では、横軸右方向が時間の進行方向であり、縦軸上方向が確保した帯域幅の増大方向である。フローから帯域要求があった場合、パスに対しては、その要求より十分大きい帯域要求を実施するものである。フロー＃１が、例えば２Ｍｂｐｓの帯域要求を行った場合、パスレベルでは例えば１０Ｍｂｐｓ単位の帯域要求を行う。これによって、過剰分の８Ｍｂｐｓまでは新たなフロー（宛先ノードを共有）による帯域要求に対し、特段の制御をしなくてもこれらのフローを設定済みのパスにアグリゲートできる。図８（ａ）では、フロー＃２、＃３の帯域要求に対し、パスの設定変更を実施しなくても対処し、フロー＃４の帯域要求に対しては、要求帯域幅は余裕帯域幅より大きい状態となり、１０Ｍｂｐｓの帯域増加を含む帯域要求を発生させ、第２の実施例による帯域予約処理を起動させる。同じ経路を用いて帯域要求に応じることができれば、パスの帯域幅を２０Ｍｂｐｓに増加させる処理だけで対応できる。帯域増加処理で対応できない場合は、第２の実施例と同様、同報処理を用いて新たなパスの探索を行う。
【実施例４】
【００４２】
本実施例は、パスの設定処理にかかる時間を、サービスの処理遅延時間として顕在化させないためのものであり、図８（ｂ）を用いて説明する。第３の実施例において、図８（ａ）の左端時点では、フロー＃１〜＃３には帯域が確保されている。図中▼印のタイミングで、新たにフロー＃４のための帯域要求が発生したとする。フロー＃１〜＃３までの予約済帯域幅及びフロー＃４用の要求帯域幅の総和は、１０Ｍｂｐｓを越えるので、更に１０Ｍｂｐｓ帯域を増やす処理が起動される。このパスの設定処理に必要な時間（ハッチで示すパスの設定処理時間）の後、▽で示すタイミングで送信が開始される。
【００４３】
これに対し、本実施例では、図８（ｂ）に示す様に、パスの予約帯域を１０Ｍｂｐｓから更に１０Ｍｂｐｓに増加させる処理は、余裕帯域が予め定められた閾値より小さくなった場合、フローが発生しなくても、許容帯域を２０Ｍｂｐｓとすべく、追加分の１０Ｍｂｐｓの帯域拡大処理を開始する。該閾値としては、フローの平均帯域幅、例えば２Ｍｂｐｓといった値を用いる。この処理時間をハッチで示す。フロー４の帯域要求の発生（▼）がこのパスの設定処理終了後ならば、この時点でフロー＃４の帯域は確保されており、直ちに▽のタイミングで送信が開始できる。図８（ａ）に比べ、通信フローの帯域要求発生（▼）から送信開始（▽）までの時間が短縮されている。この場合、同じ経路では、帯域の拡大ができない場合は、上述の実施例と同様、別の経路が設定される。このように、ある予め決められた帯域幅を単位として事前に帯域確保を行うとこにより、送信開始までの待ち時間を短縮することができる。
【００４４】
なお、ルーティング処理やスイッチング処理は、パケットあるいはフレームのヘッダ情報を用いて行われので、フローあるいはパスの帯域要求の識別情報（ＩＤ）は、これらヘッダ情報に対応付けられて管理されても、フローを定義するヘッダ情報そのものにより規定されてもよい。
【００４５】
本発明の効果をシミュレーションにより示す。図９（ａ）は、モデルネットワークを示すもので、５６ノード、双方向１００リンクで構成されている。各リンクの帯域幅を１Ｇｂｐｓとした場合、ネットワーク負荷に対するパスあるいはフローの帯域確保率を図９（ｂ）に示すように、フローあるいはパスの帯域確保率が１００％となるネットワーク負荷（帯域）は、最短経路ベースでの既存のＲＳＶＰ方式を用いた場合、１３Ｇｂｐｓ、本発明を用いた場合、２３Ｇｂｐｓとなり、より高いスループットが得られることが示される。
【実施例５】
【００４６】
本発明のネットワークの帯域予約方法を用いると、図９に示す様に、最短経路ベースで帯域を予約する場合は、従来方式と同じように、１３Ｇｂｐｓの負荷まで１００％の確率で帯域予約が可能であることは当然であるが、負荷がそれを越える場合、経路コスト値が最短ではなく、次善・次々善の経路が設定されることで、２３Ｇｂｐｓの負荷になるまで１００％確率で帯域予約が可能である。
【００４７】
一般に、次善・次々善の経路は、最短経路よりもホップ数が多い。そこで、中継ノードにごとにコンテンツをキャッシュするキャッシュサーバを配置するか、あるいは中継ノードがキャッシング機能を有する構成にすることで、負荷が大きくなるに従ってホップ数の多い経路が設定され、その結果、中継のついでにコンテンツをキャッシュするキャッシュサーバの数が増大する、という状況を生み出すことができる。
【００４８】
従って、上記のようなキャッシュサーバの数が増加することにより、コンテンツ配信サービスにおいては、サーバが分散されることになり、またホップ数のより小さい位置にあるサーバからのサービスを受けることができるようになり、そのサービスの向上をもたらすことができる。この場合、キャッシュ部分は、ノード内のスイッチ部分を通過するコンテンツをコピーして格納する。
【産業上の利用可能性】
【００４９】
本発明を用いることで、上記の他に、コンテンツ情報量に対応して、経路の帯域予約を行うコンテンツ配信ネットワークを実現することができる。また、ユーザの帯域要求あるいはトラヒック状況に応じて、ノード間の帯域を制御する仮想プライベートネットワークを容易に実現することができる。  
【図１】
2014045374.tif 000003
【図２】
2014045374.tif 000004
【図３】
2014045374.tif 000005
【図４】
2014045374.tif 000006
【図５】
2014045374.tif 000007
【図６】
2014045374.tif 000008
【図７】
2014045374.tif 000009
【図８】
2014045374.tif 000010
【図９】
2014045374.tif 000011
【図１０】
2014045374.tif 000012
【図１１】
2014045374.tif 000013