Transcript COMP 361, Fall 2000 - cse, hkust - Hong Kong University of Science

Internet Infrastructure:
Switches and Routers
Mounir Hamdi
Head & Chair Professor, Computer Science and Engineering
Hong Kong University of Science and Technology
CSIT560 by M. Hamdi
1
Goals of the Course
• Understand the architecture, operation, and evolution of the Internet
– IP, Optical, Openflow
• Understand how to design, implement and evaluate Internet routers
and switches (Telecom Equipment)
• Understand the implementation of network services (e.g., QoS) on
switches and routers
• Introduction to Network-on-Chip (NoC), Communication Performance,
Organizational Structure, Interconnection Topologies, Trade-offs in
Network Topology, and Routing
• Evaluate various Internet access methods (including wireless)
• Build solid learning skills for investigating a good project
– Task selection and aim
– Survey & conclusion & research methodology
– Presentation
CSIT560 by M. Hamdi
2
Outline of the Course
• The focus of the course is on the design and analysis of highperformance electronic/optical switches/routers needed to support
the development and delivery of advanced network services over
high-speed Internet.
• The switches and routers are the KEY building blocks of the
Internet, and as a result, the capability of the Internet in all its
aspects depends on the capability of its switches and routers
(hardware and software)
• Understand the evaluate the evolution of the Internet infrastructure
(e.g., NoC, Wireless, etc.)
• The goal of the course is to provide a basis for understanding,
appreciating, and performing research/survey and development in
networking with a special emphasis on switches and routers.
CSIT560 by M. Hamdi
3
Outline of the Course
• Introduction
– Evolution of the Internet (Architecture, Protocols and
Applications)
– Evolution of packet switches and routers, basic architectural
components, and some example architectures
– Network Processors and Packet Processing (IPv4 and IPv6)
– Architecture and operation of “optical” circuit-switched
switches/routers
CSIT560 by M. Hamdi
4
Outline of the Course
• High-Performance Packet Switches/Routers
– Architectures of packet switches/routers (IQ, OQ, VOQ,
CIOQ, SM, Buffered Crossbars)
– Design and analysis of switch fabrics (Crossbar, Clos,
shared memory, etc.)
– Design and analysis of scheduling algorithms (arbitration,
shared memory contention, etc.)
– Emulation of output-queueing switches by more practical
switches
– State-of-the-art commercial products
CSIT560 by M. Hamdi
5
Outline of the Course
• Network-on-chip (NoC) Design and Applications
– Introduction to NoC
– Communication Performance, Organizational Structure,
Interconnection Topologies, Trade-offs in Network Topology,
and Routing
– Applications of NoC in network Equipment
– Future trends of this paradigm
CSIT560 by M. Hamdi
6
Outline of the Course
• Quality-of-Service Provision in the Internet
– Internet Congestion Control
– QoS paradigms (IntServ, DiffServ, Controlled load, etc.)
– Flow-based QoS frameworks: Hardware and software
solutions
– Stateless QoS frameworks: RED, WRED, congestion
control, and Active queue management
– MPLS/GMPLS
– Openflow
– State-of-the-art commercial products
CSIT560 by M. Hamdi
7
Outline of the Course
• Optical Networks
– Optical technology used for the design of switches/routers
as well as transmission links
– Dense Wavelength Division Multiplexing
– Optical Circuit Switches: Architectural alternatives and
performance evaluation
– Optical Burst switches
– Optical Packet Switches
– Design, management, and operation of DWDM networks
– State-of-the-art commercial products
CSIT560 by M. Hamdi
8
Outline of the Course
• Internet Wireless Access
– WLANs and 802.11
– WiMAX and 802.16
– Cellular mobile networks
• Performance Evaluation
– Simulations
– Modeling
CSIT560 by M. Hamdi
9
Grading
•
Homework
20%
•
Midterm
40%
•
Project
40%
CSIT560 by M. Hamdi
10
Course project
• Investigate and survey existing advances and/or new
ideas and solutions – related to Internet Infrastrcuture - in
a small scale project (To be given or chosen on your own)
– Define the problem
– Execute the survey and/or research
– Work with your partner
– Write up and present your finding
CSIT560 by M. Hamdi
11
Course Project
• I’ll post on the class web page a list of projects
– you can either choose one of these projects or come up with your
own
• Choose your project, partner (s), and submit a one
page proposal describing:
– The problem you are investigating
– Your plan of project with milestones
• Final project presentation (20-25 minutes)
• Submit project reports
CSIT560 by M. Hamdi
12
Independent Projects
• If you want to go deeper in a topic related to Internet
Infrastructures (e.g., Wireless, Internet Routers, Data
centers, Cloud Computing, Optical, QoS, NoC,
Applications, etc.), then you might want to opt for an
Independent Project
– You can come and talk to me
CSIT560 by M. Hamdi
13
Homework
•
Goals:
1.
Synthesize main ideas and concepts from very important
research or development work
•
I will post in the class web page a list of “well-known/seminal”
papers to choose from
•
Report contains:
1.
Description of the paper
2.
Goals and problems solved in the paper
3.
What did you like/dislike about the paper
4.
How the paper affected the advances in networking (if any)
5.
Recommendations for improvements or extension of the work
CSIT560 by M. Hamdi
14
How to Contact Me
• Instructor: Mounir Hamdi, [email protected]
• TA: Miss. Lu Wang, [email protected]
• Office Hours
– You can come any time – just email me ahead of time
– I would like to work closely with each student
CSIT560 by M. Hamdi
15
Overview and History
of the Internet
CSIT560 by M. Hamdi
16
What is a Communication Network?
(from an end system point of view)
• A network offers a service: move information
– Messenger, telegraph, telephone, Internet …
– another example, transportation service: move objects
• horse, train, truck, airplane ...
• What distinguishes different types of networks?
– The services they provide
• What distinguish the services?
– latency
– bandwidth
– loss rate
– number of end systems
– Reliability, unicast vs. multicast, real-time, message vs. byte ...
CSIT560 by M. Hamdi
17
What is a Communication Network?
Infrastructure Centric View
• Hardware
– Electrons and photons as communication data
– Links: fiber, copper, satellite, WiFI, …
– Switches: mechanical/electronic/optical,
• Software
– Protocols: TCP/IP, ATM, MPLS, SONET, Ethernet, PPP,
X.25, Frame Relay, AppleTalk, Openflow, SNA
– Functionalities: routing, error control, congestion control,
Quality of Service (QoS), …
– Applications: FTP, WEB, X windows, VOIP, IPTV...
CSIT560 by M. Hamdi
18
Types of Networks
• Geographical distance
–
–
–
–
–
Body Area Networks (BAN)
Personal Areas Networks (PAN)
Sensor Networks
Local Area Networks (LAN): Ethernet, Token ring, FDDI
Metropolitan Area Networks (MAN): DQDB, SMDS (Switched Multi-gigabit
Data Service)
– Wide Area Networks (WAN): IP, ATM, Frame relay
• Information type
– data networks vs. telecommunication networks
• Application type
– special purpose networks: airline reservation network, sensor networks,
banking network, credit card network, telephony
– general purpose network: Internet
CSIT560 by M. Hamdi
19
Types of Networks
• Right to use
– private: enterprise networks
– public: telephony network, Internet
• Ownership of protocols
– proprietary: SNA
– open: IP
• Technologies
– terrestrial vs. satellite
– wired vs. wireless
• Protocols
– IP, AppleTalk, SNA
CSIT560 by M. Hamdi
20
The Internet
• Global scale, general purpose, heterogeneoustechnologies, public, computer network
• Internet Protocol
– Open standard: Internet Engineering Task Force (IETF) as
standard body
– Technical basis for other types of networks
• Intranet: enterprise IP network
• Developed by the research community
CSIT560 by M. Hamdi
21
Internet History
1961-1972: Early packet-switching principles
•
•
•
•
1961: Kleinrock - queueing
theory shows effectiveness
of packet-switching
1964: Baran – Introduced first
Distributed packet-switching
Communication networks
1967: ARPAnet conceived
and sponsored by Advanced
Research Projects Agency –
Larry Roberts
1969: first ARPAnet node
operational at UCLA. Then
Stanford, Utah, and UCSB
•
1972:
– ARPAnet demonstrated
publicly
– NCP (Network Control
Protocol) first host-host
protocol (equivalent to
TCP/IP)
– First e-mail program to
operate across networks
– ARPAnet has 15 nodes and
connected 26 hosts
CSIT560 by M. Hamdi
22
Internet History
1972-1980: Internetworking, new and proprietary nets
• 1970: ALOHAnet satellite network
in Hawaii
• 1973: Metcalfe’s PhD thesis
proposes Ethernet
• 1974: Cerf and Kahn architecture for interconnecting
networks (TCP)
• late70’s: proprietary architectures:
DECnet, SNA, XNA
• late 70’s: switching fixed length
packets (ATM precursor)
• 1979: ARPAnet has 200 nodes
Cerf and Kahn’s internetworking
principles:
– minimalism, autonomy - no
internal changes is required
to interconnect networks
– best effort service model
– stateless routers
– decentralized control
define today’s Internet architecture
CSIT560 by M. Hamdi
23
1971-1973: Arpanet Growing
• 1970 - First 2 cross-country link, UCLA-BBN and MIT-Utah,
installed by AT&T at 56kbps
CSIT560 by M. Hamdi
24
Internet History
1980-1990: new protocols, a proliferation of networks
• 1983: deployment of TCP/IP
• 1982: SMTP e-mail protocol
defined
• 1983: DNS defined for nameto-IP-address translation
• 1985: ftp protocol defined
(first version: 1972)
• New national networks:
CSnet, BITnet, NSFnet,
Minitel
• 100,000 hosts connected to
confederation of networks
• 1988: TCP congestion control
CSIT560 by M. Hamdi
25
Internet History
1990’s: commercialization, the WWW
• Early 1990’s: ARPAnet
decomissioned
• 1991: NSF lifts restrictions on
commercial use of NSFnet
(decommissioned, 1995)
• early 1990s: WWW
– hypertext [Bush 1945, Nelson
1960’s]
– HTML, http: Berners-Lee
– 1994: Mosaic, later Netscape
– late 1990’s: commercialization
of the WWW
Late 1990’s:
• est. 50 million computers on
Internet
• est. 100 million+ users in
160 countries
• backbone links running at 1
Gbps+
2000’s
• VoIP, Video on demand,
IPTV, Internet business
• RSS, Web 2.0
• Social networking
CSIT560 by M. Hamdi
26
Internet - Global Statistics
1999
2012
• 32.5 Million Hosts
• 908 Million Hosts
• 80 Million Users
• 1966 Million Users
(approx. 4.6Billion mobile phone users, as of 2010)
CSIT560 by M. Hamdi
Internet Users by World Region
CSIT560 by M. Hamdi
28
Internet Domain Survey Host Count
CSIT560 by M. Hamdi
29
Internet Penetration 2012
CSIT560 by M. Hamdi
30
Top 20: % Internet Use (2012)
#
Country or Region
1
China
2
United States
3
Population,
2012 Est
Internet Users
Year 2000
Internet Users
Latest Data
Penetration
(% Population)
Users
% World
1,343,239,923
22,500,000
538,000,000
40.1 %
22.4 %
313,847,465
95,354,000
245,203,319
78.1 %
10.2 %
India
1,205,073,612
5,000,000
137,000,000
11.4 %
5.7 %
4
Japan
127,368,088
47,080,000
101,228,736
79.5 %
4.2 %
5
Brazil
193,946,886
5,000,000
88,494,756
45.6 %
3.7 %
6
Russia
142,517,670
3,100,000
67,982,547
47.7 %
2.8 %
7
Germany
81,305,856
24,000,000
67,483,860
83.0 %
2.8 %
8
Indonesia
248,645,008
2,000,000
55,000,000
22.1 %
2.3 %
9
United Kingdom
63,047,162
15,400,000
52,731,209
83.6 %
2.2 %
10
France
65,630,692
8,500,000
52,228,905
79.6 %
2.2 %
11
Nigeria
170,123,740
200,000
48,366,179
28.4 %
2.0 %
12
Mexico
114,975,406
2,712,400
42,000,000
36.5 %
1.7 %
13
Iran
78,868,711
250,000
42,000,000
53.3 %
1.7 %
14
Korea
48,860,500
19,040,000
40,329,660
82.5 %
1.7 %
15
Turkey
79,749,461
2,000,000
36,455,000
45.7 %
1.5 %
16
Italy
61,261,254
13,200,000
35,800,000
58.4 %
1.5 %
17
Philippines
103,775,002
2,000,000
33,600,000
32.4 %
1.4 %
18
Spain
47,042,984
5,387,800
31,606,233
67.2 %
1.3 %
19
Vietnam
91,519,289
200,000
31,034,900
33.9 %
1.3 %
20
Egypt
83,688,164
450,000
29,809,724
35.6 %
1.2 %
CSIT560 by M. Hamdi
31
Languages of Internet Users
CSIT560 by M. Hamdi
32
Who is Who on the Internet ?
• Internet Engineering Task Force (IETF): The IETF is
the protocol engineering and development arm of the Internet.
Subdivided into many working groups, which specify Request For
Comments or RFCs.
• IRTF (Internet Research Task Force): The Internet
Research Task Force is composed of a number of focused, longterm and small Research Groups.
• Internet Architecture Board (IAB): The IAB is
responsible for defining the overall architecture of the Internet,
providing guidance and broad direction to the IETF.
• The Internet Engineering Steering Group (IESG):
The IESG is responsible for technical management of IETF activities
and the Internet standards process. Composed of the Area Directors
of the IETF working groups.
CSIT560 by M. Hamdi
33
Internet Standardization Process
• All standards of the Internet are published as RFC (Request for
Comments). But not all RFCs are Internet Standards !
– available: http://www.ietf.org
• A typical (but not only) way of standardization is:
– Internet Drafts
– RFC
– Proposed Standard
– Draft Standard (requires 2 working implementation)
– Internet Standard (declared by IAB)
• David Clark, MIT, 1992: "We reject: kings, presidents, and
voting. We believe in: rough consensus and running code.”
CSIT560 by M. Hamdi
34
Services Provided by the Internet
• Shared access to computing resources
– telnet (1970’s)
• Shared access to data/files
– FTP, NFS, AFS (1980’s)
• Communication medium over which people interact
– email (1980’s), on-line chat rooms, instant messaging (1990’s)
– audio, video (1990’s)
• replacing telephone network?
• A medium for information dissemination
– USENET (1980’s)
– WWW (1990’s)
• replacing newspaper, magazine?
– audio, video (1990’s)
• replacing radio, CD, TV?
CSIT560 by M. Hamdi
35
Today’s Vision
• Everything is digital: voice, video, music, pictures,
live events, …
• Everything is on-line: bank statement, medical
record, books, airline schedule, weather, highway
traffic, …
• Everyone is connected: doctor, teacher, broker,
mother, son, friends, enemies, voter
CSIT560 by M. Hamdi
36
What is Next? – many of it already here
• E-Health, e-Govrnment, e-Banking, e-Business, ….
• Internet of Things
• Social Networking (Facebook, Twitter)
– Already has huge impact (e.g., Tunisia, Egypt, etc.)
• Electronic democracy
– little people can voice their opinions to the whole world
– WikiLeaks
– bridge the gap between information haves and have no’s
• Electronic Crimes
– hacker can bring the whole world to its knee
CSIT560 by M. Hamdi
37
Industrial Players
• Telephone companies
– own long-haul and access communication links, customers
• Cable companies
– own access links
• Wireless/Satellite companies
– alternative communication links
• Utility companies: power, water, railway
– own right of way to lay down more wires
• Medium companies
– own content
• Internet Service Providers
• Equipment companies
– switches/routers, chips, optics, computers
• Software companies
CSIT560 by M. Hamdi
38
What is the Internet?
• The collection of hosts and routers that are mutually
reachable at any given instant
• All run the Internet Protocol (IP)
– Version 4 (IPv4) is the dominant protocol
– Version 6 (IPv6) is the future protocol
• Lots of protocols below and above IP, but only one IP
– Common layer
CSIT560 by M. Hamdi
39
Commercial Internet after 1994
• Roughly hierarchical
• National/international
backbone providers
(NBPs)
– e.g., Sprint, AT&T, UUNet
– interconnect (peer) with
each other privately, or at
public Network Access
Point (NAPs)
• regional ISPs
– connect into NBPs
• local ISP, company
– connect into regional ISPs
local
ISP
regional ISP
NBP B
NAP
NAP
NBP A
regional ISP
local
ISP
CSIT560 by M. Hamdi
40
Internet Organization
CN
NAP
POP
ISP
CN
CN
ISP
CN
BSP
POP
POP
NAP
POP
POP
CN
BSP
NAP
POP
BSP
CN
POP
CN
ISP
CN
ISP = Internet Service Provider
BSP = Backbone Service Provider
NAP = Network Access Point
POP = Point of Presence
CN = Customer Network
CSIT560 by M. Hamdi
41
Commercial Internet after 1994
Joe's Company
Campus Network
Berkeley
Stanford
Regional ISP
Bartnet
Xerox Parc
SprintNet
America On Line
UUnet
NSF Network
IBM
NSF Network
Modem
Internet MCI
IBM
CSIT560 by M. Hamdi
42
Topology of CERNET
CSIT560 by M. Hamdi
43
The Role of Hong Kong Internet Exchange
Global
Internet
HK ISP-B
HK ISP-A
HKIX
Downstream Customers
Downstream Customers
CSIT560 by M. Hamdi
44
CSIT560 by M. Hamdi
45
HKIX Infrastructure
Internet
Internet
Internet
ISP 2
ISP 1
HKIX2
HKIX - AS4635
ISP 3
HKIX1
2 x 10Gbps links
ISP 4
Internet
ISP 5
Internet
CSIT560 by M. Hamdi
ISP 6
Internet
46
CSIT560 by M. Hamdi
47
HARNET/Internet
PCCW
Data Centre
HK
U
CUHK
PolyU
45M IPLC
54M/108M
6M/12M
54M/108M
6M/12M
54M/108M
6M/12M
CityU
22M/44M
11M/22M
HKBU
Internet2
STARTAP
PCCW
ATM
NETWOR
K
35M/70M
25M/50M
24M/48M
6M/12M
45M/90M
8  24M/48M
54M/108M
5M/10M
96M IP
EQUANT
INTERNET
BACKBONE
10M/20M
Commodity
Internet
2
50M/100M
HKIX
24M/48M
6M/12M
2M
CERNET/
TANET
10M
HKUST
HKIEd
LU
Equant
Data Centre
CSIT560 by M. Hamdi
48
Internet Architecture
CSIT560 by M. Hamdi
49
Basic Architecture: NAPs and National
ISPs
• The Internet has a hierarchical structure.
• At the highest level are large national Internet
Service Providers that interconnect through
Network Access Points (NAPs).
• There are about a dozen NAPs in the U.S., run by
common carriers such as Sprint and Ameritech, and
many more around the world (Many of these are
traditional telephone companies, others are pure
data network companies).
CSIT560 by M. Hamdi
50
The real story…
• Regional ISPs interconnect with
national ISPs and provide services to
their customers and sell access to local
ISPs who, in turn, sell access to
individuals and companies.
CSIT560 by M. Hamdi
51
pop
pop
pop
pop
CSIT560 by M. Hamdi
52
The Hierarchical Nature of the Internet
Central
Office
Central
Office
San Francisco
Node
Central
Office
Major
City
Regional
Center
Node
Long Distance Network
New York
Major
City
Regional
Center
Central
Office
Central
Office
Central
Office
CSIT560 by M. Hamdi
Node
Node
Metro Network
53
Points of Presence (POPs)
POP2
A
POP1
POP4
B
C
POP3
E
POP5
POP6
POP7
D
POP8
CSIT560 by M. Hamdi
F
54
Router Market Share
CSIT560 by M. Hamdi
55
A Bird’s View of the Internet
CSIT560 by M. Hamdi
56
A Bird’s View of the Internet
CSIT560 by M. Hamdi
57
Hop-by-Hop Behavior
From traceroute.pacific.net.hk to cs.stanford.edu
Within HK
Los Angeles
Qwest
(Backbone)
Stanford
traceroute to cs.stanford.edu (171.64.64.64) from lamtin.pacific.net.hk (202.14.67.228),
rsm-vl1.pacific.net.hk (202.14.67.5)
gw2.hk.super.net (202.14.67.2)
3 wtcr7002.pacific.net.hk (202.64.22.254)
4 atm3-0-33.hsipaccess2.hkg1.net.reach.com (210.57.26.1)
5 ge-0-3-0.mpls1.hkg1.net.reach.com (210.57.2.129)
6 so-4-2-0.tap2.LosAngeles1.net.reach.com (210.57.0.249)
7 unknown.Level3.net (209.0.227.42)
8 lax-core-01.inet.qwest.net (205.171.19.37)
9 sjo-core-03.inet.qwest.net (205.171.5.155)
10 sjo-core-01.inet.qwest.net (205.171.22.10)
11 svl-core-01.inet.qwest.net (205.171.5.97)
12 svl-edge-09.inet.qwest.net (205.171.14.94)
13 65.113.32.210 (65.113.32.210)
14 sunet-gateway.Stanford.EDU (171.66.1.13)
15 CS.Stanford.EDU (171.64.64.64)
CSIT560 by M. Hamdi
58
NAP-Based Architecture
CHI
NAP
SF
NAP
Sprint Net
MAE
West
NY
NAP
QWest
MCI
UUNET
CSIT560 by M. Hamdi
WDC
NAP
59
Basic Architecture: MAEs and local ISPs
• As the number of ISPs has grown, a new type of
network access point, called a metropolitan area
exchange (MAE) has arisen.
• There are about 50 such MAEs around the U.S.
today.
• Sometimes large regional and local ISPs (AOL) also
have access directly to NAPs.
• It has to be approved by the other networks already
connected to the NAPs – generally it is a business
decision.
CSIT560 by M. Hamdi
60
Internet Packet Exchange Charges
Peering
• ISPs at the same level usually do not
charge each other for exchanging
messages.
• They update their routing tables with
each other customers or pop.
• This is called peering.
CSIT560 by M. Hamdi
61
Charges: Non-Peering
• Higher level ISPs, however, charge lower level ones
(national ISPs charge regional ISPs which in turn
charge local ISPs) for carrying Internet traffic.
• Local ISPs, of course, charge individuals and
corporate users for access.
CSIT560 by M. Hamdi
62
Connecting to an ISP
• ISPs provide access to the Internet through a Point
of Presence (POP).
• Individual users access the POP through a dial-up
line using the PPP protocol.
• The call connects the user to the ISP’s modem pool,
after which a remote access server (RAS) checks
the user-id and password.
CSIT560 by M. Hamdi
63
More on connecting
• Once logged in, the user can send TCP/IP/[PPP]
packets over the telephone line which are then
sent out over the Internet through the ISP’s POP
(point of presence)
• Corporate users might access the POP using a
T-1, T-3 or ATM OC-3 connections, for example,
provided by a common carrier.
CSIT560 by M. Hamdi
64
DS (telephone carrier) Data Rates
Designation
DS0
Number of
Voice Circuits
1
Bandwidth
64 kb/s
DS1 (T1)
24
1.544 Mb/s
DS2 (T2)
96
6.312 Mb/s
DS3 (T3)
672
44.736 Mb/s
CSIT560 by M. Hamdi
65
SONET Data Rates
A small set of fixed data transmission rates is defined for SONET. All of these rates
are multiples of 51.84 Mb/s, which is referred to as Optical Carrier Level 1 (on the
fiber) or Synchronous Transport Signal Level 1 (when converted to electrical signals)
Optical Level
Line Rate, Mb/s
OC-1
51.840
OC-3
155.520
OC-9
466.560
OC-12
622.080
OC-18
933.120
OC-24
1244.160
OC-36
1866.240
OC-48
2488.320
OC-96
4976.640
OC-192
9953.280
OC-768
39813.120
CSIT560 by M. Hamdi
66
ISPs and Backbones
POP: Connection with
customers
T1 Lines to
Customers
POP: connection with POP of the
same ISP or different ISPs
T3 Lines to
Other POPs
Line
Server
Dialup Lines
to Customers
T3 Line
Router
Ethernet
Point of Presence (POP)
CSIT560 by M. Hamdi
OC-3
Line
ATM
Switch
Core
Router
OC-3
Lines
to Other
ATM Switches
67
Sprint
Abilene
CA*Net 3
UUNet
Verio
DREN
WSU
Router
Boeing
Router
Router
U Idaho
Microsoft
Switch
Switch
Router
Router
Montana
State U
HSCC
Router
High-speed
Router
High-speed
Router
AT&T
U Montana
Router
Switch
Switch
SCCD
Router
Sprint
U Alaska
Portland
POP
U Wash
CSIT560
by M. Hamdi
Inside the Pacific/Northwest
Gigapop
OC-48
OC-12
T-3
68
From the ISP to the NAP/MAE
• Each ISP acts as an autonomous system, with is
own interior and exterior routing protocols.
• Messages destined for locations within the same
ISP are routed through the ISP’s own network.
• Since most messages are destined for other
networks, they are sent to the nearest MAE or
NAP where they get routed to the appropriate
“next hop” network.
CSIT560 by M. Hamdi
69
From the ISP to the NAP/MAE
• Next is the connection from the local ISP to the
NAP. From there packets are routed to the next
higher level of ISP.
• Actual connections can be complex and packets
sometimes travel long distances. Each local ISP
might connect a different regional ISP, causing
packets to flow between cities, even though their
destination is to another local ISP within the
same city.
CSIT560 by M. Hamdi
70
Network Access Point
CSIT560 by M. Hamdi
71
ISPs and Backbones
POP
POP
POP
POP
POP
POP
ATM/SONET
Core
POP
POP
POP
Router Core
POP
POP
POP
Access Network
CSIT560 by M. Hamdi
POP
72
Three national ISPs in North America
CSIT560 by M. Hamdi
73
Backbone Map of UUNET - USA
CSIT560 by M. Hamdi
74
UUNET
• Mixed OC-12 – OC48 – OC 192
backbone
• 1000s miles of fiber
• 3000 POPs
• 2,000,000 dial-in
ports
CSIT560 by M. Hamdi
75
Backbone Map of UUNET - World
CSIT560 by M. Hamdi
76
Qwest
• OC-192 backbone
• 25,000 miles of fiber
• 635 POPs
• 85,000 dial-in ports
CSIT560 by M. Hamdi
77
AT&T
• OC-192 backbone
• 53,000 miles of fiber
• 2000 POPs
• 0 dial-in ports
CSIT560 by M. Hamdi
78
Internet Backbones after 2006
• As of mid-2001, most backbone circuits for national
ISPs in the US are 622 Mbps ATM OC-12 lines.
• The largest national ISPs converted to OC-192 (10
Gbps) by the end of 2005.
• Many are now experimenting with OC-768 (40 Gbps)
and some are planning to use OC-3072 (160 Gbps).
• Aggregate Internet traffic reached 2.5 Terabits per
second (Tbps) by mid-2001. It is expected to reach
100 Tbps by 2011.
CSIT560 by M. Hamdi
79
Data Centers
CSIT560 by M. Hamdi
Links for Long Haul Transmission
• Possibilities
– IP over SONET
– IP over ATM
– IP over Satellite
– IP over WDM
CSIT560 by M. Hamdi
81
User Services & Core Transport
EDGE
Frame Relay
IP
IP
Router
CORE
Frame
Relay
ATM
ATM
Switch
Lease Lines
Sonet
ADM
Users
Services
TDM
Switch
OC-3
OC-3
OC-12
STS-1
STS-1
STS-1
Service Provider
Networks
Transport Provider
Networks
CSIT560 by M. Hamdi
82
Typical (BUT NOT ALL) IP Backbone (Mid
2000s)
Core
Router
Core
Router
ATM
Switch
ATM
Switch
MUX
SONET/SDH
ADM
MUX
SONET/SDH
ADM
SONET/SDH
DCS
SONET/SDH
DCS
SONET/SDH
ADM
SONET/SDH
ADM
MUX
MUX
ATM
Switch
ATM
Switch
Core
Router
Core
Router
• Data piggybacked over traditional voice/TDM transport
CSIT560 by M. Hamdi
83
IP Backbone Evolution (One version)
Core
Router
(IP/MPLS)
• Removal of ATM Layer
FR/ATM
Switch
MUX
SONET/SDH
– Next generation routers
provide trunk speeds and
SONET interfaces
– Multi-protocol Label
Switching (MPLS) on
routers provides traffic
engineering
Core
Router
(IP/MPLS)
SONET/
SDH
DWDM
DWDM
(Maybe)
CSIT560 by M. Hamdi
84
Hierarchy of Routers and Switches
Core
IP Router
FR/ATM
Switch
SONET/SDH
•IP Router (datagram packet switching)
• Deals directly with IP addresses;
• Slow – typically no interface to SONET equipment
• Expensive
• Efficient (No header overhead and alternative routing)
•ATM Switch (VC packet switching)
• Label based switching
• Fast (Hardware forwarding)
• Header Tax
•SONET OXC (Circuit switching)
• Extremely fast – Optical technology
• Inexpensive
CSIT560 by M. Hamdi
85
Customer Network
• All hosts owned by a single enterprise or business
• Common case
– Lots of PCs
– Some servers
– Routers
– Ethernet 10/100/1000-Mb/s LAN
– T1/T3 1.54/45-Mb/s wide area network (WAN) connection
CSIT560 by M. Hamdi
86
Customer Network
http://www.ust.hk/itsc/network/
Clients
LAN
Ethernet
10 Mb/s
Servers
Router
WAN
T1 Link
1.54 Mb/s
CSIT560 by M. Hamdi
87
Internet Access
Technologies
CSIT560 by M. Hamdi
88
Internet Access Technologies
• Previously, most people use 56K dial-up lines to
access the Internet, but a number of new access
technologies are now being offered.
• The main new access technologies are:
– Digital Subscriber Line/ADSL
– Cable Modems
– Fixed Wireless (including satellite access)
– Mobile Wireless (WAP)
CSIT560 by M. Hamdi
89
Digital Subscriber Line
• Digital Subscriber Line (DSL) is one of the most
used technologies now being implemented to
significantly increase the data rates over traditional
telephone lines.
• Historically, voice telephone circuits have had only a
limited capacity for data communications because
they were constrained by the 4 kHz bandwidth voice
channel.
• Most local loop telephone lines actually have a
much higher bandwidth and can therefore carry data
at much higher rates.
CSIT560 by M. Hamdi
90
Digital Subscriber Line
• DSL services are relatively new and not all common
carriers offer them.
• Two general categories of DSL services have
emerged in the marketplace.
– Symmetric DSL (SDSL) provides the same transmission
rates (up to 128 Kbps) in both directions on the circuits.
– Asymmetric DSL (ADSL) provides different data rates to
(up to 640 Kbps) and from (up to 6.144 Mbps) the carrier’s
end office. It also includes an analog channel for voice
transmissions.
CSIT560 by M. Hamdi
91
Customer Premises
DSL Modem
Local Carrier End Office
Main
Distribution
Frame
Line Splitter
Voice
Telephone
Network
Local Loop
DSL
Architecture
Hub
Telephone
ATM Switch
Computer
Computer
Customer
Premises
ISP POP
DSL Access
Multiplexer
ISP POP
ISP POP
ISP POP
Customer
Premises
CSIT560 by M. Hamdi
92
Cable Modems
• One potential competitor to DSL is the “cable modem”
a digital service offered by cable television
companies which offers an upstream rate of 1.5-10
Mbps and a downstream rate of 2-30 Mbps.
• A few cable companies offer downstream services
only, with upstream communications using regular
telephone lines.
CSIT560 by M. Hamdi
93
Cable Company
Fiber Node
Customer Premises
Cable Modem
Cable Company Distribution Hub
TV Video
Network
Cable Splitter
Downstream
Optical/Electrical
Converter
Combiner
Upstream
Hub
TV
Router
Computer
Computer
Shared
Coax
Cable
System
Cable
Company
Fiber Node
Customer
Premises
Customer
Premises
Cable Modem
Termination
System
ISP POP
Cable Modem Architecture
CSIT560 by M. Hamdi
94
Fixed Wireless
• Fixed Wireless is another “dish-based” microwave
transmission technology.
• It requires “line of sight” access between
transmitters.
• Data access speeds range from 1.5 to 11 Mbps
depending on the vendor.
• Transmissions travel between transceivers at the
customer premises and ISP’s wireless access
office.
CSIT560 by M. Hamdi
95
Customer Premises
Individual Premise
DSL Modem
Fixed Wireless Architecture
Main
Distribution
Frame
Line Splitter
Voice
Telephone
Network
Hub
Telephone
Individual
Premise
Wireless
Transceiver
Individual
Premise
DSL Access
Multiplexer
Computer Computer
Wireless Access Office
Customer
Premises
Wireless
Transceiver
Customer
Premises
Router
ISP POP
CSIT560 by M. Hamdi
96
Classifying Computer
Networks
CSIT560 by M. Hamdi
97
A Taxonomy of Communication Networks
• Communication networks can be classified based on the way in
which the nodes exchange information:
Communication
Network
Switched
Communication
Network
Circuit-Switched
Communication
Network
Broadcast
Communication
Network
Packet-Switched
Communication
Network
Datagram
Network
Virtual Circuit
Network
CSIT560 by M. Hamdi
98
Broadcast vs. Switched Communication
Networks
• Broadcast communication networks
– information transmitted by any node is received by every other
node in the network
• examples: usually in LANs (Ethernet, Wavelan)
– Problem: coordinate the access of all nodes to the shared
communication medium (Multiple Access Problem)
• Switched communication networks
– information is transmitted to a sub-set of designated nodes
• examples: WANs (Telephony Network, Internet)
– Problem: how to forward information to intended node(s)
• this is done by special nodes (e.g., routers, switches) running routing
protocols
CSIT560 by M. Hamdi
99
Circuit Switching
•
Three phases
1. circuit establishment
2. data transfer
3. circuit termination
•
If circuit is not available: “Busy signal”
•
Examples
 Telephone networks
 ISDN (Integrated Services Digital Networks)
 Optical Backbone Internet (going in this direction)
CSIT560 by M. Hamdi
100
Timing in Circuit Switching
Host 1
Node 1
Node 2
Host 2
processing delay at Node 1
propagation delay
between Host 1
and Node 1
Circuit
Establishment
propagation delay
between Host 2
and Node 1
Data
Transmission
DATA
Circuit
Termination
CSIT560 by M. Hamdi
101
Circuit Switching
• A node (switch) in a circuit switching network
incoming links
Node
outgoing links
CSIT560 by M. Hamdi
102
Circuit Switching:
Multiplexing/Demultiplexing
• Time divided in frames and frames divided in slots
• Relative slot position inside a frame determines which
conversation the data belongs to
• If a slot is not used, it is wasted
• There is no statistical gain
CSIT560 by M. Hamdi
103
Packet Switching
• Data are sent as formatted bit-sequences, so-called packets.
• Packets have the following structure:
Header
Data
Trailer
• Header and Trailer carry control information (e.g., destination
address, check sum)
• Each packet is passed through the network from node to node
along some path (Routing)
• At each node the entire packet is received, stored briefly, and
then forwarded to the next node (Store-and-Forward
Networks)
• Typically no capacity is allocated for packets
CSIT560 by M. Hamdi
104
Packet Switching
• A node in a packet switching network
incoming links
Node
outgoing links
Memory
CSIT560 by M. Hamdi
105
Packet Switching:
Multiplexing/Demultiplexing
• Data from any conversation can be transmitted at any
given time
• How to tell them apart?
– use meta-data (header) to describe data
CSIT560 by M. Hamdi
106
Datagram Packet Switching
• Each packet is independently switched
– each packet header contains destination address
• No resources are pre-allocated (reserved) in advance
• Example: IP networks
CSIT560 by M. Hamdi
107
Timing of Datagram Packet Switching
Host 1
transmission
time of Packet 1
at Host 1
Node 1
Packet 1
Host 2
Node 2
propagation
delay between
Host 1 and
Node 2
Packet 2
Packet 1
Packet 3
processing
delay of
Packet 1 at
Node 2
Packet 2
Packet 3
Packet 1
Packet 2
Packet 3
CSIT560 by M. Hamdi
108
Datagram Packet Switching
Host C
Host D
Host A
Node 1
Node 2
Node 3
Node 5
Host B
Node 6
Node 7
Host E
Node 4
CSIT560 by M. Hamdi
109
Virtual-Circuit Packet Switching
• Hybrid of circuit switching and packet switching
– data is transmitted as packets
– all packets from one packet stream are sent along a preestablished path (=virtual circuit)
• Guarantees in-sequence delivery of packets
• However: Packets from different virtual circuits may
be interleaved
• Example: ATM networks
CSIT560 by M. Hamdi
110
Virtual-Circuit Packet Switching
•
Communication using virtual circuits takes place in
three phases
1. VC establishment
2. data transfer
3. VC disconnect
•
Note: packet headers don’t need to contain the full
destination address of the packet (One key to this
idea)
CSIT560 by M. Hamdi
111
Timing of VC Packet Switching
Host 1
Node 1
Host 2
Node 2
propagation delay
between Host 1
and Node 1
VC
establishment
Packet 1
Packet 2
Packet 1
Data
transfer
Packet 3
Packet 2
Packet 3
Packet 1
Packet 2
Packet 3
VC
termination
CSIT560 by M. Hamdi
112
VC Packet Switching
Host C
Host D
Host A
Node 1
Node 2
Node 3
Node 5
Host B
Node 6
Node 7
Host E
Node 4
CSIT560 by M. Hamdi
113
Packet-Switching vs. Circuit-Switching
• Most important advantage of packet-switching over
circuit switching: Ability to exploit statistical
multiplexing:
– efficient bandwidth usage; ratio between peek and average
rate is 3:1 for audio, and 15:1 for data traffic
• However, packet-switching needs to deal with
congestion:
– more complex routers
– harder to provide good network services (e.g., delay and
bandwidth guarantees)
• In practice they are combined
– IP over SONET, IP over Frame Relay
CSIT560 by M. Hamdi
114
Fixed-Rate versus Bursty Data
CSIT560 by M. Hamdi
115
Packet Switches
Destination
Address
Routing
Table
Connectionless
Packet Switch
A
A
Possibly different paths through switch
A
Connection
Identifier
B
B
Always same path through switch
B
Connection
Table
Connection-Oriented
Packet Switch
CSIT560 by M. Hamdi
116
Store-and-Forward Operation
• Packet entering switch or router is stored in a queue
until it can be forwarded
– Queueing
– Header processing
– Routing-table lookup of destination address
– Forwarding to next hop
• Queueing time variation can result in nondeterministic delay behavior (maximum delay and
delay jitter)
• Packets might overflow finite buffers (Network
congestion)
CSIT560 by M. Hamdi
117
Link Diversity
• Internet meant to accommodate many different link
technologies
– Ethernet
– ATM
– SONET
– ISDN
– Modem
• The list continues to grow
• “IP on Everything”
CSIT560 by M. Hamdi
118
Internet Protocols
CSIT560 by M. Hamdi
119
Internet Protocols
Application
Application
Transport
Transport
Network
Link
Host
Network
Link
Link
Router
CSIT560 by M. Hamdi
Network
Link
Host
120
IP Protocol Stack
Ping
Telnet
FTP
H.323
SIP
RTSP
TCP
RSVP
S/MGCP/
NCS
User
application
UDP
OSPF
ARP
ICMP
IP
IGMP
RARP
Link Layer
CSIT560 by M. Hamdi
121
Demultiplexing
Application
Application
Transport
ICMP
Application
Application
TCP
Application
UDP
IGMP
Network
IP
ARP
Link
RARP
Ethernet
Driver
incoming frame
CSIT560 by M. Hamdi
122
Link Protocols
• Numerous link protocols
– Ethernet + LLC (Logical Link Control)
– T1/DS1 + HDLC (High-level Data Link Control)
– T3/DS3 + HDLC
– Dialup + PPP (Point-to-Point Protocol)
– ATM/SONET + AAL (ATM Adaptation Layer)
– ISDN + LAPD (Link Access Protocol) + PPP
– FDDI + LLC
CSIT560 by M. Hamdi
123
Additional Link Protocols
• ARP (Address Resolution Protocol) is a protocol for
mapping an IP address to a physical machine address
that is recognized in the local network. Most
commonly, this is used to associate IP addresses (32bits long) with Ethernet MAC addresses (48-bits long).
• RARP is the reverse of ARP
CSIT560 by M. Hamdi
124
ARP Protocol
CSIT560 by M. Hamdi
125
Sending an IP Packet over a LAN
CSIT560 by M. Hamdi
126
Transport Protocols
• Transmission Control Protocol (TCP)
• User Datagram Protocol (UDP)
CSIT560 by M. Hamdi
127
Application Protocols
• File Transfer Protocol (FTP)
• Simple Mail Transfer Protocol (SMTP)
• Telnet
• Hypertext Transfer Protocol (HTTP)
• Simple Network Management Protocol (SNMP)
• Remote Procedure Call (RPC)
• DNS: The Domain Name System service provides
TCP/IP host name to IP address resolution.
CSIT560 by M. Hamdi
128
The Internet Network layer: The Glue of
all Networks
Transport layer: TCP, UDP
Network
layer
IP protocol
•addressing conventions
•datagram format
•packet handling conventions
Routing protocols
•path selection
•RIP, OSPF, BGP
routing
table
ICMP protocol
•error reporting
•router “signaling”
Link layer
physical layer
CSIT560 by M. Hamdi
129
Demultiplexing Details
echo
server
1024-5000
FTP
server
User process
User process
User process
User process
21
9
TCP src port
UDP
ICMP
IGMP
TCP dest port

header

data


17
1
2

IP header
x0806
discard
server
TCP
TCP
ARP
23
7
telnet
server
6
protocol type

hdr
cksum
dest
addr
source
addr

data

Others
RARP
x8035
IP
Novell
IP
x0800
AppleTalk
dest
addr
source
addr
Ethernet frame type

data
CRC

(Ethernet frame types in hex, others in decimal)
CSIT560 by M. Hamdi
130
IP Features
•
•
•
•
•
•
Connectionless service
Addressing
Data forwarding
Fragmentation and reassembly
Supports variable size datagrams
Best-effort delivery: Delay, out-of-order, corruption,
and loss possible. Higher layers should handle these.
• Provides only “Send” and “Delivery” services
Error and control messages generated by
Internet Control Message Protocol (ICMP)
CSIT560 by M. Hamdi
131
What IP does NOT provide
• End-to-end data reliability & flow control (done by TCP or
application layer protocols)
• Sequencing of packets (like TCP)
• Error detection in payload (TCP, UDP or other transport layers)
• Error reporting (ICMP)
• Setting up route tables (RIP, OSPF, BGP etc)
• Connection setup (it is connectionless)
• Address/Name resolution (ARP, RARP, DNS)
• Configuration (BOOTP, DHCP)
• Multicast (IGMP, MBONE)
CSIT560 by M. Hamdi
132
Internet Protocol (IP)
• Two versions
– IPv4
– IPv6
• IPv4 dominates today’s Internet
• IPv6 is used sporadically
– 6Bone, Internet 2
CSIT560 by M. Hamdi
133
IPv4 Header
0
15
Ver
HLen
TOS
Length
Ident
TTL
31
Flags
Protocol
Offset
Checksum
SrcAddr
DestAddr
Options
Pad
CSIT560 by M. Hamdi
134
IPv4 Header Fields (1)
• Ver: version of protocol
– First thing to be determined
– IPv4  4, IPv6  6
• Hlen: header length (in 32-bit words)
– Usually has a value of 5
– When options are present, the value is > 5
• TOS: type of service
– Packet precedence (3 bits)
– Delay/throughput/reliability specification
– Rarely used
CSIT560 by M. Hamdi
135
IPv4 Header Fields (2)
• Length: length of the datagram in bytes
– Maximum datagram size of 65,535 bytes
• Ident: identifies fragments of the datagram (Ethernet
1500 Bytes max., FDDI: 4900 Bytes Max., etc.)
• Flag: indicates whether more fragments follow
• Offset: number of bytes payload is from start of
original user data
CSIT560 by M. Hamdi
136
Fragmentation Example
20-byte optionless
IP headers
Id = x
0 0 1
0
492 data bytes
Id = x
0 0 0
1400 data bytes
0
Id = x
0 0 1
492
492 data bytes
Id = x
0 0 0
984
416 data bytes
CSIT560 by M. Hamdi
137
IPv4 Header Fields (3)
• TTL: time to live gives the maximum number of hops
for the datagram
• Protocol: protocol used above IP in the datagram
– TCP  6, UDP  17,
• Checksum: covers IP header
CSIT560 by M. Hamdi
138
IPv4 Header Fields (4)
• SrcAddr: 32-bit source address
• DestAddr: 32-bit destination address
• Options: variable list of options
– Security: government-style markings
– Loose source routing: combination of source and table
routing
– Strict source routing: specified by source
– Record route: where the datagram has been
– Options rarely used
CSIT560 by M. Hamdi
139
IPv6
• Initial motivation: 32-bit address space completely
allocated by 2008.
• Additional motivation:
– header format helps speed processing/forwarding
– header changes to facilitate QoS
– new “anycast” address: route to “best” of several replicated
servers
• IPv6 datagram format:
– fixed-length 40 byte header
– no fragmentation allowed (done only by source host)
CSIT560 by M. Hamdi
140
IPv6: Differences from IPv4
Flow label
– Intended to support quality of service (QoS)
• 128-bit network addresses
• No header checksum – reduce processing time
• Fragmentation only by source host
• Extension headers
– Handles options (but outside the header, indicated by “Next
Header” field
CSIT560 by M. Hamdi
141
IPv6 Headers
0
15
Ver
Pri
31
Flow Label
Payload Length
Next Header
Hop Limit
Source Address
Destination Address
CSIT560 by M. Hamdi
142
IPv6 Header Fields (1)
• Ver: version of protocol
• Pri: priority of datagram
– 0 = none, 1 = background traffic, 2 = unattended data
transfer
– 4 = attended bulk transfer, 6 = interactive traffic, 7 =
control traffic
• Flow Label
– Identifies an end-to-end flow
– IP “label switching”
– Experimental
CSIT560 by M. Hamdi
143
IPv6 Header Fields (2)
• Payload Length: total length of the datagram less that
of the basic IP header
• Next Header
– Identifies the protocol header that follows the basic IP
header
– TCP => 6, UDP => 17, ICMP => 58, IP = 4, none => 59
• Hop Limit: time to live
CSIT560 by M. Hamdi
144
IPv6 Header Fields (3)
• Source/Destination Address
– 128-bit address space
– Embed world-unique link address in the lower 64 bits
– Address “colon” format with hexadecimal
– FEDC:BA98:7654:3210:FEDC:BA98:7654:3210
CSIT560 by M. Hamdi
145
Addressing Modes in IPv6
• Unicast
– Send a datagram to a single host
• Multicast
– Send copies a datagram to a group of hosts
• Anycast
– Send a datagram to the nearest in a group of hosts
CSIT560 by M. Hamdi
146
Migration from IPv4 to IPv6
• Interoperability with IPv4 is necessary for gradual deployment.
• Two mechanisms:
– dual stack operation: IPv6 nodes support both address types
– tunneling: tunnel IPv6 packets through IPv4 clouds
• Unfortunately there is little motivation for any one organization
to move to IPv6.
– the challenge is the existing hosts (using IPv4 addresses)
– little benefit unless one can consistently use IPv6
• can no longer talk to IPv4 nodes
– stretching address space through address translation seems to
work reasonably well
CSIT560 by M. Hamdi
147