Transcript Packet Switching

Introduction To
Computer Networks
89-350 ‫מבוא לרשתות תקשורת‬
‫פרופ' אמיר הרצברג‬
Based on foils by Kurose & Ross ©, see:
http://www.aw.com/kurose-ross/
My site: http://amirherzberg.com
Course site: http://HL2.BIU.AC.IL
Computer Networking:
A Top Down Approach
Featuring the Internet,
2nd edition.
Jim Kurose, Keith Ross
Addison-Wesley, July
2002.
Introduction
1-1
Introduction To Computer Networks
‫ פרטים‬-89-350 ‫תקשורת ומחשוב‬
 Lecturer: Prof. Amir Herzberg
 Research
in applied cryptography, secure
communication and commerce, networking, dist. algs.,…
 Reception: Monday 2:00-3:45pm, room 324
 Physical mail: bin 23
 E-mail: [email protected]
• Will normally answer within a week
 Assistants: Mor Brosh, Igal Ioffe, Fridel
Fainshtain
 Use the book and foils – read at home before
lectures!!
Introduction
1-2
Introduction To Computer Networks
‫ ציונים‬-89-350 ‫תקשורת ומחשוב‬
 80% : exam
 10% : theoretical assignments (few)
 Will not consider the lowest-graded
 But submit all – assignments are (rarely) lost
 10%: programming assignment
 Great for work interviews, experience
 Mandatory to pass both assignments and exam
 Copying will lead to immediate disciplinary action (to all
parties) – please do not.
 Class attendance optional
 But no noise…
 You can pass notes, send e-mail – but no noise!
 Offenders expelled from lecture – no warning
• Additional penalties possible (points, etc.)
Introduction
1-3
Books
 Main book: Computer Networking: A Top Down
Approach Featuring the Internet,
2nd edition.
Jim Kurose, Keith Ross
Addison-Wesley, July 2002.
 In
library and should (soon?) be in shop
 Also use: Tanenbaum: Computer Networks
 Now in 4th edition
 Some copies in library
Introduction
1-4
Online Content
 Lectures, exercises and other stuff will be posted at
Hi-Learn system: http://HL2.BIU.AC.IL
 Also: submit (most) exercises via Hi-Learn
 To login:
 Use your `regular` BIU user-ID
 Your password consists of 6 characters: XYnnnn
• X is the first letter of your first name, e.g. a for Avi
• Y is the first letter of your surname, e.g. c for Cohen
• nnnn is 4 digits code you received in the printed timetable
you (should have) received, used to access the BIU
information kiosks, e.g. 1234
• Example password is ac1234
 Problems/not registered:
[email protected]
Introduction
1-5
Schedule
Lecture
Topic
1,2
K&R
Chapter
1
3,4
2
Application layer protocols
5-7
3
7,8
4
Transport layer, reliability,
congestion
Network (internet) layer
9,10
5
Data-Link layer
11,12
7, but use
notes
Network Security
13
Introduction
Overview
Introduction
1-6
Chapter 1: Introduction
(this and next lecture)
Our goal:
Overview:
 get context,
 what’s the Internet
overview, “feel” of
networking
 more depth, detail
later in course
 approach:
 descriptive
 use Internet as
example
 what’s a protocol?
 network edge
 network core
 access net, physical media
 Internet/ISP structure
 performance: loss, delay
 protocol layers, service models
 history
Introduction
1-7
What’s the Internet: “nuts and bolts” view
 millions of connected
computing devices: hosts,
end-systems


PCs workstations, servers
PDAs phones, toasters
router/switch
server

mobile
local ISP
running network apps
 communication links

workstation
regional ISP
fiber, copper, radio,
satellite
transmission rate =
bandwidth
 router/switch: forward
packets (chunks of data)
company
network
Introduction
1-8
What’s the Internet: “nuts and bolts” view
 Internet: specific standard
technologies:




TCP, UDP, IP – and others…
Allowing interoperability
RFC: Request for comments
IETF: Internet Engineering
Task Force
router/switch
server
workstation
mobile
local ISP
regional ISP
 An internet: “network of
networks”


loosely hierarchical
public Internet versus private
intranet
company
network
Introduction
1-9
Computer Communication Network
 Connection btw
computers
 Each pair can
communicate
(using `physical`
network
addresses)
 Different
implementations
 Most ensure
reliable
communication
2
1
5
3
4
Introduction
1-10
Network Types
Link
Each pair can communicate
(using network addresses)
Bus
Satellite
S
W
Network
Cellular
Switched
Star
N
M
S
Ring
Introduction
1-11
An internet: Connection of Networks
(Using TCP/IP; `Internet` is the `big, public` internet.)
R
O
U
T
E
R
R
O
U
T
E
R
Each pair can communicate
(using Internet Protocol addresses
(IP addresses))
R
O
U
T
E
R
R
O
U
T
E
R
R
O
U
T
E
R
Introduction
1-12
What’s the Internet: a service view
 communication
infrastructure enables
distributed applications:

Web, email, games, ecommerce, database., voting,
file (MP3) sharing
 Communication transport
services provided to apps:


connectionless
connection-oriented
 Use protocols to control
send, receive messages

e.g., TCP, IP, HTTP, FTP,
POP3, SMTP
Introduction
1-13
What’s a protocol?
human protocols:
 “what’s the time?”
 “I have a question”
 introductions
… specific msgs sent
… specific actions taken
when msgs received,
or other events
network protocols:
 machines rather than
humans
 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
Introduction
1-14
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.awl.com/kurose-ross
2:00
<file>
time
Q: What is this protocol?
Q: Other human protocols?
Introduction
1-15
A closer look at network structure:
 network edge:
applications and
hosts
 network core:
 routers/switches

network of
networks
Introduction
1-16
Chapter 1: roadmap
1.1 What is the Internet?
1.3 Network core
1.2 Network edge
1.4 Network access and physical media
1.5 Internet structure and ISPs
1.6 Delay & loss in packet-switched networks
1.7 Protocol layers, service models
1.8 History
Introduction
1-17
The Network Core
 mesh of interconnected
routers and switches
 Hi speed, minimize work
 Routing: how is data
transferred through net?
 circuit switching:
dedicated circuit per
call: telephone net
 packet-switching: data
sent thru net in
discrete “chunks”
Introduction
1-18
Network Core: Circuit Switching
End-end resources
reserved for “call”
 link bandwidth, switch




capacity
dedicated resources: no
sharing
circuit-like (guaranteed)
performance
call setup required
Example: phone network
Introduction
1-19
Network Core: Circuit Switching
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”
 Division for Multiple
Access:
 Frequency division
(FDMA)
 Time division (TDMA)
 Code division (CDMA)
– much later
Introduction
1-20
Circuit Switching: TDMA and FDMA
Example:
FDMA
4 users
frequency
time
TDMA
frequency
time
Introduction
1-21
Network Core: Packet Switching
each end-end data stream
divided into packets
 user A, B packets share
network resources
 each packet uses full link
bandwidth
 resources used as needed
Bandwidth division into “pieces”
Dedicated allocation
Resource reservation
resource contention:
 aggregate resource
demand can exceed
amount available
 congestion: packets
queue, wait for link use
 store and forward:
packets move one hop
at a time
 transmit over link
 wait turn at next
link
Introduction
1-22
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.
Introduction
1-23
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
 circuit-switching:
 10 users
N users
1 Mbps link
 packet switching:
 with 35 users,
probability > 10 active
less than .0004
Introduction
1-24
Packet switching versus circuit switching
Is packet switching always better?
 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 guarantee bandwidth and Quality Of
Service (QOS)? (easy with circuit switching!)
 Needed for audio/video apps
 Still an unsolved problem (chapter 6)

Introduction
1-25
Packet-switching: store-and-forward
L
R
 Takes L/R seconds to
R
transmit (push out)
packet of L bits on to
link of R bps
 Entire packet must
arrive at router before
it can be transmitted
on next link: store and
forward
 End to end delay =
(#hops)*L/R
R
Example:
 L = 7.5 Mbits
 R = 1.5 Mbps
 One link (hop):
L/R=5sec
 End to end delay =
3*L/R=15 sec
Introduction
1-26
Packet Switching: Message Segmenting
and Pipelining
Now break up the message
into 5000 packets
 Each packet 1,500 bits
 1 msec to transmit




packet on one link
pipelining: each link
works in parallel
5 sec for each link
E2E Delay=5+0.001*2
Delay reduced from 15
sec to 5.002 sec
Introduction
1-27
Packet-switched networks: routing
 Goal: move packets through routers from source to
destination (using which path?)

we’ll study several path selection (i.e. routing) algorithms
(chapter 4)
 datagram network/routing:
 destination address in packet determines next hop
 routes may change during session
 analogy: driving, asking directions
 virtual circuit network/routing:
 each packet carries tag (virtual circuit ID), tag
determines next hop
 fixed path determined at call setup time, remains fixed
thru call
 routers maintain per-call state
Introduction
1-28
Chapter 1: roadmap
1.1 What is the Internet?
1.3 Network core
1.2 Network edge
1.4 Network access and physical media
1.5 Internet structure and ISPs
1.6 Delay & loss in packet-switched networks
1.7 Protocol layers, service models
1.8 History
Introduction
1-29
The network edge:
 end systems (hosts):


Provide transport services
To application programs
• e.g. Web, email

Idea: Do most work at edge
 client/server model


client host requests, receives
service from always-on server
e.g. Web browser/server; email
client/server
 peer-peer model:


Both sides `equal`
E.g. `ad-hoc network` between
palmtop personal devices
Introduction
1-30
connection-oriented transport service
Goal: reliable 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 byte-
stream data transfer

loss: acknowledgements and
retransmissions
 flow control:
 sender won’t overwhelm
receiver
 congestion control:
 senders “slow down sending
rate” when network congested
 Prevents increased congestion
 Improves performance to all
(if all use it and delay, loss are
mainly due to congestion)
Introduction
1-31
connectionless transport service
Goal: data transfer between
end systems

same as before!
 UDP - User Datagram
Protocol [RFC 768]:
Internet’s connectionless
service
 unreliable data transfer
• Don’t resend (phone,…)


 HTTP (Web), FTP (file
transfer), Telnet
(remote login), SMTP
(email)
App’s using UDP:
no flow control
no congestion control
 streaming media,
Simple, small
Other transport services
• TCP congestion control
harmful if delay, loss
NOT due to congestion!

App’s using TCP:
teleconferencing, DNS,
Internet telephony
Introduction
1-32
Network Taxonomy
Telecommunication
networks
Circuit-switched
networks
FDM
TDM
•Internet is Packet-switched, Datagram
network
•Transport services (on end-systems):
•connection-oriented (TCP)
•connectionless (UDP)
•Recently: others (DCCP, SCP)
Packet-switched
networks
Networks
with VCs
TCP
Connection
Service
Datagram
Networks
UDP
Connection-less
Service
Introduction
1-33
Lecture 1: Main concepts




Network, internet, Internet, intranet
What’s a protocol?
Network edge, core
Network transport services


Connectionless (UDP) and connection (TCP)
Client/server vs. Peer to Peer
 Routing and switching
 Router: connects two different networks in internet
 Packet-switching versus circuit-switching (FDM,TDM)
 Packet-switching:
• Datagram vs. virtual circuit (VC)
• Packet segmentation and pipelining
 Use book and course site (in Hi-Learn system)
Introduction
1-34
Chapter 1: roadmap
1.1 What is the Internet?
1.2 Network edge
1.3 Network core
1.4 Network access and physical media
1.5 Internet structure and ISPs
1.6 Delay & loss in packet-switched networks
1.7 Protocol layers, service models
1.8 History
Introduction
1-35
Internet History
1961-1972: Early packet-switching principles
 1961: Kleinrock - queueing
theory shows
effectiveness of packetswitching
 1964: Baran - packetswitching in military nets
 1967: ARPAnet conceived
by Advanced Research
Projects Agency
 1969: first ARPAnet node
operational
 1972:




ARPAnet demonstrated
publicly
NCP (Network Control
Protocol) first hosthost protocol
first e-mail program
ARPAnet has 15 nodes
Introduction
1-36
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
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
required to
interconnect networks
 best effort service
model
 stateless routers
 decentralized control
define today’s Internet
architecture
Introduction
1-37
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 name-to-IPaddress translation
1985: FTP protocol
defined
1988: TCP congestion
control
 new national networks:
Csnet, BITnet,
NSFnet, Minitel
 100,000 hosts
connected to
confederation of
networks
Introduction
1-38
Internet History
1990, 2000’s: commercialization, the Web, new apps
 Early 1990’s: ARPAnet
decommissioned
 1991: NSF lifts restrictions on
commercial use of NSFnet
(decommissioned, 1995)
 early 1990s: Web
 hypertext [Bush 1945, Nelson
1960’s]
 HTML, HTTP: Berners-Lee
 1994: Mosaic, later Netscape
 late 1990’s:
commercialization of the Web
Late 1990’s – 2000’s:
 more killer apps: instant
messaging, peer2peer
file sharing (e.g.,
Naptser)
 network security to
forefront
 est. 50 million host, 100
million+ users
 backbone links running
at Gbps
Introduction
1-39