Transcript ppt

The Workshop on Internet
Topology (WIT) Report
ACM SIGCOMM Computer
Communication Review Volume
37 , Issue 1 (January 2007)
Dmitri Krioukov CAIDA
Fan Chung UCSD
kc claffy CAIDA
Marina Fomenkov CAIDA
Alessandro Vespignani Indiana University
Walter Willinger AT&T Research
What we need to know to
understand Internet Topology
• As and router level topology generation
mechanisms.
• Degree based methods (PLRG, BA,
BRITE, BT, INET)
• Structural methods (GT-ITM)
• Canonical topologies
• General model of Random Graphs (GRG)
• Power law Random Graph (PLRG)
Outline
• Motivation of different people interested in
this area
• Different models
• Different way for data collection
• Open Problems
• Recommendations
Motivation
networking researchers
• what a node or a link represents
• physically meaningful topologies ie router-level connectivity
• logical constructs such as AS-level topology, or overlay networks
such as the WWW graph, email graph, P2P networks
• how new technologies, policies, or economic conditions will impact
the Internet’s connectivity structure at different layers.
physicists
• Internet is just one of many examples of a complex network.
• Physicists search for inherent principles shaping small and largescale network patterns.
• They want to find universal laws on application domains.
Motivation
Mathematicians
• Internet topology analysis, having mathematicians involved will
stimulate the development of suitable mathematical apparatuses.
Engineers
• need understand the Internet structure since performance of several
applications and protocols depends strongly on peculiarities of an
underlying network.
• Ex: Recent research suggests that observed Internet-like topologies
are particularly well-structured for routing efficiency (A. Brady and L.
Cowen, “Compact routing on power-law graphs with additive
stretch,” in ALENEX, 2006. ) but the existing Internet routing
architecture does not exploit this efficiency. The knowledge and
understanding of the topological properties of the Internet should
help engineers to optimize future technological developments.
Data
• Mathematicians do not need data at all
• Physicists are interested in data to support their
models, but are not especially concerned much about
the data quality
They both rely on Networking community
• Engineers are the closest to collecting actual data, at
least about their own networks. However, data
ownership and stewardship are complex and highly
charged issues with numerous social, political, liability,
and security implications.
• It is the responsibility of all data users to educate
themselves on the incompleteness, inaccuracy, and
other deficiencies of these measurements and to avoid
over interpretation.
Data Collection Techniques
• Simulation technique for random graph generator
• Router level graph
– Trace route over months, over different monitoring points to
collect data
• WHOIS database
– Whois databases enable you to search for information about the
people, computers, organizations, and name servers. top-level
domains ".com", ".net", and ".org" can be searched from their
online database ie. http://www.whois.sc/
- Search domain names using partial word(s) in Domain Search.
- Partial word(s) searching on active domain names ("bill gates")
- IP address searching ("66.218.71.198")
- Full domain ( nameintel.com goes directly to whois)
Data Collection Techniques
• What is AS? – IP with common Routing policies
• What is BGP? - organizations can run BGP using private AS numbers to an
ISP that connects all those organizations to the Internet
• BGP data collection (Autonomous Systems AS level
graph)
– BGP tables are collected from Oregon route Server, this
connects to the various ISP for collecting BGP table.
http://www.routeviews.org
– The ability to infer AS peering relationship, from BGP routing
tables depends largely on inter-AS business contracts. If a
business contract does not permit a given inter-AS route to be
used by a third party, BGP does not advertise this information to
the global Internet.
– Internet Routing Registry (IRR) databases
Models
• Static - constructing statistical ensembles of
random networks with certain characteristics
matching values measured in the real Internet.
• Dynamic - trying to reproduce the details of the
Internet evolution/growth
Networking researchers
– descriptive in the sense of matching certain graphtheoretic properties
– provide context for known structural or architectural
features of Internet
Physicists and Mathematicians
– Lets leave it
(OPEN PROBLEMS)
better Internet topology data
•
Incompleteness of the data
– classical Erd˝os-R´enyi random graphs, are extremely unlikely to represent real
Internet topologies measured from multiple vantage points
– inference of probability distributions specifying possible quantitative deviations of
real topologies from measured ones remains largely an open problem
– lack of observation points, finite number of destinations probed, inability to
capture other layers and disambiguate between high-degree nodes and opaque
clouds
•
•
•
We need targeted measurements focused on particular geographic areas.
Existing measurement tools have not demonstrated the ability to scale up to
measure link and/or node properties across realistic networks
Internet measurement would ideally progress from measuring only the intraand inter-AS topology at the router- and AS-level (“An empirical approach to
modeling inter-AS traffic matrices,” in IMC, 2005.)
(OPEN PROBLEMS)
Modeling
• Descriptive models strive to reproduce some graphtheoretic properties of the Internet and usually are not
concerned with their network-specific interpretation.
(“The Internet AS-level topology: Three data sources and
one definitive metric,” Computer Communication Review,
vol. 36, no. 1, 2006. )
• explanatory models acknowledge domain-specific
constraints (traffic conditions, cost-minimization
requirements, technological reality ) while attempting to
simulate the fundamental principles and factors
responsible for the structure and evolution of network
topology. But which factors are critical is open problem.
(OPEN PROBLEMS)
Modeling
• Future developments in the field of Internet modeling
may include the following advancements
– Annotated models of an ISP’s router-level topology, where nodes
are labeled with router capacity, type, or role, and link labels
describe delay, distance, or bandwidth;
– annotated models of the Internet’s AS-level topology, where
node labels include AS-specific information, e.g., number and/or
locations of PoPs, customer base, and link labels reflect peering
relationships
– models built around parameters closely related to real use of the
network, e.g., routing models that define and utilize routingrelated parameters such as robustness, fairness, outage, etc.
– dynamic, evolutionary models of the Internet deriving simple
rules for network evolution from actual technological constraints,
e.g., from known Cisco router characteristics.
(OPEN PROBLEMS)
General Theory
Internet is complex engineered system because
• At the AS level, the Internet topology is a result
of local business decisions independently made
by each AS
• On the other hand, at the router level the
Internet topology is a product of humancontrolled technological optimizations aiming to
minimize cost and maximize efficiency
(OPEN PROBLEMS)
General Theory
• Traditional graph theory is not suitable for dealing with dynamic
network structures that change over time.
• Multiple layers in the Internet protocol stack have their own
corresponding topologies, i.e., fiber, optical, router, AS,Web, P2P
graphs, that describe significantly different aspects of Internet
connectivity.(Multiscale Modelling and Simulation, Springer, Berlin,
2004 )
• Need to development of new approaches, techniques, and tools for
measuring or inferring, AS related traffic.
• Interplay political, social, economical, technological diversity
– For example, is the router-level topology of a large Korean ISP different
because of their atypically high penetration of broadband deployment,
or importance of gaming traffic?
– small Chinese Internet AS-level topology preserves the structural
characteristics of the global Internet (Chinese Internet AS-level
topology,” 2006, arXiv:cs.NI/0511101.)
RECOMMENDATIONS
• Interdisciplinary communication remains a serious bottleneck,
important to read, try to understand, and cite publications from other
fields
• A lack of comprehensive and high-quality topological and traffic data
represents a serious obstacle to successful Internet topology
modeling, and especially model validation.
– outreach to Internet registries, e.g., ARIN, RIPE, and other databases
regarding access and use of their data for research purposes;
– develop new techniques and tools to collect the data for the next
generation of Internet models
– Concentrate on robustness
– support repositories of publicly available topology and traffic data
• DatCat - facilitate sharing of data sets with researchers in pursuit of more
reproducible scientific results (http://imdc.datcat.org.)
• convert theoretical results into practical solutions
• Can a GENI-like facility help in tackling some of the research
challenges identified in this report, and if so, how?