4

ネットワーク監視システムからのIPアドレスの分布(ヒストグラム)を数えるための簡単なクラスが必要です。1から1010のパケットがあり、 1から2の32アドレス(IPv6インターフェイスがある場合はそれ以上)があります。私が理想的に探しているのは、ヒストグラムを自動的に作成し、制限に達したときに、ある種のプレフィックスルーティングを介してあまり人気のないノードの結合を開始するC++クラスです。

誰かがこのようなことを知っていますか、それとも私はそれを書く必要がありますか?

ありがとう!

4

4 に答える 4

6

あなたが説明していることは、Count-Minスケッチデータ構造の完璧なユースケースのように聞こえます。このデータ構造は、データストリームからのさまざまな要素の頻度を概算するために使用され、特定の量のメモリを正確に使用するように調整できます。さらに、固定のメモリ制限が与えられた場合、それがどれだけ正確であり、あなたが望む正確な答えにどれだけ近いかを調整することができます。私の理解では、Googleはこのデータ構造を使用して、ばかげた量のディスク領域を使用せずに頻繁な検索を識別します。

追加のプラスとして、データ構造は特定の値の真の頻度を過小評価することはありません。つまり、特定のIPアドレスをどのくらいの頻度で表示したかを照会する場合、Count-Minスケッチは常に実際の数以上の値を提供します。

Count-Minスケッチは、実装が非常に簡単です。必要なのは、さまざまなハッシュ関数と2D配列だけです。また、データ構造に関するGoogleのページで、Count-Minスケッチのさまざまな実装を見つけることができます。

お役に立てれば!

于 2013-01-08T23:05:54.907 に答える
2

近似解については、@templatetypedefに+1します。

完全を期すために、正確な数を保存する必要がある場合、正確な数を保存する方法はありません。ただし、要件によっては、必要なスペースを大幅に削減できる場合があります(たとえば、10。*。*。*および192.68。*。* ipsをパブリックにルーティングすることはできません。また、25。*などの他の多くのIPもルーティングできません。 。*。*、現在、パブリックルーティングされていません)また、 (要件によっては)重要度の低いIPの大規模なグループを一緒にカウントできる場合もあります。

必要なスペースを十分に減らすことができれば、を使用してカウントを可能な限りコンパクトにメモリに保存できますbitset。ip-addressをbitset-addressにマップする簡単な方法がない場合は、簡潔なトライのようなものを使用してそれらをマップする必要があります。簡潔なトライでは、ip-groupごとに1バイト(アモライト化)が必要になります。

また、十分に下げることができない場合は、データベースを使用して、パフォーマンスの低下を受け入れる必要があります。

于 2013-01-08T23:33:53.083 に答える
0

ボーダーゲートウェイプロトコル(BGP)またはGRiDAアルゴリズムを確認できます。

于 2013-01-08T22:47:46.013 に答える
0

私はこの問題を解決するためのアルゴリズムを開発しました。アルゴリズムは、IPアドレスカウントを基数木/プレフィックスツリーに保存します。各ノードは、アドレスの次のビットと、それがターミナルノードの場合はカウントを記録します。ノードが多すぎる場合、ノードはツリーの範囲から結合されます。カウントが最も少ないリーフを持つノードが最初に結合されます。

とてもエレガントでとても速いです。興味があればC++コードを投稿できます。

于 2013-01-11T21:04:57.853 に答える