Person:

Jain, Shaili

We explore the problem of modeling Internet connectivity at the Autonomous System (AS) level and present an economically-principled dynamic model that reproduces key features of the AS graph structure. We view the graph as the outcome of optimizing decisions made by each AS given its business model. In our model, nodes (representing ASs) arrive over time and choose and change providers to maximize their utility. Our formulation of AS utility includes revenue from an AS’s own generated demand for traffic, congestion and routing costs, as well as transfers to and from provider and customer ASs, respectively. Our model has the following features: it uses an empirically-motivated model of traffic demand (Chang, Jamin, Mao, Willinger, 2005) which considers the variation in demand with ASs’ business models and the graph of business relationships; it allows for nodes to revise their connections over time, in a fashion similar to the well-known ‘forest fire’ model (Leskovec, Kleinberg, Faloutsos, 2005); a node’s utility explicitly models many of the major economic and technological issues at play. We validate our model-generated graphs against those of other generative models. Building on previous work that has shown that rule-based generative models like preferential attachment yield poorly-performing traffic routing graphs (Li, Alderson, Doyle, Willinger, 2006), we show that our graphs perform well as designed, engineered systems, while retaining measured statistical properties of the AS graph.

End-to-end packet delivery in the Internet is achieved through a system of interconnections between the network domains of independent entities called autonomous systems (ASes). Inter-domain connections are the result of a complex, dynamic process of negotiated business relationships between pairs of ASes. We present an economically-principled generative model for autonomous system graph connectivity. While there is already a large literature devoted to understanding Internet connectivity at the AS level, many of these models are either static or based on generalized stochastics.