There are strong parallels between the BGP routing space and the condition commonly referred to as the tragedy of the commons. The BGP routing space is simultaneously everyone's problem, as it impacts the stability and viability of the entire Internet, and noone's problem in that no single entity can be considered to manage this common resource. - Geoff Huston, IRTF mailing list, 15 Dec 2000
Questions about Internet growth and continuing viability of the BGP4 routing system have become regular topics at operational as well as engineering and research meetings. Many discussions result in global credence given to presented opinions no matter the scope of the data analyzed. Inadequacies in current Internet routing analysis tools and methodology handicap efforts to plan future architectures. There are currently no reasonable inter-domain Internet routing models, and current methods to analyze routing dynamics are neither calibrated nor refined. This project is predicated on the hypothesis that scalable solutions for evolution of the Internet require understanding of current behavior and trends. CAIDA plans to develop techniques for correlating massive volumes of routing and topology data and tools to support modeling and prediction of routing behavior. The four proposed research tasks are of pressing interest to Internet research, operations, and public policy; each requires maintenance of instrumentation for data acquisition as well as management, analysis and visualization of resulting data. CAIDA's extensive measurement infrastructure and previous work in analysis of the Internet's core [1,2,3] provide groundwork for this research.
The first task is to develop a calculus to describe and model the structure and dynamics of global Internet topology. The second task is to characterize the evolution of the Internet routing system, especially with respect to expansion, refinement, and churn within core BGP tables. CAIDA's preliminary investigations  indicate that actual sources and trends in recent Internet growth and dynamics contradict prevailing wisdom of experts in the area. The third task is to evaluate the effect of incongruity between topology and articulated routing policy. Disparity between paths followed by packets and policy-based BGP paths have been observed, but the effects of these incongruities [4,5] are unknown. CAIDA's topology probe monitors, many with co-located routing tables available, uniquely allow characterization of incongruity sources [6,7]. The final task focuses on modeling peering policy dynamics to capture the effects of the millions of peering computations that occur simultaneously and continuously in the Internet routing system. Peering affects the fundamental connectivity of the infrastructure, however one can currently observe only a tiny fraction of the effects. Current models of Internet structure are deceptive in simplicity - models that ignore backup paths cannot accurately portray the behavior and resilience of the Internet to damage.
The intellectual merit of this agenda is substantial, combining mathematical approaches from graph theory with extensive knowledge of BGP engineering practices to derive metrics and dimensions of the Internet's core. The vast quantity and utility of BGP data now available, as well as the ability to extend CAIDA's current topology framework, supports rigorous research. CAIDA's history of collaboration with operational network engineers provides the ability to calibrate analysis results against common engineering practice, as well as to offer insight on the effects of such practices on the larger infrastructure.
The broader impacts of this work on society are profound. An empirically-derived and reasonably detailed depiction of macroscopic Internet structure would support operational stability, national security, and development of future Internet architectures. This research will facilitate the abilities to: identify highly connected components that might jeopardize the overall infrastructure if damaged or removed, as well as strategic locations within the Internet for deploying limited resources; establish a process for incremental, hierarchical emergency notification of ISPs in the face of a critical security vulnerability, in order to minimize damage; illustrate infrastructural tradeoffs of routing and address allocation policies; and provide realistic topology input into network modeling research and simulation, rather than relying on the current limited data [8,9,10]. Understanding the underlying connectivity of the relentlessly evolving Internet, an increasingly critical national resource, is prerequisite to securing a more robust, stable, and resilient infrastructure.
Internet routing poses complex data collection and analysis problems. In an attempt to separate facts from Internet `myths' about the routing system, CAIDA hosted an Internet Statistics and Metrics Analysis (ISMA) workshop focused on Internet routing and topology data analysis. This workshop, held in December 2001 at SDSC, brought together researchers from academia and commercial ISPs actively working in this emerging field. A key workshop deliverable was to clarify what research questions are relevant to maintaining the health of the global Internet routing system.
ISP operators have questions that researchers are now in a position to answer. Research efforts offer the potential to benefit the Internet infrastructure as a whole if researchers pay attention to the needs of the operations community1. Both communities must cooperate to produce the high quality data necessary to achieve sound results. To this end, the Internet community needs to deploy more real-time instrumentation that will not negatively impact performance. Data and methodologies to support real-time analysis of critical routing events will both improve operations and help researchers to assess trends over time.
Widespread concern exists regarding the appropriate steps to promote graceful evolution of the Internet inter-domain routing system. There is a dearth of empirical data and understanding of how Border Gateway Protocol (BGP) connectivity manifests itself at the router level. For example, there are often disparities between the topology suggested by the Autonomous System (AS) BGP paths active at a given routing table and the actual forward IP path traversed by a packet leaving that router. Since BGP semantics are both applied and transmitted independently at every router, and also non-BGP-based decisions can influence routing, such incongruity is not unexpected. However these disparities undermine the integrity of any Internet modeling methodology that relies solely on topology information at the AS granularity, such as those described in [11,12,13,14].
Understanding of global inter-domain Internet routing dynamics lags significantly behind the growth in the routing system itself [15,16,17]. To improve the routing system, we need to better understand how it currently works, starting with calibration and refinement of various methods used to analyze routing dynamics. This proposal is founded on the premise that it takes an understanding of the behavior of the existing Internet to develop scalable solutions that allow graceful Internet evolution. CAIDA proposes the development of techniques for correlating massive volumes of Internet routing and topology data and the development and enhancement of tools aimed at improving the community's ability to model realistic inter-domain Internet routing behavior.
The structure of the the proposal is as follows: Section 2 describes currently available data, analyses, and tools concerning Internet topology and routing. Sections 3.1, 3.2, 3.3 and 3.4 outline the proposed research topics. For each research topic, five detailed dimensions organize CAIDA's proposed research methodology: data requirements; data collection; analysis; visualization; and broader impacts. The data collection aspect involves engineering (tool development, deployment, and data management) in addition to research. CAIDA performs engineering tasks as a foundation for rigorous inquiry, and integration of CAIDA's engineering and research has proven successful in previous efforts [18,6]. Section 4 discusses data collection, analysis, and visualization issues common to all research topics. Section 5 outlines the process of dissemination of results to the relevant communities. Section 6 describes broader social impacts of the work.
Both research and commercial entities are involved in WAN modeling and simulation efforts (e.g. VINT , OPNET , SSFnet [21,10,22]). Recent efforts have focused on analysis of real-time updates from BGP routing tables [23,24,25,3], and forward path measurement data [26,7,27,28,29]. There are currently no realistic studies of global multicast topology in the literature.
CAIDA's macroscopic topology project , sponsored since 1998 by both DARPA and NSF, provides the most comprehensive Internet public topology analysis in the world. CAIDA has gathered four years of IP-level topology information and indicators of path-specific Internet performance (e.g., latency). CAIDA monitors more than 500,000 destinations [26,7,30] from twenty sources worldwide on a daily basis. Data from this effort are currently used by more than twenty research groups  around the world. CAIDA maintains daily operational summaries , including plots of distributions of IP hop count, global RTTs, RTT by continent, RTT vs longitude, subsets of poorly served (high RTT) destinations, and distribution and dispersion of paths by country and AS. CAIDA also performed a commissioned study for RSSAC of destinations with high RTTs from root nameservers  and will continue similar DNS system topology and performance analysis work commissioned by RSSAC in 2002-2003.
Interdomain BGP routing tables  from backbone providers provide some of the most intriguing sources of Internet data today. CAIDA's December 2001 ISMA workshop report  describes public sources of global routing data and its use in modeling and analysis, including applications to traffic engineering. The RouteViews project  provides BGP data about the global routing system from several backbone perspectives around the Internet. While the RouteViews project was initially intended to help operators assess operational routing problems, many researchers have found it a rich data source for routing analysis and visualizations [17,32,29,26,33]. In 2001 RouteViews began to increase the granularity of their data collection, archiving tables every two hours rather than daily and in November 2001 they began to store individual BGP updates as well. Much of CAIDA's topology and routing research relies on the RouteViews data archive.
RIPE, a European IP network management collaboration, also recently started collecting fine-grained routing data by archiving BGP announcements from multiple locations (10 by 2001) in a MySQL database . Specifically, remote route collectors take snapshots of routing tables three times per day and store all BGP route announcements. While more peers would add incrementally to the data coverage, current routing data archives (RouteViews and RIPE) provide sufficient data to perform macroscopic analyses.
Finer-grained temporal analysis of routing dynamics require actual BGP updates (each BGP message) rather than routing table snapshots. In particular, BGP updates are necessary for studying BGP convergence  properties at up to a one-second granularity.2 Similarly, for fine-grained IP topology analysis, BGP data is necessary but not sufficient; it must be augmented with high granularity traceroute data since the nature of the incongruity between actual topology and topology available from BGP is as yet unclear. In particular, CAIDA has determined definitively that macroscopic traceroute data captures considerably more connectivity information than the aggregation of many dozens of BGP tables from top-tiered ISPs .
Formidable challenges exist in extracting meaningful insights from measurements, even of homogeneous data sets. Data sets are typically extremely large (gigabytes to terabytes), in heterogeneous formats, and gathered at different times, granularities, and locations, both geographically and logically. Developing effective and efficient distillation methods and modes of visualization are significant components of analysis tasks. Section 3 describes how CAIDA will build upon its extensive experience with analytical techniques.
Analysis of Internet router-level topology was pioneered by Paxson in his PhD thesis  and follow-up study . Other topology studies have covered smaller data sets [38,39,40], data gathered from a single source [41,42], the impact of topological properties on protocol performance , and web-based topology (from URLs and HTTP GETs) . CAIDA's studies have benefited from the availability of multiple data sources [29,26,45,32,1,2]. Several studies on Internet connectivity have used publicly available routing tables [17,46,47,48] described above in Section 2.2, in conjunction with other data for validating traffic engineering methodologies [49,50,51,52,53,54,55]. BGP data has been used to map IP addresses to ASes , and to analyze routing policies . However, BGP connectivity does not portray redundancy in different parts of the network. BGP tables show only the selected (best) routes rather than all possible paths and also do not show public and private exchange points, short-term AS path variation, or AS load balancing. Significant distortions of network connectivity, including in the core, are produced when using only BGP data to develop any kind of topology map. BGP data is simply too sparse.
Meaningful visualizations of Internet routing and topology are rare. Visualizing large network graphs has received significant attention [41,57,58] but no current tools can flexibly incorporate the semantics of BGP routing data. CAIDA has experience with developing and using tools for analysis and visualization of topology and BGP data [32,59,60,41,7], and has modified some of these tools to handle specific routing semantics or topology characteristics. CAIDA has also developed methods for mapping IP addresses to geographic (latitude/longitude) coordinates . A successful visualization technique for AS relationships is found in CAIDA's AS-based Internet core map  which incorporates BGP and skitter data with geographic information.
Advantages of an empirically-derived depiction of macroscopic Internet structure include the abilities to: identify vulnerable or strategic points in the infrastructure; develop a process for incremental emergency notification of ISPs in the face of a critical security vulnerability; and realistic topology inputs for network modeling research and simulation.
CAIDA has analyzed Internet graphs at various granularities and evaluated problems in gathering and analyzing Internet routing and topology data in graph form. Specifically, CAIDA reported the degree of connectivity information captured through BGP routing tables  versus forward topology (traceroute-like ) probes [1,29]. These results show that CAIDA's macroscopic topology data collection captures significantly more bidirectional AS-level connectivity, by at least an order of magnitude, than any publicly available interdomain (BGP) routing tables. This divergence suggests that available routing table information may provide an inaccurate representation of Internet topology. In particular, Internet vulnerability, e.g., resilience to attacks, cannot be reasonably inferred from BGP data [11,1,29].
CAIDA's current topology data sets , in conjunction with the best available BGP routing data [17,34], are sufficient for initial investigation of this topic. Deployment of additional topology probe monitors will provide more coherent sampling and allow more legitimate extrapolation to the global structure. This deployment will also support other topics of this proposal and research of other organizations.
Router-level topology data is critical for drawing global inferences about Internet core structure. CAIDA proposes to create a tool that focuses on finding new links (both core and edge) with emphasis on maintaining fresh topology state. CAIDA will also create a reliable method to determine router-level connections, (i,e. interfaces on the same routers) so as to infer which of them belong to the same physical device, and map BGP information to the router level. CAIDA's experience with both collection and analysis of router-level topology data provides a unique advantage in developing this next-generation tool.
During previous investigations of models of the Internet core, CAIDA has applied graph theory to macroscopic Internet topology data . Using traceroute-based topology data and RouteViews BGP table data, CAIDA has analyzed, at both the IP and AS levels, the most highly connected components of the global Internet . These portions represent strategic locations in the infrastructure. CAIDA has compared several combinatorial approaches, including:
Challenges in visualizing pieces of the Internet's `core' include those for visualization of any large graph; the core contains many thousands of nodes. While there is ongoing research in large graph manipulation [57,65,66,67] none have focused on Internet-specific data. The challenge is to develop techniques to allow us to identify, navigate, and analyze core components. One of the few interactive navigation tools for routing data, created at Merit in 1997 , has demonstrated limited utility thus far due to its restricted functionality, efficiency, and discontinuation of support. CAIDA's dispersion graphs  depicting both AS and country granularities provide a useful visual mode for tracking topological diffusion into the infrastructure. Topic 1 will require extension of this analysis technique to an interactive mode, and incorporation of hierarchical as well as geographical layout to allow correlation between topology and geography.
An empirically-derived and reasonably detailed depiction of macroscopic Internet structure would support operational integrity, national security, and research on viable future architectures of the Internet. Specifically, this research will enable us to:
A quantitative analysis of the hierarchical nature of the infrastructure is also likely to reduce ungrounded marketing or political assertions and increase scientific discussions on classification of service providers.3
CAIDA has used the RouteViews data to support our topology analysis [1,26,7,27,28,29,25] as well as to characterize the sources of growth and instability of the routing system .
Available BGP routing data from RouteViews and RIPE provide sufficient information for this topic.
As of November 2001 RouteViews has tables from 55 peering routers, many more than the 11 it had in November 1997. If an analysis spans a long time interval, some participants have likely joined and/or dropped out during the interval. In this case one must either use fewer tables or use tables from different peers throughout the interval. BGP routing tables available from RouteViews in November 2001 vary in size from 2 prefixes to more than 106K prefixes . Table sizes vary noticeably by day with changes up to a few percent. There is a continuous gain and loss of prefixes, a property we refer to as churn.
BGP routing is performed at the granularity of IP address prefixes. Each prefix, specified by a starting address and a CIDR length, may not be nested within another prefix. A prefix, P1, is more specific than another one, P2, if P1 is nested in P2. Similarily P2 is less specific than P1. We categorize prefixes in the BGP routing tables as:
Note that all of these definitions are relative and depend on the particular prefix set.
A prefix is globally routed if it is common to a comprehensive set of BGP tables. However results depend heavily on the particular BGP tables chosen for analysis. Analytic stability is achieved by abandoning the notion of globally routed prefixes and defining the concept of semiglobal prefixes instead. We call a prefix semiglobal if it is found in more than half of the RouteViews backbone tables. This choice of prefix set effectively rules out local prefixes seen in only one or two of the tables but also retains a prefix if it is dropped by a few peers. Use of semiglobal prefixes smooth out local variations that appear when using globally routed prefixes on different sets of tables and yield more robust results. (See  for details.)
|Figure 1: Semiglobal prefixes provide a more robust and stable set of prefixes for routing table analysis.|
Figure 1 shows the size of global and semiglobal prefix sets for 26 backbone peers in 724 snapshots taken every 2 hours for October-November 2001. We use the 711 of the tables that include more than 100K semiglobal prefixes for detailed analysis of routing system changes.
Internet growth depends upon interaction of economic, social and technological factors. Different metrics appear to grow independently, e.g., number of ASes and prefixes. However CAIDA has found a compellingly simple relation between the count of extant prefixes and ASes:
where P is the number of semiglobal prefixes and A is the number of ASes.
|Figure 2: The average number of ASes increases faster (lower line) than prefixes (upper line), showing a refinement process.|
Although oscillations in the error reflect the dynamic nature of Internet routing, the accuracy of Equation 1 is within a few percent. Figure 2 depicts this approximation against AS and prefix growth, demonstrating that Equation 1 provides an exceptional fit for semiglobal prefixes despite the variability in growth rates. Equation 1 also implies that the average number of prefix announcements per AS is shrinking at a rate of 200 / A1/3. We call this process AS refinement since the number of prefixes per AS decreases over time. This refinement process accelerated in 2001; it remains to be seen whether this 2/3 relation will continue to hold in the future.
Visualization challenges are similar to those of the Internet core, but with the additional challenge of handling depiction of macroscopic changes across time. CAIDA is currently investigating various visualization techniques to develop a method for animating such changes.
CAIDA's routing system analyses to date we have found several results that contradict prevailing wisdom. In particular, many measures of routing system complexity have demonstrated slow growth, dynamic equilibrium, and occasional contraction over the last several years. Contrary to existing operational opinion, most growth in prefixes between late 2000 and mid-2001 was in top prefixes (i.e., those prefixes that are not more specifics) and caused by four sources: allocation (55%), deaggregation(37.5%), expansion(5%) and aggregation(2.6%). Other commonly held assumptions about Internet growth are refuted by our results:
CAIDA's analyses suggest that many Internet metrics were stable and that Internet growth and instability originate mainly in large and medium-sized ISPs. The data implies that current operational thinking, which currently focuses on controlling the `explosive' inter-domain routing growth, and views the contribution of smaller (and/or non-transit) ASes as dominant, deserves reexamination. Experts in the operational routing as well as research communities suggest that the recent contraction in routing table growth and churn is the direct result of more careful management of the routing system. Huston attributes global routing system changes of the last two years to developments such as: protocol implementation maturity; widespread deployment of flap dampening; and greater levels of circuit reliability . We find all of these factors, even combined, offer a much less compelling explanation than the current global economic recession. Furthermore it is unclear how long this breathing room will last before we will need a longer-term solution to the interdomain routing problem .
Two types of incongruity in the Internet routing system remain largely unexplored. The first is the disparity between the topology suggested by the AS paths in a given BGP routing table and the actual forward IP paths taken by a packets leaving that router. BGP semantics are executed and transmitted independently at each hop with each peer. These semantics can be affected by route aggregation or overridden by traffic engineering tools or other non-BGP-based decisions, which makes such incongruity inevitable. Indeed, routing policy effects imply that just because a router can `see' an AS advertising a given prefix P seven AS hops away, this router cannot necessarily reach prefix P along that path. Any intervening AS might have a different reachability perspective. CAIDA's collection and active analysis of large topology graphs, some with routing tables co-located with the source, uniquely allows taxonomization of classes of incongruity between forward and announced paths [6,7].
A second type of topological incongruity occurs between unicast and multicast routing. Multicast routing deployment evolved independently from the existing unicast system with fundamentally different routing models. Although policy-based routing has been developed for the multicast infrastructure, it is still possible (and typical) for multicast topologies to fundamentally differ from unicast topology. This problem is increasingly relevant in the face of growth in streaming media and expanded deployment of multicast technologies. Exploratory data analysis will allow for recommendations for measurement, analysis, and mitigation of problems generated by unicast versus multicast routing incongruities.
The significance of the effects of the incongruities that we have observed [4,5] is currently unclear. Although initial investigations suggest that the consequences for network performance and for the integrity of topology modeling are substantial, quantifying the extent of the impact will be an important result of this research.
In addition to the topology data described in Section 3.1, incongruity analysis will require routing tables immediately adjacent to the host from which the topology map was gathered. CAIDA has permission from administrators at most CAIDA probe host sites to gather and archive their BGP data and the topology monitoring will continue under independent funding for the next three years.
The most important data collection goal in this topic is to characterize the limitations in the necessarily coarse granularity forward path, BGP, and multicast routing and topology data. Determining the effects (costs) of these limitations will require finer time granularities in measurement instrumentation in order to capture the incongruities of interest. Specifically, quantifying differences between the forward AS path packets follow and the AS path stored in the router will require a real-time BGP feed with triggered active probing of the forward path as soon as an update occurs. This challenge requires extension of CAIDA's current topology probing  software, which currently probes at a much lower granularity.
CAIDA has conducted preliminary studies of forward versus announced AS path incongruity . In several incongruous paths, the actual forwarded path was 2-3 ASes longer than that reported by BGP. These additional `hidden' ASes have negative implications for network performance. CAIDA has confirmed these performance effects in its study comparing the predictive value of both forward AS path lengths and BGP AS path lengths to RTT (round-trip time) performance destinations . The results suggest forward AS path lengths have a much greater predictive value than other metrics.
CAIDA has independently reported that forward path topology data is characterized by connectivity statistics that are significantly different from those derived from BGP data . These results question the validity of research efforts that use only BGP data to model Internet structure or behavior. CAIDA has also observed anomalies of unintended transit, which opens the possibility of loops for multihomed providers . CAIDA will be able to identify incongruent paths that use an AS for transit which was announced only as an origin AS in the routing table, by deriving a list of transit ASes from a routing table and comparing to actual measured forward paths.
This topic introduces a relatively unexplored area of both network and visualization research: the unique challenge of how to depict the differences between routing tables, sets of paths or both. CAIDA will initially adapt our existing powerful visualization tools Otter  and Walrus , along with our recently prototyped PlotPath , which can display forward paths between a source and a set of destinations. Further evolution of these tools will occur in conjunction with analysis of the data and concomitant refined understanding of the visualization requirements. Section 4.2 provides additional details about these tools and our goals.
The ability to compare different routing or forward topology graphs will allow network engineers to compare effects of router configurations and routing policy among various routers over time. These tools could be adapted for use on live BGP data feeds and for simulating the effects on AS topology of removing ASes, e.g., to emulate functional impact of damage to critical portions of the Internet. Analyzing the impact of congruity on performance can also help reveal limits of theoretical results using BGP data, illustrate infrastructural tradeoffs of certain policies, and suggest what other topological abstractions might be useful. Results will also apply to the problem of server selection, relevant to many current and proposed infrastructure management techniques.
As discussed in Section 3.1, a model of the Internet's core is subject to the effects of interdomain BGP peering. The observed infrastructure is the result of millions of peering computations occurring both simultaneously and continuously. Understanding routing policy and dynamics at a fine resolution is essential to understanding the structure of the Internet. Peering affects the fundamental connectivity of the infrastructure, however one can actually observe only a tiny fraction of the effects through currently feasible data collection methods. Policy observed is limited to the `best path' computed at a router. Discovery of alternative paths only occurs through changes to the primary path. A realistic model of the Internet must derive topology based on all available paths (optimal and backup). Any other model of the structure may be deceptive in its simplicity. In particular, models ignoring backup paths are poor for understanding the behavior and resilience of the Internet to damage.
Data requirements for understanding peering include the topology data described in Section 3.1 and a complete routing information base from routers. The only `routing table' available for export from current routers is the forwarding information base (`FIB'), which is insufficient for this task as it includes only the best paths rather than the full set of possible paths.4
A complete model of peering will require a mechanism to extract the entire routing information base rather than just the optimal paths used for forwarding. The engineering effort may require resources (from router vendors) beyond the scope of this project, but we will pursue other funding sources and collaborators to meet this goal, since it is central to so much of current Internet research. This objective is discussed more in Section 4.1. CAIDA's existing and planned topology measurement will fill gaps left by this lack of complete routing information base (`RIB') availability.
Accurate identification of peering points will allow us to better classify peering relationships between ISPs into categories that qualify the underlying business relationships. The model of the Internet core introduced in Section 3.1 will provide an initial framework for parameterizing routing policy relationships among ISPs in the Internet today. CAIDA will create a model with enough flexibility to express routing policies of ISPs. Because CAIDA's topology data is richer in connectivity information than available routing table data, this data will enable researchers to further develop the models of peering initially proposed by Griffin and Wilfong  and extended by Gao and Rexford . In both studies, the goal was to infer and characterize Autonomous System relationships in the Internet. Gao et al.  hierarchically categorized AS relationships and evaluated the accuracy of heuristic mechanisms for determining whether a given AS relationship is provider-customer, peer-peer (in which parties exchange customer routes) or sibling-sibling (in which parties exchange transit routes). The methodology provided a starting point for an investigation of the effects routing policy has on AS path lengths.
Refining this model will require extracting three parameters from active Internet measurements: (1) AS adjacencies, which can be extracted directly from BGP routing tables; (2) peering point prefixes, which can be extracted from traceroute data; and (3) routing policy estimates, which must be inferred from both BGP and traceroute data sources. AS adjacencies in BGP AS paths represent a record of some peering relationships between pairs of ISPs.
An effective study of routing policy cannot treat ASes as single points since ASes may span large geographical distances around the globe. CAIDA's preliminary results found several cases in which ASes do not exhibit the same per-prefix policy at all adjacencies. It is thus necessary to know which peering point the traffic crosses to understand which routing policy applies. Previous work concentrated on topology at the granularity of ASes but did not preserve sufficient per-prefix information to study the effects of routing policy in this topology.
A realistic model of the Internet core will thus require maintaining a more complete list of public prefixes used for peering between ASes in addition to a list of ISP peering sessions observed at BGP peering points. (Both tasks are already supported with some momentum but with scant funding [77,78].) The current lists can be augmented by using prefixes from traceroute data and assuming that an IP address corresponds to an exchange point if it connects two other distinct ASes. Using traceroute forward path topology in conjunction with BGP data  one can map each IP address to an origin AS. Additionally, prefixes that occur on the paths between many diverse pairs of ASes are likely candidates for exchange point prefixes.
As routing tables continue to grow, consuming computational and physical resources, it becomes increasingly important to identify the primary sources of the growth in order to limit deleterious effects. In preliminary analyses CAIDA found that many different prefixes have exactly the same AS path. (In August 2000 RouteViews data, there were seven times as many prefixes as unique AS paths in a complete BGP table.) A compelling question is: how many prefixes share a common system of AS paths versus those that are actually routed differently? Using the RouteViews data, CAIDA researchers found it possible to redistribute IP addresses such that global routing tables would contain less than 20,000 prefixes with no change to the AS path system in April 2001 .
In order to make inferences about path properties that allow improvement in routing performance, CAIDA wanted to find the most concise, stateful representation of global routing relationships. After extensive measurement and analysis, CAIDA defined an equivalence between IP prefixes in a BGP table, based on their forward AS paths: Two IP prefixes are AS-path-equivalent if their AS paths coincide in the BGP table, i.e. there is no way to distinguish between them by asking the question "What is the AS path to this prefix from peer (name)?' Such a class of AS-path-equivalent prefixes is called a BGP atom.
CAIDA's definition of BGP atom introduces an intermediate granularity between prefix and AS, useful for studying Internet routing and topology. In the actively probed topology data , there are twice as many IP address equivalence classes (atoms) as ASes, and about five times as many prefixes as atoms. Because each prefix in a BGP atom shares common characteristics, e.g. packet kinematics (RTT) and dynamics (loss), path properties currently only available via extensive and exhaustive data collection and analysis could be inferred from BGP data. Thus BGP atoms could considerably reduce the range and frequency of Internet measurements while providing input necessary to improve router performance.
When the fundamental unit is the AS path equivalence relationship represented by the BGP atom, a `routing map' would then illustrate relationships among atoms, CIDR prefixes, and lists of other attributes. Notification of changes in those attributes could occur via TCP or some other (new) protocol to articulate changes in bandwidth, reachability, performance across a given AS path. To conserve traffic the message could be compressed by encoding the AS path once and adding label, prefix, and reachability data elements. The map could be updated with information regarding a given atom rather than for every affected prefix. Using BGP atom granularity for information exchange could conceivably dramatically decrease convergence times without violating policy.
Visualization of global peering involves challenges similar to those involved in mapping the core of the Internet (Section 3.1.4). In addition, dynamic components are needed to incorporate real-time determination of global peering relationships using both graphical and text-based interfaces. Specific research goals include: selection of meaningful mappings (both spatial and logical); visualization at the router as well as AS level; identification of the age and source of peering information; and depiction of bilateral versus multi-way peering.
Enhanced understanding of peering dynamics will enable CAIDA to address questions that relate to the core mapping described in Section 3.1. A dynamically acquired/maintained map of Internet peering points will also allow us to address fundamental questions of theoretical, operational and public policy interest:
Peering points, unlike ASes, are physically localizable. While a transit AS in the Internet core is distributed over a continental or global region, a peering point is typically a single physical location where multiple routers are co-located. IP addresses inside these peering points form a small subset of all IP addresses that can be used to definitively map a path through the Internet to a series of geographical locations. The location of each peering point can be the basis for a method of mapping network devices and paths to geographical locations with a high degree of accuracy. This approach will allow CAIDA to quickly report statistics of public policy and regulatory interest, such as what percent of routes transit the U.S. or other countries and in particular what percentage of intra-country routes (where the source and destination are both in the same country) transit another (third-party) country.
For each topic described in Section 3, CAIDA recognizes the need for a router-level graph of the `core' of the Internet. It is computationally impossible to monitor every Internet router and derive a complete graph, but CAIDA's topology data collection in conjunction with CAIDA's heuristic-based interface-to-router aggregation tool provide the best feasible approximation.
CAIDA has years of experience gathering topology data, monitoring from more than 20 source monitors to more than half a million IP destinations around the world. Further, CAIDA has evolved procedures for remote administration of boxes as well as transfer and management of the resulting large data sets. Last but perhaps most important, CAIDA has also achieved an effective method for dealing with complaints from probed sites which minimizes the misunderstandings inherent to topology probing projects [42,41].
CAIDA collaborates with the University of Oregon's Advanced Network Technology Center  to expand the functionality and operational analysis of RouteViews, based on the needs and ideas from the community and our empirical datasets. Participants in the CAIDA ISMA 2000 workshop  offered useful feedback on the utility of currently collected routing data to the research community, which has led ANTC to investigate moving toward a non-IOS solution, improving the archiving infrastructure, and integrating with the RIPE-NCC's Information Service  archiving project.
The fundamental data types in this proposal are BGP routing tables and router topologies, which can be conceptualized as a complex, semantically rich graph. Researchers need visualization tools to represent this information at a higher level. Existing tools for visualizing these data sets are currently insufficient to allow researchers to filter and segregate interesting components from these graphs.
Any given BGP table holds routing information in the form of AS paths. These paths are sequences of autonomous systems a packet transits from source to destination. Elementary visualization approaches split AS path information into node pairs (i.e. two nodes and one link) to display adjacencies. However these adjacencies are meaningless in isolation from the peering session behind the link. Pure AS connectivity is misleading as it represents unilateral local peering links between two specific ASes. Therefore each AS path must be displayed as an ordered and directed `route-ful' set of AS adjacencies.
CAIDA has enhanced its Otter tool to include a "path" object, which allows a more accurate representation of BGP data. The interactive applet allows highlighting of the entire path that a given peering session believes. A second enhancement modifies Otter to allow pre-computed layout coordinates, scaling the tool from accepting graphs of only a few hundred links to those several orders of magnitude larger. This functionality has been a critical step in macroscopic topology visualization.
CAIDA's Walrus program was designed to handle large data sets (more than 500,000 nodes). Walrus makes use of 3D hyperbolic space (Figure 3) which allows the user to interactively navigate the data set while the majority of the graph remains within view. Walrus incorporates node and link color to aid in segregation of areas of the data of particular interest. Walrus is currently undergoing alpha testing with 60 users around the world.
PlotPath  was developed by CAIDA as a visualization tool that depicts paths between many different source-destination forward and reverse paths simultaneously. Information about individual links is retained. PlotPath incorporates a general layout algorithm allowing incorporation of disparate data sets while retaining a simplified (digestable) view of complex network topology. (See Figure 4.)
CAIDA recognizes that these tools will undergo development in conjunction with evolving mathematical and statistical analyses. Network topology research will require integration of disparate data sources from multiple perspectives, e.g. integration of forward paths with BGP table updates, as well as longitudinal changes in topology.
CAIDA has a long history of collaboration with vendors, ISPs, routing registries, and other researchers. This project will be no exception. Collaborators will include: UO Advanced Network Technology Center, RIPE NCC, ARIN, Cisco Systems, Inc. Juniper Networks, Inc., and MFN. In addition, we will make use of open-source routing collection software from projects such as Zebra, used in RIPE NCC's RIS Collector project.
CAIDA has a strong history of successful outreach and information dissemination through workshops , web sites, animations and videos , presentations, and presentations to commercial and research organizations. CAIDA is also known for making collected data available to researchers while protecting the privacy of users. Results from this project will lead to routing-related curriculum materials for undergraduate and graduate use as part of CAIDA's NSF-supported Internet Engineering Curriculum (IEC) repository  and Internet Teaching Labs (http://iec.caida.org/).
Results of this effort will also yield development of tools for navigation, analysis, and correlated visualization of routing tables and massive volumes of traffic data and path-specific performance and routing data critical to advancing both research and operational efforts of the evolving commercial Internet. CAIDA will create a knowledge base that will facilitate suggestions to routing vendors with respect to what instrumentation within the router would facilitate diagnosing and fixing problems in closer to real-time. This research also has implicit relevance to public policy and regulatory questions regarding concentration of administration of Internet infrastructure. Specifically, the developed tools will allow immediate feedback, concerning interrupted service or malicious damage affecting Internet health, to appropriate agencies so as to facilitate rapid implementation of global remedies and/or countermeasures.
There is widespread community concern regarding the appropriate next steps to take to support graceful evolution of the Internet inter-domain routing system. A more flexible Internet inter-domain routing system could allow for calculation of optimal route (with variety of metrics), be load-sensitive/adaptive, and even support negotiation of inter-domain SLAs. There is little chance of success in design of a new routing protocol/system without greater understanding of the dynamics of the current system. No good Internet routing models currently exist nor are current methods to analyze routing dynamics calibrated or particularly refined. Both the operational and research communities need to better understand relationships between Internet size and routing tables, topology and policy, and policy and traffic demands.
There is growing concern about the complexity of the Internet (in terms of paths, topology, convergence properties, etc.) due to more complex routing practices (multihoming, backup, load-balancing etc.). Current factors causing BGP table growth and dynamics will not be alleviated by another round of CIDR deployment pressure within the operator community. The community must consider how to manage a BGP routing table which has millions of small entries, rather than the original expectation of tens of thousands of larger entries.
A new routing architecture will require integrated economic feedback such as in-band micropayments for route announcements, as well as inter-domain propagation of performance-based metrics, e.g., RTT, packet loss, jitter, bandwidth estimates. Yet there is little chance of success in designing a new routing protocol/system without a greater understanding of the dynamics of the existing system. Not only do we currently lack any good inter-domain Internet routing models, but current methods to analyze routing dynamics are neither calibrated nor refined.
The current economic slowdown has given the global Internet routing system a bit of breathing room , but we do not know how long this respite will last, nor whether `responsible' use of the routing system can effectively hold things in check. (Consider countries in Asia, with a few billion people, huge markets, and essentially not much dependence upon the US-European economic dynamics).5 We should use this time wisely to develop models of Internet structure and change that are consistent with available and growing data archives. Payoffs to the research outlined in this proposal include greater understanding of: incongruity between routing policy and topology; peering policy dynamics; relationships between address allocation policy and connectivity; and which metrics best reflect routing dynamics and growth. Progress on understanding these fundamental aspects of the relentlessly evolving Internet is absolutely prerequisite to securing a more robust, stable, and resilient infrastructure.
8 Milestones and Timeframes for funding and research completion
Research Topic Year 1 Year 2 Year 3 Description of compare models of core; calibrate and refine propose emergency Internet structure analyze exhaustion of ASNs, topology inputs. notification process IPs, and IP space fragmentation for ISPs Routing system dynamics track growth, refinement categorize contributors to track growth, and churn; determine trends. BGP dynamics. refinement, and churn. in background update generation design algorithms to find offer data-based vs full-table transmission due to major BGP update sources policy guidance core router stability. and their propagation range Assess incongruity between identify examples of create taxonomy of incongr. evaluate effects of topology and routing policy incongruity between forward types; estimate degree of incongruity on perf. and announced paths Internet hidden NATs/VPNs and stability on host and traffic basis Model peering dynamics provide initial framework measure statistics of publish model of for paramteizing peering policy public policy interest peering dynamics
2The effects of multi-hop eBGP on the timing of these updates seems unlikely to affect the integrity of resulting convergence analyses since BGP often has to deal with such raw (single hop) latency anyway, at least internationally.
3The NANOG mailing list [69,70,71] has a recurring thread about the `tiering' of service providers in the Internet hierarchy. Although there are informal business definitions, there is no quantitative definition for what constitutes inclusion in a given tier.
4There are extremely good reasons, having to do with system stability, for making it impossible to export any but the best path via BGP, but router vendors have never provided any other means for making the entire database available.
5It is true
that by some metrics the United States indirectly controls the vast
majority of the address space and routing system,
it is important to keep in mind that a single /8 allocated to
APNIC is 65,000 /24's, a significant chunk of a
core BGP routing table. And with market pressure mounting,
ISPs may soon find incentive to drop the premise of filtering
/32's. Or, we may see entirely different inter-domain paradigm
emerge in other parts of the world, e.g., many /32s attached to NATs.