Method for Inferring AS Relationship Based on Temporal and Spatial Reliability
Abstract: In this paper, a new method of inferring AS relationship by analyzing the temporal and spatial reliability is proposed. Firstly, the method selects the routing tables which originate from different monitored points in different intervals. Based on the routing strategy and the hierarchical structure, the AS relationship of different monitored points is inferred in every time window. Moreover, we define and calculate the value of the temporal and spatial reliability by analyzing the spatial consistency and time stability. Furthermore, we set a threshold and regard any AS relationship with reliability value greater than the threshold as trusted relationship. In the meanwhile, we analyze the number of monitored points and the threshold to infer the influence on AS relationship’s validity. Experiment result shows that the accuracy of AS relationship deduction can be largely improved by selecting appropriate number of routing monitored points and the threshold value through our proposed methods.
文章引用: 刘 磊 , 朱培栋 , 胡照明 (2016) 一种基于时空可信度推断AS商业关系的方法。 软件工程与应用， 5， 38-46. doi: 10.12677/SEA.2016.51005
 Chen, E. (2004) BGP Support for Four-Octet AS Number Space. IETF Internet-Draft-4893, December 2004.
Gao, L. (2001) On Inferring Autonomous System Relationships in the Internet. IEEE/ACM Transactions on Networking, 9, 733-745.
Subramanian, L., Agarwal, S., Rexford, J. and Katz, R.H. (2002) Characterizing the Internet Hierarchy from Multiple Vantage Points. Proceedings of IEEE 21st Annual Joint Conference of the IEEE Computer and Communications Societies, 2, 618-627.
Di Battista, G., Erlebach, T., Hall, A., et al. (2007) Computing the Types of the Relationships between Autonomous Systems. IEEE/ACM Transactions on Networking, 15, 267-280.
Dimitropoulos, X., Krioukov, D., Fomenkov, M., et al. (2007) AS Relationships: Inference and Validation. ACM SIGCOMM Computer Communication Review, 37, 29-40.
Zhang, B., Liu, R., Massey, D., et al. (2005) Collecting the Internet AS-Level Topology. ACM SIGCOMM Computer Communication Review, 35, 53-61.
 Oliveria, R., Pei, D., Willinger, W., Zhang, B. and Zhang, L. (2008) Quantifying the Completeness of the Observed Internet AS-Level Structure. Technical Report TR-080026-2008, UCLA CS Dept.
Bron, C. and Kerbosch, J. (1973) Finding All Cliques of an Undirected Graph. Communications of the ACM, 16, 575- 576.
 Gregori, E., Improta, A., Lenzini, L., et al. (2011) BGP and Inter-AS Economic Relationships. NETWORKING 2011. Springer Berlin Heidelberg, 54-67.
Rekhter, Y. and Li, T. (1994) A Border Gateway Protocol 4 (BGP-4). RFC.
 王洪君, 于晓鹏. 一种BGP无效路由检测方法[J]. 吉林师范大学学报: 自然科学版, 2008(3) :54-57.
Luckie, M. (2014) Spurious Routes in Public BGP Data. ACM SIGCOMM Computer Communication Review, 44, 14- 21.
 邓文平, 郭敏, 胡晓峰, 等. 互联网AS拓扑的结构与连通性研究[J]. 计算机工程与科学, 2012, 34(6): 1-6.
 Mayer, D. (2015) University of Oregon Route Views Project. http://www.routeviews.org
 Route Views Project (2015) Route-Views Data. http://www.routeviews.org/data.html