Delay and path estimation between arbitrary points becomes even more and more crucial problem for distributed applications that heavily depend on network-internal performance. In order to deliver better performance to end-users, the Internet-wide services and applications depend on accurate information about the internal network state. Knowledge of network internals allow distributed applications to solve commonly encountered problems in their operations, such as nearest neighbor discovery, leader node selection, and optimal distribution tree organization. However, today`s Internet does not provide such information explicitly and application developers often resort to adhoc measurement tools to obtain the necessary data. This poses an additional tax on the development cost of new services and applications. In order to estimate or predict end-to-end delay accurately, a number of systems have been proposed and implemented. And these systems attempt to provide a shared measurement infrastructure for distributed applications. Though diverse in underlying mechanisms, these systems have the common goal of providing network-internal characteristics to applications, and their measurements overlap (or even wasted) significantly. Moreover, running these systems over a long period of time requires a significant effort. Not many of the proposed systems are running as of today. Longitudinal studies of the network performance are important to network operators and researchers and bring insights not available from one-time analysis.
In view of the large variety of proposed (and already deployed) measurement systems, in this dissertation we opted for an alternative approach, measurement reuse, for the Internet path and delay performance estimation. We believe that it is about time that we look into the possibility of taking the most out of existing measurements and their infrastructures, instead of building yet another measurement system. Instead of performing measurements ourselves and generating active probes, we venture out to do no additional measurements on our own (other than for evaluation). We explore how we can extend the lifetime and utility of existing measurements and make them suitable for longitudinal studies that were not in the original intent of the measurement project.
In this dissertation we present a algorithm to combine existing data sets efficiently and produce accurate estimates of the path and delay between any pair of Internet hosts. Taking existing delay measurements as input, our algorithm can return path and delay estimates for those points not covered in the input measurements. Two data sets we consider are: end-to-end delay and path measurements and BGP (Border Gateway Protocol) routing tables. The key idea is to use path and delay measurements (given in the traceroute outputs) data segmented by the AS and produces an composite estimate based on the inferred AS path between any two hosts in the Internet. As the algorithm stitch up path segments using BGP routing information, fittingly, we call our algorithm path stitching.
Path-stitching algorithm builds upon several fundamental Internet measurement techniques, such as traceroute, IP-to-AS mapping, and AS-level path inference. In every step of our algorithm, we face many sources of error. We illustrate challenges in dealing with those errors, and present a few heuristics to address them. They are not confined to our work, but apply to any other systems that use the same empirical data.
Among the proposed systems, we demonstrate that path stitching is unique in that it needs no additional on-the-spot active measurements and allows reuse of any hop-by-hop delay and path measurement. Since we do not need any additional active measurement for path stitching, we can apply path-stitching to any measurement, past or present, and reconstruct end-to-end path and delay.
In order to demonstrate that our algorithm is a powerful and versatile tool for a wide range of applications in the Internet, we presented three real applications of path stitching; we systematically reconstruct the past, present, and future of Internet path and delay.
We begin with a evaluation of path-stitching algorithm. We evaluate how estimates from our path stitching fare in comparison to {on-the-spot} delay measurements. Despite many sources of error in the algorithm, its delay estimates are close enough to live measurements: 80% of pairs have absolute errors less than 20 msec, and the median absolute error is less than 5 msec. Even without additional on-the-spot active measurements, its estimates are still similar or better than known methods with extensive new data collection campaigns. Path stitching represents a reference baseline valuable when it comes to understand the benefits (and the costs) of deploying a new measurement infrastructure.
Then we reconstruct the past history of the Internet path and delay using archival traceroute data and routing information. The six years of the reconstructed history of the delay distribution between random pairs of /24 prefixes demonstrates how the overall Internet delay performance has evolved over time. Our work is the first ever systematic approach to Internet delay distribution. In the six-year longitudinal study of the Internet-wide delay distribution from 2004 to 2009, we report that overall delay distribution has gotten worse from 2004 to 2009, while the delay distribution for the same set of host pairs remains almost identical or slightly improved. IP and AS hop counts have decreased end-to-end. We also have observed that delays over individual paths have fluctuated over time. The findings are illuminating and conform to our expectations. Our study of Internet delay distribution evolution does not focus on individual microscopic behaviors, but is more of a macroscopic summary of the evolution trend, yet accounting for all the microscopic changes.
Finally, we construct and answer what-if scenarios of AS path changes on end-to-end delay performance. Such information helps Internet service providers and customers to make informed decisions on their future traffic engineering policies, such as peering changes or service provider selections.
Our reconstruction of the past, present, and future of Internet path and delay demonstrates that path stitching is a powerful and versatile tool for a wide range of applications. It also opens up a new direction in performance estimation that takes full advantage of structural properties of the Internet.
분산 네트워크 어플리케이션들이 늘어남에 따라 인터넷 상에서 임의 지점들 사이에 인터넷 전송 속도와 전송 경로를 추정하는 문제의 중요성이 점점 더 커지고 있다. 사용자들에게 더 나은 품질의 서비스를 제공하기 위해서는 네트워크 내부 상태와 성능에 대한 정확한 정보를 활용하도록 인터넷 서비스와 어플리케이션을 설계하는 것이 필수적이기 때문인데, 인터넷 전송 시간과 전송 경로 등의 네트워크 내부의 성능 정보를 활용하면 신속한 데이터 교환에 유리한 최단 거리에 있는 이웃 노드의 검색, 대표 노드 선출, 멀티미디어 데이터 분산을 위한 최적 경로 구축 등과 같이 분산 네트워크 어플리케이션에서 흔히 마주하게 되는 문제들을 효율적으로 해결할 수 있다. 하지만 인터넷은 내부의 성능 정보를 직접 외부로 공개 하도록 설계되지 않았기 때문에 어플리케이션 개발자들은 필요한 성능 정보를 수집하기 위해 저마다의 실측 도구와 시설을 직접 구축하여 사용해야만 했다. 이렇게 인터넷 실측 작업에 들어가는 노력은 새로운 서비스나 어플리케이션을 개발하는 과정과는 별개로 추가적인 많은 비용과 장애를 발생케 하는 요인이 되었고 때문에 인터넷 서비스나 어플리케이션들 간에 공유하여 사용할 수 있도록 인터넷 전송 속도에 대한 추정치를 대신 계산하여 제공하는 많은 시스템들이 고안되었다.
본 논문에서는 이미 많은 수의 대규모 인터넷 성능 실측 시스템들이 독자적으로 구축되고 운용되고 있음에 착안하여, 이들이 제각기 수집하고 있는 데이터를 한데 모아 재사용하는 새로운 형태의 인터넷 전송 시간과 전송 경로 추정 방법론을 제안한다. 많은 수의 대규모 인터넷 성능 실측 시스템들이 제안되고 운용되어 왔으나 어떠한 실측 시스템도 인터넷 전역에 대한 성능 실측 데이터를 제공하지는 못했다. 인터넷의 모든 서브넷이나 AS 간에 실측 데이터를 수집하는 시설을 구현하여 인터넷 상에 실제로 배치 하는 것이 현실적으로 불가능하기 때문이다. 또한 이들 시스템은 서로 간에 데이터 공유나 교환을 염두에 두지 않고 매우 유사한 형태의 인터넷 성능 실측 작업을 저마다 독자적으로 수행하고 있기 때문에 네트워크 자원을 중복해서 낭비하고 있으며 수집하는 데이터도 또한 상당 부분이 겹치고 있다. 또한 대규모 시스템을 오랜 시간에 걸쳐 운용하는 데는 매우 많은 노력과 비용이 필요하기 때문에 그동안 고안된 실측 시스템들 중에서도 극소수 만이 오늘날까지 지속적으로 운용되고 있다. 이러한 관점에서 실측 데이터를 재사용하는 것은 인터넷 전역을 아우를 수 있으면서도 장기간에 걸쳐 지속적으로 운용가능한 인터넷 성능 정보 실측 및 추정 시스템의 설계에 매우 적합하다. 본 논문에서는 또 다른 대규모 성능 실측 시스템을 고안하며 운용함으로써 인터넷 자원을 낭비하는 대신, 추가적인 인터넷 실측 작업 없이도 다른 시스템들에 의해 이미 수집된 실측 데이터만을 재사용하여 인터넷 상의 임의의 지점들 사이에 인터넷 전송 시간과 전송 경로를 정확히 추정하는 방법론을 제안한다.
본 논문에서는 다른 시스템들에 의해 서로 다른 목적을 가지고 수집된 성능 실측 데이터들을 한데 모아 재사용한다. 본 논문에서 사용하는 데이터는 두 가지 유형으로, 첫째는 종단간 인터넷 전송 시간 및 경로 실측 데이터이고 둘째는 BGP (Border Gateway Protocol) 라우팅 정보이다. 이들 두 유형의 데이터는 각각 traceroute 메커니즘과 BGP 라우팅 테이블의 형태로 인터넷 상에서 오랜 세월 동안 수집되어온 가장 기본적인 형태의 성능 실측 데이터라 할 수 있다. 본 논문에서 고안한 방법론은 입력 데이터에 존재하는 호스트들 간에 성능 정보를 제공함은 물론 존재하지 않는 호스트들 간에도 인터넷 전송 시간과 경로를 추정한다. 핵심 아이디어는 traceroute 메커니즘의 결과물로 주어지는 종단간 인터넷 전송 시간 및 경로 실측 데이터를 AS 단위의 경로 세그먼트(Path Segment)들로 분할하여 저장하는 것이다. 임의의 두 지점 사이에 성능 정보를 추정하기 위해서는 이 두 지점 사이에 AS 경로를 먼저 예측하고 이 예측된 AS 경로에 해당하는 경로 세그먼트들을 검색해 재결합한다. 분할된 경로 세그먼트들을 BGP 라우팅 정보에 따라 재조합하고 연결하여 (Stitch-up) 사용한다는데 착안하여 이 방법론을 패스 스티칭(Path Stitching)이라 명명하였다.
패스 스티칭 기법은 traceroute 메커니즘, 인터넷 주소와 AS의 대응 관계, AS 경로 예측 등, 핵심적인 인터넷 실측 기법들에 기초하고 있으며, 이들 기법들을 결합하여 사용하는 과정에서 많은 오류가 발생할 소지가 있다. 본 논문에서는 이들 기법들을 인터넷 실측 연구에서 실제 적용하여 활용할 때 발생하는 여러 문제점들을 상세히 지적하고 이들 문제점을 해결하기 위한 휴리스틱 기법들을 제안한다. 이러한 휴리스틱 기법들은 비단 본 연구에만 국한되지 않으며 같은 종류의 실측 데이터를 활용하는 다른 연구나 시스템들에도 공통적으로 적용될 수 있는 부분이다.
기존에 제안된 인터넷 전송 시간 실측 및 추정 시스템들이 정확한 추정값을 도출하기 위해서 저마다 독자적인 형태의 실측 데이터 수집을 즉석에서 추가로 필요로 하는데 반해, 패스 스티칭은 모든 종류의 종단간 인터넷 전송 시간 및 경로 실측 데이터를 있는 그대로 재사용할 수 있고 전송 시간 및 전송 경로 추정을 위해 필요한 추가적인 실측 작업이 전혀 없다는 데서 분명한 독자성을 지닌다. 즉석에서 추가로 수집해야할 실측 데이터가 전혀 없다는 장점 덕분에 우리는 패스 스티칭 방법론을 현재 수집되고 있는 실측 데이터에 적용해 사용함은 물론 과거를 포함한 모든 시점에서 수집된 실측 데이터들에도 그대로 적용하여 인터넷 전송 시간과 전송 경로를 정확히 추정할 수 있다. 본 논문에서는 인터넷의 과거, 현재, 그리고 미래의 전송 시간과 전송 경로를 패스 스티칭을 이용해 재구성하고 추정함으로써 패스 스티칭 방법론이 다양한 인터넷 어플리케이션에서 폭 넓게 적용해 사용될 수 있는 강력하고 다재다능한 도구임을 본인다.
첫째로 현재 인터넷 상에서 임의로 주어진 두 지점에 대해 패스 스티치이 얼마나 정확하게 인터넷 전송 시간과 전송 경로를 추정할 수 있는지 평가했다. 이는 패스 스티칭의 추정값이 실제 측정한 값을 대신해 사용될 수 있을 정도로 충분히 정확한지 분석하기 위함인데, 실험 결과 패스 스티칭의 추정값은 실측값에 매우 근접함을 볼 수 있었다. 80%의 인터넷 호스트 페어에 대해 절대 오차가 20 msec 이하이며, 추정 오차의 중간값은 5 msec 이하이다. 추가적인 실측 데이터의 수집 없이도 패스 스티칭의 추정값은 정확한 추정을 위해 독자적인 형태의 실측 데이터 수집을 즉석에서 추가로 필요한 다른 방법론과 유사하거나 오히려 더 나은 성능을 보였다. 둘째로 우리는 패스 스티칭 기법을 인터넷 호스트 페어의 임의 추출법(Random Sampling)과 함께 과거 10 년 간에 걸쳐 수집된 실측 데이터에 적용함으로써 패스 스티칭이 지난 10년간 인터넷 전송 시간과 전송 경로가 진화해온 역사를 조사하고 분석하는 데 유용함을 보였다. 기존에 제시된 인터넷 전송 시간 분포에 대한 연구가 인터넷의 일부 지역 만을 고려한 소규모 실측 결과였다면 본 어플리케이션은 인터넷 상에서 모든 호스트들 간의 연결 관계를 고려해 인터넷 전역의 전송 시간 분포를 최초로 계산하고 분석한 연구이다.
끝으로 우리는 인터넷 라우팅의 변화가 가져올 가까운 미래의 인터넷 성능 변화를 예측하기 위해 패스 스티칭이 어떻게 사용될 수 있는지 실험했다. 이를 위해 인터넷 라우팅을 임의로 조작하는 세 가지 가정 시나리오들을 구성하고 이에 패스 스티칭을 적용함으로써 AS 경로의 변화가 가까운 미래의 종단간 인터넷 전송 성능에 미치게 되는 영향을 예측 했다. 인터넷 사업자는 인터넷 회선 변경 및 증설이나 라우터 설정 변경, 또는 다른 인터넷 사업자들과의 트래픽 전송 계약 변경 등을 통해 고객에게 제공하는 인터넷 성능을 최대화하려 하지만 이러한 직접적인 설정 변경은 잘못된 선택을 하게 될 경우 예기치 못한 장기간의 인터넷 접속 장애나 인터넷 성능 저화와 같이 심각한 문제를 초래하게 된다. 패스 스티칭을 사용함으로써 별도의 장비 설치나 라우터 설정 변경 혹은 인터넷 사업자 간 계약 변경의 위험 부담 없이도 설정 적용 후의 인터넷 전송 경로와 전송 시간 품질이 어떻게 변화하는지 효과적으로 예측할 수 있음을 보일 수 있었다.
