(57)【要約】【課題】本発明は、各スライスレベルの損失をゼロにして、複数のスライスを同一の物理ネットワーク上に構築することで、スライスを使って提供されるサービスの損失の保守運用管理を簡単にすることを目的とする。【解決手段】本願発明のデータグラムシェイピング方法は、データグラム流の間隔を矯正して出力するデータグラムシェイピング方法であって、データグラムの入力時刻が当該データグラム流よりも前に入力されたデータグラム流の出力可能時刻以前であるか否かを判定する入力時刻判定手順と、データグラムの入力時刻が当該データグラム流よりも前に入力されたデータグラム流の出力可能時刻以前である場合には当該データグラム流よりも前に入力されたデータグラム流の出力可能時刻を待って当該データグラム流を出力し、データグラムの入力時刻が当該データグラム流よりも前に入力されたデータグラム流の出力可能時刻よりも後である場合には直ちに当該データグラム流を出力するデータグラム流出力手順を順に有する。【選択図】図２
2014225799.tif 000002
【特許請求の範囲】
【請求項１】
データグラム流の間隔を矯正して出力するデータグラムシェイピング方法であって、
入力された入力データグラムの入力時刻が定められた出力可能時刻以前であるか否かを判定する入力時刻判定手順と、
前記入力データグラムの入力時刻が前記出力可能時刻以前である場合には前記直前データグラム流の出力可能時刻を待って前記入力データグラム流を出力し、前記入力データグラムの入力時刻が前記出力可能時刻よりも後である場合には直ちに前記入力データグラムを出力するデータグラム流出力手順と、
を順に有する、
データグラムシェイピング方法。
【請求項２】
前記入力データグラム流の出力開始時刻から、前記入力データグラム流の長さに比例しかつ前記入力データグラム流に割り当てられた出力帯域に反比例する出力間隔が経過した時刻を、前記入力データグラム流の後に入力される直後データグラム流の前記出力可能時刻に設定する出力可能時刻設定手順を、
前記データグラム流出力手順の後にさらに有し、
前記直後データグラム流の前記データグラム流出力手順における前記出力可能時刻は、前記出力可能時刻設定手順で設定した前記出力可能時刻である、
ことを特徴とする請求項１に記載のデータグラムシェイピング方法。
【請求項３】
前記入力データグラム流の入力時刻が、前記出力可能時刻からデータグラムシェイピング装置がデータグラム流をそのまま出力できる最大バースト時間を経過した時刻以前であるか否かを判定する出力可能時刻判定手順と、
前記入力データグラム流の入力時刻が前記最大バースト時間を経過した時刻以前であると前記出力可能時刻判定手順で判定した場合には、前記入力データグラム流の出力可能時刻から、前記入力データグラム流のデータグラムの長さに比例しかつ前記入力データグラム流に割り当てられた出力帯域に反比例する出力間隔の経過した時刻を、前記入力データグラム流の後に入力される直後データグラム流の出力可能時刻に設定し、前記入力データグラム流の入力時刻が前記最大バースト時間を経過した時刻の後であると前記出力可能時刻判定手順で判定した場合には、前記入力データグラム流の入力時刻を前記最大バースト時間さかのぼった時刻から、前記入力データグラム流のデータグラムの長さに比例しかつ前記入力データグラム流に割り当てられた出力帯域に反比例する出力間隔の経過した時刻を、前記直後データグラム流の出力可能時刻に設定する、出力可能時刻設定手順と、
を前記データグラム流出力手順の後にさらに有し、
前記直後データグラム流の前記データグラム流出力手順における前記出力可能時刻は、前記出力可能時刻設定手順で設定した前記出力可能時刻である、
ことを特徴とする請求項１に記載のデータグラムシェイピング方法。
【請求項４】
複数のノードが接続された物理ネットワーク上に少なくとも１つのスライスを構築するスライス構築方法であって、
設定されているトラヒックパラメータに従い、請求項１に記載の前記入力時刻判定手順及び前記データグラム流出力手順を実行するか、或いは、前記入力時刻判定手順及び前記データグラム流出力手順の後にさらに請求項２に記載の前記出力可能時刻設定手順を実行するか、或いは、前記入力時刻判定手順及び前記データグラム流出力手順の後にさらに請求項３に記載の前記出力可能時刻判定手順及び前記出力可能時刻設定手順を実行することによって、スライスに入力するデータグラムのシェイピング、スライスの使用するノードから出力するデータグラムのシェイピングの少なくともいずれか一つを行い、シェイピングに必要なバッファ量の管理を行う、
スライス構築方法。
【請求項５】
データグラム流の間隔を矯正して出力するデータグラムシェイピング装置であって、
入力された入力データグラムの入力時刻が定められた出力可能時刻以前であるか否かを判定する入力時刻判定部と、
前記入力データグラムの入力時刻が前記出力可能時刻以前である場合には前記直前データグラム流の出力可能時刻を待って前記入力データグラム流を出力し、前記入力データグラムの入力時刻が前記出力可能時刻よりも後である場合には直ちに前記入力データグラムを出力するデータグラム流出力部と、
を備えるデータグラムシェイピング装置。
【請求項６】
前記入力データグラム流の出力開始時刻から、前記入力データグラム流の長さに比例しかつ前記入力データグラム流に割り当てられた出力帯域に反比例する出力間隔が経過した時刻を、前記入力データグラム流の後に入力される直後データグラム流の前記出力可能時刻に設定する出力可能時刻設定部をさらに備え、
前記データグラム流出力部の前記出力可能時刻は、前記出力可能時刻設定部の設定した前記出力可能時刻である、
ことを特徴とする請求項５に記載のデータグラムシェイピング装置。
【請求項７】
前記入力データグラム流の入力時刻が、前記出力可能時刻からデータグラムシェイピング装置がデータグラム流をそのまま出力できる最大バースト時間を経過した時刻以前であるか否かを判定する出力可能時刻判定部と、
前記入力データグラム流の入力時刻が前記最大バースト時間を経過した時刻以前であると前記出力可能時刻判定部が判定した場合には、前記入力データグラム流の出力可能時刻から、前記入力データグラム流のデータグラムの長さに比例しかつ前記入力データグラム流に割り当てられた出力帯域に反比例する出力間隔の経過した時刻を、前記入力データグラム流の後に入力される直後データグラム流の出力可能時刻に設定し、前記入力データグラム流の入力時刻が前記最大バースト時間を経過した時刻の後であると前記出力可能時刻判定部が判定した場合には、前記入力データグラム流の入力時刻を前記最大バースト時間さかのぼった時刻から、前記入力データグラム流のデータグラムの長さに比例しかつ前記入力データグラム流に割り当てられた出力帯域に反比例する出力間隔の経過した時刻を、前記直後データグラム流の出力可能時刻に設定する、出力可能時刻設定部と、
をさらに備え、
前記データグラム流出力部の前記出力可能時刻は、前記出力可能時刻設定部の設定した前記出力可能時刻である、
ことを特徴とする請求項５に記載のデータグラムシェイピング装置。
【請求項８】
複数のノードが接続された物理ネットワーク上に少なくとも１つのスライスを構築するスライス構築システムであって、
設定されているトラヒックパラメータに従い、請求項５から７のいずれかに記載のデータグラムシェイピング装置を用いて、スライスに入力するデータグラムのシェイピングを行うスライス入力時シェイピング部と、
設定されているトラヒックパラメータに従い、請求項５から７のいずれかに記載のデータグラムシェイピング装置を用いて、スライスの使用するノードから出力するデータグラムのシェイピングを行うノード出力時シェイピング部と、
の少なくともいずれか一つと、
前記スライス入力時シェイピング部又は前記ノード出力時シェイピング部の少なくともいずれか一つにおけるシェイピングに必要なバッファ量の管理を行うバッファ量管理部と、
を備えるスライス構築システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データグラム（パケットやイーサネット（登録商標）フレーム等）のネットワーク内での間隔を調節するデータグラムシェイピング装置（シェイパー）及びデータグラムシェイピング方法に関する。および、それを用いてバッファ管理することによりデータグラムの損失のないネットワークを構築するスライス構築システム及びスライス構築方法に関する。
【背景技術】
【０００２】
現在、世界中の様々な所でコンピュータ間通信が行われている。このコンピュータ間通信において、コンピュータ間のネットワークで発生するデータグラムの損失が上位レイヤに大きく影響する場合がある。例えば、ネットワークにおける新しい技術として、非特許文献１などに述べられているネットワーク仮想化では、実際の物理ネットワーク上にスライスと呼ばれる仮想的なネットワークを構築する。データグラムの損失がないスライスは、スライスのユーザにとって大変扱い易い理想的なものであるが、物理ネットワーク上では、通常、ノード内のバッファ等でデータグラムの損失が発生するため、そのままではデータグラムの損失がないスライスを提供することはできない。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】中尾彰宏，“新世代ネットワーク構想におけるネットワーク仮想化”，電子情報通信学会誌，ｖｏｌ．９４，  ｎｏ．５，  ｐｐ．３８５−３９０，  Ｍａｙ  ２０１１．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上述したように、本発明が解決しようとする課題は、ネットワークにおけるデータグラムの損失を、理想として無くすこと、または、できる限り少なくすることである。例えば、スライスの場合、通常、複数のスライスが同一の物理ネットワーク上に構築されるため、実際には相互に影響し合い、提供するスライスにおけるデータグラムの損失（以下、データグラムの損失を単に損失と記す）などのネットワーク品質は変動する。このため、スライスの提供者として、保守運用管理（ＯＡＭ；Ｏｐｅｒａｔｉｏｎｓ，  Ａｄｍｉｎｉｓｔｒａｔｉｏｎ  ａｎｄ  Ｍａｉｎｔｅｎａｎｃｅ）を行ってスライスにおける損失などのネットワーク品質を把握したり、また、スライスの使用者に提供条件を示したりすることが難しかった。
【０００５】
そこで、スライスの使用者に、スライスにおける損失などのネットワーク品質をできるだけ分かり易い提供条件として示すことができるような、スライスの構築方法が必要とされていた。
【０００６】
また、その一つの解として、損失がないスライスを同一の物理ネットワーク上に複数構築することができれば、少なくともスライスにおける損失については、損失がないという分かり易い品質条件を示すことができる。
【０００７】
しかしながら、どのようにすれば損失がないスライスを同一の物理ネットワーク上に複数構築することができるか、具体的な方法は明らかにされていなかった。
【０００８】
そこで、本発明は、各スライスレベルの損失をゼロにして、複数のスライスを同一の物理ネットワーク上に構築することで、スライスを使って提供されるサービスの損失の保守運用管理を簡単にすることを目的とする。
【課題を解決するための手段】
【０００９】
本願発明のデータグラムシェイピング方法は、
データグラム流の間隔を矯正して出力するデータグラムシェイピング方法であって、
入力された入力データグラムの入力時刻が定められた出力可能時刻以前であるか否かを判定する入力時刻判定手順と、
前記入力データグラムの入力時刻が前記出力可能時刻以前である場合には前記直前データグラム流の出力可能時刻を待って前記入力データグラム流を出力し、前記入力データグラムの入力時刻が前記出力可能時刻よりも後である場合には直ちに前記入力データグラムを出力するデータグラム流出力手順と、
を順に有する。
【００１０】
本願発明のデータグラムシェイピング方法では、
前記入力データグラム流の出力開始時刻から、前記入力データグラム流の長さに比例しかつ前記入力データグラム流に割り当てられた出力帯域に反比例する出力間隔が経過した時刻を、前記入力データグラム流の後に入力される直後データグラム流の前記出力可能時刻に設定する出力可能時刻設定手順を、
前記データグラム流出力手順の後にさらに有し、
前記直後データグラム流の前記データグラム流出力手順における前記出力可能時刻は、前記出力可能時刻設定手順で設定した前記出力可能時刻であってもよい。
【００１１】
本願発明のデータグラムシェイピング方法では、
前記入力データグラム流の入力時刻が、前記出力可能時刻からデータグラムシェイピング装置がデータグラム流をそのまま出力できる最大バースト時間を経過した時刻以前であるか否かを判定する出力可能時刻判定手順と、
前記入力データグラム流の入力時刻が前記最大バースト時間を経過した時刻以前であると前記出力可能時刻判定手順で判定した場合には、前記入力データグラム流の出力可能時刻から、前記入力データグラム流のデータグラムの長さに比例しかつ前記入力データグラム流に割り当てられた出力帯域に反比例する出力間隔の経過した時刻を、前記入力データグラム流の後に入力される直後データグラム流の出力可能時刻に設定し、前記入力データグラム流の入力時刻が前記最大バースト時間を経過した時刻の後であると前記出力可能時刻判定手順で判定した場合には、前記入力データグラム流の入力時刻を前記最大バースト時間さかのぼった時刻から、前記入力データグラム流のデータグラムの長さに比例しかつ前記入力データグラム流に割り当てられた出力帯域に反比例する出力間隔の経過した時刻を、前記直後データグラム流の出力可能時刻に設定する、出力可能時刻設定手順と、
を前記データグラム流出力手順の後にさらに有し、
前記直後データグラム流の前記データグラム流出力手順における前記出力可能時刻は、前記出力可能時刻設定手順で設定した前記出力可能時刻であってもよい。
【００１２】
本願発明のスライス構築方法は、
複数のノードが接続された物理ネットワーク上に少なくとも１つのスライスを構築するスライス構築方法であって、
設定されているトラヒックパラメータに従い、前記入力時刻判定手順及び前記データグラム流出力手順を実行するか、或いは、前記入力時刻判定手順及び前記データグラム流出力手順の後にさらに前記出力可能時刻設定手順を実行するか、或いは、前記入力時刻判定手順及び前記データグラム流出力手順の後にさらに前記出力可能時刻判定手順及び前記出力可能時刻設定手順を実行することによって、スライスに入力するデータグラムのシェイピング、スライスの使用するノードから出力するデータグラムのシェイピングの少なくともいずれか一つを行い、シェイピングに必要なバッファ量の管理を行う。
【００１３】
本願発明のデータグラムシェイピング装置は、
データグラム流の間隔を矯正して出力するデータグラムシェイピング装置であって、
入力された入力データグラムの入力時刻が定められた出力可能時刻以前であるか否かを判定する入力時刻判定部と、
前記入力データグラムの入力時刻が前記出力可能時刻以前である場合には前記直前データグラム流の出力可能時刻を待って前記入力データグラム流を出力し、前記入力データグラムの入力時刻が前記出力可能時刻よりも後である場合には直ちに前記入力データグラムを出力するデータグラム流出力部と、
を備えるデータグラムシェイピング装置。
【００１４】
本願発明のデータグラムシェイピング装置では、
前記入力データグラム流の出力開始時刻から、前記入力データグラム流の長さに比例しかつ前記入力データグラム流に割り当てられた出力帯域に反比例する出力間隔が経過した時刻を、前記入力データグラム流の後に入力される直後データグラム流の前記出力可能時刻に設定する出力可能時刻設定部をさらに備え、
前記データグラム流出力部の前記出力可能時刻は、前記出力可能時刻設定部の設定した前記出力可能時刻であってもよい。
【００１５】
本願発明のデータグラムシェイピング装置では、
前記入力データグラム流の入力時刻が、前記出力可能時刻からデータグラムシェイピング装置がデータグラム流をそのまま出力できる最大バースト時間を経過した時刻以前であるか否かを判定する出力可能時刻判定部と、
前記入力データグラム流の入力時刻が前記最大バースト時間を経過した時刻以前であると前記出力可能時刻判定部が判定した場合には、前記入力データグラム流の出力可能時刻から、前記入力データグラム流のデータグラムの長さに比例しかつ前記入力データグラム流に割り当てられた出力帯域に反比例する出力間隔の経過した時刻を、前記入力データグラム流の後に入力される直後データグラム流の出力可能時刻に設定し、前記入力データグラム流の入力時刻が前記最大バースト時間を経過した時刻の後であると前記出力可能時刻判定部が判定した場合には、前記入力データグラム流の入力時刻を前記最大バースト時間さかのぼった時刻から、前記入力データグラム流のデータグラムの長さに比例しかつ前記入力データグラム流に割り当てられた出力帯域に反比例する出力間隔の経過した時刻を、前記直後データグラム流の出力可能時刻に設定する、出力可能時刻設定部と、
をさらに備え、
前記データグラム流出力部の前記出力可能時刻は、前記出力可能時刻設定部の設定した前記出力可能時刻であってもよい。
【００１６】
本願発明のスライス構築システムは、
複数のノードが接続された物理ネットワーク上に少なくとも１つのスライスを構築するスライス構築システムであって、
設定されているトラヒックパラメータに従い、本発明のデータグラムシェイピング装置を用いて、スライスに入力するデータグラムのシェイピングを行うスライス入力時シェイピング部と、
設定されているトラヒックパラメータに従い、本発明のデータグラムシェイピング装置を用いて、スライスの使用するノードから出力するデータグラムのシェイピングを行うノード出力時シェイピング部と、
の少なくともいずれか一つと、
前記スライス入力時シェイピング部又は前記ノード出力時シェイピング部の少なくともいずれか一つにおけるシェイピングに必要なバッファ量の管理を行うバッファ量管理部と、
を備える。
【発明の効果】
【００１７】
本発明によれば、各スライスレベルの損失をゼロにして、複数のスライスを同一の物理ネットワーク上に構築することで、スライスを使って提供されるサービスの損失の保守運用管理を簡単にすることができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の第１の実施の形態における（完全）シェイピングのフローチャートである。
【図２】本発明の第２の実施の形態における一定長のバーストを許容した（バースティ）シェイピングのフローチャートである。
【図３】本発明の第２の実施の形態におけるシェイピングの実行例である。
【図４】本発明の第３の実施の形態における物理ネットワークとスライスの関係の概要説明図である。
【図５】本発明の第３の実施の形態におけるシェイピングの実行例である。
【図６】本発明の第３の実施の形態におけるバッファ量管理システムの概要説明図である。
【図７】本発明の第３の実施の形態におけるバッファ量管理方法の説明図である。
【図８】本発明の第４の実施の形態におけるバッファ量管理方法の説明図である。
【図９】本発明の第５の実施の形態における物理ネットワークとスライスの関係の概要説明図である。
【図１０】本発明の第５の実施の形態におけるバッファ量管理システムの概要説明図である。
【発明を実施するための形態】
【００１９】
添付の図面を参照して本発明の実施形態を説明する。以下に説明する実施形態は本発明の実施の例であり、本発明は、以下の実施形態に制限されるものではない。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００２０】
［第１の実施の形態］
図１は、本発明におけるデータグラムシェイピング装置（シェイパー）で行うシェイピングアルゴリズムの一つである。このアルゴリズムで行うシェイピングを、以下、完全シェイピングと呼ぶことにする。図１（ａ）のアルゴリズムと図１（ｂ）のアルゴリズムは等価であり、以下、図１（ａ）のアルゴリズムについて説明する。図１（ｂ）については後に述べる。
【００２１】
ｉ番目のデータグラムのシェイパー入力時刻をＴａｉ［ｓｅｃ］、同出力可能時刻をＴｈｉ［ｓｅｃ］、同出力開始時刻をＴｏｉ［ｓｅｃ］、同出力間隔をＩｉ［ｓｅｃ］とする。出力間隔Ｉｉは、該データグラム流にできる限りバースト性がないようにした場合のｉ番目のデータグラムの先頭の出力時刻から次の（ｉ＋１）番目のデータグラムの先頭の出力時刻までの時間間隔であり、以下の式（１）で表される。
Ｉｉ＝Ｌｉ／Ｖ    （１）
ここで、Ｌｉはｉ番目のデータグラムの長さ［ｂｉｔ］、Ｖは該データグラム流に割り当てられた出力帯域Ｖ［ｂｉｔ／ｓｅｃ］である。
【００２２】
式（１）から分かるように、ｉ番目のデータグラムと（ｉ＋１）番目のデータグラムの出力間隔Ｉｉは、ｉ番目のデータグラムの長さに比例し、該データグラム流に割り当てられた出力帯域Ｖに反比例する。
【００２３】
本実施形態におけるシェイパーは、入力時刻判定部と、データグラム流出力部と、出力可能時刻設定部を備え、本実施形態に係るデータグラムシェイピング方法を実行する。本実施形態に係るデータグラムシェイピング方法は、データグラム流の間隔を矯正して出力するデータグラムシェイピング方法であって、入力時刻判定部が実行する入力時刻判定手順と、データグラム流出力部が実行するデータグラム流出力手順と、出力可能時刻設定部が実行する出力可能時刻設定手順を順に有する。説明の都合上、ｉ番目のデータグラムを入力データグラムと呼び、（ｉ−１）番目のデータグラムを直前データグラムと呼び、（ｉ＋１）番目のデータグラムを直後データグラムと呼ぶ。
【００２４】
入力時刻判定手順では、図１（ａ）に示すステップＳ１０３及びＳ１０４を実行する。具体的には、データグラムの入力時刻Ｔａｉが出力可能時刻Ｔｈｉ以前であるか否かを判定する。ｉ番目のデータグラムの出力可能時刻Ｔｈｉは、シェイパーから出力して良い時刻である。
【００２５】
データグラム流出力手順では、図１（ａ）に示すステップＳ１０５からＳ１０７を実行するか、或いは、ステップＳ１０６からＳ１０７を実行する。具体的には、入力データグラムの入力時刻Ｔａｉが出力可能時刻Ｔｈｉ以前、即ち、同時かまたはそれより前である場合には出力可能時刻Ｔｈｉを待って入力データグラム流を出力する（Ｓ１０６からＳ１０７）。一方、入力データグラムの入力時刻Ｔａｉが出力可能時刻Ｔｈｉよりも後である場合には直ちに入力データグラムを出力する（Ｓ１０５からＳ１０７）。
【００２６】
出力可能時刻設定手順では、図１（ａ）に示すステップＳ１０８を実行する。具体的には、入力データグラム流の出力開始時刻Ｔｏｉから出力間隔Ｉｉが経過した時刻を、入力データグラム流の後に入力される直後データグラム流の出力可能時刻Ｔｈｉ＋１に設定する。ここで、出力間隔Ｉｉは、入力データグラム流の長さに比例しかつ入力データグラム流に割り当てられた出力帯域に反比例する時間である。
【００２７】
このように、本実施形態に係る発明は、ｉ番目のデータグラムが時刻Ｔａｉに到着し（Ｓ１０３）、もし、データグラムがＴｈｉ以前にシェイパーに入力している場合（ステップＳ１０４においてＹｅｓ）にはシェイパー内で待機させられ、もし、データグラムがＴｈｉより後に入力した場合（ステップＳ１０４においてＮｏ）には直ちに出力される（Ｓ１０７）。
【００２８】
［第２の実施の形態］
図２は、本発明におけるシェイパーで行うシェイピングのアルゴリズムの一つである。このアルゴリズムはバースト性を考慮しているため、このアルゴリズムで行うシェイピングを、以下、バースティシェイピングと呼ぶことにする。
【００２９】
本実施形態におけるシェイパーは、入力時刻判定部と、データグラム流出力部と、出力可能時刻判定部と、出力可能時刻設定部を備え、本実施形態に係るデータグラムシェイピング方法を実行する。本実施形態に係るデータグラムシェイピング方法は、データグラム流出力手順と出力可能時刻設定手順の間に、出力可能時刻判定部が実行する出力可能時刻判定手順をさらに有する。
【００３０】
最大バースト時間をＴｍ［ｓｅｃ］とする。出力間隔Ｉｉ、データグラムのシェイパー入力時刻Ｔａｉ、データグラムの出力可能時刻Ｔｈｉ、データグラムの出力時刻Ｔｏｉ、は第１の実施の形態と同様である。
【００３１】
最大バースト時間Ｔｍは、十分な空時間の後にシェイパーに入力したバースト的なデータグラムの列、即ち、間隔が詰まったデータグラム列をそのまま出力できる最大の時間である。また、最大バースト時間Ｔｍに、シェイパーに割り当てられた該データグラム流の出力帯域Ｖ（単位はｂｉｔ／ｓｅｃ等でシェイパーの出力端の物理帯域以下）を掛けた値を最大バースト長Ｂｍ（単位はｂｉｔやＢｙｔｅ等）とすると、図２のシェイピングアルゴリズムにより、最大バースト長をＢｍまで許容しつつ、出力帯域がＶ以下になるようにシェイピングされる、と言うこともできる。（註：最大バースト長は、見かけ上隙間のないデータグラム列の最大の長さではない。）尚、この出力帯域Ｖは、後述するスライスに割り当てる帯域でもある。
【００３２】
出力可能時刻判定手順では、入力データグラム流の入力時刻Ｔａｉが、出力可能時刻Ｔｈｉから最大バースト時間Ｔｍを経過した時刻以前であるか否かを判定する（Ｓ２０１）。
【００３３】
入力データグラム流の入力時刻Ｔａｉが最大バースト時間Ｔｍを経過した時刻以前である場合（ステップＳ２０１においてＹｅｓ）には、出力可能時刻設定手順において、入力データグラム流の出力可能時刻Ｔｈｉから出力間隔Ｉｉの経過した時刻（Ｔｈｉ＋Ｉｉ）を、入力データグラム流の後に入力される直後データグラム流の出力可能時刻Ｔｈｉ＋１に設定する（Ｓ２０３）。
【００３４】
一方、入力データグラム流の入力時刻Ｔａｉが最大バースト時間Ｔｍを経過した時刻より後である場合（ステップＳ２０１においてＮｏ）には、出力可能時刻設定手順において、入力データグラム流の入力時刻Ｔａｉを最大バースト時間Ｔｍさかのぼった時刻（Ｔａｉ−Ｔｍ）を算出し（Ｓ２０２）、その時刻から出力間隔Ｉｉの経過した時刻（Ｔｈｉ＋Ｉｉ）を、直後データグラム流の出力可能時刻Ｔｈｉ＋１に設定する（Ｓ２０３）。
【００３５】
なお、ステップＳ１０１からＳ１０６まで及びＳ１０７は第１の実施形態と同様である。すなわち、ｉ番目のデータグラムの出力可能時刻Ｔｈｉは、シェイパーから出力して良い時刻であり、もし、該データグラムがそれ以前にシェイパーに入力している場合にはシェイパー内で待機させられ、もし、該データグラムがそれ以後に入力した場合には直ちに出力される。
【００３６】
尚、このアルゴリズムにおいて、最大バースト時間のパラメータＴｍを０（ゼロ）として不要な記述を省いたものが、完全シェイピングを行う図１（ｂ）のアルゴリズムである。これを更に分かり易く書き換えたものが図１（ａ）のアルゴリズムである。
【００３７】
図３の（ａ）は、バースト的なデータグラム入力の一例である。横軸の値は、最大データグラム長の入出力時間を１単位時間とした場合の値である。図３の（ｂ）〜（ｅ）は、図３の（ａ）の入力に対して、パラメータＴｍの値が３、２、１、０の場合の、図２のアルゴリズムで動作するシェイパーによるシェイピング結果（出力）を示したものである。ここでは、入力データグラム流に割り当てられた出力帯域を、シェイパーの入出力伝送路速度、即ち、物理ビットレートの半分（１／２）としている。
尚、Ｔｍ＝０の場合（図３（ｅ））は完全シェイピングになり、図１のアルゴリズムで動作するシェイパーによるシェイピング結果（出力）と同じになる。
【００３８】
［第３の実施の形態］
本発明の第３の実施の形態を、まず図４で説明する。
図４では、ノードＮｉ（ｉ＝１、２、３、．．．）が接続されている物理ネットワーク９１があり、その上にスライスＳＬ１とスライスＳＬ２が構築されている。以下では、各ノードの入出力速度、すなわち、ノード間の伝送路速度は全て等しいものとする。
【００３９】
各スライスの入力端には、スライス入力時シェイピング部として機能するシェイパー（Ｓ１、Ｓ２）があり、搭載されているシェイピングアルゴリズムと設定されているトラヒックパラメータに従って、入力データグラム流がシェイピングされる。また、各ノードの出力端にもそれぞれノード出力時シェイピング部として機能するシェイパーがあり、第１の実施の形態または第２の実施の形態に示したような、搭載されているシェイピングアルゴリズムと設定されているトラヒックパラメータに従って、各スライスの出力データグラム流がシェイピングされる。
【００４０】
尚、データグラムとしては、イーサネット（登録商標）フレームやＩＰパケットなどがあり、例えば、標準のイーサネット（登録商標）フレームの最大長は１５１８Ｂｙｔｅ（プリアンブル等の８Ｂｙｔｅを除く）であり、ＶＬＡＮの場合は１５２２Ｂｙｔｅ（プリアンブル等の８Ｂｙｔｅを除く）である。これらの場合、そこに内包されているＩＰパケットの最大長は１５００Ｂｙｔｅである。
【００４１】
一方、各ノードでは入力した各スライスのデータグラム流がスイッチングまたは多重されるが、同一方路に出力される場合には、ノード内のバッファに一時保留され、順次出力される。
【００４２】
図５の（ａ）は、ノード（例えば、図４のノードＮ１）への入力の一例であり、入力するデータグラム列の間隔は、シェイパーの出力である図３の（ｃ）と同じである（時刻はｔ’とｔ’’で異なる）。図５の（ｂ）は、上記データグラム列がノードに入力して、他のスライスのデータグラム列の影響により出力が遅延した場合の一例を示したものである。
【００４３】
図５の（ｃ）と（ｄ）は、図５（ａ）のノードへの入力が図５（ｂ）のように出力される場合の、ノードのバッファ使用量の変化を示したものである。図５（ｃ）は、ノードのバッファ使用量として、各データグラムの長さ（ｂｉｔまたはＢｙｔｅ）分の領域を確保する場合である（ケースＡ）。図５（ｄ）は、ノードのバッファ使用量として、バッファへの書き込みおよび読み出しの単位量Ｂｕ［ｂｉｔまたはＢｙｔｅ］毎に確保する場合である（ケースＢ）。各ノードのＢｕの値は、ノードのハードウェア仕様に依存するため、同一のハードウェアを用いる場合には同一になり、異なるハードウェアを用いる場合には異なる場合がある。Ｂｕの値としては、１［ｂｉｔ］、１［Ｂｙｔｅ］、８［Ｂｙｔｅ］、・・・、１５１８［Ｂｙｔｅ］、１５２２［Ｂｙｔｅ］などが考えられる。
【００４４】
以上説明したように、各スライスのデータグラム流が同一方路に出力される場合は、ノード内でデータグラムの蓄積が起こり、ノードＮｉのバッファ量Ｍｉ（ｉ＝１、２、３、．．．）を超えると、損失が発生する。即ち、バーストデータグラム流が重なる確率が小さくても、損失がゼロになることは保証されない。
【００４５】
そこで、各スライスでの損失がゼロになることを保証するために、スライスの構築時に、各ノードＮｉのバッファ量Ｍｉに対して、各スライスが使用する最大バッファ量（詳しくは後述）を確保する。もし、確保できない場合は、損失ゼロのスライスを構築できないものとする。
【００４６】
更に、個々のノードにおいて、このような判断を行うために、バッファ量を一括管理するバッファ量管理システムを設ける。バッファ量管理システムは、図６に示すように、バッファ量管理部として機能するバッファ量管理サーバ９２と、それに繋がっている物理ネットワーク９１上の全ノードおよび全シェイパーから構成される。バッファ量管理サーバ９２には、全ノードから少なくとも各バッファ量Ｍｉの情報が、全シェイパーから少なくともシェイピングに使用しているバッファ量の情報が送られてくる。
【００４７】
尚、図４および図６では、分かり易く説明するために片方向の流れを示しているが、通常のネットワークは双方向であり、逆方向の流れも存在し得る。
【００４８】
図７に、シェイピングアルゴリズムとして完全シェイピングが使われる場合のバッファ量管理サーバ９２内のバッファ量管理テーブルの一例を示す。バッファ量管理テーブル中の値は一例であり、この限りではない。
【００４９】
この例では、スイッチングと各出力端のスライス毎のシェイピングのためのバッファをノードで共通に持っていること（共通メモリ、または、共用メモリ）を前提としている。すなわち、ノードの各入力端から入力したデータグラムは、入力インターフェイスを介してノードの共通メモリに書き込まれ、各出力端のシェイピング機能によって決定した時刻に共通メモリから読み出され、入力インターフェイスを介して出力端から伝送路に出力されるものとする。もし、共通メモリ（または、共用メモリ）でない場合、共通メモリの場合と等価な値に換算できれば同様に扱うことができる。
【００５０】
まず、物理ネットワーク９１上にスライスＳＬ１を構築する場合の動作について、以下に説明する。
バッファ量管理サーバ９２には、スライスＳＬ１に関連する、少なくとも各ノードで使用可能なバッファ量Ｍｉが設定され、バッファ量管理テーブル上に記録されている（図７のバッファ量管理テーブル１、２）。
ノードＮ１に入力するスライスＳＬ１のデータグラム流は、シェイパーＳ１で完全シェイピングされた後にノードＮ１に入力し、ノードＮ１で同様に完全シェイピングされて出力端から次のノードに送られ、これが各ノードで繰り返される。
このため、各ノードに入力する最大バースト長(以下、入力最大バースト長と記す)は最大データグラム長Ｌ１（単位は例えばｂｉｔやＢｙｔｅ）になり、スライスＳＬ１のデータグラムのシェイピング用最大バッファ量をＬ１（単位は例えばｂｉｔやＢｙｔｅ）とする。（この場合には、ノードや伝送路でデータグラム間隔が揺らぐことは基本的にないと考えられるため、シェイピングをしなくてもデータグラムの損失は生じないと考えられる。）
また、入力はスライスＳＬ１からしかないため、各ノードにおいて同時到着による待ち合わせはない。このため、全てのノードにおいて待ち合わせ用バッファは必要ない（待ち合わせ用バッファ量＝０）。
【００５１】
次に、物理ネットワーク９１上にスライスＳＬ１が構築された状態から、新たにスライスＳＬ２を構築する場合の動作について、以下に説明する。
新たにスライスＳＬ２を構築するために、各ノードでスライスＳＬ２用にバッファ量を確保できるか順に確認する。
ノードＮ１に入力するスライスＳＬ２のデータグラム流は、スライスＳＬ１のデータグラム流と同様に、シェイパーＳ２で完全シェイピングされた後にノードＮ１に入力し、ノードＮ１で同様に完全シェイピング（他のスライスのデータグラム流との出力の競合による不可避な遅延を除く）されて出力端から次のノードに送られ、これがスライスＳＬ２に関係する各ノードで繰り返される。
このため、スライスＳＬ２に関係する各ノードに入力する最大バースト長(以下、入力最大バースト長と記す)は最大データグラム長Ｌ２（単位は例えばｂｉｔやＢｙｔｅ）になり、スライスＳＬ２のデータグラムのシェイピング用最大バッファ量をＬ２とする。
ノードＮ１では、スライスＳＬ１とスライスＳＬ２のデータグラムが同一の出力端から次のノードに出力されるため、場合によって出力の競合が生じ、データグラムのバッファからの読み出しに遅延が生じる。これに備えて、待ち合わせ用バッファ量としてＬ１とＬ２の最大値、すなわち、ｍａｘ（Ｌ１，Ｌ２）を確保する。
その他のノードでは出力の競合は生じないため、待ち合わせ用バッファは必要ない（待ち合わせ用バッファ量＝０）。
【００５２】
一般に、各ノードにおいて、異なる入力端から入力したデータグラム流が同一の出力端に出力される場合には、確率は小さいが同時到着による待ち合わせが発生する可能性がある。そこで、データグラム流の総数をＳとし、各データグラム流の最大データグラム長をＬｉとしたとき、（Ｌ１＋Ｌ２＋・・・＋Ｌｓ）−ｍｉｎ（Ｌ１，Ｌ２，・・・，Ｌｓ）のバッファ量が必要である。このバッファ量は、帯域が小さくてもスライスの数が増えると増加する。尚、上記ＳＬ１とＳＬ２の場合には、
（Ｌ１＋Ｌ２）−ｍｉｎ（Ｌ１，Ｌ２）＝ｍａｘ（Ｌ１，Ｌ２）
になる。
【００５３】
以上述べたように、ノードＮ１では、スライスＳＬ１とスライスＳＬ２のデータグラム流が同一の出力端からノードＮ２に出力されるため、Ｌ１＋Ｌ２＋ｍａｘ（Ｌ１，Ｌ２）のバッファ量を確保する。このバッファ量を確保できた場合に、ノードＮ１でのバッファ量確保が完了する。
【００５４】
ノードＮ２では、スライスＳＬ１の出力とスライスＳＬ２のデータグラムが別々の方路に出力されるため、スライスＳＬ２用にノードＮ４向けの出力端でシェイピングが行われる。但し、ノードＮ２にはスライスＳＬ１とスライスＳＬ２の多重されたデータグラム流が入力するため、スライスＳＬ１のデータグラム流のシェイピングに使用する最大バッファ量Ｌ１と、スライスＳＬ２のデータグラム流のシェイピングに使用する最大バッファ量Ｌ２により、Ｌ１＋Ｌ２のバッファ量を確保する。
【００５５】
ノードＮ４では、ノードＮ２の出力端でシェイピングされたデータグラム流が流入するため、シェイピング用バッファ量としてＬ２を確保する。
【００５６】
以上の動作により、図７のバッファ量管理テーブルにおいてノードＮ１、Ｎ２、Ｎ４で各バッファ量を確保できる場合にスライスＳＬ２を構築できる。
【００５７】
以上のような動作により、新たに構築したい、または、変更したいスライスに関連する全てのノードでバッファ量を確保できる場合には、スライスを構築または変更できる。
【００５８】
本実施形態では、スライス入力時シェイピング部がシェイパーＳ１及びＳ２に備わり、ノード出力時シェイピング部が各ノードに備わり、バッファ量管理部がバッファ量管理サーバ９２に備わる例について説明したが、これに限定されない。例えば、スライス入力時シェイピング部、ノード出力時シェイピング部及びバッファ量管理部は共通の装置に備わっていてもよい。
【００５９】
［第４の実施の形態］
図８に、シェイピングアルゴリズムとしてバースティシェイピングが使われる場合のバッファ量管理サーバ９２内のバッファ量管理テーブルの一例を示す。バッファ量管理テーブル中の値は一例であり、この限りではない。
この例では、スイッチングと各出力端のスライス毎のシェイピングのためのバッファをノードで共通に持っていること（共通メモリ、または、共用メモリ）を前提としている。すなわち、ノードの各入力端から入力したデータグラムは、入力インターフェイスを介してノードの共通メモリに書き込まれ、各出力端のシェイピング機能によって決定した時刻に共通メモリから読み出され、入力インターフェイスを介して出力端から伝送路に出力されるものとする。
【００６０】
まず、物理ネットワーク９１上にスライスＳＬ１を構築する場合の動作について、以下に説明する。
バッファ量管理サーバ９２には、スライスＳＬ１に関連する、少なくとも各ノードで使用可能なバッファ量Ｍｉが設定され、バッファ量管理テーブル上に記録されている（図８のバッファ量管理テーブル３、４）。
ノードＮ１に入力するスライスＳＬ１のデータグラム流は、シェイパーＳ１でバースティシェイピングされた後にノードＮ１に入力し、ノードＮ１で同様にバースティシェイピングされて出力端から次のノードに送られ、これが各ノードで繰り返される。
このため、各ノードに入力する最大バースト長(以下、入力最大バースト長と記す)をＢ１（単位は例えばｂｉｔやＢｙｔｅ）とすると、スライスＳＬ１のデータグラムのシェイピング用最大バッファ量をＢ１（単位は例えばｂｉｔやＢｙｔｅ）とする。
また、入力はスライスＳＬ１からしかないため、各ノードにおいて同時到着による待ち合わせはない。このため、全てのノードにおいて待ち合わせ用バッファは必要ない（待ち合わせ用バッファ量＝０）。
【００６１】
次に、物理ネットワーク９１上にスライスＳＬ１が構築された状態から、新たにスライスＳＬ２を構築する場合の動作について、以下に説明する。
新たにスライスＳＬ２を構築するために、各ノードでスライスＳＬ２用にバッファ量を確保できるか順に確認する。
ノードＮ１に入力するスライスＳＬ２のデータグラム流は、スライスＳＬ１のデータグラム流と同様に、シェイパーＳ２でバースティシェイピングされた後にノードＮ１に入力し、ノードＮ１で同様にバースティシェイピング（他のスライスのデータグラム流との出力の競合による不可避な遅延を除く）されて出力端から次のノードに送られ、これがスライスＳＬ２に関係する各ノードで繰り返される。
このため、スライスＳＬ２に関係する各ノードに入力する最大バースト長（以下、入力最大バースト長と記す）をＢ２（単位は例えばｂｉｔやＢｙｔｅ）とすると、スライスＳＬ２のデータグラムのシェイピング用最大バッファ量をＢ２（単位は例えばｂｉｔやＢｙｔｅ）とする。
ノードＮ１では、スライスＳＬ１とスライスＳＬ２のデータグラムが同一の出力端から次のノードに出力されるため、場合によって出力の競合が生じ、データグラムのバッファからの読み出しに遅延が生じる。これに備えて、待ち合わせ用バッファ量としてＢ１とＢ２の最大値、すなわち、ｍａｘ（Ｂ１，Ｂ２）を確保する。
その他のノードでは出力の競合は生じないため、待ち合わせ用バッファは必要ない（待ち合わせ用バッファ量＝０）。
【００６２】
一般に、各ノードにおいて、異なる入力端から入力したデータグラム流が同一の出力端に出力される場合には、確率は小さいが同時到着による待ち合わせが発生する可能性がある。そこで、データグラム流の総数をＳとし、各データグラム流の最大データグラム長をＢｉとしたとき、（Ｂ１＋Ｂ２＋・・・＋Ｂｓ）−ｍｉｎ（Ｂ１，Ｂ２，・・・，Ｂｓ）のバッファ量が必要である。このバッファ量は、帯域が小さくてもスライスの数が増えると増加する。尚、上記ＳＬ１とＳＬ２の場合には、
（Ｂ１＋Ｂ２）−ｍｉｎ（Ｂ１，Ｂ２）＝ｍａｘ（Ｂ１，Ｂ２）
になる。
【００６３】
以上述べたように、ノードＮ１では、スライスＳＬ１とスライスＳＬ２のデータグラム流が同一の出力端からノードＮ２に出力されるため、Ｂ１＋Ｂ２＋ｍａｘ（Ｂ１，Ｂ２）のバッファ量を確保する。このバッファ量を確保できた場合に、ノードＮ１でのバッファ量確保が完了する。
【００６４】
ノードＮ２では、スライスＳＬ１の出力とスライスＳＬ２のデータグラムが別々の方路に出力されるため、スライスＳＬ２用にノードＮ４向けの出力端でシェイピングが行われる。但し、ノードＮ２にはスライスＳＬ１とスライスＳＬ２の多重されたデータグラム流が入力するため、スライスＳＬ１のデータグラム流のシェイピングに使用する最大バッファ量Ｌ１と、スライスＳＬ２のデータグラム流のシェイピングに使用する最大バッファ量Ｌ２により、Ｌ１＋Ｌ２のバッファ量を確保する。
【００６５】
ノードＮ４では、ノードＮ２の出力端でシェイピングされたデータグラム流が流入するため、シェイピング用バッファ量としてＬ２を確保する。
【００６６】
以上の動作により、図８のバッファ量管理テーブルにおいてノードＮ１、Ｎ２、Ｎ４で各バッファ量を確保できる場合にスライスＳＬ２を構築できる。
【００６７】
以上のような動作により、新たに構築したい、または、変更したいスライスに関連する全てのノードでバッファ量を確保できる場合には、スライスを構築または変更できる。
【００６８】
本実施形態では、スライス入力時シェイピング部がシェイパーＳ１及びＳ２に備わり、ノード出力時シェイピング部が各ノードに備わり、バッファ量管理部がバッファ量管理サーバ９２に備わる例について説明したが、これに限定されない。例えば、スライス入力時シェイピング部、ノード出力時シェイピング部及びバッファ量管理部は共通の装置に備わっていてもよい。
【００６９】
［第５の実施の形態］
図４では、各ユーザに対応したスライスを、線的に２地点間を繋ぐものとして示したが、図９のように、スライスを面的に２地点間を繋ぐものとして構築する場合も当然あり得る。また、図１０は、図９のスライスのバッファ量管理システムの概要説明図である。このような場合も、第１の実施例と同様なバッファ量管理やシェイパーの動作設定を行うことにより、データグラムの損失のないスライスを構築することができる。尚、図９および図１０では、分かり易くするために片方向の流れを示しているが、通常のネットワークは双方向であり、逆方向の流れも存在し得る。
【００７０】
また、上述の実施形態では、ノードの伝送路速度が入力側と出力側で等しい場合で例示したが、ノード間を結ぶ伝送路速度が異なっていても良い。その場合は、最大限使用するバッファ量として、出力側と入力側の速度の差により残留するデータグラム流分を最大バースト長に加えれば良い。
【００７１】
また、前述の実施形態では、ネットワークの入り口と途中の全ノードの出力端にスライス毎のシェイパーを備える例を示したが、入り口や途中のノードの少なくとも一つにシェイパーを備えるとしてもよい。ネットワークの入り口と途中の全ノードの出力端にシェイパーを備える場合より損失が発生する確率は上がるが、スライス毎にシェイパーを備えないネットワークに比べて損失を軽減できることは明らかである。少なくとも一つであっても効果があるが、ネットワークの入り口と途中のノードでシェイパーを備えるものの比率が高いほど望ましい。スライスのピークレートの合計値をノードの伝送速度あるいはノードの伝送速度の内で本願の対象とするデータグラムが利用可能な伝送速度の所定の比以下となるようにすれば損失の発生する確率は更に軽減できる。所定の比としては、例えば、０．９５とすればよいし、マージンを見込んで０．９としてもよい。
【００７２】
また、前述の実施形態では、全ノードのバッファ量を管理する例を示したが、ネットワークの入り口や途中のノードの少なくとも一つを管理するとしてもよい。ネットワークの入り口と途中の全ノードで管理する場合より損失が発生する確率は上がるが、バッファ量を管理しないネットワークに比べて損失を軽減できることは明らかである。少なくとも一つであっても効果があるが、ネットワークの入り口と途中のノードでバッファを管理するものの比率が高いほど望ましい。
【００７３】
また、本願の図１及び図２に示すシェイパーは、スライスを用いないネットワークに適用しても良い。すなわち、本願でスライスに対して備えていたシェイパーを方路、パス、コネクション、ＶＬＡＮ、ユーザに対応付けて備えても良い。図１及び図２に示すシェイパーにより、バースト性のあるデータグラム流を許容するネットワークを容易に実現することができる。
【産業上の利用可能性】
【００７４】
本発明のシェイピングアルゴリズムにより、ネットワークにおけるデータグラムの損失を、理想として無くすこと、または、できる限り少なくすることができる。例えば、スライスの場合、通常、複数のスライスが同一の物理ネットワーク上に構築されるため、実際には相互に影響し合い、提供するスライスにおけるデータグラムの損失などのネットワーク品質は変動する。このため、スライスの提供者として、保守運用管理（ＯＡＭ）を行ってスライスにおける損失などのネットワーク品質を把握したり、また、スライスの使用者に提供条件を示したりすることが難しかった。
しかし、本発明により、その一つの解として、損失がないスライスを同一の物理ネットワーク上に複数構築することができる。また、少なくともスライスにおける損失については、損失がないという分かり易い品質条件を示すことができる。
また、本発明のバッファ量管理システムにより、スライスを使って提供されるサービスの損失の保守運用管理を簡単にすることができる。
【符号の説明】
【００７５】
９１：物理ネットワーク
９２：バッファ量管理サーバ
【図１】
2014225799.tif 000003
【図２】
2014225799.tif 000004
【図３】
2014225799.tif 000005
【図４】
2014225799.tif 000006
【図５】
2014225799.tif 000007
【図６】
2014225799.tif 000008
【図７】
2014225799.tif 000009
【図８】
2014225799.tif 000010
【図９】
2014225799.tif 000011
【図１０】
2014225799.tif 000012