JP5606629B2 - 効率的な輻輳公示監査機能のフレームワーク - Google Patents

Description

本発明は、輻輳公示対応ネットワークにおけるパケットドロッパの動作方法に関する。
送信側ホストと受信側ホストが、中間ルータを経由するネットワーク経路上でパケットのフローを送信することによって相互に通信し、輻輳を検出すると、前記フローのパケットを輻輳パケットとしてマークし、
輻輳が輻輳フィードバックメカニズムによって送信側ホストに通知され、
送信側ホストは、輻輳通知を受信すると、送信するパケットのサブセットを輻輳応答パケットとして宣言することにより、輻輳応答パケットの量が通知された輻輳レベルと均衡するか否かに応じて適合フローまたは不適合フローのいずれかを生成する。

また、本発明は、輻輳公示対応ネットワークにおいて用いられるパケットドロッパに関する。
送信側ホストと受信側ホストが、中間ルータを経由するネットワーク経路上でパケットのフローを送信することによって相互に通信し、輻輳を検出すると、前記フローのパケットを輻輳パケットとしてマークし、
送信側ホストに輻輳を通知するように構成された輻輳フィードバックメカニズムが設けられ、
送信側ホストは、輻輳通知を受信すると、送信するパケットのサブセットを輻輳応答パケットとして宣言することにより、輻輳応答パケットの量が通知された輻輳レベルと均衡するか否かに応じて適合フローまたは不適合フローのいずれかを生成する。

輻輳公示（congestion exposure）に基づく輻輳ベースのネットワークトラフィックのポリシングは、ネットワーク輻輳時にユーザトラフィックに課金するためのネットワークリソース制御パラダイムとして期待されている。例えば非特許文献１で論じられているように、従来用いられてきたフローレート公平性は、ネットワークリソースのリソース配分および課金のための妥当なメカニズムではない。その代わりに、コストベースのメカニズムが、より良好なリソース配分パラダイムを提供することが示唆されている。ここで「コスト」とは、利用可能なネットワークリソースが与えられた場合に、各ユーザの転送が他の転送を制限する程度を意味する。このコストを測定する尺度として、各ユーザによって引き起こされたネットワーク輻輳の量が提案されている。輻輳に基づくネットワークトラフィックのポリシングメカニズムは、ネットワーク事業者が自己のネットワーク上のトラフィックを管理するためのネット中立的な手段を提供する。

輻輳に基づくネットワークトラフィックのポリシングを実現するためのいくつかの提案がなされている。例えば、Ｒｅ−ＥＣＮ（Relay or Re-feedback of Explicit Congestion Notification）は、Internet Engineering Task Force（ＩＥＴＦ）Congestion Exposure（ＣＯＮＥＸ）ワーキンググループでなされている提案であり、例えば非特許文献２に記載されている。以下でさらに詳細に説明するように、Ｒｅ−ＥＣＮ、すなわち明示的輻輳通知の再フィードバックは、パケットが引き起こすことが予想される輻輳を公示するためのフィードバックメカニズムを提供する。主要な特徴は、リソース使用量に基づくのではなく、ユーザトラフィックがネットワーク内の他のユーザトラフィックに対して引き起こしつつある輻輳に基づく、ユーザベースの課金可能性である。

例えば、図１にＲｅ−ＥＣＮシステムを示す。これは、輻輳公示システムの具体的実現である。このＲｅ−ＥＣＮシステムには、以下のような複数の機能エンティティがある。ルータは、輻輳を検出し、自己のキュー内のパケットに明示的輻輳通知（Explicit Congestion Notification, ＥＣＮ）を適用する。受信側エンドポイントは、この輻輳情報を収集し、センダへ返送する。センダは、トランスポートプロトコル（例えばＴＣＰ）を実行し、この情報をトランスポートプロトコルの輻輳制御アルゴリズムのために使用することができる。また、センダは、受信したフィードバックに応答して、後続のパケット送信のために輻輳への自己の寄与を宣言することが期待される。これは、一部のパケットを適宜マークすることによって行われる。事業者が提供するポリサ（policer）は、この情報を用いて、それに従ってトラフィックのポリシングあるいは課金を行うことができる。

適合輻輳応答を測定するため、輻輳公示システムは通常、ネットワーク出口に配置された監査機能に依拠する。例えば、Ｒｅ−ＥＣＮでは、監査機能は、パケットドロッパエンティティの形態で実現される。このため、パケットドロッパおよび監査機能を以下では同義語として用いる。実際の観測された経路輻輳に基づくとともに、センダによって宣言された輻輳寄与に基づいて、このような監査機能／パケットドロッパは、特定の不適合フローに関連するパケットを廃棄することにより、全体的な輻輳ベースのポリシングを施行することができる。

輻輳状況下では、与えられた応答に対して、ネットワークによって提供される可能なビットレートに上限がある。当然、ユーザは、ネットワークにおける自己の輻輳寄与を過少申告することにより、自己のビットレート（効用）を増大させたいと考える。このような不適合挙動はチーティング（cheating, 詐欺）と呼ばれる。というのは、与えられたネットワーク輻輳の下で、このユーザは、正直に（すなわち適合的な形で）輻輳を宣言しているユーザよりも高いビットレート（すなわちネットワークリソース）を提示するからである。このため、輻輳公示システムは、期待されるネットワークリソース制御アプローチであるが、エンドホストとネットワーク事業者との共同参画を必要とするという問題が残る。

まとめると、経路輻輳およびその応答は、ネットワーク出口で最も良く推定することができる。課題として残るのは、チーティングユーザが全トラフィック集合に隠れていることである。応答を変化させることにより、ユーザは、ネットワークが識別しペナルティを科すべきチーティングパターンの豊富なセットを工夫することができる。輻輳宣言は送信側ホストの完全な制御下にあるので、事業者は、競合するホスト間の公平なリソース課金可能性のために、ネットワーク輻輳に対するユーザ応答を監視しなければならない。

米国特許出願公開第２００９／０２７９４３３Ａ１号明細書

B. Briscoe, "Flow Rate Fairness: Dismantling a Religion", ACM Computer Communications Review, 37(2), 63-74 (Apr. 2007) B. Briscoe, A. Jacquet, C. Di Cairano-Gilfedder, A. Salvatori, A. Soppera, and M. Koyabe, "Policing Congestion Response in an Internetwork using Re-feedback", Proc. ACM SIGCOMM'05, CCR, 35(4):277-288, Aug. 2005 Sally Floyd and Van Jacobson: "Random early detection gateways for congestion avoidance", IEEE Transactions on Networking, Vol. 1, No. 4, August 1993

上記に鑑み、本発明の目的は、頭書のようなパケットドロッパの動作方法およびパケットドロッパにおいて、実施の容易なメカニズムを使用することにより、チーティングユーザの正確で確実な検出が可能となるような改良およびさらなる展開を行うことである。

本発明によれば、上記の目的は、請求項１の構成を備えた方法によって達成される。この請求項に記載の通り、本方法は、前記パケットドロッパが、前記不適合フローを識別する一連のトラフィック分析ステップを順次実行することを特徴とする。

また、上記の目的は、独立請求項１１の構成を備えたパケットドロッパによって達成される。この請求項に記載の通り、本パケットドロッパは、前記不適合フローを識別するために順次使用される複数のトラフィック分析モジュールを備えたことを特徴とする。

本発明によって認識されたこととして、送信側ホストによって使用されるさまざまなチーティングパターンの正確で確実な検出、分離、そして場合によりそれにペナルティを科すことは、全集合に隠れている不適合フローを識別するための段階的アプローチによって実現することができる。提案するフレームワークは、フローのサブセットをチーティングとして分類する前に一連のステップで不適合性をチェックする。すなわち、与えられたフロー識別子のセットを識別子の２つのサブセットに分割することにより、何らかの制御条件に基づいて適合トラフィックと不適合トラフィックとを分離しようとする従来技術の解決法（例えば特許文献１に記載）とは異なり、本発明による方法およびパケットドロッパは、適合フローと不適合フローとを明示的に分離しない。その代わりに、前記不適合フローを識別するための複数のトラフィック分析モジュールが順次使用される。ここで、すべてのフロー識別子からなるスーパーセットから出発して、適合フローを廃棄しながら、不適合フローのみがステップからステップへと分析モジュールに保持される。

結果として、本発明は、チーティングトラフィックを効率的に分離しペナルティを科すための一般的な輻輳公示監査機能フレームワークを提供する。本発明を適用することにより、ネットワーク輻輳の状況における、より良好なリソース課金可能性を達成することができる。また、輻輳への自己の寄与を宣言する際に適合的なユーザに対して公平なリソース利用を施行することができる。動作の問題に関して、本発明は、段階的なアプローチにより、オンデマンド検出動作を実現することが可能であるという利点を有する。すなわち、検出アルゴリズムは、経路がチーティングユーザによって支配的に占有されているという十分な証拠がある状況でのみ実行される。

一実施形態によれば、一連のトラフィック分析ステップのうちの最初のステップは、ネットワーク出口で全トラフィック集合を監視し、全トラフィック集合に対して輻輳マークパケットおよび輻輳応答パケットを集計することを含む。この目的のため、輻輳パケットおよび応答パケットに関する情報のみを集計することによって全トラフィック集合に対する不適合性の概念を確定する集合監視モジュールが実装されてもよい。

有利な態様として、一連のステップのうちの後続ステップは、輻輳マークパケットと輻輳応答パケットとの移動差分が所定しきい値を超える場合に起動されるようにしてもよい。これにより、全トラフィック集合について輻輳パケットおよび応答パケットを集計することにより経路出口における全体的な傾向を追跡するという、一種の混成監査機能の実施態様が実現される。これらの２つの平均値、すなわち、一方で輻輳マークパケット、および他方で輻輳応答パケットの平均値に基づいて、集合監視モジュールは、対応するリンクが出口において受けている正味の欠損を追跡する。集合監視モジュールによって保持される所定の「カットオフ」しきい値は、リンクに対する移動デルタが、理想的なゼロ平均値から許容可能な偏差内にあることを意味する。デルタ値が「カットオフ」しきい値を超えると、集合監視モジュールは、出口における状態管理を起動することになる。

軽量でステートレスなパケットドロッパの実施態様を実現することに関して、後続ステップのうちの第１ステップで、移動差分に基づいてパケットの廃棄確率が計算されるようにしてもよい。別法として、より高度でステートフルな実施態様においては、後続ステップのうちの第１ステップで、全トラフィック集合から、輻輳パケットとして最近マークされたパケットを含むフローのサブセットが識別されるようにしてもよい。この目的のため、パケットドロッパは、最新状況分析モジュールを含んでもよい。輻輳は時間変化するので、このモジュールは、この情報をネットワーク経路輻輳に関連づけることによって、ユーザ応答の変化を追跡するように構成されてもよい。

別の好ましい実施形態によれば、後続ステップのうちの第２ステップは、第１ステップで求めたフローのサブセットの各要素に対して、より短い期間、輻輳マークパケットと輻輳応答パケットとの差分を観測することを含む。この目的のため、パケットドロッパは、全トラフィック集合のうちのトラフィックのサブセットが実際にチーティングであるかどうかを検出するように構成されたチータ検出モジュールを含んでもよい。不適合性は、いかなる想定可能なチーティングパターンに起因することもあり得るので、このモジュールは、前に実行されたステップで識別されたサブセットの各要素に対して、より短い期間だけ、変位した平均があるかどうかを監視する。このモジュールの尺度は、輻輳マークデータ量と輻輳応答データ量との差分（以下、簡略化して「デルタ」という）である。この差分の値は、一定数Ｎ個のサンプルに対して観測してもよく、あるいは、その期間に到着するサンプル数とは独立の時間単位に基づいて観測してもよい。不適合フロー識別子がこのモジュールに保持される一方、適合フロー識別子はこのステップで廃棄される。

さらに別の好ましい実施形態によれば、後続ステップのうちの第３ステップは、第２ステップの分析で輻輳マークパケットと輻輳応答パケットとの差分が所定しきい値を超えたフローに対して廃棄動作を適用することを含む。この目的のため、チータ検出モジュールによって不適合と識別されたフロー識別子のサブセットが、廃棄動作を適用する詳細フロー分析モジュールに渡されてもよい。このモジュールの尺度は、不適合トラフィックに対して、ある時間単位にわたる欠損を累積することであり、廃棄は、偏差の増大とともに増大することになる。このコンポーネントは、廃棄が持続的である場合にのみ、当該サブセットトラフィックを観測し続けるように、自己制御的とすべきである。後のある時点で、トラフィックが適合的であることがわかった場合には、そのインスタンスは自動的に低減されるべきである。

また、チーティングとして検出されたトラフィックのサブセットに対して、パケット廃棄を正確に施行するための特定の監査機能インスタンスが作成される。廃棄挙動コンポーネントを通じて、さまざまな廃棄ポリシーおよび実施態様を規定することができる。このコンポーネントは、さまざまなペナルティ挙動を有するように独立のままに保持してもよい。廃棄確率は、上記のように、現在累積されている欠損に基づいてモデル化されてもよい。前に実行されたステップで識別されたフローのサブセットのみが、何らかの判断基準に基づいて廃棄動作を受けてもよい。

本発明を好ましい態様で実施するにはいくつもの可能性がある。このためには、一方で請求項１および１１に従属する諸請求項を参照しつつ、他方で図面により例示された本発明の好ましい実施形態についての以下の説明を参照されたい。図面を用いて本発明の好ましい実施形態を説明する際には、本発明の教示による好ましい実施形態一般およびその変形例について説明する。

既知のＲｅ−ＥＣＮフレームワークの概観を示す図である。 支配的ユーザストラテジによるマークされた輻輳とその応答との差分の平均の分布を示す図である。 過少申告輻輳（左）と過大申告輻輳（右）に対する変位した平均の分布を示す図である。 ３ユーザに対する相異なるチーティングパターンを示す図である。 本発明の実施形態によるパケットドロッパフレームワークを示す図である。 本発明の実施形態による集合監視モジュールの実施態様を示す図である。 本発明の実施形態によるパケットドロッパの並列トラフィック分析モジュールによる状態管理を例示する図である。 本発明の実施形態によるパケットドロッパ実施態様に対する制御ループを例示する図である。 無線基地局ＤＬ（ＭＡＣ）マーカを有するパケットドロッパの実施態様を示す図である。

ネットワークトラフィックの輻輳に基づくポリシングは、「コスト公平性」に基づく形でネットワークリソースの配分および課金のための有効なメカニズムを提供する。ネットワークトラフィックの輻輳に基づくポリシングのための方法やシステムを提供するために従来いくつかの試みがなされているが、これらの従来の試みは、広く使用されることを妨げるようないくつかの問題点を有する。

図１は、Ｒｅ−ＥＣＮ（re-feedback of explicit congestion notification）フレームワークおよびその機能エンティティの概観を示している。Ｒｅ−ＥＣＮは、例えば非特許文献２に記載されている。

図１に示すように、センダ１０２（例えばＴＣＰセンダ）とレシーバ１０４（例えばＴＣＰレシーバ）が、ルータ１０６、１０８、および１１０ならびにポリサ１１２および監査機能１１４を含む経路上で通信する。センダ１０２およびレシーバ１０４にとって、経路は、遅延や、過渡的または永続的な輻輳に起因するパケット損失あるいは「Congestion Experienced」（ＣＥ）マーキングレートに関してさまざまな特性を示し得る。ルータ１０６、１０８、および１１０のようなルータは、アクティブキュー管理（active queue management, ＡＱＭ）メカニズムを実施し、永続的輻輳を検出したときに、斜線を施した長方形で示したパケット１２２のようなＩＰパケット内の明示的輻輳通知（ＥＣＮ）ビットを確率的に（ランダム早期検出（random early detection, ＲＥＤ）を用いて）セットする。レシーバ１０４は、パケット１２２のような輻輳マークパケットを受信すると、自己のトランスポートプロトコルのフィードバックメカニズムを通じて（例えばＴＣＰヘッダフィールドを用いて）、現在の輻輳レベルについてセンダに通知する。するとセンダ１０２は、受信した輻輳通知に応答して、その特定のトランスポートプロトコルの輻輳制御メカニズムに従って送信レートを適応させ、このコネクション上で送信されるＩＰトラフィックの一部をネットワークへの自己の輻輳寄与として宣言する。宣言は、塗りつぶした長方形で示した輻輳応答パケット１２０のような送信パケット内にｒｅ−ｅｃｈｏ情報を挿入することによって行われる。これは、「負の」バイト数、すなわち、輻輳フィードバックによって報告される輻輳寄与と、「正の」バイト数、すなわち、センダによって宣言された輻輳寄与応答とを均衡させることを目標とする。

このように、Ｒｅ−ＥＣＮの基本原理は、受けた輻輳に関する情報をネットワークに再挿入することである。これにより、入口ポリサ１１２は、ネットワークポリシーに従って、許容される輻輳に関してユーザにどのような権限があるかを判定することができる。これに対して、監査機能１１４は、パケットドロッパとして実現され、宣言されていることが正しいか否かを検証し、場合により、負の下流輻輳を永続的に宣言している（すなわち、輻輳寄与を過少宣言している）フロー中のパケットを廃棄する。

事業者は、例えば、与えられた期間にユーザが引き起こすことが許容される輻輳をレート制限するため、あるいは、何らかの課金方式を適用するために、ポリサ１１２をネットワーク入口に配置することを選択してもよい。事前設定された割当て分を消費したら、何らかのペナルティ、例えば、サービスレートを減少させることが可能である。なお、入口ポリサ１１２は、宣言された輻輳をレート制限するだけである。したがって、輻輳を過少申告することにより、ビットレートを高め、対応して効用を増大させることが依然として可能である。正直なユーザにとっては、応答および輻輳の一部が出口で相殺する。しかし、輻輳を過少申告しているユーザにはこれは当てはまらず、そのユーザのトラフィックは結局、出口で正味の欠損を生じる。このため、パケットドロッパあるいは監査機能は、チーティングフローにペナルティを科すため、経路内の最終エンティティであることが提案される。

次に、図２および図３を参照して、上記のチーティングメカニズムについてさらに詳細に説明する。なおこれに関して一般的に、経路状態（すなわち輻輳）は、提示される負荷に比例して変化する。そして、これは高度ＡＱＭ（Active Queue Management）メカニズム（例えば非特許文献３に記載）を実装した中間ルータにおける輻輳マーキングレートの変動を引き起こす。応答を調整するためには、フィードバックループを通じて送信側ホストでその変化が見えるようになるまで少なくとも１ＲＴＴ（ラウンドトリップ時間）かかる。順方向経路は、最終フィードバックサイクルからの変化を含み、経路状態は依然として新たな変動の可能性があるので、輻輳マークパケット数と、ネットワークを出る対応する輻輳応答パケット数との移動差分をとるのが適切である。

輻輳パケットおよびその応答パケットの移動平均（あるいは、より正確には、輻輳マークパケット数と輻輳応答パケット数との差分の移動平均）が経路出口で追跡される場合、ほとんどのサンプルはゼロ平均値に近い差分（デルタ）を有するはずである。その場合、図２に示すような正規分布が、ゼロ平均値からの平均偏差を近似するために使用可能である。Ｒｅ−ＥＣＮ準拠センダの場合、ゼロ平均値からの偏差は、平均遅延の変化、マーキングレートの変動、トランスポートプロトコルによって使用される平均パケットサイズ、経路上のパケットの再配置や損失等の要因による可能性が高い。

これに対して、持続的な負のデルタは、持続的なチーティング挙動、すなわち、ネットワークにおける輻輳寄与を過少申告している送信側ホストの存在を意味し、持続的な正のデルタは、輻輳に対する過大反応を示す。監査機能が測定に関心があるのは負のデルタである。というのは、過大申告は入口ポリサ１１２によってネットワーク入口ですでにレート制限されるからである。平均偏差に対する２つの場合を図３に例示している。持続的な負のデルタを図３ａに示し、持続的な正のデルタを図３ａに示している。

一般的に、チーティング挙動は、図３に関して説明したように正または負のいずれかの、支配的ユーザストラテジからの偏差として定義することができる。しかし、本発明が目的とするのは、図３ａに示す負の偏差のみと、経路出口におけるその分析および測定である。というのは、輻輳過大申告（図３ｂに示すような正のデルタを伴う）は、入口ポリサ１１２によってユーザ効用に正味の減少が課されることを意味するからである。経路特性の変化に起因する負の偏差を、送信側ホストによって明示的に導入される負の偏差から区別するのは微妙な違いである。慎重な分析をしないと、正直なフローが、経路出口で不正なフローのように見える可能性がある。

チーティングをモデル化する１つの方法は、輻輳マークされたデータ量とその応答のデータ量との比をセンダにおいて操作することである。この比をチート比と定義することができる。与えられた比に対して、経路出口における平均値を分析するために、ある一定の程度の応答のみが可能である。

また、センダが経路輻輳を過少申告している時間の長さとチート比を組み合わせたチートサイクルを定義することができる。与えられたチートサイクルに対して、新たなチーティング挙動を定義し、経路出口で偏差を測定することが可能である。１つのアプローチは、短いがチーティングの程度は高いチートサイクルである。このようなパターンが、固定または可変の時間間隔で反復されることが可能である。これに対して、チートサイクルの長さを増大させるがチーティングの程度すなわちチート比は低くすることによって、同様の効果を奏することが可能である。このような挙動の豊富なセットが、監査機能あるいはパケットドロッパの反応時間とペナルティ挙動を分析するためのさまざまなシナリオを提供する。図４は、３つの異なるチーティングパターンを示している。実線の曲線は短期間の高いチート比を示し、破線の曲線は長期間だが低いチート比のチートパターンを示している。最後に点線の曲線は、ある期間にわたってランダムな挙動を示している。出口で観測されるチーティング領域と非チーティング領域とを対照させるために、カットオフしきい値が概念的に示されている。まとめると、注目すべき点として、出口では、チーティング挙動はチート比、チートサイクルの長さ、およびこれに加えて、全トラフィック集合におけるチーティングユーザ数という尺度で分類することができる。

図５は、本発明の実施形態によるパケットドロッパ／監査機能５００のフレームワークを模式的に例示している。例示した実施形態は、全部で５個のコンポーネントを含む。これらは、不適合（チーティング）ユーザトラフィックを識別／検出しペナルティを科すために順次使用されるトラフィック分析モジュールである。なお、注意すべき重要な点であるが、各コンポーネントは自己のアルゴリズムを実施し、複数のコンポーネントあるいは複数のコンポーネントの組合せを使用することにより、さまざまな監査機能の実施態様を想定することができる。

以下、図５のパケットドロッパ５００の各コンポーネント、それらの基本機能、およびこれらのコンポーネントが協働してユーザの輻輳応答における時間変化する不適合性を確認する方法について、さらに詳細に説明する。当業者には明らかなように、各コンポーネントは、具体的に説明した以外のアルゴリズムや実施態様により、以下で説明するのと同様の効果を奏することも可能である。

集合監視モジュール５１０−ステップ１
集合監視モジュール５１０は、出口における全トラフィック集合に対して現在監視されている不適合性の量（すなわち、図２〜図４に関して説明したデルタのサイズ）を測定する際に、経路特性をマッピングすることを担当する。その動機は、出口における全集合はいつでも適合および不適合の両方のユーザトラフィックからなるという事実に由来し、それは不適合性の重大さを意味するからである。集合監視モジュール５１０は、集合トラフィックのみを監視することによって、複数のトラフィック分析ステップのうちの第１のトラフィック分析ステップを実行する。この測定に基づいて、監査機能の他のコンポーネントは、連続するトラフィック分析ステップを実行するよう起動されることが可能である。集合監視モジュール５１０は全トラフィックを監視しているので、フロー識別子に関して、任意の時刻にすべての識別子からなるスーパーセットを見ている。集合監視モジュール５１０の機能についてさらに詳細には、図６に関して後述する。

最新状況分析モジュール５２０−ステップ２
集合監視モジュール５１０が、ある時間単位に対する輻輳パケットとその応答パケットとの間のデルタのゼロ平均値からの偏差の有意な変化を通知する場合、集合監視モジュール５１０は、最新状況分析モジュール５２０を起動するための刺激として使用されてもよい。このモジュールは、すべてのフロー識別子（全集合）からなるスーパーセットから、最近輻輳マーキングを受けたパケットまたは輻輳応答マーキングが最近挿入されたパケットを含むフローに属するフロー識別子のサブセットを識別することを目的とする。これらのパケットはそれぞれ、図１の斜線を施したパケット１２２および塗りつぶしたパケット１２０に対応する。最新状況分析モジュール５２０の尺度は、輻輳公示対応ネットワークにおける輻輳パケットまたは応答パケットである。その動機は、偏差の変化はマークされたパケットを最近受け入れたフローに起因し、フローのこのサブセットのうちに、輻輳応答において不適合なものがある可能性が高いという観測に由来する。なお、サブセットのサイズは、集合監視モジュール５１０によってステップ１で分析されたフローのスーパーセットのサイズ以下となる可能性が高い。

チータ検出モジュール５３０−ステップ３
最新状況分析モジュール５２０によってステップ２で識別されたフローのサブセットは、実際に不適合であるフローのサブセットを再び判定するチータ検出モジュール５３０に渡される。不適合性は、図４に関して説明したように、いかなる想定可能なチーティングパターンに起因することもあり得るので、チータ検出モジュール５３０は、ステップ２チータ検出モジュール５３０で識別されたサブセットの各要素に対して、より短い期間だけ、変位した平均があるかどうかを監視する。このモジュールの尺度は、図２〜図４に関して説明したデルタである。これは、輻輳マークパケットのデータ量と輻輳応答パケットのデータ量との差分を示す。チータ検出モジュール５３０は、所定数Ｎ個のサンプルを観測することによって、または、その期間に到着するサンプル数とは独立の時間単位に基づく観測を実行することによって、デルタを測定するように構成されてもよい。結果として得られるデルタが（図４に示したような）所定のカットオフしきい値を下回る場合、対応するフローは適合フローと認定され、対応するフロー識別子はこのステップで廃棄される。他方、結果が所定のカットオフしきい値を超える場合、対応するフローは不適合フローと認定され、さらに分析するためにモジュールに保持される。チータ検出モジュール５３０の好ましい実施態様の実施形態については、図７に関してさらに詳細に後述する。

詳細フロー分析モジュール５４０−ステップ４
チータ検出モジュール５３０によってステップ３で不適合と識別されたフロー識別子のサブセットは、廃棄動作を適用する詳細フロー分析モジュール５４０に渡される。このモジュールの尺度は、不適合トラフィックに対して、ある時間単位にわたる欠損を累積することである。パケット廃棄は、偏差の増大とともに増大することになる。詳細フロー分析モジュール５４０は、廃棄が持続的である場合にのみ、当該サブセットトラフィックを観測し続けるように、自己制御的とすべきである。後のある時点で、トラフィックが適合的であることがわかった場合には、そのインスタンスは自動的に低減されるべきである。

廃棄挙動モジュール５５０−ステップ５
廃棄挙動モジュール５５０は、さまざまなペナルティ挙動を有するように独立のままに保持される。廃棄確率は、ステップ４で説明したように、現在累積されている欠損に基づいてモデル化されてもよい。ステップ４で識別されたフローのサブセットのみが、何らかの判断基準に基づいて廃棄動作を受けてもよい。

なお、注意すべき重要な点であるが、上記の実施態様は、本発明によるパケットドロッパを実現する１つの可能性に過ぎず、多くの他の具体的実施態様を想定することができる。例えば、軽量でステートレスな（すなわちフローを区別しない）パケットドロッパの実施態様では、２つのコンポーネント、すなわち、集合監視モジュール５１０および廃棄挙動モジュール５５０のみがあればよい。集合監視モジュール５１０は、輻輳およびその応答の履歴を集計し追跡するだけであってもよい。その場合、移動差分に基づいて、廃棄確率が廃棄挙動モジュール５５０によって計算されることが可能である。例えば、このような実施態様は、少数の加入者および比較的少数のフローのみを有する無線ネットワークにおける配備に有利であることがわかる。

これに対して、混成実施態様では、さらに２つのコンポーネント、すなわち最新状況分析モジュール５２０および詳細フロー分析モジュール５４０を実装する必要がある。最新状況分析モジュール５２０は、全集合におけるチーティングフローをフィルタリングして除去するために必要である。また、詳細な分析のため、アクティブな監査機能インスタンスを維持しなければならない。

図６は、本発明の実施形態による集合監視モジュール５１０の実施態様を模式的に例示している。一般的なアプローチは、全トラフィック集合について輻輳マークパケットおよび輻輳応答パケットを集計することにより経路出口における全体的な傾向を追跡することである。この目的のため、図６に示すように、集合監視モジュール５１０は、入力ストリームとして、ネットワーク出口における全トラフィック集合、すなわち、すべてのフローからなるスーパーセットを受信する。この集合から、集合監視モジュール５１０は、輻輳マークパケット、すなわち、中間ルータによりＥＣＮ（明示的輻輳通知）ビットがセットされてマークされたパケットを含むフローと、輻輳応答パケット、すなわち、ユーザによって輻輳へのその寄与を宣言することによりマークされたパケットを含むフローとを判定する。

集合監視モジュール５１０は、上記の２つのストリームの移動平均を追跡する。これらの移動平均は、図６では、「ｃｏｎ」（＝集計された輻輳マークパケットの移動平均）および「ｒｅｓ」（＝集計された輻輳応答パケットの移動平均）として表されている。図６の式において、変数ｗは、移動平均の効率的な更新のための、測定された輻輳履歴に対する実装固有の重み係数を表す。変数ｃｏｎ_ｐｋｔは、出口における最新の到着輻輳パケット、すなわち、平均輻輳（すなわち「ｃｏｎ」の値）がそれにより更新されるサンプルを表す。これに対応して、変数ｒｅｓ_ｐｋｔは、出口における最新の到着応答パケット、すなわち、平均応答（すなわち「ｒｅｓ」の値）がそれにより更新されるサンプルを表す。いずれの場合にも、更新された平均を計算するために、最新パケットのバイト数単位でのサイズが考慮される。

２つの平均値に基づいて、集合監視モジュール５１０は、対応するリンクが出口において受けている正味の欠損「デルタ」を追跡する。「カットオフ」しきい値（図４を参照）が、集合監視モジュール５１０によって保持される。「カットオフ」しきい値は、リンクに対する移動デルタが、理想的なゼロ平均値から許容可能な偏差内にあることを意味する。デルタ値が「カットオフ」しきい値を超えると、集合監視モジュール５１０は、出口における状態管理を起動する。この目的のため、本発明の一実施形態では、不適合なフロー識別子を含む可能性のある２つのストリーム「ｃｏｎ」および「ｒｅｓ」を含む出力ストリームが、さらに検査をするために、最新状況分析モジュール５２０に渡される。

図７は、本発明の実施形態によるパケットドロッパの並列監査機能インスタンスによる状態管理を例示する図である。輻輳集合から不正なフローを識別するため、監査機能／パケットドロッパの実施態様において、フィルタリングおよび観測の２段階プロセスが使用される。フィルタリング段階は、一実施形態では上記の集合監視モジュール５１０および最新状況分析モジュール５２０によって実行される。フィルタリング段階において、輻輳を受けているフローが、精密な分析のために輻輳集合から分離される。これに続く観測段階は、一実施形態ではチータ検出モジュール５３０および詳細フロー分析モジュール５４０によって実行される。観測段階について、図７を参照して以下で説明する。

観測段階では、実際の輻輳寄与を過少申告しているチーティング／不正フローを判定するために、フィルタリング段階で分離されたフローがさらに詳細に分析される。この目的のため、チータ検出モジュール５３０は、図７の右側に示されている最新マークテーブル７１０を管理する。最新マークテーブル７１０は、最新状況分析モジュール５２０によって提供され、このモジュールから、マークされたパケットを含むと識別されたフローを受け取る。それらのフローは、ソフトプッシュまたはハードプッシュのいずれかによって最新マークテーブル７１０に登録される。ソフトプッシュは、エントリに必要なスペースがテーブル内ですでに利用可能な場合、すなわち、特に何もする必要がない場合に実行される。

他方、テーブルがすでにフルである場合、すなわち、例えばドロッパ状態管理を消耗させようと試みる悪意ユーザによって一種のメモリ制約が引き起こされている場合には、ハードプッシュが実行される。このような場合、各テーブルエントリに関連づけられた制御条件を用いて、どのフローエントリが、最新マークテーブル７１０に入れられ「なければならない」新規到着フローによって置換される可能性が最も高いと考えられるかを調べる。例えば、あるしきい値に対してＮ個のサンプルが監視され、例えばＮ−２個のサンプルがすでに監視済みの場合、このフローは、新規到着フローのためのスペースを空けるためにテーブルから取り出すことができる。制御条件により、必要な任意の判断基準に基づいて、テーブル内でフローを「ソート」することが可能である。最終的に、ハードプッシュは、この制御条件を用いてメモリ制約を軽減し、新規到着トラフィックのためのスペースを空ける。不適合フローも置換される可能性があることが問題となり得るので、最新マークテーブル７１０内で不適合性に関して明示的にトラフィックを順位付けすることによって、この置換を最小限にするようにする。

図７の実施形態では、最新マークテーブル７１０は、ハッシュ値、最新状態および制御条件という３個のエントリを有する。ハッシュ値は、ＩＰヘッダから取得可能なフローパラメータ、すなわち、ソースアドレス、ソースポート、宛先アドレス、宛先ポートおよびトランスポートに対して計算される。最新状態は、一定の実装固有しきい値と、計算されたデルタ、すなわち、与えられたエントリに対する移動欠損とを含む。計算されたデルタが指定されたしきい値を超える場合、対応するエントリが観測テーブル７２０にプッシュされる。観測テーブル７２０について、以下でさらに詳細に説明する。

最新マークテーブル７１０は固定サイズであることから、テーブル内の各エントリに対応して、そのエントリがテーブル内に保持される可能性が高い期間を暗黙的に定義する制御条件が関連づけられている。これは、チーティングパターンを検出し、それによりフローをチーティングと分類するための最大許容時間である。また、その期間としきい値との組合せが、さまざまなチーティング挙動に対する感度を定義する。

前のモジュール（最新状況分析モジュール５２０）の起動挙動に基づいて、チータ検出モジュール５３０の制御条件は、自己制御およびプッシュ動作に分類される。自己制御の場合、任意のエントリがそれ自身で削除される一方、プッシュ動作の場合、最新状況分析モジュール５２０が最新マークテーブル７１０でエントリの追加または削除を行う。可能な制御条件として、最新のｎ個の輻輳サンプルのみを観測し、欠損がしきい値を超えて負でない場合、エントリをテーブルから取り出すことができる。

同様に、最新マークテーブル７１０が、あるフローを潜在的チータとして識別している場合、そのエントリが最新テーブル７１０から削除され、その状態が観測テーブル７２０に透過的に渡される。観測テーブル７２０は図７の左側に示されている。観測テーブル７２０は、詳細フロー分析モジュール５４０によって管理され、ここでは、監査機能の実際のインスタンスが、廃棄動作を慎重に分析し施行するために開始される。観測テーブル７２０は、最新輻輳履歴のＥＷＭＡ（指数加重移動平均）と、フローがテーブル内にとどまる可能性が高い時間の長さを判定するための制御条件とを保持する。観測テーブル７２０もまた、各エントリに対して定義される自己制御およびプッシュ動作を有する。観測テーブル７２０に属するトラフィックは、集合監視モジュール５１０によって、対応する監査機能インスタンスに透過的に渡される。ここで、注意すべき重要な点であるが、最新マークテーブル７１０のみが、観測テーブル７２０に対するプッシュ動作を起動することができる。最新マークテーブル７１０は、最近検出したマークされたパケットの状態を保持する高速キャッシュとして実現されてもよい。制御条件が満たされると、それらの状態が観測テーブル７２０にプッシュされる。観測テーブル７２０の可能な制御条件として、連続する廃棄動作間でパケットカウントを保持することがある。不正フローとして誤って識別された正直なフローは、低い廃棄頻度を有するであろう。これに対して、不正フローは、ほとんどの時刻に高い廃棄頻度を維持する可能性が非常に高い。

図８は、本発明の実施形態によるパケットドロッパ実施態様に対する制御ループを例示する図である。図中、以下の略記を使用する。ＯＢ＝観測テーブル７２０、ＲＳ＝最新マークテーブル７１０、ＭＰ＝マークされたパケット、ＳＣ＝自己制御、ＨＰ＝ハードプッシュ。

それぞれのマークされたパケットは、輻輳アグリゲータ８１０を更新し、実施態様は、リンクに沿った累積欠損を最小化しようとする。輻輳アグリゲータ８１０は、テーブル内のフローの現在位置に応じて、トラフィックを観測テーブル７２０と最新マークテーブル７１０との間で分割する。到着パケットが、詳細フロー分析モジュール５４０の観測テーブル７２０にすでに含まれるフローの一部である場合、対応するインスタンスが取得され、対応する状態が更新され（すなわち、デルタの現在の値が保存される）、廃棄動作が適用される。これは、パケットが廃棄されるか（ある所定の判断基準が満たされる場合）、自己制御に従うかであることを意味する。自己制御条件が満たされる場合、対応するインスタンスが削除され、パケットはステータス「ｅｎ−ｑｕｅｕｅ」（キューに入れる）が割り当てられる（すなわち、パケットは受信側ホストへ転送される）。制御条件が満たされない場合、パケットは、観測テーブル７２０から対応するインスタンスを削除せずに受信側ホストへ転送される。

これに対して、到着パケットのフローが観測テーブル７２０にまだ含まれていない場合、そのパケットがチータ検出モジュール５３０の最新マークテーブル７２０にすでに含まれているかどうかのチェックが実行される。含まれている場合、対応する状態が更新され、プッシュ動作が開始される。更新された状態が、指定されたしきい値を超えるデルタを含む場合、すなわち、対応するフローが潜在的チータとして識別されている場合、エントリは観測テーブル７２０に渡され、そのエントリは最新マークテーブル７１０から削除されるか（ハードプッシュの場合）、または保持される。

最後に、到着パケットのフローが観測テーブル７２０にも最新マークテーブル７１０にも含まれていない場合、そのパケットがマークされたパケット（輻輳または応答）であるかどうかのチェックが実行される。マークされたパケットである場合、フローは最新マークテーブル７１０パケットに登録され、マークされたパケットでない場合、パケットは目的の受信側ホストへ送信されるように準備される。

一般的に、注意すべき重要な点であるが、パケット廃棄は、並列監査機能／パケット廃棄インスタンスによって慎重に監視されるフローに対してのみ施行される。

図９は、無線ネットワークにおけるアプリケーションに対する本発明の実施形態を例示している。これにより、エアインタフェース（ＭＡＣ層）輻輳が、無線基地局（例えばＬＴＥにおけるｅＮｏｄｅＢ９００）におけるマーカエンティティ９１０によって捕捉される。不適合性（すなわちチーティング挙動）を確認しペナルティを科すため、監査機能エンティティ（これは、例示した実施形態ではＲｅ−ＥＣＮドロッパ９２０である）と、エアインタフェースにおいて測定された現在の廃棄／マーク確率との間でのレイヤ間情報交換が可能とされる。このアプローチにより、不適合性（チーティング）は、図９に示したようなエアインタフェースでの現在の輻輳を考慮する。

上記の説明および添付図面の記載に基づいて、当業者は本発明の多くの変形例および他の実施形態に想到し得るであろう。したがって、本発明は、開示した具体的実施形態に限定されるものではなく、変形例および他の実施形態も、添付の特許請求の範囲内に含まれるものと解すべきである。本明細書では特定の用語を用いているが、それらは総称的・説明的意味でのみ用いられており、限定を目的としたものではない。

Claims (11)

1. 輻輳公示対応ネットワークにおけるパケットドロッパの動作方法において、
   送信側ホストと受信側ホストが、中間ルータを経由するネットワーク経路上でパケットのフローを送信することによって相互に通信し、輻輳を検出すると、前記フローのパケットを輻輳パケットとしてマークし、
   輻輳が輻輳フィードバックメカニズムによって送信側ホストに通知され、
   送信側ホストは、輻輳通知を受信すると、送信するパケットのサブセットを輻輳応答パケットとして宣言することにより、輻輳応答パケットの量が通知された輻輳レベルと均衡するか否かに応じて適合フローまたは不適合フローのいずれかを生成し、
   前記パケットドロッパが、前記不適合フローを識別する一連のトラフィック分析ステップを順次実行し、
   前記一連のトラフィック分析ステップのうちの最初のステップが、ネットワーク出口で全トラフィック集合を監視し、該全トラフィック集合に対して前記輻輳マークパケットおよび前記輻輳応答パケットを集計することを含み、
   前記一連のステップのうちの後続ステップは、前記輻輳マークパケットと前記輻輳応答パケットとの移動差分が所定しきい値を超える場合に起動され、
   前記後続ステップのうちの第１ステップが、前記移動差分に基づいてパケットの廃棄確率を計算することを含む
   ことを特徴とする、パケットドロッパの動作方法。
2. 前記後続ステップのうちの第１ステップが、前記全トラフィック集合から、輻輳パケットとして最近マークされたパケットを含むフローのサブセットを識別することを含むことを特徴とする請求項１に記載の方法。
3. 前記後続ステップのうちの第２ステップが、前記第１ステップで求めたフローのサブセットの各要素に対して、より短い期間、前記輻輳マークパケットと前記輻輳応答パケットとの差分を観測することを含むことを特徴とする請求項２に記載の方法。
4. 観測が、所定数のサンプルパケットに対して実行されることを特徴とする請求項３に記載の方法。
5. 観測が、所定期間内に到着するすべてのパケットに対して実行されることを特徴とする請求項３に記載の方法。
6. 前記後続ステップのうちの第３ステップが、前記第２ステップの分析で前記輻輳マークパケットと前記輻輳応答パケットとの差分が所定しきい値を超えたフローに対して廃棄動作を適用することを含むことを特徴とする請求項３ないし５のいずれか１項に記載の方法。
7. 所定期間にわたって累積された前記輻輳マークパケットと前記輻輳応答パケットとの差分の増大とともに、パケット廃棄数を増大させることを特徴とする請求項６に記載の方法。
8. 輻輳公示対応ネットワークにおいて用いられるパケットドロッパにおいて、
   送信側ホストと受信側ホストが、中間ルータを経由するネットワーク経路上でパケットのフローを送信することによって相互に通信し、輻輳を検出すると、前記フローのパケットを輻輳パケットとしてマークし、
   送信側ホストに輻輳を通知するように構成された輻輳フィードバックメカニズムが設けられ、
   送信側ホストは、輻輳通知を受信すると、送信するパケットのサブセットを輻輳応答パケットとして宣言することにより、輻輳応答パケットの量が通知された輻輳レベルと均衡するか否かに応じて適合フローまたは不適合フローのいずれかを生成し、
   前記パケットドロッパが、前記不適合フローを識別するために順次使用される複数のトラフィック分析モジュールを備え、
   前記トラフィック分析モジュールが、ネットワーク出口で全トラフィック集合を監視し、該全トラフィック集合に対して前記輻輳マークパケットおよび前記輻輳応答パケットを集計するように構成された集合監視モジュールを含み、
   前記トラフィック分析モジュールが、前記全トラフィック集合から、輻輳パケットとして最近マークされたパケットを含むフローのサブセットを識別するように構成された最新状況分析モジュールを含み、
   前記トラフィック分析モジュールが、前記最新状況分析モジュールによって識別されたフローのサブセットの各要素に対して、より短い期間、前記輻輳マークパケットと前記輻輳応答パケットとの差分を観測するように構成されたチータ検出モジュールを含む
   ことを特徴とするパケットドロッパ。
9. 前記集合監視モジュールは、前記輻輳マークパケットと前記輻輳応答パケットとの移動差分が所定しきい値を超える場合に、前記複数のトラフィック分析モジュールのうちの後続モジュールを起動するように構成されることを特徴とする請求項８に記載のパケットドロッパ。
10. 前記トラフィック分析モジュールが、前記チータ検出モジュールで前記輻輳マークパケットと前記輻輳応答パケットとの差分が所定しきい値を超えたフローに対して廃棄動作を適用するように構成された詳細フロー分析モジュールを含むことを特徴とする請求項８に記載のパケットドロッパ。
11. 前記トラフィック分析モジュールが、所定の判断基準に基づいて廃棄確率をモデル化するように構成された廃棄挙動モジュールを含むことを特徴とする請求項１０に記載のパケットドロッパ。
    

Images