Transcript Diapositiva 1 - Roma Tre University

computer networks research group @ roma III university
inter-domain routing, ipv6,
and network visualization
giuseppe di battista
maurizio patrignani
main research topics
• interdomain routing
–
–
–
–
–
–
–
–
analysis of the route changes for the incoming traffic flows
location of the internet routing instabilities
modeling of bgp configurations and analysis of their stability
inference of the customer-provider relationships
study of the routing (a)symmetries
engineering of the incoming traffic flows
discovery of a large(r) as graph
integration and visualization of the irr info
• intradomain routing
– ospf visualization
– layer-3 discovery techniques
• ipv6
– support for the ipv4-ipv6 transition
– multi-homing methods
• network emulation
– cheap and easy-to-configure test-beds for complex networks
computer networks research group @ roma III university - namex 19 nov 04
analysis of the route changes for
the incoming traffic flows
• development of a web service, called bgplay,
visualizing the route changes of a prefix in a
specific time window
• two running servers at
– routing information service of the ripe ncc
(www.ris.ripe.net/bgplay/)
– route views project of the oregon university
(www.routeviews.org)
• each based on the corresponding repository of
bgp updates
• an alpha version at roma III university with the
most recent features
computer networks research group @ roma III university - namex 19 nov 04
bgplay query form
specify the prefix
(network) you want to
monitor
specify an interval
of time
select data sources
computer networks research group @ roma III university - namex 19 nov 04
computer networks research group @ roma III university - namex 19 nov 04
bgplay demo
computer networks research group @ roma III university - namex 19 nov 04
location of the internet routing
instabilities
• monitoring of the network from several
vantage points
– each vantage point stores the bgp updates
that are “visible” from its location
• related updates are grouped into “events”
• the causes of each event are (if possible)
identified by studying the evolution of the
routing over time
computer networks research group @ roma III university - namex 19 nov 04
modeling of bgp configurations and
analysis of their stability
• study of formal models for the description
of bgp configurations and behaviors
• study of the effect of different time
sequences of the events
• identification of possible routing
instabilities
• routing stability vs forwarding stability
– stability of the entire routing information base
vs stability of the best choice
computer networks research group @ roma III university - namex 19 nov 04
inference of the customer-provider
relationships
• a simple model accounting for customerprovider and peer-to-peer relationships only
• infer the types of relationship between
autonomous systems by observing the as-paths
associated with announcements
– if sensible rules of thumb are followed by network
operators, each as-path is “valley free”
• if rules of thumb are followed by network
operators, relationships can be efficiently
inferred
computer networks research group @ roma III university - namex 19 nov 04
inference of the customer-provider
relationships
• if a set of relationships making all as-paths
valley free does not exist
– we prove that maximizing the number of
valley free as-paths is a hard problem
– we propose heuristics for this problem that
outperform cutting-edge techniques described
in literature
computer networks research group @ roma III university - namex 19 nov 04
study of the routing (a)symmetries
• netviewer web service
– prototype at www.dia.uniroma3.it/~compunet/
• having at disposal internal and external
info shows routing asymmetries
• group prefixes into classes that have the
same routing
• in cooperation with caspur and garr
computer networks research group @ roma III university - namex 19 nov 04
example of routing classes
198.150.84.0
198.150.85.0
198.150.87.0
198.150.2.0
198.150.22.0
198.150.38.0
198.150.4.0
198.150.5.0
198.150.6.0
198.150.7.0
198.150.9.0
computer networks research group @ roma III university - namex 19 nov 04
1st July 2003
example of asymmetric routing
= 129.125.0.0/16
= 130.136.0.0/16
computer networks research group @ roma III university - namex 19 nov 04
1st July 2003
engineering of the incoming traffic flows
• even a limited control of the announcements
propagation could be used to
– balance traffic from the upstream providers
– prefer reliable incoming paths
– improve internal traffic flows
• engineering incoming traffic via prepending
– Integer Linear Programming formulation
– computational geometry perspective
computer networks research group @ roma III university - namex 19 nov 04
discovery of a large(r) AS graph
• starting from the bgp updates collected by the ris or orv
repositories a big picture of the internet can be obtained
• this picture can be enlarged by observing “unusual” bgp
traffic
– bgp updates with peculiar timings
– bgp updates with peculiar content
• we can gain extra info by
– observing unusual bgp updates
– probing the network with unusual bgp updates
• for example setting up suitable beacons and observing echoes
• in cooperation with namex
computer networks research group @ roma III university - namex 19 nov 04
integration and visualization of the irr info
• hermes service
– available at www.dia.uniroma3.it/~hermes/
• handles a local relational database of routing
information
– downloads rpsl information from more than 50
databases that are individually operated by
organizations such as verio, cable & wireless, merit,
ripe ncc, apnic, arin, sprint, etc.
• through a java applet it is possible to navigate
the repository and obtain information about the
rpsl objects
computer networks research group @ roma III university - namex 19 nov 04
integration and visualization of the irr info
computer networks research group @ roma III university - namex 19 nov 04
integration and visualization of the irr info
computer networks research group @ roma III university - namex 19 nov 04
integration and visualization of the irr info
computer networks research group @ roma III university - namex 19 nov 04
integration and visualization of the irr info
computer networks research group @ roma III university - namex 19 nov 04
integration and visualization of the irr info
computer networks research group @ roma III university - namex 19 nov 04
integration and visualization of the irr info
computer networks research group @ roma III university - namex 19 nov 04
ospf visualization
• polyphemous tool
– downloadable from www.dia.uniroma3.it/~polyph/
• collects routing information using snmp and
mibs
• explores an ospf network at different levels of
abstraction
– shows ospf areas an area border routers
– shows routers and links inside each area
– provides detailed info about areas, routers, interfaces.
• in cooperation with caspur
computer networks research group @ roma III university - namex 19 nov 04
ospf visualization
computer networks research group @ roma III university - namex 19 nov 04
layer-3 discovery techniques
• nethunter service
– available at www.dia.uniroma3.it/~nethunt/
• exploits a collection of traceroute servers
• explores the surroundings of an ip
interface or network by performing
traceroutes from different vantage points
• uses a logic engine for inferring topologies
– guess and check approach to asses whether
two interfaces belong to the same router
computer networks research group @ roma III university - namex 19 nov 04
support for the ipv4-ipv6 transition
• techniques to detect, and collect information about, ipv6in-ipv4 tunnels (mtu-discovery, dns, ip spoofing,…)
• discovered tunnels can be used as “vantage points” to
launch third-party tunnel-discovery explorations, scaling
up the discovery process
• wide experimentation
– 6bone tunneled network, garr network, wide network, ripe ncc
network and ttm test-boxes
• we assess to what extent 6bone registry information is
coherent with the actual network topology
• we provide the first experimental results on the current
distribution of ipv6-in-ipv4 tunnels in the Internet
• in cooperation with garr and ripe ncc
computer networks research group @ roma III university - namex 19 nov 04
multi-homing methods
• hosts in a multi-homed as receive an ipv6
address from each upstream provider
• how to handle multiple ipv6 addresses?
– need to take into account traffic loads
– need to propagate information from the border
routers to the internal networks
– need to swap ipv6 addresses without
dropping tcp connections
computer networks research group @ roma III university - namex 19 nov 04
cheap and easy-to-configure testbeds for complex networks
• netkit (network emulator)
– available at www.netkit.org
• a linux kernel may run as a user process (user mode
linux)
• a network of linux virtual machines may run on a single
host
• each linux may be configured to run routing daemons
(zebra, bird, gated, routed, xorp, quagga,…)
• new configurations may be tested before being deployed
• in cooperation with garr
computer networks research group @ roma III university - namex 19 nov 04
concluding remarks
• a mixed theoretical-technical approach in
all topics
• tight relationships with network operators
– caspur, garr, namex, orv, ripe, …
• research-teaching coupling
– univ. courses on comp. networks and courses
on specific technologies for companies and
pa
computer networks research group @ roma III university - namex 19 nov 04
thank you!
questions?
computer networks research group @ roma III university - namex 19 nov 04