ECE 465/565
Computer Networks and
Protocols
Thinh Nguyen
Email: thinhq@[Link]
Electrical Engineering and Computer Science
Oregon State University
Introduction 1-1
Office hours
My office hours: Th: 10-12 Kelley
Engineering Center 3115
TA office hours:???
Name: Dong Nguyen
Email: nguyendo@[Link]
Class homepage
[Link]
Introduction 1-2
Text
Computer
Networking: A Top
Down Approach
Featuring the
Internet,
3rd edition.
Jim Kurose, Keith
Ross
Addison-Wesley, July
2004.
Introduction 1-3
Why Should You Learn About
Communication Networks?
Even with the dot com bust, opportunities in
network and communication fields still continue
to expand.
Cool apps: IP-TV, real time voice and video over
the Internet.
[Link]
[Link]
Wireless Internet! Information access from
anywhere, any time.
Many more ! Introduction 1-4
Course Objectives
Understand and be able to analyze principles
and designs of computer networks, in particular
the Internet.
Understand various networking standards and
technologies (e.g. HTTP, WiFi, …)
Understand and be able to write simple network
programs.
Get a job $$$
Conduct research in networking
Have fun
Introduction 1-5
Course Outline
Introduction (1 week)
Application Layer (2 weeks) (HTTP, FTP, …)
Transport Layer (2 weeks) (TCP, UDP, …)
Network Layer (2 weeks) (Routing, …)
Link Layer (1 week) (MAC, fragmentation,
Physical Layer (1 lecture) (Optical communication
Syllabu
s
[Link]
Feedback
[Link]
Introduction 1-6
What is a communication
network?
Communication networks are arrangements of hardware and
software that allow users to exchange information,
E.g. Telephone network, office LANs, …
The Internet!
Introduction 1-7
Top Down Approach
A B
Application Application
Transport Transport
Network Network
Link Link
Physical Physical
Introduction 1-8
Chapter 1: Introduction
Our goal: Overview:
get “feel” and what’s the Internet
terminology what’s a protocol?
more depth, detail network edge
later in course network core
approach: access net, physical media
use Internet as Internet/ISP structure
example performance: loss, delay
protocol layers, service
models
network modeling
Introduction 1-9
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-10
What’s the Internet: “nuts and bolts”
view
millions of connected
router
workstation
computing devices:
server
hosts = end systems mobile
running network apps local ISP
communication links
fiber, copper, radio,
satellite regional ISP
transmission rate =
bandwidth
routers: forward
packets (chunks of
data) company
network
Introduction 1-11
What’s the Internet: “nuts and bolts”
view
protocols control sending, router
workstation
receiving of msgs
server
e.g., TCP, IP, HTTP, FTP, mobile
PPP local ISP
Internet: “network of
networks”
loosely hierarchical regional ISP
public Internet versus
private intranet
Internet standards
RFC: Request for comments
IETF: Internet Engineering
company
Task Force
network
Introduction 1-12
What’s the Internet: a service view
communication
infrastructure enables
distributed applications:
Web, email, games, e-
commerce, file sharing
communication services
provided to apps:
Connectionless unreliable
connection-oriented
reliable
Introduction 1-13
What’s a protocol?
human protocols: network protocols:
“what’s the time?” machines rather than
“I have a question” humans
all communication
introductions
activity in Internet
governed by protocols
… specific msgs sent
… specific actions protocols define format,
taken when msgs order of msgs sent and
received, or other received among
events network entities, and
actions taken on msg
transmission, receipt
Introduction 1-14
What’s a protocol?
a human protocol and a computer network protocol:
What’s up!
TCP connection
Not req
Themuch
sky
TCP connection
Got???
the response
time? Get [Link]
???
2:00
<file>
time
Q: Other human protocols?
Introduction 1-15
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-16
A closer look at network
structure:
network edge:
applications and hosts
network core:
routers
network of networks
access networks,
physical media:
communication links
Introduction 1-17
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-peer model:
minimal (or no) use of
dedicated servers
e.g. Gnutella, KaZaA
Introduction 1-18
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-19
The Network Core
mesh of interconnected
routers
the fundamental
question: 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-20
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
Introduction 1-21
Network Core: Circuit Switching
network resources dividing link
(e.g., bandwidth) bandwidth into
divided into “pieces”
“pieces” frequency division
pieces allocated to time division
calls
resource piece idle if
not used by owning
call (no sharing)
Introduction 1-22
Circuit Switching: FDM and TDM
Example:
FDM
4 users
frequency
time
TDM
frequency
time
Introduction 1-23
Numerical example
How long does it take to send a file of
640,000 bits from host A to host B over
a circuit-switched network?
Alllinks are 1.536 Mbps
Each connection uses TDM with 24 slots
500 msec to establish end-to-end circuit
Work it out!
500 msec + 24*640,000/1.536Mbps
Introduction 1-24
Network Core: Packet Switching
each end-end data stream resource contention:
divided into packets aggregate resource
user A, B packets share demand can exceed
network resources amount available
each packet uses full congestion: packets
link bandwidth queue, wait for link
resources used as use
needed store and forward:
packets move one
Bandwidth division into “pieces” hop at a time
Dedicated allocation Node receives complete
Resource reservation packet before forwarding
Introduction 1-25
Packet Switching: Statistical
Multiplexing
10 Mb/s
A Ethernet statistical multiplexing C
1.5 Mb/s
B
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-26
Packet switching versus circuit
switching
Packet switching allows more users to use network!
1 Mb/s link
each user:
100 kb/s when
“active”
active 10% of time
N users
circuit-switching:
1 Mbps link
10 users
packet switching:
with 35 users,
probability > 10
active less than .0004
Introduction 1-27
Packet switching versus circuit
switching
Is packet switching a “slam dunk winner?”
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
Introduction 1-28
Packet-switching: store-and-
forward
L
R R R
Takes L/R seconds to Example:
transmit (push out) L = 7.5 Mbits
packet of L bits on to R = 1.5 Mbps
link or R bps
delay = 15 sec
Entire packet must
arrive at router before
it can be transmitted Why store-and-forward?
on next link: store In other word, why not just
and forward transmit the bit immediately
delay = 3L/R after the router receives it?
Introduction 1-29
Packet-switched networks:
forwarding
Goal: move packets through routers from source to
destination
we’ll study several path selection (i.e. routing) algorithms
(chapter 4)
datagram network:
destination address in packet determines next hop
routes may change during session ( e.g. due to congestion)
analogy: driving, asking directions
virtual circuit network:
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 (all the necessary information
for routing packets)
Introduction 1-30
Network Taxonomy
Telecommunication
networks
Circuit-switched Packet-switched
networks networks
FDM Networks Datagram
TDM
with VCs Networks
Introduction 1-31
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-32
Access networks and physical media
Q: How to connect end
systems to edge
router?
residential access nets
institutional access
networks (school,
company)
mobile access networks
Keep in mind:
bandwidth (bits per
second) of access
network?
shared or dedicated?
Introduction 1-33
Residential access: point to point
access
Dialup via modem
up to 56Kbps direct access
to router (often less)
Can’t surf and phone at
same time: can’t be
“always on”
ADSL: asymmetric digital subscriber line
up to 1 Mbps upstream (today typically < 256 kbps)
up to 8 Mbps downstream (today typically < 1 Mbps)
FDM: 50 kHz - 1 MHz for downstream
4 kHz - 50 kHz for upstream
0 kHz - 4 kHz for ordinary telephone
Introduction 1-34
Range: 18000 feet (1.5Mbps) to 9000 feet (8 Mbps)
Residential access: cable modems
HFC: hybrid fiber coax
asymmetric: up to 30Mbps downstream,
2 Mbps upstream
network of cable and fiber attaches homes
to ISP router
homes share access to router
deployment: available via cable TV
companies
Introduction 1-35
Residential access: cable modems
Diagram: [Link] Introduction 1-36
Cable Network Architecture: Overview
Typically 500 to 5,000 homes
cable headend
home
cable distribution
network (simplified)
Introduction 1-37
Cable Network Architecture: Overview
cable headend
home
cable distribution
network (simplified)
Introduction 1-38
Cable Network Architecture: Overview
server(s)
cable headend
home
cable distribution
network
Introduction 1-39
Cable Network Architecture: Overview
Downstream: 50 to
FDM: 750 Mhz
C Upstream: 4 to 42
Security! V V V V V V
O
N Hz
I I I I I I D D T
Data Over Cable D D D D D D A
T
A
T
R
O
Service Interface
E
O
E
O
E
O
E
O
E
O
E
O A A L Distance???
Specification 1 2 3 4 5 6 7 8 9
If you have
(DOCSIS). Channels
Cable TV,
you are set
cable headend
home
cable distribution
network
Introduction 1-40
Company access: local area networks
company/univ local area
network (LAN) connects
end system to edge
router
Ethernet:
shared or dedicated
link connects end
system and router
10 Mbs, 100Mbps,
Gigabit Ethernet
LANs: chapter 5
Introduction 1-41
Wireless access networks
shared wireless access
network connects end
system to router
via base station aka “access router
point”
wireless LANs: base
802.11b, g (WiFi): 11 Mbps, 54 station
Mbps, 802.11e (voice over
wireles)
wider-area wireless access
provided by telco operator
3G ~ 384 kbps mobile
4G ~20Mbps ??? hosts
WAP/GPRS in Europe
Introduction 1-42
Home networks
Typical home network components:
ADSL or cable modem
router/firewall/NAT
Ethernet
wireless access
point
wireless
to/from laptops
cable router/
cable
modem firewall
headend
wireless
access
Ethernet point
Introduction 1-43
Physical Media
Twisted Pair (TP)
Bit: propagates between two insulated copper
transmitter/rcvr pairs wires
physical link: what lies Category 3: traditional
between transmitter & phone wires, 10 Mbps
receiver Ethernet
guided media:
Category 5:
100Mbps Ethernet
signals propagate in solid
media: copper, fiber, coax
unguided media:
signals propagate freely,
e.g., radio
Introduction 1-44
Physical Media: coax, fiber
Fiber optic cable:
Coaxial cable: glass fiber carrying light
two concentric copper pulses, each pulse a bit
conductors high-speed operation:
bidirectional high-speed point-to-point
transmission (e.g., 5 Gps)
baseband:
low error rate: repeaters
single channel on cable
spaced far apart ; immune
legacy Ethernet to electromagnetic noise
broadband:
multiple channel on
cable
HFC
Introduction 1-45
Physical media: radio
signal carried in Radio link types:
terrestrial microwave
electromagnetic e.g. up to 45 Mbps channels
spectrum LAN (e.g., Wifi)
2Mbps, 11Mbps
no physical “wire”
wide-area (e.g., cellular)
bidirectional e.g. 3G: hundreds of kbps
satellite
propagation
up to 50Mbps channel (or multiple
environment effects: smaller channels)
270 msec end-end delay
reflection geosynchronous versus low altitude
obstruction by objects
interference
Introduction 1-46
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-47
Internet structure: network of
networks
roughly hierarchical
at center: “tier-1” ISPs (e.g., UUNet, BBN/Genuity,
Sprint, AT&T), national/international coverage
treat each other as equals
Tier-1 providers
also interconnect
Tier-1 at public network
providers
Tier 1 ISP
NAP access points
interconnec (NAPs)
t (peer)
privately
Tier 1 ISP Tier 1 ISP
Introduction 1-48
Tier-1 ISP: e.g., Sprint
Sprint US backbone network
Introduction 1-49
Internet structure: network of
networks
“Tier-2” ISPs: smaller (often regional) ISPs
Connect to one or more tier-1 ISPs, possibly other tier-2 ISPs
Tier-2 ISPs
Tier-2 ISP pays Tier-2 ISP also peer
Tier-2 ISP privately with
tier-1 ISP for
connectivity to Tier 1 ISP each other,
rest of Internet NAP interconnect
tier-2 ISP is at NAP
customer of
tier-1 provider Tier 1 ISP Tier 1 ISP Tier-2 ISP
Tier-2 ISP Tier-2 ISP
Introduction 1-50
Internet structure: network of
networks
“Tier-3” ISPs and local ISPs
last hop (“access”) network (closest to end systems)
local
ISP Tier 3 local
local local
ISP ISP
ISP ISP
Local and Tier-2 ISP Tier-2 ISP
tier- 3 ISPs
are Tier 1 ISP
customers of NAP
higher tier
ISPs
connecting
Tier 1 ISP Tier 1 ISP Tier-2 ISP
them to rest
of Internet local
Tier-2 ISP Tier-2 ISP
ISP
local local local
ISP ISP ISP Introduction 1-51
Internet structure: network of
networks
a packet passes through many networks!
local
ISP Tier 3 local
local local
ISP ISP
ISP ISP
Tier-2 ISP Tier-2 ISP
Tier 1 ISP
NAP
Tier 1 ISP Tier 1 ISP Tier-2 ISP
local
Tier-2 ISP Tier-2 ISP
ISP
local local local
ISP ISP ISP Introduction 1-52
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-53
How do loss and delay occur?
packets queue in router buffers
packet arrival rate to link exceeds output link
capacity
packets queue, wait for turn
packet being transmitted (delay)
B
packets queueing (delay)
free (available) buffers: arriving packets
dropped (loss) if no free buffers
Introduction 1-54
Four sources of packet delay
1. nodal processing: 2. queueing
check bit errors time waiting at output
determine output link link for transmission
depends on congestion
level of router
transmission
A propagation
B
nodal
processing queueing
Introduction 1-55
Delay in packet-switched
networks
3. Transmission delay: 4. Propagation delay:
R=link bandwidth d = length of physical
(bps) link
L=packet length (bits) s = propagation speed in
time to send bits into medium (~2x108 m/sec)
link = L/R propagation delay = d/s
Note: s and R are very
different quantities!
transmission
A propagation
B
nodal
processing queueing Introduction 1-56
Caravan analogy
100 100
km km
ten-car toll toll
caravan booth booth
Cars “propagate” at Time to “push” entire
100 km/hr caravan through toll
Toll booth takes 12 sec to booth onto highway =
service a car 12*10 = 120 sec
(transmission time) Time for last car to
car~bit; caravan ~ packet propagate from 1st to
Q: How long until caravan 2nd toll both:
is lined up before 2nd toll 100km/(100km/hr)= 1 hr
booth? A: 62 minutes
Introduction 1-57
Caravan analogy (more)
100 100
km km
ten-car toll toll
caravan booth booth
Yes! After 7 min, 1st car
Cars now “propagate”
at 2nd booth and 3 cars
at still at 1st booth.
1000 km/hr 1st bit of packet can
Toll booth now takes 1
arrive at 2nd router
min to service a car before packet is fully
Q: Will cars arrive to transmitted at 1st
2nd booth before all router!
cars serviced at 1st
booth?
Introduction 1-58
Nodal delay
d nodal d proc d queue d trans d prop
dproc = processing delay
typically a few microsecs or less
dqueue = queuing delay
depends on congestion
dtrans = transmission delay
= L/R, significant for low-speed links
dprop = propagation delay
a few microsecs to hundreds of msecs
Introduction 1-59
Queueing delay (revisited)
R=link bandwidth (bps)
L=packet length (bits)
a=average packet
arrival rate
traffic intensity = La/R
La/R ~ 0: average queueing delay small
La/R -> 1: delays become large
La/R > 1: more “work” arriving than can
be serviced, average delay infinite!
Introduction 1-60
“Real” Internet delays and
routes
What do “real” Internet delay & loss look like?
Traceroute program: provides delay
measurement from source to router along end-
end Internet path towards destination. For all i:
sends three packets that will reach router i on path
towards destination
router i will return packets to sender
sender times interval between transmission and reply.
3 probes 3 probes
3 probes
Introduction 1-61
“Real” Internet delays and
routes
traceroute: [Link] to [Link]
Three delay measements from
[Link] to cs-
[Link]
1 cs-gw ([Link]) 1 ms 1 ms 2 ms
2 [Link] ([Link]) 1 ms 1 ms 2 ms
3 [Link] ([Link]) 6 ms 5 ms 5 ms
4 [Link] ([Link]) 16 ms 11 ms 13 ms
5 [Link] ([Link]) 21 ms 18 ms 18 ms
6 [Link] ([Link]) 22 ms 18 ms 22 ms
7 [Link] ([Link]) 22 ms 22 ms 22 ms trans-oceanic
8 [Link] ([Link]) 104 ms 109 ms 106 ms
9 [Link] ([Link]) 109 ms 102 ms 104 ms link
10 [Link] ([Link]) 113 ms 121 ms 114 ms
11 [Link] ([Link]) 112 ms 114 ms 112 ms
12 [Link] ([Link]) 111 ms 114 ms 116 ms
13 [Link] ([Link]) 123 ms 125 ms 124 ms
14 [Link] ([Link]) 126 ms 126 ms 124 ms
15 [Link] ([Link]) 135 ms 128 ms 133 ms
16 [Link] ([Link]) 126 ms 128 ms 126 ms
17 * * *
18 * * * * means no reponse (probe lost, router not
19 [Link] replying)
([Link]) 132 ms 128 ms 136 ms
Introduction 1-62
Packet loss
queue (aka buffer) preceding link in
buffer has finite capacity
when packet arrives to full queue,
packet is dropped (aka lost)
lost packet may be retransmitted by
previous node, by source end system,
or not retransmitted at all
Introduction 1-63
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-64
Protocol “Layers”
Networks are
complex!
many “pieces”:
Question:
hosts
Is there any hope of
routers organizing structure of
links of various network?
media
Or at least our discussion
applications
of networks?
protocols
hardware,
software
Introduction 1-65
Organization of air travel
ticket (purchase) ticket (complain)
baggage (check) baggage (claim)
gates (load) gates (unload)
runway takeoff runway landing
airplane routing airplane routing
airplane routing
a series of steps
Introduction 1-66
Layering of airline
functionality
ticket (purchase) ticket (complain) ticket
baggage (check) baggage (claim baggage
gates (load) gates (unload) gate
runway (takeoff) runway (land) takeoff/landing
airplane routing airplane routing airplane routing airplane routing airplane routing
departure intermediate air-traffic arrival
airport control centers airport
Layers: each layer implements a service
via its own internal-layer actions
relying on services provided by layer below
Introduction 1-67
Why layering?
Dealing with complex systems:
explicit structure allows identification,
relationship of complex system’s pieces
layered reference model for discussion
modularization eases maintenance, updating
of system
change of implementation of layer’s service
transparent to rest of system
e.g., change in gate procedure doesn’t
affect rest of system
layering considered harmful?
Introduction 1-68
Internet protocol stack
application: supporting network
applications application
FTP, SMTP, STTP
transport: host-host data transfer transport
TCP, UDP
network: routing of datagrams network
from source to destination
IP, routing protocols link
link: data transfer between
neighboring network elements physical
PPP, Ethernet
physical: bits “on the wire”
Introduction 1-69
source
message M applicatio
Encapsulation
segment Ht M n
datagram Hn Ht M transport
frame H l Hn H t M network
link
physical H l Hn H t M link H l Hn H t M
physical
switch
destination Hn H t M network H n Ht M
M applicatio
H l Hn H t M link H l Hn H t M
Ht M n physical
H n Ht M transport
H l Hn H t M network router
link
physical
Introduction 1-70
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-71
Internet History
1961-1972: Early packet-switching principles
1961: Kleinrock - 1972:
queueing theory shows ARPANET
effectiveness of packet- demonstrated publicly
switching NCP (Network Control
1964: Baran - packet-
Protocol) first host-
switching in military host protocol
nets first e-mail program
1967: ARPANET
ARPANET has 15
conceived by Advanced
nodes
Research Projects
Agency 1969: first
ARPANET node
operational
Introduction 1-72
Internet History
1972-1980: Internetworking, new and proprietary
nets
1970: ALOHAnet satellite
Cerf and Kahn’s
network in Hawaii
internetworking
1973: Metcalfe’s PhD thesis principles:
proposes Ethernet minimalism, autonomy
1974: Cerf and Kahn -
- no internal changes
architecture for
required to
interconnecting networks
interconnect networks
late70’s: proprietary best effort service
architectures: DECnet, SNA,
XNA model
stateless routers
late 70’s: switching fixed
length packets (ATM decentralized control
precursor) define today’s Internet
1979: ARPANET has 200 architecture
nodes
Introduction 1-73
Internet History
1990, 2000’s: commercialization, the Web, new
apps
Early 1990’s: ARPANET
Late 1990’s – 2000’s:
decommissioned more killer apps: instant
1991: NSF lifts restrictions on
messaging, P2P file
commercial use of NSFnet sharing
(decommissioned, 1995)
network security to
early 1990s: Web
forefront
hypertext [Bush 1945,
est. 50 million host, 100
Nelson 1960’s]
million+ users
HTML, HTTP: Berners-Lee
backbone links running at
1994: Mosaic, later
Gbps
Netscape
late 1990’s:
commercialization of the Web
Introduction 1-74
Introduction: Summary
Covered a “ton” of material! You now have:
Internet overview context, overview,
what’s a protocol? “feel” of networking
network edge, core, more depth, detail
access network to follow!
packet-switching
versus circuit-switching
Internet/ISP structure
performance: loss, delay
layering and service
models
history
Introduction 1-75