Transcript and packet switching - Computer Science Division

Welcome to CS 340
Introduction to Computer
Networking
Overview
• Course Administrative Trivia
• Internet Architecture
• Network Protocols
• Network Edge
• A taxonomy of communication networks
Some slides are in courtesy of J. Kurose and K. Ross
Course Overview
• Top-down Intro Networking Class
– Application down to physical layer
• Topics to Cover
– Overview of Internet architecture, protocols
– Network applications (HTTP, FTP) and programming
– Transport (TCP, UDP), congestion/flow control
– Network (IP), routing, multicast
– Data Link, error handling, LAN, wireless
Logistics
• Instructor
Aleksandar Kuzmanovic
([email protected]),
Office Hours: Th. 2-4pm or by appointment, Rm
356, 1890 Maple Ave.
• TA: Bin Lin ([email protected])
Office Hours: Tu. and Th. 11am - noon(12pm), Rm
240, Maple Ave.
• TA backup (first 2 weeks):
Yi Qiao (yqiao@cs...) Suite 300, Maple Ave.
Prerequisites
• A LOT OF WORK – Heavy Projects - but it’s worth!
– Build a TCP stack and a Web server that runs on it
– IP routing
• Required: CS311 (data structure)
• Highly Recommended: OS or having some
familiarity with Unix systems programming,
preferably in C or C++
– Minet is in C++
– BUILDING software is 50% of the grade of this class
Course Materials
• Computer Networking: A Top-Down Approach
Featuring the Internet, Third Edition, James
Kurose and Keith Ross, Addison Wesley, 2005
• TCP/IP Illustrated, Volume I: The Protocols,
Richard Stevens, Addison Wesley, 1994
• See course webpage and syllabus for other
recommended books and references
Grading
• Homeworks (4 sets) 10%
• Projects 50%
– Web client/server 10%
– TCP stack
25%
– IP routing
15%
• Midterm 20%
• Final 20%
– Exams in-class, closed-book, non-cumulative
• Late policy: 10% each day after the due date
• No cheating
Communication
• Web page:
http://www.cs.nwu.edu/~akuzma/classes/cs340w05/
• Recitation: Wed., 4-5pm, Room 342, 1890 Maple.
– TA lectures on the homework and projects, and help to
prepare the exams.
• Newsgroup are available
– cs.340.annouce
(course announcement)
– cs.340.discuss
(posting Q & A)
• Send emails to instructor and TA for questions
inappropriate in newsgroup
Overview
• Course administrative trivia
• Internet Architecture
• Network Protocols
• Network Edge
• A taxonomy of communication networks
What’s the Internet: “nuts and bolts” view
• Millions of connected
computing devices: hosts,
end-systems
– PCs, servers
– PDAs, phones, toasters, shoes
router
server
workstation
mobile
local ISP
running network apps
regional ISP
• Communication links
– Fiber, cable, radio, satellite
– Residential access: modem,
DSL, cable modem, satellite
– Transmission rate = bandwidth
• Routers: forward packets
(chunks of data)
company
network
Network Components (Examples)
Links
Interfaces
Fibers
Ethernet card
Switches/routers
Large router
Wireless card
Coaxial Cable
Telephone
switch
What’s the Internet: “nuts and bolts” view
• communication
infrastructure enables
distributed applications:
– Web, email, games, ecommerce, database., voting,
file (MP3) sharing
router
server
regional ISP
– e.g., TCP, IP, HTTP, FTP
– loosely hierarchical
– public Internet versus private
intranet
mobile
local ISP
• protocols control sending,
receiving of msgs
• Internet: “network of
networks”
workstation
company
network
History of the Internet
• 70’s: started as a research project, 56 kbps, < 200
computers
• 80-83: ARPANET and MILNET split
• 85-86: NSF builds NSFNET as backbone, links 6
Supercomputer centers, 1.5 Mbps, 10,000 computers
• 87-90: link regional networks, NSI (NASA), ESNet(DOE),
DARTnet, TWBNet (DARPA), 100,000 computers
• 90-92: NSFNET moves to 45 Mbps, 16 mid-level networks
• 95: NSF backbone dismantled, multiple private backbones
• Today: backbones run at 10 Gbps, close to 200 millions
computers in 150 countries
Growth of the Internet
• Number of Hosts on
the Internet:
Aug. 1981
213
1000000000
Oct. 1984
1,024
100000000
Dec. 1987
28,174
Oct. 1990
313,000
Oct. 1993
2,056,000
Apr. 1995
5,706,000
Jan. 1997
16,146,000
Jan. 1999
56,218,000
Jan. 2001 109,374,000
Jan 2003
171,638,297
10000000
1000000
100000
10000
1000
100
10
1
1981 1984 1987 1990 1993 1996 1999 2002
Data available at: http://www.isc.org/
Overview
• Course administrative trivia
• Internet Architecture
• Network Protocols
• Network Edge
• A taxonomy of communication networks
What’s a protocol?
human protocols:
network protocols:
• “what’s the time?”
• machines rather than
humans
• “I have a question”
• introductions
… specific msgs sent
… specific actions taken
when msgs received,
or other events
• all communication
activity in Internet
governed by protocols
protocols define format,
order of msgs sent and
received among network
entities, and actions
taken on msg
transmission, receipt
What’s a protocol?
a human protocol and a computer network protocol:
Hi
TCP connection
req
Hi
TCP connection
response
Got the
time?
Get http://www.cs.nwu.edu
2:00
<file>
time
Overview
• Course administrative trivia
• Internet Architecture
• Network Protocols
• Network Edge
• A taxonomy of communication networks
The Network Edge
• End systems (hosts):
– run application programs
– e.g. Web, email
– at “edge of network”
• Client/server model
– client host requests, receives
service from always-on server
– e.g. Web browser/server; email
client/server
• Peer-to-peer model:
– minimal (or no) use of dedicated
servers
– e.g. Gnutella, KaZaA
Network Edge: Connection-oriented Service
Goal: data transfer
between end systems
• handshaking: setup
(prepare for) data
transfer ahead of time
– Hello, hello back human
protocol
– set up “state” in two
communicating hosts
• TCP - Transmission
Control Protocol
– Internet’s connectionoriented service
TCP service [RFC 793]
• reliable, in-order bytestream data transfer
– loss: acknowledgements
and retransmissions
• flow control:
– sender won’t overwhelm
receiver
• congestion control:
– senders “slow down sending
rate” when network
congested
Network Edge: Connectionless Service
Goal: data transfer
between end systems
– same as before!
• UDP - User Datagram
Protocol [RFC 768]:
Internet’s connectionless
service
– unreliable data
transfer
– no flow control
– no congestion control
App’s using TCP:
• HTTP (Web), FTP (file
transfer), Telnet
(remote login), SMTP
(email)
App’s using UDP:
• streaming media,
teleconferencing, DNS,
Internet telephony
Overview
• Course administrative trivia
• Internet Architecture
• Network Protocols
• Network Edge
• A taxonomy of communication networks
A Taxonomy of Communication Networks
• The fundamental question: how is data
transferred through net (including edge & core)?
• Communication networks can be classified based
on how the nodes exchange information:
Communication
Networks
Switched
Communication
Network
Circuit-Switched
Communication
Network
TDM
FDM
Broadcast
Communication
Network
Packet-Switched
Communication
Network
Datagram
Network
Virtual Circuit Network
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
A Taxonomy of Communication Networks
• The fundamental question: how is data
transferred through net (including edge & core)?
• Communication networks can be classified based
on how the nodes exchange
information:
Communication
Networks
Switched
Communication
Network
Circuit-Switched
Communication
Network
TDM
FDM
Broadcast
Communication
Network
Packet-Switched
Communication
Network
Datagram
Network
Virtual Circuit Network
Circuit-Switched Network
End-end resources
reserved for “call”
• Link bandwidth, switch
capacity
• Three phases
1. circuit establishment
2. data transfer
3. circuit termination
• Dedicated resources
+ Guaranteed performance
- no sharing
Circuit Switching
Examples
• Telephone networks
• ISDN (Integrated Services Digital Networks)
network resources (e.g., bandwidth) divided into
“pieces”
• Pieces allocated to calls
• Resource piece idle if not used by owning call (no sharing)
• Dividing link bandwidth into “pieces”
– frequency division
– time division
Circuit Switching: FDM and TDM
Example:
FDM
4 users
frequency
time
TDM
frequency
time
A Taxonomy of Communication Networks
• The fundamental question: how is data
transferred through net (including edge & core)?
• Communication networks can be classified based
on how the nodes exchange
information:
Communication
Networks
Switched
Communication
Network
Circuit-Switched
Communication
Network
TDM
FDM
Broadcast
Communication
Network
Packet-Switched
Communication
Network
Datagram
Network
Virtual Circuit Network
Packet Switching
• Data is sent as formatted bit-sequences (Packets)
• Packets have the following structure:
Header
Data
Trailer
– Header and Trailer carry control information (e.g., destination
address, check sum)
• Each packet traverses 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-andForward Networks)
• No dedicated allocation or resource reservation
Packet Switching: Statistical Multiplexing
10 Mbs
Ethernet
A
B
statistical multiplexing
C
1.5 Mbs
queue of packets
waiting for output
link
D
E
Sequence of A & B packets does not have fixed
pattern  statistical multiplexing.
In TDM each host gets same slot in revolving TDM
frame.
Packet Switching versus Circuit Switching
Packet switching allows more users to use network!
• 1 Mbit link
• Each user:
– 100 kbps when “active”
– active 10% of time
N users
• Circuit-switching:
– 10 users
• Packet switching:
– with 35 users, probability >
10 active less than .0004
1 Mbps link
Packet Switching versus Circuit Switching
• Great for bursty data
– resource sharing
– simpler, no call setup
• Excessive congestion: packet delay and loss
– protocols needed for reliable data transfer,
congestion control
• Q: How to provide circuit-like behavior?
– bandwidth guarantees needed for audio/video apps
– still an unsolved problem (chapter 6)
A Taxonomy of Communication Networks
• The fundamental question: how is data
transferred through net (including edge & core)?
• Communication networks can be classified based
on how the nodes exchange
information:
Communication
Networks
Switched
Communication
Network
Circuit-Switched
Communication
Network
TDM
FDM
Broadcast
Communication
Network
Packet-Switched
Communication
Network
Datagram
Network
Virtual Circuit Network
Datagram Packet Switching
• Each packet is independently switched
– Each packet header contains destination address
which determines next hop
– Routes may change during session
– E.g., post-office analogy
• No resources are pre-allocated (reserved) in
advance
• Example: IP networks
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
Datagram Packet Switching
Host C
Host D
Host A
Node 1
Node 2
Node 3
Node 5
Host B
Node 6
Node 4
Node 7
Host E
A Taxonomy of Communication Networks
• The fundamental question: how is data
transferred through net (including edge & core)?
• Communication networks can be classified based
on how the nodes exchange
information:
Communication
Networks
Switched
Communication
Network
Circuit-Switched
Communication
Network
TDM
FDM
Broadcast
Communication
Network
Packet-Switched
Communication
Network
Datagram
Network
Virtual Circuit Network
Virtual-Circuit Packet Switching
• Hybrid of circuit switching and packet
switching
– All packets from one packet stream are sent along a
pre-established path (= virtual circuit)
– Each packet carries tag (virtual circuit ID), tag
determines next hop
• Features
– Guarantees in-sequence delivery of packets (+)
– However, packets from different virtual circuits may
be interleaved (+)
– Requires per-flow state in the network (-)
Virtual-Circuit Packet Switching
• Communication with 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
Timing of Virtual-Circuit 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
Virtual-Circuit Packet Switching
Host C
Host D
Host A
Node 1
Node 2
Node 3
Node 5
Host B
Node 6
Node 4
Node 7
Host E
Summary
• Course Administrative Trivia
• Internet Architecture, Protocols and Taxonomy
• Eight handouts
– Syllabus, Project 1, and its complementary materials
• Project 1 out
– If you don’t have a TLAB account and a keycard to get
into the lab, fill the form.
– Find partner (groups of 2 preferred)
• Recitation tomorrow on UNIX programming and
project 1