ネットワーク監視
ノードを通るフローの過度要求の基準を決定し、前記過度要求の基準を、実質的に同様の経路状態を経験する準拠するフローの期待される過度要求に依存し、許容できる過度要求を示す基準と比較し、前記過度要求が前記許容できる過度要求に従うものでない場合に、考えられる処分に対して前記フローを指定することによって、データネットワーク内のフローを監視する方法及び装置。このような方法及び装置はデータネットワークの監視を可能にし、エンドツーエンド経路の特徴付け及び／又は前記データパケットの下流経路に関する情報を搬送するデータパケット内の１つ以上のフィールドが前記データネットワークを監視するために使用される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、主にネットワーク内でのデータの制御に関し、及びデータを通信するためのインターネット等のネットワークの使用の監視を可能にする方法及びシステムに関する。
【背景技術】
【０００２】
ネットワーク輻輳に対する責任ある反応の重要性
現在のインターネットアーキテクチャは、しばしば、ホストが自発的に輻輳に対応するよう信頼すること、つまり、一般的に、これらのアルゴリズムが出現する相互信頼の環境のせいにされる過失について批判される。反応しないアプリケーションは、事実上、該アプリケーションが反応のよい流れから、必要とされるボトルネックリソースのどのような割当てをも盗んでいる可能性がある。現在の送信元の大多数はうまく機能していると考えられているが、ただ乗り行為はただ単に不愉快なだけではない。最も人騒がせなことには、現在の協力的なコンセンサスを何が安定させているのかを理解しないまま、無意識に該コンセンサスを不安定にし、戻る道がない輻輳の崩壊を引き起こす可能性がある。しかしながら、反応しないアプリケーションは平均的な帯域幅ごとに、さらに多くの容量の投資を必要とするため、より多くの漸次的な腐食がインターネットの実行可能性を脅かしている。適切に輻輳を管理する、新しいサービスの質を有する（「ＱｏＳ」）製品は、誰もが、必要とされる投資に貢献することなく、どのようにかして必要とするものを取ることができる場合には決して実行可能にはならない。しかしながら、これらの新しいサービスに対する投資はリスクが大きすぎ、なおさらに正常に動作していない（ｍｉｓｂｅｈａｖｉｎｇ）アプリケーションにとってのギャップを生じさせる。したがって、良く動作するアプリケーションは、過少投資と不良行為の悪循環に陥るだろう。
【発明の開示】
【０００３】
反応が鈍い必要のあるアプリケーションもある（双方向音声、ビデオ及びゲーム）。他のアプリケーションは単に自らにプレミアムサービスを提供するために積極的であることを選択する。また、意図的に（ピアツーピアのファイル共有により）、あるいは無意識に（ウィルスに感染しているゾンビホスト）のいずれであるかに関わらず、他のユーザよりも多くのフローで自分のアクセスリンクを継続的に満たすユーザもいる。たとえ各フローの反応がよくても、全体ではさらに多くの輻輳が生じる。
【０００４】
速度適応ポリシーの特徴付け
ＴＣＰ速度制御アルゴリズム［７］は、インターネット上での主要な輻輳の崩壊に応えて１９８０年代後半に開発された。該アルゴリズムは、インターネットを横切るあらゆるフローの速度が、各フローが任意の輻輳したルータ又はリンクの容量を公平に共有する速度に近づくように、該フローが経験した輻輳のレベルに迅速に適応されることを確実にするよう設計された。
【０００５】
ＴＣＰ速度制御アルゴリズムは、送信側ホストのオペレーティングシステム内で実行される。アプリケーションのプログラマは該アルゴリズムを使用するかどうかを選ぶことができる。双方向音声アプリケーション又はビデオアプリケーション等のビットレートの急激な変化に耐えることができないアプリケーションのプログラマはつねに該アルゴリズムを使用しないことを選ぶ。
【０００６】
もともと、ＴＣＰアルゴリズムは、紛失した肯定応答を通して損失を検出することによって、及び肯定応答が到着する前の往復遅延を測定することによって、インターネット全体で使用されている経路を特徴付けていた。最近では、ＴＣＰ／ＩＰ規格は、明示的輻輳通知（ＥＣＮ）をオプションで追加することにより改善され、これにより、初期の輻輳の兆しを経験するルータは、送信する前にパケットにマークを付けることができるであろう。また肯定応答プロトコルは、これらのマークを送信元まで伝達し戻すことを可能にするよう変更された。ＴＣＰアルゴリズムのための規格は、送信側ホストがこれらの返されるマークに、あたかも損失があったかのように応答することを必要とするように改変された。
【０００７】
多くの他の内、Ｐａｄｈｙｅら［１］は、特にＴＣＰフレンドリ速度制御（ＴＦＲＣ、より円滑な適応だけによる、ＴＣＰのウィンドウベースの機構の速度ベースのバージョン）の速度調整のための指針として使用される、定常状態にあるＴＣＰフローの長期平均に対する公式を発展させた［２］。輻輳が小さいまま（ｍ＜＜０．２）であれば、この値は方程式（１）に示されるように、平方根法に近似することが可能である。
【数１】
【０００８】
ここで、ｘはスループットの期待値であり、ｋは√（３／２）のオーダーの定数であり、ｓはフローのパケットサイズであり、Ｔはこのフローの往復時間であり、ｍは（フロー内でマークを付けられ、削除されたパケットの割合によって表されるような）エンドツーエンド輻輳測定基準である。
【０００９】
同時に起こるフローの間で、輻輳ネットワークリソースを割り当てるための他のモデルが存在する。例えば、Ｃｒｏｗｃｒｏｆｔ及びＯｅｃｈｓｌｉｎ［６］は、ω個の平行ＴＣＰフローを模倣するであろう重みパラメータωを用いてＭｕｌＴＣＰと呼ばれるＴＣＰのバージョンを作成することによって、他より多くの容量を使用することがどれほど容易であるのかを示した。Ｋｅｌｌｙら［３］は、インターネットユーザが該ユーザが生成するトラフィックに対する自らの支払い意志を明示する、ネットワークの活用の経済的な最適化に基づいて速度制御アルゴリズムを開発した。ユーザは、交換されるデータ量に関わりなくデータ転送の過程で一定の支出レートを保持するために、速度適応ポリシーを効果的に採用する。データ経路の輻輳ステータスは、転送持続時間を動的に縮小したり、引き伸ばしたりする。このようなポリシーは方程式（２）に示されるスループット方程式によって特徴付けられており、
【数２】
【００１０】
ここで、ｗはユーザの支払い意志パラメータであり、ｘ、ｍ及びｓは上記と同じ意味を有する。
【００１１】
これらの速度制御アルゴリズムのすべては、伝送が伝達される経路の測定基準に依存している。どのような測定基準であれ、該測定基準を特徴付けるための現在の構成は、損失、明示的な輻輳、あるいは往復遅延があるのかどうかに関係なく、受信機と送信機の両者が、該受信機と送信機が通信できる速度を制限することを目的としたプロトコルに誠実に準拠していることに依存している。経路全体の輻輳は、バックチャネルで受信機から送信機に送り返される送信先だけで出現する。しかしながら、どのようなデータネットワークでも、バックチャネルは、本来エンドポイント間の通信であるため、該バックチャネルは中継器に可視である必要はない（該バックチャネルは暗号化されるか、あるいは非対称でルート付けられることができ、あるいは完全に省略されることができる）。したがって、どのネットワーク要素も確実にそれらを傍受することはできない。本出願人による以前の特許出願は、後にＳｉｒｉｓ［８］によって発表された論文に説明されているセルラー無線ネットワークコントローラで具現化された、送信機に送り返される肯定応答を傍受するネットワーク装置上で実行される速度制御機構に関していた（ＷＯ第０３／０４９３１９号を参照すること）。しかしながら、このような機構は、究極的には、受信機が、自らのフィードバックを見えるようにし、該フィードバック中で経路特性を誠実に述べることに依存している。それでも、経路輻輳及び遅延に応えて正しくその速度を変更するためには、送信機にも頼らなければならない。
【００１２】
［１］Ｊ．Ｐａｄｈｙｅ、Ｖ．Ｆｉｒｏｉｕ、Ｄ．Ｔｏｗｓｌｅｙ及びＪ．Ｋｕｒｏｓｅ、「ＴＣＰスループットのモデル化：単純なモデル及びその実験検証（Modeling TCP Throughput:A Simple Model and its Empirical Validation）」、会議録ＡＣＭ ＳＩＧＣＯＭＭ１９９８年
［２］Ｓ．Ｆｌｏｙｄ、Ｍ．Ｈａｎｄｌｅｙ、Ｊ．Ｐａｄｈｙｅ及びＪ．Ｗｉｄｍｅｒ、「ユニキャストアプリケーションのための方程式ベースの輻輳制御（Equation-Based Congestion Control for Unicast Applications）」、会議録、ＡＣＭ ＳＩＧＣＯＭＭ．２０００年８月
［３］Ｆ．Ｐ．Ｋｅｌｌｙ、Ａ．Ｋ．Ｍａｕｌｌｏｏ、及びＤ．Ｋ．Ｈ．Ｔａｎ、「通信ネットワークのための速度制御：潜在価格、比例する公平性と安定性（Rate control for communication networks: shadow prices,proportional fairness and stability）」、オペレーションリサーチ学会誌（Journal of the Operational Research Society）、４９（３）：２３７−２５２ページ、１９９８年
［６］Ｊｏｎ Ｃｒｏｗｃｒｏｆｔ及びＰｈｉｌｉｐｐｅ Ｏｅｃｈｓｌｉｎ、「加重比例公平共有ＴＣＰを使用する差動式エンドツーエンドインターネットサービス（Differentiated End to End Internet Services using a Weighted Proportional Fair Sharing TCP）」、コンピュータ通信レビュー（Computer Communication Review）２８、５３から６９ページ（１９９８年７月）
［７］Ｖａｎ Ｊａｃｏｂｓｅｎ、輻輳回避及び制御（Congestion avoidance and control）、会議録、ＡＣＭ ＳＩＧＣＯＭＭ１９８８年、コンピュータ通信レビュー（Computer Communication Review）１８（４）：３１４−３２９ページ、１９８８年
［８］Ｖａｓｉｌｉｏｓ Ａ．Ｓｉｒｉｓ、ＣＤＭＡネットワークにおける弾性トラフィックのためのリソース制御（Resource control for elastic traffic in CDMA networks）、会議録、モバイルコンピューティング及びネットワークに関するＡＣＭ国際会議（ACM International Conference on Mobile Computing and Networks）、（ＭｏｂｉＣｏｍ２００２年）、ＵＲＬ：http://www.ics.forth.gr/netlab//wireless.html、２００２年９月、ＡＣＭ
速度監視
現在のインターネットでは、万一送信機がＴＣＰ規格で指定されている反応機構に準拠するのをやめた場合には、インターネット上で大混乱を引き起こすであろう。これが、ユーザがネットワーク上でトラフィックの任意の速度を送信する自らの能力を乱用しないようにフローを監視するための複数の提案が作成されている理由である。
【００１３】
前述されたように、インターネットのネットワーク要素は現在では、送信機がＴＣＰプロトコルに準拠していることを検証するために、経路についての関連する測定基準を知ることができない。（例えばＳａｎｄｖｉｎｅ(www.sandvine.com）又はＲｉｖｅｒｈｅａｄ Ｎｅｔｗｏｒｋｓ（www.riverhead.com）からの）市販の監視器（policers）は、ネットワークの残りで使用されている各経路の状態に関係なくフローが最大速度を超えないことを確実にする。このような監視器には、装置自体における局所的な輻輳についての自らの知識を使用できるが、他の場所については使用できない。
【００１４】
実際には、これらの市販されている監視器［４、５、１２、１３、１４、１５、１６］によって必要とされる状態の量を削減する、提案されている監視器が動作するためには、自らが輻輳している中継器上に置かれなければならない。「ボトルネック監視器（ｂｏｔｔｌｅｎｅｃｋ ｐｏｌｉｃｅｒｓ）」と呼ぶところの、これらの監視器の全ては異常に高いビットレートを検出するが、経路が輻輳していない場合、あるいは往復時間が短い場合には完全に筋が通っている高送信速度は検出しない。同様に、最新のブロードバンドリモートアクセスサーバ上の他の監視器は、高容量のファイル共有を制御するために月次量上限を施行する。しかしながら、このような監視器は、使用中にピークを引き起こすほど多くのトラフィックでトラフ（ｔｒｏｕｇｈ）を満たすトラフィックを処罰する。
【００１５】
Ｆｌｏｙｄ及びＦａｌｌ［４］は、無作為早期検出（ｒａｎｄｏｍ ｅａｒｌｙ ｄｅｔｅｃｔｉｏｎ，ＲＥＤ）機構に基づいたペナルティボックス機構を提案している。ＲＥＤは、インターネットルータで幅広く使用されている待ち行列管理機構であり、回線に対する出力待ち行列が長いほど、待ち行列に到達するパケットが廃棄される（ＥＣＮがイネーブルされている場合にはマークを付ける）確率が高くなる。Ｆｌｏｙｄ及びＦａｌｌの考えは、ＲＥＤアルゴリズムの廃棄履歴を監視することである。十分長い期間の後に、廃棄履歴に多く現れるいかなるフローも、正常に動作していいないと見なされ、ブラックリストに載せられ、適切な処分（削除、降格（declassing）、…）のために提示される。ＣＨＯＫｅ［５］も、極めて正常に動作していないフローは、準拠しているＴＣＰフローよりデータストリーム内にはるかに多く出現するという考えを利用している。パケットが到着するといつでも、該パケットは待ち行列から無作為に選ばれた別のパケットと比較される。該２つが同じフローからである場合、そのフローは正常に動作していないことが疑われる。ＣＨＯＫｅは異常に高速のトラフィックを押さえ込むことに非常に優れた結果を示している。
【００１６】
多くの研究提案は、Ｆｌｏｙｄ及びＦａｌｌ［４］によって初めに提案された速度監視のための技法に増分的な改善を加えたものである。安定化されたＲＥＤ（ＳＲＥＤ［１２］）が並行して発表され、後の改善策にはＣＨＯＫｅ［５］、優先的廃棄（Ｐｒｅｆｅｒｅｎｃｅ Ｄｒｏｐｐｉｎｇ）ＲＥＤ（ＲＥＤ−ＰＤ［１３］）、最小最近使用（Ｌｅａｓｔ Ｒｅｃｅｎｔｌｙ Ｕｓｅｄ）ＲＥＤ（ＬＲＵ−ＲＥＤ［１４］）、ＸＣＨＯＫｅ［１６］、及び近似公平廃棄（Ａｐｐｒｏｘ． Ｆａｉｒ Ｄｒｏｐｐｉｎｇ）（ＡＦＤ［１５］）が含まれる。
【００１７】
しかしながらすべての場合において、速度は経路の特定の特徴とは関係なく監視される。例えば、１つの共通のボトルネックをわたる２つのフローを考えてみる。短い往復時間のフローＡは、それ以外にはほとんど輻輳していない経路を通過するのに対し、フローＢは４倍長い往復時間を有し、該フローの経路上で４倍多くの輻輳を経験する。長期的には、フローＢは、フローＡが取得する帯域幅の８分の１だけ取得するべきである。それにも関わらず、すべての既存の監視器を用いると、監視器自体を収容するネットワーク要素上ではないどこかに輻輳がある場合、両方のパケットは等しく責任があると見なされるため、フローＡはフローＢよりはるかに制約される可能性が高い。
【００１８】
Ｃｌｅｒｇｅｔ及びＤａｂｂｏｕｓ［１７］は、別の種類の分散速度監視を提案している。Ｃｌｅｒｇｅｔ及びＤａｂｂｏｕｓの提案しているフレームワーク、「タグベースの統一公平性（Tag-based Unified Fairness）」（ＴＵＦ）では、既定のタイプの流れがすべてボトルネック帯域幅の同じ割当てを取得するように、ボトルネックがトラフィックを監視する。該ＴＵＦ方式は、クラス内の公平性を保証できるが、クラス間の公平性は保証できない。つまり、ｎ＿ＴＣＰ個のＴＣＰフローとｎ＿ＵＤＰ個のＵＤＰフローがボトルネックを共有する場合、
ｎ＿ＴＣＰ＊ｘ＿ＴＣＰ＋ｎ＿ＵＤＰ＊ｘ＿ＵＤＰ＝Ｃ
となるように、各ＴＣＰフローは割当てｘ＿ＴＣＰを取得し、各ＵＤＰフローは割当てｘ＿ＵＤＰを取得する。ここで、Ｃはノードの送信容量であるが、２つの非常に独特のレベル以外の任意のレベルの輻輳に対して、ｘ＿ＴＣＰ ！＝ｘ＿ＵＤＰである。さらに、ＴＵＦ方式は、クラス間公平性を達成しないことに加えて、ボトルネック監視制限器の弱点も示す。
【００１９】
また、従来の技術では、Ｒａｉｓｉｎｇｈａｎｉ及びＩｙｅｒ［１８］が、廃棄は経路の最終的な無線セクションですべて引き起こされると仮定して、フローが目指すべき達成可能な輻輳ウィンドウを制御することによって、受信機が、受信機のフローに動的に優先順位を付ける機構を開示している。これは、フロー間輻輳制御の問題に関係し、該受信機のフロー間の優先順位を調整するために受信機が輻輳信号をいじるものと考えられる。この文書は、ＲＥＤでの別の単独ボトルネック公平性最適化であるＲＥＤ−ＤＴの説明を含んでいる。該最適化は、待ち行列の長さ、バッファサイズ、及び、すべて該ノード独特の多くのフローごとの変数等の局所情報（つまり、考慮しているノードにとって局所）にだけ依存している。
【００２０】
さらなる従来の技術の文書、Ｎｉｋｏｌｏｕｚｏｕら［１９］は、一般的な差別化サービス（ＤｉｆｆＳｅｒｖ）構成を説明し、ＤｉｆｆＳｅｒｖ環境における特定のネットワークサービスの定義及び配備に取り組んでいる。
【００２１】
最近、データ送信元が高容量ネットワーク全体でどれほど高速にデータを送信できるのかを、該データ送信元の速度制御アルゴリズムが迅速に突き止めることができるようにするための提案がなされている。これらの提案では、該送信元はプロトコルフィールドに要求を入れる。ＸＣＰ［１１］では、要求は、なんらかの肯定応答が受信される前にどれほど多くのデータを送信できるのかに関している（飛行中のデータの量、又は輻輳ウィンドウと呼ばれる）。クイック−スタート［１０］では、フィールドは送信速度に関するものである。パケットがネットワークを横切るとき、ルータが許容できる測定基準の値が要求未満である場合、ルータは該フィールドを書き直す。しかしながら、結果として生じるフィールドは依然として送信機に返されなければならず、送信機は該送信機の将来の速度が該送信機の要求に対するネットワークの応答に準拠することを保証しなければならない。したがって、両方の方式とも、依然として、送信機と受信機自体の関心に逆らって該送信機と受信機の協力に依存している。該ルータは、該ルータが従前のラウンドで与えた応答を覚えており、次に送信元が準拠しているかをチェックすることができるが、これにはフローの状態がルータで保持されることが必要とされ、インターネットのパケット送信特徴である、処理状態を把握しないコネクションレスモデルの利点を失う。
【００２２】
ＡＴＭ等の接続指向ネットワークでは、ネットワーク要素は各接続に沿って輻輳バックプレッシャーメッセージ［９］を送信するが、該要素は接続指向ネットワークを信頼しないため任意のエンドツーエンドフィードバックを重複する。しかしながら、コネクションレスデータグラムネットワークにおいて、低い接続セットアップ待ち時間及びパケットネットワークのロバスト性という利点を失うことなく同様の技法を使用することは本質的に困難である。
【００２３】
参照として主題が本明細書に組み込まれている、公開番号ＷＯ２００５／０９５６６を有する、本出願人によって出願された同時係属出願では、「リ−フィードバック」と名付けられた新規のフィードバック機構が提案され、この用語は「受信機−正規化（Ｒｅｃｅｉｖｅｒ−Ｎｏｒｍａｌｉｓｅｄ）」フィードバックという考えを示している。リ−フィードバック機構によると、送信機が、任意の経路を特徴付けるフィールドの初期値を設定し、該送信機が経路情報を蓄積するまでに、該フィールドが一般的に標準化された値に設定された目的に到達する傾向がある。送信先からの送信元へのフィードバックは、次に、将来データが送信されるときの目的の値に対する誤差を継続的に訂正するよう使用される。主な優位点は、伝送経路に沿ったインライン装置による使用のために、データが、該データとともに、該データの下流経路の「予測」を効果的に搬送するという点である。
【００２４】
さらに、やはり参照として主題が本明細書に組み込まれている、公開番号ＷＯ２００５／１０９７８３を有する、同出願人によって出願された別の同時係属出願では、パケットの中の下流経路測定基準（例えば、輻輳又は遅延）が永続的に負ではないことを保証するためにトラフィックを傍受するであろう新規の廃棄監視器が提案された。該監視器は、パケット切捨て又は廃棄等の処分を使用した。これら２つの出願の発明の実施形態はともに、ネットワーク間をまたぐ伝送中に経験された輻輳及び遅延に比例して減分された後にも該フィールドが正のままとなるように十分に高い値を、各パケットの経路測定基準フィールドの中に、送信機が、必ず「あらかじめロード（ｐｒｅ−ｌｏａｄ）」することを保証するために使用されることができる。
【００２５】
［４］Ｓ．Ｆｌｏｙｄ及びＫ．Ｆａｌｌ、「インターネットにおけるエンドツーエンド輻輳制御の使用促進（Promoting the Use of End-to-End Congestion Control in the Internet）」、ＩＥＥＥ／ＡＣＭネットワーキングに関する会議記録、１９９９年５月
［５］Ｒ．Ｐａｎ、Ｂ．Ｐｒａｂｈａｋａｒ、及びＫ Ｐｓｏｕｎｉｓ、「ＣＨＯＫｅ―公平な帯域幅割当てを近似するための処理状態を把握しないアクティブ待ち行列管理方式（A statelss active queue management scheme for approximating fair bandwidth allocation）」
［９］「Ｂ−ＩＳＤＮにおけるトラフィック制御及び輻輳制御（Traffic control and congestion control in B-ISDN）」。推奨策Ｉ．３７１（０３／０４）、ＩＴＵ−Ｔ、ＵＲＬ：http://www.itu.int/rec/recommendation.asp?type=folders&lang=e&parent=T-REC-I.371、２００４年３月
［１０］Ａｍｉｔ Ｊａｉｎ、Ｓａｌｌｙ Ｆｌｏｙｄ、Ｍａｒｋ Ａｌｌｍａｎ、及びＰａｓｉ Ｓａｒｏｌａｈｔｉ、「ＴＣＰ及びＩＰのためのクイック−スタート（Quick-Start for TCP and IP）」。インターネット草案ｄｒａｆｔ-ａｍｉｔｑｕｉｃｋ−ｓｔａｒｔ−０３、インターネットエンジニアリング作業部会（Internet Engineering Task Force）、ＵＲＬ：http://www.icir.org/floyd/quickstart.html、２００４年９月（進行中の研究）
［１１］Ｄｉｎａ Ｋａｔａｂｉ、Ｍａｒｋ Ｈａｎｄｌｅｙ、及びＣｈａｒｌｉｅ Ｒｏｈｒｓ、「高帯域幅−遅延製品ネットワーク用輻輳制御（Congestion control for high bandwidth-delay product networks）」、会議記録、ＡＣＭ ＳＩＧＣＯＭＭ２００２年、コンピュータ通信レビュー（Computer Communication Review）、３２（４）：８９−１０２、２００２年１０月
［１２］Ｔｅｕｎｉｓ Ｊ．Ｏｔｔ、Ｔ．Ｖ．Ｌａｋｓｈｍａｎ、及びＬａｒｒｙ Ｈ．Ｗｏｎｇ、「ＳＲＥＤ：安定化ＲＥＤ(ＳＲＥＤ：Ｓｔａｂｉｌｉｚｅｄ ＲＥＤ)」、会議記録、コンピュータ通信に関するＩＥＥＥ会議（IEEE Conference on Computer Communications（Ｉｎｆｏｃｏｍ１９９９年）中、１３４６から１３５５ページ、ＵＲＬ：http://citeseer.nj.nec.com/ott99sred.html、１９９９年３月、ＩＥＥＥ
［１３］Ｒａｔｕｌ Ｍａｈａｊａｎ、Ｓａｌｌｙ Ｆｌｏｙｄ及びＤａｖｉｄ Ｗｅｔｈｅｒａｌ、「輻輳ルータにおける高帯域幅フローの制御（Controlling high-bandwidth flows at congested router）」、会議記録、ネットワークプロトコルに関するＩＥＥＥ国際会議（IEEE International Conference on Network Protocols）（ＩＣＮＰ２００１年）、URL:http://citeseer.nj.nec.com/545435.html、２００１年
［１４］Ｓｍｉｔｈａ Ａ．Ｌ．Ｎａｒａｓｉｍｈａ Ｒｅｄｄｙ、「ＬＲＵ−ＲＥＤ：輻輳ルータにおける高帯域幅フローを含むためのアクティブ待ち行列管理方式（LRU-RED:An active queue management scheme to contain high bandwidth flows at congested routers）」、会議記録、Ｇｌｏｂｅｃｏｍｍ２００１年、URL:http://citeseer.nj.nec.com/473674.html、２００１年１１月
［１５］Ｒｏｎｇ Ｐａｎ、Ｌｅｅ Ｂｒｅｓｌａｕ、Ｂａｌａｊｉ Ｐｒａｂｈａｋｅｒ、及びＳｃｏｔｔ Ｓｈｅｎｋｅｒ。「差分廃棄による近似公平性（Approximate fairness through differential dropping）、コンピュータ通信レビュー（Computer Communication Review）、３３（２）：２３−４０、２００３年４月
［１６］Ｐ Ｃｈｈａｂｒａ、Ｓ．Ｃｈｕｉｇ、Ａ Ｇｏｅｌ、Ａ Ｊｏｈｎ、Ａ Ｋｕｍａｒ、Ｈ Ｓａｒａｎ及びＲ Ｓｈｏｒｅｙ、「ＸＣＨＯＫＥ：インターネットゲートウェイにおける輻輳回避のための悪意のある送信元の制御（XCHOKE:Malicious Source Control for Congestion Avoidance at Internet Gateways）」、会議記録、ＩＣＮＰ、２００２年１１月
［１７］Ａｎｔｏｉｎｅ Ｃｌｅｒｇｅｔ及びＷａｌｉｄ Ｄａｂｂｏｕｓ：「ＴＵＦ：タグベースの統一公平性（TUF:Tag-based Unified Fairness）」、コンピュータ通信に関するＩＥＥＥ ＩＮＦＯＣＯＭ会議（IEEE INFOCOM Conference on Computer Communications）の会議記録、２００１年４月
［１８］Ｖｉｊａｙ Ｒａｉｓｉｎｇｈａｎｉ及びＳｒｉｄｈａｒ Ｉｙｅｒ：「公平なルータが存在する場合の受信機ウィンドウ制御の分析(Analysis of receiver window control in the presence of a fair router)」、個人通信及び無線通信に関するＩＥＥＥ国際会議（IEEE Intl.Conf.on Personal and Wireless Communications）、２００５年1月
［１９］Ｎｉｋｏｌｏｕｚｏｕ、Ｍａｎｉａｔｉｓ、Ｓａｍｐａｔａｋｏｓ、Ｔｓｅｔｓｅｋａｓ及びＶａｎｉｅｒｉｓ：「差別化されたサービスアーキテクチャにおけるネットワークサービスの定義及び配備（Network Services Definition and Deployment in a Differentiated Services Architecture）」、通信に関する国際会議(IEEE Intl.Conf.on Communications)２００２年
前述されたように、既存の監視方法によれば、速度は経路の特殊な特徴とは関係なく監視される。このため、既存の監視器は、自らの応答性（つまり、正常に動作していないフローを迅速に検出する能力）、自らのロバスト性（つまり、準拠するフローを、正常に動作していないとして識別する数をできるだけ少なくし、これによる「誤った肯定判断」を回避する能力）、及び特にこれらのような特徴の間のトレードオフを含む特定の監視特徴を最適化するための機会を自ら否定している。
【００２６】
本発明の第１の態様によると、データネットワーク内でフローを監視する方法が提供され、前記データネットワークは、基準速度適応ポリシーが関連付けられたネットワークサービスを提供し、前記方法は、
ノードを通るフローの過度要求(greediness)の基準を決定するステップと、
前記過度要求の基準を、許容できる過度要求を示す基準と比較するステップと、
前記過度要求が前記許容できる過度要求に従うものでない場合に、考えられる処分のために前記フローを指定するステップと、を備え、
許容できる過度の要求を示す前記基準は、前記ネットワークサービスと関連付けられた基準速度適応ポリシーに準拠し、実質的に同様の経路状態を経験するフローの期待される過度要求に依存して決定されることを特徴とする。
【００２７】
本発明の関連する態様によると、データネットワーク内でフローを監視する装置も提供され、前記装置は前記第１の態様による方法を実現するための前記ステップを実施するための手段を備える。
【００２８】
データネットワーク内のフローは、一般的には、複数のメッセージを備えると考えられ、これらは、問題にしているネットワーク及び／又はプロトコルに適用可能な個々のデータ搬送項目である。このような監視方法が、現在のインターネットプロトコル（ＩＰ）に関連して使用される場合、メッセージは一般的にＩＰパケットとなることが理解される。
【００２９】
（公開番号ＷＯ２００５／０９６５６６である前述された同時係属出願において、可能であることが示されたように）メッセージ又はパケット内のフィールドがメッセージ又はパケットの下流経路の予測を搬送するネットワーク要素に達すると、これらのフィールドを使用して、メッセージ又はパケットが到達すべき速度を監視することがさらに可能になる。公開番号ＷＯ２００５／１０９７８３である前述された同時係属出願に説明されたように、廃棄器（ｄｒｏｐｐｅｒ）がネットワーク間の遠隔出口（remote egress）に位置する場合、送信機が下流輻輳又は遅延を低く評価しないように強制する、説得する、あるいは少なくとも奨励することが可能になる。
【００３０】
ホストベースの速度制御アルゴリズムは、送信速度を決定する各フローの経路の最新の状況についての状態を保持する。例えば、ＴＣＰは輻輳ウィンドウ変数を保持するが、ＴＣＰフレンドリ速度制御及びＫｅｌｌｙのアルゴリズムは現在の送信速度を有する変数を保持する。
【００３１】
いったん経路特徴付けが各パケットの中で、ネットワーク要素に達すると、該要素はそれ自体の経路状態を各フローに対して保持できる。次に、該要素は、どれほど高速にフローを送信する必要があるかの独自の見通しを導くことができる。該要素は、パケットをバッファに入れることによって該フローの速度を形成するために該見通しを使用できるが、監視（policing)と呼ばれるように、該送信元が変化する経路に応じて該送信元の速度を正しく適応させているかどうかを単にチェックすることが好ましい。フロー単位の状態がネットワーク要素で保持されることを必要とする方式はあまり好ましくないことを既に述べた。しかしながら、エッジアクセスルータは、既に（カスタマの許容最大速度等の）各アクセスカスタマの状態を保持しているので、エッジアクセスルータがフローごとの状態を保持するのは、比較的問題にはならないであろう。
【００３２】
同様に、Ｆｌｏｙｄ及びＦａｌｌによって提案されているようなボトルネック監視アプローチ（上記の［４］を参照）は、複数のボトルネックをわたるフローのスループットを監視することはできないために、該ボトルネック監視制御アプローチをとることは十分ではない。さらに、ＣｌｅｒｇｅｔらのＴＵＦアプローチ（上記の［１７］を参照）は、適切なクラス間公平性を提供しない。本発明の実施形態による提案された経路独特のアプローチは、既定のネットワークサービス上で送信されるすべてのトラフィックが、同じ基準、に対して、ベンチマークテストされることができることを保証することによってこれらの欠点に対処できる。該同じ基準は、すなわち、準拠するフローが、該ネットワークサービスについて合意された速度適応ポリシー（例えばＴＣＰ速度適応）について有するであろうスループットである。
【００３３】
図１は、ボトルネック監視器（図１（ａ））と、本発明者らが提案する経路独特の監視器（図１（ｂ））の相違点を概略している。同じ概念は他の測定基準にも使用できるが、特に輻輳測定基準について相違点を説明する。局所的な輻輳ｍ１、ｍ２、ｍ３、ｍ４を有する４つのネットワークノードをわたる、送信元Ｓと送信先Ｄの間のフローを考える。監視ノードは、輻輳の局所的レベル「ｍｉ」及び該ノードが監視を実行する情報「ｙ」とともに表されている。ノードが通過させることを目的とするスループットを「ｘ（ｙ）」と定める。
【００３４】
ボトルネック監視器の場合、ｙ＝ｍｉであり、監視器があらゆる潜在的なボトルネック、つまり経路上のあらゆるルータで必要とされていることを意味する。各ボトルネック監視器の作用は以下の通りであり、
ｘｉ＝ｍｉｎ（ｘｉ−１、ｘ（ｍｉ））
したがって、全体的な作用はｘｎ＝ｍｉｎ（ｘ0、ｘ（ｍ１）、ｘ（ｍ２），．．．，ｘ（ｍｎ））となる。さらに、ｘ（ｍ）が減少関数であり、したがって
ｍｉｎ（ｘ（ｍｉ））＝ｘ（ｍａｘ（ｍｉ））
であり、したがって全体的な作用は最悪のボトルネック単独の作用であることを意味することに留意すべきである。
【００３５】
他方、経路独特の監視器の場合、ｙ＝Ｍ、つまりエンドツーエンド輻輳レベルである。この場合、各ネットワークノード（ｘ0、ｘ１，．．．ｘ４）でのスループット調整の代わりに、ｘｓからｘＤまでの潜在的なスループット調整のみが行われる。
【００３６】
経路独特の解決策の状態要件を低減するために、以下で、より少ない状態を必要とする本発明の代替実施形態を説明する。どれほど多くの状態を保持すべきかと、どれほど速く監視器が正常に動作していないフローを検出できるのかの間でトレードオフが行われてもよい。正常に動作していないフローは、同じ経路状態を与えられた準拠しているフローが使用するよりはるかに多い帯域幅を使用するフローとして定義することができる。本発明の好ましい実施形態によると、ストリーム内のパケットのフロー説明を、該フローの期待スループットに反比例する確率で記録することによって、正常に動作していないフローを検出することが提案されている。方程式（１）（上記を参照）は、どのように期待スループットが決定され得るかの一例として使用されるものであり、パケットから取得される経路独特の特徴付け値に基づいていることに留意する。フローが、該フローの速度適応において、許されている、あるいは許容できると見なされているより一貫して多く要求する（ｇｒｅｅｄｙ）場合、該フローはかなり頻繁にポーリング記録に出現し、おそらくさらなる調査期間の後に（単に警告としてのマーキングを伴う場合もあるが、降格、削除等のさらに懲罰的な処置を含む場合もある）処分のために１つずつ選び出される。
【００３７】
許可されている速度適応アルゴリズムはＴＣＰの標準的なものであってよいし、あるいは代わりに、ＭｕｌＴＣＰ又はＫｅｌｌｙのもののような送信機と進入（ｉｎｇｒｅｓｓ）ネットワークオペレータの間で合意された何らかの他のアルゴリズムであってもよい。これらの後者の場合には、重み付けパラメータω又は支払い意志パラメータｗは、送信機と進入ネットワークとの間の合意の一部でなければならない可能性がある。このパラメータはトラフィックのクラスと、特定のフロー識別子と、特定のタイプのアクセスインタフェースと、又はパケットのいくつか又はすべてで搬送されるなんらかのフィールドと関連付けられるであろう。この合意は、パラメータが必要とされるときに、信号で伝えられてもよいし、あるいは長期にわたる契約により合意されてもよい。
【００３８】
好ましい実施形態を、従来の技術の方式異ならせている特殊な態様とは、正常に動作していないフローが、該フローの絶対スループットのためだけで特徴付けられるのではなく、準拠しているフローがデータ経路上の同じネットワーク状態で取得するであろうスループットを基準にしたスループットで特徴付けられるという点である。これは、処分を行うべきフローを選択する際にはるかに正確である。
【００３９】
各フローが輻輳に応答することを保証する上記の機構に加えて、追加の機構が、好ましくは、各フローではなく各送信ユーザの単位で動作する必要がある。「ユーザ単位の」カウンタは、ポーリング記録のために確率的に選択されたパケットからのすべての輻輳値の累積合計を保持しなければなければならない。その結果、このカウンタは、より多くの輻輳を引き起こすユーザに対してより厳しく「フロー単位の」アルゴリズムを重み付けするために使用できる。
【００４０】
この追加がないと、ユーザは、単に、単一の正常に動作していないフローを、同じ送信先への複数の正常に動作するフローに分割するだけでフロー単位の監視器を迂回できるであろう。また、２つの送信者が、つねにフローが準拠していることを保証する場合であっても、一方は準拠しているフローで連続して送信機のアクセス回線を満たしているのに対し、他方は時折のユーザである可能性がある。
【００４１】
監視器の長期の挙動に対する厳密性のこの適応は、大量需要家（ｈｅａｖｙ ｕｓｅｒｓ）は依然として高速で送信できるが、輻輳が低い、あるいは経路が短い経路の中だけに送信できることを保証する。それに対して少量需要家（ｌｉｇｈｔ ｕｓｅｒｓ）はつねにフルＴＣＰ速度で送信するのを許される。これは、処分を決定するために、測定基準として、（使用のピークの間に送信されるか又はトラフ間に送信される）データ量を使用し、（たとえ輻輳していない経路に送信する場合にも）処分としてデータアクセス速度を制限する、本出願人によって出願された別の同時係属出願すなわち、公開番号ＷＯ２００５／０３２０６８に述べられている方式の実施形態を使用して可能であることに対する有利な相違点につながる。
【００４２】
上述されたように、「リ−フィードバック」の概念を使用することによって、修正されないコアルータ及び境界ルータ全体で変更されないＩＰを使用して、単にネットワーク層ヘッダを検査するだけで、ＴＣＰが対応すべきように輻輳に対応しないトラフィックをネットワーク入口で検出し、削除することが可能であることを示した。このように、インターネットサービスプロバイダがＶｏＩＰ又はビデオについての料金請求を希望する場合、ユーザは、料金請求を回避するために、（例えば、暗号化された「スカイプ（Ｓｋｙｐｅ）」ピアツーピア―www.skype.comを参照すること―を使用して）ベストエフォート型のトラフィックにユーザの反応しないトラフィックを隠すことにより利益を得られることを妨げることができる。
【００４３】
このような問題を克服するためには、Ｓａｎｄｖｉｎｅ又はＲｉｖｅｒｈｅａｄ Ｎｅｔｗｏｒｋｓ（上記を参照）等のベンダから入手できるような速度監視器を使用することは十分ではない。速度を制限し、したがってより低い層のカスタマがネットワークから引き出すことができる値を制限できることは確かに望ましい。しかし、このような制限は、最良の条件における最大を表すものである。すべてのカスタマがネットワークから引き出す値を最大限にするため、及び収益と他のネットワークとの相互接続の費用とのバランスを取るために、許容される速度はさらにネットワーク間の全体又は関連性のある部分での経路状態に依存してしまう。。
【００４４】
また、正常でない動作（misbehaviour）は、パケットが搬送するデータではなく、該パケットが到達する速度に関係し得るため、正常に動作していないフローを検出するためにディープパケットインスペクション（Deep Packet Inspection（DPI））を使用することは十分ではない。パケットは自らをＴＣＰとしてラベルを付けても、ＴＣＰアルゴリズムに従って動作しないこともできる。同様に、パケットは自らをＵＤＰ、スカイプなどとしてラベルを付けても、ＴＣＰにフレンドリなアルゴリズムを使用して送信されることができる。
【００４５】
本発明の好ましい実施形態による監視器を使用すると、例えば日数で測定される期間にわたって累積的に、人間が引き起こす、より多くの輻輳をより激しく押し戻すことが可能になる。したがって、ｐ２ｐファイル共有等の高帯域幅活動のためのネットワークの使用は、ネットワークエッジでピークから離れるようにトラフに押し込まれることができる。
【００４６】
さらに、前述された「リ−フィードバック」概念と、必要な場合に結合され、本発明の好ましい実施形態によるエッジネットワーク装置は、単にＴＣＰだけではなく任意の所望される輻輳応答を監視することができ、それによってインターネットのまさにエッジにおいてだけで監視を実施することによってプロバイダ間のＱｏＳを実施することができる。
【００４７】
本発明の好ましい実施形態は、ここでさらに詳細に添付図面に関して説明される。
【発明を実施するための最良の形態】
【００４８】
潜在的な悪用者の検出
定義及び表記
「リ−フィードバック」ネットワーク内のノードを考える。フロー１．．．ｊ．．Ｊは、時間ｔ＝０とｔ＝τの間にパケット１．．ｉ．．Ｎｊを送信し、観察期間を特徴付ける。暗に表記ＪとＮｊはτに依存するものであることを示す。送信元がペイロードデータで飽和し、そのため、送信元が準拠し、正常に動作する（ｂｅｈａｖｉｎｇ）送信元に対する速度適応ポリシーに従って、あるいは正常に動作していない送信元に対する送信元の過剰な帯域幅使用応じて、送信元が可能な限り多くのパケットを送信する状況を検討する。
【００４９】
Ｘａｐｐ、すなわち、期間τにわたるフローｊの見かけのスループットを、方程式（３）によって与えられるように、観察期間にわたって送信されるデータ量の割合として定め、
【数３】
【００５０】
ここで、Ｓｊ，ｉとＴｊ，ｉはフローｊのパケットｉのサイズと到着時刻である。
【００５１】
今日のインターネットでは、ほとんどのフローはＴＣＰに準拠していることが期待でき、該フローの長期スループットが長い間同じ経路状態を経験している並列のＴＣＰフローの長期スループットを超えることは絶対に期待できないであろう。このＴＣＰ同等速度は、方程式（１）によって与えられるものであり、ここに再度方程式（４）として示す。
【数４】
【００５２】
ここで、ｓ、Ｔ及びｍはそれぞれ、パケットサイズ、往復時間、及びエンドツーエンド輻輳レベルの、期間τにわたる平均値であり、ｋＴＣＰ＝１／√１．５である。
【００５３】
将来、他の速度適応ポリシーが一般的となる可能性があり、その場合、経路及びフロー特性に関して、異なる長期期待スループットの表現ｘ＃＝ｆ（Ｔ，ｍ，ｓ）が得られるであろう。
【００５４】
ｘ＃を、フローが辿る経路の状態に関してトラフィックを監視するための基準準拠速度として使用し、ここで、＃は、そのクラスに使用される速度適応ポリシーを示すものであり、トラフィックｘＴＣＰポリシーは、ｘ＃の特殊な場合である。
【００５５】
Ｋｅｌｌｙによって定義される、このような速度適応のその他の例は、一定の料金を支払う意志のあるユーザを前提としており、フローにおいて検出される輻輳点ごとに固定料金を請求できる状況を前提としている。このような速度適応ポリシーを使用するフローの期待長期スループットは方程式（２）（前記参照）によって特徴付けられる。
【００５６】
最終的に、フローの見かけの過度要求（ｇｒｅｅｄｉｎｅｓｓ）αｊを、方程式（５）に示されるように、フローの見かけの速度Ｘａｐｐとこの期待準拠速度ｘ＃の比として定める。
【数５】
【００５７】
フローが監視される速度適応ポリシーに準拠するフローの、期待される過度要求は１であることに留意する。
【００５８】
経路独特の監視を実行するために、準拠する過度要求α＃と上限過度要求α＊も定義する。フローｊの過度要求αｊが基準期間τ＊より長い期間、α＊に達する場合、該フローは準拠していないと見なされ、さらなる調査、処分が行われる。
【００５９】
一般性を失うものではないが、表現を簡略にするため、本文書の残りでは、ＴＣＰ速度適応との関連だけで監視器を説明し、したがってｘ＃＝ｘＴＣＰ及びα＃＝αＴＣＰと設定する。
【００６０】
経路独特の監視器の設計
監視器の一般的な目的
図３は、監視器の目的を概略する。該監視器は、見かけの過度要求αｊが期間τ＊の間、上限α＊より高い任意のフローにフラグを立てなければならない。フローｊは速度Ｘａｐｐで監視器に到達する。監視器の作用は、フローが正常に動作しているか（αｊ＜α＊）か、あるいは正常に動作していないか（αｊ＞α＊）を特定し、この情報に基づいてフローのその後の処理を分けることである。
【００６１】
ＸＴＣＰの値はフローごとに保持されなければならず、パケットが受け取られるときはいつでも更新することができる。例えば、ＸＴＣＰは方程式（４）によってリ−フィードバックフィールドからの各パケットについて得ることができる。以下に、フロー単位のαｊを監視し、期間τ＊の間、上限α＊より高い過度要求を持ったフローを処分すべく分けるためのいくつかの機構を説明する。
【００６２】
フローの正確な定義が未決のままにされていることに留意する。好ましくはフローの定義は、送信元アドレスと送信先アドレス及びポートで特定される、エンドツーエンド接続のパケットとなるであろう。フローの定義は、このような接続の集合体であってもよい。例えば、監視器の所定のインタフェースに入信し、所定のＩＰプレフィックスに向けて送信されるすべての接続である。
【００６３】
「ボトルネック監視器」として前記に参照されたタイプの１つであり得る、現在の「旧式の（ｃｌａｓｓｉｃ）」監視器に対する相違点が図２に概略されている。現在まで、監視器は、疑わしいフローを、該フローが辿る経路の状態（伝送遅延、輻輳・・・）に関係なく、該フローの見かけの速度だけに基づいて１つずつ選び出す。これは、経路独特の速度適応ポリシーに従うフロー、及び特に現在のインターネットトラフィックの大多数を構成するＴＣＰフローを監視する上で効率的ではない。図２は、この違いを示している。
【００６４】
（例えば、長い往復時間及び／又は高輻輳によって特徴付けられる）不良経路状態を経験する高速フローは旧式の監視器（図２（ａ））及び経路独特の監視器（図２（ｂ））の両方で捕らえられ、（各図のゾーン１を参照すること）、及び良好な経路状態を経験する低速フローも両方の場合で通される（ゾーン２）が、旧式の監視器はフローの以下の２つのカテゴリを間違って特徴付けるであろう。
【００６５】
−ゾーン３において、絶対的にはそれほど高くないが、それでも、好ましくない経路状態を考慮すると高すぎるスループットを有するいくつかのフローを、旧式の監視器は、正常に動作していないと分類しないであろうが、経路独特の監視器はそのようなフローを捕らえるであろう。
【００６６】
−ゾーン４では、絶対的には非常に高いが、非常に好ましい経路状態を考えると完全に許容できるスループットを有するいくつかのフローを、旧式の監視器は正常に動作していないと分類するであろうが、経路独特の監視器はそのようなフローを通過させるであろう。
【００６７】
別の重要な相違点は、既存の監視器はネットワーク内のすべての潜在的な輻輳点に配備されなくてはならないという点である。本発明の実施形態は、代わりに、ネットワークの上流端で監視が実行できるようにし、したがってネットワークのより効率的な保護を可能にする。
【００６８】
トークンバケット監視器
考えられる機構は、フローの過度要求αｊと、同じ経路状態における準拠するフローの期待される過度要求αＴＣＰ＝１との差異の累積を監視することである。図４は、これがトークンバケットによってどのように実行できるのかを示す。パケットが到着するといつでも、αＴＣＰ・ｄｔｊ，ｉがトークンバケットに追加され（この場合ｄｔｊ，ｉは前回パケットからの、到着間の時間である）、ｋＴＣＰ・Ｔｊ，ｉ・√ｍｊ，ｉがトークンバケットから取り去られる（ここで、Ｔｊ，ｉとｍｊ，ｉはパケット内のフィールドから取得される）。調整後に該バケットが空ではない場合は、パケットは要求に応じて供給される。他方、パケットが空である場合は、フローは処分するようフラグを立てられ、パケットは適切に処理される。
【００６９】
図６は、図４に関連するフローチャートを説明する。パケットが到着すると、該パケットは該パケットのフローｉｄ ｊ、下流輻輳測定基準ｍｊ，ｉ、往復時間Ｔｊ，ｉ、及び該パケットが受信された時刻ｔｎｅｗと関連付けられる。最初に、監視器は、該フローがブラックリストに載っているかどうかをチェックする（最初はブラックリストに記載されているフローはない）。該フローがブラックリストに載っていない場合、監視器はｎＴＣＰ＝ｋＴＣＰ・Ｔｊ，ｉ・√ｍｊ，ｉを決定する。該フローのためのバケットＢｊが存在しなければ、監視器はバケットを作成し、バケット内のトークン数をＢｊ＝Ｂ０に、前回更新の時刻をｔｊ＝ｔｎｅｗに初期化する。
【００７０】
次に、すべての場合において、フローの中のトークン数は、ｔｎｅｗ−ｔｊ−ｎＴＣＰを追加することによって調整され、Ｂｍａｘによって上限を定められる。方程式６（以下を参照すること）に示されるようにＢｍａｘ＝Ｂ０＝Ｂとすることが推奨される。最終ステップは、この操作の最後にバケットが空ではないことをチェックすることである。Ｂｊ＞０の場合、パケットは通常通り処理されるが、Ｂｊ＜０の場合、フローｉｄはブラックリストに載せられ、パケットは処分されるように扱われる。
【００７１】
ｎＴＣＰを決定することは、平方根（あるいは、「経路測定基準を取得する」を扱う項に説明されるように、立方根）を抽出することを必要とし得るものであり、あまり単純な演算操作ではない。したがって、監視器の実現がパケットを転送する際の遅延を最小限に抑えることを必要とされる場合、動作の順序は異なってもよい。最初に、バケットの中のトークン数がチェックされるであろう。Ｂｊ＞０の場合、パケットはただちに転送されるであろう。トークンバケットの状態の更新はオフラインでなされるだろうが、更新が往復時間内に行われるよう十分に迅速に行われるであろう。パケット処理における遅延の最小化は、正常に動作していないフローを検出するためにさらに長くかかり得るものであり、応答性が犠牲にされ得る。
【００７２】
フローｊのパケットｉが到着すると、バケット充填は（＋αＴＣＰ・ｄｔｊ，ｉ−Ｔｊ，ｉ・√ｍｊ，ｉ／ｋ）によって調整される。期間τにわたる調整の累積は（αＴＣＰ−αｊ）・τと同等のｓｕｍｉ＝１．．Ｎｊ（＋αＴＣＰ・ｄｔｊ，ｉ−ｋＴＣＰ・Ｔｊ，ｉ・√ｍｊ，ｉ）である（付録Ａ１を参照すること）。
【００７３】
フルスピードＴＣＰフローの場合、Ｅｘｐ［ｓｕｍｉ＝１．．Ｎｊ（＋αＴＣＰ・ｄｔｊ，ｉ−Ｔｊ，ｉ・√ｍｊ，ｉ／ｋ）］＝（αＴＣＰ−αＴＣＰ）・τ＝０であり、トレンドはその初期位置の回りで振動するトークン数によるものとなる。
【００７４】
Ｅｘｐ［ｓｕｍｉ＝１．．Ｎｊ（＋αＴＣＰ・ｄｔｊ，ｉ−ｋＴＣＰ・Ｔｊ，ｉ・√ｍｊ，ｉ）］＝（αＴＣＰ−αｊ）・τ＞０であるため、不飽和のＴＣＰ−フレンドリフロー（αｊ＜αＴＣＰ）のためのバケットは飽和まで線形に充填する。
【００７５】
Ｅｘｐ［ｓｕｍｉ＝１．．Ｎｊ（＋αＴＣＰ・ｄｔｊ，ｉ−ｋＴＣＰ・Ｔｊ，ｉ・√ｍｊ，ｉ）］＝（αＴＣＰ−αｊ）・τ＜０であるため、正常に動作していないフロー（αｊ＞α＊）のためのバケットは、残っているトークンがなくなるまで線形的に空になる。
【００７６】
バケットの深さは監視器の目的によって定まる。監視器は、見かけの過度要求αｊが期間τ＊の間の上限α＊より高いあらゆるフローにフラグを立てなければならない。過度要求がα＊であるようなフローの場合、バケットが開始時にいっぱいであっても、バケットはτ＊の後に空にされなければならない。すなわち、
Ｂ＋Ｅｘｐ［ｓｕｍｉ＝１．．Ｎ（＋αＴＣＰ・ｄｔｊ，ｉ−ｋＴＣＰ・Ｔｊ，ｉ・√ｍｊ，ｉ）］＝Ｂ＋（αＴＣＰ−α＊）・τ＊＝０ である。
【００７７】
言い換えると、バケットの深さＢは方程式（６）で表される。
【数６】
【００７８】
実際には、これは、正常に動作していないとして識別されるＴＣＰ準拠のパケットは、非常に小さな割合だけであるが、期間τ＊の後に検出される、過度要求がα＊であるフローは５０％であることを意味する。
【００７９】
図５に描かれているような設計における別の変形例は、小さなフローに対するフロー単位の状態要件を制限する。該変形例は、以前にＸＴＣＰとして示された期待スループットに逆比例する各フロー内のトラフィックをサンプリングすることによって過度要求を監視する。
【００８０】
パケットが到達すると必ず、抜き取り検査が実行される。最初に、［０，１］上の均一な分散からｕｉを引き出す。λを一定のサンプリングパラメータとしたとき、ｕｉ＞λ・ｓｊ，ｉ／ＸＴＣＰであれば、パケットは要求されたとおりに供給される。ｕｉ＜λ・ｓｊ，ｉ／ＸＴＣＰであれば、λ・αＴＣＰ・ｄｔｊ，ｉがトークンバケットに追加され、１つのトークンがその中から引き出され、結果として調整はλ・αＴＣＰ・ｄｔｊ，ｉ−１となる。バケットが調整後に空でなければ、パケットは要求されたとおりに供給される。他方、バケットが空の場合、該フローは処分のためのフラグを立てられ、該パケットは適切に処理される。このとき、調整の累積はλ・（αＴＣＰ−αｊ）・τに同等である（付録Ａ２を参照すること）。
【００８１】
サンプリングバージョンの、監視器の優位点は、小さな、準拠するフローはトークンバケットの作成を必要とせず、これにより、非サンプリングの実施形態と比較して、監視器の状態要件（アクティブトークンバケット数）を低減するという点である。この特徴はサービス拒否攻撃から監視器を保護する上で重要である。
【００８２】
図７は、図５に関するフローチャートを説明する。パケットが到着すると、該パケットは該パケットのフローｉｄ ｊ、下流輻輳測定基準ｍｊ，ｉ、往復時間Ｔｊ，ｉ、及び該パケットが受信された時刻ｔｎｅｗと関連付けられる。最初に、監視器は、該フローがブラックリストに載っているかどうかをチェックする（最初はブラックリストに記載されているフローはない）。該フローがブラックリストに載っていない場合、監視器はｎＴＣＰ＝ｋＴＣＰ・Ｔ，ｊ，ｉ・√ｍｊ，ｉを決定する。この段階で、サンプリング監視器は範囲［０．．１］で選ばれる無作為変数ｕｊを選択し、それをλ・ｎＴＣＰと比較する。ｕｊ＞λ・ｎＴＣＰの場合、パケットはさらなる遅延なしに転送されるよう処理される。そうでない場合、もし該フローのためのバケットＢｊが存在しなければ、監視器はバケットを１つ作成し、バケット内のトークン数をＢｊ＝Ｂ０に、前回更新の時刻をｔｊ＝ｔｎｅｗに初期化する。そのとき、すべての場合において、フローの中のトークン数はλ・（ｔｎｅｗ−ｔｊ）−１を追加することによって調整され、λ・Ｂｍａｘによって上限を定められる。方程式６に示されるようにＢｍａｘ＝Ｂ０とすることが推奨される。最終ステップは、この操作の最後にバケットが空ではないことをチェックすることである。Ｂｊ＞０の場合、パケットは通常通りに処理されるが、Ｂｊ＜０の場合、フローｉｄはブラックリストに載せられ、パケットは処分されるように扱われる。
【００８３】
λの選択により、監視器の状態要件の制御を可能にする。より高い値は、監視器が、最短で最も準拠するフローのためのトークンバケットを作成するのに余裕を与える。
【００８４】
処分
ブラックリストに記載されているフローのパケットを処理するために、以下のような幅広い数のオブションが考えられる。
【００８５】
−パケットは削除されてもよい、
−パケットは、存在する場合にはより低い優先順位のクラスに格下げされてもよい、
−パケットは、送信元が反応するための警告としてマークを付されてもよい
トークンバケットＢｊの状態は、この時点においても更新され得る。フローがブラックリストに記載されたばかりのときにある処理が適用され、該バケット内のトークン数が負のままである場合は、さらに厳しい処理が適用され、（該フローが該フローの送信速度を大幅に削減する場合に発生するであろうように）該バケット内のトークン数が再び正になると、該フローはブラックリストから削除されることができる。
【００８６】
経路測定基準の取得
経路測定基準を取得する目的のため、３つの値、すなわちフローｉｄ ｊ、リ−フィードバック輻輳フィールドｈｊ、及びリ−フィードバック下流遅延Ｄｊがパケットヘッダから取り出され得る。
【００８７】
好ましくは、監視器は、ネットワークの入口に近くに位置するべきである。エンドツーエンド測定基準が準拠性テストに必要とされる一方、リ−フィードバックフィールドは実は、下流経路のみを特徴付けることができる。監視器がネットワーク入口近くに位置する場合、２つのオプションがある。すなわち、エンドツーエンド測定基準に対する上流の貢献は取るに足らないものであることが示されるため、差異は無視されるか、あるいは上流の貢献は監視ノードによって監視され、エンドツーエンド測定基準を得るために下流の測定基準とともに使用されるかのどちらかである。これは監視ノードが該ノードの上流経路の恒久的な状態を保つことを要求し得るものであり、上流のノード数が制限されるネットワーク入口でのみ管理可能となり得る。
【００８８】
好ましい実施形態に従って、ｈｊから引き出される下流測定基準から、ｍｊを引き出すことが提案されるが、これは標準的なリ−フィードバック操作である。これは、入口アクセス要素と送信側ホストの間の上流ネットワークには大きな輻輳がないことを仮定している。
【００８９】
方程式（１）のｍは、このようなマークの１つが往復時間内に１つ以上のパケットについて発生する確率ｍｒｔｔである必要があるのに対し、リ−フィードバックフィールドから引き出される値ｍｊは、パケットがマークを付けられる確率ｍｐｋｔを特徴付けることに留意する。将来、ｍｐｋｔがより適切であることが発生する可能性があるが、現時点においてははｍｒｔｔの方がより適切である。これらの２つの値の関係の密接な近似は、ｃｗｎｄ＝ｘＴＣＰ・Ｔ／Ｓｋ／ｍｒｔｔ＾（１／２）としたときのｍｒｔｔ〜ｍｐｋｔ・ｃｗｎｄである。これによりｍｒｔｔ〜（ｋ・ｍｐｋｔ）＾（２／３）となる。
【００９０】
また、好ましい実施形態に従って、輻輳のない期間における最小数の試験を使用して、各上流送信元と監視ノード自身との間の上流往復遅延Ｔ0の記録を監視ノードで保持することが提案されている。往復時間は、対称的なルーティングを仮定するとＴｊ＝Ｔ0＋２・Ｄｊとして得ることができる。応答を得る他の技法を使用使用してもよい。例えばＪｉａｎｇ及びＤｏｖｒｏｌｉｓ［２０］を参照すること。
【００９１】
［２０］Ｈａｏ Ｊｉａｎｇ及びＣｏｎｓｔａｎｔｉｎｏｓ Ｄｏｖｒｏｌｉｓ：「ＴＣＰ往復時間の受動的な推定（Ｐａｓｓｉｖｅ ｅｓｔｉｍａｔｉｏｎ ｏｆ ＴＣＰ ｒｏｕｎｄ−ｔｒｉｐ ｔｉｍｅｓ）」、ＡＣＭ ＳＩＧＣＯＭＭコンピュータ通信レビュー（Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｒｅｖｉｅｗ）第３２巻、第３号（２００２年７月）
上限条件の設定
以下では、（正常に動作していないと見なされ得る、準拠するフローの割合に厳しい上限を課すことによって）十分なレベルのロバスト性を達成するためにα＊がどのようにして選ばれなければならないのかを概略する。
【００９２】
上限の過度要求α＊は、監視器の主要な制御パラメータである。その選択は、監視器の（正常に動作していないフローを迅速に検出する）応答性と（正常に動作していないとして識別される準拠するフローが、できるだけ少ない）ロバスト性の間のトレードオフを設定する際に重要である。ここでは、正常に動作していないとして識別される準拠するフローの割合（つまり誤った肯定判断の割合）がεより小さいままとなるようにするために、どのようにα＊を設定するのかを説明する（εが非常に小さい値、例えば多くても１０−３を取ることが期待される）。
【００９３】
最初に、観察期間が、ｍｊ輻輳が一定であるフローの往復時間Ｔｊである場合にαがどのようにして設定されるべきであるかを示し、その後この結果が監視ノードを通るすべてのフローについての絶対値を与えるためにどのようにして拡張できるかを示す。
【００９４】
一例としてＴＣＰの速度適応機構をマルコフ連鎖としモデル化することの結果として図８は、輻輳レベルｍｊ＝１０−２に対する１つの往復時間ＴｊにわたるＴＣＰ接続の輻輳ウィンドウｃｗｎｄの累積確率分布ｙ＝ｌｏｇ（Ｐ（ｃｗｎｄ＜ε））をログスケールに示す。実質的には、これは基準観察期間が、ＴＣＰフローの往復時間に等しい、すなわちτ＊＝Ｔｊである場合のＴＣＰフローのスループットの期待値である。
【００９５】
監視器に対する要件はτ＊の期間内で誤って肯定判断を行う割合が、εより小さいことであり、したがってα＊は、輻輳ウィンドウが期待平均ｃｗｎｄａｖｇをα＊倍超える確率がεより小さくなるように設定されなければならず、これはＰ（ｃｗｎｄ＞α＊・ｃｗｎｄａｖｇ）＜εによって示される。
【００９６】
図８は、ε＝１０−３のときにα＊を検出する方法を示している。この例では、ｃｗｎｄａｖｇ〜１２．７に対してα＊・ｃｗｎｄａｖｇ〜３５である（平均値はＴＣＰ輻輳ウィンドウをマルコフ連鎖として分析することにより得られる）。これにより、ε＝１０−３に対してα＊〜３となる。これは、期間τ＊の後に、過度要求がα＊より高いフローの少なくとも５０％が、正常に動作していないものと正しく判断されるのに対し、バケット深さが（α＊−αＴＣＰ）・Ｔ＊に設定される場合に、正常に動作していないとして誤って識別されるＴＣＰに準拠するフローは０．１％を超えないことを意味する。観察期間を拡大させると、（監視器の反応性は低下するが）監視器のロバスト性がさらによくなるだろう。
【００９７】
監視器がロバスト性より応答性のために寸法付けられるべき場合、バケットの深さはより低い値に設定されるべきである。
【００９８】
監視器のサンプリングバージョンが（該監視器を流れるトラフィックを監視するために必要なバケット数によって定められる）状態要件を最小限に抑えるように寸法付けられるべき場合、サンプリングパラメータλをより小さくするだけでなく、バケットがより短いと、状態要件が低減する。
【００９９】
各ユーザの輻輳履歴に対する準拠性テストを調整する、さらなる実施形態
最新の期間にユーザによって引き起こされる輻輳の量を追跡調査することによって、上記の問題に取り組むことができる。例えば、期間Ｕｋの契約された使用が分かっている場合に、送信されたデータに起因する輻輳ｍｋの量の記録をユーザごとに保持することができる。さらに、すべてのユーザＵによる総計使用の推定値、及びその結果として生じる輻輳Ｍの推定値も計算されるであろう。サンプリング係数λは、割合（ｍｋ／Ｕｋ）（Ｍ／Ｕ）を考慮に入れて調整されることができる。
【０１００】
例えば、同じサンプリング係数λをすべてのユーザに対して使用するのではなく、ユーザｋのためのサンプリング係数をλｋ＝λ・ｍａｘ｛１，（ｍｋ／Ｕｋ）（Ｍ／Ｕ）｝と定めることができ、これにより、ユーザｋが輻輳「予算」（“ｂｕｄｇｅｔ”）（Ｍ／Ｕ）＊Ｕｋを使い切ったときに、ユーザｋのためのデータｗｏはるかに厳しく監視することができる。
【０１０１】
考えられる変形例
上記の項で、確立された速度制御原理（ＴＣＰ規格）に関して、速度適応がその経路特徴に対応する必要がないフローを検出できる速度監視器の設計を提案した。この機構を、長く用いられており、定常状態にあるＴＣＰフローに対して説明している。定常状態のスループットは準拠するＴＣＰフローが達成できる最大の長期間スループットであるため、実際には監視器は任意のＴＣＰフローに対して効果的となるであろう。しかしながら、監視器は他の準拠基準を使用できる。例えば、長期間のＴＣＰ速度の公式は、Ｋｅｌｌｙの「一定の支払い意志の公式」（上記の方程式（２）を参照すること）に置き換えられるだろう。これは、概略すると各パケットが「支払い意志」フィールドを持っていることを必要とする。
【０１０２】
さまざまなクラスのトラフィックは、さまざまなクラスを使用することによってさまざまな準拠公式に対して試験されることができる。
【０１０３】
付録−トークンバケット機構の分析
付録Ａ１：サンプリングを行わないトークンバケット
提案
バケット内のトークンの量は（αＴＣＰ-αｊ）・τに同等である。
【０１０４】
証明概略：
パケットが到達するたびに、トークンの数はαＴＣＰ・（ｔｊ−ｔｊ−１）だけ増加し、Ｔｉ・√ｍｉ／ｋだけ減少する。時間τの後、バケットは、ｎ（τ）＝Ｎｊ（τ）・τとして、ｓｕｍｉ＝１．．ｎ（τ）（αＴＣＰ・（ｔｉ−ｔｉ−１）−ｔｉ・√ｍｉ／ｋ）を含む。推定値のバイアスは以下の通りである。
【数７】
【０１０５】
ｅｓｔ（Ｔ・√ｍ／ｋ）＝ｓｕｍｉ＝１・・ｎ（Ｔ）（Ｔｉ・√ｍｉ／ｋ）／ｎ（ｔ）によって定義される
したがって、最終的にはｂ＝ｎ（τ）・（１／ｎＴＣＰ−ｅｓｔ（Ｔ・√ｍ／ｋ））となる。
【０１０６】
｜ｂ｜＜εを得るためには、ｎ（τ）・｜１／ｎＴＣＰ−ｅｓｔ（Ｔ・√ｍ／ｋ）｜＜εでなければならない。
【０１０７】
実質的に、等値である“ＸＴＣＰ＝ｋ・ｓ／（Ｔ・√ｍ）ｎ”を用いて書き換えると以下が得られる。
【０１０８】
任意のε１に対し、｜１／ｎＴＣＰ−ｅｓｔ（Ｔ・√ｍ／ｋ）｜＜ε１となるようなτ１が存在する。
【０１０９】
さらに、より長いフローに対して、等値がより強力であることを強調するε１＝Ｏ（１／ｎ（τ））であると仮定すると、以下が得られる。
【０１１０】
任意のε２に対し、｜１／ｎＴＣＰ−ｅｓｔ（Ｔ・√ｍ／ｋ）｜＜ε２／ｎ（τ２）となるようにτ２が存在する。
【０１１１】
ε＝ε２／ｎ（τ２）となるようにτ２を選ぶと、｜ｂ｜＜ε、したがって提案されている等値を得る。
【０１１２】
注記：これは監視器での平均化を必要としない。指数的に重み付けされた移動平均（ＥＷＭＡ）が使用される場合、代わりにｅｓｔ（Ｔ・√ｍ／ｋ）＝ｓｕｍｉ＝１．．ｎ（τ）（ＥＷＭＡ（Ｔｉ・√ｍｊ／ｋ））／ｎ（τ）を定義でき、残りの証明はすべて、ただこれに関連するものである。これは、平均に関しては監視器の性能を改善しないかもしれない。これは、分散に関して、性能に影響する可能性が最も高い。
【０１１３】
付録Ａ２：サンプリングを行うトークンバケット
提案
バケット内のトークンの量は（αＴＣＰ−αｊ）・λ・τに同等である。
【０１１４】
証明概略
非常に類似している。サンプリングされたパケットの数としてＬ（τ）Ｌ（τ）＝ｎ（τ）・λとして定める。
【数８】
【０１１５】
ｅｓｔ（Ｔ・√ｍ／ｋ）＝ｓｕｍｉ＝１・・ｎ（Ｔ）（Ｔｉ・√ｍｉ／ｋ）ｎ（τ）によって定義される
ここでは、ｂ＝λ・ｎ（τ）・（１／ｎＴＣＰ−ｅｓｔ（Ｔ・√ｍ／ｋ））＋ｓｕｍｉ＝１．．ｎ（τ）（λ・Ｔｉ・√ｍｊ／ｋ−ｕｉ）を得る。
【０１１６】
Ａ１に示された理由のために、ε／２＝ε２／ｎ（τ３）となるようにτ３を選ぶことができる。
【０１１７】
さらにτ＞τ４のときに｜ｓｕｍｉ＝１．．ｎ（τ）（λ・Ｔｉ・√ｍｊ／ｋ−ｕｉ）｜＜ε／２であれば、τ＞ｍａｘ（τ３，τ４）のときにｂ＜εが成り立つ。
【図面の簡単な説明】
【０１１８】
【図１】ボトルネック監視器（図１（ａ））と、本発明に従って動作する経路独特の監視器（図１（ｂ））との間の根本的な相違点を概略する。
【図２】旧式の監視器（図２（ａ））と本発明の好ましい実施形態に従って動作する経路独特の監視器（図２（ｂ））との間の監視動作の潜在的な相違点を示すグラフを示す。
【図３】本発明の比較的一般的な実施形態による監視器を示す図である。
【図４】固定深さのトークンバケットのモデルを使用して、本発明の実施形態に従って動作する監視器を示す図である。
【図５】本発明の好ましい実施形態に従って動作する監視器を示す図であり、過度要求は、該監視器の期待スループットに逆比例するトラフィックのサンプリングによって監視される。
【図６】本発明の実施形態に従って動作する監視器により行われるステップを示すフローチャートであり、過度要求はトラフィックをサンプリングしないで監視される。
【図７】本発明の実施形態に従って動作する監視器により行われるステップを示すフローチャートであり、過度要求はトラフィックをサンプリングすることによって監視される。
【図８】本発明の好ましい実施形態に従って動作する監視器を通るＴＣＰフローの期待スループットを示すグラフである。
【技術分野】
【０００１】
本発明は、主にネットワーク内でのデータの制御に関し、及びデータを通信するためのインターネット等のネットワークの使用の監視を可能にする方法及びシステムに関する。
【背景技術】
【０００２】
ネットワーク輻輳に対する責任ある反応の重要性
現在のインターネットアーキテクチャは、しばしば、ホストが自発的に輻輳に対応するよう信頼すること、つまり、一般的に、これらのアルゴリズムが出現する相互信頼の環境のせいにされる過失について批判される。反応しないアプリケーションは、事実上、該アプリケーションが反応のよい流れから、必要とされるボトルネックリソースのどのような割当てをも盗んでいる可能性がある。現在の送信元の大多数はうまく機能していると考えられているが、ただ乗り行為はただ単に不愉快なだけではない。最も人騒がせなことには、現在の協力的なコンセンサスを何が安定させているのかを理解しないまま、無意識に該コンセンサスを不安定にし、戻る道がない輻輳の崩壊を引き起こす可能性がある。しかしながら、反応しないアプリケーションは平均的な帯域幅ごとに、さらに多くの容量の投資を必要とするため、より多くの漸次的な腐食がインターネットの実行可能性を脅かしている。適切に輻輳を管理する、新しいサービスの質を有する（「ＱｏＳ」）製品は、誰もが、必要とされる投資に貢献することなく、どのようにかして必要とするものを取ることができる場合には決して実行可能にはならない。しかしながら、これらの新しいサービスに対する投資はリスクが大きすぎ、なおさらに正常に動作していない（ｍｉｓｂｅｈａｖｉｎｇ）アプリケーションにとってのギャップを生じさせる。したがって、良く動作するアプリケーションは、過少投資と不良行為の悪循環に陥るだろう。
【発明の開示】
【０００３】
反応が鈍い必要のあるアプリケーションもある（双方向音声、ビデオ及びゲーム）。他のアプリケーションは単に自らにプレミアムサービスを提供するために積極的であることを選択する。また、意図的に（ピアツーピアのファイル共有により）、あるいは無意識に（ウィルスに感染しているゾンビホスト）のいずれであるかに関わらず、他のユーザよりも多くのフローで自分のアクセスリンクを継続的に満たすユーザもいる。たとえ各フローの反応がよくても、全体ではさらに多くの輻輳が生じる。
【０００４】
速度適応ポリシーの特徴付け
ＴＣＰ速度制御アルゴリズム［７］は、インターネット上での主要な輻輳の崩壊に応えて１９８０年代後半に開発された。該アルゴリズムは、インターネットを横切るあらゆるフローの速度が、各フローが任意の輻輳したルータ又はリンクの容量を公平に共有する速度に近づくように、該フローが経験した輻輳のレベルに迅速に適応されることを確実にするよう設計された。
【０００５】
ＴＣＰ速度制御アルゴリズムは、送信側ホストのオペレーティングシステム内で実行される。アプリケーションのプログラマは該アルゴリズムを使用するかどうかを選ぶことができる。双方向音声アプリケーション又はビデオアプリケーション等のビットレートの急激な変化に耐えることができないアプリケーションのプログラマはつねに該アルゴリズムを使用しないことを選ぶ。
【０００６】
もともと、ＴＣＰアルゴリズムは、紛失した肯定応答を通して損失を検出することによって、及び肯定応答が到着する前の往復遅延を測定することによって、インターネット全体で使用されている経路を特徴付けていた。最近では、ＴＣＰ／ＩＰ規格は、明示的輻輳通知（ＥＣＮ）をオプションで追加することにより改善され、これにより、初期の輻輳の兆しを経験するルータは、送信する前にパケットにマークを付けることができるであろう。また肯定応答プロトコルは、これらのマークを送信元まで伝達し戻すことを可能にするよう変更された。ＴＣＰアルゴリズムのための規格は、送信側ホストがこれらの返されるマークに、あたかも損失があったかのように応答することを必要とするように改変された。
【０００７】
多くの他の内、Ｐａｄｈｙｅら［１］は、特にＴＣＰフレンドリ速度制御（ＴＦＲＣ、より円滑な適応だけによる、ＴＣＰのウィンドウベースの機構の速度ベースのバージョン）の速度調整のための指針として使用される、定常状態にあるＴＣＰフローの長期平均に対する公式を発展させた［２］。輻輳が小さいまま（ｍ＜＜０．２）であれば、この値は方程式（１）に示されるように、平方根法に近似することが可能である。
【数１】
【０００８】
ここで、ｘはスループットの期待値であり、ｋは√（３／２）のオーダーの定数であり、ｓはフローのパケットサイズであり、Ｔはこのフローの往復時間であり、ｍは（フロー内でマークを付けられ、削除されたパケットの割合によって表されるような）エンドツーエンド輻輳測定基準である。
【０００９】
同時に起こるフローの間で、輻輳ネットワークリソースを割り当てるための他のモデルが存在する。例えば、Ｃｒｏｗｃｒｏｆｔ及びＯｅｃｈｓｌｉｎ［６］は、ω個の平行ＴＣＰフローを模倣するであろう重みパラメータωを用いてＭｕｌＴＣＰと呼ばれるＴＣＰのバージョンを作成することによって、他より多くの容量を使用することがどれほど容易であるのかを示した。Ｋｅｌｌｙら［３］は、インターネットユーザが該ユーザが生成するトラフィックに対する自らの支払い意志を明示する、ネットワークの活用の経済的な最適化に基づいて速度制御アルゴリズムを開発した。ユーザは、交換されるデータ量に関わりなくデータ転送の過程で一定の支出レートを保持するために、速度適応ポリシーを効果的に採用する。データ経路の輻輳ステータスは、転送持続時間を動的に縮小したり、引き伸ばしたりする。このようなポリシーは方程式（２）に示されるスループット方程式によって特徴付けられており、
【数２】
【００１０】
ここで、ｗはユーザの支払い意志パラメータであり、ｘ、ｍ及びｓは上記と同じ意味を有する。
【００１１】
これらの速度制御アルゴリズムのすべては、伝送が伝達される経路の測定基準に依存している。どのような測定基準であれ、該測定基準を特徴付けるための現在の構成は、損失、明示的な輻輳、あるいは往復遅延があるのかどうかに関係なく、受信機と送信機の両者が、該受信機と送信機が通信できる速度を制限することを目的としたプロトコルに誠実に準拠していることに依存している。経路全体の輻輳は、バックチャネルで受信機から送信機に送り返される送信先だけで出現する。しかしながら、どのようなデータネットワークでも、バックチャネルは、本来エンドポイント間の通信であるため、該バックチャネルは中継器に可視である必要はない（該バックチャネルは暗号化されるか、あるいは非対称でルート付けられることができ、あるいは完全に省略されることができる）。したがって、どのネットワーク要素も確実にそれらを傍受することはできない。本出願人による以前の特許出願は、後にＳｉｒｉｓ［８］によって発表された論文に説明されているセルラー無線ネットワークコントローラで具現化された、送信機に送り返される肯定応答を傍受するネットワーク装置上で実行される速度制御機構に関していた（ＷＯ第０３／０４９３１９号を参照すること）。しかしながら、このような機構は、究極的には、受信機が、自らのフィードバックを見えるようにし、該フィードバック中で経路特性を誠実に述べることに依存している。それでも、経路輻輳及び遅延に応えて正しくその速度を変更するためには、送信機にも頼らなければならない。
【００１２】
［１］Ｊ．Ｐａｄｈｙｅ、Ｖ．Ｆｉｒｏｉｕ、Ｄ．Ｔｏｗｓｌｅｙ及びＪ．Ｋｕｒｏｓｅ、「ＴＣＰスループットのモデル化：単純なモデル及びその実験検証（Modeling TCP Throughput:A Simple Model and its Empirical Validation）」、会議録ＡＣＭ ＳＩＧＣＯＭＭ１９９８年
［２］Ｓ．Ｆｌｏｙｄ、Ｍ．Ｈａｎｄｌｅｙ、Ｊ．Ｐａｄｈｙｅ及びＪ．Ｗｉｄｍｅｒ、「ユニキャストアプリケーションのための方程式ベースの輻輳制御（Equation-Based Congestion Control for Unicast Applications）」、会議録、ＡＣＭ ＳＩＧＣＯＭＭ．２０００年８月
［３］Ｆ．Ｐ．Ｋｅｌｌｙ、Ａ．Ｋ．Ｍａｕｌｌｏｏ、及びＤ．Ｋ．Ｈ．Ｔａｎ、「通信ネットワークのための速度制御：潜在価格、比例する公平性と安定性（Rate control for communication networks: shadow prices,proportional fairness and stability）」、オペレーションリサーチ学会誌（Journal of the Operational Research Society）、４９（３）：２３７−２５２ページ、１９９８年
［６］Ｊｏｎ Ｃｒｏｗｃｒｏｆｔ及びＰｈｉｌｉｐｐｅ Ｏｅｃｈｓｌｉｎ、「加重比例公平共有ＴＣＰを使用する差動式エンドツーエンドインターネットサービス（Differentiated End to End Internet Services using a Weighted Proportional Fair Sharing TCP）」、コンピュータ通信レビュー（Computer Communication Review）２８、５３から６９ページ（１９９８年７月）
［７］Ｖａｎ Ｊａｃｏｂｓｅｎ、輻輳回避及び制御（Congestion avoidance and control）、会議録、ＡＣＭ ＳＩＧＣＯＭＭ１９８８年、コンピュータ通信レビュー（Computer Communication Review）１８（４）：３１４−３２９ページ、１９８８年
［８］Ｖａｓｉｌｉｏｓ Ａ．Ｓｉｒｉｓ、ＣＤＭＡネットワークにおける弾性トラフィックのためのリソース制御（Resource control for elastic traffic in CDMA networks）、会議録、モバイルコンピューティング及びネットワークに関するＡＣＭ国際会議（ACM International Conference on Mobile Computing and Networks）、（ＭｏｂｉＣｏｍ２００２年）、ＵＲＬ：http://www.ics.forth.gr/netlab//wireless.html、２００２年９月、ＡＣＭ
速度監視
現在のインターネットでは、万一送信機がＴＣＰ規格で指定されている反応機構に準拠するのをやめた場合には、インターネット上で大混乱を引き起こすであろう。これが、ユーザがネットワーク上でトラフィックの任意の速度を送信する自らの能力を乱用しないようにフローを監視するための複数の提案が作成されている理由である。
【００１３】
前述されたように、インターネットのネットワーク要素は現在では、送信機がＴＣＰプロトコルに準拠していることを検証するために、経路についての関連する測定基準を知ることができない。（例えばＳａｎｄｖｉｎｅ(www.sandvine.com）又はＲｉｖｅｒｈｅａｄ Ｎｅｔｗｏｒｋｓ（www.riverhead.com）からの）市販の監視器（policers）は、ネットワークの残りで使用されている各経路の状態に関係なくフローが最大速度を超えないことを確実にする。このような監視器には、装置自体における局所的な輻輳についての自らの知識を使用できるが、他の場所については使用できない。
【００１４】
実際には、これらの市販されている監視器［４、５、１２、１３、１４、１５、１６］によって必要とされる状態の量を削減する、提案されている監視器が動作するためには、自らが輻輳している中継器上に置かれなければならない。「ボトルネック監視器（ｂｏｔｔｌｅｎｅｃｋ ｐｏｌｉｃｅｒｓ）」と呼ぶところの、これらの監視器の全ては異常に高いビットレートを検出するが、経路が輻輳していない場合、あるいは往復時間が短い場合には完全に筋が通っている高送信速度は検出しない。同様に、最新のブロードバンドリモートアクセスサーバ上の他の監視器は、高容量のファイル共有を制御するために月次量上限を施行する。しかしながら、このような監視器は、使用中にピークを引き起こすほど多くのトラフィックでトラフ（ｔｒｏｕｇｈ）を満たすトラフィックを処罰する。
【００１５】
Ｆｌｏｙｄ及びＦａｌｌ［４］は、無作為早期検出（ｒａｎｄｏｍ ｅａｒｌｙ ｄｅｔｅｃｔｉｏｎ，ＲＥＤ）機構に基づいたペナルティボックス機構を提案している。ＲＥＤは、インターネットルータで幅広く使用されている待ち行列管理機構であり、回線に対する出力待ち行列が長いほど、待ち行列に到達するパケットが廃棄される（ＥＣＮがイネーブルされている場合にはマークを付ける）確率が高くなる。Ｆｌｏｙｄ及びＦａｌｌの考えは、ＲＥＤアルゴリズムの廃棄履歴を監視することである。十分長い期間の後に、廃棄履歴に多く現れるいかなるフローも、正常に動作していいないと見なされ、ブラックリストに載せられ、適切な処分（削除、降格（declassing）、…）のために提示される。ＣＨＯＫｅ［５］も、極めて正常に動作していないフローは、準拠しているＴＣＰフローよりデータストリーム内にはるかに多く出現するという考えを利用している。パケットが到着するといつでも、該パケットは待ち行列から無作為に選ばれた別のパケットと比較される。該２つが同じフローからである場合、そのフローは正常に動作していないことが疑われる。ＣＨＯＫｅは異常に高速のトラフィックを押さえ込むことに非常に優れた結果を示している。
【００１６】
多くの研究提案は、Ｆｌｏｙｄ及びＦａｌｌ［４］によって初めに提案された速度監視のための技法に増分的な改善を加えたものである。安定化されたＲＥＤ（ＳＲＥＤ［１２］）が並行して発表され、後の改善策にはＣＨＯＫｅ［５］、優先的廃棄（Ｐｒｅｆｅｒｅｎｃｅ Ｄｒｏｐｐｉｎｇ）ＲＥＤ（ＲＥＤ−ＰＤ［１３］）、最小最近使用（Ｌｅａｓｔ Ｒｅｃｅｎｔｌｙ Ｕｓｅｄ）ＲＥＤ（ＬＲＵ−ＲＥＤ［１４］）、ＸＣＨＯＫｅ［１６］、及び近似公平廃棄（Ａｐｐｒｏｘ． Ｆａｉｒ Ｄｒｏｐｐｉｎｇ）（ＡＦＤ［１５］）が含まれる。
【００１７】
しかしながらすべての場合において、速度は経路の特定の特徴とは関係なく監視される。例えば、１つの共通のボトルネックをわたる２つのフローを考えてみる。短い往復時間のフローＡは、それ以外にはほとんど輻輳していない経路を通過するのに対し、フローＢは４倍長い往復時間を有し、該フローの経路上で４倍多くの輻輳を経験する。長期的には、フローＢは、フローＡが取得する帯域幅の８分の１だけ取得するべきである。それにも関わらず、すべての既存の監視器を用いると、監視器自体を収容するネットワーク要素上ではないどこかに輻輳がある場合、両方のパケットは等しく責任があると見なされるため、フローＡはフローＢよりはるかに制約される可能性が高い。
【００１８】
Ｃｌｅｒｇｅｔ及びＤａｂｂｏｕｓ［１７］は、別の種類の分散速度監視を提案している。Ｃｌｅｒｇｅｔ及びＤａｂｂｏｕｓの提案しているフレームワーク、「タグベースの統一公平性（Tag-based Unified Fairness）」（ＴＵＦ）では、既定のタイプの流れがすべてボトルネック帯域幅の同じ割当てを取得するように、ボトルネックがトラフィックを監視する。該ＴＵＦ方式は、クラス内の公平性を保証できるが、クラス間の公平性は保証できない。つまり、ｎ＿ＴＣＰ個のＴＣＰフローとｎ＿ＵＤＰ個のＵＤＰフローがボトルネックを共有する場合、
ｎ＿ＴＣＰ＊ｘ＿ＴＣＰ＋ｎ＿ＵＤＰ＊ｘ＿ＵＤＰ＝Ｃ
となるように、各ＴＣＰフローは割当てｘ＿ＴＣＰを取得し、各ＵＤＰフローは割当てｘ＿ＵＤＰを取得する。ここで、Ｃはノードの送信容量であるが、２つの非常に独特のレベル以外の任意のレベルの輻輳に対して、ｘ＿ＴＣＰ ！＝ｘ＿ＵＤＰである。さらに、ＴＵＦ方式は、クラス間公平性を達成しないことに加えて、ボトルネック監視制限器の弱点も示す。
【００１９】
また、従来の技術では、Ｒａｉｓｉｎｇｈａｎｉ及びＩｙｅｒ［１８］が、廃棄は経路の最終的な無線セクションですべて引き起こされると仮定して、フローが目指すべき達成可能な輻輳ウィンドウを制御することによって、受信機が、受信機のフローに動的に優先順位を付ける機構を開示している。これは、フロー間輻輳制御の問題に関係し、該受信機のフロー間の優先順位を調整するために受信機が輻輳信号をいじるものと考えられる。この文書は、ＲＥＤでの別の単独ボトルネック公平性最適化であるＲＥＤ−ＤＴの説明を含んでいる。該最適化は、待ち行列の長さ、バッファサイズ、及び、すべて該ノード独特の多くのフローごとの変数等の局所情報（つまり、考慮しているノードにとって局所）にだけ依存している。
【００２０】
さらなる従来の技術の文書、Ｎｉｋｏｌｏｕｚｏｕら［１９］は、一般的な差別化サービス（ＤｉｆｆＳｅｒｖ）構成を説明し、ＤｉｆｆＳｅｒｖ環境における特定のネットワークサービスの定義及び配備に取り組んでいる。
【００２１】
最近、データ送信元が高容量ネットワーク全体でどれほど高速にデータを送信できるのかを、該データ送信元の速度制御アルゴリズムが迅速に突き止めることができるようにするための提案がなされている。これらの提案では、該送信元はプロトコルフィールドに要求を入れる。ＸＣＰ［１１］では、要求は、なんらかの肯定応答が受信される前にどれほど多くのデータを送信できるのかに関している（飛行中のデータの量、又は輻輳ウィンドウと呼ばれる）。クイック−スタート［１０］では、フィールドは送信速度に関するものである。パケットがネットワークを横切るとき、ルータが許容できる測定基準の値が要求未満である場合、ルータは該フィールドを書き直す。しかしながら、結果として生じるフィールドは依然として送信機に返されなければならず、送信機は該送信機の将来の速度が該送信機の要求に対するネットワークの応答に準拠することを保証しなければならない。したがって、両方の方式とも、依然として、送信機と受信機自体の関心に逆らって該送信機と受信機の協力に依存している。該ルータは、該ルータが従前のラウンドで与えた応答を覚えており、次に送信元が準拠しているかをチェックすることができるが、これにはフローの状態がルータで保持されることが必要とされ、インターネットのパケット送信特徴である、処理状態を把握しないコネクションレスモデルの利点を失う。
【００２２】
ＡＴＭ等の接続指向ネットワークでは、ネットワーク要素は各接続に沿って輻輳バックプレッシャーメッセージ［９］を送信するが、該要素は接続指向ネットワークを信頼しないため任意のエンドツーエンドフィードバックを重複する。しかしながら、コネクションレスデータグラムネットワークにおいて、低い接続セットアップ待ち時間及びパケットネットワークのロバスト性という利点を失うことなく同様の技法を使用することは本質的に困難である。
【００２３】
参照として主題が本明細書に組み込まれている、公開番号ＷＯ２００５／０９５６６を有する、本出願人によって出願された同時係属出願では、「リ−フィードバック」と名付けられた新規のフィードバック機構が提案され、この用語は「受信機−正規化（Ｒｅｃｅｉｖｅｒ−Ｎｏｒｍａｌｉｓｅｄ）」フィードバックという考えを示している。リ−フィードバック機構によると、送信機が、任意の経路を特徴付けるフィールドの初期値を設定し、該送信機が経路情報を蓄積するまでに、該フィールドが一般的に標準化された値に設定された目的に到達する傾向がある。送信先からの送信元へのフィードバックは、次に、将来データが送信されるときの目的の値に対する誤差を継続的に訂正するよう使用される。主な優位点は、伝送経路に沿ったインライン装置による使用のために、データが、該データとともに、該データの下流経路の「予測」を効果的に搬送するという点である。
【００２４】
さらに、やはり参照として主題が本明細書に組み込まれている、公開番号ＷＯ２００５／１０９７８３を有する、同出願人によって出願された別の同時係属出願では、パケットの中の下流経路測定基準（例えば、輻輳又は遅延）が永続的に負ではないことを保証するためにトラフィックを傍受するであろう新規の廃棄監視器が提案された。該監視器は、パケット切捨て又は廃棄等の処分を使用した。これら２つの出願の発明の実施形態はともに、ネットワーク間をまたぐ伝送中に経験された輻輳及び遅延に比例して減分された後にも該フィールドが正のままとなるように十分に高い値を、各パケットの経路測定基準フィールドの中に、送信機が、必ず「あらかじめロード（ｐｒｅ−ｌｏａｄ）」することを保証するために使用されることができる。
【００２５】
［４］Ｓ．Ｆｌｏｙｄ及びＫ．Ｆａｌｌ、「インターネットにおけるエンドツーエンド輻輳制御の使用促進（Promoting the Use of End-to-End Congestion Control in the Internet）」、ＩＥＥＥ／ＡＣＭネットワーキングに関する会議記録、１９９９年５月
［５］Ｒ．Ｐａｎ、Ｂ．Ｐｒａｂｈａｋａｒ、及びＫ Ｐｓｏｕｎｉｓ、「ＣＨＯＫｅ―公平な帯域幅割当てを近似するための処理状態を把握しないアクティブ待ち行列管理方式（A statelss active queue management scheme for approximating fair bandwidth allocation）」
［９］「Ｂ−ＩＳＤＮにおけるトラフィック制御及び輻輳制御（Traffic control and congestion control in B-ISDN）」。推奨策Ｉ．３７１（０３／０４）、ＩＴＵ−Ｔ、ＵＲＬ：http://www.itu.int/rec/recommendation.asp?type=folders&lang=e&parent=T-REC-I.371、２００４年３月
［１０］Ａｍｉｔ Ｊａｉｎ、Ｓａｌｌｙ Ｆｌｏｙｄ、Ｍａｒｋ Ａｌｌｍａｎ、及びＰａｓｉ Ｓａｒｏｌａｈｔｉ、「ＴＣＰ及びＩＰのためのクイック−スタート（Quick-Start for TCP and IP）」。インターネット草案ｄｒａｆｔ-ａｍｉｔｑｕｉｃｋ−ｓｔａｒｔ−０３、インターネットエンジニアリング作業部会（Internet Engineering Task Force）、ＵＲＬ：http://www.icir.org/floyd/quickstart.html、２００４年９月（進行中の研究）
［１１］Ｄｉｎａ Ｋａｔａｂｉ、Ｍａｒｋ Ｈａｎｄｌｅｙ、及びＣｈａｒｌｉｅ Ｒｏｈｒｓ、「高帯域幅−遅延製品ネットワーク用輻輳制御（Congestion control for high bandwidth-delay product networks）」、会議記録、ＡＣＭ ＳＩＧＣＯＭＭ２００２年、コンピュータ通信レビュー（Computer Communication Review）、３２（４）：８９−１０２、２００２年１０月
［１２］Ｔｅｕｎｉｓ Ｊ．Ｏｔｔ、Ｔ．Ｖ．Ｌａｋｓｈｍａｎ、及びＬａｒｒｙ Ｈ．Ｗｏｎｇ、「ＳＲＥＤ：安定化ＲＥＤ(ＳＲＥＤ：Ｓｔａｂｉｌｉｚｅｄ ＲＥＤ)」、会議記録、コンピュータ通信に関するＩＥＥＥ会議（IEEE Conference on Computer Communications（Ｉｎｆｏｃｏｍ１９９９年）中、１３４６から１３５５ページ、ＵＲＬ：http://citeseer.nj.nec.com/ott99sred.html、１９９９年３月、ＩＥＥＥ
［１３］Ｒａｔｕｌ Ｍａｈａｊａｎ、Ｓａｌｌｙ Ｆｌｏｙｄ及びＤａｖｉｄ Ｗｅｔｈｅｒａｌ、「輻輳ルータにおける高帯域幅フローの制御（Controlling high-bandwidth flows at congested router）」、会議記録、ネットワークプロトコルに関するＩＥＥＥ国際会議（IEEE International Conference on Network Protocols）（ＩＣＮＰ２００１年）、URL:http://citeseer.nj.nec.com/545435.html、２００１年
［１４］Ｓｍｉｔｈａ Ａ．Ｌ．Ｎａｒａｓｉｍｈａ Ｒｅｄｄｙ、「ＬＲＵ−ＲＥＤ：輻輳ルータにおける高帯域幅フローを含むためのアクティブ待ち行列管理方式（LRU-RED:An active queue management scheme to contain high bandwidth flows at congested routers）」、会議記録、Ｇｌｏｂｅｃｏｍｍ２００１年、URL:http://citeseer.nj.nec.com/473674.html、２００１年１１月
［１５］Ｒｏｎｇ Ｐａｎ、Ｌｅｅ Ｂｒｅｓｌａｕ、Ｂａｌａｊｉ Ｐｒａｂｈａｋｅｒ、及びＳｃｏｔｔ Ｓｈｅｎｋｅｒ。「差分廃棄による近似公平性（Approximate fairness through differential dropping）、コンピュータ通信レビュー（Computer Communication Review）、３３（２）：２３−４０、２００３年４月
［１６］Ｐ Ｃｈｈａｂｒａ、Ｓ．Ｃｈｕｉｇ、Ａ Ｇｏｅｌ、Ａ Ｊｏｈｎ、Ａ Ｋｕｍａｒ、Ｈ Ｓａｒａｎ及びＲ Ｓｈｏｒｅｙ、「ＸＣＨＯＫＥ：インターネットゲートウェイにおける輻輳回避のための悪意のある送信元の制御（XCHOKE:Malicious Source Control for Congestion Avoidance at Internet Gateways）」、会議記録、ＩＣＮＰ、２００２年１１月
［１７］Ａｎｔｏｉｎｅ Ｃｌｅｒｇｅｔ及びＷａｌｉｄ Ｄａｂｂｏｕｓ：「ＴＵＦ：タグベースの統一公平性（TUF:Tag-based Unified Fairness）」、コンピュータ通信に関するＩＥＥＥ ＩＮＦＯＣＯＭ会議（IEEE INFOCOM Conference on Computer Communications）の会議記録、２００１年４月
［１８］Ｖｉｊａｙ Ｒａｉｓｉｎｇｈａｎｉ及びＳｒｉｄｈａｒ Ｉｙｅｒ：「公平なルータが存在する場合の受信機ウィンドウ制御の分析(Analysis of receiver window control in the presence of a fair router)」、個人通信及び無線通信に関するＩＥＥＥ国際会議（IEEE Intl.Conf.on Personal and Wireless Communications）、２００５年1月
［１９］Ｎｉｋｏｌｏｕｚｏｕ、Ｍａｎｉａｔｉｓ、Ｓａｍｐａｔａｋｏｓ、Ｔｓｅｔｓｅｋａｓ及びＶａｎｉｅｒｉｓ：「差別化されたサービスアーキテクチャにおけるネットワークサービスの定義及び配備（Network Services Definition and Deployment in a Differentiated Services Architecture）」、通信に関する国際会議(IEEE Intl.Conf.on Communications)２００２年
前述されたように、既存の監視方法によれば、速度は経路の特殊な特徴とは関係なく監視される。このため、既存の監視器は、自らの応答性（つまり、正常に動作していないフローを迅速に検出する能力）、自らのロバスト性（つまり、準拠するフローを、正常に動作していないとして識別する数をできるだけ少なくし、これによる「誤った肯定判断」を回避する能力）、及び特にこれらのような特徴の間のトレードオフを含む特定の監視特徴を最適化するための機会を自ら否定している。
【００２６】
本発明の第１の態様によると、データネットワーク内でフローを監視する方法が提供され、前記データネットワークは、基準速度適応ポリシーが関連付けられたネットワークサービスを提供し、前記方法は、
ノードを通るフローの過度要求(greediness)の基準を決定するステップと、
前記過度要求の基準を、許容できる過度要求を示す基準と比較するステップと、
前記過度要求が前記許容できる過度要求に従うものでない場合に、考えられる処分のために前記フローを指定するステップと、を備え、
許容できる過度の要求を示す前記基準は、前記ネットワークサービスと関連付けられた基準速度適応ポリシーに準拠し、実質的に同様の経路状態を経験するフローの期待される過度要求に依存して決定されることを特徴とする。
【００２７】
本発明の関連する態様によると、データネットワーク内でフローを監視する装置も提供され、前記装置は前記第１の態様による方法を実現するための前記ステップを実施するための手段を備える。
【００２８】
データネットワーク内のフローは、一般的には、複数のメッセージを備えると考えられ、これらは、問題にしているネットワーク及び／又はプロトコルに適用可能な個々のデータ搬送項目である。このような監視方法が、現在のインターネットプロトコル（ＩＰ）に関連して使用される場合、メッセージは一般的にＩＰパケットとなることが理解される。
【００２９】
（公開番号ＷＯ２００５／０９６５６６である前述された同時係属出願において、可能であることが示されたように）メッセージ又はパケット内のフィールドがメッセージ又はパケットの下流経路の予測を搬送するネットワーク要素に達すると、これらのフィールドを使用して、メッセージ又はパケットが到達すべき速度を監視することがさらに可能になる。公開番号ＷＯ２００５／１０９７８３である前述された同時係属出願に説明されたように、廃棄器（ｄｒｏｐｐｅｒ）がネットワーク間の遠隔出口（remote egress）に位置する場合、送信機が下流輻輳又は遅延を低く評価しないように強制する、説得する、あるいは少なくとも奨励することが可能になる。
【００３０】
ホストベースの速度制御アルゴリズムは、送信速度を決定する各フローの経路の最新の状況についての状態を保持する。例えば、ＴＣＰは輻輳ウィンドウ変数を保持するが、ＴＣＰフレンドリ速度制御及びＫｅｌｌｙのアルゴリズムは現在の送信速度を有する変数を保持する。
【００３１】
いったん経路特徴付けが各パケットの中で、ネットワーク要素に達すると、該要素はそれ自体の経路状態を各フローに対して保持できる。次に、該要素は、どれほど高速にフローを送信する必要があるかの独自の見通しを導くことができる。該要素は、パケットをバッファに入れることによって該フローの速度を形成するために該見通しを使用できるが、監視（policing)と呼ばれるように、該送信元が変化する経路に応じて該送信元の速度を正しく適応させているかどうかを単にチェックすることが好ましい。フロー単位の状態がネットワーク要素で保持されることを必要とする方式はあまり好ましくないことを既に述べた。しかしながら、エッジアクセスルータは、既に（カスタマの許容最大速度等の）各アクセスカスタマの状態を保持しているので、エッジアクセスルータがフローごとの状態を保持するのは、比較的問題にはならないであろう。
【００３２】
同様に、Ｆｌｏｙｄ及びＦａｌｌによって提案されているようなボトルネック監視アプローチ（上記の［４］を参照）は、複数のボトルネックをわたるフローのスループットを監視することはできないために、該ボトルネック監視制御アプローチをとることは十分ではない。さらに、ＣｌｅｒｇｅｔらのＴＵＦアプローチ（上記の［１７］を参照）は、適切なクラス間公平性を提供しない。本発明の実施形態による提案された経路独特のアプローチは、既定のネットワークサービス上で送信されるすべてのトラフィックが、同じ基準、に対して、ベンチマークテストされることができることを保証することによってこれらの欠点に対処できる。該同じ基準は、すなわち、準拠するフローが、該ネットワークサービスについて合意された速度適応ポリシー（例えばＴＣＰ速度適応）について有するであろうスループットである。
【００３３】
図１は、ボトルネック監視器（図１（ａ））と、本発明者らが提案する経路独特の監視器（図１（ｂ））の相違点を概略している。同じ概念は他の測定基準にも使用できるが、特に輻輳測定基準について相違点を説明する。局所的な輻輳ｍ１、ｍ２、ｍ３、ｍ４を有する４つのネットワークノードをわたる、送信元Ｓと送信先Ｄの間のフローを考える。監視ノードは、輻輳の局所的レベル「ｍｉ」及び該ノードが監視を実行する情報「ｙ」とともに表されている。ノードが通過させることを目的とするスループットを「ｘ（ｙ）」と定める。
【００３４】
ボトルネック監視器の場合、ｙ＝ｍｉであり、監視器があらゆる潜在的なボトルネック、つまり経路上のあらゆるルータで必要とされていることを意味する。各ボトルネック監視器の作用は以下の通りであり、
ｘｉ＝ｍｉｎ（ｘｉ−１、ｘ（ｍｉ））
したがって、全体的な作用はｘｎ＝ｍｉｎ（ｘ0、ｘ（ｍ１）、ｘ（ｍ２），．．．，ｘ（ｍｎ））となる。さらに、ｘ（ｍ）が減少関数であり、したがって
ｍｉｎ（ｘ（ｍｉ））＝ｘ（ｍａｘ（ｍｉ））
であり、したがって全体的な作用は最悪のボトルネック単独の作用であることを意味することに留意すべきである。
【００３５】
他方、経路独特の監視器の場合、ｙ＝Ｍ、つまりエンドツーエンド輻輳レベルである。この場合、各ネットワークノード（ｘ0、ｘ１，．．．ｘ４）でのスループット調整の代わりに、ｘｓからｘＤまでの潜在的なスループット調整のみが行われる。
【００３６】
経路独特の解決策の状態要件を低減するために、以下で、より少ない状態を必要とする本発明の代替実施形態を説明する。どれほど多くの状態を保持すべきかと、どれほど速く監視器が正常に動作していないフローを検出できるのかの間でトレードオフが行われてもよい。正常に動作していないフローは、同じ経路状態を与えられた準拠しているフローが使用するよりはるかに多い帯域幅を使用するフローとして定義することができる。本発明の好ましい実施形態によると、ストリーム内のパケットのフロー説明を、該フローの期待スループットに反比例する確率で記録することによって、正常に動作していないフローを検出することが提案されている。方程式（１）（上記を参照）は、どのように期待スループットが決定され得るかの一例として使用されるものであり、パケットから取得される経路独特の特徴付け値に基づいていることに留意する。フローが、該フローの速度適応において、許されている、あるいは許容できると見なされているより一貫して多く要求する（ｇｒｅｅｄｙ）場合、該フローはかなり頻繁にポーリング記録に出現し、おそらくさらなる調査期間の後に（単に警告としてのマーキングを伴う場合もあるが、降格、削除等のさらに懲罰的な処置を含む場合もある）処分のために１つずつ選び出される。
【００３７】
許可されている速度適応アルゴリズムはＴＣＰの標準的なものであってよいし、あるいは代わりに、ＭｕｌＴＣＰ又はＫｅｌｌｙのもののような送信機と進入（ｉｎｇｒｅｓｓ）ネットワークオペレータの間で合意された何らかの他のアルゴリズムであってもよい。これらの後者の場合には、重み付けパラメータω又は支払い意志パラメータｗは、送信機と進入ネットワークとの間の合意の一部でなければならない可能性がある。このパラメータはトラフィックのクラスと、特定のフロー識別子と、特定のタイプのアクセスインタフェースと、又はパケットのいくつか又はすべてで搬送されるなんらかのフィールドと関連付けられるであろう。この合意は、パラメータが必要とされるときに、信号で伝えられてもよいし、あるいは長期にわたる契約により合意されてもよい。
【００３８】
好ましい実施形態を、従来の技術の方式異ならせている特殊な態様とは、正常に動作していないフローが、該フローの絶対スループットのためだけで特徴付けられるのではなく、準拠しているフローがデータ経路上の同じネットワーク状態で取得するであろうスループットを基準にしたスループットで特徴付けられるという点である。これは、処分を行うべきフローを選択する際にはるかに正確である。
【００３９】
各フローが輻輳に応答することを保証する上記の機構に加えて、追加の機構が、好ましくは、各フローではなく各送信ユーザの単位で動作する必要がある。「ユーザ単位の」カウンタは、ポーリング記録のために確率的に選択されたパケットからのすべての輻輳値の累積合計を保持しなければなければならない。その結果、このカウンタは、より多くの輻輳を引き起こすユーザに対してより厳しく「フロー単位の」アルゴリズムを重み付けするために使用できる。
【００４０】
この追加がないと、ユーザは、単に、単一の正常に動作していないフローを、同じ送信先への複数の正常に動作するフローに分割するだけでフロー単位の監視器を迂回できるであろう。また、２つの送信者が、つねにフローが準拠していることを保証する場合であっても、一方は準拠しているフローで連続して送信機のアクセス回線を満たしているのに対し、他方は時折のユーザである可能性がある。
【００４１】
監視器の長期の挙動に対する厳密性のこの適応は、大量需要家（ｈｅａｖｙ ｕｓｅｒｓ）は依然として高速で送信できるが、輻輳が低い、あるいは経路が短い経路の中だけに送信できることを保証する。それに対して少量需要家（ｌｉｇｈｔ ｕｓｅｒｓ）はつねにフルＴＣＰ速度で送信するのを許される。これは、処分を決定するために、測定基準として、（使用のピークの間に送信されるか又はトラフ間に送信される）データ量を使用し、（たとえ輻輳していない経路に送信する場合にも）処分としてデータアクセス速度を制限する、本出願人によって出願された別の同時係属出願すなわち、公開番号ＷＯ２００５／０３２０６８に述べられている方式の実施形態を使用して可能であることに対する有利な相違点につながる。
【００４２】
上述されたように、「リ−フィードバック」の概念を使用することによって、修正されないコアルータ及び境界ルータ全体で変更されないＩＰを使用して、単にネットワーク層ヘッダを検査するだけで、ＴＣＰが対応すべきように輻輳に対応しないトラフィックをネットワーク入口で検出し、削除することが可能であることを示した。このように、インターネットサービスプロバイダがＶｏＩＰ又はビデオについての料金請求を希望する場合、ユーザは、料金請求を回避するために、（例えば、暗号化された「スカイプ（Ｓｋｙｐｅ）」ピアツーピア―www.skype.comを参照すること―を使用して）ベストエフォート型のトラフィックにユーザの反応しないトラフィックを隠すことにより利益を得られることを妨げることができる。
【００４３】
このような問題を克服するためには、Ｓａｎｄｖｉｎｅ又はＲｉｖｅｒｈｅａｄ Ｎｅｔｗｏｒｋｓ（上記を参照）等のベンダから入手できるような速度監視器を使用することは十分ではない。速度を制限し、したがってより低い層のカスタマがネットワークから引き出すことができる値を制限できることは確かに望ましい。しかし、このような制限は、最良の条件における最大を表すものである。すべてのカスタマがネットワークから引き出す値を最大限にするため、及び収益と他のネットワークとの相互接続の費用とのバランスを取るために、許容される速度はさらにネットワーク間の全体又は関連性のある部分での経路状態に依存してしまう。。
【００４４】
また、正常でない動作（misbehaviour）は、パケットが搬送するデータではなく、該パケットが到達する速度に関係し得るため、正常に動作していないフローを検出するためにディープパケットインスペクション（Deep Packet Inspection（DPI））を使用することは十分ではない。パケットは自らをＴＣＰとしてラベルを付けても、ＴＣＰアルゴリズムに従って動作しないこともできる。同様に、パケットは自らをＵＤＰ、スカイプなどとしてラベルを付けても、ＴＣＰにフレンドリなアルゴリズムを使用して送信されることができる。
【００４５】
本発明の好ましい実施形態による監視器を使用すると、例えば日数で測定される期間にわたって累積的に、人間が引き起こす、より多くの輻輳をより激しく押し戻すことが可能になる。したがって、ｐ２ｐファイル共有等の高帯域幅活動のためのネットワークの使用は、ネットワークエッジでピークから離れるようにトラフに押し込まれることができる。
【００４６】
さらに、前述された「リ−フィードバック」概念と、必要な場合に結合され、本発明の好ましい実施形態によるエッジネットワーク装置は、単にＴＣＰだけではなく任意の所望される輻輳応答を監視することができ、それによってインターネットのまさにエッジにおいてだけで監視を実施することによってプロバイダ間のＱｏＳを実施することができる。
【００４７】
本発明の好ましい実施形態は、ここでさらに詳細に添付図面に関して説明される。
【発明を実施するための最良の形態】
【００４８】
潜在的な悪用者の検出
定義及び表記
「リ−フィードバック」ネットワーク内のノードを考える。フロー１．．．ｊ．．Ｊは、時間ｔ＝０とｔ＝τの間にパケット１．．ｉ．．Ｎｊを送信し、観察期間を特徴付ける。暗に表記ＪとＮｊはτに依存するものであることを示す。送信元がペイロードデータで飽和し、そのため、送信元が準拠し、正常に動作する（ｂｅｈａｖｉｎｇ）送信元に対する速度適応ポリシーに従って、あるいは正常に動作していない送信元に対する送信元の過剰な帯域幅使用応じて、送信元が可能な限り多くのパケットを送信する状況を検討する。
【００４９】
Ｘａｐｐ、すなわち、期間τにわたるフローｊの見かけのスループットを、方程式（３）によって与えられるように、観察期間にわたって送信されるデータ量の割合として定め、
【数３】
【００５０】
ここで、Ｓｊ，ｉとＴｊ，ｉはフローｊのパケットｉのサイズと到着時刻である。
【００５１】
今日のインターネットでは、ほとんどのフローはＴＣＰに準拠していることが期待でき、該フローの長期スループットが長い間同じ経路状態を経験している並列のＴＣＰフローの長期スループットを超えることは絶対に期待できないであろう。このＴＣＰ同等速度は、方程式（１）によって与えられるものであり、ここに再度方程式（４）として示す。
【数４】
【００５２】
ここで、ｓ、Ｔ及びｍはそれぞれ、パケットサイズ、往復時間、及びエンドツーエンド輻輳レベルの、期間τにわたる平均値であり、ｋＴＣＰ＝１／√１．５である。
【００５３】
将来、他の速度適応ポリシーが一般的となる可能性があり、その場合、経路及びフロー特性に関して、異なる長期期待スループットの表現ｘ＃＝ｆ（Ｔ，ｍ，ｓ）が得られるであろう。
【００５４】
ｘ＃を、フローが辿る経路の状態に関してトラフィックを監視するための基準準拠速度として使用し、ここで、＃は、そのクラスに使用される速度適応ポリシーを示すものであり、トラフィックｘＴＣＰポリシーは、ｘ＃の特殊な場合である。
【００５５】
Ｋｅｌｌｙによって定義される、このような速度適応のその他の例は、一定の料金を支払う意志のあるユーザを前提としており、フローにおいて検出される輻輳点ごとに固定料金を請求できる状況を前提としている。このような速度適応ポリシーを使用するフローの期待長期スループットは方程式（２）（前記参照）によって特徴付けられる。
【００５６】
最終的に、フローの見かけの過度要求（ｇｒｅｅｄｉｎｅｓｓ）αｊを、方程式（５）に示されるように、フローの見かけの速度Ｘａｐｐとこの期待準拠速度ｘ＃の比として定める。
【数５】
【００５７】
フローが監視される速度適応ポリシーに準拠するフローの、期待される過度要求は１であることに留意する。
【００５８】
経路独特の監視を実行するために、準拠する過度要求α＃と上限過度要求α＊も定義する。フローｊの過度要求αｊが基準期間τ＊より長い期間、α＊に達する場合、該フローは準拠していないと見なされ、さらなる調査、処分が行われる。
【００５９】
一般性を失うものではないが、表現を簡略にするため、本文書の残りでは、ＴＣＰ速度適応との関連だけで監視器を説明し、したがってｘ＃＝ｘＴＣＰ及びα＃＝αＴＣＰと設定する。
【００６０】
経路独特の監視器の設計
監視器の一般的な目的
図３は、監視器の目的を概略する。該監視器は、見かけの過度要求αｊが期間τ＊の間、上限α＊より高い任意のフローにフラグを立てなければならない。フローｊは速度Ｘａｐｐで監視器に到達する。監視器の作用は、フローが正常に動作しているか（αｊ＜α＊）か、あるいは正常に動作していないか（αｊ＞α＊）を特定し、この情報に基づいてフローのその後の処理を分けることである。
【００６１】
ＸＴＣＰの値はフローごとに保持されなければならず、パケットが受け取られるときはいつでも更新することができる。例えば、ＸＴＣＰは方程式（４）によってリ−フィードバックフィールドからの各パケットについて得ることができる。以下に、フロー単位のαｊを監視し、期間τ＊の間、上限α＊より高い過度要求を持ったフローを処分すべく分けるためのいくつかの機構を説明する。
【００６２】
フローの正確な定義が未決のままにされていることに留意する。好ましくはフローの定義は、送信元アドレスと送信先アドレス及びポートで特定される、エンドツーエンド接続のパケットとなるであろう。フローの定義は、このような接続の集合体であってもよい。例えば、監視器の所定のインタフェースに入信し、所定のＩＰプレフィックスに向けて送信されるすべての接続である。
【００６３】
「ボトルネック監視器」として前記に参照されたタイプの１つであり得る、現在の「旧式の（ｃｌａｓｓｉｃ）」監視器に対する相違点が図２に概略されている。現在まで、監視器は、疑わしいフローを、該フローが辿る経路の状態（伝送遅延、輻輳・・・）に関係なく、該フローの見かけの速度だけに基づいて１つずつ選び出す。これは、経路独特の速度適応ポリシーに従うフロー、及び特に現在のインターネットトラフィックの大多数を構成するＴＣＰフローを監視する上で効率的ではない。図２は、この違いを示している。
【００６４】
（例えば、長い往復時間及び／又は高輻輳によって特徴付けられる）不良経路状態を経験する高速フローは旧式の監視器（図２（ａ））及び経路独特の監視器（図２（ｂ））の両方で捕らえられ、（各図のゾーン１を参照すること）、及び良好な経路状態を経験する低速フローも両方の場合で通される（ゾーン２）が、旧式の監視器はフローの以下の２つのカテゴリを間違って特徴付けるであろう。
【００６５】
−ゾーン３において、絶対的にはそれほど高くないが、それでも、好ましくない経路状態を考慮すると高すぎるスループットを有するいくつかのフローを、旧式の監視器は、正常に動作していないと分類しないであろうが、経路独特の監視器はそのようなフローを捕らえるであろう。
【００６６】
−ゾーン４では、絶対的には非常に高いが、非常に好ましい経路状態を考えると完全に許容できるスループットを有するいくつかのフローを、旧式の監視器は正常に動作していないと分類するであろうが、経路独特の監視器はそのようなフローを通過させるであろう。
【００６７】
別の重要な相違点は、既存の監視器はネットワーク内のすべての潜在的な輻輳点に配備されなくてはならないという点である。本発明の実施形態は、代わりに、ネットワークの上流端で監視が実行できるようにし、したがってネットワークのより効率的な保護を可能にする。
【００６８】
トークンバケット監視器
考えられる機構は、フローの過度要求αｊと、同じ経路状態における準拠するフローの期待される過度要求αＴＣＰ＝１との差異の累積を監視することである。図４は、これがトークンバケットによってどのように実行できるのかを示す。パケットが到着するといつでも、αＴＣＰ・ｄｔｊ，ｉがトークンバケットに追加され（この場合ｄｔｊ，ｉは前回パケットからの、到着間の時間である）、ｋＴＣＰ・Ｔｊ，ｉ・√ｍｊ，ｉがトークンバケットから取り去られる（ここで、Ｔｊ，ｉとｍｊ，ｉはパケット内のフィールドから取得される）。調整後に該バケットが空ではない場合は、パケットは要求に応じて供給される。他方、パケットが空である場合は、フローは処分するようフラグを立てられ、パケットは適切に処理される。
【００６９】
図６は、図４に関連するフローチャートを説明する。パケットが到着すると、該パケットは該パケットのフローｉｄ ｊ、下流輻輳測定基準ｍｊ，ｉ、往復時間Ｔｊ，ｉ、及び該パケットが受信された時刻ｔｎｅｗと関連付けられる。最初に、監視器は、該フローがブラックリストに載っているかどうかをチェックする（最初はブラックリストに記載されているフローはない）。該フローがブラックリストに載っていない場合、監視器はｎＴＣＰ＝ｋＴＣＰ・Ｔｊ，ｉ・√ｍｊ，ｉを決定する。該フローのためのバケットＢｊが存在しなければ、監視器はバケットを作成し、バケット内のトークン数をＢｊ＝Ｂ０に、前回更新の時刻をｔｊ＝ｔｎｅｗに初期化する。
【００７０】
次に、すべての場合において、フローの中のトークン数は、ｔｎｅｗ−ｔｊ−ｎＴＣＰを追加することによって調整され、Ｂｍａｘによって上限を定められる。方程式６（以下を参照すること）に示されるようにＢｍａｘ＝Ｂ０＝Ｂとすることが推奨される。最終ステップは、この操作の最後にバケットが空ではないことをチェックすることである。Ｂｊ＞０の場合、パケットは通常通り処理されるが、Ｂｊ＜０の場合、フローｉｄはブラックリストに載せられ、パケットは処分されるように扱われる。
【００７１】
ｎＴＣＰを決定することは、平方根（あるいは、「経路測定基準を取得する」を扱う項に説明されるように、立方根）を抽出することを必要とし得るものであり、あまり単純な演算操作ではない。したがって、監視器の実現がパケットを転送する際の遅延を最小限に抑えることを必要とされる場合、動作の順序は異なってもよい。最初に、バケットの中のトークン数がチェックされるであろう。Ｂｊ＞０の場合、パケットはただちに転送されるであろう。トークンバケットの状態の更新はオフラインでなされるだろうが、更新が往復時間内に行われるよう十分に迅速に行われるであろう。パケット処理における遅延の最小化は、正常に動作していないフローを検出するためにさらに長くかかり得るものであり、応答性が犠牲にされ得る。
【００７２】
フローｊのパケットｉが到着すると、バケット充填は（＋αＴＣＰ・ｄｔｊ，ｉ−Ｔｊ，ｉ・√ｍｊ，ｉ／ｋ）によって調整される。期間τにわたる調整の累積は（αＴＣＰ−αｊ）・τと同等のｓｕｍｉ＝１．．Ｎｊ（＋αＴＣＰ・ｄｔｊ，ｉ−ｋＴＣＰ・Ｔｊ，ｉ・√ｍｊ，ｉ）である（付録Ａ１を参照すること）。
【００７３】
フルスピードＴＣＰフローの場合、Ｅｘｐ［ｓｕｍｉ＝１．．Ｎｊ（＋αＴＣＰ・ｄｔｊ，ｉ−Ｔｊ，ｉ・√ｍｊ，ｉ／ｋ）］＝（αＴＣＰ−αＴＣＰ）・τ＝０であり、トレンドはその初期位置の回りで振動するトークン数によるものとなる。
【００７４】
Ｅｘｐ［ｓｕｍｉ＝１．．Ｎｊ（＋αＴＣＰ・ｄｔｊ，ｉ−ｋＴＣＰ・Ｔｊ，ｉ・√ｍｊ，ｉ）］＝（αＴＣＰ−αｊ）・τ＞０であるため、不飽和のＴＣＰ−フレンドリフロー（αｊ＜αＴＣＰ）のためのバケットは飽和まで線形に充填する。
【００７５】
Ｅｘｐ［ｓｕｍｉ＝１．．Ｎｊ（＋αＴＣＰ・ｄｔｊ，ｉ−ｋＴＣＰ・Ｔｊ，ｉ・√ｍｊ，ｉ）］＝（αＴＣＰ−αｊ）・τ＜０であるため、正常に動作していないフロー（αｊ＞α＊）のためのバケットは、残っているトークンがなくなるまで線形的に空になる。
【００７６】
バケットの深さは監視器の目的によって定まる。監視器は、見かけの過度要求αｊが期間τ＊の間の上限α＊より高いあらゆるフローにフラグを立てなければならない。過度要求がα＊であるようなフローの場合、バケットが開始時にいっぱいであっても、バケットはτ＊の後に空にされなければならない。すなわち、
Ｂ＋Ｅｘｐ［ｓｕｍｉ＝１．．Ｎ（＋αＴＣＰ・ｄｔｊ，ｉ−ｋＴＣＰ・Ｔｊ，ｉ・√ｍｊ，ｉ）］＝Ｂ＋（αＴＣＰ−α＊）・τ＊＝０ である。
【００７７】
言い換えると、バケットの深さＢは方程式（６）で表される。
【数６】
【００７８】
実際には、これは、正常に動作していないとして識別されるＴＣＰ準拠のパケットは、非常に小さな割合だけであるが、期間τ＊の後に検出される、過度要求がα＊であるフローは５０％であることを意味する。
【００７９】
図５に描かれているような設計における別の変形例は、小さなフローに対するフロー単位の状態要件を制限する。該変形例は、以前にＸＴＣＰとして示された期待スループットに逆比例する各フロー内のトラフィックをサンプリングすることによって過度要求を監視する。
【００８０】
パケットが到達すると必ず、抜き取り検査が実行される。最初に、［０，１］上の均一な分散からｕｉを引き出す。λを一定のサンプリングパラメータとしたとき、ｕｉ＞λ・ｓｊ，ｉ／ＸＴＣＰであれば、パケットは要求されたとおりに供給される。ｕｉ＜λ・ｓｊ，ｉ／ＸＴＣＰであれば、λ・αＴＣＰ・ｄｔｊ，ｉがトークンバケットに追加され、１つのトークンがその中から引き出され、結果として調整はλ・αＴＣＰ・ｄｔｊ，ｉ−１となる。バケットが調整後に空でなければ、パケットは要求されたとおりに供給される。他方、バケットが空の場合、該フローは処分のためのフラグを立てられ、該パケットは適切に処理される。このとき、調整の累積はλ・（αＴＣＰ−αｊ）・τに同等である（付録Ａ２を参照すること）。
【００８１】
サンプリングバージョンの、監視器の優位点は、小さな、準拠するフローはトークンバケットの作成を必要とせず、これにより、非サンプリングの実施形態と比較して、監視器の状態要件（アクティブトークンバケット数）を低減するという点である。この特徴はサービス拒否攻撃から監視器を保護する上で重要である。
【００８２】
図７は、図５に関するフローチャートを説明する。パケットが到着すると、該パケットは該パケットのフローｉｄ ｊ、下流輻輳測定基準ｍｊ，ｉ、往復時間Ｔｊ，ｉ、及び該パケットが受信された時刻ｔｎｅｗと関連付けられる。最初に、監視器は、該フローがブラックリストに載っているかどうかをチェックする（最初はブラックリストに記載されているフローはない）。該フローがブラックリストに載っていない場合、監視器はｎＴＣＰ＝ｋＴＣＰ・Ｔ，ｊ，ｉ・√ｍｊ，ｉを決定する。この段階で、サンプリング監視器は範囲［０．．１］で選ばれる無作為変数ｕｊを選択し、それをλ・ｎＴＣＰと比較する。ｕｊ＞λ・ｎＴＣＰの場合、パケットはさらなる遅延なしに転送されるよう処理される。そうでない場合、もし該フローのためのバケットＢｊが存在しなければ、監視器はバケットを１つ作成し、バケット内のトークン数をＢｊ＝Ｂ０に、前回更新の時刻をｔｊ＝ｔｎｅｗに初期化する。そのとき、すべての場合において、フローの中のトークン数はλ・（ｔｎｅｗ−ｔｊ）−１を追加することによって調整され、λ・Ｂｍａｘによって上限を定められる。方程式６に示されるようにＢｍａｘ＝Ｂ０とすることが推奨される。最終ステップは、この操作の最後にバケットが空ではないことをチェックすることである。Ｂｊ＞０の場合、パケットは通常通りに処理されるが、Ｂｊ＜０の場合、フローｉｄはブラックリストに載せられ、パケットは処分されるように扱われる。
【００８３】
λの選択により、監視器の状態要件の制御を可能にする。より高い値は、監視器が、最短で最も準拠するフローのためのトークンバケットを作成するのに余裕を与える。
【００８４】
処分
ブラックリストに記載されているフローのパケットを処理するために、以下のような幅広い数のオブションが考えられる。
【００８５】
−パケットは削除されてもよい、
−パケットは、存在する場合にはより低い優先順位のクラスに格下げされてもよい、
−パケットは、送信元が反応するための警告としてマークを付されてもよい
トークンバケットＢｊの状態は、この時点においても更新され得る。フローがブラックリストに記載されたばかりのときにある処理が適用され、該バケット内のトークン数が負のままである場合は、さらに厳しい処理が適用され、（該フローが該フローの送信速度を大幅に削減する場合に発生するであろうように）該バケット内のトークン数が再び正になると、該フローはブラックリストから削除されることができる。
【００８６】
経路測定基準の取得
経路測定基準を取得する目的のため、３つの値、すなわちフローｉｄ ｊ、リ−フィードバック輻輳フィールドｈｊ、及びリ−フィードバック下流遅延Ｄｊがパケットヘッダから取り出され得る。
【００８７】
好ましくは、監視器は、ネットワークの入口に近くに位置するべきである。エンドツーエンド測定基準が準拠性テストに必要とされる一方、リ−フィードバックフィールドは実は、下流経路のみを特徴付けることができる。監視器がネットワーク入口近くに位置する場合、２つのオプションがある。すなわち、エンドツーエンド測定基準に対する上流の貢献は取るに足らないものであることが示されるため、差異は無視されるか、あるいは上流の貢献は監視ノードによって監視され、エンドツーエンド測定基準を得るために下流の測定基準とともに使用されるかのどちらかである。これは監視ノードが該ノードの上流経路の恒久的な状態を保つことを要求し得るものであり、上流のノード数が制限されるネットワーク入口でのみ管理可能となり得る。
【００８８】
好ましい実施形態に従って、ｈｊから引き出される下流測定基準から、ｍｊを引き出すことが提案されるが、これは標準的なリ−フィードバック操作である。これは、入口アクセス要素と送信側ホストの間の上流ネットワークには大きな輻輳がないことを仮定している。
【００８９】
方程式（１）のｍは、このようなマークの１つが往復時間内に１つ以上のパケットについて発生する確率ｍｒｔｔである必要があるのに対し、リ−フィードバックフィールドから引き出される値ｍｊは、パケットがマークを付けられる確率ｍｐｋｔを特徴付けることに留意する。将来、ｍｐｋｔがより適切であることが発生する可能性があるが、現時点においてははｍｒｔｔの方がより適切である。これらの２つの値の関係の密接な近似は、ｃｗｎｄ＝ｘＴＣＰ・Ｔ／Ｓｋ／ｍｒｔｔ＾（１／２）としたときのｍｒｔｔ〜ｍｐｋｔ・ｃｗｎｄである。これによりｍｒｔｔ〜（ｋ・ｍｐｋｔ）＾（２／３）となる。
【００９０】
また、好ましい実施形態に従って、輻輳のない期間における最小数の試験を使用して、各上流送信元と監視ノード自身との間の上流往復遅延Ｔ0の記録を監視ノードで保持することが提案されている。往復時間は、対称的なルーティングを仮定するとＴｊ＝Ｔ0＋２・Ｄｊとして得ることができる。応答を得る他の技法を使用使用してもよい。例えばＪｉａｎｇ及びＤｏｖｒｏｌｉｓ［２０］を参照すること。
【００９１】
［２０］Ｈａｏ Ｊｉａｎｇ及びＣｏｎｓｔａｎｔｉｎｏｓ Ｄｏｖｒｏｌｉｓ：「ＴＣＰ往復時間の受動的な推定（Ｐａｓｓｉｖｅ ｅｓｔｉｍａｔｉｏｎ ｏｆ ＴＣＰ ｒｏｕｎｄ−ｔｒｉｐ ｔｉｍｅｓ）」、ＡＣＭ ＳＩＧＣＯＭＭコンピュータ通信レビュー（Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｒｅｖｉｅｗ）第３２巻、第３号（２００２年７月）
上限条件の設定
以下では、（正常に動作していないと見なされ得る、準拠するフローの割合に厳しい上限を課すことによって）十分なレベルのロバスト性を達成するためにα＊がどのようにして選ばれなければならないのかを概略する。
【００９２】
上限の過度要求α＊は、監視器の主要な制御パラメータである。その選択は、監視器の（正常に動作していないフローを迅速に検出する）応答性と（正常に動作していないとして識別される準拠するフローが、できるだけ少ない）ロバスト性の間のトレードオフを設定する際に重要である。ここでは、正常に動作していないとして識別される準拠するフローの割合（つまり誤った肯定判断の割合）がεより小さいままとなるようにするために、どのようにα＊を設定するのかを説明する（εが非常に小さい値、例えば多くても１０−３を取ることが期待される）。
【００９３】
最初に、観察期間が、ｍｊ輻輳が一定であるフローの往復時間Ｔｊである場合にαがどのようにして設定されるべきであるかを示し、その後この結果が監視ノードを通るすべてのフローについての絶対値を与えるためにどのようにして拡張できるかを示す。
【００９４】
一例としてＴＣＰの速度適応機構をマルコフ連鎖としモデル化することの結果として図８は、輻輳レベルｍｊ＝１０−２に対する１つの往復時間ＴｊにわたるＴＣＰ接続の輻輳ウィンドウｃｗｎｄの累積確率分布ｙ＝ｌｏｇ（Ｐ（ｃｗｎｄ＜ε））をログスケールに示す。実質的には、これは基準観察期間が、ＴＣＰフローの往復時間に等しい、すなわちτ＊＝Ｔｊである場合のＴＣＰフローのスループットの期待値である。
【００９５】
監視器に対する要件はτ＊の期間内で誤って肯定判断を行う割合が、εより小さいことであり、したがってα＊は、輻輳ウィンドウが期待平均ｃｗｎｄａｖｇをα＊倍超える確率がεより小さくなるように設定されなければならず、これはＰ（ｃｗｎｄ＞α＊・ｃｗｎｄａｖｇ）＜εによって示される。
【００９６】
図８は、ε＝１０−３のときにα＊を検出する方法を示している。この例では、ｃｗｎｄａｖｇ〜１２．７に対してα＊・ｃｗｎｄａｖｇ〜３５である（平均値はＴＣＰ輻輳ウィンドウをマルコフ連鎖として分析することにより得られる）。これにより、ε＝１０−３に対してα＊〜３となる。これは、期間τ＊の後に、過度要求がα＊より高いフローの少なくとも５０％が、正常に動作していないものと正しく判断されるのに対し、バケット深さが（α＊−αＴＣＰ）・Ｔ＊に設定される場合に、正常に動作していないとして誤って識別されるＴＣＰに準拠するフローは０．１％を超えないことを意味する。観察期間を拡大させると、（監視器の反応性は低下するが）監視器のロバスト性がさらによくなるだろう。
【００９７】
監視器がロバスト性より応答性のために寸法付けられるべき場合、バケットの深さはより低い値に設定されるべきである。
【００９８】
監視器のサンプリングバージョンが（該監視器を流れるトラフィックを監視するために必要なバケット数によって定められる）状態要件を最小限に抑えるように寸法付けられるべき場合、サンプリングパラメータλをより小さくするだけでなく、バケットがより短いと、状態要件が低減する。
【００９９】
各ユーザの輻輳履歴に対する準拠性テストを調整する、さらなる実施形態
最新の期間にユーザによって引き起こされる輻輳の量を追跡調査することによって、上記の問題に取り組むことができる。例えば、期間Ｕｋの契約された使用が分かっている場合に、送信されたデータに起因する輻輳ｍｋの量の記録をユーザごとに保持することができる。さらに、すべてのユーザＵによる総計使用の推定値、及びその結果として生じる輻輳Ｍの推定値も計算されるであろう。サンプリング係数λは、割合（ｍｋ／Ｕｋ）（Ｍ／Ｕ）を考慮に入れて調整されることができる。
【０１００】
例えば、同じサンプリング係数λをすべてのユーザに対して使用するのではなく、ユーザｋのためのサンプリング係数をλｋ＝λ・ｍａｘ｛１，（ｍｋ／Ｕｋ）（Ｍ／Ｕ）｝と定めることができ、これにより、ユーザｋが輻輳「予算」（“ｂｕｄｇｅｔ”）（Ｍ／Ｕ）＊Ｕｋを使い切ったときに、ユーザｋのためのデータｗｏはるかに厳しく監視することができる。
【０１０１】
考えられる変形例
上記の項で、確立された速度制御原理（ＴＣＰ規格）に関して、速度適応がその経路特徴に対応する必要がないフローを検出できる速度監視器の設計を提案した。この機構を、長く用いられており、定常状態にあるＴＣＰフローに対して説明している。定常状態のスループットは準拠するＴＣＰフローが達成できる最大の長期間スループットであるため、実際には監視器は任意のＴＣＰフローに対して効果的となるであろう。しかしながら、監視器は他の準拠基準を使用できる。例えば、長期間のＴＣＰ速度の公式は、Ｋｅｌｌｙの「一定の支払い意志の公式」（上記の方程式（２）を参照すること）に置き換えられるだろう。これは、概略すると各パケットが「支払い意志」フィールドを持っていることを必要とする。
【０１０２】
さまざまなクラスのトラフィックは、さまざまなクラスを使用することによってさまざまな準拠公式に対して試験されることができる。
【０１０３】
付録−トークンバケット機構の分析
付録Ａ１：サンプリングを行わないトークンバケット
提案
バケット内のトークンの量は（αＴＣＰ-αｊ）・τに同等である。
【０１０４】
証明概略：
パケットが到達するたびに、トークンの数はαＴＣＰ・（ｔｊ−ｔｊ−１）だけ増加し、Ｔｉ・√ｍｉ／ｋだけ減少する。時間τの後、バケットは、ｎ（τ）＝Ｎｊ（τ）・τとして、ｓｕｍｉ＝１．．ｎ（τ）（αＴＣＰ・（ｔｉ−ｔｉ−１）−ｔｉ・√ｍｉ／ｋ）を含む。推定値のバイアスは以下の通りである。
【数７】
【０１０５】
ｅｓｔ（Ｔ・√ｍ／ｋ）＝ｓｕｍｉ＝１・・ｎ（Ｔ）（Ｔｉ・√ｍｉ／ｋ）／ｎ（ｔ）によって定義される
したがって、最終的にはｂ＝ｎ（τ）・（１／ｎＴＣＰ−ｅｓｔ（Ｔ・√ｍ／ｋ））となる。
【０１０６】
｜ｂ｜＜εを得るためには、ｎ（τ）・｜１／ｎＴＣＰ−ｅｓｔ（Ｔ・√ｍ／ｋ）｜＜εでなければならない。
【０１０７】
実質的に、等値である“ＸＴＣＰ＝ｋ・ｓ／（Ｔ・√ｍ）ｎ”を用いて書き換えると以下が得られる。
【０１０８】
任意のε１に対し、｜１／ｎＴＣＰ−ｅｓｔ（Ｔ・√ｍ／ｋ）｜＜ε１となるようなτ１が存在する。
【０１０９】
さらに、より長いフローに対して、等値がより強力であることを強調するε１＝Ｏ（１／ｎ（τ））であると仮定すると、以下が得られる。
【０１１０】
任意のε２に対し、｜１／ｎＴＣＰ−ｅｓｔ（Ｔ・√ｍ／ｋ）｜＜ε２／ｎ（τ２）となるようにτ２が存在する。
【０１１１】
ε＝ε２／ｎ（τ２）となるようにτ２を選ぶと、｜ｂ｜＜ε、したがって提案されている等値を得る。
【０１１２】
注記：これは監視器での平均化を必要としない。指数的に重み付けされた移動平均（ＥＷＭＡ）が使用される場合、代わりにｅｓｔ（Ｔ・√ｍ／ｋ）＝ｓｕｍｉ＝１．．ｎ（τ）（ＥＷＭＡ（Ｔｉ・√ｍｊ／ｋ））／ｎ（τ）を定義でき、残りの証明はすべて、ただこれに関連するものである。これは、平均に関しては監視器の性能を改善しないかもしれない。これは、分散に関して、性能に影響する可能性が最も高い。
【０１１３】
付録Ａ２：サンプリングを行うトークンバケット
提案
バケット内のトークンの量は（αＴＣＰ−αｊ）・λ・τに同等である。
【０１１４】
証明概略
非常に類似している。サンプリングされたパケットの数としてＬ（τ）Ｌ（τ）＝ｎ（τ）・λとして定める。
【数８】
【０１１５】
ｅｓｔ（Ｔ・√ｍ／ｋ）＝ｓｕｍｉ＝１・・ｎ（Ｔ）（Ｔｉ・√ｍｉ／ｋ）ｎ（τ）によって定義される
ここでは、ｂ＝λ・ｎ（τ）・（１／ｎＴＣＰ−ｅｓｔ（Ｔ・√ｍ／ｋ））＋ｓｕｍｉ＝１．．ｎ（τ）（λ・Ｔｉ・√ｍｊ／ｋ−ｕｉ）を得る。
【０１１６】
Ａ１に示された理由のために、ε／２＝ε２／ｎ（τ３）となるようにτ３を選ぶことができる。
【０１１７】
さらにτ＞τ４のときに｜ｓｕｍｉ＝１．．ｎ（τ）（λ・Ｔｉ・√ｍｊ／ｋ−ｕｉ）｜＜ε／２であれば、τ＞ｍａｘ（τ３，τ４）のときにｂ＜εが成り立つ。
【図面の簡単な説明】
【０１１８】
【図１】ボトルネック監視器（図１（ａ））と、本発明に従って動作する経路独特の監視器（図１（ｂ））との間の根本的な相違点を概略する。
【図２】旧式の監視器（図２（ａ））と本発明の好ましい実施形態に従って動作する経路独特の監視器（図２（ｂ））との間の監視動作の潜在的な相違点を示すグラフを示す。
【図３】本発明の比較的一般的な実施形態による監視器を示す図である。
【図４】固定深さのトークンバケットのモデルを使用して、本発明の実施形態に従って動作する監視器を示す図である。
【図５】本発明の好ましい実施形態に従って動作する監視器を示す図であり、過度要求は、該監視器の期待スループットに逆比例するトラフィックのサンプリングによって監視される。
【図６】本発明の実施形態に従って動作する監視器により行われるステップを示すフローチャートであり、過度要求はトラフィックをサンプリングしないで監視される。
【図７】本発明の実施形態に従って動作する監視器により行われるステップを示すフローチャートであり、過度要求はトラフィックをサンプリングすることによって監視される。
【図８】本発明の好ましい実施形態に従って動作する監視器を通るＴＣＰフローの期待スループットを示すグラフである。
【特許請求の範囲】
【請求項１】
データネットワーク内でフローを監視する方法であって、前記データネットワークは、基準速度適応ポリシーが関連付けられたネットワークサービスを提供し、前記方法は、
ノードを通るフローの過度要求の基準を決定するステップと、
前記過度要求の基準と、許容できる過度要求を示す基準を比較するステップと、
前記過度要求が前記許容できる過度要求に従うものでない場合に考えられる処分のために前記フローを指定するステップと、を備え、
許容できる過度要求を示す前記基準は、前記ネットワークサービスと関連付けられた基準速度適応ポリシーに準拠し、実質的に同様の経路状態を経験するフローの前記期待される過度要求に依存して、決定されることを特徴とする方法。
【請求項２】
前記フローは複数のメッセージを備える、請求項１に記載の方法。
【請求項３】
前記メッセージはデータパケットである、請求項２に記載の方法。
【請求項４】
前記メッセージは、データネットワークを横断する際に前記メッセージによって使用される経路の１つ以上の特徴を示す情報を搬送する、請求項２又は請求項３に記載の方法。
【請求項５】
前記メッセージは、前記データネットワーク内のエンドツーエンド経路の特徴を示す情報を搬送する、請求項４に記載の方法。
【請求項６】
前記メッセージは、前記データネットワーク内の下流経路の特徴を示す情報を搬送する、請求項４又は請求項５に記載の方法。
【請求項７】
前記メッセージは輻輳を示す情報を搬送する、請求項４乃至請求項６のいずれか１項に記載の方法。
【請求項８】
前記メッセージは、前記データネットワーク内の前記経路を横切るメッセージの往復時間（ＲＴＴ）を示す情報を搬送する、請求項４乃至請求項７のいずれか１項に記載の方法。
【請求項９】
前記フローから１つ以上のメッセージを選択するステップをさらに備え、前記比較するステップは前記選択されたメッセージに関して実行される、請求項２乃至請求項８のいずれか１項に記載の方法。
【請求項１０】
特定のメッセージが前記フローから選択される確率が前記フローの前記過度要求に依存している、請求項９に記載の方法。
【請求項１１】
前記過度要求の基準は、前記フローの速度適応ポリシーに依存して決定される、先行する請求項１乃至請求項１０のいずれか１項に記載の方法。
【請求項１２】
前記期待される過度要求は、ＴＣＰに準拠するフローの過度要求の基準に関連して決定される、請求項１乃至請求項１１のいずれか１項に記載の方法。
【請求項１３】
許容できる過度要求を示す前記基準は、前記方法を実行するときの、ノードのロバスト性の所望されるレベルに関連して決定される、請求項１乃至請求項１２のいずれか１項に記載の方法。
【請求項１４】
許容できる過度要求を示す前記基準は、前記方法を実行するときの、ノードの応答性の所望されるレベルに関連して決定される、請求項１乃至請求項１３のいずれか１項に記載の方法。
【請求項１５】
許容できる過度要求を示す前記基準は、前記方法を実行するときの、ノードの状態要件に関連して決定される、請求項１乃至請求項１４のいずれか１項に記載の方法。
【請求項１６】
考えられる処分のための前記フローを指定する前記ステップは、前記フローの前記過度要求が許容できる過度要求の閾値レベルに合格する場合に行われる、請求項１乃至請求項１５のいずれか１項に記載の方法。
【請求項１７】
考えられる処分が行われるフローを指定する前記ステップの尤度が、前記過度要求と前記許容できる過度要求の間の差異の基準に依存する、請求項１乃至請求項１６のいずれか１項に記載の方法。
【請求項１８】
フローが指定される任意の考えられる処分の厳しさが、前記過度要求と前記許容できる過度要求の間の差異の基準に依存する、請求項１乃至請求項１７のいずれか１項に記載の方法。
【請求項１９】
考えられる処分に対して指定されたフローに関して処置を行うステップをさらに備える、請求項１乃至請求項１８のいずれか１項に記載の方法。
【請求項２０】
前記処置は、考えられる処分に対して指定された１つ以上のフローから１つ以上のメッセージを廃棄することを備える、請求項１９に記載の方法。
【請求項２１】
前記処置は、考えられる処分に対して指定された１つ以上のフローから１つ以上のメッセージを、より低い優先順位を有するトラフィッククラスに降格させることを備える、請求項１９又は請求項２０に記載の方法。
【請求項２２】
前記処置は、考えられる処分に対して指定された１つ以上のフローから１つ以上のメッセージにマークを付けることを備える、請求項１９乃至請求項２１のいずれか１項に記載の方法。
【請求項２３】
マークを付ける前記処置は、前記フローの送信元に対して、前記送信元が前記マーク付けに適切に反応できない場合にさらなる処分が加えられる可能性があることを示す通知で、メッセージにマークを付けることを備える、請求項２２に記載の方法。
【請求項２４】
前記処置は、考えられる処分に対して指定された１つ以上のフローから１つ以上の以後のメッセージを遅延させることを備える、請求項１９乃至請求項２３のいずれか１項に記載の方法。
【請求項２５】
前記処置は、考えられる処分に対して指定された１つ以上のフローに速度制御を行うことを備える、請求項１９乃至請求項２４のいずれか１項に記載の方法。
【請求項２６】
フローについて許容できる過度要求を示す前記基準は、前記フローについて過去の挙動の基準に依存して変えられてよい、請求項１乃至請求項２５のいずれか１項に記載の方法。
【請求項２７】
フローについて任意の考えられる処分の厳しさ及び／又は尤度が、前記フローについて過去の挙動の基準に依存して変えられてよい、請求項１乃至請求項２６のいずれか１項に記載の方法。
【請求項２８】
フローについて許容できる過度要求及び／又は前記期待される過度要求を示す前記基準は、前記フローのトラフィックのクラスに依存して変えられてよい、請求項１乃至請求項２７のいずれか１項に記載の方法。
【請求項２９】
データネットワーク内でフローを監視する装置であって、請求項１乃至請求項２８のいずれか１項に記載の方法を実現するための前記ステップを実施するための手段を備える装置。
【請求項１】
データネットワーク内でフローを監視する方法であって、前記データネットワークは、基準速度適応ポリシーが関連付けられたネットワークサービスを提供し、前記方法は、
ノードを通るフローの過度要求の基準を決定するステップと、
前記過度要求の基準と、許容できる過度要求を示す基準を比較するステップと、
前記過度要求が前記許容できる過度要求に従うものでない場合に考えられる処分のために前記フローを指定するステップと、を備え、
許容できる過度要求を示す前記基準は、前記ネットワークサービスと関連付けられた基準速度適応ポリシーに準拠し、実質的に同様の経路状態を経験するフローの前記期待される過度要求に依存して、決定されることを特徴とする方法。
【請求項２】
前記フローは複数のメッセージを備える、請求項１に記載の方法。
【請求項３】
前記メッセージはデータパケットである、請求項２に記載の方法。
【請求項４】
前記メッセージは、データネットワークを横断する際に前記メッセージによって使用される経路の１つ以上の特徴を示す情報を搬送する、請求項２又は請求項３に記載の方法。
【請求項５】
前記メッセージは、前記データネットワーク内のエンドツーエンド経路の特徴を示す情報を搬送する、請求項４に記載の方法。
【請求項６】
前記メッセージは、前記データネットワーク内の下流経路の特徴を示す情報を搬送する、請求項４又は請求項５に記載の方法。
【請求項７】
前記メッセージは輻輳を示す情報を搬送する、請求項４乃至請求項６のいずれか１項に記載の方法。
【請求項８】
前記メッセージは、前記データネットワーク内の前記経路を横切るメッセージの往復時間（ＲＴＴ）を示す情報を搬送する、請求項４乃至請求項７のいずれか１項に記載の方法。
【請求項９】
前記フローから１つ以上のメッセージを選択するステップをさらに備え、前記比較するステップは前記選択されたメッセージに関して実行される、請求項２乃至請求項８のいずれか１項に記載の方法。
【請求項１０】
特定のメッセージが前記フローから選択される確率が前記フローの前記過度要求に依存している、請求項９に記載の方法。
【請求項１１】
前記過度要求の基準は、前記フローの速度適応ポリシーに依存して決定される、先行する請求項１乃至請求項１０のいずれか１項に記載の方法。
【請求項１２】
前記期待される過度要求は、ＴＣＰに準拠するフローの過度要求の基準に関連して決定される、請求項１乃至請求項１１のいずれか１項に記載の方法。
【請求項１３】
許容できる過度要求を示す前記基準は、前記方法を実行するときの、ノードのロバスト性の所望されるレベルに関連して決定される、請求項１乃至請求項１２のいずれか１項に記載の方法。
【請求項１４】
許容できる過度要求を示す前記基準は、前記方法を実行するときの、ノードの応答性の所望されるレベルに関連して決定される、請求項１乃至請求項１３のいずれか１項に記載の方法。
【請求項１５】
許容できる過度要求を示す前記基準は、前記方法を実行するときの、ノードの状態要件に関連して決定される、請求項１乃至請求項１４のいずれか１項に記載の方法。
【請求項１６】
考えられる処分のための前記フローを指定する前記ステップは、前記フローの前記過度要求が許容できる過度要求の閾値レベルに合格する場合に行われる、請求項１乃至請求項１５のいずれか１項に記載の方法。
【請求項１７】
考えられる処分が行われるフローを指定する前記ステップの尤度が、前記過度要求と前記許容できる過度要求の間の差異の基準に依存する、請求項１乃至請求項１６のいずれか１項に記載の方法。
【請求項１８】
フローが指定される任意の考えられる処分の厳しさが、前記過度要求と前記許容できる過度要求の間の差異の基準に依存する、請求項１乃至請求項１７のいずれか１項に記載の方法。
【請求項１９】
考えられる処分に対して指定されたフローに関して処置を行うステップをさらに備える、請求項１乃至請求項１８のいずれか１項に記載の方法。
【請求項２０】
前記処置は、考えられる処分に対して指定された１つ以上のフローから１つ以上のメッセージを廃棄することを備える、請求項１９に記載の方法。
【請求項２１】
前記処置は、考えられる処分に対して指定された１つ以上のフローから１つ以上のメッセージを、より低い優先順位を有するトラフィッククラスに降格させることを備える、請求項１９又は請求項２０に記載の方法。
【請求項２２】
前記処置は、考えられる処分に対して指定された１つ以上のフローから１つ以上のメッセージにマークを付けることを備える、請求項１９乃至請求項２１のいずれか１項に記載の方法。
【請求項２３】
マークを付ける前記処置は、前記フローの送信元に対して、前記送信元が前記マーク付けに適切に反応できない場合にさらなる処分が加えられる可能性があることを示す通知で、メッセージにマークを付けることを備える、請求項２２に記載の方法。
【請求項２４】
前記処置は、考えられる処分に対して指定された１つ以上のフローから１つ以上の以後のメッセージを遅延させることを備える、請求項１９乃至請求項２３のいずれか１項に記載の方法。
【請求項２５】
前記処置は、考えられる処分に対して指定された１つ以上のフローに速度制御を行うことを備える、請求項１９乃至請求項２４のいずれか１項に記載の方法。
【請求項２６】
フローについて許容できる過度要求を示す前記基準は、前記フローについて過去の挙動の基準に依存して変えられてよい、請求項１乃至請求項２５のいずれか１項に記載の方法。
【請求項２７】
フローについて任意の考えられる処分の厳しさ及び／又は尤度が、前記フローについて過去の挙動の基準に依存して変えられてよい、請求項１乃至請求項２６のいずれか１項に記載の方法。
【請求項２８】
フローについて許容できる過度要求及び／又は前記期待される過度要求を示す前記基準は、前記フローのトラフィックのクラスに依存して変えられてよい、請求項１乃至請求項２７のいずれか１項に記載の方法。
【請求項２９】
データネットワーク内でフローを監視する装置であって、請求項１乃至請求項２８のいずれか１項に記載の方法を実現するための前記ステップを実施するための手段を備える装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公表番号】特表２００８−５３０８４１（Ｐ２００８−５３０８４１Ａ）
【公表日】平成２０年８月７日（２００８．８．７）
【国際特許分類】
【出願番号】特願２００７−５５３７０６（Ｐ２００７−５５３７０６）
【出願日】平成１８年２月７日（２００６．２．７）
【国際出願番号】ＰＣＴ／ＧＢ２００６／０００４１７
【国際公開番号】ＷＯ２００６／０８２４４３
【国際公開日】平成１８年８月１０日（２００６．８．１０）
【出願人】（３９００２８５８７）ブリティッシュ・テレコミュニケーションズ・パブリック・リミテッド・カンパニー (104)
【氏名又は名称原語表記】ＢＲＩＴＩＳＨ ＴＥＬＥＣＯＭＭＵＮＩＣＡＴＩＯＮＳ ＰＵＢＬＩＣ ＬＩＭＩＴＥＤ ＣＯＭＰＡＮＹ
【Ｆターム（参考）】
【公表日】平成２０年８月７日（２００８．８．７）
【国際特許分類】
【出願日】平成１８年２月７日（２００６．２．７）
【国際出願番号】ＰＣＴ／ＧＢ２００６／０００４１７
【国際公開番号】ＷＯ２００６／０８２４４３
【国際公開日】平成１８年８月１０日（２００６．８．１０）
【出願人】（３９００２８５８７）ブリティッシュ・テレコミュニケーションズ・パブリック・リミテッド・カンパニー (104)
【氏名又は名称原語表記】ＢＲＩＴＩＳＨ ＴＥＬＥＣＯＭＭＵＮＩＣＡＴＩＯＮＳ ＰＵＢＬＩＣ ＬＩＭＩＴＥＤ ＣＯＭＰＡＮＹ
【Ｆターム（参考）】
[ Back to top ]