2. RELATED WORK
Gao [18] was the first to study the inference of AS relationships. Her solution relies on the assumption that BGP paths
are hierarchical, or valley-free, i.e., each path consists of an
uphill segment of zero or more c2p or sibling links, zero or
one p2p links at the top of the path, followed by a downhill
segment of zero or more p2c or sibling links. The valley-free
assumption reflects the typical reality of commercial relationships in the Internet: if an AS were to announce routes
learned from a peer or provider to a peer or provider (creating a valley in the path), it would then be offering transit
for free. Gao’s algorithm thus tries to derive the maximum
number of valley-free paths, by selecting the largest-degree
AS in a path as the top, and assuming that ASes with similar degrees are likely to be peers (p2p). Gao validated her
results using information obtained from a single Tier-1 AS
(AT&T). Xia and Gao [36] proposed an improvement to
Gao’s algorithm that uses a set of ground truth relationships to seed the inference process. Transit relationships
are then inferred using the valley-free assumption. Gao’s
algorithm [18] is used for remaining unresolved links. They
validated 2,254 (6.3%) of their inferences using 80% of their
validation data and found their algorithm was accurate for
96.1% of p2c links and 89.33% of p2p links.
Subramanian et al. [34] formalized Gao’s heuristic into
the Type of Relationship (ToR) combinatorial optimization
problem: given a graph derived from a set of BGP paths,
assign the edge type (c2p or p2p, ignoring sibling relationships) to every edge such that the total number of valley-free
paths is maximized. They conjectured that the ToR problem is NP-complete and developed a heuristic-based solution (SARK) that ranks each AS based on how close to
the graph’s core it appears from multiple vantage points.
Broadly, as in Gao [18], ASes of similar rank are inferred to
have a p2p relationship, and the rest are inferred to have a
p2c relationship. Di Battista, Erlebach et al. [9] proved the
ToR problem formulation was NP-complete in the general
case and unable to infer p2p relationships. They reported
that it was possible to find a solution provided the AS paths
used are valley-free. They developed solutions to infer c2p
relationships, leaving p2p and sibling inference as open problems. Neither Subramanian et al. or Di Battista, Erlebach
et al. validated their inferences; rather, they determined the
fraction of valley-free paths formed using their inferences.
Dimitropoulos et al. [16] created a solution based on solving MAX-2-SAT. They inferred sibling relationships using
information encoded in WHOIS databases. Their algorithm
attempted to maximize two values: (1) the number of valleyfree paths, and (2) the number of c2p inferences where the
node degree of the provider is larger than the customer. The
algorithm uses a parameter α to weight these two objectives. They validated 3,724 AS relationships (86.2% were
c2p, 16.1% p2p, and 1.2% sibling) and found their algorithm
correctly inferred 96.5% of c2p links, 82.8% of p2p links,
and 90.3% of sibling links. Their validation covered 9.7% of
the public AS-level graph and has thus far been the most
validated algorithm. However, MAX-2-SAT is NP-hard and
their implementation does not complete in a practical length
of time for recent AS graphs.
UCLA’s Internet Research Laboratory produces AS-level
graphs of the Internet annotated with relationships [3]. The
method is described in papers by Zhang et al. [37] and
Oliveira et al. [29]. Their algorithm begins with a set of ASes
inferred to be in the Tier-1 clique, then infers links seen by
these ASes to be p2c; all other links are p2p. Zhang [37]
describes a method to infer the clique; Oliveira [29] assumes
the Tier-1 ASes are externally available, such as a list published by Wikipedia. There are a growing number of regionspecific c2p relationships visible only below the provider AS,
causing this approach to assign many p2p relationships that
are actually p2c. Gregori et al. [23] used a similar approach;
for each AS path, their algorithm identifies the relationships
possible and infers the actual relationship based on the lifetime of the paths. None of [23, 29, 37] describes validation.
The problematic lack of validation puts AS relationship inference research in a precarious scientific position. Nonetheless, research continues to build on the assumption that
meaningful AS relationship inference can be achieved and
applied to the study of the Internet, from deployment of security technologies [21], Internet topology mapping [6, 8, 12]
and evolution [13, 14], to industry complexity [17] and market concentration [15]. Due to the diversity in inter-domain
connectivity, relationship inferences do not (by themselves)
consistently predict paths actually taken by packets; such
predictive capabilities remain an open area of research [27].
Given its importance to the field of Internet research, we
revisited the science of AS relationship inference, with particular attention to validation. Our algorithm does not seek
to maximize the number of valley-free (hierarchical) paths,
since at least 1% of paths are non-hierarchical (section 3.6).
We make inferences using AS path triplets (adjacent pairs
of links) which allow us to ignore invalid segments of paths
that reduce the accuracy of valley-free path maximization
approaches. We also rely on two key assumptions: (1) an AS
enters into a c2p relationship to become globally reachable,
i.e. their routes are advertised to their provider’s providers,
and (2) there exists a clique of ASes at the top of the hierarchy that obtain full connectivity through a full mesh
of p2p relationships. We acquired external validation for
34.6% of the links in our AS graph, which was certainly a
challenge but not one as insurmountable as has been suggested (e.g. [9, 18, 23, 33, 34]).
2. 관련 연구
가오[18]는 AS 관계의 추론을 최초로 연구했습니다. 그의 솔루션은 BGP 경로가 계층적이라는 가정에 의존합니다.
계층적 또는 계곡이 없는, 즉 각 경로가 0 개 이상의 c2p 또는 형제 링크의
0개 이상의 P2P 또는 형제 링크의 오르막 구간, 0개 또는
하나의 P2P 링크가 경로 상단에 있고, 그 다음에는 내리막길
0 개 이상의 P2P 또는 형제 링크 세그먼트로 구성됩니다. 계곡이 없는
가정은 인터넷에서 상업적 관계의 일반적인 현실을 반영한 것입니다.
피어 또는 공급자로부터 피어 또는 공급자에게 (경로에 계곡을 생성하는) 경로를 발표하는 경우, 그 다음에는 트랜짓을 제공하게 됩니다.
무료로 제공하게 됩니다. 따라서 가오의 알고리즘은 밸리 없는 경로의 최대
밸리 없는 경로의 최대 개수를 도출하려고 합니다.
AS를 최상위로 선택하고, 비슷한 학위를 가진 AS는 피어(P2P)일 가능성이 높다고 가정합니다. Gao는 자신의
단일 티어 1 AS에서 얻은 정보를 사용하여 결과를 검증했습니다.
(AT&T)에서 얻은 정보를 사용하여 결과를 검증했습니다. 샤와 가오[36]는 다음과 같은 개선안을 제안했습니다.
추론 프로세스의 시딩을 위해 일련의 기준 진실 관계를 사용하는 Gao의 알고리즘. 트랜짓 관계
은 밸리 프리 가정을 사용하여 추론됩니다. Gao의
알고리즘[18]은 나머지 미해결 링크에 사용됩니다. 그들은
검증 데이터의 80%를 사용하여 2,254개(6.3%)의 추론을 검증했습니다.
검증 데이터의 80%를 사용하여 추론의 2,254건(6.3%)을 검증한 결과, 알고리즘이 다음과 같은 경우에 정확하다는 것을 발견했습니다.
P2P 링크의 96.1%, P2P 링크의 89.33%.
수브라마니안 외[34]는 가오의 휴리스틱을 다음과 같이 공식화했습니다.
관계 유형(ToR) 조합 최적화
문제: BGP 경로 집합에서 파생된 그래프가 주어집니다,
밸리가 없는 경로의 총 수가 최대가 되도록 모든 에지에 에지 유형(형제 관계를 무시한 c2p 또는 p2p)을 할당합니다.
경로의 총 수를 최대화합니다. 연구진은 ToR 문제가 NP-완결형이라고 추측하고, 그래프의 핵심에 얼마나 가까운지에 따라 각 AS의 순위를 매기는 휴리스틱 기반 솔루션(SARK)을 개발했습니다.
그래프의 핵심에 얼마나 가까이 있는지를 기준으로 각 AS의 순위를 매기는 솔루션(SARK)을 개발했습니다.
대체로 Gao [18]에서와 마찬가지로, 비슷한 순위의 AS는 다음과 같이 추론됩니다.
P2P 관계가 있는 것으로 추론되고 나머지는
P2P 관계로 추론됩니다. Di Battista, Erlebach 등[9]은 다음과 같이 증명했습니다.
ToR 문제 공식화는 일반적인 경우 NP-완전하고
경우 P2P 관계를 추론할 수 없다는 것을 증명했습니다. 그들은 다음과 같이 보고했습니다.
AS 경로가 밸리가 없는 경우 해결책을 찾을 수 있다고 보고했습니다.
솔루션을 찾을 수 있다고 보고했습니다. 그들은 P2P와 S2P 관계를 남겨두고
관계를 추론하는 솔루션을 개발했지만 P2P 및 형제 추론은 미해결 문제로 남겨두었습니다. 수브라마니안이나 디 바티스타, 에를레바흐는 그들의 추론을 검증하지 않았습니다.
는 추론의 유효성을 검증하지 않았습니다.
계곡이 없는 경로의 비율을 결정했습니다.
Dimitropoulos 등[16]은 MAX-2-SAT 풀이를 기반으로 솔루션을 만들었습니다. 그들은 WHOIS 데이터베이스에 인코딩된
정보를 사용하여 형제 관계를 추론했습니다. 그들의 알고리즘
은 (1) 계곡이 없는 경로의 수와 (2) 공급자의 노드 정도가 클수록
공급자의 노드 정도가 고객보다 큰 경우. 알고리즘은
알고리즘은 파라미터 α를 사용하여 이 두 가지 목표에 가중치를 부여합니다. 3,724개의 AS 관계를 검증했습니다(86.2%가
C2P, 16.1% P2P, 1.2% 형제자매) 3,724개의 AS 관계를 검증한 결과, 알고리즘이
c2p 링크의 96.5%, P2P 링크의 82.8%를 정확하게 추론했습니다,
그리고 90.3%의 형제 링크를 정확하게 추론했습니다. 이들의 검증은 공개 AS 수준 그래프의 9.7%를
공개 AS 수준 그래프의 9.7%를 커버하며 지금까지 가장 많은
검증된 알고리즘입니다. 그러나 MAX-2-SAT는 NP-하드이며
구현이 실제적인 시간 내에 완료되지 않습니다.
구현이 완료되지 않았습니다.
UCLA의 인터넷 연구소는 AS 수준의
관계로 주석이 달린 인터넷 그래프를 생성합니다[3]. The
방법은 Zhang 등[37]의 논문과
Oliveira 외. [29]. 그들의 알고리즘은 일련의 AS로 시작합니다.
의 집합으로 시작한 다음, 이 AS들이 보이는 링크를
링크를 추론하고 다른 모든 링크는 P2P로 간주합니다. Zhang [37]
은 파벌을 추론하는 방법을 설명합니다; Oliveira [29]는 다음과 같이 가정합니다.
티어 1 AS는 위키피디아에 게시된 목록과 같이 외부에서 사용할 수 있다고 가정합니다. 공급자 AS 아래에서만 볼 수 있는 지역별 c2p 관계가 점점 더 많아지고 있습니다,
이 접근 방식은 실제로는 P2P 관계이지만
실제로는 P2P 관계입니다. Gregori 등[23]도 비슷한 접근 방식을 사용했습니다;
각 AS 경로에 대해 그들의 알고리즘은 가능한 관계를 식별합니다.
가능한 관계를 식별하고 경로의 수명을 기반으로 실제 관계를 추론합니다. 23, 29, 37] 중 어느 것도 검증을 설명하지 않습니다.
검증의 부재로 인해 AS 관계 추론 연구는 위태로운 과학적 위치에 놓여 있습니다. 그럼에도 불구하고 다음과 같은 가정을 바탕으로 연구가 계속되고 있습니다.
의미 있는 AS 관계 추론을 달성할 수 있고
보안 기술 배포 [21], 인터넷 토폴로지 매핑 [6, 8, 12], 진화 [13, 14] 등 인터넷 연구에 적용되었습니다.
및 진화[13, 14]에서부터 산업 복잡성[17] 및 시장 집중도[15]에 이르기까지 다양합니다. 도메인 간 연결의 다양성으로 인해
연결성의 다양성으로 인해 관계 추론은 (그 자체만으로는)
패킷이 실제로 이동한 경로를 일관되게 예측하지 못합니다.
예측 기능은 여전히 미개척 연구 분야로 남아 있습니다[27].
인터넷 레졸루션 분야의 중요성을 고려하면