Understanding next-hop diversity in BGP and routing structures in content networking
BGP에서의 경로 다양성과 컨텐츠 중심 네트워크에서의 라우팅 구조에 대한 이해

DC Field Value Language
dc.description학위논문 (박사)-- 서울대학교 대학원 : 전기·컴퓨터공학부, 2012. 8. 최양희.-
dc.description.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) 컨텐트를 캐싱하는 방법의 세 가지가 일컬어진다.
우리는 이중 식별자 기반의 라우팅 구조의 비교 실험에서 자세히 다루어지지 않은 세번째 기능인 컨텐트 캐싱이 컨텐트 전송 성능을 증대시키는데에 얼마나 효과적인지를 보이는 추가적인
실험을 진행하였고 본 학위 논문에서 그 결과를 밝힌다.
dc.description.abstractToday, 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

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 network’s 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 ISP’s 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.
dc.description.tableofcontentsAbstract i
I Introduction 1
II Overview: BGP and Content-oriented networking 5
2.1 Overview of BGP 5
2.1.1 Routing in the Internet 5
2.1.2 iBGP Architectures 7
2.1.3 Path Poisoning and Hidden Paths in iBGP 8
2.1.4 Policy Routing 9
2.2 Overview of Content-oriented networking (CON) 10
2.2.1 Concept of CON 10
2.2.2 Content Naming 11
2.2.3 Name-based Routing 13
III Next-hop Diversity in BGP 17
3.1 Introduction 17
3.2 Diversities in BGP 19
3.3 Methodology 20
3.3.1 ISPA’s Topology and Next-hop Diversity 22
3.3.2 Measuring Path Diversity 23
3.4 Quantifying Next-Hop Diversity 24
3.4.1 Next-hop ASes 26
3.4.2 Next-hop POPs and Routers 27
3.5 Major Factors Impacting Next-hop Diversity 28
3.5.1 ISP’s Path Preference 30
3.5.2 Number of peering routers 31
3.5.3 Lack of Geographical Presence 32
3.6 Trends of Next-hop Diversity in Time 34
3.7 Discussions of Related Works 35
IV Performance study of name-based routing in CON 38
4.1 Introduction 38
4.2 Structured Name-based Routing of CON 41
4.2.1 Two structured approaches: Tree and DHT 43
4.2.2 In-Network Caching 46
4.2.3 Delivery Modes 47
4.3 Evaluation of structured name-based routing 48
4.3.1 Experiment setup 48
4.3.2 Comparison between two structures 53
4.3.3 In-network caching 64
4.3.4 Delivery modes 68
4.4 Evaluation of hybrid scheme 69
4.4.1 Hybrid scheme: Two-tier 70
4.4.2 Experiment setup 71
4.4.3 Evaluation Results 72
4.5 Related Work 75
V Summary & FutureWork 78
Bibliography 80
dc.format.extent1283022 bytes-
dc.publisher서울대학교 대학원-
dc.subjectBorder Gateway Protocol-
dc.subjectNext-hop diversity-
dc.subjectContent-oriented networks-
dc.subjectStructured name-based routing-
dc.titleUnderstanding next-hop diversity in BGP and routing structures in content networking-
dc.title.alternativeBGP에서의 경로 다양성과 컨텐츠 중심 네트워크에서의 라우팅 구조에 대한 이해-
dc.contributor.AlternativeAuthorJaeyoung Choi-
dc.citation.pagesix, 86-
dc.contributor.affiliation공과대학 컴퓨터공학과-
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Computer Science and Engineering (컴퓨터공학부)Theses (Ph.D. / Sc.D._컴퓨터공학부)
Files in This Item:
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.