Understanding next-hop diversity in BGP and routing structures in content networking

Abstract

오늘날 인터넷은 수만개의 AS들을 서로 연결하고 있다. AS내에서는 라우터들이 OSPF나 IS-IS등의 도메인 내 라우팅 프로토콜을 이용하여 라우팅 정보를 교환하지만, AS의 경계에 있는 라우터들은 인터넷의 도메인 간 라우팅 프로토콜에 대한 사실상의 표준인 BGP를 이용하여 라우팅 정보를 교환한다. 따라서, 네트워크들의 네트워크라고 불리우는 인터넷에 있어 라우팅은 필수불가결한 요소라 할 수 있다.

한편, 현재의 인터넷은 파일 전송이나 원격 로그인과 같은 호스트 중심의 네트워크 응용들을 지원하기 위해 설계되었다. 하지만, 최근 인터넷에 대한 측정 결과들을 보면 웹 페이지나 멀티미디어 파일들을 전송하는 컨텐트 중심의 트래픽이 점점 더 주를 이루고 있다는 점을 알 수 있다. 이러한 문제를 다루기 위해 최근 콘텐트 식별체계에 기반하여 인터넷을 다시 설계하고자 하는 많은 연구들이 발표되었다. 그러한 연구들중 가장 중요한 것은 컨텐트 식별자를 어떻게 명명할 것인지와 컨텐트 중심의 식별자에 기반하여 도메인 간의, 그리고 도메인 내의 라우팅과 레졸루션을 어떻게 처리할 것인지를 포함하는 식별자 기반의 라우팅을 어떻게 지원할 것인지라 할 수 있다. 따라서 본 학위 논문에서는 호스트 중심과 콘텐트 중심 네트워크 각각의 라우팅 성능을 탐구한다.

첫째로, BGP의 경로 다양성에 대한 측정과 분석 연구 결과를 보인다. 본 연구의 가장 주요한 목적은 네트워크의 모든 목적지에 대해 가장 좋은 단 하나의 경로만을 선택하고 전파하는 BGP의 특성에서 비롯되는 대안 경로의 부족 문제가 네트워크의 오류에 대한 견고함을 해치고 트래픽 엔지니어링에 있어서의 유연성을 부족하게 하며 네트워크 토폴로지의 변화에 적응하는 속도를 느리게 한다는 문제점과 인터넷의 풍부한 연결성을 충분히 활용하지 못하고 있다는 일반적인 우려를 확인하고자 하는 것이다. 본 학위 논문에서 우리는 인터넷의 제 1계층에 속하는 네트워크 중 하나인 ISP_A에서 2년 동안 수집된 iBGP 라우팅 정보를 이용하여 BGP의 next-hop 다양성을 측정하였다. 본 측정의 결과로 ISP_A는 대다수의 프리픽스들이 복수의 next-hop 라우터를 통해 도달가능하다는 사실을 알 수 있다. 또한, 우리는 다양한 프리픽스들에 대한 사례연구를 통해서 측정된 next-hop들의 개수에 가장 주요한 영향을 미치는 두 가지 요인이 ISP의 경로에 대한 선호도와 큰 규모의 ISP들 간에 존재하는 연결 라우터의 개수라는 사실을 알아내었다. 이러한 발견들은 BGP에 경로 다양성을 증대시키고자 하는 현재의 연구들에 대한 밑받침 자료로 사용될 수 있을 것으로 기대된다.

둘째로, 컨텐트 기반 네트워크에서의 식별자 기반 라우팅에 대해, 우리는 그 동안 제안된 연구들 중 가장 주목할만한 두 가지 라우팅 구조인 트리 구조와 DHT 구조에 대해 라우팅 확장성, 컨텐트 전송 속도, 오류에 대한 저항성 등을 종합적으로 비교 분석한 시뮬레이션 결과를 보인다. 한편, 컨텐트 중심 네트워킹을 구성하는 가장 주요한 기능으로 (i) 컨텐트를 찾는 방법, (ii) 컨텐트를 전달하는 방법, 그리고 (iii) 컨텐트를 캐싱하는 방법의 세 가지가 일컬어진다. 우리는 이중 식별자 기반의 라우팅 구조의 비교 실험에서 자세히 다루어지지 않은 세번째 기능인 컨텐트 캐싱이 컨텐트 전송 성능을 증대시키는데에 얼마나 효과적인지를 보이는 추가적인 실험을 진행하였고 본 학위 논문에서 그 결과를 밝힌다.

Today, the Internet inter-connects tens of thousands of networks called Autonomous Systems (ASes).While routers within an AS exchange routing information by employing an intra-domain routing protocol such as OSPF or IS-IS, edge routers exchange reachability information based on BGP, which is the de factor inter-domain routing protocol of Internet. Therefore, the routing is indispensable in the operation of Internet.

On the other hand, the internet was designed with host-oriented networking applications such as file transfer and remote login. However, recent internet statistics show that content-oriented traffic (e.g. web pages, multimedia clips) becomes more and more dominant. To address this issue, there have been many studies to redesign Internet based on content-oriented identification. Their studies cover various topics of Internet, but we argue the content naming and name-based routing are the most essential.

In this dissertation, we present two routing studies on (i) next-hop diversity in BGP, which is based on host-oriented paradigm and (ii) name-based routing structures in Content-oriented networking, which is based on content-oriented paradigm. First, we present our measurement and analysis studies on BGP path diversity. The major goal of our study is to verify a common concern that the rich connectivity is not fully utilized and the lack of alternative paths can reduce a networks robustness to failures as well as flexibility in traffic engineering, and can lead to slow adaptation to topological changes, which can be incurred from the selection and propagation of a single best path for a BGP router to each destination network. In this dissertation we use iBGP routing data collected from a Tier1 ISP, ISPA, over a 2-year time period to quantify BGP next-hop diversity. Our results show that ISPA reaches the majority of prefixes through multiple next-hop routers. We use several case studies of prefixes with different diversity degrees to identify two major factors that impact the number of observed next-hops: the ISPs path preference and the number of peering routers between large ISPs. This observation provides operational input to the current efforts on augmenting BGP to increase path diversity.

Secondly, we present our performance evaluation study on structured namebased routing alternatives of CON: a hierarchical tree and a flat distributed hash table (DHT) in terms of routing scalability, content transfer latency, and failure resilience through comprehensive simulations. There are three major building blocks in substantiating the CON: (i) how to locate contents, (ii) how to deliver contents, and (iii) how to cache contents. As for the last topic that is not covered by the comparison of two structures, we conduct the additional experiments to show how much in-network caching is effective in enhancing the performance of content delivery.