Actions

Difference between revisions of "Networks and Navigation - Agenda"

From Santa Fe Institute Events Wiki

(Wednesday, August 6, 2008)
m (tweaks to formatting)
Line 20: Line 20:
 
:: 9:00am - 12:00pm '''Science'''
 
:: 9:00am - 12:00pm '''Science'''
  
Aaron: Hierarchical structure of networks
 
  
Hierarchical organization -- where nodes connect together in
+
::'''Aaron''': Hierarchical structure of networks
groups, and these into groups-of-groups, etc. -- is believed to 
 
characterize the structure of many real-world networks. Here I'll 
 
briefly introduce and summarize a simple generative model of 
 
hierarchical structure, an algorithm for inferring it from real-world 
 
data, and a few quick applications of the model.
 
  
Zoltan: On realizing all simple graphs with a given degree sequence
+
::: Hierarchical organization -- where nodes connect together in groups, and these into groups-of-groups, etc. -- is believed to  characterize the structure of many real-world networks. Here I'll briefly introduce and summarize a simple generative model of  hierarchical structure, an algorithm for inferring it from real-world data, and a few quick applications of the model.
  
We give a necessary and sufficient condition for a sequence of nonnegative
+
::'''Zoltan''': On realizing all simple graphs with a given degree sequence
integers to be realized as a simple graph's degree sequence such that a
 
given (but otherwise arbitrary) set of possible connections from a node
 
are avoided.  We then use this result to present a procedure that builds
 
all simple graphs realizing a given degree sequence.
 
  
and Zoltan continues:
+
:::We give a necessary and sufficient condition for a sequence of nonnegative integers to be realized as a simple graph's degree sequence such that a given (but otherwise arbitrary) set of possible connections from a node are avoided.  We then use this result to present a procedure that builds all simple graphs realizing a given degree sequence.
  
Graph structure induced bottlenecks in packet-switching networks
+
::'''Zoltan''': Graph structure induced bottlenecks in packet-switching networks
 +
 
 +
:::We consider the effect of network topology on the optimality of packet routing which we define as  g_c, the rate of packet insertion beyond which congestion and queue growth occurs. We show that for any network, there exists an absolute upper bound, expressed in terms of graph vertex separators, for the scaling of g_c with network size N, irrespective of the static routing protocol used. We then derive an estimate to this upper bound for scale-free networks, and introduce a static routing protocol, the "hub avoidance protocol" which, for large packet insertion rates, is superior to the shortest path routing protocol.
  
We consider the effect of network topology on the optimality of packet
 
routing which we define as  g_c, the rate of packet insertion beyond
 
which congestion and queue growth occurs. We show that for any network,
 
there exists an absolute upper bound, expressed in terms of graph vertex
 
separators, for the scaling of g_c with network size N, irrespective of
 
the static routing protocol used. We then derive an estimate to this
 
upper bound for scale-free networks, and introduce a static routing
 
protocol, the ``hub avoidance protocol'' which, for large packet insertion
 
rates, is superior to the shortest path routing protocol.
 
  
 
:: 12:15pm - 1:00pm '''Lunch'''
 
:: 12:15pm - 1:00pm '''Lunch'''
Line 55: Line 38:
 
:: 1:00pm - 5:00pm '''Science'''
 
:: 1:00pm - 5:00pm '''Science'''
  
Aaron:  How do networks become navigable?
 
  
Networks such as the World Wide Web and the human social  
+
::'''Aaron''': How do networks become navigable?
network exhibit the property of local navigability, i.e., not only do
 
short paths exist between pairs of nodes, but these paths can be found
 
without resort to global information. Kleinberg's work on the
 
generalized Watts-Strogatz "small world" model gave us one example of
 
what kind of structure can give rise to this local navigability
 
property, but gave no hints about whether a natural mechanism might
 
produce it dynamically. I'll briefly summarize a model of dynamic
 
rewiring on Kleinberg networks, based on the notion of users
 
navigating the existing topology, that self-organizes to the optimally 
 
locally navigable structure.
 
  
Marian: Efficient navigation in complex networks
+
:::Networks such as the World Wide Web and the human social network exhibit the property of local navigability, i.e., not only do  short paths exist between pairs of nodes, but these paths can be found without resort to global information. Kleinberg's work on the generalized Watts-Strogatz "small world" model gave us one example of what kind of structure can give rise to this local navigability property, but gave no hints about whether a natural mechanism might produce it dynamically. I'll briefly summarize a model of dynamic rewiring on Kleinberg networks, based on the notion of users navigating the existing topology, that self-organizes to the optimally locally navigable structure.
  
Routing information through networks is a universal phenomenon in both
+
::'''Marian''': Efficient navigation in complex networks
natural and manmade complex systems. When each node has full knowledge
 
of the global network connectivity, finding short communication paths
 
is merely a matter of distributed computation.  However, in many real
 
networks nodes communicate efficiently even without such global intelligence.
 
Here we show that the peculiar structural characteristics of observable
 
complex networks are exactly the characteristics needed to maximize their
 
communication efficiency without global knowledge.  We also describe a
 
general mechanism that explains this connection between network structure
 
and function. This mechanism relies on the presence of a metric space
 
hidden behind an observable network.  Our findings suggest that real
 
networks in nature have underlying metric spaces that remain undiscovered.
 
Their discovery would have practical applications ranging from routing
 
in the Internet and searching social networks, to studying information
 
flows in neural, gene regulatory networks, or signaling pathways.
 
  
 +
:::Routing information through networks is a universal phenomenon in both natural and manmade complex systems.  When each node has full knowledge of the global network connectivity, finding short communication paths is merely a matter of distributed computation.  However, in many real networks nodes communicate efficiently even without such global intelligence. Here we show that the peculiar structural characteristics of observable complex networks are exactly the characteristics needed to maximize their communication efficiency without global knowledge.  We also describe a general mechanism that explains this connection between network structure and function. This mechanism relies on the presence of a metric space hidden behind an observable network.  Our findings suggest that real networks in nature have underlying metric spaces that remain undiscovered. Their discovery would have practical applications ranging from routing in the Internet and searching social networks, to studying information flows in neural, gene regulatory networks, or signaling pathways.
  
  
Line 97: Line 56:
 
:: 9:00am - 12:00pm '''Science'''
 
:: 9:00am - 12:00pm '''Science'''
  
Routing in the Internet and Navigability of Scale-Free Networks
 
  
The Internet has become an integral part of the ubiquitous
+
::'''Dima''': Routing in the Internet and Navigability of Scale-Free Networks
information infrastructure of the modern society. But its global
+
 
scale comes with a price: to route information packets from a given
+
:::The Internet has become an integral part of the ubiquitous information infrastructure of the modern society. But its global scale comes with a price: to route information packets from a given source to a given destination, routers maintain and constantly update an almost full view of the shortest (policy-constrained) paths in the global network topology. This maintenance involves immense computation and information processing overhead, and has recently been widely recognized as one of the biggest scalability problems in the Internet.
source to a given destination, routers maintain and constantly
+
 
update an almost full view of the shortest (policy-constrained) paths
+
:::In this talk we focus on the question if routing (or targeted information propagation) can be efficient in the Internet and networks alike without any global knowledge of the network topology. In other words we are interested if the Internet and other complex networks are navigable -- we say that a network is navigable if some simple routing strategies based only on local information available to a node are efficient. Such local information can be nodes' coordinates in some hidden metric spaces, and then nodes can route "greedily" by forwarding information to their neighbors closest to the destination in the hidden space. We show that if these spaces are hyperbolic, then networks built upon them naturally acquire scale-free node degree distributions and strong clustering. The topology of these networks are thus surprisingly similar to the topologies of real networks, including the Internet. Moreover, their navigability properties are essentially best possible: almost all greedy routes reach their destinations and follow the shortest paths in the network.
in the global network topology. This maintenance involves immense
 
computation and information processing overhead, and has recently
 
been widely recognized as one of the biggest scalability problems
 
in the Internet.
 
  
In this talk we focus on the question if routing (or targeted
+
::'''Filipo''':  @@ (he didn't answer)
information propagation) can be efficient in the Internet and
 
networks alike without any global knowledge of the network topology.
 
In other words we are interested if the Internet and other complex
 
networks are navigable -- we say that a network is navigable if some
 
simple routing strategies based only on local information available
 
to a node are efficient. Such local information can be nodes'
 
coordinates in some hidden metric spaces, and then nodes can route
 
"greedily" by forwarding information to their neighbors closest to
 
the destination in the hidden space. We show that if these spaces
 
are hyperbolic, then networks built upon them naturally acquire
 
scale-free node degree distributions and strong clustering. The
 
topology of these networks are thus surprisingly similar to the
 
topologies of real networks, including the Internet. Moreover, their
 
navigability properties are essentially best possible: almost all
 
greedy routes reach their destinations and follow the shortest paths
 
in the network.
 
  
Filipo:  @@ (he didn't answer)
 
  
 
:: 12:15pm - 1:00pm '''Lunch'''
 
:: 12:15pm - 1:00pm '''Lunch'''
Line 133: Line 70:
 
:: 1:00pm - 5:00pm '''Science'''
 
:: 1:00pm - 5:00pm '''Science'''
  
Fragkiskos:  @@  (will ask him)
 
  
Srinivas:  Evolution of the Internet AS-Level Ecosystem
+
::'''Fragkiskos''':  @@  (will ask him)
 +
 
 +
::'''Srinivas''':  Evolution of the Internet AS-Level Ecosystem
  
We present an analytically tractable model of Internet evolution at the
+
:::We present an analytically tractable model of Internet evolution at the level of Autonomous Systems (ASs). We call our model the Multiclass Attraction (MA) model. All of  its parameters are measurable based on available Internet topology data. Given the estimated values of these parameters, our analytic results accurately predict a definitive set of statistics characterizing the AS topology structure. These statistics are not part of model formulation. The MA model thus closes the ???measure-model-validate-predict??? loop. We  develop our model in stages, adding increasing detail characterizing dynamic interaction between Internet ecosystem players. We validate each stage using recent results in Internet topology data analysis. We describe the emergence of ASs, peering links formation, bankruptcies and multihoming. Our model also explains how certain circumstances naturally lead to consolidation of providers over time, unless some exogenous force interferes.
level of Autonomous Systems (ASs). We call our model the Multiclass
 
Attraction (MA) model. All of  its parameters are measurable based on
 
available Internet topology data. Given the estimated values of these
 
parameters, our analytic results accurately predict a de???nitive set
 
of statistics characterizing the AS topology structure. These statistics
 
are not part of model formulation. The MA model thus closes the
 
???measure-model-validate-predict??? loop. We  develop our model in
 
stages, adding increasing detail characterizing dynamic interaction
 
between Internet ecosystem players. We validate each stage using recent
 
results in Internet topology data analysis. We describe the emergence
 
of ASs, peering links formation, bankruptcies and multihoming. Our model
 
also explains how certain circumstances naturally lead to consolidation
 
of providers over time, unless some exogenous force interferes.
 
  
kc: top ten things i've learned about internet infrastructure economics
+
::'''kc''': top ten things i've learned about internet infrastructure economics
  
 
===Wednesday, August 6, 2008===
 
===Wednesday, August 6, 2008===
Line 160: Line 85:
 
:: 9:00am - 12:00pm '''Science'''
 
:: 9:00am - 12:00pm '''Science'''
  
open questions: folks add questions to discuss here.
 
  
(1) what are the most important things to understand about the Internet
+
::open questions: folks add questions to discuss here.
as a complex system?
+
 
 +
:::(1) what are the most important things to understand about the Internet as a complex system?
 +
:::(2) how navigable is the Internet? if we removed BGP and OSPF, could a "local" strategy work?
 +
:::(3) [your question here]
 +
 
  
 
:: 12:15pm - 1:00pm '''Lunch'''
 
:: 12:15pm - 1:00pm '''Lunch'''
  
 
:: 1:00pm - 2:00pm '''Wrap up'''
 
:: 1:00pm - 2:00pm '''Wrap up'''

Revision as of 05:49, 24 July 2008

Working Group Navigation


Networks and Navigation Working Group, August 4-6, 2008, Santa Fe NM

Joint with UCSD's Cooperative Association for Internet Data Analysis

Organizers: Aaron Clauset (SFI), Dmitri Krioukov (CAIDA), kc claffy (CAIDA) and Cris Moore (UNM & SFI)


Sunday, August 3, 2008

7:00pm Welcome dinner (Railyard)

Monday, August 4, 2008

8:30am - 9:00am Breakfast (Santa Fe Institute)
9:00am - 12:00pm Science


Aaron: Hierarchical structure of networks
Hierarchical organization -- where nodes connect together in groups, and these into groups-of-groups, etc. -- is believed to characterize the structure of many real-world networks. Here I'll briefly introduce and summarize a simple generative model of hierarchical structure, an algorithm for inferring it from real-world data, and a few quick applications of the model.
Zoltan: On realizing all simple graphs with a given degree sequence
We give a necessary and sufficient condition for a sequence of nonnegative integers to be realized as a simple graph's degree sequence such that a given (but otherwise arbitrary) set of possible connections from a node are avoided. We then use this result to present a procedure that builds all simple graphs realizing a given degree sequence.
Zoltan: Graph structure induced bottlenecks in packet-switching networks
We consider the effect of network topology on the optimality of packet routing which we define as g_c, the rate of packet insertion beyond which congestion and queue growth occurs. We show that for any network, there exists an absolute upper bound, expressed in terms of graph vertex separators, for the scaling of g_c with network size N, irrespective of the static routing protocol used. We then derive an estimate to this upper bound for scale-free networks, and introduce a static routing protocol, the "hub avoidance protocol" which, for large packet insertion rates, is superior to the shortest path routing protocol.


12:15pm - 1:00pm Lunch
1:00pm - 5:00pm Science


Aaron: How do networks become navigable?
Networks such as the World Wide Web and the human social network exhibit the property of local navigability, i.e., not only do short paths exist between pairs of nodes, but these paths can be found without resort to global information. Kleinberg's work on the generalized Watts-Strogatz "small world" model gave us one example of what kind of structure can give rise to this local navigability property, but gave no hints about whether a natural mechanism might produce it dynamically. I'll briefly summarize a model of dynamic rewiring on Kleinberg networks, based on the notion of users navigating the existing topology, that self-organizes to the optimally locally navigable structure.
Marian: Efficient navigation in complex networks
Routing information through networks is a universal phenomenon in both natural and manmade complex systems. When each node has full knowledge of the global network connectivity, finding short communication paths is merely a matter of distributed computation. However, in many real networks nodes communicate efficiently even without such global intelligence. Here we show that the peculiar structural characteristics of observable complex networks are exactly the characteristics needed to maximize their communication efficiency without global knowledge. We also describe a general mechanism that explains this connection between network structure and function. This mechanism relies on the presence of a metric space hidden behind an observable network. Our findings suggest that real networks in nature have underlying metric spaces that remain undiscovered. Their discovery would have practical applications ranging from routing in the Internet and searching social networks, to studying information flows in neural, gene regulatory networks, or signaling pathways.


6:30pm Dinner (Santa Cafe)

Tuesday, August 5, 2008

8:30am - 9:00am Breakfast (Santa Fe Institute)
9:00am - 12:00pm Science


Dima: Routing in the Internet and Navigability of Scale-Free Networks
The Internet has become an integral part of the ubiquitous information infrastructure of the modern society. But its global scale comes with a price: to route information packets from a given source to a given destination, routers maintain and constantly update an almost full view of the shortest (policy-constrained) paths in the global network topology. This maintenance involves immense computation and information processing overhead, and has recently been widely recognized as one of the biggest scalability problems in the Internet.
In this talk we focus on the question if routing (or targeted information propagation) can be efficient in the Internet and networks alike without any global knowledge of the network topology. In other words we are interested if the Internet and other complex networks are navigable -- we say that a network is navigable if some simple routing strategies based only on local information available to a node are efficient. Such local information can be nodes' coordinates in some hidden metric spaces, and then nodes can route "greedily" by forwarding information to their neighbors closest to the destination in the hidden space. We show that if these spaces are hyperbolic, then networks built upon them naturally acquire scale-free node degree distributions and strong clustering. The topology of these networks are thus surprisingly similar to the topologies of real networks, including the Internet. Moreover, their navigability properties are essentially best possible: almost all greedy routes reach their destinations and follow the shortest paths in the network.
Filipo: @@ (he didn't answer)


12:15pm - 1:00pm Lunch
1:00pm - 5:00pm Science


Fragkiskos: @@ (will ask him)
Srinivas: Evolution of the Internet AS-Level Ecosystem
We present an analytically tractable model of Internet evolution at the level of Autonomous Systems (ASs). We call our model the Multiclass Attraction (MA) model. All of its parameters are measurable based on available Internet topology data. Given the estimated values of these parameters, our analytic results accurately predict a definitive set of statistics characterizing the AS topology structure. These statistics are not part of model formulation. The MA model thus closes the ???measure-model-validate-predict??? loop. We develop our model in stages, adding increasing detail characterizing dynamic interaction between Internet ecosystem players. We validate each stage using recent results in Internet topology data analysis. We describe the emergence of ASs, peering links formation, bankruptcies and multihoming. Our model also explains how certain circumstances naturally lead to consolidation of providers over time, unless some exogenous force interferes.
kc: top ten things i've learned about internet infrastructure economics

Wednesday, August 6, 2008

8:30am - 9:00am Breakfast (Santa Fe Institute)
9:00am - 12:00pm Science


open questions: folks add questions to discuss here.
(1) what are the most important things to understand about the Internet as a complex system?
(2) how navigable is the Internet? if we removed BGP and OSPF, could a "local" strategy work?
(3) [your question here]


12:15pm - 1:00pm Lunch
1:00pm - 2:00pm Wrap up