1. INTRODUCTION
The Internet consists of thousands of independent interconnected organizations, each driven by their own business
model and needs. The interplay of these needs influences,
and sometimes determines, topology and traffic patterns,i.e., connectivity between networked organizations and routing across the resulting mesh. Understanding the underlying
business relationships between networked organizations provides the strongest foundation for understanding many other
aspects of Internet structure, dynamics, and evolution.
Business relationships between ASes, which are typically
congruent with their routing relationships, can be broadly
classified into two types: customer-to-provider (c2p) and
peer-to-peer (p2p). In a c2p relationship, the customer pays
the provider for traffic sent between the two ASes. In return,
the customer gains access to the ASes the provider can reach,
including those which the provider reaches through its own
providers. In a p2p relationship, the peering ASes gain access to each others’ customers, typically without either AS
paying the other. Peering ASes have a financial incentive
to engage in a settlement-free peering relationship if they
would otherwise pay a provider to carry their traffic, and
neither AS could convince the other to become a customer.
Relationships are typically confidential so must be inferred
from data that is available publicly. This paper presents a
new approach to inferring relationships between ASes using
publicly available BGP data.
Measurement and analysis of Internet AS topologies has
been an active area of research for over a decade. While
yielding insights into the structure and evolution of the topology, this line of research is constrained by systematic measurement and inference challenges [32], many of which our
approach proactively addresses. First, the BGP-based collection infrastructure used to obtain AS-level topology data
suffers from artifacts induced by misconfigurations, poisoned
paths, and route leaks, all of which impede AS-relationship
inference. Our algorithm incorporates steps to remove such
artifacts. Second, AS topologies constructed from BGP data
miss many peering links [6]. We show this lack of visibility
does not hinder the accuracy of inferences on the links we
do observe. Third, most AS-relationship algorithms rely on
“valley-free” AS paths, an embedded assumption about the
rationality of routing decisions that is not always valid [32],
and which our algorithm does not make. Fourth, import
and export filters can be complicated; some operators caveat
their c2p links as being region or prefix specific. However,
they still describe themselves as customers even if they do
not receive full transit. Therefore, we make a c2p inference
when any transit is observed between two ASes. We argue
that relationship inferences can still be c2p or p2p with the
caveat that the c2p relationship may be partial. We develop
techniques to mitigate the effects of such hybrid relationships
when computing an AS’s customer cone, described later in
this section. Finally, a single organization may own and
operate multiple ASes; we leave the inference of sibling relationships as future work because it is difficult to distinguish
them from route leaks. We make the following contributions:
We introduce a new algorithm for inferring c2p
and p2p links using BGP data. Our algorithm builds on
three generally accepted assumptions about industry structure: (1) there is a clique of large transit providers at the
top of the hierarchy; (2) most customers enter into a transit agreement to be globally reachable; and (3) cycles of
c2p links (e.g., where ASes A, B, and C are inferred to be
customers of B, C, and A respectively) should not exist for
routing to converge [19]. Our algorithm achieves near-perfect
accuracy for both p2p and p2c links for the subset of relationships we were able to validate, using the largest set of
externally gathered AS relationship validation data collected
to date. Since even our three different sources of validation
data disagree by 1%, our algorithm reaches the limit of accuracy achievable with available data.
We evaluate our algorithm’s accuracy by validating 43,613 (34.6%) of our inferences – the largest validation of AS-relationships performed to date. First,
we received nearly 2400 directly reported relationship assertions from operators through the interactive feedback functionality of our public repository of AS relationships [1].
Second, we use policy information encoded in the RIPE
WHOIS database to extract more than 6,500 unique relationships; we extract only relationships between ASes where
both ASes have policies recorded in the database and both
policies are expressed consistently. Third, we extract more
than 41,000 relationships using community strings encoded
in BGP messages by ASes who publish how these strings
map to AS relationships. Our validation data, 97% of which
we can share (we cannot share directly reported relationships) will itself contribute to a research area that has long
suffered from lack of validation.
We introduce a new algorithm for inferring the
customer cone of an AS. The customer cone of AS X is
defined as the set of ASes that X can reach using p2c links;
for AS X the customer cone includes X’s customers, as well
as X’s customers’ customers, and so on. The customer cone
is not a methodologically clean construct, since some ASes
have hybrid relationships; for example, they peer in some
regions (or some prefixes), but one AS will purchase from
the other for other regions (or other prefixes). We compare
the strengths and weaknesses of three distinct approaches
for computing customer cones, and explain why we believe
one approach is more accurate. We also show how this construct informs our understanding of evolutionary trends such
as the flattening of the Internet topology and the financial
consolidation of the Internet transit industry.
1. 소개
인터넷은 수천 개의 독립적인 상호 연결된 조직으로 구성되어 있으며, 각 조직은 각자의 비즈니스 모델과 필요에 따라
수천 개의 독립적인 상호 연결된 조직으로 구성되어 있습니다. 이러한 요구의 상호 작용은 토폴로지 및 트래픽 패턴에 영향을 미치고,
토폴로지 및 트래픽 패턴, 즉 네트워크로 연결된 조직 간의 연결과 그 결과 메시를 통한 라우팅에 영향을 미치고 때로는 결정하기도 합니다. 네트워크로 연결된 조직 간의 근본적인
네트워크에 연결된 조직 간의 비즈니스 관계를 이해하는 것은 인터넷 구조, 역학 관계의 다른 많은 측면을
다른 많은 측면을 이해하는 데 가장 강력한 토대가 됩니다.
AS 간의 비즈니스 관계는 일반적으로
라우팅 관계와 일치하는 AS 간의 비즈니스 관계는 크게
두 가지 유형으로 분류할 수 있습니다: 고객-공급자(c2p)와
P2P(피어 투 피어). c2p 관계에서 고객은 두 서비스 제공자 간에 전송된 트래픽에 대해
공급자에게 지불합니다. 그 대가로
고객은 공급자가 도달할 수 있는 모든 AS에 대한 액세스 권한을 얻습니다,
공급자가 자체 제공자를 통해 도달하는 AS를 포함하여
제공자. P2P 관계에서 피어링 AS는 일반적으로 어느 한 쪽이 다른 쪽에 비용을 지불하지 않고도 서로의 고객에 대한 액세스 권한을 얻습니다.
지불하지 않고도 서로의 고객에 액세스할 수 있습니다. 피어링 AS에는 재정적 인센티브가 있습니다.
정산 없는 피어링 관계에 참여할 재정적 인센티브가 있습니다.
트래픽을 전송하기 위해 제공업체에 비용을 지불하고
어느 AS도 상대방을 고객이 되라고 설득할 수 없습니다.
관계는 일반적으로 기밀이므로 공개적으로 이용 가능한 데이터를 통해
추론해야 합니다. 이 백서에서는
공개적으로 사용 가능한 BGP 데이터를 사용하여
새로운 접근법을 제시합니다.
인터넷 AS 토폴로지의 측정과 분석은
지난 10년 이상 활발하게 연구되어 온 분야입니다. 그동안
토폴로지의 구조와 진화에 대한 인사이트를 얻을 수 있지만, 이러한 연구 분야는 체계적인 측정 및 추론 문제[32]로 인해 제약을 받아왔으며, 이러한 문제 중 많은 부분을 우리의
접근 방식이 선제적으로 해결합니다. 첫째, AS 수준의 토폴로지 데이터를 얻는 데 사용되는 BGP 기반 수집 인프라는
잘못된 구성으로 인한 아티팩트, 오염된 경로, 경로 누수
경로 및 경로 유출로 인한 아티팩트가 발생하며, 이 모든 것이 AS 관계 추론을
추론을 방해합니다. 저희 알고리즘에는 이러한 아티팩트를 제거하는 단계가 포함되어 있습니다.
아티팩트를 제거합니다. 둘째, BGP 데이터로 구축된 AS 토폴로지는
많은 피어링 링크를 놓칩니다[6]. 이러한 가시성 부족은
우리가 관찰하는 링크에 대한 추론의 정확성을 방해하지 않습니다.
정확성을 저해하지 않습니다. 셋째, 대부분의 AS 관계 알고리즘은 다음과 같이
"밸리가 없는" AS 경로에 의존합니다.
라우팅 결정의 합리성에 대한 가정이 항상 유효한 것은 아닙니다 [32],
그리고 우리의 알고리즘은 만들지 않습니다. 넷째, 가져오기
및 내보내기 필터는 복잡할 수 있으며, 일부 운영자는 다음과 같이 주의합니다.
지역이나 접두사에 따라 C2P 링크가 달라질 수 있습니다. 하지만
전체 전송을 수신하지 않더라도
고객이라고 설명합니다. 따라서 크리테오는 두 지역 간 이동이 관찰될 때
를 추론합니다. 우리는 다음과 같이 주장합니다.
관계 추론은 여전히 c2p 또는 p2p가 될 수 있습니다.
c2p 관계가 부분적일 수 있다는 점을 주의하세요. 저희는
이러한 하이브리드 관계의 영향을 완화하는 기술을 개발했습니다.
이러한 하이브리드 관계의 영향을 완화하는 기술을 개발했습니다.
이 섹션에서 설명합니다. 마지막으로, 단일 조직이 여러 AS를 소유하고
여러 개의 AS를 운영할 수 있습니다. 형제자매 관계의 추론은 경로 유출과 구별하기 어렵기 때문에 향후 작업으로 남겨둡니다.
향후 작업으로 남겨둡니다. 저희는 다음과 같이 기여합니다:
BGP를 사용하여 c2p와 P2P 링크를 추론하는 새로운 알고리즘 도입
및 P2P 링크를 추론하는 새로운 알고리즘을 도입합니다. 저희 알고리즘은 다음을 기반으로 합니다.
업계 구조에 대해 일반적으로 받아들여지는 세 가지 가정: (1) 계층 구조의 최상단에 대형 대중교통 제공업체가 존재한다.
계층 구조의 최상위; (2) 대부분의 고객이 전 세계적으로 도달할 수 있도록 환승 계약을 체결하며; (3) 다음과 같은 주기
c2p 링크(예: AS A, B, C가 다음과 같이 추론되는 경우)
각각 B, C 및 A의 고객)이 존재해서는 안됩니다.
수렴하는 라우팅 [19]. 저희 알고리즘은 P2P와 P2P 모두에서 완벽에 가까운
외부에서 수집한 가장 큰 집합을 사용하여 검증할 수 있었던 관계의 하위 집합에 대해 P2P 및 P2P 링크 모두에 대한 정확도
외부에서 수집한 AS 관계 검증 데이터를 사용하여
사용하여 검증할 수 있었습니다. 세 가지 다른 검증 소스조차도
데이터조차 1%의 불일치를 보이기 때문에, 저희 알고리즘은 사용 가능한 데이터로 달성할 수 있는 정확도의 한계에 도달했습니다.
현재까지 수행한 AS 관계 검증 중 가장 많은 43,613건(34.6%)의 추론을 검증하여 알고리즘의 정확도를 평가했습니다. 먼저,
AS 관계에 대한 공개 리포지토리의 대화형 피드백 기능을 통해 운영자로부터 약 2400건의 관계 어설션을 직접 보고받았습니다[1].
둘째, RIPE 데이터베이스에 인코딩된 정책 정보를 사용하여
6,500개 이상의 고유한 관계를 추출하기 위해 다음과 같은 경우에만 AS 간의 관계를 추출합니다.
두 AS에 모두 정책이 데이터베이스에 기록되어 있고
정책이 일관되게 표현된 AS 간의 관계만 추출합니다. 셋째, 커뮤니티 스트링을 사용하여
커뮤니티 문자열을 사용하여 41,000개 이상의 관계를 추출합니다.
커뮤니티 문자열을 사용하여 41,000개 이상의 관계를 추출합니다.
관계를 추출합니다. 저희의 검증 데이터 중 97%는
공유할 수 있습니다(직접 보고된 r