Sorting of ASes: We sort ASes in the order we will estimate their c2p relationships. ASes in the clique are placed at
the top, followed by all other ASes sorted by transit degree,
then by node degree, and finally by AS number to break
ties. We sort by transit degree rather than node degree to
avoid mistaking high-degree nodes (but not high-transit degree, e.g., content providers) for transit providers. Figure 6
shows the sorted order of the ASes in that graph.
Preventing cycles of p2c links: When we infer a c2p
relationship we record the customer AS in the provider’s
customer cone, and add the AS to the cones of all upstream
providers. Any ASes in the customer’s cone not in the cones
of its upstream providers are also added to the cones of those
providers. We do not infer a c2p relationship if the provider
is already in the AS’s cone, to prevent a cycle of p2c links.
Step 5: Infer c2p relationships top-down using
ranking from Step 2. This step infers 90% of all the c2p
relationships we infer, and is the simplest of all our steps.
We visit ASes top-down, skipping clique ASes since they
have no provider relationships. When we visit AS Z, we infer Y > Z if we observe “X − Y ? Z” or “X > Y ? Z”. To have
observed “X − Y”, X and Y must be members of the clique
(step 3). To have inferred “X > Y” by now, one must have
visited Y in a previous iteration of this step. No cycle of c2p
links can be formed because c2p relationships are assigned
along the degree gradient, i.e. no c2p relationship is inferred
between two ASes where the provider has a smaller transit
degree, a necessary condition to create a cycle. For example,
in figure 6, we first consider (after the four clique ASes) c2p
relationships for 9002 (3356), then 15169 (none), etc.
The order of the ASes in the triplet is important, at this
step and for most of the remaining steps. To minimize false
c2p inferences due to misconfigurations in one direction of a
p2p relationship (an AS leaks provider or peer routes to
peers), we infer a c2p relationship when we observe the
provider or peer closer than the customer to at least one
VP in at least one triplet. This heuristic builds on the intuition that an AS enters a provider relationship to become
globally reachable, i.e., at least one VP should observe the
provider announcing the customer’s routes. For example,
when we infer 3356 > 9002 in figure 6, we use triplet “1239
3356 9002” from path 1 and not triplet “9002 3356 1239”
from path 7 because 3356 appears before 9002 in path 1.
Step 6: Infer c2p relationships from VPs inferred
to be announcing no provider routes. We assume that
“partial VPs” providing routes to fewer than 2.5% of all ASes
either (1) export only customer routes, i.e., the VP has configured the session with the collector as p2p; or (2) have
configured the session as p2c, but have a default route to
their provider, and export customer and peer routes to the
collector. Given a path “X ? Y ? Z” where X is a partial
VP and Z is a stub, the link XY can either be p2c or p2p,
requiring Y > Z. In figure 6, we use path 9 and the inference
of 15169 as a partial VP to infer 6432 > 36040.
Step 7: Infer c2p relationships for ASes where the
customer has a larger transit degree. Given a triplet
“W > X ? Y” where (1) Y has a larger transit degree than
X, and (2) at least one path ended with “W X Y” (i.e. Y
originates a prefix to X), then we assign X > Y. We assume
c2p relationships against the degree gradient are rare, although they can arise from path poisoning. Condition (2)
mitigates the risk of using poisoned paths because poisoned
segments of a path do not announce address space. In figure 6 we infer 721 (X) > 27065 (Y) because path 5 shows
27065 announcing a prefix to 721. In the absence of path 5,
we would infer that 2629 poisoned path 6 with 27065 and
we would not assign a c2p relationship. When we assign X
> Y, we also assign Y > Z where we observe triplets “X >
Y ? Z”; in figure 6 we use path 6 to infer 27065 > 2629.
Step 8: Infer customers for provider-less ASes.
We visit provider-less ASes top-down, skipping clique members because their customers were inferred in step 5. This
step is necessary because steps 5 and 7 require an AS to
have a provider in order to infer customers. Examples of
provider-less ASes are some regional and research networks,
e.g., TransitRail. For each provider-less AS X, we visit each
of its neighbors W top-down. When we observe triplet “W X
Y”, we infer W − X because we never observed W announcing X to providers or peers in previous steps; therefore, X >
Y. We remove the condition in step 5 that the peer AS must
be closest to the VP, because provider-less ASes are mostly
observed by downstream customers providing a public BGP
view. In figure 6, 11164 (X) is a provider-less AS; we use
path 8 to infer 9002 (W) − 11164 (X) and 11164 (X) > 2152
(Y). When we assign X > Y, we also assign Y > Z where weobserve triplets “X > Y ? Z”; in figure 6 we also use path 8
to infer 2152 (Y) > 7377 (Z).
Step 9: Infer that stub ASes are customers of
clique ASes. If there is a link between a stub and a clique
AS, we classify it as c2p. This step is necessary because step
5 requires a route between a stub and a clique AS to be observed by another clique AS before the stub is inferred to be
a customer. Stub networks are extremely unlikely to meet
the peering requirements of clique members, and are most
likely customers. In figure 6, path 2 reveals a link between
1239 and 13395, but there is no triplet with that link in the
set, perhaps because it is a backup transit relationship.
Step 10: Resolve triplets with adjacent unclassified links. We again traverse ASes top down to try to
resolve one link as p2c from triplets with adjacent unclassified links. We do this step to avoid inferring adjacent p2p
links in step 11, since adjacent p2p links imply anomalous
behavior, e.g., free transit or route leakage. We loosen the
requirement in step 5 that the first half of the triplet must be
resolved. When we visit Y, we search for unresolved triplets
of the form “X ? Y ? Z”, and attempt to infer Y > Z. For
each unresolved triplet “X ? Y ? Z”, we look for another
triplet “X ? Y < P” for some other P. If we find one, we
infer X < Y (and Y will be inferred as a peer of Z in step
11). Otherwise we search for a triplet “Q ? Y ? X”, which
implies Y > X, and therefore we would resolve both sides of
the original unresolved triplet to X < Y and Y > Z. Since we
are only confident of resolving one side of the original triplet
(embedding an assumption that most p2c links have already
been resolved at earlier steps), we make no inferences in this
case. Otherwise, we infer Y > Z in this step, and X − Y in
step 11.
Step 11: Infer p2p links: We assign p2p relationships
for all links that have no inferred relationships
AS를 정렬합니다: AS를 c2p 관계를 추정할 순서대로 정렬합니다. 파벌에 속한 AS는
맨 위에 배치하고, 그 다음에는 다른 모든 AS를 경유 정도별로 정렬합니다,
그 다음 노드 정도, 마지막으로 끊을 AS 번호 순으로 정렬됩니다.
타이를 끊습니다. 노드 정도가 아닌 트랜짓 정도를 기준으로 정렬하는 이유는
높은 수준의 노드(콘텐츠 제공자와 같이 전송 수준이 높지 않은 노드)를 전송 제공자로 착각하지 않도록 하기 위해서입니다. 그림 6
은 해당 그래프에서 AS의 정렬된 순서를 보여줍니다.
P2P 링크의 주기 방지: P2P 관계를 추론할 때
관계를 추론할 때 고객 AS를 제공업체의
고객 콘에 고객 AS를 기록하고 모든 업스트림 공급자의 콘에
공급자의 콘에 추가합니다. 업스트림 공급자의 콘에 없는 고객 콘의 모든 AS도
업스트림 공급자의 콘에 없는 모든 AS도 해당 공급자의 콘에 추가됩니다.
공급자의 콘에도 추가됩니다. 공급자가 이미 AS의 콘에 있는 경우에는 C2P 관계를 추론하지 않습니다.
가 이미 AS의 콘에 있는 경우에는 P2P 관계를 추론하지 않습니다.
5단계: 2단계의 순위를 사용하여 하향식으로 P2P 관계 추론
순위를 사용하여 하향식으로 P2P 관계를 추론합니다. 이 단계에서 추론하는 모든 P2P 관계의 90%는
관계의 90%를 추론하며, 모든 단계 중 가장 간단한 단계입니다.
파벌 AS는 공급자 관계가 없기 때문에 건너뛰고 하향식으로 AS를 방문합니다.
제공자 관계가 없기 때문입니다. AS Z를 방문할 때, "X - Y ? Z" 또는 "X > Y ? Z". 다음과 같은 경우
"X - Y"를 관찰하려면, X와 Y는 파벌의 구성원이어야 합니다.
의 멤버여야 합니다(3단계). 지금까지 "X > Y"를 추론하려면 다음이 있어야 합니다.
이 단계의 이전 반복에서 Y를 방문했어야 합니다. c2p의 사이클 없음
링크의 사이클이 형성될 수 없습니다.
학위 경사도를 따라, 즉, 공급자가 방문한 두 AS 간에
공급자의 트랜짓이 더 작은 두 AS 간에는
사이클을 생성하기 위한 필수 조건인 학위. 예를 들어
그림 6에서는 먼저 (네 개의 클릭 AS 다음에) 9002(3556)에 대한 c2p
관계를 고려한 다음 9002(3356), 15169(없음) 등을 고려합니다.
이 단계와 나머지 대부분의 단계에서는 트리플렛에 있는 AS의 순서가 중요합니다.
단계와 나머지 대부분의 단계에서 중요합니다. 잘못된 순서로 인한 잘못된
한 방향의 잘못된 구성으로 인한 잘못된 P2P 추론을 최소화하려면
P2P 관계(AS 누출 공급자 또는 피어 라우트)의 한 방향으로 잘못된 추론을 최소화하기 위해
피어)를 관찰할 때 P2P 관계를 추론합니다.
제공자 또는 피어가 고객보다 하나 이상에 더 가까운
VP를 관찰할 때 c2p 관계를 추론합니다. 이 휴리스틱은 AS가 공급자 관계에 진입하면 다음과 같은 직관을 기반으로 합니다.
전 세계적으로 도달할 수 있는, 즉 적어도 한 명의 VP가
공급자가 고객의 경로를 발표하는 것을 관찰해야 한다는 직관을 기반으로 합니다. 예를 들어
그림 6에서 3356 > 9002를 추론할 때 경로에서 삼중 항 "1239
3356 9002"를 경로 1에서 사용하고 경로 7에서 "9002 3356 1239"
경로 1에서 3356이 9002 앞에 나타나기 때문에 경로 7에서 "9002 3356 1239"를 사용하지 않습니다.
6단계: 추론된 VP에서 c2p 관계 추론하기
가 공급자 경로를 알리지 않는다고 가정합니다. 다음과 같이 가정합니다.
전체 AS의 2.5% 미만에 경로를 제공하는 "부분 VP"
(1) 고객 경로만 내보내거나, 즉 VP가 콜렉터와의 세션을 P2P로 구성했거나, (2)
세션을 P2P로 구성했지만 기본 경로는
공급자로 기본 경로를 설정하고 고객 및 피어 경로를
수집기로 내보냅니다. 경로 "X ? Y ? Z" 경로가 주어졌을 때 X는 부분
VP이고 Z가 스텁인 경로가 주어졌을 때, 링크 XY는 p2c 또는 p2p일 수 있습니다,
그림 6에서는 경로 9와 15169의 추론(
15169를 부분 VP로 사용하여 6432 > 36040을 추론합니다.
7단계: 고객의 경유도가 더 큰 AS에 대한
고객의 경유도가 더 큰 AS에 대한 c2p 관계를 추론합니다. 삼중항이 주어졌을 때
"W > X ? Y"가 주어졌을 때, (1) Y의 경유 도가
X이고, (2) 하나 이상의 경로가 "W X Y"로 끝나는 경우(즉, Y
가 X의 접두사에서 시작됨), X > Y를 할당합니다.
경로 중독으로 인해 발생할 수 있지만, 차수 기울기에 대한 C2P 관계는 드뭅니다. 조건 (2)
는 경로의 포이즌된
세그먼트는 주소 공간을 알리지 않기 때문에 중독된 경로를 사용하는 위험을 완화합니다. 그림 6에서는 경로 5가 다음을 보여주기 때문에 721(X) > 27065(Y)를 추론합니다.
27065가 721에 접두사를 알리기 때문입니다. 경로 5가 없으면
2629가 27065로 경로 6을 독살했다고 추론하고
C2P 관계를 할당하지 않습니다. X
> Y를 할당할 때, 우리는 또한 Y > Z를 할당하여 세 쌍둥이 "X >
Y ? Z"; 그림 6에서는 경로 6을 사용하여 27065 > 2629를 추론합니다.
8단계: 공급자가 없는 AS에 대한 고객 추론.
5단계에서 고객이 추론되었기 때문에 공급자가 없는 AS를 하향식으로 방문하고 클러스터 멤버는 건너뜁니다. 이
이 단계는 5단계와 7단계에서 AS에 제공자가 있어야
제공자가 있어야 고객을 추론할 수 있기 때문입니다. 예
제공업체가 없는 AS의 예로는 일부 지역 및 리서치 네트워크가 있습니다,
예: 트랜짓레일. 제공업체가 없는 각 AS X에 대해
이웃한 W를 하향식으로 방문합니다. 삼중 항 "W X
Y"를 관찰할 때, 이전 단계에서 W가 공급자나 동료에게 X를 알리는 것을 관찰한 적이 없기 때문에 W - X를 추론하므로 X>
Y. 5단계에서 피어 AS가 VP에 가장 가까워야 한다는 조건을 제거합니다.
피어 AS가 VP에 가장 가까워야 한다는 조건을 제거합니다.
퍼블릭 BGP를 제공하는 다운스트림 고객이 관찰하기 때문입니다.
보기. 그림 6에서 11164(X)는 제공자가 없는 AS이며, 경로 8을 사용하여
경로 8을 사용하여 9002 (W) - 11164 (X) 및 11164 (X) > 2152
(Y). X > Y를 할당할 때 Y > Z도 할당하는데, 여기서 우리는 "X > Y ? Z"; 그림 6에서는 경로 8
경로를 사용하여 2152 (Y) > 73을 추론합니다.