Network Models

We model the networks using two types of graphs: random graphs and geographic graphs. The latter consists of network nodes within each of the 50 largest US metropolitan areas. For inter-domain network connectivities, we specify a set of parameters to determine the location and density of network peering points. For intra-domain network connectivities, as ISPs are not willing to disclose fully their network topology, we assume that they are able to engineer and operate their own networks with little or no congestion internally so that the delays between the routers are dominated by the link propagation delay. Consequently, we model the intra-domain network as a complete graph. We assume the ``hot-potato'' routing policy at the inter-domain level, which minimizes the number of network domains crossed. Hence, traffic destined to another domain is always sent to the nearest peering points from the originator towards the destination domain. Although such policy does not result in the best global routes, it is widely used by the current inter-domain routing protocol: the Border Gateway Protocol (BGP) [#!bgp!#].

Our modeling choices do not correspond directly to the current Internet since the information needed to model geographically at the AS-level and the router-level networks is not generally available. The Netgeo tool [#!caida-netgeo!#] from CAIDA is probably the best mechanism available for capturing such data. It extracts information from the whois [#!whois!#] database and attempts to map Internet hosts according to their domain names. However, the accuracy of this method is not at all clear since large IP address blocks can be assigned to a single network entity, and there is the possibility of inconsistency among whois databases. Additionally, it is not possible to determine all the locations of network peering points as many ISPs have private peering links in addition to their point of presence at the public peering points such as the MAEs and NAPs. We detail our parameter choices for the two models below and summarize the parameters in Table 5.1.

Table 5.1: Parameters for Generating Network Graphs

Parameters	Meanings
$n$	network size as # of nodes
scale	size of the network graph
$N_p$	probability of a city in a network
$\tx_p$	interconnection probability between two networks
$\tx_{scope}$	scope of a region possible for interconnection
$\tx_{ds}$	interconnection density
vicinity	vicinity feasible for nodes co-location