Lecture 19: Advanced Models for Technological Systems ESD. 342 April 15, 2010p , © 2007 Chris Magee, Engineering Systems Division, Massachusetts Institute of TechnologyLecture 19 outlineLecture 19 outline Internet model by Doyle et aly y Power laws and distributions Air transport by Guimera et al Air transport by Guimera et al Future Research suggestions Organizational Design issues Organizational Design issues © 2007 Chris Magee, Engineering Systems Division, Massachusetts Institute of Technologyt tHeuristic Internet Design Note that throughout this lecture we are referring to the autonomous Internet not the worldwide web which is “carried ” th Iupon” the Internet. Heuristic Internet Design Fabrikant et. al Doyle et al. (required reading) Fabricant et. al. attempt to balance the “last mile costs” and the communication distance in a growing system (the internet). They use (and were the originators) of the already seen They noted (as did Gastner and Newman) the transition between MST and star for this case but unfortunately focused on the ease © 2007 Chris Magee, Engineering Systems Division, Massachusetts Institute of Technology of obtaining power laws (and got caught by the “scale-free virus” that was particularly active at the time)t t tttHeuristic Internet Design b Doyle et al. spend much of their time correcting the previous over-emphasis on power-laws as an indicator of structure. We i l di d th ti d ill i l h ipreviously discussed that correction and will mainly emphasize their “First-Principles Approach” to the Internet router- level design problem. F th i “Fi Pi i l ” A h D l l i l For their “First-Principles” Approach, Doyle et. al. start simple and attempt “to identify some minimal functional requirements and physical constraints needed to develop simple models that are consistent with engineering reality” They also focusthat are consistent with engineering reality . They also focus on single ISP’s as the fundamental building block. They argue that the best candidates for a minimal set of constraintson topology construction (architecture) for a constraints on topology construction (architecture) for a single ISP are: Router technology and Network economics © 2007 Chris Magee, Engineering Systems Division, Massachusetts Institute of Technology Network economicsHeuristic Internet Design c-Router Technology LimitsTechnology Limits Doyle et al point out that for a given router there is a limit on the number of packets that can be processed in any given time. This limits the number of connections and connection speeds and creates a “feasible region” and “efficient frontier” for given router designs © 2007 Chris Magee, Engineering Systems Division, Massachusetts Institute of TechnologytHeuristic Internet Design e-Economic ConstraintsEconomic Constraints Costs of installing and operating physical links can dominate the cost of the infrastructure so the availability of multiplexing d ti th h th hi h i ti land aggregating throughout the hierarchy is essential These technologies are deployed depending upon customer needs and willingness to pay © 2007 Chris Magee, Engineering Systems Division, Massachusetts Institute of TechnologyHeuristic Internet Design f: Heuristically Optimal Networksyp Doyle et al define a heuristically optimal network: They also show that several real Internet network elements have these broad characteristics (Abilene and CENIC) Note the “hierarchical tree” in the quote above would actually be better described by the Gastner-Newman model covered in lecture 17 ( a modified MST arrived at by a “growth rule” fll d b th ISP) followed by the ISP). © 2007 Chris Magee, Engineering Systems Division, Massachusetts Institute of TechnologyHeuristic Internet Design g: Properties and designs evaluatedProperties and designs evaluated Performance Th h t Throughput Router utilization ( distance to frontier) End user bandwidth Distribution End user bandwidth Distribution Robustness to attack They constructed a set of Toy Models to illustrate some of their points about the illustrate some of their points about the superiority of “constrained” vs. “freely-grown” structures/topologies. © 2007 Chris Magee, Engineering Systems Division, Massachusetts Institute of Technology g / p gDegree Distributions- from lecture 7 Define as the fraction of nodes in a network with degree k. This is equivalent to the kpprobability of randomly picking a node of degree k A plot of can be formed by making a kp A plot of can be formed by making a histogram of the degrees of the nodes. This is the degree distribution of the network. kp Histograms Normal (and nearly so) Skewed (and heavily skewed) Skewed (and heavily skewed) Suggest some normal or nearly normal distributions..and some not likely to be normal © 2007 Chris Magee, Engineering Systems Division, Massachusetts Institute of TechnologyDegree Distributions II Define as the fraction of nodes in a network with degree k. This is equivalent to the probability of randomly picking a node of degree k kpnode of degree k A plot of can be formed by making a histogram of the degrees of the nodes. This is the degree distribution of the network kpthe network. Histograms Normal (and nearly so) Sk d ( d h il k d) Skewed (and heavily skewed) Reasons for normal vs. skewed? Power law (skewed) Why power laws? α−kpk ~ © 2007 Chris Magee, Engineering Systems Division, Massachusetts Institute of Technology Why power laws?Power laws are ubiquitousLowvariabilityHighvariabilityGaussianExponentiPower lawpalCentral Marginalization CLTLimitTheorem(CLT)g(Markov property)MarginalizationMaximizationMixturesi b h l G i 2004© 2007 Chris Magee, Engineering Systems Division, Massachusetts Institute of Technology(CLT)MixturesFrom seminar by John Doyle at GT in Nov. 2004Heuristic Internet Design g: Properties and designs evaluatedProperties and designs evaluated Performance Throughput Router utilization ( distance to frontier) End user bandwidth Distribution End user bandwidth Distribution Robustness to attack They constructed a set of Toy Models to illustrate some of their points about the superiority
View Full Document
Unlocking...