Complex Networks:

Lecture 5: Internet: Topology and Modeling

Most pictures on this ppt were taken from

un-copyrighted websites on the web with thanks
 Internet
Internet is a global system of interconnected
computer networks that use the standard Internet
Protocol Suite (TCP/IP) to serve billions of users
worldwide. (Wikipedia)
China Beijing

China Internet Museum

 Internet
• Structure:
➢ Autonomous Systems (AS)
➢ Wide Area Network (WAN)
➢ Metropolitan Area Network (MAN)
➢ Local Area Network (LAN)
• Software:
➢ Transmission Control Protocol (TCP)
➢ Internet Protocol (IP)
➢ Other protocols at the application level:
▪ Internet Control Message Protocol (ICMP)
▪ File Transfer Protocol (FTP)
▪ Simple Mail Transfer Protocol (SMTP)
▪……
 Internet is a network of networks

Internet is the inter-connection of networks:

➢Internet Service Provider (ISP) networks
➢Corporate networks (e.g. Cisco and Microsoft)
➢Campus networks (e.g. CityU)
➢Mobile operator networks (e.g. one2free)
➢Government networks (e.g., [Link])
➢Internet exchanges (e.g. HKIX)
➢… …

Through optical fibers (and telephone lines)

 Internet Topology
• AS-level:
> nodes are domains (Autonomous Systems)
> edges are peering relationships
> modeling: manageable

• Router-level:
> nodes are routers
> edges are one-hop IP connections
> Modeling: partially manageable

• PC-level:
> nodes are PCs, hand-held sets
> edges are optical fibers
> modeling: not manageable
Submarine Cables in the World

TeleGeography
TeleGeography
Submarine Cables near China

TeleGeography
 Capacity of
Optical Fiber Cable

Communication at speed of
1 terabit/second, which
2024 means that 500 movies
could be downloaded within
1 second.

2019年2月12日消息，中国信息通信
科技集团科研人员在国内首次实现
1.06Pbit/s超大容量波分复用及空分
复用的光传输系统实验，可以实现
___________________ 2017年2月5日 一根光纤上近300亿人同时通话。
Internet IP
Applications

Web FTP Mail News Video Audio ping napster

Transport Protocols
TCP SCTP UDP ICMP

IP
It is governed by ICANN

Ethernet 802.11 Power lines ATM Optical Satellite Bluetooth

Link Technologies
Hari Balakrishnan
Internet IP
Internet

It is governed by ICANN
Internet Corporation for Assigned Names and Numbers
Example:
Shenzhen Guangzhou

Sun Yat-sen Univ

Guangzhou

CityU of HK
 IP Addressing
The combination of the four parts
in an IP address (e.g., [Link])
provides (256 x 256 x 256 x 256 = 4.2
billions) possible addresses

Among these 4.2 billion IP addresses in IPv4 protocol, about

600 million are reserved and cannot be used for public routing

This number is not enough for service today Human population 2024:
8.2 billions (82億)
Resolution? → IPv6

But, alternatives and extensions require extensive

hardware and software changes throughout the Internet
 IPv4 Addresses Distribution

（暗网）

As of April 2012
Internet Visualization

CAIDA Topology Mapping

 Internet Visualization

1998
(William R. Cheswick)
1999

North American Internet Backbone Has 134,855 Routers in 2006

IP addresses (router level)
Brief History of the Internet
 Brief History of the Internet
◆ 1968 - DARPA (Defense Advanced Research Projects Agency)
contracts with BBN (Bolt, Beranek & Newman) to create ARPAnet

◆ 1970 - First ARPAnet had 5 Nodes:

UCLA
Stanford
UC Santa Barbara
U of Utah
BBN

DARPA
 Leonard Kleinrock conducted early research in
queuing theory, which proved important in
packet switching, and he later played a leading
role in building and managing the world's first
packet-switched network - ARPAnet

Leonard Kleinrock (1934 - )

1961 MIT PhD Thesis:

Information Flow in Large
Communication Nets
(on queuing theory and
packet-switching networks)
Packet Switching is a digital networking communication
method, which groups all transmitted data – regardless of
their content, type or structure – into blocks, called packets

Paul Baran Donald Davies

(1926-2011) (1924-2000)

The concept of switching small blocks of data was first

explored independently by Paul Baran at the RAND
Corporation in the US and by Donald Davies at the National
Physical Laboratory (NPL) in the UK in the earlier 1960s
Packet Switching
 Vinton Gray Cerf Robert Elliot Kahn
(1943 - ) (1938 - )

TCP (Transmission Control Protocol) was invented

by Vint Cerf and Bob Kahn in 1974, which was split
to TCP and IP (Internet Protocol) in 1978

In 1967-1972, Vint Cerf was a graduate student in Kleinrock’s lab,

working on application level protocols for the ARPAnet (File Transfer
Protocol, Telnet Protocol, etc.)
 In November 1977, Cerf and Kahn performed an experiment:

UCLA ARPANet London Satellite ARPANet UCLA

Data Data
Travelling 94,000 miles
Without losing 1 bit of data

US DoD used TCP/IP to inter-connect all networks in 1982

Since then, the real Internet was considered to be born

 Protocols
• Protocol originates from the Greek word protocollon, which was a piece of paper glued
to a manuscript to describe its contents.

• In computing and communication systems, a protocol is a set of rules or a standard, that

controls the connection and data transfer between endpoints.

• Telecommunication systems:
➢ data interchange protocols at the hardware device level
➢ data interchange protocols at the application program level

• Internet:
➢ Transmission Control Protocol (TCP), for exchanging messages with other Internet points
at the information packet level
➢ Internet Protocol (IP), for sending and receiving messages at the Internet address level
➢ Other protocols: Hypertext Transfer Protocol (HTTP), File Transfer Protocol (FTP), Border
Gateway Protocol (BGP), and Dynamic Host Configuration Protocol (DHCP), ...
 How Internet Works

Every PC has a permanent (or temporary) IP address

TCP/IP offers a second transport layer service:

User Datagram Protocol (UDP)

Applications using TCP refer to data as a stream

Applications using UDP refer to data as a message

TCP calls data a segment and UDP calls its data a packet

The Internet layer views all data as blocks called datagrams

How Internet Works
Hardware

Sender:
Your PC (a client) sends or requests
data from a host system in a local
network, using TCP/IP software
Your request and the data are broken
into packets, and packets travel across
multiple networks and finally are
reassembled at their destinations
Receiver:
Reversing the above process
Software
Encapsulation
Application program

User code data

User Interface (API)

OS code TCP segment

TCP header
data

IP datagram TCP segment OS/adapter interface

IP header header
data
(exception mechanism)

Ethernet frame IP datagram TCP segment

data
header header header Adapter

Adapter/Network interface
Network
 Server

“Bus”

Permanent
IP address

Temporary
IP address
 Typical Local Structures

Ring  Computers
Bus and devices
interconnected
on a single line
Hierarchical every device can
Star communicate
directly to all
devices on bus
Internet
Internet Development
Growth of the Internet (Hosts)
 Recent Internet Statistics

As of July 2024, there were 5.45 billion internet users

worldwide, which is 67.1% of the global population Internet Data
Recent Internet Statistics

millions

January 2025 Internet Data

Top Countries with the Largest Numbers of Internet Users

Data
Recent Internet Statistics

Data
Recent Internet Statistics

World Population: > 8.2 billions

Internet Users: > 5.6 billions (68.7%)

Data: CIW

China (in millions): Data: CNNIC 中國互聯網資訊中心

Internet Users: 1123 (79.7% citizens)
iPhone Internet Users: 1267 (99.9%)
IPv4 Addresses: 3924
IPv6 Addresses: 7940 block/32
Recent Internet Statistics
网民规模和互联网普及率
手机网民及其占网民比例
Penetration rates of leading social media platforms in China

Data
Data
Internet
Topology

USA
Backbone

(2001) Shares in USA:

27.9% - UUNET/WorldCom/MCI
10.0% - AT&T
6.5% - Sprint
6.3% - Genuity
4.1% - PSINet
3.5% - Cable & Wireless
2.8% - XO Communications
2.6% - Verio
1.5% - Qwest
1.3% - Global Crossing

Today: UUNET, Level 3, Verizon, AT&T, Qwest, Sprint, IBM, …

UUNET was founded in 1987: one of the largest Internet service providers and one of the nine Tier-1 networks

ASes typically
connect at all hubs.
China
Hong Kong
TeleGeography
Internet Topology

New comer
Autonomous System (AS)-Level Internet Topology

Fiber Distributed Data Interface

AS-Level
Internet Internet has more than
50,000 AS today

AS9444:
Hong Kong Telecom

AS24112:
Standard Chartered
Bank (HK) Limited

AS4158:
EGP – Exterior Gateway Protocol City Univ of Hong Kong
IGP – Interior Gateway Protocol
Internet: AS and IXP

IXP

IXP = Internet Exchange Point (Data Center)

Internet: AS and IXP
There are > 400 IXPs today, providing services in
> 100 countries/regions
China has 4 largest IXPs
(Beijing 2, Guangzhou 1, Shanghai 1)

World: List of IXPs

Hong Kong IXPs

Data
 Local Network Topologies

• Hierarchical
Tree-like structures with messages passing along
the branches of the hierarchy

• Hybrid
A mixture of different kinds of structured topologies
It is what exactly the whole Internet looks like

• Mobile Ad-hoc Network

Structure is changing dynamically (e.g. iPhones)
Link Prediction

Predict:
Which computer
is likely to
connect to which
computer

Who is likely to be
a friend of whom
 Link Prediction

Predict link(s) from node “B” Predict link(s) from node “F”

Based on:
Degree Similarity, Property Similarity, Importance Similarity, …
Distance Closeness, Relationship Closeness, …
 Predictions

Predict link(s) from node “B” Predict link(s) from node “F”

Degree Similarity Distance Similarity

 Link Prediction
For a large-scale network, this could be challenging
More Applications

NSFNET (1991)
 Wireless Telecommunication

Cellular Transmission
Signals from cells are transmitted to a receiver
and then integrated into the regular network
 5G
5G (5th Generation of communication technology)
of cellular mobile communication systems
It succeeds the 4G (LTE/WiMax), 3G (UMTS) and
2G (GSM) systems
5G performance targets high data rate, reduced
latency, energy saving, cost reduction, higher
system capacity, and massive device connectivity
 6G

Starlink 星鏈
News: China starlink project
will launch 13000 satellites
 WWW
&
Facebook

on
Internet
Sir Timothy John Berners-Lee (1955 - )

Tim Berners-Lee (“TimBL”) developed a hypertext system

with initial versions of HTML and HTTP and first GUI web
browser called World Wide Web in 1990.

Tim Berners-Lee was the founder of the World Wide Web

Foundation, established at MIT in 1994. He was the Director of
the World Wide Web Consortium (W3C). (Stepped down in 2023)
 Internet Search Engines
1. Google
70% of searches were powered by Google
Dominating mobile/tablet search engine market shares with 81%

2. Bing
[Link]
Bing is the default search engine on Windows PCs
7.91% searches were powered by Bing

3. Yahoo (7.68%)

4. [Link] 5. [Link] 6. Baidu 7. Wolframalpha

Data
8. DuckDuckGo 9. Internet Archive 10. [Link]
A Typical Application Example - Facebook

Data
[Link]
Facebook Users in the World
 Facebook Users Distribution

Venezuela

Chile Turkey Bangladesh

Data
WeChat

Data
Social Media Platforms
 Social Media Platforms
Global Social Media
Facebook
YouTube Hong Kong Mobile Internet Users
Linkedin
Social Media in China
QQ 腾讯
Weibo 微博
Renren 人人
Kaixin 开心
Youku 优酷
Tudou 土豆
Search Engine Marketing
Google
Yahoo!
Baidu 百度
Internet Social Media Websites
Internet Websites
Data Centers Growth
Data Centers in Hong Kong
BREAK
10 minutes
 Internet Topology
• AS-level:
> nodes are domains (Autonomous Systems)
> edges are peering relationships
> modeling manageable

• Router-level:
> nodes are routers
> edges are one-hop IP connections
> partially manageable

• PC-level:
> nodes are PCs, hand-held sets
> edges are optical fibers
> modeling not manageable
 Internet Topology Generators (Models)

Three stages of development:

➢ First generation includes: random topology generators

(in 1980s); representative - Waxman generator

➢ Second generation includes: structural topology generators

(in 1990s); representatives - Tiers and Transit – Stub
generators (with hierarchical and community structures)

➢ Third generation (since 2000), based on node degrees;

representatives - BRITE and Inet, small-world and especially
scale-free network models

➢ Open Source: Net2Plan

 Internet Topological Properties and DATA

• Real AS-level Internet data can be

obtained from the website of the
Oregon Router Views Project, which
was managed by the National
Laboratory for Applied Network
Research (NLANR), expired at the
end of 2006, and now managed by
the Cooperative Association for
Internet Data Analysis (CAIDA)

• This website is being updated within

hours daily by taking snapshots from
the routing tables of the Border
Gateway Protocol (BGP)
 Internet Topological Properties
Other useful databases about the AS-level Internet:

➢ Skitter (now Ark) provides Internet topological measures by

the CAIDA, using Traceroute (a computer network tool for
determining the route taken by packets across an IP network.
➢ Whois is a domain search tool and data base, identifying the
owners and IP addresses of all domains, but it is not
automatically managed.
➢ RIPE NCC supports the infrastructure of the Internet and
provides global Internet resources and related services (IPv4,
IPv6 and AS Number resources) in Europe, Middle East and
parts of Central Asia.
 Real AS-Level Internet Data
Example:

Numbers of Internet AS (Nov. 1997 – Feb. 2002)

(Siganos et al., 2003)
Power-Law Node-Degree Distributions

Faloutsos M, Faloutsos P, Faloutsos C.

On power-law relationships of the Internet topology
ACM SIGCOMM Computer Communication Review, 1999, 29(4): 251-262

The Faloutsos Brothers

 Power-Law Node-Degree Distribution

Power law: 𝑑𝑣 ~ 𝑟𝑣𝑅 , where 𝑑𝑣 is the degree of node 𝑣, 𝑟𝑣 is

the index of node 𝑣 in the degree-decreasing ordering of
all nodes, and 𝑅 < 0 is a rank constant exponent.
 Internet Hierarchical Structures
• Internet consists of a large number of interconnected AS

• AS may be considered as a Transit domain or a Stub domain

• Transit domain can be a Metropolitan Area Network (MAN) or

a Wide Area Network (WAN), typically a regional or a national
Internet Service Provider (ISP)

• Stub domain consists of campus networks or some other

interconnected Local Area Networks (LAN)

• Transit domain is used to link many nearby Stub-domains together

• Stub domain usually processes the information starting and ending inside
the domain, while a Transit domain has no such restriction
Internet Hierarchical Structures
Internet Hierarchical Structures

AS-level Internet on 3 December 1998

(generated by Skitter)
 Internet Hierarchical Structures
• AS on the Internet can be considered as some kind of Tier
• An AS at the highest Tier belongs to the Transit domain, called Tier-1 provider

➢ Those Transit
and Stub
domains at a
lower Tier
depend on the
Transit nodes at
a higher Tier to
communicate
with the other
domains at their
same level
Internet Hierarchical Structures

Degree distribution of the AS-level Internet at different tiers

(Jaiswal et al., 2004)
Multi-Layered Network Structure
 3-Tier Structure of the CTNET (CityUofHK Campus Network)

Core
layer

Distribution
layer

Access
layer

OCIO Newsletter, Jan 2011

Internet: Some Basic Properties
Assortativity and Disassortativity

Assortativity Coefficient of a network is defined by

2
 −1 1 
M −1  ji k i −  M  ( ji + k i )
r= i  i 2 
2
1 2  −1 1 
M  ( ji + k i ) −  M  ( ji + k i )
−1 2

i 2  i 2 
where 𝑘𝑖 and 𝑗𝑖 are the degrees of the two end nodes of edge 𝑖,
and 𝑀 is the total number of edges in the network.

If 𝑟 > 0 then the network is assortative (big-big nodes);

if 𝑟 < 0 then the network is disassortative (big-small nodes).

 Assortativity and Disassortativity
In a network, if nodes with large degrees tend to connect to nodes also
with large degrees on average, the network is said to be assortative

but if nodes with large degrees tend to connect to nodes with small
degrees on average, the network is said to be disassortative

Note: Networks with the same assortativity may have different topologies
Statistical Properties of Some Real-World Networks
𝑁 – number of nodes; 𝑀 – number of edges; 𝑘 − average degree;
𝐿 – average path length; 𝛾 – power-law exponent; 𝐶 – clustering coefficient

Mostly assortative
Statistical Properties of Some Real-World Networks

Mostly disassortative
Statistical Properties of Some Real-World Networks

Various types
Rich-Club Structure of the Internet
In the Internet, a few nodes have a large number of edges, called hubs,
and they tend to connect to each other to form a Rich-Club – Assortativity
Rich-Club Structure

coefficient of any

all the degree > k

0 all the degree > k

Example:

For 𝑘 = 2

𝑁>2 = 2, 𝐸>2 = 1

1
➢Φ 2 = =1
2(2−1)/2

“Fully connected” between Nodes 1 and 2

3
➢Φ 1 = =1
3(3−1)/2

“Fully connected” among Nodes 1, 2, 3

 Rich-Club Structure of Internet (AS)

(Zegura et al., 1997)

Real data have verified that the rich-club index

Ф(k) follows nearly a power-law form
 Internet is overall disassortative

Analysis on real data using Skitter, BGP and Whois about

the Internet at some AS levels shows that their assortativity
coefficients of the Internet are – 0.24, – 0.19 and – 0.04
respectively, implying that Internet is overall disassortative

• Internet is assortative at the high level of AS (e.g., Tier-1, rich-club)

• Internet is overall disassortative (globally as a whole network)
 Coreness
2-core

1-core
3-core
0-core
(1) Inside a k-core, every node has degree at least k
(2) The coreness of a network is the highest coreness value,
so the above whole network has coreness 3
 Coreness

• The k-core in a graph is defined to be the remaining sub-graph after all the
nodes with degrees ≤ 𝑘 − 1 have been removed successively, during which:

(i) when a node is removed, all its adjacent edges will also be removed

(ii) after a node of degree ≤ 𝑘 − 1 is removed, in the remaining graph all

the remaining nodes with a new degree ≤ 𝑘 − 1 also need to be removed

➢ If a node belongs to a k-core of a graph, but it will be removed from the

(k+1)-core, then this node is said to have coreness (core value) 𝑘

➢ The largest coreness in a graph is defined to be the coreness of the graph

Examples:
Isolated node has coreness 𝑘 = 0
Fully-connected network of size 𝑁 has coreness 𝑘 = 𝑁 − 1

Star-shaped network
• the 1-core of the network is the network itself
• all nodes, including the centre, have coreness 1
• the coreness of the network is 1

Ring network
• the 2-core of the network is the network itself
• all nodes have coreness 2
• the coreness of the network is 2
Example:

➢ 1-core is the whole graph

➢ 2-core is Triangle 1-2-3
➢ Node 1, Node 2, Node 3 have
coreness 2
➢ Node 4 and Node 5 have
coreness 1
➢ Coreness of the graph is 2
 Coreness of the Internet

(Mahadevan et al., 2005)

Internet data from Skitter, BGP and Whois:
when the node degree is relatively small, they have a power-law relation,
with exponents 0.58, 0.68 and 1.07, respectively;
when the node-degree > 100, their coreness values become saturated.
 Betweenness

Definition 1 (Node-betweennes) In a network of size 𝑁,

the node-betweenness of node 𝑖 is defined by
L jl (i )
B (i ) = 
i  j l L jl
where 𝐿𝑗𝑖 is the number of all existing shortest paths from
node 𝑗 to node 𝑙, and 𝐿𝑗𝑖 (𝑖) is the number of all shortest
paths from node 𝑗 to node 𝑙 that pass through node 𝑖

(since 𝑖 ≠ 𝑗 ≠ 𝑙 the node 𝑖 itself is excluded)

Normalization: divided by total number of node-pairs not

including node 𝑖 as an end node: (𝑁 − 1)(𝑁 − 2)/2
Node-Betweenness

2 5

Example:
3
betweenness of node 1 is
4
 Betweenness
Definition 2 (Edge-betweennes) In a network of size 𝑁, the
edge-betweenness of edge 𝑒𝑖𝑗 is defined by
~
Llq (eij )
B (eij ) =  ~
(l ,q ) (i , j ) L lq

where 𝐿෨ 𝑙𝑞 is the number of all existing shortest paths from

node 𝑙 to node 𝑞, and 𝐿෨ 𝑙𝑞 (𝑒𝑖𝑗 ) is the number of all shortest
paths from node 𝑙 to node 𝑞 that pass through edge 𝑒𝑖𝑗

Normalization: divided by total number of node-pairs not

𝑁 𝑁−1
including edge 𝑒𝑖𝑗 as an end node: 2 − 1
Edge-Betweenness
1

2 5

Example:
betweenness of edge 𝑒12 is
3
4

Normalized:
 Betweenness of the Internet

(Mahadevan et al., 2005)

Internet data from Skitter, BGP and Whois:

For those from Skitter and BGP, their relations follow prominent
power-law distributions with components 1.35 and 1.17, respectively
 Most nodes in the Internet are small
• In the Internet, hubs are well interconnected (rich clubs)
• Most neighbors of a hub typically have small degrees (star-shaped)

Analysis on the Internet

data of April 2002 shows
that nodes with degrees of
1, 2, and 3 were 26%, 38%
and 14%, respectively,
which sums up to about
80% of the whole network
(Zhou and Mondragon, 2004)
(Mahadevan et al., 2005)
Features of the Internet

(Pastor-Satorras and Vespignani, 2004)

Features of the Internet

Not well
matched

B. Xiao, et al., Physica A (2009)

 Scale-Free Internet
P (k ) ~ k −

 = 2.2
 = 2.14 ~ 2.21

(Autonomous Systems level)

Z. P. Fan and G. R. Chen (2005, 2010)
 Road Map vs Airline Routing Map
−
Poisson distribution Power-law distribution p (k ) ~ k

Small-world Network Scale-free Network

(nodes: cities edges: highways) (nodes: airports edges: flights)

Brain and Internet

Any Inspiration ?
 Topology
Brain → Internet

M. Bazhenov et al., J. Neuroscience, 2002 S. I. Cai et al., Proc. IEEE CDC, 2004

IXP (Internet Exchange Point)

 Brain Topology

Small-world
Topology

Community
Structure

D. D. Bock et al., Nature, 2011

D. Krioukov et al., Scientific Report, 2012
 Brain Topology

Brain Internet

J. A. Robert, et al, Neuobiology, 2014 Faloutsos (3 brothers), ACM SIGCOMM, 1999

 Inspiration

Structure:
Layers + Communities
Feature: Small-world
Distribution:
Internet
Power-law with flat head and heavy tail
Social Networks
are typical
Small-World
Networks

Human
mobility and
behaviors both
affect Internet
topological
evolution
Brain Facebook Structure
End