Abstract
Host cardinality estimation is one crucial task in network traffic measurement. Super host is the host that exhibits anomalies in host cardinality and it is usually related to network abnormal events. Therefore, accurate host cardinality estimation is the premise of super host identification and it can be used to measure the trust degree of a network. Sketches have been widely used in super host identification. However, expanding network scale and increasing link rate bring challenges to the efficiency and accuracy of sketch-based super host identification. The size of the counters in most sketches requires a trade-off between memory resources and accuracy. To meet the need of measuring high cardinalities, large size counters are applied, which leads to memory waste in monitoring low cardinality hosts. On the other hand, most sketches have high computational overhead when tracking superhosts, resulting in inefficiency. In order to address these issues, we propose a novel memory efficient and reversible sketch, named ExtendedSketch+, to provide accurate host cardinality estimation with the purpose of super host identification and network host trust evaluation. ExtendedSketch+ achieves both high memory utilization efficiency and high accuracy, in addition to high super host identification efficiency. It applies extensible counters to record unbalanced host cardinality distribution, by adaptively expanding the counters with the increase of cardinality. It adopts a lossless traffic information transfer strategy during counter extension to ensure the accuracy of cardinality estimation. It can directly tracks the host with the highest cardinality in each bucket, which greatly improves the identification efficiency of super hosts. Based on accurate cardinality estimation of ExtendedSketch+, we can further accurately evaluate host trust degree. We theoretically analyze ExtendedSketch+ with regard to its space and time complexities and estimation accuracy. We conduct performance evaluation based on real network traffic traces. Experimental results show that ExtendedSketch+ performs better than state-of-the-art sketches regarding super host identification and provides accurate host trust evaluation.