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