(57)【要約】【課題】本発明はネットワークの各ノードにおける遅延敏感サービスの最大遅延を予測し、遅延保証を提供する【解決手段】  本発明の遅延予測方法は、サービスフローの経路の各ホップにおける当該サービスフローの遅延を予測する遅延予測方法であって、前記各ホップにおける最大のキュー長さを求める第１の工程と、求められた前記各ホップにおける最大のキュー長さに基づき、前記各ホップにおけるそれぞれの最大のキュー遅延を予測する第２の工程とを含む。【選択図】図３
2007104677.tif 000002
【特許請求の範囲】
【請求項１】
サービスフローの経路の各ホップにおける当該サービスフローの遅延を予測する遅延予測方法であって、
前記各ホップにおける最大のキュー長さを求める第１の工程と、
求められた前記各ホップにおける最大のキュー長さに基づき、前記各ホップにおけるそれぞれの最大のキュー遅延を予測する第２の工程と
を含む遅延予測方法。
【請求項２】
サービスフローの経路を選択する方法であって、
前記サービスフローの経路における各ホップの最大のキュー長さから前記各ホップにおける最大のキュー遅延を求め、前記各ホップにおける最大のキュー遅延に基づき、前記経路の総遅延を求める経路総遅延決定工程と、
所望の総遅延より小さい総遅延の経路を選択する経路選択工程と
を含む
サービスフロー経路選択方法。
【請求項３】
サービスフローの遅延要求に基づきサービスフロー経路における次のホップを定めるルート決定方法であって、
前記サービスフロー経路における現在の最後のホップから隣接する複数のノードまでのリンクコストを求めるリンクコスト決定工程と、
前記サービスフロー経路における前記各ホップの最大のキュー長さから前記各ホップにおける最大のキュー遅延を求め、前記各ホップの最大のキュー遅延に基づき、前記現在の最後のホップから前記隣接する複数のノードまでの各ノードの遅延コストを求める遅延コスト決定工程と、
前記複数のリンクコストのうち、最小のリンクコストを有するノードが複数ある場合は、最小の遅延コストを有するノードを次のホップとする工程と
を含む
ルート決定方法。
【請求項４】
サービスフローの遅延要求に基づきサービスフロー経路における次のホップを定めるルート決定方法であって、
前記サービスフロー経路における前記各ホップの最大のキュー長さから前記各ホップにおける最大のキュー遅延を求め、前記各ホップの最大のキュー遅延に基づき、現在の最後のホップから隣接する複数のノードまでの各ノードの遅延コストを求める遅延コスト決定工程と、
最小の遅延コストを有するノードを次のホップとする工程と
を含む
ルート決定方法。
【請求項５】
新しいサービスの受付制御に用いる遅延保証受付制御方法であって、
新しいサービス経路における各ホップの最大のキュー長さから、前記新しいサービス経路における各ノードの最大のキュー遅延を求め、前記各ノードの最大のキュー遅延に基づき、前記新しいサービスが前記新しいサービス経路における一部のノードでの最大遅延を増大するか否かを判断する工程と、
最大遅延が増大すると判断された前記ノードに、遅延敏感サービスフローが存在するか否かを判断する工程と、
前記ノードにおける遅延敏感サービスフローを損なわない新しいサービスのみを受け付ける工程と
を含む
遅延保証受付制御方法。
【請求項６】
サービスフローの経路の各ホップにおける当該サービスフローの遅延を予測する遅延予測装置であって、
前記各ホップにおける最大のキュー長さを求めるキュー長さ決定手段と、
求められた前記各ホップにおける最大のキュー長さに基づき、前記各ホップにおけるそれぞれの最大のキュー遅延を予測するキュー遅延決定手段と
を含む
遅延予測装置。
【請求項７】
サービスフローの経路を選択する装置であって、
前記サービスフローの経路における各ホップの最大のキュー長さから前記各ホップにおける最大のキュー遅延を求め、前記各ホップにおける最大のキュー遅延に基づき、前記経路の総遅延を求める経路総遅延決定手段と、
所望の総遅延より小さい総遅延の経路を選択する経路選択手段と
を含む
サービスフロー経路選択装置。
【請求項８】
サービスフローの遅延要求に基づきサービスフロー経路における次のホップを定めるルート決定装置であって、
前記サービスフロー経路における現在の最後のホップから隣接する複数のノードまでのリンクコストを求めるリンクコスト決定手段と、
前記サービスフロー経路における前記各ホップの最大のキュー長さから前記各ホップにおける最大のキュー遅延を求め、前記各ホップの最大のキュー遅延に基づき、前記現在の最後のホップから前記隣接する複数のノードまでの各ノードの遅延コストを求める遅延コスト決定手段と、
前記複数のリンクコストのうち、最小のリンクコストを有するノードが複数ある場合は、最小の遅延コストを有するノードを次のホップとするホップ決定手段と
を含む
ルート決定装置。
【請求項９】
サービスフローの遅延要求に基づきサービスフロー経路における次のホップを定めるルート決定装置であって、
前記サービスフロー経路における前記各ホップの最大のキュー長さから前記各ホップにおける最大のキュー遅延を求め、前記各ホップの最大のキュー遅延に基づき、現在の最後のホップから隣接する複数のノードまでの各ノードの遅延コストを求める遅延コスト決定手段と、
最小の遅延コストを有するノードを次のホップとするホップ決定手段と
を含む
ルート決定装置。
【請求項１０】
新しいサービスの受付制御に用いる遅延保証受付制御装置であって、
新しいサービス経路における各ホップの最大のキュー長さから、前記新しいサービス経路における各ノードの最大のキュー遅延を求め、前記各ノードの最大のキュー遅延に基づき、前記新しいサービスが前記新しいサービス経路における一部のノードでの最大遅延を増大するか否かを判断する第１の判断手段と、
最大遅延が増大すると判断された前記ノードに、遅延敏感サービスフローが存在するか否かを判断する第２の判断手段と、
前記ノードにおける遅延敏感サービスフローを損なわない新しいサービスのみを受け付ける受付手段と
を含む
遅延保証受付制御装置。
【請求項１１】
サービスフロー経路における各ホップでのサービスフローの遅延を予測する遅延予測装置と、
前記予測された各ホップにおける遅延に基づき、サービス品質を制御するサービス品質制御装置と
を含み、
前記遅延予測装置は、
前記各ホップにおける最大のキュー長さを求めるキュー長さ決定手段と、
求められた前記各ホップにおける最大のキュー長さに基づき、前記各ホップにおけるそれぞれの最大のキュー遅延を予測するキュー遅延決定手段と
を有する
サービス品質保証システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電気通信ネットワークにおけるサービス品質（ＱｏＳ）の制御に関し、特に、ネットワークの各ノードにおける遅延敏感サービスの遅延を予測し、遅延保証を提供する技術に関する。
【背景技術】
【０００２】
近年、益々多くの新しいサービスがＩＰネットワーク上に応用されつつある。このようなサービスのうち、ＩＰ電話、テレビ会議など多くのサービスは、ネットワークに伝送する際に生じる時間的遅延に影響されやすく、大きな遅延はサービスの品質を大きく低減する恐れがある（以下、「遅延に影響されやすいサービス」を「遅延敏感サービス」と称する）。そのため、ＩＰネットワーク制御の分野において、サービス品質（ＱｏＳ）保証は注目される研究課題になっており、既に多くの研究成果が得られている。これらの研究は主に以下２種類のモデルのいずれかに基づくものである、即ち、IntServサービス（Integrated  Service）とDiffServサービス（Differentiated  Service）である。IntServサービスモデルの長所はサービスフロー（flow）ごとにサービス品質保証を提供できることである。しかし、サービスフローごとにリソース確保と制御が必要であるため、IntServサービスモデルはスケーラビリティ（scalability）上大きな問題があり、大規模なネットワークに応用することができない。一方、DiffServサービスは、ネットワークトラヒックを異なるレベルのクラスに分類し、各トラヒッククラスに対して制御を行う。これにより、スケーラビリティの問題が解決されている。現在、DiffServサービスモデルは、既に実際のネットワークに応用されている。しかし、DiffServサービスモデルは、サービスフローごとにサービス品質保証を提供しないので、サービス提供業者（サービス・プロバイダーという）は、遅延敏感サービスのエンド・ツー・エンド（end-to-end）遅延を保証するために、「過剰配分」（over-provisioning）の方法を採用している。この過剰配分方法は以下の問題点がある。１）多くのネットワークリソースは無駄になる；２）ネットワークトラヒックが持続的に増加する際に、それと同時に全ネットワークに亘って「過剰配分」を保証することはできない；３）異なる遅延敏感サービスに対して異なる保証を提供することができない（例えば、ＩＰ電話による遅延保証要求はテレビ会議より遙かに厳しい）。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明は、ネットワークの各ノードにおける遅延敏感サービスの最大遅延を予測し、遅延保証を提供する方法を提供する。
【０００４】
また、本発明は遅延予測方法とその装置、並びに予測された遅延に基づいて、サービスフローにサービス品質（ＱｏＳ）保証を提供する方法とその装置を提供する。
【課題を解決するための手段】
【０００５】
本発明の第１の観点によれば、本発明の遅延予測方法は、サービスフローの経路の各ホップにおける当該サービスフローの遅延を予測する遅延予測方法であって、前記各ホップにおける最大のキュー長さを求める第１の工程と、求められた前記各ホップにおける最大のキュー長さに基づき、前記各ホップにおけるそれぞれの最大のキュー遅延を予測する第２の工程とを含む。
【０００６】
本発明の第２の観点によれば、本発明のサービスフロー経路選択方法は、サービスフローの経路を選択する方法であって、前記サービスフローの経路における各ホップの最大のキュー長さから前記各ホップにおける最大のキュー遅延を求め、前記各ホップにおける最大のキュー遅延に基づき、前記経路の総遅延を求める経路総遅延決定工程と、所望の総遅延より小さい総遅延の経路を選択する経路選択工程とを含む。
【０００７】
本発明の第３の観点によれば、本発明のルート決定方法は、サービスフローの遅延要求に基づきサービスフロー経路における次のホップを定めるルート決定方法であって、前記サービスフロー経路における現在の最後のホップから隣接する複数のノードまでのリンクコストを求めるリンクコスト決定工程と、前記サービスフロー経路における前記各ホップの最大のキュー長さから前記各ホップにおける最大のキュー遅延を求め、前記各ホップの最大のキュー遅延に基づき、前記現在の最後のホップから前記隣接する複数のノードまでの各ノードの遅延コストを求める遅延コスト決定工程と、前記複数のリンクコストのうち、最小のリンクコストを有するノードが複数ある場合は、最小の遅延コストを有するノードを次のホップとする工程とを含む。
【０００８】
本発明の第４の観点によれば、本発明のルート決定方法は、サービスフローの遅延要求に基づきサービスフロー経路における次のホップを定めるルート決定方法であって、前記サービスフロー経路における前記各ホップの最大のキュー長さから前記各ホップにおける最大のキュー遅延を求め、前記各ホップの最大のキュー遅延に基づき、現在の最後のホップから隣接する複数のノードまでの各ノードの遅延コストを求める遅延コスト決定工程と、最小の遅延コストを有するノードを次のホップとする工程とを含む。
【０００９】
本発明の第５の観点によれば、本発明の遅延保証受付制御方法は、新しいサービスの受付制御に用いるものであって、新しいサービス経路における各ホップの最大のキュー長さから、前記新しいサービス経路における各ノードの最大のキュー遅延を求め、前記各ノードの最大のキュー遅延に基づき、前記新しいサービスが前記新しいサービス経路における一部のノードでの最大遅延を増大するか否かを判断する工程と、最大遅延が増大すると判断された前記ノードに、遅延敏感サービスフローが存在するか否かを判断する工程と、前記ノードにおける遅延敏感サービスフローを損なわない新しいサービスのみを受け付ける工程とを含む。
【００１０】
本発明の第６の観点によれば、本発明の遅延予測装置は、サービスフローの経路の各ホップにおける当該サービスフローの遅延を予測する遅延予測装置であって、前記各ホップにおける最大のキュー長さを求めるキュー長さ決定手段と、求められた前記各ホップにおける最大のキュー長さに基づき、前記各ホップにおけるそれぞれの最大のキュー遅延を予測するキュー遅延決定手段とを含む。
【００１１】
本発明の第７の観点によれば、本発明のサービスフロー経路選択装置は、サービスフローの経路を選択する装置であって、前記サービスフローの経路における各ホップの最大のキュー長さから前記各ホップにおける最大のキュー遅延を求め、前記各ホップにおける最大のキュー遅延に基づき、前記経路の総遅延を求める経路総遅延決定手段と、所望の総遅延より小さい総遅延の経路を選択する経路選択手段とを含む。
【００１２】
本発明の第８の観点によれば、本発明のルート決定装置は、サービスフローの遅延要求に基づきサービスフロー経路における次のホップを定めるルート決定装置であって、前記サービスフロー経路における現在の最後のホップから隣接する複数のノードまでのリンクコストを求めるリンクコスト決定手段と、前記サービスフロー経路における前記各ホップの最大のキュー長さから前記各ホップにおける最大のキュー遅延を求め、前記各ホップの最大のキュー遅延に基づき、前記現在の最後のホップから前記隣接する複数のノードまでの各ノードの遅延コストを求める遅延コスト決定手段と、前記複数のリンクコストのうち、最小のリンクコストを有するノードが複数ある場合は、最小の遅延コストを有するノードを次のホップとするホップ決定手段とを含む。
【００１３】
本発明の第９の観点によれば、本発明のルート決定装置は、サービスフローの遅延要求に基づきサービスフロー経路における次のホップを定めるルート決定装置であって、前記サービスフロー経路における前記各ホップの最大のキュー長さから前記各ホップにおける最大のキュー遅延を求め、前記各ホップの最大のキュー遅延に基づき、現在の最後のホップから隣接する複数のノードまでの各ノードの遅延コストを求める遅延コスト決定手段と、  最小の遅延コストを有するノードを次のホップとするホップ決定手段とを含む。
【００１４】
本発明の第１０の観点によれば、本発明の遅延保証受付制御装置は、新しいサービスの受付制御に用いる遅延保証受付制御装置であって、新しいサービス経路における各ホップの最大のキュー長さから、前記新しいサービス経路における各ノードの最大のキュー遅延を求め、前記各ノードの最大のキュー遅延に基づき、前記新しいサービスが前記新しいサービス経路における一部のノードでの最大遅延を増大するか否かを判断する第１の判断手段と、最大遅延が増大すると判断された前記ノードに、遅延敏感サービスフローが存在するか否かを判断する第２の判断手段と、前記ノードにおける遅延敏感サービスフローを損なわない新しいサービスのみを受け付ける受付手段とを含む。
【００１５】
本発明の第１１の観点によれば、本発明のサービス品質保証システムは、サービスフロー経路における各ホップでのサービスフローの遅延を予測する遅延予測装置と、前記予測された各ホップにおける遅延に基づき、サービス品質を制御するサービス品質制御装置とを含み、前記遅延予測装置は、前記各ホップにおける最大のキュー長さを求めるキュー長さ決定手段と、求められた前記各ホップにおける最大のキュー長さに基づき、前記各ホップにおけるそれぞれの最大のキュー遅延を予測するキュー遅延決定手段とを有する。
【発明の効果】
【００１６】
本発明において、ネットワークの各ノードにおける遅延敏感サービスの最大遅延は、当該ノードの出力ポートにおける最大のキュー長さと当該ポートにおけるリンク帯域幅により計算される。また、最大のキュー長さは、当該ポートに到着可能な遅延敏感サービスのトラヒックにより予測される。
【００１７】
本発明によれば、正確に遅延保証を提供することができる。
【発明を実施するための最良の形態】
【００１８】
次に、添付した図面を参照しながら、本発明の実施形態を説明する。
【００１９】
従来の遅延予測技術は、ネットワークとトラヒックの実際の状況でなく、ネットワークとトラヒックに関する各種仮定に基づいて予測を行うものである。これら従来の技術を以下の３種類に分類することができる。
１．ネットワークにおいてＥＦトラヒック（Expedited  Forwarding  Traffic）が十分に小さく、且つ、そのキュー遅延を無視できると仮定するもの、
２．ネットワークの各ノードにおいて、ＥＦトラヒックは常にノードの全部の物理的なメモリを充填すると仮定するもの、
３．各ノードの物理的なメモリは無限であり、ネットワークの規模は有限であると仮定するものがある。
【００２０】
この３種類の技術のいずれもがネットワーク及びトラヒックの変化によりもたらした遅延への影響を考慮していない。そのため、これらの技術により得られた予測値と実際の遅延との差が大きい。また、これらの技術は各種仮定に基づいたものであるため、これら各種の仮定は技術の応用範囲を制限する。たとえば、第１類の技術はトラヒックの小さい軽負荷のネットワークにしか応用できず、第２類の技術はより負荷の重いネットワークに適用し、第３類の技術はノード数の少ない小規模のネットワークにしか応用できない。
【００２１】
これに対して、本発明は、ネットワークとトラヒックに関する仮定でなく、ネットワークとトラヒックの実際の状況に基づいて予測を行い、また、ネットワーク及びトラヒックの変化に基づき予測値を更新する。
【００２２】
具他的に、本発明は、ネットワークの各ノードにおける遅延敏感サービスの最大遅延を予測し、遅延保証を提供する。
【００２３】
DiffServサービスモデルにおいて、ＥＦトラヒックは遅延敏感サービスの伝送に用いられ、通常、ＥＦトラヒックは優先順位キューにより実現される。優先順位キューは一種のキュー制御アルゴリズムであり、優先順位の高いデータ・パッケートを優先的に送信するものである。
【００２４】
本発明の遅延予測方法は、各ノードの出力ポートにおけるＥＦトラヒックの最大のキュー長さを見積もって実行される。具体的に、本発明は、先ず最大のキュー遅延を計算し、それをその他の遅延（伝播遅延などがある。当該他の遅延は従来技術により計算できる）に足して、遅延敏感サービスの当該ノードにおける総遅延を得る。最大のキュー遅延を求める際に、まず最大のキュー長さを求め、当該最大のキュー長さに基づき、最大のキュー遅延を計算する。具体的に、本発明は、当該ノードに到着する最大ＥＦトラヒック・バーストを用いて最大のキュー遅延を計算する。
【００２５】
次に、本発明の遅延予測方法の実施の形態を説明する。
【００２６】
図１は、本発明の実施の形態を応用したシステムを示すブロック図である。
【００２７】
図１に示すシステムは３つの層、即ち、管理層１１０，制御層１２０，及びデータ層１３０からなる。
【００２８】
管理層１１０は、ユーザに対して、個人認証、承認、及びチャージを行う。と同時に、管理層１１０は、ユーザが使用中のサービスに対して行った遅延要求を受け付ける。当該遅延要求は制御層１２０に送られる。
【００２９】
制御層１２０はＱｏＳ制御装置３００，遅延予測装置３１０，記憶装置１２６、及びＱｏＳ命令ユニット１２８を含む。管理層１１０から制御層１２０へ送られてきた遅延要求はＱｏＳ制御装置３００に伝送され、そして、遅延予測装置３１０を動作させる。
【００３０】
遅延予測装置３１０は、データベースにおけるデータを用いて、ネットワークの各ノードにおけるユーザサービスフローの遅延、及び当該サービスフローによる既存のサービスへの影響を予測する。ここで、ユーザが申し入れた新しいサービスの開始時間はｔ１であると仮定する。また、ここで、「既存サービスフロー」は、既に遅延保証が得られており、かつ、終了時間はｔ１より遅い全てのサービスフローを含むと仮定する。遅延予測装置３１０は、予測した遅延をＱｏＳ制御装置３００に返す。ＱｏＳ制御装置３００は、遅延予測値、ユーザ要求、及びＱｏＳ制御戦略に基づいて当該サービスフローに対する制御方法を決定する。例えば、当該ユーザに対して遅延保証を提供するか否か、並びに当該サービスフローのネットワークにおける経路を決める。そして、この制御方法はＱｏＳ命令ユニット１２８に送られる。
【００３１】
ＱｏＳ命令ユニット１２８は、制御される設備の具体的な種類により、上記の制御方法を、制御される設備が理解及び実行可能な配置命令に変換し、対応する設備に分配する。
【００３２】
また、データ層における制御される設備は、その配置命令を受け取り、その命令に基づいて、指定されるサービスフローに対して操作を行う。
【００３３】
全体の処理プロセスにおいて、上層からの要求又は命令に対する応答は同時に反対方向に伝送される。
【００３４】
図２は、図１に示すシステムを応用したネットワークを示す概略図である。
【００３５】
図２に示すように、システム２００は、中央制御サーバー２１０、中央管理サーバー２２０、及びルーター２３０Ａ１〜２３０ＡＮを含む。
【００３６】
中央管理サーバー２２０は、図１に示す管理層１１０の機能を実現し、中央制御サーバー２１０は制御層１２０の機能を実現する。必要な計算量に応じて中央制御サーバー２１０と中央管理サーバー２２０は、一つ又は複数の物理的なサーバーに設置される。
【００３７】
ルーター２３０Ａ１〜２３０ＡＮは、ＭＰＬＳ（Multi-Protocol  Label  Switching）機能を具備するネットワーク・エッジ・ルーター（Edge  Router）であり、中央制御サーバー２１０からの命令を受け、また、図１に示すデータ層１３０の機能を実現する、即ち、受付制御（Admission  Control）、トラヒック・シェーピング・（Traffic  Shaping）、明示的なＬＳＰ立ち上げ（Explicit  Label  Switched  Path  Setup）、トラヒック優先順位標記（Traffic  Priority  Marking）、及びトラヒック・マッピング（Traffic  Mapping）などがある。
【００３８】
なお、以上にＭＰＬＳネットワークを例として説明したが、本実施形態は他のネットワークにも適用できることは明らかである。
【００３９】
次に、本実施形態による各ノードにおける遅延予測方法を説明する。
【００４０】
図３は、本実施の形態に係る遅延予測装置を示すブロック図である。
【００４１】
図３に示すように、本実施の形態に係る遅延予測装置３１０は計算部４１０，更新部４２０，予測計算部４５０，及び記憶部４４０を含む。
【００４２】
ＱｏＳ制御装置３００が新しいサービスフローに対して遅延保証を提供することを決定した場合は、当該サービスフローのネットワークにおける経路は遅延予測装置３１０に送られる。遅延予測装置３１０における計算部４１０は、当該サービスフローの入り口から、記憶部４４０におけるデータベースに含まれる各ノードの入力／出力ポートでの帯域幅の情報、及び当該ノードに到着する最大トラヒック・バーストに基づき、逐次に当該経路における各ノードの出力ポートでの最大のキュー長さを求める。
【００４３】
ここで、「逐次に」というのは、下流ノードの計算は、上流ノードの計算結果に依存することを意味する。「最大トラヒック・バースト」は、係るノードにおける全ての上流ノードの最大のキュー長さのうちの最大値である。
【００４４】
入り口ノード以外の各ホップでの最大のキュー長さを逐次に求める際に、更新部４２０は最大トラヒック・バーストを更新する。具体的に、計算部４１０はあるホップでの最大のキュー長さを計算した後、その最大のキュー長さを更新部４２０に伝送する。更新部４２０は、当該最大のキュー長さをデータベースにおける当該ノードに対応する記録の対応項目に書き込み、データベースにおいて当該ノードでの最大のキュー長さのデータを更新する。また、更新部４２０は、当該最大のキュー長さを現在の最大トラヒック・バーストと比較し、そのうちの大きい方を次のホップの入力ポートに到着するトラヒックの最大バーストとして用いる。計算部４１０は次のホップでの最大のキュー長さを計算する際に、当該更新後の最大のキュー長さを用いる。計算部４１０において最大のキュー長さの計算方法は後に説明する。
【００４５】
予測計算部４５０は、ＱｏＳ制御装置３００が所定のノードでの遅延値を必要とするときに起動され、データベースに記録される情報に基づき、遅延敏感サービスの当該ノードにおける最大のキュー遅延を計算し、ＱｏＳ制御装置３００に送る。
【００４６】
本実施形態において、ＥＦトラヒックの以下の特徴が利用される。１）ネットワークの任意経路の各ノード（ホップ）において、ＥＦトラヒックの最大のキュー長さが存在し、また、その最大のキュー長さは、必ずしもバッファーメモリの大きさではない。ここで、その最大のキュー長さをＱｍａｘと記す。２）所定の入力ポートから到着するＥＦトラヒックのバーストの最大値は、当該入力ポートの上流ノードのＱｍａｘの最大値より以下である。
【００４７】
特徴１について説明する。
【００４８】
ＥＦトラヒックの定義によると、トラヒック入力の入力エッジ・ノード（Ingress  Node）において、全てのＥＦトラヒック類型のサービスフローは、パラメータが（ｒｉ、ｂｉ）となる穴あきバケツによりトラヒック・シェーピングされ、かつ、このサービスフローの帯域幅がＱｏＳルーティング・アルゴリズムにより保証される。
【００４９】
例えば、af(t)  =  trf  +  bfで、サービスフローｆがシェーピングされた後のトラヒック曲線を表し（ここで、trfはトラヒック・シェーピングに用いた穴あきバケツの速度を表し、bfは穴あきバケツの深さを表す）、I(i)で、ポートｉでＥＦトラヒックを構成するサービスフローの集合を表すとすれば、ＥＦトラヒックのポートｉでの到着曲線は次のように表すことができる。
【００５０】
【数１】
2007104677.tif 000003
ここで、Ｄは各入力エッジ・ノードからポートｉまでの最大遅延を表す。
【００５１】
ポートｉでのサービス曲線（Service  Curve）は次のように表すことができる。
σ(t)=(tCi-MTU)+,  
ここで、ＭＴＵはポートでの最大伝送ユニットを表す。さらに、ここで、ネットワークにおける各ポートのＭＴＵは同一であると仮定する。また、Ciは当該ポートでのリンク帯域幅を表す。「＋」は数学符号であり、この式の値は負数ではないことを示す。
【００５２】
よって、ＥＦトラヒックのポートｉでの累積(queuing)曲線は次のように表すことができる。
【００５３】
【数２】
2007104677.tif 000004
帯域幅保証のため、即ち、以下の条件が要求されているので、
【００５４】
【数３】
2007104677.tif 000005
次のような結果が得られる。
【００５５】
【数４】
2007104677.tif 000006
ここで、rfはサービスフローの集合I(i)のうち、第ｆ番目のサービスフローを示し、また、サービスフローの集合I(i)は第ｉ番目のポートにおける全てのサービスフローを表す。また、ｔは時間を表す。
【００５６】
任意のネットワークに対しては、入力エッジ・ノードから所定のポートまでの最大遅延は有限値である。即ち、上記式におけるＤは有限値である。従って、各ノードの各ポートでは、ＥＦトラヒックの最大のキュー長さＱｍａｘが存在し、かつ、指定されたバッファーメモリの長さより遙か小さい可能性がある。上記式から分かるように、帯域幅が保証される場合は、ポートにおいてＥＦトラヒックのキューイングは、ＥＦトラヒック・バーストによるものである。よって、到着するＥＦトラヒック・バーストを見積もることにより最大のキュー長さの予測を行うことができる。
【００５７】
特徴２について説明する。
【００５８】
特徴２は厳密優先順位キューイング（Strict  Priority  Queuing）アルゴリズムそのものの特徴に起因する。厳密優先順位キューイングの特徴は、キューイング中の他の類型のトラヒックがいくらあるかに拘わらず、まずはＥＦトラヒックのキューを優先的にクリアしようとすることである。一方、送り出したＥＦトラヒックは出力ポートのリンクの速度で下流ノードに到着する。
【００５９】
例えば、ある経路にノード（ホップ）の数はｈである（ｈ≧１）とし、また、Ｑｉｍａｘは第ｉ（０≦ｉ≦ｈ−１）番目のホップにおけるキューのＥＦトラヒックの最大のキュー長さを表し、Ｑｍａｘ，ｊは第ｊ（０≦ｊ≦ｈ−１）番目のホップにおけるＥＦトラヒック・バーストの最大値を表すとする。よって、入力エッジ・ノードから当該経路の第１のホップへ継続的に送り出すＥＦトラヒックの最大値はＱ０ｍａｘ，０である。以下の２つの状況に応じて、このトラヒックは、第１のホップでキューイングするか、或いは、直接第２のホップへ転送される。
１）当該ホップでは、ＥＦトラヒックの到着する入力ポートの帯域幅は、ＥＦトラヒックが送り出される使用中の出力ポートの帯域幅より以下であり、かつ、当該ホップでは、他の入力ポートから到着するトラヒックは、出力ポートで上記ＥＦトラヒックに加えられることがない。この場合は、当該ＥＦトラヒックは直接次のホップへ転送される。即ち、
Ｑｍａｘ，２＝Ｑ０ｍａｘである。
２）当該ホップでは、ＥＦトラヒックの到着する入力ポートの帯域幅は、ＥＦトラヒックが送り出される使用中の出力ポートの帯域幅より大きい、または、当該ホップでは、他の入力ポートから到着するトラヒックは、出力ポートで上記ＥＦトラヒックに加えられることがある。この時、Ｑ１ｍａｘがＱ０ｍａｘより大きい場合があり、また、Ｑ１ｍａｘが出力ポートのリンク速度で継続的に当該経路における第２のホップへ転送される。即ち、
Ｑｍａｘ，２は＝Ｑ１ｍａｘである。このプロセスが続くと、第ｊ番目のホップでは、ＥＦトラヒック・バーストの最大値はＱｍａｘ，ｊは、以下のように表すことができる。
Ｑｍａｘ，ｊ＝ｍａｘ（Ｑｉｍａｘ）（０≦ｉ＜ｊ）、
または、
Ｑｍａｘ，ｊ＝ｍａｘ（Ｑ０ｍａｘ、…、Ｑｊ−１ｍａｘ、）。
以上のように、各ノードに到着するＥＦトラヒック・バーストの最大値は得られる。また、各ノードにおけるＥＦトラヒックのキュー最大値は当該バーストがノードに到着及びノードから送り出される状況から導出され得る。以下に詳細に説明する。
【００６０】
図４は、ＥＦトラヒックの出力ポートのリンク帯域幅は、その入力ポートのリンク帯域幅の総和より以上である場合、ＥＦトラヒックのキュー最大値を導出する方法を説明する図である。
【００６１】
複数のデータ・パッケートが同時に到着する場合を考慮して、線分ＯＡの最大の長さは
ｍ×ＭＴＵ／Ｃｏｕｔとなる、ここで、ｍはＥＦトラヒックの入力ポートの個数を表す。
【００６２】
よって、出力ポートにおけるＥＦトラヒックの最大のキュー長さ（即ち、線分ＡＢの最大長さ）は、以下のように表すことができる。
【００６３】
【数５】
2007104677.tif 000007
ここで、Ｃｏｕｔは出力ポートのリンク帯域幅を、ΣＣｉｎは入力ポートのリンク帯域幅の総和をそれぞれ表す。ＣｏｕｔとΣＣｉｎはネットワーク・トポロジーにより直接得られる。
【００６４】
図５は、条件ΣＣｉｎ≦Ｃｏｕｔを満たしていないときもある場合の状況を示す。
【００６５】
具体的に、図５は、ＥＦトラヒック・バーストの到着の全過程において、条件ΣＣｉｎ≦Ｃｏｕｔは満たしていない時もある場合は、到着するＥＦトラヒックと送り出されるＥＦトラヒックとの関係を示す。
【００６６】
図５に示すように、ＥＦトラヒックを受け取り始める時に（即ち、点０の場合）、入力ポートのリンク帯域幅の総和は、ＥＦトラヒックの出力ポートのリンク帯域幅より大きい。一部の入力ポートはＥＦトラヒックの受け取りを終了するにつれて、入力ポートのリンク帯域幅の総和は徐々に減少し、出力ポートのリンク帯域幅と同じ、又はそれより小さくなると、ＥＦトラヒックのキューはもはや増加しなくなる。
【００６７】
図５において、線分ＢＣの最大の長さは、ＥＦトラヒックの最大のキュー長さである。しかし、各入力ポートがＥＦトラヒックの受け取りを終了する時間の見積もりをしようとすると、計算は複雑になる。従って、本実施形態には、線分ＤＨの長さを用いて、ＥＦトラヒックの最大のキュー長さを見積もる。また、最初に、ΣＣｉｎ＞Ｃｏｕｔであるので、線分ＤＨの長さは線分ＢＣの最大の長さより大きい、これで予測値の有効性が保証されている。
【００６８】
線分ＤＨの長さは以下のように計算する。
【００６９】
【数６】
2007104677.tif 000008
ここで、Ｃｏｕｔは出力ポートのリンク帯域幅を、ΣＣｉｎは入力ポートのリンク帯域幅の総和をそれぞれ表す。ＣｏｕｔとΣＣｉｎはネットワーク・トポロジーにより直接得られる。即ち、最大のキュー長さは、到着可能な最大トラヒックから、当該トラヒックを受け取る際に発したトラヒックを引いた値に等しい。
【００７０】
以上の説明によれば、以下の式を用いて、ＥＦトラヒックの最大のキュー長さを予測する。
【００７１】
【数７】
2007104677.tif 000009
【００７２】
【数８】
2007104677.tif 000010
【００７３】
【数９】
2007104677.tif 000011
ここで、
ｋは既存のエッジ・ノードから入力された遅延敏感サービスフローの個数を示し、
ｂｉは第ｉ番目のサービスフローのバースト・トラヒックの大きさを示し、
Ｑｈｍａｘ，ｊは第ｈ番目の入力ポートから到着するＥＦトラヒックのバーストの最大値を示し、
Ｃｈ,ｊは入力ポートのリンク帯域幅を示し、
Ｃｊ＋１は出力ポートのリンク帯域幅を示し、
ｍはＥＦトラヒックの入力ポートの個数を示し、
ＭＴＵは最大伝送ユニットのサイズを示す。
即ち、ネットワーク入り口において、トラヒック・シェーピング・パラメータに基づき、入り口における最大のキュー長さを計算し、ネットワーク入り口以外の各ホップにおいて、到着可能な最大トラヒック・バースト、トラヒックが到着するポートにおける速度、及びトラヒックが送り出されるポートにおける速度に基づき、入り口以外の各ホップにおけるそれぞれの最大のキュー長さを計算する。ここで、所定のホップに到着可能な最大トラヒック・バーストは、当該ホップにおける全ての上流ノードの最大のキュー長さのうちの最大値である。
【００７４】
具体的に、以下のように入り口以外の各ホップにおけるそれぞれの最大のキュー長さを計算する。所定のホップの出口における帯域幅は、トラヒックが当該ホップに到着可能な全ての入り口の帯域幅の総和より以上である場合は、当該出口の最大のキュー長さは、最大伝送ユニットのサイズに入り口の個数を乗じた値に等しい（最大伝送ユニットの値は、各ポートにおいて固定されている）；また、当該ホップの出口における帯域幅は、トラヒックが当該ホップに到着可能な全ての入り口の帯域幅の総和より小さい場合、当該出口における最大のキュー長さは、全ての入り口に到着可能な最大トラヒック・バーストの総和から、当該トラヒック・バーストを受け取る際に発したトラヒックを引き、更に最大伝送ユニットの大きさに入り口の個数を乗じた結果を足した値に等しい。
【００７５】
なお、上記の実施形態において、線分ＤＨの長さを計算することによって、最大のキュー長さを計算する方法を採用しているが、本発明はこれに限定されない。例えば、線分ＢＣの長さを用いて最大のキュー長さを計算してもよい。数学的にこれを実現することはなんら問題がなく、よって、本発明に適用できるが、上記のように、その計算は複雑になる。また、当業者は、本発明の原理に基づいて、他の計算方法を案出することも困難ではない。上記の実施例は単なる例示に過ぎず、簡潔を期するために、他の計算方法を明示することを省略する。
【００７６】
上記の式により、出力ポートにおけるＥＦトラヒックの最大のキュー長さを得た後、当該ポートにおけるＥＦトラヒックの最大のキュー遅延（queuing  delay）は、最大のキュー長さを当該ポートにけるリンク帯域幅で割って得られる。当該ポートから隣接するノードまでの伝播遅延（propagation  delay）は、その間の物理的距離から計算でき、また、最大伝送遅延（transmission  delay）と処理遅延（processing  delay）は、リンクの速度及びノードの処理能力により計算でき、或いは、高速ネットワークにおいて無視することができる。上記最大のキュー遅延と、最大伝送遅延と、伝播遅延と、処理遅延とを合わせて、当該ポートにおける遅延敏感サービスフローの最大総遅延が得られる。
【００７７】
次に、記憶部４４０に記憶される情報を説明する。
【００７８】
図６は、記憶部４４０に記憶される情報を説明するブロック図である。
【００７９】
図６に示すように、記憶部４４０には、ネットワーク・トポロジー・データベース５１０，利用可能な帯域幅データベース５２０，遅延情報データベース５３０，及びサービスフロー情報データベース５４０が記憶されている。
【００８０】
ネットワーク・トポロジー・データベース５１０に、ネットワーク・トポロジー情報、ノード間の物理的距離及びリンク帯域幅の情報が記憶されている。これらの情報は通常ネットワーク管理システムから取得できる。
【００８１】
利用可能な帯域幅データベース５２０に，各リンク上の各トラヒッククラス（Traffic  Class）の利用可能な帯域幅（DiffServサービスモデルに、各リンク上に各トラヒッククラスのために、異なる帯域幅が確保されている）。
【００８２】
遅延情報データベース５３０に，各ノードの各ポートにおける遅延敏感サービスフローの最大のキュー長さと到着する最大トラヒック・バーストが記憶されている。遅延情報データベース５３０は、遅延予測装置により更新される。
【００８３】
サービスフロー情報データベース５４０に，各サービスフロー（既存のサービスフロー、及びユーザが既に申し入れており、なお開始されていないサービスフローを含む）の情報が記憶されている。例えば、サービスフローの経路、必要な帯域幅、要求される遅延保証値などの情報がある。利用可能な帯域幅データベース５２０とサービスフロー情報データベース５４０は、ＱｏＳ制御装置３００により更新される。
【００８４】
次に、本実施形態による遅延予測を行う装置を説明する。
【００８５】
図７は、ネットワークにおける各ノードの記録を例示する表である。
【００８６】
遅延予測を行う際に、ＱｏＳ制御装置３００は、記憶部４４０における遅延情報データベース５３０にネットワークにおける各ノードについて独立な記録を作る。図７はこのようなノードの記録を例示する。
【００８７】
各記録は、以下のような情報が含まれる。１）ノードの各ポートのリンク帯域幅、２）隣接するノード間の物理的距離、３）各ポートに到着するＥＦトラヒック・バーストの最大値、即ち、Ｑｈｍａｘ，ｊ、４）各ポートにキューイングするＥＦトラヒックの最大キュー長さ、即ち、ＱＪｍａｘ。
【００８８】
遅延予測装置３１０は、新しい遅延敏感サービスフローをネットワークに受け入れる時に、上記数式８，９，１０に基づいて、データベースに記憶されている当該サービスフローの経路上のノードにおけるＱｈｍａｘ，ｊ及びＱＪｍａｘを更新する。予測を行う場合、遅延予測装置３１０は、指定されたノードの記録を取り出し、記録に書き込まれるＱＪｍａｘ、リンク帯域幅、及び次のホップとの物理的距離に基づいて、指定されたポートの最大総遅延を計算する。
【００８９】
図８は、本実施形態におけるＱｏＳ制御装置３００の構成を示すブロック図である。
【００９０】
図８に示すように、ＱｏＳ制御装置３００は、サービスフロー経路選択ユニット３２５と、遅延ルート決定ユニット３３５と，遅延保証受付制御ユニット３４５とを含む。
【００９１】
ＱｏＳ制御装置３００は、遅延予測装置３１０から提供される遅延予測値に基づいて、本実施形態に係るＱｏＳ制御（即ち、遅延保証）を行う。サービスフロー経路選択ユニット３２５と、遅延ルート決定ユニット３３５と，遅延保証受付制御ユニット３４５とは、互いに独立し、各々は、遅延予測装置３１０から提供される遅延予測値を入力として独立して動作する。
【００９２】
サービスフロー経路選択ユニット３２５は、ＱｏＳ制御装置３００におけるＱｏＳ制御ユニット（図示されていない）により提供される明示的なルート（explicit  route）により、当該ルートにおける遅延敏感サービスの最大エンド・ツー・エンド遅延を計算し、  当該遅延をユーザにより要求された遅延と比較し、当該ルートはユーザが指定したサービスフローを伝送することができるか否かを判断する。ＱｏＳ制御ユニット（図示されていない）は、ＱｏＳルートアルゴリズムを用いて当該明示的なルートを計算する。当該ＱｏＳルートアルゴリズムによる計算は、従来のものを用いても良い。従来技術においてＱｏＳルートアルゴリズムが多くあるので、ここで説明を省略する。
【００９３】
遅延ルート決定ユニット３３５は、本実施形態によるＱｏＳルート決定方法を実行する。本実施形態のＱｏＳルート決定方法において、予測された遅延値をルートの計算に用い、エンド・ツー・エンド遅延がより小さいルートが得られ、これにより、サービス品質及びネットワークのスループットが改善される。
【００９４】
遅延保証受付制御ユニット３４５は、本実施形態による受付制御方法を実行する。本実施形態による受付制御方法は、新しい遅延敏感サービスフローにより既存の遅延敏感サービスフローに与える影響を予測し、当該新しい遅延敏感サービスフローを受け付けるか否かを決定する。
【００９５】
上記したように、サービスフロー経路選択ユニット３２５と、遅延ルート決定ユニット３３５と，遅延保証受付制御ユニット３４５とは、互いに独立して動作する。サービスプロバイダーは自分のネットワーク／トラヒック状況、及びサービス要求に基づき、サービスフロー経路選択ユニット３２５と、遅延ルート決定ユニット３３５と，遅延保証受付制御ユニット３４５とのうち一つ又は複数を起動する。例えば、ネットワークが大規模である場合、又は、数多くのユーザに遅延保証を提供する必要な場合、中央制御サーバー２１０の負荷は高くなる。この場合は、例えば、必要な計算量の最も少ないサービスフロー経路選択ユニット３２５だけを起動すればよい。
【００９６】
しかし、サービスフロー経路選択ユニット３２５だけでは、ユーザに異なる遅延保証を提供することができない、また、ネットワークスループットを最優化することができない。なぜなら、異なる遅延保証を提供するには、遅延保証受付制御ユニット３４５の機能が必要である。また、遅延ルート決定ユニット３３５は、ルート計算において遅延の大きいノードを回避し、ネットワークスループットを最優化することができる。
【００９７】
次に、サービスフロー経路選択ユニット３２５と、遅延ルート決定ユニット３３５と，遅延保証受付制御ユニット３４５とをそれぞれ説明する。
【００９８】
まず、サービスフロー経路選択ユニット３２５によるサービスフロー経路選択動作を説明する。
【００９９】
各ノードでの最大遅延を予測し、それを用いて、所定の経路のエンド・ツー・エンド遅延を以下の式で計算する。
【０１００】
【数１０】
2007104677.tif 000012
ここで、hop_delayiは、遅延予測装置３１０が予測した当該経路の第ｉ番目のホップでの最大遅延である。
【０１０１】
所定の経路のエンド・ツー・エンド遅延は、当該経路が遅延敏感サービスフローに遅延保証を提供することに適しているか否かを判断することに用いられる。予測されたエンド・ツー・エンド遅延はユーザに要求された遅延より小さい場合は、当該経路がサービスフローに遅延保証を提供することができる。この場合は、中央制御サーバー２１０は、当該経路に従ってＬＳＰ（Label  Switched  Path）を立ち上げ、指定されたサービスフローをこのＬＳＰに反映するように、ユーザのサービスフローにおける入力エッジ・ノードに命令を発する。
【０１０２】
逆に、予測されたエンド・ツー・エンド遅延はユーザに要求された遅延より大きい場合は、当該経路がサービスフローに遅延保証を提供することができない。この場合は、中央制御サーバー２１０は、当該ユーザとの合意又はサービス戦略に従って、新たなルートを検索する、または、ユーザの遅延保証要求を拒否する。
【０１０３】
図９は、サービスフロー経路選択ユニット３２５の構成を例示するブロック図である。
【０１０４】
図９に示すように、サービスフロー経路選択ユニット３２５は、経路総遅延決定部６１０と、比較部６１２とを含む。
【０１０５】
サービスフロー経路選択ユニット３２５は、ＱｏＳ制御装置３００からルートを取得し、当該ルートに従って、遅延予測装置３１０から各ノードでの遅延予測値を取得し、経路総遅延決定部６１０は、これら遅延予測値を足して、エンド・ツー・エンド遅延の予測値を得て、比較部６１２に提供する。比較部６１２は、予測されたエンド・ツー・エンド遅延をユーザに要求された遅延と比較する。予測されたエンド・ツー・エンド遅延はユーザに要求された遅延より小さい場合は、当該経路がサービスフローに遅延保証を提供することができる。この場合は、中央制御サーバー２１０は、当該経路に従ってＬＳＰ（Label  Switched  Path）を立ち上げ、指定されたサービスフローをこのＬＳＰに反映するように、ユーザのサービスフローにおける入力エッジ・ノードに命令を発する。
【０１０６】
逆に、予測されたエンド・ツー・エンド遅延はユーザに要求された遅延より大きい場合は、当該経路がサービスフローに遅延保証を提供することができない。この場合は、中央制御サーバー２１０は、当該ユーザとの合意又はサービス戦略に従って、新たなルートを検索する、または、ユーザの遅延保証要求を拒否する。
【０１０７】
次に、遅延ルート決定ユニット３３５による遅延保証ＱｏＳルート決定動作を説明する。
【０１０８】
通常のルート決定動作において遅延の情報は考慮されない。上記のエンド・ツー・エンド・サービスフロー経路選択方法は、ルート計算後に遅延を予測又はチェックすることができるものの、このような「事後チェック」は効率が低い問題がある。即ち、計算後に、ある経路の遅延はユーザに要求された遅延より大きい場合は、新たなルートを探さなければならない。しかし、その新たなルートも遅延が大きい可能性があり、また、ネットワークに遅延の非常に大きいノードが存在する場合は、適切なルート選択は困難になる。
【０１０９】
よって、本実施形態において、遅延保証ＱｏＳルート決定方法を提案する。当該遅延保証ＱｏＳルート決定方法によりルートを計算する際に、遅延予測装置３１０から提供される遅延情報が使用される。
【０１１０】
例えば、本実施形態の遅延保証ＱｏＳルート決定方法において、まず、リンクコストを計算し、そして、各リンクのリンクコストを比較し、リンクコストの最も小さいリンクを特定する。ここでリンクコストについて説明する。リンクコストは一種のパラメータであり、各リンクはユーザにより定義されたコストを有し、ルート検索際に、リンクの優先度を示す。リンクコストは帯域幅コストや、遅延コストなどを含み、それぞれ、帯域幅や遅延を基準とする場合の優先度を表す。
【０１１１】
従来技術において、最小のリンクコストを有するリンクが複数ある場合は、ランダムにリンクを選択することになっている。本実施形態には、最小のリンクコストを有するリンクが複数ある場合は、遅延コストに基づいてルートを選択する。また、現在のノードと隣接するノードとの間の「累積遅延」が所定の閾値を超えると、当該隣接するノードを経路から除去し、即ち、当該ノードを含まない経路のみを選択する。
【０１１２】
以下、最短最小ルーティング（Shortest-Minimal-Routing）を例として、本実施形態の遅延ルート決定方法を説明する。
【０１１３】
最短最小ルーティング・アルゴリズムの基本原理は、Dijkstraアルゴリズムの一つの変形である。具体的に、遅延予測装置３１０から提供される遅延情報は新たなパラメータ（ノードの一つの特性）としてDijkstraアルゴリズムに導入された。このパラメータは「累積遅延」と称し、入力エッジ・ノードから現在のノード（最後のホップ）に隣接する複数のノードまでの遅延の総和である。累積遅延は、Dijkstraアルゴリズムにおける各サイクルにおいて、入力エッジ・ノードから現在のノードに隣接する各ノードまでの遅延を記録し、これら遅延は遅延予測装置３１０から提供される遅延情報に基づいて計算される。
【０１１４】
ここで、Dijkstraアルゴリズムについて簡単に説明する。Dijkstraアルゴリズムにおいて、入力ノードからその他の全ての接続されているノードを亘って計算を行い、コストの最も低いノードを選択し、「現在のノード」とする。そして、この現在のノードからその他の全ての接続されているノードを亘って計算を行う。
【０１１５】
現在のノードから複数の隣接するノードまでのリンクコストが同一である場合は、累積遅延が最小となるノードは選択され、経路に加えられる。
【０１１６】
図１０は、最短最小遅延（Shortest-Minimal-Delay）ルート決定方法を例示する図である。
【０１１７】
図１０に示す例には、本実施形態のルート決定方法によりノードＡからノードＣまでの経路が計算される。ノードＡと隣接するノードが２つある、即ち、ノードＢとノードＤである。また、ノードＢとノードＤのコストが同じである。そこで、累積遅延を用いてどちらのノードを選択して経路に加えるかを決める。図１０に示す例には、ノードＡからノードＢまでの累積遅延は２０ｍｓで、ノードＡからノードＤまでの累積遅延は１０ｍｓであるので、ノードＤが選択され、経路に加えられる。
【０１１８】
即ち、最短最小遅延ルート決定方法は、複数のリンクコストが同一の経路から、遅延が最小となる経路を選択することができる。また、必要に応じて、遅延が大きくボトルネックとなるノードを除去する処理は計算上容易に実現できる。そのため、各サイクルにおいて、「現在ノード」から各隣接するノードまで累積遅延を要求された遅延と比較する必要がある。
【０１１９】
図１１は最短最小遅延（Shortest-Minimal-Delay）ルート決定動作において、遅延の大きいノードを除去する処理を例示する図である。
【０１２０】
図１１に示す例に、要求された遅延は２０ｍｓであり、ノードＡからノードＤの累積遅延は３０ｍｓであるので、ルートを計算する際に、ノードＤが除去され、ノードＢは、そのコストがノードＤのコストより大きいにも拘わらず、唯一の候補となる。
【０１２１】
また、図１１に示すネットワークを例にすると、もし要求された遅延は５ｍｓであれば、ノードＢとノードＤが共に除去される。この場合、ルートの計算は直ちに中止し、無駄な計算負担は発生しない。
【０１２２】
以上の例から分かるように、最短最小遅延アルゴリズムにおいて、ボトルネックとなるノードを除去した場合、計算によりあるルートが出力されると、このルートは必ず遅延要求に満たした経路である。
【０１２３】
なお、遅延予測装置３１０から提供される遅延情報に基づいて遅延保証ＱｏＳルート決定は、様々な方式で実現することができる。例えば、遅延コストを直接リンクコストとして用いてもいい。
【０１２４】
本実施形態において、予測された遅延情報は、ルートの計算に使用され、遅延がより小さい経路が検出される。その結果、ネットワークのサービス品質が改善され、より多くの遅延要求を満たしている経路を検出することができ、これによりネットワークのスループットが向上される。
【０１２５】
図１２は、遅延ルート決定ユニット３３５の構成を例示するブロック図である。
【０１２６】
図１２に示すように、遅延ルート決定ユニット３３５は、コスト決定部６１４と、累積遅延計算部６１６，経路決定部６１８，及び比較部６２０を含む。
【０１２７】
コスト決定部６１４は、データベースからネットワーク・トポロジーを読み出し、入力ノードからその他の全てのノードを亘って計算を行い、コストの最も低いノードを選択し、経路決定部６１８に出力する。
同時に、このサイクルにおいて、累積遅延計算部６１６は、遅延予測装置３１０から提供される各ノードの遅延に基づいて、入力ノードから現在ノードに接続されているノードまでの累積遅延を計算し、経路決定部６１８に出力する。
【０１２８】
コスト決定部６１４が一つのノードしか提供していない場合は、経路決定部６１８は当該ノードを次の現在ノード（次のホップ）とする。コスト決定部６１４が複数の同一コストのノードを提供した場合、経路決定部６１８は、これらノードのうち、最小の累積遅延を有するノードを次の現在ノード（次のホップ）とする。  
経路決定部６１８は、選出された新しい現在ノードをコスト決定部６１４に伝送し、次の計算サイクルの起点とする。
【０１２９】
遅延が大きくボトルネックとなるノードを除去する処理は必要である時に、比較部６２０が動作し、計算を行う。具体的に、累積遅延計算部６１６は各候補ノードの累積遅延を比較部６２０に提供する。比較部６２０がこれら累積遅延を要求された遅延と比較し、要求された遅延より大きい累積遅延が発見される場合、比較部６２０は、対応ボトルネックノードをコスト計算に考慮しないようにコスト決定部６１４に通知する。
【０１３０】
次に、本実施形態における遅延保証受付制御ユニット３４５による遅延保証受付制御動作を説明する。
【０１３１】
DiffServサービスモデルにより遅延保証を提供する場合に、一つの問題点は、サービスフローの遅延は一定ではない。新しい遅延敏感サービスフローをネットワークに受け入れることにより、サービスフロー経路におけるノードでのキューイング時間が増加する恐れがある。
【０１３２】
また、これらのノードに他のサービスフローが既に存在する場合は、その他のサービスフローの遅延が増加する恐れがある。従って、ネットワーク／サービスプロバイダーは、異なるユーザまたは異なるサービスに異なる遅延を与えることを実現するために、新しいサービスフローを受け入れることにより、既存の遅延保証を損なわないことを保証できる新しい技術が必要である。本実施形態は、このような技術を提供する。
【０１３３】
本実施形態における遅延保証受付制御は、遅延予測装置３１０から提供される遅延情報に基づいて行われる。
【０１３４】
図１３は、本実施形態における遅延保証受付制御を説明するフローチャートである。
【０１３５】
ステップ８０１において、ルート検索と行い、新しい遅延敏感サービスフローのために、所定の条件を満たしている経路を検索する。例えば、ＱｏＳルート検索とエンド・ツー・エンド遅延検索を併用し、又は、最短最小遅延ルーティングを用いる。
【０１３６】
このような経路が存在しない場合は、当該サービスフローへの要求を直接拒否する。そうでなければ、選択される経路上のノードの遅延情報が更新され、処理がステップ８０２に進む。
【０１３７】
ステップ８０２において、ノード遅延増加判断手段（図示されていない）は、当該ノードでの遅延は新しいサービスフローの受け入れにより増加するか否かを判断する。更新された場合は、新しい値と古い値とを比較する。もし新しい予測値は古い予測値より大きい場合は、当該ノードでの遅延は新しいサービスフローの受け入れにより増加すると判断する。即ち、新しいサービスフローの受け入れは、既存のサービスフローに影響する。
【０１３８】
もし新しい予測値は古い予測値より以下の場合は、当該ノードでの遅延は新しいサービスフローの受け入れにより増加しないと判断する。即ち、新しいサービスフローの受け入れは既存のサービスフローに影響しない。
【０１３９】
新しいサービスフローの受け入れは既存のサービスフローに影響すると判断される場合は、処理がステップ８０３に進む。
【０１４０】
ステップ８０３において、遅延敏感サービスフロー存在判断手段（図示されていない）は、遅延が増加するノードに、遅延敏感サービスフローが既に存在するか否かを判断する。
【０１４１】
遅延敏感サービスフローが既に存在すると判断する場合は、これらのサービスフローのエンド・ツー・エンド遅延が再度計算される。当該計算において、更新された遅延情報が用いられる。この時、データベースにおける遅延情報が既に更新されているので、対応サービスフローの経路上のノードの遅延情報を取り出して足せばよい。
【０１４２】
ステップ８０４において、新しいサービスフローの受け入れは既存のサービスフローの遅延保証を損なうか否かを判断する。
【０１４３】
具体的に、既存サービスフローの新しいエンド・ツー・エンド遅延と要求された遅延とを比較される。一つ或いは複数の既存サービスフローの新しいエンド・ツー・エンド遅延が要求された遅延より大きい場合は、新しいサービスフローの受け入れは既存のサービスフローの遅延保証を損なう可能性があると判断される。この場合は、処理がステップ８０５に進む。
【０１４４】
一方、既存サービスフローの新しいエンド・ツー・エンド遅延と要求された遅延とを比較した結果、全ての既存サービスフローの新しいエンド・ツー・エンド遅延が要求された遅延より小さい場合は、新しいサービスフローの受け入れは既存のサービスフローの遅延保証を損なわないと判断される。この場合は、処理がステップ８０６に進む。
【０１４５】
ステップ８０５において、新しいサービスフローの受け入れは既存のサービスフローの遅延保証を損なうと判断されたことを受けて、ユーザとの合意又はネットワーク運用戦略に従って、その新しいサービスフローに新たなルートを検索する、または、ユーザの遅延保証要求を拒否する。
【０１４６】
なお、新たなルートを検索する際に、図１３に示す処理フローを再度実行される。
【０１４７】
ステップ８０６において、新しいサービスフローの受け入れは既存のサービスフローの遅延保証を損なわないと判断されたので、受付要求を受け入れ、新しいサービスフローをネットワークに受け入れる。
【０１４８】
なお、ステップ８０４，ステップ８０５，ステップ８０６は遅延保証受付制御装置により実行されるとしてもよい。
【０１４９】
従来の遅延予測方法と比べれば、本発明は少なくとも以下の利点を有する。
１）．本発明は最大注入可能なトラヒックを用いて最大のキュー長さを予測する。本発明は高い優先レベルのトラヒックのバースト特性及び相互間の競合を考慮しているので、従来技術においてDiffServサービスモデルに高い優先レベルのトラヒックのキュー遅延（queuing  delay）を単純に無視する方法と比べ、本発明により得られた予測値がより有効である。
２）．本発明において、各ノードにおけるトラヒックの最大遅延は、各ノードの具体的な状況（たとえば、ネットワーク・トポロジー、ノード位置、入力／出力帯域幅）に基づいて予測されるので、従来技術においてバッファーサイズ、又は、任意のトポロジーに基づいて行われる「最悪状況」（worst-case）の予測と比べ、本発明により得られた予測値がより正確である。
３）．本発明を利用して予測を行う場合は、受け付ける遅延敏感サービスフローのトラヒックとネットワーク・トポロジーとをしか必要としない、また、この２つの情報はネットワーク管理システムから簡単に得られる。従来技術においてわざわざネットワークからデータを収集して予測する方法と比べ、本発明はネットワークに余計な負荷を掛けず、また、計算負荷も低い。
【０１５０】
以上、本発明の好ましい実施形態を説明したが、本発明はこれらの実施形態に限定されず、本発明の趣旨を離脱しない限り、本発明に対するあらゆる変更は本発明の範囲に属する。
【０１５１】
本発明は、更に以下の付記を含む。
【０１５２】
（付記１）
サービスフローの経路の各ホップにおける当該サービスフローの遅延を予測する遅延予測方法であって、
前記各ホップにおける最大のキュー長さを求める第１の工程と、
求められた前記各ホップにおける最大のキュー長さに基づき、前記各ホップにおけるそれぞれの最大のキュー遅延を予測する第２の工程と
を含む遅延予測方法。
【０１５３】
（付記２）
前記第１の工程において、前記各ホップにおける最大のキュー長さを逐次に求める
付記１に記載の遅延予測方法。
【０１５４】
（付記３）
前記第１の工程は、
ネットワーク入り口において、トラヒック・シェーピング・パラメータに基づき、前記入り口における前記最大のキュー長さを求める第３の工程と、
前記ネットワーク入り口以外の各ホップにおいて、所定のホップに到着可能な最大トラヒック・バースト、トラヒックが到着するポートにおける速度、及びトラヒックが送り出されるポートにおける速度に基づき、前記入り口以外の各ホップにおけるそれぞれの最大のキュー長さを求める第４の工程と
を含み、
前記所定のホップに到着可能な最大トラヒック・バーストは、当該所定のホップにおける全ての上流ホップの最大のキュー長さのうちの最大値である
付記２に記載の遅延予測方法。
【０１５５】
（付記４）
前記第４の工程において、
前記所定のホップの出口における帯域幅は、トラヒックが当該所定のホップに到着可能な全ての入り口における帯域幅の総和より以上である場合は、当該出口における最大のキュー長さは、最大伝送ユニットの大きさに前記入り口の個数を乗じた値に等しく、
前記所定のホップの出口における帯域幅は、トラヒックが当該所定のホップに到着可能な全ての入り口における帯域幅の総和より小さい場合は、当該出口における最大のキュー長さは、前記全ての入り口に到着可能な最大トラヒック・バーストの総和から、当該トラヒック・バーストを受け取る際に発したトラヒックを引き、更に前記最大伝送ユニットの大きさに前記入り口の個数を乗じた結果を足した値に等しい
付記３に記載の遅延予測方法。
【０１５６】
（付記５）
前記第２の工程において、所定のホップにおける最大のキュー長さを当該所定のホップの出口にけるリンク帯域幅で割った値を、前記所定のホップにおける最大のキュー遅延とする
付記１に記載の遅延予測方法。
【０１５７】
（付記６）
さらに、所定のホップにおける最大のキュー遅延と、最大伝送遅延と、伝播遅延と、処理遅延とを合わせて、前記所定のホップにおける総遅延とする工程を有する
付記１に記載の遅延予測方法。
【０１５８】
（付記７）
さらに、
前記求められた各ホップにおける最大のキュー長さを記憶する記憶工程と、
新たらしいサービスフローを加える際に、記憶された前記各ホップにおける最大のキュー長さを更新する更新工程と
を有する
付記１に記載の遅延予測方法。
【０１５９】
（付記８）
サービスフローの経路を選択する方法であって、
前記サービスフローの経路における各ホップの最大のキュー長さから前記各ホップにおける最大のキュー遅延を求め、前記各ホップにおける最大のキュー遅延に基づき、前記経路の総遅延を求める経路総遅延決定工程と、
所望の総遅延より小さい総遅延の経路を選択する経路選択工程と
を含む
サービスフロー経路選択方法。
【０１６０】
（付記９）
サービスフローの遅延要求に基づきサービスフロー経路における次のホップを定めるルート決定方法であって、
前記サービスフロー経路における現在の最後のホップから隣接する複数のノードまでのリンクコストを求めるリンクコスト決定工程と、
前記サービスフロー経路における前記各ホップの最大のキュー長さから前記各ホップにおける最大のキュー遅延を求め、前記各ホップの最大のキュー遅延に基づき、前記現在の最後のホップから前記隣接する複数のノードまでの各ノードの遅延コストを求める遅延コスト決定工程と、
前記複数のリンクコストのうち、最小のリンクコストを有するノードが複数ある場合は、最小の遅延コストを有するノードを次のホップとする工程と
を含む
ルート決定方法。
【０１６１】
（付記１０）
さらに、
前記サービスフロー経路における現在の最後のホップから前記隣接する複数のノードまでの各ノードの累積遅延を求める工程と、
前記各累積遅延を要求された遅延と比較し、前記累積遅延が前記要求された遅延より大きいノードを除去する工程と
を含む
付記９に記載のルート決定方法。
【０１６２】
（付記１１）
サービスフローの遅延要求に基づきサービスフロー経路における次のホップを定めるルート決定方法であって、
前記サービスフロー経路における前記各ホップの最大のキュー長さから前記各ホップにおける最大のキュー遅延を求め、前記各ホップの最大のキュー遅延に基づき、現在の最後のホップから隣接する複数のノードまでの各ノードの遅延コストを求める遅延コスト決定工程と、
最小の遅延コストを有するノードを次のホップとする工程と
を含む
ルート決定方法。
【０１６３】
（付記１２）
さらに、
前記サービスフロー経路における現在の最後のホップから前記隣接する複数のノードまでの各ノードの累積遅延を求める工程と、
前記各累積遅延を要求された遅延と比較し、前記累積遅延が前記要求された遅延より大きいノードを除去する工程と
を含む
付記１１に記載のルート決定方法。
【０１６４】
（付記１３）
新しいサービスの受付制御に用いる遅延保証受付制御方法であって、
新しいサービス経路における各ホップの最大のキュー長さから、前記新しいサービス経路における各ノードの最大のキュー遅延を求め、前記各ノードの最大のキュー遅延に基づき、前記新しいサービスが前記新しいサービス経路における一部のノードでの最大遅延を増大するか否かを判断する工程と、
最大遅延が増大すると判断された前記ノードに、遅延敏感サービスフローが存在するか否かを判断する工程と、
前記ノードにおける遅延敏感サービスフローを損なわない新しいサービスのみを受け付ける工程と
を含む
遅延保証受付制御方法。
【０１６５】
（付記１４）
サービスフローの経路の各ホップにおける当該サービスフローの遅延を予測する遅延予測装置であって、
前記各ホップにおける最大のキュー長さを求めるキュー長さ決定手段と、
求められた前記各ホップにおける最大のキュー長さに基づき、前記各ホップにおけるそれぞれの最大のキュー遅延を予測するキュー遅延決定手段と
を含む遅延予測装置。
【０１６６】
（付記１５）
前記キュー長さ決定手段は、前記各ホップにおける最大のキュー長さを逐次に求める
付記１４に記載の遅延予測装置。
【０１６７】
（付記１６）
前記キュー長さ決定手段は、
ネットワーク入り口において、トラヒック・シェーピング・パラメータに基づき、前記入り口における前記最大のキュー長さを求め、
前記ネットワーク入り口以外の各ホップにおいて、所定のホップに到着可能な最大トラヒック・バースト、トラヒックが到着するポートにおける速度、及びトラヒックが送り出されるポートにおける速度に基づき、前記入り口以外の各ホップにおけるそれぞれの最大のキュー長さを求め、
前記所定のホップに到着可能な最大トラヒック・バーストは、当該所定のホップにおける全ての上流ホップの最大のキュー長さのうちの最大値である
付記１５に記載の遅延予測装置。
【０１６８】
（付記１７）
前記キュー長さ決定手段は、
前記所定のホップの出口における帯域幅は、トラヒックが当該所定のホップに到着可能な全ての入り口における帯域幅の総和より以上である場合は、当該出口における最大のキュー長さとして、最大伝送ユニットの大きさに前記入り口の個数を乗じた値を用い、
前記所定のホップの出口における帯域幅は、トラヒックが当該所定のホップに到着可能な全ての入り口における帯域幅の総和より小さい場合は、当該出口における最大のキュー長さとして、前記全ての入り口に到着可能な最大トラヒック・バーストの総和から、当該トラヒック・バーストを受け取る際に発したトラヒックを引き、更に前記最大伝送ユニットの大きさに前記入り口の個数を乗じた結果を足した値を用いる
付記１６に記載の遅延予測装置。
【０１６９】
（付記１８）
前記キュー遅延決定手段は、所定のホップにおける最大のキュー長さを当該所定のホップの出口にけるリンク帯域幅で割った値を、前記所定のホップにおける最大のキュー遅延として用いる
付記１４に記載の遅延予測装置。
【０１７０】
（付記１９）
さらに、総遅延予測手段を有し、
前記総遅延予測手段は、前記最大のキュー遅延と、最大伝送遅延と、伝播遅延と、処理遅延とを合わせて、前記所定のホップにおける総遅延として用いる
付記１４に記載の遅延予測装置。
【０１７１】
（付記２０）
さらに、
前記求められた各ホップにおける最大のキュー長さを記憶する記憶手段と、
新たらしいサービスフローを加える際に、記憶された前記各ホップにおける最大のキュー長さを更新する更新手段と
を有する
付記１４に記載の遅延予測装置。
【０１７２】
（付記２１）
サービスフローの経路を選択する装置であって、
前記サービスフローの経路における各ホップの最大のキュー長さから前記各ホップにおける最大のキュー遅延を求め、前記各ホップにおける最大のキュー遅延に基づき、前記経路の総遅延を求める経路総遅延決定手段と、
所望の総遅延より小さい総遅延の経路を選択する経路選択手段と
を含む
サービスフロー経路選択装置。
【０１７３】
（付記２２）
サービスフローの遅延要求に基づきサービスフロー経路における次のホップを定めるルート決定装置であって、
前記サービスフロー経路における現在の最後のホップから隣接する複数のノードまでのリンクコストを求めるリンクコスト決定手段と、
前記サービスフロー経路における前記各ホップの最大のキュー長さから前記各ホップにおける最大のキュー遅延を求め、前記各ホップの最大のキュー遅延に基づき、前記現在の最後のホップから前記隣接する複数のノードまでの各ノードの遅延コストを求める遅延コスト決定手段と、
前記複数のリンクコストのうち、最小のリンクコストを有するノードが複数ある場合は、最小の遅延コストを有するノードを次のホップとするホップ決定手段と
を含む
ルート決定装置。
【０１７４】
（付記２３）
さらに、
前記サービスフロー経路における現在の最後のホップから前記隣接する複数のノードまでの各ノードの累積遅延を求める累積遅延決定手段と、
前記各累積遅延を要求された遅延と比較し、前記累積遅延が前記要求された遅延より大きいノードを除去する比較手段と
を含む
付記２２に記載のルート決定装置。
【０１７５】
（付記２４）
サービスフローの遅延要求に基づきサービスフロー経路における次のホップを定めるルート決定装置であって、
前記サービスフロー経路における前記各ホップの最大のキュー長さから前記各ホップにおける最大のキュー遅延を求め、前記各ホップの最大のキュー遅延に基づき、現在の最後のホップから隣接する複数のノードまでの各ノードの遅延コストを求める遅延コスト決定手段と、
最小の遅延コストを有するノードを次のホップとするホップ決定手段と
を含む
ルート決定装置。
【０１７６】
（付記２５）
さらに、
前記サービスフロー経路における現在の最後のホップから前記隣接する複数のノードまでの各ノードの累積遅延を求める累積遅延決定手段と、
前記各累積遅延を要求された遅延と比較し、前記累積遅延が前記要求された遅延より大きいノードを除去する比較手段と
を含む
付記２４に記載のルート決定装置。
【０１７７】
（付記２６）
新しいサービスの受付制御に用いる遅延保証受付制御装置であって、
新しいサービス経路における各ホップの最大のキュー長さから、前記新しいサービス経路における各ノードの最大のキュー遅延を求め、前記各ノードの最大のキュー遅延に基づき、前記新しいサービスが前記新しいサービス経路における一部のノードでの最大遅延を増大するか否かを判断する第１の判断手段と、
最大遅延が増大すると判断された前記ノードに、遅延敏感サービスフローが存在するか否かを判断する第２の判断手段と、
前記ノードにおける遅延敏感サービスフローを損なわない新しいサービスのみを受け付ける受付手段と
を含む
遅延保証受付制御装置。
【０１７８】
（付記２７）
サービスフロー経路における各ホップでのサービスフローの遅延を予測する遅延予測装置と、
前記予測された各ホップにおける遅延に基づき、サービス品質を制御するサービス品質制御装置と
を含み、
前記遅延予測装置は、
前記各ホップにおける最大のキュー長さを求めるキュー長さ決定手段と、
求められた前記各ホップにおける最大のキュー長さに基づき、前記各ホップにおけるそれぞれの最大のキュー遅延を予測するキュー遅延決定手段と
を有する
サービス品質保証システム。
【０１７９】
（付記２８）
前記サービス品質制御装置は、遅延保証受付制御装置、ルート決定装置、及びサービスフロー経路選択装置のうち、少なくとも一つを有し、
前記遅延保証受付制御装置は、新しいサービスの受付制御に用いるものであって、
新しいサービス経路における各ホップの最大のキュー長さから、前記新しいサービス経路における各ノードの最大のキュー遅延を求め、前記各ノードの最大のキュー遅延に基づき、前記新しいサービスが前記新しいサービス経路における一部のノードでの最大遅延を増大するか否かを判断する第１の判断手段と、
最大遅延が増大すると判断された前記ノードに、遅延敏感サービスフローが存在するか否かを判断する第２の判断手段と、
前記ノードにおける遅延敏感サービスフローを損なわない新しいサービスのみを受け付ける受付手段と
を含み、
前記サービスフロー経路選択装置は、サービスフローの経路を選択するものであって、
前記サービスフローの経路における各ホップの最大のキュー長さから前記各ホップにおける最大のキュー遅延を求め、前記各ホップにおける最大のキュー遅延に基づき、前記経路の総遅延を求める経路総遅延決定手段と、
所望の総遅延より小さい総遅延の経路を選択する経路選択手段と
を含む
付記２７に記載のサービス品質保証システム。
【０１８０】
（付記２９）
前記ルート決定装置は、新しいサービスのルートを決定するものであって、
前記サービスフロー経路における現在の最後のホップから隣接する複数のノードまでのリンクコストを求めるリンクコスト決定手段と、
前記サービスフロー経路における前記各ホップの最大のキュー長さから前記各ホップにおける最大のキュー遅延を求め、前記各ホップの最大のキュー遅延に基づき、前記現在の最後のホップから前記隣接する複数のノードまでの各ノードの遅延コストを求める遅延コスト決定手段と、
前記複数のリンクコストのうち、最小のリンクコストを有するノードが複数ある場合は、最小の遅延コストを有するノードを次のホップとするホップ決定手段と
を含む
付記２８に記載のサービス品質保証システム。
【０１８１】
（付記３０）
前記ルート決定装置は、サービスフローの遅延要求に基づきサービスフロー経路における次のホップを定めるものであって、
前記サービスフロー経路における現在の最後のホップから隣接する複数のノードまでのリンクコストを求めるリンクコスト決定手段と、
最小の遅延コストを有するノードを次のホップとするホップ決定手段と
を含む
付記２８に記載のサービス品質保証システム。
【０１８２】
（付記３１）
さらに、
前記サービスフロー経路における現在の最後のホップから前記隣接する複数のノードまでの各ノードの累積遅延を求める累積遅延決定手段と、
前記各累積遅延を要求された遅延と比較し、前記累積遅延が前記要求された遅延より大きいノードを除去する比較手段と
を含む
付記２９又は３０に記載のサービス品質保証システム。
【０１８３】
（付記３２）
前記キュー長さ決定手段は、
ネットワーク入り口において、トラヒック・シェーピング・パラメータに基づき、前記入り口における前記最大のキュー長さを求め、
前記ネットワーク入り口以外の各ホップにおいて、所定のホップに到着可能な最大トラヒック・バースト、トラヒックが到着するポートにおける速度、及びトラヒックが送り出されるポートにおける速度に基づき、前記入り口以外の各ホップにおけるそれぞれの最大のキュー長さを求め、
前記所定のホップに到着可能な最大トラヒック・バーストは、当該所定のホップにおける全ての上流ホップの最大のキュー長さのうちの最大値である
付記３１に記載のサービス品質保証システム。
【０１８４】
（付記３３）
前記キュー長さ決定手段は、
前記所定のホップの出口における帯域幅は、トラヒックが当該所定のホップに到着可能な全ての入り口における帯域幅の総和より以上である場合は、当該出口における最大のキュー長さとして、最大伝送ユニットの大きさに前記入り口の個数を乗じた値を用い、
前記所定のホップの出口における帯域幅は、トラヒックが当該所定のホップに到着可能な全ての入り口における帯域幅の総和より小さい場合は、当該出口における最大のキュー長さとして、前記全ての入り口に到着可能な最大トラヒック・バーストの総和から、当該トラヒック・バーストを受け取る際に発したトラヒックを引き、更に前記最大伝送ユニットの大きさに前記入り口の個数を乗じた結果を足した値を用いる
付記３２に記載のサービス品質保証システム。
【０１８５】
（付記３４）
前記キュー長さ決定手段は、以下の式（１）により、所定の経路における前記各ホップの最大のキュー長さＱＪｍａｘを求める
【０１８６】
【数１１】
2007104677.tif 000013
ここで、ｋは既存のエッジ・ノードから入力された遅延敏感サービスフローの個数を示し、
ｂｉは第ｉ番目のサービスフローのバースト・トラヒックの大きさを示し、
Ｑｈｍａｘ，ｊは第ｈ番目の入力ポートから到着するＥＦトラヒックのバーストの最大値を示し、
Ｃｈ,ｊは入力ポートのリンク帯域幅を示し、
Ｃｊ＋１は出力ポートのリンク帯域幅を示し、
ｍはＥＦトラヒックの入力ポートの個数を示し、
ＭＴＵは最大伝送ユニットのサイズを示す
付記２７に記載のサービス品質保証システム。
【図面の簡単な説明】
【０１８７】
【図１】本発明の実施の形態を応用したシステムを示すブロック図である。
【図２】図１に示すシステムを応用したネットワークを示す概略図である。
【図３】本実施の形態に係る遅延予測装置を示すブロック図である。
【図４】ＥＦトラヒックの出力ポートのリンク帯域幅は、その入力ポートのリンク帯域幅の総和より以上である場合、ＥＦトラヒックのキュー最大値を導出する方法を説明する図である。
【図５】条件ΣＣｉｎ≦Ｃｏｕｔを満たしていないときもある場合の状況を示す。
【図６】記憶部４４０に記憶される情報を説明するブロック図である。
【図７】ネットワークにおける各ノードの記録を例示する表である。
【図８】本実施形態におけるＱｏＳ制御装置３００の構成を示すブロック図である。
【図９】サービスフロー経路選択ユニット３２５の構成を例示するブロック図である。
【図１０】最短最小遅延ルート決定方法を例示する図である。
【図１１】最短最小遅延ルート決定動作において、遅延の大きいノードを除去する処理を例示する図である。
【図１２】遅延ルート決定ユニット３３５の構成を例示するブロック図である。
【図１３】本実施形態における遅延保証受付制御を説明するフローチャートである。
【符号の説明】
【０１８８】
１１０  管理層
１２０  制御層
１２６  記憶装置
１２８  ＱｏＳ命令ユニット
１３０  データ層
２００  システム
２１０  中央制御サーバー
２２０  中央管理サーバー
２３０Ａ１〜２３０ＡＮ  ルーター
３００  ＱｏＳ制御装置
３１０  遅延予測装置
３２５  サービスフロー経路選択ユニット
３３５  遅延ルート決定ユニット
３４５  遅延保証受付制御ユニット
４１０  計算部
４２０  更新部
４４０  記憶部
４５０  予測計算部
５１０  ネットワーク・トポロジー・データベース
５２０  利用可能な帯域幅データベース
５３０  遅延情報データベース
５４０  サービスフロー情報データベース
６１０  経路総遅延決定部
６１２  比較部
６１４  コスト決定部
６１６  累積遅延計算部
６１８  経路決定部
６２０  比較部
【図１】
2007104677.tif 000014
【図２】
2007104677.tif 000015
【図３】
2007104677.tif 000016
【図４】
2007104677.tif 000017
【図５】
2007104677.tif 000018
【図６】
2007104677.tif 000019
【図７】
2007104677.tif 000020
【図８】
2007104677.tif 000021
【図９】
2007104677.tif 000022
【図１０】
2007104677.tif 000023
【図１１】
2007104677.tif 000024
【図１２】
2007104677.tif 000025
【図１３】
2007104677.tif 000026