A proposal for Exploring Internet Connectivity

ABSTRACT

Exploring As connectivity can give us information about routing policies of ASes in different regions. These policies are not obvious at the first glance and need to be explored. Our major goal in this project is to use traceroutes and CAIDA data set to build a connectivity graph and then apply machine learning and graph mining methods to reveal hidden relationships and phenomena.  Having unusual or interesting phenomena may be due to political issues or business relationships between ASes.

General Terms

Measurement, Algorithms.

Keywords

Regional Internet Connectivity, Routing Policy, AS connectivity and relationships.

1.     INTRODUCTION

The Internet consists of thousands of Autonomous Systems (ASes), operated by many different administrative domains. ASes should cooperate with each other to provide global Internet connectivity using an inter-domain routing protocol. BGP is the dominant routing protocol used to exchange reachability information across ASes.

Since the early days of growing the internet, people found out that a simple shortest-path routing protocol is insufficient to handle operational, economic, and political factors involved in routing. Internet Service Providers (ISPs) would like to control the way traffic flowed for economic and political reasons. So they modified BGP which was originally a simple path-vector protocol to support routing policies. The range of these policies are long and there are various reasons for enforcing such policies such as economic, performance, security, political and scalability factors.

A link between ASes is established when a contractual agreement to exchange traffic is made between them. AS relationships have a deep influence on traffic flow in the Internet. On the other hand, policies enforced by ISPs shape routing behaviors. Reversely, routing behaviors represents general relationship between two ASes [1], [2].  Using this property, routing behaviors can be employed to reveal some hidden business or political relationships between two entities.  This notion is the main motivation of the current project.

In this project we are going to use available traceroutes and CAIDA data set to build connectivity graph. Afterwards, by means of graph mining and machine learning methodologies we attempt to explore the graph in order to study connectivity between regions at AS level and meanwhile search for interesting phenomena using the connectivity graph.

2.     PROJECT GOAL

The goal of this project is to infer policies and connectives between ASes and regional authorities in the internet. Using large traceroute data sets gathered for various regions in the world, we study AS-level connectivities and routing behaviors of these regions.

3.     SCOPE

We aim to analyze the connectivity of the network and routing behaviors of almost all major countries. We first start with some small countries and then we apply our method to more countries.

4.     PROJECT STEPS

In order to achieve the goals of the project, we follow the steps specified in the following subsections.

4.1     Data Collection

First of all, we need AS connectivity dataset to map a graph of the network.

A clear and complete model of internet topology is vital for the purpose of analyses, performance evaluation and protocol design. Despite the fact that many researches have been done on topology modeling of internet, it is still undiscovered at Autonomous System (AS) level. There are many resources that can be used for this matter but none of them is complete by itself and needs to be combined with other resources in order to  give more complete and accurate view [3], [4], [5], [6]. For this reason, different types of Data Set are often used to infer relationships between ASes. Data Set can be divided into:

• Internet Registries
  • IXP Data
  • BGP Table Dumps
  • Traceroutes Data

In this project, we employ two sources of data: regional traceroues and BGP route tables. As our goal in this project is to study regional routings within regions, we need regional traceroutes which is already collected. In case we need to do some targeted traceroutes o, we can make use of Ripe Atlas Probes.

4.1.1     Constraints and challenges

One of the limiting factor of the current project is relying only on two data set resources due to lack of time. Working with outdated or incomplete, or mix disparate data sources into one topology may result in inaccurate internet topology analysis and modeling [7], [8], [9], [10].

4.2     Data Sanitization and clustering

Having traceroute data set, we should sanitize it and remove messy trace routes. Then we do mapping between IPs and AS numbers. According to Professor Gill, these mappings are done and the traceroute dataset is mapped to the related ASes. So we only care about sanitizing targeted traceroutes that we may do ourselves.

4.2.1      Constraints and challenges

While traceroute is a simple and powerful tool which can be used to reveal the underlying network topology, it is subjected to some anomalies.  In the simplest cases, because of some firewalling policies, we may have missing destination and hops in a trace route result. But in more complex cases, when there are load balancers or MPLS routings in the network, traceroute results may suffer from missing links, false links and loops and circles. So in order to employ traceroute results to map the topology of the network, we should deal with these kind of anomalies and come up with reasonable solutions for them.

4.3     Map the network graph

After polishing our data set, plotting a graph is the next step. A graph of a network, represents hubs and their connectivities. We build a primary graph representing AS level connectivities namely peering relationship in a region.

We refer to network(s) under a single administrative control as Autonomous Systems (ASes) and the graphs representing the topology of internet at that level as AS-level graphs. ASes are an important abstraction because they are the “unit of routing policy” in the routing system of the global Internet. ASes peer with each other to exchange traffic, and these peering relationships define the high-level global Internet topology. In As graphs, nodes are ASes and links are peering relationship.

This graph will be used as a building block of next steps in order to find interesting routing behaviors. Based on the specific property we are interested to study, it may be abstracted out to more abstract graphs.

Edges: To construct this primary graph, we need to have AS-level topology and known AS peering relationships. For this purpose, we use CAIDA data set which contains a full AS graph derived from RouteViews BGP table snapshots taken at 8-hour intervals over a 5-day period. To augment this graph and cover hidden relationships, we also employ our traceroute dataset. As we are looking for interesting connectivity of nodes or group of nodes, it is not necessary to have a weighted graph.

Nodes: We also profile each node in the graph to do node clustering in next steps. For each node we assign AS number, country and continent. Based on our machine learning methods, we may add more properties to each node later.

4.4     Clustering and Discovering Interesting Routing Behaviors

Now that the problem has been converted to a graph, we study common trends in routings and look for interesting behaviors. Based on the graph structure, we find common trends of routing in a country or in a continent. As an example, we may find cases that all ISPs of a country goes through a national ISP. We may also find that some special countries in a continent are strongly connected to each other while there are countries which are somehow isolated. In addition, it may happens that some countries that does not have any political relationship with each other, have some AS connectivities.

For this purpose, we come up with some graph metrics to cluster nodes and apply machine leaning methods. The high level idea of the results in this step is as follows.

4.4.1     Finding communities

We aim to find organization of vertices in clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Then we look at the extracted communities and see if they are meaningful in the real world (ex. local ISPs of a country, or ISP’s of a continent or etc.). If we can find a meaning for these communities, we will be able to extract some regional policies based on the links between communities.

4.4.2     Finding rich nodes

Rich nodes are the nodes with high degrees. These nodes can represent vital hubs in the network which are responsible for routing the most part of the traffic in a region. For example they can be important ISPs in a region. At the autonomous systems level (AS graph), in [7] it is showed that links between rich nodes (nodes with large numbers of links) can be crucial for the network structure. Therefore, missing connecting links between rich nodes may come into consideration.

4.4.3     Finding important edges

Some edges in the graph are important because if we remove them, the graph would become loosely connected. In the real world, these are the links that connect two sets of ASes together and there are not enough backup links to provide redundancy and high availability in case of any failure of these links.

5.     TIMELINE

We plan to do the project based on the following schedule. The tasks mentioned in the table are based on the steps described in section 4.

 

Task	Start	Finish	Duration
Data Collection	02/16/2015	02/21/2015	5
Data Sanitization	02/21/2015	02/28/2015	7
Mapping the Graph	02/28/2015	04/01/2015	32
Midterm Report	04/01/2015	04/08/2015	7
Discovering Routing Behaviors	04/08/2015	05/01/2015	23
Final Report	05/01/2015	05/10/2015	9

 

6.     REFERENCES

• Gupta, M. Calder, N. Feamster, M. Chetty, E. Calandro, and E. Katz-Bassett. Peering at the Internet’s frontier: A first look at ISP interconnectivity in Africa. In Passive and Active Measurement Conference, 2014.
• https://github.com/agupta13/Peering-Africa
• Chang et al., “Towards Capturing Representative AS-level Internet Topologies,” in Computer Networks, 44(6):737–755, 2004.
• He et al., “Lord of the Links: A Framework for Discovering Missing Links in the Internet Topology,” IEEE/ACM Trans. Networking, vol. 17, no. 2, 2009.
• Oliveira et al., “In Search of the Elusive Ground Truth: The Internet’s AS-level Connectivity Structure,” in SIGMETRICS, 2008.
• Roughan, J. Tuke, , and O. Maennel, “Bigfoot, Sasquatch, the Yeti and Other Missing Links: What We Don’t Know About The AS Graph,” in IMC, 2008.
• Shi Zhou and Raul J. Mondragon, “The missing links in the bgp-based as connectivity maps,” in Passive and Active Measurement Workshop (NLANR-PAM03), April 2003.
• Clement and J. Obar. Internet Boomerang Routing: Surveillance, Privacy and Network Sovereignty in a North American Context. 2013.
• http://www.datacentermap.com/ixps.html : gives us a map and info about Internet Exchange Points.
• Augustin, B. Krishnamurthy, and W. Willinger. IXPs: Mapped? In Proc. ACM SIGCOMM IMC, 2009.