Transcript Visualizing the Internet topology - Computer Science and Engineering

Inner Sphere 3D Visualization
A novel approach to visualizing the internet.
By David S. Shelley
University of Nevada, Reno
Department of Computer Science, 2009
Outline
1. Common solutions to graphing networks?
2. Visualization Geometry
3. Inner Sphere 3D Visualization of Internet Topology
4. Issues with Method, Conclusion and Future Work
Outline
1. Common solutions to graphing networks?
2. Visualization Geometry
3. Inner Sphere 3D Visualization of Internet Topology
4. Issues with Method, Conclusion and Future Work
Common solutions to graphing large networks
Draw important objects on top of other objects.
Notice how the nodes have been covered up by edges.
Common solutions to graphing large networks
Aesthetic Considerations
Minimize lines crossing.
VS
Non-overlapping.
VS
Scale edge lengths.
VS
Common solutions to graphing large networks
Use alpha-blending
Common solutions to graphing large networks
Layout Algorithms
Planar layout
Tree layout
Circular/Spiral
And there’s more…
Common solutions to graphing large networks
Layout Algorithms Dynamic Networks
Kamada-Kawai (KK) (spring embedder)
Fruchterman-Reingold (FR) Force
Common solutions to graphing large networks
User Interaction
Theus (1996) and Unwin (1999) have proposed there are three broad components of
interaction for statistical graphics.
1. Querying
2. Selection and linking
3. Varying plot characteristics
Common solutions to graphing large networks
User Interaction
Theus (1996) and Unwin (1999) have proposed there are three broad components of
interaction for statistical graphics.
1. Querying
AT&T
Reset Nodes
Demo
http://adn.blam.be/springfield/
Common solutions to graphing large networks
User Interaction
Theus (1996) and Unwin (1999) have proposed there are three broad components of
interaction for statistical graphics.
1. Querying
2. Selection and linking
Select View
Stats View
AT&T
Sprint
Common solutions to graphing large networks
User Interaction
Theus (1996) and Unwin (1999) have proposed there are three broad components of
interaction for statistical graphics.
1. Querying
2. Selection and linking
Common solutions to graphing large networks
User Interaction
Theus (1996) and Unwin (1999) have proposed there are three broad components of
interaction for statistical graphics.
1. Querying
2. Selection and linking
3. Varying plot characteristics
Sort View
Spanish View
AT e T
AT&T
Sprint
Esprint
Common solutions to graphing large networks
User Interaction
Focus + Context
• Basic Idea:
– Show selected regions of interest in greater detail (focus)
– Preserve global view at reduced detail (context)
– NO occlusion
• All information is visible simultaneously
Visualization 2003 - Network Visualization Course - T. Alan Keahey -www.visintuit.com
Common solutions to graphing large networks
User Interaction
Focus + Context
Alternative Names for Focus + Context
• Fisheye views
• Fisheye lens
• Continuously variable zoom
• Nonlinear magnification
• Hyperbolic views
• Distortion viewing
• Rubber sheet views
• …
Visualization 2003 - Network Visualization Course - T. Alan Keahey -www.visintuit.com
Common solutions to graphing large networks
User Interaction
Focus + Context
Applications for Focus + Context
•
•
•
•
•
Visualization of Networks/Graphs
Viewing text
Image/Document viewing
Cartography
Cluster Visualization
Visualization 2003 - Network Visualization Course - T. Alan Keahey -www.visintuit.com
Common solutions to graphing large networks
User Interaction
Focus + Context
Applications for Focus + Context
•
•
•
•
•
Visualization of Networks/Graphs
Viewing text
Image/Document viewing
Cartography
Cluster Visualization
Visualization 2003 - Network Visualization Course - T. Alan Keahey -www.visintuit.com
Common solutions to graphing large networks
User Interaction
Focus + Context
Applications for Focus + Context
•
•
•
•
•
Visualization of Networks/Graphs
Viewing text
Image/Document viewing
Cartography
Cluster Visualization
Visualization 2003 - Network Visualization Course - T. Alan Keahey -www.visintuit.com
Common solutions to graphing large networks
User Interaction
Focus + Context
Applications for Focus + Context
•
•
•
•
•
Visualization of Networks/Graphs
Viewing text
Image/Document viewing
Cartography
Cluster Visualization
Visualization 2003 - Network Visualization Course - T. Alan Keahey -www.visintuit.com
Common solutions to graphing large networks
User Interaction
Focus + Context
Applications for Focus + Context
•
•
•
•
•
Visualization of Networks/Graphs
Viewing text
Image/Document viewing
Cartography
Cluster Visualization
Visualization 2003 - Network Visualization Course - T. Alan Keahey -www.visintuit.com
Common solutions to graphing large networks
User Interaction
Focus + Context
Types of Focus + Context
• Spatial
– One Dimensional
•
Easy to apply and understand
•
Most common, operating on 2D layouts of information
•
Less common
– Two Dimensional
– Three Dimensional
•
Logical
•
•
Combined Spatial and Logical
Data Driven Magnification
– Effect applies to logical structure of the information
Visualization 2003 - Network Visualization Course - T. Alan Keahey -www.visintuit.com
Common solutions to graphing large networks
User Interaction
Focus + Context
Types of Focus + Context
• Spatial
– One Dimensional
•
Easy to apply and understand
•
Most common, operating on 2D layouts of information
•
Less common
– Two Dimensional
– Three Dimensional
•
Logical
•
•
Combined Spatial and Logical
Data Driven Magnification
– Effect applies to logical structure of the information
Visualization 2003 - Network Visualization Course - T. Alan Keahey -www.visintuit.com
Common solutions to graphing large networks
User Interaction
Focus + Context
Types of Focus + Context
• Spatial
– One Dimensional
•
Easy to apply and understand
•
Most common, operating on 2D layouts of information
•
Less common
– Two Dimensional
– Three Dimensional
•
Logical
•
•
Combined Spatial and Logical
Data Driven Magnification
– Effect applies to logical structure of the information
Visualization 2003 - Network Visualization Course - T. Alan Keahey -www.visintuit.com
Common solutions to graphing large networks
User Interaction
Focus + Context
Types of Focus + Context
• Spatial
– One Dimensional
•
Easy to apply and understand
•
Most common, operating on 2D layouts of information
•
Less common
– Two Dimensional
– Three Dimensional
•
Logical
•
•
Combined Spatial and Logical
Data Driven Magnification
– Effect applies to logical structure of the information
Visualization 2003 - Network Visualization Course - T. Alan Keahey -www.visintuit.com
Common solutions to graphing large networks
User Interaction
Focus + Context
Types of Focus + Context
• Spatial
– One Dimensional
•
Easy to apply and understand
•
Most common, operating on 2D layouts of information
•
Less common
– Two Dimensional
– Three Dimensional
•
Logical
•
•
Combined Spatial and Logical
Data Driven Magnification
– Effect applies to logical structure of the information
Visualization 2003 - Network Visualization Course - T. Alan Keahey -www.visintuit.com
Common solutions to graphing large networks
User Interaction
Focus + Context
Types of Focus + Context
• Spatial
– One Dimensional
•
Easy to apply and understand
•
Most common, operating on 2D layouts of information
•
Less common
– Two Dimensional
– Three Dimensional
•
Logical
•
•
Combined Spatial and Logical
Data Driven Magnification
– Effect applies to logical structure of the information
Visualization 2003 - Network Visualization Course - T. Alan Keahey -www.visintuit.com
Example of MoireGraph
http://www.cse.msstate.edu/~tjk/publications/papers/tjk-infovis03.pdf
Common solutions to graphing large networks
User Interaction
Focus + Context
Hyperbolic Browser:
– Hyperbolic plane is used to show the structure.
John Lamping and Ramana Rao - The Hyperbolic Browser : A Focus 1 Context Technique
for Visualizing Large Hierarchies
Common solutions to graphing large networks
User Interaction
Focus + Context Limitations
• Limited degree of magnification?
– 10X Maximum?
– Open research question
• Disorientation
– Complex transformations might cause viewer to get
lost
– Need effective visual cues to avoid this
Visualization 2003 - Network Visualization Course - T. Alan Keahey -www.visintuit.com
Common solutions to graphing large networks
User Interaction
Focus + Context Strengths
• Mirrors the way the visual cortex is designed
• Good navigation tool for interactively exploring
data
– probe regions of interest before committing to
navigating to them (easily reversible)
• Can be combined with other viewing paradigms
such as Pan and Zoom
Visualization 2003 - Network Visualization Course - T. Alan Keahey -www.visintuit.com
Common solutions to graphing large networks
User Interaction
Focus + Context Alternatives
• Pan&Zoom
– Scales to high factors
– Navigation can be a problem
• Multiple views at different scales
– No distortion between scales
– No continuity either
Visualization 2003 - Network Visualization Course - T. Alan Keahey -www.visintuit.com
Common solutions to graphing large networks
User Interaction
Conclusion
Querying
Selection and linking
Varying plot characteristics
Focus + Context
Pan & Zoom
Multiple Views at Varying Scales
Outline
1. Common solutions to graphing networks?
2. Visualization Geometry
3. Inner Sphere 3D Visualization of Internet Topology
4. Issues with Method, Conclusion and Future Work
Visualization Geometry
Euclidean Geometry
Non-Euclidean Geometry
Visualization Geometry
Euclidean Geometry
Normal geometry was name after Euclid, a Greek mathematician
around 300 B.C.
Visualization Geometry
Euclidean Geometry
He wrote a book called “The Elements”.
The book talked about many things
including points, lines, and planes.
Visualization Geometry
Euclidean Geometry
He had several postulates. His 5th postulate was
If a line segment intersects two straight lines forming two
interior angles on the same side that sum to less than two
right angles, then the two lines, if extended indefinitely, meet
on that side on which the angles sum to less than two right
angles.
Visualization Geometry
Euclidean Geometry
Playfair’s postulate is equivalent Euclid’s 5th postulate which says that
Within a two-dimensional plane, for any given line ℓ and a
point A, which is not on ℓ, there is exactly one line through A
that does not intersect ℓ
ℓ
A
Visualization Geometry
Non-Euclidean Geometry
A geometry where Euclid’s 5th postulate does not hold is
considered non-Euclidean geometry.
The essential difference of Euclidean and non-Euclidean
geometry can be found in parallel lines (AKA parallel
postulate).
Visualization Geometry
Non-Euclidean Geometry
Spherical (Elliptic) Geometry
PLANE
SPHERE
Visualization Geometry
Non-Euclidean Geometry
Spherical (Elliptic) Geometry
Points are they same they just sit on the sphere
Lines are considered “great circles”
Since they wrap around the sphere like
an equator.
SPHERE
Visualization Geometry
Non-Euclidean Geometry
Spherical (Elliptic) Geometry
Euclid’s 5th postulate does not hold true for elliptic geometry
since for any given line ℓ and a point A, which is not on ℓ, there
is NOT exactly one line through A that does not intersect ℓ.
They all intersect ℓ.
ℓ
A
SPHERE
Visualization Geometry
Non-Euclidean Geometry
Hyperbolic Geometry
In the hyperbolic model, for any given line ℓ and a point A,
which is not on ℓ, there are infinitely many lines through A
that do not intersect ℓ.
This is used to model hyperbolic space.
Visualization Geometry
Conclusion
Euclidean Geometry
Parallel Lines.
Non-Euclidean Geometry
Spherical (Elliptic) Geometry
Hyperbolic Geometry
Outline
1. Common solutions to graphing networks?
2. Visualization Geometry
3. Inner Sphere 3D Visualization of Internet Topology
4. Issues with Method, Conclusion and Future Work
3D Inner Sphere Internet Visualization
Inner Sphere 3D Visualization - Novel approach to internet visualization
Data Collection -- Probing
D
C1
There are over 40,000 Autonomous Systems.
Number of addresses announced to Internet:
2,039,977,920
http://thyme.apnic.net/
A
B
Demo
You have to be sneaky when collecting data.
3D Inner Sphere Internet Visualization
Inner Sphere 3D Visualization - Novel approach to internet visualization
Data Collection – Probing with Planet-Lab
http://www.planet-lab.org/generated/World50.png
3D Inner Sphere Internet Visualization
Inner Sphere 3D Visualization - Novel approach to internet visualization
Data Collection – Alias Resolution
D
D
C1
A
A
C2
B
GOOD
Demo
C1
C2
B
BAD
3D Inner Sphere Internet Visualization
Inner Sphere 3D Visualization - Novel approach to internet visualization
Edge Representation
A
Labels on Edges
Directed Edges
Thickness of Edges
Color of Edge
Shape of Edges
3D Inner Sphere Internet Visualization
Inner Sphere 3D Visualization - Novel approach to internet visualization
Edge Representation
A
B
3D Inner Sphere Internet Visualization
Inner Sphere 3D Visualization - Novel approach to internet visualization
Node Representation
SPHERE
3D Inner Sphere Internet Visualization
Inner Sphere 3D Visualization - Novel approach to internet visualization
Node & Edge Layout and Mapping
The nodes will be laid out and mapped to surface of the sphere.
The edges will connect the nodes and curve with the surface.
Autonomous System (AS) Layouts will be created.
Geographical AS layouts will also be created.
3D Layout Demo
SPHERE
3D Inner Sphere Internet Visualization
Inner Sphere 3D Visualization
Why use the inside of a sphere to visualize the internet?
3D Inner Sphere Internet Visualization
Inner Sphere 3D Visualization
Why use the inside of a sphere to visualize the internet?
Focus+Context can be maintained by bending light.
Occlusion can be minimized through bending light.
Bending Light
3D Inner Sphere Internet Visualization
Inner Sphere 3D Visualization
Why use the inside of a sphere to visualize the internet?
Photographers have
bent light to capture
more information in
less space.
360 degree panorama
shows the bending of
light.
Baqıp çıquvda resim büyükligi: 800 × 533 piksel
Tam çezinirlik (3.000 × 2.000 piksel, fayl büyükligi: 1,06 MB, MIME çeşiti: image/jpeg)
3D Inner Sphere Internet Visualization
Inner Sphere 3D Visualization
Why use the inside of a sphere to visualize the internet?
VS
Minimize occlusion!!!
3D Inner Sphere Internet Visualization
Inner Sphere 3D Visualization
User Interaction – User Point of View
Focus of User
User
Observer is placed on the inside of the spherical plane.
3D Inner Sphere Internet Visualization
Inner Sphere 3D Visualization
User Interaction – User Point of View
This allows observer to have focus and context.
3D Inner Sphere Internet Visualization
Inner Sphere 3D Visualization
User Interaction – Navigation through the Network
The change of focus and navigation of the network occurs by
moving the sphere as the observer remains fixed. This is similar to
what happens when a gerbil runs inside a gerbil ball.
3D Inner Sphere Internet Visualization
Inner Sphere 3D Visualization
User Interaction – Interactive Zoom
Zooming retains the context by bending the structure of the sphere
towards the user’s point of view.
User’s view of focus
Zoom causes the inside of the sphere to bend towards the user.
3D Inner Sphere Internet Visualization
Inner Sphere 3D Visualization
User Interaction – Interactive Zoom preserves context
Movie 1
Movie 2
Movie 3
3D Inner Sphere Internet Visualization
Inner Sphere 3D Visualization
User Interaction – Node Information
AS16 LBL - University of California
IP 100.100.100.100
AS Neighboring: 1280
3D Inner Sphere Internet Visualization
Inner Sphere 3D Visualization
User Interaction – Animated Transitions
3D Layout Demo
Zoom into a node and discover that each AS node houses another topology.
3D Inner Sphere Internet Visualization
Conclusion
Use the inside of a sphere.
Focus+Context can be maintained by bending light.
Layout
Autonomous System (AS) Layouts will be created.
Geographical AS layouts will also be created.
Mapping
Non-Euclidean Geometry used to map nodes to a sphere
Interactive Zoom
Distorts the sphere to bring objects closer to the viewer
Query
Information about each node can be queried
Animated Transitions
When zooming into a target node, the network of the target node will smoothly enlarge to show it’s topology
Outline
1. Common solutions to graphing networks?
2. Visualization Geometry
3. Inner Sphere 3D Visualization of Internet Topology
4. Issues with Method, Conclusion and Future Work
Issues with Method
Not enough screen pixels even after the sphere mapping.
Non-Euclidean geometry may be slower than Euclidean.
Distortion Zoom may be slow.
File format of the data.
Conclusion & Future Work
I believe this 3D Inner Sphere Visualization will be a better method for
visualizing the internet.
Using a combination of many techniques will enable better focus+context for
huge data sets such as the internet topology.
The process of testing this method is underway.
Future work on how this method can be used to view other types of networks.
Summary Video
References
• Visualization 2003 - Network Visualization
Course - T. Alan Keahey -www.visintuit.com
• Graphics of Large Datasets: Visualizing a
Million -- By Antony Unwin, Martin Theus and
Heike Hofmann
Questions