Complex Networks Lecture 4a: Internet
— Topology and Modeling EE 6605
Instructor: G Ron Chen
Most pictures on this ppt were taken from un-copyrighted websites on the web with thanks
QQ Networking
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)
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:
InternetControlMessageProtocol(ICMP)
File Transfer Protocol (FTP)
Simple Mail Transfer Protocol (SMTP)
Internet is a network of networks
(structure)
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
Internet Exchanges (e.g. HKIX)
through optical fibers (telephone lines)
Submarine Cables in the World
TeleGeography
TeleGeography
Submarine Cables near China
TeleGeography
2017年2月5日
A Real Example
CityU of HK
Sun Yat-sen U Guangzhou
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 (1926-2011)
Donald Davies (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
Vinton Gray Cerf (1943 – )
Robert Elliot Kahn (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
DoD used TCP/IP to inter-connect all networks in 1982, thus the real Internet was considered to be born
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.)
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, a convention, 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), …
DARPA
Earlier History of Internet
Internet today
Data Source
Internet Data
Recent
Internet
Statistics
Internet Data
Recent
Internet
Statistics
Internet Data
Internet Data
Internet
Statistics
Recent
World Population: > 7,796,949,710
Number of Users: > 4,833,521,806 (62%)
Annual global IP traffic was 1.5 ZB per year or 122 EB per month in 2017, which will reach 4.8 ZB per year or 396 exabytes (EB) per month by 2022.
Global IP traffic will increase threefold over the next 5 years, which will reach from 16 GB per capita in 2017 to 50 GB per capita by 2022.
China (in millions): CNNIC Internet Users: 932
iPhone Internet Users: 930 IPv4 Addresses: 386
IPv6 Addresses: 50903 (#1 in world) Domain Names: 2304
Recent
Internet
Statistics
Internet
Websites
Netcraft Websites online right now > 1.7 billion today
Internet Social Media Websites
Internet
Topology
Internet
Internet
It is governed by ICANN
Internet Corporation for Assigned Names and Numbers
Structure
Internet
Applications
Web FTP Mail News Video Audio ping napster
Transport Protocols
TCP
SCTP
UDP
ICMP
IP
Ethernet
802.11
It is governed by ICANN
Power lines ATM Optical Satellite Bluetooth
Link Technologies
Hari Balakrishnan
Internet
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
NSFNET Traffic (1991)
The Internet Topology Zoo
University of Adelaide, Australia
The Internet Topology Zoo is a store of network data created from the information that network operators make public.
As such it is the most accurate large-scale collection of network topologies available, and includes meta- data that couldn’t have been measured.
Traffic within the Data Center
Data Centers in Hong Kong
Energy per bit consumed by 2010-era equipment
Internet Visualization
CAIDA Topology Mapping
1998
(William R. Cheswick)
Internet Visualization
1999
North American Internet Backbone Has 134,855 Routers in 2006 IP addresses (router level)
Growth of the Internet (AS-level)
Growth of the Internet (Hosts)
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 is the director of the World Wide Web Consortium (W3C) and he is also the founder of the World Wide Web Foundation, established at MIT in 1994
A Typical Application Example – Facebook
Mark Zuckerberg
Data Source
www.bbc.co.uk
Facebook Users Distribution
Venezuela
Chile
Turkey Bangladesh
Facebook Users Growth
Data Source
Facebook Revenue Growth
WeChat
Data Source
China Beijing
China Internet Museum
WWW: Social Media
Global Social Media
Facebook YouTube Linkedin
Social Media in China
QQ 腾讯 Weibo 微博 Renren 人人 Kaixin 开心 Youku 优酷 Tudou 土豆
Search Engine Marketing
Google Yahoo! Baidu 百度
Total number of websites
Right Now !
BREAK
10 minutes
AS
–
Level
Internet
Topology
AS = Autonomous Systems FDDI = Fiber Distributed Data Interface
Internet
Internet has more than 50,000 AS today
AS9444:
Hong Kong Telecom
AS24112:
Standard Chartered Bank (HK) Limited
AS4158:
City Univ of Hong Kong
EGP – Exterior Gateway Protocol IGP – Interior Gateway Protocol
Internet at the AS Level
(Steve Uhlig)
Internet at the AS Level
(Steve Uhlig)
Internet: AS and IXP
IXP
IXP = Internet Exchange Point
Internet: AS and IXP
There are > 400 IXPs today, providing services in > 100 countries/regions
Internet Topology Generators
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 data about the AS-level Internet:
Skitter 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
d ~rR
Power law: v v, where d is the degree of node v ,
v
rv is the index of node v in the degree-decreasing
ordering of all nodes, and R 0 is a rank constant exponent.
Internet Hierarchical Structures
Internet consists of a large number of interconnected AS
AS may be considered as a Stub domain or a Transit
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
AS-level Internet structure (Jaiswal et al., 2004)
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
(Cai et al., 2004)
Internet Hierarchical Structures
Degree distribution of the AS-level Internet at different tiers
(Jaiswal et al., 2004)
Multi-Layered Network Structure
Core layer
Distribution layer
Access layer
3-Tier Structure of the CTNET (HK CityU Campus Network, 1985 – )
OCIO Newsletter, Jan 2011
Internet: Some Basic Properties
Rich-Club Phenomenon
In the Internet, a few nodes have a large number of edges, called hubs, and they tend to connect to each other – Rich-club phenomenon – Assortativity
Rich-club phenomenon (Zegura et al., 1997)
Rich-Club Phenomenon
Rich-Club Phenomenon
(Zegura et al., 1997)
Real data have verified that the rich-club index follows nearly a power-law form
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 structure)
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)
Internet is dis-assortative
Assortativity Coefficient of a network is defined by M1jk M11(j k)2
ii2ii rii
M11(j2 k2)M11(j k )2 i 2 i i i 2 i i
where ki and ji
and M is the total number of edges in the network
are the degrees of the end nodes of edge i, If r 0 then the network is assortative (big-big nodes)
if r 0 then the network is dis-assortative (big-small nodes)
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 –
respectively, implying that Internet is overall dis-assortative
0.24
,–
0.19 and – 0.04,
Coreness
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.
(Mahadevan et al., 2005)
Betweenness
(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
Growth of the Internet
Internet is a dynamically evolving complex network, which is rapidly and continuously growing and restructuring
Some historical data of the Internet are examined below, which were provided by
SCAN Project with the software named Mercator
Oregon router services (at the AS level)
Topology Project of the Computer Science Department of the Michigan University (at the Extended AS level)
Growth of the Internet
AS Numbers
(Data Source)
Growth of the Internet
Comparison
North
America Asia
South
America Australia
Internet Traffic Growth
CDN = Content Delivery Network
Features of the Internet
(Pastor-Satorras and Vespignani, 2004)
Features of the Internet
B. Xiao, et al., Physica A (2009)
Node Evolution of the Internet
(Qin et al., 2002)
Edge Evolution of the Internet
(Vazquez et al., 2002)
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)
Robustness and Fragility of Scale-Free Networks
“Achilles’ heel”
R. Albert, H. Jeong, A. L. Barabasi, Nature, 406, 387-482 (2000)
In Greek mythology, when Achilles was a baby, his mother Thetis took him to the River Styx, which was supposed to offer powers of invulnerability, and dipped his body into the water. But as mother held Achilles by the heel, his heel was not washed over by the water of the magical river. Achilles grew up to be a man of war who survived many great battles. On one day, a poisonous arrow shot at him was lodged in his heel, killing him shortly after.
Corfu, Greece
“Achilles’ heel”
2004 film: TROY 特洛伊
Trojan Hours
Robustness versus Fragility Illustration:
Illustration Example:
(a) Random failures
(b) Intentional attacks
Simulation Example:
Robustness and fragility of ER random-graph and BA scale-free networks: (a) and (c): ER random-graph networks; (b) and (d): BA scale-free networks; squares—random removal of nodes; circles—intentional removal of nodes
S – size of largest subgraph l – average path length
f – fraction of attacks
R. Albert, H. Jeong, A. L. Barabasi,
Nature, 406, 387-482 (2000)
Internet and WWW: Simulation Results
S – size of largest subgraph l – average path length
f – fraction of attacks
R. Albert, H. Jeong, A. L. Barabasi,
Nature, 406, 387-482 (2000) Robustness and fragility of the Internet and WWW against intentional attacks:
(a) and (c): Internet; (b) and (d): WWW squares—random failures, circles—intentional attacks
End