Finding Cardinality Heavy-Hitters in Massive Traffic Data and Its Application to Anomaly Detection
スポンサーリンク
概要
- 論文の詳細を見る
We propose an algorithm for finding heavy hitters in terms of cardinality (the number of distinct items in a set) in massive traffic data using a small amount of memory. Examples of such cardinality heavy-hitters are hosts that send large numbers of flows, or hosts that communicate with large numbers of other hosts. Finding these hosts is crucial to the provision of good communication quality because they significantly affect the communications of other hosts via either malicious activities such as worm scans, spam distribution, or botnet control or normal activities such as being a member of a flash crowd or performing peer-to-peer (P2P) communication. To precisely determine the cardinality of a host we need tables of previously seen items for each host (e. g., flow tables for every host) and this may infeasible for a high-speed environment with a massive amount of traffic. In this paper, we use a cardinality estimation algorithm that does not require these tables but needs only a little information called the cardinality summary. This is made possible by relaxing the goal from exact counting to estimation of cardinality. In addition, we propose an algorithm that does not need to maintain the cardinality summary for each host, but only for partitioned addresses of a host. As a result, the required number of tables can be significantly decreased. We evaluated our algorithm using actual backbone traffic data to find the heavy-hitters in the number of flows and estimate the number of these flows. We found that while the accuracy degraded when estimating for hosts with few flows, the algorithm could accurately find the top-100 hosts in terms of the number of flows using a limited-sized memory. In addition, we found that the number of tables required to achieve a pre-defined accuracy increased logarithmically with respect to the total number of hosts, which indicates that our method is applicable for large traffic data for a very large number of hosts. We also introduce an application of our algorithm to anomaly detection. With actual traffic data, our method could successfully detect a sudden network scan.
- （社）電子情報通信学会の論文
- 2008-05-01
著者
-
小林 淳史
日本電信電話株式会社NTT情報流通プラットフォーム研究所
-
小林 淳史
NTT情報流通プラットフォーム研究所
-
Asano Shoichiro
National Institute Of Informatics
-
Asano Shoichiro
National Center For Science Information Systems
-
Hirokawa Yutaka
Ntt Information Sharing Platform Laboratories Ntt Corporation
-
Kobayashi Atsushi
NTT Information Sharing Platform Laboratories
-
Mori Tatsuya
Ntt Service Integration Laboratories Ntt Corporation
-
Kawahara Ryoichi
NTT Service Integration Laboratories NTT Corporation
-
ISHIBASHI Keisuke
NTT Information Sharing Platform Laboratories, NTT Corporation
-
小林 淳史
日本電信電話株式会社 情報流通プラットフォーム研究所
-
YAMAMOTO Kimihiro
NTT Information Sharing Platform Laboratories, NTT Corporation
-
SAKAMOTO Hitoaki
NTT Information Sharing Platform Laboratories, NTT Corporation
-
Kobayashi Atsushi
Ntt Information Sharing Platform Laboratories Ntt Corporation
-
Kawahara Ryoichi
Ntt Service Integration Laboratories Nippon Telegraph And Telephone Corporation
-
Asano Shoichiro
Nii Tokyo Jpn
-
Ishibashi K
Ntt Information Sharing Platform Laboratories Ntt Corporation
-
Ishibashi Keisuke
Ntt Information Sharing Platform Laboratories Ntt Corporation
-
Ishibashi Keisuke
Ntt Information Sharing Platform Laboralories Ntt'corporation
-
Yamamoto Kimihiro
Ntt Information Sharing Platform Laboratories Ntt Corporation
-
Sakamoto Hitoaki
Ntt Information Sharing Platform Laboratories Ntt Corporation
-
Ishibashi Keisuke
Ntt Information Sharing Laboratories Ntt Corporation
-
Kobayashi Atsushi
Ntt Information Sharing Laboratories Ntt Corp.
関連論文
- 2.IPフロー計測技術と標準化 : NetFlow,sFlow,IPFIX,PSAMP技術(IP網トラヒック計測)
- BGP経路情報とフローデータによるトラヒック変動監視システムの提案 (インターネットアーキテクチャ)
- BGP経路情報とフローデータによるトラヒック変動監視システムの提案 (技術と社会・倫理)
- 異なり数上位Nホストの推定および異常検出への応用(トラヒック,一般)
- フロー計測技術を用いた多目的トラヒック計測技術の検討(通信品質,計測技術,インターネット運用・管理,一般)
- フロー計測技術による大規模VoIPトラヒック品質計測システムの提案(NW管理,次世代NWアーキテクチャ,次世代NWのオペレーションアーキテクチャ,トラヒック計測・モデリング・品質,オーバレイネットワーク,次世代NWサービス品質,一般)
- BS-6-4 フロー計測技術におけるExporterとCollectorの連携手法の検討(BS-6.ネットワーク情報収集およびセンシングとそのネットワーク制御への活用に関する技術,シンポジウムセッション)
- BS-6-5 フロー計測技術を用いたマルチキャスト・トラヒック監視手法の検討(BS-6.ネットワーク情報収集およびセンシングとそのネットワーク制御への活用に関する技術,シンポジウムセッション)
- B-7-9 Elephantフローを用いた経路同定手法(B-7. 情報ネットワーク,一般セッション)
- 大規模ネットワーク向け異常トラヒック監視システムの開発 (特集 広域異常トラヒック検知・制御システムの研究開発)
- 選択的sFlowによる大規模VoIPトラヒック品質測定手法の提案(次世代ネットワークアーキテクチャ,次世代ネットワークのオペレーションアーキテクチャ,トラヒック計測・モデリング・品質,オーバレイネットワーク,一般)
- 大規模バックボーンネットワークにおけるアプリケーション異常トラヒック検出方式の提案(セキュリティ,オーバーレイネットワーク,VPN,DDoS,ネットワークセキュリティ,P2P通信,ネットワークソフトウェア,一般)
- フロー・メディエータを用いた大容量トラフィック・コレクタの設計(サービス管理・ビジネス管理,料金管理,及び一般)
- B-7-17 トラフィック・フロー情報の効率的な配信手法の提案(B-7.情報ネットワーク,一般講演)
- 選択的sFlowルータの実装とトラフィック分析手法の提案
- 選択的sFlowによるVoIPトラフィックのゆらぎ測定方法の提案(触覚,五感メディアの品質,一般)
- 次世代ネットワーク向けトラフィック交流監視コレクタの提案(インターネットの品質評価・品質管理技術,ネットワーク品質,トラヒック計測,一般)
- 次世代バックボーン向け大容量トラフィック・コレクタの提案(サービス管理,ビジネス管理,料金管理,及び一般)
- BGP経路情報とフローデータによるトラヒック変動監視システムの提案(経路制御技術,インターネットと情報倫理教育,一般)
- IPFIX/PSAMPを用いたデータリンク層のトラヒック監視の提案と実装(ネットワーク性能評価,インターネットと情報倫理教育,一般)
- 次世代バックボーン向け大容量トラフィック・コレクタの提案(サービス管理・ビジネス管理,料金管理,及び一般)
- BS-5-11 次世代バックボーン向けトラヒック監視システムの開発(BS-5.次世代ネットワーク構築に向けた品質・トラヒック計測技術,シンポジウム)
- BS-5-10 フロー・コンセントレータの構成モデルの提案(BS-5.次世代ネットワーク構築に向けた品質・トラヒック計測技術,シンポジウム)
- BS-5-1 異なり数上位Nホスト推定および異常検出への応用(BS-5.次世代ネットワーク構築に向けた品質・トラヒック計測技術,シンポジウム)
- IPフロー計測技術と標準化 : NetFlow, sFlow, IPFIX, PSAMP技術
- Structures of Human Relations and User-Dynamics Revealed by Traffic Data(Human Communication I)
- BGP経路情報とフローデータによるトラヒック変動監視システムの提案(経路制御技術,インターネットと情報倫理教育,一般)
- IPFIX/PSAMPを用いたデータリンク層のトラヒック監視の提案と実装(ネットワーク性能評価,インターネットと情報倫理教育,一般)
- フロー・メディエータを用いた大容量トラフィック・コレクタの設計(サービス管理・ビジネス管理,料金管理,及び一般)
- 次世代ネットワーク向けトラフィック交流監視コレクタの提案(インターネットの品質評価・品質管理技術,ネットワーク品質,トラヒック計測,一般)
- 次世代ネットワーク向けトラフィック交流監視コレクタの提案(インターネットの品質評価・品質管理技術,ネットワーク品質,トラヒック計測,一般)
- BS-5-9 次世代バックボーン向けトラヒック情報集約装置の開発(BS-5.次世代ネットワーク構築に向けた品質・トラヒック計測技術,シンポジウム)
- 蓄積活用型サービスマトリクスによる交換ソフトウェア品質確保の一手法
- フローデータとBGPの連携によるトラヒック分析システム(インターネット運用・管理,一般)
- VLBI Detections of Parsec-Scale Nonthermal Jets in Radio-Loud Broad Absorption Line Quasars
- Design and Architectural Concepts for Border Model Based IP/Optical Multi-Layer Service Networks(Next Generation Photonic Network Technologies)
- An Efficient Acquisition Scheme for a High Sensitivity Assisted GPS Receiver
- B-7-43 On traffic optimization through cooperation of overlay and underlay networks
- An IP Based Realtime VLBI Observation Testbed with Multiple STM-16c Links(New Applications))(Internet Technology IV)
- Development of Aggregation Device for Next Generation Backbone Networks
- Development of Aggregation Device for Next Generation Backbone Networks
- How do internet routing policies give rise to triangle inequality violations in latency measurements? (情報ネットワーク)
- QoS-Aware Overlay Routing with Limited Number of Alternative Route Candidates and Its Evaluation(Networking Technologies for Overlay Networks)
- Service Virtualization for Border Model Based Multi-Layer Service Network Architecture(New Technologies and their Applications of the Internet IV)
- Improvement of Luminescent Characteristics of BaGd_4Si_3O_:Tb Green VUV Phosphor by F-Incorporation
- Detection of TCP Performance Degradation Using Link Utilization Statistics(Network)
- Method of Bandwidth Dimensioning and Management for Aggregated TCP Flows with Heterogeneous Access Links(Internet)
- BS-9-2 Performance evaluation of QoS control to handle long-duration large flows(BS-9. Latest Trends on Information Networking Technologies)
- A Method of Bandwidth Dimensioning and Management Using Flow Statistics(Network Management/Operation)
- A Method of IP Traffic Management Using the Relationship between TCP Flow Behavior and Link Utilization(Network Management/Operation)
- Identifying Heavy-Hitter Flows from Sampled Flow Statistics(Next Generation Network Management)
- BS-4-14 How Incentive Helps in Making Peer-assisted CDN Deployable?(BS-4. System, control and design technologies for emerging network)
- Packet Sampling TCP Flow Rate Estimation and Performance Degradation Detection Method
- On the Characteristics of Internet Traffic Variability : Spikes and Elephants(Traffic Measurement and Analysis)(New Thechnologies and their Applications of the Internet)
- BS-3-15 Controlling Overlays with Overlay : Traffic Engineering through Cooperation between Overlay and Underlay
- Geometric overlay networks (ネットワークシステム)
- Finding Cardinality Heavy-Hitters in Massive Traffic Data and Its Application to Anomaly Detection
- Link Capacity Assignment in Packet-Switched Network with Existing Network Consideration
- 弱信号AGPS受信機における高速捕捉手法の誤差分析
- Capacity Dimensioning of VPN Access Links for Elastic Traffic in the Hose Model(Network)
- Capacity Dimensioning of VPN Access Links for Elastic Traffic in the Hose Model
- Proposal and Evaluation of Method to Estimate Packet Loss-Rate Using Correlation of Packet Delay and Loss(New Technologies in the Internet and their Applications)
- SB-10-2 Analysis of Relationship between TCP Flow Behavior and Utilization of Bottleneck Link
- Virtual Rate-Based Queueing : A Generalized Queueing Discipline for Switches in High-Speed Networks
- Routing Algorithms for Asymmetric Multi-Destination Connections in Multicluster Networks(Special Issue on Multimedia Communications in Heterogeneous Network Environments)
- BS-12-37 Identifying anomalous traffic sources using flow statistics(BS-12. Network Planning, Control, and Management)
- An Adaptive Load Balancing Method for Multiple Paths Using Flow Statistics and Its Performance Analysis(Network)
- VoIP Quality Measurement System Using Flow Mediation for Large-Scale IP Networks
- BS-3-1 Boosting IP reputation services(BS-3. Management and Control Technologies for Innovative Networks)
- Traffic Monitoring System Based on Correlation between BGP Messages and Traffic Data
- Effects of Sampling and Spatio/Temporal Granularity in Traffic Monitoring on Anomaly Detectability
- NACSIS-NSF Project
- Extended Darknet : Multi-Dimensional Internet Threat Monitoring System