Journal of Internet Computing and Services (인터넷정보학회논문지)

Korean Society for Internet Information (한국인터넷정보학회)
권호 표지

Power-Laws Exponents of the Domestic AS-level Internet Topology based on the Valley-free BGP Routing Policy

BGP 밸리-프리 라우팅 정책에 기반한 국내 AS 레벨 인터넷 토폴로지의 파워-로 지수

  • 강구홍 (서원대학교 정보통신공학과)
  • Received : 2010.05.06
  • Accepted : 2010.07.21
  • Published : 2010.08.30
Download PDF
⟨ Previous Next ⟩

Abstract

Faloustsos et al.[1,2] showed successfully that the power-laws describe the heavy-tailed distributions of the AS level Internet topology properties such as node degree. This result allows us to represent the characteristics of AS-level Internet topology using some power-law exponents with elegant and simple. In this paper, we obtained the power-law exponents of the domestic AS-level Internet topology properties - the node degree, the number of pairs within hops, and eigenvalues of the graph - based on the valley-free BGP routing policy. We used the real data sets from UCLA IRL laboratory, and showed that these power-laws fit the real data pretty well resulting in correlation coefficient of 90.7%, 96.5%, and 97%, respectively. In particular, rounding the effective diameter to three, approximately 91% of the pairs of nodes are within this distance; that is, we might conclude our topology is pretty well organized.

Faloutsos et al.[1,2]은 파워-로(power-law)를 이용해 노드 차수와 같은 Autonomous System (AS) 레벨 인터넷 토폴로지 특성의 중꼬리(heavy-tailed) 분포를 성공적으로 나타내었다. 이러한 결과는 파워-로 지수(exponents)를 이용해 이들 인터넷 토폴로지 특성을 간단 명료하게 나타낼 수 있게 한다. 본 논문에서는 BGP 밸리-프리 라우팅 정책에 기반한 국내 AS 레벨 인터넷 토폴로지 속성 - 노드 차수, 홉 수에 따른 노드 쌍의 수, 그리고 그래프의 고유치 - 의 파워-로 지수를 조사하였다. UCLA IRL 연구실이 제공하는 실제 AS 레벨 데이터 셋을 이용하였으며 이들 파워-로 근사는 상관계수(correlation coefficient)가 각각 90.7%, 96.5%, 그리고 97%로 조사되었다. 특히, 실질적인 AS 레벨 토폴로지 직경이 3홉 이내에 존재하는 AS 노드 쌍이 전체 91% 이상이며, 따라서 국내 AS 레벨 토폴로지가 비교적 잘 정리된 것으로 판단된다.

Keywords

References

  1. M. Faloutsos, P. Faloutsos, and C. Faloutsos, "On Power-Law Relationships of the Internet Topology," In Proc. of ACM SIGCOMM, 1999, pp. 251-262.
  2. G. Siganos, M. Faloutsos, P. Faloustsos, and C. Faloutsos, "Power-Laws and the AS-level Internet Topology," IEEE/ACM Trans. On Networking, Vol.11, No.4, 2003, pp.514-524. https://doi.org/10.1109/TNET.2003.815300
  3. L. Gao, "On Inferring Autonomous System Relationships in the Internet," IEEE/ACM Transactions on Networking, Vol.9, Issue 6, 2001, pp.733-745. https://doi.org/10.1109/90.974527
  4. I.V. Beijnum, "Building Reliable Networks with the Border Gateway Protocol", O'Reilly, 2002.
  5. R. Oliveira, D. Pei, W. Willinger, B. Zhang and L. Zhang, "In Search of the Elusive Ground Truth: The Internet's AS-level Connectivity Structure," In Proc. of SIGMETRICS'08, 2008.
  6. R. Oliveira, D. Pei, W. Willinger, B. Zhang and L. Zhang, "Quantifying the Completeness of the Observed Internet AS-level Structure," Technical Report TR-080026, Computer Science Department UCLA, 2008.
  7. B. Zhang, R. Liu, D. Massey, and L. Zhang, "Collecting the internet AS-level topology," SIGCOMM Computer Communication Review, Vol.35, Issue 1, 2005, pp. 53-61. https://doi.org/10.1145/1052812.1052825
  8. Q. Chen, H. Chang, R. Govindan, and S. Jamin, "The origin power laws in Internet topologies revisited," In Proc. of INFOCOM 2002, 2002
  9. RIPE routing information service project, available at http://www.ripe.net
  10. Route Views routing table archive, available at http://routeviews.org.
  11. UCLA IRL Internet Topology Collection, available at http://irl.cs.ucla.edu/topology
  12. J. Winick, S. Jamin, "Inet-3.0: Internet Topology Generator. Technical Report, Department of EECS, University of Michigan, 2002.
  13. C.D. Murta, J.N. Maciel, NIT: The New Internet Topology Generator. Technical Report, Department of Informatics, University Federal of Parana, 2008.
  14. 국내 AS 번호 목록, available at http://www.ip.kisa.or.kr/main.html.
  15. . M. Cvetkovic, M. Boob, and H. Sachs, "Spectra of Graphs," Academic press, 1979.