复旦大学：《网络科学导论 Introduction to Network Science》教学课件_8- Modelling networks_image

Network science An English introductory course for undergraduate students Lecturer: Dr. Cong LI ee@ Fudan University Adaptive Networks and Control Lab

Network Science Lecturer: Dr. Cong LI EE @ Fudan University —— An English introductory course for undergraduate students Adaptive Networks and Control Lab

Network Modelling

Network Modelling

To model the Internet topology A model for the Internet topology will: Improve the design of routing protocols Help explain the behavior of traffic Improve the validity of network simulations Estimate the vulnerability to attack Predict the growth of Internet

To model the Internet topology A model for the Internet topology will: • Improve the design of routing protocols • Help explain the behavior of traffic • Improve the validity of network simulations • Estimate the vulnerability to attack • Predict the growth of Internet

Internet Topology Generators Three generations >1980s-No clue Era: Random graph generator Waxman(Er random graph) >1990s- Common sense Era Tier. Transit-Stub >2000s-Power law Era: Structure generator BRITE, Inet(Ba scale-free family) Degree generator

Internet Topology Generators Three generations: 1980s - No clue Era: Waxman (ER random graph) 1990s - Common sense Era: Tier, Transit-Stub 2000s – Power law Era: BRITE, Inet (BA scale-free family) Random graph generator Structure generator Degree generator

First generation of Internet Topology Models 1980s Keyword: random

First generation of Internet Topology Models 1980s Keyword: random

Waxman model 1988 Start with N nodes, randomly distributed At each ste ep. random ick up two nodes u, v, and connect them by an edge with a probability defined as P(u,v)=ae d(u, v)/(B Imax) where d(u, v) is the distance between u and v, Lmax is the largest distance between two nodes How is its similarity with the er model?

Waxman model 1988 • Start with N nodes, randomly distributed. • At each step, randomly pick up two nodes, u, v, and connect them by an edge with a probability defined as – How is its similarity with the ER model? where d(u, v) is the distance between u and v, Lmax is the largest distance between two nodes

Waxman model(cont) 7.588.5 An illustration degree distribution

Waxman model (cont.) An illustration degree distribution

Second generation of Internet Topology Models 1990s Keyword: structure

Second generation of Internet Topology Models 1990s Keyword: structure

Transit-Stub Topology Multi-homed stub 83 Transit Domains Sub domains Stub-Sab edge

Transit-Stub Topology

Transit-Stub Topology Generator Generate all Transit domains Random-graph generation method, each node is a Transit domain Generate nodes in each transit domain random connect these nodes Generate Stubs for each Transit This is similar to above level Randomly select one node from Stub domain and connect this node to transit domain Generate LANs for each Stub This is similar to above level They all have star-shaped structures Connect each lan to a stub domain

Transit-Stub Topology Generator  Generate all Transit domains • Random-graph generation method, each node is a Transit domain. • Generate nodes in each Transit domain, random connect these nodes.  Generate Stubs for each Transit • This is similar to above level • Randomly select one node from Stub domain and connect this node to Transit domain  Generate LANs for each Stub • This is similar to above level • They all have star-shaped structures • Connect each LAN to a Stub domain