4. RELATIONSHIP INFERENCE
Our algorithm uses two metrics of AS connectivity: the
node degree is the number of neighbors an AS has; and the
transit degree is the number of unique neighbors that appear
on either side of an AS in adjacent links. Figure 4 illustrates
the transit degree metric; ASes with a transit degree of zero
are stub ASes. We use transit degree to initially sort ASes
into the order in which we infer their relationships, breaking
ties using node degree and then AS number. ASes inferred to
be in the clique are always placed at the top of this rank order. Sorting by transit degree reduces ordering errors caused
by stub networks with a large peering visibility, i.e., stubs
that provide a VP or peer with many VPs.
4.1 Assumptions
We make three assumptions based on discussions with operators and generally understood industry structure.
Clique: multiple large transit providers form a peering
mesh so that customers (and indirect customers) of a transit provider can obtain global connectivity without multiple
transit provider relationships.
A provider will announce customer routes to its
providers. All ASes, except for those in the clique, require
a transit provider in order to obtain global connectivity. We
assume that when X becomes a customer of Y, that Y announces paths to X to its providers, or to its peers if Y
is a clique AS. Exceptions to this rule include backup and
region-specific transit relationships.
The AS topology can be represented in a directed
acyclic graph. Gao et al. argue there should be no cycle
of p2c links to enable routing convergence [19].
4.2 Overview
Algorithm 1 shows each high-level step in our AS relationship inference algorithm. First, we sanitize the input data
by removing paths with artifacts, i.e., loops, reserved ASes,
and IXPs (step 1). We use the resulting AS paths to compute the node and transit degrees of each AS, and produce
an initial rank order (step 2). We then infer the clique of
ASes at the top of the hierarchy (step 3). After filtering
out poisoned paths (step 4), we apply heuristics to identify
c2p links (steps 5-10). Finally, we classify all remaining unclassified links as p2p. Our algorithm contains many steps,
a consequence of trying to capture the complexity of the
real-world Internet and mitigate limitations of public BGP
data [32]. The output from this process is a list of p2c and
p2p relationships with no p2c cycles, by construction4.3 Filtering and Sanitizing AS Paths
We first sanitize the BGP paths used as input to our algorithm, especially to mitigate the effects of BGP path poisoning, where an AS inserts other ASes into a path to prevent
its selection. A poisoned path implies a link (and thus relationship) between two ASes, where in reality neither may
exist. We infer poisoning, or the potential for a poisoned
path, in AS paths (1) with loops, or (2) where clique ASes
are separated. We filter out paths with AS loops, i.e., where
an ASN appears more than once and is separated by at least
one other ASN. Such paths are an indication of poisoning,
where an AS X prevents a path from being selected by a
non-adjacent upstream AS Y by announcing the path “X Y
X” to provider Z, so if the route is subsequently received by
Y it will be discarded when the BGP process examines the
path for loops [24]. For BGP paths recorded in April 2012,
0.11% match this rule. After we have inferred the clique
in step 3, we also discard AS paths where any two ASes in
the clique are separated by an AS that is not in the clique.
This condition indicates poisoning, since a clique AS is by
definition a transit-free network. For BGP paths recorded
in April 2012, 0.03% match this rule.
We also filter out paths containing unassigned ASes; in
BGP paths from April 2012, we observed 238 unassigned
ASes in 0.10% of unique paths. 222 of these ASes are reserved for private use and should not be observed in paths
received by route collectors. In particular AS23456, reserved
to enable BGP compatibility between ASes that can process
32-bit ASNs and those that cannot [35], is prevalent in earlier public BGP data and can hinder relationship inferences.
We also remove ASes used to operate IXP route servers
because the relationships are between the participants at the
exchange. Unfortunately we know of no public database of
IXP route server ASes, nor do we know of any algorithm
that reliably identifies an IXP route server. To identify IXP
route server ASes, we manually searched for IXP ASes using
a combination of routing and WHOIS data: if the name of
the AS in WHOIS contains RS or IX, we include the AS
in our list if the AS announces less address space than a
/23. This process yielded a list of 25 ASes known to operate
route servers; we remove these ASes from paths so that the
IX participants are adjacent in the BGP path.Finally, we discarded all paths from 167.142.3.6 for May
and June 2003, and from 198.32.132.97 between March and
November 2012; the former reported paths with ASes removed from the middle of the path, and the latter reported
paths inferred from traceroute.
4.4 Inferring Clique
We attempt to infer the ASes present at the top of the
hierarchy. Since Tier-1 status is a financial circumstance,
reflecting lack of settlement payments, we focus on identifying transit-free rather than Tier-1 ASes. First, we use the
Bron/Kerbosch algorithm [10] to find the maximal clique C1
from the AS-links involving the largest ten ASes by transit
degree.1 Second, we test every other AS in order by transit
degree to complete the clique. AS Z is added to C1 if it has
links with every other AS in C1 and it does not appear to
receive transit from another member of C1; i.e. no AS path
should have three consecutive clique ASes. Because AS path
poisoning may induce three consecutive clique ASes in a false
BGP path “X Y Z”, we add AS Z to C1 provided there are no
more than five ASes downstream from “X Y Z”. A nominal
value of five ASes will still capture clique ASes even in paths
poisoned multiple times, yet is unlikely to wrongly place a
large transit customer in the clique since a clique AS is likely
to announce (and we are likely to observe [28]) more than
five customers of large transit customers. If an AS would be
admitted to C1 except for a single missing link, we add that
AS to C2. Finally, because an AS might be in C1 but not in
the clique, we re-use the Bron/Kerbosch algorithm to find
the largest clique (by transit degree sum) from the AS-links
involving ASes in C1 and C2. The product of this step is a
clique of transit-free ASes.
Figure 5 shows ASes inferred to be in the clique since January 2002. Nine ASes have been in the clique nearly every
month, and ASes that are inferred to be in the clique arealmost continuously present. The consistency of the inferred
clique and our discussions with operators give us confidence
in our clique inference methodology. However, peering disputes and mergers of ASes can disrupt our inference of the
clique. ASes may form alliances to prevent de-peering incidents from partitioning their customers from the Internet. If
such a disconnection incident triggers activation of a backup
transit relationship, a peer will disappear from the clique
and instead be inferred as a customer of the allied peer. The
process of merging ASes can can also result in peers being
inferred as customers. For example, in 2013 Level3 (AS3356)
gradually shut down BGP sessions established with Global
Crossing (AS3549), shifting sessions to AS3356. In order
to maintain global connectivity during this merger process,
Level3 advertised customers connected to AS3549 to peers
that were only connected to AS3356. As a result, ASes in
the clique appeared to be customers of AS3356, when in reality they were peers. Specifically, in figure 5, AS6461 was
not inferred to be a member of the clique because it had
shifted all peering ports with Level3 to AS3356.
4.5 Inferring Providers, Customers, and Peers
The remainder of the algorithm infers p2c and p2p relationships for all links in the graph. Step 3 infers p2p relationships for the full mesh of links between clique ASes. The
rest of this section uses figure 6 as reference.
AS path triplets: We make inferences using only AS
path triplets (adjacent pairs of links). Triplets provide the
constraints necessary to infer c2p relationships while allowing us to ignore non-hierarchical segments of paths, and are
more computationally efficient than paths. For example, in
figure 6 we break path 1 into two triplets: “1239 3356 9002”
and “3356 9002 6846”.
Notation: We use the notation in table 1 to describe relationships between ASes. A p2c relationship between X and
Y is presented as “X > Y”. The notation reflects providers
as typically greater (in degree or size or tier of a traditional
hierarchical path) than their customers. A triplet with no
inferred relationships is presented as “X ? Y ? Z”.
4. 관계 추론
저희 알고리즘은 AS 연결성에 대한 두 가지 메트릭을 사용합니다.
노드 정도는 AS가 가지고 있는 이웃의 수입니다.
트랜짓 정도는 인접한 링크에서 AS의 양쪽에 나타나는
고유한 이웃의 수입니다. 그림 4는
트랜짓 정도 메트릭을 보여줍니다. 트랜짓 정도가 0인 AS는
는 스텁 AS입니다. 트랜짓 정도를 사용하여 처음에 AS를 정렬합니다.
를 관계를 추론하는 순서대로 정렬하고, 노드 정도를 사용하여 연결을 끊은 다음
노드 정도와 AS 번호를 사용하여 연결을 끊습니다. 클러스터에 있는 것으로 추론된
로 추론된 AS는 항상 이 순위 순서에서 맨 위에 배치됩니다. 경유도를 기준으로 정렬하면 피크가 큰 스텁 네트워크에서 발생하는 순서 오류가
피어링 가시성이 큰 스텁 네트워크, 즉 VP 또는 피어를 제공하는 스텁으로 인한
가 많은 피어링으로 인해 발생하는 순서 오류를 줄여줍니다.
4.1 가정
저희는 운영자와의 논의와 일반적으로 이해되는 업계 구조를 바탕으로 세 가지 가정을 세웠습니다.
파벌: 다수의 대형 대중교통 제공업체가 피어링 메시를 형성하여
메시를 형성하여 한 운송업체의 고객(및 간접 고객)이 여러 운송업체 관계 없이도 글로벌 연결성을 확보할 수 있습니다.
글로벌 연결을 얻을 수 있습니다.
제공업체는 고객 경로를 다른 제공업체에 알립니다.
제공자를 발표합니다. 파벌에 속한 AS를 제외한 모든 AS는 다음을 요구합니다.
글로벌 연결을 얻으려면 경유 제공자가 필요합니다. 우리는
X가 Y의 고객이 되면, Y는 자신의 프로바이더에게, 또는 Y가 클릭 AS인 경우 자신의 피어에게 X로 가는 경로를 발표한다고 가정합니다.
가 클릭 AS인 경우 경로를 발표한다고 가정합니다. 이 규칙의 예외에는 백업 및
지역별 트랜짓 관계.
AS 토폴로지는 방향이 지정된
비순환 그래프로 나타낼 수 있습니다. Gao 등은 라우팅을 가능하게 하는 P2P 링크의 순환이
순환이 없어야 한다고 주장합니다[19].
4.2 개요
알고리즘 1은 AS 관계 추론 알고리즘의 각 상위 단계를 보여줍니다. 먼저, 입력 데이터를 정제합니다.
아티팩트가 있는 경로, 즉 루프, 예약된 AS,
및 IXP를 제거하여 입력 데이터를 정제합니다(1단계). 결과 AS 경로를 사용하여 각 AS의 노드 및 경유도를 계산하고, 다음과 같은 초기 순위 순서를 생성합니다.
초기 순위 순서를 생성합니다(2단계). 그런 다음 다음과 같은 파벌을 추론합니다.
AS의 클러스터를 추론합니다(3단계). 필터링 후
필터링한 후(4단계), 휴리스틱을 적용해서
C2P 링크를 식별합니다(5-10단계). 마지막으로, 분류되지 않은 나머지 모든 링크를 P2P로 분류합니다. 저희 알고리즘에는 많은 단계가 포함되어 있습니다,
실제 인터넷의 복잡성을 포착하고 한계를 완화하기 위해
실제 인터넷의 복잡성을 포착하고 공용 BGP의 한계를 완화하기 위한 결과입니다.
데이터 [32]. 이 프로세스의 출력은 P2P 관계 목록입니다.
p2c 주기가 없는 P2P 관계의 목록입니다.4.3 AS 경로 필터링 및 위생 처리
먼저 알고리즘의 입력으로 사용되는 BGP 경로를 살균합니다. 특히, 한 AS가 다른 AS를 경로에 삽입하는 BGP 경로 중독의 영향을 완화하기 위해
경로에 삽입하는 것을 방지합니다. 포이즈닝된 경로는 실제로는 존재하지 않을 수 있는 두 AS 간의 링크(따라서 관계)를 의미합니다.
존재하지 않을 수 있습니다. 포이즌 경로를 추론하는 방법 또는 포이즌 경로의 가능성
경로, (1) 루프가 있는 AS 경로 또는 (2) 파벌 AS가 분리되어 있는 경우
가 분리되어 있습니다. AS 루프가 있는 경로, 즉 다음과 같은 경로를 필터링합니다.
ASN이 두 번 이상 나타나고 적어도
하나 이상의 다른 ASN. 이러한 경로는 중독의 징후입니다,
AS X가 인접하지 않은 업스트림 AS Y가
인접하지 않은 업스트림 AS Y가 경로를 선택하지 못하도록 하는 경우입니다.
X"를 공급자 Z에 알려서 나중에 경로를 수신하면
Y에 의해 경로가 수신되면 BGP 프로세스가 루프의 경로를 검사할 때
경로를 검사할 때 삭제됩니다 [24]. 2012년 4월에 기록된 BGP 경로의 경우,
0.11%가 이 규칙과 일치합니다. 3단계에서 파벌을 추론한 후
를 추론한 후, 3단계에서는 클러스터 내의 두 AS가
파벌에 속하지 않은 AS로 분리된 AS 경로도 삭제합니다.
이 조건은 포이즌을 나타냅니다. 왜냐하면 클리크 AS는 정의상
경유가 없는 네트워크이기 때문입니다. 2012년 4월에 기록된 BGP 경로의 경우
의 경우 0.03%가 이 규칙과 일치합니다.
또한 할당되지 않은 AS를 포함하는 경로도 필터링합니다.
2012년 4월의 BGP 경로에서 238개의 미할당 AS가 관찰되었습니다.
0.10%의 고유 경로에서 238개의 미할당 AS를 관찰했습니다. 이 중 222개의 AS는 개인용으로 예약되어 있으며 경로 수집기가 수신하는 경로에서 관찰되어서는 안 됩니다.
경로에서 관찰되어서는 안 됩니다. 특히 AS23456은 예약된
는 32비트 ASN을 처리할 수 있는 AS와
32비트 ASN을 처리할 수 있는 AS와 그렇지 않은 AS[35]간 호환성을 위해 예약된 AS23456은 이전의 공개 BGP 데이터에 널리 퍼져 있으며 관계 추론을 방해할 수 있습니다.
또한 IXP 라우트 서버를 운영하는 데 사용되는 AS를 제거합니다.
관계는 교환의 참여자 간의 관계이므로
교환. 안타깝게도 현재로서는
공개 데이터베이스가 없으며, IXP 라우팅 서버 AS를 안정적으로 식별하는
알고리즘도 알지 못합니다. IXP
라우팅과 WHOIS를 조합하여
라우팅과 WHOIS 데이터의 조합: WHOIS의 AS 이름에
이름에 RS 또는 IX가 포함된 경우, 해당 AS를 목록에 포함시킵니다.
를 목록에 포함시켰습니다.
/23. 이 프로세스를 통해 라우팅 서버를 운영하는 것으로 알려진 25개의 AS 목록이 생성되었습니다.
경로 서버를 운영하는 것으로 알려진 25개의 AS 목록이 생성되었으며, 이러한 AS를 경로에서 제거하여
마지막으로 2003년 5월과 6월의 167.142.3.6과 198.3.3.6의 모든 경로를 폐기했습니다.
2003년 5월과 6월, 그리고 2012년 3월과 11월 사이에 198.32.132.97에서
2012년 11월까지, 이전에 보고된 경로 중 AS가 제거된 경로를 삭제했습니다. 