3. DATA
In this section we present the sources of data we use: public BGP data, a list of AS allocations to RIRs and organizations, and multiple sources of validation data.
3.1 BGP paths
We derive BGP paths from routing table snapshots collected by the Route Views (RV) project [5] and RIPE’s
Routing Information Service (RIS) [4]. Each BGP peer is
a vantage point (VP) as it shows an AS-level view of the
Internet from that peer’s perspective. For each collector, we
download one RIB file per day between the 1st and 5th of
every month since January 1998, and extract the AS paths
that announce reachability to IPv4 prefixes. When we extract the AS paths, we discard paths that contain AS-sets
and compress path padding (i.e. convert an AS path from
“A B B C” to “A B C”). We record all AS paths that are
seen in any of the five snapshots and use the union to subsequently infer relationships. We use all paths and not just
“stable” paths because backup c2p links are more likely to
be included if we use all AS paths, and temporary peering
disputes may prevent a normally stable path from appearing
stable in our five-day window of data.
Figure 1 shows the number of ASes peering with RV or
RIS between 1998 and 2013. We also show the number providing full views (routes to at least 95% of ASes). RV is
the only source that provides BGP data collected between
1998 and 2000, and while more than two thirds of its peers
provided a full view then, it had at most 20 views during
these three years. For the last decade, approximately a third
of contributing ASes provide a full view. Most (64%) contributing ASes provide routes to fewer than 2.5% of all ASes.
The operators at these ASes likely configured the BGP ses-
sion with the collector as p2p and therefore advertise only
customer routes.
3.2 Allocated ASNs
We use IANA’s list of AS assignments [2] to identify valid
AS numbers assigned to organizations and RIRs. We filter
out BGP paths that include unassigned ASes, since these
ASes should not be routed on the Internet.
3.3 Validation data directly reported
Our website provides the ability to browse our relationship
inferences and submit validation data. We use corrections
to two separate inferred datasets, created in January 2010
and January 2011 using a previous relationship inference
algorithm. This older algorithm did not produce a cycle
of p2c links but assigned many more provider relationships
than ASes actually had; 93% of the website feedback consists
of p2p relationships, and 62% of that consists of correcting
our inference of a c2p relationship to a p2p relationship. In
total, we received 129 c2p and 1,350 p2p relationships from
142 ASes through our website. The disparity between our
previous inferences and the submissions motivated the new
algorithm that we present in this paper.
We separately followed up on unchanged inferences with
operators, as well as submissions that seemed erroneous compared to observations in public BGP paths. We received
responses from more than 50 network operators. 18 relationships submitted through our website were later acknowledged by the submitting operator to have been inaccurately
classified (9 by one operator) or to have changed subsequent
to the submission. Additionally, based on email exchanges
with operators, we assembled a file containing 974 relationships – 285 c2p and 689 p2p (contained within the “directly
reported” circle of figure 2, described further in section 3.6).
3.4 Validation data derived from RPSL
Routing policies are stored by network operators in public databases using the Routing Policy Specification Language (RPSL) [7]. The largest source of routing policies
is the RIPE WHOIS database, partly because many European IXPs require operators to register routing policies with
RIPE NCC. The routing policy of an AS is stored as part
of the aut-num record [7]. The aut-num record lists import
and export rules for each neighbor AS. An import rule specifies the route announcements that will be accepted from theneighbor, while an export rule specifies what routes will be
advertised to the neighbor. The special rule ANY is used by
an AS to import/export all routes from/to the neighbor, and
is indicative of a customer/provider relationship. Using the
RIPE WHOIS database from April 2012, we extracted a set
of c2p relationships using the following method: if X has a
rule that imports ANY from Y, then we infer a c2p relationship if we also observe a rule in Y’s aut-num that exports
ANY to A. Limiting ourselves to records updated between
April 2010 and April 2012 provided us with 6,530 c2p links
between ASes with records in RIPE NCC’s database.
3.5 Validation data derived from communities
AS relationships can be embedded in BGP community attributes included with each route announcement. Community attributes can be tagged to a route when it is received
from a neighbor. Community attributes are optional transitive attributes; they can be carried through multiple ASes
but could be removed from the route if that is the policy
of an AS receiving the route [11]. The tagging AS can annotate the route with attributes of the neighbor and where
the route was received, and the attributes can be used to
control further announcements of the route. The commonly
used convention is for the tagging AS to place its ASN, or
that of its neighbor, in the first sixteen bits. The use of the
remaining 16 bits is not standardized, and ASes are free to
place whatever values they want in them. Many ASes publicly document the meaning of the values on network operations web sites and in IRR databases, making it possible
to assemble a dictionary of community attributes and their
policy meanings. We used a dictionary of 1286 community
values from 224 different ASes assembled from [22] to construct a set of relationships from BGP data for April 2012;
in total, there are 41,604 relationships in our set (16,248 p2p
and 23,356 c2p).
3.6 Summary of validation data
Figure 2 uses a Venn diagram to show the size and overlap
of our validation data sources. Overall, 2203 of 2225 relationships that overlap agree (99.0%), with multiple explanations for the discrepancies. For the directly reported source,
some operators reported a few free transit relationships as
peering relationships, i.e., they were reported in the traditional economic sense rather than in a routing sense. For
the RPSL source, some providers mistakenly imported all
routes from their customers and some customers mistakenly
exported all routes to their providers. For the BGP communities source, some customers tagged routes exported to
a Tier-1 AS as a customer. While there are limits to the accuracy of all our sources of validation, the 99.0% overlap in
agreement gives us confidence in using them for validation.
We assembled our validation data set by combining our
four data sources in the following order: (1) directly reported using the website, (2) RPSL, (3) BGP communities,
and (4) directly reported in an email exchange. Where a
subsequent source classified a link differently, we replaced
the classification; we trust relationships acquired through
email exchanges more than relationships submitted via the
website. Our validation data set consists of 48,276 relationships: 30,770 c2p and 17,506 p2p.
To estimate possible biases in our validation data set, we
compared its characteristics with those of the April 2012
BGP dataset in terms of the link types and the minimum
distance from a VP at which those links were observed. The
closer the link is to a vantage point, the more likely we are
to see paths that cross it. We classify links as clique (one
endpoint is in the clique), core (both endpoints are not in
the clique and are not stubs), and stub (one endpoint is
a stub and the other endpoint is not in the clique). Figure 3(a) shows clique links are over-represented in our validation data set as compared to BGP data, while stub links
are under-represented. This disparity is due to the validation data from BGP communities, which mostly comes from
large ASes. Figure 3(b) shows links directly connected to a
VP (distance 0) are over-represented in our validation data
relative to April 2012 BGP data, likely due to the communities dataset, many of which involve ASes that provide VPs.
.3 데이터
이 섹션에서는 사용하는 데이터 소스, 즉 공개 BGP 데이터, RIR 및 조직에 대한 AS 할당 목록, 여러 유효성 검사 데이터 소스에 대해 설명합니다.
3.1 BGP 경로
라우트 뷰(RV) 프로젝트[5]에서 수집한 라우팅 테이블 스냅샷과 RIPE의
라우팅 정보 서비스(RIS) [4]. 각 BGP 피어는
해당 피어의 관점에서 인터넷의 AS 수준 뷰를 보여주는
인터넷의 AS 레벨 뷰를 보여줍니다. 각 수집기에 대해
1998년 1월부터 매월 1일에서 5일 사이에 하루에 하나의 RIB 파일을
1998년 1월부터 매월 1일에서 5일 사이에 하루에 하나의 RIB 파일을 다운로드하여
를 추출합니다. AS 경로를 추출할 때 AS 세트가 포함된 경로는 삭제하고
를 포함하는 경로는 삭제하고 경로 패딩을 압축합니다(즉, AS 경로를 다음과 같이 변환합니다.
"A B B C"에서 "A B C"로 변환합니다.) 다섯 개의 스냅샷 중 하나에
모든 AS 경로를 기록하고 유니온을 사용하여 관계를 추론합니다. 모든 경로를 사용합니다.
백업 c2p 링크가 포함될 가능성이 더 높기 때문에 "안정적인" 경로를 사용합니다.
모든 AS 경로를 사용하는 경우 포함되며, 임시 피어링으로 인해
분쟁으로 인해 정상적으로 안정적인 경로가 나타나지 않을 수 있습니다.
5일 동안의 데이터에서 안정적으로 나타났습니다.
그림 1은 1998년부터 2013년까지 RV 또는
RIS로 피어링한 AS의 수를 보여줍니다. 또한 전체 보기(최소 95%의 AS에 대한 경로)를 제공하는 숫자도 보여줍니다. RV는
1998년과 2000년 사이에 수집된 BGP 데이터를 제공하는 유일한 소스입니다.
1998년과 2000년 사이에 수집된 BGP 데이터를 제공하는 유일한 소스이며, 당시에는 동종 업체의 3분의 2 이상이
전체 뷰를 제공했지만, 이 3년 동안에는 최대 20개의 뷰만
최대 20건의 뷰를 제공했습니다. 지난 10년 동안, 기여한 AS의 약 1/3
전체 보기를 제공하는 AS가 증가했습니다. 기여한 AS의 대부분(64%)이 전체 AS의 2.5% 미만에 대한 경로를 제공합니다.
이러한 AS의 운영자는 아마도 수집기를
수집기와 P2P로 연결하여 고객 경로만
고객 경로만 광고합니다.
3.2 할당된 ASN

유효한 AS 번호를 식별합니다. 필터링
할당되지 않은 AS가 포함된 BGP 경로를 필터링합니다.
AS는 인터넷에서 라우팅되어서는 안 됩니다.
3.3 직접 보고된 유효성 검사 데이터
트위터 웹사이트는 트위터의 관계를 검색하고
추론하고 유효성 검사 데이터를 제출할 수 있습니다. 당사는 두 개의 개별 추론 데이터에
2010년 1월과 2011년 1월에 생성된 두 개의 개별 추론 데이터 세트에 대한 수정 사항
이전 관계 추론 알고리즘을 사용하여 2010년 1월과 2011년 1월에 생성된
알고리즘을 사용했습니다. 이 이전 알고리즘은 P2P 링크의 주기를 생성하지 않았지만
P2P 링크의 주기를 생성하지 않았지만, 실제 AS보다 더 많은 공급자 관계를
웹 사이트 피드백의 93%가 P2P 관계로 구성되어 있으며
웹 사이트 피드백의 93%는 P2P 관계로 구성되어 있으며, 그 중 62%는
c2p 관계를 p2p 관계로 추론하는 것입니다. In
총 142개 AS로부터 129건의 c2p 관계와 1,350건의 P2P 관계를 접수했습니다.
142개의 AS로부터 총 129개의 c2p 및 1,350개의 P2P 관계를 받았습니다. 이전 추론과 제출된
이전 추론과 제출된 데이터 사이의 불일치로 인해 새로운
알고리즘을 개발하게 되었습니다.
저희는 변경되지 않은 추론에 대해 별도로 후속 조치를 취했습니다.
운영자와 함께 변경되지 않은 추론과 공개 BGP 경로에서 관찰한 것과 비교했을 때 오류가 있는 것으로 보이는 제출물을 별도로 추적했습니다. 우리는 50개 이상의 네트워크 사업자로부터
50개 이상의 네트워크 사업자로부터 답변을 받았습니다. 웹사이트를 통해 제출된 18개의 관계는 나중에 제출한 사업자가 부정확한 것으로 인정했습니다.
(한 사업자가 9개) 또는 이후 변경된 것으로 확인되었습니다.
제출한 것으로 확인되었습니다. 또한, 운영자와의 이메일 교환을 바탕으로
운영자와의 이메일 교환을 기반으로 974개의 관계(285개의 C2P와 689개의 P2P)가 포함된 파일을 작성했습니다(그림 2의 "직접 보고된" 원 안에 포함됨).
보고된" 원 안에 포함되어 있으며, 3.6절에서 자세히 설명합니다).
3.4 RPSL에서 파생된 유효성 검사 데이터
라우팅 정책은 네트워크 사업자가 라우팅 정책 사양 언어(RPSL)를 사용하여 공용 데이터베이스에 저장합니다[7]. 라우팅 정책의 가장 큰 출처는
의 가장 큰 소스는 RIPE WHOIS 데이터베이스인데, 이는 부분적으로 많은 유럽 IXP가 사업자가 라우팅 정책을
RIPE NCC. AS의 라우팅 정책은 자동 번호 레코드[7]의 일부로 저장됩니다.
의 일부로 저장됩니다 [7]. 자동 번호 레코드에는 각 이웃 AS에 대한 가져오기
및 각 이웃 AS에 대한 내보내기 규칙이 나열됩니다. 가져오기 규칙은 이웃에서 수락할 경로 알림을 지정하고, 내보내기 규칙은 이웃에 알릴 경로를 지정합니다.
경로를 지정합니다. 특수 규칙 ANY는 다음에서 사용됩니다.
AS가 이웃과 주고받는 모든 경로를 가져오거나 내보내는 데 사용되며
는 고객/공급자 관계를 나타냅니다. 4월부터
2012년 4월의 RIPE WHOIS 데이터베이스를 사용하여 다음을 사용하여
다음 방법을 사용하여 c2p 관계의 집합을 추출했습니다.
규칙이 있는 경우, Y의 자동 번호에서 A로 ANY를 내보내는
사이에 업데이트된 레코드로 제한합니다.
2010년 4월과 2012년 4월 사이에 업데이트된 레코드로 제한하면 6,530개의 c2p 링크가
6,530개의 c2p 링크를 제공했습니다.
3.5 커뮤니티에서 파생된 검증 데이터
AS 관계는 각 경로 발표에 포함된 BGP 커뮤니티 속성에 포함될 수 있습니다. 커뮤니티 속성은 경로가 이웃으로부터 수신될 때 경로에 태그를 지정할 수 있습니다.
경로에 태그를 지정할 수 있습니다. 커뮤니티 특성은 선택적 전이 특성으로, 여러 AS를 통해 전달될 수 있지만
를 통해 전달될 수 있지만