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''' | ||
− | |||
− | Hierarchical | + | ::'''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 | |
− | |||
− | |||
− | |||
− | all simple graphs | ||
− | and | + | :::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. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
:: 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 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 | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | 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. | ||
Line 97: | Line 56: | ||
:: 9:00am - 12:00pm '''Science''' | :: 9:00am - 12:00pm '''Science''' | ||
− | |||
− | 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. | ||
− | + | ::'''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''' | ||
− | |||
− | 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 | ||
− | 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''' | ||
− | |||
− | (1) | + | ::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)
Contents
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