Group Study MAE 298
Popular in Course
Popular in Engineering Mechanical & Aero
This 25 page Class Notes was uploaded by Consuelo Herman DDS on Tuesday September 8, 2015. The Class Notes belongs to MAE 298 at University of California - Davis taught by Staff in Fall. Since its upload, it has received 30 views. For similar materials see /class/187472/mae-298-university-of-california-davis in Engineering Mechanical & Aero at University of California - Davis.
Reviews for Group Study
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/08/15
MAE 298 Lecture 12 Feb 25 2008 K Qz wquot L J quot 1 Flow on realworld networks II Topics o Optimal allocation of facilities and transport networks Michael Gastner SFI and Mark Newman U Mich 0 Network flows on road networks User vs System Optimal ll Braess Paradox Michael Zhang UC Davis Scale invariance in road networks Kalapala Sanwalani Clauset Moore UNMSFI o Layered interacting networks Kurant and Thiran EPFL Last time Optimal design of spatial distribution systems Download Gastnerpdf Today Flow on transportation networks Download Zhangppt Nash equilibrium versus optimal Pareto optimum Prisoner s Dilemma Cooperate Defect Cooperate 3 3 O 5 Defect 5 O 1 1 0 Blue CooperatesRed Cooperates Blue gets payout 3 0 Blue CooperatesRed Defects Blue gets 0 0 Blue DefectsRed Defects Blue gets 1 0 Blue DefectsRed Cooperates Blue gets 5 Average expected payout for defect is for cooperate is 15 Blue always chooses to Detect Likewise Red always chooses Defect Both defect and get 1 Nash even though each would get a higher payout of 3 if they cooperated Pareto Braess Paradox Dietrich Braess 1968 Currently Prof of Math at Ruhr University Bochum Germany a In a useroptimized network when a new link is added the change in equilibrium flows might result in a higher cost implying that users were better off without that link o Recall Zhang notation qw is overall traffic demand from node 239 to j taya is travel cost along link a which is a function of total flow that link Va Getting from 1 to 4 Assume traffic demand q14 6 Originally 2 paths ac and bd o taza 101a o tczC 11 50 MW Vb 50 tdltVdgt low gt Eqm 1 3 on each link 010283 Add new link Withte1e 15 10 Nowthree paths Path 3 a e d with 14 0 initially so 03 0 10 0 10 03 lt 02 and 01 so new equilibrium needed o By inspection shift one unit of flow form path 1 and from 2 respectively to path 3 0 Now all paths have flow f1 f2 f3 2 o Link OW39la 414 21C 2 yd 4145 2 ta40tb52 tc52td40te12 Cltatc92Cgtbtd92Cgtatetd92 o 92 gt 83 so just increased the travel cost Braess paradox Realworld examples from httpsupernetsomumassedufactsbraesshtml o 42nd street closed in New York City Instead of the predicted traffic gridlock traffic flow actually improved 0 A new road was constructed in Stuttgart Germany traffic flow worsened and only improved after the road was torn up Braess Paradox Applications to Internet traffic Greg Valiant Tim Roughgarden Eva Tardos eg Braess s paradox in large random graphs Proceedings of the 7th ACM conference on Electronic commerce 2006 o Removing edges from a network with selfish routing can decrease the latency incurred by traffic in an equilibrium flow a With high probability as the number of vertices goes to infinity there is a traffic rate and a set of edges whose removal improves the latency of traffic in an equilibrium flow by a constant factor a Braess paradox found in random networks often not just classic 4node construction Braess paradox depends on parameter choices a Classic 4node Braess construction relies on details of 114 and the link travel cost functions ti o The example works because for small overall demand 114 links a and d are cheap The new link 6 allows a path connecting them o If instead demand large eg Q14 60 now links a and d are costly ta td 600 while tb tc 110 The new path aed will always be more expensive so we 0 No traffic will flow on that link So Braess paradox does not arise for this choice of parameters How to avoid Braess Back to Zhang presentation typically solve for optimal flows numerically using computers Can test for a range of choices of traffic demand and link costs lt IOU IOITITITI Our modern infrastructure Layered interacting networks EOOmr m I Layered complex networks M Kurant and P Thiran Layered Complex Networks Phys Rev Lett 89 2006 o Offer a simple formalism to think about two coexisting network topologies The physical topology 0 And the virtual application topology Example 1 WWW and IP layer views of the Internet a Each WWW link virtually connects two IP addresses a Those two IP nodes are typically far apart in the underlying IP topology so the virtual connection is realized as a multihop path along IP routers o Of course the IP network is then mapped onto the physical layer of optical cables and routers The Internet hourglass Applications Video Audio 39 ping As Transport protocols Boproute TCP SCTP UDP CMP TraceRoutequot Routerevegt Ethernei 8021 Powerline 39 Bluetooth Link technologies picture from David Alderson Example 2 Transportation networks Up until now separate studies of 1 Physical topology of roads 2 Reallife traffic patterns Want a comprehensive view analyzing them both together The multilayer formalism Consider two different networks 0 G W5 E the physical graph a GA VA EA the logicalapplicationlayer graph Assume both sets of nodes identical W5 VA o The logical edges are made of a collection of physical edges Megt is a mapping of logical onto physical edges The load on a node a Load on node z39 lz is the sum of the weights of all logical edges whose paths traverse 239 o Eg in a transportation network lz is the total amount of traffic that flows through node 239 Here G is physical connection eg road rail line GA logical is the actual flow Application Study three transportation systems 1 Mass transit system of Warsaw Poland city 2 Rail network of Switzerland country 3 Rail network of major trains in the EU continent Physical graph o Logical graph They can estimate the real load from the timetables some assumptions decompose into units one train one bus etc independent of number of people Physical versus logical Physical o exponentially decaying degree distributions Diameter N W Logical 0 Right skewed degree distributions o Shorter shortest paths eg number of transfers Load They can estimate the real load from the timetables some assumptions decompose into units one train one bus etc independent of number of people Two typical load estimators 1 The node degree of the physical network 2 Betweenness of the physical network Note these estimators are the ones currently in use in almost all cases 1 Resilience of networks to edge removal 2 Modeling cascading failures etc Findings M Kurant and P Thiran Layered Complex Networks Phys Rev Lett 89 2006 o All three estimators 1 real load 2 degree 3 betweenness differ from oneanother o Using the twolayer view can see the logical graphs may have radically different properties than the physical graphs a May lead to reexamination of network robustness previous studies on Internet power grid etc based on physical layer Additional References Follow up a M Kurant P Thiran and P Hagmann Error and Attack Tolerance of Layered Complex Networks Phys Rev E Vol 762007 Multilayer systems much more vulnerable to error and intentional attack than they seem from singlelayer perspective a M Kurant and P Thiran Extraction and analysis of traffic and topologies of transportation networks Phys Rev E Vol 74 2006 David Aldous o Flows through random networks a Spatial Transportation Networks with Transfer Costs Asymptotic Optimality of Hub and Spoke Models More flows o Flows of material goods selforganization Helbing et al a Jamming and flow phase transitions Nishinari Liu Chayes Zeohina
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'