程序代写代做代考 ER gui DHCP html graph FTP Complex Networks Lecture 4a: Internet

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 M1jk M11(j k)2
ii2ii rii
M11(j2 k2)M11(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