Probabilistic Top-k Query:Model and Application on Web Traffic Analysis  

作　　者：Xiaolin Gui Jun Liu Qiujian Lv Chao Dong Zhenming Lei 

机构地区：[1]Beijing Key Laboratory of Network System Architecture and Convergence,Beijing University of Posts and Telecommunications,Beijing100876,China [2]Agricultural Bank of China Beijing 100161,China

出　　处：《China Communications》2016年第6期123-137,共15页中国通信（英文版）

基　　金：supported by 111 Project of China under Grant No.B08004

摘　　要：Top-k ranking of websites according to traffic volume is important for Internet Service Providers(ISPs) to understand network status and optimize network resources. However, the ranking result always has a big deviation with actual rank for the existence of unknown web traffic, which cannot be identified accurately under current techniques. In this paper, we introduce a novel method to approximate the actual rank. This method associates unknown web traffic with websites according to statistical probabilities. Then, we construct a probabilistic top-k query model to rank websites. We conduct several experiments by using real HTTP traffic traces collected from a commercial ISP covering an entire city in northern China. Experimental results show that the proposed techniques can reduce the deviation existing between the ground truth and the ranking results vastly. In addition, we find that the websites providing video service have higher ratio of unknown IP as well as higher ratio of unknown traffic than the websites providing text web page service. Specifically, we find that the top-3 video websites have more than 90% of unknown web traffic. All these findings are helpful for ISPs understanding network status and deploying Content Distributed Network(CDN).Top-k ranking of websites according to traffic volume is important for Internet Service Providers（ISPs） to understand network status and optimize network resources. However, the ranking result always has a big deviation with actual rank for the existence of unknown web traffic, which cannot be identified accurately under current techniques. In this paper, we introduce a novel method to approximate the actual rank. This method associates unknown web traffic with websites according to statistical probabilities. Then, we construct a probabilistic top-k query model to rank websites. We conduct several experiments by using real HTTP traffic traces collected from a commercial ISP covering an entire city in northern China. Experimental results show that the proposed techniques can reduce the deviation existing between the ground truth and the ranking results vastly. In addition, we find that the websites providing video service have higher ratio of unknown IP as well as higher ratio of unknown traffic than the websites providing text web page service. Specifically, we find that the top-3 video websites have more than 90% of unknown web traffic. All these findings are helpful for ISPs understanding network status and deploying Content Distributed Network（CDN）.

关 键 词：top-k query traffic model temporal bipartite graph uncertain data unknown traffic 

分 类 号：TP393.06[自动化与计算机技术—计算机应用技术]